Distributed Scheduling of Network Connectivity Using Mobile Access Point Robots

Abstract

In this paper, we consider scenarios where mobility can be exploited to enable reliable communications in wireless networks with scarce resources that are unable to concurrently service their nodes. Specifically, we consider cases where a team of robots operate as mobile access points (APs) that provide service, namely sufficient end-to-end communication routes, to a multihop network of static source nodes which generate data. We introduce the connectivity scheduling problem, a novel framework that combines motion planning of the APs with service scheduling of the source nodes and network routing control so that integrity of communications is guaranteed over time. We formulate the connectivity scheduling problem as a multistage mixed integer programming (MIP) problem, where path planning, service scheduling, and routing decisions are all jointly optimized over a discrete-time horizon. Since MIP problems can grow intractable quickly, we further consider a continuous convex reformulation of the problem and employ sparse optimization techniques, specifically the reweighted ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> regularization scheme, to recover the desired integrality structure of the solution. We propose a decentralized method to solve the above relaxation that is based on the recently developed accelerated distributed augmented Lagrangians (ADAL) algorithm. Specifically, we modify ADAL by incorporating in the algorithm the reweighted ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> scheme, which enables us to recover the desired sparsity structure of the original MIP at the final solution. Numerical results are presented that validate the effectiveness of the proposed framework.