Tymo

TYMO: DYMO on TinyOS

TYMO is the implementation on TinyOS of the DYMO protocol, a point-to-point routing protocol for Mobile Ad-hoc Networks (MANETs). It was initially designed by the IETF to find routes dynamically on top of the IP stack. In TYMO, we changed its packet format and implemented it on top of the Active Message stack of TinyOS.

DYMO: Dynamic MANET On-demand

As a reactive protocol, DYMO does not explicitly store the network topology. Instead, nodes compute a unicast route towards the desired destination only when needed. As a result, little routing information is exchanged, which reduces network traffic overhead and thus saves bandwidth and power. Also, since little routing state is stored, DYMO is applicable to memory constrained devices like motes.

When a node needs a route, it disseminates a Route Request (RREQ), which is a packet asking for a route between an originator and a target node. The packet is flooded to the entire network or within a number of hops from the originator. When the packet reaches its target (or a node that has a fresh route towards the target), the node replies with a Route Reply (RREP). A route reply packet is very similar to a route request, but it follows a unicast route and no reply is triggered when the target is reached.

When nodes receive a RREQ or a RREP, they cache information about the sender at the link level and the originator, so that they know a route to the orginator that can be used later (if it is fresh enough) without sending a RREQ. The nodes have the possibility to accumulate the path followed by the packet in the packet itself. So, when nodes disseminate a RREQ or RREP, a lot of information can actually be obtained from the packet, much more than a route between two nodes.

When routes have not been used for a long time, they are deleted. If a node is requested to forward a packet through a deleted route, it generates a Route Error (RERR) message to warn the originating node (and other nodes) that this route is no longer available. As another route maintenance mechanism, DYMO uses sequence numbers and hop counts to determine the usefulness and quality of a route.

MH

The purpose of DYMO is to find routes on demand. To transport data along these routes, we designed and implemented a very simple transport protocol that we simply called MH for MultiHop. It does nothing more than forwarding packets unless the receiving node is the target of the packet.

Usage

If you are familiar with the TinyOS Active Message stack, sending and receiving MH messages should be fairly easy, since this is done through the same interfaces.

Interfaces, Components and Wiring

To send and receive MH messages, you need to declare the usage of a couple of interfaces:

     module TestM {
       uses {
         interface SplitControl;
         interface AMPacket as MHPacket;
         interface Packet;
         interface Receive;
         interface AMSend as MHSend;
       }
     }
   

• The SplitControl lets you start and stop the MH and DYMO services, which is required to use them afterwards.
• The AMPacket and Packet interfaces let you fill a packet before sending it or read the content of a received packet.
• The Receive and MHSend interfaces let you receive and send MH messages in exactly the same way as TinyOS link layer packets.

To ease the work of the user, we created a single component that wires together all the modules in order to provide a MH service that relies on the DYMO service to route packets. This component is called DymoNetworkC. Just as TinyOS does with actives messages on the link layer, DymoNetworkC provides an array of Receive and Send interfaces so that several applications can use MH independently. As a result, to wire your code to DymoNetworkC, you need a configuration similar to:

     implementation {
       components TestM, DymoNetworkC;
       
       TestM.SplitControl -> DymoNetworkC;
       TestM.Packet       -> DymoNetworkC;
       TestM.MHPacket     -> DymoNetworkC;
       TestM.Receive      -> DymoNetworkC.Receive[1];
       TestM.MHSend       -> DymoNetworkC.MHSend[1];
     }

Code example

Once this is set up, you can send and receive messages just as regular AM messages, for example (you need to set up the Boot and Timer interfaces in addition to the above for this to work):

     message_t packet;
     
     //MH and AM addresses are the same
     enum {
       ORIGIN = 1, 
       TARGET = 6,
     };

     event void Boot.booted(){
       call SplitControl.start();
     }
     
     event void SplitControl.startDone(error_t e){
       if(call MHPacket.address() == ORIGIN){
         call Timer.startPeriodic(2048);
       }
     }

     event void Timer.fired(){
       nx_uint16_t * payload = call Packet.getPayload(&packet, NULL);
       error_t error;
       *payload = 1664; //Define the content of your message as you wish
       error = call MHSend.send(TARGET, &packet, sizeof(*payload));
       if(error == SUCCESS){
         //Good!
       } else {
         //Something's wrong...
       }
     }

     event void MHSend.sendDone(message_t * msg, error_t e){
       if((e == SUCCESS) && (msg == &packet) && (call MHPacket.address() == ORIGIN)){
         //Even better!
       } else {
         //The packet couldn't be sent!
       }
     }
 
     event message_t * Receive.receive(message_t * msg, void * payload, uint8_t len){
       if(call MHPacket.address() == TARGET){
         //Message received!
       } else {
         //This shouldn't happen...
       }
       return msg;
     }

     event void SplitControl.stopDone(error_t e){}

Configuration

There are various preprocessor variables that can be set to alter the caracteristics of DYMO. The list and default values can be found in lib/net/tymo/dymo/dymo_routing.h. Here is the meaning of each of them:

• MAX_TABLE_SIZE: Number of entries the routing table can store. When this number is reached, the oldest route is deleted if a new route needs to be added.
• DYMO_HOPLIMIT: Number of hops a DYMO packet can go through before being dropped.
• DYMO_ROUTE_AGE_MAX: Maximum amount of milliseconds a route can be kept.
• DYMO_ROUTE_TIMEOUT: Maximum amount of milliseconds a route can be kept without being used.
• DYMO_APPEND_INFO: 1 to append info to forwarded routing messages, 0 otherwise.
• DYMO_INTER_RREP: 1 to allow intermediate RREP, 0 otherwise.
• DYMO_FORCE_INTER_RREP: 1 to send intermediate RREP even without target's seqnum in the RREQ.
• DYMO_LINK_FEEDBACK: 1 to use acks to detect broken links.

Please refer to the DYMO specifications for more information on this caracteristics and their role.

Limitations

This project cannot be considered as stable yet. There are a couple of bugs hidden in the code, and there are various things to accomplish to improve the project:

• Debug the code and improve its efficiency;
• Test more thoroughly the code;
• Update the code to reflect latest changes in the draft specs of DYMO;
• Refactor some pieces of code to be reusable by other protocol implementors;