WHAT
Ensuring that every sensor node has the same code version is challenging in dynamic, unreliable multi-hop sensor networks. When nodes have different code versions, the network may not behave as intended, wasting time and energy. We propose and evaluate DHV, an efficient code consistency maintenance protocol to ensure that every node in a network will eventually have the same code. DHV is based on the simple observation that if two code versions are different, their corresponding version numbers often differ in only a few least significant bits of their binary representation. DHV allows nodes to carefully select and transmit only necessary bit level information to detect a newer code version in the network. DHV can detect and identify version differences in O(1) messages and latency compared to the logarithmic scale of current protocols. Simulations and experiments on a real MicaZ testbed show that DHV reduces the number of messages by 50%, converges in half the time, and reduces the number of bits transmitted by 40-60% compared to DIP, the state-of-the-art protocol.
DOWNLOAD
DHV is now part of the core networking library in TinyOS-2.x and can be downloaded from the TinyOS-2.x repository.
TinyOS-2.x
FUNDED BY
This material is based upon work supported by NSF CISE grants 0514818 and 0722063. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).
WHO
Thanh Dang, Nirupama Bulusu, Wu-chi Feng, and Seungweon Park
HOW
Figure 1: DHV Main Components
Figure 2: DHV Flow Diagram
DHV has two main phases — detection and identification. In detection, each node broadcasts a hash of all its versions called a SUMMARY message. Upon receiving a hash from a neighbor, a node compares it to its own hash. If they differ, there is at least one code item with a different version number.
In identification, the horizontal search and vertical search steps identify which versions differ. In horizontal search, a node broadcasts a checksum of all versions, called a HSUM message. Upon receiving a checksum from a neighbor, the node compares it to its own checksum to identify which bit indices differ and proceeds to the next step. In vertical search, the node broadcasts a bit slice, starting at the least significant bit of all versions, called a VBIT message. If the bit indices are similar, but the hashes differ, the node broadcasts a bit slice of index 0 and increases the bit index to find the different locations until the hashes are the same. Upon receiving a VBIT message, a node compares it to its own VBIT to identify the locations corresponding to the differing (key, version) tuples. After identifying which (key, version) tuples differ, the node broadcasts these (key, version) tuples in a VECTOR message. Upon receiving a VECTOR mes- sage, a node compares it to its own (key, version) tuple to decide who has the newer version and if it should broadcast its DATA. A node with a newer version broadcasts its DATA to nodes with an older version.
PERFORMANCE
Figure 3: DHV Implementation Statistics
(tinyos-2.x/apps/tests/TestDissemination)
DHV has a similar memory footprint compared to DIP (Figure 3). In addition, DHV can disseminate data through the network at least twice faster and uses 50% fewer number of messages compared to the state-of-the-art protocols. DHV is now part of the core networking library in TinyOS-2.x.
PUBLICATIONS
1. Thanh Dang, Nirupama Bulusu, Wu-chi Feng, and Seungweon Park, “DHV: A Code Consistent Maintenance Protocol for Wireless Sensor Networks”, In Proceedings of EWSN 2009, Cork, Ireland, Feb 2009
2. Thanh Dang, Nirupama Bulusu, Wu-chi Feng, and Seungweon Park, “DHV: An Efficient Code Consistent Maintenance Protocol for Wireless Sensor Networks”, In Proceedings of ETTX 2009 (Demo Abstract), Cork, Ireland, Feb 2009
3. Thanh Dang, Nirupama Bulusu, Wu-chi Feng, and Seungweon Park, “DHV: An Efficient Code Consistent Maintenance Protocol for Wireless Sensor Networks”, In Proceedings of EWSN 2009 (Demo Abstract), Cork, Ireland, Feb 2009
LIMITATIONS
CURRENT STATUS
The project is currently active.
OTHERS