单向链路无线传感器网络的强连通多跳控制集

Strongly connected d-hop dominating set in wireless sensor network with unidirectional links

强连通控制集常被用来代表具有不同传输范围的无线传感器网络的虚拟骨干,较小的虚拟骨干更能高效地进行数据收集和节约无线网络的能量。为了计算强连通控制集,提出了一种新的多跳宽度优先搜索树强连通控制集算法(d-hop BFS_SCDS)。该算法首先使用贪婪策略找到一个多跳控制集(d-DS),然后利用宽度优先搜索树连接d-DS中的节点形成一个强连通多跳控制集。该算法的近似比为(2.4d 2+3.6d+1.2)(dk+1/2)2,其中k是网络的传输范围比。仿真实验表明该算法是有效的,符合预期的结果。

Strong connected dominating sets are often used to represent the virtual backbone of wireless sensor network with different transmission ranges.A smaller virtual backbone can collect data more efficiently,and then save the energy of the wireless network.This paper proposed a new algorithm,called d-hop BFS_SCDS,to compute a strong connected dominating set.Firstly,this algorithm used a greedy strategy to find a multiple-hops dominating set(in brief d-DS).Secondly,it used a breadth-first search(BFS)tree to connect the nodes in the d-DS to form a strong connected multiple-hops dominating set.The approximate ratio of this algorithm was(2.4d 2+3.6d+1.2)(dk+1/2)2,where was the transmission ranges ratio of networks.Simulation results show that this algorithm is effective and meets the expected results.