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

一篇论文

第38卷 第2期计算机科学Vol.38No.2基于多蚁群算法的无线传感器网络路由的跨层设计

李丽芬 张君艳 朱永利 于永华

(华北电力大学控制与计算机工程学院 保定071003)

摘 要 针对事件驱动型无线传感器网络对数据传输的强实时性和高可靠性的要求,将统计获得的节点接入效率和负载队列长度等MAC层状态信息作为路由度量参数。考虑到蚂蚁网络算法在重负荷网络中存在传输延迟大、聚合速度慢等缺陷,提出了一种基于多蚁群算法的负载感知和高效接入的跨层路由协议,该协议把节点的单跳延迟、负载及带宽接入效率等参数作为路径的启发值进行路由优化。仿真结果表明,基于多蚁群算法的路由协议能够保证数据传输的实时性,能够实现无线传感器网络的拥塞控制及负载平衡。关键词 无线传感器网络,路由,多蚁群算法,跨层设计,服务质量中图法分类号 TP393 文献标识码 A

Cross layerRoutingDesignforWirelessSensorNetworksBasedonMultipleAntColonyAlgorithm

LILi fen ZHANGJun yan ZHUYong li YUYong hua

(SchoolofControlandComputerEngineering,NorthChinaElectricPowerUniversity,Baoding071003,China)

Abstract Sincetheevent drivenwirelesssensornetworksrequiredstrongreal timeandhighreliabilityfordatatrans mission,theaccessefficiencyandqueuelengthwhichwereobtainedfromthemediaaccesscontrollayerwereregardedasroutingmetricparameters.However,thereisincreasingconcernthattheAntNetalgorithmisbeingdisadvantagedbe causeoflargetransmissiondelayandslowpolymerizationintheheavy loadingwirelesssensornetworks,sotheload sensingandefficient accessingroutingprotocolwasproposedbasedonmultipleantcolonyalgorithm.Inordertoseektheoptimalpathfordatatransmissioninwirelesssensornetworks,thedelay,load,accessefficiencywereconsideredasroutingmetricparameters.Theresultsshowthatthecross layerroutingprotocolcanguaranteetherealtimefordatatransmissionandachievethecongestioncontrolandloadbalancingforwirelesssensornetworks.

Keywords Wirelesssensornetworks,Routing,Multipleantcolonyalgorithm,Cross layerdesign,Qualityofservice

无线传感器网络(WirelessSensorNetworks,WSN)是近几年出现的一种新的无线通信网络技术,其应用前景十分广阔,如用于交通监控、环境监测、战场信息收集等。这些应用可分为两种类型:周期性采样和事件驱动。在周期性采样应用中,无线传感器网络的节点需要周期性地对某个监控的条件或过程进行感知,并将所采集的数据以多跳的方式发送到汇聚节点。事件驱动型应用中,节点监测一个或多个关键变量,只有在接近阈值时才将报警信息进行传输。无论是哪种类型的应用,无线传感器网络都具有集中式数据收集、多跳数据传输、多对一流量模式等特征。靠近基站的节点在把自身数据传输给汇聚节点的同时,还转发来自远离汇聚节点的数据,越靠近基站的节点需要转发的数据包越多。传感器节点缓存驻留的分组数若超过节点的发送能力,将导致网络排队延迟增加,造成缓存溢出和数据分组的丢失甚至出现网络拥塞,因此无线传感器网络的性能就会明显变差,整个网络的吞吐量将随输入负荷的增加而下降。而对于事件驱动型无线传感器网络的应用,由于传输的是报警信息,因此对分组转发时

延即网络的实时性要求很高。

无线传感器网络的拥塞可以发生在两个层次:一种是与传统网络相同的拥塞,就是节点需要发送的分组流量超过节点的发送能力,使得网络排队延迟增加,甚至导致缓存溢出和数据分组的丢失;另一种类型是无线链路级的拥塞。无线信道是共享信道,在同一时刻相邻节点只能有一个节点使用无线信道。当多个相邻节点同时竞争使用无线信道时,就会产生访问冲突,引起链路级拥塞,增加分组的服务时间,降低链路利用率和网络的吞吐量。用于事件驱动型无线传感器网络路由协议的设计应采用跨层设计的方法,综合考虑了来自媒体接入控制层和节点缓存的状态信息,实现网络了的负载平衡和拥塞控制。

蚁群优化算法将问题求解的快速性、全局优化性以及高度的自组织性等特点合理结合,与无线传感器网络低能耗、自组织的大规模网络路由快速建立要求极其相似,有助于建立面向数据为中心的汇聚路由。本文采用多种群蚁群算法,基于自适应的跨层优化设计,根据统计获得的链路接入效率和

到稿日期:2010 03 02 返修日期:2010 06 10 本文受国家自然科学基金(60974125)资助。

李丽芬(1970-),女,博士,讲师,主要研究方向为无线传感器网络,E mail:lilifen70@;张君艳(1985-),女,硕士生,主要研究方向为无线传感器网络;朱永利(1963-),男,教授,博士生导师,CCF高级会员,主要研究方向为人工智能及其在电力系统中的应用;于永华(1984-),男,硕士生,主要研究方向为无线传感器网络。

一篇论文

负载队列长度等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 单跳延迟

由于传感器网络的带宽十分有限,不适宜采用专门的探测包测量单跳的延迟,因此直接测量经过该节点传输的数据包的传输延迟时间。发送端给进入网络输出队列的数据包打上时间戳,当接收到应答信息时,即可计算出该数据包来回的单跳延迟。在接收端,处理应答信息的时间放入应答数据包中,于是节点单跳的传输延迟就可以从发送者来回延迟时间中减去接收者 …… 此处隐藏：3599字，全部文档内容请下载后查看。喜欢就下载吧 ……