摘要
该文研究了Ad hoc无线网中连通支配集(CDS)的生成方法,并对CDS算法做了两个方面的改进:1)通过引入拓扑相关信息的特征矢量中心性值进行节点编号,避免节点缩减时的随机性,使节点缩减与实际网络拓扑紧密联系;2)CDS算法忽略了最大编号节点的可缩减性,为此改进了该算法并提出新规则实现最大编号节点的缩减判定。该方法解决了CDS算法在生成连通支配集时存在的完全NP难问题,而且可得到条件最优连通支配集。仿真结果验证了改进算法的优良特性。
The formation method of connected-dominating set(CDS)in ad hoc wireless network is studied and improved.There are two improvements in this paper,the first one is numbering the nodes by introducing the eigenvector center value of the network topology information,which avoids the randomness during node reduction and makes the node reduction be related to the actual network topology closely.The second one is that CDS algorithm ignores the removal of the largest numbered nodes,the improved one proposes a new rule to achieve the reduction of the maximum number nodes.Thus,the improved method solves the NP-complete problem of the CDS algorithm in formation method of connected-dominating set and achieves the conditional optimal connected-dominating set.The simulation results show the excellent characteristics of the improved method
作者
黄庆东
闫乔乔
孙晴
HUANG Qing-dong;YAN Qiao-qiao;SUN Qing(School of Communication and Information Engineering, Informations and Communications Technology of National Experimental Teaching Center,Xi’an University of Posts and Telecommunications Xi’an 710121)
出处
《电子科技大学学报》
EI
CAS
CSCD
北大核心
2017年第6期819-824,共6页
Journal of University of Electronic Science and Technology of China
基金
国家重大专项(2017ZX03001012-005)
关键词
Adhoc无线网
支配集
路由
拓扑
无向图
Ad hoc wireless networks
dominating sets
routing
topology
undirected graph
