Sensor Management with Applications in Localization and Tracking by Farhad Ghassemi M.A.Sc., The University of British Columbia, 2001 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Doctor of Philosophy in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University of British Columbia (Vancouver) June 2009 c Farhad Ghassemi 2009 Abstract In this dissertation, we explore several themes in sensor management with an emphasis on their applications for target localization and tracking. We consider the sensor subset selection problem where a pre-specified number of sensors must be selected in a sensor network to estimate an unknown value of a time-invariant parameter, e.g. the position of a target. We study the Lagrangian and continuous relaxations of this problem with the determinant of the Fisher information matrix as the objective function. We prove that the continuous bound is tighter than the Lagrangian bound and outline an algorithm based on the so-called natural selection process to compute the continuous bound when sensors are allowed to make more than one measurement. We also study how a target can identify the informative sensors when it is facing a network that attempts to estimate its position or its other critical parameters. We show that by borrowing the notion of symmetric probabilistic values from cooperative game theory, the target can assign a power index to each sensor to determine how informative it is relative to the other ones. We further show that by choosing the determinant of the Fisher information matrix as the metric of estimation accuracy, the computational complexity associated with a power index gracefully increases with ii Abstract the number of sensors. Finally, we study the trajectory design problem for bearings-only tracking where the motion of a mobile sensor, called the observer, must be planned in order to estimate the position and the velocity of a moving target via bearing measurements. Our analysis of this problem demonstrates that the optimal solutions can be uniquely specified by only two ratios: (i) The distance that the observer can travel along a straight line during the observation period to the relative distance between the observer and the target. (ii) The speed of the observer relative to the speed of the target. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Overview of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Main Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Management of Fixed Sensors . . . . . . . . . . . . . . . . . . . . . . 21 2 Upper Bounds for the Sensor Subset Selection Problem . . . . . . 22 I iv Table of Contents 2.1 Overview 2.2 Formulation of the Sensor Subset Selection Problem 2.2.1 2.3 . . . . . . . . . Structural Properties of the FIM and its Determinant Outer Approximation Algorithm 22 25 . . . . 28 . . . . . . . . . . . . . 34 . . . . . . . . . . . . . . . . 36 Characteristics of the Lagrangian Relaxation 2.3.1 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4.1 Natural Selection Process . . . . . . . . . . . . . . . . . . . . 42 2.4.2 Analysis of the Performance of a Greedy Algorithm . . . . . . 52 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3 Power Index of a Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.5 3.1 Overview 3.2 Cooperative Parameter Estimation Game 3.3 Computation of Power Indices 3.4 3.5 II Characteristics of the Continuous Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 . . . . . . . . . . . . . . . 58 . . . . . . . . . . . . . . . . . . . . . 61 Power Indices for Localization and Tracking . . . . . . . . . . . . . . 68 3.4.1 Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.4.2 Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Management of Mobile Sensors . . . . . . . . . . . . . . . . . . . . 78 4 Parameterization of Optimal Observer Trajectories . . . . . . . . . 79 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 79 Table of Contents 4.2 Formulation of the Trajectory Design Problem 4.3 Invariant Transformation of the Trajectory Design Problem . . . . . 87 4.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5 Conclusion . . . . . . . . . . . . 81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.1 Summary of Work Accomplished . . . . . . . . . . . . . . . . . . . . 97 5.2 Directions for Future Work 99 . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 vi List of Tables 2.1 Characteristics of the sensor subset selection problem . . . . . . . . . 55 3.1 Power index of sensors in Figure 3.2 for bearings-only localization . . 74 3.2 Power index of sensors in Figure 3.3 for bearings-only localization . . 74 3.3 Power index of sensors in Figure 3.2 for range-only localization . . . . 75 3.4 Power index of sensors in Figure 3.2 for bearings-only tracking . . . . 77 vii List of Figures 1.1 Sensor management for localization . . . . . . . . . . . . . . . . . . . 5 1.2 Main themes of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Examples of observable and unobservable scenarios . . . . . . . . . . 17 2.1 Geometry of bearings-only localization in three-dimensional space . . 50 2.2 A histogram for the convergence of the natural selection process . . . 52 3.1 Analyzing relative power of sensors for bearings-only localization . . . 58 3.2 A network configuration to study power indices for localization . . . . 72 3.3 A network configuration to demonstrate that the closest sensor is not the most informative one . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.4 A network configuration to study power indices for tracking . . . . . 76 4.1 Geometry of bearings-only tracking by an observer . . . . . . . . . . 86 4.2 Bounded region for the trajectory design problem . . . . . . . . . . . 89 4.3 Observer trajectories for tracking a stationary target is (CV = ∞). . . 93 4.4 Observer trajectories for localization. . . . . . . . . . . . . . . . . . . 94 viii List of Figures 4.5 Observer trajectories for tracking when the target and the observer are traveling at the same speed. . . . . . . . . . . . . . . . . . . . . . . . ix 95 Acknowledgements I am thankful to my supervisor, Dr. Vikram Krishnamurthy, for his guidance and support in this research. His enthusiasm for tackling new problems and exploring new ideas was always contagious and a source of motivation. I appreciate the benefits of useful discussions with colleagues in the statistical signal processing lab. Many illusive concepts were clarified for me after these discussions. Finally, I would like to express my gratitude to my dear parents, my sisters and many good friends who encouraged and supported me through this time. I am grateful for a fellowship from the R. Howard Webster Foundation as well as a scholarship from the National Science and Engineering Research Council of Canada that allowed me to complete this program. x Chapter 1 Introduction 1.1 Overview of Thesis Sensors are widely used in our lives. They provide quantifiable information in the form of measurements about events and real-world conditions which may be otherwise indiscernible to us. Unfortunately, however, the measurements from sensors can be inaccurate and indirect representatives of the quantity that is of interest to us. A primary task is then to infer the value of the quantity of interest after making measurements. This is known as estimation [1–4], a well-developed subject which we do not delve into here. Instead, we concern ourselves with a process before making measurements where we question how sensors can be most efficiently utilized to obtain the most accurate estimates. We refer to this decision-making process as sensor management and develop a number of optimization problems for this purpose. These optimization problems have an objective function that reflects the accuracy of estimation results and some constraints that define feasible actions of sensors. Our knowledge about the quantity that must be estimated is captured by a probability density. This probability density 1 Chapter 1. Introduction is also known as the belief state. As new measurements become available, this probability density is updated by an estimator. The estimation accuracy is related to the dispersion of this probability density. If the probability density is highly concentrated around a certain value, we can say that the quantity has been estimated with high accuracy. Formulating an optimization problem for sensor management is, therefore, established by predicting how this probability density evolves if a certain sequence of actions is given to the sensors. This problem is solved by finding an optimal feasible sequence of actions. There are several statistical and information-theoretic functions that assign a real number to a probability density reflecting its dispersion (see [5] where some of these functions are described). We call such functions the metrics of estimation accuracy. The statistical metrics of estimation accuracy are mainly based on the covariance matrix whereas the information-theoretic metrics are based on the entropy. We work with the statistical metrics of estimation accuracy as one then only needs to study the evolution of the second moment of the probability density into the future. Ideally, the metrics of estimation accuracy must be defined based on the covariance matrix of the specific estimator used for estimation. However, if we assume that the estimator is efficient [3], the metrics of estimation accuracy can be defined for a class of estimators, rather than a specific estimator. Efficiency is a desirable property for an estimator and one can expect that many estimators, at least, asymptotically satisfy this property [2,3]. Essentially, an efficient estimator is characterized by its covariance 2 Chapter 1. Introduction matrix when it attains the so-called Cramer-Rao lower bound (CRLB) [1]. The inverse of the CRLB is known as the Fisher Information Matrix (FIM). One other advntage of assuming an efficient estimator is that there are formulas for updating the FIM recursively from one time instant to another [6]. We use these formulas to predict how the FIM evolves for a given sequence of actions and their corresponding measurements. The FIM can also be computed directly for a batch of measurements [1] (see (2.4) and (2.6) where the batch and recursive formulas for computing the FIM are given in the context of the problem discussed there). In the recursive form, the CRLB and FIM are often referred to as the posterior Cramer-Rao lower bound (P-CRLB) and the Bayesian Fisher information matrix (B-FIM). As a result of the above discussion, we define our metrics of estimation accuracy based on the FIM. The FIM can be scalar when the quantity of interest only consists of a single element. However, in most cases, this quantity consists of several elements and, therefore, the FIM is a matrix. It is possible to formulate an optimization problem for sensor management with a matrix as the objective function (see [7] where optimization problems with matrix-form objective functions and constraints are discussed). However, it is more convenient to work with scalar objective functions. Therefore, we seek functions that assign a real number to the FIM. Such functions must have certain desirable properties. For instance, the real numbers assigned to the matrices must be consistent with a partial ordering on the set of matrices, i.e. if one matrix is larger than another one based on the ordering relation, its correspond- 3 Chapter 1. Introduction ing real number must also be larger. There are other desirable properties for these function. One is that these functions must be concave. We discuss the implication of concavity in Chapter 2 and use this property to prove some results there. In [8], an excellent exposition on these properties is provided where it is also shown that matrix means are functions that satisfy these properties. Examples of matrix means are the trace of a matrix divided by L, the L-th root of the determinant and the smallest eigenvalue of the matrix where L is the number of elements in the quantity of interest. Figure 1.1 illustrates the aforementioned concepts in the context of estimating the position of an object by a sensor network. Following a common practice, we call this object a target. Throughout this dissertation, we often discuss sensor management for estimating the position (and the velocity) of a target. Estimating the position of a stationary target is also known as localization while estimating the position and the velocity of a moving target is known as tracking. The optimization problem for sensor management can be formulated in various forms. In its most general form, a sensor management problem is a dynamic stochastic optimization problem. The problem is formulated based a dynamic stochastic model for the the quantity of interest, e.g. the position of the target, and a stochastic measurement model for sensors. These models determine the evolution of the probability density of the quantity of interest which is the actual underlying state in this dynamic stochastic optimization problem. In order to solve this optimization problem, we must find a policy that assigns an optimal action to each sensor for every 4 Chapter 1. Introduction Estimator Belief State Sensor Manager Actions Measurements Target Sensor Figure 1.1: Sensor management for estimating the position of a target. The sensor manager predicts how the belief state evolves if a sequence of actions is given to the sensors. The sensor manager then determines the optimal actions and communicate these actions to the sensors. New measurements are then made by the sensors and processed by the estimator to update the belief state. possible probability density at any given time instant. Finding such policies conveys a closed-loop approach to sensor management. Unfortunately, it is rarely possible to obtain closed-form expressions for such policies. Nor is it possible to compute them numerically as the domain set of these policies is an uncountable set of probability densities. In this regard, the general sensor management problem resembles partially-observable Markov decision processes (POMDP) [9] and is plagued with the same difficulties in order to be solved. There is, however, another layer of complexity in sensor management problems that does not exist in POMDPs. In sensor management problems, the objective function, i.e. the metric of estimation accuracy, is a non-linear function of the underlying 5 Chapter 1. Introduction probability density whereas in conventional POMDPs, the objective function is a linear function of the probability density. This non-linearity causes extra difficulties in solving sensor management problems which, for instance, has been discussed in [10,11] in the context of sensor management for hidden Markov models. For certain combinations of dynamic and measurement models, however, the evolution of the probability density or at least its covariance matrix is not affected by actual measurements. In such cases, the sensor management problem becomes a dynamic deterministic optimization problem and hence an open-loop solution is optimal. As an example, consider a case where both the quantity of interest and sensors have a linear Gaussian model. It is well known that for this case the Kalman filter is the optimal and efficient estimator and that the covariance matrix of the Kalman filter can be calculated a priori [12,13]. Therefore, there is no advantage in delaying actions and observing measurements. As another example, consider a deterministic dynamic model for the evolution of the quantity of interest and a measurement model for sensors that consists of a non-linear function of the value of this quantity and an additive Gaussian measurement error. It can be shown that for this case, the evolution of the FIM is deterministic and independent of actual measurements [4]. We will focus on such deterministic optimization problems throughout this dissertation. We discuss two problems in this regard. The first problem is in fact a static optimization problem which involves selecting a pre-specified number of sensors in a network of fixed sensors in order to estimate the value of a time-invariant parameter. 6 Chapter 1. Introduction In the other problem, we consider designing a trajectory for a mobile sensor in order to track a moving target. As we will see, even finding an optimal solution for these deterministic optimization problems is computationally very demanding. In connection with the first problem, we also study a problem that is posed from the perspective of the target whose position or other critical parameters is to be estimated by the sensor network. In this problem, we assume: (i) The target has some capabilities to attack and destroy a limited number of sensors or manipulate the information sent to them. (ii) It intends to use these capabilities to adversely affect the estimate of its parameter. It then must be decided which sensors to be attacked. Ideally, the answer is the sensors that are to be selected for making measurements but it is unlikely that the target exactly knows these sensors. In the absence of such knowledge, we show how a notion borrowed from cooperative game theory can be employed to identify those sensors that can be potentially more informative. In the rest of this chapter, we summarize the main contributions of this dissertation, provide a literature review, list the supporting publications and finally introduce the common notation. This dissertation is divided into two main parts based on whether sensor management is concerned with fixed or mobile sensors. In the first part, which comprises Chapters 2 and 3, we focus on fixed sensors. In the second part, which comprises Chapter 4, we concentrates on mobile sensors. 7 Chapter 1. Introduction Sensor Management via Dynamic Stochastic Optimization Sensor Management via Dynamic Deterministic Optimization Sensor Evaluation Chapter 3 Sensor Subset Selection Problem (Static Optimization) Chapter 2 Trajectory Design Problem (Dynamic Deterministic Optimization) Chapter 4 Symmetric Probabilistic Values as Power Indices Analysis of Continuous and Lagrangian Bounds Parameterization of Optimal Solutions Figure 1.2: Illustration of the main themes explored in this dissertation. 1.2 Main Contributions Figure 1.2 illustrates the main themes of this dissertation. It also shows the interaction between these themes and indicates how they have been addressed in this dissertation. In the following, we provide more details on these themes and the contributions made. 1. Analysis of Lagrangian and Continuous Relaxations of the Sensor Subset Selection Problem (Chapter 2): For a network of fixed sensors engaged in estimating the unknown value of a time-invariant parameter, a sensor management problem is how to select M out of the total of N sensors such that a metric of estimation accuracy is maximized. This problem is called the sensor subset selection problem. Since the parameter is time-invariant and sensors are also fixed, the sensor subset selection problem is a static combinatorial optimization problem i.e. a 0-1 in- 8 Chapter 1. Introduction teger program. This problem can be considered as an instance of resource allocation problems [14] or knapsack problems [15] with special characteristics of its own. In Chapter 2, we provide a through analysis of the Lagrangian and continuous relaxation of the sensor subset selection problem and outline algorithms for computing these bounds. Although the sensor subset selection problem is a static optimization problem, as a combinatorial optimization problem, it is still difficult to solve. Carrying out an N exhaustive search is prohibitively expensive because subsets must be evaluated M for this purpose. Branch-and-bound algorithms [15,16] are the alternatives which can potentially eliminate the need for an exhaustive search. However, for a branch-andbound algorithm, we need to have good upper bounds for the problem. An upper bound is often obtained by relaxing some of the constraints of the problem and solving the relaxation problem. A solution of the relaxation problem can also be exploited as a benchmark for evaluating heuristic algorithms and as an initial point for local search algorithms. Motivated by these advantages, we study the Lagrangian and continuous relaxations of the sensor subset selection problem with the determinant of FIM as the metric of estimation accuracy. We first show that the determinant of the FIM can be represented by a homogenous polynomial as a function of decision variables (see Proposition 2.2.2). We further show that the determinant of the FIM is a supermodular function (see Proposition 2.2.3) and hence the sensor subset selection problem with this metric is a 9 Chapter 1. Introduction supermodular knapsack problem. Gallo and Simeone [17] have shown that the Lagrangian relaxation of a supermodular knapsack problem can be solved in polynomial time. Mainly, we show that the dual function is a piecewise linear convex function with at most N breakpoints in the Lagrangian relaxation of the sensor subset selection problem. Therefore, the minimum of the dual function can be found by an outer approximation algorithm with at most N iterations. In each iteration of the outer approximation algorithm, the dual function must be evaluated at one point. The evaluation of the dual function requires finding the maximum of a supermodular function which is known to be computable in polynomial time [18]. However, we also show that the continuous bound is tighter than the Lagrangian bound while it can be still found in polynomial time. This latter statement is established by noting that the determinant shares a unique maximizer with its L-th root (where L is the number of elements in the parameter that must be estimated) and the log-determinant and the maximization of these two latter functions can be done in polynomial time because of their concavity. While standard algorithms for constrained convex optimization [7] can be exploited in order to solve the continuous relaxation of the sensor subset selection problem, we devise a very efficient algorithm for solving the continuous relaxation of a variation of the sensor subset selection problem. In this variation, called the measurement allocation problem, sensors are allowed to make more than one measurement and the cost of making each measurement is equal for all sensors. Knowing that the de- 10 Chapter 1. Introduction terminant can be represented by a homogenous polynomial, we then show that what is known as the natural selection process in population genetics [19] shares a unique stable equilibrium with the optimal allocation vector in the measurement allocation problem. Hence, by updating an initial allocation vector via the natural selection process, a sequence of allocation vectors are generated that eventually converges to the optimal allocation vector. 2. Symmetric Probabilistic Values for Identifying Informative Sensors (Chapter 3): We establish a novel approach for identifying the informative sensors under the assumptions of Chapter 2 from the perspective of a target whose critical parameters is to be estimated by the sensor network. We assume that the target does not exactly know how many and which sensors are to be selected but it assigns a probability to each subset of sensors reflecting its belief about the selection of that subset. We show that a power index, based on symmetric probabilistic values [20] in cooperative game theory, can be assigned to each sensor to determine how informative the sensor is relative to others. To establish this result, we first point out that parameter estimation by a sensor network can be modeled as a cooperative game where each subset is a cooperation opportunity that generates a certain estimation accuracy. It is known that in a cooperative game, symmetric probabilistic values or semivalues, computed as the weighted average of the marginal contributions of a player to all subsets, are indicators of the relative power of players. The weights for computing a 11 Chapter 1. Introduction symmetric probabilistic value are determined by how likely it is for a subset to be actually realized as the outcome of cooperation. In the context of our discussion, these weights are determined by the probabilities that the target assigns to the subsets. Computing the power index of a sensor involves a summation over all subsets of sensors. As such, the difficulty of computation increases exponentially with the number of sensors. However, we show that by choosing the determinant of the FIM as the metric of estimation accuracy and for the probabilities that only depends on the size of subsets, the computation of power indices can be done in polynomial time. This result is mainly achieved because the determinant of the FIM can be compactly represented by a (hyper-)matrix. Asserting that the determinant of the FIM has a (hyper-)matrix representation is a consequence of the fact that the determinant of the FIM can be represented by a homogenous polynomial, a result that we establish in Chapter 2. The (hyper-)matrix representation for cooperative games can be regarded as a generalization of the (hyper-)graph representation for cooperative games. Deng and Papadimitriou [21] have studied cooperative games with a (hyper-)graph representation. By extending their results, we provide explicit formulas for computing two well-known power indices: the Banzhaf value [22] and the Shapley value [23]. We also provide a formula for computing the power index when only subsets with a certain size are to be selected. From this formula, the power index for any arbitrary probability distribution over the size of subsets can be computed. 12 Chapter 1. Introduction 3. Parameterization of optimal observer trajectories for bearings-only tracking (Chapter 4): For a mobile sensor, a sensor management problem is how to plan the motion of the sensor such that a metric of estimation accuracy is maximized. This problem is called the trajectory design problem. As opposed to the sensor subset selection problem, a trajectory design problem is not a static optimization problem. A dynamic component always exists due to the presence of a mobile sensor. We consider the trajectory design problems for bearings-only tracking [3]. In bearings-only tracking, the position and the velocity of a moving target is estimated by measuring the direction-of-arrival (DOA) of an acoustic, electromagnetic or seismic signal emitted from the target to the sensor(s). We show that the optimal solutions of the trajectory design problem for bearings-only tracking can be parameterized by only two ratios. In our formulation of the problem, we assume that the mobile sensor, which is also called the observer, travels at a constant speed but the direction of its motion, i.e. its course, can be controlled as desired. We also assume a constant-velocity target, i.e. a target that has a deterministic model with fixed speed and course during the observation period. As a result, it suffices to only estimate the initial position of the target and its velocity, two time-invariant parameters. This ensures that an open-loop solution is optimal. There is, however, no closed-form expression known for the open-loop solution. The problem can be solved numerically by dynamic programming if the FIM is dis- 13 Chapter 1. Introduction cretized or alternatively by approximating the course control function by a partial sum of some basis functions such as the Chebyshev polynomials [24] and finding the coefficients of these basis functions. In general, one numerical solution must be obtained for the following set of problem-specific parameters: the initial positions of the target and the observer, the speeds of the target and the observer and the observation period. However, in the case of bearings-only localization, Hammel et al. [25] have noted that these parameters can be encompassed in what is known as the range-to-baseline ratio. In other words, the optimal course control function for bearings-only localization can be uniquely specified by the range-to-baseline ratio. This is the ratio of the distance that the observer can travel directly towards the target during the observation period relative to the initial distance between the target and the observer. We provide a more generalized result for bearings-only tracking where we show that the optimal course control function in this case can be parameterized by the range-to-baseline ratio and the velocity ratio which is the ratio of the speed of the observer relative to the speed of the target. In our proof, we show that the FIM is scaled only by a constant if the speed of the observer, the speed of the target, the observation period and the distance between the target and the observer are all simultaneously scaled such that the range-to-baseline ratio and the speed ratio both remain constant. This proves that the optimal course control function is invariant for any metric of estimation accuracy defined based on the FIM. 14 Chapter 1. Introduction 1.3 Related Works The sensor subset selection problem has gained considerable attention in recent years [5, 26–31]. A closely related problem is the sensor deployment (or placement) problem [32–35] where the position of sensors must be determined in order to obtain the maximum coverage of a field. For a general survey of sensor selection problems in sensor networks, the reader can consult with [36]. Many authors have studied the single sensor selection problem [5, 26–28]. Kaplan in [29] considers the sensor subset selection problem. He proposes a greedy algorithm [15] for solving this problem which consists of a fill-up phase and an exchange phase (see Algorithm 2.3). In Chapter 2, we verify the effectiveness of this algorithm for solving the sensor subset selection problem in the context of bearings-only localization by comparing the performance of the algorithm with the continuous bound of the problem. In [30], Kaplan also investigates a localized algorithm for the sensor subset selection problem where only sensors in a critical range are considered for making measurements. In [31], Tharmarasa et al. study the sensor subset selection problem for multi-target tracking where selected sensors remain active over a prespecified number of time instants. The authors solve the continuous relaxation of this problem and use a local search algorithm to obtain a discrete solution. The sensor subset selection problem has also been formulated in other forms. Most notably, in [37], Chhetri et al. exchange the role of the objective function and the constraint and aim at finding the minimum number of sensors that satisfy a desired 15 Chapter 1. Introduction level of estimation accuracy. They use the trace of the FIM as the metric of estimation accuracy and obtain a linear objective function and a quadratic constraint (when the number of elements in the parameter is 2). Their solution approach is based upon converting this problem to a mixed-integer program and then solving the program by a branch-and-bound algorithm. Although cooperative game theory has been considered in other works for signal processing and telecommunication applications (see [38] for packet forwarding or [39] for multiple source coding), the context for which we use cooperative game theory in Chapter 3 differs from other works in the literature. Non-cooperative game theoretic concepts have been extensively discussed in sensor networks for decentralized decision-making and learning but those are clearly different from the cooperative game theoretic concepts that we discuss here. The trajectory design problems for bearings-only localization and tracking are well-studied subjects with their origin in submarine tracking and aircraft surveillance [40,41]. These problems have been studied within two frameworks: deterministic and stochastic, with earlier works [42–47] emphasizing on a deterministic framework. In a deterministic framework, it is assumed that measurements are error-free and the motion of the target is deterministic. It is then investigated under what conditions the position of the target can be uniquely determined from bearing measurements. The general conclusion is that the observer needs to out-maneuver the target in order that a one-to-one mapping can be established between the measurements and 16 Chapter 1. Introduction Observer Trajectory Observer Trajectory Observer Trajectory acc.= 0 acc.= 0 acc.= 0 acc.= 0 Stationary Target (a) Observer Trajectory Target Trajectory Maneuvering Time (d) Target Trajectory Target Trajectory (b) (c) Stationary Observer Observer Trajectory Target Trajectory Target Trajectory (e) (f) Figure 1.3: Examples of observable and unobservable scenarios for bearings-only localization and tracking. In the scenarios shown in (a), (b), (c) and (d), the position of the target can be determined from bearing measurements. However, in the scenarios shown in (e) and (f), this is not possible. With the exception of the scenario shown in (c) where the acceleration is non-zero for the observer, the speed of the target and the speed of the observer are assumed to be constant during the observation period in all scenarios. the position of the target. More formally stated, a necessary condition is that the observer’s trajectory must have higher non-zero derivatives with respect to time than the target’s trajectory [43]. Illustrative examples for various scenarios are shown in Figure 1.3. In a stochastic framework [25, 48–55], which we also pursue in Chapter 4, an additive Gaussian measurement error is present in the measurement model and the target is assumed to have a stochastic model. We earlier mentioned the contribution 17 Chapter 1. Introduction of [25]. As a pioneer work [48], Fawcett considers the effect of a single maneuver of the observer on the FIM when the target has a constant-velocity model. Authors in [49] introduce the the trace of the FIM as a metric of estimation accuracy in the trajectory design problem and employ a gradient-based method to solve the small instances of the problem for constant-velocity targets. In [52], authors explore the use of function approximation and the differential inclusion method when there are additional constraints imposed on the observer trajectory. As opposed to previous works, Logothetis et al. [50, 51] consider a target with a stochastic model, namely a nearly-constant velocity target with random instantaneous accelerations. Along with other methods, they use a very crude discretization of the covariance matrix of the extended Kalman filter to solve the trajectory design problem with dynamic programming. In [53], by discretizing measurements and considering a Markov chain model for the target, the authors formulate the trajectory design problem as a POMDP. We previously mentioned this approach in the context of a general sensor management problem. In [54], the trajectory design problem for multiple observers is considered and myopic solutions are numerically computed. Finally, the authors in [55] consider a vision-based target localization application where the observer has a limited field of view and, therefore, additional constraints must be taken into account for trajectory design. 18 Chapter 1. Introduction 1.4 Notation Throughout this dissertation, we use lower-case bold serif letters, e.g x, for vectors and upper-case bold serif letters, e.g. X, for (hyper-)matrices. A hyper-matrix in our terminology is an array of numbers that has more than two dimensions. If we specifically work with a two-dimensional array, we use the term matrix. We also use lower-case Italic Roman letters for scalar variables, e.g. m. Parameters fixed at a given value are usually denoted by an upper-case Roman letter, e.g. N. The elements of a vector x and a (hyper-)matrix X are denoted by xi and xijk··· unless otherwise stated. An alternative method for representing a vector or a (hyper-)matrix is to place brackets around the general element of that vector or (hyper-)matrix, e.g. [xi ] and [xijk···]. If a vector or matrix has an index itself, parentheses are used to separate the index of the vector or the matrix from its elements. For instance, the elements of xi are denoted by (xi )j . The value of a variable at a given time instant is denoted by its symbol followed by the time stamp embraced with parentheses, e.g. x(k). The derivative of a vector-valued function f with respect to x is denoted by where the element in row i and column j is given by ∂f ∂x ∂fi . Although occasionally ∂xj dropped, the transpose operator is denoted by T. The transpose of the derivative of a vector-valued function is denoted by ∂Tf . ∂x We use calligraphic letters for representing sequences or sets, e.g. X = {x(k)}N k=0 for a sequence or N for a set, with the exception of universally defined sets such as the set of integers Z, or the set of real numbers R. The non-negative elements of a set 19 Chapter 1. Introduction is denoted by the set symbol and a plus sign attached to it, e.g. R+ denotes the set of non-negative real numbers. Similarly, the set of strictly positive elements of a set is denoted by the set symbol and two plus signs attached to it, e.g. Z++ denotes the set of positive integers. Symbols such as N N denote the N-time Cartesian product of set N . The cardinality or the size of set N is denoted by |N |. Expectation, when taken over probability density p(x), is denoted by Ep(x) . The Gaussian distribution is sometimes denoted by N(µ, R) where µ and R are the mean and the covariance matrix. The determinant, the trace and the set of eigenvalues of matrix X are denoted by det(X), trace(X), λ(X), respectively. Other symbols are defined as needed. 20 Part I Management of Fixed Sensors 21 Chapter 2 Upper Bounds for the Sensor Subset Selection Problem 2.1 Overview In recent years, networks of fixed sensors have been widely employed for pervasive surveillance in hostile and remote environments. These networks are often set up to monitor fire, wildlife habitats, boarder activities, etc. With very limited onboard energy and long periods of monitoring, it is crucial that the sensors are efficiently used in these networks. In this chapter, we consider the sensor subset selection problem which, to some extent, addresses this issue. In this problem, M out of N sensors must be selected to estimate the value of a time-invariant parameter such that a metric of estimation accuracy is maximized. The constraint on the number of sensors that can be selected reflects a concern on the amount of the energy that the network can consume. While various heuristic algorithms are proposed for solving the sensor subset selection problem and its variation [5,26–31], we fully analyze the characteristics of the 22 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem Lagrangian and continuous relaxations of this problem when the determinant of the (B-)FIM is used as the metric of estimation accuracy. The results of this analysis can be used in branch-and-bound algorithms and local search algorithms as well as for evaluating the performance of heuristic algorithms. In the continuous relaxation, the (binary) decision variables are allowed to take on any real number between 0 and 1. In the Lagrangian relaxation, the constraints are moved into the objective function with the decision variables still restricted to be binary. There are two determinant-based functions of the (B-)FIM that are commonly used in the literature as the metrics of estimation accuracy. The first one is the L-th root of the determinant, where L is the number of elements in the parameter. This function is a matrix mean [8] and, as such, satisfies a number of desirable properties. One of these properties is its concavity in the continuous domain. The concavity property guarantees that estimation accuracy is not improved by interpolation of measurements. The logarithm of the determinant (log-determinant) of the (B-)FIM is another determinant-based metric of estimation accuracy. The motivation for using the log-determinant stems from information theory where the log-determinant of the covariance matrix of a Gaussian distribution quantifies its entropy [56]. The logdeterminant is also a concave function that induces a partial ordering on the set of matrices identical to the one induced by the L-th root of the determinant. Hence, the sensor subset selection problem acquires the same characteristics with both functions. It is well known that if the objective function of a combinatorial optimization 23 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem is concave (in the continuous domain) and its feasible region is convex (again in the continuous domain), then its Lagrangian bound is tighter than its continuous bound [15]. Therefore, for the sensor subset selection problem with the L-th root of the determinant or the log-determinant as its objective function, the Lagrangian bound is tighter than the continuous bound. Unfortunately, however, while the continuous bound can be computed in polynomial time via a convex optimization algorithm [7], computing the Lagrangian bound remains as difficult as finding the optimal solution of the original problem. The determinant of the (B-)FIM also induces an ordering on the set of matrices which is identical to the ordering induced by L-th root of the determinant and the log-determinant but the determinant is not a concave function. We prove several properties for the determinant of the (B-)FIM and study how these properties can be exploited for solving the Lagrangian and continuous relaxations of the sensor subset selection problem and its variations. We show that both bounds can be computed in polynomial time in this case and that the continuous bound is tighter than the Lagrangian bound (as opposed to what holds for the other two functions). We also take advantage of a representation of the determinant as a homogenous polynomial to outline an algorithm for solving the continuous relaxation of a variation of the sensor subset selection problem where sensors are allowed to make more than one measurement. This chapter is organized as follows. Section 2.2 formulates the sensor subset 24 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem selection problem and proves several important properties of its objective function. Sections 2.3 and 2.4 discuss the characteristics of the Lagrangian bound and the characteristics of the continuous bound, respectively. Section 2.5 gives some concluding remarks. 2.2 Formulation of the Sensor Subset Selection Problem In this section, we formally define the sensor subset selection problem and derive several important properties of its objective function that will be used subsequently in this chapter and the following one. We start by denoting the set of all sensors by N = {1, 2, · · · , N} and the parameter vector whose value is unknown to sensors and must be estimated by p ∈ RL . The measurement model for sensors is characterized by zi = hi (p) + vi (2.1) for i = 1, 2, · · · , N where zi ∈ RD is the measurement vector of the i-th sensor, hi is a vector-valued differentiable function of p, and v1 , v2 , · · · , vN are mutuallyindependent zero-mean Gaussian random error vectors. The covariance matrix of vi is denoted by Ri . Later in this section, we comment on the implications of using a more general measurement model. As we will see, the most critical assumption for 25 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem proving our results is that the measurements should be mutually-independent. For optimization problems, it is often more convenient to have a vector representation of sets. In this chapter, we, therefore, mostly follow this convention. We identify set S ⊂ N by vector x ∈ {0, 1}N where xi = 1 if i ∈ S, (2.2) 0 if i ∈ /S for i = 1, 2, · · · , N. The vectors corresponding to sets N , {i}, and ∅ are denoted by e, ei and 0, respectively. The measurements that are collected from the selected sensors are denoted by Z(x) where x is given by (2.2). Definition 2.2.1 The sensor subset selection problem is defined as solving one of the following: 1. If p is regarded as a non-random parameter [1], max x∈{0,1}N det(J(x)) (2.3) such that cT x ≤ M, N where c ∈ R++ , M ∈ R++ and J(x) = Ep(Z(x)|p) ∂T ∂ log(p(Z(x)|p)) log(p(Z(x)|p)) ∂p ∂p for x = 0 and J(0) = 0. Furthermore, it is assumed that 26 N i=1 ci (2.4) > M > 0. Chapter 2. Upper Bounds for the Sensor Subset Selection Problem 2. If p is regarded as a random parameter, i.e. a prior density p(p) exists for p, max det(JB (x)) x∈{0,1}N (2.5) T such that c x ≤ M, N where c ∈ R++ , M ∈ R++ such that N i=1 ci > M > 0. Furthermore, JB (x) = Q + Ep(p) {J(x)} (2.6) where Q = Ep(p) ∂ T ∂ log(p(p)) log(p(p)) . ∂p ∂p (2.7) Remark Matrices J(x) and JB (x) are the FIM and the B-FIM, respectively. If we ˆ (x) an arbitrarily-chosen estimator of parameter p when measurements denote by p are collected from the non-zero elements of x, then the inverse of J(x) provides a ˆ (x) in the sense that if C(x) denotes lower bound for the covariance matrix of p the covariance matrix, C(x) − J−1 (x) is positive semi-definite. Similarly, the inverse of JB (x) provides a lower bound for the covariance matrix of an arbitrarily-chosen estimator of parameter p when, in addition to Z(x), prior density p(p) is also used for estimation. As a result, both det(J(x)) and det(JB (x)) can be regarded as the metrics of estimation accuracy. For the rest of this chapter, we assume that the sensor subset selection problem 27 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem is given by (2.3). However, most results either directly hold or can be worked out similarly for (2.5). We make a remark in this regard later. 2.2.1 Structural Properties of the FIM and its Determinant We now present three results on the nature of the FIM and its determinant. These results will be exploited in Sections 2.3 and 2.4 for computing the upper bounds. In Proposition 2.2.1, we show that the FIM can be expanded as a linear combination of N positive semi-definite matrices. In Proposition 2.2.2, we show that the determinant of the FIM can be expanded as a homogeneous polynomial. Finally, from Proposition 2.2.3, it can be deduced that the determinant of the FIM is supermodular. Proposition 2.2.1 For the measurement model (2.1), it holds that N J(x) = xi Si (2.8) i=1 where S1 , S2 , · · · , SN are positive semi-definite matrices given by Si = ∂ T hi −1 ∂hi R . ∂p i ∂p (2.9) Proof Since measurement error vectors v1 , v2 , · · · , vN are mutually-independent, 28 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem we can write p(Z(x)|p) as p(Z(x)|p) = i∈S p(zi |p) (2.10) where S is the set corresponding to vector x. It follows that J(x) = Ep(Z(x)|p) i∈S = ∂ T ∂ log(p(zi |p)) log(p(zi |p)) ∂p ∂p i∈S Ep(Z(x)|p) i∈S j∈S = Ep(zi |p) i∈S + ∂ T ∂ log(p(zi |p)) log(p(zi |p)) ∂p ∂p Ep(zi |p) i∈S j∈S j=i ∂ T ∂ log(p(zi |p)) log(p(zj |p)) ∂p ∂p ∂ T ∂ log(p(zi |p)) Ep(zj |p) log(p(zj |p)) ∂p ∂p (2.11) where in the last line we have used the fact that z1 , z2 , · · · , zN are mutually-independent. We next note that because vi has a Gaussian distribution, we can write ∂ ∂hi log(p(zi |p)) = (zi − hi )T R−1 . i ∂p ∂p (2.12) Hence, Ep(zi |p) ∂ log(p(zi |p)) ∂p 29 =0 (2.13) Chapter 2. Upper Bounds for the Sensor Subset Selection Problem and J(x) can be written as J(x) = Ep(zi |p) i∈S = i∈S = i∈S ∂hi ∂ T hi −1 Ri Ep(zi |p) (zi − hi )(zi − hi )T R−1 i ∂p ∂p (2.14) ∂ T hi −1 ∂hi R ∂p i ∂p N = ∂ ∂ T log(p(zi |p)) log(p(zi |p)) ∂p ∂p xi i=1 ∂ T hi −1 ∂hi R . ∂p i ∂p N i=1 Proposition 2.2.2 If S = xi Si where S1 , S2 , · · · , SN are L × L matrices, it holds that N N N det(S) = a1 =1 a2 =1 ··· aL =1 wa1 a2 ···aL xa1 xa2 · · · xaL (2.15) where wa1 a2 ···aL = det (Sa1 ).1 (Sa2 ).2 · · · (SaL ).L (2.16) with (Si ).j , for 1 ≤ i ≤ N and 1 ≤ j ≤ L, denoting the j-th column of matrix Si . Proof This is an immediate consequence of expressing the determinant of S as N N xa1 (Sa1 ).1 det(S) = det a1 =1 a2 =1 N xa2 (Sa2 ).2 · · · xaL (SaL ).L (2.17) aL =1 and noting that the determinant of a matrix is a multi-linear function of the columns of the matrix. 30 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem Proposition 2.2.2 states that wa1 a2 ···aL is the determinant of a matrix that is constructed by having the first column of Sa1 as its first column, the second column of Sa2 as its second column and so on. Remark We use (hyper-)matrix W = [wa1 a2 ···aL ] to compactly represent the coefficients defined by (2.16). This (hyper-)matrix has L dimensions and N elements in each dimension. Motivated by Proposition 2.2.1, we define the following function. Definition 2.2.2 Let S1 , S2 , · · · , SN be some positive semi-definite matrices. We define function v such that for any x ∈ RN , v(x) = det( N i=1 xi Si ). As we assume for the rest of this chapter, we note that if S1 , S2 , · · · , SN are given by (2.9), function v then extends the definition of the determinant of the FIM to the set of real vectors. We next prove that function v is supermodular over the set of non-negative real vectors. N Proposition 2.2.3 If x, x′ ∈ R+ , it holds that v(x1 ) + v(x2 ) ≤ v(x1 ∨ x2 ) + v(x1 ∧ x2 ) (2.18) where x1 ∨ x2 denotes the componentwise maximum and x1 ∧ x2 denotes the componentwise minimum of x1 and x2 . 31 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem N Proof We first note that function v is non-negative and non-decreasing over R+ . Inequality (2.18) can then be easily proved if N i=1 N We, therefore, consider the region of R+ where xi Si and/or N i=1 xi Si N ′ i=1 xi Si are singular. is non-singular for a given x. We denote this region by X . To prove the supermodularity of function v over X , it suffices to show that ∂ 2 v(x) ≥ 0 for any x ∈ X [57]. We note that ∂xj ∂xi ∂v(x) = det ∂xi N N xk Sk trace k=1 −1 xk Sk Si (2.19) k=1 and ∂ 2 v(x) = det ∂xj ∂xi N N xk Sk trace k=1 N −1 xk Sk k=1 Si trace −1 xk Sk Sj k=1 N − trace xk Sk )−2 Si Sj k=1 ≥0 (2.20) where we have used the fact that for any two positive semi-definite matrices A and B, trace(A)trace(B) ≥ trace(AB) [58]. Remark Although the measurement model (2.1) encompasses a large number of practical applications, a more general measurement model can also be considered for all discussions presented in this chapter if a regularity condition [2] holds for the measurement model. In particular, the general measurement model zi = hi (p, vi ) 32 (2.21) Chapter 2. Upper Bounds for the Sensor Subset Selection Problem can be considered for all discussions where zi , p and hi are defined as before and v1 , v2 , · · · , vN are mutually-independent random error vectors but it also holds that for i = 1, 2, · · · , N, function hi and the probability distribution of vi are such that Ep(zi |p) ∂ log(p(zi |p)) ∂p =0 (2.22) The above condition, which is called the regularity condition, generally holds unless the support of p(zi |p) depends on parameter p. Under this condition and by using (2.11), we can write J(x) as N J(x) = xi Ep(zi |p) i=1 ∂ T ∂ log(p(zi|p)) log(p(zi |p)) . ∂p ∂p (2.23) Therefore, by replacing the definition of Si in (2.9) with Si = Ep(zi |p) ∂ T ∂ log(p(zi |p)) log(p(zi |p)) , ∂p ∂p (2.24) we see that J(x) can be expressed as a sum of positive semi-definite matrices and all the results stated for the measurement model (2.1) can also be stated for the measurement model (2.21). 33 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem Remark Note that from (2.6) and (2.8), we can write N JB (x) = Q + Ep(p) xi Si i=1 (2.25) N =Q+ i=1 xi Ep(p) {Si }. Hence, JB (x) can also be written as a sum of positive semi-definite matrices where only a constant matrix Q is added to the sum. Consequently, the proof given for Proposition 2.2.3 can be repeated to show that the determinant of JB (x) is also a supermodular function. Because of the presence of matrix Q, the determinant of JB (x) cannot be immediately written as a homogenous polynomial as there will be some terms with an order lower than L. However, if the inequality constraint of the problem (2.5) is replaced with an equality constraint, i.e. N i=1 ci xi = 1, one M can always multiply the terms of the polynomial resulted from the expansion of the determinant with N i=1 ci xi as many times as needed without affecting the value of M the polynomial in order to obtain a homogenous representation. 2.3 Characteristics of the Lagrangian Relaxation In this section, we study the Lagrangian relaxation of the problem (2.3). The fact that the determinant is a supermodular function gives special characteristics to the Lagrangian relaxation of the problem (2.3). These characteristics were first noted by Gallo and Simeone in [17] for the more general case of the supermodular knapsack 34 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem problem. The following proposition summarizes those results. Proposition 2.3.1 [17] Consider the following combinatorial optimization problem max x∈{0,1}N q(x) (2.26) such that cT x ≤ M N where c ∈ R++ , M ∈ R++ , N i=1 ci > M > 0 and function q is a generic function defined over {0, 1}N with the following properties: (i) q(0) = 0, (ii) e = [1, 1, · · · , 1]T is a maximum point of q over {0, 1}N , (iii) q is a supermodular function over {0, 1}N . Then, the dual function of the problem (2.26) is a piecewise linear convex function with at most N breakpoints where the largest breakpoint is given by u = max{ q(e) |i = ci 1, 2, · · · , N}. The main point of Proposition 2.3.1 is that the number of breakpoints of the dual function of the problem (2.26) does not grow exponentially with N and, in fact, it is at most N. The piecewise linearity and convexity of the dual function, otherwise, hold even if properties (i) to (iii) are not satisfied. It is easy to see that the objective function of the problem (2.3) has all the properties listed in Proposition 2.3.1. Condition (i) follows immediately from the definition of the objective function of this problem. Condition (ii) follows from the fact that the 35 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem objective function is non-decreasing and, finally, condition (iii) follows from Proposition 2.2.3. 2.3.1 Outer Approximation Algorithm for Solving the Lagrangian Relaxation As a result of these observations, an outer approximation algorithm [15] with at most N iterations can be applied to find the Lagrangian bound for the problem (2.3). We introduce some notation in order to describe the steps of this algorithm. The Lagrangian of the problem (2.3) is given by L(x, u) = v(x) − u(cT x − M). (2.27) where u ∈ R+ is the Lagrange multiplier. The dual function is an over-estimator of the maximum of function v over the feasible region. The dual function is obtained by maximizing the Lagrangian with respect to x, i.e. φ(u) = max L(x, u). x∈{0,1}N (2.28) The Lagrangian bound for the problem (2.3) is given by φ∗ = min+ φ(u). u∈R 36 (2.29) Chapter 2. Upper Bounds for the Sensor Subset Selection Problem In order to find this bound, we note that, for any non-negative u, a line that passes through (u, φ(u)) and has a slope equal to the subgradient of function φ at that point is an under-estimator of function φ. A subgradient of function φ at u is given by g(u) = −(cT x(u) − M) (2.30) where x(u) is the vector that maximizes L(x, u). Similarly, for any non-negative u′ and u′′ , where u′ < u′′ , g(u′) < 0 and g(u′′) > 0, function φo (u; u′, u′′ ) = max{φ(u′) + g(u′)(u − u′ ), φ(u′′) + g(u′′ )(u − u′′ )} u (2.31) is an under-estimator (and an outer approximation) of function φ. It is easy to check that the minimizer of function φo is given by u∗ = v(x(u′′ )) − v(x(u′ )) φ(u′′ ) − g(u′′)u′′ − (φ(u′) − g(u′)u′ ) = . g(u′) − g(u′′) cT x(u′′ ) − cT x(u′ ) (2.32) Clearly, by replacing u′ with u∗ if g(u∗) ≤ 0 and by replacing u′′ with u∗ if g(u∗) > 0, another outer approximation of function φ can be obtained whose minimizer is closer to the minimizer of function φ. Since function φ has a maximum of N breakpoints, after N iterations, an approximation is obtained for which φo (u∗ , u′, u′′ ) = φ(u∗ ). Obviously the Lagrangian bound as the minimum of function φ is equal to φ(u∗ ). We note that in order to compute g(u∗), x(u∗ ) must be known. This, in turn, 37 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem requires solving the following problem max v(x) − u∗ cT x. x∈{0,1}N (2.33) However, since the objective function of the problem (2.33) is supermodular, a solution for this problem can be found in polynomial time. Consequently, the Lagrangian bound can be found in polynomial time. The overall algorithm for computing the Lagrangian bound is summarized below. The computational cost of this algorithm is dominated by the computational cost of solving the problem (2.33) which subsequently depends on what type of algorithm is used for this purpose. An algorithm, which is guaranteed to solve the problem (2.33) in polynomial-time, is the ellipsoid algorithm of Gr¨oetschel, Lov´asz, and Schrijver [18]. However, a more practical algorithm with an unknown run-time is the minimumnorm-point algorithm of Fujishige [59]. • Algorithm 2.1: The Lagrangian Bound for the Sensor Subset Selection Problem Inputs: A. A set of sensors: N = {1, 2, · · · , N}. B. Matrices S1 , S2 , · · · , SN given by (2.9) to evaluate function v. C. Cost vector: c. 38 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem D. Total number of sensors to be selected: M. Output: A. Lagrangian bound for the sensor subset selection problem: φ∗ . Steps: 1. Let u′ = 0 and u′′ = max{ q(e) |i = 1, 2, · · · , N}. ci 2. Let x(u′ ) = e and x(u′′ ) = 0. 3. Compute u∗ = v(x(u′′ )) − v(x(u′ )) cT x(u′′ ) − cT x(u′ ) 4. Find x(u∗ ) = arg maxx∈{0,1}N v(x) − u∗ cT x. 5. If u∗ = v(x(u∗ )) − v(x(u′ )) , cT x(u∗ ) − cT x(u′ ) stop and return φ∗ = v(x(u∗ )) − u∗ (cT x(u∗ ) − M). 6. If cT x(u∗ ) > M, let u′ = u∗ . Otherwise let u′′ = u∗ and go to Step 3. 39 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem 2.4 Characteristics of the Continuous Relaxation After studying the Lagrangian bound, we now consider the continuous relaxation of the problem (2.3) and study the characteristics of the continuous bound. Let vc∗ denote the continuous bound for the problem (2.3). This bound is computed via max v(x) x∈[0,1]N (2.34) such that cT x ≤ M. The following result establishes a relationship between the Lagrangian bound and the continuous bound. Proposition 2.4.1 For the problem (2.3), it holds that vc∗ ≤ φ∗ , i.e. the continuous bound is tighter than the Lagrangian bound. Proof We note that vc∗ = max {v(x)|cT x ≤ M} x∈[0,1]N ≤ min+ max L(x, u) u∈R x∈[0,1]N (2.35) = min+ max L(x, u) u∈R x∈{0,1}N = φ∗ . The second line in (2.35) is due to weak duality. The third line follows from the fact that the maximum of function L for a given u always occurs at one of the extreme 40 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem ∂ 2 v(x) ≥ 0 for i = 1, 2, · · · , N. ∂x2i ∂v(x) This result was obtained as part of the proof of Proposition 2.2.3. Hence, is a ∂xi points of [0, 1]N . To prove this, we first note that non-decreasing function. We next note that ∂L(x, u) ∂v(x) = − uci . ∂xi ∂xi (2.36) Therefore, depending on the value of u and ai , three different patterns emerge for ∂L(x, u) as xi increases from 0 to 1. It can be increasing, decreasing, or decreasing ∂xi first and then increasing from some point through this interval. However, it is never possible that ∂L(x, u) increases first and then decreases. This, in turn, shows that ∂xi every element of the maximizer of L(x, u) must be either 0 or 1. In order to solve the problem (2.34), we note that it shares identical maximizer(s) with the following problems: max x∈[0,1]N log(v(x)) (2.34′ ) such that cT x ≤ M and max x∈[0,1]N 1 v(x) L (2.34′′ ) such that cT x ≤ M. 1 This follows immediately from the fact that functions f (x) = x L and f (x) = log(x) are monotone increasing over R+ . However, while v(x) is not a concave function of x 41 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem 1 over [0, 1]N , both log(v(x)) and v(x) L are. Therefore, the problems (2.34′ ) and (2.34′′ ) have a unique maximizer which can be found in polynomial time by using algorithms for constrained convex optimization [7]. Consequently, the problem (2.34) has a unique maximizer which can be found in polynomial time. 2.4.1 Natural Selection Process for Solving a Variation of the Continuous Relaxation The continuous relaxation of the problem (2.3) can be even solved by a simpler algorithm than those commonly used for convex optimization if this problem is modified as follows. Definition 2.4.1 The measurement allocation problem is posed as solving: max x∈Z+ v(x) (2.37) such that eT x = M where M ∈ Z++ , M < N and J(x) is given by (2.4). In this variation of the problem (2.3), sensors are allowed to make more than one measurement and the cost of making one measurement is identical for all sensors. By defining m = x and taking into account Proposition 2.2.2, the continuous relaxation M 42 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem of the problem (2.37) can be written as max m∈∆N−1 N where ∆N−1 = {m ∈ R+ | 1≤a1 ,a2 ,··· ,aL ≤N N i=1 wa1 a2 ···aL ma1 ma2 · · · maL (2.38) mi = 1} denotes the standard simplex in RN . The problem (2.38) involves the maximization of a homogenous polynomial over the standard simplex. A general homogenous polynomial may have many local maximizers over the standard simplex. In fact, finding the global maximizer of a homogenous polynomial over the standard simplex is known to be NP-Hard even for L = 2 as it can be associated with the maximum clique problem [60]. However, as we discussed earlier, the problem (2.38), in our particular case, has a unique maximizer. Hence, our task for finding its maximizer becomes much simpler. We next show that the so-called natural selection process in population genetics [19] can be used to find the maximizer of the problem (2.38). The use of the natural selection process for finding the local maximizers of a quadratic homogenous polynomial, i.e. L = 2, over the standard simplex is noted in [61]. More generally, it can be shown that the set of local maximizers of a homogenous polynomial is equal to the set of the stable equilibria of the natural selection process (see Proposition 2.4.2 below). Thus, if a problem such as (2.38) has only a unique maximizer by updating an allocation vector m via the natural selection process, this maximizer can be found. To prove the desired result, it is more convenient that we first symmetrize (hyper)matrix W. Let us denote by α(a1 , a2 , · · · , aL ) all permutations of a1 , a2 , · · · , aL . 43 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem Definition 2.4.2 For (hyper-)matrix W, its symmetrization is given by (hyper)matrix U where ua1 a2 ,···aL = 1 L! wβ (2.39) β∈α(a1 ,a2 ,··· ,aL ) for 1 ≤ a1 , a2 , · · · , aL ≤ N. For instance, if W is a N × N matrix, then U is given by uij = wij + wji 2 (2.40) and if W is a N × N × N hyper-matrix, then U is given by uijk = wijk + wikj + wjik + wjki + wkij + wkji 6 (2.41) for 1 ≤ i, j, k ≤ N. It is easy to see that, in general, the value of a homogenous polynomial does not change if W is replaced with its symmetrized version U. Furthermore, it can be shown that when the elements of W are obtained via (2.16), then the elements of U are non-negative. The proof for this assertation in the general case is rather cumbersome. Instead, we just verify it when L = 2 and then take another approach to ensure the non-negativity of the elements U. For L = 2 and 1 ≤ i, j ≤ N where 44 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem j = i, we note that uii = wii = det(Si ) ≥ 0. Furthermore, 1 uij = (wij + wji) = det(Si + Sj ) − det(Si ) − det(Sj ) ≥ 0 2 (2.42) where the latter holds because the determinant is superadditive over the set of positive semi-definite matrices. However, even if there are elements of U that are negative, we note that the maximizer of problem (2.38) does not change if a constant is added to all elements of U. Hence, the non-negativity of the elements of U can be ensured by adding an appropriate constant. Remark Although never needed, some of the earlier results of this chapter can also be established by using the same technique discussed above. In particular, we note that by replacing wa1 a2 ···aL with wa1 a2 ···aL + γba1 ba2 · · · baL in (2.15) for a given γ, the maximizer of the problem (2.3) does not change. Hence, it can be always ensured that the coefficients of the objective function of this problem are non-negative by adding an appropriate constant. The supermodularity of the objective function then follows from the non-negativity of the coefficients [15], without resorting to Proposition 2.2.3. Furthermore, in Proposition 2.4.1, it is no longer to show that the derivative of the objective function with respect to a decision variable is non-decreasing since this is readily known for a polynomial with non-negative coefficients. The fact that (hyper-)matrix U is symmetric and its elements are non-negative can be used to prove the following proposition. 45 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem Proposition 2.4.2 If allocation vector m is updated via the natural selection process, i.e. mi vi (m) v(m) (2.43) uia1 a2 ···aL−1 ma1 ma2 · · · maL−1 (2.44) ua1 a2 ···aL ma1 ma2 · · · maL , (2.45) m′i = for 1 ≤ i ≤ N where vi (m) = 1≤a1 ,a2 ,··· ,aL−1 ≤N and v(m) = 1≤a1 ,a2 ,··· ,aL ≤N it then holds that v(m′ ) ≥ v(m). Proof Note that in (2.44), vi (m) is the partial weighted sum of U when the first digit in the index is fixed to i. We first extend this notation to address the partial weighted sums in other dimensions. Let I be a fixed number between 1 and L. We then define viI (m) = ua1 a2 ··· i ···aL−1 ma1 ma2 1≤a1 ,a2 ,··· ,aL−1 ≤N · · · maL−1 . (2.46) position I Therefore, viI (m) is the partial weighted sum of U when the index is fixed to i in dimension I. For instance, when L = 2, v11 (m) means the partial weighted sum of the first row, v12 (m) means the partial weighted sum of the first column and so on. Note 46 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem that vi (m) = vi1 (m). Furthermore, since U is symmetric, we have vi (m) = viI (m) (2.47) for 1 ≤ I ≤ L and 1 ≤ i ≤ N. We next rewrite the main inequality of the proposition in a form that has already been proved in the literature. We note that v(m′ ) = 1≤a1 ,a2 ,··· ,aL ≤N = 1≤a1 ,a2 ,··· ,aL ua1 a2 ···aL m′a1 m′a2 · · · m′aL ma va (m) ma2 va2 (m) ma va (m) ··· L L . ua1 a2 ···aL 1 1 v(m) v(m) v(m) ≤N (2.48) Therefore to prove that v(m′ ) ≥ v(m), we must show 1≤a1 ,a2 ,··· ,aL ≤N ua1 a2 ···aL ma1 ma2 · · · maL va1 (m)va2 (m) · · · vaL (m) ≥ (v(m))L+1 . (2.49) Using (2.47), we can write the above as 1≤a1 ,a2 ,··· ,aL ≤N ua1 a2 ···aL ma1 ma2 · · · maL va11 (m)va22 (m) · · · vaLL (m) ≥ (v(m))L+1 . (2.50) The above inequality has been proved in [62] for (hyper-)matrices with non-negative elements. 47 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem According to Proposition 2.4.2, when L = 2, the allocation vector is updated as follows: sum of elements in the first row of A sum of all elements in A sum of elements in the second row of A m′2 = sum of all elements in A m′1 = (2.51) (2.52) and so on for m′3 to m′N where A = [wij mi mj ]. To initialize the natural selection process, a reasonable choice is the centroid of ∆N−1 , i.e. [ N1 , · · · , N1 ]T . This choice ensures that the algorithm is not initially biased in favor of any particular solution. The overall algorithm for solving the continuous relaxation of the measurement allocation problem is given below. • Algorithm 2.2: The Continuous Bound for the Measurement Allocation Problem Inputs: A. A set of sensors: N = {1, 2, · · · , N}. B. (Hyper-)matrix of the sensor subset selection problem: W. C. Total number of sensors to be selected: M. D. Termination criterion: ǫ. Output: 48 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem A. An estimate for the continuous bound of the measurement allocation problem: v˜c . Steps: 1. Let m = [ N1 , N1 , · · · , N1 ]T . 2. Compute m′i = mi vi (m) v(m) for 1 ≤ i ≤ N where vi and v are given by (2.44) and (2.45), respectively. 3. If m′ − m m > ǫ, go to Step 2. Otherwise let v˜c = MN v(m′ ) and return. Algorithm 2.2 typically converges in a few tens of iterations for ǫ as low as 10−6 (see below for a numerical example). Each iteration of this algorithm is dominated by NL operations because the computation of vi in (2.44) requires NL−1 operations and vi must be computed for N sensors. As a result, for the parameters with two or three elements, i.e. L = 2 or 3, it only takes a few milliseconds on a modest personal computer to find the optimal allocation vector even when the network has a few hundred sensors. 49 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem z Target βi Sensor i y θi x Figure 2.1: Geometry of bearings-only localization in three-dimensional space. Numerical Analysis of the Convergence Rate of the Natural Selection Process To study the behavior of Algorithm 2.2 numerically, we study the problem (2.37) in the context of bearings-only localization. Figure 2.1 shows the geometry of bearingsonly localization in three-dimensional space [42]. The figure indicates that the true DOA to sensor i can be specified by two angles. If the position of the target is denoted by p = [xt , yt , zt ] and the position of sensor i for i = 1, 2, · · · , N is denoted by pi = [xi , yi, zi ], these angles are related to the position of the target and the position of the sensor via θi (p) = atan2(yt − yi , xt − xi ) βi (p) = atan2(zt − zi , (yt − yi )2 + (xt − xi )2 ) (2.53) (2.54) where atan2(y, x) is the four-quadrant arc tangent of y/x in the interval [−π, π]. As a result, we can write function hi in the measurement model (2.1) as 50 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem θi (p) . hi (p) = βi (p) and note that (2.55) sin(θi ) cos(θi ) − ∂hi rxyi rxyi = sin(β )cos(θ ) ∂p sin(βi )sin(θi ) i i − − ri ri where rxyi = (yt − yi )2 + (xt − xi )2 and ri = 0 cos(βi ) ri (2.56) (yt − yi )2 + (xt − xi )2 + (zt − zi )2 . Consequently, Si can be computed using (2.9) and W can be computed using (2.16). For bearings-only localization in two-dimensional space, we note that just one angle is sufficient to specify the DOA. Hence, hi (p) = θi (p) and ∂θi = ∂p − sin(θi ) rxyi cos(θi ) rxyi . (2.57) We generated 500 networks in both two-dimensional space and three-dimensional space with 100 sensors in each network. The target was located at the origin of a Cartesian coordinate system and the sensors were spread around the target in a 200 × 200 square or a 200 × 200 × 200 cube. The positions of the sensors were drawn from a uniform distribution. It was assumed that the standard deviation of the measurement error for each angle of the DOA is 10 degrees and that the measurement error for one angle is independent of the measurement error for the other angle. A histogram of the number of iterations needed for the convergence of Algorithm 2.2 51 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem PSfrag replacemen 70 Percentage of cases 60 50 40 30 20 10 0 1-50 51-100 101-150 151-200 201-250 251-300 Number of iterations Figure 2.2: A histogram for the number of iterations needed for the convergence of Algorithm 2.2. The dark-colored bars are for localization in two-dimensional space and the white bars are for localization in three-dimensional space. is shown in Figure 2.2 when ǫ was set to 10−6 . On average, it took 61.2 iterations for the algorithm to converge when localization was carried out in two-dimensional space while it took 85.1 iterations for the algorithm to converge when localization was carried out in three-dimensional space 2.4.2 Analysis of the Performance of a Greedy Algorithm for Solving the Sensor Subset Selection Problem One of the benefits of computing upper bounds for combinatorial optimization problems is to analyze the performance of heuristic algorithms that are used for solving them. We compared the performance of a greedy algorithm [15], which has been proposed in [29, 30] for solving the problem (2.3), with the continuous bound of this problem, which can be obtained by solving the problem (2.34). In [29, 30], the performance of this algorithm is only compared with the performance of other heuristic 52 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem algorithms. We did our analysis in the context of bearings-only localization as formulated in Section 2.4.1 This greedy algorithm is generally used for solving knapsack problems. It consists of a fill-up phase and an exchange phase and can be summarized as follows. • Algorithm 2.3: A Greedy Algorithm for Solving the Sensor Selection Problem Inputs: A. A set of sensors: N = {1, 2, · · · , N}. B. (Hyper-)matrix of the sensor subset selection problem: W. C. Total number of sensors to be selected: M (Assuming M ≥ 2). Output: A. A lower bound for the sensor selection problem: v. Phase 1 - Fill-Up Steps: 1. Find (k, l) ∈ arg max{v(ei + ej )|i, j ∈ N } where v(x) = 1≤a1 ,a2 ,··· ,aL ≤N 53 wa1 a2 ···aL xa1 xa2 · · · xaL . Chapter 2. Upper Bounds for the Sensor Subset Selection Problem 2. Let x = ek + el . 3. Let K0 = N \ {k, l} and K1 = {k, l}. 4. Repeat the following steps until |K1 | = M 4.1. Find k ∈ arg max{v(x + ei )|i ∈ K0 }. 4.2. Let x := x + ek , K0 := K0 \ {k} and K1 := K1 ∪ {k}. Phase 2 - Exchange Steps: 1. Repeat the following steps until K0 = ∅ or K1 = ∅ in which case return v = v(x). 1.1. Find (k, l) ∈ arg max{v(x + ei − ej ) − v(x)|i ∈ K0 , j ∈ K1 }. 1.2. if v(x + ek − el ) − v(x) < 0, stop and return v = v(x). Otherwise let x := x + ek − ek , K0 := K0 \ {k} and K1 := K1 \ {l}. Our empirical results indicate that Algorithm 2.3 is extremely efficient for solving the problem (2.3) in the context of bearings-only localization. The values that Algorithm 2.3 generated for the objective function of the problem (2.3) were within 1% of the continuous bound for all 500 sample networks in two-dimensional space and they were within 1% of the continuous bound for 99% sample networks in threedimensional space. 54 Chapter 2. Upper Bounds for the Sensor Subset Selection Problem 2.5 Concluding Remarks In this chapter, we analyzed the Lagrangian and continuous relaxations of the sensor subset selection problem with the determinant of the (B-)FIM as its objective function. Table 2.1 summarizes the characteristics of the sensor subset selection problem with various determinant-based objective functions. Based on these results, to obtain an upper bound for the sensor subset selection problem in polynomial time, one can solve the continuous relaxation of this problem with the log-determinant or the L-th root of the determinant as the objective function. On the other hand, when the constraint of making only a single measurement by each sensor is removed, an upper bound can be obtained in polynomial time by using the natural selection process with the determinant as the objective function. Table 2.1: Characteristics of the Sensor subset selection problem with three determinant-based objective functions Objective Function Logarithm and Lth Root of Determinant Determinant Concave Supermodular No Tighter Bound Lagrangian Bound Computable in Polynomial Time Continuous Yes No Yes Continuous Lagrangian Continuous 55 and Chapter 3 Power Index of a Sensor 3.1 Overview In this chapter, we still work under the assumptions of the previous chapter and describe a novel approach for identifying informative sensors in a network of fixed sensors from the perspective of a target that is being observed by the network. Our premise in this chapter is that the target has some capabilities to adversely affect the measurements of a limited number of sensors by attacking and destroying them or by manipulating the measurements they make. The target, however, has no perfect knowledge as to which sensors are to be selected for making measurements. In the absence of such perfect knowledge, we show that the target can assign a value to each sensor which determines, relatively, how informative that sensor is. We call this value the power index of a sensor. The power index is computed based on the measurement model for sensors as well as the probabilities that the target assigns to each subset of sensors reflecting its perception from how likely it is that the subset will be selected. If these probabilities only depend on the size of subsets, then the notion of power indices coincides with the notation of symmetric probabilistic values in cooperative 56 Chapter 3. Power Index of a Sensor game theory. Symmetric probabilistic values are known to be indicators of the relative power of players in cooperative games. To provide more perspective, let us briefly discuss a simple example that we later expand in Section 3.4. Consider Figure 3.1 where three sensors can use bearing measurements to estimate the position of a target. Let us assume that the target knows that two sensors are to be selected for making measurements but it can attack only one sensor. Since the target is only concerned how accurately its position will be estimated by the sensor network, it can choose a metric of estimation accuracy and solve the sensor subset selection problem to discover that sensors 1 are 2 are the optimal choices for making measurements. Following this line of thought, we can then argue that it is inconsequential from the perspective of the target which of the two sensors is attacked and destroyed because the other sensor cannot resolve the uncertainty about the position of the target on its own. On the other hand, it is evident that if there is even a slim chance that sensor 3 is selected instead of sensor 1, it is of great consequence for the target to destroy sensor 2, because otherwise sensors 2 and 3 can resolve the uncertainty of its position. Power indices, as we will see, capture such possibilities and declare sensor 2 as the most informative sensor. The rest of this chapter is organized as follows. In Section 3.2, we define the parameter estimation game and study its properties. In Section 3.3, we introduce the notion of power indices and discuss how they can be computed efficiently for probability distributions that only depend on the size of subsets. We also compute 57 Chapter 3. Power Index of a Sensor y coordinate 2 1 3 x coordinate Figure 3.1: A simple network configuration to study the relative power of sensors for bearings-only localization. The circle identifies the position of the target and the squares identify the position of sensors, labeled from 1 to 3. Sensor 2 has the largest power index. the power indices of sensors for bearings-only and range-only target localization and tracking in Section 3.4. Concluding remarks are made in Section 3.5. 3.2 Cooperative Parameter Estimation Game In this section, we introduce the cooperative parameter estimation game. Generally, a cooperative game is identified by a pair (N , v), where N = {1, 2, · · · , N} is the set of players and v : 2N → R is a function which assigns a real number to each subset (coalition) of players. As we will see, in the context of the parameter estimation game, function v is a metric of estimation accuracy. More specifically, we choose the determinant of the (B-)FIM as the metric of estimation accuracy because power indices can be then computed in polynomial time with this metric. As a result of this choice, the discussion in this section resembles the discussion in Section 2.2. We, therefore, shorten our discussion here and refer the reader to Section 2.2 for more explanations. 58 Chapter 3. Power Index of a Sensor Let N = {1, 2, · · · , N} denote the set of all sensors and p ∈ RL denote the parameter vector of the target, which is unknown to the sensors and must be estimated. The measurement of sensor i for i = 1, 2, · · · , N is related to p via zi = hi (p) + vi (3.1) where zi ∈ RD is the measurement vector, hi is a vector-valued differentiable function of p, and v1 , v2 , · · · , vN are mutually-independent zero-mean Gaussian random error vectors. The covariance matrix of vi is denoted by Ri . Similar to Section 2.2, all results presented here also hold for the more general measurement model (2.21). The measurements that are collected from the sensors in set S ⊂ N are denoted by ZS here. Definition 3.2.1 The cooperative parameter estimation game (N , v) is a game in which N is the set of sensors and v(S) for set S ⊂ N is one of the following functions: 1. If p is regarded as a non-random parameter [1], v(S) = det(J(S)) (3.2) ∂ T ∂ log(p(ZS |p)) log(p(ZS |p)) ∂p ∂p (3.3) where J(S) = Ep(ZS |p) 59 Chapter 3. Power Index of a Sensor for S = ∅ and J(∅) = 0. 2. If p is regarded as a random parameter, i.e. a prior density p(p) is given for p, v(S) = det(JB (S)) (3.4) JB (S) = Q + Ep(p) {J(S)} (3.5) where and Q = Ep(p) ∂ T ∂ log(p(p)) log(p(p)) . ∂p ∂p (3.6) Again, for the rest of this chapter, we assume that function v is given by (3.2). This is only for convenience and brevity in notation. All statements either directly hold or can be expanded such that they hold when function v is given by (3.4). Since a power index is computed from the target side and the exact value of p is known, it is more reasonable to use (3.2). Using (3.4) for computing a power index makes sense when the target is somehow aware of the prior density that the sensors are using. We next note that based on Proposition 2.2.2, which has been restated below, the parameter estimation game can be compactly represented by a (hyper-)matrix. By compact representation, we mean that instead of 2N numbers, which are generally needed to specify function v, only NL numbers are sufficient. Since N, the number of sensors, is often much larger than L, the size of the unknown parameter vector, it 60 Chapter 3. Power Index of a Sensor generally holds that 2N ≫ NL . Proposition 3.2.1 For set S ⊂ N , v(S) as defined by (3.2) can be written as v(S) = a1 ∈S a2 ∈S ··· wa1 a2 ···aL (3.7) aL ∈S where wa1 a2 ···aL = det (Sa1 ).1 (Sa2 ).2 · · · (SaL ).L (3.8) in which (Si ).j for i = ai ∈ S and 1 ≤ j ≤ L is the j-th column of matrix Si , where Si is given by Si = ∂ T hi −1 ∂hi R . ∂p i ∂p (3.9) Remark W = [wa1 a2 ···aL ] is an L-dimensional (hyper-)matrix with N elements in each dimension. 3.3 Computation of Power Indices Having established what the parameter estimation game is, we next define the power index of a sensor. A power index is determined by a probability distribution that captures the target’s perception of how likely it is that a certain subset will be selected. In particular, we compute power indices for three different probability distributions. In the first probability distribution, which leads to the Banzhaf value, all subsets are 61 Chapter 3. Power Index of a Sensor equally likely to be selected. In the second probability distribution, which leads to the Shapley value, all subset sizes are equally likely to be selected. Finally, we consider a probability distribution where only the probability of selecting subsets with a given size is non-zero. From the formula for this latter probability distribution, the power index for any arbitrary probability distribution that only depends on the size of subsets but not the elements of subsets can be computed. Definition 3.3.1 The power index of sensor i in the parameter estimation game (N , v) is given by ρi = S⊂N \{i} pi (S)(v(S ∪ {i}) − v(S)), (3.10) where pi (S) is the probability that the sensors in set S ⊂ N \ {i} are selected when it is known that sensor i is also selected. In practice, it is more natural to assume that the target’s probabilistic perception of subset selection is captured by a general probability distribution pa over all subsets of N from which the conditional probability distribution pi is derived. Although in general any probability distribution can be considered as pa , in what follows, we assume that pa is only determined by the size of the subsets but not their elements. This assumption means that the target has some probabilistic perception about the size of the subset that is to be selected but it does not have any probabilistic perception about specific sensors to be selected. This assumption also aligns our definition of power indices with the definition of symmetric probabilistic values in cooperative 62 Chapter 3. Power Index of a Sensor game theory and allows us to derive expressions for some well-known symmetric probabilistic values. For instance, if it is assumed that all subsets are equally likely to be selected, the power index then becomes the Banzhaf value. In this case, pa (S) for all S ⊂ N is given by 1 1 and p (S) for all S ⊂ N \ {i} is given by . We formalize this case a 2N 2N−1 by the following definition. Definition 3.3.2 A power index is called the Banzhaf value or the Banzhaf index when pi (S) = 1 2N−1 for S ⊂ N \ {i}. Proposition 3.3.1 provides a formula for computing the Banzhaf value, given the following definition. Definition 3.3.3 In (hyper-)matrix W with L dimensions and N elements in each dimension, let α = a1 a2 · · · aL be the index to element wα . For any 1 ≤ i ≤ N and 1 ≤ q ≤ L, we define L κq (i) = a1 a2 · · · aL | Ij (a1 a2 · · · aL ) = q, Ii (a1 a2 · · · aL ) = 1 (3.11) 1 if there exists j such that aj = i, (3.12) j=1 where Ii (a1 a2 · · · aL ) = 0 otherwise. If one thinks of (hyper-)graphs, κq (i) identifies the q-size edges that are shared by vertex i and q − 1 other vertices. Furthermore, note that since a1 a2 · · · aL cannot 63 Chapter 3. Power Index of a Sensor have more than L distinct digits, the maximum value of q is L. Proposition 3.3.1 The Banzhaf value of sensor i in the parameter estimation game is given by L ρB i 1 = q=1 α∈κq (i) 2q−1 wα . (3.13) Proof We consider the contribution of wα to ρB i where α ∈ κq (i). For every set S that does not contain i but contains the 1 sensors, with the addition of i, wα other q − contributes N−q sets of size S that do not contain w to ρ . There are α i 2N−1 S−q+1 1 i but contain the other q − 1 sensors and S can be any number between q − 1 and N − 1. Hence, the overall contribution of wα is N−1 N−q wα = wα 2N−1 N−1 2 s=q−1 s−q+1 N−q N − q = wα . 2q−1 r=0 r (3.14) As an illustration, consider a case where the unknown parameter belongs to R3 and hence W becomes an N × N × N hyper-matrix. Then, according to the above proposition, the Banzhaf value of sensor 1 is given by ρB 1 1 = w111 + 2 N 1 (w1ii + wi1i + wii1 ) + 4 i=2 N N (w1ij + wi1j + wij1 ). (3.15) i=2 j=2 j=i The first term in (3.15) corresponds to q = 1 in (3.13), the second term corresponds to q = 2, and finally the last term corresponds to q = 3. 64 Chapter 3. Power Index of a Sensor Another well-known case is when all subset sizes are equally likely to be selected. In this case, pa (S) for S ⊂ N is given by pa (S) = S!(N − S)! 1 1 = N+1 N + 1! N S (3.16) where S = |S|. Again, pi can be determined from pa and the following definition can be established. Definition 3.3.4 A power index is called the Shapley value when pi (S) = S!(N − S − 1)! N! for S ⊂ N \ {i}. Similar to the Banzhaf value, the following proposition provides a formula for computing the Shapley value. Proposition 3.3.2 The Shapley value of sensor i in the parameter estimation game is given by L ρSh i = q=1 α∈κq (i) 1 wα . q (3.17) Proof Again, we consider the contribution of wα to ρSh i where α ∈ κq (i). For every set S that does not contain i but contains the other q − 1sensors, with the addition of i, wα contributes N−q S!(N − S − 1)! sets of size S wα to ρi . There are N! S−q+1 that do not contain i but contain the other q − 1 sensors, and S can be any number 65 Chapter 3. Power Index of a Sensor between q − 1 and N − 1. Hence, the overall contribution of wα is N−1 wα N − q s!(N − s − 1)! . N! s=q−1 s−q+1 It can be then shown by induction that the above sum is equal to (3.18) 1 , and the result q follows. Continuing with the example given earlier, we can compute as follows the Shapley value of sensor 1 when the unknown parameter belongs to R3 ρSh 1 1 = w111 + 2 N 1 (w1ii + wi1i + wii1 ) + 3 i=2 N N (w1ij + wi1j + wij1 ). (3.19) i=2 j=2 j=i As can be seen, the elements of W that are shared by a number of sensors are equally divided between them in the computation of the Shapley value. Finally, we consider the probability distribution in which only subsets with size S are selected. It can be seen that in this case pa is given by 1 if |S| = S, N pa (S) = S 0 otherwise 66 (3.20) Chapter 3. Power Index of a Sensor and consequently 1 N−1 pi (S) = S−1 0 if |S| = S − 1 and i ∈ / S, (3.21) otherwise. By following the arguments given in Propositions 3.3.1 and 3.3.2, we state the following proposition without a proof. Proposition 3.3.3 When only the subsets with size S are selected, the power index of sensor i in the parameter estimation game is given by min(S,L) ρSi = q=1 α∈κq (i) N−q S−q wα . (3.22) N−1 S−1 Note that the power index of sensor i for any probability distribution that only depends on the size of subsets can be computed as the weighted average of ρ1i , ρ2i , · · · , ρN i where the weights represent the probability that a certain size is selected. For instance, when ρ1i , ρ2i , · · · , ρN i are equally weighed by 1 , their average is equal to the N Shapley value. Remark In [21], a cooperative game is defined over a weighted (hyper-)graph where 67 Chapter 3. Power Index of a Sensor the characteristic function of the game for any subset of vertices is the sum of the weights of the edges connecting those vertices. This definition can be extended to (hyper-)matrices as follows. Definition 3.3.5 Let W be an L-dimensional (hyper-)matrix with N elements in each dimension. Let N = {1, 2, · · · , N}. A cooperative (hyper-)matrix game, denoted by (N , W), is a cooperative game defined over N where the value of set S ⊂ N is given by v(S) = a1 ∈S a2 ∈S ··· wa1 a2 ···aL . (3.23) aL ∈S Note that the parameter estimation game is a (hyper-)matrix game. Therefore, (3.13), (3.17) and (3.22) show how various power indices can be computed in (hyper-)matrix games. 3.4 Power Indices for Localization and Tracking Arguably, the most important parameters that a target must protect are its position and velocity. It is therefore critical to know which sensors can be more informative for this purpose. Typically, target localization and tracking is carried out by using bearing or range measurements. In this section, we compute the power indices of sensors for bearings-only and range-only localization and tracking. Interestingly, we discover that power indices have a very similar structure for both measurement models and that what causes the power index of a sensor to be large for bearings-only localiza- 68 Chapter 3. Power Index of a Sensor tion also causes the power index of a sensor to be large for range-only localization (see (3.31) and (3.37)). To keep notation simple, for localization, we assume that the position of the target is estimated in two-dimensional space, i.e. p = [xt , yt ]. For tracking, we assume that the target’s position and velocity are estimated in one-dimensional space, i.e. p = [xt , vxt ]. When p ∈ R2 , it can be seen from (3.13) and (3.17) that the Banzhaf value and the Shapley value are equal and given by ρB i = ρSh i 1 = wii + 2 N (wij + wji). (3.24) j=1 j=i Similarly, from (3.22), it can be seen that the power index of sensor i when the subset size is S for 1 ≤ S ≤ N is given by ρSi S−1 = wii + N N (wij + wji). (3.25) j=1 j=i Therefore, in two-dimensional space, if wii = 0 for i = 1, 2, · · · , N, all power indices induce the same ranking among the sensors. 3.4.1 Localization We denote the position of the target by p = [xt , yt ] and the position of the i-th sensor for i = 1, 2, · · · , N by pi = [xi , yi ]. First, we consider bearings-only localization. The 69 Chapter 3. Power Index of a Sensor measurement of sensor i is given by zi = θi (p) + vi (3.26) θi (p) = atan2(yt − yi , xt − xi ) (3.27) where and v1 , v2 , · · · , vN are mutually-independent zero-mean Gaussian random errors with 2 variance σbi . We note that 1 ∂θi = ∂p ri where ri = (3.28) −sin(θi ) cos(θi ) (xt − xi )2 + (yt − yi )2 is the relative range of sensor i from the target. Consequently, from (3.9), Si can be written as 1 Si = 2 2 ri σbi sin2 (θi ) −sin(θi )cos(θi ) 2 −sin(θi )cos(θi ) cos (θi ) (3.29) and, from (3.8), wij for 1 ≤ i, j ≤ N can be written as sin2 (θi ) sin(θj )cos(θj ) sin(θi )cos(θi ) cos2 (θj ) wij = det( ) − − 2 2 2 ri2 σbi rj2 σbj ri2 σi2 rj2 σbj sin2 (θi )cos2 (θj ) − sin(θi )cos(θi )sin(θj )cos(θj ) . = 2 2 2 ri2 σbi rj σbj 70 (3.30) Chapter 3. Power Index of a Sensor Finally, by plugging (3.30) into (3.24), the power index of a sensor for bearings-only localization can be expressed as N ρBearing i = j=1 sin2 (θi − θj ) . 2 2 2 2ri2 σbi rj σbj (3.31) As a numerical example, consider a network of 5 sensors shown in Figure 3.2 with a target located at [0, 0]. We assume that the standard deviation of the measurement error is 10 degrees for all sensors, i.e. σbi = 10◦ . Using (3.31), we compute the power index of the sensors. These numbers are given in Table 3.1, which suggest that sensor 1 is the most informative one followed by sensors 3, 2, 4 and 5. To verify these results, we note that sensors 4 and 5 are farther away from the target and their measurements are almost identical. Hence, these two sensors must be the least informative ones. Among the other three sensors, the distance between sensor 2 and the target is larger while the information that can be gained from the measurement of this sensor can also be gained from the measurement of sensor 1. Therefore, this sensor must have the lowest power index among the three. Finally, between sensors 1 and 3, sensor 1 is more uniquely positioned. Hence it must have a higher power index. The above example may imply that the most informative sensor is always the one that is closest to the target. However, this is not necessarily true. As an example, consider Figure 3.3 where we have only changed the position of sensor 1 and moved it closer to sensor 3. In this configuration, sensor 2 provides more diversity in measure71 Chapter 3. Power Index of a Sensor 15 5 1 y coordinate 10 4 3 5 Target 0 -5 2 -10 -10 -5 0 5 x coordinate 10 15 Figure 3.2: A more general network configuration to study the power index of sensors for bearings-only and range-only localization. The circle identifies the position of the target and the squares identify the position of sensors which are labeled from 1 to 5. ments than sensor 1. Hence, as Table 3.2 suggests, its power index becomes larger than the power index of sensor 1 despite the fact that it is farther away from the target. For range-only localization, the measurement of sensor i is given by zi = hi (p) + vi (3.32) where hi (p) = a2 (xt − xi )2 + (yt − yi)2 (3.33) and a is a signal energy factor. Measurement errors v1 , v2 , · · · , vN are mutually2 independent zero-mean Gaussian random variables with variance σri . Following the 72 Chapter 3. Power Index of a Sensor 15 5 1 4 y coordinate 10 3 5 Target 0 -5 2 -10 -10 -5 0 5 x coordinate 10 15 Figure 3.3: This network configuration demonstrates that the closest sensor is not necessarily the most informative sensor. The circle identifies the position of the target and the squares identify the position of sensors which are labeled from 1 to 5. same procedure that we did for bearings-only localization, we determine that ∂hi −2a2 = ∂p ri3 and 4a4 Si = 6 2 ri σri (3.34) cos(θi ) sin(θi ) cos2 (θi ) sin(θi )cos(θi ) . sin(θi )cos(θi ) sin2 (θi ) (3.35) Consequently, wij for 1 ≤ i, j ≤ N is given by 4a4 cos2 (θi ) 2 ri6 σri wij = det( 4 4a sin(θi )cos(θi ) 2 ri6 σri 8 sin = 16a 2 4a4 sin(θj )cos(θj ) 2 rj6 σrj ) 4 2 4a cos (θj ) 2 rj6 σrj (θi )cos2 (θj ) − sin(θi )cos(θi )sin(θj )cos(θj ) . 2 6 2 ri6 σri rj σrj 73 (3.36) Chapter 3. Power Index of a Sensor Table 3.1: Power index of sensors in Figure 3.2 for bearings-only localization Sensor number 1 2 3 4 5 −1 Power index (10 ×) 1.07 0.84 1.00 0.67 0.33 Table 3.2: Power index of sensors in Figure 3.3 for bearings-only localization Sensor number 1 2 3 4 5 Power index (10−1×) 0.91 1.00 0.89 0.51 0.26 and the power index of a sensor for range-only localization can be expressed as N ρRange i 8 = 8a j=1 sin2 (θi − θj ) . 2 6 2 ri6 σri rj σrj (3.37) As a numerical example, we again consider the configuration shown in Figure 3.2. Table 3.3 contains the power index of the sensors, assuming that σri = 2 for all sensors and a2 = 700. This table suggests that sensor 3 is the most informative sensor for range-only localization. 3.4.2 Tracking This subsection illustrates briefly how the computation of power indices can be extended to tracking applications. We consider bearings-only tracking in one dimension where the position and velocity of a target must be estimated after collecting measurements for T time instants. The position of the target at time k for k = 1, 2, · · · , T 74 Chapter 3. Power Index of a Sensor Table 3.3: Power index of sensors in Figure 3.2 for range-only localization Sensor number 1 2 3 4 5 −1 Power index (10 ×) 1.64 0.74 1.75 0.58 0.07 is denoted by xt (k) and is determined by xt (k) = xo + kv (3.38) where xo is the initial position of the target and v is its velocity. To track the target, it suffices to know p = [xo , v]. The positions of sensors are denoted by pi = [xi , yi ] for i = 1, 2, · · · , N. The measurements of sensor i are related to xo and v via zi = hi (p) + vi where atan2(−yi , xo + v − xi ) atan2(−y , x + 2v − x ) i o i hi (p) = .. . atan2(−yi , xo + Tv − xi ) (3.39) (3.40) and v1 , v2 , · · · , vN are mutually-independent zero-mean Gaussian random error vec2 tors with covariance matrix Ri = σbi I. The derivative of hi with respect to p is given 75 PSfrag replacemen Chapter 3. Power Index of a Sensor 10 3 2 y coordinate 5 1 0 4 -5 -10 -10 -5 0 x coordinate 5 10 Figure 3.4: A network configuration to study the power index of sensors for bearingsonly tracking. Circles identify the position of the target where the measurements are made and the squares identify the position of sensors labeled from 1 to 4. by ∂hi = ∂p sin(θi (1)) − ri (1) sin(θi (2)) − ri (2) .. . − sin(θi (T)) ri (T) cos(θi (1)) ri (1) cos(θi (2)) ri (2) .. . cos(θi (T)) ri (T) where θi (k) = atan2(−yi , xo +kv −xi ) and ri (k) = (3.41) yi2 + (xo + kv − xi )2 . The power indices of the sensors can then be computed from (3.24) or (3.25) by first computing S1 , S2 , · · · , SN according to (3.9) and then computing W according to (3.8). As a numerical example, consider the configuration shown in Figure 3.4, where the position and velocity of the target must be estimated after observing the target for T = 5 time instants. Table 3.3 contains the power index of the sensors, assuming σbi = 10◦ for all sensors. In this example, sensor 3 is found to be the most informative sensor. 76 Chapter 3. Power Index of a Sensor Table 3.4: Power index of sensors in Figure 3.2 for bearings-only tracking Sensor number 1 2 3 4 Power index 6.52 5.54 7.63 6.87 3.5 Concluding Remarks In this chapter, we demonstrated how a proposed power index can be useful in identifying the informative sensors for distributed parameter estimation. Furthermore, it was shown how this power index can be efficiently computed by choosing an appropriate metric of estimation accuracy. A duality can be noted between solving the sensor subset selection problem and computing power indices. For solving the sensor subset selection problem, some knowledge of the target’s parameters is needed although such knowledge may not exist. For computing power indices, some knowledge of the sensors’ parameters is needed although such knowledge may not exist. As a remedy, one can assume a probability distribution for certain parameters of sensors and compute the expected value of power indices. This can be considered as a natural extension of this work. The analysis of power indices can ultimately be used in the design of attackresistant sensor networks by reinforcing the sensors that are deemed more informative for critical values of the target’s parameters. Furthermore, model-specific parameters of sensors can be selected such that the power indices of sensors become closer to each other. 77 Part II Management of Mobile Sensors 78 Chapter 4 Parameterization of Optimal Observer Trajectories for Bearings-Only Tracking 4.1 Overview In this chapter, we focus on the trajectory design problem for bearings-only tracking in two-dimensional space. This problem has been long studied in the literature [25, 48–55] and addresses the management of a mobile sensor, also called the observer, for estimating the position and the velocity of a moving target via bearing measurements. By a mobile sensor, we simply mean a platform that is capable of moving and is equipped with some sensory devices for making measurements. Due to difficulties with obtaining closed-form expressions for the optimal solution, this problem has been consistently only tackled numerically. A notable attempt in order to obtain closed-form expressions for the optimal solution is the work by Hammel et al. [25] where the authors have shown under the assumptions that they 79 Chapter 4. Parameterization of Optimal Observer Trajectories make for the dynamic model of the observer, the optimal solution for bearings-only localization can be uniquely uniquely specified by a single parameter. We extend these results to the more general case of bearings-only tracking. In our formulation of the problem, we assume a constant-velocity target, i.e. a target that travels at a constant speed along a straight line. We also assume that measurements are corrupted by mutually-independent additive errors with a Gaussian distribution. With these models for the target and measurements, an open-loop solution of the trajectory design problem is optimal. We, therefore, refer to an openloop solution as an optimal solution. The optimality of an open-loop solution generally holds for any deterministic model observed via measurements that have mutuallyindependent additive errors with a Gaussian distribution [4]. Following the assumptions made in [25], we consider an observer that travels at a constant speed but its course can be controlled as desired. We then show that the optimal course control function can be uniquely specified by the so-called range-tobaseline ratio (see Definition 4.3.1) and the speed ratio (see Definition 4.3.2). Our results hold for any statistical or information-theoretic metric of estimation accuracy but we prove these results based on the assumption that a scalar function of the FIM is the metric of estimation accuracy. We prove our results by showing that, in general, the FIM is only scaled by a constant if a scaling transformation of the problem-specific parameters preserves the value of the range-to-baseline ratio and the speed ratio. More specifically, we show 80 Chapter 4. Parameterization of Optimal Observer Trajectories that if the speed of the observer, the speed of the target, the observation period and the initial distance between the observer and the target are scaled such that the range-to-baseline ratio and the speed ratio remain constant, the FIM is only scaled by a constant and, therefore, the optimal course control function does not change. We finally numerically generate the optimal course control function for the given values of the range-to-baseline ratio and the speed ratio. For this purpose, we approximate the course control function by a partial sum of the Chebyshev polynomials and numerically find the coefficients of the partial sum that are optimal for the trajectory design problem. The organization of this chapter is as follows. In Section 4.2, we state the trajectory design problem for bearings-only tracking. In Section 4.3, we prove that the optimal course control functions of the trajectory design problem are invariant under the discussed transformation. We also determine the values of the range-to-baseline ratio and the speed ratio for which the objective function of the trajectory design problem is bounded. Some concluding remarks are also made in Section 4.4. 4.2 Formulation of the Trajectory Design Problem for Bearings-Only Tracking In this section, we formulate the trajectory design problem for bearings-only tracking. We start by introducing the dynamic models for the target and the observer. For the 81 Chapter 4. Parameterization of Optimal Observer Trajectories target, we assume that the following model holds xt (k + 1) xt (k) Vxt = + T , yt (k + 1) yt (k) Vyt (4.1) where T is the sampling time, [xt (k), yt (k)] is the position of the target at time instant k for k = 1, 2, · · · , N and [Vxt , Vyt ] denotes its constant velocity vector. Based on this model, the position of the target is uniquely determined at any given time if parameter pp,v = [xt (0), yt (0), Vxt , Vyt ] is known. Hence, the target is tracked if its initial position and its velocity are known. For the observer, we assume that the following model holds xo (k + 1) xo (k) cos(u(k)) = + Vo T , yo (k + 1) yo (k) sin(u(k)) (4.2) where [xo (k), yo (k)] is the position of the observer at time instant k, u(k) is the observer course control action at time instant k, Vo is its constant speed. As the observer moves according to the course control sequence U = {u(k)}N−1 k=0 , it collects N bearing measurements from time instant k = 1 to time instant k = N. A measurement at time instant k is related to the position of the target and the position of the observer at that time instant by z(k) = h(k) + v(k), 82 (4.3) Chapter 4. Parameterization of Optimal Observer Trajectories where h(k) = atan2(yt − yo (k), xt − xo (k)), (4.4) and v(1), v(2), · · · , v(N) are mutually-independent zero-mean Gaussian random errors with variance σv2 . We next determine how the FIM in bearings-only tracking can be related to the positions of the target and the observer over the observation period. Proposition 4.2.1 Based on dynamic models (4.1) and (4.2) and measurement model (4.3), the FIM for estimating pp,v = [xt (0), yt(0), Vxt , Vyt ] when the observer moves according to the course control sequence U is given by g1 (k) N g (k) 2 1 Jp,v (U) = 2 σv k=1 g (k) 3 g4 (k) g1 (k) g2 (k) g3 (k) g4 (k) , (4.5) where g1 (k) = − g2 (k) = yt (0) + kTVyt − yo(k) (xt (0) + kTVxt − xo (k))2 + (yt (0) + kTVyt − yo (k))2 xt (0) + kTVxt − xo (k) (xt (0) + kTVxt − xo (k))2 + (yt (0) + kTVyt − yo (k))2 (4.6) (4.7) g3 (k) = kTg1 (k) (4.8) g4 (k) = kTg2 (k). (4.9) 83 Chapter 4. Parameterization of Optimal Observer Trajectories Proof According to its definition [1], the FIM is given by Jp,v (U) = Ep(Z(U )|p) ∂ ∂T log(p(Z(U)|p)) log(p(Z(U)|p)) . ∂p ∂pp,v (4.10) where Z(U) = {z(k)}N k=1 is the measurement sequence and p(Z(U)|p) is the probability density of Z(U) conditioned on p. From (4.3), we note that N p(Z(U)|p) = 1 √ σ 2π k=1 v exp(− (z(k) − h(k))2 ). 2σv2 (4.11) By plugging (4.11) into (4.10) and following steps similar to those given in the proof of Lemma 2.2.1, the desired result can then be achieved. Considered separately, the dynamic models for the target and the observe can be fully specified only if N, T, xt (0), yt (0), xo (0), yo(0), Vxt , Vyt , Vo and sequence U = {u(k)}N−1 k=0 are known. However, when these models are considered together, by changing the coordinate system and writing the position of the target relative to the position of the observe, we only need to know N, T, R, Vt , Vo and sequence U = {u(k)}N−1 k=0 where R= (xt (0) − xo (0))2 + (yt (0) − yo (0))2 (4.12) 2 2 Vxt + Vyt . (4.13) and Vt = To this end, we construct a coordinate system following the arrangement shown in 84 Chapter 4. Parameterization of Optimal Observer Trajectories Figure 4.1. In this coordinate system, the origin is the initial position of the observer. The x axis is along the line that connecting the target to the observer at time instant 0 and the y axis is along the direction that the target travels. It is more convenient to prove our results in continuous domain. We, therefore, let the sampling time T approach zero in (4.5). By plugging (4.6) and (4.7) into (4.5), we can then express elements of Jp,v as 1 J11 (u) = 2 σv J22 (u) = J33 (u) = J44 (u) = 1 σv2 1 σv2 1 σv2 Tf t=0 Tf t=0 Tf t=0 Tf t=0 (Vt t − yo (t))2 dt ((R − xo (t))2 + (Vt t − yo(t))2 )2 (R − xo (t))2 dt ((R − xo (t))2 + (Vt t − yo(t))2 )2 t2 (Vt t − yo (t))2 dt ((R − xo (t))2 + (Vt t − yo(t))2 )2 t2 (R − xo (t))2 dt ((R − xo (t))2 + (Vt t − yo(t))2 )2 J12 (u) = J21 (u) = − J13 (u) = J31 (u) = J24 (u) = J42 = 1 σv2 1 σv2 1 σv2 Tf t=0 1 J34 (u) = J43 (u) = − 2 σv Tf t=0 Tf t=0 (Vt t − yo (t))(xt − xo (t)) dt ((R − xo (t))2 + (Vt t − yo (t))2 )2 t(Vt t − yo (t))2 dt ((R − xo (t))2 + (Vt t − yo (t))2 )2 t(R − xo (t))2 dt ((R − xo (t))2 + (Vt t − yo (t))2 )2 Tf t=0 t2 (Vt t − yo (t))(xt − xo (t)) dt ((R − xo (t))2 + (Vt t − yo (t))2 )2 (4.14) (4.15) (4.16) (4.17) (4.18) (4.19) (4.20) (4.21) J14 (u) = J41 (u) = J23 (u) = J32 (u) = 1 − 2 σv Tf t=0 t(Vt t − yo (t))(R − xo (t)) dt ((R − xo (t))2 + (Vt t − yo (t))2 )2 (4.22) where Tf denotes the observation period and the course control sequence U in discrete domain has been replaced with the course control function u in continuous domain. 85 Chapter 4. Parameterization of Optimal Observer Trajectories y Vo yo (k) Vt Observer h(k) Target k=0 x R yt (k) O k=0 xo (k) Figure 4.1: Geometry of bearings-only tracking by an observer. We can now formally define the trajectory design problem. Definition 4.2.1 The observer trajectory design problem in continuous domain for bearings-only tracking can be posed as solving max ψ(Jp,v (u)) such that dxo (t) = Vcos(u(t)) dt u dyo(t) = Vsin(u(t)), dt (4.23) xo (0) = yo (0) = 0 over the interval [0, Tf ] where the elements of Jp,v (u) are given by (4.14) to (4.22) and ψ is an appropriate function, e.g. the determinant, that assigns a real number to Jp,v (u). 86 Chapter 4. Parameterization of Optimal Observer Trajectories 4.3 Invariant Transformation of the Trajectory Design Problem We now define the range-to-baseline ratio and the speed ratio and prove that an optimal solution of problem (4.23) is invariant under a transformation that keeps these two ratios constant. However, prior to proving this result, we determine for what values of the range-to-baseline ratio and the speed ratio, the objective function of problem (4.23) is unbounded. These are the values for which the observer can reach the target over the observation period (see (4.14) to (4.22)). When the observer can reach the target, the optimal course control function is the one that produces this outcome and there is no need to solve the trajectory design problem. Definition 4.3.1 The range-to-baseline ratio in problem (4.23) is defined as CB = Vo Tf . R (4.24) Definition 4.3.2 The speed ratio in problem (4.23) is defined as CV = Vo . Vt (4.25) While we can specify for what combinations of Tf , R, Vt and Vo , the observer can reach the target during the observation period, the following proposition specifies such combinations in terms of CB and CV . 87 Chapter 4. Parameterization of Optimal Observer Trajectories Proposition 4.3.1 The objective function of problem (4.23) is only bounded in the following two cases: (i) 0 < CB < 1 and 0 < CV ≤ ∞ or (ii) CB ≥ 1 and 0 < CV < CB C2B − 1 . Proof Regardless of the value of the speed ratio, if Vo Tf < R, the observer can never cover the initial distance between itself and the target during the observation period and hence the first case is bounded. If, on the other hand, Vo Tf ≥ R and the observer can reach the target during the observation period, there must be some trajectory for which yo (Tf ) ≥ Vt Tf . The shortest path to achieve this goal is by traveling along the line that connects [0, 0] to [R, Vt Tf ]. Therefore, the objective function of the problem is bounded when Vt Tf > Vo Tf sin(θo ) (4.26) R = Vo Tf cos(θo ) (4.27) where θo = atan2(Vt Tf , R). The above relations yield 1 > CV 1− 1 C2B (4.28) which proves the second case. Figure 4.2 illustrates the values of the range-to-baseline ratio and the speed ratio for which the objective function of problem (4.23) is bounded. We are now ready to state the main result of this chapter. 88 Chapter 4. Parameterization of Optimal Observer Trajectories CV CV = CB C2B − 1 1 CB 1 Figure 4.2: Bounded region for the trajectory design problem. The shaded area indicates the values of CB and CV for which objective function of the trajectory design problem is bounded. Proposition 4.3.2 Consider two constant-velocity targets whose dynamic models are given by (4.1) and two observers whose dynamic models are given by (4.2). The first observer must estimate the position of the first target over the interval [0, T1 ] while it travels at the constant speed of Vo1 . Similarly, the second observer must estimate the position of the second target over the interval [0, T2 ] while it travels at the constant speed of Vo2 . Both observers start from the origin of the coordinate system and have identical measurement models given by (4.3). The initial distance of target 1 from observer 1 is R1 and the initial distance of target 2 from observer 2 is R2 . Targets 1 and 2 travel at the speed of Vt1 and Vt2 along the y axis, respectively. For a given function u defined over the absolute interval [0, 1], the course control function of observer 1 at time t is determined by u1 (t) = u(t/T1 ) and the course control function of observer 2 at time t is determined by u2 (t) = u(t/T2 ). Under these two scenarios, it then holds that for some constant K, Jp,v (u1 ) = KJp,v (u2 ) as long as the 89 Chapter 4. Parameterization of Optimal Observer Trajectories relation between R1 , R2 , Vt1 , Vt2 , Vo1 , Vo2 , T1 and T2 is such that Vo2 Vo1 = . Vt1 Vt2 Vo1 T1 Vo2 T2 = and R1 R2 Proof We prove that the result holds for the first elements of Jp,v (u1 ) and Jp,v (u2 ). A similar argument can be then pursued for other elements. Instead of working with two different time scales, we re-parameterize the trajectories of both observers as follows dxo1 (ξ) = Vo1 T1 cos(u(ξ)), dξ dyo1 (ξ) = Vo1 T1 sin(u(ξ)), dξ xo1 (0) = yo1 (0) = 0, (4.29) dxo2 (ξ) = Vo2 T2 cos(u(ξ)), dξ dyo2 (ξ) = Vo2 T2 sin(u(ξ)), dξ xo2 (0) = yo2 (0) = 0 (4.30) where [xo1 (ξ), yo1(ξ)] and [xo2 (ξ), yo2(ξ)] denote the positions of observers 1 and 2 for a given ξ ∈ [0, 1]. We then note that ξ xo2 (ξ) = Vo2 T2 cos(u(α) + u(0))dα = 0 ξ yo2 (ξ) = 0 Vo2 T2 xo1 (ξ) Vo1 T1 Vo2 T2 Vo2 T2 sin(u(α) + u(0))dα = yo1 (ξ). Vo1 T1 90 (4.31) Chapter 4. Parameterization of Optimal Observer Trajectories Therefore, the first element of Jp,v (u2 ) can be expressed as 1 σv2 T2 (Vt2 t − yo2 (t))2 dt T2 = 2 2 2 2 σv t=0 ((R2 − xo2 (t)) + (Vt2 t − yo2 (t)) ) T2 = 2 σv = = = 1 ξ=0 o2 T2 R − (( V Vo1 T1 1 2 Vo1 T21 2 Vo2 T2 σv2 2 Vo1 T1 2 Vo2 T2 σv2 T1 K σv2 t=0 1 ξ=0 T1 t=0 o2 T2 (V V T ξ− Vo1 T1 t1 1 Vo2 T2 x (ξ))2 Vo1 T1 o1 + 1 (Vt2 T2 ξ − yo2 (ξ))2 dξ 2 2 2 ξ=0 ((R2 − xo2 (ξ)) + (Vt2 T2 ξ − yo2 (ξ)) ) Vo2 T2 y (ξ))2 dξ Vo1 T1 o1 Vo2 T2 o2 T2 (V V T ξ−V yo1 (ξ))2 )2 Vo1 T1 t1 1 o1 T1 (Vt1 T1 ξ − yo1 (ξ))2 dξ ((R1 − xo1 (ξ))2 + (Vt1 T1 ξ − yo1 (ξ))2)2 (Vt1 t − yo1 (t))2 dt ((R1 − xo1 (t))2 + (Vt1 t − yo1 (t))2 )2 (Vt1 t − yo1 (t))2 dt ((xt1 − xo1 (t))2 + (Vt1 t − yo1 (t))2 )2 (4.32) where we have used (4.31) and the fact that the range-to-baseline ratio and the speed ratio are constant to prove the desired result. As a result of the above proposition, if a course control function is an optimal solution of problem (4.23) with T1 , R1 , Vt1 and Vo1 , it is also an optimal solution of problem (4.23) with T2 , R2 , Vt2 and Vo2 . It must be only ensured that the function is applied over the appropriate time scale. Remark By following similar steps, we can show that the FIM for estimating the position of a stationary target when the course control function u is applied can be expressed as J11 J12 Jp (u) = J12 J22 (4.33) Vt =0 where J11 , J22 and J12 are given by (4.14), (4.15) and (4.18), respectively. Hence, 91 Chapter 4. Parameterization of Optimal Observer Trajectories Proposition 4.3.2 also implies that the optimal course control function for bearingsonly localization is uniquely specified by the range-to-baseline ratio. Note, however, that the optimal course control function for estimating just the position of a stationary target is different than the optimal course control function for estimating both the position and the velocity of that target (see Figures 4.3 and 4.4). In both cases, the target is stationary but we are certain about this fact only in the first case. The first case involves finding a function that maximize a scalar function of Jp (u) whereas the second case involves finding a function that maximize a scalar function of Jp,v (u). Although we have shown that the optimal solutions of problem (4.23) can be specified by the range-to-baseline ratio and the speed ratio, it is still not possible to obtain closed-form expressions for these solutions and one has resort to numerical methods for computing them. To this end, we can restrict the admissible course control functions to those which can be represented by a partial sum of the Chebyshev polynomials [24], i.e. for a given integer Q, function u can be written as Q mi fi (t), u(t) = (4.34) i=0 where f0 (t) = 1, f1 (t) = t, (4.35) fi (t) = 2tfi−1 (t) − fi−2 (t). 92 Chapter 4. Parameterization of Optimal Observer Trajectories 600 400 200 Target → y 0 -200 CB = 0.10 CB = 0.20 CB = 0.90 CB = 0.30 CB = 0.80 CB = 0.40 CB = 0.70 CB = 0.50 CB = 0.60 -400 -600 -800 0 500 1000 1500 2000 x 2500 3000 3500 4000 Figure 4.3: Observer trajectories for bearings-only tracking when the target is stationary (CV = ∞). We can then find coefficients m∗1 , m∗2 , · · · , m∗Q that maximize the objective function of problem (4.23) for the given values of CB and CV . Figure 4.3 illustrates the trajectories that are generated based on using the first 7 Chebyshev polynomials when CV = ∞ and CB varies from 0 to 1, i.e. over the range that the objective function of problem (4.23) is bounded. These trajectories are computed with considering the determinant of the FIM as the objective function of problem (4.23). Since CV = ∞, these trajectories are for a stationary target. Following our earlier remark, however, note that in computing these trajectories, it is assumed that both the position and the velocity of the target are being estimated, i.e. these trajectories are for bearings-only tracking. The trajectories suggest that the observer must visit both half-planes of the plane below and above the x axis in 93 Chapter 4. Parameterization of Optimal Observer Trajectories 200 Target → 0 -200 y -400 CB = 0.10 CB = 0.90 -600 -800 CB = 0.20 CB = 0.80 CB = 0.30 -1000 CB = 0.70 CB = 0.40 CB = 0.50 CB = 0.60 -1200 -1400 0 500 1000 1500 2000 x 2500 3000 3500 4000 Figure 4.4: Observer trajectories for bearings-only localization (CV = ∞). order to obtain an accurate estimate of the velocity of the target. Compare these trajectories with those shown in Figure 4.4 where the target is still assumed to be stationary but only its position is being estimated, i.e. these trajectories are for bearings-only localization. They suggest that the target does not need to visit both half-planes of the plane below and above the x axis for bearings-only localization. A general trend is also seen in these trajectories. In the early stages of the observation period, the observer attempts to move directly towards the target and reduces its distance with the target. However, as we approach the final stages of the observation period, the observer changes its course and attempts to generate more diversity in bearing measurements. 94 Chapter 4. Parameterization of Optimal Observer Trajectories 6000 4000 CB = 1.00 3000 CB = 0.75 y 5000 Target ↓ CB = 1.25 CB = 0.50 2000 CB = 1.25 1000 CB = 1.00 CB = 0.75 0 CB = 0.25 -1000 CB = 0.25 0 500 CB = 0.5 1000 1500 2000 2500 3000 3500 4000 4500 5000 x Figure 4.5: Observer trajectories for bearings-only tracking when the target and the observer are traveling at the same speed (CV = ∞). The dots indicate the position of the target at the end of the observation period for a given value of the range-tobaseline ration. Figure 4.5 also illustrates the trajectories when CV = 1 and CB varies from 0.25 to 1.25. These trajectories have some similarities with those shown in Figure 4.3. However, since the target moves here, the observer attempts to pursue the target and maintain its distance from it low. Also, a sharp turn is more pronounced at the end of the trajectories. 4.4 Concluding Remarks In this chapter, we showed how the trajectory design problem for bearings-only tracking can be uniquely specified by only two ratios. Reducing the number of the parameters that the optimal solutions of a problem depends on can be greatly beneficial 95 Chapter 4. Parameterization of Optimal Observer Trajectories when only numerical solutions of that problem can be obtained. For the trajectory design problem, a family of optimal solutions can be generated based on the two discussed ratios and used for any scenario encountered in real-world applications. 96 Chapter 5 Conclusion 5.1 Summary of Work Accomplished With recent advances in embedded processors, microelectromechanical systems and wireless technology, it can be only expected that the world becomes a more instrumented place. As the applications for sensors broaden, new challenges also arise on how to manage the operation of these devices. In this dissertation, we explored several important themes on this subject. In particular, we studied the sensor subset selection problem for fixed sensors and the trajectory design problem for mobile sensors. We highlighted some of the characteristics of these problems that can be exploited in the development of more efficient solution algorithms. In connection with the sensor subset selection problem, we also proposed a novel approach to quantify how informative a sensor is relative to other sensors. For the sensor subset selection problem, we mainly focused on the determinant of the FIM as the metric of estimation accuracy. As a combinatorial optimization problem, we studied two well-known upper bounds for this problem: (i) the Lagrangian bound and (ii) the continuous bound. We showed that the determinant of the FIM 97 Chapter 5. Conclusion is a supermodular function from which it followed that the Lagrangian bound for the sensor subset selection problem can be computed in polynomial time. We outlined an algorithm for computing this bound. We further noted that the continuous relaxation of the sensor subset selection problem can be transformed to a convex optimization problem from which it followed that the continuous bound can be computed in polynomial time as well. Through numerical results and by comparing its performance with the continuous bound, we showed that a greedy algorithm is very efficient for solving the sensor subset selection problem. We pointed to the benefit of using the natural selection process to solve the continuous relaxation of a variation of the sensor subset selection problem where sensors are allowed to make more than one measurement. Motivated by the concept of probabilistic symmetric values in cooperative game theory, we introduced a power index for sensors to identify which ones are more informative than others. We proved that the power index can be computed in polynomial time if the determinant of the FIM is chosen as the metric of estimation accuracy. We derived formulas to compute the power indices for various probability distributions over the size of the selected subset. We discovered that if the parameter with the unknown value has only two elements and the measurement from a single sensor cannot provide information on both elements of the parameter simultaneously, the power indices induce the same ranking among the sensors regardless of the probability distribution considered for the size of the selected subset. Finally, we provided formulas 98 Chapter 5. Conclusion to compute the power indices for range and bearing (angle) sensors. Interestingly enough, we discovered that these formulas have very similar structures as each type reveals information about one dimension of the target’s position that the other type misses. For the trajectory design problem, we recognized that the optimal solutions of this problem can be uniquely specified by the range-to-baseline ratio and the speed ratio. We noted the range of these values that bounds the trajectory design problem. We also numerically investigated the characteristics of the optimal solutions of the trajectory design problem by approximating these solutions with a partial sum of the Chebyshev polynomials. 5.2 Directions for Future Work Here we present some directions and recommendations for future research. 1. Alternative upper bounds for the sensor subset selection problem: In addition to the Lagrangian and continuous bound, there are other upper bounds for combinatorial optimization problems. These upper bounds are, in general, tighter than the bounds we discussed but they are also more difficult to compute. We noted that the sensor subset selection problem is a non-linear (supermodular) knapsack problem. There are at least two types of alternative bounds that have been studied in the literature for the quadratic knapsack problem (see [15] and references therein). These bounds can be further investigated in the context of the sensor subset selection 99 Chapter 5. Conclusion problem which is more general than the quadratic knapsack problem. One alternative bound is obtained from the Lagrangian decomposition of the quadratic knapsack problem where extra variables are injected such that the dual function can be written in two parts. From these two parts, one can be solved in polynomial time. The effort can then be concentrated on solving the other part. There are also bounds proposed based on the idea of upper planes where the quadratic objective function is replaced with a linear one that is larger everywhere in the feasible region. One interesting question related to these bounds for the sensor subset selection problem asks how the coefficients of the linear function can be determined directly from the parameters of the problem such as the positions of sensors and the target. 2. Power indices of sensors in dynamic scenarios: It is interesting to investigate how a power index can be defined and computed in dynamic scenarios. In Chapter 3, we analyzed the power indices of sensors for tracking a target (see Section 3.4.2). However, we assumed that the same selected subset remains active during the entire observation period. It is, in fact, more realistic to assume that this subset will change as time passes. One approach for defining and computing the power index in dynamic scenarios can be established by considering a sequence of cooperative parameter estimation games which are parameterized by the position of the target at a given time instant. We then define the value of a subset as the sum of its value in each individual game and compute the power index based on that. This approach resembles the work discussed in [63] on dynamic cooperative games and 100 Chapter 5. Conclusion their solution concepts. 3. Symmetry analysis of the trajectory design problem: The results that we obtained in Chapter 4 can be potentially used as a basis for the symmetry analysis [64] of the trajectory design problem. The parameterization of the optimal solutions of the trajectory design problem, in fact, points to the symmetries of this problem. As we saw, these symmetries reduced the complexity of the problem. The analysis of these or other symmetries can eventually lead to further insight into the characteristics of the optimal solutions. 4. Multiple Targets/Mutiple Observers: A natural extension to what we discussed in Chapters 2 and 3 is to consider estimating multiple parameters, i.e. the position of multiple targets. For multiple parameters, various formulations of the sensor subset selection problem may arise depending how we assume the sensors make their measurements and how the constraints of the problem are set up. Similarly, we can analyze how to parameterize the optimal solutions of the trajectory design problem if multiple targets or observers exist. 101 Bibliography [1] H. L. V. Trees, Detection, Estimation, and Modulation Theory. John Wiley, 1968. [2] S. M. Kay, Fundamentals of Statistical Signal Processing: Estimation Theory. Prentice Hall, 1993. [3] Y. Bar-Shalom, X. R. Li, and T. Kirubarajan, Estimation with Applications to Tracking and Navigation. John Wiley & Sons, 2001. [4] B. Ristic, S. Arulampalam, and N. Gordon, Beyond the Kalman Filter: Particle Filters for Tracking Applications. Artech House, 2004. [5] M. Chu, H. Haussecker, and F. Zhao, “Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks,” International Journal of High Performance Computing Applications, vol. 16, no. 3, pp. 293–314, 2002. [6] P. Tichavsky, C. H. Muravchik, and A. Nehorai, “Posterior Cramer-Rao bounds for discrete-time nonlinear filtering,” IEEE Transactions on Signal Processing, vol. 46, no. 5, pp. 1386–1396, 1998. 102 Bibliography [7] S. P. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [8] F. Pukelsheim, Optimal Design of Experiments. SIAM, 2006. [9] D. P. Bertsekas, Dynamic Programming and Optimal Control. Athena Scientific, 2000. [10] J. Evans and V. Krishnamurthy, “Optimal sensor scheduling for hidden Markov model state estimation,” International Journal of Control, vol. 74, no. 18, pp. 1737–1742, 2001. [11] V. Krishnamurthy, “Algorithms for optimal scheduling and management of hidden Markov model sensors,” IEEE Transactions on Signal Processing, vol. 50, no. 6, pp. 1382–1397, 2002. [12] L. Meier, J. P. Peschon, and R. M. Dressler, “Optimal control of measurement subsystems,” IEEE Transactions on Automatic Control, vol. 12, no. 5, pp. 528– 536, 1967. [13] A. Athans, “On the determination of optimal costly measurement strategies for linear stochastic systems,” Automatica, vol. 8, pp. 397–412, 1972. [14] T. Ibaraki and N. Katoh, Resource Allocation Problems. MIT Press, 1988. [15] D. Li and X. Sun, Nonlinear Integer Progamming. Springer-Verlag, 2006. 103 Bibliography [16] L. A. Wolsey and G. L. Nemhauser, Integer and Combinatorial Optimization. Wiley-Interscience, 1999. [17] G. Gallo and B. Simeone, “On the supermodular knapsack problem,” Mathematical Programming, vol. 45, no. 1-3, pp. 295–309, 1989. [18] M. Groetschel, L. Lovasz, and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,” Combinatorica, vol. 1, pp. 169–197, 1981. [19] C. C. Li, First Course in Population Genetics. Boxwood Press, 1976. [20] D. Monderer and D. Samet, “Variations on the Shapley value,” in Handbook of Game Theory with Economic Applications, R. Aumann and S. Hart, Eds. Elsevier Science, 2002, vol. 3, ch. 54, pp. 2055–2076. [21] X. Deng and C. H. Papadimitriou, “On the complexity of cooperative solution concepts,” Mathematics of Operations Research, vol. 90, no. 2, pp. 257–266, 1994. [22] J. Banzhaf, “Weighted voting doesn’t work: a mathematical analysis,” Rutgers Law Review, vol. 19, pp. 317–343, 1965. [23] L. S. Shapley and M. Shubik, “A method for evaluating the distribution of power in a committee system,” American Political Science Review, vol. 48, pp. 787–792, 1954. [24] R. L. Burden and J. D. Faires, Numerical Analysis. Brooks Cole, 2004. 104 Bibliography [25] S. E. Hammel, P. T. Liu, E. J. Hillard, and K. F. Fong, “Optimal observer motion for localization with bearing measurements,” Computers and Mathematics with Applications, vol. 18, no. 1-3, pp. 171–180, 1989. [26] F. Zhao, J. Shin, and J. Reich, “Information-driven dynamic sensor collaboration,” IEEE Signal Processing Magazine, vol. 16, pp. 293–313, 2002. [27] J. Liu, J. Reich, and F. Zhao, “Collaborative in-network processing for target tracking,” EURASIP Journal on Applied Signal Processing, vol. v 2003, no. 4, pp. 378–391, 2003. [28] H. Wang, G. Pottie, K. Yao, and D. Estrin, “Entropy-based sensor selection heuristic for target localization,” in Proceedings of International Symposium on Information Processing in Sensor Networks, Berkeley, California, 2004. [29] L. Kaplan, “Global node selection for localization in a distributed sensor network,” IEEE Transactions on Aerospace and Electronic Systems, vol. 42, no. 1, pp. 113–135, 2006. [30] ——, “Local node selection for localization in a distributed sensor network,” IEEE Transactions on Aerospace and Electronic Systems, vol. 42, no. 1, pp. 136–146, 2006. [31] R. Tharmarasa, T. Kirubarajan, and M. L. Hernandez, “Large-scale optimal sensor array management for multitarget tracking,” IEEE Transactions on Systems, Man and Cybernetics, Part C, vol. 37, no. 5, pp. 803–814, 2007. 105 Bibliography [32] A. Krause and C. Guestrin, “Near-optimal nonmyopic value of information in graphical models,” in Proceedings of Uncertainty in Artificial Intelligence, Edinburgh, Scotland, 2005. [33] M. Cardei and D. Du, “Improving wireless sensor network lifetime through power-aware organization,” vol. 11, no. 3, pp. 233–340, 2005. [34] M. L. Hernandez, T. Kirubarajan, and Y. Bar-Shalom, “Multisensor resource deployment using posterior cramer-rao bounds,” IEEE Transactions on Aerospace and Electronic Systems, vol. 40, no. 2, pp. 399–416, 2004. [35] A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies,” Journal of Machine Learning Research, vol. 9, pp. 235–284, 2008. [36] H. Rowaihy, S. Eswaran, M. Johnson, D. Verma, A. Bar-Noy, T. Brown, and T. La Porta, “A survey of sensor selection schemes in wireless sensor networks,” in Proceedings of SPIE, vol. 6562, no. 65621A1, 2007. [37] A. Chhetri, D. Morell, and A. Papandreou-Supapola, “Sensor scheduling using a 0-1 mixed integer programming framework,” in Proceedings of IEEE Workshop on Sensor Array and Multichannel Processing, Waltham, MA, 2006. [38] Z. Han and H. V. Poor, “Coalition games with cooperative transmission: a cure for the curse of boundary nodes in selfish packet-forwarding wireless networks,” 106 Bibliography in Proceedings of International Symposium on Modeling and Optimization in Mobile, Ad Hoc,and Wireless Networks, Limassol, Cyprus. [39] M. Madiman, “Cores of cooperative games in information theory,” EURASIP Journal on Wireless Communications and Networking, no. 318704, 2008. [40] J. C. Hassab, Underwater Signal and Data Processing. CRC Press, 1989. [41] S. Blackman and R. Popoli, Design and Analysis of Modern Tarcking Systems. Artech House, 1999. [42] S. E. Hammel and V. J. Aidala, “Observability requirements for threedimensional tracking via angle measurements,” IEEE Transactions on Aerospace and Electronic Systems, vol. 21, no. 2, pp. 200–207, 1985. [43] E. Fogel and M. Gavish, “Nth-order dynamics target observability from angle measurements,” IEEE Transactions on Aerospace and Electronic Systems, vol. 24, no. 3, pp. 305–308, 1988. [44] R. R. Mohler and C. S. Hwang, “Nonlinear data observability and information,” Journal of the Franklin Institute, vol. 325, no. 4, pp. 443–464, 1988. [45] K. Becker, “Simple linear theory approach to tma observability,” IEEE Transactions on Aerospace and Electronic Systems, vol. 29, no. 2, pp. 575–578, 1993. 107 Bibliography [46] T. L. Song, “Observability of target tracking with bearings-only measurements,” IEEE Transactions on Aerospace and Electronic Systems, vol. 32, no. 4, pp. 1468–1472, 1996. [47] P. Shar and X. R.Li, “A practical approach to observability of bearings-only target tracking,” in Proceedings of SPIE Conference on Signal and Data Processing of Small Targets, Denver, Colorado, 1999. [48] J. A. Fawcett, “Effect of course maneuvers on bearings-only range tracking,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 36, no. 8, pp. 1193–1199, 1988. [49] J. P. Helferty and D. R. Mudgett, “Optimal observer trajectories for bearingsonly tracking by minimizing the trace of the cramer-rao lower bound,” in Proceedings of IEEE Conference on Decision and Control, San Antonio, Texas, 1993. [50] A. Logothetis, A. Isaksson, and R. Evans, “An information theoretic approach to observer path design for bearings-only tracking,” in Proceedings of IEEE Conference on Decision and Control, San Diego, California, 1997. [51] A. Logothetis, A. Isaksson, and R. J. Evans, “Comparison of suboptimal strategies for optimal own-ship maneuvers in bearings-only tracking,” in Proceedings of American Control Conference, Philadelphia, Pennsylvania, 1998. 108 Bibliography [52] Y. Oshman and P. Davidson, “Optimization of observer trajectories for bearingsonly target localization,” IEEE Transactions on Aerospace and Electronic Systems, vol. 35, no. 3, pp. 892–902, 1999. [53] O. Tr´emois and J.-P. L. Cadre, “Optimal observer trajectory in bearings-only tracking for manoeuvring sources,” IEE Proceedings of Radar, Sonar and Navigation, vol. 146, no. 1, pp. 31–39, 1999. [54] M. Herdandez, “Optimal sensor trajectories in bearings-only tracking,” in Proceedings of International Conference on Information Fusion, Stockholm, Sweden, 2004. [55] E. W. Frew and S. M. Rock, “Exploratory motion generation for monocular vision-based target localization,” in Proceedings of IEEE Aerospace Conference, 2002. [56] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley- Interscience, 1991. [57] D. M. Topkis, Supermodularity and Complementarity. Princeton University Press, 1998. [58] F. Zhang, Matrix Theory. Springer-Verlag, 1999. [59] S. Fujishige, Submodular Functions and Optimization. Elsevier, 1991. 109 Bibliography [60] T. S. Motzkin and E. G. Straus, “Maxima for graphs and a new proof of a theorem of Tu´ran,” Canadian Journal of Mathematics, vol. 17, pp. 533–540, 1965. [61] I. M. Bomze and V. Stix, “Genetic engineering via negative fitness: Evolutionary dynamics for global optimization,” Annals of Operations Research, vol. 89, pp. 297–318, 1999. [62] J. F. C. Kingman, “On an inequality in partial averages,” Quarterly Journal of Mathematics, vol. 12, pp. 78–80, 1961. [63] J. A. Filar and L. A. Petrosjan, “Dynamic cooperative games,” International Game Theory Review, vol. 2, no. 1, pp. 47–65, 2000. [64] G. Bluman, Symmetry and Integration Methods for Differential Equations. Springer-Verlag, 2002. 110
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Sensor management with applications in localization...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Sensor management with applications in localization and tracking Ghassemi, Farhad 2009
pdf
Page Metadata
Item Metadata
Title | Sensor management with applications in localization and tracking |
Creator |
Ghassemi, Farhad |
Publisher | University of British Columbia |
Date Issued | 2009 |
Description | In this dissertation, we explore several themes in sensor management with an emphasis on their applications for target localization and tracking. We consider the sensor subset selection problem where a pre-specified number of sensors must be selected in a sensor network to estimate an unknown value of a time-invariant parameter, e.g. the position of a target. We study the Lagrangian and continuous relaxations of this problem with the determinant of the Fisher information matrix as the objective function. We prove that the continuous bound is tighter than the Lagrangian bound and outline an algorithm based on the so-called natural selection process to compute the continuous bound when sensors are allowed to make more than one measurement. We also study how a target can identify the informative sensors when it is facing a network that attempts to estimate its position or its other critical parameters. We show that by borrowing the notion of symmetric probabilistic values from cooperative game theory, the target can assign a power index to each sensor to determine how informative it is relative to the other ones. We further show that by choosing the determinant of the Fisher information matrix as the metric of estimation accuracy, the computational complexity associated with a power index gracefully increases with the number of sensors. Finally, we study the trajectory design problem for bearings-only tracking where the motion of a mobile sensor, called the observer, must be planned in order to estimate the position and the velocity of a moving target via bearing measurements. Our analysis of this problem demonstrates that the optimal solutions can be uniquely specified by only two ratios: (i) The distance that the observer can travel along a straight line during the observation period to the relative distance between the observer and the target. (ii) The speed of the observer relative to the speed of the target. |
Extent | 532970 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-07-02 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
IsShownAt | 10.14288/1.0067304 |
URI | http://hdl.handle.net/2429/9964 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2009-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2009_fall_ghassemi_farhad.pdf [ 520.48kB ]
- Metadata
- JSON: 24-1.0067304.json
- JSON-LD: 24-1.0067304-ld.json
- RDF/XML (Pretty): 24-1.0067304-rdf.xml
- RDF/JSON: 24-1.0067304-rdf.json
- Turtle: 24-1.0067304-turtle.txt
- N-Triples: 24-1.0067304-rdf-ntriples.txt
- Original Record: 24-1.0067304-source.json
- Full Text
- 24-1.0067304-fulltext.txt
- Citation
- 24-1.0067304.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0067304/manifest