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

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

Abstract

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

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.

Figures/Tables 10

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Timer based algorithm for minimum connected dominating set construction

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 10

References 16

Related Articles 15

Metrics

Recommended 0

[1]	Zhi-nan LI,Xiao-dong YANG. Routing discovery algorithm based on reliable path stability estimation in MANET [J]. Journal on Communications, 2016, 37(8): 119-128.
[2]	. Yaksha scheme based content publish/subscribe system for NDN [J]. Journal on Communications, 2015, 36(11): 127-135.
[3]	Xu DING,Jiang-hong HAN,Lei SHI,Wei XIA,Zhen-chun WEI. Problem of the dynamic topology architecture of rechargeable wireless sensor networks [J]. Journal on Communications, 2015, 36(1): 129-141.
[4]	. Game theory based trust management method for mobile ad hoc networks [J]. Journal on Communications, 2014, 35(11): 6-49.
[5]	Jing-jing GUO,Jian-feng MA,Qi LI,Tao WAN,Cong GAO,Liang ZHANG. Game theory based trust management method for mobile ad hoc networks [J]. Journal on Communications, 2014, 35(11): 50-58.
[6]	Rong-sen LI,Wen-hua DOU. SIM: a secure IP protocol for MANET [J]. Journal on Communications, 2013, 34(Z1): 116-125.
[7]	Li-cai LIU,Li-hua YIN,Yun-chuan GUO,Yan SUN. Analysis and improvement for authentication protocols of mobile ad hoc network with CSP approach [J]. Journal on Communications, 2013, 34(Z1): 58-66.
[8]	. SIM: a secure IP protocol for MANET [J]. Journal on Communications, 2013, 34(Z1): 15-125.
[9]	. Analysis and improvement for authentication protocols ofmobile ad hoc network with CSP approach [J]. Journal on Communications, 2013, 34(Z1): 8-66.
[10]	Zhi-jun XU,Qi HU,Yu-jun ZHANG,Xin-ming YE. Trust evaluation routing protocol to enforce cooperation in mobile ad hoc networks [J]. Journal on Communications, 2012, 33(7): 27-35.
[11]	Lu WANG,Yue-mei HU,Li-xiang LIU,Xiao-hui HU. Transmission control protocol based on hop-by-hop for satellite networks [J]. Journal on Communications, 2012, 33(6): 91-102.
[12]	Yan-jing SUN,Jian-sheng QIAN,Shan-shan MA,Peng REN. Strongly connected dominating set construction algorithm balancing time delay and energy consumption [J]. Journal on Communications, 2012, 33(5): 58-65.
[13]	Ting-jun SHI,Xu-ming FANG,Yun YANG. Topology restoration algorithm for heterogeneous sensor networks based on connected dominating tree [J]. Journal on Communications, 2012, 33(10): 77-85.
[14]	Qing-song DU,Jiang ZHU,Er-yang ZHANG. Optimized AODV routing protocol based on reverse route search in leisure time and route learning [J]. Journal on Communications, 2011, 32(8): 64-71.
[15]	Hua-feng WU,Chao-jian SHI,Chuan-shan GAO. CAR:a P2P content addressable and auto-retrievable algorithm for M ANET [J]. Journal on Communications, 2011, 32(12): 18-28.