CODA [1][2] is one of the first congestion control protocols designed
specifically for multihop sensor networks. It includes a closed loop
component for long term rate control, and a suppression signal-based
open loop component to mitigate transient congestion hotspots. The
open loop component uses randomized suppression to provide a notion of
soft fairness by default, or can be used to support prioritized flows
(please refer to the paper [1][2] for details about CODA).
This is a development version for demonstration purposes only, for
researchers that are interested in studying congestion control
problems in sensor networks; the code is not "production grade" at
present, but is available as a beta stage release. Code readability
is our first priority as opposed to trying to optimize the code in
terms of program size or memory footprint. Hence, there is likely
space for code optimization and users are welcome to contribute their
modifications. Notice that we have included many detailed comments
within the code to help users understand the code and map the
implementation to the CODA design described in [1][2].
Patches/bug fixes from users of CODA are always more than welcome. It is
the authors' intention to develop a general purpose congestion control layer
for sensor networks in the spirit of open source.
This beta release of CODA includes both the CODA functionality
encapsulated in a library component, and a demo application (an
adaptation of the popular TinyOS "Surge" application) that uses the
CODA library. Both are implemented in nesC code for mica2 motes.
Finally, we have modified the default TinyOS Queue library for provide
a hook for occupancy monitoring, and modified the default B-MAC
implementation to provide a hook for channel state monitoring. All
the code is included in a single tarball "coda-beta.tgz".
[Installation]
The code has been tested on TinyOS 1.1.15 (the latest TinyOS 1.x snapshot release).
Download the latest coda tarball from the Armstrong software
directory.
The tarball can be untarred anywhere in your file system; a make file
will be modified (described below) to link in to your existing TinyOS
installation. After untarring you should see a directory named
"coda-beta". Do as follows:
1) cd into "coda-beta/apps" and open the file MakeCODA. Set the
variable CODA_DIR to point to "coda-beta". Make sure your
environment variable TOSROOT is pointing to your TinyOS installation.
2) Replace the default MAC module with the one included in the CODA
distribution by doing the following. cd into "$TODIR/platform/mica2"
and move the existing MAC module: "mv CC1000RadioIntM.nc
CC1000RadioIntM.nc.bk". Then create a link to the MAC modified to
provide channel statistics to CODA: "ln -s
<coda-beta>/tos/platform/mica2/CC1000RadioIntM.nc".
3) SurgeCODA is a demo application for the CODA link layer based on
the Surge application included in the default TinyOS distribution.
Based on the wiring configuration of Surge, users should be able to
get an idea of how to wire CODA into their own applications.
Additionally, the SurgeCODAM.nc component demonstrates use of the
RateUpdate interface to allow the packet source to opt in to closed
loop regulation (see [1][2]) and to set the desired maximum packet
send rate. Set the value INITIAL_TIMER_INTERVAL in
"coda-beta/apps/SurgeCODA/Surge.h" (default value is 0, which
disables sending).
Surge uses the MultiHopRouter component to funnel Photo sensor
readings to the sink based on periodic sampling. The routing
implementation may take several minutes in a large network to
establish routes to the sink. The constants DATA_TO_ROUTE_RATIO and
DATA_FREQ defined in "$TOSROOT/tos/lib/Route/MultiHopLEPSM.nc" can
help you balance this route settling time against acceptable control
messaging overhead.
SurgeCODA modifies
the default Surge by including the CODA link layer shim between
transmit FIFO Queue component and the MAC layer, and by stripping out
extraneous Surge command and demo interfaces. App-layer jitter is also
added as good practice. To compile SurgeCODA, cd into
"coda-beta/apps/SurgeCODA" and type "make mica2".
4) Assuming there are no compilation issues, install a sink by typing
"make mica2 install.0 eprb,xxxx", where "xxxx" is the IP address of
the MIB600 to which the node is attached. See
http://www.tinyos.net/tinyos-1.x/doc/tutorial/programmers.html for the
standard TinyOS installation instructions for other programming setups.
5) Program as many other nodes as desired, using non-zero IDs
(MultiHopRouter assumes only the sink has ID=0). CODA acts on demand,
when congestion arises, but incurs no penalty in a sparse environment
when there is little or no possibility of contention.
6) You may optionally use the Surge GUI to monitor your network by
first connecting a serial gateway to the sink node (via its MIB600).
To do this, cd into "$TOSROOT/tools/java" and type "java
net.tinyos.sf.SerialForwarder -port yyyy -comm network@xxxx:10002",
where "yyyy" is an available TCP port on localhost and "xxxx" is the
IP address of the MIB600 connected to the sink. Next, run the Surge
GUI from the "$TOSROOT/tools/java" directory by typing "java
net/tinyos/surge/MainClass 0x7d". These directions assume your
TinyOS java tree has been compiled and is correctly configured.
Instructions to do so are outside the scope of this document, but can
be found on the main TinyOS website (www.tinyos.net).
[Running/Testing CODA]
CODA runs when the application starts, implementing open loop control
at all times and closed loop control as desired by the application.
(Experts:) During the course of verifying this beta release code for
CODA, some debug/measurement code was added, and can be included into
the build by adding "CFLAGS+=-DDEBUG_CODA" in
"coda-beta/apps/SurgeCODA/Makefile". This debug code is not
part of the CODA beta release and is not supported as such, but can be
useful if you are interested in doing quantitative performance
analysis. Browse the source code and look for the code tagged with
"#ifdef DEBUG_CODA" to see the available features (tx and rx packet
counters, message handlers for stats dump, remote reset, etc.). Note
that defining DEBUG_CODA brings additional flags controlling the
packet transmissions into play and sources are disabled by default. External
messages must be sent to enable them. The beta release testing of CODA was
done on a testbed of thirty MIB600-mounted mica2 nodes (control
messages are sent using external tools over the Ethernet to the mica2
serial port). Tweaking the DEBUG_CODA code to work with your
environment may require additional work, but at least the existing
DEBUG_CODA code can act as a guide in this effort.
[CODA 0.10 Implementation Notes]
1. Reverse routing must currently be implemented inside CODA since
MultiHopRouter only implements convergecast routing to a single sink.
However, if an anycast routing layer is substituted for
MultiHopRouter, then this part of the CODA code can be eliminated to
save space.
2. Currently, during times when a node is suppressed, no packets above
the CODA layer are forwarded. This may lead to reduced delivery for
multihop control packets packets if they are sent through the CODA
send interface exported to the upper layers. Care should be taken in
configuring the application wiring.
3. In order not to disturb the LL frame, we use a bit in the 'group'
field as the request for Acks from the sink. This limits the number of
groups to 128.
4. We assume each node is reporting a different data type; CODA
executes closed loop control (if enabled) on each of the source nodes
individually. The number of sources tracked at the sink is indicated
by MAX_SOURCE_TYPES defined in coda.h.
5. We assume the 1-hop parent's ID is present in the MAC payload,
i.e., in the routing header. If this is not the case, i.e., if a
routing protocol other than MultiHopRouter/Mint is used that does not
provide this information, then an additional mechanism must be
implemented to provide this information.
6. The closed loop implementation handles only applications with
periodic loads. Handling non-periodic workloads requires more
sophisticated history-tracking and predictive models at the sink. This
is certainly possible to do, but is outside the scope of this beta demo
implementation.
7. Certain state kept by each node concerning neighbors and traffic
streams is non-adaptive in the sense that there is no
soft-state/eviction logic implemented. Adding this feature is
straightforward, but is not required to demonstrate the main CODA
mechanisms. Therefore, for simplicity we assume the static case where
adaptation to new neighbor sets (i.e., pruning old sets/state) is not
necessary.
Authors: Shane B. Eisenman, Chieh-Yih Wan <{shane,wan}@ee.columbia.edu>
-- updated June 15, 2007
End Motigo Webstats code -->
[Links to Users]
Please email us if you are using CODA in your course or project. We would
like to hear about your experiences and how you are using CODA.
[References]
[1] Chieh-Yih Wan, Shane B. Eisenman and Andrew T.
Campbell, “CODA: Congestion Detection and Avoidance in
Sensor Networks”, in Proc. of First ACM Conference on
Embedded Networked Sensor Systems (SenSys 2003), pp. 266-279, Los
Angeles, Nov 5-7 2003.
[manuscript]
[2] Chieh-Yih Wan, Shane B. Eisenman and Andrew T. Campbell,
"Congestion Detection and Avoidance in Sensor Networks",
IEEE/ACM Transactions on Networking (in revision)
[manuscript].
