Motivated by realistic sensor network scenarios that have mis-in-formed nodes and variable network topologies, we propose an approach to routing that combines the best features of limited-flooding and information-sensitive path-finding protocols into a reliable, low-power method that can make delivery guarantees independent of parameter values or information noise levels. We introduce
Parametric Probabilistic Sensor Network Routing Protocols, a family of light-weight and robust multi-path routing protocols for sensor networks in which an intermediate sensor decides to forward a message with a probability that depends on various parameters, such as the distance of the sensor to the destination, the distance of the source sensor to the destination, or the number of hops a packet has already traveled. We propose two protocol variants of this family and compare the new methods to other probabilistic and deterministic protocols, namely constant-probability gossiping, uncontrolled flooding, random wandering, shortest path routing (and a variation), and a load-spreading shortest-path protocol inspired by (Servetto and Barrenechea, 2002). We consider sensor networks where a sensor’s knowledge of the local or global information is uncertain (parametrically noised) due to sensor mobility, and investigate the trade-off between robustness of the protocol as measured by quality of service (in particular, successful delivery rate and delivery lag) and use of resources (total network load). Our results for networks with randomly placed nodes and realistic urban networks with varying density show that the multi-path protocols are less sensitive to misinformation, and suggest that in the presence of noisy data, a limited flooding strategy will actually perform better and use fewer resources than an attempted single-path routing strategy, with the
Parametric Probabilistic Sensor Network Routing Protocols outperforming other protocols. Our results also suggest that protocols using network information perform better than protocols that do not, even in the presence of strong noise.
Christopher L. Barrett is leader of the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His Group is a simulation science and technology (S&T) invention organization of 30 scientists devoted to providing large-scale, high performance methods for systems analysis and simulation-based assisted reasoning. His Group engages in fundamental mathematical, algorithmic, and complex systems analysis research. Current applied research is focused on interdependent simulation and analysis tools for complex, socio-technical systems like transportation, communications, public health and other critical infrastructure areas. His scientific experience is in simulation, scientific computation, algorithm theory and development, system science and control, engineering science, bio-systems analysis, decision science, cognitive human factors, testing and training. His applied science and engineering achievements include, for example, development of large-scale, high performance simulation systems (e.g., Transportation Analysis Simulation System, TRANSIMS) and development of a distributed computing approach for detailed simulation-based study of mobile, packet switched digital communications systems (Self Organizing Stochastic Rebroadcast Relay, SORSRER). He has a M.S. and Ph.D. in Bio-information Systems from California Institute of Technology. He is a decorated Navy veteran having served in both the submarine service and as a pilot. He has been awarded three Distinguished Service Awards from Los Alamos National Laboratory, one from the Alliance for Transportation Research, one from the Royal Institute of Technology, Stockholm, and one from Artificial Life and Robotics, Oita University, Japan.
Stephan J. Eidenbenz is a technical staff member in the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory (LANL). He received an M.Sc. in Computer Science from the Swiss Federal Institute of Technology (ETH) in Zurich in 1997 and a Ph.D. in Computer Science from ETH in 2000; he also obtained a Bachelor’s degree in business administration from GSBA in Zurich in 1999. Stephan has worked for McKinsey & Co. in Switzerland, where he received training in business administration and microeconomics. He has held a postdoctoral position at ETH and he has been a postdoctoral fellow at LANL. Stephan’s more than 30 publications cover a wide range of subjects such as approximability and inapproximability properties of visibility problems in polygons and terrains, error modeling in sequencing problems for computation biology, and designing communication protocols robust against selfish behavior. His current research interests include selfish networking, algorithmic game theory, network modeling and simulation, network design, and network optimization.
Lukas Kroc is a student of M.Sc. program in Computer Science at Charles University in Prague. In 2003, he was a Graduate Research Assistant at the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory. His research interests include simulation, wireless networking and artificial intelligence.
Madhav V. Marathe is a Team Leader for Mathematics and Computer Science in the Basic and Applied Simulation Science group, Computer and Computational Sciences (CCS-5) at the Los Alamos National Laboratory. He obtained his B.Tech in 1989 in Computer Science and Engg. from IIT Madras, India and his Ph.D. in 1994 in Computer Science, from University at Albany. His team focuses on developing mathematical and computational tools for design and analysis of large scale simulations of socio-technical and critical infrastructure systems. His research interests are in modeling and simulations of large socio-technical systems, design and analysis of algorithms, computational complexity theory, theory of parallel, distributed and mobile computing and communication systems. He has published over 100 research articles in peer reviewed journals and conferences. He is an adjunct faculty in the Computer Science Department at the University of New Mexico.
James P. Smith is a technical staff member in the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His principal interest is in high performance computing applied to modeling, simulation and analysis of socio-technical systems. His current research applies to national infrastructure, especially telecommunication/computing, public health, and transportation. He has scientific experience in high performance computing and parallel processing applied to large-scale microscopic simulations, including original software design and debugging of very large, evolving systems of inter-operable computational systems, and efficient analysis and synthesis of massive data produced by multi-scale complex environments. Before attending graduate school he worked for a short time in nuclear theory, and had several publications in experimental biophysics from the Pennsylvania Muscle Institute and Bockus Research Institute. During graduate school he took a one year hiatus to start a company to work in analytic finance, and then spent time doing theoretical space physics at LANL. His graduate work eventually included theoretical and experimental fusion research, but concentrated on computational space plasma physics. He has publications in biophysics, analytic finance, education, space plasma physics and computer science, and is a co-inventor on the TRANSIMS patent. He has a Ph.D. in Theoretical Plasma Physics from the University of Texas at Austin.