Lifetime Maximization in Wireless Ad Hoc Networks with Network Coding and Matrix Game

In this paper, we present a matrix game-theoretic cross-layer optimization formulation to maximize the network lifetime in wireless ad hoc networks with network coding. To this end, we introduce a cross-layer formulation of general NUM (network utility maximization) that accommodates routing, scheduling, and stream control from different layers in the coded networks. Specifically, for the scheduling problem and then the objective function involved, we develop a matrix game with the strategy sets of the players corresponding to hyperlinks and transmission modes, and design the payoffs specific to the lifetime. In particular, with the inherit merit that matrix game can be solved with linear programming, our cross-layer programming formulation can benefit from both game-based and NUM-based approaches at the same time by cooperating the programming model for the matrix game with that for the other layers in a consistent framework. Finally, our numerical example demonstrates its performance results on a well-known wireless butterfly network to verify the cross-layer optimization scheme.

Authors:

• Jain-Shing Liu

Keywords:

• Cross-layer design
• Lifetime maximization
• Matrix game
• Network coding

References:

<p>[1] Jae-Hwan Chang and L. Tassiulas. Maximum lifetime routing in wireless
sensor networks. IEEE/ACM Transactions on Networking, 12(4):609 &ndash;
619, aug. 2004.
[2] R.L. Cruz and A.V. Santhanam. Optimal routing, link scheduling and
power control in multihop wireless networks. In Proceedings of IEEE
INFOCOM 2003, volume 1, pages 702 &ndash; 711 vol.1, march, 2003.
[3] R. Madan, S. Cui, S. Lal, and A. Goldsmith. Cross-layer design for
lifetime maximization in interference-limited wireless sensor networks.
IEEE Transactions on Wireless Communications, 5(11):3142 &ndash;3152,
november 2006.
[4] R. Banner and A. Orda. Bottleneck routing games in communication
networks. IEEE Journal on Selected Areas in Communications,
25(6):1173&ndash;1179, Aug. 2007.
[5] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information
flow. IEEE Transactions on Information Theory, 46:1204&ndash;1216, 2000.
[6] J. Price and T. Javidi. Network coding games with unicast flows. IEEE
Journal on Selected Areas in Communications, 26(7):1302&ndash;1316, Sep.
2008.
[7] X. B. Liang. Matrix games in the multicast networks: maximum
information flows with network switching. IEEE Transactions on
Infromation Theory, 52(6):2433&ndash;2466, June 2006.
[8] E. Karami and S. Glisic. Joint optimization of scheduling and routing in
multicast wireless ad hoc networks using soft graph coloring and
nonlinear cubic games. IEEE Transactions on Vehicular Technology,
60(7):3350&ndash;3359, Sept. 2011.
[9] J. von Neumann and O. Morgenstern. Theory of games and economic
behavior. Princeton University Press, 1944.
[10] J. C. C. McKinsey. Introduction to the theory of game. RAND
Corporation, 1952.
[11] T. Ho and D. S. Lun. Network coding: an introduction. Cambridge
University Press, 2008.</p>