无人平台移动网络分簇研究

刘邈

【摘要】 无人平台集群移动网络较多呈现分布式、无中心以及网络成员数较多、动态性较强等特点，为有效确保网络运行性能，大规模的无人平台集群移动网络维护管理常利用分区域管理模式。此外，在实际应用中，无人平台集群移动网络常会遭遇由于电磁环境、干扰等因素导致的通信质量不稳定变化。因此，本文采用引入节点通信质量的网络加权分簇算法，其通过计算各相关因素的权值并根据最终得到的总权值确定簇头节点，进而完成网络的分簇。

【关键词】 网络分簇 通信质量 网络拓扑

Research of Cluster-constructing for Unmanned Platforms Mobi Network Liu Miao （Southwest China Institute of Electronic Technology， Chengdu 610036）

Abstract： There are characteristics in the Mobi Network for unmanned swarming platforms： no-centered， distributed， large amount of nodes， and more dynamic. The Mobi Network which has a large scale of nodes is managed via zoning， in order to ensure network performances. In addition， in actual use， the communication quality of the network is probably instable due to the complex electromagnetic environment or the jamming and so on. So cluster constructing algorithm based on communication quality and authoritys is discussed in this thesis. The algorithm calculates authoritys of elements， and identifies the cluster head according to the result of the authoritys sum. On this basis， cluster constructing of the network is done.

Key words： Network Clustering； Communication Quality； Network Topology；

一、引言

无人平台集群移动网络的应用越来越广泛，包括：无控制中心的分布式军事通信、无人移动平台传感器网络，以及难以部署基础设施的应急网络通信等，网络较多地呈现分布式、无中心以及网络成员数较多、动态性较强等特点，高效的网络维护管理非常重要。为有效确保网络运行性能，大规模的无人平台集群移动网络维护管理常利用分区域管理模式。因此，就必须有相应措施对网络成员进行分簇，并对分簇网络结构进行维护[1]。

此外，在实际应用中，无人平台集群移动网络常会遭遇由于电磁环境、干扰等因素导致的通信质量不稳定变化。因此，本文采用引入节点通信质量的网络加权分簇算法（Communication Quality Authority Clustering Algorithm，CQACA），将包括节点度、节点通信质量、节点移动性等在内的各相关因素赋以不同权值，根据最终所求得的总权值选取总权值最小的节点作为簇头节点，完成网络的分簇。

二、无人平台集群移动网络特点

无人平台集群移动网络根据节点成员的层次情况将形成以下典型拓扑结构：①平面结构：节点的身份角色并无特殊区分——网络中没有专门的控制管理节点；②分簇结构：在网络成员数较多、规模较大情况下使用，节点在网络中的身份角色分为：簇头节点和普通节点；③Mesh结构：约束了网络中节点的路由规模，一般情况下节点仅与其邻节点通信，该拓扑与平面结构较类似。上述几类典型拓扑结构如图1所示。

无人平台集群移动网络作为一种典型的移动Ad hoc网络（MANET），其体现出以下特点：①分布式、无中心；②突出的拓扑动态性；③无线信道将由多跳节点共享；④節点能量受限；⑤带宽受限；⑥数据业务为主；⑦建立运行灵活。此外，由于无人平台集群移动网络在较多应用条件下，常会遭遇由于电磁环境、干扰等因素导致的通信质量不稳定变化，因此对于部分对网络节点间的通信质量较为敏感的应用，保持网络节点间通信质量稳定、可靠在网络的分簇、维护管理中就较为重要。在网络分簇维护管理过程中，需要针对性地考虑上述特点对网络分簇维护管理机制的影响，而不宜直接采用通常的无线网络分簇维护管理算法、策略。

三、网络拓扑与分簇

无人平台集群的移动Ad hoc网络（MANET）在规模较大条件下，网络拓扑的构建将不可避免地面临开销较大、收敛较慢、路由不够稳定等问题。因此，网络维护管理将采取层次化的分布式方法以便提高网络运行效能：在不同的区域中选出各自的簇首节点，其将是本簇中唯一与其他簇外节点通信的节点，网络通信基干就将由簇首节点动态构成，其将负责数据的中继转发等职责。对于簇首节点的选择，其数目与簇内普通节点数应该保持协调，也即是说对于分簇算法，其所形成的簇所包含的节点既不宜太多、也不宜过少。研究发现，采用三层的层次结构将是一个较好的平衡策略[2]。

移动Ad hoc网络的网络拓扑从层次关系上看包括以下两种大的类别：节点随机扁平分布方式、分层分布方式。常用的典型Ad hoc网络其拓扑以节点随机扁平分布方式居多；较多应用于军事应用战场环境的无人平台集群移动Ad hoc网络会较多地形成分层分布式网络拓扑，这是受到部队作战指挥层次化特点影响导致的。典型的分层分布式Ad hoc网络拓扑如图2所示。

四、引入节点通信质量的网络加权分簇算法

4.1总体思路

根据无人平台集群的移动Ad hoc网络（MANET）的应用需求特点，包括：确保网络节点间的连通性，确保网络成员间对通信质量敏感的信息可靠传输，不难看出对该类网络设计网络分簇算法应当考虑下述因素：网络连通性、传输可靠性、分簇稳定性及负载均衡性等。因此，本文所提出的网络分簇算法将基于虚拟骨干网节点、引入节点通信质量按照网络加权分簇的策略实施，其思路如下：

首先，网络节点通过监听其可达范围内的邻居节点通信获取其两跳范围内的节点情况；其次，按照应用需求确定的初始节点将发送构建网络分簇请求，消息的发送对象是网络拓扑维护算法确定的虚拟网络骨干节点（即最小主控集节点），骨干节点在接收到构建分簇请求后将对其做出响应。然后，初始发送节点收到响应信息后，将根据其所获取的骨干节点及其邻节点情况，构建本分簇的拓扑结构。算法实施过程中，既应满足网络的全网连通性也应控制虚拟网络骨干节点规模，既应有所侧重满足某方面重点需求又应使系统整体性能达到均衡，节点通信质量、节点覆盖度、节点移动性、节点剩余能量、邻节点距离等都将成为影响网络分簇的因素。

4.2考虑节点通信质量的加权分簇

2002年Chatterjee提出的加权分簇算法 [3]中心思想为：综合考虑节点移动情况、节点覆盖度、节点能耗及邻节点距离等各因素，按照不同应用需求为上述因素分配不同权值，来描述其按照该应用要求在网络分簇中所起作用的重要程度。

无人平台集群的移动Ad hoc网络应用有较高的信息可靠传输需求，其对节点通信质量较为敏感，因此，本文提出一种引入节点通信质量的网络加权分簇算法（Communication Quality Authority Clustering Algorithm，CQACA）。在本算法中，节点通信质量、节点覆盖度、节点剩余能量、邻节点距离、节点移动性等因素各类因素将被赋予不同权值，根据无人平台集群的移动Ad hoc网络应用需求特点，节点通信质量将赋以较高的权值。本算法还在节点移动性、与邻节点距离两项上进行了改进：①节点移动性：采用由节点y相对其邻节点的平均移动速度替换原算法中的节点y自身的绝对平均移动速度；②与邻节点距离：采用由节点y相对其邻节点的平均距离替换原算法中的节点y与其邻节点的距离和。最终，选取所求得总权值最小的节点作为簇头节点。算法具体过程如下：

首先，对节点通信质量NodeComQuay进行定义，具体如下：

假设节点y到其n个邻居节点的丢包率分别为e1，e2，…，en，在网络运行过程中，丢包率ei=（1-C/（c2-c1））*100%。其中：ΔT时间段内，收端节点实际收到的数据包数为：C；ΔT时间段起始时刻t1收端收到的数据包序列号为：c1；终止时刻t2收端收到的数据包序列号为：c2。节点y的邻节点ri成功接收到其发送的消息时节点y所需发送的次数为：随机变量Xi；n个邻节点都成功接收到其发送的消息时，节点y所需发送的次数为：随机变量Y，那么：

网络运行过程中，网络节点到其邻居节点的链路丢包率ei能够通过周期交互的网络维护类消息获得。节点y按照上述定义将获得节点通信质量NodeComQuay，并实时更新。NodeComQuay值越小，表示节点y在网络中的通信质量越好。CQACA网络加权分簇算法将利用该实时更新的节点通信质量NodeComQuay，簇头节点则根据算法的计算结果确定。

以下将描述引入节点通信质量的网络加权分簇算法（CQACA）：

1）计算节点y的覆盖度：

①Δdegry：节点y与网络中最优覆盖度的差距，该值越小则y的覆盖度越接近最优覆盖度，即：节点y的覆盖能力越好；

②Distany：节点y相对其邻居节点的平均距离，该值越小则y距其邻节点越近，从而可能获得更好的通信质量或链路余量；

③Mobiy：节点y相对于其邻节点的相对平均速度，该值越小则y相对其邻节点的移动性越弱；

④Powy：节点y的剩余能量，Powy值越小则y剩余能量越多；

⑤NodeComQuay：节点通信质量，NodeComQuay值越小表示節点y的通信质量越好；

按照不同应用需求，上述公式中各部分因子的权值也将不同。在无人平台集群的移动Ad hoc网络的组网应用中，由于应用有较高的信息可靠传输需求且其对节点通信质量较为敏感，因此节点通信质量NodeComQuay将占有较大的权重。

根据网络分簇算法簇头选取总权值计算公式，不难看出：总权值Authorityy与各部分权值呈线性关系单调递减关系。因此，最终将选取总权值Authorityy最小的节点，作为簇首节点。

8）网络成员节点加入簇中

Ch表示所选择的簇头节点集合，如果簇头节点y覆盖度小于最优覆盖度（degry≤σ），那么y向所有邻居节点发送簇头通报消息；如果簇头节点y覆盖度大于最优覆盖度（degry>σ），那么y的所有邻节点均计算处理：A（i，y）adapt=a 2*Distany+a3*Mobiy+a5*NodeComQuay，其表示网络成员节点i加入以节点y为簇头的簇的合适程度，其中：A（i，y）adapt值越小节点i越适合加入以节点y为簇头的簇。节点y在对其全部邻节点的A（i，y）adapt做对比后选择A（i，y）adapt最小的σ-1个邻居节点，向其发送簇头通报消息。

節点y的邻节点在接收簇头通报消息后将做以下处理：首先设置一个定时器；在定时器有效时间段内若成员节点仅收到单独一条簇头通报消息，则向其回传簇头通报应答消息，并加入该簇；如果在定时器有效时间段内成员节点收到多条簇头通报消息，那么该成员节点将对每个向其发送消息的簇头节点计算A（i，x）adapt，并向所得A（i，x）adapt最小的簇头节点发送簇头通报应答消息，并加入该簇；

9）还未加入到簇中的节点均重复上述1）～8）步骤，直到网络中所有节点都加入到所生成的各簇当中后，算法结束。

4.3算法基本特性分析

以下将主要从实现算法所需的相关信息是否易于获取、以及其获取是否会额外增加网络负担等方面，对本文提出的引入节点通信质量的网络加权分簇算法（CQACA）主要特性进行分析：

相对邻节点的平均距离Distany：在进行网络维护获取最小主控集过程中节点y将获得与其一跳邻节点yi的距离，再结合degry，各节点可以直接计算得到Distany，不会增加新的开销和复杂度；

相对邻节点的平均移动速度My-opp：邻节点在周期发送的邻居拓扑信息中将携带上自身在ΔT时间段内的平均速度信息Vi；节点y易得自身在ΔT时间段内的平均速度信息Vy，再结合degry，各节点可以直接计算得到My-opp，不会增加新的开销和复杂度；

节点y的通信质量NodeComQuay：在无人平台集群的移动Ad hoc网络进行拓扑维护过程中，其获取网络最小主控集时成员就会获取并周期更新该信息，因此本算法不会增加开销和复杂度；

簇头选取总权值Authorityy计算：成员通过所获取的上述信息进行计算即可得到Authorityy；在完成自身的计算处理后，网络成员将在本周期发送的邻居拓扑信息携带上一周期的该信息，从而实现周期交互获取；

节点加入簇：需交互簇头通报消息、簇头通报应答消息，这是由网络分簇而带来的新增维护类信息交互。因此，在算法设计中考虑需尽量提高信息交互效率。

①节点将比较所获取的邻节点的Authorityy权值，结合自身覆盖度degry与最优覆盖度σ的对比情况，决定自身如何发送簇头通报消息；邻节点在收到簇头通报消息后进行判断处理，向满足条件的簇头发送簇头通报应答消息；

②当degry≤σ时，节点y将向其全部邻节点发送簇头通报消息；当degry>σ时，表示节点y有较多邻节点，其覆盖度很大。因此：根据y的邻节点上报的A（i，y）adapt信息，选择A（i，y）adapt最小的σ-1个邻节点发送簇头通报消息，该方法将有效减小簇头通报消息的发送量；

③节点y的邻节点收到簇头通报消息后，将对每个向其发送消息的簇头节点计算A（i，x）adapt，并向A（i，x）adapt最小的簇头节点发送簇头通报应答消息，并加入该簇。

五、结论

通过对无人平台集群移动Ad hoc网络特点及网络分簇、维护管理需求的分析，本文提出了一种引入节点通信质量的网络加权分簇算法（CQACA），并对算法原理和实现进行了详细描述。该分簇算法既能确保网络成员间信息尽量可靠、实时传输，还能使网络的整体性能得到一定的均衡，从而能够较好地满足无人平台集群移动Ad hoc网络的应用通信需求。

参 考 文 献

[1] 丁玲. 无线移动Ad Hoc网络拓扑管理技术. 《电子科技大学硕士论文》. 2007： 12-18.

[2] Nelson Minar， KwindleHultman Kramer， Pattie Maes. Cooperating Mobi Agents for Dynamic Network Routing chapter 12[C].In： Alex Hayzeldoned Software Agent for Future Communications Systems， 1999： 36-43.

[3] Jahani S， Bagherpour M. A clustering algorithm for Mobi ad hoc networks based on spatial auto-correlation. International Symposium on Computer Networks and Distributed Systems， Tehran， 2011：136-141.