Asma Mesmoudi* | Samira Mesmoudi | Zakarya Houari | Khelifa Mostefa
© 2021 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).
OPEN ACCESS
Wireless sensor networks have recently gained a lot of attention from the scientific community due to their very wide spectrum of applications. In such networks, the sensor nodes have limited resources. These constraints impose many challenges to the design of related protocols. Especially, routing protocols should be energy-efficient for the prolonged network lifetime. The LEACH protocol is the most popular energy-efficient hierarchical clustering protocol for WSNs that was proposed for reducing power consumption. However, LEACH suffers from several drawbacks such as the non uniform distribution of Cluster Head nodes, the possibility of choosing a low energy node as Cluster Head, etc. In this paper, an attempt is made to overcome this shortcoming by introducing a new hierarchical clustering protocol, called SCHP (Static Cluster-based Hierarchical Protocol). The SCHP protocol is based on a static cluster creation and an optimal cluster head selection. Simulation results show that the proposal guarantees better performance than the LEACH Protocol that is considered as the baseline in the literature. We used many metrics, as packet loss rate, end-to-end delay, and energy consumption to evaluate the efficiency of our proposal. We show also that the SCHP protocol can improve the network lifetime.
cluster head node, energy-efficient, hierarchical clustering, LEACH, SCHP wireless sensor network
In recent years, the rapid evolution of microelectronics technology, communication technology, and wireless sensing technology, giving rise to a new type of network called Wireless Sensor Network (WSN) [1]. This type of network has been used in a wide variety of applications and systems with varying requirements and characteristics [2]. Particularly in the area of health [3], environment, and safety.
A Wireless Sensor Network (WSN) consists of a large number of small electronic devices with a little power and cost (limited resources), capable of collecting and reporting data to a central point called a base station or sink. Each sensor node is equipped with a microprocessor with low computing power, a small battery, a radio antenna, and one or several sensors [4]. However, these constraints impose many challenges concerning the protocol design of the WSN. Especially, routing algorithms should be energy efficient to extend the network lifetime.
Usually, network structure-based routing protocols are divided into three main categories including flat, hierarchical, and location-based routing. In particular, hierarchical routing protocols have proved to be able to save in the overall energy consumption of the WSN [5].
In hierarchical routing protocols, the clustering strategy can be applied to improve the network performance. The nodes are grouped in fact into clusters, and a head node is assigned to each cluster. This node is called cluster head (CH). The CH nodes have some responsibilities like collecting and aggregating the data from their respective clusters and transmitting the aggregated data to the sink node.
The commonly known hierarchical routing protocols are LEACH [6], PEGASIS [7], TEEN [8]. The LEACH protocol is the first and most popular energy-efficient hierarchical clustering algorithm for WSNs that was proposed to reduce power consumption [5]. However, LEACH has several drawbacks such as the possibility of choosing a low energy node as CH, non uniform distribution of CHs, etc.
To address the above problems, we propose a new hierarchical routing protocol, called "SCHP: Static Cluster-based Hierarchical Protocol ". This protocol is based on a static cluster creation and an optimal cluster head (CH) selection.
The remainder of this paper is organized as follows: Section 2 discusses our motivation. A detailed description of the SCHP protocol is presented in section 3. Simulation results are reported in section 4. Finally, section 5 concludes the paper.
2.1 LEACH algorithm
Low-Energy Adaptive Clustering Hierarchy (LEACH) [6] is the most popular cluster-based routing protocol in wireless sensor networks. The LEACH protocol is the first protocol to bring the concept of round when running. During each round, the cluster head nodes are randomly selected from all the sensor nodes which allows to construct dynamically several clusters.
In LEACH, the cluster head depends on the decision made by sensor nodes. Indeed, all nodes choose a random number between 0~1, and if it is less than a threshold T(n), the sensor nodes will broadcast an announcement message to notify others that it is a cluster head. In each round, if a node has been elected as a cluster head, its T(n) is set to zero, so that the node will not be elected as a cluster head again. The threshold T(n) is set using the formula:
$T(n)=\left\{\begin{array}{c}\frac{p}{1-p \times\left(r \bmod \frac{1}{p}\right)} \quad \text { if } n \in G \\ 0 \quad\quad otherwise\end{array}\right.$ (1)
where, P is the desired percentage of cluster heads in the network (usually P is 5% in [6]), r is the current round, and G is the set of nodes that have not been cluster-heads in the last 1/p rounds.
2.2 Drawbacks of the LEACH protocol
Several studies [9-11] have shown that the use of randomized strategies of CHs rotation and CHs selection, as used by the LEACH protocol, suffers from several limitations.
Lung and Zhou [9] have shown that the main drawback of so-called probabilistic protocols, particularly LEACH, is the non-uniform distribution of cluster heads. The elected CH nodes may have been concentrated in some part of the network, which can lead some nodes to have no CH nodes in their area of coverage. Moreover, the rotation of the CH is not always uniform, which can influence the distribution of energy consumption.
Wang and Xiong [10], and Pantazis et al. [11] have shown that due to the probability-based CH selection strategy, the number of CH nodes in LEACH as well as in other protocols using the same clustering process, cannot be guaranteed to be equal to the desired optimal value (k clusters).
The strategy of selecting CH nodes based on probabilities in each round requires a large number of control messages, a significant amount of energy is then dissipated due to message duplication.
Dynamic clustering opens the door to attacks and reduces network security, where the clusters are formed repeatedly. In this protocol category, selected CH nodes are not uniformly distributed in the region. Consequently, cluster sizes, in terms of the number of nodes per cluster, are highly variable.
The use of a process for selecting CHs and building deterministic clusters would greatly reduce the drawbacks of random CH selection methods. For these multiple reasons, we propose a new hierarchical routing protocol, called SCHP, to overcome the variations in cluster sizes of the network. The SCHP protocol is unique in its way to elect the CH nodes. The SCHP protocol is described in further sections.
This section presents our proposed routing protocol. The used notations are given at the end of the paper, and then the detailed description of the protocol is exposed.
3.1 Protocol characteristics
In this section, the characteristics of our protocol are discussed.
3.1.1 Number of clusters
In our SCHP protocol, the network is partitioned into static clusters, as shown in Figure 1. Thus, the number of desired clusters “k” should between 5% and 15% of the total number of nodes [10].
Figure 1. An example of clusters creation
3.1.2 Cluster size
One of the reasons for the early death of a wireless sensor network is the uneven distribution [12] of the nodes within a cluster, which can also lead to an overload of the CH nodes. That leads our protocol to use clusters formation with an equal number of nodes. Thus, the size of the clusters is fixed by using an optimum value defined as Z/k.
3.1.3 Routing
Data routing in our protocol is performed through two levels: MN-CHs (member nodes send their packets to the CH nodes) and CH-Sink (CH nodes transmit their aggregated data to the base station).
3.1.4 Deployment of sensor nodes
Two deployment strategies are considered. Nodes can be randomly deployed from an aircraft for example, or they can be placed one by one in a deterministic way by a human or a robot.
To minimize the coverage gaps in a network, many protocols are based on a network of sensors that are uniformly distributed compared to those that are randomly distributed. Figure 2 is an illustrative example of two different deployment strategies with the same number of sensor nodes.
Figure 2. Illustrating the deployment strategy when: (a) Sensors are uniformly distributed; (b) Sensors are randomly distributed
The deployment of sensor nodes is a crucial phase that can affect significantly the coverage quality of the network monitoring area. Figure 2 shows that with a uniform distribution deployment strategy a good coverage quality is ensured. Therefore, our SCHP protocol uses a random deployment of nodes with a uniform distribution. So, the whole network is represented by a set of grid cells and each cell of the grid contains an equal number of nodes.
3.2 Protocol description
The basic assumptions considered during the construction of our protocol are presented as follows:
Each sensor node has a unique identifier ID.
All sensor nodes monitor the environment at a fixed interval, and they always have data to send to the final user.
The sink node has an unlimited energy resource and has high transmission power. As such, all sensor nodes are within the range of this node.
The nodes can use the power control to regulate the transmission power according to the transmission distance if necessary. Thus, a CH can directly perform transmission to the sink node.
All nodes are considered nomadic or stationary.
Our proposed routing protocol involves the following phases:
3.2.1 Planification phase
In this phase, the whole network is represented by a set of grid cells. Each cell of the grid (a number K of cells) will be related to a set of nodes, which will form a cluster. Moreover, each CH takes as its position the center of gravity (COG: Center Of Gravity) of each cell, as shown in Figure 3.
Figure 3. Illustrating of clusters
3.2.2 Initialization phase
The initialization phase starts by sending an initialization message from the base station to all sensor nodes in the network.
3.2.3 Announcement phase
Each CH node (the nodes located at the COG of each cell) when receiving an initialization message, broadcasts an announcement message to other nodes by using the same transmission energy.
3.2.4 Organization phase
This phase includes three steps:
Step1: After the completion of the previous three phases, all non CH nodes decide which cluster they belong to according to the strength of the RSSI signal.
Step2: Each non CH node must inform the CH that it will be a member of its cluster. They reply then with the JOIN_ REQ message, which contains their identifier (ID).
Step3: After the reception of the JOIN_ REQ message, each CH starts by identifies the set of sensors that is in the same cluster and assigns then an index for each received ID. This index is based on the order of receiving messages, as shown in Figure 4.
Figure 4. Illustrating the organization phase
3.2.5 Scheduling phase
When the clusters are formed, each CH will produce a TDMA schedule and notify all the member nodes in the cluster. After the reception of the schedule by a member node, it transmits data to its correspondent CH node in its time slots and remains in the sleep state in other slots.
3.2.6 Sharing phase
In this phase, each CH node broadcasts a message to their member’s nodes that contains the list L-MN of the IDs and their appropriate index.
where,
$\mathrm{L}_{-\mathrm{MN}}=\left\{\mathrm{id}_{\mathrm{MN}_{1}}\right.$, index $_{\mathrm{MN}_{1}}, \ldots, \mathrm{id}_{\mathrm{MN}_{\mathrm{m}}}$, index $\left._{\mathrm{MN}_{\mathrm{m}}}\right\}$ (2)
After receiving the message from its CH node, each member node identifies the member nodes that are in the same cluster and saves the information received containing the identifiers of the member nodes with its index. With this method, all nodes in the same cluster have the same saved information.
3.2.7 Transmission phase
In this phase, the data transfer to the sink will take place. Using the TDMA scheduler, member nodes transmit their captured data during their slots. This allows them to turn off their communication interfaces outside of their slots to save energy. This data is then aggregated by the CHs who merge and compress it, and, send the final result to the sink.
Our proposed protocol provides the conception of rounds. It runs with many rounds (round 0, round 1, …, round m), and each round is triggered to find out the optimal CH. The round contains different phases for two main objectives: the first is to form clusters, and the second one is to perform data transmission.
After nodes are deployed, the network starts with round 0 (r=0) to select the CH using all phases. After a certain predetermined time, the network will move to a new round. In a new round and all the following rounds (r ≠ 0), this process is repeated but the announcement phase and the organization phase are ignored. This is because the election of the CHs will be automatic.
The elected CH is the node corresponding to the appropriate ID of the minimal index saved by each member node in the Sharing phase of the previous round. As the information (containing the identifiers of the member nodes with its index) saved by the member nodes of each cluster is the same, the nodes know directly their CH for this round.
With this process, just after the reception of the initialization message of new round r, the CHs transmit directly the scheduling messages to the nodes of its cluster, then passes directly to the transmission phase and like that for all the following rounds.
In this section, we present a performance evaluation of the SCHP protocol through a set of experiments. Indeed, we provide extensive simulations to verify performance metrics such as energy consumption, network lifetime, and packet loss rate. In the set of simulations, we compare the SCHP protocol with LEACH [6], which is considered as the baseline in the literature. To that end, we implemented SCHP using the NesC [13] programming language to be integrated with TinyOS. The simulations are done using the TOSSIM [14] environment. We have also used PowerTOSSIM, a dedicated plugin that models power consumption.
In our simulations, we make use of several networks that have a size varying from 50 to 200 nodes (of MICA2 type). Among these nodes, 10% of nodes are CH. The nodes are distributed uniformly and randomly in an area of 100 × 100 m. Furthermore, the Lossy propagation model is employed.
The performance of routing protocols is evaluated in terms of the following metrics: energy consumption, network lifetime, packet loss rate, and the average end-to-end delay.
4.1 Energy consumption
Sensor nodes have limited power source. Therefore, routing protocols must be energy efficient to extend the life of the network. To evaluate the energy consumption, we used PowerTOSSIM plugin with TinyViz to analyze the energy of the two protocols.
4.1.1 The additional energy consumption
Figure 5. Additional energy consumption
We evaluated the energy consumption of the sensor nodes during five rounds. We considered a network with 150 nodes.
As shown in Figure 5, the total energy consumption of the nodes in the SCHP protocol is a little higher than that of the LEACH protocol in rounds 0 and 1, but after some time, the energy consumption of the SCHP protocol decreases compared to that of the LEACH protocol. This is due to the elimination of energy-intensive tasks (cluster organization in rounds ≠ 0) performed by the CH when it is elected in each round.
4.1.2 Energy consumption of CHs and member nodes
Concerning the SCHP protocol, it is easy to see from Figure 6 that in round 0 the average energy consumption of either member nodes and CH nodes is very high compared to that of the LEACH protocol. The rate of more than 31.95% is noted for the CH nodes on one hand and a rate of more than 28.87% is noted for member nodes on the other hand. This is due to the tasks dedicated to the sharing of the member nodes' table. We could notice that the average energy consumption of nodes in the SCHP protocol decreases for the rest of the rounds. This is due to the end of cluster organization tasks. The decrease is with an average rate of 24.42% less for CH nodes and 13.82% less for member nodes.
Figure 6. Average energy consumption of CH node and member nodes
4.1.3 Evaluation of average energy consumption with respect to network size
As shown in Figure 7, we notice that the average energy consumed in the network is independent of the number of the deployed nodes. This is due to the existence of the hierarchical topology in both protocols that make them very scalable. Besides, we observe a rate of 14.62% less dissipated energy for our SCHP protocol compared to the LEACH protocol. This is due to the decrease in the number of control messages used in the cluster organization phase.
Figure 7. Average energy consumption with respect to network size
4.2 The network lifetime
The network lifetime has become the key characteristic allowing to evaluate of key management protocols for sensor networks. We measured it concerning the number of dead nodes, which indicates when nodes exhaust all their energies.
4.2.1 Number of dead sensor nodes
As shown in Figure 8, it is clear that the SCHP protocol outperforms the LEACH protocol. Indeed, our protocol consumes less energy when performs network operations.
Figure 8. Number of dead sensor nodes with respect to time evolution
4.2.2 Distribution of dead nodes
Figure 9 shows the distribution of dead nodes for both protocols. We can see that the dead nodes in the LEACH protocol are distributed in specific areas, contrary to the SCHP protocol where the distribution is homogeneous in all the cells of the area. Therefore, this would allow for better monitoring of the desired events along the network lifetime.
Figure 9. Distribution of dead sensor nodes
4.3 Packet loss rate
The choice of this metric, as a performance criterion, stems from the necessity in some applications to exchange critical data.
As shown in Figure 10, we can see that the packet loss rates exchanged are tolerable for both protocols. We can see that the packet loss rate is higher in LEACH than in the SCHP protocol. This is because the LEACH protocol has clusters with a large number of members, which leads to collusions between the nodes, and has a higher number of dead nodes compared to the SCHP protocol.
Figure 10. Packet loss rate with respect to network size
4.4 Average end-to-end delay
This performance metric, stems from the necessity, for certain real-time applications, to obtain the information as soon as possible to take the necessary measures. Therefore, the end-to-end delay is defined as the total amount of time the system takes to route the data from the source to the base station.
Figure 11 shows that the two protocols have a very close delay. Once the network size increases, the average delay also increases. The SCHP protocol performs slightly better than the LEACH protocol. The reason is that this protocol uses a uniform distribution of clusters, which decreases the load on the CH nodes and decreases the distance between them and their member nodes.
Figure 11. Average end-to-end delay with respect to network size
Because of the limited energy resources of sensors, energy efficiency is one of the main challenges in designing protocols for WSNs. Clustering is proven to be an effective technique to attain energy efficiency. Many hierarchical clustering protocols focus on electing an optimal CH node.
In this paper, we have presented a new hierarchical routing protocol, called "SCHP: Static Clustering Hierarchy Protocol". We make use of a static clustering strategy, with an equal number of nodes for each formed cluster. During rounds that differ from 0 and based on an analysis of received information from nodes either CH nodes or members, the cluster head (CH) selection and CH nodes rotation are automatically performed.
The simulation results showed that the performance of the proposed protocol compared to the LEACH routing protocol is better in terms of energy consumption, packet loss rate, end-to-end delay, and even monitoring of efficiency.
|
CH |
Cluster Head |
|
MN |
Member Node |
|
R |
Communication range |
|
Z |
Area of the network |
|
r |
Round |
|
K |
Number of CH |
|
L-MN |
List contains the identifiers and their appropriate index of the member nodes |
|
$\mathrm{id}_{\mathrm{MN}_{\mathrm{i}}}$ |
Identifier of the member node i |
|
index $_{M N_{j}}$ |
Index of the Identifier of the member node i |
|
m |
The number of member nodes in each cluster |
[1] Mesmoudi, A., Feham, M., Labraoui, N. (2013). Wireless sensor networks localization algorithms: A comprehensive survey. International Journal of Computer Networks & Communications, 5(6): 45-64. https://dx.doi.org/10.5121/ijcnc.2013.5603
[2] Romer, K., Mattern, F. (2004). The design space of wireless sensor networks. IEEE Wireless Communication, 11(6): 54-61. https://doi.org/10.1109/MWC.2004.1368897
[3] Mesmoudi, S., Feham, M. (2011). BSK-WBSN: Biometric symmetric keys to secure wireless body sensors networks. International Journal of Network Security & Its Applications, 3(5): 55-166. https://doi.org/10.5121/ijnsa.2011.3512
[4] Syed, M., Dubey, M.K. (2020). Software-fault mitigation for derivation of quality of services (QoS) in wireless sensor networks (WSN). Instrumentation Mesure Métrologie, 19(5): 327-336. https://doi.org/10.18280/i2m.190502
[5] Uppalapati, S. (2020). Energy-efficient heterogeneous optimization routing protocol for wireless sensor network. Instrumentation Mesure Métrologie, 19(5): 391-397. https://doi.org/10.18280/i2m.190510
[6] Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. The 33rd Hawaii International Conference on System Sciences, Maui, Hawaii, USA, pp. 3005-3014. http://dx.doi.org/10.1109/HICSS.2000.926982
[7] Lindsey, S., Raghavendra, C.S. (2002). PEGASIS: Power-efficient gathering in sensor information system. IEEE Aerospace Conference, Big Sky, Montana, pp. 1125-1130. https://doi.org/10.1109/AERO.2002.1035242
[8] Manjeshwar, A., Agrawal, D.P. (2001). TEEN: A protocol for enhanced efficiency in wireless sensor networks. 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, San Francisco, CA. https://doi.org/10.1109/IPDPS.2001.925197
[9] Lung, C.H., Zhou, C. (2010). Using hierarchical agglomerative clustering in wireless sensor networks: An energy-efficient and flexible approach. Ad Hoc Networks, 8(3): 328-344. https://doi.org/10.1016/j.adhoc.2009.09.004
[10] Wang, Y., Xiong, M. (2005). Simulation of leach protocol for wireless sensor networks. 6th International Conference on Parallel and Distributed Computing Applications and Technologies, Dalian, China, pp. 85-88. http://dx.doi.org/10.1109/PCSPA.2010.113
[11] Pantazis, N., Nikolidakis, S., Vergados, D. (2013). Energy-efficient routing protocols in wireless sensor networks: A survey. IEEE Communications Surveys & Tutorials, 15(2): 551-591. https://doi.org/10.1109/SURV.2012.062612.00084
[12] Patil, M., Biradar, R.C. (2012). A survey on routing protocols in wireless sensor networks. IEEE Communications, India. http://dx.doi.org/10.1109/ICON.2012.6506539
[13] Gay, D., Levis, P., Behren, R.V., Melsh, M., Brewer, E., Culler, D. (2003). The nesC language: A holistic approach to networked embedded systems. ACM SIGPLAN International Workshop, San Diego, California, USA, pp. 9-11. http://dx.doi.org/10.1145/781131.781133
[14] Levis, P., Lee, N., Welsh, M., Culler, D. (2003). TOSSIM: Accurate and scalable simulation of entire tinyosapplications. 1st ACM Conference on Embedded Networked Sensor Systems, Los Angeles, CA, pp. 126-137. https://dx.doi.org/10.1145/958491.958506
