Make your paper interactiveCreate

Text from the interactive explanation

Pragmatic Distributed Algorithm for Spectral Access in Cooperative Cognitive Radio Networks

Wei Liang, Soon Xin Ng, Jiao Feng, Lajos Hanzo

Original paper

How selfish radios can share the airwaves — an interactive guide to Liang, Ng, Feng & Hanzo, IEEE Transactions on Communications (2014)

Every licensed radio band has an owner , and nearby unlicensed “cognitive” radios — helpers — are hungry for airtime. A helper can relay an owner’s message and be paid with a slice of the owner’s time slot. With many owners chasing a few good helpers, how should deals be struck — with no central referee?

5 helpers · 8 owners · rates in bit/s/Hz*

Round 1 · new positions and fresh fading

Owner’s transmitter (one band each)

Owner’s receiver

Helper

Helper’s own receiver

Owner sends · helper relays

Helper’s own data (its pay)

Taking turns: whose pick it is

Bidding war: a contested offer

Airtime bar of one slot: owner sends · helper relays · helper’s own time

Simulated live in your browser with the paper’s equations (ideal-capacity links, amplify-and-forward relays, random fading each round). Positions are schematic. *bit/s/Hz = bits per second for every hertz of bandwidth; the paper’s plots call it “bps” for a unit time slot and bandwidth.

Chapter 1

One deal: help for airtime

Each owner is a pair of radios: a transmitter and its receiver , two distance units apart. Outdoors, signal power falls with the fourth power of distance — double the distance and only one-sixteenth of the power arrives. So the receiver hears a faint signal, and the owner’s rate is low.

A helper standing in between changes that. For the first half of the owner’s share of the slot, the owner broadcasts and both its receiver and the helper listen. For the second half, the helper amplifies and repeats what it heard, and the receiver combines the two copies. Two short hops are far stronger than one long one, so the owner needs only a fraction β of its slot to beat what it could send alone — and it pays the helper with the rest, 1 − β, for the helper’s own data.

A deal has to beat each side’s alternative: the owner must do better than going alone, and the helper needs at least 2 bit/s/Hz for its own data. That squeezes β between two limits — the deal window . Drag the helper, its partner, and the split of the slot.

Drag the helper or its partner — or focus one and use the arrow keys.

One time slot of the owner’s band

Deal window: β from 0.27 to 0.87

Deal! Both beat their alternatives

–

Predict first

Where should the helper stand to give the owner the best deal?

Pick one — then the map of good spots appears inside the square.

Owner’s capacity with a helper (Eq. 5–6). CPU = ½ · log₂(1 + γPU|hd|²/dPt,Pr4 + f), where f is the amplify-and-forward gain of the two hops. The ½ is because the owner’s share is split into two halves (send, relay).

Owner’s rate (Eq. 4) = β · CPU. Going alone (Eq. 8): C* = log₂(1 + γPU|hd|²/24) — this is the owner’s requirement.

Helper’s rate (Eq. 9). (1 − β) · log₂(1 + γCU|hCt,Cr|²/dCt,Cr4), which must reach 2.

The deal window (Eqs. 20–21). βmin = C*/CPU ≤ β ≤ βmax = 1 − 2 / log₂(1 + SNRown).

Default view: average channels (|h|² = 1). “Let the channels flicker” draws Rayleigh fading for every link.

Chapter 2

Two owners, one great helper

Now add a second owner. Both would love the same helper: Helper 1 stands close to both their transmitters. Helper 2 is farther off and worth less to each of them.

The paper’s benchmark is a conventional distributed rule (from Bayat and colleagues, 2011) that works like an auction. Each owner proposes to its favourite helper, offering to keep a share β of its slot. A helper keeps whichever offer leaves it the most airtime. A rejected owner sweetens its offer for that helper by 5 % of the slot and tries again.

You are owner B . Owner A got there first: it holds Helper 1 with an offer of β = 0.84, and the helper turned down your equal offer (ties go to the current holder). What will you do?

Owner A holds Helper 1 at β = 0.84. Your equal offer was turned down.

Who ends up with what? (owners’ rates in bit/s/Hz)

Fighting hands airtime to the helper just to beat a rival, so the owners’ total drops. Walking away keeps the total, but only one owner benefits. Taking turns keeps nearly the whole value and shares it. The paper calls the waste “competition loss” — and its proposal simply gives up the futile competition.

Mini-game with fixed positions and average channels (no fading), owners at 10 dB, helpers at 25 dB; all numbers computed with the paper’s equations. Helper 2’s offers settle at β = 0.84, the first price on the 0.99, 0.94, 0.89 … ladder that the helper accepts.

Chapter 3

Why would anyone wait their turn?

In the paper’s proposal, all owners form one coalition and pick helpers from a rotating priority list : in round 1 owner 1 picks first, in round 2 owner 8 picks first, then owner 7, and so on. Each owner in turn takes the best helper still free and offers it the most the helper will accept. Only the first list needs broadcasting; everyone can work out the rest. Nobody needs to know anyone else’s rates.

Taking turns pays on average. But in a round where the rotation leaves you without a helper, grabbing one anyway is tempting. The paper’s answer is a known threat: if anyone breaks ranks, all owners go back to the bidding war for Tp rounds , then resume taking turns. Endless punishment would hurt everyone — the punishers too — so choose the shortest punishment that wipes out the one-time gain.

Working out the averages…

–

Average rates come from this page’s simulation of the paper’s model (2,000 random rounds per helper count, 8 owners, helpers at 25 dB). Future rounds count a little less: with patience δ, a payoff i rounds ahead is weighted by δi.

Chapter 4

The whole market: 8 owners, 2–10 helpers

Time to test all four ways of matching, on thousands of random markets. The all-knowing referee (the paper’s centralized algorithm) tries every pairing and picks the one with the highest total for the owners — the best possible, but it needs everyone’s channel information collected and the answer sent back. Taking turns is the paper’s proposal, bidding war is the conventional rule, and random offers (one fixed β, a random acceptable helper) is the floor.

Predict first

Taking turns helps most when helpers are…

Choose, then watch the gap between gold and coral in the chart below.

All-knowing referee

Taking turns

Bidding war

Random offers

Paper (hollow)

Simulating…

–

Simulated live with a re-implementation of the paper’s model (ideal-capacity links, amplify-and-forward relays, owners at 10 dB); hollow markers are the authors’ published values, re-read from their figure. Small differences are expected. Shaded bands show the simulation’s 95 % uncertainty.

Chapter 5

Real radios shift gears

Up to now every link carried Shannon’s ideal capacity — a smooth curve that real hardware can only approach. Real modems switch between a few gears : QPSK, 8PSK, 16QAM and 64QAM, carrying 1, 2, 3 or 5 information bits per symbol after turbo trellis coding — or they stay silent. The paper’s adaptive scheme (ATTCM) picks the fastest gear whose errors at the relay stay below one bit in 100,000. For these studies the relay decodes and re-sends the message (decode-and-forward).

–

Two hops, two ways to count

With decode-and-forward, the owner’s message travels transmitter → helper → receiver, each hop in its own half of the time. The paper counts the result two ways.

Chapter 6

What the authors found

The authors repeated the whole market in large computer simulations with practical radios: owners at 20 dB, helpers at 35 dB, decode-and-forward relays. Pick a kind of link and a way of counting the two hops, then hover, tap or use the arrow keys on the chart.

All-knowing referee

Taking turns

Bidding war

Random offers

–

Redrawn from Liang et al. (2014), Figs. 8–10; values re-read from the published plots (approximate). γPU = 20 dB, γCU = 35 dB, decode-and-forward relays.

Taking turns comes close to the all-knowing referee and stays above the bidding war at every helper count — for ideal and practical links alike (Figs. 5a, 8a–10a).

The gap is largest when helpers are fewer than owners. With practical ATTCM and 6 helpers, taking turns delivers 17.69 bit/s/Hz against 7.48 for the bidding war (Fig. 10a).

Competition can be worse than chance: counted with the ATTCM upper bound, the bidding war falls below random offers for 7 or fewer helpers (Fig. 10a).

More owners find a helper : the share of matched owners ranks referee > taking turns > bidding war > random (Fig. 5b).

Practical radios cost rate but not the ranking: ideal capacity > ideal code on real constellations > practical ATTCM, and the order of the strategies persists (Figs. 8–10).

The rotation is fair: after 100 or more rounds, owner 1 and owner 8 earn the same average rate (Fig. 3).

Price step trade-off: smaller bidding steps τ give slightly higher rates but longer matching; τ = 0.05 is the compromise used throughout (Fig. 7).

All results above come from the authors’ Monte Carlo computer simulations.

Chapter 7

Back to the market

So how should deals be struck with no central referee? The paper’s answer is a lightweight etiquette: a rotating priority list plus a short, credible threat . With it, selfish licence holders and unlicensed radios trade airtime nearly as well as an all-knowing referee — without anyone sharing rate information. Patient owners have no reason to cheat, so taking turns is a stable outcome of the repeated game (a subgame-perfect equilibrium). If all the rate information were available anyway, the centralized referee could be used instead.

The paper

Wei Liang, Soon Xin Ng, Jiao Feng and Lajos Hanzo, “Pragmatic Distributed Algorithm for Spectral Access in Cooperative Cognitive Radio Networks,” IEEE Transactions on Communications (accepted for publication), 2014. University of Southampton.

DOI 10.1109/TCOMM.2014.030214.130326 Accepted manuscript (PDF)

Charts redrawn from data in the paper’s figures; interactive scenes are simplified re-implementations of the paper’s equations and algorithms; layout of radios is schematic. Original paper © 2014 IEEE.

Topics in this iPaper

Engineering
supporting the efficient spectral access of multiple Primary Users (PUs) and Cognitive Users (CUs) in cooperative Cognitive Radio (CR) networks

Abstract, page 1

Computer science
this PDA is formulated as a punishment based repeated game for attaining equilibrium

Section I (Introduction), page 2

cognitive radio
Cognitive radio network, cooperative communication, spectrum access strategy, matching algorithm, ATTCM

Index Terms, page 1

cooperative communication
Cooperative communication is a novel communication paradigm

Section I (Introduction), page 1

repeated game
we considered a penalty/punishment based repeated game

Section IV (Repeated Game), page 6

spectrum sharing
spectrum sharing between PUs and CUs may last for a long period of time

Section IV (Repeated Game), page 6

turbo trellis coded modulation
we invoke an attractive practical adaptive Turbo Trellis Coded Modulation (ATTCM) scheme

Abstract, page 1

Pragmatic Distributed Algorithm for Spectral Access in Cooperative Cognitive Radio Networks — Interactive explanation | iPaper.ai