（通信与信息系统专业论文）无线蜂窝中继小区路由方法研究.pdf

摘要 摘要 面对未来无线通信系统高数据速率、高频谱效率传输的需求，以及潜在可 用频段提高导致的无线覆盖降低问题，传统的蜂窝小区结构越来越难以胜任， 需要进行升级。将中继技术引入蜂窝小区，提高小区边缘的数据吞吐率，组建 新型的蜂窝中继小区是一种非常具有应用前景的方案。在蜂窝中继小区中，如 何进行路由，为用户选择合适的中继节点，是建立蜂窝中继小区所必须的一项 关键的技术。论文主要从缩短路由时间和提高寻路质量两个方面对路由问题进 行研究。 本论文首先从蜂窝中继系统以基站为中心的特点入手，提出了一种集中式 的快速路由方法。在该方法中，用户通过向基站发送路由请求而获取中继路径。 基站维护信道质量表，并根据信道质量表，为用户指定中继节点，避免了传统 的路由方法中用户向邻节点广播路由请求，接收反馈而造成的时延、碰撞，缩 短了路由所需的时间。论文为集中式的快速路由算法设计了路由所需的信令， 并分析了基站由信令交互获取小区拓扑信息，更新信道质量表的过程。 本论文进一步在集中式的快速路由方法基础上，提出了种基于中继信道 互信息量的基站端处理算法，利用该算法，基站为用户筛选最合适的中继节点， 提高路由质量。论文首先推导了在不同的中继转发方式下，中继信道的互信息 量表达式，然后详细说明了能够使中继信道互信息量最大的节点选择方法，并 从吞吐量的角度，将其与传统方法在路由质量上进行了比较。最后，将问题扩 展到小区中有多个用户同时发出中继请求的情况，论文给出了能够使小区平均 互信息量最优的基站端处理方法，并进一步给出了能够使运算复杂度显著降低 的次优方法。 关键词：中继、蜂窝、路由 a b s t r 2 【c t a b s t r a c t w i r e l e s sc o m m u n i c a t i o ns y s t e m si nt h e 矗n u r em u s tp r o v i d el l i 曲d a t 孙s p e e da i l d s p e c t r a le 伍c i e n c y ，a n da l s of a c em ep r o b l e mt h a t 诵r e l e s sc o v e r a g ew o u l dd e c r e a l s e w h e nm eu s e 如lb a l l d sr i s e t h e r e f o r c ，t h e 饥l d i t i o n a lc e i ls t n l c t u r ei sm o r e 趾dm o r e i n c o m p e t e n ta i l dn e e d st ob ei n l p r 0 v e d t h er e l a yt e c l l i l i q u ei sv e r ya t t r a c t i v e 锄o n g a l lo ft h ec a n d i d a t e si nf u 眦c o m m u n i c a t i o ns y s t e m t h en l r o u g t l p u to nt h ee d g eo f ac e l lc a nb e 笋e a t l yi m p r 0 v e db yb u i l d i n gn e wg e n e r a t i o no fc e l l u l a rn e t w o r kw i t h r e l a y r o u t i n gi sak e yp r o b l e mi i lt h er e l a yc e l l u l a rn e t 、) r o r k p r o p e rc h o i c eo fr e l a y n o d e sg u a r a n t e e st h en e t w o r ke f 矗c i e r l c y t h i st h e s i sf o c u s e so nr o u t i n gp r o b l e mi n t h ew i r e l e s sc e l l u l a rn e t 、v o r kw i t hr e l a ya i l d 埘ui n v e s t i g a t e 铆om a i np r o b l e m s ： r e d u c i n gr o u t i n gt i m ea i l di m p r 0 v i n gr o u t i n gq u a l i t y t h i st h e s i s1 f i r s tc o n s i d e r st 1 1 ec e n t r a l i z e dr e l a yc e l l u l a rn e t w o r kw i mab a l s e s t a t i o n 孤dp r o p o s e sa 风tr o u t i n gm e t h o d i nt h em e t l l o d ，u s e r sa c q u i r er e l a yp a t h s b ys e n d i n gr e p l i e st o t l l eb a s es t a t i o n t h eb a s es t a t i o nm a i n t a i n sat a b l ew h i c h d c s c r i b e s 也es t a t u so fw i r e l e s sc h 锄l e l si nt h ec e l l b a s e do nt h et a _ b l e ，t l l eb a u s e s t a t i o na s s i g n sr e l a yn o d e sf o ru s e r s b ya v o i d i n gt h ep r o c e s so fb r o a d c a s t i n ga r l d 诧e d b a c kw m c hc a u s ed e l a ya n dc o i l i s i o n si nt m d i t i o n 鲥m e t h o d s ，t 1 1 en e wm e t h o d d e c r e a s e st h er e l a yt i i n e 伊e a t l y t h et h e s i sa l s od e s i g n sas e to fc o n ：t 1 0 ls i g n a l i n g w h i c hf i t sm en e wm e t h o da n da 1 1 a l y z e dt 1 1 e u p d a t i n gp r o c e s so fc h a i u l e lt a b l e m a i n t a i n e db yt h eb a s es t a t i o nt l l r o u 曲c o n t r o ls i g l l a l i n g t h et h e s i s 廿1 e np r o p o s e sap r o c e s s i n gm e n l o df o rb a s es t a t i o nb a s e d0 nt l l e c e n t r i cf 弧tr o u t i n g m u t u a li 0 n l l a t i o ni su s e df o rm eb a s es t a t i o nt 0c h o o s em em o s t p r o p e rr e l a yn o d ef o ru s e ra n di m p r 0 v e 也eq u a l i t yo fr o 证i n g w ef i r s td e v e l o p e x p r e s s i o n so fm u t u a li n f o m l a t i o nf o rr e l a yc h a m l e lu n d e rd i f f e r e n tr e l a ys c h e m e s ， a 1 1 dt h e ni n t r o d u c em em e t h o dw h i c hm a x i m i z e st h em u t u a li m o 肋a t i o no ff e l a y c h m m e li nd e t a i l f r o mt h ea l s p e c to fm r o u g h p u t ，w ec o m p a r et h en e wm e m o dw i m t r a d i t i o n a jo n e s a tl a s t ，、ee x t e n dt h ep r o b l e mt ot h es i t u a t i o nw h e nm u l t i u s e rh a s t 1 1 er e p l yf o rr o u t i n g w ep r o p o s em em e t h o dw 1 i c hc a i lo p t i m i z et h ea v e r a g em u t l l a l i n f 0 册a t i o n ，a n d 百v et h es u b o p t i m a lm e t h o dw h i c hc a nr e d u c et h ec o m p l e x i t yo f c o m p u t i n gg r e a t l y k e yw o r d s ：r e l a 弘c e l l u l a r ，r o u t i n g i i 插图目录 插图目录 图卜1 蜂窝多跳小区4 图2 1 中继路由系统模型7 图2 2 基于门限的定时器方法1 1 图2 3a o d v 改进路由方法1 3 图3 1 典型的蜂窝多跳小区结构1 5 图3 2r r e q _ 1 信令格式1 6 图3 3r r e o 一2 信令格式16 图3 4r r e p - 1 信令格式17 图3 5r r e p _ 2 信令格式1 7 图3 6 基站寻路过程1 8 图3 7 传统的路由反馈过程2 2 图3 8 寻路时间随小区节点个数变化曲线2 3 图3 9 平均寻路时间随寻路次数变化曲线2 4 图4 1 无线中继信道2 8 图4 2d f 转发方式的可达速率3 1 图4 3 单个源节点系统吞吐量( a f ) 3 6 图4 4 单个源节点系统吞吐量( d f ) 3 6 图4 55 个源节点吞吐量比较( a f ) 3 7 图4 61 0 个源节点吞吐量比较( a f ) 3 8 图4 72 0 个源节点吞吐量比较( a f ) 3 8 图4 85 个源节点吞吐量比较( d f ) 3 9 图4 91 0 个源节点吞吐量比较( d f ) 3 9 图4 1 02 0 个源节点吞吐量比较( d f ) 4 0 v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：筮丝 沙富年歹月，厂日 第l 章绪论 第1 章绪论 1 1 研究背景 移动无线通信在过去的2 0 年中以惊人的速度发展，新的技术层出不穷， 现在的移动通信系统无论是在用户的数量还是从业务的种类上，与当初相比都 发生了翻天覆地的变化。上世纪8 0 年代，第一代模拟无线通信系统开始投入商 用，它以频分多址( f d m a ) 为接入技术，仅能提供9 6 k b i t s 传输速率，业务也仅 限于话音服务。上世纪9 0 年代开始发展的第二代窄带数字系统把时分多址 ( t d m a ) 和码分多址( c d m a ) 作为其主要的接入技术，提供9 6 到2 8 8 k b i t s 的传 输速率，可以提供话音以及低速数据业务；而目前已经实现商用的第三代移动 通信技术，将无线通信与国际互联网等多媒体通信结合起来。它能够处理图像、 音乐、视频流等多种媒体形式，提供包括网页浏览，电话会议，电子商务等多 种信息服务，接入速率最高可以达到3 8 4 k b i t s 。 尽管无线通信已历经三个时代的飞跃，但最早的蜂窝结构却一直保持了下 来。伴随着互联网和多媒体应用的不断增多，移动通信系统对高速数据业务的 需求仍在不停增长，在未来的宽带移动通信系统中，系统将需要达到更高的传 输速率：b 3 g 系统( 如3 g p p l t e ) 要求达到下行1 0 0 m b p s 的传输速率，而目 前正在研究的4 g 系统( 如i m t - a d v ) 更是要求达到下行g b p s 的量级。在如此高 的传输速率下，传统的蜂窝结构将很难胜任。这是因为，无线通信离不开无线 信道，与有线信道相比，无线信道的衰落特性会严重影响传输的可靠性，在未 来高速率和大覆盖的通信系统中尤其如此。 无线信道的衰落主要分为大尺度衰落( 路径损耗) 和小尺度衰落两种。其 中，大尺度衰落指电波在空间传播所产生的损耗。在自由空间中路径损耗正比 于发射机和接收机之间距离的平方，实际的环境中这个指数变化范围约为2 5 到 6 。我们知道，在一定的传输功率下，分配到单位比特的能量会随着传输速率的 提高而减小。那么，在未来的高速数据传输中，为了达到一定的毛，传输的 功率必将要大大提高。在下行链路中，基站通过提高发送功率，可以在蜂窝小 区的中心或热点附近可以达到很高的传输速率，但在小区的边缘，由于路径损 耗的影响，要达到所要求的传输速率将非常困难，用户的公平性难以保证。而 第l 章绪论 在上行链路中，在小区边缘无节制地增加单个用户的发射功率会导致该用户很 快能源耗尽，同时也会造成对其它用户链路的巨大干扰。此外，频谱资源的紧 张导致未来的移动通信系统很可能运行在更高的频段上，这也将导致无线覆盖 降低的问题。 正是因为上述原因，传统的无线蜂窝覆盖需要从结构上进行升级和补充。 在目前的众多升级技术中，中继是一项很有前景的技术【l 】【2 】。中继作为一 种使网络在没有固定接入点条件下运行的手段，最早在a dh o c 网络中得到研究 和应用。在发射机和接收机之间放置一些中继节点来帮助传输，可以有效降低 每次传输的路径损耗，在总发射功率一定的条件下，可以显著提高整个蜂窝小 区的容量和覆盖范围。由于中继的众多优点，其概念已经被广泛引入到下一代 移动通信系统中，欧洲的w i n n e r 计划【3 】将中继引入到下一代宽带接入网 中，i e e e8 0 2 1 6w i m a x 标准中也建立了多跳m e s h 网络的概念【4 】。 1 2 无线通信中的中继协作 对中继传输的研究是从中继信道开始的。中继信道的概念最初由v 弧- d e r m e u l e n 在1 9 7 1 年提出，在文献【5 】中，他推导了中继信道基本的容量界，随 后s a t 0 等学者在信息论的层面做了深入的研究【6 】【7 】。然而在此后很长的一 段时间内，中继问题被看做是一个纯数学的理论，而没有实际应用价值。对中 继的研究一直没有引起人们注意，进展也不大。 随着近1 0 年来传感器网络，a dh o c 网络的发展，对于无线中继信道的研究 成为了热点。s c h e i n 和g a l l a g e r 为并行的中继信道建立了容量的上界和下界【8 】， 他们的系统包括一个源节点，两个中继和一个目的节点，并且源节点和目的节 点之间没有直接的链路连接。x i e 和k 啪a r 将他们的结论推广到了具有多个中继 的网络中【9 】。觚t p a r 和v e 妣r l i 得到了一个源节点，一个目的节点系统随中继 节点数目增多时的的渐进容量【1 0 】。 中继信道的优点在于可以利用中继节点的协助，实现源节点与目的节点之 间的可靠通信。根据中继节点的不同转发方式，可以把中继分为再生中继和非 再生中继两类。再生中继又叫做译码前向中继( d e c o d e a n d f o 删) ，是指中继 节点对接收到的源节点的信号进行完全解码再重新编码以后发给目的节点的方 式。非再生中继又被称为放大前向中继( a m p l i f 3 ，a n d f o n a r d ) ，是中继节点对接 2 第1 章绪论 收到的信号只进行简单的放大、量化等处理后直接发送给目的节点的中继方式。 根据目的节点是否能够接收到来自源节点的信号，又可以把中继分为无分 集的中继和有分集的中继( 协作) 两种情况。前一种情况指目的节点处在源节 点覆盖范围之外，无法接收源节点发出的信号，只能通过中继的转发来获得信 息。在这种情况下，中继的作用主要是通过提高覆盖范围来保证通信，许多文 献里又把这种情况叫做“多跳中继 。 当目的节点在源节点的覆盖范围以内能够收到源节点发来的信号时，就可 以把分别从中继节点和源节点接收到的信号进行合并，从而得到分集增益。这 种情况通常又被称作“协作中继 或者“协作分集 ( c o o p e r a t i v ed i v e r s i t y ) 。协 作分集的概念最早是由s e n d o n a r i s 等人提出的【l l 】【1 2 】。他们研究了上行链路 中的一种两用户协作分集模型，首先从信息论的角度分析并给出了这个系统的 容量可达区，然后讨论了协作对中断概率以及覆盖范围的影响，最后针对c d m a 接入方式提出了一种协作策略并给出实现该策略的接收机结构。研究结果表明， 协作能减小系统对信道变化的敏感性，而且还能在提高吞吐量以及小区覆盖范 围方面提供好处。文章最后启发性地指出了一些协作分集方面的关键问题，包 括用户之间谁帮助谁，在什么条件下用户之间协作，用户将在容量区的哪一点 进行协作，由移动台自己还是基站来决定协作伙伴，等等。在几乎同一时间， l a n e m a n 等学者也对协作分集技术展开了研究。文献【1 3 】研究了对用户进行协 作的情况，用户接入方式为t d m a 。作者提出了三种不同的协作分集协议：固 定中继，选择中继( s e l e c t i o nr e l a y i n g ) 和增量中继( i n c r e m e n t a lr e l a y i n 曲。固定中 继协议指得是协作伙伴在固定的时隙帮助源转发信息给目的节点。选择中继协 议是指：当源到协作伙伴之间的信道发生中断的情况下，源自己重传信息给目 的节点；否则协作伙伴充当中继的角色帮助源转发信息。增量中继协议可以被看 作是一种协作混合自动重传请求( h a i 她) 机制。目的节点能够返回一个比特的信 息指示源和协作伙伴译码是否成功，只有在源到目的端的信息不能被正确接收 的时候，协作伙伴才作为中继帮助源转发信息，最后由目的节点把这两部分信 息合并。文中指出这三种协作协议都可以采取两种不同的中继转发方式：放大 前向( a f ) 和译码前向( d f ) 。放大前向属于非再生中继，译码前向属于再生中继。 已经证明除了固定的译码前向协议之外，文中的其它几种的协议都可以获得完 全分集增益。 3 第1 章绪论 1 3 蜂窝中继小区 2 0 0 0 年，l i n 第一次提出了蜂窝多跳网( m u l t i h o pc e l l u l a rn e 似o r k ) 的概 念【1 4 】，他将a d h o c 的思想引入蜂窝系统，对传统的蜂窝小区覆盖进行升级， 并给出了两种可能的升级结构，升级后的蜂窝网络覆盖由基站直接覆盖的区域 和多跳覆盖的区域两部分组成。如下图所示，在引入了多跳之后，传统蜂窝网 络可以在基站直接覆盖范围不变的前提下减小基站密度，或者在基站密度不变 的前提下减小每个基站直接覆盖的范围，直接覆盖不到的地区采用多跳的方式 传输。y a i l i k o m e r o g l u 在他的著作中也提出了类似的思想【1 5 】。 颤蝣：毛 a鬣烈一p亿nb 图卜1 蜂窝多跳小区 蜂窝多跳网结合了传统的单跳蜂窝( s i n g l e - h 叩c e l l u l a rn e t 、o r k ) 与a d h o c 网络的优点。与以前蜂窝网络的中继站( 直放站) 不同，蜂窝多跳网中的中继 通过无线链路转发来自基站或移动台的信号，这一点与a d h o c 中的节点类似。 但蜂窝多跳网与a d - h o c 网络的根本不同在于，a d h o c 网络是在没有固定接入点 的条件下工作，而蜂窝多跳网的目的在于为蜂窝小区扩大无线覆盖，提高小区 边缘的吞吐率。y a n i k o m e r o g l u 在【1 6 】中证明了通过中继，基于t d m a 的蜂窝 小区覆盖范围可以显著增加，z a d e h 等人则研究了基于c d m a 蜂窝通信系统的 中继问题【1 7 】。 c h o 在【1 8 】中指出，在蜂窝多跳小区中，对小区边缘的用户进行2 跳或3 跳的中继对系统吞吐量增加非常明显，而更多的跳数所取得的增益就非常有限， 并且，跳数越多，系统的信令开销会大大增加，反而会造成系统性能损失，所 第1 章绪论 以此后对蜂窝多跳小区的研究大多只考虑进行2 跳( 1 次中继) 的情况。而在 l e n e m 孤等人提出利用协作中继可以获得可观的分集增益之后【“1 3 】，人们 更多的开始将协作中继运用到蜂窝小区中，“中继 成为研究的重点。s o n g 在 【1 9 】中讨论了协作中继对于蜂窝小区容量和公平度的改善，h u a n g 则研究了基 于d f 协作中继的上行c d m a 网络【2 0 】，得到了一些有价值的结论。在本文 中，我们对蜂窝多跳小区的研究也只限于进行1 次中继的情况，我们称之为“蜂 窝中继小区”。 在一个蜂窝中继小区中，如何为用户指定一个合适的中继，对于提高整个 系统的性能是非常关键的，这就需要有效的路由算法【1 6 】【2 1 2 7 】。蜂窝多 跳网的初衷是将a d - h o c 引入到传统的蜂窝小区，针对蜂窝多跳网最早提出的一 些路由算法也与a d h o c 网络中的d s r ，a o d v 【2 8 】等算法类似，是一些分布式的 算法。然而蜂窝多跳网与a d h o c 网络不同，它具有中心基站，小区中所有的用 户都需要向基站注册，并且不论上行下行，数据传输都要经过基站。基于这些 因素，考虑适合于蜂窝中继小区的新的路由方法是十分必要的。 1 4 论文的结构与贡献 论文余下的部分安排如下： 论文的第二章，介绍常见的蜂窝中继小区路由算法。 论文的第三章，从蜂窝中继小区以基站为中心的特点入手，提出了一种集 中式的路由方法。在该方法中，需要中继的用户通过向基站发送路由请求而获 取中继路径。基站维护信道质量表，并根据信道质量表，统一为用户指定中继 节点，避免了传统的路由方法中用户向邻节点广播、反馈而造成的时延、碰撞， 大大缩短了路由所需的时间。论文为集中式的路由算法设计了路由所需的信令， 并分析了基站由信令交互获取小区拓扑信息，更新信道质量表的过程。 论文的第四章，在集中式路由的基础上，提出了一种基于中继信道互信息 量的基站端中继节点选择算法。论文首先推导了在不同的中继转发方式下，中 继信道的互信息量表达式，然后针对只有单个用户的简单情况，阐述了能够使 中继信道互信息量最大的节点选择方法，并从吞吐量的角度，将其与传统方法 在路由质量上进行了比较。针对小区中有多个用户同时发出中继请求的情况， 本章给出了能够使小区整体最优的方法，并在此基础上，给出了能够使运算复 5 第1 章绪论 杂度显著降低的次优方法。 论文的最后一章是结束语，总结了全文的内容与结论、主要贡献和今后可 能的扩展研究。 6 第2 章蜂窝中继系统常见路由算法 第2 章蜂窝中继系统常见路由算法 2 1 引言 本章介绍常见的蜂窝中继系统路由算法，内容安排如下：首先介绍基于节 点距离和路径损耗的路由，然后介绍基于定时器的路由方法以及在定时器方法 基础上改进的基于门限的方法和一种路由时间优化的方法，最后介绍一种基于 a o d v 的改进方法。根据所介绍的路由方法，在结论中，我们分析了传统路由 方法存在的缺陷。 2 2 基于距离和路径损耗的路由 针对蜂窝中继小区，文献【1 6 】提出了几种非常简单的中继路由选择方法。 下图是文献中所考虑的系统模型，假设在用户s 和基站d 之间有k 个可供 选择的中继节点r ，恐，。，我们需要从这k 个节点中选出最适合作为中继的节 点b 。 憾) 、义 、 、两 一 图2 1 中继路由系统模型 文献假定路径的选择在用户端进行，并且该用户已知各种与中继路径选择 有关的信息，如所有供选择的中继节点与基站、用户之间的距离，信道状况等。 7 、3 ， 一 一 一 广 一一 第2 章蜂窝中继系统常见路由算法 需要说明的是，在实际的路由协议中，在进行路径选择之前，必须考虑网络中 的节点如何取得这些网络拓扑信息，这就涉及了各节点之间的信令交互。 首先考虑基于节点间距离的路径选择方法，文献给出了几种直观的选择标 准。假设置到源节点和目的节点的距离分别为k 。和k i ，用r 代表选择的中继 节点，可以得到下面三种准则： 最小总路径标准( s t d ) ： 足2a r g 胞( k 。- + k ，- ) ( 2 1 ) 该准则要求所选择的中继节点到源节点和目的节点的距离之和是最小的。 最小化最长跳标准( l l h ) ： r2 鹕鹏( m a x ( k k ，) ) ( 2 2 ) 该准则将中继的两跳中距离长的一跳作为比较标准，因为距离长的一条往 往是中继通信的瓶颈。 最小中继跳标准( s i m ) ： 足= a r g 恶( k ，) ( 2 3 ) 口“l e 该准则将中继的第二跳作为比较的标准。 因为在实际的系统中，节点的拓扑位置不易获得，可以用路径损耗来代替 节点之间的距离，作为选择的依据。假设第i 个节点到源节点和目的节点的路径 损耗分别为p j ，和儿肋i ，可以得到 最小化总路径损耗( m t p ) 2 a r g 胞( ，+ ，) ( 2 4 ) 最小化最大路径损耗( l m p ) = a r g 弛( m a ) 【( j ，) ) ( 2 5 ) 最小化中继跳路径损耗( m r p ) 2a r g 胞( 。，) ( 2 6 ) 此外，文献【2 l 】给出了最近邻节点算法，即选择与源节点最近的节点作 为中继。 b 2 a r g 鹏( k 。) ( 2 7 ) 或者 8 第2 章蜂窝中继系统常见路由算法 b 2 a r g 胞( 。) ( 2 8 ) 虽然上面所列举的方法都非常简单，并没有涉及具体的信令格式，交互流 程等，从某种程度上来说，它们算不上完整的路由方法，但它提出的一系列路 径挑选准则却非常具有价值，并被后来的许多文献所参考。 2 3 定时器方法 文献【2 2 】为中继网络设计了一种分布式的路由算法，用户通过该算法可 以从k 个中继节点中选择一个，选择到的中继节点能够提供最好的端到端传输 路径。算法的原理简述如下： 假设口，和分别是源节点到中继i ，中继i 到目的节点的信道。通过监听来 自源节点的准备发送包( r t s ) 和来自目的节点的可以发送包( c t s ) ，中继节 点能够得到是否适合中继的信息。通过测量源节点发送r t s ，中继节点i 可以估 计出信道实时的增益口一同样，通过测量目的节点发送的c t s ，中继节点i 可 以估计出信道的实时信息。需要注意的是，源节点不需要监听目的节点的 c t s 。 为了减小系统信令的开销，必须减少中继节点之间的通信，在这个原则下， 文献中设计了如下基于定时器的方法：一旦中继节点收到c t s 包，就启动一个 计时器，计时器从鹿开始倒计时，而忽的值则是根据信道参数a “和来确定的。 具有最好的端到端通信质量的中继节点的计时器将最早到时，到时之后，它发 送一个持续时间很短的f l a g 包，通知周围其他的中继节点。其他的所有中继节 点，此时都正在等待自己的定时器到时，并且都处于监听状态，一旦监听到了 n a g 信号，或者开始转发信息，他们就把自己的定时器清零。 上面是中继节点之间可以进行通信的情况。如果在某种环境下，所有的节 点可以听到来自源节点和目的节点的信令，但是他们彼此之间是隐藏的，不能 彼此通信，那么最佳的中继发给目的节点一个f l a g 信号，通知目的节点，再由 目的节点通过广播，通知所有的中继节点。 每个中继节点对口d 和口。d 的信道估计，描述了源中继目的之间的无线路径 质量。因为两跳对于端到端的传输表现都很重要，中继在衡量是否适合传输的 时候这两跳的值都要考虑，可以使用如下的两个公式： 9 第2 章蜂窝中继系统常见路由算法 准则i ： 曩= m i n l q f l 2 ，1 1 2 )( 2 9 ) 准则i i ： = 工三= 静褂 亿。， h1 2 。1 1 2 使公式最大的中继i 具有最好的端到端传输质量，在接收到c t s 包之后， 每个中继将自己的计时器赋初值z ，显然z 应该与绝成反比 z = ( 2 1 1 ) 其中，兄是一个常数，设 = m a ) 【 红) ，f 【1 k 】 ( 2 1 2 ) 那么与之对应的 瓦= m i n z ) ，f 【1 k 】 ( 2 1 3 ) 这样，最好的中继的倒计时器最先到0 ，因为它的倒计时器初始值比较小。 这个中继节点将中继来自源节点的信息，其余的节点将从它收到f l a g 包( 在中 继节点互不可见的情况下，从目的节点收到) ，并使清空倒计时器。 2 4 基于门限的改进方法 上面基于计时器的方法可以比较方便的找到一个“最好”的中继节点，但 是它对于信道估计的运算量很大，如果有k 个中继候选，需要进行2 k 次信道估 计，此外，当r t s 和c t s 包发送时，所有的中继节点都必须随时保持监听状态， 导致对中继的功率消耗很大。 文献【2 3 】给出了一种基于信噪比门限的改进算法，假设对于中继节点i ， 它的接收信噪比为以- l ，而目的节点接收到来自中继i 信号的信噪比为以。d ，在中 继和目的节点都设一个s n r 门限h ，具体过程如下： l o 第2 章蜂窝中继系统常见路由算法 n 图2 2 基于门限的定时器方法 这个算法的基本思想是，为中继节点接收来自源节点的信号以及目的节点 接收来自中继节点的信号都设置一个门限值，然后开始逐个中继节点的比较， 如果有中继节点能够满足两个门限，则选择这个中继节点，如果不能，则在所 有节点中选择最优的节点。 这个算法与定时器算法相比有两个好处：一是节省了中继节点的能量消耗， 因为中继节点不需要一直处于监听状态，只有信噪比大于门限的中继节点需要 开启。二是不需要做大量的信道估计工作，值需要估计一部分中继节点的信道。 2 5 时间优化方法 文献【2 4 】给出了一种对寻路时问进行优化方法，它的基本思想是： 当源节点需要进行一次中继传输时，它向周围广播一个i u 汪q 信号，所有 收到鼬也q 信号的中继节点会向源节点返回一个i 泳e p 信号，其中包含了由中 继节点测量到的儿2 i 的信息。为了避免不同中继节点的鼬汪p 信号发生碰撞， 1 1 第2 章蜂窝中继系统常见路由算法 中继会在一个随机的延迟之后再发送砒迮p 。m s 还可以通过测量从r s 返回的 砒迮p 信号强度得到兕i ，i ，这样m s 就得到了咒l ，i 和儿2 ，i 两条链路的路径损耗 信息，通过一定的比较准则，m s 选择集合，中最优的r s 作为中继节点。 采用上述的方法有一个问题，不同中继节点发出的i u 也p 信号很可能会发 生碰撞，如果采用c s m c d 的重发机制来进行碰撞重发，随着中继节点的增 多，发送的砌也p 消息增多，碰撞和重发的次数也必然增加，这将导致路由时 间的变长。文献提出了两条改进的方法： 一是源节点在发送i u 也q 时，包含源节点与目的节点之间的路径损耗 删，中继节点i 在接收到i 溉q 后，将自己。，与，删比较，只有心，小 于删的节点才向源节点返回刚砸p ，因为。， 删的节点不会取得好的 中继效果。这样做之后可以减少碰撞的概率，缩短路由的时间。 二是当中继收到i 眦q 后，不是进行一个随机的时延后发送鼬迮p 信号， 而是时延的时间与信道联系起来，进行有优先级的时延 删叫老 ( 2 1 4 ) c 形= 厅幻厂砂c i 。 ( 2 1 5 ) 其中，尸厶。由测量接收到的鼬也q 得到，剧。是中继节点能接收到砌迮q 信号的最大路径损耗值，c 是常数，它使平均的有限度为1 。c w 是通过优先级 得到的新的竞争窗口。这样，r 和s 之间的路径损耗值越小，c w 也越小，r 节 点发送砒逻p 的延迟也越小。当r 接收到足够多高优先级的迮p 后，它发送 一个结束信号，避免更多的中继节点向它发送i u 迮p ，这样就节省了路由的时间。 而发送结束信号的时间则由源节点根据中继点个数多少来确定。 2 6a o d v 的改进方法 文献【2 5 】给出了一种不断传递汪q 包的路由方法，是在传统a d - h o c 的 a o d v 路由算法基础上改进而来的。算法的基本思想是，当源节点有数据需要 进行中继传输时，它向相邻节点广播一个砌疆q 包，黜迮q 包的结构如下 其中，1 y p e 是用来区别i 眦q 和砒迮p 包的域。s o u r c ei p a d d r e s s 和i 砒q 1 2 第2 章蜂窝中继系统常见路由算法 i d 唯一的标识一个i 泳e q 包。每当源节点发出一个新的i 淝q 包，i u 也qi d 增加1 。a c c u m u l a t e dc o s t 代表从源节点到i 泳e q 发送者累计的路径损耗。王k 戤 表示由源节点确定的最大允许的跳数，h o pc o u i l t 表示当前的跳数。 一个中继节点在接收到砌迮q 后，将h o pc o u n t 加1 后的值与上，m 觚比较， 如果他们相同，则丢弃这个砒迮q 包；否则将i 己r e q 包的a c c 哪u l a t e dc o s t 域 更新为原来的值加上i u 逻q 包发送者和融汪q 包接收者之间的路径损耗( 假设 这个路径损耗值可以通过测量接收信号的强度得到) ，并继续广播出去。 图2 3a o d v 改进路由方法 在上图中，a ，b ，c 都是s 的邻节点，他们会同时收到来自s 的鼬迮q 信 号，并且将这个l 泳e q 信令的h o pc o u n t 域以及a c c u m u l a t e dc o s t 域更新，再 次广播出去。在a o d v 算法中，节点会舍弃具有相同s o u r c ei p a d d r e s s 和对迮q i d 的包，所以如果a 的i u 汪q 首先到达了d ，d 就会舍弃来自b ，c 的i 眦q ， 这样就只能建立一条通过a 的路由。 在文献的方法中，目的节点和中继节点同样处理这些具有相同s o u r c ei p a d d r e s s 和砒迮qi d 的包，这样就可以得到多条从源节点到达目的节点的路径。 当目的节点对于路径的选择兼顾了时延和损耗两个方面，为了满足时延上的要 求，目的节点在收到第一个附逻q 包后，只等待一个特定的时间，并处理这段 时间内收到的其他汪q 包。为了使总路径损耗最小，它会选择其中路径损耗 最小的一个i 沁q 包。在选择好之后，目的节点向源节点发送一个砒冱p ，通知 它找到的路径。 1 3 第2 章蜂窝中继系统常见路由算法 2 7 小- 结 本章介绍了一些常见的蜂窝中继路由算法。可以看出，这些方法都是分布 式的路由算法，在寻路都存在着一个由源节点( 用户) 向候选的中继广播请求， 然后反馈的过程，而反馈的过程不可避免的存在时延和碰撞。定时器的方法通 过由信道状况产生的倒计时参数避免反馈时的碰撞，时间优化方法通过减少反 馈节点的个数来缩短路由时间，这些算法都试图在广播反馈机制不变的基础上 做出一些改进。 1 4 第3 章蜂窝中继系统的快速路由算法 第3 章蜂窝中继系统的快速路由算法 3 1 引言 上一章介绍了一些分布式的路由算法，由于这些算法都采用了用户向周围 广播中继请求，并获取反馈的机制，反馈时不可避免的会面临系统碰撞和时延 的问题。蜂窝中继小区与a d h o c 不同的是存在着中心的基站，如果在基站中维 护一些小区的先验信息，采用集中式的处理方法，直接由基站来为用户提供路 由，可以省掉广播反馈的过程，提高系统性能。基于这种思想，在本章中，我 们提出了一种适用于蜂窝中继小区的快速路由方法，该方法充分考虑了蜂窝网 络以基站为中心的特点，显著缩短了路由时间。本章余下的部分安排如下，首 先描述蜂窝中继小区路由的系统模型，然后对新的路由方法做重点说明，接下 来给出一些仿真结果，最后是结论。 3 2 系统模型 图3 1 典型的蜂窝多跳小区结构 图3 1 是典型的蜂窝中继小区结构，这里讨论上行的情况。假设小区中的 移动台均匀分布，并且都具有中继的功能。其中有一个移动台s ，由于其处于小 区边缘，与基站d 的通信质量下降，从而需要中继的帮助。移动台s 经过一次 中继( 两跳) 与基站d 进行通信。假设此时有k 个能够提供中继的候选节点( 其 1 5 第3 章蜂窝中继系统的快速路由算法 余节点可能处于通话或高速移动的状态而不能提供中继) ，用冠，r ，r r 表示。 在移动台s 进行中继的上行传输之前，必须从蜀，足，心中选择出一个最合适 的节点作为中继节点，也就是选取条从移动台s 到基站d 的最优的两跳路径， 这就是我们考虑的蜂窝中继小区的路由问题。 为了选择一条合适的路径，系统必须要事先获取一些必要的网络拓扑信息。 如何获取这些必要的网络拓扑信息也是路由必须要考虑的问题。由于小区中节 点的实际位置信息往往不易获取，本章以小区里节点之间的无线信道信息作为 选择路由的依据。在下面的讨论中，口媚。是移动台s 与r 之间的无线信道，口。d ， ，_， 是r 与基站d 之间的无线信道，而口是移动台s 与基站d 之间的无线信道。 3 3 快速中继路由方法 3 3 1信令格式 在快速中继路由方法中，我们定义如下一些信令： 中继请求l ( r r e q 1 ) ：由移动台s 向基站d 发出的信令，它要求基站d 给 它提供一条可用的中继路由。i 氓e q1 信令的格式如下，其中，信令类型表明它 是一个i 眦ql 信令，而源地址和基站地址则唯一的区分这条信令。 图3 2r r e 虹l 信令格式 中继请求2 ( 甜适q _ 2 ) ：是由移动台d 向临近的节点广播的信令，其格式如 下图，其中，信令类型表明它是一个础迮q l 2 信令，而源地址、广播地址和基 站地址则唯一的区分这条信令。 图3 3r r e 钆2 信令格式 中继响应信号l ( 鼬也p - 1 ) ：由基站d 向移动台s 发出的信令，如果基站d 找到了路径。则把这个路径告诉移动台s ，如果没有，则通知移动台s 开始移动 台寻路的过程，其格式如下图。其中，信令类型表明它是一个砒也p _ 1 信令， 1 6 第3 章蜂窝中继系统的快速路由算法 基站地址和目的地址则唯一的区分这条信令，路径标志指示基站寻路是否成功， 如果成功，则在“路径 域中提供找到的路径，如果基站寻路失败，“路径 域 就不再出现。 i l 信令类型基站地址目的地址路径标志路径 l l 图3 4r r e p j 信令格式 中继响应信号2 ( i 龇p j ) ：在小区中的节点接收到移动台s 广播的i 眦q _ 2 后，就向基站d 发出的鼬也p _ 2 信令，信令的格式如下，其中，信令类型表明 它是一个心也q j 信令，源地址和基站地址能够唯一的区分这条信令，信道估 计值表示该节点在接收砌汪邮过程中通过信道估计得到的。 图3 5r r e p - 2 信令格式 3 3 2路由过程 如果小区中的某个移动台s 与基站d 的通信质量恶化，需要进行中继时， 就会发起一次路由过程，路由过程如图3 6 所示，包含了基站寻路和移动台寻 路两个步骤，如果基站寻路成功，基站成功的为移动台s 选择了一个中继节点， 移动台寻路的过程就不再进行。 3 3 2 1 基站寻路 基站寻路开始后，由移动台s 发出信令耻也q - 1 给基站d ，申请基站d 提 供一条中继路径。基站d 负责维护一个反映小区内各移动台( 节点) 之间以及 移动台与基站之间信道状况的信道质量表，并基于这个信道质量表为发出中继 请求的移动台提供路由