based on Distributed Compressed-Sensing20131009

By Tyler Simmons,2014-11-18 17:48
12 views 0
based on Distributed Compressed-Sensing20131009on,ON,based,Based,BASED

    A Detection Probability Localization Algorithm of Wireless

    Sensor Networks based on Distributed Compressed-


    Lin Shuo, Liu Wei


    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


    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 desired granularity of localization is itself application-dependent.

    Many of the applications and communication protocols of WSNs are based on the location information of sensor nodes, such as calculating the coverage of WSNs, tracking the location of events and intruders, geographic-based routing, and geocaching [1], [2]. Since a WSN usually consists of thousands of low-cost sensor nodes, it is not practical to equip each sensor node with a positioning device such as the Global Positioning System (GPS) [3], [4]. The range-based scheme determines the distance between two different sensor nodes based on a variety of information, such as Time of Arrival (TOA) [5], Time Difference of Arrival (TDOA) [6].

    Donho, Candes and Tao [7,8] establish the compressed sensing theory. 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 [9], D.Baron etc. first establish the basic concept and theory of distributed compressed-sensing, then and

    in [10] give the upper and lower of measurement value number, and the signal compressed rate of distributed compression-sensing theory.

    Wireless sensor network nodes generally use lithium batteries or alkaline batteries. For the limit node volume and application environment , the node itself brought the battery capacity is small , have stringent requirements on the network energy consumption wireless sensor network nodes in order to save energy communication distance is usually relatively short , usually from tens to two hundred meters , the entire network is achieved through the multi-hop communication network interconnection . General wireless network topology changes caused by the movement of the node, and the wireless sensor a network topology change is caused mainly due to the depletion of the node energy. 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.1Compressed 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 [11], and reduce 37.5% number of measurements in [12]. The process is as follows:

    MN<<()x denotes the length N sparse signal. Using a measurement matrix to calculate y which has


    yx (1)

    M;NΦWhere is measurement matrix.

    If x is a compression signal, the sampling process is can be expressed as follows:


    Θ=ΦΨM;NN;NΨWhere ,the size is . is 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:

    222(1)(1)?;Φ;+δδxxx01<<δ222, (3)

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

    reconstructing observed observed source signalsxˆsignalxsignalsysignalsyCompressedStorage andSignal


    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. Matrix

    MN;Φ;R, in which each element follows Gaussian distribution that means the mean value is 0 and the

    1/Mvariance is , can be expressed as follows

    1;;Φ:N0,ij,;;M;; (4)

    2.2Signal 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,

    ZZjcall of the original signal can be represented as a sparse public part and a unique part , so

    XZZjJ=+;1,2,,L{} (5)jcj

    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:

    ΦYX1)Input: Measurement matrix , measured value , sparsity K;

    Id=1,2,,L{}2)Output: Indices set;

    ˆrYx=?Φ1jI=;3)Initialize: Set indices set , iteration number t=1, initial iteration residual value;

    yrtt4)Normalize: Vector, get the coordinate value which is more than some specific value, so

    JjyTh=>:σ{}σtjttTht, where is the threshold in each iteration, is a corrected parameter;

5)Iteration steps:

    IIJ=;{}JttAdd coordinate value to I, ;

    Update iteration residual value


    ΦI Matrix is the sub-matrix which is composed by column of indices set I;


    6)If t<K, return (4), else end the iteration.


    3.DV-Hop Localization Algorithm Based on Detection Probability3.1Establish 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

    %dd=+εεikikikikunlocated node i is, where is the ranging error between the two points, and

    2εµσ~,Nξεµσ=?/~0,1N()()()ikikikikikikikBased on the knowledge of probability theory ,we know The form of a matrix of the system model can be expressed as

    %d?µikik~,1Nd()ikσik (6)

    XGD=+ξijii (7)






    The joint probability density function is as follows:


    PiWhere is the position of unlocated node i.

    22hhσσ=ikikikIn order to reflect the inter-node hops with ranging, it is assumed that , where is

    the number of hops between the reference node k and unlocated node i.

    3.2Collaborative Processing Method

    %%xy,()Determine the estimated coordinates of unlocated node by the weighted average


    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.

    ConfikFor node i, the credit of node k is , then the two nodes ranging error is


    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

    xy,()iithe anchor node with coordinates, the average distance per hop is estimated by the following equation:

    22xxyy?+?()();ijijji; (11)HopSize=ih;ijji;

    hxy,()iiijWhere, is the location of the anchor j, is the number of hops between the anchor node i and the

    HopSizeianchor node j. Once calculated, the estimated information is broadcasted into the network.

    3) The unknown node location can be estimated by the multilateration method when these nodes have

    TNxyin,1,2,,=L()iiithe distance estimations to at least three anchors. Given a set of reference nodes,

    TXxy,()where n is the number of anchors, let the hop value between the unknown node, and the i-th

    Rianchor is. Then the distance between the unknown node and i-th anchor node is given by

    d=rHopSizegiii. The unknown node location X can be found from:






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







    ?1TTXAAAb=()The least-squares estimate of X is.

    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. Fig.3 is C shaped random topology. 80 sensor nodes are deployed and 20 anchors in Fig. 4. Fig. 5 is illustrates C shaped gridy.;;点分布1000 Anchor900Node









    0 01002003004005006007008009001000

    Figure 2. Random deployment, 80 unknown nodes and 20 anchors.;;点分布1000 Anchor900Node800








    0 01002003004005006007008009001000

    ;;点分布Figure 3. C Shaped Random deployment, 40 unknown nodes and 5 anchors.1000 Anchor900Node800








    0 01002003004005006007008009001000

    ;;点分布Figure 4. Gridy network, 97 unknown nodes and 24 anchors.1000 Anchor900Node800








    0 01002003004005006007008009001000

    Figure 5. 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

    Average Random C Shaped Random Gridy C Shaped Gridy








    Table 2

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

    Average Random C Shaped Random Gridy C Shaped Gridy








    Table 3

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

    Average Random C Shaped Random Gridy C Shaped Gridy









    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.


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


    [1] T. He, C. Huang, B.M. Blum, J.A. Stankovic, and T. Abdelzher, .Range-Free Localization Schemes for Large Scale Sensor

    Networks,. Proc. ACM MobiCom ’03, pp. 81-95, Sept. 2003.

    [2] J.-P. Sheu, S.-C. Tu, and C.-H. Yu, .A Distributed Query Protocol in Wireless Sensor Networks,. Wireless Personal Comm.,vol. 41, no. 4, pp. 449-464, June 2007.

    [3] D. Niculescu and B. Nath, .Ad Hoc Positioning System (APS),. Proc. Global Telecomm. Conf. (Globecom ’01), vol. 1, pp. 2926-2931, Nov. 2001.

    [4] G.M. Djuknic and R.E. Richton, .Geolocation and Assisted GPS,.Computer, vol. 34, no. 2, pp. 123-125, Feb. 2001.

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

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

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

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

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

    [10] 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

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

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

Report this document

For any questions or suggestions please email