Ausarbeitung/wiselib.tex

   1 \section{Wiselib}
   2 The \definition{Wiselib}\cite{wiselib} is a C++ algorithm library for
   3 sensor networks, containing for example algorithms for routing, localization and
   4 time synchronization, and is strongly focused on portability and cross-platform
   5 development. In particular, it allows the user to develop applications that run
   6 on different hardware platforms without the need to change the code, and it
   7 strongly uses C++ templates to achieve that feature. Amongst the supported
   8 platforms are diverse sensor node platforms, like iSense, Contiki and TinyOS,
   9 but there are as well implementations for the diverse x86-compatible Personal
  10 Computer platforms, and the Shawn sensor network simulator.
  11
  12 \subsection{Architecture}
  13 \label{sec:wiselib:arch}
  14 \paragraph{Concepts and Models}
  15 Wiselib makes strong uses of \definition{concepts} and \definition{models} as
  16 central design objects. Concepts serve as an informal description of interfaces,
  17 only existent in documentation, defining expected parameters and types. Models
  18 however implement these interfaces in C++ code while fulfilling their
  19 specification. The Wiselib algorithms can in turn rely on the concepts as a
  20 generic specification, and take models as template parameters to use their
  21 functionality, so a function call will be immediately resolved to a specific
  22 model at compile time without the need for an additional function call as it is
  23 the case with virtual inheritance. Furthermore, this also allows usage on
  24 platforms which do not have support for C++, as the bytecode generated by the
  25 compiler does not include C++ specific extensions (no virtual function tables,
  26 and templates are resolved at compile time) and can be linked against any
  27 Standard C Library.
  28
  29 This makes cross-platform development easily possible. For example, to implement
  30 a routing algorithm, one can rely on the concept of a Radio to send and receive
  31 data packets, without needing to implement code specific to the used radio
  32 hardware. The users of that routing algorithm can now choose which radio model
  33 they want to use, according to their needs and the underlying hardware, provided
  34 that their radio model also implements the same Radio concept that the routing
  35 algorithm uses.
  36
  37 \begin{figure}
  38   \centering
  39   \includegraphics[width=.8\textwidth]{images/Wiselib-Arch.pdf}
  40   \caption{Wiselib architecture\label{fig:wiselib-arch}}
  41 \end{figure}
  42 Besides algorithms, and basic concepts and models, the Wiselib also consists of
  43 two other main parts: the internal interface and the external interface (see
  44 Figure~\ref{fig:wiselib-arch}).
  45
  46 \paragraph{External Interface}
  47 The \definition{External Interface} provides access to the underlying \ac{OS},
  48 like iSense, Contiki, Shawn\ldots and defines concepts like a Radio or a Timer.
  49 Thus, the concepts are as generic as possible to match all supported operating
  50 systems and provide a light-weight abstraction to the underlying \ac{OS}. These
  51 concepts sometimes extend the generic concepts, for example there is a TxRadio
  52 which has the ability to set the transmission power on the radio. The models
  53 (for example an iSenseRadioModel or a ShawnTimerModel) implement these concepts
  54 on the specific operating system, and can be passed around as template
  55 parameters.
  56
  57 \paragraph{Internal Interface}
  58 The \definition{Internal Interface} defines concepts and models for data
  59 structures that can be used in algorithms. This allows to specialize for
  60 restricted platforms; for instance a wireless sensor node without dynamic memory
  61 management can use a static implementation of lists and other containers,
  62 whereas a full-grown desktop can use the dynamic implementation provided by the
  63 C++ \ac{STL}. For this purpose, the Wiselib also contains the
  64 \acused{pSTL}\definition{pico Standard Template Library} (\acs{pSTL}) which
  65 implements a subset of the \ac{STL} without the use of dynamic memory
  66 allocation.
  67
  68 \paragraph{Stackability}
  69 Another central design principle used in the Wiselib is
  70 \definition{stackability}, which describes the possibility to stack
  71 implementations of the same concept, thereby building a layered structure. For
  72 example, one could stack a cryptography algorithm on top of a radio model, which
  73 both implement the Radio concept. In this case, the cryptography layer doesn't
  74 have to know anything at all about the underlying implementation, as long as it
  75 can use the Radio concept of the underlying layer. And it can even provide the
  76 same interface to a possibly higher layer in order to provide transparent packet
  77 de- and encryption over the radio.
  78
  79 \subsection{Roomba Control}
  80 Even more interesting is the fact that the Wiselib includes code to control an
  81 iRobot Roomba\index{Roomba} over a serial interface, and getting access to its
  82 internal sensor data, using the \ac{ROI}\index{Roomba Open Interface} mentioned
  83 earlier. For this purpose, it defines two concepts for Robot Motion:
  84
  85 \paragraph{\concept{TurnWalkMotion} concept}%\index{TurnWalkMotion (concept)}
  86 This concept represents a simple robot that can turn on the spot and walk
  87 straight, without automatic stopping.
  88 \begin{description}
  89   \item Types:
  90     \begin{description}
  91       \item[\fnfont{velocity\_t}] Type for velocity measurement
  92       \item[\fnfont{angular\_velocity\_t}] Type for angular velocity measurement
  93     \end{description}
  94   \item \todo{clearpage?} Methods:
  95     \begin{description}
  96       \item[\fnfont{int turn(angular\_velocity\_t)}] turn the robot with a
  97         constant angular velocity
  98       \item[\fnfont{int move (velocity\_t)}] move the robot straight with a
  99         constant velocity
 100       \item[\fnfont{int stop()}] stop the robot
 101       \item[\fnfont{int wait\_for\_stop()}] hold the execution until the robot
 102         has stopped
 103     \end{description}
 104 \end{description}
 105
 106 \paragraph{\concept{Odometer} concept}%\index{Odometer (concept)}
 107 This concept represents an Odometer which tracks motions over time.
 108 Whenever the object turns or moves, internal counters will adjust their
 109 guessing of the object's traveled distance and current orientation.
 110 \begin{description}
 111   \item Types:
 112     \begin{description}
 113       \item[\fnfont{angle\_t}] Type for angle measurement
 114       \item[\fnfont{distance\_t}] Type for distance measurement
 115     \end{description}
 116   \item Methods:
 117     \begin{description}
 118       \item[\fnfont{angle\_t angle()}] return the current angle
 119       \item[\fnfont{int reset\_angle()}] reset the angle of the object
 120       \item[\fnfont{distance\_t distance()}] return the current distance
 121       \item[\fnfont{int reset\_distance()}] reset the distance of the object
 122       \item[\fnfont{int register\_state\_callback (T *obj)}] register a callback
 123         that gets called when the state changes
 124       \item[\fnfont{int unregister\_state\_callback (int)}] unregister a
 125         previously registered callback
 126       \item[\fnfont{int state()}] return the current state
 127     \end{description}
 128 \end{description}
 129
 130 \paragraph{ControlledMotion model}
 131 On top of the \concept{TurnWalkMotion} and \concept{Odometer} concepts builds
 132 the \class{ControlledMotion} model. It takes implementations of each of these
 133 concepts as template parameters and extends the simple turn-and-walk paradigm by
 134 a temporal dimension, which let the robot stop after a specific time interval.
 135 In particular, it provides the following methods:
 136 \begin{description}\item
 137 \begin{description} % to match with the indentation level above
 138   \item[\fnfont{int move\_distance(distance\_t, velocity\_t)}] move the robot
 139     straight by a given distance with a given velocity
 140   \item[\fnfont{int turn\_about(angle\_t, angular\_velocity\_t)}] turn the robot
 141     about a given angle with a given angular distance
 142   \item[\fnfont{int turn\_to(angle\_t, angular\_velocity\_t)}] turn the robot
 143     to a given orientation with a given angular distance
 144 \end{description}
 145 \end{description}
 146
 147 The class first registers a callback function at the given Odometer instance,
 148 and then uses its distance and angle values to control the robot over the
 149 TurnWalkMotion instance. Everytime the state of the robot changes (i.~e. new
 150 data from its sensors are received), it compares the new actual values with the
 151 target values given by the user through the functions above, and if the actual
 152 values exceed the target values, the robot is stopped.
 153
 154 \paragraph{Underlying Roomba Implementation}
 155 The actual communication with the Roomba is done in the
 156 \class{RoombaModel} class. It implements the
 157 aforementioned \concept{TurnWalkMotion} and \concept{Odometer} concepts and
 158 therewith allows the interaction with a \class{ControlledMotion} instance. In
 159 particular, it manages the serial communication with the Roomba and translates
 160 the function calls \fnfont{turn()}, \fnfont{move()} and \fnfont{stop()} of the
 161 TurnWalkMotion concept to the according parameters for the \ac{ROI} \cmd{Drive}
 162 command, reads a subset of the Roomba's sensors and presents the sensor data to
 163 the user, and, while implementing the Odometer concept, calculates the covered
 164 distance and angle from the Roomba's right and left wheel rotations.
 165
 166 The sensor data is read from the Roomba using the \cmd{Stream} command on the
 167 \ac{ROI}, which results in a sensor data packet (see Section
 168 \ref{sec:roi-stream-packet}) every 15~ms, and $66.67$ packets per second. At a
 169 speed of 19,200 baud in mode \ac{8N1}, the maximum size of a data packet is
 170 $19,200 \div (66.67 \times 9) = 32$ byte, so at the moment only the sensor
 171 packets \emph{encoder counts left/right} (IDs~\magicvalue{0x2b},
 172 \magicvalue{0x2c}, 2+2 bytes), \emph{battery voltage/current/charge/capacity}
 173 (IDs~\magicvalue{0x16}, \magicvalue{0x17}, \magicvalue{0x19},
 174 \magicvalue{0x1a}, 2+2+2+2 bytes) are streamed, which add up to 18 data bytes +
 175 3 header/checksum bytes. There has currently been no success yet in
 176 communicating at the higher speed of 115,200 baud.
 177
 178 Also there has been research to use the distance and angle values that the
 179 Roomba itself provides (sensor packet~IDs \magicvalue{0x13} and
 180 \magicvalue{0x14}). However, according to the \ac{ROI} Specification these
 181 values are integer values, and the value is reset to zero every time it is read.
 182 By using the \cmd{Stream} command on the \ac{ROI} and therefore reading these
 183 values every 15~ms, the Roomba cannot move fast enough to increment these values
 184 to \magicvalue{1}, so everytime \magicvalue{0} is read. It is obvious that
 185 these sensor values are not suited for such rapid evaluations, and can only be
 186 used for larger distances and angles. Nevertheless, since the Wiselib Roomba
 187 control needs to keep track of the Roomba's current position and orientation as
 188 fast as possible to maintain a certain accuracy in movement, the distance and
 189 angle values as provided by the Roomba itself cannot be used. On the other hand,
 190 working with the Roomba's wheel encoder counts (sensor packet~IDs
 191 \magicvalue{0x2b} and \magicvalue{0x2c}) has proven itself quite acceptable.
 192 After a few test runs, the number of encoder counts per~mm for straight
 193 walks turned out as $2.27$, and for turning on the spot, $2.27 \times 115 =
 194 261.05$ encoder counts per radian, which is the number of encoder counts per~mm
 195 multiplicated with half the Roomba's wheelbase. So when new sensor data is read
 196 each 15~ms, the RoombaModel implementation calculates the \concept{Odometer}
 197 distance and angle from these values.