A Review Study on Analytical Estimation of Optimal Number of Clusters in Wireless Sensor Networks

  • Vinay Kumar Visvesvaraya National Institute of Technology, Nagpur, India
  • Sanjay B Dhok Visvesvaraya National Institute of Technology, Nagpur, India
  • Rajeev Tripathi MNNIT Allahabad
  • Sudarshan Tiwari NIT Raipur
Keywords: Wireless Sensor Networks, Clustering, Optimal Clustering, Energy Efficient WSNs, Optimal Number of Clusters, Algorithms for Optimal Number of Clusters

Abstract

To improve energy efficiency, total network scalability and data aggregation in Wireless Sensor Networks (WSNs), sensor nodes are often grouped into disjoint and mostly non overlapping subsets called clusters. To provide an energy-efficient system by clustering, there are three main challenges. First is to find the optimum number of nodes in a specific cluster, second is to find the optimum number of clusters in the network and the third is to find the optimum position of Cluster Head (CH) in a specific cluster. Selecting an optimum number of clusters in WSNs provide greater improvement in terms of system scalability, energy efficiency, collision reduction, network lifetime, latency, and efficient routing backbone in the network. Selection of optimal number of clusters in WSNs is affected by level at which WSNs is modeled viz. Radio Energy Model Level, Network Model Level and Clustering Level. The objective of this paper is to present a state-of-the-art survey of distinct analytical methods used to calculate the optimum number of clusters, and its time-line comparative analysis based on network type, mathematical formula for an optimal number of clusters, base station positioning, energy model, strengths, weaknesses and applications of WSNs. We have also discussed the impact of different parameters on selecting the optimal number of clusters in WSNs.

References

. Pottie, G.; Kaiser, W. Wireless Integrated Network Sensors. ACM Communications, 2000, 43, 5,p. 51–58.

. Kushwaha, S.; Kumar, V.; Jain, S. Node Architectures and Its Deployment in Wireless Sensor Networks: A Survey. In High Performance Architecture and Grid Computing, published Springer Berlin Heidelberg, 2011, p. 515-526.

. Yu, J. Y.; Chong, P. H. J. A Survey of Clustering Schemes for mobile ad hoc networks. IEEE Communications Surveys Tutorials, 2005, 7,p. 32–48.

. Kumar, V.; Jain, S.; Tiwari, S. Energy Efficient Clustering Algorithms in Wireless Sensor Networks: A survey. IJCSI International Journal of Computer Science Issues, 2011, 8(5),p. 1694-0814.

. Kumar, V.; Tiwari, S. Energy Efficient Mechanisms in Wireless Sensor Networks: A survey. International Journal of Advanced Research in Computer Science, 2011, 2(5),p. 595-604.

. Abbasi, A. A.; Younis, M. A Survey on Clustering Algorithms for Wireless Sensor Networks. Elsevier Science direct Computer Communications, 2007, 30,p. 2826–2841.

. Deosarkar, B. P.; Yadav, N. S.; Yadav, R. Cluster head selection in clustering algorithms for wireless sensor networks: A Survey. Proceedings of International Conference on Computing, Communication and Networking, 2008, p. 1–8.

. Akyildiz, I. F.; Vuran, M. C.Wireless Sensor Networks. A John Wiley and Sons, Ltd, Publication, 2010.

. Zhang, Y.; Yang, L.T.; Chen J. RFID and Sensor networks: Architectures, Protocols, Security, and Integrations. CRC press Taylor and Francis 2010.

. Heinzelman, W.R.; Chandrakasan, A.; Balakrishnan, H. Energy-efficient communication protocol for wireless microsensor networks. Proceeding 33rd Hawaii International Conference on System Sciences, 2000, p. 3005–3014.

. Dali, W.; Chan, H. A survey on cluster schemes in ad hoc wireless networks. Proceedings of 2nd International Conference on Mobile Technology, application and systems, 2005, p.1-8.

. Kozat, U.C.; Kondylis, G.; Ryu, B.; Marina, M. Virtual dynamic backbone for mobile ad hoc networks. IEEE International Conference on Communication, 2002, p.250-255.

. Chen, B.; Jamieson, K.; Balakrishnan, H.; Morris, R. SPAN: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In Wireless Networks, 2002, 8,p. 481–494.

. Krunz, M.; Siam, M. Z.; Nguyen, D. N. Clustering and power management for virtual MIMO communications in wireless sensor networks. Journal of Ad-hoc network, 2013, 11(5), p. 1571–1587.

. Naeimi, S.; Ghafghazi, H.; Chow, C.; Ishii, H. Survey on the Taxonomy for Cluster-based Routing Protocols for Homogeneous Wireless Sensor Networks. Sensors. Journal of Sensor, MDPI, 2012, 12(6),p. 7350–7409.

. Liu X. A Survey on Clustering Routing Protocols in Wireless Sensor Networks. Journal of Sensors, 2012, 12,p. 11113-11153.

. Li, J.; Mohapatra, P. Analytical modeling and mitigation techniques for the energy hole problem in sensor networks. Pervasive Mobile Computation, 2007, 3, p.233–254.

. Tran-Quang, V.; Miyoshi, T. A Transmission Range Adjustment Algorithm to Avoid Energy Holes in Wireless Sensor Networks. Proceedings of 8th Asia-Pacific Symposium on Information and Telecommunication Technologies, Kuching, Malaysia, 2010, p. 15–18.

. Ishmanov, F.; Malik, A.S.; Kim, A.S. Energy consumption balancing (ECB) issues and mechanisms in Wireless Sensor Networks (WSNs): A comprehensive overview. Eurosip Transaction on Telecommunication, 2011,22, p.151–167.

. Karl, H.; Willig, A. Protocols and architectures for wireless sensor network. A John Wiley and Sons, Ltd, Publication, 2005.

. Wang, P.; Dui, R.; Akyildiz, I. Collaborative data compression using clustered source coding for wireless multimedia sensor networks. Proceeding of IEEE Conference on Computer Communications (INFOCOM), San Diego, CA, USA, 2010, p. 1713–1723.

. Tripathi, R. K.; Singh, Y.N.; Verma, N.K. Two-tiered wireless sensor networks-base station optimal positioning case study. IET Wireless Sensor Systems, 2012, 2(4),p. 351–360.

. Mille, M. J.; Vaidya, N. H. A MAC protocol to reduce sensor network energy consumption using a wakeup radio. IEEE Transaction on Mobile Computing, 2005, 4(3), p.228–242.

. Zhu, J.; Papavassiliou, S. On the energy-efficient organization and the lifetime of multi-hop sensor networks,” IEEE Communication Letter. 2003, 7(110, p. 537–539.

. Medagliani, P.; Martalò, M.; Ferrari, G. Clustered Zigbee networks with data fusion: Characterization and performance analysis. Journal of Ad Hoc Networks, 2011, 9(7),p. 1083-1103.

. Elfes, A. Occupancy grids: a stochastic spatial representation the active robot perception. Autonomous Mobile Robots: Perception, Mapping and Navigation, 1991, p. 60-70.

. Hossain, A.; Chakrabarti, S.; Biswas, P.K. Impact of Sensing Model on Wireless Sensor Network Coverage. IET wireless sensor system, 2012, 2(3),p. 272-28.

. Gu,Y.; Wu, Q.; Rao, N. S. V. Optimizing Cluster Heads for Energy Efficiency in Large-Scale Heterogeneous Wireless Sensor Networks. International Journal of Distributed Sensor Networks, 2010.

. Dabirmoghaddam, A.; Ghaderi, M.; Williamson, C. Cluster-based correlated data gathering in wireless sensor network. Proceeding of IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems , Miami Beach, USA, 2010, p. 163–171.

. Tuah,N.; Ismail, M.; Jumari, K. Energy efficient algorithm for heterogeneous wireless sensor network. IEEE International Conference on Control System, Computing and Engineering, 2011, p. 92-96.

. Heinzelman, W. R.; Chandrakasan, A.; Balakrishnan, H. an application-specific protocol architecture for wireless microsensor networks. IEEE Transaction on Wireless Communication, 2002, 1(4),p. 660– 670.

. Depedri, A.; Zanella, R.; Verdone, R. An energy efficient protocol for wireless sensor networks. Autonomous Intelligent Networks and System, Menlo Park, 2003.

. Chen, P.; Dea, B. O.; Callaway, E. Energy Efficient System Design with Optimum Transmission Range for Wireless Ad Hoc Networks. IEEE International Conference on Communication, 2002, 2,p.945-952.

. Mhatre, V; Rosenberg, C. Design guidelines for wireless sensor networks: communication, clustering and aggregation. Journal of Ad Hoc Network Journal, 2004, 2(1),p. 45–63.

. Smaragdakis, G.; Matta, I.; Bestavros, A. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks. Proceeding of the International Workshop on SANPA, 2004.

. Pattem, S.; Krishnamachari, B.; Govindan, R. The Impact of Spatial Correlation on Routing with Compression in Wireless Sensor Networks. ACM/IEEE IPSN, Berkeley, US, 2004, p.28-35.

. Kim, H.; Kim, S.W.; Lee, S.B.; Son, B. Estimation of the optimal number of cluster-heads in sensor network. Proceeding of KES, Melbourne, Australia, 2005, 3,p. 87–94.

. Comeau, F.; Sivakumar, S.C.; Robertson, W.; Phillips W.J. Energy conserving architectures and algorithms for wireless sensor networks. 39th Hawaii International Conference on System Sciences, 2006, p.236c.

. Chen, H.; Megerian, S. Cluster Sizing and Head Selection for Efficient Data Aggregation and Routing in Sensor Networks. Proceeding of IEEE WCNC, 2006, p. 2318–2323.

. Vlajic, N.; Xia, D.Wireless sensor networks: To cluster or not to cluster. Proceedings of International Symposium on a World of Wireless, Mobile and Multimedia, 2006, 9, p. – 268.

. Xia, D.; Vlagie, X. Near optimal node clustering in wireless sensor networks for environment monitoring. 21st international conference and applications, 2007,p. 632-641.

. Yang, H.; Sikdar, B. Optimal Cluster Head Selection in the LEACH Architecture. Proceeding of IPCCC, 2007, p. 93-100.

. Wang, H.; Yu, X.; Kong, D.; Yan, X.; Ma, X. Route Protocol of Wireless Sensor Networks Based on Dynamic Setting Cluster. Proceedings of the International Conference on Information Acquisition, Jeju, Korea, 2007, p. 112–117.

. Yu, X.; Xu, L.; Wang, H. A Protocol Design of Water in a Remote Measure Based On Mobile Communication Networks and Wireless Sensor Networks. Automation in Water Resources and Hydrology, 2006, 1, p. 6-10.

. Wang, Y.; Ma, X.; Xu, L.The designing model o effectively, wireless sensor network data link layer based on information fusion strategy. Computer Engineering, 2005, 31 23,p. 6-10.

. Selvakennedy, S.; Sinnappan, S.; Shang, Y. A biologically-inspired clustering protocol for wireless sensor networks. Journal of Computer Communications, 2007, 30, 14–15, p. 2786–2801.

. Kumar, D.; Aseri, T.C.; Patel, R.B. EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks. Journal of Computer Communications, 2009, 32, 4,p.662-667.

. Chan,T.J.; Chen, M.C.; Huang, Y.F.; Lin, J.Y.; Chen, T.R. Optimal Cluster Number Selection in Ad-hoc Wireless Sensor Networks. WSEAS Transaction on Communication, 2008, 7, 8, 837-846.

. Chen, H.; Tse, C.K.; Feng, J. Minimizing effective energy consumption in multi-cluster sensor networks for source extraction. IEEE Transactions on Wireless Communications, 2009, 8(3),p. 1480—1489.

. Raghuvanshi, S.; Tiwari, S.; Tripathi, R.; Kishor, N. G K Clustering Approach to Determine Optimal Number of Clusters for Wireless Sensor Networks. Fifth IEEE Conference on Wireless Communication and Sensor network, 2009, p.1-5.

. Halgamuge, M. N.; Zukerman, M.; Ramamohanarao, K; Vu, H. L. An estimation of sensor energy consumption. Progress In Electromagnetics Research B, 2009, p.12259-295.

. Li, H.; Shunjie, X.; Shurong, L.; Weixia, Z.; Zheng, Z. Novel Method for Optimal Number of Cluster Heads in LEACH. WASE International Conference on Information Engineering, 2009, p. 302-309.

. Wang, L. C.; Wang, C. W.; Liu, C. M. Optimal number of Clusters in Dense Wireless Sensor Networks: A Cross-Layer Approach. IEEE Transactions on Vehicular Technology, 2009, 58(2), p.966-976.

. Kumar, D.; Aseri, T. S.; Patel, R. B. EECHE: Energy efficient cluster head election protocol for heterogeneous Wireless Sensor Networks. Proceedings of ACM International Conference on Computing, Communication and Control, Bandra, Mumbai, India, 2009, p. 75-80.

. Li, H.; Shunjie, X.; Guoqiang, W.; Zhe, J. Uneven Virtual Grid-Based Clustering Routing Protocol for Wireless Sensor Networks. Proceedings of IEEE International Conference on Information and Automation, Zhuhai/Macau, China, 2009, p.397-402.

. Wang, Y.; Li, C.; Zuo, Y. A selection model for optimal fuzzy clustering algorithm and number of clusters based on competitive comprehensive fuzzy evaluation. IEEE Transaction on Fuzzy System, 2009, 17(3),568–577.

. Förster; Förster, A.; Murphy, A. L. Optimal cluster sizes for wireless sensor networks: an experimental analysis. Ad-Hoc Networks, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 2010, 28,p. 49–63.

. Li, W.; Martins, P.; Shen, L. Determination method of optimal number of clusters for clustered wireless sensor networks. Journal Wireless Communications and Mobile Computing, 2012, 12(2),p. 158 – 168.

. Ahmed, A.A.; Shi, H.; Shang, Y. A survey on network protocols for wireless sensor networks. International Conference on Information Technology: Research and Education, 2003, p. 301-305.

. Raghuvanshi, A. S.; Tiwari, S.; Tripathi, R.; Kishore, N. Optimal number of clusters in wireless sensor networks: a FCM approach. International Journal of Sensor Networks, 2012, 12(1),p.16-24.

. Yang, K.; Wu, Y.; Zhou, H. Research of optimal energy consumption model in wirelss sensor network. 2nd International Conference on Computer Engineering and Technology Chengdu, China, 2010, p. V7-421 - V7-424.

. Navid, A.; Alireza, V.; Wenyao, X.; Mario, G.; Majid, S. Cluster size optimization in sensor networks with decentralized cluster-based protocols. Journal of Computer Communications, 2012, 35(2),p. 207–220.

. Chen, B.; Zhang, Y.; Li, Y.; Hao, X.; Fang, Y. A Clustering Algorithm of Cluster-head Optimization for Wireless Sensor Networks Based on Energy. Journal of Information & Computational Science, 2011,8(11),p. 2129–2136.

. Tandon, R. Determination of Optimal Number of Clusters in Wireless Sensor Networks. International Journal of Computer Networks & Communications (IJCNC), 2012, 4(4),p. 235-249.

. Tuah, N.; Ismail, M.; Jumari, K. Evaluation of Optimal Cluster Size in Heterogeneous Energy Wireless Sensor Network. 1st IEEE International Symposium on Telecommunication Technologies, 2012, p.124 – 130.

. Tripathi, R.K.; Singh, Y.N.; Verma, N.K. Clustering algorithms for non-uniformly distributed nodes in WSNs. Electronics Letters, 2013, 49, 4.

. Dabirmoghaddam, A.; Ghaderi M.; Williamson, C. On the optimal randomized clustering in distributed sensor networks. Journal of computer network, 2014, 59, 11,p.17–32.

. Katiyar, V.; Chand, N.; Soni, S. A Survey on clustering algorithms for Heterogeneous Wireless Sensor Networks. International Journal of Advanced Networking and Applications, 2011, 2(4),p. 745-754.

. Sheikhpour, R.; Jabbehdari, S.; Khadem-Zadeh, A. Comparison of Energy Efficient Clustering Protocols in Heterogeneous Wireless Sensor Networks. International Journal of Advanced Science and Technology, 2011, Vol. 36, p.27-40.

. Mhatre, V.; Rosenberg, C. Homogeneous Vs Heterogeneous Clustered Networks: A Comparative Study . Proceedings of IEEE ICC, 2004, p.1-6.

. Shih, E.; Cho, S.; Lee, F. S. B.; Calhoun, H.; Chandrakasan, A. Design Considerations for Energy-Efficient Radios in Wireless Micro-sensor Networks. Journal of VLSI Signal Process, 2004, 37(1),p. 77–94.

. Khan, S.; Ahmad, A. Cluster centre initialization algorithm for Kmeans clustering. Pattern Recognitation Letter, 2004, 25(1),p. 1293–1302.

. Redmond, S.; Heneghan, C. A method for initializing the K-means clustering algorithm using kd-trees. Pattern Recognit. Lett., 2007, 28(1), p.965–973

. Huang, H.; Yao, D.; Shen, J.; Ma, K.; Liu, H. Multi-weight based clustering algorithm for wireless sensor networks. Journal of Electronics & Information Technology, 2008,p. 1489-1492.

. Stein, E. M.; Shakarchi, R. Real Analysis: Measure Theory, Integration, and Hilbert Spaces. NJ: Princeton Univ. Press, 2005.

. Kumar, V.; Dhok, S.B.; Tripathi,R.; Tiwari, S. “Cluster Size Optimization in Gaussian Distributed Wireless Sensor Networks” International Journal of Engineering and Technology (IJET),2014, 6 (3),p. 1581-1592.

. Kumar, V.; and Tiwari, S. “Routing in IPv6 over low-power wireless personal networks (6LowPAN): A survey” Journal of computer Networks and Communication, 2012.

. Kumar, V.; Raghuvansi, A.S.; and Tiwari, S. “Performance study of beacon- enabled IEEE 802.15.4 standards in WSNs with Clustering” International conference on power control and embedded system,2010, p. 1-5.

. Kumar, V.; and Tiwari, S. “Performance of Routing Protocols for Beacon-Enabled IEEE 802.15.4 WSNs with Different Duty Cycle”, International Conference on Devices and Communications, 2011, p.1-5.

. Kumar, V.; Raghuvansi, A.S.; and Tiwari, S. “LEACH and Its Derivatives in WSN: A Survey” International Conference on Communication and computational intelligence, 2010/11, p.81-86.

. Kumar, V.; Jain, S.; and Tiwari, S. “Impact of Node Density and Mobility on Scalable Routing Protocols in Mobile AdHoc Networks”Special Issue of International Journal of Computer Applications (0975 8887) on Communication Security, No.5 Mar.2012

. Kumar, V.; Jain, S.; and Tiwari, S. “ Performance of Routing Protocols in MANETs with Node Density and Mobility using Omni and Directional Antenna”Special Issue of International Journal of Computer Applications (0975 -8887) on Wireless Communication and Mobile Networks, No.11., ww.ijcaonline.org, Jan.2012,p.51-55.

. Kumar, V.; Dhok, S.B.; Tripathi,R.; Tiwari, S. “A Review Study of Hierarchical Clustering Algorithms for Wireless Sensor Networks” IJCSI International Journal of Computer Science Issues,2014, 11(3), p.92-101.

Published
2014-11-03