A Detection Probability Localization Algorithm of Wireless Sensor -1

A Detection Probability Localization Algorithm of Wireless

Sensor Networks based on Distributed

Compressed-Sensing

Peo Ple1*, Peo Ple2**, Peo Ple2***, and Peo Ple4*

Abstract

With fast development of science and technology, People gradually need more and more information, causing significant pressure on the sampling. The sampling rate must be two times higher than the highest frequency of the signal based on Nyquist sampling theorem. Compressed Sensing (CS) employs a special sampling method which can capture and represent compressible signals at a rate significantly below the Nyquist rate. It can relieve the pressure of sampling process in Wireless Sensor Networks. And a cooperative self-localization method based on probability for wireless sensor networks is proposed. The method firstly estimates the initial Position of the located node based on the joint Probability density function of the distance between the located node and the connected reference nodes. Further, based on the refinement principle, a cooperative localization method is studied by making the best of the neighbour nodes and giving the neighbour nodes some confidence. The method improves the estimation accuracy as well as makes more unknown nodes to be located.

Key Words

Wireless Sensor Networks, Localization, DV-Hop, Compressed Sensing

1.Introduction

Wireless Sensor Networks (WSNs) distinguish themselves from other traditional wireless or wired networks through sensor and actuator based interaction with the environment. Localization is a fundamental and essential issue for wireless sensor networks. In context-aware applications, localization enables the intelligent selection of appropriate devices, and may support useful coordination among devices. The range-based scheme determines the distance between two different sensor nodes based on a variety of information, such as Time of Arrival (TOA) [1], Time Difference of Arrival (TDOA) [2], Angle of Arrival (AOA) [3], and Received Signal Strength Indicator (RSSI) [4]. Because of the drawbacks of ranged-based schemes, many range-free localization schemes have been proposed, such as Centroid [5], Peo Ple1

Faculty of Information & Control Engineering,Shenyang Jianzhu University, China

email: gzj@https://www.sodocs.net/doc/fd4489364.html,

Peo Ple2

School of Information and Communication Engineering, Dalian University of Technology, China

email: wanghy@https://www.sodocs.net/doc/fd4489364.html,

Peo Ple3

Shenyang Metrology Testing Institution, China

email: xcy0311@https://www.sodocs.net/doc/fd4489364.html,

Peo Ple4

Faculty of Information & Control Engineering,Shenyang Jianzhu University, China

email: xiaozhonghua1977@https://www.sodocs.net/doc/fd4489364.html,

Manuscript received 18 March 2013

CPE [6], DLE [7], MCL [8], MSL [9]etc. DV-Hop is one of a range-free localization algorithm which is also proposed by D.Niculescu and B.Nath [10] [11].

Donho, Candes and Tao[12][14,15] establish the compressed sensing theory. The breakthrough results of [12] and [13] theoretically proved that in certain applications it may be unnecessary to apply classical sampling at Nyquist rate to guarantee perfect signal reconstruction. With the densely distributed wireless sensor network node which is characterized by a certain storage capacity, it is necessary to take the advantage of distributed compressed-sensing study of wireless sensor networks. In [16], D.Baron etc. first establish the basic concept and theory of distributed compressed-sensing, then and in [17] give the upper and lower of measurement value number, and the signal compressed rate of distributed compression-sensing theory. in [18], the authors construct different joint sparse model and design a joint decoding algorithm . Literature [19] which is on the basis of literature [18], improving the joint decoding algorithm, and the data compression ratio; in literature [20], distributed compression-sensing theory is applied to wireless sensor networks. Compressed sensing could fetch useful information efficiently carried in the signal, and consequently proposes an effective solution to relieve the pressure of sampling process.

2. Compressed Sensing 2.1 Compressed Sensing Theory

In some cases, complete acquisition the actual sample of the signal is difficult, but also difficult to be compressed. Compressed-sensing theory which directly records the measured values of the signal effectively carries out the data acquisition. The theory core is that the compression process is in the data sampling process. .Compressed sensing uses less random observation times to get high precision reconstruction data in [21], and reduce 37.5% number of measurements in [22]. The process is as follows: x denotes the length N sparse signal. Using a measurement matrix to calculate y which has ()M N <

y x =Φ

(1)

Where Φ is M N ? measurement matrix. If x is a compression signal, the sampling process is can be expressed as follows:

y x s s =Φ=Φψ=Θ

(2)

Where Θ=Φψ,the size is M N ?. ψ is N N ? coefficient transformation matrix. Candes, Romberg and Tao give the sufficient condition of measurement matrix, which is RIP(Restricted Isometry Property). For any vector x, if Φ satisfies the following in equation:

2

2

2222

(1)(1)x x x

δδ-≤Φ≤+, 01δ<<

(3)

Then matrix Φ is meet RIP and the signals can be reconstructed precisely.

Figure 1. The process of compressed-sensing.

The RIP proposes a theoretical framework to establish a measurement matrix that can reconstruct

signals perfectly. There are many measurement matrixes. The most common matrix is Gaussian randomly measurement matrix which is uncorrelated with most sparse signals and needs small number of measurements relatively. This paper chooses Gaussian randomly measurement matrix. The RIP property

is proofed in [23] [24]. Matrix M N

R ?Φ∈, in which each element follows Gaussian distribution that means

the mean value is 0 and the variance is 1/

,i j N ?

Φ ?

(4)

2.2 Signal Reconstruction Algorithm of Distributed Compressed-Sensing

Distributed compressed sensing theory depends on the joint sparse model, so establish the model first.

Each of the original signal comprises two parts: the sparse public part and a unique part, and the signal of the model structure is impacted by a global environment and a local environment For example, a sensor network used to measure the temperature distribution in a forest, where the sun is the global environment impact, and water flow etc. can be regarded as a local environment impact. In this model, all of the original

signal can be represented as a sparse public part c Z and a unique part j Z

, so

{}1,2,,j c j X Z Z j J =+∈L

(5)

At the encoding side, a channel signal in the original signal uses the compression-sensing coding algorithm for compression encoding. At the decoding side, the channel signal use orthogonal matching pursuit algorithm for decoding, and the obtained result which is also known for other signals in the common decoding side is an estimate of the original signal. Therefore, it can be reasonably used as side information, and can simplify the coding process without reducing the decoding performance. When the other signal is encoding, it is possible to appropriately reduce the number of measured values. Then based the sparse model, the Side information based orthogonal Matching Pursuit algorithm is used in the sampling process. The algorithm is as follows:

1) Input: Measurement matrix Φ, measured value Y X =Φ, sparsity K ; 2) Output: Indices set

{}

1,2,,I d = ;

3) Initialize: Set indices set I =?, iteration number t =1, initial iteration residual value 1?j r Y x

=-Φ; 4) Normalize: Vector t t y r =Φ, get the coordinate value which is more than some specific value, so

{}

:t j t t

J j y Th σ=>, where Th is the threshold in each iteration, t σ is a corrected parameter;

5) Iteration steps: Add coordinate value t J to I , {}t I I J =?; Update iteration residual value;

2?arg min |t I z x Y z =-Φ,1?t t t r r x +=-Φ; Matrix I Φ is the sub-matrix which is composed by column of indices set I ; t =t +1; 6) If t

x r =Φ.

3. DV-Hop Localization Algorithm Based on Detection Probability

The power consumption is one of the biggest factors that impact the design and implementation of

wireless sensor networks. Precise localization which relies on the information interchange frequent neighbor and a series of measurement results increases network traffic overhead and energy consumption. Wireless communication module to send and receive information cost 80% energy consumption of sensor nodes in wireless sensor networks, so reducing the measuring number is necessary. 3.1 Establish Model

There is a static wireless sensor network, in which there are several reference nodes and unlocated nodes. This paper assumes that the relative error of the measurement distance from the true distance affect obey normal distribution with parameters.The estimated distance between reference node k and unlocated node

i is ik

ik ik d d ε=+%, where ik ε is the ranging error between the two points, and ()2

~,ik ik ik N εμσ. Based on the knowledge of probability theory ,we know ()()/~0,1ik ik ik ik N ξεμσ=-；The form of a matrix of the

system model can be expressed as

()

~,1ik ik

ik ik

d N d μσ-% (6) i j i i

X G D ξ=+

(7)

Where

11221

2,,,T i i i i iK iK i i i iK d d d X μμμσσσ??---=????%%%L

12

111,,,i i i ik G diag σσσ??

= ???L

[]12,,,T

i i i iK D d d d =L

[]12,,,T

i i i iK ξξξξ=L

The joint probability density function is as follows:

()()

()

()()/21|2exp 2K T i i i i i i i i f X P X G D X G D π-??

=---????

(8)

Where i P is the position of unlocated node i .

In order to reflect the inter-node hops with ranging, it is assumed that 22

ik ik h σσ= , where ik h is the

number of hops between the reference node k and unlocated node i . 3.2 Collaborative Processing Method

Determine the estimated coordinates of unlocated node (

)

,x y %% by the weighted average

()()()()

max

max max

max min

min

min

min

,,,,x y x y x y x y x

y x f x y dxdy y f x y dxdy =???

?

?

?

%%(9)

Collaborative processing method according to connectivity of the neighbor nodes, improves the

localization accuracy, makes more nodes to be localization, and can improve the coverage of the network node localization.In each precise localization stage, different nodes are given different weights, where the right value is defined as the node location credit. But how to choose the node credibility is not universally applicable law. In general, the size of the credit is usually based on various measurement precision. In this paper, the calculation of node credit to obey the following principles: 1. The credit range of a single node is (0, 1).

2. The credit of the node which directly connects to the reference node is highest.

3. The positioned nodes which are located become the standard reference node, but the credit is lower than the reference node.

4. The credit of more neighbors is higher than the node of fewer neighbors. For node i, the credit of node k is ik Conf , then the two nodes ranging error is

()

2

~,/ik ik ik ik N Conf εμσ (10)

When the node gets the initial position, the average credit of its neighbor nodes is its credit. Then

iteratively update their location information and credit, improve localization accuracy. With the increase number of iterations, the node Credit will gradually approaches the reference node Credit. When the node to be positioned credit exceeds a set threshold, or r the twice calculated results are very close, the algorithm ends.

The network can choose high precision positioning node to participate in the localization by hierarchical credit. The weights of high precise localization nodes are also high, so that the positioning estimation error is limited, and node localization is accuracy.We use DV-Hop algorithm to test the method.

The algorithm’s implementation is comprised of three steps:

1) All nodes in the network acquire the minimum hop count values to all anchors using flooding (anchors are the reference nodes).

2) The average single hop distance is estimated to convert hop count value into physical distance. For the

anchor node with (),i i x y

coordinates, the average distance per hop is estimated by the following equation:

HopSize j i

i

ij j i

h

≠≠=

∑ (11)

Where (

)

,i i x y , is the location of the anchor j,

ij

h is the number of hops between the anchor node i and the

anchor node j. Once calculated, the estimated HopSize i information is broadcasted into the network. 3) The unknown node location can be estimated by the multilateration method when these nodes have the

distance estimations to at least three anchors. Given a set of reference nodes (),1,2,,T

i i i N x y i n

=L ,

where n is the number of anchors, let the hop value between the unknown node (),T

X x y , and the i -th

anchor is i R . Then the distance between the unknown node and i -th anchor node is given by d =r HopSize i i i g . The unknown node location X can be found from:

12n

d d d ?==?=L

(12)

Equation (12) can be written in matrix form AX = b where:

()()()()()()112211222222n n n n n n n n x x y y x x y y A x x y y ----?? ?-- ?= ? ?

?

--?

?L

22222

2111222222

222

222222111n n n n n n n n

n n n n x x y y d d x x y y d d B x x y y d d ---??-+-+- ?-+-+- ?= ? ?

?-+-+-??L

x X y ??= ???

The least-squares estimate of X is ()1

T T X A A A b

-=.

4. Simulations and Results

In this section, simulation results are presented and analyzed. To validate the algorithm, thorough simulations are performed. The simulation result is given as average localization error of 100 experiments. We compare the DV-Hop and our proposed algorithm to evaluated location performance. And we offer simulation results under the following simulation circumstance: All the sensor nodes are random placed in a square area with the fixed size of 1000m×1000m. In the simulation the localization error is defined as the ratio of the difference between the estimated localization and real localization to the communication range of sensor nodes. The localization error reflects the accuracy of localization. The less the localization error is, the more accurate the localization performance. Fig. 2 illustrates random uniform node placement and C shaped random topology. 80 sensor

100

200

300

400

500

600

700

800

900

1000节点分布图

Figure 2. (a)Random deployment, 80 unknown nodes and 20 anchors. (b) C Shaped Random deployment, 40 unknown nodes and 5 anchors.

Figure 3. (a)Gridy network, 97 unknown nodes and 24 anchors.

(b)C Shaped Gridy deployment, 80 unknown nodes and 20 anchors.

Localization error as a function of the radio transmission range is given in Table1 ~ 3. As depicted in the Table1 ~ 3, the localization error decreases with the increase of the average connectivity, and Improved DV-Hop achieves better performances. The algorithm with Distributed Compressed-Sensing and the algorithm without Distributed Compressed-Sensing have the analogous performances.

Table 1

Location Errors of Basic DV-Hop

Table 2

Location Errors of improved DV-Hop without Distributed Compressed-Sensing

Location Errors of improved DV-Hop with Distributed Compressed-Sensing

Conclusion

Positioning plays a critical role in many applications. It is one of the basic functions of wireless sensor networks to determine the position of sensor nodes and the occurred event. And the former is the basis of the latter. After the located node receives the information from many reference nodes, some better reference nodes need to be selected to estimate the position of the located node to improve the localization accuracy. It is the main research content of the choose mechanism of reference nodes for localization to how to select the best suitable reference nodes to locate the unknown nodes and achieve the best localization results.

In this paper, the improvement DV-Hop algorithm with distributed compressed-sensing is proposed. Simulation results show that this paper scheme is better compared to the original DV-Hop algorithm. The algorithm requires a small number of sampling. It not only can improve the positioning accuracy can also be calculated the probability of each anchor node. The algorithm is extraordinary simple. Acknowledgements

The authors acknowledge the financial support of fund and program of Housing and Urban Development of China (2011-k1-32; sjw10-04).

References

[1] G.J. Pottie and W.J. Kaiser, .Wireless Integrated Network Sensors,. Comm. ACM, vol. 43, no. 5, pp. 51-58, May 2000.

[2] N.B. Priyantha, A. Chakraborty, and H. Balakrishnan, .The Cricket Location-Support System,. Proc. ACM MobiCom ’00, pp. 32-43, Aug. 2000.

[3] A. Savvides, C.-C. Han, and M.B. Strivastava, .Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,. Proc. ACM MobiCom ’01, pp. 166-179, July 2001.

[4] J. Hightower and G. Borriello, .Location Systems for Ubiquitous Computing,. Computer, vol. 34, no. 8, pp. 57-66, Aug. 2001.

[5] N. Bulusu, J. Heidemann, and D. Estrin, .GPS-Less Low Cost Outdoor Localization for Very Small Devices,. IEEE Personal Comm. Magazine, vol. 7, no. 5, pp. 28-34, Oct. 2000.

[6] L. Doherty, K.S.J. Pister, and L.E. Ghaoui, .Convex Position Estimation in Wireless Sensor Networks,. Proc. IEEE INFOCOM ’01, vol. 3, pp. 1655-1663, Apr. 2001.

[7] J.-P. Sheu, J.-M. Li, and C.-S. Hsu, .A Distributed Location Estimating Algorithm for Wireless Sensor Networks,. Proc. Int’l Conf. Senso r Networks, Ubiquitous, and Trustworthy Computing (SUTC ’06), vol. 1, pp. 218-225, June 2006.

[8] L. Hu and D. Evans, .Localization for Mobile Sensor Networks,. Proc. ACM MobiCom ’04, pp. 45-47, Sept. 2004.

[9] M. Rudafshani and S. Datta, .Localization in Wireless Sensor Networks,. Proc. Int’l Conf. Information Processing in Sensor Networks (IPSN ’07), pp. 51-60, Apr. 2007.

[10] D.Niculescu,B.Nath., “Ad hoc positioning system (APS)”,in Proc.of IEEE Global Telecommunications Conf (GLOBECOM01),Vol.5,pp.2926-2931,2001.

[11] Niculescu D.Nath B, “DV based positioning in ad hoc networks[J],” Joural of Telecommunications Systems,pp.267-280,2003,22(1/4).

[12] Emmanuel Candes, Justin Romberg, Terence Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 2006, 52(2), 489-509

[13] D. Donoho, High-dimensional centrally symmetric polytopes with neighborlines proportional to dimension, Discrete & Computational Geometry, 2006, 35(4), 617–652.

[14] David L.Donoho, Cornpressed sensing, IEEE Transactions on Information Theory, 2006, 52(4), 1289-1306

[15] Emmanuel Candes, Compressive sampling, Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006, 3, 1433-1452

[16] D.Baron,M.B.Wakin,S.Sarvotham,M.F.Duarte and R.GBaraniuk, Distributed compressive sensing, In Technical RePort,Pre-print,2005.

[17] D.Baron,M.F.Duarte, S.Sarvotham, M.B.Wakin and R.GBaraniuk. An Information Theoretic Approach to Distributed Compressed Sensing, Conference on Communication, Control, and Computing, Allerton, Sept. 2005

[18] M.F.Duarte, S.Sarvotham.D.Baron.M.B.Wakin and R.G.Baraniul, Distributed Compressed Sensing of Jointly Sparse Signals, Proceedings of the 39th Asilomar Conference on signals, systems and computation, 1537-1541, Pacific Grove, CA, Nov 2005.

[19]M.BWakin, S.Sarvotham, M.F.Duarte,D.Baron,and R.G.Baraniuk, Recovery of jointly Sparse Signals From Few Random Projections, Proceedings of the workshop on Neural Information Processing Systems, 1435-1442, Vancouver,Candada, Dec, 2005.

[20]J.Tropp, A.C.Gilbert,and M.J.Strauss, Simulataneous sparse approximation via greedy pursuit, in IEEE 2005 Int, Conf. Acousics, Speech, Signal Processing, Philadelphia, Mar, 2005.

[21]E. Candes, T. Tao, Near optimal signal reeovery from random projeetions: Universal encoding strategies. IEEE Transactions on Information Theory, 2006, 52(12), 5406-5425

[22] Zhang Wenbo, The algorithms research and applications of distributed compressed sensing, Beijing, 40-43, 2011

[23]Richard Baraniuk, Mark Davenport, Ronald DeVore, Michael Wakin, A simple proof of the restricted Isometry Property for random matrices, Construetive Approximation, Dee. 2008, 28(3), 253-263 [24]J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matehing Pursuit, IEEE Transactions on Information Theory, 2007, 53(12), 4655-4666