2011 IEEE 22nd International Symposium on Personal, Indoor and Mobile Radio Communications

Performance based Channel Allocation
in IEEE 802.22 Networks
Saptarshi Debroy Shameek Bhattacharjee and Mainak Chatterjee
Department of Electrical Engineering & Computer Science
University of Central Florida
Orlando, FL 32816
Email: {saptarsh.shameek.mainak}@eecs.ucf.edu

Abstract-The main challenge in resource allocation in cogni­
tive radio based IEEE 802.22 networks is the absence of pre­defined control channels. Moreover, the fleeting nature of theavailable spectrum also hinders the communication as the radios
must relinquish the acquired channels once the primary users of
those channels return.
In this paper, we propose a performance metrics based datachannel allocation scheme for IEEE 802.22 networks where thebase station allocates interference free channels to the consumer
premise equipments using a spectrum map. The base station
creates the spectrum map by using the raw spectrum usage
data that are shared by a small subset of consumer premise
equipments. The usage data are fused at the base station usinga modified version of Shepard's interpolation technique. We
construct a continuous and differentiable spatial distribution ofspectrum usage that the base station consults to estimate thespectrum occupancy vector at any arbitrary location in its cell.
Such spectrum usage is then utilized to proactively evaluate somekey network and radio performance metrics which in turn help
allocating the best candidate channel to a given consumer premise
equipment ensuring highest achievable performance.

I.

INTRODUCTION

The IEEE 802.22 wireless regional area network(WRAN) [2] is a cognitive radio based technology [3]that exploits the unused sub-900 MHz bands. These bands areprimarily owned and licensed by TV stations (primary users).
The core components of an IEEE 802.22 network, basestations (BS) and the consumer premise equipments (CPE),
continuously scan the entire spectrum and opportunisticallyaccess the unused or underutilized TV bands. Channel
allocation to the CPEs are done by the BS. Upon detectionof any transmission activity from a primary user on thechannels being used, the secondary users are mandated torelinquish those channels [1]. The ability of the BS to assign
the best possible channels to the CPEs depends on how wellthe BS is able to capture the spectrum availability at thevarious CPE locations. Since the BS cannot perform sensing
at locations other than itself, it has to rely upon the sensed
spectrum reports shared by the CPEs. If all the CPEs were
to continuously share their spectrum usage reports, the BS
would have the most accurate information. However, thecommunication overhead becomes a bottleneck as sharingof data has to be done on the same channels that the BS isThis research was sponsored by National Science Foundation, under award
no.CCF-0950342.

978-1-4577-1348-4/11/$26.00 ©2011 IEEE

supposed to allocate. Thus channel assignment to CPEs is achallenging problem.
Most of the existing work in IEEE 802.22 networks arefocused on self-coexistence [12], signal detection or spectrum
sensing [4], [13], inter-cell and control channel assignment [6];however, to the best of our knowledge, no significant work
has been done investigating channel allocation within an IEEE
802.22 cell.
In this paper, we propose an on-demand channel allocation
scheme for IEEE 802.22 networks where the BSs allocate
unused channels to CPEs. We argue that the lack of knowledge
about the channel usage scenario at the CPE locations is theprimary difficulty in efficient channel assignment. To counter
this, we propose the creation and maintenance of a Spectrum
Map at the BS. A Spectrum Map describes the spectrum
usage of an area under the purview of a given BS. To createa Spectrum Map, the BS elects a subset of CPEs, called
delegates, to opportunistically share their spectrum usage with
the BS. The BS intelligently fuses such spectrum usage data
and uses Shepard's interpolation [11] method to construct theSpectrum Map. The map is used for quicker communication
with a candidate CPE and increases the probability of synchro­nization between the CPE and the BS. Such communication
allows the BS to acquire the actual spectrum usage at the CPE
and evaluate different performance metrics such as wirelesscapacity, secondary network throughput, spectrum efficiency,
and bit error rate for candidate channels. Such proactive
performance analysis not only identifies the best candidate
channel for a CPE but also indicates the best possible CPE
among candidate CPEs for a particular channel. Channel
allocation scheme thus adopted increases the overall network
throughput and maximizes channel performance.
To evaluate our scheme, we construct a realistic simulation
environment emulating the location distribution of digital TV
transmitters in US [8], [9] and duplicating their transmis­
sion patterns. We deploy IEEE 802.22 networks at different
locations with varying population density of primaries. We
compare the results with actual received signal strength values.
Comparisons show a low probability of error (p=0.06) for
false positives and upto 92% reduction in redundant beaconbroadcast which increases the probability of synchronization.
Finally, the allocation algorithm shows close to perfect allo­
cation and more than 50% of free channel utilization even in
worst case scenario with no intra-cell spatial reuse.

619

Algorithm 1 Delegation selection Algorithm

II. S YSTEM MODEL
We consider an IEEE 802.22 network that is divided into
cells, each having a BS. A BS can communicate with the CPEs
in its cell as well as with its neighboring BSs.
We assume that all BSs continuously perform channel
sensing, i.e., they scan the entire spectrum (from 54 to 698
MHz) and create their respective spectrum usage report. The
IEEE 802.22 draft [I] requires all the devices in the network
to be installed in fixed locations and the BS to be aware of thelocation of all the CPEs under it. According to [I] there are no
pre-defined control channels in the system and the only meansof communication between the BS and the CPE are the freechannels that are currently not being used by the primary users.
Apart from allocating free channels to the CPE, the BS is also
responsible for transmitting beacons to advertise free channels,
gather sensed data from the CPEs, and fuse those spectrum
data. We select a subset of CPEs that we call delegation CPEs.
These delegated CPEs are chosen in a dynamic manner basedon their location and transmission activity.
@o•Delegated CPE

Oldie CPE with channel® Allocated CPEoFig. I.

Idle erE without channel

IEEE 802.22 network with BS and different types of CPEs

A. Zones

Zones are logical divisions of the coverage area of BS. Thisdivision is proposed as a BS specific feature and therefore
does not violate[1] specifications. The purpose of such
zonal division is efficient channel allocation. Such division
is governed by the requirement to keep similar densities ofCPEs per zone. A CPE cannot be allocated any channel which
is being used by the allocated or delegated CPEs of that zone
unless they are beyond the interference region of the CPE. The
zones are also important for selecting the delegation CPEs. The
idea is to have almost equal representation from all zones andno zone is unrepresented as far as possible. The BS maintains
three queues for each zone, namely : AQ (for allocated CPEs),
DQ (for delegated CPEs) and HQ (for potentially delegate
CPEs i.e., idle CPEs with channels).
B. Delegation of CPEs

The underlying principle of efficient channel allocation isthe ability of the BS to successfully predict the spectrum
usage at any CPE location in the cell. To achieve this, theBS needs to periodically collect raw spectrum usage datafrom the delegated CPEs. At any instance, only delegatedCPEs take part in sharing their spectrum usage with the
BS. A prudent choice of delegation CPEs results in betterinterpolation of spectrum usage. BS controls the selection ofa particular CPE as a delegation member. BS aims to have\: Assume ILl.1 is the number of delegation ePEs
2: Assume e is the desired lower bound of ILl.1
3: if ILl.I :::; e thenFind zone of the ePE to be selected from
4:

5:

6:
7:
8:

9:

Extract AQ,HQ,DQ for the zone
if emptyHQ=FALSE thenenDQ=deHQ \ \Selecting deHQ as the replacement
else {emptyAQ=FALSE}
enDQ=deAQ \ \Selecting deAQ as the replacement

else
10:
II:
Find the nearest zone
12:
Repeat from queue extraction (Step 5.)
13:
end if
14: end if

delegation representatives from different zones of the cell as
more geographically dispersed delegated CPEs will help tocreate a more accurate Spectrum Map. Selection takes place
after termination of data transmission (either voluntarily orforcefully) with the channels previously allocated for trans­mission now serving as sharing medium. If not selected fordelegation, a CPE can relinquish its channels or hold onto
the channels in anticipation of channel requirement in thenear future. Holding time depends on the demand for theparticular channels by other CPEs. However, such holding onto
channels can result in that CPE being selected as a delegation
member (using the same channels for sharing) if instructedby the BS. A delegated CPE continues to serve until it isinstructed otherwise by the BS. This obligates the CPE to use
the allocated channels only as means to share its spectrum
usage with BS even if the CPE wants to go to the transmission
state. The decision of keeping such a CPE in sharing state
solely depends on the importance of that CPE in building thespectrum profile. Soon after the BS finds a suitable alternative,it allows the CPE to switch to the transmission state anduse the same channel for data communication. Algorithm I
describes the selection process of a delegation member.
In Fig. 1, we see how the coverage area of the BS is divided
into zones. The BS attempts to find a delegated CPE for every
zone. However, the BS might fail to do so for every zone.
C. Intelligent beacon broadcast

The IEEE 802.22 draft [1] mandates a BS to broadcast bea­cons as a part of advertising the availability of free channels to
the CPEs. Instead of sending beacons in all the free channels,
we adopt an intelligent beacon broadcasting technique where
the beacons are sent only on selected channels depending on
the requirement of idle CPEs. These selected channels arethose that belong to the common set of the available channels
for allocation and the set of channels which are estimated to
be available for the idle CPEs.
If there are K CPEs in a IEEE 802.22 cell and Palloc is theprobability that a CPE is allocated at any instance then thereare (KPalloc
I�I) idle CPEs currently in the system. Let
Vest (where Vest E N) to be the estimated set of available
channels for the idle CPEs with N being the total set ofchannels in the spectrum and INI=N. If "(jree be the set ofallocable set of channels on offer for the BS then beacons
are send only on the channels belong to Vest n "(jree' We
assume a single beacon is sent per channel. We assume that"(free is the set of free channels at a CPE c and this contains

620-

the channels on which the CPE tunes its radio for beacon
reception. Therefore, assuming negligible time for broadcast
and propagation, probability of synchronization is given by:. . beac nP( CPE recezvzn
g
o )

=

IVest n 'Yjree n 'Yfree Ib
I Vest n 'Yfree
I I 'YCfree I(1)A beacon contains the IDs of all the channels on which the
beacons are being sent. Therefore, a CPE,
once receivinga beacon sends back channel allocation requests in all theadvertised channels along with the actual spectrum usageat
YC={'P� I
E N}. The completion of BS-CPE
handshaking process is marked by the reception of the channel
allocation request by BS in any of the I Vest n 'Yjree I channels.
Therefore,

c,

c

Vchq

.

P( Successful handshakzng)=

I Vest n 'Yjree n 'Yfree Ib121'YCfree I
I Vest n 'Yfree( 2)

This intelligent broadcasting scheme reduces the number of
redundant beacons and increases the probability of synchro­nization with 0.67 in the best case and 0.35 in the worst case.
III.

Algorithm 2 Interpolation Algorithmr

1: Find radius
2: Find the set of data points Re = {6i 1 0
3: for all channels in the spectrum do
for all data points i in the set Re do
4:
if 0:::: i then
5:
6:
¢= *

q

7:

8:
9:
10:
1 1:
12:
13:
14:
15:
16:
17:
18:
19:
20:
2 1:

We have I� I cognitive radio enabled delegation CPEs andlet the co-ordinates of the ith delegation CPE c5i be (Xi, Yi).
Also, this CPE records some data value of Zi. The data value
can correspond to one of the many radio parameters like SNR,
duty cycle, or detected energy for a particular channel that theCPE is sensing. Now, given c5 such triplets (Xi, Yi, Zi), we seek
to find a two dimensional interpolation function f(x, y)Zthat will be continuous and differentiable, passing through all
the data points i.e., f(xi, Yi)
Zi, and should conform to reallife values.
==

We use Shepard's [11] method of interpolation for ir­
regularly spaced data points in a two dimensional region
to estimate the spectrum usage at
If
is the value ofthe detected energy at c5i for channel
then interpolated
spectrum usage using Shepard's method [11] is given as:

e�
chq,

(3)

The process of computing <I>c is shown in Algorithm 2.
Detailed discussion on the method of finding <I>c is discussedc,in [11]. From the estimated spectrum usage at
the BS finds
the set 'ljJ�st (set of free channels atapplying hypothesis
analysis on estimated channel usages of all channels.

c)¢=

end iffor all data points k where i # k do
Find Pk

angle�k ( - Xi)(X - Xk)+ (y - k)
sfk numfk+ pd1 - anglefk) Yi)(Y Y
tik denik+ Pk
end fora': t�i kk
wi (pn2(1+ an
numf wfe� + numf
denf wi+ denf
e�d r
� i
<P
¢=

The complexity of algorithm 2 is O(m2 N) where N is thenumber of channels and m is the number of delegation CPEs
involved in the interpolation. Since the number of delegation
CPEs is a constant, the average case complexity is O(N).
I We use the delegation CPEs as the data gathering points, hence we also
refer to them as 'data points'.

¢=

x

¢=

8e

¢=

z

¢=

{::::

¢=

IV.

Estimating the spectrum usage at any CPE from a given set
delegation points is non-trivial. In essence, we seek to definea continuous two-dimensional interpolation function which
passes through all the given irregularly-spaced data points I .

c.

::; d�
pf
else H ::;'df::; r}pf ¥(� - 1)2

q �
22: end for

INTERPOLATION OF SPECTRUM DATA::; d� ::; ...::; d�}

nurn
den�
•

PERFORMANCE BASED C HANNEL ALLOCATION

Successful beacon reception from a CPE initiates the BS to
calculate performance metrics and allocate suitable channels
to the CPE. Such metrics include channel capacity, spectrum
efficiency, throughput, bit error rate etc.
A. Performance metrics

The interference experienced by any CPE is due to theprimary transmitters as well as other transmitter-receiver pairs
using the same channel. Let us suppose the respective inter­
ferences experienced by CPE located at (xc, Yc) in channelcchq are ¢� (estimated using eqn. 3) and Ig

L Plh�12
VjEl<qwith ",q being the set of all other CPEs using channel chq .
=Below we discuss BS calculating four of numerous pos­sible performance metrics namely channel capacity, spectral
efficiency, network throughput, and bit error rate.
Channel Capacity : The channel capacity cg for channel
is calculated using Shannon-Hartley theorem [10].

chq

C�

=

B

Plhcl2log2(1 + ¢c +qIJ
q q

(4)

where B is the channel bandwidth.
Secondary Network Throughput : If a BS transmits withpower
to CPE
then the transmission rate considering allother secondary communication is given byPc,Plh�12(5)'Ircq log(l + Ic + ¢c + (]" )q q 2
where the received signals are corrupted by zero-mean additive
white Gaussian noise of power (]"2. Network throughput for a=particular channel is the sum the transmission rates of all the
BS-CPE pairs using the same channel
and given as:

IIq=

L 'Ircq
�E�

chq

=

Plh�12
L log(l + IC + ¢c + (]"2)
q q
�E�

(6)

Spectral Efficiency : Spectral efficiency provides an in­
dication of how efficiently a bandwidth-limited frequency
spectrum is used. Link spectral efficiency in bits/sec/Hz isdefined as the net bit-rate that can be achieved by a link per

621

channel bandwidth (Hz). Thus, link spectral efficiency for chq
between the BS and CPE c is

Plhcl2

�� = B log(l + Ic q¢;c + (J"2)
1

q+ q

(7)

The system spectral efficiency also in bits/seclHz is defined as the maximum throughput, summed over all nodes,
divided by the channel bandwidth. Therefore, system spectral
efficiency is

Plhcql2
1
3q = L �� = B L log(l + IC
c + (J"2)q + ¢;qVjEKq
VjEK'I(8)

in [8] [9]. The total number of channels considered is 50 withbandwidth of 6 MHz. The power-profile of the TV stations
ranges between IOkW-IMW. We identify two regions with
dense and sparse primary densities (mimicking big cities andsmall towns) and deploy IEEE 802.22 networks (WRAN cells)
shown in Fig. 3. Locations of different types of nodes andtransmission patterns are different in the two scenarios while
total number of CPEs, density, and the number of delegatedCPEs are kept the same. We evaluate the proposed techniqueboth in terms of accuracy of spectrum usage estimation andperformance of the allocation algorithm.

Spectral efficiency gives the number of secondary nodes thatcan be simultaneously supported by the available spectrum in ageographic area. In other words, we regard it as a quantitative
measure for self-coexistence of IEEE 802.22 networks.
Bit error rate : The bit error rate (BER) between BS and
CPE is dependent on the modulation and coding schemes forcommunication. For DPSK, BER is given by [7]BERDPSK= �e- �bq

(9)

1
BERDPSK="2e- "';.�c
'I 'I
q

(10)

2

where
is the average energy per bit transmitted and 'rJ/2
is the noise power spectral density. The former is expressedas= P/,rr g. Noise power spectral density is given by 'rJ =¢;g/ Substituting the values in equation (9), we get,

Eb

Eb
B.

If there are Q bits in a transmitted packet then the packet error
rate is given by= 1- (1BER and PER canbe calculated for any modulation scheme.

PER

BER)Q.

B. Allocation process

The allocation process by the BS is initiated by reception ofchannel allocation reply from any CPE c in any of the Vest n'Yjree n 'Yfree channels. Such allocation reply is accompaniedwith raw spectrum usage at c, yc={ ¢;jll::fchj E N}. BS createsthe set of available channels p�vl={jl l::f¢;j < T} allocable toc. Channels used by other allocated or delegated CPEs in theinterference range of c can not be allocated to c for obvious
reasons. In order to ensure this, the BS finds the AQ, DQ and
HQ of all the zones within the interference range of c. From-cthe AQs, the BS creates the set AQ with only those channels
which are allocated to CPEs within the interference range of
-c
-c
-c
..
c. Similarly DQ and HQ are created. No channels in AQ-cand DQ can be allocated to avoid co-channel interference.
BS updates the set of available channels for allocation P�vl
excluding all such channels. For all the rest of the channels
in P�vl' expected channel performance (can be any desirable
parameter or a combination of some) is calculated and given ascore. P�vl is further updated with descending order of channel-cscore. There is also the set HQ whose channels are held byother idle CPEs in the interference range of c. The purposeof allowing the CPEs to hold onto channels is not making
them go through the entire handshaking process and expedite
channel allocation. Therefore, BS always tries to allocate thebest channel among Ip�vll not belonging to HC/, if possible.
V.

SIMULATION RESULTS

We simulate TV stations in a 500x500 sq. miles gridas shown in Fig 3 using TV station location distribution

Fig. 3.

Simulation grid with primary transmitters, secondary BSs and CPEs

In figures 2(a), 2(b), and 2(c), 2(d), we show the estimatedand actual signal strengths for two regions. The figures reflect
the success of the interpolation technique to capture the natureof spectrum usage in the regions. By comparing the estimatedand actual signal strength values for both region , we get theerror in estimation of the order 10-6 m W which is too small
to alter the occupancy decision vector.
Fig. 4 shows the channel occupancy vectors of two different
CPEs located in two regions. In both the cases the predictionof channel occupancy is highly accurate with only 6 and 3
false positives respectively. It is important to note that noneof these variations are false negatives which is essential forsecondary communication. Our results show that on an average
the probability of false positive is as low as 0.08. Such accurate
estimation can lead upto 92% reduction in beacon broadcast.
Figs. 5(a) and 5(b) show the spatial distribution of channel
capacity for the two scenarios. Such spatial distribution helps
the BS not only to find the best candidate channel for a CPE
but also the best candidate CPE for a particular channel which
will realize the highest achievable capacity for that channel.
The bandwidth of the channels are kept constant at 1 MHz.
Fig. 6(a) shows the performance of allocation method for
different probability of white space. We show the results for
worst case scenario when upto 200 simultaneous idle CPEs
want to get allocated. The scheme performs very well for
realistic simultaneous allocable CPEs with realistic probabilityof white space (0.6 and higher.).
Utilization of free channels using our scheme is shown in
Fig. 6(b). We see that on an average more than 50% of the

622

(a)
Fig. 2.

(b)

(d)

(c)

(a) (b) Estimated and actual signal strengths of a channel for Region 1; (c) (d) Estimated and actual signal strengths of a channel for Region 2IIo

I I I,

I
30
20
Channel ID

10

40

50

� 120 --e-N.... ...fI<k-ICPf.s,.I.'i(}� ..o __ N.... ...fd<-ICPl.'.s><200!:i:(a) Estimated channel occupancy of CPE #38 in Region 1

'

I
o

i

30
20
Channel ID

10

40

50

(a) Actual channel occupancy of CPE #38 in Region 1

I
o

I
10

(a) Allocation for different
probability of white space

I

20
30
Channel ID

40

Fig. 6.

50

I
10

30
20
Channel ID

40

Estimated and actual channel occupancy of two CPEs in two regions(a)Fig. 5.

(b)

Spatial distribution of channel capacity for two regions

free channels of the spectrum are being utilized. Utilization
increases with increasing demand from idle CPEs.
VI.

Efficiency of channel allocation technique

REFERENCES

50(b) Actual channel occupancy of CPE #106 in Region 2
Fig. 4.

(b) Allocation for differnt
number of idle CPEs

performance. Through simulation experiments, we showed theaccuracy of the spectrum estimation and effectiveness of theallocation technique.

(a) Estimated channel occupancy of CPE #106 in Region 2o10CONCLUSIONSIn this paper, we proposed a spectrum usage estimation
technique for IEEE 802.22 networks. We used Shepard's inter­
polation method to construct spectrum map. We showed how
the data gathered only from the delegated CPEs can be used toevaluate the channel occupancy vector which is then used tocommunicate with the idle CPEs. We also proposed a channel
allocation algorithm which enhances channel and network[I] IEEE P802.221D1.0 Draft Standard for Wireless Regional Area Networks Part
22: Cognitive Wireless RAN Medium Access Control (MAC) and Physical Layer(PHY) Specifications: Policies and Procedures for Operation in the TV Bands,
April 2008[2] IEEE 802.22, Working Group on Wireless Regional Area Networks (WRAN),
http://grouper.ieee.org/ groups /802122[3] Akyildiz,1. E; Lee,W. Y; Vuran,M.e.; Mohanty,S.; ,"NeXt GenerationlDynamic
Spectrum Access/Cognitive RadioWireless Networks: A Survey, " Elseview Jour­nal of Computer Networks,Vol. 50,pp. 2127-2159, September 2006
[4] Hou-Shin Chen; Wen Gao; Daut, D.G.; , "Signature Based Spectrum Sensing
Algorithms for IEEE 802.22 WRAN," Communications, 2007. ICC '07. IEEE
International Conference on ,pp. 6487-6492,24-28 June 2007
[5] Ganesan, G.; Li Yeo , "Cooperative Spectrum Sensing in Cognitive Radio, Part
11: Multiuser Networks," Wireless Communications,IEEE Transactions on ,vol.6,
no.6,pp.2214-2222,June 2007
[6] Lazos, L.; Sisi Liu; Krunz, M.; , "Spectrum Opportunity-Based Control Channel
Assignment in Cognitive Radio Networks," Sensor, Mesh and Ad Hoc Commu­
nications and Networks, 2009. SECON '09. 6th Annual IEEE Communications
Society Conference on ,pp. 135-143,22-26 June 2009[7] Proakis,J. G.; ,Digital Communications,4th ed. McGraw-Hill,2001[8] Riihijarvi, J.; Mahonen, P.; Wellens, M.; Gordziel, M.; , "Characterization andmodelling of spectrum for dynamic spectrum access with spatial statistics andrandom fields," Personal, Indoor and Mobile Radio Communications, 2008.
PIMRC 2008. IEEE 19th International Symposium on ,pp.I-6,15-18 Sept. 2008
[9] Riihijarvi, J.; Mahonen, P.; , "Exploiting Spatial Statistics of Primary and Sec­
ondary Users towards Improved Cognitive Radio Networks," Cognitive Radio
Oriented Wireless Networks and Communications, 2008. CrownCom 2008. 3rd
International Conference on ,pp.I-7,15-17 May 2008[10] Shannon,C. E.; , "A mathematical theory of communication," Bell Syst. Tech. J.,
vol. 27,pp. 379-423,623-656,1948[II] Shepard,D.; , "A Two-Dimensional Interpolation Function for Irregularly-Spaced
Data," ACM National Conference,1968[12] Sengupta,S.; Chandramouli,R.; Brahma,S.; Chatterjee,M.; , "A game theoretic
framework for distributed self-coexistence among IEEE 802.22 networks," Global
Telecommunications Conference,2008. IEEE GLOBECOM 2008. IEEE ,pp. 1-6,
Nov. 30 2008-Dec. 4 2008[13] Tachwali, Y; Bames, W.J.; Basma, E; Refai, H.H.; , "The Feasibility of a
Fast Fourier Sampling Technique for Wireless Microphone Detection in IEEE
802.22 Air Interface," INFOCOM IEEE Conference on Computer Communications
Workshops ,2010 ,pp. 1-5,15-19 March 2010623