# An Energy-Efficient Clustering Routing for Wireless Sensor Networks Based on Energy Consumption Optimization

Authors: Xu Huibin; Zeng Mengjia
Journal: International Journal of Digital Multimedia Broadcasting
 (2022)

---

## Abstract

In order to alleviate energy consumption of wireless sensor networks (WSNs), energy consumption optimization-based clustering routing (ECOR) is proposed in this paper. In ECOR, network is gridding by hexagon. And there is only a cluster head (CH) in each hexagon, which makes the distribution of CHs more even. Residual energy of nodes and distance from the centroid of hexagon are used to elect CHs. For any a CH, dynamic time slot allocation strategy is adopted to allocate time slot for its cluster members. According to status of cluster members, the duration of time slot is dynamically adjusted. In intercluster communication, the Dijkstra algorithm is used to construct the shortest path between CHs in order to shorten the distance of transmitting data. Simulation results show that the ECOR algorithm outperforms the improved-Low Energy Adaptive Clustering Hierarchy (I-LEACH) algorithm in terms of distribution of CHs and energy consumption.


---

## Body

## 1. Introduction

In wireless sensor networks (WSNs), a sensor node (or simply a node) is a device that can gather sensory information, perform some processing, and communicate with other nodes [1, 2]. However, limited energy capacity [3] and computation limit the applications of these devices.Therefore, energy efficiency is crucial performance of WSNs. Many studies show that routing protocol plays an important role in saving energy of nodes [4]. The clustering routing protocol [5, 6] were applied in WSNs since that it has the advantages of scalability, resource sharing, and energy saving.One of the most popular and widely clustering protocols is the low-energy adaptive clustering hierarchy (LEACH) [7], which is presented by Heinzelman et al. It is probabilistic approach that randomly selects cluster heads (CHs) in each round. After the CH selection, CHs broadcast information toward nearby nodes to form clustering. Receiving the information, nearby nodes will select the nearest CH to join [8]. Then, member nodes (MNs) send data toward its CHs.Though LEACH improves energy efficiency of network, some disadvantages are associated with it. One is the network lifetime. In LEACH, a sensor node with least residual energy may be selected to be a CH, which may be reduce the network lifetime. Another is distribution of CHs. Random selection of CHs results in the uneven distribution of CHs [9–11].Therefore, energy consumption optimization-based clustering routing (ECOR) is proposed in this paper. The monitoring area is gridding by hexagon, and the CH is selected in each hexagon to make CH distribution more even. The weight of nodes to be a CH is computed. Energy of nodes and distance from the centroid of hexagon is taken into account when the weight was computed. In each hexagon, node with the biggest weight is selected to be a CH.Intracluster communication, the duration of time slot is adjusted to reduce consumption of energy. In Intercluster communication, the Dijkstra algorithm is applied to construct the shortest path between CHs, and the consumption of CHs’ energy are reduced.The rest of this paper is organized as follows: Section2 presents related works. Section 3 describes the system model, including network model, energy consumption model, and round structure. Section 4 presents the proposed routing in detail. Section 5 explains the analysis of simulation results. Finally, we conclude this paper in Section 6.


## 2. Related Works

Reference [12] proposed a residual energy-based cluster-head selection algorithm so that the network lifetime is improved. The algorithm focuses on an efficient CH selection scheme. In CH selection process, energy and an optimum value of CHs are used to elect the next round CHs. Similar to work in reference [12], reference [13] also proposed a CH selection algorithm. CH election has done based on threshold energy, residual energy, and optimum numbers of clusters.In addition, both references [14, 15] have reduced the consumption of energy in view of simplifying sensing data of nodes. Namely, the aim of reference [14] is to reduce the energy consumption by reducing the number of sensors reporting information to the sink without worsening the reliability, while basic idea of reference [15] is to weight the information detected by the sensors according to the distortion area to better estimate the event at the sink node.Reference [16] proposed the improved LEACH (I-LEACH) algorithm, which optimized the energy consumption of the whole network to determine the optimal number of CHs. And the threshold of CH selection was set by the idea of equalization. Reference [17] proposed a particle swarm optimization-based cluster routing to make CH distribution more even. However, the single hop communication mode is still adopted in data transmission, which increases energy consumption of data transmission. In addition, reference [18] proposed wolf optimizer-based centralized cluster algorithm. The algorithm selects CHs using the grey wolf optimizer.Reference [19] proposed fuzzy comprehensive evaluation-based energy-efficient cluster routing (FCCR). In FCCR, the improved K-means cluster is used to form clustering. The CH selection is optimized by using fuzzy comprehensive evaluation. Reference [20] proposed the improved-firefly-based clustering (IFFC) algorithm. It uses the improved firefly clustering algorithm to form clustering. The algorithm has two main advantages. One is even distribution of CHs, and another is that balance the energy consumption between heterogeneous nodes. And frequency of reclustering is dropped. However, the IFFC algorithm did not optimize the data transmission path of intercluster communication.


## 3. System Model

### 3.1. Network Model

N sensor nodes are randomly deployed in ℓa×ℓbm2 area. The relevant constraints of network model are as follows [10]:
(1)
Initial state of all nodes is same. That is, battery capacity of each node is same. The energy consumption of transferring unit data to unit distance is same for all nodes(2)
There is only a base station (BS) in the network, and its energy is not limited(3)
Physical position of all nodes is fixed after the deployment(4)
Each node has its own ID. They can know their remaining energy and position. In addition, each node is able to fuse with its received data(5)
The communication link is symmetrical. For each node, the distance between transmitter and receiver is estimated through received signal strength index (RSSI). The transmitting power and communication radius of node can be adjusted by itselfMoreover, some important notations used in this paper are summarized in Notation1.Notation 1. Notations and their descriptions.
Notation: Description,
d:Distance between transmitter and receiver,
ETxm,d:Consumed energy that the transmitter transmit m bits data toward receiver,
ERxm,d:Consumed energy that the receiver received m bit data,
Ξk:kst hexagon,
Nk:The set of nodes in Ξk,
Si:ist sensor node,
Xi:Position vector of si,
Wik:Weight of si that located in Ξk,
Eires:Residual energy of si,
Ekavg:Average residual energy of all nodes in Ξk,
Ft,j:State of si in frame tst,
λt+1,j:Time slot adjustment factor of si in t+1st frame,
Ci:Represent the ist CH,
Ecires:Residual energy of all nodes in Ci.


### 3.2. Energy Consumption Model

The energy consumption model [21, 22] of the ECOR algorithm is as shown in Figure 1. Let ETxm,d refers to consumed energy that the transmitter transmits m bits data toward receiver. And the distance between transmitter and receiver is d.
(1)ETxm,d=mEelec+mεfsd2,ifd≤d0,mEelec+mεampd4,ifd>d0,where Eelec represents the consumed energy that transmitted per bit data. εfs and εamp represent energy-consuming factor under free space and double-path fading model, respectively, d0=εfs/εamp.Figure 1
Energy consumption model.Received node consumes energyERxm to receive m bit data:
(2)ERxm=mEelec.


### 3.3. Round Structure

Each round consists of the initial phase and data transmission phase. In the initial phase, the CH selection is completed, and cluster is formed. In data transmission phase, time is divided into different equal time slots [23]. The duration of the allocated time slot is adjusted through the node state.Each node transmits its data toward its CH in its time slot, as shown in Figure2. The data transmission phase is composed of multiple frames. At the end of each frame, CH transmits data toward BS.Figure 2
Round structure.


## 3.1. Network Model

N sensor nodes are randomly deployed in ℓa×ℓbm2 area. The relevant constraints of network model are as follows [10]:
(1)
Initial state of all nodes is same. That is, battery capacity of each node is same. The energy consumption of transferring unit data to unit distance is same for all nodes(2)
There is only a base station (BS) in the network, and its energy is not limited(3)
Physical position of all nodes is fixed after the deployment(4)
Each node has its own ID. They can know their remaining energy and position. In addition, each node is able to fuse with its received data(5)
The communication link is symmetrical. For each node, the distance between transmitter and receiver is estimated through received signal strength index (RSSI). The transmitting power and communication radius of node can be adjusted by itselfMoreover, some important notations used in this paper are summarized in Notation1.Notation 1. Notations and their descriptions.
Notation: Description,
d:Distance between transmitter and receiver,
ETxm,d:Consumed energy that the transmitter transmit m bits data toward receiver,
ERxm,d:Consumed energy that the receiver received m bit data,
Ξk:kst hexagon,
Nk:The set of nodes in Ξk,
Si:ist sensor node,
Xi:Position vector of si,
Wik:Weight of si that located in Ξk,
Eires:Residual energy of si,
Ekavg:Average residual energy of all nodes in Ξk,
Ft,j:State of si in frame tst,
λt+1,j:Time slot adjustment factor of si in t+1st frame,
Ci:Represent the ist CH,
Ecires:Residual energy of all nodes in Ci.


## 3.2. Energy Consumption Model

The energy consumption model [21, 22] of the ECOR algorithm is as shown in Figure 1. Let ETxm,d refers to consumed energy that the transmitter transmits m bits data toward receiver. And the distance between transmitter and receiver is d.
(1)ETxm,d=mEelec+mεfsd2,ifd≤d0,mEelec+mεampd4,ifd>d0,where Eelec represents the consumed energy that transmitted per bit data. εfs and εamp represent energy-consuming factor under free space and double-path fading model, respectively, d0=εfs/εamp.Figure 1
Energy consumption model.Received node consumes energyERxm to receive m bit data:
(2)ERxm=mEelec.


## 3.3. Round Structure

Each round consists of the initial phase and data transmission phase. In the initial phase, the CH selection is completed, and cluster is formed. In data transmission phase, time is divided into different equal time slots [23]. The duration of the allocated time slot is adjusted through the node state.Each node transmits its data toward its CH in its time slot, as shown in Figure2. The data transmission phase is composed of multiple frames. At the end of each frame, CH transmits data toward BS.Figure 2
Round structure.


## 4. ECOR Routing

### 4.1. Hexagonal Grid-Based Cluster

The interesting region is divided into hexagon. There is only a CH in each hexagon to make the distribution of CH more even, as shown Figure3. Centroid is the same distance from any point on the edge of the hexagon. If the node close to the centroid is chosen as the CH, the whole network can be covered with the smallest numbers of CH.Figure 3
Hexagonal grid-based cluster model.We considerℓa×ℓb area of the 2D plane. And the number of centroid is
(3)M=ℓa×ℓbA,where ⋅ represents floor function. A=3/23R2 is the area of a hexagon. R represents the radius of inner tangential circle of the hexagon. xkc is the position vector of centroid the of kst hexagon Ξk, and k=1,2,⋯,M.If all CHs are located at the centroid of hexagons, the network can be covered with the least numbers of CHs, which is also the original intention of adopting hexagonal grid-based cluster scheme. BS loads all position vectors into Hello packet and broadcasts the Hello packet throughout the network.Received from position vectors, each node computes the distance from the centroids of all hexagons. The node is inkst hexagon Ξk, if the distance from xkc is not more than R, k=1,2,⋯,M, so that these nodes know in which hexagon they are.LetNk represents the set of nodes in kst hexagonΞk, k=1,2,⋯,M, and its definition is given by
(4)Nk=sixi−xkc<R,Where xi represents the position vector of si, and i=1,2,⋯,N..


### 4.2. Selection of CHs and Cluster Formation

In the initial phase, the tentative CHs are initially chosen using a back-off timer [24]. Each tentative CH will collect average residual energy of all nodes in its hexagon. The timer value is inversely proportional to the residual energy level of node. For instance, the back-off timer value will be low if the energy level is high, and vice versa.Therefore, back-off timer value will be expired soon for the nodes with higher energy level. Once the back-off timer reaches zero, the respective node declares itself as tentative CH and broadcast tentative CH advertisement message (Ten_CH) within its hexagon. When any of the nodes in hexagon receives Ten_CH before its timer expires, it transmits its residual energy level toward the tentative CH. When tentative CH has received residual energy level of all nodes in its hexagon, it calculates the average residual energy of all nodes in hexagon, which is given by
(5)Ekavg=1Nk∑h=1NkEhres,sh∈Nk,Where Ekavg is the average residual energy of all nodes in hexagon Ξk. Ehres denotes the residual energy of node sh. Nk is the number of elements in the set Ξk.It is worth explaining that the node with the largest remaining energy is chosen as tentative CH because energy is consumed to calculate the average energy consumption and broadcast this information. This helps balance the residual energy levels of nodes in the hexagon.Residual energy of node and distance of node from centroid of the hexagon are used to compute the weight. Then, the node with the largest weight will be selected to be a CH. LetWik denote the weight of node si∈Nithat is located in kst hexagon Ξk, and its definition is given by
(6)Wik=αEiresEint+β1−di,ΞkR,Eires≥Ekavg0,Eires<Ekavg,whereEires denotes the residual energy of node si∈Ni. Eint denotes initial energy of node si∈Ni. According to the abovementioned network model, the initial energy of all nodes is equal. di,Ξk is the distance between the node si and the centroid of the hexagon. Both α and β are the weight coefficients, which control the proportion of residual energy and distance in the weight value.According to equation (6), when the residual energy of a node is lower than the average residual energy of all nodes in the hexagon in which the node located, the weight of the node is zero. The node with largest weight in each hexagon will be selected to be a CH of the hexagon. The entire process is depicted in a flowchart as shown in Figure 4.Figure 4
Flowchart of selecting CH.After the selection of CHs, CHs broadcastInv_CH message to nearby nodes for clustering. Each node chooses the closest CH to join using optimal distance communication. Therefore, MNs send Join_CH message toward the closest CH. Eventually cluster formation is done.


### 4.3. Intracluster Communication

After CH was selected, CH will allocate time slot to its MNs in the way of time division multiple access (TDMA) [25]. MNs would transmit data toward CH during its allocated time slot.


#### 4.3.1. Initial Time Slot Allocation

Initially, CH adopts equal time slot scheme to allocate time slot for MNs. In ECOR routing, there arem frames, and there are n time slots in each frame, as shown in Figure 5.Figure 5
Initial time slot allocation.After time slot have been allocated, CH broadcasts time slot allocation table in the cluster. Once received the time slot allocation table, MNs know its allocated time slot and transmit its data during its allocated time slot.If the data is completely transmitted during its allocated time slot, node would send a send-over control message at the completion of transmitting data. The send-over control message indicates the completion of the data transmission. Afterward, the node will go to sleep and turn off the radio. For simplicity, the type of node is called working-node.If the data is not completely transmitted during its allocated time slot, node sends the request-continue control message at the end of the time slot. For simplicity, the node that sends the request-continue control message is called the busying node, as shown in Figure6.Figure 6
Working node and busying node.


#### 4.3.2. Time Slot Adjustment

CH will adjust the duration of time slot according to the type of node in the previous round. Therefore, time slot adjustment factorλ is introduced. Let Ft,j represents the state of node sj in tst frame. If the state of node sj is working node, Ft,j=0. Otherwise, if the state of node sj is busying node,Ft,j=1.Letλt+1,j represents time slot adjustment factor of node sj in t+1st frame, andλt+1,j=1+0.5Ft,j. Assume that there are n nodes in the cluster, CH adjusts duration of time slot in next frame according to equation (7):
(7)Tst+1,j=nλt+1,j∑i=1nλt+1,iTst,j,where Tst,j represents the duration of jst time slot in tst frame.Tst+1,j represents the duration of jsttime slot in t+1st frame.


### 4.4. Intercluster Communication

According to equation (1), the consumed energy of node is proportional to the 2 ~ 4th power of the transmission distance. If d<d0, transmitter transmits data in single hop way. If d>d0, transmitter still adopts the single hop way, and the energy consumed in transmitting data process is 4th power of d.In this case, consumed energy of node can be reduced by transmitting in multihop way. Based on the above analysis, the shortest path based on the improved-Dijkstra algorithm [26] is adopted to construct intercluster communication.In the Dijkstra algorithm, the network topology is represented by weighted graphG=V,E, where V denotes the vertex set that composed of CHs and BS. The E denotes set of weights that is the distance between the vertices.Initially, the BS is considered to be a source node, shortest path vertex setSh_pathid, and all vertex sets Allid are constructed. At first, there is only the BS in Sh_pathid set, namely, Sh_pathid=BS.Allid contains all vertices except the BS and CHs that are able to communicate directly with the source node. If the distance between a CH and BS is less than d0, CH communicates directly with BS in single hop way without multihop communication. Let DC⟶BS represents CH set that distance from BS is less than d0, and its definition is shown in Equation (8).
(8)DC⟶BS=CidCi⟶BS<d0,where Ci represents the ist CH, and i=1,2,⋯,M. dCi⟶BS represents the distance Ci and BS.Initially,Allid=V/BS/DC⟶BS. When Sh_pathid and Allid are initialized, for any a CH Ch∈Allid, the CH Ch with the shortest path from the source node and its residual energy more than average residual energy of all CHs is selected to join in Sh_pathid. Let ECHavg denotes the average residual energy of CHs in Allid:
(9)ECHavg=1Allid∑i=1AllidECires,where ECires denotes the residual energy of Ci. Allid is the number of CHs in Allid.Afterward, the length of path between source node and any CH located inAllid is updated. Repeat the above process until that all vertices in Allid are join in Sh_pathid. Finally, the shortest path from source node from each CH is constructed. The steps are depicted in the flowchart given in Figure 7.Figure 7
Flowchart of constructing the shortest path.The process of constructing the shortest path is illustrated in detail with the help of Figure8. In Figure 8, V=BS,A,B,C,D,E,F,G. Assume that the distance between vertex E,F,Gand BS are less than d0, and DC⟶BSid=E,F,G, so that, at first, Allid=A,B,C,D.Figure 8
Improved Dijkstra algorithm.After, for any a vertex inAllid=A,B,C,D, the vertex with the shortest path from BS is selected to join inSh_pathid. As shown Figure 8, it is the vertex A with the shortest path from BS, and its path is 20. Therefore, vertex A is joined inSh_pathid, namely, Sh_pathid=Sh_pathid∪A.Subsequently, the length of shortest path between source node and any CH located inAllid is updated, as shown in Table 1. At first, the shortest path between BS and vertex B is cannot be confirmed; so, the shortest path is denoted by“∞,” as shown in Table 1. But when vertex A is joined in Sh_pathid, the shortest path between the BS and vertex B can be constructed with the help of vertex A, and the shortest path between the BS and vertex B is updated to 80, as shown in Table 1.Table 1
Shortest path iteration.
IterationSh_path (id)ABCDAt firstBS20∞110301BS,A20100302BS,A,D2080303BS,A,D,B208090304BS,A,D,B,C20809030Repeating the above procedure until that the shortest path from BS to all vertexes is completely constructed, as shown in Table1. As known from Table 1, the shortest path from BS to vertex A is BS⟶A. The shortest path from BS to vertex B is BS⟶A⟶B. The shortest path from BS to vertex C is BS⟶D⟶C. The shortest path from BS to vertex D is BS⟶D.


## 4.1. Hexagonal Grid-Based Cluster

The interesting region is divided into hexagon. There is only a CH in each hexagon to make the distribution of CH more even, as shown Figure3. Centroid is the same distance from any point on the edge of the hexagon. If the node close to the centroid is chosen as the CH, the whole network can be covered with the smallest numbers of CH.Figure 3
Hexagonal grid-based cluster model.We considerℓa×ℓb area of the 2D plane. And the number of centroid is
(3)M=ℓa×ℓbA,where ⋅ represents floor function. A=3/23R2 is the area of a hexagon. R represents the radius of inner tangential circle of the hexagon. xkc is the position vector of centroid the of kst hexagon Ξk, and k=1,2,⋯,M.If all CHs are located at the centroid of hexagons, the network can be covered with the least numbers of CHs, which is also the original intention of adopting hexagonal grid-based cluster scheme. BS loads all position vectors into Hello packet and broadcasts the Hello packet throughout the network.Received from position vectors, each node computes the distance from the centroids of all hexagons. The node is inkst hexagon Ξk, if the distance from xkc is not more than R, k=1,2,⋯,M, so that these nodes know in which hexagon they are.LetNk represents the set of nodes in kst hexagonΞk, k=1,2,⋯,M, and its definition is given by
(4)Nk=sixi−xkc<R,Where xi represents the position vector of si, and i=1,2,⋯,N..


## 4.2. Selection of CHs and Cluster Formation

In the initial phase, the tentative CHs are initially chosen using a back-off timer [24]. Each tentative CH will collect average residual energy of all nodes in its hexagon. The timer value is inversely proportional to the residual energy level of node. For instance, the back-off timer value will be low if the energy level is high, and vice versa.Therefore, back-off timer value will be expired soon for the nodes with higher energy level. Once the back-off timer reaches zero, the respective node declares itself as tentative CH and broadcast tentative CH advertisement message (Ten_CH) within its hexagon. When any of the nodes in hexagon receives Ten_CH before its timer expires, it transmits its residual energy level toward the tentative CH. When tentative CH has received residual energy level of all nodes in its hexagon, it calculates the average residual energy of all nodes in hexagon, which is given by
(5)Ekavg=1Nk∑h=1NkEhres,sh∈Nk,Where Ekavg is the average residual energy of all nodes in hexagon Ξk. Ehres denotes the residual energy of node sh. Nk is the number of elements in the set Ξk.It is worth explaining that the node with the largest remaining energy is chosen as tentative CH because energy is consumed to calculate the average energy consumption and broadcast this information. This helps balance the residual energy levels of nodes in the hexagon.Residual energy of node and distance of node from centroid of the hexagon are used to compute the weight. Then, the node with the largest weight will be selected to be a CH. LetWik denote the weight of node si∈Nithat is located in kst hexagon Ξk, and its definition is given by
(6)Wik=αEiresEint+β1−di,ΞkR,Eires≥Ekavg0,Eires<Ekavg,whereEires denotes the residual energy of node si∈Ni. Eint denotes initial energy of node si∈Ni. According to the abovementioned network model, the initial energy of all nodes is equal. di,Ξk is the distance between the node si and the centroid of the hexagon. Both α and β are the weight coefficients, which control the proportion of residual energy and distance in the weight value.According to equation (6), when the residual energy of a node is lower than the average residual energy of all nodes in the hexagon in which the node located, the weight of the node is zero. The node with largest weight in each hexagon will be selected to be a CH of the hexagon. The entire process is depicted in a flowchart as shown in Figure 4.Figure 4
Flowchart of selecting CH.After the selection of CHs, CHs broadcastInv_CH message to nearby nodes for clustering. Each node chooses the closest CH to join using optimal distance communication. Therefore, MNs send Join_CH message toward the closest CH. Eventually cluster formation is done.


## 4.3. Intracluster Communication

After CH was selected, CH will allocate time slot to its MNs in the way of time division multiple access (TDMA) [25]. MNs would transmit data toward CH during its allocated time slot.


### 4.3.1. Initial Time Slot Allocation

Initially, CH adopts equal time slot scheme to allocate time slot for MNs. In ECOR routing, there arem frames, and there are n time slots in each frame, as shown in Figure 5.Figure 5
Initial time slot allocation.After time slot have been allocated, CH broadcasts time slot allocation table in the cluster. Once received the time slot allocation table, MNs know its allocated time slot and transmit its data during its allocated time slot.If the data is completely transmitted during its allocated time slot, node would send a send-over control message at the completion of transmitting data. The send-over control message indicates the completion of the data transmission. Afterward, the node will go to sleep and turn off the radio. For simplicity, the type of node is called working-node.If the data is not completely transmitted during its allocated time slot, node sends the request-continue control message at the end of the time slot. For simplicity, the node that sends the request-continue control message is called the busying node, as shown in Figure6.Figure 6
Working node and busying node.


### 4.3.2. Time Slot Adjustment

CH will adjust the duration of time slot according to the type of node in the previous round. Therefore, time slot adjustment factorλ is introduced. Let Ft,j represents the state of node sj in tst frame. If the state of node sj is working node, Ft,j=0. Otherwise, if the state of node sj is busying node,Ft,j=1.Letλt+1,j represents time slot adjustment factor of node sj in t+1st frame, andλt+1,j=1+0.5Ft,j. Assume that there are n nodes in the cluster, CH adjusts duration of time slot in next frame according to equation (7):
(7)Tst+1,j=nλt+1,j∑i=1nλt+1,iTst,j,where Tst,j represents the duration of jst time slot in tst frame.Tst+1,j represents the duration of jsttime slot in t+1st frame.


## 4.3.1. Initial Time Slot Allocation

Initially, CH adopts equal time slot scheme to allocate time slot for MNs. In ECOR routing, there arem frames, and there are n time slots in each frame, as shown in Figure 5.Figure 5
Initial time slot allocation.After time slot have been allocated, CH broadcasts time slot allocation table in the cluster. Once received the time slot allocation table, MNs know its allocated time slot and transmit its data during its allocated time slot.If the data is completely transmitted during its allocated time slot, node would send a send-over control message at the completion of transmitting data. The send-over control message indicates the completion of the data transmission. Afterward, the node will go to sleep and turn off the radio. For simplicity, the type of node is called working-node.If the data is not completely transmitted during its allocated time slot, node sends the request-continue control message at the end of the time slot. For simplicity, the node that sends the request-continue control message is called the busying node, as shown in Figure6.Figure 6
Working node and busying node.


## 4.3.2. Time Slot Adjustment

CH will adjust the duration of time slot according to the type of node in the previous round. Therefore, time slot adjustment factorλ is introduced. Let Ft,j represents the state of node sj in tst frame. If the state of node sj is working node, Ft,j=0. Otherwise, if the state of node sj is busying node,Ft,j=1.Letλt+1,j represents time slot adjustment factor of node sj in t+1st frame, andλt+1,j=1+0.5Ft,j. Assume that there are n nodes in the cluster, CH adjusts duration of time slot in next frame according to equation (7):
(7)Tst+1,j=nλt+1,j∑i=1nλt+1,iTst,j,where Tst,j represents the duration of jst time slot in tst frame.Tst+1,j represents the duration of jsttime slot in t+1st frame.


## 4.4. Intercluster Communication

According to equation (1), the consumed energy of node is proportional to the 2 ~ 4th power of the transmission distance. If d<d0, transmitter transmits data in single hop way. If d>d0, transmitter still adopts the single hop way, and the energy consumed in transmitting data process is 4th power of d.In this case, consumed energy of node can be reduced by transmitting in multihop way. Based on the above analysis, the shortest path based on the improved-Dijkstra algorithm [26] is adopted to construct intercluster communication.In the Dijkstra algorithm, the network topology is represented by weighted graphG=V,E, where V denotes the vertex set that composed of CHs and BS. The E denotes set of weights that is the distance between the vertices.Initially, the BS is considered to be a source node, shortest path vertex setSh_pathid, and all vertex sets Allid are constructed. At first, there is only the BS in Sh_pathid set, namely, Sh_pathid=BS.Allid contains all vertices except the BS and CHs that are able to communicate directly with the source node. If the distance between a CH and BS is less than d0, CH communicates directly with BS in single hop way without multihop communication. Let DC⟶BS represents CH set that distance from BS is less than d0, and its definition is shown in Equation (8).
(8)DC⟶BS=CidCi⟶BS<d0,where Ci represents the ist CH, and i=1,2,⋯,M. dCi⟶BS represents the distance Ci and BS.Initially,Allid=V/BS/DC⟶BS. When Sh_pathid and Allid are initialized, for any a CH Ch∈Allid, the CH Ch with the shortest path from the source node and its residual energy more than average residual energy of all CHs is selected to join in Sh_pathid. Let ECHavg denotes the average residual energy of CHs in Allid:
(9)ECHavg=1Allid∑i=1AllidECires,where ECires denotes the residual energy of Ci. Allid is the number of CHs in Allid.Afterward, the length of path between source node and any CH located inAllid is updated. Repeat the above process until that all vertices in Allid are join in Sh_pathid. Finally, the shortest path from source node from each CH is constructed. The steps are depicted in the flowchart given in Figure 7.Figure 7
Flowchart of constructing the shortest path.The process of constructing the shortest path is illustrated in detail with the help of Figure8. In Figure 8, V=BS,A,B,C,D,E,F,G. Assume that the distance between vertex E,F,Gand BS are less than d0, and DC⟶BSid=E,F,G, so that, at first, Allid=A,B,C,D.Figure 8
Improved Dijkstra algorithm.After, for any a vertex inAllid=A,B,C,D, the vertex with the shortest path from BS is selected to join inSh_pathid. As shown Figure 8, it is the vertex A with the shortest path from BS, and its path is 20. Therefore, vertex A is joined inSh_pathid, namely, Sh_pathid=Sh_pathid∪A.Subsequently, the length of shortest path between source node and any CH located inAllid is updated, as shown in Table 1. At first, the shortest path between BS and vertex B is cannot be confirmed; so, the shortest path is denoted by“∞,” as shown in Table 1. But when vertex A is joined in Sh_pathid, the shortest path between the BS and vertex B can be constructed with the help of vertex A, and the shortest path between the BS and vertex B is updated to 80, as shown in Table 1.Table 1
Shortest path iteration.
IterationSh_path (id)ABCDAt firstBS20∞110301BS,A20100302BS,A,D2080303BS,A,D,B208090304BS,A,D,B,C20809030Repeating the above procedure until that the shortest path from BS to all vertexes is completely constructed, as shown in Table1. As known from Table 1, the shortest path from BS to vertex A is BS⟶A. The shortest path from BS to vertex B is BS⟶A⟶B. The shortest path from BS to vertex C is BS⟶D⟶C. The shortest path from BS to vertex D is BS⟶D.


## 5. Performance Analysis

### 5.1. Simulation Parameters

In order to better analyze the performance of the ECOR algorithm, the WSN-based simulation software NS-2.35 [27] is used to analyze the network performance of the ECOR algorithm, I-LEACH, and FCCR algorithm.In simulation, the number of nodes is 100. The specific simulation parameters are shown in Table2. 100 nodes are randomly deployed in 200×200m2 area, as shown in Figure 9. The circle in Figure 9 denotes BS. Other black solid points represent the nodes.Table 2
Simulation parameters.
ParametersValueSimulation area200×200m2Number of nodes100Initial energy of node2 JPosition of BS(100, 100)Transmission range45 mPacket size4000 bitEelec50nJ/bitεfs10pJ/bit/m2εamp0.0013pJ/bit/m4Figure 9
Distribution of 100 nodes in200×200m2.The number of network survival nodes and energy consumption were selected to evaluate the performance of ECOR algorithm. The evaluation criteria of network alive nodes were adopted in the reference [28], namely, first node death (FND) and half of node alive (HNA).


### 5.2. Distribution of CHs

The distribution performance of CHs of the ECOR algorithm, I-LEACH, and FCCR algorithm is analyzed, as shown in Figure10. The hollow triangle denotes CH. Figure 10(a) shows the distribution of CHs of the ECOR algorithm. Figure 10(b) shows the distribution of CHs of the I-LEACH algorithm. Figure 10(c) shows the distribution of CHs of the FCCR algorithm.Figure 10
Performance analysis in terms of distribution of CHs.
(a)(b)(c)As shown in Figure10, compared with the I-LEACH algorithm and FCCR algorithm, the distribution of CHs of the ECOR algorithm is more even. In the ECOR algorithm, CHs are arranged in approximately three rows. Distribution of CHs in both the I-LEACH algorithm and FCCR algorithm is haphazard. It is because that the ECOR algorithm has used hexagon-based grid to generate a CH in each grid, making distribution of CHs more even. However, the I-LEACH algorithm selects CHs based on the energy of node, which do not consider the position of nodes. So, the distribution of CHs is uneven in the I-LEACH algorithm.


### 5.3. Number of Alive Nodes

Firstly, the number of alive nodes in each algorithm is analyzed, as shown in Figure11.Figure 11
Performance analysis in terms of number of alive nodes.From Figure11, it is clear that the performance of number of alive nodes in ECOR is better than I-LEACH and FCCR. The I-LEACH algorithm loses 35% of the nodes at 800 rounds. And the FCCR algorithm loses 35% of the nodes after more rounds approximately at 1200 rounds. The proposed ECOR algorithm has a minimum lose rate.


### 5.4. FND and HNA

Secondly, FND and HNA in each algorithm are analyzed, as shown in Figure12.Figure 12
Performance analysis in terms of FND and HNA.From Figure12, it is clear that the ECOR algorithm has achieved better performance than all other algorithm in terms of FND and HNA. Compared with I-LEACH, FND of the FCCR algorithm is improved by nearly 13%. The reason is that the FCCR algorithm has used fuzzy comprehensive evaluation to select CHs, which makes CHs more evenly distributed and balances energy consumption between nodes.Compared with the I-LEACH algorithm and FCCR algorithm, the FND of the ECOR algorithm is increased by 18% and 4%, respectively. This is mainly due to the following reasons: CH distribution of the ECOR algorithm is reasonable. The time slot of nodes is adjusted within the intracluster communication in order to optimize the time slot allocation. When the nodes that do not need to transmit data go to sleep, the energy consumption is reduced.Figure12 also represents the HNA of the I-LEACH, FCCR, and ECOR algorithm. The HNA of the I-LEACH algorithm is the lowest. The HNA of the ECOR algorithm is the highest. Compared with the I-LEACH and FCCR algorithm, the HNA of the ECOR algorithm is improved by about 32% and 21%, respectively. These results show that the ECOR algorithm effectively reduces energy consumption and improves the energy efficiency by optimizing CH selection.


### 5.5. Average Remaining Energy of Nodes

Figure13 displays the average remaining energy of the I-LEACH, FCCR, and ECOR algorithm. From Figure 13, it is clear that the average remaining energy of ECOR is higher than the I-LEACH algorithm and FCCR algorithm. The reason is that the ECOR algorithm makes CH distribution more even, and the transmission path between CHs is shorten. In consequence, energy consumption is reduced.Figure 13
Performance analysis in terms of average remaining energy.The proposed ECOR routing has capitalized on two complementary techniques for reducing energy consumption. More precisely, in intracluster communication, the duration of time slot is dynamically adjusted according to the state of nodes. In intercluster communication, the Dijkstra algorithm is used to construct the shortest path between CHs.In addition, in order to analyze the contribution of these two complementary technologies to the proposed routing, the performance of two technologies is analyzed separately.Therefore, let us think about two cases in the ECOR algorithm. Case 1:the ECOR algorithm does not adopt the shortest path between CHs, that is, ECOR without the Dijkstra algorithm. Case 2: the ECOR algorithm does not adopt duration of time slot allocation, that is, ECOR without time slot allocation.Energy consumption of ECOR, ECOR without Dijkstra, and ECOR without time slot allocation is shown in Figure14 when they performed 1000 rounds. From Figure 14, we can obviously see that energy consumption of ECOR routing is the lowest in line with expectations. ECOR has used the two complementary technologies to reduce energy consumption of nodes.Figure 14
Consumed Energy of ECOR, ECOR without Dijkstra, and ECOR without time slot allocation.As is clearly shown in Figure14, compared with ECOR without Dijkstra, ECOR without time slot allocation consumes less energy. The result shows that the shortest path strategy constructed by the Dijkstra algorithm is more effective in reducing energy consumption compared with time slot allocation. The main reason is that power dissipation of transmission unit in sensors is much bigger than the sum of other units, to shorten the path of data transmission can greatly reduce energy consumption of nodes.


## 5.1. Simulation Parameters

In order to better analyze the performance of the ECOR algorithm, the WSN-based simulation software NS-2.35 [27] is used to analyze the network performance of the ECOR algorithm, I-LEACH, and FCCR algorithm.In simulation, the number of nodes is 100. The specific simulation parameters are shown in Table2. 100 nodes are randomly deployed in 200×200m2 area, as shown in Figure 9. The circle in Figure 9 denotes BS. Other black solid points represent the nodes.Table 2
Simulation parameters.
ParametersValueSimulation area200×200m2Number of nodes100Initial energy of node2 JPosition of BS(100, 100)Transmission range45 mPacket size4000 bitEelec50nJ/bitεfs10pJ/bit/m2εamp0.0013pJ/bit/m4Figure 9
Distribution of 100 nodes in200×200m2.The number of network survival nodes and energy consumption were selected to evaluate the performance of ECOR algorithm. The evaluation criteria of network alive nodes were adopted in the reference [28], namely, first node death (FND) and half of node alive (HNA).


## 5.2. Distribution of CHs

The distribution performance of CHs of the ECOR algorithm, I-LEACH, and FCCR algorithm is analyzed, as shown in Figure10. The hollow triangle denotes CH. Figure 10(a) shows the distribution of CHs of the ECOR algorithm. Figure 10(b) shows the distribution of CHs of the I-LEACH algorithm. Figure 10(c) shows the distribution of CHs of the FCCR algorithm.Figure 10
Performance analysis in terms of distribution of CHs.
(a)(b)(c)As shown in Figure10, compared with the I-LEACH algorithm and FCCR algorithm, the distribution of CHs of the ECOR algorithm is more even. In the ECOR algorithm, CHs are arranged in approximately three rows. Distribution of CHs in both the I-LEACH algorithm and FCCR algorithm is haphazard. It is because that the ECOR algorithm has used hexagon-based grid to generate a CH in each grid, making distribution of CHs more even. However, the I-LEACH algorithm selects CHs based on the energy of node, which do not consider the position of nodes. So, the distribution of CHs is uneven in the I-LEACH algorithm.


## 5.3. Number of Alive Nodes

Firstly, the number of alive nodes in each algorithm is analyzed, as shown in Figure11.Figure 11
Performance analysis in terms of number of alive nodes.From Figure11, it is clear that the performance of number of alive nodes in ECOR is better than I-LEACH and FCCR. The I-LEACH algorithm loses 35% of the nodes at 800 rounds. And the FCCR algorithm loses 35% of the nodes after more rounds approximately at 1200 rounds. The proposed ECOR algorithm has a minimum lose rate.


## 5.4. FND and HNA

Secondly, FND and HNA in each algorithm are analyzed, as shown in Figure12.Figure 12
Performance analysis in terms of FND and HNA.From Figure12, it is clear that the ECOR algorithm has achieved better performance than all other algorithm in terms of FND and HNA. Compared with I-LEACH, FND of the FCCR algorithm is improved by nearly 13%. The reason is that the FCCR algorithm has used fuzzy comprehensive evaluation to select CHs, which makes CHs more evenly distributed and balances energy consumption between nodes.Compared with the I-LEACH algorithm and FCCR algorithm, the FND of the ECOR algorithm is increased by 18% and 4%, respectively. This is mainly due to the following reasons: CH distribution of the ECOR algorithm is reasonable. The time slot of nodes is adjusted within the intracluster communication in order to optimize the time slot allocation. When the nodes that do not need to transmit data go to sleep, the energy consumption is reduced.Figure12 also represents the HNA of the I-LEACH, FCCR, and ECOR algorithm. The HNA of the I-LEACH algorithm is the lowest. The HNA of the ECOR algorithm is the highest. Compared with the I-LEACH and FCCR algorithm, the HNA of the ECOR algorithm is improved by about 32% and 21%, respectively. These results show that the ECOR algorithm effectively reduces energy consumption and improves the energy efficiency by optimizing CH selection.


## 5.5. Average Remaining Energy of Nodes

Figure13 displays the average remaining energy of the I-LEACH, FCCR, and ECOR algorithm. From Figure 13, it is clear that the average remaining energy of ECOR is higher than the I-LEACH algorithm and FCCR algorithm. The reason is that the ECOR algorithm makes CH distribution more even, and the transmission path between CHs is shorten. In consequence, energy consumption is reduced.Figure 13
Performance analysis in terms of average remaining energy.The proposed ECOR routing has capitalized on two complementary techniques for reducing energy consumption. More precisely, in intracluster communication, the duration of time slot is dynamically adjusted according to the state of nodes. In intercluster communication, the Dijkstra algorithm is used to construct the shortest path between CHs.In addition, in order to analyze the contribution of these two complementary technologies to the proposed routing, the performance of two technologies is analyzed separately.Therefore, let us think about two cases in the ECOR algorithm. Case 1:the ECOR algorithm does not adopt the shortest path between CHs, that is, ECOR without the Dijkstra algorithm. Case 2: the ECOR algorithm does not adopt duration of time slot allocation, that is, ECOR without time slot allocation.Energy consumption of ECOR, ECOR without Dijkstra, and ECOR without time slot allocation is shown in Figure14 when they performed 1000 rounds. From Figure 14, we can obviously see that energy consumption of ECOR routing is the lowest in line with expectations. ECOR has used the two complementary technologies to reduce energy consumption of nodes.Figure 14
Consumed Energy of ECOR, ECOR without Dijkstra, and ECOR without time slot allocation.As is clearly shown in Figure14, compared with ECOR without Dijkstra, ECOR without time slot allocation consumes less energy. The result shows that the shortest path strategy constructed by the Dijkstra algorithm is more effective in reducing energy consumption compared with time slot allocation. The main reason is that power dissipation of transmission unit in sensors is much bigger than the sum of other units, to shorten the path of data transmission can greatly reduce energy consumption of nodes.


## 6. Conclusion

In order to reduce energy consumption and optimize CH selection, the ECOR algorithm was proposed in this paper. In ECOR, CHs are selected by using the centroid of hexagonal network topology. The ECOR algorithm makes the distribution of CHs more even. In intracluster communication, the duration of time slot is dynamically allocated according to the state of node. In intercluster communication, the Dijkstra algorithm is used to construct the shortest path among CHs, in order to shorten the path of transmitting data.Simulation results show that the ECOR algorithm outperforms the I-LEACH algorithm in terms of distribution of CHs and energy consumption. The aim of the ECOR algorithm is to reduce energy consumption of node and make CHs’ distribution even. In the future, other performance of the ECOR algorithm will be analyzed, including transmission data delay and packet transmission success rate.



---

*Source: 5566365-2022-03-10.xml*