Informatica 42 (2018) 245–251 245 Weighted Density Center Clustering Protocol for Wireless Sensor Networks Amira Slimani and Mohammed Redjimi Universite 20 Aout 1955- Faculte des sciences, Departement d’informatique- 21000 Skikda, Algeria E-mail: amira201015@hotmail.fr, redjimimed@yahoo.fr Djamel Slimani LIS laboratory, Department of electronics communication, University of Setif 1, 19000 Setif, Algeria E-mail: slimani.djamel@ymail.com Keywords: WSNs, LEACH, clustering, hierarchical protocols Received: December 29, 2016 Wireless sensor networks (WSNs) are often composed of a huge number of micro sensors. Low energy batteries and low processing capabilities characterize these tiny devices. The most critical challenge in these networks is the energy conservation. Hierarchical architecture with clustering of nodes is suitable for solution of many problems in the WSNs and has many benefits as energy efficiency, data aggregation and scalability. Low Energy Adaptive Clustering Hierarchy (LEACH) and its centralized version LEACH-C are the most popular hierarchical protocols. This paper proposes a cluster based routing protocol for WSNs, which is an improvement of LEACH-C. It is based on the weighted density center and energy criteria in the selection of the cluster heads (CH). The proposed protocol provides a significant increasing in network lifetime and more energy efficiency. The simulation results show that the proposed algorithm performs better than LEACH-C, Improved-LEACH and the Distance and Energy Aware LEACH (DE-LEACH) algorithms Povzetek: Prispevek predlaga protokol usmerjanja v brezžičnih senzorskih omrežjih (WSN) kot izboljšanje protokola LEACH-C. 1 Introduction With the recent advancements in wireless communication and miniaturization technology, micro sensors have become possible and popular techniques in military, health, security, commercial and industrial applications [1-4]. These tiny sensors, dispersed in huge numbers and autonomous manner, have a capacity to form self-configured networks [5-6]. In Wireless Sensor Network (WSN) applications. Useful collected data by sensors from environment are then sent to the base station. Therefore, the most challenge of these devices is the energy conservation since they operate with limited non-rechargeable batteries. In large scale WSNs, clustering technique is usually used to provide effectiveness in energy saving and topology stability [7- 8]. In cluster-based protocols, nodes are regrouped in clusters in where a leader node is elected as a cluster head (CH). Each CH receives the data transmitted by the other node members of the cluster and in turn transmits them in aggregated form to the base station. So, the CH must be efficiently selected, as it is required to organize activities in cluster. These activities deal with data aggregation, monitoring and scheduling the cluster communication to optimize the energy of sensors and extend the network lifetime [3]. Several protocols have been proposed in literature [9-20] to optimize the operation of sensors and raise the network efficiency. Among these research works, the hierarchical protocols based on network division into clusters and election of a cluster leaders according to metrics are the mostly considered. The Low Energy Adaptive Clustering Hierarchy (LEACH) is the first and the most popular hierarchical protocol, which operates on rounds. In each round, two principal operations are performed. The first; called setup phase, concerns the creation of clusters and the election of their leaders. The second deals with the data transmission to the base station by the CHs [10]. The Low Energy Adaptive Clustering Hierarchy centralized (LEACH-C) is the centralized version of LEACH that operates in rounds as in LEACH and each round is divided into two phases: setup and steady state. It provides the energy conservation efficiency particularly in setup phase where it takes into account the energy level of sensors in selection of CHs, which is not considered in LEACH [11]. After these two popular protocols, many other approaches have been proposed and adopted. Some of them are based on LEACH [12- 15]. The Mobile-LEACH (M-LEACH) [12] is a multi- hop version of LEACH, which uses a multi hop to send data to the base station. The Two Levels Low Energy Adaptive Clustering Hierarchy protocol (TL-LEACH) [13] uses two types of CHs: primary and secondary CH to ensure more reliability in the CH. The Improved- LEACH [14] routing communication protocol for wireless sensor network proposes a vice cluster head for 246 Informatica 42 (2018) 245–251 A. Slimani et al. each cluster during the communication process. The Distance and Energy Aware LEACH (DE-LEACH) [15] is an improved LEACH routing protocol for WSNs in where the network is divided into two parts according to the distance of sensors from the base station. In the other hand, several routing protocols based on fuzzy logic are proposed for the WSNs as Cluster Head Election mechanism using Fuzzy logic (CHEF) [16].This latter uses two fuzzy descriptors for CH election; the first is based on the residual energy and the second on the distance between nodes having the same radius r. This protocol operates on rounds. The Energy-aware Clustering Protocol using Fuzzy-logic (ECPF) [17] is another protocol based on fuzzy logic, which processes on three operations: initialization, processing and finalization. Other techniques are used for WSNs such as bio-inspired and heuristic-based algorithms. Among them are the Ant Colony Optimization (ACO), the Genetic Algorithms (GA) and the Particle Swarm Optimization (PSO). The ant colony optimization algorithms are among the most popular used techniques in the last few years. [18] Proposed an ACO, which uses a probabilistic approach to choose the best solutions. This approach is based on metrics and the most important one is the pheromone value, which is a variable that defines the quality of path. ’Ants’, in these protocols, are placed in each node transmitter. Many other protocols are proposed for WSNs and they have alternative objectives added to the energy as in [19] where its main goal is the network security. Scalable data coupled clustering for large-scale WSNs algorithm is proposed in [20] in order to improve and achieve high scalability of the network. To reduce the energy consumption and extend the lifetime of sensor network, many research works have proposed a multi-hop communication. However, in the multi-hop algorithms, the intermediate nodes routing cannot be avoided, which in turn may increase the energy consumption. In order to overcome this problem, the approach proposed in this paper considers a transmission mode in where the message is directly transmitted from the cluster members to the cluster head (CH). The CH election is based on the energy criteria and weighted density center (WDC) of cluster nodes. The WDC idea reduces significantly the communication distances among nodes. Consequently, the energy conservation is enhanced. This approach is inspired from LEACH-C protocol. However, when selection of CH is considered, the WDC algorithm chooses the nearest point to all nodes in the cluster and it is elected as cluster head. Then, the data transmission from the nodes of the cluster to the CH is carried out in a single hop and over a short distance. This mode of transmission avoids losses due to long node transmissions and reduces the number of paths and energy consumption in the WSN. The rest of this paper is organized as follows: section 2 describes the network model. Section 3 deals with the energy model. Section 4 presents a description of the proposed algorithm. Sections 5 and 6 present respectively the simulation results and the conclusion. 2 The network model The following properties are used to model a sensors region:  The sensor nodes and the base station are assumed stationary once they are deployed in the environment.  The base station is static, and its location is initially known.  Wireless sensor network includes homogeneous sensor nodes.  Initially, all sensor nodes have the same amount of energy.  The base station is not limited in terms of energy, memory and computing power.  The nodes are eligible to determine its current energy level and location information through GPS service.  All the sensor nodes are immobile and having fixed node identification.  Data aggregation is done at the CH node. The following figure (Figure 1) shows the initial network vision: 3 The energy model The energy consumption model, which is used in the proposed protocol, is presented figure 2. It is the same radio model, which is used in LEACH-C [10]. The transmitter dissipates energy for a transmission of k-bits data, which is given by equation 1 𝐸 𝑡𝑥 (𝑘 , 𝑑 ) = { 𝐸 𝑒𝑙𝑒𝑐 × 𝑘 + 𝐸 𝑎𝑚𝑝 × 𝑘 × 𝑑 2 , 𝑑 < 𝑑 0 𝐸 𝑒𝑙𝑒𝑐 × 𝑘 + 𝐸 𝑎𝑚 𝑝 × 𝑘 × 𝑑 4 , 𝑑 ≥ 𝑑 0 (1) Where 𝐸 𝑡𝑥 (𝑘 , 𝑑 ) : Transmitter dissipated energy 𝐸 𝑒𝑙𝑒𝑐 : Electronic devices energy 𝐸 𝑎𝑚𝑝 : Power amplifier d: Transmission distance d 0: is the threshold distance that depends on the environment. k: is the number of transmitted bits. Figure 1: Network Model. Weighted Density Center Clustering Protocol ... Informatica 42 (2018) 245–251 247 For receiving of 𝑘 -bits data by each sensor node, the receiver-dissipated energy 𝐸 𝑟𝑥 is given by equation 2 𝐸 𝑟𝑥 (𝑘 , 𝑑 ) = 𝐸 𝑒𝑙𝑒𝑐 × 𝑘 (2) 4 The proposed WDC-LEACH-C clustering protocol The proposed protocol called Weighted Density Center Clustering Protocol based on LEACH-C (WDC-LEACH- C) operates in several rounds; each round is divided into two phases. The first is the setup phase, which consists of the cluster formation, CHs election and the scheduling transmission of nodes in each cluster. The scheduling is created by using a Time Division Multiple Access (TDMA) protocol. The CHs election is based on metrics: initial energy, residual nodes energy and the distance’s criteria. This important latter parameter is managed by the WDC of nodes in the same cluster. Therefore, the message is directly transmitted from the cluster member’s to the cluster head (CH). The criteria of WDC is not considered in LEACH-C, Improved-LEACH and DE-LEACH. When the setup phase is completed, the second phase (steady state) begins by a data collecting, aggregation and transmission to the base station. WDC- LEACH-C follows a strategy of clustering in setup phase basing on the remaining energy of sensors, distances among nodes and a single hop communication. The proposed protocol minimizes the communication distance and the number of transmission routes and consequently reduces the energy consumption. Figure 3 shows a comparison between a multi-hop communication and a WDC single-hop communication in terms of paths. The proposed protocol is working as follows: Initially, after deployment of nodes in harsh environments, each sensor sends its information (local information and energy level) to the remote BS. Note that the periodicity of these initial packets is ignored in simulation time. After receiving this information, a division of network into equal regions is carried out to form balanced clusters in terms of nodes number. Once the clusters are formed, a CH should be chosen from each cluster. CH should be the node, which holds the highest energy and the closest to the cluster nodes. The selection of CH is done in the following manner: - Computing the average separation distance 𝑑 𝑎𝑣𝑔 (𝑖 ) from any node i to all nodes of the same cluster using the equation (3) 𝑑 𝑎𝑣𝑔 (𝑖 ) = 1 𝑛 ∑ 𝑑 𝑖𝑗 𝑛 𝑗 =1 𝑖 ≠𝑗 (3) Where 𝑑 𝑎𝑣𝑔 (𝑖 ) : is the average distance 𝑑 𝑖𝑗 : is the distance from the node i to the node j 𝑛 : is the total number of cluster nodes. - Choosing the node placed at the center of gravity of the cluster. We call it the weighted density center node (WDC) in equation (4) : 𝑑 𝑊𝐷𝐶 = min{𝑑 𝑎𝑣𝑔 (𝑖 ) } 𝑖 =1 𝑛 (4) - Selection of nearest nodes to WDC to constitute group G: this can be done by performing the following test { Init G=0; For (i=1…n) If 𝑑 𝑎𝑣𝑔 (𝑖 ) <𝑑 𝑇 ℎ𝑟𝑒𝑠 ℎ𝑜𝑙𝑑 then 𝐺 = 𝐺 + 1; End } Where 𝑑 𝑇 ℎ𝑟𝑒𝑠 ℎ𝑜𝑙𝑑 is approached by the following formula that selects the perfect group G in each cluster 𝑑 𝑇 ℎ𝑟𝑒𝑠 ℎ𝑜𝑙𝑑 = 𝑑 𝑊𝐷𝐶 + 1 𝑛 ∑ 𝑑 𝑎𝑣𝑔 (𝑖 ) 𝑛 𝑖 =1 2 (5) - Among a group G, selection of the most energized node to be the cluster head (CH). This is done in the following way: 1- Computation of the probability of the remaining energy for each node in a group G. 𝑃 𝑗 = 𝐸 𝑟𝑒𝑠𝑖𝑑𝑢𝑎𝑙 (𝑗 ) 𝐸 𝑖𝑛𝑖𝑡𝑖𝑎𝑙 (𝑗 ) 𝑗 ∈ 𝐺 (6) 2- Choosing the node among G that has a maximum energy. This can be done by (7) 𝐸 𝑚𝑎𝑥 = 𝑚𝑎𝑥 { 𝑃 𝑗 } 𝐺 𝑗 =1 (7) Figure 2: Radio energy model [10]. Figure 3: Number of paths in multi-hop and WDC single-hop communication. 248 Informatica 42 (2018) 245–251 A. Slimani et al. The CH is chosen to be the node j that has a maximum energy. The figures 4 and 5 depict the WDC operations and the CH election, and the figure 6 shows the general Flowchart of clustering and CHs election. Figure 4: WDC calculation. Figure 5: CH selection. No Yes Figure 6: Flowchart of the clusters formation and CHs election in WDC-LEACH-C. 5 Simulation and results In this section, the simulation process is carried out on WSNs with 100 nodes where the following parameters (Table 1) are used: In order to validate the performance of the proposed WDC-LEACH-C algorithm, a comparison with LEACH- C, Improved-LEACH (Impro-LEACH in figures) and DE-LEACH algorithms has been done. In this comparison, five important metrics are considered: 1- Network lifetime: the network lifetime can be defined by three ways FND (First Node Died): is also called stability period, this is the time interval between the start of simulation and the death of the first node. HLD (Half Node Died): is the time between the start of simulation and the time of death of the half of nodes. Start Send information of each node (X, Y, E) to the Base Station Division of network into zones Calculate the weighted density center WDC of each zone Select nearest nodes to the WDC Select among the group G a node that has more energy as CH Node i near to the WDC Ignore the node i Node belongs to G End Parameters Values Simulation area (100 m× 100 m) Network size 100 sensors BS Location (50,50) Initial Energy 2 joules Minimum Energy 0.001 joule Maximum duration of the simulation 3600 seconds Data packet size 25 Bytes Table 1: Simulation parameters. Weighted Density Center Clustering Protocol ... Informatica 42 (2018) 245–251 249 LND (Last Node Died): is the time between the start of simulation and the time of death of the last node. 2- Number of alive nodes per round: this will measure the number of alive nodes in each round. 3- Consume energy: represents the energy consumption of nodes over simulation rounds. The main objective of routing protocols is to save the energy of sensors because if the sensor node runs out of energy then it will be dead and its life will be over too, so energy is the key factor needed to be considered in WSNs. 4- The quantity of data received by the BS is measured in Bytes. 5- Each data packets received by the BS corresponds to 25 Bytes. The periodicity of these packets is ignored in simulation time because our clustering algorithm does not include periodic transmissions to the base station as in LEACH –C algorithm. Figure 7 represents the network lifetime in which FND, HND and LND are shown for the LEACH-C, Improved-LEACH, DE-LEACH and for the proposed protocol WDC-LEACH-C. Seen from this figure, death time of the first, half and last nodes in WDC-LEACH-C is latter than that in LEACH-C, Improved-LEACH, and DE-LEACH. Therefore, the WDC-LEACH-C provides a better long life for the network due to the minimization of the number and length of routes, which optimizes the energy consumption of sensors. Figure 8 shows the number of alive nodes per round in network. As we can see from this figure; the vanishing of alive nodes is decreasing slowly in the proposed algorithm WDC-LEACH-C, compared to LEACH-C, Improved-LEACH and DE-LEACH algorithms.When all nodes run out of energy in LEACH-C, Improved- LEACH and DE-LEACH, nodes in WDC-LEACH-C can still run for several additional rounds. Consequently, the network stability and life time in the proposed algorithm is much better with respect to DE-LEACH, Impro- LEACH and LEACH-C algorithms. Figure 8: Number of alive nodes. Figure 9 illustrates the energy consumption of nodes in network. Observed from this figure, we can obtain that our proposed protocol WDC-LEACH-C consumes less energy than LEACH-C, Improved-LEACH and DE- LEACH algorithms over the simulation rounds. This can be explained by the fact that the proposed algorithm provides better clustering and a good choice of CH. Since the CH is the WDC node, short transmission distances are used. Thus, network performance has been greatly improved. Figure 9: Energy consumption of nodes over simulation rounds. Figure 10 shows the amount of data received by the base station. As shown in figure 10, the amount of data received by the base station is much greater in the proposed protocol compared to DE-LEACH, Impro- LEACH and LEACH-C. Figure 7: Network lifetime. 250 Informatica 42 (2018) 245–251 A. Slimani et al. Figure 10: Quantity of data received by the BS. Figure 11 shows that the total number of packets sent to the base station is higher in WDC-LEACH-C compared to DE-LEACH, Improved-LEACH and LEACH-C algorithms. These results include initial packets of energy and GPS position Figure 11: Number of packets received by the BS. Table 2 summarizes the obtained results. As we can see from this table, the WDC-LEACH-C outperforms the other algorithms. This performance is in terms of energy consumption, prolonging network lifetime, data and received packets by the BS. 6 Conclusion In this paper, WDC-LEACH-C a single hop communication protocol for homogenous WSNs is proposed. The developed algorithm is based on the weighted density center (WDC) of cluster nodes and on the residual energy in the selection of cluster head (CH). WDC-LEACH-C algorithm ensures better energy saving and a prolonging lifetime of the network compared to LEACH-C, Improved-LEACH and DE-LEACH algorithms. 7 References [1] Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). Wireless sensor networks: a survey. Computer networks, 38(4), 393-422. [2] Baronti, P., Pillai, P., Chook, V. W., Chessa, S., Gotta, A., & Hu, Y. F. (2007). Wireless sensor networks: A survey on the state of the art and the 802.15. 4 and ZigBee standards. Computer communications, 30(7), 1655-1695. [3] Boyinbode, O., Le, H., & Takizawa, M. (2011). A survey on clustering algorithms for wireless sensor networks. International Journal of Space-Based and Situated Computing, 1(2-3), 130-136. [4] Aseri, T. C. (2014, March). Comparison of routing protocols in wireless sensor network using mobile sink-A survey. In Engineering and Computational Sciences (RAECS), 2014 Recent Advances in (pp. 1- 4). IEEE. [5] Afsar, M. M., & Tayarani-N, M. H. (2014). Clustering in sensor networks: A literature survey. Journal of Network and Computer Applications, 46, 198-226. [6] Jiang, C., Yuan, D., & Zhao, Y. (2009) Towards clustering algorithms in wireless sensor networks- a survey. In Wireless Communications and Networking Conference, WCNC 2009. IEEE, pp. 1- 6, doi: 10.1109/WCNC.2009.4917996 [7] Kawadia, V., & Kumar, P. R. (2003, March). Power control and clustering in ad hoc networks. In INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies (Vol. 1, pp. 459- 469). IEEE. [8] Karenos, K., Kalogeraki, V., & Krishnamurthy, S. V. (2008). Cluster-based congestion control for sensor networks. ACM Transactions on Sensor Networks (TOSN), 4(1), 5. [9] Ahmad, H., & Kohli, N. (2015, November). A survey on various static and mobile base stations and wireless charging of sensor nodes in WSNs. In Communication Networks (ICCN), 2015 International Conference on (pp. 16-22). IEEE. [10] Heinzelman, W. R., Chandrakasan, A., & Table 2. Simulation results. Protocol First node died in round Last node died in round Total energy consumption (Joules) Total quantity of data sent to the BS (Bytes) Total number of packets sent to BS LEACH-C 382 569 376 79845 3193 Impro-LEACH 429 600 305 101434 4057 DE-LEACH 511 732 250 147599 5903 WDC-LEACH-C 581 801 217 167132 6680 Weighted Density Center Clustering Protocol ... Informatica 42 (2018) 245–251 251 Balakrishnan, H. (2000, January). Energy-efficient communication protocol for wireless microsensor networks. In System sciences, 2000. Proceedings of the 33rd annual Hawaii international conference on (pp. 10-pp). IEEE. [11] 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-670. [12] Mhatre, V., & Rosenberg, C. (2004, June). Homogeneous vs heterogeneous clustered sensor networks: a comparative study. In Communications, 2004 IEEE International Conference on (Vol. 6, pp. 3646-3651). IEEE. [13] Loscri, V., Morabito, G., & Marano, S. (2005, September). A two-level hierarchy for low-energy adaptive clustering hierarchy (TL-LEACH). In Vehicular Technology Conference, 2005. VTC- 2005-Fall. 2005 IEEE 62nd (Vol. 3, pp. 1809-1813). IEEE. [14] Zhao, F., Xu, Y., & Li, R. (2012). Improved LEACH routing communication protocol for a wireless sensor network. International Journal of Distributed Sensor Networks, 2012. [15] Kumar, S., Prateek, M., Ahuja, N.J., & Bhuchan, B. (2014, February). DE-LEACH Distance and Energy Aware LEACH. International Journal of Computer Applications, 88(9), 36-42. [16] Runkler, T. A. (2008). Wasp swarm optimization of the c‐means clustering model. International Journal of Intelligent Systems, 23(3), 269-285. [17] Pinto, P., Runkler, T. A., & Sousa, J. M. (2005). Wasp swarm optimization of logistic systems. In Adaptive and Natural Computing Algorithms (pp. 264-267). Springer, Vienna. [18] Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: from natural to artificial systems (No. 1). Oxford university Press. [19] Engelbrecht, A. P. (2006). Fundamentals of computational swarm intelligence. John Wiley & Sons. [20] Kim, J. M., Park, S. H., Han, Y. J., & Chung, T. M. (2008, February). CHEF: cluster head election mechanism using fuzzy logic in wireless sensor networks. In Advanced communication technology, 2008. ICACT 2008. 10th international conference on (Vol. 1, pp. 654-659). IEEE. [21] Taheri, H., Neamatollahi, P., Younis, O. M., Naghibzadeh, S., & Yaghmaee, M. H. (2012). An energy-aware distributed clustering protocol in wireless sensor networks using fuzzy logic. Ad Hoc Networks, 10(7), 1469-1481. [22] Sharma, T., Kumar, B., Berry, K., Dhawan, A., Rathore, R. S., & Gupta, V. (2014, April). Ant based cluster head election algorithm in wireless sensor network to avoid redundancy. In Communication Systems and Network Technologies (CSNT), 2014 Fourth International Conference on (pp. 83-88). IEEE. [23] Eschenauer, L., & Gligor, V. D. (2002, November). A key-management scheme for distributed sensor networks. In Proceedings of the 9th ACM Conference on Computer and Communications Security (pp. 41-47). ACM. [24] Chidean, M. I., Morgado, E., del Arco, E., Ramiro- Bargueno, J., & Caamaño, A. J. (2015). Scalable data-coupled clustering for large scale WSN. IEEE Transactions on Wireless Communications, 14(9), 4681-4694. 252 Informatica 42 (2018) 245–251 A. Slimani et al.