TMCnet News

A Relative Positioning Technique with Spatial Constraints for Multiple Targets Based on Sparse Wireless Sensor Network [Sensors & Transducers (Canada)]
[April 22, 2014]

A Relative Positioning Technique with Spatial Constraints for Multiple Targets Based on Sparse Wireless Sensor Network [Sensors & Transducers (Canada)]


(Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: Many applications of wireless sensor network require precise knowledge of the locations of nodes. Conventional sparse wireless sensor network, which is formed by a restricted number of nodes, has two drawbacks, i.e., low connective ratio and hop count limited, which probably cause the network link failure and/or low locating performance. To improve the relative position precision and reliability of multiple targets based on the sparse wireless sensor network, a relative locating method with spatial constraints is proposed according to the different network configuration and inter-range between target nodes for the sparse wireless sensor network, of which the spatial constraint benchmarks include two categories of datum, namely, the spatial absolute displacement datum and direction rotation datum. In particular, it is proven on the basis of the principle of survey adjustment that the nodes' position ambiguity, which is caused by the rank deficiency, could be solved while the estimating precision of the target nodes position is unchanged. The simulation results show that compared to the conventional time-varying filtering, e.g. Kalman Filtering, the proposed constraint position method may rapidly respond to network-link communication failure, and increase relative positioning precision about 32.9 % via introducing the spatial constraint benchmarks. Copyright © 2013 IFSA.



Keywords: Wireless sensor network, Multiple targets, Relative position, Spatial constraint, Position benchmark, Kalman Filtering.

(ProQuest: ... denotes formulae omitted.) 1. Introduction With the rapid development of microelectromechanical system, wireless communication system and low-power embedded system, wireless sensor network (WSN) come into being [1], of which sea-surface wireless sensor network (S2WSN) are regarded as a special communication networks consisting of a number of ships and buoys, namely, multiple targets, according to a certain communication protocols. Through radio technology, these targets communicate with each other, which may implement cooperative observation, cooperative communication and cooperative remote sensing for environment in times of exterior location benchmarks (like global positioning system, GPS) outages or in these benchmarks denied sea areas. These WSN are expected to form the backbone of future intelligent networks for a broad range of applications such as underwater surveillance and traffic monitoring.


For most applications of the WSN, multiple-target localization is one of the most challenging and important issues, because the location information is typically useful for coverage, deployment, routing, location service, target tracking, and rescue operations in WSN.

In the development of ocean resource, utilizing WSN together with engineering boat, ocean drilling platform and underwater robot to collaboratively determine the target location, can improve the precision of underwater pipeline laying, oilfield mining and waterway dredging [2], In salvaging the crash ship and aircraft, using the WSN and the engineering boat to collaboratively determine the position of black box for ship and/or aircraft, can improve the precision and efficiency of underwater salvage. In enforcing oceanic law, using WSN positioning technology can improve the timeliness and accuracy of sea police deployment.

As for space environment monitoring, maneuvering status of flying vehicles (FVs) may be described in detailed through cooperative positioning among the S2WSN and the FVs. As such, they have superior positioning precise and reliability during tracking the FVs in the bad ocean environment because they can automatically deploy nodes and deal with the communication malfunction among the nodes when some network nodes fail or new nodes become a member of the network.

The remainder of this paper is organized as follows. Section 2 introduces the relevant work about relative positioning method for multiple targets based on WSN. In Section 3, we describe the basic principle of relative positioning on basic of the sparse distributed WSN (SWSN). Section 4 deduces the mathematical model of constraint position for the SWSN. Section 5 presents simulation results to verify the effectiveness of the proposed algorithm. Finally, Section 6 summarizes the contributions and concludes the paper.

2. Relevant Work As to the features of modem WSN with large node number and huge network scale, the positioning algorithms proposed currently for multiple targets have many superior performances, such as low energy consumption, low dependence, strong robustness and high adaptability.

Xing and Jian considered cooperative positioning using acoustic range measurements for underwater sensor networks, including networks formed by autonomous unmanned underwater vehicles. Severe multipath scattering from the seabed and sea surface can result in inaccurate range measurements. In an inhomogeneous medium, such as sea water, the direct path was not necessarily the strongest path or the first arrival. Then, the range measurements based on the first or strongest arrival could be significantly biased. Xing and Jian introduce herein a centralized cooperative positioning algorithm for underwater multiple targets, referred to as the weighted Gerchberg-Saxton algorithm (WGSA). The proposed algorithm assumed that for each acoustic ranging channel, multiple range measurements corresponding to several propagation paths, one of which was the direct path, were available for cooperative positioning. The WGSA can be used to automatically identify the direct path [3].

He et al. presented multiple target localization via compressed sensing in the WSN. The multiple target localization issue was transformed into compressed sensing issue by designing iteration backtracking algorithm using multi-resolution analysis idea. The achievement of this algorithm was to save the energy of WSN nodes, by minimizing inter-node communication, in the result of which the lifetime of the WSN was prolonged, at the cost of increasing the computation complexity in the fusion center instead. However, the time complexity of the algorithm was increased [4], An ultra-wideband 3-D positioning technique was described for locating wireless sensor nodes in extreme multipath environments [5]. They typically constructed part of a network of sensors used to monitor salient parameters such as temperature and humidity in large industrial storage vessels. The novelty of this approach was twofold. First, a leading ultra-wideband pulse edge detection method was combined with a series of spatially diverse measurements to isolate the line-of-sight (LOS) component from the unwanted multipath interference from the vessel walls. Second, a new location algorithm based on the statistical analysis of spherical function intersection points was applied to the received time-domain data to improve the estimation of the time of flight at each measurement location. These two features combined to facilitate both precision positioning and cumulative error source estimation and yielded resolutions approaching 2 cm in rich scattering environments.

Literature [6] described mobile anchor positioning, a range-free positioning method, which made use of the beacon packets of mobile anchor and the location packets of neighbor nodes to calculate the location of the nodes. The anchor node, which was equipped with global positioning system, e.g., GPS, broadcasts its coordinates to the sensor nodes as it moved through the network. As the sensor nodes collect enough beacons, they were able to calculate their locations locally.

But for sea-surface wireless sensor networks, the network connectivity and single-hop distance was low because of ocean dynamic environment, sea clutter, and other influences. Therefore, to solve this problem, we need to improve their network density or increase the antenna height, etc.

As to the WSN constructed by flying vehicles, the high-density network in the air can't be random deployed on account of ground control, aircraft loading, cost and other factors. Meanwhile, caused by antenna scope, transmission media, costs and other influence, this type of sensor was difficult to implement through multi-hop mesh to improve connectivity and reliable relative positioning.

Generally, through the deployment of a limited number of nodes according to a certain spatial configuration to accomplish specific tasks, this WSN is named as a sparse distributed WSN (SWSN) in this paper. Based on the distribution characteristics of the SWSN, we propose a relative positioning algorithm for multiple targets based on spatial constraints, which is named as RPSC. In benchmark denied sea areas and unavailable solving location parameters of the target nodes, the SWSN network reliability and precision of relative positioning may be improved by introducing spatial constraints and spatial correlation conditions of the SWSN. Furthermore, the effectiveness of the algorithm is testified by Monte Carlo simulation.

3. The Basic Principle of Relative Positioning for Multiple Targets Without loss of generality, taking a sea-surface SWSN with four sensors, namely, four nodes or targets, as an example for collaborative task, the state equation of the SWSN can be expressed as ... (1) where X=\X^ X2 X$ X^ , and Xi denote the state vectors of four sea-surface sensors, i.e., Xi=[xi x, xi y¿ ÿi yi ¿i '¿if, (x,y,z) are the position components of the surface sensor, while (i, j,z)are the velocity components and (x,ÿ,z) are the acceleration components. F is the state transition matrix. While, U is the input matrix and W is the system process noise, which is assumed to be a zeromean Gaussian white noise. It is worth noting that literature gives its adaptive variance Q as follows [7].

... (2) where a is the reciprocal of the maneuver (acceleration) time constant and Q0 is an initial value of adaptive variance Qt * For example, a «1/60 for a lazy turn, a «1/20 for an evasive maneuver, and a « 1 for atmospheric turbulence.

The localization protocols are classified into two categories: range-based protocol and range-free protocol. The range-based protocols employ distance or angle estimation techniques to achieve fine accuracy, which require the use of expensive hardware. On the other hand, the range-free techniques depend on the contents of received messages to support coarse accuracy. Currently, available observation information for positioning SWSN has time of arrival (TOA), time difference of arrival (TDOA), received signal strength indicator (RSSI), frequency difference of arrival (FDOA) and other forms [8-9], commonly using TDOA. Therefore, taking a SWSN based on TOA among the target nodes as an example for following discussions, the relative distance measurements among the nodes are ... (3) where (x,y,z).. (í* j and i, j = 1, 2, . . ., 4) are the coordinates of the SWSN. Then, the nonlinear observing equation is written as ... (4) where Zk=\f]2 r\3> r\A r4i] > which is the measurement vector, and is the measurement noise, which is assumed to be a zero mean white Gaussian noise vector with covariance matrix R(k).

Converting equation (4) into linear format, it yields the error equation as follows: ... (5) where A is measurement equation ...

4. The Mathematical Model of Constraint Position for SWSN Using relative distance observations rij among sensors for independent relative positioning, if the ranging links of the sensor were uninterrupted, we may attain 12 range measurements. Fortunately, this number is equal to the number of unknown coordinates of the four sensors, while meets the requirements of the necessary number of observations [10]. The transmission links between the target nodes are easily unlocked, furthermore, reducing the connectivity on account of transmission media, node attitude, atmosphere, oceans environment, and other influences. At this moment, without loss of generality, setting u as the number of the coordinates parameters for the whole SWSN nodes while t as the necessary number of observations in solving equation (5), the rank of the measurement matrix A is rank(yá) = t<u, and the number of rank deficiency =u-t.

According to the principle of least squares V PV = min , where P is nonsingular empowering matrix, the norm equation is written as ... (6) where W=AJPL, and rank(A) = rank(ylT/M) = t <u . The normal equation has many infinite solutions while N is singular.

In order to achieve the only solution of the unknown parameters, the constraint condition of the given datum ST is ... (7) where rank(S) = d , and AS = 0 . Left multiplying AS by AtP , we can attain (ArPA)S = NS = 0 , where 5T is row full rank. Px is named as the datum weight, and the different Px reflects the differences in datum constraints [10-11].

Generally, when SWSN conducts collaborative detection mission, e.g., underwater surveillance, they must maintain a required geometry configuration by some control methods. In other words, the SWSN topology is correlated in adjacent moments. According to the above-mentioned assumption, two categories of spatial benchmark conditions are defined.

a) Absolute displacement benchmark. As shown in Fig. 1, the solid lines denote the position lines of the sensors before adjustment, while the dashed lines after adjustment. Point O' is the virtual centroid.

Then, the absolute displacement datum condition means that the sums of displacement values before and after adjustment are equal to zeros in the respective axis. That is represented as ... (8) where ( x , y., z. ) are the displacement values of position adjustments.

b) Direction rotation benchmark condition. As shown in Fig. 2, 0i (i = I, 2, ... , 4) are the relative rotation angles centering at virtual centroid after position adjustment.

The direction benchmark means that the sums of direction rotation angles before and after adjustment are equal to zeros in the respective coordinate plane. That is ... (9) where ( xf,yf,zf ) denote the approximate coordinates, i.e., the system output at moment k~ 1.

It follows that equation (8) and equation (9) can be uniformly represented as ... (10) According to the aforementioned six benchmark conditions, the coefficient matrix S is given by ... (11) According to the different measurements and the configurations of the SWSN, Table 1 lists the general expression of the corresponding constraint benchmark S.

According to the above constraint datum S and the principle of least squares, setting the function ... we can achieve the following equations [11].

... (12) where K is the coefficient matrix. Left multiplying the first equation in equation (12) by ST , and considering AS = 0 and NS = 0, we can attain ... (13) For the quadratic form STPXS can't be equal to zero, the matrix K= 0 in equation (13). Obviously, (p = V1 PV = min .

It is concluded that the solving nature of the relative positioning of the SWSN is unrelated with the additional constraint datum S of the unknown parameters, namely, VTPV is an invariant, and the correction value V obtained from solving isn't changed with the different constraint benchmark. In other words, under the condition without changing the final arguments precision, through introducing the spatial constraint benchmark, the numerous solutions problem of the measurement equation is overcome due to lack of benchmark, namely, solving ambiguity.

Left multiplying the second equation in equation (12) by PXS , then adding the first equation of equation (12), considering K= 0, we can attain ... (14) At this moment, coefficient matrix (N + PXSSTPx) is full rank. Setting matrix Qp as Qp = (N + PXSSTPx)~', the final estimates of node localization parameters is ... (15) 5. Simulation and Analysis To validate the effectiveness of the proposed positioning algorithm with benchmark constraint, we set a Monte Carlo simulation with 500 times. The four target nodes are deployed to a rectangle. The simulation lasts for 2250 s with a 1-s sampling interval. During 1-800 and 1743-2250 s, the SWSN maneuver in a straight line at constant velocity. During 801-1742 s, the SWSN maneuver in a semicircle with a rotating speed of 0.19deg/s. The initial position of node No. 1 is (10, 0, 0) km, with an initial velocity of (-15, 0, 0) m/s. The precision of the two-way ranging is 1.0 m while the precision of the velocity measuring is 0.2 m/s. The influence of the ocean current or air turbulence is 0.5 m.

Table 2 lists the statistic value of the nodes' tracking error responding to the environmental influence by the proposed algorithm compared with the conventional Kalman filtering (KF). Fig. 3 shows the tracking error of the virtual centroid as to the different positioning algorithms.

From Fig. 3, it is shown that the RPSC algorithm has similar tracking performance to that of the conventional KF method when the SWSN maneuver in a straight line with constant velocity. During 1800 s, the two methods have approximately equal root-mean-square errors (RMSE) for tracking. However, when maneuvering in a semicircle, the KF method has an obviously sudden change compared with the RPSC algorithm, particularly at the starting point of semicircular motion, e.g., at 801 s. However, at this moment the RPSC algorithm uses spatial constraint benchmarks and the virtual centroid O ' of the SWSN tracks the sudden maneuvering timely.

As shown in Table 2 and Fig. 3, at 801s, the tracking error of RPSC is 2.37 m. The tracking accuracy of the RPSC algorithm increases by 32.9 % compared to the KF method with a 1.58 m precision.

In order to verify the processing performance of the RPSC algorithm to deal with communication failure, a communication failure is assumed in a node, i.e., No. 1. The simulation lasts for 200 s with a 1-s sampling interval. The SWSN maneuvers with a constant velocity of 20 m/s, and other simulation parameters are not changed. During 70-120 s, an external interference is added to node No. 1, and the ranging signal is unlocked in the network consequently. Fig. 4 shows the tracking error of the four target nodes.

Fig. 4 shows that, when node No. 1 loses synchronization at 70 s due to communication failure, its positioning error is suddenly deteriorated to a scale of [9.2-12.8] m. Other nodes affected by the inter-ranging error have a about 5-m positioning precision. After about 6 s, by receiving a signal-tonoise ratio (SNR), the RPSC algorithm determines communication failure, deletes the wrong information of the node No. 1. Then, the algorithm continuously locates the rest nodes while increasing the positioning precision.

At 120 s, after repairing the ranging equipment of the node No. 1, the RPSC algorithm timely utilizes the relative measurements among the four nodes to accomplish positioning mission and the positioning precisions of the four nodes are all recovered to the scale before communication failure. If by filtering technology to calculate the nodes' positions, we may judge the sudden changes of the SWSN nodes with the sensor fault detection algorithm according to the filtering gain [12].

6. Conclusions To improve the precision and reliability of relative positioning for the multiple targets based on the SWSN, this paper proposes a relative positioning method on basic of space constraints by introducing a spatial constraint condition to solve ambiguity of the relative positioning due to missing benchmark. Compared with the common methods, e.g., Kalman filtering, the proposed RPSC algorithm, which utilizes graphical topological conditions among target nodes by introducing a spatial constraint benchmarks, can achieve a continuous tracking of nodes while SWSN network responds to environmental sudden change. The relative positioning accuracy is around 32.9 % and relative position deviation is less than 3 m.

The RPSC algorithm can respond timely to communication link failure. When a node is destroyed, it is able to remove the node, which ensures the reliability of relative positioning for the multiple targets. It is to note particularly that we only consider how to improve the locating performance from the spatial constraints in this paper, actually, SWSN also has some statistical correlation in the time domain when the multiple targets maneuvering.

In the future, we may integrate the spatial-domain benchmark with the time-domain constraint to enhance the positioning performance for the targets according to a priori movement statistics information.

Acknowledgements This work was supported by the National Science Foundation under Grant 61071006, by the National Science Foundation for Post-doctoral Scientists of China (Grant No. 22012T50871, 20110490189), by Open Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing under Grant 10P03, and by the Start Fund of Liaoning Province Doctor under Grant 20101130.

References [1]. Y. Jennifer, M. Biswanath, G. Dipak, Wireless sensor network survey, Computer Network, Vol. 52, Issue 12,2008, pp. 2292-2330.

[2]. S. D. Moreno, A. M. Pascoal, J. Aranda, Optimal sensor placement for underwater positioning with uncertainty in the target location, in Proceeding of the IEEE International Conference on Robotics and Automation, Shanghai, China, 9-13 May 2011, pp. 2308-234.

[3]. T. Xing, L. Jian, Cooperative positioning in underwater sensor networks, IEEE Transactions on Signal Processing, Vol. 58, Issue 11, 2010, pp. 5860-5871.

[4]. F. H. He, Z. J. Yu, H. T. Liu, Multiple target localization via compressed sensing in wireless sensor networks, Journal of Electronics & Information Technology, Vol. 34, Issue 3, 2012, pp. 716-721.

[5]. G. D. John, S. Robin, J. P. Anthony, A threedimensional positioning algorithm for networked wireless sensors, IEEE Transactions on Instrumentation and Measurement, Vol. 60, Issue 6, 2011, pp. 1423-1432.

[6]. W. H. Liao, Y. C. Lee, S. P. Kedia, Mobile anchor positioning for wireless sensor networks, IET Communications, Vol. 5, Issue 7,2011, pp. 914-921.

[7]. R. A. Singer, Estimating optimal tracking filter performance for manned maneuvering targets, IEEE Transactions on Aerospace and Electronic Systems, Vol. 6, Issue 4, 1970, pp. 473-483.

[8]. M. Sun, K. C. Ho, An asymptotically efficient estimator for TDOA and FDOA positioning of multiple disjoint sources in the presence of sensor location uncertainties, IEEE Transactions on Signal Processing, Vol. 59, Issue 7,2011, pp. 3434-3440.

[9]. L. Bin, Z. G. Zhang, S. C. Chan, DOA estimation and tracking of ULAS with mutual coupling, IEEE Transactions on Aerospace and Electronic Systems, Vol. 48, Issue 1,2012, pp. 895-901.

[10]. W. M. Xu, L. L. Kuang, J. H. Lu, Positioning algorithm with joint space-time constraints for unmanned network-flying vehicles, IEEE Transactions on Geoscience and Remote Sensing, Vol. 47, Issue 8,2009, pp. 2694-2704.

[11]. X. Z. Cui, Z. C. Yu, B. Z. Tao, Generalized surveying adjustment, 1st edition, Wuhan Surveying & Mapping University Press, Wuhan, 2001.

[12]. C. M. Hajiyev, F. Caliskan, Fault detection in flight control systems based on the generalized variance of the Kalman filter innovation sequence, in Proceeding of the American Control Conference, San Diego, California, USA, 2-4 June 1999, pp. 109-113.

Weiming XU, Xiaodong YIN, Zhuzi HE, Tianyang LIU Department of Hydrography and Cartography, Dalian Naval Academy, 116018, Dalian, Liaoning, P. R. China Tel.:+86-411-858-56438 E-mail: [email protected] Received: 18 September 2013 /Accepted: 25 October 2013 /Published: 30 November 2013 (c) 2013 International Frequency Sensor Association

[ Back To TMCnet.com's Homepage ]