基于相交环的水下无线传感器网络节点自定位研究*

单志龙，胡 燕

(华南师范大学计算机学院，广州 510631)

水下无线传感器网络UWSN(Underwater Wireless Sensor Network)可用于海洋学数据收集、污染监测、近海探测、灾难防御以及协助海军进行战术跟踪等领域。与其他水下探测工具相比，UWSN节点成本低，体积小，适合大范围部署和长时间监测，因此越来越受到国内外众多研究机构和企业的关注［1］。

水下无线传感器网络与地面无线传感器网络TWSNs(Terrestrial Wireless Sensor Networks)存在一些相同的特征，如大量的节点和有限的能量等［2］。同时，UWSNs又有自己独特的方面。首先，由于水的盐碱度对无线电信号传输产生干扰，无线电通信的方式在水下不能很好地工作，之后有人提出声波通信，但声波信道通常有较大的传播迟延、低带宽和多径效应严重［3］。其次，水下传感器节点可能会受到水流或其他因素影响从而产生位置移动。因此，原本适用于TWSN中的定位协议并不能很好地应用于UWSN。

现有的UWSN定位技术主要有GPS智能浮标［4－5］、USP［6］、SLMP［7］、水下 APS 定位系统［8］、AHLoS-3C(Ad Hoc Localization System)［9－10］定位系统等几种方案。文献［11］利用节点自组织过程中用到的数据传输算法，也提出了一种分布式的水下节点自定位算法。在这些方案中，有的是依赖于节点的密度，有的依赖于GPS或特殊节点等，相应就存在了传感器节点定位代价大和精度低等问题。

本文针对UWSN中传统定位协议的定位效率受限于节点密度的问题，提出了一种适用于节点稀疏(未知节点邻居节点数小于3)网络下的基于相交环的两跳定位算法IR2H(Intersect Rings 2-Hops location scheme)，并通过实验仿真验证了算法的性能。

1 AHLoS-3C水下定位算法

经典的三圆相交定位(AHLoS-3C)算法［12］思想是在对未知节点进行定位时，利用速度和已知节点与未知节点数据包传输时间分别求得节点间距离。如图1所示，若未知节点D收到三个已知节点A1、A2和A3发出的定位信息数据包，则D的坐标可以通过三边定位法求得。当D求得自身坐标后，成为已知节点并将自身坐标信息广播出去，其它未知节点若能收到至少三个已知节点的定位信息，则可以使用同样的方法计算自身坐标，全网通过递归方式实现对未知节点的自定位。

利用AHLoS-3C定位算法进行水下节点的定位过程较简单且易于实现，定位算法收敛速度较快，适用于移动节点网络，但在锚节点稀疏情况下，即未知节点周边没有三个以上的锚节点时，未知节点则无法获得定位信息。

图1 AHLoS-3C定位算法

2 基于相交环的两跳定位算法

IR2H算法针对网络中锚节点极其稀疏，未知节点无法得到足够锚节点位置信息来实现定位的情况下，借助其他未知节点来转发信息，从而增加未知节点获得的定位信息量，使得未知节点有可能依靠两跳的信息来完成定位。

2.1 单环的定义和同心环裁剪

图2 单圆环

如图2所示，节点A为锚节点，B和C均为未知节点，且C在A的通信半径之外。假设水声速度为v0。A发出的定位信息经B转发到达C，则C可获得信息＜xA，yA，dAB，tB＞，其中xA和yA是A的坐标，dAB表示A与B的距离，tB表示B发出该数据包的时刻，则节点C在tC时刻接收到数据包时，节点B和C之间的距离dBC=v0·(tC－tB)。由于B可能出现在以A为圆心、dAB为半径的圆周上的任意一点，C可能出现在以B为圆心、dBC为半径的圆周上的任意一点，因此C可能出现在图2单圆环阴影部分中的任一位置上，其位置可由式(1)表示:

若节点C同时收到节点B和D的两个信息:＜xA，yA，dAB，tB＞和＜xA，yA，dAD，tD＞，如图 3，则节点C经过同心环裁剪后，必处于两环相交阴影区域内，其位置可由式(2)表示:

图3 同心环裁剪

显然，节点C的中继节点越多，则环的厚度有可能越薄，这样有利于缩小节点C的位置区域。设节点C收到节点A经不同中继节点转发的两跳定位信息集为IAC，则有＜xA，yA，dAi，ti＞∈IAC，其中i为任一中继节点。取rA=max{dAi}，RA=min{dAi+diC}，则节点C处在以A为圆心的环形区域内:

2.2 相交环和节点定位

如图4所示，若节点C收到两个一跳距离锚节点A4和A3的定位信息，则其位置可能是C1或C2。若节点C此时又收到来自两跳距离的锚节点A1、A2的定位信息，则利用同心环裁剪的方法可获得节点C必处于两环相交区域内，且C1点即为C的位置。

图4 两锚节点多环定位

若节点C只收到来自一跳距离的锚节点A3的定位信息，且收到两跳距离锚节点A1和A2的定位信息，如图5所示，C必处于弧P1P2的某处，取弧P1P2的中点作为C的位置，此时定位精度为|P1P2|/2。

图5 单锚节点两环定位

如图6所示，若节点C一跳范围内不存在任何锚节点，只能通过式(4)多环相交确定其大致的区域，然后未知节点的坐标由区域的质心获得。

图6 多环相交定位

2.3 IR2H算法流程图

IR2H定位算法有效地解决了稀疏锚节点情况下AHLoS-3C的有效定位率低或者完全无法定位的问题，提高了定位率，其算法流程如图7所示。

图7 IR2H算法流程图

3 仿真分析

3.1 水声模块介绍

本文采用NS2水声协议模块模拟水下环境，对IR2H算法和AHLoS-3C算法进行了仿真分析。该模块可分为4个部分:水声传输模型、水声信道模型、物理层模型和调制解调模型。水声传输过程因受环境影响产生的总衰减A(d，f)等于扩展损耗与吸收损耗之和［12］:

其中d为传输距离，a为吸收系数，k为衰减系数，一般取1到2，a(f)［13］是根据 Thorp近似计算得到的吸收损耗，单位为dB/km:

水下环境噪声N(f)主要包括湍流噪声、航船噪声、风成噪声和热噪声［14］，接收节点处的信噪比为:

其中Pt为发送功率，则接收功率为:

一般情况下水声速度假设为恒定值v0=1 500 m/s，若考虑声波水下传输过程受深度、温度和盐度等环境因素的影响，水声速度可以近似计算为［12］:

其中t为水体温度，z为水深，S为水的盐度。

水声传输模型使用式(5)计算传输过程总衰减，用式(7)计算接收节点处的信噪比SNR，在此基础上用式(8)计算接收信号强度。水声信道模型调用传输模型进行冲突检测和传输错误发现，并计算有效带宽。物理层调用传输模型和信道模型，并利用式(9)计算传输时间和总延迟，并调用调制解调模型计算误码率［15］。

如图8所示，红色十字标记表示节点实际位置，蓝色实心圆标记表示锚节点。绿色标记表示节点通过定位算法计算获得的位置，黑色线条表示节点实际位置与计算位置之间的偏差。节点的布置是随机分布在大小为10 000 m×10 000 m场景区域中，总节点数为300，锚点数为4，节点通信半径为1 650 m。

由于锚节点之间间距的远近直接影响到未知节点是否可以被准确定位，所以在进行仿真时，我们将通过对锚节点间距远近情况的讨论来分析两种算法的性能。

3.2 锚节点间距较远

如图8所示，当采用AHLoS-3C单跳定位算法时，因为锚节点之间距离大于节点的通信直径，未知节点不能从至少3个相距较远的锚节点获取距离信息，因此将会出现未知节点无法定位的情况。而用IR2H算法对节点进行定位时，如图9所示，由于使用了两跳相交环辅助定位技术，因此可以有效解决在锚节点间距离大于节点的通信直径情况下的定位问题，从而提高锚节点部署稀疏且相距较远情况下的定位率。

图8 节点分布场景及AHLoS-3C算法(锚节点远)

图9 IR2H定位算法(锚节点距离远)

3.3 锚节点间距较近

图10和图11展示了锚节点间距离较近情况下，在用两种定位算法进行一次定位估计时的直观定位效果。图10采用AHLoS-3C算法，被定位节点数274，其中被错误定位节点数为13，所有被错误定位节点的平均定位误差为101.18 m。图11采用IR2H算法，被定位节点数283，其中被错误定位节点数为6，所有被错误定位节点的平均定位误差为43.44 m。从两个图中可以看出，在节点覆盖区域的边缘，使用AHLoS-3C算法时，有不少节点的真实位置和实际位置之间存在较大差异，而使用IR2H算法时，这种差异下降比较明显。为了更好地比较两个算法，在仿真时，对仿真数据取50次运算后的均值来比较有效定位率、平均定位误差和定位耗时上的差异。

图10 AHLoS-3C算法(锚节点距离近)

图11 IR2H算法(锚节点距离近)

(1)有效定位率［16］

有效定位率指的是全网已被正确定位节点数占总节点数的百分比。随着节点总数的增加，两种定位算法的有效定位率均有所提高，IR2H的有效定位率最终稳定在80%左右，而AHLoS-3C的有效定位率稳定为75%，如图12所示，可见IR2H比AHLoS-3C在大范围定位过程中能保持较高的有效定位率。

(2)平均定位误差

平均定位误差指的是已定位节点的位置与实际位置的平均误差。从图13可知，总体上两种定位算法的定位误差随着节点数量的增加逐渐减少，但由于节点位置坐标是随机生成的，因此有可能增加定位算法的不稳定性，即少部分节点可能产生较大的定位误差，图像的波动情况也正说明了这个现象。IR2H采用两跳定位方法，有助于抑制定位误差的积累和传递，因此总体定位误差优于AHLoS-3C。

图12 有效定位

图13 平均定位误差

(3)定位耗时

定位耗时指的是完成一次全网定位所用时间。由图14可知，两种算法的完成一次全网定位所需时间比较相近，随着节点数的增加，两种算法的耗时都明显有增大趋势，且IR2H相对耗时稍大一点。一方面是由于随着节点数的增加，争用信道造成某些节点处于等待状态增加耗时，另一方面是因为节点密度增加，增加了定位率，从而加大了计算量，造成总耗时增大。

图14 定位耗时

4 结论

为了降低网络定位代价，减少水下网络节点定位对锚节点数的依赖性，本文提出了一种能够在锚节点数稀疏的情况下实现节点自定位的新算法IR2H，该算法利用同心环的裁剪来缩小未知节点的定位区域，并通过两跳来定位节点。仿真实验表明，较AHLoS-3C算法，IR2H算法能够提高了定位精度、降低了网络代价和提高了节点定位率。在此过程中，相应地付出了时延增多的代价。

［1］王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，16(5):857－868.

［2］John Heidemann，Wei Ye，Jack Wills，et al.Research Challenges and Applications for Underwater Sensor Networking［C］//Proc.of the IEEE Wireless Communications and Networking(WCNC)，Las Vegas，2006:228－235.

［3］刘玉梁，潘仲明.水下无线传感器网络能量路由协议的仿真研究［J］.传感技术学报，2011，24(6):905－908.

［4］SavvidesA，Han CC，Srivastava Mb.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［C］//ACM MOBICOM，2001:166－179.

［5］杜晓旭，宋保维，胡海豹，等.AUV拖曳GPS浮标系统仿真研究［J］.西北工业大学学报，2008，26(1):88－92.

［6］Xie P，Lao L，Cui J H.VBF:Vector-Based Forwarding Protocol for Underwater Sensor Networks［J］.Lecture Notes in Computer Science，2006，3976:1216－1221.

［7］Zhou Z，Jun-Hong C，Amvrossios B.Scalable Localization with Mobility Prediction for Underwater Sensor Networks［C］//IEEE Infocom，2008:2198－2206.

［8］Dragos，Niculescu，Badri Nath.Ad Hoc Positioning System(APS)Using AOA［C］//IEEE Infocom，2003:1734－1743.

［9］Cheng X，Thaeler A，Xue G，et al.TPS:A Time-Based Positioning Scheme for Outdoor Wireless Sensor Networks［C］//IEEE Infocom，2004:2685－2696.

［10］Savvides A，Han C C，Srivastava M B.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［C］//ACM Mobicom，2001:16－21.

［11］梁玥，刘忠，夏清涛.水下声学传感器网络节点定位算法及自组织过程研究［J］.传感技术学报，2011，24(3):402－406.

［12］Urick R.PrinciplesofUnderwaterSound［M］.McGraw-Hill，1983.

［13］Berkhovskikh L，Lysanov Y.Fundamentals of Ocean Acoustics［M］.New York:Springer，3rd Edition，2002.

［14］Coates R.Underwater Acoustic Systems［M］.Wiley，1989.

［15］Harris A F，Zorzi M.Modeling the Underwater Acoustic Channel in Ns2［C］//Proc.of the 2nd International Conference on Performance Evaluation Methodologies and Tools(NSTools’07)，Nantes，France，2007.

［16］Zhong Zhou，Jun-Hong Cui，Amvrossios Bagtzoglou.Scalable Localization with Mobility Prediction for Underwater Sensor Networks［C］//IEEE Infocom，2008:2198－2206.