（计算机应用技术专业论文）无线传感器网络差错控制技术研究.pdf

硕士论文 无线传感器网络差错控制技术研究 摘要 无线传感器网络具有移动性、自组织性、以数据为中心等诸多特点，被认为是未来 最具有影响，最能改变世界的技术之一。因为嵌入在每个节点中的电池寿命有限，所以 减少节点和处理器的能量消耗对于传感器网络稳定和成功地运转是至关重要的。进一步 说，功耗或者能量的利用效率是极为重要的，所以最好的w s n 设计就是消耗最小的能 量去提供最可靠的通信。 差错控* o ( e c c ) 对于增加网络稳定性和降低所需的传输功耗是一个非常好的方法。 但是，尽管如此，由于接收端的解码器本身也消耗一定的能量，并且这方面的消耗很可 能抵消了e c c 所带来的能量节省。因此一个好的e c c 编码方案应该是消耗尽可能少的 能量，但是从另一方面上说越复杂即越强大的解码器必然消耗越多的能量。总之，如果 在解码器上花费的能量超出了利用e c c 所带的功耗的节省，那么这个e c c 相对于没有 编码的系统而言并不是能量有效的。 本文主要讨论差错控制技术，主要是前向纠错( f e c ) 编码技术在传感器网络中的应用， 主要讨论该技术怎样才能在传感器网络上达到能量节省的应用效果。我们考虑了单跳簇 状网络模型、线性多跳网络模型和基于洪泛的多路径模型。其中多路径模型是专门为了 应用网络编码所引进的。对于这些模型，首先，我详细地分析了它们的能耗模型，然后在 能耗模型基础上，从数学分析到仿真，详细讨论相关的内容。对于单跳簇状网络模型， 我们讨论了f e c 编码同最佳簇头和最佳数据包长度的相结合技术，最后，我们讨论了 先检错再纠错的c r c f e c 联合方法；对于线性多跳网络，我们引入了最优节点间距的 概念，并在此基础上讨论了端到端f e c 和逐跳f e c ，在洪泛的多路径模型中，我们讨 论了网络编码技术，并讨论了将f e c 编码和网络编码n c 进行联合编码的技术科c f e c ) 。 关键词：差错控制前向纠错能量消耗网络编码无线传感器网络 a b s t r a c t 硕士论文 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 sw i t hm o b i l i t y ，s e l f - o r g a n i z a t i o n , d a t a c e n t r a l i z a t i o na n dm a n y o t h e rf e a t u r e sa r ec o n s i d e r e da so n eo ft h em o s ti n f l u e n t i a lt e c h n o l o g i e st h a tc a n c h a n g et h e w o r l di nt h ef u t u r e d u et ol i m i t e de m b e d d e db a t t e r yl i f e t i m ea te a c hs e n s o rn o d e ，m i n i m i z i n g p o w e rc o n s u m p t i o ni nt h es e n s o r sa n dp r o c e s s o r si sc r u c i a lt os u c c e s s f u la n dr e l i a b l en e t w o r k o p e r a t i o n p o w e ra n de n e r g ye f f i c i e n c yi so f p a r a m o u n ti n t e r e s t , a n dt h eo p t i m a lw s n d e s i g n s h o u l dc o n s u m et h em i n i m u ma m o u n to f p o w e rn e e d e dt op r o v i d er e l i a b l ec o m m u n i c a t i o n e r r o rc o n t r o lc o d i n g ( e c c ) i sac l a s s i ca p p r o a c hu s e dt oi n c r e a s el i n kr e l i a b i l i t ya n d b w e rt h er e q u k e dt r a n s m i t t e dp o w e r h o w e v e t , l o w e r e dp o w e ra tt h et r a n s m i t t e rc o m e sa tt h e c o s to fe x t r ap o w e rc o n s u m p t i o nd u et ot h ed e c o d e ra tt h er e c e i v e r s t r o n g e rc o d e sp r o v i d e b e t t e rp e r f o r m a n c ew i t hl o w e rp o w e rr e q u i r e m e n t s ，b u th a v em o r ec o m p l e xd e c o d e r sw i t h h i g h e rp o w e rc o m u n a p t i o nt h a ns i m p l e re r r o rc o r s r o lc o d e s i f t h ee x t r ap o w e rc o n s u r r p t i o na t t h ed e c o d e ro u t w e i g h st h et r a m m i t t e dp o w e r 鼢v i i l 笋d u et ou s i n ge c c ，t h e ne c cw o u l dn o t b ee m r g y = e f f i c i e n tc o m p a r e dw i t ha nu n e o d e ds y s t e m t h i sp a p e rd i s c u s s e se l i - o rc o n t r o lt e c h n o l o g y , m a i n l yt h ef o r w a r de r r o rc o r r e c t i o nf f z c ) t e c h n o b g ya n dh o wc a ni ta c h i e v ee m r g y - 阻v i n ge f f e c ti nt h es e n s o rn e t w o r k w ec o n s i d e r t h r e en e t w o r km o d e l s ：as i n g l ej u m pc l u s t e rn e t w o r km o d e l , ah r i e a rm u l t i - h o pn e t w o r km o d e l a n daf l o o dm u l t i - p a t hm o d e lt h a tc a nb eu s e db yn e t w o r kc o d i n g f o rt h e s em o d e l s ，f i r s to f a l l , id e t a i l e da n a l y s i so ft h e i re n e r g yc o m u m p t i o nm o d e l ，a n dt h e nb a s e do nt h em o d e lo f e n e r g yc o n s u m p t i o n , t i o mt h em a t h e m a t i c a la l i a l y s i st ot h es i m u l a t i o n , id e t a t i e dd i s c u s s i o m 他l a t e dc o n t e n t f o rs i n g l e j u m pc l u s t e rn e t w o r km o d e l ，w ef i r s td i s c u s s e dt h eo p t i m a ln u m b e r o fc l u s t e rh e a da n dt h eo p t i m a ld a t ap a c k e tl e n g t h , t h e nh o wf e ci n t e g r a t e dw i t ht h e m , f i n a l l y ，w ed i s c u s s e dt h ec r c - f e cj o i n ta p p r o a c h f o rm l i n e a rm u l t i - h o pn e t w o r k ，w e h a v ei n t r o d u c e dt h eo p t i m a ld i s t a n c eb e t w e e nn o d e s ；o nt h eb a s i so fo p t i m a ld i s t a n c e ，w e a l s od i s c m st h ee n d - t o - e n df e ca n dh o p - b y - h o pf e c ；f o rt h ef l o o dm u l t i - p a t hm o d e l , w e d i s c u s s e dt h en e t w o r kc o d i n gt e c h n o l o g y , a n dat e c h n o b g yo fn e t w o r kc o d i n gj o i n te c c o d i n g ( n c f e c ) k e yw o r d s ：e r r o rc o m r o l ，f o r w a r de r r o rc o r r e c t i o n ，e n e r g y ，w i r e l e s ss e n s o rn e t w o r k 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 触丝 够年占月矽日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 ： j - 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理： 研究生签名：越墼o 雪年月之羽 硕士论文无线传感器网络差错控制技术研究 1 绪论 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 ) 以下简称传感器网络，就是由部署在监测区 域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网 络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给 观察者。传感器、感知对象和观察者构成了传感器网络的三个要素。如果说i n t e r n e t 构 成逻辑上的信息世界，改变了人与人之间的沟通方式，那么，无线传感器网络就是将逻 辑上的信息世界与客观上的物理世界融合在一起，改变人类与自然界的交互方式。人们 可以通过传感器网络直接感知客观世界，从而极大地扩展现有网络的功能和人类认识世 界的能力。美国商业周刊和m i t 技术评论在预测未来技术发展的报告中，分别将无线 传感器网络列为2 l 世纪最有影响的2 l 项技术1 1 i 和改变世界的1 0 大技术之一2 l 。无线传 感器网络、塑料电子学和仿生人体器官又被称为全球未来的三大高科技产业。 无线传感网络在新一代网络中具有关键性的角色，作为一种新的计算模式，推动科 技发展和社会进步，已成为国际竞争的焦点和制高点，关系到国家政治、经济、社会安 全。发展我国具有自主知识产权的无线传感网络技术，推动我国新型无线传感网络产业 的跨越式发展，对于我国在2 l 世纪确立国际战略地位具有至关重要的意义。 1 1 2 课题研究的意义 传感器网络目前被广泛应用于通信设备，包括工业、安全监控、医疗、环境和天气 监测等等。特别是在恶劣环境下或者是人所不易到达的环境中实现各种参数( 如温度、 湿度、目标位置等) 的监测和对某些敏感数据的采集。由于这些传感器节点受自身规模 的限制，而且能源有限，要给网络内大量的节点重新补充能源几乎是不可行的，这就需 要考虑如何在能源有限的情况下最大限度地降低节点能耗以延长传感器网络的连续工 作时间。所以减少节点能量消耗对于网络稳定和成功地运转是至关重要的。进一步说， 能量的利用效率是极为重要的，所以优秀的w s n 设计就是消耗最小的能量去提供最可靠 的通信。目前在发射机和整个系统设计上，关于如何去降低传感器网络上的能耗已经提 出了一些新的方法i 嵋l 。 我们知道由于信道干扰和路径损耗的影响，无线信道的错误率非常高的，而这会导 致能量浪费。差错控制( e r r o rc o n t r o lc o d i n g ，e c c ) o 对于增加网络稳定性和降低所需的 绪论硕士论文 传输功耗是一个非常好的方法。尽管如此，由于在接收端的解码器【4 i 本身也消耗一定的 能量，并且这方面的消耗很可能抵消了差错控制所带来的能量节省。因此，对于传感器 网络而言，一个好的编码方案应该消耗尽可能少的能量，但是通常越复杂的解码器必然 消耗越多的能量。如果在解码器上花费的能量超出了利用e c c 所带的传输功耗的节省， 那么该e c c 方案相对于无编码的系统而言并不是能量有效的。所以如何实现这两方面 能量消耗的平衡，就是非常重要的了。 1 2 无线传感器网络概述 1 2 1 传感器网络的起源、发展与现状 同其他许多新兴技术一样，军事驱动着传感器网络的研究和发展。二十世纪7 0 年代， 冷战时期的声音监测系统( s o u n ds u r v e i l l a n c es y s t c m - s o s u s ) 、空中预警与控制系统( a i r b o r n ew a r n i n ga n dc o n t r o ls y s t e m - a w a c s ) 都是最早期的传感器网络。这些传感器网络采 用了分级的处理器结构，声音信号处理技术和跟踪技术也在这些系统中得到了发展。 现代传感器网络的研究大概开始于1 9 8 0 年，归咎于d a p p a 的分布式传感器网络项 目( d i s t r i b t s e ds e n s o r n e t w o r k s d s n ) 的启动。d s n 项目的技术主要包括传感( 主要是声 音) 、通信( 共享网络的连接) 、数据处理技术和算法( 包括传感器的自治算法) 和分布 式的软件( 分布式系统和语言的设计) 。这段时间卡耐基梅隆大学( c m u ) 和m i t 也分别 在操作系统和信号处理方面对传感器网络做了很多的研究。 近年来，随着微电子系统( m e m s ) 的发展，体积小和廉价的传感器节点的研制成为 可能，这也直接推动了无线传感器网络的应用。许多商业公司都开始投资于传感器节点 和系统的开发和配置。在1 9 9 8 年，g r e g o r y j p o t t i c 阐释了w s n 的科学意义，且d a r p a 巨资启动了s e n s l t 项目，其目标是实现“超视距一战场监测。1 9 9 9 年橡树岭国家实验 室更是提出了“网络就是传感器的论断。2 0 0 1 年t 技术评论将w s n 列于十种 改变未来世界新技术之首。2 0 0 3 年商业周刊预测：w s n 和其他三项信息技术将会 在不远的将来掀起新的产业浪潮。 2 0 0 6 年初我国发布的国家长期科学与技术发展规划纲要为信息技术确定了三个 前沿方向，其中两个与w s n 的研究直接相关，即智能感知技术和自组织网络技术。国 内的一些科研单位和大学己经初步开展了在传感器及传感器网络方面的研究工作并取 得了一些可喜的成果。 1 2 2 传感器网络的体系结构 典型传感器网络结构结构如图1 1 所示i s l ，包括传感器节点( s e n s o rn o d e ) 、汇聚节点 ( s i n kn o d e ) 和管理节点。大量传感器节点随机部署在监测区域( s e n s o rf i c l d ) 内部或附近， 2 硕士论文 无线传感器网络差错控制技术研究 能够通过自组织方式构成网络。传感器节点监测的数据沿着其他传感器节点逐跳地进行 传输，在传输过程中监测数据可能被多个节点处理，经过多跳后路由到汇聚节点，最后 通过互联网或卫星到达管理节点。用户通过管理节点对传感器网络进行配置和管理，发 布监测任务以及收集监测数据。 普 图1 1传感器网络体系结构 网络协议结构是网络的协议分层以及网络协议的集合，是对网络及其部件所应完成 功能的定义和描述。虽然无线传感器网络与传统网络相比有很多不同的地方，但是其网 络协议栈都可以划分成t c p i p 的五层模型，如图1 2 所示。其中，物理层遵照 i e e e s 0 2 1 5 4 标准提供简单但健壮的信号调制和无线收发技术；数据链路层又分成两个 子层：逻辑链接控制层( l l c ) 和介质访问控制层( m a c ) ，主要负责数据成帧、帧检测、 媒介访问控制和差错控制；网络层主要负责路由生成与路由选择；传输层负责数据流的 传输控制，是保证通信服务质量的重要部分；应用层包括一系列基于检测任务的应用层 软件；能量管理平台管理传感器节点如何使用能源，在各个协议层都需要考虑节省能量； 移动管理平台检测、注册传感器节点的移动，维护到汇聚节点的路由，使得传感器节点 能够动态跟踪其邻居的位置；任务管理平台在一个给定的区域内平衡和调度监测任务。 3 绪论硕士论文 图1 2 无线传感器节点协议栈结构图 1 2 3传感器网络的关键技术 无线传感器网络作为当今信息领域新的研究热点，涉及多学科交叉的研究领域，有 非常多的关键技术有待发现和研究，在此本文仅讨论部分关键技术。 1 ) 低功耗控制 鉴于传感器网络的应用环境，基于电池供电的传感器节点通常无法进行能源替换， 以致能量消耗直接影响网络的生命周期和稳定性。所以如何进行有效的能量利用贯穿着 整个传感器网络体系结构的设计。在系统的功耗模型中，我们最关心的是： ( 1 ) 微控制器的操作模式( 休眠模式、操作模式、潜在的减慢时钟速率等) ，无线前端 的工作模式( 休眠、空闲、接收、发射等) ； ( 2 ) 在每种模式中，每个功能块的功耗量，及它与哪些参数有关； ( 3 ) 在发射功率受限的情况下，发射功率和系统功耗的映射关系； ( 4 ) 从一种操作模式转换到另一种操作模式的转换时间及功耗； ( 5 ) 无线调制解调器的接收灵敏度和最大输出功率； ( 6 ) 附加的品质因数( 如发射前端的温漂和频稳度、接收信号场强指示( r s s i ) 信号的 标准。 传感器节点消耗能量的模块包括传感器模块、处理器模块。随着集成电路工艺的进 步，处理器和传感器模块的功耗变得很低，绝大部分能量消耗在无线通信模块上。图1 3 所示的是d e b o r a he s a i n 在m o b i c o m2 0 0 2 会议上的特邀报告( w i r e l e s ss e n s o rn e t w o r k , p a r ti v ：s e n s o rn e t w o r kp r o t o c o l s ) q a 所叙述传感器节点各部分能量消耗的情况，从图中 可知传感器节点的绝大部分能量消耗在无线通信模块。传感器节点传输信息时要比执行 4 硕士论文无线传感器网络差错控制技术研究 计算时更耗电能，1 0 0 m离时传输l 比特信息需要的能量大约相当于执行3 0 0 0 条计算 指令消耗的能量。所以考虑如何在无线通信中节省能量消耗是非常重要的，本文考虑的 差错控制方案正是无线通信中的一种有效节能方案。 2 a ； i s e 襄1 0 雷 5 i ：o 传感器 处理器 发送：接收空闲二v - i a k ， 图1 3 传感器节点各部分能量消耗 2 ) 拓扑控制 由无线传感器网络生成的网络拓扑中，可以直接通信的两个结点之间存在一条拓扑 边。如果没有拓扑控制，所有结点都会以最大无线传输功率工作。在这种情况下，一方 面，结点有限的能量将被通信部件快速消耗，降低了网络的生命周期。同时，网络中每 个结点的无线信号将覆盖大量其他结点，造成无线信号冲突频繁，影响结点的无线通信 质量，降低网络的吞吐率。另一方面，在生成的网络拓扑中将存在大量的边，从而导致 网络拓扑信息量大，路由计算复杂，浪费了宝贵的计算资源。因此，需要研究无线传感 器网络中的拓扑控制问题，在维持拓扑的某些全局性质的前提下，通过调整结点的发送 功率来延长网络生命周期，提高网络吞吐量，降低网络干扰，节约结点资源。 目前传感器网络中的拓扑控制按照研究方向可以分为两类：节点功率控制和层次型 拓扑结构组织。功率控制机制调节网络中每个节点的发射功率，在满足网络连通度的前 提下，均衡节点的单跳可达邻居数目。层次型拓扑控制利用分簇机制，让一些节点作为 簇头节点，由簇头节点形成一个处理并转发数据的骨干网，其他非骨干网节点可以暂时 关闭通信模块，进入休眠状态以节省能量。目前在这两方面都提出了很多的方法1 5 】，但 是大多还不完善。大部分算法处于理论研究阶段，而且，随着传感器网络技术的发展， 拓扑研究的分类已经没有那么严格，往往是多种方式的结合，并引入启发性、数据捎带 等机制，以达到能量节省和拓扑快速形成的目的。 3 ) 定位 传感器网络定位技术中，根据节点自身位置是否已知，可分为信标节点( b e a c o nr o d e ) 莉位置节点( u n k n o w nn o d e ) ，信标节点可通过携带g p s 等定位设备来获取自身的精确位 置，位置节点通过信标节点的位置确定自己的位置。节点定位算法通常可以分为基于距 绪论 硕士论文 离和距离无关定位。基于距离定位通常定位精度相对较高，但对硬件要求较高，耗能也 较多。基于距离定位的方法可分为t o a 、t d o a 、a o a 和r s s i 定位等。距离无关定位 无需实际测量节点间的绝对距离或方位就能够计算未知节点的位置，因此降低了对节点 硬件的要求，使得节点成本更适合于大规模传感器网络，但是定位精度相对要差一点。 目前提出的定位机制主要有质心算法、d v - h o p 算法、a m o r p h o u s 算法、a p i t 算法等。 4 ) 同步 时钟同步是无线传感器网络的一项重要支撑技术，其自身协议的运行及基于其上的 应用( 如标记数据采集时间、时分多址接入、协同休眠、定位、数据融合等) 都需要网络 中节点的时钟保持同步。目前知名的定位技术有网络时间协议( n t p ) 和全球定位系统 ( g p s ) 。n t p 是局部最优的有线网络时间同步技术，而w s n 的同步是无线且需要全局 最优，所以n t p 是不适合w s n 的。g p s 系统对接收机的要求较高，且在有障碍的环境 中基本无法使用。所以g p s 只能有限地应用于某些w s n 中。 j e l s o n 和k r o m e r 在2 0 0 2 年8 月的h o t n e t s - i 国际会议上首次提出和阐述了传感器 网络中的时间同步机制的研究课题后，世界上有许多大学和科研机构都开始了同步技术 的深入研究，其中r b s 0 b f e r e n c eb r o a d c a s ts y n c h r o n i z a t i o n ) 、t i n y m i n i s y n c 和t p s n ( t i m i n g - s y n cp r o t o c o lf o rs e n s o rn e t w o r k s ) 被认为是三种最基本的同步机制1 5 1 。其中 r b s 机制是基于接收者接收者的时间同步，通过广播发送时间参考分组实现同步； t i n y m i n i s y n c 是简单的轻量同步机制；t p s n 采用层次结构实现整个网络节点的时 间同步。 1 3 本文研究的内容 差错控制技术( e r r o rc o n t r o l ，e c ) 是数据链路层的一个最重要的任务，其目标是允许 一定差错水平基础上，在传输信道上可靠地传输分组数据。目前差错控制技术已经广泛 应用于有线网络和普通的无线网络，例如a dh o c 网络，但是对于传感器网络，我们却 不能把这些网络的差错方案原样照搬过来，主要是由于传感器网络能量供应受限的特点。 在无线传感器网络中，要获得可靠性的传输，还要满足其他条件，并且要保证能量消耗 最小。最重要的和普遍应用的差错控制方法和校正机制是冗余技术、重传技术及传输参 数的选择问题，这些参数包括分组大小和传输功率等。 、 本文中主要讨论前向纠错( f e c ) 在单跳传感器网络和多跳传感器网络的应用情况。传 感器网络中一个很重要的问题是保证可靠性与消耗能量的关系问题，通常较高的可靠性 要消耗较多的能量。对于应用在f e c 技术中的差错控制编码( e c c ) 来说，复杂的编码纠 错能力强，但冗余度可能很大或者解码算法过于复杂以至于消耗更多的能量，相反，简 6 硕士论文无线传感器网络差错控制技术研究 单的编码虽然冗余度和解码算法都很简单，但是纠错能力不强的编码是不能应对差的信 道条件。针对于此，本文对单跳和多跳传感器网络做了详细研究。本文首先提出了详细 的能耗模型，然后以此模型为基础找到各种差错技术在不同信道条件下的可靠性和能耗 的最佳平衡点。在此过程中，本文还找出了最佳的数据包大小和单跳网下的最佳簇头数。 多跳网络环境中，本文比较分析了逐跳( h o p b y - h o p ) f e c 和端到端( c a d t o e n d ) f e e 技术， 并且提出了先检错在纠错的c r c f e c 技术。在此，本文还引入了近年来提出来的极具 创新思想的网络编码技术科c ) ，并且提出了网络编码和差错编码( e c c ) 相结合的联合编 码技术( n c e c c ) 。 1 4 与本文相关的前期研究 由于国内在传感器上的研究刚刚起步，所以研究的方向也集中在核心技术上面，比 喻说路由、拓扑、定位和同步，关于传感器网络差错控制方面只有很少的涉及。国外由 于传感器网络发展的较早，关于传感器网络的差错控制也有一定的研究，在此我讨论一 些与本文相关的研究文献。 1 ) 文献【6 】讨论了一系列差错控制编码( e c c ) 译码器的执行情况，包括数字和模拟的线 性分组码、卷积码和迭代码译码器。作者在此基础上不仅讨论了e c c 所带了的能量节 省，而且还提出了关键距离( d 僳) 的概念。关键距离就是在此距离上利用差错编码和没有 利用差错控制编码的每比特的能量消耗是相等的，当距离大于d c r 时，利用差错编码的 系统将会节省w s n 的能量。作者还得出了路径损耗因子1 1 = 2 ，3 ，4 时，各种频率( f ) 下的关键距离取值： 当n = 2 时，在f = 1 0 g h z ，模拟的( 1 6 ，1 1 ) 扩展海明码最短的关键距离是3 0 m ， ( 1 6 ，1 1 ) 2 t u r b o 乘积解码器的最短关键距离是4 8 m 。这些解码器对于室内或者走廊环境是 实用的。并且，在很低的频率下且在没有额外的噪音和干扰的自由空间中，d f r 的值是 极其大的，直到频率f = 3 g h z 时，所有解码器的关键距离才降到1 0 0 m 以下。 当n - - 3 时，模拟( 1 6 ，1 1 ) 扩展海明码和( 1 6 ，1 1 ) 2 扩展t u r b o 乘积解码器在此有最小的 关键距离，当f = 5 g h z 时，关键距离分别是1 5 m 和2 1 m ；当f = 1 0 g h z 时，分别是1 0 和1 3 m 。在最低频率4 5 0 m h z 时，最小的关键距离是0 6 ，1 1 ) 扩展海明码所得到的 d r r = 7 6 m 。然而其他所有的解码器的关键距离都在1 0 0 m 以上。 当n = 4 时，f = 2 g h z 时，除了模拟t u r b o 解码器以外的模拟解码器的关键距离都小 于2 5 m ，甚至在1 0 g h z 时还小于1 0 m 。作者还提出，当频率为2 4 g h z 时，模拟( 1 6 ，1 1 ) 扩 展海明码和( 1 6 1 1 ) z t u r b o 乘积解码器的能量效益最大。 最后作者得出结论：o ) 除了模拟的t u r b o 解码器以外，其他的模拟解码器都是能量 高效的。( 1 0 同模拟解码器相比，数字解码器通常都有更大的d c r 值，通常比模拟解码 7 绪论 硕士论文 器多2 到4 倍。o n ) 对于某些场景而言，特别是在f 1 g h z 时的自由空间传输时，差错 控制编码只有在很大的距离才能节省能量。所以能量高效的差错控制编码必须要考虑传 输环境、频率和解码器装备。 该文很好的说明了节点之间的距离对能量消耗的影响，特别是说明了各种环境下用 哪种差错控制编码是最能量高效的，这对差错控制编码在传感器网络上应用具有指导意 义。 2 ) 文献 7 】提出了能量效率的概念，并以其作为能量消耗和可靠性之间的度量。事实上， 能量效率代表了应用在相邻节点间通信总能量中的有效部分，作者以其为基础，进一步 讨论了无差错编码和有差错编码下的最佳数据包长度，最佳数据包长度就是能量效率最 高时的数据包长度。 从文中可以看出，不管是否利用差错控制编码，当信道出错率p 固定时，如果数据 包长度小于最佳数据包长度时，能量效率呈现陡然下降的趋势。这个现象归咎于传输小 数据包的高花费和启动能量消耗。另一方面来说，当负载长度大于最佳长度时，能量效 率下降但是平稳的。通常最佳数据包长度随着可靠性( r ) 的增加而增加，所以，在可靠的 信道条件下，我们能传输长的数据包仍然能获得好的能量效率。总之，最佳数据包尺寸 对w s n 的能量节省是非常重要的。 文中还讨论了纠错能力为t - = 2 、4 和6 的二进制b c h 的线性分组码进行前向纠错。 作者发现利用差错编码进行纠错会显著地改进能量效率，其中4 纠错能力的二进制b c h 码改进能量效率多达2 3 。二进制b c h 码的最大可获得的能量效率随着t 增加而增加， 且相关的最佳数据包尺寸也随着增长。但是当数据包非常小时( f 满足加法交换律。对于加法，相加后使所得值不变的元素称为零元素，用0 表示。 f 中的非零元素满足乘法交换律。对于乘法，相乘后使所得值不变的元素称为 单位元素，用l 表示。 f 满足分配率。即对于f 中的任何三个元素a 、b 和c ，有a ( b + c ) = a b + a c 对于任何质数q ，存在一个含有q 个元素的有限域。我们称其为伽罗华域( g a l o i s 域) ， 记做g f 。g f 可以扩展到q m 个元素，记做g f ( q m ) ，称为g f ( q ) 的扩展域，其中m 为正整数。在数字传输和存储系统中，由于编码总是二进制形式的，因而使用最广泛的 是二进制g f ( 2 ) 及其扩展域g f ( 2 m ) 。二进制算法中，采用的是模2 加和模2 乘。除了2 被看做0 以外，其他的算法与普通算术相同。 r e e d s o l o m o n 码使用的是非二进制域g f ( 2 m ) ，其元素个数大于2 ，它是二进制 g f ( 2 产o ，1 ) 的扩展。g f ( 2 m ) 域除了0 和l 之外，其余元素都相等，可用a 表示。所有 非0 元素都可以用a 的幂表示。 为了表达伍的幂，我们必须定义扩展域中的乘法操作“一。使用乘法操作可以产生 一个含有无限多元素的集合f ： f = ( o ，一，仅1 ，a 2 ，a j ，) ( 2 2 ) 为了从f 获得有限域g f ( 2 m ) ，必须对f 加以条件限制，以便选出2 m 个元素，且令这2 m 个 元素对于乘法运算子封闭。这个条件就是一个不可约多项式，其典型格式如下： a 2 m 一1 = 1 = a o 门孙 、一一， 1 3 差错控制技术及其他相关技术硕士论文 使用这个不可约多项式，幂次大于2 m 一2 的元素可以简化成幂次小于2 m 一2 的元素，即： 0 2 m + n = 0 2 m 一1 0 n + 1 = 0 n + 1 ( 2 4 ) 于是集合f 变为集合f ，其非零项对于乘法运算自封闭： f = ( 0 ，1 0 2 ，o c 2 m ，铲m ，辞m ，) = ( 0 ，a 0 ，a 1 ，0 2 ，0 1 2 m - 2a 0 ，1 ，铲) ( 2 5 ) 取f + 的前2 m 项，就可以得到有限域g f ( 2 m ) 元素的表示： g f ( 2 m ) = f 0 ，0 0a 1 ，a 2 ，a 2 m - 2 ) ( 2 6 ) 有限域g f ( 2 m ) 中的2 m 个元素可表示成一个多项式，其幂次小于或等于m 1 ；另外 元素0 由零多项式( 即不带非零项的多项式) 表示。g f ( 2 m ) 中的每个非零元素可记做多项 式( x ) ，其m 个系数中至少有一个不为零， 0 i = o h c x ) = o h , o + o h a x + o h , z x 2 + + o h , m - 1 x m 一1 ( 2 7 ) 而且，有限域中两个元素间的加法将定义为相应多项式系数的模2 加。即： 0 i + d = ( o h ，o + 吗，o ) + ( 1 + 吗1 ) x + + ( ，i n 一1 + c l j 皿一1 ) x m 一1 ( 2 8 ) 这样，我们就可得到一个有限域g f ( 2 m ) ，并且通过式( 2 7 ) 可以获得对有限域中2 m 各元 素的多项式表示。 2 2 常用差错控制技术 2 2 1 自动重发请求( a r q - a u t o m a t i cr e p e a tr e q u e s t ) 自动重发请求是指发送端发送能够检测错误的编码序列，编码方法主要是通过在数 据包尾部加入校验和( 帧校验序列) ，校验和是用户数据和首部的函数。c r c 是一个应用 广泛的校验和，这种方法常采用8 比特、l6 比特或3 2 比特的校验和数据。c r c 值得计算 可以用一个线性反馈移位器来实现1 1 7 l 。接收端译码器对接收到的首部和用户数据重新计 算校验和。如果重新计算的校验和与包含在分组中的校验和相等，则接收机认为接收数 据是正确的，返回无错认可( a c k ) ，否则发送有错否认( n a g ) 。如果发送端接收到n a k 请求，其将有错的码组重发，直到接收端认为正确接收为止。典型的a r q 模型如图2 3 所示： 1 4 硕士论文 无线传感器网络差错控制技术研究 信道 解码器 及缓存 图2 3 自动重发请求模型 目前主要有三种标准的a r q 协议，它们之间的主要区别在于它们不同的缓冲要求和 重传策略。 1 ) 停止一等待策略( s t o p - a n d w a i o 这种方法要求发送端收到了a c k 后才能发送下一个包，可见如果在“长而宽带管 道”中传输时，该方法效率是不高的。 2 ) 退n 步策略( g o - b a c k - n ) 该策略中，发送方无需等到a c k 就可以发送下一个包，直到收到接收端发出的重发 请求时停止。此时，发送端停止发送，后退到那个不能被正确接收到的码字序列。相比 停止等待策略，该策略提高了系统的吞吐量而且减少了延迟。然而，由于退n 步策略 也重传了已经正确接收到的分组，因此浪费了一些能量。 3 ) 选择重传( s e l e c t i v e - r e p e a t ) 相比较于退n 步重传策略，选择重传策略只重发那个错误接收到码字，而不重发从 错误码字后面的已经被成功接收到的码字。不过，选择重传策略需要合适的缓冲区及算 法实现。 从上可以看出a r q 主要的优点是构造比较简单，不需要复杂的编码和解码算法。 主要缺点是重传所带来的巨大的延迟，而且不管传递是否正确，都要返回一个确认数据 包，这对于能量有限的w s n 不是能量高效的。 2 2 2 前向纠错( f e c - f o r w a r de r r o rc o r r e c t i o n ) 前向纠错( f e c ) 依赖于在发送端码字中有控制地加入冗余信息，信号在噪声信道中进 行传输时会产生误码的情况，借助于冗余信息可以在接收端进行检错和纠正，不管码字 是否成功，接收端不再进行任何的下一步处理。图2 4 表示了典型的f e c 结构模型： 差错控制技术及其他相关技术硕士论文 信编码器 源及缓存 信道 噪声 图2 4前向差错控制模型 自从香农于1 9 4 8 年开创了编码于信息论的领域以来，已经提出了许多编码方案。两 种广泛应用的编码方法是分组块编码和卷积码。最近提出的t t r b o 码具有接近香农信道 容量的潜力，但是实现起来比较复杂，直到现在还没有作为无线传感器网络的候选编码 方式。所以目前本文只能从已有的编码里面选择最适合的。下面分别讨论块编码和卷积 码。 1 ) 块编码f e c 块f e c 编码器取k 个p 迸制源符号( s o t r c es y m b o l s ) 作为一个数据块或一个字( w o r d ) ， 产生一个包含n 个q 进制信道符号( c h a n n e ls y m b 0 1 ) 的数据库。通常，取p = q = 2 ，n k ， 符号即对应于比特，不同的源数据块是互相独立地进行编码的。由2 k 个不同源符号到2 n 个不同信道符号的映射是单射的，且映射到范围是有效信道符号的集合。这种映射称为 编码( c o d e ) ，k n 的比值称为码率( c o d er a t e ) 。在信道中长度为n 的数据块中能被可靠地 纠正的比特数t 值，取决于编码方法。然而，其上界受到海明界( h a m m 证gb o u n d ) 的限制。 海明界表示，如果式2 9 表示条件得到满足，将k 比特用户数据块映射为n 个信道比特 的映射，可以纠正最大的t 比特的差错： 2 n - k ；o ( ? )( 2 9 ) 三个变量( n ，l ( ，t ) 满足上述关系，并不表示具有这种性质的编码一定存在。 块编码的一个重要规则是海明距离( h a m m i n gd i s t a n c e ) 。两个有效的信道字w 】和w 2 的海明距离定义为这两个字中两两不同的比特数。整个编码的海明距离d m i n 则定义为所 有有效信道字海明距离的最小值。任何具有海明距离d i n l n 的编码能够可靠地检测出多至 d m i n 一1 个比特差错，并能够可靠地校i e 多至( d m i n i ) i z 个比特差错。在实际应用中， 有效码字的集合应该满足容易进行编码和解码的要求。例如，在线性快编码的方法中， 利用了一个具有2 n 个码字的矢量空间结构，并 1 2 k 个有效码字的子集构成一个子空间。 解码的过程可以被看做一个寻找接收码字在有效码字子空间的正交投影的过程。 r e e d s o b m o n ( r s ) 编码和b o s e c h a u d h u r i - h o c q u c n g h e n m ( b c h ) 编码是广泛应用的块编 码方法。 1 6 硕士论文无线传感器网络差错控制技术研究 如果采用块f e c 作为开环技术来应用，则在每个分组中都会产生一个固定的开销。 在发送模式中，这种开销包括发送一些额外的比特以及为编码所进行的必要的计算等。 对于二进制b c h 编码，编码过程使用一种线性反馈移位寄存器，并假定其能量消耗可 以忽略。对于解码来说，已经开发了一些有效的算法。例如，b c r l c k a m p m a s s c y 算法l 知i 。 这些算法的能量消耗取决于块长度n 和可校正的码率编码数。这些算法的能量消耗基本 上随块长度n 的增加而增加。解码能量1 2 1 l 消耗主要取决于块长度n 和可校正的比特数t ， 如下所示： e d e c = ( 2 n t + 2 t 2 ) 。( e a d d + e 硼小) ( 2 1 0 ) 式中，e a d d 和e 舢l t 是g a b i s 域( g f ( 2 m ) ) 上，m = 【l 0 9 2n + 1 j 时进行加法和乘法所需要的 能量。对于r e e d s o l o m o n 编码，由于这种编码为非二进制b c h 编码的一个子类，因此 也有类似的关系。参考文献【1 8 】中给出的实验表明，能量消耗还取决于码率，能量的消 耗随码率的增加而降低。 2 ) 卷积码瞄l 在卷积码中，也是将k 比特用户数据映射为n 个信道符号。然而，两个连续的k 比 特数据块不是相互独立的。下面简要解释卷积码的操作。 编码过程是按步进行的。在