16-10-2012, 12:30 PM
CellSense: An Accurate Energy-Efficient GSM Positioning System
CellSense.pdf (Size: 569.78 KB / Downloads: 53)
Abstract
Context-aware applications have been gaining huge
interest in the last few years. With cell phones becoming ubiquitous
computing devices, cell phone localization has become
an important research problem. In this paper, we present
CellSense, which is a probabilistic received signal strength indicator
(RSSI)-based fingerprinting location determination system
for Global System for Mobile Communications (GSM) phones.We
discuss the challenges of implementing a probabilistic fingerprinting
localization technique in GSM networks and present the details
of the CellSense system and how it addresses these challenges.
We then extend the proposed system using a hybrid technique that
combines probabilistic and deterministic estimations to achieve
both high accuracy and low computational overhead. Moreover,
the accuracy of the hybrid technique is robust to changes in its parameter
values. To evaluate our proposed system, we implemented
CellSense on Android-based phones. Results from two different
testbeds, representing urban and rural environments, for three
different cellular providers show that CellSense provides at least
108.57% enhancement in accuracy in rural areas and at least
89.03% in urban areas compared with current state-of-the-art
RSSI-based GSM localization systems. In additional, the proposed
hybrid technique provides more than 6 and 5.4 times reduction
in computational requirements compared with state-of-the-art
RSSI-based GSM localization systems for rural and urban testbeds,
respectively. We also evaluate the effect of changing the
different system parameters on the accuracy–complexity tradeoff
and how the cell tower and fingerprint densities affect system
performance.
INTRODUCTION
AS CELL PHONES become more ubiquitous in our daily
lives, the need for context-aware applications increases.
One of the main context information is location, which enables
a wide set of cell phone applications including navigation,
location-aware social networking, and security. Although the
Global Positioning System (GPS) [2] is considered to be the
most well-known localization technique, it is not available in
many cell phones, requires direct line of sight to the satellites,
and consumes a lot of energy. Therefore, research for
other techniques for obtaining cell phone location has gained
momentum fueled by both the users’ need for location-aware
applications and government requirements, e.g., Federal Communications
Commission [3]. City-wide WiFi-based localization
for cellular phones has been investigated in [4] and [5], and
commercial products are currently available [6]. However,WiFi
chips, similar to GPS, are not available in many cell phones,
and not all cities in the world contain sufficient WiFi coverage
to obtain ubiquitous localization. Similarly, using augmented
sensors in cell phones, e.g., accelerometers and compasses,
for localization has been proposed in [7]–[9]. However, these
sensors are still not widely used in many phones.
Time-of-Arrival (ToA)-Based Localization
In ToA-based systems, the cell phone estimates its distance to
a reference point based on the time a signal takes to travel from
the reference point to it. Similarly, time-difference-of-arrivalbased
systems use the principle that the emitter location can
be estimated by the intersection of the hyperbolae of constant
differential ToA of the signal at two or more pairs of base
stations [3].
The most well-known localization technique, i.e., the GPS
[2], can be categorized as a ToA-based system. Time-based
systems require special hardware and therefore are usually deployed
on high-end phones. In addition, GPS suffers from two
other main problems: 1) availability and 2) power consumption.
It requires line of sight to the satellites; therefore, it does not
work indoors, and it consumes a lot of power of the energylimited
cell phones.
AOA-Based Systems
AOA-based systems use triangulation based on the estimated
AOA of a signal at two or more base stations to estimate
the location of the desired transmitter [3], [13]–[16]. Antenna
arrays are usually used to estimate the AOA. Similar to TOAbased
systems, AOA-based systems require specialized hardware,
which makes them less attractive for a large deployment
on cell phones.
RSSI-Based Systems
Recently, RSSI-based systems have been introduced and implemented
for cell phone localization. Since RSSI information
is readily available to the user’s applications on almost all
GSM phones, such systems have the potential of localizing
80–85% of today’s cell phones [10], work all over the world,
and consume minimal energy, in addition to standard cell phone
operation.
However, since RSSI is a complex function of distance [19],
RSSI-based systems usually require building an RF fingerprint
of the area of interest [5], [11], [12], [20]. A fingerprint stores
information about the RSSI received from different base stations
at different locations in the area of interest. This is usually
constructed once in an offline phase. During the tracking phase,
the received RSSI at an unknown location is compared with the
RSSI signatures in the fingerprint, and the closest location in the
fingerprint is returned as the estimated location. Constructing
the fingerprint is a time consuming process. However, this is
typically done in a process called war driving, where cars drive
the area of interest continuously scanning for cell towers and
recording the cell tower ID, RSSI, and GPS location. Current
commercial systems, such as Skyhook, Google MyLocation,
and StreeView services, already perform scanning for other
purposes. Therefore, constructing the fingerprint for GSM localization
can be piggybacked on these systems without extra
overhead.
Summary
Compared with TOA, AOA, city-wide WiFi, and augmented
sensor-based systems, our proposed system CellSense requires
no specialized hardware and is more ubiquitous in terms of the
number of cell phones it runs on and the coverage area.
Compared with cell-ID based systems and the current fingerprinting
techniques, our technique is probabilistic. Using a
probabilistic approach should enhance the accuracy of localization
compared with a deterministic approach. However, it
comes with its own challenges, such as constructing the RSSI
probability distribution with minimal overhead. Our proposed
technique addresses these challenges and provides accuracy
better than all of the current techniques with minimal computational
requirements, as we quantify in Section IV.
CELLSENSE SYSTEM
In this section, we describe our CellSense system for GSM
phone localization. We start by an overview of the system followed
by the details of the offline training and online tracking
phases. Finally, we propose a hybrid approach that combines
the basic CellSense and a deterministic approach to achieve
both accurate localization and low computational overhead.
CONCLUSION
We have proposed CellSense, which is a probabilistic RSSIbased
fingerprinting approach for GSM cell phone localization.
We presented the details of the system and how it constructs
the probabilistic fingerprint without incurring any additional
overhead. We also proposed a hybrid approach that combines
probabilistic and deterministic techniques to achieve both high
accuracy and low computational requirements.
We implemented our system on Android-based phones and
compared it to other GSM-localization systems under two
different testbeds. Our results show that the CellSense-Hybrid
technique accuracy is better than other techniques with at least
108.57% in rural areas and at least 89.03% in urban areas
with more than 5.4 times savings in running time compared
with state-of-the-art RSSI-based GSM localization techniques.
We also studied the effect of different parameters on the performance
of the system and how the cell tower density and
fingerprint density affect accuracy.