适用于水下物联网的混合地理路由协议设计

闫 磊 何天恺 王易因 张榕鑫 李鑫滨

①(东北大学秦皇岛分校计算机与通信工程学院 秦皇岛 066004)

②(系统控制与信息处理教育部重点实验室 上海 200240)

③(燕山大学电气工程学院 秦皇岛 066004)

④(上海交通大学自动化系 上海 200240)

⑤(上海工业智能管控工程技术研究中心 上海 200240)

⑥(厦门大学水声通信与海洋信息技术教育部重点实验室 厦门 361005)

1 引言

近年来水下物联网(Internet of Underwater Things, IoUT)受到了广泛的关注[1-4]。相对陆基的物联网，IoUT要更为复杂，存在造价昂贵、能量受限以及更为稀疏的布置[5]等挑战。同时，严苛的水下环境造成的不可忽视的高时延、节点移动性、低带宽等降低通信可靠性的挑战[6,7]也同样给IoUT节点间的通信造成不小的困扰。因此，IoUT需要更加高效的路由协议通过声学或光学的方式完成数据的转发[8,9]。

IoUT中的通信和数据传输主要可分为依靠节点间的多跳传递和借助AUV的数据收集两种方法。本文主要讨论依靠节点网络自身的多跳路由，其关键在于保障收发节点和中继节点之间端到端的可靠链路以及在整个网络中的可靠路径[10]。其中可靠链路在于克服水声信道严苛的信道状态完成邻居节点之间的有效数据传输，而可靠路径则是应对水下复杂环境和死亡节点等因素造成的中继无以为继的路由虚空区，保证收发节点之间的有效路由。

水下物联网中的路由方法大致可分为表格驱动路由、按需路由、机会路由、基于多播树的路由和地理路由方法[11]。前4种方法分别存在着高能量开销、高路由时延、高数据包冲突和在移动节点网络中低稳定性等较为突出的劣势。地理路由方法是一种能够以低通信、低存储开销完成数据传输，并保证路径可靠性的有效方案。它只需求掌握目标节点与相邻节点的位置信息，无需维持全局信息或者对网络进行泛洪，具有很强的实际可操作性。地理路由采用贪婪转发策略获取次优的传输路径，这条路径在大多数情景中为最短路径。地理路由一般还包含某种迂回模式。GPSR协议通过右手法则绕过贪婪转发无以为继的局部最小值[12]。GOFAR+协议将数据的转发限制在一个可探索区域内以更快地从迂回模式中回归到贪婪转发模式[13]。然而当应用场景变换到诸如水下网络或空天地一体网络的3维空间时，基于两种模式的路由协议的可用性被严重削弱[14,15]。为解决3维路由问题，近年出现了许多基于深度或压力的定向路由协议[16-18]。随着IoUT应用范围的扩张，相较于以往的只用于某种特定应用的水下传感器网络，这些定向路由协议并不能很好地适应大规模且多AUV、水下滑翔机异构移动节点参与的多功能应用情景。简而言之，IoUT对能够连接网络中的任意两个节点并完成数据传输的路由方法提出了需求。

值得一提的是无状态几何路由(Geometric STAteless Routing, G-STAR)[14]为地理路由协议在3维空间中的应用提供了一个新的思路。由于无需切换到某个特定的迂回路径，G-STAR不需要对转发模式进行切换或对网络拓扑进行平面化处理，由此显著地降低了路由复杂度。但是，此协议在IoUT中的应用仍存在以下问题。

(1) 位置信息的获取。网络中的节点的绝对或相对位置信息的先验获取是完成地理路由的关键。全球定位系统(Global Positioning System, GPS)在水下环境中无法运作。而由于水下声速剖面(Sound Speed Profile, SSP)随水深呈非线性变化[19]，基于到达时间(Time of Flight, ToF)的测量方法有可能获得不准确的测量结果。此外，通过传统水下测距或定位方法难以同时大规模地获取节点的准确位置信息[16]。

(2) 水下信道和网络状态。声学与光学的无线信道存在传输的“阴影区”[20,21]或“虚空区”[18]。此外，受限于有限的能源，大部分节点一般处于睡眠模式中，在某时刻的路由中，网络中可进行路由的节点数目是受限的。由此，一个直线的直达路径在大多数情况下是不可能的，需绕行其余可用节点进行路由，因此在路由过程中网络的拓扑经常显示为一种显著的C型拓扑。得到次优路径的地理路由协议在这种情况下会带来大量的无效转发。

(3) 探索与利用之间的折中。G-STAR协议的主导思想是建立一个基于位置信息的树，动态地搜索路由路径。对树搜索而言，尤其是在IoUT网络中，探索和利用的折中是不可忽略的。对树广度的搜索，可以视为网络中对最优路由的探索，探索的增加能够不断优化路由路径的选择，直至寻找到存在的最优路径，但同时也带了更大的能耗和更长的时延。对于网络的利用则是指树深度的发掘，使数据尽可能早地抵达目标位置，但路由所寻到的路径在大多数情况下并非最优。例如，在提高网络的整体性能时，我们也需考虑数据传输所占用的开销。而在复杂的物理层环境中，我们需要考虑在利用尽可能少的跳数的情况下，保持较低的误码情况。

综上，为解决以上所提出的问题，本文基于GSTAR协议与无协作转发方法，设计一种可适用于IoUT情景的可靠传输的混合路由协议。文章其余部分结构如下：第2节陈述与本文研究相关的技术；第3节描述所提出的H-G-STAR协议；第4节给出实验仿真结果与分析；第5节得出结论；第6节对H-G-STAR的未来研究进行探讨。

2 相关技术

本节讨论H-G-STAR协议的相关技术。首先对水下无线路由器的混合解决方法以及IoUT的通信、定位和导航一体化(Integration of Communication, Positioning, Navigation, ICPN)进行分析。接着给出设计协议时所采用的无线信道传输模型。

2.1 水下无线路由器的混合解决方法以及ICPN

由于IoUT同时对远距离网络覆盖和高速数据传输提出了需求，许多水下无线通信机的混合方案应运而生。文献[9]为IoUT引入了光学-声学的混合通信方案。文献[22]所提出的采用两种不同频段的声学混合通信机能达到近似于CDMA-IoT LTE系统的性能[23]。这些混合架构的提出，令IoUT网络能够轻松地执行图1所示的ICPN[24,25]。此类轻量化的海洋协作导航系统相比于超短基线、海面无人舰艇协作导航等较高复杂度的定位系统而言，能够以稍低的定位精度的代价，取得有限错误率、低开销和高续航的定位与导航能力，更为适用于水下传感器、AUV等能源受限的轻型设备。由此可以采用低复杂度的测距方法[4,26]获得网络中各个节点的准确位置信息。

图1 图l l2-AUV-MN-2.0网络模型的 ICPN[4]

2.2 信道模型

其中，µξ和σξ分别为l nx的均值和方差。作为大尺度衰落，阴影效应ξm和距离衰减dm在一个相对较长的时间尺度上不发生变化，假定其为常数。

3 H-G-STAR地理路由协议

3.1 G-STAR协议[14]和无协作转发[27]

对于G-STAR协议，数据的转发总是通过贪婪转发策略完成，即便是进入了一个局部最小值也不会切换到某个迂回路由策略上。相应地，G-STAR协议的数据帧需对其已探索的网络节点进行记录以应对局部最小值。

当某个节点产生数据帧时，帧内将初始化一个空白的路由表。路由过程中，每当一个节点接收到此数据帧时，路由表会登记此节点并且查询该节点是否重复登记。若重复，则路由表保留最早的记录并移除此次登记。由此，路由过程中的每个节点仅在路由表上出现1次。对于当前节点，路由表中记录的上一个相邻节点即为其上一跳节点，标注为当前节点的父节点。

当遇到局部最小值时，数据帧将被回退转发至其父节点处。父节点使用贪婪转发策略将数据帧转发给它其余未被路由表登记的相邻节点。若父节点的所有相邻节点均被路由表登记，父节点便将数据帧继续回退至它的父节点。由此循环往复直到跳出局部最小值或回退至发送节点处，后者标志G-STAR路由的失败。

3.2 改进协议流程

本协议默认使用G-STAR协议进行数据转发，当节点的环境符合条件时，在使用G-STAR协议的同时也启用无协作转发方法进行数据发送。H-G-STAR协议的流程框图如图2所示。

图2 H-G-STAR 协议工作流程图

各个节点通过式(4)计算其与各节点的位置，并以此位置信息作为地理路由的先验知识。由此位置信息以及预设的相邻节点范围，划定各节点所对应的相邻节点。

为H-G-STAR协议设定一个相邻节点阈值，只有当相邻节点的数量到达此阈值时，当前节点才同时尝试使用无协作转发方法进行发送。启用无协作转发方法时，根据当前节点的相邻环境，主要存在以下几种判决情况：

(1) 无协作转发方法首先在相邻节点中搜索存在于转发圆锥范围内的备选节点。利用路由中各节点与目标节点及其相邻节点的距离已知，通过余弦函数计算相邻节点相对于当前节点与目标节点相连的轴线的角度，将处在扩散角内的节点列为备选节点。若无备选节点存在，无协作转发不生效，仅进行依据G-STAR协议的转发。

(2) 存在备选节点，无协作转发通过广播方式发送数据。各备选节点通过广播数据中的导频信息，对其与发送节点之间信道的物理层CSI进行信道估计。节点调用数据链路层计时器T(hm)，函数设定的计时长度与物理层所反馈的CSI优劣呈负相关趋势。开始计时并进行信道监听。若其备选节点中计时器函数T(hm)数值最小，即CSI最佳的节点与GSTAR协议所选节点相同，那么此跳转发视为仅进行了依据G-STAR协议的转发，不产生新分支。

(3) G-STAR协议转发的节点和无协作方法选择的下一个发送节点不同，路径产生新分支。原分支的下一跳选择记录为G-STAR协议所选择的节点，无协作转发所选择的下一跳则记录在新分支中。

每个路由分支根据H-G-STAR协议独立地执行路由步骤直到完成路由或抵达生存时间值(Timeto-Leave, TTL)所容许的转发跳数上限。成功完成路由的分支将被标记为有效分支，而后者为无效分支并舍弃。

完成路由后，为进一步精简路径，通过信道监听技术对G-STAR协议产生的路径进行剪枝[28]，消除G-STAR协议本身无法除去的回路。由此得到一棵路由树，其首个分支为G-STAR主导而末尾分支拥有最高的无协作转发比例。

H-G-STAR协议通过使用G-STAR协议和无协作转发方法分别拓展了它的路由树的深度和广度。G-STAR协议所遵循的贪婪转发模式能够尽可能快速地完成信息传输所需要的路由。而相较于G-STAR协议的单一路径，运用H-G-STAR协议进行路由的节点通过产生的多个分支在目标节点处实现协作分集，并在后续的传输中选择已探索的路由树中CSI最佳的信道进行使用，减少后续的通信开销。

4 仿真分析

本节首先讨论H-G-STAR协议在路由中的树搜索过程。H-G-STAR协议在C型拓扑的路由路径如图3所示。可见其利用G-STAR的特性，对树的深度进行了充分的发掘，为此次数据传输保证了路由可能。同时在邻居节点数量允许时，选择了信道状况最佳的邻居节点进行路由，优化了路由路径的选择，实现了对树的广度的搜索。

图3 H-G-STAR 协议树搜索的探索和利用

如图4、图5所示，网络以随机拓扑布置，总节点数分别为75, 150个节点，对应为平均相邻节点数分别为6和12的网络密度。图4的数据帧在两条分支路径中均经历4跳转发，其中仅有1跳产生了分支并在下一跳重新融合。无协作路由避开了劣化的信道，由仅仅1跳的区别便取得优于仅使用G-STAR的性能。使用无协作路由进行分支的机会随着网络密度的提升而升高。如图5所示，当节点总数达到150个时，G-STAR协议主导的路径经历4跳传输而无协作主导的路径经历5跳。尽管增加了跳数，使传输路径延长，将信道状况纳入转发条件的无协作路由的误比特率仍显著低于G-STAR协议。

图4 随机拓扑的误比特率，网络节点数为 75

图5 随机拓扑的误比特率，网络节点数为 150

在C型拓扑中的路由一般会在发送节点附近形成数个回路，这是由于贪婪转发策略尝试直接向目标节点进行发送而遇到中心虚空区域造成的。这些回路会通过后续的剪枝进行去除。此拓扑中无协作路由产生的分支主要发生在发送源位置以及当路径越过C型弯以后指向目标节点时，前者由回路所激活的多个节点产生，后者是因为那些能够在TTL内完成数据帧传输的节点进入了转发节点的备选锥体范围内。

H-G-STAR协议在C型拓扑中的表现与随机拓扑的结论相似。如图6所示，在稀疏网络中混合协议的误比特率仅有较小的优势。这个优势随着网络密度的提升而逐渐显著，如图7所示，在150个节点的网络中H-G-STAR的误比特率相较G-STAR低了约5 dB。

图6 C 型拓扑的误比特率，网络节点数为 75

图7 C 型拓扑的误比特率，网络节点数为 150

图8、图9展示了H-G-STAR协议的送达率。图中将H-G-STAR协议的送达率与仅使用G-STAR协议、基于深度的GCORP的送达率进行比较。图8为在随机拓扑中路由的送达率，网络密度从3提升到12。每个密度值生成1000个不同的拓扑，TTL阈值设定为10跳。可见H-G-STAR协议与G-STAR协议的性能相似。在可能存在水平传输的随机拓扑中，基于深度由深向浅路由的GCORP有着较低的送达率。图9为C型拓扑的送达率，网络密度从3提升到13。由于在此类拓扑下，所需路由跳数较多，因此将TTL阈值设定为40跳。从图中可见H-G-STAR协议利用分支传输，在较高网络密度中的送达率比G-STAR高了约10%。此外，可以观察到图中产生了一个送达率峰值。这是由于随着节点数的增加，浪费在回路中的跳数也不可避免地增多，使数据帧在路由完成前便已经耗尽了TTL。而在为绕过虚空区而必然存在水平传输的C型拓扑中，GCORP几乎无法送达。表1、表2分别为3种传输协议在数量为150个节点，比特能量Eb/No为20 dB的随机和C型拓扑中误码率随网络密度的变化趋势。在随机拓扑中，G-STAR和H-G-STAR表现相似且误码率随着网络密度的提升显著下降。基于深度的GCORP则有着一定的送达能力，但是可靠性不佳。而C型拓扑中，H-G-STAR能够取得优于G-STAR的误码表现，而GCORP几乎无法送达。只有在网络密度扩大到16个邻居节点以上时，GCORP才能够勉强完成送达而且误码严重。

图8 随机拓扑的送达率，TTL=10

图9 C 型拓扑的送达率，TTL=40

表1 随机拓扑的误码率

表2 C型拓扑的误码率

5 结束语

本文提出了一个适用于IoUT的混合地理路由协议。通过利用ICPN，地理路由所使用的先验位置信息能够以较低复杂度的方法获取。为进一步提升水下路由在不同拓扑，尤其是有限能量和(或)严苛信道环境造成的C型拓扑中的可用性，本文使用无协作转发延伸动态树搜索的宽度。同时，通过将计时器的设定与CSI挂钩，路径探索的过程中仍能保证一个较低的误比特率。

通过对两种不同网络拓扑的仿真，可见稀疏网络中可产生分支的可选路径较少，并且G-STAR协议本身便已经能够较好地完成路由过程，H-G-STAR协议的优越性随网络密度的提升而显现。该混合协议带来的低误比特率弥补了其对通信开销和存储需求的更高要求，同时相较于需要全局信息或网络泛洪的传统协议，H-G-STAR仍属于轻量化协议。

本文展现了H-G-STAR的基础研究工作，作者认为此工作还能在以下方向进行延伸。从理论角度而言，路由的目标节点可通过无协作转发实现协作分集，以此取得优于仅使用G-STAR协议的物理层性能。后续将进行协作分集的理论分析，以优化物理层性能和网络送达能力之间的折中。在此文中，每个时隙中的信道状况参数被假定为恒定值，从实际应用角度出发，路由过程中需求较为准确的信道追踪或信道预测，通过机器学习进行辅助是解决该问题的一个有效方案[29]。