Energy-optimal collaborative GPS localization with short range communication

Energy-Optimal Collaborative GPS Localization with Short Range Communication Jeongho Kwak, Jihwan Kim, and Song Chong Department of Electrical Engineering, KAIST E-mail: {jh.kwak, kimji}@netsys.kaist.ac.kr, songchong@kaist.edu Abstract—The key issue of the localization study is that how we can minimize the energy consumption of devices with guaranteeing high degree of accuracy. In this paper, we show that the collaboration among proxy devices with short range communication is helpful to energy-efficiently localize their locations in time-average sense by analyzing the device proximity including real GPS trace of students in KAIST and NCSU campuses. Next, we deliberate what is the best method for selfish mobile users to collaborate for the energy-efficient localization, and formulate an optimization problem which considers the energy efficiency and/or user fairness. However, optimizing this problem is tricky since it requires a global knowledge of sets of proxy devices and also solving a NP-hard problem to select devices which directly measure locations. This paper makes a contribution towards presenting a practical and fully distributed location sharing protocol based on competition for turning off GPS, and an optimal algorithm which controls mean waiting time used for the competition. Through the extensive simulations under several sample topologies and real mobility trace in KAIST campus, we obtain the following interesting observations: (i) (in sample topologies) our scheme achieves a near-optimal performance of proposed problem in terms of energy efficiency and fairness (up to 27.2% power saving with 35.8% higher fairness than existing heuristic algorithms), (ii) (in real mobility trace) our scheme well adapts at even unpredictably changing mobility environment (65.5% power saving than no collaboration, 27.4% or more power saving with 25% higher fairness than the existing algorithms). I. I NTRODUCTION Recently, the number of applications which demand consecutive and accurate locations in smart phones/pads have been increasing [1]–[3]. For example, Google Now [3] continuously senses your position to provide appropriate service based on the location. Moreover, in the next generation networks using a technique of location based beamforming [4], base stations should know consecutive locations of every associated device for network management. To the best of our knowledge, GPS is the most accurate localization technique in outdoor environment. However, the GPS modules in mobile devices consume significant amount of energy compared to the other modules (e.g., (i) a GPS-enabled N95 smartphone consumes more than sevenfold time-average power compared to a GPSdisabled one, (ii) keeping GPS continuously activated drains the 1200mAh battery in less than 11 hours [5]). To reduce localization energy, there have been several researches, e.g., [5]–[9] which use WiFi/cellular infrastructures or adscititious sensors. However, some of energy-efficient schemes which “This research was supported by the KCC(Korea Communications Commission), Korea, under the R&D program supervised by the KCA(Korea Communications Agency)”(KCA-2013- (11-911-05-004)). do not use GPS such as WPS (WiFi-based positioning system from SkyHookWireless [6]), or GSM-based positioning system had sacrificed accuracy by reducing the energy (e.g., accuracy of GPS: 8.8m, WPS: 32.44m, GSM:176.7m in open sky environments [5]). Since the recent applications [1]–[4] demand consecutive positions with guaranteeing a high degree of accuracy, we need a localization solution to satisfy both of a localization accuracy and of an energy efficiency. The key idea of this paper is to share the position information with proxy devices using the short range communication (SRC) such as Bluetooth or Zigbee [10] which use less energy than GPS (e.g., average GPS power consumption: 440mW [5], average Bluetooth power consumption: 110.5mW [11]) in order to reduce localization energy. For example, if there are 9 devices around a certain device within a few meters and the all 10 devices should consecutively know their own locations, the certain device can measure its location using GPS and share the location information with the other 9 devices using the SRC. Then the 10 devices can obtain their locations with consuming high GPS power of only one device plus low Bluetooth power of all devices while guaranteeing accuracy of GPS plus SRC range (e.g., average range of Bluetooth: 10m [12], GPS accuracy: 8.8m [5]). In this idea, the energy efficiency for localization probably depends on the number of proxy devices within the SRC coverage. Since the human beings are social creatures, they spend a lot of time with other people. For example, students taking the same class are likely to be closely located in the campus, and relationless people also happen to be closely located when they are in the crowed places such as downtown in the city. The recent human mobility studies, see [13] and references therein, also have told that the moving of the human being reflects the social proximity with other people. At this point, we define two proximity natures: (i) Temporal proximity, i.e., how long a person stay with other people? (ii) Spatial proximity, i.e., how close a person is with other people? According to the American time use survey in [12], a person had enjoyed social relationship with acquaintances for 8.5 hours in average. Also, an analysis of MIT reality mining data [12] told that if a person once meets other people, they had enjoyed the meeting during over 1 hour for 47%. These studies show that the temporal proximity of general human beings is long enough. To observe the spatial proximity, we first statistically analyze the proximity of the human being based on real GPS trace data of students in the KAIST (Korea Advanced Institute of Science and Technology), Korea and NCSU (North Carolina State University), USA campuses. The key result of the analysis is that approximately 5-10 numbers of people are located within a 10m coverage which is average Bluetooth range [12]. However, there are rising questions from the idea of the collaborative localization: (i) Who measures GPS among proxy devices? (ii) How long the device should measure GPS? If total devices can share their locations with minimum number of devices who turn on GPS, they maybe achieve the highest energy efficiency. On the other hand, if total devices can turn on GPS with the same time portion, probably they fairly share the location. Since the owners of the smartphones/pads are selfish, they may not want to spend all of the energy alone for localization. Therefore, considering fairness among devices is no less important than energy efficiency. However, since the devices cannot satisfy both of the highest energy efficiency and complete fairness simultaneously, the answers of above two questions are directly connected to strike a balance between the energy efficiency and fairness of devices. Therefore, we formulate long-term problem which strives to reduce timeaverage GPS power consumption of all devices and controls the fairness of the devices. As a solution of the proposed problem, we should find a sequence of GPS-on device sets that average GPS-on/off time portion of each device asymptotically approaches to an optimal solution. This notion of optimality was similarly considered in the concept of clustering in sensor networks [14]– [16]. However, the clustering cannot directly be applicable in localization due to the different objectives, e.g., maximizing network lifetime. Also, optimizing our problem requires (i) a global knowledge of sets of proxy devices, and also (ii) solving a NP-hard problem of maximum weighted independent set selection form. To resolve these two non practicality, we present (i) a distributed location sharing (DLS) protocol which is operated by proxy device sensing and waiting time to turn off GPS, and (ii) an optimal mean waiting time decision (OWD) algorithm which makes DLS protocol achieve an optimal GPSon/off time portion of each device using only past GPS-on/off statistics. The key mechanism of DLS protocol is that proxy devices compete to turn off GPS with random waiting time whose average value is updated by OWD algorithm. Through the simulations under the several location topologies and real mobility trace in KAIST campus, we find the following key observations. (i) We verify our DLS protocol and OWD algorithm (DLS+OWD) can obtain a near-optimal performance in terms of GPS energy-efficiency and device fairness by comparing with an optimal centralized algorithm. (ii) Our DLS+OWD achieves up to 27.2% power saving with 35.8% higher fairness, and (iii) uses 15-22% of fewer numbers of message passing with proxy devices compared to the existing heuristic algorithms under the sample topologies. (iv) Our DLS+OWD achieves 65.5% power saving compared to no collaboration, and 27.4% or more power saving with 25% higher fairness compared to the existing algorithms under real mobility trace. This shows that our scheme well adapts at even unpredictably changing mobility environment. In the rest of this paper, we begin with the analysis of device proximity in Section II. Next, in Section III, we develop a DLS protocol and an OWD algorithm. In Section IV, we evaluate proposed scheme under the several environments. In Section V, we take a review of related works. Finally, we conclude this paper in Section VI. II. D EVICE P ROXIMITY A NALYSIS Environment and Metrics. We had collected the GPS traces of 93 and 99 students with 5 seconds granularity for 7 days in the KAIST and NCSU campuses, respectively. The areas of campuses are 2km × 2km (KAIST) and 8.5km × 8.5km (NCSU), and the total numbers of students and faculties are approximately 10000 (KAIST) and 40000 (NCSU), respectively. We assume that the distributions of the experimental volunteers are the same as distributions of all the people in each campus, respectively. So, weqscale down the distance # of experimental volunteers between two devices to factor of # of all the people in the campus in this analysis. For the analysis, three kinds of metrics are considered. Sojourn time is continuous retention time of a device within 10m coverage from a reference user, Countave (t) is average number of devices within 10m coverage in time (r) where Avecount (r) is timet, Avecount,N (r) = Avecount r average number of devices within rm coverage. Finally, we define the information sharing gain as the number of total devices divided by the number of devices who measures some information and shares it with proxy devices using SRC. Trace Analysis. From the trace analysis, we made three interesting observations. (i) Sojourn time depends on the attribute of human mobility. Therefore, estimating the event of future mobility is maybe difficult. For example, at 2:00PM and 8:00PM, sojourn time is relatively shorter (average 1 min in KAIST, NCSU (2:00PM), 2min 30sec in KAIST, 3 min 30 sec in NCSU (8:00PM)) than dawn (16min 30sec in KAIST, 9min 30sec in NCSU (6:00AM)) since people more actively move around campus at afternoon and evening than dawn. However, the observed time scale of sojourn time can be considered in the design of a localization scheme. (ii) In weekdays, there exist approximately 10 Countave in KAIST, and 5 Countave in NCSU, respectively. This implies that average 10 number of devices in KAIST, 5 number of devices in NCSU can collaboratively share some information within 10m coverage. However, keep in mind that it does not mean that an information sharing gain is 10 or 5 because the number of information measuring devices varies depending on the SRC connectivity and the selection of sharing device. Our clear objective is to maximize information sharing gain and we will handle this issue in this paper. The reason why NCSU has fewer number of devices than KAIST is that the density of people in the NCSU campus (40000persons/75.25km2 = 531persons/km2 ) is lower than KAIST campus (10000persons/4km2 = 2500persons/km2 ). (iii) Using only short range (e.g., 0-20m) communication may be enough to obtain the information sharing gain. In both campuses, Avecount,N of a long range is smaller (e.g., KAIST with 50m distance: 0.7242, NCSU with 50m distance: 0.3282) than short range (e.g., KAIST with 10m distance: 1.123, NCSU with 10m distance: 0.508). The additional observations are 1 1.4 ͣͦ 0.9 0.8 KAIST 6:00 AM KAIST 2:00 PM KAIST 8:00 PM NCSU 6:00 AM NCSU 2:00 PM NCSU 8:00 PM 0.5 0.4 0.3 0.2 0.1 250 500 750 1000 1250 1500 1750 2000 1.2 Avecount,N 0.6 Countave CDF 0.7 0 0 rhpz{ ujz| ͣ͡ ͦ͢ ͢͡ KAIST NCSU 1 0.8 0.6 0.4 ͦ 0.2 Prq Wxh Zhg Wkx Iul Vdw Vxq 0 0 ͡ Sojourn time [sec] 10 20 30 40 50 Distance from device [m] ͵ΒΪΤ (a) CDF of continuous retention time within 10m (b) Average number of devices within 10m for days (c) Distance-normalized time-average number of defrom reference user vices within rm coverage Fig. 1: KAIST & NCSU trace analysis available in our technical report [17]. In summary, we could obtain a motivation that the average energy consumption of devices can be significantly reduced when we collaboratively measure their locations with proxy devices from the proximity analysis in both campus scenarios1 . From this motivation, we develop an energy efficient collaborative localization scheme in the next section. III. E NERGY O PTIMAL C OLLABORATIVE L OCALIZATION In this section, we formulate a convex optimization problem considering energy efficiency and device fairness, and propose a distributed location sharing protocol and an optimal algorithm to solve the problem. A. Model and Problem Formulation Model. We consider a set N of devices who require consecutive location information and are capable of short range communication (SRC). We define the neighbors as two devices who can communicate each other, i.e., bidirectional communication link. Then, the SRC connectivity is represented by a conflict graph G in which each node represents a device and an edge between two nodes represents a communication link if corresponding two devices are neighbors. Let a device n be a G-leader (GPS leader) if it measures GPS2 and broadcasts location value. Each G-leader has G-members (GPS members) receiving G-leader’s location value. We denote the sharing set of G-leader n by Sn , i.e., Sn = {m ∈ N | n, m are neighbors}. Note that one G-member can be belonged to multiple sharing sets and some G-leaders may have an empty sharing set. Let’s consider a vector x ∈ {0, 1}|N | where nth element of x is 1 (xn = 1) if device n is a G-leader, and xn = 0 otherwise. We say that x is a feasible G-leader set if it satisfies a following condition. Definition 1. (Feasible G-leader set condition): Since all devices should consecutively know their locations for all time, 1 Although our analysis is carried out in the limited scenarios, the other environments such as crowed hotspot at downtown or the movement of soldiers with the same mission are expected to have the similar proximity properties. 2 Although we consider the GPS as location measuring method, it can be generalized into the other localization methods. the feasible G-leader set condition of x is given by: [ (Sn ∪ {n}) = N . (1) n:xn =1 This definition means that every device is contained at least one sharing set or turns on GPS. Then, we can define a set I of feasible G-leader set condition where (xi , i ∈ I) satisfies the condition (1) for given conflict graph G. Problem Formulation. Our two questions in Introduction for collaborative localization were as follows: (i) Who measure GPS among proxy devices? (ii) How long the device should measure GPS? To deal with two questions, our objective is to find the time portion of G-leader of each device n, θn ∈ θ, which is the solution of an optimization problem with the constraints on feasible G-leader condition. All possible vector sets of θ satisfying feasible G-leader sets are given by: X X φi = 1, φi ≥ 0} (2) xin φi , ∀n, F = {θ ∈ R|N | |θn ≥ i∈I i∈I where φi ∈ φ is the time portion of xi . The optimization problem [P-EOL] is chosen such that Energy optimal G-leader selection problem [P-EOL]3 X X (Pn θn )α , (3) (En )α = min θ subject to n∈N n∈N θ∈F (4) where Pn is the average power to use GPS of device n, En is the average-consumed energy during unit period to use GPS of device n, and α ≥ 1 is the fairness parameter. When α is 1, we only consider a sum energy minimization. As α is bigger, the problem [P-EOL] tends to select less elected devices as Gleader to minimize the objective function, which means higher fairness is enforced. 3 Since actual G varies depending on the mobility of devices, we should know the future mobility events to solve this problem. Unfortunately, estimating future mobility events is intractable as mentioned at observation (i) in section II, so we assume that pursuing the optimal solution under the current G is the best under the current status. Even in this assumption, our simulation results show enough energy saving under the real mobility scenario. TABLE I: Decomposed Problems and Solutions Problems Solutions for all n Dual  problem [DP] X ∗ , ∀n max λn  xin φ∗i −θn λn λn (t + Primal problem1 [PP1] X min ((Pn θn )α −λ∗n θn )) θ i∈I ∗ (t)) T ) = λn (t)+β(ρn (t)−θn n∈N n 1/(α−1) /Pn , if α > 1, ∗ (t) = (λn (t)/α) θn ρn (t), if α = 1, min φ X i∈I problem2 Primal   [PP2] X X φi λ∗n xin , s.t. φi = 1 n∈N i∈I Centralized, NP-hard [18] θn∗ becomes small by (7), so λn (t) increases at even small increment of GPS-on ratio, which affects a decrement of GPSProblem Decomposition. We can solve the [P-EOL] problem on ratio. Therefore, more fairness is enforced. When α = 1, to find the GPS-on time portion θn of each device n using the virtual queue λn is the same for all time and all devices. the primal-dual technique [19]. The Lagrangian function of Therefore, φ in [PP2] is selected when the number of G[P-EOL] is given by: leaders satisfying a feasible G-leader set condition is minimum !! X X (i.e., total energy consumption is minimized). This means that (Pn θn )α + λn xin φi − θn ) , (5) the solution absolutely does not consider fairness. L(θ, φ, λ) = B. Optimal Solutions n∈N i where λn ∈ λ is a dual variable for satisfying the constraint (2). From the primal-dual decomposition, the original problem [P-EOL] is divided into the primal-dual problems as shown in Table I. By iteratively solving the three decomposed problems as follows, we can find an optimal G-leader (GPS-on) time portion of each device. Let t = kT for some nonnegative integer k = 0, 1, 2, ... and T > 0 is a constant. 1) [DP] solution: Using the form of distributed gradient method [20] in [DP], dual variable λn of each device n can be updated per each t = kT as a follow. λn (t + T ) = λn (t) + β(ρn (t) − θn∗ (t)) (6) where ρn (t) denotes the actualPGPS-on ratio of device n for last T which is equivalent to i∈I xin φi in [DP], θn∗ (t) is a solution of [PP1], and β > 0 is a constant. 2) [PP1] solution: We can easily derive the θn∗ (t) by applying Karush-Kuhn-Tucker (KKT) conditions [21] because [PP1] is a convex function. The derived θn∗ (t) is as a follow. ( 1/(α−1) /Pn , ∀n ∈ N , if α > 1, (7) θn∗ (t) = (λn (t)/α) ρn (t), ∀n ∈ N , if α = 1, 3) [PP2] solution: [PP2] is a problem to find a G-leader set i which has the minimum sum of virtual queues in all possible G-leader sets at time t = kT . Therefore, while [DP] and [PP1] can be solved by distributed manners, [PP2] is centralized problem where the problem is NP-hard [18], and solver of the problem should know all SRC connectivity G information in order to find φ. So in the next subsection, we present a fully distributed algorithm which contains the distributed solution of [PP2]. Solution Mechanism. The dynamics in (6) can be considered as a queueing system (we call a virtual queue) in which the arrival quantity is ρn and departure quantity is θn∗ . When α > 1, the virtual queue λn is operated to achieve fairness among devices. For example, λn increases if device n is sufficiently selected as the G-leader compared to θn∗ , i.e., ρn > θn∗ . Then, the device is less selected since the solution of [PP2] finds devices whose sum of virtual queues is minimum. Then, the GPS-on ratio of the device decreases. This mechanism forms a negative feedback of (6). If α is large, the departure value C. DLS Protocol and OWD Algorithm In this subsection, we first describe a collaborative localization protocol which is operated by a distributed manners, called distributed location sharing (DLS) protocol, and design an optimal mean waiting time decision (OWD) algorithm which makes to achieve optimality of the [P-EOL] problem. Similar with CSMA/CA, our DLS protocol is operated by the competition among neighbors for turning off GPS based on the different randomly selected waiting time of each device. By doing so, a sequence of the selected G-leader set becomes reversible Markov chain which has stationary distribution depending only on the waiting time. In OWD algorithm, we inherit the distributed solutions of [PP1] and [DP] problems, and develop a distributed optimal solution for remained [PP2] problem. This algorithm controls an mean waiting time of each device with only the past GPS-on statistics, which makes DLS protocol find optimal GPS-on time portion of each device. Distributed Location Sharing Protocol. We inherit the idea from well-known CSMA/CA [22] for the distributed operation, where the key operations are carrier sensing and random waiting time. Similarly, our protocol selects a G-member set (it is a complementary G-leader set) by individual operations, neighbor sensing and random waiting time, of each device. Neighbor sensing: each device listens location values broadcasted from G-leaders for checking competition devices who are turning on GPS as well as GPS sharing. We assume that each device can know identifications of neighbors using the SRC. Therefore, each device can know the number of competition devices. Random waiting time: if there exist neighbors who are G-leaders, the devices compete for turning off GPS with randomly selected waiting time between 0 and maximum waiting time, e.g., the device who selects shorter waiting time is winner. Also, each device has the maximum waiting time which is controlled and updated every T time by OWD algorithm. Next, we deal with four practical problems in DLS protocol. (i) How to communicate among devices with short range communication? We consider four types of messages: location value, GPS-on/off, NO message. The location value means longitude and latitude acquired by the GPS measurement. This value is broadcasted by G-leader at every tGP S . The GPS-on/off messages mean that some device informs that the device turns on or off GPS to neighbors. The NO message is used for feasibility condition. (ii) How to detect device topology? Since the neighbors content based on hearing of GPS-on/off and location value messages, they do not need additional messages for topology detection. The devices can know the number of neighbors or competitors based on the location values which are received during past tGP S . (iii) Which location value is selected if a certain device receives several GPS location values from several GPS-on devices? Since the devices do not measure signal strengths of SRC, the devices do not know which devices are closer. Therefore, we make a decision that the devices who received location values from several devices calculate their locations as the average of all received location values. (iv) What happens if the SRC links are broken while the location sharing? The GPSoff devices turn on GPS and broadcast their location values, then the devices naturally participate in the competition under the newly determined SRC connectivity. In summary, the DLS protocol can be presented by a flowchart as Fig. 2. : Feasible state set : Infeasible state set D1 D2 D3 (0,0,0) (0,0,1) (0,1,1) (1,1,1) (0,1,0) (1,0,1) (1,1,0) (1,0,0) (a) Device topology: a line between (b) Markov states: 0 denotes devices represents that two devices are GPS-on, 1 denotes GPS-off neighbors Fig. 3: Example: device topology and Markov states Waiting time D1 Waiting NO message After waiting time, D1 broadcasts GPS-off message After waiting NO message, D1 turns off GPS during GPS-off duration D2 receives NO message from D1 after broadcasting GPS-off message D2 D2 loses competition Location sharing every After waiting time, D3 and turn on GPS broadcasts GPS-off message After waiting NO message, D3 turns off GPS D3 Fig. 4: Example: distributed location sharing protocol G-leader (GPS on) G-member (GPS off) Measure & broadcast location value Receive location value? YES NO Neighbor sensing? Count # of neighboring G-leaders & calculate avgerage location GPS-off competition Count # of competitors Randomly select & wait Receive GPS-off message & # of neighbor G-leaders=1? Send NO message # of competitors=0? GPS-off duration is over? Broadcast GPS-off message Receive NO message? Send GPS-on message Fig. 2: Flowchart of distributed location sharing protocol In Fig. 2, we consider three states of a device, each of which represents G-leader (GPS-on), G-member (GPS-off) and GPS-off competition state. At G-leader state, each device measures GPS and broadcasts the location value every tGP S . If the device listens location values or GPS-on messages from neighbors during tGP S , (neighbor sensing), the device goes to the GPS-off competition state. At G-member state, each device listens location values from its G-leaders. Then the device calculates an average location based on received location values. If the device receives GPS-off message from its only one G-leader, the device sends NO message. If GPSoff duration is over, the device broadcasts GPS-on message and goes to GPS-off competition state. If the device cannot receive location values, the device goes to the G-leader state. At GPS-off competition state, each device checks the number of neighbors who are G-leaders based on GPS-on messages or location values during tGP S . Then, the device randomly selects waiting time τ̃n between 0 and maximum waiting time τn which is updated by OWD algorithm, and waits for τ̃n . If the number of competitors becomes zero, the device goes to G-leader state, otherwise, broadcasts GPS-off message. If the device receives NO message after broadcasting GPS-off message, the device loses competition and goes to G-leader state. We present a simple example of the DLS protocol. In Fig. 3(a), D1-D3 devices are located where D1, D2 are neighbors and D2, D3 are neighbors. From this SRC connectivity, we can model Markov states as shown in Fig. 3(b). For the feasible G-leader set condition, the probabilities to the infeasible state sets from other state sets should be zero. To that end, we introduce ”NO message” which prevents going to the infeasible state sets. For example, assume that waiting times of D1, D2 and D3 are initially selected by the order of D3 > D2 > D1 as shown in Fig. 4. Then, D1 first broadcasts GPS-off message. Since D2 is in the GPSoff competition state, D2 does not send NO message. After waiting time, D1 turns off GPS. Next, D2 broadcasts turn off message. Since D1 is turning off GPS, D1 sends NO message to D2 in order to prevent going to the infeasible state. After then, D2 loses competition, and turns on GPS. Finally, after transmitting GPS-off message and waiting NO message, D3 turns off GPS during GPS-off duration. Optimal mean Waiting time Decision Algorithm. The DLS protocol is continuously operated by the fully distributed mechanism depending on the only maximum waiting time, which is double of mean waiting time. To find optimal solution of [P-EOL] problem by DLS protocol, we develop an optimal mean waiting time decision (OWD) algorithm. Since [PP1] and [DP] problems can be solved by distributed manner, the remaining issue is to find distributed optimal solution of [PP2] in Table I. From now on, instead of [PP2], we use the complementary maximization form as follows. Lemma 1. Denote by yni the GPS-off indicator of device n in G-leader set i, i.e., yni = 1 if device n is in G-member state, and yni = 0 otherwise. Then, [PP2] is equivalent to !! X X X i φi = 1. (8) , s.t. λn yn φi max φ i i n∈N Proof: See our technical report [17]. Let τ = [τ1 , ...τ|N | ]T be a vector of the mean random waiting time, and µ = [µ1 , ...µ|N | ]T be a vector of the mean GPS-off duration. If each device n runs a DLS protocol in Fig. 2, the G-member selection procedure follows a Markov chain in which a state is a G-member set. Consider a state y i and a device n who is a G-leader, i.e., yni = 0, and has at least one neighboring G-leader. Then, state y i transits to state y i + en with rate 1/τn , and state y i + en transits to state y i with rate 1/µn , where en is a |N | vector whose nth value is 1 and other values are 0s. If the device n has no neighboring G-leader, then state y i cannot transit to state y i + en due to the NO message in Fig.2. Thus, similar to the CSMA Markov chain in [22], the Markov chain of the G-member selection is reversible, and the stationary distribution is given by: Q µn φi (τ ) = P i =1 τ n:yn n i′ ∈I Q µ′n i′ =1 n′ :yn τn′ ′ . (9) This equation shows that a G-member set i is more frequently visited in the Markov chain if it contains devices with low waiting time. We assume that µn of all devices are constants. We control a parameter τ to solve [PP2] for given λ as a follow. τn = µn exp(−Bλn ), ∀n ∈ N . (10) where B > 0 is a constant. Then, the following result is an immediate consequence of the rule in (10). Theorem 1. Fix λ and consider a DLS protocol under the waiting time satisfying (10). Then, in steady state, the optimal G-leader set of [PP2] is visited only and all as B goes to infinity. Proof: If a DLS protocol runs with a waiting time satisfying (10), a time fraction (or stationary distribution) of G-member set i, φi , is given by: P exp(B n∈N λn yni ) P . (11) φi (τ ) = P i′ n∈N λn yn ) i′ ∈I exp(B P Let U (i) = n∈N λn yni and I ∗ be a set of i in which U is to be a global maximum. Note that points in set I ∗ are one of solutions of [PP2] from Lemma 1. Next, divide numerator and denominator of (11) by ekB where k = maxi U (i). Then, φi (τ ) = P = i′ ∈I ∗ e(B(U (i)−k)) P (B(U (i)−k)) + i′ ∈I / ∗e e(B(U (i)−k)) e(B(U (i)−k)) P (B(U (i)−k)) |I ∗ | + i′ ∈I / ∗e (12) (13) As B goes to infinity, the time fraction of G-member set i is given by:  1 if i ∈ I ∗ , |I ∗ | , lim φi (τ ) = (14) B→∞ 0, if i ∈ / I ∗, since eB(U (i)−k) goes to 0 if U (i) < k and 1 if U (i) = k. Thus, the Markov chain visits only and all the optimal Gmember set of [PP2] equally likely. Now, we can describe our optimal mean waiting time decision (OWD) algorithm by the optimal solutions of three decomposed problems in Table I as follows. OWD: Optimal mean Waiting time Decision Algorithm Let t = kT for some nonnegative integer k = 0,1,2,... and T > 0 is a constant. Every kT , each device updates mean waiting time τn (kT ) by the following mechanisms for all n. τn (t + T ) = µn exp(−Bλn (t)), (15) !#+ 1 (" ( λnα(t) ) α−1 , if α > 1,(16) Pn λ (t+T )= λn (t)+β ρn (t)− n λn (t), if α = 1, where ρn (t) is the GPS-on ratio of device n for T . The mean waiting time τn is operated to stabilize its virtual queue. For example, the virtual queue λn (t) increases when the device n is sufficiently selected as G-leader by (16). Then, τn (t) decreases by (15), so the device n try to turn off GPS with high probability. This forms a negative feedback mechanism. Note that the DLS protocol continuously operates even though mean waiting time and virtual queue are updated by OWD algorithm for every T . IV. E VALUATION To verify the optimality of our scheme (DLS protocol and OWD algorithm), and compare with existing algorithms in specific scenario, we first consider fixed topology scenarios. After then, we verify the performance of DLS+OWD and the other algorithms under real mobility trace in KAIST campus. A. Verification under Sample Topologies Setup. We consider four topologies, each of which has different SRC connectivity among devices as shown in Fig. 5. Also, we use a Bluetooth inquiry protocol for SRC, and the average power consumption for transmit/receive of Bluetooth signal is 110.5mW [11]. Due to limited space, justifications about four topologies and detailed explanation about Bluetooth inquiry protocol are available in our technical report [17]. A reference GPS power consumption is 440mW [5]. In OWD algorithm, β, B and a initial virtual queue are set to be 0.1, 0.1 and 50, respectively. We establish the GPS-off duration as 10 seconds, and the location sharing period, i.e., tGP S , is 1 second. As performance metrics, the average GPS power consumption and Jain’s fairness index [25] are considered. Verification of Optimality. We verify an optimality of DLS+OWD under a star topology (Fig. 5(c)). For comparison, we consider an optimal centralized solution (OPT) which finds k[ k] (a) Symmetric k[ kX kY k] kX k[ k^ (b) Complex1 kZ kY k\ k[ kX k\ k^ 400 300 250 200 150 100 50 1 2 3 6 0.8 0.7 DLS+OWD OPT 0.6 0.5 0.4 0.3 0.2 1 2 3 4 5 6 Fairness parameter [ ] (b) Jain’s fairness index vs. fairness parameter α Fig. 6: Verification of optimality 350 1 300 250 200 150 Low-ID High-C HEED DLS+OWD with =2 100 50 Symmetric Star Complex1 Complex2 Fig. 7: Average power consumption Jain's fairness index Average power consumption [mW] 5 (a) Average GPS power consumption vs. fairness parameter α Fig. 5: Device topologies 0 4 0.9 Fairness parameter [ ] (d) Complex2 (c) Star DLS+OWD OPT No Col. 350 kZ k\ 1 Jain's fairness index kZ Average GPS power consumption [mW] kY kY kX 450 0.9 Average number of messages 0.8 Topologies 0.7 Low-ID, High-C, DLS+OWD HEED with α=2 Symmetric 1 0.8481 Star 1 0.7785 Complex1 1 0.8536 Complex2 1 0.7978 0.6 0.5 0.4 Low-ID High-C HEED DLS+OWD with =2 0.3 0.2 0.1 0 Symmetric Star Complex1 Complex2 Fig. 8: Jain’s fairness index optimal φ in [PP2] problem with a global knowledge of SRC connectivity. Fig. 8 shows the average GPS power consumption and Jain’s fairness index for the fairness parameter α: DLS+OWD approach to OPT for all fairness parameters (α=16) in both terms of average GPS power consumption and fairness. Comparison with Other Algorithms. We compare the performance of DLS+OWD with the other clustering algorithms (Low-ID [14], High-C [15] and HEED [16]) in four different topologies as shown in Fig. 5. In the existing algorithms, devices exchange costs (random numbers (Low-ID), inverse of the number of connectivity (High-C) and inverse of the number of connectivity plus residual energy (HEED)) with neighbors and select a device having the lowest cost as a cluster head which turns on GPS. Figs. 7, 8 show the GPS+Bluetooth power consumption and the Jain’s fairness index. (i) For all topologies, Low-ID tends to select a cluster head with fair time portion for all devices, so the average power consumption is high although the fairness is highly maintained. High-C always select the same devices as cluster head, so the fairness is very low. HEED strives to increase fairness than High-C, but still it has lower performance than DLS+OWD with α=2. (ii) Especially, in Fig. 5 (b), (d), DLS+OWD with α=2 outshines HEED and High-C (up to 27.2% power saving with 35.8% higher fairness). This is because our OWD algorithm strives to find an optimal G-leader set which minimizes sum of square of GPS power in α=2 whereas High-C and HEED cannot find this optimal G-leader set. Table II shows the normalized average number of messages of our scheme while the other algorithms use the constant number of messages. (iii) For all topologies, TABLE II: Normalized average number of message passing among devices the DLS+OWD uses 15-22% of fewer numbers of message passings than the other algorithms. B. Verification under Real Mobility Trace Setup. We delegate mobility trace data of 93 students in KAIST campus at Monday to Thursday PM 1:00 to PM 8:00 (for seven hours). We assume the Bluetooth coverage is 10m [12]. The other assumptions are the same as the device proximity analysis in Section II. Also, the GPS-off duration and location sharing period as well as the GPS and Bluetooth settings are the same as Section IV-A. The fairness parameter α is set to be 2. As performance metrics, we consider average power consumption (GPS+Bluetooth) of all devices, Jain’s fairness index and average location difference from GPS, i.e., degree of accuracy of localization scheme. Performance Comparison with Other Algorithms. Fig. 9 shows the average power consumption, Jain’s fairness index and average location difference from GPS of 93 students: (i) our DLS+OWD with α=2 reduces the average power consumption by 65.5% compared to no collaboration, and by 27.4% compared to HEED under 25% higher fairness even in real mobility trace simulation. (ii) Location difference from GPS of all algorithms are much smaller than 8.8m which is the accuracy of GPS [5]. This implies that the estimated location using our scheme is not far from real location even though we do not consider accuracy in the design of DLS+OWD. V. R ELATED W ORK Localization. There was a localization approach based on the fingerprint in cellular or WiFi networks without GPS [7], [26]. 400 300 Low-IDHigh-C HEED 200 DLS +OWD 100 0 (a) Average power 0.8 DLS High-C +OWD HEED Low-ID 0.6 0.4 0.2 0 (b) Jain’s fairness index Location difference from GPS [m] No Col. Jain's fairness index Average power consumption [mW] 1 500 8 7 6 5 4 3 DLS +OWD HEED Low-ID High-C 2 1 0 (c) Accuracy Fig. 9: Performance under real mobility trace in KAIST: a black line denotes a variation of each bar. For example, in [26], a device estimates the WiFi signals and matches with the prior measured signal map to obtain its location. However, these techniques require prior signal information and are available only for given WiFi or cellular infrastructures. Localization methods using adscititious sensors of the mobile device were also considered in literatures [8], [9]. The authors in [8] use the velocity history information to determine the GPS activation period, i.e., if the velocity is lower under the same location and time, then the GPS is more sparsely activated. However, these schemes also consume the energy for using sensors, and still provide low accuracy than the continuous GPS positioning. On the other hand, our DLS+OWD do not require prior signal information, network infrastructure and additional sensors. Cooperative Communication. There were clustering studies in sensor network domains of which objective is prolonging network lifetime. Most of the optimal clustering problems in this objective is known for NP-hard [18]. Therefore, several heuristic distributed algorithms have been suggested [14]– [16], [27]. For example, HEED [16] considers both of the highest connectivity among proxy devices and residual energy of each device. Recently, Lee et al. [12] presented a cooperative sensing technique between two proxy devices. However, they considered only contract-based cooperation between two devices, but did not consider the energy efficiency and fairness of the total proxy devices. VI. C ONCLUSION The main contributions of this paper are three-folds. First, we define spatial and temporal proximity of human beings and give a motivation that collaboration with proxy devices for localization maybe achieve high energy efficiency by analyzing human mobility traces in KAIST and NCSU campuses. Second, we formulate an optimization problem which considers energy efficiency and/or user fairness for collaborative localization. However, solving this problem is hard because it requires a global knowledge of SRC connectivity and also solving a NP-hard problem. Therefore, finally, we suggest DLS protocol and OWD algorithm (DLS+OWD) which practically solve the optimization problem. The DLS protocol operates with only passive neighbor sensing and waiting time for competition to turn off GPS, and the OWD algorithm presents mean waiting time which makes the DLS protocol find an optimal solution of the problem. Also, we verify that DLS+OWD well adapt even at the unpredictably changing SRC connectivity through the real mobility trace simulation. Additional benefit of our scheme is that it can be generally applied in other sensing data sharing such as dust/UV sensors or activity observations. R EFERENCES [1] P. Mohan, V. Padmanabhan, and R.Ramjee, “Nericell: rich monitoring of road and traffic conditions using mobile smartphones,” in Proc. of SenSys, Raleigh, NC, USA, Nov. 2008, pp. 323–336. [2] “iPhone application: BikeMateGPS.” [Online]. Available: http: //bikemate.01mia.com/wp/ [3] “Google service: Google Now.” [Online]. Available: http://www.google. com/landing/now/ [4] S. Mumtaz, J. Bastos, J. Rodriguez, and C. Verikoukis, “Adaptive beamforming for OFDMA using positioning information,” in Proc. of Wireless Advanced (WiAd), London, U.K., Jun. 2011, pp. 7–14. [5] J. Paek, J. Kim, and R. Govindan, “Energy-efficient rate-adaptive GPSbased positioning for smartphones,” in Proc. of MobiSys, San Francisco, California, USA, Jun. 2010, pp. 299–314. [6] “Skyhook wireless.” [Online]. Available: http://www.skyhookwireless. com/ [7] S. Wang, M. Green, and M. Malkawi, “Mobile positioning technologies and location services,” in IEEE Radio and Wireless Conference(RAWCON), 2002, pp. 9–12. [8] I. Constandache, R. Choudhury, and I. Rhee, “Towards mobile phone localization without war-driving,” in Proc. of INFOCOM, San Diego, CA, USA, Mar. 2010, pp. 1–9. [9] M. Azizyan, I. Constandache, and R. Choudhury, “Surroundsense: Mobile phone localization via ambience fingerprinting,” in Proc. of MobiCom, Beijing, China, Sep. 2009, pp. 261–272. [10] H. Labiod, H. Afifi, and C. Santis, WiFi, Bluetooth, Zigbee and WiMAX. Springer, 2007. [11] “Bluetooth for device discovery networking guide,” [Online] Available: http://www.libelium.com/documentation/waspmote/. [12] Y. Lee, Y. Ju, C. Min, S. Kang, I. Hwang, and J. Song, “CoMon: cooperative ambience monitoring platform with continuity and benefit awareness,” in Proc. of MobiSys, L. District, UK, Jun. 2012, pp. 43–56. [13] K. Lee, S. Hong, S. Kim, I. Rhee, and S. Chong, “SLAW: self-similar least action human walk,” IEEE/ACM Transactions on Networking, vol. 20, no. 2, pp. 515–529, Apr. 2012. [14] D. Baker and A. Ephremides, “A distributed algorithm for organizing modeling radio telecommunication networks,” in Proc. of ICDCS, Paris, France, Apr. 1981, pp. 476–483. [15] A. Parekh, “Selecting routers in ad-hoc wireless networks,” in Proc. of SBT/IEEE ITS, Aug. 1994, pp. 420–424. [16] O. Younis and S. Fahmy, “HEED: a hybrid energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366–379, 2004. [17] J. Kwak, J. Kim, and S. Chong, “Energy-optimal collaborative GPS localization with short range communication,” Technical Report, Jan. 2013. [Online]. Available: http://netsys.kaist.ac.kr/publication/papers/ Resources/R4 [18] P. Agarwal and C. Proopiuc, “Exact and approximation algorithms for clustering,” in Proc. of the 9th annual ACM-SIAM SODA, Baltimore, MD, Jan. 1999, pp. 658–667. [19] A. Stolyar, “Greedy primal-dual algorithm for dynamic resource allocation in complex networks,” Queueing Systems, vol. 54, no. 3, pp. 203–220, Jul. 2006. [20] R. Gibbens and F. Kelly, “Resource pricing and the evolution of congestion control,” Automatica, vol. 35, no. 12, pp. 1969–1985, 1999. [21] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge Univ Press, 2004. [22] L. Jiang and J. Walrand, “A distributed CSMA algorithm for throughput and utility maximization in wireless networks,” IEEE/ACM Transactions on Networking, vol. 18, no. 3, pp. 960–972, Jun. 2010. [23] R. Jain, The art of computer systems performance analysis. John Wiley and Sons, 1991. [24] J. Park, D. Curtis, S. Teller, and J. Ledlie, “Implications of device diversity for organic localization,” in Proc. of INFOCOM, Shanghai, China, Apr. 2011, pp. 3182–3190. [25] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energyefficient communication protocol for wireless microsensor networks,” in Proc. of ICSS, Jan. 2000.