Statistical Routing for Multihop Wireless Cognitive Networks

Emiliano Dall'Anese, Georgios B. Giannakis

This paper, published in the IEEE Journal on Selected Areas in Communications, presents a robust mathematical framework for routing data through wireless networks that must "borrow" spectrum from licensed users.

TL;DR

The authors propose a cross-layer optimization framework for multihop cognitive radio networks that treats channel randomness and interference as statistical variables rather than fixed values. By jointly optimizing routing, medium access, and transmit power through a distributed algorithm, they ensure reliable data delivery while strictly protecting licensed "primary" users from interference.

What Problem Does This Paper Address?

In Cognitive Radio (CR) networks, unlicensed users (secondary users) must communicate without disrupting licensed Primary Users (PUs). This is incredibly difficult because wireless channels are inherently unpredictable due to fading and shadowing. Furthermore, in a hierarchical setup, the secondary users often don't have perfect information about when or where a PU is transmitting.

Traditional routing protocols usually rely on a "disk model" (if you are within $X$ meters, you have a link) or fixed link capacities. These fail in CR environments where a link might disappear instantly because a PU started talking or a shadow fell over the receiver. The challenge is to find a way to route packets that is "spectrum-cognizant"—meaning it accounts for the statistical likelihood of a link being available and reliable at any given moment.

Methods

The authors move away from deterministic routing and toward Statistical Routing. Key components include:

  • Stochastic Modeling: They use the Fenton-Wilkinson method to approximate the Signal-to-Interference-plus-Noise Ratio (SINR) as a log-normal distribution. This allows them to calculate "outage probabilities" for every potential link.
  • Cross-Layer Optimization: Instead of looking at routing in isolation, they solve a joint problem that determines:
  • Routing: The probability of forwarding a packet to a specific neighbor.
  • MAC: The probability that a node attempts to transmit in a given time slot.
  • Physical Layer: The optimal transmit power for each node.
  • Successive Convex Approximation (SCA): The resulting optimization problem is non-convex (notoriously hard to solve). The authors use SCA to transform it into a series of simpler convex problems that converge to a high-quality solution.
  • Distributed Computation: To make the system scalable, they use the Alternating Direction Method of Multipliers (ADMoM) and primal decomposition. This allows individual nodes to compute their own optimal settings by only exchanging small amounts of data with their immediate neighbors.

Datasets

The paper evaluates the proposed algorithms using simulated network environments rather than static datasets.

  • Setup: A 7-node secondary network attempting to reach a sink node while 2 PU transmitters are active.
  • Parameters: They modeled path loss with an exponent of 3.5, log-normal shadowing with a 6 dB standard deviation, and Rayleigh small-scale fading.
  • Benchmarks: The performance is measured against traditional shortest-path routing and evaluated based on exogenous traffic rates (how much data the network can actually handle).

Key Insights and Ideas

  • Outage-Awareness: The most significant "aha moment" is that the algorithm doesn't just look for the shortest path; it looks for the most reliable path. In simulations, the network avoids nodes physically close to PUs. Even if those nodes are on the shortest path, the interference constraints force them to use very low power, making their links unreliable.
  • Dynamic Adaptability: Because the algorithm is iterative and distributed, it can be implemented "online." If a PU stops transmitting, the CR nodes sense the change in statistics and automatically shift their routes to more direct paths that were previously too risky.
  • Guaranteed Delivery: The authors provide a mathematical proof (Proposition 3) that as long as the network remains "statistically connected," packets are guaranteed to reach their destination with probability 1, even with random routing.

Key Results

  • Convergence: The distributed ADMoM algorithm reached consensus on local variables within approximately 8 to 15 iterations in the test scenarios.
  • Interference Protection: The primal decomposition method successfully enforced PU interference power constraints (set at -80 dBW in tests) even during the learning phase of the algorithm.
  • Efficiency: The statistical approach allowed for higher "exogenous traffic rates" (the amount of new data the network can accept) compared to protocols that don't account for the randomness of the medium.

Limitations and Future Work

  • Mobility: The current framework is designed for "slow" environmental dynamics. If nodes are moving very fast, the time required for the distributed algorithm to converge might exceed the time the topology remains stable.
  • Control Channel Overhead: The distributed implementation relies on a control channel for neighbors to exchange multipliers and local variables. In highly congested or restricted spectrum environments, this overhead could become a bottleneck.
  • Future Directions: The authors suggest extending this work to mobile ad-hoc networks (MANETs) where channel uncertainty is even higher due to rapid topological changes.

Summary updated

Abstract

To account for the randomness of propagation channels and interference levels in hierarchical spectrum sharing, a novel approach to multihop routing is introduced for cognitive random access networks, whereby packets are randomly routed according to outage probabilities. Leveraging channel and interference level statistics, the resultant cross-layer optimization framework provides optimal routes, transmission probabilities, and transmit-powers, thus enabling cognizant adaptation of routing, medium access, and physical layer parameters to the propagation environment. The associated optimization problem is non-convex, and hence hard to solve in general. Nevertheless, a successive convex approximation approach is adopted to efficiently find a Karush-Kuhn-Tucker solution. Augmented Lagrangian and primal decomposition methods are employed to develop a distributed algorithm, which also lends itself to online implementation. Enticingly, the fresh look advocated here permeates benefits also to conventional multihop wireless networks in the presence of channel uncertainty.
BibTeX
@article{dallanese2012statistical,
  author = {Emiliano Dall'Anese and Georgios B. Giannakis},
  title = {{Statistical Routing for Multihop Wireless Cognitive Networks}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2012},
  url = {https://openreview.net/forum?id=Z3G9St7P4p},
}

Loading related content...

Figure