nido.tex

传感器网络中的嵌入式操作系统源代码

\vspace{0.2in}
\begin{tabular}{ll}
all:      & Enable all available messages \\
boot:     & Simulation boot and StdControl\\
clock:    & The hardware clock\\
task:     & Task enqueueing/dequeueing/running\\
sched:    & The TinyOS scheduler\\
sensor:   & Sensor readings \\
led:      & Mote leds\\
crypto:   & Cryptographic operations (e.g., TinySec)\\
route:    & Routing systems\\
am:       & Active messages transmission/reception\\
crc:      & CRC checks on active messages\\
packet:   & Packet-level transmission/reception\\
encode:   & Packet encoding/decoding\\
radio:    & Low-level radio operations: bits and bytes\\
logger:   & Non-volatile storage\\
adc:      & The ADC \\
i2c:      & The I2C bus\\
uart:     & The UART (serial port)\\
prog:     & Network reprogramming\\
sounder:  & The sounder on the mica sensor board\\
time:     & Timers\\
sim:      & \sim internals\\
queue:    & \sim event queue\\
simradio: & \sim radio models\\
hardware: & \sim hardware abstractions\\
simmem:   & \sim memory allocation/deallocation (for finding leaks)\\
usr1:     & User output mode 1\\
usr2:     & User output mode 2\\
usr3:     & User output mode 3\\
temp:     & For temporary use\\
\end{tabular}
\vspace{0.2in}
\normalsize

As an example, the statement

\scriptsize
\begin{verbatim}
        dbg(DBG_CRC, "crc check failed: \%x, \%x\n", crc, mcrc);
\end{verbatim}
\normalsize

\noindent will print out the failed CRC check message if the user has enabled
CRC debug messages, while

\scriptsize
\begin{verbatim}
        dbg(DBG_BOOT, "AM Module initialized\n");
\end{verbatim}
\normalsize

\noindent will be printed to standard out if boot messages are enabled. DBG
flags can also be combined, as in this example:

\scriptsize
\begin{verbatim}
        dbg(DBG_ROUTE|DBG_ERROR, "Received control message: lose our network name!.\n");
\end{verbatim}
\normalsize

\noindent This will print out if either route or error messages are enabled.

There are a set of bindings from ASCII strings to debug modes. For
example, setting DBG to ``{\tt boot}'' will enable boot message (by
setting the appropriate bit in the mask). Setting DBG to ``{\tt
boot,route,am}''\footnote{E.g. ``{\tt export DBG=boot,route,am}'' in bash,
``{\tt setenv DBG boot,route,am}'' in tcsh, etc.} will enable boot,
routing and active message output. Generally, the name of the flag in
TinyOS source is ``{\tt DBG\_}'', followed by the name of the DBG
option in all caps. For example, the environment variable value ``{\tt
am}'' enables {\tt DBG\_AM} messages, and the value ``{\tt usr1}''
enables {\tt DBG\_USR1} messages. Note that if you don't set DBG, then all
debug output is enabled and the simulation will run very slowly.

Four modes are reserved for application components: usr1, usr2, usr3,
and temp. Developers are urged to use these modes in their code. When
TinyOS is compiled for mote hardware, all of debug statements are
removed; we have verified that they add no instructions to the TinyOS
code image.

We have found one of the easiest way to run experiments and gather
data is to use dbg statements and save them to a file. Generally, the
more data printed out, the better (to a point); Perl scripts or other
tools can then read in the log of the run and provide information on
packet loss rates, routing state, etc. A useful function, defined in
{\tt external\_comm.c}, is {\tt printTime(char* buf, int len)}. It
takes the current time in simulation and converts it to the form
HH:MM:SS, putting it in {\tt buf}..

\subsection{Network Monitoring and Packet Injection}

To interact with a simulated network, you must use SerialForwarder,
the standard TinyOS interface tool. To work with \sim,
SerialForwarder's input source must be set appropriately. \sim
provides two modes: communication through a serial port to mote 0
and network snooping.

The serial port mode (``tossim-serial'' in the ``Mote Communications''
field or ``-comm tossim-serial'' at the command line) interacts with mote 0
over its serial port. Programs connecting to SerialForwarder can read
messages mote 0 sends to its serial port, and send messages to mote 0 over
its serial port.

The snooping mode (``tossim-radio'' in the ``Mote Communications'' field
or ``-comm tossim-radio'' at the command line) sits on top of the \sim
network model. Programs connecting to SerialForwarder hear every radio
message sent in the network, and can inject radio messages to arrive
(without error) at any mote. Because this mode outputs every message {\it
sent}, it does not consider loss; programs connecting will hear packets
that might not arrive successfully at any mote.

It's often helpful to use the {\tt -l} flag when using the serial port
mode; external applications can then interact with a network in
something approximating real time. Otherwise, in simulations of small
numbers of motes, things like network timeouts can go off before a PC
application has a chance to respond.

Message Interface Generator (MIG) is a tool that generates Java
classes for TinyOS packets. The MIG tool parses C structures for
TinyOS packets and builds a Java class with accessors for each of the
packet fields. The message classes can also unpack from and pack to
byte arrays.

Using MIG with \sim has one hitch; you must specify the {\tt
-target=pc} flag when compiling your message classes. MIG classes
generated for motes may not work with \sim; the two platforms do not
necessarily pack messages identically. Having different word
boundaries (one byte on motes, four bytes on PCs) means that
structures will have different padding. Problems will definitely
appear if message structures use platform-dependent types such as {\tt
int}. 

\section{Radio Models}
\label{sec:radio}

\sim simulates the TinyOS network at the bit level, using TinyOS
component implementations almost identical to the mica 40Kbit
RFM-based stack. \sim provides two radio models: simple and lossy. The
mica2 CC1000-based stack does not currently have a simulation
implementation.

In \sim, a network signal is either a one or zero. All signals are of
equal strength, and collision is modeled as a logical or; there is no
cancellation. This means that distance does not effect signal
strength; if mote B is very close to mote A, it cannot cut through the
signal from far-away mote C. This makes interference in \sim generally
worse than expected real world behavior.

The ``simple'' radio model places all nodes in a single cell. Every
bit transmitted is received without error. Although no bits are
corrupted due to error, two motes can transmit at the same time; every
mote in the cell will hear the overlap of the signals, which will
almost certainly be a corrupted packet. However, because of perfect
bit transmission in a single cell, the probability of two motes
transmitting at the same time is very, very low, due to the TinyOS
CSMA protocol.

The simple model is useful for testing single-hop algorithms and
TinyOS components for correctness. Deterministic packet reception
allows deterministic results.

\begin{figure}
\centering
\subfigure[Empirical] {\centering
\label{fig:loss_empirical}
          \includegraphics[clip,angle=-90,width=2in]{fig/empirical.pdf}}
\subfigure[Simulated] {\centering
\label{fig:loss_sim}
          \includegraphics[clip,angle=-90,width=2in]{fig/simulated.pdf}}

\caption{Empirical and Corresponding Simulated Packet Loss Data}
\label{fig:loss_fig}
\end{figure}


The ``lossy'' radio model places the nodes in a directed graph. Each
edge $(a,b)$ in the graph means $a$'s signal can be heard by
$b$. Every edge has a value in the range $(0,1)$, representing the
probability a bit sent by $a$ will be corrupted (flipped) when $b$
hears it. For example, a value of 0.01 means each bit transmitted has
a 1\% chance of being flipped, while 1.0 means every bit will be
flipped, and 0.0 means bits will be transmitted without error. Each
bit is considered independently.

The graph of the lossy model can be specified at \sim boot with a
file. \sim looks for the file ``lossy.nss'' by default, but an
alternate file can be specified with the {\tt -rf} flag. The file has
the following format:

\begin{verbatim}
<mote ID>:<mote ID>:bit error rate
<mote ID>:<mote ID>:bit error rate
<mote ID>:<mote ID>:bit error rate ...
\end{verbatim}

For example,

\begin{verbatim}
0:1:0.012333
1:0:0.009112
1:2:0.013196
\end{verbatim}

\noindent specifies that mote 1 hears mote 0 with a bit error rate of 1.2\%,
mote 0 hears mote 1 with a bit error rate of 0.9\%, and mote 2 hears
mote 1 with a bit error rate of 1.3\%. By making the graph directed,
\sim can model asymmetric links, which initial empirical studies have
suggest are a common occurance in TinyOS RFM-stack networks.

By specifying error at the bit level, \sim can capture many causes of
packet loss and noise in a TinyOS network, including missed start
symbols, data corruption, and acknowledgement errors.

\sim includes a Java tool, {\tt net.tinyos.sim.LossyBuilder} for generating
loss rates from physical topologies.  The tool models loss rates
observed empirically in an experiment performed by Woo et al. on a
TinyOS network~\cite{empirical}.  The empirical data is from a network
of twenty-six \motes, placed in a line, spaced at regular two foot
intervals, with the TinyOS radio set at a medium power setting (50 out
of 100). Each \mote transmitted two hundred packets, with each other
\mote keeping track of the number of packets
heard. Figure~\ref{fig:loss_empirical} shows a plot of this empirical
data.

To generate lossy models, the tool has Gaussian packet loss
probability distributions for each distance, fit to match the
empirical data. Given a physical \mote topology, the tool generates
packet loss rates for each \mote pair by sampling these
distributions. The tool translates packet error rates into independent
bit error rates.  Figure~\ref{fig:loss_sim} shows the results of the
experiment used to gather loss data when run in \sim.

The lossy model models interference and corruption, but it does not
model noise; if no mote transmits, every mote will hear a perfectly
clear channel.

\subsection{Using LossyBuilder}

LossyBuilder assumes each mote has a transmission radius of 50
feet. Combined with the bit error rate, this means each mote transmits
its signal in a disc of radius 50 feet, with the bit error rate
increasing with distance from the center.

LossyBuilder can read in or generate physical topologies ((x,y)
coordinates), and generate loss topologies from physical topologies by
sampling from the model of the empirical distribution in
Figure~\ref{fig:loss_empirical}. Its usage is:

\begin{verbatim}
usage: java net.tinyos.sim.LossyBuilder [options]
options:
  -t grid:       Topology (grid only and default)
  -d <m> <n>:    Grid size (m by n) (default: 10 x 10)
  -s <scale>:    Spacing factor (default: 5.0)
  -o <file>:     Output file
  -i <file>:     Input file of positions
  -p:            Generate positions, not error rates
\end{verbatim}