Necessity

There is a difference between mechanism and policy. In IEEE802.15.4e, the mechanism is how to synchronize the network, and enable channel hopping; the policy is how to use the resulting slotted organization to efficiently transport data over multiple hops. IEEE802.15.4e defines the mechanisms, but not the policy.

The figure below presents a simple case of a 8-node IEEE802.15.4e network with a slot frame length of 10 slots. IEEE802.15.4e defines how nodes synchronize; because on each slot, a node has a choice of 16 frequency channels, this results in a grid structure, with time on the x-axis, and frequency on the y-axis. IEEE802.15.4e does not specify how these cells are to be used: a mechanism is missing which allows each pair of neighbor nodes to agree on cells to communicate on. Agreeing is necessary because the transmitter will need to transmit at the same time and frequency as the receiver is listening. Each slot only allows the transmission of data in one direction, so if two nodes want to establish bidirectional connectivity, they need to schedule at least two cells, one in each direction.

IEEE802.15.4e does not specify how such distributed scheduling should happen. Because the next upper layer (6LoWPAN) assumes that all nodes are capable to communicating with all of their neighbors, there is a "gap" to be filled to glue IEEE802.15.4e to the upper stack. This Section describes a protocol which we have developed, called uRES, which allows each node to establish bidirectional connectivity with all of its neighbors.

A slot in the scheduling table of a node can take one of the following states:

• ADV, a slot shared by all the nodes in the network to exchange advertisement packets on a shared channelOffset;
• RES, a slot used by a node to receive uRES packets from any of its neighbors, on a channelOffset announced in its advertisement packets;
• TX, a transmit slot to a specific neighbor, on a specific channelOffset;
• RX, a reception slot from a specific neighbor, on a specific channelOffset;
• OFF, no activity, the radio stays off.

When a node has just joined a network, the first slot in its slotframe is of type ADV, the second of type RES, and all the rest are of type OFF. uRES is used to populate the OFF slots, so that a node has exactly one TX slot to each neighbor and one RX slot from each neighbor. uRES packets are exchanged exclusively in the RES slot of the slotframe.

Procedure of uRes

The following is an example which shows the procedure when mote-6 joins in network, where mote-4 and mote-5 are in radio range of mote-6.

There are two methods to establish the links.

• Fast join in: after mote-6 receives Advertisement BEACON and synchronizes to existing network, it should use the links described by Slotframe and Link IE in the Advertisement BEACON to send data packets.
• Reservation:
  • mote-6 may use the link described by Slotframe and Link IE in the Advertisement to send Reserve Link Request. After obtaining the information of all Slotframe and reservaed links in each Slotframe carried in Reserve Link Response packet, mote-6 maysend/receive data on the reserved links.
  • If mote-6 wants more links for QoS, it may start link reservation again, in which, the process of Schedule Request and Schedule Schedule Response may be included. The Reservation procedure should be initialized by upper layer when a certain bandwidth with particular neighbor is / is not needed; or initialized by uRes self when certain links are found in bad link quality.

The procedure may involves 6 related packets, including, Advertisement BEACON, ResLinkReq, ResLinkResp, RemoveLinkReq, ScheduleReq (option), ScheduleResp. (option)

Considering the integrity of IEEE802.15.4 specification, uRes related packets must be coded in Information Elements (IE). The IEs of Advertisement packets must be carried by payload IEs of BEACON, and the IEs of other packets above must carried by payload IEs of DATA.

Information Elements

The related IEs are defined as follows

1. TSCH Synchronization IE (Sync IE)
   
   Descriptor (2B): 

   • b0-7, length = 6
   • b8-14, subID = 0x1a
   • b15, type = 0 (short)
   • IE Content (6B):
     • ASN (5B), little endian
     • Join priority (1B)
       
       

2. TSCH slotframe and link IE (Frame&Link IE)
   
   Descriptor (2B):

   • • b0-7, length =  variable
     • b8-14, subID = 0x1b
     • b15, type = 0 (short)
     • IE Content (variable):
       • Number of Slotframes (1B) = variable
       • Slotframe Info. and Links for each Slotframe
         • Slotframe ID (1B)
         • Size (2B)
         •  # of links (1B)
         • Link(s)
   • • • • • Channel Offset (2B)
           •  Timeslot (2B)
           •  Link Options (1B)
             • Bit 0: TX = 1
             • Bit 1: RX = 1
             • Bit 2: shared = 1
             • Bit 3: Timekeeping = 1
             • Bits 3-7: 0
   
   
   

3. TSCH Timeslot Template IE (Timeslot IE)
   
   Descriptor (2B): 

   • b0-7, length = 1
   • b8-14, subID = 0x1c
   • b15, type = 0 (short)
   • IE Content (1B):
     • Timeslot template ID (1B) = 0x00, the 10 ms default slot defined in the spec. 
     • Other fields elided
       
       

4. Channel hopping IE (Ch-Hopping IE)
   
   Descriptor (2B): 

   • b0-10, length =  1
   • b11-14, subID = 0x9
   • b15, type = 1 (long)
   • IE Content (1B/8B):
     • Hopping sequence ID (1B) = 0x01 – this is taken to mean channels 11-25 in order, such that for offset 0, the channel used at ASN=0 is channel 11.
   
   
   

5.  LinkType IE
   
   Descriptor (2B):

   • • b0-7, length =  variable
     • b8-14, subID = 0x40
     • b15, type = 0 (short)
     • IE Content (variable):
       • Number of Slotframes (1B) = variable
       • Slotframe Info. and Links for each Slotframe
         • Slotframe ID (1B), same as that in Frame&Link IE in the same Advertisement BEACON
         • # of links (1B), , same as that in Frame&Link IE in the same Advertisement BEACON
           •  Link(s)
           •  Channel Offset (2B), same as that in Frame&Link IE in the same Advertisement BEACON
           •  Timeslot (2B), , same as that in Frame&Link IE in the same Advertisement BEACON
           • LinkType (1B)

    

   	Link Type
   0x00	Advertisement
   0x01	TX
   0x02	RX
   0x03	TXRX

   
   
   

6. uRes command IE (uRes-Cmd IE)
   
   Descriptor (2B): 

   • • b0-7, length =  1
     • b8-14, subID = 0x41
     • b15, type = 0 (short)
     • IE Content (1B):
       • uRes command ID (1B)

    

   Command ID	function
   0x00	Reserve Link Request
   0x01	Reserve Link Response
   0x02	Remove Link Request
   0x03	Schedule Request
   0x04	Schedule Response

   
   
   

7. uRes Bandwidth IE
   
   Descriptor (2B): 

   • b0-7, length =  2
   • b8-14, subID = 0x42
   • b15, type = 0 (short)
   • IE Content (2B):
     • Slotframe ID (1B)
     • # of links (1B)
   
   
   

8. uResGeneral Schedule IE (Schedule IE)
   
   Descriptor (2B): 

   • • b0-7, length = variable
     • b8-14, subID = 0x43
     • b15, type = 0 (short)
     • IE Content (variable):
       • Compression Type (1B)

   When Compression Type =0x00, i.e. BitMap

   • • • • Slotframe ID (1B)
         • Size (2B)
         • StartSlotOffset (2B)
         • # of Slot (1B)
         • BitsOnOneSlot(s)
           • BitMap ofchannel 11-18 (1B)
           • BitMap of channel 19-26 (1B)

uRes Packets

The IEs in each packet are summarized as follows.

Since Slotframe and Link IE (Frame&Link IE) is used in multiple packets, we define its coding and function in each packet as follows.

Frame&Link IE in advertisement provides one slotframe information and the link(s) in the slotframe for mote to join in network.Frame&Link IE in ResLinkReq defines the proposed candidate link list, from which the destination mote will choose links for reservation. Frame&Link IE in RemoveLinkReq defines the links, which will be removed. Function of Frame&Link IE in ResLinkResp packet defines every slotframe by (Slotframe ID, Size), which the associated mote can use and defines Links, which the associated mote can use. The Frame&Link in ScheduleResp lists all of links used by the sender of the packet.

In addition, General Schedule IE can be used as alternative of Frame&Link IEs in the packets except advertisement BEACON.

General Schedule IE explanation

As alternative of Frame&Link IE, General Schedule IE will represent different information in different packets.

• When it is used in ResLinkReq, it represents the proposed candidate listin specified slotframe.
• When it is used in RemoveLinkReq, it represents the links to be removed in specified slotframe.
• When it is used in ResLinkResp, it represents the reserved links in specified slotframe.
• When it is used in ScheduleResp, it represents all of links in some time interval.

For example, type=0x00, i.e. BItMap.Since a mote may use multiple Slotframes, BitMap will be the results of overlapping the link usage in every Slotframe. Thus, SlotframeID must be set as 0xFF. Here is an example. Assume number of channel is 8, and there are two Slotframes, the first one size=12, and the second one size=36, the BitMap IE example is shown as follows.

FSM of reservation and related functions

The figure below illustrates the finite-state machine of reservation. Res circles indicate state; green rounded rectangles indicate reservation commands and notification of command reception. Blue rectangles indicate middle procedures of reservation.

Reservation module starts with an “IDLE” state. Reservation module is driven by button interrupt. When you press button, reservation module will check variable “button_event”.

pseudo-code:

Switch button_event:

Case 0:

Case 1:sending “Link Request” command.

Case 2:sending “remove links” command.

Default: sending a data at a TX slot, not at a TXRX slot.

Button_event++;

"Link Request" command

When a “Link Request” command is triggered, reservation module will do serial procedures to generate a “Link Request” message.

1. Get a free msg (OpenQueueEntry).
2. Generate candidate links.
3. Set frame&link IE, uRes command IE and bandwidth IE.
4. Put IE into msg->l2payload.
5. Delivery msg to res by calling res_send(). 

"Remove Link" command

When a “Remove Link” command is triggered, reservation module will do serial procedures to generate a “Remove Link” message.

1. Get a free msg (OpenQueueEntry).
2. Generate links to be removed.
3. Set frame&link IE and uRes command IE.
4. Put IE into msg->l2payload.
5. Delivery msg to res by calling res_send().

"Link Response" command

When calling “Link Response” command, reservation module will do serial procedures to generate a “Link Response” message.

1. Get a free msg (OpenQueueEntry).
2. Set frame&link IE, uRes command IE. (Before calling “Link Response” command, links have been generated already.)
3. Put IE into msg->l2payload.
4. Delivery msg to res by calling res_send(). 

Function "reservation_sendDone()"

This function is called by task_resNotifSendDone(). It will check the variable “State”.

pseudo-code:

Switch State:

Case S_WAIT_RESLINK REQUEST_SENDDONE:

Chang state to S_WAIT_FORRESPONSE.

Case S_WAIT_RESLINK RESPONSE_SENDDONE

Chang state to S_IDLE.

Casse S_WAIT_REMOVE LINK REQUEST_SENDDONE

Chang state to S_IDLE.

 Function "notifyReceiveuResCommand()"

When received a uRes command, reservation module will check variable “uResCommandID”.

pseudo-code:

Switch uResCommandID:

Case 0: this is “Link Request” command, calling “notifyreceiveuResLink Request”.

Case 1: this is “Link Response” command, calling “notifyReceiveuResLink Response”.

Case 2: this is “remove link” command, calling “notifyReceiveRemove Link Request”.

Case 3: this is “schedule request” command.

Case 4: this is “schedule response” command.

Function "notifyReceiveuResLink Request()"

When received “Link Request” command, reservation module allocates links for sender mote. Then, reservation module adds new slots to “scheduleBuffer”, and calls “Link Response” command.

Function "notifyReceiveuResLink Response()"

When received “Link Response” command, reservation module adds new links to “scheduleBuffer”.

 Function "notifyReceiveRemove Link()"

When receive “remove link” command, reservation module removes links from “scheduleBuffer”.

 Function "reservation_pretendSendData()"

When “reservation_pretendSendData” is triggered, reservation module generates a new data message.

Function "reservation_pretendReceiveData()"

When “reservation_pretendSendData” is triggered, reservation module will print message data.

Function "res_send()"( belong to res module)

When calling “res_send()”, res module will check the creator of msg.

pseudo-code:

If(msg->creater == COMPONENT_RESERVATION)

         Send data at TXRX slot

If(msg->creater== COMPONENT_UPPERLAYER)

         Send data at TX slot

Call res_send_interval()

Reservation code url:

"https://github.com/openwsn-berkeley/openwsn-fw/blob/uRes_branch_2545/openwsn/02b-MAChigh/reservation.c",

"https://github.com/openwsn-berkeley/openwsn-fw/blob/uRes_branch_2545/openwsn/02b-MAChigh/reservation.h" 

Failsafe Components

In the implementation of uRES, a number of failsafe components are added to uRES.

Each instance of uRES has a maximum lifetime after which it is terminated. This is useful in the case when the replier disappears while the requester is waiting for its answer. In that case, the lifetime of the associated uRES instance expires, the instance is terminated and the reserved cell is returned to its initial OFF state.

Whenever a node transmits a uRES request to schedule a cells (txCommand is set to RES_ACTION_REQ_CELL), it also checks whether it has a RX cell scheduled from that same neighbor, and indicates that in the rxCommand, rxSlotOffset and rtxChannelOffset portion of the uRES message. Similarly, the replier indicates whether it has a TX cell to that neighbor in the txCommand, txSlotOffset and txChannelOffset portion of the uRES message. This allows node to opportunistically verify that their schedules are consistent.

When a node detects and inconsistency, it cancels all TX and RX slots with that neighbor and issues a uRES message with txCommand set to RES_ACTION_FREE_CELL for that neighbor. Upon receiving this message, the neighbor also cancels all TX and RX. Because the implementation regularly checks whether there is a TX slot to each stable neighbor, a node will invoke a new instance of uRES to re-establish connectivity.

This fail-safe component enabled uRES to be robust against nodes being reinitialized at any time.

An Alternative: Slotted ALOHA

uRES schedules TX and RX slots explicitly between neighbor nodes. An alternative is to declare shared reception slots among all nodes in the network. This results in a slotted ALOHA communication scheme, which may complement or replace the explicit use of uRES. Note that this scheme has not been implemented yet, but will be used for the interoperability operation.