Istituto di Informatica e Telematica     
Brar G., Blough D. M., Santi P. Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks. In: Mobicom - Twelfth ACM Annual International Conference on Mobile Computing and Networking (Los Angeles USA, 2006). Proceedings, pp. 2 - 13. ACM, 2006.
Wireless mesh networks are expected to be widely used to provide Internet access in the near future. In order to fulfill the expectations, these networks should provide high throughput simultaneously to many users. Recent research has indicated that, due to its conservative CSMA/CA channel access scheme and RTS/CTS mechanism, 802.11 is not suitable to achieve this goal.In this paper, we investigate throughput improvements achievable by replacing CSMA/CA with an STDMA scheme where transmissions are scheduled according to the physical interference model. To this end, we present a computationally efficient heuristic for computing a feasible schedule under the physical interference model and we prove, under uniform random node distribution, an approximation factor for the length of this schedule relative to the shortest schedule possible with physical interference. This represents the first known polynomial-time algorithm for this problem with a proven approximation factor.We also evaluate the throughput and execution time of this algorithm on representative wireless mesh network scenarios through packet-level simulations. The results show that throughput with STDMA and physical-interference-based scheduling can be up to three times higher than 802.11 for the parameter values simulated. The results also show that our scheduling algorithm can schedule networks with 2000 nodes in about 2.5 minutes.
DOI: 10.1145/1161089.1161092
Subject STDMA scheduling
network capacity
physical interference model
wireless mesh networks

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional