软件工程硕士论文-机会网络中容错传输机制的研究.pdf

湖南大学 硕士学位论文 机会网络中容错传输机制的研究 姓名：黄德君 申请学位级别：硕士 专业：软件工程 指导教师：王如龙;莫继红 20100324 机会网络中容错传输机制的研究 摘要 机会网络是一种无线自组织网络，在实际的应用环境中，这种网络大部分时候不连 通。机会网络不要求源节点与目标节点之问必须存在至少一条完整的通信路径，它可以 利用节点的移动形成的通信机会来转发信息，这种通信模式完全不同于传统的路由方 式，它的很多特点都引起了人们的广泛关注。 本文重点研究机会网络中的容错传输算法，特别针对机会网络中传输数据包的突发 性集中丢失现象，提出了一种基于分组交织与插值技术的容错算法。算法从数据发送和 数据接收两个方面解决数据丢失问题。在数据发送时，算法采用分组交织思想分散数据 包；在数据接收时，利用机会网络中传输数据自相关性强的特点，用插值法恢复丢失的 数据。实验结果表明，该算法能有效的恢复原始数据，当连续丢失的数据包增多时，其 容错性能愈加明显。 由于交织编码以时间为代价，交织深度越大，造成的传输延时也越大。针对这一问 题，本文继而提出基于主成分分析的容错传输算法。利用主成分分析法的数据降维功能 对传输数据进行特征提取，选取合适的主成分，采取a c k 方案对其进行重传。在保留 原始数据主要信息的前提下，减少了传输延时，节约了网络开销。仿真实验表明，这种 算法在提高数据传输效率方面效果良好。 然而，主成分分析并不太适合低维数据集，它的应用具有一定的局限性，因此，本 文提出一种基于h a a r 小波多分辨的容错传输算法。首先，在发送端对信号进行小波变 换，分离出低频系数和高频系数；对低频系数采取确认重传机制传输，对高频系数则直 接传输。然后，利用时频能量守恒性质，在接收端对信号进行重构，恢复原始信号。这 种机制不仅解决了丢失数据恢复的问题，而且时延和网络开销小，适用性强。理论分析 和模拟实验表明，该算法能有效的恢复原始信号，且在连续数据包丢失增多的恶劣干扰 下，仍具有较好的容错性能。 关键词：机会网络；传输容错；分组交织；主成分分析；多分辨 i i _ 1 。程颂f j 学位论史 a b s t r a c t o p p o r t l m i s t i cn e t w o r k si so n ek i n do fw i r e l e s sa dh o cn e t w o r k s ， i nm a n yr e a l i s t i c a p p l i c a t i o ne n v i r o n m e n t ，n o d e sf o 姗ad i s c o 彻e c t e dn e t w o r kf o rm o s to ft h et i m e h o w e v e r ， o p p o r t u j l i s t i cn e t w o r k sd o e s n tr e q u i r ea tl e a s to n ep a t he x is t i n g 仔o ms o u r c et od e s t i n a t i o n n o d e s ，i tc a nu t i l i z et h ec o m m u n i c a t i o no p p o r t u n i s t i ca r i s i n g 矗d mn o d em o v e m e n tt of o n a r d m e s s a g e s ， a n dt h i sc o m m u n i c a t i o nm o d e li st o t a l l yd i f f e r e n tf b mm et r a d i t i o n a lr o u t ew a y ， c 印n 盯e s 黟e a ti n t e r e s t s 舶mr e s e a r c h e r si nl o t so fa s p e c t s ， a 1 1 dt h i st h e s i sh a v er e s e a r c h e d f a u l t t o l e r a n ta l g o r i t me m p h a t i c a l ly t h i st h e s i se l a b o r a t e so naf a u l t - t o l e r a n ta l g o r i t b a s e do ni n t e r l e a v e dc o d i n gt os o l v e d a t ap a c k e t s 1 0 s sp r o b l e mw h i c hc a u s e da b r u p t l yi no p p o 咖n i s t i cn e t w o r k s t h ea 1 9 0 r i t h m c a ns o l v ed a t e 1 0 s sp b l e l ni nt w oa s p e c t s s e n d i n ga n dr e c e i v i n gd a t a w h i l es e n d i n gd a t a ， a l g o r i t h mc a nd i s p e r s ed a t ap a c k e t st h r o u g ht h et h o u 曲to fi n t e r w e a v i n gt r a n s p o r t ，w l l i l e r e c e i v i n gd a t a ，b e c a u s ed a t ai no p p o n i m i s t i cn e m o r k sh a v ea 托a i to fa u t o c o r r e l a t i o n ，b yu s i n g i n t e r p o l a t i o nt h e1 0 s td a t ac a nb er c c o v c r e d t h ee x p e r i m e n tr e s u l t ss h o w e d t h a tf a u l t - t o l e r a n t a l g o r i t h mb a s e do ni n t e m e a v e dc o d i n gc a ne m c i e n t l yr e c o v e rm el o s td a t a m o r e o v e r ， a l g o r i t h mc a i lm a i n t a i ng o o d 如n c t i o ne v e nd a t ap a c k e t sl o s em o r e b u ti n t e r l e a v i n gc o d i n gt a k e st h et i m ea sp r i c e ， t h a ti st o s a yt h a tt r a n s m i s s i o nd e l a y w i l li n c r e a s ew i mt h ei n c r e a s i n go fi n t e d e a v i n gd 印t h t bd e a lw i t hm i sp r o b l e m ， t h et h e s i s p r o p o s e daf 犯l t t o l e r a n ta i g o n m mb a s e d 伽p r i n c i p a lc o m p o n e i l ta l l a l y s i s ( p c a ) f i r s t ， c 痂e so nt h ef e a t u r ee x t r a c t i o nt ot h ed a t a ， b e c a u s et h ep c ah a sa 如n c t i o no fr e d u c i n gd a t a d i m e i l s i o n a l i t y a n dm e n ， s e l e c t sm e 印p r o p r i a t ep r i n c i p a lc o m p o n e n t st ou s et h ea c k m e c h a n i s m ，u n d e rt h ep r 锄i s eo fr e t a i n i n gt h em a i nm e s s a g eo fo r i 酉n a ld a t a ， r e d u c et h e t r a i l s m i s s i o nd e l a va n ds a v em en e t w o r ko v e r h e a d t h es i m u l a t i o nr e s u l t ss h o wt h a tt h e a 1 9 0 r i t h n lh a sag o o dm n c t i o no f r e c 0 v e r i n gt h el o s td a t a h o w e v e r ，t 1 1 ep c ai sn o ts u i t a b i e 向ra nd a t as e t s ， i t sa p p l i c a t i o nh a ss o m e1 i m i t a t i o n s s o ，af a u l t t 0 1 e r a n ta l g o r i t h mb a s e do nm u l t i r e s o l u t i o nh a a rw a v e l e t sw a sp r o p o s e dt od e a l w i mt h ep r o b l 唧o fc o n c e n t r a t e dd a t ap a c k e t sl o s ti no p p o r n l n i s t i cn e t 、) l ，o r k s t h eb a s i ci d e a o fa l g o t h mc a l lb ed e s 嘶b c da sf o l l o w s f i r s t ， t h es i 印a l sa r ed e c o m p o s e db yw a v e l e t t r 觚s f o m l a t i o nt og e tt h el o w - 缸e q u e n c yc o e 伍c i e n t sa n dh i g l l 一舶q u e n c yc o e m c i e i l t sb e f o r ei t i ss e n t t l l ea r qm e c h a i l i s mi su s e dt ot r a n s 衔m el o w 一疗e q u e i l c yc o e 伍c i e i l t s t h e h i 曲一矗e q u e i l c yi st r 锄s f i e 盯e dd i r e c t l y n l e i l ， t h es i 印a l sa r er e s t o r e db a s e do nc o n v e r s a t i o no f 饥吣yi nm er e c e i v e l1 1 1 e o r e t i ca n a l y s i sa i l ds i m u l a t i o nr e s u l t ss h o wt l l a tm ep r o p o s e d a i g o d t h mc a ne 伍c i e l l t l y r 。c o v e rt h eo r i 酉n a ls i 朗a l 锄dm a i n t a i ng o o df a u l t t 0 1 e r a l l t p 酬f 0 册a n c ee v e l lc o n t i n u o u sp a c k e t s l o s tb e c a u s eo ft h eb a dd i s t u r b 锄c e i i i 机会网络中容 ； ；f 输机制的形f 究 k e yw o r d s ：o p p o t u n i s t i cn e t w o r k s ；f a u l t t o l e r a n tt r a n s m i s s i o n ；g r o u pi n t e r l e a v i n g ； p r i n c i p a lc o m p o n e n ta n a l y s i s ；m u l t i r e s o l u t i o n i v t 程埘 f j 学化论文 插图索引 图2 1 分组交织原理图9 图2 2 卷积交织原理图1o 图3 1 波和小波对比示意图15 图3 2 傅里叶变换的几个基函数示意图一1 5 图3 3 小波变换的几个基函数示意图16 图3 4h 从r 尺度函数及其伸缩平移图1 9 图3 5h a a r 小波函数的伸缩、平移图2 0 图3 6 维信号小波分解的迭代过程2 2 图3 7 一维信号小波重构的迭代过程2 3 图4 1 机会网络中丢包示意图2 5 图4 2 样本集分组交织原理图一2 6 图4 3 拉格朗日插值算法基本原理图2 7 图4 4 不同丢包率下的轨迹曲线3 2 图4 5 交织前后数据恢复情况对比图一3 3 图4 6 均方误差曲线对比图：3 4 图5 1 无丢包情况下确认重传示意图3 6 图5 2 有丢包情况下确认重传示意图一3 7 图5 3 原始的轨迹曲线3 8 图5 4 丢包率为1 0 时数据恢复前后的曲线对比一3 8 图5 5 丢包率为2 0 时数据恢复前后的曲线对比3 9 图5 6 丢包率为3 0 时数据恢复前后的曲线对比3 9 图5 7 丢包率为4 0 时数据恢复前后的曲线对比4 0 图6 1 系数分解图4 3 图6 2 系数重构图4 4 图6 3 不丢包情况下获取的轨迹曲线一4 5 图6 4 丢包率10 时数据恢复前后的轨迹曲线4 6 图6 5 丢包率2 0 时数据恢复前后的轨迹曲线4 6 图6 6 丢包率3 0 时数据恢复前后的轨迹曲线4 7 图6 7 均方误差曲线4 7 v i l t 程顾i j 学位论文 1 1 研究背景及意义 第1 章绪论 机会网络由延迟容忍网络( d e l a yt o l e r a n tn e t w o r k ，d t n ) 发展而来，d t n 是指能够容忍较大延时的网络，它起源于星际互联网i p n ( i n t e rp 1 a n e t a r y n e t w o r k s ) 【1 1 。d t n 互联网络由多个独立的互联网络组成，每个独立的互联网络 被称为d t n 域，它们分别运行自己的通信协议，各个d t n 域之间存在预期或随 机的通信机会，由d t n 网关负责它们的互联1 2j 。 机会网络的本质是一种无线自组织网络。相比于传统的网络任一节点对之间 存在至少一条完整的端到端通信路径，机会网络中的节点被分割成多个孤立的连 通区域，即源节点和目的节点之间很可能不存在一条完整的通信链路p 】，因此， 传统的m a n e t ( m o b i l ea dh o cn e t w o r k ) 通信模式无法有效的运行。然而，不存 在完整的通信连路并不代表不能通信。在机会网络中，节点之间通过移动所带来 的相遇机会来实现通信。相对于d t n 网络，机会网络更强调通过节点移动而形成 的节点之间的通信机会，从而能够为非连通区域提供数据传输服务。 机会网络不要求网络的全连通，更适合实际自组网的需求，因为在各种实际 自组织网络应用中，节点移动、节点稀疏、射频关闭或障碍物造成信号衰减等多 种原因都可能导致网络大多数时候不能连通。例如，行驶在公路上带有智能设备 的车辆自组成车载网络，实现交通事故预警和其他道路安全应用；各种配备蓝牙 或w i f i 接口的手持电子设备，如m p 3 播放器、手机、p d a 等自组成网络以实 现数据共享或协作访问互联网；放置在动物身上的传感器组成移动传感器网络收 集动物迁徙数据等【4 】。 在这类网络环境中，传统的m a n e t 通信模式并不适用，因为m a n e t 在传 输用户数据之前，需要预先通过a o d v ( a d - h o co n d e m a n dd i s t a n c ev e c t o r ) 或 d s r ( d y n a m i cs o u r c er o u t i n g ) 等路由算法建立通信端点之间的路由，并将数据分组 按照节点路由表中确定的下一跳节点顺序转发到目标节点【5 】。这种工作模式隐含 一个重要的假设：网络大部分时候是连通的，任一节点对之间存在至少一条完整 的端到端通信路径。而在前述网络中，在一个特定时刻，网络可能被分割成不连 通的子区域，源节点和目标节点位于不同的连通域而导致m a n e t 路由协议不能 发现去往目标节点的路由。然而，通信源和目标不存在完整连通路径并不意味着 不能实现通信，由于节点的移动，两个节点可以进入相互通信范围而交换数据， 机会网络就是利用这种节点对之间的逐跳转发将数据从源节点传输到目标节点。 机会网络的首要任务是把数据在不稳定链接的网络中传输到指定目标节点。 然而由于机会网络采用无线的方式进行通信，节点的移动和链接的不稳定性给节 机会网络中容错传输机制的研究 点问的数据传输带来了新的挑战。首先，因为节点间大部分时间不存在通信链路， 那么数据会长时问的在某个节点上存留，而节点的存储资源是有限的，在短时间 的链接中把大量数据传送出去，需要对数据进行压缩编码传输。其次，由于节点 的移动性将带来无线信道的突发性多径衰落和多普勒频移，而在机会网络中采用 确认重传机制并不现实。为了使接收节点能尽量获得一个完整的数据集，需要提 出新的容错传输机制。 上述两点已成为制约机会网络发展的瓶颈，因此对机会网络中的容错传输机 制进行深入研究对解决上述问题具有重要的意义。 1 2 研究现状 机会网络不要求网络全部连通，更适合实际自组网的需求，因此它被广泛应 用于手持设备组网、野生动物追踪、车载网络和偏远地区的网络传输等方面。例 如在手持设备组网方面，美国剑桥大学和i n t e l 研究院提出的p s n ( p o c k e ts w i t c h e d n e t w o r k ) 是由人随身携带的手持设备形成的机会网络，每个设备节点既可以通过 人们相遇带来的局部通信机会，也可以通过w i f i 或者g p r s ( g e n e r a lp a c k e tr a d i o s e r v i c e ) 等接入i n t e r n e t 的全局连接转发数据，当目标节点位于当前节点附近区域或 不能接入i n t e r n e t ，或者用户应用需要很高的带宽和很小的延迟时，局部连接能比 全局连接提供更好的服务1 6 】。p s n 旨在充分利用手持设备的计算、存储和带宽资 源，透明地利用各种连接方式为用户提供网络服务。如，电子邮件丰富，当发送 节点和接收节点位于相互通信范围内时，p s n 节点不需要接入i n t e r n e t 通过传统的 s m t p 和p o p 3 等技术实现，而是直接利用本地连接转发数据。随着网络技术的进 步和社会经济的发展，越来越多的应用领域将会展示到我们面前，可以肯定，机 会网络的应用前景将会更会宽泛。目前机会网络的研究热点问题包括三个方面， 即节点移动模型、机会转发机制和基于机会通信的数据分发和检索等。 节点移动模型广泛应用于自组织网协议性能的分析和评价，是自组织网络的 基础研究之一，它用来描述节点的位置、速度等特征的变化。由于机会网络中的 数据传输依赖于节点移动带来的相遇机会，因此节点的移动模型以刻画节点相遇 特征为核心。主要有三种类型1 7j ： ( 1 ) 独立同分布的理论移动模型。这种模型下刻画节点相遇特征的参数有两 个：相遇时间m t ( m e e t i n gt i m e ) 和相遇间隔时间i m t ( i n t e rm e e t i n gt i m e ) 。其 中m t 是指两节点从静止开始到首次相遇( 进入通信范围) 所经历的时间长度，而 i m t 是指两节点前后两次相遇的时间问隔长度。有研究表明，节点期望相遇时间 ( e x p e c t e dm e e t i n gt i m e ) 服从指数分布或者其尾部服从指数分布，且相遇时间和 相遇间隔时间的尾部分布式无记忆的博j 。 ( 2 ) 基于统计的实际移动模型。这种模型不仅依靠理论推导，还利用统计方 法，通过收集实际环境中节点的运动轨迹来研究节点的移动特性【9 】。研究人员还 2 丁平口硕l j 学位论文 发现，实际节点的移动具有社区特性，节点相遇时间服从近似的幂律分布，而不 是根据经典移动模型推导出的指数分布f l0 1 。这些成果证实了传统的移动模型并不 定适用于实际节点的移动特性。 ( 3 ) 基于社区的移动模型。该模型下的节点不是随机选取移动位置，而是考 虑节点偏好、节点异构和行为时变性来决策下一步移动的位置【l5 1 。所谓节点偏好 是指节点比其他节点更倾向于去往某个特定位置或遇到特定节点；节点异构性指 某些节点能够到达所有位置或遇到所有节点。行为时变性只节点移动随时间变化 而变化。这种模型根据节点之间联系的紧密程度把节点分布在多个不同区域的社 区，然后计算不同社区对每个节点的吸引力，并以此确定节点是否移动以及朝哪 个目标区域移动j 。 因为路由和转发是任一网络技术面临的首要问题，机会转发机制成为机会网 络中研究的重点与热点。根据转发策略的不同，可以分为基于冗余的转发机制、 基于效用的转发机制、冗余效用混合机制和基于主动运动的转发机制等4 种。在 基于冗余的转发机制中，通过基于复制或编码的方式，每个消息消息产生多个冗 余消息在机会网络中多路径并行扩散传播，提高消息传输性能【2 ，1 3 】。 文献 1 4 提出了一种基于复制转发的2 h o p 算法，源节点上的缓存消息不要 求非遇到目标节点才转发，而是把消息拷贝给先遇到的m 个中继节点，继而再转 发给目标节点，因此消息需要两跳到达目标节点。假设独立移动的节点之l 日j 相遇 的概率为p ，则d t 的传输成功率为p ，而2 h o p 算法的传输成功率为 l 一( 1 一“犯+ 1 ) p ( 当p 较小时) ，这种算法由于支持多条路径，所以可靠性较高。 但只有在少量数据包的情况下，路由的效率高。原因在于数据交换频繁，对节点 的缓存要求较高，并且网络开销较大。 文献 15 提出了一种基于随机线性网络编码的机会转发机制，把网络编码的 技术引入到机会网络中。将来自不同源节点的消息映射到一个有限域内形成一个 信息向量，然后和中间节点随机生成的编码向量进行线性编码，形成一个新的向 量重新注入到机会网络中，当目标节点接收到一定的消息向量后便可解码出原始 信息。而采用网络编码提高网络吞吐量的同时，增加了网络节点的编码操作，继 而提高了其网络开销。 在基于效用的转发机制中，使用单消息拷贝单路径传输，利用网络状态信息 来决策下一跳节点【l6 】；冗余效用混合机制的核心思想为：每个消息产生多个冗余 消息，每个冗余消息按照基于效用的转发策略转发到目标节点【1 7 l8 】；基于节点主 动运动的转发机制是网络中某些节点在部署区域内主动运动莱维其他节点提供通 信服务，不用被动等待，一定程度上提高了网络传输效率【l9 1 。 文献 2 0 提出了一种基于链路估计的转发机制。在最短期望路径路由中，每 个节点都维护到达已知节点的链路可用概率值，节点f 与，之间的链路可用概率为 最，= 乙毛乙是时问窗口乙内节点维持连通的时间长度。该概率值随节点之间的相 3 机会网络中容锗传输机制的研究 遇而更新，也就是说节点每相遇一次，该值就更新一次，并且节点之问相互交换 概率表。该算法把穿越链路时间作为链路长度，假定链路时i 日j 与链路概率值成反 比，当节点获得所有已知节点的本地链路概率后，利用d i i k s t r a 算法计算当前节点 到达目标节点的最短路径，提高链路的效用值。然而为了计算i 、j 节点间的双向 链路质量，必须要在其邻居节点间交换入站链路质量，从而增大了网络开销和传 输延时。 机会网络中的数据是以存储转发的模式来传输数据的，每个转发节点上都会 缓存转发的消息，这种特征使得内容存储成为机会网络的核心部分。在机会数据 分发机制中，请求节点首先发布订阅请求或兴趣消息，产生资源数据的节点将数 据分发给感兴趣的节点。这种机制在d t n 系统，车载机会网络中都有广泛的运用 【2 。机会数据检索机制中，请求节点在网络内发布查询消息，存储对应数据的节 点返回结果消息到请求节点。 机会网络在未来一段时间内的研究热点还有： ( 1 ) 随着手持设备的大量涌现和应用范围的迅速扩大，需要结合社会网络理 论研究手持设备所形成的机会移动模型与高效转发机制的研究。 ( 2 ) 根据具体场合，如车载网络信息分发、水下传感器网络的数据收集等， 研究跨应用层、网络层甚至m a c 等多层的优化通信协议。 ( 3 ) 可以考虑设计机会网络与其他传统集中式网络的混合式应用系统，例如 与蜂窝网或w l a n 的联合应用等。 1 3 本文的研究内容 由于机会网络目前正处于初步的研究阶段，在机会转发机制、节点移动模型 和容错传输技术等方面都有许多难题需要进行深入的研究与实践的检验。本文针 对机会网络中的容错传输机制进行了研究，其主要工作有： ( 1 ) 数据传输机制的研究。 研究机会网络中数据传输机制，分析机会网络中的数据传输特性，对机会网 络中的压缩传输编码和容错传输编码进行深入研究，设计符合机会网络传输特性 的容错传输算法。 ( 2 ) 基于交织与插值容错传输算法的研究。 针对机会网络中数据包突发性集中丢失现象，提出基于交织的容错算法。首 先通过交织传输算法将集中丢失的数据包进行分散，然后利用传输数据自相关性 强的特点对分散后的丢失数据进行插值恢复。 实验表明，基于交织编码容错传输算法不仅能对丢失数据进行恢复，而且随 着连续丢失数据包数量的增多，抗错性能明显增强。 ( 3 ) 基于主成分分析容错传输算法的研究。 由于交织编码以时间为代价，当交织深度增大的时候将会导致较大的传输延 4 丁程硕i j 学位论文 时。为了解决这一问题，提出了基于主成分分析的容错算法。该算法有效的降低 了数据的维度，通过保留低阶成分，忽略高阶成分，从而维持原始信号的基本概 貌。 实验证明，此算法不仅能有效恢复丢失的数据，而且很好的解决了时间开销 的问题。 ( 4 ) 基于h a a r 小波多分辨的容错传输算法 针对低维数据集不太适合单独做主成分分析的不足，提出了基于h a a r 小波多 分辨的容错算法。首先，在发送端对信号进行小波变换，分离出低频系数和高频 系数，对低频系数采取确认重传机制传输，对高频系数则直接传输。然后，利用 时频能量守恒性质，在接收端对信号进行重构，恢复原始信号。 实验结果表明：该算法的容错性能良好，对突发性丢失的数据包具有很好的 恢复性能，且网络开销低，计算简单，易于实现，适用范围广。 全文主要包含如下六个部分，各部分内容安排如下： 第一章绪论。讨论机会网络的相关背景，研究热点，理论与实际意义以及本 文所做的工作； 第二章无线网络中传输编码技术的研究。通过对比分析几种常用的网络编码 技术，获得提高机会网络数据传输效率的编码机制。 第三章主成分分析和小波变换理论的研究。分析主成分分析的特点，以及小 波变换的基本理论，研究h a a r 小波分析和多分辨分析的技术和作用，为建立机会 网络中的容错传输算法提供理论依据。 第四章基于交织编码的数据容错算法。提出基于交织编码的容错算法，并对 该算法的应用效果进行了详细的理论分析和仿真实验。 第五章基于主成分分析的容错传输算法。包括算法的提出，理论分析和实验 验证； 第六章基于小波多分辨的容错传输算法。提出了算法模型，并对该模型的容 错性能进行分析和模拟实验。 总结对全文的研究成果和创新性工作进行了总结，并对本文的下一步研究工 作进行了展望。 5 机会网络中容锚传输机制的研究 第2 章数据传输中编码容错技术的研究 机会网络采用无线的方式进行通信，节点的移动和链接的不稳定性给节点间 的数据传输带来了新的挑战。由于节点间大部分时间不存在链接，那么数据会长 时间的在某个节点上滞留，而节点的存储资源有限，要在很短的链接时间内把大 量数据传送出去，需对数据进行压缩编码传输。 节点的移动性将带来无线信道的突发性多径衰落和多普勒频移，而在机会网 络中采用确认重传机制并不现实，为了使接收节点能尽量获得一个完整的数据集， 需要提出新的容错传输编码机制。一般的编码器为了提高数据压缩比，都采用帧 间预测、离散余弦变换、量化与可变长编码等技术尽可能地去除信号中的时间相 关性和空问相关性【2 2 1 。该方案虽然能取得很高的编码效率，但也使得编码数据流 更容易受误码的影响。无线通信的信道误码率一般都比较高，所以若不采取相应 的控制措施，这些误码扩散与传播将会导致传输信号质量下降到无法接受的程度。 为了减小或消除信道差错的影响。必须采用相应的解决方案和合适的技术来 对抗信道差错。因此，容错技术已成为易发生差错信道下数据压缩编码的重要内 容之一【23 1 。 2 1 传输域容错技术 2 1 1 前向纠错 前向纠错( f o r w a r de r r o rc o r r e c t i o n ，f e c ) 的基本方法是在原始信息中加入 一定的冗余信息，以使在出现传输差错时解码器仍然能够重建原始信息。对于包 交换传输，f e c 信道码通常采用块编码方案，即数据流被分割成不同的段，每个 段被分到不同的数据包中，对每个分段的t 个数据包采用块编码生成n 个数据包， 其中n t 。对具有包顺序的分段，用户只需接收到n 个包中任意t 个，即可精确地恢 复该分段内的原始数据。当前的f e c 方案可分为三种情况【2 4 】： ( 1 ) 基于信道编码的f e c 。对压缩后的数据流进行纠错保护信道编码，常用 的信道码有r s 码、t u r b o 码等。不同于比特差错信道，包交换的无限自组织网络 传输中的f e c 是以包为基本单位的，为包丢失提供恢复保护。它的主要缺点是增 加了码率、引入了时延，同时因采取固定的信道编码码率，因而难以自适应信道 的丢失变化。 ( 2 ) 基于信源编码的f e c 。与信道编码不同，信源编码将冗余信息加到压缩 的数据流中而不是增加额外的包交换码。相对于信道编码的f e c ，这种方法的优 点是时延较低。 ( 3 ) 信源信道联合编码的f e c 。依据s h a n n o n 分离理论，信源和信道可独立 6 t 譬顾l j 学位论义 编码【25 1 。考虑到实际应用中有限的时延要求，该理论的严格条件在实用中难以满 足。为了在信源高效压缩的同时将信道的鲁棒传输考虑进去，联合信源信道编码 已被证明是一种行之有效的解决上述问题的编码技术、。该技术将信源与信道编码 结合在一起考虑，比将最优的信源编码方案与最优的信道编码方案相级联的传统 方法更加有效。 2 1 2 条件重传 典型的条件重传采用“自动重传请求( a u t o m a t i cr e p e a t r e q u e s t ，a r q ) ”的机 制。它对错误纠正的方法是：丢弃已经接收的含有错误的数据包，向发送点请求 重新发送含有错误的数据包。解码端发现差错就立即给发送端发出重传请求，编 码端根据a r q 请求进行数据重发，解码端等到重传数据到来后再处理后续数据。 重传因为会引入反馈与数据往返的时间延迟，当信道波动较大时往返时延会产生 较大的抖动，因而在实时的传输应用中受到较大的约束【2 5 1 。 在停止一等待式a r q 中，数据报文发送完成之后，发送方等待接收方的状态报 告，如果状态报告报文发送成功，发送后续的数据报文，否则重传该报文。它的 工作原理如下：发送点对接收点发送数据包，然后等待接收点回复确认字符 ( a c k n o w l e d g ec h a r a c t e r ，a c k ) 并开始计时。在等待过程中，发送点停止发送 新的数据包。 当数据包没有成功被接收点接收时候，接收点不发送a c k 这样发送点在等 待一定时间后，重新发送数据包。反复以上步骤直到收到接收点发送的a c k 。发 送点的等待时间应当至少大于传输点数据包发送时间( 数据包容量除以发送点传 输速度) ，接收点a c k 接收时间( a c k 容量除以接收点传输速度) ；数据在连接 上的传送时间，接收点检验接收数据是否正确的时间之和。 在实际应用当中，等待时间是这个和的2 到3 倍。这个协议的缺点是较长的等 待时间导致低的数据传输速度。在低速传输时，对连接频道的利用率比较好，但 是在高速传输时，频道的利用率会显著下降。 为了克服停止等待a r q 协议长时间等待a c k 的缺点。连续a r q 协议会连续发 送一组数据包，然后再等待这些数据包的a c k 。 2 2 压缩域容错技术 压缩域的容错技术有两类方法：主要用于发送端的容错控制和主要在解码端 实现的差错掩盖【26 1 。本节主要研究编码端的容错机制。发送端即编码端，主要通 过码流中增加冗余降低差错传播达到容错效果，缓解数据的丢失，尽可能减少由 信息丢失造成的损失。 根据使用网络的不同，通常把编码端容错工具分为用于电路交换信道的容错 方法和用于分组交换信道的容错方法。传统标准中的容错工具包括重同步标示、 数据分割和数据恢复等三种【2 7 1 。但这些方法都是用来对付比特差错信道的，不适 7 机会网络中容错f 输机制的研究 用于基于分组交换的无线自组织网络。目前，适用于无线自组网的容错工具主要 有分层编码、多描述编码及交织编码等【2 引。 2 2 1 分层编码 分层编码( l a y e rc o d i n g ，l c ) 也称为可伸缩性编码，它是指将源信息编码成 一个基本层和一个或多个增强层，使用户具有不同的带宽适应能力。为了具有容 错性，在传输过程中l c 必须具有不对等保护的特性，基本层应该受到最高级别 的保护。例如，分配更可靠的信道，用更强的前向纠错码，或允许更多的重传1 2 引。 分层编码的最终目的是将传输的信息编码为一个可以单独解码的基本层码流 和一个可以在任何时刻中断的增强层码流，其中基本层码流适应于网络所能提供 的最低带宽，而增强层码流用来适配网络实时变动的可用带宽。 2 2 2 多描述编码 多描述编码( m u l t i p l ed e s c r i p t i o nc o d i n g ，m d c ) 是在压缩效率和抗误码性能 之间进行折衷考虑的容错方法。m d c 将信号源编码成几个相关且同等重要的子码 流，也称描述【3 0 】。任何单个的描述可以提供基本质量的信号，更多的描述提供更 高的质量。m d c 相对l c 有一个优点，它不需要网络单独提供一个可靠的子信道。 分层编码的基本层是至关重要的，如果失去基本层，剩下的其他比特流将毫 无用处，而m d c 中的多个描述分别通过多个独立的信道传送到接收端，这样，当 其中一个描述符中的某些帧受到损害时，可以利用其他描述符中未受损害的帧来 修复本描述符中受损的帧。因此即便是两个描述都遭受了分组丢失，只要这两个 描述遭受的分组丢失不是同时发生，它们仍然可以维持原始的信号概貌。 2 2 3 交织编码 交织编码( i n t e r l e a v i n g ) 的目的是使信道传输过程中突发产生的集中错误最 大限度的分散化【3 。在实际的通信系统中，嗓声干扰的影响往往是前后相关的， 从而导致发生的错误也具有较强的相关性。也就是说，当发生一个错误时，往往 波及后面的很多数据，导致一片数据都发生错误，这类错误称为突发差错。由于 这种突发性的存在，可能使得短暂时间内的丢包率超过了前向纠错( f o r w a r de r r o r c o r r e c t i o n ，f e c ) 所能纠正的范围。这样使得丢失的数据包无法完全恢复。而采 用交织编码，可以打乱码字比特之间的相关性，将信道传输过程中成群的突发差 错离散成随机差错，再用f e c 技术消除随机差错【32 1 。交织深度越大，则离散 度越大，抗突发差错能力也就越强。但交织深度越大，交织编码处理时间越 长，从而造成数据传输时延也增大，换言之，交织编码以时间为代价。 交织编码有两种类型：分组交织和卷积交织。分组交织又称为矩阵交织或块 交织。在这个过程中，通过编码后的码字序列被按行填入一个行为m 列为n 的矩阵， 如图2 1 所示。 8 t 稃硕 j 学位论文 按 行 输 入 按多读撼 c ：。霸j馥舻2 气o c 2 伊lc 毛扩： 气尊 e 舭：c _ 护： 气壤 图2 1 分组交织原理图 矩阵填满以后按列发出。同样，接收端的解交织器将接收到的信号按列填入 一个大小同样为m n 的矩阵，填满后按行读出，送往解码器进行正常解码【3 3 1 。 这样，信道中的连续突发错误被解交织器以m 个比特为周期进行分隔再送往解码 器，如果这m 个错误比特处于信道编码的纠错能力范围内，则达到了消除错误突 发的目的。 分组交织编码的算法如下：将i 个能纠t 个错的分组码( n ，k ) 中的码元比特排 列成i 行n 列的方阵。每个码元比特记作b ( i ，n ) 。交织前如果遇到连续j ( j t ) 个 比特的突发错误，则无法正确对出错码组进行纠错，因为对其中的连续两个码组 而言，错误数已远远大于纠错能力t 。交织后，总的比特数不变，但传输次序由原 来的b ( 1 ，1 ) ，b ( 1 ，2 ) ，b ( 1 ，3 ) b ( 1 ，n ) ，b ( 2 ，1 ) ，b ( 2 ，2 ) ， b ( 2 ，3 ) b ( 2 ，n ) b ( i ，1 ) ，b ( i ，2 ) ， b ( i ， 3 ) b p ，构造样本阵， 标准化变换，如公式( 3 3 ) 所示： 五j ；兰堕卫，i ；1 ，2 ，砧；j = 1 ，2 ，p 其中奶= 学，弓=其中巧2 ，勺2 墨，( 一奶) 2 以一1，得标准化阵z 。 ，昂) 0 n 个样 对样本阵元进行 ( 3 3 ) ( 2 ) 对标准化阵z 求相关系数矩阵，如公式( 3 4 ) 所示： 冗也忉= 鲁4 ， 1 3 机会网络中容错传输机制的研究 廿。广望掣 歹：1 ，2 ，卯 其中，5 盖f j = 1 ，z “ 。 ( 3 ) 解样本相关矩阵r 的特征方程l r 一屿l = 0 得p 个特征根，确定主成 分 按戳独铋确定m 能删8 5 地 九，j 一1 ，2 ，m ，解方程组r 6 = 九，6 得单位特征向量。 坤 ( 4 ) 将标准化后的指标变量转换为主成分，如公式( 3 5 ) 所示： = 考鳄，j = 1 ，2 ，m( 3 5 ) u l 称为第一主成分，观称为第二主成分，称为第p 主成分。 ( 5 ) 对m 个主成分进行综合评价 对m 个主成分进行加权求和，即得最终评价值，权数为每个主成分的方差贡 献率。 3 2 小波变换 小波分析是传统傅罩叶分析发展史上里程碑式的进展，作为一种新的数学工 具，被誉为是泛函分析、傅罩叶分析、样条分析、调和分析和数值分析的最完美 结合。其在图像处理及模式识别等领域有着重要的应用，包括图像融合、增强、 数据压缩、边缘检测、纹理分析等诸多方面。小波变换被认为是近年来在工具和 方法上的重大突破。 3 2 1 小波变换理论概述 小波的概念是由法国从事石油勘测信号处理的地球物理学家m o d e t 于l9 8 4 年 提出的【4 1 1 。1 9 8 6 年j a f f e r d ，l e m a v i e 和m e v e r 与从事信号处理的m a u a t 合作提出了 小波正交基的构造可纳入一个统一框架，引入多分辨分析的概念，统一了前入构 造的具体小波，并给出了多分辨分析构造正交小波基的一般化方法。m a l l a t 在b m t 和a d e l s o n 的塔式分解算法启发下，巧妙的将计算机视觉领域的尺度分析思想引入 小波分析研究了小波变换的离散化情况，并提出了相应的m a l l a t 算法。该算法在