Locating and Bypassing Holes in Sensor Networks

In real sensor network deployments, spatial distributions of sensors are usually far from being uniform. Such networks often contain regions without enough sensor nodes, which we call holes. In this paper, we show that holes are important topological features that need to be studied. In routing, holes are communication voids that cause greedy forwarding to fail. Holes can also be defined to denote regions of interest, such as the “hot spots” created by traffic congestion or sensor power shortage. In this paper, we define holes to be the regions enclosed by a polygonal cycle which contains all the nodes where local minima can appear. We also propose simple and distributed algorithms, the Tent rule and BoundHole, to identify and build routes around holes. We show that the boundaries of holes marked using BoundHole can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest. Qing Fang is currently a Ph.D. student in Department of Electrical Engineering at Stanford University. Her research interests include algorithm, architecture and protocol design for wireless sensor networks and ad hoc communication. She received her MS in Electrical Engineering from University of Texas at Austin in Fall 1995 and worked in the industry as a system software engineer before joining Stanford in 1999. Jie Gao received her Ph.D. degree from department of computer science at Stanford University in 2004 and her B.S. degree from University of Science and Technology of China in 1999. She joined State University of New York, Stony Brook as an assistant professor in Fall 2005. Her research interests are algorithms design and analysis, ad hoc communication and sensor networks and computational geometry. Leonidas J. Guibas heads the Geometric Computation group in the Computer Science Department of Stanford University. He is a member of the Computer Graphics and Artifical Intelligence Laboratories and works on algorithms for sensing, modeling, reasoning, rendering, and acting on the physical world. Professor Guibas’ interests span computational geometry, geometric modeling, computer graphics, computer vision, sensor networks, robotics, and discrete algorithms–-all areas in which he has published and lectured extensively. Leonidas Guibas obtained his Ph.D. from Stanford in 1976, under the supervision of Donald Knuth. His main subsequent employers were Xerox PARC, MIT, and DEC/SRC. He has been at Stanford since 1984 as Professor of Computer Science. At Stanford he has developed new courses in algorithms and data structures, geometric modeling, geometric algorithms, and sensor networks. Professor Guibas is an ACM Fellow.