[1] Sun Yanjing, Qian Jiansheng, Gu Xiangping, Chen Guangzhu, et al. (α, β)-constraints connected dominating set algorithmin wireless sensor network [J]. Journal of Southeast University (English Edition), 2008, 24 (4): 414-419. [doi:10.3969/j.issn.1003-7985.2008.04.004]

Copy

(α, β)-constraints connected dominating set algorithmin wireless sensor network()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 4

Page:

414-419

Research Field:

Computer Science and Engineering

Publishing date:

2008-12-30

Info

Title:

(α, β)-constraints connected dominating set algorithmin wireless sensor network

Author(s):

Sun Yanjing¹;  Qian Jiansheng¹;  Gu Xiangping¹;  Chen Guangzhu²

¹ School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221008, China
² School of Mechanical and Electrical Engineering, China University of Mining and Technology, Xuzhou 221008, China

Keywords:

wireless sensor network;  connected dominating set;  transmission delay;  maximal independent set;  power consumption

PACS:

TP393.01

DOI:

10.3969/j.issn.1003-7985.2008.04.004

Abstract:

To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set(CDS)algorithm with(α, β)-constraints is proposed.Based on the(α, β)-tree concept, a new connected dominating tree with bounded transmission delay problem(CDTT)is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes.The CDT algorithm consists of two phases:The first phase constructs a maximum independent set(MIS)in a unit disk graph model.The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPT, respectively.The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTT problem and forms a virtual backbone with(α, β)-constraints balancing the requirements of power consumption and transmission delay.

References:

[1] Wan Pengjun, Alzoubi Khaled M, Frieder Ophir.Distributed construction of connected dominating set in wireless ad hoc networks[J].Mobile Networks and Applications, 2004, 9(2):141-149.
[2] Dai Fei, Wu Jie.On constructing k-connected k-dominating set in wireless ad hoc and sensor networks[J].Journal of Parallel and Distributed Computing, 2006, 66(7):947-958.
[3] Du Wei, Wu Li, Du Hongwei, et al.Maximal independent set and minimum connected dominating set in unit disk graphs[R].Department of Computer Science and Engineering of University of Minnesota, 2004.
[4] Blum Jeremy, Ding Min, Thaeler Andrew, et al.Connected dominating set in sensor networks and MANETs[M].Hingham, MA:Kluwer Academic Publishers, 2004:329-369.
[5] Wu Yiwei, Wang Feng, Thai My T, et al.Constructing k-connected m-dominating sets in wireless sensor network[C]//Military Communications Conference.Orlando, FL, 2007:1-7.
[6] Wu Weili, Du hongwei, Jia Xiaohua, et al.Minimum connected dominating sets and maximal independent sets in unit disk graphs[J].Theoretical Computer Science, 2006, 352:1-7.
[7] Basagni S, Mastrogiovanni M, Panconesi A, et al.Localized protocols for ad hoc clustering and backbone formation:a performance comparison[J].IEEE Transactions on Parallel and Distributed Systems, 2006, 17(4):292-306.
[8] Khan Maleq, Pandurangan Gopal.Energy-efficient distributed constructions of minimum spanning tree for wireless ad-hoc networks[R].West Lafayette:Department of Computer Science Purdue University, 2006.
[9] Li Yingshu, Thai My T.On the construction of a strongly connected broadcast arborescence with bounded transmission delay[J].IEEE Transactions on Mobile Computing, 2006, 15(10):1460-1470.
[10] Khuller Samir, Raghavachari B, Young N.Balancing minimum spanning trees and shortest path trees[J].Algorithm, 1994, 120(4):305-321.
[11] Thai My T, Feng Wang D L.Connected dominating sets in wireless networks with different transmission ranges[J].IEEE Transactions on Mobile Computing, 2007, 16(7):1-10.
[12] Cidon Israel, Mokryn O.Propagation and leader election in a multihop broadcast environment[C]//Proceedings of the 12th International Symposium on Distributed Computing. Andros, Greece, 1998:104-119.
[13] Gallager R G, Humblet P A.A distributed algorithm for minimum-weight spanning trees[J].ACM Transactions on Programming Languages and Systems, 1983, 5(1):66-77.
[14] Brim L, Cerna I, Krcal P, et al.Distributed shortest paths for directed graphs with negative edge lengths, technical report FIMU-RS-2001-01 [R].Faculty of Informatics of Masaryk University, 2001.
[15] Sharma M B, Iyengar S S, Mandyam N K.An optimal distributed depth-first-search algorithm[C]//Proceedings of 17th Ann ACM Conf Computer Science:Computing Trends in the 1990s.Louisville, Kentucky, USA, 1989:287-294.

Memo

Memo:

Biographies: Sun Yanjing(1977—), male, doctor;Qian Jiansheng(corresponding author), male, doctor, professor, qianjsh@cumt.edu.cn.
Foundation items: Major Program of the National Natural Science Foundation of China(No.70533050), High Technology Research Program of Jiangsu Province(No.BG2007012), China Postdoctoral Science Foundation(No.20070411065), Science Foundation of China University of Mining and Technology(No.OC080303).
Citation: Sun Yanjing, Qian Jiansheng, Gu Xiangping, et al.(α, β)-constraints connected dominating set algorithm in wireless sensor network[J].Journal of Southeast University(English Edition), 2008, 24(4):414-419.

Common functions