Olga Saukh
Abstract
Boundary recognition is an important and challenging issue in wireless sensor networks when no coordinates or distances are available. The distinction between inner and boundary nodes of the network can provide valuable knowledge to a broad spectrum of algorithms. This article tackles the challenge of providing a scalable and range-free solution for boundary recognition that does not require a high node density. We explain the challenges of accurately defining the boundary of a wireless sensor network with and without node positions and provide a new definition of network boundary in the discrete domain. Our solution for boundary recognition approximates the boundary of the sensor network by determining the majority of inner nodes using geometric constructions, which guarantee that for a given d, a node lies inside of the construction for a d-quasi unit disk graph model of the wireless sensor network. Moreover, such geometric constructions make it possible to compute a guaranteed distance from a node to the boundary. We present a fully distributed algorithm for boundary recognition based on these concepts and perform a detailed complexity analysis. We provide a thorough evaluation of our approach and show that it is applicable to dense as well as sparse deployments.
- Aspnes, J., Goldenberg, D., and Yang, Y. 2004. On the computational complexity of sensor network localization. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks.Google Scholar
- Blough, D. M., Leoncini, M., Resta, G., and Santi, P. 2003. The k-neigh protocol for symmetric topology control in ad hoc networks. In Proceedings of the 4th International Symposium on Mobile Ad Hoc Networking & Computing. Google ScholarDigital Library
- Breu, H. and Kirkpatrick, D. G. 1998. Unit disk graph recognition is NP-hard. Computat. Geom. Theory Appl. 9 (1--2); 3--24. Google ScholarDigital Library
- Bruck, J., Gao, J., and Jiang, A. A. 2005. MAP: Medial axis based geometric routing in sensor networks. In Proceedings of the 11th International Conference on Mobile Computing and Networking (MobiCom). Google ScholarDigital Library
- Fekete, S. P. and Kröller, A. 2006. Geometry-based reasoning for a large sensor network. In Proceedings of the 22nd Symposium on Computational Geometry. Google ScholarDigital Library
- Fekete, S. P., Kröller, A., Pfisterer, D., Fischer, S., and Buschmann, C. 2004. Neighborhood-based topology recognition in sensor networks. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks.Google Scholar
- Funke, S. 2005. Topological hole detection in wireless sensor networks and its applications. In Proceedings of the Joint Workshop on Foundations of Mobile Computing. Google ScholarDigital Library
- Funke, S. and Klein, C. 2006. Hole detection or: “How much geometry hides in connectivity?”. In Proceedings of the 22nd Symposium on Computational Geometry. Google ScholarDigital Library
- Kröller, A., Fekete, S. P., Pfisterer, D., and Fischer, S. 2006. Deterministic boundary recognition and topology extraction for large sensor networks. In Proceedings of the 17th Symposium on Discrete Algorithms. Google ScholarDigital Library
- Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2004. Unit disk graph approximation. In Proceedings of the Joint Workshop on Foundations of Mobile Computing. Google ScholarDigital Library
- Rao, A., Papadimitriou, C., Shenker, S., and Stoica, I. 2003. Geographic routing without location information. In Proceedings of the 9th International Conference on Mobile Computing and Networking. Google ScholarDigital Library
- Schmid, S. and Wattenhofer, R. 2006. Algorithmic Models for Sensor Networks. In Proceedings of the 14th International Workshop on Parallel and Distributed Real-Time Systems. Google ScholarDigital Library
- Wang, Y., Gao, J., and Mitchell, J. S. 2006. Boundary recognition in sensor networks by topological methods. In Proceedings of the 12th International Conference on Mobile Computing and Networking. Google ScholarDigital Library
Index Terms
- On boundary recognition without location information in wireless sensor networks
Recommendations
Sink placement without location information in large-scale wireless sensor networks
AINTEC '09: Proceedings of the 4th Asian Internet Engineering ConferenceWireless Sensor Networks (WSN) comprise a large number of sensor nodes that possess scarce energy supplies. To minimize energy consumption and to consequently extend the lifetime of WSNs, we propose a local search technique for sink placement in WSNs. In ...
Boundary coverage and coverage boundary problems in wireless sensor networks
The extent of coverage of a Wireless Sensor Network (WSN) is of fundamental importance and determines the utility and effectiveness of the deployment. Determining the least number of sensors required to cover the boundary of a region (boundary coverage) ...
Relay Node Placement in Wireless Sensor Networks
A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy ...
Reviews
Jun Li
In wireless sensor networks (WSNs), an important issue is the distinction between boundary nodes and inner nodes; it is especially challenging when the location information of nodes is completely unknown. To tackle this problem, Saukh et al. propose a geometric graph approach, which they claim is purely distributed and allows the algorithm to run in polynomial time. In contrast to classical studies on boundary recognition problems, their approach guarantees recognition of inner nodes in a WSN, which are separated from the boundary nodes. In this work, a pattern is defined as a d -quasi unit disk graph ( d -QUDG) that assures that some certain node must be inside the graph. Fundamental lemmas and theorems are provided to find those specific and generic patterns. Using the proved generic pattern rules, a sensor node is able to identify one or more potential patterns from its local connection graph, so that the sensor node recognizes itself as an inner node of the whole network. A thorough quantitative evaluation of the proposed solution is conducted. It is shown that the geometric graph approach is applicable to both sparse and dense deployments of sensor nodes, and thus is robust. This paper is generally theoretical, but has great application potential for real WSN deployments. It is well organized, starting from simple facts in the beginning to advanced theorems at the end. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments