Analytical investigation of intersection based range-free localization

The localization of mobile devices is essential for the provisioning of location-based services, e.g., to locate people facing an accident or to provide relevant information to device users, depending on their current whereabouts. Several localization mechanisms have been developed using estimates of absolute distances or angles between the devices and the base stations of the networks. These mechanisms often require expensive enhancements of the existing base stations or mobile devices. In recent years, so-called range-free approaches have been proposed, which limit the possible positions of a device to the coverage areas of radio network cells, without relying on precise distances or angles. The accuracy of the corresponding information can be refined by computing the intersection area of all cells that cover the current position of the device. However, the computation of this intersection area, e.g., by the location server of a network carrier, can be a complex task. To avoid unnecessary workload, one would like to preestimate the possible reduction of location uncertainty, i.e., the information gain that can be achieved. The contribution of this paper is an analytical and numerical investigation of the problem. Several approaches are presented for the computation of the information gain, based on stochastic geometry and on a Monte-Carlo method. We show that simple scaling arguments can be used to estimate the order of magnitude of the average information gain, while more complex approximations based on Voronoi cells lead to relatively good results.