Fair and efficient transmission scheduling in multihop packet radio networks

A scheduling algorithm for packet transmission is designed for multihop packet radio networks. The design objective is to have a schedule with minimum cycle length, maximum network throughput and fair allocation of transmission capacities among all stations. For comparison with other scheduling algorithms in the literature the following performance measures for scheduling algorithms are derived: (1) the cycle length, (2) the scheduling delay, (3) the minimum transmission capacity and (4) the normalized network capacity. The new algorithm is found to give schedules that have (1) the shortest cycle length, (2) the smallest scheduling delay, (3) the largest minimum transmission capacity and (4) the same normalized network capacity as two of the best scheduling algorithms in the literature