分层Ad Hoc网络的分群及群首选举算法研究

杨健康，汤晓晨，陈颖颖

（1.装甲兵工程学院 信息工程系，北京　100072；2.63996部队，北京　100094）

分层Ad Hoc网络的分群及群首选举算法研究

杨健康1，汤晓晨2，陈颖颖1

（1.装甲兵工程学院 信息工程系，北京100072；2.63996部队，北京100094）

文章分析了战术互联网是典型的Ad Hoc网络，其结构导致层次及分群相对固定，可通过地址列表信息来完成群首的选举，以维护特殊情况下的群稳定性和网络功能。

Ad Hoc；群首选举；分群算法

Ad Hoc（点对点）网络具有网络的自组织性、动态的网络拓扑结构、有限的无线传输带宽及分布式网络、单向无线信道等特点。Ad Hoc网络中的所有节点作用相同，既可以作为主机发送接收信息，也可以作为路由器对数据进行转发。Ad Hoc网络可以应用于无基础设施的应用环境，包括无线传感器网络、作战与训练、抢险救灾、应急事件处置、个人通信等。Ad Hoc网络的主要研究包括信道接入、路由协议等，其中路由协议研究又是热点。对于战术互联网等特殊环境下的Ad Hoc网络，分群方法及群维护算法成为路由协议研究的重要内容。

战术互联网作为Ad Hoc网络，具有以下特点［1］：（1）无基础性网络；（2）节点资源的有限性；（3）无线通信介质的不可靠性；（4）节点的移动性。

除此之外，战术互联网还具有如下特征：（1）信道速率低，一般为几K到几十K；（2）网络覆盖范围大，一般大于40×40km；（3）节点的传输距离远，干线通信设备电台可达10～20km；（4）节点密度较大，网络覆盖范围的节点数量远大于一般应用场景。

同时战术互联网环境中的大部分节点都是1跳或2跳可达的，节点的相对运动速率较低，网络拓扑的变化速率比典型的Ad Hoc网络低［2］。因此，需要对现有的Ad Hoc路由协议针对战术互联网进行改进，以满足其要求。由于作战分队本身是具有指挥层级的层次性结构，即上级单位包含一定数量的下级单位，下级单位有唯一的上级单位，各个分队及单位之间不会相互重叠。可结合该特点设计相应的分群算法。

1　分群算法

根据Ad hoc网络固有的特性，以及对网络信息开销和节点移动性的考虑，Ad Hoc网络更适合采用分层式管理［3］，它是由管理者（Manager）、群首（Cluster Head）和代理（Agent）3级组成。最底层是代理，每个代理管理所在节点及周边链路等；多个代理形成一个群并由群首管理；群首则由网络管理者管理［4—5］。

根据Ad Hoc网络的分群过程，分群算法与群维护算法是管理过程中对群的不同阶段的管理。分群算法根据系统管理和运行要求，按照既定的规则将网络划分成互相连通且覆盖各个节点的群组；分群过程结束时，网络中各节点应该已经加入且唯一加入某个群。群维护算法是在网络结构或者节点状态发生变化时更新群结构，来保证网络的正常运行，一般指分群过程结束之后即进入群维护过程。

群的大小是分群过程的重要信息，一般群的大小根据各节点的传输功率和节点自身的特性来决定。其目标是尽量减少计算和通信开销来构造和维护网络群集合，该集合能够覆盖整个网络，其中构造群集合主要由分群过程完成，维护群集合主要由群维护过程完成，且该群集合具有较好的协议兼容性并支持网络资源管理。

2　按编制的战术互联网分群方法

以营级分队组网为例，基于编制的战术互联网无线通信网络模型如图1所示。

图1　基于编制的营级战术互联网通信网络模型

（1）营级。包括营长指挥车：营长指挥车；医疗车；运输车；服务车等。营指挥车是网络管理的顶层，是网络管理的核心，负责监控网络运行状态，并在运行过程中对关键事件进行分析、处理和调度。营指挥车一般是相对固定的节点。营网是网络的骨干，通信带宽设置最大，同时该层不对数据包/帧进行任何处理，以提高包交换的速度。核心层的主要目的是实现连排节点与营指挥网络以及各连排节点之间的高速连接。

（2）连排级。包括各连连长车和各排排长车，作为各群的群首，即节点车。连排指挥车作为一级，是营指挥级和作战车辆的连接点［6］，同时对网络的边界进行定义，通常是静态和动态路由选择协议之间的分界点。对数据包/帧的处理应该在该层完成。数据包的处理、路由选择、策略路由是该级的主要功能。

（3）作战车辆。包括各连的作战车辆，各连作战车辆只能在自己的子网内和本连的车辆进行通信以协同作战，接受直接上级即连排指挥车的领导，从连排指挥车接收战场态势及作战命令。若某作战车辆有特殊情况需要向营指汇报或是和他连的作战车辆通信，则需要通过上级节点寻找路由，将消息转发出去。因此，这些节点需要实现共享带宽、交换带宽等功能。

3　基于地址表的群首选举方法

上述分级方式遵从了实际作战编制，指挥体系明确，终端节点在自己的子网内通信。由于需要和另一子网交互的信息量不大，通过转发寻找路由的方式能够基本完成［7］。但是，考虑到实际作战情况，即电磁干扰、以及战损的情况下，一旦某一连的连排指挥车被干扰或是击毁，这一个连的作战车辆就会进入接受不到命令，不清楚战场态势的危险情况下，直接导致一个连战斗力的丢失。因此，需要对这样的分级网络进行改进。改进的过程如下：

（1）连网各群的群首节点（连排车）定期广播声明消息，该消息的内容包含网络标识和群首地址。声明消息的作用是向网内其他节点（战斗车）通报该群中已存在群首节点，且始终维护全网节点的地址使用情况表（Address In Used Table，AIUT），该表的版本号越大，则表中的信息越准确。

（2）若该群中某一节点（如Tank5）未收到声明消息，则认为网络中无群首，它在等待随机时间后进行全网洪泛选举消息，声明它希望成为该群临时新群首。

（3）收到选举消息的节点将自己的AIUT版本号与收到的版本号比较，若自己的版本号大于收到的版本号，则标记自己是临时新群首；若两者等，则选择具有最高地址的节点作为临时新群首；若自己的版本号小于收到的版本号，则认为Tank5节点就是临时新群首。

（4）如果在一段时间内临时的新群首没有收到其他节点的选举消息，则自己成为该群的群首，并启动预先存储的上级网（即营指挥网）的路由表进行通信。

这样，新群首选举过程就是寻找具有最高AIUT版本的节点的过程。如图1中网络，设Plotoon2失效后，选举Tank5作为新群首，如图2所示。

图2　通过版本选举Tank5为新群首

4　仿真结果分析

按图1结构采用集成网络仿真（Virtual Reality Network，VRNET）环境建立仿真模型［8］，设Company1损毁的情况下，按照使用备选路由直接和营指挥车通信的状况下Tank1的UDP交付率和延迟情况如图3—4所示。

图4　UDP Packet Delay

在群首节点更换后，网络通过竞争选择了新的群首。在图5仿真实验中可以看出，3个节点的误比特率在节点更换时同时达到峰值，但随着新的拓扑路由的建立，误比特率呈下降的趋势，在一定时间后，即恢复到正常的水平。

图5　Bit Error Rate

另外，在仿真中发现，节点移动得越快，场景的移动性越大。随着节点移动速率的提高，分组递交率有所下降，因为提高节点移动速率会使路由失效得更快，从而导致部分分组因找不到路由而被丢弃。但分组抵达率下降的幅度并不是很大，成功率大于70%。

［1］郑少仁，王海涛，赵志峰.Ad Hoc网络技术［M］.北京：人民邮电出版社，2005.

［2］曹志刚.现代通信原理［M］.北京：清华大学出版社，2002.

［3］马志欣，赵鼎新，谢显中，等.车载通信网中基于DSR分层机制的移动代理路由策略研究［J］.重庆邮电大学学报（自然科学版），2011 （2）：207-213.

［4］沈中.无线Ad Hoc网络拓扑管理研究［D］.西安：西安电子科技大学，2005.

［5］HEN W C，JAIN N，SINGH S.ANMP：Ad Hoc Network Management Protocol［J］.IEEE Journal on selected aeras in communications，1999（8）：1506-1531.

［6］George F.Elmasry.战术无线通信与网络—设计概念与挑战［M］.曾浩洋，田永春，译.北京：国防工业出版社，2014.

［7］张冬辰，周吉.军事通信［M］.北京：国防工业出版社，2008.

［8］霍景河.网络仿真VRNET基础与开发［M］.北京：北京交通大学出版社，2016.

Research of clustering and group leader election algorithmon hierarchy Ad Hoc network

Yang Jiankang1， Tang Xiaochen2， Chen Yingying1
（1. Department of Information Engineering， Academy of Armored Forces Engineering， Beijing 100072， China；
2. Troop No. 63996 of PLA， Beijing 100094， China）

Tactical Networks is typical Ad Hoc Network. Its structure leads to relative fixation for hierarchy and clustering. In order to maintain the cluster stabilization and network function in particular cases， Group leader election can be reached by address list message. Key words: Ad Hoc； Group leader election；clustering algorithm

杨健康（1978— ），男，河北深州，硕士，讲师；研究方向：战术通信技术及应用。