This article has been accepted for inclusion in a future issue of this joural.Content is final as presented,with the exception of pagination IEEE/ACM TRANSACTIONS ON NETWORKING Capacity Scaling of General Cognitive Networks Wentao Huang and Xinbing Wang,Member,IEEE Abstract-There has been recent interest within the networking are able to sense and adapt to their spectral environment,such as research community to understand how performance scales in cog- cognitive radios,to become secondary or cognitive users.Cog- nitive networks with overlapping n primary nodes and m sec- nitive users could opportunistically access the spectrum origi- ondary nodes.Two important metrics,i.e.,throughput and delay, are studied in this paper.We first propose a simple and extendable nally licensed to primary users in a manner in which their trans- decision model,i.e.,the hybrid protocol model,for the secondary missions will not affect the performance of primary users.Pri- nodes to exploit spatial gap among primary transmissions for fre- mary users have a higher priority to the spectrum;they may be quency reuse.Then,a framework for general cognitive networks legacy devices and may not cooperate with secondary users.The is established based on the hybrid protocol model to analyze the occurrence of transmission opportunities for secondary nodes.We overlapping primary network and secondary network together show that if the primary network operates in a generalized TDMA form the cognitive network. fashion,or employs a routing scheme such that traffic flows choose This paper focuses on the performance scaling analysis of relays independently,then the hybrid protocol model suffices to cognitive networks with an increasing number of n primary guide the secondary network to achieve the same throughput and users and m secondary users.The fundamental scaling laws in delay scaling as a standalone network without harming the per- ad hoc networks has attracted tremendous interest in the net- formance of the primary network,as long as the secondary trans- mission range is smaller than the primary range in order.Our ap- working community for long.This track of research is initi- proach is general in the sense that we only make a few weak as- ated by Gupta and Kumar,whose landmark work [4]showed sumptions on both networks,and therefore it obtains a wide variety that generally the per-node throughput capacity of a wireless ad of results.We show secondary networks can obtain the same order hoc network with n users only scales as O(1/vn).1 Following of throughput and delay as standalone networks when primary works have covered a wide variety of ad hoc networks with dif- networks are classic static networks,networks with random walk ferent features,such as mobile ad hoc networks (MANETs)[5]. mobility,hybrid networks,multicast networks,CSMA networks, networks with general mobility,or clustered networks.Our work hybrid networks [6].[7],multicast networks [8],[9],hierarchi- presents a relatively complete picture of the performance scaling cally cooperative networks [10],clustered networks [11],[12], of cognitive networks and provides fundamental insight on the de- etc.Performance metrics other than capacity are also studied, sign of them. among which delay and its optimal tradeoff with throughput are Index Terms-Capacity,cognitive. of critical importance 13],[14]. As with most related works,under the Gaussian channel model,Jeon et al.[15]considered the capacity scaling of a I.INTRODUCTION cognitive network where the number of secondary users,m,is larger thann in order.Under a similar assumption,Yin et al.[16] HE ELECTROMAGNETIC radio spectrum is a natural developed the throughput-delay tradeoff of both primary and resource,the use of which by transmitters and receivers secondary networks,and Wang et al.[17]studied the cases of is licensed by governments.Today,as wireless applications de- multicast traffic pattern.Interestingly,all these works showed mand ever more bandwidth,efficient usage of spectrum is be- that both primary and secondary networks can achieve similar coming necessary.However,recent measurement [2]observed or same performance bounds as they are standalone networks. a severe underutilization of the licensed spectrum,implying the All previous works on cognitive networks [15]-[17]consid- nonoptimality of the current scheme of spectra management.As ered some particular scenarios.Typically,they first assumed a remedy,the Federal Communications Commission(FCC)has some particular primary networks with specific scheduling recently recommended [2],[3]more flexibility in spectrum as- and routing protocols,then proposed the communication signment so that new regulations would allow for devices that schemes for secondary users accordingly,and lastly showed such schemes suffice to achieve the same performance bounds as standalone networks.However,a key principle of cognitive Manuscript received August 24.2011;revised December 05,2011;accepted networks is that primary users are spectrum license holders and December 10,2011;approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor A.Capone.This work was supported by National Fundamental Research may operate at their own will without considering secondary Grant 2011CB302701.NSF China under Grant 60832005,the China Ministry nodes.Therefore,though assuming a specific primary network of Education New Century Excellent Talent under Grant NCET-10-0580,the China Ministry of Education Fok Ying Tung Fund under Grant 122002,a Qual- can simplify the problem,the results will heavily depend on comm Research Grant,the Shanghai Basic Research Key Project under Grant the communication schemes of the primary network,which is 11JC1405100,and National Key Project of China under Grant 2010ZX03003- often unmanageable. 001-01.An earlier version of this paper appeared in the Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Recall that:1)f(n)=O(g(n))means that there exists a constant c and Shanghai,China,April 10-15,2011. integer N such that f(n)<cg(n)for n>N:2)f(n)=o(g(n))means that The authors are with Department of Electronic Engineering,Shanghai Jiao limnoof(n)/g(n)=0;3)f(n)=(g(n))means that g(n)=o(f(n)): Tong University,Shanghai 200240,China (e-mail:yelohuang@sjtu.edu.cn; 4)f(n)=w(g(n))means that g(n)=o(f(n)):5)f(n)=e(g(n))means xwang8@sjtu.edu.cn). that f(n=o(g(n)))and g(n)=o(f(n)). Digital Object Identifier 10.1109/TNET.2011.2180400 1063-6692/$26.00©2011EEEThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING 1 Capacity Scaling of General Cognitive Networks Wentao Huang and Xinbing Wang, Member, IEEE Abstract—There has been recent interest within the networking research community to understand how performance scales in cog￾nitive networks with overlapping primary nodes and sec￾ondary nodes. Two important metrics, i.e., throughput and delay, are studied in this paper. We first propose a simple and extendable decision model, i.e., the hybrid protocol model, for the secondary nodes to exploit spatial gap among primary transmissions for fre￾quency reuse. Then, a framework for general cognitive networks is established based on the hybrid protocol model to analyze the occurrence of transmission opportunities for secondary nodes. We show that if the primary network operates in a generalized TDMA fashion, or employs a routing scheme such that traffic flows choose relays independently, then the hybrid protocol model suffices to guide the secondary network to achieve the same throughput and delay scaling as a standalone network without harming the per￾formance of the primary network, as long as the secondary trans￾mission range is smaller than the primary range in order. Our ap￾proach is general in the sense that we only make a few weak as￾sumptions on both networks, and therefore it obtains a wide variety of results. We show secondary networks can obtain the same order of throughput and delay as standalone networks when primary networks are classic static networks, networks with random walk mobility, hybrid networks, multicast networks, CSMA networks, networks with general mobility, or clustered networks. Our work presents a relatively complete picture of the performance scaling of cognitive networks and provides fundamental insight on the de￾sign of them. Index Terms— Capacity, cognitive. I. INTRODUCTION T HE ELECTROMAGNETIC radio spectrum is a natural resource, the use of which by transmitters and receivers is licensed by governments. Today, as wireless applications de￾mand ever more bandwidth, efficient usage of spectrum is be￾coming necessary. However, recent measurement [2] observed a severe underutilization of the licensed spectrum, implying the nonoptimality of the current scheme of spectra management. As a remedy, the Federal Communications Commission (FCC) has recently recommended [2], [3] more flexibility in spectrum as￾signment so that new regulations would allow for devices that Manuscript received August 24, 2011; revised December 05, 2011; accepted December 10, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor A. Capone. This work was supported by National Fundamental Research Grant 2011CB302701, NSF China under Grant 60832005, the China Ministry of Education New Century Excellent Talent under Grant NCET-10-0580, the China Ministry of Education Fok Ying Tung Fund under Grant 122002, a Qual￾comm Research Grant, the Shanghai Basic Research Key Project under Grant 11JC1405100, and National Key Project of China under Grant 2010ZX03003- 001-01. An earlier version of this paper appeared in the Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Shanghai, China, April 10–15, 2011. The authors are with Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200240, China (e-mail: yelohuang@sjtu.edu.cn; xwang8@sjtu.edu.cn). Digital Object Identifier 10.1109/TNET.2011.2180400 are able to sense and adapt to their spectral environment, such as cognitive radios, to become secondary or cognitive users. Cog￾nitive users could opportunistically access the spectrum origi￾nally licensed to primary users in a manner in which their trans￾missions will not affect the performance of primary users. Pri￾mary users have a higher priority to the spectrum; they may be legacy devices and may not cooperate with secondary users. The overlapping primary network and secondary network together form the cognitive network. This paper focuses on the performance scaling analysis of cognitive networks with an increasing number of primary users and secondary users. The fundamental scaling laws in ad hoc networks has attracted tremendous interest in the net￾working community for long. This track of research is initi￾ated by Gupta and Kumar, whose landmark work [4] showed that generally the per-node throughput capacity of a wireless ad hoc network with users only scales as .1 Following works have covered a wide variety of ad hoc networks with dif￾ferent features, such as mobile ad hoc networks (MANETs) [5], hybrid networks [6], [7], multicast networks [8], [9], hierarchi￾cally cooperative networks [10], clustered networks [11], [12], etc. Performance metrics other than capacity are also studied, among which delay and its optimal tradeoff with throughput are of critical importance [13], [14]. As with most related works, under the Gaussian channel model, Jeon et al. [15] considered the capacity scaling of a cognitive network where the number of secondary users, , is larger than in order. Under a similar assumption, Yin et al. [16] developed the throughput–delay tradeoff of both primary and secondary networks, and Wang et al. [17] studied the cases of multicast traffic pattern. Interestingly, all these works showed that both primary and secondary networks can achieve similar or same performance bounds as they are standalone networks. All previous works on cognitive networks [15]–[17] consid￾ered some particular scenarios. Typically, they first assumed some particular primary networks with specific scheduling and routing protocols, then proposed the communication schemes for secondary users accordingly, and lastly showed such schemes suffice to achieve the same performance bounds as standalone networks. However, a key principle of cognitive networks is that primary users are spectrum license holders and may operate at their own will without considering secondary nodes. Therefore, though assuming a specific primary network can simplify the problem, the results will heavily depend on the communication schemes of the primary network, which is often unmanageable. 1Recall that: 1) ￾￾ ￾￾ means that there exists a constant  and integer  such that ￾￾ ￾ ￾ for ; 2) ￾￾ ￾￾ means that  ￾￾ ￾; 3) ￾￾ ￾￾ means that ￾ ￾￾￾; 4) ￾￾ ￾￾ means that ￾ ￾￾ ￾; 5) ￾￾ ￾￾ means that ￾￾ ￾￾ and ￾ ￾￾￾. 1063-6692/$26.00 © 2011 IEEE