基于共面性与区域限制的三维wsn定位算法

1、第 43 卷 增刊8 月计 算 机 研 究 与 发 展JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENTVol.43, Suppl. Aug. 2006基于共面性与区域限制的三维 WSN 定位算法谭大元宋国治廖冬阳李润东(天津工业大学 计算机科学与软件学院 天津 300387)(guo)摘要 定位是无线传感器网络技术和应用的重要组成部分，相对于二维定位，三维定位更符合实际需求。在三维空间中，我们利用四面体的特性，提出一个基于共面性和区域限制的 3D 定位算法，并给出算法实现。仿真表明，对节点进行定位中，我们提出的定位算法，定位精度明显优于经典的 DV-ho

2、p 算法和质心算法，并且稳定性也高于另外两者。关键词 无线传感器网络；三维定位；共面性；体积比阈值中图法分类号 TP3913D Localization Algorithm for Wireless Sensor Networks Based on Degree ofCoplanarity and Restricted SpaceDayuan Tam,Guozhi Song,Dongyang Liao and Rundong Lee(School of Computer Science & Software Engineering, Tianjin Polytechnic University

3、, Tianjin 300387)Abstract Localization is an important part of Wireless Sensor Networks technology, and only the 3D location technology is appropriate for real applications. We propose a novel 3D localization algorithm based on DCP (Degree of Coplanarity) and Restricted Space. Simulation results ind

4、icate that the average location accuracy of the improved localization algorithm is much better than classical 3D DV-hop algorithmand Centroid algorithm. Moreover the stability of the new algorithm is better than others.Keywords Wireless Sensor Network; Degree of Coplanarity ; 3D Localization ; Volum

5、e Ratio threshold无线传感器网络 (Wireless Sensor Networks, WSNs )技术是一种全新的信息获取和处理技术，由于自身具有自组织、部署快捷、高容错等特性，因此可以广泛应用在军事、工农业、医疗、智能家居、海洋探测等领域中1。其中传感器位置信息对于无线传感器网络来说是一个非常重要的信息2，许多传感器网络的应用都是以位置信息为基础的，因此能否精确定位显得尤为重要。传统的传感器节点定位算法可以分为基于测距的定位算法和基于非测距的定位算法两大类3，基于测距的定位算法是通过获取节点到节点的距离来计算节点定位，常见的基于测距定位算法有 RSSI(Received S

6、ignal Strength indication) 4、TDOA (Time Difference of Arrival) 5、AOA (Angle of Arrival ) 6等；非测距的定位算法一般利用节点间的关系和连通性来估计位置坐标，典型的基于非测距的定位算法有 DV-hop (Distance Vector-hop)算法7, 8、质心算法9、 APIT (Approximate PIT Test)算法10等。由于基于测距的定位算法往往需要在节点上添加额外的设备，因此有较高的成本限制和硬件条件的约束，所以我们更倾向于研究基于非测距的定位算法。现实应用中，节点的位置可能在山峰、海底等非

7、平面的位置，测定的区域也非平面，所以二维节点定位算法无法满足现实应用的需求，有必要进行三维定收稿日期：2015-05-17基金项目：国家级大学生创新创业训练计划项目(201410058046)，国家自然科学基金（61272006），天津市教委科技发展基金(No.20110808)本论文第一作者为学生2计算机研究与发 展位算法的研究。现阶段很多学者已经开始着手于三维定位算法 的研究。针对不同的问题与应用，人们已经提出了多 种三维定位算法，其中有许多三维定位算法是由传统 的二维定位算法衍生而来的，文献11中就是将一个 二维质心算法进行加权改进，扩展至三维空间衍生成 为三维加权质心算法；文献12首先

8、将二维 DV-hop 扩 展到三维 DV-hop，然后在三维 DV-hop 算法的基础 上，对形状和层次结构进行分析，接着引入共面和投 影的性质，实现位置定位。这些算法采用将二维平面 的算法加上 Z 轴坐标直接拓展为三维空间算法，然而 由于三维空间相对于二维平面更加复杂，所以这样简 单的转化衍生的效果并不太理想。还有另外一种解决 三维定位问题的思路，是把三维问题转化为二维问题，然后利用二维定位算法将问题解决，最后再将结果转 化为三维结果。比如文献13中利用水下声音传感器 提出一种水下定位算法，就是把三维的水下环境转化 为二维来解决问题。另外还有的是提出了新型的三维定位算法，文献14 提出了一个

9、基于空间限定的三维定位算法 Constrain 3-D，基于传统的三角运算，测量并计算与邻接节点的距离来估计自身位置；文献15通过使用数学中向量和矩阵的理论，进行四面体的构造，然后通过四面体的质心估算未知节点的位置；文献16在其他三维定位算法的基础上，引入位置估算偏差值，然后使用加权质心算法进行位置估算。本文中，笔者对四面体的形状特征和体积进行分析，基于数学中的几何原理，引入体积比阈值并结合四面体质心算法进行位置估算，提出一个新的三维定位算法。论文的余下内容分为四部分，第 1 部分概述四面体质心算法的推导过程；第 2 部分介绍理论背景，并在第 3 部分我们提出的新算法并给出算法原理及步骤；第

10、4 部分与第 5 部分中我们将提出的算法进行详细的仿真并分析；最后在第 6 部分中，我们得出总结。2 12 12 13 23 24 34 316 3 2=4 3坐 标 为 (x, y, z) ， 令 A =设 未 知 节 点1122211134113434然后通过(1)我们推导未知节点 K(1, 2, 3, 4)，则34341= =2 3 4(2)= 1 (+ + + )1121314162= =3413 4(3)34= 1 (+ + + )1222324263= =41241 24(4)= 1 (+ + + )1323334364= =31 2 3(5)123= 1 (+ + + )1424

11、34446从式(2)至式(5)可以推得12112131411111122232423 =46= 6 (6)33344411四面体质心定位算法21 3 = (7)三维空间中，文献17利用数学中四面体坐标的 理论提出了一种四面体质心算法。以下简述具体过程：引理： 假设四面体 顶点 的坐标为 411112令1 = 222则，根据(7)可以转换( , , ),那么其体积可由如下行列式表示：34333444 (=1,2,3,4)V =4(1)23推出1234 = (8)3计 算机研究与 发 展11 =221其中 = x, y, z，h = 3 3， (14)21623 ( +

12、+ )( + )( + )( + )=044DCP = 0 , 111(15), = 222。333444用最小二乘法(LS),可以推得DCP 的值域为(0,1，其中当 DCP 的值趋近于 1时，四面体越趋近于正四面体；反之，当 DCP 的值趋近于 0 时，四面体四个顶点越接近共面。 = ( )1(9) 经过计算可以得出114111222141 = 3 3 = 14 3(10)2.2 区域位置限制文献17中介绍四面体质心算法，首先未知节点选取周边最近的四个信标节点并把它们组成四面体，然后将四面体的质心的坐标位置作为未知节点的坐标，从而实现三维空间的定位。但在这种四面体质心算法中，未知节点本身可

13、能在组成的四面体区域的外部，这种情况将会引起较大的节点定位误差，因此为了避免出现此类状况，我们通过设定一个阈值，来保证未知节点处于组成的四面体的区域内，具体如下。如图 1 所示，假设四面体1234 的体积为44414从(8)和(10)式我们可以计算未知节点的坐标1 = ( )1(11) 12理论背景在第三节介绍我们提出的基于共面性与区域限制的 WSN 定位算法之前，需要先介绍一些新算法中用的基本概念，分别是四面体的共面性判断和如何进行区域位置的限制。1234 ， M为四面体质心的估计节点， 则有M234、1M34、12M4、123M 四个小四面体，体积分别是234 、134 、124 、2.1

14、 四面体的共面性判断四面体的共面性(Degree of Coplanarity, DCP)可以用于判断四面体共面程度，文献18和19已经进行了对四面体的研究并且在定位里有所应用，其中文献18描述测量方法有“最小立体角(Minimum Solid Angle)”、“半径比(Radius Ratio)”和“平均比(Mean Ratio)”三种，而文献19将半径比应用于三维定位算法，这次我们也使用半径比来判断共面程度，并将其与质心算法相结合。判断的公式定义为： = 3/，其中代表四面体内切球的半径，代表四面体外接球的半径，为半径比，值域为(0,1。四面体内切球与外接球的半径公式为：123。为了判断点

15、 M 是否在四面体1234内部，我们引入一个体积比阈值 T： =234 + 134 + 124 + 123234(16)从纯理论上讲，当点 M 在四面体1234内部时，四面体1234的体积应当等于四个小四面体的体积之和，即 T=1，此时即可保证未知节点一定在四面体内部。但由于在实际中 M 的坐标为测量值，存在误差，所以 T 的范围则非常不确定。我们将最终确定一个 T 的阈值，以确保满足阈值条件的四面体均能保证未知节点在其区域内部。关于 T 值的选择将在第4 部分阈值选取中予以分析。3 =(12)3=0 =( + + )( + )( + )( + )(13)24其中 v 为四面体的体积，为四面体

16、四个面的面积，a、b、c 为分别为四面体的三条对边，接着将(12)和(13)结合：4计算机研究与发展开始NNDCP是否满足？Y区域位置是否在附近？图 1 四面体1234Y3基于共面性与区域限制的三维WSN 定位算法我们提出的基于共面性与区域限制的 WSN 定位算法是通过设定的阈值不断进行筛选，对符合条件的四面体运用四面体质心定位，再将各四面体质心定位的结果的平均值作为未知节点最后的位置坐标，具体步骤如下：第 1 步：信标节点在它的通信范围内广播自身的位置信息，未知节点收集到信标节点的信息，并收集和计算节点到节点之间的距离；第 2 步：每个未知节点对通信范围内的信标节点按照远近顺序进行编号，并将

17、在其通信半径内所有信标节点按照编号顺序每次选取四个点组成四面体；第 3 步：对上一步组成的四面体进行 DCP 阈值判断，如果满足条件则进入下一步，如果不满足条件则返回第二步按照顺序重新选择四面体；第 4 步：对第三部符合条件的四面体进行体积比 倍数阈值的判断，如果小于等于此阈值则继续下一步，如果不满足阈值条件则返回第二步按照顺序重新构 造四面体；第 5 步：对步骤 4 得到的四面体进行四面体质心定位算法，得到未知节点的测量坐标。通过一系列满足条件的四面体可以得到未知节点的一系列测量坐标，计算出这些测量坐标的平均值，并将其作为未知节点的最终坐标。之后再继续下一个未知点的定位。流程图如图 2 所示

18、。结束图 2 算法流程图4阈值分析上一节我们提出基于共面性和区域限制的 WSN定位算法，并且给出了算法步骤与流程图。其中，我们设定了两个阈值来作为对四面体的约束，然而如何选取合适的阈值，既让算法有更好的定位精度，又能保证算法的稳定性，成为算法的关键所在。对此，在这节中我们对阈值的取值进行详细的分析，实验采用的工具是 MATLAB。4.1 共面性阈值在共面性阈值(Degree of Coplanarity)的分析中，我们分别改变信标节点比率、通信半径和节点数目来观察不同参数条件下不同阈值对定位精度的影响。在这个环节中，我们并未加入体积比阈值。首先，我们先设定一组参数来讨论共面性阈值对定位精度的影

19、响，之后再通过改变实验参数获取不同参数下 DCP 阈值对定位精度的影响。其中，图 3 为实验结果，实验参数如表 1。图 4 表示的是在第一组参数实验的基础上，将信标节点比率改为 30%，其他参数不变的情况下，共面性阈值对定位的影响，实验参数如表 2。同理图 5 和取一系列未知点的平均值作为未知节点的最终坐标四面体质心求得估计未知点坐标每个未知节点规则地选取四面体组未知节点收集信息信标节点广播节点位置5计 算 机研究与 发 展图 6 分别表示了其他参数条件下共面性阈值对定位精度的影响，对应的参数表分别为表 3 和表 4。表 1 共面性阈值对定位误差的影响的实验参数（1）表 3 共面性阈值对定位误

20、差的影响的实验参数（3）实验参数参数值实验参数参数值100m 100m 100m100 个15%100m 100m 100m100 个15%空间区域空间区域节点数目节点数目信标节点比率信标节点比率通信半径50m0.10.9通信半径70m0.10.9DCP()DCP()图 3 不同参数下共面性阈值对定位误差的影响（1）图 5 不同参数下共面性阈值对定位误差的影响（3）表 2 共面性阈值对定位误差的影响的实验参数（2）表 4 共面性阈值对定位误差的影响的实验参数（4）实验参数参数值实验参数参数值100m 100m 100m100 个100m 100m 100m300 个空间区域空间区域节点数目节点

21、数目信标节点比率30%50m信标节点比率15%50m通信半径通信半径DCP()0.10.9DCP()0.10.9图 4 不同参数下共面性阈值对定位误差的影响（2）图 6 不同参数下共面性阈值对定位误差的影响（4）6计 算 机 研究 与 发 展表 6 体积比阈值 T 对定位误差的影响的实验参数（2）实验参数参数值从上述四组实验中我们可以看出，不同参数下，随着共面性阈值的不断增加，定位误差总有着下降的趋势，即不论参数如何变化，总是共面性阈值越大效果越好。但我们在实验中也发现当我们选取的阈值大于 0.9 时，算法的稳定性明显降低，因此我们选取 0.9作为我们算法的最终共面性阈值。空间区域100m 1

22、00m 100m200 个30%节点数目信标节点比率通信半径50m0.9DCP()体积比阈值 T0.754.2 体积比阈值 T在关于共面性阈值对定位误差影响的讨论中，我们最终选择设 0.9 作为我们算法的共面性阈值。在这个前提下，我们进行体积比阈值的讨论，同理我们设置不同的参数来对比不同情况下体积比阈值对定位误差的影响。首先设定一组参数讨论体积比阈值 T 对定位精度的影响，结果为图 7 所示，参数如表 5。图 8、图 9、图 10 分别表示了其他参数条件下定位误差率与体积比阈值的关系，对应的参数表分别为表 6、表 7 和表 8。图 8 不同参数下体积比阈值 T 对定位误差的影响（2）表 5 体

23、积比阈值 T 对定位误差的影响的实验参数（1）表 7 体积比阈值 T 对定位误差的影响的实验参数（3）实验参数参数值实验参数参数值100m 100m 100m200 个空间区域100m 100m 100m200 个15%70m空间区域节点数目节点数目信标节点比率15%信标节点比率通信半径50m0.9通信半径DCP()DCP()体积比阈值 T0.90.75体积比阈值 T0.75图 7 不同参数下体积比阈值 T 对定位误差的影响（1）图 9 不同参数下体积比阈值 T 对定位误差的影响（3）7计 算 机研究与发 展表 8 体积比阈值 T 对定位误差的影响的实验参数（4）表 9 改变信标节点比率的实验

24、参数实验参数参数值实验参数参数值空间区域100m 100m 100m400 个15%空间区域100m 100m 100m200 个10%25%节点数目节点数目信标节点比率信标节点比率通信半径50m0.9通信半径50m0.9DCP()DCP()体积比阈值 T0.75体积比阈值 T1图 10 不同参数下体积比阈值 T 对定位误差的影响（4）图 11 改变信标节点比率对定位误差产生的影响由上述四图可知，我们发现体积比阈值大于 1 时，定位误差上升较为快速，小于1 则误差变化不明显。同时这与我们之前分析的纯理论环境下的阈值非常接近，所以我们设1 为我们新算法的体积比阈值。即如果 T1，则说明 M 点在

25、此四面体区域内部或附近，不会偏离较远；否则则与估计位置偏离区域较大。接着我们测试不同通信半径对定位误差的影响， 实验参数设定如表 10。结果如图 12 所示，三角标注 的线为原始的三维 DV-hop 算法，圆圈标注的线为传 统的质心算法，星号标注的线为我们提出的新三维定 位算法。随着通信半径的不断增大，新型的 WSN 定 位算法依然优于传统的两种算法，而且在较小的通信 半径区域内这种优势较为明显。当通信半径增大到 85 以上时，质心算法的精度优于传统三维 DV-hop 算法，但是无论通信半径如何变化，我们的新算法总是最优的。5实验结果与仿真分析接下来我们对提出的算法进行仿真实验，我们将通过改变

26、不同参数，从不同角度分析比较我们的新算法与传统三维 DV-hop 算法及经典质心算法的区别。在以下的所有仿真实验中，我们每个实验都执行 100次然后取 100 个数据的平均值作为实验结果。图 11 表示我们通过改变信标节点的比率来对比在不同信标节点比例的情况下三个算法的性能。三角标注的线为原始的三维 DV-hop 算法，圆圈标注的线为传统的质心算法，星号标注的线为我们提出的新三维定位算法。同传统的三维 DV-hop 算法和质心算法进行对比，实验参数如表 9。无论信标节点比例如何变化，新三维 WSN 定位算法精度总是比其他两个算法高，而且对比原始 DV-hop 算法效果更为明显。表 10 改变通

27、信半径的实验参数实验参数参数值100m 100m 100m200 个20%空间区域节点数目信标节点比率通信半径30m100m0.9DCP()体积比阈值 T18计 算 机研究 与 发 展综上所述，通过与传统的三维 DV-hop 算法和质心算法的比较，我们得出基于共面性与区域限制的三维定位算法在定位准确度方面有着较为明显的提高，而且有更好的稳定性。6 结束语我们提出了一种新的基于共面性与区域限制的 WSN 三维定位算法，并对该算法进行大量的仿真实 验。结果表明，相比于两种传统的三维定位算法，新 算法能有效地降低节点定位误差，并且提高定位的稳 定性。另外该算法是在三维环境中布置的，相比较二 维平面的

28、定位算法而言，更具有实际性质。另一方面，本算法虽然定位误差降低，但算法复杂性也有所增加，未来我们将继续对三维定位算法进行改进与优化以获得定位精度与算法复杂度的平衡。图 12 改变通信半径对定位误差的影响最后我们测试改变总节点数目对定位的影响，实验参数设定如表 11。结果如图 13 显示，三角标注的线为原始的三维 DV-hop 算法，圆圈标注的线为传统的质心算法，星号标注的线为我们提出的新三维定位算法。其中，传统的质心算法在改变节点数目中优于原始的三维 DV-hop 算法，而我们所提出的三维质心算法优于传统的质心算法，与原始的三维 DV-hop 相比则效果更为明显。参 考 文 献1Akyildi

29、z, I. F., Su, W., Sankarasubramaniam, Y, & Cayirci, E. (2002).Wireless sensor networks: a survey. Computer networks, 38(4), 393-422. MAO, Guoqiang; FIDAN, Bar; ANDERSON, Brian DO. Wirelesssensor network localization techniques. Computer networks, 2007, 51.10:2表 11 改变节点数目的实验参数2529-2553.Zhang J, Yang

30、R, Li J. An Enhanced DV-Hop Localization Algorithm3实验参数参数值using RSSI. 2013.T.S.Rappapport, Wireless Communications: Principles and Practice. Prentice Hall: New Jersey, pp.50-143 1996.100m 100m 100m200600 个空间区域4节点数目信标节点比率15%40m5X. Cheng, T. A, G. Xue, D. Chen, “TPS: a time-based positioning scheme通信半

31、径for outdoor wireless sensor networks,” IEEE2004, HongDCP()体积比阈值 T0.91Kong, China. pp. 2685-2696, March, 2004.T. D. J. “Statistical theory of passive location systems,” IEEE Trans. on AES. vol.20, no.2, pp. 183-198, Mar.1984.67Niculescu D, Nath B. Ad-hoc positioning system (APS). Proc. of theIEEE, S

32、an Antonio, 2001:2926-2931.8Niculescu D, Nath B. DV Based Positioning in Ad hoc Networks. Journalofmunication Systems, 2003, 22(1-4):267-2809Bulusu N, Heidemann J, Estrin D. GPS-less low cost outdoor localizationfor very small devices. IEEE Personal Communicaitons Magzine, 2000,7(5):28-3410 He T, Hu

33、ang C D, Blum B M, Stankovic J A, Abdelzaher T. Range-freeLocalization Schemes for Large Scale Sensor Netowrks. In: Poc. of 9th Annual International conference on Mobile Computing and Networking .San Diego USA: ACM, 2003.81-9511 XU, Lisheng, et al. A study on 2D and 3D weighted centroid localization

34、图 13 改变节点数目对定位误差的影响9计 算 机 研究与发展algorithm in Wireless Sensor Networks. In: Advanced Computer Control(ICACC), 2011 3rd International Conference on. IEEE, 2011. p. 155-159.12 陈庆章, et al. 基于共面度和分层结构的 WSN 三维定位算法. 电子测量与仪器学报, 2012, 26.8: 673-680.13 Cheng, W., Teymorian, A. Y., Ma, L., Cheng, X., Lu, X., & Lu, Z. (2008,April). Underwater localizat