Wireless sensor networks consist of many small and cheap computational nodes that can sense the environment, communicate with neighboring nodes, and perform simple computations on sensor data. They may be deployed outdoors in large sensor fields to help detect and control the spread of wild fires, to detect and track enemy vehicles, or for environmental monitoring and precision agriculture. In many such application, each node requires location information to properly interpret its own sensor data and to act according to its placement in the world and in the network. Calamari is a system for providing each node in a sensor field with its own location information.

Calamari has been deployed on both small and large scales and is built on the Mica2 wireless sensor platform. It has successfully localized nodes in ad-hoc networks using both ultrasound ranging and radio signal strength (RSS). Using ultrasonic ranging, a 49 node network deployed over a 144 square meter (1600 square foot) area was localized with a median error of .53m (1.7 feet). Using RSS, the system localized 49 nodes spread over half of a football field with a median error of 4.1 meters.

Localization in sensor networks differs from localization in other domains in one key aspect: sensor networks have multihop topologies. This implies nodes must localize themselves based on information from neighboring nodes which also do not know their positions. For single-hop localization, where the localizing nodes can communicate directly with previously localized anchor nodes, there are many well known analytical solutions and deployed implementations (GPS,Cricket,RADAR,Active Bats, etc). Multi-hop sensor field localization, however, is still challenging because of the complex interaction between ranging error, the localization algorithm, and the actual network topology. One primary focus of Calamari is to explore these interactions and to predict them using thorough empirical characterizations and trace-based simulations. These simulation techniques have been shown to successfully predict the results discussed above.

This web page provides code, simulations, data, hardware schematics, papers, etc that were collected in the process of building Calamari:

1. Large data sets from different ranging technologies including radio connectivity, radio signal strength, acoustic time of flight, and ultrasound time of flight. 
2. A Matlab toolkit with many different localization algorithms, tools for generating random topologies, running simulations, generating analysis, and predicting the accuracy of a specific deployment. The simulations can use both simulated ranging data as well as actual collected data. 
3. Code implementing calibration/auto-calibration techniques to account for environmental properties as well as variations between individual hardware ranging devices
4. Localization algorithm implementations in NesC that run on both the Mica hardware platform and in TOSSIM, the mote simulator. 
5. Hardware schematics for an ultrasound ranging device designed specifically for the Mica2 
6. NesC software to drive the ultrasound board, filter noisy estimates and provide distances
7. NesC software for extracting distance estimates from RSS

The Silhouette Simulator

Silhouette is a Matlab-based simulator for sensor network localization. It uses statistical sampling techniques to employ traces of empirical ranging data in simulations of any size. The mathematical techniques used are described in this paper. Silhouette comes with empirical traces of both ultrasound and radio signal strength data, which are described in the section below as well as the paper.

A large number of localization algorithms have already been implemented in the Silhouette simulator, including Bounding Box, Iterative Multilateration, the Ad-hoc Position System's (APS) DV-hop and DV-distance algorithms, MDS-Map, MDS-Map(P), Robust Quads, GPS-free and brute force global grid search. The algorithms, along with the empirical traces, make the Silhouette simulator an ideal foundation for comparative analysis of new algorithms. A comparative analysis of the localization algorithms that have already been implemented is available in this paper. Please reference this paper if you publish results using the silhouette simulator.

To use the Silhouette simulator, use the following steps:

1. Download and unzip the Silhouette simulator tarball
2. Modify the first line of the silhouette.m script to point to the silhouette installation directory.
3. Open Matlab
4. "cd" into the Silhouette directory
5. Run the silhoeutte.m script, which will setup your Matlab environment
6. Run one of the sample scripts in the Silhouette directory to run anexperiment
7. Modify the sample script to run your own experiement

Older Matlab Simulations

You can find the older Matlab simulation code in the tinyos cvs in /tinyos-1.x/tools/matlab/contrib/kamin/localizationSimulation/.  The code has three main parts:

1. test cases: network topologies, anchor node specifications and noise parameters
2. algorithms: various ways of deriving location from distance estimates
3. evaluation: plot the network and each node's error vector along with important error statistics

To test the code out, add the enture localizationSimulation/ directory to your matlab path.  Then run the lines

The first line loads an array of test cases "t" from the localizationSimulation/testcases/isotropic.mat file.  The second command runs the "composition" algorithm from the localizationSimulation/algorithms/ directory on the first test case, and prints output.  You should see the following screen appear:

The graph at the top shows the distribution of errors normalized to the length of the maximum radio range in the network topology.  The bottom graph shows the actual network topology, where dots are nodes, gray lines indicate connectivity, and red X's indicate anchor nodes, nodes that know their own locations.  The blue arrow on each mobile node indicates the error vector, ie. it points to the position where the algorithm things the node is.

To use the code more generally, use the "generateTestSuite.m" command in the localizationSimulation/testcases/ directory and any of the algorithms in the algorithms/ directory to test each algorithm against different characteristic networks.

TinyOS Localization code

TinyOS code for calamari has been written using the Neighborhood abstraction and resides in the tinyos code repository in tinyos-1.x/contrib/calamari.  The README files in the subdirectories indicate what each test application will do.

(NOTE: the rest of these instructions are for running the code in simulation and are out-of-date. The simulation code will still work but is no longer supported.) To compile and run the code, run the following lines from the mentioned directory:

make pc
./build/pc/main.exe -gui 10

In another shell, type 

java net/tinyos/sim/TinyViz

The first line makes the application for the simulator and the second line starts the simulator in gui mode with 10 nodes in the network.  The third line starts the simulator gui, TinyViz.  Activate the "Calamari" plugin in the TinyViz window, set the range and noise on the ranging technique and hit the ply button until the simulation starts.  You should see a window that looks like this:

Each node displays a red ring around itself if it is an anchor node.  The mobile nodes display a blue arrow indicating the current error vector and the circle around the arrow's tip indicates the node's own estimate of it's own noise on the location estimate.

Note that in the current implementation, the Simulator visualization is controlling the algorithm.  To compile for a mica, simply switch the appropriate components such that

1. the anchor nodes are set by a radio message instead of by TinyViz
2. the distance estimates are coming from ranging code, as described below, instead of from TinyViz
3. the calibration coeffs are set by the user instead of by TinyViz

Code for Ultrasound and Radio Signal Strength Ranging

Early ranging work used the 4.3KHz sounder and the microphone on the standard Mica sensor board because of its relatively good omni-directional properties. The acoustic pulse was synchronized with a radio message and was received by the tone detector unit on the sensor board. Code for this implementation can still be found in the tinyOS code repository, although it only runs with the original Mica radio stack and is only there for reference; it is no longer supported. The main libraries can be found in tinyos-1.x/tos/lib/Ranging and a sample application can be found in tinyos-1.x/contrib/ucb/apps/TestTofRanging. People who want to use the Mica sensor board for localization should investigate the code provided by Vanderbilt in tinyos-1.x/contrib/vu/apps.

Code for Ultrasonic Calibration

The Joint Calibration method described in this paper is quite simple to implement and is completely contained in the file in the tinyos cvs in /tinyos-1.x/tools/matlab/contrib/kamin/chipconRssi/analysis called "estimateCalibCoefficients.m".  To understand the resulting calibration coefficients, look at or use the function "calibrateReading.m".

RF Signal Strength vs. Distance/Radio -- submitted 5-26-04 by Kamin Whitehouse
These environments were empirically characterized using the data collection process described in this paper. Indoors, in a large 22x12m room that was cluttered with chairs, pillars, and other items, as shown in Figure~\ref{intel}, we characterized the environment 6cm from the ground at five different transmission powers: -20, -15, -10, 0, and 10dBm. Similar experiments were performed in open grassy fields, but at 3 different elevations of 0, 6, and 30cm over a 30x30m area. Experiments were repeated with/without plastic enclosures, with the mica2 and the mica2dot, etc for a total of 40 environmental characterizations in total. This data is packaged together with the Silhouette simulator, which can use the data in simulation. Of course, the tab-delimited files containing the data can also be used without the simulator, but the simulator code probably must be read to figure out the meanings of the columns. The data files can found in the "datafiles" subdirectory of the simulator.

Ultrasound vs. Distance -- submitted 4-9-04 by Kamin Whitehouse
Similar to the data collected above, the ultrasonic ranging devices were characterized using the techniques described in this paper. Data was collected indoors on a carpet and with obstacles, in the grass, on pavement, and in free space for a total of 4 different environments. This data is packaged together with the Silhouette simulator, and can be found in the "datafiles" subdirectory.

RF Signal Strength vs. Distance/Radio -- submitted 5-22-03 by Kamin Whitehouse
This dataset answers the following questions:  If a packet is received, with what signal strength will it likely be received at a given distance and how much does that vary from radio to radio?  This is important for any algorithm that makes use of signal strength for predicting distance.  Note that this data is specific to the CC1000 433Mhz radio, which is used in the Mica2. 

Acoustic time of flight vs. Distance/Sounder/Mic -- submitted 5-22-03 by Kamin Whitehouse
This dataset answers the following questions:  If an acoustic chirp is received, with what time of flight reading will it likely be received at a given distance and how much does that vary from sounder/mic pair to sounder/mic pair?  This is important for any algorithm that makes use of acoustic time of flight for predicting distance.  Note that this data is specific to the sounder and microphone on the standard mica sensor board. 

RF Signal Strength vs. Distance/Strength -- submitted 10-15-01 by Rob Szewczyk
This dataset answers the following questions:  If a packet is received, with what signal strength will it be received at a given distance when it is sent with a given transmission strength?  This is important for any algorithm that makes use of signal strength for predicting distance.  Note that this data is specific to the TR1000 radio, which is used by TinyOS and SpotOn.  The potentiometer do not represent the entire spectrum of transmission strength, but represent a good sample.  Included graphs give strong support for the use of the median rather than the mean or mode of the RSSI.

RF Connectivity vs. Distance/Strength-- submitted 10-04-01 by Alec Woo
This dataset answers the following question:  What is the probability that a packet will be received at a given distance when it is sent with a given transmission strength?  This is important for any algorithm that makes assumptions about connectivity.  Note that this data is specific to the TR1000 radio, which is used by TinyOS and SpotOn.  The potentiometer settings are meant to represent the entire spectrum of transmission strengths that are meaningful over these distances.  Data was collected in an open parking lot in the evening when temperatures were near 60 F.

RF Signal Strength and Noise Characterizations over Distance -- submitted 10-03-01 by Kamin Whitehouse 
This dataset tries to answer the following question:  What is the probability of measuring a certain signal strength and getting a certain number of errors given the distance of the transmitter?  This data is very old and the actual measurements have been outdated, but it may still be useful for the first-order graphical analysis.  The data is grouped by distance, transceiver, receiver, and position of the experiment, where the positions were simply different corners of the lab.   Each grouping is then graphed.  The data is formatted as raw packets, where all bytes are constant (usually '0's) except for bytes 27 and 28, which represent the high and low end bits of the signal strength respectively, and bytes 9 and 29 which are junk.  The error rates are simply deviations from the intended, constant values of each byte.  It is not recommended to use these signal strength readings due to flaws in the sampling method. 

RF Characterization over Distance -- submitted 10-03-01 by Kamin Whitehouse 
This data tries to answer the following questions:  What aspects of an RF transmission can we use to infer the distance between transmitter and receiver?  The graphs illustrate the relation between distance and: Signal Strength, Error, Packet Loss, Standard deviation of signal strength.  The graphs are followed by the actual packets received, grouped by the mote that generated the data and by the location of the experiment.  However, it is not recommended to use this data beyond the first-order graphical analysis due to serious flaws in the experimental design and sampling method. 

The latest ultrasound hardware was designed for both the Mica2 and Mica2dot form factor and uses a reflective cone to provide omni-directionality in a plane (see images), an approach borrowed from the millibots project. The ultrasound transducer is connected to an Atmel Atmega8 1MHz microcontroller which is used for both transmitting and receiving. Both devices are mounted as a separate board on a mote, which consists of a ChipCon CC1000 FSK 433Mhz radio and an Atmel Atmega128 4MHz microcontroller. We calculate acoustic time of flight by transmitting a radio message from the Mica2Dot and an ultrasonic pulse from the ultrasound board simultaneously and measure the time difference on arrival at the receiver. A single interrupt line to carry hardware interrupts is used for precise time synchronization between the two processors.

Piezoelectric ultrasonic transducers have been used successfully in several location-based projects \cite{cricket00, activeBats, savvides01dynamic}. Generally speaking, higher frequencies achieve higher accuracy but shorter range. We selected the frequency in \calamari just above audible frequency at 25KHz for maximum range while minimizing human irritation. Piezoelectric transmitters and receivers are typically tuned slightly differently for optimal performance, but we specifically tuned those in Calamari so that a single transducer could function as both a transmitter and receiver. These two factors result in slightly less accuracy than solutions that use 40KHz transmitter/receiver pairs but enable higher range and require less hardware. Having a single transducer was also critical for using a cone to achieve omni-directionality in a plane. The UART or I2C bus are used to communicate the time of flight reading to the Mica.  Accurate measurements to within approximately 10cm of error have been measured at up to 10-12 meters (30 feet) when the acoustic transducers are pointed at each other. When the reflective cone is used, a maximum range of about 5m (15 feet) is observed.

The current Mica2dot form factor board is pictured below on the left with the reflective cone while the Mica2 form factor board is pictured on the right. While the boards are not being sold publicly, the schematics, layout and bill of materials are available.

Kamin Whitehouse, David Culler.  "Macro-calibration in Sensor/Actuator Networks."  Mobile Networks and Applications Journal (MONET), Special Issue on Wireless Sensor Networks.  June, 2003.  ACM Press.  

Kamin Whitehouse, Chris Karlof, David Culler. "A Practical Evaluation of Radio Signal Strength for Ranging-based Localization".  ACM Mobile Computing and Communications Review (MC2R), Special Issue on Localization Technologies and Algorithms. 2007.

Kamin Whitehouse, David Culler. "A Robustness Analysis of Multi-hop Ranging-based Localization Approximations".  The Fifth International Conference on Information Processing in Sensor Networks (IPSN '06).  Nashville, TN, April 19-21, 2006.

Kamin Whitehouse, Chris Karlof, Alec Woo, Fred Jiang, David Culler.  "The Effects of Ranging Noise on Multihop Localization: an Empirical Study"  The Fourth International Conference on Information Processing in Sensor Networks (IPSN '05).  Los Angeles, California. April 25-27, 2005. (ppt)

Kamin Whitehouse, Fred Jiang, Alec Woo, Chris Karlof, David Culler.  "Sensor Field Localization: a deployment and empirical analysis."  UC Berkeley Technical Report UCB//CSD-04-1349,   April 9, 2004.

Kamin Whitehouse, David Culler.  "Calibration as Parameter Estimation in Sensor Networks."  In Proceedings of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02).  Atlanta, Georgia, September 28, 2002.  ACM Press.   (ppt)

Kamin Whitehouse

Xiaofan Jiang