A fast greedy algorithm for routing concurrent video flows

Abstract — Real-time multimedia communication is an important ser-vice that should be supported in wireless ad hoc networks. In this paper, we consider the problem of how to optimally support multiple concurrent video communication sessions in a wireless ad hoc network. Our problem formulation follows an application-centric cross-layer approach with the objective of minimizing the average distortion of all video sessions via finding optimal paths for each session. Since this network-wide optimization problem is shown to be NP-complete, we pursue to develop competitive heuristic algorithms to address this problem. Specifically, we describe a greedy algorithm based on the key characteristics of the end-to-end video distortion model, and use numerical results to demonstrate its performance as compared to the global optima. This greedy heuristic algorithm can be used to quickly compute a set of good paths for the video sessions. It can also be used to speed up the Genetic Algorithm-based algorithm proposed in our previous work. I