76 ⦾ 2013，49（10） Computer Engineering and Applications 计算机工程与应用 网络、通信、安全 ⦾ 基于锚球交域重心的 WSN 三维定位算法研究 夏心江 1，2，胡 钢 1，2，王烨华 1，2 XIA Xinjiang1，2, HU Gang1，2, WANG Yehua1，2 1.河海大学 计算机与信息学院，江苏 常州 213022 2.常州市传感网与环境感知重点实验室，江苏 常州 213022 1.College of Computer and Information, Hohai University, Changzhou, Jiangsu 213022, China 2.Changzhou Key Laboratory of Sensor Networks and Environment Perception, Changzhou, Jiangsu 213022, China XIA Xinjiang, HU Gang, WANG Yehua. Research on three-dimensional positioning algorithm of wireless sensor network based on cross domain gravity center of anchor balls. Computer Engineering and Applications, 2013, 49（10）：76-79. Abstract：The paper presents a three-dimensional positioning algorithm about wireless sensor network based on Bounding Cube algorithm with cross domain gravity center of anchor balls. The algorithm calculats the possible position of the unknown node by solving intersect ball regional gravity center. The algorithm simplifies complexity of the calculation with dimensionality reduction. Simulations result shows that when 1,000 sensor nodes are deployed randomly within the region in a confine of 10 m×10 m×10 m, the positioning accuracy of the algorithm on average rise up 48.93 percent compares to Bounding Cube algorithm when the proportion of anchor nodes rising from 4 percent to 10 percent. It only uses 40 anchor nodes to lower the position error to 31.96%. Key words：wireless sensor networks; cross-domain gravity center of anchor ball; three dimensional localizations; dimension reduction; positioning accuracy 摘 要：针对无线传感器网络在三维空间应用场景，基于 Bounding Cube 算法，提出一种基于锚球交域重心的无线传感器 网络三维定位算法，通过求解相交球区域重心，确定未知节点可能的定位坐标位置。算法通过降维处理，简化了计算的复 杂度。仿真结果表明，在 10 m×10 m×10 m 的区域内随机部署 1 000 个传感器节点，锚节点比例由 4%增加到 10%的过程中， 算法的定位精度比 Bounding Cube 算法平均提升了 48.93%，仅需 40 个锚节点，就能将定位误差降低到 31.96%。 关键词：无线传感器网络；锚球交域重心；三维定位；降维；定位精度 文献标志码：A 中图分类号：TP212 doi：10.3778/j.issn.1002-8331.1107-0153 在无线传感器网络（Wireless Sensor Networks，WSN）[1-2] 应用中，其工作区域有时是人类不适合进入的区域，但节点 所采集到的数据又必须与被测点的位置相结合才有意义。 考虑到节点能量有限，因此，必须要以最小能量的通信开 销和硬件代价实现节点定位[3]。 现有的二维定位系统受限于功耗与成本，很难推广到 实际的三维空间应用中。因此，针对三维空间定位问题， 人们提出了很多算法 [5-7]。这些非测距三维定位算法虽然 都取得了一定效果，同时也存在着通信和计算开销大、定 位精度不够高、依赖基础设施等不足[8]。 目前的各种定位算法中，大多数针对二维平面进行定 位，而现实应用中的无线传感器网络节点往往是分布在三 维空间中，它相比于二维空间中的无线传感器网络具有更 丰富的位置信息，且网络规模、分布密度和定位复杂度也 都有所增加，因此，研究三维空间定位更具有实用性和发 展潜力[4]。 文献[9]提出了 bounding cube 算法，该算法根据未知 节点邻居已知节点的通信范围，确定出包含有未知节点的 限定立方体，然后用立方体的质心作为未知节点的估计位 置。该算法具有计算简单、计算量小的特点，不足之处是 对节点密度和通信半径有一定的要求，且算法对通信范围 本身采取一定的近似处理，容易造成定位误差。因此，本 基金项目：中国水利水电科学研究院开放研究基金项目（水科科计便函[2008]010 号）；常州市科技攻关项目（No.CE20090036）。 作者简介：夏心江（1986—），男，硕士，研究方向：无线传感器网络定位；胡钢（1958—），男，教授，硕士生导师，研究方向：无线传感器网络。 E-mail：jianghehai1@163.com 收稿日期：2011-07-08 修回日期：2011-10-18 文章编号：1002-8331（2013）10-0076-04 CNKI 出版日期：2011-11-14 http://www.cnki.net/kcms/detail/11.2127.TP.20111114.0951.091.html 

夏心江，胡 钢，王烨华：基于锚球交域重心的 WSN 三维定位算法研究 2013，49（10） 77 文提出了一种改进算法：基于三维空间锚球交域重心的无 线传感器网络定位算法，算法主要通过改变相交球半径大 小确定交集区域，再求出交集区域的重心，即为未知节点 的估算坐标。算法特点是保持了 bounding cube 算法计算 量小的优点的同时，大大提高了定位的精确度。 1 锚球交域重心定位算法 1.1 问题提出 Bounding Cube 算法通信范围采用近似处理，算法本 身加入了一定误差，该算法的近似通信范围是 1 个内接于 球体的正方体，如图 1 所示。 A L/ 2 R S L/2 O L 图 1 Bounding Cube 算法节点近似通信范围 设正方体的边长为 L，球半径为 R，则有 SO = L 2 ，SA = ，由三角形三边关系得： L 2 L 2 2 ö ø÷ = R2 2 ö ø æ è L 2 + æ èç 解之得： L = 2R 3 因为通信范围是近似处理，所以有部分区域在定位之 初便被忽略，这部分区域体积大小 V - L3 = 4 3 πR3 - 8R3 V = 4πR3 3 x 3 3 为： x 将因通信范围近似处理而产生的误差定义为节点通 信覆盖误差 ε ，误差大小为某锚节点通信范围近似处理 后 未 被覆盖部分体积 V 与原通信范围覆盖体积 V 百分 比。Bounding Cube 算法的节点通信覆盖误差为： x ε = V x V ´ 100% = 4 3 πR3 - 8R3 3 3 4πR3 3 ´ 100% = 3 π - 2 3 π ´ 100% » 63.24% Bounding Cube 算法通信范围的近似处理导致 63.24% 的定位覆盖误差。因为，图 1 中未知节点如果位于正方体 与球体之间，则在定位过程中将被近似处理到正方体内 部，节点的真实位置信息被人为改变。 如果通信范围未进行近似处理，即以球体做节点通信 x 范围，则 V V x V ε = = 0 ´ 100% = ´ 100% = 0 0 4πR3 3 因为图 1 中未知节点位于球内任何位置，都认为其已 处于定位空间内，无需做任何近似处理，所以，节点的真实 位置信息将被真实记录。 1.2 锚球交域重心定位算法原理 以一个锚节点为球心，分别以它到附近未知节点之间 的距离为半径画球，接着将半径按照一定的规则增加一个 数值，待定位的节点必然位于球内。以不同的锚节点做球 心，找到一系列包含待定位节点的球，则任意一个待定位 节点被同时包含在不同的球内，取这些球的交集作为待定 位节点最可能存在的最小区域，取这个小区域的重心坐标 作为未知节点的坐标，如图 2 所示。 Ai 锚节点 S 相交区域 P 未知节点 Intersection Field S Anchor A1 Unknown Node P S P Anchor A3 Anchor A2 图 2 算法三维空间定位示意图 对于三维空间的定位，其计算量非常大，而传感器节 点能量有限，使节点无论是计算能力还是通信能力都有 限。所以，在定位过程中，有效地降低运算复杂度，提高运 算效率是十分必要的。 本文算法在三维定位思路的基础上，为了降低运算 量，将三维坐标分别向 XOY、YOZ 平面做投影，三维空间定 位问题转换为二维平面的定位。由于向平面投影后，得到的 圆半径大小不变，所以，平面定位的结果真实反映了未知节 点的空间位置情况，图 3 所示为三维空间在 XY 平面的投影。 b y Unknown Node P Anchor A1 Intersection Field S Ai 锚节点 S 相交区域 P 未知节点 P Anchor A3 Anchor A2 图 3 三维空间在 XY 平面的投影 b x 图 3 中 P 位于锚节点 A 1 2 所对应的坐标为 (x 、A 、A 所确定的相交区域 S  R ， 2 n 与相邻锚节点的距离，即初始球半  R ) ，R 1  y i 3 i 内部。令锚节点 A n > 0 为某个未知节点 P i i 

78 2013，49（10） Computer Engineering and Applications 计算机工程与应用 为某个规则下需要增加的半径值。则未知  d 径，d 1 节点 P i n  d 2 将位于如下区域 S 内： ) min(x i ) min(y S = (max(x i (max(y - R i - R - d i - d j j j + R i + R j j + d i + d )) ´ )) j 3.809 1，分别将值填入表 2 中 X1 所在行的第 1、第 2 个位置。 2.2 求解域锚球 通过事先制定的规则计算域锚球半径 R，并保存在表 3 中，保存规则与表 2 相同。 同理，可求出在 YZ 平面上的投影区域 Q ，则未知节点 表 3 各未知节点保存的锚球半径 最终坐标在以下区域 N 内： N = Q  S = (max(x (max(y (max(Z - R j - R k j k + d )) ´ i ) min(x i - d - R i ) min(y j ) min(Z i - d j - d k + R i )) ´ i + d j + d )) k + R j + R k k 对区域 N i 求重心坐标可得未知节点的最终估算坐标。 1.3 锚球交域重心定位算法步骤 步骤 1 提取位置信息。锚节点以功率 P 向周围未知节 点广播自己的位置信息，未知节点则可以监听到附近锚节 点的位置信息，记录这些锚节点的信号强度，利用信号强 度计算出锚节点与未知节点之间的距离，将所求的值作为 以锚节点为球心的初始球半径，将这类球命名为点锚球。 步骤 2 按照一定的规则增加球半径，使未知节点包含 于该球内，将这类球命名为域锚球。 步骤 3 将空间中所有节点及锚球分别向 XOY、YOZ 平 面投影。 步骤 4 求出所有包含未知节点的相交圆区域。 步骤 5 求出这个交集区域的重心坐标作为未知节点 估算坐标。 2 锚球交域重心定位算法实现 本文在求相交圆区域时采用扫描标记点法，本文方法 是将平面划分成许多大小相同的小正方形，取正方形的中 心点作为这个小正方形的标记点，这个标记点的坐标即代 表了这个小正方形的近似坐标。 2.1 位置信息提取 未知节点监测到附近的锚节点信号，将这些锚节点编 号保存在表 1 中，同时通过信号强度计算出初始球半径 r， 并保存在表 2 中。例如表 1 中编号为 X1 的未知节点所监测 到的锚节点编号为 20，23，32，……59，其中，经过计算 20 号、 23 号锚节点与 X1 未知节点间的距离分别为 3.306 7、3.809 1， 说明这两个锚节点所对应的点锚球半径分别为 3.306 7、 表 1 各未知节点保存定位所需已知节点位置信息 未知节点编号 未知节点所监测到的锚节点编号 X1 X2 ︙ Xn 20 25 ︙ 23 23 26 ︙ 32 32 27 ︙ 34 … … … 57 54 ︙ －1 59 58 ︙ －1 表 2 各未知节点保存锚节点的初始球半径 节点编号 点锚球半径 (x X1 X2 ︙ Xn 3.306 7 0.113 7 ︙ 3.809 1 2.618 1 ︙ 4.144 0 1.975 7 ︙ 0.888 0 3.731 0 0.820 3 … … … 1.662 2 3.139 2 ︙ －1 i_c i_c  z i_c ) 为未知节点 i 的实际坐标。  y n 个未知节点的平均定位误差为： i_r i_r i_r - -- ----- error] = [ n å i = 1 error i n × 100% 节点编号 域锚球半径 X1 X2 ︙ Xn 3.372 9 0.115 9 ︙ 3.885 3 2.670 4 ︙ 4.226 9 2.015 2 ︙ 0.905 8 3.805 7 0.836 7 … … … 1.695 5 3.202 0 ︙ －1 2.3 确定相交圆区域 针对某一未知节点，计算各标记点到锚节点的距离，判 断这个距离值是否小于表 3 中对应的值，如果小于表 3 的数 值，则在表 4 中相应的标记点位置上增加 1，记为扫描次数增 1，最后，认为被扫描次数最多的标记点位于相交区域内，同时 记录下标记点的坐标值 Xi，Yi。例如表 4 中 2 号标记点被扫 描的次数达到最大值 15，则确定该标记点位于相交区域内。 表 4 某未知节点保存小正方形被扫面次数 标记点编号 扫描次数 1 13 2 15 3 14 4 15 5 11 … … n1 14 2.4 计算定位坐标 根据表 4 的数据，统计各相交区域中标记点的个数 N， 填入表 5，综合表 4、表 5 数据，求出表 4 标记点的 X、Y 坐标 的均值，作为某未知节点 X，Y 坐标的估算值，即： X_估算 = X N å i = 1 N i ，Y_估算 = N å Y i = 1 N i 表 5 某未知节点保存标记点被扫面次数 未知节点编号 标记点个数 X1 2 336 X2 412 X3 318 … … Xn 479 3 锚球交域重心定位算法仿真及性能分析 为比较验证本文算法与 Bounding Cube 算法，并观察 本文算法在不同规则条件下的性能。本文采用 MATLAB 对该算法进行了仿真实验。仿真环境为在 10 m×10 m×10 m 的区域内随机部署 1 000 个节点，锚节点的通信半径为 5 m。 锚节点比例由 4%增加到 10%每次变化 1%，即锚节点个数 由 40 变化到 100，每次增加 10 个锚节点。 3.1 定位误差 定位误差公式为： [error ] = (x - x )2 + (y - y )2 + (z - z )2 i_r i_c i_r i_c i_r i_c 其中，( x  z ) 为本文算法估算的未知节点 i 的坐标， i  y 

夏心江，胡 钢，王烨华：基于锚球交域重心的 WSN 三维定位算法研究 2013，49（10） 79 实验中，本文算法设定了计算锚球的 2 个规则，具体定 义及仿真结果如下： 规则 1 在求锚球半径的过程中，采用初始球半径静态 增径法，即： R = r + d 其中，R 为域锚球半径，r 为点锚球半径，d 为固定值，d 值可 由人为设定，值的大小可根据实际经验确定。在本实验 中，d 的值取 0.1 m，分别对本算法与 Bounding Cube 算法进 行仿真，结果如图 4 所示。 N å i = 1 n T X_i N t = 其中，T 为扫描每个标记点所用时间，n 为求解第 i 个未 X_i 知节点所需标记点个数，N 为未知节点总数。 图 6 所示为两种规则下，锚节点密度变化对运算时间 的影响情况。从仿真图中可以看出随着锚节点密度的增 加，两种规则反应出不同的特性，规则 1 条件下运算时间增 加，而规则 2 条件下的运算时间稳定在 180 T 左右。 锚球交域重心定位算法 bounding cube 算法 0.7 0.6 0.5 0.4 0.3 0.2 0.1 ） % /（ 差 误 位 定 均 平 800 700 600 500 400 300 200 / T 间 时 算 运 规则 1 规则 2 0 0.4 0.5 0.7 0.6 0.8 锚节点密度/（%） 0.9 1.0 图 4 两种算法定位误差对比图 100 0.4 0.5 0.7 0.6 0.8 锚节点密度/（%） 0.9 1.0 图 6 锚节点密度与运算时间 从图 4 中可以看出，仅需 0.04%的锚节点（即 40 个锚节 点）的情况下，就能将定位误差降低到 31.96%。在同等条 件下，本文算法的平均定位误差明显比 Bounding Cube 算 法要小，精度提升了 48.93%。在其他条件不变的情况下， 增加锚节点密度，本文算法的定位误差随之降低，说明本 文算法的精度与锚节点的密度有很大关系。 规则 2 在求锚球半径的过程中，采用初始球半径动态 4 结论 本文提出一种基于锚球交域重心的无线传感器网络 三维定位算法，将三维空间定位问题转换为二维平面的 定位，简化了算法的复杂度，同时降低算法计算量，对传 感器节点能量有限的情况下能取得很好的效果。通过算 法仿真表明，该算法定位精度能够满足三维空间的定位 要求。 增径法，即： R = r + r 10R r 其中，R 为域锚球半径，r 为初始球半径，R 半径。 r 为锚节点通信 图 5 反映两种规则下，锚节点密度对平均定位误差影 响的对比情况，图中显示在锚节点密度达到 60%之前，规则 2 条件下的仿真结果定位精度相对比较高，在达到 60%之 后，两种规则下的定位精度相差不大。 规则 1 规则 2 ） % /（ 差 误 位 定 均 平 0.40 0.35 0.30 0.25 0.20 0.15 0.10 0.05 0.4 0.5 0.7 0.6 0.8 锚节点密度/（%） 0.9 1.0 图 5 两种规则下算法仿真对比图 3.2 运算时间分析 运算时间公式为： 参考文献： [1] Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）： 393-422. [2] Niculescu D，Nath B.Ad Hoc positioning system（APS） us- ing AOA[C]//Proc of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies INFO- COM 2003.San Francisco，CA，USA：IEEE，2003：1734-1743. [3] 刘衍珩，刘炳日.WSN 中一种 DV-Hop 定位精度改进算法[J].吉 林大学学报：工学版，2010，40（3）. [4] 于宁，万江文，马万兴.无线传感器网络三维抽样定位[J].北京 邮电大学学报，2008，31（3）. [5] 刘玉恒，蒲菊华，赫阳，等.无线传感器网络三维自身定位方 法[J].北京航空航天大学学报，2008，34（6）：647-651. [6] Ou C H，Su K F.Sensor position determination with flying anchors in threedimensional wireless sensor networks[J].IEEE Transactions on Mobile Computing，2008，7（9）：1084-1097. [7] 吕良彬，曹阳，高洵，等.基于球壳交集的传感器网络三维定位 算法[J].北京邮电大学学报，2006，29（增刊）：48-51. [8] 王德华，邢建平，张军.无线传感网的分布式非测距三维定位 算法[J].北京航空航天大学学报，2010，36（2）：206-209. [9] 李娟，王珂，卢长冈.Bounding Cube：一种无线传感器网络节点 三维定位算法[J].中国海洋大学学报，2009，39（6）：1265-1268.