臺灣博碩士論文加值系統

在本研究中，我們將提出具自我適應的定位技術。所謂自我適應，有幾個層次：(i)可自我修正radio map；(ii)使用感測器與建築空間地圖來定位；(iii)以現智慧型手機上的sensors，無需外在輔助基地台(如WiFi Access Points)，即可由手機自定位。我們將跳脫傳統樣本比對法的，以手機上的感測器、相機來定位。本研究包含: (i) 以WiFi基地台相互監測訊號強，完成具有自我適應的訊號地圖：我們將允許基地台間收集訊號強，這稱之為基地台間的感測(inter-beacon measurement)；以此基地台間的感測資訊我們將可以預估訊號地圖的變化。基地台間的感測的功能是在現新一代的WiFi與Zigbee所允許的功能，據此我們將提出具有自我適應的樣本比對技術。(ii) 使用感測器與建築空間地圖來定位:我們可以使用移動感測器與空間地圖，讓定位目標在經過樓層轉換時，可透過移動資訊與空間分隔來做到有效的定位技術。(iii)開發創新的無輔助訊號室內/室外定位技術：我們使用智慧型手機上的相機、感測元件以標記室內/室外標的物，同時使用慣性元件中的e-compass以感測各標的物的方向角，最後透過三個以上的標的物的方向角計算提供定位服務。這方法將跳脫過去需要外在AP或基地台發射訊號並收集訊號強的依賴，達到手機自主定位之目的。

In this research, we are going to develop a new concept, called self-content localization.
There are several levels of challenges for a localization system to be self-content: (i) How
can a localization system calibrate its radio maps automatically? (ii) How can we use the
motion and building information for localization? (iii) Is it possible that a user device
can determine its own location without using any auxiliary signal transmitted from any
infrastructure network (such as WiFi network)? For example, a big challenge is: Can
a smart phone use its own sensors and camera to calculate its location without relying
on any external signal source. The goal of this project is to enhance the self-calibration
capability of pattern-matching techniques and even gradually relieve the dependence on
any infrastructure in typical pattern-matching techniques when conducting localization.
This is what we mean by "self-content" localization. Based on these goals, we plan to
investigate in three issues:
(i)Self-adaptive radio maps: We will develop enabling techniques to allow APs to
detect each other's RSS and use such information as indices to self-calibrate radio maps.
First, we will switch an AP to the receive mode from time to time. Under the receive
mode, an AP will be able to overhear nearby APs' RSSs. We call this inter-beacon measurement.
An important observation is: If we conducted such inter-beacon measurement
when collecting training data during the training phase, these measurements can be used
as important indices of the environment factors when collecting our training data. Then,
at the on-line localization phase, we can also ask APs to collect current inter-beacon
measurements and use them as indices to select a "proper" radio map for comparison.
As far as we know, both WiFi and ZigBee are able to support such capability. Based on
this novel idea, we will develop several pattern-matching localization methods with selftraining,
self-adaptive, and self-calibrating capabilities. (ii) we consider location tracking
in a multi-floor building, which we call a 2.5-D space, by taking wireless signals, inertial
sensing data, and indoor floor plans of a 2.5-D space as inputs and building a SPF (sensor-assisted particle filter) model to fuse these data. Inertial sensors are to capture human mobility, while particles reflect our belief of the user's potential locations. Our work makes the following contributions. First, we propose a model to partition a 2.5-D space into multiple floors connected by stairs and elevators and further partition each floor, according to its floor plan, into logical units connected by passages. Second, based
on the 2.5D space model, we then propose particle sampling and resampling mechanisms
over the logical units using wireless signal strengths and inertial sensing data to adjust
our beliefs of the user's potential locations. Third, to conquer the signaldrifting problem,
we propose a weighting mechanism to control the distribution of particles based on user's
activities of walking on grounds/stairs and taking elevators.
(iii) Self-content localization without auxiliary signals: The previous solutions all rely
on some sort of training data. In this part, we will develop a self-content concept for
localization. We plan to use the camera and sensors on a smart phone to realize the goal.
The basic idea is to use the augmented reality (AR) concept to identify objects captured
by a smart phone. In the meantime, the angle relative to the phone is calculated by
the e-compass of the smart phone. By identifying at least three objects and calculating
their angles relative to the smart phone, we will show how to compute the user's current
location. Note that the above process does not rely on any auxiliary signal transmitted
by external infrastructure. Therefore, this process is fully self-content. In addition, we
will further extend our model to mobile cases, where the user may move around while
identifying objects. The movement of the user will be computed by other sensors, such
as accelerometer. Then, we will show how to conduct mobile self-content localization.

Chinese Abstract i
English Abstract ii
Acknowledgment iv
Contents v
List of Figures vii
List of Tables ix
1 Introduction 1
2 Related Work 4
2.1 Basic Localization Methods . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Data Fusion Techniques for Localization . . . . . . . . . . . . . . . . . . 6
2.3 Adaptive Localization Schemes . . . . . . . . . . . . . . . . . . . . . . . 7
3 Adaptive Radio Maps for Pattern-Matching Localization via Inter-Beacon
Co-calibration 10
3.1 Radio-based Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Adaptive Radio Maps via Inter-Beacon Measurement . . . . . . . . . . . 12
3.2.1 Solution 1: Clustering-based Scheme . . . . . . . . . . . . . . . . 13
3.2.2 Solution 2: Regression-based Scheme . . . . . . . . . . . . . . . . 16
3.3 Simulation and Experimental Results . . . . . . . . . . . . . . . . . . . . 18
3.3.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 18
v
3.3.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Wireless Location Tracking by a Sensor-Assisted Particle Filter and
Floor Plans in a 2.5-D Space 27
4.1 The SPF Model for Location Tracking . . . . . . . . . . . . . . . . . . . 28
4.1.1 Behavior Estimation Module . . . . . . . . . . . . . . . . . . . . . 31
4.1.2 Particle Sampling Module . . . . . . . . . . . . . . . . . . . . . . 33
4.1.3 Particle Weighting Module . . . . . . . . . . . . . . . . . . . . . . 37
4.1.4 Particle Resampling Module . . . . . . . . . . . . . . . . . . . . . 38
4.2 Experiment and Simulation Results . . . . . . . . . . . . . . . . . . . . . 39
4.2.1 Conguration and Simulator . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5 Self-Contained Localization without Auxiliary Signals on Smart Device 42
5.1 Signal-Based Localization . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Signal-Based Localization . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.3 Localization without Auxiliary Signals . . . . . . . . . . . . . . . . . . . 44
5.3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3.2 Example Implementation . . . . . . . . . . . . . . . . . . . . . . . 48
5.3.3 Angulation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 50
5.3.4 Analysis of Localization Errors . . . . . . . . . . . . . . . . . . . 55
5.4 Simulation and Experimental Results . . . . . . . . . . . . . . . . . . . . 58
5.4.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 60
6 Conclusions 63
Bibliography 65

[1] P. Bahl and V. N. Padmanabhan, RADAR: An in-building RF-based user location
and tracking system," in IEEE Int. Conf. Comput. Communicat., vol. 2, 2000, pp.
775~784.
[2] P. Bahl, V. N. Padmanabhan, and A. Balachandran, Enhancements to the radar
user location and tracking system," technical report, Microsoft Research, Tech. Rep.,
2000.
[3] Y. Jiang, X. Pan, K. Li, Q. Lv, R. P. Dick, M. Hannigan, and L. Shang, ARIEL:
Automatic Wi-Fi based room ngerprinting for indoor localization," in Proc. 2012
ACM Conf. Ubiquitous Computing, 2012, pp. 441{450.
[4] M. M. Atia, A. Noureldin, and M. J. Korenberg, Dynamic online-calibrated radio
maps for indoor positioning in wireless local area networks," IEEE Trans. Mobile
Computing, vol. 12, no. 9, pp. 1774{1787, Sept 2013.
[5] J. Niu, B. Wang, L. Cheng, and J. J. P. C. Rodrigues, \WicLoc: An indoor localization
system based on WiFi fingerprints and crowdsourcing," pp. 3008~3013, June
2015.
[6] C.-C. Lo, S.-C. Lin, S.-P. Kuo, Y.-C. Tseng, S.-Y. Peng, S.-M. Huang, Y.-N. Hung,
and C.-F. Hung, People help people: A pattern-matching localization with inputs
from user community," in Int. Comput. Symp., 2010, pp. 638~641.
[7] Y. Ji, S. Biaz, S. Pandey, and P. Agrawal, Ariadne: a dynamic indoor signal map
construction and localization system," in Proceedings of the 4th international conference on Mobile systems, applications and services. ACM, 2006, pp. 151~164.
65
[8] S. h. Fang, T. n. Lin, and K. c. Lee, \A novel algorithm for multipath fingerprinting
in indoor WLAN environments," IEEE Trans. Wireless Communicat., vol. 7, no. 9,
pp. 3579~3588, September 2008.
[9] A. Haeberlen, E. Flannery, A. M. Ladd, A. Rudys, D. S. Wallach, and L. E. Kavraki,
Practical robust localization over large-scale 802.11 wireless networks," in Proc. 10th
Annu. Int. Conf. Mobile Computing and Networking, 2004, pp. 70~84.
[10] N. Chang, R. Rashidzadeh, and M. Ahmadi, Robust indoor positioning using differential
Wi-Fi access points," IEEE Trans. Consumer Electronics, vol. 56, no. 3,
pp. 1860~1867, Aug 2010.
[11] W. Murphy and W. Hereman, \Determination of a position in three dimensions
using trilateration and approximate distances," Colorado School of Mines, Golden,
CO, MCS-95-07, Tech. Rep., 1995.
[12] A. Savvides, C.-C. Han, and M. B. Strivastava, \Dynamic ne-grained localization
in Ad-Hoc networks of sensors," in ACM/IEEE Annu. Int. Conf. Mobile Comput.
and Networking, 2001, pp. 166{179.
[13] D. Niculescu and B. Nath, \Ad-Hoc positioning system (APS) using AoA," in IEEE
Int. Conf. Comput. Communicat., vol. 3, 2003, pp. 1734{1743.
[14] J. Yang and Y. Chen, \Indoor localization using improved rss-based lateration methods,"
in IEEE Global Telecommunications Conf., 2009, pp. 1{6.
[15] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, \The Cricket locationsupport
system," in ACM/IEEE Annu. Int. Conf. Mobile Comput. and Networking,
2000, pp. 32{43.
[16] A. Harter, A. Hopper, P. Steggles, A. Ward, and P. Webster, \The anatomy of a
context-aware application," Wireless Networks, vol. 8, no. 2/3, pp. 187{197, 2002.
[17] Q. Cai and J. K. Aggarwal, \Tracking human motion in structured environments using
a distributed-camera system," IEEE Trans. Pattern Anal. Mach. Intell., vol. 21,
no. 11, pp. 1241{1247, 1999.
66
[18] S. L. Dockstader and A. M. Tekalp, \Multiple camera tracking of interacting and
occluded human motion," Proc. IEEE, vol. 89, no. 10, pp. 1441{1455, 2001.
[19] Y. Kim, Y. Shin, and M. Yoo, \Vlc-tdoa using sinusoidal pilot signal," in Int. Conf.
IT Convergence and Security, Dec 2013, pp. 1{3.
[20] M. Kotaru, K. Joshi, D. Bharadia, and S. Katti, \Spot: Decimeter level localization
using WiFi," SIGCOMM Comput. Commun. Rev., vol. 45, no. 4, pp. 269{282.
[21] ||, \Spot: Decimeter level localization using WiFi," in Proc. ACM Conf. Special
Interest Group on Data Communicat., 2015, pp. 269{282.
[22] R. Harle, \A survey of indoor inertial positioning systems for pedestrians," IEEE
Communicat. Surveys Tutorials, vol. 15, no. 3, pp. 1281{1293, March 2013.
[23] O. J. Woodman, \An introduction to inertial navigation," Tech. Rep., 2007.
[24] S. Godha and G. Lachapelle, \Foot mounted inertial system for pedestrian navigation,"
Measurement Science and Technology, vol. 19, no. 7, p. 075202, 2008.
[25] E. Foxlin, \Pedestrian tracking with shoe-mounted inertial sensors," IEEE Comput.
Graph. and Applicat., vol. 25, no. 6, pp. 38{46, 2005.
[26] N. Casta~neda and S. Lamy-Perbal, \An improved shoe-mounted inertial navigation
system," in Int. Conf. Indoor Positioning and Indoor Navigation, Sept 2010, pp. 1{6.
[27] D. Pai, I. Sasi, P. S. Mantripragada, M. Malpani, and N. Aggarwal, \Padati: A
robust pedestrian dead reckoning system on smartphones," in Int. Conf. Trust, Se-
curity and Privacy in Comput. and Commun., 2012, pp. 2000{2007.
[28] F. Li, C. Zhao, G. Ding, J. Gong, C. Liu, and F. Zhao, \A reliable and accurate
indoor localization method using phone inertial sensors," in Proc. ACM Conf. Ubiq-
uitous Comput, 2012, pp. 421{430.
[29] M. Alzantot and M. Youssef, \UPTIME: Ubiquitous pedestrian tracking using mobile
phones," in IEEE Wireless Commun. and Networking, 2012, pp. 3204{3209.
67
[30] Y. Jin, H.-S. Toh, W.-S. Soh, and W.-C. Wong, \A robust dead-reckoning pedestrian
tracking system with low cost sensors," in IEEE Int. Conf. Pervasive Comput. and
Commun. (PerCom), 2011, pp. 222{230.
[31] A. Doucet, S. Godsill, and C. Andrieu, \On sequential Monte Carlo sampling methods
for Bayesian ltering," Stat. and Comput., vol. 10, no. 3, pp. 197{208, 2000.
[32] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, \Robust Monte Carlo localization
for mobile robots," Articial Intell., vol. 128, no. 1{2, pp. 99{141, 2001.
[33] H. Wang, H. Lenz, A. Szabo, J. Bamberger, and U. Hanebeck, \WLAN-based pedestrian
tracking using particle lters and low-cost MEMS sensors," in Workshop on
Positioning, Navigation and Commun., 2007, pp. 1{7.
[34] A. Rai, K. K. Chintalapudi, V. N. Padmanabhan, and R. Sen, \Zee: zero-eort
crowdsourcing for indoor localization," in Proc. 18th Annu. Int. Conf. Mobile Com-
puting and Networking, 2012, pp. 293{304.
[35] H. Leppakoski, J. Collin, and J. Takala, \Pedestrian navigation based on inertial
sensors, indoor map, and WLAN signals," in IEEE Int. Conf. Acoustics, Speech and
Signal Process., 2012, pp. 1569{1572.
[36] P. Robertson, M. G. Puyol, and M. Angermann, \Collaborative pedestrian mapping
of buildings using inertial sensors and FootSLAM," in ION GNSS, 2011, pp. 1366{
1377.
[37] L.-w. Chan, J.-r. Chiang, Y.-c. Chen, C.-n. Ke, J. Hsu, and H.-h. Chu, \Collaborative
localization: Enhancing wi-based position estimation with neighborhood links in
clusters," in Int. Conf. Pervasive Computing, 2006, pp. 50{66.
[38] H. Liu, Y. Gan, J. Yang, S. Sidhom, Y. Wang, Y. Chen, and F. Ye, \Push the limit
of WiFi based localization for smartphones," in Proc. Int. Conf. Mobile Comput.
and Networking, 2012, pp. 305{316.
68
[39] J. Jun, Y. Gu, L. Cheng, B. Lu, J. Sun, T. Zhu, and J. Niu, \Social-Loc: Improving
indoor localization with social sensing," in Proc. ACM Conf. Embedded Networked
Sensor Syst., 2013, pp. 1{14.
[40] D. Taniuchi, X. Liu, D. Nakai, and T. Maekawa, \Spring model based collaborative
indoor position estimation with neighbor mobile devices," IEEE J. of Selected Topics
in Signal Process., vol. 9, no. 2, pp. 268{277, 2015.
[41] L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil, \LANDMARC: indoor location sensing
using active RFID," Wireless networks, vol. 10, no. 6, pp. 701{710, 2004.
[42] P. Krishnan, A. Krishnakumar, W.-H. Ju, C. Mallows, and S. Gamt, \A system for
LEASE: Location estimation assisted by stationary emitters for indoor RF wireless
networks," in IEEE Int. Conf. Comput. Communicat., vol. 2. IEEE, 2004, pp.
1001{1011.
[43] J. Yin, Q. Yang, and L. M. Ni, \Learning adaptive temporal radio maps for signalstrength-
based location estimation," IEEE Trans. Mobile Comput., vol. 7, no. 7, pp.
869{883, 2008.
[44] C.-C. Lo, L.-Y. Hsu, and Y.-C. Tseng, \Adaptive radio maps for pattern-matching localization
via inter-beacon co-calibration," Pervasive and Mobile Computing, vol. 8,
no. 2, pp. 282{291, 2012.
[45] A. R. Jimenez, F. Seco, C. Prieto, and J. Guevara, \A comparison of pedestrian deadreckoning
algorithms using a low-cost MEMS IMU," in IEEE Int. Symp. Intelligent
Signal Process., 2009, pp. 37{42.
[46] S. Yang and Q. Li, \Ambulatory walking speed estimation under dierent step
lengths and frequencies," in IEEE/ASME Int. Conf. Advanced Intelligent Mecha-
tronics, July 2010, pp. 658{663.
[47] S. Madgwick, \Automated calibration of an accelerometers, magnetometers and
gyroscopes-a feasibility study," Technical report, Tech. Rep., 2010.
69
[48] S. O. H. Madgwick, A. J. L. Harrison, and R. Vaidyanathan, \Estimation of IMU
and MARG orientation using a gradient descent algorithm," in IEEE Int. Conf.
Rehabilitation Robotics, June 2011, pp. 1{7.
[49] S.-P. Huang, J.-W. Qiu, C.-C. Lo, and Y.-C. Tseng, \Wearable localization by particle
lter with the assistance of inertial and visual sensors," in IEEE Int. Conf.
Wearable and Implantable Body Sensor Networks, 2014, pp. 52{57.
[50] J.-W. Qiu, C.-C. Luo, Y.-C. Tseng, Y.-W. Kao, and L.-C. Kuo, \Method and system
of generating indoor map," Taiwan, Republic of China Patent I497 462, 2015.
[51] B. Li, B. Harvey, and T. Gallagher, \Using barometers to determine the height for
indoor positioning," in Int. Conf. Indoor Positioning and Indoor Navigation, 2013,
pp. 1{7.
[52] J.-W. Qiu, C. C. Lo, C.-K. Lin, and Y.-C. Tseng, \A D2D relative positioning system
on smart devices," in IEEE Wireless Commun. and Networking Conf. (WCNC),
2014, pp. 2168{2172.
[53] J. W. Qiu and Y. C. Tseng, \M2M Encountering: Collaborative Localization via
Instant Inter-Particle Filter Data Fusion," IEEE Sensors J., vol. 16, no. 14, pp.
5715{5724, July 2016.
[54] J.-W. Qiu, C.-P. Lin, and Y.-C. Tseng, \BLE-based collaborative indoor localization
with adaptive multi-lateration and mobile encountering," in IEEE Wireless Com-
mun. and Networking Conf. (WCNC), 2016, pp. 1{7.
[55] \The open and interoperable proximity beacon specication," Altbeacon, 2015.