基于计时器的最小连通支配集生成算法

doi:10.3969/j.issn.1000-436x.2013.02.012

通信学报 ›› 2013, Vol. 34 ›› Issue (2): 100-108.doi: 10.3969/j.issn.1000-436x.2013.02.012

基于计时器的最小连通支配集生成算法

杨阳,芮兰兰,郭少勇,邱雪松,亓峰

北京邮电大学网络与交换技术国家重点实验室，北京 100876

出版日期:2013-02-25 发布日期:2017-07-17
基金资助:
国家自然科学基金创新研究群体科学基金资助项目;国家科技重大专项基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家科技支撑计划基金资助项目

Timer based algorithm for minimum connected dominating set construction

Yang YANG,Lan-lan RUI,Shao-yong GUO,Xue-song QIU,Feng QI

State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

Online:2013-02-25 Published:2017-07-17
Supported by:
The Science Fund for Creative Research Groups of National Natural Science Foundation of China;The National S＆T Major Project;The National High Technology R＆D Program (863 Program);The National Key Technology R＆D Program

摘要/Abstract

摘要：

摘要：在分簇的MANET中，基于计时器思想提出最小连通支配集生成算法，实现动态拓扑下骨干网构建与重构，证明了算法正确性。仿真结果表明，该算法能以少量消息开销，生成较小连通支配集，快速调整骨干网适应拓扑变化。

关键词: 移动自组网, 虚拟骨干网, 连通支配集, 启发式分簇, 动态拓扑

Abstract:

In clustered MANET,a timer theory based MCDS algorithm was proposed to construct and reconstruct visual backbone quickly under dynamic topologies.The validity of this MCDS algorithm was established.The simulation results demonstrate that our algorithm produces a CDS of competitive size with low message overhead and adjusts the visual backbone fast to adapt to dynamic network topologies.

Key words: MANET, virtual backbone, connected dominating set, heuristic clustering, dynamic topology

杨阳,芮兰兰,郭少勇,邱雪松,亓峰. 基于计时器的最小连通支配集生成算法[J]. 通信学报, 2013, 34(2): 100-108.

Yang YANG,Lan-lan RUI,Shao-yong GUO,Xue-song QIU,Feng QI. Timer based algorithm for minimum connected dominating set construction[J]. Journal on Communications, 2013, 34(2): 100-108.

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 16

[1]	唐勇, 周明天, 张欣 . 无线传感器网络路由协议研究进展[J]. 软件学报, 2006,17(3): 410-421. TANG Y , ZHOU M T , ZHANG X . Overview of routing protocols in wireless sensor networks[J]. Journal of Software, 2006,17(3): 410-421.
[2]	GAREY M R , JOHNSON D S . Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. New York: W H Freeman ＆CoPress, 1979.
[3]	DAS B , BHARGHAVAN V . Routing in ad-hoc networks using minimum connected dominating sets[A]. Proceedings of the I E International Conference on Communications[C]. Montreal,Canada, 1997. 376-380.
[4]	DAI F , WU J . An extended localized algorithm for connected dominating set formation in ad hoc wireless networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2004,15(10): 908-920.
[5]	VAHID G , SEYED N , MOJTABA M . Connected dominating set construction using an efficient pruning method in ad hoc networks[A]. Wireless Internet Conference (IEEE WICON) The 5th Annual ICST[C]. Singapore, 2010. 1-8.
[6]	RAJIV M , CHITTARANJAN M . Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010,21(3): 292-302.
[7]	BO H . Zone-based virtual backbone formation in wireless ad hoc networks[J]. Ad Hoc Networks, 2009,7: 183-200.
[8]	TORKESTANI J A , MEYBODI M R . An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata[J]. Computer Networks, 2010,54: 826-843.
[9]	KIM D Y , ZHANG Z , LI X Y ,et al. Better approximation algorithm for computing connected dominating sets in unit ball graphs[J]. IEEE Transactions on Mobile Computing, 2010,9(8): 1108-1118.
[10]	DING L , GAO X F , WU W L ,et al. Distributed construction of connected dominating sets with minimum routing cost in wireless networks[A]. Distributed Computing Systems (IEEE ICDCS)[C]. Genoa,Italy, 2010. 448-457.
[11]	WANG Y M , ZHAO D S . A serial MIS based CDS constructing algorithm for wireless networks[A]. Green Computing and Communications(GreenCom)IEEE/ACM Int'l Conference on ＆ Int'l Conference on Cyber Physical and Social Computing (CPSCom)[C]. Hangzhou,China, 2010,466-469.
[12]	DING L , WU W L , WILLSON J ,et al. Efficient algorithms for topology control problem with routing cost constraints in wireless networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011,22(10): 1061-1069.
[13]	ZHENG C , SUN S X , HUANG T Y . Constructing distributed connected dominating sets in wireless ad hoc and sensor networks[J]. Journal of Software, 2011,22(5): 1053-1066.
[14]	YINA B , SHI H C , SHANG Y . An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks[J]. Journal of Parallel and Distributed Computing, 2011,77: 27-39.
[15]	ZOU F , WANG Y X , XU X H ,et al. New approximations for mini-mumweighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs[J]. Theoretical Computer Scie , 2011,412: 198-208.
[16]	ARIYAM D , CHITTARANJAN M , CHRIS R . An improved greedy construction of CDS in MANET[A]. Wireless Communications and Networking Conference (IEEE WCNC)[C]. Cancun,Mexico, 2011. 790-795.

基于计时器的最小连通支配集生成算法

Timer based algorithm for minimum connected dominating set construction

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 16

相关文章 15

Metrics

推荐阅读 0

[1]	陈振,韩江洪,杨勇,刘征宇,陆阳. VANET中利用空闲TDMA时隙协助发送数据的方法[J]. 通信学报, 2015, 36(7): 92-101.
[2]	李洪成，吴晓平，严博. 面向MANET异常检测的分布式遗传k-means研究[J]. 通信学报, 2015, 36(11): 167-173.
[3]	丁煦,韩江洪,石雷,夏伟,魏振春. 可充电无线传感器网络动态拓扑问题研究[J]. 通信学报, 2015, 36(1): 129-141.
[4]	闻英友,赵博,赵宏. 基于博弈理论的移动自组网激励机制研究[J]. 通信学报, 2014, 35(4): 44-52.
[5]	闻英友1,2，赵博1，赵宏2. 基于博弈理论的移动自组网激励机制研究[J]. 通信学报, 2014, 35(4): 6-52.
[6]	郭晶晶,马建峰,李琦,万涛,高聪,张亮. 基于博弈论的移动自组织网络的信任管理方法[J]. 通信学报, 2014, 35(11): 50-58.
[7]	郭晶晶，马建峰，李琦，万涛，高聪，张亮. 基于博弈论的移动自组织网络的信任管理方法[J]. 通信学报, 2014, 35(11): 6-49.
[8]	许智君,胡琪,张玉军,叶新铭. MANET网络激励节点协作的信任评估路由协议[J]. 通信学报, 2012, 33(7): 27-35.
[9]	王路,胡月梅,刘立祥,胡晓惠. 基于跳到跳信息的卫星网络传输控制协议研究[J]. 通信学报, 2012, 33(6): 91-102.
[10]	孙彦景,钱建生,马姗姗,任鹏. 时延和能耗均衡的强连通支配集构造算法[J]. 通信学报, 2012, 33(5): 58-65.
[11]	史庭俊,方旭明,杨云. 基于连通支配树的异构传感器网络拓扑修复算法[J]. 通信学报, 2012, 33(10): 77-85.
[12]	吴华锋,施朝健,高传善. CAR：一种MANET环境下的P2P资源定位与获取算法[J]. 通信学报, 2011, 32(12): 18-28.
[13]	宋磊,窦文华,饶丽萍. 认知无线电ad hoc网络分布式簇构建和维护算法[J]. 通信学报, 2011, 32(11A): 79-85.
[14]	叶晖,陈志刚,赵明. ON-CRP ：机会网络缓存替换策略研究[J]. 通信学报, 2010, 31(5): 98-107.
[15]	杜春来,胡铭曾,张宏莉,张冬艳. 基于双向散列链具有撤销能力的自愈组密钥分发机制[J]. 通信学报, 2009, 30(6): 33-37.