Boundary recognition in sensor networks by topological methods
Boundary recognition in sensor networks by topological methods
复制标题
DOI：
10.1145/1161089.1161104
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
Yue Wang;Jie Gao;Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
Yue Wang;Jie Gao;Joseph S. B. Mitchell
无线传感器网络与传感器部署的底层环境紧密相关。网络的全局拓扑结构对传感器网络应用和网络功能的实现都具有重要意义。在本文中，我们研究的问题，拓扑发现，特别是在传感器网络中的边界识别。假设大量的传感器节点分散在一个几何区域内，附近的节点直接相互通信。我们的目标是通过只使用连接信息来找到边界节点。我们不假设任何知识的节点的位置或间距，我们也不强制要求通信图遵循单位盘图模型。我们提出了一个简单的分布式算法，正确地检测节点的边界，并将它们连接到有意义的边界循环。我们获得作为副产品的中轴线的传感器领域，这在创建虚拟坐标路由的应用程序。我们通过大量的模拟表明，该算法给出了良好的效果，即使是低密度的网络。我们还严格证明了算法的正确性连续几何域。
Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this paper we study the problem of topology discovery, in particular, identifying boundaries in a sensor network. Suppose a large number of sensor nodes are scattered in a geometric region, with nearby nodes communicating with each other directly. Our goal is to find the boundary nodes by using only connectivity information. We do not assume any knowledge of the node locations or inter-distances, nor do we enforce that the communication graph follows the unit disk graph model. We propose a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles. We obtain as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing. We show by extensive simulation that the algorithm gives good results even for networks with low density. We also prove rigorously the correctness of the algorithm for continuous geometric domains.