AODV implementation on TinyOS-2.x
written by Junseok KIM, last updated April 8, 2011
Here, I post the source code of Ad-hoc On-demand Distance Vector (AODV) routing protocol for TinyOS-2.x.
This is not a perfect code based on the RFC, but
it supports basic functions of AODV such as the route discovery and the
local route recovery. You might be able to use this code to implement
your idea or to develop an ad-hoc application. Since this code is under
the GNU license, you can freely use it and post it or changes on the
other website under GNU license.
Let me explain on how AODV is implemented and how
it is working. When a node gets a message from an upper layer such as
application or TCP, AODV looks the route table to find the next
hop information. If
the route table has no route information, the route discovery is
initiated by broadcasting a route request (RREQ) packet. AODV does not
have a route information of networks a prori, and tries to find a route
when there is a demand. That is, AODV is a reactive routing protocol.
Please see a following example. Since node 1 does
not know where to transmit a message to get node 4, it broadcasts a
RREQ packet.
Upon receiving the RREQ packet, node 2 decodes RREQ's header and stores, in the RREQ cache table, the information such as sequence, destination, and source address. These information is used to prevent re-broadcasting the same RREQ packet.
And the node 2 inserts the information (sequence, destination, next-hop node, hop) of the transmitter and the source of the RREQ into the route table.
The RREQ is flooding throughout the network.
When the node 4 received the RREQ, the reverse route is established (4-->1) and the node 4 tries to send the route reply (RREP) to the node 1 (the source of the RREQ).
See above figure. RREP is forwarded to node 4, because of the next hop node information in the route table.
While RREP transmitting to the node 1, the forward route (1-->4) is established.
After that, the data messages can be forwarded from the node 1 to the node 4 through the established route.
When data transmission fails several times, the route error (RERR) packet is sent to the
source node.
Upon receiving the RERR, a node deletes the
route information, for the source and destination pair, in the route
table. When the source node is received the RERR, it restarts the route discovery
by broadcasting a new
RREQ packet.
This program was tested with different platforms:
TOSSIM,
MicaZ, Mica2,
Tmote, and Hmote.
I believe, it will be working with other platform because it's a network layer protocol. If you encounter any problem, email me.