Effect of Selfish Node Behavior on Efficient Topology Design

Ramakant S. Komali, Allen B. MacKenzie, Robert P. Gilles

Research output: Contribution to journalArticlepeer-review

92 Citations (Scopus)


The problem of topology control is to assign per-node transmission power such that the resulting topology is energy efficient and satisfies certain global properties such as connectivity. The conventional approach to achieve these objectives is based on the fundamental assumption that nodes are socially responsible. We examine the following question: if nodes behave in a selfish manner, how does it impact the overall connectivity and energy consumption in the resulting topologies? We pose the above problem as a noncooperative game and use game-theoretic analysis to address it. We study Nash equilibrium properties of the topology control game and evaluate the efficiency of the induced topology when nodes employ a greedy best response algorithm. We show that even when the nodes have complete information about the network, the steady-state topologies are suboptimal. We propose a modified algorithm based on a better response dynamic and show that this algorithm is guaranteed to converge to energy-efficient and connected topologies. Moreover, the node transmit power levels are more evenly distributed, and the network performance is comparable to that obtained from centralized algorithms.

Original languageEnglish
Pages (from-to)1057-1070
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number9
Publication statusPublished - Sep 2008

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)


Dive into the research topics of 'Effect of Selfish Node Behavior on Efficient Topology Design'. Together they form a unique fingerprint.

Cite this