2018, Vol. 50引用本文 |
2. 中国海洋大学 信息科学与工程学院，山东 青岛 266100
2. College of Info. Sci. and Eng., Ocean Univ. of China, Qingdao 266100, China
定位是水下传感器网络的重要问题，海洋科学研究、目标监测、资源勘测等各类数据必须和位置信息相结合才有意义，位置信息的准确程度决定了感知数据的应用价值[1]。水下传感器网络依赖水声进行通信，水声信道传播延迟长，延迟方差大，传播损失大，可用的频段非常有限，多途现象严重，多普勒频散严重，环境噪声强，信号的信噪比低，误码率高[2]，陆地传感器网络的研究成果不能应用于水下。
目前，针对水下传感器网络定位的研究较多[3]，现有的水下传感器网络定位算法主要可以分为基于测距的定位算法和无需测距的定位算法[4]。
基于测距的定位算法需要先测量节点间的距离，再进行定位计算[5]。下潜和上升（Dive ’N’ Rise，DNR）算法提出的较早，信标节点在水中起伏并发送位置变化信息，待定位节点监听信标节点发送的信息来计算位置，但是，DNR信标需要浮出水面接收GPS坐标，较低了定位的灵活性，并且预先假设节点时间同步，通信成本相应增加[6]。被动定位算法中，Silent Positioning需要4个大功率的锚节点辅助定位，节点无需时间同步，但是，锚节点功率较大，需要额外的设备，加大了节点定位的成本[7]。基于自主水下航行器 （autonomous underwater vehicle，AUV）的定位算法利用自控水下航行器周期性地发送位置信息进行定位，但是，其通信具有一定延迟，节点定位精度降低[8–9]。无锚定位算法（anchor-free localization algorithm，AFLA）是一种无锚节点水下传感器网络定位算法，在没有锚节点的情况下，通过节点间的几何关系推算节点的相对位置，但由于信标节点和水下节点通信频繁，导致能耗增加[10]。基于到达角度测距（angle of arrival，AOA）的定位算法通过计算信号到达角度测算多跳节点间的距离定位，但是，未考虑水下节点移动性，在动态环境中，节点误差将会变大[11]。基于到达时间测距(time of arrival，TOA)的定位算法利用信号到达时间推算节点间的距离，再通过三边定位技术得到节点的位置，忽略了水下环境信号衰减的特性，节点定位误差将会变大[12]。基于到达时间差（time difference of arrive，TDOA）的大规模传感器网络定位（large scale localization in sensor networks，LSLS）算法将3维模型投射到2维，再利用节点间的距离定位，但是由于辅助节点选择的不同，带来的节点定位误差也会不同[13]。递归基础算法（recursive basic algorithm，RBA）根据协方差律定义了参考节点的置信值，利用节点间的距离采用递归算法预测节点的位置，但如果选用的辅助定位节点位置误差较大，利用递归的方法将会对节点定位误差造成较大影响[14]。三边定位（trilateration localization，TL）算法是典型的定位方法，利用至少3个不共线的辅助节点通过TOA获得节点之间距离进行位置的计算，定位过程简单，可以作用于多种水下环境，但由于其定位过程受到自身算法影响以及忽视了多种外界因素，会加大节点位置误差[15]。
无需测距的定位算法不需要计算节点之间的距离，但是，精度较低，需要更多的能量消耗与通信开销。区域定位策略（area localization scheme，ALS）调节锚节点不同的发射功率，将大的区域分割成许多小区域从而实现节点的区域定位，但是，定位精度并没有精确到节点本身，带来的定位误差也会受到相应影响[16]。多跳拟和定位算法（multihops fitting localization algorithm，MFLA）利用信标节点和待定位节点之间的中间节点作为路由节点，将多跳路径与角度信息相结合近似为节点间的直线路径再利用三边定位，但由于参与定位的辅助节点较多，能耗将会增加[17]。海上传感器网络垂直相交（perpendicular intersection，PI）定位算法利用一个移动的信标节点定位，无需计算节点间的距离，而是通过传输能量衰减与距离的关系推算节点间的几何关系得到节点位置,但是，该算法并没有考虑水下节点在动态环境中具有移动性的这种情况，将会大大降低节点的定位精度[18–19]。移动多功率范围定位（mobile multipower range localization，MMRL）算法利用几何学原理，通过一个移动的锚节点寻找包含待定位节点的最大矩形区域实现定位[20]。
上述水下传感器网络定位算法都没有考虑水下节点浮动受限的特点，它们采用各种方法直接计算水下节点的位置，而忽略了锚的位置在定位中的重要作用。
针对使用锚固定在水底的浮动受限节点，文献[21]提出了受限浮动传感器（restricted floating sensors，RFS）模型 ，并通过节点的移动范围推算海水深度，但是，节点的移动性和基于接收信号强度指示（received signal strength indicator，RSSI）信号测距的误差对其推测的海水深度带来一定的影响。水下传感器网络受限移动定位（localization for active restricted，LAR）算法分析了水下节点的受力情况，根据水下传感器节点活动范围判断节点的运动状态和位置关系[22]。针对DR-OSNs （drifting restricted floating ocean sensor networks）的传感器网络漂浮受限定位（localization for drifting-restricted sensor networks，LDSN）算法通过自停泊节点定位、水下节点定位和漂浮节点定位3个步骤来计算节点的位置，但是，辅助节点采用双头设计，使整个定位通信的能耗增加[23]。专门针对浮动受限节点的研究成果不多，现有的算法都是通过各种方式判读节点的移动范围或移动规律得到节点的位置。
作者根据水下节点的移动规律设计了受限浮动水下传感器网络定位算法（restricted floating localization，RFL）。该算法结合水下节点的受限移动规律以及移动信标的位置信息，通过理论分析推导锚的位置，从而确定节点的移动范围和部署区间，进一步利用锚和移动信标的位置信息计算节点位置。RFL算法不同于现有的受限移动节点定位算法，并不直接计算受限移动节点的当前位置，而是先计算固定节点的锚的位置，再利用锚的位置信息辅助计算节点的当前位置，定位精度高、代价小，是一种简单实用的定位方式。
1 网络模型及定位算法设计了受限浮动水下传感器网络定位算法（RFL）。该算法步骤为：1）根据水下节点在缆绳拉力等力的作用下的活动规律，建立受限浮动节点模型；2）移动信标辅助定位，该移动信标在部署区域内沿直线移动，每过一段时间变换一次方向并广播位置信息，利用移动信标的位置信息结合水下节点的受限移动规律，由理论分析推导锚的位置，并通过多次计算取中值以降低锚位置的求解误差；3）利用锚和移动信标的位置信息，计算出水下节点的位置。
1.1 模型设计为了避免水下节点随水流离开部署区域，需要通过缆绳把节点与锚相连，锚沉入水底后不再移动。节点在重力、浮力、水流冲力、缆绳拉力作用下活动，缆绳总处于拉紧状态，节点的浮动范围是以锚
 |
| 图1 受限浮动节点模型 Fig. 1 Restricted floating node model |
1.2 受限浮动定位算法设计
水下节点的位置随水流而不断的变化，但是锚的位置部署之后不再改变。计算出锚的位置就可以掌握节点的移动范围，也可用于节点实时位置的计算。
采用一个移动信标辅助定位，该移动信标可以是水下自主航行器，也可以是其他水下设备，还可以知道自身的位置。由于移动信标可以浮上水面充电或更换电池，其能量不受限制，在定位过程中不必考虑其能耗。移动信标在部署区域内沿直线移动，每过一段时间变换一次方向，每次变换方向后广播一次位置信息。如图2所示，移动信标在位置S1发送的位置信息被待定位节点在位置A收到，节点收到信息后立刻返回定位信息，移动信标在位置S2收到该消息。水下节点具有移动性，但是，节点收到信息后立刻返回定位信息，所需时间极短，在这么短的时间内，可以忽略节点的移动。
 |
| 图2 信息交换过程 Fig. 2 Information exchange process |
水下节点可以通过测距算法得到其与移动信标之间的距离，根据距离公式可得：
| $\left\{{\begin{aligned}& {({x_{\rm{A}}} - {x_{{\rm{S1}}}})^2} + {({y_{\rm{A}}} - {y_{{\rm{S1}}}})^2} + {({{\textit{z}}_{\rm{A}}} - {{\textit{z}}_{{\rm{S1}}}})^2} = {d_{{\rm{AS1}}}^2},\\& {({x_{\rm{A}}} - {x_{{\rm{S2}}}})^2} + {({y_{\rm{A}}} - {y_{{\rm{S2}}}})^2} +{({{\textit{z}}_{\rm{A}}} - {{\textit{z}}_{{\rm{S2}}}})^2} = {d^2_{{\rm{AS2}}}}\end{aligned}} \right.$ | (1) |
式中，
 |
| 图3 移动信标辅助节点定位 Fig. 3 Mobile beacon assist node localization |
接下来，如图3所示，信标改变移动方向，再次广播位置信息。移动信标在位置S3发送的位置信息被待定位节点在位置B收到，节点收到信息后立刻返回定位信息，移动信标在位置S4收到该消息。同理，可以得到两个节点的位置（B和B1）。
由于节点收到两次信标广播的时间间隔很短，节点移动速度又有限，因此，节点位置A和B之间的差值不应大于上限
比较
| $\begin{aligned}[b]& \{ ({d_{{\rm{AB}}}} < {D_{\max }}) \cap ({d_{{\rm{A1B}}}} > {D_{\max }}) \cap \\& \;\;\;\;\;\;({d_{{\rm{AB1}}}} > {D_{\max }}) \cap ({d_{{\rm{A1B1}}}} > {D_{\max }})\} \end{aligned}$ | (2) |
通过式（2）可确定节点的位置为A和B，舍去其他无效位置。若得到的位置信息无法满足式（2），则在移动信标变换方向后，再次求取节点位置，用于判断，直到符合式（2）为止。
重复上述过程，直到得到4个节点的位置，如图4所示。
 |
| 图4 锚的位置计算 Fig. 4 Anchor position calculation |
图4中，节点A、B、C、D的坐标分别为
| $\left\{ {\begin{aligned}& {{{({x_{\rm{A}}} - {x_{\rm{O}}})}^2} + {{({y_{\rm{A}}} - {y_{\rm{O}}})}^2} + {{({{\textit{z}}_{\rm{A}}} - {{\textit{z}}_{\rm{O}}})}^2} = {L^2},}\\& {{{({x_{\rm{B}}} - {x_{\rm{O}}})}^2} + {{({y_{\rm{B}}} - {y_{\rm{O}}})}^2} + {{({{\textit{z}}_{\rm{B}}} - {{\textit{z}}_{\rm{O}}})}^2} = {L^2},}\\& {{{({x_{\rm{C}}} - {x_{\rm{O}}})}^2} + {{({y_{\rm{C}}} - {y_{\rm{O}}})}^2} + {{({{\textit{z}}_{\rm{C}}} - {{\textit{z}}_{\rm{O}}})}^2} = {L^2},}\\& {{{({x_{\rm{D}}} - {x_{\rm{O}}})}^2} + {{({y_{\rm{D}}} - {y_{\rm{O}}})}^2} + {{({{\textit{z}}_{\rm{D}}} - {{\textit{z}}_{\rm{O}}})}^2} = {L^2}}\end{aligned}}\right.$ | (3) |
求解方程组（3），将会得到锚的坐标O
如图5所示，移动信标在位置S1发送的位置信息被待定位节点在位置A收到，节点收到信息后立刻返回定位信息，移动信标在位置S2收到该消息，根据节点间的距离公式可得：
| $\left\{ {\begin{aligned}& {{{({x_{\rm{A}}} - {x_{{\rm{S1}}}})}^2} + {{({y_{\rm{A}}} - {y_{{\rm{S1}}}})}^2} + {{({{\textit{z}}_{\rm{A}}} - {{\textit{z}}_{{\rm{S1}}}})}^2} = d_{{\rm{AS1}}}^{\rm{2}},}\\& {{{({x_{\rm{A}}} - {x_{{\rm{S2}}}})}^2} + {{({y_{\rm{A}}} - {y_{{\rm{S2}}}})}^2} + {{({{\textit{z}}_{\rm{A}}} - {{\textit{z}}_{{\rm{S2}}}})}^2} = d_{{\rm{AS2}}}^{\rm{2}},}\\& {{{({x_{\rm{A}}} - {x_{\rm{O}}})}^2} + {{({y_{\rm{A}}} - {y_{\rm{O}}})}^2} + {{({{\textit{z}}_{\rm{A}}} - {{\textit{z}}_{\rm{O}}})}^2} = {L^2}}\end{aligned}} \right.$ | (4) |
式中，
 |
| 图5 锚的位置辅助节点定位 Fig. 5 Anchor position assist node localization |
由于锚固定在水底不动，其位置不会改变，在定位过程中，仅第1次定位时要计算锚的位置，此后可以直接使用锚的位置。为了避免锚的位置计算误差过大，在求解锚的位置时，计算多次，取其中值为锚的位置。根据锚的位置信息就可以确定节点的浮动范围和部署区间，在锚的位置信息辅助下，节点与移动信标进行一次双向信息交换就可以实现定位，极大地减少了通信次数，节省了计算量，消除了节点移动对定位精度的影响。
算法的定位误差主要来源于节点与信标测距的误差、定位计算误差。定位计算误差主要与硬件设备的运算能力和程序的舍入精度有关，其影响较小且可控。节点与信标测距的误差受到多种因素影响，例如，海水的深度、温度、盐度、水声传播速度、传播延迟、节点间的时间同步精度等等，其与具体海洋环境相关，较为复杂。为了简化计算过程，作者忽略了深度、温度、盐度、声速等变化的影响，将传播延迟作为测距误差的主要来源。
2 仿真结果通过仿真分析算法的性能，假设在200 m
仿真内容分为3部分：1）锚的定位精度，锚的定位误差对于节点的定位精度的影响，以及求得的节点位置与实际位置的比较；2）RFL算法与TL算法、MFLA算法、LSLS算法求得的节点定位误差的比较；3）大规模部署的水下传感器网络中，RFL算法和TL算法的节点定位误差比较。
首先，分析RFL算法所得锚的定位精度，如图6所示，其中，锚的实际位置用圆圈（○）表示，RFL算法得到的锚的位置用星号（*）表示，由图6可以看出，RFL算法较准确地计算出锚的位置，锚定位的平均位置误差为2.19 m。
 |
| 图6 锚的位置比较 Fig. 6 Anchor position comparison |
为了评估锚的位置误差对节点定位精度的影响，利用RFL算法进行了两者关系的比较。图7分析了锚定位误差与节点定位误差的关系。仿真计算得到锚的平均定位误差为2.81 m，节点的平均定位误差为1.64 m。从图7可以看出，锚的定位误差与节点的定位误差没有明显的比例关系，这是由于节点的定位误差受到信标位置、测距精度等多种因素影响，具有很大的随机性。但是，随着锚的定位误差的增加，节点的定位误差也有所增加，这表明当锚节点的误差过大时就会直接影响节点定位精度。因此，在求解锚的位置时，计算多次，取中值作为锚的位置，避免锚的位置计算误差过大。
 |
| 图7 锚与节点定位误差 Fig. 7 Anchor and node localization error |
利用计算得到的锚的位置信息和信标的位置信息计算节点的位置。如图8所示，圆圈（○）代表节点的实际位置，星号（*）代表用RFL算法得到的节点位置，其中，节点定位的平均误差为1.81 m。通过比较可以看出，RFL算法对锚的定位误差大于对节点的定位误差，这是由于锚的位置是通过4个已定位节点的位置间接推算得到，已定位节点的位置计算和锚的位置计算都会带来误差；而节点定位直接利用了信标的位置信息和锚的位置信息，只需要一次计算，因此节点定位精度高于锚的定位精度。
 |
| 图8 节点的位置比较 Fig. 8 Node position comparison |
然后，将RFL算法与TL、MFLA[17]和LSLS算法[13]进行比较。其中，TL算法是经典定位算法之一，应用非常广泛，其与本文算法一样不需要额外的硬件设备辅助，也不需要对节点特殊部署；MFLA算法利用信标和待定位节点之间的中间节点作为路由节点，将多跳路径与角度信息相结合近似为节点间的直线路径，再利用三边定位；基于TDoA的LSLS定位算法将3维模型投射到2维，利用节点间的距离定位。这3种方法和本文算法一样都是基于多边计算的定位方法。
如图9所示，TL、MFLA和LSLS算法的定位误差远大于RFL算法。这是由于水下节点随水流移动，节点在与信标通信的同时，其位置也在不断的变化。TL算法所采用的信标位置信息对应的并不是待定位节点的同一个位置，导致了较大的定位误差；MFLA算法采用节点之间夹角的角度变化幅度，具有差异性，在动态环境中定位误差较大；LSLS算法定位时选择的信标与水下节点位置距离的变化，导致定位通信时间不同，算法时间运算部分的误差加大，增加了定位误差；RFL算法在推导锚位置时通过中值运算缩小了误差范围，在求节点位置的时候利用锚的位置信息消除了节点移动的影响，提高了算法的定位精度。
 |
| 图9 节点定位误差比较 Fig. 9 Comparison of node localization error |
表1列出了采用RFL、TL、MFLA、LSLS算法的平均定位误差、最大定位误差和最小定位误差对比。
由表1可知：RFL算法的平均定位误差为1.81 m，仅是TL算法的49.6%，MFLA算法的44.8%，LSLS算法的32.1%。TL算法的最大定位误差是最大的，这是由于其测距估算的误差最不稳定。RFL算法的最大误差与最小误差都小于TL、MFLA和LSLS算法，具有较好的稳定性。
| 表1 定位误差比较 Tab. 1 Comparison of localization error |
 |
为了进一步研究算法的性能，将部署的节点增加到250个，每5个节点为一个簇，共50个簇，由簇首节点收集本簇内节点的平均定位误差。该仿真环境下，RFL、TL算法的平均定位误差对比，如图10所示，RFL算法的平均定位误差为1.79 m，TL算法的平均定位误差为3.13 m，RFL算法的平均定位误差是TL算法的57.19%。可见，在大规模部署的水下传感器网络中，RFL算法的定位精度也明显高于TL算法。
 |
| 图10 簇定位误差比较 Fig. 10 Comparison of cluster localization error |
通过上述仿真分析可以看出，RFL算法利用移动信标位置信息和节点移动规律计算出锚的位置用于水下节点定位，消减了节点浮动对定位精度的影响，减少了定位算法对信标数量的依赖，其定位精度好于现有的定位算法，使用方便，实用性强。
3 结 论基于水下节点的受限浮动规律，结合移动信标的位置信息，作者提出了受限浮动水下传感器网络定位算法（RFL）。该算法可以推导得到锚的位置，根据锚的位置就可以确定节点的移动范围和部署区间，再用锚的位置信息辅助节点定位。仿真实验表明，RFL算法通信量少、能耗低、定位效果好。今后的工作中，将研究不同水下环境的节点移动规律，进一步降低算法的节点定位误差；并在提高定位精度的同时，考虑算法的能耗情况。
| [1] |
Zhang Chao,Liu Yingjian,Guo Zhongwen,et al.Minimum cost localization problem in three-dimensional ocean sensor networks[C]//Proceedings of the 2014 IEEE International Conference on Communications (ICC).Sydney:IEEE,2014:496–501.
|
| [2] |
Choi J Y,Kim K S,Sung C J. A computational study on sensor localization for underwater acoustic sensor network in the east sea environmental model[J]. Journal of Marine Science and Technology, 2016, 24(6): 1146-1154. DOI:10.6119/JMST-016-1026-3 |
| [3] |
Zazo J,Macua V S,Zazo S,et al. Underwater electromagnetic sensor networks,part Ⅱ:Localization and network simulations[J]. Sensors, 2016, 16(12): 2176. DOI:10.3390/s16122176 |
| [4] |
Chen Tao,Yang Zheng,Liu Yunhao,et al. Localization-oriented network adjustment in wireless ad hoc and sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 146-155. DOI:10.1109/TPDS.2013.17 |
| [5] |
Uddin Y S.Low-overhead range-based 3D localization technique for underwater sensor networks[C]//Proceedings of the 2016 IEEE International Conference on Communications (ICC).Kuala Lumpur:IEEE 2016:1–6.
|
| [6] |
Erol M,Vieira L, Gerla M.Localization with Dive’N’Rise (DNR) beacons for underwater acoustic sensor networks[C]//Proceedings of the Second ACM International Workshop on Underwater Networks.New York:ACM,2007:97–100.
|
| [7] |
Chen Xiuzhen,Shu Haiting,Liang Qilian,et al. Silent positioning in underwater acoustic sensor networks[J]. IEEE Transactions on Vehicular Technology, 2008, 57(3): 1756-1766. DOI:10.1109/TVT.2007.912142 |
| [8] |
Erol M,Vieira L F M,Gerla M.Auv-aided localization for underwater sensor networks[C]//Proceedings of the International Conference on Wireless Algorithms Systems andApplications(WASA 2007).Chicago:IEEE,2007:44–54.
|
| [9] |
Li Bo,Xu Yuanxin,Xu Wen.Multi-AUV localization for an underwater acoustic sensor network[M]//Underwater Acoustics and Ocean Dynamics.Singapore:Springer,2016:117–127.
|
| [10] |
Guo Ying,Liu Yutao. Localization for anchor-free underwater sensor networks[J]. Computers and Electrical Engineering, 2013, 39(6): 1812-1821. DOI:10.1016/j.compeleceng.2013.02.001 |
| [11] |
Huang Huai,Zheng Y R.AoA assisted localization for underwater Ad-Hoc sensor networks[C]//Proceedings of the 2016 MTS/IEEE Monterey OCEANS.Monterey:IEEE,2016:1–6.
|
| [12] |
Chang H Y,Su H M,Choi J W.Performance evaluation of ToA-based sensor localization system in underwater sensor networks[C]//Proceedings of the 2015 15th International Conference on Control,Automation and Systems (ICCAS).Busan:IEEE,2015:493–498.
|
| [13] |
Cheng Wei,Thaeler A,Cheng Xiuzhen,et al.Time-synchronization free localization in large scale underwater acoustic sensor networks[C]//Proceedings of the 2009 29th IEEE International Conference on Distributed Computing Systems Workshops.Montreal:IEEE,2009:80–87.
|
| [14] |
Han Yunfeng,Zheng Cui’e,Sun Dajun. Localization of large scale underwater sensor networks based on recursive position estimation[C]//Proceedings of the 2015-MTS/IEEE Washington OCEANS.Washington:IEEE,2015:1–4.
|
| [15] |
Caffery J J.A new approach to the geometry of TOA location[C]//Proceedings of the IEEE 52nd Vehicular Technology Conference Fall.Boston:IEEE,2000:1943–1949.
|
| [16] |
Chandrasekhar V,Seah W.An area localization scheme for underwater sensor networks[C]//Proceedings of the 2006-Asia Pacific OCEANS.Singapore:IEEE,2006:1–8.
|
| [17] |
Liu Linfeng,Wu Jiagao,Zhu Zhiwen.Multihops fitting approach for node localization in underwater wireless sensor networks[J].International Journal of Distributed Sensor Networks,2015,11(7).DOI:10.1155/2015/682182.
|
| [18] |
Guo Zhongwen,Guo Ying,Hong Feng,et al. Perpendicular intersection:Locating wireless sensors with mobile beacon[J]. IEEE Transactions on Vehicular Technology, 2010, 59(7): 3501-3509. DOI:10.1109/TVT.2010.2049391 |
| [19] |
Guo Zhongwen,Guo Ying,Hong Feng,et al.Perpendicular Intersection:Locating wireless sensors with mobile beacon[C]//Proceedings of the 2008 IEEE Real-time Systems Symposium).Barcelona:IEEE,2008:93–102.
|
| [20] |
Zhou Yi,He Jianhua,Chen Kai,et al.An area localization scheme for large scale underwater wireless sensor networks[C]//Proceedings of the 2009 WRI International Conference on Communications and Mobile Computing.Piscateway:IEEE,2009:543–549.
|
| [21] |
Yang Zheng,Li Mo,Liu Yunhao.Sea depth measurement with restricted floating sensors[C]//Proceedings of the 28th IEEE Real-time Systems Symposium (RTSS 2007).Tucson:IEEE,2007:469–478.
|
| [22] |
Guo Ying. Localization for active-restricted 3D underwater sensor networks[J]. Journal of Software, 2013, 24(增刊1): 33-40. [郭瑛. 活动受限三维水下传感器网络节点定位算法[J]. 软件学报, 2013, 24(增刊1): 33-40.] |
| [23] |
Luo Hanjiang,Wu Kaishun,Gong Yuejiao,et al. Localization for drifting restricted floating ocean sensor networks[J]. IEEE Transactions on Vehicular Technology, 2016, 65(12): 9968-9981. DOI:10.1109/TVT.2016.2530145 |