Channel allocation algorithms for co-existence of base stations in IEEE 802.22 networks

Abstract

The purpose of the Wireless Regional Area Networks (WRANs) is to allow the use of spectrum allocated for television broadcasting in areas with sparse users, ensuring no interference with licensed operators. Cognitive radios using the IEEE 802.22 standard should monitor the environment to not cause interference in primary operators. When multiple WRANs intend to operate on the same set of frequencies in overlapping areas, the 802.22 standard provides mechanisms for their co-existence and provides a temporal multiplexing scheme to solve this problem. We propose three channel allocation algorithms to support the co-existence of potentially interfering WRANs. The proposed algorithms are based on graph coloring, and the innovation is to consider the demand for bandwidth from each WRAN, maintaining proportionality between the demand for frequencies of each WRAN and what is actually allocated. The algorithms are evaluated and it is concluded that they can efficiently assign channels to WRAN taking into account the bandwidth needs of each network.

Keywords

Channel allocation IEEE 802.22 networks graph coloring

1 Introduction

A cognitive radio is a device capable of changing its transmission and reception parameters according to the information it has about the environment in which it is located. The development of cognitive radios created the foundations for the IEEE 802.22 standard that drives the operation of Wireless Regional Area Network (WRAN) [12]. WRANs are formed by base stations (BS) and customer premises equipments (CPE). The IEEE 802.22 standard allows the secondary use of spectrum allocated for television broadcasting between 54 and 862 MHz, ensuring no interference in the covered area with licensed operators, including the sporadic use of low power devices, as wireless microphones. The cognitive function of WRAN should scan the environment and change its operation to keep in line with the non interference assumption. In situations of interference with a primary operator, the cognitive radio can reduce its transmission power to limit the range of the signal, or can change the operating frequency. In the first case, a CPE can stay out of range of the BS and join another WRAN, becoming part of it. However this can involve different organizations that may not consent to receive CPEs from each other, leaving only the second option, that is, changing the operating frequency. Thus, co-existence strategies should be considered, where different overlapping WRANs would transmit using distinct channels.

The allocation of channels to interfering WRANs is an area of study that has aroused the interest of the scientific community, and several studies have addressed this problem. Many different techniques were employed, such as fuzzy logic [13], genetic algorithms [3], game theory [4] and distributed pseudo tree-optimization procedure [7]. Some proposals, like ours, make use of graph coloring to address co-existence issues, not only for networks in IEEE 802.22 standard, but also to other technologies such as femtocell [6] and cellular networks [8]. The following recent studies can be highlighted. Gardellin et al. [2] address the coexistence of WRANs in IEEE 802.22 networks proposing two channel assignment schemes for cooperative and non-cooperative devices. The channels are selected based on the cumulative interference that all WRAN cells cause on individual cells, which is evaluated by measuring the corresponding SINR. In the cooperative approach, nodes are grouped together and operate as a single entity. The allocation of channels within a group is performed by an exhaustive search algorithm. The control of the complexity of the exhaustive search is done making the number of members of each small subgroup. The non-cooperative method is iterative and continuously takes local channel assignment decisions in order to maximize spatial reuse and minimize interference. Salameh et al. [9] propose a channel allocation mechanism that tries to avoid the blocking of secondary users through a min–max algorithm, which is adaptive and distributed. Time is divided into intervals that include a beacon interval and a data transmission interval. Each WRAN cell maintains a traffic table, which is updated with the information exchanged in the beacon messages, which inform the channels currently available, the expected number of transmission of secondary users and the sequence of beacon transmissions. The traffic demand is normalized in relation to the smallest need for traffic, and available resources are divided and allocated to the cells. Shi et al. [11] propose a spectrum sharing scheme for self-coexistence in IEEE 802.22 networks. Orthogonal frequency division multiple access (OFDMA) is used at the physical layer, with frames divided into subframes upstream downstream. Downstream subframes contain network control information and data, while the upstream subframe contains only data. Neighboring cells overlapping WRAN exchange information. On that basis, cells are organized in groups where the coexistence mechanism operates. Channel allocation is performed by the leader of the group, which collects and maintains channel allocation information. The leader makes allocation decisions based on the assignment of inter-cell channels that indicates which channels are allocated to the cells and the corresponding frames. A cell can join multiple groups and can receive various functions of each.

Among the proposals that use graph coloring, we highlight the algorithms UGC (utility graph coloring) from [10] and ESC (exclusive self-coexistence) from [1]. UGC performs in three steps, first finding the minimum number of colors (representing channels) required to cover all nodes (representing WRANs). Then it maximizes the use of one of the colors, by testing if its use does not result in conflicts, and replaces used colors by the one it intends to maximize the use. After maximizing the use of the chosen color, the spectrum is divided according to three strategies that are described in Section 3. ESC proposes a solution for channel allocation for the case where the number of channels is insufficient, and where multiplexing is required. It introduces a method that allocates bandwidth proportionally to the demand. It is assumed that each BS is able to recognize the WRANs with which it can communicate, being responsible for informing to the coordinator the WRANs it is able to listen, as well the available frequencies it has identified. The BS also reports to the coordinator its own bandwidth requirements. The two mentioned propositions have characteristics in common with our proposition, since both propose a centralized procedure for allocation of channels, and make use of graph coloring. The UGC algorithm assumes that all nodes operate on the same set of frequencies, which can be a limiting factor in its applicability. The ESC algorithm uses time multiplexing to allocate channels where there are not enough frequencies for each WRAN. It provides a solution that is capable of distributing channels in environments where not all networks have the same frequency set available. From a practical standpoint, UGC is unfeasible for use in large scenarios.

This paper presents a scalable graph coloring approach to solve the channel allocation problem, where the available bandwidth is organized in sub channels that have the minimum bandwidth required for the operation of a WRAN. We describe two different allocation strategies: the first procedure colors the nodes with highest degree first, and the second applies an heuristic to maintain the proportionality between the required and the allocated bandwidth. This last approach is explored in two versions, one that allocates all available bandwidth and the other that stops allocation when the demand of all WRANs is met. We compare the proposed algorithms with UGC, evaluating the utility of the spectrum and the mean square deviation of allocated bandwidth to the required bandwidth. In the next section we detail the proposed algorithms. We discuss the results in Section 3 and present our conclusions in Section 4.

2 Algorithms

The considered scenario includes a set of WRANs with possible overlapping of communication spectrum and interference between them. We consider the WRANs involved have a trust relationship with a central entity that performs channel allocation, what is a common assumption in the literature (see, for example, [1]). We also consider that the equipments follow IEEE 802.22 standard, and that the demand for bandwidth for each WRAN is known. Also, the WRANs functioning according to the IEEE 802.22 standard operate on secondary mode. The possibility of a CPE pertaining to one WRAN migrate to another, owned by a different organization, is not considered.

We consider the following assumptions: (i) The exchange of messages between different WRANs occurs according to the IEEE 802.22 co-existence protocols, that is, WRANs exchange messages through BSs or CPEs. (ii) WRANs always have a way to communicate with the central node, either to inform the result of sensing or to receive channel allocations from the central node. (iii) Overlapping WRANs may not have the same frequencies available. This information is collected through sensing by BSs and consolidated at the central node. (iv) A BS in conflict is aware of the channels that are available for use in the area it operates. It also knows the existence of other WRANs placed in its communication range. WRANs exchange this information via the co-existence protocol, possibly using CPEs as a bridge. (v) A WRAN knows the location of CPEs that are within a conflict area, and the channels available for its use.

The problem is modeled by a graph, where the nodes are WRANs and each edge represents the interference between the nodes. The goal is to assign different sub channels for interfering WRANs. The channel allocation is solved by a graph coloring approach, where the channels are represented by colors to be assigned to the nodes. The logical topology is represented by the graph $G = (V, E)$ , where V is the set of nodes representing the WRANs and E is the set of edges representing the interference (see Fig. 1).

Fig. 1.

Logical topology.

The number of WRANs is given by $N = | V |$ . The nodes are identified by $i = 1, \dots, N$ . The first parameter to the algorithms is G, while the second is the vector $q$ , which contains the nodes ordered according to the coloring logic, as explained below. We assume that the number of available non-multiplexed channels is M, each one with bandwidth ${BW}_{ch}$ . The algorithms follow an iterative-based approach where at each iteration it applies a different channel multiplexing level which will determine the sub channel bandwidth. The multiplexing level is identified by $k = 1, \dots, T$ , which also identifies the current iteration of the algorithm. The parameter T represents the maximum multiplexing level and it is limited by the minimum required bandwidth. At iteration k the sub channel bandwidth is defined by ${BW}_{sub}^{k} = {BW}_{ch} / k$ . The minimum bandwidth that can be allocated to a WRAN is ${BW}_{\min} = {BW}_{ch} / T$ . At the kth iteration the number of available sub channels is $(M \cdot k)$ and the set of available colors is ${AC}^{k} = {1, \dots, (M \cdot k)}$ . In order to represent the different set of channels available for each WRAN we introduce the matrix $av$ (of dimension $N \times (M \cdot k)$ ) that identifies the colors available for the WRAN i in the iteration k, such that ${av}^{k} [i, j] = 1$ if color $j \in AC$ is available for WRAN i in interaction k and ${av}^{k} [i, j] = 0$ otherwise. The classic graph coloring algorithms allocate only one color to each node. In our proposal, if possible and desirable, you can assign more than one color to a node. The final bandwidth allocated to a node is calculated by multiplying the number of assigned colors to ${BW}_{sub}^{k}$ , where k is the last iteration. Distinct WRANs can have different demands, which are stored in the demand vector $d^{k} = [d_{1}, d_{2}, \dots, d_{N}]$ , where $d_{i}$ is the demand of node i.

The algorithm CLF (Coloring Largest First) assigns colors to nodes equitably according to the availability of colors (see Algorithm 1). This procedure is based on the proposal in [5], which considers that nodes with lower degrees have more flexibility in choice of colors. The approach is to color nodes with higher degree first, thus $q$ contains the list of nodes belonging to V, ordered decreasingly with respect to their degrees.

Algorithm 1.

CLF (G, $q$ )

The algorithm CBD (Coloring Based on Demand) assigns colors to nodes until the demand is met in every node, and stops even if there are still colors (sub channels) available (see Algorithm 2). The order in which nodes are colored follows a sequence inspired by the technique proposed by [1]. To define the sequence, the normalized demands are stored in vector $q$ computed by $q = p \cdot ln (m + 1),$ (1) where $p_{i}$ contains the number of colors required by node i; and $m_{i}$ contains the number of colors that are already allocated to node i. Thus, $q_{i}$ contains the contribution to reach the normalized demand when node i is colored. Vector $q$ is ordered in decreasing order before calling Algorithm 2.

Algorithm 2.

CBD ( $G, q$ )

The algorithm CPD (Coloring Proportionally to the Demand) is similar to CBD, except that it does not end the assignment of colors when the demand of the nodes are met. The algorithm continues assigning colors until they are depleted. As it follows the same criteria adopted in Algorithm 2, it maintains the proportionality between what is assigned to a node to what is demanded.

3 Evaluation

Three variables are considered in the performance evaluation presented in this section: the average degree of the nodes; the amount of nodes; and the amount of spectrum used by primary operators. Three experiments are described, and in each, only one variable is changed. Although the algorithms proposed in Section 2 can be executed in a scenario where the available communication spectrum is distinct among WRANs, so they can be compared with the UGC algorithm, all experiments consider the same availability for all WRANs. This means that all the conflicting WRANs have the same set of channels available. The graphs are connected and randomly generated. All simulations were performed 30 times and the results represent the mean values.

In the figures shown in this section, the legends that represent the values obtained by the UGC algorithm refer to the three approaches proposed in [10]: UGC-1 allocates a minimum amount of bandwidth to all colors except to the one that is mostly repeated in the graph that. This is the most present color, which receives the maximum bandwidth. UGC-2 splits equally the bandwidth among the nodes. UGC-3 divides the available bandwidth among the minimum number of colors needed to cover the graph.

The experiments evaluate the algorithms based on three metrics: the utility of the electromagnetic spectrum; the mean square deviation between the required and the allocated bandwidth; and the normalized mean square deviation (please, see the definition bellow). Evaluations compare the three approaches of the UGC algorithm and the three approaches described in Section 2. To calculate the spectrum utility we multiply the total bandwidth allocated by channel size, in the same way described in [10].

The mean square error ( $MSE$ ) is given by $MSE = \sqrt{\frac{1}{N} \sum_{i = 1}^{N} {(dm [i] - as [i])}^{2}},$ (2) where ${dm}_{i}$ stores the demand of node i, and ${as}_{i}$ the total bandwidth allocated to the node i. The normalized mean square error ( $NMSE$ ) is calculated from the normalization of the demands and allocations.

In the first simulation the independent variable is the percentage of used space in the spectrum of primary operators. The parameters are presented in Table 1.

Table 1

Simulation 1 parameters

Parameter	Value
Average node degree	3
Number of nodes in the graph	10
Available channels (primary + secondary)	60
Minimum sub channel bandwidth	6 MHz
Number of requested sub channels	1, 5, 5, 5, 3, 5, 7, 5, 5, 6

Fig. 2.

Utility of spectrum (Scenario 1).

As expected, Fig. 2 shows that the amount of spectrum for WRANs decreases as the space released by primary users decreases. It can be seen that CBD obtains the worst result, since it terminates execution as long as it allocates the amount of bandwidth demanded by the nodes. The best performing approaches are CLF, CPD and UGC-1, which reach similar performance.

Fig. 3.

Mean square error (Scenario 1).

Fig. 4.

Normalized mean square error (Scenario 1). (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150508.)

Figure 3 shows the variation of the $MSE$ . It is observed that UGC-1 introduces a larger deviation than the others. This is because it prioritizes one channel over the others. The deviation introduced by the CBD is nil, since it would introduce deviations only in scenarios where there is not enough bandwidth to meet the demand. UGC-3, CBD and CLF show similar results. UGC-2 introduces slightly larger deviations, because it also prioritizes the use of spectrum. We can also observe that $MSE$ decreases when the bandwidth available for WRANs decreases (i.e., the bandwidth used by primary operators increase). This is because the algorithms distribute the exceeding bandwidth, what is considered a deviation. If there is exceeding bandwidth, the less the bandwidth, the less the deviation.

The $NMSE$ remains constant, independent of space spectrum occupied by primary users. The largest $NMSE$ is introduced by UGC-1, while the smallest is introduced by CLF (see Fig. 4). Considering only the methods that distribute the exceeding bandwidth, the best result is obtained by CBD. The values shown in Fig. 4 are different from zero because when you take into account the combination of neighbor nodes, this can generate constraints that prevent the free distribution of colors.

In the second simulation, both the number of nodes and the percentage of space used by primary users were fixed in 20% and 30%, respectively. The graphs were generated randomly varying the average node degree. The parameters are shown in Table 2.

Table 2

Simulation 2 parameters

Parameter	Value
Number of nodes in the graph	20
Available channels (primary + secondary)	60
Minimum sub channel bandwidth	6 MHz
Number of requested sub channels	1, 5, 5, 5, 3, 5, 7, 5, 5, 6
Number of requested sub channels	2, 4, 4, 4, 6, 8, 1, 3, 5, 6

Fig. 5.

Utility of spectrum (Scenario 2).

We can see in Fig. 5 that all approaches, except CBD, reduce the utility as the average node degree increases. This is because denser graphs typically have more restrictions on the use of colors when compared to less dense graphs. CBD was not affected by the node degree variation because it stops channel allocation when it reaches the desired demand, and available spectrum was sufficient to meet the demand even at the highest graph density. CLF, CPD and UGC-1 present very close performance with respect to the utility, repeating the result found in the first simulation. Considering that the goal of UGF-1 is to maximize the utility, while the goal of CPD is to seek a valid solution that maintains proportionality with demand, we can conclude that the latter is competitive with respect to the efficiency of spectrum use, even maintaining the proportionality of distribution.

Fig. 6.

Mean square error (Scenario 2).

The mean square deviation decreases as the average degree of nodes increases in the second scenario (see Fig. 6). This is because the chances of reusing a color decrease with the new restrictions and, consequently, this reduces reuse. As expected, the CBD has zero deviation and UGC-3 shows the largest deviation for all node degrees. UGC-1 approach presents the highest normalized mean square deviation (see Fig. 7). When we consider only those methods that try to distribute all channels, CPD is the method that has the lowest proportional deviation, which will be zero when the number of available colors is multiple of channel needs.

Fig. 7.

Normalized mean square error (Scenario 2). (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150508.)

In the third simulation we fix the average degree in 3 and the space used by primary users in 30%, varying the amount of nodes. The simulation parameters are shown in Table 3. The demands remain fixed for the same number of nodes, e.g., for 10 nodes, the first 10 demands are used, for 15 nodes, the first 15 demands are used, and so on.

Table 3

Simulation 3 parameters

Parameter	Value
Average node degree	3
Available channels (primary + secondary)	60
Minimum sub channel bandwidth	6 MHz
Number of requested sub channels	1, 5, 5, 5, 3, 5, 7, 5, 5, 6
	2, 4, 4, 4, 6, 8, 1, 3, 5, 6
	10, 5, 8, 4, 7, 7, 1, 5, 4, 8

Fig. 8.

Utility of spectrum (Scenario 3).

In Fig. 8, we can see an increase of the utility of the spectrum when the number of nodes increases. This is observed because the more nodes we have in the graph, more opportunities to reuse the spectrum. UGC-1, CLF and CPD present the greatest utility with equivalent results. However, as the graph size increases the difference between the methods increases.

Fig. 9.

Mean square error (Scenario 3).

The $MSE$ behavior for the third simulation is shown in Fig. 9, which remains almost stable regardless of the number of nodes. The largest deviations are observed in the UGC-1 and UGC-2 approaches, while the lowest are observed in CLF, CPD and UGC-3. Again, CBD presents zero mean square deviation.

Fig. 10.

Normalized mean square error (Scenario 3). (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150508.)

The $NMSE$ behavior can be seen in Fig. 10 and as in the previous simulations, the CPD is the algorithm that shows the lowest deviation, among the methods that involve the distribution of the excess channel. UCG-1 is the one that shows the largest. The CLF approach, as observed in other scenarios, presents $NMSE$ similar to that presented in UGC-3. This is because both methods color graphs directly, without any additional strategy, and the only difference between them is that UGC-3 allocates with just one color and the total bandwidth that can be provided for the corresponding channel, and CLF assigns different colors associated with a predetermined band.

4 Conclusion

This paper addressed channel allocation to coexisting WRANs adherent to the IEEE 802.22 standard. It provides a solution that is capable of distributing channels in environments where not all networks have the same frequency spectrum available. It proposes three different algorithms to solve the problem, which are evaluated and compared to the algorithms proposed in [10]. The results indicate that CPD is the algorithm that gets the best results by maximizing the utility of the spectrum and minimizing the mean square deviation of the requested bandwidth with respect to the delivered bandwidth.

To continue this work we intend to investigate the use of other graph coloring algorithms, including alternative strategies to obtain the proportionality between the requested and allocated bandwidth. A distributed version of the algorithms is also being investigated, what would increase the system reliability and eliminate the assumption of a trusted central entity. Finally, despite the fact that this study is applied for a scenario involving the IEEE 802.22 standard, it could be applied in other scenarios involving cognitive radios.

References

[1]

Camarda,

Cormio and

Passiatore, An exclusive self-coexistence (ESC) resource sharing algorithm for cognitive 802.22 networks, in: 2010 5th IEEE International Symposium on Wireless Pervasive Computing (ISWPC), May 2010, 2010, pp. 128–133.

[2]

Gardellin,

Das and

Lenzini, Self-coexistence in cellular cognitive radio networks based on the IEEE 802.22 standard, Wireless Communications, IEEE 20(2) (2013), 52–59.

[3]

Kim and

Shin, Asymmetry-aware real-time distributed joint resource allocation in IEEE 802.22 WRANs, in: INFOCOM, 2010 Proceedings IEEE, March 2010, 2010, pp. 1–9.

[4]

C.-H.

Ko and

H.-Y.

Wei, Game theoretical resource allocation for inter-BS coexistence in IEEE 802.22, IEEE Transactions on Vehicular Technology 59(4) (2010), 1729–1744.

[5]

Kosowski and

Manuzeewski, Classical Coloring of Graphs,

Kubale, ed., 2004.

[6]

S.-Y.

Lien,

C.-C.

Tseng,

K.-C.

Chen and

C.-W.

Su, Cognitive radio resource management for QoS guarantees in autonomous femtocell networks, in: 2010 IEEE International Conference on Communications (ICC), May 2010, 2010, pp. 1–6.

[7]

Monteiro,

Pujolle,

Pellenz,

Penna,

Enembreck and

Demo Souza, An optimal channel assignment strategy for WLANs using distributed optimization, in: Network Operations and Management Symposium (NOMS), 2012 IEEE, April 2012, 2012, pp. 286–292.

[8]

M.-V.

Nguyen and

H.-S.

Lee, Effective scheduling in infrastructure-based cognitive radio networks, IEEE Transactions on Mobile Computing 10(6) (2011), 853–867.

[9]

Salameh,

Jararweh,

Aldalgamouni and

Khreishah, Traffic-driven exclusive resource sharing algorithm for mitigating self-coexistence problem in WRAN systems, in: Wireless Communications and Networking Conference (WCNC), 2014 IEEE, 2014, pp. 1933–1937.

10.

[10]

Sengupta,

Brahma,

Chatterjee and

S.S.

Nandagopalan, Self-coexistence among interference-aware IEEE 802.22 networks with enhanced air-interface, Pervasive and Mobile Computing 9(4) (2013), 454–471.

11.

[11]

Shi,

Prasad,

Niemegeers,

Xu and

Rahim, Self-coexistence and spectrum sharing in device-to-device WRANs, in: 2014 IEEE International Conference on Communications (ICC), June 2014, 2014, pp. 1651–1656.

12.

[12]

C.R.

Stevenson,

Chouinard,

Lei,

Hu,

S.J.

Shellhammer and

Caldwell, IEEE 802.22: the first cognitive radio wireless regional area network standard, Comm. Mag. 47(1) (2009), 130–138.

13.

[13]

S.-F.

Yang and

J.-S.

Wu, A spectrum sharing method based on fuzzy logic in IEEE 802.22 WRAN, in: 2010 International Conference on Wireless Communications and Signal Processing (WCSP), October 2010, 2010, pp. 1–5.