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

Hao Chen, Qinghe Du, Pinyi Ren


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.


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

Full Text:



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.

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

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.

DOI: https://doi.org/10.15837/ijccc.2012.3.1383

Copyright (c) 2017 Hao Chen, Qinghe Du, Pinyi Ren

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

IJCCC is an Open Access Journal : CC-BY-NC.

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]

INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.


 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2);

SCImago Journal & Country Rank

Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.