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 条
[41]   Topology Control for Increasing Connectivity in Cooperative Wireless Ad Hoc Networks [J].
Yu, Jieun ;
Roh, Heejin ;
Cao, Jun ;
Pack, Sangheon ;
Lee, Wonjun ;
Du, Ding-Zhu ;
Hong, Sangjin .
IEICE TRANSACTIONS ON COMMUNICATIONS, 2010, E93B (04) :1029-1032
[42]   Mobility-sensitive topology control in mobile ad hoc networks [J].
Wu, J ;
Dai, F .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2006, 17 (06) :522-535
[43]   Energy-Efficient Topology Control in Cooperative Ad Hoc Networks [J].
Zhu, Ying ;
Huang, Minsu ;
Chen, Siyuan ;
Wang, Yu .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2012, 23 (08) :1480-1491
[44]   Cooperative topology control for low interference in wireless ad hoc networks [J].
Wang, Xinglong ;
Huang, Liusheng ;
Xu, Hongli .
INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING, 2017, 24 (04) :213-224
[45]   Receiver Cooperation in Topology Control for Wireless Ad-Hoc Networks [J].
Moon, Kiryang ;
Yoo, Do-Sik ;
Lee, Wonjun ;
Oh, Seong-Jun .
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, 2015, 14 (04) :1858-1870
[46]   Topology control in ad hoc wireless networks using cooperative communication [J].
Cardei, M ;
Wu, J ;
Yang, SH .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2006, 5 (06) :711-724
[47]   Localized topology control for unicast and broadcast in wireless ad hoc networks [J].
Song, WZ ;
Li, XY ;
Frieder, O ;
Wang, WZ .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2006, 17 (04) :321-334
[48]   Using β-skeletons for localized topology control in wireless ad hoc networks [J].
Bhardwaj, M ;
Misra, S ;
Xue, GL .
Conference Proceedings of the 2005 IEEE International Performance, Computing and Communications Conference, 2005, :637-638
[49]   Mobility-Based Topology Control for Wireless Ad Hoc Networks [J].
Seol, Jae-Young ;
Kim, Seong-Lyun .
IEICE TRANSACTIONS ON COMMUNICATIONS, 2010, E93B (06) :1443-1450
[50]   Topology Control in Wireless Mobile Ad Hoc Networks with Directional Antennas [J].
Zhang, Wang ;
Peng, Laixian ;
Xu, Renhui ;
Zhang, Lei .
2016 2ND IEEE INTERNATIONAL CONFERENCE ON COMPUTER AND COMMUNICATIONS (ICCC), 2016, :1701-1705