基于iBeacon的三维无线传感网络定位算法优化研究

林信川

(福建商学院 信息管理工程系，福建 福州，350012)

基于iBeacon的三维无线传感网络定位算法优化研究

林信川

(福建商学院 信息管理工程系，福建 福州，350012)

针对三维传感网络中传统四面体质心算法定位精度不高且收敛慢的情况，提出一种基于iBeacon的三维无线传感网络定位优化算法。在定位前通过样本采集、滤波和拟合，建立室内三维传感环境下的iBeacon传播模型。在定位过程中通过排除待测节点位于参考锚节点四面体外以及位于同一平面内的情况，利用优化的加权因子提升与待测节点较近的参考锚节点在定位过程中的作用。对满足四面体构成条件的情况采用四面体加权质心迭代求解，对不满足条件的参考锚节点组合采用优化的加权因子进行定位。仿真结果表明，该算法在提升定位精度和收敛速度方面相较传统四面体质心算法具有明显提升。

无线传感网络三维定位；iBeacon；锚节点；RSSI；加权因子

0.引言

伴随着物联网技术的蓬勃发展，无线传感器网络(Wireless Sensor Networks，WSNs)[1]中的室内精确定位问题成为一个新的研究热点。作为一种自组织形式的分布式网络，无线传感节点定位技术在环境检测、目标定位等方面具有重要的应用价值。目前基于测距(range-based)算法和测距无关(range-free)算法是两类较为常见的定位算法，二者的主要区别在于针对测量过程中不同节点间的角度或距离数据的关注侧重点不同。RSSI、TOA、TDOA和AOA[2]等是常见的基于测距的定位算法，其实现思路是在收集节点间距离或角度数据的基础上，通过三边测量法、三角测量法或极大似然估计法等计算待测节点的位置。此类算法虽对硬件有一定要求，但定位精度较高。质心算法、Amorphous算法和DV-Hop算法[3]是常见的测距无关算法，此类算法在定位过程中通常依据网络连通数据进行分析。虽然此类算法对硬件的要求较低，但受反射、散射和绕射等因素的影响，定位误差较大。

iBeacon[4]是由苹果公司于2013年发布的基于低功耗蓝牙4.0(BLE 4.0)的技术，在降低功耗和提升通信效率方面相较传统蓝牙技术存在明显优势。iBeacon作为一种连接线下场景的短距离无线传输传感器通讯技术，在低成本、低功耗和高可移动性方面有巨大优势，当前各大互联网厂商都在各自的APP应用上集成了iBeacon应用，该技术已普遍用于各类室内定位的应用场景。iBeacon锚节点通过既定的频率持续对外广播其UUID及位置信息，所有支持BLE 4.0的设备均可接收到附近iBeacon锚节点的UUID，并获取其推送的数据。

目前多数研究是就无线传感空间中的二维定位问题进行的，以不同的思路提供了位于相同平面高度上锚节点的定位解决方案。尽管在现实场景中无线传感网络往往部署于复杂的三维地形中，但多数研究成果均以假定二维无线传感网络为前提，若忽略大范围环境中参考锚节点间及其与待测节点的高度差异，简单将适用于二维平面的定位技术扩展到三维空间中，有可能导致较大的定位误差[5]，因此设计出高精度和容错能力强的三维定位方法更具应用性和发展潜力。文献[6]对传统的DV-hop算法进行了优化处理，利用投影测距技术将三维空间投影到二维平面，通过全网平均每跳距离减小跳距误差。该算法受跳数和跳距影响较大，具有一定的实施难度。文献[7]在一定程度上避免了传统无线传感器网络节点，运行三维定位算法过程中产生奇异矩阵的情况，提出运用平面上向量旋转的二维线性最小二乘估计，变换待测节点的目标位置，进而由变换的目标位置及偏移向量得出最终估算坐标。该算法实施需要配备低主频和小内存的微型无线传感器，在一定程度上增加了设备投入成本。文献[8]提出一种基于小波支持向量机的定位算法，通过优化核函数在一定程度上优化了定位速度和定位精度。该算法的定位成本较高，参数设置和优化问题还需进一步改进才能适用于更加复杂的定位环境。文献[9]提出的粒子群算法实现较为简单，且运行较为稳定，在一定程度上提高了定位精度，但算法在处理离散的、多维的问题时容易陷入局部最优的情况。

本文在对传统四面体质心定位算法进行分析的基础上，针对待测节点位于参考锚节点四面体内和四面体外的两种情况，利用筛选过RSSI值较优的 iBeacon参考锚节点，提出了一种新的三维传感网络定位优化算法的实现思路，并通过仿真环境对比验证了优化算法在定位精度和收敛速度方面的提升效果。

1.iBeacon测距技术

iBeacon锚节点以其自身为圆心，持续性向周围广播其UUID和位置信息。当支持BLE 4.0的设备进入广播区域时，通过设备端安装的应用即可获取参考锚节点的广播数据。

iBeacon锚节点的通信过程遵循无线信号传输模型。常见的无线信号传输损耗模型有自由空间传播模型、对数距离路径损耗模型和对数-常态分布模型，对数-常态分布模型为评估信号受不同环境影响的损耗程度，增加了一个随机变量，用于描述特定室内环境中信号传播损耗与传播距离之间的关系。因此本文在研究iBeacon锚节点构建的三维传感空间中的定位模型，将基于该模型进行研究。该模型使用公式表述如下：

PL(d) =PL(d0) + 10nlg(d/d0) +ε(式1)

其中d和d0为待测节点位于不同位置时与参考锚节点间的欧式距离，PL(d)和PL(d0)分别为距参考锚节点d和d0处的信号强度，其单位为dBm；n是一个经验值，作为无线传输信号的衰减因子，取值依赖于室内环境和建筑物的类型；ε为一个均值为0且同时服从高斯分布的随机变量。

若在定位过程中将待测节点置于d0=1m处，那么PL(d0)即为距iBeacon锚节点1m处的接收功率。在以下研究过程中iBeacon锚节点芯片型号相同，理论上其值将为固定值。因此iBeacon在室内三维传感环境下的信号传播模型可表述为：

RSSI=T- 10nlgd+ε

(式2)

其中T表示位于iBeacon参考锚节点1m处测得的RSSI值，T和n需要通过对多个相同芯片的iBeacon锚节点采集大量样本数据并进行筛选和拟合后得到。待测节点与各参考锚节点间的RSSI值可通过蓝牙终端测得。

2.三维定位优化算法

2.1传统四面体质心算法问题描述

在三维空间内随机部署有多个iBeacon参考锚节点，待测节点L位于三维传感空间中某处，如图1所示。

图1 待测节点L与四面体位置关系Fig.1 The relationship between the measured node L and tetrahedral position

A、B、C和D为四个不位于同一平面上的iBeacon参考锚节点，可构成四面体ABCD，M为四面体的质心，待测节点L位于四面体外。若利用传统坐标四面体质心算法进行待测节点位置的估算，将无法较好地处理L位于四面体外的情况，即利用质心M的位置估算为L的位置将造成较大误差；如果利用待测节点到四面体各顶点欧式距离的平均值判断待测节点与四面体的位置关系，仍存在误判的可能性；此外若L周围的iBeacon参考锚节点的数量不足4个，也无法使用传统四面体质心算法进行定位。因此在利用质心算法进行待测节点L位置的估算时，判断待测节点L与四面体ABCD的位置关系，优先选择包含待测节点的四面体并采用合理的定位方法，是本优化算法需要解决的问题。

另外传统四面体质心算法基于通用自由空间无线电传播路径损耗模型，将测得的RSSI值用于参考锚节点和待测节点间欧式距离的计算。因实际环境复杂性和节点性能分散性等因素的影响，实际的路径损耗与理论值并不吻合，因此所得的欧式距离的误差将导致四面体质心定位的误差。在以下优化算法研究过程中，将通过大量样本数据针对公式2进行拟合以提升算法的精度。

2.2三维定位优化算法

本文提出的优化算法是基于样本数据拟合所得的公式2，通过计算待测节点与各参考锚节点间的欧式距离，比较所构成的四面体的体积组成，最终筛选掉不包含待测节点的四面体构成方案。针对无法找到符合包含待测节点的四面体或可用于定位的iBeacon参考锚节点数达不到四个的情况，将考虑采用加权质心算法[10]进行位置估算。

由对数-常态分布模型可知，待测节点与iBeacon参考锚节点间的距离越近定位精度越高，即信号强度高的参考锚节点对定位精度起到更加显著的影响效果。因此有别于传统四面体质心算法，同时考虑到算法复杂度对定位效率的影响，以下将采用待测节点与iBeacon参考锚节点间欧式距离倒数之和作为加权因子。

三维定位优化算法主要实现思路描述如下：

步骤1RSSI信号采集和滤波筛选

待测节点根据其接收到的通信范围内所有参考锚节点的RSSI信号，分类记录各参考锚节点RSSI值样本数据集。与传统四面体质心算法不同，待测节点相对每个参考锚节点记录的样本集数据，通过高斯滤波模型进行滤波后取算术平均值作为该iBeacon参考锚节点的RSSI值，此举旨在避免测试过程信号干扰的同时，提升样本数据的稳定性。

将高斯滤波后确定的各参考锚节点对应的RSSI值按降序进行排列，取其中RSSI值较大的iBeacon参考锚节点作为定位待测节点的参考节点。

步骤2iBeacon信号传播模型拟合和测距

根据步骤1排序筛选后的样本数据，利用全站仪针对不同样本数据对应的iBeacon参考锚节点与待测节点之间的距离进行测量，生成RSSI值与节点间距离d映射关系集合，通过该集合数据拟合后计算公式2中各参数的具体取值，以确定iBeacon信号传播模型。相较传统四面体质心算法使用通用自由空间路径损耗模型，该拟合后得到的模型更适用于当前复杂室内环境中。

将待测节点置于其他位置并重复步骤1可得相应的样本筛选数据，利用步骤2确定的传播模型，记录待测节点与iBeacon参考锚节点间的测距数据集。

步骤3 确定参考锚节点构成的四面体

若待测节点L(x,y,z)通信范围内的iBeacon参考锚节点少于4个，则执行步骤6。否则从步骤2的测距数据集元素中，通过一定随机算法选择4个坐标位置已知的参考锚节点A(xA,yA,zA)、B(xB,yB,zB)、C(xC,yC,zC)和D(xD,yD,zD)组成四面体，如图2所示。

图2 四面体ABCDFig.2 Tetrahedron ABCD

为了让以上四个参考锚节点构成四面体，必须保证其不处于同一个平面上。

(式3)

若公式3中|r| = 0，说明四个参考锚节点位于同一个二维平面上。舍弃该参考锚节点组合，重复步骤3选择其他的参考锚节点组合。

步骤4 确定待测节点与四面体的位置关系

四面体六条边的长度dAB、dAC、dAD、dBC、dBD和dCD可通过计算已知坐标顶点间的欧式距离得到。待测节点L与四面体各顶点间的欧式距离dLA、dLB、dLC和dLD，可通过公式2计算得到。

假设四面体ABCD、LABC、LABD、LACD和LBCD的体积分别表示为V、V1、V2、V3和V4，若存在关系V=V1+V2+V3+V4，则待测节点L可认定为位于四面体ABCD内。若V

(式4)

(式5)

步骤5 四面体加权质心定位

重复步骤3和步骤4，得到符合条件的四面体集合，若集合为空则执行步骤6，否则执行如下步骤：

1)对集合中的每个四面体组合，依次利用已确定的加权因子计算其加权质心坐标。

2)对得到的一组加权质心坐标，依次随机选择4个作为顶点构成新四面体。若加权质心坐标数无法被4整除，则在接下来的迭代计算过程中，将剩余的加权质心坐标加入计算。通过步骤3的方法判断是否舍弃该四面体。若该四面体符合条件，继续利用加权因子计算其加权质心坐标。

3)重复以上两个步骤，当得到的加权质心坐标少于4个时停止计算。若最终仅存在1个加权质心坐标，则该坐标即为所求的四面体加权质心坐标。若最终存在2个或3个加权质心坐标，执行步骤6。

步骤6 非四面体定位

若待测节点通信范围内的参考锚节点少于4个或步骤5中的四面体集合为空，则参考锚节点不作共面判断，直接利用加权因子参照文献[10]进行加权质心计算，所得即为待测节点估计值。

2.3误差分析

利用本文算法进行定位的误差可表示为：

(式6)

其中(x,y,z)为待测节点L的实际坐标， (xe，ye，ze)为通过算法定位后L的理论坐标。若待测节点的个数为k，则可得本算法的平均误差E为：

(式7)

3.仿真实验

3.1 测距并拟合

选择一个80m*80m*80m的空间作为测试场所，进行iBeacon传播模型的测距拟合实验。首先将iBeacon参考锚节点置于测试场所中，然后设置40个测试点，通过全站仪将测试点分别设置于距该参考锚节点2m、6m、10m、…、78m处。使用支持BLE4.0的蓝牙设备在每个测试点采集100组RSSI样本数据。反复完成共50个相同芯片iBeacon参考锚节点的样本数据采集工作，并将高斯滤波后样本数据的平均值作为该位置的RSSI值。最后使用MATLABR2015b对样本数据进行拟合，拟合曲线如图3所示，得到拟合函数即iBeacon在室内环境下的信号传播模型为：

RSSI= -20.1lgd-50.6

(式8)

3.2 实验论证及分析

在相同实验环境中进行优化算法验证。使用MATLABR2015b进行优化算法仿真过程中，公式(2)中的信号衰减因子由以上拟合曲线可知为n=2.01，信道中的随机高斯噪声分布在5～10之间。传统四面体质心定位算法与优化算法的仿真结果如图4—图6所示。

在测试环境中部署20个参考锚节点并设定其通信半径为30m的情况下，从图4不难发现在将待测节点置于100个随机位置时，传统算法及优化算法随时间变化均呈现出收敛的趋势，优化算法的误差在25s左右已基本收敛于1.2m，而传统算法在40s左右才呈现较为明显的收敛状态，优化算法收敛精度和收敛时机明显优于传统算法。其原因在于优化

图4 平均误差随时间变化图Fig.4 Diagram of the mean error varies with time

算法对位于构成四面体的参考锚节点的共面情况和无法包含待测节点的情况进行了筛选，抛弃了无效的随机四面体构成方案，在加快收敛速度的同时有效降低了误差。同时通过拟合生成的公式8相较通用的自由空间路径损耗模型，在减小欧式距离定位误差的同时有效提升了优化算法定位精度。

图5 平均误差随通信半径变化图Fig.5 Diagram of the average error varies with communication radius

通过逐步增加部署参考锚节点的通信半径，在其数量为30个且采样频率为30s/次的环境中，随机部署100个待测节点。通过图5可知优化算法较传统环形定位算法表现出更高的定位精度和更快的收敛速度。在通信半径达到20m时误差范围已控制在1.2m以内，且随着通信半径的合理增加，其误差范围还将进一步减小。在通信半径达到40m时优化算法已表现出明显的收敛迹象，而传统算法在通信半径增加至70m时才逐渐表现出收敛趋势。若在实际三维传感空间中应用该算法模型，较小的通信半径意味着iBeacon参考锚节点将以更低的功率工作，能够有有效延长iBeacon的独立工作时间。

图6 平均误差随锚节点数量变化图Fig.6 Diagram of the average error varies with the number of anchor nodes

在参考锚节点通信半径设置为40m且采样频率固定为30s/次的仿真环境中，随机部署100个待测节点。通过增加参考锚节点的部署数量，两种算法均能有效提升定位精度。从图6可知优化算法较传统算法收敛速度更快，在实验环境中参考锚节点部署数量达到30个时平均误差已收敛至0.5m以内，而此时传统算法的平均误差仍高于1.5m。当前的定位精度及其所需的锚节点配置，已能够满足多数对精度要求不高的应用场景，若需进一步提升定位精度，可适当增加参考锚节点的数量。

4.结语

在三维无线传感网络中，如何有效提升算法定位效率和定位精度是当前传感网络定位领域的研究热点。本文结合iBeacon技术的普及应用场景，在研究和分析二维定位算法的基础上，通过对传统四面体质心定位算法进行改进，提出了基于iBeacon的三维传感网络定位优化模型。该算法模型通过筛选和舍弃位于同一个二维平面四面体顶点的锚节点组合，并结合待测节点位于随机四面体外情况的检测方法，对符合条件的四面体进行质心迭代求解，对非四面体的情况采用加权质心定位求解。在求解过程中利用拟合所得的iBeacon在室内环境下的信号传播模型，相较使用自由空间传播模型提升了定位精度。同时通过提升与待测节点较近的参考锚节点在定位过程中的地位，使用加权因子避免了非关键参考锚节点对定位精度的干扰。

仿真数据证明优化算法较之传统算法，能够表现出更高的定位精度和更快的收敛速度，体现了优化算法的优势。当前算法模型在定位效率和随机参考锚节点的选择方面还有一定优化空间，未来计划将该算法模型应用于实际项目中，通过应用环境进一步验证和改进算法模型的精度、性能和可适应性。

[1]SASI S B，SIVANANDAM N，EMERITUS.A survey on cryptography using optimization algorithms in WSNs[J].Indian Journal of Science & Technology，2015，8(3):216.

[2]AKBAS M I，EROLKANTARCI M，TURGUT D.Localization

for wireless sensor and actor networks with meandering mobility[J].Computers IEEE Transactions on，2015，64(4):1015-1028.

[3]赵大龙，白凤山，董思宇，等.一种基于卡尔曼和线性插值滤波的改进三角质心定位算法[J].传感技术学报，2015(7):1086-1090.

[4]张倬胜，艾浩军，马方方，等.基于iBeacon定位技术的智慧图书馆[J].电子产品世界，2015(1):31-35.

[5]张欣慧，徐晶晶，许必宵，等.无线传感器网络三维定位算法研究[J].计算机技术与发展，2016，26(12):195-199.

[6]张冠华，侯立刚，曹江涛，等.基于DV-hop算法的楼宇内三维投影质心定位算法研究[J].测控技术，2015，34(2):118-120.

[7]黄庆宇，刘新华.基于线性最小二乘估计的传感网节点三维测距定位算法[J].计算机工程，2016，42(12):11-15.

[8]梁娟，吴媛.采用WSVM的三维无线传感器网络节点定位[J].华侨大学学报(自然科学版)，2016，37(1):79-83.

[9]张烈平，陈鸣，季文军.基于PSO优化LSSVR的三维WSN节点定位方法[J].中国科技论文，2014(1):24-27.

[10]林信川，游贵荣.基于iBeacon的室内定位算法优化研究[J].陕西理工大学学报(自然科学版)，2017，33(3):67-73.

(责任编辑：杨成平)

PositioningOptimizationAlgorithmofThree-dimensionalWSNsBasedoniBeacon

LIN Xin-chuan

(Department of Information Management and Engineering,Fujian Business University, Fuzhou 350012, China)

Aiming at the problems of low localization accuracy and slow convergence of traditional tetrahedral centroid algorithm in three-dimensional wireless sensor networks (WSNs), a positioning optimization algorithm in three-dimensional WSNs based on iBeacon is proposed. The signal propagation model of iBeacon in the indoor three-dimensional sensing environment is established by sampling, filtering and fitting before positioning. This algorithm eliminates the situations that the nodes to be measured are located outside the tetrahedron of the reference anchor node, and the situation that the reference anchor nodes are in the same plane in the positioning process, and then uses the optimized weighting factor to enhance the role of the reference anchor node near the node to be measured. In the case of satisfying the conditions of the tetrahedron, the tetrahedron weighted centroid iteration is used to solve the problem. Otherwise, the optimized weighting factor is used to locate the unknown node. The simulation results show that this algorithm can improve the positioning accuracy and convergence speed compared with the traditional tetrahedral centroid algorithm.

three-dimensional positioning of wireless sensor networks (WSNs); iBeacon; anchor node; RSSI; weighting factor

TP212.9，TP301.6

A

2096-3300(2017)05-0093-08

2017-08-15

福建省教育厅中青年教师教育科研项目(科技类)“室内三维传感空间定位模型优化研究”(JAT170690)。

林信川(1981-)，男，福建福州人，讲师，硕士。研究方向：物联网、移动互联网。