Price/Utility-based Optimized Resource Allocation in Wireless Ad hoc Networks

Abstract — This paper proposes a scheme for bandwidth allocation in wireless ad hoc networks. The Quality of Service (QoS) levels for each end-to-end flow are expressed using resource-utility functions, and our algorithms aim to maximise the aggregated utility of the flows. The scheme differentiates between applications with flexible resource requirements and rigid (real-time) requirements. As an abstract notion of resource, we use maximal cliques of mutual interfering links. Using concave piece-wise linear utility functions we present a linear programming (LP) formulation of the problem that can serve as an optimal though unrealistic solution. Then we replace this centralised approach with a distributed low complexity solution. A key concept, borrowed from the dual of the optimal allocation problem, is the shadow price of a resource. The contributions of the paper are twofold: (1) a distributed algorithm that allocates the bandwidth based on bids that are calculated using the shadow price of the resources and the flow’s utility function, (2) a utility-aware on-demand ”shortest ” path routing algorithm in which the shadow prices are used a natural distance metric. We compare the performance of the distributed allocation scheme with the centralised, optimal linear programming solution. We also compare with a non-utility-based QoS allocation scheme, that uses hop-based shortest path routing followed by highest possible bandwidth accommodation of the flow. I