（信号与信息处理专业论文）协作通信网络的伙伴选择改进算法.pdf

协作通信网络的伙伴选择改进算法 摘要 在协作无线通信网络中，伙伴选择问题是其实际应用中的重要步骤， 也是影响通信质量的重要因素。本文在总结现有伙伴选择算法的基础上， 针对两种具体应用场景，提出了两种新的改进伙伴选择算法。 首先，针对无线传感器协作通信网络，分析了该场景下协作伙伴选 择方法中的中继节点抢占问题，提出一种中继复用的分布式改进协作伙 伴选择方法。建立允许协作链路间复用中继节点的系统模型，运用拉格 朗日乘子法优化中继节点上功率分配最大化协作增益，分析复用中继能 获得误码率增益和功率增益的条件和功率分配方法。理论分析和仿真结 果表明，允许中继通过功率分配进行复用的新伙伴选择方案能降低无线 传感器网络的系统总功率消耗，并使更多链路的误码率需求得到满足。 其次，针对基于i d m a 叠加调制的协作蜂窝网。引入i d m a 叠加调 制可以提高系统的时隙利用率，获得更大的协作增益。但叠加调制要求 两个源节点必须互为中继，已有的伙伴选择策略不能很好的满足这一要 求。本文推导了高信噪比下基于i d m a 叠加调制的t d m a 半双工协作通 信网络的中断概率表达式，分析了采用i d m a 叠加调制能获取增益的条 件，针对基于i d m a 叠加调制的协作通信网络提出了最优的集中式改进 伙伴选择策略和次优的分布式改进伙伴选择策略。仿真结果显示，改进 的伙伴选择算法可以有效地降低网络的平均中断概率。 关键字协作分集；伙伴选择；分配算法 i 啤r o v e dp ar t n e rs e l e c t l 0 nm e t h o df o r c o o p e r a t i v en e t w o r k a bs t r a c t i nc o o p e r a t i v ec o m m u n i c a t i o n ，p a r t n e rs e l e c t i o ni sa ni m p o r t a n ts t 印i n r e a l i z i n gc o o p e r a t i v ep r o t o c o la n dak e yf a c t o rw h i c ha f f e c tt h ep e r f o r m a n c e o ft h es y s t e m i nt h i sp a p e r , t h ee x i s t i n gp a r t n e rs e l e c t i o na l g o r i t h m sw e r e s u m m a r i z e d b a s e do nt h ee x i s t i n ga l g o r i t h m s ，t w on e wi m p r o v e dp a r t n e r s e l e c t i o na l g o r i t h m sw e r ep r o p o s e df o rt w or e a ls c e n a r i o so fc o o p e r a t i v e w i r e l e s sn e t w o r k f i r s t ，f o rc o o p e r a t i v ew i r e l e s ss e n s o rn e t w o r k ，r e l a yn o d ec o m p e t i t i o n p r o b l e mu n d e rt h i ss c e n a r i ow a sa n a l y z e da n da d i s t r i b u t e dr e l a ym u l t i p l e x i n g p a r t n e rs e l e c t i o nm e t h o dw a sp r o m o t e df o rs o l v i n gt h i sp r o b l e m a s y s t e m m o d e lw h i c ha l l o w sc o o p e r a t i v e1 i n k st om u l t i p l e xt h er e l a yn o d ew a sg i v e n m a x i m u mc o o p e r a t i o ng a i nw a so b t a i n e db yo p t i m i z i n gr e l a yn o d e sp o w e r a l l o c a t i o nw i t h l a g r a n g em e t h o d t h ec o n d i t i o n a n do p t i m u mp o w e r a l l o c a t i o nm e t h o dw h e ns y s t e mc a ng e tb e rg a i no rp o w e rg a i nw a sa n a l y z e d t h e o r ya n a l y s i sa n ds i m u l a t i o nr e s u l t sp r o v et h a tt h en e w m e t h o dc a ns a t i s f y t h eb e r r e q u i r e m e n to f l i n k sb e t t e ra n dr e d u c et o t a lp o w e rc o n s u m p t i o n t h e n e f f e c tw a ss p e n to nac o o p e r a t i v ec e l l u l a rn e t w o r kw h e r ei d m a s u p e r p o s i t i o nm o d u l a t i o nw a sa p p l i e d i ti s c o n v i n c e dt h a ts u p e r p o s i t i o n m o d u l a t i o nc a ni m p r o v et i m es l o te f f i c i e n c y h o w e v e r , t h ea p p l i c a t i o no f s u p e r p o s i t i o nm o d u l a t i o nh a sb r o u g h tn e wp r o b l e m sf o rp a r t n e rs e l e c t i o ni na c o o p e r a t i v ec e l l u l a rn e t w o r k i nt h i sp a p e r , f i r s tt h ee x p r e s s i o no fo u t a g e p r o b a b i l i t y f o rac o o p e r a t i v en e t w o r kb a s e do ni d m as u p e r p o s i t i o n m o d u l a t i o nw a sd e r i v e d t h e nt h ec o n d i t i o nw h e ni d m as u p e r p o s i t i o n m o d u l a t i o nc o u l d o u t p e r f o r m d i r e c tt r a n s m i s s i o nw a sa n a l y z e d b y c h a n g i n ge x i s t i n go u t a g eg a i nm a t r i xi n t oas y m m e t r i cn e w o n ea n da p p l y i n g h u n g a r ya n dw l fa l g o r i t h m ，ac e n t r a l i z e do p t i m a la n dad i s t r i b u t e d s u b - o p t i m a lp a r t n e rs e l e c t i o ns t r a t e g i e sw e r ep r o p o s e df o rs u p e r p o s i t i o n m o d u l a t i o nc m ac e l l u l a rn e t w o r kb a s eo nt h em o d if i e d g a i n m a t r i x s i m u l a t i o nr e s u l t ss h o w st h a tt h ep r o p o s e dp a r t n e rs e l e c t i o ns t r a t e g i e sc o u l d r e d u c et h ea v e r a g eo u t a g eo ft h en e t w o r k e f f e c t i v e l y k e y w o r d ：c o o p e r a t i v ed i v e r s i t y ；p a r t n e rs e l e c t i o n ；a l l o c a t i o na l g o r i t h m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丞i 童纽 日期：! ：2 ：! ：! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以 公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇 编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名： 盈f 鱼垒日期：兰：翌：! ：! 导师签名：逝) 挫日期： 翻：三：! 第一章绪论 1 1 选题背景和意义 m i m o 技术作为抵抗多径衰落的重要手段得到人们越来越多的关注，已经被认为 是新一代无线传输系统的关键技术之一。但从实际工程角度考虑，对于蜂窝通信系统 上行信道而言，由于受到移动终端尺寸、功耗、天线设置等因素的限制，很难在一个 移动终端上装置多根天线，m i m o 技术很难直接应用到实际通信系统中。因此，如何 更好地将分集的强大优势和具体实现结合起来一直是一个值得研究的问题。 c o v e r 和g a m a l 曾提出中继信道模型【l 】，s e n d o n a r i s 等人受到中继信道的启发，首 先提出了协作分集的概念【2 j 1 2 1 引，使具有单根天线的移动台获得类似于m i m o 系统中的 空间分集增益。其基本思想是在多用户环境中，具有单根天线的移动台可以按照一定 的方式来共享彼此的天线，从而产生一个虚拟m i m o 系统，以获得分集增益。 s e n d o n a r i s 等人在信息论理论上对信道容量，中断概率和遍历概率所做的分析揭示了 协作分集的巨大潜力。并且表明协作分集不但能提高系统的传输速率，还可以降低系 统的中断概掣2 1 。l a n e m a n 提出了两种基于重传的协作分集方案【4 1 ，放大中继和解码 中继，进而又针对解码中继进行了扩展，提出了选择中继和增强中继协作方案【5 】。由 于放大中继和解码中继都是基于重传的协作方案，因此从信道编码角度来看，它们都 没有很好的利用信道带宽，于是h u n t e r 等人提出了采用信道编码的协作方案，编码 协作【6 j 【丌。不像放大中继和解码中继需要重复发送信号，编码协作分集中将所需发送 的码字分为两部分，一部分由发送端发送，另一部分由协作端发送。研究表明编码协 作分集比放大中继和解码中继具有更好的性能。 当协作通信的物理层逐步发展的时候，其上层的问题，例如：中继伙伴选择问题 和协作的资源分配问题也开始引起重视和研究。 1 2 协作伙伴选择问题当前主要研究方向 中继节点可以分为两种：一种是固定中继，即在现有网络中增加一些新的节点， 专门用来转发源节点发往目的节点的数据；另一种是不增加新的外设，利用网络中某 些信道条件好的用户为信道条件恶劣的用户( 如小区边缘用户) 转发数据。相比而言， 后者的实现方式更为简单，即在原有的蜂窝网的基础上引入协作传输，这种网络结构 通常称为协作蜂窝网。伙伴选择问题主要解决的是后者的选择问题。 伙伴选择问题的基本目的，是为一个发送节点指定一个中继节点来实现协作。其 最终目标是为一个发送节点选择一个中继节点，以使该链路的增益达到最大。当系统 是个具有多接入的网络的时候，伙伴选择问题变成为所有的源节点指派一个中继节 点，并使整个网络的增益最大化。 对于伙伴选择的问题，当前的研究方向主要有两个。较早的研究主要集中在如何 在一个一发一收多中继的模型上，为链路选择一个最好的中继节点；稍后的研究则开 始讨论在一个通信网络中，如何同时为多条链路分别指派合适的中继节点。 1 - 3 研究内容和创新 研究内容：本文主要从m a c 层入手，结合物理层的理论分析，针对两个具体的 实际通信网络场景，提出了已有伙伴选择算法的改进方案。首先分析了节点功率受限 明显，中继节点不充足的热点传感器网络。通过理论分析，提出了使用中继复用的系 统模型，并以此为基础改进已有伙伴选择算法。其次，针对i d m a 叠加调制协作蜂 窝网，通过分析该协作协议的特点，指出传统的伙伴选择算法不能满足该网络的需要。 随后，修改并提出了一种分布式和一种集中式的伙伴选择算法来适应该网络的需求。 创新：第三章的数学推导和仿真实验证明了，本文提出的基于中继复用的伙伴选 择方法，在中继节点不够充裕的环境下，在平均误码率和满足需求链路数上都优于传 统的伙伴选择方法。改进的伙伴选择方法能更充分的利用中继节点的功率和信道，在 中继数的下降时相对传统伙伴选择有更好的适应性。仿真实验还证明了，修改后的伙 伴选择算法只用0 0 q 2 ) 的计算复杂度，就可以获得近似甚至超越计算复杂度为0 0 q 3 ) 的匈牙利算法的平均增益。 第四章的数学推导和仿真实验证明了，但引入叠加调制后，传统的伙伴选择方案 不再适用。本文针对叠加调制协作通信网络，修改了已有的伙伴选择方案，推导并证 明适用于该网络的最优伙伴选择算法。仿真表明，修改后的算法在不同的发送信噪比 和中断速率要求下，都可以降低系统平均的中断概率，更适合于叠加调制协作通信网 络。 1 4 论文结构 第二章介绍了协作分集技术，协作中的伙伴选择问题，并从已有文献出发，总结 了现有伙伴选择算法上的研究成果； 第三章针对中继节点不充分的热点传感器网络，通过理论分析，提出了使用中继 复用的方法来改进已有伙伴选择算法。并通过仿真分析比较了现有算法和本文算法； 第四章先介绍了一种旨在提高半双工协作通信网络的时隙利用率的叠加调制技 2 术，并指出现有的伙伴选择算法不能很好的适应该系统。针对这种网络，提出了一种 改进的分布式伙伴选择算法。同时提出另一个集中式的伙伴选择算法，并简单的证明 了该集中式伙伴选择算法可以得到全局最优解； 第五章对论文工作做出总结。 第二章协作分集技术 协作分集是一项崭新的技术，国外的研究刚刚起步，国内已经引起人们的关注。 协作分集的主要思想就是通过多用户系统中的各个用户的单一天线之间的协作，产生 一个虚拟的多天线收发系统。协作分集技术最早源于中继信道( r e l a yc h a n n e l ) 研究，但 协作又不同于中继：中继用户只是为源用户转发数据，而协作用户既是转发者，又是 数据源【8 】。 2 1 协作分集概念 无线信道的多径衰落特性是阻碍信道容量增加和服务质量改善的主要原因之一。 分集技术可以通过在发射端发射多个信号样本，在接收端合并多个经历独立衰落的信 号样本，以对抗无线信道中的衰落。常见的分集方式主要有时间分集、频率分集和空 域分集，其中空域分集技术由于不会额外占用时间和带宽资源，并且可与其他分集方 式相结合，因而更具吸引力。空域分集也称为天线分集，其基本思想是利用空间上分 离的多个发射信号样本或多个接收信号样本来对抗多径衰落。近年来提出的m i m o 技术，通过在接收端和发射端同时安置多个天线，从而充分利用了空域资源，大幅度 提高了信道容量。尽管m i m o 技术具有明显的优势，并已逐渐被新一代无线通信系 统的主流协议所采纳，但仍然存在问题【9 】。具体地讲，现有的多天线都设置在基站端， 而移动终端则很难安置多天线。这主要有两方面的原因：一，移动终端对体积、质量 和功耗的要求远比基站苛刻得多；二，理想的m i m o 系统要求相邻天线之间的间距 要远大于电波波长，并且多个收发天线之间的传输信道是独立的( 或至少是不相关 的) ，而移动终端由于体积限制，根本无法做到这一点。为此，研究者一方面提出了 等效天线阵和穿戴式天线的概念，另一方面则致力于研究相关信道下的信号设计。然 而，这些解决办法收效甚微，实际可获得的信道容量比理想值大打折扣。 为了打破这种僵局，s e n d o n a r i s 等人提出了一种新的空域分集技术协作分集， 使单天线的移动终端也可以实现空域分集。它的基本思想是系统中的每个移动终端都 有一个或多个协作伙伴，协作伙伴之间有责任在传输自己信息的同时，帮助其伙伴传 输信息。这样，每个终端在传输信息的过程中既利用自己又利用协作伙伴的空间信道， 从而获得一定的空间分集增益。现有的研究结果表明：协作分集可以扩大系统容量， 提高网络服务质量，改善系统性能。由于协作分集中的协作伙伴共享彼此的天线，构 成了虚拟的m i m o 多天线系统，并利用分柿式传输和信号处理获得分集增益，从这 4 个意义上讲，协作分集为m i m o 技术走向实用提供了一条新的途径p j 。协作分集的思 想具有非常广阔的应用前景，可应用于蜂窝移动通信系统、无线a dh o c 网络、无线 局域网以及无线传感器网络等多种场合l l 叭。 协作分集的过程可以分为两步：第1 步，源节点以广播方式发送信号，目的节点 和所有的中继节点接收信号，中继节点对接收到的信号进行处理，为第2 步做准备； 第2 步，中继节点将处理后的信号发送给目的节点，此时源节点也可以向目的节点发 送重复的信息或者新的信息，最后目的节点按照某种规则合并两步接收到的信掣引。 从本质上说，协作分集就是希望借助于协作伙伴的天线，与其自身天线共同构造 多发射天线，并通过模仿传统的多发射天线分集来获得空间分集增益。如果在某个时 段用户没有信息要传送，那么在没有协作时其资源只能闲置，而协作分集则可以实现 用户资源的充分利用。另外，在用户资源没有闲置时，用户既要传送自己的信息，又 要传送其协作伙伴的信息，会牺牲一部分自己的资源，但是，用户也通过协作利用了 其协作伙伴的空域资源。只要合理地设计协作方案，完全可以做到协作分集带来的增 益大于其所付出的代价。 综合来讲，协作分集可以更有效地利用整个网络的资源，使网络性能更稳定。协 作分集的思想虽然来源于中继通信，但是在许多方面却不同于中继通信。首先，在中 继通信中，中继节点的作用是形成主信道，它是单纯作为中继而存在的，本身没有信 息要传送，而协作分集的通信机制更为复杂，远不止是一个简单的中继问题，因为每 个用户既要中转其协作伙伴的信息，还要传送自己的信息。此时，中继节点的作用是 协助、增强主信道。此外，在协作分集中，用户间的信道是有噪声的，也就是说，不 能保证每个用户都可以成功接收并正确检测到其协作伙伴发送的信息。最关键的是， 传统的中继没有分集的功能，而通过协作可以使单天线用户也获得分集增益。当然， 协作分集不局限于两个用户之间的协作，可以是多用户之间的相互协作，即一个用户 可以同时拥有多个协作伙伴。 针对在接收端如何相互处理自己和“伙伴”的有用信号的问题，目前主要提出了 3 种方案【8 。1 l 】：放大前传( a m p l i f ya n df o r w a r d ) 、解码前传( d e c o d ea n df o r w a r d ) 与编码 协作( c o d e dc o o p e r a t i o n ) 。 放大前传方式( a m p l i f ya n df o r w a r d ，a f ) 最早由l a n e m a n 提出并进行了详细的分 析。这是一种简单的协作处理方法，即每个用户接收到加有噪声的伙伴的信号后，进 行放大，然后重新将这加有噪声的信号发送给基站。基站接收到用户和伙伴的信号后 再进行判决。在这种方案中，尽管协作者在放大信号的同时也放大了噪声，但基站能 接收到两个独立的衰落信号，仍然能起到分集的作用，最后检测结果的性能还是改善 了。l a n e m a n 的研究表明在高信噪比时，在两个用户的情况下，该机制可以获得的分 集阶数为2 。这里，分集阶数可以看作空间不相关信道的个数。需要注意的是，分集 阶数并不简单地等于天线个数或参与协作的用户数。在放大转发机制中，该机制假设 已知用户间信道系数，从而可以进行最优译码【l2 1 。所以，基站端要完成最优检测，还 需要知道用户间信道的状态信息。另外，如何采样、存储、放大并重传模拟信号的技 术也是值得研究的问题。 解码前传方式( d e c o d ea n df o r w a r d ，d f ) 与传统中继方法很接近。每个用户首先去 尝试检测出伙伴的数据比特，然后将检测出的比特重新发送。伙伴可以通过基站或其 他技术进行指定。这样在实际中，每个用户都有一个伙伴为它提供第二条路径，从而 形成分集。这种信号处理机制非常简单，但还存在以下问题：a ) 中继节点处对源节点 信号的检测可能失败，这时基站进行的最后检测是有害的；b ) 为了获得最优译码，基 站需要知道用户之间信道的差错特性，这无疑提高了系统的要求。为了避免上述差错 传播问题，l a n e m a n 等人提出了种选择解码中继( s e l e c t i o nd f ) 方案，即当用户间信 道的瞬时信噪比较高时，各用户才检测并转发其伙伴的数据，而当用户间信道的瞬时 信噪比较低时，用户则转为非协作模式。研究表明，当信噪比较高时，两用户的选择 解码中继不仅可以和放大中继一样，具有二阶的分集增益，而且可以获得更低的误比 特率( b e r ) 和误块率( b l e r ) 【”】。选择中继( s e l e c t i o nr e l a y ) 可以看作是解码中继的延伸， 这种方式是根据用户间信道的状态决定是否进行协作，也可以在放大中继中应用。在 以上两种协作模式的基础上，还有另外一类延伸，即增强中继( i n c r e m e n t a lr e l a y i r i g ) 。 增强中继是根据用户一基站间的信道质量来决定是否进行中继，一般的实现方式是， 基站以广播的形式发送一个反馈信息，然后用户和其伙伴根据反馈信息决定是否协 作。若基站认为信道质量较好，不需要进行协作，则用户发送下一部分信息，从而提 高了频谱效率。 编码协作( c o d e dc o o p e r a t i o n ，c o ) 是将协作和信道编码结合起来的方法，它的工 作原理是将每个用户的码字的不同部分在两条相互独立的衰落信道上分别传输，基本 方法是每个用户设法将增加的冗余部分发给对方。当他们之间的信道非常恶劣，这种 协作无法实现时，用户们会自动回到非协作的模式。因此，编码协作的高效性的关键 就是在于无需用户问的反馈，而通过码字的设计自动完成。多种信道编码方法都可以 运用在编码协作的系统里，如卷积码、分组码或两者的结合等，两帧信号的形成可以 通过删余、乘积码或其他形式的级联码来得到由于能具有不同的编码速率和分帧方 法，对不同的信道状况编码协作具有很强的灵活性，因此相应地性能都有显著增益， 这一点是优于前两种方案的。 6 通过对3 种协作方式的比较，发现在低s n r 时，解码转发机制和编码协作机制 效率都不高，这是由于此时系统相当于重复编码，编码协作机制的性能与未协作系统 的性能相差不多；在中、高s n r 时，编码协作机制的性能远优于其他协作机制。 2 2 协作分集增益 2 2 i 提高信息传输速率 研究证明，当两个用户到基站的信道统计特性相似，即有相同的均值，并且两用 户间的信道质量较好时，协作方案提高信息传输速率的幅度就越大，系统性能的提升 就越显著。当两个用户到基站信道统计特性不同时，协作依然能提高信息传输速率， 且本身通信质量较差的用户受益较大，而相对通信质量较好的用户并没有受到不良的 影响，可达速率区域仍然是有所增加的例。 2 2 2 减少系统中断概率 实际系统中，时延要求常使我们不能够有一定长度的码序列，由此传信率就成为 随衰落程度变化而变化的随机变量。有些无线系统对信息传输速率有最低要求，如果 低于这个值即认为系统不可靠，无法继续运行。这时，如果得到的随机变化的传信率 低于一定的水平，即业务可靠速率，则发生“中断。因而，中断概率也成为系统性 能的一个评判标准。 研究表明，如果两用户传信率相等时，对所有业务的可靠速率，协作系统的中断 概率都要小于非协作系统的中断概率。即便是传信率的提高并不多，但系统的健壮性 却能提高很多i l 。 2 2 3 扩大覆盖范围 协作通信属于中继通信的一种，它也具有提高覆盖范围的特点。对于处于小区边 缘外侧的用户，通过采用小区内的中继( 移动或固定) 使用协作通信方式提高上下行 速度，从而达到小区的接入要求。从这个意义上说，在引入了协作通信之后，小区的 覆盖范围可以较原有的通信蜂窝网络有所提高。同时，对于处于阴影效应下等通信盲 区的用户，利用中继带来的分集效果，同样可以提高上下行速度。因而，协作通信还 可以提高小区内的用户覆盖率【l0 1 。 2 2 4 减少传输的误码率 7 由于中继重传了源节点发送的信号，在接收端获得了空间分集增益，信道质量得 到提升，接受信噪比上升，传输的可靠性可以得到明显提升。因而，在协作通信下， 系统的误码率可以得到提升【5 1 。 2 2 5 减少功率消耗 对于一些功率受限的很明显的网络，例如传感器网络，在满足传输需求的前提下 降低节点的功率消耗，延长系统的生存时间非常重要。2 2 2 节中，我们提到由于中 继重传了源节点发送的信号，在接收端获得了空间分集增益，信道质量得到提升，接 收信噪比上升，误码率下降。因此，当网络中存在最高信噪比要求时，功率的消耗可 以通过协作通信得到降低，获得能量效应。 另一方面，传统的直传通信，功率的消耗集中在源节点；而在协作通信中，功率 消耗重新分配到了源节点和中继节点两个节点上。这使单个节点的传输压力减小，能 量消耗分散，使传感器网络的生命时间得到延长。事实上，一个实际中的网络中，通 常并不是所有节点都总是处在繁忙状态，总是存在空闲节点。因而，协作通信合理利 用了这些空余节点，使网络性能得到更充分的发挥。 2 3 协作伙伴选择 2 3 1 伙伴选择问题介绍 协作伙伴选择是影响协作增益的重要因素，选择好的协作伙伴节点能进一步提高 协作增益。对于一条协作链路，伙伴选择问题是从候补中继节点中，选出能带来最大 增益的节点。而针对存在多个中继节点的无线网络，随着参与协作的节点数增多，伙 伴选择的主要目标变为合理地取舍协作节点，使系统中更多的链路能获得协作增益。 目前，对于协作通信的研究j 下逐渐从经典的三点模型的研究分析，转移到多中继模型 乃至多点通信网络模型的研究分析上，这对伙伴选择的研究带来了更多的挑战。 2 3 2 单链路伙伴选择方法 8 固 哆伙 图2 = i 单链路多中继信道模型 图2 - i 是单链路多中继信道的系统模型。该模型中存在一条通信链路以s 为源节 点，d 为目的节点。该链路通过要通过协作来提高传输质量，需要从候选的n 个中 继节点r i ( i 1 ，2 ，n ) ，选择一个作为其中继。 以a f 中继策略为例，当链路采用r i 作为中继进行协作后d 点的接受信噪比s n r f 可以表示如下： s n r = p r s h 伊s ：o + 亍；刁孑丢善兰 c 2 。) 其中，咫表示源节点s 的发送功率，戽表示节点r i 的发送功率，h s d 是节点s 到节点d 之间信道的信道增益，以和h 毛分别表示节点s 到节点r i 和节点r i 到节 点d 之间信道的信道衰落，盯2 表示系统中的加性高斯白噪声功率。 在该模型的研究中，通常都不考虑节点功率输出上的差别，即是认为 b = 碟= 焉= = 掣= p 。因此，( 2 1 ) 也可以表示为： s n r j = 等+ 研砑p h s r p 瓦h 肋硐 倍2 ) r 叮2r 仃2 f 尸! 日：+ 朋：。+ 仃21 、7 在高信噪比下，可以简化为： s n 如p h s o + 褊i t ( 2 - 3 ) 1 1 盯2r 仃2f 日：+ h ! 1 、7 其中等表示直传信道的接收胤匕，褊表示中继信道的接收 信噪比。此时，我们可以简单描述图2 - 1 的问题为如下： m j a xs n r ( 2 3 ) 9 但根据式( 2 2 ) ，可以看出各s n r 。的不同主要取决于中继信道带来的信噪比提高。 而中继信道的信噪比提高则主要由中继链路的两条信道决定。即，中继信道的质量决 定该协作链路的性能。考察中继的不同带来的增益差别有多大。因为信道增益主要取 决于大尺度衰落，因此可以使用距离来近似描述信道增益。假设信道衰落因子为2 ， 则如玄，其中r s d 是节点s 到节点d 的距离。类似的转化和，式( 2 2 ) 可以近似为： d 厂 、l 洲肌击l岳+丽j(2-4)fo- 2i “心+ 患j 由图2 - 1 可知，式( 2 4 ) 有限制条件+ 。因此，可以推导得到s n r 的取 值范围为主7 玄 s n r k 1v 江1 ，2 ， ( 2 5 ) 丙。 为了解决式( 2 5 ) 的问题，s a d e k 等人提出了以节点的位置为标准，选择最近的节 点为协作伙伴节点的方法。并通过轮询将该方法应用到包含多个节点的蜂窝网模型中 【1 6 】。用位置信息代替的信道信息，可以认为是在降低了精度的情况下，更容易的获取 了决定协作伙伴参数。距离是决定信道质量的主要参数之一，因此该方法的本质依旧 是以信道质量来决定协作伙伴。h u n t e r 在文献 1 7 】中采用了贪婪法来协作进行伙伴选 择，但仍然是一个局部最优的算法。文献 1 8 1 使用了匈牙利算法来代替文献 1 7 】中的 贪婪算法，使用全局最优的匈牙利算法，在高信噪比条件下，可以以相对较高的计算 复杂度换来更低的中断概率。贪婪算法和轮询的方法所需的计算复杂度为o ( n 2 ) ，而 优化后匈牙利算法的结果为o ( n 3 ) ，穷举的计算复杂度为o ( n 4 ) 。可以看出，匈牙利算 法和穷举算法计算复杂度明显较高。m a h i n t h a n 等人提出并比较了基于m w 匹配算法 和w l f 匹配算法的多种匹配算法来进行伙伴选择【19 1 。y a nc h e r t 2 0 1 根据效应函数的不 同，提出了m t u 、m m u 、m p u 等算法，但其核心算法部分是的图论中的匹配算法。 m u k h e r j e e 2 i 】引入了拍卖理论来解决伙伴选择问题，其选择部分的核心算法是用的穷 举匹配。 自h u n t e r 在文献 1 7 】的研究之后，人们逐渐注意到，在满足链路和中继节点一一 对应的要求时，协作伙伴选择问题( 或协作伙伴分配问题) 可以通过图论中的分配算 法来进行解决。无论是贪婪算法、匈牙利算法、m w 算法、w l f 算法等，都是基于 图论中的最优匹配原理的。因此，这些算法的数学模型也可以回归到图论中的解决最 优匹配的数学模型加权二分匿 ( p r i c e db i p a r t i t eg r a p h ) 。 xy 源节点1 源节点2 源节点n 中继节点l 中继节点2 中继节点m 图2 - 4 用二分图表示的伙伴选择问题 图2 4 是用二分图表示的伙伴选择问题。其中，左侧的x 集合为源节点集合，右 侧的j ，集合为源节点集合，两个集合间的连线上有权值e i ，这些权值的集合用图中的 8 表示。在物理意义上，权值e ，即等价于式( 2 5 ) 9 的。 这类二分图最优匹配问题( p e r f e c tm a t c h i n g ) ，图论中已经证明，其存在一个最优 解。匈牙利算法( h u n g a r ym e t h o d ) 就是获得该最优解的一种方法。该方法由匈牙利数 学家e d m o n d s 于1 9 6 5 年提出。具体步骤如下： 第一步：使指派问题的系数矩阵经变换，在各行各列中都出现零元素。 ( 1 ) 从系数矩阵的每行元素减去该行的最小元素。 ( 2 ) 再从所得系数矩阵的每列元素中减去该列的最小元素。 第二步：进行试指派，以寻求最优解。为此，按以下步骤进行： ( 1 ) 从只有一个零元素的行( 列) 开始，给这个零元素加圈。 ( 2 ) 给只有一个零元素的列( 行) 的零元素加圈，然后划去该零元素所在行( 列) 的其它零元素。 ( 3 ) 反复进行( 1 ) 、( 2 ) 两步，直到所有零元素都被圈出和划去为止。 ( 4 ) 若仍存在没有划圈的零元素，且同行( 列) 的零元素至少为两个。这可用不 同的方案去试探，从剩余零元素最少的行( 列) 开始，比较这一行各零元素所在列中零 元素的数目，选择零元素少的那列的这个零元素加圈。然后划掉同行同列的其他零元 素，可反复进行，直到所有零元素都已圈出和划掉为止( 此步无须再调用( 1 ) ( 2 ) ( 3 ) ) 。 ( 5 ) 若圈出的零元素数目m 等于矩阵的阶数n ，那么这指派问题的最优解已求得， 否则转入下一步 第三步：作最少的直线覆盖所有的零元素，以确定该系数矩阵中能找到的最多的独立 元素数，为此按以下步骤进行： ( 1 ) 对没有圈零行打 ( 2 ) 对打行中有零元素的列打 ( 3 ) 对打列中含圈零元素的行打 ( 4 ) 重复( 2 ) 与( 3 ) 直到打不出为止 ( 5 ) 对没有打的行画一直线，对打的列画一直线，令这些直线数目为，即为 覆盖所有零元素的最少直线数。 若成功，说明必须变换当前的系数矩阵，才能找到n 个独立的零元素，为此转入第四 步；否则应回到第二步( 4 ) ，另行试探。 第四步：对所得矩阵进行变换的目的是增加零元素。为此在没有被直线覆盖的部分中 找到最小元素，然后在打行的各元素中都减去这最小元素，而在打列的各元素都 加上这个最小元素，以确保原来的零元素不变。这样可以得到新的系数矩阵( 最优解 与原来相同) ，若得到1 1 个独立的零元素，则已得到最优解，否则回到第三步重复进 行。 匈牙利算法的计算复杂度原本为o ( n 3 j ) ，后经过改良，降低为o ( n 3 ) 。在上述的 解决伙伴选择问题的文献中，通常认为该方法虽然可以得到最优的解，但计算复杂度 比较高，对节点( 特别是分布式系统中的节点) 的计算能力要求太高而不适合应用。 在很多的情况下，该算法主要用于计算理论最优值作为比较。但通常，集中式的伙伴 选择方法的计算复杂度很难再比o ( n 3 ) 低了。因此，除了匈牙利算法外，人们也在进 一步探索改良贪婪算法等局部最优的算法来获取计算复杂度和增益的折中。其中 m a h i n t h a n 等人采用的w l f ( w o r s tl i i l kf i r s t ) 算法获得了比较不错的效果。该w l f 算 法的过程如下： 第一步：从还没有分配到中继的源节点中，选出直传信道质量最差的源节点f 。 第一步：考察所有的未被分配的候选中继节点，从中选择出能为节点f 带来最大协作 增益的中继节点，。 第三步：重复第一步和第二步，直到没有未分配到中继节点的源节点或是所有的候选 中继节点都已经分配出去了。 w l f 算法的主要效果来自于地板效应。网络的平均误码率( 误帧率、中断概率等) 通常由最差的一条( 或几条) 链路来决定。因此，优先把资源分配到这些链路上，可 以提高系统的可靠性和稳定性。 1 4 图2 5w l f 和匈牙利算法的中断概率性能比较 2 4 本章小结 本章介绍了协作通信的基本概念，主要的分集方式以及协作分集带来的主要增 益。随后，详细描述了单链路下的伙伴选择问题和协作无线通信系统中的伙伴选择问 题，并介绍了现有的解决方案和主要算法，对这些算法做出了比较分析。 第三章一种功率节省的传感器网络改进伙伴选择方法 3 1 无线传感器网络 3 1 1 无线传感器网络特点 能量受限。传感器节点体积微小，通常携带能量十分有限的电池。由于传感器节 点个数多、成本低廉、分布区域广，且工作环境复杂，有些甚至是人不能到达的地方， 所以通过更换电池的方式来补充能源是不现实的。因此，降低和平衡节点能耗，延长 网络的生命周期就成为无线传感器网络研究中的一个关键领域。在无线传感器网络设 计过程中，任何技术和协议的使用都要以节能为前捌2 2 】。 以数据为中心。目前的互联网是一个以口地址为中心的网络，地址标识、资源 定位和信息传输都依赖于计算机终端、路由器、服务器等网络设备的i p 地址。无线 传感器网络是任务型的网络，每个节点没有统一编址的i p 地址。是否需要节点标识， 取决于网络通信协议的设计。在传感器网络中，人们通常只关心某个区域的某个观测 指标的值，而很少去关心具体某个节点的观测数据。比如说人们可能希望知道“检测 区域的湿度是多少”，而不会关心“某个节点所探测到的温度值是多少【2 3 1 。所以通 常说传感器网络是一个以数据为中心的网络。 节点数量多，密度大。外界的不确定性使得必须布置大量的传感器节点并使之协 同工作才能完成信息收集等任务，为了对一个区域执行监测任务，往往有成千上万传 感器节点空投到该区域。 大规模，自组织。传感器节点通常被放置在没有基础结构的地方，节点的位置不 能预先精确设定，节点之间的相互邻居关系预先也不知道。且在使用过程中部分传感 器节点由于能量耗尽或环境因素造成失效，也有一些节点为了弥补失效节点、增加监 测精度而补充到网络中，使节点的个数动态地增加或减少。这样就要求传感器节点具 有自组织的能力，能够自动进行配置和管理，通过控制机制和网络协议自动形成转发 数据的无线网络。 拓扑结构变化快，无中心。无线传感器网络中所有节点地位平等，是一个对等式 网络。节点可以随时加入或离开网络，任何节点的故障不会影响整个网络的运行，具 有很强的抗毁性。并且，由于传感器节点在工作和睡眠状态之间切换以及传感器节点 随时可能由于各种原因发生故障而失效。这些特点都使得传感器网络的拓扑结构变化 很快，对路由算法和链路质量控制等协议的有效性提出了挑战。此外，如果节点具备 1 6 移动能力，也有可能带来网络的拓扑变化。 通信、计算、存储能力有限。无线传感器网络是在微电子技术、数字电路技术基 础上发展起来的，传感节点各部分集成度很高，因此具有体积小的优点。当然从应用 角度讲，减小节点尺寸也是必须考虑的设计要素。正因如此，其计算和存储能力都很 有限。这就决定了在节点操作系统设计中，协议层次不能太复杂。 3 1 2 无线传感器网络的节能技术 节能是无线传感器网络的核心，直接关系到传感器网络的生命周期。根据传感器 网络的特点，其节能技术可分为两个方面：一是，针对数据处理节能；二是，针对数 据传输节能。 ( 1 ) 数据处理节能技术 数据处理节能技术主要是降低处理器的能量消耗，目前关于数据节能的技术有以 下几种【2 4 】： 动态电压缩放技术。它是1 9 9 8 年美国c a l i f o r n i a 大学b e r k e l e y 电子研究实验室的 t r e v o r p e r i n g 等学者就提出的，这项技术的出发点是：在大多数传感器节点上，负载 是随时间变化的，因此并不需要微处理器在任何时刻都保持峰值性能。通过动态改变 微处理器的工作电压和频率，使其刚好满足当时的运行需求，从而在性能和能耗之间 取得平衡。 动态功率管理技术。这是l b e n i n i 等学者提出的，其基本思想是尽可能使系统各 部分运行在节能模式下。最常用的管理策略是关闭空闲模块，在这种状态下，部分传 感器节点将被关闭或者处于低功耗状态，直到有感兴趣的事件发生。 能量可扩展d s p 算法。美国麻省理工大学的a s i n h a 等学者提出的能量可扩展 d s p 算法设计的概念以进一步节省处理器能耗为目的。基本思想是将传统d s p 算法 的执行操作按影响结果的显著程度进行排序，将影响结果大的操作先执行，这样就可 以在能耗与结果精确程度之间寻求一个权衡。 ( 2 ) 数据传输节能技术 由于数据传输是能耗的主要部分，涉及到网络通信的各个协议层，现有研究工作 既有关注m a c 的节能技术，也有关注网络路由和无线传输的节能技术 2 z ，2 5 。 m a c 节能技术主要解决的问题是如何构造一个能量最优化的拓扑及如何调度各 节点的睡眠以节能。因无线传感器网络的特殊性，使得它在m a c 协议设计与传统网 络m a c 协议设计有很大不同。典型节能m a c 协议有： s - m a c 协议。这是一种基于周期性睡眠侦听调度机制的协议，通过周期性睡眠， 能有效减少无线模块处于侦听状态的能耗，但同时会引入一定时延开销。根据此协议 又提出了动态s - m a c 的协议( d s m a c ) ，该协议在原有s - m a c 协议的基础之上增 加了占空比动态调整特性，能获得比s m a c 协议更好的节能效果。