PaperlayerView exact revision on arXiv

Source-linked AI summary

Coalition Formation Games for Collaborative Spectrum Sensing

Walid Saad, Zhu Han, Tamer Basar, Merouane Debbah, Are Hjørungnes

arXiv:1010.4501v1cs.ITcs.GTmath.IT

TL;DR

Collaborative spectrum sensing must improve primary-user detection without letting false alarms compromise spectrum use. The paper models cooperation as a non-transferable coalitional game and proposes distributed coalition-formation algorithms; simulations report reduced miss probability for CF and target detection for many SUs with CF-PD.

  • Problem

    CSS must balance reducing missed PU detections against maintaining a reasonable false-alarm probability, while SUs may need to form local groups without centralized fusion.

    Source: §II · p. 3

  • Method

    The paper models CSS as a non-transferable coalitional game and proposes distributed CF and voting-based CF-PD algorithms for forming coalitions under false-alarm costs or PU detection targets.

    Source: §I · p. 2

  • Results

    CF reduces average probability of miss per SU by up to 88.45% relative to the non-cooperative case, while CF-PD enables up to 87.25% of SUs to achieve the required detection probability through minimal winning coalitions.

    Source: §VIII · p. 19

  • Takeaways & Limitations

    The algorithms let SUs self-organize into coalitions and adapt network structure to environmental changes such as mobility.

    Source: §VIII · p. 19

Abstract

from arXiv · show

Collaborative Spectrum Sensing (CSS) between secondary users (SUs) in cognitive networks exhibits an inherent tradeoff between minimizing the probability of missing the detection of the primary user (PU) and maintaining a reasonable false alarm probability (e.g., for maintaining a good spectrum utilization). In this paper, we study the impact of this tradeoff on the network structure and the cooperative incentives of the SUs that seek to cooperate for improving their detection performance. We model the CSS problem as a non-transferable coalitional game, and we propose distributed algorithms for coalition formation. First, we construct a distributed coalition formation (CF) algorithm that allows the SUs to self-organize into disjoint coalitions while accounting for the CSS tradeoff. Then, the CF algorithm is complemented with a coalitional voting game for enabling distributed coalition formation with detection probability guarantees (CF-PD) when required by the PU. The CF-PD algorithm allows the SUs to form minimal winning coalitions (MWCs), i.e., coalitions that achieve the target detection probability with minimal costs. For both algorithms, we study and prove various properties pertaining to network structure, adaptation to mobility and stability. Simulation results show that CF reduces the average probability of miss per SU up to 88.45% relative to the non-cooperative case, while maintaining a desired false alarm. For CF-PD, the results show that up to 87.25% of the SUs achieve the required detection probability through MWC

I. INTRODUCTION

The paper develops distributed coalition formation for collaborative spectrum sensing, balancing improved PU detection against false-alarm costs. Its system model lets SUs cooperate locally while making autonomous coalition decisions.

I. INTRODUCTION

  • Distributed CSS is needed because centralized fusion can impose infrastructure, overhead, and complexity that are impractical for ad hoc networks of geographically dispersed SUs.Prior cluster approaches cited in the introduction either assume preformed clusters or retain centralized fusion, and do not account for the miss–false-alarm tradeoff.Source: §I · pp. 1–2
  • The paper models CSS as a non-transferable coalitional game and proposes distributed CF and CF-PD algorithms for autonomous coalition formation.CF accounts for detection gains and false-alarm costs; CF-PD adds a coalitional voting game to form minimal winning coalitions when the PU requires a detection probability target.Source: §I · pp. 1–2
  • The motivation is to improve PU detection without allowing false alarms to undermine spectrum utilization, while accounting for SUs’ cooperative incentives.The paper also studies how the network structure changes with those incentives.Source: §I · p. 2

II. SYSTEM MODEL

  • The system considers energy-detecting SUs and a PU, with stationary or mobile nodes; its miss-probability model averages small-scale Rayleigh fading and focuses on large-scale path loss.The model does not account for shadowing.Source: §II · p. 2
  • Within each coalition, a coalition head collects sensing bits and applies OR-rule fusion; the model selects the SU with the lowest non-cooperative miss probability as head.This choice avoids reporting the coalition’s most reliable sensing bit, which could be received in error; other head-selection approaches can also be accommodated.Source: §II · p. 3
  • As coalition size increases, miss probability decreases but false-alarm probability increases, shaping which coalitions are worthwhile.A centralized optimum would minimize average miss probability per SU subject to an average false-alarm constraint, but finding the optimal partition is NP-complete and can disregard individual SU preferences.Source: §II · p. 3

A. Game Formulation and Properties

The game assigns coalition utility to detection performance while penalizing false alarms, so cooperation can improve sensing but does not generally favor the grand coalition. A logarithmic barrier cost enforces the false-alarm limit and makes cooperation increasingly costly near it.

A. Game Formulation and Properties

  • The paper models CSS as an NTU game because coalition value is not freely apportioned among its members.The payoff set for a coalition is a singleton, with each member’s payoff equal to v(S).Source: A. Game Formulation and Properties · p. 4
  • The coalition utility v(S) combines detection probability with a cost that decreases utility as false-alarm probability rises.The cost depends on the coalition’s false-alarm probability and constraint; the paper assumes the same constraint α for every coalition.Source: A. Game Formulation and Properties · p. 4
  • Each SU in a coalition receives the coalition’s full value, making its payoff non-divisible and the game non-transferable.Because coalition members act on the coalition head’s fused decision, each member has the coalition’s miss and false-alarm probabilities.Source: A. Game Formulation and Properties · p. 4
  • The grand coalition seldom forms because cooperation’s false-alarm costs limit the detection gains; instead, disjoint independent coalitions form.The coalition structure captures the tradeoff between lower miss probability and false-alarm costs.Source: A. Game Formulation and Properties · pp. 4–5
  • Larger coalitions reduce miss probability, but their rising false-alarm probability can exceed the constraint and remove incentives to cooperate.Without collaboration costs, the grand coalition would maximize detection probability; the false-alarm constraint changes that structure.Source: A. Game Formulation and Properties · p. 4

B. Cost Function

  • The false-alarm cost must rise increasingly steeply with false-alarm probability and prevent any coalition from exceeding α.The paper uses a logarithmic barrier penalty that makes the collaboration cost increase sharply near the allowed false-alarm level.Source: B. Cost Function · p. 5
  • As false-alarm probability approaches α, the barrier raises collaboration costs, requiring greater detection improvement for SUs to have an incentive to cooperate.The cost also increases with coalition size and with the distance between coalition members, through the false-alarm probability and reporting error.Source: B. Cost Function · p. 5

IV. COALITION FORMATION GAMES IN CSS

The CF algorithm uses distributed merge-and-split decisions to form disjoint coalitions that balance detection gains against false-alarm costs. Its operation is designed to adapt to network changes, while coalition size and feasible merges are constrained by sensing and reporting conditions.

A. Distributed Coalition Formation Algorithm (CF)

  • CF applies merge-and-split rules using Pareto order, allowing changes only when no involved SU loses utility and at least one strictly benefits.Agreements to cooperate are partially reversible through a subsequent split agreement.Source: A. Distributed Coalition Formation… · p. 5
  • Each CF round discovers neighboring SUs and relevant sensing and distance information, adapts coalitions through sequential merge-and-split, then performs coalition sensing using OR-rule fusion.SUs report sensing bits to coalition heads, which make and share the final PU decision.Source: A. Distributed Coalition Formation… · pp. 5–6
  • Coalitions negotiate pairwise over a control channel, evaluating prospective merges with member miss probabilities and accepting them only when Pareto order is satisfied.Merge and split decisions are made without a centralized entity.Source: A. Distributed Coalition Formation… · pp. 6–7
  • Merge-and-split iterations converge to a cooperative partition whose SU payoffs are at least as good as the non-cooperative state, regardless of operation order.Under certain partition conditions, operation order does not affect the final structure.Source: A. Distributed Coalition Formation… · p. 7
  • Periodic CF reruns let coalitions adapt to mobility or SU arrivals and departures, with shorter intervals trading greater formation overhead for faster environmental adaptation.The analysis assumes changes during one algorithm run are small enough not to drastically affect utilities or decisions.Source: A. Distributed Coalition Formation… · p. 7
  • Two SUs can merge only when their reporting-channel error is below a bound determined by their sensing probabilities, yielding a distance-based merge region.The bound limits tolerated reporting error because greater error increases miss and false-alarm probabilities.Source: A. Distributed Coalition Formation… · p. 8
  • The proposed utility’s false-alarm cost bounds coalition size; the maximum depends on α and Pf, not SU placement or network population.The bound is obtained using a perfect-reporting coalition, which accommodates the largest number of SUs.Source: A. Distributed Coalition Formation… · p. 8
  • The algorithm limits coalition size according to the false-alarm constraint α and non-cooperative false-alarm probability Pf, independently of SU locations or network size.A larger α or smaller Pf permits a larger upper bound on coalition size.Source: A. Distributed Coalition Formation… · p. 8

B. Partition Stability

The algorithm always reaches a Dhp-stable partition, and reaches the stronger Dc-stable partition when one exists. Dc-stability is not guaranteed because its conditions depend on coalition and cross-coalition relationships that can be difficult to characterize.

B. Partition Stability

  • Every partition produced by CF is Dhp-stable: no coalition has an incentive to merge or split further.When no Dc-stable partition exists, the final partition is Dhp-stable.Source: B. Partition Stability · pp. 9–10
  • A Dc-stable partition is not guaranteed to exist, and checking its cross-coalition condition is difficult because a closed-form characterization is unavailable.The number of relevant incompatible coalitions grows for larger networks.Source: B. Partition Stability · p. 9
  • Dc-stability requires both within-coalition stability under splitting and that every cross-coalition group prefer its projection onto the partition.These requirements depend on the SUs’ distances and their miss and false-alarm probabilities.Source: B. Partition Stability · p. 9
  • If a Dc-stable partition exists, CF converges to that optimal partition, which is the unique outcome of merge-and-split iterations.Dc-stability is stronger than Dhp-stability and entails Pareto-optimal utility distribution under Pareto order.Source: B. Partition Stability · p. 9

V. DISTRIBUTED COALITION FORMATION ALGORITHM WITH PROBABILITY OF DETECTION GUARANTEES (CF-PD)

CF-PD adds a voting-game requirement for coalitions to meet a PU-specified detection target while respecting the false-alarm constraint. It uses minimal winning coalitions to meet that target without retaining members whose departure would leave the coalition winning.

V. DISTRIBUTED COALITION FORMATION ALGORITHM WITH PROBABILITY OF DETECTION GUARANTEES (CF-PD)

  • The adjunct voting game marks a coalition winning when it meets the required detection probability while keeping false alarm at or below α.The PU may impose the detection target to control allowed interference or the number of SUs using the spectrum.Source: §V · p. 10
  • A minimal winning coalition achieves the detection target, but becomes losing if any member defects, giving members no incentive to leave it.MWCs also avoid further coalition growth once detection requirements are met, limiting added false alarm and signaling overhead.Source: §V · p. 10
  • The adjustment procedure removes members whose removal leaves a winning coalition, producing an MWC from a winning coalition.The paper orders exclusions by increasing non-cooperative probability of miss.Source: §V · pp. 10–11
  • CF-PD first adjusts existing coalitions into MWCs, then applies merge-and-split to remaining coalitions and adjusts any newly formed coalition.Formed MWCs stop participating; excluded SUs continue in merge-and-split, and losing coalitions may need environmental changes to meet the target.Source: §V · pp. 10–11

VI. DISTRIBUTED IMPLEMENTATION OF CF AND CF-PD

The section addresses implementation challenges for CF and CF-PD in practical cognitive networks.

VI. DISTRIBUTED IMPLEMENTATION OF CF AND CF-PD

  • The section discusses challenges in implementing CF and CF-PD in practical cognitive networks.The supplied passage does not specify the challenges.Source: §VI · p. 11

A. Neighbor Discovery

Neighbor discovery supplies the local and PU-related information SUs need to assess potential coalition merges. CF-PD repeats discovery and coalition-adjustment phases before coalition sensing, with periodic repetition allowing adaptation to environmental changes.

A. Neighbor Discovery

  • CF-PD divides each round into discovery, partition adjustment, adaptive coalition formation, and coalition sensing.The initial partition is divided into losing and winning coalitions; the algorithm applies split-and-adjust and merge-and-split operations until they terminate.Source: A. Neighbor Discovery · p. 11
  • CF-PD periodically repeats its partition-adjustment and coalition-formation phases so SUs can adapt to environmental changes such as mobility.Discovery and coalition sensing remain as in CF.Source: A. Neighbor Discovery · p. 11
  • Coalitions survey neighboring coalitions within merge range and use the Pareto order to assess potential merges.SUs need their own miss probabilities and distances to neighbors; neighbors can share their miss probabilities over a control channel during negotiation.Source: A. Neighbor Discovery · p. 11
  • The information needed for coalition formation includes distances between neighboring SUs and between each SU and the PU.In Rayleigh fading, non-cooperative miss probability mainly depends on average SNR to the PU, which depends on distance.Source: A. Neighbor Discovery · p. 11
  • Candidate ways to obtain this information include cognitive control channels, signal processing, ad hoc neighbor discovery, and geo-location.The passage lists CPC –, signal-processing methods,,,,, ad hoc methods –, and geo-location, –.Source: A. Neighbor Discovery · p. 11

1) Neighbor discovery through control channels:

Control channels, particularly the Cognitive Pilot Channel (CPC), can provide SUs with information for discovering neighbors and forming coalitions. The CPC may be broadcast or delivered on demand, and may be supplied by receivers or a spectrum broker.

1) Neighbor discovery through control channels:

  • The CPC can carry spectrum opportunities, PU and SU locations, and other information that helps cognitive users sense and access spectrum.It can help SUs discover neighboring PUs and SUs in networks with multiple access technologies and heterogeneous environments.Source: 1) Neighbor discovery through control… · p. 12
  • The CPC can be broadcast to all users or sent on demand, with delivery by receivers or a stand-alone spectrum broker.After coalition formation, an SU can signal its membership to the receiver or broker for inclusion in the CPC.Source: 1) Neighbor discovery through control… · p. 12
  • By listening to the CPC, SUs can learn their miss probabilities, neighboring SUs, inter-SU distances, and potentially neighbors’ coalition memberships.The paper says this information can support CF and CF-PD with reasonable overhead.Source: 1) Neighbor discovery through control… · p. 12

2) Signal processing-based methods:

Neighbor discovery can use received-power estimates, ad hoc routing techniques, or geo-location databases. These approaches provide information for coalition decisions, with the paper noting a tradeoff between discovery accuracy and complexity.

2) Signal processing-based methods:

  • In Rayleigh fading, SUs can estimate neighboring-node distances from mean received power and use PU signal measurements to estimate their own miss probabilities.Coalition members can combine their individual miss probabilities to determine the coalition’s potential miss probability; only nearby SUs need be discovered for potential merges.Source: 2) Signal processing-based methods · p. 12

3) Existing ad hoc routing discovery techniques applied in cognitive networks:

  • Ad hoc neighbor discovery can use periodic “Hello” packets and replies to discover SUs and enable subsequent coalition formation.The packets can carry location, coalition membership, and control-channel scheduling information.Source: 3) Existing ad hoc routing discovery… · pp. 12–13

4) Geo-location techniques:

  • Geo-location databases can provide PU and neighboring-SU positions and potentially coalition memberships for CF or CF-PD.For mobile nodes, the paper describes GPS outdoors and other positioning methods when GPS is unavailable or nodes are indoors.Source: 4) Geo-location techniques · p. 13
  • The paper treats neighbor-discovery methods as alternatives, with a tradeoff between accuracy and complexity, provided they convey enough information about neighboring SUs and the PU.Once the needed parameters are estimated, coalitions can choose merge partners and decide whether to split according to the Pareto order.Source: 4) Geo-location techniques · p. 13

B. Coalition Formation Operations: Merge, Split, and Adjust

The paper discusses the practical costs of merge, split, and adjust operations, then describes coalition sensing and how estimation errors affect coalition decisions. Merge and split decisions are local, while the paper leaves a procedure for excluding a poorly performing SU outside its scope.

B. Coalition Formation Operations: Merge, Split, and Adjust

  • In the worst case, merge search may require N(N−1)/2 pairwise attempts, though proximity and false-alarm costs reduce attempts in practice.Later runs involve fewer coalitions than the initial N individual SUs, and successful merges reduce remaining merge possibilities.Source: B. Coalition Formation Operations:… · p. 13
  • Split search can grow exponentially with coalition size because it may examine Bell-number many partitions, but it is confined to individual coalitions.Increasing false-alarm costs and SU locations limit coalition size; sequential search can stop once a Pareto-improving split is found.Source: B. Coalition Formation Operations:… · pp. 13–14
  • In CF-PD, adjust is local to each winning coalition, has no effect on losing coalitions, and has complexity linear in the number of its SUs.The paper says winning coalitions do not participate in merge and split, which are typically less complex in CF-PD than CF.Source: B. Coalition Formation Operations:… · p. 14
  • Coalition sensing uses local sensing bits sent to a coalition head, which fuses them with the OR rule and broadcasts the result to members.The coalition-formation algorithm can be tailored to other decision-fusion techniques.Source: C. Coalition Based Sensing · p. 14
  • Coalition-level sensing uses less communication overhead than network-wide fusion, where every SU reports to a fusion center, and the paper also identifies reliability and power-consumption benefits.Coalition sensing exchanges single bits locally; coalition size is upper bounded by the false-alarm constraint, and coalition formation is repeated periodically to adapt to changes such as mobility.Source: C. Coalition Based Sensing · p. 14
  • Low-SNR estimation errors are reflected in SUs’ miss probabilities and are handled by Pareto-based merge and split decisions without perturbing algorithm convergence.This treatment assumes honest SUs and miss probabilities averaged over fading realizations.Source: D. Impact of Potential Estimation Errors · pp. 14–15
  • If an SU’s actual miss probability in cooperative operation is much higher than anticipated, the coalition may exclude it, but the exclusion procedure is outside the paper’s scope.The paper suggests approaches similar to those used to identify malicious SUs, such as onion peeling,.Source: D. Impact of Potential Estimation Errors · p. 15

VII. SIMULATION RESULTS AND ANALYSIS

The simulations show that distributed CF can substantially reduce missed detections while respecting the false-alarm tradeoff, and CF-PD helps many SUs meet required detection targets through minimal winning coalitions. Coalition structure also adapts to mobility and varies with detection conditions and user incentives.

VII. SIMULATION RESULTS AND ANALYSIS

  • For N = 16, CF-PD forms 10 coalitions including five non-cooperative SUs, while CF forms five coalitions and leaves none non-cooperative.Five nearby SUs already exceed χ = 95% individually; CF-PD makes each a singleton MWC, whereas CF continues to seek miss-probability gains.Source: Figure 2 · p. 15, §VII · p. 15
  • At m = 5 and N = 50, CF reduces average probability of miss per SU by up to 88.45% relative to the non-cooperative case.The reported comparison covers m = 5 and m = 1000; the centralized exhaustive-search comparison is limited to N ≤ 7 because larger searches are intractable.Source: §VII · pp. 15–16, Figure 3 · p. 16
  • For all tested m, distributed CF achieves lower average false alarm than the centralized solution, while at m = 1000 it forms no coalitions and performs comparably to non-cooperation.At m = 5 and N = 50, CF’s detection performance is comparable to, and slightly better than, non-cooperative sensing at m = 1000, without the longer sensing delay or wasted bandwidth.Source: Figure 4 · p. 16, §VII · p. 16
  • Theorem 1’s approximate merge angle closely matches the exact solution; merge regions shrink for better-performing SU1 locations and larger SU2 radii.When SU1 is at 0.8 km, it can merge with SU2 on circles up to 2.3 km in radius; at 0.4 km, the maximum is 1.5 km.Source: Figure 6 · p. 17, §VII · p. 17
  • Under 120 km/h mobility, CF evolves from 50 singletons to 18 coalitions averaging 2.77 SUs initially, then to 20 coalitions averaging 2.5 after five minutes.As speed increases, operation frequency rises; CF-PD has fewer merge-and-split operations but adds adjustments, with lower complexity than merge or split.Source: §VII · pp. 17, 19, Figure 7 · p. 18
  • At N = 50, CF-PD reaches 87.25% winning SUs, roughly tripling the non-cooperative share; at N = 7, it is within 3.7 percentage points of optimal.Some SUs still miss the χ = 95% target because of their locations and channels; mobility or new SUs may change that.Source: Figure 8 · p. 18, §VII · p. 18
  • At γ = 0.01, CF-PD enables at least 74.1% of SUs to meet the target, around eight times the non-cooperative share.As γ increases and the required detection probability becomes less stringent, the winning share increases for both approaches.Source: Figure 9 · p. 18, §VII · p. 18
  • As non-cooperative Pf increases, coalition sizes shrink; average maximum size stays at or below 5 SUs for CF and 3 for CF-PD.CF-PD coalitions are smaller because they stop collaborating once they achieve χ.Source: §VII · pp. 18–19, Figure 10 · p. 19

VIII. CONCLUSIONS

The paper models collaborative spectrum sensing as a non-transferable-utility coalitional game and proposes distributed coalition-formation algorithms that balance detection gains against false-alarm costs. The algorithms address unconstrained sensing improvement and detection-probability guarantees, with simulations reporting reduced miss probability, target attainment through minimal winning coalitions, and adaptation to environmental changes.

VIII. CONCLUSIONS

  • CF uses distributed merge-and-split rules to improve PU detection while accounting for false-alarm costs in coalition formation.The paper models the problem as a non-transferable-utility coalitional game.Source: §VIII · p. 19
  • CF-PD complements CF with a coalitional voting game when the PU imposes detection-probability guarantees, enabling minimal winning coalitions.The paper also characterizes the resulting network structure and proves properties of the proposed algorithms.Source: §VIII · p. 19
  • Up to 88.45% reduction in average probability of miss per SU versus the non-cooperative case; CF-PD enables up to 87.25% of SUs to meet the required detection probability through minimal winning coalitions.The results also show that the algorithms can adapt network structure to environmental changes such as mobility.Source: §VIII · p. 19

A. Proof of Theorem 1

The proof turns the pairwise merge condition into an inequality involving reporting error and false-alarm costs. Because the inequality is transcendental, it derives a sufficient approximate solution by considering the sign of D.

A. Proof of Theorem 1

  • A merge by SUs i and j requires the coalition payoff to exceed the higher singleton payoff, yielding an inequality in their reporting-error probability.With v({i}) ≥ v({j}), the Pareto condition reduces to v(S) > v({i}) ≥ v({j}).Source: A. Proof of Theorem 1 · p. 19
  • The resulting transcendental inequality has no analytical expression, so its satisfying range can be found numerically by plotting both sides against Pe,j,i.The proof then develops a sufficient approximate range instead.Source: A. Proof of Theorem 1 · p. 20
  • By algebraic manipulation, (18) yields a quadratic inequality in Pe,j,i, and the analysis distinguishes two cases according to the sign of D = Pm,i (1 − 2Pm,j).Source: A. Proof of Theorem 1 · p. 20
  • For each sign case, the proof derives a sufficient analytical approximation to the range of reporting-error probabilities satisfying the original inequality.The cases use roots of the quadratic when Pm,j ≤ 1/2 and an analogous approximation when Pm,j > 1/2.Source: A. Proof of Theorem 1 · p. 20
Loading 1010.4501v1…