面向无人机网络快速路由恢复的改进OLSR协议
2022-12-30刘青昕朱小军刘世超
刘青昕，朱小军，董 超 *，刘世超
(1.南京航空航天大学 电子信息工程学院，江苏 南京211106；2.南京航空航天大学 计算机科学与技术学院，江苏 南京 211106)
0 引言
近年来，无人机由于其低成本、小体积、易携带等优势，在各领域都有了越来越多的应用[1]，在实时监控、远程检测、搜寻救援甚至是战场侦察[2]与协同作战[3]等方面都有着出色的表现。相比单架无人机，无人机群协同配合能够更加有效、迅速、灵活地完成数量更多、更复杂的任务。
FANET[4]将移动自组网的应用拓展到空中，为无人机群的可靠通信提供了一种可行的解决方案，使得无人机群能够协同配合完成各项任务。通过FANET，无人机之间无需通过基础设施就可以直接进行通信。此外，部分无人机可以与地面站或卫星进行通信。但由于无人机节点的高动态性、拓扑结构易发生变化等特点[5]，导致网络的链路状态更加频繁地发生变化，在网络开销增加的同时，还会导致端到端时延增加、数据包投递率下降等，甚至造成路由协议失效的情况[6]。因此FANET对路由协议提出了很大的挑战，路由性能的好坏直接影响着网络的性能。移动自组织网络中的路由协议因为没有考虑无人机的高移动性、剧烈变化的网络拓扑和间歇性连接的通信链路，因此不能直接应用于无人机网络[7]。
OLSR[8]是针对移动无线网络需求而形成的经典链路状态算法的优化，是自组织网络中广泛使用的协议之一。多点中继(MPR)是在洪泛过程中转发广播信息的选定节点，与传统的洪泛机制相比，该协议通过使用MPR技术大大减少了消息开销。协议中节点需要周期性地交换各种控制信息，通过分布式计算来更新和建立自己的网络拓扑图，被邻居节点选为MPR的节点需要周期性地向网络广播控制信息。通过这些机制，OLSR一定程度上保证了节点不会使用过时的路由表，保证了一定的实时性。然而，其对拓扑变化频繁的网络不够敏感，当网络中链路突然出现故障时，网络的平均吞吐量、端到端时延等性能指标将有所恶化。
1 相关工作
考虑到移动自组织网络经常发生链路和节点故障，AOLSR[9]将DSR与OLSR进行结合，并基于改进的Dijkstra算法实现路由恢复功能。文献[10]在OLSR的基础上，实验了一种定时器管理技术Pop-Routing。其利用中间性和中心性的概念，根据网络中节点的位置调整参数，使得网络在总体开销不变的情况下，更快地恢复导致较大流量损失的故障。MP-OLSR[11]路由中的每一个节点检查下一跳是否仍在邻居表中，并通过多径路由来为下一跳不在邻居表中的节点规划新的路由。在MP-OLSR的基础上，一种改进的MP-OLSR[12]被提出以优化其路径选择。VANET QoS-OLSR[13]考虑车辆自组织网络，通过蚁群优化算法选择MPR，并在此基础上提出MPR恢复算法。当节点未收到来自MPR的预期TC消息时启动恢复算法以处理故障链路。
还有一些研究尝试对OLSR进行优化以适应FANET。D-OLSR[14]是一种针对配有定向天线的无人机所设计的协议。该协议提出了一种新的转发机制：无人机在每次向目标发送数据时，会测试与目标无人机的距离，若距离小于定向天线最大通信距离的一半且全向天线可用，则使用全向天线；否则，使用定向天线。通过上述机制，该协议减少了所需MPR的数量。P-OLSR[15]在OLSR的基础上，引入了GPS信息。该协议将GPS信息包含在报文中，节点接收到信息时，可以基于此计算出两个节点的相对速度，从而评估节点间的通信链路质量，进而选择质量更高的链路进行通信。进一步地，ML-OLSR[16]考虑了移动与负载感知。与P-OLSR类似，ML-OLSR通过移动感知算法，考虑与邻居节点的相对速度和位置以避免选择高速移动的节点作为MPR。同时，还引入了负载感知算法，考虑每架无人机上的数据包负载，以发现更稳定的路线，避免通过拥塞节点进行路由。与ML-OLSR相似，LTA-OLSR[17]考虑链路质量和流量负载感知。该协议提出了一种链路质量方案，通过使用接收信号强度的统计信息来区分节点与其邻居节点之间的链路质量。还提出了一种流量负载方案，通过考虑信道利用率和缓冲负载来确保较轻的负载路径，然而该协议存在高开销和高计算复杂度的问题。
虽然已有研究对OLSR做出了改进以适应FANET的特点，然而他们主要将目标集中于丢包率与端到端时延。对于FANET中经常出现的节点和链路故障，研究较少。OLSR由于其超时管理机制，当链路断开时，需要较长的时间才能恢复，无法将时间保持在可接受的范围内。因此，需要对OLSR进行优化以使其能够更快地对故障进行反应。
2 路由恢复时间测量与评估
2.1 路由恢复时间测量方法
为了衡量对链路或节点故障反应的快慢，本文使用了路由恢复时间这一概念。路由恢复时间是指自某一时刻网络中发生故障开始，至网络完全删除这一故障的影响为止所经历的时间，该指标能够衡量整个网络对链路或节点故障的敏感性。
在实际运行的无人机网络中，测量路由恢复时间是困难的。原因在于获取准确的故障发生时刻是困难的，故障既可能源自节点自身，也可能源自环境的变化和恶意的干扰。同时对于分布式的无人机网络，信道质量难以保证，单个节点或地面站难以实时获取整个网络的路由表。因此，提出了一种测量方法以检测路由恢复时间。为每一张路由表添加了时刻，如图1所示，首先在故障发生后，记录故障和发生的时刻，然后在每次路由表发生更新时进行检查，直至路由中的故障链路或节点完全删除且不存在回路的影响，记录该时刻与故障发生时刻的差值即为路由恢复时间。应当指出，在实际运行中不需要执行这些操作以测量路由恢复时间，仅在对协议进行评估时需要测量。
图1 测量方法流程Fig.1 Measurement method flowchart
其测量方法可表述为如下步骤：
① 当网络中链路或节点发生故障时，记录故障链路或节点IP，记录当前时刻为故障发生时刻。
② 当网络中路由表发生变化时，获取路由表(包含目的IP、下一跳和跳数)和当前时刻。
③ 遍历路由表，查看是否存在故障链路或节点。若存在，返回步骤②。
④ 对于每一个节点路由表的每一个目的IP，按照如下规则进行路由查找以验证路由是否正确：
a. 记录当前节点、下一跳、目的IP、跳数；
b. 节点变为当前节点的下一跳，跳数减一；
c. 比较记录的跳数和新的当前节点的跳数，若不相等，则返回步骤②；
d. 若跳数不等于一，则返回步骤a；否则，返回步骤④。
⑤ 当路由表被遍历完毕后，输出当前时刻与故障发生时刻的差值作为路由恢复时间。
路由恢复时间测量方法伪代码如算法1所示。
算法1 路由恢复时间测量方法输入:故障链路Rerr或故障节点IPerr、故障发生时刻terr输出:路由恢复时间1.R←getRoutingTable();∥读取全网路由表R2.whileRoutingTableChangedo3. R←getRoutingTable();4. tcur←getCurretTime();∥记录当前路由表时刻tcur5. ifRcontainsRerrorIPerrthen6. gotoline2;7. endif8. 初始化矩阵Q使得Q[i,j]为false,其中i,j分别表示路由起始节点和目的节点9. foreachRijwithQ[i,j]=falsedo∥从R中获取i到j的路由Rij10. hops←hopsij;∥hopsij表示路由表中从i到j的跳数11. Q[i,j]←true;12. whilehops>1do13. i←nextij;∥获取下一跳节点14. ifQ[i,j]then15. gotoline10;∥该路由已被查验16. endif17. hops←hops-1;18. ifhops≠hopsijthen19. gotoline2;20. endif21. Q[i,j]←true;22. endwhile23. endfor24. returntcur-terr;25.endwhile
定理1：算法1能够正确检测路由恢复时间，其时间复杂度为O(kn2)，其中k为故障发生后至路由恢复时路由表发生变化的次数，n为网络中节点的数量。
证明：当路由表中存在故障链路或故障节点时，算法将在第6行重新开始下一轮检测。当路由表中存在环路或过时的路由时，算法将在第19行重新开始下一轮检测。当算法执行至第24行时，路由表中不存在故障链路或节点，同时不存在环路。因此，算法1能够正确检测路由恢复时间。
对于最外层的while循环，算法1运行k轮。在每一轮中，第3～8行运行一次，复杂度为O(n2)；由于第21行会将一个Q中元素从false置为true，而Q共有O(n2)个元素，因此第9～23行的for循环的时间复杂度至多为O(n2)。因此，算法1的时间复杂度为O(kn2)。
2.2 OLSR路由恢复分析与评估
对于网络中路由的更新，OLSR主要受到以下参数的影响[18]：① HELLO消息的发送间隔(Hello Interval，HI)；② 邻居保持时间(Neighbor Hold Time，NHT)；③ TC消息发送间隔(TC Inteval，TCI)；④ 拓扑保持时间(Topology Hold Time，THT)。在默认设置中，HI=2 s，TCI=5 s，NHT与THT分别被设置为HI与TCI的3倍。在每个网络接口，节点会广播HELLO消息以发现邻居节点，将邻居节点添加到自己的邻居表中，并在HELLO消息过期后将邻居删除。HELLO消息仅在一跳范围内传播，不会被其他节点转发。另外，每个MPR节点广播TC消息以更新路由。TC消息在整个网络中传播，使得每个节点建立并维护拓扑表。一旦节点失效，所有包含该节点的路由将失效，在新的TC消息广播至网络或者TC消息过期之前，还可能会导致临时的路由环路。具体而言，不同参数影响路由恢复时间的原理如下。
HELLO消息被每个节点以HI为周期广播，节点接收到HELLO消息后NHT时间内将该信息视为有效信息。HELLO消息承担邻居检测任务，通过类似3次握手的机制完成邻居检测。一旦节点与邻居节点完成邻居检测，则将邻居节点记录在邻居表中，并开放接口连接邻居节点；如果邻居检测失败，则删除记录。HELLO消息还承担着链路感应任务，节点在每个接口上检测和邻居接口之间的链路。节点会在每个接口上广播其一跳邻居，为了链路感应的目的，每个节点到每个邻居的链路具有“对称”“非对称”和“丢失”的状态。“对称”表示到该邻居节点的链路已被验证为双向，即可以在两个方向上传输数据。“非对称”表示已经接收到来自该节点的HELLO消息，但无法确认该节点是否能接收消息。“丢失”表示节点和邻居接口之间的链路已断开。通过交换HELLO消息，OLSR维护一张邻居表，其中包含一跳邻居地址、链路状态、有效时间，以及通过该一跳邻居可达的2跳邻居地址与有效时间。每当收到新的HELLO消息时，节点便会更新邻居表中的条目，并将更新条目的过期时刻设置为当前时刻加上NHT。OLSR会周期性地更新邻居表以删除其中过期的条目。因此，NHT的长短决定了节点对链路断开的敏感性，NHT越长，邻居表中条目的有效时间越长，发现链路过期越慢，反之，NHT越短，邻居表中条目的有效时间越短，发现链路过期的越快。由于OLSR的邻居发现机制，NHT不应小于3倍HI，所以NHT应与HI一同调整。
基于邻居表，每个节点选择出MPR节点集。网络中的节点会向其他节点以TCI为周期广播TC消息，其中包含所有选择该节点为MPR的节点的地址(称作MPR selector)。被选作MPR的节点按照规则生成和转发TC消息等控制消息，通过控制MPR集的大小可以减少洪泛的开销。其他节点收到TC消息后THT时间内将该消息视为有效。基于TC消息的交换，各个节点维护一张拓扑表。同样的，拓扑表中条目的过期时刻为收到TC消息的时刻+THT。网络中的节点通过TC消息保持拓扑表更新，通过拓扑表和邻居表可以计算出全局路由。通过减小TCI，能够使节点更频繁地广播TC消息，从而更快地更新网络中节点的拓扑表。通过减小THT，能够防止即使在TC消息丢失等情况下，也不至于使用过时的拓扑信息。
基于以上分析，测试了改变以上参数时OLSR的路由恢复性能。采用了经典的环形拓扑，每个节点只能与相邻两个节点进行通信，在EXata 5.1上进行了多次重复仿真，每次仿真持续60 s，并设定其中一个节点在第20 s时离线，仿真结果如图3所示。从图中可以发现，默认的OLSR路由恢复时间较长，网络中节点难以及时更新拓扑信息，这对于无人机网络是难以忍受的。另一方面，相较于OLSR的默认设置，当节点数量较少时，减小TCI与THT对减少路由恢复时间效果不明显，随着节点数量的增加，情形逐渐好转。而减小HI与NHT能够显著且迅速地减少路由恢复时间，可以认为减小HI与NHT效果比减小TCI与THT更明显。当以上参数同时减小为默认值的一半时，取得了最好的路由恢复性能，但是这会增加大量额外的控制开销。因此，急需对OLSR进行优化以加速网络的路由恢复。
图2 不同参数OLSR路由恢复时间对比Fig.2 Comparison of OLSR routing recovery time with different parameters
3 FR-OLSR协议
3.1 协议描述
在2.2节中分析了OLSR路由恢复的影响因素，注意到OLSR节点邻居表中条目过期后，并不会实时更新邻居表，同时更新后的MPR selector需要等待TC消息周期性广播至整个网络，这大大增加了OLSR的路由恢复时间。考虑到无人机计算资源与能源的紧张性，也不宜频繁地计算路由信息。因此，提出快速路由恢复协议FR-OLSR，其核心机制如下：
每次节点生成HELLO消息时，检测HELLO消息中是否有与邻居类型为对称节点或MPR节点的链路状态为链路丢失。若有，则在HELLO消息发送后，更新邻居表与路由表，生成并发送一个新的TC消息。实际上，实时监测邻居表，每当邻居表中存在过期条目时更新邻居表与路由表能够使邻居节点更快路由恢复。然而，对于拥有多个接口多个邻居的节点，由于邻居表中还包含2跳邻居节点，邻居表中条目状态变化是频繁的。实时监测邻居表并更新会导致计算开销成倍甚至是几十倍的增长。仅在生成的HELLO消息中进行检测，在检测到链路丢失时额外发送一个TC消息，能够在多条链路频繁丢失时也仅在HI时间内额外生成一个TC消息，有效控制额外的开销。
当节点收到HELLO消息后，同样检测HELLO消息中是否有与邻居类型为对称节点或MPR节点的链路状态为链路丢失。若有，则记录当前时刻，并在NHT秒后更新邻居表与路由表。对于运行OLSR的小规模网络，当发生节点或链路故障时，2跳邻居节点总是最后路由恢复的。通过检测接收的HELLO消息中的链路丢失信息，能够在不监测邻居表中2跳邻居信息的同时，有效加速路由恢复。伪代码如算法2所示。
算法2 FR-OLSR核心机制输入:事件类型eventType1.ifeventType=GenerateHelloMessagethen2. foreachneighborinhellomessagedo3. ifneighborType=SYMorMPRandlinkStatus=LostLinkthen∥检测到与邻居类型为对称节点或MPR节点的链路状态为丢失4. sendHelloMessage();5. refreshNeighborTable();6. calculateRoutingTable();7. generateTCMessage();8. sendTCMessage();9. endif10. endfor11.elseifeventType=ReceiveHelloMessagethen12. foreachneighborinhellomessagedo13. ifneighborType=SYMorMPRandlinkStatus=LostLinkthen14. refreshNeighborTable(NHT);∥NHT秒后更新邻居表15. calculateRoutingTable(NHT);∥NHT秒后计算路由表16. endif17. endfor18.endif
3.2 协议分析
引理1：OLSR的路由恢复时间为max(2NHT+Tnh-Terr,Ttc-Terr+to)，其中Terr为故障发生时刻，Tnh为故障发生后下一次邻居表更新时刻，Ttc为邻居节点路由恢复后下一次TC消息发送时刻，to为新生成的TC消息广播至所有节点所花费的时间。
证明：当节点故障或是链路突然断开，对于OLSR网络的路由恢复，可以分为3种节点：邻居节点、2跳邻居节点和其他节点。邻居节点在上一次接收到对应的HELLO消息NHT时间后故障链路过期，并在之后最近一次的邻居表更新计时器到期时更新路由。则邻居节点的路由恢复时间为：
trn=NHT+Tnh-Terr。
(1)
由于在邻居节点故障链路过期前，2跳邻居节点会收到邻居节点周期性广播的含有该链路的HELLO消息，因此2跳邻居节点的路由恢复时间为：
tr2n=trn+NHT=2NHT+Tnh-Terr。
(2)
其他节点则会在收到故障链路邻居节点的TC消息时将故障链路删除，即其他节点的路由恢复时间为：
tro=Ttc-Terr+to。
(3)
如图3所示，网络的路由恢复时间为：
tr=max(trn,tr2n,tro)=max(tr2n,tro)。
(4)
图3中，Xi为OLSR周期性广播TC消息时刻，Yi为邻居表更新计时器到期时刻。
定理2：FR-OLSR的路由恢复时间为max(t′rn+NHT,t′rn+to)，路由恢复性能优于OLSR，其中t′rn为邻居节点路由恢复时间。
证明：对于运行FR-OLSR的节点，邻居节点的路由恢复时间为：
t′rn=min(NHT+Th-Terr,NHT+Tnh-Terr)，
(5)
式中，Th为故障发生后下一次发送HELLO消息的时刻。
图3 OLSR路由恢复时间示意图Fig.3 Schematic diagram of OLSR routing recovery time
2跳邻居节点的路由恢复时间为：
t′r2n=t′rn+NHT。
(6)
其他节点的路由恢复时间为：
t′ro=t′rn+to。
(7)
如图4所示，网络的路由恢复时间为：
t′r=max(t′r2n,t′ro)。
(8)
图4中,Zi为OLSR周期性广播HELLO消息时刻。
因为t′r2n-t′ro=NHT-to，所以当to
图4 FR-OLSR路由恢复时间示意图Fig.4 Schematic diagram of OLSR routing recovery time
考虑到Th∈[0,HI)、Tnh∈[0,NHT)，因此tr2n-t′r2n=trn-t′rn∈[0,NHT)，即对于邻居节点和2跳邻居节点，FR-OLSR能够比OLSR路由恢复时间减少[0,NHT)。考虑到Ttc-Terr-trn∈[0,TCI)，因此tro-t′ro∈[0,NHT+TCI)，即对于其他节点，FR-OLSR能够比OLSR路由恢复时间减少[0,NHT+TCI)。综上，在参数相同的情况下，FR-OLSR能够比OLSR路由恢复时间减少[0,NHT+TCI)。
4 实验评估
4.1 仿真设置
本文基于EXata 5.1进行仿真，网络拓扑如图5所示，分别为正方形环形拓扑与网状拓扑，调整传输功率使节点仅能与相邻节点进行通信(即图5中虚线所示)。每个节点物理层采用802.11b协议，设置路径损耗模型为两径模型，每次仿真时间为60 s，并在第20 s时其中一个节点离线。
(a) 环形拓扑
4.2 仿真结果
为了评估FR-OLSR的性能，本文选择了EXata中的OLSR-INRIA作为对比协议，从路由恢复时间和协议开销两个方面，针对两种拓扑不同节点数量进行了多次重复实验。本文对两种协议均设置了默认参数和高性能参数进行仿真。对于OLSR,默认参数为HI=2 s，NHT=6 s，TCI=5 s，THT=15 s，高性能参数(OLSR*)为HI=1 s，NHT=3 s，TCI=2.5 s，THT=7.5 s；对于FR-OLSR,默认参数为HI=2 s，NHT=6 s，TCI=5 s，THT=15 s，高性能参数(FR-OLSR*)为HI=1 s，NHT=3 s，TCI=5 s，THT=15 s。
图6(a)给出了环形拓扑下随着节点数量增加OLSR和FR-OLSR路由恢复时间的变化曲线，由图可知，FR-OLSR能加快路由恢复，减小突然断开的链路对网络的影响。同时，路由恢复时间与节点数量呈现出单调增加的趋势。因为在该拓扑下，网络中路由最大跳数较大，TC消息广播至整个网络所需时间较长，路由恢复时间主要受该因素影响。图6(b)给出了网状拓扑下随着节点数量增加OLSR和FR-OLSR路由恢复时间的变化曲线，由图可知，当节点数量较小时，两种协议的路由恢复时间均维持在一定范围内。因为TC消息能够较快的广播至整个网络，路由恢复时间主要取决于2跳邻居节点的恢复时间。
图7展示了两种拓扑下不同协议不同参数每个节点平均生成的TC消息数量。可以发现相较于同参数的OLSR，FR-OLSR仅生成极少的额外TC消息。而减小TC消息发送间隔，显而易见的，会生成更多的TC消息，带来更多的开销。
图8展示了两种拓扑下不同协议不同参数每个节点平均转发的TC消息数量。结合之前的图表进行分析，减小TC消息发送间隔，OLSR仅能够有限地减少路由恢复时间，但会带来大量的额外开销，大幅占用无人机有限的资源。
(a) 环形拓扑
(a) 环形拓扑
(a) 环形拓扑
表1展示了不同协议不同参数每个节点生成的HELLO消息数量。实际上，这一指标仅与HI有关。由于HELLO消息仅在一跳范围内传播，不会被接收到的节点转发。因此，减小HELLO消息发送间隔，仅会带来少量额外开销。
表1 HELLO消息平均生成数量Tab.1 Average number of HELLO messages generated
综上所述，相较于OLSR，在均为默认参数的情况下，FR-OLSR可以在增加5%控制开销的情况下，将路由恢复时间降低25%。而通过将FR-OLSR的HI与NHT减小为原来的一半，FR-OLSR能够在增加15%控制开销的情况下，将路由恢复时间降低50%。
5 结论
传统的OLSR协议是针对移动无线网络需求而形成的经典链路状态算法的优化，但在FANET中，由于其超时管理机制，当链路断开时，需要较长的时间才能恢复，无法将时间保持在可接受的范围内。本文给出了路由恢复时间的一种全新测量方法，分析了OLSR协议中影响路由恢复时间的因素，并提出了FR-OLSR以快速恢复网络中的路由。EXata仿真结果表明，相较于OLSR，FR-OLSR能够在增加少量通信开销的同时，减少路由恢复时间，加快网络的路由恢复。
