Kinetically Stable Task Assignment for Networks of Microservers

This paper studies task migration in a network of resource constrained servers (called microservers). A task is an abstraction of a moving physical object or phenomenon that we are interested in monitoring, such as a vehicle, and the microserver is a computational device that can receive sensor data pertaining to the object of interest. Due to motion, the microservers that can observe a particular task change over time and there is overhead involved in migrating tasks among microservers. Furthermore, communication, processing, or memory constraints, allow a microserver to only serve a limited number of tasks at the same time. Our overall goal is to allocate tasks to microservers so as to minimize the number of migrations, while guaranteeing that as many tasks as possible are monitored at all times. When the task trajectories are known in advance, we show that this problem is NP-Complete (even over just two time steps), has an integrality gap of at least 2, and can be solved optimally in polynomial time if we allow tasks to be assigned fractionally. When only probabilistic information about future movement of the tasks is known, we propose two algorithms: a multi-commodity flow based algorithm and a maximum matching algorithm. We use simulations to compare the performance of these algorithms against the optimum task allocation strategy.