Adapting Wardrop equilibrium to facilitate optimal routing in wireless ad hoc networks

摘要

The majority of routing protocols for wireless ad hoc networks are based on selfish strategies, aiming to maximize the performance of a flow between a source-destination (S-D) pair. However, due to the competing nature of individual flows, selfish routing does not produce an optimal solution that minimizes the cost, e.g. delay, experienced by all the traffic in a network. It has been shown that the optimal routing in wired networks can be achieved at the Wardrop equilibrium of marginal link cost. However, such equilibrium can not produce optimum in wireless environments due to the broadcast nature of wireless transmissions. In this paper, we extend the optimal Wardrop equilibrium in ad hoc networks by deriving a marginal cost for wireless medium and proving that the Wardrop equilibrium under such cost produces optimal routing solution. Based on the proposed cost model, we design a Newton-based routing algorithm that converges to the optimal Wardrop equilibrium. This is followed by a statistical evaluation of the optimal equilibrium.