«上一篇/Previous Article|本期目录/Table of Contents|下一篇/Next Article»

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

31

期数:

2021年01期

页码:

122-125

栏目:

网络与安全

出版日期:

2021-01-10

文章信息/Info

Title:

Optimal Connected Dominating Set for Messages in Wireless AD Hoc Network

文章编号:

1673-629X(2021)01-0122-04

作者:

唐天兵; 朱继生; 梁家荣

广西大学 计算机与电子信息学院,广西 南宁 530004

Author(s):

TANG Tian-bing; ZHU Ji-sheng; LIANG Jia-rong

School of Computer and Electronic Information,Guangxi University,Nanning 530004,China

关键词:

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

Keywords:

maximal independent set;  connected dominating set;  message-optimal;  minimum connected dominating set;  virtual backbone network

分类号:

TP393

DOI:

10. 3969 / j. issn. 1673-629X. 2021. 01. 022

摘要:

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

Abstract:

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.

常用功能

更新日期/Last Update: 2020-01-10