A Novel Method for Scheduling of Wireless Ad Hoc Networks in Polynomial Time
| Autor: | Noyan Evirgen, Hakan Gokcesu, Kaan Gokcesu, Alper Kose, Muriel Medard |
|---|---|
| Přispěvatelé: | Gökçesu, Hakan, Gökcesu, Hakan |
| Rok vydání: | 2021 |
| Předmět: |
Claw-free graph
Theoretical computer science Optimization problem Maximum weighted independent set Job shop scheduling Computer science Wireless network Wireless ad hoc network Applied Mathematics 020206 networking & telecommunications 02 engineering and technology Graph Computer Science Applications Scheduling (computing) 0202 electrical engineering electronic engineering information engineering Wireless ad hoc networks Maximal independent set Conflict graph Electrical and Electronic Engineering Scheduling in polynomial time Time complexity |
| Zdroj: | IEEE Transactions on Wireless Communications |
| ISSN: | 1558-2248 1536-1276 |
| DOI: | 10.1109/twc.2020.3025448 |
| Popis: | In this article, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when scheduling problems can be represented by claw-free conflict graphs where we consider a wireless broadcast medium. It is possible to formulate a scheduling problem of broadcast transmissions as finding the maximum weighted independent set (MWIS) in the conflict graph of the network. Finding the MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. In a claw-free conflict graph, MWIS may be found in polynomial time leading to a throughput-optimal scheduling. We show that the conflict graphs of certain wireless ad hoc networks are claw-free. In order to obtain claw-free conflict graphs in general networks, we suggest introducing additional conflicts (edges) with the aim of keeping the decrease in MWIS size minimal. To this end, we introduce an iterative optimization problem to decide where to introduce edges and investigate its efficient implementation. We conclude that the claw breaking method by adding extra edges can perform very close to optimal scenario and better than the polynomial time maximal independent set scheduling benchmark under the necessary assumptions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|