无线Ad Hoc网络中异构链表支配集算法  

Heterogeneous Chain Dominating Set Algorithm in Wireless Ad Hoc Networks

作　　者：韩冰青 陈一飞 HAN Bing-qing;CHEN Yi-fei(School of Technology,Nanjing Audit University,Nanjing 211815,China)

机构地区：[1]南京审计大学工学院,南京211815

出　　处：《计算机科学》2018年第9期135-140,共6页Computer Science

基　　金：国家自然科学基金项目(61402231);江苏省自然科学基金项目(BK2011692)资助

摘　　要：首先给出无线Ad Hoc网络的异构圆盘图模型HDG,并分析HDG模型的不同形态;然后设计出一种新的节点双向链表结构,在此基础上,提出一种基于链表结构的异构连通支配集算法C-LDS。该算法通过双向链表结构管理支配集,并通过节点引用的方式来提高支配集节点增加、删除及修改的时间效率,从而得到优化的连通支配集。将CLDS算法与其他支配集算法进行对比测试,结果表明:在均匀分布以及随机分布的网络场景中,C-LDS所生成的支配集尺寸是最小的;在随机移动的网络场景中,C-LDS的分组投递率是最高的,展现出了较好的异构连通性并且提高了支配集节点的生成效率。Firstly,the heterogeneous disk model HDG of Ad Hoc network was presented,and different forms of HDG model were analyzed.Secondly,a new two-way chain table structure was designed.Based on the chain structure,a connected dominating set algorithm C-LDS was proposed,which manages dominating set through two-way chain table structure,and improves the time efficiency of inserting,deleting and modify the dominating node through the node refe-rence way.Thus,the connected dominating set of Ad Hoc network is optimized.Finally,the C-LDS algorithm was compared with other dominating set algorithms.The simulation results show that C-LDS algorithm generates minimal CDS size in both uniform and random scenarios,and can achieve highest packet delivery ratio in mobile network scenarios,which shows good heterogeneous connectivity and improves the efficiency yeneration of dominating set node.

关 键 词：连通支配集 双向链表 异构圆盘 无线自组网 

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