Dynamic Interference Minimization Routing Game for On-Demand Cognitive Pilot Channel

Quanyan Zhu, Zhou Yuan, Ju Bin Song, Zhu Han, Tamer Basar

Abstract

This paper presents a distributed routing framework for multi-hop cognitive radio networks (CRNs) designed to minimize interference with primary users (PUs) and network congestion. By modeling the routing process as a dynamic non-cooperative game and utilizing geometric medial axis pathfinding, the proposed algorithm allows secondary users (SUs) to reach a Cognitive Pilot Channel (CPC) base station efficiently. Simulations demonstrate that the approach achieves a superior balance between interference avoidance and packet delay compared to traditional Dijkstra and medial axis routing methods.

Introduction

In Cognitive Radio (CR) networks, Secondary Users (SUs) must communicate without interfering with licensed Primary Users (PUs). A critical component of this is the Cognitive Pilot Channel (CPC), which provides SUs with necessary spectrum information. However, routing requests to a CPC base station in a multi-hop environment is challenging. Shortest-path algorithms like Dijkstra’s often lead to high interference with PUs or network congestion at specific relay nodes.

Researchers from the University of Illinois and the University of Houston have proposed a novel solution: treating routing as a dynamic, multi-stage game. This research addresses the need for a distributed, interference-aware routing mechanism that dynamically adapts to the volatile wireless landscape.

Methodology

The proposed solution integrates geometry, queueing theory, and game theory into a multi-layered framework.

Geometric Pathfinding and Hierarchy

The algorithm utilizes the "medial axis"—a geometric curve equidistant from PU footprints—to identify paths where interference is naturally lowest. To prevent "traffic jams" on this narrow line, a relaxation factor ($\omega$) is introduced, widening the potential routing path and allowing more nodes to participate. The network is organized into hierarchical levels to facilitate multi-hop communication toward the CPC base station.

Multi-hop routing model using the medial axis and hierarchical levels for secondary user requests.

Game-Theoretic Routing

Routing is modeled as a stochastic multi-stage non-cooperative game where each SU acts as a player seeking to minimize a personal cost function. This cost includes:

  1. Interference: Proximity to PU footprints.
  2. Delay: Calculated using the Pollaczek-Khinchin formula for M/G/1 queueing systems. This ensures that as a node becomes congested, its cost increases, naturally diverting traffic to less busy relays.

Nodes employ "fictitious play," an iterative learning process where they observe neighbor behavior to pick optimal responses. The authors demonstrate that a mixed Nash Equilibrium can be reached via backward induction.

Simulation Setup

The framework was evaluated in a simulated 2 km x 2 km area with 3,000 randomly deployed nodes and two PUs with radii of 0.5 km and 0.2 km. Standard wireless parameters, including a 1W transmission power and a path loss factor of 2.5, were applied to test the algorithm's robustness.

Key Results

The simulation results highlight the algorithm's ability to find a "sweet spot" between interference and delay.

  • Convergence: The fictitious play algorithm is efficient, typically converging to a stable Nash Equilibrium within 60 iterations.
  • Performance Trade-offs: Compared to Dijkstra’s algorithm, the proposed method significantly reduces interference with PU networks. More importantly, it overcomes the limitations of pure Medial Axis (MA) routing. While MA is safe from interference, it causes significant packet delays due to congestion on the center line. The proposed "relaxed" game-theoretic approach drastically reduces these delays while maintaining acceptable interference levels.
Comparison of normalized packet delay across different routing algorithms as a function of distance.

Conclusion and Future Work

This research provides a robust mathematical foundation for distributed routing in CRNs. By treating congestion as a game mechanic, the network becomes self-regulating. Future work will address practical challenges such as imperfect PU footprint sensing, non-stationary PU behaviors, and the implementation of these complex algorithms on hardware-constrained IoT devices.

Summary updated

BibTeX
@inproceedings{zhu2010dynamic,
  author = {Quanyan Zhu and Zhou Yuan and Ju Bin Song and Zhu Han and Tamer Basar},
  title = {{Dynamic Interference Minimization Routing Game for On-Demand Cognitive Pilot Channel}},
  booktitle = {GLOBECOM},
  year = {2010},
  doi = {10.1109/glocom.2010.5683923},
}
Figure