（信息与通信工程专业论文）基于petri网的无线链状网mac协议与路由算法研究.pdf

“ ：，i i ! 原创性声明 | i f j f l l1i l li i i1 1 1 1f l l l li ii y 1719 4 2 5 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 储硌盂蛊吼竺年量月萼日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：皇曼堑导师签名拄占期：业月猸 摘要 随着列车重载运输的高速发展，国家对货物列车的安全运行提出 了更高的要求。针对货物列车的特点，本文提出了一种利用无线传感 器对重载货物列车危险状态进行在线监测的新网络一一无线链状网 ( w i r e l e s sc h a i nn e t w o r k ，w c n ) 。虽然无线传感器网络的研究已取得 一定成果，但其特殊性使得无线传感器网络中的通信协议不适合这种 网络结构。 在分析无线传感器网络相关领域的研究成果及应用情况之后，结 合8 6 3 课题的研究内容，并针对无线链状网络的结构特点和多跳中继 通信的特点，将方向定在设计新的结合路由信息的m a c 协议和相关 的路由协议。本文主要做了以下几个方面研究工作： 首先，本文在当前无线传感器网络通信协议i e e e 8 0 2 11 的基础 上，根据跨层设计思想，将网络层和m a c 层信息结合起来设计出一 种结合主动路由和多信道的m a c 协议( m c m a c ) ，以解决无线传感 器网络当前信道容量不足的问题。并依据有色p e t r i 网理论，使用 c p n t o o l s 工具对该多信道m a c 协议建模和仿真，从可达图和线性代 数两个方面论证该模型的正确性。 其次，基于无线链状网的拓扑结构特点，选择o l s r 协议作为基 础协议，一方面修改h e l l o 和t c 消息的设定，使其能为m c m a c 协议有效地分配信道，另一方面改进m p r 集的设定，快速的寻找合 适的路由而非最优路径。改进后的协议称之为e o l s r 协议。 最后，利用n s 2 分别对多信道m a c 协议和改进的o l s r 路由协 议进行性能仿真分析，并与标准m a c 协议i e e e 8 0 2 11 和o l s r 协 议的性能分析比较。仿真结果表明，m c m a c 协议性能明显高于 i e e e 8 0 2 11 协议，e o l s r 协议在各方面的表现均比o l s r 协议要好。 关键词有色p e t r i 网，无线链状网，m c m a c ，e o l s r a b s t r a c t a st h eh i g h l yd e v e l o p m e n to ff r e i g h tt r a i n ，t h eg r e a t e rd e m a n d so f s a f e t y w o r ka r er e q u e s t e d i nt h i st h e s i s ，an e wn e t w o r kn a m e dw i r e l e s s c h a i ni sp r o p o s e dt om o n i t o rt h er e a l t i m es t a t eo fo v e r l o a df r e i g h tt r a i n d u et ot h ep a r t i c u l a r i t yo fw i r e l e s sc h a i nn e t w o r k ，t h ec o m m u n i c a t i o n p r o t o c o l so fw i r e l e s ss e n s o rn e t w o r ko nw h i c hm a n yr e s e a r c hh a db e e n d o n ea r ei n a p p r e c i a t i v ef o ri t a f t e raf a i r l ys t u d yo nt h ea c h i e v e m e n t sa n d a p p l i c a t i o n so f w i r e l e s s s e n s o rn e t w o r k ，a n dc o m b i n e dw i t ht h en a t i o n a l8 6 3t o p i c ，t h et h e s i sa i m s a taf u l l yd e s i g no fn e w p r o t o c o l sa b o u tt h em a cp r o t o c o lc o m b i n e dw i t h r o u t ei n f o m a t i o na n dr o u t ep r o t o c o lr e l a t e d ，c o n s i d e r i n gt h e d e s i g n f e a t u r ea n dm u l t i h o po fw i r e l e s sc h a i nn e i w o r k t h em a i nw o r k sa r ea s f o l l o w s ： f i r s t ，am u l t i - c h a n n e lm a cp r o t o c o lb a s e do nt h ei e e e8 0 2 1 li s p r o p o s e dt os o l v et h ep r o b l e mo ft h el a c ko fc h a n n e lc a p a c i t y , w h i c h u n i t e dt h ei n f o r m a t i o no fm a cl a y e ra n dn e t w o r kl a y e r a n dw em a k e c p n t o o l sa sat o o lt ob u i l dt h em o d e lo fm u l t i c h a n n e lm a cp r o t o c o l a n dp e r f o r mt h es i m u l a t i o nu s i n gt h et h e o r yo fc o l o r e dp e t r in e t t h e n ， t w om e t h o d s - - r e a c h a b i l i t yt r e ea n dm a t r i xe q u a t i o n s - f u l l yv e r i f yt h e c p nm o d e l s e c o n d ，c o n s i d e r i n gt h et o p o l o g yo fw c na n dm a k i n go l s r p r o t o c o la st h eb a s i cp r o t o c o l ，w ed ot w om a i n l yc h a n g e so no l s r ： m o d i f y i n gt h ef o r m a to fh e l l oa n dt cm e s s a g et oa s s i g nc h a n n e l sf o r m c m a cp r o t o c o lm o r ee f f e c t i v e l y ；e n h a n c i n gt h em p rs e l e c t i o nt o c h o o s et h es u i t a b l er o u t er a t h e rt h a no p t i m u mr o u t e w en a m et h en e w r o u t e p r o t o c o le o l s r l a s t ，t oc o m p a r et h ep e r f o r m a n c eo fm c m a cw i t hi e e e 8 0 2 1 l a n de o l s rw i t ho l s r , n s 2i su s e dt op e r f o r mt h es i m u l a t i o no f m e n t i o n e d p r o t o c o la b o v e t h er e s u l ts h o w st h a tm c m a cg i v e s ab e t t e r p e r f o r m a n c et h a n i e e e 8 0 2 11 ，a n de o l s ra l s ot u m so u tah i g h e r b e h a v i o rt h a no l s r k e yw o r d s c o l o r e dp e t r in e t ，w i r e l e s sc h a i nn e t w o r k ，m c - m a c ， e o l s r i i i 目录 摘要i a b s t r a c t i i 第一章绪论j1 1 1 引言1 1 2 本课题的研究背景及意义1 1 2 1 本课题的研究背景l 1 2 2 本课题的研究目的及意义2 1 3 国内外研究现状与水平2 1 3 1p e t r i 网技术的研究与发展2 1 3 2 无线链状网络的研究与发展4 1 4 本文主要研究内容5 1 5 本文的整体结构及章节安排一6 第二章无线链状网的m a c 及路由分析7 2 1 无线链状网概述7 2 1 1 无线链状网的特点7 2 1 2 无线链状网的技术挑战8 2 2 无线链状网的m a c 协议1 0 2 2 1 传统m a c 协议问题。1 0 2 2 2m a c 协议要求1 1 2 3 无线链状网的路由协议1 2 2 3 1 传统路由协议问题1 2 2 3 2 路由协议要求1 3 2 4 本章总结1 4 第三章有色p e t r i 网的网络协议建模理论基础15 3 1 有色p e t r i 网的定义和性质1 5 3 1 1 有色p e t r i 网的定义1 5 3 1 2 有色p e t r i 网的基本性质1 6 3 2 有色p e t r i 网的建模步骤1 9 3 3 有色p e t r i 网的分析方法1 9 3 3 1 可达树方法1 9 3 3 2 线性代数方法2 0 3 4 本章总结2 2 第四章基于p e t r i 网的多信道m a c 协议分析2 3 4 1 无线链状网的多信道m a c 协议2 3 4 1 1 关于多信道协议。2 4 4 1 2 面临的问题2 7 4 1 3m c m a c 协议一2 7 4 2 多信道m a c 协议模型及分析2 8 4 2 1 多信道m a c 协议的c p n 网模型2 8 4 2 2 多信道m a c 协议的模型分析3 2 4 3 多信道m a c 协议的性能仿真3 5 4 3 1 仿真场景设置3 5 4 3 2 仿真结果分析3 6 4 4 本章总结3 8 第五章无线链状网的路由协议研究3 9 5 1 路由协议的选择3 9 5 2o l s r 路由协议4 1 5 2 1o l s r 的基本原理4 l 5 2 2o l s r 路由协议分组格式4 3 5 3 改进的o l s r 路由协议4 4 5 3 1 信道分配最优链路状态路由( c a o l s r ) 协议4 4 5 3 2c a o l s r 算法的c p n 模型4 7 5 3 3m p r 集的最优选择5 0 5 4 路由性能评估与仿真5 4 5 4 1 性能评估指标5 4 5 4 2 仿真场景设置5 5 5 4 3 仿真结果分析5 6 5 5 本章总结5 8 第六章总结与展望5 9 6 1 论文工作总结5 9 6 2 后续工作展望6 0 参考文献6 l 附录6 6 致谢6 7 攻读硕士学位期间科研及论文完成情况。：6 8 v 硕十学位论文 第一章绪论 1 1 引言 第一章绪论弟一早三百下匕 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 是国际上当前备受关注 的、多学科高度交叉、知识高度集成的前沿热点研究领域。传感器技术、无线通 信和现代网络等技术的进步，推动了现代无线传感器网络技术的产生和发展。无 线传感器网络大大扩展了人们信息获取能力，将传输网络同客观世界的物理信息 连接在一起，将在下一代网络中为人们提供最真实、最直接、最有效的信息。无 线传感器网络能够获取客观物理信息，因此具有十分广阔的应用前景，它能应用 于军事国防、工农业控制、危险区域远程控制、环境检测、生物医疗、城市管理 以及抢险救灾等领域。已经引起了许多国家学术界和工业界的高度重视，被认为 是对2 l 世纪产生巨大影响力的技术之一。 无线传感器网络主要由部署在监测区域内大量的廉价微型传感器节点构成， 通过无线通信方式而形成的一个多跳自组织的网络系统，其目的在于协作地采集 和处理无线网络覆盖区域中感知对象的信息，并发送给观察者。传感器、感知对 象以及观察者构成了无线传感器网络中的三个要素。 1 2 本课题的研究背景及意义 1 2 1 本课题的研究背景 本课题来源于申请中的国家高技术研究发展计划( 8 6 3 计划) 课题：基于无 线传感器网络的铁路重载货运车辆危险状态监测系统研究与应用。 无线传感器网络技术【1 1 被认为是2 1 世纪最重要的技术之一，根据无线传感 器网络和铁路重载货物列车的特点，该8 6 3 计划首次提出了利用无线传感器网络 对重载货物列车危险状态进行在线监测的新方法。它的实施将使无线传感器网络 在铁路上的应用得以实现并将对无线传感器网络技术自身的发展产生深远的影 响。 无线信息传输网络是根据铁路重载货运车辆运行危险状态监控的需要，建立 无线链状网络( w c n ，w i r e l e s sc h a i nn e t w o r k ) 的体系结构。无线链状网络是 无线传感器网络中的一种特殊拓扑结构，它和无线传感器网络一样，由于应用环 境和传感器节点体积的限制，对能量的消耗有很高的要求，因此能量就成为无线 传感器网络最重要的性能指标之一1 2 】。 中南大学硕十学位论文 无线传感器网络研究中，从不同的方向考虑可有多种节省能量的方式，大体 归纳可以分为：低功耗的射频技术和硬件设计；传感器节点的自适应休眠：采用 数据聚合手段减少传输的数据量；能量有效的多跳路由算法等。本课题将采用 p e t r i 网【3 1 对无线链状网络( w c n ) 建模，并从m a c 协议和路由算法着手对无线 链状网络的节能进行研究。 1 2 2 本课题的研究目的及意义 p e t r i 网是一种基于系统图形化的语言，可对复杂系统进行很好地描述与分 析。论文主要从无线链状网络的建模和分析技术两个方面来进行系统和深入的研 究，并利用有色p e t r i 网的性质对无线链状网络通信系统进行分析，特别是无线 链状网的m a c 协议和路由协议等。在借鉴和充分研究当前无线网络通信技术的 基础上，探讨影响无线链状网络通信系统可靠性的主要因素，并针对本课题的实 际要求，研究提高无线链状网络通信系统可靠性的解决方案，指导无线链状网络 通信系统的整个生命周期的运行。 无线链状网络是该8 6 3 计划中货物列车危险状态监测系统的一个重要组成 部分，运用合适的m a c 协议和路由算法来控制链路节点之间的通信，对于减少 链路节点的能源损耗、增加网络生存周期有着重大的现实意义。 1 3 国内外研究现状与水平 1 3 1p e t r l 网技术的研究与发展 p e 廿i 网是原联邦德国c a r ta d a mp e t r i 博士于1 9 6 2 年初提出的研究信息系统 及其相互关系的数学模型【3 】，经过近4 0 年的发展，已成为具有严密数学基础， 多种抽象层次的通用网络，得到了广泛的应用。 关于p e t r i 网理论方面与应用方面的详细综述，可参考以下两篇文章：蒋昌 俊的“p e t r i 网理论与方法研究综述”1 4 j 和t m u r a t a 的“p e t r in e t s ：p r o p e r t i e s ， a n a l y s i sa n da p p l i c a t i o n s ”1 5 】。在p e t r i 网的理论研究方面，主要包括p e t r i 网状态 复杂性问题、分析技术、并发行为特性，p e t r i 网语言的拓展和p e t r i 网模型的建 立。在p e l r i 网实际应用方面，网络通信协议的分析与验证、工作流调度和并发 程序的描述与验证等领域都取得了诸多可喜的成果【1 1 。 对于网络通信协议的形式化建模与分析，h e n kj o n k e r s 等人设计了一种新的 建模和设计语言a m b ，为通信协议设计和量化分析以及性能分析提供了一种统 一的形式。d r l e f e b v r e 等人研究了如何运用p e t r i 网技术对通信协议进行控制， 2 硕十学位论文 第一章绪论 同时利用p e t r i 网的建模和分析技术分析了网络协议的性能1 6 】。 h a n p a n gh u a n g ，m u d e rj e n g f 7 1 ，z h o n g - j i ew a n g 引，m i n g h u a n gl i n 等分 别对网络通信协议运用不同的扩展p e t r i 网进行了建模分析。h a n p a n gh u a n g 等 对基础p e t r i 网进行了扩展，将分别应用于不同的模型建立和分析中。 c h u n g h s i e n k u o 用一个分布式着色时间p e t r i 网( d c t p n ) 来对网络协议进行建模 以及特性评价1 9 1 。 n e n n i n g e r 提出一种联合微分方程和p e t r i 网0 p n ) 的解释方法。在该方法中， 微分方程用来描述连续部分，i p n 用于描述离散动态部分，两者的相互作用通过 d c 和c d 来表述。s c h n i r d e s 和c h o u i k h a 共同提出了一种类似方法，用连续p e t r i 网来对系统的连续部分建模，因而不再需要c d 和d c 来连接系统中的离散部 分和连续部分。 w e i m i n gl u 根据网络协议的设计原则，给出了一种新的设计方法和技术 1 1 0 。m k a m e i 等讨论了一种使用p e t r i 网描述分布式自治网络的方案，并提出相 应的性能分析方法。s c a v a l i e r i 等分析了i e c i s a 和p r o f i b u s 协议里集中和分布 式方法的应用，并通过基于网络协议的p e t r i 网模型进行仿真来估计其特性。 c m u r r a yw o o d s i d e 应用一种迭代的方法来解决状态空间爆炸的问题，并采用 p e t r i 网来表示数据通讯协议的模型。s h a r i r i 等采用分层思想先将网络分成多层， 再逐层分析，最后将各层统一分析。c o n g z h e z h a n g 应用随机p e t r i 网对a dh o e w s n 进行建模和分析。 国内的许多项目在相关方面都用到了p e t r i 网理论，如加工制造系统、故障 诊断、协议设计与分析等。基于不同的应用对象，基础的p e t r i 网理论已经不胜 任，因此，很多研究者对p e t r i 网进行了拓展。已有很多优秀研究成果发表在软 件学报、计算机研究与发展、计算机工程等重要期刊上。 郭希民等提出了一种扩展的时间p e t r i 网一一带抑制弧的时间p e t r i 网，可以 用来很好地描述网络协议【1 1 l 。严海蓉等提出了p e t r i 网建模的一般步骤，并以 c s m c d 协议为例建立了仿真模型，然后总结了p e t r i 网建模优点，并对流程 图与p e t r i 网建模进行比较1 1 2 1 。 杨根科等定义了一类混合系统的p e t r i 网模型，该模型强调连续与离散动态 在同一层次的直接交互，最后提出基于混合p e t r i 网的混合控制器设计方法。 李忠勇等提出了广义的随机p e t r i 网建模理论，并对计算机网络建立广义随 机p e t r i 网模型，在此基础上提出了进行性能评估的相关指标和计算方法，避免 了以往建模时的盲目性【l 引。文献【1 3 】中还提出了用广义随机p e w i 网建模并进行 网络性能计算的系列方法。这些方法可有效地完成网络协议的建模和对性能指 标的计算，对设计和分析网络协议具有普遍的指导意义。 3 中南大学硕士学位论文 范训礼等用p e t r i 网进行f t p 代理服务器的设计仿真1 1 4 】。陈萃萌等提出了一 种基于p e t r i 网的模型以描述通信设备的工作原理。在此基础上给出了设计该模 型的方法，并给出了一个性能测试的实例，为网络协议的设计和性能分析提供了 一种新的方法1 1 5 1 。 姜浩等以有色p e t r i 网为基础，在经过了必要的功能扩充后，针对知识验证 的主要内容，建立了有色p e t r i 网的知识表示模型，提出了一种简洁有效的、基 于有色p e t r i 网的知识库验证方法，并给出了相应的判定准则，最后给出了一个 说明知识表示模型和知识验证判定准则的实例i l 6 。 1 3 2 无线链状网络的研究与发展 无线传感器网络出现在2 0 世纪9 0 年代末，其出现为当前很多难题的解决提 供了可能性，因此受到了各界的高度重视。美国和欧洲相继启动了多项无线传感 器网络方向的研究计划。2 0 0 4 年初，第一届“无线传感器网络论坛”在德国柏林 举行，关于无线传感器网络方向的研究正处于热点研究阶段。 i a ne a k y i d e i z ，w e i l i a ns u i 】等对无线传感器网络进行了探讨，包括已出现的 m a c 协议和路由协议，并分析和展望了一些有价值的应用领域。结合已有研究， 总结并详细阐述了包括介质访问控制方法和低功耗路由技术等在内的热点研究 问题。 i r h e e 1 8 】等在i e e e 8 0 2 1 1 的基础上提出一种新的适合无线传感器网络的混 合m a c 协议：z m a c 。该协议将t d m a 和c s m a 结合起来，既可获得c s m a 的高信道利用率，又可得到t d m a 的低延迟，从而使协议达到更好的性能。其 特点是协议的性能受同步误差、时隙分配以及信道条件的影响较小。但是，在最 坏条件下，该协议的性能不如c s m a 。 h o i s h e n g ，j e a nw a r l a n d ，j e o n g h o o nm o b 9 1 提出了一种基于多信道的m a c 协 议：m c m a c 。与单信道m a c 协议不同之处在于多信道m a c 协议中的信道冲 突大大减少。另外，该协议可同时利用多条信道进行数据传输，大大改善了无线 网络信道的利用率。 k e m a la k k a y a , m o h a m e dy o u n i s 2 0 j 对无线传感器网络的路由协议进行了深 入研究。文中将现有的路由协议进行了分类整理，将其分为数据类( d a t a - c e n t r i e ) 、 层次类( h i e r a r c h i c a l ) 、位置类( 1 0 c a t i o n - b a s e d ) - - 类。并对各类路由协议的相似之处 以及q o s 服务进行了分析。 我国对智能无线传感网络的研究几乎与发达国家同步启动。国内许多学者也 在国内外的重要期刊上发表了很多的研究成果。目前，国家自然科学基金、国家 9 7 3 计划和国家8 6 3 高技术计划等均设了专项以资助该领域的理论、方法和关键 4 硕士学位论文第一章绪论 技术研究，也取得了可喜的成果。 减小动态源路由协议d s r 的开销、提高无线信道的利用率的关键是在协议 运行时，使用m a c 地址对节点进行标识。杨仕平1 2 1 l 等研究了如何为特定i p 地 址标识的网络节点动态分配m a c 地址，实现了一种基于预测的无冲突m a c 地 址动态分配方法，实验证明该方法所引入的开销较低。 龚海刚1 2 2 j 等提出了一种自适应低延迟的节能m a c 协议一- - s e e l 协议。此 协议主要做了一下三方面的改进：自适应地调节竞争窗口的大小，从而减小节点 数据传送的碰撞几率和由于碰撞而导致的能量消耗；采用快速退避机制，减少了 节点在退避过程中的空闲监听时间；扩展r t s c t s 消息机制，减少了节点在每 帧活动阶段的时间以及减小数据的延迟，两者都能节约能量的使用。该协议为协 议节能设计提供了一种新的方法。 李红艳1 2 3 1 等对一种基于i e e e8 0 2 1 1d c f 协议多信道多址接入方案的性能 进行了分析。采用马尔科夫链构建了控制信道的预约模型，给出了多信道吞吐量 的理论分析算法。并通过仿真给出了信道吞吐量与信道数、节点密度、数据分组 长度、信道切换时延等参数之间的数值关系。 卢宇【2 4 】等针对移动a dh o c 网络通信节点共享通信介质且易受网络负荷影 响的特点，提出了一种基于m a c 层信息的o l s r 协议改进方案。方案改进了t c 消息源头节点的发送方式，采用源节点二次发送机制以降低对路由性能有重要影 响的信令信息丢失的概率，稳定路由协议的性能，减少数据在网络层的丢包。 关于无线链状网络( w c n ) 的研究，目前还处于起步阶段。虽然无线传感 器网络的研究已取得了一些研究成果，但其并不十分适用于无线链状网络结构。 无线链状网络的特殊性使得许多无线传感器网络中的通信协议和算法不适合，需 要研究新的体系结构和方法以适应于这种网络结构。 1 4 本文主要研究内容 本文的主要研究对象为实现重载货物列车运行状态的监控数据进行实时通 信的无线链状网络协议，以保证异常状态的实时处理。本文主要做了以下几项工 作： 1 分析了无线传感器网络相关领域的研究成果及应用情况，结合8 6 3 课题 确定了论文的研究内容，针对无线链状网络的结构特点和多跳中继通信的特点， 将方向定在设计新的结合路由信息的m a c 协议和相关的路由协议。 2 针对重载货物列车的结构特点提出一种特殊的网络结构一一无线链状网 ( w h l e s sc h a i nn e t w o r k ，w c n ) ，在当前无线传感器网络通信协议i e e e 8 0 2 1 l 的基础上提出一种结合路由的多信道m a c 协议，并对o l s r 路由协议进行了改 中南大学硕士学位论文 进以更加适用无线链状网络结构。 3 使用c p n t o o l s 工具，采用p e t r i 网理论对提出的多信道m a c 协议建模， 论证该模型的正确性。 4 利用n s 2 分别对多信道m a c 协议和改进的o l s r 路由协议进行性能仿 真分析，并与标准m a c 协议i e e e 8 0 2 1 1 和o l s r 协议的性能分析比较。 5 对多信道m a c 协议和改进的o l s r 路由协议存在不足和进一步改善的方 向进行了分析讨论。 1 5 本文的整体结构及章节安排 根据以上的研究内容，将全文的篇章安排如下： 第一章绪论，主要介绍无线传感器网络的背景，并对p e t r i 网和无线链状 网络的发展和现状做了相关介绍，同时也对本文的主要研究方向一一无线链状网 的m a c 协议和路由算法给出简单提示，安排了全文的结构。 第二章对无线链状网络的相关技术进行综述，内容包括无线链状网络的概 况、m a c 协议以及路由算法等。主要为本文后续章节所研究的问题提供详细的 研究背景。 第三章该部分主要介绍p e t r i 网的基本定义和一些性质，并给出p e t r i 网 的分析方法以及其存在的一些基本问题，从而扩展随机p e t r i 网得到混合随机 p e t 对网，以便用来对无线链状网的多信道m a c 协议进行建模和分析。 第四章主要内容为多信道m a c 协议的研究，包括p e t r i 网综述，无线链状 网的多信道m a c 协议描述以及该协议的p e t r i 模型和性能分析。 第五章主要为o l s r 路由协议的研究，包括o l s r 的基本原理，分组格式， 对o l s r 协议的改进等。并对改进的o l s r 协议进行了建模和仿真分析。 第六章总结与展望，总结整个论文的内容，分析比较得出的结果，最后对该 方向以后的研究与需改进的方向做了简单的展望。 6 硕十学位论文第二章无线链状网的m a c 及路由分析 第二章无线链状网的m a c 及路由分析 本章主要对无线链状网络的相关技术进行介绍和分析，内容包括无线链状网 络的概况、目前无线网络的m a c 协议以及路由算法等。第一部分是对无线链状 网络的概述，包括其结构特点，网络特征等；第二部分阐述无线链状网络的m a c 协议，内容包括传统m a c 协议在该网络中存在的问题，无线链状网m a c 协议 的设计要求；第三部分讲述无线链状网的路由技术，内容包括传统路由协议在该 网络中存在的问题，无线链状网路由协议的设计要求。通过本章的综述，为后文 的研究系统详细的背景。 2 1 无线链状网概述 2 1 1 无线链状网的特点 无线链状网( w i r e l e s sc h a i nn e t w o r k ，w c n ) 是一种利用无线传感器对重 载货物列车危险状态进行在线监测的新网络。一般情况下，单节车厢的长度在 1 0 1 2 米之间，载重为1 0 0 吨，万吨级重载货物列车车长在1 0 0 0 1 2 0 0 米。考虑 到每节车厢上安装一个通信节点，并在机车头上安装主控制节点，其结构示意图 可用图2 1 表示： 毯卜一 图2 - 1 无线链状网络结构示意图 用于铁路重载货车车辆运行危险状态检测的无线链状网( w e n ) 是无线自 组网中的重要组成部分，因此它具有无线自组网的一般特性i z 纠： ( 1 ) 多跳组网：由于节点发送功率的限制，节点的发射范围一般不大，当 两个距离较远的节点进行通信时，需要网络中其它节点进行转发，此时就会形成 一条多跳路径。多跳是无线自组网的基础。 ( 2 ) 动态拓扑：在无线自组网中，由于节点位置的随机移动、节点的自主 开机或关机、无线发射功率的变化、环境的影响等因素，使得节点间经由无线链 7 中南大学硕士学位论文 路形成的网络拓扑结构随时可能发生变化，且变化速度和方式难以预测。 ( 3 ) 链路带宽有限：无线自组网中数据采用无线信道进行传输。与有线信 道相比，无线信道的带宽要低得多，同时无线信道容易受到环境的干扰，导致能 提供的带宽比理论值更低，且不稳定。 ( 4 ) 节点的局限：网络中节点采用能量有限的电池供电，硬件的内存又比 较小、c p u 计算能力较弱。因此，设计m a c 协议时需要从各个层面来考虑怎样 降低节点功耗，延长节点寿命和无线网络的生命期。同时，因节点硬件局限性， 网络协议必须简洁实用。 ( 5 ) 安全性差：由于采用无线通信信道，且网络拓扑动态变化，加上网络 中节点的局限性，无线自组网的安全面临极大的威胁。无线信道容易受到窃听、 消息破坏等攻击；网络的动态拓扑使得传统网络中的加密和认证等安全方案无法 适应这种需求。 作为无线自组网的一种特殊结构，无线链状网除具有无线传感器网络的一般 特性外，还有以下特点： ( 1 ) 拓扑结构相对稳定，如图2 1 所示。在货物列车行驶过程中，该拓扑结 构会有少许变化，我们可以从图5 1 5 中看到笔直行驶时、在弯道行驶时、进入 隧道时的拓扑示意图。该拓扑结构由无线链状网的应用对象重载货物列车决定， 无论发生多少次解编组，列车始终保持链状状态。 ( 2 ) 节点变化不多。重载货物列车大部分时间运行在铁轨上，此时列车上 各节点保持不变，只有在货物列车进站后的解编组才会使节点发生变化；另外， 节点发送故障时，如缺少能量供应、传感器损环等也可造成节点的变化。 ( 3 ) 节点等距分布( 1 2 5 米) ，传输路径上的节点数在3 0 2 0 0 之间，部分 数据包经过的节点很多，这样将会造成数据包传输延迟大，从而影响铁路货车安 全监测所需数据的准确性和及时性。 ( 4 ) 节点采用自供电技术和节能控制两种方法控制能量消耗，因此节点运 行功耗不是首要考虑问题。 基于以上特点，无线链状网络m a c 协议和路由算法的设计充满了挑战，在 下面几节中将对此详细描述。 2 1 2 无线链状网的技术挑战 m a c 及路由分析 控制层。当前的i e e e 8 0 2 1 1 协议中，多节点共享一个信道，有时会造成信道使 用的不公平性，如b e b 算法会使有些节点长期占有信道，其他节点很难获得信 道资源。 因此，该信道接入控制协议要求在解决多节点公平接入共享信道的基础上尽 量地提高信道利用率【2 6 1 。而无线链状网的多跳共享信道、拓扑动态变化等特点使 得上述目标难以实现。如何设计高效、公平的m a c 协议成为m a c 层研究的重 点。 ( 2 ) 路由 路由是网络层的主要功能。路由协议主要作用是建立源节点和目的节点之间 的可达路径。无线网络拓扑的动态变化给路由协议的设计带来了巨大的困难和挑 战【l 引。传统的链路状态路由和距离矢量协议明显无法直接用于网络拓扑动态变化 的无线链状网，其在路由收敛性、环路路由、无线带宽资源和节点电池能量等方 面存在着严重问题和缺陷。针对无线链状网特点，路由协议的主要设计要求包括： 适应网络动态拓扑、尽可能小的路由控制开销、路由算法运算简单、扩展性强等。 ( 3 ) 可靠传输 鼍 在传统因特网中，数据的可靠传输是由t c p 协议提供的，t c p 协议是一种 面向连接的传输层协议，该协议最初针对有线网络设计，通过三次握手建立可靠 连接，提供数据传输。无线网络中的高误码率、信道的不可靠等使得可靠传输困 难重重，如果不加改进地将t c p 协议应用到无线网络中，将导致严重的问题。 ( 4 ) 节能 ， 簪 无线链状网的节点采用电池供电。降低节点功耗，对延长节点使用寿命，增 加网络生命周期有重大意思。节点节能牵涉到多个层面，m a c 层可采用增加休 眠时间、加少信道冲突等方法。网络层可采用数据融合、用功耗优化路由等方法。 通过w c n 中各层的合作达到节能的目的。 ( 5 ) 安全 安全主要由应用层协议保证。传统网络的应用层中提供了多种方式以保证安 全性：如加密，密钥体制，访问控制等。在无线网络中，数据通过无线广播传输， 该特性使得其极容易受到窃听和入侵。节点的计算能力不足使得加密，密钥体制 等无法应用在无线网络中。基于此上，无线链状网络的安全性受到严重挑战。 本小节从m a c 层、网络层、应用层角度分别讨论了信道接入控制问题、路 由问题、安全问题等，这些问题不能简单划分在某一层解决，涉及协议栈的多个 层，需要多层协作解决。m a c 问题和路由问题是无线链状网技术最具特色的两 个核心问题，本章后续小节将对m a c 技术和路由技术分别进行详细分析，为后 面无线链状网m a c 协议和路由算法的研究做准备。 9 中南人学硕士学位论文 2 2 无线链状网的m a c 协议 2 2 1 传统m a c 协议问题 f 、口弦铲? i ? tg l ， l ，7， 、义邀 。 、一 k 二二 二一7 ，_ 巧瑟 o 、 ， ，、 f、叶： l 扣。1 1 ) i 、艾逡 。 、一乏之二 图2 - 3 暴露终端问题 l o 硕十学位论文第二章无线链状网的m a c 及路由分析 暴露终端【2 玎因得知发送节点的发送而延时发送，但因它在接收节点的范围之 外，实际上它的发送不会造成接收节点处的报文冲突，因而引入了不必要的延迟。 3 ) q o s 服务 在无线链状网络中，提供q o s 保障的通信传输比较困难。基于其多跳、动态 拓扑等特点，其q o s 实现起来较其他网络更为复杂。 4 ) 广播消息 传统的无线网络多是依靠广播信号来实现网络的操作。由于节点的移动性、 无线信道的不可预知性，一个节点可能失去网络链接，因而需时时更新路由信息。 设计多信道m a c 协议时，需考虑必要广播消息的准确、及时传送。对于一个节 点来说，采用切换方式，有可能遗漏某些广播消息。因此，在设计多信道m a c 协议的过程中，有效保证广播信息的接收十分重要。 2 2 2m a c 协议要求 m a c 协议设计的基本要求包括以下两方面1 2 列：1 、公平性，尽量保证节点 公平占用公共信道；2 、信道利用率高，充分利用有限的信道带宽资源。即要求 m a c 协议在解决多个节点公平接入公共信道的基础上，尽量提高信道的利用率。 对于基本要求中的第一点，主要涉及到信道公平接入方面的研究。在 i e e e 8 0 2 11 m a c 协议中，通常采用退避算法和发送概率两种方法来实现节点的 随机接入。在b e b 算法中，退避时间越小或发送概率越大，节点抢占信道的能 力越强。从而导致某些节点长期占用信道，使其他节点无法占到信道，引发节点 信道接入的公平性问题。因此有必要研究新的、公平的信道接入和信道分配算法。 在蜂窝无线通信系统中，通常由基站来解决信道接入的公平调度【2 酊。而无线 链状网中不存在类似的网络控制中心节点，从而不能直接套用蜂窝无线通信系统 里的中心仲裁方法，只能采取分布式方法来解决信道接入公平性问题。本文将在 第四章对如何公平接入信道进行详细研究( 采用新的信道分配算法) 。 对于基本要求中的第二点，以往的单信道m a c 协议中，由于单信道带宽本 身的限制，无论怎样提到信道利用率，带宽最多达到单信道的理论值上限。本文 中采用多信道m a c 协议，大大提高了信道可用带宽。在文中第四章将对如何提 高信道带宽进行详