无线多跳网络基于位势博弈的传输调度方法

无线多跳网络基于位势博弈的传输调度方法樊帅;张林;王耀希;任勇【期刊名称】《计算机应用研究》【年(卷),期】2012(29)3【摘要】To further increase the throughput of wireless multi-hop networks, this paper proposed a scheduling method based on potential game with physical interference model. It considered that the link rate could change in terms of SINR dynamically. By designing the potential function properly, the existence and convergence of the Nash equilibrium could be guaranteed. Meanwhile, the global function could be optimized while each player tried to minimize its payoff. Simulation results show that the method has good performance.%为了进一步提高无线多跳网络的吞吐量,采用物理干扰模型,考虑链路速率可以随信干噪比( signal to interference plus noise ratio,SINR)动态可调,提出了基于位势博弈的传输调度算法.通过设计合适的位势函数,使得纳什均衡点的存在性和收敛性都得到保证.同时,每个参与者在最小化自己支付的同时,使全局函数达到最优.仿真结果表明,该算法具有较好的吞吐量性能,而且有较快的收敛速度.【总页数】5页(P1014-1018)【作者】樊帅;张林;王耀希;任勇【作者单位】清华大学电子工程系,北京100084;清华大学电子工程系,北京100084;云南大学,昆明650223;清华大学电子工程系,北京100084【正文语种】中文【中图分类】TN925;TP393【相关文献】1.基于无线多跳网络有限理性节点博弈分析 [J], 陈心瑜;舒兆港;赖晓燕;魏芬;阮凯斌2.基于贝叶斯博弈模型的无线多跳网络激励机制 [J], 许力;陈心瑜;陈志德3.无线多跳网络中基于博弈论的协作激励机制研究 [J], 谢鲲;孙家奇;伏梦盈4.无线多跳网络中SVC视频流传输的分布式优化方法 [J], 由磊;雷建军;王丕超5.一种基于休眠调度的无线多跳网络路由协议 [J], 焦磊;郑秋红因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于无线多跳网络的跨层优化算法曾捷【摘要】针对无线多跳网络目前存在的问题,提出了一种较完善的跨层优化调度算法,在兼顾优先级较高的实时性业务的同时,有效扩展节点覆盖范围,提升了系统整体容量.对系统的吞吐量和延迟性能指标进行了仿真比较分析.【期刊名称】《安徽师范大学学报（自然科学版）》【年(卷),期】2014(037)001【总页数】5页(P39-42,46)【关键词】无线多跳网络;吞吐量;延迟;仿真【作者】曾捷【作者单位】深圳大学信息工程学院,深圳 518060【正文语种】中文【中图分类】TN911.6无线多跳网络是指具有分布式特性和多跳特性的无线网络，主要应用包括：分布式WLAN、移动Ad-Hoc网、无线Mesh网、WSN(wireless sensor network，无线传感器网络)、无线中继网络、3G LTE的混合网络等.无线多跳网络通过定向通信技术能进一步增大覆盖范围，具有良好的开发应用前景.为了得到更大的网络吞吐量，高层协议需要充分利用低层协议的潜能，跨层优化设计对进一步优化无线多跳网络技术十分必要[1].近年来许多学者对多跳网络跨层优化设计进行了相关的研究.清华大学的Juan Liu等人考虑了实时可伸缩的通信业务，通过跨层优化和机会调度相结合，来提升系统性能[2].国防科技大学的王建新、魏急波等人提出了一种基于位置信息的波束调整机制[3]，可以灵活地加载于路由层与MAC层的算法之中，对采用定向天线传输的多种路由策略进行仿真评估.华中科技大学的李之棠等人提出了采用了智能天线的多跳MAC协议DMH-MAC[4]，使用波束跟踪天线，经过较少的跳数传递数据包，从而改善网络性能.西南交通大学的冯军焕提出基于邻居意识的定向天线控制方法(NEMA-DMAC)[5]，让Ad-Hoc网络中的每个节点了解当前信道的使用情况，相应地调整定向天线的波束角度，以此来提高空间信道的使用率.以上文献虽然对网络延时、抖动和吞吐量等性能有较好的改进，但无法解决如下突出的问题：第一、通过现有的扫描方法来估算小区内节点的角度信息有需要改善的空间.全向天线覆盖范围较窄；单波束的圆周扫描耗时较长；物理层DOA估算，复杂度和硬件成本都较高[6].第二、传统方法没有考虑用户的移动性或者突变性，从而导致小区划分不合理.例如，将小区划分固定宽度的扇区以获得更高的网络资源复用，往往由于不能灵活适应不稳定和不均匀的移动节点分布，结果小区内有的地方因负荷太大引起了中断，而有的地方流量比较小通信资源闲置[7].为了解决上述问题，本文提出一种多跳网络的跨层优化调度算法, 有效地弥补了目前系统的不足之处, 尤其是在系统吞吐量和延迟测试中取得较好的效果.采用OPNET结合MATLAB来构建仿真平台.MATLAB负责物理层算法实现，OPNET主要负责物理层以上协议层的通信协议构建，同时通过OPNET构建和MATLAB实时通信的软件接口[8].本文所提出的实验平台系统结构如图1所示.作为接收端时，天线阵列接收到信号后，通过A/D模块变换到基带，通过不同扇区的波束权值向量滤波后，将不同扇区的信号区分开，经过解码和判决输出得到最终的信号；作为发送端时，发送信号经过编码后，通过不同扇区的波束权值向量预处理后叠加，通过A/D变换到高频后，再通过天线阵列发送出去.需要指出的是，为了满足多个正交波束能对小区进行完整的覆盖，我们假设天线个数M是大于扇区个数N的，这在实际通信中是很容易满足的.系统所使用的跨层优化调度结构如图2所示.在物理层，通过正交多波束技术实现最优扇区化的基础上，在MAC层对每个扇区的输出进行监控，以网络整体系统容量为优化目标，建立每个扇区的目标函数，设计高效的优化调度算法，避免盲区和隐藏节点的产生，来充分利用多波束技术带来的高空间信道复用率潜力，达到大幅度提升系统吞吐量的目的[9].优化调度算法流程图如图3所示.(1)初始化系统，确定最大扇区个数N.能并行处理的最大扇区数N根据热点节点的硬件条件来确定；(2)将整个小区平均分为N个扇区，并对每个扇区并行发送RTS信号.这个只是一个初步的扇区粗划分，在实际通信中，节点的分布往往都是非均匀的，所以这种初步划分是不合理的[10-11]，需要后面进一步处理；(3)节点收到RTS后，会反馈一个CTS，这里根据反馈回来的CTS，确定每个扇区内的节点数；(4)判断某个扇区是否存在需要通信的节点. 如果存在了，再通过固定正交波束的方法进行精细扫描，而扫描的精度由扇区内通信节点的数目来确定，节点数越多，扫描间隔越精细，反之亦然. 如果没有存在需要通信的节点，则跳过精细扫描过程；通过第(2)～(4)步骤，就可以估算出每个通信节点的角度信息，值得一提的是，这样的角度信息估算肯定不会是非常准确，但是经过研究发现角度信息较小的误差在自适应扇区化应用中所带来的影响是可以忽略的. 第(2)～(4)步骤估算通信节点角度信息的优势是明显的：相对于全向天线，新方法形成的波束覆盖范围更广；相对于单波束的圆周扫描方法，本方法的并行扫描中每个精细扫描只在自身扇区进行，可以节省时间至少超过N倍；另外相对于单独使用物理层DOA估算方法，复杂度和硬件成本都大大降低.(5)将节点的角度信息传给物理层，通过最优扇区化波束合成算法或者快速收敛波束合成算法计算每个扇区的权值向量. 相对于第(2)步的扇区粗划分，当前的划分才是最优划分；(6)得到每个扇区的权值向量后，可以开始正常的多波束通信；(7)判断是否有某个扇区完成了通信，如果有的话，就快速估算系统整体的平均掉话率P.如果还没有完成通信，就继续回到第(6)步，进行多波束通信；(8)计算出了掉话率P后，使其与某一个阈值δdp进行比较. 如果出现了P>δdp，则表示当前的扇区划分不合理，有必要再次进行自适应扇区划分，来降低掉话率提升性能. 如果不满足P>δdp这个条件，继续回到第(6)步，进行多波束通信；(9)在满足了P>δdp这个条件基础上，是否再次开始新的扇区划分，还要兼顾优先级高的实时性通信，需要再进一步判断其他扇区是否存在实时性高的通信，如果存在了，还是继续回到第(6)步进行多波束通信. 如果不存在实时性高的通信，则推迟其他扇区的后续通信(即等其他扇区当前通信帧完成后，通知后续帧进行等待，重新自适应扇区化完成后再进行通信)，并返回到第(2)步重新进行自适应扇区化. 通过仿真比较发现，如BEB算法和HBAB算法[12]，存在抗干扰差、不公平、不能实时更新和盲区等问题，新算法具有更好的吞吐量和更小的延迟，具有较高的收敛速度和较低的复杂度，从而提高了系统的可靠性，如图4所示.构建一个多点跳转网络的实验，场景如图5所示，希望从node_1发送业务流到node_0.分别比较当节点使用全向天线和本文算法对网络性能的影响.使用智能天线时，从node_1到node_0只需一跳，使用全向天线时，需要6跳，如图5(a)和图5(b)所示所示.通过网络延迟可以清楚的体现两种情况性能差别，如图6所示. 本文提出了一种基于无线多跳网络的灵活、快速和实时的优化调度算法对系统性能进行监控.传统的调度算法往往采用两种思路，一种是定时的，比如每个一小时进行一次重新扇区化，显得非常机械，不够灵活，不能根据真实的通信进行调整；另外一种是要等所有扇区都通信完了，才进行监控是否需要重新扇区化，导致等待时间过长，性能的提升受到限制.此外，传统算法没有对真实通信中优先级较高的一些实时性通信业务进行考虑. 该算法对降低系统复杂度和改善系统性能具有实际指导意义.【相关文献】[1] YAZDANPANAH M, ASSI C, SHAYAN Y. Optimal joint routing and scheduling in wireless mesh networks with smart antennas[C], 2010 IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, 2010：1-7.[2] 王杉,张旭东,魏急波,王建薪.定向天线在Ad Hoc网络中的设计与应用[J].计算机工程与应用,2006，42(21)：2.[3] 范军.采用智能天线和功率控制的Ad Hoc网络MAC协议的研究[D].武汉：华中科技大学,2008.[4] 黄胜豹.Ad Hoc网络中基于邻居意识的定向天线控制方法[D].成都：西南交通大学2009.[5] JUAN L, WEI C， Z Ying Jun, C. Zhigang. Distributed beamforming based directional spectrum sharing. 2011 Conference Record of the Forty Fifth Asilomar Conference on Signals, Systems and Computers[C], 2011：1330-1334.[6] OLEN C A， JR R T C. A numerical pattern synthesis algorithm for arrays[C]. IEEE Transactions on Antennas and Propagation,1990，(38)：1666-1676.[7] WANG A, KRISHNAMURTHY V. Mobility enhanced smart antenna adaptive sectoringfor uplink capacity maximization in CDMA cellular network[C]. IEEE Transactions on Communications, 2008，(56)：743-753.[8] 王正林，王胜开，陈国顺，等. MATLAB/Simulink与控制系统仿真[M].北京：电子工业出版社，2008：51.[9] 刘永强，严伟，赵通，等.面向路径的无线多跳网络端-端吞吐量分析[J].电子学报,2007,35(5)：971-975.[10] 王文博,张金文.OPNET Modeler与网络仿真[M].北京：人民邮电出版社,2003：28-49.[11] 方明星，吴敏，佘锦华.等价输入干扰结构主动控制系统的分析与设计[J].安徽师范大学学报：自然科学版，2009，32(6)：534-537.[12] XU S, SAADAWI T. Does the IEEE802. 11 MAC protocolwork well in multihop wireless Ad Hoc networks[J]. IEEE Communication, 2001, 39(6):130-137.。

基于潜在博弈的多源多跳无线传感器网络流量分配算法张伟;张玲华【摘要】无线传感器网络中存在大量数据,数据融合及网络优化可以有效降低网络能耗,提升网络吞吐量.由于无线传感器网络自身的广播特性,在无线网络中应用网络编码可以带来吞吐量提升等性能增益.考虑将N个源节点的K个数据发送到D个不同目的节点的情况,源节点在自身可用路径上分配流量,利用博弈论研究无线传感器网络流量分配问题,提出了一种动态控制方案,源节点根据效用函数调整路径流量分配,以增加网络编码机会,从而降低网络能耗.理论分析和仿真结果表明,该方案是稳定、有效的.【期刊名称】《电信科学》【年(卷),期】2015(031)002【总页数】5页(P75-79)【关键词】无线传感器网络;网络编码;潜在博弈;数据共享【作者】张伟;张玲华【作者单位】南京邮电大学通信与信息工程学院南京210003;南京邮电大学通信与信息工程学院南京210003;江苏省通信与网络技术工程研究中心南京210003【正文语种】中文1 引言无线传感器能够利用自组织能力形成网络，协作地感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并将这些信息发送给网络所有者。

因而可以说，传感器网络的出现弥补了人类无法涉足的区域信息获取困难的遗憾，具有广阔的应用前景。

它将现代社会三大信息技术（即传感器技术、计算机技术和通信技术）有效地应用于一体。

无线传感器网络中，节点数目往往很大，节点只能获取局部拓扑结构信息，路由解决方案要能在局部网络信息的基础上选择合适的路径，同时，传感器网络节点能量有限且一般没有能量补充，因此路由解决方案是否能高效地利用能量就成为衡量传感器网络系统的重要性能指标。

传统路由策略往往需要知道整个网络的全局信息，难以应用。

其根本问题在于以往的无线传感器网络解决方案中，传感器节点传送数据的方式是存储转发，即除了数据发送节点和接收节点以外的中间节点只负责路由，而不对数据内容做任何处理，中间节点扮演转发器的角色。

基于W学习的无线网络传输调度方案朱江;彭祯珍;张玉平【摘要】针对无线网络的传输问题,提出了一种适用于无线网络的智能传输调度方案,在马尔可夫决策过程(MDP)的基础上构建了系统模型,通过W学习算法的引入,中继节点对缓存器储存状态及信道质量进行学习,从而在信息数据包的传输过程中智能地选择数据包传输对象及数据包传输方式来达到在节省能量损耗的前提下尽量减少数据包丢失的目的.通过状态聚合方法解决因状态空间过大而导致的维灾问题,同时采用了行动集缩减来以减少某些状态对应的行动数,利用这些简化方法可以发现逐次逼近法的存储空间压缩率为41％,W学习算法的存储空间压缩率为43％.最后,系统仿真结果表明,提出的传输调度方案可以在节省能耗的基础上尽量地传输数据,减少了数据包的丢失,同时采取的状态聚合法及行动集缩减在有效地简化计算的同时并没有影响算法的性能.【期刊名称】《计算机应用》【年(卷),期】2013(033)011【总页数】6页(P3005-3009,3015)【关键词】传输调度方案;马尔可夫决策过程;W学习算法;中继节点;近似最优策略【作者】朱江;彭祯珍;张玉平【作者单位】重庆邮电大学移动通信技术重庆市重点实验室,重庆400065;重庆邮电大学移动通信技术重庆市重点实验室,重庆400065;重庆邮电大学移动通信技术重庆市重点实验室,重庆400065【正文语种】中文【中图分类】TN9250 引言随着无线通信技术的不断发展，频谱资源日趋紧张，与此同时，通信网络的规模也在不断扩张中。

由于智能传输不仅可以提高频谱分配效率，还可以解决大规模传输网络的传输调度问题，所以适用于无线网络的智能传输调度成为研究热点之一。

文献［1］在具有节能意识的传感器通信中构建了一种近似最优的加强学习框架，通过使用加强学习来减少传输对系统转移概率的依赖;文献［2］则基于马尔可夫决策过程(Markov Decision Process，MDP)在学习算法的基础上构建了一种无线电网络的传输调度方案，使得在满足缓存器丢包率约束的前提下，最小化平均功率消耗;文献［3］则基于自适应行为，利用指数退避针对载波侦听多路访问(Carrier Sense Multiple Access，CSMA)网络中节点的竞争与合作建立了一种新的方法;此外也有很多文献对无线网络的智能传输调度进行了相关研究［4－9］。

无线多跳中继网络资源调度的开题报告
一、选题背景和意义
随着信息技术的快速发展和物联网技术的逐渐成熟，无线多跳中继网络已经成为一种重要的网络结构。

无线多跳中继网络通信链路的重复利用能够极大地提高网络吞
吐量和覆盖范围，使得其在军事、应急救援、智能交通等领域有着广泛应用。

然而，
多跳中继网络资源分配和调度一直是该网络面临的一个重要研究问题。

本文针对无线
多跳中继网络资源调度问题进行研究，对提高其性能和可靠性具有积极的作用和意义。

二、研究内容和方案
1.研究现有的无线多跳中继网络资源调度算法及其优缺点，深入分析其局限性，为进一步改进提供基础和依据；
2.结合无线多跳中继网络的特性，提出一种适用于该网络的资源调度算法，该算法应重点考虑节点间的通信质量、网络拓扑结构和数据传输的实时性等因素；
3.在求解算法中使用优化方法，设计一个合适的目标函数并制定相应的约束条件，以提高算法的效率和有效性。

同时在算法的实现过程中应考虑资源利用的平衡性和公
平性等问题；
4.基于模拟实验和仿真实验，对提出的资源调度算法进行性能测试，验证其有效性和可行性。

三、预期研究成果
通过本次研究，我们预计能够提出一种创新的、适用于无线多跳中继网络的资源调度算法，并在实验中得到验证。

该算法应具有高效性、公平性和自适应性，能够有
效地提高网络性能和可靠性。

同时，我们的研究也将为其他关于多跳中继网络的资源
分配与调度的研究提供参考和借鉴。

收稿日期:2007-04-26　作者简介:秦晓卫,男,1979年生,讲师,博士研究生,研究方向为无线通信及无线网中资源分配;徐佩霞,女,1941年生,教授,博士生导师,研究方向为无线通信与信号处理.无线多跳网的一种端到端的最大最小公平调度算法秦晓卫,徐佩霞(中国科学技术大学电子工程与信息科学系,安徽合肥,230027)E-mail:qinxw @us tc.ed 摘　要:提出一种基于效用函数的分布式最大最小公平性调度算法及其跨层控制模型,算法针对无线多跳网中端到端的流,通过对偶规划以及拉格朗日松弛算法把问题分解成传输层和M A C 层两个子问题,在传输层上采用基于最大价格的最大最小公平速率分配方案来交叉控制M AC 层的调度,给出了跨层层控制模型.仿真结果表明该算法具有良好的公平性和调度性能.关键词:最大最小公平性;调度;M ax Net ;对偶规划;拉格朗日松弛中图分类号:T N 915.65 文献标识码:A 文章编号:1000-1220(2008)09-1664-05Scheduling Algorithm for End -to -end Max -min Fairness in Wireless Multi -hop NetworksQ IN Xiao -w ei,XU P ei-x ia(De p ar tment of E lectronic Eng ineer ing and I nf ormation Sc ience ,Univ er sity of S cience and T echnology of China ,H e f ei 230027,China )Abstract :A utility functio n based distr ibuted scheduling algo rithm and cr o ss-lay er contr ol model for max -min fair ness w as pro -po sed .T he algo rithm w as desig ned for end -t o -end f lo w in wireless multi -hop netw or ks .With dual pro gr amming and L agr ange relax ation,ma x -min fair r ate allo cat ion schedule was decompo sed into tw o subpro blems o f t ranspo rt layer a nd M AC lay er .T hescheduling policy of M A C layer w as built on m ax -pr ice based max -min fair ra te allocatio n scheme o f tr anspo rt layer .T he cr oss -layer co ntr o l model w as pro vided.Simulat ion result show s that pro po sed alg or it hm has g oo d fair ness and pr etty scheduling per -for mance .Key words :max -min fairness;scheduling ;M ax Net ;dual pro gr amming ;lagr ange r elaxat ion1　引　言随着无线多跳网逐渐由实验阶段发展到商业应用,为网络用户合理有效的分配带宽成为一个重要的研究方向,该问题的主要障碍来自于共享无线媒质传输的空间竞争.空间竞争可从物理层和M A C 层来考虑,针对物理层而言,单信道下空间竞争激烈,多信道则相对缓和.但多信道下也存在着空间竞争,一般终端节点只装备一个收发器,因此它不能同时发送或者接收;针对M A C 层,现有随机分布式M A C 协议虽然具有分布特点和一定机动性,但这种随机接入的M A C 协议无法提供带宽分配的保证[1],建立一个无冲突的公平调度是M A C 协议的目标之一,所谓无冲突公平调度就是在保证流公平性基础上,任意时刻处于工作状态的无线链路之间互不干扰.寻找一个完美的无冲突公平调度是一个困难的问题,已有的很多文献研究了最大最小公平调度算法[2-5].文献[5]给出了有线数据网中一种最大最小公平调度策略,但有线网与无线多跳网在资源分配的限制条件方面存在着显著的不同.文献[4]首次以无线网时隙多信道下最大最小公平性为目标,给出了对应的调度策略,但算法部分是集中式的,需要全局信息,这在实际中很难实现,另外它主要针对单跳流.文献[3,4,6]是一类基于最大化效用函数的资源分配算法,[3,4]给出了对应的公平调度算法,这一类方法适用于按比例公平性,对于最大最小公平调度,由于效用函数参数取值的问题,算法收敛非常缓慢.本文主要考虑无线网络中端到端多跳流的最大最小公平性,采用对偶理论将问题分解成源端传输层子问题和M AC 层子问题,在源端传输层上采用M a xN et 控制模式实现最大最小公平性速率分配,并通过链路和集群价格因子与M AC 层的调度问题进行交叉控制,最后给出其跨层控制模型.2　最大最小公平性以及系统描述本文中,假设无线节点只有一个无线收发器因而不能同时接收和发送,无线节点之间干扰是互相的,基于以上的假设,一个无线多跳网的网络拓扑图可用一个无向图来描述,无向图中,顶点代表无线节点,边代表两节点之间距离小于无线传输距离,一般把这种无向图称为节点图.在无线多跳网中,如果一条链路的源点或者端点在另外一条链路的源点或者端点的干扰范围之内,那么这两条链路相互冲突,基于这些冲突信息,可以把节点图转化成冲突图.在冲突图中,每个顶点代表一条链路,边代表两条链路之间存在着冲突,如图1所示,小型微型计算机系统Jo urnal of Chinese Co mput er Sy st ems 2008年9月第9期V ol.29N o.92008(a )是一个无线多跳网的节点图,(b )是由(a )派生出的流冲突图G ,这里我们引进冲突图中集群和独立集的概念.图1　无线多跳网拓扑图以及流冲突图F ig.1　Wireless multi-ho p net wo rk to po log yand flow conflict gr aph定义1.(集群):集群为冲突图G 的完全子图,极大集群为冲突图G 极大完全子图.定义2.(独立集):独立集为冲突图G 顶点集的子集,其中任意两点不相邻.由以上定义可知,极大集群内同一个时刻只能有一条链路处于工作状态,即集群内的链路分享集群的“容量”,一条链路可同时属于几个极大集群,同一独立集内的链路可同时工作.设L 维矢量y T ={y 1,…,y l ,…,y L },其中y l 代表链路l 上的流速率,设c 0l 为链路l 的最大容量,则链路l 上的归一化速率为y l /c 0l,根据集群定义可以得出某一集群cl i 内可行性速率限制为: ∑ly l /c 0l ≤1 l ∈cl i(1)上述可行性限制可以通过引入竞争矩阵F 来描述,N ×L 竞争矩阵F 定义如下: F nl =1/c 0l l ∈cl n0 other s式(1): Fy ≤1(2)式中1表示一个N 维矢量,注意上式仅在网络节点图为完美图[7]时才是可行性的一个充要条件,否则极大集群的归一化容量要减小到2/3时方可成为一个充要条件[8],一般拓扑结构的可行性限制写为: Fy ≤E(3)式中E 表示一个N 维矢量,有E T={2/3,…2/3,…2/3}.设网络中端到端流用集合S 表示,端到端流速率用S 维矢量x 表示,每个流S 经过的链路集为L s <L ,L ×S 路径矩阵R 定义如下: R ls =1 l ∈L s 0 others端到端流速率矢量x 与单跳流矢量y 的关系为:y =R ・x ,因此式(3)可写为: FRx ≤E (4)Ber tsekas 在[9]中给出了有线网中最大最小公平性定义,根据以上对可行性条件的分析,我们类似的给出无线多跳网中最大最小公平性定义如下:定义3.(最大最小公平性):无线多跳网中,可行的流速率向量x 满足如下条件即为最大最小公平分配:(1)满足可行性;(2)每个端到端的流x s 至少存在一极大集群满足各个流的速率之和为集群最大容量且x s 为该极大集群中的最大流.以上的最大最小公平性可采用最大化效用函数为目标函数,进行非线性规划[3]:设每一个端到端流x s 均可从该速率获得一个效用函数U s (x s ),U s (・)为连续可微递增的严格凹函数,x s ≥0.规划的目标是要寻找一个流矢量x 达到:max x s≥0∑sU s (x s )s .t .　FRx ≤E(5)上式中效用函数直接关系着系统能达到怎样的公平性,常见的效用函数如下[10]:U s (x s )=f A (x s )=log x s A =1(1-A )-1x 1-As A≠1(6)文献[10]A 决定,当A =0时,系统追求最大吞吐量;当A =1时,系统追求按比例的公平性目标;当A →∞时,系统追求最大最小公平性目标.3　基于最大价格的分布式调度算法本节我们首先介绍式(5)的对偶规划并把它分解成两个子问题,其次结合M ax N et 控制模式给出一种分布式最大最小公平调度算法及其交叉层控制模型.3.1　规划的分解调度问题是M A C 层根据某种机制来决定链路何时处于工作状态的一个问题,本文主要研究无线多跳网端到端流的最大最小公平性的调度.研究公平调度之前我们先分析一下式(5)所示的线性规划,这里引入一个辅助L 维矢量c ,矢量中的元素c l 代表链路l 的有效容量或平均容量,式(5)可进一步表示为: ma x x s ≥0,c l ≥0∑s U s (x s )s .t . Rx ≤c &Fc ≤E(7)上式中第一个约束条件代表各条链路上各个流速率之和不超过链路有效容量,第二个约束条件代表各个极大集群内的各链路有效容量之和不超过集群容量.对式(7)进行拉格朗日松弛以及对偶规划[11]得: min p ≥0d (p )d (p )=maxx s≥0,c l ≥0∑s U s (x s )-p T (Rx -c )s .t . Fc ≤E(8)式中L 维矢量p T ={p 1,…p i ,…p L }为拉格朗日算子矩阵,矩阵中各元素实际意义为对应链路价格因子[6],式(8)可进一步分解成两个子问题: d 1(p )=max x s ≥0∑sU s (x s )-p T Rx(9) d 2(p )=max c l ≥0p T c s .t .　Fc ≤E(10)16659期 秦晓卫等:无线多跳网的一种端到端的最大最小公平调度算法3.2　基于最大价格的最大最小公平调度算法在将问题分解成两个子问题后,我们对其逐一分析求解.首先观察d 1(p ),由式(9)可知d 1(p )是一个无约束条件的非线性规划问题,这是一个传输层端到端的流量控制问题[6],对其微分求极大值可得各端到端的流的速率: x s =U ø-1s(∑lp l R ls )=D s (∑lp l R ls )(11)式中U ø-1s (・)为U s (・)微分函数的反函数,D s (・)称为需求函数,是一递减函数.其次考虑对d 2(p )的求解,一般分析中,矢量c 可取两种模式,一种是连续流模式,另一种为离散流模式.连续流模式下,矢量c 代表各个链路的有效容量;而实际工作中是一种离散流模式,即每条链路只能存在两种状态:工作状态或空闲状态,即链路容量为最大容量c 0l 或0.约束条件Fc ≤E 对连续流模式为一充分条件,针对离散流模式,根据极大集群定义的某一时刻集群内最多只能有一条链路处于工作状态,约束条件可松弛为Fc ≤1,因此对于离散流模式,d 2(p )可描述为: max c ≥0　p T c s .t .　Fc ≤1,c l =0或c l =c 0l ,l ∈L(12)上式描述的问题是一个整数线性规划问题,即在满足集群内无冲突约束条件下求解链路瞬时速率矢量c 使得目标函数最大化,矢量c 中的元素为0或者1,代表对应链路处于空闲或工作状态,这是一个M A C 层无冲突链路调度的问题.首先对目标函数引入一个罚函数D c T c 可得: max c ≥0(p T c -D c T c )(13)式中D 是一个很小的正数,当D →0时,目标函数求解所得结果逼近原始目标函数的最佳值,对上式进行拉格朗日松弛和对偶规划可得: min K ≥0　L (K )L (K )=max c ≥0p T c -D c T c -K T(Fc -1)(14)式中N 维矢量K T ={K 1…K n ,…K N }拉格朗日算子矩阵,矩阵中各元素实际意义为集群价格因子,用梯度法[11]可得c l 和K n 的迭代过程为:c l (t )=(p l -∑nK n (t )F nl )/2D+K n (t +1)=K n (t )+B (∑nF nl c l (t )-1)+(15)式中B 为步长因子,算法收敛所要求的步长因子B 的范围为[6]: 0<B <4D /ON式中O 代表冲突图内集群所包含的链路最大个数,N 代表包含同一链路的最大集群数目.我们把网络运行时间分为若干个连续的时隙T s lot ,在一个时隙中根据式(15)逐步迭代,选取合适的时隙大小可使得式(15)在一个时隙内迭代达到收敛,根据收敛后的各链路容量c l 与设定门限值为c 0l /2比较来判定c l 取0或者c 0l ,即以此来确定下一时隙各个链路的工作状态,故以上算法可作为对应的M A C 层调度策略.由式(15)可知当算法收敛时,该时刻有p l →∑nK n (t )F nl ,故式(11)可写为: x s (t )=D s (∑l∑nK n (t )F nl R ls )(16)上式表明源端控制流速率取决于反馈回各链路所属集群的价格之和,这是一种SumN et 的控制模式[12],该模式对于最大最小公平速率分配存在着收敛速度过慢的缺点.由式(6)可知,当A →∞时代表系统追求最大最小公平流速率分配,对应的需求函数D s (p )=U ø-1s =p -1/A,需求函数的梯度为d dpD (p )=-1Ap 1-A A ,当A →∞时,梯度对于任意的p 均趋向于0,即意味着算法以缓慢的速度收敛至最大最小公平.为克服SumN et 控制模式对于最大最小公平性收敛过慢的缺点,本文采用M ax Net 控制模式[12,13].文献[12]中指出M ax Net 控制模式下,若源端采用端到端路径上所有链路的最大价格做为反馈信息,则任意单调递减的需求函数均可实现最大最小公平性速率分配.对于有线网络反馈信息指所经链路的最大价格,本文中对于无线网络则为所经集群的最大价格,如图2所示,式(16)对应的流价格q s 为: q s =max l ,nK n (t )F nl R ls(17)对应的源端速率为: x s (t )=D ~s (max l ,nK n (t )F nl R ls )(18)式中D ~s(・)为一任意递减函数.图2　M ax N et 控制模式Fig.2　M ax N et contr ol mo de式(9)、(10)中d 1(p )可微,但d 2(p )是一个分段线性函数,不可微,因此d (p )并非在任意的p 处均可微,对此须采用子梯度算法[2]来迭代求解链路价格p l :p l (t +1)=[p l (t )+C t (∑sR ls (t )x s (t )-c l (t ))]+(19)式中C t 为正的标量步长因子,当链路上流速率之和小于链路容量,即供过于求时价格p l 增大,反之减小.基于以上分析可知,最大最小公平性调度算法可描述如下:初始化:k =0,x s (0)=01.计算下一时隙各链路价格p l ((k +1)T slot )=p l (kT s lot )+C t∑sR ls ・x s (K T s lot )-c l (K T slo t )+2.令k =k +1,在第k 时隙kT s lot 内迭代计算下式至收敛c l (t )=p l (k T slot )-∑nK n (t )F nl /2D+K n (t +1)=K n (t )+B∑nF nl c l (t )-1+3.K n (kT s lot )令为收敛后K n (t )的值if c l (t )≥c 0l /2then c l (kT s lot )=11666 小　型　微　型　计　算　机　系　统 2008年else c l (k T slot )=04.计算下一时隙各端到端流速率x s (kT s lot )=D ~s max l ,nK n (kT slo t )F nl R ls5.Go to 1算法中步骤4是各源端传输层进行速率分配,步骤3是实现途经各节点M AC 层的调度问题,整个算法的公平性调度策略可用图3所示的跨层控制模型来描述,各源端传输层图3　跨层控制模型F ig.3　Cro ss-lay er co nt ro l mo del通过该端到端流途经各链路的调度信息c l 以及集群价格K n 来计算各端到端流的公平速率x s 以及各链路价格p l ,并将p l 反馈给相关各节点的M A C 层来决定下一时隙各链路的调度.源端传输层和流所经各节点M AC 层之间通过链路价格p l 和集群价格K n 相关联实现最大最小公平性调度.4　仿　真本文以图4所示的无线多跳网拓扑图为例在M atla b 中对算法进行仿真,设各相邻节点之间距离相等,节点传输距离略大于相邻节点距离,载波侦测范围为两倍传输距离.仿真中图4　网络拓扑图F ig .4　Net wo rk to polog y取D ~s (x )=1/x ,网络中包含8个节点,三条端对端的流,设每条链路归一化最大容量均为1,采用集中式的“注入法”算法[1]求出各个流在最大最小公平性下的归一化理论速率为(0.25,0.5,0.25),各链路理论有效容量如表1所示.表1　最大最小公平性下理论有效容量T able 1　Effect ive capacities in theor y fo r max -min fair ness链路123456链路容量0.50.250.250.250.50.25根据式(6),当效用函数取U s (x s )=(1-A )-1x 1-As且A →∞时,算法在SumNet 控制模式下最终收敛为最大最小公平速率.令C =0.1,取A =3和5分别进行仿真,结果如图5所示.当A=3时,算法在迭代10000次后已经收敛,收敛后各流的速率为(0.2256,0.5492,0.3421);当A =5时,算法以极其缓慢的速度收敛,迭代50000次后逐渐收敛,收敛后各流速率为(0.2565,0.5358,0.3228).可见,随着A 逐渐增大,算法的收敛速度越来越慢,收敛后的值也越来越逼近最大最小公平性下的理论速率.图5　SumNet 控制模式下的不同参数A 的收敛状况F ig .5　T he co nver gence of differ ent par ameterA under SumNet co ntro l mode步长因子C 作为调整链路价格变化快慢的因子影响算法的收敛速度,首先我们取C =0.1对算法进行仿真,结果如图6所示.图6　C =0.1下的流速率F ig.6　F low rat es w it h stepsize C =0.1图6显示当算法迭代到一定次数开始收敛,对比图5可见算法收敛速度远快于SumN et 控制模式.注意这里的收敛并非是单调收敛,而是围绕着一个中心值振荡,各条曲线的中心值接近理论最大最小公平性流速率.图7(见下页)中左图是算法收敛后链路2在某段时间内的调度状况,仿真取了20个时隙,链路容量为1代表链路处于工作状态,0代表处于空闲状态,图7显示链路容量为1占了5个时隙,为0的占了15个时隙,即链路的有效容量在算法收敛后为0.25;右图是算法收敛后各链路有效容量的直方图,对比表1可见两者基本接近.仿真结果表明算法收敛后各端到端流速率基本满足最大最小公平性,各链路调度性能良好.下面取C =0.2对算法进行仿真,如图8(见下页)所示,对比图6可以看出,当C 取值增大,算法收敛速度加快,但同时收16679期 秦晓卫等:无线多跳网的一种端到端的最大最小公平调度算法 敛后的振荡增强.因此在实际中要综合考虑收敛速度和振荡强弱这两个方面,折中考虑C 的取值.5　结　论本文给出了一种基于效用函数的最大最小公平调度算法及其交叉层控制模型,算法通过对无线多跳网中的公平性调图7　链路2某20个时隙内的调度及各链路有效容量F ig.7　T he schedule o f link 2in 20slo ts andeffectiv e capacities of all links度问题进行非线性规划,采用拉格朗日松弛法和对偶规划的理论把问题分解成端传输层和M A C 层两个子问题,整个调图8　C =0.2下的流速率F ig .8　Flow r ates with stepsize C =0.2度策略基于链路价格和集群价格使得端传输层和M A C 层相互关联、相互控制.传输层通过M ax N et 模式实现最大最小公平速率分配,加速算法收敛.仿真表明算法能达到良好的公平性和调度性能.考虑到实际的无线多跳网中信息传播延迟等因素,一种更加快速和有效的算法是我们进一步研究的目标.References :[1]Xu S ,S afadaw i T .Does the IEEE 802.11M AC protocol w orkw ell in mu ltihop w ireles s ad hoc netw orks [J].IEEE C om muni-cations M agaz ine,2001,39(6):130-137[2]Ch en L,Low S H,Doyle J C.Joint conges tion control an d mediaaccess control des ign for w ireless ad hoc netw ork s[C].Proc.of IEEE Infocom ,M iami ,2005,3:2212-2222[3]Chen L,Low S H ,Chiang M ,et al.Cross -layer conges tion con-trol ,routing and sched uling des ign in ad hoc w ireless netw or ks [C].Proc.of IEEE Infocom,Barcelon a,2006.[4]Tass iulas L ,Sarkar S.M axm in fair scheduling in w ireles s adhoc netw orks [J].IEEE J.on Selected Ar ea in Comm unications,2005,23(1):163-173.[5]Hahn e E .Round -robin sch eduling for max -min fairness in datanetw orks [J ].IEEE J.on Selected Area in Comm unications,1991,9(7):1024-1039[6]Low S H,L aps ley D E.Optimization flow control I:bas ic algo-rithm and con vergence [J ].IEEE /ACM T rans action s on Net-w orking (T ON ),1999,7(6):861-874.[7]Diestel R,Graph T heory,S pringer-verlag,1997.[8]Hajek B ,S as aki G .L ink scheduling in polynomial time [J ].IEE E Trans action s on In formation T heory,1998,34(5):910-917.[9]Bertsekas D,Gallager R.Data netw ok rs.2n d edition [].Pr en-tice Hall,1992.[10]M o J ,Walrand J .Fair end -to -end win dow -b as ed conges tion con-trol[J].IE EE/ACM T ransactions on Netw orking,2000,8(5):556-567.[11]Bertsekas D,Nonlinear Programmin g [].2nd edition,Athen as cientific,1999[12]W ydrow ski B,Zuk erman M .M ax Net:a new network conges-tion control architectu re for m ax-m in fairn ess [C].IEEE ICC,Alas ka ,2003,1,132-136.[13]Wydrow sk i B,Zukerman M.M ax Net:a con ges tion control ar-chitecture for maxmin fairness [J ].IEEE Com munications Let-ters,2002,6(11):512-514.1668 小　型　微　型　计　算　机　系　统 2008年。

专利名称：基于中继站的多跳无线网络的资源调度方法专利类型：发明专利
发明人：郭欣,马文超
申请号：CN200710118087.2
申请日：20070628
公开号：CN101335971A
公开日：
20081231
专利内容由知识产权出版社提供
摘要：本发明公开了一种基于中继站的多跳无线网络的资源调度方法，包括步骤：获取基站、各中继站当前覆盖下的所有直接与它们进行信号传输的移动用户的连接的最小资源需求，对其求和得到基站、各中继站的最小资源需求；获取各中继站之间的干扰状况，根据基站、各中继站的最小资源需求和各中继站之间的干扰状况，采用不同的划分策略对各中继站进行划分，将各中继站分入可以占用共同资源的不同的独立集中，判断、比较各划分策略下的总的资源需求，以获得优化的资源复用调度划分策略。

采用该资源调度方法，能够更好的满足各连接的QoS需求，并且能够适用于动态非对称的多跳网络。

申请人：联想(北京)有限公司
地址：100085 北京市海淀区上地西路6号
国籍：CN
代理机构：北京汇泽知识产权代理有限公司
代理人：张颖玲
更多信息请下载全文后查看。

基于信道有限状态信息实现延迟受限的无线多跳网的传输调度研究宋勇;席伟;戢纳【摘要】为了进一步提高无线多跳网络的可靠性,在相关衰落信道下,提出了延迟受限的无线多跳网中相互关联的衰落链路数据传输调度.首先通过闭环的端到端可靠性,引出可以用增量算法解决的最优调度.其次由数值分析证实关联衰落链路的有限信道状态,以提升端到端的传输可靠性,同时给出相关系数的影响,如多谱勒频移、时隙长度和信道状态数等.最终得出结论,即当传输延迟要求不严时,所提方案提升性能更加明显.%In order to further improve the reliability of wireless multi-hop networks,in correlated fading channels,the packet transmission scheduling in multi-hop wireless networks with transmission delay constraint over correlated fading links is proposed.Firstly,the closed-form end-to-end reliability is derived to formulate the optimal scheduling problem,which can be further solved by using the incremental algorithm.Then,numerical analysis confirms that the achieved end-to-end reliability performance can be improved by using the finite channel-state-information of the correlated fading links,particularly when the transmission delay constraint is not so strict.【期刊名称】《通信技术》【年(卷),期】2017(050)010【总页数】5页(P2285-2289)【关键词】端到端可靠性;传输调度;有限状态马尔可夫信道;无线多跳网【作者】宋勇;席伟;戢纳【作者单位】中国移动通信集团设计院有限公司四川分公司,四川成都610045;中国移动通信集团设计院有限公司四川分公司,四川成都610045;中国移动通信集团设计院有限公司四川分公司,四川成都610045【正文语种】中文【中图分类】TN914当前，延迟受限的无线多跳网中的数据传输调度的研究多关注效率和速率[1-4]，多忽略了有限延迟情况下端到端的可靠性，即从源地址正确传输到目的地址的概率。