A fast greedy algorithm for routing concurrent video flows

Real-time multimedia communication is an important service 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 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.