（信号与信息处理专业论文）基于时分复用的无线网络分组调度算法优化研究.pdf

南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档； 允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以 采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文 的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 涉密学位论文在解密后适用本授权书。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ 南京邮电南京邮电大大学学 硕士学位论文摘要硕士学位论文摘要 学科、专业： 工科 信号与信息处理 研究方向 ： 现代通信中的智能信号处理 作 者： 2009 级硕士研究生 田绪俊 指导教师： 邱晓晖 教授 题 目： 基于时分复用的无线网络分组调度算法优化研究 英文题目：research on the packet scheduling algorithms optimization of wireless network based on tdm 主 题 词 ：无线网络 分组调度 服务质量 吞吐量 公平性 key words: wireless network; packet scheduling; service quality; throughput; fairness 南京邮电大学硕士研究生学位论文 摘要 i 摘摘 要要 当今社会，互联网与移动通信已成为人们生活中的重要组成部分。无线网络是近年来新 发展的产物，通过无线网络资源的调度，可以保证各类业务的服务质量要求。根据业务类型 不同，可以将无线网络的业务分为非实时和实时两类。 对于非实时业务，基于统计公平的时间调度算法可以实现加权的服务时间份额公平性， 但是也存在不足，它只能使用户的服务时间份额随权值变化，却不能保证平均数据传输率也 与其权值呈对应关系。本文在统计公平调度算法的基础上进行改进，保留最大相对信噪比与 虚拟时间的因素，再加入用户的平均数据传输速率，三者相结合共同决定算法的调度结果。 通过平均数据传输速率随调度情况的自适应调整来实现平均数据传输速率的加权公平。同时 在算法仿真中对参数做了具体分析，并给出参数选择的最佳值。 对于实时业务，机会的实时业务调度算可以获得较好的信道利用率，且对信道条件较好 的用户可以在短时间内给予响应，不足的是信道条件较差的用户需要在相对较长的时间内才 能获得服务响应。针对此种缺陷，文中将机会的实时调度算法的判决条件中加入了用户平均 数据传输速率，通过平均数据传输速率的调整来削弱信道条件对判决结果的过度影响，使信 道条件较差的用户也能在较短的时间内获得调度。 对于以上提出的两类改进算法，文中从理论上做了充分的分析，同时进行仿真实验的验 证。文中将这两种改进算法与经典调度算法和后来研究人员提出的算法分别进行比较，通过 仿真证明这两种改进算法在性能上都得到了显著提高。 关键字：关键字：无线网络 分组调度 服务质量 吞吐量 公平性 南京邮电大学硕士研究生学位论文 abstract ii abstract now, the internet and mobile communications become an important part of peoples lives. the wireless network is a new product in recent years and there are kinds of business applications in the internet. according to different type of business, business on wireless network can be divided into two types: real-time business and non-real-time business. the difference between these two types of business is reflected on the time delay requirements. for non-real-time business, some researchers put forward statistical fairness based opportunistic scheduling. this article improves on fair scheduling algorithm based on statistics. it retentions the maximum signal-to-noise ratio and the virtual time, and then adds users with an average data transfer rate. through the average data transfer rate with adaptive adjustment of scheduling results achieve an average data transfer rate of weighted fair. for real-time business, researchers present a scheduling algorithm for real-time business opportunity based on the basis of classical algorithms. this algorithm can achieve good channel utilization, and users with better channel condition can be responded in a short time. but, users with poor channel conditions need to be responded in a relatively long time to get the service. by adding the average data transfer rate into judgment, the adjustment of the average data transfer rate can weaken the channel conditions influence on the judgment results. this enables users with poor channel conditions be scheduled within a relatively short period of time. it provides better performance for all the users. the two improved algorithms are theoretically proved. it also requires experimental validation of the simulation. by simulation, it proved that the improved algorithms are better than the other algorithms. finally, it summaries the whole text and gives the direction that are not studied in this article. keyword: wireless network; packet scheduling; service quality; throughput; fairness 南京邮电大学硕士研究生学位论文 目录 iii 目目 录录 摘 要 . i abstract . ii 目 录 . iii 第一章 绪论 . 1 1.1 无线网络概述 . 1 1.2 研究背景与意义 . 3 1.3 分组调度算法简介 . 4 1.4 本文的结构安排 . 7 第二章 分组调度算法概述 . 8 2.1 非实时业务分组调度算法 . 8 2.1.1 循环调度算法 . 8 2.1.2 公平吞吐量调度算法 . 9 2.1.3 最大信噪比调度算法 . 10 2.1.4 最大相对信噪比调度算法 . 10 2.1.5 比例公平调度算法 . 11 2.1.6 加权循环调度算法 . 12 2.1.7 基于统计公平的时间调度算法 . 13 2.2 实时业务分组调度算法 . 15 2.2.1 多载波比例公平调度算法 . 16 2.2.2 指数比例公平调度算法 . 16 2.2.3 修正的最大加权时延优先调度算法 . 17 2.2.4 机会的实时调度算法 . 19 2.3 本章小结 . 21 第三章 非实时业务算法改进及仿真 . 23 3.1 系统仿真模型 . 23 3.2 仿真工具 . 24 3.3 仿真小区模型 . 26 南京邮电大学硕士研究生学位论文 目录 iv 3.4 加权时间公平算法 . 28 3.4.1 算法描述 . 28 3.4.2 算法分析 . 29 3.5 算法仿真 . 31 3.5.1 与经典算法比较 . 31 3.5.2 与统计公平算法比较 . 36 3.5 本章小结 . 41 第四章 实时业务算法改进及仿真 . 43 4.1 队首分组等待时间递增算法 . 43 4.1.1 算法描述 . 44 4.1.2 算法分析 . 45 4.2 算法仿真 . 46 4.2.1 与经典算法比较 . 46 4.2.2 与实时的机会算法比较 . 49 4.3 本章小结 . 50 第五章 总结与展望 . 51 5.1 论文总结 . 51 5.2 展望 . 53 致谢 . 54 参考文献 . 55 攻读研究生期间发表的论文 . 59 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 随着互联网技术的快速发展，网络中的用户越来越多，业务种类越来越复杂，一些如视 频和多媒体应用等高速业务比语音等基本业务的使用更为频繁，人们对这类业务的要求也越 来越高，因此能够提供这些业务的网络发展迫在眉睫。有线网络已普遍存在，却因设备、成 本等各方面的限制不能满足人们日益增长的需求。 未来， 无线网络的发展更值得人们去研究。 当前研究的重点是设计能够满足多种业务服务质量(qos，quality of service) 1要求的无线网 络，如何利用有限的资源进行调度，设计出最优的网络以支持不同 qos 的服务，网络中分 组调度算法的研究成为无线通信网络发展的关键，本文是针对时分复用条件下无线网络中的 分组调度算法优化进行研究。 1.1 无线网络概述无线网络概述 无线网络2，顾名思义，即是以无线方式非常便捷地连接设备的网络。使用者无论在任 何时间、任何地点都可以随意地访问网络资源，不受设备连接线缆、电源设备等限制。本文 主要讨论无线局域网，即 wireless local area network，wlan3。无线局域网的发展不仅推 动网络技术的进步，也让人们的生活方式发生巨大改变。人们可以用无线设备，如手机，笔 记本电脑等网络设备在覆盖无线信号的任何地方访问网络资源，不会因为没有电话线或者没 有网线而无法使用。 时代发展日新月异，传统的有线网络已经越来越无法满足人们的要求了，因此无线网络 的发展有它肥沃的土壤，也有其必然性。随着无线技术在生活中的广泛应用，无线局域网的 发展空间逐渐增加。人们有需要，就会去研究，人们有技术，就会研究出成果。现阶段，无 线网络的研究水平已经到了一定的高度，尽管在有些方面还不如有线网络，但近年来无线网 络的技术发展日益成熟稳定，产品种类丰富多彩，它正以方便快捷、简单灵活的优点在网络 应用中充当越来越重要的角色。 新兴技术的发展往往与军事相关，一个国家的军事研发力量代表了这个国家的技术发展 水平，无线网络的起源也与军事相关。第二次世界大战期间4，对于信息资料等的传输还不 是很方便，单纯靠人力传递费时又费力，于是美国陆军利用无线电传输技术研发出了一种新 的信息传输方式，采用无线电信号加密进行资料的来回传递，这样，不仅在传输形式上更加 方便，省时省力，传输的可靠性也得到了保证。后来，许多学者受到这项无线电加密传输资 料技术的启发， 期望在人们的日常生活中也能如此方便快捷且有效可靠地进行数据传输。 1971 年，当时有很多人对无线网络的研究十分感兴趣，夏威夷大学的一个学者创建了一个称为 南京邮电大学硕士研究生学位论文 第一章 绪论 2 “alohnet” 5的无线电通信网络，虽然这个网络只用很少的 7 台计算机组成，采用简单 的双向星型拓扑结构连接， 但是却能横跨夏威夷的四座岛屿， 是无线网络的最初雏形。 从此， 无线网络正式诞生。 无线网络与有限网络有很大的区别，因为它特有的网络架构和形式，它具有以下特点6： （1）网络设备可灵活移动。在有线网络中，受网络位置的限制，网络设备的安放位置不 能随意，就像电话需要在有电话线接口的地方放置。但无线网络有所不同，因为其不受传输 介质的限制，不需要电线光缆等，在区域内的任一地点，只要有无线信号覆盖，无线设备都 可以接入到网络当中，例如手机只要在有信号的地方就能使用。同样地，无线网络中的网络 设备可以任意移动位置，这也是它的一个优点，当用户连接到无线网络中以后，他可以随意 移动，而且在移动的过程中不会与网络断开，仍然可以通畅地访问网络资源。当用户抱着笔 记本在无线网络覆盖范围内任意走动却还能保持网络畅通时，无线网络的优点就充分体现出 来了。 （2）网络规划和调整便捷容易。对于有线网络来说，网络结构改变或者使用地点发生变 化时，以前的网络都可能无法再使用或者需要做很大调整才能重新使用，到新的地点也可能 需要重新建立新的网络。如，一个小区需要重新规划，它之前所建立的电话线路或者网络线 路都需要按新的小区结构重新调整，这都是一个浪费人力、物力等资源的过程，而无线网络 大可不必如此，它可以尽量减少或避免此类情况的发生。上例中，小区需要重新调整，但小 区中的基站等设备完全可以继续使用而不会影响用户的需求。因此，相比有线网络来说，无 线网络整体更容易进行重新规划调整。 （3）设备安装容易操作。对于某个区域的无线网络，一般只要安装一个或多个接入点设 备，就可以使信号覆盖整个区域，远远没有有线网络那么麻烦不易，无线局域网可以免去或 最大程度地减少网络布线的工作量，这对于建立网络使用的成本来说可以大大减少。 （4）网络容量结构扩展简单易行。当一个区域内的人数不断增加，无线网络的使用就大 大增加，其容量也同时需要扩展。基于多种配置方式的无线网络，可以很快使系统容易得以 增加，从小型局域网，只有几个用户，到大型网络，成千上万的用户，无线网络都可以迅速 实现。同时，在不同的区域间移动时，无线网络依然可以提供质量不变的服务，这是有线网 络无法做到的。 （5）故障定位迅速容易。当网络发生故障时，对于故障的检测当然是越简单越好，越迅 速越好。对于有线网络，一旦出现故障，诸如线路连接不良、设备故障等，由于网络结构比 较复杂，而且网络部署错综复杂，线路检修一般很难，付出的费用也是很高，而且需要耽误 南京邮电大学硕士研究生学位论文 第一章 绪论 3 很长的时间。无线网络不需如此，它的故障定位很容易，且在故障确定了以后只需要更换故 障的设备就可以使网络信号立刻得到恢复。 与有线网络相比，无线网络具备了以上很多优点，但事物的特性往往都是双向的，给无 线网络带来如此多优越性的特点也使它产生了无法避免的缺点，也是人们需要继续研究的方 向。 首先，从安全性来说7，无线网络是利用无线电波来进行数据传输的，不需要建立物理 上的连接通道，而无线信号是发散传播的，不是单单只有用户自己可以接收到信号，别人也 可以。因此，如果不采取严格的加密措施，很容易造成个人信息的泄漏或者信息传输的丢失 等情况。 其次，从性能上来说，无线局域网赖以生存的无线电波是通过空气这一介质来传播的， 这些电波通过无线发射装置进行发射，而空气中的车辆、建筑物、树木和其它障碍物都可能 阻碍电磁波的传输，所以会影响网络的性能。 另外，无线信道的传输速率与有线信道相比要 低得多，且稳定性也差很多，因此需要稳定快速的传输数据时是不适合使用无线网络的。 1.2 研究背景与意义研究背景与意义 本文主要探讨的内容是无线网络中分组调度算法的改进研究。对于有线网络的研究历史 悠久，迄今为止，它的分组调度算法已经形成体系并达到了一定的水平，算法的种类很多， 也各有各的优缺点。无线网络的发展比有线网络更晚，且技术更为抽象，令人难以理解，因 此研究成果远不如有线网络那么成熟稳定。有线网络链路带宽恒定8，传输速率也很稳定， 所以有线网络的分组调度算法能够很好的满足用户对吞吐量和时延的要求，可以在用户认为 较短的时间内为他们提供良好的有效性与公平性保证，从而能够最大程度地满足用户的服务 质量需求。然而，由于无线网络具有有线网络所没有的特殊性，若对有线网络的分组调度算 法不做任何改变直接在无线网络中使用，这基本上是不可能的，对无线网络分组调度算法的 深入研究是非常必要且不可避免的。 如前所述，无线网络与有线网络的最大区别在于网络中传输介质不同，无线网络的传输 介质是空气，而空气中有许多障碍物，导致其具有很强的时变特性，即无线网络中移动用户 的信道条件随时间而变，受多径、阴影等衰落以及各种损耗的影响9，表现更为明显。在以 往研究的无线网络分组调度算法中，一般把无线信道看作马尔科夫模型10或者泊松模型11， 信道建模简单，例如马尔可夫链模型只具有 0 和 1 两种状态，处于状态 0 时，相当于信道是 错误无效的，无法传输任何数据，整个信道的容量为 0；而处于 1 状态时，信道是正确有效 南京邮电大学硕士研究生学位论文 第一章 绪论 4 的，信道带宽可以全部利用，信道容量达到最大。这是一种较为简单的信道模型，在以后发 展的较为复杂的业务需求下往往无法使用。 后来有研究人员提出基于多用户分集(multiuser diversity)的“机会调度” (opportunities scheduling， os)12概念， 它是起源于一位学者 knopp 对一个无线蜂窝小区的研究。 在研究中， knopp 提出了“多用户分集”13的概念，即在同一时刻，每个用户的移动方式、与基站的距 离位置以及受到的干扰大不相同，因此信道条件具有很大差异，它们之间可以视作互相独立 互不干扰，这就是多用户分集的效应。那么，在一个许多用户共享信道的无线网络中，若采 用机会的调度算法，可以充分利用信道条件的时变特性，因为当网络中有许多用户时，每个 用户信道条件的变化相互不受影响，在许多变化着的信道条件中，在每个时刻选择较好的信 道条件用户的机会和概率也就越大，在整个传输过程的大部分时间中，信道都是获得较好的 数据传输速率，从而整个通信系统的容量也就越大。时变特性是无线网络所独具的特性，正 是因为这一点导致了网络的许多性能上的缺点，而机会调度算法14可以将这一点加以利用， 转化为调度算法中的有利条件，尽量选择信道条件处于峰值的用户进行传输，显著提高了无 线链路的利用率，这对于无线分组调度算法的研究具有十分重要的意义。 1.3 分组调度算法简介分组调度算法简介 前文提到，与有线网络相比，无线网络具有很大的特殊性，所以要将有线网络中的分组 调度算法有效地引入无线网络，就必需充分的考虑无线网络的特殊性。这些特殊性主要有下 面列举的这些15：高的误码率和突发错误，无线链路容量与位置相关，与时间相关，有限的 带宽，用户的移动性，功率受限等。考虑到无线网络具有这些特殊性，分组调度也有其具体 要求，在设计无线网络的分组调度算法时，必须兼顾到以上这些特点，具体阐述如下。 (1) 链路可变性 无线网络和有线网络的主要区别就是“有”与“无” ，即传输介质的不同，具体就体现到 无线网路的传输链路可变性更强。有线网络依靠高质量的传输媒质，数据传输错误的概率非 常低。但是，无线网络的传输介质是无处不在的空气，由于干扰、衰减等因素，信道条件在 随时变化，因此传输质量也有很高的可变性。在某些特殊情况下，如很突发的错误，一个无 线链路有可能连一个数据包都不能成功的传送， 这是极其恶劣的信道状态。 除了时变特性16， 无线网络的信道质量还与位置相关，同一时刻不同位置的信道条件好坏是不同的。在同一时 间，无线网络中的基站可以同时和几个不同的移动设备进行连接，而各个移动设备由于不同 的位置， 信道条件也有所不同， 与基站的通信质量也因此不同， 一些用户的通信质量非常好， 南京邮电大学硕士研究生学位论文 第一章 绪论 5 而有的用户通信质量非常差。此外，在无线网络中，用户设备的移动非常灵活，这同时也增 加了信道条件的变化因素，这就对调度算法提出进一步要求，必须有动态有效的调度机制来 处理这些与位置和时间有关的信道质量变化。 (2) 服务质量 无线网络为不同类型的业务提供不同的服务，对这些不同类型的业务需要提供不同的服 务质量保证。因此，在设计无线网络系统中，就必需保证不同类型的业务能获得不同的 qos 支持。为了达到这个目标，调度算法中必须要有相应的机制来实现。在不同的调度模型中， 保证 qos 的机制也是不一样的17。当然，在一个信道质量经常存在问题的链路上，保证业务 的 qos 是有一定难度的。然而只要物理信道质量恶化不超出一定的门限，对于在其上的业务 的 qos 是应该加以保证的。 (3) 公平性 对于有线网络的传输媒质，可以认为它是完全无错的，那么对于一个传输数据流来说， 分配的服务速率就是实际的传输速率。然而，在无线网络的调度策略中，公平性问题的处理 更为复杂。因为无线信道的时变特性，有时候是不稳定的，若某个用户需要传输数据，但是 可能此时无线链路处于错误的状态，如果数据已经传输了，接收方却不能正确接收，那么信 道传输就是浪费了。考虑到这样的问题，推迟将这个数据包发送，直到该链路从错误状态中 恢复过来为止，这是一个较为合理的处理方法，但是，这个受影响的数据传输就暂时损失了 分配给它的带宽。为了确保用户使用的公平性，在无线链路的状态恢复以后，需要对这个受 影响的数据传进行带宽损失的补偿，而怎样补偿这个损失的带宽却不是一个很容易实现的问 题。此外，在多长的时间内能够保证用户的公平性实现也是一个值得探讨的问题，在调度算 法中都应该考虑到。 (4) 功率限制 在无线网络中，基站的功率控制一般是不用考虑的，因为它有足够的电源使用。但是， 对于移动设备来说，由于电源等资源是有限的，因此它的功率也是受到限制的。所以在设计 的分组调度算法时，应该尽量用最少数量来控制更多的信息，以减少移动设备发送这些信息 所使用的功率开销。 (5) 吞吐量和利用率 对于无线网络来说，最重要的资源就是带宽。一个好的分组调度算法应该尽量减少用户 在错误的信道条件下进行传输，因为此时的传输是无效的，只会浪费信道资源，所以分组调 度算法应该做到尽量多的有效传输，以提高信道利用率。 南京邮电大学硕士研究生学位论文 第一章 绪论 6 除了以上几点之外， 所设计的分组调度算法还必需满足尽量简单的原则， 不能过于复杂， 这样才能在尽量短的时间内使分组调度算法得以实现，以满足用户严格的时延要求。 从目前的研究状况来看，根据业务类型的不同，可以将分组调度算法分为两类，即非实 时业务的分组调度算法和实时业务的分组调度算法。 非实时与实时的主要区别就是在对时延的要求上， 非实时业务对时延要求相对来说较低， 调度算法也更为简单，目前比较经典的调度算法有：rr 循环调度算法、fth 吞吐量公平算 法、max_snr 最大信噪比算法、max_rsnr 最大相对信噪比算法以及 pf 比例公平调度算 法。其中，前两种算法属于简单调度算法，优点是算法简单容易理解，但都存在着公平性与 有效性二者不能兼顾的缺点，因此性能上一般不能满足用户的要求，对于后三种调度算法， 它们的调度原则都是基于多用户分集的机会调度。 前面介绍过基于多用户分集的机会调度算法，可以知道：在机会调度的算法原则下，网 络中的用户量以及每个用户信道条件的时变特性都是有利因素，可以在一定程度上提高各用 户和整个系统的吞吐量；在算法的每次调度过程中，选择信道条件最好的用户进行调度，使 用信道的全部资源来传输此用户的信息，可以明显增加系统容量，提高信道资源的利用率。 由上述理论可以看出，基于多用户分集的研究可以提高整个通信系统的容量。相对于简 单调度算法来说，基于多用户分集的机会调度算法在有效性和公平性两方面选择了更折中的 调度策略， 但是对于用户的一些较为严格的要求还不能满足。 后来有研究人员提出了 sfos18 基于统计公平的时间调度算法，此算法是在最大相对信噪比算法的基础上加入一个加权系数 以及虚拟时间的概念。经研究发现，此算法可以使用户获得加权的服务时间保证，即根据用 户所占的权重来分配服务时间，但此算法同样存在着缺陷，它不能提供具有加权服务时间公 平性的保证，这些概念都将在后面的内容中做具体一一的介绍。前面提出的算法都没有考虑 到加权的服务时间公平性保证19，虽然有的算法考虑了服务时间根据权重来进行分配，但是 对于用户的数据传输速率也可以根据权重来调整这一点没有考虑，这使得整个系统的吞吐量 受到影响，论文第三章中提出的算法就是针对这一点来进行改进的。 实时业务对时延要求更高，它的算法与非实时业务有所不同，目前研究的分组调度算法 主要有：mpf 多载波比例公平算法、m-lwdf 修正的最大加权时延优先调度算法、exp/pf 指数比例公平调度算法等。这几种算法都是研究的比较多的算法，他们的研究方向都比较稳 定，得出的结论在很多地方都有很大用处。但是，在这些调度算法中，往往关系到判决条件 的系数或者参数都较难以调整，考虑影响判决条件的因素不够全面，因此系统的性能不能达 到最好。后来，有研究学者利用机会调度的概念，提出了一种实时业务调度算法，是后来研 南京邮电大学硕士研究生学位论文 第一章 绪论 7 究者在最大相对信噪比的基础上进行改动的，相较前面几种调度算法能够较好满足用户的要 求，但是也存在同样的问题，即不能更好地兼顾系统的有效性与公平性，因此论文第四章也 是在这个方面进行改进，期望使各用户和整个系统都能获得更好的性能。 1.4 本文的结构安排本文的结构安排 当前无线通信技术飞速发展，无线通信系统面临着巨大挑战，一方面使用的用户数量急 剧增加，另一方面各用户对各种业务的要求也不断提高。面临着如此多的挑战，为了能够满 足用户的这些需求，要求无线通信能够增加系统的容量，也能使不同用户的服务要求得到满 意的保证。前文提到，目前对有线网络的分组调度算法研究已经到了一定的水平，但无线网 络具有与有线网络明显区别的特殊性，从而使得有线网络的分组调度算法不能直接用于无线 网络，对无线网络分组调度算法的研究要在此基础上更加深入。对于设计的分组调度算法， 要充分利用无线网络信道的时变特性，提高系统性能，提高系统容量和资源利用率，同时尽 量减少时变特性带来的负面影响。论文所做的主要工作是将无线网络中非实时以及实时业务 的分组调度算法作为研究对象，针对算法中无法同时满足有效性与公平性的原则以及无法获 得较好的服务时间保证和服务时间公平性保证等缺陷，主要研究在时变信道环境下时分复用 (tdm)的无线网络分组调度机制。 本章主要阐述了论文的研究背景与意义以及当前的研究现状，分析文章所要研究的具体 问题，同时明确了论文研究的主要目的、研究思路和内容。在第二章中，文章主要介绍了无 线网络中非实时业务和实时业务的传统分组调度算法，其中包括比较经典的算法以及学者在 此基础上改进的算法，也为后面文中的改进算法提供了理论依据。第三章中，针对第二章介 绍的现有的分组调度算法中的缺陷与不足，提出了一种改进的非实时业务调度算法。第四章 中，针对第二章中传统实时业务算法的不足之处提出改进的算法。第五章为全文的总结和展 望，总结全文的基本内容并同时给出了以后可以继续研究的一些方向点。 南京邮电大学硕士研究生学位论文 第二章 分组调度算法概述 8 第二章第二章 分组调度算法概述分组调度算法概述 非实时应用20，一般是指允许数据经历相对大一点的延迟抖动的应用业务，基本要求是 能够得到一个可靠的、有序的端到端的数据服务，如 ftp、e-mail 等。 很多非实时业务的用户，他们对于时延的要求不是很高，只要在一定的时间内得到响应 即可，但是他们对吞吐量的要求却很高，希望在有限的时间内获得足够的数据传输量，以尽 快完成传输任务。例如，ftp 业务，用户不需要网络在最短的时间内获得响应，但是希望下 载数据的速度够快， 能够迅速的将下载任务完成。 另外， 有些用户虽然需求的是非实时业务， 但是有时候对访问时延也有一定的要求，那么这些业务在能够满足较小尺度的服务时间保证 的调度算法下，获得性能会更好。 2.1 非实时业务分组调度算法非实时业务分组调度算法 2.1.1 循环调度算法 循环调度算法，即 round robin 调度算法，简称 rr 调度算法，其思想是：按照预定次 序为每个用户提供服务，每次服务的时间固定为一个时隙，每个用户获得完全相同的服务时 间，此时吞吐量完全由信道条件决定。 根据调度算法的思想可以知道， 对于系统中任意一个用户 i , 其获得传输时的数据传输速 率只与自己的信道有关， 也就是说它实际得到的吞吐量完全由自己决定， 而与其他用户无关， 因此其吞吐量可以表示为21： 1 *(2.1)iitr n 式中，it表示任意用户 i 在整个时隙中的吞吐量， _ ir表示用户 i 所在信道的平均传输速 率，其吞吐量的计算是由平均传输速率与其获得的服务时间的乘积得到的。从吞吐量的表达 式中可以明显看出，在 rr 循环调度算法中，每个用户获得服务时间是完全相同的，也就是 说其获得服务的公平性是完全一样的。虽然说 rr 算法的公平性非常好，但因此也带来了对 吞吐量的影响。rr 算法是按顺序轮流来响应用户的服务的，由于信道的时变特性，在每个用 户获得服务的时间内，信道条件大部分可能是不太好的，因此用户获得的吞吐量一般会比较 小，这样整个系统的