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

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

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

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

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

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

隨著高校的擴大，教室的增多，以及無線網絡覆蓋率的增大，能夠精確定位在校人員所在的教室位置具有重大意義。基于信號強度的定位算法是現今無線網絡定位的主要方法。在已有算法的基礎上，針對校園環境，提出了基于WIFI BSSID相似度和RSSI概率分布的定位算法。該算法先將當前掃描的BSSID集合與事先采集的數據庫中的BSSID集合進行相似度計算，相似度高的位置可判定為定位位置。若存在多個位置相似度基本相同，則進一步根據信號強度的概率分布進行概率加權運算，權值最大的教室位置即為定位位置。實驗結果表明，該定位算法在校園室內定位中可以提高定位精確度。因此，基于該校園室內定位算法，可以有助于精確定位在校人員所在教室位置，給在校人員的學習與工作帶來便捷。

基本服務集標識符；信號強度；相似性；概率；室內定位

1 概 述

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

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

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

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

2 系統框架

基于信號強度的無線網絡定位系統主要分為離線訓練與在線定位兩個階段，如圖1所示。

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

在離線訓練階段，通過手機采集大量地理位置的無線網絡信號信息，對這些數據進行分析。根據數據規律，建立合適的位置信息數據庫—BSSID位置數據庫和信號強度概率分布數據庫。其中，BSSID位置數據庫記錄不同位置的BSSID集合，信號強度概率分布數據庫記錄不同BSSID的信號強度信息。

在在線定位階段，根據實時收集的BSSID及其信號強度調用定位算法，與數據庫進行匹配計算，最終確定定位位置。

3 離線采樣階段

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

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

相鄰的教室AP的BSSID相似度較高，距離較遠的教室BSSID相似度較低，對不同教室的BSSID集合進行相似度分析。

文中通過Jaccard[14]相似系數來衡量兩個教室的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%。

部分測試結果如下所示(其中對應的教室平面圖如圖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%

通過數據分析，發現相距較遠的教室BSSID相似度較低，而相鄰教室BSSID相似度較高。所以，BSSID相似度可以判別相距較遠的教室。

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

3.2 同一BSSID信號強度的研究

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

通過大量數據分析可知，不同教室的同一BSSID信號強度概率分布不同。由于不同教室同一BSSID的信號強度范圍基本相似，如果單取最大值與最小值，則信號強度特征不能得到充分體現，因此不能進行準確定位。基于以上分析，文中對信號強度進行如下處理。

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

(2)

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

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

(3)

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

例如，教室分別為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]。經過計算權重為：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%。

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

4 實時定位階段

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

4.1 第一階段

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

圖3 算法流程圖

4.2 第二階段

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

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

輸入：無；

輸出：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

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

5 算法測試

算法是在開發環境Eclipse下基于Android4.0實現的。測試設備是HUAWEIC8812，實驗地點是南京郵電大學教學樓。

5.1 室內定位測試

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

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

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

5.2 熱點掃描次數對精確度的影響

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

圖4是掃描次數與定位精確度關系的折線圖。實驗結果表明，當定位次數達到4次以上，可以在一定程度上避免干擾因素對定位結果的影響。因此，系統實時定位階段選擇每隔30 s進行一次定位，共4次定位。

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

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

圖4 掃描次數與精確度關系圖

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

圖5 分段值h與定位精確度關系圖

5.4 投票區域選定算法與信號強度加權算法的對比

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

圖6 不同定位算法的對比

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

6 結束語

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

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

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

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

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

[4] 史小紅.基于TDOA的無線定位方法及其性能分析[J].東南大學學報:自然科學版,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的室內測距模型的研究[J].傳感器與微系統,2010,29(8):19-22.

[8] 彭玉旭，楊艷紅.一種基于RSSI的貝葉斯室內定位算法[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] 王洪春.貝葉斯公式與貝葉斯統計[J].重慶科技學院學報:自然科學版,2010,12(3):203-205.

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

[13] 儲海兵.基于無線局域網的定位追蹤技術研究[D].杭州:浙江大學,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

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

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

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