Constrained shortest paths in wireless networks

We address several QoS routing problems in wireless ad hoc networks. Due to mobility or limited battery power, a link between two nodes can last for a certain period, which is represented by a life parameter. On the other hand, each link has cost parameters which can represent the delay of this link, the transmission power needed to support this link and so on. The life of a path is the shortest life of all links in this path; the cost of a path is the sum of the costs of all links. We first consider the problem of finding a path between a given pair of nodes with the maximum life while the cost of the path does not exceed a pre-specified bound. This problem can be solved in O((n log n + m) log n) time. Here n is the number of nodes and m is the number of links. A distributed version of the algorithm that is suitable for wireless ad hoc networks is also presented. In addition, we study the problem of finding a path between a given pair of nodes with the maximum battery energy level while the cost of the path does not exceed a pre-specified bound. We also developed both centralized and distributed polynomial-time algorithms for this problem. Specifically, when the cost represents the transmission power needed to support the link, we give a distributed algorithm with time complexity O(n log n) using O(n/sup 2/ log n) total messages.