Network Formation Games Among Relay Stations in Next Generation Wireless Networks

Walid Saad, Zhu Han, Tamer Basar, Mérouane Debbah, Are HjørungnesIEEE Trans. Communications 2011 · DOI · OpenReview

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.

Introduction

In the evolution of 4G and early 5G wireless standards, such as LTE-Advanced and WiMAX 802.16j, Relay Stations (RSs) have become essential for extending coverage and enhancing signal quality. However, organizing these relays into an efficient architecture that connects to the Base Station (BS) presents a significant challenge. Traditional research has often focused on performance metrics in static configurations, neglecting the dynamic process of network formation. Centralized control mechanisms, while theoretically optimal, often suffer from high overhead and slow adaptation in mobile environments. This paper addresses the need for a distributed framework that allows RSs to autonomously form an optimal tree-shaped network.

System Model and Game Formulation

The authors model the interaction between relay stations as a Network Formation Game. In this game, each RS acts as an independent player aiming to maximize its own utility. The core of this model is a cross-layer utility function defined as "system power," which represents the ratio of effective throughput to average multi-hop delay.

Illustration of the multi-hop relay network architecture and traffic flow parameters.

The utility function accounts for:

  1. Cooperative Gain: Improved signal quality and reduced Bit Error Rate (BER) through cooperative transmission.
  2. Multi-hop Delay: Increased queuing and transmission delays associated with additional hops, modeled using M/D/1 queuing theory.

To form the network, a distributed myopic algorithm is employed. Each RS periodically evaluates its current connection and considers switching to a different "parent" node (another RS or the BS) if it improves its utility. To ensure stability and prevent infinite loops, a "history function" is integrated, guiding the network toward a stable Nash tree network.

Performance Evaluation

The proposed framework was validated through numerical simulations in a 3km x 3km area with up to 25 RSs and 50 Mobile Stations (MSs). The simulations utilized a Poisson traffic model and Rayleigh fading channels with path loss.

Key findings include:

  • Significant Utility Gains: The distributed algorithm achieved a 17.1% improvement in average utility per MS compared to a non-relay scenario.
  • Superiority over Heuristics: It outperformed the "nearest neighbor" algorithm by up to 40.3%, demonstrating that signal strength alone is an insufficient metric for network formation.
  • Scalability and Efficiency: Even with 25 RSs, the average hop count remained below 3, indicating that the utility function effectively penalizes excessive delay. The "Price of Anarchy"—the performance gap between this distributed approach and a global optimum—was found to be approximately 9%.
  • Dynamic Adaptation: The network demonstrated "self-healing" properties, autonomously reconfiguring its topology in response to RS mobility or changes in MS distribution.

Conclusion and Future Work

This research provides a robust, distributed mechanism for relay station organization in next-generation networks. By balancing cooperative benefits against multi-hop costs, the game-theoretic approach ensures high performance and adaptability. Future research directions include joint optimization of MS-to-RS and RS-to-BS links, exploring Stackelberg game dynamics where MSs act as leaders, and incorporating energy efficiency constraints into the utility function to better support battery-powered relay nodes.

Summary updated

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.
BibTeX
@article{saad2011network,
  author = {Walid Saad and Zhu Han and Tamer Basar and Mérouane Debbah and Are Hjørungnes},
  title = {{Network Formation Games Among Relay Stations in Next Generation Wireless Networks}},
  journal = {IEEE Trans. Communications},
  year = {2011},
  doi = {10.1109/tcomm.2011.062311.100046},
}
Figure