|Zigbee Tree Routing - How It Works and Why It Sucks||| Print ||
|Written by Akiba|
|Sunday, 11 January 2009|
Zigbee 2007 (Residential) has two methods of routing: mesh routing and tree routing. Although most people talk about the mesh routing capability of Zigbee, not too many people know much about the tree routing. There's actually a good reason that it isn't discussed much and I'll get into that later. However I do receive the occasional question on how Zigbee tree routing works. Mostly, its from people that want to run Zigbee using the 802.15.4 beacon mode since tree routing is the only routing method supported in this case.
In order to understand tree routing, its first important to understand the underlying principle which is how addresses are allocated. Once that is understood, the routing becomes trivial.
Tree Address Allocation
From the picture, you can see that the maximum number of devices would be 7, hence the address space will span from 0 to 6. Also I purposely drew it in a tree structure (in this case binary tree) for purposes that you can see below.
All of these addresses are fixed for the position in the tree that a device occupies. You can see that the numbers progress sequentially from top to bottom and left to right as you follow the flow of the tree. Hence the 1st address which corresponds to the first device on the network will be 0. This corresponds to the coordinator and the coordinator's address will always be zero in a tree address allocation scheme. The first device that joins the coordinator will have an address of 1 and it's children will have 2 and 3. The second device that joins the coordinator will have an address of 4 and its children will be 5 and 6.
Of course this allocation is only based on our simple test case with a maximum of 2 routers and a max depth of 2. Here's how the address is allocated if we change our parameters so we have a maximum of 3 routers and 3 children. We can't have more routers than total children since each router is considered a child. The depth is kept the same.
In case you're wondering how I came up with the total address space, its actually quite simple. For the case with 2 routers, 2 children, and a network 2 deep, the total space is:
Total Space = 2^2 + 2^1 +2^0 = 7
For the case with 3 routers, 3 children, and 2 deep:
Total Space =3^2 + 3^1 + 3^0 = 13
If the number of children equals the number of routers, you can calculate the total number of devices from the following:
And for the general case where the number of children is not equal to the number of routers (ie: end devices also exist) the max number of devices and hence the max value of the address space is:
where Cm = Max End Devices
That's basically how the tree address allocation works for Zigbee. Now that we know how the addresses are doled out, it will be easier to see how they are used for routing.
That's pretty much all there is to tree routing. It is heavily dependent on the addresses of each device and if you understand how addresses are allocated and the concept of each device having its own address space, then understanding how the frames get routed is pretty simple.
The Problems with Tree Routing
Another fatal flaw is that there is no way to recover if the coordinator fails. It is the single point of failure for this routing method. In mesh routing, if the coordinator fails, things are still okay because from a mesh point of view, the coordinator is just another router in the routing tables.
However in tree routing, the coordinator is the vertex of the tree, where all frames must pass if the destination device is not located on the same branch as the source device. If the coordinator fails, then all the main branches become isolated and your network is pretty much useless. Currently, there's no place in the Zigbee spec (that I'm aware of) that describes how to recover from this failure.
From a reliability standpoint, tree routing is fairly dangerous. In fact, it was probably dangerous enough that the Zigbee Alliance decided to remove tree routing and addressing in the Zigbee Pro spec and I suspect that in the future, it may get taken out of Zigbee completely. In the FreakZ stack, tree routing is supported, but it's the frame forwarding method of last resort if all other methods fail.
Well, I hope this little blurb on tree routing was helpful. I don't really mean to knock on the algorithm since I think its pretty clever, but unless the Zigbee spec can address some of its reliability flaws, I would consider it dangerous to use. I guess what I'm implying in this article is that Zigbee shouldn't be used in beacon mode.
How do you like them apples...
Zigbee Tree Routing - How It Works and Why It Sucks
Jun 23 2009 09:55:06
This thread discusses the Content article: Zigbee Tree Routing - How It Works and Why It Sucks
I'm interested in this standard (IEEE802.15.4)when I can implement the AODV protocol in this networ to add the 2 metrics, delay and taux _error so i need to give me or send me somme information to help me for this implementation in Ns2.31.
i need to send me your mail, email@example.com
Re:Zigbee Tree Routing - How It Works and Why It Sucks
Jun 23 2009 15:41:55
Unfortunately, I am completely illiterate in NS2. However if you have any questions on the protocol, feel free to ask.
|< Prev||Next >|