ABSTRACT

Clustering algorithms can balance the power consumption of energy constraint wireless sensor networks. This paper proposes a new clustering protocol called Mean Territorial Energy Based Clustering Protocol (MTEP) for randomly deployed wireless sensor networks. In MTEP, cluster heads are selected according to residual energy and location information of a node in current round as well as mean territorial energy and total base station distance of node’s corresponding cluster territory in previous round. Energy consumption in conventional protocols becomes unbalanced because of clusters having different lengths. Proposed MTEP protocol addresses this problem by setting thresholds on cluster length and node to cluster head distance for producing equal length clusters. Simulation results show that MTEP protocol extends network lifetime and stability with reduction in energy dissipation compared to other clustering protocols such as LEACH and REAC.

Keywords:

Cluster Head, Base Station, Clustering Protocol, Energy Efficiency, Network Lifetime

1. Introduction

An infrastructure required for sensor consisting of sensing, computation, communication and power unit is provided by wireless sensor networks [1] . In wireless sensor networks, thousands of sensors are densely deployed to monitor different environmental conditions such as temperature, pressure, humidity and vibration etc. Wireless sensor networks have wide range of application areas such as Military, home automation, security and health [2] . The wireless sensor node is equipped with a limited power resource whose replenishment is not possible because of remote application area. As node lifetime is highly dependent on battery lifetime, power conservation is an important factor that researchers are currently focusing on. In recent years, researchers have proposed various clustering protocols to extend network lifetime. Low Energy Adaptive Clustering Hierarchy (LEACH) [3] is a well known clustering protocol that enables self organization of nodes by distributed cluster formation technique. In LEACH, cluster heads are selected according to stochastic algorithm and other nodes choose their cluster heads according to strength of received signals from all cluster heads. In LEACH, nodes with any energy have equal threshold for cluster head selection due to which nodes with less energy can also become cluster heads resulting in unbalanced energy consumption. In Hybrid Energy Efficient Distributed clustering (HEED) [4] , cluster heads are periodically selected based on nodes residual energy and nodes choose clusters according to minimum communication cost. For achieving uniform distribution of cluster heads, HEED ensures that no two nodes within a specific range will act as cluster heads across the network. HEED strongly decreases energy dissipation compared with LEACH, however large amount of energy is dissipated by head node. In Distributed Energy Efficient Clustering (DEEC) [5] , the probability of selection of cluster heads depends on ratio of nodes current energy and network average energy. Therefore high initial and current energy nodes have high cluster head selection probability. In DEEC, advanced nodes die earlier compared with normal nodes after depletion of their residual energy. In Regional Energy Aware Clustering with Isolated Nodes (REAC-IN) [6] , node’s current energy and regional average energy are considered to determine cluster head selection threshold for current round. The analysis of these conventional protocols is based on assumption of equal sized clusters. Many times cluster sizes become unequal due to random clustering approaches which results in unbalanced network load. Large amount of energy is dissipated by members of clusters having less number of nodes due to availability of more time slots compared with clusters having large number of nodes. Also large amount of data has to be transmitted by heads of cluster having less number of nodes resulting in high energy dissipation [7] . For solving this problem, there is requirement of clustering protocol which offers equal sized clusters for balancing energy consumption of entire network. In S-EECP [8] , the cluster heads (CHs) are elected by a weighted probability based on the ratio between residual energy of each node and average energy of the network. The nodes with high initial energy and residual energy will have more chances to be elected as CHs than nodes with low energy whereas in M-EECP [8] , the elected CHs communicate the data packets to the base station via multi-hop communication approach. SEECH [9] selects CHs and relays separately and based on nodes eligibilities. In this way, high and low degree nodes are, respectively, employed as CHs and relays. To consider uniformity of CHs to balance clusters, SEECH uses a new distance-based algorithm. In [10] , a new SEEC for heterogeneous WSNs is presented in which sensing area consists of a fixed number of clusters and fixed CH for each cluster. Each cluster has a powerful advanced node and some normal nodes deployed randomly. This guarantees the fair distribution of energy. This protocol is extended to multi-level heterogeneous WSN. M-SEEC assigns more powerful nodes called super nodes to cover the distant parts of the sensing area. In this paper, a new protocol is proposed called Mean Territorial Energy Based Clustering Protocol (MTEP) for randomly deployed wireless sensor networks. MTEP rotates role of cluster heads among all nodes for uniform energy consumption of each node. MTEP determines cluster head selection threshold by considering residual energy and position of a node in current round and mean territorial energy and total base station distance within a node’s particular cluster territory in previous round. In order to further extend network lifetime, MTEP is modified to produce clusters having equal length by using thresholds on cluster length and distance between node and its cluster head. The paper outline is as follows. Section II introduces proposed MTEP protocol. Section III compares proposed protocol with existing protocols such as LEACH and REAC through simulations. Finally section IV concludes the paper.

2. Proposed Protocol

In this paper, we propose a Mean Territorial Energy Based Clustering Protocol (MTEP) for randomly deployed WSNs. MTEP rotates the role of being a cluster head among all nodes for uniform energy consumption of each node as that of LEACH. MTEP selects cluster heads according to the threshold consisting of the node’s residual energy; distance from base station; mean territorial energy and total base station distance of all nodes of corresponding cluster territory in previous round unlike LEACH which uses cluster head selection threshold having fixed probability of cluster head selection.

2.1. Cluster Head Selection Algorithm

Traditionally, LEACH divides its operations into several rounds. Each round includes cluster head selection, cluster formation and steady state phase. During a cluster head selection phase, each round selects itself as cluster head according to threshold calculated by parameter p, where p is the desired percentage of cluster heads for entire network. Each node selects a random number between 0 and 1 and compares it with cluster head selection threshold. If selected number is less than threshold, then that node becomes a cluster head for current round r. In LEACH [3] , the cluster head selection threshold for i^th node is given by

$T\left(i\right)=\{\begin{array}{l}p/\left(1-p\ast \left(r\mathrm{mod}1/p\right)\right)\text{if}i\in G\\ 0\text{otherwise}\end{array}$ (1)

where G is the set of nodes which are not selected as cluster heads in the last $\frac{1}{P}$

rounds. In above threshold, $p=k/N$ where k is the pre calculated expected number of clusters and N is the total number of nodes in entire network. In LEACH, each node has equal probability p for each cluster head selection process. As all nodes have different residual energies during different rounds, low energy nodes may die quickly compared with high energy nodes. Also all randomly deployed nodes posse uneven residual energy distribution. Condition of the whole network cannot be accurately represented by global average energy for large scale WSNs. Very few existing algorithms consider local energy of nodes in determining cluster heads. Energy can be saved by considering local node’s energy level in deciding probability of a node to become a cluster head. Therefore, in order to extend network lifetime, we propose the MTEP which calculates different probability p for different nodes according to nodes residual energy and distance to base station in current round as well as mean territorial energy and total base station distance of all nodes within a node’s corresponding cluster territory in previous round.

Let a node i is present in cluster a at round r − 1. If $E_{curren{t}_{-}i}\left(r-1\right)$ is the residual energy of node i at round r − 1, n_a is the number of nodes in a cluster a at round r − 1, then mean territorial energy of node i at round r − 1 is given by,

$E_{mt{a}_{-}i}\left(r-1\right)=\frac{{\sum }_{i=1}^{n_a}{E}_{curren{t}_{-}i}\left(r-1\right)}{n_a}$ (2)

We keep desired percentage of cluster heads to be p as that of LEACH. Cluster head selection probability for node i during current round r is given by,

$p\left(i\right)=p\ast \frac{E_{curren{t}_{-}i}\left(r\right)}{E_{mt{a}_{-}i}\left(r-1\right)}\ast \frac{d_{toB{S}_{-}i}\left(r\right)}{d_{toB{S}_{-}tota{l}_{-}a}\left(r-1\right)}$ (3)

where $d_{toB{S}_{-}i}\left(r\right)$ is the distance of node i to base station at round r and $d_{toB{S}_{-}tota{l}_{-}a}\left(r-1\right)$ is the total distance of all nodes present in cluster a to base station at round r − 1. A node i selects itself as cluster head at round r according to following probability threshold.

$T\left(i\right)=\{\begin{array}{l}\frac{p\left(i\right)}{1-p\left(i\right)\ast \left(r\mathrm{mod}\frac{1}{p\left(i\right)}\right)}\text{if}i\in G\\ 0,\text{otherwise}\end{array}$ (4)

where G is the set of nodes which are not selected as cluster heads in last 1/p(i) rounds. Once a node i selects itself as cluster head, it broadcasts an advertisement message containing its id and spreading code to reduce inter cluster interference. Each node compares randomly generated number between 0 and 1 with threshold for cluster head selection mentioned above. Node work’s as a current round cluster head if generated number is less that the threshold. Once a node selects itself as a cluster head, it uses CSMA as a MAC protocol to broadcast an advertisement (ADV) message containing its ID, header to indicate it as an announcement message and a spreading code necessary to reduce inter cluster interference.

2.2. Cluster Formation Phase

In this paper, a distributed cluster formation technique is used to produce equal length clusters. Let C_l is the length of each cluster given by,

$C_l=\frac{N}{K}$ (5)

where N is the total number of nodes in the network and K is the number of cluster heads. As there are different number of cluster heads in each round, C_l is also different for different rounds. In primary cluster establishment phase, each node receives an advertisement message sent by all cluster heads and join cluster head nearest to it only if that cluster head has member nodes less than C_l. If selected cluster head has member nodes higher than C_l then normal nodes select it as temporary cluster head. Once temporary cluster formation phase is complete, a threshold on node’s distance to cluster head is calculated for final cluster establishment phase. If node j at a location (x_j, y_j) is the cluster head of node i at location (x_i, y_i) in temporary cluster establishment phase, then total distance between all nodes and their respective cluster heads is given by,

$d_{total\text{\_}ntoCH}=\sum _{i=1}^N\sum _{j=1}^k\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ (6)

For final cluster establishment phase, threshold on node to cluster head distance is given by,

$d_{t{h}_{-}ntoch}=\frac{{\sum }_{i=1}^N{\sum }_{j=1}^K\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}}{N/K}$ (7)

In final cluster establishment phase, a node who selected temporary cluster head now finds new closest cluster head k which is at a distance less than $d_{t{h}_{-}ntoch}$ ( $d_{itok}\le d_{th\text{\_}ntoch}$ ) and have cluster length less than C_l (If C_k < C_l). If normal node is unable to find out such cluster head then it selects its nearest cluster head for data transmission. Figure 1 explains cluster formation algorithm. Once final cluster establishment phase is over each member node sends a join-request message to its cluster head containing its own id, cluster head’s id and same spreading code using CSMA as a MAC protocol. After receiving join-request message from each member, a cluster head makes a TDMA schedule and broadcasts it to all its members. Nodes are allowed to turn on their radio components only during their allocated time slot due to which energy consumption and intra cluster interference can be reduced. Steady state phase begins after reception of TDMA schedule by member nodes. In steady state phase each member node wakes up during its time slot in TDMA schedule and transmits data to cluster head and goes into sleep mode again. Cluster head node in turn transmits aggregate data received from all its members to base station.

3. Results

In this section, performance of the proposed MTEP protocol is compared with other protocols such as LEACH and REAC using Matlab 7.8. In this test, we assume some initial conditions of network model as shown in Table 1.

Other parameters such as energy required to run radio electronics (E_elec) and radio amplifier (E_amp), data aggregation energy (E_DA) are taken same as [3] . Figure 2 shows number of alive nodes versus number of rounds for LEACH, REAC

and MTEP protocols. From Figure 2, we can find MTEP increases network lifetime by 2256 rounds compared with LEACH and by 1999 rounds compared with REAC protocols.

FDN (First Dead Node), HDN (Half Dead Node) and LDN (Last Dead Node) are the number of rounds after which first node, 50% and 100% of nodes are died respectively. Figure 3 compares FDN, HDN and LDN metrics for LEACH,

REAC and MTEP protocols. From Figure 3, it is noticed that MTEP extends FDN measure by 270, 84 rounds and HDN measure by 730, 506 rounds compared to LEACH and REAC protocols respectively. The residual energy of entire network for three protocols is shown in Figure 4. It is observed that MTEP reduces residual energy more slowly compared to LEACH and REAC protocols. From these results, we can see that MTEP offers more load balancing because of uniform energy consumption of all nodes across the network compared to LEACH and REAC.

Table 2 shows number of rounds required for the death of 20%, 40% and 80% of nodes for LEACH, REAC and MTEP respectively. From Table 1, it is seen that MTEP increases 20%, 40% and 80% node death by 413, 610, 1216 rounds compared with LEACH and by 181, 388 , 1024 rounds compared with REAC protocol respectively.

Figure 5 is the probability density function of networks residual energy with respect to time for LEACH, REAC and MTEP. This figure shows that residual energy of network have high mean in MTEP compared with LEACH and REAC.

Figure 6 shows throughput of LEACH, REAC and MTEP. From Figure 6, it is

observed that LEACH, REAC and MTEP transmit 1174, 1191 and 1373 packets to base station respectively which clearly shows higher throughput in case of MTEP than LEACH and REAC.

Ideally all packets sent by a sensor node are received at the sink successfully. But practically, some packets are lost due to noise, attenuation, interference and congestion etc. Figure 7 shows packet drop ratio of the LEACH, REAC and MTEP protocols respectively. It is noticed that LEACH, REAC and MTEP provides average packet drop ratio of 34.15%, 23.94% and 18.40% for first 500 rounds which clears that MTEP gives better performance by dropping less number of packets than LEACH and REAC.

4. Conclusion

WSN is formed by sensor nodes and wireless communication between them. Network should have long lifetime, high energy efficiency and stability. MTEP protocol proposed in this paper provides improved cluster head selection method based on node’s residual energy and location information in current round as well as mean territorial energy and total distance to base station of node’s corresponding cluster territory in previous round. Proposed MTEP protocol sets threshold on cluster length and node to cluster head distance for obtaining equal length clusters. Simulation results show that proposed protocol achieves better performance in increasing network lifetime, prolonging stability period, throughput and reducing energy consumption as well as packet drop ratio compared with other protocols such as LEACH and REAC.

Cite this paper

Gawade, R.D. and Nalbalwar, S.L. (2017) Mean Territorial Energy Based Clustering Protocol for Randomly Deployed Wireless Sensor Networks. Advances in Internet of Things, 7, 87-96. https://doi.org/10.4236/ait.2017.73006

References