Stefan Funke
ABSTRACT
Wireless sensor networks typically consist of small, very simple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly, but have no idea about their relative geographic locations. We examine how much geometry information is nevertheless hidden in the communication graph of the network: Assuming that the connectivity is determined by the well-known unit-disk graph model, we prove that using an extremely simple linear-time algorithm one can identify nodes on the boundaries of holes of the network. That is, there is enough geometry information hidden in the connectivity structure to identify topological features—in our example the holes in the network. While the theoretical analysis turns out to be quite conservative,an actual implementation shows that the algorithm works well under less stringent conditions.
- N. Amenta, M. Bern,and D. Eppstein. The crust and the β-skeleton: combinatorial curve reconstruction. Graph. Models Image Process., 60(2):125--135, 1998. Google Scholar
Digital Library
- J. Bruck, J. Gao, and A. Jiang. Map: Medial-axis-based geometric routing in sensor networks. Proc. MobiCom, 2005. Google ScholarDigital Library
- Q. Fang, J. Gao, and L. Guibas. Locating and bypassing routing holes in sensor networks. In 23rd Conf. of the IEEE Communications Society (INFOCOM), 2004.Google ScholarCross Ref
- S. P. Fekete, A. Kröller, D. Pfisterer, and S. Fischer. Deterministic boundary recognition and topology extraction for large sensor networks. In Proc. of SODA, 2006. Google ScholarDigital Library
- S. P. Fekete, A. Kröller, D. Pfisterer, S. Fischer, and C. Buschmann. Neighborhood-based topology recognition in sensor networks. In ALGOSENSORS, 2004.Google ScholarCross Ref
- S. Funke. Topological hole detection in wireless sensor networks and its applications.In DIALM-POMC: Joint workshop on Foundations of mobile computing, 2005. Google ScholarDigital Library
- F. Kuhn, T. Moscibroda, and R. Wattenhofer. Unit disk graph approximation. In Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), 2004. Google ScholarDigital Library
- T. Moscibroda and R. Wattenhofer. Maximal independent sets in radio networks. In 24th ACM Symp. on the Principles of Distributed Computing (PODC), 2005. Google ScholarDigital Library
- A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing without location information. In Proc. MobiCom, 2003. Google ScholarDigital Library
Index Terms
- Hole detection or: "how much geometry hides in connectivity?"
Recommendations
Topological hole detection in wireless sensor networks and its applications
DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computingThe identification of holes in a wireless sensor network is of primary interest since the breakdown of sensor nodes in a larger area often indicates one of the special events to be monitored by the network in the first place (e.g. outbreak of a fire, ...
Efficient hole bypass routing scheme using observer packets for geographic routing in wireless sensor networks
Greedy forwarding fails due to void area (called hole) where no nodes can be deployed in realistic wireless sensor networks. This is known as the local minimum problem. In this paper, we propose BHOP-GR(Bypassing Hole Scheme Using Observer Packets for ...
Virtual Convex Polygon Based Hole Boundary Detection and Time Delay Based Hole Detour Scheme in WSNs
Proceedings of the Symposium on Human Interface 2009 on ConferenceUniversal Access in Human-Computer Interaction. Part I: Held as Part of HCI International 2009In wireless sensor networks, an important issue often faced in geographic routing is the "local minimum phenomenon." To mitigate the local minimum issue, when the routing process becomes stuck at hole boundary nodes, the existing perimeter routing tends ...
Comments