A MAC protocol for opportunistic spectrum access in cognitive radio networks

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2008 proceedings.

OSA-MAC: A MAC Protocol for Opportunistic Spectrum Access in Cognitive Radio Networks Long Le and Ekram Hossain

Abstract— We present a MAC protocol for opportunistic spectrum access (OSA-MAC) in cognitive wireless networks. The proposed MAC protocol works in a multi-channel environment which is capable of performing channel sensing to discover spectrum opportunities. For this MAC protocol, two channel selection methods are considered which trade the implementation complexity with throughput improvement. We then analyze the saturation throughput performance of the proposed MAC protocol under scenarios where the probabilities for each channel to be available to different secondary flows are the same or different. We then derive analytically the probability of collision of secondary users with primary users due to sensing errors. This analysis can be used, for example, to determine the requirement of sensing accuracy for secondary users, and to design an admission control method. We present numerical results to demonstrate the throughput performance of the OSAMAC protocol and applications of the proposed analytical model.

throughput performance for the proposed MAC protocol. We also obtain the probability of collision of secondary users with primary users due to sensing errors. Using this analysis, we show how to quantify the sensing accuracy requirement and to perform admission control to guarantee quality of service (QoS) for primary users in terms probability of collision with secondary users. The rest of this paper is organized as follows. The system model is presented in Section II. Section III presents the proposed OSA-MAC protocol. Analysis of the OSA-MAC protocol is performed in Section IV. Section V presents the numerical results and Section VI summarizes the paper.

Index Terms— Cognitive radio, opportunistic spectrum access, spectrum sensing, multi-channel MAC protocol.

We consider the spectrum sharing problem for spectrum overlay in a cognitive wireless network, where unlicensed users (i.e., secondary users) opportunistically exploit the spectrum holes in licensed frequency bands. Specifically, secondary users can only transmit on channels if these channels are not being used by primary users. We assume that N secondary flows opportunistically seek spectrum opportunities in L different channels. Each flow is established by a pair of secondary users wishing to communicate with each other. Specifically, a secondary user senses and accesses the channels if any of these L channels is not being used by the primary users. We further assume that each secondary user has a single radio and secondary users has the capability of sensing the presence of primary users on any channel which they switch to. Our objective is to develop an intelligent MAC protocol which integrates both sensing and channel access functionalities. Here, the MAC protocol works in a multi-channel environment and each secondary user only accesses at most one channel at any time. Therefore, the issues of synchronizing transmitting and receiving entities on the same channel for control information exchange or multi-channel hidden terminal problem as in the conventional multi-channel systems should be considered [6]-[8]. In addition, to avoid collision with primary users, secondary users should perform sensing frequently besides doing contention resolution as in a conventional MAC protocol. There are two major approaches to handle the first challenge in conventional multi-channel MAC protocols. The first approach employs a dedicated control channel to exchange all control information and negotiate channel for data transmission [6], [8]. In the second approach, users follow a common or different hopping sequences where they hop through the channels in a predetermined manner [6], [7]. Users

I. I NTRODUCTION Recently, there has been an increasing interest in designing dynamic spectrum access networks which allow unlicensed users to exploit spectrum opportunities in licensed frequency bands. As described in [1], unlicensed users (referred to as secondary users) can access the spectrum owned by licensed users (referred to as primary users) using spectrum underlay or spectrum overlay. Under the spectrum underlay paradigm, secondary users are allowed to transmit simultaneously with primary users in the licensed band. We will consider the MAC layer design problem for the spectrum overlay paradigm in this paper. In [2], admission control design and rate/power allocation problems were investigated for cognitive wireless networks employing CDMA technology under spectrum underlay paradigm. In [3], the authors presented a design framework for joint spectrum sensing and access considering spectrum sensing errors by using a partially observable Markov decision process. The proposed framework is computationally complex and the detailed design of the handshaking method for the MAC protocol was not provided. Some other existing MAC protocols for opportunistic spectrum access can be found in [4], [5]. These protocols, however, required the knowledge of spectrum map, which may be difficult to obtain in practice. In this paper, we propose a new MAC protocol for opportunistic spectrum access. Then we analyze the saturation Long Le is with the Department of Electrical and Computer Engineering, University of Waterloo, Canada. Ekram Hossain is with the Department of Electrical and Computer Engineering, University of Manitoba, Canada. Email: [email protected], [email protected],

II. S YSTEM M ODEL AND THE MAC D ESIGN C HALLENGES

1525-3511/08/$25.00 ©2008 IEEE

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2008 proceedings. 2

can exchange control information and choose a channel for data transmission when they hop to the same channel. For the opportunistic spectrum access problem, using the second approach is difficult because even if a pair of secondary users hop to the same channel, they have to sense the presence of primary users before exchanging information. Given the fact that spectrum opportunities may come and go very frequently, we will use the first approach in designing the MAC protocol. III. OSA-MAC P ROTOCOL FOR O PPORTUNISTIC S PECTRUM ACCESS In this section, we propose a MAC protocol for opportunistic spectrum access. For ease of reference, we will refer to our proposed MAC protocol as OSA-MAC in the sequel. The proposed MAC protocol shares some similarities with the multi-channel MAC protocols [6], [8]. However, a MAC protocol for opportunistic spectrum access should integrate the spectrum sensing capability, which must be evoked frequently to minimize collision with primary users. Beacon Beacon Interval ATIM Window ATIM

RTS

… …

ACK

Control channel CTS

ATIM-ACK

Phase I

DATA

Phase II

Phase III DATA

RTS

ACK

Channel 1 CTS

. . .

Backoff

Sensing

RTS

DATA

ACK

Channel L CTS

Fig. 1.

Timing structure of the proposed OSA-MAC protocol.

We assume that secondary users exchange control information in a dedicated channel which is always available (i.e., this channel may be owned by the secondary service provider). Given the number of channels available for sharing is large enough (i.e., L is large), this assumption is reasonable. It is worth noting that this control channel can also be used to transmit data besides control information as will be described shortly. The proposed MAC protocol uses the idea from PSM (Power Saving Mechanism) in IEEE 802.11 DCF-based WLANs. We assume that time is divided into beacon intervals and all of the secondary users are synchronized by periodic beacon transmissions. The OSA-MAC protocol works as follows. Each beacon interval consists of a channel selection phase, sensing phase and data transmission phase which will be referred to as phase I, II, III, respectively. At the beginning of each beacon interval each secondary user who wishes to transmit data to its intended receiver will choose a potential channel by transmitting an

ATIM (Ad Hoc Traffic Indication Message) to its receiver on the predetermined control channel. Upon receiving the ATIM, the receiver will respond by transmitting an ATIM-ACK to the transmitter. Note that we use the term ATIM as in IEEE 802.11 PSM although it is used for a difference purpose here. The ATIM will contain the channel chosen by the transmitter for data transmission in phase III. Upon agreeing on the chosen channel, secondary users will switch to their chosen channels for sensing in phase II. There may be multiple ATIM transmissions from different secondary users in phase I and contention is resolved by using the backoff mechanism as in the conventional IEEE 802.11 DCF mode. The channel selection phase will occur in a predetermined interval called ATIM window as shown in Fig. 1. The ATIM window should be long enough such that all backlogged secondary users can successfully exchange ATIM and choose channels with probability very close to one. Details of the channel selection process will be elaborated shortly. When the number of secondary users is large, several secondary flows may choose the same channel in phase I. Hence, collision resolution in the data transmission phase will be performed by using the RTS/CTS/DATA/ACK four-way handshake as in the IEEE 802.11 CSMA/CA protocol (as shown in Fig. 1). Note that these four-way handshakes are performed by all secondary users on their chosen channels. The channels chosen by the secondary flows may be currently used by primary users; therefore, channel sensing needs to be performed before transmission to avoid possible collisions. Therefore, all secondary users sense their chosen channels continuously during phase II. If any chosen channel is found to be busy, the corresponding secondary users will switch to the control channel and wait until the next beacon interval. Otherwise, they proceed to phase III for another round of contention. Note that secondary users are not allowed to transmit on any channel in phase II, and therefore, these channels can only be busy in this phase because primary users are using them. At the beginning of phase III, each secondary transmitter (i.e., a secondary user who transmits data to its intended receiver) will choose a backoff value randomly in the interval [0, W − 1] where W is the fixed predetermined contention window (i.e., exponential backoff is not employed). In fact, time immediately after the end of phase II will be slotted up to W slots. The slot size is chosen such that each user can detect the transmissions from other users. Then, the transmitter will decrement its backoff timer by one over each idle slot while listening to its chosen channel. The secondary user having the smallest backoff value on each channel will win the contention and transmit data in the remaining period of phase III using the four-way handshake mechanism as in the IEEE 802.11 CSMA/CA protocol. To minimize possible collision with transmissions from primary users, only one packet from the winning user on each channel is transmitted in phase III. It is possible that no secondary user wins the contention on some channel because two or more secondary users have the same minimum backoff value. In this case, no packet is transmitted on the channel in that beacon interval and all corresponding users choosing this channel will go to sleep mode to save

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2008 proceedings. 3

power until the next beacon interval. As Fig. 1 shows, the control channel can be used for data transmission from phase II onward because this channel belongs to the secondary network provider. A. Uniform Channel Selection Secondary flow i after being successful during contention in phase I simply chooses any channel j among L channels randomly with the same probability qi,j = 1/L. This simple channel selection method does not consider different spectrum opportunities in different channels; it is, however, simple to implement.

channel selection method, we will have qi,j = qk,j = qj for all i, k ∈ {1, 2, · · · , N }. Note that we have used pj and qj to denote these probabilities for notational simplicity. We will show how to relax some of these assumptions later on. We now derive the saturation throughput for a particular channel j. The total system throughput will be the sum of throughputs of secondary users on all channels. Now, suppose that k secondary flows choose channel j and contend for channel access in phase III. Consider the event where exactly one secondary flow wins the contention (i.e., one secondary flow has the minimum backoff value) and transmits data in phase III. This event occurs with probability Sk,j =

B. Spectrum Opportunity-Based Channel Selection We can see that if the number of secondary users is small compared to the number of channels, it would be more efficient to exploit capacity of these channels by allowing secondary users to access highly available channels instead of employing the simple uniform channel selection approach. Specifically, we consider two regions in which the number of secondary links is small and large, respectively, compared to the number channels. These two regions are divided by a particular value which will be denoted by Nth . Now, secondary flows will adopt the uniform channel selection approach if N > Nth . Otherwise, a channel selection approach taking the probabilities of spectrum availability in different channels into account will be adopted as in the following. We assume that each secondary flow can estimate the total number of active secondary flows (i.e., N ) and channel j is available for secondary flow i with probability pi,j . We will refer to this probability as spectrum availability probability on channel j. We further assume that pi,j is independent and identically distributed over beacon intervals. In each beacon interval secondary user i will choose channel j with a probability proportional to pi,j . Specifically, user i chooses channel j with probability pi,j qi,j = ∑L (1) k=1 pi,k where we assume that pi,k can be estimated by secondary users correctly. IV. A NALYSIS OF OSA-MAC P ROTOCOL A. Saturation Throughput Analysis In this section, saturation throughput is analyzed under the assumption that secondary users always have data to transmit. Note that saturation throughput is an important performance measure for any MAC protocol [6]. We further assume that the ATIM window is long enough such that all secondary users succeed in choosing their channels in phase I. Suppose that there is a single contention domain where transmission from each user will collide with those of other users if these transmissions occur on the same channel as in [6]. Also, it is assumed that the spectrum status on each channel is the same for all secondary users (i.e., pi,j = pk,j = pj for all i, k ∈ {1, 2, · · · , N }). Therefore, by using the same

W l k−1 k ∑ (1 − ) W W

(2)

l=1

where W is the contention window size. Now, the probability that k secondary flows choose channel j can be calculated as ( ) N Ck,j = (qj )k (1 − qj )N −k . (3) k Recall that these k secondary flows only proceed for contention in phase III if channel j is not used by primary users. Let R, tT I and tBI denote the transmission rate, the time needed to transmit a packet on each channel and the length of the beacon interval, respectively. By accounting for the overhead involved in each beacon interval, the throughput of channel j can be written as N R × tT I ∑ Tj = Ck,j × pj × Sk,j tBI

(4)

k=1

where pj is the probability of availability of channel j. The total system throughput on L channels can be calculated as T =

L ∑

Tj

(5)

j=1

where T < R due to control, contention overhead, and spectrum usage of primary users. B. Extension of Throughput Analysis In general, spectrum opportunities are location dependent, so pi,j may not be equal to pk,j for i 6= k. If this is the case, different secondary flows will choose one particular channel with different probabilities even if they use the same channel selection approach. To derive throughput on channel j, let us consider different sets of secondary flows with size k. Specifically, we will denote by ζh,k the h-th set with k secondary flows in the set { ( )} N ∆k = ζh,k : |ζh,k | = k for h = 1, 2, · · · , k where |ζh,k | denotes the cardinality of set ζh,k and the ordering of ζh,k in ∆k is arbitrary. Now, the probability that all secondary flows in set ζh,k choose channel j can be written as       ∏   ∏ (1 − qi,j ) (6) Ch,k,j = qi,j     i∈ζ i∈ζh,k h,k

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2008 proceedings. 4

where ζ h,k is the complement of set ζh,k . Let Sil ,k,j be the probability that the l-th secondary flow in set ζh,k wins access to channel j in phase III. Then, we have W 1 ∑ l k−1 (1 − ) . W W

Sil ,k,j =

(7)

1) Constraint on sensing accuracy Pm : Given that the number of secondary flows is N and the requirement on collision probability is P0 , we should have the following constraint (c) Pmax ≈ max {Pm Bj } ≤ P0 . (11) j

l=1

Throughput of channel j can then be written as Tj =

N R × tT I ∑ tBI

∑

k ∑

Ch,k,j × pil ,j × Sil ,k,j

k=1 h: ζh,k ∈∆k l=1: il ∈ζh,k

where secondary flow il in each set ζh,k of k secondary flows wins channel access in phase III of the OSA-MAC protocol. The total system throughput can be calculated using (5). C. Collision Probability with Primary Users Suppose that all secondary users have the same sensing accuracy and let Pm denote the probability that a secondary user fails to detect the presence of primary users on one channel given that the channel is occupied by primary users. Note that collision occurs due to a particular flow if the corresponding transmitter fails to detect the presence of primary users on the channel and it proceeds to transmit the RTS packet. For simplicity, we only derive the collision probability for the case where channel availability probability is the same for all secondary flows (as considered in Section III.B). We observe that collision with primary users occurs on one particular channel if the channel is being used by primary users, one or more flows choose that channel and at least one flow fails to detect the presence of primary users on the channel. Now, given that a channel is busy, the probability that at least one among k flows fails to detect the presence of primary users is 1 − (1 − Pm )k . Thus, by considering all possible cases where different number of flows may access one particular channel j, the collision probability on channel j can be written as (c) Pj

=

N ∑

[ ] Ck,j 1 − (1 − Pm )k (1 − pj )

From this, the requirement on sensing accuracy for secondary users is Pm ≤ P0 /Bmax (12) where Bmax = maxj Bj . 2) Admission control problem: When Pm and P0 are given, we can determine the maximum number of secondary flows Nmax which can be admitted as { } (c) Nmax = max N : Pmax ≤ P0 . (13) This calculation can be used to perform admission control for secondary flows such that QoS of primary users in terms of collision probability can be guaranteed. V. N UMERICAL R ESULTS In this section, we will present some illustrative numerical results for the OSA-MAC protocol presented in Section III. We assume tT I /tBI = 0.75, R = 2 Mbps, W = 64 to obtain our numerical and simulation results for system throughput in Figs. 2-3. Simulation results are obtained from a discrete-event simulator which simulates exact operations of the proposed protocol. We assume that the probability that each channel is available for different secondary flows is the same (i.e., pi,j = pk,j = pj , ∀i 6= k). We show system throughput versus the number of secondary flows for the OSA-MAC protocol in Fig. 2, where each channel is available for secondary flows in each beacon interval with the same probability p = 0.6 (i.e., pj = p = 0.6 for j = 1, 2, · · · , L). This figure shows that simulation results match the analytical results very well which validates the analysis in Section IV.

(8)

k=1

10

(c)

(c) Pmax = max Pj .

(9)

j

D. Application of the Analysis In the following, we provide some applications for the derivations in (8), (9). For simplicity, let us use the approximation 1 − (1 − Pm )k ≈ kPm , which is tight for small Pm . Thus, we can rewrite (9) as { (c) Pmax

≈ max Pm j

∑N

N ∑ k=1

} kCk,j (1 − pj )

9

System throughput (Mbps)

where Ck,j is the probability that k flows choose channel j and (1 − pj ) is the probability that channel j is being used by (c) primary users. From Pj given in (8), the maximum collision probability on any channel can be written as

L = 10

8 L=8

7 6

L=6

5 4

Analysis Simulation

3 2 0

20

40 60 Number of secondary flows

80

100

Fig. 2. Validation of saturation throughput analysis (for tT I /tBI = 0.75, p = 0.6, W = 64).

= max {Pm Bj } (10) j

where Bj = k=1 kCk,j (1 − pj ). Now, suppose that the maximum tolerable collision probability by primary users is P0 . We have the following design applications.

Also, it can be seen from Fig. 2 that the system throughput increases with the number of secondary flows until reaching the maximum value (which is roughly equal to tT I /tBI ×p×L) and slightly decreases after that. This can be interpreted as

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the WCNC 2008 proceedings. 5

7

fixed value when the number of secondary flows becomes

L = 12

Collision Probability 6

System throughput (Mbps)

0.05 0.045

5 L =8

Rejected region

0.04

4

0.035 0.03

3 0.025

L=4

0.015

1

20

40 60 Number of secondary flows

80

Admitted region

0.01

Uniform Selection Opportunity Based Selection

0 0

P0 = 0.02

0.02

2

0.005

100

0 0.015

0.01 P

m

Fig. 3. Throughput under different channel selection approaches (for tT I /tBI = 0.75, p1 = 0.6, p2 = 0.15, W = 64).

Fig. 5.

0.005

0

10

20

30 N

40

50

Admission control example (for p = 0.6, L = 4).

−3

6

x 10

−3

P0 = 10

large enough. In Fig. 5, we show an example of admission control under the constraint that the collision probability on any channel is smaller than P0 = 0.02. In general, Nmax is an increasing function of P0 . Because N is discrete, given the sensing accuracy of secondary users (i.e., Pm ), the maximum number of admitted secondary flows can be easily determined.

P = 3.10−3

5

0

−3

P = 5.10 0

P

m

4

3

2

1

0 10

VI. S UMMARY 15

20

25 30 35 40 Number of secondary flows

45

50

Fig. 4. Required sensing accuracy for QoS protection of primary users (for p = 0.6, L = 4).

follows. Since there are multiple channels, the number of secondary flows should be large enough to “fill” the spectrum holes on these channels. When the number of secondary flows becomes very large, there will be several flows competing for the spectrum opportunity on each channel. Due to possible collision of RTS/CTS exchanges, the throughput slightly decreases with the number of secondary links in the high-load regime. In Fig. 3, we compare the throughput performance of the OSA-MAC protocol under different channel selection approaches, namely random and spectrum opportunity based channel selection. Here, we assume that half of the channels are available for secondary flows with probability p1 = 0.6 and the rest of the channels are available with probability p2 = 0.15. Also, when the number of secondary links satisfies N > 2L, each secondary flow selects one channel uniformly. Otherwise, each secondary flow chooses one channel using the probability expressed in (1). Fig. 3 shows that the spectrum opportunity-based channel selection approach can improve the throughput performance when the number of secondary links is small. In Fig. 4, we show the required sensing accuracy for secondary users in terms of Pm such that collision probability with primary users is smaller than P0 . As expected, a more stringent QoS target (i.e., smaller P0 ) requires a higher sensing accuracy. It is interesting that the required Pm tends to a

We have proposed a multi-channel MAC protocol for opportunistic spectrum access in cognitive wireless networks. The proposed OSA-MAC protocol is capable of sensing available channels and coordinating spectrum allocation for multiple secondary flows in a distributed manner. Saturation throughput analysis has been conducted for the proposed protocol. We have also derived the collision probability of secondary users with primary users which can be used in different design problems for primary users’ QoS esurance. Numerical results have validated the analysis and shown the efficacy of the proposed MAC protocol. R EFERENCES [1] Q. Zhao and B. M. Sadler, “A survey of dynamic spectrum access: Signal processing, networking, and regulatory policy,” IEEE Signal Processing Mag., pp. 79-89, May 2007. [2] L. Le and E. Hossain, “QoS-aware spectrum sharing in cognitive wireless networks,” in Proc. IEEE GLOBECOM’2007, Nov. 2007. [3] Q. Zhao, L. Tong, A. Swami, and Y. Chen “Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks: A POMDP framework,” IEEE J. Sel. Areas Commun., vol. 25, no. 3, pp. 589-600, April 2007. [4] L. .C. Wang, A. Chen, and D. S. L. Wei, “A cognitive MAC protocol for QoS provisioning in overlaying ad hoc networks,” in Proc. IEEE Consumer Communications and Networking Conference, pp. 1139-1143, Jan. 2007. [5] A. C. C.Hsu, D. S. L. Wei, and C.-C. J. Kuo, “A cognitive MAC protocol using statistical channel allocation for wireless ad-hoc networks,” in Proc. IEEE WCNC’07. [6] J. Mo, H. -S. W. So, and J. Walrand, “Comparison of multi-channel MAC protocols,” IEEE Trans. Mobile Comp., vol. 7, no. 1, pp. 50-65, Jan. 2008. [7] P. Bahl, A. Chandra, and J. Dunagan, “SSCH: Slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad hoc wireless networks,” in Proc. ACM MOBICOM’04. [8] J. So and N. Vaidya, “Multi-channel MAC for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver,” in Proc. ACM MOBIHOC’04.