一种宽带多媒体卫星系统带宽动态调度方法

摘要

本发明公开了一种宽带多媒体卫星系统带宽动态调度方法，该方法包括带宽请求列表更新，确定带宽请求的实数分配结果，将带宽请求的实数分配结果转为整数，分配剩余时隙四个周期性顺序启动的操作步骤，该方法能够在兼顾宽带多媒体卫星系统中分组传输时延性能的同时，提高带宽调度服务的公平性。

说明书

技术领域

本发明涉及宽带多媒体卫星系统中的一种带宽调度方法，具体涉及 一种采用多频时分多址接入（Multi-frequency Time Division Multiple  Access MF-TDMA）体制的宽带多媒体卫星系统中的带宽动态调度方法。

背景技术

宽带多媒体卫星系统以传输高速宽带多媒体业务为主要特色近年来 获得了迅猛发展。与传统卫星通信系统相比，其最大的不同之处在于承 载的业务由低速的数据、话音业务转变为集图像、声音、视频、文本为 一体的高速率、交互式多媒体业务。由于系统承载的用户数更多，业务 突发性更强，为系统的带宽管理带来更加严峻的挑战。

为了高效利用带宽资源，现有宽带多媒体卫星系统大都采用 MF-TDMA体制，其带宽管理分为连接和突发两个层次：连接层主要是针 对话音、视频等实时业务进行连接准入控制；突发层主要是针对网页、 电子邮件等非实时业务进行带宽动态调度。相对固定分配和随机分配， 带宽动态调度即可保证业务的可靠发送又可实现卫星波束覆盖区内不同 终端不同业务连接对带宽的统计复用，大大提高了系统带宽的利用率， 是宽带多媒体卫星系统带宽管理所采用的主要策略。

目前宽带多媒体卫星系统中有代表性的带宽动态调度的算法是 Le-Ngoc等人[1]在文献“Interactive Multimedia Satellite Access  Communications,IEEE Communications Magazine,vol.41,pp.78-85,2003” 中提出的联合按需自由分配多址接入（Combined Free/Demand Assignment  Multiple Access CFDAMA）协议族及其变种。目前广泛应用的基于卫星 回传链路的数字视频广播系统（Digital Video Broadcast-Return Channel via  Satellite DVB-RCS）标准所采用的带宽管理机制就是以该协议为基础。 CFDAMA协议在处理带宽请求时采用先按需分配，后自由分配的策略， 其中按需分配为基于带宽请求的先来先服务方式，该方法的问题在于先 来先服务无法很好的确保服务的优先级。

为解决该问题，Lee Ki-dong等人在文献“A real-time algorithm for  timeslot assignment in multirate return channels of interactive satellite  multimedia networks,IEEE Journal on Selected Areas in Communications, vol.22,pp.518-528,2004.”提出基于终端优先级权重进行带宽调度的方 法，该方法根据终端承载的业务类型将终端划分为不同优先级，带宽调 度基于事先划分好的优先级进行，该方法的问题在于终端的优先级一但 确定就很难改变，在此将该方法称为固定优先级调度(Fixed Priority  based Scheduling FPS)算法，而且该方法无法确保相同优先级终端之间的 带宽调度的公平性；

为解决该问题，Nicola等人在文献“An IP-based satellite  communication system architecture for interactive multimedia services," International Journal of Satellite Communications and Networking,vol.21,pp. 401-426,2003”中提出对来自相同优先级终端的带宽请求以跳转(skipping) 方式进行服务，在此称为轮询优先级调度(Skipping Priority based  Scheduling SPS)算法，但该算法没有考虑到MF-TDMA系统中终端分组 发送时机(Packet Transmission Opportunity PTO)对带宽请求发送先后顺序 的影响；

为解决该问题W.K.Chai等人在文献“Scheduling for proportional  differentiated service provision in geostationary bandwidth on demand  satellite networks,GLOBALCOM2005,pp.3722-3727”提出以分组等待时 间为先后顺序的调度算法，在此称为等待时间优先调度（Waiting Time  Priority Scheduling WTPS）算法，该算法提高了系统分组传输时延性能， 但在高负载尤其是系统“过载”时很难保证服务的公平性。综上所述，已 有的带宽动态调度算法没有将带宽调度服务公平性和分组传输时延性能 进行统筹考虑。

发明内容

本发明的目的在于提出一种适合MF-TDMA体制宽带多媒体卫星系 统的带宽动态调度方法，该方法能够在兼顾宽带多媒体卫星系统中分组 传输时延性能的同时，提高带宽调度服务的公平性。

本发明的技术方案是：一种宽带多媒体卫星系统带宽动态调度方法， 其特征在于，该方法包括四个周期性顺序启动的操作步骤：

步骤1：带宽请求列表更新，即对列表中带宽请求状态进行更新，并 将前一个带宽调度周期内新到达的带宽请求读入到带宽请求列表中；

步骤2：确定带宽请求的实数分配结果，即以带宽请求的等待时间为 优先级采用公平性调度算法根据各带宽请求的时隙请求数目，确定各带 宽请求的实数分配结果；

步骤3：将带宽请求的实数分配结果转为整数，即将步骤2所取得的 实数分配结果向下取整，得到对应的整数分配结果；

步骤4：分配剩余时隙，即根据步骤3得到的整数分配结果，将系统 中剩余的可用时隙按照带宽请求优先级由高至低，终端序号由大至小的 顺序逐个分配。

进一步地，在步骤1中需要维护一个带宽请求列表，其特征在于该 列表将带宽请求按照终端序号从1到Q进行排列，其中Q为大于1的正 整数，并为每个终端维护L个优先级的带宽请求，优先级最低的为1，最 高为L，其中L为大于1的正整数，每个带宽请求通过时隙请求数目x_i，j和带宽请求的等待时间T_i，j进行标识，其中i为终端序号，j为优先级标识。

进一步地，步骤1中所述带宽请求列表更新的方法具体包括：

步骤1.1：按照式(1)和(2)对各终端优先级L的带宽请求进行状态更 新；

x_i，L=x_i，L-1+x_i，L  i∈[1…Q]     (1)

T_i，L=T_i，L+T  i∈[1…Q]        (2)

步骤1.2：按照式(3)和(4)依次对优先级L-1到2的带宽请求进行状态 更新；

x_i，j＝x_i，j-1  i∈[1…Q]  j∈[2…L-1]    (3)

T_i，j＝T_i，j-1+T  i∈[1…Q]  j∈[2…L-1]   (4)

步骤1.3：根据前一调度周期到来的带宽请求R_i按照式(5)对列表中优 先级1的带宽请求进行状态更新。

x_i,1=R_i  i∈[1…Q]        (5)

进一步地，步骤2中所述以带宽请求等待时间T_i，j为优先级采用公平 性调度算法根据各带宽请求的时隙请求数目x_i，j，确定各带宽请求的实数 分配结果y_x，j，其中y_i，j是正实数，确定实数分配结果y_i，j的具体步骤包括：

步骤2.1：初始化变量λ^(k)＝0.01  k＝1；

步骤2.2：初始化变量i＝1...Qn＝1；

步骤2.3：根据式(6)计算y_i，j,并根据式(7)确定y_i，j取值。

$y_{i,j}=\frac{T_{i,j}}{{\lambda }^{\left(k\right)}+N_i^{\left(n\right)}}---\left(6\right)$

$y_{i,j}=\left(\begin{array}{cc}{y}_{i,j}& y_{i,j}\le x_{i,j}\\ x_{i,j}& y_{i,j}>x_{i,j}\end{array}\right)---\left(7\right)$

步骤2.4：根据式(8)更新

$N_i^{(n+1)}=N_i^{\left(n\right)}+0.01(R_{\max }-\underset{j=1}{\overset{L}{\Sigma }}{y}_{i,j})---\left(8\right)$

其中R_max每终端时隙请求数目上限，是一个大于1的正整数。

步骤2.5：判断(9)式是否成立，若成立，则转到步骤2.6，若不成立， 执行n=n+1，并转到步骤2.3;

$\left|N_i^{(n+1)}(R_{\max }-\underset{j=1}{\overset{L}{\Sigma }}{y}_{i,j})\right|<0.1---\left(9\right)$

步骤2.6：根据式(10)更新λ^(k+1);

${\lambda }^{(k+1)}={\lambda }^{\left(k\right)}+0.01(C-\underset{j=1}{\overset{L}{\Sigma }}\underset{i=1}{\overset{Q}{\Sigma }}{y}_{i,j})---\left(10\right)$

其中C为系统可用时隙总数，是一个大于1的正整数。

步骤2.7：判断式(11)是否成立，若成立则保存实数分配结果y_i，j并转 至步骤3，若不成立，则执行k＝k+1，并转至步骤2.2；

$\left|{\lambda }^{(k+1)}(C-\underset{j=1}{\overset{L}{\Sigma }}\underset{i=1}{\overset{Q}{\Sigma }}{y}_{i,j})\right|<0.1---\left(11\right)$

进一步地，步骤3中将所述步骤2所取得的实数分配结果y_i，j向下取 整，得到整数分配结果的方法是按照式(12)进行；

进一步地，步骤4中分配剩余时隙的具体步骤包括：

步骤4.1：根据式(13)获得剩余时隙数目C_remain；

$C_{\mathrm{remain}}=C-\underset{i=1}{\overset{Q}{\Sigma }}\underset{j=1}{\overset{L}{\Sigma }}{y}_{i,j}---\left(13\right)$

步骤4.2：令i＝Q,jL；

步骤4.3：按照式(14)计算y_i，j;

y_i，j＝y_i，j+min(x_i，j-y_i，j,C_remain)    (14)

步骤4.4：按照式(15)更新C_remain，若C_remain>0，则执行步骤4.5，否 则转入步骤4.7;

C_remain＝C_remain-min(x_i,j-y_i，j，C_remain)    (15)

步骤4.5：如果i>1则执行i=i-1并转入步骤4.3，否则转入步骤4.6

步骤4.6：如果j＞1则执行j＝j-1，i=Q并转入步骤4.3，否则转入步骤 4.7。

步骤4.7：根据式(16)对带宽请求列表中各带宽请求的时隙请求数目 进行更新。

x_i,j＝y_i,j-x_i,j    (16)

采用本发明的有益效果是：由于本发明以带宽请求的等待时间作为 带宽调度的优先级，因此能够提升系统在高负载业务条件下分组传输的 实时性，由于采用公平调度算法，因此可以有效保证带宽调度过程中的 公平性。

附图说明

图1为本发明的工作流程图；

图2为在采用PowONOFF业务源，归一化系统业务负载为0.95情 况下，本发明与其它算法的端到端传输时延概率累积分布对比图；

图3为在采用PowONOFF业务源，归一化系统业务负载为0.97情 况下，本发明与其它算法的端到端传输时延概率累积分布对比图；

图4为在采用PowONOFF业务源情况下，本发明与其它算法的服务 公平性对比图；

图5为在采用ExpONOFF业务源，归一化系统业务负载为0.95情况 下，本发明与其它算法的端到端传输时延概率累积分布对比图；

图6为在采用ExpONOFF业务源，归一化系统业务负载为0.97情 况下，本发明与其它算法的端到端传输时延概率累积分布对比图；

图7为在采用ExpONOFF业务源情况下，本发明与其它算法的服务 公平性对比图；

具体实施方式

以下将结合附图1-7对本发明的具体技术方案进行说明。

如图1所示，本发明通过四个周期性顺序启动的操作步骤实现，启动 的周期为T（单位为毫秒）。T可为MF-TDMA帧长也可为帧长的整数倍。 MF-TDMA帧长可以根据系统需求进行设计，例如可以参照欧洲电信标准 化组织制定的数字视频广播-基于卫星回传信道(Digital video  broadcasting-return channel via satellite DVB-RCS)标准中的设计，该标准 规定MF-TDMA帧长为26.5毫秒。

步骤1：带宽请求列表更新，即对带宽请求列表中带宽请求状态进行 更新，并将前一个带宽调度周期内新到达的带宽请求读入到带宽请求列 表中。表1给出了一个带宽请求列表的示例，从表中可以看出，终端序 号按照1到Ｑ的顺序排列，其中Ｑ为大于1的正整数，每个终端有L个 优先级的带宽请求，优先级最低的为1，最高为L，其中L为大于1的正 整数，每个带宽请求通过时隙请求数目x_i，j和带宽请求的等待时间T_i，j进 行标识，其中x_i，j为正整数，T_i，j正实数，i为终端序号，j为优先级标识。

表1带宽请求列表示例

终端序号 优先级1 ... 优先级j ... 优先级L 1 x_1,1/T_1,1... x_1，j/T_1，j... x_1,L/T_1，L2 x_2,1/T_2,1... x_2，j/T_2，j... x_2,L/T_2，L： ： ： ： ： ： i x_i,1/T_i,1... x_i，j/T_i，j  x_i，L/T_i，L： ： ...       Ｑ X_Q,1/T_Q,1... x_Q，j/T_Q，j  x_Q，L/T_Q，L

进一步地，步骤1可以分为以下三个操作步骤：

步骤1.1：按照式(1)和(2)对各终端优先级L的带宽请求进行状态更 新；

x_i，L=x_i，L-1+x_i，L  i∈[1…Q]   (1)

T_i，L=T_i，L+T  i∈[1…Q]    (2)

步骤1.2：按照式(3)和(4)依次对优先级L-1到2的带宽请求进行状态 更新；

x_i，j＝x_i，j-1  i∈[1…Q]  j∈[2…L-1]   (3)

T_i，j=T_i，j-1+T  i∈[1…Q]  j∈[2…L-1]  (4)

步骤1.3：根据前一调度周期到来的带宽请求R_i按照式(5)对列表中优 先级1的带宽请求进行状态更新。

x_i,1=R_i  i∈[1…Q]   (5)

步骤2：确定带宽请求的实数分配结果。以带宽请求等待时间T_i，j为 优先级采用公平性调度算法根据各带宽请求的时隙请求数目x_i，j，确定各 带宽请求的实数分配结果y_i，j，其中y_i，j为正实数；

进一步地，步骤2可分为7个操作步骤。在本实施例中，系统可用 时隙总数为C，每终端时隙请求数目上限为R_max。

步骤2.1：初始化变量λ^(k)＝0.01  k＝1；

步骤2.2：初始化变量i＝1...Qn＝1；

步骤2.3：根据式(6)计算y_i，j,并根据式(7)确定y_i，j取值。

$y_{i,j}=\frac{T_{i,j}}{{\lambda }^{\left(k\right)}+N_i^{\left(n\right)}}---\left(6\right)$

$y_{i,j}=\left(\begin{array}{cc}{y}_{i,j}& y_{i,j}\le x_{i,j}\\ x_{i,j}& y_{i,j}>x_{i,j}\end{array}\right)---\left(7\right)$

步骤2.4：根据式(8)更新

$N_i^{(n+1)}=N_i^{\left(n\right)}+0.01(R_{\max }-\underset{j=1}{\overset{L}{\Sigma }}{y}_{i,j})---\left(8\right)$

步骤2.5：判断(9)式是否成立，若成立，则转到步骤2.6，若不成立， 执行n=n+1，并转到步骤2.3;

$\left|N_i^{(n+1)}(R_{\max }-\underset{j=1}{\overset{L}{\Sigma }}{y}_{i,j})\right|<0.1---\left(9\right)$

步骤2.6：根据式(10)更新λ^(k+1);

${\lambda }^{(k+1)}={\lambda }^{\left(k\right)}+0.01(C-\underset{j=1}{\overset{L}{\Sigma }}\underset{i=1}{\overset{Q}{\Sigma }}{y}_{i,j})---\left(10\right)$

步骤2.7：判断式(11)是否成立，若成立则保存实数分配结果y_i，j并转 至步骤3，若不成立，则执行k＝k+1，并转至步骤2.2；

$\left|{\lambda }^{(k+1)}(C-\underset{j=1}{\overset{L}{\Sigma }}\underset{i=1}{\overset{Q}{\Sigma }}{y}_{i,j})\right|<ϵ---\left(11\right)$

步骤3：将步骤2所取得的实数分配结果y_i，j按照式(12)向下取整，得 到整数分配结果；

步骤4：分配剩余时隙。即根据步骤3得到的整数分配结果，将系统 中剩余的可用时隙按照带宽请求优先级由L至1，终端序号由Q至1的 顺序逐个分配。进一步地，可分为以下7个操作步骤：

步骤4.1：根据式(13)获得剩余时隙数目C_remain；

$C_{\mathrm{remain}}=C-\underset{i=1}{\overset{Q}{\Sigma }}\underset{j=1}{\overset{L}{\Sigma }}{y}_{i,j}---\left(13\right)$

步骤4.2：令i＝Q,jL；

步骤4.3：按照式(14)计算y_i，j;

y_i，j＝y_i，j+min(x_i，j-y_i，j,C_remain)    (14)

步骤4.4：按照式(15)更新C_remain，若C_remain>0，则执行步骤4.5，否 则转入步骤4.7;

C_remain＝C_remain-min(x_i,j-y_i，j，C_remain)   (15)

步骤4.5：如果i>1则执行i=i-1并转入步骤4.3，否则转入步骤4.6

步骤4.6：如果j＞1则执行j＝j-1，i＝Q并转入步骤4.3，否则转入步骤 4.7。

步骤4.7：根据式(16)对带宽请求列表中各带宽请求的时隙请求数目 进行更新。

x_i,j＝y_i,j-x_i,j    (16)

在OPNET Modeler14.0的环境下通过计算机仿真实验对本发明的实 施效益进行验证，仿真采用PowONOFF和ExpONOFF两种业务模型， 相关参数如表2所示。衡量指标包括分组端到端传输时延和服务公平性。 分组传输时延通过概率累积分布函数(Cumulative Distribution Function  CDF)来衡量，服务公平性通过公平性因子Y衡量，Y通过式(17)求得。

$\gamma ={\left(\underset{i=1}{\overset{Q}{\Sigma }}\underset{j=1}{\overset{L}{\Sigma }}(y_{i,j}/x_{i,j})\right)}^2/\left(\mathrm{QL}\underset{i=1}{\overset{Q}{\Sigma }}\underset{j=1}{\overset{L}{\Sigma }}{(y_{i,j}/x_{i,j})}^2\right)---\left(17\right)$

表2仿真参数

参数 取值 帧长(秒) 0.192 时隙/帧 1024 信元/时隙 1 上行基本信息速率 2.048Mbps 下行链路复用方式 统计复用 下行基本信息速率 8.192Mbps 星上交换体制 ATM 业务源模型 PowONOFF/ExpONOFF 归一化系统业务负载 0.1-0.97 仿真时间(秒) 180

图2和图3给出了业务源模型为PowONOFF，负载为0.95和0.97情 况下，分组端到端传输时延性能的对比，横轴是端到端分组传输时延值， 纵轴是对应的概率累积分布函数。从图中可以看出，负载为0.95时，SPS 算法的时延性能最差，负载为0.97时，FPS算法时延性能最差，这说明 SPS算法并不能总是改善系统的时延性能，在这两种负载条件下，本发 明的分组传输时延性能均优于其它两种算法，这主要是由于本发明在带 宽调度的过程当中充分考虑了数据分组在终端缓存处等待的时间。

图4给出了输入为PowONOFF模型情况下服务公平性的比较，横轴 是归一化系统业务负载，纵轴是公平性因子。公平性因子越大，说明服 务公平性越好。从图中可以看出，在低业务负载条件下，各种算法都能 充分满足终端的带宽需求，因此公平性因子均为1。负载大于0.9之后， 由于业务的突发性，导致部分时段系统业务过载，终端带宽请求无法得 到满足，服务公平性受到影响，相比之下本发明由于采用了公平调度的 策略，因此公平性因子始终优于其它两种算法。

图5和图6给出了输入为ExpONOFF业务源负载分别为0.95和0.97 情况下的分组传输时延性能比较，横轴是端到端分组传输时延值，纵轴 是对应的概率累积分布函数。从图中可以看出，本发明的分组传输时延 性能均优于其它两种算法，

图7给出了输入为ExpONOFF模型情况下服务公平性的比较，横轴 是归一化系统业务负载，纵轴是公平性因子。公平性因子越大，说明服 务公平性越好。从图中可以看出，在低业务负载条件下，各种算法都能 充分满足终端的带宽需求，因此公平性因子均为1。负载大于0.9之后， 由于业务的突发性，导致部分时段系统业务过载，终端带宽请无法得到 满足，服务公平性受到影响，相比之下本发明由于采用了公平调度的策 略，因此公平性因子始终优于其它两种算法。