Optimisation of LEACH protocol based on a game theory clustering approach for wireless sensor networks

Optimisation of LEACH protocol based on a game theory clustering approach for wireless sensor networks

• 1.
  Indonesian Journal ofElectrical Engineering and Computer Science Vol. 21, No. 2, February 2021, pp. 938~944 ISSN: 2502-4752, DOI: 10.11591/ijeecs.v21.i2.pp938-944  938 Journal homepage: http://ijeecs.iaescore.com Optimisation of LEACH protocol based on a game theory clustering approach for wireless sensor networks Yassine Oukessou1 , Mohamed Baslam2 , Mohamed Oukessou3 1,3 Applied Mathematics and Scientific Computing Laboratory, Faculty of Sciences and Technics, Sultan Moulay Slimane University, Beni Mellal, Morocco 2 Information Processing and Decision Support Laboratory, Faculty of Sciences and Technics, Sultan Moulay Slimane University, Beni-Mellal, Morocco Article Info ABSTRACT Article history: Received Jun 22, 2020 Revised Aug 23, 2020 Accepted Sep 7, 2020 The wireless sensor network clustering routing mechanism is the best multi- hop algorithm used to aggregate data from sensors to the base station. Therefore the elected nodes refuse to be a clusters heads CH and have a selfish and non cooperative behaviours in each group cluster. All that due to the high electric energy consumption, and especially that the most existing sensors are powered by batteries. In this paper, we will analyse the selfishness behaviour by using the most knowing mathematical model Game theory to improve the interaction decision making for the CH selection, and make a comparison with LEACH protocol. Keywords: Cluster head Game theory LEACH Nash equilibrium WSN This is an open access article under the CC BY-SA license. Corresponding Author: Yassine Oukessou Applied Mathematics and Scientific Computing Laboratory Faculty of Sciences and Technics Sultan Moulay Slimane University, Beni Mellal, Morocco Email: Oukyassine@gmail.com 1. INTRODUCTION Wireless sensor network (WSN) [1, 2] have today a wide civil and military applications, such as industrial applications, transportation and logistics, agriculture and animal tracking, smart buildings, smart grids, health care, security and surveillance, and it refers to a network of sensors used to monitor and record environmental physical conditions and aggregate the collected data to a central location. The sensor nodes have four main functions: sensing, processing, communication and power units. The sensing module can measures via a probe the physical variations then send the collected data to the processing system that contains a micro controller. After that the communication system via a radio module: transmitter/receiver antennas and network processing unit will relay the processed data to a base station for a further use. Thus, the data transfer can be done directly if the both units, node and base station are in the same communication range; if not a multi-hop routing protocol [3-6] will be used to enhance the delivery of the data packets. Finally the power management subsystem is responsible of monitoring of the real time residual battery energy then will be reported via the communication system to the central unit or broadcasted the the other network nodes. Unlike the old classic networks, the WSN motes are deployed in an unattended environment, with limited power capabilities with small or irreplaceable batteries. Thus the necessity of a new energy efficieny routing algorithms are mandatory in case if these nodes are cooperatives.
• 2.
  Indonesian J ElecEng & Comp Sci ISSN: 2502-4752  Optimisation of LEACH protocol based on a game theory clustering approach for… (Yassine Oukessou) 939 The wireless sensor network clustering consequentely is the best routing mechanism aiming reducing the throughput load and by the way enhancing sensors batteries consumption, especially in low power wide area networks LPWAN [7-9] technologies. The routing technique is done by dividing the network nodes into small groups forming the clusters and then each cluster elect a cluster head (CH) for collecting data and send it back to the getaway-sink. A various approaches are proposed based on LEACH routing protocol [10-17]. LEACH is a hierarchical routing protocol, iterated by rounds. When the clusters are organized, the round begins with a set-up phase, and then followed by a steady-state phase when data transfers to the sink. During the set-up stage, every node chooses whether or not to turn into a CH, in view of a determined threshold and a produced random number m somewhere in the range of 0 and 1. if m is less than T(n) then the node become cluster head for the current round, and advertise its status to the other nodes into the cluster. Else the nodes pick the accessible adjacent CH. The threshold value is expressed as follows (1): { ( . /) (1) Where G is the set of nodes not selected in the last 1/p rounds as cluster head and r is the round number. Once the clustering head operations are done. The steady-state phase starts by each CH arrange a TDMA frame by allocating a time slot to each member node, then the collecting and processing of the returned data will be begin and in the last stage will be transferred to the sink, as it is shown in Figure 1. Figure 1. Architecture of LEACH protocol In the other hand, the cluster heads consume more energy for relaying data; therefore, some nodes have a selfishness behavior and refuse to be CH for saving their energies and by the way forming a non- cooperative model. Recently the Game Theory [18] has been used for analyzing the selfishness phenomenon of sensors and propose a new clustering mechanism, clustered routing for selfish sensors (CROSS) [19], where each mote is presented as a player capable of hearing all other players messages and knowing their numbers. Each mote finds then an equilibrium value based on the range of players, which determines whether or not a player becomes a CH. In this paper we represent the game theory model and propose the game algorithm based on Nash Equilibrium for designing the non-cooperative environment and optimize the selfishness issue in Section 2. The simulation and performance results analysis comparison are detailed in Section 3. The Section 4 contains the assessment of the implemented algorithm and the representation of the future work.
• 3.
   ISSN: 2502-4752 IndonesianJ Elec Eng & Comp Sci, Vol. 21, No. 2, February 2021 : 938 - 944 940 2. PROPOSED GAME THEORY ALGORITHM 2.1. Game model representation As we have seen above, in the selfishness environment the nodes are refusing to be CH in order to save their energy. So we will introduce our model for resolving this phenomenon as follows: First, we schematize the CH declaration as a game, and then we assume a non-cooperative game model, where each mote hope maximizes its gain by choosing a strategy depending to others motes choices. By this way we define the game as * + where and N is a set of motes; the strategy space: * + where ACH is Announcing cluster head and RCH is Refuse to be cluster head; is the utility of the node . We define the utility function as follow (2): { (2) Where g is the benefit gets by the mote when it refuse to be cluster head and other one is be. c is the cost a node pays when it select to be a cluster head. In [20], the ( ) parameter cost is depending to the number n of nodes in the cluster and the distance d between the CH and sink. For the rest of the paper we consider that c is constant, and g is the residual energy on the node, which is defined in [21] as (3): (3) Where and are the initial energy and the energy drained after each round of the node respectively. We assume that a mixed strategy Nash Equilibrium can be found to allow each player to choose his strategy randomly following a probability distribution. Let's set p as the probability of a node announcing a CH, and then the chance of refusing will be the . We consider the following utility values if we have N node players and at least one node declares CH: { ( ( ) ) (4) As we described before, the game follows a distribution probability so a mixed strategy Nash Equilibrium will be concluded by the expression: = y solving it we get the below expression (5), (6): = ( ( ) ) (5) We have so: . / (6) 2.2. IGTLEACH algorithm Authors in [22] counseled a progressive selection technique wherein the network was divided into areas and a temporary choice distribution technique changed into used. The area nodes j decide first, then the region nodes decide right now afterwards, in order that the vicinity nodes can bear in mind the presence of cluster heads from the precedent region and forestall seeking to be a cluster head every time there's a close neighbour. In our improved game theory LEACH algorithm IGTLEACH, we propose another progressive regions division technique for cluster forming; where the nodes are uniformly distributed in a rectangle, as shown in Figure 2.
• 4.
  Indonesian J ElecEng & Comp Sci ISSN: 2502-4752  Optimisation of LEACH protocol based on a game theory clustering approach for… (Yassine Oukessou) 941 Figure 2. Cells network subdivision map We start by dividing the rectangle into cells. Let us make W and L the width and length of the rectangle, N is the number of sensor nodes, and is the desired percentage of cluster heads CH. We set then: (√ ) (7) Where is the number of segments in each side of the square, let us make: { (8) We set the zone as cell 0, the zone as the union of the cell 0 and cell 1, so we make (9): ⋃ , - (9) The selection procedure will use the same concept as LEACH. In the first stage, each mote collects its corresponding cluster data by performing the neighbor relationship process; by sending the HELLO packets and receiving the ACK messages that contains the residual power of all the cluster nodes [23]. After that each node generates a random number between 0 and 1, and if it is less than a new threshold , it will announce itself as CH. We assume that each node calculate the new threshold in its set up phase [24] as follow (10): ( ( )) (10) Where G is the set of nodes selected in the last round as cluster heads, and is the probability found by resolving the Mixed Strategy Nash Equilibrium. As we have seen in the cluster forming part that use our zone/cell division technique. The process selection in each round will progressively start from zone k to zone , and during that time the motes of the zone k play the game and take in consideration the strategies selected by the previous zone k-1. 3. PERFOFORMANCE SIMULATION RESULTS ANALYSIS Exploiting the MATLAB Simulator [25], we have made a comparison between LEACH protocol and our Improved Game Theory LEACH protocol. So in the first simulation, we check the entire energy drained by all the nodes during a period of the time. The second simulation is the lifetime of the sensors, related to the dissipation power previously evaluated. In the last one, we have evaluated the throughput generated by all the nodes and distributed to the single access gateway (sink). 3.1. Network configuration We assume that the sink have always enough power, and located in the center of the rectangle, and all the motes are fixed in their positions locations, as it is shown in Figure 3. By the way we set some network parameters in Table 1.
• 5.
   ISSN: 2502-4752 IndonesianJ Elec Eng & Comp Sci, Vol. 21, No. 2, February 2021 : 938 - 944 942 Figure 3. CH selection simulation in progress Table 1. Network simulation parameters Parameter Value Number of nodes 100 Network size 1000m×1000m Initial energy of each node 2J Simulation time 1000s Desired percentage of cluster heads 0.1 Packet size for cluster head 6400bits Packet size for normal node per round 200bits 3.2. Performance results In the first simulation test, Figure 4 shows us a significant gap in total energy dissipated starting from about 250 seconds between our improved game theory LEACH algorithm IGTLEACH and LEACH protocol, thus allowing more motes that are alive by keeping their lifetime uniformly decreasing in time Figure 5. The last simulation result Figure 6 shows us a stable uniform total throughput of our IGTLEACH algorithm, which is explained by the resistance to death done by the motes. In other case, if we increase the number of nodes to 400 motes we get more lifetime efficiency gap Figure 7. This means that our algorithm is more efficient in terms of nodes density. Figure 4. Comparison of network energy consumptions of LEACH and IGTLEACH
• 6.
  Indonesian J ElecEng & Comp Sci ISSN: 2502-4752  Optimisation of LEACH protocol based on a game theory clustering approach for… (Yassine Oukessou) 943 Figure 5. Comparison of network life spans of LEACH and IGTLEACH Figure 6. Comparison of network throughputs of LEACH and IGTLEACH Figure 7. Comparison of network life spans of LEACH and IGTLEACH with 400 nodes
• 7.
   ISSN: 2502-4752 IndonesianJ Elec Eng & Comp Sci, Vol. 21, No. 2, February 2021 : 938 - 944 944 4. CONCLUSION Despite that the clustering is the best technique to avoid the non-distribution of CH selection in the wireless sensor networks, the selfishness behavior and the energy storage challenge of nodes affect its efficiency. In this work we have proposed a new clustering game selection process of CH, where the network energy drained slowly than the famous LEACH mechanism, consequently better performances shown in simulation comparisons. In our future work, we plan to more optimize the equilibrium equation without using the subdivision technique, because the clustering forming method has a CPU processor stress impact on the nodes, which increase their power consumption. So for that, we will introduce a new energy parameters, and also not considering the cost as constant as we have seen in the section 3 that is depend to the distance from the sink and the number of nodes in the cluster. REFERENCES [1] M. A. Matin and M. M. Islam, “Overview of wireless sensor network,” in Wireless Sensor Networks-Technology and Protocols, InTech, 2012. [2] D.-S. Kim and H. Tran-Dang, “An overview on wireless sensor networks,” in Computer Communications and Networks, Cham : Springer International Publishing, pp. 101-113, 2019. [3] A. Guermazi, A. Belghith, and M. Abid, “Multi-hop routing for distributed clustering protocols in wide wireless sensor networks,” in 2015 IEEE/ACS 12th International Conference of Computer Systems and Applications (AICCSA), pp. 1-6, 2015. [4] S. Rani and S. H. Ahmed, Multi-hop Routing in Wireless Sensor Networks, Singapore : Springer Singapore, 2016. [5] A. Vinitha, M. S. S. Rukmini, and Dhirajsunehra, “Secure and energy aware multi-hop routing protocol in WSN using Taylor-based hybrid optimization algorithm,” J. King Saud Univ. - Comput. Inf. Sci., 2019. [6] M. N. Jambli, et al, “Evaluation of clustering and multi-hop routing protocols in Mobile Ad-hoc Sensor Networks,” in 2015 9th International Conference on IT in Asia (CITA), pp. 1-5, 2015. [7] O. Yassine, M. Baslam, and M. Oukessou, “Lpwan ieee 802.11ah and lorawan capacity simulation analysis comparison using ns-3,” in 2018 4th International Conference on Optimization and Applications (ICOA), pp. 1-4, 2018. [8] K. Mekki, E. Bajic, F. Chaxel, and F. Meyer, “A comparative study of LPWAN technologies for large-scale IoT deployment,” ICT Express, vol. 5, no. 1, pp. 1-7, 2019. [9] J. Rubio-Aparicio, F. Cerdan-Cartagena, J. Suardiaz-Muro, and J. Ybarra-Moreno, “Design and implementation of a mixed IoT LPWAN network architecture,” Sensors (Basel), vol. 19, no. 3, 2019. [10] Y. Liu, Q. Wu, T. Zhao, Y. Tie, F. Bai, and M. Jin, “An improved energy-efficient routing protocol for wireless sensor networks,” Sensors (Basel), vol. 19, no. 20, 2019. [11] A. Iqbal, M. Akbar, N. Javaid, S. Bouk, M. Ilahi, and R. Khan, “Advanced LEACH: A static clustering-based heteroneous routing protocol for WSNs,” ArXiv, 2013. [12] L. Tang and S. Liu, “Improvement on LEACH routing algorithm for wireless sensor networks,” in 2011 International Conference on Internet Computing and Information Services, pp. 199-202, 2011. [13] W. Huang, Y. Ling, and W. Zhou, “An improved LEACH routing algorithm for wireless sensor network,” Int. J. Wirel. Inf. Netw., vol. 25, no. 3, pp. 323-331, 2018. [14] A. O. Abu Salem and N. Shudifat, “Enhanced LEACH protocol for increasing a lifetime of WSNs,” Pers. Ubiquitous Comput., vol. 23, no. 5-6, pp. 901-907, 2019. [15] Zhao, Jianli & YANG, Lirong, "LEACH-A: An adaptive method for improving LEACH protocol," Sensors and Transducers, vol. 162, no. 1, pp. 136-140, 2014. [16] Z. Zhao, G. Li, and M. Xu, “An improved algorithm based on LEACH routing protocol,” 2019 IEEE 19th International Conference on Communication Technology (ICCT), Xi'an, China, 2019, pp. 1248-1251, 2019. [17] M. Amru, M. Jabirullah, and A. C. Krishna, “An improved network coding based LEACH protocol for energy effectiveness in wireless sensor networks,” in Intelligent Systems Reference Library, Cham: Springer International Publishing, pp. 125-136, 2020. [18] C. Hilbe, A. Traulsen, and K. Sigmund, “Partners or rivals? Strategies for the iterated prisoner’s dilemma,” Games Econ. Behav., vol. 92, pp. 41-52, 2015. [19] H.-Y. Shi, W.-L. Wang, N.-M. Kwok, and S.-Y. Chen, “Game theory for wireless sensor networks: A survey,” Sensors, vol. 12, no. 7, pp. 9055-9097, 2012. [20] Q. Liu and M. Liu, “Energy-efficient clustering algorithm based on game theory for wireless sensor networks,” Int. J. Distrib. Sens. Netw., vol. 13, no. 11, p. 155014771774370, 2017. [21] Z. Xu, Y. Yin, X. Chen, and J. Wang, “A game-theory based clustering approach for wireless sensor networks,” NGCIT 2013, ASTL, pp. 58-66, 2013. [22] L. SHEN and X. SHI, "A location based clustering algorithm for wireless sensor networks," International journal of Intelligent Control and Systems, vol. 13, no. 3, pp. 208-213, 2008 [23] S. Magotra and K. Kumar, “Detection of HELLO flood attack on LEACH protocol,” in 2014 IEEE International Advance Computing Conference (IACC), pp. 193-198, 2014. [24] E. F. Youssef, F. Mohammed, and E. Abedellah, “Improvement of leach routing algorithm based on the use of game theory,” in Proceedings of the International Conference on Internet of things and Cloud Computing - ICC ’16, pp. 1-5, 2016. [25] [Online]. Available: www.mathworks.com [Accesed: October 20, 2019]