Intermittent CSMA/CA for Unlicensed Dynamic Spectrum Access
A. Adamis1, Ph. Constantinou1
1Mobile Radio-Communications Laboratory, School of Electrical and Computer Engineering, National Technical University of Athens, 9 Heroon Polytechneiou Street, 15773, Athens, Greece. {adamis,fkonst}@mobile.ntua.gr
Spectrum Pooling and unlicensed spectrum access by Cognitive Radios can compensate for spectrum scarcity, caused by static licensing policies, by utilizing spectrum opportunities. In this work we modify CSMA/CA MAC protocol for operation over a spectrum pooling environment and for secondary, overlay, distributed Cognitive Radio Networks. New performance limits and design - tradeoffs are discovered. Moreover, a new MAC protocol is proposed to improve CSMA/CA throughput over spectrum pooling. All MAC protocols are evaluated through extensive simulations.
1.Introduction
Today's radio networks are governed by a static spectrum policy. These old-dated spectrum rules have resulted in spectrum underutilization originating by the fact that transmissions are not continuous in time, frequency and space domains. Idle spectral ranges are referred to as spectrum holes and have been recognized as a valuable resource for providing communications services. Cognitive Radios (CR), as enabled by the frequency agile software definedradio PHY layer, can use these gaps found in time, frequency and space domain if they are allowed to transmit on spectral areas currently licensed to various radio services. CR network though have to operate transparently to the licensee radio system (also referred to as Primary system) by respecting its interference criteria. Transmitting in spectrum holes when and where Primary system is idle is called Secondary use of spectrum.
Cognitive Radio Technology and secondary use of spectrum can implement autonomous and self-deployed communication networks whenever and wherever needed. These networks can be classified as centralized and distributed from the architectural point of view, cooperative and non-cooperative from the spectrum allocation behavior point of view and overlay and underlay from the spectrum access technique point of view [2].
In this paper we study the performance of a modified Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) MAC as the Spectrum Sharing Algorithm for a distributed, overlay CR Network. We implement three backoff algorithms for the CSMA/CA and we compare their behavior in an overlay operation. Moreover we introduce a new decentralized slot division multiple access scheme based on CSMA/CA to provide more efficient spectrum hole utilization than that obtained by the modified CSMA/CA.
Figure 1: Spectrum Pooling Environment.
2.Spectrum Pooling And MAC Design Issues
As in [7] we study the case where the Primary system utilizes some combination of TDMA/FDMA access scheme and thus its spectral occupancy is similar to that of Fig.1a with gray areas representing Primary system transmissions. Unavoidably, every possible CR network that would be allowed to operate as a secondary system would operate in an intermittent manner in recurrent cycles of scan for time τscan - and - transmit for time TS-τscan, where TS is the scan period and τscanis the time needed for the spectrum measurement and measurements broadcast function, or scan delay. This recurrent operation must be frequent enough, depending on the Primary system that owns the spectral area, in such a way that the overlay system meet its design targets [3] and respect the interference criteria of the Primary system. A flexible enough modulation scheme for the secondary system that would fill the spectrum holes found during the scan period is OFDM. If each Primary system subchannel contains an integer number of OFDM subcarriers then by "turning-off" those subcarriers that correspond to occupied channels, the remaining subcarriers could be transmitted without causing interference to the Primary system. This is shown in Fig.1b and, of course, for each scan period the OFDM symbol formulation would be different.
For exactly TS-τscanthe OFDM symbol formulation is constant and provides a constant transmission rate to the MAC layer. We call this time useful time. Moreover transmission rate is zero during the scan procedure for τscan. At that time period MAC layer must refrain from transmitting and must hold incoming higher layer traffic. A MAC protocol designed for such an operation must be able to handle as well the rapid and continuous altering of transmission rate provided by the PHY layer as the continuous stops in transmission.
scan periodTS depends on the underlying Primary system's specifications. Smaller slot duration of the TDMA structure and higher traffic time variations of a Primary system demand for more frequent secondary system scan procedures, thus smaller TS. scan delayτscandepends Primary on the total bandwidth that is chosen for overlay operation fH-fL. Higher bandwidth needs more time to be scanned. On the other hand higher bandwidth provides also higher transmission rates introducing a fundamental trade-off for the design of secondary overlay systems between transmission rate and useful time. Moreover, different sensing algorithms need longer processing times and provide different performance on sensing error and false alarm probability. Depending on the underlying Primary system and its interference tolerance metrics, CR terminals may choose different sensing methods to obtain the required sensing error probabilities. On the other hand the digital signal processors industry continuously provide us with higher processing speeds and what today is ideal tomorrow may be feasible. A scheme of this performance trade-offs as well as the industry and algorithm complexity trends is given in Fig.2. It is clearly shown that a MAC protocol for a secondary overlay system must be robust and operational in a wide range of value pairs TSand τscan.
Figure 2: Tx Rate to Useful Time tradeoff.
3.CSMA/CA Implementation
We implement the 802.11 DCF MAC protocol with necessary modifications that enable its operation in a secondary overlay manner and we name the new MAC protocol Overlay CSMA/CA (O-CSMA/CA). In the following we emphasize on the modifications that were performed on the 802.11 DCF protocol.
3.1Access Scheme
The protocol is in operational state between successive spectrum scans procedures, exactly for time TS-τscan. During the useful time, transmission rate is considered constant. During the scan procedure, that is for time τscanthe protocol ceases transmission attempts and pauses its state.
The basic operation of the MAC protocol is by successive frame exchange sequences (FES) RTS-CTS-DATA-ACK as in 802.11 DCF. Each transmitter before attempting to transmit, it must find the carrier to be idle for a time period of DIFS seconds. After deferring for the DIFS period the station selects a backoff value for an additional deferral time before transmitting. This backoff period corresponds to an integer number of time slots of the protocol and is selected according to some of the algorithms that are described in subsection 3.5. From now on it is referred to as backoff value. When some other transmission is detected the backoff procedure pauses and starts over when the medium is found to be idle for one DIFS period. If a collision occurs the stations that were involved have to restart the access procedure with DIFS period and a new backoff value.
3.2Virtual Carrier Sensing and Timeouts
The virtual carrier sensing mechanism is implemented as a decreasing time counter called NAV (Network Allocation Vector) that shows in time slots units a prognosis for how much longer the medium is expected to be busy for the current FES. But in a spectrum pooling environment a FES is very likely to finish after one or more scan procedures. The transmission rates can be different after the scans and thus a different virtual carrier sensing mechanism must be implemented.
In O-CSMA/CA the "DurationID" field of the transmitted packets instead of carrying direct information on the time needed until the end of the ongoing FES, as in 802.11, it holds the DATA packet size that is going to be transmitted. Moreover, each terminal not participating in the FES sets its NAV according to the type of the received packet, the DATA packet size and the current transmission rate accordingly. NAV is not set for the whole remaining FES, as in 802.11, but only for the next expected packet, either it is a control packet (CTS, ACK) or it is a data packet, plus two SIFS periods. DurationID carries, when necessary, only the upcoming data packet size because control packet sizes are constant and known. The reason for this is that it is not known how many scan procedures will take place and how many times the transmission rate will be altered until the FES finishes. Additionally, before setting the NAV, it is checked if there is enough time before the upcoming spectrum scan, for the next packet of the FES to be sent. If not, then stations do not set the NAV before the upcoming scan, in order to obtain the updated-valid transmission rate.
3.3Back Off Mechanism
The intermittent way that O-CSMA/CA operates necessitates the modification of the way the backoff counter decreases. In order to preserve the fairness of the protocol, the backoff decrease must pause not only when a transmission is detected and when the MAC freezes its state (during spectrum scan). It must pause at a specific time point before the next spectrum scan starts, which is called last Tx opportunity. This is explained below using an example.
Fig.3 depicts two CR terminals that contend for the medium by decreasing their backoff counters. As soon as a backoff counter reaches zero the terminal win the contention and transmits its RTS control packet. In Fig.3a the backoff procedure is presented without modifications and results to a collision because both backoff counters zeroed before the scan start time point, and both had to wait for the scan to finish. This example is not a rare case during MAC operation and, thus, the backoff countdown must pause when the current time crosses the tlastOpportunity time point. The last Tx opportunity time point is defined as the time point at which the RTS packet of size LC to be transmitted with rate R can just fit in time before the upcoming spectrum scan. In Fig.3b CR1 and CR2 simultaneously pause their backoff procedure and priorities are preserved.
3.4.Dynamic Data Packet Fragmentation
The case in which a data packet is not being sent because there is not enough time before the upcoming spectrum scan, is quite frequent. If the size of the packet that would fit in the remaining time is larger than a minimum Packet Size threshold then the Data packet is fragmented to two in order not to waste the time until the upcoming scan. The minimum Packet Size Threshold is also a parameter of the protocol. This function is the one that renders the protocol operation feasible at values of useful time TS-τscan in the order of magnitude of LD/R, where LD the packet size and R the mean transmission rate provided by the PHY.
Figure 3: Back off procedure.
3.5Back Off Algorithms
The standard protocol performance has been thoroughly studied and it has been shown that the backoff distribution is crucial to its performance. In O-CSMA/CA we implemented the following backoff algorithms namely standard, additive and multiplicative.
standard The initial contention window size is CW0. Upon failed transmission the contention window is doubled. The Contention window is reset upon successful transmission.
additive As proposed in [5] for the additive algorithm each time upon a failure in transmission the contention window is increased by a constant value ω while in case of a successful transmission the contention window is decreased by ω with probability δ.
multiplicative In [1] the increase of the contention window is the same as in the standard backoff but after a successful transmission the contention window decrease to a fraction of the current value, that is CW= δxCWcurrent, with δ lying in the interval 0 to 1.
4.Distributed Slot Division Multiple Access (DSDMA)
In this section we develop a new MAC protocol based on the O-CSMA/CA described in the previous Section, to improve the capacity by eliminating the collisions that is the dominant factor of the protocol performance degradation.
A major assumption for the protocol to operate is that the number of Active Stations N is known. This knowledge can be obtained for example by counting signs of life[6]
By the term Active Stations we are referring to stations that contend for the medium and for the time of this contention they operate on asymptotic conditions, that is always they have packets queued for transmission. This is valid in the sense that in certain communication services, data traffic statistics has the form of periods of continuous packet transmission, as in streaming services. Next we describe the two basic functions of the protocol namely Slot Monitoring and Backoff Selection.
Figure 4: Slot Monitoring Function
4.1Slot Monitoring Function
Each Station except from reading from each received packet the DurationID field for setting the NAV it also extracts the Address1 or Address2 field, which refers to the transmitter of each FES. For RTS and DATA packet types Address1 refers to the Transmitter of a FES while Address2 refers to the Receiver. For CTS and ACK packet types Address 2 refers to the Transmitter. Each station by knowing the transmitter of the FES, also knows to whom belongs the current slot that its own current backoff value indicates. This is shown in the example of Fig.4 where for Station STA4 slot index 9 belongs to STA3, slot index 5 to STA2 and slot index1 to STA1, while the remaining slots don't belong to anyone. Similar to the analysis of Cali in [4], the term slot corresponds to the time between two decrements of the backoff value of a station. The time interval between two consecutive slot time beginnings may be much longer than the protocol's slot time size, as it may include the transmission of FES.
Each station maintains internally a Slot Allocation Table, each entry of which shows the holder of the slot. Note that the indexing is different for each Station and depends on the time that the station begun to backoff. For example slot index 4 for STA1 corresponds to slot index 5 for STA4 and belongs to STA2.
4.2Back Off Selection Function
As shown, the Slot Monitoring Function enables stations to know which slots are occupied and which are idle. So they can set their backoff values for one of the idle slots and avoid colliding with a station that already holds his own slot. The Contention Window size is set equal to N+1. After a successful transmission a station becomes holder of the slot it used and continues transmitting there by setting always each back off value to N+1. This access scheme algorithm is shown in Fig.5. The Contention Window size is chosen as N+1 in order to always exist one idle slot. This idle slot is used by new stations to be able to transmit their initial message and become members of the Active Stations.
After the access scheme stabilizes each station holds each own slot and the system resembles to some kind of distributed TDMA scheme where no collisions exist, except from the beginning and until every node becomes a slot holder. This state is the no-collisions state. The overhead of RTS, CTS and ACK packets, though, is needed to accommodate the Slot Monitoring Function for new Active Nodes that are hidden or exposed and of course to accommodate already active nodes' virtual carrier sensing mechanism. For now, we assume that N is known and in Section 5 we study its performance for time periods that N is constant. This can also be regarded as a performance limit of DSDMA which is achieved while operating in such time periods.
Figure 5: DSDMA Back off Selection
5.Simulation Studies
The physical channel was considered to be ideal, thus the only reason behind erroneous reception was the collision between two or more concurrent transmissions.
We model the Primary system's band as an M/M/m/m Markovian chain with varying arrival rate and throughput. In the following τscan is normalized to the TS and the measured throughput is normalized to the mean PHY rate Ε[R]. Moreover all stations are operating in asymptotic conditions and the measured throughput is the saturation throughput.
Two types of experiments were performed for each described protocol: throughput as a function of active nodes, and throughput as a function of scan period and scan delay. Extensive simulations for the performance evaluation of the protocols operating in secondary - overlay manner were carried out for various parameters. Here we present some indicatory results.
Fig.6 through Fig.9 present throughput as a function of Active Nodes N for 2ms scan period and normalized scan delay 0.2. In Fig.9 the terms best-standard, best-multiplicative, best-additive imply that for each value N the best possible protocol parameters (δ, ω, CW0) were chosen for each protocol, between several simulations.
In Fig.9 an ideal theoretical limit of DSDMA is also presented. This theoretical limit is calculated following the virtual transmission time analysis found in [4]. In DSDMA when no-collisions state has been reached, after a DIFS period and one protocol time slot, the current slot Holder initiates a FES by sending the RTS message. The FES ends with the ACK sent by the receiver. We assume a virtual transmission time to be the time that all N stations have sent one packet. Recall that there is always an idle slot in DSDMA where no-one transmits except from new stations. For constant DATA packet length LD, DATA MAC-PDU header length LDHEADER, control packet lengths LC, time slot duration tslot we obtain:
/ (1),which gives the theoretic throughput limit of DSDMA as a function of N. The above equation implies perfect synchronization between FES start/end points and scan procedures that is FES are not interrupted due to scan procedures and all packets are sent without the problem described in Section 3.2. This is not realistic, especially for small scan periods TS, and that's why there is a distance between the theoretic limit and the simulation results for DSDMA throughput. The DSDMA performance improvement over the three other protocols is obvious.