多元尺度法應用於網路資源下的行動定位

Network-Based Mobile Localization Using Multidimensional Scaling.

徐瑛佐(Ying-Tso Hsu)

指導教授 ： 方士豪

元智大學/電機通訊學院/電機工程學系/碩士(2011年)

https://doi.org/10.6838/YZU.2011.00198

摘要

隨著科技的進步，許多擷取環境相關資訊並加以計算的定位應用服務也不斷增
加。在本篇研究論文中，我們透過理論基礎並發展一套無需任何事前建置的室外
定位系統。我們使用兩種不同分支的多元尺度法(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.

並列關鍵字

Multidimensional Scaling

參考文獻

ronment parameters on the performance of network-based mobile station posi-

tion estimators," IEEE Transactions on Vehicular Technology, vol. 53, no. 1,

less localization via semide nite programming: Noncooperative and cooperative

schemes," IEEE Transactions on Vehicular Technology, vol. 59, no. 3, pp. 1307

{1318, 2010.