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 article

Abstract

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
Volume59
Issue number9
DOIs
StatePublished - Sep 1 2011

Fingerprint

Wireless networks
Parallel algorithms
Long Term Evolution (LTE)
Game theory
Base stations
Bit error rate
Topology
Costs

Keywords

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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Network formation games among relay stations in next generation wireless networks. / Saad, Walid; Han, Zhu; Basar, Tamer; Debbah, Mérouane; Hjørungnes, Are.

In: IEEE Transactions on Communications, Vol. 59, No. 9, 5936797, 01.09.2011, p. 2528-2542.

Research output: Contribution to journalReview article

Saad, Walid ; Han, Zhu ; Basar, Tamer ; Debbah, Mérouane ; Hjørungnes, Are. / Network formation games among relay stations in next generation wireless networks. In: IEEE Transactions on Communications. 2011 ; Vol. 59, No. 9. pp. 2528-2542.
@article{e1c8460f6f804fdb90e008859775c0ea,
title = "Network formation games among relay stations in next generation wireless networks",
abstract = "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.",
keywords = "802.16j, LTE, Relay stations, game theory, network formation, next generation networks",
author = "Walid Saad and Zhu Han and Tamer Basar and M{\'e}rouane Debbah and Are Hj{\o}rungnes",
year = "2011",
month = "9",
day = "1",
doi = "10.1109/TCOMM.2011.062311.100046",
language = "English (US)",
volume = "59",
pages = "2528--2542",
journal = "IEEE Transactions on Communications",
issn = "0090-6778",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

TY - JOUR

T1 - Network formation games among relay stations in next generation wireless networks

AU - Saad, Walid

AU - Han, Zhu

AU - Basar, Tamer

AU - Debbah, Mérouane

AU - Hjørungnes, Are

PY - 2011/9/1

Y1 - 2011/9/1

N2 - 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.

AB - 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.

KW - 802.16j

KW - LTE

KW - Relay stations

KW - game theory

KW - network formation

KW - next generation networks

UR - http://www.scopus.com/inward/record.url?scp=80052925404&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052925404&partnerID=8YFLogxK

U2 - 10.1109/TCOMM.2011.062311.100046

DO - 10.1109/TCOMM.2011.062311.100046

M3 - Review article

AN - SCOPUS:80052925404

VL - 59

SP - 2528

EP - 2542

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

SN - 0090-6778

IS - 9

M1 - 5936797

ER -