a novel energy efficient routing protocol EACBM for scalable wireless sensor networks

Published Online May 2018 in MECS DOI: 10.5815/ijcnis.2018.05.02

Wireless Sensor Networks (WSNs) are distributed networks which grow incredibly for the infrastructure- less environment in which little bandwidth is enough for transmitting data to the destined places and various components are assimilated into a single smaller chip [1]. These include a group of small devices (hundreds or thousands) called Sensor Nodes (SNs) deployed randomly over a field to monitor it, are of low cost and tiny size. Its range depends upon the application in which it is going to be used like in military application, disaster management schemes, security supervision and much more. WSNs face many technical challenges like energy efficient routing, data aggregation techniques, improvement in network lifetime and much more.

The routing algorithms are used for transmitting the important information to the designated places. Now a day’s mostly research on routing algorithms mainly focused on energy efficiency, lifetime, stability, packet delivery rate etc [2]. So, routing algorithm should be designed for WSNs which proficiently uses limited battery power of SNs.

Routing protocols can be classified into flat and hierarchical routing. In flat routing, every SN is assigned the identical role and function whereas, in case of hierarchical routing, they assign different role and function. All these SNs can take part in the process of clustering. In Clustering, SNs are grouped to form clusters and inside each cluster, a node is selected as CH which performs the task of data aggregation and transferring data to BS [15]. The run time of this process is divided into rounds. It is an effective way to reduce the consumption of SNs energy and extend the network lifetime.

This paper is organized as follows; in Section II Related work is provided. The detail description for proposed routing protocol is described in Section III. In Section IV, Simulations and results are discussed in details. Finally, in Section V the conclusion is done.

• II.    Related Work

  LEACH (2000) [4] is the pioneer centralized cluster based routing protocol for homogeneous WSN environment wherein the formation of clusters and the selection of CH is on the basis of probability equation. Also, LEACH provides improvement when compared with direct communication but it fails in the case of heterogeneous WSN.

Stable Election Protocol (SEP) (2004) [5] was first introduced into the study the impact of energy heterogeneity on WSNs and to enhance the stable region. It includes two level of heterogeneity which means it uses 2 types of SNs i.e. Normal SNs and Advance SNs. Advance SNs have more energy with respect to Normal SNs. But its performance decreases to the minimum when more than 2 level of heterogeneity is considered.

Distributed Energy Efficient clustering (DEEC) (2006) [6] was proposed to deal with the challenges of multilevel heterogeneous WSNs. In DEEC algorithm, CHs are selected on the strength of probability equation according to the ratio of remaining energy of each SN and the average energy of the sensor network. Due to this, the network scalability is enhanced when compared with SEP and ESEP.

Multi-hop LEACH (MLEACH) (2007) [7] tries to overcome this issue of LEACH by introducing the concept of scalability along with multi-hop inter-cluster communication. This improvement of MLEACH still it fails to implement it in heterogeneous WSN environment.

Centralized Energy Efficient Clustering (CEEC) (2012) [8] routing protocol is for a three-level heterogeneous network in which entire network is isolated into 3 equal regions and inside each region, SNs having same energy level are deployed. This enhances the lifetime and throughput of the network.

Orphan node LEACH (O-LEACH) (2016) [9] is particular routing protocol which are used for covering SNs which lies far away from CH or where CH cannot reach to collect data because it may be the case that those far away SNs may contain some relevant data which are required in some particular type of application. It outperforms in case of network connectivity between SNs and coverage of whole WSN environment as compared to LEACH and other routing protocols.

Low Energy Fixed Clustering Algorithm (LEFCA) (2016) [10] is an algorithm where clusters are formed in the set-up phase and all SNs which become the member of the particular cluster will remain inside that cluster throughout the lifetime of the network. This enhances the lifetime and decreases the energy dissipation of sensor network.

A state-of-art comparison of these existing cluster based routing protocols is presented in Table 1. The proposed EACBM routing protocol covers all these features like heterogeneity, scalability, multi-hoping, inter-cluster communication, connectivity, tackle unattended area and are well used for large area applications.

• III.    Proposed Routing Protocol

In this, a new energy efficient routing protocol called EACBM for WSNs is proposed with the aim to enhance the network lifetime, scalability, energy efficiency, connectivity, and coverage.

• A.    Assumptions

• •    Every SN should be deployed randomly over an area and are static after deployment.

• •    All SNs have information for BS.

• •    SNs are heterogeneous in nature.

• •    SNs cannot be re-energized after deployment and should be considered dead after depletion of their energy.

• •    One Base Station (BS) should be there in WSN whose position is at the centre of the network and is stationary after its deployment.

Table 1. A state-of-art Comparison of Existing Cluster based Routing Protocols

Features	LEACH	MLEACH	SEP, DEEC	CEEC	O-LEACH	LEFCA
Heterogeneous	No	No	Yes	Yes	No	No
Scalable	No	No	Yes	No	No	No
Tackles unattended area	No	Yes	No	No	Yes	No
Multi-hoping	No	Yes	No	No	No	No
Inter-cluster Communication	No	Yes	No	No	No	No
Connectivity/ Coverage	No	No	No	No	Yes	No
Applicable for large area network	No	No	No	No	No	No

• B.    Basic Concept

The main emphasis during designing of an algorithm is that WSNs are deployed in large area network, so to minimize its SN energy consumption for long distance transmission. Connectivity of SNs with CH is also a concern while designing an algorithm, so that, no SN is left behind which cannot transmit its information to CH. Because it may be the case that, those SNs collect some important information which may be useful for some specific application.

The proposed EACBM routing protocol follows two models; Network model (Cluster formation and CH selection) for Setup phase and Radio energy model (energy consumed during transmission and reception) for Steady-State phase.

1) Network Model

It mainly focuses on the formation of clusters and selection of CH. The network may be defined as a square field in which SNs are uniformly distributed randomly and they became static after its deployment. After that SNs start collecting data from the field according to its sensing features and transmit it to BS.

The basic architecture for proposed approach is as shown below (Fig. 1). Here, all SNs are randomly deployed in network field area and then clusters are formed. There may be the case that some SNs have not joined any cluster due to their far away location. So to cover those SNs, sub-clusters have created. After that data transmission takes place between SNs and CH and then from CH to BS which is explained in detail in the following sections.

is less than EACBM threshold value; only then, in that case, that particular SN will be elected ad CH for that particular round. The new threshold value is given by:

T(n Z ) =

{    1-P Z (

P Z r∗ mod

(1⁄PZ))

∗

[S(i). E]

if n ϵ GZ

(1) otherwise

Cluster

Base Station

Sub-Cluster о   Normal SNs        о Intermediate SNs

• Advance SNs / Cluster Heads

*   Sub- Cluster Heads

PZ is the optimal number of CHs, Z can be Normal (nrm) SNs, Intermediate (int) SNs or Advance (adv) SNs, r means the count of current round, [S(i).E] is current energy of SN and it suggests that high-energy SN should be CH with respect to low energy SNs, G is the set of SNs that had not been selected as CH in the last round P rounds.

As three types of SNs are used, so the reference value for each SN should be specified according to its initial value of energy. So, the probability equation of all three types of SNs should be different and is as follows: i.e.

Fig.1. EACBM Routing Protocol Architecture

The steps followed by EACBM protocol are illustrated in Fig. 2.

The flowchart for EACBM protocol scheme is shown in Fig. 3 having two phases; Setup phase and Steady-state phase.

• Setup phase

In the Setup phase, clusters are formed and a CH is selected for each round. In EACBM protocol; the Setup phase is a little bit different from other cluster based routing protocols in terms of probability equation. It assumes three level heterogeneous WSN containing three different types of SNs having different energy level. SNs are classified into Advance, Intermediate and Normal SNs having Е 0 (1 + а) , Е 0 (1 + в) and Е 0 amount of initial energy respectively and are randomly deployed in the network field. So, the total initial energy of 3 level heterogeneous WSNs is given by: E total = E adv + E int + Е _ nrm .

Each SN generate a random number which lies between 0 and 1 and if that randomly generated number

Randomly Deployment of Sensor Nodes

BS is located at center of Network area

Cluster formation

*     ~

CH selection process based on Probability equation

CH advertise its Id and its status as CH to all SNs to join as cluster member SNs

*        ~

If any SN does not join any cluster any clusters or are not in the coverage range of CH then Create Sub-Cluster

*        ~

Again create Sub-CH in each Sub-cluster

Inside each Sub-cluster, all SNs transmits their data to sub-CH and then Sub-CH transmit data to main CH

*        ~

Data Aggregation takes place at each CH

Aggregated Data is transmitted to BS directly if distance is less then threshold distance otherwise multi-hop data transmission occurs

*        ~

Check CH remaining energy. If it is high, remain it as CH otherwise select new CH

Fig.2. Steps Followed by EACBM Routing Protocol

Steady State Phase                                                        _{Set up Phase}

Fig.3. Set up Phase and Steady-state Phase of EACBM Protocol

P nrm , P int and P adv for Normal, Intermediate and

Advance SNs respectively are:

P opt is the optimal election probability of SN to be CH. α is the energy factor for the Advanced SNs and β is the energy factor Intermediate SNs. With the addition of different energy level of SNs, the new epoch of network will be ^—. (1 + a. m + x. в) . And the number of Normal, Intermediate and Advance SNs will be n.(1-m-x), n.x and n.m respectively.

Once CH is selected, it broadcasts its status of being CH for current round using CSMA MAC protocol. Every SN starts to join CH which lies in its RSSI range which is provided by CH during its cluster formation phase. Then every SN starts sending a message to CH that they want to be the member of that cluster. Finally, CHs generates a TDMA schedule so that every member SN of each cluster can impart their data. This TDMA frame size depends upon the number of member SNs present in particular cluster. Every CH then generates a CDMA code and distributes it to its member SNs so that no inter-cluster interference can be minimized.

Nevertheless, in any round, there may be some SNs which have not attached with any CH because it lies far away from the reach of CH or which cannot be covered in any cluster. In that reason, a new Sub-cluster is created whose aim is to cover these kinds of outside SNs because it might be the case that those outside SNs provide some relevant information which is of great importance in some particular application. So, a Sub-CH is formed in that Sub-cluster which is positioned at the intermediate distance between cluster member SNs and far away outside SNs present in Sub-cluster.

Once clusters and Sub-clusters are created and TDMA schedule frame gets fixed, all cluster and sub-cluster member SNs starts sensing and collecting the data.

• 2)    Radio Energy Model

The Radio energy model defines the amount of energy dissipated during transmitting and receiving of information. Following are the equations that authors used for both free space propagation and multipath propagation in their work for calculating the energy dissipation during transmitting (E_TX) and receiving (E R _X) of K-bit of message over a distance of d [4, 5, 11, 14]. The amount of energy used for free space model is proportional to d² (if d < d₀) and for multipath model is proportional to d⁴ (if d > d₀) because the transmitting signal follows different paths to reach BS.

K. Eelec + K. f d2 if d < do . - .

K. Eelec + K.Emp.d4 if d > d0 (5)

^E TX ^(K, ^d) — {

P    —   Popt nrm   1+a.m+x.g

p _ P opt Cl+P)

^int    1+a.m+x.g

E elec is the energy required per bit to active the transmitter or the receiver circuit, Ɛ fs and Ɛ mp are energy required for amplification of transmitter amplifier model i.e. free space or multipath model respectively.

By equating the equations of ETX(K, d) at d = d0

P adv

P opt(1+a)

1+a.m+x.p

d0=Efsemp

Here, d 0 is threshold distance which specifies the propagation transmission distance from the direct path to multi-path model. If transmission distance is lesser than the threshold distance (d₀) then the free space model is used otherwise, the multipath model is used.

The amount of energy consumed for receiving K-bit of message is calculated by:

E RX (K) =K. E elec                   (7)

• • Steady State phase

In this phase, actual data transmission takes place between CH and BS. All SNs after collecting their data forward it to the CH. Like in Sub-cluster, its entire member SNs transfers their data to sub-CH which furthers forward this data by combines its own data with the collected data to the main CH. Each CH of every cluster starts combining and aggregating the data of sub-CH with their own collected data of member SNs. And finally, this aggregated data is transferred to the BS.

But before forwarding the aggregated data to the BS, CHs have to check; are they lie far way from BS or near to BS. If the distance (di) is less than threshold distance (d TH ) in that case CH forwards the data directly to BS or free space model is used but if not, then CH has to select next CH which lies close to it. This information of next closest CH is obtained from BS. In this way, CH forwards its data to next hop CH to next hop CH until data reaches the BS. During this steady phase, the residual energy of CH is also calculated after every round so that high residual energy SN will be CH for next round. And this whole process continues until all SNs are dead.

• IV.    Simulation and Results

In this section, the performance evaluation of the proposed protocol is done using MATLAB and their different performance metrics are explored in the presence of energy heterogeneity by comparing it with SEP, LEACH, CEEC and LEFCA routing protocol.

• A.    Simulation Set up

The deployments of SNs in WSNs are arranged by MATLAB simulator is shown in Figure 4.

In the simulation scenario, 3 different networks scaling of sizes are considered; 1) Having 1000 SNs uniformly deployed in network area over 100*100m2; 2) Having 1000 SNs uniformly deployed in network area over 500*500m2 and 3) Having 1000 SNs uniformly deployed in network area over 1000*1000m2.

The various parameters used for simulation setup are listed in Table 2 [12, 13].

• B.    Results and Discussion

Performance metrics chosen for above scenarios are Network lifetime, Packets transmitted to BS, Number of CHs per round, and Number of Dead Nodes per round for WSN.

Table 2. Parameter Settings

Parameter	Scenario 1	Scenario 2	Scenario 3
Network Area Dimensions (M x N)	100m x 100m	500m x 500m	1000m x 1000m
Number of SNs (n)	1000	1000	1000
Rounds (r)	10000	10000	10000
Electronic energy (E elec )	50 nJ / bit	50 nJ / bit	50 nJ / bit
Data aggregation energy (EDA)	5 nJ / bit / message	5 nJ / bit / message	5 nJ / bit / message
Initial energy (E 0 )	0.5 J	0.5 J	0.5 J
Size of the message (k)	4000 bits	4000 bits	4000 bits
Probability (P opt )	0.05	0.05	0.05
Friss free space (Ɛ fs )	10 pJ / bit / m2	10 pJ / bit / m2	10 pJ / bit / m2
Friss multi-path (Ɛmp)	0.0013 pJ / bit / m4	0.0013 pJ / bit / m4	0.0013 pJ / bit / m4
Energy level for Advance nodes (a)	3	3	3
Energy level for Intemediate nodes (b)	1.5	1.5	1.5
% of nodes to be Advanced and Intemediate (m,x)	0.2,0.3	0.2,0.3	0.2,0.3
BS Location	(50,50)	(250,250)	(500,500)

• 1)    Network Lifetime of Nodes Per Rounds

Network Lifetime may be defined as the time interval from the start of operation of SNs until the death of the last alive SN. As the energy of SNs is drained out, it cannot be used to communicate with each other anymore.

Fig. 4 (a), (b), (c) illustrates that EACBM outperforms the other existing protocols in terms of number of Alive SNs (i.e. Network Lifetime) per rounds for Small Scale Network (100m*100m.), Medium Scale Network (500m*500m.)    and Large    Scale Network

(1000m*1000m.) respectively because in LEACH, SEP, CEEC and LEFCA; single hop communication is used while in EACBM routing protocol multi-hop communication between CH and BS is used which results in less consumption of SNs energy. EACBM also performs better than others protocols when network area is increased. This improvement in network lifetime is due to efficient use of clustering method, awareness in terms of energy heterogeneity and using multi-hop pattern used for communication between CH and BS. So it performs better than others in large area network. For Small Scale network, the network lifetime of EACBM is 4%, 46%, 34% and 42% better than CEEC, LEFCA, SEP, and LEACH respectively; for Medium Scale network, the network lifetime of EACBM is 6%, 23%, 14% and 43% better than CEEC, LEFCA, SEP, and LEACH respectively and for Large Scale network, the network lifetime of EACBM is 49%, 71%, 72% and 73% better than CEEC, LEFCA, SEP, and LEACH respectively. The Stability period (time interval from the start of network operation until the death of first SN) of EACBM is also better as compared to LEACH, SEP, CEEC, and LEFCA in all three scenarios.

Fig.4. (a). The Network Lifetime for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Small Scale Network (100m*100m.)

Fig.4. (b). The Network Lifetime for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Medium Scale Network (500m*500m.)

Table 3. Performance comparison between EACBM, CEEC, LEFCA, SEP and LEACH

Protocols	Stability period round	In-stability period round	Network Lifetime round
Scenario of Small Scale Network (100m*100m.)
EACBM	1-1258	1259-4563	1-4563
CEEC	1-1724	1725-4353	1-4353
LEFCA	1-1162	1163-2454	1-2454
SEP	1-1009	1010-3024	1-3024
LEACH	1-506	507-2663	1-2663
Scenario of Medium Scale Network (500m*500m.)
EACBM	1-283	284-4849	1-4849
CEEC	1-113	114-4627	1-4627
LEFCA	1-89	90-3743	1-3743
SEP	1-68	69-2824	1-2824
LEACH	1-13	14-2738	1-2738
Scenario of Large Scale Network (1000m*1000m.)
EACBM	1-30	31-8403	1-8403
CEEC	1-23	24-4266	1-4266
LEFCA	1-17	18-2419	1-2419
SEP	1-13	14-2319	1-2319
LEACH	1-7	8-2289	1-2289

Fig.4. (c). The Network Lifetime for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Large Scale Network (1000m*1000m.)

The performance degradation of LEACH is also due to the fact that it treats all SNs equally without any energy discrimination. SEP performs better than LEACH due to its SNs initial energy discrimination. Due to the smart determination of CH in LEFCA, it performs better than LEACH and SEP. While in CEEC, the cluster formation is centralized and the deployment of SNs is also planned, so that’s why its performance is better than LEACH, SEP, and LEFCA. But EACBM outperforms all of them.

Table 3 shows the statistical value comparison between EACBM, CEEC, LEFCA, SEP and LEACH routing protocol under the three scenarios, which is from the simulation results.

• 2)    Number of CHs per Round and Packets Transmitted to BS Per Rounds

  Fig. 5 (a), (b), (c) shows the number of CHs per round for Small Scale Network (100m*100m.), Medium Scale Network (500m*500m.) and Large Scale Network (1000m*1000m.) respectively. Here as the network size is increased; protocols like LEACH, SEP, CEEC, and LEFCA are not performing well as compared to EACBM and less number of packets is transmitted to BS. In EACBM, the determination of CH is optimal and it provides continuous CH for each round due to which it consumes less energy as compared to others. Also for transferring information to BS, it uses nearby CH in a multi-hoping manner instead of transmitting directly to BS. Due to this, it provides high data rate as compared to SEP, LEACH, CEEC, and LEFCA. The performance degradation of LEACH and SEP is due to distributed nature of CHs selection and fails to provide the optimal number of CHs. Due to which it shows the negative impact on the handling of network traffic and results in the loss of packets due to insufficient TDMA slots. CEEC performs better than LEACH, SEP, and LEFCA because up to some extent it provides the optimal number of CHs for each round.

Fig.6. (a). Packets transmitted to BS for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Small Scale Network (100m*100m.)

Fig.5. (a). Number of CHs for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Small Scale Network (100m*100m.)

Fig.5. (b). Number of CHs for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Medium Scale Network (500m*500m.)

Fig.6. (b). Packets transmitted to BS for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Medium Scale Network (500m*500m.)

Fig.5. (c). Number of CHs for EACBM, SEP, LEACH, CEEC and LEFCA per rounds for Large Scale Network (1000m*1000m.)

Fig.6. (c). Packets transmitted to BS for EACBM, SEP, LEACH, CEEC and LEFCA per rounds Large Scale Network (1000m*1000m.)

Fig. 6 (a), (b), (c) illustrated the number of packets transmitted to BS per round for Small Scale Network (100m*100m.), Medium Scale Network (500m*500m.) and Large Scale Network (1000m*1000m.) respectively during network lifetime and it is important to determine this for quality of every protocol because it delivers the actual data gathered and transmitted to the BS. A number of packets received at the BS are high in EACBM over the number of rounds in all three settings as compared to LEACH, SEP, CEEC, and LEFCA. This is due to the selection of CH in EACBM which have a uniform number of CHs in every round whereas, in case of others, the number of CHs selection per round becomes unstable after the death of first SN in the network.

• 3)    Number of Dead SNs Per Rounds

  As the number of rounds increases, the number of participants of active SNs decreases due to exhaustion of their energy and they became dead. The increase in the number of dead SNs means increment in the rate of instability period as the operation of network proceeds. Fig. 7 (a), (b), (c) shows the number of dead SNs per round for Small Scale Network (100m*100m.), Medium Scale Network (500m*500m.) and Large Scale Network (1000m*1000m.) respectively. Here the number of dead SNs is very high in case of LEACH, SEP, CEEC, and LEFCA as a number of rounds reaches to 2000th round. But in case of EACBM, very less number of SNs is dead as compared to other existing routing protocols as a number of rounds increases which results in the improvement of WSN performance as the passage of network operation. The other important point is that the instability of EACBM starts at a later stage for large area

network as compared to LEACH, SEP, CEEC, and LEFCA. So, EACBM is more resilient and it sends collected data to the network field for more number of rounds.

Fig.7. (a). Number of Dead SNs for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Small Scale Network (100m*100m.)

Fig.7. (b). Number of Dead SNs for EACBM, SEP, LEACH, CEEC and LEFCA per-rounds for Medium Scale Network (500m*500m.)

Fig.7. (c). Number of Dead SNs for EACBM, SEP, LEACH, CEEC and LEFCA per rounds for Large Scale Network (1000m*1000m.)

• V.    Conclusion

This paper proposes EACBM routing protocol for three-level heterogeneous networks for improving the energy efficiency, network lifetime, scalability and coverage of WSNs. Here, a novel method for CH selection is adopted so that only high-energy SN should have more possibility to be CH as compared to others SNs in the current round. Energy dissipation of SNs is greatly reduced by using the concept of both multihoping and clustering together for transferring data to the destined place. It shows better results for heterogeneous WSNs when compared with homogeneous WSNs.

The performance of EACBM routing protocol is compared with LEACH, SEP, CEEC and LEFCA and the simulation results show that EACBM outperforms them in terms of network lifetime, stability, throughput and no. of dead nodes per round in all three different network sizes that are considered in the simulation settings. So, for applications (like military reconnaissance, environment monitoring, and medical services) in which energy efficiency and network lifetime of SNs is concerned, EACBM routing protocol is the better choice. As for our future work, we will analyze EACBM routing protocol more deeply with mobile SNs.