PaperlayerView exact revision on arXiv

Source-linked AI summary

Coalitional Games for Distributed Collaborative Spectrum Sensing in Cognitive Radio Networks

Walid Saad, Zhu Han, Merouane Debbah, Are Hjørungnes, Tamer Başar

arXiv:0905.2659v1cs.GTcs.IT

TL;DR

Collaborative sensing must improve primary-user detection without incurring excessive false alarms, while existing approaches emphasize centralized coordination. The paper uses a non-transferable coalitional game with distributed merge-and-split formation, achieving up to 86.6% lower average missing probability per secondary user than non-cooperation and adapting topology to mobility.

  • Problem

    Collaborative sensing faces a trade-off between improved primary-user detection and false-alarm costs, while centralized coalition optimization is NP-complete.

  • Method

    The paper models sensing as a non-transferable coalitional game and uses distributed merge-and-split rules for autonomous coalition formation.

  • Results

    Up to 86.6% reduction in average missing probability per secondary user is achieved relative to the non-cooperative case while maintaining a false-alarm constraint.

  • Takeaways & Limitations

    The algorithm forms disjoint coalitions with a maximum coalition size and autonomously adapts network topology to environmental changes such as mobility.

Abstract

from arXiv · show

Collaborative spectrum sensing among secondary users (SUs) in cognitive networks is shown to yield a significant performance improvement. However, there exists an inherent trade off between the gains in terms of probability of detection of the primary user (PU) and the costs in terms of false alarm probability. In this paper, we study the impact of this trade off on the topology and the dynamics of a network of SUs seeking to reduce the interference on the PU through collaborative sensing. Moreover, while existing literature mainly focused on centralized solutions for collaborative sensing, we propose distributed collaboration strategies through game theory. We model the problem as a non-transferable coalitional game, and propose a distributed algorithm for coalition formation through simple merge and split rules. Through the proposed algorithm, SUs can autonomously collaborate and self-organize into disjoint independent coalitions, while maximizing their detection probability taking into account the cooperation costs (in terms of false alarm). We study the stability of the resulting network structure, and show that a maximum number of SUs per formed coalition exists for the proposed utility model. Simulation results show that the proposed algorithm allows a reduction of up to 86.6% of the average missing probability per SU (probability of missing the detection of the PU) relative to the non-cooperative case, while maintaining a certain false alarm level. In addition, through simulations, we compare the performance of the proposed distributed solution with respect to an optimal centralized solution that minimizes the average missing probability per SU. Finally, the results also show how the proposed algorithm autonomously adapts the network topology to environmental changes such as mobility.

I. INTRODUCTION

Cognitive radio networks seek to exploit underused licensed spectrum, but reliable sensing is difficult because signal degradation can cause harmful PU interference. The paper proposes distributed coalitional collaboration that balances improved detection against false-alarm costs.

  • Licensed spectrum remains unoccupied for large periods, motivating cognitive radio access by secondary users when primary users are absent.
  • Signal degradation from path loss or shadowing creates a hidden-terminal problem that can reduce primary-user detection performance.
  • The paper develops distributed collaboration strategies and studies how the detection–false-alarm trade-off shapes secondary-user network topology.
  • A non-transferable coalitional game and merge-and-split algorithm let secondary users autonomously form or break coalitions while accounting for false-alarm cost.
  • The study evaluates coalition performance against non-cooperative and centralized solutions and examines adaptation to mobility.

II. SYSTEM MODEL

The system models secondary users sensing a primary user with energy detectors and collaborating through coalition-based decision fusion. Increasing coalition size lowers missing probability but raises false-alarm probability, creating the central topology-design trade-off.

  • The network contains N secondary-user transmit–receive pairs and one primary user, with users and the primary user potentially stationary or mobile.
  • Each secondary user uses an energy detector to sense the primary-user signal in the non-cooperative setting.
  • The detection model uses time-bandwidth product m, common threshold λ, gamma functions, and average received SNR γ̄_i.
  • Within a coalition, a coalition head collects sensing bits and makes the coalition-based decision on primary-user presence or absence.
  • The coalition head is chosen as the member with the lowest non-cooperative missing probability.
  • As coalition size increases, missing probability decreases while false-alarm probability increases, constraining collaboration and network topology.

III. COLLABORATIVE SPECTRUM SENSING AS COALITIONAL GAME

The paper formulates collaborative spectrum sensing as a coalitional game and establishes properties of that game before presenting coalition-formation strategies.

  • Collaborative spectrum sensing is modeled as a coalitional game whose key properties are then proved and discussed.

A. Centralized Approach

The centralized benchmark searches over partitions to minimize average missing probability subject to a false-alarm constraint. This optimization is computationally difficult because the number of coalition structures grows exponentially with the number of users.

  • A. Centralized Approach: A centralized entity can gather user information and seek the coalition structure that minimizes average missing probability subject to a false-alarm constraint.
  • A. Centralized Approach: Every secondary user in a coalition inherits that coalition’s missing and false-alarm probabilities through the coalition-head decision.
  • A. Centralized Approach: The centralized problem optimizes over all partitions of the secondary-user set, with coalition cardinality represented by |S|.
  • A. Centralized Approach: Finding the optimal coalition structure is NP-complete because the number of partitions grows exponentially with N.
  • A. Centralized Approach: The centralized solution is therefore used as a benchmark for the distributed method in reasonably small networks.

B. Game Formulation and Properties

The paper models collaborative spectrum sensing as a non-transferable coalitional game whose utility balances detection gains against false-alarm costs. Because false alarms increase with coalition size, disjoint coalitions may form instead of the grand coalition.

  • Game model: The proposed collaborative sensing problem is modeled as a non-transferable coalitional game among secondary users.Each coalition has a value function, and individual utilities cannot be arbitrarily apportioned among coalition members.
  • Utility design: Coalition value increases with detection probability and decreases with false alarm probability.The utility uses detection probability Qd,S = 1 − Qm,S and a false-alarm cost C(Qf,S).
  • Coalition structure: False-alarm costs can prevent the grand coalition from forming, yielding disjoint independent coalitions.Larger coalitions improve detection but also increase false alarms, so the grand coalition is generally not optimal when cooperation costs are included.
  • Distributed formation: The proposed game seeks a distributed coalition-formation algorithm for secondary users.The algorithm is designed to account for the cooperation cost while forming coalitions.

C. Cost Function

The cost function penalizes false alarms increasingly sharply and enforces a maximum tolerable false-alarm probability. Its effective cooperation cost also rises with coalition size and inter-user distance.

  • Design requirements: The cost function must increase with false-alarm probability and impose an upper bound on tolerable false alarms.Its slope should become steeper as false-alarm probability increases.
  • Penalty function: The proposed cost function is a logarithmic barrier penalty function.The barrier makes costs increase steeply as false-alarm probability approaches the constraint α.
  • Constraint: The false-alarm constraint α is imposed per coalition and per secondary user.The cost depends on Qf,S, the coalition false-alarm probability.
  • Network effects: Cooperation costs increase with coalition size and with distance between coalition members.Both effects act through the false-alarm probability Qf,S.

IV. DISTRIBUTED COALITION FORMATION ALGORITHM

The paper proposes a distributed coalition-formation algorithm and analyzes its main properties.

  • Distributed algorithm: A distributed coalition-formation algorithm is proposed for collaborative spectrum sensing.The section also discusses the algorithm’s main properties.

A. Coalition Formation Concepts

The coalition-formation framework represents the network as disjoint coalitions and compares alternative partitions using player utilities. Because utilities are non-transferable, the paper uses the Pareto order for preferences.

  • Coalition formation: Coalition formation uses merge-and-split rules to construct distributed structures when the grand coalition is not optimal.The framework supports coalitions forming and breaking through simple distributed operations.
  • Coalition concepts: A collection is a set of mutually disjoint coalitions, and it is a partition when it spans all players.The collection is denoted S = {S1, . . . , Sl}.
  • Preference relations: A preference operator compares two partitions of the same subset of players.The relation indicates which partition is preferred under a specified criterion.
  • Order types: Coalition-value orders compare collections using coalition values, whereas individual-value orders compare player utilities.The two categories differ in whether comparison is based on coalition values or individual payoffs.
  • Pareto preference: The proposed game uses an individual-value Pareto order because its utilities are non-transferable.A partition is preferred when all relevant player utilities are no worse and at least one is strictly better.

B. Coalition Formation Algorithm

The distributed algorithm forms coalitions through merge-and-split operations, combining local sensing, adaptive formation, and coalition sensing. Its utility and cost models limit coalition size and support autonomous adaptation to environmental changes.

  • Merge-and-split rules: Merge and split rules let coalitions reorganize when the resulting collection is preferred under the selected order.Under Pareto order, at least one SU must strictly improve its utility without reducing the utilities of the others.
  • Distributed operation: Merge decisions can be made distributively by individual SUs or already formed coalitions, without a centralized entity.The process iterates successive merge-and-split operations until the partition terminates.
  • Algorithm phases: The algorithm has three phases: local sensing, adaptive coalition formation, and coalition sensing.Coalitions ultimately share local sensing bits with a coalition head, which applies an OR decision-fusion rule.
  • Adaptation: The algorithm periodically repeats coalition formation so SUs can adapt the network topology to mobility and SUs joining or leaving.Each coalition reassesses possible merges or splits subject to the Pareto-order rule.
  • Coalition-size bound: The proposed utility and cost models impose an upper bound on the maximum number of SUs per coalition.The bound follows from the false-alarm constraint and the log-barrier cost, with Mmax depending mainly on α and the non-cooperative false alarm probability Pf.

C. Stability

The proposed coalition structures are analyzed using Dhp- and Dc-stability. The algorithm always converges to a Dhp-stable partition and reaches the optimal Dc-stable partition when that partition exists, although its existence depends on SU and PU locations.

  • Dhp-stability: Every partition produced by the coalition formation algorithm is Dhp-stable.Dhp-stability means no coalition has an incentive to merge or split further.
  • Dc-stability: If it exists, a Dc-stable partition is the unique outcome of arbitrary merge-and-split iterations and is also Dhp-stable.Dc-stability additionally corresponds to a unique maximal partition under the selected order, including Pareto-optimal utility distribution when that order is Pareto.
  • Algorithmic guarantee: The algorithm converges to the optimal Dc-stable partition when one exists; otherwise, it produces a Dhp-stable final partition.This is the stated guarantee for the proposed collaborative-sensing game.
  • Existence conditions: A Dc-stable partition is not always guaranteed to exist.Its existence requires Pareto-order conditions for coalitions within each partition and for coalitions spanning different coalitions.
  • Location dependence: A closed-form geometric existence condition is infeasible because stability depends on SU and PU locations through individual missing and false alarm probabilities.Those locations may be random parameters in practical networks.

V. SIMULATION RESULTS AND ANALYSIS

Simulations show that distributed coalition formation reduces missing probability while trading off false alarms, forms small coalitions, and adapts topology to mobility.

  • Performance: 86.6% reduction in average missing probability per SU is achieved at N = 30 compared with the non-cooperative case.The advantage increases with network size, although the distributed method remains behind the optimal centralized solution.
  • Performance: The distributed solution achieves lower average false alarm than the centralized solution, while the non-cooperative case achieves the lowest false alarm.This lower false alarm compensates for the distributed solution’s missing-probability performance gap.
  • Performance: As non-cooperative Pf approaches α = 0.1, collaborative-sensing gains diminish and the network converges toward the non-cooperative case.For N = 7, decreasing Pf increases the missing-probability advantage except at very small Pf, where the advantage reaches its maximum.
  • Coalition topology: At Pf = 0.01 with N = 7, distributed and centralized coalition structures are almost comparable, but SU 4 selects a different coalition under autonomous utility maximization.SU 4 prefers {1, 2, 4, 6}, with utility 0.9957 and missing probability 0.00099, over {3, 4, 5}.
  • Mobility adaptation: After SU 1 moves 0.8 km, merge-and-split separates {1, 6} from {1, 2, 4, 6}, and SU 6 rejoins {2, 4} to form {2, 4, 6}.The rejoining increases the utilities of all three SUs, illustrating adaptation during mobility.
  • Coalition topology: For N = 30, the average maximum coalition size does not exceed 4 SUs, despite the upper bound Mmax increasing sharply as Pf decreases.The resulting topology generally contains many small coalitions rather than a few large ones.

VI. CONCLUSIONS

The paper proposes a distributed coalitional-game algorithm for collaborative spectrum sensing. It characterizes the resulting network structure and evaluates its sensing, coalition-size, and mobility behavior.

  • Method: The proposed method models collaborative sensing as a non-transferable-utility coalitional game using merge-and-split rules.These rules let SUs cooperate while accounting for false-alarm costs.
  • Analysis: The analysis characterizes network stability and establishes a maximum number of SUs per coalition for the proposed utility model.The simulations further examine performance against non-cooperation and an optimal centralized solution.
  • Results: The distributed algorithm reduces average missing probability per SU by up to 86.6% relative to the non-cooperative case while maintaining a false-alarm level.It also autonomously adapts network topology to environmental changes such as mobility.
Loading 0905.2659v1…