# Energy-Aware Sink Node Localization Algorithm for Wireless Sensor Networks

Authors: Mohamed Mostafa Fouad; Vaclav Snasel; Aboul Ella Hassanien
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Wireless sensor networks (WSNs) are a family of wireless networks that usually operate with irreplaceable batteries. The energy sources limitation raises the need for designing specific protocols to prolong the operational lifetime of such networks. These protocols are responsible for messages exchanging through the wireless communications medium from the sensors to the base station (sink node). Therefore, the determination of the optimal location of the sink node becomes crucial to assure both the prolongation of the network’s operation and the quality of the provided services. This paper proposes a novel algorithm based on a Particle Swarm Optimization (PSO) approach for designing an energy-aware topology control protocol. The deliverable of the algorithm is the optimal sink node location within a deployment area. The proposed objective function is based on a number of topology control protocol’s characteristics such as numbers of neighbors per node, the nodes’ residual energy, and how they are far from the center of the deployment area. The simulation results show that the proposed algorithm reveals significant effectiveness to both topology construction and maintenance phases of a topology control protocol in terms of the number of active nodes, the topology construction time, the number of topology reconstructions, and the operational network’s lifetime.


---

## Body

## 1. Introduction

The increasing needs for ubiquitous devices to interact with the physical world have developed the importance of wireless sensor networks (WSNs) in a number of applications. These applications may include military [1], remote environmental monitoring [2], smart road monitoring [3], and remote patient monitoring [4] applications. The major challenges attached with such applications are related to the wireless sensor networks’ limitations, where a sensor node has a limited energy source, a small memory footprint, and low computational capability processor. Furthermore, the deployment strategies of the sensors may add extra limitations; for example, the random deployment of large numbers of sensors may develop other issues related to the wireless network’s scalability, data reliability, security, privacy, and efficient coverage.Determining the sensor node location is an important matter in WSNs; the more accurate the node placement reinforcement, the more the sensing accuracy. The nodes’ locations information becomes more important when the sensors are deployed randomly, which means that they should automatically reconfigure themselves without any human intervention or control. After the network establishment, each node captures some measurements from its environment and broadcasts these data through its neighbors to the sink node. However, assigning a sink node address in self-configuration topology raises another problem that influences the performance of the WSN in terms of energy, delay, and operational lifetime. Therefore, the sink node location should be accurately selected so other nodes will not use much power to deliver their data to that location. As a consequence, the network’s lifetime will be maximized. Furthermore, any proposed optimization should not trade off the area coverage or network’s connectivity characteristics.A great number of researches assumed that, within a single network, the sink node should always be deployed within the center point of the area of interest [5], for example, the work done in [6, 7] which applied the P-Median Problem (PMP) model, which is a well-known NP-hard problem defined by Hakimi [8]. It defined the sink node location where the total weighted distance of reaching all nodes is minimized. On the other hand, [9] gives a comparison between a number of sink placement strategies. Among the other discussed strategies is the Geographic Sink Placement (GSP) strategy, in which the sink is placed at the center of gravity of a sector of a circle. Although it gives fast suitable solutions, it cannot guarantee the optimal sink node location. Also the authors introduced another heuristic based approach entitled Genetic Algorithm-Based Sink Placement (GASP). The GASP is suitable to produce nearly optimal solution for large-scale networks.Chen and Li [5] investigated two proposed sink node placement strategies: the energy-oriented and lifetime-oriented strategies in both the single-hop and multiple-hop WSNs, respectively. The two strategies adopted a routing-cost based Ant routing algorithm. According to their conclusion, the lifetime-oriented strategy had outperformed the energy-oriented strategy in terms of network’s lifetime. Other researches used the integer linear programming to find either the optimal position for the sink node or relay nodes, for example, the work of Hou et al. [12] that developed an efficient polynomial-time heuristic algorithm (SPINDS), which attempted to increase the network lifetime by iteratively moving a relay node to another enhanced location. Güney et al. [13] developed two mixed-integer linear programming formulations as well: those had easily computed good feasible solutions for the sink location and efficient routing. They used a Tabu Search heuristic to identify the best sensor locations that could guarantee the total network’s coverage.Selecting best locations for cluster heads within clustering based routing algorithms is more similar to selecting a location for a sink node within a wireless sensor network. Usually, both are sharing the same aim which is trying to reduce the required transmission energy used by sensor nodes within a network.Yadav et al. [14] suggest a PSO-based solution to the optimal clustering problem through the use of residual energy and transmission distance of sensor nodes. They consider a new operator to be applied inside their algorithm that checks the validity of reached location of the head of the cluster within the current iteration of the PSO algorithm. If the location is not valid, then the algorithm returns to the nearest valid node location that has the highest residual energy to become the current head of the cluster. Although the results are promising, the main limitation within the algorithm is the need for a centralized authority node.Moreover there are other nature inspired algorithms that were used to optimally formulate and optimize routing through clusters. Pan et al. [15] propose an algorithm based on Uneven Clustering Multihop Algorithm (UCMA) and an Improved Ant Colony Optimization (IACO) algorithm. The first former algorithm is used for grouping sensor nodes into unequal clusters along with selecting their cluster head. The decision of the UCMA is based on the nodes’ locations and their residual energies. On the other hand, the IACO is applied for the routing discovery between the head of the cluster and the sink node. The performance evaluations of their proposed algorithms show that the application of the IACO algorithm had accelerated the iterative conversion rate and efficiently reduces the energy consumption rate.This paper proposes an energy-aware sink node localization algorithm for a topology control protocol using a Particle Swarm Optimization technique. The simulation results show that the proposed energy-aware algorithm minimizes the numbers of active nodes and subsequently increases the whole network’s lifetime.The remainder of this paper is organized as follows: Section2 gives a brief overview of topology control protocols. In Section 3 is the proposed optimization technique. The simulation results and a number of performance evaluations are given in Section 4. Finally, Section 5 points out the concluding remarks.


## 2. Topology Control Protocols

A large number of protocols and algorithms have been proposed to overcome the constrained resources of the wireless sensor networks. Many of these protocols and algorithms were developed to extend the lifetime of the wireless network through wisely managing the use of their constrained resources. Topology control (TC) protocols are of the algorithms designed to construct minimized topologies. These topologies proved their efficiency for both energy consumption and radio interferences reductions.A topology control protocol is an iterative process that dynamically reduces the initial topology of a wireless sensor network through controlling nodes’ transmission ranges. The main advantage of the TC protocols is the assets saving of the wireless sensor networks such as the network’s connectivity and coverage [16, 17]. Figure 1 illustrates with brief descriptions the topology control protocol’s phases.Figure 1
Topology control protocols phases.Although the TC protocols reduce energy consumption ratio, they still suffer from a number of drawbacks; for example, securing topology control protocols could negatively affect the performance of such protocols [18]; therefore the current existing security schemes should be adopted to suit TC protocols [19]. On the other hand, most of the designed TC protocols (such as A3 [17] and A3Cov [20]) suppose that even if the deployment is randomized, the sink node location should be fixed within the center of the deployment area, which is not the optimal case in real-life scenarios. Therefore, this paper provides a contribution that is of worth in enhancing the lifetime and the performance of the WSNs. It proposes a PSO-based algorithm to find the adequate position for the sink node within a topology control protocol (the A3 protocol).


## 3. Proposed Sink Node Localization Algorithm Using PSO

Particle Swarm Optimization or PSO is a computational method which could be defined within the heuristic methods categories. As a member of Swarm Intelligence methods (Ant Colony Optimization, Genetic Algorithm, etc.), this method tries to find best solutions from a set of candidate solutions (particles) based on predefined criteria [21]. The differential feature of the PSO is that each particle memorizes both its position and velocity within the search area. Then, it takes a decision according to a predefined objective function: how well is its current position? Through a set of iterations, the particle position is updated using two “best” values. The first one is the best solution the particle achieved so far and the other tracked value is the best value obtained so far by any particle within the solution space.The first aim of this paper is to define the fitness function of the proposed PSO-based algorithm. It is composed of a number of features that affect the stability of any topology control protocols such asthe number of adjacent neighbors,the neighbors’ residual energy, andthe Euclidean distance to the center of the deployment area [5]. Since the nodes in our experiments are stationary, it was assumed that there are N particles which are distributed randomly within the deployment area [22]. Each particle inherits specific properties from its nearest node such as position, residual energy, and neighbor’s list. Figure 2 shows an illustrated example, where particle (p1) inherits the properties of its nearest sensor node (s4). Then and according to the fitness values, the particles will shift their position towards the currently detected gBest. The following steps give a complete view of the proposed PSO-based algorithm.Figure 2
Illustration of particles that simulate sensors’ shifts to the fittest sink node location.Input. A set of sensor nodes S={s1,s2,…,sM}, where M is the number of nodes. Each sensor node si has a number of characteristics; si=(posi,ei,ni), where posi represents the position of the node si within the deployment area, ei defines its residual energy, and ni is the number of neighbors existing within its communication radius.Another important input is a set of particlesP={p1,p2,…,pN}, where N is the number of particles and P≤S. Each pi=(vi,posi,pBesti,gBest), where vi is a vector that represents the particle pi velocity, posi is another vector that saves particle’s position within the deployment area, and finally pBesti and gBest refer to the current best solution the particle pi has achieved and the best solution within the search space, respectively.Output. The fittest node s∈S that will act as a sink node, where its location guarantees the network’s performance in terms of connectivity, coverage, and operational lifetime.Step 1.
Initializevi for all particles to zero.Step 2.
Adjust the initial fitness values ofpBestpi and gBest to zero.Step 3.
Each particle inherits the nearest node characteristics.Step 4.
Use the following equation to compute the fitness valuef(pi) for each particle pi: (1)fpi=α1Npi+α2∑p∈Npip.e+α3dp,where α1, α2, and α3 are random numbers ranged in [0,1]. While N(pi) refers to the sensors neighbors for the particle pi, p.e refers to the residual energy within a neighbor node p∈N(pi) and dp is the Euclidean distance between the position of the particle p and the center of the deployment area.Step 5.
UpdatepBesti using (2)pBesti=pifpi>fpBesti,pBestiotherwise.Step 6.
Select the optimizedpBestpi value among all particles to update the value of gBest using(3)gBest=max⁡pBestp∣p∈P.Step 7.
Calculate the new velocity per each particle within the current iteration using(4)vit+1=ωvit+c1r1pBesti-vit+c2r2gBest-vit.
Whilet denotes the iteration counter and vi represents the particle velocity, ω parameter is a constant inertia-weight that controls velocity of the exploration within the search space. Also, r1 and r2 are random numbers in the range [0,1]. Whereas c1 represents the cognitive coefficient, c2 represents the social coefficient towards the best solution [11].Step 8.
Each particle updates its position based on the new velocity by means of the following equation:(5)posit+1=posit+vit+1.Step 9.
While either a stopping criterion or a predefined number of iterations are still not satisfied, repeat from Step3; otherwise go to Step 10. The intended stopping criterion, within the PSO part of the proposed algorithm, is when gBest value fixed into a certain threshold.Step 10.
Select the nearest node to the final obtainedgBest particle as the fittest position suiting enough to act as a sink node for the current scenario.Although the PSO proved that it is one of the best optimization techniques to solve many problems, it still suffers from the trapping within local optima specially in low dimensional search space. Therefore, the proposed algorithm uses the Gaussian jump to escape from the local minima [23] within Step 9. For limited iterations, when gBest value fixed into a certain threshold, each particle updates its position by a Gaussian jump (shift) using (6) and then the algorithm returns to start from Step 3. Consider(6)posi′=posi+gaussian(),where posi′ is the new position shift of particle pi and gaussian() is a random number based on the Gaussian distribution [23].


## 4. Experiments and Performance Evaluation

The proposed PSO-based algorithm was coded and evaluated using a Java based simulation tool called Atarraya [24]. While Table 1 lists the adjusted PSO parameters for the experiments, Table 2 shows a summary of the most important simulation parameters that were adjusted for the experimental scenarios. The nodes within the simulation are assumed to mimic the characteristics of Crossbow’s Mica Mote sensors with the energy model defined in [25]. The experiments that test the whole network’s lifetime use thedynamic global time-based topology recreation (DGTTRec) topology maintenance protocol, which was proved as the best maintenance policy for the A3 construction protocol [20]. The adjusted triggering criterion for the construction of a new reduced topology is when the time threshold is exceeded, which has been set to 1000 seconds.Table 1
The adjusted PSO parameters.
Parameter
Value
Fitness function probabilityα1
0.4
Fitness function probabilityα2
0.1
Fitness function probabilityα3
0.5
The inertia-weightω
0.8 [10]
The acceleration constants(c1,c2)
2 [11]
Random numbers(r1,r2)
0.5Table 2
Atarraya simulation parameters.
Parameter
Value
Deployment area
600 m∗ 600 m
Number of nodes
100, 200, 300, 400, 500, 600, 700
Sensor node model
Mica Mote
Node communication range
100 m
Node sensing range
20 m
Node location distribution
Uniform
Node energy distribution
Uniform
Max energy
2000 milliamperes-hour (mA-h )The performance metric used within the experiments is the number of active nodes provided by the topology construction that guarantee coverage and the total network’s lifetime. The evaluation section is divided into two parts: the first part tests the impact of the proposed optimization technique on the A3 topology as a construction protocol, while the second part evaluates the performance of adding a maintenance policy to the already optimized topology. The paper will refer to the original A3 topology control protocol (without any optimization feature) as the basic topology protocol (BTP) throughout the context.


### 4.1. The Influences over the Topology Construction Phase

This part tests the impacts of setting the sink node location using the proposed PSO-based algorithm on the topology construction process. Figure3 shows the consumed time per each topology construction scenario (the experiments did not consider the sink node PSO-based selection time within the scope of this paper). Although the results cannot be generalized to different deployment scenarios, the experiments of uniform distribution of nodes within the deployment area show that the sink node PSO-based localization algorithm needs shorter time to construct a topology (the time preservation ranged from 10% to 15% of time units) than the BTP.Figure 3
Topology construction time.Moreover, the proposed algorithm utilizes a lesser number of active nodes with an average of 11% of network’s nodes for the topology construction compared to the BTP that utilizes nearly 12% of active nodes as it is illustrated in Figure4. This significant small reduction of active nodes will assure the prolongation of the operational lifetime of the sensor network since it will save more nodes for future maintenance phases. This reduction cuts down the messages’ complexity between the nodes as well.Figure 4
Number of active nodes.Furthermore, Tables3 and 4 show some statistical analysis for testing the performance of the proposed algorithm through a number of experiments conducted per each nodes’ deployment scenario (four experiments per each scenario). While Table 3 shows a reduction of number of active nodes achieved by the proposed algorithm that reached 6.13%, Table 4 defines a 5.63% decrease in the total mean time required to construct a topology by the proposed algorithm.Table 3
The mean values of the number of active nodes scenarios.
Number of nodes per each scenario
100
200
300
400
500
600
700
Topology with PSO algorithm
34.8
40.75
46.75
43.8
49.5
50.5
52.25
The basic topology
33.25
41.5
47.75
49.4
52.25
62
53Table 4
The mean values of the topology construction time scenarios.
Number of nodes per each scenario
100
200
300
400
500
600
700
Topology with PSO algorithm
54.26
48.23
44.25
46.53
46.05
44.17
46.07
The basic topology
58.4
47.53
45.07
49.21
48.47
53.14
47.41


### 4.2. The Influences over the Whole Network’s Performance

As it is previously proved that the proposed optimization algorithm is an efficient technique that minimizes the number of active nodes per topology construction, it is also proved that the sink node localization within TC protocols is influencing the number of topology maintenance reconstruction executions which give more extensions to the network operational lifetime. Figure5 shows that the proposed algorithm preserves the network health through a number of topology maintenance procedures with an average of 6% compared to 4.8% for the topology control without any optimization feature.Figure 5
Number of topology maintenance reconstructions.As a consequence of the optimization granted from both the number of active nodes and the number of topology reconstruction executions, the sensor network will operate for a lifetime long enough to fulfill the application requirements. Figure6 demonstrates a chart that shows the network’s lifetime changes over different network’s capacities. The chart shows that the proposed PSO-based algorithm had clear advantage within a range from 300 to 600 of network’s capacities. The study of the convergence between our algorithm and the basic topology protocol in high network’s capacities (over 700 nodes) is currently under investigation.Figure 6
Operational network’s lifetime.


## 4.1. The Influences over the Topology Construction Phase

This part tests the impacts of setting the sink node location using the proposed PSO-based algorithm on the topology construction process. Figure3 shows the consumed time per each topology construction scenario (the experiments did not consider the sink node PSO-based selection time within the scope of this paper). Although the results cannot be generalized to different deployment scenarios, the experiments of uniform distribution of nodes within the deployment area show that the sink node PSO-based localization algorithm needs shorter time to construct a topology (the time preservation ranged from 10% to 15% of time units) than the BTP.Figure 3
Topology construction time.Moreover, the proposed algorithm utilizes a lesser number of active nodes with an average of 11% of network’s nodes for the topology construction compared to the BTP that utilizes nearly 12% of active nodes as it is illustrated in Figure4. This significant small reduction of active nodes will assure the prolongation of the operational lifetime of the sensor network since it will save more nodes for future maintenance phases. This reduction cuts down the messages’ complexity between the nodes as well.Figure 4
Number of active nodes.Furthermore, Tables3 and 4 show some statistical analysis for testing the performance of the proposed algorithm through a number of experiments conducted per each nodes’ deployment scenario (four experiments per each scenario). While Table 3 shows a reduction of number of active nodes achieved by the proposed algorithm that reached 6.13%, Table 4 defines a 5.63% decrease in the total mean time required to construct a topology by the proposed algorithm.Table 3
The mean values of the number of active nodes scenarios.
Number of nodes per each scenario
100
200
300
400
500
600
700
Topology with PSO algorithm
34.8
40.75
46.75
43.8
49.5
50.5
52.25
The basic topology
33.25
41.5
47.75
49.4
52.25
62
53Table 4
The mean values of the topology construction time scenarios.
Number of nodes per each scenario
100
200
300
400
500
600
700
Topology with PSO algorithm
54.26
48.23
44.25
46.53
46.05
44.17
46.07
The basic topology
58.4
47.53
45.07
49.21
48.47
53.14
47.41


## 4.2. The Influences over the Whole Network’s Performance

As it is previously proved that the proposed optimization algorithm is an efficient technique that minimizes the number of active nodes per topology construction, it is also proved that the sink node localization within TC protocols is influencing the number of topology maintenance reconstruction executions which give more extensions to the network operational lifetime. Figure5 shows that the proposed algorithm preserves the network health through a number of topology maintenance procedures with an average of 6% compared to 4.8% for the topology control without any optimization feature.Figure 5
Number of topology maintenance reconstructions.As a consequence of the optimization granted from both the number of active nodes and the number of topology reconstruction executions, the sensor network will operate for a lifetime long enough to fulfill the application requirements. Figure6 demonstrates a chart that shows the network’s lifetime changes over different network’s capacities. The chart shows that the proposed PSO-based algorithm had clear advantage within a range from 300 to 600 of network’s capacities. The study of the convergence between our algorithm and the basic topology protocol in high network’s capacities (over 700 nodes) is currently under investigation.Figure 6
Operational network’s lifetime.


## 5. Conclusions

The wireless sensor networks energy model is affected by nodes’ distribution and the sink node’s location. In this paper, a Particle Swarm Optimization approach has been used to select the optimal location for the sink node within a topology control protocol. The proposed fitness function for that topology control included the number of neighbors, their residual energy, and the distance to the center of the deployment area. The simulation results confirm that the proposed optimization approach improves the performance of both phases of the topology control protocol: the topology construction phase and the topology maintenance phase. Since the topology construction time is shortened by a range of 10% to 15% along with the number of active nodes, those pledge the coverage and network’s connectivity; thus the approach provides a layout for a prolongation of the network’s lifetime.



---

*Source: 810356-2015-07-16.xml*