Exact models for the κ-connected minimum energy problem

Abstract

We consider the minimum energy problem for a mobile ad hoc network, where any node in the network may communicate with any other via intermediate nodes. To provide quality of service, the network must be connected, even if one or more nodes drop out. This motivates the notion of κ-connectivity. The minimum energy problem aims to optimize the total energy that all nodes spend for transmission. Previous work in the literature includes exact mixed-integer programming formulations for a 1-connected network. We extend these models for when the network is κ-connected, and compare the models for various network sizes. As expected, the combinatorial nature of the problem limits the size of the netwo..