Towards an understanding of the impact of dependent blocking on localization performance

2018-07-29The ability to accurately determine the location of (i.e., localize) one or more targets remotely is an essential requirement for many applications, such as navigation, search-and-rescue operations etc. The canonical localization problem involves estimating the target locations in an environment by analyzing wireless signals emanating from them at a collection of known anchor locations. If the targets transmit their own signals, it is referred to as active localization; on the other hand, if the targets only reflect the incoming signals from the anchors (e.g., tumors in medical imaging), it is referred to as passive localization. In either case, localization typically involves the following two steps: (a) Ranging: In this step, each anchor obtains an estimate of its round-trip distance (or range) or bearing to each target using a location-dependent feature of the received signal, such as time-of-arrival, signal strength or angle-of-arrival. (b) Multilateration or Triangulation: Once all the range and/or bearing estimates are available at the anchor locations, they are combined to obtain position estimates for all the targets in this step. ❧ Throughout this dissertation, we assume time-of-arrival based ranging and subsequent localization. To obtain accurate range estimates, it is desirable for the direct paths (DPs) from the anchors to the targets (i.e., going from a transmitter and reflecting off a target to a receiver) to be unblocked. However, in many environments (especially indoors), obstacles in the environment (such as walls) can cause the DPs to be blocked. If the obstacle locations are unknown, then the blocking of the DPs can be modeled as a stochastic phenomenon which influences both the design of localization networks - in terms of determining the number of anchors required, as well as their positions - and the performance of any localization algorithm in those networks. As a result, the accurate characterization of blocking is important for a network and algorithm design perspective. A common assumption is to consider the DP blocking events to be mutually independent. However, the distributed (i.e., non-point) nature of the obstacles induces a statistical dependence between the blocking of different DPs in general, with the extent of dependence being a function of the size of the obstacles, as well as the geometry of the links. This phenomenon is commonly referred to as correlated blocking or dependent blocking and we use both these terms interchangeably from here on. This dissertation, comprising five chapters, primarily focuses on modeling and understanding the dependent blocking phenomenon and presents some insights into its impact on localization performance. ❧ In Chapter 2, the impact of dependent blocking on the performance of localization algorithms is investigated. In particular, the problem of localizing an unknown number of passive (i.e., reflecting) targets by single antenna anchors that cannot determine directions of departure and arrival is addressed. In addition to dependent blocking, we also consider the presence of multipath propagation and assume that all the targets have the same radar signature. In its most general form, this problem can be cast as a Bayesian estimation problem, where the propagation path of every multipath component is also estimated, along with the target locations. However, when the environment map is unknown, this problem is ill-posed and hence, a tractable approximation is derived where only the DPs are identified. In this framework, the dependent blocking caused by distributed obstacles in the environment is modeled as a Bayesian prior. A sub-optimal polynomial-time algorithm to solve the Bayesian multi-target localization problem with dependent blocking is proposed and its performance evaluated using simulations and measurements. In particular, when the DP blocking events are highly dependent, assuming them to be independent and having a constant probability (as was done in previous papers) resulted in poor detection performance, with false alarms more likely to occur than detections. ❧ The impact of dependent blocking on localization network design is studied in Chapters 3 and 4. The blocking of DPs between anchors and targets by distributed obstacles in an environment can create blind spots in a localization network if there is an insufficient number of unblocked anchors. In Chapter 3, we characterize the blind spot probability of a network, using tools from stochastic geometry to model the spatial randomness of the obstacle and anchor locations. In particular, a homogeneous Poisson point process is used to model the anchor locations, while a germ-grain model is employed to represent the obstacle locations and shapes. Using this model, we first characterize the regime over which the independent blocking assumption underestimates the blind spot probability of the typical target, which in turn, is characterized as a function of the distribution of the unshadowed area, as seen from the target location. Since this distribution is difficult to characterize exactly, we formulate the nearest two-obstacle approximation, which is equivalent to considering the effects of dependent blocking for only the nearest two obstacles from the target, while assuming independent blocking due to the remaining obstacles. As nearby obstacles induce greater blocking correlation than farther ones, this approximation achieves a reasonable trade-off between accuracy and tractability. Based on this quasi-independent blocking assumption, we derive a closed form (approximate) expression for the blind spot probability, which helps determine the intensity with which anchors need to be deployed so that the blind spot probability at a typical target location is bounded by a pre-defined threshold. ❧ Even if a target is not situated in a blind spot, the localization mean square error (MSE) depends on the relative geometry of the anchors, i.e., the point process formed by the unblocked anchors, as seen from the target location. An outage occurs if the positioning error exceeds a pre-defined threshold. From a design perspective, characterizing the distribution of the positioning error over an ensemble of target and anchor locations is essential for providing probabilistic performance guarantees against outage. However, even for the simplest case where the anchors are deployed according to a Binomial point process and do not experience any blocking, this problem has remained unsolved. Hence, in Chapter 4, we tackle this open problem and derive a tractable approximation for the MSE distribution. Finally, some promising ideas for future work are proposed in Chapter 5 to conclude this dissertation