Qualityofservice (QoS) provisioning for a cognitive mesh network (CMN) with heterogeneous services has become a challenging area of research in recent days. Considering both realtime (RT) and nonrealtime (NRT) traffic in a multihop CMN,
[1]
studied crosslayer resource management, including joint access control, route selection, and resource allocation. Due to the complexity of the formulated resource allocation problems, which are mixedinteger nonlinear programming, a lowcomplexity yet efficient algorithm was proposed there to approximately solve the formulated optimization problems. In contrast, in this work, we present an application of genetic algorithm (GA) to readdress the hard resource allocation problems studied in
[1]
. Novel initialization, selection, crossover, and mutation operations are designed such that solutions with enough randomness can be generated and converge with as less number of attempts as possible, thus improving the efficiency of the algorithm effectively. Simulation results show the effectiveness of the newly proposed GAbased algorithm. Furthermore, by comparing the performance of the newly proposed algorithm with the one proposed in
[1]
, more insights have been obtained in terms of the tradeoff among QoS provisioning for RT traffic, throughput maximization for NRT traffic, and time complexity of an algorithm for resource allocation in a multihop network such as CMN.
1. Introduction
T
o accommodate the explosively growing data traffic in a large coverage area, cognitive radio based wireless mesh network or cognitive mesh network (CMN) has been considered as one of the most promising solutions
[1

3]
. By using cognitive radio, CMN is capable of utilizing spectrum resource from primary spectrum such as TVband spectrum. However, to protect the transmission of primary users, a cognitive radio shall switch among primary channels if a primary user returns to the channel it uses, leading to timevarying capacity of a cognitive radiobased network
[4]
. As such, qualityofservice (QoS) provisioning for such a network is a challenging issue.
In the literature, there exist a number of research works studying resource allocation and/or QoS provisioning for cognitive radio networks (CRNs).
[5]
studied joint spectrum allocation, scheduling, and flow routing such that the required networkwide radio spectrum in a CRN is minimized. By integrating pernodebased power control, the algorithm proposed in
[6]
can minimize the networkwide bandwidthfootprintproduct (BFP) of a CRN. With physical layer signaltointerferenceandnoiseratio (SINR) model,
[7]
studied capacity maximization for CRNs by jointly optimizing power control, scheduling, and flow routing. However, the heterogeneous services which can coexist in a CMN and the support of their differentiated QoS requirements were not taken into account in the aforesaid works. In contrast, QoS provisioning for heterogeneous services in CRNs was studied in some recent works (e.g.,
[8

10]
). In
[8]
, QoS differentiation between realtime (RT) and nonrealtime (NRT) secondary users (SUs) was achieved at the call level when allocating channel between the two types of users. Studied in
[9]
and
[10]
were joint channel and power allocation with the objective of maximizing network capacity while providing minimum rate guarantee for SUs with RT traffic and fair rate sharing among SUs with NRT traffic. However, as these works mainly focus on singlehop CRNs, directly applying these schemes in a multihop CMN can be ineffective or inefficient.
Differently, by considering heterogeneous traffic consisted of both RT and NRT traffic in a multihop setting of CMN, studied in
[1]
were crosslayer resource management, including joint access control, route selection, and channel and power allocation. Mathematically, the crosslayer resource allocation problem studied in
[1]
was formulated as three optimization subproblems. The first one was to select route requested by any new flow, with the objective of choosing a route with maximal expected transmission rate, and it was addressed by the shortestpathbased algorithm. The other two were on joint channel and power allocation, which, respectively, were for RT flows with the objective of minimizing consumed network resources but serving as many RT flows as possible and for NRT flows with the objective of maximizing the total background throughput. Both were formulated as interrelated NPhard mixedinteger nonlinear programming (MINLP) problems. The access control for RT flows was implemented accompanied with route selection and channel and power allocation. By using a twolevel decoupling approach, a lowcomplexity yet efficient algorithm was proposed to approximately solve the highcomplexity MINLP problems. Simulation results show the effectiveness of the proposed algorithm in terms of improving both the RT flow’s mean access ratio and the NRT flow’s mean throughput. However, due to the complexity of the formulated channel and power allocation problems, the algorithm proposed in previous works
[1]
failed to show the optimal performance of a CMN when supporting both RT and NRT traffic.
To have an indepth understanding of the performance of a CMN supporting heterogeneous services including both RT and NRT traffic, in this work we present an application of genetic algorithm (GA) to readdress the resource allocation problems (channel and power allocation for both RT and NRT traffic) studied in
[1]
. The newly proposed GAbased algorithm can be treated as the optimal solution, because GA has been proven to be effective in solving NPhard problems
[11
,
12]
. The main contributions and significance of this work are twofold.
First of all, we propose a novel GAbased algorithm that is tailored for the channel and power allocation for a multihop CMN with both RT and NRT traffic. Novel initialization, selection, crossover, and mutation operations are defined such that solutions with enough randomness can be generated and converge with as less number of attempts as possible, which improves the efficiency of the algorithm effectively. Apart from this, elitism strategy is integrated into the algorithm design to guarantee the performance of the proposed algorithm.
Secondly, the effectiveness of the proposed GAbased algorithm can be observed from simulation results, especially in increasing the access ratio of RT flows. Furthermore, with the GAbased algorithm, the tradeoff between QoS provisioning for RT flows and throughput maximization for NRT flows can be more obvious, because the GAbased algorithm is able to fully utilize network resources to admit as many RT flows as possible. Additionally, by comparing the performance of the newly proposed algorithm with the algorithm designed in
[1]
, more insights have been obtained in terms of the tradeoff among QoS provisioning for RT traffic, throughput maximization for NRT traffic, and time complexity of a resource allocation algorithm.
The remainder of this paper is organized as follows. A short review of applying GA to resource allocation for wireless networks is provided in Section 2. Section 3 introduces the system model reused from
[1]
. The GAbased algorithm tailored for RT traffic resource allocation (named GART) and that for NRT traffic resource allocation (named GANRT) are described in Sections 4 and 5, respectively. After presenting our simulation results in Section 6, we conclude this paper in Section 7.
2. Related Work
In this section, we present a short review of the recent works that apply GAbased algorithm to resource allocation for wireless networks. Considering a multicell scenario with nonuniform traffic distribution in multihop networks, the search for the optimal topology is an NPhard problem. To address the aforesaid issue,
[13]
proposed a novel sequential genetic algorithm in which topologies were encoded as a set of chromosomes and special crossover and mutation operations were proposed. Both high performance improvements in the system and fast convergence compared with exhaustive search were shown in the numerical test. In CRNs, to mitigate the impact of spectrum usage termination and switching, minimum interference robust topology construction (MIRTC) is a critical problem. In
[14]
, MIRTC was formulated as an integer programming problem and was addressed by a geneticalgorithmbased channel assignment (GACA) scheme, which could construct a robust CR topology while minimizing interference. In
[15]
, based on genetic algorithm an adaptive intelligent task mapping together with a scheduling scheme was proposed to provide a realtime guarantee for parallel processing in a multihop wireless network. Furthermore, to alleviate power scarcity of a multihop wireless network, a hybrid fitness function was devised and embedded in the algorithm to extend the overall network lifetime. Studied in
[16]
was NPhard reinforced backbone network deployment problem, with the practical consideration of the limitation of available backbone nodes and the enforcement of backbone network connectivity. In that work, GA was treated as the optimal solution to find the performance bound of the proposed heuristic algorithm. In
[17]
, with a goal of maximizing the service provider’s revenue taking into consideration user churn behavior, the authors studied power constrained discrete rate allocation (PCDRA) problem in a CDMA data network. Due to its proved NPComplete complexity, two GAbased algorithms were proposed to solve the problem. Considering a cochannel deployment of femtocells in a macrocell network,
[18]
formulated a multiobjective optimization problem with the objectives of maximizing the throughput of all users and increasing the power efficiency of femtocell base stations. The authors solved the problem by using nondominated sorting genetic algorithm version II. In
[19]
, GAbased approach was combined with KarushKuhnTucker (KKT)driven approach to solve the joint powersubcarriertime intracluster resource allocation problem in wireless mesh networks, which was proved as an NPhard problem.
3. System Model
In a multihop CMN as considered in
[1]
, heterogeneous traffic is characterized by two classes of coexisting traffic, namely realtime traffic and nonrealtime traffic. The network is aimed at supporting QoS provisioning and service differentiation for both types of traffic. The important symbols defined in
[1]
and reused in this paper are summarized in
Table 1
.
Summary of Important Symbols
Summary of Important Symbols
In this paper, we consider slotbased resource allocation, integrating functions, including joint access control, and channel and power allocation, via the following two optimization problems. For more details, interested readers are suggested to refer to
[1]
. Specifically, RT traffic is allocated channel and power resource ahead of NRT traffic, due to its high priority. For the RT flows, we try to serve as many RT flows as possible. If there are too many RT flows as compared with the amount of network resources, we adopt the strategy of firstinfirstserved (FIFS) which means the RT flow that arrived last is ignored and so on. Once the network resources are sufficient for RT flows, we try to minimize networkwide resources consumed by RT flows while guaranteeing their data rates, thus leaving as many network resources as possible for NRT flows to boost background throughput. Resource allocation for RT flows is formulated as:
where (1a) is the cost function representing the total radio resources, including channel
x_{RT}
and power
p_{RT}
, consumed by the RT flows in Λ
_{RT}
, (1b) describes that any channel of a node can be used to either transmit or receive one flow from one neighboring node, (1c) means that the actual flow rate must be greater than the minimum rate requirement
R
(
l
) for this RT flow, with
representing the received SINR (taking the maximum interference from the NRT flows into account) on channel
m
of link (
i
,
j
) given RT flows’ power allocation
p_{RT}
and
the mean effective transmission rate of the same channel given received SINR
γ
for more details, see
[1]
), (1d) is the power constraint which means that the total power at a node is limited, and (1e) gives the range of each optimization variable.
Due to the fact that the NRT flows are assigned with a low priority, we only allocate remaining allocatable channel and power to the NRT flows. When allocating resources to the NRT flows, we adopt the strategy of best effort, which means that we try to use up all remaining resources to boost the overall throughput of the NRT flows. With the objective of maximizing throughput, we formulate the optimization problem for the NRT flows as:
where
x_{NRT}
,
p_{NRT}
, and
Ψ
= [
r
(
l
)]
_{1×∧NRT}
are optimization variables, corresponding to channel allocation, power allocation, and endtoend flow transmission rate, respectively, with
r
(
l
) being the transmission rate of NRT flow
l
and defined as the lowest rate on all hops of flow
l
, (2b) is the channel allocation constraint implying that any channel of a node can be used to either transmit or receive one traffic flow from one neighboring node, (2c) means that the transmission rate over each hop of an NRT flow must be no less than the flow’s endtoend transmission rate, (2d) is the power constraint which means that the total power at a node is limited to the remaining power after the allocation for the RT flows, (2e) denotes that the interference from the NRT flows to any RT flow cannot be greater than the tolerable interference Δ(i.e., the interference cushion), (2f) gives the range of each optimization variable. Although here we adopt a twostep approach to decouple the resource allocation for the two types of coexisting RT and NRT traffic, resource allocation for each of them is interrelated with each other through interference cushion involved constraints (1c) and (2e).
Since
and (1c) in OP1 are integer variable and nonlinear constraint (for more details, see
[1]
), respectively, OP1 is a mixedinteger nonlinear programming (MINLP), which is NPhard in general
[20]
. Similarly, we can find that OP2 is also anMINLP problem. Since GA has been shown to be an effective way in finding the global optimal solution
[11
,
12]
, we will present the application of GA in seek of the solution that can achieve the optimum, i.e., the performance bound of the network.
4. GAbased RT Traffic Resource Management
Due to the high priority, we first allocate resources to RT traffic. Accordingly, in this section, a GAbased algorithm (named GART) is firstly proposed to solve the RT traffic resource allocation problem formulated as OP1. It starts with an initial population of individuals characterized by chromosomes, and then improves the quality of the population through evolution. In each generation, three operations are carried out one by one to yield a new population, which are: 1) selection; 2) crossover; and 3) mutation. Due to the multiple complex constraints of the optimization problem, novel approaches are designed to facilitate the implementation of the proposed GAbased algorithm. In the following, we first explain the encoding scheme on which the algorithm is based, and then introduce our design for each of the aforesaid operations.
 A. Encoding Scheme
Before the resource allocation, the gateway node which plays the role of resource manager, needs to collect sensing results and traffic demands in the network
[1]
. The results about all
nl
available links in the network in current slot are recorded in a matrix
chromosomes_format_info
(see
Fig. 1
). Specifically, the information on each link, namely, the sender and the receiver of this link, and the number of available channels and that of flows allocated over this link are recorded in
sender
,
receiver
,
available_chl_num
, and
flow_num
, respectively. Besides, the index of available channels and that of flows over each link are recorded in matrices
available_chl_idx
and
flow_id
, respectively. The collected information facilitates the following coding for chromosomes.
The structure of chromosomes_format_info
A chromosome or an individual of the population corresponds to a channelpower allocation that needs to be optimized. It is coded as a vector shown in
Fig. 2
, where
denotes the number of available channels over available link
i
. Moreover, each available channel of a link should be allocated to at most one single flow with constrained transmit power for the sender.
A genetic representation of a set of feasible solutions to the optimization problem
 B. Initialization
To start the GA we need to set up an initial population of a number of chromosomes. In
Fig. 2
,
Q
chromosomes are generated. For OP1, the initialization process includes both channel and power allocations. Normally, both the allocations in an initial solution should be generated randomly. But, in this case, due to the channel constraint (1b) and the rate requirement (1c), total randomness causes the initialization to fail frequently, leading to many attempts, which reduces the efficiency of the algorithm significantly. To address this issue some novel strategies are adopted when allocating channel and power.
Considering the interference between RT flows, first we finish channel allocation (i.e., flow assignment) for all links, and then allocate power to all channels with flow assignment. To ensure sufficient randomness, we allocate channel to different chromosomes in a random order of links. Further, for any chromosome, when allocating channel, we record the used channels at each node, and only allocate unused channels in order to satisfy (1b). For any link (say link
i
), a necessary condition for a successful channel allocation is
where
denote the number of flows and the number of allocatable channels on link
i
, respectively. Specially, if
, the channels are definitely insufficient and the RT flow that arrived last should be suspended. Besides, to support all the flows on link
i
, each flow is allocated a channel firstly. For the remaining unused channels on link
i
, we allocate each of them randomly to one of the flows on the link, with probability
p_{init}
. Accordingly, the probability that this channel is not used is (1 
p_{init}
).
When the channel allocation is successful, we allocate power to the channels in use. Due to the rate requirement (1c), we find that, in contrast to random power allocation, equal power allocation is more likely to satisfy (1c). Thus we count the number of times each node is used as a sender to transmit RT flows and equally allocate power to the channels that have the same sender, so that (1d) is satisfied. However, if equal power allocation meets requirement (1c), to generate sufficient randomness we reduce the power used on each channel by a random value up to
d
_{1}
(in percent) which is preset, otherwise we regard power allocation as failed and try to reallocate channel again and begin to delete RT flows after certain number of attempts. We keep reducing the power for at most
N_{p}
times until (1c) is unsatisfied and use the latest feasible result, because using as less power for RT flows as possible can reserve more available resources for NRT flows in general.
The initialization stops if the total
Q
chromosomes are generated. If some chromosomes are failed to be generated after a sufficient number of generation attempts but at least one chromosome has been initiated, we can randomly duplicate the required chromosomes from those that have been initiated. It should be noticed that, if the network resources are too limited, OP1 can be infeasible and therefore it is possible that no chromosome can be initiated in this case. The algorithm designed for initialization is summarized in
Algorithm 1
, which consists of a triplenested loop (see Lines 3, 5, 30). Notice that the outmost loop at Line 30 corresponds to the case that we apply FIFS to reduce the number of RT flows due to the limited amount of network resources. Besides, in the innermost loop, three sequential subloops are enclosed, for flow assignment (Line 6), equal power allocation to all channels with flow assignment at any nodes (Line 18), and power reduction attempt (Line 22), respectively. Therefore, the time complexity of the algorithm is on the order of
O
(
N_{t}N_{c}
(
n_{l}
+
NM
+
N_{p}
)Λ
_{RT}
), where
N_{t}
,
N_{c}
,
N
, and
M
are the maximum number of generation attempts (defined in Line 3), the maximum number of channel allocation attempts (defined in Line 5), the number of nodes and that of channels in the network, respectively.
 C. Fitness Function and Selection Operation
During each successive generation, chromosomes that are fit enough are selected to survive and to breed a new generation. The wellknown RouletteWheel scheme
[21]
is used here, where each solution is picked with the probability related to a fitness function of the current solution. However, as the RouletteWheel scheme cannot be directly applied to a minimization problem such as OP1 and negative fitness values are not allowed (thus simply maximizing the negative value of (1a) is invalid), it is necessary to map the objective function (1a) to an appropriate fitness function form. The following transformation is considered
[22]
where
C
_{max}
is the maximum value of the objective function (1a) till current generation. More specifically, we define the objective function
f
(
x_{RT}
,
p_{RT}
,Λ
_{RT}
) in OP1 as:
After fitness calculation for the
Q
solutions, the fitness function of
pop_{i}
is recorded as
F_{i}
. Following elitism strategy
[23]
, we reserve the best chromosome satisfying
for the next generation directly. To improve the performance of the GA, the best chromosome will be kept throughout this generation. For the other (
Q
1) solutions in the next generation, we randomly pick them from the current generation. According to the Roulette Wheel scheme, the probability that
pop_{i}
in the current generation is picked is
The algorithm designed for selection operation is summarized in
Algorithm 2
. The time complexity of the algorithm depends mainly on the operation to find the best chromosome (Line 2) and the chromosome selection between Lines 4 and 11, thus is on the order of
O
(
Qn_{chl}
+
Q
^{2}
) =
O
(
Q
(
M
+
Q
)) , where
is the number of total available channels on all links that we have to check to derive
F_{i}
for a chromosome.
 D. Crossover Operation
To produce next generation, single point crossover method is applied in our algorithm. For solutions in current population, every two of adjacent ones make up a group (denoted as
parent
_{1}
and
parent
_{2}
) and go through crossover operation with probability
p_{co}
. At the beginning of crossover, we randomly select link
k
as a crossover point. Two children solutions denoted as
children
_{1}
and
children
_{2}
are generated by firstly duplicating the channelpower allocation of the links before link
k
from
parent
_{1}
and
parent
_{2}
, respectively, i.e.,
and then exchanging the channel allocation of the remaining parts from the two parents, i.e.,
Obviously, the first step of direct duplication will never violate channel constraint (1b); however, the second step is prone to make mistakes. Therefore, any violation of (1b) should be detected in the exchange process. If so, a new crossover point should be reselected.
The exchange of power allocation is implemented after a successful exchange of channel allocation. The blending method for power exchange follows the way for continuous value
[23]
. If the power levels allocated to
parent
_{1}
and
parent
_{2}
at the same channel (say channel
j
) over the same link (say link
q
) are
p
_{parent1}
(
q
,
j
) and
p
_{parent2}
(
q
,
j
), respectively, the power levels for their children at the same channel over the same link are
where
q
∈ {
k
+ 1,
k
+ 2,....,
n_{l}
}, and
α
is a random value on the interval [0, 1]. However, remedy might be still needed if power constraint (1d) is violated with such power blending. If so, we can readjust power allocation by taking into account both the maximal power a node can use and the allocated power of the link sender,
where
x_{u,q}
is an indicator which is equal to one if links
u
and
v
have the same transmitter and zero otherwise, and
β_{i}
is a random value on the interval [0, 1].
After power allocation, we check whether or not the children solutions satisfy rate requirement (1c). If not, we can first try different power allocations for a number of attempts and then turn to change the crossover position if necessary. Finally, if all possible crossover positions are used and failed, or we skip crossover operation at the beginning (with probability (1
p_{co}
)), we duplicate parent solutions directly. But, the best chromosome is kept from crossover due to elitism strategy. The algorithm for crossover operation is summarized in
Algorithm 3
. For the time complexity of the algorithm, we know that: 1) for a population of size
Q
the crossover operation is executed
Q
/2 times (Line 2); 2) to finish channel exchange, any channel crossover that violates (1b) initiates a new crossover link point selection (Line 10), thus contributing at most
n_{l}M
times of channel exchanges; and 3) to finish power exchange, any power crossover that violates (1c) initiates a new power allocation for every channel over the links after crossover link point, as long as the limit of power allocation attempts
N_{p}
is not reached (Line 14), thus generating at most
N_{p}n_{l}M
times of power allocations. To sum up, the time complexity of
Algorithm 3
is thus on the order of
O
(
Q
/2·(
n_{l}M
+
N_{p}n_{l}M
)) =
O
(
Qn_{l}MN_{p}
).
 E. Mutation Operation
To maintain genetic diversity and increase convergence rate, mutation is performed to alter some positions or genes in chromosomes randomly. But the solution with the highest fitness (i.e.,
pop_{best}
) is kept from mutation. For the other solutions, we alter the channelpower allocation in them with probability
p_{mut}
, which means that totally (1) ⎿
p_{mut}
×
n_{chl}
× (
Q
1)⏌positions are changed in mutation operation.
When mutating, we first randomly choose a mutation position. Let
m
_{RT}
denote the index of the channel related to the selected position. We record the channel and power allocation of other positions in this solution. Under constraint (1b), if the channel at
m
_{RT}
is not usable, we regard mutation in
m
_{RT}
as finished. Otherwise, we check whether or not current flow on this channel can quit by setting the power over channel
m
_{RT}
as zero and checking rate requirement (1c). If the requirement is not satisfied, we also consider this mutation as finished. Otherwise, we randomly choose one of the flows on the link
i
ncluding 0 which means this channel is not to be used after mutation.
Then we update power allocation. If the power over channel
m
_{RT}
is nonzero before mutation, we keep reducing the power by a random value up to
d
_{2}
(in percent) which is preset until rate requirement (1c) is not satisfied or we have tried at most
N_{p}
times, and use the last feasible power result. However, if the channel is not used before, we firstly allocate a random part of remaining power to this node and check (1c). On condition that (1c) is unsatisfied, we again try to reduce the power by a random value up to
d
_{2}
(in percent) until we have tried at most
N_{p}
times. If the attempt fails or there is no remaining power at first, we withdraw flow assignment. The algorithm for mutation operation is described in
Algorithm 4
. The time complexity of the algorithm depends mainly on the number of mutation attempts (see Line 4) and that of power adjustment attempts
N_{p}
(see Lines 14 and 20) and is thus on the order of
O
(⎿
p_{mut}
×
n_{chl}
× (
Q
1)⏌
N_{p}
) =
O
(
MQN_{p}
).
To sum up the GART algorithm, it is composed of an initialization operation and several iterations to improve the quality of the population. Each iteration includes three operations: selection, crossover, and mutation. As such, the time complexity of GART is on the order of
O
(
N_{t}N_{c}
(
n_{l}
+
NM
+
N_{p}
)Λ
_{RT}
 +
T
(
Q
(
M
+
Q
) +
Qn_{l}MN_{p}
+
MQN_{p}
)) , where
T
is the generation number.
5. GAbased NRT Traffic Resource Management
After allocating resource to RT traffic, to solve the NRT traffic resource allocation problem formulated as OP2, we design a GAbased algorithm (named GANRT), similar to the one proposed for RT traffic. However, as OP2 is to maximize the overall throughput of all NRT flows and more constraints (e.g., interference constraint (2e)) appear in the optimization problem, the algorithm proposed for OP1 cannot be directly applied to OP2. In the following, we introduce our design in applying GA to solve OP2 while mainly focusing on the difference between GART and GANRT. It is also worth mentioning that the encoding scheme for GART can be reused for GANRT.
 A. Initialization
To increase throughput of all NRT flows, in the initialization of GANRT we try to use up all remaining resources that are unoccupied by RT flows. Moreover, for different chromosomes, we allocate all remaining channels to NRT flows one by one in a random flow permutation order, which helps to generate sufficient randomness. When allocating these channels, in each allocation round we only assign at most one usable channel to each hop of a flow. Further, we separate disconnected NRT flows from connectable or connected NRT flows, and keep allocating channel to connectable or connected NRT flows until all of them cannot be allocated more channels. A flow will be marked as disconnected if channel allocation fails on a link of the flow before it achieves an endtoend connection. The channels allocated to a disconnected flow should be withdrawn and reused by other flows with certain probability.
When channel allocation finishes, we do power allocation under constraints (2d) and (2e). To ensure randomness under constraint (2d), for any sending node, with probability
p_{eq}
we equally allocate the remaining power to the channels with NRT flow assignment, which is similar to the equal power allocation adopted in GART’s initialization. On the other hand, with probability (1
p_{eq}
) we randomly allocate part of the remaining power to the channels with NRT flow assignment. Besides, if RT flows pose nonzero interference constraint on the transmitters of NRT flows (i.e., Δ ≠ 0), we might need to further reduce the power allocation by taking constraint (2e) into account. Thus we can ensure that both constraints are satisfied and we use as many channel and power resources as possible yet still generate enough randomness.
 B. Fitness Function and Selection Operation
Similar to GART, the selection operation of GANRT is based on the RouletteWheel scheme. The only difference lies in the fitness function. Because OP2 is to maximize the total NRT traffic throughput
, where
r
(
l
) is the transmission rate of NRT flow
l
and is defined as the lowest rate on all hops of flow
l
, the fitness function
H
(
x_{NRT}
,
p_{NRT}
,
Ψ
) for GANRT can follow the form
[21]
where
C
_{min}
is the minimum value of the objective function (2a) till current generation. Again, following elitism strategy, the best chromosome will be recorded and kept throughout the generation.
 C. Crossover Operation
The crossover operation of GANRT is designed as the same for GART in terms of the crossover of spectrum resource. The difference lies in the crossover of power allocation, because of the newly added interference constraint (2e). After channel crossover, the power levels for the children solutions at an available channel (say channel
j
) of a link (say link
q
) after the crossover point (say link
k
) are derived (denoted as
p
_{childrem1}
(
q
,
j
) and
p
_{childrem2}
(
q
,
j
) respectively) through (9) and (10). If
p_{childremi}
(
q
,
j
) is too large to satisfy (2d) and (2e), we readjust it by
where
q
∈ {
k
+ 1,
k
+ 2,...,
n_{l}
},
δ_{i}
is a random value on the interval [0, 1], and
denotes the remaining power the sender of link
q
can use for NRT traffic but excluding the power this node has already used for NRT traffic in links 1 to
q
, with
t
(
q
) representing the sender of link
q
and
x_{u,q}
an indicator implying whether or not links
u
and
q
have the same transmitter.
 D. Mutation Operation
The mutation operation in GANRT starts with fitness calculation, which identifies
pop_{best}
and further restricts the range of mutation positions in the remaining solutions. Similar to the mutation in GART, the one here at a specific position
m
_{NRT}
includes both channel and power reallocation. To reallocate channel, we shall find out whether or not the channel at a mutation position can be used under channel constraint (2b). If so, to utilize the channel, we also need to know whether there is enough remaining power under power constraint (2d). Besides, if the channel at position
m
_{NRT}
is used by a flow before mutation, we check whether this channel is the only channel that the flow uses at this hop as well. If the channel is unique, it cannot be reassigned to the other flow, or the original flow will break at this hop and its rate will fall into zero. Finally, under the circumstance that the channel at position
m
_{NRT}
can be allocated to the other flow, we randomly reallocate it to one of the flows on the link
i
ncluding 0 which means this channel is not to be used after mutation operation.
Power reallocation is implemented for any channel with successful flow reassignment. By considering the power constraints (2d) and (2e), power reallocated for a channel (say channel
j
) of a link (say link
q
) in a solution (say
pop_{i}
) can be given by
where
ρ
is a random value on the interval [0, 1],
is the remaining power the sender of link
q
can use for NRT traffic but excluding the power this node has already allocated to the channels of NRT traffic without requiring mutation, with indicator
y_{u,q,v}
representing whether or not links
u
and
q
have the same transmitter and channel
v
at link
u
requires mutation.
For the time complexity of the GANRT algorithm, given the same generation number and the same order for the number of RT flows and that of NRT flows, it should not be larger than that of the GART algorithm, because iterative power reduction adopted in the initialization and mutation operations in GART, to reserve as many power resources as possible, are avoided in the counterparts of GANRT. Moreover, no NRT flows have to be suspended and thus no iterative resource allocation as we do for RT flows is required, which further reduces the time complexity of GANRT. As such, the overall time complexity of the GAbased resource allocation for both RT and NRT flows in CMNs is on the order of that of GART as derived in Section 4.
6. Performance Evaluation
We consider a CMN with 9 nodes randomly located in 375m×375m coverage area. The spectrum is of 2.5MHz bandwidth and is partitioned into 12 channels, with each having a bandwidth of 208.33kHz. The impact of primary activity is studied in terms of the mean idle time of each channel. In the simulation, the mean idle time of each channel on any link
i
s set to be the same value
λ
. The RT and NRT traffic flows are generated according to a Poisson process with mean rate set as
λ_{RT}
flow/s and 0.5 flow/s, respectively. To restrict the running time of the proposed GAbased resource allocation algorithm, we set the maximal number of generations in both GART and GANRT as 20 and population size as 10. Further,
p_{init}
,
p_{co}
,
p_{mut}
,
p_{eq}
,
d
_{1}
,
d
_{2}
, and
N_{p}
used in GART and GANRT are 0.5, 0.8, 0.1, 5%, 5%, and 2000, respectively. Other system parameters are chosen according to
[1]
. To compare the performance of the newly proposed GAbased algorithm, the algorithm proposed in
[1]
, which utilizes a twolevel decoupling approach (i.e., decouple power allocation from channel allocation and channel allocation from link allocation) to allocate channel and then geometric program to solve power allocation, and the greedy algorithm adopted in
[24]
for comparison, which is based on greedy channellink mapping and uniform power allocation, are utilized. We perform the simulation by matlab on an Intel Xeon 3.47GHz machine for 40 times, and each run lasts for 20s of network time. The 95% confidence interval is also given.
Fig. 3
shows the relationship between the mean access ratio of RT flows and the mean idle time
λ
of each channel given different values of interference cushion. It can be seen that with an increase of
λ
, the access ratio of RT flows increases for any of the three algorithms, due to more opportunities to find an idle channel. Also, the access ratio decreases if the interference cushion Δ increases, since more network resources are reserved for NRT flows. From
Fig. 3
, we can find out that the proposed GAbased algorithm is better than the other algorithms in all simulated cases in terms of the mean access ratio of RT flows. For example, when Δ = 0 and
λ
= 9, the access ratios with the GAbased algorithm, with the algorithm proposed in
[1]
, and with the greedy algorithm are 84.33%, 69.78%, and 56.77%, respectively. Moreover, when Δ = 0, the access ratio with the GAbased algorithm is on average 15.79% higher than that with the algorithm proposed in
[1]
and 42.5% higher than that with the greedy algorithm.
Mean access ratio of RT flows vs. λ
In contrast to the access ratio of RT traffic,
Fig. 4
shows the simulation results of the mean throughput of NRT traffic. As observed, the throughput of NRT flows with each of the three algorithms increases as
λ
increases, due to the fact that increasing interference cushion reserves more network resources for NRT flows. Obviously, the GAbased algorithm performs better than the other two algorithms. When Δ = 10
^{8}
W and
λ
= 9s, the throughputs with the GAbased algorithm, with the algorithm in
[1]
, and with the greedy algorithm are 6.50Mbps, 4.67Mbps, and 3.09Mbps, respectively. Moreover, when Δ = 0, the throughput with the newly proposed algorithm is on average 39.07% (104.33%) higher than that with the algorithm in
[1]
(the greedy algorithm). However, it is also noteworthy that the throughput with the algorithm in
[1]
at Δ = 10
^{8}
W is higher than the throughput with the GAbased algorithm at Δ = 0. The reason is that, when Δ = 0, GA allocates a large amount of resources for RT flows, limiting the remaining resources for NRT flows. Similar observation will be made in
Fig. 11
when studying the impact of traffic load.
Mean throughput of NRT flows vs. λ
Fig. 5
compares the mean running time of the three algorithms. From the figure, we can find out that the mean running time of the algorithm in
[1]
is two orders of magnitude higher than the greedy algorithm but four orders of magnitude lower than the newly proposed GAbased algorithm. With an increase of
λ
, the mean running time increases slightly and converges because the network is saturated. Thus, we can conclude that GA improves the performance at the cost of time complexity. In addition,
Figs. 6

9
show the relationship between the average fitting value of allocating resource for RT traffic as well as that for NRT flows with the GAbased algorithm and the number of generations, at
λ
= 3s and 9s, respectively. From the figures, we can find out that, GA is easy to converge when
λ
is small and hard to converge when it is large. The reason comes from the fact that the number of the idle channels on all links increases with an increase of
λ
, which enlarges the searching space accordingly. In other words, for the GAbased algorithm, it is important to select an appropriate generation number in order to well balance the tradeoff between performance improvement and running time reduction.
Mean running time of the three algorithms vs. λ
Fitting value of allocating resource to RT flows vs. number of generations at λ=3s
Fitting value of allocating resource to NRT flows vs. number of generations at λ=3s
Fitting value of allocating resource to RT flows vs. number of generations at λ=9s
Fitting value of allocating resource to NRT flows vs. number of generations at λ=9s
Furthermore, we perform simulation to observe the impact of traffic load on the network performance by the proposed GAbased algorithm.
Fig. 10
shows the relationship between the mean access ratio of RT flows and the mean arrival rate
λ_{RT}
of RT flows given different values of interference cushion. From the figure, we can find that the mean access ratios of RT flows with the three algorithms firstly increase then decrease as
λ_{RT}
increases. The reason for the increase when
λ_{RT}
≤ 0.5 flow/s is that, as compared with the increased traffic load, the network might still have resources to serve a part of the increased RT flows. However, if the traffic load further increases, the network tends to be saturated. As such, the increasing RT flows are hard to be admitted, making the overall access ratio decline. The access ratio also decreases when interference cushion increases, because more network resources are reserved for NRT flows. Moreover, the GAbased algorithm obtains the highest access ratio as compared with the other two algorithms. For instance, when Δ = 0 and
λ_{RT}
= 1, the access ratios with the GAbased algorithm, with the algorithm in
[1]
, and with the greedy algorithm are 62.88%, 54.64%, and 45.99%, respectively. On average, the access ratio with the GAbased algorithm is 12.88% higher than that with the algorithm in
[1]
and 30.36% higher than that with the greedy algorithm, if considering Δ = 0.
Mean access ratio of RT flows vs. λ_{RT}
Fig. 11
shows the simulation results of the mean throughput of NRT traffic when the traffic load of RT flows changes. In general, the throughput of NRT flows with each of the three algorithms decreases as
λ_{RT}
increases, because more resources are used by RT flows. To boost the throughput of NRT traffic, one can increase Δ when allocating resource to RT traffic, as it reserves more resources for NRT traffic. Noticeably, the throughput with the GAbased algorithm decreases more dramatically than the other algorithms when
λ_{RT}
increases. The reason may stem from the fact that due to the superiority of the genetic algorithm, when allocating resources to RT traffic, the newly proposed GAbased algorithm is able to use up more network resources to admit more RT flows and leaves less network resources for NRT traffic. Therefore, the throughput degradation for NRT traffic can be much more obvious in the GAbased algorithm. Further, as compared to
Fig. 5
, similar observation on the running time of the three algorithms has been made when simulating the impact of traffic load.
Mean throughput of NRT flows vs. λ_{RT}
It is worth mentioning that the proposed GAbased algorithm improves the network performance but at the cost of time complexity, which is one of the drawbacks of genetic algorithms
[11
,
12
,
23]
. To further improve the feasibility of both GART and GANRT, similar to
[19]
, we can adopt the strategy that combines a GAbased algorithm and a lowcomplexity algorithm (e.g., the one in
[1]
), via independently obtaining the resource allocation solutions using both algorithms and then simply choosing the better one out of the two solutions. Another strategy is using the solution of the lowcomplexity algorithm as an initial chromosome of the GAbased algorithm. Obviously, with either strategy, if we reduce the generation number of the GAbased algorithm, the timecomplexity of the algorithm can be reduced; yet, due to the comparison mechanism or elitism strategy used in the GAbased algorithm, we can guarantee that the final solution is at least not worse than the one of the lowcomplexity algorithm. In other words, feasibility of the proposed GAbased algorithm can be improved if combined with other lowcomplexity algorithms, but at the cost of a certain extent of performance.
7. Conclusion
To have an indepth understanding of the performance of a CMN with heterogeneous services as well as to explore the feasibility of any new approach to solve complex resource allocation problems in such a network, we have designed a new algorithm based on genetic algorithm to address the resource allocation problems studied in
[1]
, which are MINLP. The newly designed GAbased algorithm can be treated as the optimal solution, because genetic algorithm is usually a robust search method requiring little information to search effectively in a large or poorlyunderstood search space. Novel initialization, selection, crossover, and mutation operations are designed such that solutions with enough randomness can be generated and converge with as less number of attempts as possible, improving the efficiency of the algorithm effectively. The algorithm designed in this paper can provide a comprehensive example of designing GAbased algorithm for many other application scenarios where similar complex wireless resource allocation problems are formulated. Simulation results show the superiority of the newly proposed GAbased algorithm, in increasing both the access ratio of RT flows and the throughput of NRT flows. However, it has also been found that in a CMN with both the RT and NRT traffic, due to the high priority of RT flows, the GAbased algorithm tends to fully utilize network resources to serve as many RT flows as possible, leaving fewer resources to NRT flows. Further, simulation results also reveal that as compared with algorithm in
[1]
it is also important to balance the tradeoff among QoS provisioning for RT traffic, throughput maximization for NRT traffic, and time complexity of a resource allocation algorithm. For the future work, we will optimize the design of the proposed GAbased algorithm to further reduce its time complexity.
BIO
Hangguan Shan received the B.Sc. degree in electrical engineering from Zhejiang University, Hangzhou, China, in 2004 and the Ph.D. degree in electrical engineering from Fudan University, Shanghai, China, in 2009.
From 2009 to 2010, he was a Postdoctoral Research Fellow with the University of Waterloo, Waterloo, ON, Canada. In February 2011, he joined the College of Information Science and Electronic Engineering, Zhejiang University, Hangzhou, China, as an Assistant Professor.
His research focuses on crosslayer protocol design, resource allocation, and QoS provisioning in wireless networks.
Dr. Shan was a corecipient of the Best Industry Paper Award from the IEEE Wireless Communications and Networking Conference (WCNC) 2011, Quintana Roo, Mexico.
Ziyun Ye received the B.Sc. degree in information and communication engineering from Zhejiang University, Hangzhou, China, in 2015. He is pursuing the M.Sc. degree in electrical engineering from University of California, Los Angeles, Los Angeles, U.S. His research interests include wireless networks, cognitive radio networks, cooperative networks, resource management, and heterogeneous networks.
Yuanguo Bi received the B.Sc. degree in Liaoning University, Shenyang, China in 2003 and the M.Sc. and Ph.D. degrees in Northeastern University, Shenyang, China in 2006, both in computer science. From 2007 to 2009, he was a visiting PhD student at the Department of Electrical and Computer Engineering, University of Waterloo, Canada. He is an Associate Professor at the College of Information Science and Engineering, Northeastern University, China. His current research interests include medium access control, QoS routing, multihop broadcast, and transmission control in vehicular networks.
Aiping Huang graduated from Nanjing Institute of Post and Telecommunications, China in 1977, received the M.Sc. degree from Nanjing Institute of Technology (current name: Southeast University), China in 1982, and received Licentiate of Tech. degree from Helsinki University of Technology (HUT), Finland in 1997. She worked from 1977 to 1980 as an engineer at Design and Research Institute of Post and Telecom. Ministry, China. From 1982 to 1994, she was with Zhejiang University (ZJU), China as an Assistant Professor and then Associate Professor in the Dept. of Scientific Instrumentation. She was a Visiting Scholar and then a Research Scientist at HUT (current name: Aalto University) from 1994 to 1998. From 1998, she is a full professor in the College of Information and Electronics Engineering at ZJU. She serves as the vice chair of IEEE ComSoc Nanjing Chapter. She published a book and more than 160 papers in refereed journals and conferences on communications and networks, signal processing. Her current research interests include heterogeneous networks, performance analysis and crosslayer design, planning and optimization of cellular mobile communication networks.
Zhou N.
,
Shan H.
,
Huang A.
,
Wang X.
“Resource management for heterogeneous services in cognitive mesh networks, ”
in Proc. of IEEE WCSP’13
Hangzhou, China
2013
Liang Y.C.
,
Chen K.C.
,
Li G. Y.
,
Mahonen P.
2011
“Cognitive radio networking and communi cations: An overview,”
IEEE Trans. Veh. Technol.
60
(7)
3386 
3407
DOI : 10.1109/TVT.2011.2158673
Chen T.
,
Zhang H.
,
Matinmikko M.
,
Katz M. D.
“CogMesh: Cognitive wireless mesh networks,”
in Proc. of IEEE GLOBECOM workshops
2008
Gunawardena S.
,
Zhuang W.
2011
“Capacity analysis and call admission Control in distributed cognitive radio networks,”
IEEE Trans. Wireless Comm.
10
(9)
3110 
3120
DOI : 10.1109/TWC.2011.072011.110406
Hou Y. T.
,
Shi Y.
,
Sherali H. D.
2008
“Spectrum sharing for multihop networking with cognitive radios,”
IEEE J. Sel. Area. Comm.
26
(1)
146 
155
DOI : 10.1109/JSAC.2008.080113
Shi Y.
,
Hou Y. T.
,
Zhou H.
2009
“Pernode based optimal power control for multihop cognitive radio networks,”
IEEE Trans. Wireless Comm.
8
(10)
5290 
5299
DOI : 10.1109/TWC.2009.081702
Shi Y.
,
Hou Y. T.
,
Kompella S.
,
Sherali H. D.
2011
“Maximizing capacity in multihop cognitive radio networks under the SINR model,”
IEEE Trans. Mobile Computing
10
(7)
954 
967
DOI : 10.1109/TMC.2010.204
Alshamrani A.
,
Shen X.
,
Xie L.L.
2011
“QoS provisioning for heterogeneous services in cooperative cognitive radio networks,”
IEEE J. Sel. Area. Comm.
29
(4)
819 
830
DOI : 10.1109/JSAC.2011.110413
Wang S.
,
Zhou Z.H.
,
Ge M.
,
Wang C.
2013
“Resource allocation for heterogeneous cognitive radio networks with imperfect spectrum sensing,”
IEEE J. Sel. Area. Comm.
31
(3)
464 
475
DOI : 10.1109/JSAC.2013.130312
Xie R.
,
Yu F. R.
,
Ji H.
2012
“Dynamic resource allocation for heterogeneous services in cognitive radio networks with imperfect channel sensing,”
IEEE Trans. Veh. Technol.
61
(2)
770 
780
DOI : 10.1109/TVT.2011.2181966
Davis L.
1991
Handbook of Genetic Algorithms.
Van Nostrand Reinhold
Holland J. H.
1975
Adaptation Natural and Artificial Systems.
The MIT Press
Lorenzo B.
,
Glisic S.
2013
“Optimal routing and traffic scheduling for multihop cellular networks using Genetic Algorithm,”
IEEE Trans. Mobile Computing
12
(11)
2274 
2288
DOI : 10.1109/TMC.2012.204
Tseng P.K.
,
Chung W.H.
,
Hsiu P.C.
“Minimum interference topology construction for robust multihop cognitive radio networks,”
in Proc. of IEEE WCNC’13
2013
101 
105
Jin Y.
,
Jin J.
,
Gluhak A.
,
Moessner K.
,
Palaniswami M.
2012
“An intelligent task allocation scheme for multihop wireless networks,”
IEEE Trans. Parallel and Distributed Systems
23
(3)
444 
451
DOI : 10.1109/TPDS.2011.172
Chu S.
,
Wei P.
,
Zhong X.
,
Wang X.
,
Zhou Y.
2013
“Deployment of a connected reinforced backbone network with a limited number of backbone nodes,”
IEEE Trans. Mobile Computing
12
(6)
1188 
1200
DOI : 10.1109/TMC.2012.88
Chatterjee M.
,
Lin H.
,
Das S. K.
2007
“Rate allocation and admission control for differentiated services in CDMA data networks,”
IEEE Trans. Mobile Computing
6
(2)
179 
191
DOI : 10.1109/TMC.2007.29
Sharma N.
,
Badheka D.
,
Anpalagan A.
2014
“Multiobjective subchannel and power allocation in interferencelimited twotier OFDMA femtocell networks,”
IEEE Systems Journal
(99)
1 
12
Cheng H. T.
,
Zhuang W.
2009
“Novel packetlevel resource allocation with effective QoS provisioning for wireless mesh networks,”
IEEE Trans. Wireless Communications
8
(2)
694 
700
DOI : 10.1109/TWC.2009.080739
Garey M. R.
,
Johnson D. S.
1979
Computers and intractability: A guide to the theory of NPcompleteness
Goldberg D. E.
1989
Genetic Algorithms in Search, Optimization and Machine Learning
Wu Q.
,
Zheng Z.
,
Deng W.
2009
Operations Research and Optimization with MATLAB Programming
Haupt R. L.
,
Haupt S. E.
2004
Practical Genetic Algorithms
Cheng H. T.
,
Zhuang W.
2008
“Joint powerfrequencytime resource allocation in clustered wireless mesh networks,”
IEEE Network
22
(1)
45 
51
DOI : 10.1109/MNET.2008.4435902