based on Distributed Compressed-Sensing20131009

By Tyler Simmons,2014-11-18 17:48
10 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.