IEEE802.15.4e

Status

IEEE802.15.4e is an active working group. It has produced its latests public draft standard in September 2011, which you can buy here. This draft standard (or a very minor revision thereof) will be adopted in the next version of the IEEE802.15.4 standard, probably by the end of 2011.

On top of the draft standard above, the following documents are of interest:

Overview

IEEE802.15.4e is a working group by the IEEE chartered to define a MAC amendment to the existing standard 802.15.4-2006 to better support industrial markets. The key element of the solution proposed by 802.15.4e is channel hopping, which significantly increases robustness against external interference and persistent multi-path fading.

Time is divided into slots; an Absolute Slot Number (ASN) is incremented at each slot and shared by all nodes. At each new slot, the frequency to be used is calculated using the equation below. channelOffset is a number between 0 and 15 which is assigned to each slot during reservation. 100 slots form a slotframe; this slotframe repeats over time.

frequency = (ASN + channelOffset)%16

During reservation, one of the slots in the slotframe of node A may be reserved for sending data to B at a given channelOffset. Every 100 slots, A can thus send to B at a frequency calculated with the equation above. The key is that ASN is incremented at each slot, so subsequent packets are sent at different frequencies.

Channel Hopping

WSNs face the challenge of ensuring reliable communication over inherently unreliably links. External interference and multi-path fading cause the quality of wireless links to change dramatically in an unpredictable way. These phenomena change depending on the frequency the nodes are communicating on. Channel hopping is a technique proven to efficiently combat the unreliable nature of wireless.

Connectivity traces were collected by J. Ortiz and D. Culler in a UC Berkeley office space (traces are made available at http://wsn.eecs.berkeley.edu/connectivity/). 46 IEEE802.15.4-compliant TelosB motes are deployed in a 50m by 50m indoor environment, and are constantly listening for packets. One after the other, each mote transmits a burst of 100 packets, with a 20ms inter-packet time and a transmission power of 0dBm, on each of the 16 frequency channels which span the 2.4-2.485GHz band. Timers are used to ensure that all nodes switch channels simultaneously. Note that, because bursts are sent in sequence, there are no collisions. All non-transmitting nodes record the timestamp of the packets received, their source address, and the frequency channel the packets are received on. After all 46 nodes have sent a burst, each node reports what packets it has received. This process is repeated in 17 runs. A single run completes in 13 minutes; several hours separate subsequent runs.

With these traces in hand, one can plot the reliability of a link depending on its frequency. Reliability can be simply expressed as the Packet Delivery Ratio (PDR): the ratio between the number of received packets and the number of sent packets. A PDR of 1 indicates a perfect link. The figure below plots the average reliability of all links, depending on their frequency. While at some frequencies (e.g. channel 26, or 2.480GHz) PDR is around 87%, it drops to close to 75% at others (e.g. channel 12, 2.415GHz). This is due to IEEE802.11 (!WiFi) activity on IEEE802.11 channels 1, 6 and 11.

For more information of how channel hopping combats external interference, please read:

  • Thomas Watteyne, Ankur Mehta, Kris Pister. "Reliability Through Frequency Diversity: Why Channel Hopping Makes Sense". Sixth ACM International Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), Tenerife, Canary Islands, Spain, 26-30 October 2009.
  • Branko Kerkez, Thomas Watteyne, Mario Magliocco, Steven Glaser, Kris Pister. "Feasibility Analysis of Controller Design for Adaptive Channel Hopping". First International Workshop on Performance Methodologies and Tools for Wireless Sensor Networks (WSNPerf), Pisa, Italy, 23 October 2009.

In an indoor environment, every wall, person, and piece of furniture acts as a reflector for RF signals. As a result, on top of the signal following the direct line-of-sight (LOS) path, a node receives multiple echoes which have bounced off nearby elements. Because the paths those echoes follow are necessarily longer than the LOS path, they arrive a bit later, typically within a few $ns$ later. This is an unwanted phenomenon, particularly in narrowband communication. If the different signals are phased appropriately, they can destructively interfere, and the receiver is unable to decode the signal even when physically close to the transmitter.

Let's consider some experimental results. A computer is connected to a fixed receiver mote; a transmitter mote is mounted on a motorized arm. At the beginning of a measurement, the arm is moved to a given location. The transmitter then transmits 1000 29-byte-long packets at a given requested frequency. The PDR is determined by the receiver as the fraction of packets that were successfully received. Each of the 1000 packets take 2.3ms to be send; one measurement (including the movement of the arm) takes 4s. This measurement is repeated for different transmitter locations inside a 20cm by 34cm plane; with a 1cm step in both directions, i.e. 735 data points are acquired.

The figure below depicts the resulting 3D plot of PDR versus transmitter location, when transmitter and receiver are separated by (only) 1m. While on most locations connectivity is good with PDR hovering around 100%, in locations just centimeters away, PDR drops to 0%.

Because multi-path fading depends entirely on the environment, it cannot be predicted without infinite knowledge of the object's location, orientation and reflective characteristics. When adding the fact that people walk around, and doors are opened and closed, predicting the location of the deep fades (the location where PDR reaches 0%) is infeasible.

Yet, this phenomenon depends on frequency. Repeating the same measurement for different frequency channels does indeed show that the "topography" of the figure above changes significantly from one channel to another. In fact, for transmitter and receiver separated by a couple of meters or more, the impact of the operating frequency is such that a frequency shift of only 5MHz (one channel in the IEEE802.15.4 standard) leads to an entirely different topography.

For more information of how channel hopping combats external interference, please read:

  • Thomas Watteyne, Steven Lanzisera, Ankur Mehta, Kris Pister. "Mitigating Multipath Fading Through Channel Hopping in Wireless Sensor Networks". IEEE International Conference on Communications (ICC), Cape Town, South Africa, 23-27 May, 2010.

In a communicating system, channel hopping should be used. In a channel hopping system, subsequent packets are sent at a different frequency, following a pseudo-random hopping pattern. This means that, if a transmission fails, retransmission will happen on a different frequency. And because a different frequency means different effects of multi-path fading and interference, this means that the transmission has a greater chance of being successful that if the retransmission happened on the same channel.

Reference

One is strongly encouraged to read the draft standard. What follows can be used as a desktop reference when implementing the protocol. Following the structure of IEEE standards, we start by defining the MAC primitives, frame formats and state before describing what all of this is actually used for.

MAC primitives

MAC primitives constitute the interface between the MAC layer and the next upper layer. Following IEEE tradition, primitives are grouped into MLME and MCPS classes (to be detailed). For each primitive name, there are possibly three calls: requestindication and confirm. When node A communicates to node B, A's next upper layer starts by _request_ing the MAC layer to send a given packet over the air; when this is done, A's MAC layer _confirm_s successful transmission. B's MAC layer _indicate_s the reception of the frame.

MLME stands for MAC sublayer management entity. These primitives are used to configure the protocol.

  • MLME-SET-SLOTFRAMEis used to add, delete, or change a slotframe
    • request (slotframeId,operation,size,channelPage,channelMap,activeFlag)
    • confirm (slotframeId,operation,status)
  • MLME-SET-LINKis used to add, delete, or change a link
    • request (operationType,linkHandle,slotframeId,timeslot,chanOffset,linkOptions,linkType,nodeAddr)
    • request (operationType,linkHandle)
    • confirm (status,linkHandle)
  • MLME-TSCH-MODEputs the MAC into TSCH mode, or out of TSCH mode (other modes are hence possible)
    • request (modeSwitch)
    • confirm (modeSwitch,status)
  • MLME-LISTENinitiates the search for a TSCH network
    • request (time,numPageChannel,pageChannels[])
    • confirm (status)
  • MLME-ADVERTISEis used to start sending Advertisement command frames so that new nodes can find the network and this device
    • request (advertiseInterval,channelPage,channelMap,hoppingSequenceId, timeslotTemplateId,securityLevel,joinPriority,numSlotframe,slotframes[])
    • indication (PANId,timingInformation,channelPage,channelMap,hoppingSequenceId,timeslotTemplateId, securityLevel,joinPriority,linkQuality,numSlotframes,slotframes[])
    • confirm (status)
  • MLME-KEEP-ALIVEcauses an empty (no MAC payload) frame to be sent in order to keep synchronization
    • request (dstAddr,linkHandle,period)
    • confirm (status)
  • MLME-JOINis used by a new device to join the TSCH network
    • request (dstAddr,securityInformation,numNeighbors,neighbors[])
    • indication (linkHandle,newNodeAddr,securityInformation,numNeighbors,neighbors[])
    • confirm (status)
  • MLME-ACTIVATEis used by a node already in the network to accept a new device in the network
    • request (dstAddr,securityInformation,slotframes[])
    • indication (srcAddr,securityInformation)
    • confirm (status)
  • MLME-DISCONNECTis used to gracefully disconnect from the TSCH network
    • request ()
    • indication (srcAddress)
    • confirm (status)

MCPS for MAC common part sublayer. These primitives are used to exchange data, once the MAC layer is correctly configured.

  • MCPS-DATAis used to transfer data from one node to its neighbor
    • request (!SrcAddrMode,!DstAddrMode,DstPANId,!DstAddr,msduLength,msdu,msduHandle,!TxOptions, SecurityLevel,!KeyIdMode,!KeySource,!KeyIndex,numberOfAdditionalDstAddr,additionalDstAddr)
    • confirm (msduHandle,status,Timestamp,dstAddr)
    • indication (!SrcAddrMode,SrcPANId,!SrcAddr,!DstAddrMode,DstPANIdDstAddr,msduLength,msdu, mpduLinkQuality,DSN,Timestamp,!SecurityLevel,!KeyIdMode,!KeySource,!KeyIndex)

Frame formats

IEEE802.15.4-2006 devices have 64-bit identifiers which can be compacted to 16 bits. Moreover, to differentiate different networks, each network (called a Personal Area Network, or PAN), has a PAN ID. As a result, a device is uniquely identified by the tuple PAN ID, 16/64-bit identifier.

The start of the IEEE802.15.4-2006 header is the 2-byte frame control field, depicted below, and which is present in all frames. Its 3-bit Type field differentiates between the 4 types of frames: beacon (not used in IEEE802.15.4e), data, acknowledgment and command. Four flags follow: Security Enabled, Frame Pending (not used in IEEE802.15.4e), Acknowledgment Requested and PAN ID compressed. PAN ID compressed means that the PAN ID is the same for source and destination (which is most often the case), and is hence written only once in the packet. Acknowledgment Requested is set to one for all frames that needs acknowledgment; in practice all but the advertisement. IEEE802.15.4e does not use beacon frames, and uses the same data format as IEEE802.15.4-2006.

type (3b)

security enabled (1b)

packet pending (1b)

acknowledgment requested (3b)

PAN ID compressed (1b)

reserved (3b)

Destination Address Mode (2b)

frame version (2b)

Source Address Mode (2b)

IEEE802.15.4e does not change the format of the data frames, but redefines the acknowledgment frame. In order to be backwards-compatible, in reality an acknowledgment in a data packet (i.e. Frame Type in the Frame Control Field is set to 0b001). This redefined acknowledgment consists of a DATA header, with a DHR frame control and a Time correction field. This is described on pp.56-57 of IEEEStd802.15.4e-D0.x. Time correction is used for a sender node to synchronize off of the acknowledgment received from the receiver.

802.15.4e uses three types of command frames:

  • Advertisement frames are used by nodes in the network to advertise that they exist, so that new nodes can join the network. Their structure is described on pp.70-73 of IEEEStd802.15.4e-D0.x.
  • join frame is sent by a new node which has heard an advertisement frame and would like to join the network. Its structure is described on pp.73-75 of IEEEStd802.15.4e-D0.x.
  • An activate frame is issued by a node of the network after it receives a join command, to inform the new node whether or not it can join. Its structure is described on pp.75-76 of IEEEStd802.15.4e-D0.x.

The 5 resulting types of frames (advertisement, join, active, acknowledgment and data) are presented in OpenPacketStructure.

State

A number of variables need to be stored in RAM when running IEEE802.15.4e.

Global variables are:

macDisconnectTime

time to send out Disconnect frames before disconnecting

macMinBE

minimum value of the backoff exponent (BE)

macMaxBE

maximum value of the backoff exponent (BE)

For each slotframe in the macSlotframeTable, the node needs to store:

slotframeId

its identifier

slotframeSize

the number of timeslots in the slotframe

activeFlag

a flag indicating if the slotframe is currently activated

channelPage

the channel Page of channels used in this slotframe

channelMap

a bitmap of active channels

For each link in the macLinkTable, the node needs to store:

linkId

the identifier of the link

linkOption

a set of flags indicating whether the link is used for transmit, receive, or shared transmissions

linkType

an enumeration indicating the type of link: Normal, Join, or Advertising

slotframeId

the identifier of the slotframe to which this link belongs

nodeAddress

16-bit address of the node connected to this link

timeslot

the timeslot for this link

channelOffset

the channel offset for this link

For each timeslot template in the macTimeslotTemplate table, the node needs to store (the unit for all durations is micro-seconds):

!TimeslotTemplateId

the identifier of Timeslot Template

TsCCAOffset

the time between the beginning of timeslot and start of CCA operation

TsCCA

the duration of CCA

!TsTxOffset

the time between the beginning of the timeslot and the start of packet transmission

!TsRxOffset

beginning of the timeslot to when the receiver must be listening

!TsRxAckDelay

end of packet to when the transmitter must listen for Acknowledgment

!TsTxAckDelay

end of packet to start of Acknowledgment

!TsRxWait

the time to wait for start of packet

!TsAckWait

the minimum time to wait for start of an Acknowledgment

!TsRxTx

transmit to Receive turnaround (12 symbols)

!TsMaxAck

transmission time to send Acknowledgment

!TsMaxTx

transmission time to send the maximum length packet (133 bytes)

Slotframes and Slots

All nodes in the network are synchronized on a slotted time base. A slotframe is a collection of timeslots repeating in time. The number of timeslots in a given slotframe determines how often each timeslot repeats. The total number of timeslots that has elapsed since the start of the network is called the Absolute Slot Number (ASN). The pairwise assignment of a directed communication between devices in a given timeslot on a given channel offset is a link. Physical channel selection in a link is using:

frequency = (ASN + channelOffset)%16

During a timeslot, one node typically sends a frame, and another sends back an acknowledgement if it successfully receives that frame. If an acknowledgement is not received within the timeout period, retransmission of the frame waits until the next assigned transmit timeslot (in any active slotframe) to that address occurs.

As shown above, the timeslot starts at time T=0 from the transmitting device's perspective (lower part). The transmitter waits TsTxOffset us, then begins transmitting the packet. The transmitter then waits TsRxAckDelay us, then goes into receive mode to await the acknowledgment. If the acknowledgment does not arrive within TsAckWaitTime us the device may idle the radio and that no acknowledgment will arrive. From the beginning of the slot, the receiver (upper part) waits TsRxOffset us, then switches on its radio. It stays on for a maximum of TsPacketWaitTime us, or until receiving a packet. After receiving a packet, it wait for TsTxAckDelay us, and replies with an acknowledgement.

Synchronization

Device-to-device synchronization is necessary to maintain connection with neighbors in a slotframe-based network. There are two methods for a device to synchronize to the network:

  • Acknowledgment-based synchronization involves the receiver calculating the delta between the expected time of frame arrival and its actual arrival, and providing that information to the sender node in its acknowledgment. This allows a sender node to synchronize to the clock of the receiver.
  • Frame-based synchronization involves the receiver calculating the delta between the expected time of frame arrival and its actual arrival, and adjusting its own clock by the difference. This allows a receiver node to synchronize to the clock of the sender.

Such simple synchronization allows nodes to be synchronized within a few tens of us, which is small compared to the guard time allows by the protocol (typically 1ms). Nodes keep a sense of time by counting the number of oscillations of typically a quartz-based oscillator. While it is meant to oscillate at 32768Hz, differences in fabrication or temperature cause frequencies to be slightly off. Typically, two clock will have a relative drift of 10 parts-per-million, or ppm, which means that after one second, the clock will be off by 10us. As a result, node need to resynchronize from time to time. When there is traffic on the network, nodes which are communicating will implicitly resynchronize using the data packets they exchange. If they haven't been communicating for a some time (typically 30s), nodes will exchange empty data packet (called keep-alive messages) simply to resynchronize.

A node will only synchronize to its time-parent, where the tree formed by the time parents is rooted at the gateway. This forms a synchronization tree, and ensures that all the nodes in the network has a common sense of time. In practice, a node chooses its time parent to be also its preferred routing parent.

Network Formation

There are two components of network formation in the TSCH network: advertising and joining. As a part of advertising, network devices that are already part of the network send advertisement command frames announcing the presence of the network. A new device trying to join listens for the Advertisement command frames. A new device joins the network by sending a Join request command frame to an advertising node. The advertiser activates the device by sending an activate frame.

A new network starts when the PAN coordinator starts to advertise (typically at the request of Network Manager residing in the PAN coordinator). Being the first node in the network, the PAN coordinator starts at least one slotframe, to which other network devices may later synchronize.