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. 

TrackBack URI for this entry

Comments (9)

Subscribe to this comment's feed

...
written by ward, December 07, 2008

very clear, thanks !

report abuse

vote down

vote up

Votes: +3

...
written by geoff, February 24, 2009

cheers for this overview, very helpful!

report abuse

vote down

vote up

Votes: +0

...
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!

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: +0

...
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

Show/Hide comment form

Name

Email

Website

Title

Comment

smaller | bigger

Subscribe via email (Registered users only)

I have read and agree to the Terms of Usage.

Add Comment