A Survey on Routing Protocols for Cognitive Radio Networks

A Survey on Routing Protocols for Cognitive Radio Networks

Monisha Devi Dipjyoti Deka

Department of Computer Science and Engineering Department of Computer Science and Engineering Tezpur University Tezpur University

Tezpur, Assam, India Tezpur, Assam, India

Abstract In todays world of communication, cognitive radio (CR) has emerged as one of the most promising technology to overcome the inefficient spectrum utilization problem. The basic intention behind CR is to opportunistically allow unlicensed users to utilize the vacant licensed spectrum without causing much interference to licensed users, thereby providing a solution to limited available spectrum. CR nodes are adapted to the dynamics of spectrum availability. Although, routing is a fundamental concept in ad hoc wireless communication, but in CR network, spectrum scarcity makes routing a challenging issue to carry out end-to-end data transmission. Change in available channel list for a CR user firmly accounts to the problem of routing. In this paper, a survey of different routing protocols used in CR ad hoc network has been presented.

Keywords Cognitive radio network (CRN), routing, primary user (PU), secondary user (SU), spectrum opportunity (SOP)

1. INTRODUCTION

   Use of radio frequency (RF) bands has shown a rapid growth in the recent years all around the world. Users rely on allocation of these spectrum bands for carrying out various services. However, according to spectrum allocation policy, certain frequency bands are allocated only to licensed users, while others are open for all unlicensed users. Some of the devices that can make efficient use of unlicensed spectrum are like, Bluetooth, Wifi, digital cordless phone etc. The frequency bands are regulated by several standard bodies. Federal Communications Commission (FCC) of United States of America[2] is one such body according to whom, plenty of space in licensed spectrum remain underutilized for most of the time, and on the other hand, unlicensed bands often remain congested causing interference among the applications functioning in this band. The spectrum utility has been illustrated in Figure

   1. Hence, to rule out the spectrum usage problem and to make the best use of RF spectrum, cognitive radio (CR) [1] was brought into use.CR makes a flexible use of RF spectrum by permitting access to the unused licensed spectrum in an opportunistic manner. Unlicensed or Secondary users (SU) make effective use of these underutilized bands by reconfiguring the parameters dynamically. A cognitive radio network (CRN) comprises of nodes equipped with CR transceiver. In this net- work environment, CR nodes determine the available spectrum bands which are also known as spectrum holes,

      characterize the selected bands and choose the most appropriate band from the availability list

      In situations where a Primary user (PU) returns to a spectrum band that is currently being utilized by some Secondary user, the CR user experiences spectrum mobility where in, the CR user immediately vacates the band and moves to another spectrum hole. Therefore, the foremost aim of CRN is to enhance the spectrum utilization efficiency for better communication performance.

      Fig 1: Spectrum Utilization [1]

      The rest of the paper is organized as follows. In Section 2, we discussed about the routing functionality in CR network. In Section 3, the routing protocols designed for CRN are classified accordingly. In Section 4, we tabled the routing protocols by carrying out a comparison between them. And finally we conclude our survey of routing techniques in CRN in Section 5.

2. ROUTING IN CRN : A CHALLENGE Secondary users (SU) in a CR network communicate

   among

   themselves in a multi hop ad hoc manner. While performing end-to end data transmission between any of these users, certain complications are being faced because of the dynamic nature of spectrum availability and data rates. This dynamic behavior of the allocated channels arises because of some

   Primary user activity. Even if a route is being built between the users, links on the route remain unstable and at any time when dynamic channel on a link becomes unavailable, the route breaks down calling off the data transmission. In a CRN environment, the available spectrum bands may vary from user to user with time and location. This characteristic of CR nodes necessitates collaboration between spectrum decision and route selection to design route in multi hop CRN. Therefore, planning a routing protocol for CR network needs to consider the above mentioned issues [3].In our upcoming sections, we have presented some of the routing protocols favored in this network.

3. CLASSIFICATION OF ROUTING PROTOCOLS

   CRN routing protocols are comparatively different from those used in traditional multi hop ad hoc networks. These protocols have been classified into several categories based on their operation, which includes, tree based routing, location coordination based routing, on demand routing, dynamic spectrum routing, and multipath based routing. A figure representing this classification is shown below:

   Routing protocols for CRN

   Dynamic Spectrum Routing

   Tree Based Routing

   On Demand Routing

   Local Coordination Routing

   Multipath Based Routing

   Fig 2: Routing protocols for CRN

   1. Tree Based Routing

      Tree based routing is an approach where formation of a spectrum-tree manages the collaboration between route selection and spectrum decision in a well-organized way. The following subsection summarizes two such protocols.

      1. Spectrum-Tree Based On-Demand Routing Protocol (STOD-RP): While routing in CRN, users come across a situation that requires spectrum awareness to get hold of correct routing decisions. To secure this cooperation between route selection and spectrum decision, STOP-RP protocol [10] was designed that aims at constructing a spectrum tree in each spectrum band by considering a new route metric. Cognitive route cost is the metric preferred for this solution as it considers both CR users QoS requirements and Primary user activities to provide an effective path. Each spectrum-tree picks out only one root node that keeps information about the entire topology of spectrum tree. However, some users may belong to more

         than one spectrum tree and are recognized as overlapping users. Framework for STOP-RP is shown in Figure 3.

         In one spectrum tree, each node has a unique CR user identifier (CRID) that basically stipulates a proactive route to the root node. Accordingly, overlapping users will have multiple CRIDs, one for each spectrum tree. This protocol initializes with root selection procedure by sending out a Root Request. Once the root user is selected, a Root Announcement message is broadcast by the root node. Furthermore, STOP- RP presents CR routing as intra- spectrum routing and inter- spectrum routing where inter- spectrum happens to be in a single spectrum tree, whereas, intra-spectrum operates in multiple trees. To construct a route for end-to-end data transmission, STOP-RP exchanges two types of control messages: Spectrum Route REQuest (SRREQ) with fields: [CRIDS, CRIDD, metric, intra/inter] and Spectrum Route REPly (SRREP) with fields: [CRIDS, CRIDD, intra/inter], where, [CRIDS] and [CRIDD] are the CRIDs of source node and destination node, respectively, [metric] is the cumulative cognitive route cost and [intra/inter] indicates whether the destination and source nodes are in the same spectrum-tree or no.

         Fig 3: Framework for STOP-RP [10]

         The Spectrum-Tree based On-Demand Routing algorithm puts together tree-based proactive routing and on-demand route discovery that is an extension of original AODV protocol [7] for establishing route between source and destination nodes. Moreover, it provides a fa s t r o ut e – recovery method for effectively dealing with situations where a spectrum band being used by a Secondary user for transmission gets occupied by a Primary user. Ultimately, simulations have shown that STOP-RP has reduced end-to-end delay with increase in the number of nodes that belong to multiple spectrum trees and it has also lessen the control overhead.

      2. Cognitive Tree-based Routing (CTBR): CTBR [9] works as an extension of TBR (tree based routing) protocol proposed for wireless mesh networks. In CTBR protocol, each Cognitive Transceiver (CT) in CR environment maintains a routing table based on the tree structure, using which data packets are forwarded across the CR network.

         This routing solution uses global and local decision schemes for route calculation. A tree structured network is formed by configuring cognitive radio base-station as root node. As in TBR protocol, CTBR in cognitive network also performs the routing procedure, where, root node periodically sends Root Announcement (RANN) message for forming the tree. When a CT receives a RANN message, it caches the CT from whom it received this announcement message as its potential parent. Thereafter, the CT rebroadcasts the RANN with updated link metric. In addition to this, the CT also selects a parent CT from among all the potential parents based on the best metric for the path to root node. For registering with the root, each CT sends a RREP towards the root node when it hears the RANN message from its parent CT. An intermediate CT on receiving RREP, forwards this RREP message to its parent CT, and at the same time, updates its routing table by selecting source CT of the RREP as its destination node. Finally at the end, root node constructs a tree structure to reach any node in the network, as the root has now knowledge about all CTs.

   2. On Demand Based Routing

      This approach for routing in CRN is a modification of on demand routing protocols used in wireless ad hoc networks. In such protocols, a path is established only when an active communication is required. Following subsection describes two such routing protocols.

      1. Spectrum Aware On Demand Routing Protocol (SORP): SORP [6] is a modified form of ad hoc on demand distance vector (AODV) routing protocol to adapt in CR environment. Such modifications are needed in CRN because of the dynamics in spectrum availability. In SORP, modifications are made by inserting spectrum related information of CR users into control packets, such as RREQ and RREP, while they are being forwarded across the network. This scenario for routing in CRN assumes a common control channel (CCC) for the entire network to exchange control messages. For performing end- to-end data transmission, source node broadcasts a RREQ over the CCC. This RREQ will now have spectrum opportunity (SOP) of the source node piggybacked on it. However, each relay node on forwarding this RREQ appends its SOP on the RREQ. This continues until destination is reached, where, a spectrum band for data transfer is chosen from the received SOP. Thereafter, the destination assigns the spectrum and sends back a RREP along with a Choice list containing the selected spectrum band towards the source node, over the reverse path of RREQ. Likewise, the intermediate nodes assign the spectrum bands on forwarding the RREP. One such scenario is shown in Figure 4.

         Fig 4: Inclusion of SOP into RREQ and Choice list into RREP while they are forwarded [14]

         As such , on forwarding of RREQ and RREP messages, the size of the packets increases with agreement with the hop or with the distance between source and destination. Moreover, SORP defines cumulative delay caused by existing flows at a node as the sum of switching delay and backoff delay. Switching delay is caused by switching among frequency bands, whereas, backoff delay is caused by multi-flow interference within a frequency band. Since, SORP focuses on delays, it is suitable for delay-sensitive applications.

      2. Multi-hop Single-transceiver Cognitive Radio Networks Routing Protocol (MSCRP): MSCRP [5] uses on demand routing based on ad hoc on-demand distance vector(AODV) routing protocol. This scheme disallows the use of common control channel (CCC) [15] for exchanging control messages across the CR network. No node in the network is aware of the channel availability list of the other network nodes. As such, AODV needs to be modified so that spectrum related information can be exchanged among the nodes. Since, two nodes may be listening on different channels in CRN, they may not be able to communicate with each other. In order to avoid this problem, two consecutive nodes in a flow cannot be in the switching state simultaneously. As the communication with a switching node is difficult, therefore, the switching node uses LEAVE or JOIN messages to inform its neighbor nodes about its working channel.

         In MSCRP, route discovery is initiated by broadcasting RREQ message on all available channels of the sender node. The channel availability related information is piggybacked on RREQ message. An intermediate node on receiving a RREQ, appends its state and channel availability list to the RREQ message and thereafter forwards the RREQ.As the RREQ is forwarded among the nodes, a reverse path gets established from destination to the source node. When RREQ message reaches destination node, destination comes to know about channel availability list of every node on the path, and then, it assigns a channel for this flow. In response to RREQ, destination node sends back a RREP that includes the assigned channel, along the reverse path of RREQ to the source node. Hence, a path is set for end-to-end

         transmission of data packets. This approach is well suitable for multi-hop and single transceiver CRNs. However, it somewhat introduces extra overhead for broadcasting RREQ messages on all available channels instead on a single channel.

   3. Local Coordination Based Routing

      Local coordination based approach for routing in CRN is an extended work of SORP. It aims at providing good adaptability for handling situations that arise due to inconsistency in available spectrum bands.

      1) Local Coordination Based Routing and Spectrum Assignment in Multi-hop Cognitive Radio Networks: This approach [4] is a continuous work of SORP that involves a local coordination scheme to be applied on intersecting nodes to perform load balancing. Basically, this solution consists of two parts: a joint on-demand Routing and Spectrum Assignment Protocol for constructing a multi-hop path between source and destination nodes, and, a local coordination scheme for balancing the traffic load at intersecting nodes along the path in order to achieve minimal end-to-end delay. The proposed protocol looks for exchanging SOP information among the network nodes and assigning a suitable spectrum band to each link on the established route. The local coordination scheme, on the other hand, gets invoked at a node as soon as the node transforms into an intersecting node. This scheme allows the intersecting node to decide whether to accommodate the ongoing flow or to redirect it so as to distribute the workload among neighbor nodes.

      As shown in Figure 5, node A is serving flow 2 while

      another node B is serving flow 3.When a new flow 1 appears, it takes nodes A and B as its intermediate nodes. These two relay nodes perform a local coordination to identify its neighbors so as to redirect the flow appropriately. And as a result of this scheme, node A redirects flow 1 to node C whereas node B redirects flow 3 to node D.

      Fig 5: Local coordination scheme applied for load balancing [14]

      This functionality helps to reduce workload at the intermediate node by interacting with the neighbors. As such, this routing solution results in a path with low cumulative delay.

   4. Dynamic Spectrum Aware Routing

      Dynamic spectrum aware routing enables CR users to forward the data traffic through paths having high spectrum availability in an opportunistic way. One such routing protocol has been discussed in the following subsection.

      1) Spectrum Aware Mesh Routing in Cognitive Radio Net- works (SAMER): SAMER [11] is a routing solution for mesh networks in the CR environment where it allows the traffic to route along the paths having high spectrum availability so as to utilize the spectrum holes efficiently. This scheme uses a new routing metric based on the computation of spectrum availability of path. This new metric constructs a route that is optimal in terms of hop-count, thus, providing long-term stability routes. SAMER builds a runtime forwarding mesh through which the data packets are forwarded opportunistically. The constructed mesh is periodically updated according to the dynamics of spectrum availability and also it offers a set of candidate routes to the destination node.

      For building a mesh around the optimal hop-count path, a cost, given by Costi, is computed for each node i in the net- work. SAMER calculates all the routes from a node i to destination node D having length less than H hops and thereafter it selects the path with highest spectrum availability. As such, the computed cost represents the spectrum availability of a path from node i to node D whose length is at most H hops and also has the highest spectrum availability. However, it is a tough decision to look for the value of H that needs to be computed for estimating the cost. Ultimately, SAMER provides a balance between long-term route stability and short-tern opportunistic performance by carrying out data transmission across a mesh that is centered around the shortest hop-count path having highest spectrum availability. Hence, SAMER achieves high end-to-end throughput by utilizing long term stability and short term opportunistic spectrum access.

   5. Multipath Based Routing

   Multipath based routing protocols enable multiple paths to exist between source and destination nodes. They have the ability to reduce route discovery frequency and also provide load balancing to satisfy Q o S r e q u i r e m e n t s of CR users. Following subsection presents two such routing protocols.

   1. Multipath Routing and Spectrum Access (MRSA): MRSA[8] is the first multipath routing protocol for CR environment that aims at minimizing inter path contention and interference. In this approach, spectrum wise disjointness concept is revised, which specifies that, if multiple paths do not have any interfering bands between them than these paths are

      considered as spectrum wise disjoint. MRSA assumes that there are N bands for sending out data traffic in the spectrum. However, signaling traffic can also be delivered over these bands, but this requires broadcasting signaling traffic on all available bands because of which a separate band is being assumed for signaling traffic. The route discovery procedure of MRSA uses dynamic source routing (DSR)[13] mechanism according to which source node broadcasts a RREQ message with new RREQ ID and attaches its band radio usage table (BRT) to the message. An intermediate node on receiving RREQ checks whether the RREQ ID in the message is new or is an old one, before forwarding the RREQ. In case, RREQ ID is not new, the relay node counts the hop count from source node. If current RREQ has fewer hop count than the previous RREQ, the relay node appends its BRT to the message and then forwards the RREQ. Proceeding in this way, the destination node receives the same RREQ from multiple paths. Thus it first assigns band and radio to each link and then evaluates all the candidate paths by their available bandwidth. Hence, this routing technique p r o v i d e s e n d – to – e n d d a t a t r a n s m i s s i o n b y constructing multiple paths to minimize contention and interference and maximize spectrum wise disjointness.

   2. Ad Hoc On-Demand Multipath Distance Vector (AOMDV) Routing Protocol: AOMDV [12] protocol extended the ad hoc on-demand distance vector (AODV) routing protocol to calculate multiple loop-free and disjoint paths between source and destination. However, the main difference between AODV and AOMDV lies in the number of routes computed in each route discovery. When a RREQ is broadcast from source towards the destination, multiple reverse routes get established both at intermediate nodes as well as at destination node. In response to the RREQ, multiple RREPs traverse back along the reverse paths to the source node. Furthermore, this routing solution ensures that the multiple paths discovered are disjoint and loop-free by applying route update rules at each node locally. Figure 6 shows an example where source node S broadcasts a RREQ.

   Fig 6: Multipath between source and destination [12]

   Intermediate node I duplicates the first RREQ copy via node A and suppresses the second RREQ copy via node B.As such, two copies of the first RREQ copy via A reaches destination node D.D replies to both the RREQ

   copies even though reverse path is formed only via node X (assuming that the first copy reaches D via X earlier).Thereafter, two RREPs, one for each copy of RREQ, are sent by node D and they get merged at node I which forwards them along two disjoint paths (via A and B). As such, S obtains two link disjoint paths to D.

4. COMPARISON OF ROUTING PROTOCOLS IN CRN

   Table 1 presents a comparison among some of the routing solutions used in cognitive radio network. The table specifies category of the protocol to which in belongs, route discovery procedure initiated by the protocol and method applied by the protocol for selecting best route to perform end-to-end data transmission.

5. CONCLUSION

This survey paper presents a number of routing proto- cols used in ad hoc cognitive radio networks with their efficiency. However, routing in CRN in a challenging issue because of the dynamics in spectrum availability of CR users.Therefore, routing in CRN has attracted a lot of attention in recent years as a result of which, researchers all around the world are focusing to introduce some novel routing solutions for CR environment. Our paper has analyzed some of the routing protocols in CRN by classifying them into tree based protocols, on demand based protocols, local coordination based protocols, dynamic spectrum aware based protocols and multipath based protocols.

Table 1: Comparison of routing protocols in CRN

We have also summarized the routing operations related to the protocols we presented. Looking at existing works and discussions on routing protocols in CRN, it can be stated that most of these protocols use the same routing metric as used in traditional wireless networks. As such, there is a need to design new routing metric that can exploit all dynamic characteristics of CRN. Therefore, it is believed that by analyzing the existing routing techniques used in CR network, various new open issue could be exposed and also some novel routing solutions could be developed by enhancing the current routing schemes.

REFERENCES

1. IF Akyildiz, WY Lee, MC Vuran, M Shantidev, NeXt genera- tion/dynamic spectrum access/cognitive radio wireless networks: a survey. Computer Networks 50(13), 21272159 (2006)

2. FCC, ET Docket No 03-222 Notice of proposed rule m a k i n g and order, December 2003.

3. M Cesana, F Cuomo, E Ekici, Routing in cognitive radio networks: challenges and solutions. Ad Hoc Networks, 9(3), 228248 (2011)

4. Z Yang, G Cheng, W Liu, W Yuan, W Cheng, Local coordination based routing and spectrum assignment in multi- hop cognitive radio networks. Mobile Network. Appl. 13, 6781 (2008). [16] B. Zhang, Y. Takizawa, A.

5. Ma, H. and Zheng, L. and Ma, X. and Luo, Spectrum- aware routing for multi-hop cognitive radio networks with a single transceiver, Proceedings of the Cognitive Radio Oriented Wireless Networks and Communications (CrownCom) 2008.

6. Cheng, G. and Liu, W. and Li, Y. and Cheng, Spectrum aware on-demand routing in cognitive radio networks, 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, 2007. DySPAN 2007.pp.571574.

7. C. E. Perkins and E. M. Royer, Ad hoc on-demand distance vector routing, in Proc. of IEEE Workshop on Mobile Computing Systems and Applications, 1999.

8. Wang, X. and Kwon, T.T. and Choi, A multipath routing and spectrum access (MRSA) framework for cognitive radio systems in multi-radio mesh networks, Proceedings of the 2009 ACM workshop on Cognitive radio networks 2009.

9. B. Zhang, Y. Takizawa, A. Hasagawa, A. Yamauchi, and S. Obana, Tree-based routing protocol for cognitive wireless access networks, in Proc. of IEEE Wireless Communications and Networking Conference 2007.

10. G-M. Zhu, I. F Akyildiz, and G-S. Kuo, STOD-RP: A spectrum tree based on-demand routing protocol for multi hop cognitive radio networks, in Proc. IEEE Globecom, November-December 2008.

11. I. Pefkianakis, S. H. Y. Wong, S. Lu, SAMER: Spectrum aware mesh routing in cognitive radio networks, in Proc. IEEE DySPAN, October 2008.

12. M. K. Marina, S. R. Das, AOMDV: Ad hoc on-demand multipath distance vector routing, in Wireless Communication Mobile Computing. 2006.

13. D Johnson, Y Hu, D Maltz, The dynamic source routing protocol (DSR) for mobile ad hoc networks for Ipv4. (IETF RFC 4728, 2007). http://www.ietf.org/rfc/rfc4728.txt. Accessed

    24 January 2011.

14. S. Salim, S. Moh, On-demand routing protocols for cognitive radio ad hoc networks, in EURASIP Journal on Wireless Communications and Networking, 2013.

15. B. F. Lo, A survey of common control channel design in cognitive radio networks, Physical Communication 4 (2011).