A graph based routing algorithm for multi-hop cognitive radio networks

ABSTRACT

Cognitive radio networks that allow dynamic spectrum access are considered spectrally more efficient than networks using fixed spectral allocation. These networks are characterized by dynamically changing channel sets at each node. The graph theoretic approach used in traditional multi-hop networks fails to efficiently model multi-hop cognitive radio networks and capture the required information for optimal routing. Hence, conventional graph-based routing protocols such as DSR or AODV cannot be used directly, for route discovery in such networks. In this paper, a unique multi-edge planar graph model for routing in such type of networks is proposed, which is quite simple and could be used in conjunction with any conventional graph-based routing protocol. The model is validated through simulations and the complexity of the model is shown to be lesser than an earlier layered graph model.

REFERENCES

• 1: Q. Zhao, B. M. Sadler, "A Survey of Dynamic Spectrum Access: Signal Processing, Networking, and Regulatory Policy", IEEE Signal Processing Magazine, May, 2007.
• 2: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 3: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 4: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 5: Pradeep Kyasanur, Nitin H. Vaidya, "Protocol Design Challenges for Multi-hop Dynamic spectrum Access Networks", Proc. IEEE DySPAN 2005, November 2005, pp. 645--648.
• 6: Chunsheng Xin, Bo Xie, Chien-Chung Shen, "A novel layered graph model for dynamic spectrum access networks", Proc. IEEE DySPAN 2005, November 2005, pp. 308--317.
• 7: Bing Qi , Saâd Biaz , Shaoen Wu , Yiming Ji, An interference-aware routing metric in multi-radio multi-hop networks, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina [doi>10.1145/1233341.1233457]
• 8: L. De Nardis and M.-G. Di Benedetto, "Cognitive routing in UWB networks", invited paper at the IEEE International Conference on UWB 2006 (ICUWB2006), September 24--27 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Standardization, Verification

Keywords:
cognitive radio networks, multiple edge graph, routing