Implementing a new MAC protocol for IEEE 802.15.4

Development archive
1

Hello RIOTers,

I want to use RIOT for a low-power 802.15.4 network project. Having a bit familiarized with RIOT and my samr21-xpro boards now I want to tackle my next milestone, i.e. I need a MAC protocol that fits my requirements (see below).

As it seems that there are only 2 MAC implementations for now [1,2], both not what I'm searching for and also not merged, I decided to try this on my own.

Therefore I studied some papers and existing MAC schemes to not reinvent the wheel. There is one nice paper [3] that sums up quite nicely the most basic duty-cycling schemes (p. 4ff).

There are some adaptions and refinements to these protocols which might improve the throughput or energy-saving further, but I think that these basic schemes already provide a good starting point. Namely there is ContikiMAC [4] that incorporates these improvements.

While I want to start implementing a basic and simple protocol first, I wonder if it could be nice for RIOT to have some ContikiMAC-compatible MAC layer later.

I can't promise anything for now on how well this will work in the end, but I wanted to inform you about my undertaking and maybe you have some thought or pointers that could help me. As there is so much change in all over the network stack at the moment, it would be nice to know which (for me relevant) parts of the stack I should use that are not subject to change shortly.

I gathered some notes and requirements, please find them below.

Best regards, Daniel Krebs

[1] https://github.com/rousselk/RIOT/commits/s-cosens [2] https://github.com/RIOT-OS/RIOT/pull/2467 [3] http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4539479 [4] http://dunkels.com/adam/dunkels11contikimac.pdf

Requirements for MAC-layer

2

Hello RIOTers,

I want to use RIOT for a low-power 802.15.4 network project. Having a bit familiarized with RIOT and my samr21-xpro boards now I want to tackle my next milestone, i.e. I need a MAC protocol that fits my requirements (see below).

As it seems that there are only 2 MAC implementations for now [1,2], both not what I'm searching for and also not merged, I decided to try this on my own.

Therefore I studied some papers and existing MAC schemes to not reinvent the wheel. There is one nice paper [3] that sums up quite nicely the most basic duty-cycling schemes (p. 4ff).

There are some adaptions and refinements to these protocols which might improve the throughput or energy-saving further, but I think that these basic schemes already provide a good starting point. Namely there is ContikiMAC [4] that incorporates these improvements.

While I want to start implementing a basic and simple protocol first, I wonder if it could be nice for RIOT to have some ContikiMAC-compatible MAC layer later.

+1 We use mostly Contiki-based applications presently and it would be a big improvement if it was possible to get ContikiMAC duty cycling working in RIOT as well.

I can't promise anything for now on how well this will work in the end, but I wanted to inform you about my undertaking and maybe you have some thought or pointers that could help me. As there is so much change in all over the network stack at the moment, it would be nice to know which (for me relevant) parts of the stack I should use that are not subject to change shortly.

I gathered some notes and requirements, please find them below.

Best regards, Daniel Krebs

[1] Commits · rousselk/RIOT · GitHub [2] Initial import of csma_mac protocol by jremmert-phytec-iot · Pull Request #2467 · RIOT-OS/RIOT · GitHub [3] Power saving algorithms for wireless sensor networks on IEEE 802.15.4 | IEEE Journals & Magazine | IEEE Xplore [4] http://dunkels.com/adam/dunkels11contikimac.pdf

Requirements for MAC-layer

# Requirements

* Mesh topology => no single-point-of-failure

Is this not a requirement of the routing?

* Low energy consumption * Relatively small single-hop network (~10 nodes) * New nodes can join and leave the network * No need to comply with IEEE 802.15.4 MAC schemes * No need for hard realtime * Should be reasonibly simple to implement

# Ideas / Questions

* Do we need broadcasting?

Routing protocols might need it. RPL sends solicitation messages to ask for routing information.

* Add multi-hop / routing later? Is this even reasonable?

Some kind of routing will be necessary for any useful applications, at least some kind of hardware address to IPv6 address mapping must exist to fill the neighbor cache. (e.g. RPL, NDP)

* Do we really need adaption to traffic load? * Find out which APIs to use in RIOT to have a modular MAC protocol that might    work with multiple transceivers

# Observations

* Requirements seem to match ContikiMAC, so maybe aim for compatibility?

Yes!

# Implementation

* Duty cycle nodes for energy saving * LPEAS => Implicit synchronization * Use 802.15.4 features, so this might only work with 802.15.4 networks _______________________________________________ devel mailing list devel@riot-os.org https://lists.riot-os.org/mailman/listinfo/devel

Best regards, Joakim

3

Hi Joakim,

+1 We use mostly Contiki-based applications presently and it would be a big improvement if it was possible to get ContikiMAC duty cycling working in RIOT as well.

Who is "we" if I may ask? Just curious.

# Requirements

  * Mesh topology => no single-point-of-failure Is this not a requirement of the routing?

Did you have a look at the IEEE 802.15.4 specification? It's assumed to have a so called PAN coordinator that forces the network to a star topology. It's extendable to a tree of stars, but still you need a PAN coordinator in every region. This node is the mentioned single point of failure and additionally has increased energy consumption.

This is exactly what I don't want.

# Ideas / Questions

  * Do we need broadcasting?

Routing protocols might need it. RPL sends solicitation messages to ask for routing information.

There are broadcasting schemes for the implementation I aim for, but they don't come for free in terms of energy consumption, like e.g. on a network bus. I'll elaborate about this later if you want.

  * Add multi-hop / routing later? Is this even reasonable?

Some kind of routing will be necessary for any useful applications, at least some kind of hardware address to IPv6 address mapping must exist to fill the neighbor cache. (e.g. RPL, NDP)

Sure. Hardware addresses are needed anyway to get your data delivered to the destination node.

Best regards, Daniel Krebs

4

Hi Daniel,

I want to use RIOT for a low-power 802.15.4 network project. Having a bit familiarized with RIOT and my samr21-xpro boards now I want to tackle my next milestone, i.e. I need a MAC protocol that fits my requirements (see below).

As it seems that there are only 2 MAC implementations for now [1,2], both not what I'm searching for and also not merged, I decided to try this on my own.

Better don´t look at [2] for now ;). Currently that PR is based on a deprecated proposal that does not poperly use the netdev interface. I hope I will have time for an update of this PR this week. Even if that is not what you are searching for, maybe it could be used to make this a base of an more advanced MAC layer. The intention of [2] is to provide an implementation of CSMA-mechanisms, random backoff-time when the channel is busy and acknowledge handling. Since this procedure is different for each driver (Hard-MAC vs. Soft-MAC) this [2] adaption MAC-layer will be necessary to avoid re-implementing in each radio-driver.

Therefore I studied some papers and existing MAC schemes to not reinvent the wheel. There is one nice paper [3] that sums up quite nicely the most basic duty-cycling schemes (p. 4ff).

There are some adaptions and refinements to these protocols which might improve the throughput or energy-saving further, but I think that these basic schemes already provide a good starting point. Namely there is ContikiMAC [4] that incorporates these improvements.

We also made some research in this field. Since we want to use our sensor-nodes in combination with Linux, we came to the conclusion that a MAC layer accordingly to the IEEE 802.15.4 standard will fit most for us. The biggest benefit is the compatibility to all IEEE 802.15.4 devices. Also a high configurability (e.g. the beacon interval length) is a feature of this standard. There are some optional mechanisms like GTS that don´t have to be implemented in the first step. But I agree, there might be easier duty-cycling MAC-layers. Since the architecture of the network stack allows to choose different MAC layers there is no problem of having different ones.

While I want to start implementing a basic and simple protocol first, I wonder if it could be nice for RIOT to have some ContikiMAC-compatible MAC layer later.

I can't promise anything for now on how well this will work in the end, but I wanted to inform you about my undertaking and maybe you have some thought or pointers that could help me. As there is so much change in all over the network stack at the moment, it would be nice to know which (for me relevant) parts of the stack I should use that are not subject to change shortly.

I gathered some notes and requirements, please find them below.

Best regards, Daniel Krebs

[1] Commits · rousselk/RIOT · GitHub [2] Initial import of csma_mac protocol by jremmert-phytec-iot · Pull Request #2467 · RIOT-OS/RIOT · GitHub

BTW: Is this also publicly availble somewhere? [2]

[3] Power saving algorithms for wireless sensor networks on IEEE 802.15.4 | IEEE Journals & Magazine | IEEE Xplore [4] http://dunkels.com/adam/dunkels11contikimac.pdf

Requirements for MAC-layer

# Requirements

* Mesh topology => no single-point-of-failure * Low energy consumption * Relatively small single-hop network (~10 nodes) * New nodes can join and leave the network * No need to comply with IEEE 802.15.4 MAC schemes * No need for hard realtime * Should be reasonibly simple to implement

# Ideas / Questions

* Do we need broadcasting? * Add multi-hop / routing later? Is this even reasonable?

As I understand it, the routing protocol is located on top of any MAC protocol. The mechanisms of the MAC protocol will be transparent to the upper layers.

* Do we really need adaption to traffic load? * Find out which APIs to use in RIOT to have a modular MAC protocol that might    work with multiple transceivers

# Observations

* Requirements seem to match ContikiMAC, so maybe aim for compatibility?

# Implementation

* Duty cycle nodes for energy saving

For the sleeping periods we might have to use a low-power timer (mostly low speed clock oscillator, 32khz or so), since most 16Mhz oscillators consume to much energy for long sleeping periods.

5

You’re right that it’s good idea to have some adaption layer on top of the device drivers that enables usage of hardware MAC mechanism s while providing a software approach for transceiver that don’t support this. The question here is if it’s possible to meet the tight timings. Need to investigate further. I’m going to need a Linux-bridge, too. The packets my MAC protocol will send will also be 802.15.4-2006(?) compatible, but the channel access scheme will be different. So at least sniffing should be no problem. In the end I hope to be able to use my RIOT implementation on native for this bridge, but didn’t look into further. I did a quick search and wasn’t able to find it publicly :frowning: That’s right. But at least multi-hop networks have some implications on the MAC scheme. Just wanted to state that this is not my first priority, because I don’t want to deal with this for now. Sure. That’s why I started familiarizing with RIOT by implementing the RTT peripheral for the samr21-xpro. The RTC, at least on this board, might be the only peripheral that can run in every power mode and wake up the MCU Best regards, Daniel

6

Hi Daniel

7

Hi Daniel!

>Is this not a requirement of the routing? Did you have a look at the IEEE 802.15.4 specification? It's assumed to have a so called PAN coordinator that forces the network to a star topology. It's extendable to a tree of stars, but still you need a PAN coordinator in every region. This node is the mentioned single point of failure and additionally has increased energy consumption.

This is exactly what I don't want.

PAN coordinators are only required for the beacon enabled mode in IEEE 802.15.4. 6LoWPAN, for instance, does not require this mode (I'm not even sure if it is supported by the spec) and thus, there is no need for a PAN coordinator or star topology.

Cheers, Oleg

8

Hi Joakim,

+1 We use mostly Contiki-based applications presently and it would be a big improvement if it was possible to get ContikiMAC duty cycling working in RIOT as well.

Who is “we” if I may ask? Just curious.

Sorry about that, I should have started with “At Eistec, we use mostly contiki…”

BR, Joakim

9

Hi Daniel!

As it seems that there are only 2 MAC implementations for now [1,2], both not what I'm searching for and also not merged, I decided to try this on my own.

There's a third inside the OpenWSN stack using the TSCH (Time Slotted Channel Hopping) as specified in the IEEE 802.15.4e amendment. I'm currently spending some time to see how it could be used separately from the remaining OpenWSN stack, but don't expect any results before next month.

While I want to start implementing a basic and simple protocol first, I wonder if it could be nice for RIOT to have some ContikiMAC-compatible MAC layer later.

One downside of ContikiMAC is that is not standardized, but that's not necessarily a problem in many use cases. I think the protocol is quite widely deployed and familiar to most people working with WSNs, so I guess it would be really nice to have a compatible implementation.

A similar scheme to ContikiMAC was implemented in RIOT, but only for the CC110x transceiver and not adapted to the new interfaces [0].

As there is so much change in all over the network stack at the moment, it would be nice to know which (for me relevant) parts of the stack I should use that are not subject to change shortly.

The relevant parts for a MAC layer implementation are probably netdev [1] describing the interface to the transceiver driver, currently implemented for at86rf2xx and XBEE, and the netapi [2] describing the interface of any layer in the network stack, including the MAC protocol. There's also a sketch of the new architecture made by Hauke some time ago [3].

I don't think it's realistic to say that these APIs won't change any more, but I guess they should be stable enough to start implementing against them.

* No need to comply with IEEE 802.15.4 MAC schemes

Can you elaborate on this point?

* Do we need broadcasting?

Depends on your use case - for a generic implementation, definitely yes. Remember that typical radio devices in this domain are omnidirectional, hence, you cannot really distinguish between unicast and broadcast on the physical layer.

* Add multi-hop / routing later? Is this even reasonable?

That's independent from the MAC layer. Can you elaborate on this?

* Do we really need adaption to traffic load?

One of the main issues with contention based MAC protocols is that they are heavily affected by the traffic load, so you should at least consider different scenarios.

* Find out which APIs to use in RIOT to have a modular MAC protocol that might work with multiple transceivers

See above, netdev should be your friend.

# Observations

* Requirements seem to match ContikiMAC, so maybe aim for compatibility?

That would be awesome.

* LPEAS => Implicit synchronization

I wonder if you really want to go for synchronization for a simple contention based protocol. Don't underestimate this challenge.

* Use 802.15.4 features, so this might only work with 802.15.4 networks

I think you should make the requirements on the transceiver somewhere explicit.

Cheers, Oleg

[0] https://github.com/RIOT-OS/RIOT/tree/master/drivers/cc110x_legacy_csma [1] https://github.com/RIOT-OS/RIOT/blob/master/sys/include/net/ng_netdev.h [2] https://github.com/RIOT-OS/RIOT/blob/master/sys/include/net/ng_netapi.h [3] http://riot-os.org/files/nstf-overview.pdf

10

Hi,

11

Hi,

> > Hi Daniel! > > > >Is this not a requirement of the routing? > > Did you have a look at the IEEE 802.15.4 specification? It's assumed to have > > a so called PAN coordinator that forces the network to a star topology. It's > > extendable to a tree of stars, but still you need a PAN coordinator in every > > region. This node is the mentioned single point of failure and additionally > > has increased energy consumption. > > > > This is exactly what I don't want. > > PAN coordinators are only required for the beacon enabled mode in IEEE > 802.15.4. 6LoWPAN, for instance, does not require this mode (I'm not even sure > if it is supported by the spec) and thus, there is no need for a PAN > coordinator or star topology.

I'm not 100% sure, since I'm not THAT knowledgeable in terms of IEEE 802.15.4, but isn't that what 6LoWPAN's mesh-under mode [1] is for? All we need to do to support this mode is to implement support for 6LoWPAN's Mesh [2] and Broadcast [3] headers.

6LoWPAN can be used in a "route-over" mesh using just IP, as well, for example using RPL as a routing protocol. This mode is of operation is incorporated into the ZigBee-IP specification [1].

- Ralph

[1] http://www.zigbee.org/zigbee-for-developers/network-specifications/zigbeeip/#learnmore; the ZigBee-IP specification document is available for free but requires registration.

12

Hi Oleg,

PAN coordinators are only required for the beacon enabled mode in IEEE 802.15.4. 6LoWPAN, for instance, does not require this mode (I'm not even sure if it is supported by the spec) and thus, there is no need for a PAN coordinator or star topology.

That's unfortunately not the case. Please refer to the specs [1] at Section 5.3, especially the second paragraph. According to the specification a PAN coordinator is always required, even in "Mesh" topology where it may get dynamically elected.

It get's even better (5.5.2.3 Peer-to-peer data transfers):

In a peer-to-peer PAN, every device may communicate with every other device in its radio sphere of influence. In order to do this effectively, the devices wishing to communicate will need to either receive constantly or synchronize with each other. In the former case, the device can simply transmit its data using unslotted CSMA-CA. In the latter case, other measures need to be taken in order to achieve synchronization. Such measures are beyond the scope of this standard.

As receiving all the time is no option because of energy consumption you need some kind of synchronization. but that's "[...] beyond the scope of this standard". Thank you IEEE.

That's why I don't aim to be compatible with IEEE 802.15.4-2006 in terms of the MAC-layer. Either I have a PAN coordinator or it advises me to do what I want.

Best regards, Daniel Krebs

[1] https://openwsn.atlassian.net/wiki/download/attachments/688143/ieee802154-2006.pdf

13

Hi Emmanuel,

One question: do you expect that network membership is rather dynamic, or rather static? (i.e. do nodes come and go due to mobility for example, or due to really long sleeping periods).

Depending on the answer to this question, some mechanisms may be more applicable than others...

The network will be kind of static, that is my nodes won't be moving around. But I expect to have nodes joining and leaving from time to time, i.e. nodes going offline for a short amount of time, and completely new nodes joining the network.

I would be really happy for any advice you could give :slight_smile:

Best regards, Daniel

14

Hi Daniel!

>PAN coordinators are only required for the beacon enabled mode in IEEE >802.15.4. 6LoWPAN, for instance, does not require this mode (I'm not even sure >if it is supported by the spec) and thus, there is no need for a PAN >coordinator or star topology. That's unfortunately not the case. Please refer to the specs [1] at Section 5.3, especially the second paragraph. According to the specification a PAN coordinator is always required, even in "Mesh" topology where it may get dynamically elected.

Ok, I was imprecise here. You still have a pan coordinator but it has another role and it's not really important for the MAC protocol any more (if I'm not completely mistaken). At least, it is not a single point of failure any more, so I fail to see how this is a problem.

It get's even better (5.5.2.3 Peer-to-peer data transfers): >In a peer-to-peer PAN, every device may communicate with every other >device in its radio sphere of >influence. In order to do this effectively, the devices wishing to >communicate will need to either receive >constantly or synchronize with each other. In the former case, the device >can simply transmit its data using >unslotted CSMA-CA. In the latter case, other measures need to be taken in >order to achieve synchronization. >Such measures are beyond the scope of this standard. As receiving all the time is no option because of energy consumption you need some kind of synchronization. but that's "[...] beyond the scope of this standard". Thank you IEEE.

That's why I don't aim to be compatible with IEEE 802.15.4-2006 in terms of the MAC-layer. Either I have a PAN coordinator or it advises me to do what I want.

Well, if the spec tells you to do what you want (inside the boundaries of this spec), then you can to what you want and be still 802.15.4 compliant.

Cheers, Oleg

15

Hi Oleg again,

There's a third inside the OpenWSN stack using the TSCH (Time Slotted Channel Hopping) as specified in the IEEE 802.15.4e amendment. I'm currently spending some time to see how it could be used separately from the remaining OpenWSN stack, but don't expect any results before next month.

I'll have a look at it, thanks for the pointer.

As there is so much change in all over the network stack at the moment, it would be nice to know which (for me relevant) parts of the stack I should use that are not subject to change shortly.

The relevant parts for a MAC layer implementation are probably netdev [1] describing the interface to the transceiver driver, currently implemented for at86rf2xx and XBEE, and the netapi [2] describing the interface of any layer in the network stack, including the MAC protocol. There's also a sketch of the new architecture made by Hauke some time ago [3].

I don't think it's realistic to say that these APIs won't change any more, but I guess they should be stable enough to start implementing against them.

Yesterday I had a look at all the APIs and also found [3] som etime ago on the mailing-list. This helped a lot, thanks Hauke! I summarized my findings in a diagram, now attached to this mail. I also inlcudes the MAC hardware-feature abstraction that Jonas mentioned yesterday.

  * No need to comply with IEEE 802.15.4 MAC schemes

Can you elaborate on this point?

As pointed out in my previous mail, I don't aim for compatibility with devices that strictly implement the specification, i.e. need a PAN coordinator. Reasons given in the other mail.

  * Do we need broadcasting?

Depends on your use case - for a generic implementation, definitely yes. Remember that typical radio devices in this domain are omnidirectional, hence, you cannot really distinguish between unicast and broadcast on the physical layer.

The probem with duty-cycling is, that packets are not broadcast anymore per-se. You (the sender) need to make sure that every node has woken up at least one time while you have been sending your packet.

  * Add multi-hop / routing later? Is this even reasonable?

That's independent from the MAC layer. Can you elaborate on this?

When having multi-hop networks, you essentially have nodes outside the radio scope of each others. But you also have nodes in between that are in the reach of both. This can create a need for scheduling, imagine both nodes, that don't see each other, try to communicate at the same time with the node in between. But I didn't think this through all the way, I just wanted to state that I'm going to ignore this for now.

I really shouldn't have used the term "routing" here :stuck_out_tongue:

  * Do we really need adaption to traffic load?

One of the main issues with contention based MAC protocols is that they are heavily affected by the traffic load, so you should at least consider different scenarios.

That's right. I can't really estimate my load at the moment apart from the fact that I'm not going to stream videos and that it will be more than one sensor value per node every 5 minutes :

  * LPEAS => Implicit synchronization I wonder if you really want to go for synchronization for a simple contention based protocol. Don't underestimate this challenge.

Did you have a look at the paper that expalins LPEAS? It's a really simple synchronization scheme.

Cheers, Daniel

MAC_Overview.pdf (44.3 KB)