Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating newcollective works for resale or redistribution to servers or lists or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
IEEE TRANSACTIONS ON MOBILE COMPUTING,

VOL. 12,

NO. X,XXXXXX 2013

1

UPL: Opportunistic Localization
in Urban Districts
Akira Uchiyama, Member, IEEE, Sae Fujii, Kumiko Maeda, Takaaki Umedu, Member, IEEE,
Hirozumi Yamaguchi, Member, IEEE, and Teruo Higashino, Senior Member, IEEE
Abstract—We propose an opportunistic ad hoc localization algorithm called Urban Pedestrians Localization (UPL), for estimating
locations of mobile nodes in urban districts. The design principles of UPL are twofold. First, we assume that location landmarks are
deployed sparsely due to deployment-cost constraints. Thus, most mobile nodes cannot expect to meet these location landmarks
frequently. Each mobile node in UPL relies on location information received from its neighboring mobile nodes instead in order toestimate its area of presence in which the node is expected to exist. Although the area of presence of each mobile node becomesinexact as it moves, it can be used to reduce the areas of presence of the others. Second, we employ information about obstacles suchas walls, and present an algorithm to calculate the movable areas of mobile nodes considering obstacles for predicting the area ofpresence of mobile nodes accurately under mobility. This also helps to reduce each node’s area of presence. The experimental results
have shown that UPL could be limited to 0:7r positioning error in average, where r denotes the radio range by the above two ideas.
Index Terms—Mobile ad hoc networks, range-free localization, urban pedestrians

Ç
1

INTRODUCTIONLOCATION

information provides people in cities withhighly personalized and reliable services such as routenavigation, location-dependent advertisements and localized communication. Since GPS does not often work inurban areas, WiFi and/or cellular base stations are also
used for localization [1], [2], [3], [4], [5], [6], [7], [8], of whichtransmission range is from 100 m to kilometers. However,receiving signals from landmarks over a distance requires
clear Line-Of-Sight (LOS), which is sometimes hard to
obtain in urban areas with tall buildings and undergroundcities. On the other hand, some other techniques assume alarge number of landmarks with short transmission range
in order to cover the target fields by these landmarks.
Another alternative is to introduce mobile landmarks thatenhance the coverage of regions [9]. This works fine if thesemobile landmarks well cover the target field. However, it isalso hard for ordinary (nonlandmark) nodes to find thosemobile landmarks.
Some techniques exploit indirect information fromlandmarks. Techniques categorized into “collaborative
multi-lateration” such as [10], [11], [12], [13], [14], [15],[16], [17], [18], [19], [20] assume that landmarks’ position
information is delivered in a multihop manner, and the
distance to the landmarks is approximated by information
on wireless ad hoc networks such as the number of hops.
The other techniques categorized into “iterative multilateration” such as [21], [22], [23], [24], [25] use the. The authors are with the Mobile Computing Laboratory, Graduate Schoolof Information Science and Technology, Osaka University, 1-5 Yamadaoka,
Suita, Osaka 5650871, Japan. E-mail: {utiyama, s-fujii, umedu, h-yamagu,
higashino}@ist.osaka-u.ac.jp, kumaeda@jp.ibm.com.
Manuscript received 18 Oct. 2011; revised 12 Feb. 2012; accepted 24 Feb.
2012; published online 28 Mar. 2012.
For information on obtaining reprints of this article, please send e-mail to:
tmc@computer.org, and reference IEEECS Log Number TMC-2011-10-0577.
Digital Object Identifier no. 10.1109/TMC.2012.86.
1536-1233/13/$31.00 ß 2013 IEEEestimated position of each node to estimate positions of
its neighbors and run this estimation process iteratively.
However, these techniques may not work well if nodes aremobile and networks are frequently partitioned, which istrue in urban areas.
To overcome this problem, in this paper, we present an
opportunistic ad hoc localization algorithm called Urban
Pedestrians Localization (UPL) designed for positioning
mobile terminals in urban areas. The key idea of UPL is thefollowing. In urban areas, we do not assume that mobile
nodes hear signals from location landmarks frequently andthat networks are fully-connected. Thus, each mobile node in
UPL maintains its own area of presence, and updates thearea whenever it encounters other nodes and receives
information about the areas of presence of those nodes.
Localization is performed by intersecting its own area ofpresence with the received ones considering the radio range.
This “opportunistic” localization does not require wellconnected ad hoc networks. On the other hand, due tomovement of mobile nodes, the area of presence expands astime passes. Let us consider an example in free space. At timet, we assume that a node’s area of presence is represented asa circle of radius u centered at point c. If the maximum speedof the node is vmax , then the area of presence of the node attime t þ t can be estimated as the circle of radius u þ vmax t centered at c. This means that the area of presence
expands quadratically with respect to vmax at each time unit.
However, actually in urban areas, mobile nodes do not movein free space but in space restricted by walls and streets.
Considering this fact, expanding the area of presence in sucha way is overcautious. Thus, our algorithm utilizes obstacle
information, and precisely determines the movable areas ofmobile nodes considering the obstacles. To do so, each node
only needs to know an obstacle map of its neighborhood.
Unlike car navigation systems, such a map is simple andlightweight to distribute.
Published by the IEEE CS, CASS, ComSoc, IES, & SPS

2IEEE TRANSACTIONS ON MOBILE COMPUTING,

The main contributions of this work are as follows:
Considering urban environments where pedestrians passeach other on pathways between buildings and in underground cities, we have designed an “opportunistic”
localization algorithm called UPL. As far as we know, thisis the first range-free ad hoc localization that is tailored tosuch environments. We note that the algorithm should becompact so as to be implemented for small devices such as
smartphones. To this goal, we provide an efficient way of
estimating mobility on a given map. To examine its
performance, extensive simulations, real experiments using
sensor nodes, and comparison with the tracking result of
iPhone 3GS have been conducted. From the simulation
results assuming a real region of Osaka downtown, UPL
could achieve smaller position errors (7 m in average with
10 m of radio range) than the two existing localization
methods by using simple devices only. Theoretical analyses
are also provided to show its property.
In our previous work [26], we have presented a newconcept of localization which well fits for positioning mobile
nodes in urban districts, and proposed an efficient localization algorithm. In this paper, we have newly investigatedthe characteristics of UPL by additional simulations and realexperiments, and have given theoretical analyses on thecomputation cost and estimation accuracy.

2

RELATED WORK

2.1 Sensor Localization
For sensor localization, many efforts have been dedicated so
far to investigate localization algorithms [27]. Range-based
positioning techniques rely on physical information between nodes [28], [29], [30], [31], [32]. These range-based
techniques are generally very accurate, e.g., positioning
accuracy in the order of centimeters, although they incur
cost for the dedicated hardware to measure distance.
On the other hand, range-based techniques using RSSI
do not generally need additional hardware for localization.
The study in [33] and [34] investigates to improve thequality of RSSI-based measurement. MDS-MAP is proposedin [16], which uses shortest path information between nodes
to estimate the distance, and uses “multidimensional
scaling” to determine the positions. Zero-configuration
localization for indoor environments using RSSI has been
proposed in [35], which automatically adjusts the distancefunction of RSSI in order to achieve robustness against
fluctuations in the radio signal. Goldenberg et al. [36]propose the Sweeps algorithm for localization in bilateration networks where the average degree is relatively low.
Sequence-based localization is presented in [37], which
utilizes the ranking of signal strength from multiple
landmarks. In urban environments, there are many buildings and walls that often cause multipath effects. In
addition, different types of wireless devices are used indifferent types of mobile terminals such as smartphones
and laptops. For this reason, RSSI measurements areunreliable in urban districts.
In contrast to range-based techniques, range-free techniques are cost effective and reliable alternatives, since they
only require communication function between nodes while

VOL. 12, NO. X,

XXXXXX 2013

the accuracy is generally lower than range-based techniques. This is because they only rely on information included
in received messages such as connectivity. Thus, they are
well-fit for urban ad hoc wireless networks. Savvides et al.
[38] have presented the following categories of localization
algorithms; hyperbolic trilateration (positioning by distances from three landmarks), triangulation (if angles are
obtained via AOA), and maximum likelihood multilateration (taking the region where the target node most likely
exists). Multilateration is further classified into the following three simple categories, called atomic, collaborative, anditerative multilateration. The atomic multilateration uses
more than two landmarks to determine a position. In thecollaborative multilateration, nodes exchange landmark
information cooperatively to be used for estimation. The
iterative multilateration uses estimated positions as newreference points and estimates the other positions iteratively. Since our proposed UPL exploits range-free multilateration, we survey similar techniques in more detail.
First, as the atomic multilateration techniques, Centroid[39] assumes landmarks with long transmission radius or alarge number of landmarks so as to cover the target fields.
Each node estimates its position by calculating the centroidof all the landmarks it hears. APIT [40] uses a set of triangles
formed by landmarks which have long transmission radius,and determines the location by checking that a node isinside or outside of each triangle. MCL [9] takes a different
approach where each node updates the set of its likelihood
points whenever it hears a signal from a landmark. IMCL
[41] applied prediction of moving directions based on MCL.
Second, as the cooperative multilateration techniques,
Ad hoc Positioning System (APS) [10], [11] approximates
the distance from an indirect landmark by several ways, by
estimation of hop distance or the number of hops. Savarese
and Rabaey [12] present a similar hop-based approach.
Amorphous [13] is also range-free localization that utilizes
hop counts from landmarks as well, where each node
estimates its coordinates by finding coordinates thatminimize the total squared error between the calculated
and estimated distances. Yang et al. [14] propose HCRL
which exploits hop count ratios to landmarks from eachnode and transmission power control to increase accuracy.
Self-configurable positioning [15] takes a similar approach
where a distance is approximated via hop-based analysis,
but then landmarks exchange the information to determine
their coordinates followed by local coordination determination performed by each node. Lim and Hou [17] present a
method to map “proximity” information, e.g., hop countinformation, between nodes into geographic distanceconsidering the characteristics of anisotropic networks.
Wang and Xiao [18] present an algorithm for sensor
positioning in concave areas based on distance bounds. Li
and Liu [19] use a boundary detection protocol for sensor
localization in concave areas. Another sensor localization
technique in concave areas is presented in [20], which
estimates reliable landmarks and utilizes them for position
estimation. For anisotropic sensor networks, Xiao et al. [42]propose sensor localization which mitigates the effect of
detour paths by relying on landmarks within a few hops.
Highly scalable sensor localization is proposed in [43],UCHIYAMA ET AL.: UPL: OPPORTUNISTIC LOCALIZATION IN URBAN DISTRICTS

based on the Ricci flow method for distorting a curved
Riemannian metric to a flat one. Wang et al. [44] identify
turning nodes, that are on the corners of the shortest paths
between nodes, for accurate distance estimation.
Finally, as the iterative multilateration, recursive position
estimation in [21] presents a fundamental technique for
iterative multilateration. Bischoff and Wattenhofer [22]present a theoretical limit of connectivity-based multihop
positioning and provide an algorithm that outperforms
hop-based algorithms. Guha et al. [23] present a range-freealgorithm called Sextant, which uses connectivity information. Sextant represents a region of presence by Bézier
curves to pursue the accuracy. Then, the region is updated
by iterative multilateration. Furthermore, study in [24]improved MCL [9] by using estimated locations ofneighbors in addition to location information from landmarks. A bounding-box method is used to reduce thecomputation time in order for finding valid samples ofMonte Carlo-based algorithms in [25].
These methods will work fine in open space and/or inconnected (i.e., not partitioned) networks that we cannot
expect in urban districts.

2.2 Localization in Urban Districts
Localization based on Wi-Fi and/or cellular networks has
been investigated for mobile nodes in urban districts. In
Place Engine [1], signal strength from multiple Wi-Fi
access points at each location (i.e., fingerprints) is used for
localization of mobile terminals. The accuracy is on theorder of 5 to 100 meters depending on the density of Wi-Fi
access points. Similar services such as Google Latitude [3]using Skyhook technology [2] and Virtual Earth [4] byMicrosoft have recently been launched. The performanceof metropolitan-scale war walking and war driving isanalyzed in [45].
Some others use signals from Global System for Mobile
Communications (GSM) cellular towers. The study in [5]measures AOA from cellular towers. TOA is also used tomeasure geographic relationships (i.e., distance/angle)
between a mobile node and cellular towers [6]. Laitinen
et al. [7] present a GSM-based localization technique using
fingerprinting. In order to achieve better accuracy, PlaceLab [8] uses Wi-Fi and GSM signals, and reduces themedian of the position errors to 15-20 meters in urban areas.
Chiu and Chen [46] use a mixed-norm approach to consider
obstruction of signals from cellular towers measured by
TOA for mobile location estimation in urban areas. LOS and
Non-Line-Of-Sight (NLOS) states of signals from basestations are switched based on a Markov process, and used
for accurate distance estimation in [47]. LAH [48] exploits
ad hoc communication between nodes and employs a linear
regression model for predicting the node mobility from
history of encountered landmarks. In the existing localization techniques for urban areas above, the error ranges fromtens of meters to kilometers, which are not sufficient toprovide various services for pedestrians in urban districts.
On the other hand, Dead Reckoning (DR) [49], [50]estimates a position based on the speed and heading of amobile node. Many recent approaches use accelerometers,
gyro sensors, and digital compasses that are available on
off-the-shelf smartphones. SparseTrack [51] combines DR

3

TABLE 1
Notationswith sparse beacon nodes to overcome cumulative errors of
DR for indoor pedestrian tracking. However, there still
remain challenges to accurate DR. For example, theaccuracy of DR changes depending on device placements
such as on a hip, in a pocket, and in a bag. Steinhoff andSchiele [52] study the accuracy of DR for different types oftrouser pockets.

3

UPL ALGORITHM

3.1 Overview and Assumption
We assume that each node is equipped with a PAN device
such as ZigBee and Bluetooth. Our algorithm does notdepend on specific hardware; however, it is not realistic toassume that each portable device continues seeking neighbors which are several tens of meters away, especially in adense crowd like in a downtown area, due to limitations ofbatteries and bandwidth. Thus, as a realistic hardware
environment, we assume these PAN technologies. Note that
it is also possible to set a high threshold on received signal
strength from existing WiFi access points to detect that anode is in the proximity of those access points. We use thenotation shown in Table 1. For simplicity of discussion, we
assume the same maximum communication range rmax for
all the nodes. We also assume the same maximum velocity
vmax for all the nodes. Hereafter, we let Rti denote an
estimated area of presence (or simply called an area ofpresence) of node i at time t. The area of presence of node idenotes the region in which node i is expected to exist.
Each node broadcasts hello messages with regularintervals to its neighbors. A hello message transmitted
from node i at time t includes the area of presence Rtii ,where ti is the time when the last localization was executedat node i, and time duration t  ti (denoted by ti ). At the
beginning of localization, Ri is unknown and initialized byreceiving known areas of presence of others (e.g., landmarks). Thus, Rtii denotes the most recently updated area ofpresence of node i, and time duration ti indicates theelapsed time from ti . Clock synchronization among mobile
nodes is not required because ti is calculated by a local
timer of node i.
We also assume that each node has a common obstacle
map M of a target region, which can be preinstalled or
downloaded from base stations such as WiFi hotspots andlandmark nodes. The data structures of areas of presence
and M are given later in Section 3.2. In UPL, obstacles aredefined as regions where pedestrians cannot always exist
and the assumed radio signal is obstructed. Thus, thick andhigh walls of metal or concrete are obstacles in most cases
but fences may be not. Note that the obstacle map does notneed to represent all obstacles, that is, the more obstacles

4IEEE TRANSACTIONS ON MOBILE COMPUTING,

Fig. 1. Localization process of UPL.

are represented by the obstacle map, the more accurate thelocalization results are. This means UPL still works even if
there is no information about obstacles. In order for
automatically constructing the obstacle map, we can simply
use image processing techniques if a digital map of theregion is available. In the real experiments in Section 5, we
extracted obstacle regions from Google Maps and Yahoo!
Maps by simple image processing. Alternatively, we may
use a map generation technique using both location
information and ad hoc communication among nodes
presented in [53].
When node i receives a hello message from node j attime t, node i immediately runs the UPL algorithm toupdate its area of presence. UPL is executed as follows:t
Node i calculates Rti and Rtj from given Rtii and Rjj where ti
and tj denote the time when the last UPL was executed at
nodes i and j, respectively (Figs. 1a and 1b). Moreover,based on the calculated Rtj where node j is expected to exist
at time t, node i calculates the region in which node j’s
signal can be heard at time t (Fig. 1c). We calculate thisregion by expanding Rtj by adding the maximum communication range rmax and it is denoted by Rtj  rmax . Finally,
we obtain the new area of presence of node i at time t, byintersecting Rti and Rtj  rmax as shown in Fig. 1d because
node i must be located in both Rti and Rtj  rmax .
We say that Rti is complete if and only if Rti contains the
position of node i at time t. Moreover, for two complete^t of node i at time t, if jRt j < jR
^t jareas of presence Rti and R
i
i
i
t
t
^
then Ri is said to be more accurate than Ri where jRti jdenotes the area of Rti . Our goal is to design an algorithm
that can determine complete areas of presence of all mobile
nodes which are as accurate as possible.
To take benefit from ad hoc localization by mobile nodes
and obstacle information, we need to calculate the movement of nodes among obstacles. Thus, we carefully design
the data structures and the algorithms which do not
overload small hand-held devices with low computational
capability. In the following sections, we present the data
structure and UPL algorithm details.
The information about areas of presence can be used formany services. For example, if service providers receive
areas of presence of shopping customers, they may send theinformation about shops and restaurants in that area. In sucha case, to avoid sending useless information for users, precise
identification of the area of presence is an important issue.
For services which need to identify the location of nodes suchas navigation systems, we also present how to determine acertain point from a given area of presence in Section 3.4.

VOL. 12, NO. X,

XXXXXX 2013

3.2 Data Structure
Several data structures have been introduced and used torepresent an area of presence in the existing localization
algorithms. In [23], several data structures are given anddiscussed in detail. In a simple way, we may use circles orsimple polygons such as rectangles to approximate areas ofpresence, but obviously it lacks the accuracy of approximation. Monte Carlo-based localization such as MCL [9] uses a
set of randomly selected points to represent an area ofpresence, where simplicity is a merit for small handheld
devices. Sextant [23] utilizes a list of representative points
and the area is approximated as a set of Bézier curves
between those points.
Unlike these methods, we divide a target region into
small cells and represent areas of presence and obstacles bysets of cells. Here, the form of each area of presence in UPL
is more complex than those in the existing methods because
we consider regions restricted by obstacles and the movement of nodes in such complex regions. There are somemethods that deal with obstacles. For example, Sextant [23]takes into account an area restricted by obstacles. However,it only deals with stationary nodes. Considering the factthat in our case the operations on areas of presence are more
complex, we use grid cells to represent areas of presence
and obstacle maps.
3.3 UPL Algorithm Details
3.3.1 Computing Area of Presence
We present an algorithm to compute Rtj , an area of presencetof node j at time t, from given Rjj (tj < t), tj ¼ t  tj andan obstacle map M. Rtj and M are represented by sets ofcells. This algorithm is referred to as the Area of Presence
Computation (APC) algorithm and does not requirecomplex functions, for example, like computing intersections of polygons. Instead, we only use simple andlightweight operations.
First, we represent the map M by set F S, the set of all thecells in the movable space (free space) of M. That is, F S is
the set of all the cells which are not included by the
obstacles. Basically, to calculate Rtj , the APC algorithm addst
the cells in F S within vmax  tj distance from Rjj . However,it may be expensive under the existence of obstacles totcalculate the shortest distance from Rjj for each cell in F S.
We therefore design an algorithm that can obtain Rtj bytexpanding Rjj by simple computation. This is accomplishedby approximating distance calculation. The detailed process
is described below.
We introduce some terminologies and notations. For cellg, a cell which shares a side with g is called a side cell, and acell which is not a side cell of g and shares a single vertex
with g is called a diagonal cell. The side cells and diagonal cells
are called neighboring cells. Also, for a set G of cells, a cell in G
which has at least one neighboring cell outside G is called aborder cell. For each cell g, we let dðgÞ denote thet(approximated) shortest distance from Rjj (dðgÞ ¼ 0 if g istj
in Rj ). Here, the distance of two neighboring cells is the
Euclid distance between the centers of the cells.
The APC algorithm is described as follows: We start witht
Rjj and iterate the following procedure. For eachRtjborder cell g of Rtj with the shortest distance dðgÞ, we add

UCHIYAMA ET AL.: UPL: OPPORTUNISTIC LOCALIZATION IN URBAN DISTRICTS

5

Fig. 2. Computing an area of presence and its expansion by maximum communication range.

each side cell g0 of g in F S to Rtj if dðgÞ þ w  vmax  tj
where w is the side length of a cell. If g0 is added, we set the
shortest distance of g0 as dðg0 Þ ¼ dðgÞ þ w. Similarly, we
pﬃﬃﬃadd
each diagonal cell g00 of g in F S to Rtj if dðg00 Þ þ 2w 
isﬃﬃﬃadded, we set the shortest distance of g00 as
vmax  tj . If g00 p
00dðg Þ ¼ dðgÞ þ 2w. Then, we remove all g0 and g00 whichhave been added to Rtj from F S. This procedure is repeateduntil there are no new cells in F S which can be added to Rtj .
tFigs. 2a and 2b show examples of Rjj and Rtj , respectively.
tj
Also in Fig. 3, we illustrate
pﬃﬃﬃ how Rj expands at each step of
the algorithm where 2  1:4. The formal description ofthis APC algorithm is given in Fig. 4.

3.3.2 Expanding Area of Presence by Communication
Range
Then, we compute Rtj  rmax , the area of presence of node j
at time t expanded by the maximum communication range
rmax . We call this area a communicable area of j at time t
hereafter. There is a possibility to receive a hello message
from j at time t in this communicable area under theassumptions that the maximum velocity of nodes is vmax
and the maximum communication range is rmax .
For computing communicable areas, we may apply the
APC algorithm. In actual fact, radio propagation may beaffected by multipath effects in urban districts where manybuildings exist. Ideally, we should design a propagation
prediction algorithm considering the multipath effects byusing precise radio propagation models such as Rayleighfading and Rician fading [54]. However, in our environment,

Fig. 3. First and second steps of the APC algorithm (value inside atcell represents distance from Rjj ).

it is not reasonable to implement such a complex algorithm
considering the computation cost. Furthermore, even though
we apply such an NLOS propagation model, its impact on
the performance is expected to be small because UPL
expands an area of presence by the communication range
from every point in the area of presence. For example, Fig. 5ashows a real position in an area of presence and LOS andpossible NLOS areas from the position. Note that the effect ofreflection is negligible in such places like pathways inunderground cities and streets among buildings because theradio range is too short (e.g., 10 m) for reflection. To see theeffect of diffraction, we calculated RSS at five positions
shown in the figure by the knife-edge diffraction model [55].
The transmission power was set to 18 dBm, and the RSS
threshold of a receiver was set to 78 dBm, which was thesame value as the expected RSS at 10 m distance using thefree space path loss model [56]. The calculated RSS values
are shown in Table 2. We can see all the RSS values are lower
than the threshold. Furthermore, as shown in Fig. 5b, LOS
from every point in the area of presence includes most of
possible NLOS points. For this reason, the difference of LOS

Fig. 4. Area of presence computation algorithm.

6IEEE TRANSACTIONS ON MOBILE COMPUTING,

VOL. 12, NO. X,

XXXXXX 2013

Fig. 6. Simulation maps (snapshot from MobiREAL).

Fig. 5. LOS from every point in AoP covers NLOS.

and NLOS models does not have so much impact on theperformance. Hence, we adopt a LOS propagation modeland simply use the APC algorithm to expand Rtj (see Fig. 2c).

3.3.3 Intersecting Two Areas
Intersecting Rti and Rtj  rmax is simple. We seek cells which
are included in the both areas and obtain the new area ofpresence, Rti \ fRtj  rmax g.
3.4

Selecting a Point from Estimated Area of
Presence
From the definition of an area of presence, a node exists at apoint in its area of presence. The probability that a point innode’s area of presence is its actual position is uniform andequal to the inverse of the size of the area of presence.
Many applications require a point as an estimation
result. Here, in case that we need to identify the location ofa node from its area of presence, we give a position
estimation function that determines the point in the area ofpresence, which minimizes the upper bound of distanceerrors. We have used the following estimation function todetermine the point p from an area of presence R and an
obstacle map Mdistðp; p0 Þ;
select p 2 R that minimizes max
0
p 2R

ð1Þ

where distðp; p0 Þ is the shortest distance between p and p0 on
M (that is, the shortest distance among obstacles). An
example of such a point is illustrated as a white circle inFig. 2b. Considering the fact that the actual point should exist
within R, selecting such p that minimizes the maximum
distance between p and another point p0 in R minimizes the
maximum distance error of positioning.

3.5 Other Optimization
The existing techniques have utilized some other information to assist more accurate localization. Some techniques
maintain and use the history of signal receptions from alandmark. Concretely, by knowing the timing when thenode entered or left the communication range of a landmark, we may be able to identify the position of the node
TABLE 2
RSS Calculated by a Knife-Edge Diffraction Model

exactly on the disc edge of the communication range of thelandmark. Also some try to extend the communication
range of a landmark by multihop propagation of thelandmark information. In our experiments, we haveborrowed a sophisticated technique from MCL [9], whichuses a two-hops advertisement of landmark positions toextend the coverage of landmarks.

4

PERFORMANCE EVALUATION

4.1 Simulation Settings
To confirm the effectiveness of UPL, we have conductedsimulations using our open source mobile network simulator MobiREAL [57], [58]. We have used three maps:
1) Manhattan region [59] of 500 m  500 m with eight streets(Fig. 6a); 2) the real map of 500 m  500 m region in front of
the Osaka train station (Fig. 6b) called Osaka downtown; and
3) Free space of 500 m  500 m without obstacles (Fig. 6c). In
the figures, the radio range and deployment of landmarks
are represented as circles. In Manhattan and Osaka downtown regions, we have specified areas except roads as
obstacles, and LOS radio propagation was considered.
UPL requires the maximum velocity of nodes vmax as an
input parameter and assumes moving speeds of nodes are
no more than vmax . However, in practice, the speeds may befaster than vmax . Hence, it is important to determine vmax sothat we can change its correctness, i.e., the number of nodesof which speeds are no more than vmax . For this purpose,the moving speeds v of nodes are determined so that they
follow the normal distribution of (v , v2 ) where v > 0. Basedon these parameters, vmax is defined asvmax ¼ v þ kv ;where k > 0 and k ¼ 5 in the default setting. From thecharacteristic of the normal distribution, approximately
99.999942 percent of nodes do not exceed vmax when k ¼ 5.
We used the above normal distribution for moving speeds
in Manhattan and Osaka downtown regions. In Manhattan
region, nodes are moved according to “random-streetdecision” mobility where at each intersection each nodedecides to which direction it goes, except the backward
direction. In Osaka downtown region, nodes’ mobility is“random-street-decision” mobility except in the free spaceof 170 m  250 m at the bottom right corner where nodes
move based on Random Waypoint mobility [60]. In Free
space, nodes are moved according to Random Waypoint
mobility where pause time is zero. As for Random
Waypoint mobility, the minimum and maximum moving
speeds are 1.0 and 2.0, respectively, and vmax is set to 2.0. In
all the simulations, the default values described in Table 3

UCHIYAMA ET AL.: UPL: OPPORTUNISTIC LOCALIZATION IN URBAN DISTRICTSTABLE 3
Simulation Parameters

are used except when we explicitly mention it. Also, we
assume each node has an obstacle map from the beginning.

4.2 Impact of Parameters and Environments
We have conducted the simulations of the first type in
Manhattan region. For the areas of presence, we havemeasured their accuracy, i.e., their sizes. The average sizes
are derived from 10 simulation cases. The results are
summarized in Table 4.
4.2.1 Cell Size
The cell size w may affect accuracy. We have evaluated theaverage sizes of areas of presence under different values ofcell size w (1 m, 2 m, and 4 m). From the result, we can see
explicit difference of the sizes. This is because smaller cells
can represent the borders of areas of presence moreaccurately. In the case of w ¼ 4, the average size is about
400 m2 , which is rather large compared with the cases ofw ¼ 2 and w ¼ 1. Also we do not see big difference
between the cases of w ¼ 1 and w ¼ 2. Considering the factthat the cell size quadratically affects memory space, we
may select w ¼ 2.
4.2.2 Hello Message Interval
The frequency of hello message transmissions will affect theaccuracy because receiving a “fresh” area of presence
information is much more useful to reduce the area ofpresence for the receiver. In order for a node (say node i) toreceive a hello message from a node (say node j) which ismoving toward node i, the interval must not be greater thanrmax =vmax . In this experiment, rmax ¼ 10 m and vmax ¼ 2 m/s;
thus, the interval of 5 seconds is the maximum. We see theaccuracy in different intervals (1, 2, 5, and 10 sec). From theresult, the interval of 2 seconds seems the most reasonableinterval because it achieved the similar size as the case of
1 second interval with the less number of messages.
4.2.3 Moving Speed
As moving speeds become large, there is a merit for eachnode that it may meet more nodes. However, quick

7

TABLE 5
Degeneracy Ratio

expansion of areas of presence is a demerit. To see what
happens if we increase the speeds of nodes, we have varied
the average moving speed v . The size of the area ofpresence increases linearly as the speed increases. Thus,
slow speed is better for the accuracy. Since increasing
speeds has similar effect with increasing hello message
intervals, this is the result as expected. This result proves
our localization is well fit for slow pedestrians.

4.2.4 Number of Landmarks
One of the advantages of UPL is that it does not require
many landmarks. To see what happens if we decrease thenumber of landmarks, we have varied the number oflandmarks (8, 12, and 16). This is the natural result where
the accuracy increases as the number of landmarks
increases. Here, 16 landmarks with 10 m transmission
range only cover 12.8 percent of the movable areas(32  103 m2 ). Even in such a region with sparsely deployed
landmarks, UPL could achieve reasonable accuracy where
200 m2 indicates that we can identify a node on a street with
8 m width within 25 m length.
4.3

Effect of Opportunistic Localization and Precise
Calculation of Movement
To see the effectiveness of our two key ideas: 1) opportunistic localization between mobile nodes, and 2) precise
calculation of nodes’ movement among obstacles, we also
examine the performance of two simplified versions of
UPL; UPLno adhoc which uses information from landmarks
only and UPLno obs which does not utilize obstacle
information to predict the movement of nodes and to
calculate communication range. We have measured theaverage sizes of areas of presence in UPLno adhoc , UPLno obs
and UPL, and calculated each ratio to original UPL in
Manhattan region. We call this the degeneracy ratio.
Table 5 shows the averages of the degeneracy ratios. We
can see that ad hoc localization and obstacles information
effectively reduce 89 and 19 percent of the sizes of the areasof presence, respectively. Fig. 7 shows the size distributionsof areas of presence. As we can see, obstacle information

TABLE 4
Impact of Parameters and Environments on PerformanceFig. 7. Size distribution of areas of presence.

8

IEEE TRANSACTIONS ON MOBILE COMPUTING,

VOL. 12, NO. X,

XXXXXX 2013

Fig. 9. Bandwidth consumption.

obstacles. Surprisingly, Amorphous shows less accuracy
compared with MCL and UPL, that limit the hello message
propagation to two hops at most (see Fig. 8a). Second, in
MCL, the more the node density, the higher the accuracy inboth of two maps. MCL propagates landmarks’ information
to two hops, and the increase of the node means the wider
spread of accurate information. In order to achieve thecomparable accuracy to UPL, MCL requires more landmarks because MCL relies on direct (or two hops)
information from landmarks. On the other hand, UPL
outperforms these methods and the error is 0:7r, that is, 7 m
in Osaka downtown. Moreover, UPL achieves the higher
accuracy than Amorphous even in Free space because UPL
is opportunistic localization and sustainable against the low
node density.
Fig. 8. Estimated position errors.

gives a certain amount of impact on accuracy of many
nodes. On the other hand, opportunistic localization
dramatically improves the accuracy of some nodes. This
fact indicates that in some places which are away fromlandmarks, opportunistic localization is very helpful. Fromthese results, we could confirm the effectiveness of two key
ideas of UPL.

4.4 Comparison with Other Approaches
For comparison, we have measured the estimated position
errors of UPL, MCL [9], and Amorphous [13] using Osaka
downtown region and Free space. MCL only uses shortrange landmarks in addition to the maximum velocity ofnodes, and Amorphous performs multihop cooperative
multilateration. We chose these two typical methods forcomparison although many mobile localization algorithms
have been presented. This is because we can see thedifference between UPL and other localization algorithms
using location information of other mobile nodes in
addition to landmarks from the result of UPLno obs shownin Section 4.3. In UPL, we have used the position estimation
function (1) of Section 3.4. Figs. 8a and 8b show the position
errors regarding the communication range (r ¼ 10 m). We
see the accuracy of MCL and UPL in Osaka downtown ishigher than that in Free space. This is because areas where
nodes can move in Osaka downtown are smaller than in
Free space, which means nodes receive more areas ofpresence in Osaka downtown.
First, the accuracy of Amorphous is expected to behigher as the node density increases, which is true in Free
space (see Fig. 8b). However, it is not true in Osaka
downtown where the shape of the network is restricted by

4.5 Communication Overhead
The number of messages sent in UPL is much less thanflooding-based techniques such as Amorphous since eachnode in UPL periodically broadcasts its area of presence toneighbors. However, the size of each message is large
because it contains grid cells’ information. Hence, in order
to see communication overhead, we changed the number ofnodes and measured the bandwidth consumption by UPL
in Osaka downtown. From the results shown in Fig. 9, we
see that the bandwidth consumption becomes larger as
the number of nodes increases. However, at the same time,
the size of each hello message becomes smaller because thesizes of areas of presence decrease. From this result,the bandwidth consumption by UPL is small enough forthe implementation based on Bluetooth, ZigBee, and so on.
4.6 Effect of vmax
UPL assumes the speeds of nodes are no more than vmax . In
practice, the speeds of nodes may be faster than vmax
however. Here, we evaluate UPL in such situations. We setv and v to 1.5 and 1.0, respectively. Fig. 10 shows theFig. 10. Impact of vmax on performance.

UCHIYAMA ET AL.: UPL: OPPORTUNISTIC LOCALIZATION IN URBAN DISTRICTS

9

Fig. 12. Region used in real experiment.

Here, a method named selective broadcast is introduced formessage reduction of similar areas of presence. Selective
broadcast decides whether a node executes broadcasting of
its area of presence or not by comparing the size jRi j of its
own area of presence and the average size jRrecv j of areas ofpresence received in the last hello message interval. A nodebroadcasts a hello message if the following condition meets:jRi j <   jRrecv j;

Fig. 11. Effect of selective broadcast.

completeness and the accuracy where the parameter k forvmax is set to 0.5, 1.5, or 2.5. Here, the completeness ratio isdefined as# of complete areas of presence:# of calculated areas of presence
Theoretically, all areas of presence are complete. However,
the approximation caused by APC algorithm and the data
structure of grid cells make errors between theoretical areasof presence and computed ones. The computed areas ofpresence are therefore not always complete. In addition,areas of presence may become incomplete when the moving
speeds of nodes exceed vmax .
In Fig. 10, the completeness and the size decrease as thenumber of nodes whose speeds are more than vmax increases.
This is because the degeneracy of completeness leads to theoccurrence of an “empty region” as a result of computing anintersection of two regions.1 On the other hand, both thecompleteness and the size increased when vmax was set to 4
since most of nodes moved slower than vmax . This is atradeoff. In order to increase the accuracy, we may set
different vmax for each node and broadcast it with hellomessages if moving speeds widely vary depending on nodes.

4.7 Selective Broadcast for Message Reduction
In urban districts, many areas of presence broadcast fromneighboring nodes, may be similar in size and location due
to high density. Such similar areas of presence cannot
contribute to improve location accuracy of other nodes.
1. In all the simulations, we expand areas of presence gradually when anintersection of two regions is empty.

ð2Þ

where   0 is a constant. Note that if the node has notreceived any hello message in the last interval, it broadcasts
a hello message.
We simulated the effect of selective broadcast withdifferent values of  in Manhattan map. We also changed
the hello message interval to 1 or 2 seconds. From the resultin Fig. 11, it is obvious that there is a tradeoff between thenumber of broadcasting and accuracy. In this result,  ¼
1:0 achieves a good tradeoff, and reduces the number ofhello messages by 50 to 80 percent approximately keeping
accuracy compared to the case of  ¼ 1 where selective
broadcast is not employed. The effect of selective broadcast
is large especially when the hello message interval is
1 second because areas of presence of neighbors are similar
in most cases.

5

REAL EXPERIMENT

5.1 Simulation Using Real Communication Log
5.1.1 Setting
To see the effect of radio propagation that is observed in thereal world, we have conducted a real experiment using asmall sensor called MICAz Mote [61], which supports
ZigBee communication. In a 20 m  20 m square region withT-shaped roads, four Motes were deployed at intersections
A, B, C, and D, and regarded as landmarks (see Fig. 12). The
obstacle map was defined as shown in Fig. 12b based on theimage from GoogleMap. In this region, three persons
holding Motes started walking from the landmark A, B,
and C to the adjacent landmarks, respectively, as shown in
Fig. 12. Each Mote broadcast a hello message at the rate of
5 Kbps during the experiment. Specifically, the packet
payload size is limited to 64 Bytes and 10 packets werebroadcast every second. In the experiment, we regarded
node i successfully received an area of presence from node j
only when i received all the 10 packets from j. The
transmission power was adjusted so as to the transmission
range was approximately 2 m, and rmax was set to 4 m. The

10IEEE TRANSACTIONS ON MOBILE COMPUTING,

VOL. 12, NO. X,

XXXXXX 2013

TABLE 6
Real Experiment Result

moving speeds of nodes were 1.25 m/s and vmax was set to
2.0 m/s. In the above environment, three persons walked
for 192 seconds and recorded the number of packets
successfully received from other nodes. Based on therecorded logs, areas of presence were calculated by UPL.
The cell size was set to 1 m  1 m, and the cells covering thebuildings were specified as obstacle cells in UPL. We haveevaluated sizes of areas of presence and completeness ratios
after updates of areas of presence. The results werecompared with those in ideal radio propagation.

5.1.2 Result
The result is shown in Table 6. The completeness ratio in theideal case is 1.0, and the average size of areas of presence is
14:7 m2 , which is 22 percent smaller than that of the case ofradio propagation that is observed in the real world. This isnatural because nodes can transmit areas of presence
information immediately when they enter the neighbors’radio range in the ideal radio propagation case. Such perfectsensing capability of transmission opportunity can keep theareas smaller, and accordingly those in any other cases will
be larger than the ideal case, leading to less accuracy.
Nevertheless, by the experiment in this section, we canprove that the accuracy of UPL with realistic propagation isstill sufficient for street-level pedestrian tracking since anarea of presence covers the road segment where the node
exists in most cases.
5.2

Comparison with Smartphone Tracks and Other
Methods in a Real Urban Underground City
5.2.1 Setting
To see the localization accuracy of commercial off-the-shelfdevices and the effectiveness of UPL, we collectedpedestrian tracks recorded by iPhone 3GS in a real urban
underground city in Osaka (see Fig. 13a), and compared itwith simulation results of UPL, Amorphous, and MCL. The
area size is 246 m  358 m, and GPS does not work in thearea. Even without GPS signals, iPhone can find its locationby using RSS database from WiFi base stations and cellular
towers. We used the obstacle map shown in Fig. 13b where
the obstacles were represented as shaded areas, andassumed five landmarks were deployed at the points ofwhite circles in Fig. 13b. The obstacle map was easily
obtained by applying image processing to the original map.
The circles also represent their radio range. Note that wecompensated the iPhone tracks so that the tracks did notcross over obstacles. For this purpose, if a line connecting
two adjacent locations crosses over obstacle(s), we have
replaced the line with the shortest path between thelocations. To get stable WiFi signals for the iPhone tracks,
we also paused at locations represented by small circles inFig. 13a for about 60 seconds. Assuming UPL and MCL candetect whether the node is moving or not with an

Fig. 13. Real underground city map and tracking results. (a) Undergroundcity map and tracking results: ground truth (dashed); iphone (red thin);
UPL (green bold). (b) Obstacle map and landmark coverage.

accelerometer, UPL and MCL set the maximum speed usedin localization to zero during the pauses. The mobility was
reproduced by Urban Pedestrian Flow (UPF) [62] based on
the number of pedestrians counted at several locations. In
the reproduced mobility, the average number of nodes was
about 243. The other parameters were set to the values
shown in Table 3.

5.2.2 Result
The tracking results of UPL and iPhone are shown in
Fig. 13a. We have drawn a line between a location and its
adjacent location in the results. Overall, the average
localization error of iPhone was about 50 m, and that of
UPL was about 14 m. We can see the tracks of UPL are
more similar to the ground truth than those of iPhone, and
UPL correctly estimates the tracks in terms of streets inmost cases. On the other hand, iPhone tracks sometimes
jump to distant locations since the location estimation of
iPhone relies on WiFi and cellular towers with low
granularity. Moreover, the average error of Amorphous
was 89 m because multihop networks were often disconnected due to mobility. Hence, distance estimation from
more than two landmarks could not be processed in manycases. On the other hand, the average error of MCL was
72 m due to the small number of landmarks. From theseresults, we have confirmed UPL works well for pedestrians
in urban areas.

6

ANALYSIS

6.1 Space Complexity
MCL represents areas by a set of points; hence, the data
size is proportional to the number of points. In Sextant, thedata size is proportional to the number of control points
since areas are represented by a set of Bézier curves. Thus,
the space complexities of above two techniques are on theorder of bytes.
On the other hand, UPL represents areas by grid cells.
Here, we estimate the required memory space based on theparameter settings used in Section 4. Assuming the region is
500 m  500 m and the size of cells is 2 m  2 m, the total

UCHIYAMA ET AL.: UPL: OPPORTUNISTIC LOCALIZATION IN URBAN DISTRICTS

11

number of cells is 250  250. The data size for an obstacle
map or an area of presence is approximately 8 Kbytes
because 1 bit is enough for each cell to represent the cell is
included in obstacles or areas of presence. Each node
executes UPL whenever it receives an area of presence fromothers. The required memory space in UPL is three times ofgrid cells needed for representation of the whole region,that is, 24 kbytes. Additionally, APC algorithm needs tocalculate the shortest distances between an area of presence
and each grid cell. When the settings are vmax ¼ 2 m/s,
rmax ¼ 10 m, and tmax ¼ 2 sec, the expanded distance is
14 m at most. Thus, we need 1 byte per cell for thecomputation of the expansions. This means APC algorithm
requires 62.5 Kbytes. Based on the above discussion, thememory space required in each node is about 90 Kbytes,
which is large compared with MCL and Sextant. However,
it is still acceptable on recent handheld terminals that have amemory on the order of megabytes.

6.2 Time Complexity
Calculating the shortest distance between any two points ina region with obstacles requires a visibility graph, of which
the time complexity is Oðn2 log nÞ where n is the number of
obstacle edges [63]. In a straightforward approach, expansion of an area of presence represented by a polygon with
M vertices is computed as follows:
Compute the bounding box of the polygon.
Expand the bounding box by vmax  t without
considering obstacles. The bounding box always
includes the expanded area of presence.
3. Construct grid cells in the expanded bounding box.
4. For each cell in free space, check its reachability fromthe original area of presence, i.e., check if the
distance from the cell to any one of the cells in theoriginal area of presence is equal to vmax  t or less.
For this purpose, we need calculate distance
between two points in a region with obstacles. Time
complexity of this calculation is Oðn2 log nÞ where nis the number of obstacle edges.
5. Build the expanded area of presence represented bya polygon from the cells that are reachable from theoriginal area of presence.
On the other hand, our APC algorithm does not requirecalculation of distance in a region with obstacles. Instead,the algorithm iterates calculation of distances to neighboring cells. The expansion of an area of presence can becomputed in Oðvmax  t=wÞ time in any environment,
where w denotes the cell size. Hence, it is reasonable tochoose grid cells as data structure, considering energy
consumption for computation.
1.
2.

6.3 Accuracy Analysis
In order to simplify the analysis, we consider areas ofpresence on a 1D segment of which the length is L m asshown in Fig. 14a. We assume that two landmarks areplaced at the locations 0 and L, and N nodes (1; 2; . . . ; N)move on this segment ½0; L . In this environment, we focus
on a certain node i and consider the change of i’s area ofpresence represented as a segment in ½0; L . For simplicity of
discussion, the moving speed and the radio range of all

Fig. 14. One-dimensional model for accuracy analysis.

nodes except node i are vð vmax Þ and rð rmax Þ, respectively. Note that each node knows only vmax and rmax .
Moreover, we assume the following. First, all nodes except
for the focused node i only use information sent directlyfrom landmarks. Hence, we do not consider exchange ofareas of presence among nodes except i. Second, the focusednode i receives an area of presence of another node j
immediately when i comes into the radio range of j. We canignore the hello message interval based on this assumption.
We consider that node i starts moving at time 0 withspeed vi and node j which moves from location L toward 0
at time t0 with speed v. We let t1 ð> t0 Þ denote the time when
j goes out of the radio range of the landmark. Then, the areaof presence of j at time t1 is represented by a segment½L  r; L . We denote i’s area of presence at that time as asegment ½li ; ri . Hereafter, areas of presence are supposed to
be within the segment ½0; L (see Fig. 14a).
We define t2 ð> t1 Þ as the time when i comes into the radio
range of j. Here, we assume that i has not encountered any
nodes since t1 . The area of presence of i at t2 is represented
by ½li  vmax t; ri þ vmax t (t ¼ t2  t1 ). The area ofpresence of j is represented by ½L  r  vmax t; L likewise(see Fig. 14b).
Then, i shrinks its area of presence by using j’s area ofpresence. However, the “tail” of the j’s segment (i.e., thesegment end in the opposite direction of j’s movement) is
hardly useful because it is larger than the “head” of i’ssegment (i.e., the segment end in the direction of i’s

12IEEE TRANSACTIONS ON MOBILE COMPUTING,

VOL. 12, NO. X,

XXXXXX 2013

Fig. 16. Moving speed v versus length of areas of presence.

Fig. 15. Time versus node i’s area of presence.

movement). On the other hand, j’s head is effective forshrinking. j’s head is expanded to ðvmax  vÞt ahead fromthe current position of j, and the distance between i and j isr. i’s tail is cut off to vi t2  ðvmax  vÞt (see Fig. 14c). This
example is shown in Fig. 14d as a graph. Similarly, i’s headis cut off to ðvmax  vÞt2 ahead from i’s current position
when j moves toward the same direction as i.
Next, we focus on the interval between encountering two
adjacent nodes in each case of passing and crossing. We
consider two adjacent nodes j and k that are moving toward
the same direction, and k is following j. The interval isdefined as the length of time it takes for i to enter the radio
range of k after entering that of j. Assuming the uniform
distribution of nodes, the distance between two adjacentnodes moving toward the same direction as i is
2L
ðmÞ:
N þ1
Thus, the interval of passing Tpass is
Tpass ¼

2L
ðsec:Þ ðif v > vi Þ:ðv  vi ÞðN þ 1ÞSimilarly, the interval of crossing Tcross is
Tcross ¼

2L
ðsec:Þ:ðv þ vi ÞðN þ 1ÞThe extent of shrinking becomes smaller proportionallyto the product of ðvmax  vÞ and the elapsed time since theencountered node received information from the lastlandmark. In this analysis, we approximate the extent ofshrinking to that obtained at the location L=2. Therefore,
when j passes/crosses i, the head/tail of i’s area ofpresence is cut offðvmax  vÞ

L
2
v

ð3Þ

away from i’s current position. Consequently, i iterates
expanding and shrinking its area of presence at the intervalof Tcross and Tpass as shown in Fig. 15.
The average length jMi j of i’s area of presence is equal
to the average height of the shaded area in Fig. 15. We

can calculate jMupper j, the average length of i’s head, as
follows:
8ðvmax  vÞLðvmax  vi ÞL
>
>
þ
>
>
>
2
v
ð
v
 vi ÞðN þ 1Þ
>

< 
i ÞL

if
v
>
v
and
jMupper j  ðvmax2v
i
jMupper j ¼
v
>
>
>
>
>
ðv
 vi ÞL
>: maxðotherwiseÞ:2vi
Because of the approximation in the expression (3), jMupper j
may become longer than that without passing. Hence, we
limit the maximum of jMupper j in addition to the conditionv > vi . The following denotes the average length jMlower j of
i’s tail:
jMlower j ¼

ðvmax  vÞLðvmax þ vÞL
:
þ
2
v
ð
v þ vi ÞðN þ 1Þð4Þ

We then obtainjMi j ¼ jMupper j þ jMlower j:ð5ÞIn order to confirm the correctness of the analysis above,
we have compared jMi j in the analytic model and simulations. We set L ¼ 500 m, vmax ¼ 2 m/s, vi ¼ 1:5 m/s,
rmax ¼ 10 m, and N ¼ 100, and measured jMi j by simulations. Both of the results in Fig. 16 show the similar values
and trend, and we could confirm the correctness of theanalysis. When v is less than vi , the simulation result issmaller than the analytic result. The reason is the effect of ad
hoc localization among other mobile nodes. In the simulation, an area of presence is shrunk by others’ areas ofpresence although we assume that nodes except i rely only
on the directly received information from landmarks in theanalysis. This difference affects the size of the area ofpresence in the analysis remarkably as v is low because theanalytic model expands the areas of presence considering
the worst case, which results in the larger areas of presence.
The concept of the 1D analysis can be extended to a 2D
case. Different from the 1D analysis, the 2D analysis
requires considering encounter directions in 360 degree.
For this purpose, we may be able to use the expectedencounter time between different nodes provided in [64]. If
the encounter intervals for each direction are given, then wecan calculate the average lengths for each direction
similarly to (4) and (5). Approximation of shapes of areasof presence (e.g., circles) may be necessary for the simplicityof the analysis.

UCHIYAMA ET AL.: UPL: OPPORTUNISTIC LOCALIZATION IN URBAN DISTRICTS

7

CONCLUSION

In this paper, we have proposed an opportunistic localization algorithm called UPL for positioning mobile users inurban districts. UPL exploits obstacle information andlocation information from neighboring nodes. For thispurpose, each mobile node maintains its area of presence
where the node exists. To show the effectiveness of UPL,
extensive simulations and real experiments have been
conducted. From the results, we have shown that UPL could
achieve reasonable accuracy for positioning of mobile users
in urban cities, compared with typical existing methods.

ACKNOWLEDGMENTS
This work was supported in part by Core Research for
Evolutional Science and Technology (CREST, JST), theKDDI foundation, and the CPS-IIP Project (FY2012FY2016) in the research promotion program for national
level challenges by the Ministry of Education, Culture,
Sports, Science and Technology (MEXT), Japan.

REFERENCES
[1]
[2]
[3]
[4]
[5]

[6]

[7]
[8]
[9]
[10]
[11]
[12]
[13]

[14]

[15]
[16]
[17]
[18]
[19]

Place Engine, http://www.placeengine.com/en, 2012.
Skyhook Wireless, http://www.skyhookwireless.com/, 2012.
Google Latitude, http://www.google.com/latitude, 2012.
Virtual Earth, http://virtualearth.msn.com/, 2012.
S.C. Swales, J.E. Maloney, and J.O. Stevenson, “Locating Mobile
Phones and the US Wireless E-911 Mandate,” Proc. IEE Colloquium
Novel Methods of Location and Tracking of Cellular Mobiles and Their
System Applications, pp. 2/1-2/6, 1999.
L. Lopes, E. Villier, and B. Ludden, “GSM Standards Activity on
Location,” Proc. IEE Colloquium Novel Methods of Location andTracking of Cellular Mobiles and Their System Applications, pp. 7/17/7, 1999.
H. Laitinen, J. Lahteenmaki, and T. Nordstrom, “Database
Correlation Method for GSM Location,” Proc. IEEE VehicularTechnology Conf., pp. 2504-2508, 2001.
J. Hightower, A. LaMarca, and I.E. Smith, “Practical Lessons from
Place Lab,” IEEE Pervasive Computing, vol. 5, no. 3, pp. 32-39, JulySept. 2006.
L. Hu and D. Evans, “Localization for Mobile Sensor Networks,”
Proc. ACM MobiCom, pp. 45-57, 2004.
D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS),”
Proc. IEEE GlobeCom, pp. 2926-2931, 2001.
D. Niculescu and B. Nath, “DV-Based Positioning in Ad Hoc
Networks,” J. Telecomm. Systems, vol. 22, nos. 1-4, pp. 267-280,
2003.
C. Savarese and J. Rabaey, “Robust Positioning Algorithms forDistributed Ad Hoc Wireless Sensor Networks,” Proc. USENIX
Ann. Technical Conf., pp. 317-328, 2002.
R. Nagpal, H. Shrobe, and J. Bachrach, “Organizing a Global
Coordinate System from Local Information on an Ad Hoc Sensor
Network,” Proc. Int’l Workshop Information Processing in Sensor
Networks, pp. 333-348, 2003.
S. Yang, J. Yi, and H. Cha, “HCRL: A Hop-Count-Ratio Based
Localization in Wireless Sensor Networks,” Proc. Ann. IEEE Comm.
Soc. Conf. Sensor, Mesh and Ad Hoc Comm. and Networks (SECON),
pp. 31-40, 2007.
H. Wu, C. Wang, and N.-F. Tzeng, “Novel Self-Configurable
Positioning Technique for Hop Wireless Networks,” IEEE/ACM
Trans. Networking, vol. 13, no. 3, pp. 609-621, June 2005.
Y. Shang, W. Ruml, Y. Zhang, and M.P.J. Fromherz, “Localizationfrom Mere Connectivity,” Proc. ACM MobiHoc, pp. 201-212, 2003.
H. Lim and J.C. Hou, “Localization for Anisotropic Sensor
Networks,” Proc. IEEE INFOCOM, 2005.
C. Wang and L. Xiao, “Locating Sensors in Concave Areas,” Proc.
IEEE INFOCOM, 2006.
M. Li and Y. Liu, “Rendered Path: Range-Free Localization in
Anisotropic Sensor Networks with Holes,” Proc. ACM MobiCom,
pp. 51-62, 2007.

13[20] B. Xiao, L. Chen, Q. Xiao, and M. Li, “Reliable Anchor-Based
Sensor Localization in Irregular Areas,” IEEE Trans. Mobile
Computing, vol. 9, no. 1, pp. 60-72, Jan. 2010.
[21] J. Albowicz, A. Chen, and L. Zhang, “Recursive Position
Estimation in Sensor Networks,” Proc. IEEE Int’l Conf. Network
Protocols (ICNP), pp. 35-41, 2001.
[22] R. Bischoff and R. Wattenhofer, “Analyzing Connectivity-BasedMultihop Ad-Hoc Positioning,” Proc. Second IEEE Int’l Conf.
Pervasive Computing and Comm. (PerCom), 2004.
[23] S. Guha, R. Murty, and E.G. Sirer, “Sextant: A Unified Node andEvent Localization Framework Using Non-Convex Constraints,”
Proc. ACM MobiHoc, pp. 205-216, 2005.
[24] M. Rudafshani and S. Datta, “Localization in Wireless Sensor
Networks,” Proc. Int’l Workshop Information Processing in Sensor
Networks, pp. 51-60, 2007.
[25] S. Zhang, J. Cao, L. Chen, and D. Chen, “Accurate and EnergyEfficient Range-Free Localization for Mobile Sensor Networks,”
IEEE Trans. Mobile Computing, vol. 9, no. 6, pp. 897-910, June 2010.
[26] A. Uchiyama, S. Fujii, K. Maeda, T. Umedu, H. Yamaguchi, and T.
Higashino, “Ad-Hoc Localization in Urban District,” Proc. IEEE
INFOCOM, pp. 2306-2310, 2007.
[27] C. Wang and L. Xiao, “Sensor Localization under Limited
Measurement Capabilities,” IEEE Network, vol. 21, no. 3, pp. 1623, May/June 2007.
[28] D. Niculescu and B. Nath, “VOR Base Stations for Indoor 802.11
Positioning,” Proc. ACM MobiCom, pp. 58-69, 2004.
[29] C.K. Seow and S.Y. Tan, “Non-Line-of-Sight Localization in
Multipath Environments,” IEEE Trans. Mobile Computing, vol. 7,
no. 5, pp. 647-660, May 2008.
[30] O. Hernandez, F. Bouchereau, and D. Munoz, “Maximum Likelihood Position Estimation in Ad-Hoc Networks Using a Dead
Reckoning Approach,” IEEE Trans. Wireless Comm., vol. 7, no. 5,
pp. 1572-1584, May 2008.
[31] N.B. Priyantha, A. Chakraborty, and H. Balakrishnan, “TheCricket Location-Support System,” Proc. ACM MobiCom, pp. 3243, 2000.
[32] A. Smith, H. Balakrishnan, M. Goraczko, and N. Priyantha,“Tracking Moving Devices with the Cricket Location System,”
Proc. ACM MobiSys, pp. 190-202, 2004.
[33] P. Bahl and V.N. Padmanabhan, “RADAR: An In-Building RFBased User Location and Tracking System,” Proc. IEEE INFOCOM, pp. 775-784, 2000.
[34] N. Patwari and A.O. Hero, “Using Proximity and Quantized RSS
for Sensor Localization in Wireless Networks,” Proc. ACM Int’l
Conf. Wireless Sensor Networks and Applications, pp. 20-29, 2003.
[35] H. Lim, L.-C. Kung, J.C. Hou, and H. Luo, “Zero-Configuration,
Robust Indoor Localization: Theory and Experimentation,” Proc.
IEEE INFOCOM, 2006.
[36] D.K. Goldenberg, P. Bihler, M. Cao, J. Fang, B.D.O. Anderson, A.S.
Morse, and Y.R. Yang, “Localization in Sparse Networks Using
Sweeps,” Proc. ACM MobiCom, pp. 110-121, 2006.
[37] K. Yedavalli and B. Krishnamachari, “Sequence-Based Localization in Wireless Sensor Networks,” IEEE Trans. Mobile Computing,vol. 7, no. 1, pp. 81-94, Jan. 2008.
[38] A. Savvides, C.-C. Han, and M.B. Strivastava, “Dynamic FineGrained Localization in Ad-Hoc Networks of Sensors,” Proc. ACM
MobiCom, pp. 166-179, 2001.
[39] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-Less Low Cost
Outdoor Localization for Very Small Devices,” IEEE PersonalComm. Magazine, vol. 7, no. 5, pp. 28-34, Oct. 2000.
[40] T. He, C. Huang, B.M. Blum, J.A. Stankovic, and T. Abdelzaher,“Range-Free Localization Schemes for Large Scale Sensor Networks,” Proc. ACM MobiCom, pp. 81-95, 2003.
[41] J.-P. Sheu, W.-K. Hu, and J.-C. Lin, “Distributed Localization
Scheme for Mobile Sensor Networks,” IEEE Trans. Mobile
Computing, vol. 9, no. 4, pp. 516-526, Apr. 2010.
[42] Q. Xiao, B. Xiao, J. Cao, and J. Wang, “Multihop Range-Free
Localization in Anisotropic Wireless Sensor Networks: A PatternDriven Scheme,” IEEE Trans. Mobile Computing, vol. 9, no. 11,
pp. 1592-1607, Nov. 2010.
[43] M. Jin, S. Xia, H. Wu, and X. Gu, “Scalable and Fully Distributed
Localization with Mere Connectivity,” Proc. IEEE INFOCOM,
pp. 3164-3172, 2011.
[44] Y. Wang, K. Li, and J. Wu, “Distance Estimation by Constructing
the Virtual Ruler in Anisotropic Sensor Networks,” Proc. IEEE
INFOCOM, pp. 1-9, 2010.

14

IEEE TRANSACTIONS ON MOBILE COMPUTING,[45] A.W. Tsui, W.-C. Lin, W.-J. Chen, P. Huang, and H.-H. Chu,
“Accuracy Performance Analysis Between War Driving and War
Walking in Metropolitan Wi-Fi Localization,” IEEE Trans. Mobile
Computing, vol. 9, no. 11, pp. 1551-1562, Nov. 2010.
[46] W.-Y. Chiu and B.-S. Chen, “A Mixed-Norm Approach Using
Simulated Annealing with Changeable Neighborhood for Mobile
Location Estimation,” IEEE Trans. Mobile Computing, vol. 9, no. 5,
pp. 633-642, May 2010.
[47] C.-Y. Yang, B.-S. Chen, and F.-K. Liao, “Mobile Location
Estimation Using Fuzzy-Based IMM and Data Fusion,” IEEE
Trans. Mobile Computing, vol. 9, no. 10, pp. 1424-1436, Oct. 2010.
[48] J. Yi, J. Koo, and H. Cha, “A Localization Technique for Mobile
Sensor Networks Using Archived Anchor Information,” Proc.
Ann. IEEE Comm. Soc. Conf. Sensor, Mesh and Ad Hoc Comm. and
Networks (SECON), pp. 64-72, 2008.
[49] A. Agarwal and S.R. Das, “Dead Reckoning in Mobile Ad Hoc
Networks,” Proc. IEEE Wireless Comm. and Networking Conf.,
pp. 1838-1843, 2003.
[50] J. Koo, J. Yi, and H. Cha, “Localization in Mobile Ad Hoc
Networks Using Cumulative Route Information,” Proc. 10th Int’l
Conf. Ubiquitous Computing (UbiComp), pp. 124-133, 2008.
[51] Y. Jin, M. Motani, W.-S. Soh, and J. Zhang, “SparseTrack:
Enhancing Indoor Pedestrian Tracking with Sparse Infrastructure
Support,” Proc. IEEE INFOCOM, pp. 1-9, 2010.
[52] U. Steinhoff and B. Schiele, “Dead Reckoning from the Pocket - An
Experimental Study,” Proc. IEEE Int’l Conf. Pervasive Computing
and Comm. (PerCom), pp. 162-170, 2010.
[53] S. Minamimoto, S. Fujii, H. Yamaguchi, and T. Higashino, “Local
Map Generation Using Position and Communication History ofMobile Nodes,” Proc. IEEE Int’l Conf. Pervasive Computing andComm. (PerCom), pp. 2-10, 2010.
[54] B. Sklar, “Rayleigh Fading Channels in Mobile Digital Communication Systems. I. Characterization,” IEEE Comm. Magazine,
vol. 35, no. 7, pp. 90-100, July 1997.
[55] W.C. Lee, Mobile Communication Engineering. McGraw-Hill, 1982.
[56] J.D. Parsons, The Mobile Radio Propagation Channel. Wiley, 1992.
[57] MobiREAL, http://www.mobireal.net, 2012.
[58] K. Maeda, A. Uchiyama, T. Umedu, H. Yamaguchi, K. Yasumoto,and T. Higashino, “Urban Pedestrian Mobility for Mobile Wireless
Network Simulation,” Ad Hoc Networks, vol. 7, no. 1, pp. 153-170,
2009.
[59] T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models
for Ad Hoc Network Research,” Wireless Comm. and Mobile
Computing, vol. 2, pp. 483-502, 2002.
[60] J. Broch, D. Maltz, D. Johnson, Y.-C. Hu, and J. Jetcheva, “A
Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proc. ACM MobiCom, pp. 85-97, 1998.
[61] MEMSIC Corporation, http://www.memsic.com/products/
wireless-sensor-networks/wireless-modules.html, 2012.
[62] K. Maeda, K. Sato, K. Konishi, A. Yamasaki, A. Uchiyama, H.
Yamaguchi, K. Yasumoto, and T. Higashino, “Getting Urban
Pedestrian Flow from Simple Observation: Realistic Mobility
Generation in Wireless Network Simulation,” Proc. ACM/IEEE
Int’l Symp. Modeling, Analysis and Simulation of Wireless and Mobile
Systems (MSWiM), pp. 151-158, 2005.
[63] M.D. Berg, O. Schwarzkopf, M.V. Kreveld, and M. Overmars,
Computational Geometry: Algorithms and Applications, second ed.
Springer-Verlag, 2000.
[64] T. Spyropoulos, K. Psounis, and C.S. Raghavendra, “Performance
Analysis of Mobility-Assisted Routing,” Proc. ACM MobiHoc,
pp. 49-60, 2006.

VOL. 12, NO. X,

XXXXXX 2013

Akira Uchiyama received the ME and PhD
degrees in information science and technology
from Osaka University in 2005 and 2008,
respectively, and is currently an assistantprofessor at Osaka University. He was a visiting
scholar in the University of Illinois at UrbanaChampaign in 2008 and a research fellow of theJapan Society for the Promotion of Science from2007 to 2009. His current research interests
include localization and applications in wirelessnetworks and ubiquitous computing. He is a member of the IEEE andInformation Processing Society of Japan (IPSJ).
Sae Fujii received the ME and PhD degrees in
information science and technology from Osaka
University, Japan, in 2008 and 2011, respectively. Her current research interests include
applications and services on mobile ad hoc
networks. She is a member of Information
Processing Society of Japan (IPSJ).

Kumiko Maeda received the ME and PhD
degrees in information science and technology
from Osaka University, Japan, in 2009 and 2006,
respectively. She is currently with IBM Japan,
Ltd. Her current research interests include
wireless network simulation and high performance computing for heterogeneous systems.

Takaaki Umedu received the ME degree in
informatics and mathematical sciences and the
PhD degree in information science from Osaka
University, Japan, in 2001 and 2004, respectively. He is currently an assistant professor at
Osaka University. His current research interests
include design and implementation of distributed
systems and mobile systems. He is a member of
the IEEE and the Information Processing Society of Japan (IPSJ).

Hirozumi Yamaguchi received the BE, ME, and
PhD degrees in information and computersciences from Osaka University, Japan, in
1994, 1996, and 1998, respectively. He iscurrently an associate professor at Osaka
University. His current research interests include
design, development, modeling, and simulationof mobile and wireless networks and applications. He is a member of the IEEE.

Teruo Higashino received the BS, MS, and
PhD degrees in information and computersciences from Osaka University, Japan, in
1979, 1981, and 1984, respectively. He joined
the faculty of Osaka University in 1984. Since
2002, he has been a professor in the Graduate
School of Information Science and Technology
at Osaka University. His current research interests include the design and analysis of distributed systems, communication protocols, andmobile computing. He is a senior member of the IEEE and the IEEE
Computer Society, a fellow of Information Processing Society of Japan(IPSJ), and a member of ACM and IEICE of Japan.