Connectivity-based and Boundary-Free Skeleton Extraction in Sensor Networks
Connectivity-based and Boundary-Free Skeleton Extraction in Sensor Networks
复制标题
DOI：
10.1109/icdcs.2012.10
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Wenping Liu;Hongbo Jiang;Chonggang Wang;Chang Liu;Yang Yang-Yang;Wenyu Liu-;Bo Li
中科院分区：
文献类型：
--
作者：
Wenping Liu;Hongbo Jiang;Chonggang Wang;Chang Liu;Yang Yang-Yang;Wenyu Liu-;Bo Li
在传感器网络中，骨架（也称为中轴）提取被认为是一种有吸引力的方法，以支持许多应用，如负载平衡路由和位置自由分割。文献中现有的解决方案严重依赖于所识别的边界，这限制了骨架提取算法的适用性。在本文中，我们进行的第一项工作的连接为基础的和边界自由的骨架提取计划，在传感器网络。详细地说，我们提出了一个简单的，分布式的和可扩展的算法，正确地识别一些骨架节点，并将它们连接到一个有意义的网络表示，而不依赖于任何约束的通信无线电模型或边界信息。我们算法的核心思想是利用骨架点的必要（但不是充分）条件：与由x生成的弦上的其他点相比，以骨架点x为中心的圆盘的相交区域应该是最大的，其中弦被称为连接x和边界中的切点的线段。为此，我们提出了一个点的ε-中心性的概念，定量地衡量一个点的“中心”。因此，骨架点与由该点生成的弦上的其他点相比应具有最大的ε中心性值。我们的模拟结果表明，所提出的算法，即使在网络的节点密度较低或倾斜的节点分布等，此外，我们得到了两个副产品，边界和分割结果的网络。
In sensor networks, skeleton (also known as medial axis) extraction is recognized as an appealing approach to support many applications such as load-balanced routing and location free segmentation. Existing solutions in the literature rely heavily on the identified boundaries, which puts limitations on the applicability of the skeleton extraction algorithm. In this paper, we conduct the first work of a connectivity-based and boundary free skeleton extraction scheme, in sensor networks. In detail, we propose a simple, distributed and scalable algorithm that correctly identifies a few skeleton nodes and connects them into a meaningful representation of the network, without reliance on any constraint on communication radio model or boundary information. The key idea of our algorithm is to exploit the necessary (but not sufficient) condition of skeleton points: the intersection area of the disk centered at a skeleton point x should be the largest one as compared to other points on the chord generated by x, where the chord is referred to as the line segment connecting x and the tangent point in the boundary. To that end, we present the concept of ε-centrality of a point, quantitatively measuring how "central" a point is. Accordingly, a skeleton point should have the largest value of ε-centrality as compared to other points on the chord generated by this point. Our simulation results show that the proposed algorithm works well even for networks with low node density or skewed nodal distribution, etc. In addition, we obtain two by-products, the boundaries and the segmentation result of the network.