基于仿射传播聚类的概率分布室内定位算法

唐笑谋，唐佳杰

（1 重庆邮电大学重庆市移动通信技术重点实验室，重庆 400065；2. 重庆工商大学计算机科学与信息工程学院，重庆 400067）

基于仿射传播聚类的概率分布室内定位算法

唐笑谋1，唐佳杰2

（1 重庆邮电大学重庆市移动通信技术重点实验室，重庆 400065；2. 重庆工商大学计算机科学与信息工程学院，重庆 400067）

随着定位技术的快速发展，基于无线局域网的室内定位成为新的研究热点。本文提出了一种基于近邻传播聚类的概率分布无线局域网（WLAN）室内定位算法。与传统室内定位算法相比，该算法首先引入近邻传播聚类缩小参考点搜索空间，然后利用概率分布定位算法进行精确定位。仿射传播聚类可以有效减少概率分布定位算法的计算量，应用于系统后将有效降低系统复杂度。实验结果表明，本文所提算法具有更好的定位精度，可实现对WLAN室内定位目标的快速、可靠定位。

WLAN室内定位；指纹法；仿射传播聚类；信号强度；概率分布

近年来，随着数据业务的快速增加，人们对定位与导航的需求日益增大，尤其对于复杂、动态室内环境下的用户位置判断。IEEE 802.11无线局域网(WLAN)标准的问世，让无线通信市场需求迅猛增长[1]。WLAN接入点(AP)定时发送信标信息中所含的接收信号强度(RSS)为基于位置指纹的室内定位技术提供了可能。目前，国内外最具代表性的室内定位系统有美国微软研究院的RADAR系统[2]、马里兰大学的Horus系统[3]、加利福尼亚大学洛杉矶分校的Nibble系统[4]、北京航天航空大学的Weyes系统[5]等。RADAR系统定位过程简单，但精度不高；Horus系统采用信号强度的概率分布函数，作为位置指纹的基本信息，精度较高，但复杂度也较高；Nibble采用信噪比作为信号空间样本，而非RSS，精度不高，但其定义的目标位置点粒度较大，一般被定义为整个房间或者重要的位置附近区域；Weyes系统不直接采用RSS，而采用差值模型，误差值在不同设备之间差别较大，精度不高。

在室内环境中利用无线信号强度进行定位时，应尽量保持室内环境的相对稳定，但随着室内人数增多且存在相对运动时，无线指纹信号的不确定性就会增大，从而严重影响指纹法的定位精度[6]。为了获得较高的定位精度，基于信号强度的匹配定位技术一般需要在训练阶段采集大量且具有位置标记的信号样本，以构建位置坐标与信号强度的有效、可靠映射关系(Radio Map)，训练工作量较大。于是，为了减小训练难度，Ocana[7]使用K-means聚类算法证明，减少位置数以及在每个位置点的采样时间对定位准确度影响不大，证实了在一定程度上降低训练难度的可行性。在定位计算阶段，为了降低匹配计算量，文献[8]采用Median和K-means聚类算法，根据训练数据集的信号强度向量对实际物理位置进行聚类，然后在在线定位阶段，首先计算待定位节点的所属聚类，然后在该聚类内进行细粒度的位置匹配计算。

为降低计算复杂度、提高定位精确度，本文利用仿射传播聚类方法，从指纹定位基本原理出发，研究粗定位阶段的聚类产生过程与匹配过程，并通过精定位阶段的概率分布定位算法，对定位目标进行精确位置估计，以实现对目标的快速、可靠定位。

本文组织结构如下：第一节介绍了基于仿射传播聚类的概率分布定位算法的基本流程；第二节对仿射传播聚类用于数据库预处理的算法步骤进行了详细讨论；第三节利用在线阶段的概率分布定位算法，实现对目标的精定位过程；第四节是算法的实验结果，比较和验证了本文所提定位算法的精度有效性；第五节对全文进行总结。

1 算法基本流程

指纹定位法分为两个阶段，离线建立阶段和在线定位阶段[9]。离线阶段，在WLAN定位网络的覆盖区域内采集信号样本，建立覆盖区域对应的WLAN位置指纹图。定位阶段，又主要包括粗定位和精定位两个步骤。

由于室内电波传播复杂的时变特性，在线阶段的实时接收信号强度测量值与离线阶段指纹库存在差异。为了降低信号时变特性所带来的影响，去除潜在异常值，本文首先利用仿射传播聚类，对数据库中参考点的RSS向量进行分类，保证同类中样本具有邻近物理位置关系，且RSS向量间具有最大相似度[10]。在在线阶段的粗定位过程中，聚类结果可将目标位置估计区域缩小至一个聚类中。从而，在每个较小聚类中实现精定位，既降低了RSS时变特性所带来的影响，又提高定位算法的计算效率。

近邻传播聚类的基本思想是通过消息传递，让数据点相互选择聚类质心和聚类归属集合。近邻传播过程可看作相似度消息在双向图上按照一定概率进行传播，这个双向图模型描述任意两个数据点之间相似度。通过消息迭代传播，可最终从被聚类数据中挑选出聚类质心和将每个数据点归属到某个最可能聚类集中。经典的K均值聚类方法需要通过随机方式选取初始类首，聚类结果很大程度上依赖于初始类首的选择[11]，且容易陷入局部极值。相反，仿射传播聚类则将数据集的所有N个样本点作为候选类首，每个样本点分别对应一个实数，称为偏向值(Preference)，偏向值越大，对应样本点被选为类首的可能性越大。由于仿射传播聚类算法无需随机选取类首，算法收敛速度较快且有效，其结果更符合数据拓扑分布，因而可将其应用于指纹定位系统离线阶段的数据处理。

确定性方法和概率分布方法是指纹定位法中两种较为主要的定位方法。其中确定性方法在离线阶段测量并保存一定采样时间内接收信号的强度平均值，并在在线阶段利用信号间欧氏距离来计算不同信号强度间的匹配性，RADAR和Weyes系统均采用这类方法。而概率分布方法则测量并保存信号的概率分布，利用贝叶斯法则估计位置坐标，其中，以Nibble和Horus系统最为典型。

不同于传统位置指纹定位算法，本文提出的基于仿射传播聚类的概率分布室内定位算法，包括离线指纹预处理与在线粗精双步定位两个步骤。首先，在离线阶段，对数据库进行仿射传播聚类处理。然后，在在线阶段，利用RSS测量值与指纹库的匹配，经过粗定位和精定位两个过程，完成仿射聚类传播算法与概率分布定位算法的结合，以实现对目标的快速、可靠定位。算法的基本流程如图1所示。

图1 仿射传播聚类概率定位算法的基本流程

2 仿射传播聚类算法

为了降低室内电波传播特性所带来的影响，去除潜在异常值，本文首先应用仿射传播聚类算法对数据库中参考点所对应的RSS向量进行聚类，类信息将为在线阶段的粗定位机制所用。

在近邻传播聚类中，参考点间相互传递两类信息，即r(i， j)(Responsibility)和a(i， j)(Availability)，其中r(i， j)表示参考点RPj作为RPi的聚类中心的可信度，a(i， j)表示参考点RPi选择参考点RPj作为其聚类中心的可信度。基于近邻传播聚类的参考点聚类算法的伪代码流程如下所示：

输入：任意两个参考点RPi和RPj间的相似度s(i， j)

输出：参考点聚类结果和相应聚类中心

算法过程：

初始化：

a(i， j)=0

更新参考点之间的r值：

更新参考点之间的a值：

更新同一参考点自身之间的a值：

计算：

从而，利用仿射传播聚类所形成的类首和对应信号强度向量，本文首先利用基于类匹配的粗定位过程，将定位区域缩小至目标的某个邻近物理区域，即具有最大相似度的聚类中，并进而在该类中实现精定位。

计算：

精定位只需在聚类Cj中实现即可。

3 概率分布定位算法

概率分布定位算法通过计算采集到的无线信号强度与位置指纹图中各点的匹配概率，选取概率最大的参考点作为目标的估计位置。在统计信号强度分布时，通过引入高斯信号概率函数，利用统计数学期望和方差来刻画室内定位环境中任意位置处的信号强度分布特征。对于实际采集的无线信号强度集合，通常认为服从正态总体分布N(μ，σ2)，统计参量为μ和σ2。

似然函数为：

对数方程为：

似然方程组为：

于是，可以得到：

似然方程组有唯一解(μ*，σ*2)，而且它一定是最大值点，这是因为当|μ|→∞或σ2→0或∞时，非负函数L(μ，σ2)→0。于是μ和σ2的最大似然估计为：

用X表示所有涉及的样本，因为最大似然估计μ*和σ*2都是统计量，在抽取一定的样本空间后，认为计算的结果μ*和σ*2为真实值，并将μ*作为该点的信号强度。

在离线训练阶段，位置指纹图的构建，首先在定位区域内选取参考点，然后测量每个参考点处不同AP(Access Point)信号强度平均值ei和di方差，其中，i为不同AP标识，与参考点对应位置坐标一起构建位置指纹数据库。

在在线定位阶段，主要根据实时采集到的信号强度，与室内定位区域内位置指纹图进行匹配，以实现精定位。对于采集到的所有L个AP无线信号强度值{rssi，i=1，2，…，L}，利用公式(10)所示正态分布概率公式（取μ=ei、σ=di），计算Pi=(x，y)，即得到第i个AP在位置指纹图中的点(x，y)的概率。

获得所有AP的无线信号强度在地图中的分布概率后，将采集到的无线信号强度值代入概率公式，并计算出各个参考点的概率P=(x，y)，如公式(11)所示。求得最大概率积，并把其对应的坐标(x，y)作为当前位置估计坐标。

4 实验结果及分析

4.1 实验设置

本文利用图2所示物理环境，对包含9个AP的WLAN信号强度数据进行采集，并通过与基于K均值聚类的K近邻定位算法和概率分布定位算法，以及基于近邻传播聚类的K近邻定位算法的定位性能比较，验证本文所提基于近邻传播聚类的概率分布定位算法的有效性及可靠性。该实验区域尺寸为66×22 m2，9个AP型号为Cisco WRT54G。

图2 实验场景布置

图3 基于仿射传播聚类的参考点聚类结果

图4 测试轨迹

4.2 定位结果

图3为利用仿射传播聚类算法进行数据库预处理得到的结果。圆圈代表采集到的所有参考点，圆圈上的颜色代表不同聚类。图中182个参考点被划分为7个聚类，同一聚类参考点具有物理临近性。

在实验场景中随机选择一条定位曲线作为测试轨迹，如图4所示。

在该定位测试轨迹上随机选取81个物理位置点作为定位测试点。4种典型定位算法（K均值+K近邻，K均值+概率分布，近邻传播+K近邻，以及近邻传播+概率分布）的误差结果如表1所示。此外，4种定位算法的累计误差函数如图5所示。

4.3 误差分析

由上述实验结果可知：基于近邻传播聚类的概率分布定位算法相对于基于K均值聚类的K近邻定位算法和概率分布定位算法，以及基于近邻传播聚类的K近邻定位算法，平均误差分别降低了34.02%、28.3%和16.17%；本文所提算法误差在3 m内的置信概率为80.49%，显著优于其它3种典型定位算法的置信概率43.9%、62.2%和65.85%。

5 结束语

本文提出的基于近邻传播聚类的概率分布定位算法，与传统室内指纹定位算法相比，缩小了定位搜索空间，降低了算法计算开销。实验结果显示本算法具有更高的定位精度。同时，本文所提定位算法不仅适用于WLAN室内定位网络，也同样可应用于其它基于信号强度的无线定位网络，如WSN、RFID、移动蜂窝网络等。然而，该算法的不足之处是在离线阶段聚类完成后，各聚类集中的样本点不完全具有物理临近性。在下一步工作中，将继续开展对网络AP优化布置的研究，并优化聚类结果，进而提高定位精度。

表1 4种典型定位算法的误差比较

图5 累计误差函数

[1] XU Y Q， Lau S L， Kusber R， David K. An experimental investigation of indoor localization by unsupervised Wi-Fi signal clustering[A]. FutureNetw[C]. 2012， pp 1-10.

[2] Bahl P， Venkata N. Padmanabhan V N1 RADAR： an in-building RF-based user location and tracking system[J] Info Com 2000.

[3] Youssef M， Agrawala A. The horus WLAN location determination system[A]. Third International Conference on Mobile Systems，Applications， and Services (MobiSys2005)[C]. June 2005.

[4] Castro P， Chiu P， Kremenek T， et al. A probabilistic room location service for wireless networked environments[A]. UbiComp 2001[C]，2001. 18～34.

[5] Lang V， Xu K. A difference model for open WLAN enviroment based location service submitted[A]. IEEE Infocom[C]. 2006.

[6] 任福君， 倪鹏， 王殿君， 姜永成， 段云涛. 基于概率法的移动机器人无线网络定位系统[J]. 科技导报. 2010，28(10).

[7] Ocana M. Bergasa L M， Sotelo M A， et al. Indoor robot location system using Wi-Fi signal measure and minimizing calibration effort[A]. Proc of IEEE International Symposium on Industrial Electronics[C]. Dubrovnik， Croatia， 2005.1545-1550.

[8] Nattapong S， Prashant V K. On clustering rss fingerprints for improving scalability of performance prediction of indoor positioning systems[A]. Proc of the 1st ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environment[C]. San Francisco， California， USA， 2008.61-66.

[9] Alsindi N， Chaloupka Z， Aweya J. Entropy-based location fingerprinting for WLAN systems[A]. Indoor Positioning and Indoor Navigation[C]. 2012， 1-7.

[10] Feng C， Au W S A ， Valaee S， Tan Z. Compressive sensing based positioning using RSS of WLAN access points[A]. INFOCOM 2010 Proceedings IEEE[C]. March 2010， pp. 1-9.

[11] 顾诤， 肖若贵. 基于AP聚类和频繁模式挖掘的视频摘要生成方法[J]. 计算机应用与软件. 2010，27(6).

Probability distribution-aided indoor positioning algorithm based on affinity propagation clustering

TANG Xiao-mou1; Tang Jia-jie2
(1 Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China; 2 School of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China)

With the rapid development of localization technology, the WLAN-based indoor localization becomes a new signif i cant research concern. This paper proposes a probability distribution-aided indoor positioning algorithm based on affinity propagation clustering. Compared to the conventional indoor positioning algorithms, this paper fi rst introduces the aff i nity propagation clustering to minimize the search space of reference points. Second, we use the probability distribution-aided algorithm to realize the accurate localization purpose. Aff i nity propagation clustering can effectively reduce the calculation cost of the probability distribution-aided localization algorithm, and thereby the systematic complexity can be effectively decreased. Experimental results show that the algorithm introduced in this paper not only performs better in accuracy, but realizes the fast and reliable localization.

WLAN indoor positioning; fi ngerprinting; aff i nity propagation clustering; RSS; probability distribution

TP391

A

1008-5599（2013）08-0062-06

2013-07-04