软件定义无人机自组网高效自适应路由维护机制*

周佳琦，黄 璨2，曹建玲，任丽丹，任 智

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.北京邮电大学 电子工程学院，北京100876)

0 引 言

节点构成的无线自组织网络，由于其灵活性，可快速在空中组成骨干网络，为缺少基础设施的地面提供可靠的通信，因此被广泛应用于各类场景[1-2]。由于无人机(Unmanned Aerial Vehicle,UAV)快速移动和能量限制等特性，网络中的资源管理、协议差异性和拓扑管理等问题仍然存在不少的挑战[1，3-4]。软件定义网络(Software-defined Network，SDN)作为一种新型的网络架构，将网络分为数据平面和控制平面，控制平面与数据平面通过南向协议OpenFlow连接[5]，其逻辑上的集中控制和网络开放可编程等特性能够很好地解决上述问题[6-7]，因此部分学者提出了软件定义无人机自组网(Software-defined Unmanned Aerial Vehicle Ad Hoc Network，SD-UANET)。

文献[3]提出了一种基于SDN的UANET拓扑管理协议，目标是建立和维护UANET拓扑结构，该文献中提到在UAV节点接收到流表项缺失数据包后选择请求控制节点处理。文献[8]针对UANET高动态、不稳定的空中无线链路和无人机碰撞的特性提出了SD-UANET架构。文献[9]为了保证UAV状态信息的可靠传输，在控制节点收到状态信息后向UAV节点回复一个ACK消息。文献[10]中UAV节点周期性发送HELLO消息收集邻居信息，通过AODV路由协议将邻居信息发送给控制节点，控制节点根据收集的邻居信息计算路由并向每个UAV节点下发路由信息。文献[11]中UAV节点将更新消息和下游节点的更新消息相合并发送给控制节点，减少路由更新过程的控制开销。文献[12]为最新的OpenFlow协议标准，协议标准规定在节点缓存区足够的情况下采用请求流表项的处理方式，在节点缓存区不足的情况下将整个数据包发送给控制节点处理。

通过以上研究发现，现有SD-UANET中针对流表项缺失数据包处理方法的研究较少且存在如下问题：一是UAV节点对于接收到的流表项缺失数据包目前采用向控制节点发请求消息或向控制节点发送流表项缺失数据包的处理方式，由于UAV节点的移动性，最短时延的转发方式不断发生变化，采用单一的转发方式会带来较大的时延；二是控制节点与UAV节点之间发送的控制包数量较多，产生的网络控制开销较大且无线碰撞概率较大。

为了解决现有文献在SD-UANET路由维护方面存在的问题，本文提出了一种高效自适应的软件定义无人机自组网路由维护机制，通过估计距离自适应选择时延最低的转发方式；同时提出了基于周期恢复的消息聚合策略，聚合两类数据包减少网络控制开销，降低无线碰撞概率。

1 网络场景和问题描述

1.1 网络场景

SD-UANET的拓扑图如图1所示，由一个控制节点(Controller Node，CN)和多个UAV节点组成，UAV节点之间通过数据平面传输数据包，CN与UAV节点之间使用OpenFlow协议通信。首先,每个UAV节点周期性发送HELLO消息收集邻居节点信息，UAV节点将收集好的邻居信息周期性的发送给CN；然后,CN节点根据收集到的邻居信息建立全网拓扑并计算每个UAV节点的路由；最后,CN节点周期地向每个UAV节点下发流表，UAV节点根据收到的流表转发数据包。若UAV节点收到流表项缺失数据包，则将数据包缓存，向CN发送请求流表项的消息，若UAV节点缓存空间不足，则将整个数据包发送给CN，CN根据流表信息转发CN数据包。

图1 SD-UANET拓扑图

1.2 问题描述

(1)目前SD-UANET中UAV节点接收到流表项缺失数据包后处理方法有两种：方法1采用请求CN下发流表项，由UAV转发；方法2将数据包直接发送给CN，由CN转发。由于UAV节点的移动性，即使UAV节点的缓存区有足够的空间，当方法1的转发时延大于方法2时，单一的选择方法1转发会产生较高的时延。

(2)UAV节点不仅要周期性的上传邻居信息，也需要在接收到流表项缺失数据包后向控制节点发送数据包或请求流表项消息，当两种过程同时进行时会增大无线传输的碰撞概率。此外，这两种过程都需要UAV节点向CN发送数据，相比于聚合消息发送，单独发送数据包所产生的网络控制开销更大。

2 OpenFlow-EARM

针对现有的SD-UANET中流表项缺失处理时延长、网络控制开销大和无线传输碰撞问题，本文提出了OpenFlow-EARM。新机制包含如下两个策略：一是基于距离估计的自适应转发策略，在UAV节点中收到流表项缺失的数据包的情况下，UAV节点通过历史流表项信息估计目的节点的位置，再根据估计位置选择时延最低的转发方式；二是基于周期恢复的消息聚合策略，通过聚合邻居信息和流表项缺失处理过程的控制包减少网络控制开销，考虑到邻居信息是周期性上传，流表项缺失处理过程的控制包为非周期发送，由于聚合消息产生后立即发送，因此在聚合消息发送后需要将邻居信息的发送周期恢复到原周期。

2.1 基于距离估计的自适应转发策略

针对1.2 问题描述(1)，本文提出了基于距离估计的自适应转发策略，该策略核心思想是，通过流表项删除后的时间值和UAV节点最快移动速度计算得到目的UAV的最大移动范围，根据最大移动范围信息计算得到UAV节点到目的节点和控制节点到目的节点的距离；然后通过以上两个距离信息和UAV节点到控制节点的距离计算出两种方法的时延；最后根据计算出的时延选择最低时延的方法转发。

2.1.1 距离估计

假设UAV的最大移动速度为vmax，流表项移除后的时间值tmove为

tmove=Tnow-Tremove。

(1)

该值等于当前时刻与流表项移除时刻之差。假设Tnow时刻的UAV节点的位置为L(Xu,Yu)，控制节点的位置为L(Xc,Yc)，Tremove时刻目的节点的位置为L(Xd,Yd)。通过公式(2)计算得到tmove时间内UAV的最大移动距离Dmax为

Dmax=vmax×tmove。

(2)

因此在tmove时间内，目的UAV节点的活动范围为以L(Xd,Yd)为中心、半径为Dmax的圆内，根据公式(3)计算得到圆上的坐标位置L(Xr,Yr)为

(3)

如图2所示，L(Xu,Yu)和L(Xc,Yc)分别与圆心L(Xd,Yd)连为一条线段并将其延伸，这两条线段与圆上相交4个点，这4个点分别为距离UAV节点和控制节点的最远和最近坐标点。

图2 距离估计原理图

根据UAV节点的通信范围，可以得到相邻节点之间平均距离间隔为Dinter，最后根据公式(4)计算得到距离为D的路径上产生的时延d为

(4)

式中：PL为发送数据包的包长，Rtrans为发信机的发送速率，dprop、dproc和dque分别为UAV节点的传播时延、处理时延和排队时延。

2.1.2 基于距离估计的自适应转发策略具体流程

基于距离估计的自适应转发策略流程如图3所示。

图3 基于距离估计的自适应转发策略流程图

基于距离估计的自适应转发策略的具体步骤如下：

Step1 判断UAV节点的历史流表项信息中是否有流表项缺失数据包匹配的流表项，若有则执行Step 2，若没有则执行方法1，控制节点向UAV节点下发到目的节点的流表项。

Step2 根据公式(5)和各节点坐标计算得到UAV节点与控制节点之间距离Duc、控制节点到目的节点最小距离Dcr1、最大距离Dcr4，UAV节点到目的节点最小距离Dur2、最大距离Dur3：

(5)

Step3 将Step 2计算出的距离代入公式(4)，计算得到方法1和方法2的最大、最小转发时延，如公式(6)所示：

(6)

若满足公式(7)表示方法1转发的最大时延小于方法2转发的最小时延，则选择方法1转发；若满足公式(8)表示方法1转发的最小时延大于方法2转发的最大时延，则选择方法2转发，若都不满足则执行Step 4。

(dway2)min>(dway1)max，

(7)

(dway2)max<(dway1)min。

(8)

Step4 根据时刻Tremove目的节点的位置分别计算两种方法的转发时延，选择时延最小的方法转发。

2.2 基于周期恢复的消息聚合策略

针对1.2 问题描述(2)，本文提出了基于周期恢复的消息聚合策略。该策略核心思想是，通过聚合邻居信息和流表项缺失处理过程的控制包减少网络控制开销，考虑到邻居信息是周期性上传，流表项缺失处理过程的控制包为非周期发送，在流表项缺失处理过程执行后，控制包以多于一个原周期的间隔发送直到恢复到原周期。

2.2.1 Packet-in消息格式修改

本策略使用OpenFlow协议中的Packet-in消息传输邻居信息、流表项缺失数据包和请求流表项消息，Packet-in消息格式如图4所示。

图4 Packet-in数据包结构

在不触发流表项缺失处理过程的情况下，UAV节点传输邻居信息使用原有的Type值(Packet-in Type=10)，如果触发了流表项缺失处理过程，则使用新定义的聚合消息：聚合消息分为邻居信息与流表项缺失数据包聚合(Type=74)和邻居信息与请求流表项消息聚合(Type=138)，由于聚合消息需要将邻居信息与整个流表项缺失数据包(或128 B的字节头[12])区分开，本策略将添加一个32 b的Position字段表示流表项缺失数据包在Data字段的位置。

2.2.2 基于周期恢复的消息聚合策略具体流程

基于周期恢复的消息聚合策略流程如图5所示。

图5 基于周期恢复的消息聚合策略流程图

基于周期恢复的消息聚合策略的具体步骤如下：

Step1 UAV节点以周期T向控制节点发送邻居信息，控制节点收到邻居信息后向UAV节点发送ACK消息。

Step2 UAV节点判断是否在超时时间内收到来自于控制节点的ACK消息，若收到了则执行Step 3，若没有收到则执行Step 1。

Step3 判断是否有请求流表项消息或流表项缺失数据包需要发送，如果有则执行Step 4，如果没有则执行Step 1。

Step4 聚合两类消息，立即发送。

Step5 发送聚合消息后，判断发送时刻是否为周期T的整数倍，如果是则执行Step 6；如果不是则下一个邻居信息以上整数[T]+1时刻发送，然后再次执行Step 5。

Step6 判断发送次数是否等于周期数，如果等于表示已经恢复到原来的周期；如果不是则以1.5个原周期发送邻居信息，然后再次执行Step 6。

3 仿真验证

本文使用OPNET14.5仿真软件对OpenFlow-EARM机制的性能进行验证，在相同的网络环境下，将OpenFlow-EARM机制与现有的最优化链路状态路由(Optimal Link State Routing,OLSR)协议和OpenFlow协议相比较。

3.1 仿真参数设置

主要的仿真参数如表1所示，仿真场景由一个控制节点和多个UAV节点组成，UAV节点均匀的分布在2 500 m×2 500 m的场景中。

表1 主要仿真参数

3.2 性能指标

3.2.1 平均端到端时延

平均端到端时延是数据包成功地从源节点到达目的节点所花费的平均时间。可以使用公式(9)进行计算:

(9)

式中：ATi是数据包到达时间，STi是数据包发送时间，n是数据包总数。

3.2.2 网络控制开销

OLSR和OpenFlow采用不同控制方式，本文对于不同控制方式网络的网络控制开销统计方式有所不同，OLSR作为表驱动协议，其网络控制开销主要来自于路由表更新，为了与OpenFlow中的流表项缺失处理过程相对应，本文统计OLSR中路由表更新和缺失路由表项处理两个部分的网络控制开销；OpenFlow由于其控制平面和数据平面分离，流表更新过程中网络控制开销来自于UAV节点发出的HELLO消息、UAV节点上传邻居信息和控制节点下发流表这三个过程，与OLSR相对应，本文统计OpenFlow协议中流表更新和流表项缺失处理的网络控制开销。

3.2.3 丢包率

丢包率(Packet Loss Rate,PLR)为丢失数据包数量占发送数据包数量的比率，如公式(10)所示：

(10)

式中：PT为源节点发送的数据包个数，PR为目的节点成功接收的数据包个数。

3.3 仿真分析

3.3.1 平均端到端时延

图6所示为平均端到端时延。由图可知，随着节点数量的增多，平均端到端时延逐渐增大。这是因为场景中的节点数更加密集，端到端的跳数越多，场景的范围较小，因此传播时延对平均端到端时延的影响较少。仿真结果表明，在节点数为25时，OpenFlow与OLSR相比时延降低了2.6%，OpenFlow-EARM与OpenFlow相比时延降低了8.3%，主要原因有如下三点：一是OLSR节点在收到没有路由表项的数据包时，节点会丢弃数据包或缓存数据包等待下一次路由表更新后再查表转发，OLSR需要等待至少一个更新周期才能转发数据包，因此带来的时延较大；二是OpenFlow在节点收到没有流表项的数据包时，采用1.2 问题描述(1)中的两种方法，这两种方法主动处理流表项缺失数据包，相比于OLSR的时延更低；三是OpenFlow-EARM机制采用距离估计选择时延最低的转发方式，相比于OpenFlow的较为单一的转发方式，OpenFlow-EARM自适应选择时延最低的方式转发，转发流表项缺失数据包所花费的时间更短，因此平均端到端时延更短。值得注意的是，在节点数量为20时，OpenFlow-EARM相比于OpenFlow时延只降低了3.4%，这是因为距离估计会带来一定的误差，但是从整体来说，OpenFlow-EARM的平均端到端时延低于OpenFlow。

3.3.2 网络控制开销

图7所示为网络控制开销。由图可知，随着节点数的增多网络控制开销逐渐增大。这是因为网络拓扑建立过程需要收集信息的节点数增多。在25节点情况下OpenFlow相比于OLSR控制开销降低了49.6%，主要原因是OLSR协议由于其分布式结构，需要每个节点收集拓扑信息并构建全网拓扑，构建过程中每个节点需要发送HELLO消息建立邻居表和MPR节点广播TC消息，因此随着节点的增加，网络控制开销也急剧增加；OpenFlow由于其集中式控制消除了OLSR协议所使用的泛洪，因此，使用OpenFlow减少了转发的信息，从而减少了网络控制开销。OpenFlow-EARM将处理流表项缺失过程的控制包与UAV节点邻居信息相聚合，虽然聚合的数据包相比于原有的Packet-in多了Position字段，但是减少了控制数据包的发送次数，Packet-in数据包包头所带来的控制开销远大于Position字段，因此OpenFlow-EARM的网络控制开销比OpenFlow低，节点数为25时，相比于OpenFlow，OpenFlow-EARM控制开销只降低了1.3%，其原因是随着节点数的增多，相比于聚合消息减少的网络控制开销，网络中出现节点流表项缺失的情况增多带来的网络控制开销更大，因此节点数量越多，OpenFlow-EARM的网络控制开销越接近OpenFlow的网络控制开销。

图7 网络控制开销

3.3.3 丢包率

图8所示为丢包率。由图可知，随着节点数量的增加，丢包率逐渐增大。这是因为节点数量增多，导致数据消息和控制消息发送的数量增多，从而导致无线信道中碰撞概率的增大。节点数为25时，OpenFlow相比于OLSR丢包率降低了6.4%，其原因是OLSR在数据包没有路由的情况下，UAV节点会将数据包直接丢弃或者等待下一次的更新，然而OpenFlow中数据包没有匹配的流表项会立即向控制节点报告，因此OpenFlow这种主动式的处理过程减少了丢包的概率。节点数为25时，OpenFlow-EARM相比于OpenFlow丢包率降低了2.1%，其原因是邻居信息上传和流表项缺失处理过程是同时进行的，由于OpenFlow-EARM机制采用了消息聚合的方式，降低了两种过程所产生的无线碰撞的概率，因此OpenFlow-EARM的丢包率低于OpenFlow。

图8 丢包率

4 结束语

本文针对目前SD-UANET中流表项缺失处理过程中转发数据包时延高、网络控制开销大和无线碰撞的问题，提出了OpenFlow-EARM机制。新机制根据删除流表项的时刻值和UAV节点最大移动速度估算两种转发流表项缺失数据包所需要的时延，以此来选择时延最低的转发方式，降低了传输数据包的时延，并且在处理流表项缺失的过程中利用消息聚合的方法减少数据包的发送次数，从而减少网络控制开销，然后利用一种周期恢复的策略将邻居信息上传的数据包的发送间隔恢复到原周期。仿真结果表明，OpenFlow-EARM机制在平均端到端时延、网络控制开销和丢包率等方面优于对比的协议。未来的工作将深入研究控制节点与UAV节点之间的控制消息传输问题。