吴佳楠, 吴 剑, 邸焕双, 王玉英, 李念峰

(长春大学 网络安全学院, 长春 130022)

以自主式水下航行器AUV(autonomous underwater vehicle)[1]为代表的水中机器人, 因具有良好的自主性和灵活性, 已成为一种行之有效的水下探索工具. 张晗等[2]研究了一种新的水下电场通信仿箱鲀机器鱼, 其仿生对象箱鲀鱼有一种特殊的电感知能力, 可通过特殊的放电器官发射一种称为EOD(electric organ discharges)的脉冲式信号, 与同类物种交流信息, 还能主动探测周围环境. 仿箱鲀机器鱼具有体积紧凑、 能耗低、 全向性好等优点, 可只靠0.81 W的发射功率在3～5 m的通信距离上进行约1 KB/s的数据传输. 实现多个仿生机器鱼的智能集群, 协同完成复杂任务是该领域的研究热点[2].

分簇思想是一种有效的群体控制方法, 目前存在的分簇协议从网络拓扑角度可分为两种: 平面路由协议和分簇路由协议[3-4]. 常见的平面路由协议有DD(directed diffusion)[5],SAR(sequential assignment routing)[6],SPIN(sensor protocols for information via negotiation)[7]和K阶生成簇算法等[8]. 该类协议的主要优点是具有良好的健壮性和强连通性, 不易产生瓶颈效应, 适合小规模的网络集群. 但无法针对特定环境进行通信资源的优化, 网络中无管理节点, 网络的动态变化反应速度较慢[9]. 分簇协议的主要优点是簇首负责管理, 大部分簇内成员为“待机”状态, 可节省整个网络的能量[10], 不同的簇相互组合便于分布式管理, 利于扩展[11]. 常见的分簇协议包含簇首产生、 簇形成和数据传输3个阶段. 针对簇首形成的算法[12-13]目前有LEACH(low-energy adaptive clustering hierarchy)[14]及其相关优化算法LEACH-C(LEACH-centralized)[15],HEED(hybrid energy-efficient distributed clustering)[16]算法和CEFL(cluster-head election using fuzzy logic)[17]算法等, 其中LEACH将整个网络的能量消耗分布到每个节点中, 从而有效延长网络生命周期. 针对形成簇阶段的算法有ACMWN(adaptive clustering for mobile wireless networks)[18],PEGASIS(power-efficient gathering in sensor information systems)[19]和HYENAS(hybrid energy-aware sensor network)[20]等, 其中ACMWN算法更简单有效, 每个节点独立运行, 广播交换信息, 基于最小ID选举簇头, 形成簇. 针对数据传输阶段的算法有PEGASIS(power-efficient gathering in sensor information systems),TEEN(threshold sensitive energy efficient sensor network protocol)[21]和APTEEN(adaptive periodic threshold sensitive energy efficient sensor network protocol)[22]等. 上述分簇算法更注重于信息传递过程的优化及基于强连通性的群体节点一体化控制, 虽能有效提高群体控制效率并改善网络性能, 但缺少灵活性.

水下智能集群在实现有效控制节点的前提下, 进一步降低群体内耗实现总体能量的最大化输出, 是其面向实用化的一项重要目标. 为在实现群体的有效协同及灵活控制的同时尽可能减少网络整体能耗, 提升续航能力, 本文提出一种基于逻辑分区的仿箱鲀鱼群负载均衡分簇控制算法. 先采用改进的ACMWN算法实现局部快速分簇, 减少节点间维护报文数量, 降低系统整体开销； 再基于簇内逻辑分区策略, 实现监测、 保障和侦察多区域协同控制, 并结合最小响应时间整编零散鱼群, 优化网络控制体系的同时提高组网灵活性； 最后在维护过程中采用区域节点角色转换机制, 实现网络负载均衡.

图1 仿生鱼体功能模块Fig.1 Function module of bionic fish body

1 仿生鱼体功能模块设计

机器鱼体主要包括初始化器、 事件生成器、 输入/输出模块、 报文分类处理器、 群内成员更新模块、 邻居群表更新模块、 数据库7个组成部分, 如图1所示. 为提高处理效率并减轻系统负担, 整体设计为单进程结构, 各模块间的交互采用函数调用和数据传输的方式. 仿生鱼体各模块功能如下.

1) 初始化器： 初始化机器鱼的身份标识和能量权值, 启动系统.

2) 事件生成器： 生成事件, 驱动算法正常执行； 维护报文队列, 提供函数接口.

3) 输入/输出模块： 调用服务, 解析报文.

4) 报文分类处理器： 从事件生成器接收报文, 通过报文标识判断事件类型, 事件分为更新群内成员事件和更新邻居群表事件.

5) 群内成员表更新模块： 更新群内成员表信息, 群内成员表中信息包括网络号、 群内成员标识、 区标识、 响应时间和能量权值.

6) 邻居群表更新模块： 更新邻居群表信息, 邻居群表信息主要包括邻居群网络号、 响应时间、 网络规模等.

2 基于逻辑分区的分簇算法

2.1 网络参数与定义

本文用G表示图,V表示顶点集,E表示边集,C表示群集, ID表示身份标识,Wn表示能量权值, CH表示簇首标识, CRA表示中心簇首标识,T表示响应时间, Msg表示信息报文.

网络参数设定如下：

1) 簇内机器鱼数量区间设为[cl,cu], 其中cl为下限值,cu为上限值；

2) 机器鱼的电量最低为Pmin, 簇首电量降到Pmin时与监测区节点互换, 监测区或侦察区节点电量降到Pmin时与保障区节点互换；

3) 每条鱼的ID全网唯一；

4) 鱼群采用水下电场通信的工作方式交互信息, 最大有效通信距离为8 m.

定义1网络拓扑可视为由节点和链路构成的图, 记为G=(V,E), 其中:V表示节点集合;E表示链路集合. 任意节点Vi和Vj之间被称为互相通信的一跳邻居时, 当且仅当Vi和Vj之间存在边E(i,j).

定义2(邻居簇) 两个簇通过各自侦察区可建立连接, 即两个簇互为邻居簇.

定义3(簇连接度) 某簇的邻居簇个数称为该簇的簇连接度.

定义4(能量权值) 能量权值为区域角色转换的参考值, 记为Wn. 当簇首或侦察区节点电量降到Pmin时, 选择Wn最大的节点更换区域角色, 表示为

Wn=e1×σP-e2×τT,

(1)

e1+e2=1，

(2)

其中：Wn表示每个节点的权值；e1,e2为(可调节)权值系数；σ,τ为归一化系数；P表示节点当前剩余电量；T表示与簇首的响应时间, 反应其与簇首的距离.

2.2 算法设计

2.2.1 基于ACMWN的快速分簇 该过程基于ACMWN算法分簇思想, 实现局部快速分簇, 减少节点间维护报文数量, 降低系统整体开销. 基于ACMWN的快速分簇过程如下：

步骤1) 初始化信息, 每条鱼Vi具有唯一的IDi；

步骤2) 如果E(i,j)≠Ø, 则Vi向Vj广播自己的ID号；

步骤3) ID号比周围低的节点被选举为簇首CH, CH向邻居节点广播当选簇首的信息MsgA, 收到MsgA的邻居节点加入簇A, 并向簇首CH单播申请加入簇的消息MsgB；

步骤4) 簇首CH对收到消息的MsgB计数, 如果数量达到cu, 则拒绝加入；

步骤5) 如果未达到cu, 则簇首CH对收到的申请节点进行回复, 收到回复的邻居节点加入簇A, 并向附近广播已加入簇A的消息；

步骤6) 其余未成簇的节点重复上述过程, 直至形成所有的簇.

图2 逻辑分区示意图Fig.2 Schematic diagram of logical partition

2.2.2 簇内动态逻辑分区 簇内采用逻辑分区的思想, 划分为监测区MA(monitoring-area)、 保障区GA(guarantee-area)和侦察区RA(reconnaissance-area), 区域间在物理上无明显界限, 个体节点按区域功能转换角色, 不需要物理上的移动, 实现簇内能量均衡, 以提高整体续航能力. 逻辑分区方式如图2所示, 其中: 簇首CH具有维持簇内基本管理的作用, 发布任务, 确定鱼群运动方向； 监测区MA负责实时监控簇首状态, 如果簇首CH电量达到Pmin值, 则与监测区内最大能量权值节点进行角色更换； 侦查区RA负责外联, 并通过传感器探测群体周围环境； 保障区GA的主要功能是更换监测区和侦察区能量到达Pmin的成员角色. 多区域协同及区域节点角色转换机制, 实现了群体网络的负载均衡.

簇内动态逻辑分区过程如下：

步骤1) 在形成簇首CH过程中, 簇首CH的群内成员表具有每个成员的ID号, 簇首CH向每个成员点名, 收到的成员进行回复, 簇首可测算出每条鱼的响应时间T(CH,j)；

步骤2) 簇首CH根据响应时间T(CH,j)大小, 将簇内成员进行逻辑分区, 分为监测区MA、 保障区GA和侦察区RA, 并广播分区信息, 收到信息后的簇内成员Vj根据该信息修改区号标识Tagj.

2.2.3 零散簇间整编 在分簇过程中, 簇的数量区域为[cl,cu], 首次分簇后会留下数量小于cl的鱼群Ci. 为进一步优化控制体系, 结合最小响应时间对零散鱼群进行整编, 优化网络控制体系的同时提高了组网的灵活性.

零散簇间整编过程如下：

步骤1) 鱼群Ci通过侦察区向周围广播申请加入信息MsgC, MsgC中包含群内节点数量；

步骤2) 附近侦察区的机器鱼收到并发现不同于自身网络号的MsgC信息时, 将请求发送给簇首, 簇首判断MsgC中Ci内的节点数量小于等于cl, 则批准加入；

步骤3) 鱼群Ci收到多个反馈信息时, 选择响应时间最短的鱼群加入；

步骤4) 如果无法联系到其他鱼群, 则将成为孤立鱼群, 自主向目标节点行进.

2.2.4 中心簇选举 该过程用于寻找群中簇连接度最大的簇, 作为群体控制中心.

中心簇选举过程如下：

步骤1) 每个簇通过交互信息获得邻居簇的数目, 得到自己的簇连接度；

步骤2) 每个簇将自己的簇连接度向邻居簇广播；

步骤3) 具有簇连接度最大的簇被选为中心簇CRA；

步骤4) 中心簇CRA的一跳邻居簇成为中心簇所组织的成员；

步骤5) 重复上述过程直到所有的簇加入.

3 仿真实验与性能评价

3.1 分簇仿真实验

用MATLAB软件对分簇过程进行仿真, 结果如图3所示, 其中： 蓝色圆点表示初始节点； 黑色圆点表示簇内普通成员； 红色节点表示簇首(CH)； 蓝色星形表示监测区(MA)成员； 黑色圆圈表示保障区(GA)成员； 蓝色三角形表示侦查区(RA)成员. 图3(A)为模拟鱼群入水后的初始随机分布位置； 图3(B)表示快速分簇结果； 图3(C)表示簇内分区过程： 簇首基于成员节点响应时间, 将整个簇划分为监测区、 保障区和侦察区； 图3(D)表示簇间整编过程.

图3 簇的形成与整编Fig.3 Formation and integration of clusters

图4为中心簇选举过程示意图, 其中中心簇首CRA所在簇为中心簇, 每个簇与自己的邻居簇交换簇连接度信息, 簇连接度最大的簇当选为中心簇. 中心簇一跳范围内的簇加入该群, 其他簇通过侦察区找到自己的上级簇, 最终整个鱼群建立联系.

3.2 网络性能分析

为验证本文算法在延长网络能量消耗、 网络生命周期和能量均衡性方面的特性, 选取LEACH算法[14]和LEACH-C算法[17]进行对比实验. 使用MATLAB进行仿真分析, 在300 m×300 m内, 随机模拟400个节点, 每个节点的初始能量为0.5 J, 簇数量上限为20, 下限为5, 共进行1 800轮实验, 节点每次发送4 000 bit的数据.

3.2.1 网络能量消耗 下面用Efs表示自由空间能量,Emp表示衰减空间能量,do表示通信半径,Ei表示节点i的当前能量，ETX表示发射单位报文损耗能量,k表示数据包大小, disij表示节点i和节点j之间的距离,ERX表示接收单位报文损耗的能量，EDA表示多路径衰减能量. 则通信半径为

(3)

发送数据为

(4)

接收数据为

Ei=Ei-(ERX+EDA)×k.

(5)

图4 中心簇选举过程示意图Fig.4 Schematic diagram of election process of central cluster

图5为3种算法网络总能量随运行周期(轮数)的变化曲线. 由图5可见, LEACH和LEACH-C算法随着轮数的增加, 能量下降趋势明显快于本文算法, 在约800轮时所有的节点能量为0, 而本文算法采用能量均衡措施, 能量下降趋势更平缓, 约运行1 000轮时能量为0. 图6为不同算法发送给簇首的报文总数. 由图6可见, 本文算法在初期阶段发送给簇首的报文相对较多, 这主要是由于中心簇形成过程相对复杂, 维护报文较多； 随着轮数的增加, 报文数量相对变少, 最终达到的峰值明显低于其他两种对比算法, 从而减少了网络总体能耗.

图5 不同算法的总能量变化曲线Fig.5 Total energy change curves of different algorithms

图6 不同算法发送给簇首的报文总数Fig.6 Total number of messages send to cluster head of different algorithms

3.2.2 网络生命周期 网络生命周期[23]能反应执行算法过程的节点运行时间, 是评价网络性能的一个重要指标, 而负载均衡有助于延长网络生命周期. 节点的初始化能量为

(6)

图7为3种算法的死亡节点数量随运行周期的变化曲线. 由图7可见, LEACH和LEACH-C算法随着程序的运行死亡节点的增幅明显高于本文算法. 本文设网络生命周期为所有节点失效的时间, 不同算法网络生命周期的对比结果如图8所示. 由图8可见, LEACH和LEACH-C算法的生命周期均约为800轮, 而本文算法的生命周期约为1 000轮. 其他两种算法均在100轮前出现首个失效节点, 而本文算法的首个失效节点出现在500轮后, 相比其他两种算法延迟很多, 表明本文算法群体能耗更少, 工作时间更长, 能有效提高群体协同续航能力.

图7 不同算法死亡节点数随运行周期的变化曲线Fig.7 Curves of number of dead nodes of different algorithms with running cycle

图8 不同算法的节点死亡周期Fig.8 Node death cycle of different algorithms

3.2.3 能量均衡性 本文将网络的平均能量和能量方差相结合对网络的能量均衡性进行评价. 能量均值函数为

(7)

能量方差函数为

(8)

其中Ei(o)为节点i的能量.ME(o)越大,DE(o)越小, 表明该时刻网络的能量均衡性越好. 网络能量的均衡性是对网络负载的分配情况, 均衡效果越好, 越有利于实现最大输出.

图9为不同算法网络均值能量随运行周期的变化曲线； 图10为不同算法网络能量方差随运行周期的变化曲线. 在某轮中, 均值能量越大、 方差越小, 表明该轮网络能量的均衡性越好. 由图9可见, 随着轮数的变化, 本文算法的能量均值始终高于LELACH和LEACH-C算法. 由图10可见： LEACH和LEACH-C算法能量方差开始阶段变化较大, LEACH算法约在60轮到达最高点, LEACH-C算法约在230轮到达最高点, 这两种算法在800轮后能量降为0, 总体上能量方差变化幅度较大； 本文算法开始阶段增幅平缓, 约630轮达到最高点, 1 000轮后降为0, 总体上能量方差变化幅度更小, 表明本文算法具有良好的能量均衡性.

图9 不同算法网络均值能量随运行周期的变化曲线Fig.9 Curves of network mean energy of different algorithms with running cycle

图10 不同算法网络能量方差随运行周期的变化曲线Fig.10 Curves of network energy variance of different algorithms with running cycle

综上所述, 为降低节点间负载不均衡性所导致的能量损耗, 提升仿箱鲀鱼群的协同续航能力, 本文设计了一种基于逻辑分区的仿箱鲀鱼群负载均衡分簇控制算法. 该算法采用分簇方式, 减少了节点间的维护报文数量, 降低了系统整体开销； 基于簇内逻辑分区策略, 实现监测、 保障和侦察多区域协同控制, 并结合最小响应时间整编零散鱼群, 优化网络控制体系的同时提高了组网灵活性； 在维护过程中采用区域节点角色转换机制实现网络负载均衡. 仿真实验验证了算法的有效性及可行性.