Coexistence of Heterogeneous Cellular Networks

Abstract

Many wireless standards for cellular networks (e.g., IEEE 802.11af and IEEE 802.22) have been developed or are currently being developed for enabling opportunistic access to spectrum using cognitive radio (CR) technology. When heterogeneous cellular networks that are based on different wireless standards operate in the same spectrum band, coexistence issues can potentially cause major problems. Enabling coexistence via direct coordination between heterogeneous cellular networks is very challenging due to incompatible MAC/PHY designs of coexisting networks, the conflict of interest issues, as well as customer privacy concerns. This chapter introduces a number of research problems that may arise in the context of coexistence of heterogeneous cellular networks, namely, the hidden terminal problem, the multichannel broadcast problem, the spectrum sharing problem, and the channel contention problem. This chapter also identifies the major challenges for addressing these problems, proposes the guidelines for devising potential solutions, and provides results of performance evaluation on the proposed solutions.

Introduction

Industry and research stakeholders have launched standardization efforts to enable the secondary networks’ utilization of unused spectrum by leveraging cognitive radio (CR) technology. These efforts include IEEE 802.22 wireless regional area networks (WRAN) [22], IEEE 802.16h Cognitive WiMax, IEEE 802.11af (WiFi over TV white space) [20], ECMA 392 (WPAN over TV white space) [8], etc. All of these standards rely on CR technology to overcome the challenging vertical or incumbent coexistence problem between primary and secondary networks as well as the horizontal coexistence problem between secondary networks.

Heterogeneous vs. homogeneous coexistence:

There exists a significant body of work on vertical coexistence [5, 6], and it has been attracting significant interest from academia and industry. In contrast, horizontal coexistence has garnered less attention thus far. Horizontal coexistence can be further categorized into:

• Heterogeneous coexistence that refers to the coexistence of networks that employ different wireless technologies (e.g., the coexistence between WiFi and Bluetooth [19, 50], the coexistence of heterogeneous wireless networks over TV white space [21]);

• Homogeneous coexistence (aka self-coexistence) that refers to the coexistence of networks that employ the same wireless technology (e.g., neighboring CR networks of the same type [3, 31], or neighboring 802.11 hotspots [30]).

This chapter has a focus on the heterogeneous coexistence between secondary cellular networks that employ different wireless technologies and uses the term “cellular network” to denote a CR-enabled cellular network operating over TV white space.

Existing coexistence schemes:

The coexistence schemes for wireless networks can be broadly classified into two categories.

• A noncollaborative coexistence scheme is the only feasible approach when there are no means of coordination between the coexisting networks, such as the coexistence of WiFi and ZigBee networks [19, 50].

• A collaborative coexistence scheme can be employed when coexisting networks can directly coordinate their operations, such as the self-coexistence schemes for 802.22 networks [3, 31].

Major challenges:

Existing coexistence schemes fail to adequately address the heterogeneous coexistence problem in TVWS for a number of technical and policy reasons. Noncollaborative schemes cannot facilitate the coexistence among heterogeneous networks due to their incompatible MAC strategies. Collaborative strategies may require the exchange of potentially sensitive information (e.g., traffic load, bandwidth requirements) across different networks to negotiate the spectrum partitioning [47, 48], which could raise conflict-of-interest issues and customer privacy concerns for competing wireless networks or service providers. Moreover, it is difficult to find a third party that can serve as a global or centralized decision-maker that supervise all heterogeneous networks and allocate spectrum them.

Problems in focus:

This chapter studies a few challenging problems that are related to the medium access control (MAC) layer protocol design for coexistence of heterogeneous coexistence of cellular networks.

• Hidden terminal problem can be potentially exacerbated by the heterogeneity of the PHY/MAC designs of the coexisting cellular networks, especially when TDM-based cellular networks coexist with CSMA-based networks.

• Broadcast failure problem may arise over a single broadcast channel when the broadcast channel is reclaimed by a primary (or licensed) user that has a higher priority of accessing the spectrum, or when secondary users in coexisting cellular networks moves into a region where the co-channel interference is caused.

• Spectrum sharing among coexisting heterogeneous cellular networks is very challenging via direct coordination, while a mediator system is able to establish an indirect coordination mechanism for spectrum sharing between networks.

• Channel contention is a distributed inter-network coordination process that enables a CR network in need of more spectrum resources to acquire channels from neighboring networks by exchanging control messages via a local controller.

The following sections discuss each problem and its corresponding solution respectively.

Hidden Terminal Problem

In wireless networks, when more than one transmitter-receiver pairs share a channel, the hidden terminal problem can occur. This problem occurs when a transmitter is visible from a receiver node, but hidden from (or out of the sensing range of) another transmitter that is visible from the same receiver. This leads to packet collisions at the receiver when the two transmitters send packets simultaneously. The hidden terminal problem in single-channel environments has been widely studied. In single-channel systems employing CSMA/CA, a handshaking procedure (i.e., using RTS/CTS control packets [29]) has been adopted to address the problem. For handling the hidden terminal problem in multichannel wireless networks, some have proposed the use of a fixed control channel to facilitate a handshake procedure between two transceivers [40].

Unfortunately, the aforementioned handshaking procedures do not work when the hidden terminal problem is caused by heterogeneous coexistence. This is because the hidden terminal problem in heterogeneous coexistence is different from those mentioned above and is due to the fact that the coexisting networks cannot understand each others’ control messages because they use different air interfaces (i.e., PHY/MAC stacks). An example is shown in Fig. 1 in which: an 802.22 network is coexisting with an 802.11af network. The 802.22’s MAC protocol is TDM (time-division multiplexing) based with PHY resources allocated using OFDMA, while 802.11af relies on a contention-based CSMA protocol. Because the 802.22 base station (BS) and the 802.11af access point (AP) are hidden from each other, packets sent by the BS and the AP may collide at the 802.11af receiver node. Previous works have shown that enabling fair and efficient spectrum sharing is challenging in scenarios where a network with a contention-based MAC protocol (e.g., 802.11af) coexists with a network with a tightly scheduled TDM-based MAC protocol (e.g., 802.22 or 802.16h) [10, 11, 13, 27, 39, 44]. IEEE 802.22 is the first worldwide wireless standard based on CR technology for utilizing TVWS in rural areas. The 802.22 standard prescribes incumbent protection techniques necessary for secondary users to operate in licensed TV bands, while 802.16 does not. It is assumed that the TDM device can distinguish a packet sent by a CSMA device from the background noise. This section focuses on the particular type of heterogeneous coexistence between TDM and CSMA networks.

Fig. 1

An example of the hidden terminal problem caused by heterogeneous coexistence

The hidden terminal problem in this heterogeneous coexistence scenario induces two types of packet collisions:

• 1. Collisions at the receivers of a TDM MAC network that are caused by hidden transmitters of a CSMA MAC network

• 2. Collisions at the receivers of a CSMA MAC network that are caused by hidden transmitters of a TDM MAC network

This section presents a coexistence scheme that mitigates the packet collisions caused by the hidden terminal problem in a particular type of heterogeneous coexistence scenario – viz., coexistence of TDM and CSMA MAC networks (e.g., 802.22 and 802.11af networks).

• To mitigate the first type of collisions, a beacon transmission mechanism is introduced to enable the receivers in a TDM MAC network to send beacon signals to prevent the hidden CSMA devices from accessing the shared channel, while transmitters of the TDM MAC network occupy the channel.

• To mitigate the second type of collisions, a dynamic quiet period mechanism is presented for the TDM MAC networks. This mechanism requires a TDM transmitter to dynamically determine the end point of its current quiet period (QP) in order to reduce the probability of packet collisions. The length of the quiet period is dynamically adjusted in order to maintain long-term weighted fairness in channel access between the coexisting TDM and CSMA networks .

Two Types of Collisions

Type 1: Collisions at the TDM Network Receiver

This type of collisions occur when a TDM receiver is located within the transmission ranges of both the TDM and CSMA transmitters, but the two transmitters are hidden from each other. To reduce this type of collisions, the TDM network has to prevent the CSMA transmitter from transmitting while the TDM transmitter is transmitting.

A straightforward solution to mitigate packet collisions in this scenario is to require the TDM receiver to emit beacon signals during a small time fraction at the beginning of every time slot. This time fraction is called the beaconing fraction of a time slot. Here, it is assumed that the TDM receiver is within the CSMA transmitter’s sensing range – i.e., the CSMA transmitter can sense the TDM receiver’s beacon signals. The beacon signal’s presence in the channel will cause the CSMA transmitter to suspend transmissions. It is reasonable to assume that the coexistence enabling system (e.g., 802.19.1 system) mandates the use of beacon signals by the TDM receivers to facilitate coexistence, since the TDM MAC networks are registered.

During the beaconing fraction of a time slot, the TDM transmitter stops transmitting, and the TDM receiver emits beacon signals such that the coexisting CSMA transmitter can detect the beacons and refrain from transmitting in the channel. As a result, the collision-free receptions at the TDM receivers can be guaranteed. Requiring the TDM receiver to transmit beacons can be a costly overhead and thus should be required only when its benefits outweigh the costs .

Type 2: Collisions at the CSMA Network Receiver

This type of collisions occur when the CSMA receiver is located within the transmission ranges of both the TDM and CSMA transmitters, but the two transmitters are hidden from each other. In this scenario, packet collisions occur because the TDM transmitter initiates transmission before the CSMA transmitter has finished transmitting its data packets.

A specific example of this scenario is shown in example in Fig. 2. In the figure, the first TDM frame transmitted by the TDM transmitter in the (N + 1)-th superframe collides with the CSMA transmitter’s ongoing packet transmissions which started in the QP of the N-th superframe and has continued on past the QP. In this situation, requiring the CSMA receivers to use beacons is not a plausible solution, because they are not under the control of the 802.19.1 system.

Fig. 2

Collisions at the end of the N-th frame’s QP. Dotted-line rectangles represent the CSMA data packets

During a QP, a TDM transmitter suspends its transmission, and it terminates the QP at the scheduled end time point by transmitting a prescribed number of beacons. After transmitting a prescribed number of beacons, the TDM transmitter terminates the current QP and starts the TDM frame of the next superframe. Note that the TDM transmitter simply terminates the QP at the scheduled time point, and it will not wait until the ongoing transmission for CSMA data and/or ACK packets to be finished.

Beacon Transmission by TDM Receiver

Consider an 802.22 WRAN co-located with an 802.11af WLAN, both sharing the same TV white space channel. To mitigate the first type of collisions, it is recommended to support two modes at the TDM receiver: beaconing and non-beaconing modes. It can switch from one mode to the other depending on the channel conditions, and this procedure of switching contains two steps:

• 1. First, the network entity performs channel evaluation to determine when to switch from one mode to the other. The TDM receiver measures the received SIR, estimates the channel capacity in the two modes, and makes a decision of which mode to operate in.

• 2. Then, the TDM receiver will notify the TDM transmitter if it decides to switch to the beaconing mode. In the beaconing mode, the TDM transmitter has to stop transmitting in the beaconing duration.

Beaconing by TDM receivers will incur additional overhead and waste the channel time. That is why a dynamic switch is needed between the two modes to balance the tradeoff between the performance loss due to interference caused by CSMA packets, and the beaconing overhead.

First, calculate the channel capacity in each of the two modes. By estimating the channel access time and packet error rate, the capacity of the shared channel, C, is:

$$\displaystyle \begin{aligned} C=\left(1-\frac{u}{t}\right)\cdot (1-\epsilon), \end{aligned} $$

(1)

where t is the length of a time slot, u is the duration of beaconing in a time slot, and ε denotes the packet error rate on the shared channel at the TDM receiver. In (1), $\left (1-\frac {u}{t}\right )$ represents the ratio of channel access time used for non-beaconing transmission and the length of a time slot and (1 − ε) shows the rate of successful packet reception given possible packet errors. The packet error can be caused by a few factors, such as noise, interference, fading, etc.

The reduction of channel capacity can be caused by two factors in the considered scenarios of heterogeneous coexistence, namely, the beaconing duration, and the inter-network interference. In the beaconing mode, the beaconing duration, u, is the major cost that may lower the channel capacity, and the inter-network interference can lead to a high packet error rate (i.e., a low channel capacity according to (1)) in the non-beaconing mode. The effect of fading may vary with time, geo-locations, or frequency, and it is independent of whether the beaconing mode is used.

Let γ denote the maximum achievable SIR perceived by the TDM receiver on the shared channel. In [38], Shellhammer describes a way of estimating ε based on γ: the symbol error rate (SER), ρ, can be estimated based on γ; then, ε can be calculated based on the SER. If the modulation is BPSK, the SER $\rho = Q[\sqrt {2\gamma }]$, where the function Q(⋅) is the integral of the tail of a normalized Gaussian probability density function [37]. The packet error rate in a packet of m symbols is the probability that at least one symbol is incorrect,

$$\displaystyle \begin{aligned} \epsilon=1- (1-\rho)^m. \end{aligned}$$

Channel capacity in beaconing mode:

To avoid the first type of collisions, the TDM receiver is allowed to block the medium by emitting beacon signals in every time slot. The capacity of the shared channel in this mode can be expressed as

$$\displaystyle \begin{aligned} C_b=\left(1-\frac{u}{t}\right)\cdot (1-\epsilon). \end{aligned}$$

The CSMA transmitter could sense an idle channel during a time period of (t − u) in every TDM time slot. To successfully block the medium, the TDM receiver needs to guarantee that the value of (t − u) is less than the time for channel clear assessment (CCA) in CSMA networks. The time for CCA in WiFi networks is 28 μs [25].

Assume the noise source is additive white Gaussian noise (AWGN) N ₀, and the signal-to-noise ratio is represented as E _s∕N ₀, where E _s denotes the signal energy in a symbol. That is,

$$\displaystyle \begin{aligned} \gamma = \frac{E_s}{N_0}. \end{aligned}$$

Given the modulation, the TDM MAC network is able to estimate C _b using γ.

Channel capacity in non-beaconing mode:

If the feature of beacons is disabled, the TDM receiver may experience the first type of collision when there is a nearby CSMA transmitter that is hidden from the TDM transmitter. The channel capacity in the non-beaconing mode can be expressed as

$$\displaystyle \begin{aligned} C_n= \left(1-\frac{u}{t}\right)\cdot (1-\epsilon) = 1-\epsilon. \end{aligned}$$

The fundamental principal of this approach in the non-beaconing mode is to equate the interference power at the TDM receiver, after the receive filter, to the equivalent noise power after the receive filter.

Given the AWGN N ₀, the signal energy in a symbol of period T is related with the symbol power $P_s=\frac {E_s}{T}$. Let B denote the noise equivalent bandwidth of the receive filter for a symbol period of T, and $B=\frac {1}{T}$. The noise power after the receiver filter is given by $P_n=\frac {N_0}{B}$. The ratio E _S∕N ₀ can be expressed in terms of the signal power and the noise power after the receiver,

$$\displaystyle \begin{aligned} \frac{E_s}{N_0}=\frac{P_s T}{P_n T}=\frac{P_s}{P_n}, \end{aligned}$$

Since the TDM receiver has the same TVWS channel model as the interferer (CSMA transmitter), the noise power after the receive filter is equal to the value of the interference signal, $P_I^r$, after the receive filter [38], i.e., $P_n = P_I^r$. Therefore,

$$\displaystyle \begin{aligned} \gamma = \frac{E_s}{N_0}=\frac{P_s}{P_I^r}, \end{aligned}$$

and C _n can be accordingly estimated .

An approach of switching between two modes:

In the proposed approach, the non-beaconing mode over the shared mode is attempted first. If the maximum achievable SIR on the channel is not sufficiently high, it is prescribed that the beaconing mode for TDM networks will block the medium and prevent CSMA devices’ access to the channel. One possible approach is introduced here for determining when to enable the beaconing mode.

The network determines which mode for the the TDM receiver to operate in, for a given channel, by comparing γ with the required SIR threshold parameter γ ^∗. To obtain the value of γ ^∗, first solve for ε in the equation C _b = C _n and then find the SIR value corresponding to the solved ε, which is used as the value of γ ^∗.

• 1. If γ ≥ γ ^∗, the TDM receiver operates in the non-beaconing mode. The benefits of non-beaconing mode (e.g., low control overhead) outweigh the benefits of beaconing (e.g., no collisions).

• 2. If γ < γ ^∗, the TDM receiver operates in the beaconing mode. The benefits of beaconing mode outweigh the benefits of non-beaconing mode .

Dynamic Quiet Period at TDM Transmitter

In the proposed approach, the TDM transmitter chooses the appropriate starting time point for TDM transmission in order to avoid overlapped TDM and CSMA transmissions, and it starts occupying the channel immediately after the transmission of a whole CSMA packet and before the transmission of the next CSMA packet.

Quiet Period

In TDM MAC networks, channel access occurs in scheduled blocks of time slots; in CSMA MAC networks, channel access is contention based, and there is no predetermined schedule for channel access. A “universal” superframe structure is representative in TDM MAC networks with coexistence mechanisms (e.g., 802.22 or 802.16 networks). Time is divided into superframes, each superframe is divided into frames, and each frame contains a number of f time slots.

In 802.16h, a quiet period (QP) that contains an integer number of frames is periodically scheduled [22, 36]. During a QP, the BS suspends its data transmissions to provide channel access opportunities for CSMA networks. Similarly, a QP is scheduled at the end of every superframe, and non-QP frames are considered as data frames.

Let q denote the number of frames contained in a QP, and let d denote the number of data frames contained in a superframe. Thus, the number of frames in a superframe is d + q, and the number of time slots in a superframe is (d + q)f. A TDM network starts transmitting data immediately after the end of a QP (i.e., end of a superframe). The value of q quantifies the number of frames that TDM networks can share with CSMA networks during a superframe. The values of d and q are predetermined collectively by the coexisting TDM MAC networks or determined by the coexistence mediator. During a TDM QP, the CSMA networks sense an idle channel and start to transmit CSMA packets.

The proposed approach is built on top of the superframe structure of TDM MAC networks, and it adopts an innovative way of dynamically determining the length of the quiet period, which reduces the second type of collisions as well as maintains the weighted fairness for the TDM MAC network in channel access. It employs the following algorithms to achieve these objectives.

• Collision avoidance algorithm. The TDM transmitter monitors the data traffic during the QP and captures the ACK packets emitted by CSMA networks. To avoid collisions, the TDM transmitter is allowed to terminate the QP immediately after detecting an ACK packet. This will lead to a shortened QP in the current superframe and an advanced frame in the next superframe, which hurts the short-term weighted fairness for the TDM MAC network.

• Weighted fairness maintenance algorithm. By counting the number of time slots lost in previous shortened QPs, the TDM transmitter is able to determine whether it needs to increase the length of the next QP such that the long-term fairness can be maintained.

Collision avoidance:

In either saturated or unsaturated WLANs, the aggregated traffic pattern (the inter-arrival time between WLAN packets) approximates a Poisson distribution [7, 49]. The experimental results in [19] show that the inter-arrival time of WLAN frame clusters fits a Pareto model. It is assumed that the packet arrival of the WLAN follows a Poisson distribution. Let λ denote the WLAN data packets’ arrival rate, and thus the mean inter-arrival time is 1∕λ.

Definition 1

When the TDM network enters a scheduled QP,

• The elapsed QP is the time duration from the start of the QP to the current time point.

• The residual QP is the time duration from the current time point to the expected end of the QP.

Figure 3 illustrates the elapsed QP and residual QP.

Fig. 3

Illustration of the elapsed QP and residual QP in a superframe of the TDM MAC network

To avoid collisions to the potential hidden CSMA receiver at the end of the QP (defined as the second type of collisions), the TDM MAC network (or TDM transmitter) has to make a decision upon detecting a CSMA ACK packet: Is the residual QP long enough for completing another CSMA packet transmission?

• 1. If the answer is “yes,” the TDM network will keep silent and wait for the next CSMA packet arrival (i.e., the next detected ACK).

• 2. If the answer is “no,” the TDM network should terminate the QP by immediately starting TDM transmissions (or beacon transmissions) such that the CSMA receiver would refrain from operating in the channel.

As a result, it enables the TDM MAC network to autonomously terminate the QP at an “appropriate” time point.

Let e _i denote the duration of the elapsed QP and r _i denote the duration of the residual QP, in the i-th superframe, both of which are on a time slot basis. Let l _d and l _a denote the mean length of WLAN’s data packets and the length of ACK packet, respectively. Recall that the number of time slots in a frame is f. Let p denote the probability that the next CSMA packet transmission can be finished in the residual QP, r _i. Upon detection of an ACK packet, the length of the residual QP is r _i, and the TDM network calculates the probability p.

• When r _i < l _d, the residual QP is smaller than the mean length of a WLAN data packet, and thus p = 0.

• When r _i ≥ l _d, the residual QP is longer than the mean length of a WLAN data packet, and the next CSMA packet transmission can be finished in the residual QP, only if the packet arrives in next (r _i − l _d) slots.

  $$\displaystyle \begin{aligned} p &= \mathbb{P}\{\text{CSMA pkt arrival in next }(r_i- l_d)\text{ slots}\} \notag\\ &= 1- \mathbb{P}\{\text{no CSMA pkt arrival in next }(r_i-l_d)\text{ slots}\} \notag\\ &= 1-e^{-\lambda (r_i-l_d) }. \end{aligned} $$

  (2)

Decision rule of dynamic QP mechanism:

Based on the calculated value of p, the TDM network is able to decide whether to terminate the QP upon detection of CSMA ACK packets, using the following decision rule, in which q _i denotes the length of QP (on a frame basis) in the i-th superframe, and the initial value q ₁ = q. How to dynamically update the value of q _i will be described later.

• 1. When e _i < q _i f, the QP of the current superframe has not finished. Upon the detection of a CSMA ACK packet,

  • a. The TDM network predicts that the residual QP is insufficiently long for completing a next CSMA packet transmission if p < τ. Then, it terminates the QP by immediately transmitting beacons;

  • b. The TDM network predicts that the residual QP is long enough for completing a next CSMA packet transmission if p ≥ τ. Thus, the TDM transmitter waits for the next ACK packet without sending any beacons.

  τ denotes the threshold that represents the expected probability that the next CSMA packet transmission can be finished in the residual QP.

• 2. When e _i = q _i f (i.e., the residual QP r _i = 0), it means that the elapsed QP length exceeds the original length of QP in the i-th superframe, and the TDM network has to terminate the QP immediately even without detecting any ACK packet. In unsaturated CSMA networks, the waiting time before a CSMA packet arrival might be very long, which degrades the channel utilization. This step prevents the case that the waiting time is longer than the length of the current QP .

Simulation

This section compares the proposed approach with the fixed QP (FQP) mechanism, and considers a heterogeneous coexistence scenario between TDM networks (e.g., 802.22 networks) and CSMA networks (e.g., 802.11 networks). In each TDM network, there is one BS and multiple user devices, and the BSs of TDM networks are synchronized. Each CSMA network is placed at a location such that the AP is hidden from the BS. All coexisting networks are able to identify available TVWS channels by making queries to the TVWS database or leveraging the spectrum sensing techniques.

A synchronized superframe structure is simulated for all coexisting TDM networks to share the same channel. In each data frame, the TDM receiver is required to adopts the beacon transmission mechanism to prevent the collisions to the TDM packet reception when necessary. In each quiet period, the TDM transmitters suspend their traffic and observe the possible CSMA transmission over the channel to carry out the dynamic QP mechanism. The decision-making threshold τ = 0.5, which implies that in the residual QP, the probability of the next complete CSMA packet transmission is required to be greater than the probability of an incomplete transmission. The length of QP is counted by the number of frames, and each frame contains ten time slots. The CSMA packet duration consists of multiple time slots. The CSMA packet arrival rate quantifies the probability that the CSMA packet arrives in a time slot. In the CS-based spectrum access scheme, $\frac {s}{f} = \frac {1}{5}$, which is the fraction of time a device spends on spectrum sensing in every time slot. The simulation parameter values were chosen to be consistent with those used by the 802.22 working group [23, 24].

Normalized Throughput in the Quiet Period

In a quiet period-based approach, the packet collision due to the hidden terminals only happens at the end of a QP.

Define the normalized throughput in the QP as the ratio between the number of time slots for transmitting CSMA packets without collisions during a QP and the total number of time slots in the QP. In general, Figs. 4 and 5 show that the performance of the dynamic QP approach is better than that of the FQP scheme in all cases.

Fig. 4

Normalized throughput under the hidden terminal situation, when varying the basic QP length, l _d = 2 and λ = 0.5

Fig. 5

Normalized throughput when varying the CSMA packet duration, q = 1 and λ = 0.5

As shown in Fig. 4, the gap between SHARE and FQP in terms of the normalized throughput narrows as the length of the QP increases. In contrary, the throughput gap between SHARE and FQP becomes wider when the CSMA packet duration l _d increases, as shown in Fig. 5. The reason has been explained above: with an increased CSMA packet duration, the collision probability increases in every QP, which decreases the normalized throughput.

The purpose of this set of simulations is to investigate how much is the performance gain that can be obtained from the proposed protocol.

• In Fig. 4, the performance gain is approximately 20% when the length of the quiet period is as small as the half of a frame length;

• As Fig. 5 shows, the longer the CSMA packet is, the more performance gain can be obtained (approximately 40% when the CSMA packet length is five slots).

Thus, the proposed protocol has a significant performance gain when a CMSA network that has a long packet length coexists with a TDM network that has a small QP length. Meanwhile, it has no significant performance gain given various packet arrival rates.

Multichannel Broadcast Problem

Broadcast in cellular networks is typically offered as a push-type service for distributing important control information from the base station to a group of users that share radio resources. Moreover, broadcast enables the low-cost delivery of large volumes of popular content (e.g., multimedia content) to users in a cell. There are many existing solutions to broadcast in the market, including mobile TV broadcasting (DVB-H) [32], audio casting, massive software updates, content delivery over WiMax [28], and broadcast (or multicast) service offered by 3GPP in LTE cellular networks [15].

A single channel, referred to as a broadcast channel, is usually used by a base station to distribute the same content to a group of users that subscribe to the same service [9]. Meanwhile, a base station may employ multiple broadcast channels for delivering different contents to groups of users that subscribe to different services. A user or a content subscriber is able to successfully receive the broadcasted content when (1) the broadcast channel is available and (2) the user is located within the transmission range of the base station.

In dynamic spectrum access, the broadcast failure problem can occur due to the temporal and spatial variations in channel availability. Specifically, the primary users (PU, or licensed users) may reclaim the spectrum band where broadcast channels reside and the unlicensed users have to vacate this channel according to the requirement for protection of licensed users in CR networks. On the other hand, a secondary user is likely to move into a region where the interference is caused by coexisting cellular networks. In either case, the broadcast channel becomes unavailable thereby leading to unsuccessful deliveries of broadcasts.

A vast majority of existing work has focused on tackling this problem in multi-hop or ad hoc CR networks. Instead of relying on a single broadcast channel, the control information is transmitted over a preselected set of broadcast channels, which can be derived based on the neighbor graphs [33]. To determine the minimum broadcast schedule length for a CR network, two heuristics are presented and they can produce schedules that have either optimal or near-optimal lengths [2]. In [26], a mixed broadcast scheduling algorithm is proposed under the unit disk graph (UDG) model, which combines the uni-cast and broadcast collaboratively in order to obtain a small broadcast latency. To broadcast over multiple channels, the channel hopping technique is used by cognitive radios without requiring the knowledge of global network topology or the requirement of time synchronization information [41,42,43].

This section focuses on the broadcast failure problem in the context of coexisting cellular networks, i.e., infrastructure-based CR networks. To guarantee the successful broadcast, a base station has to employ a multichannel broadcast protocol – i.e., it delivers contents over multiple broadcast channels using broadcast radios, so as to reduce the chance of colliding with primary users’ transmissions or coexisting networks in the spatial or temporal domain.

This section presents a multichannel broadcast protocol, called Mc-Broadcast, for delivering contents to secondary users that are located in coexisting cellular networks. Every broadcast radio at a base station selectively transmit over a number of channels via a channel hopping process. The channel hopping sequence is generated using a mathematical construct called Langford pairing, such that Mc-Broadcast can only incur a small broadcast latency and guarantee a high successful delivery ratio .

Definition of Langford Pairing (LP)

Given an integer n, Langford pairing is a sequence of length 2n that consists of two 1s, two 2s, …, and two ns and satisfies that there are exactly one number between the two 1’s, exactly two numbers between the two 2’s, …, and exactly n numbers between the two n’s.

Formally, A Langford pairing, {l _i}_{0≤i≤2n−1} of order n, also called a Langford sequence, is a permutation of the sequence of 2n integers {1, 1, 2, 2, 3, 3, …, n, n}, and it satisfies the Langford property: if l _i = l _j, 0 ≤ i < j ≤ 2n − 1, then j − i = l _i + 1.

For example, the sequence l = {3, 1, 2, 1, 3, 2} is a Langford pairing of order n = 3. There is only one number (that is, 2) between the two 1s, two numbers (they are 1 and 3) between the two 2s and three numbers (they are 1, 2 and 1) between the two 3s. Given i = 0 and j = 4, then l ₀ = l ₄ = 3, and j − i = 3 + 1; given other combinations of i and j, the sequence l also satisfies the Langford property.

Slightly different from LP, an extended Langford pairing (ELP) is defined to contain two 0s (note that an LP does not contain any 0s) and that these two 0s be neighboring. Formally, an ELP, $\{l^{\prime }_{i}\}_{0\leq i\leq 2(n+1)-1}$ of order n, which is a permutation of the sequence of 2(n + 1) integers:

$$\displaystyle \begin{aligned} \{0,0,1,1,2,2,\ldots,n,n\}. \end{aligned}$$

The sequence satisfies the Langford property, i.e., if l _i = l _j, 0 ≤ i < j ≤ 2(n + 1) − 1, then j − i = l _i + 1. For example, the sequence

$$\displaystyle \begin{aligned} l'=\{0,0,3,1,2,1,3,2\}, \end{aligned}$$

is an extended Langford pairing (ELP) of order n = 3.

Multichannel Broadcast Process

In a cellular network, the BS and the users in the BS’s service area are secondary users, and they are equipped with CRs operating over broadcast channels. Due to PU’s activities or interference from coexisting networks, a broadcast channel may become unavailable at any time. Therefore, the BS has to broadcast the content over multiple channels to ensure the successful delivery to users, and such a process is called a multichannel broadcast process.

Suppose there are N broadcast channels, labeled as 0, 1, 2, …, N − 1. The BS is equipped with multiple broadcast radios, labeled as r ₁, r ₂, …, r _R, where R is the total number of the BS’s broadcast radios. There are U users s ₁, s ₂, …, s _U in the service area. Every user is equipped with a single radio interface.

Broadcast via Channel Hopping (CH)

To implement the multi-channel broadcast protocol, a BS’s broadcast radio or a user’s radio can hop across multiple broadcast channels to deliver or to receive the broadcast content. Thus, the channel hopping (CH) sequence is chosen to define the order with which a BS’s broadcast radio (or a user’s radio) visits the set of broadcast channels.

Consider a time-slotted communication system, where a global system clock exists. The local clock of each node may be synchronized to the global clock or may differ with the global clock by a certain amount of clock drift. A radio is assumed to be capable of hopping between different channels according to a channel hopping sequence and its local clock. A packet can be exchanged between two radios if they hop onto the same channel in the same time slot.

Then, a CH sequence u of period T can be represented as a sequence of channel indices:

$$\displaystyle \begin{aligned} u=\{u_{0},u_{1},u_{2},\ldots,u_{i},\ldots,u_{T-1}\}, \end{aligned}$$

where u _i ∈ [0, N − 1] represents the channel index of the ith time slot of CH sequence u. If u _i = u _j, ∀i, j ∈ [0, T − 1], the radio using u as its CH sequence stays on the same channel and does not hop.

Given two CH sequences of period T, u and v, if there exists i ∈ [0, T − 1] such that u _i = v _i = h, where h ∈ [0, N − 1], we say that a broadcast delivery occurs between u and v in the ith time slot on broadcast channel h. The ith time slot is called a delivery slot and channel h is called a delivery channel between u and v.

Given N channels, let $\mathcal {C}(u,v)$ denote the set of delivery channels between two CH sequences u and v. The cardinality of $\mathcal {C}(u,v)$ is called the number of broadcast delivery channels, denoted by $|\mathcal {C}(u,v)|$, and $|\mathcal {C}(u,v)|\in [0,N]$. The number of broadcast delivery channels measures the number of channels in which successful broadcast delivery occurs, i.e., the diversity of broadcast delivery channels.

Let $\mathcal {T}(u,v)$ denote the set of delivery slots between two CH sequences u and v, and $|\mathcal {T}(u,v)|\in [0,T]$. The cardinality of $\mathcal {T}(u,v)$ reflects the number of times lots in which successful broadcast delivery occurs within a period .

Broadcast by Multiple Radios

To reduce the broadcast latency, the BS is allowed to use a set of broadcast radios, denoted by $\mathcal {B}=\{r_{1},r_{2},r_{3},\ldots ,r_{R}\}$. Since the BS has multiple radios, the broadcast delivery occurs between the BS and a user s if the broadcast delivery occurs between one of the BS’s broadcast radios and the user s’s radio – i.e., the broadcast delivery occurs between a radio set $\mathcal {B}$ and a user s if there exists a radio $r_{i}\in \mathcal {B}$ such that a broadcast delivery occurs between the CH sequences of radios r _i and s. To simplify the notation, it is recommended to use r _i to denote the CH sequence of the BS’s broadcast radio $r_{i}\in \mathcal {B}$ and use s to denote the CH sequence of user s’s radio.

The set of broadcast delivery channels between the BS with its set of broadcast radios $\mathcal {B}$ and a user s is the union of the sets of broadcast delivery channels between each broadcast radio of the BS and the user s’s radio, i.e., let $\mathcal {C}(\mathcal {B},s)=\bigcup _{r\in \mathcal {B}}\mathcal {C}(r,s)$ denote the set of broadcast delivery channels between the BS with its set of broadcast radios $\mathcal {B}$ and the user s’s radio, and the cardinality of $\mathcal {C}(\mathcal {B},s)$ is called the number of delivery channels, denoted by $|\mathcal {C}(\mathcal {B},s)|$, and $|\mathcal {C}(\mathcal {B},s)|\in [0,N]$.

Similarly, the set of delivery slots between the BS with its set of broadcast radios $\mathcal {B}$ and a user s is the union of the sets of delivery slots between each broadcast radio of the BS and the user s’s radio, i.e., let $\mathcal {T}(\mathcal {B},s)\triangleq \bigcup _{r\in \mathcal {B}}\mathcal {T}(r,s)$ denote the set of delivery slots between the BS with its set of broadcast radios $\mathcal {B}$ and the user s’s radio, and $|\mathcal {T}(\mathcal {B},s)|\in [0,T]$.

An Asynchronous Multichannel Broadcast System

Given a CH sequence u, use rotate(u, k) to denote a cyclic rotation of CH sequence u by k time slots, i.e.,

$$\displaystyle \begin{aligned} rotate(u,k)=\{v_{0},\ldots,v_{j},\ldots v_{T-1}\}, \end{aligned}$$

where v _j = u _{(j+k) mod T}, j ∈ [0, T − 1]. For example, given u = {0, 1, 2} and T = 3, rotate(u, 2) = rotate(u, −1) = {2, 0, 1}.

Define an asynchronous multichannel broadcast (AMB) system $\mathcal {M}$ with CH period T as an ordered pair $(\mathcal {B},\mathcal {U})$:

• $\mathcal {B}$ is the set of CH sequences of period T used by broadcast radios of the BS. Suppose $\mathcal {B}=\{r_{1},r_{2},r_{3},\ldots ,r_{R}\}$, where R is the number of the BS’s broadcast radios, and the BS’s broadcast radio r _i uses the CH sequence r _i in $\mathcal {B}$.

• $\mathcal {U}$ is the set of CH sequences of period T used by the users. Suppose $\mathcal {U}=\{s_{1},s_{2},s_{3},\ldots ,s_{U}\}$, where U is the number of users, and the user s _j’s radio uses the CH sequence s _j in $\mathcal {U}$.

An AMB system must satisfy the rotation closure property: ∀k, l ∈ [0, T − 1], $\forall s\in \mathcal {U}$, there exists $r\in \mathcal {B}$ such that $|\mathcal {C}(rotate(s,k),rotate(r,l))|\geq 1$. And thus the design problem of CH sequences of the BS’s broadcast radios and users’ radios is mapped to the design problem of an AMB system with rotation closure property. And the rotation closure property implies that for all possible clock drifts between the BS and users, every user can have successful broadcast delivery with the BS, i.e., with one of the BS’s broadcast radios.

In other words, in an AMB system, the BS, with each broadcast radio using CH sequences in $\mathcal {B}$, can deliver broadcast messages to all users using CH sequences in $\mathcal {U}$ via a channel hopping process for all possible clock drifts .

Performance Metrics

Given an AMB system $\mathcal {M}=(\mathcal {B},\mathcal {U})$, the following metrics are defined to evaluate its performance.

• Delivery channel diversity. The delivery channel diversity for an AMB system measures the lower bound of the number of delivery channels between the BS and an arbitrarily given user for all possible clock drifts. The delivery channel diversity, denoted by $DIV(\mathcal {M})$, is the minimum number of delivery channels $|\mathcal {C}(\mathcal {B},rotate(s,k))|$ for every $s\in \mathcal {U}$ and every $k\in \mathbb {Z}$ , i.e.,

  $$\displaystyle \begin{aligned} \begin{array}{rcl} DIV(\mathcal{M}) &\displaystyle = &\displaystyle \min_{s\in\mathcal{U},k\in\mathbb{Z}}|\mathcal{C}(\mathcal{B},rotate(s,k))|\\ &\displaystyle = &\displaystyle \min_{s\in\mathcal{U},k\in\mathbb{Z}}|\bigcup_{r\in\mathcal{B}}\mathcal{C}(r,rotate(s,k))|. \end{array} \end{aligned} $$

• Broadcast latency. To quantify the broadcast latency , we define the maximum broadcast latency for a given AMB system as the upper bound of the latency before the first successful broadcast delivery between the BS and an arbitrary user on at least one channel for all possible clock drifts, which can be computed by

  $$\displaystyle \begin{aligned} \max_{s\in\mathcal{U},k\in\mathbb{Z}}\left[\min\mathcal{T}(\mathcal{B},rotate(s,k))\right]. \end{aligned}$$

• Delivery ratio. To measure the proportion of delivery slots in a period, first it is needed to define the delivery ratio for a CH sequence pair. The delivery ratio for a CH sequence pair r and s, denoted by ρ(r, s), is

  $$\displaystyle \begin{aligned} \min_{k,l\in\mathbb{Z}}(|\mathcal{T}(rotate(r,k),rotate(s,l))|/T). \end{aligned}$$

  And then introduce the delivery ratio for an AMB system $\mathcal {M}=(\mathcal {B},\mathcal {U})$, which measures the minimum proportion of delivery slots in all time slots. To be precise , the delivery ratio is

  

Extended Langford Pairing-Based Broadcast Protocols

An AMB system $\mathcal {M}=(\mathcal {B},\mathcal {U})$ is constructed based on the extended Langford pairing (ELP). To illustrate the design of the ELP-based AMB system, it is better to first investigate a simple scenario in which the BS has a single radio, i.e., $|\mathcal {B}|=1$, and there is only a single user, i.e., $|\mathcal {U}|=1$. Then, the problem in a general scenario will be addressed where $|\mathcal {B}|$ and $|\mathcal {U}|$ are generally greater than 1.

CH Sequence Generation

In the ELP-based channel hopping protocol for AMB systems with a single radio pair, $\mathcal {M}=(\{r\},\{s\})$, where r is the only BS radio and s is the only user.

First look at the simple scenario where $|\mathcal {B}|=|\mathcal {U}|=1$, i.e., $\mathcal {B}=\{r\}$ and $\mathcal {U}=\{s\}$.

Consider the original Langford pairing (LP). If N is congruent to 0 or 3 modulo 4, there exists an LP {l _i}_{0≤i≤2N−1} of order N. Suppose both r and s use the CH sequence {l _i − 1}_{0≤i≤2N−1} of period 2N. If s is one time slot ahead, the broadcast delivery cannot occur between r and s. For example, suppose the channel number N = 3 ≡ 3 (mod 4) and {3, 1, 2, 1, 3, 2} is an LP of order 3. Both r and s use the CH sequence {2, 0, 1, 0, 2, 1} of period 6. If s is one time slot ahead, the broadcast delivery cannot occur between r and s , i.e., $|\mathcal {C}(r,rotate(s,1))|=0$.

However, an AMB system can be constructed by using ELP. If the channel number N is congruent to 0 or 1 modulo 4, then N − 1 is congruent to 0 or 3, there exists an ELP $\{l^{\prime }_{i}\}_{0\leq i\leq 2N-1}$ of order N − 1. For example, when N = 4, the ELP-based CH sequence is

$$\displaystyle \begin{aligned} u=\{0,0,3,1,2,1,3,2\}. \end{aligned}$$

When N≢0, 1 (mod 4), easily use the downsizing scheme or the padding scheme to transform it into an AMB system design problem with the channel number N ^′ congruent to 0 or 1 modulo 4.

Downsizing scheme.

Suppose the channel number N≢0, 1 (mod 4), let N ^′ be $\max \{N^{\prime }\leq N:N^{\prime }\equiv 0,1\pmod {4}\}$. It is easy to see that |N − N ^′|≤ 2. The donwsizing scheme will limit the set of broadcast channels to a N ^′-element subset of the original broadcast channel set, e.g., {0, 1, 2, …, N ^′− 1} is used as the new broadcast channel set .

Padding scheme.

Suppose the channel number N≢0, 1 (mod 4), let N ^′ be $\min \{N^{\prime }\geq N:N^{\prime }\equiv 0,1\pmod {4}\}$. It is easy to see that |N − N ^′|≤ 2. In contrast with the downsizing scheme, the padding scheme introduces N ^′− N more channels but maps them to the original broadcast channels in {0, 1, 2, …, N − 1}. For example, suppose N = 7 and then N ^′ = 8. Now add one more channel, i.e., channel 7, and adjoin channel 7 to the original broadcast channel set {0, 1, 2, …, 6}, but channel 7 is an alias of channel 0 – i.e., it is mapped to channel 0.

For instance, if N ≡ 2 (mod 4), use the downsizing scheme and |N − N ^′| = 1; if N ≡ 3 (mod 4), use the padding scheme and |N − N ^′| = 1. And this will only lead to a very mild degradation of performance since |N − N ^′| = 1.

With the aid of the downsizing scheme and the padding scheme, the problem in focus becomes the AMB design problem with the channel number N ^′ congruent to 0 or 1 modulo 4 .

A Simple Broadcast (S-Broadcast) Scheme for a Single CH Sequence Pair

This section presents a simple broadcast scheme, called S-Broadcast, for the simple scenario of the AMB system ($\mathcal {M}=(\{r\},\{s\})$) design problem.

Motivation.

If the broadcast radio r and the user radio s both use the same ELP $u=\{l^{\prime }_{i}\}_{0\leq i\leq 2N^{\prime }-1}$, the successful broadcast delivery between them is guaranteed; however, the delivery channel diversity is not ensured. If the broadcast radio uses cyclic rotated copies of u and the user radio uses periodically extended u, the delivery channel diversity will be increased.

To be precise, the CH sequences for the broadcast and user radios can be generated as follows:

• 1. The broadcast radio generates its CH sequence

  $$\displaystyle \begin{aligned} r=\prod_{f=1}^{F}rotate(u,o_{f}), \end{aligned}$$

  where {o _f}_1≤f≤F is a sequence of integers that are used to deliberately manipulate the clock drift and $\prod _{f=1}^{F}\theta _{f}$ denotes the concatenation of strings θ ₁, θ ₂, θ ₃, …, θ _F, i.e., $\prod _{f=1}^{F}\theta _{f}=\theta _{1}\parallel \theta _{2}\parallel \theta _{3}\parallel \cdots \parallel \theta _{F}$.

• 2. The user radio generates its CH sequence as $s=\prod _{f=1}^{F}u$, which is the periodic extension of u.

The delivery channel determination functio n is defined as

$$\displaystyle \begin{aligned} \delta:\mathbb{Z}\to\mathbb{Z}. \end{aligned}$$

For $k\in \mathbb {Z}$, k ≡ g (mod 2N ^′) where |g|≤ N ^′, then δ(k) = |g|− 1. For example, when N ^′ = 4, δ(1) = 0, δ(2) = 1, δ(3) = 2, δ(4) = 3, δ(5) = 2, δ(6) = 1, δ(7) = 0, and in particular δ(0) = −1.

S-Broadcast.

The proposed broadcast protocol for the simple scenario of the AMB system ($\mathcal {M}=(\{r\},\{s\})$) design problem, S-Broadcast, is an asynchronous CH-based channel broadcast protocol that achieves the broadcast latency at most 2N ^′− 1, the delivery ratio $\rho =\frac {1}{N^{\prime }}$ and full diversity. According to the design of S-Broadcast,

• $r=\prod _{f=1}^{2N^{\prime }}rotate(u,f-1)$.

• $s=\prod _{f=1}^{2N^{\prime }}u$.

Two examples illustrating the CH sequences of S-Broadcast when N ^′ = 4 are shown in Fig. 6.

Fig. 6

Example illustrating the CH sequences of S-Broadcast when N ^′ = 4. Radio r is the BS’s broadcast radio, and there is only one user, i.e., radio s. The CH sequences of the two radios can achieve full diversity within a period of 4N ^′2 = 64 time slots, given a clock drift of two slots either forwards or backwards. The delivery latency in (a) and (b) is 3 and 5 time slots, respectively, both less than 2N ^′− 1 = 7. And the delivery ratios in these two figures are both $\frac {1}{N^{\prime }}= \frac {1}{4}$

A Multichannel Broadcast (Mc-Broadcast) Scheme for Multiple CH Sequence Pairs

In the general AMB system design problem, $|\mathcal {B}|$ and $|\mathcal {U}|$ are generally greater than 1, i.e., $\mathcal {B}=\{r_{1},r_{2},r_{3},\ldots ,r_{R}\}$, $\mathcal {U}=\{s_{1},s_{2},s_{3},\ldots ,s_{U}\}$, R, U ≥ 1. This section presents two ELP-based CH protocols, A-Broadcast and L-Broadcast, for the case R ≥ 2N ^′ and the case R < 2N ^′, respectively.

Then, a multichannel broadcast protocol, called Mc-Broadcast, is the hybrid of the two above ELP-based CH protocols – i.e., it adopts A-Broadcast if R ≥ 2N ^′ and it adopts L-Broadcast if R < 2N ^′.

Suppose $u=\{l^{\prime }_{i}\}_{0\leq i\leq 2N^{\prime }-1}$ is an ELP of order N ^′− 1. The roadcast delivery can occur between any two cyclic rotation copies of u, say, between rotate(u, k) and rotate(u, l) – i.e., if ∀1 ≤ i ≤ R, r _i = rotate(u, o _i), and ∀1 ≤ j ≤ U, s _j = u, $\mathcal {M}=(\mathcal {B},\mathcal {U})$ is an AMB system. However, full delivery channel diversity ($DIV(\mathcal {M})=N^{\prime }$) is not necessarily guaranteed, and it is expected to reduce the broadcast latency. To take the advantage of multiple broadcast radios of the BS, it would be beneficial to select o _i’s properly so as to achieve full delivery channel diversity, reduce the broadcast latency down to zero and guarantee successful broadcast delivery in every time slot.

Define the balance sequences as

$$\displaystyle \begin{aligned} \psi_{i}^{n,k}(0\leq i<\operatorname{lcm}(n,k)/k), \end{aligned}$$

where $\psi _{i}^{n,k}$ is a sequence of k elements and $\operatorname {lcm}(n,k)$ is the least common multiple of n and k. Denote the j-th element in $\psi _{i}^{n,k}$ by $\psi _{i,j}^{n,k}$, where 0 ≤ j < k. And let

It is easy to see that $\{ik+j|0\leq i<\operatorname {lcm}(n,k)/k,0\leq j<k\}=\{0,1,2,3,\ldots \operatorname {lcm}(n,k)-1\}$. Hence ∀n ₀ ∈ [0, n − 1], there exist exactly $\frac {\operatorname {lcm}(n,k)}{n} (i,j)$-pairs such that $\psi _{i,j}^{n,k}=(ik+j)\bmod {n}=n_{0}$.

As a result, ∀n ₀ ∈ [0, n − 1], there exist exactly $\frac {\operatorname {lcm}(n,k)}{n}$ (i, j)-pairs such that $\psi _{i,j}^{n,k}=(ik+j)\bmod {n}=n_{0}$.

A-Broadcast when R ≥ 2N^′:

If the BS has a large number of broadcast radios, i.e., R ≥ 2N ^′, the AMB system can be designed to have guaranteed successful broadcast delivery in every time slot and full delivery channel diversity. Suppose R = 2qN ^′ + w, where $q=\lfloor \frac {R}{2N^{\prime }}\rfloor \geq 1$ and 0 ≤ w < 2N ^′. A-Broadcast is designed as follows:

• ∀1 ≤ i ≤ 2qN ^′,r _i = rotate(u, (i − 1) mod 2N ^′).

• ∀1 ≤ i ≤ w, from time slot $\lfloor \frac {t_{B}}{2N^{\prime }}\rfloor$ to time slot $\lfloor \frac {t_{B}}{2N^{\prime }}\rfloor +(2N^{\prime }-1)$, radio $r_{2qN^{\prime }+i}$ uses

  $$\displaystyle \begin{aligned} rotate\left(u,\psi_{\lfloor\frac{t_{B}}{2N^{\prime}}\rfloor\bmod{\operatorname{lcm}(2N^{\prime},w)/w},i-1}^{2N^{\prime},w}\right) \end{aligned}$$

  as its CH sequence, where t _B is the BS’s local clock time (i.e., according to the BS’s local clock, it is the t _B-th time slot).

• ∀1 ≤ j ≤ U, s _j = u.

An example illustrating the CH sequences of A-Broadcast when N ^′ = 4 is shown in Fig. 7.

Fig. 7

Example illustrating the CH sequences of A-Broadcast when N ^′ = 4. Radios r ₁, r ₂, r ₃, …, r ₁₀ are the BS’s broadcast radios and there are two users – radio s ₁ and radio s ₂. The clock of radio s ₁ is two time slots behind (or six time slots ahead of) that of the BS while the clock of radio s ₂ is three times lots ahead of (or five time slots behind) that of the BS. The blocks with red/blue fill pattern represents the time slots in which radio s ₁/s ₂ receives successful broadcast delivery from the BS, respectively, while the blocks with gray fill pattern represents the time slots in which both users (radios s ₁ and s ₂) receive successful broadcast delivery from the BS simultaneously. Both users can receive broadcast delivery from at least $2q=2\lfloor \frac {10}{8}\rfloor =2$ and on average $\frac {R}{N^{\prime }}= \frac {10}{4}=2.5$ BS’s broadcast radios every time slot and achieve full broadcast channel diversity

The A-Broadcast protocol has the following properties [4].

• A-Broadcast has zero broadcast latency.

• It achieves full delivery channel diversity. And the interval (i.e., 2N ^′) is bounded – within every 2N ^′ time slots, it achieves full delivery channel diversity.

• The delivery ratio is $\frac {1}{N^{\prime }}$.

• In every time slot, every user can receive broadcast delivery from at least 2q BS radios, and on average $\frac {R}{N^{\prime }}$ radios.

L-Broadcast when R < 2N ^′:

If the number of BS broadcast radios R is less than 2N ^′, we can also use the balance sequence to achieve delivery channel diversity and maximize delivery ratio. L-Broadcast is an ELP-based protocol, which is described as follows:

• ∀1 ≤ i ≤ R, from time slot $\lfloor \frac {t_{B}}{2N^{\prime }}\rfloor$ to time slot $\lfloor \frac {t_{B}}{2N^{\prime }}\rfloor +(2N^{\prime }-1)$, radio r _i uses

  $$\displaystyle \begin{aligned} rotate\left(u,\psi_{\lfloor\frac{t_{B}}{2N^{\prime}}\rfloor\bmod{\operatorname{lcm}(2N^{\prime},R)/R},i-1}^{2N^{\prime},R}\right) \end{aligned}$$

  as its CH sequence, where t _B is the BS’s local clock time (i.e., according to the BS’s local clock, it is the t _B-th time slot).

• ∀1 ≤ j ≤ U, s _j = u.

An example illustrating the CH sequences of L-Broadcast when N ^′ = 4 is shown in Fig. 8.

Fig. 8

Example illustrating the CH sequences of L-Broadcast when N ^′ = 4. Radios r ₁, r ₂, r ₃, r ₄ are the BS’s broadcast radios and there are two users – radio s ₁ and radio s ₂. The clock of radio s ₁ is two time slots behind (or six time slots ahead of) that of the BS, while the clock of radio s ₂ is three time slots ahead of (or five time slots behind) that of the BS. The blocks with red/blue fill pattern represents the time slots in which radio s ₁/s ₂ receives successful broadcast delivery from the BS, respectively, while the blocks with gray fill pattern represents the time slots in which both users (radios s ₁ and s ₂) receive successful broadcast delivery from the BS simultaneously. Both users can receive broadcast delivery from $\frac {R}{N^{\prime }}= \frac {4}{4}=1$ BS’s broadcast radio on average and achieve full delivery channel diversity every $2N^{\prime }\cdot \lceil \frac {2N^{\prime }}{R}\rceil =8\cdot \frac {8}{4}=16$ time slots

The L-Broadcast protocol has the following properties [4].

• The broadcast latency of the AMB system that implements L-Broadcast is at most 2N ^′− 1.

• It achieves full delivery channel diversity. And the interval (i.e., $2N^{\prime }\cdot \lceil \frac {2N^{\prime }}{R}\rceil$) is bounded – it achieves full delivery channel diversity every $2N^{\prime }\cdot \lceil \frac {2N^{\prime }}{R}\rceil$ slots.

• In every time slot, every user can receive broadcast delivery from $\frac {R}{N^{\prime }}$ radios on average.

Simulation

This section compares the performance of the proposed Mc-Broadcast protocol and other existing protocols, including the distributed broadcast protocol (or simply called “distributed”) proposed in [43] and the random channel hopping scheme, via simulation results. In each simulated network cell, the BS has R broadcast radios available; a number of U users are connected to the BS, and each user has a single radio interface; each radio can access N broadcast channels (i.e., the number of broadcast channels available to the network is N). The BS or its connected users generate their CH sequences using the agreed broadcast scheme (i.e., either Mc-Broadcast, the distributed protocol, or the random channel hopping protocol) and perform CH in accordance with the sequences. Once two nodes hop onto the same channel that is free of primary user signals, the broadcast delivery between them is successful.

Traffic model.

A number of X primary transmitters are simulated, operating on X channels independently, and these channels were randomly chosen in each simulation run. In most existing work, it is assumed that a primary user transmitter follows a “busy/idle” transmission pattern on a licensed channel [12, 18], and the same traffic pattern is assumed here. That is, the busy period has a fixed length of b time slots, and the idle period follows an exponential distribution with a mean of l time slots. A channel is considered “unavailable” when PU signals are present in it. The intensity of primary user traffic can be characterized as $PU=\frac {X}{N}\cdot \frac {b}{l+b}$.

Random clock drift.

In a CR network, the BS and the user may lose clock synchronization or even link connectivity at any time when they experience the broadcast failure problem due to primary user affection. Hence, the clock of the BS and those of the users are not necessarily synchronized. In each simulation run, each secondary node (the BS and the users) determines its clock time independently of other nodes. Note that the radios of the BS are synchronized, and there is a random clock drift between the BS and any of its connected users.

Average broadcast latency.

Figures 9 and 10 show the simulation results with respect to the average broadcast latency under the conditions N = 4, 5 and 8, respectively. It is illustrated that as the number of broadcast radios increases, it takes fewer time slots on average before the first successful delivery for both schemes under different PU traffic. This implies that a greater number of broadcast radios is conducive to mitigating the average broadcast latency.

Fig. 9

The average broadcast latency versus the number of broadcast radios at the base station (N = 4), with a 95% confidence interval attached to each bar

Fig. 10

The average broadcast latency versus the number of broadcast radios at the base station (N = 5), with a 95% confidence interval attached to each bar

It is noteworthy that for different numbers of available channels and different PU traffic, the average latency of Mc-Broadcast is smaller than those of other existing broadcast protocols.

Spectrum Sharing Problem

This section investigates the spectrum sharing problem among coexisting heterogeneous cellular networks.

To address this problem, it is needed to establish a coexistence framework that employs an indirect coordination method for enabling collaborative coexistence among networks. The proposed framework was inspired by the interspecies relations that exist in biological ecosystems. A symbiotic relation is a term used in biology to describe the coexistence of different species that form relations via indirect coordination. It exploits a mediator system (e.g., the 802.19.1 system) that forwards sanitized data to establish the indirect coordination mechanism between coexisting networks. It employs an ecology inspired spectrum sharing algorithm inspired by an interspecific resource competition model that enables each CR network to autonomously determine the amount of spectrum that it should appropriate without direct negotiation with competing networks. Results show that this framework guarantees weighted fairness in partitioning spectrum and improves spectrum utilization.

The Mediator System

The recently formed IEEE 802.19.1 task group (TG) was chartered with the task of developing standardized methods, which are radio access technology independent, for enabling coexistence among dissimilar or independently operated wireless networks [21]. This standard is currently being developed, and it has yet to prescribe solid solutions. The IEEE 802.19.1 system is a good candidate to serve as the mediator. The IEEE 802.19.1 system [21] defines a set of logical entities and a set of standardized interfaces for enabling coordination between heterogeneous CR networks. Figure 11 shows the architecture of an 802.19.1 system which includes three entities in the grey box: (1) the coexistence manager (CM) acts as the local decision-maker of the coexistence process; (2) the coexistence database and information server (CDIS) provides coexistence-related control information to the CMs, and (3) the coexistence enabler (CE) enables communications between the 802.19.1 system and the TV band device (TVBD) network. The TVWS database indicates the list of channels used by primary users and their locations, and it is connected to the 802.19.1 system via backhaul connections .

Fig. 11

IEEE 802.19.1 system architecture

Interspecific Competition in Ecology

In ecology, interspecific competition is a distributed form of competition in which individuals of different species compete for the same resource in an ecosystem without direct interactions between them [45]. The impact of interspecific competition on populations have been formalized in a mathematical model called the Lotka-Volterra (L-V) competition model [34, 46]. In this model, the impact on population dynamics of species i can be calculated separately by a differential equation given below:

$$\displaystyle \begin{aligned} \frac{d N_i}{d t} = r_i N_i \left ( 1 - \frac{ N_i + \sum_{j\neq i} \alpha_{ij} N_j } {K_i} \right). \end{aligned} $$

(3)

In this equation, N _i is the population size of species i, K _i is the carrying capacity (which is the maximum population of species i if it is the only species present in the environment), r _i is the intrinsic rate of increase, and α _ij is the competition coefficient which represents the impact of species j’s population growth on the population dynamics of species i.

Framework Overview

Consider n heterogeneous networks are co-located, and they coexist in the same spectrum band that includes N channels with an identical bandwidth. Let $\mathcal {K}$ denote this set of networks, and all of these networks in $\mathcal {K}$ are registered with the mediator system. Every network is composed of multiple devices and a base station (BS) (or access point). Channels are labeled with indices 0, 1, …, N − 1.

Time-spectrum blocks .

Time is divided into periods, each period contains a number of u superframes, and each super-frame contains f frames (such a structure based on frames can be found in IEEE 802.16 and 802.22). A time-spectrum block is the minimum unit for spectrum allocation, which can be defined by a channel index and a frame index. Specifically, a time-spectrum block can be represented using a three-tuple (i, j, k) – i.e., the k-th frame in the j-th superframe over channel i. Over channel i, there are a number of uf blocks that can be allocated during a period. It is assumed that a BS or network with multiple radios is able to scan and access multiple time-spectrum blocks on different channels simultaneously. Furthermore, define the capacity, C, as the total number of spectrum-time blocks during a period, given N channels.

The bandwidth requirement .

Define the bandwidth requirement of a network as the number of time-spectrum blocks that it needs to satisfy the QoS requirements of its traffic load. Let R _i denote the bandwidth requirement of network i.

The mediator-based indirect coordination .

SHARE establishes a mediator-based indirect coordination mechanism between coexisting networks. There is no direct coordination between the coexisting networks, and they have to interact with each other by exchanging control information through a third-party mediator. Specifically, SHARE utilizes a CDIS (which is one of the components of an 802.19.1 system) as a mediator. Note that CDIS is not a global or centralized decision-maker, but rather it is an information directory server with simple data processing capabilities.

Necessity of sanitized information .

The mediator helps address conflict-of-interest issues and customer privacy concerns, which may arise when coexisting networks operated by competing service providers are required to exchange sensitive traffic information in order to carry out coexistence mechanisms. The mediator sanitizes the sensitive information received from the coexisting networks and then returns the sanitized information back to them. The coexisting networks execute their coordinated coexistence mechanisms using the sanitized data.

Ecology Inspired Spectrum Allocation

As mentioned before, spectrum allocation among the coexisting networks through direct coordination may not be possible (due to a lack of infrastructure), may be too costly, or may be shunned by the competing network operators because they do not want to provide their sensitive information. Instead of direct coordination, the SHARE framework adopts an indirect coordination mechanism, which is inspired by an interspecific competition model from theoretical ecology.

Design objective.

In a spectrum sharing process, a network has to figure out how much spectrum it can appropriate given its bandwidth requirement. Suppose a time-spectrum block is the minimum unit amount of spectrum allocation. Let S _i denote the number of time-spectrum blocks allocated to network $i\in \mathcal {K}$, and S _i refers to as the spectrum share of network i.

The objective is that the spectrum sharing process will eventually reach a state of equilibrium, where the number of allocated blocks to each network is proportional to its reported bandwidth requirement.

Inspiration from ecology.

In ecology, the population dynamics of a species in the interspecific resource competition process can be captured by the L-V competition model. In the context of network coexistence, a weighted competition model is built to help a network to determine the dynamics of its allocated spectrum, given its bandwidth requirement.

Information exchange between the mediator and a network.

The mediator exchanges two types of control information with every CR network:

• 1. Upload of local report. Network i reports the current value of S _i to the mediator.

• 2. Download of sanitized data. The mediator replies back to network i with the sanitized data, i.e., sum of numbers of time-spectrum blocks of all other coexisting networks, i.e., $\sum _{j\neq i, j\in \mathcal {K}} S_j$.

Problem Formulation

Suppose that $\mathcal {K}$ denotes a set of n co-located networks that have individual bandwidth requirements R ₁, R ₂, …, R _n, and operate over the same WS. The first objective for coexisting networks is to split the WS into n pieces that are proportional to their individual bandwidth requirements, without sharing individual bandwidth requirements with each other.

Let $\mathbf {S}(\mathcal {K})=[S_1, S_2, \dots , S_n]$ denote the spectrum share vector for $\mathcal {K}$ over the white space. The fairness index, $F(\mathbf {S}(\mathcal {K}))$, for networks in $\mathcal {K}$ is defined as follows:

$$\displaystyle \begin{aligned} F(\mathbf{S}(\mathcal{K})) =\frac{ \left( \sum_{i \in \mathcal{K}} S_i \right)^2 }{ \sum_{i \in \mathcal{K}} R_i \cdot \sum_{i \in \mathcal{K}} R_i \left(\frac{S_i} {R_i} \right)^2 }. \end{aligned} $$

(4)

The maximum value of $F(\mathbf {S}(\mathcal {K}))$ is one (the best or weighted fair case), where the allocated spectrum share value of a network is proportional to its bandwidth requirement.

Let $\mathcal {I}_i$ denote the set of shared control information known by network i, and it is easy to see that $R_i \in \mathcal {I}_i$. However, it is assumed that $R_j \notin \mathcal {I}_i$ – i.e., co-located networks, i and j, do not know each other’s bandwidth requirements.

A weighted fair spectrum sharing allocation problem is formulated for heterogeneous networks to dynamically determine their spectrum share values.

Problem 1

Given a set of n co-located networks, $\mathcal {K}$, operating over N channels, one has to solve the following problem to find the spectrum share vector for $\mathcal {K}$:

$$\displaystyle \begin{aligned} \text{Maximize} &~~ F(\mathbf{S}(\mathcal{K}))\\ \text{subject to} &~~ \frac{S_i}{S_j} = \frac{R_i}{ R_j}, R_j \notin \mathcal{I}_i, \forall i,j \in \mathcal{K}. \end{aligned} $$

The first constraint $\frac {S_i}{S_j} = \frac {R_i}{R_j}$ guarantees the weighted fairness .

An Ecology-Inspired Spectrum Share Allocation Algorithm

The Stable Equilibrium of the L-V Competition Model

The L-V competition model provides a method for defining a state of “stable equilibrium” and finding the sufficient conditions for achieving it. If one considers the interspecific competition process described by equation (3), when K _i = K _j and α _ij = α _ji for any two species i and j, then the sufficient condition for stable equilibrium is α _ij < 1.

The Basic Spectrum Competition Model

Table 1 shows a number of analogies between a biological ecosystem and a network system. Based on equation (3) and the analogies, the following basic spectrum competition model is obtained:

$$\displaystyle \begin{aligned} \frac{d S_i}{d t} = r S_i \left( 1- \frac{S_i + \alpha \sum_{j\neq i} S_j } {C} \right), \end{aligned} $$

(5)

where S _i is the spectrum share for network i, and r is an intrinsic rate of increase. In equation (5), the carrying capacity is equal to the number of time-spectrum blocks in a period given N channels. A competition coefficient α < 1 will guarantee a stable equilibrium – i.e., all the competing networks will have the same spectrum share value.

Table 1 A mapping between biological and CR network ecosystems

Next section shows how to extend the basic competition model to a weighted fair spectrum competition model that complies with the weighted fairness requirement (i.e., $\frac {S_i}{S_j} = \frac {R_i}{R_j}$ for any two networks i and j) in a state of stable equilibrium.

The Weighted Fair Spectrum Competition Model

The basic spectrum competition model guarantees a stable equilibrium where all the competing networks have the same spectrum share value. However, solutions to Problem 1 must satisfy the requirement of weighted fairness, which implies that the competing networks’ spectrum share values are proportional to their bandwidth requirements. For example, if network i has a bandwidth requirement that is twice that of network j, then network i’s allocated spectrum share should also be twice the allocated spectrum share of network j.

To support the weighted fairness in spectrum share allocation, a weighted fair spectrum competition model introduces the concept of “subspecies.” A network with a higher bandwidth requirement would have a greater number of subspecies than a network with a lower bandwidth requirement. The bandwidth requirement R _i is used as the number of sub-species of network i.

Let S _i,k denote the spectrum share allocated to the subspecies k of network i, where k ∈ [1, R _i]. In the weighted competition model, every subspecies k of network i calculates the change in its spectrum share according to the following equation:

$$\displaystyle \begin{aligned} \delta_{i,k} &= \frac{dS_{i,k}}{dt} \\ &= r S_{i,k} \left( 1- \frac{S_{i,k} + \alpha \sum_{\kappa \neq k} S_{i,\kappa} + \alpha \sum_{j\neq i} S_j } {C} \right). \end{aligned} $$

(6)

Then, network i obtains its spectrum share value by combining the spectrum share values of all its subspecies, i.e., S _i =∑_k S _i,k.

Every network i periodically sends its spectrum share value S _i to the mediator, and then the mediator sends back the sanitized data β _i =∑_{j ≠ i} S _j to network i. The spectrum share allocation process terminates when δ _i,k = 0 for all i and k. Note that the sanitized data β _i is used (instead of actual bandwidth requirement information) to mitigate conflict of interest and privacy issues that may arise between competing networks. The use of sanitized data coincides with the second constraint of Problem 1. The procedure is described as below.

• 1. A network i starts its spectrum share allocation process by creating a number of R _i sub-species.

• 2. At the beginning of every frame, every sub-species calculates the change rate of its spectrum share (i.e., $\frac {dS_{i,k}}{dt}$) using the sanitized data β _i obtained from the mediator.

• 3. If the change rate of the spectrum share is positive (or negative), a subspecies increases (or decreases) its spectrum share by randomly selecting a number of time-spectrum blocks to access (or releasing/freeing a number of occupied time-spectrum blocks).

• 4. At the end of every iteration, every network i calculates its new spectrum share value by S _i =∑_k S _i,k, and sends S _i to the mediator. Meanwhile, the network updates the value of β _i from the mediator.

• 5. Last three steps are repeated until there is no subspecies with a non-zero change rate of spectrum share; that is $\frac {dS_{i,k}}{dt}=0$ for every subspecies k of any network i.

• 6. The allocated spectrum share for network i is ∑_k S _i,k.

In this framework, the spectrum share allocation algorithm satisfies the requirement of weighted fairness .

Simulation

This section evaluates the performance of the proposed approach by looking into the stable equilibrium achieved by the weighted fair spectrum share allocation scheme.

Consider two CR networks that coexist in a block of spectrum that is divided into 20 channels, and fix the bandwidth requirements of the two networks as R ₁ = 2 and R ₂ = 3, which implies that network 1 has two subspecies and network 2 has three in the spectrum share allocation process. In the L-V competition model, the competition coefficient α < 1 and the intrinsic rate of increase r < 2 [35]. The discussions on how to choose appropriate parameter values to achieve fast convergence to an equilibrium can be found in [35]. In this set of simulations, α = 0.9 and r = 1.95.

Convergence to an equilibrium.

Figure 12 shows the dynamics of the spectrum share value of each network and each subspecies within a network. “Subspecies (i, j)” in the figure legend represents sub-species j within network i. The system converges to an equilibrium state in finite time where all subspecies of every network are allocated the same spectrum share value. The aggregate spectrum share value allocated to a network is proportional to its bandwidth requirement.

Fig. 12

Convergence to the equilibrium

Weighted Fairness.

In each simulation run, the bandwidth requirement, R _i, of each network i is randomly chosen from the range [1, 5]. A “noncollaborative” allocation scheme implies that every coexisting network determines its spectrum share value without coordinating with others. This is equivalent to splitting the available spectrum “randomly” to n pieces and allocates them to n coexisting networks. The fairness values are measured using the fairness index defined in (4). Figure 13 clearly shows that SHARE allocates spectrum in a weighted fair manner, whereas the noncollaborative allocation scheme does not .

Fig. 13

Measured fairness values

Channel Contention Problem

When coexisting networks have a means for direct coordinations, the channel contention protocol is a viable way of addressing the heterogeneous coexistence problem.

A channel contention protocol facilitates the dynamic spectrum allocation among coexisting networks in a distributed manner when a network is in need of spectrum to satisfy its service requirement. There is no need to start the spectrum sharing process for self-coexistence when the available spectrum is sufficient to satisfy all coexisting networks.

When the available spectrum is insufficient, every network (or network BS) occupies an amount of spectrum that is no more than it needs (i.e., its service requirement). IEEE 802.22 defines an inter-BS spectrum contention protocol for network cells to achieve the goal of self-coexistence.

• A BS that is in need of spectrum (contention source BS) is allowed to win channels via pairwise contentions with its neighboring BSs (contention destination BSs).

• If the contention source wins the contention, it occupies the contended channels exclusively, while the contention destinations vacate those channels via channel switching.

To ensure the fairness in the contention process, existing proposals adopt a simple unbiased contention resolution rule based on random number selection [16, 17], such that either a contention source or a contention destination has an equal probability of winning the pairwise contention.

However, the existing design of a coexistence protocol fails to consider the successive events that may be triggered by the spectrum redistribution during a local spectrum contention process. For example, the channel redistribution via contentions may satisfy the contention source, but meanwhile the contention destination that loses spectrum may become short of spectrum and successively initiate a cascading spectrum contention process to acquire more spectrums. A cascade is a series of events, in which the occurrence of an event can trigger the occurrence of successive events. As a result, unrestricted local spectrum contentions may trigger a series of successive contention instances that proliferate over the whole network, which may waste the network resources.

This section systematically studies the spectrum contention problem using the percolation theory in the context of coexisting cellular networks. The process of cascading spectrum contentions under existing spectrum contention resolution rules is equivalent to a site percolation process that can readily lead to a network-wide cascade. Moreover, a biased spectrum contention protocol is presented to mitigate this problem .

Spectrum Contention

When available spectrum is insufficient to satisfy all coexisting BSs, an 802.22 BS in need of spectrum can initiate an inter-BS spectrum contention process so that better channels or more channels can be acquired from neighboring BSs to satisfy the QoS of its workload [22].

• 1. The BS that initiates the spectrum contention process is the contention source (SRC). A spectrum contention process consists of a number of pairwise contentions, and every pairwise contention is carried out between the SRC and a neighboring BS that is referred to as the contention destinations (DST).

• 2. The SRC sends a contention request message to contend for a target channel that is currently occupied by a DST. The DST uses a specific contention resolution rule to determine the winner of the contention.

• 3. In the unbiased contention resolution rule [16, 17], every BS (either SRC or DST) is required to select a spectrum contention number (SCN) that is uniformly distributed in the range [0, W − 1], and exchange the SCN values, where W is a constant representing the contention window size.

• 4. The BS that has selected the largest CN among all participating BSs is the winner of the contention. Other BSs (and their 802.22 networks) that fail to win will vacate the channel.

Site Percolation

A percolation process resides in a graph including sites (vertices) or bonds (edges). The most common percolation model takes the graph structure of a regular lattice (e.g., a square lattice). In the site percolation process, every site is either open (i.e., open to flow, diffusion, etc.) randomly and independently with probability p, or closed (i.e., closed to flow, diffusion, etc.) with probability 1 − p.

Definition 2

A path is open if all its sites are open and it is close if all its sites are closed. Sites u and v are said to be open connected if there exists an open path that connects u and v. Define v to be open connected to itself.

It follows immediately that open connection is an equivalence relation. Write u ↔ v if u and v are open connected, and $u\nleftrightarrow v$ if u and v are not open connected.

Definition 3

The open cluster C(v) at site v is the set of all sites that are open connected to v, represented as

$$\displaystyle \begin{aligned} C(v)=\{u\in V|u\leftrightarrow v\}. \end{aligned}$$

Intuitively, as p increases, the size of an open cluster also increases. At a critical value of p, the long-range connectivity in the network appears – there is a transition in the topological structure of the network from a macroscopically disconnected to a connected one – and thus this critical value is called the percolation threshold or critical probability [14]. Let p _c denote the percolation threshold, the following fundamental results can be obtained from percolation theory [14]:

• when p > p _c, with probability one, there exists an infinite cluster, and with a positive probability, the origin (or any other fixed point) belongs to an infinite cluster

• when p < p _c, all clusters are finite

When the graph structure resides in continuous space (e.g., a random geometric graph), the resulting percolation model is described as continuum percolation .

Network Model

Network graph .

The placement of BSs of CR networks could transform to an undirected network graph G = (V, E), where V is the set of vertices and E is the set of edges. Each vertex i ∈ V represents a BS of a network cell, and the BS represented by a vertex i is called BS i. If two BSs i and j are neighboring to each other in the network, there is an edge {i, j}∈ E connecting the two vertices i, j ∈ V (i.e., an inter-BS communication link connecting the two BSs). In this case, vertex j is said to be a neighbor of vertex i. Let N(i) denote the set of all neighbors of vertex i in graph G: N(i) = {j ∈ V |{i, j}∈ E}. The cardinality of N(i) is called the degree of vertex i, written as d(i) = |N(i)|.

Base station placement on a lattice.

In an 802.22 system, the rural area is divided into regular-shaped cells, which can be hexagonal, square, or some other irregular shapes. They are generalized to the notion of lattice [1], and three common types of lattices are triangular, square, and honeycomb lattices.

Service requirement

Every BS i requires r _i channels to satisfy the QoS of its admitted workload, and N is the maximum number of available channels. The value of r _i, called the service requirement of BS i, depends on the intra-cell traffic demand raised by the secondary users (i.e., CPEs) connected to the BS i. Let A _i denote the set of channels that are occupied by BS i.

Every BS i tries to claim as many unoccupied channels as possible until |A _i| = r _i or there is no unoccupied channels that can be claimed. Thus, |A _i|≤ r _i for any BS i. To avoid co-channel interference, neighboring BSs i and j occupy disjoint sets of channels, i.e., $A_{i}\cap A_{j}=\varnothing$.

Network states.

Every BS i occupies an amount of spectrum that is no more than its service requirement. It is assumed there are two states for a given CR network – a state wherein the BS is in need of spectrum, and a state wherein the BS does not need additional spectrum. These two states are called “starving” and “satisfied,” respectively.

• When |A _i| < r _i, BS i is a starving BS.

• When |A _i| = r _i, BS i is a satisfied BS.

Causes for spectrum contention.

The root cause for incurring spectrum contention is the existence of a starving BS. There are three factors that make a satisfied BS i become starving: (1) the reclaim of occupied channels in A _i by the primary user, (2) the increase of r _i due to an increased intra-cell workload, and (3) losing channels in A _i due to spectrum contentions.

The probability that a satisfied BS i becomes starving due to all these factors is called the starving probability of BS i, denoted by p _i. Meanwhile, call the probability that a satisfied BS i becomes starving due to non-contention (the first two) factors as spontaneous starving probability, denoted by p _i,0.

Problem Formulation

In an inter-BS spectrum contention process, the channel redistribution may satisfy the contention source BS i, but meanwhile a contention destination BS j that loses the target channel may become starving and successively initiate a cascading contention process. Therefore, the event that a BS j becomes starving is caused by a spectrum contention initiated by a starving BS i. That is, a local spectrum contention initiated by a BS may cause a cascade of spectrum contentions, which will result in futile contention results and waste network resources. Such a phenomenon is referred to as a cascading spectrum contention, which is formulated as a site percolation process over the network graph as follows.

Similar to the definitions of open/closed sites (vertices) in the percolation process, define open/closed BSs in the context of CR networks. A vertex i in the network graph G is open if BS i is a starving BS, and call it an open BS. Otherwise, the vertex i is closed if BS i is a satisfied BS, and call it a closed BS.

Two BSs i and j are said to be open connected if there exists a path in the network graph that connects vertices i and j, and every vertex in this path is open. The open cluster at BS i is the set of all BSs that are open connected to BS i.

It is believed that BSs i and j in the same open cluster are related in a certain relationship of spectrum contentions, e.g., there may exist a path starting at BS i and ending at BS j, where a pairwise contention occurs between every pair of BSs along this path, or there exist two contention paths between k and i, k and j, where k is a third BS in the same cluster. The open cluster in the network graph describes the set of BSs that are in the “starving” state that may be caused by cascading spectrum contentions.

The size of an open cluster.

Metrics in the percolation theory are used to quantify the magnitude of cascading spectrum contentions. Define the mean open cluster size at BS i as

$$\displaystyle \begin{aligned} \chi_{i}(p_{i}:i\in V)=E_{(p_{i}:i\in V)}(|C(i)|), \end{aligned}$$

where $E_{(p_{i}:i\in V)}(X)$ denotes the expectation of a random variable X, given that BS i is open independently with probability p _i (i ∈ V ).

Lower bound case with starving probability p.

There is a lower bound p of p _i’s, i.e., p ≤ p _i, ∀i ∈ V . Thus $\chi _{i}(p_{i}:i\in V)\geq \chi _{i}(p)\triangleq E_{p}(|C(i)|)$, where E _p(X) denotes the expectation given that every BS is open independently with probability p, i.e. χ _i(p) is a lower bound of χ _i(p _i : i ∈ V ).

So far the study of χ _i(p _i : i ∈ V ) is transformed into the study of χ _i(p) in a lower bound case where every BS i is open independently with probability p.

Since the placement of BSs of CR networks form a lattice G = (V, E), whose automorphism group acts transitively upon V (also known as vertex-transitive) [1], then ∀i, j ∈ V , C(i) = C(j) and χ _i(p) = χ _j(p) due to the homogeneity of a lattice. Hence, simply use C and χ(p) instead of C(i) and χ _i(p).

Therefore, the cascading spectrum contention process in CR networks is mapped to the lower bound site percolation process over the network graph where every vertex (BS) is open independently with probability p.

Global and Severe Cascades

Since χ(p) is defined to characterize the magnitude of cascading spectrum contentions, a global cascade of spectrum contentions occurs if the mean open cluster size is infinite, i.e., χ(p) = ∞. According to the percolation theory, an infinite open cluster exists (χ(p) = ∞) with probability one, if and only if p ≥ p _c, where p is the starving probability and p _c is the critical probability.

In the subcritical phase when p < p _c, a severe cascade of spectrum contentions is to said to occur if the mean open cluster size χ(p) ≥ χ (χ is a predefined threshold, e.g., that χ is set to be 50 means that a cascade involving in over 50 BSs is considered to be a severe cascade), which suggests that an average open cluster of BSs is large.

A Biased Spectrum Contention Protocol

Contention Resolution Rule

A biased contention resolution rule is found to be effective to mitigate this problem by reducing the winning probability of a contention source in a pairwise contention. Define a contention path between BSs i and j as a path between vertices i and j in the network graph, such that the channel redistribution via a pairwise contention process occurs for every pair of neighboring BSs that belong to the path. The procedure for the biased contention resolution is described below.

• 1. In the contention request, every contention source BS i includes the target channel number h, its SCN s _i chosen from [0, W − 1], and the current length of the contention path l _i measured by BS i. If the BS i does not belong to any contention path, it sets l _i = 0, which implies that it is the starting vertex of a new contention path.

• 2. Every contention destination BS j checks the values of l _i and SCN s _i in the contention request from the contention source BS i. Let S(j) denote the set of contention sources that send contention requests to BS j during a self-coexistence window.

• 3. If |S(j)| > 1, BS j is being reached by more than one contention paths. The contention destination BS j measures its l _j as max_{i ∈ S(j)}{l _i} + 1 and generates its own SCN s _j from a modified contention window [0, l _j ⋅ W − 1]. The measured value of l _j will be used by BS j in future contention requests if it becomes a contention source.

• 4. If the contention destination BS j has the greatest SCN value, it wins the contention. Otherwise, the contention source who has the greatest SCN value wins, and the contention destination BS j releases the target channel.

If p ₀ ≥ p _c, a global cascade of spectrum contentions is inevitable. The fact that p ₀ ≥ p _c strongly suggests the insufficiency of overall spectrum resources. Next section discusses the case when p _i,0 < p _c for all i ∈ V .

Finite Cluster Size

Decreasing the winning probability of a contention source can prevent the occurrence of infinite contention paths. There is no infinite contention path if the biased contention resolution rule is used for contention resolution in the case of p _i,0 < p _c, ∀i ∈ V .

Simulation

This section compares two contention resolution rules, namely, the unbiased rule and the proposed biased rule, in terms of feasibility of invoking the cascade phenomenon in spectrum contentions under various conditions in CR networks.

Simulation Setup

Topology.

Consider simulating three typical lattices: coexisting BSs are placed on a honeycomb lattice (d = 3), a square lattice (d = 4), and a triangular lattice (d = 6), respectively.

Self-coexistence window and inter-BS spectrum contention.

In a network cell, the BS provides broadband access to secondary users according to a time schedule consisting of superframes. 802.22 provides the inter-BS synchronization mechanism for neighboring BSs to align their superframes. In 802.22, a superframe has 16 frames, and a self-coexistence window (SCW) is periodically scheduled in every frame for spectrum contention.

Service requirement.

There are a total number of N = 30 channels in the simulations. Every BS requires 10, 20, or 30 channels to satisfy the QoS of its admitted workload. Neighboring BSs occupy disjoint sets of channels, and a BS claims a number of channels which is no more than its service requirement.

Primary user (PU) traffic generation.

It is assumed that there is one primary transmitter per cell, and every primary transmitter randomly selects X ∈ [0, N _a] channels to emit its signals, where N _a is the number of PU’s active channels. In most existing work, it is assumed that a primary transmitter follows a “busy/idle” traffic pattern on a licensed channel [12]. Hence, a “busy/idle” pattern is simulated for each primary transmitter: the busy period has a fixed length of b time slots, and the idle period follows an exponential distribution with a mean of l frames. Thereafter, the notation $\lambda _{e}=\frac {1}{l}$ is the primary transmission rate. Every BS is able to detect the signals from the primary transmitter in the same cell. A channel is considered “unavailable” when primary user signals are present in it. All secondary users (BSs) should vacate unavailable channels during the period of primary user transmission.

Phenomenon of Cascading Spectrum Contentions

The mean cluster size, χ, is measured when varying the following parameters: the degree d of the lattice where BSs are placed, the number k of pairwise contentions initiated by a contention source, and the PU traffic pattern (the number N _a of PU’s active channels and the primary transmission rate λ _e).

Impact of lattice degree.

In this set of simulations, we fix r = k∕d = 1. In the honeycomb lattice case (d = 3), the mean open cluster size is the smallest, while the triangular lattice (d = 6) shows the largest mean open cluster size (Fig. 14). These results coincide with the previous conclusion, with r = k∕d fixed, there is a positive correlation between χ and d.

Fig. 14

Mean open cluster size vs. lattice degree

Impact of number of pairwise contentions.

As is shown in Fig. 15, the more pairwise contentions initiated by a contention source, the larger the mean open cluster size .

Fig. 15

Mean open cluster size vs. number of pairwise contentions

Conclusion and Future Directions

This chapter reviews four important research problems for coexistence of heterogeneous cellular networks using cognitive radio technologies. Specifically, the hidden terminal problem can be factored into two types of collision problems, and the beacon transmission scheme and the dynamic quiet period scheme can address them respectively. Next, it is showed that the channel hopping technique is useful to alleviate the broadcast failure problem in cellular CR networks by leveraging the Langford paring for creating channel hopping sequences. When the inter-network direct coordination is not feasible, a mediator system is able to establish an indirect coordination mechanism for spectrum sharing between networks. On the other hand, when the inter-network direct coordination is not supported, a local controller helps a CR network in need of more spectrum resources to acquire channels from neighboring networks via channel contention without causing the cascading contention problem.

Future work lies in three directions: (1) the evaluation of the coexistence schemes in the real-world scenarios of heterogeneous cellular networks, (2) how to address the violation to the conflict of interests and customer privacy when heterogeneous coexistence of cognitive cellular networks is feasible, and (3) the application of the cutting-edge machine learning techniques to upgrade the existing design principles and frameworks for the coexistence of heterogeneous cellular networks.