WSN’s Life-Time Improvement Passing from Hierarchical to Hybrid Routing Techniques: A Comparative Study

Abstract

Wireless sensor networks consist of a large number of nodes deployed randomly in an area of interest. Theses nodes have sensing, computation, and wireless communications capabilities. In another hand nodes have energy constraints since they are equipped by non-rechargeable batteries. To handle this issue, routing protocols consist of designing the network in order to collect and transmit data with less energy consumption. In this paper we present a life-time and throughput comparative study passing from classical clustering protocols (LEACH) to a hybrid routing protocol, combines between clustering and Multi-hop Routing techniques (SMR). SMR introduces another type of nodes, called Independent Nodes (IN), whose role is to help Cluster Heads (CHs) to route their collected data to the Base Station (BS). Finally, a comparative study is done, in the first place, between LEACH and SMR in a homogeneous network. And in a second place between LEACH, DEEC and SMR in heterogeneous environment. Those simulations show a great improvement in network’s life-time and throughput using SMR technique in both homogeneous and heterogeneous environment when the base station is far from the center of the network, and less performance when the SB is placed in the middle of the network.

1 Introduction

Wireless Sensor Networks (WSNs) are attracting the attention of many researchers thanks to their participation in a variety of practical applications [1]. The main problem of WSNs is energy harvesting, because nodes are equipped with a non-rechargeable battery. Many routing, power management, and data dissemination protocols have been specially designed for WSNs where energy awareness is an essential design issue [2]. In another hand, routing protocols plays a very important role in routing the data collected by the sensors to the base station with the minimum cost of energy. Although, routing protocols defines the structure of the network and data transmission strategy. For this reason, LEACH [3], provided a clustering-based algorithm consisting of creating an optimal number of clusters determined by a probability $p_{opt}$. The election process is based on a random probabilistic method. Elected CHs are responsible of collecting data from cluster members and transmit it in a direct way to the BS. Furthermore, LEACH present a great improvement compared to direct schemes [3], but the main problems of LEACH are:

$\diamond$:

not considering nodes residual energy in election process.

$\diamond$:

CHs transmit directly to the BS, so knowing that the energy is related to distance to BS, the energy consumed by far CHs is high than energy consumed by close CHs.

In another hand the main idea of SMR [1] is to dived the network into levels, counted from the BS, as in MHT-LEACH [4] and IMHT-LEACH [5], and introduces another type of nodes called independent nodes NIs, created by limiting the number of cluster members to No, as in EDMHT-LEACH [6]. In addition, the cluster is divided into two levels, for that reason SMR consider inter and intra-cluster communication.

2 Related Work

A lot of researches are done in order to handle energy harvesting problem for WSN. Thus most of the current clustering algorithms are: LEACH [3], selects CHs periodically and drains energy uniformly by role rotation. Each node decides itself whether or not a CHs distributed by a probability. Under the homogeneous network, LEACH performs well, but its performance become badly in the heterogeneous network [7]. In PEGASIS [8], nodes organizes theirs self to form a chain. This method is difficult to implement due to the requirement of global knowledge of the network topology. In a heterogeneous environment, there is, SEP [10] considers that the network is consist of two types of nodes, normal nodes and advanced nodes whom have more energy than normal nodes. SEP is based on the same principle of LEACH except that each type of nodes has a specified election probability based on the proportion of each type in the network. DEEC [7], is an election energy aware protocol. It uses the same technique of LEACH, it introduce nodes residual energy in CHs election process so that nodes with more energy have more chance to be CHs than nodes with less energy. This process distribute consumption of energy in the network. Analysis of this protocol is not considered on this paper rather it’s used on comparative study.

3 Radio Model

In this paper we use the common radio model of a node to represent consumed energy in different transmissions of collected data through the network to the BS (see Fig. 1). To compute the consumed energy, we use the energy dissipation model proposed in [9]. The required energy to transmit and receive a k-bits message is calculated using the following equations [9]:

$$\begin{aligned} E_{Tx}(d)= LE_{ele} + \left\{ \begin{array}{ll} L\epsilon _{fs} d^2&{} \text{ si } \quad d<d_0 \\ \ L\epsilon _{amp} d^4&{} \text{ si } \quad d\ge d_0 \end{array} \right. \end{aligned}$$

(1)

$$\begin{aligned} E_{Rx}= lE_{ele} \end{aligned}$$

(2)

With d is the distance between the two nodes, $\mathbf {E_{TX}}$ is the energy dissipated during transmission and $\mathbf {E_{RX}}$ is the consumed energy in reception. $\epsilon _{fs}$ is the transmission power in the free space transmission model, $\epsilon _{amp}$ is the transmission power in the multi-hop transmission model. $\mathbf {d_0}$ is the limit value between free space and multi-hop transmission models, it’s expression is giving in [9, 11] as follow:

$$\begin{aligned} d_o=\sqrt{\frac{\epsilon _{fs}}{\epsilon _{amp}}} \end{aligned}$$

(3)

Fig. 1.

Radio model of a node

4 LEACH: Low Efficent Adaptative Cluster Hierarchy

LEACH is a self-organizing, adaptive clustering protocol that uses randomization to distribute the energy load evenly among the sensors in the network [3]. It consists in electing an optimal number $k_{opt} = p_{opt}N$ of CHs. The latter are responsible for creating their clusters and receiving data collected by the cluster member nodes, after that, they are responsible of routing the data to the base station. Knowing that the energy consumption in the CHs is large compared to the normal nodes and in order to balance the energy consumption between the different nodes, LEACH is divided into rounds and each round starts with a set-up phase in which the clusters are formed, followed by a communication phase during which data is routed to the base station (see Fig. 2).

Fig. 2.

Example of a hierarchical architecture model.

This protocol is applied on a homogeneous network whose initial energy of each node is $\mathbf {E_0}$, which gives that the total initial energy of the network is given by the Eq. (5).

$$\begin{aligned} E_{initot}=\displaystyle \sum _{i=1}^{N}E_i =NE_0 \end{aligned}$$

(4)

LEACH is divided into rounds, each round contains a set-up phase, and a communication phase [1, 3]. In the Set-up phase each node decides whether it will be a CH or not, based on the following procedure: each node chooses a random number between 0 and 1, if the chosen number is less than the threshold value $\mathbf { T (n)}$, the node becomes a CH. With $\mathbf { T (n)}$ is given by the following expression as in [3]:

$$\begin{aligned} T(n) = \left\{ \begin{array}{ll} \frac{p_{opt}}{1-p_{opt} \left( r mod \frac{1}{p_{opt}}\right) } &{} \text{ if } \{n\} \in G \\ 0 &{} \text{ otherwise. } \end{array} \right. \end{aligned}$$

(5)

With $p_{opt}$ is the optimal probability of a node to be a CH and G is the set of legitimate nodes to be CHs for the round r. After the election, each CH for the round r, broadcasts an advertising message to all the nodes using the CSMA MAC protocol, to avoid collision with other CHs messages. Then each normal node decides which cluster will belong by sending a JOIN-REQ to the corresponding CH. At this time, each CH generates a time schedule using the TDMA which manages the transmission periods of each cluster members.

In the Communication phase, each cluster member collect data and send is to his CH in the time slot reserved by the TDMA. The CH aggregate data received and send it to the BS using the node radio model discussed earlier.

The energy consumed by a cluster member (CM) and a CH are expressed respectively in (6) and (7) as expressed in [11]:

$$\begin{aligned} E_{cm}=L.E_{elec}+\left\{ \begin{array}{ll} L\epsilon _{fs} d_{toCH}^2&{} \text{ si } \quad d_{toCH}<d_0 \\ \ L\epsilon _{amp} d_{toCH}^4&{} \text{ si } \quad d_{toCH}\ge d_0 \end{array} \right. \end{aligned}$$

(6)

$$\begin{aligned} E_{CH}=\frac{N}{k}L\left( E_{data}+ E_{elec}\right) + \left\{ \begin{array}{ll} L\epsilon _{fs} d_{toBS}^2&{} \text{ si } \quad d_{toBS}<d_0 \\ \ L\epsilon _{amp} d_{toBS}^4&{} \text{ si } \quad d_{toBS}\ge d_0 \end{array} \right. \end{aligned}$$

(7)

$E_{data}$ is the aggregation energy. The total energy consumed by a cluster in a single round is expressed as in [10].

$$\begin{aligned} E_{clus}=E_{CH}+\frac{N}{k_{opt}} E_{cm} \end{aligned}$$

(8)

With N is the total number of nodes in the network and $k_{opt}$ is the optimal number of clusters.

Let $e =\frac{1}{p_{opt}}$, the epoch, defined as the number of rounds necessary so that all nodes are being legitimate again to be elected as CHs [7]. Since the network is homogeneous, in terms of energy, all nodes have the same possibility of being a CH once per epoch. Figure 3 shows the dynamic process of creating clusters in two different rounds. All nodes marked with the same symbol belongs to the same cluster.

Fig. 3.

Network’s state in two different rounds

LEACH protocol has gained much popularity in the WSN research field, due to its outstanding success [1], prolonging network’s life-time and throughput compared to direct schemes. But it still have a lot of limitations, we mention, not considering node’s residual energy on election process. and the fact that CHs transmit theirs collected data directly to the BS. Knowing that the election process is totally random, far CHs will consume more energy than close CHs, this results that far nodes dies quickly due to the imbalanced energy consumption.

5 SMR: Static Multi-hop Routing

SMR is a hybrid routing protocol, that combines between Hierarchical and flat routing schemes in order to prolong network’s life-time and throughput. The main idea of this protocol is to divide the network into many levels, starting from the BS, the length of each level is $\frac{d_o}{2}$. Each node calculate it’s level according to the distance to the BS. For example, the CH located at a distance less than $\frac{d_o}{2}$ from the BS will belong to the first level, whereas the CH with a distance equal or larger than $\frac{d_o}{2}$ but less than $d_o$ will belong to the second level and so on [1] (see Fig. 4).

Fig. 4.

The general topology of a WSN using the proposed approach

SMR is composed of four phases as in [6].

5.1 Initial Phase

In this phase, the election of CH’s is done. The process is the same as in LEACH, but the difference is in the threshold expression. The new election threshold is expressed as follow [6, 12]:

$$\begin{aligned} T(n_i) = \left\{ \begin{array}{ll} max\left( \frac{p_i}{1-p_i.\left( r mod \frac{1}{p_i}\right) }\times \frac{E_{res}}{E_{init}}, T_{min}\right) &{} \text{ si } \{n_i\} \in G \\ 0 &{} \text{ Otherwise. } \end{array} \right. \end{aligned}$$

(9)

Here, the $\mathbf { E_{res}}$ is the amount of energy, which the node still has after a period of working.$\mathbf { E_{init}}$ denotes the amount of energy incorporated in a node before starting its activity. $\mathbf {T_{min}}$ refers to the minimum value of the threshold, which can be used if the $\mathbf { E_{res}}$ value has descended to low values [1]. As fixed in [6], each cluster have a limited, permitted, number of members fixed to $N_o=\frac{N}{k_{opt}}$. Moreover, the proposed approach assumes that the sensor node is only able to join the cluster is the distance between them is less than $d_o$.

The limited number of CMs and distance approach results the apparition of another types of nodes that’s not belong to any cluster. Those nodes are called Independent Nodes (INs) whose used to help CHs route data to the BS. The new approach add by this protocol is clusters leveling. It assume that each cluster is also divided into two levels, and each one is a $\frac{d_o}{2}$ length.

5.2 Announcement Phase

After election process each node, CHs, CMs and INs, declare it self in the network broadcasting a message containing it’s ID, localization (x, y) and level.

5.3 Selection Phase

Diffused messages are helping nodes far from the BS to create theirs Routing tables (RTs), containing the hops to passe through to attend the BS. We can examine two cases:

Intra-communication: CMs existing in cluster’s first level (FCM) send their data directly to the CH. CMs existing in cluster’s second level, create a RT containing the closest FCMs to route their data. The process is that each node Ns send a request message to the FCMs, this one checks its TDMA schedule, if there is an empty slot it sends back an acceptance message and it’s add to CM’s RT. If not it passes to the other closest FCM.

Inter-communication: each node Ns send a request message to the New Hop Node (NHN), NHN can be a CH or an IN existing on lower levels than the sending node. the NHN checks its TDMA schedule, if there is an empty slot it sends back an acceptance message and it’s add to it’s RT. If there is no empty slot, the NHN send a refusal message.

5.4 Routing Phase

SMR consist of creating a static road to route data collected by nodes to the BS every round. We have two types of communications, intra and inter cluster communication.

Intra-cluster Routing: As mentioned above, each cluster is divided into two levels. The nodes of the 1st level communicate directly with the CH and the CMs of 2nd level uses their RTs to select the closest node of 1st level which forward then the data towards the CH. The chosen route will be used during all the present round.

Inter-cluster Routing: Routing is done by the same way, the difference is that the communication in this case is between CHs and INs. CHs/INs existing on the lowest level send directly to the BS, and those far frome the SB send to others in lower levels, and so on until data is routed to the SB.

The energy consumed in transmitting or receiving data is calculated using the same Eq. (1) and (2).

6 Simulation Results

In this section we will evaluate the performance of the hybrid protocol SMR performing three experiments. the three cases of simulations, type of the network, and protocols analyzed per experiment are resumed on Table 1. A MATLAB program is used to evaluate the performance and to make the comparative study in a network of 200 nodes randomly deployed in an area of 200 $\times$ 200 m.

Table 1. Experiments specifications

Analysis will be divided into three sections: in the first experiment, we will discuss the performance of SMR compared to LEACH in a homogeneous network (nodes have the same initial energy) and the SB is located far from the network. After that, SMR performance is evaluated in case of a heterogeneous network (nodes have different initial energy) for a SB located far from the network (second experiment) and for a SB located in the center of the network (third experiment). Common parameters used in the simulations, are mentioned in Table 2.

Table 2. The essential simulation parameters

6.1 1st Experiment

Figure 5 represents the network life time of SMR and LEACH. Based on the obtained results, we can denote that SMR, have a great improvement in network life time compared to LEACH. This result is achieved because the SMR suppose that the network is divided into levels around the BS and the CHs. Particularly, the CHs and the INs determine their levels around the BS, whereas the CMs will identify their levels based on the distances to its CH. Thus, all sensor nodes of the network use multi-hop routing to deliver the data to the destinations either the BS or the CHs.

Due to network leveling, the distance of transmission is reduced to be less or equal to $\frac{d_o}{2}$, so we use the free space model that consumes less energy. Thus, it explains prolonging stability zone and life-time occurred by SMR.

Fig. 5.

The comparison of the number of alive nodes in the SMR and LEACH for experiment 1.

In Fig. 6, we represent the number of packets sent to the BS and to CHs. We observe that due to the increasing of network’s life time, the number of packets sent using SMR is very large than the number of packets sent using LEACH.

Fig. 6.

Comparison of the number of packets sent to CHs (a) and to BS (b) using LEACH and SMR techniques in experiment 1.

6.2 Experiments 2 and 3

From Table 1, we can denote that the difference between the second and the third experiments is the localization of the SB. For this reason we will discuss results in the same section. To create an heterogeneous network, each node will have a specific energy equal to $E_0(1+a_i)$, with $0<a_i\le 1$ [7]. In this case each node will have a specific exceed of energy that makes it unique in the network. Since SMR have done well in the exp. 1, in exp. 2, SMR is evaluated, for the first time, in a heterogeneous network and compared with LEACH and DEEC, knowing that the SB is localized, far from the network, in (100m, 300m).

The results of simulation of the second and the third experiments are presented on Figs. 7 and 8.

Figure 7, represent network’s life time of SMR, DEEC and LEACH in an heterogeneous network with the SB is located respectively at (100m, 300m) (a), and (100 m,100 m) (b).

Fig. 7.

The comparison of the number of alive nodes in the SMR, DEEC and LEACH, in experiments 2 & 3.

We can clearly observe that SMR perform very well in the case where the SB is located far from the network (Fig. 7(a)). As in homogeneous network, stability zone is larger and network’s life time is prolonged and the number of packets sent to the SB (resp. CHs) Fig. 8(a) (resp. Fig. 8(b)) is very large using SMR compared to DEEC and LEACH.

Fig. 8.

Comparison of the number of packets sent to BS (a), (c) and to CHs (b), (d) using LEACH, DEEC and SMR techniques for experiments 2 & 3.

In the other side, when the SB is located in the center of the network (Fig. 7(b)), SMR have an improvement compared to LEACH but not compared to DEEC.

Life-time is prolonged, but the stability zone is still shorter, than stability zone obtained using DEEC. Furthermore, the number of packets sent to SB and CHs, using SMR, is greater than number obtained using LEACH, but less than number obtained using DEEC, Fig. 8(c) and (d).

6.3 Results Discussion

Analyzing obtained results, SMR showed a remarkable improvement, in network’s life time and throughput, in both homogeneous and heterogeneous networks, when the SB is located far from the network, compared to LEACH and DEEC. This can be explained by the fact that in LEACH and DEEC, CHs transmit their data directly to the BS, no matter what the distance is. This results a raise in energy consumption specially for far CHs and create an unbalanced consumption of energy. In the other hand SMR limited the distance of transmission to $\frac{d_0}{2}$, for both inter and intra communications, using multi-hop transmission and introducing the INs. This solution reduced the energy consumed by nodes during transmission and results prolonging network life time and improving throughput. In the third simulation, the little improvement in stability zone using SMR, compared to LEACH can be explained by the fact that the number of nodes per clusters in SMR is limited to $N_o$, this reduce load on CHs and save more energy aggregating collected data and explain the slow raise in the number of packets sent to CHs using SMR in the third experiment, Fig. 8(d). Rather that the stability zone is not improved compared to DEEC, that is explained by the fact that SMR is based on the same election process of LEACH, not using an election process based on the global and residual energy of nodes in each round.

Despite the stability zone is not prolonged, Network’s life-time using SMR is extended compared to LEACH and DEEC, this is, as explained before, due to the multi-hop communication schemes.

As regards throughput. In experiments 1 and 2, SMR showed a great raise in the number of packets sent to the BS and the CHs. That is clearly related to the great improvement in network’s life-time and stability zone extension.

6.4 Statistics

More statistics presenting information about rounds of the First Nodes Dead (FND), Half Node dead (HND) and All Nodes Dead (AND) of compared protocols in the three experiment are resumed in Table 3.

Table 3. FND, HND and AND rounds of SMR, DEEC and LEACH in all experiments

From this statistics we can see that passing from a homogeneous network to a heterogeneous network (exp. 1 to exp. 2) have increased performance of SMR and LEACH. This is explained by the random value of energy (a(i)) add to each sensor node to create a heterogeneity in the network.

7 Conclusion

In this paper, we have analyzed two techniques for routing data in WSNs: the LEACH and SMR techniques. LEACH is a hierarchical based routing protocol consisting of a random process of election of CHs. Those elected nodes (CHs) are responsible of creating clusters, collecting data and send it to the BS. Furthermore, LEACH presented a great success comparably to direct schemes but still have limitations. The second technique is a hybridization between multi-hop and clustering concepts. The principal idea of this protocol is assuming that all nodes could be in one of three situations during the network rounds: CH, IN or CM. Using network leveling strategy, SMR introduces two types of data routing: the first type is the intra-cluster data routing and the second type is the inter-cluster data routing. The SMR technique have presented a new approach for disseminating the data through the network levels.

Three simulations were done to evaluate the performance of the SMR. For the first one SMR was compared to LEACH on an homogeneous network with the SB is located far from the network. The Second was on an heterogeneous network, where the SB is located far from the network and the third simulation is the same as the second but, this time, the SB is located in the center of the network.

Simulations results demonstrated that SMR’s routing technique have prolonged network’s life-time and increased throughput, compared to LEACH, in the first experiment, and compared to LEACH and DEEC in the second experiment. The reduction in transmission distances, which is obtained by applying network leveling approach, has reduced the energy dissipation, and has increased the stability of the network. In the third simulation, SMR showed an improvement in stability compared to LEACH, but not a considerable performance compared to DEEC when the SB is located at the center of the network.

Finally, basing on simulations results, we can conclude that SMR performs very well when the SB is far from the network, in both homogeneous and heterogeneous networks, compared to LEACH and DEEC. In the other hand SMR didn’t show a significant improvement when the SB is in the center of the network.