=Paper=
{{Paper
|id=None
|storemode=property
|title=Towards Using Location Poly-Hierarchies for Energy-Efficient Continuous Location Determination
|pdfUrl=https://ceur-ws.org/Vol-850/paper_schirmer.pdf
|volume=Vol-850
|dblpUrl=https://dblp.org/rec/conf/gvd/SchirmerH12
}}
==Towards Using Location Poly-Hierarchies for Energy-Efficient Continuous Location Determination==
https://ceur-ws.org/Vol-850/paper_schirmer.pdf
Towards Using Location Poly-Hierarchies for
Energy-Efficient Continuous Location Determination
Maximilian Schirmer and Hagen Höpfner
Bauhaus-Universität Weimar
Media Department / Mobile Media Group
Bauhausstraße 11, 99423 Weimar, Germany
maximilian.schirmer@uni-weimar.de, hoepfner@acm.org
Keywords other hand, indoor GPS positioning is almost impossible because of
Location Determination, Location Poly-Hierarchies, Energy Effi- the occlusion and shielding of satellite signals created by building
ciency structures.
Mobile devices are battery-driven. So, energy is one of the most
limiting factors for their uptime. Additionally, the user acceptance
ABSTRACT of location-based or context-aware mobile applications is nega-
Location awareness is a key feature of mobile information systems. tively influenced when the applications heavily strain the mobile
Typically, location is determined by interpreting a set of measured devices’ batteries. Furthermore, location-based applications differ
positions. Various approaches for position determination do exist. in their required precision [16]. While the name of the city a user
They vary greatly in their precision, applicability, and energy re- or a device is currently located in might be appropriate for an event
quirements. As mobile devices are battery-driven, energy is one of information system, a navigation system might demand for exact
the most limiting factors for the system’s uptime. Locations have coordinates or street names at least. A common representation of
a hierarchical nature and location-based applications differ in their locations follows their hierarchical nature. In a hierarchical model,
required precision. In this paper, we present three approaches that earth is divided into continents, continents into countries, countries
utilise location poly-hierarchies in order to reduce the energy de- into states, states into cities, cities into streets and streets into street
mand of continuous location determination: (1) We analyse the numbers, and so on. Consequently, determining low-level location
dependencies among the different hierarchy levels, (2) we incor- information in this hierarchy also determines upper levels and con-
porate an adaptive delay between measurements based on the hier- tains information that is connected to these levels. In addition to
archy level and the calculated minimal required time to change, and this, locations only change if the device is moving. While GPS
(3) we select appropriate positioning techniques for each hierarchy coordinates might change with each movement, city information is
level. We implemented and evaluated our approaches. stable until the device leaves the city. Hence, the system might wait
with the next energy-demanding location determination on the city
1. INTRODUCTION AND MOTIVATION level until the device possibly left the city. In this paper, we present
Navigation systems, social network apps, tourist information sys- three approaches that utilise location poly-hierarchies for reducing
tems, event information systems, shop finders and many more heav- the energy demand of continuous location determination:
ily rely on position data of their users. Consequently, almost all 1. We analyse dependencies among different hierarchy levels.
modern smartphones supply positioning techniques. The most pop-
ular positioning technique is the Global Positioning System (GPS). 2. We postpone position measurements based on a calculated
However, even devices that do not provide GPS hardware are able minimal time that is required for leaving the current location.
to locate themselves using alternative techniques such as geotagged
Wi-Fi hotspot and cell tower databases (db), wireless signal trian- 3. We select appropriate positioning techniques for each hierar-
gulation/lateration, or geotagging. Although all of them allow lo- chy level.
calisation of a mobile device, they vary dramatically in precision,
applicability, hardware requirements, and energy demands. A GPS Our preliminary experimental results show that there is a strong po-
request requires a GPS receiver with a much higher energy demand tential in these techniques to reduce the energy demand compared
compared to an on-device database lookup that is based on already to continuous GPS polling.
localised cell towers or Wi-Fi hotspots [4]. However, in an outdoor The remainder of the paper is structured as follows: Section 2
scenario, GPS is far more precise than the analysis of location in- discusses related work. Section 3 introduces the concept of loca-
formation of connected Wi-Fi hotspots or cell towers [22]. On the tion hierarchies. Section 4 presents the three aforementioned ap-
proaches. Section 5 describes the evaluation approach and the re-
sults. Section 6 summarises the paper.
2. RELATED WORK
Our work mainly overlaps with the research fields location mod-
els and energy-aware computing. Location models form the basis
for all high-level operations on location data. Consequently, the
24th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. frequent and enduring use of location data in mobile computing
Copyright is held by the author/owner(s). immediately raises the issue of the mobile devices’ limited energy
resources. The field of energy-aware computing presents a variety requires dedicated software engineering with new concepts and al-
of concepts and methods to compensate for these constraints. gorithms [9].
One concept of energy-aware computing is resource substitution
2.1 Location Models [3]. It is based on the observation that in most cases, alternative
Location models as core components of location-based appli- resources exist for a given resource. These alternatives often vary
cations represent location information and spatial (or even spatio- greatly in their costs (e.g., computing power, storage capacity, or
temporal [15]) relationships in data. They help to express relative energy demands), but also in their accuracy, granularity, and fre-
locations, proximity, and allow users to determine containment of quency of data updates. This directly influences their appropri-
locations or connectedness of relationships. ateness for substitution. In general, resource substitution favours
The authors of [21] present in great detail the broad variety of resources with a lower cost (energy requirements) over expensive
location models that have been developed in recent years of active (high-energy) alternatives. In many cases, a high-energy resource
research. A key factor for distinguishing and characterising loca- is not necessarily required and can be substituted without measur-
tion models is their way of representing spatial relationships. Ac- able impact on system performance or user acceptance [19].
cording to [1], they can be categorised into set-based, hierarchical, The authors of [17] utilise resource substitution in the form of
and graph-based models. Hybrid models that combine several as- sensor substitution. In a location-based context, data from a GPS
pects exist as well. Figure 1 presents an overview of the three main device is often substituted with triangulation or lateration data from
concepts. In the illustrated examples, the set-based approach is the cell towers or Wi-Fi stations. A comparable concept is sensor trig-
least expressive one, as it only models the fact that there are two gering, where logical dependencies between different sensors are
distinct locations within a set of locations, and a set of coordinates used. When low-energy sensors detect changes in the environment,
is assigned to each location. The hierarchical model adds contain- a detailed update with high-energy sensors is triggered. An exper-
ment information, and the graph-based model adds connectedness iment described in [17] shows that low-energy accelerometer data
as well as distance in the form of edge weights. can be used to trigger high-energy GPS sampling. This approach
greatly reduces the energy demand of location determination for
mobile applications that do not require a gap-less reconstruction of
Location A
Location A World routes. This triggering approach has also been applied in the area of
(1,2)
(1,2) (1,3) (2,3) (2,4) (1,2)
civil engineering, where it is critical that autonomous sensor nodes
50
60
25
in buildings gather highly detailed data when vibrations occur. In
Location B Location C the “Lucid Dreaming” system [13], a low-energy analogue circuit
Location B Location A Location B
(2,4) (1,3) is sufficient to watch for these environment changes. It triggers
(2,3)
(1,2) (1,3) (2,3) (2,4)
a high-energy microcontroller-based sensor to gather the required
25 100
fine-grained data.
Location D Location E
Location c
10
(1,2) (2,3) (2,5)
3. TERMS AND DEFINITIONS
(a) (b) (c) According to [18], “location of an object or a person is its geo-
graphical position on the earth with respect to a reference point.”
Figure 1: Examples for different popular location models: set- From our viewpoint, this definition is too restrictive, as geographic
based (a), hierarchical (b), and graph-based (c). The edge positions are points. In contrast to a point, a location has a spatial
weights in the graph-based model represent distance informa- extent. Due to [5], “geographic location is the text description of an
tion. area in a special confine on the earth’s surface.”. However, an area
is a set of geographical positions. So, we use a set-oriented defini-
tion: A location is a named set of geographical positions on earth
Hierarchical location models as a special case of set-based mod- with respect to a reference point. In a two-dimensional coordi-
els represent containment relationships between different levels of nate system, e.g., the location of a building is given as a set, where
the model and are widely used as basis for location-based appli- each position (point) belongs to the building’s area. We do not dis-
cations [14, 2, 6]. They cannot represent distance information or cuss the calculation of point sets here, but rather refer to techniques
directly encode proximity, but they have great advantages in traver- of geographical information systems (GIS) [7]. The location mod-
sal and for containment queries. They are very close to the com- els presented in Section 2.1 describe relationships among locations.
mon human understanding of locations. Almost everyone under- However, reality requires a more sophisticated location model. Is-
stands the widely acknowledged segmentation of locations into ad- tanbul, as the capital of Turkey, belongs to Europe and Asia. The
ministrative regions (country, state, city, street, etc.). At this, on same issue holds for Russia, which is located in Europe and in Asia,
a city level, a lot of implicit information can be derived through too. Another problem results from enclaves: Kaliningrad is part
the top-level relationship to a state or country (e.g., administrative of Russia, but this information is not sufficient to decide whether
language, local cuisine, prevalent religions). Kaliningrad belongs to Europe or Asia. The solution for these prob-
lems is to use set overlaps instead of containment relationships in
2.2 Energy-aware Computing combination with a poly-hierarchical location model [11].
Energy-aware computing recognises the need for energy as a Figure 2 illustrates the simplified poly-hierarchies for Istanbul
factor in modelling and implementing computing systems in or- and Kaliningrad, represented as directed acyclic graphs. Each node
der to manage and reduce their energy demand. This includes both is a location and each directed edge represents that the child node
hardware and software systems. While energy-aware hardware has belongs (semantically) to the parent node(s). Moreover, the location
been under active research for many years, energy-aware software poly-hierarchy LP H has a unique root node because the entire co-
is still a novel and underestimated field of research. Hardware solu- ordinate system is closed in case of locations (all considerable po-
tions such as sleep modes or performance scaling cannot be directly sitions are elements of the set of all positions on earth). We do not
transferred or adapted to software systems. Energy-aware software discuss the construction of LP H in this paper, but assume that an
and Asia. So, the number of comparisons depends on the structure
earth
earth
of the given poly-hierarchy. Our algorithm calculates the correct
path for a given location while minimising the number of compar-
isons. We assume that the names of the leaf and inner nodes in
Europe
Asia
Europe
Asia
LP H are unique and referenced within the GIS db.
earth
earth
earth
earth
earth
Russia
Russia
Europe
Asia
Europe
Asia
Europe
Asia
Europe
Asia
Europe
Asia
Russia
Russia
Russia
Russia
Russia
Istanbul
Istanbul
Istanbul
Istanbul
Istanbul
Istanbul
Kaliningrad
(a) (b) (c) (d) (e)
(a) (b)
Figure 3: Traversing the location poly-hierarchy in case of Is-
Figure 2: Poly-hierarchical example locations: Istanbul (a), tanbul.
Kaliningrad (b).
earth
earth
earth
earth
expert defined it in advance. Furthermore, we assume that the level Europe
Asia
Europe
Asia
Europe
Asia
Europe
Asia
of a node is defined as the number of nodes on the longest direct Russia
Russia
Russia
Russia
path from root to this node, plus one. As illustrated in Figure 2(b),
level(Russia) = 2 and level(Kaliningrad) = 3. Kaliningrad
Kaliningrad
Kaliningrad
Kaliningrad
(a) (b) (c) (d)
4. LOCATION DETERMINATION STRATE-
Figure 4: Traversing the location poly-hierarchy in case of
GIES Kaliningrad.
The research question addressed in this paper is twofold: we
want to continuously determine the location of an object while re-
ducing the energy requirements for positioning, and we want to The algorithm works as follows (cf. Figures 3 and 4): At first, the
offer location information that is appropriate for different applica- proper leaf node is selected using a db query (F. 3(a); F. 4(a)). We
tion scenarios. The two extrema are: GPS polling and not mea- then traverse the LP H bottom-up and mark nodes that belong to
suring at all. Polling is the most energy-intensive approach and the correct path: The direct (grand)parent node(s) with the lowest
not measuring is the most imprecise “solution”. We developed level are analysed. If the current node has only one (grand)parent
three approaches for calculating appropriate location information node in this level, this node is selected as path anchor (F. 4(b)).
with a minimal amount of energy. The first strategy reflects the If more than one (grand)parent node exists on the minimal level,
fact that memory-intensive computations require much more en- we check them with a db query (F. 3(b)), mark the correct one and
ergy than CPU-intensive ones [8] and reduces the number of re- select it as path anchor (F. 3(c)). We continue with the path anchor
quired database lookups. The other two strategies aim for reducing until we reach the root node (F. 3(d); F. 4(c)). The last step is to
the number of GPS request and lookup operations in order to find collect the nodes on the path from root to the leaf node including
the correct path from a detected node to the root of LP H. This all marked inner nodes (F. 3(e); F. 4(d)).
path correctly describes the different levels of detail for the current
location. 4.2 Postponed Measurements
The postponed measurements strategy predicts the time required
4.1 Level Dependencies for a person or object to leave the current location. This time de-
In LP H the point sets’ cardinalities of locations represented pends on the hierarchy level, the geographical model used for this
by higher-level nodes are smaller than those of locations repre- level and on the movement speed [20].
sented by the linked lower-level nodes. The assignment of a lo- For simplification purposes, the application specifies the veloc-
cation to a set of positions uses default GIS techniques. So, a db ity of the moving object as a movement profile (pedestrians: ≈
stores border polygons, and a db lookup fetches the proper location 6 km h−1 , cyclists: ≈ 11 km h−1 , car drivers: ≈ 60 km h−1 ). The
values from the db. Hence, one location lookup requires certain most obvious approach is to take the object’s current position Lc =
memory-intensive operations. Moreover, in case of continuous lo- (xc , yc ) and then calculate the minimal Euclidean distance d to all
cation determination, queries must be performed for each move- locations within the current path in LPp H. For each location L on
ment of the requesting object. However, if we know about the this path, we have to calculate: min( (xc − xl )2 + (yc − yl )2
(semantic) dependencies among certain levels within the location |∀(xl , yl ) ∈ L). With a simple calculation, we then compute the
poly-hierarchy, we can reduce the amount of energy-intensive db time the object would need to leave this location. If, e.g., a pedes-
lookups by traversing LP H. trian is 5 km away from the city limit, he or she would need at
Figure 2(b) shows that if an object is located within Kaliningrad, least 50 minutes ( 50006000
m∗3600 s
m
= 3000 s) to leave the city. So, we
it is in Russia and Europe and on earth, too. So, only one compar- postpone the next position measurement by 50 minutes if the appli-
ison of location sets is necessary. For the example in Figure 2(a), cation requires the location at a city level. The Euclidean distance
this is not as trivial. The requesting object is located in Istanbul and guarantees the calculation of the shortest distance. Hence, if the
in Turkey. However, requesting the continent information requires velocity is correct, the calculation always returns a time window
an additional set comparison as Istanbul belongs to both Europe the moving object must be in the current location.
This approach is used for area-like locations where no route in- tions on the city level might be used in a polling mode. Anyway,
formation exists. In case of a map-based location management, we position-based location determination such as cell tower triangula-
utilise crossroad data to get more precise predictions (cf. [10]). tion in combination with a GIS requires too much calculation effort,
Therefore, we maintain a db with all crossroads and calculate the if used in a polling manner. However, we will research a combina-
Euclidian distance between the current position and the closest cross- tion of polled and time-triggered updates of location information in
road. Of course, the prediction is more exact if we use the en- a location poly-hierarchy in the near future.
tire map information but storing the complete maps would require
much space (e.g., for the German state of Thuringia, we have to 5. EVALUATION
maintain 125,034 crossroads or to store and query 657 MB of Open-
Our prototype is still work in progress. Therefore, we present a
StreetMap data).
preliminary evaluation that enabled us to estimate the energy foot-
Besides the postponement calculation for the various levels, we
print of our proposed concept in an exemplary scenario.
have to consider the poly-hierarchy as well. Referring back to the
Istanbul-Example: if the moving object is located in Istanbul, it 5.1 Experimental Setup
may take one hour to leave the city, but only 10 minutes to leave
The evaluation system was implemented as a mobile application
the continent. The solution for this issue is to analyse the LP H in
on the Android 2.3.4 platform. We conducted our tests with the
the following way. Given the LP H, the current location and the
recently released HTC Sensation smartphone. As shown in Fig-
current velocity. First we calculate the correct location path using
ure 5(b), the application is mainly a data logger for location and
the algorithm discussed in Section 4.1. In the next step, we cal-
power management data. In order to gather location data, we im-
culate the postponement value for each location in this path using
plemented a cell tower lateration algorithm, and used the Android
the appropriate calculation (Euclidian distance, crossroad analysis).
SDK’s methods for obtaining GPS data. The application reads
The minimal value determines the time until the next measurement.
energy-related data (battery voltage and current) directly from the
4.3 Level Appropriateness device’s power management. It was implemented as an indepen-
dent background logging service that gathers data even when the
There exist various technologies to measure positions such as
device is locked. The experimental setup follows our data-based
geotagged Wi-Fi hotspot and cell tower databases, wireless sig-
energy measurement approach, as described in [12].
nal triangulation/lateration, or geotagging. They vary in their en-
ergy demand and their precision. While looking at the location
poly-hierarchy one can recognise that locations represented closely
to the root node mostly require less precise location techniques.
Country information can directly be read from the country code
provided by mobile telecommunications operators. The city infor-
mation can be harvested from cell tower information using a simple
db lookup. We have to use the most high-energy GPS only if pre-
cise location information are required. The approach discussed in
the following combines the techniques illustrated in Section 4.1 and
Section 4.2.
Hierarchy level Level Technique
Earth 0 known to be true
Continent 1 Country code + Cell tower ID lookup
Country 2 Country code
State 3 Cell tower ID lookup
City 4 Cell tower triangulation
Street 5 GPS
Table 1: Location determination lookup table. (a) (b)
For the postponed measurements, we adapted the cross-level post- Figure 5: Celludroid evaluation app running on an HTC Sen-
ponement value in a way that we calculate different postponement sation smartphone.
values for each level while alternating the measurement strategy
(cf. Table 1). Let’s say that the object is located in Istanbul, and All data was stored in an sqlite database that could later on easily
that the GPS-based measurement resulted in a postponement value be used for analysis. For convenience, the application also shows
of 10 minutes for the continent, and a postponement value of 1 hour the estimated location on a map (cf. Figure 5(a)) and allows to
for the city. After 10 minutes, we then check the appropriateness explore the properties of nearby cell towers.
of the continent location using energy-efficient cell tower triangu- The cell tower lateration uses a Google service1 to look the lo-
lation and calculate a new postponement value for this level on this cation of nearby cell towers up. Because all retrieved cell tower
basis. Hence, in best case (we do not leave the continent), we can locations are cached in an sqlite database, subsequent location re-
wait with the next GPS positioning for 50 more minutes. quests for previously discovered cell towers do not require addi-
A more trivial approach supported by this idea are applications tional (high-energy) network communication.
that do not need exact position information. As mentioned above, 1
Unfortunately, access to this service is not publicly documented,
requesting the country information does not need any positioning our implementation is based on the general process documented
as the information is provided by the service provider. Further- in this forum article: http://stackoverflow.com/a/
more, less energy-intensive cell ID lookups for determining loca- 3356956
1100 GPS
Our test run consisted of a sequence of 30-minute city walks, one
1000
for each test condition:
900
a) baseline, 800
b) cell tower lateration, and 700 Cell tower
lateration
Energy [J]
600 Baseline
c) GPS. 500
In the baseline condition, the display was turned off, Wi-Fi was on, 400
GPS
Bluetooth was off, and no background tasks except our logging ser- 300 Cell tower
lateration
Baseline
vice were running. During each run, power management data and 200
cell tower locations were logged every second. GPS was requested 100
every 5 s. However, the Android SDK cannot guarantee an exact 0
time between GPS location updates. In fact, our measured time is 10 minutes 30 minutes
slightly higher (7.2 s on average).
From the power management data, we derived electrical power Figure 7: Comparison of accumulated energy demand.
and electrical energy data. In order to assess the accuracy of the
gathered location data, additional processing was necessary. While
the GPS data already included accuracy information, we computed even showed an error of more than 800 m. These extreme differ-
accuracy information for the cell tower lateration by comparing the ences highlight the fact that the reduced energy requirements of cell
gathered coordinates to their counterparts from the GPS run. This tower lateration condition have an at least equally drastic influence
enabled us to give an estimate for the upper bound of the error. on accuracy.
5.2 Results and Discussion 5.3 Scenario
The gathered results provide insight into the areas of applica-
Energy tion where sufficient potential exists to reduce the energy require-
Our results indicate that cell tower triangulation has no significant ments for continuous location determination. In this subsection, we
impact on the device’s energy demand at all. The baseline con- sketch a scenario that relies on our three conceptual pillars:
dition shows a total of 181.07 J after 10 minutes and 565.5 J after a) using level dependencies,
30 minutes, while the test run with cell tower lateration resulted in a
slightly higher 183.76 J after 10 minutes and 583.28 J after 30 min- b) postponed measurements,
utes. This difference of 1.5 % is within the measuring tolerance of c) using appropriate positioning techniques.
our method. Far more interesting is the difference between baseline
This scenario-based evaluation surely cannot serve as a proof for
1000 our proposed concept, but it provides a glimpse on its possible im-
900
800
pact. Our scenario application is a mobile tourist information sys-
700 tem for smartphones. All data is stored on the mobile device and
Power [mW]
600
500 can be accessed using db queries. The application can access the
400 following device’s location sensors:
300
200
100
a) SIM card operator’s country code (country information),
0
5 min 10 min 15 min 20 min 25 min 30 min
b) Cell tower association (state information),
Time
c) Cell tower lateration (city part/street information),
Figure 6: Comparison of power consumption for GPS (red line, d) GPS (street number information).
top) and cell tower lateration (blue line, bottom) during contin-
uous position determination. In our scenario, a tourist from Japan is on a bus tour through Ger-
many and is currently visiting Thuringia. In Weimar, she decides
and GPS condition. Figure 6 documents the power consumption to start using the tourist information system.
progress during cell tower and GPS run. In the GPS run, the device
required 316.07 J after 10 minutes and 1057.8 J after 30 minutes. Using level dependencies
Compared to baseline, this is an increase of 74.56 % after 10 min- Upon first use, the system requires a single positioning with cell
utes, or 87.06 % after 30 minutes (cf. Figure 7). Remember, GPS tower lateration. With the gathered coordinates, the country, state,
data was gathered every 7.2 s on average. In these 7.2 s, our setup and city nodes of the location poly-hierarchy can be determined:
required 4896 mJ of energy on average (7.2 s · 680 mJ s−1 ). In the earth→Europe→Germany→Thuringia→Weimar. The system
baseline condition, 7.2 s of idling required 1296 mJ of energy on uses this data to switch to the tour mode for Thuringia.
average (7.2 s·180 mJ s−1 ), which is 26.5 % of the amount required
for GPS. Using appropriate techniques according to level
In this mode, a continuous perimeter search delivers points of in-
Accuracy terest, such as restaurant, museums, public places, or theaters. Be-
The results regarding accuracy of the position determination tech- cause this feature at this point only requires the general information
niques are very clear. While the GPS condition results show an about the presence of such points of interest (and not a detailed
average of 9.2 m, cell tower lateration performs drastically worse routing information on how to get there), it is appropriate to rely on
at 308.26 m (a difference of 3242.55 %). Some outliers in the data cell tower lateration.
Postponing unnecessary measurements [5] Z. Dongqing, L. Zhiping, and Z. Xiguang. Location and its
When the tourist finished exploring the city, she wants to find a nice Semantics in Location-Based Services. Geo-spatial
place to have lunch. After selecting one of the restaurants from the Information Science, 10(2):145–150, June 2007.
perimeter search result list, the tourist information system enters [6] F. Dürr and K. Rothermel. On a location model for
the navigation mode. In this mode, a database of intersections is fine-grained geocast. In UbiComp ’03 Proc., pages 18–35.
used in combination with a movement profile to estimate important Springer, 2003.
turning points along a route where it is necessary to activate the [7] I. Heywood, S. Cornelius, and S. Carver. An Introduction to
GPS technique. Geographical Information Systems. Prentice Hall, Upper
Saddle River, NJ, USA, 2nd edition, Nov. 2002.
Estimation of reduced energy requirements [8] H. Höpfner and C. Bunse. Towards an energy-consumption
Upon first use, at least one GPS request can be saved. As we based complexity classification for resource substitution
have shown in the previous subsection, each request requires about strategies. In GVDB ’10 Proc., volume 581. CEUR-WS.org,
4896 mJ. The continuous perimeter search for points of interest May 2010.
took 2 hours in our scenario. During these 2 hours, a continu- [9] H. Höpfner and C. Bunse. Energy Awareness Needs a
ous GPS polling would have required about 1000 GPS requests Rethinking in Software Development. In ICSOFT ’11 Proc.,
(4896 J). In contrast, the cell tower lateration used by the sys- volume 2, pages 294–297. SciTePress, 2011.
tem only required 1296 J. Giving an estimation of the reduction [10] H. Höpfner and M. Schirmer. Energy efficient continuous
achieved by the postponed measurements in the navigation mode location determination for pedestrian information systems. In
(using the intersection database) is very difficult, as it relies on a MobiDE ’12 Proceedings, 2012. accepted for publication.
multitude of factors (e.g., velocity, distance between intersections). [11] H. Höpfner and M. Schirmer. Towards modeling locations as
A conservative lower bound would be to assume that this method poly-hierarchies. In GVBD ’12 Proc., May 2012. accepted
reduces the amount of GPS requests to 50 %. for publication, forthcoming.
[12] H. Höpfner, M. Schirmer, and C. Bunse. On measuring
6. SUMMARY, CONCLUSIONS, AND OUT- smartphones’ software energy requirements. In ICSOFT ’12
LOOK Proc., 2012. accepted for publication, forthcoming.
We addressed two research questions in the area of continuous [13] S. Jevtic, M. Kotowsky, R. P. Dick, P. A. Dinda, and
location determination: We analysed precision appropriateness and C. Dowding. Lucid dreaming: Reliable analog event
discussed energy requirements. We utilised the poly-hierarchical detection for energy-constrained applications. In IPSN ’ß07
nature of locations to provide different levels of location informa- Proc., pages 350–359. ACM, 2007.
tion. We discussed three approaches: We reduced the amount of [14] C. Jiang and P. Steenkiste. A hybrid location model with a
location calculations within the location poly-hierarchy, we intro- computable location identifier for ubiquitous computing. In
duced the concept of postponed measurements, and we discussed Ubicomp ’02 Proc., pages 246–263. Springer, 2002.
appropriateness issues in location poly-hierarchy levels. [15] T. Kauppinen, R. Henriksson, R. Sinkkilä, R. Lindroos,
The overall goal behind our research is to realise a location frame- J. Väätäinen, and E. Hyvönen. Ontology-based
work that application developers can use to implement location- Disambiguation of Spatiotemporal Locations. In IRSW ’08
aware applications without the need to take care of the high en- Proc., volume 422. CEUR-WS.org, 2008.
ergy requirements of GPS. We know that various frameworks do [16] B. N. Schilit, A. LaMarca, G. Borriello, W. G. Griswold,
exist and address the same issue. However, our results show the D. McDonald, E. Lazowska, A. Balachandran, J. Hong, and
potential to reduce the required energy further. The paper opens V. Iverson. Challenge: ubiquitous location-aware computing
various research directions that we will follow on: The concept of and the “place lab” initiative. In WMASH ’03 Proc., pages
location poly-hierarchies requires a detailed and formal definition. 29–35. ACM, 2003.
While location hierarchies and ontology-based models are well re- [17] M. Schirmer and H. Höpfner. SenST: Approaches for
searched, poly-hierarchies are rather novel. Furthermore, more re- Reducing the Energy Consumption of Smartphone-Based
search needs to be done in the area of calculating the postponement Context Recognition. In CONTEXT ’11 Proc., pages
values, and the combination of polling and postponed updates must 250–263. Springer, 2011.
be addressed. [18] A. Y. Seydim, M. H. Dunham, and V. Kumar. Location
dependent query processing. In MobiDE ’01 Proc., pages
7. REFERENCES 47–53. ACM, 2001.
[1] C. Becker and F. Dürr. On location models for ubiquitous [19] J. P. Sousa, R. K. Balan, V. Poladian, D. Garlan, and
computing. Personal and Ubiquitous Computing, M. Satyanarayanan. User Guidance of Resource-Adaptive
9(1):20–31, 2005. Systems. In ICSOFT ’08 Proc., volume SE/GSDCA/MUSE,
[2] M. Beigl, T. Zimmer, and C. Decker. A location model for pages 36–44. INSTICC press, 2008.
communicating and processing of context. Personal [20] O. Wolfson, B. Xu, S. Chamberlain, and L. Jiang. Moving
Ubiquitous Computing, 6:341–357, Jan. 2002. Objects Databases: Issues and Solutions. In SSDBM ’98
[3] C. Bunse and H. Höpfner. Resource substitution with Proc., pages 111–122. IEEE CS, 1998.
components — optimizing energy consumption. In ICSOFT [21] J. Ye, L. Coyle, S. Dobson, and P. Nixon. A unified
’08 Proc., volume SE/GSDCA/MUSE, pages 28–35. semantics space model. In LoCA ’07 Proc., LNCS, pages
INSTICC press, July 2008. 103–120. Springer, 2007.
[4] I. Constandache, S. Gaonkar, M. Sayler, R. R. Choudhury, [22] P. A. Zandbergen. Accuracy of iPhone Locations: A
and L. P. Cox. Energy-Efficient Localization via Personal Comparison of Assisted GPS, WiFi and Cellular Positioning.
Mobility Profiling. In MobiCASE ’09 Proc., pages 203–222. Transactions in GIS, 13(s1):5–26, July 2009.
Springer, 209.