- 1 -
中国科技论文在线
基于仿射传播聚类辅助的指纹定位算法
邓中亮，陈沛*
作者简介：邓中亮(1965-)，男，教授、博士生导师，近年来，一直致力于无线传感器网络、卫星导航定位、
多媒体通信、微电子设计、MEMS 等研究
（北京邮电大学电子工程学院，北京 100876）
5 摘要：随着大型场馆大量兴建，位置服务已不仅仅局限于室外区域， 传统的卫星定位系统
不能很好的在大型场馆室内区域发挥作用，庞大的室内位置感知需求与无线局域网技术的日
益成熟使得研究基于 RSS 的无线定位技术具有非常重要的现实意义。本文针对现在常用的
WLAN 室内定位指纹匹配算法的匹配时间过长的问题，提出一种名为仿射传播聚类的聚类
算法辅助的指纹定位算法加以改进，算法通过对指纹数据库进行聚类划分从而节省指纹数10
据库的匹配时间，提高了定位时的效率。
关键词：仿射传播聚类；室内定位；WLAN 定位；指纹匹配
中图分类号：TN961
A fingerprint positioning algorithm based on Affinity 15
Propagation clustering
DENG Zhongliang, CHEN Pei
(Electronic Science and Technology School, Beijing University of Posts and Telecommunications,
Beijing 100876)
Abstract: The huge demand for location-aware services as well as the wireless LAN technology 20
has become more sophisticated, makes the study of RSS-based wireless location technology be
very important and WLAN indoor positioning algorithm based on fingerprint
matching may consume plenty of time at matching stage when there is a huge fingerprint database.
To enhance the efficiency of the algorithm, this paper proposed an improved fingerprint matching
positioning algorithm based on a clustering algorithm named Affinity Propagation clustering, it 25
can save a lot of time and improved the positioning efficiency.
Key words: Affinity Propagation clustering; Indoor positioning; WLAN positioning; fingerprint
matching
0 引言 30
随着 技术的日渐成熟和无线局域网在全世界的普及，鉴于 GPS 定位技术在
室内复杂场景下达不到理想的定位效果，基于 WLAN 的室内定位技术已经成为全球室内人
员定位的研究热点。
基于 WLAN 的室内定位技术主要是通过接收来自 WLAN 设备的 RSS 来进行定位的。
而基于 RSS 的定位又有许多方法，其中包括：三边定位法，最近信标法和基于位置指纹法35
等等。而位置指纹法由于其不需要预先知道信标的具体位置，且不需要通过 RSS 测距，从
而不须考虑测距误差而得到广泛的应用与推广。
1 基于位置指纹定位技术的不足
WLAN 定位算法的速度与精度一直是这一定位领域的重点和难点。
对于基于指纹匹配算法的定位，在定位阶段，匹配算法效率直接影响到定位的效率。而40
现有的匹配算法都需要将在线采集的 RSS 测量向量与整个指纹库的每一个点的测量向量进
行比较。因此，对于大型场馆的室内人员定位来说，用户的手持终端设备的运算量也会呈线
- 2 -
中国科技论文在线
性增长。对于当前市面上普及的终端设备的运算能力来说，这无疑会大大影响定位的速度，
由此而造成的结果就会变成：定位结果滞后，用户体验十分糟糕。
2 基于仿射传播聚类辅助的指纹定位算法 45
我们知道一个信标节点的信号覆盖范围有限：典型覆盖范围是 100m，但是实际情况中，
由于环境的影响，其覆盖范围可能会更小，因此在离线采集时，并不是所有的采集点都会被
所有的信标覆盖。例如，如图一所示，信标 1 和信标 2 可能在区域 1 中接收到，但由于其覆
盖范围有限，他们在离区域 1 一定距离的区域 2 中接收不到，或接收到的信号极其微弱。那
么，就可以将整个定位场景划分为几个小区域，可以认为每个区域中能采集到 RSS 测量向50
量具有一定的相似度匹配度，同时这些测量向量与其他区域中的测量向量没有相似度匹配度
或相似匹配度极小。
图一：信标覆盖区域示意图
区域1
区域2
信标1 信标2
信标3 信标4
红色表示区域的范围边界
蓝色表示信标信号覆盖边界
有了这样的划分后，可以从以下方案来解决上面提到的问题。 55
既然，整个定位区域可以划分为几个小区域，且这些小区域内部与其他区域的相似匹配
度存在明显差异。那么在定位匹配时，我们只需找到在线实时接收到的 RSS 测量向量属于
哪个小区域即可，从而在对整个数据库进行遍历匹配时，只需对场景某一区域的指纹数据进
行匹配，而不必对整个场景的数据都进行遍历，这样就大大节省了匹配算法的时间，提高了
定位的效率。 60
因此，需要找到一种方法来将整个指纹数据库通过聚类划分出几个区域，区域内的点与
类中心点的相似匹配度，要大于与其他区域的类中心点的相似匹配度。本文采用一种名为仿
射传播的聚类[1]方向来进行划分。
仿射传播聚类方法介绍
仿射传播聚类(Affinity Propagation clustering)，也称 AP 算法，是在 Science 上提出的一65
种新的聚类算法,由 Frey 等人提出的，其优势体现在处理类数很多的情况时运算速度和收敛
速度很快。该算法在人脸图像的聚类、基因外显子发现、搜索最优航线等方面得到了应用。
该聚类算法相比于通常的聚类算法还有以下的优点[2][3][4]：（1）它不需要事先确定聚类
的数目（2）无需人为确定聚类中心，不会像 K 均值聚类算法那样由于初始聚类中心的选择
不当而得不到最优的聚类结果。 70
- 3 -
中国科技论文在线
AP 算法需通过样本点与样本点之间的相似度来建立一个相似度矩阵，记为 S，若样本
点总数为 N，则 S 是一个N N 的矩阵， ,S i j 表示样本点 i 与样本点 j 之间的相似度，对
于指纹点数据样本，若以
表示指纹点的 RSS 信号向量， ,S i j 表示两个指纹点的 RSS
信号向量的相似度，可表示为：
2
, i jS i j
。
算法最开始是将所有样本点都看作类中心点，通过循环迭代来不断缩小类中心点的范75
围，迭代过程中用到的判断标准或称证据有以下两个：
1） 吸引度，表示一个样本点 j 作为另一样本点 i 的类中心的适合程度的依据，记为
,R i j 。
2） 归属度，表示一个样本点 i 认为另一样本点 j 为其类中心的适合程度的依据，记为
,A i j 。 80
具体的，相似度 ,S i j 越大表示样本点j对样本点i的吸引程度越大，或者样本点i认为
样本点j 为聚类中心的归属感越强，这样处于聚类中心处样本点到其它点之间的吸引度之和
较大，成为聚类中心的可能性就愈大。从而，不断地从数据样本中搜集相关的证据： ,R i j
和 ,A i j ，证据越强（即 ,R i j 与 ,A i j 越大），样本点j作为聚类中心的可能性就越大。
通过迭代过程来搜集和传递证据，最终产生M个高质量的聚类中心，将样本点分配到最近的85
聚类中心中就得到M个聚类（即聚类结果）。
算法的具体步骤可表示为如下：
1） 根据相似度公式计算得到相似度矩阵S，其中，对角线函数 ,S i i 需人为确定，称
为：偏向参数(preference)p, 偏向参数越大，对应样本点成为类中心的可能性越大。
同时，偏向参数的选取也将影响聚类数目。Frey等人认为在没有先验知识的情况下，90
( )p median S ，为相似度的中值函数，即 ,S i i p 。并且初始化
, 0, , 0,( 1,2,3..., ; 1,2,3..., )R i j A i j i n j n
2） 更新相似度矩阵 ,R i j ：
, ,PR i j R i j
, ( , ) max , ,
k j
R i j S i j A i k S i k
95
, 1 , ,N PR i j R i j R i j
, ,NR i j R i j
其中 ( 1,2,3..., ; 1,2,3..., )i n j n
3） 更新归属度矩阵 ,A i j ：
, ,PA i j A i j 100
, max 0, ,
k j
A j j R k j
,
, min 0, , max 0, ,
k i j
A i j R j j R k j
, 1 , ,N PA i j A i j A i j
, ,NA i j A i j
- 4 -
中国科技论文在线
其中 ( 1,2,3..., ; 1,2,3..., )i n j n 105
4） 寻找聚类中心点，判定依据为：若数据点b使得 , ,R i b A i b 是
, , ( 1,2,3..., )R i k A i k k n 中的最大值，那么此时b为i的聚类中心
5） 此时，检查迭代是否完成，若完成，则输出聚类中心和相应聚类，若未完成，则继
续从步骤2开始执行，由此循环。迭代是否完成的依据可为：聚类中心经过l次迭代
后仍无变化则认为迭代完成。 110
在每一次更新迭代过程中， PR 和 PA 表示前一个迭代值， NR 和 NA 表示当前迭代值，每迭
代一次更新 ,R i j 和 ,A i j ，在下次迭代时此值作为 PR 和 PA 。阻尼系数 0,1 ，也是
人为设定的，一般默认值设定为 ,它的作用则是对相似度矩阵和归属度矩阵的加权
更新[5][6]。
仿射传播聚类应用于指纹定位算法的实现 115
为了找到与在线阶段接收的RSS信号向量满足一定匹配度的指纹数据向量，在目前常用
的指纹匹配算法中，须对整个数据库进行遍历，从而找出一个或几个采集指纹点，根据采集
指纹点相应的绝对或相对坐标来确定当前定位点。当引入AP聚类算法后，将整个场景的指纹
数据采集点划分出几个子类，只需根据在线阶段接收的RSS信号向量确定此信号向量最有可
能落在哪个子类里，那么，将此信号向量与其所在类的指纹数据进行匹配定位即可。具体实120
现如下：
1） 离线阶段，在对整个场景进行采集建立完备的数据库之后，将这些指纹数据通过AP
算法进行聚类，此时，AP算法步骤1中的相似度计算公式，即两指纹点的相似度，可采用如
下公式计算：
2
, i jS i j
，
表示指纹点的RSS信号向量。
算法的输出M个聚类中心和相应的聚类成员。此时指纹数据库被划分为M个子集。然后，125
需通过相似度计算公式计算出每个子集中类成员与类中心相似度的最小值。这样数据库所记
录的信息包括：每个指纹采集点的RSS信号向量以及采集时此指纹点的绝对或相对坐标
, ( 1,2,3,.. )i ix y i n 、每个指纹采集点所应属于的聚类子集编号 ( 1,2,3,..., )m m M 、每
个聚类子集中的类中心向量 ( 1,2,3,..., )
c
i i M
、每个聚类子集中与类中心向量的相似度的
最小值 ( 1,2,3,..., )iL i M 。 130
2） 在线阶段，当用户通过设备接收到当前所在位置的RSS信号向量后，首先将之与数
据库中M个类中心向量进行相似度运算，得出的相似度值 ( 1,2,3,..., )il i M ，若 il 的最大值
不小于 i aL ，则判定信号向量属于编号为a的类中，那么，只需将信号向量与此类中的所有
指纹向量来进行匹配定位即可。
假设整个指纹数据库的数据总数为N，未引入AP算法前，若对整个数据库进行遍历，次135
数为N；若AP算法输出M个类，每个类的数据量为 ( 1,2,3,..., )in i M ,那么，在匹配算法的遍
历过程中计算量为 ( )kM n k i ，其中M为与M个类中心的遍历次数， kn 为某一个子类中
的指纹点数目，遍历效率提高了1 ( , 1,2,3,..., )k
M n
k i i M
N
。
3 实验结果
实验采用地域面积为3万平米左右（指纹库总量为320,采集间隔为10米）的室内环境来140
验证AP算法两个参数对聚类结果的影响，进一步选取合适参数来进行定位效率验证。实验中
聚类中心经过10次迭代后仍无变化则认为聚类算法已经收敛，可认为迭代完成，且若经100
- 5 -
中国科技论文在线
迭代后仍未收敛，也认为迭代完成。
表1表示参数参数P变化时对AP算法的影响。参数P的变化范围为相似度S的最大值-59
和最小值-66094之间，取值为从中值-33077到最小值和最大值各分成五等分; 参数变化145
范围为（）。
表1 参数参数P变化时算法的结果（是否收敛与聚类个数）
-66092 15 15 15 15 16 15 不收敛 不收敛 不收敛
-59489 16 16 16 16 16 16 不收敛 不收敛 不收敛
-52866 16 16 16 16 16 16 不收敛 不收敛 不收敛
-46283 16 16 16 16 16 16 不收敛 不收敛 不收敛
-39680 16 16 16 16 16 16 16 不收敛 不收敛
-33077 17 18 18 18 17 17 不收敛 不收敛 不收敛
-26474 20 20 20 22 22 22 不收敛 不收敛 不收敛
-19871 30 28 27 27 28 28 不收敛 不收敛 不收敛
-13268 45 46 45 44 44 不收敛 不收敛 不收敛 不收敛
-6665 123 123 122 120 118 119 不收敛 不收敛 不收敛
-62 不收敛 不收敛 不收敛 不收敛 不收敛 不收敛 不收敛 不收敛 不收敛
由上表看出当取值为时且P取小于等于-39680时输出类数趋于稳定。
由此，对于此定位环境，取 ，P值取相似度S中值与最小值之间五等分点的第二
等分点，即 min min25medp S S S 150
经由AP算法输出16个子类。按照此种划分，将指纹库划分为16个子类，然后用KNN算法
进行定位匹配，分别进行三次仿真，三次仿真表示分别在大场景中的三个不同小区域进行100
次定位，给出采用AP算法前后的定位时间对比如下：
表2 采用AP算法和普通指纹定位算法的定位时间
仿真次数 采用AP算法后100次定位总时间 普通指纹算法100次定位总时间
1
2
3
平均 28s
可知，采用 AP 算法后定位平均时间比原来减少了了 57%，提高了定位的效率。 155
4 结论
为了提高传统的指纹匹配算法的效率，本文将仿射传播聚类算法引入指纹定位算法中，
减少了匹配算法中遍历过程的运算量，减少了定位运算时间。本文所提出的算法也存在不足
与改进之处，因为，对于仿射传播聚类算法本身，两个参数偏向参数 p 和阻尼系数 λ 值的
确定会对聚类结果产生影响，偏向参数影响聚类的数目，阻尼系统影响着聚类的收敛性,如160
何找到一种普适的方法来确定这两个参数的最优值从而得到最优的聚类结果还有待进一步
的研究。
[参考文献] (References)
[1] Frey B J,Dueck D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.
[2] Xu R, WUNSCH D. survey of clustering algorithms[J]. IEEE Transactions 0n Neural Networks, 2005, 165
16(3):645-678.
[3] 吉贵，刘杰，赵连宇. 聚类算法研究[J]. 软件学报，2008，19(1)：48-61.
[4] 徐森，卢志茂，顾国昌. 解决文本聚类集成问题的两个谱算法[J]. 自动化学报，2009，35(7)：997 一 1002
- 6 -
中国科技论文在线
[5] 王羡慧，覃征，张选平，高洪江. 采用仿射传播的聚类集成算法[J]. 西安交通大学学报，2005，5（8）：
2-6. 170
[6] 王开军，张军英，李丹，张新娜，郭涛. 自适应仿射传播聚类[J]. 自动化学报，2007，33（12），1242-1246.
