stack.tex

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

\documentclass[11pt]{article}

\usepackage{graphicx}
\usepackage{graphics}
\usepackage{multicol}
\usepackage{epsfig,amsmath,amsfonts}

\makeatletter                                   % Make '@' accessible.

\oddsidemargin=0in                              % Left margin minus 1 inch.
\evensidemargin=0in                             % Same for even-numbered pages.
\marginparsep=0pt                               % Space between margin & text

\renewcommand{\baselinestretch}{1}              % Double spacing

\textwidth=6.5in                                % Text width (8.5in - margins).
\textheight=9in                                 % Body height (incl. footnotes)

\topmargin=0in                                  % Top margin minus 1 inch.
\headsep=0.0in                                  % Distance from header to body.
\skip\footins=4ex                               % Space above first footnote.
\hbadness=10000                                 % No "underfull hbox" messages.
\makeatother                                    % Make '@' special again.


\begin{document}

\fontfamily{cmss}                               % Make text sans serif.
\fontseries{m}                                  % Medium spacing.
\fontshape{n}                                   % Normal: not bold, etc.
\fontsize{10}{10}                               % 10pt font, 10pt line spacing 
\selectfont

\title{Mica High Speed Radio Stack}
\author{Nelson Lee, Philip Levis, Jason Hill}
\maketitle

\fontfamily{cmr}                                % Make text Roman (serif).
\fontseries{m}                                  % Medium spacing.
\fontshape{n}                                   % Normal: not bold, etc.
\fontsize{12}{12}                               % 12pt font, 12pt line spacing
\selectfont

\section*{Introduction}
This document describes the TinyOS networking stack released in TinyOS
1.0. This stack provides variable length packets and data-link level
synchronous acknowledgements at a 40Kb data rate; it only works on
mica motes. This document assumes the reader is familiar with nesC.

\section*{The Old Network Stack}

The pre-mica TinyOS networking components used a vertical protocol
stack. It roughly had this structure:

\small
\begin{verbatim}

       Application
            |
            V
       GENERIC_COMM
            |
            V
       AM_STANDARD
            |
            V
    CRCPACKETOBJ_SIGNAL
            |
            V
 SEC_DED_RADIO_BYTE_SIGNAL
            |
            V
           RFM

\end{verbatim}
\normalsize

This vertical layering made each component dependent on the
components directly above and below it, and allowed different
components (e.g. a non CRC packet) to be easily interchanged. However,
experience has shown that most of the interesting and important
functionality had to be encapsulated in {\tt SEC\_DED\_RADIO\_BYTE\_SIGNAL},
as only it could use the bit-level interface to the radio ({\tt RFM}).

For example, {\tt SEC\_DED\_RADIO\_BYTE\_SIGNAL} was responsible for the MAC
layer, packet start symbol detection, and data encoding/decoding:
three very separate pieces of functionality.

\section*{Introducing the New Radio Stack in nesC}

In nesC, configuration files link components together according to the
interfaces they use and provide.  The hierarchy that links
applications to the radio stack is as follows:

\small
\begin{verbatim}
        Application
            |
            V
        GenericComm (configuration ``/tos/system/'')
            |
            V
        AMStandard (module ``/tos/system'')
            |
            V
        RadioCRCPacket (configuration ``/tos/platform/mica'')
            |
            V
        MicaHighSpeedRadioM (module ``/tos/platform/mica'')
            |
     _______|___________________________________________
     |           |         |          |        |        |
     |           |         |          |        |        |
     V           |         V          |        V        |  
ChannelMonC.td   |  RadioTimingC.td   |   SlavePinC.td  |
                 V                    V                 V
          SpiByteFifoC.td        SecDedEncoding.td  RandomLFSR.td

\end{verbatim}
\normalsize

All componenents below {\tt RadioCRCPacket}, except for {\tt RandomLFSR}, are  
implemented in \\{\tt /tos/platform/mica}.


\section*{A Brief Overview}

Several components combine to form the network stack.

\begin{itemize}

\item {\tt MicaHighSpeedM} contains the logic and state at the
packet-level, and acts as a central controller for all of the
components below it. It does not communicate directly to hardware,
instead, it calls on other components to do so.

\item {\tt ChannelMonC} observes the radio at bit-level at 20kbps.  When the
stack is idle, it samples waiting for the preamble and start symbol.
When the stack is sending a packet and is in backoff, {\tt ChannelMon}
monitors the radio and signals idleDetect to {\tt MicaHighSpeeedM}.

\item {\tt SpiByteFifo} provides a byte-level abstraction to the radio.  In
essence, it uses the Serial Peripheral Interface (SPI) of the
ATmega103 processor to shift out bits to the radio when sending, and
shift in bits from the radio when receiving at 40kbps.  

\item {\tt SlavePinC} calls {\tt HPL} functions to flip the {\tt SlavePin} high and low.

\item {\tt RadioTiming} uses counters on the ATmega103 and input capture to sync a
receiver of a packet to the sender.

\item {\tt SecDedEncoding} provides a byte-level implementation of
encoding/decoding single error correction and double error detection.

\item {\tt RandomLFSR} returns a 16 bit random number. This is used by
{\tt ChannelMon} to determine the length of the backoff state in radio clock ticks.
\end{itemize}

\section*{Init/Idle}
The network stack is initialized by calling init() in
{\tt MicaHighSpeedRadioM}.  In turn, {\tt RandomLFSR} is initialized
and {\tt ChannelMonC}
is initialized.  {\tt RandomLFSR} initializes the seed from the ID of the mote
for the random number generator.  {\tt ChannelMonC} sets its {\tt CM\_waiting}
field to -1, sets the radio hardware to receiving, scales timer2 and
compare register2, clears the current counter value and enables
timer2's interrupt to go off every 200 clock ticks (200 clock
ticks/bit = 4MHz/20kbps).

Every time timer2's interrupt fires, {\tt TOSH\_SIGNAL(SIG\_OUTPUT\_COMPARE2)}
is called in {\tt ChannelMonC}. While the entire network stack is idle
({\tt MicaHighSpeedRadioM} has not accepted any packets and its {\tt
state} and {\tt send\_state}
are both {\tt IDLE\_STATE}), it shifts in the bit received into a buffer and
checks for the preamble. Preamble/start symbol detection will be
discussed in further detail below.

\section*{The new TOSMsg format}
The new structure of the {\tt TOS\_Msg} (the struct declaration can be found
in {\tt ``/tos/system/AM.h''}:

\begin{verbatim}
typedef struct TOS_Msg
{
  uint16_t addr;
  uint8_t type;
  uint8_t group;
  uint8_t length;
  int8_t data[TOSH_DATA_LENGTH];
  uint16_t crc;
  uint16_t strength;
  uint8_t ack;
  uint16_t time;
} TOS_Msg;
\end{verbatim}

It consists of an unsigned two byte field {\tt addr}, followed by
three unsigned single byte fields {\tt type}, {\tt group}, and {\tt
length} {\tt addr} specifies a moteID or the broadcast address ({\tt
0xffff}).  When the {\tt MicaHighSpeedRadioStackM} receives a packet,
the packet is passed to the AM level. If {\tt addr} is not the broadcast
address nor the address of the mote receiving the packet, the packet
is dropped.  The {\tt group} field specifies a channel for motes on a
network. If a mote receives a packet sent by a mote with a different
{\tt group} field, the packet is dropped at the AM level. The default
{\tt group}
is 0x7d. The {\tt type} field specifies which handler to be called at
the AM level when a packet is received. The {\tt length} field
specifies the length of the data portion of the {\tt TOS\_Msg}. Packets have
a maximum payload of 29 bytes.

The next field in the {\tt TOS\_Msg} struct is the {\tt data} portion. It
consists of an array of 29 bytes (as specified by
{\tt TOSH\_DATA\_LENGTH}). The unsigned two byte field {\tt crc}
follows. When sending, the CRC is incrementally calculated as each
byte of the packet is transmitted. The maximum length of a transmitted
{\tt TOS\_Msg} is 36 bytes ({\tt addr}(2 bytes) + {\tt type}(1 bytes)
+ {\tt group}(1 bytes) +
{\tt length}(1 bytes) + {\tt data}(29 bytes) + {\tt crc}(2 bytes = 36 bytes)). The {\tt
strength}, {\tt ack}, {\tt and time} fields are not transmitted; they
are meta-data about the packet.

The last three fields of {\tt TOS\_Msg} are the single unsigned byte {\tt
ack} field, the unsigned two byte {\tt strength} and unsigned two byte {\tt time}
fields.  The {\tt ack} is sent by the receiver, and set by the
sender. This is the mechanism that can provide reliability in the
stack. When the network stack finishes sending a packet, it will
return the {\tt TOS\_MsgPtr} to the application that issued the send
request, with the {\tt ack} field set to either 1 or 0.  If the field
is 1, the data link layer received an acknowledgement for the
packet. When a packet is received, the data link layer transmits an
{\tt ack} if the receiving mote is a valid destination for the packet:
({\tt rec\_ptr$->$addr == TOS\_LOCAL\_ADDRESS $\parallel$ rec\_ptr$->$addr ==
TOS\_BCAST\_ADDR}).  The {\tt strength} field of {\tt TOS\_Msg} is currently
unused, and the {\tt time} field stores an atomic capture of a 16-bit 4MHz
counter. 

\section*{Sending a Packet}
MicaHighSpeedRadioM contains two state variables, {\tt send\_state} and
{\tt state}.  When AMStandard hands down a {\tt TOS\_MsgPtr} to send,
MicaHighSpeedRadio's state must be {\tt IDLE\_STATE}.  If it is {\tt IDLE\_STATE}, then the
radio stack accepts the packet.  Its state changes and does not return 
until a packet is completely sent, which includes the reception of an
ack.

{\tt MicaHighSpeedRadioM} then calls {\tt macDelay}() in {\tt
ChannelMonC}.  {\tt macDelay} sets its {\tt CM\_waiting} field to a
random number.  {\tt CM\_waiting} specifies the number of {\tt
ChannelMonC} clock ticks (one {\tt ChannelMonC} clock tick is equal to
200 ATmega clock ticks at 4MHz) to wait for idle over the network.
This Backoff state, as described previously, ensures that a sender of
a packet in the network will not interfere with the transmission of
another sender's packet in the network. The random factor prevents
starvation.

Now, since {\tt ChannelMonC} is waiting for idleness in the network, each
call to \\
{\tt TOSH\_SIGNAL(SIG\_OUTPUT\_COMPARE2)} in {\tt ChannelMonC} decrements
{\tt CM\_waiting}.  When {\tt CM\_waiting} is equal to 1, it checks to see if 
during the past 12 {\tt ChannelMonC} clock ticks a single 1 bit was not
received (checking if {\tt CM\_search[0]} \& 0xfff == 0).  If so, it sets
{\tt CM\_waiting} to -1, disables timer2's interrupt (thereby disabling
{\tt ChannelMonC}) and signals {\tt MicaHigSpeedRadioM} that idleness was