Wireless Netw (2013) 19:1037–1049
DOI 10.1007/s11276-012-0516-2

Quantifying relationship between relative position errorof localization algorithms and object identification
Noboru Kiyama • Akira Uchiyama •Hirozumi Yamaguchi • Teruo Higashino

Published online: 30 October 2012
Ó Springer Science+Business Media New York 2012

Abstract Positioning of things, devices and people is thefundamental technology in ubiquitous computing. However, few literature has discussed the impact of positioning
errors due to localization algorithm properties such asranging noise and deployment of anchors on people’s
identification of objects. Since several factors such as relative distance, relative angles and grouping of objects are
intricately related with each other in such identification, it
is not an easy task to investigate its characteristics. In thispaper, we propose criteria to assess the ‘‘accuracy’’ of theestimated positions in identifying the objects. The criteria
are helpful to design, develop and evaluate localization
algorithms that are used to tell people the location of
objects. Augmented reality is a typical example that needs
such localization algorithms. To model the criteria without
ambiguity, we prove that the Delaunay triangulation wellcaptures natural human behavior of finding similarity
between estimated and true positions. We have examineddifferent localization algorithms to observe how the proposed model quantifies the properties of those algorithms.
Subjective testing has also been conducted using questionnaires to justify our quantification sufficiently renders
human intuition.

N. Kiyama (&)  A. Uchiyama  H. Yamaguchi  T. Higashino
Graduate School of Information Science and Technology,
Osaka University, 1-5 Yamadaoka, Suita, Osaka 5650871, Japane-mail: n-kiyama@ist.osaka-u.ac.jp
A. Uchiyama
e-mail: utiyama@ist.osaka-u.ac.jp
H. Yamaguchi
e-mail: h-yamagu@ist.osaka-u.ac.jp
T. Higashinoe-mail: higashino@ist.osaka-u.ac.jp

Keywords Relative positioning  Localization 
Object identification  Delaunay triangulation

1 Introduction
Positioning systems have been investigated so far for location-aware services such as outdoor/indoor navigation andpersonal object identification in rooms. GPS is the mostpopular global system for outdoor positioning of single
nodes. For the situation where GPS is not available, localization algorithms using a variety of devices have beendeveloped. In wireless sensor networks, cooperative selflocalization is mandatory since in most cases we cannot
attach GPS to small-sized wireless sensor nodes due to limitation of cost and battery lifetime. Some other services suchas support of social interaction [1] and indoor navigation for
emergency service [2] need positioning of mobile nodes.
In those applications, the accuracy of position information is highly significant. In particular, we focus on suchapplications that need identification of real objects fromposition information. Let us suppose an AR (augmented
reality) system in a huge storehouse that shows article IDs
over camera views by balloons using the estimated positions of those articles (Fig. 1). The errors from the positioning system may directly appear as the deviation of ID
balloons from the true positions in the camera views.
Although case 1 (Fig. 1(a)) and case 2 (Fig. 1(b)) have
similar amounts of deviations from the true positions, mostpeople may not be able to find the correct matching in case
2 where switching of B and C is likely to occur (or even
A and B). This is obviously because the relative location of
B and C (and also A and B) is quite different from the truth.
As seen, such errors that cause mismatching between
estimated positions and truth should be represented not

123

1038

Wireless Netw (2013) 19:1037–1049

Subjective testing has also been conducted using 120
questionnaires. Analyzing the obtained 6,480 answers from54 examinees, we have confirmed that our quantification
could sufficiently render human perception.

2 Related work
2.1 Relative position accuracy(a) case 1(b) case 2

Fig. 1 Example of object identification in augmented reality: AR
system shows article IDs over camera views by balloons using
estimated positions of those articles. Most people may not be able tofind the correct ID matching in b although a and b have similar errors
from the positioning system

only by the deviation from the true positions but also by thedeviation from the true position relationship. Although theterm ‘‘relative position’’ partially captures the concept of
position relationship, it does not take the impact on people’s
object identification into consideration (namely, it is definedindependently of application context). Therefore, ourapproach is differentiated from existing ones that have dealt
with relative position accuracy [3, 4]. In brand-new mobile
and pervasive applications that associate estimated location
information obtained by positioning systems with thephysical things, such an impact should be considered andthus some reasonable criteria are desired for the purpose.
In this paper, we focus on how to characterize the outputs by a localization algorithm and try to quantify the
impact of positioning errors on people’s identification of
objects independently of specific localization algorithms.
Given a set of estimated positions of target objects and theanonymous set of their true positions, we propose criteria
to access the ‘‘accuracy’’ of the estimated positions in
identifying the objects at true positions. The proposed
accuracy criteria can be used in design, development andevaluation of localization algorithms that are used to tellpeople the location of objects (augmented reality is atypical example). To define the criteria without ambiguity,
we prove that (1) neighbor proximity and uniqueness are
significant factors to identify objects and the Delaunay
triangulation captures these properties, and (2) grouping of
nearby neighbors should also be considered and properlydesigned clustering captures the property. Then position
relationship dissimilarity is defined by the degree of discrepancy (DoD) of Delaunay triangulations on estimatedand true positions considering clusters.
In order to validate our approach, we have analyzed
properties of three localization algorithms using the proposed criteria. The results have shown that the criteria
could capture the qualitative properties of each algorithm.

123

There have been several researches that deal with relative
position accuracy [3–5] in different research domains. For
example, Ref. [5] in the computer vision research considers
the correctness of relationship between two objects byshapes or directions in 2D or 3D space. However, theseapproaches do not consider the correctness of position
estimation in terms of object identification.
Relative positioning accuracy analysis has beenachieved in wireless sensor network localization by several
papers like Refs. [3, 4]. Most of these papers dealing withrelative positioning accuracy have focused on the errors
from the measurement. Since the anchors are not concernedin relative positioning, errors are usually defined as deviation from the measurement such as distance, angles and
RSS. Therefore, these approaches are different from ours
since they do not take the impact on people’s object
identification into account. In other words, they are definedindependently of application context.
2.2 Localization algorithm classification
In Sect. 6, we have analyzed some existing localization
algorithms by our proposed criteria. Before that section, we
briefly address the classification of localization algorithms
here. We note that this section is not intended to survey
recent work on localization, but to introduce different typesof localization algorithms.
Range-based localization techniques rely on distanceestimation by received signal strength (RSS) to distancemapping, time of arrival (TOA) by ultrasound or audible
sound, time difference of arrival (TDOA) in ultra wideband or simultaneous use of RF and ultrasound [6] and soon. Directional antennas are often used to estimate angle ofarrival (AOA). Based on the ranging technique, this category can further be categorized into two different types of
localization algorithms. Single node localization uses trior multi-lataration where distance or angle informationfrom at least three reference points is used to determine thelocation (GPS falls into this category). Wi-Fi and/or cellular fingerprinting such as [7] also fall into this category.
On the other hand, MDS-MAP [8] is a known algorithm for
localizing multiple nodes simultaneously. It uses shortest
path information or other ranging techniques to estimate

Wireless Netw (2013) 19:1037–1049

the distance, and uses ‘‘multidimensional scaling’’ todetermine their positions.
Range-free techniques are cost effective alternatives
since they only require communication function. Amorphous [9] is a well-known range-free algorithm that utilizes
hop counts from landmarks, where each node estimates its
coordinates by finding coordinates that minimize the totalsquared error between the calculated and estimated distances. TRADE [10] is a constraint-based algorithm tolocalize mobile nodes. It constrains the location of nodes
from temporal–spatial information about wireless connectivity and movement, and estimates likely points from theregion that satisfies the constraints.
2.3 Delaunay triangulation for similarity quantification
Pattern matching problems in image recognition deal withquantifying relationship between two objects. The basic
algorithm usually consists of two processes; feature
extraction and identification. The former process extracts
significant points (e.g. a nose or eyes in facial recognition)from input data. The latter process quantifies these significant points by classifying or categorizing them. There are
two types of identification in pattern matching problems.
One is statistical pattern recognition which compares input
data with enormous accumulated data. Another is structural
pattern recognition which analyzes deployment of significant points obtained from input data. Therefore priorknowledge is not required. For example, in Ref. [11],eigenvectors are used for identification in facial recognition. In Ref. [12], singular points are used for identificationin image matching. Ref. [13] obtains relationships between
significant points using the Delaunay triangulations for
identification in fingerprint matching. Ref. [14] proposedan algorithm to group points using reduced Delaunaygraphs (RDGs). It is based on the Gestalt law of proximity
in Gestalt psychology [15] that suggests the law of proximity as an important factor of grouping objects in humanperception.
These approaches use the Delaunay triangulation torepresent the feature amount of given images. Our
approach is completely different in the sense that we aim atquantifying the relationship between localization errors andobject identification, and use the Delaunay triangulationand clustering for such quantification.
2.4 Our contributions
To the best of our knowledge, this is the first approach thatquantifies localization errors in the context of object
identification. As briefly discussed in Sect. 1, the existing
approaches that have dealt with relative position accuracy[3, 4] are different from ours in the sense that they consider

1039

relative position errors, which are defined by distanceamong objects and relative angles. We can intuitively
understand that the ‘‘relative position errors’’ may represent some features of algorithm performance in object
identification, though discussion has not been given andcorresponding criteria have not been quantitatively defined.
Meanwhile, our approach considers several features inobject identification, such as proximity–uniqueness property, clustering and viewpoints. Justification has been doneby experiments and subjective test using questionnaires
and a tool developed for this purpose. As stated in theprevious section, the notion of Delaunay triangulation
similarity is found in image recognition, but they use theDelaunay triangulations only to characterize point patterns.
In other words, they use only the planer-graph property tocharacterize a point distribution on a 2D plane.
We believe that new mobile and pervasive applications
like navigation of articles and people are beneficial from
our approach to assess adequacy of positioning systems
they use.

3 Basic approach
3.1 Concept
Position relationship dissimilarity between true and estimated positions is quantified by the Delaunay triangles in
our approach. To imagine what should be considered in
node identification, we introduce a simple example. Figure 2(a) shows real placement of nodes and Fig. 2(b),(c) show two different estimations. We assume these figures are drawn in bird’s-eye view. Compared with the true
positions, the relative positions of nodes F and G in
Fig. 2(c) are ‘‘opposite’’ from the viewpoint of node C,
while those in Fig. 2(b) are consistent. In terms of relationship between C and the pair (F, G), we may think
Fig. 2(b) is ‘‘better’’ than Fig. 2(c).
We have also prepared 4 sets of node positions witherrors as shown in Fig. 3 where the true positions areshown in Fig. 3(c). Each set is generated by adding 3 merror to the true position of each node in a 20 m 9 20 m
square area. Therefore, the average position errors of thosesets are the same. We note that solid lines indicate alphabetically consecutive node pairs (H–A is also drawn) andarrows show the position errors. We can say that Fig. 3(a),(b) have certain similarity to the true positions rather thanFig. 3(d), (e) although their average errors are the same.
Suppose identification of anonymous nodes at true positions by a given set of estimated positions like Fig. 3(a) as
exemplified in Sect. 1. Obviously neither of Fig. 3(d), (e) is
helpful for such a purpose because the position relationshipamong neighbors is hardly preserved. For example, in the

123

1040

Wireless Netw (2013) 19:1037–1049

Fig. 2 Relative positions of
F and G from bird’s-eye view:a real position, b ‘‘consistent’’estimation, c ‘‘inconsistent’’estimation

Fig. 3 Comparison of relative
positions: a, b consistentestimations, c real position, d,e inconsistent estimation.
Arrows indicate real positions ofeach nodetrue positions, node O seems surrounded by the othernodes, but Fig. 3(d), (e) never indicate such ‘‘relationship’’among neighbors.
We try to define such position relationship dissimilaritythat affects identification of nodes. The position relationship is usually defined by relations among neighboring
nodes, but we need to define necessary and sufficient‘‘neighbors’’ in the context of node identification.
Let us consider identifying node O in Fig. 4(a) by
regarding a set of its ‘‘neighbors’’ as reference points. The
set {A, B, C, D, E, F} where each node is close to O is apossibility, but F may be redundant since having A and B in
the set may be sufficient to identify O. This concept iscalled uniqueness. The uniqueness is defined for a node in anode set and the node is called unique if there is noalternative in the node set. In the example, the pair of A andB may be substituted for F’s role of a reference point andtherefore F is not unique in {A, B, C, D, E, F}.

123{A, B, C, D, E} is such a set of nodes where each nodesatisfies the uniqueness. Even though all the nodes in anode set is unique, it does not mean the uniqueness ofthe node set itself. For example, different node set{A, C, D, E, G} shown in Fig. 4(b) is also such a node set.
To distinguish these node sets and to choose the best one,
we introduce proximity to O, i.e. the closer one to O should
be prioritized. In this case, {A, B, C, D, E} is better than{A, C, D, E, G}.
3.2 Definition of position relationship dissimilarity
Based on the illustrative examples, we know that a set ofneighbors that satisfies the above uniqueness and proximity
simultaneously should be chosen. For this purpose, we
introduce the proximity–uniqueness concept hereafter. We
define the property of proximity–uniqueness with respect tonode O as follows.

Wireless Netw (2013) 19:1037–1049

1041

Fig. 4 ‘‘Neighbor’’ sets of node
O: {A, B, C, D, E}. a Node F is
not a neighbor of node O due tonode A, B, b Node G is not aneighbor of node O due tonode B

Definition 1 Let V and N(O) denote the set of all thenodes and the set of node O’s neighbors, respectively. We
define a necessary and sufficient condition for node X to be
an element of N(O) as follows.
X 2 NðOÞ , for each Z 2 V  fX; Og;
9Y 2 NðOÞ  fXg; f ð4OYXÞ  f ð4OYZÞ
Let us assume that f represents X’s negative ‘‘proximity–
uniqueness’’ using some neighbor Y 2 NðOÞ (larger
f means less ‘‘proximity–uniqueness’’). Then thedefinition means that X is a neighbor if and only if thepair of X and some other neighbor Y achieve better
proximity–uniqueness than any other pair of Z and Y. We
regard N(O) that satisfies this condition as the best set ofneighbors of O.
Finally, we need to define function f to represent theproximity–uniqueness. More concretely, f is a function oftriangles and should return the negative degree of theproximity–uniqueness of X with respect to O and Y thanany other node Z. For the objective, we define the value off(T) as the circumradius of given triangle T. In this case, as
shown in Fig. 5, X is chosen as a neighbor of O based on
the proximity and uniqueness as follows.
1.

2.

(Proximity) when node E of Fig. 5(a) is regarded as
Z in Definition 1, there exists X such that thecircumradius of triangle OYX is smaller than that oftriangle OYE. Therefore, E cannot be a neighbor in thepresence of X.
(Uniqueness) when node D of Fig. 5(b) is supposed tobe Z in Definition 1, the circumradius of triangle OYX
is smaller than that of triangle OYD. Moreover, X is
located in the circumcircle of OYD and no node canmake a smaller circumcircle with Y and O. Therefore,
X cannot be replaced by any other node due to its
uniqueness to Y and O.

In order to prove validity of the proposed criteria withrespect to human perception, we will show the results fromreal experiments based on a questionnaire in Sect. 5. The
set of triangles determined by function f which returns thecircumradius is exactly equal to that of triangles derived byusing the Delaunay triangulation algorithm [16]. We notethat since a Delaunay triangulation is always unique for agiven set of nodes, its corresponding N(O) is also unique.
Therefore, we define the position relationship dissimilarity between a true position set and an estimated position
set (usually given by a localization algorithm) as the degreeof discrepancy (DoD) of Delaunay triangles formed on
those sets. We define DoD by graph edit distance (GED)[17], which represents the minimum number of edge
insertion and deletion required to transform one graph into
the other. GED indicates the possible number of incorrect
identification. Let Er and Ee denote the sets of Delaunayedges in true positions and estimated positions, respectively. Also the Delaunay diagrams on true positions andestimated positions are denoted as Gr = (V, Er) andGe = (V, Ee), respectively. The GED between Gr and Ge isdefined as follows.
PGEDðX; YÞ
X;Y2V
Graph edit distance ¼
2
8
if ðX; YÞ 2 Er ^ ðX; YÞ 62 Ee<
1GEDðX; YÞ ¼_ðX; YÞ 62 Er ^ ðX; YÞ 2 Ee:
0 otherwise
We use a normalized value of GED to define DoD.
When Ee does not include any edges in Er, GED takes the
maximum value of |Er| ? |Ee|. Hence we define DoD as
DoD ¼

Graph edit distance:jEr j þ jEe j

In the example of Fig. 6, common edges between Gr(left) and Ge (right) are shown by solid lines. There are

123

1042

Wireless Netw (2013) 19:1037–1049

Fig. 5 Neighbors definition
based on circumscribed circles:
a node E is not a neighbor ofnode O because the radius of 4
OYE is longer than that of
4OYX. b Node X is a neighborof node O because the radius of
4OYX is shorter than that of
4OYD

Fig. 6 An example ofdiscrepancy between Delaunay
triangulations: links OB, DH,
and BF are extra Delaunayedges and links OJ, AH, and CI
are missing Delaunay edges

three missing edges (shown by dotted lines) and three extra
edges (shown by dashed lines) in Ge. Thus GED is 6 in this6
’ 0:26. We note that when DoD
case and DoD becomes 23
is equal to 0, all Delaunay edges in Ee correspond to the
Delaunay edges in Er. Thus all neighbors of each node in
the estimated positions completely match those in the realpositions. As DoD approaches to 1, it is harder to identify
nodes from the estimated positions.
We assume there is no need to calculate DoD in realtime since DoD is expected to be used for choosing the best
localization algorithms before running location-based systems. Nevertheless, we discuss the computational complexity of the proposed method. The computation ofDelaunay Triangulations requires O(nlog n) while thatof graph edit distance is O(n2) where n is the number of123

nodes. Therefore, the computational complexity is O(n2).
This indicates it is also possible to compute DoD in realtime if needed.

4 Additional important criteria
In this section, we discuss other criteria that should also be
considered to capture human perception as well as theDelaunay triangulation.
4.1 Viewpoint location
We have defined DoD based on bird’s-eye view (i.e.
2D-DoD). However, its 3D version (3D-DoD) should also

Wireless Netw (2013) 19:1037–1049

1043

Fig. 7 Effect of different
viewpoints

Fig. 8 Transformation withviewpoint: a objects A, B, C,
and D on plane H are projected
to objects A0 ; B0 ; C 0 , and D0 on
plane M which is perpendicular
to the line of sight. b Projectionof A and C seeing from the side

be designed to consider viewpoint location in the realworld. In applications such as a storehouse example shownin Fig. 1, estimation results are shown to users in a target
field. In such cases, object deployment seems different
depending on viewpoints of users. The major effect ofviewpoints is that distance between nearby objects appears
to be longer than that between distant objects. For example,
distance between node F and H is shorter than that between
A and C in the bird’s-eye view shown in Fig. 7(a). However, distance between node F and H becomes longer thanthat between A and C in 3D view (see Fig. 7(b)).
In order to define DoD considering such viewpoint
effects, we transform the ground plane (2D-plane) toanother plane in a 3D space by using the line of sight.
Suppose that the target region is a ground region H where aviewpoint is at e = (x, y, z) and the eyes are looking at apoint h = (p, q, 0) in region H as shown in Fig. 8(a). We
introduce the oblique region M which is perpendicular to!
eh (the line of sight) and contains h. Then node positions
A, B, C, and D on H are projected onto M. We consider
rays from the viewpoint e to each node position. Finally,
we map node positions A, B, C, and D on H to intersections
A0 ; B0 ; C0 , and D0 of M and the rays, respectively. For
example, Fig. 8(b) shows projection of A and C seeing
from the side. The distance between A and h is equal to thatbetween C and h on H. However, after projection onto M,
distance between A0 and h becomes shorter than thatbetween C0 and h as shown in the figure. By the abovetransformation, we can apply our approach to locationbased applications affected by viewpoints in a 3D space.

We note that the correspondence between the bearingsof real/estimated positions is assumed to be known.1 This is
usually done by referring to absolute reference points on
the ground (e.g. buildings and signs in real world’s views)
or digital compasses in mobile devices.
4.2 Nodes in close proximity
In human perception, nodes in close proximity are regarded
as a cluster (i.e. group) [15]. Since those nodes in the samecluster are too close to each other, they may not be necessary to be distinguished in most realistic applications andsituations. Meanwhile, if organization of clusters in estimated positions is quite different from that in true positions, it significantly affects identification accuracy.
Therefore, we quantify the degree of discrepancy
between two cluster organizations in real and estimatedpositions. For this purpose, we propose a clustering algorithm that fits for human perception and introduce a similar
idea to the graph edit distance in the Delaunay triangulations. We note that the existing clustering algorithms[18–21] are classified into hierarchical or non-hierarchicalalgorithms. In non-hierarchical algorithms such as [19], thenumber of clusters must be specified before clustering
nodes. However, since clustering based on human perception largely depends on the distribution of nodes, it is1

Without this assumption, identification becomes very hard sincerotation should be considered.

123

1044

Wireless Netw (2013) 19:1037–1049

Fig. 10 # of mis-assignments of 54 subjects. Each dot indicatesaverages of mis-assignments and each line shows ranges of misassignments

Fig. 9 Example of questionnaire: picture shows estimated positionsof 10 objects. Photograph showing real positions of corresponding 10
persons. Subjects are required to guess IDs of each person

hard to specify the number of clusters beforehand, andhierarchical algorithms such as [20] are more appropriate.
Based on informal interviews with emergency medical
doctors who are our collaborators in the emergency rescue
support project [22] and actually need identification of
injured people in disaster sites, we recognize that intercluster distance is a significant factor. We take from theexisting clustering algorithm a strategy that renders thisfactor.
To consider inter-cluster distance, we introduce thegroup average method [21] which uses the average distance
between nodes in two different clusters as the inter-cluster
distance. Inter-cluster distance d(C1,C2) of clusters C1 andC2 is defined as:XX1
dðC1 ; C2 Þ ¼
dðp; qÞ
ð1Þ
jC1 jjC2 j p2C1 q2C2
where |C1| and |C2| respectively denote the number ofnodes in C1 and C2, and d(p, q) is the Euclidean distance
between nodes p and q.
[Clustering Algorithm](Step 1) Let N be the number of nodes. Initialize the set
C of clusters to N clusters where each cluster has one node.
(Step 2) For clusters C1 and C2 in C with the shortest
inter-cluster distance, check if d(C1, C2) is less thanthreshold a or not. If true, merge C1 and C2 in C and go to
Step 2. Otherwise terminate the algorithm. Empirically ashould be less than 1 m and a = 0.6 m was used in thefollowing experiments.

123

We tailor DoD defined in Sect. 3.2 such that it can
incorporate the clustered nodes. Firstly, we organize theclusters over real positions using the above algorithm. Then
we apply the same cluster organization to estimated positions. Regarding the centroid of each cluster as the locationof the cluster, we build the Delaunay triangles on real andestimated clusters and compare them to derive DoD.

5 DoD and identification accuracy correlation
We have conducted an experiment to see the correlation
between DoD and human intuition. In the experiment, wehave prepared 30 pairs of real positions and their corresponding estimated positions of 10 nodes (actually they are
10 students). Eyepoints in estimation results were set to the
4 corners of the area with 170 cm height. Therefore, wehave prepared 120 pairs as a total and 54 examinees participated in this experiment. As a total, we had 6,480
answers for 120 questionnaires.
An example questionnaire is shown in Fig. 9 where
node IDs were shown in the estimated positions but hiddenin the real positions. For real positions, we have used thepictures of 10 students lying on the floor. Such a situation is
likely to happen in emergency sites where injured persons
are waiting to be treated and delivered to hospitals [22].
Given a pair of position sets, each examinee was required
to identify node IDs in the real positions. The correctnessof the answer is observed by the number of mis-assignments in each pair.
In order to examine the individual variability before theanalysis of results, we summarized the average number of
mis-assignments with error bars for each examinee. From
the result shown in Fig. 10, we can see that the average
number of mis-assignments is very similar among

Wireless Netw (2013) 19:1037–1049

1045

We have also calculated the correlation coefficient and it
was 0.82, which generally indicates strong relationship.

6 Analysis of localization algorithm by DoD
In the last section, we have shown that DoD could capture
human perception in identifying object location. Based on
this, we characterize different types of localization algorithms and analyze their localization ‘‘accuracy’’ in termsof object identification.
6.1 Localization algorithms to be examined
Fig. 11 DoD versus # of mis-assignments. Each dot indicatesaverages of mis-assignments and each line shows ranges of misassignments

Fig. 12 Avg. DoD versus # of mis-assignments. The line indicatesstraight-line approximation

examinees and it is not necessary to take individual variability into account. We note that for the same questionnaire, there is of course variability among examinees. Even
though it is mostly impossible to disregard such variability
for different types of questionnaires, the data in Fig. 10 is
helpful to analyze DoD trend in the followings and tojustify the uniformity of the dataset among the examinees.
Figure 11 shows the number of mis-assignments witherror bars for each DoD value. Due to difference among
questionnaires and viewpoints, the range of mis-assignments for the same DoD value seems spread. However, we
can see certain trend of mis-assignment growth along with
DoD where the trend more clearly appears on the averagevalues.
In order to make this trend more visible, we have taken
the averages of DoDs and the number of mis-assignments
over the 13 different examinees and 4 different eyepoints.
From the resulting 30 cases, we have discarded 10 %to avoid outliers and finally 27 cases were left in Fig. 12.

We have selected (a) GPS as a non-cooperative, rangebased positioning system, (b) MDS-MAP [23] as a multihop, range-based cooperative localization algorithm, and(c) TRADE [10] as a multihop, range-free cooperative
localization algorithm that utilizes connectivity information. This is reasonable selection where we can see thecharacteristics of different localization algorithms on DoD
through comparison between (1) non-cooperative andcooperative algorithms, and (2) range-based and range-freealgorithms. Although we have not selected an algorithm
from the non-cooperative range-free category, we can
suppose its characteristic from the above comparison.
In non-cooperative range-based techniques such as GPS,each node independently estimates its own position byusing direct measurement from reference points. MDSMAP is a localization algorithm based on multi-dimensional scaling [24]. MDS-MAP exploits estimated distances between nodes based on received signal strength(RSS). Then the positions of nodes are estimated by matrix
calculations with constraints on distances among nodes.
Euclid distance between nodes is approximated by network
hop counts and estimated per-hop distance.
Finally, TRADE is a localization algorithm using
internode connectivity information. Nodes in TRADE
continue adjusting their positions and past trajectories to fit
for spatial constraints from the maximum communication
range and maximum movement speed.
6.2 Simulation settings
The default values of simulation parameters are shown in
Table 1. Four viewpoints were set at the corners of thetarget region with 170 cm height. To generate GPS errors,
we have given both distance and directional errors for eachtrue position which were randomly selected in [0, eg] and[0, h], respectively. Then GPS has been examined with the
maximum distance error eg 2 ½0:4; 2:8 m with step 0.8 m
and the angle error h = [0.5p, 2.0p] with step 0.5p. MDSMAP has been examined with three distributions of

123

1046

Wireless Netw (2013) 19:1037–1049

Table 1 Simulation parameters
Area size

10 (m) 9 10 (m)# of landmarks

4# of nodes

30

Node mobility

Random waypoint

Moving speed

1.0–1.5 (m/s)

Pause time0 (s)Simulation time

100 (s)Clustering threshold (a)0.6 (m)measurement errors; uniform, normal and biased distributions with the ‘‘maximum measurement error’’ em, which is
given as a ratio to true distances. In the uniform distribution, the measurement error was determined by randomly
choosing values from [ - em, em]. In the normal distribution, the measurement error followed the normal distribution with mean 0 and r = em/2. In the biased distribution,
it was determined by randomly choosing values from[ - em, - em ? 0.05] and [em - 0.05, em] (errors stickaround ± em with 5 % deviation). In TRADE, the numberof nodes was selected from 20, 30, 40, and 50, and communication range r was set to 2, 4, 6, or 8 m.
In comparison between different localization algorithms
in Sect. 6.4, the area size was set to 25 m 9 25 m and thenumber of nodes was 20. In GPS, distance and directional
errors were randomly selected from the range [0 m, 3 m]
and [0, 2.0p], respectively. We randomly selected distancemeasurement errors in MDS-MAP from the range [ - 10,
10 %] and used 10m of communication range r in TRADE.

Fig. 13 Maximum distance error eg in GPS versus DoD and absolute
errorFig. 14 Maximum measurement error em in MDS-MAP versus DoD
and absolute error

6.3 DoD characteristics of different localization
algorithms
Fig. 13 shows DoDs versus the maximum distance error eg
in GPS. The bar chart indicates the average distance errors
using the right Y-axis (i.e. it shows not ‘‘relative errors’’
but ‘‘absolute errors’’). The important point is that although
the absolute errors are almost equal among different angle
errors in [0.5p, 2.0p], DoDs shown by the line chart using
the left Y-axis show different values and trends. Since
angle errors significantly affect the relative location ofnodes, a larger angle error should generally indicate more
rapid growth of DoD. This property can be observed in the
DoD line chart, and we can say that DoD can distinguishsuch errors that are caused by directional errors.
Figure 14 shows DoDs versus the maximum distanceerror em in MDS-MAP. Similarly with the GPS case, theabsolute errors are shown by the bar chart using the rightY-axis. The interesting characteristics are found in the biased
distribution where the absolute errors are largest but DoDs
are smallest with larger em (50 and 70 %). Since biased

123

Fig. 15 # of nodes in TRADE versus DoD and absolute error

distribution generated almost two constant values as errors(± em with small deviations), in the most part the position
relationships were kept intact under large absolute errors. As
in the GPS case, we could observe that DoD could capturesuch a property.

Wireless Netw (2013) 19:1037–1049

1047

Fig. 16 Estimated positions bydifferent localization
algorithms. Each line indicatesthe distance and angle error ofeach node in estimated positions

Table 2 Position errors of localization algorithms
GPS

MDS-MAPTRADE

Absolute error (per R)

0.168

0.188

0.154

Degree of discrepancy

0.331

0.127

0.246

Finally, DoDs versus the number of nodes in the case of
TRADE are shown in Fig. 15. Overall, the absolute errorsof TRADE decrease with the increase of node density
because the amount of spatial constraints increases. Communication ranges also affect absolute errors since a larger
communication range may increase connectivity. However,the large communication range may also increase absolute
errors since it may relax spatial constraints. When thecommunication range was 2 m, the absolute error was thesecond worst among the four ranges because the range wastoo small to constrain the location of other nodes. Here, due
to the feature of range-free algorithms where relative
positions are not preserved strictly, the position relationshipis also affected by the evaluated factors, i.e. node density
and communication range. In this context, DoDs follow thesimilar trend of the absolute errors, which is natural.

6.4 Comparison between different localization
algorithms
Figure 16(b), (d) show snapshots of estimated positions of
the three algorithms and their real positions are shown in
Fig. 16(a) when the number of nodes is 20 with 4 landmarks (IDs 0–3). The absolute errors are shown by segments from each node. We can see the difference inrelative positions between these algorithms, especially fornodes marked by circles in the snapshots. Relative positions in MDS-MAP (Fig. 16(c)) are very close to those in
the real positions (Fig. 16(a)).
Table 2 also describes the absolute and relative errors atthat time. Surprisingly, MDS-MAP is the best in the relative error but the worst in the absolute error. This means
relative errors cannot be measured by absolute errors only.
Therefore, it is important to evaluate localization algorithms in terms of relative errors depending on services
and applications. From the above results, we have confirmed that DoDs could represent the different characteristics of localization algorithms in terms of position
relationship.

123

1048

Wireless Netw (2013) 19:1037–1049

7 Conclusion
In this paper, we have proposed a method to quantify
localization accuracy in terms of object identification. We
have analyzed primary factors that affect object identification and have found that the Delaunay triangulation
could capture such factors. We have also analyzed additional factors such as eyepoints and grouping. By subjective testing based on 120 questionnaires by 54
examinees with 6,480 answers, we have justified our proposed metric, i.e. degree of discrepancy (DoD) between thereal and estimation positions. Simulation results have also
shown that DoD could capture the different characteristics
of localization algorithms which have not been found by
absolute errors. We believe that new emerging mobile andpervasive applications such as AR-based navigation are
beneficial from our approach to assess adequacy of positioning systems they use.
Acknowledgments

This research was supported by JST, CREST.

References
1. Olguin, D. O., Waber, B. N., Kim, T., Mohan, A., Ara, K., &Pentland, A. (2009). Sensible organizations: Technology andmethodology for automatically measuring organizational behavior. IEEE Transactions on Systems, Man, and Cybernetics, Part
B: Cybernetics, 39(1), 43–55.
2. Lukowicz, P., Timm-Giel, A., Lawo, M., & Herzog, O. (2007).
WearIT@work: Toward real-world industrial wearable computing. IEEE Pervasive Computing, 6(4), 8–13.
3. Yang, Z., & Liu, Y. (2010). Quality of trilateration: Confidencebased iterative localization. IEEE Transactions on Parallel andDistributed Systems, 21(5), 631–640.
4. Ash, J. N., & Moses, R. L. (2008). On the relative and absolute
positioning errors in self-localization systems. IEEE Transactions
on Signal Processing, 56(11), 5668–5679.
5. Matsakis, P., & Wendling, L. (1999). A new way to represent therelative position between areal objects. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 21(7), 634–643.
6. Priyantha, N. B., Chakraborty, A., & Balakrishnan, H. (2000).
The cricket location-support system. In Proceedings of the
MobiCom (pp. 32–43).
7. Place engine. http://www.placeengine.com/en.
8. Shang, Y., Ruml, W., Zhang, Y., & Fromherz, M. P. J. (2003).
Localization from mere connectivity. In Proceedings of the ACM
MobiHoc (pp. 201–212).
9. Nagpal, R., Shrobe, H., & Bachrach, J. (2003). Organizing a
global coordinate system from local information on an ad hoc
sensor network. In Proceedings of the information processing insensor networks (pp. 333–348).
10. Fujii, S., Nomura, T., Umedu, T., Yamaguchi, H., & Higashino,
T. (2009). Real-time trajectory estimation in mobile ad hoc networks. In Proceedings of the ACM international conference onmodeling, analysis and simulation of wireless and mobile systems(pp. 163–172).

123

11. Turk, M., & Pentland, A. (1991). Face recognition using eigenfaces. In Proceedings of the IEEE conference on computer visionand pattern recognition (pp. 586–591).
12. Demirci, M. F., Platel, B., Shokoufandeh, A., Florack, L. L. M. J.,& Dickinson, S. J. (2009). The representation and matching ofimages using top points. Journal of Mathematical Imaging andVision, 35(2), 103–116.
13. Bebis, G., Deaconu, T., & Georgiopoulos, M. (1999). Fingerprint
identification using Delaunay triangulation. In Proceedings of theIEEE international conference on intelligence, information andsstems (pp. 452–459.
14. Papari, G., & Petkov, N. (2005). Algorithm that mimics humanperceptual grouping of dot patterns. In Proceedings of theinternational symposium on brain, vision and artificial intelligence (Vol. 3704, pp. 497–506).
15. Wertheimer, M. (1938). Laws of organization in perceptualforms. A Sourcebook of Gestalt Psycychology, 71–88.
16. Lee, D.T., & Schachter, B.J. (1980). Two algorithms for constructing a Delaunay triangulation. International Journal of
Parallel Programming, 9(3), 219–242.
17. Bunke, H. (1997). On a relation between graph edit distance andmaximum common subgraph. Pattern Recognition Letters, 18(8),689–694.
18. Murtagh, F. (1983). A survey of recent advances in hierarchicalclustering algorithms. The Computer Journal, 26(4), 354–359.
19. Macqueen, J. B. (1967). Some methods of classification andanalysis of multivariate observations. In Proceedings of theBerkeley symposium on mathematical statistics and probability(pp. 281–297.
20. Ward, J.H. (1963). Hierarchical grouping to optimize an objectivefunction. Journal of the American Statistical Association,
58(301), 236-244.
21. Sokal, R.R., & Michener, C.D. (1958). A statistical method forevaluating systematic relationships. University of Kansas Scientific Bulletin, 28, 1409–1438.
22. E-triage project. http://www-higashi.ist.osaka-u.ac.jp/research/etriage.html.
23. Shang, Y., Ruml, W., Zhang, Y., & Fromherz, M. (2004).
Localization from connectivity in sensor networks. IEEE Transactions on Parallel and Distributed Systems, 15(11), 961–974.
24. Carroll, J. D., & Chang, J. J. (1970). Analysis of individual differences in multidimensional scaling via an N-way generalizationof Eckart-Young decomposition. Psychometrika, 35(3), 283–319.

Author Biographies
Noboru Kiyama received the
ME degree in Information andComputer Science from Osaka
University, Japan in 2010. He iscurrently a researcher at Hitachi,Ltd. and also a doctoral student at
Osaka University. His current
research interests include Telematics services for electric vehicles. He
is a member of Information Processing Society of Japan (IPSJ).

Wireless Netw (2013) 19:1037–1049
Akira Uchiyama received the
ME and Ph.D. degrees in Information and Computer Sciencefrom Osaka University, Japan in2005 and 2008, respectively, andis currently an Assistant Professor at Osaka University. He wasa visiting scholar in University
of Illinois at Urbana- Champaign
in 2008 and a research fellow of
the Japan Society for the Promotion of Science from 2007 to
2009. His current research interests include modeling, designand development of wirelessnetwork applications. He is a member of IEEE and Information Processing Society of Japan (IPSJ).

1049
Teruo Higashino received his
BS, MS and Ph.D. degrees inInformation and Computer Sciences 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 Graduate School ofInformation Science and Technology at Osaka University. His
current research interests include
design and analysis of distributed systems, communication
protocol and mobile computing.
He is a senior member of IEEE, a fellow of Information Processing
Society of Japan (IPSJ), and a member of ACM and IEICE of Japan.

Hirozumi Yamaguchi received
his BE, ME and Ph.D. degrees inInformation and Computer Sciences from Osaka University,
Japan in 1994, 1996 and 1998,
respectively. He is currently an
Associate Professor at Osaka
University. His current researchinterests include design, development, modeling and simulation of mobile and wirelessnetworks and applications. He isa member of IEEE.

123