[发明专利]一种基于新贪心策略的按需服务数据包调度贪心算法

摘要

本发明属于计算机无线通信技术领域，涉及在基站集成无线网络环境下,一种基于新效用函数贪心策略的按需服务数据包调度贪心算法。首先我们建立该环境下数据包调度问题的数学模型，包括时隙模型和报文请求模型，将原问题转化为整形规划问题，这种整形规划问题可以证明为NP问题，在线性时间内不能找到其最优解，根据模型的特殊情况，可以将问题转化为0‑1整形规划问题，这样可以大大的减少求解问题的复杂性。在实际的online条件(即当前只有部分信道情况已知，部分待调度报文到达)下，基于本文提出的效用函数函数值的贪心策略比基于现有效用函数的贪心策略具有更好的仿真效果，能够提高分配报文的总效益。

主权项

一种基于新贪心策略的按需服务数据包调度贪心算法，其特征在于如下步骤：步骤一，将按需服务的数据包调度问题转化为整数最优规划问题；1)建立时隙模型；和表示网络用户进入和离开信息站h,h＝1,2,…,H的传输范围的时刻，时间在每个间隔期间内被等分为时长TF的时隙，第H信息站覆盖的区域分为个时隙，用于数据传输的时隙总数确定在信息站每时隙内的最大数据包传输数量Cn,n＝1,2,…,N；2)建立服务请求模型；设用户服务请求集合为S，S中的每个服务请求s(s∈S)表示为一个四元组：(Gs,Qs,Ds,Ws(n))    (1)其中，Qs为每个服务需要被调度的数据包数量，Gs为每个服务的到达时间，Ds为该服务的最晚调度时间，Ws(n)为收益，其中n为该数据包的发送时隙；如果该服务的请求在它的生命周期[Gs,Ds]内被调度，那么该请求的每一个数据包将会获得一定收益，否则将不会获得收益；3)将问题转化为求解最优整数规划问题；令xns表示请求s在时隙n内发送数据包的数量，则调度方案表示为向量该调度方案将调度产生的总收益表示为如下目标函数：maxXΣs∈S[Ws(n)Σn=GsDsxns]---(2)]]> 其中，xns∈Z+,∀n∈[Gs,Ds],∀s∈S---(2a)]]>Σs∈Sxns≤Cn,∀n=1,2,...,N---(2b)]]>Σn=GsDsxns≤Qs,∀s---(2c)]]>步骤二，将整数最优规划问题转化为0‑1最优规划问题；根据时隙n的容量Cn，该时隙被划分成Cn个微时隙，每个微时隙的容量是1，即最多仅一个数据包可以在每个微时隙内调度传输；通过这种映射关系，N个时隙共产生个微时隙；经过映射后，服务s的到达时间Gs和最晚调度时间Ds分别转化为：和令m表示微时隙的序号，xms表示微时隙m∈[gs,ds]内服务s传输数据包的数量，且xms∈{0,1}；maxXΣs∈S[Ws(m)Σm=gsgsxms]---(3)]]> 其中，xms∈{0,1},∀n∈[gs,ds],∀s∈S---(3a)]]>Σs∈Sxms≤1,∀m---(3b)]]>Σn=gsdsxms≤Qs,∀s---(3c)]]> 步骤三，根据新贪心策略采用贪心算法对该问题进行优化求解； 1)提出一种新的效用函数值作为新贪心策略：Us=Ws×Qs1-α1-α,α≥0,α≠1---(4)]]> 其中α是可变的参数； 2)基于1)中的新贪心策略利用贪心算法求解式(3)。