On the Complexity of Power-Aware Multiple Routing for Mobile Ad Hoc Networks

Abstract

Most of the existing routing protocols for mobile ad hoc networks are designed primarily to carry best-effort traffic and only concerned with shortest-path routing. Little attention is paid to the issues related to the quality-of-service (QoS) requirement of a route. In this paper, we will consider the problem of searching for multiple paths between multiple pairs of sources and destinations satisfying the power requirement in a mobile ad hoc network. We will show that the problem is NP-complete.