by user

Category: Documents






Zhi Tian*
Geert Leus†
Vincenzo Lottici‡
Dept. of Electrical & Computer Engineering, Michigan Technological University, Houghton, MI, USA
Faculty of Electrical Engineering, Delft University of Technology, Delft, The Netherlands
Department of Information Engineering, University of Pisa, Pisa, Italy
This paper discusses the issue of dynamic resource allocation (DRA)
in the context of cognitive radio (CR) networks. We present a general framework adopting generalized transmitter and receiver signalexpansion functions, which allow us to join DRA with waveform
adaptation, two procedures that are currently carried out separately.
Moreover, the proposed DRA can handle many types of expansion
functions or even combinations of different types of functions. An iterative game approach is adopted to perform multi-player DRA, and
the best-response strategies of players are derived and characterized
using convex optimization. To reduce the implementation costs of
having too many active expansion functions after optimization, we
also propose to combine DRA with sparsity constraints for dynamic
function selection. Generally, it incurs little rate-performance loss
since the effective resources required by a CR are in fact sparse.
Index Terms— cognitive radio, dynamic resource allocation,
game theory, waveform adaptation, sparsity
In cognitive networks, radios dynamically decide the allocation of
available radio resources to improve the overall utilization efficiency,
also known as dynamic resource allocation (DRA) [1]. In view of
the competitive nature of a resource-constrained multi-user system,
DRA can be carried out in a distributed fashion using multi-player
games [2, 3]. In that case, every radio will iteratively sense the available resources and adjust its own usage of these resources accordingly. Such resources could for instance be represented by transmitter and receiver signal-expansion functions, which can be judiciously
chosen to enable various radio platforms, such as frequency, time, or
code division multiplexing (FDM, TDM, CDM). While an OFDM
platform with carriers has been generally considered for CRs [4],
many platforms are TDM- or CDM-based and make use of different
types of expansion functions such as pulses, codes, or wavelets.
This paper presents a general DRA approach that allows us to
handle and even combine all kinds of expansion functions. This
signal expansion framework also enables us to combine DRA with
waveform adaptation [7, 8], two operations that are generally carried
out separately. The joint treatment is essential in implementing practical iterative DRA games that require dynamic interference sensing.
Finally, when some fixed type of expansion functions is used
to represent the dynamic resource opportunities in the wideband
regime, the optimal number of active expansion functions could
Zhi Tian is supported in part by the NWO-STW under the work visit
program (DTC.7800), and by the US NSF grant #CCF-0238174. Geert Leus
is supported in part by NWO-STW under the VIDI program (DTC.6577).
1-4244-1484-9/08/$25.00 ©2008 IEEE
be huge, leading to highly complex iterative games with slow convergence. To solve this problem, we will incorporate some proper
sparsity constraints in the DRA games to limit the number of active expansion functions. The dynamic function selection strategy,
coupled with a set of redundant expansion functions as the selection
base, may reduce the implementation costs at little performance
loss, with improved convergence in the iterative games. Simulation
results are provided to illustrate the proposed techniques.
Consider a wireless network with Q active CR users seeking radio
resources, where each CR refers to a pair of one transmitter and one
receiver. In this paper, the resources are represented by means of
a set of transmitter and receiver functions/filters {ψk (t)}K−1
k=0 and
{φk (t)}K−1
k=0 . Through block transmission, CR q transmits a K × 1
coded data vector uq = Fq sq in each block, where sq consists of
K i.i.d. information symbols {sq,k }K−1
k=0 , and Fq is a square linear
precoding matrix. Inter-block interference (IBI) can for instance be
avoided by the use of a cyclic prefix, as we will illustrate later. The
data uq,k are communicated using the transmitter expansion
ψk (t), yielding the transmitted waveform uq (t) = k uq,k ψk (t).
The CR sends uq (t) over a dispersive channel with impulse
response gq (t), and preprocesses it at the receiver using the receiver functions {φk (t)} to collect a block of K data samples
xq := [xq,0 , . . . , xq,K−1 ]T . Each CR pair is assumed to be synchronized, but different CRs do not have to be synchronized among
one another. Hence, the discrete-time input-output relationship is
xq = Hq uq + vq
channel matrix with its (k, l)-th
where Hq is the K × K aggregate
element given by hq,k,l := gq (t) ψk (t) φR∗l (−t)dt, ∀k, l, and
vq is the K × 1 filtered noise vector with vq,l = vq (t) φ∗l (−t)dt.
The above setup incorporates FDM, TDM, as well as CDM scenarios. For example, in a baseband digital implementation, the set of
transmitter and receiver functions can be chosen as:
ck,<n−N>K p(t − nT ),
ψk (t) = √K+N
φl (t) = √1K n=N
ck,n−N p(t − nT ),
where {ck,n }k,n represent the digital modulation/demodulation coefficients, < n >K denotes the remainder after dividing n by K, and
p(t) is the normalized pulse used at the DAC and ADC. It is assumed
that p(t) has a span [0, T ) and an essential bandwidth [−B/2, B/2)
(B = 1/T ). Here, the considered range is t ∈ [0, (K + N )T ),
where N T is an upper bound on the length of any channel gq (t).
We have assumed that the transmit functions ψk (t) include a cyclic
prefix of length N T , and that the receive functions φk (t) remove
this cyclic prefix. That way IBI is avoided. In FDM, we could
, whereas in TDM, we could take ck,n =
√ ck,n = e
Kδk−n . Note that the above described FDM scheme actually corresponds to OFDM (orthogonal frequency division multiplexing),
whereas the TDM scheme actually corresponds to SCCP (single carrier with a cyclic prefix). CDM covers intermediate schemes, where
the functions {ψk (t)}k and {φk (t)}k could for example be related to
spreading codes or wavelets. Also combinations of the above waveforms can be considered, as we will discuss later on.
DRA in a CR network concerns the spectrum utilization efficiency, measured for instance by the system capacity. DRA can be
amplicarried out through the linear precoder Fq and a length-K
tude scaling vector aq , whose k-th element is aq,k = E(|sq,k |2 ).
Given the signal expansion structure and assuming uncorrelated interferences on the different waveforms {φk (t)}k , the per-user capacity formula is given by
log2 ˛IK + diag(aq )FH
C(aq , Fq ) =
q Bq Fq diag(aq )˛
where Bq := HH
q Rq Hq and Rq := E(vq vq ) is the interference
covariance matrix. We have omitted the impact of data detection,
since the MMSE receiver is known to be capacity-preserving [9]. We
assume that the knowledge of Hq and Rq , and thus Bq , is known to
CR q, using some channel and interference estimation techniques [9].
In CR applications, the spectral shapes of transmitted waveforms
need to comply with some design and regulatory requirements. For
CR q, the PSD of the transmitted signal uq (t) is given by
2 ˛
Sq (f ; aq , Fq ) = K−1
k=0 aq,k ˛
i=0 [Fq ]i,k ψi (f )˛ .
Hence, the average power constraint can be expressed as
Sq (f ; aq ,Fq )df = tr diag(aq )FH
q Sψ Fq diag(aq ) ≤ Pq,max
where Pq,max
R is the ∗power upper limit, Sψ is the K × K matrix with
[Sψ ]k,l = ψk (f )ψl (f )df , and tr(·) denotes trace.
We further impose a cognitive spectral mask Sc (f ) that accounts
for government spectral regulations and cognition-based frequency
notch masks for interference control. The spectral mask constraint is
Sq (f ; aq , Fq ) ≤ Sc (f ),
∀f, q.
3.1. Distributed Game Formulation and Implementation
In a DRA game, CRs are game players, each of which seeks to maximize a capacity-related utility function by taking allocation actions
on (aq , Fq ) from its own set of permissible strategies. A standard
non-cooperative game can be formulated as
aq 0,Fq
C(aq , Fq ),
s.t. (5), (6).
On a per-user basis, (8) presents a decentralized DRA formulation
for deciding (aq , Fq ), without knowledge of other users’ allocation {(ar , Fr )}r=q . Nevertheless, the interference Rq needs to be
sensed, while the sensing task needs to be carried out when other
users are transmitting using their allocation {(ar , Fr )}r=q . The intricacy among sensing, transmission and distributed DRA suggests
a repeated game approach, in which players repeat the optimization
in (8) multiple rounds, until reaching steady-state DRA decisions, if
existent. Steps in an iterative game are summarized below.
S1) In current round, choose the order for CRs to take actions, in
a sequential, simultaneous, or asynchronous fashion [11];
S2) For CR q that is in order to take its action,
(a) senses the channel and interference Hq and Rq ,
(b) finds the current best response strategy (aq , Fq ) that
optimizes (8), which we will elaborate in Section 4,
(c) adapts its transmission by implementing (aq , Fq ) on
the signal expansion functions;
S3) iterate to the next round, until convergence.
This game procedure joins the two tasks of DRA optimization
(in S2(b)) and online waveform adaptation (in S2(c)), thanks to the
enabling signal expansion framework we adopt. By doing so, it is
feasible for CRs to perform dynamic sensing of the aggregate interference (in S2(a)). In contrast, existing DRA literature mainly focuses on direct optimization of the power spectrum Sq (f ) based on
proper spectrum efficiency criteria [2, 3], while the waveform design
literature investigates analog or digital pulse shaping techniques to
comply with the allocated power spectrum Sq (f ) [7, 8]. The separate approach to DRA and waveform design requires that each CR
estimates and exchanges the information of all the received interfering channels (with the exception of OFDM systems which is a
special case herein), incurring considerable overhead in signaling,
communication and computation. Our DRA approach offers a truly
distributed framework in which the allocation actions are optimized
under a practical transmitter implementation structure.
3.2. Game Characterization
From a global network perspective, the objective of DRA is to determine the collective actions {(aq , Fq )}Q−1
q=0 that maximize the sumrate of all users, that is,
{aq 0}q ,{Fq }q
C(aq , Fq ),
s.t. (5), (6), ∀q.
Here we do not optimize the expansion functions, but nevertheless
jointly adapt the waveforms Sq (f ; aq , Fq ) during DRA on (aq , Fq ).
However, the formulation (7) leads to a centralized non-convex
optimization problem with NP-hard complexity [3]. Furthermore,
it requires knowledge of all the channel information {Rq , Hq }q ,
which can be infeasible to obtain even for a central spectrum controller such as a base station. For any-to-any connections, it is more
appropriate to perform decentralized DRA, for which the gametheoretic approach is well motivated due to its distributed nature.
In game theory, it is essential to characterize the properties of steady
state Nash Equilibriums (NEs) in order to assess the game outcomes.
Relevant issues include the existence, optimality, uniqueness of NEs,
and whether a game implementation converges to the NEs.
The noncooperative game in (8) can be shown as a convex optimization problem. The utility is continuously quasi-concave, while
the action space defined by the power and mask constraints is a nonempty compact convex set. As such, the Glicksberg-Fan fixed point
theorem ensures the existence of NEs by pure strategies [11].
In Section 4, we will show that the matrix-valued problem in
(8) can be transformed into a vector-valued convex problem with
a diagonalized channel structure. As such, it resembles a standard
OFDM-based game based on orthogonal carriers. For synchronous
OFDM systems that appear in DSL applications, sufficient conditions for uniqueness have been delineated under the power and mask
constraints [4, 6]. For the mask-constrained asynchronous case we
consider here, the uniqueness of the NE is still an open problem [5].
4.2. Reduced-cost DRA under Sparsity Constraints
This section solves for the best responses to the per-user optimization problem in (8). The characteristic of the best response strategies
affects the NE properties of the corresponding game.
4.1. Convex Formulation and Water-filling Interpretation
To deal with the pulse-shaping autocorrelation matrix Sψ in (5), we
define F̄q := Λs UH
s Fq , where Us and Λs are the eigenvector
and eigenvalue matrices of Sψ respectively. Rewriting the power
constraint as tr(diag(aq )F̄H
q F̄q diag(aq )) ≤ Pq,max , and using the
Hadamard inequality, we deduce that the determinant in (3) is max−1/2 H
Us Bq Us Λs
. Let
imized when F̄q diagonalizes B̄q := Λs
Uq and Λq denote the eigenvector and eigenvalue matrices of B̄q ,
respectively. This suggests setting F̄q = Uq and Fq := Us Λs Uq ,
which yields
C(aq ) := max C(aq , Fq ) =
log2 ˛IK + Λq diag(aq )2 ˛
a2q,k λq,k ), λq,k := [Λq ]k,k . (9)
= K
Let us define an K × 1 power loading vector pq : pq,k := a2q,k .
Since FH
q Sψ Fq = F̄q F̄q = I, the power constraint in (5) becomes
1T pq ≤ Pq,max .
Meanwhile, the transmitted PSD in (4)
˛Pcan be re-written ˛as
Sq (f ; pq ) = zq (f )pq , where [zq (f )]k := ˛ K−1
i=0 [Fq ]i,k ψi (f )˛ .
To render the number of spectral mask constraints finite, we sample
Sq (f ; pq ) uniformly in frequency at N points FN := {f1 , . . . , fN },
N ≥ K, and replace (6) by
ZTq,N pq ≤ Sc,N ,
Sc,N := [Sc (f1 ), . . . , Sc (fN )]T ,
where Zq,N := [zq (f1 ), . . . , zq (fN )] is an N × K matrix.
The per-user DRA optimization problem in (8) can now be simplified by (9), (10) and (11) into
maxpq 0
1 X
C(pq ) =
log2 (1 + pq,k λq,k )
K k=0
1T pq ≤ Pq,max
pq ≤ pq,max ,
pq,max := Z†q,N Sc,N .
Interestingly, the matrix-valued DRA problem in (8) with respect
to (aq , Fq ) has been reformulated into a vector-valued problem in
(12) with respect to pq . The best response to (12) is the well-known
water-filling scheme [2, 4, 6], that is,
˜pq,max (k)
pq : pq,k = μq − λ−1
Fq = Us Λ1/2
s Uq ,
q,k 0
where [x]ba is the Euclidean projection of x onto [a, b] and the water
level μq is chosen to satisfy K−1
k=0 pq,k = Pq,max as in (12b) [4].
Remark 1: In [4], a noncooperative game is proposed using linear
precoding strategies under both power and spectral mask constraints.
The schemes therein require block-by-block synchronization among
users, whereas this paper obviates this assumption. In [9], a filterbank structure is proposed for transceiver optimization, whereas our
expansion functions are not confined to be mutually orthogonal. The
capability in subsuming various types of expansion functions offers
added flexibility in re-shaping the dispersive channels. Even though
these expansion functions are fixed in this paper for simplicity, we do
allow for redundant non-orthogonal functions to explore the sparsity
property in CR networks, as discussed next.
In order to represent the optimal transmitted PSD over a very wide
band, the required number of expansion functions can generally be
very large. On the other hand, the effective resources needed for a
CR to transmit reliably are in fact sparse compared with the total
available resources in the wideband network. This observation suggests that (near-)optimal DRA may be carried out over a few selected
expansion functions. Function selection also reduces hardware costs.
4.2.1. Function Selection Formulation
Suppose that each CR transmits data over M expansion functions,
M < K. Functions are selected via a selection matrix Jq = diag(jq )
where jq ∈ {0, 1}K is a K ×1 sequence indicating whether ψq,k (t)
is selected (‘1’) or not (‘0’). Removing those all-zero columns in Jq ,
we get J̃q of size K × M . DRA are performed on the M selected
functions, via an M ×1 loading vector ãq = J̃H
q aq and an M ×M
precoder F̃q = J̃H
q Fq J̃q . The aggregated channel effect is captured
in B̃q = J̃H
q Bq J̃q , and the capacity formula in (3) is modified to
C(aq ,Fq ,Jq ) = log2 ˛IM +diag(ãq )F̃H
q B̃q F̃q diag(ãq )˛ . (14)
Replacing the utility function in (8) by (14), we reach a DRA game
with dynamic function selection. It resembles the antenna selection
problem in MIMO literature [12, 13], which is known to be NP-hard
due to its combinatorial optimization nature. To bypass the difficulty,
we resort to a suboptimal two-stage approach to separately treat the
filter selection problem and the DRA problem, as follows.
s1) decide jq using fast antenna selection schemes, e.g., [12, 13];
s2) find the best response to (14) on the selected filters, using the
formulation in (12) and the solution in (13).
These two stages are carried out in Step S2(b) in Section 3.
4.2.2. Sparsity-Constrained DRA Formulation
Selecting M functions is equivalent to setting (K − M ) elements
of the allocation vector aq to be zeros, that is, ||aq ||0 = M . When
M K, aq becomes a sparse vector, which can be treated under the
framework of compressive sampling [10]. A general-form sparsity
measure of aq is its l-norm ||aq ||l , where 0 ≤ l < 2. We now tackle
the function selection problem by introducing sparsity constraints.
In the absence of linear precoding, function selection boils down
to limiting the l-norm of aq by an upper bound Lq,max . Adding this
sparsity constraint to (8), we merge DRA with function selection:
maxaq 0
C(aq , Fq = IK )
(5), (6);
||aq ||l ≤ L(l)
q,max .
When l = 0, the parameter Lq,max directly reflects the number of
functions selected, but (15) is nonconvex and difficult to solve. When
l ∈ [1, 2), (15) is a convex problem that permits well-behaved nu(l)
merical algorithms. However, the parameter Lq,max is more difficult
to choose in order to produce exact sparsity.
When linear precoding is present (Fq = IK ), we note from (9)
that the linear precoder F̄q serves to diagonalize the channel B̄q ,
while the ensuing power loading in (12) is determined by the channel eigenvalues Λq . This observation suggests to perform function
selection by finding a primary minor channel matrix
B̃q with the
˛ best
eigenvalue quality measured by |IM + B̃q | = ˛IK +JH
q B̄q Jq , i.e.,
||jq ||l ≤ L(l)
− jp,k = 0, k = 0, . . . , K − 1 (16c)
eTk Jq ek = jq,k , k = 0, . . . , K − 1
eTk Jq el
= 0,
∀k = l
where ek denotes the k-th column of the identity matrix IK , ∀k.
Here, (16c) is imposed to enforce jq,k ∈ {0, 1}, and (16d) and (16e)
are used together to express the relationship Jq = diag(jq ) as the
intersection of a set of convex functions in jq and Jq . Relaxing l
to be l = 1, (16) becomes a convex problem that obviates undesired
combinatorial search. The optimized selection decision jq replaces
the first stage s1) in Section 4.2.1. Afterwards, DRA is carried out
on the M functions using (14), in which the linear precoder B̃q can
diagonalize the channel to simplify (14) to a water-filling scheme.
Remark 2: It is interesting to observe that our DRA problem based
on the signal expansion framework resembles the multiuser MIMO
problems. Expansion functions play the roles of transmit and receive
antennas, corroborated by the capacity formula (3) that applies to
both problems. Hence, the literature on multiuser MIMO can benefit our work and from our work as well. Nevertheless, our design
focus is to perform efficient resource allocation rather than harvesting antenna diversity and multiplexing gains. As such, we may use
a large number of expansion functions to induce redundancy in resource representation, followed by dynamic function selection to allocate resources efficiently at reduced implementation costs. In this
sense, our theme departs from that of multiuser MIMO problems.
Besides, channel estimation is an easier task in our problem, allowing possibly compressed sensing at reduced sampling rates.
Consider a Q-user peer-to-peer CR network. Each channel link experiences frequency-selective fading modeled by an Nt -tap tapped
delay line, where each tap coefficient is complex Gaussian with zeromean and unit variance. The link power gain is denoted by a scalar
ρrq > 0, ∀r, q ∈ [1, Q], which captures both the path loss and the
fading power. Subsequently, the interference covariance matrix Rq
is given by the covariance of the aggregated interference (from all
the Q−1 received interference channels) plus noise. We set Q = 4,
Pq,max = 20 (with reference to unit noise variance), ρqq = 1, ∀q,
and ρrq = 8 for ∀r = q. FDM subcarriers are used as the transmitter
and receiver functions, with K = 32 subcarriers.
To demonstrate the inherent sparsity in the CR context, we compare three DRA techniques: i) DRA via (8) without function selec(0)
tion; ii) DRA via (14) performed over a fixed selection of Lq,max =
M functions; and, iii) DRA with dynamic function selection via (15)
under sparsity constraints on the l-norm, for l = 0.2 and l = 1.
Fig. 1(a) depicts the sum capacity of all users versus the sparsity
parameter Lq,max , averaged over 100 sets of channel realizations.
When the sparsity constraints in ii) and iii) are loose, all DRA designs converge to the same C(pq ) of the sparsity-unconstrained design i), indicated by the rightmost region in Fig. 1(a). In design ii), as
M decreases, the sparsity constraints becomes tighter, and the resulting capacity exhibits a noticeable gap from that of i). This indicates
that a fixed function selection cannot efficient allocate resources in
dynamic channel environments. In contrast, the sparsity-constrained
DRA designs in iii) result in average capacities close to that in i),
because iii) optimally selects active expansion functions where the
effective resources lie on dynamically.
In terms of the sparsity metric, the l0 -norm constraint directly
controls the exact sparsity, but incurs combinatorial computational
load. When l is close to 0, e.g., l = 0.2, the optimal solution closely
approximates a sparse representation. However, l < 1 results in a
nonlinear concave constraint and is thus subject to convergence issues. For l ≥ 1, the sparsity constraint becomes convex. However,
as l increases, the resulting allocation tends to be less sparse. The
assessment on the average complexity is corroborated in Fig. 1(b).
[1] “Facilitating Opportunities for Flexible, Efficient, and Reliable Spectrum Use Employing Cognitive Radio Technologies,”
FCC Report and Order, FCC-05-57A1, March 2005.
[2] W. Yu, W. Rhee, S. Boyd and J. Cioffi: “Iterative Water-filling
for Gaussian Vector Multiple Access Channels,” IEEE Trans.
on Information Theory, vol. 50, no. 1, pp.145-151, Jan. 2004.
[3] J.Huang, R. Berry and M. L. Honig, “Distributed interference
compensation for wireless networks,” IEEE J. on Selected Areas in Communi., vol. 24, No. 5, pp. 1074-1084, May 2006.
[4] G. Scutari, D. P. Palomar, and S. Barbarossa, “Asynchronous iterative waterfilling for Gaussian frequency-selective channels,”
Proc. of IEEE SPAWC Conf., Cannes, France, July 2006.
[5] G. Scutari, D. P. Palomar, and S. Barbarossa, “Competitive Design of Multiuser MIMO Interference Systems Based on Game
Theory,” Proc. of IEEE ICASSP, April 2008.
[6] Z.-Q. Luo, J.-S. Pang, “Analysis of Iterative Waterfilling Algorithm for Mul- tiuser Power Control in Digital Subscriber
Lines,” EURASIP JASP Vol. 2006, Article ID 24012, 2006.
[7] J. G. Proakis, and D. G. Manolakis, Digital Signal Processing:
Principles, Algorithms and Applications, Macmillan, 1996.
[8] X. Wu, Z. Tian, T. N. Davidson, and G. B. Giannakis, “Optimal waveform design for UWB radios,” IEEE Trans. on Signal
Processing, vol. 54, no. 6, pp. 2009-2021, June 2006.
[9] A. Scaglione, G. B. Giannakis, and S. Barbarossa, “Redundant
Filterbank Precoders and Equalizers,” IEEE Trans. on Signal
Processing, vol. 47, no. 7, pp. 1988-2006, July 1999.
[10] D. L. Donoho, “Compressed Sensing,” IEEE Trans. on Information Theory, vol. 52, pp. 1289-1306, April 2006.
[11] D. Fudenberg, J. Tirole, Game Theory, MIT Press, 1991.
[12] A. Gorokhov, D. A. Gore, and A. J. Paulraj, “Receive Antenna
Selection for MIMO Spatial Multiplexing”, IEEE Trans. on
Signal Processing, vol. 51, no. 11, Nov. 2003.
[13] M. Gharavi-Alkhansari, and A. B. Gershman, “Fast Antenna
Subset Selection in MIMO Systems,” IEEE Trans. on Signal
Processing, vol. 52, no. 2, Feb. 2004.
(i) unconstrained
(ii) fixed sparsity
(iii), small norm (l=0.2)
(iii), 1−norm (l=1)
sparsity bound (Lmax)
sum sparsity (0−norm)
log2 ˛IK + JH
q B̄q Jq ˛
sum Capacity
maxjq 0
(i) unconstrained
(ii) fixed sparsity
(iii), small norm (l=0.2)
(iii), 1−norm (l=1)
sparsity bound (Lmax)
Fig. 1. Sparsity-constrained DRA: (a) average sum capacity, (b) average sum complexity measured by l0 -norm.
Fly UP