- 1 -
中国科技论文在线
基于 Dijkstra 辅助的指纹定位算法
潘永灿，黄建明**
作者简介：潘永灿（1988-），男。硕士，电子科学与技术
通信联系人：黄建明(1972-),男，副教授，主要研究方向：微电子机械，大数据等
（北京邮电大学电子工程学院，北京 100876）
5 摘要：物联网技术是目前的热点技术，对行业的发展有广阔的应用前景。室内定位技术对物
联网有着极为重要的意义。目前室内定位技术众多，然而由于室内无线网络环境的复杂
性，室内定位技术的准确性一直是该领域研究的重点。本文通过分析室内物体运动的规
律，提出一种基于Dijkstra辅助的位置指纹定位算法，旨在提高室内定位技术的准确性和稳
定性。通过在复杂室内环境中对比不同的定位算法，验证了该算法的有效性，并具有一定10
的实际应用价值。
关键词：物联网 ；室内定位；位置指纹
中图分类号：TN961
A fingerprint positioning algorithm based on Dijkstra 15
PAN Yongcan, HUANG Jianming
(Electronic Engineering School,Beijing University of Posts and Telecommunications beijng
100876)
Abstract: Internet of Things technology is the current hot technology and has broad application
prospects of the development of the industry. Indoor positioning technology has a very important 20
significance for the Internet of things. However, due to the complexity of indoor wireless network
environment, the accuracy of indoor positioning technology has been the focus of research in this
field. In this paper, an algorithm of location fingerprint location based on Dijkstra is proposed in
order to improve the accuracy and stability of indoor positioning technology by analyzing the law
of motion of indoor objects. By comparing different localization algorithms in a complex indoor 25
environment, the effectiveness of the algorithm is verified and has some practical application
value.
Key words: Internet of Things; Indoor positioning technology; location fingerprint
0 引言 30
物联网和云计算是重要的新一代信息技术产业，将对我国未来发展发挥重要作用。没有
位置的物联网服务会大大降低物联网的应用价值。目前，室外定位技术比较成熟，以 GPS
为代表的室外定位技术已广泛应用在生产生活的各个方面，然而相对应的室内定位技术却发
展迟缓。尽管目前已经出现了很多室内定位技术的算法，但统一的室内定位技术还没有像
GPS 那样，被广泛的使用。 35
定位算法从定位手段上分为两大类：基于测距算法（range-based）[1]和无需测距算法
（range-free）[2]。在信号传播的过程中，由于障碍物的阻挡而造成的多径、阴影效应，基于
此的测距技术很难保证测距的稳定性和准确性，由此计算出的定位结果其精度相对较低。
多径传播过程中对环境具有依赖性，呈现出非常强的特殊性，对于每个位置而言，该位
置上信道的多径结构是唯一的，这样的多径特征(如信号强度)可以认为是该位置的“指纹”40
[3]。移动设备扫描周围无线信号的强度，将其与预先存储在数据库中的指纹数据进行匹配，
找到最相似的结果来进行定位。这就是基于信号强度的指纹定位算法。
指纹定位技术是目前定位技术研究的热点，其匹配算法的效率和定位的精度是该领域关
- 2 -
中国科技论文在线
注的重点。由邓中亮等人提出的基于仿射传播聚类辅助的指纹定位算法[4]能有效提高指纹定
位的效率，但对定位的精度没有说明。本文旨在提高指纹定位算法的精度和稳定性。 45
1 建立模型
常见的指纹库定位算法有 3 种，分别是最邻近法[5]、加权最邻近法[6]、贝叶斯法[7]。其
中的最邻近法和加权最邻近法都使用的是把在线阶段采集到的数据按欧氏距离最短进行遍
历查找，最终确定欧氏距离最短的即为定位的坐标点。贝叶斯法在离线阶段获取采样点的位
置指纹特征，建立所有信标节点(本文指在固定位置发射无线信号的设备，比如在本文第 350
章提到的路由)RSSI(Received Signal Strength Indication)值的概率分布。贝叶斯算法就是通过
计算每个位置的后验概率来确定最有可能的位置。
尽管建立信号强度的指纹定位算法能有效减少信号多径传播过程中的不良影响，但无线
网络信号容易受到其他无线网络的干扰，并且移动的物体对信号的传播也有一定影响，实际
上定位精度常常不稳定。而且在室内定位中，不同楼层或者不同房间在邻近的位置上很可能55
出现指纹相似的情况，用常见的指纹库匹配算法很容易混淆相似的位置，从而导致将用户定
位在错误的房间或者楼层。用户在室内走动时，其位置移动路线是连续的，不会从一个房间
跳跃到另一个房间，也不可能从一个楼层跳跃到另一个楼层[8]。基于此，本文提出根据最近
历史指纹采样点求最短的路径，来匹配出最有可能的位置。
最短路径介绍 60
Dijkstra 算法的基本思路是: 假设每个点都有一对标号 ，其中 是从起源点 到点
的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；
则是从 到 的最短路径中 点的前一点。求解从起源点 到点 的最短路径算法的基本过程如
下：
1 ) 初始化，起源点设置为：① ， 为空；②所有其他点： ， ；③65
标记起源点 ，记 ，其他所有点设为未标记的。
2) 检验从所有已标记的点 到其直接连接的未标记的点 的距离，并设置：
，式中， 是从点 到 的直接连接距离。
3) 选取下一个点，从所有未标记的结点中，选取 中最小的一个 ：
，点 就被选为最短路径中的一点, 并设为已标记的。 70
4) 找到点 的前一点，从已标记的点中找到直接连接到点 的点 作为前一点，设置 。
5) 标记点 。如果所有点已标记，则算法已完全推出，否则，记 ，转到 2)再继续。
Dijkstra 算应用于指纹定位
对于每一个信号指纹，系统根据欧几里德最近邻居算法找到在该信号指纹的情况下用户
最有可能所在的 k 个位置（这里 k 个位置即最近的 k 个采样点，也称为 k 个最近邻居）。以75
图 1 为例，系统使用 3 个时间上连续的信号指纹进行定位，即历史深度为 3(H=3)，最近邻
居个数为 4(K=4)。
- 3 -
中国科技论文在线
图 1 最近指纹采样点最短路径推理
图 1 中，a、b、c、d 是信号指纹 1 的最近指纹采样点，e、f、g、h 是信号指纹 2 的最80
近指纹采样点，i、g、j、k 是信号指纹 3 的最近指纹采样点。该算法获得的最短路径是 p→d
→e→g，即在指纹信号 3 求出的最有可能位置是 g 点。
图 2 最短路径理论推理
图 2 中，在信号指纹 1 的情况下，系统找到最近邻居 a、b、c、d；在信号指纹 2 的情85
况下，系统找到最近邻居 e、f、g、h；在信号指纹 3 的情况下，系统找到最近邻居 i、g、j、
k；这些最近邻居组成一个深度为 3 的序列。利用 Dijkstra 最短路径算法系统计算出从上一
次用户位置 p，经过区域 1 和区域 2，到区域 3 的最短路径：p→d→e→g。该算法中两个位
置之间距离是它们的空间直线距离，即欧式距离。最短路径的终点 g 被认为是用户的当前位
置，也就是基于 Dijkstra 辅助的位置指纹定位算法计算出来的位置。 90
- 4 -
中国科技论文在线
和最近邻居算法相比，基于 Dijkstra 辅助的位置指纹定位算法增加了计算历史序列最短
路径的时间。由于历史深度 H 和最近邻居个数 K 都是很小的整数，这个时间可以忽略不计，
因此基于 Dijkstra 辅助的算法几乎没有增加计算复杂度。该算法使用若干个时间上连续的信
号指纹进行定位，在提高了定位精度的同时，也有效地增强了定位的稳定性。
2 算法的实现 95
离线指纹数据库的建立
指纹数据库建立的精度会直接影响到最终定位结果的精度，所以，建立高精度的指纹数
据库是提高定位精度的先决条件。由于在选取数据采集点进行 RSSI 数据采集时，邻近的数
据采集点的 RSSI 总是会有一定的交叠，为此选用如下采样数据处理方法，来提高指纹数据
库的建库精度。 100
选取某个数据采样点上采集的一组数据进行分析，令 为在这一点上采集到第 i
个参考节点 RSSI 值的 n 组数据，即：
(1)
其中，n 为在此点采集的数据组数；i 表示相对于第 i 个参考节点。由于在数据采集过程
中，干扰等原因会出现某组数据的突变，为了防止这种有害数据被最终纳入指纹数据库，结105
合实验设置了一个上下的阈值。此采集点接收到来自第 i 个参考节点的 RSSI 平均值可以表
示为：
(2)
令变化因子为θ ，即有：
(3) 110
(4)
当式(3)成立时，说明采集过程中没有发生数据的突变；当式(4)成立时，说明此数据为
突变数据，应将其剔除，以其平均值 代替。获取各个数据采集点的数据经过上述处理后消
除了其中的突变数据的影响，建立的指纹数据库如下所示，每个采样位置选取 4 个最大的信
标节点的 RSSI，按从大到小进行排序，录入数据库，如表 1 所示。 115
表 1 指纹数据库
Database Ref1 Ref2 Ref3 Ref4
在线定位
1) 匹配最近的 4 个采样位置
在线阶段中，当需定位节点进入定位区域后，可以实时获得位置指纹，样例记为 S，它
- 5 -
中国科技论文在线
包含有来自 m 个信标节点接收信号强度值，即 ，将这 m 个 RSSI 值由大到120
小进行排序，找出 RSSI 值最大的 4 个 ，记为 , j=1,2,3,4。利用离线阶段此范围内选取一
系列采样点记作 ，每个 包含 4 个信标节点的 RSSI，记做 ，j=1,2,3,4，
计算欧式距离：
(5)
通过找出最小的 4 个欧式距离，来确定与样例最近的 4 个采样点位置，125
。
2) 求出到最近采样位置的距离
假设需定位节点的初位置为 P，对应的坐标为 ，第一个指纹匹配的 4 个采样位置
坐标为 ， ， ， ，则 P 到这 4 个采样位置的距离为
, (6) 130
第二个指纹匹配的 4 个采样位置坐标为 ， ， ， ，第一
个指纹对应的 4 个采样位置与第二个指纹对应的 4 个采样位置之间的距离为
, (7)
第三个指纹匹配的 4 个采样位置坐标为 ， ， ， ,
与第二个指纹对应的 4 个采样位置之间的距离为 135
, (8)
3) 求出最可能位置
找出 P 与第一个指纹对应的 4 个采样位置的最短距离 D(1)，则
(9)
设第一个指纹匹配的最近的 4 个采样位置中未使用过的点记为 ，求出在剩下的采样位140
置中，到 P 的最短距离 D(2)，则
(10)
设第一个指纹 4 个采样位置中未使用过的点记为 ，设第二个指纹 4 个采样位置中未使
用过的点记为 ，求出在剩下的信标节点中，到 P 的最短距离，则
145
(11)
若D(3)求出的最短距离包含第 3个指纹对应的采样位置，即包含 中
的一个，则那个采样位置即为定位结果，否则，在剩余的节点中继续求最短距离，直到求出
包含有第 3 个指纹对应的采样位置。
- 6 -
中国科技论文在线
3 实验与结果分析 150
实验场地选择广州市二汽客运站一层，实验环境足够复杂，不仅有大型客运车的移动，
而且在人群密度较大的地方，处在复杂的电磁场环境中。本实验选择基于 ZigBee 的无线传
感器网络(Wireless Sensor Networks, WSN)环境。图 3 中，进站位的红色方块 代表汇聚节
点，用来组建 ZigBee 网络。其余的红色方块代表路由节点，用来向终端发送 RSSI 信息，并
承担通信的中继工作。在本次实验中，活动区域限定在 50mX25m 黑色方框内。夜间采样，155
采样间隔 1m，每个点采样 10s，加上中间休息，共采样 6 个小时。
图 3 室内定位地图
定位实验选择在白天车站正常工作的情况下，本次实验通过对比最邻近法、加权最邻近
法、贝叶斯法来验证算法的准确性和稳定性。图 4 为根据不同的算法，现场试验得出的误差160
分析图。纵坐标为累计误差的比例，横坐标为误差范围。
图 4 定位精度对比
- 7 -
中国科技论文在线
从图 4 可以看出，基于 Dijkstra 的定位精度优于其他另外 3 种算法，误差曲线变化的较
为平缓。 165
为了验证算法的稳定性，在现场实验过程中，在活动区域随机选取 5 个点，每个点定位
5 次，定位波动次数如表 2 所示：
表 2 定位波动情况对比
定位算法 基于 Dijkstra 的最
邻近算法
加权最邻近法 贝叶斯法 最邻近法
位置 1 波动次数 0 1 0 1
位置 2 波动次数 0 0 1 2
位置 3 波动次数 0 1 1 2
位置 4 波动次数 1 1 2 3
位置 5 波动次数 0 0 1 1
总计波动次数 1 3 5 9
从表 2 可以看出，基于 Dijkstra 的最邻近算法累计只出现了一次波动，明显小于最邻近
算法的波动。相比于其他表中列出的算法，基于 Dijkstra 的最邻近算法更加稳定。 170
4 结论
通过算法的理论分析可知，基于 Dijkstra 的最邻近算法符合行走移动的规律，能够在减
小定位误差的同时，能够提高定位的稳定性。通过现场试验统计数据验证了设想的正确性。
实验选择复杂环境下的汽车客运站作为试验环境，相比其他典型定位算法，取得了一定的优
势，具有实际利用价值。 175
[参考文献]
[1] Chen Kai,Zhou Yi,He Jianhua. A localization scheme for underwater wireless sensor networks[J]. International
Journal of Advanced Science and Technology, 2009, 4: 09-16.
[2] M Chu, H Haussecker, F Zhao. Scalable Information-driven Sensor Querying and Routing for Ad Hoc 180
Heterogeneous Sensor Networks [J]. International Journal of High Performance Computing Applications
(S1094-3420), 2002, 16(3): 90-110.
[3] 陈俊阳, 谢锋, 马晟杰. 医院无线定位系统设计及实现①[J].2013.
[4] 邓中亮, 陈沛. 基于仿射传播聚类辅助的指纹定位算法[J]. 2012.
[5] Liu Hui. Survey of Wireless Indoor Positioning Techniques and Systems[J]. IEEE Transactions on Systems, 185
Man, and Cybernetics, Part C: Applications and Reviews, 2007, 37(6): 1067-1080.
[6] 陈 群. ZigBee 技术在室内定位中的应用研究[D]. 南昌: 南昌大学, 2012.
[7] King T, Kopf S, Haenselmann T, et al. A Probabilistic Indoor Positioning System Based on and Digital
Com-passes[C] Proc. of the 1st ACM International Workshop on Wireless Network Testbeds. Los Angeles, USA:
[s. n.], 2006. 190
[8] 周瑞.应用室内结构布局提高 Wi-Fi 定位精度和稳定性[J].电子科技大学学报,2013, 42(2):295-299.
