Network formation games among relay stations in next generation wireless networks

Walid Saad, Zhu Han, Tamer Basar, Mérouane Debbah, Are Hjørungnes

Research output: Contribution to journalReview articlepeer-review


The introduction of relay station (RS) nodes is a key feature in next generation wireless networks such as 3GPP's long term evolution advanced (LTE-Advanced), or the forthcoming IEEE 802.16j WiMAX standard. This paper presents, using game theory, a novel approach for the formation of the tree architecture that connects the RSs and their serving base station in the uplink of the next generation wireless multi-hop systems. Unlike existing literature which mainly focused on performance analysis, we propose a distributed algorithm for studying the structure and dynamics of the network. We formulate a network formation game among the RSs whereby each RS aims to maximize a cross-layer utility function that takes into account the benefit from cooperative transmission, in terms of reduced bit error rate, and the costs in terms of the delay due to multi-hop transmission. For forming the tree structure, a distributed myopic algorithm is devised. Using the proposed algorithm, each RS can individually select the path that connects it to the BS through other RSs while optimizing its utility. We show the convergence of the algorithm into a Nash tree network, and we study how the RSs can adapt the network's topology to environmental changes such as mobility or the deployment of new mobile stations. Simulation results show that the proposed algorithm presents significant gains in terms of average utility per mobile station which is at least 17.1% better relatively to the case with no RSs and reaches up to 40.3% improvement compared to a nearest neighbor algorithm (for a network with 10 RSs). The results also show that the average number of hops does not exceed 3 even for a network with up to 25 RSs.

Original languageEnglish (US)
Article number5936797
Pages (from-to)2528-2542
Number of pages15
JournalIEEE Transactions on Communications
Issue number9
StatePublished - Sep 2011


  • 802.16j
  • LTE
  • Relay stations
  • game theory
  • network formation
  • next generation networks

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Network formation games among relay stations in next generation wireless networks'. Together they form a unique fingerprint.

Cite this