基于消息线程的群管理研究

谢志敏 梁进君 严宏举 霍永华

摘要：针对节点局部移动或离开所在群所引起的群布局部分和全部失效问题，研究群维护算法和群首维护算法。群维护算法设计了离群节点快速入群或重新组群的算法，确定算法中涉及的消息格式，设计了节点在正常担任群首职责期间对群成员的维护流程。通过设定群成员存活最新时间，定期进行心跳检测，实时更新群成员列表，基于消息线程分时同步处理群消息，实现了群管理的实时性和准确性，维护群结构的稳定性。

关键词：群首；分群结构；多属性拍卖；消息线程

中图分类号：TP393文献标志码：A文章编号：1008-1739（2018）15-67-3

Study on the Cluster Management Based on Message Threading

XIE Zhimin1， LIANG Jinjun2， YAN Hongju3， HUO Yong hua4（1. Special Office of PLA Marine Environment， Beijing 100181， China； 2. System Engineering Research Institute， Academy of Military Science， Beijing 100141， China； 3.Unit 31679， PLA， Xinxiang Henan 453000， China； 4. The 54th Research Institute of CETC， Shijiazhuang Hebei 050081， China）

0引言

在军事应用环境下，节点移动性较强，导致网络拓扑动态变化，分群结构频繁变动对网络运行性能和管理的效率产生极大的影响。提出的群维护算法和群成员维护算法，可以解决局部节点移动或离群所引起的群结构部分或全部失效问题，从而降低群成员或群首的离群对网络性能的影响，并且离群节点能够迅速加入新群或自组成群，从而避免重新调用分群算法而引起的大规模全网群重构。

1算法消息格式

解决节点部分移动所引起的群结构部分摧毁或全部摧毁问题，在群维护算法中，考虑了游离节点快速加入群或重新生成一个新群的方案的2种情况，避免重新调用分群算法所导致的全网重组。该算法提出以拍卖方式来解决群首委托问题，群首委托[1]是指由于设备处理能力变化、电量限制、安全能力限制及隶属关系变化等原因，群首无法继续执行群首职能，在其离群期限截止前由管理者指定或者群首选择一个新的群首来替代其职能，令该群的管理和任务不受群首离群影响而继续正常执行。

节点的3种状态有未分群、群首和群成员状态。节点在初始化时处于未分群状态，经过分群后，节点的角色成为群首或群成员，此后进入群维护状态。在群维护状态中，群首或群成员如果离群，则有可能直接在群维护中转变角色，或进入到未分群状态[2-3]。

2群首维护算法

假设群首离群时限设置为（=1）min，收到的前一群成员应答消息的时间戳为_。群成员离群时限设置为（=1）分钟，群首记录更新一个群成员列表，该列表存储着每个群成员的应答和反馈消息[4-5]，记录应答消息的时间列表_[]，记录该群成员的最新确认存活时间。在群首和群成员都维护一个接收群维护消息的超时计时器为_，该时限=（ ， ）。

群维护算法流程：

步骤1：周期性的群维护场景下，群首进行初始化，设置广播信息的地址和端口，群首计时器设置初值_=当前时间，在群成员列表中，计时数组为_[]=当前时间。

步骤2：群首向群成员发送群维护请求消息包，以便确定当前群成员是否正常存在。群成员收到群首发送的群维护请求包后，要尽快向群首返回群维护响应包。

步骤3：群首每收到一个群维护响应包时，根据收到该包的当前时间，更新群维护计时器值_。当计时器值超过时限

后，超时时间△=当前时间- _。若△<，说明群首还在本群未离开，则需转到步骤3.1，在该步骤中根据群首当前电量即将耗尽等原因进行群首委托的判断，若群首无法继续担任该群的群首，则需要向管理者申请在群成员中选择一个合适的群成员作为新的群首；若△>，则说明该群首已离群，转步骤3.2，在此期间，如果群首收到新成员加入该群的请求消息，则将该消息进行暂存。

步骤3.1：判断群首电池电量是否低于某个阈值（假设

=30%），若群首电池电量低于阈值，则向管理者提出群首转任申请，若管理者指定新的群首，则转入步骤3.1.3；若管理者回复群首自主进行职能委托，则转到步骤3.1.1；否则电量充足，转到步骤3.1.2。

步驟3.1.2：群首具有充足电量继续担任群首职能，执行步骤4。

步骤3.1.3：若管理者指定群首，原群首则对指定群首发送群首委托确认消息，并向管理者发送群首注销请求消息以注销自己的群首职能，同时释放本地群成员列表信息、本地线程和缓冲区中待处理新成员加入请求消息等，将自身状态转为群成员状态。

步骤3.2：若△>，则说明群首已离群，则向管理者发群首注销请求消息以注销自己群首职能，同时释放本地群成员列表信息、本地线程和缓冲区中待处理新成员加入请求消息等，群首进入未分群状态。

步骤4：群首继续执行群维护功能，判断本群群成员时候有离群操作。通过计算△=当前时间-群成员应答时间数组值_[ ]，判断△与门限值的关系。若△[ ]≥，表示群成员有离群操作，转入步骤4.1；否则标识该群中没有群成员离群，转入步骤5。

步骤5：判断缓冲区中是否有新成员加入请求消息；若无请求消息，则转到步骤6，若有请求消息，则进一步判断当前群成员是否达到群上限（假设定义每个群规模限定成员最大个数为），若已经达到群上限，执行步骤5.1，否则若未达到群上限，则执行步骤5.2。

步骤5.1：群首发送群成员被拒绝消息，到待加入的群节点，继续执行步骤6。

步骤5.2：发送群成员加入响应消息给待加入的节点。启动等待计时器_，如果在计时器范围内收到新成员加入确认消息，则更新本地群成员列表，执行步骤6；如超过计时器范围，则直接执行步骤6。

步骤6：群首发送群成员更新消息给管理者，转到步骤2，重复执行群维护过程。

在上述步骤中，群首委托是指当设备处理能力变化、电量限制、安全能力限制、隶属关系变化等原因，可能导致群首无法继续担任群首职能。该群首需要在离群期限截止前选择一个新的群首，并通告给管理者和原群成员。当某个群首选择群首继任者时，采用单轮、多属性英式拍卖方式向群成员广播群首委托邀请信息，群成员评估自身资源状态，填入到群首委托响应消息，并回复给群首。群首评估各个群成员返回的各项属性值，根据当前网络需求调整的各个属性权重因子，并选择

最小的群成员作为群首继任者。原群首向管理者注销当前身份，并转为普通群成员状态。新群首需向管理者注册，更新群成员列表。

设计了当群首发现自身电量不足、移动速度过大或安全能力[6-7]受到威胁时，需将群首职责委托给其他群成员。算法采用拍卖思想进行群首职责拍卖，各个群成员必须返回其值。通过群首职责委托，避免了大规模重新分群所带来的额外网络流量，大大减少了控制信息的数量。另外算法实时性强，可尽快选取新的群首实现对群成员的管理和维护。

设计了节点在正常担任群首职责期间，对群成员的维护流程。群首处理新节点的入群请求，如未达到该群的规模上限，则返回群成员加入响应信息给新节点。当收到该节点的群成员加入确认信息后，获取该节点当前状态信息，更新群成员列表并上报给管理者。

3群成员维护算法

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

步骤1：群成员开启离群的计时器_（计时器取值为群首发送群维护消息的周期时长），用以判断自己是否已经离开当前所在的群。如果距离群首前一次广播的群维护请求消息的等待时长已超出计时器范围，则转到步骤3进行离群判断，否则转到步骤2。

步骤2：如果收到群首周期性广播的群维护请求消息，判定自己仍处于群中，给群首返回群维护响应消息，_取值更新为当前取值，并转到步骤1；如果收到群首委托请求消息，根据自身各项资源状态填入群首委托响应消息，并发送给群首，转到步骤1；如果收到群首委托确认消息，则进入群首维护状态，维护本地群成员列表。

步骤3：若当前取值_超出范围，则判断为群成员已经离群。群首查询距离自己距离为一跳的邻居节点是否也处于未分群状态，若处于未分群状态，则转到步骤3.1，否则为已分群状态，转到步骤3.2。

步骤3.1：若群首发现有未分群的距离为一跳邻居节点存在，说明群首离群导致当前群失效，则处于未分群状态的所有节点均重新执行分群算法进行重新组群。

步骤3.2：群成员查询邻居表中是否有群首。若无群首，该节点自组成新群。若有群首，则向群首发送群成员加入请求消息并等待群首应答，同时启动消息接收线程和计时器，进入步骤4。

步骤4：当收到第一个群成员回复的加入响应消息时（假设群首同意群成员加入），则发送群成员加入群的确认消息给群首。同时把群信息加入到本地群成员列表，转步骤1；若收到群首发送的拒绝入群消息，且收到消息时并未超时，则群首继续在消息线程中等待接收新的群成员响应消息；若未收到任何群成员加入响应消息且已经超时，即没有任何群首同意新群成员加入，则该群节点自组成新群。

离群的计时器_的设置周期等同于群首发送群维护消息的周期时长，当超出计时器范围时，说明自身已不处于群首的管辖范围，需按离群节点重新加入某一个群。

4结束语

群维护算法对分群算法完成后的分级网络结构进行支撑和调整，群维护算法的设计需要尽量确保调整后网络中的群规模不超过上限，从而节省群首维护控制开销，并且群数量维持在恰当数量，从而减少全网控制信息的交互能耗。另外实时性也是考察群维护算法的重要指标之一，离群节点需要尽快加入新群或重新自组成群，从而维护整个分级网络结构的稳定和完整，增强了军事网络的鲁棒性和抗毁性。

参考文献

[1]郑相全等编著.无线自组网技术实用教程[M].北京：清华大学出版社，2004.

[2]王海濤，田畅，郑少仁.一种新型的Ad Hoc网络分簇算法及其性能仿真[J].系统仿真学报，2003，15（2）：193-197.

[3]蒲潇.战术自组网网络结构及分群算法研究[D].大连：大连理工大学，2009.

[4]林军.Ad Hoc按需加权自适应（AOW）算法的改进研究[D].天津：天津大学，2006.

[5]程伟明，周新运.一个用于Ad Hoc网络的分簇方法[J].计算机学报，2005，28（5）：864-869.

[6]程伟明，郑健平，盛凌志.一个Ad Hoc网络中的簇结构模式[J].计算机研究与发展，2004，41（4）：674-678.

[7]胡光明.簇结构移动自组网络安全关键技术研究[D].长沙：国防科学技术大学，2007.