ECOPS: Energy-Efficient Collaborative Opportunistic Positioning for Heterogeneous Mobile Devices

Abstract

The fast growing popularity of smartphones and tablets enables us to use various intelligent mobile applications. As many of those applications require position information, smart mobile devices provide positioning methods such as Global Positioning System (GPS), WiFi-based positioning system (WPS), or Cell-ID-based positioning service. However, those positioning methods have different characteristics of energy-efficiency, accuracy, and service availability. In this paper, we present an Energy-Efficient Collaborative and Opportunistic Positioning System (ECOPS) for heterogeneous mobile devices. ECOPS facilitates a collaborative environment where many mobile devices can opportunistically receive position information over energy-efficient and prevalent WiFi, broadcasted from a few other devices in the communication range. The position-broadcasting devices in ECOPS have sufficient battery power and up-to-date location information obtained from accurate but energy-inefficient GPS. A position receiver in ECOPS estimates its location using a combination of methods including received signal strength indicators and 2D trilateration. Our field experiments show that ECOPS significantly reduces the total energy consumption of devices while achieving an acceptable level of location accuracy. ECOPS can be especially useful for unique resource scarce, infrastructureless, and mission critical scenarios such as battlefields, border patrol, mountaineering expeditions, and disaster area assistance.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Kaustubh Dhondge 1 and Hyungbae Park 1 and Baek-Young Choi 1 and Sejun Song 2

Recommended by Lingjia Liu

1, University of Missouri-Kansas City, 546 Flarsheim Hall, 5110 Rockhill Road, Kansas City, MO 64110, USA
2, Texas A&M University, Fermier Hall 008, 3367 TAMU, College Station, TX 77843, USA

Received 16 June 2012; Revised 12 October 2012; Accepted 19 November 2012

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Smart mobile devices such as smartphones and tablets are rapidly becoming prevalent in our lives. They have spurred a paradigm shift from traditional restricted phone applications to intelligent mobile applications such as location-based, context-aware, and situation-aware services. For example, a social-network-based traffic information system [ 1] allows each mobile user to report and use real-time traffic information, in addition to the archived traffic information from the US Department of Transportation.

As many of those application services require position information, smart mobile devices provide various positioning services via Global Positioning System (GPS) [ 2], WiFi-based positioning system (WPS) [ 3], or Cell-ID Positioning [ 4]. Being dedicated equipment for positioning, GPS becomes available for many smart devices as an additional feature and is considered to be an accurate and preferred method for location-based services (LBSs) [ 5, 6]. However, its high energy consumption, due to the Time To First Fix (TTFF), becomes a significant drawback. WPS approximates a position from the location information of a nearby wireless access point (AP) that is stored in the database. Its energy efficiency is much better than GPS, and the accuracy is moderate. As WiFi is a de facto standard in wireless local area network (WLAN) communication, it is broadly available on most smart devices. However, the service is limited to indoor or urban areas where the access points are densely populated. Cell-ID Positioning provides an approximate location from the serving cell tower, where a cell area range is around 100 ~ 500 m in urban areas, but it can span up to 10 Km for rural areas. Although this is the most power saving approach, due to a large error range caused by the coarse cell tower density, Cell-ID Positioning cannot offer the utility of most LBS applications. In addition, mobile devices such as the WiFi version of tablets are not fully equipped with 3G/4G data chips at the present time even though 3G and 4G wireless networks provide enough bandwidth to enable explicit support for real-time LBS. We have summarized the characteristics of positioning methods ([ 7]) in Table 1.

Table 1: Characterization of various positioning methods.

Positioning method	Accuracy	Energy efficiency	Equipment availability	Service limitations
GPS	High (within 10 m)	Low	Low	Indoor and canyon
WPS	Moderate (within 50 m)	Moderate	High	Coarse AP density area
Cell-ID Positioning	Low (within 5 Km)	High	Moderate	Rural area

Energy efficiency while maintaining required accuracy for the given service limitations is one of the most critical issues in mobile devices, due to limited battery life and the high energy consumption of applications. As different positioning methods available on a mobile device have different characteristics with respect to accuracy, energy-efficiency, and service availability, there have been several proposals for dynamic selection of a positioning method on an individual device. For example, [ 8] uses an accelerometer for movement detection to power cycle GPS, if the device is not mobile. However, the effectiveness of most of the existing heuristics is limited by equipment constraints or service availability, as the applications choose a preferred positioning method that is available within an individual device.

In this paper, we propose ECOPS to facilitate a WiFi hotspot mode [ 9] or WiFi Direct mode [ 10] based approximation in collaboration with a few available GPS broadcasting devices under budget constraints. ECOPS is a collaborative positioning method between WiFi and GPS mobile devices, in addition to a positioning method selection heuristic within a mobile device. It can achieve moderate accuracy with low energy usage. Although there is a previous collaborative work [ 8] that pairs two devices via Bluetooth to save GPS power cycle, the approach needs both GPS and Bluetooth on both devices. Instead, ECOPS supports heterogeneous methods among mobile devices. There are many mobile devices including the majority of current tablets that only support a basic wireless communication method which is WiFi. The WiFi-only device can obtain position information from a GPS device with ECOPS. This proposed system can operate opportunistically, where each device can resolve the location via various available methods including trilateration [ 11] with three GPS broadcasting devices and a received signal strength indicator (RSSI) [ 12] or approximation with geomagnetic sensors [ 13] and a single GPS device without requiring any WiFi AP.

We implemented ECOPS using Android-powered mobile devices such as smartphones and tablets. The evaluation results show that ECOPS significantly saves the total energy consumption of the devices while achieving a good level of location accuracy. In addition, it enables constrained devices to enjoy location-based services that would otherwise not be possible.

The rest of the paper is organized as follows. Potential application scenarios are described in Section 2. Section 3discusses the existing and state-of-the-art techniques. A detailed explanation of the proposed system is presented in Section 4. The performance evaluations and experimental scenarios are explained in Section 5. Finally, we conclude the paper in Section 6.

2. Application Scenarios

While security and social incentive issues are not in the scope of this paper, the proposed opportunistic and collaborative positioning scheme can be especially useful for unique resource scarce and mission critical applications. Such examples include border patrol, battlefields, mountaineering expeditions, and disaster area assistance.

For example, suppose a team of border patrol officers is searching for an illegal immigrant in the border area. In some areas of rigid terrain, GPS and cellular signals can be lost in a canyon. Some projects [ 14] employ a low-altitude tethered aerostat to set up a temporary WiFi hotspot. To help with positioning, a few officers stay at the top of the valley to relay their GPS position information to the officers searching down in the valley. Such a collaborative positioning is a natural application scenario of ECOPS.

In a battlefield scenario, when a platoon is air-dropped into a war zone, it is nearly impossible to find WPS services in the surroundings. Even with the availability of technology like LANdroids [ 15] to provide a network in such conditions, it is not a simple task. Also, it is crucial for soldiers to have accurate location information in the battlefield. In such a scenario, the capabilities of ECOPS can be exploited to maintain accurate location information while reducing overall energy consumption. Although one may not have a strong incentive to take a lead and offer location information for others, such concerns are lifted immediately if a leadership hierarchy preexists in the application scenario. For instance, when a platoon is being deployed in a battlefield, the platoon leader chooses to be the primary location broadcaster using ECOPS along with a few others at the top of the hierarchy. The other soldiers in the unit are able to estimate their location information based on the geocoordinates they receive from their unit's command. This will result in fewer devices from the unit querying satellites for location information and reduce the overall energy consumption. Extending the lifetime of devices during the operation is a mission critical parameter as the duration of an operation is not fixed and often tends to be longer than expected. Under the Battlefield Air Targeting Man Aided Knowledge (BATMAN) [ 16] project, the United States Air Force is actively seeking to equip their soldiers with modern Android-powered smartphones to obtain accurate location information with high energy efficiency. Modified versions of Android [ 17, 18] enable the desired level of security for military use. Such projects can benefit greatly by ECOPS.

Another scenario where ECOPS can be extremely useful is during natural calamities. In such cases, emergency responders who are involved in search and rescue missions can host an ECOPS-based location broadcasting service over WiFi Direct. As they move around the area, victims can use their smart devices to either request assistance or transmit their locations.

3. Related Work

Positioning schemes on mobile devices have been a long standing topic of exploration. This resulted in three main positioning techniques using either the information provided by the GPS, WPS, or Cell-ID Positioning. Also, there have been several research proposals for specific environments.

3.1. Global Positioning System (GPS)

The Global Positioning System (GPS) is a satellite navigation system that provides location and time information anywhere on earth with four or more GPS satellite signals. It is originally deployed and maintained by the United States government and is now freely accessible to anyone [ 2]. The GPS provides very high level of accuracy, but suffers from a high TTFF due to the large distance between the GPS receiver and serving satellites. This problem has been somewhat addressed by the use of assisted GPS (aGPS) that relies on the cellular or internet infrastructure to get a faster lock on the serving satellites while obtaining precise time information from the network.

Within the navigation message continuously broadcasted by each of the satellites in the constellation, the GPS receiver looks for three important pieces of data as illustrated in Figure 1. The first piece of data consists of the GPS date and time information. It additionally also consists of the health statistics of the satellite. The ephemeris data forms the second important piece and allows the GPS receiver to calculate the position of the satellite and is broadcasted every 30 seconds. The ephemeris data is valid for no longer than four hours. The third important piece is the almanac data which provides approximate information concerning the rest of the satellites. This data is transmitted over 12.5 minutes and is valid for a maximum of 180 days. The almanac data can be obtained from any satellite, and it enables the GPS receiver to determine which particular satellite to search for next. As the signal from the selected satellite becomes directly available, the GPS receiver then downloads the second important data, that is, the ephemeris data. It is absolutely necessary that the GPS receiver has the satellite's complete copy of the ephemeris data to determine its position. In case the signal is lost in the middle of acquiring this data, the GPS receiver will have to discard whatever data was downloaded and start searching for a new satellite signal.

Figure 1: Illustration of Global Positioning System.

[figure omitted; refer to PDF]

Once the GPS receiver has ephemeris data directly from three or more satellites, it can carry out various methods to accurately determine its own location. These methods involve and are not restricted to 3D trilateration, Bancroft's method, and multidimensional Newton-Raphson calculations. Due to the high propagation delays, getting the ephemeris and almanac data can take up to 15 minutes for a device just out of the factory, and then around ~20 seconds after the initial configuration. To expedite this process, some GPS receivers can use multiple channels for faster fixes. Another strategy is to obtain the ephemeris and almanac data from a faster network like the cellular network or the internet as in the case of a GPS.

3.2. WiFi-Based Positioning System (WPS)

WPS maintains an extensive database of WiFi access points (APs) along with their geographic locations [ 19, 20]. This information has to be collected painstakingly over a large duration of time and is vulnerable to changes in the location of APs or the discontinuation of their service. The information of APs-SSID and geographic location can be collected manually or in a more automated way by retrieving the GPS location of smart devices connected to the AP and associating that information with the AP. Once such a large and dedicated database is ready and a device is in the vicinity of an AP, or several APs, it can provide the RSSI values and the SSID of the APs to the WPS servers. The WPS servers, based on proprietary techniques, apply filtering approaches and trilateration techniques to this data and determine the accurate location of the smart device. This geographic location information is then relayed back to the smart device which can exploit it for various LBSs. The illustration of WPS is depicted in Figure 2.

Figure 2: Illustration of WiFi positioning system.

[figure omitted; refer to PDF]

While the WPS service approaches work well in terms of energy efficiency [ 21- 23], they are not globally available for users. A solution leveraging the existing infrastructure, such as APs without requiring any specialized infrastructures for localization, has been proposed in [ 24]. However, since this localization scheme is limited to the indoors and still relies on infrastructure, such as APs, it cannot be useful outdoors where the WiFi signals are neither dense enough nor covered.

3.3. Cell-ID Positioning

In Cell-ID Positioning, a mobile device obtains its position from the geographic location of its associated base transreceiver station (BTS), with an error range proportional to the signal strength within a cell. The mobile device can estimate its location as the BTS periodically broadcasts its Cell-ID along with its location. Once this information is available to the mobile device, it can use the location of the BTS as its own location with the error calculated using the propagation model. Another technique that may be used for cell phones to estimate their location is to observe the delay in receiving a special message broadcasted by the BTS from the time it was transmitted. This information is used by the mobile device to estimate its distance from the BTS.

Note that a cell size can be very large especially in rural areas and highways where the density of cellular towers is very low. One cellular tower is often capable for serving up to 5 Km radius. As this large cell size leads to a significant error range, other nearby cell tower signals may be used in order to improve the accuracy [ 4, 25]. Such approaches also exploit the fading phenomenon independently or along with predictive techniques to improve the accuracy of Cell-ID Positioning. However, the accuracy is still limited as the propagation model needed for the trilateration does not work well, due to complex signal fading behavior over long distances. The illustration of Cell-ID Positioning is depicted in Figure 3.

Figure 3: Illustration of Cell-ID Positioning.

[figure omitted; refer to PDF]

3.4. Recent Research Proposals

While most of commercial approaches heavily depend on infrastructures [ 3, 26], or use extra high-end sensors and exploit the available information from an individual device [ 26- 28], research proposals mostly aim to improve the positioning accuracy or energy efficiency through algorithmic approaches [ 8, 23, 24, 29- 33].

The work in [ 31- 33] attempt to learn a known location from a training phase for a better location accuracy. The authors of [ 33] employ indoor positioning, and perform fingerprinting and training of the known space using multiple sensors in a smartphone such as WiFi radio, cellular communications radio, accelerometer, and magnetometer. In order to improve Cell-ID location accuracy in low-end cell phones where neighboring cell tower information is not available, [ 32] uses RSSI from only the associated cell tower and leverages the signal strength history to estimate the location. The Cell-ID Aided Positioning System (CAPS) [ 31] relies on the continuous mobility and position history of a user to obtain better location accuracy over a basic cell tower-based approach. It uses Cell-ID sequence matching to estimate current position based on the history of Cell-ID and GPS position sequences that match the current Cell-ID sequence. CAPS assumes that the user moves on the same routes repeatedly and has the same cellular chip and infrastructure availability.

A few studies address energy efficiency of smartphones using power duty cycling techniques [ 7, 8, 31] that use a combination of the basic positioning techniques in a smartphone. The authors of [ 7] use different positioning schemes depending on the condition, for the purpose of target tracking. In the scheme, energy-efficient but inaccurate Cell-ID Positioning or WPS is used when the target is distant, while accurate but energy-inefficient GPS is used when the target is close. The rate-adaptive positioning system (RAPS) [ 8] uses built-in sensors in a smartphone to determine if the phone has moved beyond a certain threshold and decides whether to turn on the GPS or not. RAPS also stores the space-time history of the user's movements to estimate how to yield high energy efficiency. Another idea presented by the authors involves a Bluetooth-based position synchronization (BPS) in which devices share their location information over a Bluetooth connection. While a Bluetooth connection consumes less power as compared to a WiFi ad hoc, it also limits the range of communication to less than 10 m. Our work has advantages over the basic BPS technique in several aspects. Not only does a WiFi ad hoc mode give us a better range, but we have also taken into account the heterogeneity amongst the devices in terms of availability of a GPS chip or cellular connection. We expect all the devices to have at least a WiFi module present onboard. In BPS, once location information is obtained from a neighboring device, only a fixed error range of 10 m (e.g., same as the range of a typical Bluetooth) is associated with that information. However, in ECOPS we exploit the RSSI values of the connection to determine the accurate distance between the two devices, and when three or more location transmitting devices are available, the trilateration technique achieves pinpoint locating capabilities.

The work in [ 34] proposed to use minimal auxiliary sound hardware for acoustic ranging in order to improve the accuracy. The acoustic ranging technique estimates the distance among peer phones, then maps their locations jointly against a WiFi signature map subject to ranging constraints. It is a WPS augmentation technique to improve the accuracy over a pure WPS.

Our approach is unique in that we use a collaborative approach rather than focusing on the information in an individual device and do not rely on any special hardware or infrastructure such as WPS or Cell-ID Positioning. Note that we only use a small amount of GPS information and the WiFi ad hoc mode of mobile nodes. ECOPS is specifically aimed at resource constrained environments such as battlefields where GPS is the only available positioning infrastructure, and WiFi ad hoc mode is readily available in most mobile devices while allowing good network range (up to 100 m). Beside controlling energy usage and location accuracy, we allow to use heterogeneous mobile device types.

4. ECOPS Approach

In this section, we discuss ECOPS algorithms in detail. Figure 4shows an ECOPS deployment example. It consists of mobile devices with heterogeneous positioning methods available such as GPS, WiFi, and Cell-ID. These devices virtually establish an ad hoc network using WiFi to build a collaborative positioning environment. In the established ECOPS ad hoc network, a device may function as either a position broadcaster (PB) or a position receiver (PR). A GPS-equipped device with sufficient battery life and up-to-date location information becomes a candidate for a PB. Other devices with no GPS that need current location information will become PRs.

Figure 4: ECOPS deployment example.

[figure omitted; refer to PDF]

Three algorithms are presented for the overall operation of the ECOPS. Algorithm 1describes the initial procedure deciding whether a device becomes a PB or a PR. After the initial decision, Algorithms 2and 3depict how the devices in ECOPS collaboratively maintain their most updated location information as a PB or a PR, respectively. For GPS-equipped devices, the role of the devices can be changed during their operation according to their residual energy level (i.e., PB ...PR ). As illustrated in Algorithm 1, a device, once it starts ECOPS operation, will check the time elapsed since the device got the location information ( _{t e} ) and residual power ( _{p r} ) to see if it is qualified for being a PB. Since we are looking for the devices that have the most recent location information with enough residual power, the device with the conditions such as _{p r} ...5; _{p min} and _{I decay} ...5; α can be a PB, where _{p min} is the minimum residual energy that a PB has to maintain and _{I decay} is the level of the validity with respect to time for the location information, defined by [figure omitted; refer to PDF] where _{t d} is the maximum time in which the location information is considered to be valid.

Algorithm 1: ECOPS: Initial procedure deciding whether a device becomes either a PB or a PR.

1: check the residual power ( _{p r} );

2: if GPS-equipped device & _{p r} ...5; _{p min} then

3: device becomes PB and activates WiFi hotspot;

4: executes CollaborativePB ();

5: else if non-GPS device |"|" _{p r} < _{p min} then

6: device becomes PR and executes CollaborativePR ();

7: end if

Algorithm 2: ECOPS: CollaborativePB ().

1: while _{p r} ...5; _{p min} do

2: listen to connection request from a PR ;

3: wait for location request from a PR ;

4: if PR requests then

5: check the time elapsed since the device got location

information ( _{t e} )

6: calculate _{I decay} ;

7: if _{I decay} < α then

8: update its GPS location information;

9: _{t e} =0 ;

10: end if

11: end if

12: broadcast current GPS location information;

13: check the residual power ( _{p r} );

14: end while

15: execute CollaborativePR ();

Algorithm 3: ECOPS: CollaborativePR ().

1: while non-GPS device |"|" (GPS-equipped device & _{p r} < _{p min} ) do

2: sleep until the device needs to update location information

3: numofPBs = 0;

4: check the list of available PBs ;

5: make connection to each PB and request GPS location

information sequentially;

6: calculate the distance to each PB using the obtained

RSSI value;

7: set numofPBs to the number of the detected PBs

8: if numofPBs == 1|"|" one of PBs is within the near field

threshold ( β meters) then

9: use the received GPS location information immediately

without trilateration;

10: continue;

11: end if

12: if numofPBs == 2 then

13: calculate two possible locations ( PR ) and get the

middle location between the two possible locations;

14: end if

15: if numofPBs >= 3 then

16: select three PBs randomly and calculate the its cur-

rent location ( PR ) with the GPS coordinates and

distance information of the selected PBs ;

17: end if

18: if GPS-equipped device then

19: check the residual power ( _{p r} );

20: end if

21: end while

22: execute CollaborativePB ();

If a device is equipped with a GPS receiver and satisfies the _{p min} , it can be a PB. Once it becomes a PB, it will start its WiFi hotspot mode and serve the most up-to-date location information to a PR when a PR requests the location information. An Android device cannot use the WiFi Internet service while it is in the WiFi hotspot mode. However, with (Android 4.0), WiFi Direct technology can be used for PBs. In a PB mode with WiFi Direct, the users can enjoy their WiFi Internet service and provide the most up-to-date location information simultaneously. The device without a GPS receiver will automatically be a PR once it enters ECOPS, and then search for PBs around it.

As shown in Algorithm 2, once the device enters the PB mode, it plays a role of the PB while it satisfies the _{p min} constraint. The threshold α is a system parameter that can be varied according to the requirement of applications. The tradeoff between location accuracy and energy consumption can be adjustable using α . An application requiring high accuracy will select a small amount of α , but a high value of α is used for applications requiring low energy consumption. The PB will check _{I decay} to see if the current location information is adequate (e.g., _{I decay} ...5; α ) before broadcasting it.

In Algorithm 3, a PR will collect the possible number of GPS coordinates and corresponding RSSI values and apply opportunistic localization as illustrated in Figure 5. If a PR finds a PB within the threshold distance ( β meters), then a PR uses the GPS coordinate from a PB as is. The parameter β is controllable and users of ECOPS can set it according to their preference. Once a PR estimates its location, it can become a PB. However, we do not use those cases in our experiments to avoid the additional errors that will be induced from PBs and focus on the PR's accuracy.

Figure 5: 2D trilateration.

[figure omitted; refer to PDF]

ECOPS is opportunistic, meaning that getting the most updated location via trilateration is not limited by the number of available PBs. Supposing that there is only one GPS broadcaster in Figure 5, say node C , then the center of an error range of the circle _{C 3} will become the PR's approximated position. Another possible situation is when there are two PBs, say nodes A and B ; then the middle point of two possible points, D and ^{D [variant prime]} , is selected as an approximated PR location. The accuracy of the estimated location will range from one point where the two circles intersect in the best case to the diameter of the smaller circle in the worst case, respectively. In order to get the most accurate location information for a PR, we need at least three PBs to provide their location information obtained from the GPS receiver along with the RSSI values, so that we can build an absolute coordinate system from the relative coordinate system. For example, in Figure 5, we calculate the distance parameters a , b , c , and d using the algorithm described in [ 35] in order to obtain the values of e and f . We convert the obtained distances e and f into the unit of the GPS coordinates to get the final calculated GPS coordinate. The distance between two GPS coordinates, (la _{t 1} , _{lng 1} ) of e and (la _{t 2} , _{lng 2} ) of f , is computed using the haversine formula that gives a spherical distance between two points from their longitudes and latitudes [ 35, 36]. The formula is described in ( 2) and the formula for the value of dist is shown in ( 3): [figure omitted; refer to PDF]

Thus, we can calculate relative coordinates ( a , b , c , and d ) as follows: [figure omitted; refer to PDF]

The distances ( _{d 1} , _{d 2} , and _{d 3} ) between node D and other nodes ( A , B , and C ) can be derived from the measured RSSI values of node D , using the formula from the path loss propagation model [ 37]: [figure omitted; refer to PDF] where RSSI is the received power which is a function of the distance between the transmitter and the receiver (T-R), n is the signal propagation constant (also called propagation exponent), d is the T-R separation distance in meters, and [Lagrangian (script capital L)] is the system loss factor. Based on ( 5), we derived the distance ( d ) between two devices using the average RSSI value as follows: [figure omitted; refer to PDF]

Now, the three circles in Figure 5can be represented by the following, respectively: [figure omitted; refer to PDF] where the location of node A is set to (0,0 ) .

We obtain the relative coordinate of PR node D from node A , (e ,f ) , by calculating the point where these three circles intersect. In other words, we want to calculate the coordinate values of X and Y that simultaneously satisfy ( 7), ( 8), and ( 9). We first extend ( 8) and ( 9) as follows: [figure omitted; refer to PDF] By applying ( 7) into ( 10), the circles _{C 2} and _{C 3} can be written as [figure omitted; refer to PDF]

Finally, the node D 's coordinate that satisfies the three circles is attained by replacing X and Y with e and f , respectively, in ( 11). We can formulate the equations in terms of e and f as follows: [figure omitted; refer to PDF] where _{D vec1} = ^{_{d 2} 2} - ^{_{d 1} 2} - ^{a 2} - ^{b 2} and _{D vec2} = ^{_{d 3} 2} - ^{_{d 1} 2} - ^{c 2} - ^{d 2} .

We have implemented ECOPS as an Android application for a feasibility test and analysis. Figure 7shows the screenshots of the ECOPS application. Figure 7(a)displays the main screen that allows users to manually select an ECOPS device option either in PB mode or PR mode, or to request the selection automatically based on various parameters such as the remaining energy and sensor availabilities. Figure 7(b)presents a PB screen that lists the broadcasting location information. Figure 7(c)shows a PR screen that lists the received information and measured distance using the RSSI value. Although the current implementation is on an application level, as illustrated in Figure 6, it is still capable of making the received location information available to other application services. It will eventually be implemented within the application framework so that other applications can use the ECOPS services via APIs.

Figure 6: Android module architecture.

[figure omitted; refer to PDF]

ECOPS screenshots.

(a) Main menu

[figure omitted; refer to PDF]

(b) PB mode

[figure omitted; refer to PDF]

(c) PR mode

[figure omitted; refer to PDF]

5. Experiments

In this section, we present the evaluation results of ECOPS in terms of energy efficiency and location accuracy. We have implemented an ECOPS Android application and used several Android smartphones including Samsung Galaxy Nexus S running Android version 2.3.6 and two LG Optimus V running Android version 2.2.2. We have turned the GPS off on some of the devices to mimic heterogeneous devices.

5.1. Validation of Smartphone GPS Accuracy and Propagation Model

As a first step, we test the accuracy of commodity GPS receivers on smartphones since they are not dedicated devices like the navigation devices for positioning. We have measured the accuracy of smartphones' GPS, by walking around the Kansas City area while carrying three smartphones. As shown in Figure 8, the GPS collected locations are presented accurately except for a little error between tall buildings (~10 m).

Figure 8: GPS trace obtained by smartphone.

[figure omitted; refer to PDF]

Next, we validate the path loss model for correlation of the distance between a WiFi signal emitter and receiver with the measured RSSI values at the signal receiver for both indoor and outdoor environments. We compared the measured RSSI value with the theoretical RSSI value from the path loss model. As RSSI values often vary at each time of measurement for a given location, we used an averaged RSSI value with multiple samples (e.g., 1,000 samples within a few seconds). In Figures 10and 11we compare the measured RSSI with the theoretical RSSI while varying the distance between PB and PR; both inside a building and in outdoor environments are shown, respectively. The theoretical RSSI values are derived from ( 5). The dotted blue line shows the measured average RSSI values, and the solid green line represents the theoretical RSSI values at the corresponding distances. The system loss factor value ( A ) is set to 30. For the indoor environment, since we measured the RSSI between two devices while they were in the line-of-sight, we set the system loss factor ( n ) to 0.6. For the outdoor environment, we used n =1.9 . As evidenced in the figures, we observe that the path loss model works well for us in estimating the distance.

5.2. Energy Consumption

We now compare the total energy consumption of ECOPS devices to that of devices with GPS only scheme in various settings. First, we compare the energy consumption of a node that is ECOPS PR with a node using only GPS at per second granularity as illustrated in Figure 9. This power consumption profiling was done using PowerTutor [ 38]. The GPS uses 429 mW/s continuously once it is powered up and takes several seconds to power down which adds up to the energy consumption. Meanwhile, the WiFi module once powered up uses 720 mW/s in an active state and 38 mW/s when in an idle state. During the experiment, for the same operational time of one minute, an ECOPS PR node uses only 3000 mW of energy in total whereas the GPS-only node uses 7432 mW of total energy. This clearly shows that an ECOPS PR is more energy efficient than a GPS-only node. These values are for an LG Optimus V model in particular, and similar for most smartphones.

Figure 9: Energy usage: GPS versus ECOPS PR.

[figure omitted; refer to PDF]

Figure 10: Measured RSSI (avg. of 1,000 samples) at various indoor spots.

[figure omitted; refer to PDF]

Figure 11: Measured RSSI (avg. of 1,000 samples) at various outdoor spots.

[figure omitted; refer to PDF]

Next, we contrast the energy consumption of a node that is ECOPS PR with a node using only GPS while varying the operational time with 1 minute increments as illustrated in Figure 12. We do this experiment to analyze the effectiveness of ECOPS over a duration of time. It shows that ECOPS is increasingly energy efficient with the elapsed time over the GPS only scheme.

Figure 12: Comparison of individual node energy consumption: GPS versus ECOPS PR.

[figure omitted; refer to PDF]

In Figure 13, we compare the energy consumption of nodes that are ECOPS PR with nodes using only GPS while varying the number of devices in the network. We do this experiment to analyze the energy efficiency of ECOPS as the number of devices in the network scales. Note that for the ECOPS PR scheme, the PRs receive GPS data from three PBs and their energy consumption is accounted for in the results. The energy efficiency of ECOPS compared with the GPS only scheme is clear from Figure 13and becomes increased substantially as the number of devices in the network scales.

Figure 13: Comparison of total energy consumption of nodes (1 min): GPS versus ECOPS.

[figure omitted; refer to PDF]

5.3. Location Accuracy

In this section, we evaluate the location accuracy of ECOPS as compared to that of GPS, WPS, and Cell-ID Positioning. We tested ECOPS in a soccer field using four smartphones for the accuracy measurements. The soccer field was chosen, so that we have a clear and unhindered view of the sky, and in turn the experimental results are not influenced by the GPS position errors, and the ECOPS errors are precisely measured. We turned on GPS for three devices and turned it off for a device that acted as the PR. In order to measure the location accuracy, as illustrated in Figure 14, we placed the PR device at the center of the area and moved the other PB devices around multiple locations within the soccer field. The PR device computed its location using the measured RSSI values, and GPS coordinates from the PBs, and the trilateration technique described in Section 4.

Figure 14: An example of field experiments.

[figure omitted; refer to PDF]

We have moved the PBs to various places around the PR and recorded the PR's computed locations. As shown in Figure 15, we observed that ECOPS achieves a minimum error range of 2.32 m and a maximum error range of 33.31 m. While from Figure 16we can observe that nearly 60% of these locations are within a 10 m error range and less than 10% have an error range greater than 15 m. The results represent that ECOPS can achieve a higher location accuracy than WPS while using less energy than GPS receivers. Also, note that the error ranges we observe here are an amalgamation of the general GPS receiver error from the PBs and the distance measurement error from the RSSI values.

Figure 15: Experiment results: points calculated with three GPS coordinates and RSSI values.

[figure omitted; refer to PDF]

Figure 16: Distribution in error range for location estimated by PR.

[figure omitted; refer to PDF]

Finally, we compare the errors of different positioning methods in Figure 17. As before, a smartphone that needs positioning is located at the center of soccer field. The network positioning API in Android obtains the location information either from WPS or Cell-ID Positioning. In order to ensure the Cell-ID Positioning in Android, the smartphone acquired the location from network positioning API while turning off the WiFi signal. The location information received was off by almost 300 m. Together with the location, it also suggested its own estimated error range of 1,280 m associated with it. Clearly, such information is too inaccurate to be used in most of LBS application scenarios. As for WPS, the smartphone obtained the location from Android network positioning API while turning off cellular signal. Note that WPS is not typically available in outdoor environment. Thus, we used an average WPS error from what we experimented at multiple locations in Kansas City area where WPS is available and found it to be 60 m. It is the dotted blue line in Figure 17. While the GPS-based location information proved to be the most accurate with an error range of about 2 m, ECOPS achieved the accuracy ranging from 2.32 m to 33.31 m. This is better than the performance of a WPS and fairly close to GPS accuracy while saving energy costs. This encourages us to comment that even when WPS service might be available, using ECOPS will facilitate a smartphone to receive more accurate location information at the same energy cost.

Figure 17: Accuracy comparison: ECOPS, GPS, WPS, and GSM-based positioning.

[figure omitted; refer to PDF]

6. Conclusion

We have presented an Energy Efficient Collaborative Opportunistic Positioning System (ECOPS) for heterogeneous mobile devices. Unlike existing approaches that are seeking the best available positioning method from an individual device, ECOPS facilitates collaborative environments among a set of mobile devices, and thus mobile devices benefit from their neighboring devices. ECOPS supports heterogeneous devices to maximize energy-efficiency, as a device with only WiFi can collaborate with a few available GPS broadcasting devices via WiFi hotspot mode or WiFi Direct-based approximation. A beneficiary device may use one or more locations' information from neighbors opportunistically, depending on their availability. Furthermore, each device improves the received location accuracy via various available methods including trilateration or approximation with geomagnetic sensors. We have implemented an ECOPS prototype application on Android 2.3.6 and 2.2.2 and have tested it with various types of Android mobile devices. The results show that ECOPS provides accuracy within 10 m for nearly 60% of the location estimates, and within 15 m for more than 90% of them. ECOPS also offers significantly more energy efficiency than a GPS-only scheme, while overcoming various service limitations.

Future work includes fine-tuning the accuracy by opportunistically exploiting other available sensors on mobile devices. We also plan to consider strategies for various types of LBSs to improve their utility and energy efficiency.

References

[1] E. Kwon, S. Song, D. Seo, I. Jung, "Agent-based on-line traffic condition and information analysis system for wireless V2I communication," in Proceedings of the 2nd International Conference on Ubiquitous and Future Networks (ICUFN '10), pp. 360-365, Jeju Island, Republic of Korea, June 2010.

[2] "Global positioning system standard positioning service performance standard," http://www.gps.gov/technical/ps/2008-SPS-performance-standard.pdf

[3] "Skyhook wireless," http://www.skyhookwireless.com/

[4] E. Trevisani, A. Vitaletti, "Cell-ID location technique, limits and benefits: an experimental study," in 6th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA '04), pp. 51-60, December 2004.

[5] "Google latitude," 2012, http://www.google.com/latitude

[6] "Foursquare," https://foursquare.com/

[7] U. Bareth, A. Kupper, "Energy-efficient position tracking in proactive location-based services for smartphone environments," in Proceedings of the 35th IEEE Annual Computer Software and Applications Conference (COMPSAC '11), pp. 516-521, Munich, Germany, July 2011.

[8] J. Paek, J. Kim, R. Govindan, "Energy-efficient rate-adaptive GPS-based Positioning for smartphones," in Proceedings of the 8th Annual International Conference on Mobile Systems, Applications and Services (MobiSys '10), pp. 299-314, New York, NY, USA, June 2010.

[9] "Android 2. 2 platform highlights--portable hotspot," http://developer.android.com/about/versions/android-2.2-highlights.html

[10] "Wi-Fi direct," http://developer.android.com/guide/topics/wireless/wifip2p.html

[11] Y. Zhang, L. Yang, J. Chen RFID and Sensor Networks: Architectures, Protocols, Security and Integrations , CRC Press, New York, NY, USA, 2009.

[12] T. Rappaport Wireless Communications Principles and Practice , Prentice Hall, New York, NY, USA, 1996.

[13] "3-Axis geomagnetic sensor for electronic compass," http://developer.android.com/guide/topics/connectivity/wifip2p.html

[14] M. Mohorcic, D. Grace, G. Kandus, T. Tozer, "Broadband communications from aerial platform networks," in Proceedings of the 13th IST Mobile and Wireless Communications Summit, pp. 257-261, 2004.

[15] "LANdroids robot," 2012, http://www.irobot.com/gi/research/AdvancedPlatforms/LANdroidsRobot

[16] "The air force has its own batman," 2012, http://money.cnn.com/video/technology/2012/05/18/t-ts-wpafb-batman.cnnmoney/

[17] "U.S. government, military to get secure Android phones," 2012, http://www.cnn.com/2012/02/03/tech/mobile/government-android-phones/index.html

[18] National Security Agency(NSA), "Nsa-grade security enhanced android source released," 2012, http://www.androidauthority.com/nsa-grade-securityenhanced- android-source-released-45532/

[19] "Google maps location based services," http://support.google.com/maps/bin/answer.py?hl=en&answer=1725632

[20] "Apple location based services," http://www.apple.com/privacy/

[21] B. N. Schilit, A. LaMarca, G. Borriello, W. G. Griswold, D. McDonald, E. Lazowska, A. Balachandran, J. Hong, V. Iverson, "Challenge: ubiquitous location-aware computing and the "place lab" initiative," in Proceedings of the 1st ACM International Workshop on Wireless Mobile Applications and Services on WLAN Hotspots (WMASH '03), pp. 29-35, September 2003.

[22] W. Ho, A. Smailagic, D. P. Siewiorek, C. Faloutsos, "An adaptive two-phase approach to WiFi location sensing," in Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops '06), pp. 452-456, Pisa, Italy, March 2006.

[23] D. Kelly, R. Behant, R. Villingt, S. McLoone, "Computationally tractable location estimation on WiFi enabled mobile phones," in Proceedings of the IET Irish Signals and Systems Conference (ISSC), 2009.

[24] K. Chintalapudi, A. P. Iyer, V. N. Padmanabhan, "Indoor localization without the pain," in Proceedings of the Mobile Computing and Networking (MobiCom '10), pp. 173-184, 2010.

[25] "Blackberry locate service," https://developer.blackberry.com/devzone/develop/platform_services/platform_locate.html

[26] "Ekahau real time location system (RTLS)," http://www.ekahau.com/products/real-time-location-system/overview.html

[27] "Cisco AeroScout location-based services solution," http://www.cisco.com/web/strategy/docs/manufacturing/Aeroscout-Cisco-Brochure.pdf

[28] "Broadcom: new location architecture withBCM4752," http://www.broadcom.com/products/features/GNSS.php

[29] F. Schrooyen, I. Baert, S. Truijen, L. Pieters, T. Denis, K. Williame, M. Weyn, "Real time location system over WiFi in a healthcare environment," Journal on Information Technology in Healthcare , vol. 4, no. 6, pp. 401-416, 2006.

[30] A. Ofstad, E. Nicholas, R. Szcodronski, R. R. Choudhury, "AAMPL: accelerometer augmented mobile phone localization," in Proceedings of the 1st ACM International Workshop on Mobile Entity Localization and Tracking in GPS-Less Environments (MELT '08), pp. 13-18, New York, NY, USA, September 2008.

[31] J. Paek, K. H. Kim, J. P. Singh, R. Govindan, "Energy-efficient positioning for smartphones using cell-ID sequence matching," in Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services (MobiSys '11), pp. 293-306, New York, NY, USA, July 2011.

[32] M. Ibrahim, M. Youssef, "A hidden Markov model for localization using low-end GSM cell phones," in IEEE International Conference on Communications (ICC '11), pp. 1-5, Kyoto, Japan, 2011.

[33] E. Martin, O. Vinyals, G. Friedland, R. Bajcsy, "Precise indoor localization using smart phones," in Proceedings of the 18th ACM International Conference on Multimedia ACM Multimedia 2010 (MM '10), pp. 787-790, October 2010.

[34] H. Liu, Y. Guan, J. Yang, S. Sidhom, Y. Wang, Y. Chen, F. Ye, "Push the Limit of WiFi based Localization for Smartphones," in Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (Mobicom '12), pp. 305-316, 2012.

[35] "Calculating distance between two points given longitude/latitude," http://www.freevbcode.com/ShowCode.asp?ID=5532

[36] R. W. Sinnott, "Virtues of the Haversine," Sky and Telescope , vol. 68, no. 2, article 158, 1984.

[37] K. Aamodt, "Applicationnote AN042 (Rev.1.0)," pp. 7-8, 2006

[38] "PowerTutor," http://ziyang.eecs.umich.edu/projects/powertutor/

[]