浅析蚁群无线网络路由算法

浅析蚁群无线网络路由算法

这里针对WRSN提出了一种并发蚁群算法,实现网络资源的均衡优化及路由的鲁棒性。多同质蚁群间信息素吸引因子与排斥因子设计在一个多蚁群算法模型中,信息素的吸引因子与排斥因子为不同蚁群间数据信息交流的阈值,直接影响模型计算性能。这里提出一种特定的吸引因子与排斥因子定义。设Aki表示种群k中第i只蚂蚁,同种群内的蚂蚁均释放同一种类型的信息素,不同种群释放的信息素类型不同。则αkij为种群k的蚂蚁当前位于传感器节点i,在其邻域Πi内选择下一个节点j的k类型信息素的吸引因子,则αkij=τkij/∑h?Πiτkkh。(1)式中,τij为边(i,j)上的第k种信息素浓度。βkij为种群k的蚂蚁当前位于传感器节点i,在其邻域Πi内选择下一个节点j的k类型信息素的排斥因子,则βkij=∑h≠kτhij/∑h?Πiτkih。(2)式中,τij为边(i,j)上的第k种信息素浓度。当位于节点i的蚂蚁在其邻域Πi内根据概率转移规则选择下一个传感器节点i时,该蚂蚁会以更高的概率选择具有较高自己类型信息素浓度的路径。

多同质蚁群间概率转移规则在蚁群计算模型中,种群中蚂蚁选择下一步路由的转移概率规则也是算法模型的重要组成部分。这里采用的规则为:种群S中位于传感器节点i的蚂蚁选择下一节点j进行路由时的转移概率表达式为:Psij(k)=[τsij(t)]ε•αkij/βkij×[ηij(t)]β∑h?tabuk[τsih(t)]ε•αkij/βkij×[ηih(t)]β,j?tabuk0,,{其他。(3)式中,τsij为t时刻在边(i,j)上的s类信息素的浓度。每个节点维护一张信息素表,记录邻边上信息素的浓度;ε>0为调整因子,用以调节信息素信息的影响权重;启发函数ηij综合考虑单跳延迟、节点负载及接入效率等QoS路由度量参数,则ηij=ξj/Lj×Dij,ξj为下一跳传感器节点j的带宽接入效率,Lj为节点j的负载,Dij表示节点i到节点j的单跳延迟。

蚂蚁的信息素更新策略在蚁群进行路由搜索时,前向蚂蚁的信息素更新策略也是重要的设计要素。由于无线网络的结构不确定性,因此在设计更新策略时,需考虑局部网络情况与全局网络情况,提出不同的更新策略。种群中的前向蚂蚁根据本种群的信息素转移到下一个节点后,局部更新该种群的信息素。局部更新规则为:τkij(t+1)=(1-ρ)τkij(t)+ρΔτkij。(4)式中,ρ为信息素挥发后的残留因子。在蚂蚁经过的路径上采用蚁密模型的更新模式,即前向蚂蚁在经过的路径(i,j)上释放的信息素量为每单位长度Q,Δτkij(t,t+1)=Q,k∈(i,j)0,{其他。(5)式中,Q为一常数。当前向蚂蚁到达目的节点后,将收集到的从源节点到目的节点的路径信息记录下来,并通过测试消息转移给后向蚂蚁,自身将被删除。逆向蚂蚁更新的规则为:τkij(t+n)=(1-ρ)τkij(t)+ρQRs。(6)式中,R为种群S中的蚂蚁k在一次循环结束后路径上的网络资源消耗值。

多蚁群并行路由优化算法流程综合上述分析,设计多蚁群并行路由优化算法流程如下:①选择子汇聚节点。从靠近基站的传感器节点中选择子汇聚节点,由所需的子汇聚节点数和各个传感器节点已成为子汇聚节点的次数来决定。②多蚁群算法初始化。算法将从源节点出发代表网络流量的蚂蚁划分成k个子群,为每个子群分配一个相应的子汇聚节点作为目的节点。将网络中的蚂蚁分为前向蚂蚁和后向蚂蚁并初始化蚂蚁的禁忌表,后向蚂蚁在返回源节点的过程中对路径进行全局更新。③多蚁群并行优化计算。并行计算各蚁群的信息素吸引因子、排斥因子、蚁群概率转移规则与信息素更新策略,并刷新当前蚁群的配置参数,当后向蚂蚁返回到源节点后出动第2批蚂蚁,直至达到算法最大迭代次数NCmax时跳出循环。结束时,每个种群可以得到一条优化路径,多个种群可得多个路径。④根据无线网络的指标来对蚁群所得的路由进行比较,如未符合实际工程需求则返回步骤②再次进行蚁群初始化与计算,直至找到合适的路由结果。2仿真实验下面在Matlab2010b上对设计的基于多蚁群算法的负载感知和高效接入跨层路由协议进行实验。感知区域为(0,0)到(1000,1000)的平面正方形监测区域,随机散布M=50个被控电源节点,仿真时间为T=1000s。考虑到传感器网络节点的现实情况,将节点最大传输距离设为L=100m,控制数据帧平均大小为Sframe=512B,系统缓冲区队列长度为Lframe=100数据包的长度,MAC层采用IEEE802.11协议。多蚁群算法的迭代次数NCmax固定为$200$代,汇聚节点个数或种群个数k=3。其他参数取值采用经验的方法设置为:每个种群中的蚂蚁个数m=100,ε=0.85,α=3,β=2,ρ=0.2,Q=100。运行经典蚁群算法和本文优化蚁群算法对无线电源监控网络路由进行计算,取n=10次实验结果的平均值进行比较。用本文算法和经典算法对重负荷无线电源监控网络进行路由优化时,最优路径上数据包从源节点到目的节点所需平均传输时延大小比较如图1所示。从仿真结果可见,当网络达到稳定时,经典算法的数据包延迟比多种群蚁群算法要大,达到稳定状态需要较长的时间且波动大,因此本文采用改进的多种群蚁群算法在进行无线电源监控网络路由跨层优化时,具有传输时延小、收敛速度快且传输较为稳定等明显优势。

结束语

上述采用一种智能优化的多蚁群算法对WRSN进行跨层路由优化。仿真实验证明,该算法得出的最优传输路径能够满足无线电源监控网络的实时性、可靠性及负载平衡等方面的要求,保证了无线电源监控网络的服务质量。该技术适用于物联网环境,为其他有线网络系统转向物联网系统提供了有益的探索实践经验。

本文作者:姜福祥 钱建波 于正永 单位:淮安信息职业技术学院