# Backup Routing Algorithm Based on Delay Constraint in Cognitive Radio Sensor Networks

Authors: Zhenguo Wu; Xiaozhu Liu; Yan Zhang; Hooman Samani; Rongbo Zhu
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

In cognitive radio sensor networks (CRSNs), the frequency used by second users will be terminated unexpectedly as the preemption of primary user or reinitialized route discovery process in data transmission process, which will lead to unreliable communication and degrade the network performance greatly. In this paper, an efficient backup routing algorithm is proposed for reliable routing based on the uncorrelated degree and delay constraint in CRSNs. Numerical and simulation results show that the proposed algorithm can effectively overcome the intermittent connection problem and decrease delay greatly.


---

## Body

## 1. Introduction

With the rapid development of wireless communication technology, the contradiction between limited spectrum resources and the demand of growing applications became more and more prominent [1]. As one of promising technique to improve spectrum resource utilization, cognitive radio (CR) [2–4] is able to change the transmitter parameters based on its interactive work environment. From the perspective of signal processing, CR is an intelligent wireless communication system, which can sense the external environment and learn from the environment using artificial intelligence techniques, by changing operating parameters in real time (e.g., transmission power and carrier frequency and modulation techniques). And this makes the internal state to adapt to the change of the received radio signal statistics to achieve highly reliable communication at any time in any place and makes use of spectrum resources effectively.Recently a variety of techniques are developing to promote the development of CR in different application scenarios [5–8], such as wireless local area network (WLAN) based air interface standards (IEEE 802.22), IEEE 802.16, and cognitive radio sensor networks (CRSNs) [9–11]. CRSNs are the potential next generation wireless sensor networks (WSNs), which can mitigate overcrowded unlicensed spectrum bands by opportunistically using temporally unoccupied unlicensed and licensed spectrum bands [12–14]. The notable features of CRSN are flexible, intelligent, and reconfigurable [15–18]. Based on internal state statistical variations of the received radio signal [11, 19], nodes will sense the external environment and use artificial intelligence to learn from the environment, to adjust some system parameters timely to achieve highly reliable communication and efficient use of heterogeneous network environment of limited radio spectrum resources [20–25]. CRSNs also can solve spectrum resources scarcity and a variety of heterogeneous network coexistence issues [26, 27], which use cognitive sensors to improve system performance without interference and reduce the total energy consumption.Routing is an important issue in CRSNs [28, 29]. Recent work on CR routing protocol mainly focuses on reducing the data transmission delay and packet loss ratio and improves throughput. Although there are many effective routing schemes in CRSNs [17, 24], the existing schemes mostly focus on energy constraint and do not consider the reliability. Another issue is the effective intelligent cognitive routing that will be considered to provide better routing discovery and recovery in CRSNs.In this paper, an efficient reliable backup routing algorithm based on the unrelated degree and delay constraint (BUD) is proposed, which overcomes the intermittent connection problems and decrease delay greatly. The main idea of the proposed scheme is providing not only efficient fault tolerance scheme, but also fast recovery mechanism when channel of second user is deprived. In order to meet this requirement, the proposed algorithm will find the smallest delay route as the primary route and then calculate a suboptimal route as a backup route according to the unrelated degree and delay in all candidate routes. When the primary route fails, the proposed scheme can use the backup route to transmit data effectively. Numerical analysis and detailed simulation results show that the proposed algorithm can overcome the intermittent connection problem and decrease delay greatly.


## 2. Related Work

Routing algorithm in cognitive radio networks focuses on three aspects: active routing, cross-layer routing, and network performance metric. Spectrum aware on-demand routing protocol (SORP) [30] based on multi-hop spectrum aware on-demand routing cross-layer joint strategy proposed a scheduling scheme based on active frequency collection of polling cross-node multiband multistream. DORP [31] protocol is based on delay metric on-demand routing protocol, which uses joint interaction strategies and spectrum scheduling. DORP employed the analysis model NAM to describe polling-based scheduling channel allocation process, which can reduce interference between data streams and spectrum switching delay. MSCRP protocol [32] is based on a single transceiver multi-hop CRN spectrum sensing on-demand routing protocol. Each node has only one CR transceiver which is the main characteristic, and a routing protocol packet exchange mechanism is also proposed in MSCRP.Cognitive networking with opportunistic routing protocol for CRSNs is proposed in [10], which improves the network performance after increasing network scalability based on an accurate channel model to evaluate the signal strength in different areas of a complex indoor environment. An energy- and cognitive-radio-aware routing protocol (ECR) was proposed in [11], which performs joint node-channel assignment by taking energy into consideration, is aware of cognitive radio at the network layer, and can seize spectrum opportunity in other spectrum bands.In active routing based on table-driven approach, nodes need to maintain the whole routing table, which does not has response delay, while leads to heavy overhead. The stability CR routing protocol SRP [33] has higher stability and less signaling overhead, which can achieve less end-to-end delay and higher throughput than the existing methods. The difference between on-demand routing and active routing is that on-demand routing is only created by the source node. Therefore, the routing table is updated on-demand. Generally, on-demand routing includes three phases: route discovery, route maintenance, and routing release. The on-demand routing protocol [30, 32] can reduce interference between data flows and spectrum switching delay, and it has low packet loss rate and can reduce the primary user interference. However, it will lead to high overhead in route establishment and maintenance [34–36].In order to achieve better performance, cross-layer design considers both routing and spectrum selection [9, 37, 38], which can improve system performance greatly [33, 39, 40]. However, cross-layer design will inevitably degrade system versatility and portability, and it is not conducive to the routing updating and maintenance. And cross-layer considerations for implementing viable CRSN routing solutions also were explored in [19]. Additionally, a detailed performance evaluation of routing strategies in a cognitive radio environment is performed to expose research gaps.With considering different metric, the routing protocol can meet the quality of service, optimize network resource, reduce packet loss, and improve network throughput. However, the routing maintenance caused by spectrum change is not considered comprehensively. A high-throughput channel allocation routing protocol was proposed [14], which can achieve robustness; efficient, low computational complexity; and low protocol complexity. However, it will lead to high overhead in route establishment and maintenance.A spectrum-aware cluster-based energy-efficient multimedia (SCEEM) routing protocol for CRSNs was proposed [9], which jointly overcomes the formidable limitations of energy and spectrum to support the quality of service and energy-efficient routing by limiting the participating nodes in route establishment. Data collection and dissemination framework was proposed in [12], which can fully utilize wireless resources while maintaining a reliably connected and efficient topology for each channel. In the proposed framework, each sensor node selects a channel considering the primary user (PU) channel utilization and network connectivity. Cognitive information-centric sensor networks (CICSNs) were explored in [13], in which sensory information is identified using attribute-value pairs, and elements of cognition are used to deliver data to the sink with user-desired quality of information. Latency and reliability are identified as attributes that impact the quality of information (QoI) perceived by the end user.In CRSNs, the routing design will improve the resource utilization while considering cognitive capacity of nodes. Considering the resource-constrained node characteristics, energy optimization strategy also should be considered in routing protocol. The adaptive reliable and scalable, robust routing protocol will also be considered in dynamic topology.


## 3. Routing Algorithm Design

The backup routing algorithm (BUD) and route metrics are proposed for reliable routing based on the unrelated degree and delay constraint, which includes two parts: route discovery and route maintenance. Notation Description list shows the notations in the proposed routing algorithm.


### 3.1. Unrelated Degree

The optimized alternative route known as the backup routeb
r is selected from all candidate routes c
r. Considering the impact on data transmission and network topology, in order to select backup route efficiently, the unrelated degree ∂ is considered to save power for sensor nodes.In the proposed scheme, each cognitive nodev
i maintains not only a regular route r
b, but also a backup route b
r
b, and cognitive node v
i can be expressed as(1)
v
i
∣
r
b
,
b
r
b
.When a data transmission session is established between source nodes
(
v
i
) and destination node d
(
v
i
), s
(
v
i
) will store the data transmitted by the primary route p
r
t
d and the data of backup route which can reach the same destination node b
r
d. It can be expressed as(2)
b
r
b
∣
p
r
t
d
,
b
r
d
,and the number of backup route b
r considers both the density of nodes and the amount of packets to be transmitted.In addition to the source nodes
(
v
i
) and the destination node d
(
v
j
) in the primary route p
r, all nodes in the candidate route c
r and each node of the primary route p
r will be considered. If a node is included in the primary route p
r, the node is a contained node; otherwise it is a noncontained node.Unrelated degree∂ is defined as the ratio of the number of contained nodes n and all nodes N (exclude the source node s
(
v
i
) and the destination node d
(
v
j
)) in the candidate route c
r; namely,(3)
∂
=
n
N
0
≤
∂
≤
1
,if ∂
=
0, which indicates that two routes are unrelated completely; otherwise, they are related. When unrelated degree ∂ is high, there are a lot of contained nodes and few uncontained nodes, and two routes will be very similar. The link of primary route p
r is disconnected when primary user of preemption or nodes failure and the probability of backup route also will be affected greatly. On the other hand, when unrelated degree is low, there are few contained nodes and a lot of uncontained nodes. The value of unrelated degree is very important to discover the optimal backup route b
r.


### 3.2. Delay Parameter

In the proposed scheme, when selecting a backup route,b
r, not only unrelated degrees ∂, but also delay is considered in the CRSNs. For most traffic in CRSNs, delay is a very important issue for sensing data and events in environment. The transceiver of cognitive nodes will lead to some delay when it switches between different channels. The switching delay is determined by the relative frequency band relationship between the two channels on the radio spectrum. For example, in the spectrum of 20 MHz~3 GHz, when the frequency band of the transceiver change is 10 MHz, the switching delay is 10 ms. Therefore, the channel switching delay within the node cannot be ignored [12, 13, 41].In CRSNs, the transmission delay of source nodes
(
v
i
) to the destination node d
(
v
j
) consists of the forwarding data transmission delay d
s
(
v
i
)
d
(
v
j
), forwarding data transmission delay between nodes d
t
d
e
l, and receiving data channel switching delay c
s
d
e
l:(4)
d
s
v
i
d
v
j
∣
d
t
d
e
l
,
c
s
d
e
l
.Transmission delay and spectrum handoff latency data transceiver of each forwarding node can be expressed as(5)
d
e
l
=
t
d
e
l
+
c
s
d
e
l
.The CRSN can be denoted by a directed graphG
(
V
,
E
), where V is the set of culminations to the diagram G. E represents CR links, that is, the set of edges directed graph G. The delay is set to the side length of directed graph, and then the delay d
e
l from source node s
(
v
i
) to the destination node d
(
v
j
) is the path weight w
i
j.Suppose there aren
p paths from the source node s
(
v
i
) to the destination node d
(
v
j
). Calculate the size of each path delay t
i
(
0
<
i
≤
n
p
) in ascending order. The minimum is the primary route p
r, and then calculate the value of the remaining paths with unrelated degree ∂. Because the backup route b
r satisfies both delay t
i and unrelated degree ∂ constraints, we can use weighted average of the two metrics as a basis for selecting a backup route b
r:(6)
β
=
a
t
i
+
1
-
a
∂
i
0
≤
a
≤
1
,where ∂
i represents the unrelated degrees and a is an adjustable parameter between t
i and ∂
i to achieve balance, while the value of a should be greater than 0.5 due to intermittent connectivity in CRNS.


### 3.3. Route Discovery

When the source nodes
(
v
i
) needs to send data to destination node d
(
v
j
), it sends network routing request message (RREQ), which is shown as(7)
R
R
E
Q
=
R
I
D
,
S
I
D
,
D
I
D
,
N
I
L
,
N
L
W
,where R
I
D indicates the route request identity, S
I
D indicates the address of the source node s
(
v
i
), D
I
D indicates the address of the destination node d
(
v
j
), N
I
L indicates the list of the intermediate nodes, and N
L
W indicates link weights between adjacent nodes. The intermediate message is as follows:(8)
m
v
i
∣
A
d
d
r
s
,
S
O
P
s
,
C
s
,where A
d
d
r
s denotes the address of intermediate node m
(
v
i
), S
O
P
s denotes spectrum opportunity set, and C
s denotes available channels. After the intermediate node received a non-duplicate RREQ, its address, spectrum opportunity set, and available channels will be added to the routing information list and then forwarded to the node of the next hop. When the destination node receives RREQ message, it will know the decision of the channel information of all links. Then, the proposed scheme will choose a route with the minimum delay as the primary route, p
r, and calculate a backup route b
r from all candidate routes according to expression (6). Then it sends the channel selection information routing reply message to the source node s
(
v
i
). Route response message is shown as(9)
R
R
E
P
=
P
T
,
R
I
D
,
D
I
D
,
R
R
,where P
T indicates the type of package, R
I
D denotes the neighbor node address of the RREP packet, D
I
D indicates the source node address of the route, R
R denotes route reply packet, and it consists of four parts:(10)
R
R
∣
N
L
,
C
C
,
W
C
,
L
W
,where N
L indicates the node sequence of source node s
(
v
i
) to destination node d
(
v
j
), C
C is the link assigned channel between cognitive nodes and the next cognitive node in N
L, W
C denotes all channels used by this cognitive node, and L
W is the weight of this link. When the source node s
(
v
i
) receives the RREP, it can send data according to the routing information.


### 3.4. Route Maintenance

The primary user preemption or node failure will lead to disconnected link. Quickly recover interrupted data transfer and effective rerouting become very important. In the proposed routing algorithm, when the source nodes
(
v
i
) failed to forward packets to the destination node d
(
v
j
), the link is disconnected or node failure. Then cognitive node will send a RSUS (Route Suspend) message and will notify the source node to suspend the current route request. If the disconnected link or node is not restored within the time t, it will send RERR (Route Error) to the source node. When the source node receives RERR message, if the backup route b
r is available, the source node will select the backup route b
r as the primary route p
r to transmit data packets; if the backup route b
r is unavailable, the source node s
(
v
i
) will initiate a new route discovery process.


### 3.5. Algorithm Design

The proposed algorithm BUD employs an improved depth first search (DFS) algorithm to find multiple paths in CRSNs. From the source node to the destination node, the DFS algorithm can only find one path. In order to find multiple suboptimized paths, when accessing a nodev
i, the proposed algorithm marks it as being accessed and set v
i
s
i
t
e
d
[
v
i
]
=
t
r
u
e until v
i is not the path to neighboring nodes and then set v
i
s
i
t
e
d
[
v
i
]
=
f
a
l
s
e. Hence the proposed algorithm can find all the paths from the source node s
(
v
i
) to the destination node d
(
v
j
).Considering the route selection criteria, the proposed algorithm BUD chooses a route with the minimum delay as the primary routep
r and then decides backup route b
r according to the delay parameter t
i and unrelated degree parameter ∂. The algorithm is described in detail as in Algorithm 1, and the flowchart is shown in Figure 1.Algorithm 1:The proposed routing algorithm.
Backup Routing Algorithm BUD
Input: Source node, destination node
Output: primary route, backup route
(1)visited
[
f
(
v
i
)
]
=
true; Push
(
&
S
,
f
(
v
i
)
);
(2)if  (
f
(
v
i
)
=
=
t
(
v
j
)
)
go to step 3,
else
go to step 4.
(3)vector
<
node
>
result
t
(
v
j
)
f
(
v
i
)
(
temp
,
sum
); node
x; x
.
path
=
temp
t
(
v
j
)
f
(
v
i
)
[
n
];
x
.
cos
⁡
t
=
sum
t
(
v
j
)
f
(
v
i
); result
t
(
v
j
)
f
(
v
i
)
(
temp
,
sum
)
.
push
_
back
(
x
);
go to step 8.
(4)f
o
r (i
n
t
k
=
0
;
k
<
nodenumber; ++k
)
(5)if  (
Graph
⁡
[
f
(
v
i
)
]
[
v
k
]
&
&
!
visited
[
v
k
]
)
go to step 6;
else
go to step 8.
(6)visited
[
v
k
]
=
true
;
Push
(
&
S
,
v
k
);
(7) DFS (G, v
k, t
(
v
j
)).
(8)visited
[
v
k
]
=
false
;
Pop
(
&
S
,
&
e
)
(9)if stack is empty
go to step 10;
else
find the next neighbor nodes of the top node in the stack;
go to step 5.
(10)if  (
result
t
v
j
f
v
i
(
temp
,
sum
)
[
i
]
.
cos
⁡
t
<
result
t
v
j
f
v
i
(
temp
,
sum
)
[
sum
min
⁡
]
.
cos
⁡
t
)
sum
min
⁡
=
i;
(11)c
r
β
i
=
α
*
result
t
v
j
f
v
i
(
temp
,
sum
)
[
i
]
.
cos
⁡
t
+
(
1
-
α
)
*
count
/
result
t
(
v
j
)
f
(
v
i
)
(
temp
,
sum
)
[
i
]
.
path
.
size
(
)
-
2;
if  (
c
r
β
i
<
b
r
β
)
b
r
β
=
c
r
β
i
;
c
r
min
⁡
=
i;
Select the route with smallestc
r
β
i value as backup route;
(12)return  p
r and c
r
β
i.Figure 1
The flowchart of the proposed algorithm BUD.The proposed algorithm works as follows.Step 1.
For the nodev
i, put it into the stack P
u
s
h
(
&
S
,
f
(
v
i
)
), and mark node v
i is accessing v
i
s
i
t
e
d
[
f
(
v
i
)
]
=
t
r
u
e.Step 2.
If the top node in the stack is the destination noded
(
v
j
), go to Step 3, or else go to Step 4.Step 3.
Store the sequence of nodes and the weights of this path inr
e
s
u
l
t
t
(
v
j
)
f
(
v
i
)
(
t
e
m
p
,
s
u
m
), then go to Step 8.Step 4.
Find the neighbor nodev
k of the top node.Step 5.
If the neighbor nodev
k is not visited, go to Step 6, or else go to Step 8.Step 6.
Setv
i
s
i
t
e
d
[
v
k
]
=
t
r
u
e and put node v
i into the stack.Step 7.
Consider DFS (G
,
v
k
,
t
(
v
i
)).Step 8.
Output current node from the stack and markv
k as v
i
s
i
t
e
d
[
v
k
]
=
f
a
l
s
e.Step 9.
If the stackS is empty, go to Step 10, or else find the next neighbor node v
k of the top node in the stack and then go to Step 5.Step 10.
Select the minimum weight path as the primary routep
r.Step 11.
Calculatec
r
β
i of all candidates route, and select the route with smallest c
r
β
i value as backup route.Step 12.
Output primary routep
r and backup route c
r
β
i.A general CRNS topology is shown in Figure2. The corresponding weighted adjacency matrix is shown in Figure 3.Figure 2
General CRSN topology.Figure 3
Weighted directed graphG.Weighted Adjacency Matrix. Consider(11)
0
w
a
b
w
a
c
0
w
a
e
0
0
0
0
0
0
w
b
f
0
0
0
w
c
d
0
0
0
0
0
0
0
w
d
f
0
0
0
w
e
d
0
w
e
f
0
0
0
0
0
0
.As shown in Figure2, v
i denotes cognitive sensor node and the weight w
i
j in directed edges denotes the delay of packet transmission from v
i to v
j, such as the weights from v
a to v
b are represented by w
a
b. From the topology shown in Figure 2, primary route p
r and backup route b
r can be discovered from the source node to the destination node according to the proposed route selection algorithm.For example, suppose thatv
a is the source node and v
f is destination node. In order to find the primary route p
r and backup route b
r from cognitive sensor nodes from v
a to v
f, the proposed algorithm finds all paths from v
a to v
f, and then the path of minimum weight will be the primary route p
r. And then calculate the value of β in each path according to (6) and choose the smallest value of the β as backup route b
r. All paths from v
a to v
f in this network topology are as follows: V
a
→
V
b
→
V
f, V
a
→
V
e
→
V
f, V
a
→
V
e
→
V
d
→
V
f, and V
a
→
V
c
→
V
d
→
V
f.


## 3.1. Unrelated Degree

The optimized alternative route known as the backup routeb
r is selected from all candidate routes c
r. Considering the impact on data transmission and network topology, in order to select backup route efficiently, the unrelated degree ∂ is considered to save power for sensor nodes.In the proposed scheme, each cognitive nodev
i maintains not only a regular route r
b, but also a backup route b
r
b, and cognitive node v
i can be expressed as(1)
v
i
∣
r
b
,
b
r
b
.When a data transmission session is established between source nodes
(
v
i
) and destination node d
(
v
i
), s
(
v
i
) will store the data transmitted by the primary route p
r
t
d and the data of backup route which can reach the same destination node b
r
d. It can be expressed as(2)
b
r
b
∣
p
r
t
d
,
b
r
d
,and the number of backup route b
r considers both the density of nodes and the amount of packets to be transmitted.In addition to the source nodes
(
v
i
) and the destination node d
(
v
j
) in the primary route p
r, all nodes in the candidate route c
r and each node of the primary route p
r will be considered. If a node is included in the primary route p
r, the node is a contained node; otherwise it is a noncontained node.Unrelated degree∂ is defined as the ratio of the number of contained nodes n and all nodes N (exclude the source node s
(
v
i
) and the destination node d
(
v
j
)) in the candidate route c
r; namely,(3)
∂
=
n
N
0
≤
∂
≤
1
,if ∂
=
0, which indicates that two routes are unrelated completely; otherwise, they are related. When unrelated degree ∂ is high, there are a lot of contained nodes and few uncontained nodes, and two routes will be very similar. The link of primary route p
r is disconnected when primary user of preemption or nodes failure and the probability of backup route also will be affected greatly. On the other hand, when unrelated degree is low, there are few contained nodes and a lot of uncontained nodes. The value of unrelated degree is very important to discover the optimal backup route b
r.


## 3.2. Delay Parameter

In the proposed scheme, when selecting a backup route,b
r, not only unrelated degrees ∂, but also delay is considered in the CRSNs. For most traffic in CRSNs, delay is a very important issue for sensing data and events in environment. The transceiver of cognitive nodes will lead to some delay when it switches between different channels. The switching delay is determined by the relative frequency band relationship between the two channels on the radio spectrum. For example, in the spectrum of 20 MHz~3 GHz, when the frequency band of the transceiver change is 10 MHz, the switching delay is 10 ms. Therefore, the channel switching delay within the node cannot be ignored [12, 13, 41].In CRSNs, the transmission delay of source nodes
(
v
i
) to the destination node d
(
v
j
) consists of the forwarding data transmission delay d
s
(
v
i
)
d
(
v
j
), forwarding data transmission delay between nodes d
t
d
e
l, and receiving data channel switching delay c
s
d
e
l:(4)
d
s
v
i
d
v
j
∣
d
t
d
e
l
,
c
s
d
e
l
.Transmission delay and spectrum handoff latency data transceiver of each forwarding node can be expressed as(5)
d
e
l
=
t
d
e
l
+
c
s
d
e
l
.The CRSN can be denoted by a directed graphG
(
V
,
E
), where V is the set of culminations to the diagram G. E represents CR links, that is, the set of edges directed graph G. The delay is set to the side length of directed graph, and then the delay d
e
l from source node s
(
v
i
) to the destination node d
(
v
j
) is the path weight w
i
j.Suppose there aren
p paths from the source node s
(
v
i
) to the destination node d
(
v
j
). Calculate the size of each path delay t
i
(
0
<
i
≤
n
p
) in ascending order. The minimum is the primary route p
r, and then calculate the value of the remaining paths with unrelated degree ∂. Because the backup route b
r satisfies both delay t
i and unrelated degree ∂ constraints, we can use weighted average of the two metrics as a basis for selecting a backup route b
r:(6)
β
=
a
t
i
+
1
-
a
∂
i
0
≤
a
≤
1
,where ∂
i represents the unrelated degrees and a is an adjustable parameter between t
i and ∂
i to achieve balance, while the value of a should be greater than 0.5 due to intermittent connectivity in CRNS.


## 3.3. Route Discovery

When the source nodes
(
v
i
) needs to send data to destination node d
(
v
j
), it sends network routing request message (RREQ), which is shown as(7)
R
R
E
Q
=
R
I
D
,
S
I
D
,
D
I
D
,
N
I
L
,
N
L
W
,where R
I
D indicates the route request identity, S
I
D indicates the address of the source node s
(
v
i
), D
I
D indicates the address of the destination node d
(
v
j
), N
I
L indicates the list of the intermediate nodes, and N
L
W indicates link weights between adjacent nodes. The intermediate message is as follows:(8)
m
v
i
∣
A
d
d
r
s
,
S
O
P
s
,
C
s
,where A
d
d
r
s denotes the address of intermediate node m
(
v
i
), S
O
P
s denotes spectrum opportunity set, and C
s denotes available channels. After the intermediate node received a non-duplicate RREQ, its address, spectrum opportunity set, and available channels will be added to the routing information list and then forwarded to the node of the next hop. When the destination node receives RREQ message, it will know the decision of the channel information of all links. Then, the proposed scheme will choose a route with the minimum delay as the primary route, p
r, and calculate a backup route b
r from all candidate routes according to expression (6). Then it sends the channel selection information routing reply message to the source node s
(
v
i
). Route response message is shown as(9)
R
R
E
P
=
P
T
,
R
I
D
,
D
I
D
,
R
R
,where P
T indicates the type of package, R
I
D denotes the neighbor node address of the RREP packet, D
I
D indicates the source node address of the route, R
R denotes route reply packet, and it consists of four parts:(10)
R
R
∣
N
L
,
C
C
,
W
C
,
L
W
,where N
L indicates the node sequence of source node s
(
v
i
) to destination node d
(
v
j
), C
C is the link assigned channel between cognitive nodes and the next cognitive node in N
L, W
C denotes all channels used by this cognitive node, and L
W is the weight of this link. When the source node s
(
v
i
) receives the RREP, it can send data according to the routing information.


## 3.4. Route Maintenance

The primary user preemption or node failure will lead to disconnected link. Quickly recover interrupted data transfer and effective rerouting become very important. In the proposed routing algorithm, when the source nodes
(
v
i
) failed to forward packets to the destination node d
(
v
j
), the link is disconnected or node failure. Then cognitive node will send a RSUS (Route Suspend) message and will notify the source node to suspend the current route request. If the disconnected link or node is not restored within the time t, it will send RERR (Route Error) to the source node. When the source node receives RERR message, if the backup route b
r is available, the source node will select the backup route b
r as the primary route p
r to transmit data packets; if the backup route b
r is unavailable, the source node s
(
v
i
) will initiate a new route discovery process.


## 3.5. Algorithm Design

The proposed algorithm BUD employs an improved depth first search (DFS) algorithm to find multiple paths in CRSNs. From the source node to the destination node, the DFS algorithm can only find one path. In order to find multiple suboptimized paths, when accessing a nodev
i, the proposed algorithm marks it as being accessed and set v
i
s
i
t
e
d
[
v
i
]
=
t
r
u
e until v
i is not the path to neighboring nodes and then set v
i
s
i
t
e
d
[
v
i
]
=
f
a
l
s
e. Hence the proposed algorithm can find all the paths from the source node s
(
v
i
) to the destination node d
(
v
j
).Considering the route selection criteria, the proposed algorithm BUD chooses a route with the minimum delay as the primary routep
r and then decides backup route b
r according to the delay parameter t
i and unrelated degree parameter ∂. The algorithm is described in detail as in Algorithm 1, and the flowchart is shown in Figure 1.Algorithm 1:The proposed routing algorithm.
Backup Routing Algorithm BUD
Input: Source node, destination node
Output: primary route, backup route
(1)visited
[
f
(
v
i
)
]
=
true; Push
(
&
S
,
f
(
v
i
)
);
(2)if  (
f
(
v
i
)
=
=
t
(
v
j
)
)
go to step 3,
else
go to step 4.
(3)vector
<
node
>
result
t
(
v
j
)
f
(
v
i
)
(
temp
,
sum
); node
x; x
.
path
=
temp
t
(
v
j
)
f
(
v
i
)
[
n
];
x
.
cos
⁡
t
=
sum
t
(
v
j
)
f
(
v
i
); result
t
(
v
j
)
f
(
v
i
)
(
temp
,
sum
)
.
push
_
back
(
x
);
go to step 8.
(4)f
o
r (i
n
t
k
=
0
;
k
<
nodenumber; ++k
)
(5)if  (
Graph
⁡
[
f
(
v
i
)
]
[
v
k
]
&
&
!
visited
[
v
k
]
)
go to step 6;
else
go to step 8.
(6)visited
[
v
k
]
=
true
;
Push
(
&
S
,
v
k
);
(7) DFS (G, v
k, t
(
v
j
)).
(8)visited
[
v
k
]
=
false
;
Pop
(
&
S
,
&
e
)
(9)if stack is empty
go to step 10;
else
find the next neighbor nodes of the top node in the stack;
go to step 5.
(10)if  (
result
t
v
j
f
v
i
(
temp
,
sum
)
[
i
]
.
cos
⁡
t
<
result
t
v
j
f
v
i
(
temp
,
sum
)
[
sum
min
⁡
]
.
cos
⁡
t
)
sum
min
⁡
=
i;
(11)c
r
β
i
=
α
*
result
t
v
j
f
v
i
(
temp
,
sum
)
[
i
]
.
cos
⁡
t
+
(
1
-
α
)
*
count
/
result
t
(
v
j
)
f
(
v
i
)
(
temp
,
sum
)
[
i
]
.
path
.
size
(
)
-
2;
if  (
c
r
β
i
<
b
r
β
)
b
r
β
=
c
r
β
i
;
c
r
min
⁡
=
i;
Select the route with smallestc
r
β
i value as backup route;
(12)return  p
r and c
r
β
i.Figure 1
The flowchart of the proposed algorithm BUD.The proposed algorithm works as follows.Step 1.
For the nodev
i, put it into the stack P
u
s
h
(
&
S
,
f
(
v
i
)
), and mark node v
i is accessing v
i
s
i
t
e
d
[
f
(
v
i
)
]
=
t
r
u
e.Step 2.
If the top node in the stack is the destination noded
(
v
j
), go to Step 3, or else go to Step 4.Step 3.
Store the sequence of nodes and the weights of this path inr
e
s
u
l
t
t
(
v
j
)
f
(
v
i
)
(
t
e
m
p
,
s
u
m
), then go to Step 8.Step 4.
Find the neighbor nodev
k of the top node.Step 5.
If the neighbor nodev
k is not visited, go to Step 6, or else go to Step 8.Step 6.
Setv
i
s
i
t
e
d
[
v
k
]
=
t
r
u
e and put node v
i into the stack.Step 7.
Consider DFS (G
,
v
k
,
t
(
v
i
)).Step 8.
Output current node from the stack and markv
k as v
i
s
i
t
e
d
[
v
k
]
=
f
a
l
s
e.Step 9.
If the stackS is empty, go to Step 10, or else find the next neighbor node v
k of the top node in the stack and then go to Step 5.Step 10.
Select the minimum weight path as the primary routep
r.Step 11.
Calculatec
r
β
i of all candidates route, and select the route with smallest c
r
β
i value as backup route.Step 12.
Output primary routep
r and backup route c
r
β
i.A general CRNS topology is shown in Figure2. The corresponding weighted adjacency matrix is shown in Figure 3.Figure 2
General CRSN topology.Figure 3
Weighted directed graphG.Weighted Adjacency Matrix. Consider(11)
0
w
a
b
w
a
c
0
w
a
e
0
0
0
0
0
0
w
b
f
0
0
0
w
c
d
0
0
0
0
0
0
0
w
d
f
0
0
0
w
e
d
0
w
e
f
0
0
0
0
0
0
.As shown in Figure2, v
i denotes cognitive sensor node and the weight w
i
j in directed edges denotes the delay of packet transmission from v
i to v
j, such as the weights from v
a to v
b are represented by w
a
b. From the topology shown in Figure 2, primary route p
r and backup route b
r can be discovered from the source node to the destination node according to the proposed route selection algorithm.For example, suppose thatv
a is the source node and v
f is destination node. In order to find the primary route p
r and backup route b
r from cognitive sensor nodes from v
a to v
f, the proposed algorithm finds all paths from v
a to v
f, and then the path of minimum weight will be the primary route p
r. And then calculate the value of β in each path according to (6) and choose the smallest value of the β as backup route b
r. All paths from v
a to v
f in this network topology are as follows: V
a
→
V
b
→
V
f, V
a
→
V
e
→
V
f, V
a
→
V
e
→
V
d
→
V
f, and V
a
→
V
c
→
V
d
→
V
f.


## 4. Performance Analysis

### 4.1. Numerical Results

The CRNs can be denoted as a directed graphG
(
V
,
E
). Figure 3 shows an example of weighted directed graph G, where there are 6 sensor nodes. And v
0 represents source node, v
5 represents destination node, and the weights in edge represent the delay between two nodes. The weighted adjacency matrix of directed graph G is shown in the following equation. According to the proposed algorithm, Table 1 shows the process of path discovery.Table 1
Path finding process ofG.
Current access node
Next accessible node
Access sequence
Weights
v
0
v
1, v
3
v
0
→
v
1
v
2, v
3
v
0
→
v
1
→
0.3
v
2
v
4, v
5
v
0
→
v
1
→
v
2
→
0.9
v
4
v
5
v
0
→
v
1
→
v
2
→
v
4
→
1.1
v
5
v
0
→
v
1
→
v
2
→
v
4
→
v
5
1.3
v
2
v
5
v
0
→
v
1
→
v
2
→
0.9
v
5
v
0
→
v
1
→
v
2
→
v
5
1.1
v
1
v
3
v
0
→
v
1
→
0.3
v
3
v
5
v
0
→
v
1
→
v
3
→
0.9
v
5
v
0
→
v
1
→
v
3
→
v
5
1.1
v
0
v
3
v
0
→
v
3
v
5
v
0
→
v
3
→
0.8
v
5
v
0
→
v
3
→
v
5
1.0Weighted Adjacency Matrix of
G. Consider(12)
0
0.3
0
0.8
0
0
0
0
0.6
0.6
0
0
0
0
0
0
0.2
0.2
0
0
0
0
0
0.2
0.9
0
0
0
0
0.2
0
0
0
0
0
0
.The proposed algorithm BUD works as follows. Pushv
0 into the stack and mark it as being accessed. Since v
0 is not the destination node v
5, continue to visit the next accessibility node of v
0, namely, v
1 and v
3. Moreover, record access sequence v
0
→ and corresponding weights 0. For the node v
1, put it into the stack and mark it as being accessed. Since v
1 is not the destination node v
5, it continues to visit the next accessibility nodes of v
1, v
2, and v
3 and record access sequence v
0
→
v
1
→ and corresponding weights 0.3. For the node v
2, put it into the stack and mark it as being accessed. Considering that v
2 is not the destination node v
5, continue to visit the next accessibility node of v
2, including v
4 and v
5 and then record access sequence v
0
→
v
1
→
v
2
→ and corresponding weights 0.9. For node v
4, put v
4 into the stack and mark it as being accessed, and since v
4 is not the destination node, it will continue to visit the next accessibility node v
5 of v
4. Since v
5 is the destination node, record access sequence v
0
→
v
1
→
v
2
→
v
4
→
v
5 and corresponding weights 1.3.Pop the top node of the stack and mark it as not being accessed. Since the stack is not empty, the top node of the stack node isv
4, and hence mark it as not being accessed. Since the next node is the destination node v
5, the algorithm records access sequence v
0
→
v
1
→
v
2
→
v
5 and corresponding weights 1.1.With the similar method, we can get all paths and corresponding weights from source nodev
0 to the destination node v
5 as follows:Path 1:v
0
→
v
3
→
v
5, cost: 1;
Path 2:v
0
→
v
1
→
v
2
→
v
5, cost: 1.1;
Path 3:v
0
→
v
1
→
v
3
→
v
5, cost: 1.1;
Path 4:v
0
→
v
1
→
v
2
→
v
4
→
v
5, cost: 1.3.According to the proposed algorithm, the shortest path 1 is the primary routep
r with the least delay. Then calculate the value of the remaining three paths according to (6) with a
=
0.6 as follows: (13)
β
1
=
0.6
∗
1.1
+
0.4
∗
0
2
=
0.66
,
β
2
=
0.6
∗
1.1
+
0.4
∗
1
2
=
0.86
,
β
3
=
0.6
∗
1.3
+
0.4
∗
0
3
=
0.78
.According to the results, although the two paths (v
0
→
v
1
→
v
2
→
v
5 and v
0
→
v
1
→
v
3
→
v
5) have the same delay, the path v
0
→
v
1
→
v
2
→
v
5 includes node v
3 with the primary route p
r (without considering the source node s
(
v
0
) and the destination node d
(
v
5
)). Therefore, the value of β
2 is greater than β
1. Although v
0
→
v
1
→
v
2
→
v
5 and v
0
→
v
1
→
v
2
→
v
4
→
v
5 do not contain the same node with the primary route p
r, the latter has higher delay than the former. This is the reason that β
3 is greater than β
1. And it is clear that the path v
0
→
v
1
→
v
2
→
v
5 will be the backup route b
r. The results also verify the effectiveness of the proposed algorithm.Figure4 shows another weighted directed graph G
′, where there are 7 cognitive nodes, v
0 represents source node, v
6 represents destination node, and the weights in edge represent the delay between two nodes. The weighted adjacency matrix of directed graph G
′ is shown in the following equation (14). And Table 2 shows the path discovery process of weighted directed graph G
′. The proposed algorithm is able to find all paths from the source node v
0 to the destination node v
6. The primary route and backup route are v
0
→
v
2
→
v
4
→
v
6 and v
0
→
v
1
→
v
3
→
v
6, respectively.Table 2
Path finding process ofG
′.
Current access node
Next accessible nodes
Access sequence
Weights
v
0
v
1, v
2
v
0
→
v
1
v
3
v
0
→
v
1
→
0.5
v
3
v
4, v
5, v
6
v
0
→
v
1
→
v
3
→
1.1
v
4
v
6
v
0
→
v
1
→
v
3
→
v
4
→
1.4
v
6
v
0
→
v
1
→
v
3
→
v
4
→
v
6
1.6
v
5
v
6
v
0
→
v
1
→
v
3
→
v
5
→
1.4
v
6
v
0
→
v
1
→
v
3
→
v
5
→
v
6
1.8
v
6
v
0
→
v
1
→
v
3
→
v
6
1.7
v
2
v
3, v
4
v
0
→
v
2
→
0.5
v
3
v
4, v
5, v
6
v
0
→
v
2
→
v
3
→
1.2
v
4
v
6
v
0
→
v
2
→
v
3
→
v
4
→
1.5
v
6
v
0
→
v
2
→
v
3
→
v
4
→
v
6
1.7
v
5
v
6
v
0
→
v
2
→
v
3
→
v
5
→
1.5
v
6
v
0
→
v
2
→
v
3
→
v
5
→
v
6
1.9
v
6
v
0
→
v
2
→
v
3
→
v
6
1.8
v
4
v
6
v
0
→
v
2
→
v
4
→
1.1
v
6
v
0
→
v
2
→
v
4
→
v
6
1.3Figure 4
Weighted directed graphG
′.Weighted Adjacency Matrix of
G
′
. Consider(14)
0
0.5
0.5
0
0
0
0
0
0
0
0.6
0
0
0
0
0
0
0.7
0.6
0
0
0
0
0
0
0.3
0.3
0.6
0
0
0
0
0
0
0.2
0
0
0
0
0
0
0.4
0
0
0
0
0
0
0
.According to the proposed algorithm, we can get all paths and the corresponding weights from source nodev
0 to the destination node v
6 as follows:Path 1:v
0
→
v
1
→
v
3
→
v
5
→
v
6, cost: 1.8;
Path 2:v
0
→
v
1
→
v
3
→
v
6, cost: 1.7;
Path 3:v
0
→
v
1
→
v
3
→
v
4
→
v
6, cost: 1.6;
Path 4:v
0
→
v
2
→
v
4
→
v
6, cost: 1.3;
Path 5:v
0
→
v
2
→
v
3
→
v
4
→
v
6, cost: 1.7;
Path 6:v
0
→
v
2
→
v
3
→
v
6, cost: 1.8;
Path 7:v
0
→
v
2
→
v
3
→
v
5
→
v
6, cost: 1.9.It is clear that the pathv
0
→
v
2
→
v
4
→
v
6 is the primary route p
r with the least delay, and then we can calculate the unrelated degrees of the remaining six paths according to (6) as follows with a
=
0.6:(15)
β
1
=
0.6
∗
1.8
+
0.4
∗
0
3
=
1.08
;
β
2
=
0.6
∗
1.7
+
0.4
∗
0
2
=
1.02
;
β
3
=
0.6
∗
1.6
+
0.4
∗
1
3
=
1.09
;
β
4
=
0.6
∗
1.7
+
0.4
∗
2
3
=
1.28
;
β
5
=
0.6
∗
1.8
+
0.4
∗
1
2
=
1.28
;
β
6
=
0.6
∗
1.9
+
0.4
∗
1
3
=
1.39
.Although path 2 and path 5 have the same delay, path 5 has the same nodesv
2 and v
4 with the primary route p
r (without considering the source node s
(
v
0
) and the destination node d
(
v
6
)). Therefore, β
5 is greater than β
2. Although path 2 and path 1 v
0
→
v
1
→
v
3
→
v
5
→
v
6 do not have the same node compared with the primary route p
r, the latter has bigger delay than the former. Hence path 2 is the backup route b
r. The results also verify the effectiveness of the proposed algorithm.


### 4.2. Simulation Results

In order to evaluate the performance of the proposed scheme, we implemented the backup routing based on delay constraint (Bud) with C++, and the algorithm without Bud is also simulated as discussed here. Our simulation is performed considering the deployed region as a square of fixed area of 500 m × 500 m. The communication range between two nodes is 100 m. The run time is 100 s. The system will generate 30 cognitive nodes randomly in every 10 s. And the source node and destination nodes also will be selected randomly.In the first scenario, we consider the random multi-hop topology networks with uniform increasing load. Figure5 shows the primary route, backup route, and topology with uniform increasing load when t
=
10 s and Figure 7 shows the delay of different schemes.Figure 5
Route and topology with uniform increasing load (t
=
10
s).As shown in Figure5, there are 2 nodes in the primary route from source SN to destination node DN and 3 nodes in the backup route. And the unrelated degree of two routes is zero, which means that the backup route will work efficiently if the primary route fails.The delay of difference routes is shown in Figure6. As the load increases, the delay of two schemes will increase accordingly. When the load is less than 30%, the delay of the proposed scheme is slightly higher than the scheme without the Bud. The reason is that backup route will lead to some delay in channel switching. However, for the scheme without the Bud, delay will increase to more than 130 ms when the load increases to 40%, which is obviously higher than that of the proposed scheme, while the delay is 87 ms for the proposed scheme. The reason is that, without Bud, nodes will start the route discovery procedure when load is heavy. In particular, the primary node will occupy most channel and some nodes will fail as the load increases. However, the proposed scheme takes both delay and unrelated degree into consideration, which will help the traffic to avoid the failure nodes and start backup route to guarantee transmission delay.Figure 6
Delay of different schemes with uniform increasing load (t
=
10
s).Figure 7
Route and topology with random increasing load (t
=
80
s).In the second scenario we evaluate and compare the performances with/without the proposed scheme in randomly network topologies with random load. Figures7 and 8 show route and delay, respectively, when t
=
80 s.Figure 8
Delay of different schemes with random load (t
=
80
s).As shown in Figure7, the primary route includes 6 nodes from source SN to destination node DN, and the backup route includes 6 nodes, too. And there is one contained node in the backup route (excluding the source node and destination node). The unrelated degree ∂ of two routes is 0.25, which means the backup route will fail if the contained node is invalidation. However, the backup route will work effectively in most cases when the primary route is out of service.The delay of difference route schemes with random load is shown in Figure8. As the load increases, the delay of two schemes will increase accordingly. When the load is less than 10%, the delay error of two schemes is not obvious. However, for the scheme without the Bud, delay will increase greatly. For example, the delay is more than 200 ms after the load increases to 30%, which is more than 100% of the proposed scheme, since the delay is 99 ms for the proposed scheme. When the load arrives at 95%, the delays of two schemes are 642 ms and 341 ms, respectively. And the reason is that, without Bud, random increasing load will lead some nodes to consume power quickly, and the failure nodes will lead to the primary route out of work, which will make the node to start the route discovery procedure and lead to heavy delay. In particular, the primary node will occupy most channel and some nodes will fail as the load increases. However, the proposed scheme will start backup route easily to avoid the failure nodes and guarantee transmission delay, since it considers both delay and unrelated degree. The results in Figure 8 also show the effectiveness of the proposed scheme.


## 4.1. Numerical Results

The CRNs can be denoted as a directed graphG
(
V
,
E
). Figure 3 shows an example of weighted directed graph G, where there are 6 sensor nodes. And v
0 represents source node, v
5 represents destination node, and the weights in edge represent the delay between two nodes. The weighted adjacency matrix of directed graph G is shown in the following equation. According to the proposed algorithm, Table 1 shows the process of path discovery.Table 1
Path finding process ofG.
Current access node
Next accessible node
Access sequence
Weights
v
0
v
1, v
3
v
0
→
v
1
v
2, v
3
v
0
→
v
1
→
0.3
v
2
v
4, v
5
v
0
→
v
1
→
v
2
→
0.9
v
4
v
5
v
0
→
v
1
→
v
2
→
v
4
→
1.1
v
5
v
0
→
v
1
→
v
2
→
v
4
→
v
5
1.3
v
2
v
5
v
0
→
v
1
→
v
2
→
0.9
v
5
v
0
→
v
1
→
v
2
→
v
5
1.1
v
1
v
3
v
0
→
v
1
→
0.3
v
3
v
5
v
0
→
v
1
→
v
3
→
0.9
v
5
v
0
→
v
1
→
v
3
→
v
5
1.1
v
0
v
3
v
0
→
v
3
v
5
v
0
→
v
3
→
0.8
v
5
v
0
→
v
3
→
v
5
1.0Weighted Adjacency Matrix of
G. Consider(12)
0
0.3
0
0.8
0
0
0
0
0.6
0.6
0
0
0
0
0
0
0.2
0.2
0
0
0
0
0
0.2
0.9
0
0
0
0
0.2
0
0
0
0
0
0
.The proposed algorithm BUD works as follows. Pushv
0 into the stack and mark it as being accessed. Since v
0 is not the destination node v
5, continue to visit the next accessibility node of v
0, namely, v
1 and v
3. Moreover, record access sequence v
0
→ and corresponding weights 0. For the node v
1, put it into the stack and mark it as being accessed. Since v
1 is not the destination node v
5, it continues to visit the next accessibility nodes of v
1, v
2, and v
3 and record access sequence v
0
→
v
1
→ and corresponding weights 0.3. For the node v
2, put it into the stack and mark it as being accessed. Considering that v
2 is not the destination node v
5, continue to visit the next accessibility node of v
2, including v
4 and v
5 and then record access sequence v
0
→
v
1
→
v
2
→ and corresponding weights 0.9. For node v
4, put v
4 into the stack and mark it as being accessed, and since v
4 is not the destination node, it will continue to visit the next accessibility node v
5 of v
4. Since v
5 is the destination node, record access sequence v
0
→
v
1
→
v
2
→
v
4
→
v
5 and corresponding weights 1.3.Pop the top node of the stack and mark it as not being accessed. Since the stack is not empty, the top node of the stack node isv
4, and hence mark it as not being accessed. Since the next node is the destination node v
5, the algorithm records access sequence v
0
→
v
1
→
v
2
→
v
5 and corresponding weights 1.1.With the similar method, we can get all paths and corresponding weights from source nodev
0 to the destination node v
5 as follows:Path 1:v
0
→
v
3
→
v
5, cost: 1;
Path 2:v
0
→
v
1
→
v
2
→
v
5, cost: 1.1;
Path 3:v
0
→
v
1
→
v
3
→
v
5, cost: 1.1;
Path 4:v
0
→
v
1
→
v
2
→
v
4
→
v
5, cost: 1.3.According to the proposed algorithm, the shortest path 1 is the primary routep
r with the least delay. Then calculate the value of the remaining three paths according to (6) with a
=
0.6 as follows: (13)
β
1
=
0.6
∗
1.1
+
0.4
∗
0
2
=
0.66
,
β
2
=
0.6
∗
1.1
+
0.4
∗
1
2
=
0.86
,
β
3
=
0.6
∗
1.3
+
0.4
∗
0
3
=
0.78
.According to the results, although the two paths (v
0
→
v
1
→
v
2
→
v
5 and v
0
→
v
1
→
v
3
→
v
5) have the same delay, the path v
0
→
v
1
→
v
2
→
v
5 includes node v
3 with the primary route p
r (without considering the source node s
(
v
0
) and the destination node d
(
v
5
)). Therefore, the value of β
2 is greater than β
1. Although v
0
→
v
1
→
v
2
→
v
5 and v
0
→
v
1
→
v
2
→
v
4
→
v
5 do not contain the same node with the primary route p
r, the latter has higher delay than the former. This is the reason that β
3 is greater than β
1. And it is clear that the path v
0
→
v
1
→
v
2
→
v
5 will be the backup route b
r. The results also verify the effectiveness of the proposed algorithm.Figure4 shows another weighted directed graph G
′, where there are 7 cognitive nodes, v
0 represents source node, v
6 represents destination node, and the weights in edge represent the delay between two nodes. The weighted adjacency matrix of directed graph G
′ is shown in the following equation (14). And Table 2 shows the path discovery process of weighted directed graph G
′. The proposed algorithm is able to find all paths from the source node v
0 to the destination node v
6. The primary route and backup route are v
0
→
v
2
→
v
4
→
v
6 and v
0
→
v
1
→
v
3
→
v
6, respectively.Table 2
Path finding process ofG
′.
Current access node
Next accessible nodes
Access sequence
Weights
v
0
v
1, v
2
v
0
→
v
1
v
3
v
0
→
v
1
→
0.5
v
3
v
4, v
5, v
6
v
0
→
v
1
→
v
3
→
1.1
v
4
v
6
v
0
→
v
1
→
v
3
→
v
4
→
1.4
v
6
v
0
→
v
1
→
v
3
→
v
4
→
v
6
1.6
v
5
v
6
v
0
→
v
1
→
v
3
→
v
5
→
1.4
v
6
v
0
→
v
1
→
v
3
→
v
5
→
v
6
1.8
v
6
v
0
→
v
1
→
v
3
→
v
6
1.7
v
2
v
3, v
4
v
0
→
v
2
→
0.5
v
3
v
4, v
5, v
6
v
0
→
v
2
→
v
3
→
1.2
v
4
v
6
v
0
→
v
2
→
v
3
→
v
4
→
1.5
v
6
v
0
→
v
2
→
v
3
→
v
4
→
v
6
1.7
v
5
v
6
v
0
→
v
2
→
v
3
→
v
5
→
1.5
v
6
v
0
→
v
2
→
v
3
→
v
5
→
v
6
1.9
v
6
v
0
→
v
2
→
v
3
→
v
6
1.8
v
4
v
6
v
0
→
v
2
→
v
4
→
1.1
v
6
v
0
→
v
2
→
v
4
→
v
6
1.3Figure 4
Weighted directed graphG
′.Weighted Adjacency Matrix of
G
′
. Consider(14)
0
0.5
0.5
0
0
0
0
0
0
0
0.6
0
0
0
0
0
0
0.7
0.6
0
0
0
0
0
0
0.3
0.3
0.6
0
0
0
0
0
0
0.2
0
0
0
0
0
0
0.4
0
0
0
0
0
0
0
.According to the proposed algorithm, we can get all paths and the corresponding weights from source nodev
0 to the destination node v
6 as follows:Path 1:v
0
→
v
1
→
v
3
→
v
5
→
v
6, cost: 1.8;
Path 2:v
0
→
v
1
→
v
3
→
v
6, cost: 1.7;
Path 3:v
0
→
v
1
→
v
3
→
v
4
→
v
6, cost: 1.6;
Path 4:v
0
→
v
2
→
v
4
→
v
6, cost: 1.3;
Path 5:v
0
→
v
2
→
v
3
→
v
4
→
v
6, cost: 1.7;
Path 6:v
0
→
v
2
→
v
3
→
v
6, cost: 1.8;
Path 7:v
0
→
v
2
→
v
3
→
v
5
→
v
6, cost: 1.9.It is clear that the pathv
0
→
v
2
→
v
4
→
v
6 is the primary route p
r with the least delay, and then we can calculate the unrelated degrees of the remaining six paths according to (6) as follows with a
=
0.6:(15)
β
1
=
0.6
∗
1.8
+
0.4
∗
0
3
=
1.08
;
β
2
=
0.6
∗
1.7
+
0.4
∗
0
2
=
1.02
;
β
3
=
0.6
∗
1.6
+
0.4
∗
1
3
=
1.09
;
β
4
=
0.6
∗
1.7
+
0.4
∗
2
3
=
1.28
;
β
5
=
0.6
∗
1.8
+
0.4
∗
1
2
=
1.28
;
β
6
=
0.6
∗
1.9
+
0.4
∗
1
3
=
1.39
.Although path 2 and path 5 have the same delay, path 5 has the same nodesv
2 and v
4 with the primary route p
r (without considering the source node s
(
v
0
) and the destination node d
(
v
6
)). Therefore, β
5 is greater than β
2. Although path 2 and path 1 v
0
→
v
1
→
v
3
→
v
5
→
v
6 do not have the same node compared with the primary route p
r, the latter has bigger delay than the former. Hence path 2 is the backup route b
r. The results also verify the effectiveness of the proposed algorithm.


## 4.2. Simulation Results

In order to evaluate the performance of the proposed scheme, we implemented the backup routing based on delay constraint (Bud) with C++, and the algorithm without Bud is also simulated as discussed here. Our simulation is performed considering the deployed region as a square of fixed area of 500 m × 500 m. The communication range between two nodes is 100 m. The run time is 100 s. The system will generate 30 cognitive nodes randomly in every 10 s. And the source node and destination nodes also will be selected randomly.In the first scenario, we consider the random multi-hop topology networks with uniform increasing load. Figure5 shows the primary route, backup route, and topology with uniform increasing load when t
=
10 s and Figure 7 shows the delay of different schemes.Figure 5
Route and topology with uniform increasing load (t
=
10
s).As shown in Figure5, there are 2 nodes in the primary route from source SN to destination node DN and 3 nodes in the backup route. And the unrelated degree of two routes is zero, which means that the backup route will work efficiently if the primary route fails.The delay of difference routes is shown in Figure6. As the load increases, the delay of two schemes will increase accordingly. When the load is less than 30%, the delay of the proposed scheme is slightly higher than the scheme without the Bud. The reason is that backup route will lead to some delay in channel switching. However, for the scheme without the Bud, delay will increase to more than 130 ms when the load increases to 40%, which is obviously higher than that of the proposed scheme, while the delay is 87 ms for the proposed scheme. The reason is that, without Bud, nodes will start the route discovery procedure when load is heavy. In particular, the primary node will occupy most channel and some nodes will fail as the load increases. However, the proposed scheme takes both delay and unrelated degree into consideration, which will help the traffic to avoid the failure nodes and start backup route to guarantee transmission delay.Figure 6
Delay of different schemes with uniform increasing load (t
=
10
s).Figure 7
Route and topology with random increasing load (t
=
80
s).In the second scenario we evaluate and compare the performances with/without the proposed scheme in randomly network topologies with random load. Figures7 and 8 show route and delay, respectively, when t
=
80 s.Figure 8
Delay of different schemes with random load (t
=
80
s).As shown in Figure7, the primary route includes 6 nodes from source SN to destination node DN, and the backup route includes 6 nodes, too. And there is one contained node in the backup route (excluding the source node and destination node). The unrelated degree ∂ of two routes is 0.25, which means the backup route will fail if the contained node is invalidation. However, the backup route will work effectively in most cases when the primary route is out of service.The delay of difference route schemes with random load is shown in Figure8. As the load increases, the delay of two schemes will increase accordingly. When the load is less than 10%, the delay error of two schemes is not obvious. However, for the scheme without the Bud, delay will increase greatly. For example, the delay is more than 200 ms after the load increases to 30%, which is more than 100% of the proposed scheme, since the delay is 99 ms for the proposed scheme. When the load arrives at 95%, the delays of two schemes are 642 ms and 341 ms, respectively. And the reason is that, without Bud, random increasing load will lead some nodes to consume power quickly, and the failure nodes will lead to the primary route out of work, which will make the node to start the route discovery procedure and lead to heavy delay. In particular, the primary node will occupy most channel and some nodes will fail as the load increases. However, the proposed scheme will start backup route easily to avoid the failure nodes and guarantee transmission delay, since it considers both delay and unrelated degree. The results in Figure 8 also show the effectiveness of the proposed scheme.


## 5. Conclusion

This paper proposed a backup routing algorithm for reliable routing based on the delay constraint and unrelated degree, which is able to provide higher reliability to dynamic spectrum used by the primary route and backup route. The proposed algorithm will determine the primary route with the smallest delay and select the backup route with the minimumβ according to expression (6). Numerical and simulation results show that the proposed algorithm can effectively overcome the intermittent connection problem and also decrease delay greatly.



---

*Source: 937104-2015-10-19.xml*