基于信息區分度的AP有效集構建方法

嚴維軒，朱立才*，季衍輝，李 永，楊 浩,3

(1.南京工業大學 計算機科學與技術學院，江蘇南京 211816；2.鹽城師范學院信息工程學院，江蘇鹽城 224001；3.中國科學技術大學蘇州高等研究院，江蘇蘇州 215123)

隨著無線網絡應用的不斷擴展，基于位置的服務（LBS）在日常生活中已不可或缺[1]。LBS一般分為室外和室內2個場景。在室外環境中，基于衛星信號的定位技術大都取得米級的定位精度，可以滿足大多數情況下室外LBS要求。然而，室內環境中的衛星信號由于受多種障礙物的阻擋，難以實現視距傳播，導致無法實現準確定位[2-3]。為此，研究人員提出利用部署多個接入點并結合指紋定位技術進行目標位置計算，以實現室內環境的有效LBS。

隨著室內定位場景的擴大，為實現高精度定位，需要部署更多的AP。在一定程度上，大量的AP有利于提升指紋地圖的分辨率。然而，隨著AP增多，定位過程的計算時間和能量消耗也急劇增多，嚴重影響用戶體驗。此外，大量增多的AP并不能提供更好的空間區分度，甚至會降低定位精度，并且增加定位時間，即出現“無效AP”的現象。因此，需要選擇合適的AP集合來進行定位。

目前，相關研究主要圍繞2個方面：單一AP選擇和多個AP組合。對于單一AP選擇來說，主要考慮的是AP點信號強度的分布特征。Max-Mean算法是AP單點選擇方法的開山之作[4-5]，通過計算AP點在地圖所有采樣點處的RSS平均值，選擇其若干個最大的AP用于位置估算，這是一種簡單易行的AP剔除方式。Chen等[6]提出了基于信息增益的AP選擇算法。Tao等[7]提出了一種AIPS算法，考慮信號噪聲，構造AP環，選擇環數最大的參考點作為最近的參考點，然后用區域生長算法搜索出環數較大的參考點來估計測試點的位置。Sadhukhan等[8]提出了一種ESC指紋定位系統聚類策略，通過應用1-way HCS進行AP聚類。Ranasinghe等[9]提出了一種基于圖神經網絡的無線大規模多輸入多輸出系統（M IMO）AP選擇算法。Pu等[10]提出一種利用稀疏恢復方式的AP定位方案。

與上述方式僅關注單個AP特征不同，多個AP選擇進一步考慮AP組合情形。Lin等[11]考慮了多個AP間的組合關系，提出基于組判別（GDB）的AP點選擇算法，其通過對組合重要性排序實現AP選擇，該算法利用支持向量機SVM中的風險函數評估每一組AP點子集的分值，并選擇分值最低的AP點子集作為算法的結果。Lee等[12]基于軟件定義網絡（SDN），提出無線網絡中提供最優AP的接入點選擇算法。Zhao等[13]應用Dixon準則通過W i-Fi信號穩定性、信號相關性、參考點識別能力等3個參數對AP進行篩選和選擇。M a等[14]結合使用距離度量學習和接入點選擇方法來權衡定位精度和時間消耗，提出了一種新穎的FIL系統。Li等[15]提出了一種基于非均勻量化RSS熵NQRE的定位模型來選擇合適的定位AP。Zhang等[16]提出了一種基于多目標優化的AP選擇算法來提高室內W i-Fi定位精度，自適應AP選擇算法可以應用于多種實際場景。Asad等[17]提出了一種客戶端節能AP選擇方法，用于在混合無線保真和輕保真網絡中提供服務質量。Tian等[18]利用Saleh–Valenzuela（S–V）信道模型分析了多徑信號對直接信號能量譜的影響，提出一種天線選擇方法。Xia等[19]提出接入點AP通過二進制模式選擇合適的發送或接收AP，實現同時為上行鏈路和下行鏈路用戶提供服務的目的。Van等[20]針對可檢測AP數量低、中和高的情況設計了3個分類器來實現AP聚類。

由上可知，選擇合適的AP集合的挑戰有：1）準確評估AP的定位能力；2）選擇出AP的有效組合。為此，本文提出一種基于信息區分度的AP有效集構建方法（EID），該方法通過評估每個AP的信號指紋對地圖的分辨度選擇合適的AP組合，在減少AP冗余的同時，提高定位精度。首先，采用信息區分度（ID，用BID表示）評估每個AP的指紋在不同點的差異；然后，設計基于信息區分度的增量聚類算法，獲得AP候選集。在實際場景中，AP不是固定不變的，而是會隨著定位需求增加或者減少，并且一些AP是通過電池供電，需要考慮其壽命，因此增量式聚類方式更加符合現實情形需求；最后，面向所構建的類，利用點集距離（DPS）最大原則設計有效集選擇策略，根據聚類結果和選擇要求，得到合適的AP有效集合。

1 基于區分度的AP有效集構建

1.1 基本思想

為實現高精度定位，本文提出一種基于信息區分度的AP有效集構建方法。其基本思想是：首先，為每個AP構建指紋地圖。然后，評估AP的空間分辨率，即對采樣點的區分能力，本文利用信息區分度表示采樣點間的差別，以展示AP對不同點的區分度，同時聚類同類型AP以構建有效集。為保證構建過程的魯棒性，設計了增量聚類算法，根據BID的大小進行逐步聚類；通過比較AP指紋與類地圖的相似度，判斷該AP是否被聚為同一類。最后，根據聚類結果和選擇要求，構建出合適的AP有效集。

EID方法如圖1所示。

圖1 EID方法框架Fig. 1 Framework of EID

EID方法具體步驟如下：

1）建立AP指紋集：對感知區域采樣，根據采樣位置為每個AP建立對應的指紋集。

2）計算區分度：處理指紋地圖的異常點；根據每個AP的指紋地圖計算相應的BID，并對所有AP按照BID進行從小到大排序。

3）增量聚類：每個類都有相應的類信息區分度（CID，用CCID表示）。在某一AP進行增量聚類時，從大到小對比CCID與每個類的相似度，判斷是否加入某一個類或者建立一個新類。同時，更新相應的類地圖和CCID。最后，得到AP的聚類結果。

4）構建AP有效集：將聚類結果中的類按CCID從大到小排序。然后，選擇CCID最大的類，將該類中每個AP與有效集（ES）比較相似度，并利用DPS最大的原則選擇合適的AP。該原則將AP與ES中所有元素相似度最小的值作為該AP與ES的DPS。然后，選擇DPS最大的AP加入到ES。按照這一原則，根據預先給定的選擇要求，得到合適的有效集。

1.2 建立AP指紋

在感知區域進行測量時，每個采樣位置能夠監測到多個AP的信號強度（RSS，用R表示）。若區域內有n個AP且共測量m個點，則AP的指紋集是R(Ai)=(r1i,r2i,···,rmi)，其中變量A表示AP。

每個AP都有2個屬性，即對采樣點的區分能力以及與其他AP的相似程度。前者用來判斷自身是否適合被用于定位，后者則用來決定該AP與其他AP是否為同類。

1.3 計算AP區分度

在實際定位中，會部署較多的AP以提升定位精度，但每個AP對采樣點的分辨能力不同。本文用區分度表示AP對不同采樣位置的區分能力，并用信息增益（IG，用DIG表示）和信息增益率（IGR，用EIGR表示）相結合的方式來計算BID。信息增益表示某個特征對整體不確定性的減小程度。對于AP來說，在采樣點間的信號值不相同的程度越大，則該AP的信息增益越大。換句話說，信息增益可以表示AP對感知區域采樣點的區別程度。然而，若某一AP產生的不同信號值較多，則會使該AP的信息增益遠大于其他AP。在實際場景中，這一情形往往是由于AP出現異常導致的。為此，本文進一步結合信息增益率來避免這一情形。

在一個基于網格（Grid）的定位系統中，令網格數為n，AP數為m。對于每個Ai(1 ≤i≤m)，每個網格G j(1 ≤j≤n)的信號強度可視為一個特征，即每個AP有n個特征。AP區分度的計算方式如下：

1）計算每個AP的信息增益：

首先，計算每個AP的信息熵：

式中，G表示網格集合，Gj為該網格中包含的采樣點數，P(G j)為該網格中采樣點數在整個地圖的占比。對于本文來說，每個網格包含1個采樣點。

然后，計算AP的條件熵：

式中，P(G j,R(Ai)=v)表示網格G j中Ai的信號強度R為v的概率，P(G j|R(Ai)=v)表示網格G j中Ai的信號強度R為v的條件概率。

由式（1）和（2）得Ai的信息增益：

1.4 設計增量聚類算法

區分度表示了AP對空間的分辨能力，可以代表其定位能力。與此同時，需要考慮AP指紋信號的空間分布情況。例如，若3個AP，分別為A1、A2和A3，并且BID(A1)>BID(A2)>BID(A3)。其中，A1和A2的位置較近，且均與A3的距離較遠，如圖2（a）所示。

根據3個AP的指紋信號空間分布，A1和A2相似，且與A3的差異較大。如圖2（b）～（d）所示，若選擇2個AP進行組合，{A1,A2}組合的定位效果顯然不如{A1,A3}或{A2,A3}組合。由于不同AP組合的定位能力差異非常明顯，為選擇出合適的AP有效集，需要對整個AP集合進行聚類。

圖2 不同位置AP的信號覆蓋Fig. 2 Signal coverage of different APs

本文利用增量聚類的思想，設計聚類算法AP_Cluster。為獲得合適的聚類結果，定義了類區分度，用來表示該類中AP的平均區分度，其計算方式為：

若類FL中有L個AP，則該類的CCID為：

AP_Cluster算法思想如下：

村黨支部書記邱祺才說，過去村里的土地全部包產到戶，村級財政幾乎沒有收入來源，村里需要的各項資金完全依賴上級撥款。捉襟見肘的集體收入導致資金的嚴重缺乏，產業發展一片空白，貧困落后的面貌始終難以改變。

1）將AP集合Set(A)按區分度BID從大到小排序；

2）選擇區分度最大的Amax，并將該AP從Set(A)刪除；

3）若聚類集合F有N個類，則Amax的指紋R(Amax)依次與集合中每個類Fi的所有元素對比相似度；

4）若Amax與第i個類Fi中所有元素的相似度均小于閾值，則將該AP加入到Fi，同時更新它的CCID；

5）否則，F中新建一個類{Amax}，且聚類的數量加1；

6）對所有類，按照CCID從大到小進行排序。

經過上述聚類方式，將相似度較高的AP聚為同一類。AP_Cluster算法流程如下：

算法1 AP_Cluster算法。

其中，Sort表示排序函數，順序為從大到??；Sim(a,b)表示a和b的相似度。

1.5 構建AP有效集

對AP進行聚類后，根據DPS最大原則和實際要求，選擇有效的AP集合。具體步驟如下：

1）初始化：聚類集合F中類數為N，所需AP數為M，AP有效集ES為空，被選擇類的數量游標T=2；

2）F1中BID最大的AP加入ES，并從F1中刪除該AP；

3）對于類FT中任一Aj，計算它與ES中所有AP的相似度，并選擇最小值作為該AP的DPS。其中，Aj∈FT；

4）選擇類FT中DPS最大的AP，加入到ES；

5）從FT中刪除該AP；

6）T=T+1；

7）如果T

8）如果T

根據上述構建方法，得到滿足條件的有效集ES，具體算法如下：

算法2構建有效AP集合。

輸入：聚類集合F中類數為N，所需AP數為M，被選擇類的數量游標T；

輸出：有效集合ES。

2 結果與分析

2.1 實驗與實驗環境

本文在大規模場景進行實驗，并使用經典的wknn算法定位誤差來驗證算法性能。實驗場景為寫字樓和存儲倉庫，感知面積分別為1200和1500m2。實驗各種設置參數如表1所示。在本實驗中，w knn定位算法中的近鄰值為5。

表1 實驗設置Tab.1 Experimental setup

2.2 定位精度對比

為評估EID的性能，將其與現有的多個AP選擇算法進行對比，包括基于組判別的GDB算法、基于SDN的AP接入點選擇算法和基于非均勻量化RSS熵的NQRE算法。圖3為在不同設備的測試下，本文方法與其他3種算法的定位誤差對比圖。實驗結果為2個場景的平均值。

圖3 不同算法誤差對比Fig. 3 Comparison of accuracy in different methods

根據實驗對比，EID方法在不同設備下的定位結果均優于其他算法，平均定位精度分別提升了18.7%、11.2%和14.6%。EID方法考慮到了類間的相關性，具有更好的類特征性。與基于多個AP的選擇算法相比，充分考慮類間的相關性和互補性，性能波動較小，定位穩定性更強，95%的情形下定位誤差低于1.2m。

2.3 定位開銷對比

EID剔除了冗余AP，不同算降低了定位計算開銷，如圖4所示。本文對比了不同算法的定位時間。在實驗中，定位時間的對比結果用時間比（TR）表示：

式中，LA為定位算法，t(LA)為LA的算法開銷，t(e)為EID算法開銷，因此TR(e)=1。

實驗結果顯示，利用EID定位所需計算時間最少。對比其他方法，EID的定位時間分別減少46.3%、30.4%和38.8%。在不同場景不同設備情形下，EID的平均定位開銷降低了38.5%。

2.4 AP數量影響

評估EID方法在不同場景下使用不同AP的定位結果。使用全部AP不同百分比的定位結果如圖5所示。由圖5可知，當使用全部AP時，定位效果并不是最優的，原因是當AP數量增多時，會出現“無效AP”的現象，即AP冗余，甚至對定位精度有不利影響。因此，AP數量并不是越多越好，合適的AP數量既提升了定位精度，也減少了能量消耗，延長了AP的使用壽命。當EID方法減少了42%和40%的AP數量時，定位精度分別提升了10.8%和11.3%，該方法在減少大量AP的同時，提高了定位的準確率。

圖5 不同數量AP定位誤差Fig. 5 Accuracy for different number of APs

2.5 聚類數量影響

當聚類個數過多或過少都會對定位精度產生很大影響，甚至極大改變定位效果。實驗通過調整相似度閾值，將AP分別聚成12、16、20、24和28類5種情形。根據實驗結果，AP占全部數量的55%～65%時，EID的定位效果較好。因此，本文選擇60%的AP進行聚類。

圖6為不同聚類數量的定位誤差。由圖6可知，聚類數為20時的定位誤差最小。表2為不同情形下AP在不同類的均值和標準差。

圖6 不同聚類個數對定位的影響Fig.6 Influence of different number of clusters on positioning

表2 不同聚類個數的均值與標準差Tab.2 Mean and standard deviation in different clusters

2.6 討 論

與傳統AP選擇方法相比，本文提出的方法有以下優勢：

1）本文使用區分度評估AP的空間分辨程度，有效展示了接入點的定位能力。

2）本文提出的增量聚類算法適應復雜環境下AP的變化，同時提出AP有效集選擇策略，合理兼顧不同的聚類類別，提高了定位精度并延長AP的整體使用壽命。

3）本文將EID方法應用于寫字樓和智能倉儲，在減少不低于40%AP數量的情形下，EID的平均定位精度提升超過11%。

3 結 論

隨著無線網絡的普及，AP個數成倍增長，不但增加了指紋定位的計算開銷，更影響了定位效果。本文提出了一種基于信息區分度的AP有效集構建方法，該方法使用AP區分度來評估AP的空間區分能力；然后，設計了增量聚類算法來得到不同類別的AP集合；最后，根據點集距離最大原則選擇合適的AP有效集。根據實驗驗證，本文提出的EID方法優于當前的AP選擇方法，在減少不低于40%AP數量的情形下，定位精度分別提升了10.8%和11.3%。因此，EID方法能避免無效AP，在減少定位成本的同時提升定位精度。

本文的AP區分度評估使用的是原始RSS，由于RSS信號的波動性，導致不同時刻的AP指紋會產生差異。為此，可進一步研究和設計更穩定的指紋信號，以提升AP區分度的魯棒性。