# A Distance-Based Maximum Likelihood Estimation Method for Sensor Localization in Wireless Sensor Networks

Authors: Jing Xu; Jingsha He; Yuqiang Zhang; Fei Xu; Fangbo Cai
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Node localization is an important supporting technology in wireless sensor networks (WSNs). Traditional maximum likelihood estimation based localization methods (MLE) assume that measurement errors are independent of the distance between the anchor node and a target node. However, such an assumption may not reflect the physical characteristics of existing measurement techniques, such as the widely used received signal strength indicator. To address this issue, we propose a distance-based MLE that considers measurement errors that depend on distance values in this paper. The proposed distance-based MLE is formulated as a complicated nonlinear optimization problem. An exact solution is developed based on first-order optimal condition to improve the efficiency of search. In addition, a two-dimensional search method is also presented. Simulation experiments are performed to demonstrate the effectiveness of this localization. The simulation results show that the distance-based localization method has better localization accuracy compared to other range-based localization methods.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are self-organizing networks. In most applications, wireless sensor nodes in a WSN are randomly deployed. Thus, the location information of nodes is essential for WSNs [1]. However, due to energy constraints of the nodes, regular sensor nodes or unknown nodes cannot locate their own positions directly. These nodes have to rely on some external nodes that are often referred to as the anchor nodes to help them accomplish the task of determining their locations. Localization of wireless sensor nodes has become a hot research issue in recent years.Anchor nodes in WSNs are usually equipped with GPS modules and can thus obtain their own locations through corresponding localization functions. Unknown nodes, on the other hand, derive their location information with the help of the anchor nodes [2]. More specifically, the unknown nodes would calculate their own locations through communication with the anchor nodes based on a localization algorithm although there are some applications in which the unknown nodes may not have to rely on the anchor nodes for coarse localization [3].Localization methods can be divided into range-based and range-free methods [4]. Range-based location methods generally measure the absolute distance or azimuth information between an anchor node and an unknown node as the basis for the calculation of the location of the unknown node [5]. Range-free localization methods do not need to measure the absolute distance or azimuth information. Rather, they estimate the distance between nodes based on the internode connectivity, the plurality of routing information exchange, and the overlapping areas [6]. Although range-free location methods have lower requirements for hardware and power consumption, the accuracy of localization is generally lower than that of the range-based methods [7, 8]. In this paper, we employ an approach that follows the range-based methods.Range-based localization methods have relatively higher localization accuracy. In such a method, one or more distance measurement techniques are used to estimate the localization of the unknown nodes [9]. Existing techniques for distance measurement include received signal strength indicator (RSSI) [10], time of arrival (TOA) [11], time difference of arrival (TDOA) [12], and angle of arrival (AOA) [13].Range-based techniques based on RSSI rely on the principle that the radio signal is attenuated regularly as the distance increases [14]. Such techniques use the attenuation degree of received signals to estimate the distance between the anchor node and the unknown target node without requiring any additional hardware and data exchange. The cost of implementation is low and can thus be realized easily [15]. Therefore, such techniques have become the most commonly used techniques for localization of wireless sensor nodes in WSNs. Based on the general principle of RSSI, most traditional maximum likelihood estimation (MLE) localization methods assume that measurement errors are independent of the distance between the anchor node and the unknown target node and thus calculate the position of the unknown target node by solving a convex optimization problem. However, the assumption may contradict with the physical characteristics of RSSI.To address this issue, we propose a distance-based MLE in which we take into consideration measurement errors that vary with the distance. The proposed distance-based MLE is then formulated as a complicated nonlinear optimization problem. To solve this optimization problem, two solutions will be presented. The first one is based on the first-order optimal condition and the second is based on a two-dimensional search. Simulation experiments will also be performed to demonstrate the effectiveness of our proposed localization methods. The simulation results show that our distance-based localization methods have better localization accuracy compared to other range-based localization methods.The rest of this paper is organized as follows. In Section2, we review some related work on sensor localization. In Section 3, we present a model in which a mobile anchor node is introduced into sensor localization to help further reduce energy consumption of regular sensor nodes for localization. In Section 4, we present our proposed methods. In Section 5, we conduct some experiments to evaluate the proposed methods and to demonstrate the advantages of our methods through comparison analysis. Finally, in Section 6, we conclude this paper.


## 2. Review of Existing Work

Suppose, in a two-dimensional space, there areN anchor nodes P
i
=
(
x
i
,
y
i
)
,
i
=
1,2
,
…
,
N
(
N
≥
3
), and an unknown node P
=
(
x
,
y
). Based on the communication between anchor nodes and the unknown node, N values on the distance can be obtained which are expressed as r
i
,
i
=
1,2
,
…
,
N. Note that the obtained distance values include measurement errors due to various noises during the measurement. Based on the obtained distance values, the position of the unknown node P
=
(
x
,
y
) can be calculated. In particular, when N
=
3, this method becomes the widely used trilateration method.In the following subsections, we will briefly review two commonly used range-based localization methods: the traditional range-based multilateral measurement localization method and the maximum likelihood estimation method.


### 2.1. Range-Based Multilateral Measurement Based Methods

The range-based multilateral measurement localization method (RB-MML) is commonly used for node localization in WSNs. If there is no measurement noise, the positions of the unknown node and the anchor nodes satisfy the following equations [16]. Thus, to obtain the position of the unknown node, we need to solve the following equations:(1)
x
1
-
x
2
+
y
1
-
y
2
=
r
1
2
,
x
2
-
x
2
+
y
2
-
y
2
=
r
2
2
,
⋮
x
N
-
x
2
+
y
N
-
y
2
=
r
N
2
.From the above equation system, we can get the following solution:(2)
X
=
A
T
A
-
1
A
T
B
,where(3)
A
=
2
x
1
-
x
i
2
y
1
-
y
i
⋮
⋮
2
x
i
-
1
-
x
i
2
y
i
-
1
-
y
i
,
B
=
x
1
2
-
x
i
2
+
y
1
2
-
y
i
2
+
r
i
2
-
r
1
2
⋮
x
i
-
1
2
-
x
i
2
+
y
i
-
1
2
-
y
i
2
+
r
i
2
-
r
i
-
1
2
,
X
=
x
y
.It should be noted that traditional range-based multilateral measurement localization methods ignore the effect of measure noises, affecting the accuracy of localization. Thus, methods that consider the effect of measure noises should be investigated such as the maximum likelihood estimation method.


### 2.2. Maximum Likelihood Estimation Based Methods

Maximum likelihood estimation (MLE) methods suggest that the measured distanceR
i between anchor node P
i and unknown node P is a random variable subject to Gaussian normal distribution N
μ
i
,
σ
2, where μ
i is the true distance between anchor node P
i and unknown node P and σ
2 is a fixed constant. MLE further assumes that different measurement distances by different anchor nodes and the unknown node are independent from one another. Let the sample value of the measurement distance R
i be r
i
,
i
=
1,2
,
…
,
N.Recall that the probability density functions ofR
i are f
i
t
=
1
/
2
π
σ
e
-
t
-
μ
i
2
/
2
σ
2. Then, MLE first establishes the likelihood function as follows:(4)
L
x
,
y
=
∏
i
=
1
n
f
i
r
i
=
∏
i
=
1
n
1
2
π
σ
e
-
r
i
-
μ
i
2
/
2
σ
2
=
1
2
π
σ
n
e
-
1
/
2
σ
2
∑
i
=
1
n
r
i
-
μ
i
2
,where μ
i
=
(
x
i
-
x
)
2
+
y
i
-
y
2, which is equivalent to solving the following equations: (5)
∑
i
=
1
n
x
i
-
x
μ
i
-
r
i
μ
i
=
0
,
∑
i
=
1
n
y
i
-
y
μ
i
-
r
i
μ
i
=
0
.By solving the above equations, we can obtain the maximum likelihood estimation value for the unknown node. This method improves the accuracy of localization compared to range-based multilateral measurement localization methods.


## 2.1. Range-Based Multilateral Measurement Based Methods

The range-based multilateral measurement localization method (RB-MML) is commonly used for node localization in WSNs. If there is no measurement noise, the positions of the unknown node and the anchor nodes satisfy the following equations [16]. Thus, to obtain the position of the unknown node, we need to solve the following equations:(1)
x
1
-
x
2
+
y
1
-
y
2
=
r
1
2
,
x
2
-
x
2
+
y
2
-
y
2
=
r
2
2
,
⋮
x
N
-
x
2
+
y
N
-
y
2
=
r
N
2
.From the above equation system, we can get the following solution:(2)
X
=
A
T
A
-
1
A
T
B
,where(3)
A
=
2
x
1
-
x
i
2
y
1
-
y
i
⋮
⋮
2
x
i
-
1
-
x
i
2
y
i
-
1
-
y
i
,
B
=
x
1
2
-
x
i
2
+
y
1
2
-
y
i
2
+
r
i
2
-
r
1
2
⋮
x
i
-
1
2
-
x
i
2
+
y
i
-
1
2
-
y
i
2
+
r
i
2
-
r
i
-
1
2
,
X
=
x
y
.It should be noted that traditional range-based multilateral measurement localization methods ignore the effect of measure noises, affecting the accuracy of localization. Thus, methods that consider the effect of measure noises should be investigated such as the maximum likelihood estimation method.


## 2.2. Maximum Likelihood Estimation Based Methods

Maximum likelihood estimation (MLE) methods suggest that the measured distanceR
i between anchor node P
i and unknown node P is a random variable subject to Gaussian normal distribution N
μ
i
,
σ
2, where μ
i is the true distance between anchor node P
i and unknown node P and σ
2 is a fixed constant. MLE further assumes that different measurement distances by different anchor nodes and the unknown node are independent from one another. Let the sample value of the measurement distance R
i be r
i
,
i
=
1,2
,
…
,
N.Recall that the probability density functions ofR
i are f
i
t
=
1
/
2
π
σ
e
-
t
-
μ
i
2
/
2
σ
2. Then, MLE first establishes the likelihood function as follows:(4)
L
x
,
y
=
∏
i
=
1
n
f
i
r
i
=
∏
i
=
1
n
1
2
π
σ
e
-
r
i
-
μ
i
2
/
2
σ
2
=
1
2
π
σ
n
e
-
1
/
2
σ
2
∑
i
=
1
n
r
i
-
μ
i
2
,where μ
i
=
(
x
i
-
x
)
2
+
y
i
-
y
2, which is equivalent to solving the following equations: (5)
∑
i
=
1
n
x
i
-
x
μ
i
-
r
i
μ
i
=
0
,
∑
i
=
1
n
y
i
-
y
μ
i
-
r
i
μ
i
=
0
.By solving the above equations, we can obtain the maximum likelihood estimation value for the unknown node. This method improves the accuracy of localization compared to range-based multilateral measurement localization methods.


## 3. Mobile Anchor Node Localization Model

Boukerche et al. proposed the LTS-MB model to locate unknown nodes using a single mobile anchor node [17] in which the mobile anchor node is assumed to have unlimited energy supply. In this model, the mobile anchor node moves along a prespecified path in the deployment area of the sensor nodes and broadcasts its position information to unknown nodes along the way. After receiving the position information from the mobile anchor node, an unknown node would use the RSSI based location method to calculate its own position.To reduce the energy consumption of unknown nodes, especially that resulting from location computation, we improve the LTS-MB model in our proposed method. First, during communication, after receiving the position information from the mobile anchor node, the unknown node only returns a confirmation message and never calculates its own position. The calculation of the position of the unknown node is performed by the mobile anchor node, which has sufficient energy and computation power. Therefore, the energy consumption of unknown nodes is further reduced in our model. Second, we improve the localization method based on RSSI and propose an improved distance-based maximum likelihood estimation (DB-MLE) localization method. In this method, a distance influence factor is introduced to reflect the influence of ranging errors on the location values. Our proposed method is suitable for applications where the requirement on the accuracy of positions is very high. To make our method suitable for applications that require quick response, we further design a quick local search method in the calculation of the position of the unknown nodes.


## 4. The Proposed DB-MLE Method

Traditional MLE methods can improve the accuracy of range-based localization to a certain extent. However, they fail to consider the effect of measurement errors on the measured distances. Here, we propose an improved distance-based maximum likelihood estimation (DB-MLE) localization method in which we consider measurement errors that depend on distance values. Specifically, DB-MLE assumes that measurement error will increase as the distance between the anchor node and the unknown node increases. Based on this assumption, DB-MLE introduces the concept of the measurement error factor which weighs the importance of different measurement values to reduce the effect of measurement errors on localization results, thus further improving the accuracy of localization.


### 4.1. Assumptions and Model

Given a mobile anchor nodeP
m
(
x
m
,
y
m
) and an unknown node P
(
x
,
y
), let us define the true distance between these two nodes as d
M
=
x
-
x
M
2
+
y
-
y
M
2. Due to measurement noises, the actual measured distance r
m is a random variable which depends on the real value d
m.Based on the ranging principle, we make the following assumptions:(1)
The measured distance is proportional to the true distance, which satisfies the following condition:(6)
r
M
=
d
M
1
+
ξ
,
where the random variableξ is the Gauss white noise that follows the normal distribution N
0
,
σ
2.
(2)
Different measurement distances among different nodes are independent of each other.With the above assumptions, the joint probability density function is as follows:(7)
f
r
1
,
…
,
r
N
=
∏
i
=
1
N
1
2
π
σ
d
i
exp
⁡
-
r
i
-
d
i
2
2
σ
2
d
i
2
,where the measurement distance between anchor nodes P
i
=
(
x
i
,
y
i
) and unknown node P
(
x
,
y
) is d
i
=
x
i
-
x
2
+
y
i
-
y
2 and the marginal probability density function is(8)
f
i
r
i
=
1
2
π
σ
d
i
exp
⁡
-
r
i
-
d
i
2
2
σ
2
d
i
2
.The corresponding likelihood function becomes(9)
ln
⁡
f
r
1
,
r
2
,
…
,
r
N
=
-
∑
i
=
1
N
ln
⁡
d
i
-
∑
i
=
1
N
r
i
-
d
i
2
2
σ
2
d
i
2
-
N
ln
⁡
2
π
σ
.DR-MLE calculates the position of the unknown node by maximizing the above objective function. Due to its nonconvexity, we propose two different methods to solve this problem.


### 4.2. The First-Order Optimality Method

Note that solving DR-MLE is equivalent to minimizing the following objective function:(10)
f
x
,
y
=
ln
⁡
x
-
a
2
+
y
-
b
2
+
r
-
x
-
a
2
+
y
-
b
2
2
2
σ
2
x
-
a
2
+
y
-
b
2
.And its partial derivative is(11)
∂
f
∂
x
=
x
-
a
x
-
a
2
+
y
-
b
2
+
r
x
-
a
x
-
a
2
+
y
-
b
2
-
r
σ
2
x
-
a
2
+
y
-
b
2
2
,
∂
f
∂
y
=
y
-
b
x
-
a
2
+
y
-
b
2
+
r
y
-
b
x
-
a
2
+
y
-
b
2
-
r
σ
2
x
-
a
2
+
y
-
b
2
2
.We then propose the following method based on the first-order optimality condition.(1)
Solve the following equations. Suppose that all roots are given asx
¯
j
,
y
¯
j
j
∈
J,(12)
∑
i
=
1
N
x
-
x
i
x
-
x
i
2
+
y
-
y
i
2
+
r
x
-
x
i
x
-
x
i
2
+
y
-
y
i
2
-
r
σ
2
x
-
x
i
2
+
y
-
y
i
2
2
=
0
,
∑
i
=
1
N
y
-
y
i
x
-
x
i
2
+
y
-
y
i
2
+
r
y
-
y
i
x
-
x
i
2
+
y
-
y
i
2
-
r
σ
2
x
-
x
i
2
+
y
-
y
i
2
2
=
0
.
(2)
Calculate the objective valuef
x
¯
j
,
y
¯
j for different roots in x
¯
j
,
y
¯
j
j
∈
J. The unknown node position is then x
,
y
=
arg
min
j
∈
J
⁡
f
x
¯
j
,
y
¯
j
.


### 4.3. The Two-Dimensional Search Method

According to the characteristics of multilateral triangle localization method, we further design a two-dimensional search method. Define the position coordinate of the unknown node(
x
,
y
) as follows:(13)
x
=
∑
i
=
1
N
λ
i
x
i
,
y
=
∑
i
=
1
N
λ
i
y
i
,where ∑
i
=
1
N
λ
i
=
1 and λ
i
≥
0. To obtain the position of the unknown node, we first divide the interval [
0,1
] into a specified number of subintervals with equal length, then calculate the objective function value corresponding to different possible positions, and finally select the node with the maximal likelihood function value.In (13), λ is a unitless weight and (x
,
y) lies in a convex polygon. The coordinates of the vertices of the convex polygon are (x
i
,
y
i), that is, the coordinates of the anchor nodes. With a given λ, (x
,
y) can be determined accordingly. Figure 1 gives a geometric illustration of (13) with 5 anchor nodes and the convex pentagon defined by these nodes is P
1
P
2
P
3
P
4
P
5. As λ varies according to the constraints, the unknown node moves inside the convex pentagon. For example, if λ
1
=
1, λ
2
=
λ
3
=
λ
4
=
λ
5
=
0, the unknown node would locate at P
1; if λ
2
=
1, λ
1
=
λ
3
=
λ
4
=
λ
5
=
0, the unknown node would locate at P
2; if λ
1
=
λ
2
=
1
/
2, λ
3
=
λ
4
=
λ
5
=
0, the unknown node would locate at the midpoint of the line segment between P
1 and P
2.Figure 1
Geometric illustration of (13).


### 4.4. A Quick Local Search Method

The proposed first-order optimality and two-dimensional search methods can find the optimal location of the unknown node in our DB-MLE model. However, the computational efficiency of these methods may be low. To reduce the computation burden, we propose a quick local search method (QLSM) based on gradient descent.QLSM includes three phases: initialization, gradient descent, and optimal selection. In the initialization phase, we generateK initial solutions based on the range-based multilateral measurement localization method. Specifically, to generate the kth initial solution (
x
k
0
,
y
k
0
) where k
=
1,2
,
…
,
K, we randomly select n
k anchor node positions {
P
i
(
x
i
,
y
i
)
,
1
≤
i
≤
n
k
} where n
k
≥
3 and (
x
k
0
,
y
k
0
) is given by (4).In the gradient descent phase, we separately search for a near-optimal solution based on each initial solution. The update equation based on thekth initial solution is as follows:(14)
x
k
m
+
1
=
x
k
m
+
s
m
∂
g
x
k
m
,
y
k
m
∂
x
,
y
k
m
+
1
=
y
k
m
+
s
m
∂
g
x
k
m
,
y
k
m
∂
y
,where (
x
k
m
,
y
k
m
) is the solution in the mth iteration based on the kth initial solution, s
m is the step size in the mth iteration, and ∂
g
/
∂
x
,
∂
g
/
∂
y is the partial derivative of(15)
g
=
∑
i
=
1
N
ln
⁡
x
-
x
i
2
+
y
-
y
i
2
+
∑
i
=
1
N
r
i
-
x
-
x
i
2
+
y
-
y
i
2
2
2
σ
2
x
-
x
i
2
+
y
-
y
i
2
.The step size is chosen ass
m
=
1
/
m
+
1, where m
≥
1. We stop the iterative update when (
x
k
m
+
1
,
y
k
m
+
1
)
-
(
x
k
m
,
y
k
m
)
≤
δ where δ is a prespecified value.In the optimal selection phase, supposing that the near-optimal solutions obtained in the gradient descent phase are(
x
k
∗
,
y
k
∗
)
:
1
≤
k
≤
K, we choose the final solution as follows:(16)
x
∗
,
y
∗
=
arg
min
⁡
g
x
k
∗
,
y
k
∗
:
1
≤
k
≤
K
.


## 4.1. Assumptions and Model

Given a mobile anchor nodeP
m
(
x
m
,
y
m
) and an unknown node P
(
x
,
y
), let us define the true distance between these two nodes as d
M
=
x
-
x
M
2
+
y
-
y
M
2. Due to measurement noises, the actual measured distance r
m is a random variable which depends on the real value d
m.Based on the ranging principle, we make the following assumptions:(1)
The measured distance is proportional to the true distance, which satisfies the following condition:(6)
r
M
=
d
M
1
+
ξ
,
where the random variableξ is the Gauss white noise that follows the normal distribution N
0
,
σ
2.
(2)
Different measurement distances among different nodes are independent of each other.With the above assumptions, the joint probability density function is as follows:(7)
f
r
1
,
…
,
r
N
=
∏
i
=
1
N
1
2
π
σ
d
i
exp
⁡
-
r
i
-
d
i
2
2
σ
2
d
i
2
,where the measurement distance between anchor nodes P
i
=
(
x
i
,
y
i
) and unknown node P
(
x
,
y
) is d
i
=
x
i
-
x
2
+
y
i
-
y
2 and the marginal probability density function is(8)
f
i
r
i
=
1
2
π
σ
d
i
exp
⁡
-
r
i
-
d
i
2
2
σ
2
d
i
2
.The corresponding likelihood function becomes(9)
ln
⁡
f
r
1
,
r
2
,
…
,
r
N
=
-
∑
i
=
1
N
ln
⁡
d
i
-
∑
i
=
1
N
r
i
-
d
i
2
2
σ
2
d
i
2
-
N
ln
⁡
2
π
σ
.DR-MLE calculates the position of the unknown node by maximizing the above objective function. Due to its nonconvexity, we propose two different methods to solve this problem.


## 4.2. The First-Order Optimality Method

Note that solving DR-MLE is equivalent to minimizing the following objective function:(10)
f
x
,
y
=
ln
⁡
x
-
a
2
+
y
-
b
2
+
r
-
x
-
a
2
+
y
-
b
2
2
2
σ
2
x
-
a
2
+
y
-
b
2
.And its partial derivative is(11)
∂
f
∂
x
=
x
-
a
x
-
a
2
+
y
-
b
2
+
r
x
-
a
x
-
a
2
+
y
-
b
2
-
r
σ
2
x
-
a
2
+
y
-
b
2
2
,
∂
f
∂
y
=
y
-
b
x
-
a
2
+
y
-
b
2
+
r
y
-
b
x
-
a
2
+
y
-
b
2
-
r
σ
2
x
-
a
2
+
y
-
b
2
2
.We then propose the following method based on the first-order optimality condition.(1)
Solve the following equations. Suppose that all roots are given asx
¯
j
,
y
¯
j
j
∈
J,(12)
∑
i
=
1
N
x
-
x
i
x
-
x
i
2
+
y
-
y
i
2
+
r
x
-
x
i
x
-
x
i
2
+
y
-
y
i
2
-
r
σ
2
x
-
x
i
2
+
y
-
y
i
2
2
=
0
,
∑
i
=
1
N
y
-
y
i
x
-
x
i
2
+
y
-
y
i
2
+
r
y
-
y
i
x
-
x
i
2
+
y
-
y
i
2
-
r
σ
2
x
-
x
i
2
+
y
-
y
i
2
2
=
0
.
(2)
Calculate the objective valuef
x
¯
j
,
y
¯
j for different roots in x
¯
j
,
y
¯
j
j
∈
J. The unknown node position is then x
,
y
=
arg
min
j
∈
J
⁡
f
x
¯
j
,
y
¯
j
.


## 4.3. The Two-Dimensional Search Method

According to the characteristics of multilateral triangle localization method, we further design a two-dimensional search method. Define the position coordinate of the unknown node(
x
,
y
) as follows:(13)
x
=
∑
i
=
1
N
λ
i
x
i
,
y
=
∑
i
=
1
N
λ
i
y
i
,where ∑
i
=
1
N
λ
i
=
1 and λ
i
≥
0. To obtain the position of the unknown node, we first divide the interval [
0,1
] into a specified number of subintervals with equal length, then calculate the objective function value corresponding to different possible positions, and finally select the node with the maximal likelihood function value.In (13), λ is a unitless weight and (x
,
y) lies in a convex polygon. The coordinates of the vertices of the convex polygon are (x
i
,
y
i), that is, the coordinates of the anchor nodes. With a given λ, (x
,
y) can be determined accordingly. Figure 1 gives a geometric illustration of (13) with 5 anchor nodes and the convex pentagon defined by these nodes is P
1
P
2
P
3
P
4
P
5. As λ varies according to the constraints, the unknown node moves inside the convex pentagon. For example, if λ
1
=
1, λ
2
=
λ
3
=
λ
4
=
λ
5
=
0, the unknown node would locate at P
1; if λ
2
=
1, λ
1
=
λ
3
=
λ
4
=
λ
5
=
0, the unknown node would locate at P
2; if λ
1
=
λ
2
=
1
/
2, λ
3
=
λ
4
=
λ
5
=
0, the unknown node would locate at the midpoint of the line segment between P
1 and P
2.Figure 1
Geometric illustration of (13).


## 4.4. A Quick Local Search Method

The proposed first-order optimality and two-dimensional search methods can find the optimal location of the unknown node in our DB-MLE model. However, the computational efficiency of these methods may be low. To reduce the computation burden, we propose a quick local search method (QLSM) based on gradient descent.QLSM includes three phases: initialization, gradient descent, and optimal selection. In the initialization phase, we generateK initial solutions based on the range-based multilateral measurement localization method. Specifically, to generate the kth initial solution (
x
k
0
,
y
k
0
) where k
=
1,2
,
…
,
K, we randomly select n
k anchor node positions {
P
i
(
x
i
,
y
i
)
,
1
≤
i
≤
n
k
} where n
k
≥
3 and (
x
k
0
,
y
k
0
) is given by (4).In the gradient descent phase, we separately search for a near-optimal solution based on each initial solution. The update equation based on thekth initial solution is as follows:(14)
x
k
m
+
1
=
x
k
m
+
s
m
∂
g
x
k
m
,
y
k
m
∂
x
,
y
k
m
+
1
=
y
k
m
+
s
m
∂
g
x
k
m
,
y
k
m
∂
y
,where (
x
k
m
,
y
k
m
) is the solution in the mth iteration based on the kth initial solution, s
m is the step size in the mth iteration, and ∂
g
/
∂
x
,
∂
g
/
∂
y is the partial derivative of(15)
g
=
∑
i
=
1
N
ln
⁡
x
-
x
i
2
+
y
-
y
i
2
+
∑
i
=
1
N
r
i
-
x
-
x
i
2
+
y
-
y
i
2
2
2
σ
2
x
-
x
i
2
+
y
-
y
i
2
.The step size is chosen ass
m
=
1
/
m
+
1, where m
≥
1. We stop the iterative update when (
x
k
m
+
1
,
y
k
m
+
1
)
-
(
x
k
m
,
y
k
m
)
≤
δ where δ is a prespecified value.In the optimal selection phase, supposing that the near-optimal solutions obtained in the gradient descent phase are(
x
k
∗
,
y
k
∗
)
:
1
≤
k
≤
K, we choose the final solution as follows:(16)
x
∗
,
y
∗
=
arg
min
⁡
g
x
k
∗
,
y
k
∗
:
1
≤
k
≤
K
.


## 5. Simulation Results

Using the MATLAB simulation platform, we perform some simulation experiments to evaluate the three different location methods described in this paper, RB-MML, MLE, and DB-MLE. In the experiments, we select the commonly used trilateration, that is,N
=
3, to analyze the accuracy of localization of the three methods and discuss the influence of different communication radius and different ranging error parameters on average localization error, the accuracy of localization, and other performance of the methods.Figures2–5 show the influence of the different ranging random error parameters on the precision of localization. The error parameter represents the degree that the ranging error is affected by the measured distance since the ranging error affects the precision of localization directly. In all the figures, the x-axis indicates the horizontal coordinates of the node position and the y-axis indicates the longitudinal coordinate of the node position. The four figures present the localization effects of the three different localization methods when the error parameter takes four different values; that is, σ
=
0.1,0.15,0.2,0.25. In each figure, there are four points with different colors and different shapes: of these, ◯ represents the actual position of the unknown node, + represents the estimated position by DB-MLE, and the two ∗s represent the estimated positions by MLE and by RB-MML.Figure 2
Localization effect withσ
=
0.1.Figure 3
Localization effect withσ
=
0.15.Figure 4
Localization effect withσ
=
0.2.Figure 5
Localization effect withσ
=
0.25.From the figures, we can see that whenσ
=
0.1, the localization effect is the best. Afterwards, localization error becomes bigger along with an increase in the value of σ which reaches the maximum value when σ
=
0.25. This is because a bigger error parameter would indicate that ranging error is greatly influenced by the distance of the node, resulting in a relatively lower distance measurement accuracy. However, no matter how the error parameter σ changes, we can see that + are always closer to ◯ than the two ∗s; that is, the localization effect of DB-MLE is obviously better than both MLE and RB-MML.Figure6 shows the location errors of DR-MLE, MLE, and RB-MML, respectively, as σ varies. It is easy to see that although localization error increases in all the three localization methods, in general, localization error in DR-MLE is smaller than the other two methods. That is, our proposed method improves the accuracy of location.Figure 6
Localization error of the methods asσ changes.Figure7 is the histogram of the relative localization errors of the three methods with different values of the communication radius R. As can be seen from the graph, when radius R is 15, the localization error is relatively small. But no matter how R changes, the relative error of DB-MLE localization method is always smaller than the other two methods with the second best one being MLE and the conventional range-based localization method exhibiting the biggest localization error.Figure 7
The histogram of relative error with the communication radius ofR changes.In the last experiment, we deployed 50 unknown nodes and 10 anchor nodes randomly in a rectangular area of800
∗
800 m2 and used one mobile anchor node to do 20 random trials continuously. The communication radius of both the anchor nodes and the unknown nodes is 100 meters. MLE and RB-MML use the 10-anchor node to perform localization and the DB-MLE and QLSM use the mobile anchor node to perform localization. Figure 8 shows the localization error of the four methods while Figure 9 shows the average localization error of the methods in 20 independent experiments.Figure 8
Localization error of the evaluated methods in a single instance of the experiment.Figure 9
Average localization error in 20 experiments.From Figures8 and 9, we see that the localization accuracy of DB-MLE is a little higher than that of QLSM which is a little higher than MLE and RB-MML has the biggest average error. As far as the time complexity is concerned, QLSM runs much faster than DB-MLE though.


## 6. Conclusion

In this paper, we proposed a distance-based maximum likelihood localization estimation method called DB-MLE for node localization in WSNs. Unlike the traditional range-based multilateral measurement localization method, which does not consider the effect of measurement errors, and the traditional maximum likelihood estimation method, which assumes that the measurement errors are independent of the measurement distances, the proposed DB-MLE considers measurement errors that depend on the measured distances. Such assumptions are more suitable for practical distance measurement techniques, such as RSSI.The optimization for DB-MLE leads to a complex nonconvex optimization problem. To solve the problem, we proposed two solutions based on the first-order optimality condition and the two-dimensional search. We evaluated the performance of the proposed methods through simulation experiment in which we also compared them to some existing localization methods. Simulation results showed that DB-MLE provides higher localization accuracy compared to the other methods.



---

*Source: 2080536-2016-04-14.xml*