（计算机应用技术专业论文）无线多跳网络的拓扑容错策略研究.pdf

福建师范大学林力伟硕士学位论文 ， ，张 一 摘要 a b s t r a c t a san e wk i n do fn e t w o r k , l e s sm u l t i - h o pn e t w o r k si sv e r yu s e f u la n di tc a n a p p l yi nm a n yf i l e ds u c ha sm i l i t a r y , e n v i r o n m e n t , m e d i c a l ，f a m i l ya n ds oo n f o r e x a m p l e ，w i r e l e s sa dh o cn e t w o r k ，w i r e l e s ss e n s o rn e t w o r ka n dw i r e l e s sm e s hn e t w o r k a r ea l lb e l o n gt o 骶l e s sm u l t i h o pn e t w o r k s s i n c e l e s sm u l t i h o pn e t w o r k si s l i m i t e db yp o w e r , c o m p u t ec a p a b i l i t y , s t o r a g ea n db a n d w i d t h , h o wt op r o l o n gt h el i f e t i m e o fn e t w o r ka n dg u a r a n t e et h er e l i a b l ed a t at r a n s m i s s i o na r es i g n i f i c a n tp r o b l e m s f i r s t l y ，t h et h e s i si n t r o d u c e dt h eb a s i cc o n e e p t s ，f e a t u r e s ，a p p l i c a t i o n s ，a n dr e s e a r c h i nt o p o l o g yf a u l t - t o l e r a n c es t u d ys t a t u sa n di n a d e q u a t e s e c o n d l y , i no r d e rt ob a l a n c et h e p o w e rc o n s u m i n gi nt h ew h o l en e t w o r k , w er e a d j u s tt h es i z eo fc l u s t e rt h r o u g ht h e d i f f e r e n c ep o w e rc o n s u m i n ga m o n gn e i g h b o rc l u s t e rh e a d ，s ot h a tc a l lb a l a n c ec l u s t e r h e a d 8p o w e rc o n s u m i n gm o r ec o m p l e t e l y a n daf a u l t - t o l e r a n c es c h e m ei sp r o p o s e dt o i m p r o v et h er o b u s t n e s so fn e t w o r k s t h e n ，a i m i n gt ot o l e r a n c et h el i n kf a u l t ，n e t w o r k c o d i n gi su s e di nt h el i n kf a u l t - t o l e r a n c es c h e m eb a s eo nt h ec l u s t e rm o d e li nt h ef j r s t s c h e m e ，a n dt h i sl i n kf a u l t - t o l e r a n c es c h e m ec o u l dn o tc a u s ea n yd a t at r a n s m i s s i o nd e l a y w ea n a l y z et h ev a l i d i t yo fn e t w o r kc o d i n gf o rl i n kf a u l t - t o l e r a n c ef r o mt h e o r e t i e a l l y c o m p a r e dt h i ss c h e m ew i mt r a d i t i o n a lf a u l t - t o l e r a n c es c h e m et h r o u g hs i m u l a t i o n t h i s s c h e m ec a l lr e d u c et h el o a do fn e t w o r k st h a ti sc a u s e db yf a u l t - t o l e r a n c e l a s t l y ，a i ma t m o r el i n kf a u l ti nt h en e t w o r ke s p e c i a l l yt h es i t u a t i o nt h a tn e t w o r kc a l lh a r d l yp r o v i d e e x t r at r a n s m i s s i o np a t ha n dr e q u i r eh i g hc o m m u n i c a t i o nq u a l i t y ，w ep r o p o s eam u l t i - p a t h f a u l t - t o l e r a n c es c h e m eb a s e d0 nn e t w o r kc o d i n g a n dt h e nw ev e r i f yt h ev a l i d i t yo ft h i s s c h e m ef r o mt h e o r e t i c a l l y k e y w o r d s ：w i r e l e s sm u l t i - h o p n e t w o r k s ；w i r e l e s s s e n s o r n e t w o r k ；t o p o l o g y o p t i m i z a t i o n ；f a u l tt o l e r a n c e ；n e t w o r kc o d i n g i 福建师范大学林力伟硕士学位论文 i v 中文文摘 中文文摘 无线多跳网络是近年来迅速发展和普遍重视的新型网络，它有传统无线网络无 法替代的优势，具有十分广阔的应用前景，它的存在和发展甚至会影响到第四代移 动通信网络( 4 g ) 。无线多跳网络可以实现人与人i 人与物、物与物之间通信，在 军事领域、商业领域、医疗、个人家庭、科研等诸多领域具有广阔的应用前景和极 高的应用价值。 网络的拓扑结构在网络中起着支撑网络的作用，它是网络协议运行、应用实现 的基石。由于无线多跳网络的特点，如信道质量较差、信号冲突严重、网络拓扑结 构动态变化、以及网络节点的能量和c p u 处理能力的局限性等，使网络无法保障可 靠的通信。因此如何保证可靠的通信、延长网络生存时间是无线多跳网络研究的重 点和热点。对于如何保障无线多跳网络可靠的通信、延长网络生存时间，对网络的 拓扑容错和优化是关键。 目前无线多跳网络的拓扑容错问题的研究中，较多的是采用网络拓扑控制，或 者增加额外辅助节点来优化网络拓扑结构，实现对拓扑的容错。通过改变网络的物 理和逻辑拓扑结构来优化网络的拓扑结构，使网络的拓扑结构更加健壮，在网络的 拓扑结构上设计一些路由算法，能够容忍其中的一部分节点或者链路发生故障而使 网络照样能正常运行。同时，网络编码的独特优势可以容忍网络中的节点或者链路 故障，保证信息的可靠传输，因此在无线多跳网络中加入网络编码策略可以提高网 络拓扑的鲁棒性。 本文的绪论中首先介绍了无线多跳网络的概念、分类、特点以及应用场景，并 且介绍了无线多跳网络在拓扑容错问题方面的一些研究方法，以及在这方面研究的 一些国内外研究现状。 分簇算法是无线多跳网络中实施分层路由所采用的重要方法，尤其是网络节点 受到能量和带宽的严重制约。如何合理、有效地利用分簇算法使得网络中节点的能 量分布趋于均匀，从而延长网络的生命周期，提高系统的整体性能和容错性。第一 章中，我们先介绍了无线传感器网络的分簇模型，网络采用非均匀分簇，每个簇成 员节点都属于两个簇，相邻簇的簇头之间能互相通信。“热区问题 是传感器网络 v 。_ 福建师范大学林力伟硕士学位论文 研究的重要问题。由于各个簇头的负载不同，在网络中会有“热区 ：在靠近汇聚 节点的簇头节点由于需要接收和转发其他簇头的数据，因此在靠近汇聚节点的簇头 节点能量消耗会比其他的一些簇头节点快而过快死亡，外面的数据无法传到汇聚节 点，网络出现断层从而使网络过早死亡，这就是“热区问题”。由于网络的节点的 能耗大部分是消耗在接收和发送数据上，因此我们在网络运行中，利用相邻簇的簇 头能耗差异，调整簇的规模，使负载大的簇头节点的簇规模减小，将簇成员转移到 相邻的其他簇中来进一步平衡网络中的簇头能耗，进而延长网络的生存时间。同时 由于簇头在网络中扮演的角色更加重要，在第一章中的分簇模型每个节点都属于两 个簇，如果网络中某个簇头出现故障，其簇成员就归向另一个簇，以保证网络的正 常运行，提高网络的容错性。用v i s u a lc + + 6 0 构建仿真系统，通过仿真表明，该 策略能有效地延长网络的生存时间。 在第一章的分簇网络模型基础上，第二章引入了网络编码思想，来实现对网络 链路的容错。同样每个普通的传感器节点可以直接和两个簇头通信，其所属簇的簇 头为簇头节点，另一个为副簇头节点。首先每个簇的簇头对其簇成员根据它们所属 的副簇头来分组，每组中簇成员的副簇头均不同，给相同分组的簇成员赋予一个网 络编码编号，不同编码分组的编码编号不同。网络运行时，簇成员向其簇头和副簇 头组播数据。簇头根据簇成员的分组情况，把相同编码编号分组的成员节点发送过 来的数据进行编码后再转发至汇聚节点。通过理论分析可以得出改策略可以容忍簇 内任意一条链路出错，而接收方仍然可以恢复出原始数据。最后，用v i s u a lc + + 6 o 构建仿真系统，并对算法进行性能分析与评估。仿真表明，与传统的1 + 1 数据 保护模式的容错策略相比，在相同容错能力的前提下，该策略可以大大较少了网络 中传输的数据量，并且不增加网络数据的传输延时。 第二章中的策略可以容忍任意一条簇成员与簇头之间的链路出错。但对真实的 网络来说，尤其是对链路质量较差的情况下( 例如工作在恶劣环境下的无线多跳网 络) ，仅能容许一条链路出错是不够的。在第三章中，我们设计了网络编码策略来容 忍数据传输对多条路径故障的容错性，并且不需要额外的数据传输路径。我们采用 线性网络编码，其计算复杂度不高，适用于网络节点资源有限的无线多跳网络，并 且证明了编码策略的正确性和可行性。与传统的数据备份多路径发送策略相比，基 于网络编码的路径容错策略可以达到较好的性能优势：1 、相同的数据包发送轮数达 v i k 文 福建师范大学林力伟硕士学位论文 到较高的容错能力；2 、在相同的容错要求的情况下，需要发送的数据包的轮数较少， 从而减少网络中传输的数据包数量来减少网络节点的能耗。并且该策略无需添加额 外的传输路径，在现有的路径情况下就可以实现对多跳路径的容错。因此该策略适 用于无线多跳网络，尤其能很好地应用与节点较稀疏、网络的链路质量较差的情况。 第四章对本论文的研究成果进行了总结，并对下一步的研究工作提出了一些展 望。 v 福建师范大学林力伟硕士学位论文 v i h 谤p x 。，采 k _ ， h j ： - 飘 目录 目录 中文摘要i a b s t r a c t i 】 i 中文文摘 目录i x 绪论1 第一节无线多跳网络简介1 一基本榜e 念1 二无线多跳网络的特点。3 三无线多跳网络的应用5 第二节无线多跳网络拓扑容错策略研究概况6 第三节课题来源及内容安排9 第一章能量均衡的无线传感器网络容错分簇优化策略1 1 第一节无线传感器网络分簇容错优化研究背景1 1 第二节网络模型与问题描述。1 2 一 一网络模型1 2 。 二问题描述一1 3 第三节构建路由主干网1 3 一网络分簇- 1 3 - 二节点加入簇。1 4 三簇问路由协议- 1 4 - 第四节簇的优化调整。一1 5 一 一簇结构优化调整。- 1 5 一 二簇结构优化调整分析1 6 三容错机制- 1 6 第五节仿真及分析。- 1 6 - 第六节本章小结1 8 第二章基于网络编码的分簇传感器网络链路容错策略2 1 福建师范大学林力伟硕士学位论文 第一节相关研究工作2 1 第二节模型假设及编码容错策略2 2 一网络模型2 2 二编码算法及链路容错思想2 3 第三节数据编码及解码2 4 。 一采用的数据结构2 4 二编码过程。2 4 三解码策略2 5 第四节性能分析2 7 一理论分析。2 7 二仿真分析2 9 第五节本章小结3 0 第三章基于网络编码的无线多跳网络多条路径容错策略。3 3 第一节相关研究工作：3 3 第二节网络模型及容错编码发送协议3 4 一网络模型。3 4 二问题描述3 4 三容错数据发送协议。3 5 四解码策略3 7 第三节策略分析3 7 第四节问题扩展3 9 第五节策略性能分析4 0 第六节本章小结。- 4 2 第四章结论。一4 5 - 第一节本文工作总结。4 5 第二节今后工作展望一4 6 - 参考文献。- 4 9 一 攻读学位期间承担的科研任务与主要成果。- 5 5 - 鸳贮谢。- 5 7 一 个人简历一5 9 x l 绪论 绪论 第一节无线多跳网络简介 传统的移动通信技术一般都是集中式控制的，它们需要通过_ 些固定的基础设 施才能工作，而像战争、抗震救灾这类特殊的场合没有基础设施的支持，传统的移 动通信系统无法运行。无线多跳网络( m u l t i - h o pw i r e l e s sn e t w o r k ) 技术【l 】，作为移 动通信的一个重要分支，无需中心支持，组网方便迅速，可以很好地满足这类特殊 场合的需要，在军事、民用、商业、科研等领域具有广阔的应用前景【】，无线传感 器网络，无线自组网，无线m e s h 网等都是无线多跳网络的典型应用。近年来，有 学者甚至认为无线多跳网络很可能会影响第四代移动通信( 4 g ) 网络技术【4 】。无线 多跳网络的发展应用会使得人与人之间、人和物之间以及物与物之间的通信交互更 加方便和快捷。 一基本概念 与传统的无线通信网络相比，无线多跳网络最主要的的特点是源节点到目的节 点之间的典型路径是由多跳组成的，无须固定基础设施的支持，网络中的节点可以 是源节点和目的节点来发送和接收数据，也可以充当路由器节点转发数据的。如图 o 1 所示，a 、b 、c 、d 、e 、f 、g 、b i 为网络中的节点，图中的双箭头连线表示节 点间可以直接通信。例如当f 节点h 节点要通信( 发送数据) 时，由于f 节点与h 节点在彼此的信号覆盖范围之外，无法直接通信，它们根据图中红色的路径，通过 中问节点d 、b 、g 节点转发数据。 无线a dh o e 网络【5 1 、无线传感器网络【6 - 7 1 ( w s n ，w t r e l e s ss e n s o rn e t w o r k ) 以 及无线m e s h 网络( w m n ，w i r e l e s sm e s hn 幽v o r k s ) 【8 彤1 是无线多跳网络的典型应用。 随着社会的进步，传统的无线通信网络无法满足人们日益增长的通信需求，无线a d h o e 网络、无线传感器网络和无线m e s h 网络可以满足人们多方面的通信需求，他 们是现有无线通信网络的一个重要补充，正影响着通信技术的发展方向。 a dh o c 网络【1 1 也叫“自组网”，如图o 2 所示，组网不需要预先假设的通信基础 设置，仅依靠a dh o e 节点就可以在任意时刻、任意地点方便迅速地把通信网络构 建起来。只要整个网络保持连通，网络中的节点就可以与其他节点通信。 福建师范大学林力伟硕士学位论文 图o 1 无线多跳网络示意图 f i g u r e0 - 1e x a m p l eo f m u l t i - h o pw i r e l e s sn e t w o r k s 图0 - 2 典型的a dh o c 网络结构 f i g u r e0 - 2t h ec l a s s i c a la r c h i t e c t u r ea dh o cn e t w o r k s 无线传感网络【2 】是一种综合了传感器、低功耗通信以及微机电等技术的网络。 在无线传感器网络中，传感器节点由体积小、成本低、靠电池供电。传感器网络的 任务就是每个节点采集、感知并分析获得的传感数据，再发送到数据聚合节点( s i n k 节点) 。如图o 3 所示，一般来说无线传感器网络是在传感区域，布置由大量的传感 器节点，节点与节点之间以a dh o c 方式组成的网络。 无线m e s h 网络( w i r e l e s sm e s hn e t w o r k ，w m n ) ，也叫无线网状网和无线网格网 【3 】，如图0 4 所示。它吸收了无线局域网和无线自组网的优点，可以和多种宽带无 线接入技术以及3 g 移动通信等技术相结合，支持多点对多点的网状结构，组成一 个含有多跳无线链路，具有自组织、自修复和节点自我管理等特点的无线网状网络。 f 一 h a 绪论 传感区域传感器节点 图0 3 传感器网络体系结构 f i g u r e0 - 3s e n s o rn e t w o r k ss 饥l c t u r e ，；，：o ：。j p ，：名w i r e l e s s m e s h c ! e n t s 一，：。一，：。：i ：，j ：一i 。： 图0 4 无线m e s h 网络结构图 f i g u r e0 - 4w i r e l e s sm e s hn e t w o r k ss t r u c t u r e 二无线多跳网络的特点 无线多跳网络无中心、组网方式灵活，可以随时随地以任意的方式组网。这样 的网络是自组织的( s e l f - o r g a n i z i n g ) 、自生成的( s e l f - c r e a t i n g ) 和自管理的 ( s e l f - a d m i n i s t e r i n g ) 。虽然这三种网络均是无线多跳网络，但它们有各自不同的产 生背景和特点。 无线多跳网络的共同特点： 1 ) 多跳路由：由于节点的发射功率和能量有限，当目的节点在源节点的信号覆 嚣 福建师范大学林力伟硕士学位论文 盖范围之外时，源节点和目的节点之间的信息传送需要网络中其他节点的协 作，采用多跳传输，节点既可以接收数据，也可以转发数据。同时，采用多 跳路由也可以降低节点的发送功率，降低节点的能耗，延长网络的生存时间。 但由于数据传输需要经过多跳，路径上任意一个节点出现故障都会导致数据 丢失，因此多跳路由也增加了数据不可靠传输的概率。 2 ) 节点能量和计算能力有限：网络中节点的能量一般是采用电池供电，能源受 限、c p u 的计算处理能力也较低。节点资源的限制会导致网络中一些通信链 路的不稳定，数据传输可能无法正确到达目的节点。因此如何降低节点的能 耗、延长网络生存时间，提高数据传输鲁棒性是非常重要的问题。 3 ) 动态拓扑：在无线多跳网络中节点具有移动性，节点也可以随时关闭电台或 者调整发射功率，在加上无线信道互相干扰，以及受其他外界因素的影响， 网络的拓扑会随时可能发生变化。节点的离开、加入、死亡、睡眠和唤醒也 都会造成拓扑变化。动态的拓扑结构同样会导致数据传输的不稳定性，对拓 扑的管理，因此设计出适应动态拓扑网络的路由协议显得十分重要。 4 ) 组网方式灵活：无线多跳网络具有独立组网的能力，节点可以随时加入或离 开网络，不会影响整个网络的运行。当网络节点离开或者死亡时，可以通过 增加新节点或者寻找替代节点保证网络正常运行，因此组网的灵活性便于网 络的“修复”。 5 ) 网络鲁棒性较强：多跳无线网络结构灵活，具有较好的网络连通性和容错能 力。节点的加入和离开无需依赖某些专门的节点来进行组织控制，它允许节 点发生故障，加入或者离开。任意节点的故障不会影响到整个网络的运行。 但同时三种网络也具有其自身的特点： 1 ) 产生的背景及应用场景不同：无线a dh o c 网络是起源于军事应用，用于通 信。无线传感器网络主要是以检测数据采集，无线m e s h 网络可以看成是商 业版的无线a dh o c 网络，用于i n t e r a c t 的补充，为用户提供无线接入服务。 2 ) 业务流不同：无线a dh o c 网络主要是网络中的任意节点一对一之间互相通 信；无线传感器网络是以数据为中心，网络中的通信流主要是传感器节点与 s i n k 节点之间的通信；无线m e s h 网络主要用于商业领域，主要是网络中节 点与i n t e m e t 之间的数据业务来往。在通信容错方面，无线a dh o c 网络主要 是考虑网络中节点之间的可靠通信；无线传感器网络主要是考虑传感器节点 ，蕊j ，；吲。 ：j _ l _ ：，；，社 绪论 与汇聚节点( s i n k ) 之间的可靠通信：无线m e s h 网络主要看通信业务流， 一般来讲，节点与节点之间，节点与网关之间的可靠通信都要考虑。 3 ) 节点密度不同：无线传感器节点体积小，功率低，节点的数量级通常为几百 或者几千，有的甚至上万，节点密度远大于无线a dh o e 网络和无线m e s h 网络。无线a dh o c 网络节点可以任意移动，网络节点一般不会聚集在一起； 无线m e s h 网络中网络节点的功率较大，且节点一般为静态或者弱移动性， 某一块区域如果节点数量太多容易造成网络堵塞。 4 ) 节点资源限制性不同：无线传感器网络与另外两种网络相比，节点的处理能 力、计算能力更差，存储量更小，通信距离更短，一般只有几十米，甚至更 短。 5 ) 网络拓扑稳定性不同：无线传感器网络节点具有弱移动性，其网络拓扑结构 相对比较稳定，无线a dh o c 网络节点可以以任意速度移动，无线m e s h 网络 节点移动性取决于节点的类型，m e s h 网络网关和路由器的移动性一般较低， 而客户端节点可以是静态的，也可以是任意移动的节点。 三种网络存在不同的特点，其对容错的要求以及容错策略的设计也不完全相同， 根据具体的网络的实际应用，设计不同的容错策略。 三无线多跳网络的应用 随着社会的发展，人们对各种各样的通信需求越来越多，无线多跳网络的发展 可以弥补传统无线通信网络的不足，具有非常广阔的应用前景。 1 )军事应用：无线a dh o e 网络本身就起源于战争环境下数据通信中的应 用研究。无线传感器网络低成本、自组织、节点密度大、容错能力强， 非常适合应用于恶劣的战场环境中，例如侦查敌方动静、战场实时监督、 战场损失评估等。 2 )紧急突发事件：一些灾害性的紧急突发事件，例如地震、水灾、火灾、 停电以及其他灾害性突发事件，将会导致网络基站等通信基础设施无法 工作，这种情况下可以组建一个临时的自组网络( 即a dh o c 网络) 来 帮助抢救和抢修人员完成通信工作。 3 )环境检测：无线传感器网络可以为研究人员方便地获取野外随机性的研 究数据，也可以实现对生态环境【1 6 】、生物多样性【1 7 1 、森林火情、河道水 - 福建师范大学林力伟硕士学位论文 4 ) 5 ) 文【1 8 】等监控以及水灾预警【1 9 】等作用。 个人家庭应用：无线传感器网络可以实现家居工作环境智能化【2 0 】，如在 家用电器里装置传感器节点，连接i n t e m e t ，用户就可以非常方便地本地 或远程控制管理家用电器；通过a dh o c 网络可以构建虚拟教室和讨论 组等移动对等应用。 商业应用：基于传感器网络技术的物联ne 2 1 - 2 2 1 就是为了把任何物品与互 联网连接起来，进行信息交换和通讯，以实现智能化识别、定位、 跟踪、监控和管理。无线m e s h 网络通过“最后一公里”的无线接入方式 为用户提供无线接入服务，在商业上可以大大缓解用户业务与系统资源 之间的矛盾1 3 j 。 第二节无线多跳网络拓扑容错策略研究概况 网络的容错能力是无线多跳网络研究的热点问题。由于无线多跳网络的广阔应 用前景，网络承载越来越多的应用和服务时，网络的性能以及故障将产生巨大的影响 将是巨大的，所以网络的容错能力变得十分现实和重要。 数据通信是计算机网络最主要目的，如何保证可靠的通信一直以来都是计算机 网络领域研究的重点，网络系统的构建和网络的高可靠设计是系统中非常重要的环 节。拓扑结构的好坏会直接影响到网络节点的能量消耗，也会影响到网络的总体开 销和生存时间，同时对节点间的通信干扰情况也有影响；网络的拓扑结构为路由协 议运行提供基础。无线多跳网络拓扑的容错能力是无线多跳网络容错问题的一个重 要方面。网络数据的传递需要依托于网络的拓扑结构，网络数据的正确传递需要网 络对拓扑的具有容错能力。如图0 5 所示，无线多跳网络在不同的抽象层具有不同 的技术，每层上的技术策略都可以提高网络的拓扑容错的能力。硬件容错保障了网 络正确运行，是增强网络拓扑容错能力的基础；链路层上主要的容错技术包含对容 错覆盖的讨论以及对容错拓扑控制的研究等，使网络的拓扑结构更加健壮；网络层 的容错研究主要是设计具有容错能力的路由算法，保障数据的正确传递，从而提高 数据传输对网络拓扑的容错性；在传输层建立故障检测与隔离机制，能够较早地发现 并隔离故障节点，从而可以调整网络运行的拓扑结构。在应用层对数据进行融合，发 送方把数据进行编码发送，接收方对数据进行解码操作，可以容忍网络中的部分拓 扑失效、出错；增强网络的拓扑容错能力跨越了不同的网络抽象层。 绪论 应用层数据融合、编码、解码 增 强 传输层故障检测与隔离 网 络 的 网络层容错路由 拓 扑 容 链路层网络覆盖与拓扑控制 错 能 l 力 物理层硬件容错 网络抽象结构层无线多跳网络每层相关技术 图0 5 无线多跳网络抽象层及其相关技术 f i g u r eo - 5a b s t r a c tl a y e ro fw i r e l e s sm u l t i - h o pn e t w o r k sa n di t st e c h n o l o g yi ne v e r yl a y e r 图0 - 6 无线多跳网络拓扑容错技术 f i g u r e0 - 6t o p o l o g yf a u r t o l e r a n c es c h e m ei nw i r e l e s sm u k i - h o pn e t w o r k s 如图o 6 所示，提高无线多跳网络拓扑容错能力可以通过以下几种方法：1 ) 拓 扑控制；2 ) 网络编码；3 ) 其他策略如小世界理论等。拓扑控制是无线多跳网络研 福建师范大学林力伟硕士学位论文 一， 究中的核心问题之一，可分为物理拓扑控制( 例如节点功率控制等改变网络物理拓 扑结构) 和逻辑拓扑控制( 例如分簇策略，改变网络的逻辑拓扑结构) 。网络编码是 一种融合编码和路由的信息交换技术，在传统存储转发的路由方法基础上，网络中 的节点可以对接收的数据包进行编码融合和解码，通过计算代价来提升网络的性能。 结合网络编码思想，可以使网络对拓扑具有更强的容错性。 在平面结构网络中，主要是控制节点的功率，使源节点和目的节点之间有k 连 通的路径 2 3 - 3 1 】，或者通过放置节点使网络达到k 连通的容错要求 3 2 - 3 5 】。 当网络规模增大，节点数量增多的时候，平面结构的路由维护和网络管理需要 消耗过多的带宽，因此网络的可扩充性较差1 3 6 。分簇结构可以克服平面结构可扩充 性差的缺点，通过增加簇的个数或网络的级数能够增加网络的容量。对网络节点进 行拓扑控制改变了真实的物理拓扑结构，而与分簇结合的拓扑容错研究是从网络节 点的逻辑关系上来改变网络中节点的逻辑拓扑结构。在分簇结构的无线多跳网络中， 作为簇头节点的网关节点负责接收本簇内部传感器节点采集的数据，并通过与其他 网关节点的多跳通信最终将数据传送给接收节点。在分簇结构中，网关节点的选取 和放置是容错研究的主要内容之一。 在分簇的无线传感器网络中会形成“热区”效应：在无线传感器网络中，网络在 分成各个簇结构之后，簇成员与簇头之间为了更加方便调度成员的数据传输，可以 采用单跳的方式通信；当簇头向汇聚点进行长距离数据传输时，特别是在大规模网 络传输中，采用多跳路由的方式能显著降低能量消耗。为了实现节点能量的负载均 衡，簇头应尽可能均匀地分布在整个网络中。但是在每一轮中，由于靠近基站的簇 首承担了额外的数据转发任务，易造成节点过早能量耗尽而失效，降低网络的生存 时间。由于业务流的不同( 无线传感器网络是多对一通信模式，a dh o e 网络则更强 调网络中节点对等通信模式) ，传统的a dh o c 网络中的均匀分簇策略无法解决无线 传感器网络中能耗不均衡的“热区”问题。目前已经提出很多策略来解决“热区”问题 【3 7 羽】。但这些策略中没有考虑到簇头容错性问题，分簇传感器网络中，簇头担任着 重要的角色，簇头失效意味着整个簇的信息都无法采集，对网络会产生巨大影响。 为确保簇头节点的安全性，也有相应的一些策略，例j t l ：l - 簇头备份和轮换机制【4 0 4 1 】， 但这些簇头容错机制没有考虑到网络中的能量平衡问题。因此在传感器网络中，既 要考虑到网络的容错性，又要考虑到这个网络的能耗均衡。 在实际应用中，无线多跳网络的节点和链路经常会失效，从而影响网络的鲁棒 绪论 性。传统的网络链接恢复方法是重新路由。但是，采用网络编码可以弱化由于节点 离开或者网络的链路失效导致的其他节点获取数据的不利影响，从而提高整个网络 的容错性和鲁棒性【4 2 】。尤其是当无线多跳网络的拓扑结构不能改变或者很难改变的 情况下，网络编码可以进一步提高网络对拓扑的容错性。 4 3 1 针对传感器网络提出了 一种结合分布式源编码和网络编码的优化算法，目的是用来提高传感器网络的容错 性和可靠性。5 1 利用网络编码提高信息传送对链路失效的容错性，但对网络的拓 扑结构有一定的要求。 相对于传统的数据传输容错策略，例如1 + 1 数据容错需要在网络中传输的信息 量增加1 倍，而1 ：l 数据备份容错策略虽然会减少网络中的数据传输量，但会增加 因数据丢失而造成的重传的网络延时。利用网络编码与容错结合，可以在容错与延 时得到很好的折衷。 4 6 4 7 】将网络编码与多路径传输结合，中间节点对传输的数据再 编码转发，可以提高数据传输的可靠性。但这些策略都是依概率恢复数据，很难保 证1 0 0 恢复出原始数据，当数据量不够恢复出数据时需要往前再申请数据直至有 足够的数据量为止，尤其是源节点与目的节点路径数较少时会造成较大的延时。 第三节课题来源及内容安排 、掣 尽管无线多跳网络的应用前景非常广阔，但相对于传统网络而言，很多技术还 处于起步阶段，存在诸多不足之处，如何保证网络可靠的通信是无线多跳网络研究 的重点之一。由于无线多跳网络节点的能耗、功率、体积以及工作环境的限制和影 响，数据通信无法得到很好的保障。本文主要从优化无线多跳网络拓扑结构、实现 无线多跳网络数据传输对拓扑容错性方面展开研究。 本文的课题来源于如下基金项目：国家自然科学基金f n o 6 0 5 0 2 0 4 7 ) “安全和能 量感知的可编程复杂动态自组织网络研究”、福建省教育厅重点项目 甜o j a 0 7 0 3 0 ) “基于可信分簇的无线传感器网络安全关键技术”、福建省自然科学基 金项目( n o 2 0 0 8 j 0 0 1 4 ) “基于容错分簇和跨层协作的传感器网络安全匿名路由技术” 和福建省高等学校新世纪优秀人才支持计划项目 o f m 0 3 5 ) “无线多跳网络安全 技术”等。 本文的主要工作和内容安排如下： 首先简单介绍了无线多跳网络的基本概念、特点及其应用领域，阐述了无线多 跳网络拓扑容错优化技术，以及无线多跳网络拓扑容错优化的研究现状。 第一章是在分簇传感器网络拓扑结构的基础上，利用相邻簇之间的能量消耗差 福建师范大学林力伟硕士学位论文 、， 、h h 异来调整簇的规模，进一步平衡网络中簇头的能量消耗，并增加了簇头容错策略， 并对其进行了仿真分析和比较。 第二章是在第一章中传感器网络初始分簇模型的基础上，引入网络编码策略， 簇头对簇内成员进行分组，依据分组号对簇成员的信息进行编码发送。通过理论分 析和仿真表明，通过网络编码转发数据实现容错与传统的备份数据容错方案相比可 以大大减少网络中的数据量传送，节省网络的能耗，并且不增加信息传输的延时， 编码计算复杂度低，适用于对无线传感器网络的能耗有较严格要求的应用。 第三章利用网络编码策略，提出了无线多跳网络中多路径容错策略。该策略中 的网络编码是线性编码，计算复杂度较低，能构实现同时对多跳路径的容错，适合 用于通信质量较差的网络应用环境。 第四章对本论文的研究成果进行了总结，并对下一步的研究工作提出了一些展 望。 第一章能量均衡的无线传感器网络容错分簇优化策略 第一章能量均衡的无线传感器网络容错分簇优化策略 无线传感器网络( w s n ) 中，传感器节点通常是由能量十分有限的电池供电，而且 在部署后难以二次补充能量，因此传感器网络存在严重的能量约束问题。如何提高能 量效率成为传感器网络研究的重大问题 4 8 - 4 9 1 。 传感器网络节点绝大部分能量都消耗在通信模块_ l ：t s 0 1 。一些网络节点距离汇聚 点的距离较远，如果直接采用节点与汇聚点的单跳通信，网络节点需要很大的功率 来发送数据，这样会极大地消耗节点的能量。已有研究【5 l 】表明在节点与汇聚点之间 采取多跳的方式进行通信更能降低节点的通信的能量消耗。然而这种做法带来了一 个能量消耗不均衡的“热区”问题，即在传感器网络的多对一通信模式中，靠近汇聚 节点的网络节点需要再转发其他簇的数据，节点能量过快消耗至死亡，造成网络分 割，降低网络生存时间。 第一节无线传感器网络分簇容错优化研究背景 由于无线传感器网络规模比较大，基于分簇的层次式拓扑管理结构可以有效地 提高网络的可扩展性。在以分簇方式组织的传感器网络中，传感器节点的角色分为 簇头和簇成员两种。簇头作为簇的中心负责簇结构的建立，收集簇成员的数据，经融合 处理后发送给汇聚点。由于簇首距离汇聚点的距离较远，簇头与汇聚节点之间的通 信采用多跳传输带来的能量消耗不均衡的“热区 问题，造成网络分割，降低网络 生存时间。 针对传感器网络簇头能量消耗平衡问题，目前已经提出了多种分簇策略1 5 2 5 4 来 减少能耗，这些研究主要集中于均衡簇成员节点之间的能量消耗，没有考虑到簇头间 的能量消耗均衡问题。划分子簇的方法【5 5 j 贝i j 是在簇中继续划分多级子簇来减小簇头 节点的能量消耗，该策略在子簇头数据融合度比较高的情况下可以较好地减少簇头 节点的能耗，但如果子簇头也只是单纯转发簇成员数据，则不能降低簇头节点的能 耗，也无法解决热区问题。由于无线传感器网络与无线a dh o e 网络业务流的不同， 无线a dh o e 网络中的均匀分簇的思想会加剧无线传感器网络的能耗不均衡问题， 因此在无线传感器网络中适合采用非均匀分簇策略。e e u c 明采用竞争半径的不同， 让网络进行非均匀分簇来平衡各个簇之间的能耗，较好地解决“热区”问题。但e e u c 在网络节点分布不均匀的情况下可能还会使靠近汇聚节点的一些簇负载过大而使簇 福建师范大学林力伟硕士学位论文 头节点过早死亡，降低网络生存时间。 为了更好地解决“热区 问题，本章提出了非均匀容错分簇优化( u n e v e n f a u l t - t o l e r a n c ec l u s t e ro p t i m i z e ，简称u f t c o ) 策略，其核心思想是采用非均匀分簇思想， 在网络运行过程中调整簇的规模，更好地平衡簇头之间的能量消耗，并引入了容错 机制提高网络对簇头节点的容错性。 第二节网络模型与问题描述 一网络模型 网络以分簇的形式组织节点，网络中有三种节点：簇头( c l u s t e rh e a d ，简称c h ) 、 普通节点和汇聚( d s ) 节点。c h 节点和普通节点的配置相同，其发射功率以及节 点的能量均有限，本策略中认为d s 节点发射功率和能量是无限的。 考虑由n 个随机部署的传感器节点形成的网络，节点集合为 s = s l ，j 2 ，- - ，讲) ，isl _ ，其应用场景为周期性的数据收集。本策略假设： ( 1 ) 数据汇聚点位于一个方形观测区域的外侧边缘且位置固定。传感器节点部 署后位置基本不发生移动。 ( 2 ) 所有节点都是同构的，具备数据融合的功能，每个节点都有一个唯一的标识 ( i d ) 。 ( 3 ) 根据接收者的距离远近，节点可以自由调整其发射功率以节约能量消耗。节 点的发射功率范围有限，最大通信半径为r a n g e 。 ( 4 ) 链路是对称的。若已知对方发射功率，节点可以根据接收信号的强度计算出 发送者到自己的近似距离。 本策略中采用的无线通信能量消耗模型描述如下：节点发射k 比特的数据到距 离为d 的位置，消耗的能量为： 西( 后，d ) = + 后删2 ( d r a n g e ) ( 1 - 1 ) 节点接收k 比特数据的能量消耗为： e r s (