Abstract
In wireless cluster networks with a single non mobile sink, finding the optimal cluster assignment is a non-trivial problem. The inherently non centralized nature of wireless sensor networks poses a problem as majority of the learning algorithms are centralized. It is also desirable that single routing algorithm be applicable regardless of whether the sensor network is a dense single-hop network or a sparse multi-hop network. In this paper we present the two phased routing incorporating distributed genetic algorithm and gradient based heuristic (TRIGGER) as an attempt to solve these problems. In the first phase of TRIGGER a distributed (island model) genetic algorithm based clustering is employed to find a spatially optimal cluster assignment. In the second phase a gradient based routing forwards the already aggregated data to the sink. We discuss the rationale behind the two phased nature of TRIGGER. We demonstrate the effectiveness of TRIGGER with extensive simulations and discuss the results.
Similar content being viewed by others
References
Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd annual Hawaii international conference on system sciences, 2000 (pp. 1–10). IEEE.
Yi, S., Heo, J., Cho, Y., & Hong, J. (2007). PEACH: Power-efficient and adaptive clustering hierarchy protocol for wireless sensor networks. Computer Communications, 30(14), 2842.
Younis, O., & Fahmy, S. (2004). HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Transactions on Mobile Computing, 3(4), 366.
Aslam, N., Phillips, W., Robertson, W., & Sivakumar, S. (2011). A multi-criterion optimization technique for energy efficient cluster formation in wireless sensor networks. Information Fusion, 12(3), 202.
Ye, M., Li, C., Chen, G., & Wu, J. (2005). EECS: An energy efficient clustering scheme in wireless sensor networks. In 24th IEEE international conference on performance, computing, and communications, 2005, IPCCC 2005 (pp. 535–540) IEEE.
Abdulla, A. E., Nishiyama, H., Yang, J., Ansari, N., & Kato, N. (2012). Hymn: A novel hybrid multi-hop routing algorithm to improve the longevity of wsns. IEEE Transactions on Wireless Communications, 11(7), 2531.
Maulik, U., & Bandyopadhyay, S. (2000). Genetic algorithm-based clustering technique. Pattern Recognition, 33(9), 1455.
Sen, S., Narasimhan, S., & Deb, K. (1998). Sensor network design of linear processes using genetic algorithms. Computers & Chemical Engineering, 22(3), 385.
Jin, S., Zhou, M., & Wu, A.S. (2003). Sensor network optimization using a genetic algorithm. In Proceedings of the 7th world multiconference on systemics, cybernetics and informatics (pp. 109–116).
Hussain, S., Matin, A. W., & Islam, O. (2007). Genetic algorithm for hierarchical wireless sensor networks. Journal of Networks, 2(5), 87.
Hussain, S., Matin, A. W., & Islam, O. (2007). Genetic algorithm for energy efficient clusters in wireless sensor networks. In Fourth international conference on information technology, 2007. ITNG'07 (pp. 147–154). IEEE.
Hussain, S., & Islam, O. (2009). Genetic algorithm for energy-efficient trees in wireless sensor networks. In Advanced intelligent environments (pp. 139–173). Springer US.
Ferentinos, K. P., & Tsiligiridis, T. A. (2007). Adaptive design optimization of wireless sensor networks using genetic algorithms. Computer Networks, 51(4), 1031.
Chakraborty, A., Mitra, S. K., & Naskar, M. K. (2011). A Genetic algorithm inspired routing protocol for wireless sensor networks. International Journal of Computational Intelligence Theory and Practice, 6(1), 1.
Lindsey, S., & Raghavendra, C.S. (2002). PEGASIS: Power-efficient gathering in sensor information systems. In IEEE aerospace conference proceedings, 2002 (Vol. 3, pp. 3–1125). IEEE.
Gupta, S. K., & Jana, P. K. (2015). Energy efficient clustering and routing algorithms for wireless sensor networks: GA based approach. Wireless Personal Communications, 83(3), 2403.
Song, Y., Gui, C., Lu, X., Chen, H., & Sun, B. (2015). A genetic algorithm for energy-efficient based multipath routing in wireless sensor networks. Wireless Personal Communications, 85(4), 2055.
Whitley, D., Rana, S., & Heckendorn, R.B. (1997). Island model genetic algorithms and linearly separable problems. In AISB International Workshop on Evolutionary Computing (pp. 109–125). Berlin, Heidelberg: Springer.
McCallum, A., Nigam, K., & Ungar, L. H. (2000) Efficient clustering of high-dimensional data sets with application to reference matching. In Proceedings of the sixth ACM SIGKDD international conference on knowledge discovery and data mining (pp. 169–178). ACM.
Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558.
Bhattacharyya, P., & Chakrabarti, B. K. (2008). The mean distance to the nth neighbour in a uniform distribution of random points: An application of probability theory. European Journal of Physics, 29(3), 639.
Wadaa, A., Olariu, S., Wilson, L., Jones, K., & Xu, Q. (2003). On training a sensor network. In Proceedings of the international parallel and distributed processing symposium, 2003 (issue 8). IEEE.
Olariu, S., & Stojmenovic, I. (2006). Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting. In INFOCOM (pp. 1–12).
Davies, D. L., & Bouldin, D. W. (1979). A cluster separation measure. In IEEE transactions on pattern analysis and machine intelligence (issue 2, p. 224).
Heinzelman, W. B., Chandrakasan, A. P., & Balakrishnan, H. (2002). An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4), 660.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Banerjee, S., Chowdhury, C., Chattopadhyay, S. et al. Two Phased Routing Protocol Incorporating Distributed Genetic Algorithm and Gradient Based Heuristic in Clustered WSN. Wireless Pers Commun 97, 5401–5425 (2017). https://doi.org/10.1007/s11277-017-4786-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11277-017-4786-y