无线自组网络中的消息最优的连通控制集  

Optimal Connected Dominating Set for Messages in Wireless AD Hoc Network

作　　者：唐天兵[1] 朱继生 梁家荣[1] TANG Tian-bing;ZHU Ji-sheng;LIANG Jia-rong(School of Computer and Electronic Information,Guangxi University,Nanning 530004,China)

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004

出　　处：《计算机技术与发展》2021年第1期122-125,共4页Computer Technology and Development

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

摘　　要：在无线自组网中,提出了一种虚拟骨干网连通控制集(connected dominating set)。然而,寻找最小连通控制集(minimum connected dominating set)是一个NP困难的问题。在很多文献中已经提出了计算最小连通控制集的近似算法,这些算法大都存在近似比很差、时间复杂度和消息复杂度高等问题。近年来,提出了一些新的构造连通控制集的分布式启发式算法。这些新的启发式算法基于生成树的构造,这使得在迁移和拓扑更改的情况下维护连通控制集的通信开销非常昂贵,会对整个网络的性能及生存时间产生影响。因此消息最优的连通控制集也就被提出。在保证构建消息最优的连通控制集的情况下,通过建立一种新的求解极大独立集的模型,考虑到圆不能密铺会造成一定的误差,通过使用正六边形来代替R为0.5的圆,从而求得了一个更为精确的三跳内极大独立集,改善了文献[16]中的结果,得到了更小的连通控集近似比,其值为143opt+33。In the wireless AD Hoc network,a virtual backbone network CDS(connected dominating set)is proposed.However,finding the MCDS(minimum connected dominating set)is a NP-hard problem.In many literatures,approximation algorithms for calculating the minimum connected control set have been proposed.Most of these algorithms have poor approximation ratio,high time complexity and message complexity.In recent years,some new distributed heuristic algorithms for constructing CDS are proposed.These new heuristics are based on the construction of spanning trees,which makes it quite expensive to maintain the communication overhead of CDS in the case of migration and topology changes,which will affect the performance and lifetime of the entire network.Therefore,the optimal connected dominating set for messages is proposed.Under the condition that the optimal connected dominating set of messages is guaranteed to be constructed,a new model for solving the maximal independent set is established.Considering that the circle cannot be closely packed will cause certain errors,a more accurate 3-hop maximal independent set is obtained by using a regular hexagon instead of a circle with R=0.5,which improves the results in literature[16]and obtains a smaller approximate ratio of connected dominating set,whose value is 143opt+33.

关 键 词：极大独立集 连通控制集 消息最优 最小连通控制集 虚拟骨干网 

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