I thought I would spend this portion of the series discussing some of the more detailed parts of the data path. Since the tree and mesh routing is already explained in other articles, I’d like to talk about the other two forwarding methods: broadcasting and the neighbor table.
For those new to the Zigbee spec and trying to implement the broadcast functionality, it can be pretty confusing. At least it was for me when I had to figure it out so hopefully this can help clear some of the haze. Broadcasting plays an important role in Zigbee and is used for many functions. Two of the most prominent are route discovery and group transmissions. Route discovery is the process of locating a path to a destination address whose route is unknown. Zigbee uses a modified form of AODV (Ad-hoc On-demand Distance Vector) which is just fancy terminology for “flood the network with pings until you hit the destination address”. The flooding part occurs by broadcasting route requests and have them propagate through the network until the destination is reached. Group transmissions are a method of transmitting data to all devices within a certain group. A broadcast is used to transmit the data and the frame will be discarded by any members that don’t belong to the group. Along with those functions, there are numerous other smaller functions that utilize broadcasts in both the ZDO (Zigbee Device Object or endpoint 0 on all Zigbee devices) and the ZCL (Zigbee Cluster Library).
To understand broadcasts, it might make sense to discuss some of the different device types a bit. There are three types of Zigbee devices: the coordinator, routers, and end devices. The coordinator is just a router that starts the network. It always has a network address of 0 and mainly performs the function of scanning the network and selecting the channel and ID for the network. A router is a device that has the capability to forward frames and usually, is able to accept child devices. An unfortunate attribute of routers and coordinators in Zigbee is that they’re unable to sleep which is a standard complaint among many people that are investigating using Zigbee for wireless sensor networking. This limitation means that Zigbee routers usually need to be attached to a MAINs power supply.
An end device has no resources to forward frames and can only join and communicate with a parent router. The simplified communication capabilities allow most of the MAC, NWK, and APS management functions to be stripped out and should result in a very small memory footprint. Sleepy end devices are able to be duty-cycled where they sleep most of the time and awaken periodically to poll its parent for any buffered messages. It uses 802.15.4 indirect transmission for the polling, which is discussed in more detail in my 802.15.4 series. Duty cycling the end device allows it to consume very little power, thus increasing the battery life which is one of the most important factors in wireless sensor networking.
So anyways, back to broadcasting. The reason I discussed the device types is because you can target your broadcasts based on the device type. There are four broadcast addresses that can be used depending on your broadcast audience:
|Address|| Audience |
|0xFFFF || All Devices|
|0xFFFD || All Devices with Receiver on Permanently |
|0xFFFC || Routers and Coordinators|
|0xFFFB || Low Power Routers |
Just a note, although low power routers are specified, I haven’t heard of any actual implementations of them yet. Feel free to correct me on this.
Transmitting a network broadcast frame in Zigbee actually sets off a chain of events. If a new broadcast is received, either from another device or from a higher layer, a broadcast transaction record is created. If the frame was received from another device, a copy of the frame is also made and sent up to the next layer for processing.
The broadcast transaction record is used to track the source address and sequence number of the broadcast. These two pieces of information are used to uniquely identify a broadcast frame. This is important because once the broadcast frame is forwarded, all neighbors within earshot will re-send the broadcast frame and you’ll get multiple copies of it. As long as you have the broadcast transaction record, you’ll know that you’ve already received and processed the frame so you can discard the copies.
Broadcast Transaction Record Entry:
|Src Address|| 16-bit Network Address of Broadcast Initiator |
|Sequence Number || Network Layer Frame Sequence Number|
|Expiration Time || Amount of Time Before This Entry Expires|
The record that was created actually goes into a table called the Broadcast Transaction Table, or BTT. The BTT implements what’s called a passive acknowledgement system, and is used to ensure that all known neighbors have received the broadcast sent by the device. As I mentioned previously, when a broadcast is transmitted, all devices that receive it will broadcast a copy. Each time a copy of the broadcast arrives, the address of the sender will be added to the BTT to mark that it has relayed the broadcast. After a broadcast timeout, if all neighbors haven’t relayed the broadcast, meaning they aren’t present in the BTT, then the original sender will need to do a broadcast retry. This happens until the max retries (usually 3) or all the neighbors show up in the BTT.
Apologies if it might sound a bit confusing. I had to read the broadcast section more than a couple of times and actually wrote some simple simulation programs to gain an understanding of the behavior and the passive ACK mechanism.
The problem with the BTT is that it is not very deterministic. If there are a lot of neighbors, ie: the network is dense, then the broadcast transaction table has the potential to become large, eating into the RAM. Thus there is an option in the Zigbee specification to forgo the broadcast transaction table. The tradeoff is that the device will need to broadcast the frame the maximum amount of retries for any broadcast. At first glance, this would be desirable because you can get rid of the BTT which has an unknown number of entries. However this also means that each broadcast will be retried three times (the default retry number), taking a toll on all devices on the network. Each received frame, whether a duplicate or not, requires RAM since it needs to get to the network layer before it can be checked and discarded. If many devices on the network have no broadcast table, then each broadcast would generate a huge amount of traffic, possibly triggering some devices to run out of memory. So when you see warnings in the software documentation that broadcast transmissions should be used sparingly, they’re usually referring to the fact that a broadcast storm may chew up the available RAM in a node.
Since the mesh and tree routing mechanisms as well as the broadcasts have been covered, it's time to discuss the final method of data forwarding, which is the neighbor table. The neighbor table contains a list of the devices that are within transmission/reception range and provide a convenient single hop transmission to the destination. It is also used during the discovery or rejoin process to see if the joining device was previously a child of the node. According to the specification, the neighbor structure contains both mandatory and optional fields. However in actual usage, the optional fields are required since they will be needed by some of the ZDO functions. Just a little gotcha for those implementing their own stack:
Neighbor Table Entry - Mandatory
|Field || Description|
|Extended Address || 64-bit device address |
|Network Address || 16-bit network address |
|Device Type || Coordinator, router, end device|
|Rx On When Idle || Flag to mark sleepy end devices |
|Relationship || Parent, child, sibling, no relationship|
|Transmit Failure || Transmission failure counter |
|LQI || Link quality indicator |
|Outgoing Cost || Cost of outgoing link as measured by neighbor. Only required if symmetrical links are used. |
|Age || Time since link status command was received. Only required if symmetrical links are used. |
Neighbor Table Entry - Optional (Not)
|Extended PAN ID|| 64-bit unique PAN ID |
|Channel|| Operating channel|
|Depth|| Tree depth of device |
|Beacon Order|| 802.15.4 Beacon Order. Zigbee uses no beacons so this should be 0x0F |
|Permit Joining|| Flag to indicate whether device is accepting join requests |
|Potential Parent|| Flag to indicate if neighbor satisfies parent criteria |
The neighbor table is initially populated during device discovery when a device is searching for a parent to join to get on the network. I’ll discuss the join procedure later when I get into the network management side of things. Anyways, when a device tries to join a network, it will first perform a device discovery where it broadcasts a beacon request. All routers within earshot will respond with a beacon frame containing information about themselves. This information will get stored into the neighbor table. Unfortunately, the spec is a bit light on details about populating the neighbor table after the initial join procedure. In order to keep the table up-to-date, any beacons that are seen should be compared to the neighbor table and added to it if an entry doesn't exist.
Well, that kind of takes care of most of the main points of the network layer’s data path. Within the Zigbee stack, or even the full protocol stack including 802.15.4, I’d say that the network layer data path is the most complex. Next up should be the network management which includes device discovery, joining, leaving, and network maintenance.