Comparative Cluster Based Routing Protocols Investigations for Distributed Wireless Networks

Vinod Kumar Verma^*, Umabharati Rawat

Department of Computer Science and Engineering, Sant Longowal Institute of Engineering and Technology, (SLIET), Deemed University, Punjab, India

Abstract

Wireless sensor networks technology has become a vast field of research due to its wider sphere impacting our daily lives. This paper presents elementary work to address network load effect over energy efficiency through heterogeneous distributed energy efficient routing protocols. Since clustering is one of the major factors for energy optimization in routing protocols. So, we focus our research work on clustering based heterogeneous routing protocols for comparative analysis in wireless sensor networks. We included network workload scaling metric to address performance based aspects. Moreover, performance evaluation metrics for energy consumption like dead node count, alive node count, throughput, and cluster-head count are also evaluated. Finally, simulation analysis has been done to prove validity of our proposal. This work seems to be a bench mark for wireless sensor network system designer towards distributed energy efficient routing protocols.

Keywords

Clustering, Count, Heterogeneity, Node, Routing Protocol, Scalability, WSN

Received: June 30, 2016
Accepted: July 25, 2016
Published online: November 2, 2016

@ 2016 The Authors. Published by American Institute of Science. This Open Access article is under the CC BY license. http://creativecommons.org/licenses/by/4.0/

1. Introduction

At present wireless sensor networks have become a novel and influential tool for diverse fields such as sensing, data gathering, tracking and wide range of monitoring [1]. Application domain [2] of WSNs associated with environmental monitoring, security and surveillance, precision agriculture, and industrial usage etc. Such a network consists of set of large micro sensors deployed randomly in harsh environment to perform some sensing task. Due to probability of working in harsh and inaccessible environment, batteries of sensor nodes cannot be charge and substitute further [3]. That’s why energy consumption becomes a key limitation in WSNs. Since each node has limited capacity but summation of entire network’s energy performs the designated task in WSNs. Collaboration power of WSNs can be achieved naively via routing protocols to ensure multi hop communication. In routing protocols, clustering remains one of the novel ways for energy optimization [4]. In clustering, nodes arrange themselves into local clusters electing one node as a cluster-head. Initially, non cluster-head nodes transmit data to the cluster-head node. Next, two functions namely data aggregation and data fusion are performed at cluster-head node to eliminate redundant information. Finally, data is forwarded to the remote base station. Clustering approach in routing protocols is significant way to reduce energy consumption. WSNs can be broadly classified namely homogeneous and heterogeneous sensor networks based on their nodes capacity [5]. Nodes are of same capacity deployed in randomly distributed environment is treated as homogeneous WSNs. In contrary with different nodes capacity on the basis of their bandwidth, data rates are called heterogeneous wireless sensor networks. Clustering with heterogeneity in routing protocols is most practically applicable concept to deal with energy consumption challenge in WSNs. In this paper, we included low energy adaptive clustering hierarchical protocol (LEACH) [5], stable election protocol (SEP) [6], distributed energy efficient clustering routing protocol (DEEC) [7], developed distributed energy-efficient clustering protocol (DDEEC) [8], enhanced distributed energy efficient clustering protocol (EDEEC) [9], and threshold distributed energy efficient clustering routing protocol (TDEEC) [10] for heterogeneous WSNs. In LEACH protocol, cluster-head selection idea is backbone for energy optimization. Cluster-heads are local base stations to maintain energy load for all the nodes. LEACH is able to achieve factor of eight reductions in energy dissipation with tradition routing protocols [5]. In SEP protocol, cluster-head selection is based on weighted election probabilities in each node. SEP always prolongs the stability period but only achieve two-level heterogeneity [6]. In DEEC protocol, cluster-head selection is probability is the ratio of residual energy of node to average energy of network. Multilevel heterogeneity is achieved in DEEC [7]. In DDEEC protocol, key idea for cluster head selection is based on dynamic behaviour probability [8]. EDEEC protocol performs better than SEP with more stability period [9]. EDEEC also achieve multilevel heterogeneity. In TDEEC protocol, cluster-head selection process achieves better results due to change in threshold value [10-11]. This paper presents comparative evaluation of heterogeneous routing protocols based on network lifetime and energy consumption aspects. Verma et al. [12] contributed towards scalability issue in AODV routing protocol for wireless sensor networks. Data dissemination based investigations over sensor node distribution strategies have been reported in references [13-14]. Sensors augmentation influence over trust and reputation models has been reported in reference [15].

The layout plan for this paper is as follows. Section II defines related work on explorative distributed routing protocols. In section III, we define cluster-head selection phase for each routing protocol for comparative analysis. In section IV detail experimental setup with performance measurement parameters are defined. Simulation results are shown with evaluation parameters in section V. Finally, conclusion and future direction are defined in section VI.

2. Related Work to Distributed Routing Protocols

Usages of heterogeneous routing protocols [16] are increasing day by day. This is due to routing protocols are one of efficient and realistic way to address energy consumption aspects. In this section we have included network model and energy consumption model.

2.1. Network Model

We have taken network model in consistent pattern of DEEC routing protocol. N numbers of sensor nodes randomly distributed over M×M square region. Network model can be extended in terms of heterogeneity. In this model, all the sensor nodes always have data to transmit to a base station. In such type of network model, heterogeneity can be achieved up to multilevel.

In case of two-level heterogeneity, two types of sensor nodes present in the network. One is normal node with initial energy E₀ and second is advance node with initial energy (1+a) × E₀. Advance nodes have a time more energy than normal nodes. If fraction of m number of sensor nodes are advanced nodes in that case (1-m) × N normal nodes are present in the network. Total energy of the two level heterogeneous networks can be calculated using equation (1),

   (1)

In case of three-level heterogeneity, three types of nodes present in the network. Node types included normal node, advanced node, and super node with initial energy E₀, (1+a) × E₀, (1+b) × E₀ respectively. Super node has b time more energy than advance node. In that case, total energy of the network can be calculated as,

             (2)

In case of multi-level heterogeneity, there are multiple nodes are present with different energy capacity. Range of energy lies between E₀ to E₀ (1+a_max), where E₀ is minimum range, and E₀ (1+a_max) is maximum range with  determine value of maximum energy. In case of multilevel heterogeneity, total energy of the network can be calculated as,

)   (3)

2.2. Energy Consumption Model

We take energy consumption model in consistent pattern of distributed energy efficient clustering algorithm with improved coverage [4]. We have included transmission energy, receiving energy and energy consumption and dissipation in one round in this model. Energy consumption included  (depending on factors such as digital coding, modulation, filtering and spreading of the signal). Energy dissipation included both free space (d² power loss) and multipath (d⁴ power loss) fading channel models. These losses depend on the distance d between transmitter and receiver. Thus, to transmit l bit message from transmitter to receiver with distance d, energy expands

           (4)

As well, for receiving l bit message between sensor nodes, energy expands

                        (5)

Total energy consumption in the network during a round is calculated as:

  (6)

3. Cluster-Head Selection Process

In this paper, we evaluated clustered based heterogeneous routing protocols. In these protocols, selection of cluster-head procedure is different which is responsible for better performance. We included cluster-head selection phase for each routing protocol as described below.

3.1. Low Energy Adaptive Clustering Hierarchy (LEACH)

In LEACH protocol, initially group of sensor nodes make single cluster and no cluster-head present in network. Here, optimal election probability (P) to be a cluster-head is predefined. Before cluster-head selection, firstly residual energy is checked for satisfying criteria. Random value is selected and compared with threshold value i.e. (p/1-p × mod (r, round (1/p))). Estimated random value is less than threshold value than that node becomes a cluster-head for current round. For next round, other nodes have chance to be a cluster head node except elected nodes. When cluster-head selection process is over, co-ordinates are assigned to cluster-head node. Distance between cluster-head node to sink node is calculated. After that ID is assigned to cluster-head node. Residual energy of each node is calculated based on free space loss and multi path losses for each round. This process is repeated for every node. Lastly, cluster-head count is calculated.

3.2. Stable Election Protocol (SEP)

Stable Election Protocol follows the consistent pattern of LEACH protocol for cluster-head selection. Election probability to be a cluster-head for each node is predefined. Threshold value is used to compare with estimated random value. Thus, those nodes satisfying the required criteria selected as cluster-head for current round. This process is repeated for all the active nodes until nodes are inactive.

3.3. Distributed Energy Efficient Clustering Protocol (DEEC)

In DEEC Protocol, Initially no cluster-head is present, group of sensor nodes make single cluster. Average energy (E_a) of the network will be checked for each node. Probability to be a cluster-head (p(i)) is calculated for every node using equation given below.

                 (7)

           (8)

For election of cluster head node, residual energy will be checked for minimum value. A random value is taken between 0 and 1 and compare with threshold value i.e. . If random value is less than threshold value for a node that node will selected as cluster-head. DEEC followed cluster-head selection strategy is shown in figure 1.

Figure 1. Cluster-head selection procedure flow chart.

3.4. Developed Distributed Energy Efficient Clustering Protocol (DDEEC)

DDEEC routing protocol follows consistent pattern of DEEC in cluster-head selection phase. We have seen disparity present in cluster-head selection probability. Probability to be a cluster-head can be calculated based on energy based heterogeneity. Energy heterogeneity can be implemented such as (initial energy)  probability to be a cluster-head can be calculated using equation (9).

    (9)

 Probability to be a cluster-head can be calculated using equation (10).

        (10)

 Probability to be a cluster-head can be calculated using equation (11).

  (11)

After calculating probabilities, estimated random value is compared with threshold value. DDEEC protocol follows consistent pattern of DEEC for further processing. Lastly, cluster heads are calculated.

3.5. Enhanced Distributed Energy Efficient Clustering Protocol (EDEEC)

EDEEC Protocol followed consistent pattern of DEEC protocol for cluster-head selection procedure. Differentiation is present in terms of node heterogeneity. In this protocol residual energy is calculated for normal node, advanced node, and super node. Probability to be a cluster-head selection is based on nodes heterogeneity such as if (Initial Energy <= 0) Then probability to be a cluster-head can be calculated using equation (12).

        (12)

If (Initial Energy <= E₀ × (1+a)) Then probability to be a cluster-head for advanced node can be calculated using equation (13).

     (13)

If (Initial Energy <= E₀ × (1+b)) Then cluster-head selection probability for super node can be calculated using equation (14).

     (14)

Furthermore, a random value is chosen and compared with threshold value i.e. for cluster-head selection. After completion of cluster-head selection various operations are performed for further processing. Residual energy also calculated based on two types of losses namely free space loss and multipath loss. For each round, those nodes satisfying required criteria selected as cluster-head.

3.6. Threshold Distributed Energy Efficient Clustering Protocol (TDEEC)

TDEEC protocol also followed consistent pattern of DEEC routing protocol for cluster-head selection phase. Cluster-head selection probability is calculated based on nodes heterogeneity level. In this protocol, residual energy will be Calculated for normal node, advanced node, and super node before cluster-head selection procedure. But threshold value is modified such that. This value can be compared with random variable, if smaller value then random value is found node will be selected as cluster-head node.

4. Detail Setup

In this section, we deployed investigational framework to analyze different heterogeneous routing protocols. For simulation setup, we have taken N number of sensor nodes randomly distributed over M×M square region. We have included energy consumption parameters like  etc for network load analysis. Figure 2 shows network model with 100 nodes that are spread over 100m×100m region. We have taken base station is in centre of the sensing region for simplicity purpose.

Figure 2. Experimental Simulation Setup.

In experimental simulation scenario, (o) oval represents normal nodes, (+) represents advance nodes, and (×) represents sink node. In this setup, red marks denote number of dead node after some iteration. Simulation is based on various fixed and scalable parameters. In table 1, we have included energy and network parameters.

Table 1. Simulation Parameters.

5. Results

We used MATLAB over windows platform to evaluate the performance based on network load and energy constraints. Performance investigation is basically evaluating energy consumption and dissipation aspects through five parameters namely: DNC, ANC, PTBS, PTCH, and CHC. This section shows effect of network load over such as LEACH, SEP, DEEC, DDEEC, EDEEC, and TDEEC routing protocols. Network load can be defined as number of sensor nodes present in the network. Network life time can be defined as counting of number of rounds until all alive nodes are dead in the network. Dead node count is defined as counting of number of rounds showing number of inactive nodes present in the network. Alive Node Count is defined as counting of number of rounds until all alive nodes become dead. Packets send to Base Station is defined as data packets need to send from cluster-head node to the base station. Packets send to Cluster head is defined as number of data packets send between non cluster-head nodes to the cluster-head nodes. Cluster-head count calculates number of cluster-head present per round.

Figure 3 presents performance based evaluations for 100 nodes. This figure divided into four subplots. In which x-axis represents number of rounds and y-axis represents number of nodes, packet size, and number of cluster-heads respectively. First and second sub plots represent network life time through dead node count and alive node count. In third and fourth subplots, we represent energy consumption through packets send to base station and cluster-head count. We analyzed network lifetime is less in LEACH and SEP protocols. In EDEEC and TDEEC routing protocols network lifetime is more and energy consumption is less.

Figure 3. Performance based evaluations for 100 nodes.

Figure 4 presents performance based evaluation for 200 nodes. This figure shows, how network load affect energy parameters. First and second subplots shows network lifetime may decreases as network load increases. This is due to more number of data packets send to base station resulting in increment of cluster-head count. In this case, we analyzed LEACH, and SEP protocols are more affected in terms of energy consumption.

Figure 4. Performance based evaluations for 200 nodes.

Figure 5 represents performance based evaluation for 300 nodes. We have evaluated routing protocols affected through network load based scalability in term of energy consumption. Performance of LEACH and SEP protocols is less in term of network lifetime. Other routing protocols like EDEEC and TDEEC perform better.

Figure 5. Performance based evaluations for 300 nodes.

Figure 6 represents performance based evaluation for 400 nodes. In this figure first subplot shows, stability period and network lifetime have decreased. Remaining three subplots show energy consumption and throughput have increased. We have analyzed, two routing protocols such as LEACH and SEP have more influenced with network load while DEEC and its variants perform well in this aspect.

Figure 6. Performance based evaluations for 400 nodes.

Figure 7 represents performance based evaluation for 500 nodes. First subplot shows all nodes are dead earlier with fewer rounds. Network lifetime also decreased in alive node count with more network load. Moreover, packets send to base station and cluster-head count increased with more network load. As cluster-head count increases in each round, energy consumption is more. We analyzed in DDEEC protocol, energy consumption is more due to more number of cluster-heads present per round. Network lifetime is more in EDEEC and TDEEC routing protocols due to less number heads.

Figure 7. Performance based evaluations for 500 nodes.

Table 2 represents performance evaluation of six heterogeneous routing protocols name as Low Energy Adaptive Clustering Hierarchy (LEACH) protocol, Stable Election Protocol (SEP), Distributed Energy Efficient Clustering Routing protocol (DEEC), Developed Distributed Energy Efficient Clustering Protocol (DDEEC), Enhanced Distributed Energy Efficient Clustering Routing Protocol (EDEEC), and Threshold Distributed Energy Efficient clustering protocol (TDEEC). This performance evaluation is based on five parameters name as dead node count, alive node count; packets send to base station, packets send to cluster-head, and cluster-head count.

Table 2. Network load based comparison analysis.

6. Conclusion and Future Direction

This paper presented comparative analysis of six distributed energy efficient clustered routing protocols. We have evaluated network lifetime and energy consumption issues over network load parameter. We have analyzed that network load affects stability period and network lifetime. This is due to increment in energy consumption and decrement in stability period. We have analyzed that LEACH protocol gives low performance for heterogeneous environment. In SEP protocol, stability time improves than the LEACH protocol. In DEEC protocol along with its variants, both stability period and network lifetime increases.

In the future, this work can be extended to performance affecting parameters such as network size, fraction of energy enhancement, and security aspects etc.

Appendix

References

1. Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002) A survey on sensor networks. Communications magazine, IEEE, 40(8), 102-114.
2. Patil, M., & Biradar, R. C. (2012, December) A survey on routing protocols in Wireless Sensor Networks. In Networks (ICON), 2012 18th IEEE International Conference on (pp. 86-91). IEEE.
3. Duarte-Melo, E. J., & Liu, M. (2002, November) Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks. InGlobal Telecommunications Conference, 2002. GLOBECOM'02. IEEE (Vol. 1, pp. 21-25). IEEE.
4. Liu, Z., Zheng, Q., Xue, L., & Guan, X. (2012) A distributed energy-efficient clustering algorithm with improved coverage in wireless sensor networks. Future Generation Computer Systems , 28(5), 780-790.
5. Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000, January) Energy-efficient communication protocol for wireless microsensor networks. In System sciences, 2000. Proceedings of the 33rd annual Hawaii international conference on (pp. 10-pp). IEEE.
6. Smaragdakis, G., Matta, I., & Bestavros, A. (2004, August) SEP: A stable election protocol for clustered heterogeneous wireless sensor networks. InSecond international workshop on sensor and actor network protocols and applications (SANPA 2004) (Vol. 3).
7. Qing, L., Zhu, Q., & Wang, M. (2006) Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks. Computer communications, 29(12), 2230-2237.
8. Elbhiri, B., Saadane, R., El Fkihi, S., & Aboutajdine, D. (2010, September) Developed Distributed Energy-Efficient Clustering (DDEEC) for heterogeneous wireless sensor networks. In I/V Communications and Mobile Network (ISVC), 2010 5th International Symposium on (pp. 1-4). IEEE.
9. Saini, P., & Sharma, A. K. (2010, October) E-DEEC-enhanced distributed energy efficient clustering scheme for heterogeneous WSN. In Parallel Distributed and Grid Computing (PDGC), 2010 1st International Conference on (pp. 205-210). IEEE.
10. Saini, P., & Sharma, A. K. (2010) Energy efficient scheme for clustering protocol prolonging the lifetime of heterogeneous wireless sensor networks. National Institute of Technology Jalandhar, Department of Computer Science & Engineering, International Journal of Computer Applications , 6(2).
11. Liu, Z., Zheng, Q., Xue, L., & Guan, X. (2012) A distributed energy-efficient clustering algorithm with improved coverage in wireless sensor networks.Future Generation Computer Systems, 28(5), 780-790.
12. Verma, V. K., Singh, S., & Pathak, N. P. (2014) Analysis of scalability for AODV routing protocol in wireless sensor networks. Optik-International Journal for Light and Electron Optics, 125(2), 748-750.
13. Verma, V. K., Singh, S., & Pathak, N. P. (2014) Comprehensive event based estimation of sensor node distribution strategies using classical flooding routing protocol in wireless sensor networks. Wireless networks, 20 (8), 2349-2357.
14. Singh, S., Verma, V. K., & Pathak, N. P. (2015) Sensors Augmentation Influence Over Trust and Reputation Models Realization for Dense Wireless Sensor Networks. Sensors Journal, IEEE, 15(11), 6248-6254.
15. Verma, V. K., Singh, S., & Pathak, N. P.(2016) Analytical Event Based Investigations Over Delphi Random Generator Distributions for Data Dissemination Routing Protocols in Highly Dense Wireless Sensor Network. Wireless Personal Communications , 1-14.
16. Hong, Z., Wang, R., & Li, X. (2016) A clustering-tree topology control based on the energy forecast for heterogeneous wireless sensor networks. Automatica Sinica, IEEE/CAA Journal of, 3(1), 68-77.