一种基于主动门限设置的自适应分簇方法

摘要

本发明一种基于主动门限设置的自适应分簇方法，属于通信领域。具体步骤为：首先，为无线网络中的每个节点寻找邻居节点，并按欧式距离从小到大排列；每个节点计算自身权值，并发送给邻居节点；然后，每个节点判断自身权值是否大于所有邻居节点的权值，如果是，设定并根据邻居节点的数量门限，发送“簇头存在”消息或“已分簇”消息，同时对节点进行标记；否则，根据邻居节点发送的“簇头存在”消息或“已分簇”消息分别对节点进行标记；最后，判断标记后的节点是否为簇头节点，如果是执行簇头节点入簇；否则执行成员节点入簇；优点在于：门限机制预设的不是具体值，更为全面和可调，在负载均衡性上有显著提高。

说明书

技术领域

本发明属于通信领域，涉及一种基于主动门限设置的自适应分簇方法。

背景技术

通信领域的分簇算法最早出现在无线传感器网络中，后又引入到无定形扁平化自组织无线网络中，无定形扁平化自组织无线网络希望将终端、基站和核心网扁平化为单一的网络节点，所有节点的地位平等，并具有自组织的能力。

现有的分簇算法有最小ID法、最高连接度法、门限法和加权法等。

门限法指：设置分裂和合并门限，簇内节点数量大于分裂门限则执行簇分裂，小于合并门限则执行簇合并。加权法指：综合考虑节点连接度、节点剩余能量等多个因数，对每一个节点进行归一化并加权以得到分簇权值，以权值为基础进行分簇。相似算法为自适应按需加权(AOW，Adaptive On-demand Weighting)分簇算法，同样是针对同质节点组成的无线网络的自适应加权算法。

在现有的门限法中，设置的是单一的节点数量的门限。而每一个节点在一段时间以后，由于剩余能量等其他因素的不同，所能承受的负载并非都是一样的。因此设置单一的门限标准不利于网络的自适应。

在非交叠簇模式下，每个成员节点只属于一个簇，而在扁平化自组织的前提下，一个成员节点可能会收到两个甚至多个簇头发出的分簇消息。针对这种情况，现有通常采用先到先得的方式选择入簇，即簇成员在收到第一个符合条件的分簇消息后便入簇。这样会与事先的分簇思想冲突：一些簇头未能聚集预期数量的成员，而一些簇头聚集了过多数量的成员。

发明内容

本发明结合现有算法的特点，加入以簇的成员节点主动选簇头的新模式，在不明显增加通信消耗的前提下显著提高分簇结构的负载均衡性，提出了一种基于主动门限设置的自适应分簇方法。

具体步骤如下：

步骤一、将无线网络中的每个终端作为一个节点，对每个节点寻找邻居节点，并按欧式距离从小到大排列；

步骤二、每个节点通过加权法计算自身权值，并将自身权值发送给邻居节点；

步骤三、每个节点判断自身权值是否大于所有邻居节点的权值，如果是，进入步骤五，否则进入步骤四；

步骤四、针对某个节点i，根据邻居节点发送的“簇头存在”消息或“已分簇”消息分别对节点i进行标记；

具体步骤如下：

步骤401、针对节点i，判断是否有邻居节点发送“簇头存在”消息，如果是，进入步骤402；否则，进入步骤403；

步骤402、节点i向所有邻居节点发送“已分簇”消息，并将节点i标为成员节点；进入步骤六；

步骤403、判断是否权值大于自身的全部邻居节点均发送“已分簇“消息，如果是，进入步骤五，否则，返回步骤401；

步骤五、针对节点i，设定并根据邻居节点的数量门限，发送“簇头存在”消息或“已分簇”消息，同时对节点i进行标记；

具体步骤如下：

步骤501、各个节点自适应生成三个门限：最小规模门限minn、最佳规模门限pren和最大规模门限maxn。

步骤502、判断节点i的邻居数量n超出minn，则进入步骤503，否则超出maxn进入步骤504；

步骤503、判断节点i的邻居数量n是否小于minn，如果是，向邻居节点发送“已分簇”消息，并将节点i标为成员节点；否则将节点i标为簇头节点；

步骤504判断节点i的邻居数量n是否大于maxn，如果是，根据最佳规模门限pren数量，向欧式距离最近的pren个邻居节点发送“簇头存在”消息，向其余节点发送“已分簇”消息，将节点i标为簇头节点；否则，向所有邻居节点发送“簇头存在”消息，将节点i标为簇头节点。

步骤六、判断标记后的节点i是否为簇头节点，如果是进入步骤七，否则为成员节点进入步骤八；

步骤七、执行簇头节点i的入簇阶段；

具体步骤如下：

步骤701、设置簇头节点i的状态s_i为0，已入簇的邻居节点数量n_i为0，统计邻居节点中未入簇的成员节点，数量为d_i；

步骤702、判断节点i未入簇成员节点数量d_i是否为0或簇头状态s_i是否为3，如果是，簇头节点i的入簇阶段结束；否则进入步骤703；

步骤703、判断节点i已入簇节点数量n_i是否大于等于当前簇头状态s_i所对应的门限数量； 如果是，则当前簇头状态s_i加1，并向所有邻居节点发送包含当前簇头状态信息的“状态改变”消息；返回步骤702；否则，进入步骤704；

当前簇头状态si的值分别为0，1，2和3；簇头状态0对应的门限数量为小于最小规模门限minn值；簇头状态1对应的门限数量为大于等于最小规模门限minn值到小于最佳规模门限pren值；簇头状态2对应的门限数量为大于等于最佳规模门限pren值到小于最大规模门限maxn值；簇头状态3对应的门限数量为大于等于最大规模门限maxn值；

步骤704、判断是否收到簇头节点i的邻居节点j发送的“已入簇”消息，如果是，则未入簇成员节点个数d_i减1，返回步骤702，否则进入步骤705；

步骤705、判断是否收到簇头节点i的邻居节点j发送的“请求入簇”消息，如果是，则已入簇的邻居节点数量n_i加1，并向邻居节点j发送“允许入簇”消息，返回步骤702；否则返回步骤704；

步骤八、执行成员节点i的入簇阶段；

具体步骤如下：

步骤801、针对成员节点i，统计簇头状态si不为3的簇头节点数量为D_i；

根据收到的“簇头存在”消息统计邻居节点中的簇头节点数量；

步骤802、针对节点i，判断簇头节点数量D_i是否等于0，如果是，则将节点i标记为“悬空节点”，节点i完成入簇阶段；否则进入步骤803；

步骤803、针对某个节点i，根据收到的“状态改变”消息更新邻居节点的状态表，从中找出邻居节点中簇头状态最小的“簇头节点”中欧式距离最近的节点j，向节点j发送“请求入簇”消息；

步骤804、针对某个节点i，判断是否收到节点j返回的“允许入簇”消息，如果是，向所有其它邻居发送“已入簇”消息，节点i完成入簇阶段；否则进入步骤805；

步骤805、针对某个节点i，判断是否收到节点j返回的“状态改变”消息，如果是，进入步骤806，否则回到步骤804；

步骤806、针对某个节点i，判断是否收到邻居节点发送的簇头状态更新为3的“状态改变”消息，如果是，簇头状态不为3的“簇头节点”个数D_i减1，返回步骤802，否直接回到步骤802；

本发明的优点在于：

1、一种基于主动门限设置的自适应分簇方法，更切合自适应的要求：门限机制预设的不是具体值，在选举阶段和门限机制中综合考虑到剩余能量等其他因素，更为全面和可调。

2、一种基于主动门限设置的自适应分簇方法，相对于AOW算法，在负载均衡性上有显著提高。

附图说明

图1为本发明基于主动门限设置的自适应分簇方法流程图；

图2为本发明中根据邻居节点的发送消息对节点进行标记的流程图；

图3为本发明中根据邻居节点的数量门限，发送消息并对节点进行标记的流程图；

图4为本发明执行簇头节点的入簇方法流程图；

图5为本发明执行成员节点的入簇方法流程图；

图6为本发明本发明算法与传统AOW算法的负载平衡因子随通讯距离的变化情况图。

具体实施方式

下面将结合附图对本发明作进一步的详细说明。

为了保证网络的可扩展性和服务质量(QoS，Quality of Service)，无线移动网络通常采用分级结构。在无定形扁平化自组织无线网络中，分级结构通常采用分簇的方式来构造，而分簇算法的好坏将直接影响着无线移动网络的性能。

一种基于主动门限设置的自适应分簇方法，简称ALB算法；通过节点成员在被选举为簇头后，根据预先设置的算法自适应地生成该节点的门限标准，簇成员在获得所有邻居簇头发送的信息后，主动判断应该加入哪一个簇；以及从而提高网络的负载均衡性。

如图1所示，具体步骤如下：

步骤一、将无线网络中的每个终端作为一个节点，对每个节点寻找自身的邻居节点，并计算自身节点与邻居节点之间的欧氏距离，将欧式距离按从小到大排列；

每个节点周期性地广播“Hello”消息，“Hello”消息包括了自身编号和发送时间；当节点i收到节点j发送的“Hello”消息后，节点i将节点j标记为自身的邻居节点，并计算节点i与节点j之间的欧式距离，计算完欧式距离后，将欧式距离按从小到大排列；

本实施例中选用15个节点，分别为节点1到节点15；每个节点的邻居节点按欧式距离从小到大排序后，如表1所示；

表1

步骤二、每个节点通过加权法计算自身权值，并将自身权值发送给邻居节点；

加权法在本实施例中采用连通度与节点编号结合的方式计算，每个节点的自身权值如表2所示；

表2

步骤三、每个节点判断自身权值是否大于所有邻居节点的权值，如果是，进入步骤五，否则进入步骤四；

步骤四、针对某个节点i，根据邻居节点发送的“簇头存在”消息或“已分簇”消息分别对节点i进行标记；

如图2所示，具体步骤如下：

步骤401、针对节点i，判断是否有邻居节点发送“簇头存在”消息，如果是，进入步骤402；否则，进入步骤403；

步骤402、节点i向所有邻居节点发送“已分簇”消息，并将节点i标为成员节点；进入步骤六；

步骤403、判断是否权值大于自身的全部邻居节点均发送“已分簇“消息，如果是，进入步骤五，否则，返回步骤401；

步骤五、针对节点i，设定并根据邻居节点的数量门限，发送“簇头存在”消息或“已分簇”消息，同时对节点i进行标记；

如图3所示，具体步骤如下：

步骤501、各个节点自适应生成三个门限：最小规模门限minn、最佳规模门限pren和最大规模门限maxn。

步骤502、根据节点i的邻居数量n进行划分，判断关于minn的范围则进入步骤503，否则关于maxn的范围进入步骤504

步骤503、判断节点i的邻居数量n是否小于minn，如果是，向邻居节点发送“已分簇”消息，并将节点i标为成员节点；否则将节点i标为簇头节点；

步骤504判断节点i的邻居数量n是否大于maxn，如果是，根据最佳规模门限pren数量，向欧式距离最近的pren个邻居节点发送“簇头存在”消息，向其余节点发送“已分簇”消息，将 节点i标为簇头节点；否则，向所有邻居节点发送“簇头存在”消息，将节点i标为簇头节点。

针对节点1到节点15，通过分别比较自身权值与自身邻居节点的权值，可知，节点4的自身权值大于节点4的所有邻居节点；节点9的自身权值大于节点9的所有邻居节点；节点4和节点9分别执行步骤五。

本实施例为了方便说明，每个节点生成的门限均设置为：minn＝2、pren＝3、maxn＝4；

首先，针对节点4，邻居数量为6大于maxn，向欧式距离最近的3个邻居节点发送“簇头存在”消息，即向节点10、节点8和节点1分别发送“簇头存在”消息；向节点13、节点14和节点2分别发送“已分簇”消息。同时节点4标记为簇头节点。

同理，针对节点9，邻居数量为3，选择向所有邻居节点，节点6，节点7和节点1发送“簇头存在”消息，将节点9标为簇头节点。

下一步，针对节点1，收到“簇头存在”消息，则节点1向所有邻居节点(节点10，节点4和节点9)发送“已分簇”消息，并将节点1标为成员节点；

针对节点6和节点7，分别收到节点9发送的“簇头存在”消息，则向所有邻居节点(均为节点9)发送“已分簇”消息，并将节点6和节点7分别标为成员节点；

针对节点2，收到节点4发送的“已分簇”消息，但是因为未收到所有权值大于节点2的权值的邻居节点发送的“已分簇”消息(节点13的权值大于节点2的权值)，所以继续等待；

针对节点8，收到节点4发送的“簇头存在”消息，则节点8向所有邻居节点(节点4和节点14)发送“已分簇”消息，并将节点8标为成员节点；

针对节点10，收到节点4发送的“簇头存在”消息，则节点10向所有邻居节点(节点4，节点13和节点1)发送“已分簇”消息，并将节点10标为成员节点；

针对节点13，收到节点4发送的“已分簇”消息，权值大于节点13的邻居节点只有节点4，已收到所有权值大于自身权值的邻居节点发送的“已分簇”消息，继续判断节点13的邻居数量5大于maxn，向欧式距离最近的3个邻居节点发送“簇头存在”消息，即向节点15、节点10和节点4分别发送“簇头存在”消息；向节点3和节点2分别发送“已分簇”消息。同时节点13标记为簇头节点。

针对节点14，收到节点4发送的“已分簇”消息，节点2的权值也大于节点14的权值，但是未收到节点2发送的“已分簇”消息，所以继续等待；

针对节点2，收到节点13发送的“已分簇”消息，之前收到节点4发送的“已分簇”消息，已收到所有权值大于自身权值的邻居节点发送的“已分簇”消息，继续判断节点2的邻居数量5大于maxn，向欧式距离最近的3个邻居节点发送“簇头存在”消息，即向节点14、节点13和节点12分别发送“簇头存在”消息；向节点4和节点11分别发送“已分簇”消息。同时节点2标记为簇头节点。

针对节点3，收到节点13发出的“已分簇”消息，节点11的权值也大于节点3的权值，但是未收到节点11发送的“已分簇”消息，所以继续等待；

针对节点14，收到节点8发送的“已分簇”消息，未收到节点2发送的“已分簇”消息，却收到节点2发送的“簇头存在”消息；则向所有邻居节点(节点2，节点8和节点4)发送“已分簇”消息，并将节点14标为成员节点。

针对节点15，收到节点13发出的“簇头存在”消息；则向所有邻居节点(节点3和节点13)发送“已分簇”消息，并将节点15标为成员节点；

针对节点3，收到节点15发出的“已分簇”消息，但是未收到节点11发送的“已分簇”消息，所以继续等待；

针对节点11，收到节点2发出的“已分簇”消息，已收到所有权值大于节点11权值的邻居节点发送的“已分簇”消息，继续判断节点11的邻居数量4不大于maxn，向所有邻居节点节点12、节点2和节点3和节点5分别发送“簇头存在”消息；同时节点11标记为簇头节点。

针对节点12，收到节点2或节点11发送的“簇头存在”消息；则向所有邻居节点(节点11和节点2)发送“已分簇”消息，并将节点12标为成员节点；

针对节点3，收到节点11发出的“簇头存在”消息；则向所有邻居节点(节点15，节点13和节点11)发送“已分簇”消息，并将节点3标为成员节点。

针对节点5，收到节点11的“簇头存在”消息；向邻居节点11发送“已分簇”消息，并将节点5标为成员节点；

步骤六、判断标记后的节点i是否为簇头节点，如果是进入步骤七，否则为成员节点进入步骤八；

本实施中，节点2，节点4，节点9，节点11和节点13为簇头节点；其余均为成员节点；节点在自身和所有邻居节点均完成选举阶段后开始进入入簇阶段。

步骤七、执行簇头节点i的入簇阶段；

通过选举阶段已收集到自身和邻居节点的信息，设未入簇邻居节点的数量为d个，簇头初始状态s为0，已入本簇的成员节点数量为n；开始接收消息，若收到已入簇消息则d－1；若收到请求入簇消息则n+1，且回复允许入簇消息。直到n值达到新的门限值，则s+1，且向所有未入簇邻居节点发送状态改变消息；当d＝0或s＝3时，即所有邻居成员节点完成入簇或自身负载饱和时，该簇头完成入簇阶段。

如图4所示，具体步骤如下：

步骤701、设置簇头节点i的状态s_i为0，已入簇的邻居节点数量n_i为0，统计邻居节点中未入簇的成员节点，数量为d_i；

步骤702、判断节点i未入簇成员节点数量d_i是否为0或簇头状态s_i是否为3，如果是，簇头节点i的入簇阶段结束；否则进入步骤703；

步骤703、判断节点i已入簇节点数量n_i是否大于等于当前簇头状态s_i所对应的门限数量；如果是，则当前簇头状态s_i加1，并向所有邻居节点发送包含当前簇头状态信息的“状态改变”消息；返回步骤702；否则，进入步骤704；

当前簇头状态s_i的值分别为0，1，2和3；簇头状态0对应的门限数量为小于最小规模门限minn值；簇头状态1对应的门限数量为大于等于最小规模门限minn值到小于最佳规模门限pren值；簇头状态2对应的门限数量为大于等于最佳规模门限pren值到小于最大规模门限maxn值；簇头状态3对应的门限数量为大于等于最大规模门限maxn值；

步骤704、判断是否收到簇头节点i的邻居节点j发送的“已入簇”消息，如果是，则未入簇成员节点个数d_i减1，返回步骤702，否则进入步骤705；

步骤705、判断是否收到簇头节点i的邻居节点j发送的“请求入簇”消息，如果是，则已入簇的邻居节点数量n_i加1，并向邻居节点j发送“允许入簇”消息，返回步骤702；否则返回步骤704；

步骤八、执行成员节点i的入簇阶段；

通过选举阶段已收集到自身和邻居节点的信息，共有D个负载未饱和的簇头；即s<3；若D＝0，即不存在负载未饱和的簇头，成员节点悬空；若D＝1，则直接发送入簇请求，否则向s最小的邻居簇头中欧式距离最近的一个发送入簇请求；若收到回复的允许入簇信息，则向其余邻居簇头发送已入簇信息，完成入簇；否则若收到状态改变信息则更新D再次判断。

如图5所示，具体步骤如下：

步骤801、针对成员节点i，统计簇头状态s_i不为3的簇头节点数量为D_i；

根据收到的“簇头存在”消息统计邻居节点中的簇头节点数量；

步骤802、针对节点i，判断簇头节点数量D_i是否等于0，如果是，则将节点i标记为“悬空节点”，节点i完成入簇阶段；否则进入步骤803；

步骤803、针对某个节点i，根据收到的“状态改变”消息更新邻居节点的状态表，从中找出邻居节点中簇头状态最小的“簇头节点”中欧式距离最近的节点j，向节点j发送“请求入簇”消息；

步骤804、针对某个节点i，判断是否收到节点j返回的“允许入簇”消息，如果是，向所有其它邻居发送“已入簇”消息，节点i完成入簇阶段；否则进入步骤805；

步骤805、针对某个节点i，判断是否收到节点j返回的“状态改变”消息，如果是，进入步骤806，否则回到步骤804；

步骤806、针对某个节点i，判断是否收到邻居节点发送的簇头状态更新为3的“状态改变” 消息，如果是，簇头状态不为3的“簇头节点”个数D_i减1，返回步骤802，否直接回到步骤802；

针对某个未入簇的成员节点m有邻居簇头节点n，当节点n的已入簇节点数量s_n达到最大规模门限maxn值时，节点n的簇头状态将变为3，即节点n所在簇达到饱和，不再接收其它节点的“请求入簇”消息，同时向节点m发送簇头状态更新为3的“状态改变”消息，节点m收到此消息后将簇头状态不为3的“簇头节点”个数D_m减1，即不再考虑加入节点n所在簇。该情况在本实例中未出现。在实际情况中，因节点间关系的变化和门限值的设定的不确定，有可能出现该情况。

按照节点自身和所有邻居节点完成选举阶段的时间顺序，成员节点1、节点6、节点7、节点10最先同时申请入簇，簇头节点9最先允许入簇；然后成员节点8、节点12和节点14同时申请入簇，簇头节点2和节点4允许入簇；最后成员节点3、节点5和节点15同时申请入簇，簇头节点11和节点13允许入簇。

具体过程如下：

针对节点1，统计它的簇头节点数量D₁为2，分别为节点4和节点9；根据节点4和节点9簇头状态相同，选择欧式距离最近的节点4发送“请求入簇”消息；节点4未回应，节点1等待；

针对节点6的簇头节点数量D₆为1，只有节点9，发送“请求入簇”消息；

针对节点7的簇头节点数量D₇为1，只有节点9，发送“请求入簇”消息；

针对节点10，统计簇头节点数量D₁₀为2，分别为节点4和节点13；根据节点4和节点13簇头状态相同，选择欧式距离最近的节点4发送“请求入簇”消息；节点4未回应，节点10等待；

节点9初始簇头状态s₉为0，已入该簇的邻居节点数量n₉为0，邻居节点中未入簇的成员节点d₉为3，分别为节点6，节点7和节点1；当前簇头状态s₉所对应的门限值为2，进入步骤705，收到节点6发送的“请求入簇”消息，将邻居节点数量n₉加1，并向邻居节点6发送“允许入簇”消息；节点6发送“已入簇”消息给所有邻居节点，d₉减1，为2；节点6入簇阶段完成；节点9继续等待下一个请求入簇的节点；

节点9簇头状态s₉为0，已入该簇的邻居节点数量n₉为1，邻居节点中未入簇的成员节点d₉为2，分别为节点7和节点1；当前簇头状态s₉所对应的门限数量为2，进入步骤705，收到节点7发送的“请求入簇”消息，将邻居节点数量n₉加1，变为2；并向邻居节点7发送“允许入簇”消息；节点7发送“已入簇”消息给所有邻居节点，d₉减1，为1；节点7入簇阶段完成；

节点9返回步骤702继续，目前节点9已入簇节点数量n₉等于当前簇头状态s₉所对应的 门限值2；则当前簇头状态s₉加1，并向所有邻居节点(节点6，节点7和节点1)发送包含当前簇头状态信息的“状态改变”消息；再次返回步骤702，此时s₉加1后变为3，目前的n₉(2)小于当前簇头状态s₉所对应的门限值3；节点9继续等待下一个请求入簇的节点；

然后成员节点8、节点12和节点14同时申请入簇，簇头节点2和节点4允许入簇；

针对节点8，统计簇头节点数量D₈为1，只有节点4，发送“请求入簇”消息；节点4未回应，节点8等待；

针对节点12，统计簇头节点数量D₁₂为2，分别为节点2和节点11；根据节点2和节点11簇头状态相同，选择欧式距离最近的节点11发送“请求入簇”消息；

针对节点14，统计簇头节点数量D₁₄为2，分别为节点2和节点4；根据节点2和节点4簇头状态相同，选择欧式距离最近的节点2发送“请求入簇”消息；

节点2初始簇头状态s₂为0，已入该簇的邻居节点数量n₂为0，邻居节点中未入簇的成员节点d₂为2，分别为节点14和节点12；当前簇头状态s₂所对应的门限值为2，进入步骤705，收到节点14发送的“请求入簇”消息，将邻居节点数量n₂加1，并向节点14发送“允许入簇”消息给所有邻居节点；节点14发送“已入簇”消息，d₂减1，为1；节点14入簇阶段完成；节点2继续等待下一个请求入簇的节点；

针对节点4，收到节点14发送的“已入簇”消息，d₄减1；

节点4初始簇头状态s₄为0，已入该簇的邻居节点数量n₄为0，邻居节点中未入簇的成员节点d₄为3，分别为节点10，节点8和节点1；因为节点14已经入簇，所以未入簇的成员节点就不包括节点14了。当前簇头状态s₄所对应的门限值为2，进入步骤705，收到节点10发送的“请求入簇”消息，将邻居节点数量n₄加1，并向邻居节点10发送“允许入簇”消息；节点10发送“已入簇”消息给所有邻居节点，d₄减1，为2；节点10入簇阶段完成；节点4继续等待下一个请求入簇的节点；

针对节点13，收到节点10发送的“已入簇”消息，d₁₃减1；

节点4簇头状态s₄为0，已入该簇的邻居节点数量n₄为1，邻居节点中未入簇的成员节点d₄为2，分别为节点8和节点1；当前簇头状态s₄所对应的门限数量为2，进入步骤705，收到节点8发送的“请求入簇”消息，将邻居节点数量n₄加1，变为2；并向邻居节点8发送“允许入簇”消息；节点8发送“已入簇”消息给所有邻居节点，d₄减1，为1；节点8入簇阶段完成；节点4继续返回步骤702，目前节点4已入簇节点数量n₄等于当前簇头状态s₄所对应的门限值2；则当前簇头状态s₄加1，并向所有邻居节点(节点10，节点8、节点1、节点13、节点14、节点2)发送包含当前簇头状态信息的“状态改变”消息；再次返回步骤702，此时s₄加1后n₄(2)小于当前簇头状态s₄所对应的门限值3；节点4继续等待下一个请求入簇的节点；

针对节点1，均收到节点4和节点9发送的“状态改变”消息；邻居节点的簇头状态相同(均为1)，选择向欧式距离较近的节点4发送“请求入簇”消息；

节点4簇头状态s₄为1，已入该簇的邻居节点数量n₄为2，分别为节点8和节点10，邻居节点中未入簇的成员节点d₄为1，为节点1；当前簇头状态s₄所对应的门限数量为3，进入步骤705，收到节点1发送的“请求入簇”消息，将邻居节点数量n₄加1，变为3；并向邻居节点1发送“允许入簇”消息；节点1发送“已入簇”消息给所有邻居节点，d₄减1，为0，完成入簇阶段；

针对节点9，收到节点1发送的“已入簇”消息，d₉减1，变为0，完成入簇阶段；

最后成员节点3、节点5和节点15同时申请入簇，簇头节点11和节点13允许入簇。

针对节点3，统计簇头节点数量D₃为2，分别为节点11和节点13；根据节点11和节点13簇头状态相同，选择欧式距离最近的节点13发送“请求入簇”消息；

针对节点5的簇头节点数量D₅为1，只有节点11，发送“请求入簇”消息；

针对节点15的簇头节点数量D₁₅为1，只有节点13，发送“请求入簇”消息；

节点11初始簇头状态s₁₁为0，已入该簇的邻居节点数量n₁₁为0，邻居节点中未入簇的成员节点d₁₁为3，分别为节点12，节点3和节点5；当前簇头状态s₁₁所对应的门限值为2，进入步骤705，收到节点12发送的“请求入簇”消息，将邻居节点数量n₁₁加1，并向邻居节点12发送“允许入簇”消息；节点12发送“已入簇”消息给所有邻居节点，d₁₁减1，为2；节点12入簇阶段完成；节点11继续等待下一个请求入簇的节点；

针对节点2，收到节点12发送的“已入簇”消息，d₂减1，变为0，完成入簇阶段；

节点11簇头状态s₁₁为0，已入该簇的邻居节点数量n₁₁为1，邻居节点中未入簇的成员节点d₁₁为2，分别为节点3和节点5；当前簇头状态s₁₁所对应的门限数量为2，进入步骤705，收到节点5发送的“请求入簇”消息，将邻居节点数量n₁₁加1，变为2；并向邻居节点5发送“允许入簇”消息；节点5发送“已入簇”消息给所有邻居节点，d₁₁减1，为1；节点5入簇阶段完成；节点11继续返回步骤702，目前节点11已入簇节点数量n₁₁等于当前簇头状态s₁₁所对应的门限值2；则当前簇头状态s₁₁加1，并向所有邻居节点发送包含当前簇头状态信息的“状态改变”消息；再次返回步骤702，此时s₁₁加1后n₁₁(2)小于当前簇头状态s₁₁所对应的门限值3；继续等待下一个请求入簇的节点；

节点13初始簇头状态s₁₃为0，已入该簇的邻居节点数量n₁₃为0，邻居节点中未入簇的成员节点d₁₃为2，分别为节点3和节点15；因为节点10已经入簇，故节点13的未入簇邻居不包括节点10；当前簇头状态s₁₃所对应的门限值为2，进入步骤705，收到节点3发送的“请求入簇”消息，将邻居节点数量n₁₃加1，并向邻居节点3发送“允许入簇”消息，节点3发送“已入簇”消息给所有邻居节点，d₁₃减1，为1；节点3入簇阶段完成；节点13继续等待下一个 请求入簇的节点；

针对节点11，收到节点3发送的“已入簇”消息，d₁₁减1，变为0，完成入簇阶段；

节点13簇头状态s₁₃为0，已入该簇的邻居节点数量n₁₃为1，邻居节点中未入簇的成员节点d₁₃为1，为节点15；当前簇头状态s₁₃所对应的门限数量为2，进入步骤705，收到节点15发送的“请求入簇”消息，将邻居节点数量n₁₃加1，变为2；并向邻居节点15发送“允许入簇”消息；节点15发送“已入簇”消息给所有邻居节点，d₁₃减1，为0，完成入簇阶段。

最终形成的簇如下：

簇头2的成员为节点14；簇头4的成员为节点10，节点1和节点8；簇头9的成员为节点6和节点7；簇头11的成员为节点5和节点12；簇头13的成员为节点3和节点15。

本发明中的门限不是预设值，而是预设规则，具体门限值由每个簇头根据规则自适应生成。成员节点入簇不是看分簇信息达到先后，而是根据所有邻居簇头所处状态(门限阶段)来选择。

本发明在门限法和加权法的基础上提出，针对无定形扁平化自组织无线网络中的同质节点组成的网络结构。如图6所示，为本发明ALB算法与AOW算法的负载平衡因子(LBF，Load Balancing Factor)随通讯距离的变化情况。实验环境为：假设网络中的100个节点均匀分布在一个10002单位距离的区域中，通讯距离从200变化至500，既要保证节点之间全联通，又要使节点之间不完全一一互为邻居节点。因为LBF值仅反应簇头对成员数量的负载情况，所以实验中设置为节点初始状态相同。

从图中可见，两个算法的LBF都随着节点个数的增多、通讯距离的增大而呈下降趋势。这是因为节点个数会使簇的数量增加，而通讯距离的增大虽然会减小簇的数量，但也会使各个簇的成员数差距增大，故而LBF会减小。而ALB算法在各个阶段的LBF值都要高于AOW算法，即负载均衡性高于AOW算法。