基于多蚁群算法的无线传感器网络路由的跨层设(3)

一篇论文

性。

蚁群算法通过群体智能能够得到全局最优解,具有很强的可扩展性、鲁棒性及适应于动态环境的特性,非常适用于无线传感器网络且在多个研究领域中受到了广泛的关注。目前用于网络路由的蚁群优化算法包括用于移动自组网的ARH算法、用于解决电信线路交换网络负载平衡问题的ABC算法、用于解决线路交换网络的路由问题的ASGA算法及自适应分布式且基于移动代理的AntNet算法。在这些群体智能路由算法中,AntNet算法在吞吐量和包延迟等方面有着较为显著的优越性,但是该算法存在着在重负荷下延迟大、聚合速度慢及可扩展性差等缺陷,因此并不适用于大规模事件驱动型无线传感器网络的路由优化

[5]

表,其中前向蚂蚁收集节点信息并进行信息素的局部更新,到达目的节点后把收集的路径信息转移给后向蚂蚁。后向蚂蚁在返回源节点的过程中对路径进行全局更新。

Step3 信息素吸引因子及排斥因子。Aki表示种群K中第i只蚂蚁代理,该种群内的蚂蚁均释放同一种类型的信息素,不同种群释放的信息素类型不同[7]。

k

定义3(吸引因子) ij为种群k的蚂蚁当前位于传感器节点i,在其邻域 i内选择下一个节点j的k类型信息素的吸引因子,其表达式定义如下

kkij

ij=kkh

h

i

(5)

式中, ij为边(i,j)上的第k种信息素浓度。

k定义4(排斥因子) ij为种群k的蚂蚁当前位于传感器

。本文提出了

一种基于多种群蚁群的路由优化算法(MACO,Multiple

AntCol onyOptimizationforWirelessSensorNetworks)来对无线传感器网络进行路由优化。基本思路是将基本蚁群算法中的蚂蚁分为两个或者多个种群,利用多个蚁群并行执行搜索任务,通过不同蚁群间信息素的相互作用并把端到端的延迟、节点负载及接入效率作为路径启发值,然后定期地替换最优解进行信息素更新,来保证解的多样性,实现网络资源的均衡优化及路由的鲁棒性。

节点i,在其邻域 i内选择下一个节点j的k类型信息素的排斥因子,表达式定义如下

=

kij

h k

hijkih

(6)

h i

式中, ij为边(i,j)上的第k种信息素浓度。

当位于节点i的蚂蚁在其邻域 i内根据概率转移规则

选择下一个传感器节点j时,该蚂蚁会以更高的概率选择具有较高自己类型信息素浓度的路径,由不同类型信息素浓度的排斥作用将以较低的概率选择具有来自其它群体较高信息素浓度的路径。

Step4 概率转移规则。种群S中位于传感器节点i的蚂蚁选择下一节点j进行路由时的转移概率表达式定义如下:

[ (t)]

P(k)=

sij

h tabuk

sk k ij/

ij

3 基于多蚁群算法的WSN路由跨层优化

数据收集型的无线传感器网络中,大部分流量都是通过各个传感器节点流向汇聚节点的,网络中源节点众多而汇集节点单一,以汇集节点为目的的数据流远远超过以它为源的控制流,因此数据流量分布极不均衡,这是无线传感器网络路由协议亟待解决的主要问题。考虑到无线传感器网络中靠近基站的节点负载过重将可能导致严重的网络拥塞甚至拥塞崩溃的问题,从靠近基站的传感器节点中选出一部分子汇聚节点,其它的节点只有通过子汇聚节点才能与汇聚节点进行通信,作为普通的传感器节点利用多蚁群算法中不同蚁群间信息素的相互协作与动态更新来快速地寻找从源节点到子汇聚节点代价小的最优路径。无线传感器网络跨层路由优化策略如下。

Step1 选择子汇聚节点。从靠近基站的传感器节点中选择子汇聚节点,由所需的子汇聚节点数和各个传感器节点已成为子汇聚节点的次数来决定[6]。具体方法是每个节点选择[0,1]之间的一个随机数,随机数随着时间的增长逐渐变大。如果选定的值大于某一个阈值T(n),那么这个节点成为子汇聚节点。T(n)的表达式如下

T(n)=

k

,

N-k[rmod(n/k)]

0,

若n G否则

(4)

[ ij(t)]

[ ih(t)]

[ sih(t)]

kk/ ijij

,j tabuk

(7)

0,否则k

式中, k式(6)给出, sij(t)表示t时刻在边ij, ij分别由式(5)、eij上的S类信息素的浓度。每个节点维护一张信息素表,记录邻边上信息素的浓度。 >0为调整因子,用以调节信息素信息的影响权重。启发函数 ij综合考虑单跳延迟、节点负载及接入效率等QoS路由度量参数,其表达式为

j

ij=(8)

Ljij

式中, j表示下一跳传感器节点j的带宽接入效率,Lj表示节点j的负载,Dij表示节点i到节点j的单跳延迟。Step5 前向蚂蚁的信息素局部更新策略。不同种群通过网络中的传感器节点时所释放的信息素是不同的。种群中的前向蚂蚁根据本种群的信息素转移到下一个节点后,局部更新该种群的信息素。局部更新规则表达式如下

k)* k k(9)ij(t+1)=(1- ij(t)+ ij式中, 为信息素挥发后的残留因子。在蚂蚁经过的路径上采用蚁密模型的更新模式,即前向蚂蚁在经过的路径(i,j)上释放的信息素量为每单位长度Q,模型如下

Q,蚂蚁k经过路径(i,j)

k(10)ij(t,t+1)=

0,否则

式中,Q为一常数。

Step6 后向蚂蚁的信息素全局更新策略。当前向蚂蚁到达目的节点后,将收集到的从源节点到目的节点的路径信

式中,N代表网络中传感器节点的个数,k为子汇聚节点的个数,r为算法执行的次数,G为总的执行次数 …… 此处隐藏：392字，全部文档内容请下载后查看。喜欢就下载吧 ……