Equilibria in topology control games for ad hoc networks

被引:56
作者
Eidenbenz, Stephan
Kumar, V. S. Anil
Zust, Sibylle
机构
[1] Los Alamos Natl Lab, Los Alamos, NM 87544 USA
[2] Virginia Tech, Virginia Bioinformat Inst, Blacksburg, VA USA
[3] Virginia Tech, Dept Comp Sci, Blacksburg, VA USA
关键词
ad hoc networks; wireline networks; directional antenna networks; game theory; Nash equilibrium; topology control;
D O I
10.1007/s11036-005-4468-y
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that-among the games we define-these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the STRONG CONNECTIVITY GAME). For a variation called CONNECTIVITY GAME, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the REACHABILITY GAME, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the STRONG CONNECTIVITY GAME and the CONNECTIVITY GAME to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks.
引用
收藏
页码:143 / 159
页数:17
相关论文
共 50 条
  • [31] CLTC: A cluster-based topology control framework for ad hoc networks
    Shen, CC
    Srisathapornphat, C
    Liu, R
    Huang, ZC
    Jaikaeo, C
    Lloyd, EL
    [J]. IEEE TRANSACTIONS ON MOBILE COMPUTING, 2004, 3 (01) : 18 - 32
  • [32] An SPT-based topology control algorithm for wireless ad hoc networks
    Wang, Szu-Chi
    Wei, David S. L.
    Kuo, Sy-Yen
    [J]. COMPUTER COMMUNICATIONS, 2006, 29 (16) : 3092 - 3103
  • [33] Topology control of ad hoc wireless networks for energy efficiency
    Cheng, MX
    Cardei, M
    Sun, JH
    Cheng, XC
    Wang, LS
    Xu, YF
    Du, DZ
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (12) : 1629 - 1635
  • [34] Nash equilibria of packet forwarding strategies in wireless ad hoc networks
    Félegyházi, M
    Hubaux, JP
    Buttyán, L
    [J]. IEEE TRANSACTIONS ON MOBILE COMPUTING, 2006, 5 (05) : 463 - 476
  • [35] Optimal Solutions for Fault-Tolerant Topology Control in Wireless Ad Hoc Networks
    Moraes, Renato E. N.
    Ribeiro, Celso C.
    Duhamel, Christophe
    [J]. IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, 2009, 8 (12) : 5970 - 5981
  • [36] Energy-Aware Topology Control And Qos Routing In Ad-Hoc Networks
    Yakine, Fadoua
    Idrissi, Abdellah
    [J]. 10TH INTERNATIONAL CONFERENCE ON FUTURE NETWORKS AND COMMUNICATIONS (FNC 2015) / THE 12TH INTERNATIONAL CONFERENCE ON MOBILE SYSTEMS AND PERVASIVE COMPUTING (MOBISPC 2015) AFFILIATED WORKSHOPS, 2015, 56 : 309 - 316
  • [37] A Novel Adaptive Topology Control in Mobile Ad Hoc Networks based on Connectivity Index
    Kunavut, Kunagorn
    [J]. 2015 INTERNATIONAL CONFERENCE ON INTELLIGENT INFORMATICS AND BIOMEDICAL SCIENCES (ICIIBMS), 2015, : 87 - 91
  • [38] A New Distributed Topology Control Algorithm Based on Optimization of Delay in Ad Hoc Networks
    Hu, Yachao
    Liu, Daliang
    Wu, Yingfeng
    [J]. 2016 FIRST IEEE INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATION AND THE INTERNET (ICCCI 2016), 2016, : 148 - 152
  • [39] Energy-efficient topology control in wireless ad hoc networks with selfish nodes
    Zarifzadeh, Sajjad
    Yazdani, Nasser
    Nayyeri, Amir
    [J]. COMPUTER NETWORKS, 2012, 56 (02) : 902 - 914
  • [40] Cooperative Bridges: Topology Control in Cooperative Wireless Ad Hoc Networks
    Yu, Jieun
    Roh, Heejun
    Lee, Wonjun
    Pack, Sangheon
    Du, Ding-Zhu
    [J]. 2010 PROCEEDINGS IEEE INFOCOM, 2010,