Basic Design Components

Basic Design Components

Structure

The Wiselib is divided into multiple parts: The external interface that defines the interface to the OS, the internal interface that defines internally available data structures, and algorithms such as routing or time synchronization. As with other C++ template libraries such as the STL or CGAL, the fundamental design parts are concepts and models. A concept is an interface description, only existing in documentation. It describes exactly both the types that are defined in a class, and the provided methods with expected parameters. A model in turn is the implementation of one (or also more) concepts - each type and each method that is described in the concept must be provided in the model.

Algorithms are, as basically everything else within the Wiselib, implemented as templates. They expect the implementations (models) of several concepts as template parameters - e.g., a radio for sending messages and a timer for time-based event registration, thereby only knowing the interface description, and not which implementation is passed; thus, the compiler would resolve each call to the underlying OS directly at compile time. Consequently, it is not known inside an algorithm for which platform is will be compiled.

Next, each part of the Wiselib (connection to the underlying OS, data structures, platform independent serialization for heterogeneous message delivery) is described separately, as well as a first example of integrating a Wiselib algorithm in the own application.

External Interface - Os Facets

The External Interface provides access to the underlying OS. This can be a sensor node OS such as Contiki or the iSense OS, a simulator such as Shawn or TOSSIM, or also a component model such as OpenCom. It offers OS specific functionality; e.g., sending a message over the radio or the time-based registration of an event. The concepts for these functions are therefore held as generic as possible. For instance, the basic radio can only be used for sending a message to a given destination, registration of a callback for received messages, and returning the id of the node. Furthermore, there are concepts derived from the basic ones. In case of the radio, there are a TX radio (ability to change transmission power) and an extended-data-radio (ability to add extended data such as link quality indicator to received messages).

A subset of the concept of the radio, for example, looks as follows:

concept RadioFacet
{
  [...]

  int send( node_id_t receiver, size_t len, block_data_t *data );
  node_id_t id();
  template<class T, void (T::*TMethod)(node_id_t, size_t, block_data_t*)>
    int reg_recv_callback( T *obj_pnt );
}

Example concepts for external interface/Os facets are:

• Os Facet provides information about the OS, and also defines a standard radio, a standard timer, ...
• Radio Facet allows sending and receiving messages
• Timer Facet allows registration of events/callbacks after a given time
• Clock Facet allows getting the current system time
• ...

Internal Interface - Data Structures

The internal interface contains data structures that can be used in an algorithm. For example, this may be a routing table for routing algorithms, or simply a list of neighbors provided by a neighborhood discovery algorithm. The reason for hiding these data structures behind concepts is that the Wiselib deals with a high amount of different platforms: From tiny micro-controllers such as a MSP430 running firmware that does not provide dynamic memory allocation, over high-end nodes such as an iMote2 that is able to even run an embedded Linux, to simulators running on ordinary PCs. In the former case, we need static data structures where the size is known at compile-time, whereas a PC may offer the STL. The approach with the Internal Interface allows for passing exactly the data structure that is most suitable for the appropriate target platform.

We provide a subset of the STL, called pSTL (pico STL), which includes the basic containers and sequences already known from the STL. The pSTL does not use any dynamic memory allocation, nor exceptions due to a lack of availability on some systems (and the corresponding overhead, even if it would be available on all platforms). When compiling for a certain platform, the user can decide which data structure is passed, and thus which level of flexibility can be used by an algorithm.

Our subset of the STL contains all important data structures such as list, stack, queue, and map. Based on these data structures, we also offer specializations: E.g., a routing table as a map with a node id as key type, or a neighbor list as a container of node ids.

Algorithms

The Wiselib contains different kinds of algorithms; from simple neighborhood discovery solutions, over routing algorithms, to localization or time-synchronization protocols. Each algorithm expects the needed connection to the underlying OS - the parts of the External Interface - and the needed data structures as template parameters. It then uses the appropriate models as described in the concept. An example may look as follows:

template<typename Os, typename Radio = typename Os::Radio>
class MyAlgorithm
{
public:
  int init(Radio& radio) { radio_ = &radio; }
  void run()
  {
    Radio::block_data_t buffer[10];
    radio_->send( Radio::BROADCAST_ADDRESS, sizeof(buffer), buffer );
  }
private:
  Radio *radio_;
}

The algorithm MyAlgorithm expects the OS it is compiled for, and a radio model as template parameter. It is then initialized with a reference to the radio (by definition, there is no instance of the OS available), which in turn is used in the run()-method by broadcasting a message. Each algorithm in the Wiselib follows this approach (Os functionality as template parameters, instances are passed in a init(...)-method).

Algorithms are also designed similar to appropriate concepts in the external interface - at least where possible. For instance, a routing algorithm must provide the same types and methods as the radio. Hence, such an algorithm can also be passed to another algorithm, where only an Os facet is expected, while being completely transparent to this algorithm. This allows for maximal flexibility in stacking algorithms together.

Among others, we have concepts for the following algorithms in the Wiselib:

• Routing Algorithms
• Clustering Algorithms
• Time-Synchronization Algorithms
• Localization Algorithms
• Energy-Preservation Algorithms (covering sleeping cycles, for example)

Message Delivery in Heterogeneous Systems

Due to the support for many different platforms, there are many diversities in bit-width, endianness, and alignment restrictions. For instance, the MSP430 is a 16-bit platform, whereas iSense is 32-bit; the MSP430 cannot read an uint16_t directly from an odd address; iSense requires quad-byte access when dealing with 32-bit values. We address this issue also with templates. Basically, there is a read and a write method available, both allowing for reading data from or writing data to a buffer. These methods can be specialized for individual systems via template specialization; hence, completely transparent for the user.

As an example, such a buffer can be accessed as follows.

block_data_t buffer[Radio::MAX_MESSAGE_LENGTH];
...
uint8_t value;
value = read<OsModel, block_data_t, uint8_t>( buffer );
...
uint16_t store = 42;
write<OsModel, block_data_t, uint16_t>( buffer + 4, store );

User Applications

Finally, an algorithm must be integrated in an user application. The Wiselib is basically only an algorithm library, not providing any compilation ability - compilation must be done from the application, where algorithms are included. However, a part of the Wiselib are several examples of how to integrate an algorithm.

There are two sub-folders, iapps and shawn_apps, the former showing examples of algorithms directly used in an iSense application, the latter contains examples of integration in a Shawn processor.

Furthermore, it is possible to create a so-called Generic Wiselib Application, which can be compiled for several platforms without changing any line of code; instead, just the make target. Examples can be found in the sub-folder applications and basically work as follows.

First, one must implement an application_main-method, which expects a parameter of type Os::AppMainParameter&`. Second, a class must be written that provides at least a init-method expecting the AppMainParameter as parameter. Inside the init-method, instances of Os facets must be created. Finally, the self-written class must be passed as template parameter to a class WiselibApplication, which in turn is called in the application_main-method. Altogether, this looks as follows.

#include "external_interface/external_interface.h"
#include "algorithms/routing/tree/tree_routing.h"

// OSMODEL is defined by the provided makefiles, and thus adapts automatically to current platform
typedef wiselib::OSMODEL Os;
typedef wiselib::TreeRouting<Os, Os::Radio, Os::Timer, Os::Debug> TreeRouting;

class TreeRoutingApplication
{
   public:
      void init( Os::AppMainParameter& value )
      {
         Os::Radio& radio = wiselib::FacetProvider<Os, Os::Radio>::get_facet( value );
         Os::Timer& timer = wiselib::FacetProvider<Os, Os::Timer>::get_facet( value );
         Os::Debug& debug = wiselib::FacetProvider<Os, Os::Debug>::get_facet( value );

         tree_routing.init( radio, timer, debug );
         timer.set_timer<TreeRoutingApplication, &TreeRoutingApplication::start>( 500, this, 0 );
      }
      // --------------------------------------------------------------------
      void start( void* )
      {
         tree_routing.send( 1, 0, 0 );
      }
   private:
      TreeRouting tree_routing;
};
// --------------------------------------------------------------------------
// --------------------------------------------------------------------------
// --------------------------------------------------------------------------
wiselib::WiselibApplication<Os, TreeRoutingApplication> routing_app;

void application_main( Os::AppMainParameter& value )
{
   routing_app.init( value );
}

Note that this way it is very easy to put the same algorithm on different hardware platforms, just by changing the makefile target.