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

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

作　　者：李艳艳 梁家荣[1,2] Li Yanyan;Liang Jiarong(School of Computer&Electronics Information,Guangxi University,Nanning 530004,China;Guangxi Key Laboratory of Multimedia Communications&Network Technology,Guangxi University,Nanning 530004,China)

机构地区：[1]广西大学计算机与电子信息学院,南宁530004 [2]广西大学广西多媒体通信与网络技术重点实验室,南宁530004

出　　处：《计算机应用研究》2020年第11期3441-3445,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61862003);广西自然科学基金资助项目(2018GXNSFDA280152)。

摘　　要：强连通控制集常被用来代表具有不同传输范围的无线传感器网络的虚拟骨干,较小的虚拟骨干更能高效地进行数据收集和节约无线网络的能量。为了计算强连通控制集,提出了一种新的多跳宽度优先搜索树强连通控制集算法(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.

关 键 词：无线传感器网络 磁盘图 强连通多跳控制集 宽度优先搜索树 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]