Beacon Vector Routing User's Guide


Rodrigo Fonseca, May 2005

The fine print

"Copyright (c) 2003-2005 The Regents of the University of California. All rights reserved.

Permission to use, copy, modify, and distribute this software and its documentation for any purpose, without fee, and without written agreement is hereby granted, provided that the above copyright notice, the following two paragraphs and the author appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."

Copyright (c) 2003-2005 Intel Corporation All rights reserved.

This file is distributed under the terms in the attached INTEL-LICENSE file. If you do not find these files, copies can be found by writing to Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, 94704. Attention: Intel License Inquiry.

Author: Rodrigo Fonseca Date Last Modified: 2005/06/07

If you got here you probably already know what BVR is, but I'll say anyway. Beacon Vector Routing is an any-to-any routing scheme, suited for wireless sensor networks. It borrows from the scalability of geographic routing by using a greedy mode of forwarding based on coordinates. These coordinates however are not geographic in nature, but are rather derived only from the topology of the network. In a nutshell, a node's coordinates are the set of hop distances to a number of reference nodes which we call beacons. To learn more, I suggest you read our NSDI paper. [put link here]

People

BVR was developed at Intel Research, Berkeley, the University of California, Berkeley, and the International Computer Science Institute, in ... , right, Berkeley. The authors are We would also like to thank Cheng Tien Ee for invaluable help in testing the code in the Soda Hall testbed.

Intro

This version of BVR is tested to run on TinyOS v1.1. The PC simulations used the TOSSIM-packet simulator, found in the /beta subtree of the tinyos tree. BVR as released provides a "route to coordinates" interface to applications. It only supports application messages on one AM channel, AM_BVR_APP_MSG, but that should be easy to change in case there is a need for it. We are writing a location database that will support a route to id interface.

Using BVR

The "point of entry" for applications into the BVR code is BVRRouterC, which provides the interfaces BVRSend, and BVRReceive (not yet BVRIntercept), to send and receive unicast messages. These interfaces follow the model in MultihopRoute, i.e., the sender has a buffer, and requests a pointer into the payload area into that buffer.

TestBVRSimple is a (simple) application that wires to BVRRouterC and sends messages back and forth between nodes. It is driven externally through the BVRCommand interface.

The structure of the BVR code

The code is divided in support modules, and BVR itself. The main BVR modules are: These modules use two core support modules, LinkEstimator and BVRCommStack. There are also important peripheral modules that are used in interacting with nodes: the Logger and Command modules.

2.1 BVRCommStack

Starting from the bottom, BVRCommStack is literally a stack of modules that implement parametrized SendMsg and ReceiveMsg, just like GenericCommM. The diagram below shows how BVRCommStack is decomposed, and which modules use it to send and receive packets. It does two main things. First, it takes care of the parts of the LinkEstimator that have to be in the data path (see the description of the link estimator). Second, it integrates the send queue for packets, which includes retransmissions as well. GenericCommReallyPromiscuous just turns on the promiscuous mode of AMPromiscuous upon initialization. On the PC side we divert all UART packets to the debug output with UARTInterceptComm, which is not wired when compiling to the motes. 
  
  Application
  (route to coords)    
         \                  
           BVRRouterC   BVRStateC   UARTLoggerM   BVRCommand

               \           \          /              /

               --------------------------------------
                         | BVRCommStack | 
                          -------------- 
                                |       
                         FilterLocalComm
                                |
                         LinkEstimatorComm
                                |
                         BVRQueuedSendComm 
                                |
                     LinkEstimatorTaggerComm
                                |
                       [ UARTInterceptComm ] (PC only)
                                |
                     GenericCommReallyPromiscuous
                                |                 BVR specific
               ---------------------------------------
                      GenericCommPromiscuous       TinyOS standard 
                      AMPromiscuous
The LinkEstimatorTaggerComm tags all packets with a per source unique (16 bits) sequence number. This info goes in the LEHeader structure. All messages sent through BVRCommStack should follow the BVRRawMessage format, which is to say they should have space for LEHeader as the first 4 bytes of the AM payload. LinkEstimatorComm collects statistics on the receive side, for the different neighbors. It integrates directly with the LinkEstimator module, and drives all changes to that module. LinkEstimatorComm also sends its own periodic packets for reverse link quality estimation. These two components are split because of the queue component: the reverse link estimation packets are also enqueued and retransmitted, while all packets that leave the radio (including multiple retransmissions of the same higher layer packets) receive a unique id.

Lastly in the CommStack is FilterLocalComm, which reverts the effect of the promiscuous mode of the lower parts of the stack. It is here so that components that use the stack and assume that they will only receive packets destined for the node.

2.2 Link Estimator

BVR uses a passive link estimator that works counting packets received and packets sent by each neighbor. As mentioned above, all packets that are sent over the radio by a node receive a unique increasing sequence number. A node B in range of a node A sending can then determine if it has missed any packets from A by looking at the last received sequence number. This link estimator is loosely based on the work by Alec Woo. Periodically the LinkEstimator updates the statistics, and keeps an exponentially weighted moving average of the quality estimates. The updates are not performed at every packet received, but rather in discreet windows of time. Basically at each window the estimate is #packets received / (total sent packets). Total sent packets is the maximum between #sent + #received and an expected minimum number of packets sent (LINK_ESTIMATOR_MIN_PACKETS). This number depends on what is known about the traffic pattern of whatever is going on on the motes, and should be set accordingly. In the case of BVR, we know that nodes will send packets at every I_BEACON_INTERVAL interval.

Look at the code for more comments. LinkEstimatorComm updates packet counters upon receiving packets, and the link quality is changed when the LinkUpdateTimer fires. Every time the timer fires a new estimate of the quality is computed. This takes into account the number of packets received and missed in the last LINK_ESTIMATOR_RECEIVE_WINDOW update periods. At this time the window is advanced also, and new packets are counted in a fresh window.

Eviction is handled separately from quality: after AGE_THRESHOLD periods without hearing any packets from a node, we evict it from the cache. The quality also drops, so it might be replaced before that.

When a new node is added to the cache, it enters a probation period during which it cannot be replaced. This is set by LINK_ESTIMATOR_PROBATION, and was set as the number of link estimation periods one would need to get to within 10% of the true value (assuming 0 as an initial value, and successive inputs of value 1). It thus shold vary with different values of alpha, the weight of the history in the moving average.

Replacement is done if we hear about a new neighbor. What we currently do is that every node that has quality below LINK_ESTIMATOR_REPLACE_THRESH and has past the probation period (meaning it has a sensible estimate of the quality), is up for being replaced, and we pick the one with the lowest quality. The result of this is that there are nodes with quality above the threshold, they will remain in the cache.

To do: change the link estimator replacement strategy such that we keep the k best neighbors, and have n-k slots for probation.

2.3 CoordinateTable

The CoordinateTable maintains the coordinates of (a subset of) the neighbors that are in the LinkEstimator table. Insertions occur when we receive a BVRBeaconMsg from a neighbor AND that neighbor is in the LinkEstimator table. Evictions occur when a neighbor is evicted from the LinkEstimator table. These two are kept in sync by means of the LinkEstimatorSynch interface, wired through BVRStateC. It is only accessed from BVRStateC.

The CoordinateTable module also provides the very important command getNextHops, which returns a list of neighbors that are good next hops for a given packet and destination, ordered by progress weighted by bidirectional quality to the neighbor.

To do: the CoordinateTable interface passes pointers to the entries in the table. Change this to have methods that modify these entries based on the address as the key, similar to what the link estimator does.

2.4 BVRStateC

This is the main module responsible for keeping the BVR state information, as well as the control traffic. This means that it know who the beacons are, and handles the local neighbor message exchanges that allow nodes to

All is done by sending and receiving BVRBeaconMsg's, which contain primarily a node's own coordinates (distances to each beacon). They also contain information to allow a node to use such information relative to each beacon in computing its own coordinates: a sequence number for each beacon, and the cumulative quality of the reverse path to each beacon.

This is how we ensure that we have reasonable trees: each node has a parent, and we make sure that when we say we are X hops from the beacon this is along a good quality path. Otherwise we might be considering very poor quality and long links to be 'hops'. It is still an open question what is the best way to count hops when we have 'links' which are not physical wires but this shared, changing wireless medium. We found though that the trees produced by this method are pretty good.

The basic idea then is that if you receive a message from a neighbor saying they are 3 hops from beacon 5, you consider yourself to be 4 hops from beacon 5. Each beacon starts this process by stating distance 0 from themselves, and update a sequence number for each such broadcast they do. A node will update its distance only once per sequence number, this avoids count-to-infinity problems, and loops. A node maintains a parent in each beacon tree, and will occasionally change parents if another parent offers a better quality path to the root. The quality of a path is measured in ETX - expected number of transmissions to get to the root, taking into account the quality of each link along that path and assuming you would do hop-by-hop retransmissions.

There are also details involving when to choose a new parent, in order to avoid instability and flapping, while still reacting to significant changes in connectivity. I encourage you to look into the code as the authoritative source on how that is done, and ask any questions you may have to me.

2.5 BVRRouterC

2.6 Logger Interface and UARTLogger

2.7 BVRCommand

2.8 Code Size

As of version 0.5, the code size is distributed as follows (not including comments, blank lines, and preprocessor directives) bvr commstack linkestimator command util (includes UARTlogger) total

3. Parameters

There are several parameters that tune the operations of BVR, the amount of memory required, the bandwidth of the control traffic, and the speed of convergence of link estimation and coordinate propagation. Before nodes can route properly, two pieces of information need to be acquired: the estimation of the bidirectional link qualities between a node and its neighbors, and the coordinate system. The latter involes each node knowing the distance between itself and each of the beacons, and also knowing the coordinates of its neighbors.

3.1 Memory

There are different parameters in BVR that affect how much memory the code will require. These are mainly the size of the packets and the sizes of the different tables and buffers. In TinyOS all memory is allocated statically, and while there is a file called BufferPool in BVR, the memory is not shared among different modules.
MAX_ROOT_BEACONSMin. TOSH_DATA_LENGTH
5 31
[queue buffers] [UARTLogger buffer pool] [size of neighbor table] [size of coordinate table]

3.2 Time and Bandwidth

[periodic beacon] [periodic reverse link estimation message] [link estimator periodic update]

4. Running BVR

4.1 Mica2 Testbed

Here we assume access to a testbed with an ethernet backchannel to the motes. This assumption has two implications: first, from a central PC it is possible to issue commands through the backchannel to all motes. Second, the motes can log all the events to the UART, and these packets are received by a central machine through the backchannel. Alternative configurations are possible, such as sending commands over the air from a base station, and logging to the EEPROM, but we don't discuss this, and haven't implemented such EEPROM logging modules.

For running the experiments, we use a couple of Java tools to interact with the motes. We collect a log of the packets sent to the UART by the motes using the class net.tinyos.testbed.TestBedPacketLogger, and send commands to the motes using either a standalone tool, net.tinyos.bvr.BVRCommandInject, or a scripted driver, net.tinyos.bvr.ThroughputTestDriver. So that these tools can simultaneously talk to the motes, we connect all motes to SerialForwarders, and have the tools talk to the SerialForwarders. The tools assume that a mote of id X will be connected to a SerialForwarder that listens on port B+X. We generally use B=9100, such that mote id 85 will be connected to a SerialForwarder at port 9185. The SerialForwarder multiplexes connections to the motes, making it really convenient and flexible to run experiments.

Steps:

  1. program the motes
    tools/run/program_all_motes.pl
  2. start the serial forwarders
    tools/run/testbed_start_sf.pl will start the serial forwarders.
  3. verify that the motes are alive and programmed and talking
    tools/run/get_id_all_motes.pl * See troubleshooting below. Possibly go back to a.
  4. start the packet logger
    java net.tinyos.testbed.TestBedPacketLogger
  5. start the traffic driver
    java net.tinyos.bvr.ThroughputTestDriver
  6. process the logs... The logs are written as
    <time(ms)> <id(decimal)> <hex dump of packet>

For the last step I wrote some perl scripts that parse the logs, but you may want to write a java class that reads the textual format of the logs and converts them to the java message classes created by mig, which would make it easy to get access to all fields from within your program. Shouldn't be hard to do. Other people have taken different approaches for d, e, and f above. For example, you can connect your motes to a database, and then process everything with some java program that understands the messages, or with MatLab.

If you don't have access to a testbed with ethernet or usb connected motes, you can implement a module that implements the Logger interface, but writes the info to the EEPROM, and then can have each mote dump its information from the EEPROM. The difficulty here would be to correlate the logs in time, since each one would be in its own timescale. Maybe if the motes are timesync'd, or you can alternatively extract causal relationships between events from one mote to the other. We don't have code to do this in BVR, though.

*Troubleshooting (some) There are several reasons motes fail to program, or respond. I generally have 15% of them not working for one reason or another. Check that the cables are connected. Try powercycling the mote and the ethernet adapter. Telnet into the EPRB and verify its settings. Reset everything. Try again. If you don't get some mote working, go back and adjust your testbed config file, and repeat, until you get a set of working motes...

4.2 TOSSIM

We developed a couple of tools to allow different network topologies to be generated and tested using TOSSIM, including topologies with lossy characteristics. The simulation described here is done using the packet level radio simulator in TOSSIM. We also do not use the sockets interface to interact with TOSSIM, because of serious speed concerns. Instead, we use a hook to the event loop in TOSSIM that allows us to insert and process specific events in TOSSIM's event queue.

4.1 Generating topologies

Requirements: perl, java net.tinyos.LossyBuilder, optionally graphviz

4.2 internal_interrupt.c

Requirements: patched tossim code