A Joint Routing and Time-Slot Assignment Algorithm for Multi-Hop Cognitive Radio Networks with Primary-User Protection


  • Hao Chen 1. Department of Information and Communication Engineering, Xi’an Jiaotong University, Xi’an, Shaanxi,710049, China 2. State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an, Shaanxi, 710071, China
  • Qinghe Du Department of Information and Communication Engineering, Xi’an Jiaotong University, Xi’an, Shaanxi,710049, China
  • Pinyi Ren Department of Information and Communication Engineering, Xi’an Jiaotong University, Xi’an, Shaanxi,710049, China


Cognitive Radio Networks, Primary-user Protection, Joint Routing and Time-slot Assignment


Cognitive radio has recently emerged as a promising technology to improve the utilization efficiency of the radio spectrum. In cognitive radio networks, secondary users (SUs) must avoid causing any harmful interference to primary users (PUs) and transparently utilize the licensed spectrum bands. In this paper, we study the PUprotection issue in multi-hop cognitive radio networks. In such networks, secondary users carefully select paths and time slots to reduce the interference to PUs. We formulate the routing and time-slot assignment problem into a mixed integer linear programming (MILP). To solve the MILP which is NP-Hard in general, we propose an algorithm named RSAA (Routing and Slot Assignment Algorithm). By relaxing the integral constraints of the MILP, RSAA first solves the max flow from the source to the destination. Based on the max flow, RSAA constructs a new network topology. On the new topology, RSAA uses branch and bound method to get the near optimal assignment of time slots and paths. The theoretical analyses show that the complexity of our proposed algorithm is O(N^4). Also, simulation results demonstrate that our proposed algorithm can obtain near-optimal throughputs for SUs.


FCC, ET Docket No 03-222 Notice of proposed rule makingand order, December 2003.

J. Mitra III and G. Q. Maguire JR., "Cognitive radio: making software radios more personal," IEEE ersonal Commun., pp. 13-18, Aug. 1999.

I. Akyildiz,W. Lee, M. Vuran, and S. Mohanty. "NeXt Generation / Dynamic Spectrum Access/Cognitive adio Wireless Networks: A Survey." Compo Netw. Jour. (Elsevier), Vol.50, no.13, pp. 2127- 159, Sept. 2006. http://dx.doi.org/10.1016/j.comnet.2006.05.001

T. Yucek, H. Arslan, "A survey of spectrum sensing algorithms for cognitive radio applications," ommunications Surveys & Tutorials, IEEE, vol.11, no.1, pp.116-130, First Quarter 2009.

H.Wang, H. Qin, L. Zhu, "A Survey onMAC Protocols for Opportunistic Spectrum Access in Cognitive adio Networks," Computer Science and Software Engineering, 2008 International Conference n, vol.1, no., pp.214-218, 12-14 Dec. 2008

Y. Wang, P. Ren, and G. Wu, "A throughput-aimed MAC protocol with QoS provision for cognitive d hoc networks," IEICE Trans. Commun., vol. E93-B, no. 6, pp. 1426-1429, Jun. 2010.

H. Khalife, N. Malouch, S. Fdida, "Multihop cognitive radio networks: to route or not to route," etwork, IEEE, vol.23, no.4, pp.20-25, July-August 2009

M. Ceasna, F. Cuomo, E. Ekici, "Routing in cognitive radio networks: Challenges and solutions", d Hoc Netw., Vol. 9, no. 3, pp.228-248, May 2011

X. Zhou, L. Lin, J. Wang and X. Zhang, "Cross-layer routing design in cognitive radio networks by olored multigraph model," Wireless Personal Communications, vol. 49, no.1, pp. 123-131, April 009

Y.T. Hou, Y. Shi, H.D. Sherali, "Optimal Spectrum Sharing for Multi-Hop Software Defined Radio etworks," INFOCOM 2007. 26th IEEE International Conference on Computer Communications. EEE, vol., no., pp.1-9, 6-12, May 2007

Y.T. Hou, Y. Shi, H.D. Sherali, "Spectrum Sharing for Multi-Hop Networking with Cognitive Radios," elected Areas in Communications, IEEE Journal on, vol.26, no.1, pp.146-155, Jan. 2008

I. Filippini, E. Ekici, M. Cesana, "Minimum maintenance cost routing in Cognitive Radio Networks," obile Adhoc and Sensor Systems, 2009. MASS '09. IEEE 6th International Conference n, vol., no., pp.284-293, 12-15 Oct. 2009

K.R. Chowdhury, I.F. Akyildiz, "CRP: A Routing Protocol for Cognitive Radio Ad Hoc Networks," elected Areas in Communications, IEEE Journal on, vol.29, no.4, pp.794-804, April 2011

L. Ding, T. Melodia, S.N. Batalama, J.D. Matyjas, M.J. Medley, "Cross-Layer Routing and Dynamic pectrum Allocation in Cognitive Radio Ad Hoc Networks," Vehicular Technology, IEEE ransactions on, vol.59, no.4, pp.1969-1979, May 2010

M. Xie,W. Zhang, K.K.Wong, "A geometric approach to improve spectrum efficiency for cognitive elay networks,"Wireless Communications, IEEE Transactions on, vol.9, no.1, pp.268-281, January 010

Z. Yuan, J. B. Song, Z. Han, "Interference Minimization Routing and Scheduling in Cognitive adio Wireless Mesh Networks," Wireless Communications and Networking Conference (WCNC), 010 IEEE, vol., no., pp.1-6, 18-21 April 2010

P. Gupta, P.R. Kumar, "The capacity of wireless networks," InformationTheory, IEEE Transactions n, vol.46, no.2, pp.388-404, Mar 2000.

K. Jain, J. Padhye, V.N. Padmanabhan, L. Qiu, "Impact of Interference on Multi-Hop Wireless etwork Performance", Wireless Networks, Vol 11, no 4, pp. 471-487, July 2005 http://dx.doi.org/10.1007/s11276-005-1769-9

H.D. Sherali,W.P. Adams, P.J. Driscoll, "Exploiting Special Structures in Constructing a Hierarchy f Relaxations for 0-1 Mixed Integer Problems", Operations Research, Vol.46, no.3, pp.396-405, ay 1998

S. Gao. Graph Theory and Network Flow Theory, 1rd ed., BeiJing: Higher Education Press, 2009, p.307-314

P. Erdfs and A. Renyi, "On the evolution of random graphs", PubI. Math. Inst. Hung. Acad. Sci. 5, 960, pp.17-61.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.