Interference-Aware Broadcast Scheduling in Wireless Networks
| Autor: | Gruia Calinescu, Sutep Tongngam |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Schedule
Mathematical optimization Computational complexity theory Computer Networks and Communications Wireless network Computer science Approximation algorithm Upper and lower bounds Scheduling (computing) Hardware and Architecture Broadcast scheduling Heuristics Integer programming Software Distance |
| Zdroj: | MSN |
| DOI: | 10.1109/msn.2008.37 |
| Popis: | In this paper, we study the interference-aware broadcast scheduling problem, where all nodes in the Euclidean plane have a transmission range and an interference range equal to r and alphar for alphages1, respectively. Minimizing latency is known to be NP-hard even when alpha=1. The network radius D, the maximum graph distance from the source to any node, is also known to be a lower bound. We formulate the problem as integer programs (IP) and optimally solve moderate-size instances. We also propose six variations of heuristics, which require no pre-processesing of inputs, based on the number of receivers gained by each additional simultaneous broadcasting node. The experimental results show that the best heuristics give the solutions only 13-20% exceeding the optimum solutions. Further, an O(alphaD) schedule is proven to exist yielding an O(alpha) approximation algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|