دانلود رایگان مقاله برنامه ریزی بی سیم با نرخ داده های متعدد: از دخالت فیزیکی به گراف دیسک ها

Abstract

Scheduling of wireless transmissions is a core component of performance optimization of wireless ad-hoc networks. Current radio technologies offer multi-rate transmission capability, which allows to increase the network’s throughput. Nevertheless, most approximability results of scheduling algorithms have focused on single-rate radios. In this paper, we propose two formulations for the problem of scheduling wireless requests with multiple data-rates, considering the physical interference model with uniform power assignment. The objective of both problems is to select a subset of communication requests to transmit simultaneously, such that the sum of their data rates is maximized and no collisions occur. In the first formulation, data-rates are given as part of the input. In the second formulation, the data-rate assignment is part of the solution. We show that, under certain constraints on the input, these problems can be approximated by a disk graph model. This means that, despite the global nature of the physical interference model, conflicts between simultaneous requests can be restricted to the local neighborhood of the transmitting nodes. We show how to build the corresponding disk graph instances and prove that a weighted maximum independent set in this graph-based model provides a constant-factor approximation in the physical interference model. Moreover, we implement a polynomial-time approximation scheme, as well as a parallel implementation of the algorithm, to obtain solutions that are within an arbitrarily small factor of being optimal in the disk graph model.

8. Conclusion

In this paper, we studied the problem of scheduling wireless requests in the physical interference model with multiple and variable data rates. We proposed a method of solving two versions of the problem by providing intermediate representations as disk graphs. As opposed to the majority of previous results on graph-based models, our approach allows the application of graphtheoretic algorithmic tools, while guaranteeing feasible solutions in the physical interference model, which is closer to reality than graph models.