Name
Abstract | ||
|---|---|---|
Finding an optimal/near-optimal scheduling algorithm to minimize the age of information (AoI) in a multi-source G/G/1 system is well-known to be a hard problem. In this paper, we consider this problem for the non-preemptive setting, where an algorithm is free to choose which update to transmit, but an update under transmission is not allowed to be preempted. For this problem, we propose a novel randomized scheduling algorithm and show that its competitive ratio is at most 3 plus the maximum of the ratio of the variance and the mean of the inter-arrival time distribution of sources. Notably, the competitive ratio is independent of the number of sources, or their service time distributions. For several common inter-arrival time distributions such as exponential, uniform and Rayleigh, the competitive ratio is at most 4. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.23919/WiOpt56218.2022.9930540 | 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt) |
Keywords | DocType | ISBN |
age of information,scheduling,competitive ratio | Conference | 978-1-6654-6076-7 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kumar Saurav | 1 | 0 | 0.34 |
| Rahul Vaze | 2 | 463 | 45.64 |