Position location techniques and applications - Part 2: Ad hoc and sensor network scenarios

If the data are known to be well described by a particular statistical model (e.g., Gaussian or M-Erlang), then the ML estimator can be derived and implemented [63]. One reason that the ML estimators are used is that their variance asymptotically approaches the lower bound given by the Cramer-Rao bound (CRB). In this kind of estimator, the maximum of the likelihood function must be found. There are two difficulties with this approach.

1. Local maxima: Unless we initialize the ML estimator to a value close to the correct solution, it is possible that our maximization search may not find the global maxima.

2. Model dependency: If measurements deviate from the assumed model, the results are no longer guaranteed to be optimal.

One way to prevent local maxima is to formulate the localization as a convex optimization problem. In Doherty et al. [19], convex constraints are presented and can be used to require a node location estimate to be within radius r and/or angle range [α1, α2] from a second node. Multidimensional scaling (MDS) algorithms [76] formulate sensor localization from range measurements as a least-squares (LS) problem. In classical MDS, the LS solution is found by eigendecomposition,which does not suffer from local maxima. To linearize the localization problem, the classical MDS formulation works with squared distance rather than distance itself, and the end result is very sensitive to range measurement errors.

Distributed Algorithms
Distributed algorithms have two advantages. First, for some applications, no central processor is available to handle the calculations. Second, when a large network must forward all measurement data to a single central processor, there is a communication bottleneck and higher energy drain at and near the central processor. Distributed algorithms for cooperative localization generally fall into one of two schemes.

Classical multilateration: Each sensor estimates its multihop range to the nearest land-reference nodes. These ranges can be estimated via the shortest path between the node and reference nodes, that is, proportional to the number of hops or the sum of measured ranges along the shortest path [59]. Note that the shortest path algorithm is already executed in a distributed manner across the network. When each node has multiple range estimates to known positions, its coordinates are calculated locally via multilateration [77].

Successive refinement: These algorithms try to find the optimum of a global cost function (e.g., LS, WLS, or ML). Each node estimates its location and then transmits that assertion to its neighbors [70]. Neighbors must then recalculate their location and transmit again, until convergence. A device starting without any coordinates can begin with its own local coordinate system and later merge it with neighboring coordinate systems [7]. Typically, better statistical performance is achieved by successive refinement compared to network multilateration, but convergence issues must be addressed.

Bayesian networks provide another distributed successive refinement method to estimate the probability density of sensor network parameters. These methods are particularly promising for position localization. Here each node stores a conditional density on its own coordinates based on its measurements and the conditional density of its neighbors. These algorithms are important given the lack of infrastructure that provides beacons or landmarks as references. A summary of several techniques, some of which have been described in this section, can be found in Basagni et al. [3].

Coming up next: Mobility in wireless networks.

Printed with permission from Academic Press, a division of Elsevier. Copyright 2009. "Position Location Techniques and Applications" by David Munoz, Frantz Bouchereau Lara, Cesar Vargas & Rogerio Enriquez-Caldera. For more information about this title and other similar books, please visit www.elsevierdirect.com.

For more articles like this and others related to designing for the embedded Internet, visit Embedded Internet Designline and/or subscribe to the biweekly Embedded Internet newsletter (free registration).

REFERENCES
[1] J. Albowicz, A. Chen, L. Zhang, Recursive position estimation in sensor networks, Proceedings of the IEEE International Conference on Network Protocols, November (2001) 35–41.

[3] S. Basagni,M. Conti,S. Giordano,I. Stojmenovic (Eds.), MobileAd-Hoc Networking, IEEE Press,Wiley-Interscience, 2004.

[7] S. Capkun,M. Hamdi, J.P. Hubaux,GPS-free positioning in mobile ad hoc networks, Proceedings of the 34th IEEE Hawaii International Conference on System Sciences (HICSS-34), January (2001) 9008.

[9] H. Celebi, H. Arslan, Utilization of location information in cognitive wireless networks, IEEEWireless Communications, 14 (4) (2007) 6–13.

[10] S. Chakrabarti, A. Mishra, QoS issues in ad hoc wireless networks, IEEE Communications Magazine, 39 (2) (2001) 142–148.

[12] I. Chlamtac, M. Conti, J.J.N. Liu, Mobile ad hoc networking: imperatives and challenges, Ad Hoc Networks Journal, 1 (1) (2003) 13–64.

[19] L. Doherty, K.S.J. Pister, L.E. Ghaoui,Convex position estimation in wireless sensor networks, Proceedings of the IEEE INFOCOM 3 (2001) 1655–1663.

[22] M. Frodigh, P. Johansson, P. Larsson, Wireless ad hoc networking—the art of networking without a network, Ericsson Review, 4 December (2000) 248–263. Available at www.ericsson.com/about/publications/review/2000_04/files/2000046.pdf.

[28] E.G. Goodaire,M.M. Parmenter, Discrete Mathematics with GraphTheory,Prentice Hall, 1998.

[30] P. Gupta, P.R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, 6 (2) (2000) 388–404.

[36] K. It ˆ o,H.P. McKean, Jr.,Diffusion Processes and their Sample Paths,Springer-Verlag, 1974.

[38] S. Karlin, H.M. Taylor, A First Course In Stochastic Processes, 2nd edition, Academic Press, 1975.

[39] S. Karlin, H.M. Taylor, A Second Course In Stochastic Processes, Academic Press, 1981.

[40] F.P. Kelly, Reversibility and Stochastic Networks, JohnWiley & Sons, 1987.

[41] T.J. Kwon, M. Gerla, Clustering with power control, Proceedings of the IEEE Military Communications Conference, 2 (1999) 1424–1428.

[43] A.B. Lawson, D.G.T. Denison, Spatial Cluster Modelling, Chapman & Hall/CRC, 2002.

[47] A.B. McDonald,T.F. Znati,A mobility-based framework for adaptive clustering in wireless ad hoc networks, IEEE Journal on Selected Areas in Communications, 17 (8) (1999) 1466–1487.

[49] R. Meester,R. Roy, Continuum Percolation, Cambridge University Press, 1996.

[54] J. Moller, R.P.Waagepetersen, Statistical Inference and Simulation for Spatial Point Processes,Chapman & Hall/CRC, 2004.

[55] R.L. Moses, D. Krishnamurthy, R. Patterson,An auto-calibration method for unattended ground sensors, Proceedings IEEE ICASSP, 3,May (2002) 2941–2944.

[59] D. Niculescu, B. Nath, Ad hoc positioning system (APS),IEEE GlobalTelecommunications Conference, 5 (2001) 2926–2931.

[60] D. Niculescu, B. Nath, Ad hoc positioning system (APS) using AOA, Proceedings IEEE INFOCOM,3 (2003) 1734–1743.

[62] N. Patwari, R.J. O‘Dea,Y.Wang, Relative location in wireless networks,Proceedings IEEE VTC01, 2 (2001) 1149–1153.

[63] N. Patwari, J.N.Ash,S. Kyperountas, A.O. Hero III,R.L. Moses,N.S. Correal,Locating the nodes, IEEE Signal Processing Magazine, 22 (4) (2005) 54–69.

[69] C. Savarese, J.M. Rabaey, J. Beutel,Locationing in distributed ad-hoc wireless sensor networks, Proceedings IEEE ICASSP,May (2001) 2037–2040.

[70] A. Savvides, H. Park, M.B. Srivastava, The bits and flops of the N-hop multilateration primitive for node localization problems, Proceedings of the International Workshop on Sensor Networks and Applications, September (2002) 112–121.

[71] A. Savvides,W.L. Garber, R.L. Moses, M.B. Srivastava, An analysis of error inducing parameters in multihop sensor node localization, IEEE Transactions on Mobile Computing, 4 (6) (2005) 567–577.

[74] G. Sun, J. Chen,W. Guo, K.J.R. Liu, Signal processing techniques in network-aided positioning, IEEE Signal Processing Magazine, July (2005) 12–23.

[76] J.B. Tenenbaum, V. de Silva, J.C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science, 290 (2000) 2319–2323.

[77] D.J. Torrieri, Statistical theory of passive location systems, IEEE Transactions on Aerospace and Electronic Systems, 20 (2) (1984) 183–198.

[84] M.Z. Antonio,A theoretical framework for the evaluation of connectivity, robustness and reachability in wireless ad hoc networks, M.Sc. Thesis, ITESM-Monterrey, 2005.