Localization with a Mobile Beacon Based on Compressive Sensing in Wireless Sensor Networks

Abstract

Node localization technology is especially important to most applications of wireless sensor network. However, each mobile beacon needs to broadcast its current position many times, and locating all the nodes must take a long time in most of the localization algorithms. In order to solve these problems, we propose a novel range-free localization algorithm—localization with a mobile beacon based on compressive sensing (LMCS). LMCS makes use of compressive sensing (CS) to get the related degree of the sensor nodes and all the mobile beacon points. According to the related degree, the algorithm decides the weight value of each beacon point for the mass coordinate, and estimates the sensor node location. LMCS does not ask for all nodes hearing directly with beacon node, so it is more suitable for practical application than other localization algorithms. The simulation results show that compared with MAP schemes, LMCS has better localization performance, especially under irregularity of radio range and obstacle environment. Therefore, LMCS is a reliable, useful, and effective localization algorithm.

1. Introduction

With the development of technology, wireless sensor networks have been widely used for various applications, such as routing, monitoring, and tracking. A wireless sensor network is composed of a large number of cheap and energy limited sensor nodes, which are densely distributed in a field, and each sensor node can detect specific events in its sensing field. In wireless sensor networks, there are several important issues (e.g., localization, deployment, and coverage). However, localization is the most essential problem because the location information is the important premise for deployment, coverage, routing, monitoring, and tracking.

Many localization algorithms, broadly divided into two categories, have been proposed, including range-based schemes and range-free schemes. The range-based schemes are achieved by measuring the distance between two neighbor nodes [1–8]. For instance, the distance can be calculated based on the Received Signal Strength Indication (RSSI), Time of Arrival (TOA), Time Difference of Arrival (TDOA), or Angle of Arrival (AOA). The range-based location algorithms have high location precision common, but it require additional measuring equipment. Many range-free schemes have been proposed in [9–20].

Compared with the Nyquist sampling theorem, compressive sensing (CS) [21, 22] only needs fewer noisy measurements to recover the signal, which is sparse or compressible under a transform basis. CS can reconstruct exactly the original sparse signal with high probability by dealing with a minimization problem [23–25]. Many researchers [26–28] address target localization problem in WSNs using the theory of CS. In [26], a novel multiple target localization approach based on CS theory is proposed, and a preprocessing is introduced to enable the measurement matrix to meet Restricted Isometry Property (RIP) [22], so the performance can be guaranteed. In [27], Zhao and Xu propose a novel target localization algorithm based on Bayesian CS, and the algorithm can effectively save the energy of sensor node, but it may produce false targets. In [28], Zhang et al. propose a Greedy Matching Pursuit (GMP) algorithm to reconstruct the signal with a better resistance to noise compared with the traditional algorithm. However, these algorithms solve not only node localization, but also target localization by CS, and they all adopt RSSI to localization, so the performance of them will be affected by noise. In this paper, we use CS to realize node localization, and the algorithm proposed adopts the connectivity information, rather than RSS, which can avoid the influence of noise.

In this paper, a novel range-free localization approach, LMCS, is proposed. In LMCS, we only use the connectivity information to locate the positions of all sensor nodes. First, the mobile beacon periodically sends a message, and each sensor node gets the hop-count from the position, where the mobile beacon broadcasts the message. The mobile beacon obtains the connectivity information between all beacon points through the use of sensor nodes. Then, we utilize all connectivity information to compute the degree of correlation between the sensor node and all beacon points by CS. Finally, by the degree of correlation, we can get the locations of all sensor nodes.

The rest of the paper is organized as follows. Section 2 introduces the related works on localization in WSN. A brief of background on CS and Centroid are introduced in Section 3. We describe the detail of LMCS in the Section 4. The performance of LMCS is shown in Section 5. Finally, the conclusion is given in Section 6.

2. Related Work

Many algorithms have been proposed to solve the localization problem in the literature. Excellent surveys of the related studies can be found in [29]. The major localization studies are summarized in the section below.

2.1. Range-Based

The range-based schemes are achieved by measuring either node-to-node distances or angles to estimate locations. The typical range-based schemes include strategies based on RSSI, TOA, TDOA, and AOA. In [1], the RSSI is converted to distance information and then node's location is estimated by using the triangulation. Bergamo and Mazzini propose a triangulation strategy for the localization and analyze the effects of fading and sensor mobility on localization [2]. To estimate its possible locations, node uses the beacon advertisements received for ranging [3]. Niculescu and Nath compute comparative angles between neighboring nodes for angulations [4, 5].

2.2. Range-Free

Due to the sensor devices' hardware limitations, the range-free schemes are more economic than the range-based schemes. Centroid scheme is proposed by Bulusu et al. [9]. Centroid formula based on received beacons' locations is used to determine node's locations. The improved Centroid schemes are proposed in [10, 11]. Niculescu and Nath introduce DV-Hop approach to estimate node's locations by measuring hop-counts from each node to specific beacons [12]. The DV-Hop algorithm is improved by using RSSI technology in [13]. APIT scheme uses few beacons to locate each sensor node, but needs high density of beacons [14]. Tran and Nguyen propose LSVM algorithm, which applies SVM to locate sensor node [15].

2.3. Mobile Beacon

As beacons are powerful but expensive, it is very important to minimize the number of beacons, which is used to locate nodes' position. Assume few beacons can move and periodically broadcast their locations, in other words, many statistical beacons can be replaced by few mobile beacons. Therefore, many schemes are proposed by using a beacon or few beacons. Widely speaking, these schemes can also be divided into range-based and range-free.

A range-based localization mechanism combined with the RSSI technique is proposed in [6], sensor nodes' possible locations can be estimated by hearing a single mobile beacon. Sun and Guo's probabilistic localization algorithm based on a mobile beacon utilizes TOA technique for ranging and uses Centroid formula based on distance information to estimate nodes' location [7]. Xia and Chen present a localization scheme by using TDOA technique with mobile beacons, in which the nodes use trilateration to decide their locations [8].

The half arrival and departure overlap (HADO) is a range-free localization scheme proposed by Xiao et al., and it adopts arrival and departure constraint area to decide each node's location [16]. However, HADO has a strict requirement for the path of mobile beacons. In [17], antennas are introduced to estimate each node location, so mobile beacon needs to equip with four directional antennas. In Ssu's MAP localization algorithm, the information received from the mobile beacon is used to find two chords of a circle, and the senor node's location can be estimated by the center of the circle [18]. MAP + GC algorithm uses the intersecting area of two circles to decide the node's location within a possible sensing area by utilizing geometric constraints [19]. Liao et al. propose two enhanced MAP schemes—MAP − M and MAP − M&N, in these algorithms, if the centre and radii of two circles are known, two possible locations are obtained, and then the node's location can be ensured by beacon or neighbor node [20].

3. Compressive Sensing and Centroid

3.1. Compressive Sensing

Nyquist sampling theorem suggests that the sampling rate must be at least double the signal's bandwidth to reconstruct original signal exactly. However, for a large bandwidth signal, a high sampling rate causes too much sampling points, and increases the calculation of the subsequent signal processing. CS technology [21, 22] can solve this problem since it can greatly compress the sampling data to reduce computation. A brief introduction of CS is described below.

Suppose $f \in R^{k \times 1}$ is a real signal, and u is its representation in domain $Ψ$ , which is shown as

\begin{matrix} f = \sum_{i = 1}^{k} Ψ_{i} u_{i} = Ψ u, \end{matrix}

(1)

where

Ψ

is a basis matrix, and

Ψ_{i} \in Ψ

i \in {1,2, \dots, k}

. If the signal f is s-sparse under the basis matrix

Ψ

, then the measurement of signal f is as follows:

\begin{matrix} y = Φ f, Φ : m \times k, \end{matrix}

(2)

where y is the measurements, and

Φ

is a measurement matrix, which must meet RIP. Combining (1) and (2), y can be rewritten as

\begin{matrix} y = Φ Ψ u = A u, \end{matrix}

(3)

where

A = Φ Ψ

is the CS information operator. Then, the sparse solution can be expressed as

\begin{array}{l} \min_{u} {∥ u ∥}_{0} \\ s . t . A u = y . \end{array}

(4)

However, $l_{0}$ -minimization problem cannot be solved directly as it is a nonpolynomial (NP) hard problem. Considering that the signal is sparse, $l_{0}$ -minimization problem can be converted to $l_{1}$ -minimization problem or $l_{2}$ -minimization problem. Where $l_{1}$ -minimization problem can be solved by basis pursuit (BP) [23], which is a global optimal solution, and $l_{2}$ -minimization problem can be solved by Matching Pursuit (MP) [24] algorithm, which has a much faster convergence rate, however, MP is not an optimization algorithm and only has a local optimal solution. Then, many improved algorithms based on MP algorithm, such as orthogonal Matching Pursuit (OMP) [25] algorithm, are proposed.

3.2. Centroid

Centroid lets the geometric center of all beacons within the sensor node communication range be sensor node's estimated position. The localization process can be described as follows: each beacon periodically broadcasts a beacon signal, which includes the ID and location information of the beacon, to the neighbor nodes. When the sensor node receive the number of the beacon signal from beacon node that exceeds the preset threshold in a period of time, the sensor node will let the geometric center of all beacons within the sensor node communication range be estimated position of the sensor node. Assume that there are N nodes $S_{1}, S_{2}, \dots, S_{N}$ located in a $X \times Y$ area with k beacons $(S_{1}, S_{2}, \dots, S_{k})$ . The estimated location $(x (S_{j}), y (S_{j}))$ of the jth sensor node can be expressed as

\begin{matrix} (x (S_{j}), y (S_{j})) = \frac{\sum_{i = 1}^{k} ω_{j, i} (x (S_{i}), y (S_{i}))}{\sum_{i = 1}^{k} ω_{j, i}}, \end{matrix}

(5)

where

ω_{j, i}

is equal to 1 or 0. While the jth sensor node can hear the ith beacon node,

ω_{j, i}

equals to 1, otherwise is 0.

Then, the various improved algorithms have been proposed in [10, 11], and the weighted Centroid were presented that the weighted coefficient is gained through the RSSI between beacon and sensor node.

In this paper, we let the weighted Centroid of all beacon points be the estimated location of the sensor node. According to the correlation degree between the sensor node and all beacon points, the weighted coefficient for the Centriod will be obtained. LMCS is different from traditional Centriod, and it uses not only few one-hop beacon points, but also all beacon points in the location estimation process.

4. LMCS: Localization Algorithm with a Mobile Beacon Based on Compressive Sensing

4.1. Localization Algorithm Principle

$(x (B_{i}), y (B_{i}))$ is the position of the ith mobile beacon point, and the connectivity information between the ith beacon point and all k beacon points is shown as

\begin{matrix} Ψ_{i} = (h (B_{i}, B_{1}), \dots, h (B_{i}, B_{j}), \dots, h (B_{i}, B_{k})) \in R^{k \times 1}, \end{matrix}

(6)

where

h (B_{i}, B_{j}), (i, j = 1,2, \dots, k)

is the hop-count from the ith beacon point to the jth beacon point and

h (B_{i}, B_{i}) = 0

. Then, the basis matrix

Ψ

is described as

\begin{matrix} Ψ = [Ψ_{1}, Ψ_{2}, \dots, Ψ_{k}] \in R^{k \times k} . \end{matrix}

(7)

The connectivity information between the jth sensor node and all k beacon points is shown as

\begin{matrix} H_{j} = (h (S_{j}, B_{1}), \dots, h (S_{j}, B_{i}), \dots, h (S_{j}, B_{k})) \in R^{k \times 1}, \end{matrix}

(8)

where

h (S_{j}, B_{i}), (j = 1,2, \dots, N)

is the hop-count from the jth sensor node to the ith beacon point. If let

Ψ

be the basis matrix, the jth sensor node can be linearly decomposed by

\begin{matrix} H_{j} = \sum_{i = 1}^{k} Ψ_{i} μ_{j, i} = Ψ μ_{j}, \end{matrix}

(9)

where

μ_{j} = (μ_{j, 1}, \dots, μ_{j, i}, \dots, μ_{j, k})

(i = 1,2, \dots, k)

, and

μ_{j, i}

is the related degree between the jth sensor node and the ith beacon point. If the jth sensor node is closer to the ith beacon point in geometry, the correlation coefficient

μ_{j, i}

may be greater, and the main component of the jth node connectivity information could be described by the connectivity information of few beacon points, which are close to the jth node, so only few coefficients bigger, and most of the coefficients are close to 0 or equal to 0, that is, to say,

μ_{j}

is sparse. Therefore, we may use CS to accurately reconstruct

μ_{j}

. The CS theory has indicated that an inner product between a signal and a measurement matrix

Φ \in R^{m \times k} (m < k)

can effectively reduce the dimension of the original signal, and meanwhile, keep its original characteristics. Then, a sampling dictionary is shown as

\begin{matrix} A = Φ Ψ \in R^{m \times k} . \end{matrix}

(10)

In the same way, the measurement $Y_{j}$ can be obtained by compressing $H_{j}$ , and $Y_{j}$ is given by

\begin{matrix} Y_{j} = Φ H_{j} = Φ Ψ μ_{j} = A μ_{j} \in R^{m \times 1} . \end{matrix}

(11)

Then, the position of the jth sensor node $(x {(S_{j})}_{est}, y {(S_{j})}_{est})$ can be shown as

\begin{matrix} (x {(S_{j})}_{est}, y {(S_{j})}_{est}) = \sum_{i = 1}^{k} ω_{j, i} (x (B_{i}), y (B_{i})), \end{matrix}

(12)

where

(x {(S_{j})}_{est}, y {(S_{j})}_{est})

is the estimated position of the jth sensor node,

ω_{j, i}

is the weighted value of the ith beacon point, and

\begin{matrix} ω_{j, i} = \frac{μ_{j, i}}{\sum_{i = 1}^{k} μ_{j, i}}, \end{matrix}

(13)

where

μ_{j, i}

is the related degree between the jth sensor node and the ith beacon point by solving (4), which can be converted to

l_{1}

-minimization problem or

l_{2}

-minimization problem, and these minimization problems can be solved by BP, MP, and OMP.

4.2. Algorithm and Protocol

The algorithm for the sensor node localization mainly includes three parts. First, calculate the correlation coefficient between the sensor node and all beacon points. Second, utilize the correlation coefficient ensured above to compute the weighted value between the sensor node and all beacon points. Finally, estimate the location of the sensor node. The process of LMCS is described as follows.

Algorithm (estimate the location of the sensor node $S_{j}$ ) is as follows. (1)

Input: the measurement $Y_{j}$ , the sampling dictionary A, and all beacon points' positions $(x (B_{i}), y (B_{i})) (i = 1,2, \dots, k)$ .

(2)

Output: the position $(x (S_{j}), y (S_{j}))$ of the node $S_{j}$ .

(3)

The process for the sensor node localization is as follows

(a)

calculate the correlation coefficients between sensor node $S_{j}$ and all beacon points by CS;

(b)

use the correlation coefficients obtained above to compute the weighted values both them by (13);

(c)

estimate the position $(x (S_{j}), y (S_{j}))$ of the sensor node $S_{j}$ by (12).

According to the principle description, the key to locate a sensor node is the related degree between the sensor node and all beacon points. Then the localization Protocol of sensor nodes can be divided into three stages.

Stage 1: Data Collection. The mobile beacon which reaches the ith beacon point should send a HELLO message ${ID, h}$ , where ID is the label of the ith beacon point and h is hop-count, whose initial value is one. Each sensor node only records the minimal hop-count to the ith beacon point and then transmits ID and a new h to neighbor node, where the new h is obtained by adding one to the minimal hop-count. After this round, each sensor node knows its connectivity information $H_{j}$ . To obtain the connectivity information between all beacon points, while the mobile beacon moves the ith position, the beacon must collect the connectivity information between the ith position and previous $i - 1$ positions. If the distance between the ith position and the lth position is no more than communication range, the hop-count between them is one, otherwise the mobile beacon must use all one hop sensor nodes to ensure the minimal hop-count between the ith beacon point and the lth beacon point, where $i = 1,2, \dots, k$ , $l = 1,2, \dots, i - 1$ .

Stage 2: Advertisement. The mobile beacon lets the connectivity information $Ψ$ compress the sample dictionary A by the measurement matrix $Φ$ . Then, the mobile beacon broadcasts a HELLO message ${A, P}$ to each sensor node by a one-hop or multihop path, where P describes the positions of all k beacon points.

Stage 3: Localization. Each sensor node starts this stage after receiving the sample dictionary A from the advertisement stage. First, each sensor node compresses the hop-count information $H_{j}$ into $Y_{j}$ by the measurement matrix $Φ$ . Second, each sensor node gets the correlation coefficients $μ_{j}$ in accordance with CS theory. Finally, each sensor node can obtain its position by weighted centroid.

4.3. Algorithm Analysis

Figure 1 shows how to linearly decompose one sensor node by all beacon points. The square represents the sensor node, and circular and star express all beacon points with zero correlation coefficients and nonzero correlation coefficients, respectively. When the star is greater, the coefficient is greater. As shown in Figure 1, the closer the position of the beacon point in geometry is, the larger the correlation coefficient may be, but the further away the position of the beacon point is, the smaller the correlation coefficient must be, and even close to 0, which trends coincide well with the reality. We can also find $μ_{j}$ is sparse in Figure 1, namely, it is reasonable to adopt CS to excavate the related degrees in geographic.

Figure 1

The schematic of the correlation coefficients.

4.4. Error Analysis

We analyze the LMCS error bound under the effect of the CS error in theoretical as follows.

Lemma 1.

One fix an orthogonal basis $Ψ = {ϕ_{i}}$ , $i \in {1,2, \dots, k}$ , and rearrange the entries $f_{i} (u) = 〈 u, ϕ_{i} 〉$ of the coefficient vector $f (u)$ in decreasing order of magnitude ${| f |}_{1} \geq \dots \geq {| f |}_{i} \geq \dots \geq {| f |}_{k}$ , where ${| f |}_{i}$ is the ith largest entry of the vector $| f (u) |$ , and $| \cdot |$ is absolute value. We say that $f (u)$ belongs to the weak- $l_{p}$ ball of radius R for some $0 < p < \infty$ and $C > 0$ if for each i,

\begin{matrix} {| f |}_{i} \leq R * i^{- 1 / p} . \end{matrix}

(14)

This means that p controls the speed of the decay: the smaller the p, the faster the decay.

Theorem 2.

Suppose all the coefficients ${(f_{i} (u))}_{1 \leq i \leq k}$ are known, and consider the partial reconstruction $f_{s} (u)$ obtained by keeping the s largest entries of the vector $f (u)$ (and setting the others to zero). Therefore, according to (14), the reconstruction error can be expressed as

\begin{matrix} {∥ f (u) - f_{s} (u) ∥}_{2} \leq C_{p} \cdot R \cdot s^{- r}, r = \frac{1}{p} - \frac{1}{2}, \end{matrix}

(15)

where

{∥ L ∥}_{2}

expresses

l_{2}

norm of L, and

C_{p}

which only depends on p is a constant. The details of Lemma 1 and Theorem 2 are presented in [30].

Then, the error of the related degree between the sensor node and all beacon points can be obtained as

\begin{matrix} {∥ μ_{j} - μ_{j}^{est} ∥}_{2} \leq C_{p} \cdot R \cdot s^{- r}, r = \frac{1}{p} - \frac{1}{2}, \end{matrix}

(16)

where

μ_{j}

μ_{j}^{est}

are the real and estimate of the related degree, respectively.

μ_{j}^{est}

is the estimate related degree by keeping the largest coefficients in the expansion of

μ_{j}

under the reference basis

Ψ

Assume the jth sensor node is exact linearly expressed by all beacon points, then the real location can expressed as

\begin{matrix} (x (S_{j}), y (S_{j})) = \sum_{i = 1}^{k} ω_{j, i} (x (B_{i}), y (B_{i})), \end{matrix}

(17)

where

ω_{j, i} = μ_{j, i} / \sum_{l = 1}^{k} μ_{j, l}

, and

μ_{j} = (μ_{j, 1}, μ_{j, 2}, \dots, μ_{j, k})

According to (12), the estimate location of the jth sensor node can be obtained as

\begin{matrix} (x {(S_{j})}_{est}, y {(S_{j})}_{est}) = \sum_{i = 1}^{k} ω_{j, i}^{est} (x (B_{i}), y (B_{i})), \end{matrix}

(18)

where

ω_{j, i}^{est} = μ_{j, i}^{est} / \sum_{l = 1}^{k} μ_{j, l}^{est}

and

μ_{j}^{est} = (μ_{j, 1}^{est}, μ_{j, 2}^{est}, \dots, μ_{j, k}^{est})

According to (17) and (18), we can get the localization error E as follows:

\begin{array}{l} E = sqrt (\underset{X}{\underset{︸}{{(\sum_{i = 1}^{k} x (B_{i}) (ω_{j, i} - ω_{j, i}^{est}))}^{2}}} \\ + \underset{Y}{\underset{︸}{{(\sum_{i = 1}^{k} y (B_{i}) (ω_{j, i} - ω_{j, i}^{est}))}^{2}}}) . \end{array}

(19)

Let $μ_{j, i} / \sum_{l = 1}^{k} μ_{j, l}$ and $μ_{j, i}^{est} / \sum_{l = 1}^{k} μ_{j, l}^{est}$ replace $ω_{j, i}$ and $ω_{j, i}^{est}$ , and then the inner summation X may be expressed as

\begin{matrix} X = {(\sum_{i = 1}^{k} x (B_{i}) (\frac{μ_{j, i}}{\sum_{l = 1}^{k} μ_{j, l}} - \frac{μ_{j, i}^{est}}{\sum_{l = 1}^{k} μ_{j, l}^{est}}))}^{2} . \end{matrix}

(20)

Because $μ_{j}^{est}$ is the estimate correlation coefficients by keeping the largest coefficients in the expansion of $μ_{j}$ in the transform basis $Ψ$ , $\sum_{l = 1}^{k} μ_{j, l}$ is greater than $\sum_{l = 1}^{k} μ_{j, l}^{est}$ . Therefore X is less than $(\sum_{i = 1}^{k} (x (B_{i}) / \sum_{l = 1}^{k} μ_{j, l}) {(μ_{j, i} - μ_{j, i}^{est}))}^{2}$ . Since Only a few $μ_{j, i}$ are larger, and these positions of the beacon point are closer to the sensor node, and other $μ_{j, i}$ are close to zero, $\sum_{i = 1}^{k} (x (B_{i}) / \sum_{l = 1}^{k} μ_{j, l}) (μ_{j, i} - μ_{j, i}^{est})$ is approximate to $\sum_{i = 1}^{k} (x (S_{j}) / \sum_{l = 1}^{k} μ_{j, l}) (μ_{j, i} - μ_{j, i}^{est})$ . Therefore, X can be expressed as

\begin{matrix} X \leq {(\sum_{i = 1}^{k} \frac{x (S_{j})}{\sum_{l = 1}^{k} μ_{j, l}} (μ_{j, i} - μ_{j, i}^{est}))}^{2} . \end{matrix}

(21)

Based on the same reason, the inner summation Y can be expressed as

\begin{matrix} Y \leq {(\sum_{i = 1}^{k} \frac{y (S_{j})}{\sum_{l = 1}^{k} μ_{j, l}} (μ_{j, i} - μ_{j, i}^{est}))}^{2} . \end{matrix}

(22)

Then, the localization error E could be demonstrated as

\begin{array}{l} E \leq sqrt ({(\sum_{i = 1}^{k} \frac{x (S_{j})}{\sum_{l = 1}^{k} μ_{j, l}} (μ_{j, i} - μ_{j, i}^{est}))}^{2} \\ + {(\sum_{i = 1}^{k} \frac{y (S_{j})}{\sum_{l = 1}^{k} μ_{j, l}} (μ_{j, i} - μ_{j, i}^{est}))}^{2}) \\ \leq \frac{1}{\sum_{l = 1}^{k} μ_{j, l}} \\ \cdot sqrt (k \cdot \sum_{i = 1}^{k} (x^{2} (S_{j}) + y^{2} (S_{j})) \cdot {(μ_{j, i} - μ_{j, i}^{est})}^{2}) \\ = \frac{\sqrt{k \cdot (x^{2} (S_{j}) + y^{2} (S_{j}))}}{\sum_{l = 1}^{k} μ_{j, l}} \cdot \sqrt{\sum_{i = 1}^{k} {(μ_{j, i} - μ_{j, i}^{est})}^{2}} \\ = \frac{\sqrt{k \cdot (x^{2} (S_{j}) + y^{2} (S_{j}))}}{\sum_{l = 1}^{k} μ_{j, l}} \cdot {∥ μ_{j} - μ_{j}^{est} ∥}_{2} . \end{array}

(23)

According to above deduction and (16), we can describe the localization error E as follows:

\begin{matrix} E \leq \frac{\sqrt{k \cdot (x^{2} (S_{j}) + y^{2} (S_{j}))}}{\sum_{i = 1}^{k} μ_{j, i}} \cdot C_{p} \cdot R \cdot s^{- r} . \end{matrix}

(24)

5. Simulation Study and Analysis

To compare the performance of MAP + GC [19], MAP – M [20], and MAP − M&N [20] with LMCS, we discuss the performance of four algorithms under ideal environment (Figure 2(a)) and obstacle environment (Figure 2(b): assume that there are four 10 m × 20 m obstacles that existed in the sensing field), and analyze the radio range, GPS error, radio irregularity, and the velocity of mobile beacon to impact on the performance of four algorithms. We also discuss the effect of compression ratio and radio time on the performance of LMCS.

Figure 2

Simulation environment.

Take one network with 1,000 sensor nodes for example, suppose all nodes locate in a 100 m × 100 m area, and their locations obey uniform random distribution. We assume that the mobile beacon and all the sensor nodes have the same communication range being 20 m, the mobile beacon is assumed to move straight at a velocity of 20 m/s and the mobile beacon path follow the random waypoint (RWP) model [31]. In three MAP algorithms, the mobile beacon broadcasts a message every 0.1 sec, and 10000 times; in LMCS, the mobile beacon broadcasts a message every 1 sec, and 800 times, the measurement matrix $Φ$ employs random Gaussian matrix, and compression ratio is equal to 0.3.

5.1. Ideal Environment

Figure 3 shows each node's location error in ideal environment. In Figures 3(b), 3(c), and 3(d), the red circles represent the nodes, which are not located. We can see, roughly, that most of the location errors have no more than 5 m in LMCS, but many location errors are large in three MAP schemes. It can be also found that the maximum location error of LMCS is far smaller than that of MAP + GC, MAP − M, and MAP − M&N. As the beacon points exist, there is improper selection in MAP + GC, MAP − M, and MAP − M&N, which will cause a large location error. Although the mobile beacon broadcasts 10000 times, some sensor nodes still cannot be located for MAP + GC, MAP − M, and MAP − M&N. But this problem is nonexistent in LMCS. As LMCS uses the connectivity information to localize nodes, and no matter how many time the radio is, all nodes can be localized. However, for the other three schemes, the radio time will affect the number of nodes localized. To localize all nodes, these three schemes must have high radio time. Certainly, the localization accuracy of LMCS will be affected by the radio time.

Figure 3

The location error of each sensor node.

We make 120 times Monte Carlo experiments to obtain the average location error of the four schemes under an ideal environment, which is shown in Table 1. The average location error of LMCS is smaller than that of MAP + GC, MAP − M, and MAP − M&N. Therefore, LMCS is a better choice for localization than MAP + GC, MAP − M, and MAP − M&N.

Table 1

The localization performance comparison.

Scheme	Avg. location error (m)
LMCS	1.69
MAP + GC	1.98
MAP − M	2.48
MAP − M&N	4.31

5.2. Obstacle Environment

Table 2 illustrates the localization performance comparison under obstacle environment for the four methods. We can see that the average location error of LMCS is smaller than that of MAP + GC, MAP − M, and MAP − M&N; in other words, the localization performance of LMCS is much better than MAP + GC, MAP − M, and MAP − M&N.

Table 2

The localization performance comparison.

Scheme	Avg. location error (m)
LMCS	2.85
MAP + GC	5.71
MAP − M	6.92
MAP − M&N	11.14

Compared with Tables 1 and 2, we can find the localization performance of four methods under obstacle environment is worse than under ideal environment, and the influence of environment on LMCS is much less than MAP + GC, MAP − M, and MAP − M&N. Due to existing obstacles, the choice of beacon point is more prone to errors in MAP + GC, MAP − M, and MAP − M&N, and the localization performance of MAP + GC, MAP − M, and MAP − M&N is much worse. However, as obstacles only have little impact on the connectivity information, the performance of LMCS will not get worse.

5.3. Impact of GPS Error

All GPS receivers have localization error in real environments, which include three basic location errors, that is, single-point positioning error, differential positioning error, and carrier positioning error [32]. The simulations assume GPS errors based on a normal distribution. Applying the carrier positioning error, the mean GPS errors are specified as 0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, and 1 meter, respectively, with a standard deviation of 0.05 meters.

Figure 4 illustrates the variation of the localization error with the GPS error for the four methods. In general, with the increase of the GPS errors, the location errors of the four schemes are increased with a slow trend, in other words, while GPS errors are small, the impact of which is not very obvious for localization accuracy.

Figure 4

Relationship between localization performance and GPS error.

5.4. Impact of Radio Range

Figure 5 shows the variation of the location error as the radio range for the four schemes. It can be seen that, with the increase of the radio range, the location errors of the four schemes are increased. And yet, the impact of radio range on MAP + GC, MAP − M, and MAP − M&N is more than LMCS.

Figure 5

Relationship between localization performance and radio range.

5.5. Impact of Radio Irregularity

As the radio range of node is irregular in practical environment, the influence of degree of irregularity (DOI) is discussed in this section. DOI is defined as the maximum radio range variation per unit degree change in the direction of radio propagation as

\begin{matrix} K_{i} = {\begin{cases} 1, & i = 0, \\ K_{i - 1} \pm Rand \times DOI, & 0 < i < 360, \end{cases} \end{matrix}

(25)

where

| K_{0} - K_{359} | \leq DOI

[33].

Figure 6 describes the average location error of these four schemes under different DOI. As shown, the average location errors of MAP + GC, MAP − M, and MAP − M&N schemes are increased with the increase of DOI, in other words, DOI has an evident influence on these three schemes. However, the average location error of LMCS remains a constant. Namely, DOI has a slight influence on LMCS. This is because MAP + GC, MAP − M, and MAP − M&N schemes make use of the irregular radio range to estimate the location of the node, but LMCS use the connectivity information, and DOI has little effect on the connectivity information.

Figure 6

Relationship between localization performance and DOI.

5.6. Impact of the Velocity of Mobile Beacon

Figure 7 shows the variation of the location error as the velocity of mobile beacon for the four schemes. It can be seen that, with the increase of the velocity, the location errors of LMCS scheme is almost a constant value, but the location errors of MAP + GC, MAP − M, and MAP − M&N schemes are increased. Because the velocity is different, beacon distance which affects the performance of MAP + GC, MAP − M, and MAP − M&N schemes is also different. But in LMCS, since the number of beacon points is the same, the completeness of the sampling dictionary remains almost unchanged and the performance remains. Therefore, the velocity of mobile beacon has obvious influence on MAP + GC, MAP − M, and MAP − M&N, but almost no influence on LMCS.

Figure 7

Relationship between localization performance and the velocity of mobile beacon.

Table 3 illustrates the number of sensor nodes localized comparison under different the velocity of mobile beacon for the four methods. As it can be seen, the number of sensor nodes localized is increased with the increase of the velocity for MAP + GC, MAP − M, and MAP − M&N schemes, but LMCS scheme has always localized all nodes. In Figure 7, we can see that the performance of MAP + GC is slightly better than that of LMCS while the velocity is 10 m/s, however, according to Table 3, our scheme can localize all node while the mobile beacon just broadcasts 800 times, but MAP + GC only localizes 886 nodes while the mobile beacon broadcasts 10000 times. Besides, we can increase the broadcasting time to improve the performance of LMCS scheme.

Table 3

The number of sensor nodes localized.

Velocity (m/s)	The number of nodes
Velocity (m/s)	LMCS	MAP + GC	MAP − M	MAP − M&N
10	1000	886	901	967
20	1000	894	913	978
30	1000	929	940	981
40	1000	946	953	993
50	1000	958	973	999

5.7. Impact of Compression Ratio

The average location error as the function of compression ratio $m / k$ is shown in Figure 8. It can be seen that LMCS has less localization error with the growth of the compression ratio. However, while compression ratio reaches a certain value, the change of localization accuracy is not obvious. And, with the increase of compression ratio, we need more memory to store sampling atoms, and more energy consumption. Therefore, we must reasonably select compression ratio.

Figure 8

Relationship between localization performance and compression ratio.

5.8. Impact of Radio Time

Figure 9 shows the average location error as the function of radio time in LMCS. It can be seen that the localization error of sensor nodes reduces with the increase of radio time. Since the sampling dictionary becomes more complete while radio time is more, then sensor nodes can be more accurately expressed. Therefore, the localization performance becomes better.

Figure 9

Relationship between localization performance and radio time.

6. Conclusion

A novel range-free localization algorithm—LMCS is proposed in this paper. LMCS makes use of CS to excavate the degree of correlation between sensor nodes and beacon points, and then weighted Centroid to realize node localization. Simulation studies confirm that, compared with MAP + GC, MAP − M, and MAP − M&N, LMCS has lower average location error. What is more, as LMCS adopts the connectivity information to localize each node, the obstacles and DOI have little effect on LMCS, but they have great effect on these three MAP algorithms. Therefore, LMCS is more suitable for practical application than MAP algorithms. In addition, LMCS can completely locate all nodes with few beacon points, but MAP algorithms cannot ensure to completely locate all nodes even with huge beacon points. Above all, LMCS is a reliable, effective, and useful range-free localization algorithm and more suitable for practical application. However, LMCS also has few shortcomings, such that it needs sensor node to obtain the connectivity information, and it consumes energy of sensor node.

Footnotes

Acknowledgments

This study is supported by the National Natural Science Foundation of China (61077079), the Ph.D. Programs Foundation of the Ministry of Education of China (20102304110013), and the Fundamental Research Funds for the Central Universities (HEUCF1208).

References

Bahl

Padmanabhan

V. N.

RADAR: an in-building RF-based user location and tracking system

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '00)

March 2000

775 784

2-s2.0-0033872896

Bergamo

Mazzini

Localization in sensor networks with fading and mobility

Proceedings of the 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC '02)

September 2002

Ferrara, Italy

750 754

2-s2.0-79955500345

10.1109/PIMRC.2002.1047322

Priyantha

N. B.

Chakraborty

Balakrishnan

Cricket location-support system

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00)

August 2000

Boston, Ma, USA

32 43

2-s2.0-0034539094

Niculescu

Nath

Ad hoc positioning system (APS) using AOA

Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03)

March 2003

San Francisco, Calif, USA

1734 1743

Nasipuri

A directionality based location discovery scheme for wireless sensor networks

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications

September 2002

Atlanta, Ga, USA

105 111

2-s2.0-0036986579

Sichitiu

M. L.

Ramadurai

Localization of wireless sensor networks with a mobile beacon

Proceedings of the IEEE International Conference on Mobile Ad-Hoc and Sensor Systems

October 2004

Fort Lauderdale, Fl, USA

174 183

2-s2.0-20344396105

Sun

G.-L.

Guo

Comparison of distributed localization algorithms for sensor network with a mobile beacon

Proceedings of the IEEE International Conference on Networking, Sensing and Control

March 2004

Taipei, Taiwan

536 540

2-s2.0-2942668036

Xia

Chen

A localization scheme with mobile beacon for wireless sensor networks

Proceedings of the 6th International Conference on ITS Telecommunications (ITST '06)

June 2006

Chengdu, China

1017 1020

2-s2.0-44449143101

10.1109/ITST.2006.288725

Bulusu

Heidemann

Estrin

GPS-less low-cost outdoor localization for very small devices

IEEE Personal Communications 2000 7 5 28 34

2-s2.0-0034291601

10.1109/98.878533

10.

Wang

Urriza

Han

Cabric

Weighted centroid localization algorithm: theoretical analysis and distributed implementation

IEEE Transactions on Wireless Communications 2011 10 10 3403 3413

2-s2.0-80855147421

10.1109/TWC.2011.081611.102209

11.

Yang

Kong

Dai

An improved weighted centroid location algorithm

Journal of Xi'an Jiaotong University 2010 44 8 1 4

2-s2.0-77956830421

12.

Niculescu

Nath

DV based positioning in Ad hoc networks

Telecommunication Systems 2003 22 1–4 267 280

2-s2.0-0038703640

10.1023/A:1023403323460

13.

Savarese

Rabaey

J. M.

Langendoen

Robust positioning algorithms for distributed ad-hoc wireless sensor networks

Proceedings of the General Track of the Annual Technical Conference (USENIX '02)

June 2002

Berkeley, Ca, USA

317 327

14.

Huang

Blum

B. M.

Stankovic

J. A.

Abdelzaher

Range-free localization schemes for large scale sensor networks

Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking, MobiCom 2003

September 2003

San Diego, Ca, USA

81 95

2-s2.0-1542329081

15.

Tran

D. A.

Nguyen

Localization in wireless sensor networks based on support vector machines

IEEE Transactions on Parallel and Distributed Systems 2008 19 7 981 994

2-s2.0-62449093573

10.1109/TPDS.2007.70800

16.

Xiao

Chen

Zhou

Distributed localization using a moving beacon in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2008 19 5 587 600

2-s2.0-42549119365

10.1109/TPDS.2007.70773

17.

C. H.

A localization scheme for wireless sensor networks using mobile anchors with directional antennas

IEEE Sensors Journal 2011 11 7 1607 1616

18.

Ssu

K.-F.

C.-H.

Jiau

H. C.

Localization with mobile anchor points in wireless sensor networks

IEEE Transactions on Vehicular Technology 2005 54 3 1187 1197

2-s2.0-21244474042

10.1109/TVT.2005.844642

19.

Lee

Kim

Localization with a mobile beacon based on geometric constraints in wireless sensor networks

IEEE Transactions on Wireless Communications 2009 8 12 5801 5805

2-s2.0-73049116477

10.1109/TWC.2009.12.090319

20.

Liao

W.-H.

Lee

Y.-C.

Kedia

S. P.

Mobile anchor positioning for wireless sensor networks

IET Communications 2011 5 7 914 921

2-s2.0-80053252423

10.1049/iet-com.2010.0336

21.

Donoho

D. L.

Compressed sensing

IEEE Transactions on Information Theory 2006 52 4 1289 1306

2-s2.0-33645712892

10.1109/TIT.2006.871582

22.

Candès

E. J.

Plan

A probabilistic and RIPless theory of compressed sensing

IEEE Transactions on Information Theory 2011 57 11 7235 7254

2-s2.0-81255188959

10.1109/TIT.2011.2161794

23.

Chen

S. S.

Donoho

D. L.

Saunders

M. A.

Atomic decomposition by basis pursuit

SIAM Review 2001 43 1 129 159

2-s2.0-0035273106

10.1137/S003614450037906X

24.

Mallat

S. G.

Zhang

Matching pursuits with time-frequency dictionaries

IEEE Transactions on Signal Processing 1993 41 12 3397 3415

2-s2.0-0027842081

10.1109/78.258082

25.

Tropp

J. A.

Gilbert

A. C.

Signal recovery from random measurements via orthogonal matching pursuit

IEEE Transactions on Information Theory 2007 53 12 4655 4666

2-s2.0-64649083745

10.1109/TIT.2007.909108

26.

Feng

Valaee

Tan

Multiple target localization using compressive sensing

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '09)

December 2009

Honolulu, Hawaii, USA

4356 4361

2-s2.0-77951543254

10.1109/GLOCOM.2009.5425808

27.

Zhao

Energy constraint Bayesian compressive sensing detection algorithm

Journal on Communications 2012 33 10 1 6

28.

Zhang

Cheng

Zhang

Cui

Liang

Sparse target counting and localization in sensor networks based on compressive sensing

Proceedings of the IEEE International Conference on Computer and Communications Societies (INFOCOM '11)

April 2011

Shanghai, China

2255 2263

2-s2.0-79960852449

10.1109/INFCOM.2011.5935041

29.

Cheng

Zhang

Maple

A survey of localization in wireless sensor network

International Journal of Distributed Sensor Networks 2012 2012 12

962523

10.1155/2012/962523

30.

Candes

E. J.

Tao

Near-optimal signal recovery from random projections: universal encoding strategies?

IEEE Transactions on Information Theory 2006 52 12 5406 5425

2-s2.0-33947416035

10.1109/TIT.2006.885507

31.

Broch

Maltz

D. A.

Johnson

D. B.

Y. C.

Jetcheva

J. G.

A per-formance comparison of multi-hop wireless ad hoc network routing protocols

Proceedings of 4th Annual International Conference on Mobile Computing and Networking(MOBICOM '98)

October 1998

New York, NY, USA

85 97

32.

Geodetic Survey Division-Geodesy-GPS Accuracy Levels, http://www.geod.nrcan.gc.ca/edu/geod/gps/gps13_e.php

33.

Zhou

Krishnamurthy

Stankovic

J. A.

Impact of radio irregularity on wireless sensor networks

Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services (MobiSys '04)

June 2004

Boston, Ma, USA

125 138