INVITED PAPER Cooperative Localization in Wireless Networks In harsh environments where geographic positioning fails, communication between wireless nodes can be used to improve the accuracy of location information. By Henk Wymeersch, Member IEEE, Jaime Lien, Member IEEE, and Moe Z. Win, Fellow IEEE ABSTRACT | Location-aware technologies will revolutionize many aspects of commercial, public service, and military sectors, and are expected to spawn numerous unforeseen applications. A new era of highly accurate ubiquitous locationawareness is on the horizon, enabled by a paradigm of cooperation between nodes. In this paper, we give an overview of cooperative localization approaches and apply them to ultrawide bandwidth (UWB) wireless networks. UWB transmission technology is particularly attractive for short- to mediumrange localization, especially in GPS-denied environments: wide transmission bandwidths enable robust communication in dense multipath scenarios, and the ability to resolve subnanosecond delays results in centimeter-level distance resolution. We will describe several cooperative localization algorithms and quantify their performance, based on realistic UWB ranging models developed through an extensive measurement campaign using FCC-compliant UWB radios. We will also present a powerful localization algorithm by mapping a graphical model for statistical inference onto the network topology, which results in a net-factor graph, and by developing a suitable net-message passing schedule. The resulting algorithm (SPAWN) is fully distributed, can cope with a wide variety of scenarios, and requires little communication overhead to achieve accurate and robust localization. Manuscript received November 3, 2006; revised February 1, 2008. Current version published March 18, 2009. This work was supported in part by the Belgian American Educational Foundation, the JPL Strategic University Research Partnerships, and the National Science Foundation under Grants ECCS-0636519 and ANI-0335256. H. Wymeersch and M. Z. Win are with the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139 USA (e-mail: hwymeers@mit.edu; moewin@mit.edu). J. Lien was with the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139 USA. She is now with the Jet Propulsion Laboratory, Pasadena, CA 91109 USA (e-mail: Jaime.Lien@jpl.nasa.gov). Digital Object Identifier: 10.1109/JPROC.2008.2008853 KEYWORDS | Cooperative processing; factor graphs; localization; sum-product algorithm; ultrawide bandwidth transmission I. INTRODUCTION Location awareness is rapidly becoming an essential feature of many commercial, public service, and military wireless networks [1], [2]. Information collected or communicated by a wireless node is often meaningful only in conjunction with knowledge of the node’s location. For example, sensor networks used for detecting spatial variations in environmental conditions, such as temperature or pollution, require knowledge of each sensor’s location [3]–[5]. Location information also facilitates a node’s interactions with its surroundings and neighbors, enabling pervasive computing and social networking applications [6]. Location-aware technologies can enable or benefit a vast array of additional applications, including intruder detection [7], blue force tracking [8], finding friends or landmarks [9], healthcare monitoring [10], asset tracking [11], and emergency 911 services [12], [13]. Network nodes must have the capability to self-localize in scenarios where nodes cannot be manually positioned or located by a central system administrator [14], [15]. The goal of self-localization is for every node to know its own state. A state usually includes the two- or three-dimensional position, and possibly other properties such as the velocity and the orientation of the node [16]–[18]. The concept of state depends on the application and may also vary from node to node. In our exposition, we will use the terms state, position, and location interchangeably, while in our examples we will narrow the scope of state to two-dimensional geographical coordinates. We will distinguish between two types of nodes: agents, which have a priori unknown states, and anchors, which have known states at all times. Both agents and anchors may be mobile. The localization process typically consists of two phases [1]. The first phase is the measurement phase, during which 0018-9219/$25.00 Ó2009 IEEE Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 427 Wymeersch et al.: Cooperative Localization in Wireless Networks agents measure internal state information (e.g., using an inertial measurement unit (IMU)) and estimate signal metrics1 based on direct communication with neighboring agents and/or anchors. The second phase is the locationupdate phase, during which agents infer their own state based on the internal state measurements, estimated signal metrics, and state information of neighboring nodes. For instance, when an agent obtains distance estimates with respect to three anchors, the agent can infer its own position through trilateration, provided the agent knows the positions of the anchors. The measurement phase is affected by uncertainty due to sources such as noise, multipath, blockages, interference, clock drifts, and environmental effects [1], [19]–[24]. The underlying transmission technology is a critical factor in how these sources affect the measurements [2]. For instance, the poor signal penetration capabilities of the widely used Global Positioning System (GPS) prevent consumer-grade GPS receivers from making reliable measurements indoors, under forest canopies, and in certain urban settings, leading to inadequate positional information [25]. In challenging environments such as these, ultrawide bandwidth (UWB) transmission technology [26]–[28] is a promising alternative for localization [29]–[31]. UWB systems are inherently well suited for localization since the use of extremely large transmission bandwidths results in desirable capabilities such as 1) accurate ranging due to fine delay resolution; 2) simple implementation for multiple-access communications; and 3) obstacle penetration capabilities [32]–[38]. For more information on the fundamentals of UWB, we refer the reader to [26]–[28], and [39]–[45] and references therein. Given an underlying transmission technology, localization performance is also dependent on the specific algorithm used in the location-update phase. An emerging paradigm is cooperative localization, in which nodes help each other to determine their locations [46]. Cooperative localization has received extensive interest from the robotics, optimization, and wireless communications communities (see [14], [21], [30], [31], and [47]–[61] and references therein). A simple comparison of conventional and cooperative localization is depicted in Fig. 1: while each agent (mobile unit) cannot independently determine its own position based on distance estimates with respect to the anchors (base stations), they can cooperatively find their positions. In general, cooperative localization can dramatically increase localization performance in terms of both accuracy and coverage.2 1Signal metrics include any property of the received signal that depends on the relative positions of the transmitter and the receiver. Examples include the time of flight, the angle of arrival, and the received signal strength. 2Coverage is the fraction of nodes that have an accurate location estimate. Fig. 1. The benefit of cooperative localization: using only distance estimates with respect to the anchors (nodes 1, 2, and 5), agent nodes 2 and 4 are unable to determine their respective positions without ambiguity. Observe that node 2 cannot communicate with node 5, and node 4 cannot communicate with node 1. When agent nodes 2 and 4 communicate and range directly (as depicted by the red arrow), they can cooperate to unambiguously determine their positions. In this paper, we provide an overview of cooperative localization algorithms in wireless networks. • We consider large-scale dynamic heterogeneous networks and examine how cooperation can be used to improve localization accuracy and coverage with respect to noncooperative techniques. • We focus on algorithms based on the principles of estimation theory and statistical inference [62], [63] and outline a framework for the systematic design of inference algorithms, using the theory of factor graphs (FGs) [64]–[66]. • We develop a localization algorithm by mapping a FG onto the time-varying network topology and by employing a spatiotemporal message schedule, resulting in a network FG (Net-FG) and network message passing (Net-MP). The proposed algorithm, called SPAWN (sum-product algorithm over a wireless network), is fully distributed and cooperative. SPAWN also accounts for different state types among nodes, for node mobility, and for any uncertainties associated with both the measurement and location-update phases. • We show how SPAWN generalizes previously proposed localization algorithms, reverting to Bayesian filtering in the case of a single agent [18] and to nonparametric belief propagation localization [14] in the case of a homogeneous network with static nodes. This paper is organized as follows. In Section II, we provide an overview of methods used for the two phases of localization. We describe and compare various signal metrics and localization approaches, emphasizing the advantages of UWB as an underlying transmission technology. In Section III, we provide a concise overview of general purpose estimation techniques and factor graphs. Section IV deals with non-Bayesian and Bayesian 428 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks cooperative localization strategies. Section V details the results of an extensive range measurement campaign using FCC-compliant UWB radios. We then present a case study for indoor localization in large UWB networks in Section VI and quantify the performance of different cooperative and noncooperative localization algorithms in terms of accuracy and availability using experimental data. In Section VII, we draw our conclusions and present avenues for further research in this area. Notation: Throughout this paper, we will use the following notation. The state of node i at time t will be denoted by t2 will be xði tÞ. The denoted state sequence of node i from time t1 by xði t1:t2Þ. Random variables will to be capitalized and vectors written in bold unless there is no ambiguity. Distributions such as pXðxÞ will at times be abbreviated by pðxÞ. II. LOCALIZATION APPROACHES FOR WIRELESS NETWORKS In this section, we describe different types of signal metrics and classify different types of localization algorithms. We apply this classification to well-known localization systems, considering both indoor and outdoor scenarios. A. Measurement Phase In the first phase of localization, packets are exchanged between neighboring nodes in the network (say, nodes A and B). From the physical waveforms corresponding to these packets, the receiver (node B) can extract information regarding its location relative to the location of the transmitter (node A) by measuring or estimating one or more signal metrics. The inherent uncertainty in localization arises from these signal metrics, which are subject to various sources of error. Below, we briefly list several common measurements and describe their use in localization and their sources of error. The distance between nodes can be measured through a variety of metrics. Received signal strength (RSS) exploits the relation between power loss and the distance between sender and receiver [67]. The ability of node B to receive packets from node A, known as connectivity, can constrain the distance between node A and node B to the communication range of node A [68], [69]. Distance measurements of finer resolution can be obtained by estimating the propagation time of the wireless signals. This is the basis of time of arrival (TOA), time difference of arrival (TDOA), and round-trip time of arrival (RTOA) [23], [47]. RTOA is the most practical scheme in a decentralized setting, as it does not require a common time reference between nodes [70]. For example, node B sends a packet to node A at time tB;send in its own time reference. Node A receives the packet at time tA according to its own clock and responds with a packet at tA þ Á, where Á is a time interval that is either predetermined or communicated in the response packet. Node B receives the packet from A at time tB;rec and can then determine the distance dAB through the relation ðtB;rec À tB;send À ÁÞ Â v ¼ 2dAB, where v is the signal propagation speed. Relative orientations can be determined through angle of arrival (AOA) estimation when a node is equipped with directional or multiple antennas [47]. For instance, in a linear array with spatial antenna separation , the difference in arrival time between any two successive antenna elements is given by Át ¼ =ðv cos ABÞ, where AB is the angle between the impinging signal and the antenna array [20]. Beyond distance and angle, one can estimate other properties such as the velocity of a node by measuring Doppler shifts [71]. Information about the state of the node can also be measured internally; for example, distances traveled using an odometer or pedometer, acceleration using an accelerometer, and orientation using an IMU. More problem-specific techniques such as visual odometry [72] may also be considered as signal metrics. Measurements are subject to estimation errors. For instance, RSS estimators may exhibit large errors due to shadowing and multipath. The connectivity metric tends to produce coarse location information, especially when the communication range is large or the connectivity of the network is low. Time delay-based signal metrics (such as TOA, TDOA, RTOA, and AOA) are susceptible to errors due to obstructions between the transmitter and the receiver. These obstructions, leading to so-called non-lineof-sight (NLOS) conditions, can cause a positive bias in the distance estimate. Noise, interference, multipath, clock drifts, and other sources may also introduce errors in estimating arrival times. Finally, internal measurement devices such as IMUs and odometers may accumulate errors over time due to inherent properties of the sensors. For additional information regarding sources of error, the reader is referred to [1], [2], [23], [25], [47], [73], and [74]. B. Location-Update Phase In the second phase, measurements are aggregated and used as inputs to a localization algorithm. A possible taxonomy of localization algorithms is the following (see also [47], [54], and [75] and references therein). 1) Centralized Versus Distributed: In centralized localization, the positions of all agents are determined by a central processor. This processor gathers measurements from anchors as well as agents and computes the positions of all the agents. Centralized algorithms are usually not scalable and thus impractical for large networks. In distributed localization, such as GPS, there is no central controller and every agent infers its own position based only on locally collected information. Distributed algorithms are scalable and thus attractive for large networks.3 3Distributed localization is sometimes referred to as self-localization, while centralized localization is sometimes referred to as remote localization. Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 429 Wymeersch et al.: Cooperative Localization in Wireless Networks 2) Absolute Versus Relative: Absolute localization refers to localization in a single predetermined coordinate system [25]. Relative localization refers to localization in the context of one’s neighbors or local environment [54], [76]; hence, the coordinate system can vary from node to node. 3) Noncooperative Versus Cooperative: In a noncooperative approach, there is no communication between agents, only between agents and anchors. Every agent needs to communicate with multiple anchors, requiring either a high density of anchors or long-range anchor transmissions. In cooperative localization, interagent communication removes the need for all agents to be within communication range of multiple anchors; thus high anchor density or long-range anchor transmissions are no longer required. Since agents can obtain information from both anchors and other agents within communication range, cooperative localization can offer increased accuracy and coverage. We will quantify these performance improvements in Section VI. C. Outdoor and Indoor Localization 1) Outdoor Localization: Examples of outdoor systems include GPS, LORAN-C, and radio-location in cellular networks. GPS is a distributed, absolute, and noncooperative localization approach [25], relying on TOA estimates from at least four anchors (GPS satellites) to solve a fourdimensional nonlinear problem (three spatial dimensions and one time dimension, since the agent is not synchronized to the anchors). Assisted GPS is a centralized version of GPS, reducing the computational burden on the agents [25]. LORAN-C is a terrestrial predecessor of GPS [77], which offers centralized, absolute, and noncooperative localization services based on TDOA. Cell phone radio-location services such as E911 commonly employ TDOA and are centralized, absolute, and noncooperative [78], [79]. delay estimation algorithms improves with increasing transmission bandwidth [23]. Moreover, the wide bandwidth allows multipath components to be resolved and enables superior signal penetration through obstacles [27], [32]–[38]. Hence, robust communications in dense multipath environments and ranging in NLOS conditions can be achieved [32]–[36]. The penetration capabilities of UWB signals also make them useful for detecting and potentially compensating for the effects of obstacles and NLOS conditions [88], [89]. In addition, UWB transmitters are low complexity, low cost devices, practical for dense and rapid deployment [90]. Since the power is spread over a large bandwidth, UWB communication systems are covert and power-efficient, and cause minimal interference to other systems [26]–[28], [34]. UWB signals have the unique advantage of simultaneously accomplishing robust communication and precision ranging. Nodes can therefore extract information about their relative positions from signals already used for communication without any additional overhead. The recently completed IEEE 802.15.4a standard [91] will likely spawn numerous practical systems and applications in this sphere. III. BACKGROUND ON INFERENCE Before presenting cooperative localization algorithms, we first give a brief overview of important techniques from estimation theory and statistical inference, which can be applied to the localization problem. There are a number of approaches for estimating a parameter x from an observation z. Apart from ad hoc techniques, we generally categorize these as Bayesian or non-Bayesian, depending on whether or not we consider x as a realization of a random variable [62]. In this section, we describe both approaches. Within the context of Bayesian techniques, we then consider approximate inference, factor graphs, and sequential estimation. 2) Indoor Localization: Existing and emerging indoor localization methods include WiFi, radio-frequency identification (RFID), and UWB localization [80], [81]. RADAR, based on WiFi fingerprinting at multiple anchors [82]; PlaceLab, using connectivity from 802.11 access points; and GSM base stations [83] employ centralized, absolute, and noncooperative approaches. Passive RFID tags can be used in conjunction with RFID readers to provide connectivity-based localization [84] that is centralized, relative, and noncooperative. Both WiFi and RFID systems suffer from poor accuracy due to coarse measurements. On the other hand, UWB signals have a number of characteristics that make them more attractive for indoor localization, as well as for indoor communication in general [85]–[87]. The fine delay resolution of UWB signals is well suited for estimating propagation times (e.g., for RTOA or AOA), since the performance of A. Non-Bayesian Estimation Two common non-Bayesian estimators, which treat x as an unknown deterministic parameter, are the least squares (LS) estimator and the maximum likelihood (ML) estimator. • The LS estimator assumes that z 2 IRN and z ¼ f ðxÞ þ n, where f ðÁÞ is a known function and n is a measurement error. The LS estimate of x is obtained by solving the following optimization problem: x^LS ¼ arg minkz À f ðxÞk2: (1) x The LS estimator does not exploit any knowledge regarding the statistics of n. 430 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks • The ML estimator accounts for the statistics of noise sources and maximizes the likelihood function x^ML ¼ arg max x pZjXðzjxÞ: (2) B. Bayesian Estimation Two common Bayesian estimators, which treat x as a realization of a random variable X with an a priori distribution pXðxÞ, are the minimum mean squared error (MMSE) estimator and the maximum a posteriori (MAP) estimator. • The MMSE estimator finds the mean of the a posteriori distribution Z x^MMSE ¼ xpXjZðxjzÞdx: (3) Fig. 2. Minimizing the KLD can lead to different Bayesian inference algorithms, including sum-product algorithm (SPA), MMSE, mean-field (MF), expectation-propagation (EP), expectation-maximization (EM), variational EM (VEM), and MAP. class C, we try to find the distribution bX that minimizes the KLD bÃX ¼ arg min DðbXkpXjZÞ: bX 2C (6) • The MAP estimator finds the mode of the a posteriori distribution x^MAP ¼ arg max x pXjZðxjzÞ: (4) If pXjZðÁjzÞ is difficult to determine, or if the dimensionality of X is high so that the integration in (3) or the maximization in (4) become intractable, we can resort to MMSE or MAP estimates of the components of X rather than the entire vector. For example, when X ¼ ½X1; . . . ; XN, then the MMSE (respectively, MAP) estimate of Xk is given by the mean (respectively, mode) of the marginal a posteriori distribution pXkjZðÁjzÞ of the variable Xk. C. Approximate Inference In many inference problems, the a posteriori distribu- tion pXjZðÁjzÞ is difficult to describe, and obtaining its mean, mode, or marginals is a very hard problem. In such situations, one can turn to an alternative distribution, say, bXðÁÞ, belonging to a certain class C. Inferences can then be drawn based on a particular bXðÁÞ that is close to pXjZðÁjzÞ. A common measure of closeness between distributions is the Kullback–Leibler divergence (KLD) [92], defined as Z DðbXkpXjZÞ ¼ bX ðxÞ ln bXðxÞ pXjZðxjzÞ dx: (5) It is easy to verify that DðbXkpXjZÞ ! 0 and that DðbXkpXjZÞ ¼ 0 if and only if bX ¼ pXjZ. For a given Often bÃX cannot be found in closed form; we can only determine a description (e.g., a list of necessary conditions imposed on bX) of the stationary points4 of DðbXkpXjZÞ. Using this description, one can then develop iterative algorithms to find those stationary points. Different classes C lead to different solutions, including mean-field, expectation-propagation, expectation-maximization, and the sum-product algorithm (see Fig. 2). For a detailed exposition, see [93] and [94]. These solutions can be found through message passing on an FG, as detailed in the next section. D. Factor Graphs and the Sum-Product Algorithm We cover some basic concepts of FGs and the SPA; for a detailed treatment, the reader is referred to [64]–[66], and [94]. In many inference problems, the a posteriori distribution can be factorized, with every factor kðÁÞ depending only on a small subset of variables xk & x: pXjZðxjzÞ ¼ 1 Q YM k¼1 kðxkÞ (7) where M is the number of factors and Q is a (possibly unknown) normalization constant. 1) Factor Graphs: A factor graph5 is a way to graphically represent a factorization such as (7). • For every factor, say, ðÁÞ, we create a vertex (drawn as a circle or square) and label it B.[ 4A stationary point can be a minimum, a maximum, or a saddle-point. 5We focus on Forney-style FGs, also known as normal graphs [95]. Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 431 Wymeersch et al.: Cooperative Localization in Wireless Networks important distinction. Only when the FG does not have cycles, i.e., it is a tree, it can be shown that the a posteriori distribution can be expressed as [94] pXjZðxjzÞ ¼ QQNl¼Mk1¼Âp1 XplXjZkðjZxlðjxzÞkjÃzdlÞÀ1 (10) Fig. 3. FG of Aðx1ÞBðx1; x2ÞCðx1; x2ÞDðx2; x3Þ, on the left. Grouping BðÁÞ and CðÁÞ into ðÁÞ yields the FG on the right. • For every variable X, we create an edge (drawn as a line) and label it BX.[ When a variable X appears in a factor ðÁÞ, we connect the edge X to the vertex . Since edges can be connected to at most two vertices, we must treat variables that appear in more than two factors as a special case. • For a variable X that appears in D > 2 factors, we create a so-called equality vertex and label it B¼.[ We also create D edges and connect every edge to the equality vertex and one of the D factors. The edges are labeled with a dummy name of the variable (e.g., X0 and X00 for X). The equality vertex represents a Dirac delta function. For instance, an equality vertex with edges X, X0, and X00 corresponds to a function ðx À x0Þðx À x00Þ. For nota- tional convenience, we often label all the edges connected to an equality vertex with the same label (X, in this case). Let us examine a simple example, where X ¼ ½X1; X2; X3 has an a posteriori distribution that can be factorized as pðx1; x2; x3jzÞ ¼ 1 Q Aðx1ÞBðx1; x2ÞCðx1; x2ÞDðx2; x3Þ (8) where M is the total number of factors, N is the total number of variables, and dl is the number of factors in (7) where the variable xl appears.7 For instance, when using the factorization (9), we can express pðx1; x2; x3jzÞ as (with d1 ¼ d3 ¼ 1, d2 ¼ 2)8 pðx1; x2; x3jzÞ ¼ pðx1; x2jzÞpðx2; x3jzÞ pðx1jzÞ0pðx2jzÞ1pðx3jzÞ0 : (11) Given a factorization of the form (7), we can introduce a class CSPA of functions bXðÁÞ of the following form: bXðxÞ ¼ QQNl¼Mk1¼½b1 XblXðxklðÞxdkl Þ À1 (12) P P s u b j e c t t o P bXk ðxkÞ ! 0, bXl ðxlÞ ! 0, xk bXk ðxkÞ ¼ xl bXl ðxlÞ ¼ 1, xknl bXk ðxkÞ ¼ bXl ðxlÞ, 8k; l : xl 2 xk. The description of the stationary points of DðbXkpXjZÞ is expressed in terms of the functions bXk ðÁÞ and bXl ðÁÞ. Comparing (10) and (12), we see that when the FG of the factorization of pXjZðÁjzÞ has no cycles, the optimization problem (6) with C ¼ CSPA has a unique global minimizer bÃX, with corresponding KLD equal to zero. Furthermore, the a posteriori distribution pXjZðÁjzÞ can be recovered based solely on bÃXk ðÁÞ and bÃXl ðÁÞ, 8k; l, since the uniqueness of the solution implies that where Q is an unknown constant. Factorizations are by no means unique: by grouping BðÁÞ and CðÁÞ into a new factor, say, ðÁÞ, a different factorization is obtained: bÃXk ðxkÞ ¼ pXkjZðxkjzÞ; 8k; xk (13) bÃXl ðxlÞ ¼ pXljZðxljzÞ; 8l; xl: (14) pðx1; x2; x3jzÞ ¼ 1 Q Aðx1Þ ðx1; x2ÞDðx2; x3Þ: (9) FGs corresponding to (8) and (9) are depicted in Fig. 3. 2) Trees and Cyclic GraphsVPart 1: The factorization (8) results in a cyclic FG,6 while (9) does not. This is an 6The FG of (8) has a cycle given by edges X10 ; X100; X2; X200. 3) The Sum-Product Algorithm: The SPA is a message passing algorithm on a cycle-free FG that efficiently computes bÃXk ðÁÞ and bÃXl ðÁÞ, 8k; l, when C ¼ CSPA. The SPA operates by computing messages inside the vertices and sending those messages over the edges. 7For mathematical convenience, we need to assume that xk contains at least two variables. We group variables together where necessary. See also [94]. 8Since A has only one variable, we have grouped A and . 432 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks A message over an edge X is a function of the corresponding variable and is denoted X!ðÁÞ or !XðÁÞ, where is a vertex adjacent to edge X. Given a factor ðx1; . . . ; xDÞ and incoming messages Xk!ðÁÞ8k, the outgoing message over edge Xi is given by Z Y !Xi ðxiÞ / ðx1; . . . ; xDÞ Xk!ðxkÞdx1 . . . k6¼i dxiÀ1dxiþ1 . . . dxD (15) where the proportionality symbol indicRates that the message !Xi ðÁÞ is normalized, such that !Xi ðxiÞdxi ¼ 1. For example, in Fig. 3, the message from to X2 is given by schedule), and each schedule may lead to different functions bÃXk ðÁÞ and bÃXl ðÁÞ. The ability to choose schedules will turn out to be important in deriving a cooperative localization algorithm. E. Sequential Estimation In some scenarios, variables may change over time. Sequential or online estimation deals with such scenarios by estimating variables at a certain time, say, variable xðtÞ at time t, taking into account independent observations taken up to and including t, say, zð1:tÞ ¼ ½zð1Þ; . . . ; zðtÞ [17], [97], [98]. We rely on the following Markovian assumptions: pðxðtÞjxð0:tÀ1ÞÞ ¼ pðxðtÞjxðtÀ1ÞÞ and pðzðtÞjxð0:tÞÞ ¼ pðzðtÞjxðtÞÞ. It can then easily be shown that Z !X2 ðx2Þ / ðx1; x2ÞX1! ðx1Þdx1: (16) Z p xðtÞjzð1:tÞ ¼ p xðtÞ; xðtÀ1Þjzð1:tÞ dxðtÀ1Þ / p zðtÞjxðtÞ p xðtÞjzð1:tÀ1Þ (20) (21) Messages start with the half-edges (sending a constant message) and the vertices of degree 1 (sending the corresponding factor). For example, in Fig. 3, X3!D ðx3Þ / 1 and A!X1 ðx1Þ ¼ Aðx1Þ. For equality vertices, it can be shown that an outgoing message is simply the point-wise product of the incoming messages. For example, in Fig. 3, the message from X10 to B is given by X10 !B Àx01Á / A !X1 Àx01 Á C !X100 Àx01 Á : (17) where Z p xðtÞjzð1:tÀ1Þ ¼ p xðtÞjxðtÀ1Þ p xðtÀ1Þjzð1:tÀ1Þ dxðtÀ1Þ: (22) The marginal of a certain variable is obtained by pointwise multiplication of the two messages passed over the corresponding edge. In our example from Fig. 3, bÃX2 ðx2Þ / X2!D ðx2Þ Â D!X2 ðx2Þ: (18) The marginal of a cluster of variables xk is obtained by multiplying the incoming messages with the corresponding factor. For instance, in the example from Fig. 3, bÃX1;X2 ðx1; x2Þ / ðx1; x2ÞX1! ðx1ÞX2! ðx2Þ: (19) 4) Trees and Cyclic GraphsVPart 2: The SPA provides us with exact marginals for FGs without cycles (i.e., trees). For FGs with cycles, we can easily extend the SPA, which becomes iterative. However, the computed functions bÃXk ðÁÞ and bÃXl ðÁÞ are no longer exactly equal to the corresponding marginal a posteriori distributions, and bX is not necessarily a distribution [96]. Furthermore, in an FG with cycles, there are many possible orders in which messages are computed (also known as the message This implies that, given pðxðtÀ1Þjzð1:tÀ1ÞÞ, we can determine pðxðtÞjzð1:tÞÞ as follows: i) a prediction operation, during which we determine the distribution pðxðtÞjzð1:tÀ1ÞÞ, given all observations before time t, according to the integral in (22); and ii) a correction operation, in which we account for the new observation zðtÞ to calculate pðxðtÞjzð1:tÞÞ, according to (21). Hence, at every time t, we have the a posteriori distribution pðxðtÞjzð1:tÞÞ of the variable xðtÞ, given all the observations up to and including time t. We can determine the mean or the mode of this a posteriori distribution, giving us the MMSE estimate or MAP estimate of xðtÞ, respectively. The entire procedure is initialized by pðxðtÞjzð1:tÞÞjt¼0 ¼ pðxð0ÞÞ. Sequential Estimation and FGs: Sequential estimation can be obtained by creating an FG of pðxð0:TÞjzð1:TÞÞ and then applying the SPA. Using the Markovian assumptions and the fact that the measurements are independent, we easily find that YT p xð0:TÞjzð1:TÞ / p xð0Þ p xðtÞjxðtÀ1Þ p zðtÞjxðtÞ t¼1 (23) Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 433 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 4. Sequential estimation: an FG of pðxð0:2Þjzð1:2ÞÞ, where ðtÞðxðtÞ; xðtÀ1ÞÞ is a shorthand for pðxðtÞjxðtÀ1ÞÞ and ðtÞðxðtÞÞ is a shorthand for pðzðtÞjxðtÞÞ. with a corresponding FG depicted in Fig. 4 for T ¼ 2. The message schedule is shown with arrows, starting with the black messages from the leaves of the tree. At time t ¼ 1, the red message ð1Þ!Xð1Þ ðÁÞ is given by Z xð1Þ ð1Þ !X ð1Þ / xð0Þ X ð0Þ !ð1Þ Â ð1Þ xð1Þ; xð0Þ dxð0Þ Z ¼ p xð0Þ p xð1Þjxð0Þ dxð0Þ ¼ p xð1Þ (24) which corresponds to the prediction operation. Using (17), the blue message Xð1Þ!ð2Þ ðÁÞ is given by x / x x ð1Þ X ð1Þ !ð2Þ ð1Þ ð1Þ ð1Þ !X ð1Þ ð1Þ !X ð1Þ ¼ p zð1Þjxð1Þ p xð1Þ (25) which is exactly the correction operationR. At time slot t ¼ 2, we easily find that ð2Þ!Xð2Þ ðxð2ÞÞ / Xð1Þ!ð2Þ ðxð1ÞÞ pðxð2Þjxð1ÞÞdxð1Þ a n d t h a t Xð2Þ!ð3Þ ðxð2ÞÞ / pðzð2Þjxð2ÞÞ ð2Þ!Xð2Þ ðxð2ÞÞ. The sequence of prediction operation (red arrows) followed by correction operation (blue arrows) continues with messages flowing from past to present to future. In principle, messages can also be computed from future to present to past, a process known as smoothing. In this section, we apply the cooperative paradigm to a completely different problem: localization. We present several fundamental cooperative localization algorithms based on the methodologies from Section III. Both nonBayesian and Bayesian approaches will be considered. For the sake of the exposition, we focus on small-scale examples. In Section VI, we will present a case study for a large network with more than 100 nodes. A. Problem Formulation We consider a wireless network with N nodes in an environment E. Time is slotted, and nodes can move independently from positions at time slot t À 1 to new positions at time slot t. The state of node i at time t is written as xði tÞ. We denote by S ðtÞ !i the set of nodes from which node i may receive signals during time slot t. Similarly, we denote by Sði!tÞ the set of nodes that may receive a signal from node i during time slot t. At time slot t, node i may estimate local metrics zði;tsÞelf based on internal measurements (e.g., using an IMU or an odometer). Based on the signal received from node j 2 Sð!tÞi, node i can estimate signal metrics zðj!tÞ i. We denote the collection of all signal metrics and all internal measurements collected by all nodes at time t as zðtÞ. Note that we can break up zðtÞ into zðsteÞlf and zðrteÞl, where zðsteÞlf contains all the internal measurements of all the nodes, while zðrteÞl contains all the relative signal metrics from all the nodes with respect to their neighbors. The goal of node i is to estimate its own state xði tÞ at time t, given only information up to time t. Ideally, the localization process should require low complexity and communication overhead per node and incur a low latency. B. Assumptions We make the following assumptions, which are reasonable in many practical scenarios. a) The states pðxð0ÞÞ ¼ QofNi¼th1 epðnxoði 0dÞeÞ.s are a priori independent: b) Nodes move according to a memoryless walk: YT p xð0:TÞ ¼ p xð0Þ p xðtÞjxðtÀ1Þ : t¼1 (26) IV. COOPERATIVE LOCALIZATION The concept of cooperation in networks is fairly new: it relies on direct communication between agents rather than through a fixed infrastructure [99]–[101]. Cooperation has been successfully applied to wireless peer-to-peer communication, leading to standards such as Bluetooth [102] and Zigbee [103], and is expected to be applied to cellular systems over the next few years [104]. c) Nodes move independently: p xðtÞjxðtÀ1Þ ¼ YN p xði tÞjxði tÀ1Þ : i¼1 (27) d) Relative measurements are independent of the internal measurements, conditioned on the states 434 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks of the nodes: C. Non-Bayesian Cooperative Localization In non-Bayesian cooperative localization, we treat the state of node i at time t as a nonrandom but unknown p zðr1e:lTÞjxð0:TÞ; zðs1e:lTf Þ ¼ p zðr1e:lTÞjxð0:TÞ : (28) parameter. For an overview of non-Bayesian localization techniques, the reader is referred to [75]. We focus on cooperative ML and LS localization. The cooperative LS e) Internal measurements are mutually independent algorithm forms the basis of [30], [47], [48], [50], [53], and depend only on the current and previous state: [54], [56]–[58], and [61], as well as variations such as weighted LS, where signal metrics have an associated weight reflecting the quality of the estimate [105], and p zðse1:lTf Þjxð0:TÞ ¼ YT p zðsteÞlf jxðtÀ1Þ; xðtÞ : (29) regularized LS, where certain locations are penalized [106]. Based on cooperative LS, a cooperative ML algorithm was t¼1 adopted in [51]. The ML and LS estimators minimize a cost function CðtÞðxÞ with respect to x ¼ ½x1; . . . ; xN at a particular time f) Internal measurements at node i depend only on slot t. For the LS estimator, this cost function is given by the state of node i: p zðsteÞlf jxðtÞ; xðtÀ1Þ ¼ YN p zði;tsÞelf jxði tÀ1Þ; xði tÞ : i¼1 (30) CðLtSÞ ðxÞ ¼ XN X zðj!tÞ i À f ðxi; xjÞ2 i¼1 j2Sð!tÞi (33) g) Relative measurements are independent from time slot to time slot, conditioned on the states of the nodes. Moreover, they depend only on the current states: p zðr1e:lTÞjxð0:TÞ ¼ YT p zðrteÞljxðtÞ : (31) t¼1 h) Relative measurements at any time slot t are conditionally independent and depend only on the two nodes involved: p zðrteÞljxðtÞ ¼ YN Y p zðj!tÞ ijxði tÞ; xðj tÞ : i¼1 j2Sð!tÞi (32) We further assume that node i knows the following: i) the state distribution pðxði 0ÞÞ at time t ¼ 0; ii) its own mobility model pðxði tÞjxðitÀ1ÞÞ at any time t; iii) the internal measurements zði;tsÞelf and the corre- sponding likelihood function pðzði;tsÞelf jxði tÀ1Þ; xði tÞÞ at any time t; iv) the signal metrics zðj!tÞ i and the likelihood function pðzðj!tÞ ijxði tÞ; xðj tÞÞ at any time t. Since this information is available to node i at time t, we call such information local. For other information to be obtained by node i, packets must be sent over the network. where f ðxi; xjÞ is a suitable function based on the signal metrics. For instance, when xi and xj are the position coordinates of nodes i and j, and when zðj!tÞ i is an estimate of the distance between node i and node j, as estimated by node i, then f ðxi; xjÞ ¼ kxi À xjk. For the ML estimator, the cost function becomes (see (32)) CðMtÞLðxÞ ¼ Àlog p zðrteÞljx (34) ¼ XN À X log p zðj!tÞ ijxi; xj : i¼1 j2Sð!tÞi (35) In general, for both the function is of the form MCðtLÞðxanÞd¼LPS Nie¼s1tPimja2tSoð!rtÞis,cjt!hieðzcðj!otÞsit; xi; xjÞ. To minimize this cost function, we set the derivative with respect to xi equal to zero, where @CðtÞðxÞ X @cj!i zðj!tÞ i; xi; xj ¼ @xi j2S ðtÞ !i @xi X @ci!k zði!tÞ k; xk; xi þ : k2Sði!tÞ @xi (36) We can now apply gradient descent to iteratively minimize CðtÞðxÞ, starting from an initial estimate at time slot t, x^ðt;0Þ. A distributed, cooperative gradient descent algorithm is shown in Algorithm 1, where iðt;lÞ represents a step size that controls the convergence speed. Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 435 Wymeersch et al.: Cooperative Localization in Wireless Networks Algorithm 1 Cooperative LS and ML Localization 1: given x^ði0Þ, 8i 2: for t ¼ 1 to T do {time slot index} 3: set x^ði t;0Þ ¼ x^ði tÀ1Þ 4: for l ¼ 1 to Niter do {iteration index} 5: nodes i ¼ 1 to N in parallel 6: broadcast current location estimate x^ði t;lÀ1Þ 7: receive estimate from neighbors x^ðj t;lÀ1Þ, j 2 Sð!tÞi 8: 9: update location x^ði t;lÞ ¼ x^ði t;lÀ1Þ þ end parallel esiðtt;ilÞmPatje2S{ð!otÞinlyðj!t;flÀio1rÞ agents} 10: end for 11: set x^ði tÞ ¼ x^iðt;NiterÞ 12: end for For notational convenience we have introduced Equation (38) can be interpreted as follows: every term in the summation is zero when the distance estimate d^ðj!tÞ i matches the distance between the estimates x^ði t;lÀ1Þ and ^xðj t;lÀ1Þ. When d^ðj!tÞ i is smaller than the distance kx^ði t;lÀ1Þ À x^ðj t;lÀ1Þk between the two estimates, the LS algorithm corrects this by moving the estimated position x^ðit;lÞ of node i towards x^ðj t;lÀ1Þ. Conversely, when d^ðj!tÞ i is larger than kx^ði t;lÀ1Þ À x^ðj t;lÀ1Þk, the LS algorithm corrects this by moving x^ðit;lÞ can be tuned by the positive aswcaalyarfrsotmepx^sðj it;zlÀe 1Þ .iðtT;lÞh. e movement Algorithm 2 SPAWN 1: given pðxði0ÞÞ, 8i 2: for t ¼ 1 to T do {time index} 3: nodes i ¼ 1 to N in parallel 4: prediction operation, according to (15) ðt;lÀ1Þ j!i ¼Á @ cj!i zðj!tÞ i; xi @xi ; x^ðj t;lÀ1Þ : xi ¼x^iðt;lÀ1Þ (37) Here, l is the iteration index and P xði tÞ a t k2S ðtÞ i! t ð@ he ci!k lt h ðzði!tÞ k iteratio ; xk; xiÞ=@ n xi . Þ Algorithm 1, line 8, since the x^ði t;lÞ is the estimate of Note that the te in (36) is omitted measurement zði!tÞ k is the rm in not available at node i. Observe also that Algorithm 1 operates in two time scales: in the shorter time scale, indexed by l in line 4, nodes iteratively update their state estimate for fixed t. The movement of the nodes occurs in the longer time scale, set by the time slots and indexed by t in line 2. The global minimum may not be reached through iterative descent, since the cost function CðtÞðxÞ is usually not convex. Example: We will now illustrate the behavior of cooperative LS localization in a plane using the example in Fig. 1, where zðj!tÞ i ¼ d^ðj!tÞ i is an estimate made by node i regarding its distance to node j and f ðxi; xjÞ ¼ kxi À xjk. After some straightforward manipulations, line 8 in Algorithm 1 becomes x^ði t;lÞ ¼ x^ði t;lÀ1Þ þ iðt;lÞ X d^ðj!tÞ i À d~ðj!t;lÀi 1Þ eðijt;lÀ1Þ j2Sð!tÞi (38) where d~ðj!t;lÀi 1Þ ¼ kx^ði t;lÀ1Þ À x^ðj t;lÀ1Þk and eðijt;lÀ1Þ is a unitvector oriented along the line connecting x^ði t;lÀ1Þ and ^xðj t;lÀ1Þ: ðtÞ Z x hði tÀ1Þ!XiðtÞ i / |pﬄﬄﬄxﬄﬄðiﬄﬄtﬄÞﬄjﬄﬄxﬄﬄðiﬄtﬄÀﬄﬄ1ﬄﬄÞﬄﬄﬄﬄpﬄﬄﬄ{zzðiﬄ;tﬄsÞﬄeﬄlﬄfﬄﬄjﬄxﬄﬄðiﬄtﬄÀﬄﬄﬄ1ﬄÞﬄﬄ;ﬄﬄxﬄﬄðiﬄtﬄÞﬄﬄ} ð Þ ¼hði tÀ1Þ xði tÀ1Þ;xði tÞ Â XiðtÀ1Þ!hði tÀ1Þ xði tÀ1Þ dxði tÀ1Þ 5: end parallel 6: correction operation: see Algorithm 3 7: end for In Fig. 1, anchor nodes 1, 3, and 5 have perfect location information, so that x^ðit;lÞ ¼ xðit;lÞ, 8l; t, i 2 f1; 3; 5g. We also know from Fig. 1 that agent node 4 suffers from a position ambiguity. Specifically, if we place the network topology in a 50 Â 50 m2 map (see Fig. 5), agent node 4 can constrain its or location to x^ð4t;lÞ ¼ ½40; either x^ð4t;lÞ ¼ ½20; 60 (the correct position) 60 (the incorrect position), under noise-free distance estimates. If the correct position estimate is broadcast by agent 4 and received by agent 2 (Fig. 5(a)), the LS cost function for node 2 has a global minimum at its true position. Hence, the LS algorithm will move the estimate of the position of node 2 towards the true position, as the iterations progress. If the information from agent node 4 is incorrect (Fig. 5(b)), the LS cost function has a minimum at a position far away from its true position, and the LS algorithm will move the estimate of the position of node 2 away from the true position. eðijt;lÀ1Þ ¼ xx^^ðiði tt;;llÀÀ11ÞÞ À À x^ðj t;lÀ1Þ x^ðj t;lÀ1Þ : D. Bayesian Cooperative Localization Bayesian approaches to localization have been used in (39) robotics for the noncooperative mobile single-agent case [18] and for the cooperative mobile multiagent case [49], 436 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 5. Contour plots of the LS cost function for agent node 2, for two possible position estimates of agent node 4. The true locations of anchors and agents are depicted by red squares and green circles, respectively. The estimated position of agent 4 is marked as a cross, with x^ð4t;lÞ ¼ ½20; 60 in (a) and x^ð4t;lÞ ¼ ½40; 60 in (b). The minimum of the LS cost function for agent node 2 is far away from the correct location when agent node 4 broadcasts an incorrect location estimate (in (b)). [60], [107]. Bayesian cooperative localization for networks without mobility was investigated in [14], [108], and [109]. In this section, we develop a general Bayesian framework for cooperative localization in heterogeneous, mobile networks. We first create an FG of a factorization of pðxð0:TÞjzð1:TÞÞ and map this FG onto the time-varying network topology, resulting in a network FG (Net-FG). This mapping is one-to-one in the sense that every node in the network is associated with a unique subgraph of the FG. We then introduce a message schedule that accounts for both spatial and temporal constraints of the message flow, resulting in network message passing (Net-MP). In particular, we can execute a sum-product algorithm on the Net-FG, giving rise to the SPA over a wireless network (SPAWN). Below, we describe the steps in developing the Net-FG, Net-MP, and, finally, SPAWN. Due to independent movement and independent internal measurements, both pðxðtÞjxðtÀ1ÞÞ and pðzðsteÞlf jxðtÀ1Þ; xðtÞÞ can be further factorized according to (27) and (30). The FG of pðxð0:2Þjzð1:2ÞÞ corresponding to the example network in Fig. 1 has a structure as shown in Fig. 6. The vertices in blue correspond to the factors pðzðrteÞljxðtÞÞ, each Step 1VFactorization of pðxð0:TÞjzð1:TÞÞ: We first create an FG of a factorization of pðxð0:TÞjzð1:TÞÞ. Using our complete statistical description, we factorize pðxð0:TÞjzð1:TÞÞ as (see (28)) p xð0:TÞjzð1:TÞ / p xð0:TÞ; zðs1e:lTf Þ p zðr1e:lTÞjxð0:TÞ : (40) Substituting (26), (29), and (31) into (40) then leads to YT n p xð0:TÞjzð1:TÞ / p xð0Þ p xðtÞjxðtÀ1Þ t¼1 o Â p zðsteÞlf jxðtÀ1Þ; xðtÞ p zðrteÞljxðtÞ : (41) Fig. 6. FG of pðXð0:2Þjzð1:2ÞÞ, corresponding to the example network in Fig. 1. We use the following abbreviations: fiðXið0ÞÞ ¼ pðXið0ÞÞ and hðitÀ1ÞðXiðtÀ1Þ; XiðtÞÞ ¼ pðXiðtÞjXiðtÀ1ÞÞ pðzið;tsÞelfjXiðtÀ1Þ; XiðtÞÞ. The arrows represent the temporal flow of the message (from past to present). Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 437 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. The 7. Correction node j!iðXiðtÞ; operation: FG of pðzðrteÞl XjðtÞÞ ¼ pðzjð!tÞ ijXiðtÞ; XjðtÞÞ. jXðtÞÞ, with incoming messages hðitÀ1Þ!XiðtÞ ðÁÞ and outgoing messages XiðtÞ!hðitÞ The structure of this FG depends on the network topology at time slot t. ðÁÞ. of which can be further factorized9 as in (32) with an FG shown in Fig. 7. Step 2VCreating the Net-FG: The Net-FG involves mapping the FGs from Figs. 6 and 7 onto the network topology according to the information that is local to each node. From Fig. 6, we see that the vertices hði tÀ1ÞðXiðtÀ1Þ; XiðtÞÞ ¼ pðXiðtÞjXiðtÀ1ÞÞ pðzði;tsÞelf jXiðtÀ1Þ; XiðtÞÞ can be mapped to node i, as these vertices contain information local to node i. This is depicted for node i ¼ 2 in Fig. 6 with a red box. The mapping of the FG in Fig. 7 onto the network topology is less obvious. We see from Fig. 7 that for every variable XiðtÞ, there is an equality vertex as well as a number of vertices labeled j!i for j 2 Sð!tÞi. These latter vertices are a function of zðj!tÞ i, local to node i. A natural mapping would thus be to associate the equality vertex and the vertices labeled j!i to node i. This association is shown in Fig. 8. As an example, the box in red shows the vertices associated with node 2. Combining all the vertices mapped to a single node i, we observe that they form a tree subgraph of the overall FG corresponding to pðxð0:TÞjzð1:TÞÞ, and that this tree depends only on locally available measurements zðj!tÞ i for j 2 Sð!tÞi and zði;tsÞelf, t ¼ 1; . . . ; T. Algorithm 3 SPAWNVCorrection Operation 1: nodes i ¼ 1 to N in parallel 2: initialize bð0Þ XiðtÞ ðÁÞ ¼ ðÁÞ hði tÀ1Þ!XiðtÞ 3: end parallel 4: for l ¼ 1 to Niter do {iteration index} 5: nodes i ¼ 1 to N in parallel 6: broadcast bðlÀ1Þ XiðtÞ ðÁÞ 7: receive bðlÀ1Þ XjðtÞ ðÁÞ from neighbors j 2 Sð!tÞi 9In FG parlance, this is known as opening a vertex [66]. 8: convert bðlÀ1Þ XjðtÞ ðÁÞ to a distribution over XiðtÞ using (15) Z x ðlÞ ðtÞ j!i!XiðtÞ i / p zðj!tÞ ijxði tÞ; xðj tÞ bðlÀ1Þ XjðtÞ xðj tÞ dxðj tÞ 9: compute new message using (15) bðlÞ XiðtÞ xði tÞ / xðtÞ hði tÀ1Þ!XiðtÞ i Y j2Sð!tÞi x ðlÞ ðtÞ j!i!XiðtÞ i 10: end parallel 11: end for 12: nodes i ¼ 1 to N in parallel 13: determine outgoing message: XiðtÞ!hði tÞ ðÁÞ ¼ bðNiter XiðtÞ Þ ðÁÞ 14: end parallel Step 3VCreating the Net-MP and SPAWN: We introduce a message schedule that accounts for the time-varying network topology, leading to the Net-MP. Net-MP consists of two types of messages: messages internal to subgraphs (intranode messages, corresponding to messages computed internally by a node in the network) and messages between subgraphs (internode messages, corresponding to messages between nodes in the network). The former type of message involves computation within a node, while the latter is sent as a packet over the wireless link. We introduce a message schedule that takes into account the spatiotemporal constraints of the network: • To account for temporal constraints, messages flow only forward in time. This is shown by the arrows in Fig. 6. Messages from the present to the past are not computed, as the state information would be outdated and network connectivity may have 438 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 8. Correction operation: mapping of subgraphs to nodes and scheduling of messages leads to a Net-MP. changed. This leads to the first part of SPAWN, as described in Algorithm 2. Observe that, similar to Section III-E, there is a prediction operation, accounting for local mobility, and a correction operation, accounting for measurements between nodes. During the prediction operation, node i computes the message hðitÀ1Þ!XiðtÞ ðÁÞ, based on the message ðÁÞ, XiðtÀ1Þ!hðitÀ1Þ on the local mobility model pðxðitÞjxðitÀ1ÞÞ, and on the local likelihood function pðzði;tsÞelf jxði tÀ1Þ; xði tÞÞ. During the correction operation, node i based on all the determines metrics zðrteÞl messages XiðtÞ!hðitÞ measured by all ðÁÞ, the nodes, as well as on all the messages hðktÀ1Þ!XkðtÞ ðÁÞ, 8k. This implies that the correction operation requires exchange of information between nodes. In other words, nodes need to cooperate. • To account for the network topological constraints at a fixed time t, we choose a message flow shown in Fig. 8, with the arrows showing the direction of the messages. The bold red arrows represent internode messages sent as packets over a wireless link. The blue arrows represent intranode messages, com- puted internally within a node. According to this schedule, messages only flow in one direction over every edge. This implies that internode messages do not depend on the recipient node. In other words, these messages can be broadcast. The re- sulting SPAWN for the correction operation is given in Algorithm 3. The internode message broadcast by node i is denoted by bðlÞ XiðtÞ ðÁÞ, where t is the time index and l is the iteration index. The overall SPAWN algorithm thus corresponds to Algorithm 2, with the correction operation computed ac- cording to Algorithm the belief of node i at 3. We will iteration l innatmimeethselomt te.sAsatgaenbyðXltiðÞitÞmðÁeÞ slot t, every node i can determine the MMSE or MAP estimate of its own state by taking the mean or the mode of its local message XiðtÞ!hðitÞ ðÁÞ. Note that the time slots at different nodes need not be synchronized; the algorithm can be interpreted as being completely asynchronous. Example: Let us consider the correction operation for the example network in Fig. 1, where we perform localization in a 50 Â 50 m2 plane. Assume that the agent nodes 2 and 4 begin with no information about their position, so that bð0Þ X2ðtÞ ðÁÞ and bð0Þ X4ðtÞ ðÁÞ in line 2 of Algorithm 3 are uniform over the entire map. Anchor nodes 1, 3, and 5 have and perfect location bð0Þ X5ðtÞ ðÁÞ are Dirac information, so that bð0Þ X1ðtÞ ðÁÞ, delta functions. We focus bð0Þ X3ðtÞ ðÁÞ, on two successive iterations of Algorithm 3 for agent node 2. Due to symmetry in the network, all the statements below can be applied to agent node 4, mutatis mutandis. 1) Iteration l ¼ 1. All the nodes broadcast their current belief. Agents can remain silent during this step, since their beliefs contain no useful information about their location at this iteration. Agent node 2 has as neighbors Sð!1Þ2 ¼ f1; 3g and computes the message line 8 in Alðg11oÞ!r2i!thXm2ðtÞ ð3ÁÞ, (and based onð1t3Þh!e2!rXe2ðctÞeðiÁvÞe),d using belief bð0Þ X1ðtÞ ðÁÞ (and bð0Þ X3ðtÞ ðÁÞ), as well as on range estimate zð1t!Þ 2 (and zð3t!Þ 2). As expected, the messages ð1Þ 1!2 !X2ðtÞ ðÁÞ and ð1Þ 3!2 !X2ðtÞ ðÁÞ are roughly circular distributions around the positions of the two anchors (see Fig. 9(a)). Node 2 now computes its new belief (line 9 in Algorithm 3) by multiplying ð1Þ 1!2 !X2ðtÞ ðÁÞ, ð1Þ 3!2 !X2ðtÞ ðÁÞ, and its own (uniform) belief which bð0Þ X2ðtÞ ðÁÞ. The result shows the contour is depicted in plot of bð1Þ X2ðtÞ ðÁÞ, Fig. 9(b), a bimodal distribution. Agent node 4 goes through similar cstoeuprsseanisdadlseotearmbiimneosdaitlsdbisetlriiebfutbiðXo14ðnÞtÞ)ð.ÁÞ (which of 2) Iteration l ¼ 2. Agent nodes 2 and 4 broadcast their beliefs to their neighbors (line 6). Agent Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 439 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 9. Consider the point of view of agent node 2 for iteration l ¼ 1 (a)-(b) and iteration l ¼ 2 (c)-(d). (a) At l ¼ 1, anchor nodes 1 and 3 broadcast their beliefs (line 6 of Algorithm 3). Node 2 receives the beliefs and converts them based on range measurements (line 8 of Algorithm 3). The messages ð1Þ 1!2 !X2ðtÞ ðÁÞ and ð1Þ 3!2 !X2ðtÞ ðÁÞ are shown as contour plots. (b) Agent node 2 updates its belief (line 9 of Algorithm 3). Observe that the updated belief is bimodal, as indicated in Fig. 1. (c) At iteration l ¼ 2, node 2 receives beliefs from anchor nodes 1 and 3 and agent 4 (line 7 and ð2Þ 4!2 !X2ðtÞ ðÁÞ of Algorithm are shown as 3co) nantoducropnlovtesr.tOs bthseermve(ltihnaet8ðo24fÞ!2A!lgX2ðotÞ rðÁiÞthismm3o)rbeassperdeaodnoruatntgheamn eða21!Þsu2!rXe2ðmtÞ ðeÁÞnatns.dThð2e3Þ!m2!eXs2ðtÞsðaÁÞg.eTshisð2i1!Þs2b!eXc2ðtÞaðuÁÞs,eiðn23Þ!f2o!rmX2ðtÞaðtÁÞio, n from anchors only has a single source of uncertainty (the range measurement), while information from agents has two sources of uncertainty (the range measurement and the uncertain location of the agent node 4). (d) Agent node 2 updates its belief (line 9 of Algorithm 3) through multiplication of position without the messages ambiguity. ð2Þ 1!2 !X2ðtÞ ðÁÞ, ð2Þ 3!2 !X2ðtÞ ðÁÞ, and ð2Þ 4!2 !X2ðtÞ ðÁÞ. The updated belief is unimodal so that agent node 2 can now determine its node 2 receives beliefs from anchor nodes 1 and 3 and from agent node 4 (line 7). Agent node 2 then ctahnoemdseputtðh2e4Þ!rse2!emXm2ðetÞsðesÁsaÞsgaeg(selisneað2r1Þ!e82)!s. hX2ðotCÞwðoÁnÞn,toinurð23FÞ!ip2g!l.oXt2ð9stÞ(ðcÁoÞ)f,. Observe that the messages from the anchors acorð2r3eÞ!re2!spuXo2ðntÞnðcÁdÞhi¼nagngðt13eoÞ!d2!a: gX2eðtÞnðÁtðÞ21,Þ!4a2,!ndX2ðtÞðtð2h4ÁÞ!Þa2¼tðÁtÞh,ðe11Þ!ism2!emXs2ðstuÞaðcÁgÞhe, broader than those corresponding to the anchors, due to the uncertainty that agent 4 has with respect to its own position. Node 2 computes its new ð2Þ 4!2 !beXl2ðitÞeðfÁÞ(,linðe24Þ!92!) Xb2ðtyÞ ðÁmÞ,ualntidpliytisnogwnð21(Þ!u2n!iXfo2ðtÞrðmÁÞ), belief which bð0Þ X2ðtÞ ðÁÞ. shows The result is depicted in Fig. 9(d), the contour plot of bð2Þ X2ðtÞ ðÁÞ having a unimodal distribution. Thus, agent node 2 can un- ambiguously estimate its own position by taking the mean or mode of bð2Þ X2ðtÞ ðÁÞ (for MMSE or MAP esti- mation, respectively). Similarly, agent 4 can now determine its position without ambiguity. In conclusion, through cooperation, both agents can self-localize. V. TRACTABLE AND REALISTIC UWB RANGING MODELS From the previous section, we know that cooperative ML, MMSE, and MAP localization requires every node i to 440 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks Table 1 Environments Used for Measurement Campaign know the distribution pðzðj!tÞ ijxðitÞ; xðj tÞÞ. Existing ranging models, derived from experimental campaigns, are based on highly idealized signals [110], [111] or significant postprocessing [112]. Such simplifications lead to unrealistic or impractical ranging models. Other UWB measurement campaigns have been undertaken with the goal of characterizing channel parameters such as path loss, fading, and delay spread, independent of the effect of the measurement device and methods [34], [36], [113]. Ranging models extracted from these channel models [23], [86] make implicit assumptions that may not hold in realistic environments, which in turn may lead to unrealistic predictions of localization performance. In order to obtain ranging models that closely reflect practical operating conditions, we have performed an extensive experimental campaign with commercial UWB radios, performing RTOA distance estimation. In this section, we describe the experimental setup, our methodology to extract ranging models, and the resulting ranging models. At the end of this section, we show different ways in which cooperative localization algorithms can cope with NLOS conditions. A. Experimental Setup The experiment consisted of commercial FCC-compliant [114] UWB radios with a bandwidth of approximately 3. 2 GHz centered at 4.7 GHz. Each radio was capable of transmitting and receiving packets through an omnidirectional antenna. To account for the nature of realistic localization networks, which may be composed of off-theshelf parts, range measurements were collected as is, without making any modifications to the hardware or embedded and host software in the UWB radios. A series of five campaigns was performed in different indoor environments around the MIT campus: two campaigns at the Laboratory for Information and Decision Systems (LIDS), two campaigns at the Computer Science and Artificial Intelligence Laboratory (CSAIL), and one campaign in a hangar of the Department of Aeronautics and Astronautics. Details of the environments are given in Table 1. Of these campaigns, two were in NLOS conditions (CSAIL-NLOS and LIDS-NLOS), while the remaining three were in line-of-sight (LOS) conditions. In each environment, the nodes were placed 89 cm above the ground (see Fig. 10). One radio was static, while the other moved in 25 cm increments towards the static radio. At each separation distance dsep, 1000 ranging measurements were collected. We do not perform averaging of measurements, unlike [110] and [111]. Floor plans10 for the LIDS and CSAIL experimental campaign are provided in Fig. 11. B. Ranging Models We observed that a histogram of the 1000 ranging measurements collected at any distance dsep typically contains one large peak near dsep plus a small set of outliers on each side of the peak (see Fig. 12). The outliers are consistently located at large distances from the main peak, sometimes producing negative range measurements. The fact that some measured ranges are significantly smaller or greater than the true distance dsep indicates that far-lying outliers are likely caused by the ranging algorithm (both positively and negatively biased outliers) and multipath (positive outliers due to strong reflections) rather than NLOS conditions. Further examination revealed that the time of flight estimated11 by the UWB nodes, using an existing proprietary algorithm, exhibits high variance and possibly large errors. These findings indicate that the measurement devices and ranging protocols are important factors to take into consideration when characterizing UWB range measurements. The operating environment has a significant effect on the distribution of the measurements. The measurements collected in the CSAIL hallway (with no clutter) have many fewer outliers than those collected in the LIDS hallway (with adjacent concrete pillars and walls) and in the hangar (with large crates and other objects nearby). Measurements made in NLOS conditions tend to have more outliers than in LOS conditions. Additionally, the nature of the blockage affects the measurements in NLOS conditions. The glass doors in CSAIL caused many fewer outliers than the concrete wall in LIDS. These findings corroborate the results in other UWB measurement campaigns, e.g., [30] and [111]. Based on these histograms, we concluded that a reasonable underlying distribution for the measurements collected in a given environment E at distance dsep is a Fig. 10. Experimental setup involving two FCC-compliant UWB radios. 10Detailed floor plans are available at floorplans.mit.edu/pdfs/ 32_6.pdf (LIDS) and floorplans.mit.edu/pdfs/32_6.pdf (CSAIL). 11That is, tB;rec À tB;send in the notation from Section II-A. Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 441 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 11. Floor plans of (a) LIDS and (b) CSAIL experimental campaigns. The dots represent the initial positions of the UWB radios. One radio is static (the red dot), while the other radio (the black dot) moves in 25 cm increments towards the static radio. Gaussian mixture density with three components, labeled k ¼ 1; 2; and 3 for the lower outliers, main component, and upper outliers, respectively. Each component is parameterized by a mean E;kðdsepÞ, a variance 2E;kðdsepÞ, and a weight wE;kðdsepÞ. Hence, the distribution of range measurements collected at distance dsep is given by X3 pðd^jdsep; EÞ ¼ wE;kðdsepÞN d^ E;kðdsepÞ; 2E;kðdsepÞ (42) k¼1 where N xð; 2Þ denotes the Gaussian distribution with mean and variance 2, evaluated in x. In order to estimate the mean E;kðdsepÞ, variance 2E;kðdsepÞ, and weight wE;kðdsepÞ for each k and E, we applied the expectation-maximization (EM) algorithm [115], [116] to the set of 1000 measurements collected at each discrete distance dsep in environment E. The estimated Gaussian parameters capture the features of the histograms. The main component k ¼ 2 typically has a large weight, a small variance, and a mean with small bias. Measurements made in NLOS conditions exhibit a larger positive bias than those in LOS conditions. This agrees with other UWB measure- ment campaigns and models [30], [117]. The lower and upper outliers, represented by components k ¼ 1 and k ¼ 3 respectively, are characterized by smaller weights than k ¼ 2 and larger variances. Unlike [111], we find that the variance of the measurements does not always increase with distance. Our results also demonstrate that the effect of the surrounding environment may outweigh the effect of distance and LOS/NLOS conditions. Finally, we model the distribution of the ranging error for the continuous value of distances d by fitting quadratic polynomials PE;;kðdÞ, PE;2;kðdÞ, and PE;w;kðdÞ to E;kðdsepÞ, 2E;kðdsepÞ, a n d wE;kðdsepÞ, r e s p e c t i v e l y . S i n c e wE;kðdsepÞ ( 1 for k ¼ 1 and k ¼ 3, the outliers are easy to identify, and we only report in Table 2 the coefficients for the resulting polynomials of form d2 þ d þ for the main mode of the distributions. Our final model of the UWB ranging measurements d^as a function of true distance d in environment E is a Gaussian density described by pðd^jd; EÞ ¼ N À d^ PE;;2ðdÞ; Á PE;2;2ðdÞ : (43) Fig. 12. Histogram of range measurements, environment LIDS-LOS, at With the polynomial coefficients as its only parameters, this dsep ¼ 16:25 m. Outliers on either side of the main peak are visible. UWB ranging model is tractable and easily implemented in 442 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks Table 2 Polynomial Coefficients of Ranging Models d2 þ d þ 2) When LOS/NLOS detection is not performed, but nodes have knowledge of the environment E and the locations of obstructions, then [30], [122] X pðd^j!ijxi; xjÞ ¼ pðd^j!ijxi; xj; ijÞpðijjxi; xjÞ (46) ij where pðijjxi; xjÞ is either zero or one, depending on whether there is an obstruction between the positions xi and xj. 3) When LOS/NLOS detection is performed, it can be based on some underlying statistics j!i extracted from the received signal [89], such as the mean excess delay. We can replace ^j!i by j!i in (44), in which case nodes require knowledge of pðj!ijijÞ rather than pð^j!ijijÞ. localization systems. Moreover, it accurately describes a practical ranging device operating in realistic environments. C. NLOS Conditions Our measurements indicate that ranging performance depends on the LOS/NLOS conditions. In a practical setting, radios may be implemented with the capability for NLOS detection [88], [89], [118]–[121]. Let us introduce the signal metrics estimated by node i as zðj!tÞ i ¼ ½d^ðj!tÞ i; ^ðj!tÞ i, where d^ðj!tÞ i denotes the estimate of kxði tÞ À xðj tÞk by node i, and ^ðj!tÞ i denotes the decision at node i regarding the LOS/ NLOS condition ðijtÞ 2 fLOS; NLOSg between nodes i and j at time t. The function pðzðj!tÞ ijxði tÞ; xðj tÞÞ then becomes (omitting the time index t) VI. INDOOR LOCALIZATION: A CASE STUDY In this section, we combine the algorithms from Section IV with the ranging models from Section V. We first describe the performance criterion and simulation setup and then provide numerical results for both static and dynamic location-aware networks. A. Performance Criterion and Simulation Setup To evaluate localization performance, we employ the outage probability criterion: for a certain scenario (number of agents, number of anchors, anchor positions, time index t, and LOS/NLOS conditions) and a certain allowable error eth (say, 2 m), an agent is said to be in outage when its position error kX À X^k exceeds eth. The outage probability is then given by X pðd^j!i; ^j!ijxi; xjÞ ¼ pðd^j!ijxi; xj; ijÞ ij Â pð^j!ijijÞpðijjxi; xjÞ: (44) Variations of (44) include the following. 1) When LOS/NLOS detection is not performed, and nodes have no information regarding their environment, then ^j!i is not computed, pðijjxi; xjÞ ¼ pðijÞ and pðzj!ijxi; xjÞ reverts to [51], [87] X pðd^j!ijxi; xjÞ ¼ pðd^j!ijxi; xj; ijÞpðijÞ: (45) ij In this case, pðijÞ is assumed to be predetermined within the radio or simply set to 1/2. PoutðethÞ ¼ ÈÈ IE II kX À X^k > ÉÉ eth (47) where IIfPg is the indicator function, which is zero when proposition P is false and one otherwise. The expectation in (47) is taken with respect to the locations of the agents. The outage probability is implicitly conditioned on the scenario. To characterize the outage performance of the different cooperative localization algorithms developed in Section IV, we have performed computer simulations using on the ranging models described in Section V. We considered localization in a 100 by 100 m2 environment with 13 anchors and 100 or 50 agents. Anchors are static, while agents may be mobile. Every node can range with neighbors within 20 m. Messages are represented by samples [14], [18], [123]: in our case, 500 samples for internode messages and 2000 samples for intranode messages. Note that messages may be represented in Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 443 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 13. The benefit of cooperation. The 13 squares are the anchors, the 100 blue dots are the agents, and the white circles are the estimated positions of the agents. The lines represent localization errors, connecting the estimated position and the true position of every agent. (a) shows the performance of MMSE localization without cooperation. (b) shows the performance of the cooperative MMSE localization algorithm after four iterations. other ways, using techniques such as the extended Kalman filter [124], [125] or Rao–Blackwellization [97], [126]. B. Static Networks We now illustrate the performance of MMSE localiza- tion in LOS conditions. Initially, none of the agents has information about their position, represented by a uniform a priori distribution. The agents then perform MMSE localization, the results of which are shown in Fig. 13 for a particular realization of the network. The lines in Fig. 13 connect the MMSE estimate and the true position of the agent. It can be seen in Fig. 13(a) that without cooperation, only a few agents can be localized accurately. By contrast, Fig. 13(b) shows that with cooperation, all agents but one are localized with high accuracy after only four iterations. The single agent that cannot be localized is connected to only two other nodes (one agent and one anchor), and therefore unable to determine its position without ambiguity. A different view is offered in Fig. 14, showing the evolution of the localization error for 100 agents as a function of the iteration index. For a systematic comparison of different localization algorithms, we have evaluated the outage probability for noncooperative and cooperative MMSE localization, as well as cooperative LS localization. The cooperative LS algorithm uses a fixed step size and is initialized with the noncooperative MMSE position estimates. As a benchmark, we have also included a centralized MMSE algorithm.12 Fig. 15 shows the outage probability as a function of allowable error for networks with 100 agents over an ensemble of 20 random network instantiations. We observe that noncooperative localization results in large outage probabilities, greater than 50% for allowable errors below 5 m. Cooperative LS can reduce the outage probability to some extent, while cooperative MMSE offers significant additional performance gains. In fact, the performance of cooperative MMSE is close to centralized MMSE. At an allowable error of eth ¼ 1 m, about 90% of the agents are in outage for noncooperative localization. The outage probability drops to 40% for cooperative LS, and is further reduced to less than 1% for cooperative MMSE. From our simulations, we observe that for this scenario the cooperative MMSE converges13 in about four iterations, whereas cooperative LS requires many more iterations to converge. Thus, while cooperative MMSE certainly requires more computations per node, it Fig. 14. A contour plot of the localization error (logarithmic) for every agent, as a function of the iteration index. 12The centralized algorithm is closely related to [14] and corresponds to an FG (see Fig. 7) where vertices j!i and i!j are merged into a single vertex. 13By convergence, we mean that the outage curve no longer changes noticeably for subsequent iterations. 444 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 15. Comparison of different localization algorithms for 13 anchors and 100 agents. Cooperative LS outperforms noncooperative MMSE localization. The cooperative MMSE approach offers significant performance gains and attains an outage performance close to that of the centralized algorithm. Fig. 17. Outage probability for 13 static anchors and 100 mobile agents. The agents move according to a Gaussian random walk. After 20 time slots, noncooperative MMSE localization results in high outages, whereas outages remain low for cooperative MMSE localization. converges in far fewer iterations. This is a critical point for network algorithm design, since every iteration requires packets to be broadcast over the network, increasing interference and reducing throughput. Moreover, more iterations corresponds to an increased delay in determining one’s position. This makes cooperative MMSE localization more suitable for real-time applications. Similar results are shown in Fig. 16 for a setting with 50 agents. By comparing Figs. 15 and 16, we observe that the outage performance for noncooperative localization attains similar values, irrespective of the number of agents, while cooperative localization improves as the network density increases. This was also observed in [127]. C. Dynamic Networks Let us now consider the case when agents are mobile. As a in a and worst case scenario, every agent i direction dði tÞ $ N ði tÞ ð0; at every time 1Þ.14 Agents step t, move mwoitvhesðiatÞd$istUan½0ce; 2dði tÞÞ independently with respect to one another and from time slot to time slot. At time t ¼ 0, every node is assumed to have perfect knowledge of its position, so that the a priori distribution of every agent is a Dirac delta function. Agents do not know in which direction they move, but they do know the distance they travel.15 Hence, zði;tsÞelf ¼ d^ði tÞ ¼ dði tÞ and p zði;tsÞelf jxði tÀ1Þ; xði tÞ ¼ xði tÞ À xði tÀ1Þ À zði;tsÞelf (48) so that p xði tÞjxði tÀ1Þ p zði;tsÞelf jxði tÀ1Þ; xði tÞ / xði tÞ À xði tÀ1Þ À zði;tsÞelf : (49) Fig. 16. Comparison of different localization algorithms for 13 anchors and 50 agents. Cooperative LS outperforms noncooperative MMSE localization. The cooperative MMSE approach offers significant performance gains and attains an outage performance close to that of the centralized algorithm. For fair comparison between noncooperative and cooperative localization, we reduce the complexity of Algorithm 3 14Here U½a; bÞ denotes the uniform distribution between a 2 IR and b 2 IR, a G b. 15Agents could be equipped with a pedometer, for instance. Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 445 Wymeersch et al.: Cooperative Localization in Wireless Networks Fig. 18. Contour plots of the outage probability as a function of time. (a) corresponds to noncooperative MMSE localization, while (b) corresponds to cooperative MMSE localization. In the noncooperative case, outages increase as time progresses, while for the cooperative case, outages remain low for all times. by setting Niter ¼ 1 (see line 4). Fig. 17 shows the outage probability for time slots t ¼ 1 and t ¼ 20, for both noncooperative and cooperative MMSE localization. Observe that after 20 time slots, the noncooperative approach exhibits significant performance degradation, while cooperative localization maintains fairly low outage probabilities. For a more detailed investigation of the behavior over time, we refer to Fig. 18, which shows the outages as a function of time. In the noncooperative case, performance clearly degrades with time. In the cooperative case, the network quickly achieves a steady-state performance, and outages remain low. VII. CONCLUSION Location-awareness is a key feature of future-generation wireless networks, enabling a multitude of applications in the military (e.g., blue force tracking), public (e.g., searchand-rescue), and commercial (e.g., navigation) sectors. Cooperation among nodes has the potential to dramatically improve localization performance. In this paper, we have given an overview of the main approaches to cooperative localization from the viewpoint of estimation theory and factor graphs. We have shown how to create a network FG by mapping vertices of the FG onto the network topology. A network message passing algorithm can then be obtained by appropriate message scheduling, accounting for the time-varying network topology. The resulting algorithm (SPAWN) is a distributed, cooperative localization algorithm that outperforms many conventional noncooperative and cooperative localization techniques. We have per- formed an extensive UWB measurement campaign to determine tractable yet realistic ranging models. These models were used to validate SPAWN in a large-scale network involving 100 agents. Location-awareness has a great number of associated research challenges, including efficient, robust, and accurate ranging algorithms; low-complexity implementations of algorithms such as SPAWN; integration of different signal metrics; LOS/NLOS detection; investigation of interference effects, update rate, and message representations; and the determination of fundamental performance bounds. A next phase to the development of this field involves the interaction of SPAWN with higher level communication applications, such as location-aware routing [128], location-aware cryptography [129], locationaware information delivery [130], and location-aware computing [131], to name but a few. h Acknowledgment The authors would like to thank Y. Shen, U. J. Ferner, G. Chrisikos, A. Conti, and W. M. Gifford for their careful reading of the manuscript and valuable suggestions. They are also grateful to Z. Botev for providing them with a fast kernel density estimator, to U. Ferner for helping with the simulations for mobile networks, and to the TELIN department and P. Serbruyns for providing them with the computational resources to perform their extensive simulations. Finally, they would like to thank everyone involved in the UWB measurement campaign, in particular S. J. Teller for the lively discussions. REFERENCES [1] F. Gustafsson and F. Gunnarsson, BMobile positioning using wireless networks: Possibilities and fundamental limitations based on available wireless network measurements,[ IEEE Signal Process. Mag., vol. 22, pp. 41–53, Jul. 2005. [2] S. Gezici, Z. Tian, G. B. Giannakis, H. Kobayashi, A. F. Molisch, H. V. Poor, and Z. Sahinoglu, BLocalization via ultra-wideband radios: A look at positioning aspects for future sensor networks,[ IEEE Signal Process. Mag., vol. 22, pp. 70–84, Jul. 2005. [3] D. Dardari, A. Conti, C. Buratti, and R. Verdone, BMathematical evaluation of environmental monitoring estimation error through energy-efficient wireless sensor 446 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 networks,[ IEEE Trans. Mobile Comput., vol. 6, pp. 790–802, Jul. 2007. [4] A. Mainwaring, D. Culler, J. Polastre, and R. S. J. Anderson, BWireless sensor networks for habitat monitoring,[ in Proc. 1st ACM Int. Workshop Wireless Sensor Netw. Applicat. (WSNA’02), New York, 2002, pp. 88–97. [5] N. Bulusu, J. Heidemann, and D. Estrin, BGPS-less low-cost outdoor localization for Wymeersch et al.: Cooperative Localization in Wireless Networks very small devices,[ IEEE Pers. Commun., vol. 7, pp. 28–34, Oct. 2000. [6] K. Lyytinen, Y. Yoo, U. Varshney, M. Ackerman, G. Davis, M. Avital, D. Robey, S. Sawyer, and C. Sorensen, BSurfing the next wave: Design and implementation challenges of ubiquitous computing environments,[ Commun. Assoc. Inf. Syst., vol. 13, no. 716, pp. 697–716, 2004. [7] T. Yan, T. He, and J. Stankovic, BDifferentiated surveillance for sensor networks,[ in Proc. 1st Int. Conf. Embedded Networked Sensor Syst., New York, Nov. 2003, pp. 51–62. [8] B. Robinson, BWho goes there?’’ IEEE Spectr., vol. 40, pp. 42–47, Oct. 2003. [9] A. H. Sayed, A. Tarighat, and N. Khajehnouri, BNetwork-based wireless location: Challenges faced in developing techniques for accurate wireless location information,[ IEEE Signal Process. Mag., vol. 22, no. 4, pp. 24–40, Jul. 2005. [10] T. Budinger, BBiomonitoring with wireless communications,[ Annu. Rev. Biomed. Eng., vol. 5, no. 1, pp. 383–412, Aug. 2003. [11] R. Fontana, E. Richley, and J. Barney, BCommercialization of an ultra wideband precision asset location system,[ in Proc. IEEE Int. Conf. Ultra-Wideband (ICUWB), Nov. 2003, pp. 369–373. [12] J. Caffery and G. Stuber, BRadio location in urban CDMA microcells,[ in Proc. IEEE Int. Symp. Personal, Indoor Mobile Radio Commun., Toronto, ON, Canada, Sep. 1995, vol. 2, pp. 858–862. [13] J. Warrior, E. McHenry, and K. McGee, BThey know where you are-location detection,[ IEEE Spectr., vol. 40, pp. 20–25, Jul. 2003. [14] A. T. Ihler, J. W. Fisher, III, R. L. Moses, and A. S. Willsky, BNonparametric belief propagation for self-localization of sensor networks,[ IEEE J. Sel. Areas Commun., vol. 23, pp. 809–819, Apr. 2005. [15] R. Moses, D. Krishnamurthy, and R. Patterson, BA self-localization method for wireless sensor networks,[ EURASIP J. Appl. Signal Process., vol. 2003, no. 4, pp. 348–358, Mar. 2003. [16] S. Se, D. Lowe, and J. Little, BMobile robot localization and mapping with uncertainty using scale-invariant visual landmarks,[ Int. J. Robot. Res., vol. 21, no. 8, p. 735, Aug. 2002. [17] D. Fox, J. Hightower, L. Liao, D. Schulz, and G. Borriello, BBayesian filtering for location estimation,[ IEEE Pervasive Comput., vol. 2, pp. 24–33, Jul.–Sep. 2003. [18] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, BRobust Monte Carlo localization for mobile robots,’’ Artif. Intell., vol. 128, no. 1, pp. 99–141, May 2001. [19] Y. Shen and M. Z. Win, BFundamental limits of wideband localization accuracy via Fisher information,[ in Proc. IEEE Wireless Commun. Netw. Conf., Kowloon, Hong Kong, China, Mar. 2007, pp. 3046–3051. [20] Y. Shen and M. Z. Win, BPerformance of localization and orientation using wideband antenna arrays,[ in Proc. IEEE Int. Conf. Ultra-Wideband (ICUWB), Singapore, Sep. 2007, pp. 288–293. [21] Y. Shen, H. Wymeersch, and M. Z. Win, BFundamental limits of wideband cooperative localization via Fisher information,[ in Proc. IEEE Wireless Commun. Netw. Conf., Kowloon, Hong Kong, China, Mar. 2007, pp. 3951–3955. [22] M. Z. Win, Y. Shen, and H. Wymeersch, BOn the position error bound in cooperative networks: A geometric approach,[ in Proc. IEEE Int. Symp. Spread Spectr. Tech. Applicat., Bologna, Italy, Aug. 2008, pp. 637–643. [23] D. Dardari, A. Conti, U. J. Ferner, A. Giorgetti, and M. Z. Win, BRanging with ultrawide bandwidth signals in multipath environments,[ Proc. IEEE, vol. 97, no. 2, Feb. 2009. [24] J.-Y. Lee and R. A. Scholtz, BRanging in a dense multipath environment using an UWB radio link,[ IEEE J. Sel. Areas Commun., vol. 20, pp. 1677–1683, Dec. 2002. [25] E. D. Kaplan and C. J. Hegarty, Eds., GPS: Principles and Applications. Reading, MA: Artech House, 2006. [26] M. Z. Win and R. A. Scholtz, BImpulse radio: How it works,[ IEEE Commun. Lett., vol. 2, pp. 36–38, Feb. 1998. [27] M. Z. Win and R. A. Scholtz, BUltra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communications,[ IEEE Trans. Commun., vol. 48, pp. 679–691, Apr. 2000. [28] M. Z. Win, BA unified spectral analysis of generalized time-hopping spread-spectrum signals in the presence of timing jitter,[ IEEE J. Sel. Areas Commun., vol. 20, pp. 1664–1676, Dec. 2002. [29] D. B. Jourdan, D. Dardari, and M. Z. Win, BPosition error bound for UWB localization in dense cluttered environments,[ IEEE Trans. Aerosp. Electron. Syst., vol. 44, pp. 613–628, Apr. 2008. [30] D. Dardari, A. Conti, J. Lien, and M. Z. Win, BThe effect of cooperation on localization systems using UWB experimental data,[ EURASIP J. Appl. Signal Process. (Special Issue on Wireless Cooperative Networks), vol. 2008, pp. 1–11, 2008. [31] H. Wymeersch, U. Ferner, and M. Z. Win, BCooperative Bayesian self-tracking for wireless networks,[ IEEE Commun. Lett., vol. 12, pp. 505–507, Jul. 2008. [32] M. Z. Win and R. A. Scholtz, BOn the robustness of ultra-wide bandwidth signals in dense multipath environments,[ IEEE Commun. Lett., vol. 2, pp. 51–53, Feb. 1998. [33] M. Z. Win and R. A. Scholtz, BOn the energy capture of ultra-wide bandwidth signals in dense multipath environments,[ IEEE Commun. Lett., vol. 2, pp. 245–247, Sep. 1998. [34] M. Z. Win and R. A. Scholtz, BCharacterization of ultra-wide bandwidth wireless indoor communications channel: A communication theoretic view,[ IEEE J. Sel. Areas Commun., vol. 20, pp. 1613–1627, Dec. 2002. [35] D. Cassioli, M. Z. Win, and A. F. Molisch, BThe ultra-wide bandwidth indoor channel: From statistical model to simulations,[ IEEE J. Sel. Areas Commun., vol. 20, pp. 1247–1257, Aug. 2002. [36] A. F. Molisch, D. Cassioli, C.-C. Chong, S. Emami, A. Fort, B. Kannan, J. Karedal, J. Kunisch, H. Schantz, K. Siwiak, and M. Z. Win, BA comprehensive standardized model for ultrawideband propagation channels,[ IEEE Trans. Antennas Propag. (Special Issue on Wireless Communications), vol. 54, pp. 3151–3166, Nov. 2006. [37] C. Falsi, D. Dardari, L. Mucchi, and M. Z. Win, BTime of arrival estimation for UWB localizers in realistic environments,[ EURASIP J. Appl. Signal Process. (Special Issue on Wireless Location Technologies and Applications), vol. 2006, pp. 1–13, 2006. [38] D. Dardari, C.-C. Chong, and M. Z. Win, BThreshold-based time-of-arrival estimators in UWB dense multipath channels,[ IEEE Trans. Commun., vol. 56, pp. 1366–1378, Aug. 2008. [39] A. Ridolfi and M. Z. Win, BUltrawide bandwidth signals as shot-noise: A unifying approach,[ IEEE J. Sel. Areas Commun., vol. 24, pp. 899–905, Apr. 2006. [40] W. Suwansantisuk, M. Z. Win, and L. A. Shepp, BOn the performance of wide-bandwidth signal acquisition in dense multipath channels,[ IEEE Trans. Veh. Technol. (Special Section on Ultra-Wideband Wireless CommunicationsVA New Horizon), vol. 54, pp. 1584–1594, Sep. 2005. [41] W. Suwansantisuk and M. Z. Win, BMultipath aided rapid acquisition: Optimal search strategies,[ IEEE Trans. Inf. Theory, vol. 53, pp. 174–193, Jan. 2007. [42] T. Q. S. Quek and M. Z. Win, BAnalysis of UWB transmitted-reference communication systems in dense multipath channels,[ IEEE J. Sel. Areas Commun., vol. 23, pp. 1863–1874, Sep. 2005. [43] T. Q. S. Quek, M. Z. Win, and D. Dardari, BUnified analysis of UWB transmitted-reference schemes in the presence of narrowband interference,[ IEEE Trans. Wireless Commun., vol. 6, pp. 2126–2139, Jun. 2007. [44] D. Cassioli, M. Z. Win, F. Vatalaro, and A. F. Molisch, BLow-complexity Rake receivers in ultra-wideband channels,[ IEEE Trans. Wireless Commun., vol. 6, pp. 1265–1275, Apr. 2007. [45] M. Chiani and A. Giorgetti, BCoexistence between UWB and narrowband wireless communication systems,[ Proc. IEEE, vol. 97, no. 2, Feb. 2009. [46] H. Wymeersch, Y. Shen, J. Lien, and M. Z. Win, BLocation, location, location: Performance bounds and algorithms for cooperative localization in UWB networks,[ in Proc. 36th Annu. IEEE Commun. Theory Workshop, Sedona, AZ, May 2007. [47] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero, III, R. L. Moses, and N. S. Correal, BLocating the nodes: Cooperative localization in wireless sensor networks,[ IEEE Signal Process. Mag., vol. 22, pp. 54–69, Jul. 2005. [48] N. Alsindi, K. Pahlavan, and B. Alavi, BA novel cooperative localization algorithm for indoor sensor networks,[ in Proc. IEEE Int. Symp. Personal, Indoor Mobile Radio Commun., Sep. 2006, pp. 1–6. [49] A. Howard, M. Mataric, and G. Sukhatme, BPutting the FI_ in Fteam_: An ego-centric approach to cooperative localization,[ in Proc. IEEE Int. Conf. Robot. Autom., 2003, vol. 1. [50] M. W. Carter, H. H. Jin, M. A. Saunders, and Y. Ye, BSPACELOC: An adaptive subproblem algorithm for scalable wireless sensor network localization,[ SIAM J. Optim., pp. 1102–1128, 2006. [51] B. Denis, J. B. Pierrot, and C. Abou-Rjeily, BJoint distributed synchronization and positioning in UWB ad hoc networks using TOA,[ IEEE Trans. Microwave Theory Tech., vol. 54, pp. 1896–1911, Jun. 2006. [52] A. Howard, M. Mataric, and G. Sukhatme, BLocalization for mobile robot teams: A distributed MLE approach,[ Exper. Robot. VIII, vol. 5, pp. 146–155, 2003. [53] K. Langendoen and N. Reijers, BDistributed localization in wireless sensor networks: A quantitative comparison,[ Elsevier Comput. Netw., vol. 43, no. 4, pp. 499–518, Nov. 2003, Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 447 Wymeersch et al.: Cooperative Localization in Wireless Networks Faculty of Information Technology and Systems, Delft Univ. of Technology. [54] N. B. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller, BAnchor-Free Distributed localization in sensor networks,[ Massachusetts Inst. of Technol., Tech. Rep. TR-892. [Online]. Available: http://www. nms.lcs.mit.edu/cricket [55] C. Savarese, J. M. Rabaey, and J. Beutel, BLocationing in distributed ad-hoc wireless sensor networks,[ in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., May 7–11, 2001, vol. 4, pp. 2037–2040. [56] M. Rydstrom, E. Strom, and A. Svensson, BRobust sensor network positioning based on projections onto circular and hyperbolic convex sets (POCS),[ in Proc. IEEE Workshop Signal Process. Adv. Wireless Commun., Jul. 2006, pp. 1–5. [57] B. Cheng, R. Hudson, F. Lorenzelli, L. Vandenberghe, and K. Foo, BDistributed Gauss-Newton method for node localization in wireless sensor networks,[ in Proc. IEEE Workshop Signal Process. Adv. Wireless Commun., Jun. 2005, pp. 915–919. [58] D. Blatt and A. Hero, BEnergy-based sensor network source localization via projection onto convex sets,[ IEEE Trans. Signal Process., vol. 54, pp. 3614–3619, Sep. 2006. [59] A. Galstyan, B. Krishnamachari, K. Lerman, and S. Pattem, BDistributed online localization in sensor networks using a moving target,[ in Proc. 3rd Int. Symp. Inf. Process. Sensor Netw. (ISPN), Apr. 2004, pp. 61–70. [60] R. Madhavan, K. Fregene, and L. Parker, BDistributed cooperative outdoor multirobot localization and mapping,[ Auton. Robots, vol. 17, no. 1, pp. 23–39, Jul. 2004. [61] G. Di Stefano, F. Graziosi, and F. Santucci, BDistributed positioning algorithm for ad-hoc networks,[ in Proc. Int. Workshop Ultra Wideband Syst. (IWUWBS), Jun. 2003. [62] H. L. Van Trees, Detection, Estimation and Modulation Theory. New York: Wiley, 1968, vol. 1. [63] D. MacKay, Information Theory, Inference and Learning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, 2003. [64] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, BFactor graphs and the sum-product algorithm,[ IEEE Trans. Inf. Theory, vol. 47, pp. 498–519, Feb. 2001. [65] H.-A. Loeliger, BAn introduction to factor graphs,[ IEEE Signal Process. Mag., vol. 21, pp. 28–41, Jan. 2004. [66] H. Wymeersch, Iterative Receiver Design. Cambridge, U.K.: Cambridge Univ. Press, 2007. [67] N. Patwari and A. O. Hero, III, BUsing proximity and quantized RSS for sensor localization in wireless networks,[ in Proc. IEEE/ACM 2nd Workshop Wireless Sensor Netw. Applicat., Sep. 2003, pp. 20–29. [68] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, BLocalization from mere connectivity,[ in Proc. ACM Symp. Mobile Ad Hoc Netw. Comput., Jun. 2003, pp. 201–212. [69] S. Guha, R. Murty, and E. Sirer, BSextant: A unified node and event localization framework using non-convex constraints,[ in Proc. ACM Symp. Mobile Ad Hoc Netw. Comput., May 2005, pp. 205–216. [70] Y. Jiang and V. Leung, BAn asymmetric double sided two-way ranging for crystal offset,’’ Proc. Int. Symp. Signals, Syst. Electron. 2007 (ISSSE), Jul. 2007, pp. 525–528. [71] J. How, N. Pohlman, and C. Park, BGPS estimation algorithms for precise velocity, slip and race-track position measurements,[ in SAE Int., Dec. 2002. [72] R. Li, B. Archinal, R. Arvidson, J. Bell, P. Christensen, L. Crumpler, D. Des Marais, K. Di, T. Duxbury, M. Golombek et al., BSpirit rover localization and topographic mapping at the landing site of Gusev crater, Mars,[ J. Geophys. Res, vol. 111, Jan. 2006. [73] J. O’Kane and S. LaValle, BLocalization with limited sensing,[ IEEE Trans. Robot. Autom., vol. 23, pp. 704–716, Aug. 2007. [74] A. Brown, BGPS/INS uses low-cost MEMS IMU,[ IEEE Aerosp. Electron. Syst. Mag., vol. 20, pp. 3–10, Sep. 2005. [75] G. Mao, B. Fidan, and B. D. O. Anderson, BWireless sensor network localization techniques,[ Comput. Netw., vol. 51, no. 10, pp. 2529–2553, Jan. 2007. [76] L. Fang, W. Du, and P. Ning, BA beacon-less location discovery scheme for wireless sensor networks,[ in Proc. IEEE Joint Conf. IEEE Comput. Commun. Soc., Mar. 2005, vol. 1, pp. 161–171. [77] E. Evenson, A. Martin, and R. Sherman, BThe accuracy of multiple sensor time and bearing localization,[ Oceans, vol. 2, pp. 126–129, Sep. 1970. [78] J. J. Caffery and G. L. Stuber, BOverview of radiolocation in CDMA cellular systems,[ IEEE Commun. Mag., vol. 36, pp. 38–45, Apr. 1998. [79] Y. Zhao, BStandardization of mobile phone positioning for 3G systems,[ IEEE Commun. Mag., vol. 40, pp. 108–116, Jul. 2002. [80] K. Pahlavan, X. Li, and J. P. Makela, BIndoor geolocation science and technology,[ IEEE Commun. Mag., vol. 40, pp. 112–118, Feb. 2002. [81] T. Pavani, G. Costa, M. Mazzotti, A. Conti, and D. Dardari, BExperimental results on indoor localization techniques through wireless sensors network,[ in Proc. IEEE Semiannual Veh. Technol. Conf., Melbourne, Australia, May 2006, vol. 2, pp. 663–667. [82] P. Bahl and V. N. Padmanabhan, BRADAR: An in-building RF-based user location and tracking system,[ in Proc. IEEE Joint Conf. IEEE Comput. Commun. Soc., Tel Aviv, Israel, Mar. 2000, vol. 2, pp. 775–784. [83] A. LaMarca, Y. Chawathe, S. Consolvo, J. Hightower, I. Smith, J. Scott, T. Sohn, J. Howard, J. Hughes, F. Potter et al., BPlace Lab: Device positioning using radio beacons in the wild,[ in Proc. IEEE Int. Conf. Pervasive Comput. Commun., 2005, vol. 3468, pp. 116–133. [84] D. De Luca, F. Mazzenga, C. Monti, and M. Vari, BPerformance evaluation of indoor localization techniques based on RF power measurements from active or passive devices,[ EURASIP J. Appl. Signal Process., vol. 2006, no. 1, pp. 160–160, 2006. [85] K. Yu and I. Oppermann, BPerformance of UWB position estimation based on time-of-arrival measurements,[ in Proc. Int. Workshop Ultra Wideband Syst. (IWUWBS), Oulu, Finland, May 2004, pp. 400–404. [86] D. B. Jourdan, J. J. Deyst, M. Z. Win, and N. Roy, BMonte-Carlo localization in dense multipath environments using UWB ranging,[ in Proc. IEEE Int. Conf. Ultra-Wideband (ICUWB), Zu¨rich, Switzerland, Sep. 2005, pp. 314–319. [87] B. Denis, L. Ouvry, B. Uguen, and F. Tchoffo-Talom, BAdvanced Bayesian filtering techniques for UWB tracking systems in indoor environments,[ in Proc. IEEE Int. Conf. Ultra-Wideband (ICUWB), Sep. 2005. [88] I. Gu¨ven¸c, C.-C. Chong, and F. Watanabe, BNLOS identification and mitigation for UWB localization systems,[ in Proc. IEEE Wireless Commun. Networking Conf., Kowloon, Hong Kong, China, Mar. 2007, pp. 1571–1576. [89] I. Gu¨ven¸c, C.-C. Chong, F. Watanabe, and H. Inamura, BNLOS identification and weighted least-squares localization for UWB systems using multipath channel statistics,[ EURASIP J. Adv. Signal Process., vol. 2008, 2008. [90] A. Molisch, Y. Nakache, P. Orlik, J. Zhang, Y. Wu, S. Gezici, S. Kung, H. Kobayashi, H. Poor, Y. Li et al., BAn efficient low-cost time-hopping impulse radio for high data rate transmission,’’ Proc. Wireless Personal Multimedia Conf., 2005, vol. 2005, no. 3, pp. 397–412. [91] IEEE Standard for Information TechnologyVTelecommunications and Information Exchange Between SystemsVLocal and Metropolitan Area NetworksVSpecific Requirement Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs), IEEE Std 802.15.4a-2007 (Amendment to IEEE Std 802.15.4-2006), 2007. [92] T. A. Cover and J. A. Thomas, Elements of Information Theory, 1st ed. New York: Wiley, 1991. [93] T. Minka, BDivergence measures and message passing,[ Microsoft Research, Tech. Rep. MSR-TR-2005-173, 2005. [94] J. S. Yedidia, W. T. Freeman, and Y. Weiss, BConstructing free energy approximations and generalized belief propagation algorithms,[ IEEE Trans. Inf. Theory, vol. 51, pp. 2282–2312, Jul. 2005. [95] G. D. Forney, Jr., BCodes on graphs: Normal realizations,[ IEEE Trans. Inf. Theory, vol. 47, pp. 520–545, Feb. 2001. [96] Y. Weiss and W. T. Freeman, BCorrectness of belief propagation in gaussian graphical models of arbitrary topology,[ Neural Comput., vol. 13, no. 10, pp. 2173–2200, Oct. 2001. [97] A. Doucet, N. de Freitas, and N. Gordon, Eds., BSequential Monte Carlo methods in practice,[ in Particle Filters for Mobile Localization. New York: Springer-Verlag, 2001. [98] M. Arulampalam, S. Maskell, N. Gordon, T. Clapp, D. Sci, T. Organ, and S. Adelaide, BA tutorial on particle filters for online nonlinear/non-GaussianBayesian tracking,[ IEEE Trans. Signal Process., vol. 50, pp. 174–188, Feb. 2002. [99] J. H. Winters, BOn the capacity of radio communication systems with diversity in Rayleigh fading environment,[ IEEE J. Sel. Areas Commun., vol. SAC-5, pp. 871–878, Jun. 1987. [100] A. Nosratinia, T. Hunter, and A. Hedayat, BCooperative communication in wireless networks,[ IEEE Commun. Mag., vol. 42, pp. 74–80, Oct. 2004. [101] A. Bletsas, H. Shin, and M. Z. Win, BCooperative communications with outage-optimal opportunistic relaying,[ IEEE Trans. Wireless Commun., vol. 6, pp. 3450–3460, Sep. 2007. [102] F. J. Gonzalez-Castano and J. Garcia-Reinoso, BBluetooth location networks,[ in Proc. IEEE Global Telecomm. Conf., Taipei, Taiwan, R.O.C., Nov. 2002, pp. 233–237. [103] W. Chen and X. Meng, BA cooperative localization scheme for Zigbee-based 448 Proceedings of the IEEE | Vol. 97, No. 2, February 2009 Wymeersch et al.: Cooperative Localization in Wireless Networks wireless sensor networks,[ in Proc. IEEE Int. Conf. Netw., Sep. 2006, vol. 2. [104] R. Pabst, B. H. Walke, D. C. Schultz, P. Herhold, H. Yanikomeroglu, S. Mukherjee, H. Viswanathan, M. Lott, W. Zirwas, M. Dohler, H. Aghvami, D. D. Falconer, and G. P. Fettweis, BRelay-based deployment concepts for wireless and mobile broadband radio,[ IEEE Commun. Mag., vol. 42, pp. 80–89, Jan. 2004. [105] C. Savarese, J. M. Rabaey, and K. Langendoen, BRobust positioning algorithms for distributed ad-hoc wireless sensor networks,[ in Proc. General Track: 2002 USENIX Annu. Tech. Conf., Berkeley, CA, Jun. 2002, pp. 317–327. [106] J. Costa, N. Patwari, and A. O. Hero, III, BDistributed multidimensional scaling with adaptive weighting for node localization in sensor networks,[ ACM Trans. Sensor Netw., vol. 2, no. 1, pp. 39–64, Feb. 2006. [107] D. Fox, W. Burgard, H. Kruppa, and S. Thrun, BA Monte Carlo algorithm for multi-robot localization,[ Computer Science Dept., Carnegie Mellon Univ., Pittsburgh, PA, Tech. Rep. CMU-CS-99-120, 1999. [108] C. Chang, W. Snyder, and C. Wang, BRobust localization of multiple events in sensor networks,[ in Proc. IEEE Int. Conf. Sensor Netw., Ubiquitous, Trustworthy Comput. (SUTC), Jun. 2006, vol. 1, pp. 168–177. [109] R. Peng and M. Sichitiu, BProbabilistic localization for outdoor wireless sensor networks,[ ACM SIGMOBILE Mobile Comput. Commun. Rev., vol. 11, no. 1, pp. 53–64, Jan. 2007. [110] C. Gentile and A. Kik, BA comprehensive evaluation of indoor ranging using ultra-wideband technology,[ EURASIP J. Wireless Commun. Netw., vol. 2007, no. 1, pp. 12–12, Jan. 2007. [111] B. Denis, J. Keignart, and N. Daniele, BImpact of NLOS propagation upon ranging precision in UWB systems,[ in Proc. IEEE Conf. Ultra Wideband Syst. Technol. (UWBST), Nov. 2003, pp. 379–383. [112] Z. N. Low, J. H. Cheong, C. L. Law, W. T. Ng, and Y. J. Lee, BPulse detection algorithm for line-of-sight (LOS) UWB ranging applications,[ IEEE Antennas Wireless Propag. Lett., vol. 4, pp. 63–67, 2005. [113] D. Cassioli, M. Z. Win, and A. F. Molisch, BThe ultra-wide bandwidth indoor channel: From statistical model to simulations,[ IEEE J. Sel. Areas Commun., vol. 20, pp. 1247–1257, Aug. 2002. [114] FCC, ‘‘Revision of Part 15 of the commission’s rules regarding ultra-wideband transmission systems, first report and order,’’ ET Docket 98-153, Feb. 14, 2002. [115] T. K. Moon, BThe expectation-maximization algorithm,[ IEEE Signal Process. Mag., vol. 13, pp. 47–60, Nov. 1996. [116] J. Bilmes, BA gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models,[ Int. Computer Science Inst., Tech. Rep. 97-021, 1998. [117] B. Alavi and K. Pahlavan, BModeling of the TOA-based distance measurement error using UWB indoor radio measurements,[ IEEE Commun. Lett., vol. 10, pp. 275–277, Apr. 2006. [118] J. Borras, P. Hatrack, and N. B. Mandayam, BDecision theoretic framework for NLOS identification,[ in Proc. IEEE Semiannu. Veh. Technol. Conf., Ottawa, ON, Canada, May 1998, vol. 2, pp. 1583–1587. [119] B. Denis and N. Daniele, BNLOS ranging error mitigation in a distributed positioning algorithm for indoor UWB ad-hoc networks,[ in Proc. Int. Workshop Wireless Ad-Hoc Netw., May/Jun. 2004, pp. 356–360. [120] S. Gezici, H. Kobayashi, and H. V. Poor, BNon-parametric non-line-of-sight identification,[ in Proc. IEEE Semiannu. Veh. Technol. Conf., Orlando, FL, Oct. 2003, vol. 4, pp. 2544–2548. [121] S. Venkatraman and J. Caffery, Jr., BStatistical approach to non-line-of-sight BS identification,[ in Proc. 5th Int. Symp. Wireless Personal Multimedia Commun., Honolulu, HI, Oct. 2002, vol. 1, pp. 296–300. [122] T. Schouwenaars, A. Stubbs, J. Paduano, and E. Feron, BMulti-vehicle path planning for non-line of sight communication,[ J. Field Robot., vol. 23, no. 3–4, p. 269, Apr. 2006. [123] Univ. of Queensland and Z. Botev. (2007, Nov.). Nonparametric density estimation via diffusion mixing. [Online]. Available: http://www. espace.library.uq.edu.au/view/UQ:120006 [124] L. Ljung, BAsymptotic behavior of the extended Kalman filter as a parameter estimator for linear systems,[ IEEE Trans. Autom. Control, vol. AC-24, pp. 36–50, Feb. 1979. [125] S. Thrun, Y. Liu, D. Koller, A. Ng, Z. Ghahramani, and H. Durrant-Whyte, BSimultaneous localization and mapping with sparse extended information filters,[ Int. J. Robot. Res., vol. 23, no. 7–8, pp. 693–716, Jul.–Aug. 2004. [126] A. Doucet, S. Godsill, and C. Andrieu, BOn sequential Monte Carlo sampling methods for Bayesian filtering,[ Statist. Comput., vol. 10, no. 3, pp. 197–208, Jul. 2000. [127] B. Anderson, P. Belhumeur, T. Eren, D. Goldenberg, A. Morse, W. Whiteley, and Y. Yang, BGraphical properties of easily localizable sensor networks,[ Wireless Netw., pp. 1–15, Apr. 2007. [128] W. Liao, J. Sheu, and Y. Tseng, BGRID: A fully location-aware routing protocol for mobile ad hoc networks,[ Telecommun. Syst., vol. 18, no. 1, pp. 37–60, Sep. 2001. [129] D. Huang, M. Mehta, D. Medhi, and L. Harn, BLocation-aware key management scheme for wireless sensor networks,[ in Proc. 2nd ACM Workshop Security of Ad Hoc Sensor Netw., New York, Oct. 2004, pp. 29–42, ACM. [130] N. Marmasse and C. Schmandt, BLocation-aware information delivery with ComMotion,[ in Proc. 2nd Int. Symp. Handheld Ubiquitous Comput., Sep. 2000, pp. 157–171. [131] A. Ward, A. Jones, and A. Hopper, BA new location technique for the active office,[ IEEE Personal Commun. Mag., vol. 4, pp. 42–47, Oct. 1997. ABOUT THE AUTHORS Henk Wymeersch (Member, IEEE) received the Ph.D. degree in electrical engineering from Ghent University, Belgium, in 2005. He is a Postdoctoral Associate with the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology (MIT), Cambridge. In 2005–2006, he was a Postdoctoral Fellow with the Belgian American Educational Foundation, MIT. He is author of Iterative Receiver Design (Cambridge, U.K.: Cambridge University Press, 2007). His research interests include algorithm design for wireless transmission, statistical inference, and iterative processing. Dr. Wymeersch is an Associate Editor of IEEE COMMUNICATION LETTERS. In 2006, he received the Alcatel Bell Scientific Award for his Ph.D. dissertation. Jaime Lien (Member, IEEE) received the bachelor’s and master’s degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 2005 and 2007, respectively. Since 2007, she has been with the Jet Propulsion Laboratory, Pasadena, CA, as a Member of the Telecommunications Architectures group. Her research interests include wireless communications, localization, and cooperative networks. Ms. Lien received the 2007 David Adler Memorial Thesis Award for her research on localization in ultrawide bandwidth radio networks, conducted at the MIT Laboratory for Information and Decision Systems. Vol. 97, No. 2, February 2009 | Proceedings of the IEEE 449 Wymeersch et al.: Cooperative Localization in Wireless Networks Moe Z. Win (Fellow, IEEE) received both the Ph.D. in Electrical Engineering and M.S. in Applied Mathematics as a Presidential Fellow at the University of Southern California (USC) in 1998. He received an M.S. in Electrical Engineering from USC in 1989, and a B.S. (magna cum laude) in Electrical Engineering from Texas A&M University in 1987. Dr. Win is an Associate Professor at the Massachusetts Institute of Technology (MIT). Prior to joining MIT, he was at AT&T Research Laboratories for five years and at the Jet Propulsion Laboratory for seven years. His research encompasses developing fundamental theory, designing algorithms, and conducting experimentation for a broad range of realworld problems. His current research topics include location-aware networks, time-varying channels, multiple antenna systems, ultra-wide bandwidth systems, optical transmission systems, and space communications systems. Professor Win is an IEEE Distinguished Lecturer and an elected Fellow of the IEEE, cited for Bcontributions to wideband wireless transmission.[ He was honored with the IEEE Eric E. Sumner Award (2006), an IEEE Technical Field Award for Bpioneering contributions to ultra-wide band communications science and technology.[ Together with students and colleagues, his papers have received several awards including the IEEE Communications Society_s Guglielmo Marconi Best Paper Award (2008) and the IEEE Antennas and Propagation Society_s Sergei A. Schelkunoff Transactions Prize Paper Award (2003). His other recognitions include the Laurea Honoris Causa from the University of Ferrara, Italy (2008), the Technical Recognition Award of the IEEE ComSoc Radio Communications Committee (2008), Wireless Educator of the Year Award (2007), the Fulbright Foundation Senior Scholar Lecturing and Research Fellowship (2004), the U.S. Presidential Early Career Award for Scientists and Engineers (2004), the AIAA Young Aerospace Engineer of the Year (2004), and the Office of Naval Research Young Investigator Award (2003). Professor Win has been actively involved in organizing and chairing a number of international conferences. He served as the Technical Program Chair for the IEEE Wireless Communications and Networking Conference in 2009, the IEEE Conference on Ultra Wideband in 2006, the IEEE Communication Theory Symposia of ICC-2004 and Globecom2000, and the IEEE Conference on Ultra Wideband Systems and Technologies in 2002; Technical Program Vice-Chair for the IEEE International Conference on Communications in 2002; and the Tutorial Chair for ICC-2009 and the IEEE Semiannual International Vehicular Technology Conference in Fall 2001. He was the chair (2004–2006) and secretary (2002–2004) for the Radio Communications Committee of the IEEE Communications Society. Dr. Win is currently an Editor for IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS. He served as Area Editor for Modulation and Signal Design (2003–2006), Editor for Wideband Wireless and Diversity (2003–2006), and Editor for Equalization and Diversity (1998–2003), all for the IEEE TRANSACTIONS ON COMMUNICATIONS. He was Guest-Editor for the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS (Special Issue on Ultra-Wideband Radio in Multiaccess Wireless Communications) in 2002. 450 Proceedings of the IEEE | Vol. 97, No. 2, February 2009

## 评论