# Amorphous Localization Algorithm Based on BP Artificial Neural Network

Authors: Lin-zhe Zhao; Xian-bin Wen; Dan Li
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Accurate localization of nodes is one of the key issues of wireless sensor network (WSN). Because the disadvantages of the classical Amorphous algorithm will produce large localization error in the process of localization, an improved localization algorithm is proposed in this paper to solve the problem. The improved algorithm introduces the received signal strength threshold to modify the minimum hop from the unknown node to the beacon node. Then, Back Propagation (BP) algorithm is introduced to optimize the threshold and reduce the localization error. The simulation results show that the localization accuracy of the improved algorithm is higher than that of other algorithms and the energy consumption does not increase too much.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) is composed of a large number of sensor nodes, which can monitor and acquire physical information in the distribution detection area in real time. WSN has gained a wide attention in recent years and has been applied to the medical field, the industry, the military, and other fields, such as remote health, smart home, battlefield reconnaissance, and environmental monitoring. The location of sensor nodes needs not be engineered or predetermined. This means that sensor nodes can be deployed randomly in inaccessible terrains or disaster relief operations. In addition, this also means that sensor network protocols and algorithms must possess self-organizing capabilities [1].The localization problem of WSNs can be interpreted that, in a sensor network in which the own location of multiple nodes has been known, which is named by the beacon node, and the location of target node which is named by the unknown nodes is obtained by the sensor information and effective localization algorithm. According to most of the applications in WSN, the information without space and time data is unvalued. In order to better monitor and track the target, the location of sensor node is one of the most important information [2, 3]. In recent years, localization of wireless sensor network node has become a popular and significant issue.At present, according to whether or not the network needs to measure the actual distances between network nodes, the WSN localization algorithm can be divided into two categories: one is Range-Based algorithm and the other is Range-Free algorithm. The Range-Based algorithm mainly includes the measurements of angle and distance, such as Received Signal Strength Indicator (RSSI), Time of Arrival (TOA), Time Difference on Arrival (TDOA), and Angle of Arrival (AOA) [3]. Then, the location of the unknown node can be calculated by the trilateral measurement method and triangulation method. So it needs extra hardware supporting, large computing, and communicating with high energy consumption. The Range-Free approach only depends on the connectivity of nodes such as the hops for localization without any extra hardware supporting. It includes Centroid algorithm [4], Distance Vector-Hop (DV-Hop) [5], and Amorphous algorithm. Although the localization accuracy of the range-based algorithm is usually higher than that of the range-free algorithm, because of the simple hardware support, the lower consumption, and the antinoise ability, the range-free algorithm is widely used in many applications.In this case, how to improve the localization accuracy of Range-Free approach has drawn much attention. Many experts put forward the optimization algorithms based on intelligent algorithm to improve the localization accuracy. For example, BP localization algorithm based on virtual nodes (VN-BP) with lower localization error has been proposed in [6]. The advantages of BP artificial neural network in error optimization are formidable self-organizing and self-learning capacity, error back-propagation, and error minimum principle [7]. Therefore, it is a good idea to introduce BP neural networks in the localization algorithm to improve the localization accuracy. Although Amorphous algorithm is easy to implement, it will produce large error in the process of localization. In order to solve the problem, an improved localization algorithm is proposed in this paper to reduce the localization error. The proposed algorithm is clarified in two aspects: (1) modify the minimum hop from the unknown node to the beacon node by setting the received signal strength threshold; (2) BP algorithm is introduced to optimize the threshold and reduce the localization error.


## 2. Amorphous Localization Algorithm

Amorphous algorithm is similar to DV-Hop algorithm, and the idea is to calculate the hop distance between two nodes instead of the linear distance between them. Amorphous algorithm is composed of the following three steps [8].


### 2.1. Calculate the Minimum Hop from the Unknown Node to the Beacon Node

Every beacon node sends messages to the unknown nodes by flooding method. Formula (1) is used to calculate the minimum hop from the node i to k:(1)Si,k=∑j∈nbrsihj,k+hi,knbrsi+1-0.5,where S(i,k) is the minimum hop from the unknown node i to the beacon node k; h(j,k) is the integer hop from the unknown node j to the beacon node k; h(i,k) is the integer hop from the unknown node i to the beacon node k; nbrs(i) are the neighbor nodes around the unknown node i; |nbrs(i)| is the number of the neighbor nodes around the unknown node i.


### 2.2. Calculate the Distance from the Unknown Node to the Beacon Node

Formula (2) is used to calculate the average distance of one hop:(2)HopSize=r1+e-nlocal-∫-11e-nlocal/πarcos⁡t-t1-t2dt,where r is the wireless range of the node and nlocal is the average connectivity of the network.The distanced from the unknown node to the beacon node can be calculated on the basis of the average distance of one hop and the minimum hop from the unknown node to the beacon node. It can be expressed by the following formula:(3)d=HopSizei×Si,k.


### 2.3. Adopt the Least Squares Method to Locate

When the estimated distances from the unknown node to three or more than three beacon nodes have been obtained, the location of the unknown node can be calculated. It is shown as(4)x1-x2+y1-y2=d12⋮xn-x2+yn-y2=dn2.The above formula will be solved by the least squares method; the location of the unknown node can be obtained:(5)X=ATA-1ATb,where (x1,y1),(x2,y2),(x3,y3),…,(xn,yn) are the coordinates of n beacon nodes, (x,y) is the coordinates of the unknown node, and d1,d2,d3,…,dn are the distances from the unknown node to the beacon nodes:(6)A=2x1-xn2y1-yn⋮⋮2xn-1-xn2yn-1-yn,b=x12-xn2+y12-yn2+dn2-d12⋮xn-12-xn2+yn-12-yn2+dn2-dn-12.The location of the unknown node can be calculated on the basis of (5) and (6).


## 2.1. Calculate the Minimum Hop from the Unknown Node to the Beacon Node

Every beacon node sends messages to the unknown nodes by flooding method. Formula (1) is used to calculate the minimum hop from the node i to k:(1)Si,k=∑j∈nbrsihj,k+hi,knbrsi+1-0.5,where S(i,k) is the minimum hop from the unknown node i to the beacon node k; h(j,k) is the integer hop from the unknown node j to the beacon node k; h(i,k) is the integer hop from the unknown node i to the beacon node k; nbrs(i) are the neighbor nodes around the unknown node i; |nbrs(i)| is the number of the neighbor nodes around the unknown node i.


## 2.2. Calculate the Distance from the Unknown Node to the Beacon Node

Formula (2) is used to calculate the average distance of one hop:(2)HopSize=r1+e-nlocal-∫-11e-nlocal/πarcos⁡t-t1-t2dt,where r is the wireless range of the node and nlocal is the average connectivity of the network.The distanced from the unknown node to the beacon node can be calculated on the basis of the average distance of one hop and the minimum hop from the unknown node to the beacon node. It can be expressed by the following formula:(3)d=HopSizei×Si,k.


## 2.3. Adopt the Least Squares Method to Locate

When the estimated distances from the unknown node to three or more than three beacon nodes have been obtained, the location of the unknown node can be calculated. It is shown as(4)x1-x2+y1-y2=d12⋮xn-x2+yn-y2=dn2.The above formula will be solved by the least squares method; the location of the unknown node can be obtained:(5)X=ATA-1ATb,where (x1,y1),(x2,y2),(x3,y3),…,(xn,yn) are the coordinates of n beacon nodes, (x,y) is the coordinates of the unknown node, and d1,d2,d3,…,dn are the distances from the unknown node to the beacon nodes:(6)A=2x1-xn2y1-yn⋮⋮2xn-1-xn2yn-1-yn,b=x12-xn2+y12-yn2+dn2-d12⋮xn-12-xn2+yn-12-yn2+dn2-dn-12.The location of the unknown node can be calculated on the basis of (5) and (6).


## 3. The Improved Amorphous Algorithm Based on BP Artificial Neural Network

Because the disadvantages of the classical Amorphous algorithm will produce large localization error in the process of localization, an improved localization algorithm is proposed in this paper to solve the problem. The improved algorithm introduces the received signal strength threshold to modify the minimum hop from the unknown node to the beacon node. Then, BP algorithm is introduced to optimize the threshold and reduce the localization error. The improved algorithm is composed of the following two parts. Sections3.1 and 3.2 describe the two parts, respectively.The flow chart of the improved algorithm is shown in Figure1.Figure 1
The flow chart of the improved algorithm.


### 3.1. The Choice of the Hop

In the classical Amorphous localization algorithm, there exists large deviation when calculating the distanced. As shown in Figure 2, nodes A and B are both in the wireless range of node O. As a result, the hops of them are set as one, while the disparity of |OA| and |OB| is huge [9]. This is a common problem existing in the real network. So the hops between two nodes cannot reflect the distance between them exactly. Then, an improved method is proposed to solve the problem in the classical algorithm. The signal strength analysis module is added to the sensor node, and the initial threshold is set as M, which is the signal strength when the transmission distance is R/2. The signal strength and the distance between two nodes are usually inversely proportional. So the hop is set as 0.5 if the received signal strength is above the threshold M; otherwise the hop is set as 1.Figure 2
Principle diagram of hops correction.Therefore,(7)hi,k=1,rssii,k≤M0.5,rssii,k>M,where rssi(i,k) is the signal strength which the unknown node i receives from the beacon node k and h(i,k) is the hop from the unknown node i to the beacon node k.


### 3.2. BP Algorithm Will Be Introduced to Optimize the Threshold to Reduce the Localization Error

The received signal strength threshold has been set to modify the minimum hop. How many the threshold should be set to minimize the localization error? In order to solve the problem, the BP neural network is introduced to optimize the threshold and reduce the localization error.BP neural network is one of the most widely used models in neural networks. BP algorithm is a neural network of three-tier or more structure. This method with the Error Minimum Principle and using recursive method to find the network weight and threshold of each node among BP algorithms is called deepest gradient descent. The advantages of BP artificial neural network in error optimization are formidable self-organizing and self-learning capacity, error back-propagation, and error minimum principle [7, 10]. A three-layer BP neural network is constructed in this paper (see Figure 3) and operated on the sensor nodes. Steps of the proposed algorithm are as follows.Figure 3
Neural network model.Step 1.
Firstly, the BP neural network is operated on the sensor nodes and trained by the data of beacon nodes.Step 2.
The received signal strength thresholdM and the signal strength (rssi(i,m),rssi(i,n),rssi(i,r)) which the unknown node i receives from three beacon nodes are two units of the input layer. The estimated distances (dm,dn,dr) from the unknown node i to three beacon nodes are the output layer [11].Step 3.
Calculate the input and output of each unit in the network.
The inputnet1 of hidden layer (8)net1=M=whi1M,where whi(1) is the weight from unit i to unit h.
The outputf1(net1) of hidden layer(9)f1net1=hi,k=1,rssii,k≤net10.5,rssii,k>net1.The input net2 of output layer (10)net2=∑j∈nbrsiwkh2hj,k+hi,k,where wkh(2) is the weight from unit h to unit k.
The outputf2(net2) of output layer (11)f2net2=d=net2nbrsi+1×HopSizei,where d is the distance from the unknown node to the beacon node.Step 4.
Calculate the errorδ output unit k:(12)δk=∑k=1mtk-dkf′2net2hidden unit h. Consider(13)δh=f′1net1∑k=1mtk-dkf′2net2wkh2,where tk is the desired output and dk is the actual output.Step 5.
Update each weightw output unit k:(14)wkh2=wkh2+ηδkf1net1and hidden unit h(15)whi1=whi1+ηδhM,where η is the learning rate, i is the input, and k is the output.
Thus,M=whi(1)M; update the threshold M until it obtains an appropriate value.Step 6.
This training process is carried out continuously until the network error is reduced to an acceptable level or preset numbers of learning. Then, the location of the unknown node can be calculated on the basis of (5) and (6) in Section 2.


## 3.1. The Choice of the Hop

In the classical Amorphous localization algorithm, there exists large deviation when calculating the distanced. As shown in Figure 2, nodes A and B are both in the wireless range of node O. As a result, the hops of them are set as one, while the disparity of |OA| and |OB| is huge [9]. This is a common problem existing in the real network. So the hops between two nodes cannot reflect the distance between them exactly. Then, an improved method is proposed to solve the problem in the classical algorithm. The signal strength analysis module is added to the sensor node, and the initial threshold is set as M, which is the signal strength when the transmission distance is R/2. The signal strength and the distance between two nodes are usually inversely proportional. So the hop is set as 0.5 if the received signal strength is above the threshold M; otherwise the hop is set as 1.Figure 2
Principle diagram of hops correction.Therefore,(7)hi,k=1,rssii,k≤M0.5,rssii,k>M,where rssi(i,k) is the signal strength which the unknown node i receives from the beacon node k and h(i,k) is the hop from the unknown node i to the beacon node k.


## 3.2. BP Algorithm Will Be Introduced to Optimize the Threshold to Reduce the Localization Error

The received signal strength threshold has been set to modify the minimum hop. How many the threshold should be set to minimize the localization error? In order to solve the problem, the BP neural network is introduced to optimize the threshold and reduce the localization error.BP neural network is one of the most widely used models in neural networks. BP algorithm is a neural network of three-tier or more structure. This method with the Error Minimum Principle and using recursive method to find the network weight and threshold of each node among BP algorithms is called deepest gradient descent. The advantages of BP artificial neural network in error optimization are formidable self-organizing and self-learning capacity, error back-propagation, and error minimum principle [7, 10]. A three-layer BP neural network is constructed in this paper (see Figure 3) and operated on the sensor nodes. Steps of the proposed algorithm are as follows.Figure 3
Neural network model.Step 1.
Firstly, the BP neural network is operated on the sensor nodes and trained by the data of beacon nodes.Step 2.
The received signal strength thresholdM and the signal strength (rssi(i,m),rssi(i,n),rssi(i,r)) which the unknown node i receives from three beacon nodes are two units of the input layer. The estimated distances (dm,dn,dr) from the unknown node i to three beacon nodes are the output layer [11].Step 3.
Calculate the input and output of each unit in the network.
The inputnet1 of hidden layer (8)net1=M=whi1M,where whi(1) is the weight from unit i to unit h.
The outputf1(net1) of hidden layer(9)f1net1=hi,k=1,rssii,k≤net10.5,rssii,k>net1.The input net2 of output layer (10)net2=∑j∈nbrsiwkh2hj,k+hi,k,where wkh(2) is the weight from unit h to unit k.
The outputf2(net2) of output layer (11)f2net2=d=net2nbrsi+1×HopSizei,where d is the distance from the unknown node to the beacon node.Step 4.
Calculate the errorδ output unit k:(12)δk=∑k=1mtk-dkf′2net2hidden unit h. Consider(13)δh=f′1net1∑k=1mtk-dkf′2net2wkh2,where tk is the desired output and dk is the actual output.Step 5.
Update each weightw output unit k:(14)wkh2=wkh2+ηδkf1net1and hidden unit h(15)whi1=whi1+ηδhM,where η is the learning rate, i is the input, and k is the output.
Thus,M=whi(1)M; update the threshold M until it obtains an appropriate value.Step 6.
This training process is carried out continuously until the network error is reduced to an acceptable level or preset numbers of learning. Then, the location of the unknown node can be calculated on the basis of (5) and (6) in Section 2.


## 4. Simulation and Analysis

### 4.1. The Simulation Platform and Distribution of Nodes

MATLAB simulation software can be used to verify the feasibility of the proposed algorithm. Network deployment area is 1000 m × 1000 m, the node coordinates are generated randomly, the number is 300, there are 60 beacon nodes, the proportion of beacons is 20%, the wireless range is 300 m, and communication model is Regular Model. Distribution of nodes is shown in Figure4.Figure 4
Distribution of nodes (the red star points represent the anchor nodes and the little blue circles represent the unknown nodes).


### 4.2. The Definition of Localization Error

The localization error is an extremely important indicator to evaluate the localization performance. Formula (16) is used to calculate the localization error:(16)localizationerror=x1-x22+y1-y22R,where (x1,y1)2 is the actual location of the unknown node and (x1,y1)2 is the estimated location, where R is the wireless range.


### 4.3. The Simulations of Amorphous Algorithm, VN-BP Algorithm, and Improved Algorithm

First of all, Amorphous algorithm, VN-BP algorithm, and improved algorithm can be simulated to get the localization error figure. It is shown in Figure5.Figure 5
The localization error figures: (a) Amorphous algorithm, (b) VN-BP algorithm, and (c) Improved algorithm.
(a)
(b)
(c)In Figure5, the little blue circle represents the estimated location of the unknown node and the blue line represents the localization error of the unknown node. The localization error of Amorphous algorithm is 0.23107. BP Localization Algorithm Based on Virtual Nodes (VN-BP) is proposed in [6]. In Figure 5(b), the localization error is 0.14818, the localization accuracy of VN-BP algorithm is higher than that of the original Amorphous algorithm. In Figure 5(c), the localization error of improved algorithm is 0.11958. We can see that the localization accuracy of the improved algorithm is higher than that of the original Amorphous algorithm and VN-BP algorithm obviously from the figure.


### 4.4. The Simulations of Amorphous, VN-BP, and Improved Algorithm in Different Proportions of Beacons

The localization error figures of Amorphous algorithm, VN-BP algorithm, and improved algorithm in different proportions of beacons are shown in Figure6. It is clear that the localization accuracy of the improved algorithm is superior to that of the original Amorphous algorithm and VN-BP algorithm; it improves the localization accuracy effectively. And the localization error of improved algorithm declines as the proportion of beacons increases.Figure 6
The localization error in different proportions of beacons: (a) Amorphous, (b) VN-BP, and (c) Improved algorithm.
(a)
(b)
(c)


### 4.5. The Simulations under Different Conditions Are Completed for the Five Algorithms

To find out the performance of the algorithm proposed in this paper, the simulations under different conditions are completed for Centroid, DV-HOP, Amorphous, VN-BP (which selects the unknown nodes as the subbeacons based on the virtual nodes), and the improved algorithm. All the nodes in the simulation are randomly distributed in the area 1000 m × 1000 m. Each set of the condition is run for 1000 times so as to factually reflect the localization error of different algorithms. The average value of the localization error is used for the comparison [6].In the condition of different proportions of beacons, there are 300 nodes in total with wireless range being set as 300 m. From Figure7(a), it is clear that the localization error of the five algorithms decreases as the proportion of beacons increases. Under the same proportion of beacons, the localization error of the improved algorithm decreases, respectively, about 25%, 20%, and 12% on average than that of the Centroid algorithm, DV-HOP algorithm, and Amorphous algorithm. The localization accuracy of the improved algorithm is higher than that of the VN-BP algorithm, and the localization error is reduced by about 3% on average, demonstrating the effectiveness of the improved algorithm in different proportions of beacons.Figure 7
The localization error under different conditions: (a) proportion of beacons and localization error, (b) wireless range and localization error, and (c) number of nodes and localization error.
(a)
(b)
(c)In the simulation of different wireless range, the proportion of beacons is set by 20% and the total number of nodes is set by 300. Figure7(b) shows the result of the simulation. It is clear that the localization error of the improved algorithm and VN-BP algorithm decreases as the wireless range increases. In the same condition, the localization error of the improved algorithm decreases, respectively, about 17% and 18% on average than that of the Centroid algorithm and DV-HOP algorithm. The localization error of the Amorphous algorithm increases when wireless range is more than 300 m. And the improved algorithm overcomes the problem. The localization accuracy of the improved algorithm is higher than that of the VN-BP algorithm, and the localization error is reduced by about 3% on average, reflecting the effectiveness of the improved algorithm in different wireless range.Based on different numbers of nodes, wireless range is set as 300 m, and the proportion of beacons is set as 20%. The result is shown in Figure7(c). It is clear that the localization error of the 5 algorithms decreases as the number of nodes increases. In the same number of nodes, the localization error of the improved algorithm decreases, respectively, about 23%, 22%, and 15% on average than that of the Centroid algorithm, DV-HOP algorithm, and Amorphous algorithm. The localization accuracy of the improved algorithm is higher than that of the VN-BP algorithm, and the localization error is reduced by about 3.5% on average, showing the effectiveness of the improved algorithm in different numbers of nodes.


### 4.6. The Computing Time of Improved Algorithm Is Compared with Other Algorithms

According to the analysis of the paper [12], computational costs make up only a small part of all energy consumption in WSN; most of the energy consumption is communication. So decreasing the energy consumption of communication is the key to extend the lifecycle of network. In order to decrease the energy consumption of communication, all nodes cannot send the information to a central node to calculate their location, because the energy consumption of communication is too large. The improved localization algorithm should adopt distributed computation, and the neural network is constructed and operated on the sensor nodes. Table 1 compares the average computing time needed by the five algorithms to localize a single node and localization error.Table 1
Average computing time to localize single node and localization error.
Computing time (s)
Localization error
Centroid
0.383
0.29858
DV-HOP
0.512
0.30776
Amorphous
0.536
0.23107
VN-BP
0.859
0.14818
Improved algorithm
0.772
0.11958All experiments are conducted on the same computer. Network deployment area is 1000 m × 1000 m, the node coordinates are generated randomly, the number is 300, the proportion of beacons is 20%, the wireless range is 300 m, and communication model is Regular Model. Due to the simple calculation, Centroid algorithm generally requires less computing time than the other four algorithms. Amorphous algorithm is similar to DV-Hop algorithm. VN-BP algorithm and improved algorithm require more computing time because of the neural network model construction. In addition, VN-BP algorithm takes much time to find virtual nodes. The algorithms need more computing time as the localization error decreases. This is an unavoidable problem. But the improved algorithm decreases the energy consumption of communication and greatly improves localization accuracy; the total energy consumption increases a little bit. The results will be described in Section4.7.


### 4.7. The Energy Consumption of Improved Algorithm Is Compared with Other Algorithms

To find out the performance of the algorithm proposed in this paper, the simulations of energy consumption under different conditions are completed for Centroid, DV-HOP, Amorphous, VN-BP, and the improved algorithm. All the nodes in the simulation are randomly distributed in the area 1000 m × 1000 m. Each set of the condition is run for 1000 times so as to factually reflect the energy consumption of different algorithms.In the condition of different proportions of beacons, there are 300 nodes in total with wireless range being set as 300 m. The result of energy consumption is shown in Figure8(a). It is clear that energy consumption of the five algorithms increases as the proportion of the beacons increases. Under the same proportion of beacons, the energy consumption of Centroid algorithm is lowest, because it broadcasts only once. DV-hop algorithm needs to broadcast twice, so the energy consumption of communication is large [13]. The energy consumption of improved algorithm and that of classical Amorphous algorithm are almost the same. They all adopt distributed computation, so the energy consumption of communication is decreased. But the improved algorithm takes some time to construct the neural network; energy consumption increases a little bit. A little increase of energy consumption can be ignored considering that the improved algorithm greatly improves localization accuracy. Moreover, the energy consumption of improved algorithm is lower than that of VN-BP algorithm. This reflects the effectiveness of the improved algorithm in energy consumption.Figure 8
Energy consumption under different conditions: (a) energy consumption on different proportions of beacons, (b) energy consumption on different wireless range, and (c) energy consumption on different numbers of nodes.
(a)
(b)
(c)In the case of different wireless range, there are 300 nodes in total with proportion of beacons being set as 20%, and in the case of different numbers of nodes, wireless range is set as 300 m, the proportion of beacons is set as 20%. The similar result can be got in Figures8(b) and 8(c). It is certain that accurate localization will bring more energy consumption. So localization algorithm should be designed according to different applications.


## 4.1. The Simulation Platform and Distribution of Nodes

MATLAB simulation software can be used to verify the feasibility of the proposed algorithm. Network deployment area is 1000 m × 1000 m, the node coordinates are generated randomly, the number is 300, there are 60 beacon nodes, the proportion of beacons is 20%, the wireless range is 300 m, and communication model is Regular Model. Distribution of nodes is shown in Figure4.Figure 4
Distribution of nodes (the red star points represent the anchor nodes and the little blue circles represent the unknown nodes).


## 4.2. The Definition of Localization Error

The localization error is an extremely important indicator to evaluate the localization performance. Formula (16) is used to calculate the localization error:(16)localizationerror=x1-x22+y1-y22R,where (x1,y1)2 is the actual location of the unknown node and (x1,y1)2 is the estimated location, where R is the wireless range.


## 4.3. The Simulations of Amorphous Algorithm, VN-BP Algorithm, and Improved Algorithm

First of all, Amorphous algorithm, VN-BP algorithm, and improved algorithm can be simulated to get the localization error figure. It is shown in Figure5.Figure 5
The localization error figures: (a) Amorphous algorithm, (b) VN-BP algorithm, and (c) Improved algorithm.
(a)
(b)
(c)In Figure5, the little blue circle represents the estimated location of the unknown node and the blue line represents the localization error of the unknown node. The localization error of Amorphous algorithm is 0.23107. BP Localization Algorithm Based on Virtual Nodes (VN-BP) is proposed in [6]. In Figure 5(b), the localization error is 0.14818, the localization accuracy of VN-BP algorithm is higher than that of the original Amorphous algorithm. In Figure 5(c), the localization error of improved algorithm is 0.11958. We can see that the localization accuracy of the improved algorithm is higher than that of the original Amorphous algorithm and VN-BP algorithm obviously from the figure.


## 4.4. The Simulations of Amorphous, VN-BP, and Improved Algorithm in Different Proportions of Beacons

The localization error figures of Amorphous algorithm, VN-BP algorithm, and improved algorithm in different proportions of beacons are shown in Figure6. It is clear that the localization accuracy of the improved algorithm is superior to that of the original Amorphous algorithm and VN-BP algorithm; it improves the localization accuracy effectively. And the localization error of improved algorithm declines as the proportion of beacons increases.Figure 6
The localization error in different proportions of beacons: (a) Amorphous, (b) VN-BP, and (c) Improved algorithm.
(a)
(b)
(c)


## 4.5. The Simulations under Different Conditions Are Completed for the Five Algorithms

To find out the performance of the algorithm proposed in this paper, the simulations under different conditions are completed for Centroid, DV-HOP, Amorphous, VN-BP (which selects the unknown nodes as the subbeacons based on the virtual nodes), and the improved algorithm. All the nodes in the simulation are randomly distributed in the area 1000 m × 1000 m. Each set of the condition is run for 1000 times so as to factually reflect the localization error of different algorithms. The average value of the localization error is used for the comparison [6].In the condition of different proportions of beacons, there are 300 nodes in total with wireless range being set as 300 m. From Figure7(a), it is clear that the localization error of the five algorithms decreases as the proportion of beacons increases. Under the same proportion of beacons, the localization error of the improved algorithm decreases, respectively, about 25%, 20%, and 12% on average than that of the Centroid algorithm, DV-HOP algorithm, and Amorphous algorithm. The localization accuracy of the improved algorithm is higher than that of the VN-BP algorithm, and the localization error is reduced by about 3% on average, demonstrating the effectiveness of the improved algorithm in different proportions of beacons.Figure 7
The localization error under different conditions: (a) proportion of beacons and localization error, (b) wireless range and localization error, and (c) number of nodes and localization error.
(a)
(b)
(c)In the simulation of different wireless range, the proportion of beacons is set by 20% and the total number of nodes is set by 300. Figure7(b) shows the result of the simulation. It is clear that the localization error of the improved algorithm and VN-BP algorithm decreases as the wireless range increases. In the same condition, the localization error of the improved algorithm decreases, respectively, about 17% and 18% on average than that of the Centroid algorithm and DV-HOP algorithm. The localization error of the Amorphous algorithm increases when wireless range is more than 300 m. And the improved algorithm overcomes the problem. The localization accuracy of the improved algorithm is higher than that of the VN-BP algorithm, and the localization error is reduced by about 3% on average, reflecting the effectiveness of the improved algorithm in different wireless range.Based on different numbers of nodes, wireless range is set as 300 m, and the proportion of beacons is set as 20%. The result is shown in Figure7(c). It is clear that the localization error of the 5 algorithms decreases as the number of nodes increases. In the same number of nodes, the localization error of the improved algorithm decreases, respectively, about 23%, 22%, and 15% on average than that of the Centroid algorithm, DV-HOP algorithm, and Amorphous algorithm. The localization accuracy of the improved algorithm is higher than that of the VN-BP algorithm, and the localization error is reduced by about 3.5% on average, showing the effectiveness of the improved algorithm in different numbers of nodes.


## 4.6. The Computing Time of Improved Algorithm Is Compared with Other Algorithms

According to the analysis of the paper [12], computational costs make up only a small part of all energy consumption in WSN; most of the energy consumption is communication. So decreasing the energy consumption of communication is the key to extend the lifecycle of network. In order to decrease the energy consumption of communication, all nodes cannot send the information to a central node to calculate their location, because the energy consumption of communication is too large. The improved localization algorithm should adopt distributed computation, and the neural network is constructed and operated on the sensor nodes. Table 1 compares the average computing time needed by the five algorithms to localize a single node and localization error.Table 1
Average computing time to localize single node and localization error.
Computing time (s)
Localization error
Centroid
0.383
0.29858
DV-HOP
0.512
0.30776
Amorphous
0.536
0.23107
VN-BP
0.859
0.14818
Improved algorithm
0.772
0.11958All experiments are conducted on the same computer. Network deployment area is 1000 m × 1000 m, the node coordinates are generated randomly, the number is 300, the proportion of beacons is 20%, the wireless range is 300 m, and communication model is Regular Model. Due to the simple calculation, Centroid algorithm generally requires less computing time than the other four algorithms. Amorphous algorithm is similar to DV-Hop algorithm. VN-BP algorithm and improved algorithm require more computing time because of the neural network model construction. In addition, VN-BP algorithm takes much time to find virtual nodes. The algorithms need more computing time as the localization error decreases. This is an unavoidable problem. But the improved algorithm decreases the energy consumption of communication and greatly improves localization accuracy; the total energy consumption increases a little bit. The results will be described in Section4.7.


## 4.7. The Energy Consumption of Improved Algorithm Is Compared with Other Algorithms

To find out the performance of the algorithm proposed in this paper, the simulations of energy consumption under different conditions are completed for Centroid, DV-HOP, Amorphous, VN-BP, and the improved algorithm. All the nodes in the simulation are randomly distributed in the area 1000 m × 1000 m. Each set of the condition is run for 1000 times so as to factually reflect the energy consumption of different algorithms.In the condition of different proportions of beacons, there are 300 nodes in total with wireless range being set as 300 m. The result of energy consumption is shown in Figure8(a). It is clear that energy consumption of the five algorithms increases as the proportion of the beacons increases. Under the same proportion of beacons, the energy consumption of Centroid algorithm is lowest, because it broadcasts only once. DV-hop algorithm needs to broadcast twice, so the energy consumption of communication is large [13]. The energy consumption of improved algorithm and that of classical Amorphous algorithm are almost the same. They all adopt distributed computation, so the energy consumption of communication is decreased. But the improved algorithm takes some time to construct the neural network; energy consumption increases a little bit. A little increase of energy consumption can be ignored considering that the improved algorithm greatly improves localization accuracy. Moreover, the energy consumption of improved algorithm is lower than that of VN-BP algorithm. This reflects the effectiveness of the improved algorithm in energy consumption.Figure 8
Energy consumption under different conditions: (a) energy consumption on different proportions of beacons, (b) energy consumption on different wireless range, and (c) energy consumption on different numbers of nodes.
(a)
(b)
(c)In the case of different wireless range, there are 300 nodes in total with proportion of beacons being set as 20%, and in the case of different numbers of nodes, wireless range is set as 300 m, the proportion of beacons is set as 20%. The similar result can be got in Figures8(b) and 8(c). It is certain that accurate localization will bring more energy consumption. So localization algorithm should be designed according to different applications.


## 5. Conclusions

The localization accuracy is an extremely important indicator to evaluate the localization performance. The higher the localization accuracy is, the better the localization performance is. Because the disadvantages of the classical Amorphous algorithm will produce large localization error in the process of localization, an improved localization algorithm is proposed in this paper to solve the problem. The improved algorithm introduces the received signal strength threshold to modify the minimum hop from the unknown node to the beacon node. Then, BP algorithm is introduced to optimize the threshold and reduce the localization error. Simulation results show that the improved algorithm overcomes the error stack effect of traditional Amorphous algorithm in the case of multiple hops and greatly improves localization accuracy. In addition, the localization accuracy of improved algorithm is higher than that of other algorithms and the energy consumption does not increase too much. Therefore, it is suitable for the actual large-scale network node localization.



---

*Source: 657241-2015-07-07.xml*