# ACO-Based Routing Algorithm for Cognitive Radio Networks

Authors: Peng Huang; Feng Lin; Jiliu Zhou
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Cognitive Radio Networks (CRNs) are an outstanding solution to improve efficiency of spectrum usage. Secondary users in cognitive networks may select from a set of available channels to use provided that the occupancy does not affect the prioritized licensed users. However, CRNs produce unique routing challenges due to the high fluctuation in the available spectrum as well as diverse quality-of-service (QoS) requirements. In CRNs, distributed multihop architecture and time varying spectrum availability are some of the key factors in design of routing algorithms. In this paper, we develop an ant-colony-optimization- (ACO-) based on-demand cognitive routing algorithm (ACO-OCR), jointly consider path and spectrum scheduling, and take advantage of the availability of multiple channels, to improve the delivery latency and packet loss rate. Then, an analytical framework based on M/G/1 queuing theory is introduced to illustrate the relay node queuing model. The performances of ACO-OCR have been evaluated by means of numerical simulations, and the experimental results confirm its effectiveness. Simulation results show that ACO-OCR outperforms other routing approaches in end-to-end path latency and package loss rate.


---

## Body

## 1. Introduction

According to a report by FCC in 2002, average utilization of many spectrum bands allocated through static assignment polices varies between 15% and 85% [1]. In order to improve the utilization efficiency of existing radio spectrum, so-called Cognitive Radio (CR) has emerged as a technique which allows unlicensed secondary users (SUs) to access the licensed spectrum when no licensed primary users (PUs) appear on the frequency band. Primary users use traditional wireless communication system with static spectrum allocation while secondary users use CRs to complete communication through spectrum opportunities without interfering with Pus activities. With CRs, the efficiency in spectrum utilization will be improved significantly [2].In realizing Cognitive Radio Networks (CRNs), both occupied spectrum and participating nodes of an abstract wireless link are opportunistically determined by their instantaneous availabilities. To fully explore the potentials of CRNs, it is important to study routing in dynamic spectrum access system while considering the unique properties of cognitive environment. Routing in cognitive radio networks shows characteristics different from traditional network and there are important differences in research methods. Due to characteristics of dynamic spectrum access, CR nodes channel changes with time and space. The quick changing channels and PUs interferences will lead to route instability. Therefore, most existing routing algorithms could not work well in CRNs. In this paper, we focus on the local spectrum knowledge scenario of multihop CRNs. We propose a framework of spectrum aware on-demand routing based on ant colony optimization, which could find the globe optimal path with minimum end-to-end delay and max delivery rate. The main contributions of this paper are listed as follows.(1)
A distributed, on-demand, optimal dynamic multihop routing algorithm for CRNs, named ACO-OCR, is proposed by introducing improved ACO in routing determination.(2)
A preemptive resume priority (PRP) M/G/1 queuing network model to characterize the spectrum usage behaviors between primary and secondary users in CR networks is proposed.(3)
A series of experimentations are conducted to validate the performance of the proposed algorithm. The results have demonstrated that ACO-OCRs have better performance in end-to-end path latency and average package loss rate when compared with JSORP and CAODV.The rest of the paper is organized as follows. Section2 describes the related works of distributed routing algorithms of CRNs, and Section 3 presents the design of ACO-OCR. In Section 4 we give the node queuing analysis. In Section 5, we present out simulation results, while Section 6 concludes the paper.


## 2. Related Works

One of the main differences between ad hoc networks and traditional CRNs is frequency distribution, which is static in traditional ad hoc networks but dynamic in CRNs. The frequency distribution in CRNs varies with the PUs working condition. Routing algorithms for CRNs should utilize the flexibility of CRs and deal with the critical challenges that do not exist in the traditional ad hoc networks. Generally, there are two main kinds of routing scenario in CRNs: the CR nodes with full spectrum knowledge and with local spectrum knowledge. In the former case, all the CR nodes have a spectrum occupancy map of the CRNs, or there is a central control entity, which could indicate over time and space the channel availabilities [3]. On the other hand, CR nodes with local knowledge are that nodes locally construct spectrum availability information.Under local spectrum knowledge scenario, Cheng et al. [4, 5] propose an approach based on local spectrum knowledge and integrating consideration of the switching delay and back off delay along the path. With full consideration of all possible delays during a multihop transmission through Cognitive Radio Network, the authors develop metrics and mechanism of spectrum assignment. Cheng’s approach has a good performance and many algorithms compare with it. Yang et al. [6] analyze and model per node delay and the path delay in multihop Cognitive Radio Network. Then, they propose a framework of local coordination based routing and spectrum assignment, which consists of one protocol for routing path and one scheme for neighborhood region. In brief, the proposals [4–6] are “greedy-like” approaches and have the potential of ending up in a bad locally optimal solution. The Spectrum Aware Mesh Routing (SAMER) proposal [7] opportunistically routes traffic across paths with higher spectrum availability and quality via a new routing metric. It balances between long-term route stability and short-term opportunistic performance. However, this algorithm assumes that nodes are able to communicate with each other with several possible disjoint channels at the same time. In addition, this routing algorithm works based on link state routing, which requires time to converge and create a network topology map. Thus, this approach may not be suitable to CRNs. Shiang and van der Schaar [8] propose a distributed resource-management algorithm that allows network nodes to exchange information and that explicitly considers the delays and cost of exchanging the network information over multihop cognitive radio networks. In this algorithm, spectrum sensing plays an essential role in all SUs. If the detection is highly unreliable, the collisions between the SUs and PUs may happen more frequently. As a result, the overall spectral efficiency cannot be improved. Han et al. [9] present provably good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in Software-Defined Radio (SDR) wireless networks. Unfortunately, this algorithm can only achieve a fraction of the maximum achievable throughput in the worst case.Cacciapuoti et al. [10] propose CAODV which avoids regions of PU activity during both route formation and packet discovery without requiring any dedicated control channel. However, CAODV broadcast route requests messages to all available channels which increase the protocol overhead and route discovery time. In [11], by introducing preservation regions around primary receivers, a modified multihop routing protocol is proposed for the cognitive users. Under this protocol, there are possibly some SUs that can never be served. Thus, to design more robust and scalable routing algorithm for CRN and take into account the efficiency of optimization, we propose a more dynamic and more practical ACO-based routing algorithm for CRNs.


## 3. Routing Algorithm (ACO-OCR)

Some assumptions of ACO-OCR are as follows. First, a common channel [12] which enables CR nodes to transmission control packets is used. Meanwhile, CR nodes can adjust the working frequency band to transmit data. Second, each node should maintain lists of locally available channels that are not occupied by primary users. Thus, each node can individually detect its spectrum opportunity (SOP) [13], which is a set of frequency bands currently unoccupied and available. Third, in our mechanism, there are two kinds of ants: forward ants and backward ants. The forward ant executes path search function and the backward ant establishes the pheromone table.The route establishment is listed as follows.(1)
When the source node has data to transmit, route discovery process starts. The source node sends forward ant which uses ACO mechanism to choose the next node through common control channel. Because CR nodes have multichannel, traditional ant optimization formula should be adapted. When forward ants arrived in nodei, the probabilities of selection of next node and channel are calculated in formula (1) or (2) as follows:
(1)s={argmaxj∈allowedk{[τijlα(t)·ηijlβ(t)]},ifq≤q0,S,otherwise,(2)S={τijlα(t)·ηijlβ(t)∑s∈allowedkτisα(t)·ηisβ(t),j∈allowedk,0,otherwise,whereq is a random number generated by forward ant obeying uniform distribution in [0,1]. q0 is a predefined threshold parameter (0≤q0≤1). If q≤q0, the ants use prior knowledge to choose next node and channel. τijl(t) is pheromone concentration parameter of node i to node j through channel l. ηijl(t) is the “heuristic visibility” and is defined as follows:
(3)ηijl(t)=K1tsi+K2tqj,wheretsi represents the channel switch delay of node i. tqj is queuing delay of node j. K1, K2 are the weight coefficients of parameters tsi and tqj, respectively, and K1+K2=1.(2)
When forward ants arrived at destination node, the backward ants are generated. The backward ants return the source node and update the local pheromone concentration. The local pheromone concentration is updated using(4)τijl(t+Δt)=(1-ρ)·τijl(t)+ρ·Δτijl(t,t+Δt),whereρ is coefficient of pheromone evaporation and 0<ρ<1.(3)
Once all the backward ants back to the source node, a simple local search scheme is applied. The scheme has potential to further reduce the path delay and accelerate convergence of ACO algorithm. Assume the path which a forward ant has established as a vertex setv={v1,v2,…,vi}. The procedure of the local search for ant k’s path, we call the first path, in the ACO-OCR is described as follows.Step 1. Choose another ant j’s path, we call the second path, which has less path latency.Step 2. For each path vertex of the first path, try to find same vertex in path vertex of the second path.Step 3. If two paths have same vertex, two paths are broken into two segments: the beginning part which contains the same vertex and the remaining part of the path. Then, the first path is obtained by combining the beginning part of the first path with the ending part of the second selected tour. At the same time, the second new path can be obtained by inversing the previous operation. All the same vertex should be tested.Step 4. Compute the path latency, if the latency is shorter or the path has fewer vertex. The new path is accepted.(4)
The global update rule is implemented to the global optimized path. The global update of pheromone concentration is implemented using(5)τ(r,s)=(1-α)·τ(r,s)+α·Δτ(r,s),Δτ(r,s)={(Lgb)-1,if(r,s)∈globaloptimizedpath,0,otherwise,whereα presents the evaporation coefficient of pheromone and 0<α<1. Lgb is the global optimized path up to now.(5)
If the route is selected, another kind of global update is made; the pheromone concentration in node is cleared.


## 4. Performance Analysis

In this section, we present the queuing analytical mode of a cognitive relay node. We assume that connections have same priority and follow the first-come-first-served (FCFS) scheduling principle. Each of the nodes has an infinite buffer for storing fixed-length packets.Assume that there are parallel channels (indexed from 0 ton) available for transmissions by primary and secondary users and that primary users can access these channels at any time according to a certain protocol and a secondary sense the spectrum and tries to access available frequency bands. For ease of analysis, let {N(t),t≥0} denote the neighbor node forward data rate process, which follows Poisson distribution with parameter λf. If there is no route to destination, the data flow packets will be dropped; otherwise the packets will be sent to next node (Figure 1).Figure 1
Node buffer queue.We assume that the duration of one data flowtdd follows negative exponential distribution with parameter λdd and mean μdd-1, where λdd=μdd-1, and assume that the time for searching forward tcs follows negative exponential distribution with parameter λcs and mean μcs-1, where λcs=μcs-1. Let 1/μdd=E[Tdd] and 1/μcs=E[Tcs]. Y denotes the time of a dataflow being looking for forwarding opportunity. Obviously, Y=tdd+tcs. The distribution, distribution density function and expectation of Y are shown in (6), (7), and (8), respectively:
(6)F(y)=1-(λddλdd-λcs·e-yλcs-λcsλdd-λcs·e-yλdd),(7)f(y)=λddλcs(e-yλddλcs-λdd+e-yλcsλdd-λcs),(8)E(y)=λddλcs(λcs-λdd)+λcsλdd(λcs-λdd),(9)E(y2)=2λcsλdd(λcs-λdd)+2λddλcs(λdd-λcs).So, the model becomes an M/G/1 queuing network model. LetTn′(n≥1) denote ending of the nth data flow service. Define Qn=QTn′(n≥1) as the dataflow remaining in the system after the nth dataflow leaves the node and An as the arrived dataflow number in nth dataflow forward time; for n>0, we have
(10)Qn+1={Qn-ε(Qn)+An+1(Qn≥1)An+1(Qn=0).LetL denote the expectation of packet number, L=E(Qn). From (9), when Qn≥1, we can get
(11)E(Qn+1)=E(Qn)-E[ε(Qn)]+E(An+1).
Let E(Q)=limn→∞E(Qn), and then limn→∞E(Qn+1)=limn→∞E(Qn), and we have
(12)E(An+1)=∫0∞E[N(t)]dF(t)=∫0∞λftdF(t)=ρ.
In (11), let n→∞, and we can get
(13)1-limn→∞P{Qn=0}=ρ.Taking mathematical expectation on both sides after square of (13), we can establish
(14)E(Q2)=E(Q2)+E[ε(Q)]+E(A2)-2E(Q)-2E(A)E[ε(Q)]+2E(Q)E(A).From (14), we can get
(15)E(Q)=E[(A2)-2ρ2+ρ]2-2ρ,
where
(16)E[(A2)]=E[N2(F)]=∫0∞E[N2(F)∣F=y]dF(y)=λ2E(y2)+λE(y).
Furthermore, taking (16) to (15), we can get the expectation of average packet number E(Q)(17)E(Q)=ρ+λf2E[y2]2(1-ρ).According to Little formula, average lingering timeW is
(18)W=Lλf=1E(y)+λfE[y2]2(1-ρ).Similarly, we can get average queue sizeLq and average waiting time Wq as follows:
(19)Lq=L-ρ=λf2E[y2]2(1-ρ),(20)Wq=Lqλf=λfE[y2]2(1-ρ).


## 5. Simulations and Results

In this section, we evaluate the effectiveness of ACO-OCR to improve the end-to-end delay and packet loss rate. We build our simulation model with C++ language. In 200 × 200 square, we randomly deploy 30 CR nodes which have communication radius of 30. The dataflow consists of several packets and each packet has 1024 bytes. The expectation of numbers of packets in dataflow is 100.We change the numbers of frequency band and channel avail rate and then conduct the simulation. The numbers of each CR node of frequency bands varies from 2 to 8. The available rate of each band varies from 0.1 to 0.9. Then, we compared our algorithm with CAODV [10] and JSORP [4]. From Figures 2, 3, 4, 5, 6, 7, 8, and 9, we can see that with increase of channel available rate, the delay becomes longer and the average packet loss rate becomes lower. When the channel available rate is low, the performances of the three algorithms are almost the same. The reason is that there is not much chance to send the packet. When the channel available rate is bigger than 0.6, the ACO-OCR has better performance than CAODV and JSORP. That is because when the channel available rate is larger, the nodes have more opportunities to send data, so the packet loss rate is decreased and with more packet to send, the delay is increased. In Figures 10, 11, 12, and 13, we set packet loss rate to 0.1 and increase the channel number from 2 to 8; the same result is derived. In Figures 14 and 15, when the channel available rate is high, the average delay and packet loss rate have slight changes. That is because under the high channel available rate, the algorithm already finds the best route, and the increasing of channel number could have little effect on routing. Due to consideration of queuing delay of node buffer, the performances of JSORP and ACO-OCR are better than CAODV. Because routing metrics of ACO-OCR employ weighted approach, when the path to the destination is long, it is more likely to choose a better relay node. Thus, the global delay is lower.Figure 2
Average delay when channel number = 2.Figure 3
Average packet loss rate when channel number = 2.Figure 4
Average delay when channel number = 3.Figure 5
Average packet loss rate when channel number = 3.Figure 6
Average delay when channel number = 4.Figure 7
Average packet loss rate when channel number = 4.Figure 8
Average delay when channel number = 5.Figure 9
Average packet loss rate when channel number = 5.Figure 10
Average delay when channel available rate = 0.1.Figure 11
Average packet loss rate when channel available rate = 0.1.Figure 12
Average delay when channel available rate = 0.5.Figure 13
Average packet loss rate when channel available rate = 0.5.Figure 14
Average delay when channel available rate = 0.9.Figure 15
Average packet loss rate when channel available rate = 0.9.


## 6. Conclusion

Routing is one of the important problems in cognitive radio. In this paper, we propose an ACO-based on-demand routing algorithm to tackle this problem. With the framework of ACO, we implement several operations so as to make ACO capable of routing and channel assignment in multihop cognitive radio networks. Our approach jointly considers the path and channel decisions and thus the end-to-end path latency is minimized. Then, we derive the queuing delay and average queuing length of a cognitive relay node. We validate the effectiveness of the algorithm by thorough simulation and find that our approach provides better performance than JSOR and CAODV in both spectrum distribution varying and channel availability varying environment. This suggests that ACO may be more suitable to solve similar problems than other computing techniques. In the future, we will develop tailor-made operators for ACO to get even better performance and also compare our algorithm with a broader class of algorithms.



---

*Source: 264504-2013-06-27.xml*