# ECMTADR: Energy Conservative Multitier Architecture with Data Reduction for Cluster-Based Wireless Sensor Networks

Authors: Taner Cevik
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Regarding the energy shortage problem of wireless sensor networks (WSNs), various schemes and protocols are proposed to prolong the network lifetime. Data communication is undoubtedly the most important determinant for this energy scarce network type. In this paper, we propose a sophisticated architecture comprising data reduction, load balance, and topology control. Data reduction is ensured by the parameter spatial correlation proximity range (SCPR) that can be adjusted statically at the setup phase or dynamically revised depending on the necessities in the network. Four-layer virtual architecture is applied for implementing topology control. Furthermore, network area is partitioned into fixed-size hexagonal clusters. Depending on the regions in which the clusters take place, cluster heads (CHs) are elected from the respective subregions of the clusters. Load balance is achieved by considering residual energies and distances to the sink during both CH election and data transmission stages. Aggregated data in each cluster is transmitted towards the sink by using a load balancing single-hop intercluster routing protocol instead of direct transmission as offered in LEACH. Simulation results demonstrate that the proposed architecture ECMTADR shows almost 50% better performance in terms of energy conservation and network lifetime when it is compared to LEACH and HEED.


---

## Body

## 1. Introduction

Recent technological developments in areas such as microelectronic, signal processing, and communication protocols have enabled sensor nodes to be produced cheaply with extremely small sizes which led wireless sensor networks to be deployed, self-organized, and activated rapidly with conceivable maintenance costs. This, in turn, provided to WSNs a broad range of application areas including industry, military, agriculture, health care, and sports [1–4]. Fortunately, it has recently become possible to perform dangerous and time-consuming jobs for humankind by computers in a very short time with higher accuracy and lower costs than before [5].The mandate of WSNs consists of three stages: gathering data from the environment, in-processing (optional), and transmitting raw data (results) to the data collection center (sink). Obviously, a sensor node consists of four subunits: sensing subunit, processing subunit, communication subunit, and a power source. Among these subunits, the radio communication subsystem is the primary energy consumer of a sensor node [6]. The amount of energy consumed by the radio communication subunit during transmission of one bit is equal to the amount of energy consumed during transaction of 1000–10000 bits inside the processing subunit [7].In order to achieve low cost operation and minimal maintenance, sensor nodes are produced in very small sizes which begot the fundamental challenge to overcome, that is, energy constraint [8]. The protocols and architectures developed for traditional wireless ad hoc networks cannot be applied to WSNs. Staff employed in traditional wireless networks is not as energy scarce as the ones that operate in WSNs. Therefore, the energy constraint problem is not the primary determinant during protocol and architecture description. Regarding the type of the application, hundreds, even thousands, of sensor nodes are scattered to the environment [9]. In many cases, substituting the energy depleted node for the new one can be dangerous, infeasible, time-consuming, costly, or impossible [10]. Thus, depending on the type of the application, WSNs should maintain durability long enough without any human intervention after the initial deployment stage [11]. General acceptance for network lifetime definition is the time that the first node depletes energy. Thus, WSN-specific software and architecture design is crucial in order to maximize network lifetime [12].Due to the aforementioned reasons, energy efficiency has received a great deal of attention from both academy and industry and since communication is the determinant energy consumer, the vast majority of the efforts have been devoted to improving longevity of sensor networks [13]. In this context, clustering is one of the most promising approaches among the ideas that have been proposed so far. Nodes are virtually organized into groups called clusters centrally or in a distributed manner. Energy consumption increases exponentially in proportion to the increase in the amount of data transmitted on the network. Thus, the point is to reduce the number of messages conveyed, thereby eliminating data redundancy [14]. By assigning some tasks to a group of nodes, not to just a single node, helps the total load to be shared. For event-based applications, an event can be recognized and the same information may be obtained by multiple nodes. Instead of all nodes in the sensing range sending their obtained data, it is sufficient for just a single node or groups of nodes to relay data towards the sink. In each cluster, a single node is elected as a cluster head (CH). CHs take the responsibility for gathering data from other plain staff and relaying the aggregated data to the sink. Aggregated data can be filtered, processed, or directly transmitted in the raw state to the sink that is application-specific and can be left to the discretion of the software embedded in the CH.In this paper, we present a sophisticated cluster-based architecture regarding energy efficiency at each stage of lifetime such as CH election and intercluster routing. Nodes are organized into hexagonal fixed-size clusters statically. Each cluster is also partitioned into six equal-sized cells. Furthermore, a higher layer virtual segmentation of the topology is performed for preventing redundant retransmissions. Depending on the region in which a cluster falls, CHs are elected among the nodes falling into the cells facing the sink. CH selection is performed at the beginning of each round depending on both residual energy levels and the distances of the nodes to the sink. At the beginning of each round, nodes gather data from the environment. However, not all of them send their data to their respective CHs. A parameter called SCPR is considered. Each node starts a timer at the beginning of each data collection period. The timer of the node with a larger residual energy level expires earlier. And other nodes located in the SCPR of that node refrain from sending their data to the CH. By this means, redundant energy consumption and bandwidth invasion are prevented. During the interrouting process again energy levels of the next-hop candidates are considered.The rest of the paper is organized as follows. Section2 reviews existing protocols related to clustering in WSNs. Sections 3-4 provide an overview of the system model and the proposed scheme ECMTADR, respectively. Section 5 presents the simulation-based evaluation of the proposed architecture. Finally, Section 6 concludes the paper and provides an outline of future directions.


## 2. Motivation

Depending on the application type, hundreds and even thousands of nodes are utilized in a WSN. Particularly, for application areas where periodical data acquisition is required, an excessive amount of data transmission occurs in the network. As mentioned in the previous section, to operate at low costs for a satisfactory lifetime, sensor nodes of very small sizes are produced. An ultimate outcome is that a limited amount of resources such as antenna and power supply can be embedded in this restricted node body. The primary vital reflection of this resource constraint is the limited communication capacity.Though WSNs are a type of ad hoc network, conventional methods, protocols, and architectures utilized for classical wireless networks cannot be employed in WSNs. WSNs are generally utilized for gathering scalar data from the environment. The size of the acquired data mostly does not exceed 50 bytes, whereas traditional ad hoc networks cover much larger data packets in greater amounts. Furthermore, sensor nodes are equipped with radios that can transfer messages at most 250 kbps. More competent radios entail additional energy expenditure. Thus, in order not to violate energy conservation, low capacity devices are preferred, which, in turn, causes low bandwidth. Therefore, in order to accomplish the assigned task at reasonable costs for satisfactory periods with sufficient rates, degradation in the quantity of transmitted data is essential.In this context, a number of solutions are proposed thus far. The most two promising ones among these suggestions are data aggregation and reduction. Data reduction is performed locally which is called in-node processing. On the other hand, depending on the application type, data reduction may not always be possible. Another promising alternative solution is configuring the network hierarchically rather than utilizing a flat network topology. Clustering has been trailed by a broad range of research activities in order to achieve energy efficiency and network scalability. Sensor nodes are organized into groups called clusters. Ordinarily, one of the nodes in the cluster is elected as CH. Other nodes are called plain nodes. Plain nodes gather data from the environment and transmit it to their corresponding CH. After receiving data from plain nodes, CH endeavors to relay the aggregated data to the data collection center that is called a sink. Hence, just a single node in each cluster is responsible for the transfer of data to the sink which yields efficient common resource sharing that is wireless medium.Several research activities have focused on cluster-based WSNs. Three remarkable issues about cluster-based WSNs are as follows.(i)
Clustering algorithm, which defines the methodology of dividing the network into clusters virtually. Clustering may be done statically at the beginning during setup phase and dynamically at regular intervals or when a certain condition occurs.(ii)
Cluster head election algorithm, which identifies the method of electing the optimum CH candidate. For the purpose of sharing the burden of holding the responsibility of supervising a cluster of nodes, CH election should be made periodically or with regard to occurrence of a condition.(iii)
Clustering routing algorithm, which describes the way of conveying aggregated messages to the sink. Two challenges to be overcome are intracluster routing and intercluster routing which define the methodology of conveying data from plain nodes to CHs and from CHs to the sink, respectively.The most prominent of the relevant studies are briefly discussed in [15–21].


## 3. System Model

### 3.1. Network Model

There aren nodes (set of nodes →|V|=n) deployed over a square shaped region randomly. A single sink with unconstrained energy supply is positioned at the center of the topology. Network can be represented by a graph model G=(V,E). E denotes the set of links connecting the nodes in the network. Link between two nodes u and v (u,v∈V) is represented by (e→(u,v), {e∈E∣d(u,v)<=r}). d(u,v) which is also equal to the length (u,v) of the link (u,v) denotes the Euclidean distance between the nodes u and v. r represents the coverage radius of the radio which is the maximum distance that a bit of data can be transmitted with a reasonable SINR value. Links are bidirectional and half-duplex. That is, each link between two nodes represents a single communication channel on which one-way transmission can occur at a time as shown in Figure 1.Figure 1
Symmetric half-duplex link.Propagation delay and other parameters such as SINR and loss rate for links (channels)e(u,v)=e(v,u) are assumed to be the same for both directions which, in turn, results in(1)t2-t1=t3-t2Esndu,v=Esndv,u.Each node owns a unique id number assigned in a distributed manner at the setup phase. Uniqueness is achieved by constituting the id number by the relative(x,y) coordinates of the node in the topology. Each node is assumed to know its relative position. That can be achieved by equipping each node with a low power GPS device or by means of applying special signal processing techniques [22].


### 3.2. Radio Model

In this work, we use the first-order radio model as utilized by many works proposed in the literature [23, 24]. The amount of energy consumed during send and receive operations is given below:(2)Esndl,d=Esnd-elecl+Esnd-ampl,d,where Esnd-elec and Esnd-amp represent the energies dissipated during running the transmitter circuit and amplification for achieving a reasonable SINR value, respectively:(3)Esnd(l,d)=(l∗Eelec)+(l∗εfs∗d2)d<d0(l∗Eelec)+(l∗εmp∗d4)d≥d0(4)Ercv=l∗Eelec(5)d0=εfsεmp.Equations (3)-(4) identify the energy dissipated by the nodes during transmit and receive operations. In the equations, l denotes the number of bits to be transmitted and d represents the Euclidean distance between the communicating pairs. As is known, if the distance between two nodes is below the threshold distance (5) which is denoted by d0, the energy consumed by the sender node is calculated according to the first part of (3). Otherwise, the energy consumed by the sender node is calculated according to the second part. It is obvious that if the distance between the communicating pairs increases, the amount of energy consumed rises exponentially.


## 3.1. Network Model

There aren nodes (set of nodes →|V|=n) deployed over a square shaped region randomly. A single sink with unconstrained energy supply is positioned at the center of the topology. Network can be represented by a graph model G=(V,E). E denotes the set of links connecting the nodes in the network. Link between two nodes u and v (u,v∈V) is represented by (e→(u,v), {e∈E∣d(u,v)<=r}). d(u,v) which is also equal to the length (u,v) of the link (u,v) denotes the Euclidean distance between the nodes u and v. r represents the coverage radius of the radio which is the maximum distance that a bit of data can be transmitted with a reasonable SINR value. Links are bidirectional and half-duplex. That is, each link between two nodes represents a single communication channel on which one-way transmission can occur at a time as shown in Figure 1.Figure 1
Symmetric half-duplex link.Propagation delay and other parameters such as SINR and loss rate for links (channels)e(u,v)=e(v,u) are assumed to be the same for both directions which, in turn, results in(1)t2-t1=t3-t2Esndu,v=Esndv,u.Each node owns a unique id number assigned in a distributed manner at the setup phase. Uniqueness is achieved by constituting the id number by the relative(x,y) coordinates of the node in the topology. Each node is assumed to know its relative position. That can be achieved by equipping each node with a low power GPS device or by means of applying special signal processing techniques [22].


## 3.2. Radio Model

In this work, we use the first-order radio model as utilized by many works proposed in the literature [23, 24]. The amount of energy consumed during send and receive operations is given below:(2)Esndl,d=Esnd-elecl+Esnd-ampl,d,where Esnd-elec and Esnd-amp represent the energies dissipated during running the transmitter circuit and amplification for achieving a reasonable SINR value, respectively:(3)Esnd(l,d)=(l∗Eelec)+(l∗εfs∗d2)d<d0(l∗Eelec)+(l∗εmp∗d4)d≥d0(4)Ercv=l∗Eelec(5)d0=εfsεmp.Equations (3)-(4) identify the energy dissipated by the nodes during transmit and receive operations. In the equations, l denotes the number of bits to be transmitted and d represents the Euclidean distance between the communicating pairs. As is known, if the distance between two nodes is below the threshold distance (5) which is denoted by d0, the energy consumed by the sender node is calculated according to the first part of (3). Otherwise, the energy consumed by the sender node is calculated according to the second part. It is obvious that if the distance between the communicating pairs increases, the amount of energy consumed rises exponentially.


## 4. ECMTADR

In this section we briefly clarify the details of our proposed architecture ECMTADR. The first section describes the clustering method employed. Subsequent sections introduce the methodologies suggested for neighborhood definition, data reduction, CH election, intracluster communication, and intercluster communication processes, respectively.


### 4.1. Clustering

The network area is configured into a four-level hierarchy. In the first step, topology is zoned into 8 regions as depicted in Figure2. During CH election stage, nodes will only be selected among the nodes appearing in the corresponding sectors depending on the zone that the cluster locates.Figure 2
Network area zoning.Subsequently, topology is sliced into tiers from the inside out. Afterwards, each tier is again virtually partitioned into fixed-size hexagonal cells as done in recent cellular communication. The number of clusters that appear at each tier is given in the following:(6)numOfClstierNo=tierNo∗6∣0≤tierNo≤NumOfTiers.In (6), tierNo and NumOfTiers denote the corresponding tier number and the total number of tiers present in the network, respectively.Any two nodes deployed in a cluster should be able to communicate directly with each other. Thus, the distance between the two most distant points of the cell which represents the diameter (2r) of the hexagon is adjusted so as to be equal to the coverage radius of the radio (rcov) as clarified as follows (Figure 3):(7)rcov=2r.Figure 3
Cluster diameter and radio coverage.The final stage of the configuration is parceling out each cell into six equal sectors. As was mentioned above, CH election in each cluster is performed according to at which region the cluster takes place. In order to prevent redundant retransmission back towards the sink, nodes deployed at shaded sectors can be CH candidates. As an example, considering region 1, if a node locating in one of the sectors(4,5,6) is elected as the CH, after the data aggregation process, data has to be transmitted in the opposite direction backward to the sink which ultimately results in a redundant energy dissipation. Therefore, in region 1, a node among the nodes that belong to one of the sectors (1,2,3) is selected as the CH.All the above-mentioned hierarchical configurations of the network area and the CH candidate pattern for each zone are illustrated in Figure4.Figure 4
Hierarchical configuration of the network area.The sink is positioned at the center of the topology with the coordinates (x=0,y=0). Cluster central point calculation and assignment of the nodes to the corresponding clusters are performed as follows.(i)
(x,y) coordinates of the cluster CLS0 are defined for each tier as follows:(8)x0=0,y0=TierNo∗2∗r.(ii)
Rotate the center point of the previous cluster through angleα clockwise (Figure 5). The value of angle α is calculated according to(9)α=2π(TierNo∗6).Rotation of a point through angle α about the origin is performed according to(10)xi=xi-1∗cos⁡⁡α-(yi-1∗sin⁡α)yi=xi-1∗sin⁡α+yi-1∗cos⁡⁡α.Algorithmic representation of the cluster center definition procedure is presented in Algorithm 1.Algorithm 1:Clusters’ central point calculation.
ClusterCenterCalculation(){
for (i←1  to NumOfTiers) do
Tiersi.Cls0.x=0
Tiersj.Cls0.y=(i∗2∗r)
for (j←1  to (i∗6)) do
Tiersi.Clsj.x=(Tiersi.Clsj-1.x∗cos⁡α)-(Tiersi.Clsj-1.y∗sin⁡⁡α)
Tiersi.Clsj.y=(Tiersi.Clsj-1.x∗sin⁡⁡α)+(Tiersi.Clsj-1.y∗cos⁡α)
end for
end for
}Figure 5
Central point rotation pattern for each tier.Assignment of the nodes to the clusters is done at the setup phase in a distributed manner. The sink is responsible for virtual parcellation of the network area into clusters. The relative geographical coordinates of the center point of each cluster are calculated by the sink and then broadcast to the network over the common communication channel. This broadcast message includes the id,(x,y) coordinates of the central point, and the channel that will be used in the cluster (Figure 6). Since the nodes are assumed to know their relative geographical coordinates, each of them selects the cluster with the closest central point.Figure 6
Structure of the broadcast message announcing the coordinates and the assigned channel number of each cluster.


### 4.2. Neighborhood Definition

Following the process of identifying the corresponding cluster, each node should inform other nodes that belong to the same cluster about its existence and relation to the cluster that it selects. Since multiple nodes will try to attain to the common transmission medium at the same time, in order to prevent multiaccess collision, each node starts a timer. Only after the expiration of its timer, a node can make an attempt to transmit its announcement message. Each node defines a timer value different from that of the other nodes. Since two nodes possess different(x,y) coordinates, it is not possible for two timers to expire at the same time. By the time a node hears the announcement of another node, it records the values included in the message to its neighborhood table which is consulted during intercluster routing stage.


### 4.3. Data Gathering and Reduction

The major concern during communication protocol and architecture definition for WSNs is energy efficiency. One promising solution is the reduction of data that is transmitted in the system. Depending on the type and the aim of the application, not all of the nodes deployed in a particular proximity have to gather data and convey it to the CH. Among the nodes in a particular area, the one with the highest residual energy level gathers data and first transmits it to the corresponding CH. Other nodes overhearing this message that appears in the proximity range abort their transmission attempt. This determinant is called the spatial correlation proximity range (SCPR) and will be denoted byrSCPR.In the scenario depicted in Figure7, the only data transmitter is N1, where(i)
d12, d13, and d14 denote the distances between the nodes;(ii)
rSCPR≥d12,d13,d14;(iii)
ResEngN1>ResEngN2,ResEngN3,ResEngN4.Figure 7
Sample scenario.


### 4.4. CH Election

With the aim of providing fair load balance in the clusters, the cluster leadership task should be assigned dynamically to different nodes. During this dynamic assignment process, different parameters can be considered, such as proximity to the sink or residual energy level. In this study, we suggest a cost factor (costCH) which is calculated for each node in every cluster at the beginning of each cycle. Each node calculates its own costCH and lack of the knowledge about the other nodes’ cost values. In many research studies, nodes inform each other about the values of such parameters. However, that will cause collision and transmission errors, which, in turn, results in redundant energy consumption. Therefore, without any necessity of any communication, each node starts a timer internally. The value of each node’s timer depends on the cost factor calculated by the node. Since each node runs the same algorithm, they will get the results in the same direction proportional with their cost factors. The timer of the node with the largest cost factor expires earliest and accesses to the common communication medium first. In this way, it makes its announcement of being the CH of the corresponding cluster at the present cycle. Other nodes of the cluster receive the message and stop the operation of CH calculation and assign the announcing node as their CH. The cost factor and timer value calculations are performed as follows:(11)intraCost=∑n=1InClsNumOfNodesdnode(n)costCH=ResEng∗dsink-1∗intraCost-1timer=costCH-β,where(i)
ResEng anddsink denote the residual energy level and distance of the node to the sink, respectively.(ii)
intraCost is the cost belonging to a node and calculated by adding the distances between the node and the remaining nodes in the cluster.(iii)
InClsNumOfNodes represents the number of nodes in the corresponding cluster.(iv)
dnode is the distance between the concerned node and the node in the same cluster.(v)
β stands for the parameter used during simulations in order to scale the cost value into the time domain.Equation (11) clearly identify that a node with a higher residual energy level and closer to the sink, at the same time with a closer proximity to other nodes in the cluster, has a higher probability for being the CH. Flow chart of the proposed CH election method is depicted in Figure 8.Figure 8
Flowchart of the CH election process.


### 4.5. Intracluster Communication

In order to prevent collision during intracluster transmission, nodes apply an 802.11-type CSMA mechanism. Since every node can receive the transmission of any other node in the cluster, when a node overhears the transmission of another node directed toward the CH, it refrains from accessing to the common transmission medium.


### 4.6. Intercluster Communication

CHs aggregate the data arriving from the plain nodes and transmit it towards the sink. If the sink is in the coverage, aggregated data is transmitted directly to the sink. Otherwise, an intermediate relay node belonging to one of the clusters on the way is selected as the next hop. During next-hop selection, firstly the residual energy levels of the candidate nodes are considered. The node with the highest energy level is selected as the relay node. In the situation of equality, the proximity to the sink is taken into account. Among the nodes with equal residual energies, the one closer to the sink is selected as the relay node.


### 4.7. Energy Consumption Model

As mentioned in the previous sections, the primary energy exhausting unit of a sensor node is the communication subunit. Thus, the energy dissipated by the other staff is ignored. Nodes are classified as CH or plain. The amount of energy consumed by the communication subunit changes depending on the situation whether it becomes the CH or not in each cycle:(12)En=ECH∗ρCH+EP∗1-ρCH,where En is the total amount of energy consumed for the node n in a single cycle. The energy dissipated by a node when it is elected as the CH is denoted by ECH. ρCH represents the probability for a node to be elected as the CH in its cluster. If a node is not elected as the CH, then it serves as a plain node. EP denotes the energy consumed if the node n is a plain node: (13)ECH=Ercv-intra+EInter-Snd+EInter-Rrelay.The amount of energy consumed by a CH is denoted byECH in (13). When a node is elected as the CH, it aggregates the data sent by the plain nodes in its cluster. Energy dissipated by a CH during this aggregation process is shown with Ercv-intra and clarified in (14). EInter-Snd is the energy consumed during internally transmitting the aggregated data towards the sink and identified in (15). Lastly, a node can be selected as a relay node for sending the aggregated data incoming from a cluster positioning at an outer tier. The amount of energy consumed as a relay node is denoted by EInter-Rrelay and expressed in (16)–(18):(14)Ercv-intra=∑n=1InClsNumOfNodesl∗Eelec(15)EInter-Snd=l∗InClsNumOfNodesEelec+εfs∗d2(16)EInter-Relay=EInter-Relay_Rcv+EInter-Relay_Snd(17)EInter-Rcv=ρrelay∗(lInterRelay∗Eelec)(18)EInter-Snd=ρrelay∗lInterRelay∗Eelec+εfs∗d2.The energy consumed by a node when it becomes a plain node is denoted byEP calculated according to the model given in (3). This time, d, represents the distance between the plain node and the sender CH.


## 4.1. Clustering

The network area is configured into a four-level hierarchy. In the first step, topology is zoned into 8 regions as depicted in Figure2. During CH election stage, nodes will only be selected among the nodes appearing in the corresponding sectors depending on the zone that the cluster locates.Figure 2
Network area zoning.Subsequently, topology is sliced into tiers from the inside out. Afterwards, each tier is again virtually partitioned into fixed-size hexagonal cells as done in recent cellular communication. The number of clusters that appear at each tier is given in the following:(6)numOfClstierNo=tierNo∗6∣0≤tierNo≤NumOfTiers.In (6), tierNo and NumOfTiers denote the corresponding tier number and the total number of tiers present in the network, respectively.Any two nodes deployed in a cluster should be able to communicate directly with each other. Thus, the distance between the two most distant points of the cell which represents the diameter (2r) of the hexagon is adjusted so as to be equal to the coverage radius of the radio (rcov) as clarified as follows (Figure 3):(7)rcov=2r.Figure 3
Cluster diameter and radio coverage.The final stage of the configuration is parceling out each cell into six equal sectors. As was mentioned above, CH election in each cluster is performed according to at which region the cluster takes place. In order to prevent redundant retransmission back towards the sink, nodes deployed at shaded sectors can be CH candidates. As an example, considering region 1, if a node locating in one of the sectors(4,5,6) is elected as the CH, after the data aggregation process, data has to be transmitted in the opposite direction backward to the sink which ultimately results in a redundant energy dissipation. Therefore, in region 1, a node among the nodes that belong to one of the sectors (1,2,3) is selected as the CH.All the above-mentioned hierarchical configurations of the network area and the CH candidate pattern for each zone are illustrated in Figure4.Figure 4
Hierarchical configuration of the network area.The sink is positioned at the center of the topology with the coordinates (x=0,y=0). Cluster central point calculation and assignment of the nodes to the corresponding clusters are performed as follows.(i)
(x,y) coordinates of the cluster CLS0 are defined for each tier as follows:(8)x0=0,y0=TierNo∗2∗r.(ii)
Rotate the center point of the previous cluster through angleα clockwise (Figure 5). The value of angle α is calculated according to(9)α=2π(TierNo∗6).Rotation of a point through angle α about the origin is performed according to(10)xi=xi-1∗cos⁡⁡α-(yi-1∗sin⁡α)yi=xi-1∗sin⁡α+yi-1∗cos⁡⁡α.Algorithmic representation of the cluster center definition procedure is presented in Algorithm 1.Algorithm 1:Clusters’ central point calculation.
ClusterCenterCalculation(){
for (i←1  to NumOfTiers) do
Tiersi.Cls0.x=0
Tiersj.Cls0.y=(i∗2∗r)
for (j←1  to (i∗6)) do
Tiersi.Clsj.x=(Tiersi.Clsj-1.x∗cos⁡α)-(Tiersi.Clsj-1.y∗sin⁡⁡α)
Tiersi.Clsj.y=(Tiersi.Clsj-1.x∗sin⁡⁡α)+(Tiersi.Clsj-1.y∗cos⁡α)
end for
end for
}Figure 5
Central point rotation pattern for each tier.Assignment of the nodes to the clusters is done at the setup phase in a distributed manner. The sink is responsible for virtual parcellation of the network area into clusters. The relative geographical coordinates of the center point of each cluster are calculated by the sink and then broadcast to the network over the common communication channel. This broadcast message includes the id,(x,y) coordinates of the central point, and the channel that will be used in the cluster (Figure 6). Since the nodes are assumed to know their relative geographical coordinates, each of them selects the cluster with the closest central point.Figure 6
Structure of the broadcast message announcing the coordinates and the assigned channel number of each cluster.


## 4.2. Neighborhood Definition

Following the process of identifying the corresponding cluster, each node should inform other nodes that belong to the same cluster about its existence and relation to the cluster that it selects. Since multiple nodes will try to attain to the common transmission medium at the same time, in order to prevent multiaccess collision, each node starts a timer. Only after the expiration of its timer, a node can make an attempt to transmit its announcement message. Each node defines a timer value different from that of the other nodes. Since two nodes possess different(x,y) coordinates, it is not possible for two timers to expire at the same time. By the time a node hears the announcement of another node, it records the values included in the message to its neighborhood table which is consulted during intercluster routing stage.


## 4.3. Data Gathering and Reduction

The major concern during communication protocol and architecture definition for WSNs is energy efficiency. One promising solution is the reduction of data that is transmitted in the system. Depending on the type and the aim of the application, not all of the nodes deployed in a particular proximity have to gather data and convey it to the CH. Among the nodes in a particular area, the one with the highest residual energy level gathers data and first transmits it to the corresponding CH. Other nodes overhearing this message that appears in the proximity range abort their transmission attempt. This determinant is called the spatial correlation proximity range (SCPR) and will be denoted byrSCPR.In the scenario depicted in Figure7, the only data transmitter is N1, where(i)
d12, d13, and d14 denote the distances between the nodes;(ii)
rSCPR≥d12,d13,d14;(iii)
ResEngN1>ResEngN2,ResEngN3,ResEngN4.Figure 7
Sample scenario.


## 4.4. CH Election

With the aim of providing fair load balance in the clusters, the cluster leadership task should be assigned dynamically to different nodes. During this dynamic assignment process, different parameters can be considered, such as proximity to the sink or residual energy level. In this study, we suggest a cost factor (costCH) which is calculated for each node in every cluster at the beginning of each cycle. Each node calculates its own costCH and lack of the knowledge about the other nodes’ cost values. In many research studies, nodes inform each other about the values of such parameters. However, that will cause collision and transmission errors, which, in turn, results in redundant energy consumption. Therefore, without any necessity of any communication, each node starts a timer internally. The value of each node’s timer depends on the cost factor calculated by the node. Since each node runs the same algorithm, they will get the results in the same direction proportional with their cost factors. The timer of the node with the largest cost factor expires earliest and accesses to the common communication medium first. In this way, it makes its announcement of being the CH of the corresponding cluster at the present cycle. Other nodes of the cluster receive the message and stop the operation of CH calculation and assign the announcing node as their CH. The cost factor and timer value calculations are performed as follows:(11)intraCost=∑n=1InClsNumOfNodesdnode(n)costCH=ResEng∗dsink-1∗intraCost-1timer=costCH-β,where(i)
ResEng anddsink denote the residual energy level and distance of the node to the sink, respectively.(ii)
intraCost is the cost belonging to a node and calculated by adding the distances between the node and the remaining nodes in the cluster.(iii)
InClsNumOfNodes represents the number of nodes in the corresponding cluster.(iv)
dnode is the distance between the concerned node and the node in the same cluster.(v)
β stands for the parameter used during simulations in order to scale the cost value into the time domain.Equation (11) clearly identify that a node with a higher residual energy level and closer to the sink, at the same time with a closer proximity to other nodes in the cluster, has a higher probability for being the CH. Flow chart of the proposed CH election method is depicted in Figure 8.Figure 8
Flowchart of the CH election process.


## 4.5. Intracluster Communication

In order to prevent collision during intracluster transmission, nodes apply an 802.11-type CSMA mechanism. Since every node can receive the transmission of any other node in the cluster, when a node overhears the transmission of another node directed toward the CH, it refrains from accessing to the common transmission medium.


## 4.6. Intercluster Communication

CHs aggregate the data arriving from the plain nodes and transmit it towards the sink. If the sink is in the coverage, aggregated data is transmitted directly to the sink. Otherwise, an intermediate relay node belonging to one of the clusters on the way is selected as the next hop. During next-hop selection, firstly the residual energy levels of the candidate nodes are considered. The node with the highest energy level is selected as the relay node. In the situation of equality, the proximity to the sink is taken into account. Among the nodes with equal residual energies, the one closer to the sink is selected as the relay node.


## 4.7. Energy Consumption Model

As mentioned in the previous sections, the primary energy exhausting unit of a sensor node is the communication subunit. Thus, the energy dissipated by the other staff is ignored. Nodes are classified as CH or plain. The amount of energy consumed by the communication subunit changes depending on the situation whether it becomes the CH or not in each cycle:(12)En=ECH∗ρCH+EP∗1-ρCH,where En is the total amount of energy consumed for the node n in a single cycle. The energy dissipated by a node when it is elected as the CH is denoted by ECH. ρCH represents the probability for a node to be elected as the CH in its cluster. If a node is not elected as the CH, then it serves as a plain node. EP denotes the energy consumed if the node n is a plain node: (13)ECH=Ercv-intra+EInter-Snd+EInter-Rrelay.The amount of energy consumed by a CH is denoted byECH in (13). When a node is elected as the CH, it aggregates the data sent by the plain nodes in its cluster. Energy dissipated by a CH during this aggregation process is shown with Ercv-intra and clarified in (14). EInter-Snd is the energy consumed during internally transmitting the aggregated data towards the sink and identified in (15). Lastly, a node can be selected as a relay node for sending the aggregated data incoming from a cluster positioning at an outer tier. The amount of energy consumed as a relay node is denoted by EInter-Rrelay and expressed in (16)–(18):(14)Ercv-intra=∑n=1InClsNumOfNodesl∗Eelec(15)EInter-Snd=l∗InClsNumOfNodesEelec+εfs∗d2(16)EInter-Relay=EInter-Relay_Rcv+EInter-Relay_Snd(17)EInter-Rcv=ρrelay∗(lInterRelay∗Eelec)(18)EInter-Snd=ρrelay∗lInterRelay∗Eelec+εfs∗d2.The energy consumed by a node when it becomes a plain node is denoted byEP calculated according to the model given in (3). This time, d, represents the distance between the plain node and the sender CH.


## 5. Performance Evaluation

In this section, we evaluate the key performance metrics of the ECMTADR protocol via extensive simulations. The proposed approach is compared with LEACH [25, 26] and HEED [27]. Performance assessment is made in terms of energy consumption, delay, and lifetime.The metrics that are evaluated during simulations are given in the following.(i)
End-to-end delay is the time elapsed between the time that the first cycle starts and the time that the last cycle ends.(ii)
TotalEnergyis the total energy consumed in the network by all sensor nodes.(iii)
Lifetime is the time when the first node depletes energy.(iv)
MaxEnergyConsumed is the amount of energy dissipated by the node which is the one that has the lowest residual energy level.The major factors that affect these metrics are the number of tiers, the number of nodes, the cell radius, and SCPR. As a result of detailed simulations, the way these factors affect the metrics described above is obtained.Simulations are performed for 100 rounds on a 500 m∗ 500 m square network area. Events occur randomly in the network without depending on any constraint. A sink equipped with a single half-duplex transceiver is positioned at the center. It is assumed that there are n nonoverlapping channels comprising a common data channel and (n-1) data channels. Each sensor node is equipped with a single half-duplex radio with transmission rate of 250 Kbps.Following the values defined in the literature for the parameters expressed in Section3, the values given in Table 1 are considered during energy consumption calculations. All sensors are considered to be identical with an initial residual energy of 3 J. The transmission range of each sensor node is set to 100 meters. The energy spent in transmitting a bit over a 1 meter distance is taken as 10 pJ/bit/m2 and the energy spent in receiving a bit is set to 50 nJ/bit.Table 1
Simulation parameters.
Radio transmission data rate
250 Kbps
d
0 (threshold distance)
85 m
R
0 (coverage radius)
100 m
E
elec
50 nJ/bit
ε
fs
10 pJ/bit/m2
E
mp
0.0013 pJ/bit/m4
E
Residual-Initial
3 J


### 5.1. Node Density

In this study, end-to-end delay refers to the time that elapses between the time that the simulation first starts and the time when the last cycle ends. There are two alternatives for the definition of the term duration here. 100-round simulation is performed for each parameter-metric pair evaluation. The first definition for the term duration is that if a node exhausts energy before the completion of the 100th cycle, duration becomes the lifetime of the network. Otherwise, if none of the sensor nodes depletes energy until the end of the last cycle, duration is the time at which the last cycle ends.Node density is a crucial determinant for energy consumption. Thus, in this study, the impact of node density on different performance metrics of the network is analyzed briefly. In this study, the major concern is to prolong the network lifetime to the utmost; therefore, the delay is disregarded. As obviously depicted in Figure9, all of the three methods perform nearly identically in terms of end-to-end delay. A sharper increase in delay occurs up to a threshold density. However, when the density reaches the specified level, a smoother incline is at stake.Figure 9
Effect of the number of tiers on end-to-end delay.Figure10 represents the change in energy consumption regarding the variation in node density. Increase in node density accordingly leads to an increase in the amount of data carried in the network, which, in turn, induces energy dissipation at the same time. Figure 10 clarifies that LEACH and HEED outperform ECMTADR in terms of the total amount of energy consumed in the network. However, the decisive factor while developing an architecture or protocol for WSNs is the lifetime of a single node which actually stands for the lifetime of the network. One way of extending the network lifetime is achieving load balance among the staff as much as possible. In this study, a maximum number of nodes collaborate possibly during data transmission towards the sink. Therefore, though it may seem that much more energy is dissipated totally, the individual performance lies exactly in the opposite sense which is clearly identified in Figure 11. The reason of the deviations encountered is the random deployment of the nodes at the beginning of each simulation. That is, the topology of a 500-node network and one with a 600 node is not identical.Figure 10
Total energy consumed in the network.Figure 11
Impact of the node density on the network lifetime.MTE above refers to the “minimum transmission energy” routing method. ECMTADR shows nearly 50% better performance in terms of network lifetime. Figure11 proves that, by increasing the number of the staff in the network, a better load distribution is achieved. Fair load distribution inherently prolongs the network lifetime. Although the increase in the population seems to induce a rise in energy consumption cumulatively, in the individual sense that will eventuate with network lifetime prolongation.


### 5.2. Cluster Size and Radio Coverage

Cluster size has also crucial impact in terms of delay and energy efficiency. During the design stage, it is intended for all nodes in a cluster to communicate directly with each other. Therefore, each cell diameter is set to be equal to the radio coverage. As the coverage radius increases clusters also expands. Thus, the number of nodes per cluster density increases. In this way, especially during intercluster communication, if an intermediate relay node covers the distance, it will prefer to relay the data directly to the sink which ultimately reduces delay. The impact of cluster size on delay is depicted in Figure12.Figure 12
Impact of the cluster size on the network lifetime.As mentioned before, our methodology does not have any claim on the improvement of the delay. Therefore, as can be seen from the graph, all three methods perform nearly the same.In terms of total energy consumption in the network, LEACH and HEED are seen to outperform ECMTADR as depicted in Figure13. However, as expressed previously, the point is reducing the individual energy consumption which ultimately delays node failure. As obviously identified in Figure 14, the amount of the energy consumed by a node in ECMTADR is lower when compared with LEACH and HEED. Up to a threshold value for the cluster size and radio coverage, individual energy consumption value stays constant. However, after the threshold value, a trend in the vertical direction is observed. That is because the distance between the plain nodes and their CHs and also between the CHs and intermediate relay nodes increase.Figure 13
Total energy consumed in the network.Figure 14
Maximum energy dissipated individually.


### 5.3. SCPR

The major energy consuming component of a sensor node is the communication subunit. Therefore, most of the effort focuses on the challenge of reducing communication energy expenditure. Some of the studies have focused on developing energy-efficient protocols and architectures. Besides, some of them aimed to reduce the amount of data transmitted in the network. One way of achieving data reduction is reducing the amount of emerged data in each cluster. That refers to assigning the task of data gathering to certain nodes, not all of them. In this study, a parameter with the name spatial correlation proximity range (SCPR) is suggested in order to reduce the amount of data created. Nodes with higher energies are charged with data gathering. When a node is assigned the task of data gathering, other nodes located in the area with the radius of SCPR do not perform any data collection from the environment. Depending on the type of the application requirements, the value of SCPR can vary.Lower data transmission inevitably achieves improvement in delay as shown in Figure15. Moreover, by reducing the amount of data carried in the network, substantial energy saving is achieved as represented in Figures 16-17.Figure 15
Impact of SCPR on delay.Figure 16
Impact of SCPR on total energy consumption.Figure 17
Impact of SCPR on individual energy consumption.


## 5.1. Node Density

In this study, end-to-end delay refers to the time that elapses between the time that the simulation first starts and the time when the last cycle ends. There are two alternatives for the definition of the term duration here. 100-round simulation is performed for each parameter-metric pair evaluation. The first definition for the term duration is that if a node exhausts energy before the completion of the 100th cycle, duration becomes the lifetime of the network. Otherwise, if none of the sensor nodes depletes energy until the end of the last cycle, duration is the time at which the last cycle ends.Node density is a crucial determinant for energy consumption. Thus, in this study, the impact of node density on different performance metrics of the network is analyzed briefly. In this study, the major concern is to prolong the network lifetime to the utmost; therefore, the delay is disregarded. As obviously depicted in Figure9, all of the three methods perform nearly identically in terms of end-to-end delay. A sharper increase in delay occurs up to a threshold density. However, when the density reaches the specified level, a smoother incline is at stake.Figure 9
Effect of the number of tiers on end-to-end delay.Figure10 represents the change in energy consumption regarding the variation in node density. Increase in node density accordingly leads to an increase in the amount of data carried in the network, which, in turn, induces energy dissipation at the same time. Figure 10 clarifies that LEACH and HEED outperform ECMTADR in terms of the total amount of energy consumed in the network. However, the decisive factor while developing an architecture or protocol for WSNs is the lifetime of a single node which actually stands for the lifetime of the network. One way of extending the network lifetime is achieving load balance among the staff as much as possible. In this study, a maximum number of nodes collaborate possibly during data transmission towards the sink. Therefore, though it may seem that much more energy is dissipated totally, the individual performance lies exactly in the opposite sense which is clearly identified in Figure 11. The reason of the deviations encountered is the random deployment of the nodes at the beginning of each simulation. That is, the topology of a 500-node network and one with a 600 node is not identical.Figure 10
Total energy consumed in the network.Figure 11
Impact of the node density on the network lifetime.MTE above refers to the “minimum transmission energy” routing method. ECMTADR shows nearly 50% better performance in terms of network lifetime. Figure11 proves that, by increasing the number of the staff in the network, a better load distribution is achieved. Fair load distribution inherently prolongs the network lifetime. Although the increase in the population seems to induce a rise in energy consumption cumulatively, in the individual sense that will eventuate with network lifetime prolongation.


## 5.2. Cluster Size and Radio Coverage

Cluster size has also crucial impact in terms of delay and energy efficiency. During the design stage, it is intended for all nodes in a cluster to communicate directly with each other. Therefore, each cell diameter is set to be equal to the radio coverage. As the coverage radius increases clusters also expands. Thus, the number of nodes per cluster density increases. In this way, especially during intercluster communication, if an intermediate relay node covers the distance, it will prefer to relay the data directly to the sink which ultimately reduces delay. The impact of cluster size on delay is depicted in Figure12.Figure 12
Impact of the cluster size on the network lifetime.As mentioned before, our methodology does not have any claim on the improvement of the delay. Therefore, as can be seen from the graph, all three methods perform nearly the same.In terms of total energy consumption in the network, LEACH and HEED are seen to outperform ECMTADR as depicted in Figure13. However, as expressed previously, the point is reducing the individual energy consumption which ultimately delays node failure. As obviously identified in Figure 14, the amount of the energy consumed by a node in ECMTADR is lower when compared with LEACH and HEED. Up to a threshold value for the cluster size and radio coverage, individual energy consumption value stays constant. However, after the threshold value, a trend in the vertical direction is observed. That is because the distance between the plain nodes and their CHs and also between the CHs and intermediate relay nodes increase.Figure 13
Total energy consumed in the network.Figure 14
Maximum energy dissipated individually.


## 5.3. SCPR

The major energy consuming component of a sensor node is the communication subunit. Therefore, most of the effort focuses on the challenge of reducing communication energy expenditure. Some of the studies have focused on developing energy-efficient protocols and architectures. Besides, some of them aimed to reduce the amount of data transmitted in the network. One way of achieving data reduction is reducing the amount of emerged data in each cluster. That refers to assigning the task of data gathering to certain nodes, not all of them. In this study, a parameter with the name spatial correlation proximity range (SCPR) is suggested in order to reduce the amount of data created. Nodes with higher energies are charged with data gathering. When a node is assigned the task of data gathering, other nodes located in the area with the radius of SCPR do not perform any data collection from the environment. Depending on the type of the application requirements, the value of SCPR can vary.Lower data transmission inevitably achieves improvement in delay as shown in Figure15. Moreover, by reducing the amount of data carried in the network, substantial energy saving is achieved as represented in Figures 16-17.Figure 15
Impact of SCPR on delay.Figure 16
Impact of SCPR on total energy consumption.Figure 17
Impact of SCPR on individual energy consumption.


## 6. Conclusions

In this paper, we propose a sophisticated architecture called ECMTADR that comprises data reduction, load balance, and topology control. Two important solutions that have been suggested for energy conservation are clustering and data reduction. Both of these methodologies intend to mitigate the challenge of redundant energy consumption induced by the greedy communication subunit. ECMTADR establishes a four-layer architecture virtually. In first place, the network area is partitioned into eight regions. Above the regionalized architecture, sensor nodes are grouped into fixed-size hexagonal clusters at which CHs are elected periodically depending on their residual energy levels, distances to the sink, and other nodes deployed in their clusters. In this way, a fair energy load balance is achieved. Depending on the type of application, data generation can be restrained. In each cluster, only the nodes with higher energy levels can gather data. Other nodes that are positioned in the SCPR range of those nodes do not need to proceed during that stage. Besides, each cluster is again virtually divided into triangular sectors. The reason for sectoring each cluster is to prevent redundant backward transmission. In this way, unnecessary energy expenditure is also prevented. Extensive simulations are performed by considering major parameters that have serious impact on network lifetime and delay. Simulation results clarify that ECMTADR performs better than LEACH and HEED in terms of energy efficiency and lifetime.



---

*Source: 236354-2015-08-02.xml*