Journal of Networks, Vol 6, No 3 (2011), 505-512, Mar 2011
doi:10.4304/jnw.6.3.505-512

A Scalable Clustering Algorithm in Dense Mobile Sensor Networks

Jianbo Li, Shan Jiang

Abstract


Clustering offers a kind of hierarchical organization to provide scalability and basic performance guarantee by partitioning the network into disjoint groups of nodes. In this paper a scalable and energy efficient clustering algorithm is proposed under dense mobile sensor networks scenario. In the initial cluster formation phase, our proposed scheme features a simple execution process with polynomial time complexity, and eliminates the “frozen time” requirement by introducing some GPS-capable mobile nodes to act as cluster heads. In the following cluster maintenance stage, the maintenance of clusters is asynchronously and event driven so as to thoroughly eliminate the “ripple effect” brought by node mobility. As a result local changes in a cluster need not be seen and updated by the entire network, thus bringing greatly reduced communication overheads and being well suitable for the high mobility environment. Extensive simulations have been conducted and the simulation results reveal that our proposed algorithm successfully achieves its target at incurring much less clustering overheads as well as maintaining much more stable cluster structure, as compared to HCC(High Connectivity Clustering)  algorithm


Keywords


mobile sensor networks;topology control; clustering scheme; high connectivity clustering; scalability

References


[1] K.Dantu, M. Rahimi, H.Shah, S.Babel, A. Dhariwal et al., “Robomote: Enabling Mobility in Sensor Networks”, in Proceedings of IEEE IPSN’05, April 2005, pp 404-409.

[2] N. Li, J. C. Hou and L. Sha., “Design and Analysis of An MST-Based TopologyControl Algorithm”, in Proc. of IEEE INFOCOM’03, March/April 2003, Vol3, pp. 1702-1712.

[3] L. Li, J. Y. Halpern and P. Bahl, Y-M. Wang and R. Wattenhofer. “A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks”, in Proc.of IEEE/ACM Transactions on Networking (TON’05), Vol. 13, Issue 1, February 2005, pp. 147-159.

[4] R.Wattenhofer and A. Zollinger, “XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks”, in Proc. of 18th International Parallel and Distributed Processing Symposium (IPDPS’04) - Workshop 12, 2004, p. 216a.

[5] S-Y. Lee, A.Ranjitkar and Y-B Ko, “K-Neigh Backbone Tree based Topoloy Control for Tactical Mobile Ad Hoc Networks”, International Conference on Information Science and Applications 2010 (ICISA’10), 2010, pp1-8.

[6] L.Bao and J. J. Garcia-Luna-Aceves, “Topology Management in Ad Hoc Networks”, In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ’03), Annapolis, MD, ACM, New York 2003, pp. 40–48.

[7] Y. Xu, S. Bien, Y. Mori, J. Heidemannn, and D. Estrin, “Topology Control Protocols to Networked Sensing”, UCLA, Los Angeles,Tech. Rep, 2003.

[8] T.C.Hou, and T.J.Tsai, “An Access-based Clustering Protocol for Multihop Wireless Ad Hoc Networks”, IEEE JSAC, vol.19(no.7), 2001,pp 1201—1210,

[9] D.Kumar, T.Aseri, and R.B.Patel, “EEHC: Energy Efficient Heterogeneous Clustered Scheme for Wireless Sensor Networks”, Computer Communications, vol.32(no.4), Mar 2009, pp 662-667.
doi:10.1016/j.comcom.2008.11.025

[10] J.Y.Yu and P.H.J.Chong, “An Efficient Clustering Scheme for Large and Dense Mobile Ad Hoc Networks(MANETs)”, Computer Communications, vol 30, Aug, 2006,pp 5-16.
doi:10.1016/j.comcom.2006.07.014

[11] A. Ephremides, J.E. Wieselthier and D.J. Baker, “A Design Concept for Reliable Mobile Radio Networks with Frequency Hop-ping Signaling”, In Proceedings of IEEE, vol. 75(1), Jan, 1987,pp 56–73.
doi:10.1109/PROC.1987.13705

[12] C.-H.R. Lin and M. Gerla, “A Distributed Architecture for Multimedia in Dynamic Wireless Networks”, in Proceedings of IEEE GLOBECOM’95, Mar 1995, pp 1468–1472.

[13] J.Y.Yu and P.H.J, Chong, “3hBAC(3-hop between adjacent clusterheads):a novel non-overlapping clustering algorithm for mobile ad hoc networks, in proceeding of IEEE Pacrim’03, vol.1, Aug 2003, pp318-321.

[14] V.Davies, “Evaluating Mobility Models within an Ad Hoc Network”, Phd dissertation, Golden, Colorado, Colorado School of Mines, 2000.

[15] L.Zhao, “Topology Control for Mobile Ad Hoc Networks”, PHD dissertation, 2007, pp. 9-10

[16] L. Zhao, E. L. Lloyd and S. S. Ravi., “Topology Control for Constant Rate Mobile Networks”, Proc. of IEEE GLOBECOM, November 2006, pp. 1-6.

[17] P. Siripongwutikorn, B.Thipakorn, “ Mobility-aware Topology Control in Mobile Ad Hoc Networks”, Computer Communications, 2008, 31, pp. 3521-3532.
doi:10.1016/j.comcom.2008.06.015

[18] L. Zhao and E. L. Lloyd., “Distributed Topology Control for Stationary and Mobile Ad Hoc Networks”, Proc. of 3rd IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS’06), October 2006, pp. 521-524.
doi:10.1109/MOBHOC.2006.278600

[19] J.Wu and FDai, “Mobility Sensitive Topology Control in Mobile Ad Hoc Networks”, IEEE Transactions on Parallel and Distributed Systems, Vol. 17, No. 6, June 2006, pp. 522-535.
doi:10.1109/TPDS.2006.73

[20] F.Dai and J.Wu, “View Consistency for Reliable Topology Control in Mobile Ad Hoc Networks”, Global Telecommunications Conference, 2005.,(GLOBECOM '05), Volume 5,2005, pp 2860-2864.

[21] Y.Xu, J.Heidemann and D.Estrin, “Geography-Informed Energy Conservation for Ad Hoc Routing”, In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, Italy, 2001-7, pp 70–84.

[22] A. Varge, “The OMNET++ Discrete Event Simulation System”, In Proceeding of the European Simulation Multiconference.Pargue, 2001, pp 319-324.

[23] L.J. Bo, H.L.Sheng and W.Gang., “A Novel Clustering Algorithm by Using Mobile Gateways in Densely Deployed Sensor Networks”, In proceedings of International Conference on Information and Automation, Zhangjiajie, China, 2008-06, pp 1553–1559.

[24] C.Bettstetter, C.Wagner, “The Spatial Node Distribution of the Random Waypoint Model”, In Proc of 1st German Workshop on Mobile Ad-Hoc Networks(WMAN’02), 2002, pp 1–18.


Full Text: PDF


Journal of Networks (JNW, ISSN 1796-2056)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.