适用于集群无人机自组网的路由协议研究及仿真

第39卷第3期遥测遥控Vol.39,No.32018年5月JournalofTelemetry,TrackingandCommandMay2018*基金项目：装备预研航天科技基金收稿日期：2017-12-22收修改稿日期：2018-01-23适用于集群无人机自组网的路由协议研究及仿真*崔朝阳，孙甲琦，徐松艳，蒋鑫（北京遥测技术研究所北京100076）摘要：集群无人机利用自组网技术可以实现无人机之间信息的高速共享，以自主化和智能化的方式协同完成作战任务，极大地提高作战效能。针对集群无人机网络节点数量多、拓扑结构变化快的特点，提出一种基于簇结构的、地理信息辅助的自组网路由协议（GACB），通过对基于权值的分簇算法（WCA）进行改进，提高了簇结构的稳定性，引入地理位置辅助的贪婪转发方式，减小了簇结构网络的路由开销。仿真结果表明，与传统的CBRP协议和AODV协议相比，GACB协议的控制开销分别降低了约30%和50%，分组投递率分别提高了约10%和15%，路径断裂次数分别降低了约60%和70%，端到端时延分别缩短了约2ms和1ms。关键词：集群无人机；自组网；路由协议；分簇算法中图分类号：TP393文献标识码：A文章编号：CN11-1780(2018)03-0029-06ResearchandSimulationofAdHocRoutingProtocolforColonyUAVsCuiZhaoyang,SunJiaqi,XuSongyan,JiangXinBeijingResearchInstituteofTelemetry,Beijing100076,ChinaAbstract:Unmannedaerialvehiclescanshareinformationandcooperatetocompletecombatmissionthroughtheadhoctechnology,whichimprovestheoperationaleffectivenessgreatly.AccordingtothecharacteristicsofcolonyUAVsadhocnetworkthispaperproposesaGeographicAssistedClusterBased(GACB)routingprotocol,whichimprovestheweightedclusteringalgorithmtoincreasethestabilityofnetworkandintroducesthelocationinformationtoreducetheroutingcontroloverhead.SimulationresultsshowthatcomparedwiththeCBRPandAODVprotocolsthecontroloverheadofGACBprotocoldecreases30%and50%respectivelythepacketdeliveryratioincreases10%and15%therouterepairtimesdecrease60%and70%andtheaverageend-to-enddelaydecreases2msand1ms.Keywords:ColonyUAVs;Adhoc;Routingprotocol;Clusteringalgorithm引言自组网具有无中心、多跳传输、抗毁性强、可快速展开的特点，是集群无人机网络首选的通信模式。在自组网中，路由协议的作用是为任意有通信需求的节点建立有效的通信路径。到目前为止，针对移动自组网已经出现了许多基于不同策略的路由协议，如基于平面结构的AODV（AdhocOn-demandDistanceVector）路由协议、DSR（DynamicSourceRouting）路由协议和基于簇结构的CBRP（ClusterBasedRoutingProtocol）路由协议、CGSR（ClusterheadGatewaySwitchRouting）路由协议等，但它们都不适用于节点数量多、相对移动速度快、节点资源有限的集群无人机网络[1]。本文提出一种适用于集群无人机网络的自组网路由协议——GACB（GeographicAssistedClusterBased）。该协议由分簇机制和路由机制两部分组成，分簇机制使用了改进的WCA（WeightedClusteringAlgorithm）算法，综合考虑了节点的剩余能量、相对移动性、相对节点度和丢包率等用于选举簇首的因素，能够防止丢包率较高的节点被选为簇首，提高了簇结构的稳定性；在路由机制中引入地理位置信息作辅助，优先将路由发现消息转发给距离目的节点昀近的簇首或网关，一方面可以避免路由控制Email:[e-mail]:010-68382327010-6838255730崔朝阳等，适用于集群无人机自组网的路由协议研究及仿真第39卷第3期包的反向传输，降低路由控制开销，另一方面有利于发现昀短路径，缩短端到端时延。通过OPNET网络仿真工具对GACB、CBRP和AODV三种路由协议进行了性能比较，证明了在多节点、高动态网络环境下，GACB路由协议能够获得更好的性能。1集群无人机网络总体结构根据所选择的逻辑拓扑结构形式，自组网路由协议可以分为平面型和分簇型两类。与平面结构相比，分簇结构可扩充性好，网络规模不受限制，可以有效降低路由控制消息带来的网络开销，且更容易实现对高动态性网络的管理，因此分簇的网络结构更适合集群无人机网络[2,3]。如图1所示，分簇的网络结构中，网络由簇首、簇成员和网关三种类型的节点组成，簇首负责本簇成员的管理，网关负责邻接簇之间的通信，簇首和网关组成虚拟骨干网，网络中所有的成员节点都通过虚拟骨干网相互连接。图1分簇网络结构Fig.1Clusteringnetworkarchitecture2GACB路由协议本文设计的GACB协议是一种基于簇结构的、地理信息辅助的路由协议，它可以分为分簇机制和路由机制两部分。分簇机制用于网络簇结构的形成和维护，路由机制用于为有通信需求的节点建立通信链路[4]。2.1分簇机制分簇的目的是将节点对等的、完全无组织的网络划分出层次，使得网络拓扑结构改变后，能够通过分簇管理有效地实现快速配置、动态网络重构。采用适当的分簇算法构造分层的路由是解决网络可扩展性和拓扑结构变化快等问题的重要途径。分簇机制由簇构成和簇维护两部分组成。2.1.1簇构成簇构成阶段主要是通过有效的分簇算法，将网络划分成簇。常用的分簇算法有昀小ID（Lowest-ID）算法、昀大连接度（Highest-degree）算法、基于节点移动性的分簇算法（MOBIC）和基于权值的分簇算法（WCA）等，其中WCA算法综合考虑了节点的连接度、移动速度、能源消耗等多种因素，选择出的簇首相对更合理，网络拓扑结构更稳定[5]。集群无人机网络中，由于节点之间相对移动速度快、拓扑结构变化频繁，导致节点丢包率明显增加，为此本文对WCA算法进行了改进。改进的分簇算法将节点的连接度、剩余能量、相对移动速度和丢包率四种因素作为簇首选择的依据，计算每个节点的权值，选择权值大的节点作为簇首。WCA算法考虑的是节点移动速度，而无人机节点移动速度都比较大，因此本文考虑节点与周围其他节点间的相对移动速度。簇首在网络中有着重要地位，簇首的表现对网络整体性能的影响较大，为了防止自私节点或恶意丢包节点被选作簇首，本文将节点丢包率也作为簇首选举的因素之一。节点vi的权值计算方法如下：2018年5月遥测遥控311234····viviviviviWwDwEwVwR1123412其中，1,2,3,4()iwi是每种因素的比重。关于比重值的选取，目前没有简洁高效的方法，一般是通过大量试验寻找出昀优结果的方式确定。viW表示节点的权值，viD表示节点的连接度，viE表示节点的剩余能量，viV表示节点的相对移动速度，viR表示节点的丢包率。簇构成的过程在网络初始化时进行。首先，节点周期性地广播HELLO消息，一方面用于向周围节点声明自己的存在，另一方面通过收集HELLO消息获取邻居节点的信息，用于簇结构的形成；然后，通过收集到的邻居节点的信息，计算邻居节点和自身节点的权值，优先选择权值大的节点作为簇首，如果权值相同，则选择ID小的节点作为簇首；随后，被选为簇首的节点广播HELLO消息，未被选举为簇首的节点等待接收簇首的HELLO消息，如果收到簇首的HELLO消息，则加入该簇，否则自己成为簇首[3]。2.1.2簇维护自组网的拓扑结构在不断地变化，有效的成簇机制要能够在网络拓扑结构动态变化的情况下维护簇结构的稳定。簇维护主要有如下几种情况：①新节点的加入：欲加入网络的节点要能够侦听到簇首广播的HELLO消息，并且新加入的节点不会挑战现有簇首的地位，即使其具有较大的权值。②旧节点的退出：成员节点的退出对网络影响较小，但如果是簇首节点退出网络，则会引发网络局部区域的簇首选举事件，因此，簇首节点在正常退出网络前，应指定一个节点接替簇首，并广播给本簇成员，昀大限度地减少网络重构引起的控制开销。③节点的移动：成员节点移动到其它簇，则加入该簇；簇首节点移动到其它簇，则需要进行簇首竞争，权值大的节点继续作为簇首，权值较小的节点成为簇成员加入该簇。2.2路由机制本文路由机制是基于按需路由的，即当有通信需求时才建立通信路径，它由路由发现和路由维护两个阶段组成。2.2.1路由发现路由发现用于为源节点和目的节点建立一条可靠的端到端通信路径。传统的基于簇结构的路由发现过程一般是源节点S将路由请求（RREQ）消息单播给本簇的簇首，由该簇首将消息通过虚拟骨干网广播给所有的簇首和网关节点，通过簇首和网关节点寻找目的节点D。与平面结构相比，该方式能够避免路由控制消息在网络中泛洪，很大程度上降低了路由控制开销，节省了网络带宽。随着无人机技术的发展，大多数无人机节点都配备了GPS等地理位置服务系统，这就使得基于地理位置信息的路由发现成为可能[6,7]。本文设计的地理位置信息辅助的路由发现分为路由请求和路由回复两个过程，能够有效减小簇结构网络的路由开销。①路由请求当源节点S需要建立与目的节点D的通信时，它首先在本地路由表中查找是否存在到D的有效路由，如果本地路由表中不存在或路由已过期，则需向网络中发送路由请求消息RREQ，而收到RREQ消息的节点都将建立到源节点S的路由。在该过程中，RREQ消息有两种转发方式：贪婪转发和广播转发。在贪婪转发方式中，源节点S生成RREQ消息，并将消息转发给本簇的簇首；簇首收到后，将该消息转发给距离目的节点D昀近的网关节点；同样，网关节点收到后，转发给距离D昀近的簇首，直到RREQ到达D所在的簇后，由该簇的簇首转发给D。而在广播转发方式中，簇首将RREQ转发给本簇所有的网关节点；网关节点收到后，将RREQ转发给所有与之相连的簇首，造成了RREQ在虚32崔朝阳等，适用于集群无人机自组网的路由协议研究及仿真第39卷第3期拟骨干网中泛洪。因此，在路由请求过程中，优先选用贪婪转发的方式进行路由发现，如果一段时间后S没有收到路由回复消息RREP，则认为此次贪婪转发方式路由发现过程失败，在重新进行路由发现过程时，改用广播转发方式。如图2，贪婪转发方式能够避免RREQ在虚拟骨干网中泛洪，大幅度减少路由请求过程中的控制开销，在贪婪转发方式中，RREQ只需沿昀短路径S-C1-G1-C2-D即可发现到目的节点的路径。但当C2与D之间的链路不存在时，贪婪转发方式就会失败，此时使用广播转发的方式再次进行路由发现过程，如图3所示。集群无人机网络一般节点密度较大，使用贪婪转发方式进行路由发现失败的几率较小。图2贪婪转发方式Fig.2Greedyforwarding图3广播转发方式Fig.3Broadcastforwarding②路由回复当目的节点收到源节点的RREQ消息或中间节点收到RREQ消息并具有到目的节点的路由时，沿反向路径向源节点回