面向高速节点自组网的三级树形结构令牌双簇首分簇方法

摘要

一种面向高速节点自组网的三级树形结构令牌双簇首分簇方法，它包括：初始化分簇的步骤；选择各簇的簇首并建立低空、高空节点的步骤；对高空节点进行二次分簇并建立中心节点的步骤以及建立备用中心节点的步骤。本发明能够实现高速节点自组网的快速收敛，分簇稳定，抗摧毁能力强等特性，提高高速节点生存能力及攻击性能，充分发挥各节点通信能力，节省资源，以更好的完成通信任务。

说明书

技术领域

本发明涉及移动自组网领域，尤其是面向高速节点自组网的分簇方法， 具体地说是面向高速节点自组网的三级树形结构令牌双簇首分簇方法。

背景技术

随着移动自组网理论的应用越来越多，国内外开发了不少协同通信产品， 国内高速节点协同通信研究起步比国外晚，尚处于初始阶段。

有学者根据移动自组网中节点地位及担负功能的不同区分为平面结构和 分级结构两种拓扑结构，对于平面结构，因为其中每个节点的地位平等，故 又称为对等式结构，这种结构形成的网络比较健壮，由于覆盖范围比较小， 网络中节点相对比较安全，但它也有其缺点，例如在网络控制开销方面，如 果节点较多并且多数处于移动的情况下，开销会很大，因为在传输数据时， 节点移动导致路由经常中断，需要不停的重新建立路由导，致传输数据稳定 性较差，因此平面机构不具有较好的可扩展性。

相对的分级结构多用于大型的网络，分级网络依据不同的标准划分为若 干个簇(Cluster)，簇与簇组成网络，簇由一个称为簇首的节点和若干个称为簇 内成员节点组成，簇首大多由分簇算法选举产生，主要负责本簇内成员节点 的通信，如果簇内节点要和簇外节点通信，簇首负责转发数据，而簇首之间 可以借助网关或直接通信，分簇内成员加簇首构成一个簇，而簇首和网关形 成更高一级称为虚拟骨干网(VBN)的网络。

在分级结构的移动自组网中，分簇内成员的功能比较简单可以直接进行 通信，成员之间不需要维护复杂的路由信息，无形中就减少网络中很多路由 开销，因此当网络规模需要扩大时，具有较好的扩展性，同时可以根据需要 随时选举簇首节点，具有较强抗毁性。但分级的结构也有它的缺陷，首先， 簇首选举需要适合的簇首选举算法和为了维护稳定的结构需要建立簇维护机 制，其次，因为簇首节点担负簇之间以及簇内成员的通信，负载相对较重因 为能量损耗较快很可能成为网络的瓶颈，最后，节点间通信借助簇首进行， 选择的路由不一定是最佳路由。

分簇算法主要考虑重点是结构的稳定与网络性能是否可靠等，即如何在 移动网络环境中获得稳定的簇结构，并实现有效可靠路由、增强网络管理、 提高网络性能等。目前针对不同的应用环境和组网要求已提出了一些分簇算 法，例如：最高连接度分簇算法、最小ID分簇算法、最小簇改变算法、移动 度量MOBIC算法，改进后的分簇算法有自适应按需加权分簇算法、给予树形 骨干网的分簇算法和双簇首的分簇算法。但是考虑到网络体系结构以及使用 环境要达成目标和性能的不同，并没有一种通用的、可随时组网、放之四海 而皆准的分簇算法，但是公认采用分簇结构有很多优点诸如减少路由开销， 有效利用有限网络带宽，利于解决避免簇内访问冲突，便于网络管理以及增 强网络使用寿命等。

发明内容

本发明的目的在于提供一种面向高速节点自组网的三级树形结构令牌双 簇首分簇方法，从而实现高速节点自组网的快速收敛，分簇稳定，抗摧毁能 力强等特性，提高高速节点生存能力及攻击性能，充分发挥各节点通信能力， 节省资源，以更好的完成通信任务。

本发明的技术方案是：

一种面向高速节点自组网的三级树形结构令牌双簇首分簇方法，它包括： 初始化分簇的步骤；选择各簇的簇首并建立低空、高空节点的步骤；对高空 节点进行二次分簇并建立中心节点的步骤以及建立备用中心节点的步骤。

本发明具体包括以下步骤：

（A）、初始化分簇的步骤；首先，为网络中每个节点分配唯一ID，使用最小 ID分簇算法对网络进行初始化分簇，形成一级分簇；

（B）、选择各一级分簇的簇首并建立低空、高空节点的步骤；在各个分簇中， 依据最小ID分簇算法初步选举出一级分簇的簇首节点，并在一级分簇内进行 广播，簇内其他节点收到广播后，依据自己通信能力竞争簇首，竞争成功后 更改一级分簇的簇首，最终产生的一级分簇的簇首节点称为高空节点，广播 通知一级分簇内其他节点成为簇成员，即低空节点；

（C）、对高空节点进行二次分簇并建立中心节点的步骤：采用最小ID分簇算 法对网络中所有高空节点进行二次分簇，形成二级分簇；在各个二级分簇中， 依据最小ID分簇算法初步选举出二级分簇的簇首节点，并在二级分簇内进行 广播，簇内其他节点收到广播后，依据自己通信能力竞争簇首，竞争成功后 更改二级分簇的簇首，最终产生的二级分簇的簇首节点称为中心节点，并广 播给二级分簇内其余高空节点；

（D）、建立备用中心节点的步骤：二次分簇后，在各二级分簇中选择通信能 力次强的节点作为各簇的二级分簇的次簇首，各次簇首作为备用中心节点并 广播给簇内其余二级分簇内的高空节点，建立三级树形结构。

本发明的步骤（B）中，在各个一级分簇和二级分簇中，簇内节点依据自 己通信能力竞争簇首的方法是：

步骤一、建立各分簇节点的集合：记A={x₁,x₂......x_n}为初始化和二次分簇后， 任一一级分簇和二级分簇中所有节点的集合，n为任一分簇中节点的个数；

步骤二、在任一分簇中，采用如下公式计算各节点的通信能力F(x_i)，

F(x_i)=F(af₁(x_i),bf₂(x_i),cf₃(x_i))；

其中，1≤i≤n，f₁(x_i)表示在t₀-t₁时刻，节点x_i与分簇内其余各节点建立的通信 链路的利用率的均值，t₀-t₁为初始化分簇后的任一时间段；f₂(x_i)代表节点x_i与 簇内其余各节点传输延迟的均值；f₃(x_i)表示节点x_i与簇内其余各节点通信出 错率的均值；a，b，c为通信网络中各参数对应的加权系数。

本发明的步骤一中，设A={x₁,x₂......x_n}为任一分簇中所有节点的集合，运 用NUM(·)计算集合中节点的个数NUM(A)=n。

本发明的步骤（C）中，建立中心节点后，各中心节点向控制中心通报网 络状况，控制中心产生一个令牌交给中心节点即根结点，令牌在通讯过程中 使用。

本发明中，各节点中选举出的中心节点后，由控制中心赋予令牌，节点 消失则令牌重新产生，各簇内令牌在中心节点与高空节点组成的令牌环间流 转，其地址为中心节点ID，环内其余节点需要使用信道传输信息，拿到令牌 后使用信道，信道使用完毕释放令牌，每个节点申请使用令牌时间固定，未 传递完毕信息再次申请，令牌每轮转一次，信息数加一，如果中心节点在申 请使用时间完毕未收到返回令牌，则认定令牌失效，重新产生新令牌。

本发明的有益效果：

本发明通过建立低空节点、高空节点和中心节点形成三级树形结构，便 于管理，有利于网络的稳定性和可靠性。

本发明的分簇算法，能够快速收敛，分簇稳定性高，抗摧毁能力强。

本发明使用的令牌可确保通信的顺畅，充分利用带宽；确保网络结构不 发生剧烈变化。

附图说明

图1是高速节点组网模型示意图。

图2是分簇算法实现过程。

图3是高空节点选举过程。

图4是中心节点选举过程。

图5是备用中心节点选举过程。

图6是重新选举中心节点过程。

图7是树生成算法流程图。

图8是簇维护算法流程图。

具体实施方式

下面结合附图和实施例对本发明作进一步的说明。

如图1所示，本发明将高速节点组成的网络分为三级的树形结构。第一 级节点中心节点，即根结点，负责与控制中心例如卫星等的通信，同时兼顾 管理其他高空节点；第二级节点高空节点，即根结点的子节点，负责与中心 节点通信，管理低空节点；第三极节点低空节点即叶子节点与高空节点通信。

如图2所示，分簇算法的主要思想如下：

A：预先发射时赋予各个高速节点唯一ID，使用最小ID分簇算法对网络 初始化分簇，采用协同通信优先级调整分簇产生高空节点，进而选举出中心 节点，最后再产生一个备用中心节点。

B：选举出的中心节点向控制中心通报网络状况后，控制中心产生一个令 牌交给中心节点，即根结点，令牌在通讯过程中使用。

C：需要重新选举中心节点时依据备用中心节点是否存活采取不同策略。

D：需要重新选举高空节点时依据分簇算法产生。

通信时，在各节点中选举出的中心节点由控制中心赋予令牌，节点消失 令牌重新产生，令牌在中心节点与高空节点组成的令牌环间流转，其地址为 中心节点ID，其他节点需要使用信道传输信息，拿到令牌后使用信道，信道 使用完毕释放令牌，每个节点申请使用令牌时间固定，未传递完毕信息再次 申请，令牌每轮转一次，信息数加一，如果中心节点在申请使用时间完毕未 收到返回令牌，则认定令牌失效，重新产生新令牌。

选举产生各簇首节点时，1)产生高空节点如图3所示，依据ID初步选 举出簇首节点并在分簇内进行广播，其他节点收到广播后依据自己通信能力 竞争簇首，最终产生簇首节点称为高空节点，广播通知其他节点成为簇成员； 2)产生中心节点如图4所示，中心节点产生后其他高空节点相应成为分簇成 员；3)产生备用中心节点如图5所示，中心节点选出来后，综合衡量簇成员 通信优先级，指定备用中心节点，并广播给簇内其他节点。选举具体过程如 下：

Step1：开始时，分配节点唯一的ID号，节点周期性地广播发送Hello消 息建立和维持自身与邻居节点之间信息列表。

Step2：每个节点在获取邻居节点Hello报文广播信息后对比自己的ID值， 如果较小则向对方发送Join信息宣布自己成为簇首节点，同时向其邻居广播 自己簇首信息。

Step3：每个节点在获取自己邻居节点Join信息后将自身ID值与其比较， 如果较小则向其发送包含Join信息宣布自己成为簇首节点并向其邻居广播， 如果不是则向发送Join信息的节点发送Accept信息加入簇，不再参与簇首选 举。

Step4：如果一个节点发现收到多个Join信息则对比ID值加入具有最小 ID值节点构成的分簇。

Step5：节点接到邻居节点发送的Accept信息将其加入自己的分簇成员列 表。

Step6：如果在给定的时间内一个节点没有收到任何Join信息则向邻居节 点发送Join信息请求成为簇成员然后跳转步骤4。

Step7：如果在给定时间内，宣布成为分簇簇首的节点没有再收到任何Join 信息则表明初始分簇选举结束，成为簇首的节点计算自身通信能力，向分簇 内成员发送Hello信息自己的节点信息及通信能力。

Step8：分簇内成员收到信息后，计算出自身通信能力，两者对比，如果 自己通信能力强，则发送Change消息给簇首，否则不作回应。

Step9：簇首在收到一个或多个Change消息后，选择通信能力强的一个节 点发送Accept信息，并广播其节点信息给簇内其他成员，更新新簇首消息。 如果簇首在给定时间内没有收到回应，或新簇首选举出来后，则宣布自己为 高空节点并向全网发送包含自身成员信息在内的Hello信息进行广播，其他分 簇同步进行选举出高空节点。

Step10：每个高空节点在获取到Hello信息后将自己的ID与其进行比较， 如果发现自己ID值较小则向比对方节点发送Join信息，宣布自己成为簇首节 点。

Step11：每个高空节点在获取到Join信息后将自己的ID与其进行比较， 如果发现自己ID值较小则向比对方节点发送Join信息，宣布自己成为簇首节 点，否则发送Accept信息加入簇，不再参与簇首选举。

Step12：如果一个节点接到其他节点Accept信息，将其加入自己的分簇 成员列表。

Step13：如果在给定时间内，宣布成为簇首的高空节点没有再收到任何 Join信息，则表明选举结束，该节点成为簇首的高空节点，计算自身通信能 力向其他高空节点发送Hello信息进行广播。

Step14：分簇内成员收到信息后，计算出自身通信能力，进行对比，如果 自己通信能力强，则发送Change消息给簇首，否则不作回应。簇首在收到一 个或多个Change消息后，选择通信优先级最高的一个节点发送Accept信息， 并广播其节点信息给簇内其他成员，更新新簇首消息。如果簇首在给定时间 内没有收到回应，或新簇首选举出来后，则宣布自己为中心节点并向全网发 送包含自身成员信息在内的Hello信息进行广播。

Step15：中心节点产生后，向其分簇成员发送Hello消息询问各个分簇成 员协同通信优先级，查询出通信能力最强的一个节点，并广播其节点信息宣 布其作为备用中心节点，其他簇成员收到Hello消息后在自己簇首消息列表中 加入备用中心节点信息。

Step16：中心节点选出后，向控制中心发送Control信息广播移动自组网 信息，控制中心收到Control信息后，产生令牌并与Sure信息一起发送给中心 节点，中心与高空节点使用令牌控制通信信道，协调控制其他节点。

当中心节点或高空节点被损坏，失去与控制中心的联系，这时就需要重 新选举中心和高空节点。1)选举中心节点时，若是备用中心节点没有被摧毁， 控制中心经过查询确定备用中心节点没有被摧毁，则备用中心节点直接成为 中心节点，然后向整个网络发布Hello消息成为中心节点，控制中心产生新的 令牌交予中心节点；若是备用中心节点被摧毁，则在各个高空节点组成的分 簇中重新选举中心节点，选举示意图如图6所示，过程如下：

Step1：每个高空节点向整个网络发送广播包含自己ID号等节点信息的 Hello报文。

Step2：每个高空节点在获取到Hello消息后比较自己ID，如果发现自己 ID较小则向其发送Join消息宣布自己成为簇首节点。

Step3：每个高空节点在获取到Join消息后对比ID，如果自己ID较小则 向对方发送Join消息宣布自己成为簇首节点，否则发送Accept报文广播加入 此节点形成簇，不再参与簇首选举。

Step4：如果一个节点接到Accept消息将其加入自己的分簇成员列表。

Step5：如果在给定时间内宣布成为簇首的节点没有在收到任何Join消息 则表明簇首选举结束，成为簇首的节点向其他高空节点发送Hello报文广播本 节点通信能力及节点信息。

Step6：分簇内成员收到信息后，对比自身通信能力，如果自己通信能力 强，则发送Change消息给簇首，否则不作回应。簇首在收到一个或多个Change 消息后，选择通信能力最强的一个节点发送Accept信息，并广播其节点信息 给簇内其他成员，更新新簇首消息。如果簇首在给定时间内没有收到回应， 或新簇首选举出来后，则宣布自己为中心节点，并向全网发送包含自身成员 信息在内的Hello信息进行广播。同时选举出备用中心节点。

Step7：中心节点选出后，向控制中心发送Control消息广播自组网信息， 控制中心收到Control信息后，产生令牌并与Sure信息一起发送给中心节点。

2)重新选举中心节点时，若高空节点所在的分簇成员较多，则直接选举 出高空节点，其选举过程与初始高空节点选举过程一致，只是在新的高空节 点产生后，向整个网络发送Hello报文广播自己的节点信息，请求加入中心节 点的分簇，中心节点在收到Hello消息后，向其发送Join消息将其加入自己簇 成员消息列表；若高空节点所在的分簇成员少于两个，则分簇成员直接加入 邻近的分簇成为分簇成员。过程如下：

Step1：每个低空节点向邻居节点发送Hello消息广播自己的节点信息。

Step2：邻近的高空节点在获取到Hello消息后向低空节点发送Join消息。

Step3：低空节点接收到Join消息后，选择其中ID号最小的一个发送 Accept消息加入其中成为簇成员。

Step4：高空节点在获取到Accept消息后将低空节点加入自己分簇成员列 表。

树结构生成算法如图7所示，具体步骤如下：

Step1：指定中心节点为树生成算法的源头，产生仅有一个节点的核心树。

Step2：中心节点向网络广播包含自己ID的Hello消息，未加入核心树的 高空节点簇首收到消息后，单播发出加入核心树请求Want-Join消息。

Step3：在核心树中收到加入请求的中心节点发出Sure-Join消息。

Step4：高空节点根据收到的应答，选择中心节点的分簇作为自己簇首， 并且播发出Member消息，Member消息中包括了自己簇内所有低空节点的信 息。

Step5：收到Member消息的中心节点将分簇内信息加入分簇成员列表并 将其设置成自己的子簇。

Step6：未加入网络的其他高空节点重复步骤2-5直到高空节点都加入到 核心树上。

在簇维护算法中加入节点定时器，通过定时器的运作来判断簇成员低空 节点或高空节点以及中心节点是否还存在，或者是否已经被摧毁。其算法流 程图如图8所示。

其中，算法中应用到的消息，Hello信息为所有的节点在每个Hello时间 间隔周期性地向外广播Hello信息通告自身节点情况，每个节点的Hello信息 包括它的邻居表和簇首邻表。Accept消息用于回复节点加入分簇申请，Change 消息用于更新簇首，Control消息用于控制中心与中心节点交流，Hello消息用 于广播节点自身信息及传递命令节点间信息交流等，Join消息用于申请加入 分簇，Sure消息用于确认消息。

本发明未涉及部分均与现有技术相同或可采用现有技术加以实现。