FFCS:WiMAX Mesh网络中一种流公平集中式调度算法

FFCS:a Centralized Scheduling Algorithm Based on Flow Fairness in WiMAX Mesh Network

在WiMAX Mesh集中式调度模式下,通常难以同时保证带宽分配的公平性和网络的吞吐量,从而造成拥塞或低吞吐量等问题.本文综合考虑公平性和空间重用性两个方面,提出基于流公平的WiMAX Mesh集中式调度模型,将调度问题归结为0-1非线性规划问题.由于非线性规划是一个NP难解问题,难以求出最优解,本文提出一种启发式调度算法FFCS,采用拉斯维加斯随机算法思想,将随机初始调度调换成较优调度,通过增加随机次数取优逼近最优解.仿真实验表明,FFCS在带宽分配的公平性上比两个典型调度算法LIF和MRF略有提高,当带宽请求较少时网络吞吐量分别比两个算法提高了12.2%和19.8%,带宽请求较多时可提高15.5%和21.6%.

It is usually hard to obtain both fairness of bandwidth allocation and good throughput under WiMAX Mesh Centralized Scheduling mode.In this paper,we tradeoff bandwidth allocation fairness and spatial reuse,then propose a novel centralized scheduling model based on flow fairness.In this model,scheduling scheme come down to a 0-1 nonlinear programming problem.Since nonlinear programming is a NP hard,finding an optimal solution is difficult.We put forward a Heuristic algorithm named FFCS to approximate the optimal solution.FFCS is based on Las Vegas random algorithm,which changes random initial scheduling to a better one.By increasing the number of random initial scheduling,FFCS gradually approaches optimal solution.Simulation results show that fairness performance of FFCS is better than other two typical scheduling algorithms： LIF and MRF.Compared with these two algorithms,FFCS increases throughput by 12.2% and 19.8% in low requirement network,15.5% and 21.6% in high requirement network.