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