（计算机科学与技术专业论文）基于网络编码的wsn可靠传输机制研究.pdf

s p e c i a l t y ：c o m p u t e rs c i e n c ea n dt e c h n o l o g y _ m a s t e r d e g r e ec a n d i d a t e ：c a ih o n g s u p e r v i s o r ：p r o f w e i p i n gw a n g c o l l e g eo f i n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a h u n a np r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：垒丝 e lg q ： 亟丝年月土日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：垒! 兰 导师签名型拯日期：2 坐年上月生日 摘要 无线传感器网络具有功耗低、成本低、分布式和自组织等特点， 往往被部署在各种恶劣环境中，改善了人们获取信息的能力。能量高 效的可靠传输机制对于延长能量有限的传感器网络的生命周期、保障 传输质量是非常必要的。传感器网络可靠传输问题的传统解决方法主 要包括重传和冗余。无线网络编码允许通过侦听收到包的各个节点对 数据包进行处理、转发，有效地提高了传输可靠性，但也带来了过多 的冗余编码包传输问题。研究以最小的编码冗余来获得最大的传输可 靠性对于网络编码在无线传感器网络中的广泛应用具有重要的理论 意义和应用价值。 本文首先对无线传感器网络的可靠传输问题的研究现状进行了 总结和分类，介绍了目前几种主要的基于重传和路径冗余、编码冗余 的传输机制，并分析了各自的优缺点。 为了保证传输可靠性，减少冗余编码包的数量，本文提出了一种 新的基于控制消息的网络编码传输机制。在源节点及其近邻居转发节 点采用随机线性网络编码发送编码数据包，在其它中间节点传输时， 发送节点选择两个可靠性最高的下一跳接收节点，使得当一个节点接 收失败时，可以触发备用节点来转发，提高发送节点的传输可靠性。 模拟结果表明在达到相当可靠性的情况下，该方法与r m r n c 方法相 比，能有效地减少传输一组包所需要的发送次数。 针对传感器网络中的节点分布式强的特点，本文还提出了一种冗 余编码传输机制。每个节点对于收到的编码包，根据一定的可靠度独 立地确定自己需要发送的编码包个数以及每个邻居节点需要承担的 转发包个数，动态地调整每个节点需要发送的编码包数。模拟结果表 明在链路错误率较大时该方案比基于a c k 重传的方法相比，减少了 传输一组包所需要的发送次数。 最后，对本文所做的工作进行了总结，指出了将来的研究方向。 关键字传感器网络，可靠传输，网络编码 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k sa l w a y sh a v el i m i t e de n e r g y , a n dt h e ya r e l o wc o s t ，d i s t r i b u t e da n ds e l f - o r g a n i z e d t h e ya r ea l w a y sl o c a t e di nv e r y s p e c i a le n v i r o n m e n ta n di m p r o v ep e o p l e sa b i l i t yt oo b t a i ni n f o r m a t i o n e n e r g ye f f i c i e n tt r a n s m i t t i n gm e c h a n i s mi sv e r yi m p o r t a n tf o rw i r e l e s s s e n s o rn e t w o r k s m a n yr e s e a r c h e sh a v eb e e nd e v e l o p e da b o u tr e l i a b l e t r a n s m i t t i n g ；t h e ym a i n l y f o c u so n r e t r a n s m i t t i n g a n dr e d u n d a n t t r a n s m i t t i n g w i t ht h ed e v e l o p m e n to fn e t w o r kc o d i n g ，t h en o d e sc a nn o t o n l yf o r w a r dt h ep a c k e t sb u ta l s op r o c e s st h e mw i t hn e t w o r kc o d i n g ，s oi t i m p r o v et h er e l i a b i l i t y , b u ti ta l s ob r i n g st h ep r o b l e mo fh o w t od e c i d et h e n u m b e ro fr e d u n d a n tp a c k e t s 1 1 1 i st h e s i ss u r v e y st h er e s e a r c hs t a t u so fr e l i a b l et r a n s m i t t i n gi n w i r e l e s ss e n s o rn e t w o r k s ，a n dt h e na l s o g i v e s t h ed e t a i lo fm a i n r e t r a n s m i t t i n ga n dr e d u n d a n tm e c h a n i s m i no r d e rt o i m p r o v et h er e l i a b i l i t y o ft r a n s m i t t i n g ，t h i st h e s i s p r o p o s e sar e l i a b l et r a n s m i t t i n gm e c h a n i s mb a s e do n c o n t r o lm e s s a g e ，t h e s e n d e rs e l e c t st w op o i n t sw h o s er e l i a b i l i t yi st h eh i g h e s ti ni t sn e i g h b o r s ， w h e ni tc a n n o tr e c e i v et h ea c kf r o mo n en o d e ，i tc a na s ka n o t h e rn o d et o s e n da st h eo t h e rn o d eh a sr e c e i v et h ep a c k e tw i t hal a r g ep r o b a b i l i t y i n s u c haw a y , t h es e n d e rc a nr e d u c ei t sn u m b e ro fr e t r a n s m i s s i o n t h e s i m u l a t i o nr e s u l t ss h o wt h i sm e c h a n i s mc a nr e d u c et h en u m b e ro f t r a n s m i s s i o nc o m p a r i n gw i t hr m r n c i no r d e rt oa d j u s tt ot h ed i s t r i b u t i o no fs e n s o rn e t w o r k s ，t h i st h e s i s t h e np r o p o s e san e t w o r kc o d i n gt r a n s m i t t i n gm e c h a n i s mc o n s i d e r i n g r e d u n d a n tp a c k e t sc o n t r o l l i n g e v e r yn o d ec a l c u l a t e st h en u m b e ro f p a c k e t si ts h o u l ds e n dt od e c i d et h en u m b e ro fr e d u n d a n tp a c k e t s t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h en u m b e ro ft r a n s m i s s i o ni tn e e d se v e nl e s s t h e nt h em e c h a n i s mo fr e t r a n s m i t t i n gb a s e do na c kw h e nt h ec h a n n e l e r r o rr a t ei sh i 曲 k e yw o r d sw i r e l e s ss e n o rn e t w o r k s ，r e l i a b l et r a n s m i t t i n g ，n e t w o r k c o d i n g i l 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 传感器网络概述1 1 1 1无线传感器网络体系结构l 1 1 2 传感器网络的特点以及应用环境3 1 2无线传感器网络可靠传输5 1 2 1 a r q 自动重传。5 1 2 2冗余传输6 1 3 主要研究目标与研究内容7 1 4章节安排8 第二章网络编码及其应用概述9 2 1网络编码。9 2 1 1网络编码的提出9 2 1 2网络编码的基本概念9 2 1 3网络编码的发展现状1 0 2 2网络编码实现方法11 2 2 1线性网络编码1 l 2 2 2随机线性网络编码。1 2 2 3网络编码的特点1 3 2 4网络编码应用1 4 2 4 1有线网络中的应用1 5 2 4 2 无线网络中的应用15 2 5 本章小结1 9 第三章基于网络编码和控制消息的w s n 可靠传输机制2 0 3 1相关研究2 0 3 1 1r e l n f o r i l l 机制一2 0 3 1 2 基于网络编码的多路径传输机制2 2 3 1 3 两种机制的性能比较2 4 3 2 基于控制消息触发传输的策略2 5 3 2 1t s c m 的基本思想。2 6 3 2 2 发送代价分析2 7 i i i 3 3基于控制消息和网络编码的多路径可靠传输2 9 3 - 3 1m p t c n 基本思想2 9 3 3 2邻居发现阶段3 0 3 3 3数据包传输阶段3l 3 3 4数据包解码阶段3 4 3 4模拟与分析3 4 3 5本章小结3 7 第四章一种基于网络编码的冗余传输策略研究3 8 4 1 随机线性网络编码冗余传输3 8 4 2 一种基于网络编码的冗余传输策略4 1 4 2 1 邻居发现阶段4 1 4 2 2 编码包传输阶段4 2 4 3 模拟与分析4 5 4 3 1模拟环境4 5 4 3 2 模拟结果分析4 5 4 4本章小结4 7 第五章结束语4 8 5 1工作总结4 8 5 2进一步的研究工作4 9 参考文献一5 0 致 射5 5 攻读硕士期间主要的研究成果5 6 w 第一章绪论 随着科学技术地发展，计算机网络已经渗透到人类社会生活的各个领域。随 着无线通信技术、微电子技术和分布式信息处理技术的发展，无线传感器网络也 得到了飞速发展。目前，传感器网络已经被广泛应用于军事战场获取与监控敌方 信息、监测与预报环境状况、检测健康、智能家居、监控建筑物状态、监控复杂 机械运行状况、监控城市的交通，对空间探索以及大型车间，以及机场、大型工 业园区的安全进行监测。 1 1 传感器网络概述 无线传感器网络i l 刮是( w i r e l e s ss e n s o r n e t w o r k s ，w s n ) 由部署在检测区 域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组 织的网络系统。它的目的是协作地感知、采集和处理网络覆盖区域中感知对象的 信息，并发送给观察者。传感器网络是集成了检测、控制以及无线通信的网络系 统。网络中，节点的数目庞大( 成千甚至上万) 、分布非常密集；节点的能量、 处理能力和存储能力都非常有限。而很多传感器网络应用比如军事战争环境、高 速铁路桥的监控和生化检测等都对数据传输可靠性提出了要求。 1 1 1无线传感器网络体系结构 无线传感器网络主要有传感器节点、感知对象和观察者三个部分组成。观察 者通过传感器网络可以主动地查询传感器网络搜集到的感知信息，或者被动地获 得传感器网络发布的信息，然后对获取的信息进行分析、挖掘，从而制定决策作 出相应的行动。 ( 1 ) 传感器网络体系结构 传感器节点往往被大规模地随机撒播在监测区域，它们自动组织成网。一个 典型的无线传感器网络的体系结构如图1 - 1 所示。我们将传感器中的节点分成3 类：普通节点，汇聚节点和任务管理节点。传感器普通节点将监测到的数据通过 其它节点逐跳传输，中间节点可以对数据进行处理，也可以不处理直接转发。经 过多跳转发以后，数据被传输到汇聚节点。管理节点能够对传感网进行配置管理。 一般来说，汇聚节点和任务管理节点无需感应数据。汇聚节点的处理能力、存储 能力和通信能力都较强，它比普通节点拥有更多的内存和计算资源，而且拥有足 够的能量供应。普通节点一般使用电池供电，常因电池能量耗尽而被网络抛弃。 但是汇聚节点和任务管理节点与因特网或管理节点通信，将所有数据发送出去， 一般采用电源供电以保证它们能够持续工作。 图1 - 1 传感器网络体系结构 ( 2 ) 传感器网络协议栈 网络协议结构是网络协议分层以及网络协议的集合，是对网络及其部件所应 完成功能的定义和描述。虽然无线传感器网络与传统网络相比有很多不同的地 方，但它们的网络协议栈都可以划分成t c p i p 五层模型，如图1 2 所示。 图1 2 传感器网络节点网络协议栈结构 其中，物理层遵照i e e e 8 0 2 1 5 4 1 4 1 标准提供简单但健壮的信号调制和无线收 发技术；数据链路层又分成两个子层：逻辑链接控制层( l l c ) 和介质访问控制层 ( m a c ) ，主要负责数据成帧、帧检测、媒介访问控制和差错控制；路由生成与路 由选择主要是在网络层完成；数据流的传输控制，是保证通信服务质量的重要部 分，有传输层来提供；基于检测任务的应用层软件部署在应用层；在各个协议层 都需要考虑节省能量，能量管理模块负责管理节点能量的使用情况；移动管理平 台检测、注册传感器节点的移动，维护到汇聚节点的路由，使得传感器节点能够 动态跟踪其邻居的位置；任务管理平台在一个给定的区域内平衡和调度监测任 务。 2 1 1 2传感器网络的特点以及应用环境 ( 1 ) 传感器网络的特点 由于传感器网络特殊的应用环境使得它具有以下特点： ( a ) 以数据为中心。传感器网络是任务型的网络。网络中的节点采用节点 编号标识，节点编号是否需要全网唯一取决于网络通信协议的设计。用户在使用 传感器网络查询事件时，直接将所关心的事件通告给网络，而不是通告给某个确 定编号的节点。这种以数据本身作为查询或传输线索的思想更接近于自然语言交 流的习惯，所以传感器网络是一个以数据为中心的网络。 ( b ) 大规模。传感器节点往往由飞机随机撒播在很大的地理区域范围内， 部署的位置往往是随机的，具有不确定性；另外，节点被部署得很密集。大规模 的部署传感器网络能带来以下好处：通过分布式处理大量的采集信息能够提高监 测的精确度，降低对单个节点传感器的精度要求；大量冗余节点的存在，使得系 统具有很强的容错性能；大量节点能够增大覆盖的监测区域，减少监测盲区。 ( c ) 动态自组织性。通常情况下传感器节点被放置在没有基础结构的地方， 节点的位置不能预先精确设定。这就要求节点具有强大的自组织能力，能自动进 行配置和管理，通过拓扑控制机制和网络协议自动形成转发监测数据的多跳无线 网络系统。而且部分传感器节点由于能量耗尽或者由于环境因素造成失效，或者 传感器网络、感知对象和观察者这三要素都可能具有移动性，导致网络的拓扑结 构也随之动态变化。因此，传感器网络的自组织性要能够适应这种网络拓扑的动 态变化。 ( d ) 可靠性。传感器网络特别适合部署在恶劣环境或人类不宜到达的区域， 传感器节点可能工作在露天环境中，遭受太阳的暴晒或风吹雨淋，甚至破坏；无 线广播的特性使得传输的数据包容易受到无线链路之间的相互干扰产生错误；在 传感器网络中往往是相距多跳的两个节点传输数据，随着跳数的增加，低质量的 链路直接给网络传输的可靠性带来了很大的影响。考虑到这些因素，传感器网络 的软硬件都被设计得具有鲁棒性和容错性。 ( 2 ) 传感器网络应用环境 传感器网络的应用前景非常广阔，能够广泛应用于军事、环境监测和预报、 健康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、 大型车间和仓储管理，以及机场、大型工业园区的安全监测等领域。随着传感器 网络的深入研究和广泛应用，传感器网络将逐渐深入到人类生活的各个领域。 ( a ) 军事应用。 传感器网络具有可快速部署、自组织、隐蔽性强和高容错性的特点，因此非 3 常适合在军事上应用。利用传感器网络能够实现对敌军兵力和装备监控、战场的 实时监视、目标的定位、战场评估、核攻击和生物化学攻击的监测和搜索等功能。 传感器网络已经成为军事系统必不可少的一部分，受到军事发达国家普遍重视。 ( b ) 环境观测和预报系统。 随着人们对于环境的日益关注，环境科学所涉及的范围越来越广泛。传感器 网络在环境研究方面可用于监视农作物灌溉情况、土壤空气情况、牲畜和家禽的 环境状况和大面积的地表监测等，可用于行星探测、气象和地理研究、洪水监测 等，还可以通过跟踪鸟类等小型动物和昆虫进行种群复杂度的研究等。基于传感 器网络的a l e r t 系统中就有数种传感器用来监测降雨量、河水水位和土壤水分， 并依此预测爆发山洪的可能性。美国加州大学伯克利分校i n t e l 实验室和大西洋 学院联合在大鸭岛上部署了一个多层次的传感器网络系统，用来监测岛上海燕的 生活习性。 ( c ) 医疗护理。 传感器网络在医疗系统和健康护理方面的应用包括监测人体的各种生理数 据，跟踪和监控医院内医生和患者的行动，医院的药物管理等。如果在住院病人 身上安装特殊用途的传感器节点，如心率和血压监测设备，医生利用传感器网络 就可以随时了解被监护病人的病情，发现异常能够迅速抢救。传感器网络还可以 被用来长时间地收集人体的生理数据，这些数据对了解人体活动机理和研制新药 品都是非常有用的。 ( d ) 智能家居。 在家电和家具中嵌入传感器节点，通过无线网络与i n t e r a c t 连接在一起，将 会为人们提供更加舒适、方便和更具人性化的智能家居环境。利用远程监控系统， 可以完成对家电的远程遥控。 ( e ) 建筑物状态监控。 建筑物状态监控是利用传感器网络来监控建筑物的安全状态。美国加州大学 伯克利分校的环境工程和计算机科学家们采用传感器网络，让大楼、桥梁和其它 建筑物能够自我感知、检测它们本身的状况，将它们的状态信息自动地告诉管理 部门，并能自动按照优先级来进行一系列自我修复工作。 ( f ) 其它方面的应用。 采用无线传感器网络可以降低复杂机械维护的人工开销。随着无线技术的发 展，人们采用无线传输技术代替昂贵的线缆连接，采用传感器节点实现数据的采 集和分析。 我们看到传感器网络已经得到飞速发展，它也将会得到更加广泛的应用，巨 大地影响着人们的生产，极大地推动社会生产的发展与进步。 4 1 2 无线传感器网络可靠传输 很多的无线传感器网络的可靠性对于观察者来说非常重要，比如高速铁路桥 的监控、军事战争环境、生化检测等。影响无线链路的传输质量的因素( 物理链 路错误、休眠机制、信道冲突) 很多：它们常常部署在环境恶劣的地方，链路质 量低可能造成丢包；无线广播的特性使得传输的数据包容易受到无线链路之间的 相互干扰产生错误；在传感器网络中往往是相距多跳的两个节点传输数据，随着 跳数的增加，低质量的链路直接给网络传输的可靠性带来了很大的影响。拥有足 够的能量和时间是能够保障一定的可靠性的。但是普通节点的能量是由电池供 电，所以传感器网络更加需要的是能量高效的一种可靠传输机制。 为了解决无线传感器网络的能量高效的可靠传输问题，国内外已经做出了部 分相关研究。主要的方法是重传丢失包和传输冗余数据包。 1 2 1 a r q 自动重传 基于应答确认的重传主要有逐跳重传和端到端重传。 ( 1 ) 逐跳重传 逐跳重传主要用于m a c 层，当节点收到下一跳节点对缓冲区域中消息的确 认后，才会释放缓冲区域的数据，否则将会自动重传数据。当链路质量高、丢包 率较低、网络延时低并且能量充足时，逐跳重传是提高网络可靠性的一个有效途 径。但是，考虑到传感器网络能量有限、带宽低、链路可靠性不高等特点，单纯 的逐跳重传并非解决传输可靠性的最优途径，因为这种方式要求接收节点对收到 的每一个包作出应答，应答消息的频繁发送不仅占用了带宽而且在网络丢包率大 时，它的丢失将导致频繁重传。在链路错误率较高时，数据包丢失频繁也导致了 频繁的重传。 ( 2 ) 端到端重传 在端到端重传机制中，由目的节点检测错误和丢包并请求重传，主要是在传 输层来实现。该机制的有效性依赖于每条链路的质量，整条路径的可靠性p 与每 条链路错误率e 、路径长度h 的关系是一1 p ) h 。其次，应用端到端的a c k 将导 致吞吐率更低，传输延迟更大，因此将t c p 协议简单移植到传感器网络显然是 不适应的，为此有部分研究对传统的t c p 协议进行了改进使其适用于无线网络， 比如d t s n t 5 1 、e s r t n 、r m s t t 7 】等。文献 8 】指出，当在无线传感器网络中应用 端到端重传时，当信道错误率达到1 0 以上时，端到端的可靠性将急剧恶化。 1 2 2冗余传输 冗余传输是指，发送节点在发送一份数据的同时发送多份副本，接收节点只 要收到它发出的所有数据中的任意一份即可。根据冗余传输实现方法的不同，我 们可以将冗余传输的方法大致分为以下两类： ( 1 ) 多路径传输 多路径传输是指在信息的源节点和目的节点之间同时建立多条传输路径，源 节点将要发送的数据包同时放在多条路径之间传输，目的节点只要收到这多条路 径中传来的任意一个数据包就可以了。因此，在网络层，已有部分的路由协议致 力于这方面的研究，基于不相交多路径的路由机, t j g j 、r e i i l f o m 【1 0 1 路由、s p e e d p l l 协议，以及缠绕多路径 9 1 等机制。在源节点与目的节点建立多条路径进行信息传 输，不但可以有效地提高信息传输的可靠性，而且可以平衡网络负载，节省节点 能量的消耗从而延长网络的生存周期。在多数情况下，采用多路径传输冗余信息 不仅提高了接收端成功接收信息的概率即期望可靠性【9 】也提高了信息传输的速 率。 文献【9 】提出了一种传感器网络中寻找不相交路径的算法。不相交多路径是 指从源到目的节点之间的任意两条路径都没有相交的节点。不相交路径建立的过 程如下：首先，源节点进行洪泛以寻找到汇聚节点的路径，汇聚节点收到请求后 通过主路径增强消息建立从自己到源节点主路径；然后发送次优路径增强消息给 次优节点( 不在已经被选过的路径上) ，次优节点再选择自己的最优节点，继续 传递次优路径增强信息，直到构造一条从汇聚节点到源节点的次优路径。按照同 样的方式，可继续构造下一条次优路径。 通过上述方法能找到一组不相交的路径，但是路径与路径之间的长度可能相 差会很大，因此缠绕路径的概念被提出。缠绕多路径由一组缠绕路径组成。条 缠绕路径对应于主路径上的一个节点，当网络不包括该节点时，形成从源节点到 汇聚节点的优化备用路径。局部缠绕多路径的生成算法如下：汇聚节点分别发送 最优路径增强消息和次优路径增强给它的最优邻居节点和次优邻居节点。最优邻 居节点继续传递最优路径增强消息给它的最优邻居。当次优邻居节点收到一个备 用路径增强消息后，继续将此消息转发给它的最优邻居，直到与主路径相交形成 一条新的备用路径。 b u d h a d i t y ad e b 等人提出了一种r e l n f o r m 路由协议，假设每个节点知道自己 至l j s i n k 节点的跳数以及所有邻居至u s i n k 节点的跳数。数据源节点根据可靠性要求 计算所需的路径数；然后在邻居节点中选择一定数目的节点作为下一跳转发节 点，并且分配一定数目的路径给它们；邻居节点接收到数据源节点的数据后，将 6 自己看成是源节点，重复以上路由过程。只要多个邻居节点中的任意一个接收到 数据，就会传输成功。这种方法动态选择多个节点转发，能有效的保障可靠性但 是，能量的消耗也是比较大的。 为了解决水下传感器网络错误率高、数据传输率低以及具有移动性等问题， 文献 1 2 】提出了v b f 路由协议。v b f 协议中，每个数据包带有发送节点、目标节 点以及上一跳上跳转发节点的位置。节点收到数据包后，通过接收到信号的角度 以及到转发者的距离计算它到转发者的位置。如果节点判定它很接近路由向量， 则将自己计算得到的位置放到包里并继续转发包，否则丢弃。如此，从源到汇聚 节点形成了一个路由管道，管道内的节点都有可能成为转发节点，而管道外的节 点则不转发。 相比较于单路径路由，多路径路由能够有效地利用带宽，均衡负载，处理拥 塞和突发流量。但是除了具有这些优势，它也不可避免地面临着一些挑战：建立 和维护路径需要耗费不少的能量；在多条路径上传输同样的信息，浪费了带宽； 由于采用的是并行方式传输数据，各条路径的长度、节点的处理能力以及带宽的 差异将使得数据传输的延时差别较大，导致在目的端接收出现乱序现象；网络拓 扑变化和链路差错引起的数据丢失使得重传需要付出很大的代价。 ( 2 ) 纠错冗余 f e c 1 3 1 6 】编码、f o u n t a i n b l i s 】编码通过将要发送的数据包编码，有控制地加 入冗余信息，接收节点利用冗余信息可以进行检错和纠错。由于f e c 编码带有比 较大的编码与解码复杂度，因此文献【1 9 通过改进r e d s o l o m n l 2 0 】编码方案，降低 编码和解码复杂度，证明在链路丢包率为1 0 以下时，能有效地提高链路的可靠 性。文献【2 1 研究了一种低复杂度、解码速度快的l d p c 编码方法，并且给出了 对每个编码块最佳大小的估算。多路径f e c 编码传输利用多条路径传输从源节点 到目的节点的数据包，只要任意一定条数的路径收到同组包，就能获得原始数据 包，这种方法也能一定程度的克服节点失效和链路失效的错误情况。 各种关于冗余编码的方法通过减小编码复杂度，使其适用于能力有限的传感 器网络，在链路错误率较低时能够有效地提高传输可靠性。 1 3 主要研究目标与研究内容 很多的无线传感器网络的可靠性对于观察者来说非常重要，比如高速铁路桥 的监控、军事战争环境、生化检测等。影响无线链路的传输质量的因素( 物理链 路错误、休眠机制、信道冲突) 很多：它们常常部署在环境恶劣的地方，链路质 量低可能造成丢包；无线广播的特性使得传输的数据包容易受到无线链路之间的 相互干扰产生错误；在传感器网络中往往是相距多跳的两个节点传输数据，随着 7 跳数的增加，低质量的链路直接给网络传输的可靠性带来了很大的影响。拥有足 够的能量和时间是能够保障一定的可靠性的。但是普通节点的能量是由电池供 电，所以传感器网络更加需要的是能量高效的一种可靠传输机制。由于传感器网 络中，大部分的能量被消耗在通信中，计算所耗的能量与之相比几乎可以忽略不 计，因此系统中节点的数据包平均发送次数能够一定程度的反应系统的能量消 耗。 我们将已有的可靠传输机制分为三大类：一类采用基于a c k 重传的策略， 接收节点收到包后向发送节点应答，如果发送节点一定的时间内不能收到发送节 点的应答则自动重传整个数据包；第二类采用冗余的方法，即发送节点通过多条 路径或者多次传输发送冗余的信息包，使得接收节点只要收到这些信息中的任意 一个副本就可以。第三类采用网络编码【2 2 2 4 l 的方法，即发送节点通过将原始信息 编码成多个编码包，在接收节点只要收到一定数目编码包就可恢复出原始信息。 本文深入研究了目前基于网络编码的多路径可靠传输机制，分析机制中相关 参数( 源、s i n k 节点之间跳数和链路错误率) 对系统的平均发送次数的影响；分 析了该机制存在的缺点，并通过在传输过程中引入基于控制消息触发次优节点进 行传输的策略以及在源节点的近邻居中进一步进行网络编码的方法对该机制进 行了改进。 针对收到多个编码包的节点如何进行冗余编码问题，研究冗余编码传输与逐 跳重传在达到相当可靠性时耗费平均的发送次数，并提出了一种基于网络编码冗 余传输机制，更进一步地减少了系统的平均发送次数。 1 4 章节安排 本文共分五章，具体安排如下。 第一章简要介绍了无线传感器网络的基本特点，无线传感器网络可靠传输 的研究现状和需要解决的问题，并对本文的研究目标、内容和结构进行了论述； 第二章对无线传感器网络的可靠传输机制进行了总结和分类，介绍了目前几 种主要的可靠传输方法，分析了各自的优缺点，明确了可靠传输机制的研究方向； 第三章提出了一种新的基于网络编码和控制消息的可靠传输机制。通过在发 送节点选择多个可靠性较高的下一跳接收节点，使得当一个节点接收失败时，启 动次优节点来转发，提高发送节点的传输可靠性，减少了重传次数。 第四章每个节点对于收到的同组编码包，根据一定的可靠度确定自己需要发 送的编码包个数以及每个邻居节点需要承担的转发包个数，动态地调整每个节点 需要发送的编码包数，提高了传输可靠性。最后，模拟实验验证了方案的有效性。 第五章对全文进行了总结。 8 2 1 网络编码 第二章网络编码及其应用概述 随着信息技术的不断发展，各种通信网络与人们生活的各个方面的联系越来 越紧密。同时，由于用户数量的激增，网络服务的多样化以及对网络传输质量要 求的不断提高，使得提高现有网络资源的利用率以及优化网络成为当今网络通信 研究的重要课题之一。 2 1 1网络编码的提出 传统的网络路由方式是在网络中在源节点与s i n k 节点之间选择一条或者多 条传输路径，这种方式下路径上的节点只对数据分组进行路由或复制，并不对数 据做任何其它操作。2 0 0 0 年，网络编码的概念被首次提出。它是一种融合了编 码和路由的信息交换技术，允许转发节点对接收的多个数据包进行编码信息融 合，增大单次传输的信息量，提高网络的整体性能。它表明，对组播网络中的某 些节点附加额外的编码操作能使源与组播成员间达到最大流最小割【2 5 】的组播速 率。 2 1 2 网络编码的基本概念 通信网络中的信息流就像是渠道中流动的水，渠道中可以通过的水量受到渠 道的横截面积的影响。所以，具有单位信道容量的边不能同时被多于一个单位信 息速率的信源使用。而在通信网络中，传输的信息是一系列的比特串，这就与像 水那样的媒质有着本质的区别，所以我们可以对在某条边上传输的信息进行处 理，即进行网络编码。下面介绍网络编码的网络模型。 ( 1 ) 网络模型 一个通信网络以有向图g ( k 日来表示，其中球表节点集，e v x 矿表示边 集。考虑组播情况，用scy 来表示通信网络中的信源，集合tcv 表示目的节 点的集合。网络中的节点可以分为源节点、中间节点和目的节点( 有时一个节点 可能既是中间节点又是源节点) 。我们用“1 ，) 来表示节点v 到节点y 的边，即 “v ) e ；边p = “ ，) 的头为1 ，= ( p ) ，其尾为1 ，= “p ) ，几，) 表示节点v y 的输入边 的集合几订表示节点，y 的输出边集合。 某个信源节点1 ，产生的信息空间为口( 力= f 坂v j ) ，坝v2 ) ，：坦e 2 ( v ) ) ，它是由 ( ，) 个离散独立的随机过程组成的，其中每个离散随机过程均取自有限域矽 2 6 l ， 9 所以节点y 的熵由公式( 2 1 ) 计算获得。 世) h = 艺h ( x ( v ，f ) ) = m t ( v ) 公式( 2 1 ) i = 1 目的节点所收到的信息空间函( 功= z ( v n 狲2 ) ，”：z ( e 刀( v ) ) ) ，它是由刁 个离散随机过程组成。在一个通信网络中，可以用“1 ，：q “v ，) ) 来表示节点v 和节 点v 之间的通信，它们之间所需传输的信息是口“1 ，) 。节点v 可以通过从它出发 的边p = “1 ，) 来传输信息，我们用随机过程及p ) 表示。边上所传输的随机过程的取 值范围是有限域矽。 ( 2 ) 网络编码定义 网络编码不同于传统路由之处就在于在各个中间节点上的信息处理方式，下 面定义各边上的函数映射。对边集e 中的每条边p = “v j ) ，存在一种映射，如公式 ( 2 2 ) 所示。 厂? 。县，) f 2 m f 2 一 公式( 2 - 2 ) 这是对应于每条边的编码函数，它把某个节点所有输入边上的信息映射成其 某个输出边上将传输的信息。为了得到所需信息，目的节点对映射矾，是对应与目 的节点v 的第f 个所需信息的译码函数，如公式( 2 3 ) 所示。它从此日的节点输 入边上所传输的信息中恢复出所需信息。如果存在编码函数力和译码函数凰，使 口 v 夕c 痧r v 夕，则称通信网络 v ：口“v ) ) ，是可解的，同时称编码函数和译 码函数凰，是此网络的一组解。 v z v ，d 垂v ) ， g ，j ，野，) f 2 m - - ，矿 公式( 2 - 3 ) 2 1 3网络编码的发展现状 自从r a hl s w e d e 等人提出网络编码的基本概念之后，关于网络编码的研究 如雨后春笋般先后开展起来。目前，有很多电信业巨头和著名的大学都在致力于 这方面的研究，比如说，有香港中文大学、微软、麻省理工学院、伊利诺伊大学、 加利福尼亚大学洛杉矶分校、以色列的t e l a v i v 大学等等。 继网络编码概念被提出后，s y r l i 2 7 1 等人随后表明采用线性的网络编码 在有限足够大的域中能够达到组播容量。m e d a r d 2 s 等人提出了网络编码的代数 框架，并证明了满足组播容量的线性时不变编码。他们的工作为网络编码的发展 提供了必要的理论基础。h om e d a r d l 2 9 1 等人于2 0 0 3 年进一步提出了随机网络编 码，它的提出扩大了网络编码的应用环境，使其不再被局限于应用于特定的拓扑 结构中。对于现有网络编码方式，根据它生成方式的不同，我们可以将其分为以 l o 下两大类：根据编码系数生成的随机性可划分为随机网络编码和确定网络编码， 对于确定网络编码，根据构造方式，又可分为代数构造方式和多项式时间够造方 式；按照节点输出和输入的关系可划分为线性网络编码和非线性网络编码。 按网络编码的构造方式，可以将确定性网络编码方法分为两种：一种方法是 由mm e d a r d 和r ko e t t e r 给出的网络编码的代数构造方式。这种网络编码的构 造方法需要首先知道整个网络的拓扑信息，用一个系统转移矩阵描述信源输入信 息和信宿上接收到的信息之间的关系，并通过构造符合要求的系统转移矩阵来实 现网络编码。另一种是p s a l l d e r 【3 0 】等人提出的一种实现网络编码的多项式时间算 法，这种方法将网络编码的构造进一步简化，但是它也需要知道网络拓扑，通过 最小割最大流算法找到完成组播所需的路径的集合，在找出的这个子图上，再自 上而下的确定各个节点所需要进行的操作。这种编码方法不但降低了网络编码中 所采用的字母表的下限，还把网络编码构造的复杂度从指数级降到了多项式级。 上述方法都是基于己知整个网络的拓扑信息的编码方法，随机网络编码的提 出使得网络编码不再局限于只能在确定网络拓扑结构中应用。随机网络编码的实 现是通过在网络的中间节点上对接收到的信息在一个有限域内随机选择一个元 素作为组合的系数进行编码。研究表明只要有限域取得足够大，这种方法的失败 率就可以很低。这种方法带来的缺点为了使得解码概率大，必须增大通信网络中 所需的字母表的大小。 线性网络编码是在对信息进行编码时，只对它进行线性组合的变换，在实现 网络编码过程中所用到的编码函数和译码函数均采用线性函数。它不但可以用在 己知拓扑的构造方式中，也可以用在未知网络拓扑信息随机网络编码中。中间节 点将接收到的数据在有限域内进行线性组合，节点收到足够数量的独立数据包就 可以通过正确译码得到全部信息内容。 上述研究都是针对有线组播网络的，并且大部分的研究都集中在提高吞吐量 方面。关于无线网络中的网络编码的研究也是网络编码研究中的一个热点。由于 无线网络自身的一些不同于有线网络的特性，这使得网络编码在无线网络中的应 用带来了新的好处，比如提高吞吐率、减少发送次数、提高传输可靠性、负载均 衡、提高安全性等。本文就是主要关于随机线性网络编码在无线传感器网络中应 用的研究。 2 2 网络编码实现方法 2 2 1线性网络编码 网络编码按照节点输出和输入的关系可划分为线性网络编码和非线性网络 编码。本文主要讨论具有很强的分布式的线性网络编码，当节点在对收到的信息 进行处理时，只对它做线性组合变换，接收节点接收足够数量的独立数据包就可 以通过正确译码解得全部信息内容，能够充分利用网络带宽。在线性编码方式中， 节点运用乘法和加法运算，使发送出去的数据为该节点接收到信息的线性组合。 它的具体定义如公式( 2 4 ) 所示。 l ( e ) = 口“x ( 1 ，) + 尾。， ) ，= l p ： ( p 。) 可( f ) 在接收节点处可得到如公式( 2 5 ) 所示的关系。 z ( v ，f ) =巳f i ( e ) 公式( 2 4 ) 公式( 2 5 ) 在上面的两个式子中，c le , i ，p 咖，p “被称为局部编码向量，它们都取自于域 矽之中。在组播通信网络g ( 形d 中，信源s 矿的输入可以看作