Port WMTP to TinyOS 2.x

Table of Contents

People

Hugo Freire

Project Details:

Goal: WMTP - The Wireless Modular Transport Protocol is a WSN transport layer protocol developed within IST/TUL. Although the protocol itself is platform agnostic, it was specifically developed for the now deprecated 1.x version of TinyOS. The goal of this project is to port the entire protocol framework, including the core and all of the implemented features, to TinyOS 2.x. The porting effort should not be limited to a mere interface translation that would only ensure minimal compatibility, but should revise the entire system to make full use all of the new features that TinyOS 2.x provides. Additionally, a new adaptation layer should be developed to allow WMTP to be used by traditional TinyOS applications, without modifying their implementation code (i.e. simply by rewiring them).

Upon project completion, the updated system's performance should be retested and the new results should be posted, along with the new source code, to the project's web page.

Overview

This project aims to port WMTP - Wireless Modular Transport Protocol to TinyOS 2.x. WMTP [1,2] was intially implemented in TinyOS 1.x which is now deprecated. The goal proposed for this project is not a simply rewrite and adapt code for the newer version of TinyOS, it is also expected that WMTP make full use of the new features avaiable in this new version and additionally develop a new adaptation layer which should allow TinyOS applications make use of WMTP without any change on their code.

Journal

19th of August, 2009 - Tests and evaluations of the port were realized and submitted during this past week. The objectives for this project were achieved and concluded with satisfactory results. The port of WMTP to TinyOS 2.x has brought a lower code size and RAM footprint while using the new functionalites that TinyOS 2.x has to offer to their applications. Additionally a new adaptation layer was implemented to ease those applications that were designed without considering WMTP utilization. Following up this port and for future work, there is a need to extend the tests of WMTP to more realistic scenarios and possibly real deployment of applications making use of WMTP.

6th of August, 2009 - This project is reaching it's final days. During this past week the adaptation layer was implemented and submitted to the repository. This adaptation layer allows traditional non-aware WMTP applications to make use of WMTP functionalities without modifying their implementation, for example, for the majority of the applications out there, they only need to use WmtpAdapterC instead of the ActiveMessageC in their configuration files and include WMTP in their compile path with the desired features. The implementation of the adaptation layer and the evaluation and testing of the port is being done simultaneous and should be finnished in the beginning of the next week.

21th of July, 2009 - The source code that assures a minimal compatibility with TinyOS 1.x was submitted during this past week. Due to the fact that a minimal compatibility was done, I started implementing the new features provided by TinyOS 2.x. At this point WMTP TinyOS 2.x is already making full use of queues provided by QueueC instead of the previous used linked lists. The planning was updated to reflect the advances made this past week. Added a new section describing the new ADTs used in TinyOS 2.x.

6th of July, 2009 - A simple port was commited to the repository this past week. Some small port highlights are given in detail in Noteworthy port changes. Introduced memory footprint comparison charts which reflect the effort on trying to reduce the memory usage by WMTP throughout this project. The Changes section now reflects the history log of the repository (easier to maintain). The planification was updated to match the drawbacks experienced this past month.

27th of May, 2009 - Planification was updated reflecting the delays on revising the system architecture. Added RSS to the webpage so that the project can be easily monitored by the course staff. Created a branch from the current trunk of WMTP on the GEMS code repository. Finished the minimal requirements. Analysed the TinyOS 2.x interfaces that should be taken into account in the additional requirements.

Planning

planning.gif: 1202x310, 14k (February 01, 2010, at 06:24 PM)
Planning

Requirements

  • Minimal requirements: A minimal porting compatibility from previous version. which can follow the suggestions made on the TinyOS 2.x documentation. Take into account the updated Coding Standard (TEP 3). A directory structure that allows an easy merge with TinyOS directory distro (contrib distro).
  • Additional requirements: A revision of the implementation of the system architecture, mainly on WMTP Core interfaces, message formats, the linked lists, memory subsystem and features to make use of the new TinyOS native functionalities: TimerC (TEP 102), BitVectorC, PoolC, QueueC. An adaptation layer which should offer an easier way for non-aware WMTP applications to make use of WMTP (typically traditional TinyOS applications).

Noteworthy porting changes

  • String substitutions

%s/TOS_LOCAL_ADDRESS/TOS_NODE_ID/g

%s/TOS_BCAST_ADDR/AM_BROADCAST_ADDR/g

%s/TOS_MsgPtr /message_t */g

%s/TOS_Msg /message_t/g

%s/interface Timer/interface Timer<Milli>/g

%s/(TIMER_ONE_SHOT,/OneShot(/g

%s/(TIMER_REPEAT,/Periodic(/g

%s/TimerC/new TimerMilliC()/g

%s/event result_t Timer\.fired/event void Timer\.fired/g

%s/RandomLFSR/RandomC/g

%s/rand()/rand32()/g

%s/components Main/components MainC/g

%s/result_t/error_t/g

%s/dbg(DBG_USR1/dbg("DBG_USR1", /g

%s/dbg(DBG_USR2/dbg("DBG_USR2", /g

%s/includes \(.\+\);/#include "\1"/g

%s/Leds\.red/Leds\.led0/g

%s/Leds\.green/Leds\.led1/g

%s/Leds\.yellow/Leds\.led2/g

%s/PLATFORM_PC/TOSSIM/g

%s/bool/uint8_t/g

  • result_t/error_t and SUCCESS/FAIL

The value of SUCCESS and FAIL used for example on the return value of a call has changed in TinyOS 2.x:

Some typical cases where one uses the implicit return values:

  • Boot-up sequence changes

Typical scenarios where changes occur in the boot-up sequence:

  • Components/interfaces changes

Typical components and interfaces changes:

  • tos_time_t

TinyOS 2.x contributors and developers decided to stop using tos_time_t which basically is a two 32 bit integers structure to store time related variables due to its overwhelming size and most often unnecessary time lenght. In WMTP it was decided to use just a 32 bit integer which gives us ~49 days before an overflow occurs. Typically this type of overflow will not be a critical issue which can lead to node or transport failure.

  • TOS_Msg/message_t

In TinyOS 2.x we're able to access the fields of a packet through the AMPacket interface as can be seen here:

New features in TinyOS 2.x to be used

  • Time

TinyOS 2.x has two timer interfaces: Timer, which is synchronous and operates in task context, and Alarm, which is asynchronous and involves directly handling a hardware interrupt. For the most part, applications use Timer. Some low-level systems (such as MAC protocols) or applications that require precise timing use Alarm. Additionally, nodes can access their local time with the LocalTime interface. A node's local time starts when it boots, so different nodes typically do not have the same time. 

      The basic Timer abstraction is TimerMilliC:

      generic configuration TimerMilliC() {
        provides interface Timer<TMilli>;
      }

      Local time can be obtained from LocalTimeMilliC:

      configuration LocalTimeMilliC {
        provides interface LocalTime<TMilli>;
      }
  • Data Structures
    • BitVectorC

BitVectorC provides the abstraction of a bit vector. It takes a single parameter, the width of the vector. The BitVector interface has commands for getting, setting, clearing, and toggling individual bits or all of the bits at once. Because of nesC's heavy inlining, using BitVectorC is preferable to writing our own bit vector macros within a component. BitVectorC allocates N/8 bytes for an N-bit wide vector. 

            generic module BitVectorC(uint16_t max_bits) {
              provides interface BitVector;
            }
  • QueueC

QueueC provides the abstraction of a queue of items with a fixed maximum size. It takes two parameters: the type of the items it stores and the maximum size of the queue. The Queue interface has commands for enqueuing items on the end of the queue, dequeuing the head of the queue, and commands for checking the queue size. It also allows random-access lookup: you can scan the queue. 

            generic module QueueC(typedef queue_t, uint8_t QUEUE_SIZE) {
              provides interface Queue<queue_t>;
            }

QueueC is used heavily in networking protocols like WMTP. A routing protocol, for example often creates a QueueC of pointers to message buffers (message_t *) for its forwarding queue, as well as a PoolC to allocate a number of buffers so it can receive packets to forward.

  • PoolC

PoolC is the closest thing TinyOS has to a dynamic memory allocator. It takes two parameters: the type of object to allocate, and how many. Components can then dynamically allocate and free these objects to the pool. But as the maximum pool size is set at compile-time, a memory leak will cause the pool to empty, rather than cause the heap and stack to collide. Because it does the allocation, you specify a type to PoolC, but its commands use pointers to that type. For example, if we allocate a pool of message_t buffers, then calls to Pool pass message_t* [3]. 

            generic configuration PoolC(typedef pool_t, uint8_t POOL_SIZE) {
              provides interface Pool<pool_t>;
            }

Adaptation layer for non-aware WMTP applications

  • Proposed adaptation layer

A typical stack layer approach is proposed to allow a lightweight adaptation mechanism to enable non-aware WMTP applications (traditional TinyOS applications) to make a limited use of WMTP functionalities without needing to change their implementation.

The goal is to allow traditional applications make use of WMTP just by modifying their configurations, i.e. wiring toWMTP adapter component instead of the Active Message component.

Implementation of the adaptation layer The adaptation layer is implemented in WmtpAdapterP which makes use of WMTP through normal interfaces and allows to export WMTP functionalities to other applications through WmtpAdapterC with the use of more common and traditional interfaces like AMSend and Receive interfaces found in TinyOS distribution. Although WMTP makes use of a StdControl interface to allow control of its execution, there was a need to translate this control logic into a split-phase control through the use of a SplitControl interface taking into account that most traditional applications make use of ActiveMesssageC.SplitControl to start the radio before any attempt to send or receive messages from it.

  • Typical WMTP application interfaces for components that are aware of WMTP existence

The following component WmtpAwareAppC shows a configuration wiring WmtpAwareAppP interfaces to WmtpC. These are the basic interfaces provided by WMTP to the application layer. Commands and event description are ommited for simplicity. For a more detailed description of WMTP interfaces, commands and events, please consult WMTP documentation in the References section. 

      WMTP Aware Application Interfaces

      configuration WmtpAwareAppC {
      } implementation {

        components ..., WmtpAwareAppP, WmtpC;
        ... 
        WmtpAwareAppP.WmtpControl -> WmtpC.StdControl;
        WmtpAwareAppP.WmtpConnectionManager -> WmtpC.WmtpConnectionManager[unique["WmtpApplicationId"]];
        WmtpAwareAppP.WmtpSendMsg -> WmtpC.WmtpSendMsg[unique["WmtpApplicationId"]];
        WmtpAwareAppP.WmtpReceiveMsg -> WmtpC.WmtpReceiveMsg[unique["WmtpApplicationId"]];
        ...
      }
  • WMTP adaptation component that permits traditional applications that are non-aware of WMTP to make use of WMTP functionalities

WmtpNonAwareAppC component shows a configuration wiring a non-aware WMTP application to the WMTP adapter component. The WmtpAdapterC component, encapsulates a limited WMTP logic and exports it in common, traditional interfaces. For a more detailed description of SplitControl, AMSend and Receive interfaces, commands and events, consult the TinyOS documentation that is available in it's distribution. 

      WMTP Non-Aware Application Interfaces

      configuration WmtpNonAwareAppC {}
      implementation {
        components ..., WmtpNonAwareAppP;
        //components new AMSenderC(AM_NONAWARE_APP_MSG);
        //components new AMReceiverC(AM_NONAWARE_APP_MSG);
        //components ActiveMessageC;
        components WmtpAdapterC;
        ...
        //WmtpNonAwareAppP.Receive -> AMReceiverC;
        WmtpNonAwareAppP.Receive -> WmtpAdapterC.Receive;
        //WmtpNonAwareAppP.AMSend -> AMSenderC;
        WmtpNonAwareAppP.AMSend -> WmtpAdapterC.AMSend;
        //WmtpNonAwareAppP.AMControl -> ActiveMessageC;
        WmtpNonAwareAppP.AMControl -> WmtpAdapterC.SplitControl;
        //WmtpNonAwareAppP.Packet -> AMSenderC;
        WmtpNonAwareAppP.Packet -> WmtpAdapterC.Packet;
        ...
      }

In this code excerpt we can see with some detail that we easily switched from using ActiveMessageC to WmtpAdapterC component allowing the non-aware WMTP application to make use of WMTP without needing to modify their implementation. For ease of use, the WmtpAdapterC component also explorts the Packet and AMPacket interface. The features available for WMTP are accessible for these non-aware WMTP applications likewise the aware applications, they just need to be included during the compilation process and the WmtpAdapterP will detect them and make use of them.

Port considerations

The following version of compilers, libraries and tools were use:

  • Memory usage

Memory footprint throughout the porting of WMTP (repository revision). The memory charts displayed below reflect the compilation of WMTP in TinyOS 2.x with the application TestWMTP for the MICAz platform.

The following table shows the ROM code size and and RAM footprint of WMTP implementation in the previous TinyOS 1.x and the actual TinyOS 2.x version compiled for the MICAz platform. The size in bytes represents each part compiled individually and idenpendently from other parts. The total ROM value of the sum of all parts compiled individually may be larger than the size of all parts when compiled together due to compiler optimizations.

The following chart represents the compilation of only the WMTP stack for TinyOS 2.x comparing the RAM size of its core and modules.

Port test and evaluation

  • Simulator

In order to test and evaluate the port success and performance, a special test application created by the author of WMTP and now ported will be simulated under the TOSSIM enviroment. This simulator was built to reproduce real-life WSN conditions very closely and, as such, simulates multiple nodes arranged according to specific topology.

  • Test Scenarios

The test scenario chosen was the same used by the author of WMTP while testing and evaluating his implementation on TinyOS 1.x. In this test scenario, there are a total of sixe sensor nodes, of which three are source nodes, which generate data, two are relay nodes, that simply forward the data, and one is a sink node, which consumes the data [1].

  • The author also made a special exception scenario for the quality-of-service assessment simulations. Since quality-of-service is supposed to provide assured performance levels, even in the most unfair of enviroments, a special scenario was used for these tests.
  • Test Application and Methodology

The performance monitor component developed by the author was also ported, in order to measure certain specific metrics, such as the number of data packets and radio messages generated and received, as well as the minimum core queue availability during the measured period. The ported performance monitor module periodically dumps and resets its statistical counters every 10 seconds. This output data will be processed using a traditional spreadsheet for charts creation.

  • Simulation Results
    • Base-line Scenario

This scenario represents the lowest possible performance case in which WMTP is not making any effort whatsoever to mitigate the congestion felt on the network.

(:thumb "WSN-2009.WMTPPortProject/hfreire-wmtp_tos2-baseline-generated.jpg" captionfmt="Planning")

As we can see the availabe core queue on all three elements are depleted quite soon leading to a severe congested network and a high rate of unreceived packets on all elements. In this type of scenario we have a high overhead on transmitting a packet, mainly due to the massive unreceived packets these nodes are subjected to.

  • Throttling and Flow-control

For both throttling and flow-control, a data generation rate of two packets every second was applied. The only difference between these two is which node decides at what rate the data is generated. In a throttling scenario the sources are the ones who decide this rate, while on a flow-control scenario this decision is left to the sink node. The following 4 charts represent the generated packet rate, minimum core queue availability, unreceived packets and overhead present in a simulation with throttling enabled.

The results show that throttling works as expected. In these results we can see a steady packet rate generation defined by the throttling mechanism which prevents nodes from exausting their core queues. We can also confirm that the small rate of unreceived packets allows for a small overhead while transmitting a packet.

  • Congestion-Control and Fairness

The following four charts reflect a simulation with congestion-control enabled and a size of 22 queue elements to mimic the conditions in the tweaked version test in the author thesis paper [1].

These results shows that congestion-control works as expected by mitigating congestion on the network on a considerable basis. Even though by defining a queue of 22 packets we manage to keep the nodes from depleting their queues, the high rate of unreceived packets leads to a less than desirable overhead on packet sending.

The fairness feature as tested and shown to work in the following charts works by defining the rate at which the core is able to send packets instead of operating on core queue availability like congestion-control.

The simulation results shows that the fairness feature operates as expected. A initial period of instability can be seen at the beginning, but once fairness starts to operate, it mitigates with success the existence of congestion in the network, keeping core queues from depleting and lowering the unreceived packets thus leading to a lower overhead.

In the following simulation we tested fairness with different weights on the three nodes. This simulation sets a weight of one, two, and three to each source, respectively.

Since the nodes farther away from the sink are the ones with the highest weight, they tend to generate more data, and so, are susceptible to more link layer packet collisions than the nodes with a lower weight.

  • WMTP Reliability

The following simulation tests WMTP reliability. Since reliability mechanisms make use of cached packets in the source and fowarding nodes it is understandable that the use of these reliability semantics may involve a high performance penalty.

The previous simulation shows that WMTP operates as expected, since the growth tendency of unreceived packets is unexistent, making it clear that the feature does, in fact provide full packet reliability. On the other hand, the generated packet rate cleary shows the performance penalty that reliability by it self brings to the network, leading to burstiness in the generated rates and severe overheads.

This previous simulation shows how WMTP reliability operates under extreme load, since each source is generating data at the highest rate that it physically can. In order to show how this feature works under a less stressing enviroment an additional simulation was carried. In which each source varied the rate at which it throttled its data generation. Starting by generating data every five seconds and then reducing this packet period by 250 ms, every 30 seconds thus ending up generating its data at the highest rate they physically can.

As shown by this simulation, for lighter loads WMTP reliability feature operates without congesting the network. This completly stops the packet generation burstiness and reducing the end-to-end delay to a minimum as can be seen in the unreceived packets chart.

The following simulation shows how WMTP reliability with congestion-control and fairness work simultaneously.

This simulation shows that WMTP reliability while simultaneously using congestion-control and fairness manages to obtain some advantages and disadvantages associated with each individual feature. The congestion-control feature has success in mitigating the overall congestion state of the network as the minimum core queue availability doesn't tend to zero but allows for a performance penalty by decreasing packet generation. Fairness feature is also shown to work in this scenario, since packet generation rates still converge torwards a common value.

  • Quality-of-Service

The following simulation tries to show the advantage of using WMTP quality-of-service. Two simulations were created, one with quality-of-service enabled and one with it disabled. Both simulations use the special quality-of-service scenario previously described. Nodes 1 and 4 generate data at the highest rate that they physically can, while the quality-of-service enabled node, node 5, generates a packet every 200 ms.

The results show that quality-of-service feature tends to obtain a slighty lower packet loss while maintaining the same received packet rate as it's quality-of-service disabled simulation.

Source

The source code of WMTP for TinyOS 2.x can be found in TinyOS 2.x Contribuitions CVS repository

Documents

  • 19/08/09 - Report (pdf)
  • 19/08/09 - Results (tar.gz)

References

[1] Luís D. Pedrosa, "WMTP: Wireless Modular Transport Protocol", MSc Thesis, Instituto Superior Técnico, Technical University of Lisbon, 2007
[2] Luís D. Pedrosa, Rui M. Rocha, "WMTP - A Modular WSN Transport Protocol: The Fairness Module", Nov. 2008
[3] Philip Levis, David Gay, "TinyOS Programming", Cambridge University Press, Feb. 2009