Sage Journals: Discover world-class research

Abstract

We discuss the delay-constrained energy efficient multicast routing problem in cognitive radio ad hoc networks. A cognitive radio ad hoc network is a wireless multihop network established by secondary users on varying available spectrum bands. The research on routing is a hot topic in the field of cognitive radio ad hoc networks. However, multicast routing algorithm study of cognitive radio ad hoc networks is still at its start stage. In this paper, we proposed a novel delay-constrained energy efficient multicast routing algorithm (DCEEMR) in cognitive radio ad hoc networks. The DCEEMR guarantees that the multicast tree can be found if it exists, and the multicast tree satisfies the delay bound and has low energy consumption. The algorithm uses delay-energy function to construct the multicast tree based on the spectrum selection. Through an example with random network topology, we demonstrate that our algorithm is better in terms of energy cost of multicast tree as compared to the existing algorithm QoS dependent multicast routing (QDMR). Moreover, the algorithm does not suffer from high complexity common to the algorithm QDMR. Experiment results by NS-2 show that the delay and cost of tree are lower than well-known multicast ad hoc on-demand distance vector (MAODV) protocol.

1. Introduction

Recent technological advances have resulted in the development of wireless ad hoc networks composed of devices that are self-organizing and can be deployed without infrastructure support. These devices generally have small form factors and have embedded storage, processing, and communication ability [1]. With the growing proliferation of wireless devices, spectra are increasingly becoming congested.

The license of the wireless spectrum is currently undertaken on a long-term basis over vast geographical regions. In order to address the critical problem of spectrum scarcity, the Federal Communications Commission (FCC) has recently approved the use of unlicensed devices in licensed bands. Consequently, dynamic spectrum access techniques are proposed to solve these current spectrum inefficiency problems. This new area of research foresees the development of cognitive radio networks to further improve spectrum efficiency. The basic idea of cognitive radio networks is that the unlicensed devices (also called cognitive radio users or secondary users) need to vacate the band once the licensed device (also known as a primary user) is detected. The emerging field of cognitive radio networks is geared to address the increasing congestion in the unlicensed band by opportunistically using vacant spectrum, such as frequencies licensed for television broadcast and public service, among others [2]. Cognitive radios are highly agile wireless platforms capable of autonomously choosing device parameters based on prevailing operating conditions [3]. Cognitive radio networks, however, impose unique challenges due to the high fluctuation in the available spectrum as well as diverse quality of service (QoS) requirements [4].

Cognitive radio ad hoc networks can be defined as follows [5]: cognitive radio ad hoc network is considered for realizing the cognitive radio by using multihop communication networks without giving the large interference toward the primary system. In [1], the authors give the differences between cognitive radio ad hoc networks and classical ad hoc networks.

(i) Choice of transmission spectrum: in cognitive radio ad hoc networks, the available spectrum bands are distributed over a wide frequency range, which vary over time and space. Thus, each user shows different spectrum availability according to the primary user activity. As opposed to this, classical ad hoc networks generally operate on a predecided channel that remains unchanged with time. For the ad hoc networks with multichannel support, all channels are continuously available for transmission, though nodes may select few of the latter from this set based on self-interference constraints. A key distinguishing factor is the primary consideration of protecting the primary user transmission, which is entirely missing in classical ad hoc networks.

(ii) Topology control: in classical ad hoc networks, this is easily accomplished by periodic beacon messages on the channel. However, in cognitive radio ad hoc networks, as the licensed spectrum opportunity exists over large range of frequencies, sending beacons over all the possible channels is not feasible. Thus, cognitive radio ad hoc networks are highly probable to have incomplete topology information, which leads in an increase in collisions among cognitive radio users as well as interference to the primary users.

(iii) Multihop/multispectrum transmission: the end-to-end route in the cognitive radio ad hoc networks consists of multiple hops having different channels according to the spectrum availability. Thus, cognitive radio ad hoc networks require collaboration between routing and spectrum allocation in establishing these routes. Moreover, the spectrum switches on the links are frequent based on primary user arrivals. As opposed to classical ad hoc networks, maintaining end-to-end QoS is involved.

(iv) Distinguishing mobility from primary user activity: in classical ad hoc networks, routes formed over multiple hops may periodically experience disconnections caused by node mobility. These cases may be detected when the next hop node in the path does not reply to messages and the retry limit is exceeded at the link layer. However, in cognitive radio ad hoc networks, a node may not be able to transmit immediately if it detects the presence of a primary user on the spectrum, even in the absence of mobility. Thus, correctly inferring mobility condition and initiating the appropriate recovery mechanism in cognitive radio ad hoc networks necessitate a different approach from the classical ad hoc networks.

(v) Spectrum sensing for cognitive radio: spectrum sensing is the very task upon which the entire operation of cognitive radio rests. For cognitive radio to fulfill the potential it offers to solve the spectrum underutilization problem and do so in a reliable and computationally feasible manner, we require a spectrum sensor that detects spectrum holes (i.e., underutilized subbands of the radio spectrum), provides high spectral-resolution capability, estimates the average power in each subband of the spectrum, and identifies the unknown directions of interfering signals [6–8].

Based on the above, the existing routing algorithms and routing protocols in classical ad hoc networks are not suitable for cognitive radio ad hoc networks and are unaware of the changing spectrum opportunity. In cognitive radio ad hoc networks, routes must be constructed to avoid the regions affected by active primary users and must also adapt themselves to subsequent changes induced by new primary user's arrival. We discuss the delay-constrained energy efficient multicast routing algorithm based on this principle.

The most significant challenges of routing in cognitive radio ad hoc networks are to maximize secondary users' throughput and minimize their consumed energy, while not interfering with the primary users. Energy efficiency is a critical issue in cognitive radio ad hoc network routing algorithms due to lack of infrastructure supporting. Furthermore increasing real-time applications require satisfying QoS constraints, such as delay, jitter, and data packets loss. For the sake of guaranteeing the behalf of primary user, such application requires consideration of spectrum selection and spectrum switching.

In the paper, we address the problem of multicast routing in cognitive radio ad hoc networks and first propose the delay-bounded energy efficient multicast routing algorithm in cognitive radio ad hoc networks. Multicast is communication from a single source node to a group of multicasts. A fundamental issue in multicast communication is route selection, usually based on trees. So our multicast routing algorithm makes great efforts to find a multicast tree, which is rooted from the source, spans all multicast nodes, and has lowest energy cost of the tree. In cognitive radio ad hoc networks, nodes communicate with each other by radio signals, which are broadcast in nature. The algorithm uses the local cost information, which it makes easily actualized in a distributed manner.

2. Related Works

Routing algorithm is a hotspot issue in the field of cognitive networks. In cognitive radio ad hoc networks, its routing research requires consideration of selection spectrum and routing path [9, 10]. However, numerous works focused multicast routing on classical wireless ad hoc networks [11]. Though there are some routing protocols on supporting spectrum decision in cognitive radio networks [12, 13], most of the existing works focus on unicast routing. As far as multicast routing algorithm is in cognitive radio ad hoc networks, the research is still in beginning stage.

In a classical ad hoc network, each node has a limited energy resource (battery) and operates in an unattended manner. Consequently, energy efficiency is an important design consideration for these networks. Most recent work [14–18] has been proposed for the problems of minimizing the energy consumption for multicasting in classical wireless ad hoc networks, addressed as minimum-energy multicast (MEM) [9, 14], respectively. Since the MEM problem has recently been shown to be NP-hard [19, 20], they proved the energy efficient multicast routing problem unlikely has an approximation algorithm with a constant performance ratio of the number of nodes in the networks. Efficient heuristic algorithm design has received much more attention. Li et al. [9] proposed a Steiner tree based algorithm with a guaranteed approximation performance ratio and two efficient heuristic algorithms for the energy efficient multicast problem in ad hoc networks. And they first prove the problem is NP-hard.

For the MEM problem, a straight greedy approach is the use of multicast trees that consist of the best unicast paths to each individual destination from the source node. In [14], multicast incremental power (MIP) method is based on a broadcast tree construction algorithm with pruning the redundant branches of the broadcast tree to obtain a multicast tree in wireless networks. For supporting real-time applications, there have been many delay-constrained multicast routing algorithms [15–17]. In [15], Kou et al. proposed a heuristic algorithm KMB named by the abbreviation of their names for the Steiner tree problem. In [16], Kompella et al. designed an algorithm named KPP (the abbreviation of the authors); the algorithm extends KMB algorithm to construct delay-constrained multicast tree. KPP algorithm assumes that the delay bound and link delays are all integers. Guo and Matta proposed QDMR algorithm in [17], which modified destination-driven multicast routing (DDMC) algorithm, where DDMC is an unconstrained Steiner tree heuristic algorithm [18]. QDMR dynamic adjusts its indicator function according to ratio between end-to-end delay (from source node to multicast node) and the delay bound. But the two algorithms are not designed for cognitive radio ad hoc network. Cheng et al. [12] proposed the method to evaluate cumulative delay in cognitive radio ad hoc network. In their protocol, the cumulative delay was regarded as routing metric, which was based on ad hoc on-demand distance vector (AODV) [21].

Our multicast routing algorithm arises from the observation that DDMC algorithm gives priority to multicast nodes and QDMR algorithm chooses the new adding node with lower end-to-end delay in constructing multicast tree as soon as possible. But it is quite different from these algorithms: at first, our multicast routing algorithm adapts to cognitive radio ad hoc network environment based on spectrum selection mechanism. The algorithm can construct an energy efficient multicast tree with satisfying the delay bound. Spectrum selection is based on our energy-delay function. Secondly, our algorithm considers the average cost consuming of candidate node covering multicast node in constructing multicast tree, so it is more efficient than existing algorithms. We detail our algorithm in Section 3. In the numerical results, we demonstrate that our algorithm is better in terms of energy cost as compared to the existing algorithm QDMP through an example. Experiment results by NS-2 show that the delay and energy cost are lower than well-known MAODV protocol [22].

In the remainder of this paper, in Section 2, the network model and the problem definition are given. We detail our algorithm DCEEMR in Section 3. In Section 4, we present the simulation results. Section 5 concludes this paper.

3. Network Model and Problem Specification

A cognitive radio ad hoc network can be modeled as a directed graph $G = (V, E)$ where $V = V_{C} \cup V_{P}$ represents total network nodes, $V_{C}$ represents cognitive nodes (secondary users), and $V_{P}$ represents primary nodes (primary users). E is the set of links representing logical connectivity between all cognitive nodes. There is no link among primary nodes and between primary nodes and cognitive nodes. If a link exists between cognitive nodes $v_{i}$ and $v_{j}$ , that means $v_{i}$ and $v_{j}$ can connect directly while not interfering with any primary node. We assume that $v_{i} \in V_{C}$ is a cognitive node and $N_{i}$ is the set of neighbor nodes of $v_{i}$ . Let $prec (v_{i})$ be the predecessor node of $v_{i}$ and $ε (v_{i}, v_{j})$ is the energy cost of link $(v_{i}, v_{j})$ . In this paper, we will construct an energy efficient multicast tree T, where $T \in G$ is a subnetwork of the cognitive ad hoc network. Our aim is to find a multicast tree T such that the sum of energy costs $ε (v_{i}, v_{j})$ $(i, j \in T)$ in multicast tree T is lower as soon as possible.

In addition, based on spectrum availability and node mobility of cognitive radio ad hoc networks, end-to-end delay should be considered during the process of designing algorithm. We assume that there are K channels in link $(v_{i}, v_{j})$ and $d^{k} (v_{i}, v_{j})$ is the delay of link $(v_{i}, v_{j})$ from node $v_{i}$ to $v_{j}$ through channel $k \in K$ and Δ is the delay bound, where $v_{i}, v_{j} \in V_{C}$ . In cognitive radio ad hoc networks, the end-to-end delay not only denotes path latency from source node to a multicast node but also includes the time of switching channel owing to the factor of primary user activity. Here, let $P (s, v_{i})$ denote a path (or routing) from source node s to $v_{i}$ . Similar to [2, 12], we assume that the channel switching time $t_{swich}^{v_{m}}$ is fixed at $v_{m} \in P (s, v_{i})$ and path latency $t_{p (s, v_{i})}^{v_{i}}$ is delay sum of all links from source node to multicast node $v_{i} \in M$ . If there is not primary user activity in a routing, then we have $t_{swich}^{v_{m}} = 0$ . In our algorithm, we will optimize the two objectives: energy consumption and end-to-end delay. But the energy efficiency is considered first; that is, if we find newly adding node which satisfy energy efficiency, then we check whether the network satisfies delay requirement. We will describe concretely our problem as follows.

Given a multicast request $(s, M)$ , where s is a source node and M is a set of multicast nodes; let T be a multicast tree rooted at source node s. Leaf nodes in T only receive message and do not need to transmit them. We assume receiving messages does not consume any energy that means only transmitting message could incur energy cost. Let $C_{T} (e)$ be the energy cost of the links in T. We assume that $D (v_{i}) = \sum_{v_{m} \in P (s, v_{i})} t_{swich}^{v_{m}} + t_{p (s, v_{i})}^{v_{i}}$ is the end-to-end delay of the path from source node s to the multicast node $v_{i} \in M$ and Δ is a delay bound which means the maximum tolerance of network if end-to-end delay is less than Δ. For every node $v_{i} \in M$ , the delay bound from s to $v_{i}$ must be satisfied. That means

\begin{matrix} Min \sum_{e \in T} C_{T} (e), \end{matrix}

(1)

\begin{matrix} D (v_{i}) < Δ \forall v_{i} \in M . \end{matrix}

(2)

When setting the delay bound to be infinity, the delay-constrained MEM problem simplifies to the unconstrained MEM problem in cognitive radio ad hoc network. Cognitive nodes in cognitive radio ad hoc network can be regarded as the nodes in classical ad hoc network without consideration of the interfering with primary users, and the problem can be seen as the special case of unconstrained MEM problem, which has been proved to be NP-hard. Our problem is how to, given a multicast request $(s, M)$ and energy cost $C_{T} (e)$ ( $e \in T$ ) for each link e, find a multicast tree rooted at s and spanning all nodes in M such that total energy cost is minimized. In this paper, we present a heuristic algorithm to resolve this problem.

4. DCEEMR Algorithm

In this section, we shall describe the algorithm in three parts: (i) the spectrum selection in multicast tree and (ii) the algorithm description and at last (iii) giving an example of DCEEMR algorithm. Through an example, we demonstrate that our algorithm is better in terms of energy cost of multicast tree as compared to the existing algorithm QDMR.

4.1. Spectrum Selection in Multicast Tree

In cognitive radio ad hoc networks, routing algorithm not only considers path selection but also faces spectrum decisions. Many routing protocols of cognitive radio ad hoc networks are based on basically routing protocols of classical ad hoc networks; for example, the routing selecting in [12, 23] is based on unicast routing protocol AODV and in [2] is based on geographic routing protocol greedy perimeter stateless routing (GPSR) [24]. The best routing paths are fist identified and then the preferred spectrums among the path are chosen in [3]; here, the AODV routing protocol is modified to include the list of preferred spectrums by a given node as the route request (RREQ) is forwarded. Once the RREQ is received, the destination is aware of spectrums that may be used to transmit at each hop and finds the optimal combination such that channel switching is minimized. These routing protocols are not applicable in delay-constrained energy efficient multicast routing problem, because it cannot guarantee the delay from source node to multicast nodes all satisfies the delay bound. But our spectrum selection mechanism is similar to these spectrum opportunities (SOP) methods [12]. Intuitively, a channel can be considered as an opportunity if it is not currently used by primary users [25]. Consider a pair of secondary users (A and B) aiming to communicate in the presence of primary users. A channel is an opportunity to A and B if they can communicate successfully over this channel while limiting the interference to primary users below a prescribed level determined by the regulatory policy. A common control channel is then formed by those traditional interfaces such that all nodes' SOP can be shared among network. The key message is that SOP must be defined jointly at the transmitter and the receiver. It is a function of (i) the transmission powers of both primary and secondary nodes, (ii) the geographical locations of these nodes, and (iii) the interference constraint. From this definition, we arrive at the following properties of spectrum opportunity. (P1)

Spectrum opportunity depends on both transmitting and receiving activities of primary users.

(P2)

Spectrum opportunity is, in general, asymmetric: a channel that is an opportunity when A is the transmitter and B the receiver may not be an opportunity when B is the transmitter and A the receiver.

In [12, 24], end-to-end delay consists of channel switching time and path latency which is delay sum of all links from source node to multicast node $v_{i} \in M$ . Based on $D (v_{i}) = \sum_{m \in P (s, v_{i})} t_{swich}^{m} + t_{p (s, v_{i})}^{i}$ , we can get the end-to-end delay from the source node to the nodes in multicast tree T. Similar with [2, 12], we select appropriate spectrum based on the delay for every node. Thus our work focuses on selecting appropriate nodes as tree nodes to construct a delay-bounded energy efficient multicast tree; we consider spectrum decision based on the delay in multicast tree in cognitive radio ad hoc network.

At first, a RREQ packet with piggyback (SOP s) information which is available spectrum band is transmitted by the source node s on each channel that is not affected by the primary user activity. For example, in Figure 1, the RREQ packet carries (SOP s) of node s transmit to node H, node I, and node J. If SOP information of receiving nodes shows intersection with sending node, this means that receiving node can use the same spectrum with sending node and does not interfere with nearby primary node; then the receiving node adds its own SOP information to the packet and then forwards the message. (i)

Handling RREQ packet: after receiving RREQ packet, as forwarding nodes, node H and node I add their own SOP information to the packet and then forward the different RREQ packet (bring their (SOP s, H) and (SOP s, I) information, resp.) to their next hop nodes if their SOP information shows intersection with (SOP s) and otherwise drops RREQ. But as destination nodes, nodes J, K, F, and G choose available spectrum band from intersection of (SOP s) and then encapsulate spectrum choice into route reply (RREP) and send it back to predecessor node or source node.

(ii)

Handling RREP packet: after receiving RREP packet, as forwarding nodes, nodes H and I assign an appropriate spectrum band to the next hop or source node, respectively, based on our delay-energy function in DCEEMR algorithm, which will be described concretely in the next subsection. But as source node, it starts data packet transfer.

Figure 1

Spectrum selection in multicast tree.

4.2. Formulas in DCEEMR Algorithm

Given a multicast request $(s, M)$ , we first define three sets. Firstly, let $V (T)$ be the set of nodes in multicast tree T, including only source node s at the beginning of constructing the tree. We aim to find the delay bounded efficient energy multicast tree including all multicast nodes in $V (T)$ . Let $N_{T}$ be the set of neighbor nodes of the multicast tree T; that is, it contains the neighbor nodes of candidate nodes. Meanwhile, let U be the set of the uncovered multicast nodes. An uncovered multicast node means a node belongs to neither $V (T)$ nor $N_{T}$ . We assume that $v_{i} \in V_{C}$ is a cognitive node and $N_{i}$ is the set of neighbor nodes of $v_{i}$ . Let $prec (v_{i})$ be the predecessor node of $v_{i}$ and $ε (v_{i}, v_{j})$ is the cost of link $(v_{i}, v_{j})$ .

This heuristic grows the multicast tree from s. At the beginning, $V (T)$ only contains source node s, $N_{T}$ contains the neighbor nodes of s, and U contains all multicast nodes. After running the algorithm to end, U becomes ⌀ that means $V (T)$ contains all multicast nodes. For selecting appropriate forwarding nodes to minimize the total cost in formula (1) and to satisfy the delay bound Δ, we define a delay-energy function to evaluate each candidate node $v_{i} \in N_{T}$ :

\begin{array}{l} f (v_{i}) = (ε (prec (v_{i}), v_{i}) + \frac{\sum_{v_{j} \in N_{i} \cap U} ε (v_{i}, v_{j})}{|N_{i} \cap U|}) X, \\ X = \frac{1}{\sum_{v_{j} \in N_{i} \cap U} (Δ - D (v_{j})) (1 / |N_{i} \cap U|)}, \\ |N_{i} \cap U| \neq 0, \end{array}

(3)

\begin{array}{l} g (v_{i}) = ε (prec (v_{i}), v_{i}) \frac{D (v_{i})}{Δ}, |N_{i} \cap U| = 0, D (v_{i}) < Δ, \end{array}

(4)

where

ε (prec (v_{i}), v_{i})

denote link cost between tree node

prec (v_{i})

and the candidate node

v_{i}

and

(\sum_{v_{j} \in N_{i} \cap U} ε (v_{i}, v_{j})) / |N_{i} \cap U|

denotes the average energy cost of the candidate node

v_{i} \in N_{T}

covering a multicast node.

\sum_{v_{j} \in N_{i} \cap U} (Δ - D (v_{j})) (1 / |N_{i} \cap U|)

denotes the average residual delay from the source node to a multicast node covered by the candidate node

v_{i}

, where

D (v_{i}) = \sum_{v_{m} \in P (s, v_{i})} t_{swich}^{v_{m}} + t_{p (s, v_{i})}^{v_{i}}

is the end-to-end delay from the source node to the multicast node

v_{j}

. The nodes with lower energy cost and delay are chosen to add to the tree in our algorithm.

If the candidate node $v_{i} \in N_{T}$ subject to $N_{i} \cap U \neq ⌀$ , choose the node with lower $f (v_{i})$ using formula (3) to add to the tree. If he candidate node $v_{i} \in N_{T}$ subject to $N_{i} \cap U = ⌀$ , we use formula (4) to evaluate every candidate node.

Now, we discuss our energy-delay function. In KPP algorithm, the choice function only adds the cost link which ensures the ratio of the cost between two multicast nodes and residual delay in completed graph to be lowest. But it does not fit for cognitive radio ad hoc network. Instead, we first calculate the average cost of the candidate node covering multicast nodes and then use the sum of the average cost and the communication cost between the candidate node and its father node as numerator. This sum value is more fair and proper to the delay-constrained energy efficient multicast routing problem in cognitive network. While the value of $f (v_{i})$ is lower, the cost consuming of candidate node covering multicast node is more efficient, and at the same time, the end-to-end delay is less than delay bound Δ.

In DDMC algorithm, the algorithm gives priority to multicast nodes. The cost of a new node v via a node u to add to the multicast tree is $Cost (v) = I_{D} (u) Cost (u) + c (u, v)$ , where the indicator function $I_{D} (u)$ is defined as follows:

\begin{matrix} I_{D} (u) = \{\begin{cases} 0, & if u \in M, \\ 1, & otherwise, \end{cases} \end{matrix}

(5)

where M is the set of multicast nodes. If node u is a multicast node, the cost of the new node v is only the cost of the link from node u to v. It made the path to a new node via a multicast node more likely to add to the tree. This information is used to give “preference” to multicast nodes. But the constructed tree is easy to have some very long branches like a chain of multicast nodes, which make some multicast nodes violate delay bound. Guo and Matta proposed QDMR algorithm in [17], which modified DDMC algorithm. It modified the indicator function, which can be adjusted according to how far a multicast node is from the delay bound. The indicator function is

\begin{matrix} I_{D} (u) = \{\begin{cases} \frac{Delay (u)}{Δ}, & if u \in M, \\ 1, & otherwise, \end{cases} \end{matrix}

(6)

where

Delay (u)

is the delay sum of all links from source node to multicast node u and Δ is the delay bound. If the delay of the source node to a multicast node is closer to delay bound, the multicast nodes are given less priority to be a parent node of the newly added node.

In our algorithm, formula (4) is based on the indicator function of QDMR algorithm. But our $D (v_{i})$ and $ε (prec (v_{i}), v_{i})$ are quite different with QDMR as mentioned. $D (v_{i})$ is the end-to-end delay from the source node to node $v_{i}$ which is the neighbor node of the tree. In QDMR algorithm, $Delay (u)$ in its indicator function means the delay from the source node to the multicast node u in tree. And the cost of a newly added node v need add the cost of the node which is in the tree. Our algorithm does not need to give priority to multicast nodes, and the cost of a new node v is not related with the parent tree node in the algorithm. Instead, we evaluate the cost of a new node by its delay and the energy cost between the tree and it. Similar to (3), formula (4) gives the priority to the node which consumes less energy and lower delay.

When selecting the next hop node, if $N_{i} \cap U \neq ⌀$ , choose the node with lower $f (v_{i})$ to add to the tree. If nodes have the same $f (v_{i})$ or $N_{i} \cap U = ⌀$ (that means the set of neighbor nodes of candidate nodes has no any multicast node), choose the node with $g (v_{i})$ lower to add to the tree.

4.3. Algorithm Implements

Input. Network graph G, a source node s, and the set of multicast nodes M.

Output. A delay-bounded energy efficient multicast tree T.

Step 1.

Initialization: let $V (T) = \{s\}$ , $U = M$ , and $N_{T} = N_{s}$ .

Step 2.

Based on the spectrum section mechanism in Section 4.1, source node s and candidate nodes select available spectrums to neighbor nodes of $N_{T}$ .

Step 3.

If $U \neq ⌀$ , consider the following. (1)

If exists $v_{i} \in N_{T}$ subject to $N_{i} \cap U \neq ⌀$ , select an appropriate $v_{i} \in N_{T}$ to minimize $f (v_{i})$ in formula (3).

(2)

If has no node $v_{i} \in N_{T}$ subject to $N_{i} \cap U \neq ⌀$ , select an appropriate $v_{i} \in N_{T}$ to minimize $g (v_{i})$ in formula (4).

When choose the node to add to the tree, let $V (T) = V (T) \cup \{v_{i}\} \cup (N_{i} \cap U)$ , and $U = M - M \cap N_{i}$ , and update $N_{T}$ .

Step 4.

If $U = ⌀$ , the algorithm stops. Otherwise go to Step 2.

Theorem 1.

Given a request $(s, M)$ in $G = (V, E)$ , the DCEEMR algorithm can output a delay-constraint energy efficiency multicast tree in time $O ({|V|}^{2})$ .

Proof.

To prove correctness, we need show the algorithm satisfies following conditions: (a)

feasibility, that is, output of the algorithm is a multicast tree;

(b)

the multicast tree is delay-constraint energy efficiency.

In the above-mentioned two conditions, (a) can be satisfied because the algorithm is greedy algorithm based on the idea of SPT (shortest path tree algorithm) [26]; it is easy to know that the greedy algorithm can output a multicast tree. For condition (b), the energy efficiency and delay-constraint can be guaranteed by Step 3 based on delay-energy function. If there have not been any multicast nodes in the set of neighbor nodes of candidate nodes ( $|N_{i} \cap U| = 0$ ), we choose the node with lowest value of $g (v_{i})$ . If the delay violates the delay bound Δ, then it shows the delay bound is too tight for the network. Thus it is impossible to construct a multicast tree to satisfy such QoS of the application layer.

The running time is obvious: searching for the node with lowest $f (v_{i})$ (or $g (v_{i})$ ) requires $O (|V|)$ and the number of cycles in worst case is $|V|$ times in Step 3. Therefore the time complexity of DCEEMR algorithm is $O ({|V|}^{2})$ .

4.4. An Example of DCEEMR

As the above, we know that the algorithm QDMR [17] is close to our algorithm. Though the algorithm QDMR is adapted to classical ad hoc networks, it does not conflict with our comparison if we do not consider spectrum selection. We will compare these algorithms through an example. In this example, we assume that a network scenario is random as in Figure 2. Given a multicast requirement as Figure 2, s is a source node and $D = \{d_{1}, d_{2}, d_{3}, d_{4}\}$ is the set of multicast nodes. The parameters of link denote energy cost and delay value. Here, we assume the constrained delay $Δ = 7$ .

Figure 2

Network scenario.

Figures 3 and 4 show that the multicast tree constructed by QDMR and our algorithm DCEEMR. From the figures, we can see that the cost of multicast tree by QDMR is 20 and the cost of multicast tree by our algorithm is 17. It means that the performance of DCEEMR about tree cost is better than QDMR, and it is important on delay-bounded minimum-cost multicast routing problem.

Figure 3

The multicast tree obtained by QDMR.

Figure 4

The multicast tree obtained by DCEEMR.

5. Numerical Results

In this section, we use numerical results from NS-2 to evaluate the performance of DCEEMR under different network conditions. The simulation model is built in the NS-2 simulator with multiradio multichannel extensions. We model the primary users' activities by using the exponential ON-OFF process as in [2]. Simulations are performed in random multihop network topologies of 50 nodes in an area of 1000 m × 1000 m. The coverage range of the primary user on its occupied channel is 300 m and the transmission range of the secondary user is set at 120 m. The node and primary user locations are randomly chosen in each trial run and an average of 30 trial runs is used for a data point. In this simulation, the initial energy of all nodes is set to be 10 J, and the transmission power of sending node is 0.66 W. We assumed that the receiving messages do not consume any energy that means only transmitting message could incur energy cost. We set channel switching time as 5 ms and the delay bound $Δ = 0.5 s$ . The size of every data packet is 256 bits and the maximum number of transmission packet is 1024.

We demonstrate the performance improvement attained by DCEEMR, by (i) direct comparison with classical multicast routing protocol MAODV, suitably extended for a multichannel environment, and (ii) by selectively enabling the joint path and channel optimization modules present in it. We perform four different tests in our study by measuring the impact of (a) number of channels, (b) number of primary users, (c) network size, and (d) multicast group size.

At first, we study the impact of number of channels and number of primary users. We consider two separate cases of 5 and 10 channels, in which a randomly chosen number of primary users is considered from the range [1, 9]. We first consider the end-to-end delay for 5 and 10 channels, as shown in Figures 5(a) and 5(b), respectively. The difference in end-to-end delay between DCEEMR and MAODV is significant. It is counterintuitive as the path to the destination for MAODV is the least in terms of hops, as it is not sensitive to the presence of the primary users. Further investigation revealed that the end-to-end delay is larger when 5 channels are present as compared to 10 channels. This is because when more channels are present, the cognitive users can use more channels and can select the link or routing with shorter delay. But the end-to-end delay is increasing with the increasing number of primary users. This is because the channel switch time is increasing due to the fact that the more primary users render large regions ineffective for transmission.

Figure 5

(a) The end-to-end delay for the case of 5 channels. (b) The end-to-end delay for the case of 10 channels.

Figures 6(a) and 6(b) show that energy consumption of constructing multicast tree with using DCEEMR and MAODV, respectively. We observe that the DCEEMR gives a good performance because the algorithm considers the energy efficiency based on delay-energy function. We can see that the energy consumption is increasing with the increasing number of primary users for both protocols. This is the key reason for higher retransmission radio and more forwarding nodes. In comparison, the DCEEMR uses delay-energy function to select next hop; this alleviates the energy consumption in the network thus giving better energy efficiency.

Figure 6

(a) The energy consumption for the case of 5 channels. (b) The energy consumption for the case of 10 channels.

We next observe the end-to-end delay and energy consumption of the multicast trees that are built using DCEEMR and MAODV when we fix the number of primary users and channels. Figures 7(a) and 7(b) show the end-to-end delay of multicast tree for the MAODV and DCEEMR in above simulation environment. It can be seen that the DCEEMR has the lower end-to-end delay than MAODV. This means that the speed of building multicast tree by our algorithm DCEEMR is faster than MAODV and satisfies the delay bound Δ.

Figure 7

(a) Delay of constructing multicast tree by MAODV. (b) Delay of constructing multicast tree by DCEEMR.

We next compare the energy consumption of the multicast tree built using above DCEEMR and MAODV. We track the energy consumption of DCEEMR and MAODV for 30, 35, 40, 45, and 50 nodes networks in Figure 8. From Figure 8, we can see that the energy consumption of DCEEMR is obviously smaller than MAODV whether over time and for different network size.

Figure 8

Energy consumption of multicast tree in MAODV and DCEFHA with network size.

Finally, we track the tree cost of DCEEMR and MAODV for different multicast group size. Figure 9 shows the tree cost of two algorithms for multicast group size from 10 to 20. It can be seen that the tree cost of DCEEMR is obviously smaller than the tree cost of MAODV, and increasing speed of tree cost is more and more slow in DCEEMR than in MAODV. From Figure 9, we can see the tree cost in MAODV is not mean in the rising process, because the MAODV cannot consider the energy cost of the multicast tree.

Figure 9

Energy consumption of multicast tree in MAODV and DCEFHA with multicast group size.

6. Conclusions

In this paper, we discuss the problem of construction minimum cost multicast tree satisfying delay bounded in cognitive radio ad hoc networks, which has been proved to be NP-hard. We proposed a novel delay-constrained energy efficient multicast routing heuristic algorithm (DCEEMR) to solve this NP-hard problem and the algorithm can be easily implemented in a distributed fashion because it only requires each node to have the information about its direct neighbors.

In the algorithm, we propose a delay-energy function which guarantees lower energy cost and lower residual end-to-end delay. The algorithm uses the delay-energy function to construct the multicast tree based on the spectrum selection. Through an example, we demonstrate that our algorithm is better in terms of energy consumption cost as compared to the existing algorithm QDMP. Experiment results by NS-2 show that the delay and energy cost are lower than well-known MAODV protocol.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported in part by the National Science Foundation of P. R. China under Grant (no. 61309033) and meanwhile is supported by the Education Department of Research Foundation for Key Program of Education Bureau of Henan Province (no. 13A510030 and no. 14A520024) and Zhengzhou Science and Technology bureau Research Project (no. 131PPTTGG423-2). This work is also supported by National Natural Science Foundation of China (no. U1304606), Science and Technology Development Project of Henan Province (no. 132102210555), National High Technology Research and Development Program of China (863 Program) (no. 2012AA101608), and Research Foundation for Key Program of Education Bureau of Henan Province (no. 14B413008). In addition, we hereby express gratitude to my dear partners Yingfeng Wang, Long Zhang, and Junling Yuan; without their effort, this thesis cannot be accomplished.

References

Akyildiz

I. F.

Lee

W.-Y.

Chowdhury

K. R.

CRAHNs: cognitive radio ad hoc networks

Ad Hoc Networks 2009 7 5 810 836

10.1016/j.adhoc.2009.01.001

2-s2.0-60249084757

Chowdhury

K. R.

Felice

M. D.

Search: a routing protocol for mobile cognitive radio ad-hoc networks

Computer Communications 2009 32 18 1983 1997

10.1016/j.comcom.2009.06.011

2-s2.0-70449523011

Haykin

Cognitive radio: brain-empowered wireless communications

IEEE Journal on Selected Areas in Communications 2005 23 2 201 220

10.1109/JSAC.2004.839380

2-s2.0-13844296408

Akyildiz

I. F.

Lee

W. Y.

Vuran

M. C.

Mohanty

Next generation dynamic spectrum access/cognitive radio wireless networks: a survey

Computer Networks 2006 50 13 2127 2159

10.1016/j.comnet.2006.05.001

2-s2.0-33745648091

Fujii

Kamiya

Suzuki

Multi-band ad-hoc cognitive radio for reducing inter system interference

Proceedings of the IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC ′06)

September 2006

Piscataway, NJ, USA

10.1109/PIMRC.2006.254062

2-s2.0-44949105328

Ding

Wang

Yao

Y.-D.

Spatial-temporal opportunity detection for spectrum-heterogeneous cognitive radio networks: two-dimensional sensing

IEEE Transactions on Wireless Communications 2013 12 2 516 526

10.1109/TWC.2012.122212.111638

2-s2.0-84874945569

Axell

Leus

Larsson

E. G.

Poor

H. V.

Spectrum sensing for cognitive radio: state-of-the-art and recent advances

IEEE Signal Processing Magazine 2012 29 3 101 116

10.1109/MSP.2012.2183771

2-s2.0-84859887551

Ding

Yao

Y.-D.

Wang

Chen

Kernel-based learning for statistical signal processing in cognitive radio networks: theoretical foundations, example applications, and future directions

IEEE Signal Processing Magazine 2013 30 4 126 136

10.1109/MSP.2013.2251071

2-s2.0-84879166568

Liu

Jia

Energy efficient multicast routing in ad hoc wireless networks

Computer Communications 2007 30 18 3746 3756

10.1016/j.comcom.2007.09.003

2-s2.0-36549023397

10.

Fujii

Multi-band routing for ad-hoc cognitive radio networks

Proceeding of the Technical Conference and Product Exposition (SDR ′06)

2006

11.

Guo

Yang

Energy-aware multicasting in wireless ad hoc networks: a survey and discussion

Computer Communications 2007 30 9 2129 2148

10.1016/j.comcom.2007.04.006

2-s2.0-34250685782

12.

Cheng

Liu

Cheng

Joint on-demand routing and spectrum assignment in Cognitive Radio Networks

Proceedings of the IEEE International Conference on Communications (ICC ′07)

June 2007

Glasgow, Scotland

6499 6503

10.1109/ICC.2007.1075

2-s2.0-38549100661

13.

Xin

Shen

C.-C.

A path-centric channel assignment framework for cognitive radio wireless networks

Mobile Networks and Applications 2008 13 5 463 476

10.1007/s11036-008-0084-y

2-s2.0-52549088584

14.

Wieselthier

J. E.

Nguyen

G. D.

Ephremides

On the construction of energy-efficient broadcast and multicast trees in wireless networks

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM ′00)

March 2000

New York, NY, USA

585 594

2-s2.0-0033894011

15.

Kou

Markowsky

Berman

A fast algorithm for Steiner trees

Acta Informatica 1981 15 2 141 145

10.1007/BF00288961

MR599613

2-s2.0-34250246836

16.

Kompella

V. P.

Pasquale

J. C.

Polyzos

G. C.

Multicasting for multimedia applications

Proceedings of the 11th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′92)

May 1992

Florence, Italy

2078 2085

10.1109/INFCOM.1992.263480

17.

Guo

Matta

QDMR: an efficient QoS dependent multicast routing algorithm

Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium (RTAS ′99)

June 1999

Vancouver, Canada

213 222

2-s2.0-0032593178

18.

Shaikh

Shin

Destination-driven routing for low-cost multicast

IEEE Journal on Selected Areas in Communications 1997 15 3 373 381

10.1109/49.564135

2-s2.0-0031120635

19.

Mario

Hubaux

J. P.

Christian

Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues

Proceedings of 8th Annual International Conference on Mobile Computing and Networking (MOBICOM ′02)

2002

Atlana, Ga, USA

172 182

20.

Clementi

A. E.

Crescenzi

Penna

Rossi

Vocca

On the complexity of computing minimum energy consumption broadcast subgraphs

Proceedings of 18th International Symposium on Theoretical Aspects of Computer Science

2001

Dresden, Germany

121 131

21.

Perkins

Belding

Das

Ad-hoc on-demand distance vector (AODV) routing

RFC 2003 3561

22.

Royer

E. M.

Perkins

C. E.

Multicast ad hoc on-demand distance vector (MAODV) routing

IETF Manet (draft-ietf-manet-maodv-00.txt), 2000

23.

Cheng

Liu

Cheng

Spectrum aware on-demand routing in cognitive radio networks

Proceedings of the 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN ′07)

April 2007

Dublin, Ireland

571 574

10.1109/DYSPAN.2007.80

2-s2.0-34548754577

24.

Karp

Kung

H. T.

GPSR: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00)

August 2000

243 254

2-s2.0-0034547115

10.1145/345910.345953

25.

Zhao

Spectrum opportunity and interference constraint in opportunistic spectrum access

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP ′07)

April 2007

III605 III608

10.1109/ICASSP.2007.366752

2-s2.0-34547520030

26.

Fujinoki

Christensen

K. J.

New shortest best path tree (SBPT) algorithm for dynamic multicast trees

Proceeding of the 24th Conference on Local Computer Networks (LCN '99)

October 1999

Lowell, Mass, USA

204 211

2-s2.0-0033326464

DCEEMR: A Delay-Constrained Energy Efficient Multicast Routing Algorithm in Cognitive Radio Ad Hoc Networks

Abstract

1. Introduction

2. Related Works

3. Network Model and Problem Specification

4. DCEEMR Algorithm

4.1. Spectrum Selection in Multicast Tree

4.2. Formulas in DCEEMR Algorithm

4.3. Algorithm Implements

Step 1.

Step 2.

Step 3.

Step 4.

Theorem 1.

Proof.

4.4. An Example of DCEEMR

5. Numerical Results

6. Conclusions

Footnotes

Conflict of Interests

Acknowledgments

References