Downlink data transmission scheduling algorithms in wireless networks

The problem of downlink data transmission scheduling in wireless networks is studied. It is pointed out that every downlink data transmission scheduling algorithm must have two components to solve the two subproblems of power assignment and transmission scheduling. Two types of downlink data transmission scheduling algorithms are proposed. In the first type, power assignment is performed before transmission scheduling. In the second type, power assignment is performed after transmission scheduling. The performance of two algorithms of the first type which use the equal power allocation method are analyzed. It is shown that both algorithms exhibit excellent worst-case performance and asymptotically optimal average-case performance under the condition that the total transmission power is equally allocated to the channels. In general, both algorithms exhibit excellent average-case performance. It is demonstrated that two algorithms of the second type perform better than the two algorithms of the first type due to the equal time power allocation method. Furthermore, the performance of our algorithms are very close to the optimal and the room for further performance improvement is very limited. It is shown that all the above algorithms can be extended to schedule downlink data transmissions with parallel channels. It is also shown that the simple sequential scheduling algorithm is optimal if the total transmission power is equally allocated to the channels. As an extra contribution, an M/G/1 queueing model for the FCFS queueing discipline is established, and it is observed that increasing the number of channels has more impact on the reduction of the average response time than increasing the total transmission power.