Relay Placement for Maximum Flow Rate via Learning and Optimization over Riemannian Manifolds

Networks topology can be represented over Riemannian manifolds (i.e., curved surfaces), given the symmetric positive definite (SPD) property of their spectral graphs. Moreover, maximizing flow rate of a baseline network topology through relay placement can be equivalent to finding the relay location that maximizes the geodesic distance (i.e., Riemannian metric) between the representations of a relay-assisted network topology and the baseline one over Riemannian manifolds. Therefore in this paper, we propose two complementary approaches to find relay locations that maximize Riemannian metrics, such as Log-Euclidean metric (LEM), and hence maximize the network flow rate. First, we propose a Riemannian multi-armed bandit (RMAB) reinforcement learning model to track the relay positions, which increase the LEM towards the baseline network. Particularly, selecting a possible relay location is considered as an action, whereas the LEM represents the reward of the RMAB model. Second, we propose a Riemannian Particle Swarm Optimization (RPSO) algorithm that iteratively attempts to find the representation of relay-assisted network topology with maximum LEM towards that of the baseline network over the Riemannian manifold. Simulation results show that both the RMAB and RPSO approaches converge to near-optimum solutions, which in the case of single relay placement achieve 94.3% and 90.6%, respectively, of the maximum possible network flow rate.