ad hoc网络中的公平调度策略研究

《ad hoc网络中的公平调度策略研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文Adhoc网络中的公平调度策略研究姓名：曾国锴申请学位级别：硕士专业：计算机软件与理论指导教师：许胤龙20050501中国科学技术走学硕士学位论更Adhoc网络中的心平调度策略研究中文摘要Adhoe刚络是一一种不需要任何同定的基站支持、能够随时随地构建的自组网络。正是由于这种特性，使得adhoc刚络的应用越来越广泛，例如灾难等突发性事件中的恢复、人群控制、野外搜救等。近年来，adhoc网络的算法和协议不断涌现，其最终目标是为了嘲络拓扑结构变化，通讯能力受限的adhoc网络能够提供良好的服务质量。其中，最

2、大化网络资源的利用率和公平地分配通讯信道是两个非常重要的设计目标。最大化网络资源的利用率对于满足刚络中频繁的通讯请求非常重要，而公平性则保护了遵守网络规则的用户不会由于其它用户过分占用网络资源而处于不利的境地。本文的主要内容和贡献如下：(1)本文提出了数据流长期公平度的概念，并设计出相应的追求最大流量的公平调度算法。通过分析验证了该算法较前人算法有着更大的网络流量．分布式的实现也更加简易。(2)本文定义了加权的流冲突图，根据所关心的网络参数，设置节点的权值。在图上计算一个最大加权独立集是一个NP难的问题，本文提出了最大加权独立集的

3、贪心算法，并利用backo蹴『l制和IHs／CTs握手机制设计出贪心算法的分布式实现。(3)本文提出了最大能量优先算法(GEF)，将权值设置为节点的剩余能量，在保证每个数据流的基本公平度的基础上，最大化网络的生存时间和系统的总流量。(4)本文提出了最大包数优先算法(GPF)和最大势包数优先算法(GPPF)，将权值设置为节点缓冲区中剩余数据包的数目，在保证每个数据流的基本公平度的基础上，最小化通信请求的总延迟和总传输时问。(5)搭建了模拟实验环境，通过模拟实验验证丫本文算法的有效性。关键词：adhoe网络，公平调度，长期公平度，加权

4、流冲突图，最大加权独立集。中国科学技术大学硕士学位论丈Adhoe网络中的公平调度策略研究AbstractAdhocnetworkisakindofautonomousnetworkwhichcanbeorganizedanytimeandanywhere．AnditdoesnotneedanybasestationDuetoitscharacteristics，ithasmoreandmoreapplication，suchasrecoveryfromparoxysmalevents，publiccontrol，searchint

5、hefield，andsoon．Recently,manyalgorithmsandprotocolsforadhocnetworkshavebeendevelopedTheendgoalistoprovidewellQoSforcapacity-constrainedanddynamicadhocnetworksInthesedesigns，fairdistributionofbandwidthandmaximizationofresourceutilizationhavebeenidentifiedastwoimportant

6、designgoals．Maximizingresourceutilizationiscriticaltoeffectivelysupportcommunication—intensiveapplications，whilefairnessiscriticaltoensurethatwell—behavedusersarenotpenalizedbecauseoftheexcessiveresourcedemandsofaggressiveusersThemainworkandcontributionofthisthesisinc

7、ludesthefollowingaspects：(1)Thisthesisproposestheconceptionoflong—termfairness，anddevisestheMaximumFlowFairSchedulingAlgorithm(MFFS)．MFFSalgorithmhasgreatersystemthroughputandsimplerdistributedimplementation．(2)Thisthesisdefinesaweightedflowcontentiongraphinwhichamaxi

8、malweightedindependentsetisalwayscomputedforscheduling．ComputingamaximumweightedindependentsetinagraphisNP—hardSo，thethesisp