（计算机应用技术专业论文）蚁群算法在wsn分层路由中的应用研究.pdf

南京邮电大学硕士研究生学位论文中文摘要 中文摘要 近年来，无线通信和电子技术的不断进步，促进了微型无线通信传感器节点的长足发 展。由这些低功耗、多功能的节点所构成的无线传感器网络具有十分广阔的应用前景，目 前已成为计算机科学技术领域中的研究热点。 由于无线传感器网络与无线a dh o e 网络等通信网络相比有着显著的不同特点，使得 无线传感器网络的路由研究极具挑战性。近年来提出了许多新的无线传感器网络路由算 法，如l e a c h 、p e g a s i s 、g a f 、t o p d i s c 、t e e n 等，但这些协议都存在着一定的不足 与缺陷。论文中对这些路由协议进行了分析与研究，并针对其不足，提出了基于蚁群算法 的无线传感器网络分层路由协议( i m p r o v e da n tc l u s t e r i n gh i e r a r c h y ，i a c h ) 。 蚁群算法是一种优良的演化算法，具有简单易于实现、局部工作、将链路质量融合到 信息素形成中以及支持多条路径等特点，本文基于蚁群算法设计了路由协议i a c h 。该协 议通过在整个网络中广播类似蚂蚁的报文来建立若干个路径链，形成和更新各条路径上的 信息素，并最终向基站或汇聚节点提交融合后的数据。信息素的形成不仅考虑簇内节点的 全部能量消耗，还融合了节点的剩余能量。节点在选择路由时，根据信息素浓度计算各节 点被选择作为下一跳的概率，以形成路径链。也就是说，剩余能量多的节点更有可能在路 径链中承担耗能较大的任务，总体能耗最少的路径链方案更有可能脱颖而出，而且数据包 的发送不会总是沿着一条路径。这样，在沿着路径链发送的同时，能使节点能量的消耗尽 可能的平均，提高网络生命周期。经过对该路由协议的仿真测试，证明该算法基本达到了 无线传感器网络路由算法的设计目标。 关键字：i a c h ，无线传感器网络，蚁群算法 南京邮电大学硕士研究生学位论文 a b s t r a c t i nr e c e n ty e a r s ，a d v a n c e si nw i r e l e s sc o m m u n i c a t i o n sa n de l e c t r o n i c sh a v ee n a b l e dt h e d e v e l o p m e n to ft i n ys e n s o rn o d e s w i r e l e s ss e n s o rn e t w o r k ( w s ，w h i c hc o n s i s to ft h e s e l o w - p o w e ra n dm u l t i f u n c t i o n a ls e n s o rn o d e s ，w i l lh a v eav a r i e t yo fa p p l i c a t i o n si nt h ef u t u r ea n d c u r r e n t l yi sah o tr e s e a r c hf i e l do fc o m p u t e rs c i e n c ea n dt e c h n o l o g y r o u t i n gi nw s n i sv e r yc h a l l e n g i n gd u et os e v e r a lc h a r a c t e r i s t i c st h a td i s t i n g u i s hi tf r o ma d h o ea n do t h e rc o m m u n i c a t i o nn e t w o r k s t h u sm a n yn e wa l g o r i t h m sh a v eb e e np r o p o s e df o r r o u t i n gi nw s n t h e s ey e a r s ，s u c ha sl e a c h ，p e g a s i s ，g a f , t o p d i s c ，t e e n ，e t c h o w e v e r , t h e r ea r eal o to fs h o r t c o m i n g sa n dd e f i c i e n c i e se x i s t i n gi nt h e s ep r o t o c o l s ，w h i c ha r ea n a l y z e d a n dc o m p a r e di nt h et h e s i sa n do nt h eb a s i so fa s s i m i l a t i n gt h ee x c e l l e n ti d e aa m o n gt h e m ，an e w r o u t i n ga l g o r i t h m ，i m p r o v e da n tc l u s t e r i n gh i e r a r c h y ( i a c h ) ，i sp r o p o s e d a n tc o l o n ya l g o r i t h mi sag o o de v o l u t i o n a r ya l g o r i t h m ，w h i c hh a sl o t so fc h a r a c t e r i s t i c s ， i n c l u d i n ge a s yt ob er e a l i z e d ，l o c a lw o r k , i n t e g r a t i n gl i n kq u a l i t yi n t ot h ec o m p u t a t i o no ft h e p h e r o m o n ec o n c e n t r a t i o n , s u p p o r t i n gm u l t i - p a t h i a c h i s d e s i g n e db a s e do na n tc o l o n y a l g o r i t h m t h i sp r o t o c o ls e t su p 百n u m b e ro fp a t hc h a i n st of o r ma n du p d a t ep h e r o m o n eo ne a c h p a t hb yb r o a d c a s t i n ga n t - l i k e dp a c k e t st h r o u g ht h en e t w o r k ，a n du l t i m a t e l ys u b m i t si n t e g r a t e d d a t at ot h eb a s es t a t i o no rs i n kn o d e t h ef o r m a t i o no fp h e r o m o n et a k e si n t oa c c o u n tn o to n l yt h e e n t i r ee n e r g yc o n s u m p t i o no fn o d e si nac l u s t e r , b u ta l s ot h ec o n v e r g e n c eo ft h er e s i d u a le n e r g y o fn o d e s w h e ns e l e c t i n gt h er o u t i n g ，n o d e sw i l lc a l c u l a t et h en e x th o ps e l e c t i o np r o b a b i l i t y a c c o r d i n gt op h e r o m o n ec o n c e n t r a t i o n ss oa st of o r mt h ep a t hc h a i n i no t h e rw o r d s ，t h en o d e s w i mm o r er e s i d u a le n e r g ya r em o r el i k e l yt oa s s u n l eal a r g e re n e r g y - c o n s u m i n gr e s p o n s i b i l i t y , a n dt h ep a t hc h a i ns o l u t i o n sw h i c hc o n s u m et h eo v e r a l lm i n i m u me n e r g ya r em o r el i k e l yt o c o m et ot h ef o r e ，p a c k e t sw i l ln o ta l w a y sb es e n ta l o n go n ep a t h i nt h i sw a y , w h e nd a t as e n t a l o n gt h ep a t hc h a i n , t h en o d ee n e r g yc o n s u m p t i o nc a na v e r a g ea sm u c ha sp o s s i b l ea n dt h e l i f e c y c l eo fn e t w o r kw i l lb ei m p r o v e d t h er e s u l t so fs i m u l a t i o ns h o wt h a tt h ei a c ha c h i e v e si t s d e s i g no b j e c t i v e k e yw o r d s ：i m p r o v e da n tc l u s t e r i n gh i e r a r c h y , w i r e l e s ss e n s o rn e t w o r k , a n tc o l o n y a l g o r i t h m i i 南京邮电大学硕士研究生学位论文缩略词 缩略词 缩略词英文全称译文 w s nw i r e l e s ss e n s o rn e t w o r k 无线传感器网络 a c o a n tc o l o n ya l g o r i t h m蚁群算法 i a c h i m p r o v e da n tc l u s t e r i n gh i e r a r c h y改进的蚁群聚类分层协议 l e a c hl o w e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y低功耗自适应聚类路由 p o w e r - e f f i c i e n tg a t h e r i n gi ns e n s o ri n f o r m a t i o n传感信息系统能量效率聚集协 p e g a s i s s y s t e m 议 g 鼹 g e o g r a p h i c a la d a p t i v ef i d e l i t y基于地理位置的拓扑算法 t o p d i s et o p o l o g ydiscoveropologyd i s c o v e r y拓扑发现算法 t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o r基于能量效率的阈值敏感传感 t e e n n e t w o r kp r o t o c o l器网络协议 、v l a nw i r e l e s sl o c a la r e an e t w o r k s无线局域网 b sb a s es t a t i o n 基站 m cm e d i u ma c c e s sc o n t r o l 介质访问控制 f d m a f r e q u e n c yd i v i s i o nm u l t i p l ea c c e s s频分多址接入 s d m a s p a c ed i v i s i o nm u l t i p l ea c c e s s 空分多址接入 c d m ac o d ed i v i s i o nm u l t i p l ea c c e s s 码分多址接入 无线自组网按需平面距离矢量 a o d va dh o eo n - d e m a n dd i s t a n c ev e c t o r 路由协议 t o r a t e m p o r a l l yo r d e rr o u t i n ga l g o r i t h m临时按序路由协议 d d d i r e c t e dd i f f u s i o n定向扩散 s a r s e q u e n t i a la s s i g n m e n tr o u t i n g连续分配路由 n pn o n - d e t e r m i n i s t i cp o l y n o m i a l 非确定多项式 a sa n ts y s t e m 蚂蚁系统 n sn e t w o r ks i m u l a t o r网络器 第5 7 页 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名锯名壤 日期：护9 妒、弓 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存 论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密 论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：镑钚霉 导师签名： 飘、矽珂矗 日期：汐c 7 鲰弓 南京邮电大学硕士研究生学位论文第一章绪论 1 1 课题背景 1 1 1 无线传感器网络概述 第一章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 是一种新型的、无基础设施的、自 组织的无线网络n 1 。无线传感器网络中的传感器节点完成一些数据采集工作，节点通过传 感器网络将数据发送到网络中，并最终由特定的应用接收。传感器节点集成传感器件、数 据处理单元和通信模块，并通过自组织的方式构成网络。借助于传感器节点中内置的形式 多样的传感器件，可以测量所在周边环境中的热、红外、声纳、雷达和地震波信号等信号， 从而探测包括温度、湿度、噪声、光强度、压力、土壤成分、移动物体的大小、速度和方 向等等众多感兴趣的物质现象。无线传感器网络是一种全新的信息获取和信息处理模式。 无线传感器网络与传统的无线网络( 如w l a n 和蜂窝移动电话网络) 有着不同的设计 目标，后者在高度移动的环境中通过优化路由和资源管理策略最大化带宽的利用率，同时 为用户提供一定的服务质量保证。在无线传感器网络中，除了少数节点需要移动以外，大 部分节点都是静止的。因为它们通常运行在人无法接近的恶劣甚至危险的远程环境中，能 源无法更换，设计有效的策略延长网络的生命周期成为无线传感器网络的核心问题。当然， 从理论上讲，太阳能电池能持久地补给能源，但工程实践中生产这种微型化的电池还有相 当的难度。在无线传感器网络的研究初期，人们一度认为成熟的i n t e m e t 技术加上a dh o e 路由机制对无线传感器网络的设计是足够充分的，但深入的研究表明口1 无线传感器网络与 传统网络有着明显不同的技术要求。为了适应广泛的应用程序，传统网络的设计遵循着“端 到端 的边缘论思想，强调将一切与功能相关的处理都放在网络的端系统上，中间节点仅 仅负责数据分组的转发，对于无线传感器网络，这未必是一种合理的选择；一些为自组织 的a dh o e 网络设计的协议和算法也未必适合无线传感器网络的特点和应用的要求d 3 。无线 传感器网络中的大部分节点不像传统a dh o e 网络中的节点一样快速移动，因此没有必要 花费很大的代价频繁地更新路由表信息；中间节点上与具体应用相关的数据处理、融合和 缓存也显得很有必要。在密集分布的无线传感器网络中，相邻节点问的距离非常短，低功 耗的多跳通信模式节省功耗，同时增加了通信的隐蔽性，也避免了长距离的无线通信易受 第1 页 堕室坚皇查芏里主旦圣兰兰些苎兰 墨二苎塑兰 外界噪声干扰的影响，这些独特的要求和制约因素为传感器网络的研究提出了新的技术问 题。 无线传感器网络由许许多多个功能相同或不同的无线传感器节点组成。每一个传感器 节点由数据采集模块( 传感器) 、数据处理和控制模块( 微处理器、存储器) 、通信模块 ( 无线收发器) 和供电模块( 电池、能量转换器) 等组成。节点在网络中可以充当数据采 集者、数据中转站或簇首节点( c l u s t e r - h c a dn o d e ) 的角色。如图i - i 所示，作为数据采 集者，传感器节点收集周围环境的数据( 如温度、湿度) ，通过通信路由协议直接或间接 将数据传输给远方基站( b a s e s t a t i o n ) 或汇聚节点( s i n k n o d e ) 。作为数据中转站，节点 除了完成采集任务外，还要接收邻居节点的数据，将其转发给距离基站更近的邻居节点或 者直接转发到基站或汇节点作为簇首节点，节点负责收集该簇内所有节点采集的数据， 经数据融合后，发送到基站或汇节点。 i 譬 叁 肇 图i - i 无线传感器网络工作示意图 传感器网络与传统网络相比有一些独有的特点。正是由于这些特点使得传感器网络存 在很多新问题，提出了很多新的挑战。传感器网络的主要特点有： ( i ) 传感器网络的节点数量大、密度高。为了对一个区域执行监测任务，往有成千上 万个传感器节点空投到该区域。传感器节点分布非常密集，利用节之问高度连接性来保证 系统的容错性和抗毁性。 ( 2 ) 传感器网络的节点有一定的故障率。由于传感器网络可能工作在恶劣的界环境之 中，网络中的节点可能会由于各种不可预料的原因而失效，为了保网络的正常工作，要求 传感器网络必须设计成具有一定的容错能力，允许传器节点具有一定的故障率。 ( 3 ) 传感器网络节点在电池能量、计算能力和存储容量等方面存在限制。节点由于受 价格、体积和功耗的限制，其计算能力、程序空间和内存空间普通的计算机功能要弱很多。 这一点决定了在节点操作系统设计中，协议层不能太复杂。网络节点由电池供电，电池的 容量一般不是很大。其特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池， 镕2 面 汐 雹 南京邮电大学硕士研究生学位论文第一章绪论 一旦电池能量用，这个节点也就失去了作用( 死亡) 。因此在传感器网络设计过程中，任 何协议的使用都要以节能为前提。 ( 4 ) 无控制中心。无线传感器网络中没有严格的控制中心，所有节点地位平等，是一 个对等式网络。结点可以随时加入或离开网络，结点的故障不会影响整体网络的运行，具 有很强的抗毁性。 ( s ) 传感器网络的拓扑结构变化很快。由于传感器网络自身的特点，传感器点在工作 和睡眠状态之间切换以及传感器节点随时可能由于各种原因发生故障而失效，或者有新的 传感器节点补充进来以提高网络的质量，这些特点都使得传感器网络的拓扑结构变化很 快，这对各种算法( 如路由算法和链路质量控制协议等) 的有效性提出了挑战。此外，如 果节点具备移动能力，也有可能带来网络的拓扑变化。 ( 6 ) 以数据为中心。在传感器网络中人们关心某个区域的某个观测指标的值，比如“检 测区域的温度是多少 ，“某个节点所探测到的二氧化碳浓度值如何 。 1 1 2 面向环境监测的应用背景 无线传感器网络应用领域非常广泛，但是无论在哪一种应用领域中，w s n 一般都不是 作为一个单独的系统运行，这说明w s n 市场最大的特点是“无单一市场、市场无处不在 【4 】。美国的相关研究表明，预计近几年为w s n 的市场发展期，市场成熟期应在2 0 1 0 年以 后；而根据日本“传感器网络 联盟的研究报告，发展期在2 0 0 7 年左右，2 0 1 0 年左右为 w s n 市场的成熟期。不论是根据哪种预测，到2 0 1 0 年全球w s n 市场的整体规模都将超 过1 0 0 0 亿美元。目前w s n 产业己经具备基本的政策环境，得到了各国政府的政策支持， 也出现有大量的市场推动者。所以说w s n 有着良好的发展前景。 在美国，已经有研究成果出现，例如加州大学的大鸭岛( g r e a td u c ki s l a n d ) 项卧引。 加州大学伯克利分校计算机系i n t e l 实验室和大西洋学院联合开展了一个利用传感器网络 监测海岛生态环境的项目。项目组在若干海岛上进行了实地考察并建立了完善的后勤系 统。最后在大鸭岛开展了对海燕栖息地的研究。节点上装有多种传感器以监测海岛上不同 类型的数据。使用光敏感传感器、数字温湿度传感器和压力传感器来监测海燕巢穴的微观 环境使用低能耗的被动红外传感器监测巢穴的使用情况。实验中首先关注的问题是传感器 网络的生存期。为了检验传感器节点的生存期，节点上运行了一个应用程序，该程序每隔 7 0 秒采样一次数据并发送到基站。数据报长度为3 6 个字节，并在本地记录发送时间。经 过1 2 3 天的试验后，整个传感器网络得到了大约1 1 万条数据记录。实验表明，传感器网络 第3 页 南京邮电大学硕士研究生学位论文第一章绪论 在这样的应用环境中有非常明显的优势。 对于很多场合来说，现场测量以及数据采集只能使用无线通信技术，此时无线传感器 网络具有非常明显的优势。把传感器送到危险的环境中，这些分散在各处的传感器组成a d h o c 网络，可以实现传感器之间和与控制中心之间的通信，将传感器所在现场的信息传送 到危险现场以外，避免救援人员进入现场，就能收集和辨别事故信息。与传统的环境监测 方法相比，使用传感器网络对环境进行监测有三个显著的优势： ( 1 ) 传感器节点的体积很小且整个网络只需要部署一次，因此我们认为部署传感器网 络对所监测的环境影响很小。这一点在外来生物活动敏感的环境中尤其重要。 ( 2 ) 传感器节点数量很大，分布密度高，每个节点可以监测到局部环境的详细信息 并汇总到基站。因此传感器网络具有数据采集量大，精度高的特点。 ( 3 ) 无线传感器网络的节点本身具有一定的计算能力和存储能力，可以根据环境的 变化进行较为复杂的监测。例如，在矿井环境监测中通常需要对矿井风速、矿尘、一氧化 碳、温度、湿度、氧气、硫化氢和二氧化碳等参数进行监测。现有的监控检测系统需要在 矿井铺设通信线路，传递监测信息。生产过程中矿井结构在不停变化，加之有些坑道空间 狭小，对通信线路的延伸和维护提出了很高的要求。一旦通信链路发生故障，整个监测系 统就可能瘫痪。而传感器节点具有无线通信的能力，可以在节点间进行协同监控。节点的 计算能力和无线通信能力使得传感器网络能够重新编程和重新部署，对环境变化、传感器 网络自身变化以及网络控制指令做出及时反应。即使矿井结构遭到破坏，仍能自动恢复组 网，传递信息，为矿难救助等提供重要信息。无线传感器网络自身的这些特点特别适用于 环境监测。 传感器节点的部署密度通常比较大，并且部署在若干个不相邻的监测区域内，从而形 成多个传感器网络。传输网络是负责协同各个传感器网络网关节点、综合网关节点信息的 局部网络。基站负责搜集传输网络送来的所有数据，发送到i n t e r a c t ，并将传感数据的日志 保存到本地数据库中。对于大规模集中监测系统，传感器节点搜集到的数据传送到中心数 据库存储。中心数据库提供远程数据服务，科研人员可以通过接入终端使用远程数据服务， 对数据进行进一步的分析处理。 如前所述，w s n 有着广泛而有价值的应用领域，结合现代监测理论及w s n 技术，布 置节点实现无人值守，为设计施工及时反馈信息，对减轻观测的劳动强度，提高安全监控 的技术水平，具有重大的社会经济效益和应用价值。而在个人研究既有重要的社会意义又 蕴含着潜在的经济价值。因此它已经引起了世界工业界和学术界的极大关注，开展这项对 人类未来生活影响深远的前沿科技的研究，对整个国家的社会、经济将有重大的战略意义。 第4 页 南京邮电大学硕士研究生学位论文第一章绪论 而从网络层模型的角度分析，每一层都有需要结合w s n 的特点进行细致研究的问题，已 有的研究主要集中在网络层和链路层。 1 1 3 研究的目的与意义 路由协议在无线传感器网络通信中发挥着重要的作用。网络数据传输离不开路由协 议，路由协议是其组网的基础。目前，对无线传感器网络的研究主要集中在网络层和链路 层，而路由算法已成为无线传感器网络的核心技术之一。 根据无线传感器网络中各个节点的地位和功能是否相同，路由协议可以分成平面路由 协议和分层路由协议。在平面路由协议中，所有节点的地位是平等的，不存在等级和层次 差异。它们通过相互之间的局部操作和信息反馈来生成路由。平面路由的优点是简单、易 扩展，无须进行任何结构维护工作，所有网络节点的地位平等，不易产生瓶颈效应，因此 具有较好的健壮性。平面路由的最大缺点在于：网络中无管理节点，缺乏对通信资源的优 化管理，自组织协同工作算法复杂，对网络动态变化的反应速度较慢等。在分层结构的网 络中，簇内各成员的功能比较简单，不需要维护复杂的路由信息，这样就大大减少了网络 中路由控制信息的数量，而且分层路由协议具有很好的可扩展性。其缺点是簇首节点可能 会成为网络的瓶颈。如果簇内节点数量众多，簇首节点的能量会很快耗尽，从而网络需要 重新组织。 无线传感器网络除了具有a dh o c 网络的一般特性，如无中心自组织等，还具有本身 的一些显著特点：每个传感器节点通常是带有有限的、不可更换的电源，节点数量多，并 且节点出现故障的频率要大于a dh o c 网络，维护困难甚至不可维护。因此，与传统网络 以提供高质量网络服务为主要目标不同，传感器网络必须以节约能源为主要目标，并在延 长网络存活时间和提高网络吞吐量、降低通信延迟间做出选择。 根据无线传感器网络的这些特点，在设计路由协议时，必须考虑算法的节能性、数据 融合、扩展性、健壮性等方面。其中首要目标是节能性，要通过高效的算法形成合理的网 络结构，通过能量管理阻止网络连通性的下降，延长网络的生命周期。因此，能量消耗成 了通信连接性能好坏、网络运行周期长短的主要决定因素。 路由选择问题是w s n 网络构建时所要着重考虑的一个问题，从路由的角度来看，w s n 有其自身的特点，使它既不同于传统网络，又不同于无线自组网a dh o c 网络。传统的无 线a dh o c 网络路由协议不适合用于w s n ，我们必须设计全新的、适合于w s n 特点的路 由协议。 第5 页 南京邮电大学硕士研究生学位论文第一苹绪论 路由协议作为影响网络性能的一个重要因素，是确保w s n 网络正常运行的关键。虽 然已提出了很多的协议，但目前已有的无线传感器网络路由协议大都存在着各种不同缺 陷。因此研究这些路由协议，针对特殊的应用环境提出合适的解决方案显得尤为重要，也 是此论文的意义所在。 蚁群算法是最近提出的求解复杂组合优化问题的启发式算法，它是模拟自然界中蚂蚁 搜索食物行为而提出的一种启发式智能进化算法，该算法由意大利学者m d o r i g o 等人提 出。虽然单只蚂蚁的行为非常简单，但是蚂蚁间可以通过一种叫做信息索的分泌物作为媒 介进行信息交流，通过合作来实现复杂的计算。 本课题以提高w s n 网络的性能为目的，对其中的路由问题进行研究，重点对现有的 w s n 分层路由协议进行归纳、对比、分析，从中得出了值得借鉴的优秀思想。有针对性的 选择了分层路由协议l e a c h 和p e g a s i s 作为研究重点，分析了其存在的问题，并针对这 些问题融入蚁群算法提出了改进方案。总之，对该领域进行深入而广泛的研究将为w s n 的应用提供重要的科学依据。 1 2 本文研究的主要内容 本文主要工作归纳如下： ( 1 ) 总结了无线传感器网络的发展历程、概念、结构、特点及应用，分析了w s n 存 在的关键性问题。 ( 2 ) 深入研究了w s n 的网络协议体系和路由协议，分析和比较了目前国外学者提出 的几种有代表性的针对w s n 的路由协议及它们的优缺点。 ( 3 ) 有针对性的选择了经典的分层路由协议l e a c h 和p e g a s i s 作为研究重点，分 析了它们的设计思想、工作过程及存在的问题，并提出了基于蚁群算法的改进算法i a c h ， 详细描述了算法的整个过程。 ( 4 ) 采用n s 2 网络仿真工具对l e a c h 和p e g a s i s 协议和改进后的协议i a c h 进行 了仿真实现，并对仿真结果进行了比较分析，证实改进后的算法在网络生命周期、系统整 体能耗上比原算法均有了很大的提高。 1 3 论文的组织结构 本文共分为六章，其主要内容如下： 第一章：概述无线传感器网络的特点及现阶段研究热点，分析该课题的研究背景及研 第6 页 南京邮电大学硕士研究生学位论文 第一章绪论 究目的，描述本文所做的主要工作及组织结构。 第二章：讨论无线传感器网络路由协议的特点及其设计要求，分析分层路由协议的特 点及其研究现状。在对l e a c h 、p e g a s i s 协议进行重点研究的基础上，对分层路由算法 三个关键技术进行分析，并指出分层路由算法现在需要解决的问题。 第三章：介绍蚁群算法的起源、应用及实现，并针对具体参数的选取进行了分析。 第四章：针对现有分层路由算法存在的缺点，设计出一种新的分层路由协议，对所设 计路由协议过程进行详细描述，并指出新算法的特点。 第五章：利用仿真工具n s 2 对该协议进行仿真，从网络生存周期、能量效率、平均端 到端的延迟等方面验证该协议。 第六章：对本文的内容进行总结，并对以后的研究工作进行展望。 第7 页 南京邮电大学硕士研究生学位论文 第二章路由协议技术分析 第二章路由协议技术分析 2 1 无线传感器网络的协议栈 在传统有线网和无线网中，有两种参考模型：o s i 参考模型和t c p 参考模型 6 1 。如果 将无线传感器网络参照o s i 网络体系结构进行划分，可将无线传感器网络划分为物理层、 数据链路层、网络层、传输层、应用层和能源管理平台，移动管理平台和任务管理平台的 三维立体参考模型。无线传感器网络参考模型如图2 1 所示。其中，各层的功能和作用如 下： 图2 1 无线传感器网络参考模型 ( 1 ) 物理层：无线传感器网络物理层的设计要根据实际需要而定。以发送接收信号 为主要功能的物理层首先要考虑的是信号的传输介质。目前，无线传感器网络主要是基于 无线电通信，在一些特殊的应用中也适用红外线和声波。无线电通信要解决的主要问题是 无线频段的选择，跳频技术和扩频技术。物理层是决定无线传感器网络的节点体积、成本 及能耗的关键环节，是无线传感器网络的研究重点之一。能耗和成本是无线传感器网络最 主要的两个性能指标，也是无线传感器网络物理层协议设计中需要重点考虑的关键问题。 ( 2 ) 数据链路层：数据链路层重点研究介质访问控制。介质访问控制( m e d i u ma c c e s s c o n t r o l ，m a c ) 协议的主要功能是在相互竞争的用户之间分配信道资源。在传统网络中， 第8 页 南京邮电大学硕士研究生学位论文第二章路由协议技术分析 有两种基本的分配无线信道的方法【7 】。预先固定分配信道法，包括频分多址接入 ( f r e q u e n c yd i v i s i o nm u l t i p l ea c c e s s ，f d m a ) 和空分多址接入( s p a c ed i v i s i o nm u l t i p l e a c c e s s ，s d m a ) 、时分多址( t i m ed i v i s i o nm u l t i p l ea c c e s s ，t d m a ) 、码分多址接入( c o d e d i v i s i o nm u l t i p l ea c c e s s ，c d m a ) 等。随机分配信道法，包括8 0 2 11 使用的c s m a 、m a c a 和用于无线的m a c a w ( m u l t i p l ea c c e s sw i t hc o l l i s i o na v o i d a n c ef o rw i r e l e s s ，m a c a w ) 等。 ( 3 ) 网络层：网络层路由协议的功能是在网络中任意需要通信的两点间建立并维护 数据传输路径。传统的无线网络的路由协议设计是以避免网络拥塞、保持网络的连通性和 提高网络服务质量为主要目标。 ( 4 ) 传输层：传输层的主要功能是负责数据流的传输控制，在网络层的基础上为应 用层提供一个可靠、高质量的数据传输服务。t c p 是因特网上的主要传输协议，它的目的 是在不可靠的i p 层上为应用层提供面向连接的、可靠的数据传输服务。其主要功能包括 流量控制、差错控制和拥塞控制。 ( 5 ) 应用层：解决应用的共性问题，包括应用基础和典型应用，目前各国学者正在 深入研究的应用层协议有：s m p ( s e n s o rm a n a g e m e n tp r o t o c 0 1 ) ，t a d a p ( t a s k a s s i g n m e n t a n dd a t aa d v e r t i s e m e n tp r o t o c 0 1 ) 和s q d d p ( s e n s o rq u e r ya n dd a t ad i s s e m i n a t i o np r o t o c 0 1 ) 。 各管理平台的作用如下： ( 1 ) 能源管理平台管理节点如何使用自己的能源。比如节点会在收到一个报文后关 闭自己的接收装置，这可以避免获得重复的报文。而且，一旦节点的能量级较低的时候， 节点可以向邻居广播一个报文，告诉邻居自己不再承担路由转发的任务，剩余能量只是用 来感知数据。 ( 2 ) 移动管理平台用来探测和注册节点的移动，因此，总是维护着到s i n k 节点的路 由，并且，节点总是知道谁是自己的邻居，可以平衡自己的能源和任务。 ( 3 ) 任务管理平台平衡和调度某个特殊区域分配的任务。在同一时间，在某个区域 的所有节点并不需要都执行相同的感知任务，因此，是否执行这个任务就取决于节点自身 的能源状况。这三个平台互相配合工作，使得传感器节点能够协调、高效地运行，为整个 网络进行路由，在节点间进行资源共享。 2 2 无线传感器网络网络层特点 我们要针对无线传感器网络设计新的路由协议，必须清楚的了解其网络层的特点，知 第9 页 南京邮电大学硕士研究生学位论文第二章路由协议技术分析 道为什么不能使用传统网络和a dh o c 网络中的路由协议。 ( 1 ) 从宏观上看，无线传感器网络的数据传输遵循多对一( m a n yt oo n e ) 的模式， 这是二种收敛播( c o n v e r g ec a s t ) f 8 】，s i n k 节点是无线传感器网络中的特殊节点，起着非 常关键的作用，经常作为网关与i n t e m e t 相连接。它远离感知区域，向传感器节点发送控 制命令，传感器节点在感知或接收到新数据后，经过中间节点的转发和融合，最终的目的 是要将数据传送到s i n k 节点，由s i n k 节点进行分析、加工，转换成人们所需的信息。从 宏观上看，这是传统网络很少有用到的一种通信模式收敛播，图2 2 示意了这种通信 模式。 图2 2 收敛搔 ( 2 ) 无线传感器网络是以数据为中心的( d a t ac e n t r i c ) 进行路由的，不同于传统a d h o c 网络以地址为中心( a d d r e s sc e n t r i c ) 进行路由的模式，以数据为中心进行路由是无线 传感器网络网络层的一个显著特点，与之相反，传统网络可以称为以地址为中心或以节点 为中心进行路由，传统网络传送的数据是和节点的口地址联系起来的，以数据为中心的特 点要求传感器网络能够脱离传统网络的寻址过程，快速有效的组织起各个节点的信息并融 合提取出有用信息直接传送给用户。图2 3 说明了以数据为中心进行路由和以地址为中心 进行路由的区别。 第1 0 页 南京邮电大学硕士研究生学位论文第二章路由协议技术分析 l a 源2 s i n k 以数据为中心的 路由 2 b a s i n k 以地址为中心的 路由 2 b 图2 3 以地址为中心进行路由和以数据为中心进行路由 ( 3 ) 无线传感器网络邻近节点间采集的数据具有相似性，存在冗余信息，需经数据 融合处理再进行路由；由于传感器最基本任务就是感知、采集数据，在无线传感器网络中， 数量庞大的无线传感器密集分布在感知区域，地理位置邻近的节点间采集的数据必然具有 相似性，如果不对这些相似的数据进行数据融合，将会产生大量的冗余信息，直接将这些 未经处理、存在冗余的数据进行传输，将会造成网络带宽、节点能量的巨大浪费，导致节 点迅速死亡，缩短整个网络的生命周期。 ( 4 ) 无线传感器网络的节点易于失效，且数量远远大于传统的a dh o e 网络中的节点 数，而节点的处理能力、存储能力和通信能力却远远低于传统的a dh o c 网络中的节点： 无线传感器网络中传感器节点分布密集，数量巨大，可能达到几万、几十万，甚至更多， 而对于每个无线传感器节点来说，其处理能力、存储能力和通信能力无法和传统a dh o e 网络中的节点便携式计算机相提并论，例如，u c b e r k e l e y 开发的无线传感器节点 m o t e ，其c p u 采用a t m e l 公司的8 位处理器，主频为4 m h z ，其r o m 是1 2 8 k bf l a s h ， 其s d r a m 只有4 k b ，其e e p r o m 也只有4 k b 。如何在这种节点数量巨大，单个节点易 于失效且资源及其有限的网络中进行路由就成了前所未有的挑战。 ( 5 ) 无线传感器网络中的大部分节点不像传统a dh o e 网络中的节点一样快速移动， 因此没有必要花费很大的代价频繁地更新路由表信息。在传统a dh o e 网络中，由于应用 第l l 页 南京邮电大学硕士研究生学位论文第二章路由协议技术分析 的要求，节点频繁移动，动态变化的拓扑结构是传统a dh o c 网络最显著的特点，快速有 效的达到路由协议收敛状态是其路由协议的首要目标【9 】；而对于传感器网络，除了原有节 点失效和新的节点加入外，拓扑结构基本不会发生变化，因此没有必要花费很大的代价频 繁地更新路由表信息。 ( 6 ) 单向信道的存在会对路由协议带来影响。常规路由协议通常认为底层的通信信 道是双向的；但是在采用无线通信的无线传感器网络环境中，由于发射功率或地理位置等 因素的影响，可能存在单向信道。它为常规路由协议带来三个严重的影响：认知的单向性、 路由单向性和汇点不可达【1 0 1 。 由于无线传感器网络网络层以上特点，使得传统网络的路由协议如r i p 、o s p f 以及传 统的a dh o c 网络路由协议如a o d v 1 1 】( a dh o co n - d e m a n dd i s t a n c ev e c t o r ) 和t o r a 1 2 】 ( t e m p o r a l l yo r d e rr o u t i n ga l g o r i t h m ) 都不适用于无线传感器网络，无线传感器网络需要 设计新的路由协议。 2 3 路由协议设计要求 无线传感器网络的路由协议负责将数据分组从源节点通过网络转发到目的节点，它主 要的功能是寻找源节点和目的节点间的优化路径，将数据分组沿着优化路径正确转发。由 于无线传感器网络具有很强的应用相关性，不同的应用中的路由协议的差别可能很大，没 有单一的路由协议会满足各种应用场合。此外，无线传感器网络的路由机制还经常与数据 融合技术联系在一起，通过减少通信量而节省能量。所以，传统无线网络的路由协议不适 应于无线传感器网络。 由于传统无线网络的首要任务是提供高质量的服务以及合理地利用网络带宽，因此要 求路由协议完成移动条件下最优路径的寻找，拥塞避免和流量均衡等功能，而并未把能耗 问题作为考虑的重点。对于无线传感器网络而言能量资源非常紧张，必须把如何节约能量 资源作为首要考虑因素，设计无线传感器网络路由协议需要满足的要求有： ( 1 ) 能量有效性。为最大限度地延长无线传感器网络的寿命，路由协议在进行路径 选择时，要把能否节约节点能耗，能否使网络能耗均衡作为衡量路径好坏的首要标准。 ( 2 ) 简单性。相对于传统网络而言，传感器节点的运算能力和存储能力极其有限， 这种硬件资源有限的节点却承担着主机和路由器的双重角色，这就要求我们不能照搬传统 网络路由协议的设计恩想，要为这种节点资源有限的特殊网络“量身定制一种简单有效 路由协议，要求路由协议的报文和算法简单有效，实现的程序代码短小精悍，路由表项尽 第1 2 页 南京邮电大学硕士研究生学位论文第二章路由协议技术分析 可能少。 ( 3 ) 健壮性和容错性。无线传感器网络多应用于恶劣环境，传感器节点经常会因为 能量耗尽或环境因素而失效，加之无线链路自身的不稳定性，要求无线传感器网络具有一 定的容错能力。 ( 4 ) 可扩展性。在无线传感器网络中，由于经常有节点失效和新节点加入，网络拓 扑动态变化频繁，因此路由机制需要具备一定