Multihop Routing in Sensor Networks

Alec Woo
(Professor David E. Culler)
(DARPA) NEST F33615-01-C-1895 and Intel Research Laboratory, Berkeley

Motivated by our technical report on the subject of empirical study of epidemic algorithms in large scale multihop networks, we have pursued the idea of neighborhood discovery based on passive link quality estimations, and the use of such information to analyze different distributed algorithms to perform routing tree construction. One interesting routing algorithm we have developed seeks to obtain the maximum reliable routing path from each node to the base station in a distributed manner based on local link quality estimations. Initial results from static analysis to low level simulations in TOSSIM were promising and motivate us for further investigation against different distributed routing algorithms such as naÔve broadcast based routing, and shortest path routing over reliable neighbors. Lacking a visually rich simulator, we adopted Vanderbiltís Matlab simulator for TinyOS (Prowler) and enhanced it with features that allow detail study of routing algorithms and GUI support to visualize the routing tree evolution. To capture a more realistic model of the radio channel for the simulator, we perform new empirical experiments on the new MICA platform to create a probabilistic model for the radio channel and packet collision. Current results of this work were presented at the Berkeley NEST retreat, Intel Berkeley Research Lab, and NEST PI meeting.

More information ( or

Send mail to the author : (

Edit this abstract