自组织网络中的自适应分簇路由算法

田斌鹏 黄盛 王昭

1.航空工业第一飞机设计研究院陕西西安710089 2．中国西南电子技术研究所四川成都610036

自组织网络是由若干个移动节点通过分布式网络协议自发组成的一个无中心多跳网络.自组织网络能够高效地处理网络拓扑变化、传输链路故障等问题,具有很强的灵活性和抗毁性.无线自组织网络环境下,节点间的无线链路及网络拓扑结构随节点的位置移动、信道的变化等因素呈现出动态变化的特性,需通过有效的路由算法保障网络节点之间的连通性[1−5].

无线自组织网络具有两种不同的层次结构:平面路由结构和分层路由结构[6−8].在平面路由结构中,所有节点的地位平等,每个节点都需要知道到达其他所有节点的路由,需要维护大量的动态路由控制信息;网络规模越大,路由维护的开销就越大,所以平面路由结构的网络可扩展性较差.分级路由结构需要相应的分簇算法和簇维护机制,簇头负责本簇内成员节点之间的通信,以及本簇成员节点和其他簇成员节点间的通信[9−11].姜春晓等研究了路由算法对提升未来天基指挥控制网络效率的重要性[12].分簇路由技术是提高自组织网络效率的有效手段,它可以有效地降低网络复杂度,减小路由开销[13−15].

1 系统模型

1.1 网络模型

图1 多跳自组织网络拓扑示意图Fig.1 Network Topology of multi-hop self-organization networks

本文研究由U个节点构建的多跳自组织网络,节点集合定义为U={1,2,···,U}.所有节点可通过自组织网络协议周期地与一跳邻居节点交互控制包信息,如图1所示.在多跳自组织网络中,每个网络节点配置了环境感知、自学习和自决策3 大功能模块,如图2所示.各个网络节点周期地利用无线传输模块与邻居节点交互路由控制信息,由环境感知功能模块统计邻居节点的分簇控制信息,再由自学习功能模块将所有邻居节点的分簇控制信息提炼成局部网络的分簇状态变化信息,最终由自决策功能模块依据本节点当前的分簇角色,以及相应的分簇状态转移条件,自适应地调整本节点的分簇状态,使得全部网络节点能够依据邻居列表信息,自适应地处理网络拓扑的动态变化和网络分簇状态变化,实时地优化簇头选择与分簇结果.

图2 网络节点的功能结构Fig.2 Function structure of network nodes

1.2 问题描述

多跳自组织网络在网络拓扑结构动态变化的情况下,如何分布式地选择分簇簇头、实时地优化节点分簇状态及分簇链接关系,自适应地完成簇头选择、簇头替换、簇头切换、分簇裂变、分簇合并等流程,从而达到均衡分簇规模并保障网络连通性的目标.

2 自适应分簇路由算法

自适应分簇路由算法利用分簇控制信息交互触发网络节点,依据分簇状态转移条件和转移流程实时地更新本节点,分簇状态及分簇链接关系.

2.1 分簇控制信息

分簇控制信息如表1所示,包含该节点的簇头权值、分簇状态及目的节点ID、连通簇头集合和邻居列表.其中,簇头权值表示该邻居节点适合担任簇头节点的程度,簇头权值越高的节点越适合在自组织网络中担任簇头节点;分簇状态包含申请入簇、簇成员、簇头、簇头替换、簇头切换、分簇裂变和分簇合并共7 种状态,分簇状态及目的节点ID 表明了该邻居节点的分簇角色与该邻居节点正在执行的分簇操作,以及配合其完成分簇操作的目的节点;连通簇头集合包含该邻居节点能够连通的所有簇头节点,可用于判断分簇结构在自组织网络中的连通性;邻居列表包含该邻居节点的所有邻居节点,表明了该邻居节点在自组织网络中的局部拓扑结构.

表1 分簇控制信息示例Table 1 Cluster control information

2.2 节点分簇状态转移条件

在多跳自组织网络中,任意节点收到邻居节点的分簇控制信息后,由自学习功能模块提取邻居列表信息、分簇状态信息、连通簇头信息和簇头权值信息,并依据节点分簇状态转移条件,分析本节点两跳范围内的局部网络的分簇状态变化信息.

1)簇头替换条件:本节点的邻居节点及本节点组成的集合,是某个邻居簇头及其邻居节点组成的集合的真超集.

2)成功入簇条件:本节点指定的簇头的分簇状态为簇头,并且该簇头的邻居列表信息包含本节点ID.

3)簇头切换条件:本节点的所有邻居簇头之间是连通的,并且所有邻居簇头以及它们的邻居节点的并集是本节点及本节点的邻居节点组成的集合的超集.

4)分簇裂变条件:本节点为簇头且收到了新的入簇申请,并且当前簇成员的数目加上新入簇成员的数目,将达到预设的最大簇成员容量限制.

5)分簇合并条件:当前控制周期内存在邻节点的连通簇头集合中的最小节点ID,不等于本节点的连通簇头集合中的最小节点ID.

6)邻簇合并状态:当前控制周期内存在邻簇的簇头的分簇状态为分簇合并,则邻簇合并状态的判断结果为存在邻簇处于合并状态.

2.3 节点分簇状态转移流程

在多跳自组织网络中,网络节点依据本节点分簇角色与分簇状态转移条件,自适应地执行分簇路由流程,完成申请入簇、提升簇头、簇头替换、簇头切换、分簇裂变、分簇合并等分簇状态更新行为,优化全网分簇路由结构,如图3所示.

2.3.1 待入簇节点

待入簇节点的分簇状态转移流程如下:

1)待入簇节点判断簇头替换条件;若簇头替换条件满足,则本节点的分簇角色提升为簇头节点;否则,待入簇节点继续判断候选簇头集合是否非空.

图3 节点分簇状态转移流程Fig.3 Transition process of node cluster states

2)若本节点的候选簇头集合为空,则本节点的分簇角色提升为簇头节点;否则,待入簇节点继续选择合适的簇头.

3)待入簇节点从候选簇头集合中选择簇头权值最大的簇头作为本节点指定的簇头,并通过本节点的分簇控制信息申请加入该分簇.

2.3.2 申请入簇节点

申请入簇节点的分簇状态转移流程如下:

1)申请入簇节点判断成功入簇条件;若成功入簇条件满足,本节点的分簇角色设置为簇成员节点;否则,申请入簇节点更新候选簇头集合.

若本节点的候选簇头集合为空,则本节点的分簇角色提升为簇头节点.

否则,本节点从候选簇头集合中选择簇头权值最大的簇头作为本节点指定的簇头,并通过本节点的分簇控制信息申请加入该分簇.

2.3.3 簇成员节点

簇成员节点的分簇状态转移流程如下:

1)若簇成员节点收到了本簇簇头的切换消息,则本节点以待入簇节点的身份执行分簇状态转移.

2)否则:

上述分析表明，四大自贸试验区在“一带一路”建设中的定位有所不同，因此，各个自贸试验区应根据自身优势及战略定位，差异化参与和推动“一带一路”建设。

a)若簇成员收到了本簇裂变消息,则本节点依据裂变消息与邻居列表信息执行如下操作:

①若本节点为本簇簇头指定的新簇头,则本节点将分簇角色提升为簇头节点.

②否则,若新簇头为本节点的邻居节点,则本节点将分簇控制信息的目的节点ID 更换为新簇头ID.

③否则,本节点保持分簇控制信息的目的节点ID 为原簇头ID.

b)否则,本节点判断分簇合并条件与邻簇合并状态:

①若分簇合并条件满足并且无邻簇处于合并状态,则本节点触发分簇合并流程,本节点的分簇角色提升为簇头节点,分簇合并流程将无连通链路的两个分簇的边缘节点提升为簇头节点,为这两个分簇构建连通链路,实现分簇间的数据中继传输.

②否则,本节点的分簇角色保持为簇成员节点.

2.3.4 簇头节点

簇头节点的分簇状态转移流程如下:

1)簇头节点判断簇头切换条件;若簇头切换条件满足,则本节点触发簇头切换流程,簇头切换流程指导本簇的簇成员加入其他邻居簇头节点来优化分簇结构;否则,本节点继续判断分簇裂变条件.

2)若分簇裂变条件满足,则本节点触发分簇裂变流程,分簇裂变流程指导本簇的簇成员构建新分簇来均衡网络分簇规模,本节点从本簇的簇成员中选择邻居节点数最多的节点作为新簇头,通知新簇头及本簇的簇成员进行分簇裂变;否则,本节点继续判断分簇合并条件.

3)若分簇合并条件满足,则本节点将分簇控制信息的目的节点ID 设置为连通簇头集合的最小ID,与本节点的连通簇头集合的最小ID 不一致的邻居节点的ID,并将本节点连通簇头集合更新为本节点的连通簇头集合,与目的节点ID 的连通簇头集合的并集,通过交互分簇控制信息完成分簇合并;否则,本节点保持为簇头节点.

3 仿真结果与数值分析

3.1 仿真设置

利用OPNET 仿真软件,验证自适应分簇路由算法在路由收敛时间和网络开销上的性能.在OPNET仿真软件中构建了32 个节点的栅格拓扑结构网络场景,并且设置32 个节点在1 s 时刻同时开机,各个节点在完成入网操作后,通过执行自适应分簇路由算法来构建本节点的路由表.

3.2 仿真结果

图4 全网节点路由收敛时间Fig.4 Route convergence time for whole network nodes

图5 全网节点平均路由信息开销Fig.5 Average cost of route information for whole network nodes

如图4和图5所示,所有网络节点在开机后,各个网络节点通过交互分簇控制信息迅速地发现其他网络节点,在约30 s 时刻全网节点可达的平均目的节点个数已经达到30 个.此时,由于网络拓扑中新入网的成员迅速增多,导致分簇状态中簇头成员比例较高,因此,平均路由开销最高.随着在网成员数逐渐稳定,网络成员自适应地依据实时网络拓扑状态完成分簇状态转移.在50 s 时刻全网节点即可获得所有其余31 个目的节点的路由信息,网络分簇结构能够收敛至稳定的状态,全网平均路由开销也逐渐下降至较优值.当全网路由信息收敛时,32 个节点的分簇状态及分簇链接关系如图6所示.

图6 分簇拓扑仿真结果Fig.6 Simulation results of clustered topology

4 结论

在多跳自组织网络中,提出了一种自组织网络的自适应分簇路由算法,通过优化分簇控制信息、节点分簇状态转移条件和节点分簇状态转移流程,使得网络节点的路由信息能够实时地匹配网络拓扑与链路状态的变化,优化簇头选择和分簇链接关系,从而达到均衡分簇规模并保障网络连通性的目标.通过OPNET 仿真验证,本文提出的自适应分簇路由算法具有快速收敛的优点,全网平均路由开销可快速收敛至较优值.