Journal of Computer Research and Development (计算机研究与发展) 2009/2009:12 PP.2033-2043

A Tree-Based Clustering Construction Algorithm (TBCCA) in Wireless Sensor Network

Aimed at the disadvantages on current clustered and topology control protocols in distributed wireless sensor network (WSN), such as high energy cost, non-balanced communication overhead, unsatisfactory computational complexity and extra consumption, etc., a novel tree based clustering construction algorithm (TBCCA) is presented. Firstly, it provides some premises and definitions about topologic model such as area radius, cluster radius and reachable adjacent domain, etc. Based on isosceles triangle clustered-tree structure, it proposes clustering strategy according to three types of threshold sets called near set, common set and medium set, and cluster radius controlled by RSSI (received signal strength indicator) value between neighboring nodes. Detailed procedures which contain cluster head selection and determination of candidate nodes are described in this paper, where some theorems about topology & coverage are in proof, and several optional strategies are provided in terms of different requirements on price of computation or communication. Performance analysis and simulation results illustrate that TBCCA has advantage over some existing algorithms in computational expense, for instance, TopDisc or DLMST; And compared with Leach protocol and HEED protocol, TBCCA is energy-efficient and energy-balanced, and expands the life-time of network while lower complexity, higher coverage and connectivity is guaranteed.

Key words:wireless sensor network,clustering,topology control,tree-based structure,coverage

ReleaseDate:2014-07-21 15:00:20

[1] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless micro-sensor networks[C] Proc of the 33rd Annual Hawaii Int Conf on System Sciences. Los Alamitos, CA: IEEE Computer Society, 2000: 3005-3014

[2] Manjeshwar A, Grawal D P. TEEN: A protocol for enhanced efficiency in wireless sensor network[C] Proc of the 15th Parallel and Distributed Processing Symp. Los Alamitos, CA: IEEE Computer Society, 2001: 2009-2015

[3] Younis O, Fahmy S. Heed: A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks[J] . IEEE Trans on Mobile Computing, 2004, 3(4): 660-669

[4] Gupta I, Riordan D, Sampalli S. Cluster-head election using fuzzy logic for wireless sensor network[C] Proc of the 3rd Annual Communication Networks and Services Research Conf. Los Alamitos, CA: IEEE Computer Society, 2005: 255-260

[5] Li N, Hou J C. Topology control in heterogeneous wireless networks: problems and solutions[C] Proc of the IEEE Conf on Computer Communications (INFOCOM). New York: IEEE Computer Society, 2004: 232-243

[6] Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for ad hoc routing[C] Proc of the ACM Int Conf on Mobile Computing and Networking (MobiCom). New York: ACM, 2001: 70-84

[7] Jin Xin, Xiong Yan, Li Min, et al. A connectible-cell based topology control algorithm for wireless sensor network[J] . Journal of Computer Research and Development, 2008, 45(2): 217-226 (in Chinese)(金鑫, 熊焰, 李旻, 等. 基于可连Cell的无线传感器网络拓扑控制算法[J] . 计算机研究与发展, 2008, 45(2): 217-226)

[8] Cerpa A, Estrin D. ASCENT: Adaptive self-configuring sensor networks topologies[C] Proc of the IEEE Conf on Computer Communications (INFOCOM). New York: IEEE Computer Society, 2002: 1278-1287

[9] Wattenhofer R, Zollinger A. XTC: A practical topology control algorithm for ad-hoc networks[C] Proc of the Int Parallel and Distributed Processing Symp (IPDPS). Los Alamitos, CA: IEEE Computer Society, 2004: 216-223

[10] Fang Q, Zhao F, Guibas L J. Lightweight sensing and communication protocols for target enumeration and aggregation[C] Proc of the 4th ACM Int Symp on Mobile Ad Hoc Networking & Computing. New York: ACM, 2003: 165-176

[11] Deb B, Bhatnagar S, Nath B. A topology discovery algorithm for sensor networks with applications to network management, DCS-TR-441[R] . New Brunswick, NJ: Rutgers University, 2001

[12] Amis A D, Prakash R, Huynh D, et al. Max-min d-cluster formation in wireless ad hoc networks[C] Proc of the IEEE Conf on Computer Communications (INFOCOM 2000). Los Alamitos, CA: IEEE Computer Society, 2000: 32-41

[13] Rappaport T S. Wireless Communications: Principles and Practice[M] . 2nd Edition. Upper Saddle River, NJ: Prentice Hall PTR, 1996

[14] Goldsmith A. Wireless Communications[M] . Cambridge, England: Cambridge University Press, 2005([美] Goldsmith A. 无线通信[M] . 杨鸿文, 等译. 北京: 人民邮电出版社, 2006)

[15] Chipcon AS SmartRF. CC1000 Datasheet (rev.2.3)[EB/OL] . [2009-04-20] . http:

[16] Li Haosheng. Application research on localization technology of wireless sensor network[D] . Nanjing: Nanjing University of Posts & Telecommunications, 2009 (in Chinese)(李昊生. 无线传感器网络定位技术及其应用研究[D] . 南京: 南京邮电大学, 2009)