# VCH-ECCR: A Centralized Routing Protocol for Wireless Sensor Networks

Authors: Rohit Pachlor; Deepti Shrimankar
Journal: Journal of Sensors
 (2017)

---

## Abstract

A wireless sensor network (WSN) is a collection of hundreds to thousands of compact, battery-operated sensors. It is deployed to accumulate useful information from the nearby environment. Depending upon the type of application, the sensors have to work for months to years with a finite energy source. In some extreme environments, the replacement of energy source is challenging and sometimes not feasible. Therefore, it is vital for sensors to perform their duties in an energy efficient way to improve the longevity of the network. This paper proposes an energy-efficient centralized cluster-based routing protocol called Vice-Cluster-Head-Enabled Centralized Cluster-based Routing protocol (VCH-ECCR). The VCH-ECCR uses a two-level hierarchy of vice cluster heads to use the energy of sensors efficiently and to cut back the frequency of the clustering. The performance of VCH-ECCR is compared with low-energy adaptive clustering hierarchy (LEACH), LEACH-Centralized (LEACH-C), and base station controlled dynamic clustering protocol (BCDCP). The experimental results show that the VCH-ECCR outperforms over its comparative in terms of network lifetime, overall energy consumption, and throughput.


---

## Body

## 1. Introduction

When deployed in a target area, sensors monitor the surrounding events and cooperatively communicate monitored information to a base station (BS) [1]. The sensors are equipped with limited energy, communication, sensing, and processing resources. The size and cost of sensors limit their resources. The size of a sensor may differ from a brick such as a weather station to a microscopic particle such as a tooth sensor. The cost of a sensor also varies with the extent of required capabilities—high for powerful sensors (equipped with complex hardware resources) and low for simple sensors. Changes in the size and cost of the sensor directly change the sensor’s resource limitations [2].The battery is the most precious and critical resource of a sensor as it has a significant impact on the overall lifetime of a WSN. Therefore, sensors must be operated in an energy efficient manner [3]. After deployment, the possible ways through which the energy consumption of a sensor node can be reduced are the following:
(i)
Data aggregation [4, 5]: readings of nearby sensors are spatially correlated. Data aggregation eliminates this redundant data transmission thereby reducing the bandwidth usage and energy consumption of the network. The energy consumption of a sensor is directly proportional to the number of packets sent by the node.(ii)
Reduce transmission power [6, 7]: the energy consumption of a sensor is directly proportional to the distance at which it transmits data. It can be reduced by adjusting the transmission power of the sensor and transmitting data at short distances. Sensors are capable of dynamically controlling their transmission power.(iii)
Save idle time and energy [8]: sensors which send data periodically can save substantial idle time and energy using duty cycles. The sensor turns on its radio component at times depending on whether it has data to transmit or not.A cluster-based routing technique serves all the purposes mentioned above [9–13]. In a cluster-based network, all network nodes are divided into several clusters. Each cluster has member nodes and a leader called a cluster head (CH). The CH is responsible for aggregating the data received from members and transmitting it to the BS through direct communication or via other CHs as shown in Figure 1. The CH creates a time division multiple access (TDMA) schedule for members. The member nodes send data to the CH according to the TDMA schedule. It reduces intracluster data inference and collisions. It also allows cluster members (CMs) to turn off their radio components at all times except during their transmission slot.Figure 1
Clustering hierarchy: (a) two-level and (b) multilevel.Clustering technique divides the process of communication of sensors with the BS into several rounds. Each round composed of setup phase and steady-state phase. The setup phase mainly includes activities related to the clustering such as CH selection and cluster membership (formation). The steady-state phase is related to transmission of the sensor’s data to the BS. The setup phase is an overhead over the actual transmission of sensed data. Performing clustering in each communication round increases the setup overhead. The main contribution of this paper can be summarized as follows:(1)
A centralized cluster-based routing protocol is proposed, which efficiently uses the energy of all nodes to boost the longevity of the network.(2)
Two-phase vice cluster head hierarchy is used to reduce the frequency of clustering and save maximum energy while transmitting the required information for the setup phase.(3)
The desired number of CHs is not fixed. They are updated at every communication round based on the number of alive nodes in the network. A dead node is a node with zero residual energy.The rest of the paper is organized as follows: Section2 presents the problem statement, Section 3 presents the related work, Section 4 explains the proposed VCH-ECCRH protocol, Section 5 evaluates the performance of VCH-ECCRH, Section 6 presents the reclustering overhead analysis, and Section 7 presents the conclusions of the work.


## 2. Problem Statement

Let us supposen be the number of sensor nodes which are randomly deployed in a M × M m2 area. The objectives of this work are as follows:
(1)
Divide the nodes into several clusters with one of the nodes working as a cluster head such that(a)
the overall energy consumption during the data communication phase is minimized;(b)
the cluster heads are well-distributed in the network (must not get concentrated in one area of the network) and serve their job for a long time;(c)
the energy-intensive role of the cluster head rotates in all the nodes of the network to distribute the energy load evenly using reclustering.(2)
Minimize the clustering setup overhead and cut back the frequency of the clustering.


### 2.1. Data Dictionary

Table1 describes all the variables and constants used in this paper.Table 1
Variable list.
Variable name
Description
ET,X(k,d)
Energy required to transmitk bits at distance d.
E
R(k)
Energy required to receivek bits.
E
elec
Energy required to run transceiver circuitry.
ε
fs
The free space energy loss.
ε
mp
The multipath energy loss.
n
Total number of sensors.
n
alive
Total number of alive sensors.
E
r(i)
Residual energy ofith sensor.
E
max
Initial maximum energy of a sensor node.
d
B
S
2
Distance of the nearest node to the BS.
M
Side-length ofM × M deployment area.
N
CH
Desired number of CHs.
C(c)
cth cluster where c:1, 2, … , NCH.
N
C(c)
Total numbers of members in clusterC(c).
E
avg (C(c))
Average node energy in clusterC(c).
ANDCenC(c)
Average node distance incth cluster from its centroid.
D
Cen(j)
Distance ofjth member node from the cluster centroid.


### 2.2. Network Model

We have the following assumptions about the network:(1)
The sensors are randomly deployed. Sensors and the BS are immobile after deployment. The BS is located faraway and outside the observation field where sensors are deployed.(2)
All sensors know their physical location.(3)
All sensors are homogeneous: starting with the same initial energy, computational, and communication capabilities.(4)
All sensors have a limited energy source. Battery recharge or replacement is impossible after the deployment. The BS is not energy constrained.(5)
All sensors have limited sensing range but can adapt transmission power depending upon the transmission distance.(6)
Links between nodes are symmetric. A packet transmission between any two sensors takes the same amount of energy regardless of whichever node initiates the transmission.(7)
All sensors are sensing at a steady rate, and so they always have data to send.(8)
All sensors are fault-tolerant.(9)
Intercluster and intracluster communications are one-hop communication.


### 2.3. Energy Model

We have used an energy model to calculate the energy dissipation of a node while transmittingk bits at d distance and receiving k bits, respectively, which are as follows [13]:
(1)ET,Xk,d=k∗Eelec+k∗εfs∗d2∀d<ds,k∗εmp∗d4∀d≥ds,(2)ERk,d=k∗Eelec,where ds is the crossover distance calculated using
(3)ds=εfsεmp.


## 2.1. Data Dictionary

Table1 describes all the variables and constants used in this paper.Table 1
Variable list.
Variable name
Description
ET,X(k,d)
Energy required to transmitk bits at distance d.
E
R(k)
Energy required to receivek bits.
E
elec
Energy required to run transceiver circuitry.
ε
fs
The free space energy loss.
ε
mp
The multipath energy loss.
n
Total number of sensors.
n
alive
Total number of alive sensors.
E
r(i)
Residual energy ofith sensor.
E
max
Initial maximum energy of a sensor node.
d
B
S
2
Distance of the nearest node to the BS.
M
Side-length ofM × M deployment area.
N
CH
Desired number of CHs.
C(c)
cth cluster where c:1, 2, … , NCH.
N
C(c)
Total numbers of members in clusterC(c).
E
avg (C(c))
Average node energy in clusterC(c).
ANDCenC(c)
Average node distance incth cluster from its centroid.
D
Cen(j)
Distance ofjth member node from the cluster centroid.


## 2.2. Network Model

We have the following assumptions about the network:(1)
The sensors are randomly deployed. Sensors and the BS are immobile after deployment. The BS is located faraway and outside the observation field where sensors are deployed.(2)
All sensors know their physical location.(3)
All sensors are homogeneous: starting with the same initial energy, computational, and communication capabilities.(4)
All sensors have a limited energy source. Battery recharge or replacement is impossible after the deployment. The BS is not energy constrained.(5)
All sensors have limited sensing range but can adapt transmission power depending upon the transmission distance.(6)
Links between nodes are symmetric. A packet transmission between any two sensors takes the same amount of energy regardless of whichever node initiates the transmission.(7)
All sensors are sensing at a steady rate, and so they always have data to send.(8)
All sensors are fault-tolerant.(9)
Intercluster and intracluster communications are one-hop communication.


## 2.3. Energy Model

We have used an energy model to calculate the energy dissipation of a node while transmittingk bits at d distance and receiving k bits, respectively, which are as follows [13]:
(1)ET,Xk,d=k∗Eelec+k∗εfs∗d2∀d<ds,k∗εmp∗d4∀d≥ds,(2)ERk,d=k∗Eelec,where ds is the crossover distance calculated using
(3)ds=εfsεmp.


## 3. Background and Related Work

Energy saving routing schemes for WSN can be well-classified using the logical topology used to organize nodes in the network [14]. An ideal efficient topology should minimize energy consumption, the possibility of the message loss and radio interference between nodes with enhancing longevity and scalability of the network. Moreover, it should also deal with various aspects of managing a group such as a group size and management of new and nonfunctional (dead) nodes. Based on the topology, WSN routing schemes can be classified as flat, chain-based, tree-based, and cluster-based routing. Flat routing schemes use message flooding to find the routes between nodes. Therefore, they cannot be used as energy-saving schemes for WSNs. In this section, we discuss the major energy-saving routing schemes for WSNs, namely, chain-based, tree-based, and cluster-based routing. The primary focus of this section is on cluster-based routing schemes.


### 3.1. Chain-Based Routing

The chain-based protocols set up chains to connect the sensor nodes with one another with an objective to minimize the energy consumption during data transmission. After the chain formation, a random node is selected as the chain leader. It is responsible for transmitting data to the BS. All the other nodes forward their data to their successor node towards the BS. The successor node aggregates its data with the data received from the predecessor and then transmit it to its successor. This way data reaches to the leader. At any time, the leader can receive data from two directions and therefore, it uses the token passing scheme to start the data transmission from the ends of the chain [15].Power-efficient gathering in sensor information systems (PEGASIS) [15], Load balanced and energy efficient routing algorithm (LBEERA) [16], and chain-based hierarchical routing protocol (CHIRON) [17] are chain-based routing protocols. LBEERA and CHIRON use multiple chains. LEBEERA uses a centralized protocol for chain formation.


### 3.2. Tree-Based Routing

Tree-based protocols set up a logical tree of sensor nodes. All nodes send their data to their parent node. The parent node aggregates its data with the data received from its children and then transmit it to its parents. This way the data transmission proceeds from the end node to the root node (BS).TREEPSI [18] and Plus-tree [19] are tree-based routing protocols proposed for WSNs. The Plus-tree protocol stores alternative neighbor paths other than tree paths to transmit the data.


### 3.3. Cluster-Based Routing

Clustering techniques can be broadly classified as distributed [13, 20–30] and centralized clustering [20, 31–34] based on the answer to the following question: Who coordinates the cluster setup and the BS/CH?In distributed clustering, the CH selection is done either at the individual node level [13, 20, 21, 31] or using neighbor coordination [28, 29]. The CH selection can be random [13] or based on some predefined parameters such as residual energy [29, 30, 32, 33, 35], intercluster communication cost [29], distance from the sink [35], the number of neighbor nodes (node degree) [30], and timer-based approach [35]. The parameters can also be combined to get a trade-off between different parameters. Once the CHs get selected, they send their status to other nodes by broadcasting a message. The non-CH nodes join one of the CH based on a cluster formation algorithm. The decision mostly based on minimum cluster distance to reduce intercluster communication cost, but in the case of a load-balanced cluster, the non-CH node may join a higher communication cost CH [32, 33]. The performance of clustering technique highly depends on the CH selection and the way other nodes join a CH. The major drawbacks of distributed clustering are (1) not well distribution CHs; CHs may place into one area of the network. (2) No control over the total number of CHs; Any node which passes the CH selection test becomes the CH. In [29], the authors proposed a distributed clustering which achieves fairly well distribution of CHs.In centralized clustering, the BS takes the responsibility of cluster formation. All the nodes send their location, energy, and ID information to the BS. After analyzing the received information, the BS selects the optimum clusters. It then broadcasts information of all the clusters in the network. Upon receiving this information, each node finds its responsibility in the cluster by comparing its ID with the IDs of CH. If the node is CH, it takes the responsibility of data aggregation and data dissemination to the BS; otherwise, the node fetches its TDMA slot and goes to sleep until its transmission turn comes. LEACH-C [20] is a centralized cluster-based routing protocol. The BS runs simulated annealing optimization to determine the optimum clusters. After cluster formation, the BS broadcasts back the cluster information in the network, and then, data dissemination starts. BCDCP [33] is another centralized clustering protocol that uses cluster splitting for cluster formation and energy-aware minimum spanning tree of CHs for data dissemination. In BCDCP, CHs share the burden of sending data to the BS. In each communication round, a one randomly selected CH act as a leader for all other CHs. The other CHs communicate with the leader CH to reach the BS. In every setup phase of BCDCP, every node sends its energy information to the BS. BCDCP assumes that the BS keeps up-to-date information on location for all the nodes in the network. The major drawbacks of centralized clustering are (1) high energy dissipation at long distance in every communication round as each node sends it location, energy, and ID information to the BS. (2) They are suitable for small networks because they assume that all the nodes can directly communicate with the BS which is not always true for large networks.One common problem with both centralized and distributed clustering is related to the frequency of the clustering. The setup cost increases as the clustering frequency increases. To overcome this problem, they use the concept of CH rotation or VCH. In CH rotation/VCH technique, some of the communication rounds use clusters of their predecessor round with a new CH chosen among the CMs [20]. In the literature, the VCH is used to cut back the frequency of clustering [31, 36]. In VCH-ECCR, VCH is used for two purposes, and they are as follows:
(1)
To guard the CH: in existing centralized techniques, all the nodes directly send their energy and location updates to the BS at the beginning of each round. However, in VCH-ECCR, all transmissions to the BS are solely through the CH only, except for the first communication round. Therefore, the CH depletes its energy quickly. The VCH-ECCR uses Vice Cluster Head (VCH) to guard the CH against failure due to complete energy depletion.(2)
Additionally, it reduces the clustering frequency.CH rotation (or VCH) may lead to new problems, for instance, if the new CH (or VCH) is rotated solely based on residual energy than it may increase transmission cost of some CMs. It is possible that a new CH for the next round is located faraway from a member node compared to other CHs. As a result, the node has to use the large communication energy CH, while the CH of another cluster is nearby. VCH-ECCR takes both residual energy and intracluster communication cost into account for selecting a node as a VCH. LEACH-C and BCDCP routing techniques have been selected by the authors for performance evaluation as they also use the same concept of centralized clustering.


### 3.4. Discussion

During the literature survey of the energy-efficient routing protocols, the authors have found that chain-based techniques are more energy-efficient than cluster-based technologies and then, tree-based techniques come. Even then, clustering techniques are widely used because they make the network highly scalable with less topology management overhead. Chain-based protocols suffer from too much delay in the data collection. Tree-based techniques are proven to be more energy-efficient than cluster-based for data collection, but they also suffer from high topology maintenance [37].


## 3.1. Chain-Based Routing

The chain-based protocols set up chains to connect the sensor nodes with one another with an objective to minimize the energy consumption during data transmission. After the chain formation, a random node is selected as the chain leader. It is responsible for transmitting data to the BS. All the other nodes forward their data to their successor node towards the BS. The successor node aggregates its data with the data received from the predecessor and then transmit it to its successor. This way data reaches to the leader. At any time, the leader can receive data from two directions and therefore, it uses the token passing scheme to start the data transmission from the ends of the chain [15].Power-efficient gathering in sensor information systems (PEGASIS) [15], Load balanced and energy efficient routing algorithm (LBEERA) [16], and chain-based hierarchical routing protocol (CHIRON) [17] are chain-based routing protocols. LBEERA and CHIRON use multiple chains. LEBEERA uses a centralized protocol for chain formation.


## 3.2. Tree-Based Routing

Tree-based protocols set up a logical tree of sensor nodes. All nodes send their data to their parent node. The parent node aggregates its data with the data received from its children and then transmit it to its parents. This way the data transmission proceeds from the end node to the root node (BS).TREEPSI [18] and Plus-tree [19] are tree-based routing protocols proposed for WSNs. The Plus-tree protocol stores alternative neighbor paths other than tree paths to transmit the data.


## 3.3. Cluster-Based Routing

Clustering techniques can be broadly classified as distributed [13, 20–30] and centralized clustering [20, 31–34] based on the answer to the following question: Who coordinates the cluster setup and the BS/CH?In distributed clustering, the CH selection is done either at the individual node level [13, 20, 21, 31] or using neighbor coordination [28, 29]. The CH selection can be random [13] or based on some predefined parameters such as residual energy [29, 30, 32, 33, 35], intercluster communication cost [29], distance from the sink [35], the number of neighbor nodes (node degree) [30], and timer-based approach [35]. The parameters can also be combined to get a trade-off between different parameters. Once the CHs get selected, they send their status to other nodes by broadcasting a message. The non-CH nodes join one of the CH based on a cluster formation algorithm. The decision mostly based on minimum cluster distance to reduce intercluster communication cost, but in the case of a load-balanced cluster, the non-CH node may join a higher communication cost CH [32, 33]. The performance of clustering technique highly depends on the CH selection and the way other nodes join a CH. The major drawbacks of distributed clustering are (1) not well distribution CHs; CHs may place into one area of the network. (2) No control over the total number of CHs; Any node which passes the CH selection test becomes the CH. In [29], the authors proposed a distributed clustering which achieves fairly well distribution of CHs.In centralized clustering, the BS takes the responsibility of cluster formation. All the nodes send their location, energy, and ID information to the BS. After analyzing the received information, the BS selects the optimum clusters. It then broadcasts information of all the clusters in the network. Upon receiving this information, each node finds its responsibility in the cluster by comparing its ID with the IDs of CH. If the node is CH, it takes the responsibility of data aggregation and data dissemination to the BS; otherwise, the node fetches its TDMA slot and goes to sleep until its transmission turn comes. LEACH-C [20] is a centralized cluster-based routing protocol. The BS runs simulated annealing optimization to determine the optimum clusters. After cluster formation, the BS broadcasts back the cluster information in the network, and then, data dissemination starts. BCDCP [33] is another centralized clustering protocol that uses cluster splitting for cluster formation and energy-aware minimum spanning tree of CHs for data dissemination. In BCDCP, CHs share the burden of sending data to the BS. In each communication round, a one randomly selected CH act as a leader for all other CHs. The other CHs communicate with the leader CH to reach the BS. In every setup phase of BCDCP, every node sends its energy information to the BS. BCDCP assumes that the BS keeps up-to-date information on location for all the nodes in the network. The major drawbacks of centralized clustering are (1) high energy dissipation at long distance in every communication round as each node sends it location, energy, and ID information to the BS. (2) They are suitable for small networks because they assume that all the nodes can directly communicate with the BS which is not always true for large networks.One common problem with both centralized and distributed clustering is related to the frequency of the clustering. The setup cost increases as the clustering frequency increases. To overcome this problem, they use the concept of CH rotation or VCH. In CH rotation/VCH technique, some of the communication rounds use clusters of their predecessor round with a new CH chosen among the CMs [20]. In the literature, the VCH is used to cut back the frequency of clustering [31, 36]. In VCH-ECCR, VCH is used for two purposes, and they are as follows:
(1)
To guard the CH: in existing centralized techniques, all the nodes directly send their energy and location updates to the BS at the beginning of each round. However, in VCH-ECCR, all transmissions to the BS are solely through the CH only, except for the first communication round. Therefore, the CH depletes its energy quickly. The VCH-ECCR uses Vice Cluster Head (VCH) to guard the CH against failure due to complete energy depletion.(2)
Additionally, it reduces the clustering frequency.CH rotation (or VCH) may lead to new problems, for instance, if the new CH (or VCH) is rotated solely based on residual energy than it may increase transmission cost of some CMs. It is possible that a new CH for the next round is located faraway from a member node compared to other CHs. As a result, the node has to use the large communication energy CH, while the CH of another cluster is nearby. VCH-ECCR takes both residual energy and intracluster communication cost into account for selecting a node as a VCH. LEACH-C and BCDCP routing techniques have been selected by the authors for performance evaluation as they also use the same concept of centralized clustering.


## 3.4. Discussion

During the literature survey of the energy-efficient routing protocols, the authors have found that chain-based techniques are more energy-efficient than cluster-based technologies and then, tree-based techniques come. Even then, clustering techniques are widely used because they make the network highly scalable with less topology management overhead. Chain-based protocols suffer from too much delay in the data collection. Tree-based techniques are proven to be more energy-efficient than cluster-based for data collection, but they also suffer from high topology maintenance [37].


## 4. Vice-Cluster-Head-Enabled Centralized Clustering

Like all the clustering techniques, VCH-ECCR divides the communication process into several numbers of rounds. Each round comprised of a setup phase and data transmission phase. As previously mentioned, the setup phase is an overhead over actual data transmission. The primary focus of VCH-ECCR is to reduce this overhead. To accomplish this, VCH-ECCR uses Vice Cluster Head (VCH) and Vice-Vice Cluster Head (V-VCH). This two-level VCH hierarchy helps to reduce the energy required to transmit necessary information for the setup phase to perform clustering operations. It also reduces the frequency of the setup phase. In the following subsections, we describe each phase in detail.


### 4.1. Setup Phase

The setup phase is not identical for all communication rounds. It differs based on whether the network has clusters or not.


### 4.2. Setup Phase with Zero Clusters

When the network has zero clusters, each alive node sends a control packet to the BS which includes its ID, location, and energy information. A dead node is a node with zero residual energy. The BS uses location and energy information for two different purpose—location information for cluster formation and energy information for cluster head selection. After receiving the status information from all the nodes, the BS divides the network into several numbers of clusters. The number of clusters is not fixed, and in every reclustering, the clusters are changed. The total number of clusters is equal to the desired number of cluster heads which are calculated using [13]
(4)NCH=MdBS2εfsεmpnalive2π,where M is the sides of M×M deployment area, dBS2 is the distance of the nearest node to the BS, and nalive is the number of alive nodes. Initially, the value of nalive is equal to n. In each communication round, the protocol keeps track of alive nodes and updates the value of nalive.The BS usesk-means clustering with minimum distance criterion to minimize the within-cluster sum of squares for cluster formation. The BS divide the nodes of the network into NCH clusters (k=NCH) using (4). The base station calculates the Euclidean distance from each node to all centroids using the location information and assigns it to the centroid nearest to it. The performance of the k-means clustering depends heavily on the initial centroids. Poor initialization of centroids will produce poor clusters. In VCH-ECCR, initial centroids are selected using the k-means++ initial centroid selection method to avoid the poor distribution of centroids. k-means++ is an approximation algorithm for the NP-hard k-means problem. The algorithm starts by randomly choosing a centroid c0 from all nodes. For centroid ci, the probability of a node ni to be chosen as a centroid is proportional to its squared distance from its nearest centroid. k-means++ ensures the good distribution of CHs. After cluster formation, the BS does the following steps for each cluster C(c): c=1,…,k.Step 1.
Calculate the average node energy of each clusterEavgCc using
(5)EavgCc=∑j=1NEirN∀j∈Cc,
whereErj and EavgCc are the residual energy of the jth member node and average cluster energy of Cc, respectively.Step 2.
Select a set of member nodes,Sc, such that
(6)Erj>EavgCc.Step 3.
Calculate the average node distance from the centroid using(7)ANDCc=∑j=1NDCjN,where ANDCc is the average node distance of cluster Cc from its centroid, DCj is the distance of jth node from the centroid of the cluster, and N is the total number of cluster members (CMs).Step 4.
Apply functionF to each node of set Sc to obtain the weight vector Wc.
(8)Wc=FSc=ErjEmax−Erj2∗ANDCc−DCiDCi,
whereEmax represents the maximum energy of a node at the time of deployment. The multiplicand part of (8) ensures that the energy-rich node is selected as the CH whereas the multiplier part ensures that the node which minimizes the intracluster communication cost is selected as the CH.Step 5.
Select three nodes fromSc for which maximum weights are obtained in Wc, to act as CH, VCH, and V-VCH, respectively. The remaining nodes become the normal member of cluster Cc.Step 6.
Create TDMA schedule ofCc for data transmission.Step 7.
For the selected CHs of each cluster, construct a chain using a minimum spanning tree such that it minimizes energy consumption of each CH in transmitting data to the BS [33, 38].Step 8.
Broadcast a control packet into the network which includes information of each cluster.Step 9.
Upon receiving this, each node compares its ID with the IDs of CH, VCH, and V-VCH to know its responsibility in the cluster.(1)
If CH, then the node takes the responsibility of data aggregation of data received from CMs and transmits it to the BS.(2)
If VCH or V-VCH, then the node goes into the sleeping mode.(3)
If the node is not CH or VCH or V-VCH, then it fetches the ID of the corresponding CH along with the TDMA slot.


### 4.3. Setup Phase with Clusters

Each CH performs the following steps:Step 1.
Each CH checks its residual energy after every communication round, and if it is less than or equal to ten percent of initial energy (when handed the responsibility of the CH) it awakens the corresponding VCH. It then transfers its current state to the VCH such as IDs of all CMs and neighbor(s) information along the CH chain.Step 2.
The CH becomes the common node of the cluster.Step 3.
The VCH becomes the new CH, creates the new TDMA for the cluster, and broadcasts it to the CMs.Step 4.
The VCH joins the chain of CHs by sending a message to neighboring CHs (VCHs).Each VCH performs the following steps.Step 1.
Each VCH checks its residual energy after every communication round, and if it is less than or equal to ten percent of initial energy (when handed the responsibility of the VCH), it awakens the corresponding V-VCH. It then transfers its current state to the V-VCH such as IDs of all CMs and neighbor(s) information along the CH chain.Step 2.
The VCH becomes the common node of the cluster.Step 3.
The V-VCH informs its members and neighbors along the chain of CHs about the need of reclustering. Moreover, it asks its members, the neighbors, and their members to submit their current energy status.Step 4.
The neighboring CHs or VCHs or V-VCHs also inform their members about reclustering and ask them to submit their current energy status. After getting the reclustering message, the member nodes submit their current energy status to the associated CH/VCH/V-VCH. After this, the member nodes forget the associated cluster and its head and become the unclustered nodes. All the CHs/VCHs/V-VCHs submit the current energy status of themselves and their associated members to the V-VCH who called for reclustering and then become unclustered nodes.Step 5.
The V-VCH then sends energy status of all the nodes to the base station and becomes an unclustered node.Now the network is in zero cluster mode, and the base station applies the same clustering procedure used in Section3.2. New clusters will be formed; in addition to this, the number of clusters can also change because the value of nalive can change if some nodes are dead in the previous communication rounds. In intermediate communication rounds, any node does not directly transmit its energy information, if needed, to the BS. It sends it through CH or VCH. Therefore, if any of them fails due to the lack of energy, then all its members will get isolated from the network. In such a situation, the VCH protects the CH and takes responsibility of VCH on failure; likewise, V-VCH protects VCH and takes responsibility of VCH on failure. The CH/VCH periodically sends its energy status to VCH/V-VCH. In this way, VCH/V-VCH detects the state of CH/VCH, and if the CH/VCH has a severe problem, the VCH/V-VCH takes the responsibility of CH/VCH. Moreover, cluster members can trigger a recovery function if the communication link to the CH is dead and send their data to the VCH instead of the CH. Therefore, no data will be lost. This complete energy depletion situation does not apply to the V-VCH because if any of the clusters go into V-VCH state, the V-VCH calls for reclustering.


### 4.4. Data Transmission Phase

Data transmission phase consists of three subphases, namely, data collection, data aggregation, and data routing. During data collection, each node sends its sensed data to the corresponding CH (VCH). Once data from all the CMs is received, the CH (VCH) aggregates the received data. After aggregation, a randomly chosen CH receives data from all the clusters of the network. It aggregates the received data and transmits it to the BS. The VCH-ECCR uses code-division multiple access (CDMA) to counteract the radio interference caused by neighboring clusters. A unique spreading code is assigned to each cluster to differentiate their CMs data from CMs of neighboring clusters.The need of a random CH that sends data to the BS is justified since the data transmission to the BS is an energy-intensive job. If we use the CHs’ closest to the BS to carry out this task regularly, then it results in heavy and quick depletion of energy resources for the CHs’ closer to the BS. Therefore, by randomizing the CH transmissions to the BS, VCH-ECCR distributes the load of routing evenly among all the cluster heads.


## 4.1. Setup Phase

The setup phase is not identical for all communication rounds. It differs based on whether the network has clusters or not.


## 4.2. Setup Phase with Zero Clusters

When the network has zero clusters, each alive node sends a control packet to the BS which includes its ID, location, and energy information. A dead node is a node with zero residual energy. The BS uses location and energy information for two different purpose—location information for cluster formation and energy information for cluster head selection. After receiving the status information from all the nodes, the BS divides the network into several numbers of clusters. The number of clusters is not fixed, and in every reclustering, the clusters are changed. The total number of clusters is equal to the desired number of cluster heads which are calculated using [13]
(4)NCH=MdBS2εfsεmpnalive2π,where M is the sides of M×M deployment area, dBS2 is the distance of the nearest node to the BS, and nalive is the number of alive nodes. Initially, the value of nalive is equal to n. In each communication round, the protocol keeps track of alive nodes and updates the value of nalive.The BS usesk-means clustering with minimum distance criterion to minimize the within-cluster sum of squares for cluster formation. The BS divide the nodes of the network into NCH clusters (k=NCH) using (4). The base station calculates the Euclidean distance from each node to all centroids using the location information and assigns it to the centroid nearest to it. The performance of the k-means clustering depends heavily on the initial centroids. Poor initialization of centroids will produce poor clusters. In VCH-ECCR, initial centroids are selected using the k-means++ initial centroid selection method to avoid the poor distribution of centroids. k-means++ is an approximation algorithm for the NP-hard k-means problem. The algorithm starts by randomly choosing a centroid c0 from all nodes. For centroid ci, the probability of a node ni to be chosen as a centroid is proportional to its squared distance from its nearest centroid. k-means++ ensures the good distribution of CHs. After cluster formation, the BS does the following steps for each cluster C(c): c=1,…,k.Step 1.
Calculate the average node energy of each clusterEavgCc using
(5)EavgCc=∑j=1NEirN∀j∈Cc,
whereErj and EavgCc are the residual energy of the jth member node and average cluster energy of Cc, respectively.Step 2.
Select a set of member nodes,Sc, such that
(6)Erj>EavgCc.Step 3.
Calculate the average node distance from the centroid using(7)ANDCc=∑j=1NDCjN,where ANDCc is the average node distance of cluster Cc from its centroid, DCj is the distance of jth node from the centroid of the cluster, and N is the total number of cluster members (CMs).Step 4.
Apply functionF to each node of set Sc to obtain the weight vector Wc.
(8)Wc=FSc=ErjEmax−Erj2∗ANDCc−DCiDCi,
whereEmax represents the maximum energy of a node at the time of deployment. The multiplicand part of (8) ensures that the energy-rich node is selected as the CH whereas the multiplier part ensures that the node which minimizes the intracluster communication cost is selected as the CH.Step 5.
Select three nodes fromSc for which maximum weights are obtained in Wc, to act as CH, VCH, and V-VCH, respectively. The remaining nodes become the normal member of cluster Cc.Step 6.
Create TDMA schedule ofCc for data transmission.Step 7.
For the selected CHs of each cluster, construct a chain using a minimum spanning tree such that it minimizes energy consumption of each CH in transmitting data to the BS [33, 38].Step 8.
Broadcast a control packet into the network which includes information of each cluster.Step 9.
Upon receiving this, each node compares its ID with the IDs of CH, VCH, and V-VCH to know its responsibility in the cluster.(1)
If CH, then the node takes the responsibility of data aggregation of data received from CMs and transmits it to the BS.(2)
If VCH or V-VCH, then the node goes into the sleeping mode.(3)
If the node is not CH or VCH or V-VCH, then it fetches the ID of the corresponding CH along with the TDMA slot.


## 4.3. Setup Phase with Clusters

Each CH performs the following steps:Step 1.
Each CH checks its residual energy after every communication round, and if it is less than or equal to ten percent of initial energy (when handed the responsibility of the CH) it awakens the corresponding VCH. It then transfers its current state to the VCH such as IDs of all CMs and neighbor(s) information along the CH chain.Step 2.
The CH becomes the common node of the cluster.Step 3.
The VCH becomes the new CH, creates the new TDMA for the cluster, and broadcasts it to the CMs.Step 4.
The VCH joins the chain of CHs by sending a message to neighboring CHs (VCHs).Each VCH performs the following steps.Step 1.
Each VCH checks its residual energy after every communication round, and if it is less than or equal to ten percent of initial energy (when handed the responsibility of the VCH), it awakens the corresponding V-VCH. It then transfers its current state to the V-VCH such as IDs of all CMs and neighbor(s) information along the CH chain.Step 2.
The VCH becomes the common node of the cluster.Step 3.
The V-VCH informs its members and neighbors along the chain of CHs about the need of reclustering. Moreover, it asks its members, the neighbors, and their members to submit their current energy status.Step 4.
The neighboring CHs or VCHs or V-VCHs also inform their members about reclustering and ask them to submit their current energy status. After getting the reclustering message, the member nodes submit their current energy status to the associated CH/VCH/V-VCH. After this, the member nodes forget the associated cluster and its head and become the unclustered nodes. All the CHs/VCHs/V-VCHs submit the current energy status of themselves and their associated members to the V-VCH who called for reclustering and then become unclustered nodes.Step 5.
The V-VCH then sends energy status of all the nodes to the base station and becomes an unclustered node.Now the network is in zero cluster mode, and the base station applies the same clustering procedure used in Section3.2. New clusters will be formed; in addition to this, the number of clusters can also change because the value of nalive can change if some nodes are dead in the previous communication rounds. In intermediate communication rounds, any node does not directly transmit its energy information, if needed, to the BS. It sends it through CH or VCH. Therefore, if any of them fails due to the lack of energy, then all its members will get isolated from the network. In such a situation, the VCH protects the CH and takes responsibility of VCH on failure; likewise, V-VCH protects VCH and takes responsibility of VCH on failure. The CH/VCH periodically sends its energy status to VCH/V-VCH. In this way, VCH/V-VCH detects the state of CH/VCH, and if the CH/VCH has a severe problem, the VCH/V-VCH takes the responsibility of CH/VCH. Moreover, cluster members can trigger a recovery function if the communication link to the CH is dead and send their data to the VCH instead of the CH. Therefore, no data will be lost. This complete energy depletion situation does not apply to the V-VCH because if any of the clusters go into V-VCH state, the V-VCH calls for reclustering.


## 4.4. Data Transmission Phase

Data transmission phase consists of three subphases, namely, data collection, data aggregation, and data routing. During data collection, each node sends its sensed data to the corresponding CH (VCH). Once data from all the CMs is received, the CH (VCH) aggregates the received data. After aggregation, a randomly chosen CH receives data from all the clusters of the network. It aggregates the received data and transmits it to the BS. The VCH-ECCR uses code-division multiple access (CDMA) to counteract the radio interference caused by neighboring clusters. A unique spreading code is assigned to each cluster to differentiate their CMs data from CMs of neighboring clusters.The need of a random CH that sends data to the BS is justified since the data transmission to the BS is an energy-intensive job. If we use the CHs’ closest to the BS to carry out this task regularly, then it results in heavy and quick depletion of energy resources for the CHs’ closer to the BS. Therefore, by randomizing the CH transmissions to the BS, VCH-ECCR distributes the load of routing evenly among all the cluster heads.


## 5. Performance Evaluation

The performance of VCH-ECCR has been evaluated using MATLAB simulation and compared with LEACH [13, 20], LEACH-C [13, 20], and BCDCP [33].


### 5.1. Performance Metrics

The following performance metrics are used to evaluate the performance of VCH-ECCR:(1)
Average energy consumption(2)
Lifetime of the network(3)
ThroughputThe average energy consumption is the proportion of the total amount of energy used per node to send data to the BS. There are various definitions of network’s lifetime which have been proposed in the literature such as the time until the first or last node dies and the time until all the nodes die. Throughput is calculated as the total number of data packets received at the BS per communication round.


### 5.2. Results and Discussion

We simulate 50 different 100 × 100 m2 random network scenarios for the performance evaluation. The value of network parameters during simulation is specified in Table 2.Table 2
Network model parameters.
Network parameter
Value
Network area
100 × 100 m2
Total numbers of nodes (n)
500
Initial energy of nodes (Einit)
2 J
Coefficient for free-space fading (εfs)
10 pJ/bit/m2
Coefficient for multipath fading (εmp)
0.0013 pJ/bit/m2
Data packet size
6400 bits
Control packet size
200 bits
Idle state energy (ET,X = ER)
50 nJ/bit
Data-aggregation energy
5 nJ/bit/signal
Round length
40 TDMA data framesFigure2 shows the alive nodes over the communication rounds. All the nodes remain alive for VCH-ECCR till 27 rounds while it is 14, 16, and 21 for LEACH, LEACH-C, and BCDCP, respectively. Moreover, if the network lifetime is defined as the number of rounds till 50 percent of the nodes remains alive, VCH-ECCR outperforms LEACH, LEACH-C, and BCDCP by 45, 26, and 10 percent, respectively. It is because the VCH-ECCR has good control over the reclustering duration. When the residual energy of CH is less than or equal to a low threshold, it awakens the VCH. The VCH expands all of its energy only as a CH before that it is in sleep mode.Figure 2
A comparison on the network lifetime.Figure3 shows that the average energy consumption for VCH-ECCR is less than its comparative. On average, the energy expenditure of VCH-ECCR is reduced by 50, 20, and 11 percent over LEACH, LEACH-C, and BCDCP, respectively. The reduction in average energy consumption of VCH-ECCR is justified for the following reasons: (1) in VCH-ECCR, the setup overhead is minimal compared to its comparative. In LEACH after every communication round, all CHs broadcast their status to other nodes, and then the non-CH nodes send a joining message to the CH. In LEACH-C and BCDCP, all nodes send their energy status directly to the BS whereas in the case of VCH-ECCR all communications are only through CHs. (2) The provision of VCH delays the reclustering time. (3) The node which is rich in energy and minimizes the intracluster communication cost becomes the CH for a cluster. (4) The CHs are not fixed and gets updated on every reclustering based on the nodes that are alive in the network.Figure 3
A comparison of average energy consumption.Figure4 shows the number of data packets received at the BS over the communication rounds. It is very clear from the plot that the VCH-ECCR is more effective as it delivers significantly more data messages than its comparative. The VCH-ECCR delivers 153819 data packets to the BS until the last node dies while LEACH, LEACH-C, and BCDCP deliver 102919, 121863, and 139500, respectively. It is because we have guarded the CH using VCH, and VCH is guarded by the V-VCH. For most of the communication rounds, the CH (VCH) does not die because of complete battery depletion. When they expand 90% of their energy, they become the normal nodes of the cluster.Figure 4
A comparison on the received packets by the base station.Figure5 shows the average reclustering time in rounds for VCH-ECCR and its comparatives. The average reclustering time for VCH-ECCR is 1.85 communication rounds approximately whereas for LEACH, LEACH-C, and BCDCP it is one communication round because, after every round LEACH, LEACH-C, and BCDCP perform re-clustering. The main factors that affect the reclustering duration are failure of CH/VCH and density of the cluster. The CH/VCH failure, in any cluster, will soon switch that cluster in V-VCH mode and then the V-VCH will call for reclustering. Similarly, if the cluster is highly dense, the CH/VCH quickly run out of their energy and the cluster will quickly go into the V-VCH mode and then the reclustering happens.Figure 5
A comparison of average reclustering time.


## 5.1. Performance Metrics

The following performance metrics are used to evaluate the performance of VCH-ECCR:(1)
Average energy consumption(2)
Lifetime of the network(3)
ThroughputThe average energy consumption is the proportion of the total amount of energy used per node to send data to the BS. There are various definitions of network’s lifetime which have been proposed in the literature such as the time until the first or last node dies and the time until all the nodes die. Throughput is calculated as the total number of data packets received at the BS per communication round.


## 5.2. Results and Discussion

We simulate 50 different 100 × 100 m2 random network scenarios for the performance evaluation. The value of network parameters during simulation is specified in Table 2.Table 2
Network model parameters.
Network parameter
Value
Network area
100 × 100 m2
Total numbers of nodes (n)
500
Initial energy of nodes (Einit)
2 J
Coefficient for free-space fading (εfs)
10 pJ/bit/m2
Coefficient for multipath fading (εmp)
0.0013 pJ/bit/m2
Data packet size
6400 bits
Control packet size
200 bits
Idle state energy (ET,X = ER)
50 nJ/bit
Data-aggregation energy
5 nJ/bit/signal
Round length
40 TDMA data framesFigure2 shows the alive nodes over the communication rounds. All the nodes remain alive for VCH-ECCR till 27 rounds while it is 14, 16, and 21 for LEACH, LEACH-C, and BCDCP, respectively. Moreover, if the network lifetime is defined as the number of rounds till 50 percent of the nodes remains alive, VCH-ECCR outperforms LEACH, LEACH-C, and BCDCP by 45, 26, and 10 percent, respectively. It is because the VCH-ECCR has good control over the reclustering duration. When the residual energy of CH is less than or equal to a low threshold, it awakens the VCH. The VCH expands all of its energy only as a CH before that it is in sleep mode.Figure 2
A comparison on the network lifetime.Figure3 shows that the average energy consumption for VCH-ECCR is less than its comparative. On average, the energy expenditure of VCH-ECCR is reduced by 50, 20, and 11 percent over LEACH, LEACH-C, and BCDCP, respectively. The reduction in average energy consumption of VCH-ECCR is justified for the following reasons: (1) in VCH-ECCR, the setup overhead is minimal compared to its comparative. In LEACH after every communication round, all CHs broadcast their status to other nodes, and then the non-CH nodes send a joining message to the CH. In LEACH-C and BCDCP, all nodes send their energy status directly to the BS whereas in the case of VCH-ECCR all communications are only through CHs. (2) The provision of VCH delays the reclustering time. (3) The node which is rich in energy and minimizes the intracluster communication cost becomes the CH for a cluster. (4) The CHs are not fixed and gets updated on every reclustering based on the nodes that are alive in the network.Figure 3
A comparison of average energy consumption.Figure4 shows the number of data packets received at the BS over the communication rounds. It is very clear from the plot that the VCH-ECCR is more effective as it delivers significantly more data messages than its comparative. The VCH-ECCR delivers 153819 data packets to the BS until the last node dies while LEACH, LEACH-C, and BCDCP deliver 102919, 121863, and 139500, respectively. It is because we have guarded the CH using VCH, and VCH is guarded by the V-VCH. For most of the communication rounds, the CH (VCH) does not die because of complete battery depletion. When they expand 90% of their energy, they become the normal nodes of the cluster.Figure 4
A comparison on the received packets by the base station.Figure5 shows the average reclustering time in rounds for VCH-ECCR and its comparatives. The average reclustering time for VCH-ECCR is 1.85 communication rounds approximately whereas for LEACH, LEACH-C, and BCDCP it is one communication round because, after every round LEACH, LEACH-C, and BCDCP perform re-clustering. The main factors that affect the reclustering duration are failure of CH/VCH and density of the cluster. The CH/VCH failure, in any cluster, will soon switch that cluster in V-VCH mode and then the V-VCH will call for reclustering. Similarly, if the cluster is highly dense, the CH/VCH quickly run out of their energy and the cluster will quickly go into the V-VCH mode and then the reclustering happens.Figure 5
A comparison of average reclustering time.


## 6. Reclustering Overhead Analysis

The energy consumption of the sensor node is due to the sensing, processing, transmitting, receiving, and overhearing or idle listening to the channel. Packet transmission and reception take the lion share of overall energy consumption compared to the other three factors. Therefore, we have done an overhead analysis of VCH-ECCR in terms of a number of control packet generated during communication round. The number of control packets generated in VCH-ECCR is compared with the control packets generated in LEACH, LEACH-C, and BCDCP. Table3 shows the number of control packets generated for LEACH, LEACH-C, BCDCP, and VCH-ECCR. Let us assume that N sensor nodes are distributed randomly in M×M sensor field. The expected number of CHs per round is NCH. The entire network is divided into NCH clusters and each cluster includes a cluster head and the remaining N/NCH−1 noncluster head nodes.Table 3
A comparison on a number of control packets generated.
Protocol
Number of control packets generated
Reclustering/CH rotation frequency
First round
Rest of the rounds
LEACH
N + N
CH
N + N
CH
In every round, reclustering happens at local level.
LEACH-C
N + 1
N + 1
In every round, reclustering happens at the BS level.
BCDCP
N + 1
N + 1
In every round, reclustering happens at the BS level.
VCH-ECCR
N + N
CH
N + N
CH
+ 1
Clustering occurs after every 1.85 rounds. See Figure5 to see the average reclustering time for VCH-ECCR.In LEACH, the control messages are generated for advertisement phase, joining message for CH, and TDMA-schedule broadcast before sending actual data to the corresponding CH. The number of control messages generated in every round of leach is given byNCH+NCHN/NCH−1+NCH⇒N+NCH. NCH nodes advertise their CH status, N/NCH−1 nodes join to NCH CHs, and NCH CHs broadcast TDMA schedule for their member nodes.In LEACH-C, all nodes send their current energy and location status to the BS in every communication round. The BS forms optimal clusters and selects CH for each cluster and broadcast this information back into the network. So, the number of control messages generated in every round of LEACH-C is given byN + 1. N nodes send their status to the BS, and the BS broadcasts one packet in the network.In BCDCP, all nodes send their current energy to the BS in every communication round. The BS divides the network into a desired number of clusters using a load-balanced cluster spiting process and broadcasts this information back into the network. So, the number of control messages generated in every round of BCDCP is given byN + 1. N nodes send their status to the BS, and the BS broadcasts one packet in the network.In VCH-ECCR, the number of control messages generated in the first round is given byN + 1 similar to LEACH-C and BCDCP. On each reclustering, when any cluster goes into V-VCH status, new clusters are formed. So, the number of control messages generated is given by 1+N/NCH−1+1+NCH−1∗1+N/NCH−1+1+1⇒N+NCH+1. V-VCH broadcast one reclustering message for its members and neighbors. NCH−1 CHs/VCHs broadcast reclustering message for their members. In NCH, cluster N/NCH−1 members send their current energy and location information to the corresponding CH/VCH. NCH-1 CHs/VCHs transmit current energy and location information of themselves and their members to the V-VCH who called for reclustering. The V-VCH then generates one control packet and sends the energy status of all the nodes to the base station. Based on the feedback, the BS forms new clusters and broadcast one control packet in the network.Table3 makes it clear that the VCH-ECCR generates less control packets than LEACH, LEACH-C, and BCDCP protocols in the event of reclustering. The average reclustering time for VCH-ECCR is 1.85 communication rounds. Since the average reclustering time for VCH-ECCR is 1.85 communication rounds, it generates control packets after every 1.85 communication rounds. Moreover, the control packets generated in LEACH-C and BCDCP is for the BS. So, the nodes have to incur high energy dissipation at long distance. While in VCH-ECCR, the control packets are for CHs/VCHs at the local level and only one node (V-VCH) sends a control packet to the BS.


## 7. Conclusions

The VCH-ECCR is the centralized cluster-based communication protocol for WSNs which reduces the overall average energy consumption of the network. In VCH-ECCR, all the communications to the BS are allowed solely through CH/VCH/V-VCH which leads to a reduction in energy consumption of individual nodes. Moreover, the provision of VCH and V-VCH reduces the frequency of clustering thereby reducing the energy consumption. Simulation results show that the VCH-ECCR outperforms its comparative regarding network lifetime, average energy consumption, and throughput.In VCH-ECCR, we have assumed that the nodes are fault-tolerant but if the nodes are not fault-tolerant and if the CH (VCH) dies for other reasons (not because of complete battery depletion) then it leads to the isolation of all the cluster members from the network. In VCH-ECCR, we have assumed that the intercluster and intracluster communication are one-hop communication and this limits the scalability of the WSN. This problem can be tackled if we allow multihop communication by the CHs.



---

*Source: 8946576-2017-12-14.xml*