On frame and orientation localization for relative sensing networks

doi:10.1016/j.automatica.2012.09.014

Automatica

Volume 49, Issue 1, January 2013, Pages 206-213

https://doi.org/10.1016/j.automatica.2012.09.014 Get rights and content

Abstract

We develop a novel localization theory for networks of nodes that measure each other’s bearing, i.e., we assume that nodes do not have the ability to perform measurements expressed in a common reference frame. We begin with some basic definitions of frame localizability and orientation localizability. Based on some key kinematic relationships, we characterize orientation localizability for planar networks with angle-of-arrival sensing. We then address the orientation localization problem in the presence of noisy measurements. Our first algorithm computes a least-squares estimate of the unknown node orientations in a ring network given angle-of-arrival sensing. For arbitrary connected graphs, our second algorithm exploits kinematic relationships among the orientations of nodes in loops in order to reduce the effect of noise. We establish the convergence of the algorithm, and through some simulations we show that the algorithm reduces the mean-square error due to the noisy measurements in a way that is comparable to the amount of noise reduction obtained by the classic least-square estimator. We then consider networks in 3-dimensional space and we explore necessary and sufficient conditions for orientation localizability in the noiseless case.

Introduction

One of the key problems in sensor networks is localization, i.e., determining the location of each sensor in the network. Sensor networks are used in a large number of applications which cover a wide range of fields, such as, surveillance, controls, communications, monitoring areas, intrusion detection, vehicle tracking, mapping and reconstruction of environments (camera sensor networks). In particular, angle-of-arrival sensors are used for operations such as maintaining formations of robotic agents, or geographically locating cell phones and other wireless devices based on the information from multiple antennas.

We address the aforementioned problem in a distributed manner, by assuming that any node in the network has its own reference frame, and does not have any knowledge about its physical position in the environment or the position of the other nodes. Each node, through a sensor, can detect the relative position of any other node inside a given sensor footprint. The measurements are affected by noise, so we extend our analysis to the noisy case. We call frame localization the problem of computing the relative location and orientation of each node of the network with respect to each other. In the 2-d case, we aim to solve the problem through a distributed algorithm, which computes the estimate of the angle associated to every edge of the graph by distributing the error of every cycle on its edges.

Network localization has been the center of extensive research work, and the various approaches are due to different assumptions on the deployment of the nodes, the dimension of the space, and the type of sensors employed. In some cases, there is the use of special nodes, whose positions are known, called beacons or anchors (e.g., see Aspnes et al., 2006, Khan et al., 2009, Moore et al., 2004) (Aspnes et al., 2006) present a theoretical foundation of the network localization problem; the authors provide conditions for uniqueness in localization of networks with beacons and distance measurements, and study the computational complexity in uniquely localizable networks and in typical network deployment scenarios. Together with the aforementioned, other works that exploit distance information or relative positions between node in studying networks and robot formations are available in the literature; e.g., see (Trawny et al., 2010, Zhou and Roumeliotis, 2007). In the present work, we focus on angle-of-arrival measurements. Therefore, particular interest arises from the work by Rong and Sichitiu (2006), who propose a localization and orientation approach based on angle-of-arrival information between neighboring nodes. However, again, prior knowledge of the orientation of a few nodes is required. The authors of Eren, Whiteley, and Belhumeur (2006) study the uniqueness of network localization solutions through the theory of rigid graphs, but they do not provide an algorithm to compute such a solution, even for the noiseless case. Huang and Jiang (2008) provide two methods for network localization using angle-of-arrival measurements. However, the problem statement differs from ours in that it utilizes the relationship between triplets of nodes, whereas we admit a relationship between a greater number of nodes. Our work is more closely related to the work of Tron and Vidal (2009), where a distributed algorithm for 3-d sensor network orientation and translation localization is proposed.

This paper contains several contributions. First, we present a novel formulation of the frame localizability and frame computational localization problem for networks in 2-d or 3-d ambient space with relative sensing. Second, we define a characterization of frame localizability for planar networks, focusing on consistency for the orientation localization problem. Third, we consider arbitrary connected graphs and provide a distributed algorithm for planar orientation localization which exploits kinematic relationships among the orientation of nodes in loops in order to reduce the effect of noise. Fourth, we provide simulations in order to validate our algorithm results. Finally, we consider networks in three-dimensional space and we explore necessary or sufficient conditions for orientation localizability in the noiseless case.

The paper is organized as follows. Section 2 reviews some basic notions from kinematics and graph theory. Section 3 contains the model and the problem statement. Section 4 contains the localizability results and the localization algorithm. Section 5 explores the orientation localizability problem in three-dimensional space.

Section snippets

Elements of kinematics

Let $R$ and $C$ denote real and complex numbers, respectively. Let $‖ v ‖$ denote the Euclidean norm of the vector $v \in R^{d}$ . Define the versor operator $vers : R^{d} \to R^{d}$ by vers $(0) = 0$ and $vers (v) = v / ‖ v ‖$ for $v \neq 0$ . Define the map $proj : R \to [- π, π [$ by $proj (x) = (x + π) mod 2 π - π,$ and similarly $proj : R^{n} \to [- π, π [^{n}$ by $proj ({[x_{1}, \dots, x_{n}]}^{T}) = {[proj (x_{1}), \dots, proj (x_{n})]}^{T}$ . Let $∠ z$ denote the phase of $z \in C$ . We are interested in measurements expressed in different reference frames. Accordingly, we review some basic kinematic conventions. We let $Σ_{1} = {p_{1}, x_{1},$

Network model and localization problems

In what follows we describe our notion of a network equipped with relative sensors. We consider a group of $n$ distinct nodes ${p_{1}, \dots, p_{n}}$ in $R^{d}$ , for $d \in {2, 3}$ , and corresponding reference frames ${Σ_{1}, \dots, Σ_{n}}$ with the property that $p_{i}$ is the origin of $Σ_{i}$ for all $i \in {1, \dots, n}$ .

Orientation localizability with angle-of-arrival sensors

Theorem 9 Orientation Localizability

For a planar relative sensing network with noiseless angle-of-arrival sensing, the following statements are equivalent:

(i)
the sensing graph is connected, and
(ii)
the network is orientation localizable.

Proof

For every undirected edge $(i, j)$ of the sensing graph, the angles $∠ p_{j}^{i}$ and $∠ p_{i}^{j}$ are measured. Therefore, (8) implies that the relative angle $θ_{j}^{i}$ is uniquely determined from the measurements. Now, let us prove (i) $⟹$ (ii). If the network is connected, there exists a path from a reference node, e.g., node 1,

Three-dimensional frame localization

Here, we consider first a network composed by three nodes in 3-dimensional space with a complete sensing graph. The setup is illustrated in the left image in Fig. 3.

Lemma 13 Feasible Orientations

Given unit-length measurements $u_{j}^{i} = vers (p_{j}^{i})$ and $u_{i}^{j} = vers (p_{i}^{j})$ , compute $H_{j}^{i} \in S O (3)$ by $H_{j}^{i} = exp (α_{j}^{i} \hat{e_{j}^{i}})$ , where $e_{j}^{i} \in R^{3}, α_{j}^{i} \in [0, π]$ are defined²by $e_{j}^{i} = {\begin{cases} vers (u_{j}^{i} \times u_{i}^{j}), & if u_{j}^{i} \times u_{i} \end{cases}$

Conclusions

This paper has introduced the frame localization problem in a connected network. For the planar orientation localization problem with angle-of-arrival (bearing) sensors, we developed an exponentially fast algorithm that reduces the effect of noise. For the three-dimensional case, we have explored necessary and sufficient conditions for a noiseless network to be orientation localizable.

Giulia Piovan is currently working toward the Ph.D. degree in Mechanical Engineering at the University of California, Santa Barbara. She received her Laurea Triennale and Specialistica degrees in Automation Engineering from the University of Padova, Italy, and the M.S. degree in Mechanical Engineering from the University of California, Santa Barbara. Her research interests focus on the analysis and control of dynamical locomotion with underactuated legged robots, and she has worked on

References (18)

M. Arioli et al.
Dual variable methods for mixed-hybrid finite element approximation of the potential fluid flow problem in porous media
Electronic Transactions on Numerical Analysis
(2006)
J. Aspnes et al.
A theory of network localization
IEEE Transactions on Mobile Computing
(2006)
R. Diestel
Eren, T., Whiteley, W., & Belhumeur, P.N. (2006). Using angle of arrival (bearing) information in network localization....
L.R. Foulds
Graph theory applications
S. Kaczmarz
Approximate solution of systems of linear equations
International Journal of Control
(1993)
U.A. Khan et al.
Distributed sensor localization in random environments using minimal number of anchor nodes
IEEE Transactions on Signal Processing
(2009)
Moore, D., Leonard, J., Rus, D., & Teller, S. (2004). Robust distributed network localization with noisy range...
R.M. Murray et al.
A mathematical introduction to robotic manipulation
(1994)

There are more references available in the full text version of this article.

Cited by (62)

Bearing-only distributed localization for multi-agent systems with complex coordinates
2023, Information Sciences
This paper addresses the bearing-only distributed localization, which is more accurate and more reliable than traditional localization technologies. A new bearing-only distributed localization framework is proposed to solve localization problems for both static sensor networks and mobile multi-agent systems (MASs). Based on the complex coordinate representation, a novel bearing-only distributed localization algorithm for sensor networks is proposed. The algorithm combines the orientation estimation and the position estimation to solve the orientation alignment problem, which makes the compasses no longer needed for the localized networks. The localization for the mobile MASs is also studied and the corresponding localization algorithm is designed, which is more general and more challenging. The key to obtaining positions of moving agents, is the velocity estimator in the proposed localization algorithm which makes the estimated positions and velocities converge to the true value simultaneously. A distinctive advantage of the localization framework proposed in this paper is that the bearing-only localization algorithms can be applied to more general systems, such as sensor networks and MASs. Simulations and experiment are presented to verify the proposed algorithms.
Pose localization of leader–follower networks with direction measurements
2020, Automatica
A distributed pose localization framework based on direction measurements is proposed for a type of leader–follower multi-agent system in $R^{3}$ . The novelty of the proposed localization method lies in the elimination of the need for using distance measurements and relative orientation measurements for the network pose localization problem. In particular, a network localization scheme is developed based directly on the measured directions between an agent and its neighboring agents in the network. The proposed position and orientation localization algorithms are implemented through differential equations which simultaneously compute poses of all followers by using locally measured directional vectors and angular velocities, and actual pose knowledge of some leader agents, allowing some tracking of time-varying orientations. Further, we establish almost global asymptotic convergence of the estimated positions and orientations of the agents to the actual poses in the stationary case.
Distributed bearing vector estimation in multi-agent networks
2020, Automatica
Citation Excerpt :
In network localization, estimation of the orientations of agents can be also considered. The work in Piovan, Shames, Fidan, Bullo, and Anderson (2013) addressed an orientation localization problem, to compute the orientation of each node based on the relative bearing measurements. This paper defines and analyzes a new localization problem, the problem of estimating the bearing vectors between the agents in a two dimensional multi-agent network with only the subtended angle measurements.
This paper focuses on the problem of estimating bearing vectors between the agents in a two dimensional multi-agent network based on subtended angle measurements. We propose an edge localization graph to investigate the solvability of this problem and a distributed estimation method via orientation estimation of virtual agents to solve the problem. Under the proposed method, the estimated bearing vector exponentially converges to the real one with a common bias if and only if the edge localization graph has an oriented spanning tree. Furthermore, the estimated variables exponentially converge to the true values if the edge localization graph has an oriented spanning tree with a root knowing the bearing vector from it to one of its neighbors.
Multiple-source ellipsoidal localization using acoustic energy measurements
2020, Automatica
Citation Excerpt :
In this paper, we focus on the multiple-source localization problem where the aim is to estimate the coordinates of multiple acoustic sources. The problem of source localization has been addressed by many authors (see papers Bishop et al., 2010; Chen et al., 2016; Han et al., 2017; Masazade et al., 2010; Niu et al., 2012; Niu, Vempaty, & Varshney, 2018; Piovana, Shames, Fidanc, Bulloa, & Andersond, 2013; Shames, Fidan, & Anderson, 2009; Vempaty, Han, & Varshney, 2014; Vempaty, Ozdemir, Agrawal, Chen, & Varshney, 2013; Win, Dai, Shen, Chrisikos, & Vincent Poor, 2018; Wymeersch, Lien, & Win, 2009 and books Mao & Fidan, 2009; Strumiłło, 2011; Zekavat & Buehrer, 2011). Most localization methods are based on one of the following three types of physical variables measured by sensor readings for localization: direction of arrival (DOA), time difference of arrival (TDOA) and received sensor signal strength (RSS).
In this paper, the multiple-source ellipsoidal localization problem based on acoustic energy measurements is investigated via set-membership estimation theory. When the probability density function of measurement noise is unknown-but-bounded, multiple-source localization is a difficult problem since not only the acoustic energy measurements are complicated nonlinear functions of multiple sources, but also the multiple sources bring about a high-dimensional state estimation problem. First, when the energy parameter and the position of the source are bounded in an interval and a ball respectively, the nonlinear remainder bound of the Taylor series expansion is obtained analytically on-line. Next, based on the separability of the nonlinear measurement function, an efficient estimation procedure is developed. It solves the multiple-source localization problem by using an alternating optimization iterative algorithm, in which the remainder bound needs to be known on-line. For this reason, we first derive the remainder bound analytically. When the energy decay factor is unknown but bounded, an efficient estimation procedure is developed based on interval mathematics. Finally, numerical examples demonstrate the effectiveness of the ellipsoidal localization algorithms for multiple-source localization. In particular, our results show that when the noise is non-Gaussian, the set-membership localization algorithm performs better than the EM localization algorithm.
Collision avoidance cooperative attack with multiple pursuers based on bearing-only measurements
2020, Journal of the Franklin Institute
Citation Excerpt :
The control algorithm based on bearing-only measurements is quite practical, because most of the missiles and vehicles are vision-based systems and the bearing measurement is more cost effective compared with the relative position information measurement when considering the cost of the measuring equipment [26,27]. In [28–30], the bearing measurements are proposed for the location of a 2-D network, and Zhao and Zelazo [31] extends this problem to d-dimensional spaces. In [32], the author considers the measurements problem with a switching topology, so that the communication topologies in the localization process can switch over time.
This paper provides a novel collisions avoidance cooperative attack method for multiple pursuers system based on bearing-only measurements. In the cooperative attack problem, the control algorithm must drive all of the attackers to converge to the desired position (target). However, the traditional consensus protocol based on the relative position information may cause the intervehicle collisions before the attackers can hit the target. To solve this issue, a distributed cooperative consensus control algorithm is proposed. Under this algorithm the potential collisions are proved to be avoided while the pursuers can achieve the final attack. Further more, considering the relative distance information is unavailable for some types of the pursuers to get, a control algorithm based on bearing-only measurements is proposed by referencing the distributed localization algorithm used in the sensors network. The advantages of this method are summed up as fully distributed, collisions avoidance, and bearing-only measurements. Finally, the effectiveness of the results is illustrated by numerical simulation.
3-D Distributed Localization with Mixed Local Relative Measurements
2023, arXiv

View all citing articles on Scopus

Iman Shames is currently a Postdoctoral Researcher at the ACCESS Linnaeus Centre, the KTH Royal Institute of Technology, Stockholm, Sweden. He received his B.S. degree in Electrical Engineering from Shiraz University, Iran in 2006, and the Ph.D. degree in Engineering and Computer Science from the Australian National University, Canberra, Australia. He has been a Visiting Researcher at the KTH Royal Institute of Technology in 2010, the University of Tokyo in 2008, and at the University of Newcastle in 2005. His current research interests include multi-agent systems, sensor networks, systems biology, and distributed fault detection and isolation.

Barış Fidan received the B.S. degrees in Electrical Engineering and Mathematics from the Middle East Technical University, Turkey in 1996, the M.S. degree in Electrical Engineering from Bilkent University, Turkey in 1998, and the Ph.D. degree in Electrical Engineering at the University of Southern California, USA in 2003. He worked at the University of Southern California in 2004 as a Postdoctoral Research Fellow, and at the National ICT Australia and the Research School of Information Sciences and Engineering of the Australian National University in 2005–2009 as a Researcher/Senior Researcher. He is currently an Assistant Professor at the Mechanical and Mechatronics Engineering Department, University of Waterloo, Canada. His research interests include autonomous multi-agent dynamical systems, cooperative driving, cooperative target localization, sensor networks, adaptive and nonlinear control, switching and hybrid systems, mechatronics, and various control applications including vehicle and transportation control, high performance and hypersonic flight control, semiconductor manufacturing process control, and disk-drive servo systems.

Francesco Bullo is currently a Professor with the Mechanical Engineering Department and the Center for Control, Dynamical Systems and Computation at the University of California, Santa Barbara. He was previously associated with the University of Padova, the California Institute of Technology and the University of Illinois at Urbana-Champaign. His main research interest is multi-agent networks with application to robotic coordination, distributed computing and power networks; he has worked on vehicle routing, geometric control, and motion planning. He is the coauthor of “Geometric Control of Mechanical Systems” (Springer, 2004, 0-387-22195-6) and “Distributed Control of Robotic Networks” (Princeton, 2009, 978-0-691-14195-4).

Brian D.O. Anderson was born in Sydney, Australia, and educated at Sydney University in Mathematics and Electrical Engineering, with a Ph.D. in Electrical Engineering from Stanford University in 1966. He is a Distinguished Professor at the Australian National University and a Distinguished Researcher in National ICT Australia (NICTA). His awards include the IFAC Quazza Medal in 1999, the IEEE Control Systems Award of 1997, the 2001 IEEE James H Mulligan, Jr. Education Medal, and the Bode Prize of the IEEE Control System Society in 1992, and a number of other medals and best paper prizes. He is a Fellow of the Australian Academy of Science, the Australian Academy of Technological Sciences and Engineering, the Royal Society, an Honorary Fellow of the Institution of Engineers, Australia, and a Foreign Associate of the US National Academy of Engineering. He holds honorary doctorates from a number of universities, including Université Catholique de Louvain, Belgium, and ETH, Zürich. He is a past president of the International Federation of Automatic Control and the Australian Academy of Science. He served as the first President of NICTA, and was a member of company boards, including Cochlear ltd., the world’s major supplier of bionic ears, and a member of the Prime Minister’s Science Council under three Prime Ministers. His current research interests are in distributed control, sensor networks and econometric modeling.

^☆: This material was supported in part by NSF Awards CNS-0834446 and IIS-0904501. The material in this paper was presented at the 47th IEEE Conference on Decision and Control (CDC 2008), December 9–11 2008, Cancún, Mexico. This paper was recommended for publication in revised form by Associate Editor Yoshito Ohta under the direction of Editor Roberto Tempo. National ICT Australia (NICTA) is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program. Iman Shames was supported by the Swedish Research Council and Knut and Alice Wallenberg Foundation.

^☆☆: A preliminary version of this work appeared as (Piovan, Shames, Fidan, Bullo, & Anderson, 2008); differences with this article include complete proofs of all statements, improved discussions about motivation and performance, and the treatment of 3-dimensional problems.

¹: Tel.: +1 805 280 8904; fax: +1 805 893 8651.

View full text

Brief paperOn frame and orientation localization for relative sensing networks☆,☆☆

Abstract

Introduction

Section snippets

Elements of kinematics

Network model and localization problems

Orientation localizability with angle-of-arrival sensors

Three-dimensional frame localization

Conclusions

Dual variable methods for mixed-hybrid finite element approximation of the potential fluid flow problem in porous media

Electronic Transactions on Numerical Analysis

A theory of network localization

IEEE Transactions on Mobile Computing

Graph theory applications

Approximate solution of systems of linear equations

International Journal of Control

Distributed sensor localization in random environments using minimal number of anchor nodes

IEEE Transactions on Signal Processing

A mathematical introduction to robotic manipulation

Brief paper
On frame and orientation localization for relative sensing networks☆,☆☆