Computer Engineering and Applications计算机工程与应用 2007,43( 无线自组网络中公平带宽分配机制的研究 张晓梅 ZHANG Xiao—mei 上海工程技术大学计算中心,上海201620 Shanghai University of Engineering Science,Shanghai 201620,China mail.com E—mail:zxmccnu@hot_ZHANG Xino-mei.Research On fair bandwidth allocation scheme in wireless Ad Hoe networks.Computer Engineering and Appfications,2007,43(22):133—135. Abstract:Three m0de1s on bandwidth allocation for WANET are studied and compared.We propose a new price—based max—rain fair bandwidth allocation scheme,which is shown to be adaptive to the routing changeovers arising from the mobility of wireless networks in the sense that the baJ1dwidth allocation is still able to maintain max-min fairness for wireless mobile networks.The simulation resuIts show that山is method is able to meet the wireless constraint and to achieve max—min fainess among mulrti— hop flows in wireless networks even if the topology varies,as is the case in a mobile environment・ Key words:bandwidth allocation;wireless Ad Hoc networks;max—min fainess r摘 要:对已有的三种无线自组网络的带宽分配算法进行比较研究,并提出了一种新的基于代价的最大最小带宽分配机制。此机 制不仅能保证最大最小公平性,而且可以适应无线网络的移动性引起的路由变化。仿真结果表明,该方法能够满足无线网络的约 束,并且在移动的环境中也能够对无线网络数据流进行最大最小公平带宽分配。 关键词:带宽分配;无线自组网络;最大最小公平性 文章编号:1002—8331(2007)22—0133—03 文献标识码:A 中图分类号:TP393 1 引言 近几年.无论是在有线网络中还是无线网络中,带宽分配 而达到公平分配带宽的目的。通过仿真结果表明,该算法能够 满足MAC限制并且在无线多跳网络中使得多跳数据流之间达 到最大最小公平性。甚至是由移动引起的拓扑结构多变的环境 问题引起了许多学者的高度重视 。带宽分配问题在有线网络 和无线网络中有很大的差别。因为在无线网络中,由于一个发 送器对于邻近接收器的冲突使得一些周围的链路不能同时被 下也能达到公平的带宽资源分配。 使用。大多这种额外的限制在蜂窝电话领域以“群限制”的概念 被首次提出来 ,并且[31将其应用于自组网络中。如果每条链路 具有一个有限的资源(频率或者扩展编码),一组更简单的限制 集合就产生了;在这种情况下,这种额外的限制归纳于“MAC 限制”,这就要求每个结点不能同时发送和接收数据包嗍。因此, 在无线自组网络中进行带宽分配时。既要考虑信道带宽限制又 要考虑这些额外的限制。 文献[3]和文献 ]提出了在无线自组网络中满足“MAC限 制”条件下进行最大最小公平带宽分配的调度算法。同样考虑 “MAC限制”,使用基于优化框架,文献[1]的作者们研究了一种 基于速率的拥塞控制算法,从而达到数据流之间的比例公平带 宽分配。文献[3]在考虑“群限制”条件下提出了一种基于代价的 带宽分配机制,从而实现各竞争数据流带宽分配之间的比例公 2无线网络限制描述 本文将链路模拟为具有固定的带宽,基于这些情况下(1) 信道带宽的改变被物理层译码所屏蔽,这种调制机制使得对在 高层看来,信道不是时变的而是不变的;(2)信道的改变比拥塞 机制控制的速度要慢很多。用一个无向图G( , ,C,F), 表 示无线网络中结点集合,L表示无向图中的边集合,C表示各 链路带宽集合,F表示数据流集合。 无向图的每个群都是一个完全网状子图。一个最大群是指 不包含任何其它群的子图的群。很明显.G中群的任何两条边 都存在竞争,不能同时发送/接收数据包【3],即在一个群中各条 边活动占有一定的时间比例,一个群中所有边使用的时间比例 总合不能超过1。“群限制”用数学公式描述如下: 平性。这三种无线自组网络带宽分配算法在资源优化、公平性、 分布式特性等方面各有优点和缺点。本文也同样在考虑“MAC 限制”条件下,提出了一种新的基于代价的最大最小公平性带 宽分配机制,它通过将传输路径中所有结点的代价的最大值作 。ZE s ES(Z)C/ ∑∑ ≤1 (1) ,c 表示流s在群r中流经链路f所占的时间比例,C 表示G 中第i个最大群中的边集合。 “MAC限制”是比“群限制”更简化、更宽泛的限制,它要求 为反馈信号。源端通过收到的反馈信号调节数据流的速率,从 作者简介:张晓梅(1981一),女,助教,主要研究方向为计算机网络。 对于共享结点的流相互竞争,不能同时发送和接收数据包;没 维普资讯 http://www.cqvip.com 134 2007.43(22) Computer Engineering and Applications计算机工程与应用 最大最小公平的带宽分配。此机制基于结点代价的模型,将代 价作为反馈信号返回给源端,源端再根据反馈回的信号调节下 一有共享结点的流互相之间没有竞争,可以同时发送和接收数据 包。在实际中这个条件存在于蓝牙(blue tooth)网络和单无线 电波(single radio)并采用FDMA或CDMA技术的无线网络中。 也可以这样描述.在一个结点上各条数据流接收/发送数据占 时刻的发送速率,从而达到整体的公平带宽分配。无线网络 网络拓扑变化的情况下仍然能够对数据流进行最大最小公平 的移动性一般会引起网络拓扑结构的变化;提出的算法即使在 带宽分配。此外,由于它完全分布式的特性,这种机制非常适用 有一定的时间比例,而所有此结点上的数据流使用的时间比例 总合不能超过1。“MAC限制”用数学公式描述如下: Z x( + l (2) 于实际应用中。 4.1 问题描述 本文考虑链路具有固定带宽的无线多跳自组网络,同时满 ,(r)表示在结点r上的数据流集合,z (r,s)和 (r,s)分别表示 数据流s流进和流出结点r的链路。对于任何流的源结点q )= 足无线网络的MAC限制。运用Kellv的效用最大化的理论口,61 中的代价更新方法(规则),约束于无线多跳自组网络模型中的 。。;对于任何流的源结点 ):。。。可以看出, 可以解释 额外限制。设,表示数据流集合,I(r)表示在结点r上的数据流 u‘Ci.J) 集合。所有数据流效用函数总合的优化约束于MAC限制如下 为数据流s单位时间在结点r接收数据包的时间比例; 表示: ‘0 ) 表示数据流s单位时间在结点r发送数据包的时间比例。本文 max∑ ( ) (3) 提出的基于代价的带宽分配机制考虑无线网络中的“MAC限 制”实现对数据流的最大最小公平带宽分配。 s.t. Xs(— 一+— 一)≤1 (4) ¥EI(t) I(r’|) L(¨) 3带宽分配算法介绍 式(3)中的目标函数是严格凹函数,采用与文献【2,6】相似 对已有的三种无线自组网络的带宽分配算法进行研究:最 的方法推导.可以得到新的无线网络中的代价迭代公式: 大最小公平调度算法、基于速率控制器的带宽分配算法以及基 r 1 于代价的比例公平带宽分配算法。这些算法在资源优化、公平 P,(()t+1):1=l,P ( )+y(∑ (y( ()t)(上— ++上— 一))一1)l)I (5) L s el(r) ‘(¨) ‘(,'5) J 性、分布式特性等方面各具有自己的优缺点。 文献『41提出了一种最大最小公平数据包的调度机制,这种 这里参数y表示步长,函数 。定义为 。=max{z,0l。P,可以 机制能够对于无线自组网络的单跳数据流进行公平的带宽分 将p,解释为单位时间使用结点r所花的代价。式(5)同样也与 配.并且在公平性和资源利用之间达到很好的平衡。但是,此机 市场规律一致:如果在结点r上所有数据流要占用的时间比例 制没有考虑在真实无线自组网络的通过多跳的端到端数据流 总合超过1,结点的价格P,( )就会上涨;反之,P,( )就会下降。 情况.并且同时考虑资源利用和公平性时不能达到整体优化。 在设计的方法中,术语“代价”简单地作为一种拥塞信号来引导 文献【11的作者们运用优化框架,设计了一种带权值的比例 源端的决策。 公平性拥塞控制算法来实现对数据流的带宽分配。这种方法将 4.2最大最小公平带宽分配算法 MAC限制表示成一种信道时间限制.同时在延迟存在的情况 设A(s)表示数据流经过的所有结点的集合s。系统中,数 下,算法能够达到全局稳定。文献【31对于信道切人使用基于群 据流的源端要对每单位带宽付费。因此每个结点根据公式(5) 的代价机制,而不是有线网络中传统的基于链路的代价机制。 来计算数据流使用自己所需付的单位代价,而这种代价又作为 在这个模型的基础上.作者们对于端到端多跳数据流提出了一 反馈信号来反映在无线结点上的通信负载情况。模型中,结点 种基于代价的比例公平带宽分配。文献【1,31的两种带宽分配机 代价作为反馈拥塞信号来控制数据流的速率。数据流s经过的 制都需要知道用户的效用函数或“满意”函数.这样才能在分配 端到端的传输路径上所有的结点中最大代价值反馈给数据流 网络带宽的同时最大化效用函数的总和。这种方法的缺点在于 s源端,即拥塞信号g 。使用这种方法,设计的这种机制就可以 用户必须直接知道他们自己的效用函数。可大多数情况下,用 控制和调节源端数据流的发送速率.从而达到公平的带宽分 户的满意度并不能用分配带宽的具体函数表示出来。 配。此机制如图1所示。 表1分别从公平性、效用优化、限制、分布性等方面将这三 反馈信号q, 种带宽分配算法进行了比较。 表1无线自组网络三种带宽分配机制的}B较 吼 l q,=max(q,,P2) =max(q,,P3)q,=max(q,,P4) 数据流 图l 基于代价的最大最小带宽分配机制模型 最大最小公平调度算法最大最小公平性 否 MAC限制单跳非完全分布式 基于速率拥塞控制机制带权比例公平性 是 MAC限制多跳 完全分布式 为了实现这个目标.数据包格式必须包括一些数位存储完 基于代价带宽分配算法 比例公平性 是 群限制 多跳 完全分布式 整的拥塞代价值。如果结点原来的代价值比经过它的数据包中 的代价值要小,结点就将数据包中的代价值作为自己新的结点 4一种新的基于代价的最大最小公平性带宽分配 代价值存储下来。数据流s源端有一个需求函数D。(・),这样 算法 可以调节它的发送速率 :D (q )。在模型中,所有数据流的需 本文提出了一种新的基于代价的带宽分配机制,在满足无 求函数都是齐次函数。具体的算法描述如下: 线自组网络MAC限制的条件下.从而达到对多跳数据流进行 (1)在结点r执行的算法 维普资讯 http://www.cqvip.com
张晓梅:无线自组网络中公平带宽分配机制的研究 2007,43(22) 135 在t=l。2,…时刻。结点r执行下面步骤: ①对于通过结点r的所有数据流,从它们数据包中得到每 一条数据流的速率; ②利用这些信息计算公式(5)来得到下一时刻新的代价值; ③对于所有经过结点r的数据流,从它们的数据包头部得 到代价值g ,将g 与新算出的结点r代价值P (t+1)比较。如果 P,(f+1)比g 大,则结点r将P (抖1)的值赋给g 。 (2)在数据流s源端执行的算法 在t=l,2,…时刻,数据流s源端执行下面步骤: Reratlon ①数据流s源端从数据流的数据包里得到反馈信息代价 图3 拓扑结构变化前后的数据流带宽分配 值g (f); ②为下一时刻计算新的传输速率:x(t+1)=D(g (t)); 以达到最大最小公平。无线网络中的最大最小公平分配带宽的 情况下。每个结点对于经过自己的数据流都平均分配带宽。这 ③在下一时刻以 (t+1)的速率发送数据包,并将 (t+1) 样数据流1。2在结点1上可以得到1/3 Mb/s,在结点5得到 的值存储在数据包相应的字节中。 1/4Mb/s。因此,数据流1,2由于结点5的限制不能得到超过 14/Mb/s的带宽。同样地,数据流4由于结点6的限制不能得 5仿真结果 到超过3/8Mb/s的带宽,数据流3由于结点3和4的限制不能 仿真的拓扑结构如图2中的(sd W/毒 1 O O O O O O O O Oa)和( O b),分别表示300更新 得到超过1/2 Mb/s的带宽。因此在4条数据流中的最大最小公 步之前的拓扑结构以及300更新步之后由于路由的变化而导 O 9 8 7 6 5 4 3 2 1 O 平带宽分配相应为1/4 Mb/s,14/ Mb/s,12/ Mb/s,3/8 Mb/s。与最 致变化的拓扑结构。网络中的信道带宽设为单位带宽1 Mb/s。 大最小公平调度算法相比嗍,提出的基于代价的带宽分配方法 拓扑结构变化前和变化后4条数据流所分配的带宽如图3 不仅是一种完全分布式算法对带宽进行最大最小公平带宽分 所示 配.而且可以满足真实无线自组网络的通过多跳的端到端数据 流情况,并适应无线网络的移动性引起的路由变化。 6结束语 lfowl 本文从公平性、效用优化、限制、分布性等方面比较研究了 已有的三种无线自组网络的带宽分配算法。在此基础上,设计 了一种新的基于代价的最大最小带宽分配机制。该方法能够满 足无线网络的约束。并且在移动的环境中也能够对无线网络数 据流进行最大最小公平带宽分配。因此此机制更适用于移动 的,多跳的无线自组网络环境下。目前关于基于代价的公平带 宽分配机制还有待于完善,作者正在系统稳定性方面作进一步 工作。(收稿日期:2006年l1月) (a)300更新步之前 lfowl 参考文献: [1】Yi Y,Shakkottai S.Hop-by-hop congestion control over a wireless multi—hop network[C]//Proceedings of the IEEE Infocom’04。Hong— Kong,China,Mamh 2004. [2]Kelly F,Maulloo A,Tan D.Rate control in communication net— works:shadow price。proportional fainress and stability[J1.Journal of hte Operational Research Society,1998,49(3):237—252. [3】Xue Y,Li B,Nahrstedt K.Price—based resource allocation in wire— less ad hoc networks[C NCS:Proceedings of the Eleventh Inter_ (b)300更新步之后 national Wo ̄shop on Quality of Service(IWQoS).ACM Springer— 图2网络拓扑结构 Vedag,Monterey,CA,June 2003,2707:79—96. 从仿真结果可以看出算法收敛于50个更新步之内。更新 [4】Tassiulas L,Sarkar S.Maxmin fair scheduling in wireless networks[C]// Proceedings of IEEE Infocom’02,New York,June 2002:763-772. 的实际速度取决于步之间的间隔时间。在仿真中,某一时刻的 [5]Everitt D,Macfadyen N W.Analysis of muhicellular mobile ra— 数据流速率完全反映了前一时刻的代价变化。这就要求一个时 diotelephone systems with loss[J1.Br Telecom Technol J,1983,1: 间间隔至少是一个R 1TI’(Round Trip Time)。如果网络最大的 37—45. R 1TI’为100 ms,则算法收敛于将近5 s,具有较好的收敛性。一 [6】Kelly F.Charging and rate control for elastic traffic[J1.European 旦拓扑结构变化后系统达到平衡后,4条数据流的速率仍然可 Transactions on Telecommunications,1997,8(1):33—37.
因篇幅问题不能全部显示,请点此查看更多更全内容