TY - GEN
T1 - Hierarchical network formation games in the uplink of multi-hop wireless networks
AU - Saad, Walid
AU - Zhu, Quanyan
AU - Başar, Tamer
AU - Han, Zhu
AU - Hjørungnes, Are
PY - 2009
Y1 - 2009
N2 - In this paper, we propose a game theoretic approach to tackle the problem of the distributed formation of the hierarchical network architecture that connects the nodes in the uplink of a wireless multi-hop network. Unlike existing literature which focused on the performance assessment of hierarchical multi-hop networks given an existing topology, this paper investigates the problem of the formation of this topology among a number of nodes that seek to send data in the uplink to a central base station through multihop. We model the problem as a hierarchical network formation game and we divide the network into different hierarchy levels, whereby the nodes belonging to the same level engage in a non-cooperative Nash game for selecting their next hop. As a solution to the game, we propose a novel equilibrium concept, the hierarchical Nash equilibrium, for a sequence of multi-stage Nash games, which can be found by backward induction analytically. For finding this equilibrium, we propose a distributed myopic dynamics algorithm, based on fictitious play, in which each node computes the mixed strategies that maximize its utility which represents the probability of successful transmission over the multi-hop communication path in the presence of interference. Simulation results show that the proposed algorithm presents significant gains in terms of average achieved expected utility per user up to 125.6% relative to a nearest neighbor algorithm.
AB - In this paper, we propose a game theoretic approach to tackle the problem of the distributed formation of the hierarchical network architecture that connects the nodes in the uplink of a wireless multi-hop network. Unlike existing literature which focused on the performance assessment of hierarchical multi-hop networks given an existing topology, this paper investigates the problem of the formation of this topology among a number of nodes that seek to send data in the uplink to a central base station through multihop. We model the problem as a hierarchical network formation game and we divide the network into different hierarchy levels, whereby the nodes belonging to the same level engage in a non-cooperative Nash game for selecting their next hop. As a solution to the game, we propose a novel equilibrium concept, the hierarchical Nash equilibrium, for a sequence of multi-stage Nash games, which can be found by backward induction analytically. For finding this equilibrium, we propose a distributed myopic dynamics algorithm, based on fictitious play, in which each node computes the mixed strategies that maximize its utility which represents the probability of successful transmission over the multi-hop communication path in the presence of interference. Simulation results show that the proposed algorithm presents significant gains in terms of average achieved expected utility per user up to 125.6% relative to a nearest neighbor algorithm.
UR - http://www.scopus.com/inward/record.url?scp=77951605931&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951605931&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2009.5426293
DO - 10.1109/GLOCOM.2009.5426293
M3 - Conference contribution
AN - SCOPUS:77951605931
SN - 9781424441488
T3 - GLOBECOM - IEEE Global Telecommunications Conference
BT - GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference
T2 - 2009 IEEE Global Telecommunications Conference, GLOBECOM 2009
Y2 - 30 November 2009 through 4 December 2009
ER -