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

Abstract

Scheduling wireless links for simultaneous activation in such a way that all transmissions are successfully decoded at the receivers and moreover network capacity is maximized is a computationally hard problem. Usually it is tackled by heuristics whose output is a sequence of time slots in which every link appears in exactly one time slot. Such approaches can be interpreted as the coloring of a graph’s vertices so that every vertex gets exactly one color. Here we introduce a new approach that can be viewed as assigning multiple colors to each vertex, so that, in the resulting schedule, every link may appear more than once (though the same number of times for all links). We report on extensive computational experiments, under the physical interference model, revealing substantial gains for a variety of randomly generated networks.

6. Concluding remarks

Although it may at first seem striking that ApproxLogN has performed so poorly across most of our experiments, it should be kept in mind that this heuristic, in all likelihood, was never meant as a strong contender for single-color link scheduling. In fact, and as noted in Section 2, ApproxLogN approaches the checking of feasibility rather indirectly, verifying sufficient conditions for feasibility to hold instead of the property itself. This is bound to prevent ApproxLogN from scheduling links for activation when they could be scheduled. What must be remembered, then, is that the use of such indirect conditions has led to important performance and capacity bounds. ApproxLogN, therefore, remains an important contribution despite its performance in more practical settings. What really is striking in our results, though, is the appearance of greater-than-1 gains practically across the board, particularly for MaxCRank or GreedyPhysical as the base, single-color heuristic. Link schedules, once determined, are meant to be used repetitively, so every link is already meant to be scheduled for activation over and over again, indefinitely. Conceptually, what our multicoloringbased wrapping of single-color heuristics tries to do is to intertwine some number of repetitions of a single-color schedule, taking up fewer time slots than the straightforward juxtaposition of the same number of repetitions of that schedule. By doing so, more link activations can be packed together in earlier time slots. As a consequence, the basic schedule to be used for indefinite repetition is now one that leads to higher network capacity and possibly higher throughput. As we mentioned earlier, multicoloring-based link scheduling of the sort we have demonstrated has roots in the multicoloring of a graph’s vertices (as well as edges, in many cases). As such, a rich body of material, relating both to computational-complexity difficulties and to workarounds in important cases, is available. Further developments should draw on such knowledge, aiming to obtain more principled, and perhaps even better performing, heuristics. Likewise, we believe that improved upper bounds on network capacity should also be obtainable. A promising way to this end seems to be to work directly on a graph whose edges (not vertices) stand for links. Doing this will bring in a considerable number of results on the multicoloring of edges, as described for example in Section 28.5 of [39], and constitutes the subject of current research. We end with a note on the eventual practical use of our approach to perform actual link scheduling on real networks. Like so many of the approaches that precede ours, any single-color heuristic conforming to the template given by Steps S1–S4 of Section 2 is essentially a centralized procedure, that is, one not naturally suited to direct deployment for operation on a real network. Instead, such heuristics aim to demonstrate strategies to better exploit the interference patterns produced by the links in order to maximize capacity. This is therefore true of both GreedyPhysical and ApproxLogN, and of MaxCRank as well, holding moreover for their multicoloring-based generalizations through Steps M1–M6 of Section 3. Turning such heuristics into distributed algorithms for the actual scheduling of links requires algorithm design that differs substantially from what we have undertaken in this work. As such, it constitutes the subject of further research.