0 引言

无线传感网络 (Wireless Sensor Network, WSN)^[1]由具有传感器的无线节点构成, 每个节点既能采集信息, 也能进行数据传输, 其中, 无线数据传输能耗较多, 影响网络的生存周期。在WSN广播中, 往往采用泛洪的方式进行路由转发, 极大地消耗了节点的能量, 规划广播路径就显得尤为重要。由于WSN中各节点的位置不同, 节点之间转发数据所需的能耗也就不同, 进而, 不同的WSN广播路径消耗的能量也不相同。在拥有N个节点的WSN中, 广播路径就有 (N-1)!种可能, 使用穷举法尝试每种路径, 找到最小能耗的路径, 费时且不切实际。因此, 本文将WSN广播路径选择当作非确定性多项式 (Non-deterministic Polynomial, NP) 问题, 使用群智能优化算法进行求解。

群智能优化算法是目前寻求全局最优解比较常用的方法, 并且求解能力显著。常用的群智能优化算法有遗传 (Genetic Algorithm, GA) 算法^[2]、模拟退火 (Simulated Annealing, SA) 算法^[3]、蚁群算法^[4]、粒子群优化 (Particle Swarm Optimization, PSO) 算法^[5]、人工蜂群算法^[6]和果蝇优化算法 (Fruit fly Optimization Algorithm, FOA)^[7-8]等。目前, 已有许多学者将群智能优化算法应用到WSN路由和路径优化中, 并取得了一定的研究成果。白舸^[9]将模拟退火 (SA) 和遗传算法 (GA) 进行组合优化，保留SA的降温过程和GA的交叉、变异，形成模拟退火遗传算法 (Simulated Annealing Genetic Algorithm, SAGA)，并利用SAGA对WSN广播路径逐步优化, 减小了广播传输的能耗, 但是算法寻优效果不好；吴意乐等^[10]对SAGA进行改进，利用改进的SAGA优化WSN路径, 降低了数据传输的能耗; 苏锦等^[11]将遗传算法和蚁群算法结合, 提高了WSN路径优化的效率, 减少了能耗, 延长了网络生存时间, 但蚁群算法计算速度慢, 耗时较多; 袁浩^[12]在粒子群算法中引入了变异算子, 找到WSN有效的优化路由, 提高了解的质量和路由成功率; 秦智超等^[13]利用粒子群优化环状簇路由协议, 克服节点过早死亡的缺点, 延长了网络寿命, 但粒子群算法参数较多, 对先验知识要求较高; 郑振华^[14]提出了基于人工蜂群算法的组播路由算法, 根据网络规模自动调整参数, 但是人工蜂群算法局部搜索能力不强, 对于复杂网络效果不明显。

果蝇优化算法 (FOA)^[7-8]是潘文超在2011年提出的新型启发式群智能优化算法, 因其参数少、实现简单、计算速度快, 受到各个领域研究学者的欢迎。本文将果蝇优化算法进行离散化处理, 得到离散果蝇优化算法 (Discrete FOA, DFOA), 使用莱维飞行 (Lévy flights) 和轮盘赌选择对DFOA进行改进, 利用改进DFOA对WSN广播路由进行优化, 寻求能耗最小的广播路径, 以提高WSN广播路由的性能, 节省网络传输的能量消耗。

1 WSN广播路由模型

WSN广播路由算法是指广播信息从首节点出发, 遍历网络中每一个节点, 使传输的能耗最小, 即改进DFOA对WSN广播路由寻优。

在实际的无线网络环境中, WSN节点的位置和周围网络环境可能随时都会发生变化, 本文假设在一个广播通信周期内, WSN拓扑结构不变, 将WSN拓扑结构简化为图论模型, 用图G=(V, E) 表示。其中:集合V={v₁, v₂, …, v_n}为WSN中的n个节点；集合E={e₁, e₂, …, e_n}为WSN中n个节点之间的链路。在二维平面内, 节点v₁和v₂的坐标分别为 (x(v₁), y(v₁)) 和 (x(v₂), y(v₂)), 可以得到v₁到v₂的距离。

$ d = \sqrt {{{\left( {x\left( {{v_1}} \right) - x\left( {{v_2}} \right)} \right)}^2} + {{\left( {y\left( {{v_1}} \right) - y\left( {{v_2}} \right)} \right)}^2}} $

(1)

WSN广播消耗的能量根据文献提出的能量模型确定。节点v_i发送单位信息的能耗为C_e(v_i)=ld(v_i)^α+c_e。其中:ld(v_i)^α为节点发送无线信息的能耗; l为节点发送无线信息的能耗系数, 由无线发送模块决定; d(v_i) 为v_i到下一节点的传输距离; α为环境影响系数, 是3~5的常量；c_e是节点处理信息的能耗, 一般为常数。节点v_i接收点位信息的能耗为C_r(v_i)=c_r, 取c_r=2/3c_e。

所以, 拥有N个节点的WSN广播消耗的总能耗由式 (2) 确定:

$ \begin{array}{l} C = \sum\limits_{i = 1}^N {C\left( {{v_i}} \right)} = \sum\limits_{i = 1}^N {\left[ {{C_e}\left( {{v_i}} \right) + {C_r}\left( {{v_i}} \right)} \right]} = \\ \;\;\;\;\;\;\sum\limits_{i = 1}^N {\left[ {ld{{\left( {{v_i}} \right)}^\alpha } + {c_e} + {c_r}} \right]} = \sum\limits_{i = 1}^N {\left[ {ld{{\left( {{v_i}} \right)}^\alpha } + \frac{5}{3}{c_e}} \right]} \end{array} $

(2)

2 基于改进DFOA的WSN广播路由算法 2.1 交换子和交换序

文献给出了交换子和交换序的定义和运算过程。

交换子的作用为交换序列中的指定位置。假设序列S=1，2，3，4，5, 交换子为SO(3, 4), 则S′=S+SO(3, 4)=1，2，4，3，5。

交换序为一个或多个交换子有序排列的集合, 即多个交换子依次作用在序列上。

两个不同序列的差为元素个数最少的交换序, 即基本交换序。

两个不同序列的距离为基本交换序的元素个数。

针对FOA^[18]仅适用于解空间为连续的情况, 本文将交换子和交换序引入到FOA中, 得到DFOA, 使得FOA能够应用到离散环境中, 求解能耗最小的WSN广播路由。

2.2 种群更新方式的改进

果蝇在寻找食物的过程中, 也像鸟类一样, 飞行轨迹符合莱维飞行。莱维飞行^[19-21]是服从Lévy分布的非高斯平稳过程, 飞行的步长满足一个重尾的莱维稳定分布, 较短的步长与偶尔较长的步长相互交替, 以发现更好的食物源。

文献中给出了Lévy分布的计算过程:

$ {\rm{Lévy}}\left( \beta \right)\frac{{\varphi \times u}}{{{{\left| v \right|}^{\frac{1}{\beta }}}}} $

(3)

其中:Lévy (β) 是一个莱维随机数, 服从Lévy分布；u、v服从标准正态分布；β为一个常数, 其取值区间一般为0 < β < 2。φ的计算公式如式 (4) 所示:

$ \varphi = {\left( {\frac{{\Gamma \left( {1 + \beta } \right) \times \sin \left( {\pi \times \frac{\beta }{2}} \right)}}{{\Gamma \left( {\left( {\frac{{1 + \beta }}{2}} \right) \times \beta \times {2^{\frac{{\left( {\beta - 1} \right)}}{2}}}} \right)}}} \right)^{\frac{1}{\beta }}} $

(4)

其中:Γ() 是标准Gamma函数。

通过莱维飞行的概念对果蝇随机探索食物源的步长公式R=R₀×rand (1) 进行改进, 多数的较短步长实现算法对局部探索能力的控制, 偶尔的较长步长使得算法能够跳出局部最优, 增加样本多样性。

$ R = {\rm{abs}}\left( {{R_0} \times {\rm{Lévy}}\left( \beta \right)} \right) $

(5)

其中:R₀为随机搜索半径范围。

在FOA中, 如果找到新的最优点, 全部的果蝇个体都飞往这个最好的位置, 这就导致算法极易陷入局部最优, 本文利用轮盘赌选择对果蝇的视觉寻优行为进行改进, 使得全部的果蝇个体选择较优点, 而不是最优点, 避免算法陷入局部最优, 增加样本多样性。

通过莱维飞行和轮盘赌选择分别对FOA的步长和位置更新方式进行改进, 莱维飞行控制的步长与原算法相比, 只是随机数的生成方面略有区别, 对于算法复杂度影响不大。然而, 轮盘赌选择较好的果蝇位置, 而不仅仅是最好的果蝇位置, 这就使得果蝇位置更新时, 保留更多的可行解, 需要进行局部探索的点也较多, 在一定程度上增加了算法的复杂度, 但是, 总的果蝇数量是不变的, 所以计算量变化不大。原算法仅保留一个最优点极易陷入局部最优, 改进后算法就很好地解决了这个问题, 增加了样本的多样性, 避免算法陷入局部最优, 才能够找到更好的可行解, 增加算法复杂度是值得的。

2.3 算法描述

本文利用改进的离散果蝇优化算法寻求WSN广播通信中能耗最小的广播路径, 以提高网络性能, 延长网络生存的时间。

假设在一个广播通信周期内, WSN的N个节点位置不变, 并为节点进行编号。广播算法步骤如下:

1) 初始化。设定迭代次数Maxgen、种群规模Sizepop。随机生成Sizepop条长度为N+1的广播序列S_i, 对果蝇群体位置进行初始化。其中:首先将迭代次数Maxgen、种群规模Sizepop设定一个数值, 然后根据实验中算法收敛情况改变Maxgen和Sizepop的值, 使其适用于WSN广播。

2) 随机搜索。利用式 (5) 生成随机搜索半径R(交换序的个数), 随机生成N个不重复的整数, 取前2R个数作为交换序SS, 生成下一代果蝇个体i的位置S_i^g+1, 随机搜索食物源。

$ S_i^{g + 1} = S_i^g + SS $

(6)

3) 计算味道浓度。根据果蝇个体S_i和式 (2), 确定味道浓度函数Smell(S_i), 并计算每个果蝇个体味道浓度Smell_i。

$ Smel{l_i} = \sum\limits_{j = 1}^N {\left[ {ld{{\left( {{v_j}} \right)}^\alpha } + \frac{5}{3}{c_e}} \right]} $

(7)

其中:v_j(j∈[1, N]) 为组成果蝇个体S_i的网络节点。

4) 选择当代最优。找出全部果蝇个体中味道浓度最小的果蝇。

$ \left[ {\begin{array}{*{20}{c}} {bestSmell}&{bestIndex} \end{array}} \right] = \min \left( {Smell} \right) $

(8)

5) 更新全局最优。比较味道浓度是否更好, 如果是, 则保留最优值和最优果蝇位置; 否则执行下一步。

$ SmellBest = bestSmell $

(9)

$ S\_best = {S_{bestIndex}} $

(10)

6) 轮盘赌选择。利用轮盘赌选择, 使果蝇个体向较优点附近靠拢。

7) 进行迭代寻优。判断是否达到迭代次数Maxgen, 如果是, 算法结束, 输出最优结果; 否则, 重复执行步骤2)~7)。

3 实验仿真与分析

本章使用Matlab对基于改进DFOA的WSN广播路由算法进行仿真, 首先, 与未改进的DFOA进行WSN广播路径优化的演化过程进行比较, 体现改进DFOA的有效性; 然后将本文算法与经典的模拟退火遗传算法、蚁群算法和粒子群算法用于WSN广播路由进行比较, 分析改进DFOA对WSN广播路径进行优化的优越性。

3.1 改进算法有效性分析

为体现对比实验的公平性, 尽可能使改进DFOA和未改进DFOA相关的参数相同:最大迭代次数Maxgen=200;种群规模Sizepop=30;随机搜索半径范围R₀=5;Lévy分布中β=1.5;WSN节点位置是在80 m×80 m的范围内随机生成的50个节点; 环境影响因素α=2;能耗系数l=1 J/m²; 节点处理信息的能耗c_e=10 J。

图 1是将改进前后的DFOA对相同WSN节点位置的广播能耗进行寻优的演化过程对比。从图 1可以看出, 改进的DFOA最终获得的广播能耗明显优于未改进的DFOA, 虽然改进DFOA收敛速度变慢, 但是能跳出局部最优, 更好地进行WSN广播路由。

图 2是在80 m×80 m的范围内, WSN中50个节点经过未优化、DFOA优化、改进DFOA优化得到的广播路径图。从图 2可看出：DFOA能找到较优的WSN广播路径；但是, 改进的DFOA找到的广播路径更为优异, 消耗的能量更少。

因此, 利用莱维飞行和轮盘赌选择对DFOA进行改进, 种群的步长不再单一, 增加了跳出局部最优的机会, 种群样本多样性得到提高, 保留了更多较优的可行解, 对其进行局部探索, 解决了DFOA易陷入局部最优的缺陷, 能找到最好的WSN广播路由策略, 图 1和图 2(c)表明本文对算法的改进是有效的。

改进DFOA中引入了莱维飞行, 对种群局部搜索的步长进行控制, 相对于单一步长的DFOA增加了步长的计算过程, 这一阶段, 增加了算法的时间复杂度, 但通过莱维飞行获得的步长同样使用变量R来保存, 因此, 算法的空间复杂度在这一阶段并未增加; 与DFOA仅保留最优点相比, 改进的算法利用轮盘赌选择对迭代过程中的果蝇位置进行更新, 保留了种群中的较优点, 时间复杂度并没有增加, 但保留较优点的内存开销增加, 算法空间复杂度有所提高。综上所述, 改进DFOA在时间复杂度和空间复杂度上都有所增加, 但是从图 1和图 2(c)可以看出, 改进前后的算法性能相差较大, 因此, 算法的复杂度增加是可以接受的。

3.2 本文算法优越性分析

本节利用改进DFOA在不同网络规模下对WSN广播路由进行寻优, 并与SAGA^[9]、改进蚁群优化 (Ant Colony Optimization, ACO) 算法^[11]和自适应离散PSO算法^[12]进行对比, 验证本文算法的优越性。WSN规模设定6种, 随机生成网络中节点的位置, 同时, 保证每个算法的初始值相同, 对不同算法进行对比仿真。

图 3是不同WSN网络规模下的本文改进DFOA和SAGA^[9]、PSO算法^[12]、ACO算法^[11]求得的广播能耗的对比图。从图 3可看出, 在WSN网络规模较小时, 四种算法的能耗相差不大, 但是, 随着WSN网络规模的增大, SAGA陷入局部最优, 因此, 其获得的广播能耗大幅度增加, 而自适应离散PSO算法和改进ACO算法在跳出局部最优方面较SAGA具有一定的优势, 但是相对于本文提出的改进DFOA, 却还是有一定的不足, 获得的广播能耗稍大于本文算法的能耗。

在3.1节的仿真实验结果表明改进DFOA在跳出局部最优方面具有较高的优越性, 而图 3的曲线显示, 改进DFOA对广播路由进行优化, 随着网络规模增大, 其获得的广播能耗增幅较小, 说明与其他算法相比, 其跳出局部最优的能力也较为出众。

4 结语

本文针对FOA仅适用于连续型问题, 引入交换子和交换序的概念, 提出了适用于WSN广播路由寻优的DFOA; 同时, 为避免DFOA陷入局部最优, 利用莱维飞行对算法步长进行控制, 提高样本的多样性; 接下来, 为解决果蝇个体都飞向最优点产生下一代个体使得样本多样性降低、易陷入局部最优的问题, 使用轮盘赌选择产生下一代个体, 保留较优的多数个体, 而不是仅保留最优点, 以发现更多的可行解。通过改进DFOA对WSN广播路由进行优化, 找到最好的广播路由策略, 减小了广播的能耗, 提升了网络的生存时间, 增强了网络性能。仿真结果表明, 与未改进的DFOA进行对比, 改进DFOA对WSN广播路由进行寻优时, 能够跳出局部最优, 找到最好的广播路径, 明显减小了广播能耗, 对算法的改进是有效的; 与SAGA、改进ACO算法和自适应离散PSO算法进行仿真对比, 在不同的网络规模下, 改进DFOA对广播路由进行优化时, 能够避免算法陷入局部最优, 得到能耗更低的广播路径, 因此, 改进DFOA对广播路由进行优化的优越性更明显。