基于模糊决策的网络簇首选举算法

丁晟皓，李小南

基于模糊决策的网络簇首选举算法

丁晟皓，李小南

（西安电子科技大学，西安 710026）

分级分簇网络是目前最为常见的自组织网络架构，簇首选举是其网络管理的关键技术。研究比较了常用的簇首选举算法，提出了一种基于模糊决策的复合加权簇首选举算法。在对节点诸多评价因素进行分析的基础上，建立了模糊评判模型，详细描述了算法的实现流程，并通过仿真验证了算法的适用性。

无线自组织网络；簇首；加权分簇；模糊决策

0 引言

移动自组织网络（Ad Hoc网络）作为一种分布式自组织的无线网络，是当前通信网络领域研究的热点之一。按照拓扑结构，Ad Hoc网络一般分为平面网络和分级网络。平面网络结构简单，如图1所示，所有节点地位均等，节点间通过路由实现消息交互。当节点数目较多，又处于移动状态时，其路由维护会变得非常困难。因此，平面结构可扩充性较差，只适用于规模较小的Ad Hoc网络。分级网络是将整个网络划分为若干个簇，每个簇由一个簇首和多个簇成员组成，这些簇首还可以组成更高一级的网络，因此也称为分级分簇结构。一种典型的分级分簇网络如图2所示。在分级网络中，簇首负责维护管理簇内各成员的资源分配和链路信息，同时负责簇间的通信，而簇成员只负责采集、处理和向簇首传递数据[1-3]。

图1 平面网络

与平面网络相比，分级网络具有更好的可扩充性，其网络规模不受限制，可通过增加簇的个数和网络的级数来增加网络成员数量。由于节点角色分工不同，簇成员数量虽多，但功能比较简单，从而大大降低了网络的维护成本。而且各簇相对独立，使路由信息局部化，有效减少了路由协议的开销，因此，随着网络规模的日益扩大，分级分簇网络已成为目前最为常见的网络架构。

图2 分级网络

分级网络中网络管理的关键技术是通过分簇算法和分簇保持实现整个网络的快速部署以及拓扑结构变化后的动态重建。从分级网络的结构可以看出，簇首在网络的管理和通信中承担重要的任务，是网络中的关键节点。因此，如何选举簇首则成为分级网络需要解决的首要问题。

1 典型簇首选举算法介绍

分级分簇网络是将网络划分为逻辑上的若干个簇，各个簇中都有一个节点被选举为簇首，是否合理的簇首选举算法能够决定网络的总体性能。一般而言，簇首选举需依赖具体应用的需求、网络的环境和节点的特征。下面介绍几种典型的簇首选举算法。

1）最小ID的簇首选举算法

最小ID算法是一种简单的簇首选举算法。在网络中，每个节点都分配了唯一的ID号，相邻节点中选举具有最小ID的节点作为簇首。并且在某些特殊情况下，现有簇首损毁或卸任时，可以将其职责继续交付给其簇内具有最小ID的成员节点，这种簇首选举算法计算量小，实现方便，算法收敛较快，而且簇首更新的频率较慢，维护开销很小。但是由于该算法倾向于选举具有较小ID的节点作为簇首，因而所选举的簇首节点相对固定，使得这些节点会消耗更多的电池能量，导致在一定时间后它将无法继续工作，从而缩短整个网络的生存时间。

2）最大节点度簇首选举算法

最大节点度算法不再简单地根据簇ID来选举簇首，而是以邻居节点数量来作为簇首选举的标准。首先计算节点连通的邻居节点数目，即节点度；再选举具有最大邻居节点数目的节点作为簇首，具体描述如下：

在个节点组成的集合中，每个节点通过消息的交互得到一个连通矩阵，如式（1）所示

式中，

定义节点的节点度如式（2）所示

若第节点的节点度满足式（3），则该节点被选举为簇首

相比最小ID的簇首选举算法，最大节点度算法选出的簇首具有较好的连通性，可以减小簇内消息转发的资源开销。但当节点移动速度较快时，由于簇拓扑结构的变化，导致簇首频繁更新，维护开销会急剧增加。

一般情况可以将最小ID算法和最大节点度算法结合起来进行簇首选举。首先根据节点度进行比较，当节点度相同时，再根据簇ID的大小进行选取。这种结合在算法上虽然进行了优化，但在实际应用场景中并没有改善簇的稳定性。

3）最低移动性簇首选举算法

为了适应节点的移动特性，提高簇结构的稳定性，可以根据节点的移动性来选举簇首。最低移动性簇首选举算法规定，节点的移动性越高，其分配的权重越低，最终选举权重最高的节点作为簇首。这种算法需要量化节点的移动性。最简单的方法是将节点相对速度绝对值的时间平均作为移动性，但这需要获取节点的位置信息，不是所有的应用环境都具备这个条件。因此最低移动性簇首选举算法具有一定的局限性，并且只适用于计算量小的场合。

4）基于能量消耗的簇首选举算法

前面介绍的几种簇首选举算法中都没有考虑负载平衡等因素，使得作为簇首的节点负担较重，很容易能量耗尽。为了解决此问题，基于能量消耗的簇首选举算法为簇首的生存时间设定一个阈值，当簇首节点承担簇首功能的时间超过此阈值时，卸任簇首功能，并将簇首转让给其他符合簇首要求的节点。该算法使簇首的负载分布相对更为均匀，增强了簇的稳定性。

5）加权簇首选举算法

以上几种算法中，簇首的选举只考虑使用单一属性作为标准。为了适应多样化的无线自组网的应用场景，可以采用一种组合的加权簇首选举算法，综合考虑节点度、移动性和能耗等多方面因素来选举簇首。加权簇首选举算法采用权值表示每个节点适合充当簇首的程度，选择权值最大的节点作为簇首，权值的计算方法如式（4）所示

加权簇首选举算法中，每个权重系数根据具体应用选用合适数值，并且可根据需要增加更多的变量，提高了算法适应性。同时通过多种因素的综合考虑，提高了分簇结构的稳定性。但在加权簇首选举算法中，如何确定各属性所占权重是个难题，同时权值的计算和存储也需要额外的成本。

2 基于模糊决策的加权簇首选举算法

从上述选举算法的比较可以看出，由于网络环境和业务需求的多样化，加权簇首选举算法的应用价值十分广泛。在传统的加权簇首选举算法中，各属性都是用一个确切的数值表示, 并用确定的系数来表示这些确切数值的权重。但在现实网络中,节点不断移动,每个节点的电量也不断变化，这些属性很难使用常规算式表示。各权重值也是根据开发者对网络环境和节点设备的认知以及经验进行选取的，标准不易界定。在考虑的属性较多时, 很难给出合理的权重值分配,导致评价结果过于简单和主观。

为了对各种属性进行综合客观的评价,相对真实地反映出各属性在簇首选举中的地位，本文设计了一种基于模糊决策的簇首选举算法，采用模糊集表示各节点的评价，建立模糊评价模型，从而得到评价结果。模糊决策是一种将一空间输入映射到另一空间输出的规则,模糊性反映事物的不确定性和不精确性,因而对动态的自组织网络有很好的 适应性。

2.1 模糊评价模型

为了使用更恰当的模型描述不确定性概念，美国控制论专家Zadeh于1965年第一次提出了模糊集合的概念[6]。与只有“属于”和“不属于”这两种状态的经典集合不同，模糊集使用隶属度函数描述元素对集合的隶属程度，该函数为每个元素分配一个介于0～1之间的隶属度，以此度量各元素对集合的隶属程度高低。

综合评价是指使用系统规范的方法对多个指标与单位建立指标体系，对它们同时进行评价。若使用的指标集为模糊集，则称为模糊评价。

对某个对象进行综合评价，需要考虑三个要素：

从属性集到评价集的评价矩阵如式（5）所示

由于各属性的重要程度不同, 因此需要进行加权处理，权重系数用式（6）的权重矩阵表示为

将权重矩阵与评价矩阵相乘，可得到对各属性的综合评价矩阵，如式（7）所示

2.2 模糊决策算法

基于模糊决策的网络簇首选举算法采取综合评价的方式，选举得分最高的节点成为簇首。

首先根据网络的实际情况，选取合理的评价因素。按照一般自组网的常用特性，本文主要考虑五个因素：节点度、节点移动性、节点中心度、链路波动性和节点剩余电量。

1）节点度：节点度是指节点通信范围内的节点个数，也就是节点的一跳邻居个数，通过连通表获得。

2）节点移动性：为了避免频繁的簇首改变，应该选举移动速率相对较低的节点担任簇首，以保持簇的稳定性。节点的移动性可通过在过去时间段内的移动速率平均值来衡量。

3）节点中心度：中心度是指与邻居节点的平均距离。中心度越高，簇首与邻居节点的平均距离越小，节点之间结构越紧密，链路由于节点移动发生断裂的可能性越小，则拓扑结构相对较稳定。

4）链路波动性：链路波动性由链路生存时间表示。链路生存时间越长，波动性越小，则网络越稳定。

5）节点剩余电量：剩余电量越多，节点生存时间越长。由于簇首承担更多的通信任务，其能耗要多于普通节点，因此簇首的选举还需考虑节点的剩余电量情况。

图3 节点度隶属度函数

图4 节点移动性隶属度函数

图5 节点中心度隶属度函数

图6 链路波动性隶属度函数

图7 节点剩余电量隶属度函数

在对关键因素的分析基础上，下一步需要确定各属性的权重。一般情况下，权重值往往是根据用户需求、网络环境、设备特征以及过往经验进行选取，具有一定的主观性。本文提供了一种特征向量法，能够较为客观地确定各项因素的权重，并且具有通用性。具体方法如下：

求出各个评价因素的相关系数矩阵，如式（11）所示

综上所述，基于模糊决策的网络簇首选择算法流程如下：

2）对参与簇首选举的全部个节点，根据其各属性值，得到观测矩阵

3）按照式（8）～式（12）计算得到权重矩阵；

4）针对任一节点，根据各属性的隶属度函数，按照图3～图7计算评价矩阵

7）重复4）～6），直至遍历全部个节点，得到所有节点的综合评分；

8）选举综合评分最高的节点为簇首，若有多个节点评分相同，则其中ID号较小的成为簇首。

2.3 仿真分析

仿真场景设置为一个1 km×2 km的监视区域，随机部署一个簇内8个节点以进行仿真验证。以节点度、节点移动性、节点中心度、链路波动性和剩余能量作为评价因素，其仿真数据如表1所示。

表1 仿真数据

以表1的仿真数据为例，按照本文提出的模糊决策方法，可计算求得权重矩阵为

表2 评价结果

比较评分结果，选举节点5作为簇首。

3 结语

本文根据自组网的特点，在分级分簇网络传统簇首选举方法的基础上,设计了一种基于模糊决策的簇首选举算法。选取节点度、移动性、中心度、链路波动性和剩余能量作为综合评价的关键因素，建立了模糊决策的数学模型，提出了各因素权重的确定方法，并详细介绍了多种因素综合评判的具体实现过程。最后通过仿真实验, 分析验证了该算法的适用性。本文提出的方法能够适合多种环境下的自组织网络，确保簇首选举的合理性和客观性，从而提高网络的整体能效。

[1] 郑少仁，王海涛，赵志峰，等. Adhoc网络技术[M]. 北京：人民邮电出版社，2005.

[2] 姚正纲，等. 一种无线链状网络路由算法的研究与应用[J]. 微计算机信息，2012（1）.

[3] 李建波. 无线传感网络拓扑控制若干问题研究[D]. 北京：中国科学技术大学，2009.

[4] 王露. 大规模无人机集群动态网络技术研究[J]. 现代导航，2022，13（5）：357-362.

[5] Zhao R，Lee H K. Fuzzy-based path planning for multiple mobile robots in unknown dynamic environment[J]. Journal of Electrical Engineering and Technology，2017，12（2）：918-925.

[6] Zadeh L A. Fuzzy sets [J]. Information and control，1965，8（3）： 338-353.

[7] ATANASSOV K T. Intuitionistic fuzzy sets [J]. Fuzzy Sets and Systems，1986，20（1）：87-96.

[8] LI X N，WANG X，LANG G M，et al. Conflict analysis based on three-way decision for triangular fuzzy information systems[J]. International Journal of Approximate Reasoning，2021，132：88-106.

[9] LI X N. Three-way fuzzy matroids and granular computing[J]. International Journal of Approximate Reasoning，2019，114：44-50.

[10] Wang Z X，Liu Y J，Fan Z P，et al. Ranking L-R fuzzy number based on deviation degree[J]. Information Sciences，2009，179（13）：2070-2077.

[11] Bustince H，Barrenechea E，Pagola M，et al. A historical account of types of fuzzy sets and their relationships [J]. IEEE Transactions on Fuzzy Systems，2015，24（1）：179-194.

[12] 张小红. 模糊数学与Rough集理论[M]. 北京：清华大学出版社，2013.

Cluster Head Election Algorithm Based on Fuzzy Decision

DING Shenghao, LI Xiaonan

Classified cluster network is the most common self-organized network architecture, and cluster head election is the key technology of network management. The popular election algorithm is compared and a composite weighted election algorithm based on fuzzy decision is proposed. Based on the analysis of many evaluation factors of nodes, a fuzzy evaluation model is established, and the implementation process of the algorithm is described in detail, and then the applicability of the algorithm is verified through simulation.

Wireless Self-Organizing Network; Cluster Head; Weighted Clustering; Fuzzy Decision

TP393

A

1674-7976-(2023)-05-381-06

2023-04-06。

丁晟皓（1996.05—），江苏睢宁人，硕士，主要研究方向为三支决策与粗糙集。