Home arrow Blog arrow Zigbee arrow Zigbee Mesh routing - Interactive Tutorial
Zigbee Mesh routing - Interactive Tutorial | Print |
Written by Akiba   
Tuesday, 08 April 2008

Man. I spent the last three days learning how to use Flash so I could create this simple tutorial. You'd think that it would be easy to create a simple interactive thing like this, but it was actually extremely painful. You can't just draw the symbols and move things around. You actually need to program in a language that Adobe (MacroMedia) made called ActionScript. The programming part is no problem, but searching the massive documentation to find the right method to do what I wanted caused me to pound a large hole in the wall with my head. I still don't know why it requires a zillion languages just to do some stuff on the web.

Anyways, this is something that I've been wanting to do for a long time. Trying to explain Zigbee mesh routing using just words is very difficult, and has the tendency to cause people's eyes to glaze over. With an interactive simulation, you can do a play-by-play analysis of what's going on which hopefully will make it easier to see the flow of events that makes up the AODV routing algorithm. I originally had the idea when I was studying the routing algorithm myself. It's almost impossible to understand what's going on by reading the Zigbee spec. That's like trying to understand how to use Linux by reading the source code. You need to be a real masochist. 

There weren't many good tutorials on the web for AODV mesh routing, either. So to save the people the same pain I had to go through in studying it, I created this little applet. To move forward one frame, just click anywhere on the graphic. To move back, press the space bar. Flash doesn't have a handler for the right-click button, because Apple users usually only have one mouse button. You can't tell who will be using the Flash file since it's accessed inside a web browser. You'll need to have Adobe Flash v9 installed (or higher depending on when you're reading this) in order to use it. Otherwise, it will probably just give you a bad graphic, no graphic, or it will cause your computer to explode.

I'm also planning to try and make other tutorials similar to this for tree routing, source routing, and possibly some other aspects of Zigbee. I think its much easier to learn visually than reading that monster document. Without further ado, here's the tutorial. Hope you like it. If there are any problems, leave a comment for me...especially if you find bugs. 

Once you understand how the Zigbee routing works, then you can see that the terms that are being thrown around like "self-healing" are more a property of the routing algorithm. If a node goes down, then it won't participate in the route discovery process and so a different route will automatically be discovered. Okay, in my scenario, there were no redundant routers to the destination so that doesn't count. 

Also, there are other subtleties associated with the algorithm used in Zigbee such as the use of "link cost" to determine the best route. This is the probability that the link may successfully transmit the frame and is a factor of interference, remaining battery life, and a gazillion other things. Its mainly subjective and depends on the company that does the implementation. There's no agreed upon way of calculating this so the spec just kind of leaves it as a ranking between 1 and 7 on how confident you think the frame will get transmitted. In my initial implementation, I'm just going to leave it as a static value. The path cost will then just reflect the number of hops from the source to the destination and the path with the least amount of hops will be chosen. Yes, its not very academic, but hey, I just want to get it to work. I'll let other people tinker with optimizing the routing depending on their needs.

Well, that just about does it for this post. Unfortunately, the research behind it took much longer than actually writing it, but at least future simulations will be much easier to make. Hope you enjoy. 

Edited 2008-04-09: I just found out that Internet Explorer 7 disabled Javascript and Active X by default which seems like its required in order to run the Flash applet. Sorry about that. 

 

Hits: 43833
Trackback(0)
Comments (10)Add Comment
...
written by ward, December 07, 2008
very clear, thanks !
report abuse
vote down
vote up
Votes: +6
...
written by geoff, February 24, 2009
cheers for this overview, very helpful! smilies/smiley.gif
report abuse
vote down
vote up
Votes: +1
...
written by Geoff, March 11, 2009
By the way, are the source and destination sequence numbers being shown in the animation? Did you remove them because they aren't really required for understanding? Just wondering how important they are. Wikipedia's article on AODV mentions a few issues with AODV concerning intermediate nodes holding recent but not up to date DestSeqNum's. They mention that it can cause intermediate nodes to hold inconsistent routes.

I'm not quite sure if I fully understand how the sequence numbers can cause inconsistent routes to be created, do you reckon you could add some explanation about it to this article? Wikipedia touches on that issue very briefly but doesn't explain it properly. Sorry to be such a nagging grandma! smilies/cheesy.gif
report abuse
vote down
vote up
Votes: +0
...
written by Akiba, March 11, 2009
The src/dest seq numbers aren't being shown. Actually, the Zigbee version of AODV uses what's called route request IDs (RREQ ID) that are stored in the route discovery tables when you are looking for a new route. Those entries are purged after a certain amount of time, which I believe is to handle the issue of stale discovery entries that you mentioned.

As for an explanation of how a stale entry can mess things up, in AODV, when you are discovering the route, you need to send a route discovery frame (route request). These get broadcast to the network and are tagged with an identifier (RREQ ID). If you don't purge these, then it's possible that some time later, a route request from a different node with the same ID comes through. Needless to say that this is not a good situation. Here's the gory details of what can happen: if the route discovery frame has a path cost less than the old discovery entry with the same RREQ ID, then the new discovery frame will be dropped and the old one will be kept. The old entry however is irrelevant to the current route discovery process that is going on so it can seriously screw up the algorithm.
report abuse
vote down
vote up
Votes: +1
...
written by Geoff, March 12, 2009
"if the route discovery frame has a path cost less than the old discovery entry with the same RREQ ID"

Hey is this supposed to be less than or more than?
report abuse
vote down
vote up
Votes: +0
...
written by Akiba, March 12, 2009
sorry. temporary brain freeze. it should be "more than", which would trigger the frame to get dropped and the old entry to be kept.
report abuse
vote down
vote up
Votes: +0
about AODV implementation
written by upasna, March 24, 2009
hello sir i want to implement this AODV algo in C#.NET. Sir, PLZ help me.
report abuse
vote down
vote up
Votes: +0
AODV implementaion in C#
written by upasna, March 24, 2009
sir can u give me idea how we implement it in C#
report abuse
vote down
vote up
Votes: +1
...
written by Akiba, March 24, 2009
I assume you want to write a simulator in C# for AODV. I think the only way to do it is to translate an existing implementation to C# or write one from scratch. I had to write a small sim in C using the Zigbee spec to test out the algorithm before I implemented it.
report abuse
vote down
vote up
Votes: +0
data loss
written by kamoni, April 02, 2014
Hello,

Could this happen that if router device sending message to coordinator, the coordinator may lose the packet in the stack as router is able to receive APS ack from the coordinator but at coordinator we are not able to see the message delieverd by the router.

If this may happen then what should be done to prevent this?
report abuse
vote down
vote up
Votes: +0

Write comment

busy
 

Discuss (39 posts)

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 13 2009 05:46:00
hi
Actually we are using a similar style for AODV implementation (first on the PC and then on the board) only thing is that 5 of us are taking up different parts of the algorithm and trying to implement their own part. once that is done then would come the testing part. Only after the testing would the integration start.

Im involved in the path discovery part which takes care of the forward and reverse path setup.

So is it necessary to maintain the reverse path or can i omit that entry in the route table and maintain a discovery table. The RREP packet would take help of the discovery table to get back to the source.

and discovery table would exist as long as the path exists.

can you help me find some flaw in this implementation.?
#1035

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 13 2009 06:18:41
Yowzah...an AODV implementation divided into five separate efforts. That's going to be a nightmare...
#1036

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 13 2009 06:31:32

Lets take that as a compliment. The initial coding is over. and testing is yet to start. I have used the idea which i mentioned before to take care of the reverse path. just wanted to clarify if thats gonna be alright. cause if not the i will have to re work the whole thing and would halt the others progress too...
#1037

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 14 2009 07:45:23
What all wud be the fields i need to save at the intermediate node while rreq is being propagated.?
rite now im having
RREQid
Source address
the address of node which send the RREQ..
shud i save the dest seq num too.?
#1040

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 15 2009 02:01:03
Since you mentioned that its a multi-person effort, it wouldn't be much challenge if I gave you all the answers now would it
#1045

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 17 2009 06:18:54
ok...
by the way we have finished the individual coding and the individual unit testing....so we are two steps closer to the "nightmare" becoming a dream...
thanks for the tips you have given....
#1061

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Jul 31 2009 08:55:13
Hey
Guess wat...?
The nightmare is soon gonna become a dream.....
But we are stuck i a small part...we are using hello message for maintaining a route..so suppose i have a master(position (0,0)), one intermediate node(0,2) and a destination(0,4)
Im able to establish a path between master and destination through intermediate node..and hello messages are being send between the neighbours...now im making the destination fail..so the intermediate node generates a RERR and sends it to the master..
Problem starts after this...master and intermediate invalidates the route to destination....but they dont stop sending hello message between each other...my doubt is that should i stop this behaviour...because now there is no node and henceforth no active nodes...rite?
Why this occurs is because the intermediate node has a entry for master in its discovery table...and master resets the timer to delete the route entry cause it receives hello from the intermediate node....
#1149

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Aug 02 2009 01:37:17
Sounds like you're making good progress. In regards to your question, I think that if a node ceases to be on the network, you should probably stop pinging it.
#1152

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Aug 07 2009 06:16:59
Hi
I found now concept which has not been mentioned(or which i have missed) in the AODV algorithm....
suppose a intermediate node fails...RERR is send to all the sources informing about all the affected destinations......but the nodes which are present between the destination and the node that failed...what happens to them....Right now in our algorithm we haven't taken care of that so they maintain a "hello msg" connectivity among them as if nothing has happened.
i wonder if this is gonna be of any use. cause that path is maintained and will not be deleted until the nodes there fail even if there is no communication between them...isn't this a flaw..but i cant figure out how to fix this...?
can u give me some idea how to fix this...? or is this wat the algorithm expects...?
#1175

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Aug 07 2009 12:09:22
Can't help you much with your issue. I haven't implemented periodic network status messages yet so I don't have much experience with this problem.
#1179

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Sep 09 2009 10:29:15
Im back...and yes i have not disappointed anyone....AODV simulator implemented and now totally into implementing it on xbee pro module...and once successful will be moving onto the microchip board...
#1280

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Sep 09 2009 12:43:05
Congratulations. Getting the AODV working is not a simple task and is the heart of a WSN stack. Good luck on the rest of your project!
#1281
AODV completed
Re:Zigbee Mesh routing - Interactive Tutorial
Nov 06 2009 09:13:36
Sorry for the delayed reply....we have successfully implemented and tested AODV algorithm(in mid October) on xbee-pro modules and is perfect...testing took place with two fixed nodes and a mobile node which keeps moving between the nodes. Each time the node reaches the vicinity of a fixed node, it is detected and as it moves out its lost...

Thanks for the support....

next step porting it to microchip boards...


Deepak
#1425
jason
Re:Zigbee Mesh routing - Interactive Tutorial
Jan 07 2010 20:46:34
Zigbee is supposed to be battery powered? Did you implement power-save AODV? Can you share any details?
#1587

Deepak Gopalakrishnan
Re:Zigbee Mesh routing - Interactive Tutorial
Jan 08 2010 11:28:29
Though zigbee is suppose to be battery powered, we had xbee modules which drew power from the laptops to which they were connected.

Yes, one concept we did include to reduce the power consumption. We removed the repeated transmission of hello msgs and used the concept of link layer acknowledgements instead.

this actually wasnt for power reduction. it was to reduce the number of msgs sent on air...which in turn will help in reducing power.

hope this was of any help
#1590
Muzzamil
Re:Zigbee Mesh routing - Interactive Tutorial
Sep 19 2011 17:49:14
Lets suppose if ED's parent is dead for some reason and this ED is in the range of another router, so will it connect to that router or will it remain orphan?

If ED is in the range of two routers, will it connect to both routers and do both router have its Node address?
#3255

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Sep 21 2011 00:25:19
In general, you would do an orphan scan in the hopes of finding the parent. When that fails, then it would rejoin with a different parent. I believe the parent will assign it a new short address.
#3261
prashanth
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 15 2012 05:23:54
hello,
i am looking for the code which is used on zigbee. give me a link where i can download that.
thank you.
#4451

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 15 2012 06:57:39
#4453
Andrew Hardy
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 30 2012 13:45:45
I just have a question about the discarding of RREQs that are received from one of the nodes you just forwarded to.

This is mentioned in the animation about the 3rd or 4th frame where the author indicates that he does not show such reverse paths in the animation because they are discarded.

Since each sending is a broadcast and link cost is static then I presume the reverse broadcast packet is passed up to the routing layer where it is found the particular RREQ has already had its first receipt and so it is dropped. Is this right?

I am just wondering, if a link cost were introduced, would this reverse broadcast also be passed up to the routing layer and in a similar manner always being found (obviously) to be a more costly path (get back here via somewhere else!) would be dropped in the same way. Right?

Now. Assuming these are the case. I think the tutorial shows coordinators and RFDs, so I am wondering, wouldn't a coordinator send to its registered devices rather than broadcast? If this were the case I have read somewhere that with distance vector routing there is a strategy called split horizon where you actually do NOT send the request back to the sender, which would be possible if a coordinator was only sending amongst its registered devices and not broadcasting.

So, I guess my first question is, what is the common way this is done? Is it MAC broadcast and the cost checked in the previous sender routing layer and dropped or are the coordinator's registered addresses used, excluding the original sender, and leave it up to the radio/mac layer of the excluded node to know the PHY broadcast packet(s) is/are not for it?

And my second question is what are the efficiency trade offs. Dependant on the mac configuration I suppose sending to individual registered neighbours would mean repeating the same paccket right? So more transmit time? But for a broadcast, more cost at the radio receiver and more processing?

May be I have this all wrong, but I'd appreciate a few pointers on this.
#4824

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 31 2012 01:41:27
Route requests are broadcasts and they flood the network. You need complete saturation to discover all potential routes. Route requests that never make it to the target node will get dropped. Repeat route requests that have been received before will also be dropped. As for cost, it is depenedent on the user. Most people use RSSI (or link quality) for cost but you can also use battery power, etc.
#4833
Andrew Hardy
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 31 2012 09:40:52
Ok, thanks.

So RREQs are always broadcasts. I guess that makes sense.

I am a bit confused however by "Repeat route requests that have been received before will also be dropped". I can see this is the case for static routing, but if a complex cost system is in place to accumulate best path cost then a RREQ may easily arrive at a node by two different routes, but the second arrival have a better cost. I presume therefore in the case of static cost (Basic AODV) drop if a subsequent RREQ because you are just testing latency, but for complex cost system (some 'potential' Zigbee implementation) drop if not a better accumulated path cost otherwise forward. Isn't this right? However, in the case of receiving the RREQ back from a node you only just sent it to, you would have to compare the path cost, but it would always be dropped. What you think?

Having said this I can see how implementations would want to always broadcast the RREQ, I guess the mac api's I have seen where coordinators send individually to all their associated devices are doing this just for some other purpose, or sending unicast in the case of data being sent along an active route.
#4846
Andrew Hardy
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 31 2012 09:45:02
By "Route requests that never make it to the target node will get dropped" do you mean that if they reach a max hop value they will be dropped and that RREQ entries will be deleted if they reach expiry without being activated? Or is there some other similar case for dropping the packet?
#4847

Akiba
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 31 2012 09:56:14
Sorry, I was thinking of normal broadcasts. Route requests get put inside a route discovery table. You will have multiple route requests but from different paths and the info will go into the route discovery table. The path cost is calculated on the reverse path back to the originator.

I've pretty much stopped development on Zigbee though since it pretty much duplicates most of what TCP and IPv6 can already do. I'm working more in the 6LoWPAN space for WSN so my Zigbee knowledge is a bit rusty.
#4848
Andrew Hardy
Re:Zigbee Mesh routing - Interactive Tutorial
Mar 31 2012 10:13:10
Ok, no worries, thanks for discussing.

Is there are forum you think might be particularly good for discussing AODV / Zigbee standards/specifications/implementations?

I've read fair bit of AODV RFC, Zigbee Spec and looked at a few implementations, but one always has questions that often can be answered quite quickly by up to date experience.

Any discussion forums fit the bill?

BTW I really liked you animation, a picture can serve for a thousand words, it would be good to extend it. Time I guess!!
#4849
There are too many comments to list them all here. See the forum for the full discussion.

Discuss...
< Prev   Next >