基于Fibonacci的动态带宽分配算法

针对WiMAX系统中混合业务的特点,提出一种基于Fibonacci的动态带宽分配算法。介绍Fibonacci数列以及带宽调度的体系结构,对于实时轮询业务,在达到其能容忍的最大时延之前完成带宽分配。实验结果表明,与亏空公平优先队列算法相比,该算法能满足不同类型业务的QoS需求,提高系统吞吐量,且具有较好的服务公平性。

第3 8卷第 6期V_1 0. 38 N O. 6

计

算

机

工

程

21 0 2年 3月M a c 2 2 r h 01

Co utrEn ne rn mp e gi e i g

网络与通信

文章编号： 0o-48 o2 6_l—0 1o-32( 1) _ol 3 2 o 6

文献标识码： A

中圈分类号： P9. T33 1 0

基于 Fb n ci io ac的动态带宽分配算法陈嫒援，冯慧芳(西北师范大学数学与信息科学学院，兰州 707) 300 摘要：针对 Wi X系统中混合业务的特点，出一种基于 F oac的动态带宽分配算法。介绍 Fbnci MA提 i nci b i ac数列以及带宽调度的体系结 o

构，对于实时轮询业务，在达到其能容忍的最大时延之前完成带宽分配。实验结果表明，与亏空公平优先队列算法相比，该算法能满足不同类型业务的 Qo S需求，提高系统吞吐量，且具有较好的服务公平性。

关健词：动态带宽调度；F o ac数列；吞吐量；公平性 i nci b

Dy a i n wi t l c to g rt m s d 0 b n c i n m cBa d d h Al a i n Al o ih Ba e n Fi o a c oCHEN a u n FENG i a g Yu n y a, Hu - n f( o l eo te t s n f r t nS in e No h e t r l ie s y L n h u7 0 7, hn ) C l g f e Mah mai dI o ma o ce c,￣ w s No ma v ri, a z o 3 0 0 C ia ca n i Un t

[ sr c]Acodn o tec aatr t so h xd b s esi i Ab tat crig t h hrce si ftemie ui s nW MAX ytm,ti pp rpo oe y a cb n wit l ct n i c n ss e hs a e rp ssad n mi ad d al ai h o oag rtm a e nFio a c . t nrdu e b n c isq n e a d te s se tu tr fba d dh s h d l.F rRe lTi ePo ln e vie lo h b sd o b n c i I i t i o c sFio a c e ue c, n h y tm s cu eo n wit c e u e o a m li g S r c r

( P )srie i fns

e eb n wit l c t n b fr e ls tlr td ly E p r na eu t s o a o ae t ed f i fi RT S evc, t i st a d dh al ai e oe t a t oe a e . x e me tl s l h w t t mp rd wi t e c a i h h o o h n a i r s h c hh i t r

p o t u u lo tm,tepo oe lo tm a ai y teQu ly o evc ( S e urmeto iee ttp s tas mpo e h ii r ry q e eag rh i h rp sd a rh c nstf ai fS rieQo )rq i gi s h t e n fdf rn y e.I l i rv ste f ot r u h u fs tm n o d s r i ef i e s h o g p t yse a d g o e v c a r s . o n

[ ywo d]d n mi a d d hd l; io ac sq e c;ho g p tfi es Ke r s y a cb wit s eue Fb n ci eu ne tru h u;a n s n h c r DOI 1.9 9jsn1 0 .4 8 0 20 .3: O3 6/i . 03 2 . 1 .60 8 .s 0 2

1概述宽带无线城域网( rls Me o oi nA e t rig Wi es t p la raNe kn, e r t wo WMA的空中接口规范为 IE 821 N) E E 0 .6标准，是解决最后一

改进算法，例如 M— WD、C E L F D—DD、VFC E D、E、—D— D XP

M—XP等 J E。文献【] 6考虑多服务流的特点，出一种公平有提效的调度与资源分配策略，达到 Q S需求并使系统吞吐量最 o大化。文献【] 7针对 Wi X实际应用中不同数据业务的突发 MA性，提出一种改进的 D P F Q算法，该算法在保证系统总吞吐

公里宽带 WMAN接入问题的全球统一标准川。该标准支持点到多点(on t on, MP和网格 2种模式。 P P itoMuiP itP ) t l在 MP模式下，WMA由一个基站( ae Sa o,B )多个子站 N B s t in S和 t (u t in s ) S b Sa o, s组成，起中心控制作用的 B t S负责管理其辖区内各个独立的 s 。 s】 基于 I E 8 21准的 Wi X技术定义 4种类型的

E E 0 .6标 MA

量的前提下，降低实时业务的平均延时，同时提高实时业务的通过量。本文受 E D算法和 DF Q算法的启发，提出一 D P种基于 Fb n c i的动态带宽分配算法一一F s F n ci io a c B (m0 acB sdD n mi B n wit c e uig算法。 ae y a c a d dhS h d l ) n

业务： j主动授权业务 uG ( n oii dGrn evc )实时 su s1 t a t ri, ce S e轮询业务 ( el i ol gS rieR P )非实时轮询业务 R a TmeP l n evc, T S, i

2基于 Fb n ci io ac数列的动态带宽分配算法21 Fb n ci . io ac数列自然界神奇数列 Fb n ci io ac数列，表现为：1 1 2 3 5 8,,,,,, 1, 1…,每一项都等于前两项的和。如果设 F n为该数列 3 2, ()

( o elTme P ln evc,N T S和尽力而为业务 N n R a i ol g S rie R P ) i ( et f r B ) B s E f t E。各类服务连接优先级按照从高到低的顺序 o,可排列为 U、R P、N T S E,但 Wi GS T S R P、B MAX没有提供不同优先级业务具体的调度方案。

的第 n项∈Ⅳ。 )那么其通项公式为： () 1 F 2=, () F I=, ()1 F n=F n 1 F 2,其中，n 3 4…。其最重要的一个属性就是 (- )一 )+=,,

目前已有很多关于 Wi X的无线资源管理文献。如文 MA献【】 4较全面对 Wi X的各种调度算法进行总结，其中有代 MA表性的包括固定优先级 (ie r ry P、加权公平队列 Fx d Pi i,F ) ot ( ihe a u un, Q、最早到期( al s Dedie Weg t F i Q eig WF ) d r E r et al i nD e DD、亏空公平优先队列 ( eii F i Piry Quu, u,E ) D f t a r i ee c r o t

随着数列项数增加，前一项与后一项之比越来越逼近黄金分割值 06 8 3 8,故此属性可写为： .1 39… 0

Fn= (+ -) . 8 (+ Fn i 1 o 1/6科学研究在许多现象中都呈现出 Fb n ci io ac数列的规律。 本文算法就是基于 Fb n ci列这一重要属性而展

开的。 io ac数

D P等算法。这些算法各有优缺点，F F Q) P算法和 WF Q算法考虑不同业务类型优先级，但不能保证实时业务最小延迟需求；E DD算法考虑各类业务的最大容忍延迟 d,在 d的值达

2带宽调度体系结构 . 2由于 UGS的优先级最高，若带宽允许，总是被分配则基金项目：甘肃省科技计划基金资助项目(1 7 J A 3 )甘肃省教 10 R Z 2 4; 育厅科研基金资助项目( 0—3;西北师范大学知识与科技创新工 0 1 ) 9 0程基金资助项目( NWNU KJ XGC一35 )— C 0—2

到之前对该业务进行调度，算法能保证实时业 Q SQ a t该 o ( u ly i o rie需求，但缺乏服务公平性；D P f evc) S F Q算法动态调配上行和下行子帧中不均衡的数据流，但它仅对单个连接的带宽请求消息进行先到先服务的处理，没有考虑子站和系统总的

作者简介：陈嫒媛(93,, 18一)女硕士研究生，主研方向：网络性能评价；冯慧芳，副教授、博士

吞吐量。基于以往算法，研究者们提出一些针对各种业务的

收稿日：21-—8期 01 80 0

Ema: hnunm e1 6. r - i cenou br@13 o l cn