Game-Theoretic Analysis of Topology Control
Ad hoc networks are emerging as a cost-effective, yet, powerful tool for communication.
These systems, where networks can emerge and converge on-the-fly, are guided by the
forward-looking goals of providing ubiquitous connectivity and constant access to information.
Due to power and bandwidth constraints, the vulnerability of the wireless medium, and
the multi-hop nature of ad hoc networks, these networks are becoming increasingly complex
dynamic systems. Besides, modern radios are empowered to be reconfigurable, which harbors
the temptation to exploit the system. To understand the implications of these issues, some
of which pose significant challenges to efficient network design, we study topology control
using game theory.
We develop a game-theoretic framework of topology control that broadly captures the radio
parameters, one or more of which can be tuned under the purview of topology control. In
this dissertation, we consider two parameters, viz. transmit power and channel, and study
the impact of controlling these on the emergent topologies.
We first examine the impact of node selfishness on the network connectivity and energy
efficiency under two levels of selfishness: (a) nodes cooperate and forward packets for one
another, but selfishly minimize transmit power levels and; (b) nodes selectively forward
packets and selfishly control transmit powers. In the former case, we characterize all the
Nash Equilibria of the game and evaluate the energy efficiency of the induced topologies.
We develop a better-response-based dynamic that guarantees convergence to the minimal
maximum power topology. We extend our analysis to dynamic networks where nodes have
limited knowledge about network connectivity, and examine the tradeoff between network
performance and the cost of obtaining knowledge. Due to the high cost of maintaining
knowledge in networks that are dynamic, mobility actually helps in information-constrained
networks. In the latter case, nodes selfishly adapt their transmit powers to minimize their
energy consumption, taking into account partial packet forwarding in the network. This
work quantifies the energy efficiency gains obtained by cooperation and corroborates the
need for incentivizing nodes to forward packets in decentralized, energy-limited networks.
We then examine the impact of selfish behavior on spectral efficiency and interference minimization
in multi-channel systems. We develop a distributed channel assignment algorithm
to minimize the spectral footprint of a network while establishing an interference-free connected
network. In spite of selfish channel selections, the network spectrum utilization is
shown to be within 12% of the minimum on average. We then extend the analysis to dynamic
networks where nodes have incomplete network state knowledge, and quantify the price of
ignorance. Under the limitations on the number of available channels and radio interfaces, we
analyze the channel assignment game with respect to interference minimization and network
connectivity goals. By quantifying the interference in multi-channel networks, we illuminate
the interference reduction that can be achieved by utilizing orthogonal channels and by distributing
interference over multiple channels. In spite of the non-cooperative behavior of
nodes, we observe that the selfish channel selection algorithm achieves load balancing.
Distributing the network control to autonomous agents leaves open the possibility that nodes
can act selfishly and the overall system is compromised. We advance the need for considering
selfish behavior from the outset, during protocol design. To overcome the effects of
selfishness, we show that the performance of a non-cooperative network can be enhanced by
appropriately incentivizing selfish nodes.
Advisor:Jeffrey H. Reed; Luiz A. DaSilva; Sandeep K Shukla; Robert P. Gilles; Allen B. MacKenzie
School:Virginia Polytechnic Institute and State University
School Location:USA - Virginia
Source Type:Master's Thesis
Keywords:electrical and computer engineering
Date of Publication:09/11/2008