基于網(wǎng)絡(luò)的定位算法研究*

陶 崢

（解放軍91550部隊(duì)，遼寧 大連 116023）

0 引 言

隨著電腦網(wǎng)絡(luò)的興起，用戶共享諸如打印機(jī)、磁盤存儲器等設(shè)備的需求隨之增多。過去，這些共享需求基于有線連接，以以太網(wǎng)為最流行的手段。然而，自從無線連接問世以來，從方便性、可購性、移動性及生產(chǎn)力優(yōu)勢的角度分析，無線局域網(wǎng)（Wireless Local Area Networks，WLAN）被推到了網(wǎng)絡(luò)應(yīng)用的前列[1]?，F(xiàn)今，通過改善安全性，管理和安裝的方便，無線熱點(diǎn)的日益增加，WLAN已經(jīng)成為極為普遍的應(yīng)用，合理替代了有線網(wǎng)絡(luò)。很多企事業(yè)單位通過在他們已有的有線網(wǎng)絡(luò)中加入WLAN熱點(diǎn)，極大地改善了員工的工作效率。本文聚焦WLAN其中的一項(xiàng)服務(wù)進(jìn)行闡述，即如何在復(fù)雜多變的室內(nèi)環(huán)境下高效定位人和物。

1 網(wǎng)絡(luò)指紋定位技術(shù)

一般來說，基本的位置指紋定位系統(tǒng)劃分為兩個(gè)階段，離線訓(xùn)練階段和在線定位階段。在離線訓(xùn)練階段，將每一個(gè)參考點(diǎn)處采集來自各AP的一組RSS值作為一條位置指紋信息存入數(shù)據(jù)庫；在在線定位階段，利用模式匹配算法對用戶移動終端實(shí)時(shí)采集的位置指紋信息和數(shù)據(jù)庫中的位置指紋信息進(jìn)行比較來獲得用戶的實(shí)際物理坐標(biāo)[2]。

1.1 離線網(wǎng)絡(luò)

在離線訓(xùn)練階段，系統(tǒng)執(zhí)行位置指紋信息的采集和訓(xùn)練，具體步驟如下。

步驟1：從定位區(qū)域內(nèi)的各AP上采集RSS值。首先，用戶移動終端在每一個(gè)參考點(diǎn)處從參與定位的R個(gè)AP上獲取一組RSS值，將在第j（j=1,2,…,M）個(gè)參考點(diǎn)上采集到的RSS值和時(shí)間τ表示為dj(τ)=[d1,j(τ),…,dR,j(τ)]T,τ=1,…,t，t＞1，其中 di,j(τ)為第j個(gè)參考點(diǎn)在時(shí)間點(diǎn)τ上接收到第i個(gè)AP的RSS值，t為采樣時(shí)段。

步驟2：將位置指紋信息發(fā)送至數(shù)據(jù)庫。在這一步，將每一個(gè)參考點(diǎn)在采樣時(shí)段各時(shí)間點(diǎn)的RSS值 求 平 均， 記 為 dj=[d1,j,d2,j…,dR,j]T， 其 中并將dj發(fā)送給服務(wù)器，同時(shí)服務(wù)器會接收到第j個(gè)參考點(diǎn)的相關(guān)物理位置信息Locj=[xj,yj]T。因此，位置指紋地圖可以表示為D=[d1,d2,…,dM]。

步驟3：訓(xùn)練。在離線訓(xùn)練階段的最后，服務(wù)器根據(jù)模式匹配算法的要求，將在定位區(qū)域內(nèi)各參考點(diǎn)上采集的RSS信息訓(xùn)練成指定的位置指紋格式，將位置指紋信息的訓(xùn)練結(jié)果存入數(shù)據(jù)庫。

1.2 在線網(wǎng)絡(luò)

在在線定位階段，待定位點(diǎn)用戶移動終端通過模式匹配算法比較實(shí)時(shí)的位置指紋信息和數(shù)據(jù)庫中的位置指紋信息獲得待定位點(diǎn)的實(shí)際物理坐標(biāo)，具體步驟如下。

步驟1：實(shí)時(shí)采集RSS值。當(dāng)用戶請求獲取物理位置信息時(shí)，用戶移動終端先在未知位置點(diǎn)[x,y]T上從參與定位的各AP上采集實(shí)時(shí)RSS值。

步驟2：將實(shí)時(shí)采樣發(fā)送至服務(wù)器。服務(wù)器接收到來自用戶移動終端的實(shí)時(shí)RSS信息，并將實(shí)時(shí)RSS信息訓(xùn)練成指定的指紋格式。

步驟3：執(zhí)行模式匹配算法。服務(wù)器通過模式匹配算法比較用戶實(shí)時(shí)的位置指紋信息和數(shù)據(jù)庫中的位置指紋信息估算用戶的實(shí)際物理坐標(biāo)。

步驟4：發(fā)送物理坐標(biāo)信息給用戶移動終端。一旦服務(wù)器完成了用戶物理坐標(biāo)的估算，服務(wù)器便將估算結(jié)果[x,y]T發(fā)送至用戶移動終端，物理位置信息將在用戶移動終端上通過可視界面顯示。

2 模式匹配算法

模式匹配算法是位置指紋定位系統(tǒng)中最重要的組成部分。一個(gè)好的模式匹配算法不僅需要精確的描繪位置指紋信息和實(shí)際物理位置信息之間的映射關(guān)系，還需要有低復(fù)雜度、低能耗等特點(diǎn)來滿足用戶實(shí)時(shí)定位的需要。因此，下面將介紹三種典型的模式匹配算法。

2.1 加權(quán)K近鄰法

經(jīng)典的加權(quán)K近鄰法[3]通常使用歐式距離作為距離的度量。歐式距離給出兩個(gè)點(diǎn)之間的絕對距離，如果在二維空間表示歐式距離，則為：

其中(x1,y1)和(x2,y2)是二維空間內(nèi)的兩點(diǎn)坐標(biāo)。

當(dāng)歐式距離應(yīng)用于定位用戶，式（1）可改進(jìn)為：

其中si為待定位點(diǎn)用戶移動終端測到第i個(gè)AP的信號強(qiáng)度，dij為位置指紋庫中第j個(gè)參考點(diǎn)接收到第i個(gè)AP的信號強(qiáng)度。

在離線訓(xùn)練階段，在定位區(qū)域內(nèi)布置M個(gè)參考點(diǎn)并獲取各參考點(diǎn)的位置指紋信息，利用這些參考點(diǎn)的位置指紋信息構(gòu)建位置指紋庫。

在在線定位階段，歐式距離通過搜索位置指紋數(shù)據(jù)庫中每一個(gè)參考點(diǎn)的位置指紋信息找到距離待定位點(diǎn)位置指紋信息最近的那個(gè)參考點(diǎn)，即找到最小的Lj，此法稱為最近鄰法。

如果選取Lj值較小的K(K≥2)個(gè)參考點(diǎn)為預(yù)定位參考點(diǎn)，并計(jì)算其對應(yīng)坐標(biāo)的平均值作為定位結(jié)果，即為K近鄰法。計(jì)算方法為：

與原始的最近鄰法相比，該法引入了K個(gè)估計(jì)位置坐標(biāo)來計(jì)算待定位點(diǎn)的位置。從理論上講，對定位精度會有一定提升，但是如果室內(nèi)環(huán)境有較大噪聲，定位誤差會明顯加大。

進(jìn)一步根據(jù)不同預(yù)定位參考點(diǎn)對定位結(jié)果的貢獻(xiàn)不同計(jì)算預(yù)定位參考點(diǎn)坐標(biāo)加權(quán)后的和作為定位結(jié)果，即為加權(quán)K近鄰法，如式（4）所示：

其中wj為預(yù)定位參考點(diǎn)j的權(quán)重因子，其值主要取決于預(yù)定位參考點(diǎn)位置指紋信息和待定位點(diǎn)位置指紋信息之間的歐式距離Lj， 計(jì)算方法為：

如果wj的計(jì)算結(jié)果為即為K近鄰法。

加權(quán)K近鄰法因其簡單性和實(shí)用性等特點(diǎn)，目前已經(jīng)成為非常流行的一種定位算法。

2.2 概率分布法

在室內(nèi)無線局域網(wǎng)覆蓋范圍內(nèi)，室內(nèi)環(huán)境的多變使得某一點(diǎn)處的RSS值并不是恒定不變的，而是帶有一定程度的波動。從實(shí)測來看，RSS值基本上呈現(xiàn)高斯分布[4]。所以，可以使用概率分布法進(jìn)行匹配定位，計(jì)算待定位點(diǎn)的位置。

在離線訓(xùn)練階段，獲取每一個(gè)參考點(diǎn)處接收來自各AP的RSS的平均值e_rssi_i和方差d_rssi_i，其中i為AP的序號，將上述數(shù)據(jù)連同各參考點(diǎn)的物理坐標(biāo)一同構(gòu)建位置指紋庫。

在在線定位階段，在待定位點(diǎn)測量來自各AP的RSS值命名為rssi_AP_i，并將其與位置指紋庫中的數(shù)據(jù)進(jìn)行匹配運(yùn)算。根據(jù)式（6）的高斯分布公式，可以獲得rssi_AP_i在位置指紋庫中點(diǎn)(x,y)處的概率pi(x,y)：

隨后將每個(gè)AP的RSS分布的概率相乘，如式（7）所示，求得待定位點(diǎn)在參考點(diǎn)(x,y)處總的分布概率：

最后，將最大的p(x,y)所代表參考點(diǎn)的物理坐標(biāo)作為定位結(jié)果。

和加權(quán)K近鄰法一樣，也可以在計(jì)算完待定位點(diǎn)在各參考點(diǎn)處總的分布概率p(x,y)后，取值較大的K(K≥2)個(gè)參考點(diǎn)作為預(yù)定位參考點(diǎn)，對待定位點(diǎn)在預(yù)定位參考點(diǎn)處總的分布概率p(x,y)取自然對數(shù)。如果預(yù)定位參考點(diǎn)有3個(gè)lnp(x1,y1)、lnp(x2,y2)和 lnp(x3,y3)， 隨 后 令 a=|lnp(x1,y1)|、b=lnp(x2,y2)、c=lnp(x3,y3)，則加權(quán)后的定位算法如式（8）和式（9）所示：

類似加權(quán)K近鄰法，通過添加合適的權(quán)重系數(shù)，可以有效降低定位誤差。

2.3 人工神經(jīng)網(wǎng)絡(luò)法

神經(jīng)網(wǎng)絡(luò)是解決模式分類問題的強(qiáng)有力的數(shù)學(xué)工具，最初為了模擬人腦的運(yùn)作而被提出。神經(jīng)網(wǎng)絡(luò)可以起到一個(gè)復(fù)雜的、非線性并行處理的計(jì)算機(jī)的作用。人腦由無數(shù)個(gè)神經(jīng)元組成，這些神經(jīng)元以某種方式組合起來進(jìn)行復(fù)雜的運(yùn)算（如模式識別），并同現(xiàn)今的計(jì)算機(jī)解法具有相同的速度和準(zhǔn)確性。

根據(jù)神經(jīng)網(wǎng)絡(luò)的特性，可以將其應(yīng)用到WLAN位置指紋定位工程應(yīng)用領(lǐng)域。神經(jīng)網(wǎng)絡(luò)法同樣分為離線訓(xùn)練和在線定位兩個(gè)階段。

在離線訓(xùn)練階段，輸入定義為每一個(gè)參考點(diǎn)接收來自各AP的RSS值組成的位置指紋信息(RSSAP1,RSSAP2,…,RSSAPN-1,RSSAPN)，輸出定義為相對應(yīng)參考點(diǎn)的物理坐標(biāo)(x,y)。利用這些數(shù)據(jù)對神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，期間不斷調(diào)整相關(guān)參數(shù)。

在在線定位階段，將待定位點(diǎn)的位置指紋信息輸入神經(jīng)網(wǎng)絡(luò)，得到的輸出即為待定位點(diǎn)的物理坐標(biāo)。

以三層前饋神經(jīng)網(wǎng)絡(luò)[5]為例，定位算法結(jié)構(gòu)圖如圖1所示。

圖1 三層前饋神經(jīng)網(wǎng)絡(luò)定位法

一般來說，三層網(wǎng)絡(luò)即可實(shí)現(xiàn)位置指紋定位中各變量之間的學(xué)習(xí)和擬合，獲得較準(zhǔn)確的定位精度。但是，如果網(wǎng)絡(luò)多于三層，就會導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、網(wǎng)絡(luò)訓(xùn)練耗時(shí)、易陷入局部最小點(diǎn)，并可導(dǎo)致結(jié)果不收斂問題。因此，在位置指紋定位的實(shí)際工程應(yīng)用中，選取三層的網(wǎng)絡(luò)模型即可（輸入層、隱藏層和輸出層）。輸入層的單位數(shù)為定位區(qū)域內(nèi)AP的總數(shù)目，利用定位區(qū)域內(nèi)每一個(gè)參考點(diǎn)的位置指紋信息作為神經(jīng)網(wǎng)絡(luò)的一個(gè)輸入向量；隱藏層單元數(shù)量的確定目前還缺乏清晰的理論指導(dǎo)，不過可以通過測試網(wǎng)絡(luò)性能好壞的方式確定，如可以先選取較多的隱藏層單元，然后逐一減少隱藏層的單元數(shù)量，一直到網(wǎng)絡(luò)性能顯著變壞[6]。

用于WLAN位置指紋定位工程應(yīng)用領(lǐng)域最常見的神經(jīng)網(wǎng)絡(luò)是BP神經(jīng)網(wǎng)絡(luò)[7]。

3 網(wǎng)絡(luò)定位面臨的挑戰(zhàn)

本文將從定位精度、復(fù)雜度和可擴(kuò)展性三個(gè)方面分析位置指紋定位技術(shù)面臨的挑戰(zhàn)。

3.1 定位精度

定位精度是面對一個(gè)定位系統(tǒng)首先應(yīng)該考慮的因素之一。所有的位置指紋定位方法都要面對復(fù)雜室內(nèi)環(huán)境帶來的影響，如多徑效應(yīng)、陰影衰落、以及環(huán)境溫度、人員走動包括手持設(shè)備方位等因素都能引起RSS向量之間的錯誤匹配，導(dǎo)致定位誤差的增大。因此，復(fù)雜室內(nèi)環(huán)境是對定位精度的首要挑戰(zhàn)。其中，根據(jù)不同AP對定位的貢獻(xiàn)不同給各AP加權(quán)，可以有效抵抗環(huán)境因素帶來的負(fù)面影響。

3.2 復(fù)雜度

定位系統(tǒng)的復(fù)雜度主要和定位系統(tǒng)的成本相關(guān)聯(lián)。復(fù)雜度主要取決于諸如硬件體系結(jié)構(gòu)、計(jì)算復(fù)雜性和易用性等因素。成本主要包括產(chǎn)品研發(fā)、定位運(yùn)算時(shí)間和電量損耗。一般來講，定位系統(tǒng)越復(fù)雜，成本就越高。一個(gè)好的位置指紋定位系統(tǒng)設(shè)計(jì)應(yīng)該做到低復(fù)雜度、低成本、運(yùn)算時(shí)間快以及方便易用，尤其是在在線定位階段。但是，很多時(shí)候高精度和低復(fù)雜度在一個(gè)系統(tǒng)里不能同時(shí)實(shí)現(xiàn)。針對這個(gè)問題，可以用聚類算法在維持定位精度的前提下，降低定位系統(tǒng)在在線定位階段的復(fù)雜度。

3.3 可擴(kuò)展性

在可擴(kuò)展性方面，位置指紋定位系統(tǒng)面臨的一個(gè)最重要的挑戰(zhàn)，是當(dāng)環(huán)境改變時(shí)重建位置指紋數(shù)據(jù)庫的工作量過大且耗費(fèi)時(shí)間。

4 結(jié) 語

本文研究基于RSS的位置指紋定位系統(tǒng)，首先概覽位置指紋定位系統(tǒng)的架構(gòu)，根據(jù)以往文獻(xiàn)總結(jié)評價(jià)定位系統(tǒng)優(yōu)劣的重要指標(biāo)，其次分析經(jīng)典的模式匹配算法，包括加權(quán)K近鄰法、概率分布法和人工神經(jīng)網(wǎng)絡(luò)法，最后分析位置指紋定位技術(shù)面臨的挑戰(zhàn)。從本文的分析可以看出，在基于RSS的位置指紋定位技術(shù)的研究中，如何有效提高定位精度和降低在線定位階段的算法復(fù)雜度是最具挑戰(zhàn)性的問題。