王麗園，吳沐陽，吳家皋,2

(1.南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003；2.東南大學(xué) 計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室，江蘇 南京 211189)

基于WIFI BSSID相似度和RSSI概率分布的定位算法

王麗園1，吳沐陽1，吳家皋1,2

(1.南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003；2.東南大學(xué) 計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室，江蘇 南京 211189)

隨著高校的擴大，教室的增多，以及無線網(wǎng)絡(luò)覆蓋率的增大，能夠精確定位在校人員所在的教室位置具有重大意義?；谛盘枏姸鹊亩ㄎ凰惴ㄊ乾F(xiàn)今無線網(wǎng)絡(luò)定位的主要方法。在已有算法的基礎(chǔ)上，針對校園環(huán)境，提出了基于WIFI BSSID相似度和RSSI概率分布的定位算法。該算法先將當(dāng)前掃描的BSSID集合與事先采集的數(shù)據(jù)庫中的BSSID集合進(jìn)行相似度計算，相似度高的位置可判定為定位位置。若存在多個位置相似度基本相同，則進(jìn)一步根據(jù)信號強度的概率分布進(jìn)行概率加權(quán)運算，權(quán)值最大的教室位置即為定位位置。實驗結(jié)果表明，該定位算法在校園室內(nèi)定位中可以提高定位精確度。因此，基于該校園室內(nèi)定位算法，可以有助于精確定位在校人員所在教室位置，給在校人員的學(xué)習(xí)與工作帶來便捷。

基本服務(wù)集標(biāo)識符；信號強度；相似性；概率；室內(nèi)定位

1 概 述

隨著無線網(wǎng)絡(luò)的發(fā)展及移動終端處理能力的提高，越來越多的用戶希望通過移動終端享受各種便捷服務(wù)。移動用戶希望在不同地點、不同時間有不同的服務(wù)體驗。移動終端中自帶的全球定位系統(tǒng)模塊(Global Positioning System,GPS)、無線局域網(wǎng)(Wireless Fidelity,WIFI)給定位帶來了便捷。在室外環(huán)境中，用戶的密度較低，GPS是一個較好的選擇。然而，在復(fù)雜的室內(nèi)環(huán)境中，GPS受其自身限制和環(huán)境影響，并不能在室內(nèi)使用[1]。而校園中的WLAN由一個或多個無線接入點構(gòu)成，更易確定位置[2]。因此，WIFI在室內(nèi)定位中更具優(yōu)勢。

現(xiàn)有的無線定位技術(shù)主要有基于到達(dá)時間(Time of Arrival,TOA)、到達(dá)時間差(Time Difference of Arrival,TDOA)、信號到達(dá)角度(Angle of Arrival,AOA)和信號強度(Received Signal Strength Indicator,RSSI)四種方式。TOA[3]是基于信號到達(dá)時間測距的算法，TDOA[4]是利用發(fā)送的兩種不同信號間的到達(dá)時間差進(jìn)行測距。這兩種方法要求系統(tǒng)精確同步，而校園環(huán)境訪問接入點AP(Access Point)分布有限，傳輸時延可以忽略不計，因此不宜采用。AOA[5]是基于信號到達(dá)角度進(jìn)行測距，需要增加額外的硬件設(shè)施。基于RSSI[6-7]的算法不需要額外的硬件，成本低，適用范圍廣。文獻(xiàn)[8]提出一種基于RSSI的貝葉斯室內(nèi)定位算法，該算法通過RSSI預(yù)處理得到初始坐標(biāo)，對其進(jìn)行貝葉斯處理得到準(zhǔn)確坐標(biāo)，該算法降低了定位誤差。

基于RSSI定位的算法中，根據(jù)數(shù)據(jù)庫中信號指紋表示方式的不同可分為兩類：基于概率的定位方法和確定性的定位算法。使用確定性的定位算法是通過求每個節(jié)點的信號強度的平均值來估計移動點位置。如K鄰近算法(K-NearestNeighborhood,KNN)[9-10]，通過在位置指紋庫中尋找與未知節(jié)點最接近的多個參考點的平均值，作為未知節(jié)點的位置。盡管KNN在算法復(fù)雜度與定位精度上具有一定的優(yōu)勢，但是由于K值的固定，最終會影響某些位置的定位精確度?；诟怕实亩ㄎ凰惴ㄒ卜Q貝葉斯概率算法[11]，通過條件概率為位置指紋建立模型，采用貝葉斯推理機制來推斷用戶所在位置。RoosT等提出了直方圖法[12]，該方法將信號強度劃分為若干區(qū)間，統(tǒng)計每個區(qū)間里信號強度出現(xiàn)的次數(shù)，將一個待定位的空間分為若干區(qū)域，每個區(qū)域?qū)?yīng)一個強度區(qū)間。盡管簡單可行，但定位精確度受信號干擾影響較大。文獻(xiàn)[13]提出了一種區(qū)域投票算法，該算法根據(jù)采樣點信號強度數(shù)據(jù)庫，求出每個區(qū)域?qū)?yīng)各個AP信號強度的最大值與最小值，存于數(shù)據(jù)庫，在實時定位階段根據(jù)所采集的信號信息給對應(yīng)區(qū)域投一票，取最多票數(shù)的區(qū)域為定位定點。該算法利用信號強度的變化特征，定位結(jié)果準(zhǔn)確。然而，實驗測試表明，在校園環(huán)境中，由于不同教室的AP信號強度范圍比較相似，因此算法定位精確度較小。

文中采用基于概率的RSSI定位算法。在文獻(xiàn)[13]的基礎(chǔ)上，結(jié)合信號強度概率分布的特點，提出了基于WIFI基本服務(wù)集標(biāo)識符(BasicServiceSetIDentifier，BSSID)相似度和RSSI概率分布的室內(nèi)定位算法。該算法在第一階段將當(dāng)前位置的BSSID集合與數(shù)據(jù)庫中的BSSID集合進(jìn)行相似度計算，排除不可識別位置。如果當(dāng)前位置存于數(shù)據(jù)庫，且數(shù)據(jù)相似度較大，則進(jìn)入第二階段，將信號強度分為若干段，根據(jù)每段的信號強度的概率分布，賦予權(quán)值。實驗結(jié)果表明，在校園環(huán)境中，該算法較區(qū)域投票算法，定位精度有所提高。

2 系統(tǒng)框架

基于信號強度的無線網(wǎng)絡(luò)定位系統(tǒng)主要分為離線訓(xùn)練與在線定位兩個階段，如圖1所示。

圖1 基于WIFI BSSID相似度和RSSI概率分布算法定位過程

在離線訓(xùn)練階段，通過手機采集大量地理位置的無線網(wǎng)絡(luò)信號信息，對這些數(shù)據(jù)進(jìn)行分析。根據(jù)數(shù)據(jù)規(guī)律，建立合適的位置信息數(shù)據(jù)庫—BSSID位置數(shù)據(jù)庫和信號強度概率分布數(shù)據(jù)庫。其中，BSSID位置數(shù)據(jù)庫記錄不同位置的BSSID集合，信號強度概率分布數(shù)據(jù)庫記錄不同BSSID的信號強度信息。

在在線定位階段，根據(jù)實時收集的BSSID及其信號強度調(diào)用定位算法，與數(shù)據(jù)庫進(jìn)行匹配計算，最終確定定位位置。

3 離線采樣階段

為了實現(xiàn)校園教室的精確定位，需要建立一個精確的校園地理信息指紋庫。通過每日不同時段的地理信息采集，將數(shù)據(jù)進(jìn)行匯總分析，建立合適的地理信息指紋庫。通過對數(shù)據(jù)表進(jìn)行匯總分析，進(jìn)行如下研究。

3.1 教室AP的BSSID相似度的研究

相鄰的教室AP的BSSID相似度較高，距離較遠(yuǎn)的教室BSSID相似度較低，對不同教室的BSSID集合進(jìn)行相似度分析。

文中通過Jaccard[14]相似系數(shù)來衡量兩個教室的BSSID集合的相似度。兩個教室Ti和Tj的BSSID相似度定義為：

(1)

例如：

S(Ti)={“00:15:70:7e:7f:8c”,“00:15:70:91:99:8c”,“5c:0e:8b:da:10:80”}

S(Tj)={“00:15:70:7e:7f:8c”,“00:15:70:91:66:50”,“00:15:70:91:99:8c”,“5c:0e:8b:da:10:80”}

J(Ti,Tj)=75%,，表示Ti和Tj兩個教室的BSSID相似度為75%。

部分測試結(jié)果如下所示(其中對應(yīng)的教室平面圖如圖2所示):

圖2 教室平面圖

J(2-104,2-103)=90.0%

J(2-104,2-107)=33.3%

J(2-106,2-107)=91.7%

J(2-107,2-103)=13.3%

通過數(shù)據(jù)分析，發(fā)現(xiàn)相距較遠(yuǎn)的教室BSSID相似度較低，而相鄰教室BSSID相似度較高。所以，BSSID相似度可以判別相距較遠(yuǎn)的教室。

基于以上分析，通過測量可獲得不同教室的BSSID集合。令T為所有教室的集合，并將其保存到數(shù)據(jù)庫中。定位時，將掃描熱點得到的BSSID集合與數(shù)據(jù)庫中的BSSID集合進(jìn)行匹配，根據(jù)計算得到的相似度確定位置。

3.2 同一BSSID信號強度的研究

針對特定的BSSID，通過先行的熱點掃描軟件進(jìn)行信號強度掃描，獲得同一BSSID在不同教室的信號強度概率分布。

通過大量數(shù)據(jù)分析可知，不同教室的同一BSSID信號強度概率分布不同。由于不同教室同一BSSID的信號強度范圍基本相似，如果單取最大值與最小值，則信號強度特征不能得到充分體現(xiàn)，因此不能進(jìn)行準(zhǔn)確定位?；谝陨戏治觯闹袑π盘枏姸冗M(jìn)行如下處理。

令P(Bi,Tj,x)表示BSSIDBi在教室Tj信號強度為x的概率。其中，信號強度x為整數(shù)，x∈[minRSSI,maxRSSI]，minRSSI,maxRSSI為信號強度的最小、最大值。概率歸一化條件要求：

(2)

將信號強度范圍[minRSSI,maxRSSI]從小到大以每段信號強度的范圍為h均勻分段，則M(k)=[minRSSI+kh,minRSSI+(k+1)h-1]，表示第k段的強度范圍。其中，k∈[0,L]，L為段數(shù)，L=「(maxRSSI-minRSSI+1?/h。

則BSSIDBi在教室Tj的第k段信號強度權(quán)重定義為：

(3)

通過采集數(shù)據(jù)得到信號強度概率分布P(Bi,Tj,x),將信號強度進(jìn)行分段處理，得到k段信號強度M(k)。將兩者結(jié)合運算得到信號強度權(quán)重W(Bi,Tj,k)，存于數(shù)據(jù)庫。

例如，教室分別為2-105、2-204、2-205，minRSSI=-92，maxRSSI=-73，若取h=6,則L=4，各段信號強度范圍：M(0)=[-92,-87],M(1)=[-86,-81],M(2)=[-80,-75],M(3)=[-74,-69]。經(jīng)過計算權(quán)重為：W(“5c:0e:8b:d7:40:90”,“2-105”,0)=12%,W(“5c:0e:8b:d7:40:90”,“2-204”,0)=78%,W(“5c:0e:8b:d7:40:90”,“2-205”,0)=62%,W(“5c:0e:8b:d7:40:90”,“2-105”,1)=27%,W(“5c:0e:8b:d7:40:90”,“2-204”,1)=2%,W(“5c:0e:8b:d7:40:90”,“2-205”,1)=14%,W(“5c:0e:8b:d7:40:90”,“2-105”,2)=23%,W(“5c:0e:8b:d7:40:90”,“2-204”,2)=16%,W(“5c:0e:8b:d7:40:90”,“2-205”,2)=18%,W(“5c:0e:8b:d7:40:90”,“2-105”,3)=38%,W(“5c:0e:8b:d7:40:90”,“2-204”,3)=14%,W(“5c:0e:8b:d7:40:90”,“2-205”,3)=6%。

將這些數(shù)據(jù)存于數(shù)據(jù)庫。實時定位時，如果多次掃描到“5c:0e:8b:d7:40:90”的BSSID，且信號強度為-91，范圍在[-92,-87]之內(nèi)，則給2-105教室權(quán)重加12，2-204教室權(quán)重加78，2-205權(quán)重加62。對實時掃描的每個BSSID的每段RSSI進(jìn)行權(quán)重處理，最終權(quán)重最大的教室即為定位教室。

4 實時定位階段

實時定位過程分為兩個階段，如圖3所示。

4.1 第一階段

掃描用戶所在區(qū)域N次，得到BSSID集合，通過一級數(shù)據(jù)庫，與數(shù)據(jù)庫中對應(yīng)BSSID集合匹配，進(jìn)行相似度計算。如果所有相似度都小于60%，則數(shù)據(jù)庫中不存在當(dāng)前定位位置，歸為不可識別的位置，結(jié)束定位。否則，當(dāng)前位置為可識別的位置，在此基礎(chǔ)上，如果相似度大于60%，且數(shù)據(jù)庫中只存在一個與之匹配的位置，則該位置為當(dāng)前定位位置。否則，掃描二級數(shù)據(jù)庫。

圖3 算法流程圖

4.2 第二階段

根據(jù)第一階段掃描得到的BSSID集合及對應(yīng)強度集合，針對每個BSSID，根據(jù)其信號強度，查找該強度在數(shù)據(jù)庫中位于哪段范圍，給對應(yīng)強度段中的位置增加對應(yīng)的權(quán)重。權(quán)重最大者即為定位位置。

基于WIFI BSSID相似度和RSSI概率分布的定位算法的偽代碼實現(xiàn)如下：

輸入：無；

輸出：Location,即定位位置。

Begin

掃描N次，得到BSSID的集合S1，對于Bi∈S1，記錄其信號強度RSSI的列表R(Bi)

ForeachTi∈T

計算S1和S(Ti)的相似度；

Endfor

If相似度都小于60%Then

Location:=Null，該位置不可識別；

ElseIf有且一個相似度大于60%Then

Location:=Ti,其中,J(Ti,T)>60%；

Else

將J(Ti,T)<60%過濾，得到T'

W(Tj)=0，?Tj∈T'

ForeachBi∈S

Foreachx∈R(Bi)

Ifx∈R(k)

W(Tj)=W(Tj)+W(Bi,Tj,k);

Endfor

Endfor

Location:=Tj使得W(Tj)取最大值；

EndIf

End

該算法復(fù)雜度分為兩部分：基于相似度算法與基于信號強度概率分布算法。相似度計算的平均時間復(fù)雜度為O(p)，信號強度概率分布算法平均時間復(fù)雜度為O(n×m×l)，總的平均時間復(fù)雜度為O(n×m×l)+O(p)。其中，p為教室—BSSID數(shù)據(jù)庫中數(shù)據(jù)記錄的條數(shù)；n為掃描得到的BSSID個數(shù)；m為不同BSSID對應(yīng)的強度個數(shù)；l為BSSID數(shù)據(jù)庫中數(shù)據(jù)記錄的條數(shù)。

5 算法測試

算法是在開發(fā)環(huán)境Eclipse下基于Android4.0實現(xiàn)的。測試設(shè)備是HUAWEIC8812，實驗地點是南京郵電大學(xué)教學(xué)樓。

5.1 室內(nèi)定位測試

由于定位一個教室時，可能會出現(xiàn)定位到周圍其他教室的錯誤結(jié)果。結(jié)合掃描信息和文中算法計算權(quán)值，將權(quán)重最大教室與實際所在教室進(jìn)行對比，驗證該定位算法的準(zhǔn)確性。

測試使用HUAWEI手機，對20個不同教室進(jìn)行定位準(zhǔn)確度測試，每隔30 s掃描一次教室熱點，共掃描4次，數(shù)據(jù)庫中每個BSSID信號強度以h=3為分段值。

實驗結(jié)果表明，基于WIFIBSSID相似度和RSSI概率分布算法定位精確度較高。

5.2 熱點掃描次數(shù)對精確度的影響

手機掃描熱點，干擾因素較多且耗電量較大。因此在實時定位階段選擇合適的掃描次數(shù)，不僅有助于提高定位精確度，同時能減少手機耗能。

圖4是掃描次數(shù)與定位精確度關(guān)系的折線圖。實驗結(jié)果表明，當(dāng)定位次數(shù)達(dá)到4次以上，可以在一定程度上避免干擾因素對定位結(jié)果的影響。因此，系統(tǒng)實時定位階段選擇每隔30 s進(jìn)行一次定位，共4次定位。

5.3 分段值h對定位精確度的影響

隨著定位數(shù)據(jù)庫的擴充，實時定位數(shù)據(jù)與數(shù)據(jù)庫的匹配速度會變慢，尋找合適的h值，可以降低算法的復(fù)雜度，從而完成快速準(zhǔn)確的定位。

圖4 掃描次數(shù)與精確度關(guān)系圖

實驗通過HUAWEIC8812，于南京郵電大學(xué)教二20個教室進(jìn)行測試，每個目標(biāo)地址共進(jìn)行10次測試，其中定位目標(biāo)教室時每隔30s掃描一次，共掃描4次。實驗結(jié)果如圖5所示。結(jié)果表明，當(dāng)h=3時，定位效果最好。

圖5 分段值h與定位精確度關(guān)系圖

5.4 投票區(qū)域選定算法與信號強度加權(quán)算法的對比

本次測試通過HUAWEI C8812，于南京郵電大學(xué)教二20個教室進(jìn)行測試，每個目標(biāo)地址共進(jìn)行10次測試，其中定位目標(biāo)教室時每隔30 s掃描一次，共掃描4次。其中數(shù)據(jù)庫中每個BSSID信號強度以h=3為分段值。實驗結(jié)果見圖6。

圖6 不同定位算法的對比

由圖可知，基于WIFIBSSID相似度和RSSI概率分布算法相比投票區(qū)域選定方法，在校園室內(nèi)定位中定位精確度更高。

6 結(jié)束語

基于對WIFI信號特征的分析，在已有算法的基礎(chǔ)上提出一種改進(jìn)的室內(nèi)定位算法—基于WIFIBSSID相似度和RSSI概率分布的算法。實驗結(jié)果表明，該算法較大提高了室內(nèi)定位精確度，但仍存在許多不足：指紋庫的建立耗時長且需不斷更新；同時，對于不同設(shè)備，指紋庫適用度低。

該算法可以運用于校園室內(nèi)定位，通過不同教室的定位，可以給在校人員的工作學(xué)習(xí)帶來便捷，具有很大的實用價值。

[1] 萬 群，郭賢生，陳章鑫.室內(nèi)定位理論、方法和應(yīng)用[M].北京：電子工業(yè)出版社，2012.

[2] 余 濤,黃書寶,葛昭攀,等.無線局域網(wǎng)環(huán)境下的位置服務(wù)研究[J].計算機工程,2005,31(14):122-124.

[3]LeeWCY.Mobilecommunicationengineering[M].NewYork:McGraw-Hill,1982:20-30.

[4] 史小紅.基于TDOA的無線定位方法及其性能分析[J].東南大學(xué)學(xué)報:自然科學(xué)版,2013,43(2):252-257.

[5]DengP,FanPZ.Anefficientposition-baseddynamiclocationalgorithm[C]//Internationalworkshoponautonomousdecentralizedsystems.[s.l.]:[s.n.],2000:36-39.

[6]HataM.Empiricalformulaforpropagationlossinlandmobileradioservices[J].IEEETransactionsonVehicularTechnology,1980,29(3):317-325.

[7] 朱明輝,張會清.基于RSSI的室內(nèi)測距模型的研究[J].傳感器與微系統(tǒng),2010,29(8):19-22.

[8] 彭玉旭，楊艷紅.一種基于RSSI的貝葉斯室內(nèi)定位算法[J].計算機工程，2012，38(10):238-240.

[9]OutemzabetS,NerguizianC.AccuracyenhancementofanindoorANN-basedfingerprintinglocationsystemusingKalmanfiltering[C]//IEEE19thinternationalsymposiumonpersonal,indoorandmobileradiocommunications.[s.l.]:IEEE,2008:1-5.

[10]RodriguesML,VieiraLFM,CamposMFM.Fingerprinting-basedradiolocalizationinindoorenvironmentsusingmultiplewirelesstechnologies[C]//IEEE22ndinternationalsymposiumonpersonal,indoorandmobileradiocommunications.Toronto,ON,Canada:IEEE,2011:1203-1207.

[11] 王洪春.貝葉斯公式與貝葉斯統(tǒng)計[J].重慶科技學(xué)院學(xué)報:自然科學(xué)版,2010,12(3):203-205.

[12]RoosT,MyllymakiP,TirriH,etal.AprobabilisticapproachtoWLANuserlocationestimation[J].InternationalJournalofWirelessInformationNetworks,2002,9(3):155-164.

[13] 儲海兵.基于無線局域網(wǎng)的定位追蹤技術(shù)研究[D].杭州:浙江大學(xué),2011.

[14]Jaccard.index[EB/OL].[2015-04-05].https://en.Wikipedia.org/wiki/Jaccard_index.

A Positioning Algorithm Based on WIFI BSSID Similarity and RSSI Probability Distribution

WANG Li-yuan1,WU Mu-yang1,WU Jia-gao1,2

(1.College of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China;2.Key Laboratory of Computer Network and Information Integration of Ministry of Education,Southeast University,Nanjing 211189,China)

With the expansion of universities,the increase of classroom as well as the wireless network coverage,to locate accurately the classroom of school personnel is of great significance.Positioning algorithm based on signal strength is popular for wireless network location.On the basis of the existing algorithms,a positioning algorithm based on WIFI Basic Service Set Identifier (BSSID) similarity and Received Signal Strength Indicator (RSSI) probability distribution is proposed for the campus environment.The similarity is calculated between the current scanned BSSID set and that collected beforehand in database,and the position with highest similarity can be determined to be current position.If there are many positions with approximate similarity,weight is calculated according to the probability distribution of the RSSI,and the position with the maximum weight is located.Experimental results show that the positioning algorithm can improve accuracy in campus indoor positioning.Thus,based on that,it can help locate the classroom of personnel and bring convenience to study and life of school personnel.

BSSID;RSSI;similarity;probability;indoor positioning

2015-11-22

2016-03-17

時間：2016-11-21

國家自然科學(xué)基金資助項目(61373139)；計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室(東南大學(xué))開放基金(K93-9-2014-05B)；南京郵電大學(xué)科研基金(NY214063)

王麗園(1993-)，女，研究方向為移動計算；吳家皋，博士，副教授，CCF會員，研究方向為計算機網(wǎng)絡(luò)、GIS應(yīng)用等。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1633.016.html

TP301.6

A

1673-629X(2016)12-0200-05

10.3969/j.issn.1673-629X.2016.12.043