A novel centralized algorithm for constructing virtual backbones in wireless sensor networks
A novel centralized algorithm for constructing virtual backbones in wireless sensor networks
复制标题
一种在无线传感器网络中构建虚拟主干的新型集中式算法
DOI：
10.1186/s13638-018-1068-7
复制
发表时间：
2018
影响因子：
2.6
通讯作者：
Li Deying
中科院分区：
文献类型：
--
作者：
Luo Chuanwen;Chen Wenping;Yu Jiguo;Wang Yongcai;Li Deying
最小连通控制集（MCDS）的求解是无线传感器网络中的一个关键问题，是实现无线传感器网络高效路由和广播的关键。然而，MCDS问题是np难题。本文提出了一种新的近似算法，近似比率为oh （Δ）+3，时间为o (n2)，用于求解MCDS问题。关键思想是将CDS中的传感器分为主传感器和辅助传感器。核心传感器在CDS中占主导地位，而支撑传感器在CDS中占主导地位。为了最大限度地减少核心和支持者的数量，提出了一种分三个阶段的算法。(1)通过构造独立集（记为asS1）寻找核心传感器，其中贪心地选择（两跳邻居数比一跳邻居数）最大的传感器进入tos1；(2)将所有基核传感器ins1连接形成连通子图，子图中的传感器称为核；(3)将核心传感器的单跳邻居加入到支撑setS2中。这保证了少量的传感器可以添加到CDS中，这是一种新的MCDS构建方案。大量的仿真结果验证了算法的性能。
Finding the minimum connected dominating set (MCDS) is a key problem in wireless sensor networks, which is crucial for efficient routing and broadcasting. However, the MCDS problem is NP-hard. In this paper, a new approximation algorithm with approximation ratioH(Δ)+3 in timeO(n2) is proposed to approach the MCDS problem. The key idea is to divide the sensors in CDS intocoresensors andsupportingsensors. The core sensors dominate the supporting sensors in CDS, while the supporting sensors dominate other sensors that are not in CDS. To minimize the number of both the cores and the supporters, a three-phased algorithm is proposed. (1) Finding the base-core sensors by constructing independent set (denoted asS1), in which the sensors who have the largest(number of two-hop neighbors over the number of one-hop neighbors) will be selected greedily intoS1; (2) Connecting all base-core sensors inS1to form a connected subgraph, the sensors in the subgraph are called cores; (3) Adding the one-hop neighbors of the core sensors to the supporter setS2. This guarantees a small number of sensors can be added into CDS, which is a novel scheme for MCDS construction. Extensive simulation results are shown to validate the performance of our algorithm.