计算机应用研究

作者：李艳艳,梁家荣,

单位：1.广西大学计算机与电子信息学院,南宁530004；2.广西多媒体通信与网络技术重点实验室,南宁530004；

关键词：无线传感器网络,单位圆盘图,虚拟骨干,3连通多跳控制集,

基金：国家自然科学基金资助项目(61862003)；广西自然科学基金资助项目(2018GXNSFDA281052,2017GXNSFAA198276,2017GXNSFAA198263)；；

无线传感器网络的一个虚拟骨干是一个节点子集，虚拟骨干中的节点负责相关的路由任务。设计的虚拟骨干越小，网络的相关开销就越少，虚拟骨干的大小是衡量虚拟骨干质量的关键因素。通常，单位圆盘图被用来模拟一个无线传感器网络。在无线传感器网络中寻找最小虚拟骨干问题可以抽象为求单位圆盘图中的最小连通控制集问题。然而，求单位圆盘图中的最小连通控制集问题是NP难问题，许多工作都是致力于寻找最小连通控制集的近似算法。无线传感器网络中构造3连通多跳控制集可以有效地减小连通控制集的大小和节点间转发的信息总数，是寻找最小虚拟骨干的有效近似。为此提出了一个无线传感器网络中构造3连通多跳控制集的算法，获得一个大小不超过5（2r+2β+1）（r+1）β|U*|-10（2+β）（r+1）-5r-12的3连通多跳控制集。最后通过仿真实验对提出的算法性能进行了相应分析，实验结果符合算法的预期效果。

来源：2020年第11期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2020年第11期