Optimization of Wireless Multi-Source Multicast Ad-Hoc Networks Using Asymmetric Matrix Games

In this paper, we use matrix games framework for joint optimization of routing and network coding under conflict free scheduling for multi-source wireless ad-hoc networks. The impact of multicast diversity on scheduling is controlled by using topology compression concept quantified through compressed multicast topology matrix. To define topology matrix, first a set of all possible paths, including network coded paths, is identified and compressed. Depending on the nature of data selected path can be unicast or multicast. Then by switching between these paths with appropriate rates (frequencies), achievable scaled throughput is maximized. A link conflict free environment is designed by appropriate conflict free network partitioning using network graph coloring algorithm. For each possible coloring scheme and considering priority assigned to each source, link scheduling partitions topology matrix into multiple sub-matrices, one for each partial topologies. Each sub-matrix is used as a payoff matrix for an asymmetrical matrix game where against any single move of the second player, first player has multiple (K) moves, corresponding to different partial topologies or their equivalent colors. The strategy sets for the players are links and paths respectively. Such a game will be formally referred to as Asymmetrical Matrix Game with notation AMG(2,K,1) and the value of this game is inverse of the scaled throughput. In this notation 2 indicates two dimensional games. At the equilibrium, mixed strategy vector of the first player indicates optimum percentage of time or optimum number of time slots dedicated to the selected partial topologies for a given partitioning of the network graph while, mixed strategy vectors of the second player is proportional to optimum usage rates of the paths. Numerical results are presented for a simple butterfly network including 6 nodes and 2 sources. One source transmits multicast and second one unicast data with different priority.