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

一篇论文

负载队列长度等MAC层的状态信息,设计了表征无线信道的接入效率和节点负载状况的综合路由度量准则;提出了一种新的基于多蚁群算法的负载感知和高效接入的跨层路由协议。仿真实验表明,基于多蚁群算法的无线传感器网络跨层路由协议能够保证节点间的传输速率,实现了网络的拥塞控制以及负载平衡机制。

j的待发送数据队列长度,N为节点i的邻点集。节点周期性发送与接收 Hello 分组,以及时获取或更新邻居节点的待发送数据队列长度[2]。1.2.3 节点接入效率

IEEE802.11的MAC层访问机制中最常用的是分布式协调功能DCF(DistributedCoordinationFunction)。如图1所示,每个节点应用DCF机制以竞争的方式接入无线链路。DCF子层在每一个节点使用CSMA机制的分布式接入算法,让各个站通过争用信道来获取发送权。任何一个节点发送数据前,先侦听信道。如果信道忙,此节点将推迟发送,以等待信道空闲。信道从忙态变为空闲,任何一个站要发送数据帧时,不仅都必须等待一个DIFS的间隔,而且还要进入争用窗口,并计算随机退避时间,以便再次重新试图接入到信道。这样各站就要执行退避算法,

以减少发生碰撞的概率。

1 问题描述及路由度量

1.1 问题描述

考虑一个由N个随机部署的传感器节点形成的网络。假设一般无线传感器网络的典型设置为:

(1)传感器节点和汇聚点在部署后均不再发生位置移动。(2)所有节点都是同构的,具备数据融合的功能。(3)无线链路是对称的。

(4)节点装备GPS,通过测量的方式可知其具体地理位置。

无线传感器网络路由优化实质上是求解一个多准则QoS路由优化问题。通常将无线传感器网络抽象成具有顶点集合V和边集合E的加权有向图G(V,E),其中节点集合V={1,2, ,n},端节点s,u V分别代表源节点和目的节点,其他则代表转发节点。集合A的元素称为边,用弧(i,j)表示节点i到节点j的边,其中i,j V,弧(i,j) E,弧边(i,j)的动态可变权值Eij表示节点i与j之间的路由度量或路由花费。1.2 路由度量方式

1.2.1 单跳延迟

由于传感器网络的带宽十分有限,不适宜采用专门的探测包测量单跳的延迟,因此直接测量经过该节点传输的数据包的传输延迟时间。发送端给进入网络输出队列的数据包打上时间戳,当接收到应答信息时,即可计算出该数据包来回的单跳延迟。在接收端,处理应答信息的时间放入应答数据包中,于是节点单跳的传输延迟就可以从发送者来回延迟时间中减去接收者的处理时间。每个节点都保存了一个邻居表,它存储了信标传递的信息,节点会定期地广播一个信标数据包给它的邻居节点,这个周期性的信标仅在相邻节点之间交换位置信息。由于传感器节点的位置基本不动或者很少移动,因此这种位置信息交换的时间间隔可以很长。除了周期性的信标交换之外,还有根据需要产生的信标:延迟估计信标[1],这一类信标只耗用很小的开销就可对网络的延时情况实施快速反应。每个节点保存了其直接邻居的节点集合,它不需要保存全部节点的路由表和数据流信息。因此,所需要的存储器大小只与邻居节点的个数成正比。

1.2.2 节点负载

节点i的负载值Qi可以取节点当前待发送数据队列的长度,该长度准确地表明了节点当前的负载。采用邻点信息表广播的方法来取得负载信息。节点定时对队列长度抽样,用抽样平均值表示一个节点的负荷,即待发送数据队列的长度,表示为

Qi=

k=1

图1 IEEE802.11的MAC层分布协调功能(DCF)示意图

众多节点对传输媒体的接入竞争会导致单个节点对带宽的利用率降低,这将大大限制系统的吞吐量。大部分无线传感器网络的路由协议没有考虑一个节点局部的带宽利用率,而这对于实时性要求较高的应用来说是非常重要的。本文将一个节点局部的接入效率作为局部带宽利用率的度量,并将其作为路由花费的一个参数用于路由跨层优化设计中。

在MAC的这种机制中,我们定义一个参数来描述一个节点i对信道的使用情况。

定义2 节点的带宽接入效率

i=

BWBWaccess

(3)

式中,负载带宽BWload传输带宽中节点用于传输其负荷的部分,用传输一个帧所需的平均时间来表示。接入带宽BWaccess节点竞争接入信道的时间,亦即用某个节点使退避计时器归零的平均时间[3]。

2 蚁群算法的扩展

蚁群算法(AntColonyAlgorithm,ACA)是由意大利学者M.Dorigo等人于20世纪90年代初期提出的一种新型模拟进化算法[3],其通过模拟真实蚁群搜索食物的过程中个体间的信息交流与相互协作来寻找从蚁穴到食物源的最短路径。基本蚁群的算法利用随机策略搜索解,存在收敛速度较慢、易陷入局部最优等缺陷,不利于发现更好的解。带精英策略的蚂蚁系统、基于优化排序的蚂蚁系统、蚁群系统和最大 最小蚁群算法等蚁群优化算法针对基本蚁群算法的缺陷进行了改进,提高了算法的性能。不论是基本蚁群算法还是改进的蚁群算法,都是基于单种群、单种信息素的算法,没有充分挖掘蚁群算法的并行性以及分布式计算等优良特性,不能完全反映真实蚂蚁社会的复杂性[4]。随着蚁群算法的不断改进,研究重点转向使用多个种群协同的多蚁群算法。该算法通过使用正负两种信息素效应,利用群体层的交互作用,尽可能地使蚂蚁代理搜索更多的路径,保证了蚁 …… 此处隐藏：278字，全部文档内容请下载后查看。喜欢就下载吧 ……