Game Theory for Multi-hop Broadcast in Wireless Networks

Multi-hop broadcast is an important application in wireless networks. It can be employed for file sharing, software update, notification distribution, video streaming, etc. In multi-hop broadcast, a node of a wireless network, as the source, shares ist message with other nodes in a multi-hop fashion. Due to the importance of power management in wireless network, in this dissertation, we study power minimization in multi-hop broadcast. In a multi-hop broadcast, the message ow from the source to the receivers can be modeled as a tree-graph, called the broadcast-tree (BT) and the problem of disseminating the message in the network with minimum-power is called the minimum-power broadcast-tree (MPBT) problem. The MPBT problem is NP-complete, meaning that a polynomial-time algorithm unlikely exists for it. Hence, many centralized and decentralized approximation algorithms are proposed in order to approximate the MPBT problem. Since managing the network traditionally from a centralized controller may not be always possible, decentralized approaches are more suitable to be employed in wireless networks.

The primary focus of this dissertation is on developing decentralized methods for tackling the MPBT problem. Seeing the MPBT problem from a decentralized optimization point of view, every individual node has to play its own role in forming the BT by establishing a communication link to another node. This can be suitably modeled by game theory, in which the players compete with each other in minimizing their own cost. In this dissertation, we first propose a game-theoretic model for the MPBT problem. In the proposed game, every node, in order to receive the message, chooses another node as its respective transmitting node. In this case, a receiving node an its respective transmitting node are called the child node (CN) and the parent node (PN), respectively. Such a decision by a CN imposes transmit power on its chosen PN. The key idea here is to assign a cost to every CN according to the power it imposes on its chosen PN so that the network power is minimized via cost minimization at the CNs. The total power required at a wireless transmitter consists of (i) the transmit power of the amplifier required for the transmission over a radio link and (ii) the circuitry power needed for passive communication hardware modules. The conventional algorithms for the MPBT problem mostly focus merely on the minimization of the power required for the radio link, but in our model, we take both powers into account and show that the circuitry power remarkably impacts the network power.

The game that we design is a non-cooperative cost sharing game. In such a game, via a so-called cost sharing scheme, the cost of using a PN is shared among the CNs that choose it. By employing a cost sharing game, the CNs are motivated to join together and form a multicast receiving group and this reduces the number of transmissions in the network. We study several cost sharing schemes and discuss the their properties in terms of the performance of the obtained BT and the convergence of the game to a Nash equilibrium (NE). It is shown that, with the marginal contribution (MC) cost sharing scheme, the cost minimization of the nodes is exactly aligned with the network power minimization. This means that cost reduction at a node results in the same reduction in the network power and hence, the global objective can be improved via local decision making. As a consequence, with MC, the optimum BT is always an NE of the game. Besides MC, we study equal-share (ES) and the Shapley value (SV) as two other widely-adopted budget-balanced cost sharing schemes. It is shown that (i) the MC performs the best for the decentralized MPBT construction, (ii) the equal-share (ES) scheme does not guarantee the convergence of the game to an NE for the MPBT problem and (iii) with budget-balanced cost sharing schemes, unlike for the MC, the local and global objectives are not aligned and hence, the optimum BT is not necessarily an NE.

Typically for the MPBT problem, a CN relies on one PN for receiving data, however, due to the broadcast nature of the wireless medium, the signals from multiple transmitters can be received at a CN. In order to exploit the signals transmitted by multiple transmitting nodes, maximal-ratio combining (MRC) is proposed to be employed at the receiving nodes. The proposed game-theoretic framework is further extended and a mixed integer-linear program (MILP) is proposed to find the global optimum solution. By the proposed algorithm a CN selects multiple PNs for itself and at the same time determines the transmit power of its chosen PNs. Since by such an approach a CN is able to exploit and accumulate the signals transmitted from multiple PNs, the required power for message dissemination in the network reduces.

It is known that video is the dominant application in the next generation of communication networks. Moreover, the success of multi-hop broadcast for video application depends highly on the collaboration of the end users. In this dissertation, the proposed game-theoretic framework is further optimized for video streaming in user-centric networks (UCNs). The considered video is assumed to be encoded by the scalable video coding (SVC) technique. An SVC video consists of several layers and in our work, it is assumed that every layer of the video is streamed by a separate BT. To receive a certain video quality, a node has to join the corresponding BTs. In order to provide an incentive for the PNs, we assume that the PNs are paid by their corresponding CNs via tokens. The payment depends on the energy consumed by the PNs. By collecting tokens in exchange for forwarding the video, a contributing node is able to receive a higher video quality. Further, in multi-hop broadcast, the contribution of the nodes who are located closer to the source is vital for the rest of the network. To address this issue, we propose a taxation mechanism that speciffically provides higher rewards for the nodes closer to the source. The utility function of the nodes in the proposed game-theoretic model captures (i) the importance of video quality for the user, (ii) the cost the user pays, (iii) the willingness of the user for contribution to the network and (iv) the reward a user receives if it forwards the video to others. A user, by maximizing her utility function, simultaneously determines how many BTs she should join to, her corresponding PN for each BT, and if she should forward the received video to others. It is shown that the proposed game-theoretic incentive mechanism significantly improves the video quality perceived by the users while preserving the energy-efficiency of the network.