无线传感器网络中APIT-SC 三维定位算法*

周礼争，唐 瑞，张乙竹，程 俊，余 敏

(1.江西师范大学 计算机信息工程学院，江西 南昌330022;2.江西师范大学 软件学院，江西 南昌330022)

0 引 言

在无线传感器网络(wireless sensor networks，WSNs)应用中，定位应用是最热门的应用研究之一。WSNs 节点定位技术是众多应用得以实施的基础和前提，也是研究的重点和难点。

WSNs 节点定位算法分为基于测距(range-based)和基于非测距(ranged-free)两类［1，2］。基于测距的定位一般需要额外的硬件支持，如TOA，AOA 及RSSI 等算法［3，4］，测量彼此间的绝对距离或角度，再利用三边测量法、三角测量法或极大似然估计法等估算位置信息。基于非测距的算法一般是利用节点间连通性、相邻特性实现定位，如质心法、DV-Hop 及APIT 等［5～7］。

在众多的三维(3D)定位算法中，DV-Hop 定位算法已近完善，但始终存在精度问题。而在其他方法中，引人关注的是刘玉恒等人提出的WSNs 近似四面体内点的三维(approximate point in tetrahedron 3D，APIT—3D)定位算法［8］。文献［9］提出基于质心迭代的APIT 定位算法，以质心迭代代替网格扫描求解定位坐标。文献［10，11］都提出基于中垂面的APIT 定位算法，以中垂面切割缩小未知节点存在区域。在上述文献思想上，本文提出一种基于球切割的APIT(APIT-SC)定位算法，未知节点定位任务分解到周围锚节点，自己求解各锚节点上报存在区域的交集的质心作为定位结果。

1 相关算法描述

1.1 基于中垂面的3D 定位算法

陈月娥、余敏提出的APIT—VP 定位算法［10］。首先，以PIT—3D 测试确认未知节点在四面体内。其次，任选取两锚节点连成线段，并以该线段的中垂线形成中垂面，未知节点对其感知这2 个锚节点的RSSI 值作比较，判断自身在中垂面的哪一侧。重复上述操作，必划分出共同区域，则以此区域质心为定位坐标。

1.2 APIT—3D 算法分析

该算法的思想: 未知节点收集可感知的锚节点，任意选4 个非共面锚节点组成四面体，以某种技术［10］判断自身是否在四面体内，若在四面体内，则称该四面体区域为未知节点存在区域(presence area，PA)。穷尽所有PA 的四面体组合，用3D 网格扫描算法获得PA 的交域，并以交域质心作为定位结果。APIT—3D 算法的基础是PIT—3D 测试原理:当未知节点在四面体外时，存在邻居节点沿着一个方向运动，邻居节点必同时远离或靠近四面体4 个锚节点。若不存在，则未知节点必在四面体内。在现实中，利用WSNs 节点分布特性，未知节点的邻居节点判断各自与锚节点距离的远近，很大程度上实现对球面所有方向进行测试。PIT—3D 测试中，通常以RSSI 的强弱来判断远离或靠近四面体的锚节点。

APIT—3D 算法有以下缺陷:

1)在PIT—3D 测试中，当未知节点的邻居节点数量较少或处于某些特殊位置时，会引起PIT 测试出现InToOut 和OutToIn 错误。

2)在节点分布不均匀时，节点密度较大的区域会引起PI—3D 测试计算量偏大。而节点密度较小时，定位精度较低，或当锚节点数量小于4 时，无法以APIT—3D 进行定位。

3)在穷尽PA 四面体交域时，采用网格扫描算法，计算量较大，效率低下。

1.3 APIT—SC 算法设计

针对APIT—3D 算法存在上述缺陷，本文提出APIT—SC定位算法，做了以下完善:1)采用四面体体积规则减少In-ToOut 和OutToIn 错误。2) 在节点密度较大时采用轮回选择法，避免一段时间内只在小区域内寻找满足PIT—3D 的邻居节点。当锚节点不足以构成四面体时，以RSSI 加权三维质心定位算法进行定位。3) 以球切割法代替网络扫描法减少计算复杂度。

体积规则:

如图1 所示，若未知节点E 在四面体内，则VABCE+VABDE+VBCDE+VACDE=VABCD;若E 在四面体外，即E'，则VABCE'+VABDE'+VBCDE'+VACDE'＞VABCD，其中VACDE'计算了2 次，有利于探测边缘效应［6］。根据RSSI 对数测距模型［12］，距离值和RSSI 值是一一对应的函数关系，故可用RSSI 值代替距离值做定性分析，即dAB=|RSSIBA－RSSIAA|，其中RSSIBA为B 点感知A 点RSSI 值，RSSIAA为A 点感知自身RSSI 值。根据欧拉四面体数学模型［13］，四面体体积公式如式(1)所示

其中，l，m，n，p，q，r 为四面体6 条棱长。

图1 体积规则示意图Fig 1 Diagram of volume rule

轮回选择法:

未知节点邻居节点如图2 所示，轮回选择步骤如下:

1)将未知节点的邻居节点分别以其感知四面体4 个锚节点RSSI 值进行排序形成4 组RSSI 单调邻居节点队列。

2)分别轮回从4 组RSSI 队列中取元素进行PIT—3D 测试，若符合，则返回测试结果并退出算法;若不符合，则在其他3 组中标记该邻居节点已被测试，执行步骤(3)。

3)重复步骤(2)，直到找到满足PIT—3D 测试的邻居节点或队列为空时，返回测试结果并退出算法。

图2 未知节点邻居节点示意图Fig 2 Diagram of neighbor nodes of unknown node

APIT—SC 算法流程如图3 所示，步骤如下:

1)在空间部署节点形成WSNs，网络初始化。

2)未知节点U(x，y，z)定位时，感知周围锚节点，记录可见锚节点信息(ID、空间坐标、RSSI 值)，将可见锚节点以其返回的RSSI 值进行降序排序存入队列Q-list(数组构成)，设队列长度为LQ 且元素个数为N。

3)若N ＜1，则执行步骤(4);若1≤N≤3，则执行步骤(5);否则，执行改进的APIT—SC 算法。

改进的APIT—SC 算法:

a.从锚节点队列中Q-list 中任选4 个锚节点，进行PIT—3D 测试和体积规则判断，将合法的四面体组合存在四面体集合Tset中，并计算每个组合两两锚节点间距离，若它们之间的距离极其接近(距离方差小于P)，则标记该组合球切割方法状态为N;否则，为Y。

b.若集合Tset为空，则执行步骤(5);否则，取集合Tset一个元素，若方法状态是N，则用RSSI 加权质心定位算法。若方法状态是Y，则对4 个锚节点两两间的距离进行排序，选距离值最小两端点的一端点作为定位发起者和球心，以球心到其他3 个锚节点距离值为半径建立3 个球，一般最大球会被其他2 个较小球切成三部分。再分别用球心探测未知节点的RSSI 值和其探测其他3 个锚节点的RSSI 值作比较，则未知节点必在这3 个区域某一区域。然后该球壳与四面体的交域作为该组合下未知节点存在区域。如图4所示，设锚节点B 感知未知节点U 的RSSI 值小于其感知锚节点D 的RSSI 值但又大于其感知锚节点A 的RSSI 值，所以，未知节点必在S2的球壳与四面体交集区域。

c.重复步骤b，求方法状态是Y，则所有四面体组合下未知节点存在区域，并将这些区域交集的质心作为定位结果。

4)若未知节点周围没有可见锚节点，则休眠一定时间t后，再向邻居节点发送定位请求，此时感知到的锚节点为N，则转入步骤(3)执行。

5)若1≤N≤3 或四面体集合Tset为空，则用RSSI 加权3D 质心定位算法［12］定位。

图3 APIT-SC 算法流程图Fig 3 Flow chart of APIT-SC algorithm

2 仿真实验和性能分析

为了验证APIT—SC 算法的性能，使用Matlab 进行仿真。仿真环境如下:3D 空间为106m3的立方体内随机部署500 个节点，锚节点控制在5%～30%，节点间通信半径均相同。考虑随机分布和偶然因素的影响，以仿真100 次的均值作为结果。仿真以不同的锚节点比例来对比APIT—SC 和APIT—3D 算法性能。

图4 球分割法示意图Fig 4 Diagram of SC method

2.1 定位覆盖率分析

定位覆盖率与锚节点比例关系如图5 所示。当锚节点比例是5%时，APIT—3D 定位覆盖率在10%左右，而APIT—SC 定位覆盖率是APIT—3D 算法的3 倍，这说明APIT—SC 算法考虑了当锚节点个数较少特殊情况。随着锚节点比例升高，两种算法的定位覆盖率明显升高。当锚节点比例上升到20%左右，APIT—SC 定位覆盖率达到85%左右。随后再随着锚节点比例的增大对覆盖率的影响越来越小，这是由于APIT—SC 算法引入未知节点转化为锚节点辅助定位。

图5 锚节点比例和定位覆盖率关系Fig 5 Relationship between localization coverage rate and ratio of beacon nodes

2.2 定位误差分析

定位误差和锚节点比例关系如图6 所示。当锚节点比例在5%时，APIT—SC 的定位误差比APIT—3D 大，这是因为引入的辅助定位算法定位精度低。当锚节点比例增大到15%～20%，两种算法定位误差相当。随着锚节点比例增加，APIT—SC 性能优胜于APIT—3D，这由于本文提出两种新的规则，又采用球切割法缩小未知节点存在区域。

图6 锚节点比例和定位误差关系Fig 6 Relationship between localization error and ratio of beacon node

3 结 论

本文在APIT—3D 基础上，提出改进的APIT—SC 算法。仿真实验表明:APIT—SC 算法克服锚节点比例较低时无法定位问题，同时根据RSSI 值缩减未知节点存在区域，提高定位精度。APIT—SC 算法在定位覆盖率和定位精度均达到预期效果，定位覆盖率可达91%，定位误差缩减至23%左右，是一种适应性强的3D 定位算法。

［1］ 信召建，胡 屏，王 玲，等.基于RSSI 值的WSNs 节点测距算法改进和定位实现［J］.传感器与微系统，2014，33(6):133－136.

［2］ 王佩琦，李艳萍，陈相南，等.基于RSSI 距离修正的WSNs 定位算法［J］.传感器与微系统，2014，33(5):135－137.

［3］ Nasipuri A，Li K.A directionality-based location discovery scheme for wireless sensor networks［C］∥Proceedings of ACM International Workshop on Wireless Sensor Networks and Application，Atlanta，USA，2002:105－111.

［4］ Girod L，Estrin D.Robust range estimation using acoustic and multimodal sensing［C］∥Proc of IEEE International Conference on Intelligent Robots and Systems，2001:1312－1320.

［5］ Zhang Jianping，Yu Min，Zhang Ke，et al.An improved weighted triangle centroid localization algorithm of APIT for wireless sensor networks［C］∥2012 International Conference on Computer and Information Science，Safety Engineering，Wuhan，China:IEEE，2012:18－21.

［6］ Zeng Fanzhen，Yu Min，Zou Chengwu，et al.An improved point in triangulation localization algorithm based on cosine theorem［C］∥2012 8th International Conference on Wireless Communications，Networking and Mobile Computing，Shanghai，China:IEEE，2012:1652－1655.

［7］ Rong P，Sichitiu M.Angle of arrival localization for wireless sensor networks［C］∥Proc of SECON’06，Reston，USA:IEEE，2006:374－382.

［8］ 刘玉恒，蒲菊华，赫 阳，等.无线传感网络三维自身定位方法［J］.北京航空航天大学学报，2008，34(6):647－651.

［9］ 王长征，汤文亮，徐 燕.无线传感器网络中四面体三维质心定位算法［J］.传感器与微系统，2012，31(8):141－146.

［10］陈月娥，余 敏.无线传感器网络中APIT—VP 三维定位算法［J］.传感器与微系统，2014，33(5):148－150.

［11］刘志强，王行甫.基于中垂面分割的WSNs 三维定位方法［J］.计算机工程，2010，36(14):90－92.

［12］王婷婷，柯 炜，孙 超.自适应环境变化的RSS 室内定位方法［J］.通信学报，2014，35(10):210－217.

［13］王荣波.基于Mathematica 下的欧拉四面体问题［J］.数学教学与研究，2010，12(1):74.