隨著科技的進步，許多擷取環境相關資訊並加以計算的定位應用服務也不斷增
加。在本篇研究論文中，我們透過理論基礎並發展一套無需任何事前建置的室外
定位系統。我們使用兩種不同分支的多元尺度法(Multidimensional Scaling) 透過
移動用戶接收基地台發射的訊號強度提高定位精準度。此兩中種方法分別為古典
多元尺度法以及非度量性多元尺度法。其中非度量性多元尺度法為我們主要的使
用方法。
多元尺度法是一種找尋多個物件之間相關性方法的統稱。最早被應用於社會
學，其後也被廣泛應用在經濟學、心理學、人類學以及市場調查等許多不同知識
領域的分析。其目的是利用成對個體間的相對接近性或相似性，建構一個合適
的低維度空間。近年來多元尺度法大量應用於感測網路中，並獲得相當良好的結
果。
第一種方法，古典多元尺度法。透過傳播路境模型(Hata model) ，將移動用
戶接收鄰近基地台發射的訊號轉換為之間的實際距離。藉由此距離建構的差異性
矩陣，將其資訊降低成二維可視化(visualize) 的數據點。第二種方法，非度量性
多元尺度法，根據個體間的差異性，近似一個非線性但正相關的低維度替換，並
能保有原資訊間的差異。在此方法中，我們只需直接計算訊號間的差異即可。
在完成多元尺度法的二維點座標估計後，我們提出了兩種分析轉換，進而達成與
實際位置的匹配。包括反矩陣的運算以及普氏分析(Procrustes analysis)。此轉換
目的在於決定某種轉換關係，使得實際狀況跟估測結果誤差最小。透過預測的基
地台位置到實際位置的矩陣轉換，移動用戶也可經由此矩陣找尋到自身位置。
我們利用筆記型電腦搭配手機網路，進行實際的室外資料量測，環境包括
元智大學校內環境。在此實驗中我們與兩種傳統基於基地台的定位演算法做比
較。包括基地台中心定位法(Cell-ID) 以及增強型基地台中心定位法(Enhanced Cell-ID)。實驗結果非度量性多元尺度法表現整體優於古典尺度法及其他兩種傳
統定位方法，可降低22.47%至49.94%定位的平均誤差。

With technique growing, there has been an increasing need to capture the context
information and to gure it into applicaitions. In this paper, we established the
theoretical base and developed a calibration-free localization system in an outdoor
enviroment. We apply two kinds of multidimensional scaling (MDS) techniques that
improve mobile localization by using the Recieve Signal Strength (RSS), including
classical MDS (CMDS) and nonmetric MDS (NMDS). The mobile device obtain
the information including the position of the base station (BS) and the RSS among
each of them. The MDS method is widely used on the wireless sensor network in the
past. In CMDS, we estimate the RSS to the Euclidean distance as the input dissim-
ilarities matrix through a Hata propagation model. The distance estimation may
su er from errors, since the magnitude of the input are sensitive to the environment.
Instead of CMDS, NMDS approximates a nonlinear, but monotonic, transformation
of given dissimilarities, which among mobile device and BSs. Although the RSS is
diverse with time, the dissimilarities between each nodes are similar. In NMDS, we
calculate the dissimilarities from the RSS as intput directly. The result approaches
to a 2-dimension point as the coordinate of each node in geometric space. We then
analyze the transformation to calculate the best shape-preserving that matches the
true location of BS such as inverse transformation and procrustes analysis. The po-
sition of the mobile device is be determined by applying the transformation nally.
This study is applied to an actual GSM network with realistic measurements. The
experiment shows NMDS with inverse transform outperformed CMDS and any con-
ventional cell-based mechanism, reducing the mean and 67-th percentile localization
errors by 22.47% - 49.94% and 375%-67.86%, respectively, compared to the Cell-ID
vi
method and the enhanced Cell-ID method.

Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Chapter 2. Background and Related Works . . . . . . . . . . . . . . . . . . . 5
2.1 Rss-based localization Systems . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Distance-based Localization Systems . . . . . . . . . . . . . . . . . . 5
2.3 Cell-based Localization Systems . . . . . . . . . . . . . . . . . . . . . 6
Chapter 3. Zero-Con guration Localization System . . . . . . . . . . . . . . . 8
3.1 Propagation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Multidimensional Scaling . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Classical Multidimension Scaling- CMDS . . . . . . . . . . . . 10
3.2.2 Nonmetric Multidimension Scaling- NMDS . . . . . . . . . . . 14
3.3 Transformation Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3.1 Inverse Transformation . . . . . . . . . . . . . . . . . . . . . . 16
3.3.2 Procrustes Analysis . . . . . . . . . . . . . . . . . . . . . . . . 17
Chapter 4. Experimental Setup and Performances of Nonmetric Multidime-
sional Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Evaluation of Performance . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Analysis on Base Stations . . . . . . . . . . . . . . . . . . . . 23
4.2.2 Analysis on Gaussian Noise . . . . . . . . . . . . . . . . . . . 25
4.2.3 Transformaiont Performance Comparison . . . . . . . . . . . . 26
Chapter 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

[1] C. Botteron, A. Host-Madsen, and M. Fattouche, E ects of system and envi-
ronment parameters on the performance of network-based mobile station posi-
tion estimators," IEEE Transactions on Vehicular Technology, vol. 53, no. 1,
pp. 163 { 180, 2004.
[2] K. Lui, H. So, and W.-K. Ma, Maximum a posteriori approach to time-of-
arrival-based localization in non-line-of-sight environment," IEEE Transactions
on Vehicular Technology, vol. 59, no. 3, pp. 1517 {1523, 2010.
[3] R. Ouyang, A.-S. Wong, and C.-T. Lea, Received signal strength-based wire-
less localization via semide nite programming: Noncooperative and cooperative
schemes," IEEE Transactions on Vehicular Technology, vol. 59, no. 3, pp. 1307
{1318, 2010.
[4] A.Weiss, On the accuracy of a cellular location system based on RSS measure-
ments," IEEE Transactions on Vehicular Technology, vol. 52, no. 6, pp. 1508 {
1518, 2003.
[5] S. Mazuelas, A. Bahillo, R. Lorenzo, P. Fernandez, F. Lago, E. Garcia, J. Blas,
and E. Abril, Robust indoor positioning provided by real-time RSSI values
in unmodi ed WLAN networks," IEEE Journal on Signal Processing, vol. 3,
no. 5, pp. 821 {831, 2009.
[6] D.-B. Lin and R.-T. Juang, Mobile location estimation based on di erences of
signal attenuations for GSM systems," IEEE Transactions on Vehicular Tech-
nology, vol. 54, no. 4, pp. 1447 { 1454, 2005.
[7] V. Honkavirta, T. Perala, S. Ali-Loytty, and R. Piche, A comparative survey of
WLAN location ngerprinting methods," Workshop on Positioning, Navigation
and Communication, pp. 243 {251, 2009.
[8] N. Swangmuang and P. Krishnamurthy, Location ngerprint analyses to-
ward e cient indoor positioning," IEEE International Conference on Pervasive
Computing and Communications, pp. 100 {109, 2008.
29
[9] Y. Li, Y. Yu, Q. Pan, and C. Zhao, Scene matching based on spatial rela-
tion constraint in suitable-matching area," IEEE International Conference on
Intelligent Computing and Intelligent Systems, vol. 4, pp. 598 {603, 2009.
[10] W. S. Torgerson, Multidimensional scaling: I. theory and method," Psychome-
trika, vol. 17, pp. 401{419, Dec. 1952.
[11] G. Young and A. S. Householder, Discussion of a set of points in terms of their
mutual distances," Psychometrika, pp. 19{22, Mar. 1938.
[12] B. Wei, W. Chen, and X. Ding, Advanced mds based localization algorithm
for location based services in wireless sensor network," Ubiquitous Positioning
Indoor Navigation and Location Based Service, pp. 1 {8, Oct. 2010.
[13] J. Desai and U. Tureli, Evaluating performance of various localization algo-
rithms in wireless and sensor networks," International Symposium on Personal,
Indoor and Mobile Radio Communications, pp. 1 {5, Sep. 2007.
[14] H. Laitinen, J. Lahteenmaki, and T. Nordstrom, Database correlation method
for GSM location," Vehicular Technology Conference, vol. 4, pp. 2504 {2508
vol.4, 2001.
[15] C. Debono and C. Calleja, The application of database correlation methods
for location detection in GSM networks," International Symposium on Com-
munications, Control and Signal Processing, pp. 1324 {1329, 2008.
[16] P. Bahl and V. Padmanabhan, RADAR: an in-building rf-based user location
and tracking system," Proc. INFOCOM, vol. 2, pp. 775 {784 vol.2, 2000.
[17] M. Khalaf-Allah and K. Kyamakya, Mobile location in GSM networks using
database correlation with bayesian estimation," IEEE Symposium on Comput-
ers and Communications, pp. 289 { 293, 2006.
[18] K. Anne, K. Kyamakya, F. Erbas, C. Takenga, and J. Chedjou, GSM RSSI-
based positioning using extended kalman lter for training arti cial neural net-
works," Vehicular Technology Conference, vol. 6, pp. 4141 { 4145 Vol. 6, 2004.
30
[19] S.-H. Fang and T.-N. Lin, A dynamic system approach for radio location
ngerprinting in wireless local area networks," IEEE Transactions on Commu-
nications, vol. 58, no. 4, pp. 1020 {1025, 2010.
[20] C.-H. Chen, K.-T. Feng, C.-L. Chen, and P.-H. Tseng, Wireless location es-
timation with the assistance of virtual base stations," IEEE Transactions on
Vehicular Technology, vol. 58, no. 1, pp. 93 {106, 2009.
[21] B.-C. Liu and K.-H. Lin, SSSD-Based mobile positioning: On the accuracy
improvement issues in distance and location estimations," IEEE Transactions
on Vehicular Technology, vol. 58, no. 3, pp. 1245 {1254, 2009.
[22] K. Yang, J. An, X. Bu, and G. Sun, Constrained total least-squares location
algorithm using time-di erence-of-arrival measurements," IEEE Transactions
on Vehicular Technology, vol. 59, no. 3, pp. 1558 {1562, 2010.
[23] S. Al-Jazzar, M. Ghogho, and D. McLernon, A joint TOA/AOA constrained
minimization method for locating wireless devices in non-line-of-sight environ-
ment," IEEE Transactions on Vehicular Technology, vol. 58, no. 1, pp. 468
{472, 2009.
[24] B. Sieskul, F. Zheng, and T. Kaiser, A hybrid SS-ToA Wireless NLoS geolo-
cation based on path attenuation: ToA Estimation and CRB for mobile posi-
tion estimation," IEEE Transactions on Vehicular Technology, vol. 58, no. 9,
pp. 4930 {4942, 2009.
[25] P. Wijesinghe and D. Dias, Novel approach for RSS calibration in DCM-based
mobile positioning using propagation models," International Conference on In-
formation and Automation for Sustainability, pp. 29 {34, 2008.
[26] D. Zimmermann, J. Baumann, A. Layh, F. Landstorfer, R. Hoppe, and
G. Wol
e, Database correlation for positioning of mobile terminals in cellular
networks using wave propagation models," Vehicular Technology Conference,
vol. 7, pp. 4682 { 4686 Vol. 7, 2004.
31
[27] Y. Chen, W. Trappe, and R. P. Martin, Adls: Attack detection for wireless
localization using least squares," IEEE International Conference on Pervasive
Computing and Communications Workshops, pp. 610 {613, Mar. 2007.
[28] Y. Chen, J.-A. Francisco, W. Trappe, and R. Martin, A practical approach to
landmark deployment for indoor localization," IEEE Communications Society
on Sensor and Ad Hoc Communications and Networks, vol. 1, pp. 365 {373,
Sep. 2006.
[29] H. Lim, L.-C. Kung, J. C. Hou, and H. Luo, ero-con guration, robust indoor
localization: Theory and experimentation," Proc. INFOCOM, pp. 1 {12, Apr.
2006.
[30] K. Cheung and H. So, A multidimensional scaling framework for mobile lo-
cation using time-of-arrival measurements," IEEE Transactions on Signal Pro-
cessing, vol. 53, pp. 460 { 470, Feb. 2005.
[31] V. D. M. Nhat, D. Vo, S. Challa, and S. Lee, Nonmetric mds for sensor local-
ization," International Symposium on Wireless Pervasive Computing, pp. 396
{400, May 2008.
[32] X. Zhang, Y. Wu, and X. Wei, Localization algorithms in wireless sensor
networks using nonmetric multidimensional scaling with rssi for precision agri-
culture," International Conference on Computer and Automation Engineering,
vol. 5, pp. 556 {559, Feb. 2010.
[33] E. Trevisani and A. Vitaletti, Cell-ID location technique, limits and bene ts:
an experimental study," IEEE Workshop on Mobile Computing Systems and
Applications, pp. 51 { 60, 2004.
[34] T. Wigren, Adaptive enhanced cell-id ngerprinting localization by clustering
of precise position measurements," IEEE Transactions on Vehicular Technol-
ogy, vol. 56, no. 5, pp. 3199 {3209, 2007.
[35] R. Yamamoto, H. Matsutani, H. Matsuki, T. Oono, and H. Ohtsuka, Posi-
tion location technologies using signal strength in cellular systems," Vehicular
Technology Conference, vol. 4, pp. 2570 {2574 vol.4, 2001.