AODV Implementation for TinyOS

TinyAODV is an open source implementation of the AODV protocol. I started working on an implementation of the protocol by Junseok Kim but I completely rewrote the code during the April of 2011 after fixing a small number of bugs because I needed to restructure the modules in order to add support for broadcast messages. It is essentially a simple routing algorithm that allows the end user to send/receive unicast and broadcast packages over N hops. In its foundation the ActiveMessages mechanism is used for transmission of packages over 1 hop.

---

The following types of interfaces are available for use.

• SplitControl
• AODVBroadcast
• AODVUnicast

AODVBroadcast

command error_t broadcast(message_t *msg, uint8_t len, uint8_t max_hops)

• msg: Message to be broadcasted
• len: Length of the message
• max_hops: Maximum number of hops the message will travel

Return Values:

• Currently TinyAODV is best-effort for broadcast messages there is no error report on them as such AODVBroadcast.broadcast() always returns SUCCESS

command void* getPayload(message_t *msg, uint8_t size)

• msg: Message for which the buffer will be returned
• size: Desired buffer size

Returns NULL on error, otherwise a pointer to the buffer is returned.

event void receive(am_addr_t src, am_addr_t last_hop, uint8_t hops, uint8_t data[], uint8_t len)

• src: The originating node address
• last_hop: The address of the node that forwarded the packet to the receiver
• hops: Times the message was broadcasted untill it reached the receiver
• data: The data contained in the message
• len: Size of the data

AODVUnicast

command error_t send(am_addr_t addr, message_t *msg, uint8_t len, uint8_t max_hops)

• addr: Destination address
• msg: Message to be sent
• len: Length of the message
• max_hops: Maximum number of hops the message will travel

Return values:

• SUCCESS if there is routing information regarding the destination address
• EBUSY if there is no routing info for the destination, the message will be pushed into the message buffer but it is not guaranteed to be delivered

event void sendDone(message_t *msg, error_t error)

• msg: Message that was sent
• error: Error code
  • SUCCESS on succesfull send to the next hop
  • Otherwise please look at the ActiveMessages error codes

command void* getPayload(message_t *msg, uint8_t size)

• msg: Message for which the buffer will be returned
• size: Desired buffer size

Returns NULL on error, otherwise a pointer to the buffer is returned.

command uint8_t maxPayloadLength() Returns the maximum payload size. ( Maximum ActiveMessageSize – sizeof(header_msg) )

event void receive(am_addr_t src, am_addr_t last_hop, uint8_t hops, uint8_t data[], uint8_t len)

• src: The originating node address
• last_hop: The address of the node that forwarded the packet to the receiver
• hops: Times the message was broadcasted untill it reached the receiver
• data: The data contained in the message
• len: Size of the data

---

Implementation Details

TinyAODV Message Buffer

At first glance using two AODVUnicast interfaces seems weird. TinyAODV was used to implement the Network layer of the POBICOS library, a decision was made to use two AODVUnicast interfaces in order to decouple the logic between PoDatagramTransportI and PoReliableTransportI. Currently both simply use AODVUnicast, the only difference is that PoDatagramTransportI can also handle broadcast messages via AODVBroadcast. In its core TinyAODV stores messages to be sent in a buffer, its maximum size can be set by editing TinyAODV.h. Since memory is finite there is a policy in place to determine whether a new message can be actually stored in the buffer. Messages are associated with a priority according to their type. The priorities are presented below in ascending order.

1. Broadcast
2. Unicast
3. Route Reply
4. Route Request

Higher priority messages may only replace lower ones in the buffer, with the exception of Broadcast messages, those may only replace older Broadcast messages.

TinyAODV Broadcast ID buffer

In order to reduce the number of times a node receives the same broadcasted message an algorithm was implemented which keeps tracks of which messages were forwarded to a node by its neighbours. Each node may remember up to SIZE_BCAST_IDS broadcast ids for a maximum of SIZE_NEIGHBOURS neighbours. Experiments show that this approach is more efficient than using a global buffer for broadcast ids without keeping track which node forwarded it last. Every broadcast id is associated with information about the address of the originating node so as to deduce whether an incoming broadcast message is stale or not. The algorithm works by testing an incoming broadcasted message’s id with every bcast_id known to the node ( at this time which neighbour forwarded the message is irrelevant since multiple paths may exist between two nodes ). If it is deemed “fresh” i.e. the node has not seen a more recent message originating from the source node the neighbour broadcast id buffer is updated. If the maximum number of entries for a neighbour is reached one is randomly evicted to make room for information about the newest message ( broadcast id and originating node address ).

---

Topology Parser

A simple topology parser was implemented using flex and bison on top of the proxy_mngr2 tool that is included with POBICOS. The first step to simulating a network is to compile a number of binaries which will then be used to simulate nodes. Each will have its own set of characteristics, depending on the binary that was chosen for it. An example topology to create a network with 2 “garage” and one “kitchen” nodes is below, Nodes 0 and 1 run the binary “garage” and node 2 runs the “kitchen” binary. Node 1 can send/receive messages from both 0 and 2 directly. However nodes 0 and 2 in order to send messages to each other have to first send them over 1 which will in turn forward them to the destination party.

# First the nodes of the network are specified in the following format
# <id> = <binary>
#      or
# <id> to <id> = <binary>
# Where ID is an integer and binary is the name of the binary that
# will be used by the node associated with ID
# ( BINARY is alphanumerical )

Nodes
{
  0 to 1 = garage;
  2 = kitchen;
}

# Next we define the way the nodes are interconnected
# unless a rule is explicitely written for a node, it adheres to the "default"
# option, which takes two values "none" and "all"
# [o] None means that it has no intermediate neighbours
# [o] All means that the specified node can receive messages from every other node
# Unless specified the "default: none" option is used
Topology
{
  default: none;

  0->1;
  1->0;

  1->2;
  2->1;
}

# Note:
#     1->2;
#  and
#     2->1;
#     1->2;
# are not the same, the first segment indicates that node 1 can receive
# messages  from node 2,
# the second segment describes a bidirectional link between the two nodes

The source code can be found here