Hierarchical Adaptive Balanced Routing Protocol for Energy Efficiency in Heterogeneous Wireless Sensor Networks

1. Introduction

Wireless sensor networks (WSNs) are composed of many homogeneous or heterogeneous sensor nodes with limited resources. Routing techniques are the most important issue for networks where resources are limited. WSNs technology’s growth in the computation capacity requires these sensor nodes to be increasingly equipped to handle more complex functions. Each sensor is mostly limited in their energy level, processing power and sensing ability. Thus, a network of these sensors gives rise to a more robust, reliable and accurate network. Lots of studies on WSNs have been carried out showing that this technology is continuously finding new application in various areas, like remote and hostile regions as seen in the military for battle field surveillance, monitoring the enemy territory, detection of attacks and security etiquette. Other applications of these sensors are in the health sectors where patients can wear small sensors for physiological data and in deployment in disaster prone areas for environmental monitoring. It is noted that, to maintain a reliable information delivery, data aggregation and information fusion that is necessary for efficient and effective communication between these sensor nodes. Only processed and concise information should be delivered to the sinks to reduce communications energy, prolonging the effective network lifetime with optimal data delivery.

An inefficient use of the available energy leads to poor performance and short life cycle of the network. To this end, energy in these sensors is a scarce resource and must be managed in an efficient manner. In this chapter we propose Hierarchical Adaptive Balanced energy efficient Routing Protocol (HABRP) to decrease probability of failure nodes and to prolong the time interval before the death of the first node (stability period) and increasing the lifetime in heterogeneous WSNs, which is crucial for many applications. We study the impact of heterogeneity of nodes, in terms of their energy, in wireless sensor networks that are hierarchically clustered. In these networks some high-energy nodes called NCG nodes (Normal node|Cluster Head| Gateway) are elected “cluster heads” to aggregate the data of their cluster members and transmit it to the chosen “Gateways” that requires the minimum communication energy to reduce the energy consumption of cluster head and decrease probability of failure nodes and properly balance energy dissipation. Simulation result shows an improvement in effective network lifetime and increased robustness of performance in the presence of energy heterogeneity.

The organization of this chapter is as followings: We briefly review related work in section 2. Section 3 describes heterogeneous sensor network. Sensor network models is analysed in section 4. In section 5, we present our HABRP protocol. Simulation results of the proposed protocol are discussed in terms of energy consumption, Length of stable region for different values of heterogeneity, number of alive nodes per round, variation of the Base Station location, sensitivity to degree of heterogeneity in large scale networks, improvement of stability period in section 6. Finally, in section 7, we conclude the chapter.

2. Related works

The main aim of hierarchical routing is to efficiently maintain the energy consumption of sensor nodes by involving them in multi-hop communication within a particular cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the sink.

LEACH (W. Heinzelman et al., 2000) is one of the first hierarchical routing approaches for sensors networks. The idea proposed in LEACH has been an inspiration for many hierarchical routing protocols. We explore recent works in this section.

2.1. Low-energy adaptive clustering hierarchy (LEACH)

Low-energy adaptive clustering hierarchy (LEACH) (W. Heinzelman et al., 2000) is one of the most popular hierarchical routing algorithms for sensor networks. The idea is to form clusters of the sensor nodes based on the received signal strength and use local cluster heads as routers to the sink. This will save energy since the transmissions will only be done by such cluster heads rather than all sensor nodes.

All the data processing such as data fusion and aggregation are local to the cluster. Cluster heads change randomly over time in order to balance the energy dissipation of nodes. This decision is made by the node $\mathrm{S}$choosing a random number $\mathrm{x}$between 0 and 1. The node becomes a cluster head for the current round if the number $\mathrm{x}$is less than the following threshold:

$$\mathrm{T}\left(\mathrm{S}\right)=\left\{\begin{array}{c}\frac{\mathrm{P}}{1-\mathrm{P*}\left(\mathrm{r\; mod}\frac{1}{\mathrm{P}}\right)}\mathrm{if\; S\; Г\; G}\\ 0\mathrm{otherwise}\end{array}\right.$$E1

Where $P$is desired percentage of cluster head nodes in the sensor network, $r$is current round number, and $G$is the set of nodes that have not been cluster heads in the last $1/p$rounds.

Figure 1.

Network model with clustering

LEACH achieves over a factor of 7 reduction in energy dissipation compared to direct communication and a factor of 4–8 compared to the minimum transmission energy routing protocol (Akkaya & Younis, 2005). The nodes die randomly and dynamic clustering increases lifetime of the system. LEACH is completely distributed and requires no global knowledge of network. However, LEACH uses single-hop routing where each node can transmit directly to the cluster-head and the sink. Therefore, it is not applicable to networks deployed in large regions. Furthermore, the idea of dynamic clustering brings extra overhead, e.g. Head changes, advertisements etc., which may diminish the gain in energy consumption.

2.2. Power-Efficient Gathering in Sensor Information Systems (PEGASIS)

This is improved version from LEACH. The main idea of PEGASIS (Lindsey & Raghavendra, 2002) is that nodes are formed into a chain where each node receive from and transmit to closest neighbor only. The distance between sender and receiver is reduced as well as decreasing the amount of transmission energy. To construct a chain, PEGASIS uses a greedy algorithm that starts from the farthest node from the base station.

Figure 2.

Chain is constructed using the greedy algorithm

In Fig.2, the algorithm starts with node 0 that connects to node 3. Then, node3 connects to node 1 and node 1 connects to node 2, which is the closest one to the base station$\mathit{BS}$. Because nodes already in the chain cannot be revisited, the neighbor distance will increase gradually. When a node dies (out of battery), the chain will be reconstructed by repeating the same procedure to bypass the dead node.

In one round of transmission, a randomized node is appointed to be the leader to transmit data to$\mathit{BS}$. If the $\mathit{BS}$locates outside the range of this node, multi-hop transmission will be employed. The leader will be changed randomly in every round, so that overall energy dissipation is balanced out. For transmitting a packet in each round, a token is used that passing from the one end of the chain to the other end of the chain. Only node that has a token can transmit a data packet to its intermediate node in the chain. When intermediate node receives data from one neighbor along with a token, it fuses the data packet with its own data and transmits a new data packet to the next node in the chain.

Figure 3.

Token passing approach in PEGASIS

In fig.3, C0 will pass its data and token to C1. C1 fuses a data packet with its own data and pass a new data packet to the leader C2. C2 does not transmit a data packet to BS yet, but rather it passes a token to C4. When C2 receives a data from C4 and C3, it fuses and transmits the sensed data to BS.

2.3. A Stable Election Protocol (SEP)

A Stable Election Protocol (SEP) (G. Smaragdakis et al, 2004) is improved version of LEACH protocol. Main aim of it was used heterogeneous sensor in wireless sensor networks. This protocol have operation like LEACH but with this difference that, in SEP protocol sensors have two different level of energy. SEP based on weighted election probabilities of each node to become cluster head according to their respective energy. This approach ensures that the cluster head election is randomly selected and distributed based on the fraction of energy of each node assuring a uniform use of the nodes energy.

In SEP, two types of nodes (normal and advanced) are considered. It is based on weighted election probabilities of each node to become cluster head according to the remaining energy in each node. This prolongs the stability period i.e. the time interval before the death of the first node.

2.4. Distributed energy efficient clustering algorithm for heterogeneous wireless sensor networks

(Qing et al, 2006) proposed a distributed energy efficient clustering scheme for heterogeneous wireless sensor networks, which is called DEEC. In DEEC, the cluster heads are elected by a probability based on the ratio between residual energy of each node and the average energy of the network. The epochs of being cluster heads for nodes are different according to their initial and residual energy.

The authors have assumed that all the nodes of the sensor network are equipped with different amount of energy, which is a source of heterogeneity. DEEC is also based on LEACH protocol, it rotates the cluster head role among all nodes to expend energy uniformity.

Two levels of heterogeneous nodes are considered in the algorithm and after that a general solution for multi-level heterogeneity is obtained. To avoid that each node needs to know the global knowledge of the networks, DEEC estimates the ideal value of network lifetime, which is used to compute the reference energy that each node should expend during a round. Simulation results show that DEEC achieves longer lifetime and more effective messages than LEACH, SEP and LEACH -E.

2.5. Improved and balanced LEACH for heterogeneous wireless sensor networks

(S. Ben alla et al. 2010) proposed Improved and Balanced LEACH (IB-LEACH), in which some high energy nodes elect themselves to be gateway at any given time with a certain probability. Base station confirms that whether those nodes suit to be gateway. These nodes broadcast their status to the other sensors in the network using advertisement message (ADV). The non -gateway nodes elect themselves to be cluster heads with a certain probability. These cluster head nodes broadcast their status to the other sensors in the network using advertisement message (ADV). The non-cluster head nodes wait the cluster head announcement from other nodes. Each sensor node determines to which cluster it wants to belong by choosing the cluster head that requires the minimum communication energy, and send the join -request (Join- REQ) message to the chosen cluster head, and the cluster head nodes wait for join-request message from other nodes.

Each cluster head collect and aggregate the data of their cluster members and transmit it to the chosen gateways that requires the minimum communication energy to reduce the energy consumption of cluster head and decrease probability of failure nodes. Simulation results show that this protocol performs better than LEACH and SEP in terms of network lifetime.

2.6. Cluster head relay routing protocol for heterogeneous sensor networks

(Du & Lin, 2005) proposed a cluster head relay (CHR) routing protocol for heterogeneous sensor networks. This protocol uses two types of sensors to form a heterogeneous network with a single sink: a large number of low-end sensors, denoted by L-sensors, and a small number of powerful high-end sensors, denoted by H-sensors. Both types of sensors are static and aware of their locations using some location service. Moreover, both L-sensor and H-sensors are uniformly and randomly distributed in the sensor field.

The CHR protocol partitions the heterogeneous network into clusters, each being composed of L-sensors and led by an H-sensor. Within a cluster, the L-sensors are in charge of sensing the underlying environment and forwarding data packets originated by other L-sensors toward their cluster head in a multi-hop transmission. The H-sensors, on the other hand, are responsible for data fusion within their own clusters and forwarding aggregated data packets originated from other cluster heads toward the sink in a multi-hop transmission using only cluster heads. While L-sensors use short-range data transmission to their neighboring H -sensors within the same cluster, H-sensors perform long-range data communication to other neighboring H-sensors and the sink. Simulation results demonstrate that CHR performs better than directed diffusion and SWR.

2.7. Energy efficient cluster head election protocol for heterogeneous wireless sensor networks

(LI Han, 2010) proposed an energy efficient cluster head election protocol for heterogeneous wireless sensor networks and using the improved Prim's algorithm to construct an inter cluster routing. He has considered three types of sensor nodes. Some fraction of the sensor nodes are equipped with the additional energy resources than the other nodes. He has assumed that all the sensor nodes are uniformly distributed.

In this protocol, the cluster head node sets up a TDMA schedule and transmits this schedule to the nodes in the cluster. This ensures that there are no collisions among data messages and also allows the radio components of each non-cluster head node to be turned off at all times except during their transmit time, thus minimizing the energy dissipated by the individual sensors.

In order to reduce the energy consumption of the cluster heads which are far away from the base station and balance the energy consumption of the cluster heads which are close to the base station, a multi-hop routing algorithm of cluster head has been presented, which introduces into the restriction factor of remainder energy when selects the interim nodes between cluster heads and base station, and also the minimum spanning tree algorithm has been included. The protocol can not only reduce the consumption of transmit energy of cluster head, but also the consumption of communication energy between non-cluster head and cluster head nodes. Simulation results show that this protocol performs better than LEACH and EECHE in terms of network lifetime.

3. Heterogeneous wireless sensor networks

This section presents a paradigm of heterogeneous wireless sensor network and discusses the impact of heterogeneous resources (Yarvis,2005)( V. Katiyar, 2011)

3.1. Types of heterogeneous resources

There are three common types of resource heterogeneity in sensor nodes: computational heterogeneity, link heterogeneity and energy heterogeneity.

Computational heterogeneity means that the heterogeneous node has a more powerful microprocessor and more memory than the normal node. With the powerful computational resources, the heterogeneous nodes can provide complex data processing and longer-term storage.Link heterogeneity means that the heterogeneous node has high bandwidth and long- distance network transceiver than the normal node. Link heterogeneity can provide a more reliable data transmission.Energy heterogeneity means that the heterogeneous node is line powered or its battery is replaceable.

Among above three types of resource heterogeneity, the most important resource heterogeneity is the energy heterogeneity because both computational heterogeneity and link heterogeneity will consume more energy resource.

If there is no energy heterogeneity, computational heterogeneity and link heterogeneity will bring negative impact to the whole sensor network, i.e., decreasing the network lifetime.

3.2. Impact of heterogeneity on wireless sensor networks

Placing few heterogeneous nodes in the sensor network can bring following benefits:

Decreasing latency of data transportation: Computational heterogeneity can decrease the processing latency in immediate nodes and link heterogeneity can decrease the waiting time in the transmitting queue. Fewer hops between sensor nodes and sink node also mean fewer forwarding latency.Prolonging network lifetime: The average energy consumption for forwarding a packet from the normal nodes to the sink in heterogeneous sensor networks will be much less than the energy consumed in homogeneous sensor networks.Improving reliability of data transmission: It is well known that sensor network links tend to have low reliability and each hop significantly lowers the end-to-end delivery rate.

With heterogeneous nodes, there will be fewer hops between normal sensor nodes and the sink. So the heterogeneous sensor network can get much higher end-to-end delivery rate than the homogeneous sensor network.

3.3. Performance measures

Some performance measures that are used to evaluate the performance of clustering protocols are listed below(R. Sheikhpour et al., 2011).

Network lifetime (stability period): It is the time interval from the start of operation (of the sensor network) until the death of the first alive node.Number of cluster heads per round: Instantaneous measure reflects the number of nodes which would send directly to the base station, information aggregated from their cluster members.Number of alive nodes per round: This instantaneous measure reflects the total number of nodes and that of each type that has not yet expended all of their energy.Throughput: This includes the total rate of data sent over the network, the rate of data sent from cluster heads to the base station as well as the rate of data sent from the nodes to their cluster heads.

Figure 4 shows the heterogeneous model for wireless sensor ne twork.

Figure 4.

Heterogeneous model for wireless sensor network.

4. Wireless sensor network models

4.1. Network model

In this chapter we assume a sensor network model with following properties:

• The sink locates at the centre of sensor nodes and has enough memory and computing capability.

• The WSNs consist of the heterogeneous sensor nodes. Percentage of sensor nodes are equipped with more energy resources than the rest of the nodes. Let $m$be the fraction of the total number of nodes $N$which are equipped with $a$times more energy than the others.

• The distance can be measured based on the wireless radio signal power.

• All sensor nodes are immobile and have a limited energy.

• All nodes are equipped with power control capabilities to vary their transmitting power.

4.2. Radio energy dissipation model

For this project, three routing protocols, namely LEACH and SEP and our protocol Hierarchical Adaptive Balanced energy efficient Routing Protocol (HABRP), We use the same radio model shown in Fig.5 for the radio hardware energy dissipation in order to achieve an acceptable Signal-to-Noise Ratio (SNR) in transmitting a $k$bit message over a distance$d$.

Figure 5.

Radio Energy Dissipation Model.

In Fig.5 $k$is the number of bits per packet transmission and $d$is distance between the sender and the receiver. Electronics energy consumption is same for transmitting and receiving the data, is given by,

$$E_{\mathit{Tx}}\left(k\right)=E_{\mathit{Rx}}\left(k\right)=E_{\mathit{elec}}\mathrm{*}k$$E2

$E$_elec is the energy dissipated per bit to run the transmitter or the receiver circuit.

Transmission cost to transmit $K$-bit message between any two nodes over distance $d$is given by the following equation:

$$E_{\mathit{Tx}}\left(k,d\right)=E_{\mathit{elec}}\mathrm{*}k+E_{\mathit{amp}}(k,d)\mathrm{}$$E3

$E_{\mathit{am}p}\left(k,d\right)$is the amplifier energy consumption and it can be further expressed in terms of $ϓ$_fs or $ϓ$_mp, depending on the transmitter amplifier mode that applied. They are power loss factors for free space (d² loss) when d < d₀; and multipath fading (d⁴ loss) when d ≥ d0, respectively.

To transmit $k$-bit message within d distance, a node expends:

$$\mathrm{}{E}_{\mathit{Tx}}\mathrm{}\left(k,d\right)=\left\{\begin{array}{c}\left(E_{\mathit{elec}}\mathrm{*}k\right)+\mathrm{}\left({ϓ}_{\mathit{fs}}\mathrm{*}k\mathrm{*}{d}^2\right)\mathrm{}\mathit{if}\mathrm{}d≣d_0\\ \left(E_{\mathit{elec}}\mathrm{*}k\right)+\mathrm{}\left({ϓ}_{\mathit{mp}}\mathrm{*}k\mathrm{*}{d}^4\right)\mathrm{}\mathit{if}\mathrm{}d>d_0\end{array}\right.$$E4

By equating the two expressions at d=d_o, we have:

$$d_0=\sqrt{\frac{{ϓ}_{\mathit{fs}}}{{ϓ}_{\mathit{mp}}}}$$E5

To receive a $k$-bit message, a node expends:

$$E_{\mathit{Rx}}\left(k\right)=E_{\mathit{elec}}\mathrm{*}k$$E6

Where E_elec is the energy used by the receiver electronics.

4.3. Optimal number of cluster

We assume there are $N$nodes distributed uniformly in $\mathit{MxM}$region. If there are $C$clusters, there are on average $N/C$nodes per cluster. Each cluster-head dissipates energy receiving signals from the nodes, beamforming the signals, and transmitting the aggregate signal to the base station. Therefore, the energy dissipated in the cluster-head node during a single frame is:

$$E_{\mathit{CH}}=\left[k\mathrm{*}{E}_{\mathit{elec}}\mathrm{*}\frac{N}{C}\right]+\left[k\mathrm{*}{E}_{\mathit{DA}}\mathrm{*}\frac{N}{C}\right]+[k\mathrm{*}{E}_{\mathit{elec}}+k\mathrm{*}{ϓ}_{\mathit{mp}}\mathrm{*}{d}_{\mathit{toBS}}^4]\mathrm{}$$E7

Where $\mathrm{k\; *\; E}\mathrm{elec}\mathrm{*}(\frac{\mathrm{N}}{\mathrm{C}}-1)\mathrm{}$is the energy consumed by the cluster head to receive $k$bits information from $\left(\frac{\mathrm{N}}{\mathrm{C}}-1\right)\mathrm{}$non cluster heads and $E$_DA represents the processing of data aggregation cost of a bit per signal. The expression for the energy spends by a non cluster head is given by:

$$E_{\mathit{non}-\mathit{CH}}=k\mathrm{*}{E}_{\mathit{elec}}+k\mathrm{*}{ϓ}_{\mathit{fs}}\mathrm{*}{d}_{\mathit{toCH}}^2\mathrm{}$$E8

Where $d_{\mathit{toCH}}^{}$ is the distance from the node to the cluster head. The area occupied by each cluster is approximately$\raisebox{1ex}{$M^2$}\!\left/ \!\raisebox{-1ex}{$C$}\right.$. In general, this is an arbitrary-shaped region with a node distribution$ϟ\left(x,y\right)$.

The expected squared distance from the nodes to the cluster head (assumed to be at the center of mass of the cluster) is given by:

$$d_{\mathit{toCH}}^2=\int \left(\left(x^2+y^2\right)\mathrm{*}ϟ\left(x,y\right)\right)\mathit{dx}\mathit{dy}=\int r^2ϟ\left(r,\varpi \right)r\mathit{dr}\mathit{d\varpi }$$E9

If we assume this area is a circle with radius $R=\raisebox{1ex}{$(M$}\!\left/ \!\raisebox{-1ex}{$\sqrt{\mathit{ϞC})}$}\right.$and $ϟ\left(r,\varpi \right)$is constant for $r$and$\varpi$, (9) simplifies to:

$$d_{\mathit{toCH}}^2=ϟ{\cup }_{\varpi }^{=}{\cup }_r^{=}{r}^3\mathit{dr}\mathit{d\varpi }=\frac{ϟ}{2Ϟ}\mathrm{}\frac{M^4}{C^2}$$E10

If the density of nodes is uniform throughout the cluster area, then $ϟ=\raisebox{1ex}{$(1$}\!\left/ \!\raisebox{-1ex}{$(\raisebox{1ex}{$M^2$}\!\left/ \!\raisebox{-1ex}{$C\left)\right)$}\right.$}\right.$and

$$d_{\mathit{toCH}}^2=\frac{1}{2Ϟ}\mathrm{}\frac{M^2}{C}$$E11

Therefore, in this case the expression for the energy spends by a non cluster head is:

$$E_{\mathit{non}-\mathit{CH}}=k\mathrm{*}{E}_{\mathit{elec}}+k\mathrm{*}{ϓ}_{\mathit{fs}}\mathrm{*}\frac{1}{2Ϟ}\mathrm{}\frac{M^2}{C}$$E12

The energy dissipated in a cluster per round, $E$_cluster, is expressed by:

$$E_{\mathit{cluster}}=E_{\mathit{CH}}+\mathrm{}\left(\frac{N}{C}-1\right)\mathrm{*}{E}_{\mathit{non}-\mathit{CH}}\ncong \mathrm{}{E}_{\mathit{CH}}+\mathrm{}\frac{N}{C}\mathrm{*}{E}_{\mathit{non}-\mathit{CH}}$$E13

Therefore, the total energy dissipated in the network per round, $E$_total, is expressed by:

$$E_{\mathit{total}}={C\mathrm{*}E}_{\mathit{cluster}}$$E14

We can find the optimum number of clusters by setting the derivative of $E_{\mathit{total}}$ with respect to $C$to zero (W.Heinzelman et al., 2002):

$$\frac{\complement E_{\mathit{total}}}{\complement C}=0\mathrm{}$$E15

$$C_{\mathit{opt}}=\sqrt{\frac{N}{2Ϟ}\mathrm{}}\mathrm{}\sqrt{\frac{{ϓ}_{\mathit{fs}}}{{ϓ}_{\mathit{mp}}}}\mathrm{}\frac{M}{d_{\mathit{toBS}}^2}$$E16

The optimal probability of a node to become a cluster head, $P_{\mathit{opt}}$, can be computed as follows:

$$P_{\mathit{opt}}=\frac{C_{\mathit{opt}}}{N}$$E17

The optimal probability for a node to become a cluster head is very important. The authors (W.Heinzelman et al., 2000) showed that if the clusters are not constructed in an optimal way, the total consumed energy of the sensor network per round is increased exponentially either when the number of clusters that are created is greater or especially when the number of the constructed clusters is less than the optimal number of clusters.

5. Hierarchical Adaptive Balanced energy efficient Routing Protocol (HABRP)

In this section we describe HABRP which is an extension of the LEACH, which improves the stability period of the clustering hierarchy and decrease probability of failure nodes using the characteristic parameters of heterogeneity.

Routing in HABRP works in rounds and each round is divided into two phases, the Setup phase and the Steady State phase, each sensor knows when each round starts using a synchronized clock. Let us assume the case where a percentage of sensor nodes are equipped with more energy resources(advanced nodes) than the rest of the nodes (normal nodes). We refer to these powerful nodes as $\mathit{NCG}$nodes (nodes selected as normal nodes or cluster heads or gateways). Let $\mathrm{m}$be the fraction of the total number of nodes $\mathrm{N}$which are equipped with $a$times more energy than the others and the rest $\left(1-m\right)\mathit{*N}$as normal nodes and $E_0$ the initial energy. We assume that all nodes are distributed uniformly over the sensor field. The total number of nodes and total energy in network is expressed by:

$$\begin{array}{l}N=N*m\left[NCG nodes\right]+ N*\left(1-m\right)\left[normal nodes\right]\\ \\ E\left[total\right]=N*m*E_0*\left(1+a\right)+ N*\left(1-m\right)* E_0\end{array}$$E18

5.1. HABRP network model

The basic system model of the protocol HABRP is depicted in Fig.6. Each sensor node sends the sensed data to its cluster head. The cluster head aggregates the collected data and transmits the aggregated information to closest gateway that will send data to the base station.

Figure 6.

The HABRP Network model

The operation of HABRP is divided into rounds. Each round begins with a set-up phase followed by a steady-state phase, as shown in Fig.7.

Figure 7.

Time line showing HABRP operation

During the set-up phase the gateways are elected and the clusters are organized. It is constituted by gateway selection algorithm, cluster selection algorithm and cluster formation algorithm.

Figure 8.

Time line showing set-up phase

After the set-up phase is the steady-state phase when data are transmitted from the nodes to the cluster head to agregate data and transmit it to the base station through the gateway that requires the minimum communication energy. The duration of the steady phase is longer than the duration of the setup phase in order to minimize overhead.

5.2. Gateway selection algorithm

Each sensor $S$elects it self to be a gateway at the beginning of each round, round. This decision is based on the suggested percentage of gateways for the network (determined a priori) and the number of rounds the node has been a gateway so far. The desired percentage of gateways is chosen such that the expected number of gateway nodes for each round is$Ng$. Thus, if there are $\mathit{N*m}$$\mathit{NCG}$ nodes (advanced nodes) in the network, the desired percentage of gateways is:

$$P_g=\frac{N_g}{N\mathrm{*}m}$$E19

Decision to become gateway is made by the node $S$choosing a random number $x$between 0 and 1. The node becomes a gateway for the current round if the number $x$is less than the following threshold:

$$\mathrm{T}\left({\mathrm{S}}_{\mathrm{gat}}\right)=\left\{\begin{array}{c}\frac{{\mathrm{P}}_{\mathrm{g}}}{1-{\mathrm{P}}_{\mathrm{g}}\mathrm{*}\left(\mathrm{r\; mod}\frac{1}{{\mathrm{P}}_{\mathrm{g}}}\right)}\mathrm{*}\frac{{\mathrm{E}}_{\mathrm{s\_current}}}{{{\mathrm{E}}_{\mathrm{s\_initial}}}_{\mathrm{}}}\mathrm{if\; S}\nabla {\mathrm{G}}_{\mathrm{gat}}\\ 0\mathrm{otherwise}\end{array}\right.$$E20

We define as $T(S$_gat$)$ the threshold for gateway node$S$, $r$is the currenet round, $G$_gat is set of nodes which have not been gateways in $1/P$_g rounds, ${\mathrm{E}}_{\mathrm{s\_current}}$is the current energy of the node and ${\mathrm{E}}_{\mathrm{s\_initial}}$ is the initial energy of the node.

5.3. Cluster head selection algorithm

The main idea is for the sensor nodes to elect themselves with respect to their energy levels autonomously. The goal is to minimize communication cost and maximizing network resources in other to ensure concise information is sent to the sink. Each node transmits data to the closest cluster head and the cluster heads performs data aggregation. Assume an optimal number of clusters $C_{\mathit{opt}}$ in each round. It is expected that as a cluster head, more energy will be expended than being a cluster member. Each node can become cluster head with a probability $P_{\mathit{opt}}$ and every node must become cluster head once every $1/\mathrm{}{P}_{\mathit{opt}}$ rounds.

The optimal probability of a node to become a cluster head, $P_{\mathit{opt}}$, can be computed as follows:

$$P_{\mathit{opt}}=\frac{C_{\mathit{opt}}}{N-Ng}$$E21

$Ng$is a number of gateway nodes, $C_{\mathit{opt}}$is the optimum number of clusters that is expressed by:

$$C_{\mathit{opt}}=\sqrt{\frac{N-Ng}{2Ϟ}\mathrm{}}\mathrm{}\sqrt{\frac{{ϓ}_{\mathit{fs}}}{{ϓ}_{\mathit{mp}}}}\mathrm{}\frac{M}{d_{\mathit{toBS}}^2}$$E22

Our approach is to assign a weight to the optimal probability${\mathit{P}}_{\mathit{opt}}$. This weight must be equal to the initial energy of each node divided by the initial energy of the normal node. Let us define as $P_{\mathit{nrm}}$ the weighted election probability for normal nodes, and $P_{\mathit{adv}}$ the weighted election probability for the advanced nodes.

Virtually there are $\mathit{N*}(1+\mathit{a*m})$nodes with energy equal to the initial energy of a normal node. In order to maintain the minimum energy consumption in each round within an epoch, the average number of cluster heads per round per epoch must be constant and equal to$C_{\mathit{opt}}$. The weighed probabilities for normal and advanced nodes are, respectively:

$$P_{\mathit{nrm}}=\frac{P_{\mathit{opt}}}{1+a\mathrm{*}m}$$E23

$$P_{\mathit{adv}}=\frac{P_{\mathit{opt}}}{1+a\mathrm{*}m}\mathrm{*}(1+a)$$E24

In Equation (1), we replace $P_{\mathit{opt}}$ by the weighted probabilities to obtain the threshold that is used to elect the cluster head in each round.

We define as $\mathrm{T}\left({\mathrm{S}}_{\mathrm{nrm}}\right)\mathrm{}$the threshold for normal nodes, and $\mathrm{T}\left({\mathrm{S}}_{\mathrm{adv}}\right)\mathrm{}$the threshold for advanced nodes. Thus, for normal nodes, we have:

$$\mathrm{T}\left({\mathrm{S}}_{\mathrm{nrm}}\right)=\left\{\begin{array}{c}\frac{{\mathrm{P}}_{\mathrm{nrm}}}{1-{\mathrm{P}}_{\mathrm{nrm}}\mathrm{*}\left(\mathrm{r\; mod}\frac{1}{{\mathrm{P}}_{\mathrm{nrm}}}\right)}\mathrm{*}\frac{{\mathrm{E}}_{\mathrm{s\_current}}}{{\mathrm{E}}_{{\mathrm{s}}_{\mathrm{initial}}\mathrm{}}}\mathrm{if}{\mathrm{S}}_{\mathrm{nrm}}\nabla {\mathrm{G}}_{\mathrm{nrm}}\\ 0\mathrm{otherwise}\end{array}\right.$$E25

Where $r$is the current round$,{\mathrm{G}}_{\mathrm{nrm}}\mathrm{}$is the set of normal nodes that have not become cluster heads within the last $1/{\mathrm{P}}_{\mathrm{nrm}}$ rounds of the epoch and $\mathrm{T}\left({\mathrm{S}}_{\mathrm{nrm}}\right)$is the threshold applied to normal nodes.

Similarly, for advanced nodes, we have:

$$\mathrm{T}\left({\mathrm{S}}_{\mathrm{adv}}\right)=\left\{\begin{array}{c}\frac{{\mathrm{P}}_{\mathrm{adv}}}{1-{\mathrm{P}}_{\mathrm{adv}}\mathrm{*}\left(\mathrm{r\; mod}\frac{1}{{\mathrm{P}}_{\mathrm{adv}}}\right)}\mathrm{*}\frac{{\mathrm{E}}_{\mathrm{s\_current}}}{{\mathrm{E}}_{{\mathrm{s}}_{\mathrm{initial}}\mathrm{}}}\mathrm{if}{\mathrm{S}}_{\mathrm{adv}}\nabla {\mathrm{G}}_{\mathrm{adv}}\\ 0\mathrm{otherwise}\end{array}\right.$$E26

Where$\mathit{r}$ is the current round, ${\mathrm{G}}_{\mathrm{adv}}$is the set of advanced nodes that have not become cluster heads within the last $1/{\mathrm{P}}_{\mathrm{adv}}$ rounds of the epoch, and $\mathrm{T}\left({\mathrm{S}}_{\mathrm{adv}}\right)$is the threshold applied to advanced nodes.

5.4. Summary of HABRP

HABRP is a self-organizing, adaptive clustering protocol that uses randomization to distribute the energy load evenly among the sensors in the network. Each sensor elects it self to be a gateway at the beginning of each round with a certain probability.

These gateway nodes broadcast their status to the other sensors in the network using advertisement message (ADV). The non-gateway nodes elect themselves to be cluster-heads with a certain probability.

These cluster-head nodes broadcast their status to the other sensors in the network using advertisement message (ADV). The non-cluster-head nodes wait the cluster-head announcement from other nodes. Each sensor node determines to which cluster it wants to belong by choosing the cluster-head that requires the minimum communication energy, and send the join-request (Join-REQ) message to the chosen cluster head, and the cluster-head nodes wait for join-request message from other nodes.

Once all the nodes are organized into clusters, each cluster-head creates a schedule for the nodes in its cluster. This allows the radio components of each non-cluster-head node to be turned off at all times except for its transmit time, thus minimizing the energy dissipated in the individual sensors. Once the cluster-head has all the data from the nodes in its cluster, the cluster-head node aggregates the data and then transmits the compressed data:

• To the chosen gateway that requires the minimum communication energy to reduce the energy consumption of cluster head and decrease probability of failure nodes if :

$$E_{\mathit{CH}\mathrm{\_}\mathit{to}\mathrm{\_}\mathit{BS}}>E_{\mathit{CH}\mathrm{\_}\mathit{to}\mathrm{\_}\mathit{Gat}}+\mathrm{}{E}_{\mathit{Gat}\mathrm{\_}\mathit{to}\mathrm{\_}\mathit{BS}}$$E27

These collected data are transmitted to the base station using cluster head-gateway-base station routing.

• To the Base station directly if :

$$E_{\mathit{CH}\mathrm{\_}\mathit{to}\mathrm{\_}\mathit{BS}}\mathrm{}≣\mathrm{}{E}_{\mathit{CH}\mathrm{\_}\mathit{to}\mathrm{\_}\mathit{Gat}}+\mathrm{}{E}_{\mathit{Gat}\mathrm{\_}\mathit{to}\mathrm{\_}\mathit{BS}}$$E28

Where $E_{\mathit{CH\_to\_BS}}$ is total energy dissipated for send data from cluster head to the base station and $E_{\mathit{CH\_to\_Gat}}$is total energy dissipated for send data from cluster head to the Gateway and $E_{\mathit{Gat\_to\_BS}}$ is total energy dissipated for send data from Gateway to the base station as shown in Fig.9.

Figure 9.

Cluster head would transmit to Base Station through Gateway if $E_{\mathit{CH\_to\_Gat}}+E_{\mathit{Gat\_to\_BS}}{<\mathit{E}}_{\mathit{CH\_to\_BS}}$

6. Simulation

6.1. Parameter settings

We use a 100m×100m region of 100 sensor nodes scattered randomly. MATLAB is used to implement the simulation. To make a fair comparison, we introduce advanced energy levels to LEACH and SEP nodes with same settings as in our HABRP protocol, so as to assess the performance of these protocols in the presence of heterogeneity.

Specifically, we have the parameter settings:

Notation	Description	Value
M x M	Area	100x100, 300x300
N	Number of the sensors	100, 900
sinkX, sinkY	Sink node location	50x50, 50x200,; 50x300, 300x300
E0	Initial energy	0.5 J
Eelec	Electronics energy	50nJ/bit
EDA	Energy of data aggregation	5nJ/bit
d0	The threshold distance	87m
εfs	Amplified transmitting energy using free space	10pJ/bit/ m 2
εmp	Amplified transmitting energy using multipath	0.0013pJ/bit/ m4
k	Data packet size	500bytes
kbroad	Broadcast packet size	25 bytes
Popt	Probability	0.05
Copt	optimum number of clusters	5
Ng	number of gateway nodes	4

Table 1.

Simulation parameter

6.2. Simulation metrics

Performance metrics used in the simulation study are:

• Energy consumption analysis

• Length of stable region for different values of heterogeneity. Stability period is the period from the start of the network operation and the first dead node. We also refer to this period as “stable region”

• Number of alive nodes per round.

• Percentage of Node death

• Variation of the Base Station Location

• Sensitivity to degree of heterogeneity in large-scale networks.

• Improvement of Stability period:

$$\mathit{Improvement}=\frac{\mathit{Stable}\mathrm{}\mathit{period}\mathrm{}\mathit{of}\mathrm{}\mathit{HABRP}-\mathit{Stable}\mathrm{}\mathit{period}\mathrm{}\mathit{of}\mathrm{}\mathit{LEACH}}{\mathit{Stable}\mathrm{}\mathit{period}\mathrm{}\mathit{of}\mathrm{}\mathit{LEACH}}$$E29

6.3. Simulation results

6.3.1. Energy consumption analysis

The performance of HABRP is compared with that of the original LEACH and SEP in terms of energy and is shown in Fig.10 and Fig.11.

With the use of gateway nodes for data transmission from cluster heads to the sink, the energy consumption of the network is decreased. This is due to the gain of the energy dissipated by cluster heads to the base station. From the graph it is clear that HABRP can achieve twice the energy savings than LEACH and SEP protocol.

Fig.10 illustrates the energy performance of HABRP in homogeneous WSNs.

Figure 10.

Energy analysis comparison of HABRP, LEACH and SEP in Homogeneous WSN (100m x 100m, 100 nodes, 0.5J/node, a=0(Homogeneous WSNs))

Fig.11 illustrates the energy performance of HABRP in heterogeneous WSNs.

6.3.2. Network lifetime

The number of nodes alive for each round of data transmission is observed for the HABRP protocol to evaluate the lifetime of the network. Fig.12 shows the performance of HABRP compared to LEACH and SEP. It is observed that the HABRP outperforms LEACH and SEP due to balanced energy dissipation of individual node through out the network.

Figure 11.

Energy analysis comparison of HABRP, LEACH and SEP (100m x 100m, 100 nodes, 0.5J/node, m=0.2, a=3(Heterogeneous WSNs))

Figure 12.

Number of alive nodes per round with 100m x 100m, 100 nodes, 0.5J/Normal node, 1J/Advanced node m=0.2, a=1, BS(50,50)

6.3.3. Variation of the Base Station Location

The results presented in the previous section show that HABRP is more energy-efficient than LEACH and SEP routing. Is this just a function of the simulation parameters? What happens if the base station is actually located within the network or very far away from the network? To answer these questions, we ran simulations where we varied the location of the base station from (x= 50, y= 50) to (x =50, y=300).

Figure 13.

Number of alive nodes per round with 100m x 100m, 100 nodes, 0.5J/Normal node, 2J/Advanced node, m=0.2, a=3, BS(50,200)

Figure 14.

Number of alive nodes per round with 100m x 100m, 100 nodes, 0.5J/Normal node, 2J/Advanced node, m=0.2, a=3, BS(50,300)

For all base station locations we simulated, as the base station moves further away from the network, the performance of HABRP improves compared to LEACH and SEP.

6.3.4. Percentage of Node death

The number of rounds for 1%, 20%, 50%, 80% of node death is observed for HABRP, LEACH and SEP in Fig.13 and Fig.14. From the results of Fig.13 the stability period of LEACH and SEP protocols is limited to 892 rounds and the HABRP protocol extents up to 1335 rounds in homogeneous WSNs. In heterogeneous WSNs HABRP provides an extended lifetime of approximately twice LEACH protocol. HABRP has longer lifetime than LEACH and SEP.

Figure 15.

Node death percentage per number of Rounds with 100m x 100m, 100 nodes, 0.5J/node, a=0

Figure 16.

Node death percentage per number of Rounds with 100m x 100m, 100 nodes, 0.5J/Normal node, 1.0J/Advanced node m=0.2, a=1

6.3.5. Stable region in heterogeneous WSNs

In fig.15 the length of stable region for differnet values of energy heterogeneity is simulated, we observed that if we increase the number of NCG nodes with$a=1$, the stability period is extended of approximately twice as LEACH protocol. In heterogeneous WSNs, HABRP has longer stable region than LEACH and SEP for differnet values of energy heterogeneity.

Figure 17.

Length of stable region for differnet values of energy heterogeneity with 100m x 100m, 100 nodes, 0.5J/node, a=1

6.3.6. Heterogeneity in large-scale networks

We simulated the performance changes in large network with 900 nodes in area$\mathrm{}300\mathrm{mx}300\mathrm{m}$.

Figure 18.

Sensitivity of HABRP, LEACH and SEP to degree of heterogeneity in large scale networks with 900 nodes in an 300mx300m field.

In Fig.16. the simulation result shows, that the network lifetime decrease in large area network and the period that the first dead node appears is earlier than those of previous cases. The phenomenon is caused by the fact that the cluster heads waste the considerable amount of energy for transmitting their data to the far away base station. In HABRP cluster head would transmit data to base station through gateway to eliminate that the cluster head far away from the base station dissipate their energy much faster than those close to the BS. HABRP outperforms LEACH and SEP for different values of total additive energy$\mathrm{a*m}$. Because in LEACH and SEP, all cluster heads transmits aggregated data to the BS directly.

6.3.7. Improvement of stability period

The comparison results are shown in Table2. show that HABRP is more energy-efficient and the stability period is extended than LEACH in both homogeneous and heterogeneous WSNs.

FND (First Node Dies)	$\mathbf{a*m}$	LEACH	HABRP	Improvement
0	892	1335	49,66%
0.1	908	1704	87,66%
0.3	1020	1820	78,34%
0.5	1076	1888	75,46%
0.7	1100	1966	78,72%
0.9	1145	2111	84,36%

Table 2.

Improvement of HABRP compared to LEACH with $a=1$

6.4. Result analysis

From our simulations, we observed the followings:

• HABRP can achieve twice the energy savings than LEACH and SEP protocol.

• HABRP outperforms LEACH and SEP due to balanced energy dissipation of individual node through out the network and extends network lifetime.

• For all base station locations we simulated, as the base station moves further away from the network, the energy efficient performance of HABRP improves compared to LEACH and SEP.

• In heterogeneous WSNs, HABRP provides an extended lifetime of approximately twice LEACH protocol and the stability period of the HABRP was prolonged than LEACH and SEP in heterogeneous settings.

• Energy dissipation is balanced between normal nodes and advanced nodes in the HABRP compared to LEACH and SEP.

• Balancing the energy consumption, reducing the phenomenon of rapid death of the cluster head caused by excessive energy consumption, also preventing the situation of instability period caused by one cluster head failure to work, ensure that the network work normally.

• Using gateway and cluster head, it saves excessive energy consumption for long-distance transmission, increased energy utilization of the entire network.

The simulation results show that HABRP protocol could suitably form clusters and effectively prolonging the survival time of the entire networks.

7. Conclusion

Energy efficient routing is paramount to extend the stability and lifetime of the wireless sensor networks. Routing in sensor networks is very challenging due to several characteristics that distinguish them from traditional communications and wireless ad-hoc networks since several restrictions, e.g., limited energy supply, computing power, and bandwidth of the wireless links connecting sensor nodes. The major difference between the WSN and the traditional wireless network is that sensors are very sensitive to energy consumption. Introducing clustering into the networks topology has the goal of reducing the number of message that need to be delivered to the sink in large-scale WSNs.

In this chapter, we have proposed an Hierarchical Adaptive Balanced energy efficient Routing Protocol (HABRP) for wireless sensor networks. The energy efficiency and ease of deployment make HABRP a desirable and robust protocol for wireless sensor networks. In order to improve the lifetime and performance of the network, routing in HABRP works in rounds and each round is divided into two phases, the Set-up phase and the Steady State phase. During the set-up phase some high-energy nodes called NCG nodes are elected gateways, other choised cluter heads and the clusters are organized. During the steady-state phase, data are transmitted from the cluster members nodes to the cluster head to agregate data and transmit it to the base station through a chosen gateways that requires the minimum communication energy to reduce the energy consumption of cluster head and decrease probability of failure nodes.

Simulation results shows that the HABRP improves the stable region of the clustering hierarchy and decrease probability of failure nodes and increase the lifetime of the network due to balanced energy dissipation of individual node through out the network and extends network lifetime. Balancing the energy consumption, reducing the phenomenon of rapid death of the cluster head caused by excessive energy consumption, also preventing the situation of instability period caused by one cluster head failure to work, ensure that the network work normally.

Finally, HABRP is scalable and achieves better performance compared to SEP and LEACH in both heterogeneous and homogenous environments.