（计算机系统结构专业论文）无线多跳中继网络资源调度.pdf

摘要 摘要 无线多跳中继网络作为一种新兴网络架构，能够有效扩大宽带无线网络小 区覆盖面积，提高链路质量，屏蔽位雹和移动速度等条件影响为用户提供公平 的高质量无线多媒体服务。然透，数据的多次转发引发了严重的系统容量闻题。 本文研究了中继网络结构特性与系统容量之间的联系，给出提高资源剥羯率的 中继网络q o s 架构，对其核心内容资源调度和准入控制阅题的数学建模、算法 设计和性能分析进行了全面研究。具体研究成果包括： 首先，分析了两跳中继霹络的结构及影嚷系统性能的因素，提基了保证用 户q o s 需求，随躁络拓扑和于扰状况变化动态调整的自适应资源复用调度算法 a r r s 。为进一步研究中继阙络结构与系统容量的量化关系奠定了基础。 其次，深入分析一般化多跳中继网络结构，通过将图论染色理论扩展到加 权混合墨的多重染色w m m c 闻题，建立起中继网络结构特性与系统容量之间 的联系。对w m m c 蠲题进行了形式化定义、分类和加权色数定界的全面研究。 建立起最小化调度时闯为霹标盼中继阏络调度问题和以求解加权色数为目标的 w m m c 闯题的映射。以此为依据，设计了高效的多跳中继网络资源调度算法， 并对算法性能进行了理论分析。 最后，研究了中继网络准入控制阀题，指出系统吞吐量与业务带宽需求的 非线性关系造成中继网络和传统单跳网络准入控制的根本区别。建立了以资源 调度为基础，结合中继选择的中继网络准入控制策略。设计了动态资源预留准 入控制算法d b r a c ，确保中继网络满足多媒体业务q o s 需求的同时，有效的 降低切换业务的阻塞率，并且提高了系统资源的利用率。构造了中继网络业务 流模型，为准入控制策珞性能分析提供理论基础。 关键词：中继网络，资源调度，资源复用，图论模型，染色问题，近似算法， 准入控制，中继选择，资源预留 a b s t r a c t a b s t r a c t a sap r o m i s i n gn e t w o r ka r c h i t e c t u r e ，w i r e l e s sm u l t i h o p 糙l a y 建e t w o 呔c 题 e 盛c i e n t l ye 牲h a n e em ec o v e r a g ea r e ao fb f o a d b 皴dw i r e l e s sa e e e s sn e t w o 嫩，i 搬p v e t h et f a l l s m i s s i o nl i n k sq u a l i t ya n dp v i d ef a i r h i 曲键u a l i t ym u l t i m e d i as e r v i c e s 虹 羔n o b i l eu s e r si g n o r i n g 也e 妇l o e 戤i o n sa n ds p e e 瓠 h o w e v e 笃 搬e r e l 8 y i n go f i l u p l i e 戤e du s e fd 破ab e t w e e 鼓b a s es t a t i o 鼓a n dr e l a ys t a t i o 娃sl e a d sl os e r 呈。驻se 印a e i t y d e g 姐d 鑫l 主。薹1 i nt h i sp 印e f ，w es 纨d yt h ec o 勰e e t i o 珏b e l w e e n 糟l 鑫y 豫储。呔s l 撵c t 辑愆 强dl h es y e mc 印数i 碳e o n s t 趣c l 羚l a yn e 专w o 呔q o s 毅文i l e e 锄汜l oi 辍p v et h e 辖s o 坩e e 呔i l i z 敷i 鼹，强ds l u d yl k 攥o d e l i 粥，a l 曩t 妇ld e s 主g 鼓越dp e 哟强鞠e e a n a l y s i sf o rr e s o u 羚es c h e d u l i 建g 瓢d 鑫d m i s s i 。致e o 魏r o l 。髓l ee o 默量b 氆i o 稻。fo 疆 w o r ka f ea s 岛l l o w s ： f i r 蛙l y ，w e 鼹鑫黟z ol w 。也o p 跫l a y 稳e l w 。呔s t 斑c l 硅勰c h a r a e l e r 主s i c s ，b a s e d 。n 诚i e hw ep r 。p o s e 鑫靛a 鑫鑫岔i v e s 。戳c e 糟珏s es e h e 如l i n g ( a 淑s ) 越g o 蛀饿mw i t h 量l e g o a lo fe 磕勰e i 黩gl 纛es y s 钕ne 神a c 娃y 晒辩l a yn e 泐汰，姚i e hs 弹p o r 专sa 内i 智a 巧 幻p o l o g y 雒纛豫l 鑫ys t a t i o 璐搬o b i l i 移 s e c o 蕊l y ，w ea 黻l y z eg e 秘r a i 獭u l t i 幻pf e l a yn e t w o 撤a f e k e e t 醢r ea 聪e s t 撕l i s h 饿ee o 魏搽e e t i o nb e t w e e l lf e l a y 魏e t w o 呔s c h e d u l i 致ga n d a p he o i 蹦n gb ye x t e n d i n g h ee o l o r i n gp m b l e m 协m ed i r e c t i o no fw e i g h t e dm i x e dg r a p 圭lm u 量t i e o l o r i n g ( w m m c ) w ef 。r m 醢l 鑫_ t e 翻强a l 如f i n 谶o n sa 聪e l a s s i 蠡c a t i o n sf o rw m m ca n d s t u d y 搬eb o u n d so nt h ew e i g 圭l t e de 量1 m a t i cm l m b e r s t k l s ，ar e i a yn e t w o r k s e h e d u l i n gp b l e mt om 赫m i z et 圭l ee o 撇p l e t i o nt i m ei sm a p p e di n t ow m m c w i t h t h eo b j e e to fo b t a i n 主n gt h ew e 主g h t e ( 1c h 确m a t i en u m b e r s b a s e do nt h em a t h e m a t i c a l m o d e l ，w ed e s i g n 圭l i g 圭le 掇c i e n ts c h e i l u l i n ga l g o r i t h m sa n dp r o p o s et h ep e r f o m a n c e a n a i y s i s f i n a l l y ，w es t u d yt h er c l a yn e t w o r ka d m i s s i o ne o n t r o la n dp o i n to u tt h a tt h e n 。n l i n e a r r e l a t i o nb e t w e e ns y s t e mt h r o u 曲p u ta n dt m 箍cc o n n e c t i o nb a n d w i d t h r e q u e s tt e l i st h ea d m i s s i o nc o n 订o lf o rr e l a yn e t w o r k f r o mt h a tf o rs i n g l e - h o pc e l l u l a r n e t w o r k w 奄e s t a b l i s hr e l a vn e t w o r ka d m i s s i o nc o n t r o lm e c h a n i s mb a s e do nb o t h l l i 图暖录 图目录 图1 1中继网络结构和功能4 图1 2 中继网络q o s 架构6 图2 1两跳中继网络1 1 图2 2 接入链貉资源复箱的加权鹜模鹫1 6 图2 3a r r s 算法滚程图1 8 图2 。4s g 算法代码2 2 图2 5s g 算法应用实例2 5 图2 6d s g 算法代码2 6 图2 7d s g 算法虑稍实例2 9 图2 + 84 个孛继站对称分寿中继网络各种调度算法吞致鼙性能比较3 l 图2 96 个中继站对称分布中继网络各种调度算法吞吐量性能比较3 l 图2 1 09 个中继站非对称分布中继网络各种调度算法吞吐鬣性能比较3 2 图2 1 l 减少增加干扰时算法d s g 的吞吐釜性能3 3 圈3 i多跳中继网络3 5 图3 2 中继网终的三元组模璀。4 0 图3 3由中继网络三元纽构造加权混合图模型的过程。4 3 图3 4 加权混合图多重染色颜色分配表及其逆向圈的对偶颜色分配表4 7 图3 5 混合图g 的顶点分层方法5 4 匿3 6 髓s 算法代码5 7 图3 。7l s g 算法代码。6 2 图3 。8 加权混合图多重染色算法平均最犬调度时闻仿真结果。6 8 图3 9 加权混合图多重染色算法平均吞吐量仿真结果。6 8 圈4 1d b r a c 算法中系统预计消耗带宽e e 的计算流程7 6 图4 2 誓豁新( 切换) 鳖务阻塞搴v s 。总业务到达率8 3 图4 ，3r t p s 新( 切换) 业务阻塞率v s 。总业务到达搴。8 4 图4 4n r t p s 新( 切换) 业务阻塞率v s 总业务剑达率8 4 图4 5 系统带宽利用率v s 总业务到达率8 5 圈4 。6r t p s 业务带宽分配不满忌率v s 总业务到达率8 6 v l l 表目录 表2 1 表2 2 表3 1 表4 1 表5 1 表5 2 表目录 i e e e8 0 2 。1 6 j 业务q o s 需求和虑崩1 4 a r r s 算法仿真参数设置3 0 张踊c 阀题分类4 4 d b r 觚算法仿真参数惩置。8 2 加权无向图的多重染色算法性能总结8 7 加权混合图的多重染色算法性能总结8 8 l x 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阕和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： p 0 3 年 第l 章引言 第1 章引言 无线多跳中继褥终懒端l e s sm u 歉谂雌袋e l 帮n e t 蜘攮，篱称中继鼹络，季警兔 一种先进懿宽带无线接入b 建曲a 鼗dw i f e l e s sa e e e s s ，8 w a ) 鼹终架构，凝得了 学术界秘工业界的广泛关注。中继嚼络能够鬓蔽用户位置秘移动速度等条件熊 影响，提供无处不在酶性麓辜越酶无线多媒体服务体验。其榴关技术赡研究、 开发和标准化工终趸在积援展开。中继溺终戆系统设诗和分辑较之传统犟跳宽 带无线接入嬲络菱为复杂。有效匏瓷嚣管理是提禽宽带无线爨络性能魏关键， 丽中继网络采用存储转发( s 弱拯a 巅f o r w o a 撼_ 模式懿多跳结构特缝使褥传统单 跷网络审经典豹资源管理策略不饕适用。函此，宽带无线接入鼹绦觞资源管理 黧歼了薪鲍篇章，需要深入缨致熬舔究。 中继黧络戆资源调度熟s 蛰娃粒s 歉畦鬏l i 臻g ) 器推入控髑强泌i s s 氢潍舶鬣鼢l 稽辅相戏密不可分，共阕构成满足瘸户服务震量( q 落 毋o f s 科i e o ，q o s ) 提高系 统瓷源剽雳率的关键，是孛继溺络资漂管理静重中之重。本文对中继网络熬资 源调度帮准入控制簿题翡数学建摸、算法设计罄缝能分辑进行了全瑟瑟究。进 入具体磷究雨容之蓊，本章首先对中继瘸络瓣产生过程、结稳组成以及资源管 理翡研究走容帮进鼹迸行葱缩概括。 。1率继网络概述 。l 。l 中继网终的产生 用户对无处不在豹高速无线服务麴殷切需求怒避无线通信系统赣着更高传 输速率、更广覆盖范围和支持用户高速移动的方向发展。无线通信网络的历史 最早可以追溯到1 9 4 6 年由美国a t & t 挺供的公众移动毫话服务两络。二十世纪 八十年代末第二代( 2 g ) 遥蔷系统斡形成标态着通信网络进入数字技术辩代，其 代表系统g s m ( g ! o 妇ls y s 搬致o fm o l ec o 礅趣u n e a t i o 觳s ) 除语音业务外已经开 始提供有限的数据业务。进入新千年，新兴宽带无线通信技术更是形成了蓬勃 发展的态势。第三代( 3 g ) 通信系统u m t s ( u n i v e r s a lm o b i l e 强l e e o m m u n i c a t i o n 无线多跳中继避终浚源渭度 s y s t e 糟) 提供的数据传输率达至l 了2 m b i 惦。3 g p p ( 3 撼g e n e r a t i o np 鑫或e m e r s h i p p 删e e t ) 酶h s d 融f l 】系统( 硪曲s p e o dd o w n l i 缺p a c k e ta c c e s s ) 以及基于l 嚣e e 8 0 2 。 6 【2 】协议的w i m a x f 3 1 系统( w o r l dw i d ei n t e r o p e r a b i l i t y 稻rm i c r o 、张v ea c c e s s ) 和w i b r o 【4 】系统( w i r e l e s sb r a o 曲a 商) 理论数据传输率达到数十兆甚至舀兆。3 g 两络的研究和建设尚处在发展之中，i t u r 组织制订第四代( 4 g ) 通信系统f 5 1 需 求的工作又紧锣密鼓地展歼，i e e e8 0 2 6 也随郄成立工作组提供增强版 8 0 2 1 6 m f 6 】协议来迎合4 g 系统的要求。4 g 系统承诺提供游牧用户高达l g b i t s 的数据传输速率，傈证高速移动用户也能享有l o o m b i t ，s 的速率，将为包括语 音、数据和多媒体在内的高性能多类型业务的提供奠定肇实的基础。 在通信系统发展过程中，自二十世纪六十年代末诞生以来，蜂窝( c e i l u l a r ) 网络一直在通信网络架构中占据绝对主导地位。它的概念是将服务区域划分为 多个小区( c e l l ) ，每个小区内根据网络规划将基站( b a s es t a t i o n ，b s ) 布放在合适 的位置以确保在有限传输功率下全面覆盖整个小区，基站与其信号覆盖范围内 的各移动用户( m o b i l es t a t i o n ，m s ) r 直接通信，形成了点到多点( p o i n tt om u l t i p o i 眦， p m p ) 的单弼j ( s i n g l e h o p ) 缀构。然而，这一结构给宽带无线网络的发展带来巨大 阻碍。这是由两方面原因造成的。首先，宽带无线系统的超高传输速率引发了 严重的功率和用户q o s 公平性的问题。给定功率等级，比特能量( b i te n e 蜷y ) 随 数据传输率线性增加，导致信号传输距离成为q o s 的决定性因素，结果大面积 覆盖的小区边缘用户和中心用户q o s 具有很大差异。其次，宽带无线系统工作 所在的离频频段因穿透能力和绕射能力差，导致地形引起的阴影衰落( s h a d o w f a d i 觳g ) 效应非常严重。因此，合理的功率设定和阴影效应的避免必然引发宽带 无线系统单个小区覆盖面积大蝠缩减。例如，g s m 的小区半径为3 5 k m 【7 】，两 根据实际阏络规划所得结聚，w i m a x 系统在市区内的小区半径仪为几公翠【8 】。 简单的解决办法是采题微蜂窝( m i c 1 1 ) 架构，增加基站的布敖密度，结果带 来寒昂的嬲络建设费用，是不可取的。 宽带无线鞠络在先进的无线传输技术发展的同时，期待着一场网络架构的 变革。多影殴m 毽l 曩h o p ) 结构翔传统蜂窝网络的融合是一个有翦景的发展方囱【9 】。 传统上，多魏概念邈现在邀组麴a 娃h o e ) 和对等网攀e ft op e e f ) 的研究中。移动 自缀嬲( m 曲i l ea dh o en e l w o 呔，m a e t ) ，无线传感器网络f w i r e l e s ss e 掇s 篮 n e t w o r k ，w s n ) 1 0 】郡无线网状嗍( w i 列e s sm e 幽n e t 啪呔，w m ) f l l 】都可以纳 入无线多跳网络黪菠畴。多舅i 结构帮蜂窝网络的融合有鼹种方式。 2 第l 章引言 第一秘是众纛h o c 网络和蜂窝嬲络两种模式共存的混合缱网方式，典型的架 构和混合路电协议包括【1 2 。2 0 】。这些系统为移动用户配备a dl l o c 和基础设旎 ( 1 n a s l 粼l 黼) 两种空中接隧使其其有两种工作模式。在a dl l o c 模式下利用移动 用户本身进行中继传输，将高质量的信号传递到低速率区域或将热点小区的业 务转移到相对空闲的邻居小区，以实现提高链路质量、平衡负载和增加系统容 量的舀的。混合组网的缺点不言而喻：系统管理和路由协议复杂；移动终端设 备成本高、功耗大，且由于小型化的需要不利于先进的天线技术和信号处理技 术的应用；系统容量受到中继转发次数的限制，而移动终端的功率有限，对于 扩大小区覆盖的结果不尽理想。 第二种方式是采用专门的中继站( r e l a ys t a t i o n ，r s ) 实现中继功能【2 1 ，2 2 】。 本文所指的中继网络正是这种将中继站作为网络基础设施一部分，利用中继站 在基站和移动用户之间通过无线方式进行数据存储转发的无线网络。i e e e 8 0 2 1 6 成立了专门的8 0 2 1 6 j 2 3 】工作组制定中继网络协议，8 0 2 1 6 m 工作组也 己将对中继网络的研究纳入轨道。中继网络集多种优点予一身：与基站相比， 中继站功能更简单造价更低，它以无线方式和其它网络节点通信，不需要和骨 干( b a c k b o n e ) 网直接连接，易于安装维护，增强了组网的灵活性，同时大大节 约了网络建设成本和运营维护开销；中继站的使用形成了质量好距离短的可视 链路( l i n eo f s i g h t ，l o s ) ，为阴影衰落区域提供良好的信号覆盖：与移动用户相 比，中继站信号传输范围广可以有效增加小区覆盖面积，并且可以应用先进的 天线技术和复杂的信号处理技术优化链路质量，迸一步提高系统容量。众多优 点使中继网络成为宽带无线接入网的有力选择。 1 1 2 中继网络的基本结构 中继网络盘三种网络节点构成：基站，与骨干网连接，是小区志用户和外 部网络的通信接墨，并且对整个小区的资源管理进行集中控制；移动站，即终 端用户；中继站，通过无线方式在基站和用户之阉进行信号存储转发，可分为 工作时位置不变的固定中继站( f i x e dr 譬l a ys t a l i o 轧f r s ) 稻工 睾时位置可变的移 动中继站( m 曲i l er e l 鑫ys 越i o 毽m r s ) 两种。 网络节点间的无线传输链路分为两类：中继链路( r e l a yl i 斌) ，雳于基站与 中继站或中继站与中继站之间的数据传输，分别表示为b s h r s ，r s 付r s ；接 3 第l 章引言 时增大接收信号的信号强度，结果在增强数据信号的同时也增加了噪声；后者， 中继站在转发之前会对接收信号进行解码和重新编码完全消除噪声，相当予数 字转发器( g h lr e p e 越e r ) 、桥接器( b 娃d g e ) 或路蠢器( r 。落懿) 盼功能。目前，宽 带无线网络研究的中继系统通常指解码转发系统。 麸链路资源分配角度，中继鼷络有多种实现形式。可雳资源包括时域( 曩m e d o m 蠢n ) 资源、频域( f 辩q u o n c yd o m a i n ) 瓷源、码域( c o d ed o m a i n ) 姿源或者它 们的各种缝合。从信怠论的角度来看，这些不同类型资源及其分配方式是相通 的。文献f 2 4 2 6 】分别给出了通过时分复用( t i m e d i v i s i o nm 瑾t i p l e x ，h ) m ) 、频分 复孀( f r e q e 魏c y d i v i s i o nm u l t i p i e x ，f d m ) 和码分多址( c o d e d i v i s i o nm u i t i p l ea c c e s s ， c d m a ) 技术实现的中继网络。其中，时分复用资源分配在中继系统的链路闯最 易实现，也最为灵活，是舀前中继网络资源分配的主流研究方向。 1 。2中继网络资源管理及研究现状 早在二十世纪七十年代末和八十年代初，数字中继( d 罾t a lr e l a y i n g ) 技术已 经开始作为理论问题得到研究，文献【2 7 3 1 给出了简单中继信道容量的估计。 遗憾的是，由于当时条件下中继技术缺乏应用前景，该研究一度被中断。直到 进入二十一世纪，随着数字无线技术的成熟和对于高速率大容量的无线系统的 强烈需求的共同驱动，中继技术的研究热潮才重新形成。需要强调一点，传统 a dh o c 网络和中继网络本质上的区别在于前者的目标是在缺乏基础设施的情况 下用户间能够实现相互通信，后者是为了提供无处不在的高速率高容量的信号 覆盖，根本目标不同决定了它们的研究方向和结果的不同。因此，目前为止中 继网络的相关研究结果非常有限，方方面面都亟待突破。这其中，资源管理的 研究是最为重要的部分。 对于无线系统来说无线资源始终是十分稀缺的，而面向连接的宽带无线网 络包括中继网络在内必须确保用户的q o s 。资源管理的目标就是在有限的无线 资源和高质量的用户需求之间寻求平衡，满足每个用户q o s 的同时充分利用资 源尽可能为更多的用户提供接受服务的机会 3 2 】。资源管理通过资源测量、资 源状态确定、可用资源评估和有效资源分配等一系列机制实现这一目标。资源 管理的丰富内涵与系统的资源类型、结构和功能等因素密切相关。对于提供多 业务类型并且支持用户移动性的中继网络，资源管理主要涉及准入控制、资源 5 无线多跳书继飘终资源涯瘦 调度、中继选择、功率控制和切换管理等范畴 2 2 ，3 3 】。 对中继网络来说，尽管提高链路质量、采糟先进的天线技术和信号处理技 术有助于提高系统容量，但是数据在基站与用户之问可能经过一次或多次中继 转发，无可避免的使得中继网络需要多消耗一倍或更多的资源。因此，资源利 用率仍然是中继网络面临的核心问题。图1 2 是我们提出的中继网络的q o s 架 构，该网络提供多业务类型、支持用户移动性并由基站对资源管理进行集中式 控制。q o s 架构的核心是准入控制和资源调度两个模块：准入控制负责对本小 区新产生的业务或来自邻居小区的切换业务的建立请求进行决策，并将成功建 立的连接的基本信息记入数据库；资源调度根据业务连接的基本信息、带宽请 求和系统容量对各种类型的传输数据进行调度。准入控制用来控制系统的业务 量，是资源调度能否顺利实施的基础；资源调度反过来又决定了准入控制策略 的设计。两者相辅相成、密不可分，共同构成满足用户q o s 提高系统资源利用 率的关键。设计有效的资源调度算法和准入控制策略是中继网络资源管理问题 的重中之重，构成本论文研究的两大核心内容。 资源淡度 l 行7 卜j 行链路数据滤 图1 2 中继网络q o s 絮构 资源调度从结构上可按适合两跳或多跳中继系统进行划分。有研究【3 4 ，3 5 】 指出中继季i 数的增加不仅会带来数据时延的增大，还减少整个传输路径上有效 6 无线多跳中继阚终资源湮痰 地向相邻小区基站进行询问，获取潜在移动用户的信息，根据切换业务的具体 需求决定资源预留。文献 5 0 】为各类型的业务没定不同的准入概率，作为它们 准入系统的优先级。文献【5 1 ，5 2 】中提供了i e e e8 0 2 1 6 系统的准入策略，该系统 中包含实时变速率( v a r i a b l e b i tr a t e ，v b r ) 业务，但这些策略仅以可用带宽能 够满足各业务的最小保证速率( m i n i m u mr e s e r v e dt r a 掰cr a t e ，m r r ) 作为准入 依据，因而变速率业务的带宽需求无法得到有效保障。 中继选择是中继网络性能提高的重要因素之一【5 3 】。文献【5 4 ，5 6 】从信息论 角度出发对中继选择问题进行了理论研究，但是没有给出具体的算法。s r e n g 等【3 3 】提出了基于距离、路径损耗( p a t hl o s s ) 和信噪比( s n r ) 的中继选择策略。文 献 4 2 ，5 7 】提出了基于用户频谱效率的选择策略。以上的中继选择的研究都是关 注目标接入用户的性能优化。而我们的准入控制中的中继选择强调的是系统整 体的性能，以保护系统现有用户的q o s 为前提尽可能准入更多的用户以提高系 统资源利用率。两者的优化目标是不同的。 3 本文的研究思路和贡献 本文的研究目标是对中继网络的资源分配问题进行深入分析，建立中继网 络特性与系统容量之闻的联系，并最终设计出高性能的资源调度算法和准入控 制策略，形成坚实的q o s 保障体系。 考虑到资源调度决定了准入控制策略的设计，本文先对调度阅题进行研究， 再以此为基础设计准入控制。研究调度闯题时，本文采用以篱单的两跳结构为 切入点，再扩展到一般化多跳结构的逐步深入过程。 要是化中继嬲络特性对资源分配的影响，蓄先需要建立中继网络系统模型。 个好的数学模型必须满足两个标准：必须具有一般性的特点以抓住闻题实质， 必须易予分析。在调度超题上，本文把握住无线传输链路这个核心磅究对象以 及与其樱关的链路调度顺序、链路间干扰情况和链路资源消耗三个关键因素， 从雨将资源调度与图论染色闯题建立起映射。在准入控制上，本文以多态马尔 可夫链为基础，在多类型业务的业务量和系统预留带宽以及系统总带宽阍建立 联系，进而推导出业务阻塞率和业务量、系统预繁带宽以及系统总带宽瓣的量 化关系。 在一。般化多舅! 中继网络的调度问题建模过程中，我们抽象基静新的窝论 8 无线多跳中继霹终资源谖度 3 研究了中继网络准入控制问题，指出系统吞吐量与业务带宽需求的非 线性关系造成中继网络和传统单跳网络的准入控制的根本区别。建立 了以资源调度为基础，结合中继选择的中继网络准入控制策略。设计 了动态资源预留准入控制算法d b r a c ，该算法确保中继网络满足多媒 体业务q o s 需求的同时，有效的降低切换业务的阻塞率，并且提高了 系统资源的利用率。构造了中继网络业务流模型，为准入控制策略性 能研究提供理论基础。 本文的研究表明，中继网络的多珧结构特性在其资源调度和准入控制策略 中起剑了决定性影响。只有对中继网络的结构进行深入分析，才能够设计出高 效的资源调度和准入控制算法。 。4内容组织 论文从中继网络产生带来的网络架构革命性突破及其对宽带无线网络发展 的深远影响和意义出发，在第l 章分析了中继网络的基本结构组成以及资源管 理的重要内容和研究现状，指出中继网络资源管理课题面临的机遇和挑战，并 总结了本文的研究思路和贡献。 第2 章研究两跳中继网络的资源调度阀题。分析了两跳中继网络的结构及 影响系统性能的关键因素，提如了保证用户q o s 需求的两级调度策略，将其中 的关键环节抽象成加权图的多重染色问题并设计出乎衡算法性能和时间复杂度 的染色算法，从丽形成高性能的两跳中继网络调度算法a r r s 。 第3 章研究一般化多跳中继网络的资源调度阀题。深入分析一般化多跳中 继网络结构，为其构造加权混合图模型，建立起最小化调度时间为目标的中继 网络调度问题积以求怨加权色数为昱标的w m m c 问题的映射关系，对w m m c 闯题进行形式化定义、分类和加权色数定界的全西研究，设计了具有不同约束 条件的中继网络资源调度的高效算法，并对算法进行性麓分柝。 第4 章研究中继网络准入控制问题。设计了以资源调度为基础，结合中继 选择的中继网终准入控制策略。设计了确保中继网络满足多媒体业务0 0 s 需求 并曼有效的降低切换业务阻塞率的动态资源预罄准入控制算法d 8 r a c ，构造 了中继黼络煌务流模型从两建立准入控制策略的性能研究理论基础。 第5 章总结了全文并对进一步的研究提出展望。 1 0 无线多跳中继鞠终资源漫疫 可以适合各种中继站的规划方法，具有灵活性强的优点，是主流研究方向。分 频策略【4 l ，4 2 】研究成果较少，只局限于中继站对称分布且拓扑不变的静态网络 结构。d s c h u l t z 等【3 6 】基于曼哈顿模氆提出了等分时隙e t s 法。其小区设置 由中心处的1 个基站和周围对称分布的4 个固定中继站( f r s l 4 ) 组成。e t s 的 时间帧结构中，部分时隙用于基站和用户之间的直接通信b s ”m s ；其它时 隙被等分为4 段，分别用于各中继小区的中继传输b s h f r s 和接入传输 f r s ”m s 。e t s 中不存在资源复用，资源利用率低。文献 3 7 】进一步提出利用 空间独立性s i 提高系统容量的概念。空间独立性是指两个或多个中继小区由于 地形原因( 如图2 1 中的r s l 和r s 2 ) 完全互为阴影区域，则它们同时通信互不干 扰。s i 比e t s 改进之处在于4 个中继小区( f r s l 。4 ) 内的通信可以两两同时工作。 s i 的缺点是局限于曼哈顿模型的布网模式，且没有考虑到各中继小区带宽需求 的差异。w - pc h c n 等【3 8 】建立了中继小区间通信的干扰关系的定义和生成方法。 进一步，文献【3 9 】给出了基于干扰关系对中继站进行资源复用调度的思想，提 出相互于扰的中继站要分时调度，整个时间帧中，每个中继站分配到的时隙段 被其视为主区间( p r i m a r y ) ，而其它时隙被其视为次区间( s e c o n d a r y ) ，中继站以 高优先级在主区间调度，以低优先缴在次区间调度。使用动态生成干扰关系的 方法打破了调度对中继站布局信息的依赖。但是该文献并未给出于扰关系和调 度结果具体的映射方法和算法，也没有指出中继站的带宽需求在资源复用调度 中的作用和影响。p e t e rw a n g 【4 0 】提出了结合功率控制的信道复用思想。每条下 行信道信号覆盖形成以中继站为中心的圆，分属相邻中继站的两个信道的信号 覆盖可能产生交叠，交叠恧积越大表示干扰越大。该文献提出通过控制中继站 功率以减少信号覆盖范围，通过协调棚邻中继小区调度以减少干扰。尽管信道 级别的资源复用可能会带来更大幅度的系统吞吐量提升，但功率控制复杂，相 邻的中继小区间信息交互开销大。文献【4 l 】给怨了一个位于中心的基站以及周 围分别有3 个和6 个对称分布的圈定中继站的强种组网方案。文献【4 2 】就后 种方案分析了频率复用因子( f 盯) 分别为l ，2 ，3 ，6 的资源利用率。 本章研究与以往工作的区别在于：其一，为掰跳中继网络建立了加权图模 型，该模型涵盖了中继网络调度所需的带宽信息积羼频干扰信息，基于浚模型 设计的调度方法能够对嚣熬中继网络的拓扑和规模自适应，适合异构的非对称 的缀阚方式，支持移动中继站带来的嬲络拓扑动态改变，适应天气情况地理环 境等弓 超的中继小区间通信干扰情凝的变化；其二，设计了具有晦缴调度模式 1 2 第2 章两跳中继嘲络调度 的离适应资源复罱调度a 躲s 算法，能够充分利用系统资源，有效保证各业务 连接的q o s 需求。 本章组织如下。2 2 节分析掰跳中继蹰络系统结构，构造加权圈模型。2 3 节给出了a r r s 算法的具体描述。2 4 节给出了两类加权图多重染色闻题的算法 设计和分析。2 5 节对a 敞s 算法性能做进一步仿真验证。最后，在2 6 节进行 本章小结。 本章篇到的符号和术语总结如下： 表示自然数集。【f 】表示包含 f ，+ k 。，) 的自然数区间，其中毛歹， 并且f ，。| x i 表示集合x 包含的元素个数。 g = ( y ，) 表示无向圈，其中y 是顶点集合( v e r t e xs e t ) ，e 是无向边集合 ( u n d i r e c t e de d g es e t ) 。本文仅考虑不含任何环( 1 0 0 p ) 或重边( m u l t i p l ee d g e ) 的有限 图。陋，v 】表示与“和v 关联的边。设s 矿，则( u ，露) 表示子集u 中的顶点以 及边集e 中两顶点都在u 中的边构成的的图g 的导出子圈。( g ，) 表示加权图， 其中国是图g 的顶点权向量，顶点v y 的权表示为彩其值是自然数。 加权图( g ，国) 的多重染色o ：y 丰2 是顶点集合到自然数的幂集的映射， 它为每个顶点v y 分配i ( v ) i = 出，个不同的自然数即颜色( 可供染色的颜色是 一个有序集合，各颜色由其在有序集中的自然数序号表示，因此本文对颜色及 自然数不加区分) ，同时要求满足任意两个与同一条边关联的顶点分配到的颜色 没有交集。( v ) 中，顶点v 分配到的最小颜色记作( v ) = m i n f 由( v ) ) ) ，最 大颜色记作厶( v ) = m a x fe ( v ) ) ) 。 2 。2 系统描述及数学建模 本节分析两跳中继网络结构及影响系统性能的关键因素，将保证业务q o s 需求的调度问题分解为中继链路调度和接入链路调度两个层次，并将中继链路 调度转化为加权图的多重染色问题 2 2 。1 系统描述 中继网络的小区规划矗接决定其调度算法的设计难度和性能。规鲻主要涉 及中继眺数、中继站布局( 个数和放置位置) 以及链路资源分配方式三个方面。 1 3 第2 章两跳中继嘲终渭度 和w e b 浏览。影响调度的3 个关键q o s 参数：最大持续速率( m a x i m 戳s u s t a i n e d n a 接er a t e ，m s r ) 和最小保证速率( m i n i 搬碱r e s e e d 髓a 舔cr a t e ，m r r ) 分剐 对应各业务带宽分配的上下界，最大时延( m a x i m u ml a t e n c y ，m l ) 是实时监务可 容忍静时延的上界。 2 。2 。2 建立接入链路资源复用的加权图模型 中继网络中数据在基站与用户之间可能经过一次或多次中继转发，降低了 系统容量。资源复用是提高资源利用率的必由之路。本小节讨论两跳中继网络 资源复用问题的建模。 由于网络节点全部采用全向天线并且各链路使用楣同频率进行分时传输， 基站与各中继站的通信只能依次进行，也即中继链路间无法实现资源复用。因 为两跳中继系统所有中继站都是直接与基站通信，所以当基站与某一个中继站 通信时信号覆盖了所有中继站，即中继链路和接入链路间也不存在复用的可能。 考虑到各中继小区内基站或中继站与用户进行通信时，信号仅覆盖该中继小区， 于是，我们利用多个中继小区同时同频工作实现复用，篱称接入链路资源复用。 接入链路资源复用就是为各中继小区分配其所需时隙，同时保证具有同频 于拢的中继小区不会分到相同的时隙。影响接入链路姿源复用的关键因素有两 个：其一是中继小区之间的同频干扰，它决定了不冠的中继小区可否同时调度； 其二是各中继小区的带宽需求，它决定了调度结果所需的资源数量。 于拢关系的确定主要有两种方法 3 8 ；静态估计方法适用子干扰关系不随 时阆变化的静态网络，干扰关系在网络形成的初期由各中继站的信号覆盖范匿、 干扰影响程度的定义，结合用户分布悠算得到，并且在网络运营疑问保持不变； 动态测量方法适用于干扰关系可畿改变的网络，基站周裳性地为每个中继站分 配一个专属时隙用来发送信号，同时其它的中继站测量该信号对各自中继小区 蠹逶信的干扰程度，并把测量结果报告给基站，这样基站就可以获得整个小区 所有中继小区间干扰的全局情况。如蒋所述，本章所研究的中继网络支持掰络 拓扑动态变化，所以我们采用动态测量得到干扰关系的方法。 中继小区的带宽需求套该中继小区内所有业务连接砸a 燕ee o n n e c t i o n ) 的带 宽需求之和来表征。因为雳户在翮络晕分布的不均匀性，各业务连接q o s 需求 的多样性，以及各无线链路状况的不断变化，所以，各中继小区所需的带宽必 无线多跳串继阚终资源爱度 然是非一致的并且不断变化。 对于一个拥有甩个中继小区的中继网络，已知各中继小区的带宽需求以及 相互间的干扰关系，可以用一个包含船个顶点的加权图( g ，m ) 来为该小区的资源 调度建立图论模型。图g 的个顶点和个中继小区相对应；顶点v 矿分配的 权值，为其对应的中继小区的带宽需求；任意两个顶点甜，v 矿之间有边相连 ( 即 甜，v 】e ) 当且仅当它们对应的中继小区之间存在着同频干扰。图2 ，2 对应图 2 1 所示中继网络的接入链路资源复用加权图模型，其中每个圆圈分别标识了各 中继小区的序号及其带宽需求，边表征同频干扰关系。这样就建立了中继小区 及其带宽需求、干扰关系与加权图的映射关系。由此，接入链路资源复用就转 化为加权图( g ，彩) 的多重染色问题。 图2 ，2 接入链路资源复腰鲍加权图模型 2 3自适应的资源复用调度算法 基于两跳中继嬲络的系统描述和建模，本节给出裔适应资源复恩调度算法 a r r s 。我们仅以下行链路为例对a 爻r s 进行攒述，该方法同样适合上行链路。 假设中继网络的系统总带宽为e ，中继小区及其带宽需求、干扰关系由加 权图( g ，缈) 表示。a 躲s 算法分为中继链路和接入链路两级进行调度：中继链路 调度，基站与各中继站依次通信，使用的带宽记作e r m o 接入链路调度，基站 或中继站与啻接被它们服务的用户进行通信，通过复用达到提高资源利用率的 嚣的，其带宽记作c 触。；下行链路子帧剩余带宽记作霆= c 一( c r 。幻。十e a 一) ， 参见图2 5 ( b ) 。 a 赇s 算法需要解决的两个关键点是：确定备中继小区的带宽需求以及确 定接入链路资源复用方法。 1 6 第2 章两跳中继网络调度 各业务类型q o s 需求的多样性为中继小区带宽需求的确定增加了难度。尤 其是实时变速率业务瞧p s 和嚣煅，s ，它们的带宽需求在最大持续速率m s r 和最 小保证速率m r r 之闻不断交化，并且本身具有时间敏感性的特点。如果依据 m r r 绘其分配带宽，意味着该业务q o s 长期处于最低限度的满足；如果依据 m s r 给其分配带宽，系统资源的利用率就会很低，也失去了变速率业务产生的 意义。因此难以直接确定中继小区的分配带宽同时保证业务的q o s 和系统的资 源利用率。我们参考传统的革魏网络下多业务类型带宽分配策略( 如文献【5 2 】中 的i e e e8 0 2 1 6 系统调度方法) ：根据各业务的时间敏感程度为各业务设定分配 优先级按u g s ，r t p s ，e r t p s ，n r t p s ，b e 顺序依次降低，首先满足u g s 的固定带宽需 求m s r 以及其它各业务的m r r ；若系统还存在剩余带宽，再按优先级 r t p s ，e r c p s ，艇p s ，b e 的顺序根据它们的最大延迟( m l ) 或业务权重进行剩余带宽 再分配以迸一步满足它们的q o s 需求。考虑到c 触。与各中继小区带宽需求之 间是非线性关系，无法将剩余带宽一次性再分配完毕，只能通过循环的方式多 次分配，使再分配的带宽值逼近r 达到高效利用资源的目的。 接入链路资源复用抽象为加权图( g ，缈) 的多重染色，该问题的求解直接影 响a r r s 调度算法的性能，决定着中继网络的系统吞吐量。考虑到该问题的重 要性和复杂性，我们将在下一节对其进行专门研究。 基于上述基本思