陳 兵 楊小玲

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210016)

一種基于概率密度的WLAN 接入點(diǎn)定位的算法

陳 兵 楊小玲*

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210016)

無(wú)線局域網(wǎng)(WLAN)中可以對(duì)無(wú)線接入點(diǎn)(Access Point, AP)進(jìn)行定位。該文提出一種基于概率密度的AP定位算法(Probability Density algorithm for Access Point Localization, PDAPL)。首先對(duì)實(shí)驗(yàn)區(qū)域進(jìn)行分區(qū)；然后根據(jù)定向天線在不同位置和不同角度收到的信號(hào)強(qiáng)度，計(jì)算AP落在各區(qū)域的概率，形成與密度有關(guān)的概率統(tǒng)計(jì)表；最后對(duì)AP的位置進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明，該文提出的算法采集數(shù)據(jù)少，只需在少量點(diǎn)和少量角度采集信號(hào)就可以得到較高的定位精度。與DrivebyLoc, Distance和AoA相比，得到相同的定位精度PDAPL所需要的測(cè)量點(diǎn)和測(cè)量角度只是DrivebyLoc的一半左右，比Distance和AoA所需要的更少；測(cè)量點(diǎn)和測(cè)量角度數(shù)量相同時(shí)，PDAPL的定位精度相對(duì)于DrivebyLoc提升了50%左右。

無(wú)線通信；接入點(diǎn)(AP)定位；定向天線；概率密度

1 引言

隨著無(wú)線通信技術(shù)的發(fā)展，無(wú)線定位服務(wù)越來(lái)越重要，但由于全球定位系統(tǒng)在高樓林立的城市街區(qū)或建筑物內(nèi)不能精準(zhǔn)工作，于是又出現(xiàn)了一系列地面無(wú)線定位系統(tǒng)[1]，例如基于紅外線、超聲波、藍(lán)牙、無(wú)線傳感器網(wǎng)絡(luò)、無(wú)線局域網(wǎng)(Wireless Local Area Network, WLAN)等定位技術(shù)，其中基于WLAN的定位技術(shù)成為研究熱點(diǎn)，其具有設(shè)備簡(jiǎn)單、覆蓋范圍廣、服務(wù)可集成高等特點(diǎn)。WLAN有兩種主要的拓?fù)浣Y(jié)構(gòu)，即自組織網(wǎng)絡(luò)和基礎(chǔ)結(jié)構(gòu)網(wǎng)絡(luò)，其中基礎(chǔ)結(jié)構(gòu)網(wǎng)絡(luò)目前應(yīng)用最為廣泛，在此結(jié)構(gòu)中，無(wú)線局域網(wǎng)的接入點(diǎn)(Access Point, AP)負(fù)責(zé)無(wú)線網(wǎng)絡(luò)的覆蓋和通信，是無(wú)線局域網(wǎng)的中心。本文主要研究無(wú)線接入點(diǎn)的定位問(wèn)題，其意義在于隨著WLAN的高密度發(fā)展，協(xié)調(diào)和管理無(wú)線網(wǎng)絡(luò)成為一個(gè)很重要的問(wèn)題，因此需要能夠通過(guò)他們的信號(hào)來(lái)確定其位置。對(duì)單獨(dú)的用戶來(lái)說(shuō)，AP定位可以幫助他們得到無(wú)線接入點(diǎn)的位置信息，進(jìn)而快速地連接網(wǎng)絡(luò)；對(duì)網(wǎng)絡(luò)管理員而言，AP定位有助于更好的網(wǎng)絡(luò)管理，識(shí)別額外接口的AP，幫助找到非法AP，尤其在一些涉密單位，可以通過(guò)AP定位來(lái)發(fā)現(xiàn)和定位無(wú)線接入點(diǎn)。

根據(jù)定位依據(jù)的物理量，無(wú)線定位可以劃分為幾下幾類(lèi)：基于信號(hào)到達(dá)時(shí)間(Time Of Arrive, TOA)[2]、基于信號(hào)到達(dá)時(shí)間差(Time Difference OfArrive, TDOA)[3]、基于信號(hào)入射角(Angle Of Arrive, AOA)[4]、基于接收信號(hào)強(qiáng)度(Receive Signal Strength, RSS)[5]?，F(xiàn)有AP定位的方法可分為以下幾類(lèi)：(1)基于信號(hào)傳播模型，例如文獻(xiàn)[6-11]。在一個(gè)或多個(gè)點(diǎn)進(jìn)行測(cè)量，得到一組RSS，利用無(wú)線信號(hào)傳播模型將信號(hào)強(qiáng)度轉(zhuǎn)化為測(cè)量點(diǎn)與AP的距離，進(jìn)而計(jì)算AP的位置；(2)基于信號(hào)強(qiáng)度的梯度值，例如文獻(xiàn)[12]。在多點(diǎn)進(jìn)行測(cè)量，比較收到的信號(hào)強(qiáng)度值，分析RSS的變化趨勢(shì)，進(jìn)而估算AP的位置；(3)基于AP之間的相對(duì)位置，例如文獻(xiàn)[13,14]。在需要定位的區(qū)域內(nèi)加入一些已知位置的AP，根據(jù)多點(diǎn)測(cè)量得到的信號(hào)強(qiáng)度，找出已知位置的AP和待定位AP的幾何關(guān)系，再通過(guò)已知位置的AP計(jì)算待定位AP的位置；(4)利用定向天線或其他類(lèi)似設(shè)備，例如文獻(xiàn)[15-17]。根據(jù)天線旋轉(zhuǎn)過(guò)程中的信號(hào)強(qiáng)度變化，判斷AP的方向，通過(guò)多點(diǎn)測(cè)量，得到各測(cè)量點(diǎn)上可能的AP的方向，然后綜合這些方向計(jì)算AP的位置。

以上方法的共同特點(diǎn)是，為了提高定位精度，需要在很多點(diǎn)和很多角度收集數(shù)據(jù)，費(fèi)時(shí)費(fèi)力。據(jù)此本文提出了一種僅需在少量采集點(diǎn)收集少量數(shù)據(jù)就可以獲得較高精度的AP定位的方法，利用定向天線各角度增益不同的特點(diǎn)，根據(jù)其在不同位置和不同角度上收到的信號(hào)強(qiáng)度，使用一種基于概率密度的定位算法，對(duì)AP的位置進(jìn)行估計(jì)。與已有算法相比，本文算法具有采集數(shù)據(jù)少而定位精度高的優(yōu)點(diǎn)。

2 基于概率密度的定位算法

2.1 基本思想

傳統(tǒng)利用定向天線進(jìn)行AP定位時(shí)，在各測(cè)量點(diǎn)上將定向天線旋轉(zhuǎn)一周，記錄并比較各角度的信號(hào)強(qiáng)度，然后取某一個(gè)角度(一般是信號(hào)強(qiáng)度最強(qiáng)的角度)作為AP的方向。這樣做能夠在當(dāng)前測(cè)量點(diǎn)獲得待定位AP的方向，但在復(fù)雜環(huán)境中，由于反射、衍射等多種因素，使得情況變得復(fù)雜。文獻(xiàn)[16]分析了使用信號(hào)強(qiáng)度最大的角度作為AP的方向時(shí)，所得的角度誤差受環(huán)境的影響程度：當(dāng)在比較簡(jiǎn)單的環(huán)境中，例如操場(chǎng)上，在各測(cè)量點(diǎn)上得到的方向大多指向AP的真實(shí)位置，平均角度誤差較??；但在復(fù)雜環(huán)境中，例如辦公環(huán)境，在各測(cè)量點(diǎn)上得到的方向比較雜亂無(wú)章，平均角度誤差達(dá)到55°，因此僅以信號(hào)強(qiáng)度最大的角度作為AP的方向來(lái)估計(jì)AP的位置不是很精確。在此基礎(chǔ)上，文獻(xiàn)[16]中提出了一種方法來(lái)估計(jì)AP的位置，將在所有測(cè)量點(diǎn)上得到的AP的方向使用k-means方法進(jìn)行分類(lèi)，得到AP的多個(gè)位置鏡像，再使用啟發(fā)式算法從中找出AP的實(shí)際位置，但這種方法只選取信號(hào)強(qiáng)度最大的角度，忽略了測(cè)量過(guò)程中得到的其它信息，使得需要在很多點(diǎn)收集很多數(shù)據(jù)才能達(dá)到較好的定位精度。對(duì)此，本文認(rèn)為定向天線在旋轉(zhuǎn)過(guò)程中得到的各角度的信號(hào)強(qiáng)度不宜輕易丟棄，雖然在這些角度上的信號(hào)強(qiáng)度不是最大的，但仍可利用這些值對(duì)AP的位置進(jìn)行估計(jì)，而不僅僅只是被用來(lái)相互比較之后就丟棄不用，本文正是基于這樣的思想，提出了一個(gè)基于概率密度的AP定位的算法(Probability Density algorithm for Access Point Localization, PDAPL)。

該算法的基本思想是：對(duì)整個(gè)實(shí)驗(yàn)區(qū)域進(jìn)行分區(qū)，并建立一張對(duì)應(yīng)的概率密度表，表中每個(gè)位置的值表示AP在相應(yīng)單元格的可能性。當(dāng)在某個(gè)測(cè)量點(diǎn)的某個(gè)角度檢測(cè)到待定位AP時(shí)，根據(jù)信號(hào)強(qiáng)度計(jì)算AP落在各單元格的可能性，并累加到概率密度表中。經(jīng)過(guò)少量點(diǎn)少量角度的數(shù)據(jù)收集和計(jì)算，最終選擇某點(diǎn)作為AP的位置。

2.2 理論基礎(chǔ)

大量研究表明，在僅考慮地面反射波的情況下，無(wú)線信號(hào)遵循對(duì)數(shù)距離路徑損耗模型[18]，即

其中Pr表示與發(fā)射源距離為d處接收到的信號(hào)強(qiáng)度，以dBm為單位；P0表示與發(fā)射源距離為d0處接收到的信號(hào)強(qiáng)度；Gt表示發(fā)射天線的增益；Gr表示接收天線的增益；n是路徑損耗指數(shù)，表明損耗隨距離增長(zhǎng)的速率，與周?chē)h(huán)境有關(guān)；Xg表示一個(gè)高斯分布的隨機(jī)變量。

2.3 算法流程

2.3.1 概率計(jì)算流程 假設(shè)定向天線在第i個(gè)測(cè)量點(diǎn)(位置記為(xi,yi))的第j個(gè)角度(即天線的方向，記為θj)檢測(cè)到待定位AP時(shí)(其信號(hào)強(qiáng)度值記為RSSij)，計(jì)算AP落在單元格k(位置記為(xk,yk))的概率，過(guò)程如下：

(1)計(jì)算單元格到測(cè)量點(diǎn)的距離Dk和單元格相對(duì)于測(cè)量點(diǎn)的角度βk，其中

(2)根據(jù)天線的方向θj和單元格相對(duì)于測(cè)量點(diǎn)的角度βk，計(jì)算出單元格相對(duì)于天線的角度Δk(0o≤Δk＜360o)，其計(jì)算公式為

根據(jù)天線的輻射方向圖得到天線相對(duì)于單元格的增益Gk；

(3)根據(jù)Dk和Gk，利用式(1)可以求出若AP在當(dāng)前單元格，在當(dāng)前測(cè)量點(diǎn)能夠收到的理論信號(hào)強(qiáng)度值Tk，并根據(jù)式(4)將Tk轉(zhuǎn)化為能夠測(cè)量到的理論值DTk：

(4)計(jì)算AP落在單元格的概率。由于式(1)只考慮直射距離對(duì)信號(hào)強(qiáng)度的影響，而在實(shí)際的環(huán)境中，AP安裝在房間內(nèi)，室外的測(cè)量點(diǎn)收到的信號(hào)由于經(jīng)過(guò)了墻壁、樹(shù)木及其它建筑物的反射、繞射等多種因素的干擾，計(jì)算出來(lái)的理論值應(yīng)大于實(shí)際測(cè)量到的信號(hào)強(qiáng)度，因此如果在某個(gè)單元格計(jì)算出來(lái)的信號(hào)強(qiáng)度的理論值小于實(shí)際測(cè)量值時(shí)，說(shuō)明AP落在該單元格的可能性很小，這時(shí)將Pm(一個(gè)相對(duì)比較大的數(shù))作為其概率值；否則將其差值作為該單元格的概率值。

2.3.2 PDAPL算法流程

(1)初始化 將整個(gè)實(shí)驗(yàn)區(qū)域進(jìn)行分區(qū)，每個(gè)單元格的大小設(shè)置為CS×CS, CS的單位是m，實(shí)驗(yàn)區(qū)域總共劃分為A×B個(gè)單元格；建立一個(gè)A×B的概率密度表Pr，表中的值表示AP落在相應(yīng)單元格的可能性，值越小，表示AP落在相應(yīng)單元格的可能性越大。初始化表中所有的值為0；

(2)預(yù)處理 將在各測(cè)量點(diǎn)和各角度收集到的信號(hào)強(qiáng)度進(jìn)行處理，得到與待定位AP有關(guān)的記錄集，記為

其中，N表示測(cè)量點(diǎn)的個(gè)數(shù)；Mi表示在當(dāng)前測(cè)量點(diǎn)測(cè)量的角度的個(gè)數(shù)；Loci表示測(cè)量點(diǎn)的位置，其坐標(biāo)用(xi,yi)表示，單位為m; θj表示定向天線的角度，從正北方向順時(shí)針旋轉(zhuǎn)的角度，0≤θj＜360; RSSij表示在當(dāng)前測(cè)量點(diǎn)的當(dāng)前角度收集的信號(hào)強(qiáng)度值。

(3)更新概率密度表 對(duì)上述的每條記錄，對(duì)所有的單元格，分別調(diào)用2.3.1的過(guò)程計(jì)算概率值。假如根據(jù)某條記錄計(jì)算單元格k的概率值為DIk，按照式(6)更新概率密度表為

(4)計(jì)算AP的位置 當(dāng)對(duì)所有的記錄都完成上述過(guò)程后，會(huì)得到表示最終結(jié)果的矩陣，每個(gè)元素標(biāo)記相應(yīng)單元格的概率值，值越小，表示AP落在相應(yīng)單元格的可能性越大。為了避免某點(diǎn)的值偏小但周?chē)闹刀己艽蟮那闆r，在這個(gè)矩陣中，取一個(gè)大小為Ar×Ar的小區(qū)域(Ar的單位是1，表示含有多少個(gè)單元格)，其平均值最小，將這個(gè)區(qū)域作為AP最有可能存在的區(qū)域，取其中點(diǎn)作為AP的位置。

2.4 算法分析

假設(shè)在某測(cè)量點(diǎn)的某個(gè)角度檢測(cè)到待定位AP，其信號(hào)強(qiáng)度記為RSSI，如圖1(a) 所示，三角形表示測(cè)量點(diǎn)的位置，黑色圓點(diǎn)表示兩個(gè)要計(jì)算概率值的單元格Cell1和Cell2的中心點(diǎn)，分別用d1和d2表示測(cè)量點(diǎn)與兩個(gè)單元格的距離，且d1?d2，且假定待定位AP的真實(shí)位置在Cell1中。根據(jù)式(5)分別計(jì)算兩個(gè)單元格的概率值：對(duì)于Cell1，若AP落在其中，在該測(cè)量點(diǎn)的這個(gè)角度接收到信號(hào)強(qiáng)度的理論值記為DT1，由于理論值的計(jì)算只考慮直射距離對(duì)信號(hào)強(qiáng)度的影響，所以DT1≥RSSI，則DI1＜50；對(duì)于Cell2，若AP落在其中，在該測(cè)量點(diǎn)的這個(gè)角度接收到信號(hào)強(qiáng)度的理論值記為DT2，由于d1?d2，那么可能DT2＜RSSI，則DI2=50。如此計(jì)算所有單元格的概率值，會(huì)得到一個(gè)區(qū)域。區(qū)域內(nèi)的單元格其概率值較小，區(qū)域外的單元格其概率值較大，當(dāng)然該區(qū)域的形狀可能是不規(guī)則的，但一定包含AP的真實(shí)位置所在的單元格，在圖中用以測(cè)量點(diǎn)為中心的圓大致表示該區(qū)域。

當(dāng)在某個(gè)測(cè)量點(diǎn)的多個(gè)角度進(jìn)行測(cè)量后，會(huì)使得該區(qū)域逐漸縮小。當(dāng)計(jì)算多個(gè)測(cè)量點(diǎn)后，該區(qū)域會(huì)縮小直至AP的真實(shí)位置，如圖1(b) 所示，黑色圓點(diǎn)表示AP的真實(shí)位置，三角形表示測(cè)量點(diǎn)的位置，當(dāng)測(cè)量一個(gè)測(cè)量點(diǎn)的多個(gè)角度后，經(jīng)過(guò)概率值的累加會(huì)使得該區(qū)域逐漸縮小，當(dāng)計(jì)算多個(gè)測(cè)量點(diǎn)后，該區(qū)域會(huì)縮小至AP的真實(shí)位置。

圖1 算法分析

3 測(cè)試

3.1 數(shù)據(jù)獲取

為了能夠自動(dòng)獲取信息并減少各設(shè)備之間的誤差，本文設(shè)計(jì)了一個(gè)基于Arduino1)) www.arduino.cc的智能小車(chē)，上面裝載GPS模塊和電子羅盤(pán)模塊，GPS模塊用來(lái)獲得當(dāng)前的坐標(biāo)，電子羅盤(pán)模塊用來(lái)獲得當(dāng)前天線的方向，使用兩種定向天線來(lái)觀察其對(duì)定位的影響，其中定向天線的輻射方向圖通過(guò)實(shí)驗(yàn)獲得，在空曠的場(chǎng)地上，獲得定向天線各個(gè)角度的信號(hào)強(qiáng)度，并與全向天線的信號(hào)強(qiáng)度對(duì)比，得到各方向的增益，進(jìn)而得到定向天線的輻射方向圖。由于從輻射方向圖中讀到的天線增益會(huì)存在誤差，因此通過(guò)電子羅盤(pán)得到的天線的角度通過(guò)四舍五入精確到十位。信號(hào)強(qiáng)度通過(guò)調(diào)用Microsoft Native WiFi API獲取，由于單次測(cè)量可能存在誤差，所以對(duì)每次測(cè)量進(jìn)行多次，取其平均值作為測(cè)量結(jié)果以減少測(cè)量誤差，實(shí)驗(yàn)中每次測(cè)量20次。

3.2 實(shí)驗(yàn)環(huán)境介紹

選取學(xué)校辦公樓作為實(shí)驗(yàn)環(huán)境，其周?chē)袠?shù)木及其它建筑物，環(huán)境比較復(fù)雜，AP安裝在內(nèi)部的房間，主要選取一樓和二樓的AP作為待定位AP。本文提出的AP定位算法主要分為兩個(gè)階段：離線數(shù)據(jù)收集階段和AP定位階段。在離線數(shù)據(jù)收集階段中，如果在某測(cè)量點(diǎn)檢測(cè)到待定位的AP，則該測(cè)量點(diǎn)對(duì)該AP的定位有影響，否則該測(cè)量點(diǎn)對(duì)該AP的定位可視為無(wú)效。由于在收集數(shù)據(jù)時(shí)無(wú)法得知任何關(guān)于AP位置的信息，并且對(duì)于不同的待定位AP，對(duì)其定位有影響的測(cè)量點(diǎn)的位置是不同的，所以測(cè)量點(diǎn)只能根據(jù)環(huán)境隨機(jī)選取。在實(shí)驗(yàn)中待定位AP都在辦公樓內(nèi)部的房間里，所以測(cè)量點(diǎn)的位置大多在辦公樓附近的道路上。實(shí)驗(yàn)環(huán)境的各參數(shù)選取如表1所示。

表1 與實(shí)驗(yàn)環(huán)境有關(guān)的參數(shù)選取

辦公樓的周?chē)h(huán)境如圖2(a)所示，黑色虛線框內(nèi)的是實(shí)驗(yàn)所用的辦公樓。測(cè)量點(diǎn)及各AP的位置如圖2(b)所示，圓圈表示待定位AP及其真實(shí)位置，白色五角星表示部分測(cè)量點(diǎn)的位置。

圖2 實(shí)驗(yàn)環(huán)境介紹

3.3 參數(shù)選取

本文假設(shè)待定位AP的發(fā)射天線都是全～向天線，因此式(1)中Gt取0；路徑損耗n一般取26之間，文獻(xiàn)[8]中對(duì)校園環(huán)境做了相關(guān)實(shí)驗(yàn)，根據(jù)其中的α1,α2,αE的參數(shù)，本文將n取值為3；對(duì)于Pm，由于調(diào)用API獲得的信號(hào)強(qiáng)度在-50～-100 dBm之間，因此將其取值為最大的差值，即50。

3.4 結(jié)果分析

下面是根據(jù)實(shí)測(cè)得到的部分待定位AP的概率密度分布圖，顏色越深，表示其值越小，AP在相應(yīng)位置的可能性越大。圖中黑色實(shí)線框標(biāo)記的區(qū)域表示顏色最深的區(qū)域，白色箭頭指向的位置表示AP的實(shí)際位置。

由圖3～圖8可以看出，顏色較深的區(qū)域大概集中在某個(gè)區(qū)域內(nèi)，說(shuō)明估計(jì)的AP的位置大概在一個(gè)范圍內(nèi)，并且根據(jù)白色箭頭和黑色實(shí)線框的相對(duì)位置可以看出，實(shí)際的AP大概也都在這個(gè)范圍內(nèi)。使用本文算法對(duì)11個(gè)AP的定位結(jié)果如圖9所示，圖中橫軸是AP的序號(hào)，縱軸是誤差距離，表示估計(jì)位置與真實(shí)位置之間的距離，值越小，定位性能越好。從圖中可以看出，誤差距離最大是32 m，最小是5 m，平均值大概是20 m，說(shuō)明使用PDAPL進(jìn)行AP定位，能直接定位到房間內(nèi)。

下面討論各參數(shù)和不同設(shè)備對(duì)定位的影響，并與其它算法進(jìn)行對(duì)比。

(1)自身參數(shù)對(duì)定位的影響 本文算法涉及的參數(shù)包括：P0和Ar(Areasize)，其中P0對(duì)定位的影響在于：由于測(cè)量的信號(hào)強(qiáng)度在-50～-100 dBm之間，若P0取值過(guò)大或過(guò)小，會(huì)導(dǎo)致在很多單元格計(jì)算出來(lái)的理論值大于-50 dBm或小于-100 dBm，算法會(huì)將其進(jìn)行量化，這時(shí)很多單元格的概率值會(huì)相差很小甚至相同，最終導(dǎo)致平均誤差距離變大。因此本文考慮將P0分別取值為-30, -40, -50, -60, -70, Ar分別取值為1, 2, 3, 4, 5，考慮其對(duì)定位的影響，結(jié)果如圖10所示。圖中5條曲線表示P0取不同值時(shí)，Ar對(duì)平均誤差距離的影響。根據(jù)這5條曲線對(duì)應(yīng)的平均誤差距離的大小，可以看出，當(dāng)P0取-40時(shí)，平均誤差距離最??；并且，5條曲線都起伏不大，趨向于水平，說(shuō)明Ar的取值對(duì)定位無(wú)太大影響，簡(jiǎn)單起見(jiàn)，將其取值為1。后面涉及這兩個(gè)參數(shù)時(shí)默認(rèn)都是P0取-40, Ar取1。

圖3 AP1的概率密度分布圖

圖4 AP2的概率密度分布圖

圖5 AP3的概率密度分布圖

圖6 AP4的概率密度分布圖

圖7 AP5的概率密度分布圖

圖8 AP6的概率密度分布圖

(2)不同設(shè)備對(duì)定位的影響 為了探究不同增益的定向天線對(duì)定位是否有影響，本文選取兩種定向天線進(jìn)行實(shí)驗(yàn)，分別是14 dBi的平板天線和18 dBi的雙極化定向天線，將兩種定向天線放置在相同位置接收同一個(gè)AP的信號(hào)，得到輻射方向圖如圖11(a), 11(b)所示，可以看出這兩種天線的增益不一樣。圖11(c)為使用兩種定向天線進(jìn)行AP定位的誤差距離的累積分布函數(shù)(Cumulative Distribution Function, CDF)，可以看出這兩條曲線大致重合，說(shuō)明使用不同增益的定向天線對(duì)定位的影響不大，這是因?yàn)楸疚奶岢龅姆椒?，在?jì)算AP落在單元格的概率時(shí)，考慮的是信號(hào)強(qiáng)度的理論值與實(shí)際值之間的差值，其主要受環(huán)境影響，與定向天線的增益大小無(wú)關(guān)。后文實(shí)驗(yàn)中只選取一個(gè)定位天線。

圖9 使用PDAPL得到的AP誤差距離

(3)與其他算法進(jìn)行對(duì)比 為了評(píng)估算法的性能，使用的對(duì)比算法有：①DrivebyLoc[16]，將信號(hào)強(qiáng)度最強(qiáng)的角度作為AP的方向，記錄各測(cè)量點(diǎn)的AP的方向，利用k-means算法和啟發(fā)式算法估計(jì)AP的位置；②Distance[9]，取信號(hào)強(qiáng)度最大的值及相應(yīng)角度，利用信號(hào)傳播模型將RSS轉(zhuǎn)化為距離，根據(jù)測(cè)量點(diǎn)的位置和角度求出AP的位置；③AoA，根據(jù)兩個(gè)測(cè)量點(diǎn)估計(jì)的AP的方向估計(jì)AP的位置。

圖10 P0和Ar對(duì)平均誤差距離的影響

圖11 兩種定向天線的輻射方向圖及對(duì)定位的影響

實(shí)驗(yàn)中，在離線數(shù)據(jù)收集階段會(huì)在很多測(cè)量點(diǎn)上收集數(shù)據(jù)，文中總共有40個(gè)測(cè)量點(diǎn)，每個(gè)測(cè)量點(diǎn)的測(cè)量角度數(shù)總共為18，得到了大量的測(cè)量數(shù)據(jù)。在性能評(píng)估時(shí)，為了得到測(cè)量點(diǎn)的個(gè)數(shù)與誤差距離的關(guān)系，本文從所有測(cè)量點(diǎn)中隨機(jī)選取一定數(shù)量的測(cè)量點(diǎn)，將在這些測(cè)量點(diǎn)上得到的測(cè)量數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，然后使用PDAPL估計(jì)AP的位置，得到平均誤差距離。該過(guò)程重復(fù)多次，最終得到測(cè)量點(diǎn)個(gè)數(shù)與平均誤差距離的關(guān)系。同理，從所有的測(cè)量角度中隨機(jī)選取一定數(shù)量的角度，將在這些角度上得到的測(cè)量數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，計(jì)算平均誤差距離，重復(fù)多次隨機(jī)選取，最終得到測(cè)量角度數(shù)與平均誤差距離的關(guān)系。

圖12表示使用4種算法對(duì)11個(gè)AP定位的結(jié)果，其中測(cè)量點(diǎn)的個(gè)數(shù)為15，每個(gè)測(cè)量點(diǎn)測(cè)量的平均角度數(shù)為10。從圖12中可以看出，PDAPL的定位精度明顯高于另外3種算法，其最大的誤差距離為32 m，最小的為5 m左右，平均誤差距離為20 m左右，大概一個(gè)房間的范圍；而DrivebyLoc的最小的誤差距離為20 m，最大的達(dá)到80 m，平均誤差距離為50 m左右；Distance和AoA的誤差距離更大。這是由于在DrivebyLoc, Distance和AoA中，只用每個(gè)測(cè)量點(diǎn)中信號(hào)強(qiáng)度最大的角度值，而總共的測(cè)量點(diǎn)個(gè)數(shù)只有15個(gè)，每個(gè)AP平均只有5個(gè)測(cè)量點(diǎn)接收到相應(yīng)的信號(hào)，測(cè)量點(diǎn)個(gè)數(shù)比較少，可利用信息比較少，導(dǎo)致較大的誤差；并且Distance直接利用對(duì)數(shù)距離傳播模型，AoA直接利用信號(hào)強(qiáng)度最大的角度，這兩種方法中，每次的測(cè)量值都會(huì)對(duì)AP的位置產(chǎn)生直接影響，可能會(huì)因?yàn)槟炒蔚臏y(cè)量誤差或模型不合適導(dǎo)致平均誤差距離變大，因此這兩種方法的定位性能低于另外兩種；而本文提出的PDAPL，利用的是每個(gè)測(cè)量點(diǎn)的所有角度的信號(hào)強(qiáng)度，并且每次不是估計(jì)出一個(gè)AP的方向或位置，而是對(duì)整個(gè)實(shí)驗(yàn)區(qū)域的概率進(jìn)行估計(jì)，相對(duì)于另3種方法而言，可利用的信息比較多，且不會(huì)因某次測(cè)量對(duì)結(jié)果產(chǎn)生很大的影響，因此定位的誤差較小。

圖13為不同算法中測(cè)量點(diǎn)的個(gè)數(shù)對(duì)平均距離誤差的影響，其中每個(gè)測(cè)量點(diǎn)平均測(cè)量的角度數(shù)為10。從圖中可以看出，初始情況下，當(dāng)測(cè)量點(diǎn)的個(gè)數(shù)為15時(shí)，PDAPL的平均距離誤差值最小，DrivebyLoc其次，Distance和AoA比較大；隨著測(cè)量點(diǎn)個(gè)數(shù)的增加，4種算法的平均誤差距離都有所降低，其中，PDAPL降低得比較緩慢，并且一直是最低的，說(shuō)明當(dāng)只有15個(gè)測(cè)量點(diǎn)時(shí)，定位能力已經(jīng)比較好；DrivebyLoc降低得最為明顯，當(dāng)增加至40個(gè)測(cè)量點(diǎn)時(shí)，其值和PDAPL的差不多，這是由于DrivebyLoc中記錄各測(cè)量點(diǎn)估計(jì)的AP的方向，當(dāng)測(cè)量點(diǎn)數(shù)量增加時(shí)，得到的估計(jì)AP方向較多，進(jìn)而能夠得到較小的定位誤差。當(dāng)需要達(dá)到相同的定位精度時(shí)，PDAPL只需要15個(gè)測(cè)量點(diǎn)，而DrivebyLoc需要35個(gè)，Distance和AoA需要的更多。因此當(dāng)每個(gè)測(cè)量點(diǎn)平均測(cè)量的角度數(shù)相同時(shí)，PDAPL需要的測(cè)量點(diǎn)最少，并且定位精度較高。

圖14表示每個(gè)測(cè)量點(diǎn)平均測(cè)量的角度數(shù)對(duì)平均距離誤差的影響，其中測(cè)量點(diǎn)的個(gè)數(shù)為15。從圖14中可以看出，當(dāng)每個(gè)測(cè)量點(diǎn)測(cè)量的角度數(shù)為2時(shí)，4種算法的平均誤差距離都很大；隨著角度數(shù)量的增加，4種算法的平均誤差距離都顯著下降，其中PDAPL和DrivebyLoc下降得最為明顯，Distance和AoA降低得較為平緩，不過(guò)當(dāng)角度個(gè)數(shù)增加時(shí)，測(cè)量花費(fèi)的時(shí)間和人力也會(huì)相應(yīng)增加。從圖14中可以看出，當(dāng)測(cè)量的角度數(shù)為12時(shí)，PDAPL的平均誤差距離為20 m, DrivebyLoc的平均誤差距離為40 m；當(dāng)測(cè)量的角度數(shù)為18時(shí)，PDAPL的平均誤差距離為15 m, DrivebyLoc的平均誤差距離為21 m。當(dāng)需要達(dá)到相同的定位精度時(shí)，PDAPL需要的角度數(shù)為10，而DrivebyLoc需要的角度數(shù)為18，另外兩種方法需要的角度數(shù)更多。因此，當(dāng)測(cè)量點(diǎn)的個(gè)數(shù)相同時(shí)，PDAPL需要測(cè)量的角度數(shù)最少，并且定位精度較高。

圖12 不同算法的誤差距離

圖13 測(cè)量點(diǎn)的個(gè)數(shù)對(duì)定位的影響

圖14 測(cè)量的角度數(shù)對(duì)定位的影響

從上面的分析中可以得出，本文提出的PDAPL只需要在少量點(diǎn)和少量角度收集數(shù)據(jù)，就能得到較好的定位精度。在需要得到相同定位精度時(shí)，PDAPL所需要的測(cè)量點(diǎn)和測(cè)量角度數(shù)只是DrivebyLoc的一半左右，比Distance和AoA更少。在相同數(shù)量的測(cè)量點(diǎn)和測(cè)量角度時(shí)，PDAPL的定位精度相對(duì)于DrivebyLoc提升了50%左右。

4 結(jié)論

本文研究了一種利用定向天線對(duì)AP的位置進(jìn)行估計(jì)的算法，并設(shè)計(jì)了一個(gè)基于Arduino的智能小車(chē)來(lái)自動(dòng)獲取相關(guān)數(shù)據(jù)。該算法利用定向天線各方向增益不同的特點(diǎn)，通過(guò)多點(diǎn)多角度的測(cè)量，獲取待定位AP的信號(hào)，根據(jù)測(cè)量點(diǎn)信號(hào)強(qiáng)度的理論值和實(shí)際值之差估算AP在實(shí)驗(yàn)區(qū)域各點(diǎn)的概率，最后通過(guò)對(duì)整個(gè)區(qū)域的概率密度表進(jìn)行分析，估算出AP的位置。實(shí)驗(yàn)結(jié)果表明，本文算法只需要在少量點(diǎn)和少量角度收集并記錄信號(hào)強(qiáng)度，就可以得到較好的定位精度。在需要得到相同定位精度的情況下，PDAPL所需要的測(cè)量點(diǎn)和測(cè)量角度只是DrivebyLoc的一半左右，比Distance和AoA更少。在相同的測(cè)量點(diǎn)和測(cè)量角度數(shù)時(shí)，PDAPL的定位精度相對(duì)于DrivebyLoc提升了50%左右，比Distance和AoA提升得更多。

[1] Liu Hui, Darabi H, Banerjee P, et al.. Survey of wireless indoor positioning techniques and systems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2007, 37(6): 1067-1080.

[2] Bialer O, Raphaeli D, and Weiss A J. Maximum-likelihood direct position estimation in dense multipath[J]. IEEE Transactions on Vehicular Technology, 2013, 62(5): 2069-2079.

[3] Wang Gang, Li You-ming, and Ansari N. A semidefinite relaxation method for source localization using TDOA and FDOA measurements[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 853-862.

[4] Sen S, Lee J, Kim K H, et al.. Avoiding multipath to revive inbuilding WiFi localization[C]. Proceedings of 11th Annual International Conference on Mobile Systems, Applications, and Services, Taipei, 2013: 249-262.

[5] Liu Hong-bo, Yang Jie, Sidhom S, et al.. Accurate WiFi based localization for smartphones using peer assistance[J]. IEEE Transactions on Mobile Computing, 2014, 13(10): 2199-2214.

[6] Ji M, Kim J, Cho Y, et al.. A novel WiFi AP localization method using monte carlo path-loss model fitting simulation[C]. Proceedings of IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), London, 2013: 3487-3491.

[7] Koo J and Cha H. Localizing WiFi access points using signal strength[J]. IEEE Communications Letters, 2011, 15(2): 187-189.

[8] Roberts B and Pahlavan K. Site-specific RSS signature modeling for WiFi localization[C]. Proceedings of Global Telecommunications Conference, Honolulu, HI, 2009: 1-6.

[9] Le T M, Liu Ren-ping, and Hedley M. Rogue access point detection and localization[C]. Proceedings of IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), Sydney, NSW, 2012: 2489-2493.

[10] Rahman A, Amiruddin M, Dashti M, et al.. Localization of unknown indoor wireless transmitter[C]. Proceedings of 2013 International Conference on Localization and GNSS(ICL-GNSS), Turin, 2013: 1-6.

[11] Chun S M, Lee S M, Nah J W, et al.. Localization of Wi-Fi access point using smartphone's GPS information[C]. Proceedings of 2011 International Conference on Selected Topics in Mobile and Wireless Networking (iCOST), Shanghai, 2011: 121-126.

[12] Han D, Andersen D G, Kaminsky M, et al.. Access point localization using local signal strength gradient[C]. Proceeding of Passive and Active Network Measurement, Seoul, Korea, 2009: 99-108.

[13] Achtzehn A, Simic L, Gronerth P, et al.. A propagation-centric transmitter localization method for deriving the spatial structure of opportunistic wireless networks[C]. Proceedings of 10th Annual Conference on Wireless On-demand Network Systems and Services (WONS), Banff, AB, 2013: 139-146.

[14] Koo J and Cha H. Unsupervised Locating of WiFi access points using smartphones[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2012, 42(6): 1341-1353.

[15] Chen Yin-jie, Liu Zhong-li, Fu Xin-wen, et al.. Theory underlying measurement of AOA with a rotating directional antenna[C]. Proceedings of IEEE INFOCOM, Turin, 2013: 2490-2498.

[16] Subramanian A P, Deshpande P, Gaojgao J, et al.. Drive-by localization of roadside WiFi networks[C]. Proceedings of 27th Conference on Computer Communications, Phoenix, AZ, 2008: 718-725.

[17] Zhang Zeng-bin, Zhou Xia, Zhang Wei-le, et al.. I am the antenna: accurate outdoor ap location using smartphones[C]. Proceedings of 17th Annual International Conference on Mobile Computing and Networking, Las Vegas, Nevada, USA, 2011: 109-120.

[18] Akl R G, Tummala D, and Li Xin-rong. Indoor propagation modeling at 2.4 GHz for IEEE 802.11 networks[C]. Proceedings of Sixth International Association of Science and Technology for Development (IASTED) International Multi-Conference on Wireless and Optical Communications, Banff, Alberta, Canada, 2006: 120-150.

陳 兵： 男，1970年生，教授，博士生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、通信安全.

楊小玲： 女，1990年生，碩士生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò).

A WLAN Access Point Localization Algorithm Based on Probability Density

Chen Bing Yang Xiao-ling
(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

The Access Point (AP) in Wireless Local Area Network (WLAN) can be localized. In this paper, an AP Localization algorithm based on the Probability Density (PDAPL) is proposed. First, the region is portioned into several cells. Then, the probability of each cell is calculated according to the receive signal strength from the directional antenna in different locations and different angles, and a probability statistical table is constructed. Finally, the location of AP is assessed. Experiment results demonstrate that the proposed algorithm does not require a lot of data and can obtain relative high accuracy with a small number of measurement points and angles. Compared with DrivebyLoc, Distance, and AoA, half of or fewer measurement points and angles are needed in the case of the same accuracy with PDAPL. And for the same measurement points and angles, the accuracy of PDAPL is improved about 50% compared with DrivebyLoc.

Wireless communication; Access Point (AP) localization; Directional antenna; Probability density

TN92

： A

：1009-5896(2015)04-0855-08

10.11999/JEIT140661

2014-05-21收到，2014-10-31改回

江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金(BY2013003-03)資助課題

*通信作者：楊小玲 yxl_9009@163.com