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

来源：计算机技术与发展杂志2021年第01期北京时间：

作者：唐天兵;朱继生;梁家荣

摘要：在无线自组网中, 提出了一种虚拟骨干网连通控制集( connected dominating set)。 然而, 寻找最小连通控制集(minimum connected dominating set) 是一个 NP 困难的问题。 在很多文献中已经提出了计算最小连通控制集的近似算法,这些算法大都存在近似比很差、时间复杂度和消息复杂度高等问题。 近年来,提出了一些新的构造连通控制集的分布式启发式算法。 这些新的启发式算法基于生成树的构造,这使得在迁移和拓扑更改的情况下维护连通控制集的通信开销非常昂贵,会对整个网络的性能及生存时间产生影响。 因此消息最优的连通控制集也就被提出。 在保证构建消息最优的连通控制集的情况下,通过建立一种新的求解极大独立集的模型,考虑到圆不能密铺会造成一定的误差,通过使用正六边形来代替 R 为 0.5 的圆,从而求得了一个更为精确的三跳内极大独立集,改善了文献[16] 中的结果,得到了更小的连通控集近似比,其值为 143 opt+33。

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