CRPCG—Clustering Routing Protocol based on Connected Graph

Full Text (PDF, 272KB), PP.11-18

Views: 0 Downloads: 0


Feng Li 1,* Liuhong Huang 1

1. Shandong University/ School of Computer Science and Technology, Jinan, China

* Corresponding author.


Received: 23 Aug. 2010 / Revised: 7 Dec. 2010 / Accepted: 3 Feb. 2011 / Published: 8 May 2011

Index Terms

Connected graph, multiple paths, optimal tree, Leach, clustering routing


In order to balance the load between cluster head, save the energy consumption of the inter-cluster routing, enhance reliability and flexibility of data transmission, the paper proposes a new clustering routing protocol based on connected graph (CRPCG). The protocol optimizes and innovates in three aspects: cluster head election, clusters formation and clusters routing. Eventually, a connected graph is constituted by the based station and all cluster heads, using the excellent algorithm of the graph theory, to guarantee the network connectivity and reliability, improve the link quality, balance node energy and prolong the network life cycle. The results of simulation show that, the protocol significantly prolong the network life cycle, balance the energy of network nodes, especially in the phase of inter-cluster data transmission, improving the reliability and efficiency of data transmission.

Cite This Paper

Feng Li, Liuhong Huang, "CRPCG—Clustering Routing Protocol based on Connected Graph", International Journal of Intelligent Systems and Applications(IJISA), vol.3, no.3, pp.11-18, 2011. DOI:10.5815/ijisa.2011.03.02


[1]Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks. IEEE Communications Magazine, 2002, 40(8): 102−114. 

[2]Shen B, Zhang SY, Zhong YP. Cluster-Based routing protocols for wireless sensor networks. Journal of Software, 2006, 17(7):1588−1600.

[3]W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan. Energy-effcient communication protocol for wireless micro sensor networks, IEEE Proceedings of the Hawaii International Conference on System Sciences, January 2000, pp. 1–10.

[4]SONG Chun-Yan, ZHANG Hua-zhong, ZHANG Xiu-yang. Clustering hierarchy tree routing algorithm based on LEACH. Journal of Computer Applications,2008-10

[5]Zhu Xiao rong, Shen Lian feng. RBF-based cluster-head selection for wireless sensor networks. Journal of Southeast University (English Edition) Vol.22, No.4, pp.451 - 455 

[6]O. Younis, S. Fahmy, HEED: A Hybrid, Energy-Effcient, Distributed clustering approach for Ad Hoc sensor networks. IEEE Transactions on Mobile Computing 3 (4) (2004) 366–379.

[7]Handy MJ, Haase M, Timmermann D. Low energy adaptive clustering hierarchy with deterministic cluster-head selection. In: Proc. of the 4th IEEE Conf. on Mobile and Wireless Communications Networks. Stockholm: IEEE Communications Society, 2002.368−372. 

[8]Ye M, Li CF, Chen GH, Wu J. EECS: An energy efficient clustering scheme in wireless sensor networks. IEEE Int’l Performance Computing and Communications Conf. IEEE Press, 2005.535−540.

[9]Manjeshwar A, Grawal DP. TEEN: A protocol for enhanced efficiency in wireless sensor networks[C]. In: Proc. of the 15th Parallel and Distributed Processing Symp. San Francisco: IEEE Computer Society, 2001. 2009−2015. 

[10]O. Younis, S. Fahmy. HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks[C]. Proceeding of IEEE INFOCOM, 2004:366-379.

[11]SHAH R C,RABAEY J. Energy aware routing for low energy Ad hoc sensor networks [C] .Proc of IEEE Wireless Communications and Networking Conference.2002:350-355

[12]Ye M, Li CF, Chen GH, Wu J. EECS: An energy efficient clustering scheme in wireless sensor networks[C]. In: Proc. of the IEEE Int’l Performance Computing and Communications Conf. New York: IEEE Press, 2005. 535−540.

[13]Younis M, Youssef M, Arisha K. Energy-Aware routing in cluster-based sensor networks[C]. In: Proc. of the 10th IEEE Int’l Symp. on Modeling, Analysis and Simulation of Computer and Telecommunications Systems. Fort Worth: IEEE Computer Society, 2002. 

[14]W. B. Heinzelman, A .P. Chandrakasan, and H.Balakrishnan. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002.1(4):660-670.

[15]S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin, and A. O. Fapojuwo. A Centralized Energy-efficient Routing Protocol for Wireless Sensor Networks [J]. IEEE Communications Magazine, 2005.43: 8-13.