WLAN Finge p in ing based Indoo Posi ioning
in he P esence o Censo ed and D opped Da a
Von de Fakul ä ü Elek o echnik, In o ma ik und Ma hema ik
de Uni e si ä Pade bo n
zu E langung des akademischen G ades
Dok o de Ingenieu wissenscha en (D .-Ing.)
genehmig e Disse a ion
on
M.Sc. Manh Kha Hoang
E s e Gu ach e : P o . D .-Ing. Reinhold Häb-Umbach
Zwei e Gu ach e : P o . D .-Ing. Pe e A. Höhe
Tag de mündlichen P ü ung: 04. Mä z 2016
Pade bo n 2016
Diss. EIM-E/321
Acknowledgmen s
Fi s o all, I would like o gi e a g ea hanks o P o . D .-Ing. Reinhold Häb-Umbach o
being my esea ch supe iso . I would ha e ne e been able o comple e my esea ch wo k
and my disse a ion wi hou his con inuous suppo , unde s anding and pa ience. He has
kindly mo i a ed me o he new challenges and pa ien ly guided me o o e come he di i-
cul ies. I eel e y lucky o ha e me P o . Häb-Umbach and wo ked wi h him. I would also
like o hank P o . D .-Ing. Pe e A. Höhe who ha e e alua ed my disse a ion and gi en me
he aluable esponses o imp o e i s quali y.
Mo eo e , I would like o hank Vie namese go e nmen o g an ing he schola ship o
my i s h ee yea s o s udying in Ge many. Wi hou i , I would ha e ne e had such a good
chance o commence his PhD deg ee in Ge many. I also owe hanks o he Depa men o
Communica ions Enginee ing, Uni e si y o Pade bo n, o p o iding me he li ing expense
o my las wo yea s o my esea ch, in pa icula , once again hanks o P o . Häb-Umbach.
I eally app ecia e all he suppo om all s a membe s o he Wo ld Uni e si y Se ice
who ha e in oduced me o P o . Häb-Umbach, helped me o a ange he accomoda ion when
I i s came o Ge many and con inuously encou aged me du ing my esea ch.
Special hanks o my colleagues and s uden s a he Depa men o Communica ions En-
ginee ing who ha e always suppo ed me o p oceed my esea ch and imp o e my disse a i-
on. In pa icula , I wish o hank D .-Ing Jö g Schmalens öe o all o his suppo , aluable
echnical ideas and commen s, wi hou ha i would be e y di icul o me o comple e my
wo k.
Las bu no leas , I wish o hank my wi e, Thi Hien T ang Vu, and my li le daugh e ,
T a My Hoang, o wi hou hei encou agemen , suppo and pa ience, his wo k would
ha e no been comple ed. In addi ion, I would like o hank my pa en s who always beside,
con inuously suppo and encou age me o no only hese yea s bu also whole my li e.
3
Con en s
1. In oduc ion 1
2. Fundamen als o Indoo Posi ioning and S a e o Resea ch 5
2.1. P oximi y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. La e a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Angula ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4. Finge p in ing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5. Dead Reckoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6. Compa ison o Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Scien i ic Objec i es 18
4. Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a 20
4.1. Mo i a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2. Pa ame e Es ima ion using EM Algo i hm . . . . . . . . . . . . . . . . . 22
4.2.1. In oduc ion o he EM Algo i hm . . . . . . . . . . . . . . . . . . 22
4.2.2. EM algo i hm o Censo ed Gaussian Da a . . . . . . . . . . . . . 23
4.2.3. EM algo i hm o Censo ed and D opped Gaussian Da a . . . . . . 30
4.3. Op imal Classi ica ion Rule o Censo ed and D opped Gaussian Da a . . . 33
5. Sma phone Adap a ion wi hin he MLLR F amewo k 35
5.1. Mo i a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2. Model Adap a ion in he P esence o Censo ed and D opped Da a . . . . . 36
5.2.1. Mean Adap a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.2. Va iance Adap a ion . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3. Reg ession Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6. Hidden Ma ko Model o Indoo Use T acking 43
6.1. Mo i a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.2. Hidden Ma ko Model o Indoo Use T acking . . . . . . . . . . . . . . 43
6.3. Fo wa d Algo i hm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.4. Mo emen Vec o Es ima ion . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.4.1. S ep De ec ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.4.2. Mo emen Heading Es ima ion . . . . . . . . . . . . . . . . . . . 50
6.4.3. Mo emen Vec o Calcula ion . . . . . . . . . . . . . . . . . . . . 51
6.5. In oduc ion o Pseudo S a es . . . . . . . . . . . . . . . . . . . . . . . . . 52
i

Con en s
ii
7. Expe imen al Resul s on Indoo Posi ioning 55
7.1. Pa ame e Es ima ion and Classi ica ion . . . . . . . . . . . . . . . . . . . 55
7.1.1. EM algo i hm o censo ed da a . . . . . . . . . . . . . . . . . . . 55
7.1.2. EM algo i hm o censo ed and d opped da a . . . . . . . . . . . . 58
7.2. Sma phone Adap a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.2.1. Classi ica ion on A i icial Da a . . . . . . . . . . . . . . . . . . . 59
7.2.2. Classi ica ion on Field Da a . . . . . . . . . . . . . . . . . . . . . 60
7.3. HMM o Indoo Use T acking . . . . . . . . . . . . . . . . . . . . . . . 62
7.3.1. A i icial Da a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.3.2. Field Da a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8. Se e Based Indoo Na iga ion Sys em 65
8.1. O e iew o Se e A chi ec u e . . . . . . . . . . . . . . . . . . . . . . . 68
8.2. Da abase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
8.2.1. Map Tile Da a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
8.2.2. RSSI da a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.3. Sha ed Memo y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
8.4. O e iew o Sma phone Applica ion . . . . . . . . . . . . . . . . . . . . 74
8.5. Sys em Ope a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.5.1. Da a Ga he ing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.5.2. Localiza ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5.3. Na iga ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.5.4. Fea u es Unde De elopmen . . . . . . . . . . . . . . . . . . . . . 83
8.6. Communica ion Se cu i y . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
9. Conclusions 88
A. Appendix 91
A.1. De i a ion o EM Algo i hm . . . . . . . . . . . . . . . . . . . . . . . . . 91
A.1.1. Compu a ion o I0. . . . . . . . . . . . . . . . . . . . . . . . . . 91
A.1.2. Compu a ion o I1. . . . . . . . . . . . . . . . . . . . . . . . . . 91
A.1.3. Compu a ion o I2. . . . . . . . . . . . . . . . . . . . . . . . . . 92
A.1.4. Compu a ion o W En ies . . . . . . . . . . . . . . . . . . . . . . 94
A.1.5. Compu a ion o In o ma ion Ma ix I. . . . . . . . . . . . . . . . 95
A.2. Pa ame e s o Kalman Fil e . . . . . . . . . . . . . . . . . . . . . . . . . 99
A.3. And oid Sma phone Applica ion . . . . . . . . . . . . . . . . . . . . . . . 99
A.3.1. Mani es File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
A.4. Reques s and Responses o he Communica ion in Indoo Na iga ion Sys em 100
A.4.1. Se F inge P in Reques and Response . . . . . . . . . . . . . . . 100
Lis o abb e ia ions 102
No a ions and Symbols 104
Lis o igu es 108
Lis o ables 111
Con en s
iii
Re e ences 112
Lis o own publica ions 119
“In he age o au oma ion he abili y o na iga e pe sons and de ices in indoo en i onmen s
has become inc easingly impo an o a ising numbe o applica ions.”
Raine Mau z [1]
“Despi e i s cu en limi a ions, indoo na iga ion’s huge po en ial economic and sociologi-
cal capabili ies a e pushing o wa d he esea ch, de elopmen , implemen a ion, and sale o
low-cos sys ems. In he nea u u e, his will change he way we in e ac wi h ou su oun-
dings, wi h many ad an ages o he a ious s akeholde s in ol ed in any indoo business.”
And ea Bo ino, Gio anni Malna i and Paolo Mon uschi [2]
1. In oduc ion
Posi ioning and na iga ion ha e played impo an oles in many aspec s o human ci iliza-
ion o housands o yea s. Demand o his se ice is inc easing s eadily in many aspec s
called loca ion-based se ices (LBS) o loca ion-awa e sys ems [3, 4] such as anspo a i-
on, secu i y, social ne wo king, ma ke ing, and so on. While posi ioning o localiza ion is
he p ocess o de e mine he coo dina es o he a ge objec s, na iga ion is he p ocess o
es ima e he ou e om one loca ion o ano he .
A he beginning, posi ioning and na iga ion echniques we e in es iga ed o ou doo en-
i onmen o suppo he anspo a ion. Ou doo posi ioning and na iga ion we e done by a
combina ion o celes ial measu emen s and land ma ks, which helped people o con ol he
essel o e a e y la ge dis ance. Wi h he de elopmen o echnology, sa elli e was in en-
ed and subsequen ly, sa elli e based na iga ion sys ems such as Global Posi ioning Sys em
(GPS) by Uni ed S a es and Global Na iga ion Sa elli e Sys em (GLONASS) by Russia we e
de eloped. A he momen , he e a e wo o he sys ems being de eloped namely Galileo by
Eu opean Union and he BeiDou Na iga ion Sa elli e Sys em by China. Among hem, GPS
[5, 6] is he mos popula and success ul na iga ion sys em. GPS was i s de eloped o
mili a y pu pose by he U.S. A my and i was made a ailable o ci ilian use in he 1990s.
Wi h GPS, posi ion es ima e in h ee dimen ions is ob ained by applying a ci cula la e a ion
echnique, which elies on ange measu emen s. Nowadays, GPS is used o suppo he ans-
po a ion o mos o he ehicles such as ai planes, ca s and ships. Mo eo e , GPS can now
be used on mos sma de ices (sma phones and able compu e s) o suppo he daily ac-
i i ies wi h lowe posi ioning accu acy han he adi ional GPS de ices since lowe -quali y
GPS chipse s a e used on po able de ices due o p ice limi a ion. In he ideal case o line-o -
sigh condi ion, i.e., no o almos no obs acles be ween he de ice and he sa elli es, GPS can
loca e a ecei e wi h an accu acy o a ew me e s. Howe e , in an u ban a ea, he accu acy
deg ades d ama ically due o non-line-o -sigh p oblems.
Beside he success ul GPS, in o ma ion om some o he sou ces, e.g., Global Sys em o
Mobile Communica ions (GSM), a e also used o he ou doo posi ioning and na iga ion
pu poses. GSM based posi ioning was de eloped o sa is y he Enhanced 911 (E-911) man-
da e om he US Fede al Communica ions Commission which equi es cellula p o ide s
o ack he loca ion o hei subsc ibe s o wi hin 50 m o o e 67% o he ime. The GSM
posi ioning sys em may ei he solely employ he GSM in o ma ion [7, 8, 9] o combine i
wi h o he sou ces o in o ma ion, e.g., GPS, ine ial senso s and WiFi, esul ing in hyb id
sys ems [10, 11] in o de o p oduce a mo e accu a e posi ion es ima ion.
In an indoo en i onmen , GPS signals a e no mally blocked o un eliable due o he a -
enua ion o signal h ough oo s o walls. As a esul , he posi ioning accu acy is poo .
The e o e, de eloping a eliable indoo posi ioning and na iga ion sys em is o a pa icula
in e es . This opic has been a ac ed he conside a ion o many esea che s o e he las de-
1
Fundamen als o Indoo Posi ioning and S a e o Resea ch
8
whe e
x=x
y(2.4)
A=


x2−x1y2−y1
.
.
..
.
.
xN−x1yN−y1


(2.5)
b=1
2


(x2
2+y2
2)−(x2
1+y2
1)−( 2
2− 2
1)
.
.
.
(x2
N+y2
N)−(x2
1+y2
1)−( 2
N− 2
1)


(2.6)
The LS solu ion o he abo e sys em o equa ions can be ob ained as ollows:
x= (ATA)−1ATb.(2.7)
BS1
BS2
BS3
M
1
2
3
Figu e 2.2.: Cicula la e a ion based posi ioning: he es ima ed posi ion o he mobile use Mis de-
e mined based on he es ima ed dis ances be ween he mobile use and he e e ence
poin s. A leas h ee e e ence poin s a e needed o calcula e he use posi ion.
•Hype bolic la e a ion:
These me hods use ange di e ences be ween he mobile objec and any pai o e e-
ence poin s o o m a sys em o equa ions o hype bolas (Eq. (2.8)) which a e hen
used o compu e he posi ion o he ecei e :
dij = i− j
=p(x−xi)2+ (y−yi)2−q(x−xj)2+ (y−yj)2,(2.8)
he e, dij deno es he ange di e ence be ween i- h and j- h e e ence poin s, ∀i, j;i6=
j.
The solu ion can be easily ob ained by applying he LS me hod in a simila ashion as
discussed in he ci cula la e a ion based me hod. The abo e sys em o equa ions can

Fundamen als o Indoo Posi ioning and S a e o Resea ch
9
be sol ed as ollows [3]:
Since
di1= i− 1,(2.9)
we ha e
( 1+di1)2= 2
i
⇔ 2
i− 2
1=d2
i1+ 2 1di1(2.10)
hen
(x−xi)2+ (y−yi)2−(x−x1)2−(y−y1)2= 2
i− 2
1
=d2
i1+ 2 1di1
⇔x2
i+y2
i−(x2
1+y2
1)−2x(xi−x1)−2y(yi−y1) = d2
i1+ 2 1di1
x(xi−x1) + y(yi−y1) + di1 1=1
2(x2
i+y2
i)−(x2
1+y2
1)−d2
i1;
(2.11)
whe e i= 1,···, N.
The abo e sys em o equa ions in Eq. 2.11 can be w i en in ma ix o m:
Ax =b,(2.12)
whe e
x=

x
y
1
(2.13)
A=




x2−x1y2−y1d21
.
.
..
.
.
.
.
.
xN−x1yN−y1dN1




(2.14)
b=1
2


(x2
2+y2
2)−(x2
1+y2
1)−d2
21
.
.
.
(x2
N+y2
N)−(x2
1+y2
1)−d2
N1


(2.15)
The LS solu ion o he abo e sys em o equa ions is hen ob ained as:
x= (ATA)−1ATb.(2.16)
Many indoo localiza ion me hods employing la e a ion echniques ha e been p oposed,
see he desc ip ions in [46, 47, 48] and he e e ences he ein. The posi ioning accu acy
depends on how accu a e he es ima e o he dis ance be ween ansmi e and ecei e is.
La e a ion based echniques can be di ided in o 2ca ego ies: ime based la e a ion and signal
s eng h based la e a ion.
Fundamen als o Indoo Posi ioning and S a e o Resea ch
10
Time based la e a ion echniques employ he TOA o TDOA in o ma ion o compu e he
dis ances. In [49], a ime based la e a ion posi ioning sys em has been de eloped. The objec
o be loca ed is he mobile ag ansmi ing ul asonic pulses in a oughly hemisphe ical
pa e n a ound he op o i , once eques ed om a mas e s a ion ia a adio signal. A cen al
posi ioning uni polls he ne wo k o he ul asonic ecei e s moun ed on he ceiling o he
oom o e ie e he ime o ligh (TOF) o he ul asound emi ed by he mobile ag (i
de ec ed a he ecei e ). The TOF in o ma ion is measu ed as he ime di e ence be ween
he momen he mas e sends ou he eques o mobile ags o emi ing ul asonic pulse and
he i s signal peak de ec ed on he ecei e . Fo ime synch oniza ion, he mas e s a ion
sends he ese signal o all ecei e s simul aneously wi h he ul asound emi ing eques .
Dis ances be ween mobile ag and ecei e s a e hen compu ed and he posi ion o he mobile
ag is de e mined by applying he LS app oach. The epo ed expe imen al esul s a e e y
imp essi e wi h a posi ioning e o in he o de o cen ime e s.
In addi ion o ime based la e a ion, signal s eng h based la e a ion echniques a e also
employed in indoo posi ioning. These echniques employ he dependence o signal s eng h
on p opaga ion dis ance. The e o e, he accu acy o hese echniques mos ly depends on how
accu a e he es ima ed pa h loss model is.
In [18], a modi ied pa h loss model o indoo en i onmen was de eloped, whe e he
a enua ion o signal pene a ing h ough walls is conside ed. The pa ame e s o he pa h
loss model a e ained empi ically. Once he dis ances be ween ansmi e s and ecei e
a e ob ained, he inal es ima e o ecei e loca ion is ob ained by a ious me hods, e.g., by
sol ing he sys em o ci cula o hypecbolic equa ions using he LS app oach as summa ized
in [46].
In [47], me hods o imp o ing posi ioning esul s using RSSI based la e a ion echniques
we e explo ed. Ins ead o using he heo e ical pa h loss model, he au ho s p oposed wo
app oaches, eg ession based and co ela ion based. In he eg ession based me hod, polyno-
mial eg ession was used o model he ela ionship be ween he RSSI and dis ance, and he
coe icien s o he polynomial a e es ima ed by employing LS app oxima ion. The co ela-
ion based me hod u ilizes he ac ha he signal p opaga ion om close-by loca ions o an
AP is highly co ela ed as hey ace he simila p opaga ion en i onmen . This me hod ecu -
si ely pe o ms localiza ion in g adually educed local a eas o app oach he ue loca ion.
In each i e a ion, a ce ain numbe o RSSI eadings which a e he closes aining poin s o
he p e ious es ima ed posi ion a e kep and used o i he p opaga ion model. Expe imen al
esul s on bo h a i icial da a and eal da a showed he conside able imp o emen s compa ed
o he o iginal RSSI based la e a ion me hods.
An o e iew o la e a ion based echniques o Ul a-Wideband signals is gi en in [48]
whe e posi ioning schemes o ime based la e a ion and RSSI based la e a ion a e discussed.
In gene al, ime based la e a ion posi ioning echniques a e mo e p ecise han RSSI based
la e a ion echniques, howe e , hey equi e addi ional ha dwa e.
2.3. Angula ion
Angula ion based posi ioning echniques employ he angle o a i al o a wi eless signal o
de e mine he posi ion o a mobile objec . Theo e ically, hese echniques a e able o compu e
he posi ion o he ecei e when he e a e a leas wo e e ence poin s, and i he posi ion
Fundamen als o Indoo Posi ioning and S a e o Resea ch
11
o he mobile objec does no lie on he line connec ing he e e ence poin s.
BS1BS2
M
α1α2
Figu e 2.3.: Angula ion based posi ioning: he es ima ed posi ion o he mobile use Mis de e mined
based on he es ima ed angle αibe ween he mobile use and he e e ence poin s. A
leas wo e e ence poin s a e needed o calcula e he use posi ion wi h he condi ion
ha he use posi ion does no lie on he line connec ing he e e ence poin s.
Fig. 2.3 illus a es he angula ion based posi ioning echniques. In his sys em, he connec-
ed line be ween wo e e ences can be conside ed as an in e nal e e ence. The angle be -
ween he ansmi e and he ecei e αican be de e mined by:
an αi=y−yi
x−xi
⇔xsin αi−ycos αi=xisin αi−yicos αi;i= 1,···, N. (2.17)
Howe e , hese echniques also su e om he e o s caused by he NLOS p oblem. I
he e a e mo e han wo e e ence poin s, he sys em o equa ions migh no p oduce a unique
solu ion. To sol e he sys em o equa ions, an app oxima e solu ion is needed. Again, he LS
me hod is he mos common solu ion o sol ing he sys em o equa ions which is de ined
by Eq. (2.17).
Eq. (2.17) can be w i en in ma ix o m as ollows
Ax =b,(2.18)
whe e
x=x
y(2.19)
A=

−sin α1cos α1
.
.
..
.
.
−sin αNcos αN


(2.20)
b=


y1cos α1−x1sin α1
.
.
.
yNcos αN−xNsin αN


(2.21)
Fundamen als o Indoo Posi ioning and S a e o Resea ch
12
The LS solu ion o he abo e sys em o equa ions can be ob ained as ollows:
x= (ATA)−1ATb.(2.22)
An indoo sa elli e posi ioning sys em has been p oposed in [38], howe e , di e en om
he sa elli e based GPS. This sys em employs he in a ed signals ins ead o ele omagne ic
wa e and angula ion echnique ins ead o la e a ion echnique. The sys em consis s o 3
in a ed ligh sou ces, called indoo sa elli es, moun ed a ixed posi ions as emi e s, and he
in a ed inciden angle senso s a he mobile objec s measu ing he inciden angle om each
emi e . The posi ion o he mobile objec s a e hen ob ained by applying he LS app oach.
In [50], angula ion based echniques ha e been employed o es ima e he cu en posi ion
o an objec . ML, LS, To al Leas Squa es (TLS) and Weigh ed LS (WLS) algo i hms we e
applied o sol e he sys em o equa ions. To imp o e he pe o mance o he posi ioning
sys em, a me hod based on Weigh ed TLS (WTLS) was de i ed. The op imis ic esul s wi h
WTLS based app oach we e p esen ed wi h simula ion da a which app oach he C ame -Rao
Lowe Bound (CRLB).
Ano he example o an AOA based localiza ion sys em can be ound in [51]. The sys em
consis s o a se o passi e he mal in a ed senso s ins alled in he oom edges o de ec
he he mal adia ion o he human skin. The he mal senso s a e he mopile-a ays, whe e
each con ains a numbe o pixels and each pixel has a ield o iew. The hea sou ce posi ion
is de e mined ia he p inciple o AOA by compu ing he in e sec ion poin c ea ed by he
di ec ions o he pixels wi h he highes ou pu s.
2.4. Finge p in ing
Finge p in ing based posi ioning echniques a e he me hods o es ima e he posi ion o an
objec which ely on aining da a om a se o e e ence poin s (ancho poin s) wi h known
loca ions. Fig. 2.4 illus a es such a inge p in ing based sys em.
BS1
BS2
BS3BS4
M
Re e ence Poin
Figu e 2.4.: Finge p in ing based posi ioning: he illed ci cles indica es he e e ence (ancho )
poin s, while he iangles show base s a ion loca ions. The use posi ion is he posi i-
on o he ancho poin whose aining da a bes ma ch he online measu emen
Finge p in ing based me hods can be well o mula ed as a machine lea ning and pa e n
ecogni ion app oach. These echniques gene ally consis o wo phases: aining phase and
classi ica ion phase (also e e ed as o line phase and online phase). In he aining phase,
Fundamen als o Indoo Posi ioning and S a e o Resea ch
13
he aining da a, i.e., RSSI, a e collec ed a he ancho poin s and used o build he da abase
which is o en called adio map which desc ibes he RSSI-posi ion ela ionship. The adio
map can be de ined as ollows
R={(ℓk,Fk)|k= 1,···, K}(2.23)
whe e ℓkis he k- h e e ence posi ion, Kis he numbe o e e ence posi ions in he deploy-
men a ea, Fkcan be ei he he se o aw measu emen s, i.e., Fk=Xk=xk,1,···,xk,N ,
whe e xk,n = [xk,n,1,···xk,n,NAP ]Tis he n- h measu emen ec o which con ains he RS-
SIs om NAP base s a ions, o i con ains he class condi ional p obabili y densi y unc ions
(PDFs), i.e., Fk=p(x|ℓk), es ima ed om he measu emen s a he k- h posi ion.
Du ing he classi ica ion phase, he online measu emen s a e compa ed agains he aining
da a a e e y ancho poin . The posi ion o he ancho poin whose aining da a bes ma ch
he online da a can be conside ed as he es ima ed posi ion o he ecei e . As discussed in
chap e 1, he e a e wo mos common app oaches o calcula ing he simila i y be ween
aining da a and online da a: de e minis ic app oaches, e.g., he k-nea es neighbo ule, and
p obabili ic app oaches, e.g., he Bayesian classi ica ion ule.
Though adio inge p in ing based posi ioning echniques can be applied o bo h indoo
and ou doo en i onmen s, i seems ha hese echniques a e mo e sui able o indoo since
he dis inc ion o adio signal s eng hs obse ed a di e en posi ions indoo is much highe
han ou doo due o he densi y o obs uc ions in indoo en i onmen s.
In he e y well-known inge p in ing based posi ioning sys em Rada [18, 21], he k-
nea es neighbo me hod is employed. The posi ion o he ecei e is compu ed by a e aging
he coo dina es o he kancho poin s which ha e highes simila i y be ween he aining da a
and he online obse a ion. The simila i y is measu ed by compu ing he Euclidian dis ance
be ween he aining da a and online obse a ion in signal s eng h space as ollows
D(o,xk,n) =
u
u
NAP
X
i=1
(oi−xk,n,i)2,∀k, ∀n(2.24)
whe e o= [o1,···, oNAP ]Tand Ddeno e he online obse a ion and he dis ance, espec-
i ely. The j- h posi ion is conside ed o be he nea es neighbo , i.e., he aining da a ha
bes ma ch he online obse a ion, i he e is a aining measu emen xj,m which sa is ies
D(o,xj,m)≤ D(o,xk,n),∀k6=j, ∀n(2.25)
In [22], an ex ensi e analysis o he inge p in ing based posi ioning sys em ha employs
he Euclidian dis ance is p esen ed. The e ec o he numbe o access poin s, he numbe
o aining samples pe posi ion, he densi y o he ancho poin s, e c. on he pe o mance
o he posi ioning sys em a e analyzed. The analysis esul s p o ide a guideline on choosing
pa ame e s o design and deploy an indoo posi ioning sys em.
In p obabili ic app oaches, in he aining phase he s a is ical pa ame e s o he PDF o
he signal s eng h a e ained. Du ing he classi ica ion phase, he simila i y be ween ai-
ning da a and online da a is compu ed by calcula ing he likelihood o obse ing he online
da a gi en he PDF o signal s eng h a ancho poin s [24, 25, 8], o some o he c i e ia
o measu e he simila i y such as he Bha acha yya dis ance [52], hen again a k-nea es
neighbo algo i hm can be applied o compu e he inal es ima ed posi ion o he ecei e .

Fundamen als o Indoo Posi ioning and S a e o Resea ch
14
The e a e wo me hods o es ima e he PDF o he aining da a, pa ame ic and non-
pa ame ic densi y es ima ion echniques [3]. Pa ame ic es ima ion me hods assume a mo-
del, e.g., a Gaussian, o he densi y unc ion and aim o es ima e he pa ame e s o he model
[25, 8], i.e., Fk=θk= (µk,Σk). On he o he hand, non-pa ame ic me hods do no assu-
me any p io model bu es ima e he class condi ional PDF by using he his og am me hod
[24, 52] o Ke nel densi y es ima o s [23, 53].
A e cons uc ing he class condi ional PDF, he inal posi ion es ima e can be ob ained by
compu ing he likelihood o he pos e io using he Bayes’ ule. The posi ion which achie es
he highes likelihood o pos e io is hen conside ed as he posi ion o he mobile ecei e .
Maximum likelihood es ima o aims o ind he posi ion ha maximizes he p obabili y o
obse ing he online measu emen o, gi en he class condi ional PDFs a e e ence poin s,
as ollows
ˆ
ℓ= a gmax
ℓk
p(o|ℓk).(2.26)
A maximum a pos e io i es ima o inds he posi ion which has he highes pos e io p oba-
bili y as
ˆ
ℓ= a gmax
ℓk
P(ℓk|o).(2.27)
Applying Bayes’ ule, P(ℓk|o)can be ob ained as ollows
P(ℓk|o) = p(o|ℓk)P(ℓk)
p(o)
=p(o|ℓk)P(ℓk)
PK
k′=1 p(o|ℓk′)P(ℓk′),(2.28)
assuming ha he p io P(ℓk)is gi en.
In [25], wo di e en ypes o class condi ional PDF a e conside ed, one is he pa ame ic
model (Gaussian) and he o he is he non-pa ame ic model. In he epo ed esul s, he
me hod employing he pa ame ic model ou pe o ms he o he . This is because, as s a ed, he
pa ame ic echnique smoo hs he dis ibu ion shape o accoun o missing signal s eng h
alues in he aining phase, (due o he ini e numbe o aining samples) which a oids
ob aining a ze o p obabili y o any signal s eng h alue ha was no obse ed in he aining
phase.
2.5. Dead Reckoning
Dead eckoning (DR) echniques employ he in o ma ion om a sys em o ine ial senso s,
i.e., accele a ion and gy oscope senso s, in o de o es ima e he posi ion o an objec based
on he p e ious es ima ed posi ion. DR echniques had been i s de eloped o he a ia ion
and ma ine indus y, nowadays hey a e also used in obo ics [54, 55, 56], indoo posi ioning
[57, 58, 59, 32], and many mo e sys ems.
Fig. 2.5 illus a es he posi ioning p ocedu e o DR echniques whe e he cu en posi i-
on is es ima ed based on he p e ious es ima e. is he mo emen ec o compu ed om
displacemen in o ma ion and mo emen heading es ima ion.
Fundamen als o Indoo Posi ioning and S a e o Resea ch
15
Wi h he de elopmen o Mic oelec omechanical sys ems (MEMS) echnology, o dina-
y sma phones now o en ha e a buil -in ine ial measu emen uni (IMU) which allows
o employ he dead eckoning echniques o indoo pedes ian acking wi hou addi ional
ha dwa e. Howe e , hey ha e lowe accu acy in compa ison wi h he IMU sys em used on
ai planes o in space science.
As discussed in chap e 1, hese echniques a e o en de eloped in a combina ion wi h
o he me hods using o he sou ces o in o ma ion, such as WiFi signal o GPS, which a e
used o egula ly ese he e o o DR echniques which accumula es o e ime and dis an-
ce. Displacemen es ima ion o he indoo use in DR based indoo posi ioning is done ia
s ep de ec ion and s ep leng h es ima ion whe e he obse ed accele a ion da a a e used. Va-
ious me hods ha e been p oposed o s ep de ec ion p ocedu e such as peak de ec ion [57],
ze o-c ossing de ec ion as men ioned in [59] o au oco ela ion app oach [32]. S ep leng h
es ima ion based on accele a ion da a is a icky ask since he accu acy o buil -in senso s
on sma phones a e o en e y low. As a esul , mos o he s ep leng h es ima ion me hods
a e based on a calib a ion phase o es ima e some heu is ic ac o s, as summa ized in [60]. A
Kalman il e is o en used o mo emen heading es ima ion which u ilizes he in o ma ion
om gy oscope and magne ic senso s [59].
1
2 3
Figu e 2.5.: Dead eckoning: he use posi ion is es ima ed based on he es ima ed mo emen ec o s
assuming ha he s a ing poin is gi en.
2.6. Compa ison o Techniques
All he abo e men ioned adio signal based echniques o posi ioning ha e hei own ad an-
ages and disad an ages and hei sui abili y depends on he deploymen en i onmen .
•P oximi y based echniques can be applied o any low cos posi ioning sys em o ei -
he ou doo o indoo (no equi emen o addi ional ha dwa e) which does no equi e
a high posi ioning accu acy. The posi ioning e o depends on he co e age ange o
he base s a ions, e.g., he p oximi y posi ioning sys ems using GSM base s a ions ha e
e o in he o de o hund eds o me e s. An indoo posi ioning sys em may use hese
echniques employing he wi eless local a ea ne wo k (WLAN) sys em. Howe e he
posi ioning e o is abou he co e age ange o an AP, i.e., oughly 100 m which is
unaccep able in he indoo en i onmen . Mo eo e , in indoo en i onmen s, he con-
ou o signal s eng h adia ed om an AP is ob iously no symme ic due o he
p esence o obs uc ions. This leads o misclassi ica ion esul s, because he ecei e
may ecei e a highe RSSI om a a he AP because o line o sigh o his AP while
i obse es a lowe RSSI om a close AP due o absence o line o sigh . Posi ioning
using iBeacon ad e ising packe s is ano he app oach which aims o p oduce a oom
p ecise localiza ion sys em. Howe e , he highe he accu acy equi emen s, he mo e
ha dwa e (iBeacon ansmi e s) needs o be ins alled.
Fundamen als o Indoo Posi ioning and S a e o Resea ch
16
•La e a ion and angula ion based echniques a e able p oduce highly p ecise posi io-
ning esul s in ee space en i onmen whe e signals can p opaga e by he di ec pa h
om he ansmi e o he ecei e and almos no mul ipa h p oblem occu s. Un o u-
na ely, he indoo en i onmen is de ini ely no ee space. I has a lo o obs uc ions
such as walls, u ni u e o mo emen o people ha makes he accu acy o he posi-
ioning using hese echniques e y limi ed. Because o he special equi emen s o
he en i onmen , hese echniques may only be sui able o posi ioning in a single
oom. Ano he limi a ion o hese echniques is he equi emen o addi ional speciali-
zed ha dwa e, i.e., an enna, mic ophone a ays, e c., and deep ha dwa e access which
seems o be no possible o a posi ioning sys em employing he exis ing WLAN in-
as uc u e and o dina y mobile de ices, i.e., sma phones. Clock synch oniza ion is
ano he challenge o la e a ion based echniques which de e mines he accu acy o
posi ioning esul s.
•Finge p in ing based me hods as discussed abo e consis o wo phases, aining phase
and classi ica ion phase. The i s and he o emos disad an age o hese echniques
is he necessi y o a aining phase which is e y ime consuming and need o be done
e y ca e ully because he classi ica ion esul s a e s ongly in luenced by he quali y
o he aining da a. Ano he disad an age o hese echniques is ha he aining da a
need o be upda ed egula ly in o de o adap o he changes o he in as uc u e and
en i onmen in o de o main ain he accu acy o he posi ioning esul s. Despi e hese
disad an ages, inge p in ing based echniques a e s ill he mos p omising me hods
o indoo en i onmen s o h ee main easons: Fi s , hey can p oduce a easonable
posi ioning esul wi hou any addi ional special ha dwa e. Second, hese echniques
a e sui able o be employed in an al eady ins alled WLAN sys em, and WLAN is
a ailable in many places. Thi d, sys ems using hese echniques can be applied in a
la ge a ea and ha e a good scalabili y.
•Dead eckoning echniques a e able o p oduce p ecise posi ioning esul s gi en he
ini ial posi ion wi hou any knowledge o he in as uc u e in he co e age a ea, ho-
we e , only o e a sho ime and mo emen dis ance. The high accu acy is no kep
long because o he accumula ion o e o o e ime and dis ance o mo emen . The
e o s a e caused, o example, by he d i o bias o senso sys ems, and also he noise
in he en i onmen s, o example he measu emen om a magne ic senso is s ongly
a ec ed by me allic ma e ials a ound he senso and no only he magne ic ield o he
ea h.
F om he analysis o he he ad an ages and disad an ages o he men ioned adio signal
based echniques, o de eloping a eal indoo posi ioning sys em based on he egula sma -
phones and he al eady ins alled WLAN sys em, he combina ion o inge p in ing based and
dead eckoning echniques appea s o be he bes solu ion because o he ollowing easons:
•Su icien accu acy: The posi ioning accu acy mee s he equi emen o indoo posi-
ioning o he common pu poses such as use acking and secu i y, in la ge indoo
a eas, i.e., uni e si ies, museums, hospi als o s o es.
•Cos e iciency: no addi ional ha dwa e is needed o build up a posi ioning sys em.
Fundamen als o Indoo Posi ioning and S a e o Resea ch
17
•Deploymen simplici y: WLAN is oday a ailable in almos e e y indoo en i on-
men . Consequen ly, he posi ioning sys em can be deployed in many indoo a eas
easily.
•Robus ness: The combina ion o WiFi inge p in ing based and DR echniques ma-
kes he sys em obus , i.e., he mobile de ices can do sel localiza ion based on DR
echniques when no WiFi signal is a ailable.
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
24
used wi h he same meaning. The goal is o es ima e he pa ame e s θ={µ, σ2}o he
unde lying Gaussian.
E-S ep
Employing he EM algo i hm we iden i y yand x o be he comple e and he obse ed da a,
espec i ely. Thus he expec ed log-likelihood o he comple e da a is gi en by
Q(θ;θ(κ)) = Eln (pY(y;θ)) |x;θ(κ)(4.4)
=
N
X
n=1 Z∞
−∞
ln (pY(yn;θ)) pyn|xn;θ(κ)dyn(4.5)
=:
N
X
n=1
nθ;θ(κ),(4.6)
whe e nθ;θ(κ)=R∞
−∞ ln (pY(yn;θ)) pyn|xn;θ(κ)dynand whe e κis he i e a ion in-
dex.
The e m p(yn|xn;θ(κ))can be de e mined as ollows:
p(yn|xn;θ(κ)) = (δ(yn−xn), i xn> c
p(xn|yn;θ(κ))p(yn;θ(κ))
p(xn;θ(κ)), i xn=c(4.7)
Fo he case xn=cwe know ha yn≤c.p(yn|xn;θ(κ))can hus be calcula ed as ollows
p(yn|xn;θ(κ)) = p(xn|yn;θ(κ))p(yn;θ(κ))
p(xn;θ(κ))
=p(xn|yn;θ(κ))p(yn;θ(κ))
Rc
−∞ p(xn|yn;θ(κ))p(yn;θ(κ))dyn
=δ(xn−c)p(yn;θ(κ))
Rc
−∞ δ(xn−c)p(yn;θ(κ))dyn
=Nyn;θ(κ)
I0(θ(κ))
He e we ha e used he no a ion
Ij(θ(κ)) = Zc
−∞
yjNy;θ(κ)dy(4.8)
wi h j= 0.I0(θ(κ))can be calula ed as ollows (see Appendix A.1.1 o he de ailed com-
pu a ion):
I0(θ(κ)) = 1
2e c −c−µ(κ)
√2σ(κ).(4.9)
Then we ob ain
p(yn|xn;θ(κ)) = (δ(yn−xn), i xn> c
N(yn;θ(κ))
I0(θ(κ)), i xn=c.(4.10)

Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
25
In oducing he bina y andom a iable Znwi h ealiza ion zn, whe e zn= 0 and zn= 1
indica e ha he n- h measu emen is no censo ed o censo ed, espec i ely, he summand
in Eq. (4.6) can be w i en as
nθ;θ(κ)=zn
I0(θ(κ))Zc
−∞
ln (N(yn;θ)) Nyn;θ(κ)dyn
+ (1 −zn) ln (N(xn;θ)) .(4.11)
he e, he ac ha yn=xnwhen zn= 0 is exploi ed.
M-S ep
The pa ame e e-es ima ion o mulas a e ob ained by compu ing he de i a i es o Eq. (4.11)
w. . . he elemen s o θand se hem o ze o:
∂
∂µ n(θ;θκ) = zn
I0(θ(κ))Zc
−∞
yn−µ
σ2Nyn;θ(κ)dyn
+ (1 −zn)xn−µ
σ2
=zn
σ2
I1θ(κ)−µI0θ(κ)
I0(θ(κ))+ (xn−µ)1−zn
σ2(4.12)
∂
∂σ n(θ;θκ) = zn
I0(θ(κ))Zc
−∞ −1
σ+(yn−µ)2
σ3Nyn;θ(κ)dyn
+ (1 −zn)−1
σ+(xn−µ)2
σ3
=zn
σ1
σ2I2(θ(κ))
I0(θ(κ))−2µI1(θ(κ))
I0(θ(κ))+µ2−1
+1−zn
σ(xn−µ)2
σ2−1,(4.13)
He e, we ha e used he no a ion as de ined in Eq. (4.8). Se ing he suma ions o he abo e
de i a i es o ze os, e-es ima ion o mulas a e eadily ob ained:
N
X
n=1
∂
∂µ n(θ;θκ)µ=µκ+1
= 0 :
µ(κ+1) =1
N
I1(θ(κ))
I0(θ(κ))
N
X
i=1
zn+1
N
N
X
i=1
(1 −zn)xn(4.14)
N
X
n=1
∂
∂σ n(θ;θκ)σ2=(σ2)κ+1
= 0 :
σ2(κ+1) =I2(θ(κ))
I0(θ(κ))−2µ(κ)I1(θ(κ))
I0(θ(κ))+µ2(κ)1
N
N
X
i=1
zn
+1
N
N
X
i=1
(1 −zn)xn−µ(κ)2.(4.15)
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
26
The compu a ion o I1(θ(κ))and I2(θ(κ))a e gi en in Appendix A.1.2 and Appendix A.1.3,
espec i ely.
As can be seen in Eq. (4.14) and Eq. (4.15), he unobse able da a, i.e., censo ed da a,
also con ibu e o he es ima es beside he obse able ones. In ui i ely, in case o absence o
censo ed da a, i.e., zn= 0 o all measu emen s, he e-es ima ion o mulas educe o he
ypical ML es ima ion o mulas o mean µand a iance σ2.
To ha e a be e in ui ion o he e-es ima ion o mulas, he si ua ion a e con e gence o
he es ima es is conside ed. Le µ(κ+1) ≈µ(κ)=: ˆµand (σ2)(κ+1) ≈(σ2)(κ)=: ˆσ2, using
his in Eq. (4.14) and Eq. (4.15) and sol ing o he es ima es, we a i e a
ˆµ=M
N
1
M
M
X
i=1
xn+1−M
NRc
−∞ ypY(y;ˆ
θ)dy
Rc
−∞ pY(y;ˆ
θ)dy,(4.16)
ˆσ2=M
N
1
M
M
X
i=1
(xn−ˆµ)2+1−M
NRc
−∞(y−ˆµ)2pY(y;ˆ
θ)dy
Rc
−∞ pY(y;ˆ
θ)dy,(4.17)
whe e we assumed wi hou loss o gene ali y ha he i s M=Pi(1 −zn)obse a ions
a e he uncenso ed ones. These exp essions lend hemsel es o he ollowing in e p e a ion:
Mean and a iance es ima es a e he weigh ed a e age be ween hei ML es ima es which a e
compu ed om he obse ed da a and he mean and a iance o he assumed unca ed Gaus-
sian o he unobse able pa s. The weigh s a e he ela i e equencies o he uncenso ed
and censo ed measu emen s, espec i ely.
P ope ies o he Es ima es
In he ollowing, he main p ope ies o he p oposed es ima o a e in es iga ed. As will be
shown, he p oposed EM algo i hm deli e s i ually bias ee and e icien es ima es.
Unbiasness and Con e gence
In o de o s udy he con e gence p ope ies he expec ed alues o he di e ence be ween
he es ima es, Eqs. (4.14) and (4.15), and he ue alues o he pa ame e s a e compu ed.
Fi s no e ha Znis a Be noulli andom a iable wi h
P(Zn= 1) = Zc
−∞
pY(y;θ)dy=I0(θ)
and P(Zn= 0) = 1 −I0(θ). Thus: E [Zn] = E[Z2
n] = I0(θ).
Taking he expec a ion o mean es ima e Eq. (4.14) we ha e
Eµ(κ+1)=1
N
N
X
i=1
E[(1 −Zn)Xn] + 1
N
N
X
i=1
EI1(θ(κ))
I0(θ(κ))Zn.(4.18)
I has o be no ed ha he es ima e θ(κ)depends on he da a and is hus andom. Thus he
expec a ion ope a o also applies o his quan i y. The i s expec a ion can be e alua ed as
ollows:
E[(1 −Zn)Xn] =
1
X
zn=0 Z∞
−∞
(1 −zn)xnP(zn|xn)pY(xn)dxn
=Z∞
c
xnN(xn;θ)dxn=µ−I1(θ).(4.19)
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
27
No e ha he e we ha e used he no a ion pY(xn)because x=yin case o no censo ed.
He e we ha e employed he ac ha
P(zn= 0|xn) = 1,i xn> c
0,else .(4.20)
Using u he E hI1(θ(κ))
I0(θ(κ))zni≈EhI1(θ(κ))
I0(θ(κ))iE[Zn]and sub ac ing µ om ei he side o
Eq. (4.18) we ob ain
E˜µ(κ+1)=−I1(θ) + I0(θ)EI1(θ(κ))
I0(θ(κ)).(4.21)
whe e ˜µ(κ+1) =µ(κ+1) −µ.
In o de o compu e he emaining expec a ion, a Taylo se ies expansion a ound he ue
pa ame e alues θ= (µ, σ2)is applied and unca ed a e he linea e m:
EI1(θ(κ))
I0(θ(κ))≈I1(θ)
I0(θ)+E˜µ(κ)∂
∂µ
I1(θ)
I0(θ)+Eh˜σ2(κ)i∂
∂σ2
I1(θ)
I0(θ).(4.22)
Expec a ion o a iance es ima e Eq. (4.15) can be calula ed in a simila p ocedu e as
ollows:
Eσ2(κ+1)=E"1
N
N
X
n=1
(1 −zn)(xn−µ)2#
+E"1
N
N
X
n=1
zn
I2(θ(κ))−2I1(θ(κ))µ+I0(θ(κ))µ2
I0(θ(κ))#
=1
N
N
X
n=1
E(1 −zn)(xn−µ)2
+1
N
N
X
n=1
Ezn
I2(θ(κ))−2I1(θ(κ))µ+I0(θ(κ))µ2
I0(θ(κ))(4.23)
The i s expec a ion can be e alua ed as ollows:
E(1 −zn)(xn−µ)2=
1
X
zn=0 Z∞
−∞
(1 −zn)(xn−µ)2P(zn|xn)pY(xn)dxn
=Z∞
c
(xn−µ)2N(xn;θ)dxn
=σ2−(I2(θ)−2µI1(θ) + µ2I0(θ)).(4.24)
Using u he E hzn
I2(θ(κ))−2I1(θ(κ))µ+I0(θ(κ))µ2
I0(θ(κ))i≈EhI2(θ(κ))−2I1(θ(κ))µ+I0(θ(κ))µ2
I0(θ(κ))iE[Zn]and
sub ac ing σ2 om ei he side o Eq. (4.23) we ob ain
Eh˜σ2(κ+1)i=−I2(θ)−2µI1(θ) + µ2I0(θ)
+I0(θ)EI2(θ(κ))−2I1(θ(κ))µ+I0(θ(κ))µ2
I0(θ(κ))(4.25)
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
28
whe e (˜σ2)(κ+1) = (σ2)(κ+1) −σ2.
In o de o compu e he emaining expec a ion, a Taylo se ies expansion a ound he ue
pa ame e alues θ= (µ, σ2)is again applied and unca ed a e he linea e m:
EI2(θ(κ))−2I1(θ(κ))µ+I0(θ(κ))µ2
I0(θ(κ))≈I2(θ)−2I1(θ)µ+I0(θ)µ2
I0(θ)
+E˜µ(κ)∂
∂µ
I2(θ)−2I1(θ)µ+I0(θ)µ2
I0(θ)
+Eh˜σ2(κ)i∂
∂σ2
I2(θ)−2I1(θ)µ+I0(θ)µ2
I0(θ).
(4.26)
W i ing Eq. (4.21) and Eq. (4.25) in ma ix o m, we a i e a
E˜µ(κ+1)
Eh(˜σ2)(κ+1)i!≈WµWµσ
Wσµ Wσ E˜µ(κ)
Eh(˜σ2)(κ)i!
=WµWµσ
Wσµ Wσκ+1 E˜µ(0)
Eh(˜σ2)(0)i!,(4.27)
whe e
Wµ=I0(θ)∂
∂µ
I1(µ)
I0(µ), Wµσ =I0(θ)∂
∂σ2
I1(θ)
I0(θ),
Wσ=I0(θ)∂
∂σ2
I2(θ)−2I1(θ)µ+I0(θ)µ2
I0(θ),
Wσµ =I0(θ)∂
∂µ
I2(θ)−2I1(θ)µ+I0(θ)µ2
I0(θ).
The Wen ies can be eadily compu ed by using he de i a i es gi en in Appendix A.1.4.
In es iga ing all he possible alues o he magni udes o he eigen alues o he ma ix
wi h he Wen ies by changing he clipping h eshold c om −∞ o ∞, we obse ed ha
hey a e always less han one (app oaching one o c→ ∞, i.e., no obse able da a). We
hus conclude ha he es ima es a e bias ee because he expec a ion o he e o dec eases
exponen ially o e i e a ions. Since, howe e , in p ac ice µhas o be eplaced by i s es ima e
in he es ima ion o he a iance, we exhibi he same bias as in o dina y ML es ima ion o
he a iance. In he applica ion conside ed he e, he bias o he ML es ima e o he a iance
can be neglec ed due o he la ge numbe o samples. Fu he , an es ima e o he con e gence
speed o he EM algo i hms can also be ob ained om Eq. (4.27), see Fig. 4.3. I can be seen
ha he numbe o i e a ions quickly ises once mo e han 50% o he da a a e clipped.
P ecision
In o de o e alua e he p ecision o ou p oposed es ima o , we calcula ed he C ame -Rao
Lowe Bound (CRLB) o he es ima o . CRLB o he es ima ion e o a iance o he mean
and a iance es ima es can be ob ained by in e ing he in o ma ion ma ix Iwhich con ains
he expec ed alues o he second-o de pa ial de i a i es o he log-likelihood unc ion.
F om he de i a ion o he EM algo i hm i can be seen ha he measu emen s consis o
wo ypes o da a, he numbe Mo noncenso ed obse a ions and he obse a ions hemsel-
es. While he o me ype is binomially dis ibu ed, he la e ype is d awn om a unca ed
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
29
c−µ
σ
No. o EM i e a ions
−2−1.5−1−0.500.51 1.52
0
100
200
300
Figu e 4.3.: Theo e ical numbe o EM i e a ions κ equi ed o educe he es ima ion e o o 10−4
o i s ini ial alue as a unc ion o (c−µ)/σ. Ini ial alues µ(0),σ2(0) ha e been se o
he ML es ima es o µ, σ2compu ed om he unclipped obse a ions only.
Gaussian. I is no ed ha he d aws om he Gaussian a e independen o he binomial an-
dom a iable. Following [65] he likelihood is hus gi en by, whe e I0(θ)is he p obabili y
o no obse ing a sample and 1
√2πσ2exp −1
2xj−µ
σ2!is he p obabili y o obse ing
xj>−100 dBm
p(x;θ) = N!
M!(N−M)!IN−M
0(θ)1
√2πσ2M
exp −1
2
M
X
j=1 xj−µ
σ2!,(4.28)
and he log-likelihood unc ion is ob ained as ollows:
ln p(x;θ) = ln N!
M!(N−M)!+ (N−M) ln (I0(θ))
−M
2ln 2πσ2−1
2
M
X
j=1 xj−µ
σ2
.(4.29)
The in o ma ion ma ix Iis de ined as:
I=
Eh−∂2
∂µ2ln p(x;θ)iEh−∂2
∂µ∂σ2ln p(x;θ)i
Eh−∂2
∂µ∂σ2ln p(x;θ)iEh−∂2
∂σ2∂σ2ln p(x;θ)i
.(4.30)
The en ies o ma ix Ican be calcula ed as ollows (see Appendix A.1.5 o he de ailed
compu a ion):
E−∂2
∂µ2ln p(x;θ)=N
σ2I2
1−I2I0
I0
+ 1(4.31)
E−∂2
∂µ∂σ2ln p(x;θ)=N
σ2 −
∂I1
∂σ2I0−I1∂I0
∂σ2
I0!(4.32)
E−∂2
∂σ2∂σ2ln p(x;θ)=N
σ2 1
2σ2−1
2σ2 ∂I2
∂σ2I0−I2∂I0
∂σ2
I0−2µ
∂I1
∂σ2I0−I1∂I0
∂σ2
I0!!
(4.33)
whe e he compu a ion o he de i a i e e ms a e gi en in Appendix A.1.4.

Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
30
CRB (σ2)
CRB (µ)
Simula ion (σ2)
Simula ion (µ)
log10(MSE)
c−µ
σ
−2−1.5−1−0.500.51 1.52
−2
−1
0
1
2
3
Figu e 4.4.: Compa ison o CRLB o mean and a iance wi h MSE ob ained om simula ion o
σ2= 25 and N= 1000.
Compu ing he I−1, we ob ain CRLB on es ima ion e o a iance o µand σ2:
Va (ˆµ)≥I−1(1,1) (4.34)
Va (ˆσ2)≥I−1(2,2) (4.35)
Fig. 4.4 compa es he CRLB wi h he mean squa ed e o (MSE) o he p oposed es ima-
o s o mean µand a iance σ2ob ained om a simula ion. I can be seen ha he es ima o
p ac ically achie es he bound. The di e ences a e so small ha hey a e no isible in he
g aph. We he e o e conclude ha he es ima o is e icien . Fu he mo e, o he limi ing ca-
se o comple ely uncenso ed da a he well-known esul s o ML pa ame e es ima ion om
a no mal popula ion a e ob ained: MSE(µ) = σ2/N; MSE(σ2) = σ4(2N−1)/N2.
4.2.3. EM algo i hm o Censo ed and D opped Gaussian Da a
In his subsec ion, he p oposed EM algo i hm o pa ame e es ima ion o censo ed Gaussian
da a is ex ended o be able o cope no only wi h he censo ed da a bu also he d opped da a.
No a ions
The measu emen model o censo ed and d opped da a is shown in Fig. 4.5. He e, he hidden
a iables dn,n= 1,...N, indica e whe he an obse a ion is d opped (dn= 1) o no
(dn= 0), whe e P(dn= 1) is he d opping a e, in he ollowing, P(dn= 1) is deno ed by
π. The a iables a e ga he ed in he bina y ec o d= [d1,...,dN], whe e Nis he numbe
o measu emen s. Fu he mo e, de ine y=y1, ..., yN, whe e he yna e i.i.d. wi h Gaussian
p obabili y densi y unc ion (PDF) pY(yn) = N(yn;µ, σ2)i dn= 0, and yn=ci dn= 1,
whe e we se c o he smalles measu able RSSI alue (e.g., c=−100 dBm). I should be
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
31
no ed ha yis no he comple e da a anymo e since he da a a e possibly d opped. Obse able
da a a e he censo ed, possibly d opped da a x=x1, ..., xN, whe e xn= max(yn, c), wi h
he censo ing h eshold cas abo e.
xn
yn
max(yn, c)
∼ N(µ, σ2)
c
dn
dn= 0
dn= 1
D opping Censo ing
Figu e 4.5.: Measu emen model.
The di e ence be ween censo ing and d opping can be exp essed as ollows: E en i he
pa ame e s o he Gaussian a e such ha p ac ically no censo ing occu s (because µ≫c),
d opping will s ill possibly occu .
The goal is o es ima e he pa ame e s θ={µ, σ2, π}. This will be achie ed by he Expec-
a ion Maximiza ion (EM) algo i hm, whe e he comple e da a a e {y,d}and he obse able
a e {x}.
E-S ep
I is no ed ha xndoes no con ey mo e in o ma ion abou θ han yn. So, he comple e da a
a e {y,d} a he han {x,y,d}. The expec ed log-likelihood o he comple e da a, gi en he
obse ed one, is gi en by:
Q(θ;θ(κ)) = Eln (p(y,d;θ)) |x;θ(κ)
=
N
X
n=1
1
X
dn=0 Z∞
−∞
ln (p(yn, dn;θ)) p(yn, dn|xn;θ(κ))dyn,(4.36)
whe e κis he i e a ion index.
p(yn, dn|xn)can be w i en as
p(yn, dn|xn;θ(κ)) = p(yn|dn, xn;θ(κ))P(dn|xn;θ(κ)).(4.37)
Fo calcula ing p(yn|dn, xn;θ(κ)), wo cases a e conside ed:
•Fo da a ha a e no d opped (dn= 0), see Eq. (4.10),
p(yn|dn= 0, xn;θ(κ)) = (δ(yn−xn),i xn> c
N(yn;θ(κ))
I0(θ(κ)),i xn=c(4.38)
•Fo da a ha a e d opped (dn= 1)
p(yn|dn= 1, xn;θ(κ)) = 0,i xn> c
δ(yn−c),i xn=c.(4.39)
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
32
Fu he mo e, he pos e io o he hidden a iable dncan be compu ed using Bayes’ ule
P(dn|xn;θ(κ)) = p(xn|dn;θ(κ))P(dn)
P1
dn=0 p(xn|dn;θ(κ))P(dn).(4.40)
Since he e a e wo a iables, ou cases can be disce ned. Using he no a ion
βn(d, z) := P(dn|zn;θ(κ)), whe e zn= 1 indica es ha xn=cand zn= 0 ha xn> c, we
ob ain:
βn(1,1) = P(dn= 1|xn=c;θ(κ))
=p(xn=c|dn= 1)P(dn= 1)
p(xn=c|dn= 0)P(dn= 0) + p(xn=c|dn= 1)P(dn= 1)
=π(κ)
I0(θ(κ))(1 −π(κ)) + π(κ),(4.41)
whe e he esul om he p e ious sec ion is employed: p(xn=c|dn= 0) = I0(θ(κ))is he
p obabili y ha a measu emen is censo ed, i.e., unobse able, gi en ha i is no d opped.
In addi ion, p(xn=c|dn= 1) is always equal o 1since i he measu emen is d opped, i is
assigned he alue o c.βn(1,1) is he p obabili y ha he measu emen is d opped gi en i
is unobse able.
The p obabili y ha he measu emen is no d opped gi en i is unobse able, βn(0,1), is
hen easily ob ained since βn(0,1) + βn(1,1) = 1.
Fu he mo e, i is ob ious ha i a measu emen is obse able, i canno be d opped, so
βn(1,0) = 0, and hus βn(0,0) = 1.
We u he no e ha
p(yn, dn;θ) = P(dn;θ)p(yn|dn;θ)
=πδ(yn−c),i dn= 1
(1 −π)N(yn;θ),i dn= 0 (4.42)
Using all he abo e in (4.36) we a i e a
Q(θ;θ(κ)) =
N
X
n=1 znZc
−∞
ln ((1 −π)N(yn;θ)) N(yn;θ(κ))
I0(θ(κ))βn(0,1)dyn
+ (1 −zn)Z∞
c
ln ((1 −π)N(yn;θ)) δ(yn−xn)βn(0,0)dyn
+znZc
−∞
ln (πδ(yn−c)) δ(yn−c)βn(1,1)dyn
=
N
X
n=1 znln(1 −π)βn(0,1)
+zn
I0(θ(κ))Zc
−∞
ln (N(yn;θ)) N(yn;θ(κ))dynβn(0,1)
+ (1 −zn) ln(1 −π) + (1 −zn) ln (N(xn;θ))
+znln(π)βn(1,1).(4.43)
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
33
M-S ep
Compu ing he de i a i e o he auxilia y unc ion Eq. (4.36) he ollowing i e a i e pa ame-
e es ima ion o mulas can be eadily de i ed:
µ(κ+1) =PN
n=1(1 −zn)xn+I1(θ(κ))
I0(θ(κ))PN
n=1 znβn(0,1)
N−PN
n=1 znβn(1,1) (4.44)
σ2(κ+1) =PN
n=1 znI2(θ(κ))
I0(θ(κ))−2µI1(θ(κ))
I0(θ(κ))+µ2βn(0,1)
N−PN
n=1 znβn(1,1)
+PN
n=1 (1 −zn)(xn−µ)2
N−PN
n=1 znβn(1,1) (4.45)
π(κ+1) =PN
n=1 znβn(1,1)
N.(4.46)
These o mulas educe o he e-es ima ion o mulas o censo ed da a p esen ed in he p e-
ious sec ion i he d opping a e is se o π= 0. Then βn(1,1) = 0 and βn(0,1) = 1.
As can be seen in Eqs. (4.44), (4.45) and (4.46), no only obse able and censo ed da a,
bu also d opped da a con ibu e o he es ima es.
4.3. Op imal Classi ica ion Rule o Censo ed and D opped
Gaussian Da a
Abo e ML pa ame e es ima ion is done o all possible use loca ions ℓkand i is done
o he measu emen s o each AP sepe a ely, assuming ha da a om di e en APs a e
independen . The inal pa ame e es ima es a e deno ed by ˆ
µk= [ˆµk,1,···,ˆµk,NAP ]Tand
ˆ
Σk=diag ˆσ2
k,1,···,ˆσ2
k,NAP , whe e NAP is numbe o obse able APs.
Indoo localiza ion can be o mula ed as a classi ica ion p oblem, whe e he classes a e
he posi ions om which RSSI measu emen s a e aken du ing he o line aining phase.
Fo each posi ion ℓk he pa ame e s o a Gaussian class-condi ional densi y pY(x|ℓk)o RS-
SI measu emen s a e es ima ed using he EM algo i hm o he las sec ions. Du ing online
classi ica ion, o es ima e he use ’s loca ion, an op imal classi ica ion ule is de eloped.
Le x=x1,···, xNAP be he ec o o he online measu emen . Fi s he pos e io is
calcula ed as ollows
p(ℓk|x) = QNAP
i=1 p(xi|ℓk)P(ℓk)
PK
k′=1 QNAP
i=1 p(xi|ℓk′)P(ℓk′)(4.47)
whe e Kis he numbe o o line aining loca ions and xiis he RSSI o i- h AP. P(ℓk)is
he p io on he posi ion. He e we ha e employed he assump ion o he independence o he
RSSIs o di e en APs. I is no ed ha he es da a a e also subjec o censo ing.
The likelihood p(xi|ℓk)in Eq. (4.47) can be calcula ed as ollows o censo ed Gaussian
da a
p(xi|ℓk) = Z∞
−∞
p(xi|yi)pY(yi|ℓk)dyi,(4.48)
Sma phone Adap a ion wi hin he MLLR F amewo k
40
w(c(k))
i(κ+1)
can be ob ained as ollows
w(c(k))
i(κ+1) =
R
X
=1
N
X
n=1
γk (n)
σ2
k ,i zn,i
I1(λ(κ)
k ,i)
I0(λ(κ)
k ,i)βk ,i(0,1) + (1 −zn,i)xn,i!ξT
k
R
X
=1
N
X
n=1
γk (n)
σ2
k ,i
(1 −zn,iβk ,i(1,1)) ξk ξT
k !−1
(5.20)
5.2.2. Va iance Adap a ion
Va iance adap a ion is pe o med a e mean adap a ion. I is no ed ha we assume he RSSI
measu emen s om di e en APs a e independen .
Le Σkbe he diagonal co a iance ma ix o he Gaussian andom ec o modelling he
RSSI eadings o he APs a posi ion ℓk. The adap ed a iance can be calcula ed as ollows
[70]: ˆ
Σk=BT
kH(c(k))Bk(5.21)
whe e H(c(k)) is he ans o m o be es ima ed and Bkis he Choleski ac o o Σk. Since Σk
a e diagonal co a iance ma ices, he e-es ima ion o mula Eq. (5.21) simpli ies o ˆσ2
k,i =
h(c(k))
iσ2
k,i;i= 1,...,NAP .
To es ima e H(c(k)), we again employ he EM algo i hm. The expec ed log-likelihood o
he comple e da a, gi en he obse ed, has he same o m as in mean adap a ion. Howe e ,
he e λk,i ={πk,i, h(c(k))
i, θk,i}wi h h(c(k))
iis he i- h componen o he main diagonal o
H(c(k)).
Using all in he expec ed log-likelihood unc ion Eq. (5.12), we a i e a :
Q(λ;λ(κ)) =
K
X
k=1
N
X
n=1
γk(n)
NAP
X
i=1 (zn,iβk,i(0,1) ln(1 −πk,i)
+zn,iβk,i(0,1)
I0(λ(κ)
k,i )Zc
−∞
ln 
1
q2πh(c(k))
iσ2
k,i
exp −(yn,i −ˆµk,i)2
2h(c(k))
iσ2
k,i !
N(yn,i;λ(κ)
k,i )dyn,i
+ (1 −zn,i) ln(1 −πk,i) + (1 −zn,i) ln 
1
q2πh(c(k))
iσ2
k,i
exp −(xn,i −ˆµk,i)2
2h(c(k))
iσ2
k,i !

+zn,iβk,i(1,1) ln(πk,i))(5.22)
The e-es ima ion omula o h(c(k))
iis eadily ob ained by compu ing he de i a i e o

Sma phone Adap a ion wi hin he MLLR F amewo k
41
Eq. (5.22) w. . . h(c(k))
iand se ing i o ze o:
h(c(k))
i(κ+1) =1
σ2
k,i PN
n=1 γk(n) (1 −zn,iβk,i(1,1))
N
X
n=1
γk(n)
((1 −zn,i)(xn,i −ˆµk,i)2βk,i(0,0)
+zn,i I2(λ(κ)
k,i )
I0(λ(κ)
k,i )−2I1(λ(κ)
k,i )
I0(λ(κ)
k,i )ˆµk,i + ˆµ2
k,i!βk,i(0,1)).(5.23)
He e ˆµk,i a e he new upda ed means which we e discussed in he p e ious subsec ion.
As can be seen in he de i a ion, beside es ima ing he adap a ion ma ices o means
Eq. (5.18) and a iances Eq. (5.23), he d opping a es o he adap a ion da a a e simul a-
neously es ima ed. Eq. (5.18) and Eq. (5.23) show ha no only he obse able measu e-
men s, bu also he unobse able ones con ibu e o he es ima e o he adap a ion ma ices.
I nei he censo ing no d opping occu s, i.e., πk,i = 0 and zn,i = 0, Eq. (5.18) and Eq. (5.23)
educe o he o mulas o mean and a iance adap a ion p esen ed in [70].
5.3. Reg ession Classes
In he p e ious sec ion, he me hod o aligning aining model wi h adap a ion da a in he
p esence o clipped and d opped da a has been p esen ed o he gene al case o mul iple
ans o ma ion ma ices.
I he ela ionship be ween wo se s o aining da a and adap a ion da a ollows only one
linea ule as men ioned in [61], only one se o adap a ion ma ices, i.e., mean adap a ion
ma ix and a iance adap a ion ma ix, o all s a es is needed.
Howe e , acco ding o ou da a p elimina y s udy, he ela ionship o RSSI da a measu-
ed by any pai o de ices does no ollow only one linea ule. Two possible main ac o s
which in luence he ela ionship be ween wo se s o da a a e signal s eng h ange and signal
equency. This is ob ious because o he ac ha he sensi i i ies o adio signal senso s de-
pend on he s eng h and he equency o he measu ed adio signal. To elax he linea i y
assump ion, a clus e ing app oach has been applied o sepe a e he use posi ions in mul iple
eg ession classes ha sha e he same linea ela ionship, howe e di e en om he o he
clus e s.
Howe e , a c i ical issue is how o de ine he eg ession classes, wi hin which he pa a-
me e s o all s a es, i.e., inge p in posi ions, change in he same manne . Since no p io
knowledge o which models should sha e he same ans o ma ion ule is a ailable, a c i e i-
on o inding eg ession classes mus be ound. Va ious c i e ia could be used o clus e ing,
o example, he posi ions wi h simila RSSI PDFs could sha e he same linea ule. The si-
mila i y o he PDFs can be measu ed by compu ing he likelihood o obse ing he aining
da a collec ed a one posi ion gi en he aining models o he o he s. Using hese c i e ia,
means and a iances o he aining models a e employed. Howe e , om ou obse a ion,
he s a es, i.e., posi ions, which ans o m in he same manne ha e simila RSSI mean a-
lues, i espec i e o he ac ual iden i y o he APs. As a esul , hose posi ions should be
assigned in o he same clus e . We hus apply a k-means clus e ing on he mean ec o s µk
Sma phone Adap a ion wi hin he MLLR F amewo k
42
o he p obabili y densi y unc ion o all loca ion ℓk o ob ain Cclus e s. Fo each clus e ,
ans o ma ion ma ices a e es ima ed as p esen ed in he p e ious sec ion.
6. Hidden Ma ko Model o Indoo
Use T acking
6.1. Mo i a ion
In chap e 4, we ha e discussed he me hod o es ima e he pa ame e s o censo ed and d op-
ped Gaussian da a and he op imal classi ica ion ule o localizing indoo use s. The p o-
posed algo i hms belong o he mos common app oach o indoo posi ioning which is he
inge p in ing based app oach. Finge p in ing echniques a e able o p oduce a s able posi-
ioning accu acy o e ime and mo emen dis ance o he use . Howe e , he e is ano he
app oach which can also be applied success ully in indoo posi ioning, namely he Dead
Reckoning echnique. This echnique uses da a om ine ial senso s o loca e he use posi-
ion. Howe e , as discussed in chap e 2, he Dead Reckoning echnique is o en applied in
a combina ion wi h o he posi ioning echniques since i can only p oduce p ecise posi ion
es ima es in a sho pe iod o ime and small dis ance. Fo long e m use and la ge dis ance,
he posi ion e o is un easonably la ge because he e o s a e accumula ed o e ime and
dis ance.
As discussed, he s abili y o inge p in ing based indoo posi ioning echniques make
hem become he common candida es o accompany wi h DR echniques in indoo posi io-
ning. Va ious combina ions ha e been p oposed o keep he ad an ages and o educe he
disad an ages o hose wo app oaches. Senso usion can be achie ed by a Kalman il e
[31], pa icle il e [32] o wi h he use o a Hidden Ma ko Model (HMM) [29, 30]. Among
hose possible solu ions, we decided o employ he HMM in ou sys em because i gi es us
he possibili y o employ he knowledge o possible walking pa h which may imp o e he
posi ioning accu acy.
6.2. Hidden Ma ko Model o Indoo Use T acking
In his sec ion, he me hod o employ a HMM o use RSSI measu emen s and s ep de ec ion
in o ma ion o posi ion es ima ion is p esen ed.
Fi s , i should be ecalled ha he s anda d HMM can be depic ed as in Fig. 6.1. He e,
s is he hidden s a e a iable and x is he obse a ion a ime . I is no ed ha he hidden
s a es canno be obse ed, howe e , he mos likely sequence o s a es can be in e ed om
he sequence o obse a ions gene a ed by HMM. The HMM is de e mined by h ee se s o
pa ame e s: he emission p obabili ies, he s a e ansi ion p obabili ies and he ini ial s a e
p obabili ies. Fig. 6.2 shows he un olding o a s a e diag am o e ime, called ellis diag am.
He e i is assumed ha he HMM has K= 4 di e en s a es, i.e., K= 4 di e en alues
43
Hidden Ma ko Model o Indoo Use T acking
44
s −1s s +1
x −1x x +1
Figu e 6.1.: S anda d Hidden Ma ko Model: s is he hidden s a e a iable and x is he obse a ion
a ime
o s :s ∈ {1,2,3,4}. Each column in he g aph (co esponding o a ime ins an ) con ains
nodes ep esen ing he s a es o he HMM. Each node in he g aph has connec ions o a leas
one node a an ea lie and one node a a la e ime. The connec ions ep esen he possible
ansi ions be ween s a es. The ansi ions om one s a e a one ime ins an o he possible
s a es a he la e ime ins an ha e p obabili ies which sum up o 1, i.e., PK
j=1 Pi,j = 1,
whe e Pi,j =P(s +1=j|s =i), assuming he ansi ion p obabili ies a e independen o ime,
gi en any i= 1,...,K. Wi hou any p io knowledge, he ansi ion p obabili ies om one
s a e o he nex can be assumed o ollow a uni o m dis ibu ion.
1
1
1
2
2
2
3
3
3
4
4
4
P1,1
P1,2
P1,3
Figu e 6.2.: T ellis diag am wi h ou di e en s a es s ∈ {1,2,3,4}and Pi,j a e he ansi ion
p obabili ies om s a e ia one ime ins an o s a e ja he la e ime ins an
The emaining pa ame e s o a HMM a e he emission p obabili y dis ibu ions. Fo each
HMM s a e, he emission p obabili y dis ibu ion p(x|s )gi es he likelihood o obse ing x
a s a e s . Those emission PDFs a e supposed o be di e en amongs s a es. Fo posi ioning
pu pose, we iden i y s wi h he posi ion o he use a ime : i s =k hen he use is a he
loca ion ℓka ime , whe e ℓkis a wo-dimensional ec o desc ibing he use ’s loca ion. In
WiFi inge p in ing based indoo posi ioning sys em, he RSSI aining models and he online
RSSI measu emen s can be conside ed as emission p obabili ies and obse a ion sequence,
espec i ely.
Howe e , wi h s ep de ec ion in o ma ion, he e is ano he se o obse a ions, i.e., mo e-
Hidden Ma ko Model o Indoo Use T acking
45
men obse a ions. To inco po a e he s ep de ec ion in o ma ion, he emission p obabili y
dis ibu ions o his kind o obse a ion need o be de ined. In ui i ely s ep de ec ion in o -
ma ion gi es us he in o ma ion abou mo ing om one s a e o ano he s a e, i.e., he s a e
ansi ions, ins ead o he in o ma ion abou a single s a e. So he solu ion he e is o associa e
an obse a ion wi h a s a e ansi ion a he han a s a e. This ends up wi h a modi ica ion o
he HMM o combine RSSI and s ep de ec ion obse a ions as depic ed in Fig. 6.3. In he
ollowing, his model is called modi ied HMM.
s −1s s +1
x −1x x +1
+1
Figu e 6.3.: Modi ied HMM o posi ion es ima ion based on he usion o RSSI and mo emen ec-
o obse a ions xand , espec i ely.
He e, is he wo-dimensional mo emen ec o which deno es he a e sed ou e om
s −1 o s . is ob ained om ine ial senso measu emen s. I s compu a ion will be discus-
sed in sec ion 6.4. In he modi ied HMM, RSSI measu emen s and mo emen ec o s a e
aken as obse a ions a ached o he hidden s a es and he s a e ansi ions, espec i ely. The
ansi ion p obabili ies be ween he s a es a e chosen o e lec which posi ions a e accessi-
ble om a gi en s a e wi hin one measu emen in e al. Only ansi ions o hose posi ions
which a e accessible wi hin one measu emen in e al will be gi en a p obabili y g ea e han
ze o. Wi h he Samsung And oid sma phones we ha e a hand, he measu emen in e al is
oughly 1,5 s which is he equi ed ime o upda e a new WiFi scan o he de ices.
6.3. Fo wa d Algo i hm
Wi h he employmen o a HMM, he es ima ion o he use posi ion can hen be ca ied ou
ei he by he Fo wa d algo i hm, he Vi e bi algo i hm o he Fo wa d-Backwa d algo i hm.
While Fo wa d algo i hm compu es he p obabili y o being in a ce ain s a e by ga he ing
he p obabili ies o e all possible p edecesso s a es, he Vi e bi algo i hm conside s only he
mos p obable p edecesso . The Fo wa d-Backwa d algo i hm is only o academic in e es
because he induced la ency is no accep able o an online posi ioning sys em. In he ollo-
wing, he Fo wa d algo i hm which aims o es ima e he mos p obable s a e a ime ins an
gi en he his o y o obse a ions was chosen o decode he use posi ion.
Le x1: = [x1,...,x ]be he sequence o RSSI measu emen s up o ime . The s ep
de ec ion in o ma ion is ga he ed in he sequence 1: = [ 1,..., ]. Ou goal is o compu e
P(s =k| 1: ,x1: ), i.e., he p obabili y o being in he k- h s a e o all possible use posi ions
ℓk, k = 1,...,K, gi en all RSSI alues and s ep de ec ion ec o s measu ed so a . Using
Bayes’ ule, he p obabili y can be exp essed as ollows:
P(s =k| 1: ,x1: ) = p(s =k, 1: ,x1: )
p( 1: ,x1: )
∝p(s =k, 1: ,x1: ) =: α (k),(6.1)

Hidden Ma ko Model o Indoo Use T acking
46
whe e he so-called Fo wa d a iable α (k)is he p obabili y o being a ime in s a e k,
while ha ing obse ed he sequence o x1: and 1: .
Using ma ginal p obabili y and chain ule, he o wa d a iable can be w i en as ollows
α (k) = X
i
p(s =k, s −1=i, 1: ,x1: )
=X
i
p( |s =k, s −1=i, 1: −1,x1: −1,x )
·p(x |s =k, s −1=i, 1: −1,x1: −1)
·P(s =k|s −1=i, 1: −1,x1: −1)
·p(s −1=i, 1: −1,x1: −1).(6.2)
Applying he p ope ies o he HMM, which a e depic ed in he g aphical model o Fig. 6.3,
i.e., x is independen o all o he a iables i s is gi en, s is independen o x1,...,x −1
and 1,..., −1i s −1is gi en, and is independen o e e y hing i s −1and s a e gi en,
and assuming he s ep de ec ion and RSSI in o ma ion o be s a is ically independen o each
o he gi en he use loca ion, he abo e o mula simpli ies o
α (k) = X
i
p( |s =k, s −1=i)·p(x |s =k)
·P(s =k|s −1=i)·p(s −1=i, 1: −1,x1: −1)
|{z }
=α −1(i)
(6.3)
which is a ecu sion o he o wa d a iable.
The inal loca ion es ima e ˆ
ℓis ob ained by he weigh ed a e age o e he se Po he
mos likely posi ions:
ˆ
ℓ=1
P
k∈P
α (k)X
k∈P
α (k)·ℓk.(6.4)
Equa ion (6.3) shows how he di e en knowledge sou ces a e combined. The ansi ion
p obabili ies P(s =k|s −1=i)a e nonze o only o hose loca ions ℓk ha can be eached
om posi ion ℓiwi hin one ime s ep. The choice o he ansi ion p obabili ies hus enco-
des ou knowledge abou he loo plan. The e m p(x |s =k)is he likelihood o he RSSI
measu emen x , assuming ha he use ’s posi ion is ℓk. The compu a ion o emission PDF
es ima ion and likelihood calcula ion we e discussed in Chap e 4. The mo emen in o ma-
ion ga he ed om he s ep de ec ion is cap u ed by he e m p( |s =k, s −1=i), i.e., he
likelihood o obse ing he mo emen ec o when mo ing om posi ion ℓi o ℓk.
I is no ed ha his de i a ion equi es ha RSSI measu emen s and he mo emen in o -
ma ion a e ob ained a he same a e. In ac , he a e o use ’s s eps is o en highe han RSSI
measu emen s. To synch onize hese 2sou ces o da a, mo emen ec o is he accumu-
la ed esul s o he s ep in o ma ion du ing 1RSSI measu emen in e al.
6.4. Mo emen Vec o Es ima ion
In his sec ion, he me hod o in e he s ep de ec ion in o ma ion om da a measu ed by
accele a ion senso , gy oscope senso and magne ic senso is summa ized. Mo e de ailed
in o ma ion abou mo emen ec o es ima ion can be ound in [71].
Hidden Ma ko Model o Indoo Use T acking
47
The sys em o es ima e he mo emen ec o s is depic ed in Fig. 6.4.
a
m
g
gy
kak ka′k
−
G
ka′kLP
Rdψ b
ψ
S eps
ψ
S ep leng h Ls ep
1:
k·k Lowpass
il e
O ien a ion
Angula
eloci y
Kalman il e
Mo emen calcula ion
S ep de ec ion
Figu e 6.4.: S ep de ec ion and posi ion es ima ion sys em o e iew
He e, ais he 3-dimen ional accele a ion ec o om he accele ome e o he sma phone,
G= 9,81 m/s2is he g a i y cons an , which will be used o pe o m he s ep de ec ion
p ocedu e. m,gand gy a e he magne ome e da a, g a i y in o ma ion and gy oscope
da a, espec i ely, will be used o es ima e he mo emen heading o he use . The g a i y
in o ma ion ec o gis he 3-dimen ional ec o which con ains he o ce o g a i y along
h ee axes o he sma phone. Ris he o a ion ma ix, ψis he angle be ween mo emen
heading and he magne ic no h di ec ion, and dψ deno es he changes o ψo e ime. The
de ail in o ma ion abou hese da a and how o e ie e hem by an And oid applica ion can
be ound on he websi e o and oid de elope s [72]. Mo emen ec o is compu ed by
accumula ing he es ima ed mo emen o all de ec ed s eps wi hin one RSSI measu emen
in e al.
6.4.1. S ep De ec ion
The s ep de ec ion p ocedu e is based on he measu ed accele a ion da a om he sma pho-
ne. The ob ained samples a e s o ed in 3-dimensional ec o s a= [ax, ay, az]Twhe e x, y, z
a e he axes in he coo dina e sys em. This is de ined in he ela ion wi h he sc een o he
sma phone as shown in Fig. 6.5(a)
(a) De ice coo dina es sys em (b) Wo ld coo dina e sys em
Figu e 6.5.: De ice coo dina e sys em (a) and wo ld coo dina e sys em (b)
Hidden Ma ko Model o Indoo Use T acking
48
The cha ac e is ics o he use mo emen is cap u ed in he accele a ion da a as depic ed in
Fig. 6.6. As can be seen in he example he accele a ion componen along he z-axis clea ly
shows he up and down mo ion caused by walking. I is no ed ha he measu ed da a a e
always in luenced by he o ce o g a i y. The e o e, o ob ain he eal accele a ion da a, he
con ibu ion o he o ce o g a i y mus be elimina ed. One can use his az o s ep de ec ion
pu pose i ha is he s able ea u e o he ob ained da a. Howe e , his is jus an example o
accele a ion da a when he sma phone was held in he way ha i s sc een is in pa allel wi h
he ea h su ace. I he sma phone, howe e , is held in an a bi a y a i ude, he obse ed
da a will no ollow he example da a in he igu e any mo e. Because o ha eason, ins ead
o using da a om one speci ic componen , he Euclidean no m o he accele a ion da a om
all h ee componen s is used o pe o m s ep de ec ion, see Eq. (6.5). Fig. 6.7 shows he
calcula ed no m alues a e subs ac ing he o ce o g a i y cons an G=9.81.
kak=qa2
x+a2
y+a2
z(6.5)
az
Samples
ay
Samples
ax
Samples
Raw Accele a ion Da a [m/s2]
128 192 256 320
128 192 256 320
128 192 256 320
−10
0
10
20
30
−20
0
20
−20
0
20
Figu e 6.6.: Example o aw accele a ion da a i he sma phone is held wi h display in pa allel o
ea h su ace when walking
To educe he a ia ion caused by senso e o s, a 5-Hz lowpass il e is applied, as is
sugges ed in [57]. Fig. 6.8 shows he ou pu signal o he lowpass il e . He e, a Bu e wo h
low-pass o o de 20, wi h a cu o equency o 0.2· n= 5Hz, whe e nco esponds o a
hal o he sampling a e (50Hz/2) is used.
In he li e a u e, wo common app oaches which ha e been employed in many esea ch o
de ec s eps using accele a ion da a a e peak de ec ion and ze o c ossing coun . In [57] a peak
de ec ion wi h a minimum h eshold is used o coun he s eps. This has he disad an age
ha some imes he maximum is spli in o wo local maxima and hus an addi ional s ep
is de ec ed. The o he me hod o de ec ing s eps calcula es he ze o c ossing a e o he
Hidden Ma ko Model o Indoo Use T acking
49
ka′k=kak−G
Samples
128 192 256 320
−10
−5
0
5
10
Figu e 6.7.: No m o accele a ion da a a e subs ac ing he o ce o g a i y cons an G=9.81
accele a ion da a [59], which in case o noisy da a may also esul in addi ionally de ec ed
s eps.
The p oposed app oach combines he s eng hs o peak de ec ion and ze o c ossing coun
app oaches by coun ing he c ossing a e o accele a ion da a o e a ce ain h eshold. Ou
me hod is hen able o cope wi h mul iple local maxima and noisy da a in he measu ed
accele a ion da a.
Fig. 6.9 illus a es he h eshold-c ossing app oach. The s ep coun e is only inc eased i
he h eshold (magen a line) is la ge han he sa e y h eshold ( ed line) o a oid an e oneous
coun ing when he use is no mo ing bu he e is s ill some luc ua ion o he obse ed
accele a ion da a. The h eshold is no a ixed alue h ough he whole p ocess, ins ead i is
calcula ed o e e y single da a block. He e a block size o 64 samples is chosen ega ding
he sampling a e o accele a ion senso and p ocessing speed. Fi s , o each da a block,
he peak mean is de e mined by calcula ing he mean o all he de ec ed peaks. Second,
he h eshold is compu ed by mul iplying he peak mean wi h an expe imen ally de e mined
weigh ing ac o . In ou expe imen , he weigh ing ac o o 0.6p oduces he bes esul s.
Recen ly, ano he me hod, namely au oco ela ion me hod, o de ec ing s eps has been
p oposed in [32]. This me hod employs he ac ha he accele a ion da a exhibi s a e y
epe i i e pa e n. The ad an age o he au oco ela ion me hod compa ed o peak de ec ion
and ze o c ossing coun me hods is ha i is able o elimina e he hand ges u es when he
use is no mo ing, ansi ion om si ing o s anding and ice e sa, and so on. Acco ding
o ou expe imen al esul s, he au oco ela ion me hod ou pe o ms he o he wo adi ional
me hods. The e o e, a he cu en s a e o ou p ojec , his me hod is employed in ou sys em
o de ec ing s eps.
Howe e , his sec ion aims o p esen ou p oposed app oach o de ec s eps which has be-
Expe imen al Resul s on Indoo Posi ioning
56
Table 7.1.: Mean and s anda d de ia ion o APs a 2 posi ions o a i ical da a expe imen
AP index AP1 AP2 AP3 AP4 AP5
µ1,i -102 -103 -97 -89 -95
µ2,i -105 -100 -99 -86 -101
σ1,i 4.8 4.9 5.0 5.2 5.1
σ2,i 5.0 4.8 4.8 5.4 5.0
Table 7.2.: Classi ica ion e o a e on a i icial censo ed da a
Me hod E o a e (%)
Plain ng + ecog 30.7
EM ng + plain ecog 26.9
EM ng + censo ed ecog 22.5
3-s onges APs 35.1
1-nea es neighbo 36.8
•Plain aining ( ng) + ecogni ion ( ecog): ML pa ame e es ima ion is ca ied ou
assuming no mally dis ibu ed, uncenso ed da a. Also ecogni ion is pe o med dis e-
ga ding any censo ing.
•EM ng + plain ecog: ML pa ame e es ima ion in aining accoun s o he censo ed
da a using he p oposed EM algo i hm, while he p esence o censo ed da a is s ill
dis ega ded in ecogni ion.
•EM ng + censo ed ecog: T aining wi h he p oposed EM algo i hm and ecogni ion
employing eq. (4.52).
•3-s onges APs: Selec h ee s onges APs o each loca ion in he aining phase, hen
apply EM ng + censo ed ecog.
•1-nea es neighbo classi ica ion ule.
Table 7.2 clea ly shows he supe io i y o he schemes which a e awa e o he censo ing.
Conside ing he p esence o censo ed da a in aining imp o ed he e o a e om 30.7% o
26.9%, and a u he imp o emen o 22.5% is ob ained by accoun ing o censo ed da a also
in ecogni ion. We can also see he impo an ole o weak APs o he ecogni ion accu acy:
using only he h ee s onges APs aises he e o a e o 35.1%.1-nea es neighbo pe o ms
wo s wi h he e o a e o 36.8%.
Field Da a
In o de o e alua e he pe o mance o he p oposed EM algo i hm on eal wo ld da a, eal
WiFi RSSI measu emen s we e ga he ed on a loo o an o ice building consis ing o 10
o ice ooms and a long aisle ha ing an o e all size o 12 m by 30 m (see Fig. 7.1). RSSI
alues we e aken a 25 di e en posi ions, oughly e enly dis ibu ed, esul ing in an a e age
dis ance o 2,7 m be ween wo loca ions. Two measu emen campaigns we e ca ied ou
using a sma phone, wi h 100 measu emen s aken pe posi ion pe campaign. Da a o he

Expe imen al Resul s on Indoo Posi ioning
57
i s measu emen campaign se ed he pu pose o aining and he second one was o es ing
pu poses. Fo he aining da a se , he pe cen age o uncenso ed obse a ions, a e aged o e
all APs which we e obse able a each loca ion, was ound o be 36.7%.
Figu e 7.1.: Floo plan o he a ea whe e ield da a has been conduc ed.
To compa e he p oposed app oach o a s a e-o - he-a sys em, he algo i hm om [52]
was implemen ed. The e, o each loca ion ℓk he p obabili y dis ibu ions o he 10 s onges
APs a e de e mined du ing he aining phase and compa ed o hose o he online measu-
emen s employing he Bha acha yya coe icien . A 3-nea es neighbo ule is hen applied
o decide on he use loca ion. Fu he mo e, we compa ed wi h he well-known sys em, RA-
DAR [18], whe e classi ica ion is pe o med wi h a 3-nea es neighbo ule, employing he
Euclidian dis ance. When applying he p oposed algo i hm, 5online measu emen s we e
used o each es ima e, he inal loca ion es ima e was hen compu ed using he 3mos likely
posi ions, see Eq. (4.53). I is no ed ha 5online measu emen s we e also employed in he
implemen a ion o he algo i hm o [52].
Fig. 7.2 shows he cumula i e dis ibu ion unc ion (CDF) o he e o as a unc ion o he
dis ance o each me hod. The CDF is de ined as he p obabili y ha he posi ioning e o ǫ
is lowe han a ce ain dis ance d:
CDFǫ(d) = P(ǫ≤d)d≥0.(7.1)
The esul s in Fig. 7.2 show ha he p oposed me hod ou pe o ms he o he wo, especial-
ly o he 40% e o quan ile. No e, also, ha he compu a ional cos o he p oposed me hod
du ing he online phase is smalle han hose o compu ing he Bha acha yya dis ances be -
ween p obabili y dis ibu ions [52] o he nea es -neighbo based [18] me hods.
A e [18]
A e [52]
P oposed algo i hm
Dis ance d[m]
CDFǫ(d)
0 2 46 8 10
0
0.2
0.4
0.6
0.8
1
Figu e 7.2.: CDF o he posi ioning e o o di e en sys ems.
Expe imen al Resul s on Indoo Posi ioning
58
Table 7.3.: Classi ica ion e o a e on a i icial censo ed and d opped da a
Me hod E o a e (%)
EM ng + censo ed ecog 29.7
Ad . EM ng + censo ed & d opped ecog 25.7
7.1.2. EM algo i hm o censo ed and d opped da a
In he ollowing, expe imen al esul s showing he e ec i eness o EM algo i hm when being
awa e o d opped da a in addi ion o censo ed da a a e p esen ed. Fo con enience, le us call
he EM algo i hm o pa ame e es ima ion o censo ed and d opped da a as he ad anced
EM algo i hm.
A i icial Da a
The a i icial da a we e gene a ed acco ding o he pa ame e s which we e used in Sec i-
on 7.1.1, howe e , he means o all APs a all posi ions a e inc eased by 10 dBm o show
mo e impac o d opped da a on he es ima ed pa ame e s and consequen ly on classi ica ion
esul s. The gene a ed Gaussian da a we e i s censo ed and hen d opped wi h he d opping
a e o 20%. Since he e ec i eness o EM algo i hm o censo ed da a has been p o ed in
he p e ious sec ions, his sec ion aims o compa e he classi ica ion esul s be ween wo
p oposed EM algo i hms o show he impo ance o he awa eness o d opped da a besides
censo ed da a.
Table 7.3 shows he classi ica ion esul s on censo ed and d opped da a using he p oposed
EM algo i hms. I can be seen ha he pa ame e es ima ion o mulas de i ed in Sec ion 4.2.3
a e able o cope wi h an unknown d op-ou a e, which leads o he imp o emen in he
classi ica ion e o a e om 29.7% o 25.7% i indeed d op-ou s occu . The eason is i
all unobse able da a a e conside ed as censo ed da a, he pa ame e s es ima ed by he EM
algo i hm which is awa e o censo ed da a only, a e inaccu a e, i.e., he es ima ed means
a e biased o he le o he ue means and he es ima ed a iances a e highe han he ue
a iances. These inaccu a e es ima ed pa ame e s cause he deg ada ion o he classi ica ion
pe o mance.
Field Da a
To demons a e he e ec i eness o he ad anced EM algo i hm, an expe imen on eal ield
da a has been done. This expe imen was done by using he same da a se s as used in he ex-
pe imen o he EM algo i hm o censo ed Gaussian da a. Fig. 7.3 shows he expe imen al
esul s on eal ield da a using he wo p oposed EM algo i hms. As can be seen, being awa e
o d opped da a imp o es he posi ioning accu acy, hough he imp o emen is mode a e.
The easons migh be ei he he amoun o aining da a, 100 samples pe posi ion, a e no
su icien o he ad anced EM algo i hm since i ies o es ima e mo e pa ame e s, o he
ue d opping a es a e low. Since he da a se s we e ga he ed in a eal indoo en i onmen ,
ue d opping a es a e unknown. As ou s udy on he esul s, he es ima ed means and a-
iances om ad anced EM a e be e han he EM algo i hm awa ing o censo ed da a only,
and he es ima ed d opping a e a e aged o e all APs and all loca ions was app oxima ely
Expe imen al Resul s on Indoo Posi ioning
59
0.37, we concluded ha he limi ed imp o emen o posi ioning accu acy is because o he
no e y accu a e es ima ed d opping a es. As p esen ed in sec ion 4.3, d opping a e plays
an impo an ole in likelihood calcula ion o he unobse able da a, so he inaccu a e es i-
ma ed d opping a es limi he imp o emen in classi ica ion esul s. In he bad case o low
accu acy o he es ima ed d opping a es, he posi ioning accu acy migh e en dec ease.
EM Censo ed
Ad . EM
CDFǫ(d)
Dis ance d[m]
01 2 3 4 56 7 8910
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figu e 7.3.: Compa ing he expe imen al esul s on eal da a using 2p oposed EM algo i hms
7.2. Sma phone Adap a ion
This sec ion in es iga es he impac o he p oposed adap a ion app oach on he accu acy o
inge p in ing based indoo posi ioning. Some a ia ions o he adap a ion app oach wi hin
he MLLR amewo k such as mean and a iance adap a ion, mean adap a ion only wi h ull
o diagonal adap a ion ma ix ha e been implemen ed. In addi ion, he impac o he numbe
o adap a ion da a and o he numbe o eg ession classes on he pe o mance o adap a ion,
and consequen ly on he posi ioning accu acy, a e also in es iga ed.
7.2.1. Classi ica ion on A i icial Da a
In his se o expe imen s, a i icial da a we e gene a ed o assess he impac o he d op-ou
a e and he amoun o adap a ion da a on he classi ica ion pe o mance.
1000 samples o aining da a we e gene a ed o each o K= 6 posi ions and o NAP = 2
access poin s. A single a ine ans o ma ion o he means o he aining da a is used o
each loca ion acco ding o ˆ
µk=Aµk+b, whe e A= [0.9,0; 0,0.9] and b= [−3,2]T.
Adap a ion and es da a we e hen gene a ed by sampling om he ans o med Gaussians
wi h means ˆ
µkand a iances as hose o he aining da a. While he amoun o adap a ion
da a was g adually inc eased om 1% o 5, 10, 50 and 100% o he numbe o aining
samples, he numbe o es samples was ixed a 100 obse a ions pe posi ion. The alue o
he d op-ou a e is se o 0% (no d op-ou s, π= 0) and 20% (π= 0.2).
Al hough he e ec i eness o being awa e o d opped da a on classi ica ion esul s was
demons a ed in sec ion 7.1.2, o he con enience o e alua ing he e ec i eness o he
adap a ion app oach, classi ica ion esul s employing ad anced EM wi h he cu en se o
pa ame e s a e s ill p esen ed. Table 7.4 discusses he impac o he d op-ou a e wi hou
Expe imen al Resul s on Indoo Posi ioning
60
Table 7.4.: Classi ica ion esul s (% posi ions co ec ly classi ied) when aining and es da a a e
gene a ed om he same pa ame e se
Awa e o d opping yes no
π= 0 86 86
π= 0.275 64
Table 7.5.: Adap a ion pe o mance (% posi ions co ec ly classi ied) on a i ical da a as a unc ion
o amoun o adap a ion da a
No. Pos wi h adap . da a π0% 1% 5% 10% 50% 100%
3 0 68 81 85 85 86 86
0.2 56 70 73 74 75 75
6 0 68 85 86 86 86 86
0.2 56 72 75 75 75 75
adap a ion. He e, he ’adap a ion’ da a we e used o a comple ely new aining om sc a ch
o each o he 6posi ions. 1000 samples o adap a ion da a we e used in his expe imen . As
can be seen, i no d opping occu s, he wo EM algo i hms p oduce he same classi ica ion
esul . Once he d opping occu s, he ad anced EM algo i hm ou pe o ms he o he .
Table 7.5 shows he e ec i eness o applying he p oposed adap a ion algo i hm. As can
be seen, he esul s when only 3loca ions ha e adap a ion da a is compa able o he case
when adap a ion da a a e a ailable o all 6loca ions. The eason is e en i he e a e only
3loca ions wi h adap a ion da a, s ill he PDFs o all loca ions a e well adap ed, since hey
a e om a single eg ession class. Howe e , i is also no iceable ha when he numbe o
adap a ion da a pe posi ion is small, i.e., less han 10% o he aining da a, classi ica ion
esul s using 6posi ions wi h adap a ion da a a e abou 1 o 4% be e han hose when
adap a ion da a a e only a ailable o 3posi ions. The column wi h 0% o adap a ion da a
shows he esul s when no adap a ion is pe o med. Compa ing wi h he esul s o Table 7.4
i is clea ha he classi ica ion esul s a e adap a ion app oach hose o e aining, excep
when he e is only 1% o adap a ion da a, e en i adap a ion da a a e only a ailable o 3ou
o 6posi ions. Fo he case o only 1% o adap a ion da a a ailable, he e is s ill a d ama ic
imp o emen in classi ica ion esul s when adap a ion is employed compa ed o he case i
no adap a ion is pe o med.
7.2.2. Classi ica ion on Field Da a
To examine he e ec i eness o he adap a ion app oach on eal wo ld da a, measu emen s
we e collec ed on 3 loo s o an o ice building wi h oughly 30 ooms (lec u e halls, o ice
and labo a o y ooms), whe e each loo has an o e all size o 35 m by 35 m, RSSI alues
we e aken a 60 di e en posi ions wi h an a e age dis ance o 5.0m be ween 2posi ions.
200 measu emen s we e aken pe posi ion wi h 2di e en sma phones a each posi ion.
Da a o he i s sma phone we e used o es ima e he aining models while da a om he
second sma phone we e di ided in o 2se s a each posi ion. The i s was used o adap a ion
(0, 5, 25, o 75 samples) o e aining (150 samples) om sc a ch and he second was o
es ing (50 samples). Fo he measu ed da a, he es ima ed d opping a e a e aged o e all
Expe imen al Resul s on Indoo Posi ioning
61
Table 7.6.: RMS posi ioning e o (in [m]) as a unc ion o he amoun o posi ions ha ing adap a ion
da a and he amoun o ada a ion da a
Condi ion Adap a ion Me hod
No. Pos wi h Amoun o µ&σ2,µonly, µonly,
adap . da a adap . da a A ull A ull Adiag
0 6.15
15
5 5.08 4.76 3.93
25 4.60 4.41 3.93
75 4.62 4.52 3.93
30
5 3.86 3.96 3.84
25 3.82 3.96 3.85
75 3.76 3.91 3.85
60
5 3.74 3.93 3.84
25 3.67 3.87 3.83
75 3.65 3.87 3.84
e ain 2.43
APs and all posi ions was app oxima ely 0.3.
Fo he adap a ion p ocedu e, he es ima ed aining means we e so ed a each posi ion in
descending o de , and only he 8s onges APs we e used o es ima e he adap a ion ma ices
since he con ibu ion o he emaining APs o he likelihood was negligible. The adap a ion
ma ices a e hen used o calcula e he adap ed pa ame e s o he 8s onges APs a all
posi ions being in he same eg ession class.
Table 7.6 shows he dependency o he posi ioning accu acy on he numbe o loca ions
o which adap a ion da a a e a ailable and he amoun o a ailable adap a ion da a a each
posi ion. The esul s in Table 7.6 a e he a e age o he oo mean squa e (RMS) posi ioning
e o o 50 expe imen s. In each expe imen , es da a, adap a ion da a and he posi ions wi h
adap a ion da a a e andomly selec ed. As expec ed, he mo e posi ions he e a e wi h adap-
a ion da a and he mo e adap a ion samples pe posi ion, he be e he posi ioning esul s.
Fo all conside ed adap a ion me hods, imp o emen s in posi ioning accu acy a e ob ai-
ned, e en when e y ew adap a ion da a a e a ailable. Howe e , mean and a iance adap a-
ion wi h a comple ely illed ma ix Adeli e s only he bes esul s i he e a e su icien ly
many adap a ion da a, while he use o only mean adap a ion wi h a diagonal Ais supe io
i only ew adap a ion da a a e a ailable, since ewe pa ame e s need o be es ima ed. F om
he p esen ed esul s, indoo posi ioning sys em de elope s could ha e an idea o which and
how pa ame e s can be e icien ly adap ed gi en he a ailable adap a ion da a.
Howe e , he posi ioning accu acy when all 60 posi ions ha e adap a ion da a is s ill well
below he accu acy achie able, when aining and es da a a e collec ed by he same sma -
phone, which is 2.43 m. The eason could be one ans o ma ion ule could no desc ibe well
he ela ionship be ween aining and adap a ion da a o all posi ions which ac ually ollows
a nonlinea ule as discussed in chap e 5.
To elax he linea i y assump ion be ween aining and adap a ion da a, mul iple eg essi-
on classes a e employed. Fo es ima ing he eg ession classes, he means o he 8s onges
APs a each posi ion a e so ed in descending o de , he esul ing 8-dimensional ec o s a e

Expe imen al Resul s on Indoo Posi ioning
62
Table 7.7.: E ec o numbe o clus e s on RMS posi ioning e o
No. o clus e s 1 2 3
RMS pos. e o [m] 3.76 3.48 3.25
clus e ed using k-means, as discussed in sec ion 5.3. Table 7.7 shows he posi ioning esul s
when doing clus e ing and es ima ing di e en adap a ion ma ices o each clus e , assu-
ming ha in each clus e 50% o posi ions ha e adap a ion da a wi h 75 adap a ion samples
pe posi ion. I has o be no ed ha he op imal numbe o eg ession classes depends on he
amoun o a ailable adap a ion da a. The mo e adap a ion da a he mo e ans o ma ion ma-
ices can be eliably es ima ed. In ou se up he bes esul s we e achie ed wi h 3clus e s,
which led o a educ ion o he RMS posi ioning e o om 3.76 m o 3.25 m.
7.3. HMM o Indoo Use T acking
This sec ion e alua es he e ec i eness o he p oposed algo i hms discussed in Chap e 6
o an indoo posi ioning p oblem bo h on a i icially gene a ed da a and eal ield da a,
especially he impac o he in oduc ion o pseudo s a es on he classi ica ion/posi ioning
esul s.
7.3.1. A i icial Da a
Fig. 7.4 shows he HMM s a es wi h he loca ions o he egula and pseudo s a es ma ked
wi h ed and g een ci cles, espec i ely.
530 535 540 545 550 555 560 565
985
990
995
1000
1005
1010
1015
x[m]
y[m]
Figu e 7.4.: The modi ied HMM s a es, i.e., he allowable use posi ions, and he ansi ions be ween
hem. Red and g een ci cles indica e egula and pseudo s a es, espec i ely.
The RSSI measu emen s o 15 andomly placed APs o aining he Gaussian emission
PDF o he egula HMM s a es a e gene a ed a i icially as ollows: The signal s eng h ol-
Expe imen al Resul s on Indoo Posi ioning
63
Table 7.8.: Mean posi ioning e o on a i icial da a
Me hod Mean e o [m]
RSSI only [74] 1.74
RSSI + s ep de . [73] 1.37
RSSI + s ep de . + pseudo s a es [75] 1.02
lows a la ge-scale log-no mal ading model wi h an addi ional ze o mean Gaussian andom
a iable wi h s anda d de ia ion σL= 5 o model small-scale ading. A each posi ion, we
gene a ed a se o 300 RSSI measu emen s as he aining da a, hen es ima ed he pa ame e s
o RSSI dis ibu ion o each AP a each posi ion as desc ibed in Chap e 4.
The s ep de ec ion in o ma ion is modeled as a bi a ia e Gaussian wi h he mean µi,j =
ℓj−ℓiand a diagonal co a iance ma ix Σ wi h en ies Σ [1,1] = Σ [2,2] = 0,25 m2. This
alue has been de e mined in o line expe imen s.
In he expe imen , pseudo s a es we e in oduced in he way ha he Euclidean dis ance
be ween neighbo ing s a es is no mo e han a mos 0,75 m (which is close o he measu ed
a e age s ep leng h wi hin he expe imen al da a), while he dis ance be ween wo neighbo-
ing egula s a es is abou 3-5m excep o some special a eas such as he s ai s. The o al
numbe o pseudo s a es is 125, which has o be compa ed o he numbe o 81 egula s a es.
In he expe imen s we assume ha a use canno mo e as e han 3 m/s. Use mo emen
is simula ed by a andom walk on he HMM g aph. Since mo emen ec o s and RSSI mea-
su emen s a e gene a ed e e y 1,5 s, only a limi ed numbe Uo HMM s a es can be eached
om any gi en s a e s −1=i(on he a e age U=15 s a es) and he co esponding ansi ion
p obabili y P(s =j|s −1=i)is se o 1
U. Fo all s a es ou side his neighbo hood he co e-
sponding ansi ion p obabili ies a e se o ze o.
Table 7.8 p esen s he mean posi ioning e o in me e s, a e aged o e 100 expe imen s,
whe e each expe imen co esponds o a di e en andom walk on he HMM g id o leng h
o abou 200 m. We compa e he pe o mance o he p oposed algo i hm wi h ou ea lie
wo k o [73], which also used RSSI and s ep de ec ion in o ma ion, howe e wi hou he
in oduc ion o pseudo s a es. Using pseudo s a es imp o es he mean posi ioning e o om
1,37 m o 1,02 m. I s ep de ec ion in o ma ion is neglec ed and use posi ioning elies only
on RSSI in o ma ion, a mean posi ioning e o o 1,74 m is ob ained.
7.3.2. Field Da a
The p oposed app oach is also e alua ed wi h he ield da a eco ded in he o ice building
depic ed in Fig. 7.1. In he aining phase, 100 RSSI measu emen s pe posi ion we e collec-
ed and he RSSI dis ibu ion we e es ima ed as desc ibed in Chap e 4. In he online es ing
phase, he sma phone use andomly wen h ough he whole loo a ea o collec he es
da a, i.e., WiFi da a and ine ial senso da a. Two di e en ajec o ies we e eco ded, each
ajec o y consis s o app oxima ely 140 es po i ions. The posi ion es ima e was pe o med
e e y 1,5 s using he p oposed app oach. The s ep de ec ion in o ma ion is modeled in he
same ashion as in he expe imen s using a i icial da a.
Acco ding o he ob ained da a and expe imen al esul s, i seemed ha he s ep de ec-
ion in o ma ion is mo e eliable han he RSSI in o ma ion, as a consequence, a heu is ic
Expe imen al Resul s on Indoo Posi ioning
64
weigh ing ac o λwas in oduced in he calcula ion o he o wa d a iable as ollows
α (j) = [p(o |s =j)]λX
i
[p( |s =j, s −1=i)](1−λ)P(s =j|s −1=i)·α −1(i).(7.2)
Fo he de e mina ion o λa jackkni e p ocedu e was employed: The da a o 1ou o he 2
ajec o ies was used o he es ima ion o λ, whe eas es s we e conduc ed on he held-ou
da a. This was epea ed 2 imes, e e y ime, one ajec o y was used o es ima e λ. Wi h
ou collec ed da a, he es ima ed alue was always λ≈0.003. The e y small alue o λ
can be explained as ollows: since he likelihood o RSSI da a is much smalle han he
likelihood o s ep de ec ion in o ma ion, his alue o λwould help o a oid he p oblem
ha he con ibu ion o he likelihood o s ep de ec ion in o ma ion o he calcula ed o wa d
a iable is domina ed by he likelihood o RSSI da a.
The p oposed me hod was compa ed o ou ealie wo k: i s , using RSSI only o use
posi ioning [74], and second, using HMM model as desc ibed in Chap e 6, howe e wi hou
he in oduc ion o pseudo s a es [73]. Fo bo h ajec o ies he expe imen al esul s showed
ha he new app oach ou pe o ms he o he s, especially o he 90% e o quan ile, in e ms
o he CDF o he posi ioning e o Eq. (7.1).
Al hough he es a ea is limi ed, he expe imen al esul s in Fig. 7.5 indica e ha he
p oposed app oach is signi ican ly be e han he o he app oaches.
RSSI only
RSSI + S ep De .
RSSI + S ep De . + Pseudo S a es
CDFǫ(d)
Dis ance d[m]
0 1 2345 6 78 9 10
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figu e 7.5.: CDF o he posi ioning e o o di e en sys ems. A e age o e 2 es ajec o ies.
8. Se e Based Indoo Na iga ion
Sys em
Na iga ion Se e
Clien s
Figu e 8.1.: Se e based Indoo Na iga ion Sys em.
Toge he wi h de eloping heo e ical algo i hms o he enhancemen o posi ioning accu-
acy, a eal indoo na iga ion sys em has been de eloped o o e a pe iod o h ee yea s wi h
he con ibu ions om many employees and s uden s a he Depa men o Communica ions
Enginee ing, Uni e si y o Pade bo n. The sys em is he esul o ou a emp o b ing he
heo e ical esea ch esul s in o eali y.
Be o e building he indoo na iga ion sys em, one needs o answe he ques ion: Which
c i e ia mus he sys em mee ? To ou unde s anding, he mos impo an c i e ia o e alua e a
eal sys em a e cos s, ease o deploymen , s abili y, secu i y, scalabili y and main ainabili y.
The be e he c i e ia a e ull illed, he be e he sys em is. Sys em a chi ec u e has he mos
impo an impac on hose c i e ia. As a consequence, o achie e he equi ed c i e ia he
bes , di e en sys em a chi ec u es ha e been analysed. The e exis wo common a chi ec u-
es o posi ioning sys ems: Fi s , sma phone based sys em in which all da a a e s o ed and
p ocesses a e pe o med on he sma phone i sel , e.g., he solu ions om WIFARER [77],
65
Se e Based Indoo Na iga ion Sys em
72
ma ke id
lon
la
oom
laye
e
ma ke loca ions
connec ionid
ma ke id
linkedma ke
dis ance
highway
access
ma ke connec ions
Table 8.1.: Map in o ma ion ables in he da abase: s o age o he geog aphical in o ma ion o in-
ge p in posi ions, and he in o ma ion abou he di ec connec ion be ween any pai o
posi ions.
we decided o combine all he sepe a e OSM map iles in o one global OSM map ile. The
na iga ion da abase is hen buil up by impo ing he in o ma ion om he global map ile o
he Pos GIS da abase.
The ende ed map iles a e s o ed on he se e and deli e ed o he clien s o map dis-
playing pu poses once he se e ecei es map eques s om clien s. Map in o ma ion s o ed
in he na iga ion da abase is he in o ma ion o inge p in ing posi ions and he connec ions
among hose. This in o ma ion is ga he ed om he s anda d ables by a C++ p og am and
s o ed in wo new ables (see Table 8.1 o an illus a ion). The bold ields a e he so-called
unique keys o mas e keys o he ables. Table ma ke loca ions con ains all he in-
o ma ion abou any inge p in ing posi ion such as longi ude, la i ude, oom numbe , laye
( loo le el) and e (co ido , oile , ec .). These inge p in ing posi ions a e he posi ions
whe e aining da a will be collec ed. I is e y con enien o dis ibu e he aining posi ions
du ing he map edi ing p ocedu e since one can choose he c i ical and in e es ing poin s on
he maps o ma k hem as inge p in ing poin s. I is also easy o manage he densi y o he
inge p in g id. Table ma ke connec ions con ains he in o ma ion abou he di ec
connec ion be ween any pai o posi ions, e.g., ID o cu en conside ed posi ion (ma ke id),
ID o he connec ed posi ion (linkedma ke ), spa ial dis ance be ween hese posi ions (di-
s ance), ype o connec ion (highway), i.e., oo way o bicycle, and accessibili y in o ma ion
(access) o indica e whe he he connec ion is blocked o i he e is ee access. The in o ma-
ion in Table ma ke connec ions is needed o he ou e es ima ion p ocedu e and he
employmen o he HMM which was discussed in Chap e 6.
8.2.2. RSSI da a
RSSI da a a e di ided in o wo ypes: aw da a (RSSI measu emen s) and p ocessed da a
( he es ima ed aining models). Table 8.2 shows he ables in he da abase which s o e he
measu emen da a. The e a e se e al easons o s o ing he aw da a. Fo example, aw da a
can be used o u u e esea ch, i.e., i new algo i hms a e used o es ima e he aining model
om measu ed da a, o o compa ison pu poses, i.e., e alua ing he posi ioning accu acy o
o he algo i hms on he same da a se . By s o ing he aw da a in he way as desc ibed in
Table 8.2, i is possible o e-gene a e he o iginal measu emen s. Tables scan esul s,
measu emen s and ha dwa ein o ma ion a e used oge he o s o e he RSSI mea-
su emen s, he posi ion, ID and o ien a ion o he de ice, and he ime s amp o he measu-

Se e Based Indoo Na iga ion Sys em
73
scanid
measu emen id
mac
ssi
scan esul s
measu emen id
lon
la
laye
hwid
o ien a ion
measu emen ime
measu emen s
hwid
modelid
uniqueid
ha dwa ein o ma ion
Table 8.2.: Measu emen ables in he da abase: con ain he RSSI measu emen s, he posi ion, ID and
o ien a ion o he de ice which has been used o collec da a, and he ime s amp o he
measu emen s
pa ame e id
ma ke id
macid
numbe o measu emen
numbe o obse a ion
mean
a iance
a e
sumo obse a ions
sumo squa e
upda ed ime
pa ame e s
macid
bssid
macadd esses
Table 8.3.: T aining model in o ma ion ables in he da abase: con ain he es ima ed pa ame e s and
he su icien s a is ics in o ma ion.
emen s. The in o ma ion abou he sma phone ha dwa e is s o ed o suppo he adap a ion
p ocedu e as desc ibed in chap e 5.
In addi ion o s o ing he aw da a, he RSSI da abase also con ains he ables o s o e he
in o ma ion o he es ima ed aining models as well as he su icien s a is ics in o ma ion
as depic ed in Table 8.3. Table pa ame e s s o es he es ima ed pa ame e s as well as
he su icien s a is ics in o ma ion. The es ima ed pa ame e s a e he means, a iances and
a e (d opping a e) o he obse ed RSSI da a o he AP, speci ied by macid, a a loca i-
on, speci ied by ma ke id. Su icien s a is ics pa ame e s such as numbe o measu emen s,
numbe o obse a ions, sum o obse a ions and sum o obse a ions squa ed, a e used o
inc emen ally upda ing he aining model o educe he es ima ion ime using he EM algo-
i hm. Ob iously, es ima ion ime is no a se ious p oblem when he amoun o aining da a
is small. Howe e , aining da a a e collec ed o e he cou se o ime and model es ima i-
on om sc a ch would ake much mo e ime han applying he inc emen al upda e me hod.
Fo con enience o AP sea ching, he able macadd esses is c ea ed o s o e he MAC
add esses o all he obse ed access poin s.
Se e Based Indoo Na iga ion Sys em
74
8.3. Sha ed Memo y
As men ioned abo e, sha ed memo y is used o ep esen he da abase in o de o speed up
he da a eading p ocedu e. The s uc u e o he da a s o ed in sha ed memo y is simila o he
s uc u e used in he Pos GIS da abase as p esen ed in he p e ious sec ion. Sepe a e sha ed
memo y a eas a e c ea ed o s o e he in o ma ion o inge p in ing posi ions, connec ions,
MAC add esses and ained models. In addi ion, o speed up he localiza ion p ocedu e,
o he a eas a e c ea ed o s o e he in o ma ion o he p e-compu ed posi ions a which a
gi en MAC add ess was obse ed in he aining da a. The eason is ha in inge p in ing
based posi ioning, online measu ed da a a e compa ed wi h he aining da a in he da abase
o come up wi h he decision o he use posi ion es ima e. Ob iously he bigge he da abase
becomes, he mo e compu a ion ime is needed o comple e he compa ison p ocedu e. To
ge id o his p oblem, ins ead o compu ing he simila i y be ween he online measu emen
wi h he whole da abase, he localiza ion module has o compu e i a he possible posi ions
only, whe e a leas one o he APs, which is p esen in he online measu emen , was obse ed
in he aining da a.
8.4. O e iew o Sma phone Applica ion
This sec ion p esen s an o e iew o he sma phone applica ion. Al hough he de eloped
applica ion is able o suppo many asks, e.g., da a ga he ing, localiza ion, na iga ion, social
ea u es (pee g oup inding) and 3-D ep esen a ion o he ou ing pa h, in he ollowing,
only he s uc u e which is ela ed o he main ea u es, which a e localiza ion and na iga ion,
is p esen ed.
Fig. 8.5 gi es an o e iew o he educed e sion o he sma phone applica ion a chi ec-
u e as a class diag am.
I should be no ed ha in Fig. 8.5, he de ails o each class, i.e., a iables and me hods, a e
no p esen ed since his would ex emely ex end he size o he g aph. In he ollowing, he
ole o each class in he applica ion and he ela ion o classes will be summa ized.
As can be seen in Fig. 8.5, besides he egula classes, he e a e se e al special ypes o
classes in an And oid applica ion such as ac i i y, se ice, applica ion which ope a e di -
e en ly [72] as summa ized below:
•Ac i i y: An ac i i y is an applica ion componen ha p o ides a single window wi h
a use in e ace ha in e ac s wi h he use s in o de o do an ac ion. An applica ion
may consis o se e al ac i i ies o handle di e en asks. An ac i i iy can s a ano-
he ac i i y. Once a new ac i i y s a s, he p e ious ac i i y is s opped. The sys em
p ese es he p e ious ac i i y in a “las in, i s ou ” s ack. The e o e, when he use
is done wi h he cu en ac i i y and p esses he “Back” bu on o he sma phone, he
p e ious ac i i y will esume.
•Se ice: A se ice is an applica ion componen ha can ope a e in he backg ound
and does no p o ide a use in e ace. A se ice can be s a ed by ano he applica ion
componen , i.e., ac i i y, and keeps unning in he backg ound e en i he use swi ches
o ano he applica ion. Se e al ypes o se ice implemen a ion can be used o manage
Se e Based Indoo Na iga ion Sys em
75
Figu e 8.5.: Class diag am o Ja a applica ion a chi ec u e
he li ecycle o a se ice ha he se ice may s op i sel when i comple es he ask o
i s binding componen s ops o an ac i i y s ops i .
•Applica ion: An applica ion is a base class o main ain global applica ion s a e.
In ou applica ion, he main ac i i y is “Indoo Na Map” which is launched when he use
s a s he applica ion. All o he ac i i ies, i.e., WiFi scanning, se ing, e c., can be ac i a ed
om his ac i i y, see he mani es ile o he applica ion in Appendix A.3.1 o in o ma ion
o all ac i i ies. Fig 8.6 shows a snapsho o he applica ion when i is launched by he use s.
In he ollowing discussion, he ela ion be ween he classes in Fig. 8.5 and he ole o
each class a e summa ized:
•“Indoo Na Map” uses he se ing in o ma ion and ini ialized in o ma ion s o ed in
“MapSc ollApplica ion” and he app op ia e me hods implemen ed in “CellMapSu a-
Se e Based Indoo Na iga ion Sys em
76
Figu e 8.6.: Ja a applica ion showing loo plan in o ma ion and use posi ion ( ed do ).
ceView” o display map and o he in o ma ion such as cu en use posi ion, na iga ion
pa h, e c. .
•“MapSc ollApplica ion”, he applica ion class, is implemen ed o main ain all he glo-
bal s a es and he da a which a e needed o map displaying, o line localiza ion, na i-
ga ion, and so on. Fo map d awing, posi ioning and na iga ion, “MapSc ollApplica i-
on” s o es he me ada a o map da a, i.e., objec s o “Map” and “MapTile” classes, and
he in o ma ion o localiza ion and na iga ion pu poses, i.e., “Bina yModel“, ”Ma-
cObjec “, ”NodeObjec “ and ”Rou ingPa hElemen “, as descibed in sec ion 8.2.
•“CellMapSu aceView” ex ends he “Su aceView” class p o ided by And oid APIs,
and con ains all me hods o manage map d awing and use in e ac ion.
•“ISe e Connec ion” is he in e ace decla ing all he me hods which a e implemen-
ed in “H pSe e Connec ion” o suppo he communica ion p ocedu e be ween he
applica ion and he se e . These me hods can be called by “Indoo Na Map” o da a
downloading o by “Localiza ionSe ice” in case o doing localiza ion in online mode.
•As all he messages a e in he p e-de ined XML o ma , me hods o w i ing/pa sing
da a o/ om XML o ma messages a e implemen ed in “XmlW i e ” and “XmlRea-
de ” o communica ing wi h he se e .
•“Localiza ionSe ice” is he se ice o handling he asks ela ed o he localiza i-
on p ocedu e. This se ice is s a ed by “Indoo Na Map” and calls he me hods im-
plemen ed in “Localiza ionManage ” o pe o m localiza ion. This se ice is s opped
au oma ically by he sys em once he use e mina es he applica ion.
•“Indoo Na MapB oadcas Re ei e ” and “Localiza ionSe iceB oadcas Recei e ” a e
implemen ed o suppo he da a exchange be ween “Localiza ionSe ice” and “In-
doo Na Map”. These wo classes ex end he “B oadcas Recei e ” p o ided by he
And oid APIs.
•“WiFiScanne ” is esponsible o WiFi da a acquisi ion o localiza ion p ocedu e.
Se e Based Indoo Na iga ion Sys em
77
•“Rou eCalcula e” con ains all he me hods ela ed o na iga ion pa h calcula ion. The-
se me hods a e ac i a ed by “Indoo Na Map” ia “MapSc ollApplica ion” whe e he
in o ma ion o he calcula ed ou e is s o ed. By doing his, i he use swi ches o any
o he ac i i ies o applica ions, once use ge s back o he “Indoo Na Map” ac i i y,
he na iga ion pa h will be displayed wi hou e-calcula ion. Mo e de ails abou he
na iga ion p ocedu e will be p esen ed in sec ion 8.5.3.
8.5. Sys em Ope a ion
This sec ion p esen s he ope a ion o he main ea u es o ou indoo posi ioning sys em
om a use ’s iew, as well as he low sequence o he sma phone applica ion o each
ea u e. The de eloped indoo na iga ion sys em is able o suppo se e al se ices such as
ga he ing o aining da a, localiza ion, na iga ion, some ini ial e sions o social ea u es
such as pee g oup inding, and 3-D ep esen a ion o he ou ing pa h. The main ea u es,
i.e., ga he ing o aining da a, localiza ion, and na iga ion, a e discussed in de ail, a sho
in oduc ion abou he o he ea u es is gi en a he end o he sec ion.
8.5.1. Da a Ga he ing
This ea u e is esponsible o ga he ing aining da a. To do his, he sma phone applica ion
pe o ms WiFi scans and w i es he measu ed da a o a “Se Finge p in Reques ”. I should
be no ed ha on he sma phones, a he momen , his ea u e is only a ailable when he
applica ion uns in he de elopmen mode in o de o a oid p oblems in case someone ies
o ha m he da abase. In u u e, o ex ending he sys em owa ds online lea ning, his ea u e
could be pe o med in he backg ound o he sma phone applica ion du ing he usage by
use s. The de elopmen mode is ac i a ed by he de elope s by choosing he op ion “Ac i a e
de elope iew”, as shown in Fig. 8.7.
Figu e 8.7.: Ja a applica ion showing se ing op ions.
The de elopmen iew o he sma phone applica ion is illus a ed in Fig 8.8. In he igu e,
he ed ci cles indica e he posi ions a which RSSI aining da a ha e al eady been collec ed.

Se e Based Indoo Na iga ion Sys em
78
By doing so, he de elope s can hen choose he inge p in posi ions which ha e no been
ained o collec RSSI da a. The ed “+” sign on he map shows he posi ion whe e WiFi
da a a e going o be collec ed. The de elope s can modi y he posi ion o he ed “+” sign
by mo ing he map. To collec he RSSI da a, since each posi ion needs a su icien amoun
o measu emen s o accu a ely es ima e aining models, an ac i i y named “WLANDa aAs-
semble Ac i i y” was de eloped o suppo his equi emen .
Figu e 8.8.: Ja a applica ion showing he de elopmen mode: he ed ci cles a e he posi ions whe e
aining da a we e al eady collec ed, he ed “+” sign on he map shows he posi ion
whe e WiFi da a a e going o be collec ed.
Once he de elope s a s he da a ga he ing p ocedu e, a window appea s which allows
he de elope o e i y he in o ma ion o he cu en posi ion and en e addi ional in o ma-
ion, i.e., name o he posi ion, amoun o scans and scan in e al, see Fig. 8.9(a). Depending
on he sampling a e o he WiFi senso o he es sma phone, he scan in e al need o be
la ge enough o a oid duplica ion o he measu emen da a, We obse ed he su icien scan
in e al o abou 1,5 s o Samsung sma phones, while o a Sony de ice i is oughly 5 s.
Once he in o ma ion is alida ed and en e ed, he measu emen p ocess will be s a ed by
simply clicking he “S a scan” bu on. Fig. 8.9(b) shows he sc eensho when he sma pho-
ne pe o ms a WiFi scan, whe e he numbe o measu emen s and scanned da a a e shown.
The measu ed da a a e hen w i en in o an XML ile which is s o ed on he local s o age o
sma phone once he scanning p ocedu e is comple ed. The XML ile con ains he measu ed
RSSIs, MAC add esses o he obse ed APs, he sma phone in o ma ion, as well as he
in o ma ion o he loca ion whe e he measu emen s a e aken. I should be no ed ha each
XML ile con ains he aining da a a one posi ion only.
A e he measu emen campaign, all XML iles a e impo ed in o he da abase on he se -
e using a C++ module named se inge p in . This module pa ses he eques and accesses
he Pos GIS da abase o inse he measu ed da a. Fo each ile, se inge p in p oduces a
esponse message o in o m whe he he da a a e success ully inse ed o he da abase o no .
Appendix A.4.1 shows an example o he “Se Finge p in Reques ” and esponse messages.
Ou sys em is also able o suppo he online mode o he measu emen campaign, i.e., he
measu ed da a a e sen di ec ly o he se e a e each measu emen ia a wi eless ne wo k,
Se e Based Indoo Na iga ion Sys em
79
(a) Se ing o WiFi scan (b) WiFi scanning
Figu e 8.9.: WiFi aining da a ga he ing
i we use he se inge p in module as a Fas CGI module. This op ion p o ides he possibi-
li y o ga he ing da a du ing he usage o use s o an online lea ning app oach. Howe e , a
he momen , no algo i hm has been de eloped o measu e he eliabili y o a measu emen .
The e o e, we empo a ily disable his op ion o a oid acciden al measu emen s con aining
w ong in o ma ion which may ha m he da abase. The indoo en i onmen and WLAN ne -
wo k a e subjec o change o e ime, his equi es egula da abase main enance (upda e) o
keep he posi ioning accu acy. I is in easible o e ain he da abase a e e e y change o he
en i onmen o he ne wo k in as uc u e. The eason is collec ing aining da a is e y ime
consuming, especially o he la ge deploymen a ea. The e o e, a me hod o au oma ically
upda ing da abase, i.e., he online lea ning app oach, could be a solu ion.
The sequence diag am o Fig. 8.10 shows how he sma phone applica ion pe o ms WiFi
scanning in o line mode, i.e., he scanned da a a e w i en in an XML ile and s o ed in he
local s o age o he sma phone.
8.5.2. Localiza ion
Fo localiza ion, use s can choose ei he he o line localiza ion mode o he online localiza-
ion mode in he se ings o he sma phone applica ion . In o line mode, posi ion es ima ion
is pe o med locally on he sma phone using he da abase which is s o ed on i s local s o-
age wi hou any need o in e ne connec ion. In online localiza ion mode, which equi es
ne wo k connec ion o da a exchange, posi ion es ima ion is pe o med on he se e . Figu-
e 8.11 shows he op ions o localiza ion, i.e., ope a ion mode and he da a sou ce.
The sequence diag ams shown in Fig. 8.12 and Fig. 8.13 p esen he communica ion
among he componen s o he sma phone applica ion o pe o m localiza ion in o line mode
and online mode using WiFi in o ma ion, espec i ely.
To pe o m he localiza ion using WiFi da a, sma phones pe iodically log he WiFi da a
which a e he MAC add esses o he obse ed APs and hei measu ed RSSIs. An es ima o
is hen used o p ocess he scanned da a o de e mine he use posi ions In o line localiza-
Se e Based Indoo Na iga ion Sys em
80
Figu e 8.10.: Sequence diag am showing he da a ga he ing p ocedu e.
ion, he es ima o is implemen ed as a me hod in he sma phone Ja a applica ion which
uses he local da abase o compa e wi h obse ed da a. Se e al issues may a ise in o line
localiza ion, o example, he local da abase o he posi ioning algo i hms migh be ou o
da e, as discussed in he beginning o his chap e . To sol e his p oblem, he local RSSI
da abase can be eloaded om se e egula ly, i.e., once a week, au oma ically o manually
i ne wo k connec ion is a ailable. The p oblem wi h posi ioning algo i hms is unsol able
unless he use upda es he applica ion. Wi hin his wo k, an au oma ic upda e p ocedu e o
sma phone applica ion has no been de eloped ye .
Fo online localiza ion, scanned da a a e sen o he se e ia he WLAN connec ion in an
XML o ma . On he se e , a Fas CGI module named “posi iones ima e” was de eloped o
pa se he eques and pe o m he localiza ion p ocedu e. The posi ion es ima ion algo i hm
was implemen ed using he classi ica ion ule which was discussed in Chap e 4, he same
algo i hm is used o o line localiza ion. This module uses he aining models s o ed in he
sha ed memo y o ca y ou he localiza ion p ocedu e.
Senso usion o he imp o emen in posi ioning accu acy as discussed in Chap e 6, is
no implemen ed on he se e side, bu on he clien side. The eason is ha he se e mus
be a s a eless se e since he e would be an explosion o he amoun o HMM s a es which
need o be s o ed i many clien s eques he localiza ion se ice a he same ime using RSSI
Se e Based Indoo Na iga ion Sys em
81
(a) Se ing op ions (b) Localiza ion modes
Figu e 8.11.: Se ing sc een showing op ions o localiza ion.
and s ep de ec ion in o ma ion. This would d ama ically deg ade he esponse ime o he
se e .
Once he posi ion es ima e is ob ained, a localiza ion esponse is sen om he se e o
he clien which con ains he in o ma ion o he es ima ed use posi ion. The clien pa ses he
esponse and shows he use loca ion on he sma phone sc een, see Fig. 8.6 whe e he ed
do ep esen s he cu en use posi ion.
8.5.3. Na iga ion
Fo na iga ion pu pose, he use can inpu he in o ma ion o he sou ce and des ina ion
posi ions, i.e., oom numbe s, and he op ions o he expec ed ou e, i.e., using ele a o s o
s ai s. Fig. 8.14 shows an example o a sma phone sc een when he use s a s he ou ing
unc ion o he sma phone applica ion.
Na iga ion, simila o localiza ion, can be pe o med in ei he o line mode o online mo-
de. In online mode, a na iga ion eques wi h he in o ma ion inse ed by he use is gene a ed
by he sma phone applica ion and sen o he emo e se e . On he se e , a Fas CGI modu-
le named “ ou ees ima e” was de eloped which is able o pa se he eques and pe o m he
ou e calcula ion. Da a o he ou e calcula ion p ocess a e ob ained by eading he sha ed
memo y. To pe o m he pa h sea ch, se e al pa h inding algo i hms ha e been conside ed
such as he well known Dijks a’s algo i hm, he A* algo i hm (a a ian o Dijks a’s algo-
i hm) and he jump poin algo i hm. In na iga ion, he pa h cos is simply he geog aphical
dis ance o any pai o connec ed posi ions. While Dijks a’s algo i hm examines all nodes
o ind he sho es pa h be ween he sou ce and he des ina ion, he A* algo i hm is ying o
examine he nodes which a e po en ially on he sho es pa h i s o op imize he compu a io-
nal demand. This is he eason why he A* is also called goal-o ien ed Dijks a’s algo i hm.
Howe e , he A* algo i hm needs heu is ic weigh s o gua an ee he solu ion is he sho es
pa h. The jump poin algo i hm ies o op imize A* in case o uni o m-cos g ids, which is
no mally no sui able o an indoo en i onmen since dis ibu ing he indoo inge p in ing
9. Conclusions
Wi hin his hesis, he echniques o imp o e he accu acy o WiFi inge p in ing based in-
doo posi ioning a e p esen ed.
The accu acy o indoo posi ioning employing WLAN in o ma ion can be enhanced by a
s a is ical app oach which is able o accoun o he a ia ion o he measu ed RSSIs in he
indoo en i onmen . The posi ioning accu acy depends on wo ac o s: aining models and
classi ica ion ule. As ou ca e ul s udy on WiFi da a in indoo en i onmen showed, RSSI
measu emen s su e om wo p oblems namely censo ing and d opping. As discussed in
chap e 2 and chap e 4, hese wo p oblems o he indoo WiFi da a ha e no been add essed
in any p e ious esea ch. The e o e, wi hin his wo k, me hods o es ima ing he pa ame e s
o he aining model and classi ica ion in he p esence o censo ed and d opped da a we e
p oposed. Fo pa ame e es ima ion, an EM algo i hm was p oposed in chap e 4 which e -
icien ly copes wi h he censo ing and d opping p oblem. The p oposed EM algo i hm o
censo ed Gaussian da a was p o ed o be a i ually bias ee and e icien es ima o . Imp o-
emen s in posi ioning accu acy a e demons a ed bo h on a i icially gene a ed da a and in
eal ield da a expe imen s compa ed o some o he app oaches. The expe imen s p esen ed
in chap e 7 showed he supe io i y o he s a is ical app oach compa ed o a de e minis ic
app oach. I is no ed ha he compu a ional demand o posi ioning using a pa ame ic s a i-
s ical app oach is less han he o he men ioned app oaches.
Ano he p oblem ha has been conside ed in his wo k is he misma ch be ween he mea-
su ed da a o he aining de ice and he es de ices as discussed in chap e 5 which leads o
a se ious educ ion o he posi ioning accu acy. In he li e a u e, we ound only one solu ion
which ied o add ess his p oblem using Leas Squa es app oach whe e he au ho s ass-
umed a linea ela ionship be ween he RSSI eadings o di e en de ices. Howe e , wha
we obse ed is ha his ela ion is no linea which ende s he LS app oach inapp op ia-
e. An e ec i e me hod o cope wi h his p oblem mus be de eloped o make WiFi signal
based indoo posi ioning ealis ic. The e o e, we p oposed a me hod o aligning he ai-
ning model wi h he p ope ies o he es de ices while elaxing he linea i y assump ion in
chap e 5. The p oposed aligning me hod called “sma phone adap a ion” was de eloped wi-
hin he MLLR amewo k which is a e y well known and success ul echnique o speake
adap a ion in au oma ic speech ecogni ion. I has o be no ed ha he p oposed adap a ion
me hod is able o cope wi h censo ed and d opped da a in he adap a ion da a, esul ing in
eliable adap ed models. Du ing he adap a ion p ocedu e, he d opping a e o he adap a-
ion da a is also es ima ed which will be used in he classi ica ion p ocedu e. Expe imen al
esul s p esen ed in chap e 7 demons a ed he e ec i eness o doing adap a ion in indoo
posi ioning. Assuming he RSSI eadings om di e en de ices ollow one linea ela ion-
ship, applying he p oposed app oach showed a big imp o emen in posi ioning accu acy,
howe e , s ill well a below he achie able accu acy. Employing clus e ing app oach be o e
88

Conclusions
89
doing adap a ion elaxed he linea i y assump ion esul ing in assuming piecewise linea i y.
As a esul , be e posi ion accu acy was ob ained.
Imp o emen s in posi ioning accu acy can be ob ained by using he in o ma ion om di -
e en sou ces such as WiFi in o ma ion and ine ial senso in o ma ion. These wo kinds o
in o ma ion a e ob ainable on mos mode n sma phones. Ine ial na iga ion which u ilizes
he da a om he buil -in senso s o he sma phones is able o p oduce p ecise posi ion es i-
ma ion in a sho e m ( ime and dis ance) only. Un o una ely he p ecise posi ioning esul s
canno be main ained o a longe pe iod o ime due o e o accumula ion o e ime and
dis ance, esul ing in un eliable posi ion es ima es. WiFi inge p in ing based posi ioning,
on he o he hand, can p o ide a s able posi ioning accu acy wi hou he e o accumula ion
p oblem. As discussed in chap e 2, hese wo posi ioning echniques can be combined in
o de o p oduce be e posi ioning esul s compa ed o using any indi idual app oach alone.
The e o e, chap e 6 p esen ed a modi ied HMM o da a usion o WiFi da a and ine ial
senso da a and u ilizing he possible walking pa h o he use o come up wi h posi ion es i-
ma es. Mo e accu a e posi ioning esul s we e ob ained by employing HMM in compa ison
wi h using WiFi in o ma ion o ine ial senso in o ma ion alone. Fu he mo e, a me hod o
educe he quan iza ion e o caused by he coa se g id o ained posi ions was p oposed in
chap e 6. By in oducing pseudo s a es o he HMM inbe ween he egula s a es and syn-
hesizing he emission PDFs o he pseudo s a es om hose o neighbo ing egula s a es,
we ob ained a dense g id o s a es wi hou addi ional aining e o . Expe imen al esul s
showed ha employing he ex ended HMM imp o ed he posi ioning accu acy.
In addi ion o he heo e ical esea ch, a eal se e based indoo posi ioning and na iga-
ion sys em was de eloped as p esen ed in chap e 8. A he momen he sys em is able o
p o ide he localiza ion and na iga ion se ices o he s uden s o he Uni e si y o Pade -
bo n. The sys em employs he ligh pd web se e and he Fas CGI p o ocol which allows
o handle housands o connec ions in pa allel on he se e . In addi ion, he Fas CGI mo-
dules, which a e w i en in C++, un in sepe a e p ocesses which make he sys em s able,
and u he , easy o scale and easy o main ain. A Ja a applica ion o And oid sma pho-
nes was de eloped which is able o un as a s andalone posi ioning sys em o as a clien
in he sys em. As discussed in chap e 8, de eloping wo possible ope a ion modes o he
sma phone applica ion sol es he p oblem o loss o in e ne connec ion, unsynch oniza ion
o map da a and inge p in ing aining model, and so on. As a esul , he sys em seems o
sa is y he equi emen s o low cos , high obus ness and simplici y in deploymen , scaling
and main enance.
Ou look
An in e es ing di ec ion o u u e esea ch is how o imp o e/upda e he adio map wi h he
measu ed da a epo ed by he use s du ing he online phase. To do ha , a possible solu i-
on is o de elop a semi-supe ised online lea ning sys em whe e he al eady buil da abase
is con inuously upda ed du ing he sys em ope a ion using he measu emen s epo ed by
use s. This kind o sys em can au oma ically handle he changes o he indoo en i onmen
o WLAN in as uc u e wi hou e- aining he da abase om sc a ch a e a ce ain amoun
o ime. This also helps o imp o e he accu acy o he aining model since mo e aining
da a a e a ailable. The challenge is how o de e mine he posi ion whe e he measu emen is
Conclusions
90
aken. The REDPIN sys em belie es in he in o ma ion ha is epo ed om any use s which
does no seem o be aul ole an since he da abase can be co up ed on pu pose o unin-
en ionally h ough w ong use posi ions. Simul aneous Localiza ion And Mapping (SLAM)
is a common app oach in he obo ics communi y which mainly elies on ine ial senso in-
o ma ion o ack he posi ion o a mobile obo and build he map simul aneously. This
app oach can be used o de e mine he posi ion a which a speci ic RSSI measu emen is col-
lec ed. Howe e , as discussed be o e, his echnique su e s om he e o accumula ion o e
ime and dis ance and, as a consequence, es ima ed posi ions a e no eliable. Map ma ching
can be o mula ed as a inge p in ing based localiza ion p oblem whe e he use posi ion is
assigned o a ou e segmen based on he online obse a ion and aining da a. The e o e, he
combina ion o SLAM and map ma ching app oach would be a ele en solu ion o es ima e
he posi ion o he use whe e RSSI measu emen is collec ed since he accumula ed e o in
ine ial na iga ion a e co ec ed globally by RSSI da a and loo plan in o ma ion.
Ou p oposed EM algo i hms p esen ed in chap e 4 a e e icien o es ima ing he pa a-
me e s o censo ed and d opped Gaussian da a. Howe e , we employed he empi ical ixed
clipping h eshold o da a measu ed by all de ices. This migh deg ade he pa ame e es i-
ma ion pe o mance i he clipping h eshold o di e en de ices a e no iden ical. The e o e,
es ima ing clipping h eshold om aining da a should be done be o e pa ame e es ima i-
on p ocedu e o ensu e he p ecision o he es ima ed pa ame e s. As a esul , a me hod o
clipping h eshold es ima ion is needed.
Employing a Gaussian mix u e model es ima ion o es ima e he RSSI dis ibu ion ins ead
o he assump ion o a single Gaussian would be an in e es ing y. This me hod migh help o
imp o e he p ecision o signal s eng h dis ibu ion es ima ion, since i is able o cap u e all
he modes in he aining da a dis ibu ion. Howe e , since censo ing and d opping a e se e e
in WiFi da a, me hods o dealing wi h censo ed and d opped da a du ing he pa ame e
es ima ion p ocedu e would need o be aken in o conside a ion.
A. Appendix
A.1. De i a ion o EM Algo i hm
A.1.1. Compu a ion o I0
I0(θ(κ)) = Zc
−∞ Ny;θ(κ)dy
=Zc
−∞
1
√2πσ(κ)exp −(y−µ(κ))2
2(σ2)(κ)dy(A.1)
Le =y−µ(κ)
√2σ(κ)and change he a iable o he in eg al, we a i e a :
I0(θ(κ)) = 1
√πZc−µ(κ)
√2σ(κ)
−∞
exp(− 2)d (A.2)
Since exp(− 2)is an e en unc ion, he limi s o he in eg al in Eq. (A.2) can be modi ied
by changing hei signs and swapping lowe and uppe limi s, hen I0(θ(κ))can be easily
ob ained by using complemen a y e o unc ion
I0(θ(κ)) = 1
2e c −c−µ(κ)
√2σ(κ)(A.3)
A.1.2. Compu a ion o I1
I1(θ(κ)) = Zc
−∞
yNy;θ(κ)dy
=Zc
−∞
y1
√2πσ(κ)exp −(y−µ(κ))2
2(σ2)(κ)dy(A.4)
Employing he in eg a ion by pa s ule, le
(u=y
d =1
√2πσ(κ)exp −(y−µ(κ))2
2(σ2)(κ)dy⇒(du=dy
=1
2e y−µ(κ)
√2σ(κ),(A.5)
hen we a i e a
I1(θ(κ)) = y1
2e y−µ(κ)
√2σ(κ)
c
−∞ −1
2Zc
−∞
e y−µ(κ)
√2σ(κ)dy
|{z }
=A1
(A.6)
91
Appendix
92
Again in eg a ion by pa s ule is used o compu ing he emaining in egal A1as ollows, o
simpli y he in eg al, le =y−µ(κ)
√2σ(κ),A1can be w i en as
A1=√2σ(κ)Zc−µ(κ)
√2σ(κ)
−∞
e ( )d (A.7)
Le
u=e ( )
d =d ⇒du=2
√πexp (− 2)d
= ,(A.8)
hen we a i e a
A1=√2σ(κ)
 e ( )
c−µ(κ)
√2σ(κ)
−∞ −1
√πZc−µ(κ)
√2σ(κ)
−∞
2 exp − 2d 

=√2σ(κ) e ( ) + 1
√πexp − 2
c−µ(κ)
√2σ(κ)
−∞
(A.9)
Using A1in Eq. (A.6), I1(θ(κ))is eadily ob ained:
I1(θ(κ)) = µ(κ)I0(θ(κ))−1
√2πσ(κ)exp −c−µ(κ)
√2σ(κ)2!(A.10)
A.1.3. Compu a ion o I2
I2(θ(κ)) = Zc
−∞
y2Ny;θ(κ)dy
=Zc
−∞
y21
√2πσ(κ)exp −(y−µ(κ))2
2(σ2)(κ)dy(A.11)
Employing he in eg a ion by pa s ule, le
(u=y2
d =1
√2πσ(κ)exp −(y−µ(κ))2
2(σ2)(κ)dy⇒(du= 2ydy
=1
2e y−µ(κ)
√2σ(κ),(A.12)
hen we a i e a
I2(θ(κ)) = y21
2e y−µ(κ)
√2σ
c
−∞ −Zc
−∞
ye y−µ(κ)
√2σ(κ)dy
|{z }
A2
(A.13)
To compu e A2, in eg a ion by pa s is again applied, le
(u1=y
d 1=e y−µ(κ)
√2σ(κ)dy⇒(du1=dy
1=Re y−µ(κ)
√2σ(κ)dy,(A.14)
Appendix
93
Fo calcula ing 1, le =y−µ(κ)
√2σ(κ)
1=√2σ(κ)Ze ( )d (A.15)
and applying in eg a ion by pa s
u2=e ( )
d 2=d ⇒du2=2
√πexp (− 2)d
2= ,(A.16)
we a i e a
1=√2σ(κ) .e ( )−1
√πZ2 exp − 2d 
=√2σ(κ) .e ( ) + 1
√πexp − 2.(A.17)
Using =y−µ(κ)
√2σ(κ)in 1 hen we ob ain
1=√2σ(κ)y−µ(κ)
√2σ(κ)e y−µ(κ)
√2σ(κ)+1
√πexp −(y−µ(κ)
√2σ(κ))2
= (y−µ(κ))e y−µ(κ)
√2σ(κ)+σ(κ) 2
πexp −y−µ(κ)
√2σ(κ)2!.(A.18)
Now, A2can be calcula ed as ollows
A2=u1 1
c
−∞ −Zc
−∞
1du1
=y((y−µ(κ))e y−µ(κ)
√2σ(κ)+σ(κ) 2
πexp −y−µ(κ)
√2σ(κ)2!)
c
−∞
−Zc
−∞ ((y−µ(κ))e y−µ(κ)
√2σ(κ)+σ(κ) 2
πexp −y−µ(κ)
√2σ(κ)2!)dy
=y((y−µ(κ))e y−µ(κ)
√2σ(κ)+σ(κ) 2
πexp −y−µ(κ)
√2σ(κ)2!)
c
−∞
−Zc
−∞
y.e y−µ(κ)
√2σ(κ)dy
|{z }
A2
+µ(κ)Zc
−∞
e y−µ(κ)
√2σ(κ)dy
|{z }
1c
−∞
−2σ2(κ)Zc
−∞
1
√2πσ(κ)exp −y−µ(κ)
√2σ(κ)2!dy
|{z }
I0(θ(κ))
(A.19)

Appendix
94
Simply using he limi s, A2is eadily ob ained:
A2=1
2y2e y−µ(κ)
√2σ(κ)
c
−∞ −1
2(µ(κ)2 +σ2(κ)).e c−µ(κ)
√2σ(κ)+ 1
−c+µ(κ)σ(κ) 2
πexp −c−µ(κ)
√2σ(κ)2!)
=1
2y2e y−µ(κ)
√2σ(κ)
c
−∞ −(µ(κ)2 +σ2(κ))I0(θ(κ))
+c+µ(κ).σ(κ)1
√2πexp −c−µ(κ)
√2σ(κ)2!(A.20)
Plugging A2in o Eq. (A.13), he calcula ion o I2ends up wi h
I2(θ(κ)) = σ2(κ)+µ2(κ)I0(θ(κ))−1
√2πσ(κ)(µ(κ)+c) exp −c−µ(κ)
√2σ(κ)2!(A.21)
A.1.4. Compu a ion o W En ies
∂
∂µI0(θ) = ∂
∂µ Zc
−∞
p(y;θ)dy
=1
σ2Zc
−∞
(y−µ)p(y;θ)dy
=1
σ2(I1(θ)−µI0(θ)) (A.22)
∂
∂µI1(θ) = ∂
∂µ Zc
−∞
y.p(y;θ)dy
=1
σ2Zc
−∞
y(y−µ)p(y;θ)dy
=1
σ2(I2(θ)−µI1(θ)) (A.23)
∂
∂µI2(θ) = ∂
∂µ Zc
−∞
y2.p(y;θ)dy
=1
σ2Zc
−∞
y2(y−µ)p(y;θ)dy
=1
σ2(I3(θ)−µI2(θ)) (A.24)
∂
∂σ2I0(θ) = ∂
∂σ2Zc
−∞
p(y;θ)dy
=−1
2σ2I0(θ) + 1
2σ4I2(θ)−2I1(θ)µ+I0(θ)µ2(A.25)
Appendix
95
∂
∂σ2I1(θ) = ∂
∂σ2Zc
−∞
yp(y;θ)dy
=−1
2σ2I1(θ) + 1
2σ4I3(θ)−2I2(θ)µ+I1(θ)µ2(A.26)
∂
∂σ2I2(θ) = ∂
∂σ2Zc
−∞
y2p(y;θ)dy
=−1
2σ2I2(θ) + 1
2σ4I4(θ)−2I3(θ)µ+I2(θ)µ2(A.27)
whe e I3(θ)and I4(θ)can be compu ed by using in eg a ion by pa s as he compu a ion o
I2(θ), howe e leng hie compu a ion
I3(θ) = Zc
−∞
y3p(y;θ)dy
=µ3σ2+µ2I0(θ)−1
√2πσ[2σ2+µ2+µc +c2] exp −c−µ(κ)
√2σ(κ)2!(A.28)
I4(θ) = Zc
−∞
y4p(y;θ)dy
= (3σ4+ 6µ2σ2+µ4)I0(θ)
−1
√2πσ[σ2(5µ+ 3c) + µ3+µ2c+µc2+c3] exp −c−µ(κ)
√2σ(κ)2!(A.29)
A.1.5. Compu a ion o In o ma ion Ma ix I
Fo con enience, he log-likelihood unc ion and he in o ma ion ma ix a e ecalled as ol-
lows
ln p(x;θ) = ln N!
M!(N−M)!+ (N−M) ln (I0(θ))
−M
2ln 2πσ2−1
2
M
X
j=1 xj−µ
σ2
.(A.30)
I=
Eh−∂2
∂µ2ln p(x;θ)iEh−∂2
∂µ∂σ2ln p(x;θ)i
Eh−∂2
∂µ∂σ2ln p(x;θ)iEh−∂2
∂σ2∂σ2ln p(x;θ)i
.(A.31)
In he ollowing, o sho en he no a ion, he pa ame e s o he Ij unc ions a e emo ed.
He e he de i a i e compu a ions o he Ijwhich we e gi en in Eq. (A.22) o (A.27) a e em-
ployed. Since I0is he p obabili y ha a measu emen is censo ed, in he ollowing de i a i-
on, he expec ed numbe o uncenso ed measu emen s is de e mined by E [M] = N(1 −I0),
whe e Nis he o al numbe o measu emen s.
Appendix
96
•Eh−∂2
∂µ2ln p(x;θ)i:
Fi s de i a i e o log-likelihood unc ion w. . . µ
∂
∂µ ln p(x;θ) = (N−M)1
I0
∂
∂µI0−1
2
M
X
j=1 −2xj−µ
σ2
= (N−M)1
I0
1
σ2I1−µI0+1
σ2
M
X
j=1
(xj−µ)(A.32)
Second de i a i e o log-likelihood unc ion w. . . µ:
∂2
∂µ2ln p(x;θ) = ∂
∂µ (N−M)1
I0
1
σ2I1−µI0+1
σ2
M
X
j=1
(xj−µ)!
=N−M
σ2
∂
∂µ I1
I0−µ−M
σ2
=N−M
σ2 ∂I1
∂µ I0−I1∂I0
∂µ
I2
0−1!−M
σ2
=N−M
σ21
σ2(I2−µI1)I0−I11
σ2(I1−µI0)
I2
0−1−M
σ2
=N−M
σ4I2I0−I2
1
I2
0−σ2−M
σ2
=N−M
σ4I2I0−I2
1
I2
0−N
σ2(A.33)
Expec a ion o he second de i a i e o log-likelihood unc ion w. . . µ:
E−∂2
∂µ2ln p(x;θ)=E−N−M
σ4I2I0−I2
1
I2
0+N
σ2
=−E[N−M]1
σ4I2I0−I2
1
I2
0+N
σ2
=−NI0
1
σ4I2I0−I2
1
I2
0+N
σ2
=N
σ2I2
1−I2I0
I0
+ 1(A.34)
Appendix
97
•Eh−∂2
∂µ∂σ2ln p(x;θ)i:
∂2
∂µ∂σ2ln p(x;θ) = ∂
∂σ2 (N−M)1
I0
1
σ2I1−µI0+1
σ2
M
X
j=1
(xj−µ)!
= (N−M)∂
∂σ21
σ2I1
I0−µ−1
σ4
M
X
j=1
(xj−µ)
= (N−M)(−1
σ4I1
I0−µ+1
σ2 ∂I1
∂σ2I0−I1∂I0
∂σ2
I2
0!)
−1
σ4
M
X
j=1
(xj−µ)·(A.35)
Expec a ion o he second de i a i e o log-likelihood unc ion w. . . µand σ2:
E−∂2
∂µ∂σ ln p(x;θ)=NI0(1
σ4I1
I0−µ−1
σ2 ∂I1
∂σ2I0−I1∂I0
∂σ2
I2
0!)
+1
σ4E"M
X
j=1
(xj−µ)#,(A.36)
whe e he emaining expec a ion can be compu ed as ollows
E"M
X
j=1
(xj−µ)#=E[M] (E[x]−µ)
=N(1 −I0)1
1−I0Z∞
c
yp(y;θ)dy −µ
=N(1 −I0)1
1−I0
(µ−I1)−µ
=N(µI0−I1).(A.37)
Using his in Eq. (A.36) we a i e a
E−∂2
∂µ∂σ2ln p(x;θ)=N
σ2−
∂I1
∂σ2I0−I1∂I0
∂σ2
I0(A.38)
•E−∂2
∂σ2∂σ2ln p(x;θ):
Fi s de i a i e o log-likelihood unc ion w. . . σ2
∂
∂σ2ln p(x;θ) = (N−M)1
I0
∂
∂σ2I0−M
2
1
σ2−1
2−1
σ4M
X
j=1
(xj−µ)2
= (N−M)−1
2σ2+1
2σ4I2
I0−2µI1
I0
+µ2
−M
2σ2+1
2σ4
M
X
j=1
(xj−µ)2(A.39)
No a ions and Symbols
Gene al No a ions and Func ions
E[·]. . . . . . . . . . . . . . . . Expec a ion
(·)T. . . . . . . . . . . . . . . . T anspose
Q(·). . . . . . . . . . . . . . . Auxilia y unc ion
(·)−1. . . . . . . . . . . . . . . In e sion
ln(·). . . . . . . . . . . . . . . Na u al loga i hm unc ion
p(x|ℓk). . . . . . . . . . . . . Class condi ional p obabili y densi y unc ion
δ(·). . . . . . . . . . . . . . . . Di ac del a unc ion
e (·). . . . . . . . . . . . . . E o unc ion
e c (·). . . . . . . . . . . . . Complemen a y e o unc ion
N(θ). . . . . . . . . . . . . . Gaussian dis ibu ion pa ame e ized by θ
p(x;θ). . . . . . . . . . . . . P obabili y densi y unc ion pa ame e ized by θ
P. . . . . . . . . . . . . . . . . Summa ion o a sequence
Q. . . . . . . . . . . . . . . . . P oduc s o a sequence
(.)! . . . . . . . . . . . . . . . . . Fac o ial o a non nega i e in ege
Fundamen als o Indoo Posi ioning and S a e o Resea ch
R. . . . . . . . . . . . . . . . . . Ma hema ical exp ession o adio map in inge p in ing based ech-
niques
ℓk. . . . . . . . . . . . . . . . . . Vec o consis s o coo dina es o he k- h posi ion
Fk. . . . . . . . . . . . . . . . . Finge p in a he k- h posi ion
Xk. . . . . . . . . . . . . . . . . Se o measu emen ec o s a he k- h posi ion
xk,n ................ Then- h measu emen ec o a he k- h posi ion
D(o,xk,n). . . . . . . . . . Euclidian dis ance be ween online sample oand aining sample
xk,n
θk. . . . . . . . . . . . . . . . . . Se o he pa ame e s o he Gaussian desc ibing he signal s eng h
dis ibu ion a he k- h posi ion
µk. . . . . . . . . . . . . . . . . Mean ec o o he Gaussian desc ibing he signal s eng h dis i-
bu ion a he k- h posi ion
Σk. . . . . . . . . . . . . . . . . Co a iance ma ix o he Gaussian desc ibing he signal s eng h
dis ibu ion a he k- h posi ion
104

No a ions and Symbols
105
Pa ame e Es ima ion o Censo ed and D opped Gaussian Da a
c. . . . . . . . . . . . . . . . . . . Clipping h eshold
Θ. . . . . . . . . . . . . . . . . . Se o pa ame e s o a GMM
πk. . . . . . . . . . . . . . . . . Mixing weigh o he k- h componen o a GMM
θk. . . . . . . . . . . . . . . . . . Se o he pa ame e s o he k- h componen o a GMM
X. . . . . . . . . . . . . . . . . . Se o obse able da a
Z. . . . . . . . . . . . . . . . . . Se o hidden a iables
y. . . . . . . . . . . . . . . . . . Se o unobse able, non-censo ed, possibly d opped da a
yn................. Then- h measu emen , scala alue
x. . . . . . . . . . . . . . . . . . Se o obse able da a
θ. . . . . . . . . . . . . . . . . . . Se o he pa ame e s o a uni a ia e single Gaussian
µ. . . . . . . . . . . . . . . . . . Mean o a uni a ia e single Gaussian
σ. . . . . . . . . . . . . . . . . . Va iance o a uni a ia e single Gaussian
θ(κ). . . . . . . . . . . . . . . . Se o he es ima ed pa ame e s o a uni a ia e single Gaussian a e
he κ- h i e a ion o an EM algo i hm
Ijθ(κ)............ Thej- h momen o he unca ed pa o a censo ed Gaussian, de-
ined in Eq. (4.8)
zn. . . . . . . . . . . . . . . . . . Realiza ion o he bina y andom a iable Znindica e whe he he
n- h measu emen is censo ed (zn= 1) o no (zn= 0)
N. . . . . . . . . . . . . . . . . . Numbe o measu emen s
M. . . . . . . . . . . . . . . . . Numbe o obse able measu emen s
˜µ(κ). . . . . . . . . . . . . . . . Di e ence be ween he es ima ed mean a e he κ- h EM i e a ion
and he ue mean
(˜σ2)(κ). . . . . . . . . . . . . Di e ence be ween he es ima ed a iance a e he κ- h EM i e a-
ion and he ue a iance
I. . . . . . . . . . . . . . . . . . . In o ma ion ma ix
dn. . . . . . . . . . . . . . . . . Hidden a iables indica e whe he he n- h measu emen is d opped
(dn= 1) o no (dn= 0)
π. . . . . . . . . . . . . . . . . . D opping a e, de ined as π=P(dn= 1)
βn(d, z). . . . . . . . . . . . P obabili y ha dn= 0 o dn= 1 gi en zn= 0 o zn= 1
Sma phone Adap a ion wi hin MLLR F amewo k
µk. . . . . . . . . . . . . . . . . Mean ec o consis s o means o all APs a he k- h posi ion
ξk. . . . . . . . . . . . . . . . . Ex ended mean ec o consis s o means o all APs a he k- h po-
si ion and a o se e m ac o
ˆ
µk. . . . . . . . . . . . . . . . . Adap ed mean ec o a he k- h posi ion
NAP . . . . . . . . . . . . . . . To al numbe o obse able APs
c(k). . . . . . . . . . . . . . . . Reg ession class c(k)whe e he Gaussian desc ibing k- h posi ion
belongs o
C. . . . . . . . . . . . . . . . . . To al numbe o eg ession classes
W(c(k)) . . . . . . . . . . . . . Mean ans o ma ion ma ix o be applied o he eg ession class
c(k)
γk(n). . . . . . . . . . . . . . The pos e io p obabili y ha RSSI measu emen ec o xnis om
posi ion ℓk
No a ions and Symbols
106
Y. . . . . . . . . . . . . . . . . . Se o measu emen ec o s
yn................. Then- h measu emen ec o consis s o RSSI om NAP APs
yn,i . . . . . . . . . . . . . . . . The non-censo ed, possibly d opped measu ed da a o he n- h mea-
su emen om he i- h AP
D. . . . . . . . . . . . . . . . . . Se o hidden a iable ec o s
dn................. Then- h hidden a iable ec o consis s o andom a iables, each
indica es whe he he measu ed da a om co esponding AP is
d opped o no
dn,i . . . . . . . . . . . . . . . . Random a iable indica es whe he he n- h measu emen om he
i- h AP is d opped o no
X. . . . . . . . . . . . . . . . . . Se o obse able, censo ed, possibly d opped measu emen ec o s
xn................. Then- h measu emen ec o consis s o obse able, censo ed, pos-
sibly d opped measu ed da a om NAP APs
xn,i . . . . . . . . . . . . . . . . The censo ed, possibly d opped measu ed da a o he n- h measu-
emen om he i-AP
w(c(k))
i. . . . . . . . . . . . . . The ow ec o which is he i- h ow o W(c(k))
λ. . . . . . . . . . . . . . . . . . Se o pa ame e s, i.e., d opping a e, mean and a iance adap a ion
ma ices, o be es ima ed o adap a ion pu pose
λk,i . . . . . . . . . . . . . . . . Se o pa ame e s, i.e., d opping a e, mean and a iance adap a ion
ma ices, o be es ima ed o he i- h AP a he k- h posi ion
πk,i . . . . . . . . . . . . . . . . D opping a e o he adap a ion da a o he i- h AP a he k- h posi-
ion
µk,i . . . . . . . . . . . . . . . . Mean o he Gaussian desc ibing he RSSI dis ibu ion o he i- h
AP a he k- h posi ion
σk,i . . . . . . . . . . . . . . . . Va iance o he Gaussian desc ibing he RSSI dis ibu ion o he i- h
AP a he k- h posi ion
zn,i . . . . . . . . . . . . . . . . . Random a iable indica es whe he he n- h measu emen om he
i- h AP is obse ed o no
βk,n,i(d, z). . . . . . . . . . P obabili y ha dn,i = 0 o dn,i = 1 gi en zn,i = 0 o zn,i = 1 a
he k- h posi ion
ˆ
Σk. . . . . . . . . . . . . . . . . Adap ed co a iance ma ix o he Gaussian desc ibing he RSSI ea-
dings o he APs a he k- h posi ion
Bk. . . . . . . . . . . . . . . . . The Choleski ac o o Σk
H(c(k)) . . . . . . . . . . . . . Va iance ans o ma ion ma ix o be applied o he eg ession class
c(k)
h(c(k))
i.............. Thei- h componen o he main diagonal o H(c(k))
Hidden Ma ko Model o Indoo Use T acking
s . . . . . . . . . . . . . . . . . . Hidden s a e a iable a ime
x . . . . . . . . . . . . . . . . . . RSSI obse a ion a ime
Pi,j . . . . . . . . . . . . . . . . T ansi ion p obabili y om he i- h o he j- h s a e
. . . . . . . . . . . . . . . . . . Two-dimensional mo emen ec o compu ed om ine ial senso
da a
No a ions and Symbols
107
α (k). . . . . . . . . . . . . . . Fo wa d a iable: The p obabili y ha he use is a ime in s a e
kgi en he obse ed sequence o o1: and 1:
a.................. 3-dimen ional accele a ion da a ec o
ax. . . . . . . . . . . . . . . . . Accele a ion da a along x-axis
ay. . . . . . . . . . . . . . . . . Accele a ion da a along y-axis
az. . . . . . . . . . . . . . . . . . Accele a ion da a along z-axis
G. . . . . . . . . . . . . . . . . . G a i y cons an
m. . . . . . . . . . . . . . . . . Magne o da a ec o
g. . . . . . . . . . . . . . . . . . G a i y da a ec o
gy . . . . . . . . . . . . . . . . Gy oscope da a ec o
R. . . . . . . . . . . . . . . . . . Ro a ion ma ix
ψ. . . . . . . . . . . . . . . . . . Azimu h angle
α(n). . . . . . . . . . . . . . . S a e ec o ha con ains he absolu e Azimu h angle and i s de i-
a i e
F(n). . . . . . . . . . . . . . . T ansi ion ma ix which indica es a ansi ion o he sys em om
ime n o n+ 1 in Kalman il e
ν1(n). . . . . . . . . . . . . . Whi e Gaussian sys em noise in Kalman il e
ν2(n). . . . . . . . . . . . . . Whi e Gaussian measu emen noise in Kalman il e
G(n). . . . . . . . . . . . . . . Ma ix ha desc ibes he in luences o he sys em noise on he s a e
ec o in Kalman il e
Q1. . . . . . . . . . . . . . . . . Co a iance ma ix o he whi e Gaussian sys em noise in Kalman
il e
Q2. . . . . . . . . . . . . . . . . Co a iance ma ix o he whi e Gaussian measu emen noise in Kal-
man il e
H(n). . . . . . . . . . . . . . . Measu emen ma ix ha desc ibes he in luences o he measu e-
men on he s a e ec o in Kalman il e
Ls ep . . . . . . . . . . . . . . . S ep leng h
Expe imen al Resul s on Indoo Posi ioning
λ. . . . . . . . . . . . . . . . . . Weigh ing ac o be ween ine ial senso in o ma ion and WiFi in-
o ma ion in he calcula ion o o wa d a iable
Lis o igu es
2.1. P oximi y-based posi ioning: he es ima ed posi ion o he mobile use Miis
he posi ion o he base s a ion BSji Mide ec s only signal om BSj, o
he obse ed signal s eng h o BSjis he s onges among he de ec ed singals 6
2.2. Cicula la e a ion based posi ioning: he es ima ed posi ion o he mobile
use Mis de e mined based on he es ima ed dis ances be ween he mobile
use and he e e ence poin s. A leas h ee e e ence poin s a e needed o
calcula e he use posi ion. . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3. Angula ion based posi ioning: he es ima ed posi ion o he mobile use M
is de e mined based on he es ima ed angle αibe ween he mobile use and
he e e ence poin s. A leas wo e e ence poin s a e needed o calcula e he
use posi ion wi h he condi ion ha he use posi ion does no lie on he line
connec ing he e e ence poin s. . . . . . . . . . . . . . . . . . . . . . . . 11
2.4. Finge p in ing based posi ioning: he illed ci cles indica es he e e ence
(ancho ) poin s, while he iangles show base s a ion loca ions. The use
posi ion is he posi ion o he ancho poin whose aining da a bes ma ch
he online measu emen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5. Dead eckoning: he use posi ion is es ima ed based on he es ima ed mo e-
men ec o s assuming ha he s a ing poin is gi en. . . . . . . . . . . . . 15
4.1. His og am o eal ield da a illus a es censo ing and d opping p oblem o
WiFi da a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2. Censo ing p oblem: le igu e: PDF om whe e yis d awn; igh igu e:
PDF om whe e he obse a ion xis d awn. . . . . . . . . . . . . . . . . . 23
4.3. Theo e ical numbe o EM i e a ions κ equi ed o educe he es ima ion
e o o 10−4o i s ini ial alue as a unc ion o (c−µ)/σ. Ini ial alues
µ(0),(σ2)(0) ha e been se o he ML es ima es o µ, σ2compu ed om he
unclipped obse a ions only. . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4. Compa ison o CRLB o mean and a iance wi h MSE ob ained om simu-
la ion o σ2= 25 and N= 1000. . . . . . . . . . . . . . . . . . . . . . . 30
4.5. Measu emen model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.1. S anda d Hidden Ma ko Model: s is he hidden s a e a iable and x is he
obse a ion a ime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.2. T ellis diag am wi h ou di e en s a es s ∈ {1,2,3,4}and Pi,j a e he
ansi ion p obabili ies om s a e ia one ime ins an o s a e ja he la e
ime ins an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
108
Lis o igu es
109
6.3. Modi ied HMM o posi ion es ima ion based on he usion o RSSI and
mo emen ec o obse a ions xand , espec i ely. . . . . . . . . . . . . 45
6.4. S ep de ec ion and posi ion es ima ion sys em o e iew . . . . . . . . . . . 47
6.5. De ice coo dina e sys em (a) and wo ld coo dina e sys em (b) . . . . . . . 47
6.6. Example o aw accele a ion da a i he sma phone is held wi h display in
pa allel o ea h su ace when walking . . . . . . . . . . . . . . . . . . . . 48
6.7. No m o accele a ion da a a e subs ac ing he o ce o g a i y cons an
G=9.81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.8. ka′ka e lowpass il e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.9. S ep de ec ion p ocedu e: In each da a block, he numbe o s eps is de e -
mined based on he c ossing a e o he accele a ion da a o e a h eshold
(magen a lines). The sa e y h eshold is he minimum h eshold alue ha
he ampli ude o noisy accele a ion da a canno exceed. . . . . . . . . . . . 51
6.10. In oduc ion o pseudo s a es: The ed ci cles a e he egula s a es wi h ai-
ning da a, he g een ci cle is he pseudo s a e in oduced inbe ween he egu-
la s a es. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7.1. Floo plan o he a ea whe e ield da a has been conduc ed. . . . . . . . . . 57
7.2. CDF o he posi ioning e o o di e en sys ems. . . . . . . . . . . . . . . 57
7.3. Compa ing he expe imen al esul s on eal da a using 2p oposed EM algo-
i hms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.4. The modi ied HMM s a es, i.e., he allowable use posi ions, and he ansi i-
ons be ween hem. Red and g een ci cles indica e egula and pseudo s a es,
espec i ely. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.5. CDF o he posi ioning e o o di e en sys ems. A e age o e 2 es a-
jec o ies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
8.1. Se e based Indoo Na iga ion Sys em. . . . . . . . . . . . . . . . . . . . 65
8.2. Se e a chi ec u e o he indoo na iga ion sys em. . . . . . . . . . . . . . 69
8.3. Examples o o iginal map and edi ed map . . . . . . . . . . . . . . . . . . 71
8.4. Map edi ing wi h JOSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.5. Class diag am o Ja a applica ion a chi ec u e . . . . . . . . . . . . . . . . 75
8.6. Ja a applica ion showing loo plan in o ma ion and use posi ion ( ed do ). 76
8.7. Ja a applica ion showing se ing op ions. . . . . . . . . . . . . . . . . . . . 77
8.8. Ja a applica ion showing he de elopmen mode: he ed ci cles a e he posi-
ions whe e aining da a we e al eady collec ed, he ed “+” sign on he map
shows he posi ion whe e WiFi da a a e going o be collec ed. . . . . . . . . 78
8.9. WiFi aining da a ga he ing . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.10. Sequence diag am showing he da a ga he ing p ocedu e. . . . . . . . . . . 80
8.11. Se ing sc een showing op ions o localiza ion. . . . . . . . . . . . . . . . 81
8.12. Sequence diag am p esen s he o line localiza ion p ocedu e. . . . . . . . . 82
8.13. Sequence diag am p esen s he online localiza ion p ocedu e. . . . . . . . . 83
8.14. Ja a applica ion showing he ou ing op ions. . . . . . . . . . . . . . . . . 84
8.15. Sequence low p esen s he o line na iga ion p ocedu e. . . . . . . . . . . 85
8.16. Ja a applica ion showing he indoo ou ing pa h. . . . . . . . . . . . . . . 86
8.17. Ja a applica ion showing he indoo and ou doo ou ing pa h. . . . . . . . 86

Lis o igu es
110
8.18. Pee g oup inding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.19. 3-D ep esen a ion o he ou ing pa h . . . . . . . . . . . . . . . . . . . . 87
Lis o ables
7.1. Mean and s anda d de ia ion o APs a 2 posi ions o a i ical da a expe imen 56
7.2. Classi ica ion e o a e on a i icial censo ed da a . . . . . . . . . . . . . . 56
7.3. Classi ica ion e o a e on a i icial censo ed and d opped da a . . . . . . . 58
7.4. Classi ica ion esul s (% posi ions co ec ly classi ied) when aining and es
da a a e gene a ed om he same pa ame e se . . . . . . . . . . . . . . . 60
7.5. Adap a ion pe o mance (% posi ions co ec ly classi ied) on a i ical da a as
a unc ion o amoun o adap a ion da a . . . . . . . . . . . . . . . . . . . 60
7.6. RMS posi ioning e o (in [m]) as a unc ion o he amoun o posi ions ha-
ing adap a ion da a and he amoun o ada a ion da a . . . . . . . . . . . . 61
7.7. E ec o numbe o clus e s on RMS posi ioning e o . . . . . . . . . . . 62
7.8. Mean posi ioning e o on a i icial da a . . . . . . . . . . . . . . . . . . . 63
8.1. Map in o ma ion ables in he da abase: s o age o he geog aphical in o ma-
ion o inge p in posi ions, and he in o ma ion abou he di ec connec ion
be ween any pai o posi ions. . . . . . . . . . . . . . . . . . . . . . . . . 72
8.2. Measu emen ables in he da abase: con ain he RSSI measu emen s, he
posi ion, ID and o ien a ion o he de ice which has been used o collec
da a, and he ime s amp o he measu emen s . . . . . . . . . . . . . . . . 73
8.3. T aining model in o ma ion ables in he da abase: con ain he es ima ed pa-
ame e s and he su icien s a is ics in o ma ion. . . . . . . . . . . . . . . 73
111
Re e ences
[1] R. Mau z, “Indoo Posi ioning Technologies,” in Habili a ion Thesis submi ed o ETH
Zu ich, Zu ich, Feb ua y 2012.
[2] “Indoo Posi ioning and Na iga ion,”
h p://www.compu e .o g/po al/web/compu ingnow/a chi e/june2013.
[3] A. Kushki, K. N. Pla anio is, and A. N. Vene sapopoulos, WLAN Posi ioning Sys ems,
Camb idge, New Yo k, Uni ed S a es, 2012.
[4] M. D. Rod íguez, J. Fa ela, E. A. Ma ínez, and M. A. Muñoz, “Loca ion-awa e access
o hospi al in o ma ion and se ices,” IEEE T ansac ions on In o ma ion Technology
in Biomedicine, ol. 8, no. 4, pp. 448–455, 2004.
[5] “GPS websi e,” h p://www.gps.go /.
[6] P. Enge and P. Mis a, “Special Issue on Global Posi ioning Sys em,” in P oceedings o
he IEEE, Janua y 1999, ol. 87, pp. 3–15.
[7] A. Va sha sky, M. Y. Chen, E. La a, J. F oehlich, D. Haehnel, J. High owe ,
A. LaMa ca, F. Po e , T. Sohn, K. Tang, and I. Smi h, “A e GSM phones THE solu-
ion o localiza ion,” in P oceedings o he 7 h IEEE Wo kshop on Mobile Compu ing
Sys ems and Applica ions, O cas Island, WA, Augus 2006.
[8] R. Haeb-Umbach and S. Peschke, “A No el Simila i y Measu e o posi ioning Cellula
Phones by a Compa ison Wi h a Da abase o Signal Powe Le els,” IEEE T ansac ions
on Vehicula Technology, pp. 368–372, 2007.
[9] M. Ib ahim and M. Yousse , “CellSense: A P obabilis ic RSSI-based GSM Posi ioning
Sys em,” in P oceedings o he GLOBECOM, Miami, PL, USA, Decembe 2010.
[10] S. Peschke, M. Be e meie , and R. Haeb-Umbach, “A GPS posi ioning app oach ex-
ploi ing GSM eloci y es ima es,” in P oceedings o he 6 h Wo kshop on Posi ioning
Na iga ion and Communica ion (WPNC 2009), D esden, Ge many, 2009.
[11] S. Panzie i, F. Pascucci, and G. Uli i, “An ou doo na iga ion sys em using GPS and
ine ial pla o m,” IEEE/ASME T ansac ions on Mecha onics, ol. 7, no. 2, pp. 134–
142, 2002.
[12] H. Liu, H. Da abi, P. Bane jee, and J. Liu, “Su ey o wi eless indoo posi ioning
echniques and sys ems,” IEEE T ansac ions on Sys ems, Man, and Cybe ne ics, Pa
C: Applica ions and Re iews, ol. 6, pp. 1067–1080, 2007.
112
Re e ences
113
[13] H. Cho, H. Jang, and Y. Baek, “P ac ical localiza ion sys em o consume de ices
using zigbee ne wo ks,” IEEE T ansac ions on Consume Elec onics, ol. 56, no. 3,
pp. 1562–1569, 2010.
[14] J. Yoon, J. Kim, W. Lee, and D. Eom, “A TDoA-Based Localiza ion Using P ecise
Time-Synch oniza ion,” in P oceedings o he 14 h In e na ional Con e ence on Ad-
anced Communica ion Technology (ICACT), PyeongChang, Feb ua y 2012.
[15] X. Li and K. Pahla an, “Supe - esolu ion oa es ima ion wi h di e si y o indoo ge-
oloca ion,” IEEE T ansac ions on Wi eless Communica ions, ol. 3, no. 1, pp. 224–234,
2004.
[16] A. Ali and A.S. Oma , “Time o A i al Es ima ion o WLAN Indoo Posi ioning
Sys ems using Ma ix Pencil Supe Resolu ion Algo i hm ,” in P oceedings o he 2 h
Wo kshop on Posi ioning, Na iga ion and Communica ion (WPNC), Hanno e , Ge -
many, Ma ch 2005.
[17] M. Li and Y. Lu, “Angle-O -A i al Es ima ion o Localiza ion and Communica ion
in Wi eless Ne wo ks,” in P oceedings o he 16 h Eu opean Signal P ocessing Con-
e ence (EUSIPCO), Lausanne, Swi ze land, Augus 2008.
[18] P. Bahl and V.N. Padmanabhan, “RADAR: An In-Building RF-Based Use Loca ion
and T acking Sys em,” in INFOCOM 2000. Nine een h Annual Join Con e ence o he
IEEE Compu e and Communica ions Socie ies. IEEE, 2000, ol. 2, pp. 775–784.
[19] H. Nu minen, J. Tal i ie, S. Ali-Löy y, P. Mülle , E. Lohan, R. Piché, and M. Ren o s,
“S a is ical pa h loss pa ame e es ima ion and posi ioning using ss measu emen s,”
Jou nal o Global Posi ioning Sys ems, ol. 12, no. 1, pp. 13–27, 2013.
[20] A. W. S. Au, C. Feng, S. Valaee, S. Reyes, S. So ou , D. Gold, K. Go don, and
M. Eizenman, “Indoo acking and na iga ion using ecei ed signal s eng h and com-
p essi e sensing on a mobile de ice,” IEEE T ansac ions on Mobile Compu ing, ol.
12, no. 10, pp. 2050–2062, 2013.
[21] P. Bahl and V.N. Padmanabhan, “Enhancemen s o he RADAR Use Loca ion and
T acking Sys em,” in Technical Repo MSR-TR-2000-12. Mic oso Resea ch, Feb u-
a y 2000.
[22] K. Kaema ungsi and P. K ishnamu h, “Modeling o indoo posi ioning sys ems based
on loca ion inge p in ing,” in P oceedings o he INFOCOM, Hong Kong, Ma ch 2004.
[23] T. Roos, P. Myllymaki, H. Ti i, P. Misikangas, and J. Sie anen, “A p obabilis ic ap-
p oach o wlan use loca ion es ima ion,” In e na ional Jou nal o Wi eless In o ma ion
Ne wo ks, ol. 9, no. 3, pp. 155–164, 2002.
[24] A. Agiwal, P. Khandpu , and H. Sa an, “Loca o : loca ion es ima ion sys em o wi e-
less LANs,” in P oceedings o he 2nd ACM In e na ional wo kshop on Wi eless mobile
applica ions and se ices on WLAN hos po s. ACM, 2004, pp. 102–109.