[MyResearch] Location and tracking system

I think the following paper should be considered as seminal in the field of estimating the position of a mobile device : P. Bahl and V. N. Padmanabhan, "Radar: An in-building rf-based user location and tracking system," In Proceedings of the IEEE Infocom 2000, Tel-Aviv, Israel, vol. 2, Mar. 2000, pp. 775--784. The authors provide the reader with a nice literature review of the existing location and tracking systems:

- Active Badge : a badge worn by a person emits a unique IR signal every 10 seconds. While this system provides accurate location information, it suffers from several drawbacks: (a) it scales poorly due to the limited range of IR, (b) it incurs significant installation and maintenance costs, and (c) it performs poorly in the presence of direct sunlight, which is likely to be a problem in rooms with windows. - cellular phones: involve measuring the signal attenuation, the angle of arrival (AOA), and/or the time difference of arrival (TDOA). While these systems have been found to be promising in outdoor environments, their effectiveness in indoor environments is limited by the multiple reflections suffered by the RF signal. - Systems based on the Global Positioning System, while very useful outdoors, are ineffective indoors because buildings block GPS transmissions.

They propose to use triangulation of the radio signal strength (expressed in unit of dBm) as a function of the user's location. Their methdology is the following :

Each base station (bs) records the signal strength (ss) measurement3 together with a synchronized timestamp t, i.e., it records tuples of the form (t, bs, ss). We collected signal strength information in each of the 4 directions at 70 distinct physical locations on our floor. For each combination of location and orientation (i.e., (x,y,d) tuple), we collected at least 20 signal strength samples. we merged all of the traces collected during the off-line phase into a single, unified table containing tuples of the form (x,y,d,ssi,snri), where I = {1, 2, 3} corresponding to the three base stations.

We consider a couple of approaches. The first is the empirical method where we use the location and SS data gathered during the off-line phase. We need a metric and a search methodology to compare multiple locations and pick the one that best matches the observed signal strength. We term our general technique nearest neighbor(s) in signal space (NNSS). The idea is to compute the distance (in signal space) between the observed set of SS measurements, (ss1,ss2,ss3), and the recorded SS, (ss’1,ss’2,ss’3), at a fixed set of locations, and then pick the location that minimizes the distance. In our analysis, we use the Euclidean distance measure, i.e., sqrt((ss1-ss’1)2+(ss2-ss’2)2+(ss3-ss’3)2). It is possible to use other distance metrics, for example, the sum of the absolute differences for each base station (the “Manhattan” distance) or a metric weighted by the signal strength level at each base station.