Connectivity-Based Space Filling Curve Construction Algorithms in High Genus 3D Surface WSNs
Connectivity-Based Space Filling Curve Construction Algorithms in High Genus 3D Surface WSNs
复制标题
DOI：
10.1145/2907947
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Chen Wang;Hongbo Jiang;Yan Dong
中科院分区：
文献类型：
--
作者：
Chen Wang;Hongbo Jiang;Yan Dong
无线传感器网络(WSNs)中的许多应用都要求将给定监测区域内的传感器观测数据以一种连续的方式聚合。这需要构建一条穿过该区域中所有传感器的路由路径，这也是线性化网络所必需的。本文提出了一种高亏格三维曲面无线传感器网络的空间填充曲线构造方案SURF，其遍历路径是可证明的非周期性的(即任何节点至多被覆盖固定次数)。SURF算法首先利用跳数距离函数构造离散环境下的等值线，然后利用Reeb图和最大割集的概念将网络划分为不同的区域。最后，提出了一种新颖的序列遍历方案，实现了区域内和区域间的遍历。据我们所知，SURF是第一个针对网络线性化的高亏格3D表面无线传感器网络目标和纯基于连接的解决方案。它是完全分布式且高度可扩展的，需要网络中每个节点几乎恒定的存储和通信成本。为了融入空间填充曲线的自适应密度，我们还设计了第二种算法SURF+，该算法利用参数化的螺旋状曲线覆盖3D曲面，从而产生一种多分辨率的SFC，以适应不同的旅行预算或融合延迟要求。文中还给出了这两种算法在高亏格三维地表无线传感器网络中的应用。在几个典型网络上的大量仿真表明，这两种算法在高亏格3D表面无线传感器网络上都能很好地工作。
Many applications in wireless sensor networks (WSNs) require that sensor observations in a given monitoring area are aggregated in a serial fashion. This demands a routing path to be constructed traversing all sensors in that area, which is also needed to linearize the network. In this article, we present SURF, a Space filling cURve construction scheme for high genus three-dimensional (3D) surFace WSNs, yielding a traversal path provably aperiodic (that is, any node is covered at most a constant number of times). SURF first utilizes the hop-count distance function to construct the iso-contour in discrete settings, and then it uses the concept of the Reeb graph and the maximum cut set to divide the network into different regions. Finally, it conducts a novel serial traversal scheme, enabling the traversal within and between regions. To the best of our knowledge, SURF is the first high genus 3D surface WSN targeted and pure connectivity-based solution for linearizing the networks. It is fully distributed and highly scalable, requiring a nearly constant storage and communication cost per node in the network. To incorporate adaptive density of the constructed space filling curve, we also design a second algorithm, called SURF+, which makes use of parameterized spiral-like curves to cover the 3D surface and thus can yield a multiresolution SFC adapting to different requirements on travel budget or fusion delay. The application combining both algorithms for in-network data storage and retrieval in high genus 3D surface WSNs is also presented. Extensive simulations on several representative networks demonstrate that both algorithms work well on high genus 3D surface WSNs.