嚴(yán)維軒，朱立才*，季衍輝，李 永，楊 浩,3

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

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

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

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

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

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

1 基于區(qū)分度的AP有效集構(gòu)建

1.1 基本思想

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

EID方法如圖1所示。

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

EID方法具體步驟如下：

1）建立AP指紋集：對感知區(qū)域采樣，根據(jù)采樣位置為每個AP建立對應(yīng)的指紋集。

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

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

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

1.2 建立AP指紋

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

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

1.3 計算AP區(qū)分度

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

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

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

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

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

然后，計算AP的條件熵：

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

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

1.4 設(shè)計增量聚類算法

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

根據(jù)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

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

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

AP_Cluster算法思想如下：

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

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

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

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

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

5）否則，F(xiàn)中新建一個類{Amax}，且聚類的數(shù)量加1；

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

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

算法1 AP_Cluster算法。

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

1.5 構(gòu)建AP有效集

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

1）初始化：聚類集合F中類數(shù)為N，所需AP數(shù)為M，AP有效集ES為空，被選擇類的數(shù)量游標(biāo)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

根據(jù)上述構(gòu)建方法，得到滿足條件的有效集ES，具體算法如下：

算法2構(gòu)建有效AP集合。

輸入：聚類集合F中類數(shù)為N，所需AP數(shù)為M，被選擇類的數(shù)量游標(biāo)T；

輸出：有效集合ES。

2 結(jié)果與分析

2.1 實驗與實驗環(huán)境

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

表1 實驗設(shè)置Tab.1 Experimental setup

2.2 定位精度對比

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

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

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

2.3 定位開銷對比

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

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

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

2.4 AP數(shù)量影響

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

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

2.5 聚類數(shù)量影響

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

圖6為不同聚類數(shù)量的定位誤差。由圖6可知，聚類數(shù)為20時的定位誤差最小。表2為不同情形下AP在不同類的均值和標(biāo)準(zhǔn)差。

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

表2 不同聚類個數(shù)的均值與標(biāo)準(zhǔn)差Tab.2 Mean and standard deviation in different clusters

2.6 討 論

與傳統(tǒng)AP選擇方法相比，本文提出的方法有以下優(yōu)勢：

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

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

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

3 結(jié) 論

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

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