Designing transmission schedules for wireless ad hoc networks to maximize network throughput

We present a method for maximizing the throughput of mobile ad hoc packet radio networks using broadcast transmission scheduling. In such networks, a terminal may become a bottleneck if it is not allocated enough transmission slots in the current transmission schedule to handle the traffic flowing through it. Topology induced bottlenecks may arise frequently in ad hoc networks due to uneven distributions of terminals. Terminals in sparse areas of a network may be required to forward a large amount of traffic to facilitate communication between dense areas of the network. We address this problem by modifying the broadcast transmission schedule so that terminals handling more traffic have more opportunities to transmit. First, we describe a theoretical framework for analyzing the performance of a given schedule in terms of end-to-end stable throughput; we also define the upper bound for this performance. Next, we introduce a centralized algorithm that uses a process similar to simulated annealing to generate schedules with near optimal performance. We conduct simulation studies to show that transmission schedules produced by the centralized algorithm offer greatly improved performance over a simple, collision-free transmission schedule in terms of end-to-end packet delay, throughput, and completion rate. These studies are performed on a variety of test networks to generalize results and demonstrate the wide applicability of these principles.