基于信息区分度的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区分度的鲁棒性。