无人机系统编队分簇网络仿真研究

徐意祥，李莉

（北京航空航天大学自动化科学与电气工程学院，北京100191）

无人机编队飞行与协同通信，是当前无人机编队的热门研究课题[1-3]。无人机可以用于军事作战，电子侦查，通信中继，还可以用于民用。无人机群的突出作用，在于利用无人机的数量优势，在各种工作场景中发挥协同的作用。因此协同控制好无人机编队，提高无人机编队的使用效率，就显得十分重要。无人机编队自主重构是为了按照需要，快速组成给定编队队形[4-6]；无人机分簇算法，是为了在无人机编队的基础上，为了提高无人机群的相互通信效率。

无人机外出执勤远离路基基站人员控制，因此需要无人机群具有一定的智能性。目前传统编队算法在无人机的队形重构上还不够智能化，也不够快速，同时无人机编队的协同通信的效率还不够高。因此需要设计算法，完成无人机自主重构[7-10]，并且提高无人机之间的协同通信效率。

通过在Linux系统上使用NS3仿真软件[11-13]，首先设计无人机类，配置无人机间的通信协议，设置无人机节点数量，配置仿真环境。然后设计鱼群算法实现无人机编队的快速自主重构，同时采用HEED分簇算法实现无人机群分簇[14-17]。

该仿真暂设定无人机数量9架。只需要给定队形，无人机就可以自动实现队形的快速自主重构。同时按照设计的HEED算法实现分簇，提高无人机的协同通信效率。该系统仿真证明，算法智能性好，编队自主重构快速，通信效率提高，容易调整维护，适应性强，鲁棒性强，能很好地解决无人机编队重构和协同通信的问题[18-21]。因此，笔者采用的鱼群算法和HEED分簇算法进行无人机系统仿真设计。

1 系统设计

1.1 仿真环境设计

无人机群由多个无人机组成。鱼群算法的关键在于：一是搜索目标位置，这需要通信协议的支持，保持无人机间的通信顺畅。而通信是三维空间的，不是平面上的。因此只要能够实现无人机间的通信，在搜索目标位置的问题上，只需要确定初选簇头节点，经过正方形编队队形的位置计算，就可以完成目标位置的搜索；二是簇头节点的竞争与选取，选取标准是无人机节点的自由度和无人机的能量参数，而无人机的自由度这一参数的确定是在通信范围内确定的一个半径r内的节点数量，同样是取决于通信，上述已经说明通信本身就是在三维空间实现；三是无人机的运动与重构，然而本课题不涉及飞控算法的研究，因此只需要确定无人机的重构算法是按照鱼群算法重构，但是至于在三维空间如何运动属于飞控研究课题，不在本文研究范围内，因此在搜索到目标位置以后，就是按照鱼群算法朝目标位置移动的过程，而且是在运动过程中继续搜索更好目标位置。

因为本课题不涉及无人机的飞控算法，在满足无人机群的编队任务需求下，对上述鱼群算法，HEED分簇算法以及混合路由协议进行仿真验证。在复杂作战任务情况下，加入飞控算法可以满足实际三维空间飞机飞行需求，同时无人机间的通信也是三维的立体的，而鱼群算法和HEED分簇算法是对编队自主重构算法和提高通信效率的设计，实际过程的重构是鱼群算法配合飞控算法完成自主重构，对三位空间和二维空间都适用，鱼群算法和HEED分簇算法的相关参数不涉及三维坐标，只和无人机节点自由度以及无人机能量有关。因此鱼群算法和HEED分簇算法在二维空间仿真也是满足研究课题需求的。故本文采用了二维空间的仿真。

1.2 无人机模型

建立单个无人机模型，根据仿真需求，完成无人机编队自主重构，分簇，实现无人机间的通信。无人机模型的主要参数有：无人机在仿真环境中的位置，无人机移动速度，无人机移动方向，无人机是否是簇头节点，以及无人机的簇群成员，无人机视野，拥挤因子，无人机最大步长，无人机行为模式，邻居通信节点的MAC地址，以及通信路由表等参数。

2 算法设计

2.1 鱼群算法自主重构

无人机群在执勤作业过程中，面对不同的任务需求和障碍，适当改变编队队形，对提高无人机编队的生存率和工作效率，是十分必要的。

仿真过程开始，无人机群随机设定初始化为三角形初始队形如图1所示是在matlab中显示的随机初始化的无人机队形，为三角形。

图1 初始无人机队形

目标队形正方形在NS3的可视化界面下仿真如图2所示。首先按照分簇算法选定簇头节点无人机，并规定该无人机按照圆形轨迹运动，其他无人机按照鱼群算法自主重构逐渐形成编队，并且最终按照圆形轨迹巡航。

图2 正方形目标队形

首先无人机群确定几何中心附近无人机节点(x0,y0)，以该无人机为正方形中心，在空间中模拟一个正方形网格，网格交叉点就是各个无人机节点最终的目标位置，并给目标位置编号(l0,l1,......,l8)，对应位置(x0,y0)，(x1,y1)……(x8,y8)。

以无人机的视野为半径r的各个目标(l0,l1,......,l8)位置周围，统计无人机节点数量nx。数量nx的大小作为目标位置周围的无人机节点的密度。鱼群算法自主重构流程图如图3所示。

图3 鱼群算法自主重构流程图

无人机节点寻找视野范围内的目标位置lx，并得到目标位置lx的无人机浓度nx。无人机节点按照步长p移动，方向是浓度最低的目标位置lx。

无人机节点准确来到目标位置lx，完成该位置的自主重构。其他剩余位置以此类推。

整个算法中，首先以其中一个无人机为参照点，该无人机作圆形轨迹的巡航运动。以该无人机为中心，计算出正方形的队形的所有空位置，作为目标位置。其他无人机在搜索过程中，计算目标位置无人机浓度，并选择目标位置，按照步长移动，直至到达目标位置为止。寻找目标位置是鱼群的觅食过程，而计算目标位置浓度是为了避免鱼群的追尾行为。

2.2 无人机编队HEED分簇算法

HEED是无线传感网的一种多跳分簇算法，簇头选取考虑两项重要参数：剩余能量和簇间通信开销。HEED在选取簇头时都考虑节点剩余能量，但是簇间通信开销反应了节点和邻居节点的距离和节点自由度，同时还被用作决定节点是否加入分簇的参考指标。低能量的簇群会从新限定通信范围，而高能量的簇群则扩大通信范围，覆盖更多的簇群。HEED算法为网络提供统一的簇头分布和更好的负载平衡。HEED算法是一个分布式分簇算法，簇头节点从分散的传感网络中选取。HEED综合考虑了节点剩余能量和簇间通信开销，不像LEACH随机选出簇头节点。在HEED算法中，节点被唯一映射到一个簇群中，并且可以直接和簇头通信。但是该算法在选取簇头时，节点多次重复发送数据直到找到最小通信能耗的节点作为自己的簇头，否则选自己为簇头。这样势必带来一定的通信开销和能量损耗。

仿真采用改进的HEED算法，在选择簇头时，依据能量、节点自由度，采取竞争机制选取簇头。其余节点依照改进的分簇算法选择合适的簇头节点请求加入。完成分簇。具体设计过程如下：

首先依照节点剩余能量Ei'和节点自由度mi，统计候选簇头节点；

剩余能量计算公式：Ei'=Ei-Et-qi·X-qi'·t，其中Ei为无人机i的初始能量，Et是利用NS3软件的能量模块统计处的通信能耗，qi是无人机的单位距离飞行能耗，X为飞行路程，qi'是无人机i的单位时间巡航能耗，t为巡航时间。

以平均无人机编队的能量分布和负载均衡为考量，在无人机编队中选出剩余能量最多Ei和自由度最高mi的无人机节点作为簇头节点Ci；

选择簇头的标准：gi=λ1·mi+λ2·Ei

簇头的参数指标gimax当选簇头，其中λ1和λ2为常系数。

没有当选簇头节点的节点以到簇头节点的距离di、簇群节点数量nc为参考，选择最优的簇头，并申请加入该簇群；

所有的无人机节点作为簇头或者普通成员节点，完成分簇；如果触发了重新分簇的条件，比如簇头节点能量过低或者通信阻塞，则在簇内重新选择簇头，替代原有簇头；如果编队重组，则触发簇头竞争机制，回到第一步重新分簇。无人机群的HEED分簇算法流程如图4所示。

2.3 无人机编队路由算法

整个仿真中路由协议的算法是贯穿整个无人机网络协调通信与交互信息的关键。路由的算法主要分为路径发现模块，路径维护模块，路径选择模块3部分，同时主要分为编队之前和分簇之后的两个阶段。在编队之前主要是路由形成过程，需要动态路由算法，在完成分簇之后，编队自主重构也完成了，这是就会进行路由维护，需要静态路由算法。

图4 HEED分簇算法流程图

路径发现模块调整了无人机节点对PREQ和PREP帧的处理方法，从信号帧中提取无人机节点的位置信息，是否有簇头标志，无人机的自由度，无人机的MAC地址等，并配合自主重构算法和HEED分簇算法完成通信及分簇的必要通信，并产生无人机节点间通信的路由路径，同时保存到路由表中，在路由表中按照编号产生路由表。路径发现模块是路由算法的核心模块。

路径维护模块负责维护已经生成的并且编队稳定的路由表。路由表的每条路径都有一定的生存时间，当编队自主重构触发或者分簇算法触发之后，会重新回到路由发现模块，并且重新产生新的路由表，删除旧的路由表。在维护路由表过程中，每一个节点都会保存一条到达簇头的路由表，而簇头节点则会保存到达每一个普通节点的路由表。当某个节点失效时，路径上的节点收到通知后删除该包含节点的路由。

路径选择模块则是在同时可用多条路径时，为无人机节点选择路径最短通信最不拥堵的路径，并将该路径设为主路径，其他路径按照同样的标准按照序号备份。主路径失效后或者不是最优，按照序号选择备份路径，并取代主路径。如果节点之间跳数过多超过2跳时，则会选择跳数最少的路径，通常是找簇头节点，由簇头节点充当中间节点。否则跳数小于等于两跳时，会选择路径最短的路径。

AODV和OLSR混合路由建立过程是为了建立无人机节点间的多条通信路由，具体步骤如下：

源节点启动路由发现机制，查找AODV路由表，看看是否存在目标节点的路由信息。在形成编队自主重构和完成分簇后，通常直接选择选择路径Metric值最小的主路径进行通信。在编队过程中，没有目标节点的稳定路径，需要启动路由发现过程。源节点构造Improved PREQ帧，并在网络中广播Improved PREQ帧。AODV协议原来的路由信息表包括下一个目的节点的MAC地址、目的节点的MAC地址、发现重试次数以及路径状态标志FLAGS、路径空时链路METRIC值、目的节点序列号SN、路由发现过程超时的时间、路由信息表过期时间；改进的路由协议新增了第一跳邻居节点的MAC地址，用于记录距离目标节点只有一跳的邻居节点MAC地址。

中间节点处理Improved PREQ帧，接收一个新的PREQ帧，按照OLSR协议的算法，决定是否更新到源节点的路由，并判断是否继续转发该帧。如果路由表没有这条路径，就新建一条路径，否则查看所收到的PREQ帧中源节点的序列号及Metric值，再判断要不要更新路由表和继续转发该帧信号；如果本节点是目的节点，则不用转发，否则继续转发。目的节点可能收到多个来自同相同源节点的PREQ帧，根据路由表的相关更新算法，判断最优路径，丢掉非最优路径。

目的节点收到转发过来的PREQ帧时，根据路由算法，判断是否更新路由，并向源节点发送PREP帧回复。

中间节点收到来自目的节点的PREP帧，按照之前保存的最优路径转发PREP给源节点。

源节点收到目的节点的PREP帧后，在路由表中保存路径，便完成了路由发现和保存过程。该混合路由算法流程如图5所示。

3 仿真验证

图6是无人机群以簇头无人机为中心，按照圆形轨迹运动，其余无人机节点按照鱼群算法完成编队自主重构，形成的运动轨迹，该轨迹是在MATLAB下仿真得出的运动轨迹效果图。最终无人机群基本完成圆形运动，轨迹图显示编队的自主重构效果良好。在自主重构运动过程中，预定位置是以簇头为中心的正方形网格的几个点。

图7描述的是无人机节点与各自目标位置的距离误差。虽然距离误差有些波动，但是最终程收敛状态。说明鱼群算法在自主重构中的效果良好，并且收敛速度快。

图5 路由算法流程图

图6 无人机群自主重构过程运动轨迹

图7 无人机队形预定位置误差

图8显示的是无人机群在完成自主重构以后，形成的编队状态。黑色边缘线节点是簇头节点，是初始状态下按照HEED分簇算法选取的无人机簇头节点。

图8 簇头初始选择

当自主重构完成以后，分簇效果如图8显示选出的簇头并不是最佳，而分簇算法在完成编队以后会重新触发竞争簇头节点，中间节点是竞争之后选取的新节点。图9中显示该簇头的自由度最高，通信效率有所提升。说明HEED分簇算法良好。

图10显示无人机群完成编队的自主重构，并且完成簇头重新竞争之后的整个仿真效果图，图中显示无人机群间的通信正常，并且以中间的簇头节点无人机为中心，无人机间的通信效率有所提高，没有发生通信阻塞情况。

4 结 论

无人机群采用鱼群算法完成自主重构正常，无人机群在给定编队队形情况下能够快速自主重构，完成编队工作，收敛正常，无人机仿真飞行运动正常；分簇功能正常，分簇可以通过图形界面形象展示簇群分布，可以通过图形如圆形划分标示簇群，更直观反应簇的分布和簇内节点成员；分簇算法运行正常，簇头选取正常，无人机节点可以正常请求离开和加入簇群；簇头竞争机制正常，簇间通信良好；从生成仿真环境，开始运行仿真，采用反应路由和按需路由混合的路由协议实现无人机群通信正常，通信稳定；完成编队自主重构和分簇过程中，通信协议能够有效为无人机群的协同提供良好的通信服务；完成分簇后和之前，通信协议的工作模式可以正常切换，通信效率提升，无人机节点通信负载减轻。

图9 簇头竞争选择

图10 无人机编队的通信仿真