基于决策树的无人机自组网DSR协议

2021-01-22刘庆华黄声培叶金才康一鸣

桂林电子科技大学学报 2020年4期

刘庆华，黄声培，叶金才，康一鸣

(桂林电子科技大学信息与通信学院，广西桂林 541004)

无人机自组网(UAV ad hoc network)[1-2]是一个无中心服务器，以无人机为载体，网络中各节点是对等的临时性网络，自组网节点兼具收发机和路由器的功能。由于单个无人机节点的传输范围有限，当2个无人机节点的距离在传输范围内时，节点可直接进行通信；而当2个无人机节点距离较远，超出传输范围时，需要通过中间节点传递的方式进行远距离通信。相比传统的移动自组网，无人机自组网的拓扑结构变化更迅速。如何在拓扑结构变化迅速的无人机自组网中选取相对较稳定的传输路径是无人机自组网面临的一大难题。

无人机节点能量有限[3-4]，节点能量耗光会导致节点失效，引发通信链路断裂。传输路径失效会重启路由发现过程，重启路由发现将产生大量的路由控制消息，增加传输延迟，进而降低无人机自组网的性能。为了在拓扑结构变化迅速的无人机自组网中探寻得到相对稳定的传输路径，在路由发现时，需将影响无人机节点稳定性的因素，如节点能量消耗、节点移动速率和缓冲区拥塞率等纳入路径选择的考量中。

决策树(decision tree)是一种机器学习算法[5]，将无人机自组网节点的稳定性进行相应的分类，利用决策树思想来优化无人机自组网DSR协议[6]的路径选择过程，提出了一种基于决策树的无人机自组网DSR协议(decision tree DSR，简称DT_DSR)，提高传输路径的稳定性，降低无人机自组网的路由开销。

1 DSR协议

动态源路由(dynamic source routing，简称DSR)协议是经典的按需驱动路由协议[7]，DSR协议不需要通过周期性广播来维护整个网络[8]，该协议有业务发送需求且无缓存有相应的传输路径时，才会探寻从源节点到目的节点的传输路径。相比于表驱动路由协议[9]，DSR协议的路由开销相对较低。DSR协议的路由发现过程主要分为路由请求和路由回复2个部分，路由请求过程如图1所示。

图1 路由请求

源节点S有业务发送需求且无缓存有达到目的节点D的路径时，启动路由发现，向邻居节点(A，B，C)广播路由请求，通过中间节点不断转发传递的方式，从源节点S探寻前往目的节点D的传输路径(S—B—H—D，S—A—F—G—D，S—C—E—I—D)。路由回复过程如图2所示。

图2 路由回复

目的节点D接收到路由请求后，沿着首条抵达的传输路径逆向往源节点S发送路由回复(D—H—B—S)，节点S收到回复后，表明传输路径建立完成，源节点S开始向目的节点D发送业务数据。

2 DT_DSR协议

2.1 DT_DSR思想

由于无人机自组网与传统地面移动自组网区别很大，无人机场景下的自组网拓扑结构变化更快。无人机节点的能量有限且无法及时补充，节点能量耗完会导致节点死亡，进而引起通信链路断裂。传统DSR协议采用最小跳数作为传输路径，而在无人机场景的自组网中，最小跳数策略往往不适用，容易导致传输链路断裂[10]。优化的DSR协议中，选取节点移动速率、节点拥塞率和节点能量消耗3种影响节点稳定性的因素，采用决策树分类思想，将节点的稳定性进行相应的分类，综合选择稳定性较高的节点转发数据。基于决策树的DSR协议总体框架如图3所示。

图3 决策树DSR协议框架

网络节点稳定性的考虑因素包含下列3点：

1)节点缓冲区拥塞率。每个无人机节点均有一个缓冲数据包的缓存区，用来缓存还未来得及发送的数据包，高拥塞的无人机节点往往会导致较高的延迟，且容易丢失数据包，因此，选取低拥塞的节点传输数据更为可靠。节点的拥塞率为

在“互联网+”阅读教育之下，互联网作为载体其容纳空间不再受到实际空间的限制，均以数据形态在网络中展示，此时就改善了传统图书馆中公共容纳性不足的问题。因为“互联网+”阅读教育图书馆改善了公共容纳性不足的问题，所以其可以使大量学生在同一时间内进行阅读，在理论上避免了类似“一人使用，另一人无法使用”的窘境，并在《公共图书馆宣言》中的表述之下，显然“互联网+”阅读教育图书馆更加能够体现出此表述当中的含义。

(1)

其中：Bmax为可缓存最大容量的节点；Bnow为当前缓存的大小。c越大，节点的塞率程度越严重。

2)节点能量消耗率。无人机通常采用能量有限的电池进行供电通信，节点剩余能量直接决定了节点的生存时间，节点能量耗完时，该通信节点随即失效，进而导致通信链路断裂。在路由发现阶段的路径选择过程中，应该尽可能避免能量消耗率大的节点。能量的消耗率表示为

(2)

其中：E0为节点的初始通信总能量；Et为无人机节点发送数据包的能耗；Er为无人机节点接收数据包的能耗。

3)节点速度因子。无人机自组网节点移动速率越快[11]，网络拓扑结构变化越剧烈，选择移动速率相对较小的节点转发数据，可以延长路径的生存时间，提高传输路径的稳定性。节点移动的快慢用速度因子表示，速度因子表示为

(3)

其中：Smax为网络节点最大移动速率；Snow为当前节点的移动速率。

为了区分各属性因素的大小，根据节点缓冲区拥塞率、能量消耗率和速度因子属性的取值范围划分各属性的等级。节点属性值的等级划分如表1所示。

表1 节点属性值的等级划分

2.2 DT_DSR的实现

在DT_DSR协议的路由请求阶段，采用决策树算法计算评估节点的稳定性，依据稳定性的高低决定是否接收和处理路由请求。决策算法用0和1区分节点的稳定性，若决策为0，表示节点不稳定，节点丢弃请求的数据包；若决策为1，表示节点稳定，节点可以接收和处理路由请求。节点收到请求时执行决策算法，通过实施决策机制，避免传输链路中存在不稳定的节点，从而得到稳定的传输路径。

决策算法需要构造决策树，用决策树算法来决定节点是否稳定，采用ID3算法[12]来构造决策树。ID3算法首先计算数据集的熵，数据集的熵计算式为：

(4)

(5)

其中：E(S)为数据集S的信息熵；k为数据集样本类别数；Pi为样本i的概率；EA(S)为属性A的熵；v为数据集属性的个数；Sj为根据属性A划分S的第j个子集；S和Sj均为样本数目。

得到数据集的熵，再计算属性的信息增益，信息增益的表示式为

G(S,A)=E(S)-EA(S)。

(6)

其中，G(S,A)为属性A的信息增益，根据属性信息增益的大小来生成决策树。

根据表1属性等级和决策结果的划分，得到决策算法的训练集，如表2所示。

表2 决策树ID3算法训练集

根据数据集，得到训练结果。结果表明，节点拥塞率的信息增益最高，因此选取拥塞率作为决策树的根节点，接下来是子树。节点收到路由请求时，首先计算拥塞率，若拥塞率等级为高，则说明节点丢失数据包的概率高，因此将请求数据包丢弃；若拥塞率等级为中或低，该节点按照决策算法，进一步遍历其他属性参数，以此类推，最终得到稳定的传输路径。

3 仿真与结果分析

3.1 仿真测试

采用OPNET Modeler 14.5[13]网络仿真工具，模拟具体通信过程。其仿真参数如下：

1)无人机自组网部署区域为5 000 m×5 000 m，网络节点数为30个，节点随机分布在部署面积内，各节点的运动模型选择Random Waypoint[14]，节点的移动速率为1～10 m/s；

2)通信连接数为4条单向数据流，采用连续比特率(CBR)来模拟产生的数据包，包大小为1 024 bit，发包间隔为0.2 s；

3)节点初始能量E0设为40 J，接收单个1 024 bit数据包消耗0.006 3 J，发送单个1 024 bit数据包消耗0.008 5 J，仿真时长为10 min。

将传统的DSR协议与优化后的DT_DSR协议进行仿真，对比网络的端到端延迟、业务数据的接收速率和路由开销。

3.2 结果分析

根据OPNET仿真工具记录的统计数据，得到如图4所示的平均端到端时延结果。

图4 平均端到端时延

图4的仿真结果表明，由于选取了较稳定的节点转发数据，提高了传输链路的稳定性，传输链路不易断裂，无人机场景下，优化后的DT_DSR协议减少了端到端时延。统计结果显示，DT_DSR的平均端到端时延比原DSR协议降低了26.99%。

图5为业务数据接收速率的仿真结果。从图5可看出，在相同的发送速率下，DT_DSR协议的业务数据接收速率更高，由于传输链路稳定性较差，DSR协议的业务数据接收速率明显小于DT_DSR。结果表明，DT_DSR的业务数据接收速率比DSR协议提高了17.42%。

图5 业务数据接收速率

图6为路由数据发送速率。从图6可看出，DT_DSR的路由数据发送速率总体要低于DSR，统计结果显示，DT_DSR的路由数据发送速率比DSR减少了13.62%。图7为路由数据接收速率。从图7可看出，由于减少了不必要的洪泛，提高了路由发现的效率，DT_DSR的路由数据接收速率比DSR减少了15.25%。综上所述，相比于DSR协议，DT_DSR协议的路由开销更低。