基于膜计算的蚁群算法在配电网WSNs中路由研究*

高健文， 黄友锐， 徐善永， 韩 涛， 宋昊明

(安徽理工大学 电气与信息工程学院，安徽 淮南 232001)

0 引 言

随着国家提出了“智能电网”概念，国家电网开始由之前的传统电网向智能化电网进行转变。智能电网的优势可以通过智能设备对电网进行在线检测，使得电网的安全性与稳定性[1]大大加强。对于传统配电网来说已经难以满足可靠性和安全性的要求。因此，能够将配电网中的运行状态、操作控制等数据通过网络进行可靠传输与检测保护的智能电网产生。

无线传感器网络(Wireless Sensor Network)的优势是能耗低，方便快捷的数据收集以及快速的成网能力[2]。它可以收集智能配电网的相关设备信息和运行数据，以实现实时监控。因此，将无线传感器网络引入智能配电网具有重要意义。与WSN结合的配电网络对网络中数据传输的可靠性和实时性能有很高的要求。由于无线传感器网络由大量传感器组成，因此其节点的能量取决于其有限的存储能量。一旦安装在配电网络中，它将不再变化，并且能量耗尽时，再次充能将更加麻烦[3-4]。对于与WSN结合的智能配电网，在确保可靠的电网数据传输的同时，还必须考虑网络中节点的能耗。因此，研究能够保证配电网无线传感器网络的可靠性以及节点的均衡稳定能耗的WSN路由算法就显得尤为重要。

蚁群优化(ACO)是一种生物进化的搜索算法[5]，它具有强大的搜索路径能力。 基于这些优点，研究人员将蚁群算法结合到无线传感器网络路由算法中并进行了改进。 Kassabalidis等对经典的蚁群算法(ACA)进行研究。为了最小化网络能耗，只选择了最短路径进行数据传输，但这会导致大量能耗，并减少路径上的节点的使用寿命。童孟军等[6]将概率选择和信息素作为出发点进行改进，并提出了IEEABR算法。 罗旭等[7]提出了OARA算法，通过将惩罚函数引入到概率选择公式中，使得算法的能力得到进步，但也造成了收敛速度的减慢。

所以，在前者的基础上提出了一种膜计算-蚁群路由算法(MCACR)。通过在状态转移函数中引入动态补偿因子，避免MCACR算法因信息素过高出现过早停滞的现象；利用膜计算的膜内和膜间运算的并行能力，结合引入的最优路径衡量公式，进行多路径并行搜索获取到最优的路径，提高了MCACR算法的局部及全局的收敛能力；通过定义路由修复机制，使得MCACR算法避免了路由空洞。仿真的结果显示：MCACR算法在数据的可靠传输方面有明显增强，在节点的能量消耗方面也进行了均衡，同时让配电网WSNs的生命周期变得更久。

1 相关模型与基本算法描述

1.1 网络模型

与传统的配电网络相比，智能配电网络的优势在于可以实时监控配电过程。 为此，需要在配电网络的设备终端周围安装大量的传感器。通过将无线传感器网络等价为无向图G=，B表示网络中所有节点的集合，即B={B0，B1，…，BN}，B0代表初始节点，BN代表目标节点，节点随机分布在(M×M)m2的监视区域内，可以在设备终端上进行固定周期的信息收集。

网络中规定假设如下：所有的节点编号各不相同，并且安装后就不改变其位置；全部的节点能通过收发的信号进行双方之间的距离估值；所有节点的结构、属性及初始能量都相同；所有节点传输速度的可以根据节点之间的距离进行改变；规定网络中链路的连接是对称的。

1.2 能耗模型

能耗模型引用于文献[8]。ETx(k，d)和ERx(k，d)分别是发送和接收的距离为d，比特数是k的数据包的能耗，如式(1)和式(2)所示：

(1)

ERx=kEelec

(2)

其中，Eelec是节点发送或接收每比特数据的能量消耗；自由空间传播及多径衰落传播两个模型中的放大器能量消耗的系数由εfs和εamp表示；d表示发送和接收的节点之间的距离；d0表示距离的阈值：

(3)

1.3 蚁群算法

蚁群算法中蚂蚁寻找食物的过程主要是基于信息素。信息素是类似于蚂蚁在其走过的道路上留下的引导元素。当蚂蚁找到食物并留下信息素后，越来越多的蚂蚁通过蚂蚁留下的信息素进行寻找，留下的信息素变得更多，这样就使得后面的蚂蚁可以顺着这条路寻找食物的概率变大。式(4)、式(5)是概率选择和信息素更新公式：

(4)

(5)

式(4)、式(5)中，Pkij(t)表示蚂蚁选取下一跳节点的概率，α为信息素的影响权重值，β为启发式的影响权重值。ρ代表的是路径上信息素的挥发系数，τij(t)表示的是蚂蚁k在经过的节点i和j上留下的信息素改变量。

1.4 膜计算概述

膜计算的概念最早是由欧洲科学院[9]提出的，他是一种从生物细胞上得到的启发式计算模型。膜计算实质上是根据细胞中的例如细胞核、线粒体等之间的物质交换而演变出的计算模型，如图1所示。

图1 膜结构示意图Fig. 1 Schematic diagram of membrane structure

膜系统模型的数学表达式为

∏=(V，T，μ，ω1，ω2，…，ωm，(R1，β1)，

(R2β2)，…，(Rmβm))

其中：V和T是集合，其中V中的构成是对象，其中T属于V的集合中，μ代表膜系统中所包含的膜的个数，用m表示，称为膜系统的度，ωx表示膜内的物质对象，Rx表示进化规则的集合，每个膜内和膜间都有自己的特定规则，βx是膜系统中所有的规则的先后级别顺序。膜系统计算模型的优势如下：

(1) 膜结构中每个区域之间没有直接联系，各者之间相互独立存在。各自在膜内进行独自计算，膜内相邻近的区域进行互相交流，对于最优解的产生起到加速作用。

(2) 膜计算因为其并行不干扰的计算能力对于防止陷入局部最优的计算具有优势，所以将膜计算和其他智能仿生算法结合可以提高算法的精度。

2 改进蚁群算法

2.1 改进状态转移公式

由式(4)可以看出，信息素含量对于蚂蚁选择下跳节点是十分重要的。这种选择方式可能会造成最优路径被忽视，即只对信息素含量多的路径进行选择，从而造成选择陷入局部最优，为降低这种风险，通过在状态转移公式中引入动态补偿因子来减弱信息素带来的陷入局部最优的影响。如果信息素权重过大，则添加低动态补偿因子，反之添加高动态补偿因子。补偿因子m(i，j)定义为

(6)

其中，lmax和lmin分别代表蚂蚁在此轮中最长的路径和最短的路径，l(k)代表蚂蚁所走的路径的长度。D(i，j)表示在迭代中的经过路径i→j的集合。引入动态补偿因子后的状态转移公式为

(7)

2.2 改进信息素更新

由原始信息素更新式(5)可以得出，基本算法在进行更新时只对蚂蚁走过的路径长短进行考虑，对于例如跳数，能量等因素没有考虑。可能导致网络生命周期因为节点死亡而减少。根据此因素，将影响网络生存周期的跳数、节点自身能量和路径长度因素引入到信息素更新中。如下公式为单个蚂蚁的信息素更新改进：

(8)

其中，Hk代表蚂蚁k在本轮的搜索过程中所走过的节点总数，Ek代表搜索路径上的节点能量，Lk代表蚂蚁k走过的路程，常系数Q固定不变。

因为一条路径上的信息素含量远高于其他路径，因此可能导致算法过早停滞。 在此基础上，对路径的信息素含量进行了阈值处理，以避免上述现象。根据现有的绝大多数的蚁群算法来看，大都没有考虑到信息素的挥发值是固定值，对挥发值ρ进行改进，用于适应不同情况下将信息素的挥发进行调整，进而使得信息素的挥发更加可靠。所有的蚂蚁进行路径搜索成功后，改进公式如下：

(9)

由式(9)可知，当信息素含量超过所设阈值时，选择所设的最大阈值避免过早搜索结束。若蚂蚁选择路径Lk的长度比较长，则会挥发更多的信息素。否则挥发的更少。对于防止信息素的平衡挥发具有一定帮助。

2.3 多路径路由选取

智能配电网WSNs中的数据传输任务是由传统算法寻找出的单一路由路径承担的，容易造成最优路径负载过重导致出现故障，以致任务传输失败[10-11]。在此基础上引入膜计算进行多路径构建，同时对多条路径进行质量判断，选取一条最合适的路径进行数据传输。

定义路径度量概率C(r，t)：即将路径上的能量值作为判断依据，以此从多条路径中被选取为承担传输任务路径的概率。概率判断值考虑路径的长度以及路径中的能量因素，C(r，t)表示在t时刻时，路径r被选作为t时刻传输路径的概率：

(10)

其中，Eave(r，t)为其中一条路径上的节点平均能量，L(r，t)为其中一条路径的长度。

2.4 路由节点修复

无线传感器网络中往往会出现“路由空洞”，造成其原因的是网络中一些节点因为某些不定因素造成不能正常进行数据传输，从而导致此现象的产生。此时如果将路由算法再次进行运行，则会带来节点能耗的加剧及时间的浪费。为解决上述问题，引入路由节点修复方法，对不符合条件的节点进行替换。

(1) 规定源节点每隔一段时间派出一个路径检测蚂蚁沿着最优路径到达目标节点进行检查。在检测过程中，采集所有节点的能量指标，若当前节点的能量不满足承担发送任务所需的最低能量，则须在节点周围选取一个能量高的节点进行替换节点，同时对路由表中的最优路径进行更新。

(2) 对于能够替换损坏节点的节点选择，将搜索区域的面积和与目标节点之间的方向进行限制。从式(1)可以看出，传输消耗的能量与传输的距离d是成正比的。因此依照此因素将被替换的节点看成圆心，将d0作为搜索圆形区域的半径，将次圆形区域内的节点作为候补节点。考虑到满足距离的要求，还需满足角度范围要求。连接圆心与目标节点，为防止选取到被替换节点的后方，即远离目标节点，规定替换节点和圆心连线与目标节点和圆心连线之间的角度范围限制在圆心和目标节点连线左右60°以内，如图2所示。

图2 搜索范围示意图Fig. 2 Shematic diagram of search scope

图2中R为半径，i为被替换节点，j、j′、j″为待替换节点，θ为两条连线的夹角。

3 基于膜计算与蚁群算法的融合算法

传统的蚁群算法搜索出的路径可能是由于出现局部最优形成的，有概率是不满足最优路径的。膜计算模型可以将膜内运算独立进行，然后再进行膜间交流运算。既加速了搜索速度，同时搜索出多条路径，并且尽可能地避免了局部最优的产生。所以两者的融合对于配电网中数据传输，能耗减少等问题的解决具有十分重要的意义[12-13]。算法膜结构如图3所示。

图3 算法膜结构图Fig. 3 Algorithmic membrane structure diagram

3.1 编码规则

3.2 进化规则

图3是算法的膜结构示意图，编号1的膜作为膜系统的主膜，膜2，膜3，膜4作为辅助膜。主膜的作用是将辅助膜中的优秀蚂蚁进行接收，从全局对所送入路径排序选择最优的路径。辅助膜的作用是各自膜内的蚂蚁独立不干扰的进行路径的搜索，向主膜中输送各自膜内的优秀蚂蚁即路径。

辅助膜2内的蚂蚁由初始节点开始选取下一跳节点，选取的标准为式 (6)、式(7)，直到所有的蚂蚁遍历完所有的节点为止，即构建完成各自的路径。再根据式(10)按照选取概率由小到大进行排列，排列完成后选取前5个优势路径送入主膜1中。膜交换规则如下：

(11)

膜3中的蚂蚁按照式(7)进行下一跳节点选取。算法每完成一次迭依旧按照式(10)对路径进行排列，并将前5个路径选取送到主膜1中。对应的规则如下：

(12)

膜4中的蚂蚁按照改进蚁群算法的步骤进行，所有蚂蚁完成各自路径的构建后同样进行排序，将排序好后的五个送入主膜1中。交换规则如下所示：

(13)

主膜1内进行全局路径更新，即完成最优路径的选取。在主膜1中将送入主膜1中的15条路径通过式(10)进行比较，选择出本轮最优路径，然后基于式(8)、式(9)进行信息素更新过程。

全局更新后，若迭代次数不满足，则继续下一次的迭代。反之，则开始输出过程，即将最优路径随机送入某个子膜中进行一次构建来确认该路径是否满足条件。规则如下：

(14)

综上所述，算法的模型可表示为

∏=(V，T，μ，ω1，ω2，…，ω4，(R1，β1)，

(R2β2)，…，(R4β4))

(15)

其中：ri，rule是膜内信息素和节点选取更新规则。

3.3 算法运行步骤

步骤1 将参数初始化，包括节点的能量，信息素的浓度及节点之间的距离等。

步骤2 算法开始进行迭代之前，每个子膜中在初始节点放置n只蚂蚁。

步骤3 膜内所有蚂蚁选取下一跳节点，选取原则依据式(6)、式(7)。

步骤4 对蚂蚁经过的节点的能量等信息进行记录。

步骤5 子膜内所以蚂蚁完成搜索后，按照公式(10)进行路径长度排序，并选取排名前5的送入主膜中。

步骤6 主膜中对子膜送来的路径依据式(10)进行最优路径选取，并且按照式(8)、式(9)更新信息素。

步骤7 从步骤3开始继续运行到步骤6，直到满足迭代次数。

步骤8 将最优路径进行输出，并且需要对出现路由空洞的路径进行路由节点修复。

算法流程图如图4所示。

图4 算法流程图Fig. 4 Algorithm flow chart

4 实验分析

采用Matlab软件对提出的MCACR算法进行仿真分析，通过选取网络能量消耗、网络生命周期、路径搜索时间，节点死亡的数量作为比较对象，与ARA、OARA和Leach-Ant 3个算法进行比较，来进行算法有效性的验证。模拟环境设置为：选取一个网络覆盖区域面积为100 m×100 m的固定区域，然后将100个节点成不规则的部署在区域中。所有节点的初始能量都设置为1J，节点之间发送的数据包大小设置为2 000 bits，算法参数设置为α=1，β=0.8，ρ=0.5，Q=80。

图5展示了网络中节点的平均能耗情况，图6展示了节点的每代剩余能量情况图。由图可知，在相同的迭代次数内，提出的MCACR算法相比较于其他3种算法所消耗的能量要更少，节点的剩余能量也更多。同时可以看出且随着迭代次数的增加，网络中节点的平均能耗的增长速度也低于其他3种算法。这是因为在信息素的更新以及加入最优路径选取的公式中考虑了节点的能量和节点跳数，传统的仅仅考虑路径长度这一因素，忽略了节点能量因素，导致能耗过大。

图7显示的是路径搜索中每一节点平均能量损耗图。从图7可知，提出的MCACR算法其节点的平均能量损耗要低于其他算法。

图5 节点平均能耗变化趋势Fig. 5 Trend of average energy consumption of nodes

图6 迭代完成后节点平均剩余能量 Fig. 6 After the iteration is completed， the average remaining energy of the node

图7 各节点平均能耗情况Fig. 7 Average energy consumption of each node

同时可以看出其他3种算法某些节点出现较大波动，造成波动幅度较大的原因是因为单一路径路由造成路由空洞，容易导致节点死亡造成数据传输失败。提出的MCACR算法的大多数节点能耗波动相对较小，能量的消耗比较平均，对延长无线传感器网络的生存周期具有帮助。

表1列举了各个算法的首节点死亡代数，搜索路径的时间，迭代结束后网络的能耗情况。从表1可以看出提出的MCACR算法性能相对于其他算法具有优势。图8表示网络中各算法的第1个节点的死亡代数。

表1 算法性能比较Table 1 Algorithm performance comparison

图8 首节点死亡代数

由此可知，同一网络环境情况下，提出的MCACR算法对于网络中首节点死亡时间、网络能耗、算法搜索时间及网络生命周期上具有意义。

5 总 结

针对智能配电网 WSNs 应用场景，在满足应用期望可靠性的基础上，在传统蚁群算法的基础上，提出MCACR算法。通过在状态转移函数中引入动态补偿因子，避免MCACR算法因信息素过高出现过早停滞的现象；利用膜计算的膜内和膜间运算的并行能力，结合引入的最优路径衡量公式，进行多路径并行搜索获取到最优的路径，提高了MCACR算法的局部及全局的收敛能力；通过定义路由修复机制，使得MCACR算法避免了路由空洞。仿真的结果显示：MCACR算法在数据的可靠传输方面有明显增强，在节点的能量消耗方面也进行了均衡，同时让配电网WSNs的生命周期变得更久。