一种群维护算法研究

焦利彬 赵波 赵志军

摘要：针对网络拓扑动态变化下的群结构维护问题，提出了群首维护算法和群成员维护算法，详细介绍了算法流程。群维护算法对群规模和群数量进行控制，基于群结构进行自适应调整，设定离群定时器同时周期性广播群消息，群首与群成员交互的信息包含节点的各项属性信息和资源信息，最终计算出综合评判值，以此判断最佳群首和群成员。

关键词：群首维护；群成员维护；离群定时器；广播群消息

中图分类号：TP393文献标志码：A文章编号：1008-1739（2020）02-57-4

0引言

战场网络节点具有高动态性，随时随地向不同的方向移动导致网络节点连接关系频繁变化、拓扑结构频繁变化和重组、节点脱管失效及管理群结构发生动态变化，因此有必要研究管理群维护的相关内容和算法，使群拓扑结构对群内节点的移动或位置变化具有实时感知和应对能力，并且离群节点能够迅速找到并加入新群或自组成群。

群管理维护旨在对动态变化的管理群结构进行实时调整和管控，因此群管理维护的研究应该确保变化且调整后的管理群规模控制在合理范围内，首先要减少高动态群实时维护和管理的消息开销，同时动态群的数量也要控制在合理范围内，确保整个网络管理控制信息的带宽占用和消耗。群维护算法主要聚焦管理群内局部节点加入或离开所导致的整个群结构部分或全部失效的现象，重点研究高动态移动节点脱离某个群或重新加入某个新群的实时管理方案，避免大规模节点移动或离开而引起的大规模网络重构脱管。另外群管理维护方案也考虑实时性问题，离群节点需要尽快加入新群或重新自组成群，确保整体网络结构的稳定和完整，进而提升网络的可靠性和抗毁性。

1群首维护算法

1.1算法消息格式

当群首生成或群首变更引起群结构发生变化时，网络管理者需要实时维护并更新群结构，确认群首的管理功能及范围。另外，考虑到网络中的节点具有随机移动性，网络拓扑也会随之变化，导致群成员与群首之间的连通关系可能会频繁变化。需要研究当群首位置发生变动或由于自身电量等问题而无法承担管理职能时，该群首需将管理职能委托给具有充足的能量资源、位置稳定的群成员，从而维护管理分群的稳定。

在群结构中，群节点通常有不属于任何群、群首和群节点成员的3种存在状态。在网络拓扑初始规划时，节点处于独立存在状态，基于规划进行管理分群或拓扑分群后，节点的状态由独立节点变化或升级为群首或群节点，此后进入正常的群运行状态。在群维护中，如果发生群首故障离群或群节点移动离群事件，则节点的状态会发生改变，在未分群、群首和群成员之间切换。

算法中使用的消息定义如下：①群首注销请求消息由群首生成，用于向管理者通知自身不再为群首；②新群首注册请求消息；③新群首注册响应消息由管理者生成，用于向新群首确认其注册信息；④群查询请求消息由注册终端发给群首，请求查询群成员详细信息；⑤群查询响应消息由群首将该群成员列表详细信息发送给注册终端。

1.2群首管理算法

群首一般有属于或不属于某个群2种状态，如果群首不属于某个群，则设定一个群首离群时间阈值，初始设置为（=1）min，为了保持管理实时性，群首基于线程与群内节点进行信息交互，发送心跳信息。将群首收到的不同群成员应答消息的时间间隙设为_cnt min，群成员节点离开群的时间阈值设定为，初始化=1。

通常群成员节点信息由群首实时管理以列表形式存储，包括群首与每个群成员的握手、心跳检测和检测反馈消息，交互消息的时间记录信息以数组形式存储于_cnt[]消息数组中，对应的是该群成员节点确认存活的最新时间。

设定一个接收群维护消息的超时计时器，记作为_cnt，该计时器由群首和群成员共同维护，将计时器的初始值设定为离群时间阈值，最小值初始化为=min（ ， ）。

群管理维护算法的步骤如下：

步骤1：基于固定周期的典型群管理，将群首相关信息进行初始化配置，初始化配置内容包括①群首发送的广播信息的地址和端口号；②初始化群首离开群的时间计时器，离群时间变量设置为_cnt，初始化设定为当前时间；③群首维护的群节点成员信息的列表计时数组设为_cnt[]，初始值设定为当前时间。

步骤2：群首向所有群内成员节点广播群管理维护请求消息，目的是通过心跳消息确认当前所有群成员节点的实时状态，即是存活还是死亡。当群成员收到群管理维护的广播消息后，经分析是状态确认请求消息，则第一时间以点对点消息通信方式向群首返回群节点状态，确认维护响应消息。

步骤3：当群节点发送的状态确认群维护响应消息被发送到群首时，群首以消息包携带的时间戳信息为依据，更新计时器数组中对应的_cnt值。如果计时器出现越限情况，则计算超出时间差△=当前时间- _cnt，并判断超时时间△与时间阈值的大小。

如果超时时间△<，表明群首依然在群中，尚未离群，则转入步骤3.1。在步骤3.1中群首当前电量的实时情况是群首能否继续任职的唯一判断标准，如果群首电量即将耗尽，则群首立即向管理者发送群首委任卸任申请消息，管理者收到群首发送的委任申请消息后，立刻进行群节点状态查询，选择群节点状态为正常且满足要求的群成员节点，发送群首任命消息，宣布新的群首。

若超時差△>，则表明该群首由于种种原因目前已经离开所在群，此时转入步骤3.2。离开的群首在等待管理者发送的群首委任反馈消息的时间内，如果收到非本群新成员节点发送的入群请求消息，则暂存该请求入群消息。

步骤3.1：判断群首最新电池电量数值，比较电池电量与设定的阈值（假设=30%）并选择不同的操作步骤。如果电池电量低于设定的阈值，则群首转任申请消息由群首向管理者发送，如果新的接任群首已经被指定，则转入步骤3.1.3。

如果即将卸任的群首收到管理者发送的自主职能委托消息，则转入步骤3.1.1；否则认为群首目前电池电量充足，转入步骤3.1.2。

步骤3.1.1：群首继任者选择通过多属性拍卖方式进行，群首向群成员节点广播群首委托邀请信息，同时开启计时器，等待群成员节点收到邀请消息后的反馈，即向群首发送响应信息。

步骤3.1.2：如果群首的电池电量充足，具备能继续担任群首的条件，则转入步骤4。

步骤3.1.3：如果管理者指定新群首，群首委托确认消息由原群首发送至指定新群首，群首注销请求消息也由原群首发送至管理者，目的是宣布自己不再担任群首，同时释放清空所存储的群成员数组信息、本地线程和缓冲区中待处理新成员加入请求消息等，标记自身状态为群成员。

步骤3.2：若△>，表明群首已经离群，注销请求消息由群首发送至管理者，宣布自己不再是群首，同时释放存储的本地群成员数组信息、本地线程和缓冲区中待处理新成员加入请求消息等，此时标记群首为独立状态。

步骤4：群首继续执行正常管理操作，首先判断是否有群成员离开，依据时间差判断，时间差的计算方式为计算△=当前时间-群成员应答时间数组值_cnt [ ]，如果时间差△大于初始设定的门限阈值，且△[ ]，则发生了节点离开事件，转入步骤4.1；否则说明尚未发生节点离群事件，转入步骤5。

步骤5：群首查看缓冲区中是否有新成员请求加入消息，如果没有，则转入步骤6，否则表明有新成员请求事件发生，此时判断当前群成员个数，如果个数达到群规模规定的最大阈值（假设每个群规模阈值为），表明群规模已经达到规定的范围，转入步骤5.1，否则表明群还可以再容纳新成员，转入步骤5.2。

步骤5.1：将拒绝群成员加入消息反馈发送至待加入的节点，转入步骤6。

步骤5.2：待加入的节点收到群成员加入响应消息。启动等待计时器_cnt，如果在超时之前收到新成员加入确认消息，则更新本地群成员相关数组信息和群个数，转入步骤6；若超时仍未收到任何确认消息，则执行步骤6。

步骤6：群首向管理者发送新群成员加入更新消息，转入步骤2，重复执行群维护算法。

2群成员维护算法

2.1群成员维护算法

群成员维护算法的详细步骤如下：

步骤1：离群计时器l_cnt由群成员开启（计时器将群首发送群管理消息的周期时长设定为初始值），通过计时器判断自身与当前所在的群的关系，即在群中还是已经离群。与上一次相比，如果群首广播的群管理请求消息，等待时长越限，则转入步骤3；否则判断群成员是否已经离群，转入步骤2进行判断操作。

步骤2：群首进行周期性广播群管理请求消息，如果群成员收到广播消息，则表明自己尚未离开原始群，群成员向群首发送群维护响应消息，同时将l_cnt值更新，并转入步骤1。

如果群成员收到群首委托请求消息，将自身各项资源状态更新，并发送响应消息至群首，转入步骤1；如果群成员收到群首委托确认消息，则宣布自己为群首，以群首身份执行群管理工作。

步骤3：若l_cnt超出阈值，则群成员处于独立状态，此时该群成员查询距离自身为一跳距离的邻居节点的状态，并进行状态判断，如果这些节点也处于独立的未分群状态，既不是群首也不是群节点，则转入步骤3.1，否则转入步骤3.2。

步骤3.1：若存在未分群的一跳邻居节点，说明当前群脱离管理处于失控状态，则所有不属于某个群的独立节点重新入群组群。

步骤3.2：查询邻居表中是否有群首存在，若群中没有群首，则未分群的一跳邻居节点自组成新的群；若存在群首，则孤立节点向群首发送新入群请求消息，并启动消息接收线程和计时器等待群首响应，转入步骤4。

步骤4：假设群首cluser同意某孤立群节点加入，当群首收到第一个群节点反馈的加入响应消息时，将该节点信息更新存储至本地群节点信息数组中，并转入步骤1。

若在规定时间内请求入群的群成员收到群首的拒绝消息，则该群成员开启线程计时器，继续等待接收新消息；若已经超时且未收到任何同意加入响应消息，表明没有任何群首同意该节点入群，此时该群节点继续寻找新的距离自己最近的群并申请加入。

群成员开启离群计时器l_cnt，设定离群计时器初始值為群首发送群维护消息的周期时长，当离群计时器的值超出计时器的计时上限值时，说明群成员自身已经离群，无法接受群首管理，则群成员将自身状态标记为离群节点，进行重新加入另外一个群的入群请求申请操作。

2.2算法核心解析

当有新节点申请入群时，群首判断群内节点个数，如未达到所规定的群规模上限阈值，则同意该节点加入，同时更新群节点数组信息并上报管理者。

群首进行群维护需要判断是否离群，离群的群首不能继续对群内成员进行管理。如果群首已经离群，则立刻进入未分群状态，获取其他群首的实时信息，设置自身状态为新的群成员，同时向新群广播群成员加入请求信息。

当群首处于自身电量不足、高动态及受到威胁攻击不安全时，进行职能委任或者宣布自己不再担任群首。群首职责委托减少大规模网络重构所带来的额外网络流量，避免节点失控。另外算法实时性强，提升在高动态环境下的管理时效性。

群首维护算法和群成员维护算法设计的核心思想在于以拍卖方式进行，群首可以获取实时的群成员资源信息状况，以便选择出能够胜任群首职能的最优继任者，实时性较强；其二，相比较于直接选择某个委任者而言，拍卖方式为群成员提供了公平的竞争机会，最大程度考虑了负载平衡问题；最后，对群首即将转任而进行的拍卖方式，只需耗费一轮竞拍交互的网络流量，避免了大规模网络重构所导致的节点失控或脱离管理，大大提升管理效率。

3结束语

在高动态的典型应用环境下，网络拓扑结构频繁变化和网络大规模重组的情形随时可见，对网络稳定性和可靠性产生很大影响，同时给网络管理带来了极大的影响，导致网络节点脱离管理。本文设计的群维护算法，从控制群规模和群数量的根本点出发进行设计控制，一方面可以根据网络规模，控制所划分的管理群的个数和每个群的规模，另一方面在管理群和每个群设定好之后，可以通过设定群首、群成员的状态，以及判断每个群节点的位置、节点电量、节点与群的距离（以一跳为基准距离）等自身属性，进而判断节点是入群还是离群问题。通过上述2个设计点，解决了局部节点移动或离群所引起的群结构失效问题，同时能够根据被管网络的规模合理划分管理群，群过多会造成管理信息的海量增加，群过少会导致入群离群的时效性问题，不仅有效控制网络，同时也大大提高了管理时效性。

参考文献

[1]薛明.基于SNMP局域网流量监测系统的应用研究[D].郑州：郑州大学，2006.

[2]李涛，张亚群，刘岱平.面向服务的校园网流量监控系统设计与实现[J].现代计算机（专业版），2009（1）：154-156.

[3]宋进红，沈云琴.使用CactiEZ轻松构建校园网络流量监控系统[J].河南城建学院学报，2009，18（4）：57-59.

[4]段宗涛，林莎.基于SNMP的网络流量监控系统的设计与实现[J].微型机与应用，2001（11）：25-27.

[5]董加敏，王斌.基于SNMP协议的高校网络流量监控管理系统的研究[J].广州大学学报（自然科学版），2009，8（1）：53-57.

[6]张彤，吴世荣.基于SNMP计算机网络流量监控系统研究[J].计算机技术与发展，2011，21（1）：88-91.

[7]徐鹤，王汝传.一种P2P流量监控系统的设计及实现[J].计算机技术与发展，2009，19（10）：6-10.

[8]赵英，黄九梅，董小国，等.网络流量监控系统的设计与实现[J].计算机应用，2004（S1）：32-33.

[9]张卫东，王伟，韩维桓.网络流量测量与监控系统的设计与实现[J].计算机工程与应用，2005，41（32）：160-163.