Abstract
In this semitutorial paper, the positioning problem is formulated as a convex feasibility problem (CFP). To solve the CFP for noncooperative networks, we consider the wellknown projection onto convex sets (POCS) technique and study its properties for positioning. We also study outerapproximation (OA) methods to solve CFP problems. We then show how the POCS estimate can be upper bounded by solving a nonconvex optimization problem. Moreover, we introduce two techniques based on OA and POCS to solve the CFP for cooperative networks and obtain two new distributed algorithms. Simulation results show that the proposed algorithms are robust against nonlineofsight conditions.
Keywords:
wireless sensor network; positioning algorithm; convex feasibility problem; projection onto convex sets; outer approximation1 Introduction
Wireless sensor networks (WSNs) have been considered for both civil and military applications. In every WSN, position information is a vital requirement for the network to be able to perform in practical applications. Due to drawbacks of using GPS in practical networks, mainly cost and lack of access to satellite signals in some scenarios, position extraction by the network itself has been extensively studied during the last few years. The position information is derived using fixed sensor nodes, also called reference nodes, with known positions and some type of measurements between different nodes [17]. From one point of view, WSNs can be divided into two groups based on collaboration between targets: cooperative networks and noncooperative networks. In cooperative networks, the measurements between targets are also involved in the positioning process to improve the performance.
During the last decade, different solutions have been proposed for the positioning problem for both cooperative and noncooperative networks, such as the maximum likelihood estimator (ML) [2,8], the maximum a posteriori estimator [9], multidimensional scaling [10], nonlinear least squares (NLS) [11,12], linear least squares approaches [1315], and convex relaxation techniques, e.g., semidefinite programming [12,16] and secondorder cone programming [17]. In the positioning literature, complexity, accuracy, and robustness are three important factors that are generally used to evaluate the performance of a positioning algorithm. It is not expected for an algorithm to perform uniquely best in all aspects [7,18]. Some methods provide an accurate estimate in some situations, while others may have complexity or robustness advantages.
In practice, it is difficult to obtain apriori knowledge of the full statistics of measurement errors. Due to obstacles or other unknown phenomena, the measurement errors statistics may have complicated distribution. Even if the distribution of the measurement errors is known, complexity and convergence issues may limit the performance of an optimal algorithm in practice. For instance, the ML estimator derived for positioning commonly suffers from nonconvexity [3]. Therefore, when solving using an iterative search algorithm, a good initial estimate should be chosen to avoid converging to local minima. In addition to complexity and nonconvexity, an important issue in positioning is how to deal with nonlineofsight (NLOS) conditions, where some measurements have large positive biases [19]. Traditionally, there are methods to remove outliers that need tuning parameters [20,21]. In [22], a nonparametric method based on hypothesis testing was proposed for positioning under LOS/NLOS conditions. In spite of the good performance, the proposed method seems to have limitations for implementation in a large network, mainly due to the complexity. For a good survey on outlier detection techniques for WSNs, see [23]. A different approach was considered in [24] where the authors formulated the positioning problem as a convex feasibility problem (CFP) and applied the wellknown successive projection onto convex sets (POCS) approach to solve the positioning problem. This method turns out to be robust to NLOS conditions. POCS was previously studied for the CFP [25,26] and has found applications in several research fields [27,28]. For noncooperative positioning with positively biased range measurements, POCS converges to a point in the convex feasible set (i.e., the intersection of a number of discs). When measurements are not positively biased, the feasible set can be empty, in which case POCS, using suitable relaxations, converges to a point that minimizes the sum of squared distances to a number of discs. In the positioning literature, POCS was studied with distance estimates [29] and proximity [30]. Although POCS is a reliable algorithm for the positioning problem, its estimate might not be accurate enough to use for locating a target, especially when a target lies outside the convex hull of reference nodes. Therefore, POCS can be considered a preprocessing method that gives a reliable coarse estimate. Modelbased algorithms such as ML or NLS can be initialized with POCS to improve the accuracy of estimation. The performance of POCS evaluated through practical data in [18,19] confirms these theoretical claims.
In this semitutorial paper, we study the application of POCS to the positioning problem for both noncooperative and cooperative networks. By relaxing the robustness of POCS, we can derive variations of POCS that are more accurate under certain conditions. For the scenario of positively biased range estimates, we show how the estimation error of POCS can be upperbounded by solving a nonconvex optimization problem. We also formulate a version of POCS for cooperative networks as well as an errorbounding algorithm. Moreover, we study a method based on outer approximation (OA) to solve the positioning problem for positive measurement errors and propose a new OA method for cooperative networks positioning. We also propose to combine constraints derived in OA with NLS that yields a new constrained NLS. The feasibility problem that we introduce in cooperative positioning has not been tackled in the literature previously. Computer simulations are used to evaluate the performance of different methods and to study the advantages and disadvantages of POCS as well as OA.
The rest of this paper is organized as follows. In Section 2, the system model is introduced, and Section 3 discusses positioning using NLS. In Section 4, the positioning problem is interpreted as a convex feasibility problem, and consequently, POCS and OA are formulated for noncooperative networks. Several extensions of POCS as well as an upper bound on the estimation error are introduced for noncooperative networks. In the sequel of this section, a version of POCS and outerapproximation approach are formulated for cooperative networks. The simulation results are discussed in Section 5, followed by conclusions.
2 System model
Throughout this paper, we use a unified model for both cooperative and noncooperative networks. Let us consider a twodimensional network with N + M sensor nodes. Suppose that M targets are placed at positions z_{i }∈ ℝ^{2}, i = 1,..., M, and the remaining N reference nodes are located at known positions z_{j }∈ ℝ^{2}, j = M + 1,..., N + M. Every target can communicate with nearby reference nodes and also with other targets. Let us define = {j reference node j can communicate with target i} and = {jj ≠ i, target j can communicate with target i} as the sets of all reference nodes and targets that can communicate with target i. For noncooperative networks, we set .
Suppose that sensor nodes are able to estimate distances to other nodes with which they communicate, giving rise to the following observation:
where d_{ij }= z_{i } z_{j} is the Euclidian distance between x_{i }and x_{j }and ϵ_{ij }is the measurement error. As an example, Figure 1 shows a cooperative network consisting of two targets and four reference nodes. Since in practice the distribution of measurement errors might be complex or completely unknown, throughout this paper we only assume that measurement errors are independent and identically distributed (i.i.d.). In fact, we assume limited knowledge of ϵ_{ij }is available. In some situations, we further assume measurement errors to be nonnegative i.i.d.
Figure 1. A typical cooperative network with two targets and four reference nodes.
The goal of a positioning algorithm is to find the positions of the M targets based on N known sensors' positions and measurements (1).
3 Conventional positioning
A classic method to solve the problem of positioning based on measurements (1) is to employ the ML estimator, which needs prior knowledge of the distribution of the measurement errors ϵ_{ij}. When prior knowledge of the measurement error distribution is not available, one can apply nonlinear least squares (NLS) minimization [31]:
where Ẑ = [ẑ_{1}, ..., ẑ_{M}]. Note that when , we find the conventional noncooperative LS [11].
The solution to (2) coincides with the ML estimate if measurement errors are zeromean i.i.d. Gaussian random variables with equal variances [31]. It has been shown in [11] that in some situations, the NLS objective function in (2) is convex, in which case it can be solved by an iterative search method without any convergence problems. In general, however, NLS and ML have nonconvex objective functions.
NLS formulated in (2) is a centralized method which may not be suitable for practical implementation. Algorithm 1 shows a distributed approach to NLS for (noncooperative networks.
Algorithm 1 CoopNLS
1: Initialization: choose arbitrary initial target position ẑ_{i }∈ ℝ^{2}, i = 1, ..., M
2: for k = 0 until convergence or predefined number K do
3: for i = 1,...,M do
4: update the position estimate of target i
5: end for
6: end for
To solve (3) using an iterative search algorithm, a good initial estimate for every target should be taken. To avoid drawbacks in solving NLS, the original nonconvex problem can be relaxed into a semidefinite program [16] or a secondorder cone program [17], which can be solved efficiently. Assuming small variance of measurement errors and enough available reference nodes, a linear estimator can also be derived to solve the problem that is asymptotically efficient [13,15,32].
4 Positioning as a convex feasibility problem
Iterative algorithms to solve positioning problem based on ML or NLS for a noncooperative network require a good initial estimate. POCS can provide such an estimate and was first applied to positioning in [24], where the positioning problem was formulated as a convex feasibility problem.
POCS, also called successive orthogonal projection onto convex sets [33] or alternative projections [34], was originally introduced to solve the CFP in [25]. POCS has then been applied to different problems in various fields, e.g., in image restoration problems [35,36] and in radiation therapy treatment planning [26]. There are generally two versions of POCS: sequential and simultaneous. In this paper, we study sequential POCS and refer the reader to [33] for a study of both sequential and simultaneous projection algorithms. If the projection onto each convex set is easily computed, POCS is a suitable approach to solve CFP. In general, instead of POCS, other methods such as cyclic subgradient projection (CSP) or Oettli's method can be used [33].
In this section, we first review POCS for the positioning problem and then study variations of POCS. We then formulate a version of POCS for cooperative networks. For now, we will limit ourselves to positive measurement errors and consider the general case later.
In the absence of measurement errors, i.e., , it is clear that target i, at position z_{i}, can be found in the intersection of a number of circles with radii d_{ij }and centres z_{j}. For nonnegative measurement errors, we can relax circles to discs because a target definitely can be found inside the circles. We define the disc centered at z_{j }as
It then is reasonable to define an estimate of z_{i }as a point in the intersection of the discs
Therefore, the positioning problem can be transformed to the following convex feasibility problem:
In a noncooperative network, there are M independent feasibility problems, while for the cooperative network, we have dependent feasibility problems.
4.1 Noncooperative networks
4.1.1 Projection onto convex sets
For noncooperative networks in (5). To apply POCS for noncooperative networks, we choose an arbitrary initial point and find the projection of it onto one of the sets and then project that new point onto another set. We continue alternative projections onto different convex sets until convergence. Formally, POCS for a target i can be implemented as Algorithm 2, where are relaxation parameters, which are confined to the interval for arbitrary small ϵ_{1}, ϵ_{2 }> 0, and determines the individual set [26]. In Algorithm 2, we have introduced , which is the orthogonal projection of z onto set . To find the
Algorithm 2 POCS
1: Initialization: choose arbitrary initial target position for target i
2: for k = 0 until convergence or predefined number K do
3: Update:
4: end for
projection of a point z ∈ ℝ^{n }onto a closed convex set Ω ⊆ ℝ^{n}, we need to solve an optimization problem [37]:
When Ω is a disc, there is a closedform solution for the projection:
where z_{j }is the center of the disc . When projecting a point outside of onto , the updated estimate based on an unrelaxed, underrelaxed, or overrelaxed parameter (i.e., , respectively) is found on the boundary, the outside, or the inside of the disc, respectively. For the , unrelaxed parameter, the POCS estimate after k iterations is obtained as
There is a closedform solution for the projection onto a disc, but for general convex sets, there are no closedform solutions [29,38], and for every iteration in POCS, a minimization problem should be solved. In this situation, a CSP method can be employed instead [33], which normally has slower convergence rate compared to POCS [33].
Suppose POCS generates a sequence . The following two theorems state convergence properties of POCS.
Theorem 4.1 (Consistent case) If the intersection of in (5) is nonempty, then the sequence converges to a point in the nonempty intersection .
Proof See Theorem 5.5.1 in [33, Ch.5].
In practical cases, some distance measurements might be smaller than the real distance due to measurement noise, and the intersection might be empty. It has been shown that under certain circumstances, POCS converges as in the following sense. Suppose be a steering sequence defined as [26]
Let m be an integer. If in (10) we have
then the steering sequence is called msteering sequence [26]. For such steering sequences, we have the following convergence result.
Theorem 4.2 (Inconsistent case) If the intersection of in (5) is empty and steered sequences defined in (11) are used for POCS in Algorithm 2, then the sequence converges to the minimum of the convex function .
Proof See Theorem 18 in [39].
Note that in papers [18,24,29], and [19], the cost function minimized by POCS in the inconsistent case should be corrected to the one given in Theorem 4.2.
One interesting feature of POCS is that it is insensitive to very large positive biases in distance estimates, which can occur in NLOS conditions. For instance, in Figure 2, one bad measurement with large positive error (shown as big dashed circle) is assumed to be a NLOS measurement. As shown, a large positive measurement error does not have any effect on the intersection, and POCS will automatically ignore it when updating the estimate. Generally, for positive measurement errors, POCS considers only those measurements that define the intersection.
Figure 2. POCS is able to remove very large positive bias (big dashed circle).
When a target is outside the convex hull of reference nodes, the intersection area is large even in the noiseless case, and POCS exhibits poor performance [37]. Figure 3 shows the intersection of three discs centered around reference nodes that contains a target's position when the target is inside or outside the convex hull of the three reference nodes. We assume that there is no error in measurements. As shown in Figure 3b, the intersection is large for the target placed outside the convex hull. In [29], a method based on projection onto hyperbolic sets was shown to perform better in this case; however, the robustness to NLOS is also lost.
Figure 3. Intersection of three discs that contains the position of a target, assuming no noise in measurements. a Target is inside the convex hull of reference nodes; b target is outside the convex hull of reference nodes. As shown, the intersection in b is very large compared to a.
4.1.2 Projection onto hybrid sets
The performance of POCS strongly depends on the intersection area: the larger the intersection area, the larger the error of the POCS estimate. In the POCS formulation, every point in the intersection area can potentially be an estimate of a target position. However, it is clear that all points in the intersection are not equally plausible as target estimates. In this section, we describe several methods to produce smaller intersection areas in the positioning process that are more likely to be targets' positions. To do this, we review POCS for hybrid convex sets for the positioning problem. In fact, here we trade the robustness property of POCS to obtain more accurate algorithms. The hybrid algorithms have a reasonable convergence speed and show better performance compared to POCS for lineofsight (LOS) conditions. However, the robustness against NLOS is partially lost in projection onto hybrid sets. The reason is that in NLOS conditions, the disc defined in POCS method contains the target node; however, for the hybrid sets, this conclusion is no longer true, i.e., the set defined in hybrid approach might not contain the target node.
Projection onto Rings: Let us consider the disc defined in (4). It is obvious that the probability of finding a target inside the disc is not uniform. The target is more likely to be found near the boundary of the disc. When the measurement noise is small, instead of a disc , we can consider a ring (or more formally, an annulus) defined as
where ϵ_{l }≥ 0, ϵ_{u }≥ 0, and the control parameter ϵ_{l }+ ϵ_{u }determines the width of the ring that can be connected to the distribution of noise (if available). Then, projection onto rings (POR) can be implemented similar to POCS, except the disc in Algorithm 2 is replaced with the ring . When ϵ_{l }= ϵ_{u }= 0, POR changes to a wellknown algorithm called Kaczmarz's method [33], also called algebraic reconstruction technique (ART) in the field of image processing [33,40], or the boundary projection method in the positioning literature [41], which tries to find a point in intersection of a number of circles. The ART method may converge to local optima instead of the global optimum [37]. The ring in (12) can be written as the intersection of a convex and a concave set, and respectively, defined by
so that
Hence, the ring method changes the convex feasibility problem to a convexconcave feasibility problem [42]. This method has good performance for LOS measurements when .
In some situations, the performance of POCS can be improved by exploiting additional information in the measurements [29,30]. In addition to discs, we can consider other types of convex sets, under assumption that the target lies in, or close to, the intersection of those convex sets. Note that we still have a convex feasibility problem. We will consider two such types of convex sets: the inside of a hyperbola and a halfplane.
Hybrid Hyperbolic POCS: By subtracting each pair of distance measurements, besides discs, we find a number of hyperbolas [29]. The hyperbola defined by subtracting measured distances in reference node j and k [29] divides the plane into two separated sets: one convex and one concave. The target is assumed to be found in the intersection of a number of discs and convex hyperbolic sets. For instance, for the target i,
where is the convex hyperbolic set defined by the hyperbola derived in reference node j and k [29]. Therefore, projection can be done sequentially onto both discs and hyperbolic sets. Figure 4 shows the intersection of two discs and one hyperbolic set that contains a target. Since there is no closedform solution for the projection onto a hyperbola, the CSP approach is a good replacement for POCS [33]. Therefore, we can apply a combination of POCS and CSP for this problem. Simulation results in [29] shows significant improvement to the original POCS when discs are combined with hyperbolic sets, especially when target is located outside the convex hull of reference nodes.
Figure 4. A network consisting of two reference nodes. The intersection of two discs centred at reference nodes and one hyperbolic set determines the position of the target.
Hybrid Halfplane POCS: Now we consider another hybrid method for the original POCS. Considering every pair of references, e.g., the two reference nodes in Figure 5, and drawing a perpendicular bisector to the line joining the two references, the whole plane is divided into two halfplanes. By comparing the distances from a pair of reference nodes to a target, we can deduce that the target most probably belongs to the halfplane containing the reference node with the smallest measured distance. Therefore, a target is more likely to be found in the intersection of a number of discs and halfplanes than in the intersection of only the discs. Formally, for target i, we have
Figure 5. A network consists of two reference nodes. Intersection of two discs centred at reference nodes and one halfplane determines the position of target.
where defines a halfplane that contains reference node j or k and is obtained as follows. Let a^{T}x = b, for a,x ∈ ℝ^{2}, and b ∈ ℝ, be the perpendicular bisector to the line joining reference nodes j and k, and suppose halfplanes {x ∈ ℝ^{2}a^{T}x > b} and {x ∈ ℝ^{2}a^{T}x ≤ b} contain reference nodes j and k, respectively. The halfplane containing the target i obtained as
There is a closedform solution for the projection onto the halfplane [33]; hence, POCS can be easily applied to such hybrid convex sets. In [30], POCS for halfplanes was formulated, and we used the algorithm designed there for the projection onto the halfplane in Section 5.
When there are two different convex sets, we can deal with hybrid POCS in two different ways. Either POCS is sequentially applied to discs and other convex sets or POCS is applied to discs and other sets individually and then the two estimates can be combined as an initial estimate for another round of updating. This technique is studied for a specific positioning problem in [38].
4.1.3 Bounding the feasible set
In previous sections, we studied projection methods to solve the positioning problem. In this section, we consider a different positioning algorithm based on the convex feasibility problem. As we saw before, the position of an unknown target can be found in the intersection of a number of discs. The intersection in general may have any convex shape. We still assume positive measurement errors in this section, so that the target definitely lies inside the intersection. This assumption can be fulfilled for distance estimation based on, for instance, time of flight for a reasonable signaltonoise ratio [43]. In contrast to POCS, which tries to find a point in the feasible set as an estimate, outer approximation (OA) tries to approximate the feasible set by a suitable shape and then one point inside of it is taken as an estimate. The main problem is how to accurately approximate the intersection. There is work in the literature to approximate the intersection by convex regions such as polytopes, ellipsoids, or discs [19,4446].
In this section, we consider a disc approximation of the feasible set. Using simple geometry, we are able to find all intersection points between different discs and finally find a smallest disc that passes through them and covers the intersection. Let , k = 1, ..., L be the set of intersection points. Among all intersection points, some of them are redundant and will be discarded. The common points that belong to the intersection are selected as . The problem therefore renders to finding a disc that contains and covers the intersection. This is a wellknown optimization problem treated in, e.g., [20,45]. We can solve this problem by, for instance, a heuristic in which we first obtain a disc covering and check if it covers the whole intersection. If the whole intersection is not covered by the disc, we increase the radius of disc by a small value and check whether the new disc covers the intersection. This procedure continues until a disc covering the intersection is obtained. This disc may not be the minimum enclosing disc, but we are at least guaranteed that the disc covers the whole intersection. A version of this approach was treated in [19].
Another approach was suggested in [45] that yields the following convex optimization problem:
where S_{p }is a unit simplex, which is defined as , and χ is the cardinality of set χ. The final disc is given by a center and a radius , where
Note when there are two discs , the intersection can be efficiently approximated by a disc, i.e., the approximated disc is the minimum disc enclosing the intersection. For , there is no guarantee that the obtained disc is the minimum disc enclosing the intersection [45].
When the problem is inconsistent, a coarse estimate may be taken as an estimate, e.g., the arithmetic mean of reference nodes as
Finally, we introduce a method to bound the position error of POCS for the positive measurement errors where the target definitely lies inside the intersection. In the best case, the error of estimation is zero, and in the worst case, the absolute value of position error is equal to the largest Euclidian distance between two points in the intersection. Therefore, the maximum length of the intersection area determines the maximum absolute value of estimation error that potentially may happen. Hence, the maximum length of the intersection defines an upper bound on the absolute value of position error for the POCS estimator. To find an upper bound, for instance for target i, we need to solve the following optimization problem:
The optimization problem (22) is nonconvex. We leave the solution to this problem as an open problem and instead use the method of OA described in this section to solve the problem, e.g., for the case when the measurement errors are positive, we can upper bound the position error with [found from (20)].
4.2 Cooperative networks
4.2.1 Cooperative POCS
It is not straightforward to apply POCS in a cooperative network. The explanation why follows in the next paragraph. However, we propose a variation of POCS for cooperative networks. We will only consider projection onto convex sets, although other sets, e.g., rings, can be considered.
To apply POCS, we must unambiguously define all the discs, , for every target i. From (4), it is clear that some discs, i.e., discs centered around a reference node, can be defined without any ambiguity. On the other hand, discs derived from measurements between targets have unknown centers. Let us consider Figure 6 where for target one, we want to involve the measurement between target two and target one. Since there is no prior knowledge about the position of target two, the disc centered around target two cannot be involved in the positioning process for target one. Suppose, based on applying POCS to the discs defined by reference nodes 5 and 6 (the red discs), we obtain an initial estimate ẑ_{2 }for target two. Now, based on distance estimate , we can define a new disc centered around ẑ_{2 }(the dashed disc). This new disc can be combined with the two other discs defined by reference nodes 3 and 4 (the black solid discs). Figure 6 shows the process for localizing target one. For target two, the same procedure is followed.
Figure 6. Initial estimate for target two, , can be obtained based on reference node five and six and then a new disc with radius can be defined, shown as a dashed circle, that can be involved to improve the position accuracy for target one.
Algorithm 3 implements cooperative POCS (CoopPOCS). Note that even in the consistent case, discs may have an empty intersection during updating. Hence, we use relaxation parameters to handle a possibly empty intersection during updating. Note that the convergence properties of Algorithm 3 are unknown and need to be further explored in future work.
4.2.2 Cooperatively bounding the feasible sets
In this section, we introduce the application of the outer approximation to cooperative networks. Similar to noncooperative networks, we assume that all measurement errors are positively biased. To apply OA for cooperative networks, we first determine an
Algorithm 3 CoopPOCS
2: for k = 0 until convergence or predefined number K do
3: for i = 1,...,M do
4: find ẑ_{i }with POCS such that
5: for m = 1,...,M do
6: if m is such that , then update sets as
7: end for
8: end for
9: end for
outer approximation of the feasible set by a simple region that can be exchanged easily between targets. In this paper, we consider a disc approximation of the feasible set. This disc outer approximation is then iteratively refined at every iteration finding a smaller outer approximation of the feasible set. The details of the disc approximation were explained previously in Section 4.1.3, and we now extend the results to the cooperative network scenario.
To see how this method works, consider Figure 7 where target two helps target one to improve its positioning. Target two can be found in the intersection derived from two discs centered around z_{5 }and z_{6 }in noncooperative mode (semi oval shape). Suppose that we outerapproximate this intersection by a disc (small dashed circle). In order to help target one to outerapproximate its intersection in cooperative mode, this region should be involved in finding the intersection for target one. We can extend every point of this disc by to come up with a large disc (big dashed circle) with the same center. It is easily verified that (1) target one is guarantee to be on the intersection of the extended disc and discs around reference nodes 3 and 4; (2) the outerapproximated intersection for target one is smaller than that for the noncooperative case. Note if we had extended the exact intersection, we end up with an even smaller intersection of target one. Cooperative OA (CoopOA) can be implemented as in Algorithm 4.
Figure 7. Extending the convex region involving target two to help target one to find a smaller intersection.
We can consider the intersection obtained in CoopOA as a constraint for NLS methods (CNLS) to improve the performance of the algorithm in (3). Suppose that for target i, we obtain a final disc as with center ẑ_{i }and radius . It is clear that we can define as a constraint for the ith target in the optimization problem (3). This problem can be solved iteratively similar to Algorithm 2 considering constraint obtained in CoopOA. Algorithm 5 implements CoopCNLS.
Algorithm 4 CoopOA
2: for k = 0 until convergence or predefined number K do
3: for i = 1,...,M do
4: find outer approximation (by a disc with center ẑ_{i }and radius ) using (20) or other heuristic methods such that
5: for m = 1,...,M do
6: if m is such that , then update sets as
7: end for
8: end for
9: end for
Algorithm 5 CoopCNLS
1: Run Algorithm 4 to obtain final discs
3: for k = 0 until convergence or predefined number K do
4: for i = 1,...,M do
5: Obtain the position of ith target using nonlinear LS as
6: end for
7: end for
5 Simulation results
In this section, we evaluate the performance of POCS for noncooperative and cooperative networks. The network deployment shown in Figure 8 containing 13 reference nodes at fixed positions is considered for simulation for both noncooperative and cooperative networks. In the simulation, we study two cases for the measurement noise: (1) all measurements are positive and (2) measurements noise can be both positive and negative. For positive measurement errors, we use an exponential distribution [47]:
Figure 8. Simulation environment consists of 13 reference nodes at fixed positions.
For the mixed positive and negative measurement errors, we use a zeromean Gaussian distribution, i.e., . In the simulation for both noncooperative and cooperative networks, we set γ = σ = 1 m. For every scenario (cooperative or noncooperative), we study both types of measurement noise, i.e., positive measurement noise and mixed positive and negative measurement errors. To compare different methods, we consider the cumulative distribution function (CDF) of the position error . For the noncooperative network, one target is randomly placed inside the network shown in Figure 8 in which we assume it can communicate with all reference nodes. For the cooperative network, 100 targets are randomly placed inside the area, i.e., in Figure 8, and we assume a pair of nodes, i.e., a pair of (target, reference) or a pair of (target, target), can connect and estimate the distance between each other if that distance is less than 20 m. To evaluate the NLOS condition, we add a uniform random variable to a measured distance in 20% of cases. For noncooperative and cooperative networks, we set U = 100 m and U = 20 m, respectively.
For implementation of POCS for a target in both cooperative and noncooperative networks, we run the algorithm for 10N_{a}, where N_{a }is the number of nodes connected to the target. In the simulation for inconsistent scenario, the relaxation parameters are first set to one, and after a given number k_{0 }of iteration, decrease as [29]
where [x] denotes the smallest integer greater than or equal to x. In the simulation, we set k_{0 }= 5N_{a}. To implement NLS for noncooperative and constrained NLS for cooperative networks (CoopNLS), we use the MATLAB routine lsqnonlin[48] initialized randomly and fmincon[48] initialized and constrained with outer approximation, respectively. For the cooperative network, every target broadcasts its estimates, i.e., a point or a disc, 20 times over the network.
For Gaussian measurement errors, the feasibility set might not be consistent. For the OA approach in this case, we take the average of (pseudo) reference nodes connected to a target as a coarse estimate. For hybrid approaches, we only study the combination of discs with halfplanes since it has not been studied previously and for other two methods introduced in Section 4.1.2, we refer the reader to [18,19,29].
5.1 Noncooperative positioning
In this section, we evaluate the performance of POCS, Hybrid Halfplane POCS, OA, NLS, and CLNS for both LOS and NLOS. Figure 9 depicts the CDFs for different methods for both positive and positivenegative measurement errors in LOS conditions. As can be seen, NLS has almost the best performance among all algorithms. Since the objective function for NLS in this scenario is convex (see [11]), NLS converges to the global minimum and outperforms other methods. For positive measurement errors, it is seen that POCS outperforms NLS for small position errors, i.e., e ≤ 1m. Combining discs with halfplanes improves the performance of the POCS for large errors. OA shows good performance compared to other methods. To summarize for LOS conditions, we see that NLS outperforms other methods except for very small position error when measurement errors are positive. For the positive measurement errors, the performance of POCS, HPOCS, and OA are compared in Table 1.
Figure 9. The CDFs of different algorithms for noncooperative network in LOS condition for a positive measurement errors (drawn from an exponential distribution) and both positive and negative measurement errors (drawn from a zeromean Gaussian distribution).
Table 1. Comparison between POCS, HPOCS, and OA for LOS conditions for positive measurement errors
To evaluate the robustness of different algorithms against NLOS conditions, we plot the CDFs of the various methods in Figure 10. We see that POCS and OA are robust against NLOS conditions for both scenarios. It is also seen that NLS has poor performance and the performance of NLS can be improved by involving the constraint derived from OA. The hybrid POCS, i.e., projection onto halfplanes and discs, has poor performance compared to POCS. The reason for the poor performance is that in NLOS conditions, the distance measured from a target to reference node i might be larger than the distance measured from the target to the reference node j even the target is closer to reference nodes i. Therefore, we might end up in the wrong halfplane which results in a large error. Here, we can compare different methods similar to LOS case and rank various algorithms and make some concluding remarks.
Figure 10. The CDFs of different algorithms for noncooperative network in NLOS condition for a positive measurement errors (drawn from an exponential distribution) and both positive and negative measurement errors (drawn from a zeromean Gaussian distribution).
To assess the tightness of the upper bound on the position error for POCS, derived in Section 4.1.3, we will investigate the difference between the upper bound, and the true error e_{i }= ẑ_{i}z_{i}. In Figure 11, we have plotted the CDF of the relative difference, i.e., , for positive measurement errors for LOS and NLOS conditions. As seen, the bound is not always tight. In fact, in more than 10% of the simulated scenarios, the upper bound is more then 25 times as large as the true error.
Figure 11. The CDF of normalized error in both LOS and NLOS for consistent case.
5.2 Cooperative positioning
In this section, we evaluate the performance of CoopPOCS, CoopOA, CoopNLS, and CoopCNLS for the cooperative network for both LOS and NLOS conditions. Figure 12 shows the CDFs of different algorithms for LOS conditions. As can be seen, CoopOA and CoopCNLS show good performance. CoopPOCS exhibits an acceptable performance, and CoopNLS has poor performance compared to the other methods. We also see that cooperation between targets can significantly improve the position estimates. In Table 2, we make a comparison between different methods for LOS conditions based on position error e.
Figure 12. The CDF of different algorithms for cooperative network (LOS) for a positive measurement errors (drawn from an exponential distribution) and both positive and negative measurement errors (drawn from a zeromean Gaussian distribution).
Table 2. Comparison between NonCoopPOCS, CoopPOCS, CoopOA, CoopNLS, and CoopCNLS for LOS conditions
To evaluate the performance of different methods in NLOS conditions, we plot the CDFs of various methods in Figure 13. As this figure shows, CoopOA outperforms other methods. Involving constraints of outer approximation to CoopNLS improves the performance of this nonlinear estimator.
Figure 13. The CDF of different algorithms for cooperative network (NLOS) for a positive measurement errors (drawn from an exponential distribution) and both positive and negative measurement errors (drawn from a zeromean Gaussian distribution).
6 Conclusion
In this semitutorial paper, the problem of positioning was formulated as a convex feasibility problem. For noncooperative networks, the method of projection onto convex sets (POCS) as well as outer approximation (OA) was employed to solve the problem. The main properties of POCS were studied and an upper bound on the position error, for the case when the distance estimation errors are positive, was found by solving a nonconvex optimization problem. Motivated by noncooperative networks, we derived two new distributed algorithms based on POCS and OA for cooperative networks. POCS and OA as preprocessing methods can provide reliable coarse estimates for modelbased positioning algorithms such as maximum likelihood or nonlinear least squares (NLS) estimator. We also proposed to combine constraints derived in OA with NLS yielding a new constrained NLS. Simulation results show that the proposed methods are robust against nonlineofsight conditions for both noncooperative and cooperative networks.
Competing interests
The authors declare that they have no competing interests.
Acknowledgements
Authors would like to sincerely thank Yair Censor, University of Haifa, for the valuable discussions and comments on the cooperativePOCS algorithm.
This work was supported by the Swedish Research Council (contract no. 20076363).
References

N Bulusu, J Heidemann, D Estrin, GPSless lowcost outdoor localization for very small devices. IEEE Pers Commun 7(5), 28–34 (2000). Publisher Full Text

N Patwari, J Ash, S Kyperountas, AO Hero, NC Correal, Locating the nodes: cooperative localization in wireless sensor network. IEEE Signal Process Mag 22(4), 54–69 (2005)

M Rydström, "Algorithms and Models for Positioning and Scheduling in Wireless Sensor Networks" (Chalmers University of Technology, 2008) (Ph, 2008), . D. dissertation

AH Sayed, A Tarighat, N Khajehnouri, Networkbased wireless location: challenges faced in developing techniques for accurate wireless location information. IEEE Signal Process Mag 22(4), 24–40 (2005)

S Gezici, A survey on wireless position estimation. Wirel. Pers Commun 44(3), 263–282 (2008). Publisher Full Text

S Gezici, Z Tian, GB Giannakis, H Kobayashi, AF Molisch, HV Poor, Z Sahinoglu, Sahinoglu, Localization via ultrawideband radios: a look at positioning aspects for future sensor networks. IEEE Signal Process Mag 22(4), 70–84 (2005)

G Mao, B Fidan, Localization Algorithms and Strategies for Wireless Sensor Networks ( (Information Science Reference, Hershey, New York, 2009)

X Sheng, Y Hu, Maximum likelihood multiplesource localization using acoustic energy measurements with wireless sensor networks. IEEE Trans Signal Process 53(1), 44–53 (2005)

H Wymeersch, J Lien, MZ Win, Cooperative localization in wireless networks. Proc. IEEE 97(2), 427–450 (2009)

JA Costa, N Patwari, AO Hero, Distributed weightedmultidimensional scaling for node localization in sensor networks. ACM Trans Sens Netw 2(1), 39–64 (2006). Publisher Full Text

G Destino, G Abreu, Reformulating the leastsquare source localization problem with contracted distances. Proceeding of the Asilomar, 307–311 (2009)

J Nie, Sum of squares method for sensor network localization. Comput Optim Appl 43, 151–179 (2009). Publisher Full Text

M Sun, KC Ho, Successive and asymptotically efficient localization of sensor nodes in closedform. IEEE Trans Signal Process 57(11), 4522–4537 (2009)

X Wang, Z Wang, B O'Dea, A TOAbased location algorithm reducing the errors due to nonlineofsight (NLOS) propagation. IEEE Trans Veh Technol 52(1), 112–116 (2003). Publisher Full Text

C Meesookho, U Mitra, S Narayanan, On energybased acoustic source localization for sensor networks. IEEE Trans. Signal Process 56(1), 365–377 (2008)

P Biswas, TC Lian, TC Wang, Y Ye, Semidefinite programming based algorithms for sensor network localization. ACM Trans Sens Netw 2(2), 188–220 (2006). Publisher Full Text

S Srirangarajan, A Tewfik, ZQ Luo, Distributed sensor network localization using SOCP relaxation. IEEE Trans Wirel Commun 7(12), 4886–4895 (2008)

MR Gholami, EG Ström, M Rydström, Indoor sensor node positioning using UWB range measurements. Proceeding of the 17th European Signal Processing Conference (Eusipco), 1943–1947 (2009)

MR Gholami, EG Ström, F Sottile, D Dardari, S Gezici, M Rydström, MA Spirito, A Conti, Static positioning using UWB range measurements. Proceeding of the Future Network and Mobile Summit (2010)

S Boyd, L Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004)

PJ Rousseeuw, AM Leroy, Robust Regression and Outlier Detection (Wiley, New York, 1987)

G Destino, D Macagnano, G Abreu, Hypothesis testing and iterative WLS minimization for WSN localization under LOS/NLOS conditions. Proceeding of the IEEE 41st Asilomar Conference on Signals, Systems and Computers, 2150–2155 (2007)

Y Zhang, N Meratnia, P Havinga, Outlier detection techniques for wireless sensor networks: a survey. IEEE Commun Surv Tutor 12(2), 159–170 (2010)

AO Hero, D Blatt, Sensor network source localization via projection onto convex sets (POCS). Proceeding of the IEEE International Conference on Acoustics, Speech and Signal Processing (Philadelphia, 2007) 3, pp. 689–692

LG Gubin, B Polyak, E Raik, The method of projection for finding the common point of convex sets. USSR Comput. Math Math Phys 7, 1–24 (1967)

Y Censor, A Segal, Iterative projection methods in biomedical inverse problems. in Proceeding of the interdisciplinary workshop on Mathematical Methods in. Biomedical Imaging and IntensityModulated Radiation Therapy (IMRT) (Pisa, 2008), pp. 65–96

DC Youla, H Webb, Image restoration by the method of convex projections: Part 1theory. IEEE Trans Med Imaging 1(2), 81–94 (1982). PubMed Abstract  Publisher Full Text

GT Herman, LB Meyer, Algebraic reconstruction techniques can be made computationally efficient [positron emission tomography application]. IEEE Trans Med Imaging 12(3), 600–609 (1993). PubMed Abstract  Publisher Full Text

M Rydström, EG Ström, A Svensson, Robust sensor network positioning based on projection onto circular and hyperbolic convex sets. Proceeding of the IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp, 1–5 (2006)

MR Gholami, M Rydström, EG Ström, Positioning of node using plane projection onto convex sets. Proceeding of the IEEE Wireless Communication and Networking Conference (WCNC) (Apr (2010)

SM Kay, Fundamentals of Statistical Signal Processing: Estimation Theory (PrenticeHall, Upper Saddle River, 1993)

A Beck, P Stoica, J Li, Exact and approximate solutions of source localization problems. IEEE Trans Signal Process 56(5), 1770–1778 (2008)

Y Censor, SA Zenios, Parallel Optimization: Theory, Algorithms, and Applications (Oxford University Press, New York, 1997)

S Boyd, J Dattorro, "Alternating projections". [http://www.stanford.edu/class/ee392o/alt_proj.pdf] webcite

P OskouiFard, H Stark, Tomographic image reconstruction using the theory of convex projections. IEEE Trans Med Imaging 7(1), 45–58 (1988). PubMed Abstract  Publisher Full Text

DC Youla, H Webb, Image restoration by the method of convex projections: Part 1theory. IEEE Trans Med Imaging 1(2), 81–94 (1982). PubMed Abstract  Publisher Full Text

D Blatt, AO Hero, Energybased sensor network source localization via projection onto convex sets. IEEE Trans Signal Process 54(9), 3614–3619 (2006)

MR Gholami, S Gezici, EG Strom, M Rydstrom, A distributed positioning algorithm for cooperative active and passive sensors. Proceeding of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) (2010)

Y Censor, AR De Pierro, M Zaknoon, Steered sequential projections for the inconsistent convex feasibility problem. Nonlinear Anal Theory Method Appl Series A 59, 385–405 (2004)

C Byrne, Blockiterative algorithms. Int Trans Oper Res, 427–463 (2009)

J Wang, PA Regalia, Sensor network localization via boundary projections. Proceeding of the 43rd Annual Conference on Information Sciences and Systems, 224–229 (2009)

Y Censor, DE Gustafson, A Lent, H Tuy, A new approach to the emission computerized tomography problem: simultaneous calculation of attenuation and activity coefficients. IEEE Trans Nucl Sci NS26, 2775–2779 (1979)

S Marano, WM Gifford, H Wymeersch, MZ Win, Nonparametric obstruction detection for UWB localization. Proceeding of the IEEE Global Communication Conference, 1–6 (2009)

L Doherty, KSJ Pister, LE Ghaoui, Convex position estimation in wireless sensor networks. INFOCOM 2001 3, 1655–1663 (2001)

A Beck, On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls. J Global Optim 39, 113–126 (2007). Publisher Full Text

MR Gholami, H Wymeersch, EG Strom, M Rydstrom, Robust distributed positioning algorithms for cooperative networks. Proceeding of the 12th IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) (San Francisco, 2011), pp. 156–160 2629

PC Chen, A nonlineofsight error mitigation algorithm in location estimation. Proceeding of the IEEE Wireless Communications and Networking Conference 1, 316–320 (1999)

The Mathworks Inc. [http://www.mathworks.com] webcite