Online Learning for Wireless Distributed Computing
  There has been a growing interest for Wireless Distributed Computing (WDC),
which leverages collaborative computing over multiple wireless devices. WDC
enables complex applications that a single device cannot support individually.
However, the problem of assigning tasks over multiple devices becomes
challenging in the dynamic environments encountered in real-world settings,
considering that the resource availability and channel conditions change over
time in unpredictable ways due to mobility and other factors. In this paper, we
formulate a task assignment problem as an online learning problem using an
adversarial multi-armed bandit framework. We propose MABSTA, a novel online
learning algorithm that learns the performance of unknown devices and channel
qualities continually through exploratory probing and makes task assignment
decisions by exploiting the gained knowledge. For maximal adaptability, MABSTA
is designed to make no stochastic assumption about the environment. We analyze
it mathematically and provide a worst-case performance guarantee for any
dynamic environment. We also compare it with the optimal offline policy as well
as other baselines via emulations on trace-data obtained from a wireless IoT
testbed, and show that it offers competitive and robust performance in all
cases. To the best of our knowledge, MABSTA is the first online algorithm in
this domain of task assignment problems and provides provable performance
guarantee.
