# Prolonging the Lifetime of Two-Tiered Wireless Sensor Networks with Mobile Relays

Authors: Theodore C. Kotsilieris; George T. Karetsos
Journal: ISRN Sensor Networks
 (2013)

---

## Abstract

We propose a clustering scheme for wireless sensor nodes in hierarchical wireless sensor networking architectures that employs mobile relay nodes in order to achieve energy conservation and network lifetime prolongation. The key aspects of our scheme are relay node relocation and reclustering when failures are detected. The performance of the proposed approach is evaluated via simulations for various topology layouts based on the sensor node population and number of mobile relay nodes employed. The results show significant energy savings in particular for topologies with large numbers of sensors.


---

## Body

## 1. Introduction

Wireless sensor networks are becoming more and more popular nowadays due to the significant advantages they present in carrying out specialized monitoring tasks in certain application areas. These areas vary from military [1] and target tracking [2] to healthcare [3–5] and environmental monitoring [6–8]. However, there exist certain aspects that need to be addressed during deployment in order to achieve the best possible functionality and eliminate as much as possible problems that are inherent in wireless sensors technology and networking [9].One of the most important design issues of a wireless sensor network that should be carefully treated is energy consumption and management that directly affects the network’s lifetime. Many research approaches have been proposed already as potential solutions to this problem. The suggested methods span from MAC layer algorithms [10–15] and topology control actions [16, 17] to hierarchical architectures that adopt the introduction of special purpose nodes, called relay nodes [18–20].Research efforts on hierarchical architectures, also called two-tiered architectures, apart from introducing the role of a relay node (RN) or cluster head (CH), go further by applying clustering techniques that aim at minimizing the sensor communication cost [18, 21]. Several techniques have been proposed in the literature that aim to avoid rapid battery drainage that consequently may cause network connectivity failures or sensing area holes [22–25]. In single-hop operation of wireless sensor nodes (WSNs), data propagation towards the destination (i.e., the base station (BS)) that will further process the sensed data is accomplished by the relay nodes. Thus, in hierarchical deployments the critical factor is the lifetime achieved by the relay nodes which has to be enhanced as much as possible. Towards this, a measurable objective is the number of data gathering rounds that can be carried out by an RN. A data gathering round of an RN corresponds to the procedure of receiving the collected data from the nodes in its cluster and transmitting them to the base station [26].This work proposes a clustering scheme for SNs that enhances energy conservation and prolongs the network’s lifetime. The main difference with other similar approaches is that the RNs are not considered stationary nodes expected to function at the locations that were initially deployed but with mobility capabilities that allow them to move to new locations designated by optimal energy consumption management procedures. In particular we extend the work presented in [18] so that the RNs can move to new locations, a feature that in conjunction with re-clustering can lead to energy consumption minima.The rest of this work is organized as follows. Section2 presents background work on the field of topology control for WSNs and clustering algorithms. In Section 3, we propose an algorithm that applies postdeployment topology control functions in an already formed cluster so that energy consumption is minimized. Simulation results that highlight the energy conservation achieved by the proposed algorithm are presented in Section 4. Finally, Section 5 concludes our work and suggests future research items.


## 2. WSN Mobility-Based Topology Control and Clustering Algorithms

With the proliferation of WSN technologies and applications, the need for incorporating mobility has been identified as a means to enhance their performance. To this end various mobility models for WSNs have been introduced that range from sensing node mobility [20, 21] to base station (BS) movement in predefined or autonomous paths [27–29].In the case of mobile sensor nodes, the movement capability is limited due to energy saving constraints and usually is identified within a cluster’s scope. On the contrary, a mobile base station or data collector does not present such limitations as they can be usually fed with unlimited energy. However, an energy conservation scheme based on a mobile BS is not appropriate for real-time data collection because a sensor that is ready to transmit should wait until it gets in the communication range of the BS. In order to confront with the implied data collection delay of this scheme, aggregation and processing of sensed data take place, which are usually performed by relay nodes [30].


### 2.1. Sensor Mobility Models

Sensor mobility is a recent addition to the WSNs characteristics that has been employed to face initial deployment problems and communication holes that may arise due to node failure or battery drainage. The solutions proposed vary from working with redundant nodes [31] ready to move—in a straightforward or cascaded mode—when asked so to using functional nodes of the WSN to replace failed ones or for balancing network traffic [32]. The mobile nodes of the latter case may be plain sensors with battery limitations or relays with enriched mobility and computational capabilities [33].Our motivation of addressing such a sensor network redeployment problem combined with relay node mobility constraints is to evaluate further enhancements on scalability and power efficiency of clustering algorithms. In this paper a sensor field (topology) is divided (clustered) into groups (clusters) in accordance with the constraints defined by the Integer Linear Programming (ILP) formulas given in [18]. In this work, after the initial clustering has taken place, no further re-deployment (re-clustering) actions are taken in order to further minimize energy wastage.Our work goes a step further towards network lifetime maximization. The RNs are not considered stationary devices designated to perform data collection and cluster coordination, but may move to new locations within the formed cluster in order to achieve power consumption savings. Also, RNs are not considered to be subject of power limitations, at least not at the same extent that SNs do. The trajectory of each RN is calculated taking into account all the necessary constraints so as not to incur any side effects to the clusters’ structure.


### 2.2. Sensor Communication: Radio Model

The main components of a sensor node are a sensing circuit, a data processing unit, and a radio transceiver. However, the power required for communication is the dominant part of the total power consumption in a sensor network. A radio model that defines in detail the communication power consumption is outlined in [34].As this model suggests, energy is consumed at a rate ofETx-elec 50 nJ/bit for running the transmitter circuitry and ERx-elec 50 nJ/bit for the receiving one, which for the rest of this paper will be called Eelec. Additionally, the transmit amplifier also dissipates εamp amount of energy (a typical value is 100 pJ/bit/m2) to transmit one bit of data over unit distance.In a typical WSN, energy consumption is mainly due to three reasons: packet transmission, packet reception, and data processing.Thus, by taking into account the energy loss per bit due to transmission at a distanced, the energy dissipated by the amplifier to transmit k bits is given by
(1)ETx-amp(k,d)=εamp*k*dq,
where q corresponds to the path loss exponent. Therefore, the overall energy consumption to transmit k bits is given by
(2)ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)⟹ETx(k,d)=Eelec*k+εamp*k*dq.
On the other hand, the energy dissipated to receive k bits over a distance d is given by
(3)ERx(k)=ERx-elec(k)⟹ERx(k)=Eelec*k.
The energy consumed to process k bits is defined as
(4)ECPU(k)=εCPU*k,
where εCPU (nJ/bit) is the energy consumed for processing a single bit.


## 2.1. Sensor Mobility Models

Sensor mobility is a recent addition to the WSNs characteristics that has been employed to face initial deployment problems and communication holes that may arise due to node failure or battery drainage. The solutions proposed vary from working with redundant nodes [31] ready to move—in a straightforward or cascaded mode—when asked so to using functional nodes of the WSN to replace failed ones or for balancing network traffic [32]. The mobile nodes of the latter case may be plain sensors with battery limitations or relays with enriched mobility and computational capabilities [33].Our motivation of addressing such a sensor network redeployment problem combined with relay node mobility constraints is to evaluate further enhancements on scalability and power efficiency of clustering algorithms. In this paper a sensor field (topology) is divided (clustered) into groups (clusters) in accordance with the constraints defined by the Integer Linear Programming (ILP) formulas given in [18]. In this work, after the initial clustering has taken place, no further re-deployment (re-clustering) actions are taken in order to further minimize energy wastage.Our work goes a step further towards network lifetime maximization. The RNs are not considered stationary devices designated to perform data collection and cluster coordination, but may move to new locations within the formed cluster in order to achieve power consumption savings. Also, RNs are not considered to be subject of power limitations, at least not at the same extent that SNs do. The trajectory of each RN is calculated taking into account all the necessary constraints so as not to incur any side effects to the clusters’ structure.


## 2.2. Sensor Communication: Radio Model

The main components of a sensor node are a sensing circuit, a data processing unit, and a radio transceiver. However, the power required for communication is the dominant part of the total power consumption in a sensor network. A radio model that defines in detail the communication power consumption is outlined in [34].As this model suggests, energy is consumed at a rate ofETx-elec 50 nJ/bit for running the transmitter circuitry and ERx-elec 50 nJ/bit for the receiving one, which for the rest of this paper will be called Eelec. Additionally, the transmit amplifier also dissipates εamp amount of energy (a typical value is 100 pJ/bit/m2) to transmit one bit of data over unit distance.In a typical WSN, energy consumption is mainly due to three reasons: packet transmission, packet reception, and data processing.Thus, by taking into account the energy loss per bit due to transmission at a distanced, the energy dissipated by the amplifier to transmit k bits is given by
(1)ETx-amp(k,d)=εamp*k*dq,
where q corresponds to the path loss exponent. Therefore, the overall energy consumption to transmit k bits is given by
(2)ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)⟹ETx(k,d)=Eelec*k+εamp*k*dq.
On the other hand, the energy dissipated to receive k bits over a distance d is given by
(3)ERx(k)=ERx-elec(k)⟹ERx(k)=Eelec*k.
The energy consumed to process k bits is defined as
(4)ECPU(k)=εCPU*k,
where εCPU (nJ/bit) is the energy consumed for processing a single bit.


## 3. Optimal Relay Node Placement

The clustering model proposed in [18] is derived via integer-linear-programming- (ILP-) based formulations covering not only single-hop communications, but also multihop ones, and the corresponding methods are called ILP-S and ILP-M, respectively. The proposed version of our algorithm performs clustering under the assumption of single-hop data transmission in order to perform a preliminary evaluation of its operation without the need to take care for intersensor communication at this stage. The main innovation introduced in our approach, called MILP-S (M stands for mobile), is the possibility to relocate the RNs since they hold mobility capabilities. The scope of their movement is to find the most suitable location within a cluster so that the overall energy consumption is minimized. In order to locate the new position of the relay node that minimizes the overall energy consumption, we consider all the locations that are not further than a distance rmax from each node that comprises the cluster. Distance rmax is the transmission range of a sensor. This constraint is necessary in order to preserve the topology of the already formulated clusters. If such a location is found, the relay node is forwarded towards it and the network lifetime is increased.


### 3.1. Step  1: Single-Hop ILP Cluster Formulation

The adopted network model follows a two-tiered wireless network architecture wheres sensor nodes form the sensing area (i.e., the lower layer), and r relay nodes comprise the upper layer. The sink node (or base station) is considered to reside outside the sensing area at a long distance from both sensing and relay nodes. Thus, the total number of nodes, N, of the network is s+r+1. Each sensor is designated by label a, where 1≤a≤s. A relay is denoted by a label b, with s+1≤b≤s+r while the label of the base station is s+r+1. It should be noted that sensor and relay nodes operate in different ways. The former perform plain sensing while the latter gather the cluster’s sensed data and transmit them to the sink node. Thus, energy depletion and consequent shutdown of a sensing node may affect only the accuracy of measurements. On the other hand, a possible energy depletion of a relay node, which is actually the cluster head, results in total loss of the gathered data from the respective cluster.The simulation topology consists of a grid of sensor nodes with relay nodes placed arbitrarily on the grid and a base station. Although the sensor nodes are considered to be uniformly distributed, the relay nodes are randomly placed. This topology formation follows the algorithm’s concept. The lower layer that consists of the sensing nodes that create data has little to do with the cluster formation procedure which depends on the relay nodes’ characteristics such as position, number, and transmission range. In addition, our algorithm goes one step further: after the initial random cluster formation, we deal also with the issue of prolonging the network’s lifetime by appropriately moving and relocating the relay nodes that are less in number and have superior processing and energy characteristics. In such a setup, each sensor can belong to only one cluster and each relay node can supervise only one cluster. ILP-S proposes a formulation that createsr clusters (equal to the number of the relay nodes), each one consisting of Nb nodes, that leads to network lifetime maximization. In the single-hop model, each relay node receives data only from sensors that belong to its cluster and directly transmits them to the corresponding base station. A cluster is defined through a binary matrix Xij as
(5)Xij={1,ifnodeibelongstotheclusterofRNj,∀i,j:1≤i≤s,s+1≤j≤s+r0,inanyothercase.
The condition above (according to the predefined notations) can be re-written as
(6)Xij={1,ifni,j∈Sj∀i,j:1≤i≤|Sj|0,inanyothercase.The algorithm’s objective is to minimize the energy dissipated per round of operation,Esingle-hop, subject to the following constraintsEach sensor node must join only one cluster:(7)∑j=s+1s+rΧij=1,∀i,1≤i≤s.A sensor node may transmit to the relay node only if the latter is located within the transmission rangermax of the node
(8)Xijdij≤rmax∀i,1≤i≤s∀j,s+1≤j≤s+r,
where di,j denotes the Euclidean distance between locations i and j (i.e., dij=(xi-xj)2+(yi-yj)2).The total number of bitsfj, generated in cluster j and received by relay node j, is computed by
(9)∑i=1sbiXij=fj,∀j∈N.Furthermore, the maximum energy spent by an RN in a round is computed by(10)Esingle-hop,j=ETX-elecfj+ERX-elecfj+εampfjdj,s+r+1q,Esingle-hop=∑∀j∈NEsingle-hop,j.


### 3.2. Step  2: Relay Node Movement to New Locations

We have devised a replacement algorithm that is executed to calculate the optimum location of the relay nodes as soon as the respective clusters are formed. LetL denote the set of all possible locations for the placement of a sensor within the sensing area. Since every node belongs to a cluster, the following holds: L={Ls+1,Ls+2,…,Ls+r}, where Lj,∀j:s+1≤j≤s+r denotes all the available locations for cluster j while r denotes the number of relay nodes and consequently the clusters that will be formed. The possible locations that an RN may be placed are a subset of the locations included in the cluster. Let PLj⊆Lj be a set of feasible distinct locations (a distinct location is represented by li,j,∀i,j:1≤i≤|Lj|, s+1≤j≤s+r) for the relay node i according to
(11)min(ESingle-hop,j(lij)),
where li,j∈PLj:∥lcurrent-li,j∥≤rmax, ∀i∈{1⋯|Lj|}.The above mentioned algorithm is described in detail in Algorithm1.Algorithm 1:The relay node movement algorithm.
For eachj∈N do
PLj←0
for  eachi∈Sj, i:1≤i≤|Lj| do
if∥li,j-li′,j′∥≤rmax,  ∀li′,j′∈Lj∖{li,j} do
PLj←li′,j′
if Esingle-hop,j′<Esingle-hop,j do
li,j←li,j′
end
end
end
end


## 3.1. Step  1: Single-Hop ILP Cluster Formulation

The adopted network model follows a two-tiered wireless network architecture wheres sensor nodes form the sensing area (i.e., the lower layer), and r relay nodes comprise the upper layer. The sink node (or base station) is considered to reside outside the sensing area at a long distance from both sensing and relay nodes. Thus, the total number of nodes, N, of the network is s+r+1. Each sensor is designated by label a, where 1≤a≤s. A relay is denoted by a label b, with s+1≤b≤s+r while the label of the base station is s+r+1. It should be noted that sensor and relay nodes operate in different ways. The former perform plain sensing while the latter gather the cluster’s sensed data and transmit them to the sink node. Thus, energy depletion and consequent shutdown of a sensing node may affect only the accuracy of measurements. On the other hand, a possible energy depletion of a relay node, which is actually the cluster head, results in total loss of the gathered data from the respective cluster.The simulation topology consists of a grid of sensor nodes with relay nodes placed arbitrarily on the grid and a base station. Although the sensor nodes are considered to be uniformly distributed, the relay nodes are randomly placed. This topology formation follows the algorithm’s concept. The lower layer that consists of the sensing nodes that create data has little to do with the cluster formation procedure which depends on the relay nodes’ characteristics such as position, number, and transmission range. In addition, our algorithm goes one step further: after the initial random cluster formation, we deal also with the issue of prolonging the network’s lifetime by appropriately moving and relocating the relay nodes that are less in number and have superior processing and energy characteristics. In such a setup, each sensor can belong to only one cluster and each relay node can supervise only one cluster. ILP-S proposes a formulation that createsr clusters (equal to the number of the relay nodes), each one consisting of Nb nodes, that leads to network lifetime maximization. In the single-hop model, each relay node receives data only from sensors that belong to its cluster and directly transmits them to the corresponding base station. A cluster is defined through a binary matrix Xij as
(5)Xij={1,ifnodeibelongstotheclusterofRNj,∀i,j:1≤i≤s,s+1≤j≤s+r0,inanyothercase.
The condition above (according to the predefined notations) can be re-written as
(6)Xij={1,ifni,j∈Sj∀i,j:1≤i≤|Sj|0,inanyothercase.The algorithm’s objective is to minimize the energy dissipated per round of operation,Esingle-hop, subject to the following constraintsEach sensor node must join only one cluster:(7)∑j=s+1s+rΧij=1,∀i,1≤i≤s.A sensor node may transmit to the relay node only if the latter is located within the transmission rangermax of the node
(8)Xijdij≤rmax∀i,1≤i≤s∀j,s+1≤j≤s+r,
where di,j denotes the Euclidean distance between locations i and j (i.e., dij=(xi-xj)2+(yi-yj)2).The total number of bitsfj, generated in cluster j and received by relay node j, is computed by
(9)∑i=1sbiXij=fj,∀j∈N.Furthermore, the maximum energy spent by an RN in a round is computed by(10)Esingle-hop,j=ETX-elecfj+ERX-elecfj+εampfjdj,s+r+1q,Esingle-hop=∑∀j∈NEsingle-hop,j.


## 3.2. Step  2: Relay Node Movement to New Locations

We have devised a replacement algorithm that is executed to calculate the optimum location of the relay nodes as soon as the respective clusters are formed. LetL denote the set of all possible locations for the placement of a sensor within the sensing area. Since every node belongs to a cluster, the following holds: L={Ls+1,Ls+2,…,Ls+r}, where Lj,∀j:s+1≤j≤s+r denotes all the available locations for cluster j while r denotes the number of relay nodes and consequently the clusters that will be formed. The possible locations that an RN may be placed are a subset of the locations included in the cluster. Let PLj⊆Lj be a set of feasible distinct locations (a distinct location is represented by li,j,∀i,j:1≤i≤|Lj|, s+1≤j≤s+r) for the relay node i according to
(11)min(ESingle-hop,j(lij)),
where li,j∈PLj:∥lcurrent-li,j∥≤rmax, ∀i∈{1⋯|Lj|}.The above mentioned algorithm is described in detail in Algorithm1.Algorithm 1:The relay node movement algorithm.
For eachj∈N do
PLj←0
for  eachi∈Sj, i:1≤i≤|Lj| do
if∥li,j-li′,j′∥≤rmax,  ∀li′,j′∈Lj∖{li,j} do
PLj←li′,j′
if Esingle-hop,j′<Esingle-hop,j do
li,j←li,j′
end
end
end
end


## 4. Simulation Results

### 4.1. Environment Setup

The communication energy consumption is calculated according to the first-order radio model [34] with the constantsETX-elec=50nj/bit,ERX-elec=50nj/bit,εamp=100pJ/bit/m2,q=2,rmax=200m.Our simulation environment comprised a combination of MATLAB and FICO Xpress Optimization suite that allowed us to solve the ILP clustering problem quickly and efficiently.The simulated topologies scaled from 576 nodes (24 units of length by 24 units of width) to 10.000 nodes (100 units long by 100 units wide) while the RNs populations varied from 4 to 25. Such a dense distribution of sensing and relay nodes is allowed by the low pernode cost which supports at the same time the appropriate redundancy so as to obtain accurate field data.The simulation results reveal an improvement to the energy consumption compared to ILP-S that increases as the network topology population grows. After executing the clustering algorithm, on a square-shaped topology of 6400 sensor nodes, uniformly distributed on an area of 80 units length to 80 units width with 4 relay nodes available, we obtain the clustering depicted in Figure1.Figure 1
Clustering results with 4 relay nodes for an 80*80 sensor node topology.Accordingly, Figure2 presents a 100*100 sensor node grid topology with 9 relay nodes.Figure 2
Clustering results with 9 relay nodes for a 100*100 sensor node topology.Each cluster in Figures1 and 2 contains a different number of nodes because the initial placement of the relay nodes within the sensing area is performed randomly. On the other hand, the distribution of the sensing nodes is done in a uniform manner due to its simplicity for grid topology formation and neutrality in producing the simulation results. It is also easier to study the algorithm’s scalability performance as the sensing nodes increase. We have to note also that despite the fact that the grid sizes may seem unrealistic they are in essence very important for assessment purposes. Further simulations will be performed over special purpose topologies where harsh environments affect the sensing nodes placement but mobility is a necessary feature in order to gain network connectivity.


### 4.2. Performance Evaluation of MILP-S over ILP-S

The performance results obtained are given in this section. Our method’s primary goal is to cluster the sensor nodes around an RN such that energy consumption within the cluster is minimized. The resulting energy consumptions when forming 4, 9, 16, and 25 clusters per sensing area are depicted in Table1 and are compared to the ILP-S method.Table 1
Comparison of energy consumption between ILP-S and MILP-S for several grid sizes.
Grid size (nodes)
Energy conservation method
24 × 24(576)
30 × 30(900)
40 × 40(1600)
50 × 50(2500)
60 × 60(3600)
70 × 70(4900)
80 × 80(6400)
90 × 90 (8100)
100 × 100(10000)
Performance
2,58%
5,69%
7,06%
11,53%
12,35%
12,43%
13,15%
14,99%
16,02%
4
ILP-S
0,00785
0,012935
0,024945
0,043936
0,072339
0,102909
0,138025
0,209471
0,282038
MILP-S
0,007647
0,012199
0,023184
0,038871
0,063403
0,090113
0,119877
0,178073
0,236846
Performance
3,19%
4,22%
5,28%
9,18%
9,45%
13,29%
15,86%
16,38%
18,61%
9
ILP-S
0,007615
0,012212
0,022697
0,038056
0,057182
0,086448
0,121281
0,159343
0,220506
MILP-S
0,007373
0,011697
0,021498
0,034562
0,051780
0,074958
0,102047
0,133237
0,179472
Performance
8,88%
9,63%
9,80%
10,44%
11,19%
11,56%
11,95%
12,90%
14,31%
16
ILP-S
0,007578
0,012098
0,021989
0,035727
0,054401
0,076694
0,103474
0,138666
0,18038
MILP-S
0,006906
0,010933
0,019834
0,031996
0,048315
0,067825
0,091112
0,120772
0,154576
Performance
7,42%
8,39%
9,56%
10,29%
11,49%
12,38%
12,94%
13,11%
15,88%
25
ILP-S
0,007537
0,011954
0,021917
0,035073
0,052546
0,073813
0,100676
0,131826
0,168469
MILP-S
0,006978
0,010951
0,019821
0,031463
0,046508
0,064677
0,087652
0,114541
0,141715Table1 presents the performance improvement of MILP-S over the ILP-S method versus the number of nodes for different grid formations and relay nodes. The comparison metric is energy consumption with 4, 9, 16, and 25 relay nodes. Table 1 also includes the percentage of improvement of our algorithm over ILP-S. For clarity, the results provided in Table 1 are plotted in Figure 3.Figure 3
Energy saving improvement of MILP-S over ILP-S clustering method for several grid sizes.As it can be easily observed, MILP-S method surpasses ILP-S in energy-saving terms. Performance improvement varies from 4%, for sensing fields that contain approximately 500 sensors, to 15%–20% for large topologies with 10.000 nodes. Accordingly the achieved lifetimes are also improved (see Table2). The measurements regarding network lifetimes were conducted with an initial energy of 5 Joules per SN.Table 2
Network lifetimes for ILP-S and MILP-S for various network topologies.
Grid size (nodes)
Energy conservation method
24 × 24(576)
30 × 30(900)
40 × 40(1600)
50 × 50(2500)
60 × 60(3600)
70 × 70(4900)
80 × 80(6400)
90 × 90(8100)
100 × 100(10000)
2,65%
6,03%
7,60%
13,03%
14,09%
14,20%
15,14%
17,63%
19,08%
4
ILP-S
637
387
200
114
69
49
36
24
18
MILP-S
654
410
216
129
79
55
42
28
21
3,29%
4,40%
5,58%
10,11%
10,43%
15,33%
18,85%
19,59%
22,86%
9
ILP-S
657
409
220
131
87
58
41
31
23
MILP-S
678
427
233
145
97
67
49
38
28
9,74%
10,65%
10,87%
11,66%
12,60%
13,08%
13,57%
14,82%
16,69%
16
ILP-S
660
413
227
140
92
65
48
36
28
MILP-S
724
457
252
156
103
74
55
41
32
8,02%
9,16%
10,58%
11,47%
12,98%
14,13 %
14,86%
15,09%
18,88%
25
ILP-S
663
418
228
143
95
68
50
38
30
MILP-S
717
457
252
159
108
77
57
44
35Applying the power-law least-squares method to the computed network lifetimes results in a fit, depicted in Figure3, with the coefficient of determination, R2, varying from 0.9978 to 0.9997 (see Table 3). Thus, the lifetime of such a network layout can be predicted through an equation of the form y=AxB. The values of A and B coefficients are assumed to be related to the parameters used during the ILP formulation of the clustering problem and more specifically to the dataflow from each sensor (i.e., bits per node), the relay node location, and the first-order radio constants (i.e., ETX-elec, ERX-elec, εamp, rmax, q).Table 3
TheR2 coefficient of determination for various relays.
Number of relays
R
2
4
0,9978
9
0,9989
16
0,9995
25
0,9997From Figure4, we observe that the network lifetime decreases at unacceptable levels when the number of sensors exceeds 2000 nodes. This result has to be taken into account during deployments with such or higher number of sensors.Figure 4
Power-law least square fitting to the simulation results of the MILP-S method.


## 4.1. Environment Setup

The communication energy consumption is calculated according to the first-order radio model [34] with the constantsETX-elec=50nj/bit,ERX-elec=50nj/bit,εamp=100pJ/bit/m2,q=2,rmax=200m.Our simulation environment comprised a combination of MATLAB and FICO Xpress Optimization suite that allowed us to solve the ILP clustering problem quickly and efficiently.The simulated topologies scaled from 576 nodes (24 units of length by 24 units of width) to 10.000 nodes (100 units long by 100 units wide) while the RNs populations varied from 4 to 25. Such a dense distribution of sensing and relay nodes is allowed by the low pernode cost which supports at the same time the appropriate redundancy so as to obtain accurate field data.The simulation results reveal an improvement to the energy consumption compared to ILP-S that increases as the network topology population grows. After executing the clustering algorithm, on a square-shaped topology of 6400 sensor nodes, uniformly distributed on an area of 80 units length to 80 units width with 4 relay nodes available, we obtain the clustering depicted in Figure1.Figure 1
Clustering results with 4 relay nodes for an 80*80 sensor node topology.Accordingly, Figure2 presents a 100*100 sensor node grid topology with 9 relay nodes.Figure 2
Clustering results with 9 relay nodes for a 100*100 sensor node topology.Each cluster in Figures1 and 2 contains a different number of nodes because the initial placement of the relay nodes within the sensing area is performed randomly. On the other hand, the distribution of the sensing nodes is done in a uniform manner due to its simplicity for grid topology formation and neutrality in producing the simulation results. It is also easier to study the algorithm’s scalability performance as the sensing nodes increase. We have to note also that despite the fact that the grid sizes may seem unrealistic they are in essence very important for assessment purposes. Further simulations will be performed over special purpose topologies where harsh environments affect the sensing nodes placement but mobility is a necessary feature in order to gain network connectivity.


## 4.2. Performance Evaluation of MILP-S over ILP-S

The performance results obtained are given in this section. Our method’s primary goal is to cluster the sensor nodes around an RN such that energy consumption within the cluster is minimized. The resulting energy consumptions when forming 4, 9, 16, and 25 clusters per sensing area are depicted in Table1 and are compared to the ILP-S method.Table 1
Comparison of energy consumption between ILP-S and MILP-S for several grid sizes.
Grid size (nodes)
Energy conservation method
24 × 24(576)
30 × 30(900)
40 × 40(1600)
50 × 50(2500)
60 × 60(3600)
70 × 70(4900)
80 × 80(6400)
90 × 90 (8100)
100 × 100(10000)
Performance
2,58%
5,69%
7,06%
11,53%
12,35%
12,43%
13,15%
14,99%
16,02%
4
ILP-S
0,00785
0,012935
0,024945
0,043936
0,072339
0,102909
0,138025
0,209471
0,282038
MILP-S
0,007647
0,012199
0,023184
0,038871
0,063403
0,090113
0,119877
0,178073
0,236846
Performance
3,19%
4,22%
5,28%
9,18%
9,45%
13,29%
15,86%
16,38%
18,61%
9
ILP-S
0,007615
0,012212
0,022697
0,038056
0,057182
0,086448
0,121281
0,159343
0,220506
MILP-S
0,007373
0,011697
0,021498
0,034562
0,051780
0,074958
0,102047
0,133237
0,179472
Performance
8,88%
9,63%
9,80%
10,44%
11,19%
11,56%
11,95%
12,90%
14,31%
16
ILP-S
0,007578
0,012098
0,021989
0,035727
0,054401
0,076694
0,103474
0,138666
0,18038
MILP-S
0,006906
0,010933
0,019834
0,031996
0,048315
0,067825
0,091112
0,120772
0,154576
Performance
7,42%
8,39%
9,56%
10,29%
11,49%
12,38%
12,94%
13,11%
15,88%
25
ILP-S
0,007537
0,011954
0,021917
0,035073
0,052546
0,073813
0,100676
0,131826
0,168469
MILP-S
0,006978
0,010951
0,019821
0,031463
0,046508
0,064677
0,087652
0,114541
0,141715Table1 presents the performance improvement of MILP-S over the ILP-S method versus the number of nodes for different grid formations and relay nodes. The comparison metric is energy consumption with 4, 9, 16, and 25 relay nodes. Table 1 also includes the percentage of improvement of our algorithm over ILP-S. For clarity, the results provided in Table 1 are plotted in Figure 3.Figure 3
Energy saving improvement of MILP-S over ILP-S clustering method for several grid sizes.As it can be easily observed, MILP-S method surpasses ILP-S in energy-saving terms. Performance improvement varies from 4%, for sensing fields that contain approximately 500 sensors, to 15%–20% for large topologies with 10.000 nodes. Accordingly the achieved lifetimes are also improved (see Table2). The measurements regarding network lifetimes were conducted with an initial energy of 5 Joules per SN.Table 2
Network lifetimes for ILP-S and MILP-S for various network topologies.
Grid size (nodes)
Energy conservation method
24 × 24(576)
30 × 30(900)
40 × 40(1600)
50 × 50(2500)
60 × 60(3600)
70 × 70(4900)
80 × 80(6400)
90 × 90(8100)
100 × 100(10000)
2,65%
6,03%
7,60%
13,03%
14,09%
14,20%
15,14%
17,63%
19,08%
4
ILP-S
637
387
200
114
69
49
36
24
18
MILP-S
654
410
216
129
79
55
42
28
21
3,29%
4,40%
5,58%
10,11%
10,43%
15,33%
18,85%
19,59%
22,86%
9
ILP-S
657
409
220
131
87
58
41
31
23
MILP-S
678
427
233
145
97
67
49
38
28
9,74%
10,65%
10,87%
11,66%
12,60%
13,08%
13,57%
14,82%
16,69%
16
ILP-S
660
413
227
140
92
65
48
36
28
MILP-S
724
457
252
156
103
74
55
41
32
8,02%
9,16%
10,58%
11,47%
12,98%
14,13 %
14,86%
15,09%
18,88%
25
ILP-S
663
418
228
143
95
68
50
38
30
MILP-S
717
457
252
159
108
77
57
44
35Applying the power-law least-squares method to the computed network lifetimes results in a fit, depicted in Figure3, with the coefficient of determination, R2, varying from 0.9978 to 0.9997 (see Table 3). Thus, the lifetime of such a network layout can be predicted through an equation of the form y=AxB. The values of A and B coefficients are assumed to be related to the parameters used during the ILP formulation of the clustering problem and more specifically to the dataflow from each sensor (i.e., bits per node), the relay node location, and the first-order radio constants (i.e., ETX-elec, ERX-elec, εamp, rmax, q).Table 3
TheR2 coefficient of determination for various relays.
Number of relays
R
2
4
0,9978
9
0,9989
16
0,9995
25
0,9997From Figure4, we observe that the network lifetime decreases at unacceptable levels when the number of sensors exceeds 2000 nodes. This result has to be taken into account during deployments with such or higher number of sensors.Figure 4
Power-law least square fitting to the simulation results of the MILP-S method.


## 5. Conclusions

In this work a clustering method for prolonging the lifetime of two-tiered wireless sensor networks is proposed and evaluated. In particular, we extend static clustering through the provision of mobility for the corresponding relay nodes. The obtained simulation results show a significant performance improvement on energy savings when the relay nodes are allowed to move into new locations within the initially formulated clusters. This performance improvement may exceed 20% when large topologies with thousands of sensors are considered. Furthermore, a curve fitting analysis on the results revealed that the network lifetime follows a power-law distribution. Finally, future work will focus on optimizing network coverage, connectivity, and performance in case of sensor or even relay node failures in special purpose topologies.



---

*Source: 610796-2013-03-05.xml*