Multi-scale Spectrum Sensing in Small-Cell mm-Wave Cognitive Wireless Networks
Nicolo Michelusi Matthew Nokleby Urbashi Mitra Robert Calderbank

Weyl Semimetal and Topological Phase Transition in Five Dimensions
    Shou-Cheng Zhang
    December 30, 2023
==================================================================

gobble



In this paper, a multi-scale approach to spectrum sensing in cognitive cellular networks is proposed. 
In order to overcome the huge cost incurred in the acquisition of full network state information, 
a hierarchical scheme is proposed, based on which local state estimates are aggregated up the hierarchy to obtain
aggregate state information at multiple scales, which are then sent back to each cell for local decision making.
Thus, each cell obtains fine-grained estimates of the channel occupancies of nearby cells, but coarse-grained estimates of those of distant cells.
The performance of the aggregation scheme is studied in terms of the trade-off between the throughput achievable by secondary users and the interference
generated by the activity of these secondary users to primary users.
In order to account for the irregular structure of interference patterns arising from path loss, shadowing, and blockages, which are especially relevant in millimeter wave networks,
a greedy algorithm is proposed to find a multi-scale aggregation tree to optimize the performance.
It is shown numerically that  this tailored hierarchy outperforms a regular tree construction by  60%.






§ INTRODUCTION

 The recent proliferation of mobile devices has been exponential
in number as well as heterogeneity <cit.>.
This tremendous increase in demand of wireless services poses severe challenges due to
the finite bandwidth of current systems, and calls for new tools for the design and optimization of agile wireless networks <cit.>. 
Cognitive radio <cit.> has the potential to improve spectral efficiency, by enabling smart terminals (secondary users, SUs) to exploit resource gaps left by legacy, primary users (PUs) <cit.>.

In this paper, we consider a cognitive cellular network, which comprises a set of PUs, which are licensed to access the spectrum, and a set of SUs, which may access opportunistically any unoccupied spectrum. The network is arranged into cells. In each cell, PUs join and leave the channel at random times, thus the state of each cell is described by a first-order binary Markov process.
 In order to utilize the unoccupied spectrum, the SUs require accurate estimates of spectrum occupancies throughout the cellular network. In principle, 
 the channel occupancies can be sensed locally in each cell and collected at a fusion center; the global network state information collected at the fusion center is then broadcasted
 to each cell for
 local decision making. In practice, however, such centralized estimation can be extremely costly in terms of transmit energy and time. 
 

Due to path loss, shadowing, and blockage, SUs accessing the channel in one cell cause significant interference to nearby PUs, but negligible interference to distant PUs. Therefore, each SU needs precise information about the occupancies of nearby cells, but only coarse information about the occupancies of faraway cells.
Given this intuition, we construct a cellular hierarchy, which is used to aggregate channel measurements over the network at multiple scales.
Thus, SUs operating in a given cell have precise knowledge about the local state, aggregate knowledge of the states of the cells nearby,
aggregate and coarser knowledge of the states of the cells farther away, and so on at multiple scales, reflecting the distance dependent nature of wireless interference.



This paper provides important extensions over <cit.>, wherein we assumed a regular tree for hierarchical spectrum sensing by assuming that interference is regular and isotropic (matched to the hierarchy). Herein, we examine the irregular effects of shadowing and blockage, which are
especially severe at millimeter wave frequencies <cit.>. As in <cit.>, we tradeoff SU network throughput versus the interference generated by the SUs to the PUs. To overcome combinatorial complexity, we develop a greedy algorithm to determine the best hierarchical aggregation tree matched to the irregular interference patterns of millimeter wave communications. Optimality is defined in terms of the trade-off between SU network throughput and interference to PUs.  As expected, this tailored hierarchy outperforms the regular tree construction in <cit.> by  60%.  Our methods also apply to sub-6GHz wireless networks and are robust to issues of directionality of interferers and primary receivers.

 Hierarchical estimation was proposed in <cit.> in the context of averaging consensus <cit.>, which is a prototype for distributed, linear estimation schemes. Consensus-based schemes for spectrum estimation have also been proposed in <cit.>.
 In contrast, we focus on a dynamic setting.
  A framework  for joint spectrum sensing and scheduling in wireless networks has been proposed in <cit.>,
 for the case of a single cell. Instead, we consider a network composed of multiple cells.
 
To summarize, the contributions of this paper are as follows.
1) We propose a hierarchical framework for aggregation of channel state information over a wireless network composed of multiple cells,
with a generic interference pattern among cells.
We study the performance of the aggregation scheme in terms of the trade-off between the throughput of SUs and the interference
generated by the activity of the SUs to the PUs.
2) We develop a closed form expression for the belief of the spectrum occupancy vector that shows that this belief is statistically independent across subsets of cells at different levels of the hierarchy,
and uniform within each subset (Theorem <ref>).  This results greatly facilitates the computation of the expected average long-term reward (Lemma <ref>); and 
3) we address the optimal design of the hierarchical aggregation tree so as to optimize performance, for a given
interference pattern; due to the combinatorial complexity of this problem, we propose a greedy algorithm based on 
agglomerative clustering <cit.> (Algorithm <ref>).

This paper is organized as follows. 
In Sec. <ref>, we present the system model.
In Sec. <ref>, we present the performance analysis, for a given tree and interference pattern.
In Sec. <ref>, we address the tree design.
In Sec. <ref>, we present numerical results and, in Sec. <ref>, we conclude this paper.




 




§ SYSTEM MODEL

 
We consider a cognitive network, depicted in Fig. <ref>, composed of a primary cellular network
with N_C cells, and an opportunistic network of SUs.
Cells are indexed as 1,2,…, N_C.
We denote the set of cells as 𝒞≡{1,2,…, N_C}.
The SUs opportunistically access the spectrum so as to maximize their own throughput, under a constraint on the interference caused to the cellular network.


Let b_i,t∈{0,1} be the PU spectrum occupancy of cell i∈𝒞 in slot t. That is, b_i,t=1
if the channel is occupied by PUs in cell i at time t, and b_i,t=0 if it is idle.
We suppose that {b_i,t,t≥ 0,i∈𝒞} 
are i.i.d. across cells, and evolve according to a two-state Markov chain, as a result of PUs joining and leaving the network at random times.
We let 

    p≜ℙ(b_i,t+1=1|b_i,t=0),
    q≜ℙ(b_i,t+1=0|b_i,t=1),

be the transition probability of the Markov chain from "0" to "1" and from "1" to "0", respectively.
Therefore, the steady-state probability that b_i,t is occupied is given by

    π_B≜p/p+q.

We denote the state of the network in slot t as 𝐛_t=(b_1,t,b_2,t,…,b_N_C,t).

The activity of the SUs is represented by the SU access decision a_i,t∈{0,1}, in cell i, slot t,
where a_i,t=1 if the SUs operating in cell i access the channel at time t, and 
a_i,t=0 otherwise.
We denote the network-wide SU access decision as 𝐚_t=(a_1,t,a_2,t,…,a_N_C,t) in slot t.
The activity of the SUs generate interference to the cellular network.
We denote the interference strength between cells i and j as
ϕ_i,j≥ 0. We assume that interference is symmetric, so that ϕ_i,j=ϕ_j,i,∀ i,j∈𝒞.
Note that ϕ_i,i is the  strength of the interference caused by the SUs in cell i to cell i.
We let Φ be the symmetric interference matrix,
with components [Φ]_i,j=ϕ_i,j,∀  i,j∈𝒞.

Given the network state 𝐛_t∈{0,1}^N_C and the SU access decision a_i,t∈{0,1},
we define the local reward for the SUs in cell i as

    r_i(a_i,t,𝐛_t) = a_i,t[ρ_I (1- b_i,t) + ρ_Bb_i,t
    -λ∑_j=1^N_Cϕ_i,jb_j,t].

The term a_i,t(1- b_i,t) in (<ref>) 
equals one if and only if the SUs in cell i access the channel when cell i is idle;
ρ_I≥ 0 is the instantaneous expected SU throughput accrued in this case.
The term a_i,tb_i,t in (<ref>) 
equals one if and only if the SUs in cell i access the channel when cell i is occupied;
ρ_B is the instantaneous expected SU throughput accrued in this case, with 0≤ρ_B≤ρ_I.
Finally, the term

    a_i,t∑_j=1^N_Cϕ_i,jb_j,t

represents the overall interference generated by the
SUs in cell i to the rest of the network, cell i included.
The term λ>0 is a Lagrangian multiplier which captures the trade-off between
the reward for the SU system and the interference generated to the PUs.

The network reward is defined as the aggregate reward over the entire network,
as a function of the SU access decision 𝐚_t and network state 𝐛_t,

    R(𝐚_t,𝐛_t)=∑_i∈𝒞r_i(a_i,t,𝐛_t).


The SU access decision in cell i is decided based on partial network state information,
denoted as π_i,t at time t, where π_i,t(𝐛) is the belief that 
the network state takes value 𝐛_t in slot t, available to SUs in cell i. Given π_i,t,
the SUs in cell i choose a_i,t∈{0,1} so as to maximize the expected reward r_i(a_i,t,π_i,t),
given by

    r_i(a_i,t,π_i,t)≜∑_𝐛∈{0,1}^N_Cπ_i,t(𝐛)r_i(a_i,t,𝐛).

Thus,

    a_i,t^*=max_a∈{0,1}r_i(a,π_i,t),

yielding the optimal expected local reward

    r_i^*(π_i,t)   =max{r_i(0,π_i,t),r_i(1,π_i,t)}
    =max{0,r_i(1,π_i,t)},

where r_i(0,π_i,t)=0 from (<ref>).

Given the belief π_t=(π_1,t,π_2,t,…,π_N_C,t) across the network,
under the optimal SU access decisions 𝐚_t^* given by (<ref>), the optimal network reward is thus given by

    R^*(π_t)=∑_i∈𝒞r_i^*(π_i,t).



Using the fact that r_i(a,𝐛)≤max{r_i(0,𝐛),r_i(1,𝐛)},∀ i∈𝒞,∀ a∈{0,1},∀𝐛∈{0,1}^N_C,
we obtain the inequality 

    R^*(π_t)
       ≤∑_𝐛∈{0,1}^N_Cπ_i,t(𝐛)∑_i∈𝒞max{0,r_i(1,𝐛)},

i.e., the expected network reward under partial network state information is upper bounded
by the expected network reward obtained when full network state information is provided to the SUs in each cell (perfect knowledge of 𝐛_t).
Thus, the SUs should, possibly, obtain full network state information in order to achieve the best performance.

The belief π_i,t is computed based on spectrum measurements performed over the network.
Ideally, in order to achieve global network state information and maximize the reward (see (<ref>)),
the SUs in cell i should obtain the local spectrum state b_i,t, as well as the spectrum state from the rest of the network.
To this end, the SUs in cell j≠i should report the local spectrum state b_j,t to the SUs in cell i via information exchange, potentially over multiple hops, for transmitters/receivers far away from each other.
Since this needs to be done over the entire network (i.e., for every pair (i,j)∈𝒞^2), the associated cost of information exchange may be huge, especially in large networks
composed of a large number of small cells. In order to reduce the cost of acquisition of network state information, in this paper we propose a  
multi-scale approach to spectrum sensing. To this end, we structure the cellular grid in
a hierarchical structure, defined by a tree of depth D≥ 1.




 §.§ Tree construction

Herein, we describe the tree construction.
At level 0, we have the leaves, represented by the cells 𝒞.
We let 𝒞_0^(i)≡{i} for i∈𝒞.
At level 1, let 𝒞_1^(k),k=1,2,…,n_1 be a partition of the cells into n_1 subsets, where 1≤ n_1≤ |𝒞|.
We associate a cluster head to each subset 𝒞_1^(k);
the set of n_1 level-1 cluster-heads is denoted as ℋ_1.
Hence, 𝒞_1^(k)  is the set of cells associated to
the level-1 cluster head k∈ℋ_1.

Recursively, at level L, let ℋ_L be the set of nodes defining the level L-cluster heads,
 with L≥ 1. If  |ℋ_L|=1, then 
 we have defined a tree with depth D=L.
 Otherwise, we define a partition of ℋ_L into
n_L+1 subsets ℋ_L^(k),k=1,2,…,n_L+1,
where 1≤ n_L+1≤ |ℋ_L|,
and we associate to each subset a level-(L+1) cluster head;
the set of n_L+1 level-(L+1) cluster-heads is denoted as ℋ_L+1.
Let 𝒞_L+1^(k),k=1,2,…,n_L+1 be the set of cells associated to level-(L+1) cluster head k∈ℋ_L+1.
This is obtained recursively as

    𝒞_L+1^(k)=⋃_m∈ℋ_L^(k)𝒞_L^(m).


Let P_L(i)∈ℋ_L be the level L parent of cell i,
i.e., P_0(i)=i, and P_L(i)=k for L≥ 1 if and only if i∈𝒞_L^(k), for some k∈ℋ_L.
We make the following definition.
We define
the hierarchical distance between cells i∈𝒞 and j∈𝒞 as

    Λ(i,j)=min{L≥ 0:P_L(i)=P_L(j)}.


In other words, Λ(i,j) is the lowest level L such that cells i and j belong to the same cluster at level L. 
It follows that Λ(i,i)=0 and Λ(i,j)=Λ(j,i), i.e., the hierarchical distance between cell i and itself is 0,
and it is symmetric.

We let 𝒞_Λ^(i)(L) be the set of cells at hierarchical distance L  from cell i.
That is, 𝒞_Λ^(i)(0)≡{i}, and, for L>0,

    𝒞_Λ^(i)(L)≡𝒞_L^(P_L(i))∖𝒞_L-1^(P_L-1(i)).

In fact, by the tree construction, 𝒞_L^(P_L(i)) contains all cells with hierarchical distance (from cell i) less (or equal) than L.
Thus, 𝒞_Λ^(i)(L) is obtained by removing from 𝒞_L^(P_L(i)) all cells  with hierarchical distance less (or equal) than L-1, 𝒞_L-1^(P_L-1(i)).





 §.§ Hierarchical information exchange over the tree


In order to collect network state information at multiple scales, the SUs exchange local information
over the tree.
In particular, we propose a scheme in which the SUs  carry out a hierarchical fusion of local estimates. This fusion is patterned after hierarchical averaging, a technique for scalar average consensus in wireless networks developed in <cit.>.

At the beginning of slot t,
at the cell level (level-0), the local SUs perform spectrum sensing to estimate the local state.
Thus, the SUs in cell i estimate the local state b_i,t as b̂_i,t^(i)∈[0,1], representing the belief that the local state takes the value b_i,t=1, as seen by the SUs operating in cell i (superscript (i)).
For simplicity, in this paper we assume that local spectrum sensing is done with no errors, so that
 
    b̂_i,t^(i)=b_i,t, ∀ i∈𝒞.


Next, these observations are fused up the hierarchy. 
The level 1 cluster head m∈ℋ_1 receives the spectrum measurements from
its cluster 𝒞_1^(m), and fuses them as

    S_m,t^(1)
    =∑_j∈𝒞_1^(m) b_j,t, ∀ m∈ℋ_1.

This process continues up the hierarchy: the level L cluster head 
m∈ℋ_L receives the aggregate spectrum measurements S_k,t^(L-1) from
the level-(L-1) cluster heads k∈ℋ_L-1^(m) connected to it, and fuses them as 

    S_m,t^(L)
    =∑_k∈ℋ_L-1^(m) S_k,t^(L-1)
    =∑_j∈𝒞_L^(m) b_j,t, ∀ m∈ℋ_L.


Eventually, the aggregate spectrum measurements are fused at the unique root of the tree (level D) as

    S_1,t^(D)
    =∑_k∈ℋ_D-1^(1) S_k,t^(D-1)
    =∑_j∈𝒞 b_j,t,

where we have used the fact that 𝒞_D^(1)≡𝒞.


Upon reaching level D,
the appropriate aggregate spectrum measurements are propagated down to the individual cells i∈𝒞, following the tree.
Thus, at the beginning of slot t, the SUs operating in cell i receive 

    {[                  S_P_0(i),t^(0)                               =   ∑_j∈𝒞_0^(P_0(i)) b_j,t=b_i,t,;                  S_P_L(i),t^(L)                               = ∑_j∈𝒞_L^(P_L(i)) b_j,t, 1≤ L<D,;                       S_1,t^(D)                               =                     ∑_j∈𝒞b_j,t, ].

where we remind that P_L(i) is the level-L parent of cell i, and 𝒞_L^(P_L(i)) is the set of cells associated to P_L(i).
That is, the SUs operating in cell i receive from the level-L parent the aggregate spectrum measurements over 𝒞_L^(P_L(i)).
From this set of measurements, one can compute

    {[                                   σ_i,t^(0)                                           ≜                                      b_i,t,;                                   σ_i,t^(L)                                           ≜ S_P_L(i),t^(L)-S_P_L-1(i),t^(L-1), 1≤ L≤ D. ].

Note that σ_i,t^(L) is the aggregate spectrum measurement of the cells at hierarchical distance L from cell i,

    σ_i,t^(L)≜∑_j∈𝒞_Λ^(i)(L)b_j,t, ∀ 0≤ L≤ D.

Thus, the SUs in  cell i receive the set of aggregate spectrum measurements at
multiple scales corresponding to
 different hierarchical distances.
Importantly, they know only the aggregate spectrum measurements, but not the specific values of b_j,t,∀ j≠ i.
These aggregate spectrum measurements are used to update the belief π_i,t in the next section.




§ ANALYSIS

 
 The SUs in cell i update the belief π_i,t based on past and present spectrum measurements
σ_i,τ=(σ_i,τ^(0),σ_i,τ^(1),…,σ_i,τ^(D)),∀ 0≤τ≤ t.
The form of π_i,t is provided by the following Theorem.

 
Given σ_i,t=(o_0,o_1,…,o_D),

    π_i,t(𝐛)=∏_l=0^Dℙ(b_j,t=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,t^(L)=o_L),

independent of σ_i,τ,∀τ<t,
where 

    ℙ(b_j,t=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,t^(L)=o_L)
    
       
    =
    χ(∑_j∈𝒞_Λ^(i)(L)b_j=o_L)
    o_L!(|𝒞_Λ^(i)(L)|-o_L)!/|𝒞_Λ^(i)(L)|!,

where χ(·) is the indicator function. 

 Arxiv

See the Appendix.


Due to space constraints, the proof is in <cit.>.



From Equation (<ref>), it follows that the belief π_i,t is statistically independent 
across the subsets of cells at different hierarchical distances from cell i; this result follows from the fact that
 {b_i,t,t≥ 0,i∈𝒞} are i.i.d. across cells.
 Additionally, since ∑_j∈𝒞_Λ^(i)(L)b_j,t=o_L
 (as a result of state aggregation at hierarchical distance L)
  and b_j,t∈{0,1},
 there are ([ |𝒞_Λ^(i)(L)|;          o_L ])
 possible combinations of {b_j,t,j∈𝒞_Λ^(i)(L)};
 equation (<ref>) states that these combinations are uniformly distributed,
as a result of the i.i.d. assumption.  

Importantly, π_i,t is independent of past measurements but solely depends on the 
current one σ_i,t. In fact, spectrum occupancies b_j,t are 
identically distributed across cells.
 
 We can use Theorem <ref> to compute the expected reward in cell i, given by (<ref>).
Using (<ref>), we obtain

    r_i(a_i,t,π_i,t)=
    ρ_I a_i,t(1- ℙ(b_i,t=1|π_i,t)) 
    
         + ρ_Ba_i,tℙ(b_i,t=1|π_i,t)
    -λ a_i,t∑_j=1^N_Cϕ_i,jℙ(b_j,t=1|π_i,t)
    
       
    =
    ρ_I a_i,t(1- ℙ(b_i,t=1|π_i,t)) + ρ_Ba_i,tℙ(b_i,t=1|π_i,t)
    
         -λ a_i,t∑_L=0^D∑_j∈𝒞_Λ^(i)(L)ϕ_i,jℙ(b_j,t=1|π_i,t).

In the last step above, we have partitioned the set of cells 𝒞 into the 
subsets corresponding to hierarchical distances L=0,1,…,D from cell i.
Now, using (<ref>) in Theorem <ref>, we obtain, for all 0≤ L≤ D,
for all ∀ j∈𝒞_Λ^(i)(L),

    ℙ(b_j,t=1|π_i,t)=0, if o_L=0,
    
       ℙ(b_j,t=1|π_i,t)=
    o_L!(|𝒞_Λ^(i)(L)|-o_L)!/|𝒞_Λ^(i)(L)|!([ |𝒞_Λ^(i)(L)|-1;          o_L-1 ]),
    
                               if o_L>0,

since there are ([ |𝒞_Λ^(i)(L)|-1;          o_L-1 ])
combinations such that b_j,t=1, given that σ_i,t^(L)=o_L.
Solving, we obtain

    ℙ(b_j,t=1|π_i,t)=o_L/|𝒞_Λ^(i)(L)|.

Thus, substituting in (<ref>), and letting

    Φ_i(L)≜∑_j∈𝒞_Λ^(i)(L)ϕ_i,j

be the total interference generated by the SUs in cell i to the cells at hierarchical distance L from cell i,
we can  finally rewrite

    r_i(a_i,t,σ_i,t)=   ρ_I a_i,t(1- σ_i,t^(0)) + ρ_Ba_i,tσ_i,t^(0)
       
    -λ a_i,t∑_L=1^Dσ_i,t^(L)/|𝒞_Λ^(i)(L)|Φ_i(L),

where, for convenience, we have expressed the dependence of r_i(·) on 
σ_i,t, rather than on π_i,t.
Thus, the network reward (<ref>) is given by

    R^*(Σ_t)=∑_i∈𝒞max{0,r_i(1,σ_i,t)},

where we have defined Σ_t=[σ_1,t,σ_2,t,…,σ_N_C,t],
and, for convenience, we have expressed the dependence of R^*(·) on 
Σ_t, rather than on π_t.




 §.§ Average long-term performance evaluation

We are interested in evaluating the average long-term performance of the hierarchical estimation scheme, that is

    R̅=lim_T→∞1/T𝔼[∑_t=0^T-1R^*(Σ_t)],

where the expectation is computed with respect to the sequence {Σ_t,t≥ 0}.
We have the following result.


The average long-term network reward is given by

    R̅=
    ∑_i∈𝒞∑_o_0∈{0,1}ℬ(o_0;1)
    ∑_o_1=0^|𝒞_Λ^(i)(1)|ℬ(o_1;|𝒞_Λ^(i)(1)|)…
       …∑_o_L=0^|𝒞_Λ^(i)(L)|ℬ(o_L;|𝒞_Λ^(i)(L)|)
    …∑_o_D=0^|𝒞_Λ^(i)(D)|ℬ(o_D;|𝒞_Λ^(i)(D)|)
    
       ×max{0,ρ_I(1- o_0) + ρ_Bo_0-λ∑_L=1^Do_L/|𝒞_Λ^(i)(L)|Φ_i(L)
    },

where ℬ(·;|𝒞_Λ^(i)(L)|) is the binomial distribution  with |𝒞_Λ^(i)(L)| trials and occupancy probability π_B,

    ℬ(o_L;|𝒞_Λ^(i)(L)|)
    =([ |𝒞_Λ^(i)(L)|;          o_L ])
    π_B^o_L(1-π_B)^|𝒞_Λ^(i)(L)|-o_L.


In fact, since channel occupancy states are i.i.d. across cells, at steady-state, the number of cells 
occupied
within any subset 𝒞̃⊆𝒞 is a binomial random variable
with |𝒞̃| trials (the number of cells in the set)
and  occupancy probability  π_B (the steady-state probability that one cell is occupied).
The result then follows by applying this argument to the hierarchical aggregation scheme.


Note that R̅ depends on the structure of the tree employed for network state information exchange.
In the next section, we present an algorithm to design the tree so as to maximize the network reward R̅.

Using (<ref>), we  can compare the network reward R̅ with the upper bound computed under the assumption of
full network state information at each cell, given by

    R̅_up=
    ∑_i∈𝒞∑_𝐛∈{0,1}^N_Cπ_B^∑_i b_i(1-π_B)^N_C-∑_i b_i
       ×max{0,ρ_I(1- b_i) + ρ_Bb_i-λ∑_j=1^N_Cϕ_i,jb_j}.






§ TREE DESIGN


 
The reward of the network depends crucially on the tree employed for information exchange. Optimizing the network reward over the set of all possible trees is a combinatorial problem with high complexity. Instead, we employ methods from hierarchical clustering to build a tree.  Hierarchical clustering is well-studied (see, e.g. <cit.>), with two main approaches: divisive clustering, in which a tree is built by successively splitting larger clusters;
and agglomerative clustering, in which a tree is built by successively combining smaller clusters.
Our algorithm is based on the latter.


1em

Agglomerative clustering requires a similarity metric between clusters; at each round, similar clusters are aggregated. Our goal in designing a tree-based approach to spectrum sensing is to prioritize information that nodes can use to limit the interference they generate to other cells. Therefore, we want to aggregate cells together with high potential for interference. To this end, we define the similarity between level-L clusters k_1,k_2∈ℋ_L as

    γ_L(k_1,k_2) = ∑_i ∈𝒞_L^(k_1)∑_j ∈𝒞_L^(k_2)ϕ_i,j,

or the sum of inter-cluster interference strengths. 









The algorithm proceeds as shown in Algorithm <ref>. We initialize it with the N_C leaves 𝒞_0^(i)={i},i=1,2,…,N_C.
 Then, at each level L, we iterate over all of the clusters, pairing each one with the cluster with which it has the most interference
 (this can be done in order of pairs with maximum similarity (<ref>)). 
  This forms the set of level L+1 clusters. If the number of clusters at level L happens to be odd, one cluster may not be paired, in which case it forms its own cluster at level L+1. The algorithm continues until the cluster 𝒞_L^(1) contains the entire network, i.e., a tree is formed.


Agglomerative clustering has complexity O(N_C^2 log(N_C)), where the N_C^2 term owes to searching over all pairs of clusters.





 

§ NUMERICAL RESULTS

  
 In this section, we provide numerical results.
 We consider a 4× 4 cells network. We set the parameters as follows: ρ_I=1, ρ_B=0, λ=1, p=q=0.1.
 We use the following interference model between a pair of cells (assuming there is no blockage between them):
 
    {[ ϕ_i,j=𝐩(i)-𝐩(j)^-α, i≠ j,;                  ϕ_i,i=1, ].

 where 𝐩(i) is the position of cell i, 𝐩(i)-𝐩(j) is the distance between cells i and j,
and  α=2 is the pathloss exponent.







 
 We define random "walls" between cell boundaries, i.i.d. with probability p_block∈[0,1].
 If a wall is present, then all the cells separated by it experience mutual blockage; thus, if cells i and j are separated by a wall,
 then ϕ_i,j=ϕ_j,i=0. The blockage topology is generated randomly, for a given blockage  probability p_block,
 and a sample average of the performance is computed over 200 independent trials.
 
In Fig. <ref>, we plot the curve of the network reward as a function of the blockage probability  p_block, for different schemes:


  * a scheme in which a regular tree is used for state information aggregation. In this case, neighboring cells and clusters are paired together, in order, independently of the interference pattern.
This scheme is similar to <cit.>;

  * a scheme in which the tree is generated with Algorithm <ref>, by leveraging the specific structure of interference;

  * an upper bound in which the reward is computed under full network state information at each cell, given by (<ref>).
This is computed via Monte Carlo simulation over 5000 independent realizations of 𝐛_t (at steady-state).

We notice that the best performance is obtained under full network state information available at each cell. This is because each cell can leverage the most refined information on
the interference pattern. However, this comes at a huge cost of propagating network state information over the network.
 In contrast, the cost of acquisition of state information can be significantly reduced using aggregation, at the cost of some performance degradation.
Remarkably, by using the greedily optimized algorithm for information aggregation, the performance improves by up to 60% with respect to a scheme that uses a regular tree.
 In fact, the greedily optimized algorithm leverages the specific structure of interference over the network.



§ CONCLUSIONS

 
In this paper, we have proposed a multi-scale approach to spectrum sensing in cognitive cellular networks. 
To reduce the cost of acquisition of network state information, 
we have proposed a hierarchical scheme, that makes it possible to obtain aggregate 
state information at multiple scales, at each cell.
We have studied analytically the performance 
 of the aggregation scheme in terms of the trade-off between the throughput achievable by secondary users and the interference
generated by the activity of these secondary users to primary users.
We have proposed a greedy algorithm to find a multi-scale aggregation tree, matched to the structure of interference, to optimize the performance.
Finally, we have shown performance improvement up to 60% using a greedily optimized tree, compared to a regular one.

 Arxiv



§ APPENDIX: PROOF OF THEOREM <REF>


We prove (<ref>) and (<ref>) by induction on t.
At time t=0, given σ_i,0=(o_0,o_1,…,o_D),
using Bayes' rule we obtain

    π_i,0(𝐛)=ℙ(b_j,0=b_j,∀ j|σ_i,0=(o_0,o_1,…,o_D))
    
       
    =
    ℙ(σ_i,0=(o_0,o_1,…,o_D)|b_j,0=b_j,∀ j)ℙ(b_j,0=b_j,∀ j)/𝐛̃∈{0,1}^N_C∑ℙ(σ_i,0=(o_0,o_1,…,o_D)|b_j,0=b̃_j,∀ j)ℙ(b_j,0=b̃_j,∀ j)
    .

Then, noticing that  σ_i,0^(L) in (<ref>)
is only a function of b_j,0,∀ j∈𝒞_Λ^(i)(L), but is independent of 
b_j,0,j∉𝒞_Λ^(i)(L),
and since b_j,0 is statistically independent across cells j,
we obtain

    π_i,0(𝐛)
    
       
    =
    [
    [ ∏_L=0^Dℙ(σ_i,0^(L)=o_L|b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L));                     ×ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)) ]]
    /𝐛̃∈{0,1}^N_C∑[
    [ ∏_L=0^Dℙ(σ_i,0^(L)=o_L|b_j,0=b̃_j,∀ j∈𝒞_Λ^(i)(L));                     ×ℙ(b_j,0=b̃_j,∀ j∈𝒞_Λ^(i)(L)) ]]
    .

Using the fact that {𝒞_Λ^(i)(L),L=0,1,…, D} define a partition of {1,2,…, N_C},
we have that 

    ∑_𝐛̃∏_L=0^D f_L(b̃_j,j∈𝒞_Λ^(i)(L))
    
       =
    ∏_L=0^D∑_b̃_j,j∈𝒞_Λ^(i)(L)f_L(b̃_j,j∈𝒞_Λ^(i)(L)),

for generic functions f_L:{0,1}^|𝒞_Λ^(i)(L)|↦ℝ, hence 
by using this fact in the denominator of (<ref>) we obtain

    π_i,0(𝐛)
    
       
    =
    ∏_L=0^D
    [
    [ ℙ(σ_i,0^(L)=o_L|b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L));              ×ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)) ]]
    /b̃_j∈{0,1},∀ j∈𝒞_Λ^(i)(L)∑[
    [ ℙ(σ_i,0^(L)=o_L|b_j,0=b̃_j,∀ j∈𝒞_Λ^(i)(L));              ×ℙ(b_j,0=b̃_j,∀ j∈𝒞_Λ^(i)(L)) ]]
    .

By Bayes' rule we finally obtain

    π_i,0(𝐛)
    =
    ∏_L=0^D
    ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,0^(L)=o_L),

yielding (<ref>) for t=0.

Note that 

    ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,0^(L)=o_L)
    
       
    =
    [
    [ ℙ(σ_i,0^(L)=o_L|b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L));              ×ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)) ]]
    /b̃_j∈{0,1},∀ j∈𝒞_Λ^(i)(L)∑[
    [ ℙ(σ_i,0^(L)=o_L|b_j,0=b̃_j,∀ j∈𝒞_Λ^(i)(L));              ×ℙ(b_j,0=b̃_j,∀ j∈𝒞_Λ^(i)(L)) ]]
    .

Then, using the definition of σ_i,0^(L) in (<ref>),
and noticing that it is a function of b_j,0,∀ j∈𝒞_Λ^(i)(L),
 we obtain

    ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,0^(L)=o_L)
    
       
    =
    χ(j∈𝒞_Λ^(i)(L)∑b_j=o_L)j∈𝒞_Λ^(i)(L)∏ℙ(b_j,0=b_j)
    /b̃_j∈{0,1},∀ j∈𝒞_Λ^(i)(L)∑χ(j∈𝒞_Λ^(i)(L)∑b̃_j=o_L)j∈𝒞_Λ^(i)(L)∏ℙ(b_j,0=b̃_j)
    .

Note that, if 𝐛 is such that 
j∈𝒞_Λ^(i)(L)∑b_j≠ o_L,
then ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,0^(L)=o_L)=0 as in 
(<ref>). Conversely, if 
j∈𝒞_Λ^(i)(L)∑b_j=o_L,
for all vectors 𝐛̃ such that 
j∈𝒞_Λ^(i)(L)∑b̃_j=o_L
we have that 

    j∈𝒞_Λ^(i)(L)∏ℙ(b_j,0= b_j)=
    j∈𝒞_Λ^(i)(L)∏ℙ(b_j,0=b̃_j),

since b_j,0 are identically distributed. Thus it follows that 

    ℙ(b_j,0=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,0^(L)=o_L)
    
       
    =
    χ(j∈𝒞_Λ^(i)(L)∑b_j=o_L)
    /b̃_j∈{0,1},∀ j∈𝒞_Λ^(i)(L)∑χ(j∈𝒞_Λ^(i)(L)∑b̃_j=o_L)
    
       
    =
    χ(∑_j∈𝒞_Λ^(i)(L)b_j=o_L)
    o_L!(|𝒞_Λ^(i)(L)|-o_L)!/|𝒞_Λ^(i)(L)|!,

since there are ([ |𝒞_Λ^(i)(L)|;          o_L ])
 possible combinations of {b̃_j,j∈𝒞_Λ^(i)(L)}
 such that j∈𝒞_Λ^(i)(L)∑b̃_j=o_L.
This proves (<ref>) for t=0.

Now, let t≥ 1 and assume (<ref>) and (<ref>) hold for t-1.
We show that they hold at time t as well.
We have

    π_i,t(𝐛)=ℙ(b_j,t=b_j,∀ j|σ_i,τ,τ≤ t)
    
       
    =ℙ(b_j,t=b_j,∀ j,σ_i,t=(o_0,o_1,…,o_D)|σ_i,τ,τ≤ t-1)
    /∑_𝐛̃ℙ(b_j,t=b̃_j,∀ j,σ_i,t=(o_0,o_1,…,o_D)|σ_i,τ,τ≤ t-1)
    
       
    =[
    [ ℙ(σ_i,t=(o_0,o_1,…,o_D)|b_j,t=b_j,∀ j);         ×ℙ(b_j,t=b_j,∀ j|σ_i,τ,τ≤ t-1) ]]
    /∑_𝐛̃[
    [ ℙ(σ_i,t=(o_0,o_1,…,o_D)|b_j,t=b̃_j,∀ j);         ×ℙ(b_j,t=b̃_j,∀ j|σ_i,τ,τ≤ t-1) ]]
    ,

where we have used Bayes' rule. Using the fact that 
σ_i,t^(L) in (<ref>)
is a function of b_j,t,∀ j∈𝒞_Λ^(i)(L), we then obtain

    π_i,t(𝐛)
    =[
    [ ∏_L=0^Dχ(j∈𝒞_Λ^(i)(L)∑b_j=o_L); ×ℙ(b_j,t=b_j,∀ j|σ_i,τ,τ≤ t-1) ]]
    /∑_𝐛̃[
    [ ∏_L=0^Dχ(j∈𝒞_Λ^(i)(L)∑b̃_j=o_L); ×ℙ(b_j,t=b̃_j,∀ j|σ_i,τ,τ≤ t-1) ]]
    .


Note that, since {b_j,t,t≥ 0} is a Markov chain, we obtain

    ℙ(b_j,t=b_j,∀ j|σ_i,τ,τ≤ t-1)
    
       
    =
    ∑_𝐛̂ℙ(b_j,t=b_j|b_j,t-1=b̂_j,∀ j)π_i,t-1(𝐛̂)
    
       
    =
    ∑_𝐛̂π_i,t-1(𝐛̂)
    ∏_L=0^D
    ∏_j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_j|b_j,t-1=b̂_j),

where

    π_i,t-1(𝐛̂)=ℙ(b_j,t-1=b̂_j,∀ j|σ_i,τ,τ≤ t-1).

In the last step of (<ref>), we have used the fact that 
{b_j,t} are statistically independent across cells, and that 
{𝒞_Λ^(i)(L),L=0,1,…, D} define a partition of {1,2,…, N_C}.

Now, using the induction hypothesis, 
we can express π_i,t-1 using (<ref>), hence

    ℙ(b_j,t=b_j,∀ j|σ_i,τ,τ≤ t-1)
    
       =
    ∏_L=0^D
    ∑_b̂_j,j∈𝒞_Λ^(i)(L)∏_ j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_j|b_j,t-1=b̂_j)
    
       ×ℙ(b_j,t-1=b̂_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,t-1^(L)=ô_L),

where we used (<ref>).
Then, using (<ref>)
to express ℙ(b_j,t-1=b̂_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,t-1^(L)=ô_L) 
and substituting the resulting expression in (<ref>), we obtain

    π_i,t(𝐛)
    
       =∏_L=0^D
    [[ b̂_j,j∈𝒞_Λ^(i)(L)∑χ(j∈𝒞_Λ^(i)(L)∑b_j=o_L,
    j∈𝒞_Λ^(i)(L)∑b̂_j=ô_L);                        ×∏_ j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_j|b_j,t-1=b̂_j) ]]
    /[[ b̂_j,b̃_j,j∈𝒞_Λ^(i)(L)∑χ(j∈𝒞_Λ^(i)(L)∑b̃_j=o_L,j∈𝒞_Λ^(i)(L)∑b̂_j=ô_L);                            ×∏_ j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b̃_j|b_j,t-1=b̂_j) ]]
    .


Note that, for any 𝐛 and 𝐛̃,
and for any permutation P(·):𝒞_Λ^(i)(L)↦𝒞_Λ^(i)(L) of the elements in the set 𝒞_Λ^(i)(L),
we have

    ∏_j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_j|b_j,t-1=b̂_j)
    
       
    =
    ∏_j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_P(j)|b_j,t-1=b̂_P(j)),

since b_j,t are statistically identical across cells.

Thus,
for any 𝐛 and 𝐛̃ such that 

    j∈𝒞_Λ^(i)(L)∑b_j=j∈𝒞_Λ^(i)(L)∑b̃_j=o_L,

we obtain

    ∏_j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_j|b_j,t-1=b̂_j)
    
       
    =
    ∏_j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b̃_j|b_j,t-1=b̂_P(j)),

where P(·) is a proper permutation which maps b_j to b̃_j,∀ j∈𝒞_Λ^(i)(L).
The existence of such permutation is guaranteed by the condition (<ref>),
since {b_j,j∈𝒞_Λ^(i)(L)} and {b̃_j,j∈𝒞_Λ^(i)(L)} have the same number of zero and non-zero elements.

Therefore, for any 𝐛 and 𝐛̃ satisfying (<ref>),

    b̂_j,j∈𝒞_Λ^(i)(L)∑χ(∑_j∈𝒞_Λ^(i)(L)b̂_j=ô_L)∏_ j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b̃_j|b_j,t-1=b̂_j)
    
       
    =
    b̂_j,j∈𝒞_Λ^(i)(L)∑χ(∑_j∈𝒞_Λ^(i)(L)b̂_P(j)=ô_L)∏_ j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b̃_j|b_j,t-1=b̂_P(j))
    
       
    =b̂_j,j∈𝒞_Λ^(i)(L)∑χ(∑_j∈𝒞_Λ^(i)(L)b̂_j=ô_L)∏_ j∈𝒞_Λ^(i)(L)ℙ(b_j,t=b_j|b_j,t-1=b̂_j),

where in the last step we have used the fact that 
the sum over 
{b̂_j,j∈𝒞_Λ^(i)(L)}
covers the same set of elements as
the sum over the set with permuted entries,
{b̂_P(j),j∈𝒞_Λ^(i)(L)}.

Finally, substituting in (<ref>) we obtain

    π_i,t(𝐛)
    =
    ∏_L=0^D
    χ(j∈𝒞_Λ^(i)(L)∑b_j=o_L)
    /b̃_j,j∈𝒞_Λ^(i)(L)∑χ(j∈𝒞_Λ^(i)(L)∑b̃_j=o_L)
    .

Note that this expression implies that 
π_i,t(𝐛) is only a function of  σ_i,t but is independent of σ_i,τ,τ≤ t-1;
additionally, {b_j,j∈𝒞_Λ^(i)(L_1)} is statistically independent of 
{b_j,j∈𝒞_Λ^(i)(L_2)} for L_1≠ L_2, given σ_i,t.
Thus, (<ref>) follows, where
ℙ(b_j,t=b_j,∀ j∈𝒞_Λ^(i)(L)|σ_i,t^(L)=o_L) is given as in 
(<ref>).
Finally, (<ref>) follows from (<ref>)-(<ref>).

The induction step, and the Theorem, are thus proved.






 

IEEEtran
 

