基于背包理论的无线通信数据包优化调度算法

An optimal algorithm of data packets scheduling for wireless communication systems by using Knapsack theory

基于背包算法理论,提出了一种新的无线通信系统的资源优化调度算法,即数据背包填充算法(KFA),并详细分析了其参数的设置.该算法利用动态编程求解技术,从待传输的无线通信数据包中优选出一组最佳的数据包,并装载成帧发送.与传统的背包算法不同的是,该算法适合于多维目标优化.系统仿真分析的结果显示在用户数少于每扇区300时,FIFS算法和KFA算法的性能差别不很大,但是随着系统中用户数目增多,系统负荷变大时,采用KFA算法的系统吞吐率比采用FIFS算法的系统高20%,且KFA算法能满足不同用户对服务质量的个性化要求,可广泛应用于3 G和4 G等无线通信系统中.

An optimal data packets scheduling algorithm for wireless data communication systems, knapsack filling algorithm （KFA）, is presented based on Knapsack theory, in which the most suitable data packets were selected among the data packets scheduled for transmission and transfer them through frames by using dynamic program technology. The setting of the parameters of KFA was analyzed. Being different from the traditional Knapsack algorithm, KFA is for multiple-objective optimization. The system simulation results show that the system data packet throughputs of FIFS algorithm and KFA are similar when users in each cell are less than 300, but the throughput of KFA would increased by 20 % when the user number in each cell is large in the wireless communication system. KFA algorithm can improve the data throughput and satisfy different QoS requirements for users, and used in many wireless communication systems such as 3 G and 4 G systems.