Capacity Scaling of General Cognitive Networks

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©2011EEE

This 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

This 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 That motivates us to study a general cognitive network in TABLE I this paper.Our major contributions are threefold.First,we IMPORTANT NOTATIONS characterize the regime that cognitive networks can achieve Notation Definition the same order of throughput and delay scaling as standalone position of primary user i position of secondary user networks.Second,we propose a simple decision model for (a,) feasible family of physical model secondary users to identify transmission opportunities and, (a+e) feasible family of primary scheduler based on it,establish a framework with which schemes of 2p(△p,2s(△e) feasible family of protocol model ,f(△p△p△sp,△） feasible family of hybrid protocol standalone networks can be readily extended to secondary model networks.Third,we apply the framework to various specific S(p) set of active primary links scenarios and show that secondary networks can obtain the S() set of active secondary links S(p)US(s) same order of throughput and delay as standalone networks Ri Tx range of active link (Xi.XRx( when primary networks are classic static networks,networks Tx range of active link (Yj.YRx()) with random walk mobility,hybrid networks,multicast net- Tx power of primary network P Tx power of link (Y3,YRx() works,CSMA networks,networks with general mobility,or clustered networks. In particular,when all of the following three conditions hold, protocol model.We apply the general results to several specific it is sufficient for a general cognitive network to achieve the cognitive networks in Section VI.and Section VII concludes the same throughput and delay bounds as standalone networks. paper. A1)The cognitive network is subject to the physical in- IⅡ.SYSTEM MODEL terference model.The primary network operates at a signal-to-interference-plus-noise ratio (SINR)level Throughout this paper,we denote the probability of event E larger than the threshold for successful reception by as Pr(E)and say E happens with high probability (w.h.p.)if some small allowance. limnoo Pr(E)=1.By convention,fci}denotes positive con- A2)The primary network is scheduled in a generalized stants,and [Ci(n)}parameters dependent onn.Other notations round-robin TDMA manner,or traffic flows of the pri- are defined in Table I. mary network choose relays independently for routing. A.Network Topology A3)Scheduling schemes of the secondary network follow Tmax(m)=o(Rmin(n))and =o(Rin/RTax) We define the network extension to be a unit square.Two with high probability,where R(n)and r(m)are the kinds of nodes,i.e.,the primary nodes and the secondary nodes. transmission ranges of primary and secondary networks, overlap in O.They share the same time,space,and frequency and y is the path loss exponent. dimensions.Unless further specifications are made,by conven- Intuitively,condition Al ensures that primary transmission tion we assume n primary nodes are independently and identi- links are neither too dense nor too vulnerable so that there exist cally distributed (i.i.d.)in O according to uniform distribution, opportunities for secondary users.Such opportunities will fre- and so do the m secondary users.Notice that different from pre- quently appear,as a consequence of A2.The first equation of vious related works that require n=o(m),i.e.,the primary A3 is the generalization of the condition m =w(n)in related user density is asymptotically smaller than the secondary user works,while the second equation is more technical.It char- density,we allow the relation between m and n to be arbitrary acterizes the case that the scheduling of primary networks is Their positions are andVi.j.YO. somewhat"homogeneous"such that there exists a simple rule At times we may denote a node by its position,i.e.,we refer for opportunity decision.Al is based on the physical interfer- to primary node i and secondary node j as Xi and Yi,and let ence model,and similar results hold under the Gaussian channel Xi-Yil be the distance between them.Two types of nodes model. form their respective networks,the primary network and the sec- We note this paper is not merely a generalization of results ondary network.In each network,nodes are randomly grouped from previous works.Our work shows the fact that cognitive into source-destination(S-D)pairs,such that every node is both networks,and especially secondary networks,can achieve the source and destination,with traffic rate A.Equivalently,we can same throughput and delay scaling as standalone networks is describe the traffic pattern in matrix form AA,where A=[Ad] mainly determined by the underlying interference model,and it is a random permutation matrix2 with Asd E[0,1}.Note that only weakly relies on the specific settings such as scheduling we do not consider cross-network traffic.We use index p and s and routing protocols of primary networks.Such insight is fun- to distinguish quantities between primary nodes and secondary damental and implies that for quite general cases,"cognitive" nodes when needed,.for example,.入pandλs. will not be a handicap to performance scaling. B.Communication Model This paper is organized as follows.In Section II,we intro- duce system models and formalize the operation rules of cog- We assume all nodes share a wireless channel with band- nitive networks,and Section III presents an overview of our width W b/s.Assume that path loss exponent is >2,then solution.We propose the hybrid protocol model and establish its the normalized channel gain between a transmitter at location physical feasibility in Section IV.Section V identifies the con- Zr and a receiver at Zr is G(IZr -ZR)=Zr -ZR-Y. ditions under which the secondary network will have plenty of transmission opportunities if scheduled according to the hybrid 1:(=1 2三【fis a permutation matrix if(gfsd）由al:(gafa=

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 2 IEEE/ACM TRANSACTIONS ON NETWORKING That motivates us to study a general cognitive network in this paper. Our major contributions are threefold. First, we characterize the regime that cognitive networks can achieve the same order of throughput and delay scaling as standalone networks. Second, we propose a simple decision model for secondary users to identify transmission opportunities and, based on it, establish a framework with which schemes of standalone networks can be readily extended to secondary networks. Third, we apply the framework to various specific scenarios and show that 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 net￾works, CSMA networks, networks with general mobility, or clustered networks. In particular, when all of the following three conditions hold, it is sufficient for a general cognitive network to achieve the same throughput and delay bounds as standalone networks. A1) The cognitive network is subject to the physical in￾terference model. The primary network operates at a signal-to-interference-plus-noise ratio (SINR) level larger than the threshold for successful reception by some small allowance. A2) The primary network is scheduled in a generalized round-robin TDMA manner, or traffic flows of the pri￾mary network choose relays independently for routing. A3) Scheduling schemes of the secondary network follow and with high probability, where and are the transmission ranges of primary and secondary networks, and is the path loss exponent. Intuitively, condition A1 ensures that primary transmission links are neither too dense nor too vulnerable so that there exist opportunities for secondary users. Such opportunities will fre￾quently appear, as a consequence of A2. The first equation of A3 is the generalization of the condition in related works, while the second equation is more technical. It char￾acterizes the case that the scheduling of primary networks is somewhat “homogeneous” such that there exists a simple rule for opportunity decision. A1 is based on the physical interfer￾ence model, and similar results hold under the Gaussian channel model. We note this paper is not merely a generalization of results from previous works. Our work shows the fact that cognitive networks, and especially secondary networks, can achieve the same throughput and delay scaling as standalone networks is mainly determined by the underlying interference model, and it only weakly relies on the specific settings such as scheduling and routing protocols of primary networks. Such insight is fun￾damental and implies that for quite general cases, “cognitive” will not be a handicap to performance scaling. This paper is organized as follows. In Section II, we intro￾duce system models and formalize the operation rules of cog￾nitive networks, and Section III presents an overview of our solution. We propose the hybrid protocol model and establish its physical feasibility in Section IV. Section V identifies the con￾ditions under which the secondary network will have plenty of transmission opportunities if scheduled according to the hybrid TABLE I IMPORTANT NOTATIONS protocol model. We apply the general results to several specific cognitive networks in Section VI, and Section VII concludes the paper. II. SYSTEM MODEL Throughout this paper, we denote the probability of event as and say happens with high probability (w.h.p.) if . By convention, denotes positive con￾stants, and parameters dependent on . Other notations are defined in Table I. A. Network Topology We define the network extension to be a unit square. Two kinds of nodes, i.e., the primary nodes and the secondary nodes, overlap in . They share the same time, space, and frequency dimensions. Unless further specifications are made, by conven￾tion we assume primary nodes are independently and identi￾cally distributed (i.i.d.) in according to uniform distribution, and so do the secondary users. Notice that different from pre￾vious related works that require , i.e., the primary user density is asymptotically smaller than the secondary user density, we allow the relation between and to be arbitrary. Their positions are and . , , , . At times we may denote a node by its position, i.e., we refer to primary node and secondary node as and , and let be the distance between them. Two types of nodes form their respective networks, the primary network and the sec￾ondary network. In each network, nodes are randomly grouped into source–destination (S–D) pairs, such that every node is both source and destination, with traffic rate . Equivalently, we can describe the traffic pattern in matrix form , where is a random permutation matrix2 with . Note that we do not consider cross-network traffic. We use index and to distinguish quantities between primary nodes and secondary nodes when needed, for example, and . B. Communication Model We assume all nodes share a wireless channel with band￾width b/s. Assume that path loss exponent is , then the normalized channel gain between a transmitter at location and a receiver at is . 2￾￾  is a permutation matrix if ￾  ￾   ￾ ￾  ￾ ￾ 

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination HUANG AND WANG:CAPACITY SCALING OF GENERAL COGNITIVE NETWORKS Moreover,wireless transmission may be subject to failures or Operartion Rule 1:Decision model for the primary network: collisions caused by noise or interference.To judge whether a The primary scheduler considers the transmission from X;to direct wireless link is feasible,we have the following physical Xi to be feasible if model,whose well-known prototype is proposed in [4] Physical Model:Let{Xi;i∈T(p)}and{Y;j∈Ts}be PG (Xi-Xi) the subsets of nodes simultaneously transmitting at some time N+∑0PG0K-XD≥+6 instant.Let P be the uniform power level of primary network, and Pi be the power chosen by secondary node Yi,for jT(s). The feasible family of the primary decision model is denoted as Then,for the primary network,the transmission from node Xi (a+E). is successfully received by node Xi if Then,as the operation rule,secondary nodes should guar- antee that the feasible state under the decision model above PG(Xi-Xi) should be indeed feasible under the physical model. N+∑ke7 PNiPG(IX&--XD+2 eToPG0m-XD≥a Operation Rule 2:Decision model for the secondary net- (1) work:Let S(p)and S(s)be the sets of active primary links and where N is ambient noise and constant a characterizes the active secondary links.If S()(a+e),then S(p)US()E minimum SINR necessary for successful receptions for pri- 乎(a,3),w.hp. mary nodes.For the secondary network,the transmission from Note that compared to most existing related literatures where node Yi is successfully received by node Yi if the concept of user priority is usually scheme-or network-spe- cific,Operation Rules 1 and 2 formally define the principle of PG (Yi-Yil) cognitive behaviors in a general sense. N+erva BG(-yD+,∑PGx-yT之B kET()\{} L∈T(P) D.Capacity Definition where constant B is the minimum required SINR for secondary Definition I:Feasible throughput:Per-node throughput g(n) network.Note that we allow secondary users to have more flex- of the primary network is said to be feasible if there exists a ible power control ability.This is in accord with the design prin- spatial and temporal scheme for scheduling transmissions,such ciple of cognitive radios that by operating the primary network in a multihop fashion and We call a couple of nodes a link if they form a transmitter-re- buffering at intermediate nodes when awaiting transmission op- ceiver pair,e.g.,(Xi,Xi).Given an interference model,in gen- portunities,every primary source can send g(n)b/s to its desti- eral there is a number of subsets of links that can be active si- nation on average. multaneously.We call such subsets of links feasible states,and Definition 2:Asymptotic per-node capacity Xp(n)of the pri- define the set of all feasible states as feasible family.We use mary network is said to be (g(n))if there exist two positive ()to denote the feasible family of the physical model. constants c and c such that limn→ooPr{λp(n)=cg(n)is feasible}=l C.Operation Rules limnoo Pr (p(n)=cg(n)is feasible}<1. The essential differences between cognitive networks and Similarly,we can define the asymptotic per-node capacity normal ad hoc networks are the operation rules.Though A(m)for the secondary network. primary and secondary users overlap and share the channel, they are different essentially because of their behavior.In principle,primary nodes are spectrum license holders and III.OVERVIEW OF IDEA AND SOLUTION have the priority to access the channel.It is followed by two important implications.First,primary nodes may operate at Our system model begins with a very classical setup,where the network topology,node communication capabilities,and their own will without considering secondary nodes.They may be legacy devices running on legacy protocols,which are fixed performance metrics fall in the same framework that is most commonly deployed in related works on asymptotic analysis of and unmanageable.Therefore,the assumptions made about wireless networks.An extensive body of literature [4]-[14]has primary networks should be as few and general as possible. investigated various specific networks under this framework. Moreover,the secondary network,which is opportunistic in For that matter,the key issue that we aim to address in this paper nature,should control its interference to the primary network is how the cognitive principles,i.e.,Operation Rules 1 and 2, and prevent deteriorating the performance of primary users. may impact network performance,especially with respect to the The challenge is that the primary scheduler may not alter its abundant insights already gained in previous works on asymp- protocol due to the existence of the secondary network,and its totic network capacity and delay. decision model could be different from the physical model (1), Clearly this is a nontrivial problem:Operation Rules 1 and 2 i.e.,the interference term from the secondary network in the have introduced fundamental heterogeneities into the network denominator is not available.However,in order to leave some in the sense that nodes now have different levels of priority. margin for secondary nodes,it is necessary for the decision Such heterogeneities are exactly the most essential idea of how model to operate at an SINR larger than a by an allowance e. cognitive networks operate

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. HUANG AND WANG: CAPACITY SCALING OF GENERAL COGNITIVE NETWORKS 3 Moreover, wireless transmission may be subject to failures or collisions caused by noise or interference. To judge whether a direct wireless link is feasible, we have the following physical model, whose well-known prototype is proposed in [4] Physical Model: Let and be the subsets of nodes simultaneously transmitting at some time instant. Let be the uniform power level of primary network, and be the power chosen by secondary node , for . Then, for the primary network, the transmission from node is successfully received by node if (1) where is ambient noise and constant characterizes the minimum SINR necessary for successful receptions for pri￾mary nodes. For the secondary network, the transmission from node is successfully received by node if where constant is the minimum required SINR for secondary network. Note that we allow secondary users to have more flex￾ible power control ability. This is in accord with the design prin￾ciple of cognitive radios. We call a couple of nodes a link if they form a transmitter–re￾ceiver pair, e.g., . Given an interference model, in gen￾eral there is a number of subsets of links that can be active si￾multaneously. We call such subsets of links feasible states, and define the set of all feasible states as feasible family. We use to denote the feasible family of the physical model. C. Operation Rules The essential differences between cognitive networks and normal ad hoc networks are the operation rules. Though primary and secondary users overlap and share the channel, they are different essentially because of their behavior. In principle, primary nodes are spectrum license holders and have the priority to access the channel. It is followed by two important implications. First, primary nodes may operate at their own will without considering secondary nodes. They may be legacy devices running on legacy protocols, which are fixed and unmanageable. Therefore, the assumptions made about primary networks should be as few and general as possible. Moreover, the secondary network, which is opportunistic in nature, should control its interference to the primary network and prevent deteriorating the performance of primary users. The challenge is that the primary scheduler may not alter its protocol due to the existence of the secondary network, and its decision model could be different from the physical model (1), i.e., the interference term from the secondary network in the denominator is not available. However, in order to leave some margin for secondary nodes, it is necessary for the decision model to operate at an SINR larger than by an allowance . Operartion Rule 1: Decision model for the primary network: The primary scheduler considers the transmission from to to be feasible if The feasible family of the primary decision model is denoted as . Then, as the operation rule, secondary nodes should guar￾antee that the feasible state under the decision model above should be indeed feasible under the physical model. Operation Rule 2: Decision model for the secondary net￾work: Let and be the sets of active primary links and active secondary links. If , then , w.h.p. Note that compared to most existing related literatures where the concept of user priority is usually scheme- or network-spe￾cific, Operation Rules 1 and 2 formally define the principle of cognitive behaviors in a general sense. D. Capacity Definition Definition 1: Feasible throughput: Per-node throughput of the primary network is said to be feasible if there exists a spatial and temporal scheme for scheduling transmissions, such that by operating the primary network in a multihop fashion and buffering at intermediate nodes when awaiting transmission op￾portunities, every primary source can send b/s to its desti￾nation on average. Definition 2: Asymptotic per-node capacity of the pri￾mary network is said to be if there exist two positive constants and such that is feasible is feasible Similarly, we can define the asymptotic per-node capacity for the secondary network. III. OVERVIEW OF IDEA AND SOLUTION Our system model begins with a very classical setup, where the network topology, node communication capabilities, and performance metrics fall in the same framework that is most commonly deployed in related works on asymptotic analysis of wireless networks. An extensive body of literature [4]–[14] has investigated various specific networks under this framework. For that matter, the key issue that we aim to address in this paper is how the cognitive principles, i.e., Operation Rules 1 and 2, may impact network performance, especially with respect to the abundant insights already gained in previous works on asymp￾totic network capacity and delay. Clearly this is a nontrivial problem: Operation Rules 1 and 2 have introduced fundamental heterogeneities into the network in the sense that nodes now have different levels of priority. Such heterogeneities are exactly the most essential idea of how cognitive networks operate

This 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 However,though the two operation rules are ideal definitions Recall from operation rules that primary nodes are unmanage- for cognitive principles,they are not convenient from the per- able,so in fact the key issue is the schedule strategy for the spective of analysis and practice because,despite their simple secondary network.Specifically,we will face two challenges: forms,they actually involve numerous underlying details such first,how to ensure that secondary transmissions are harmless as the whole network topology,transmission power,and ag- to the primary network;second,how to establish a secondary gregate interference in judging the eligibility of even a single link given uncontrollable interference from the primary net- link.Therefore,we introduce the hybrid protocol model,which work.Our goal is to design a practical decision criteria for the loosely speaking is a subset of Operation Rules 1 and 2 in the secondary users to address these two seemingly contradictory sense that it is a somewhat"stricter"criterion.The hybrid pro- challenges at the same time.Intuitively.that is to say we should tocol model is significantly simpler to analyze because it only find simpler rules for secondary nodes to hunt and exploit relies on the geometry of node positions and conceals other opportunities in the network subject to the operation rules. details.To establish the correspondence between the operation rules and the hybrid protocol model is the main mission of Section IV,where we design the protocol parameters and the A.Hybrid Protocol Model underlying power assignment schemes.Then,we may use the hybrid protocol model instead of the operation rules in later Since we assume the primary network to be a general network analysis of network performance,only at the cost of losing a that operates according to decision model (a+e),it is our marginal portion of secondary transmission opportunities due starting point.is of physical concern and cares about the ag- to the slight inequivalence between the two sets of criteria. gregate interference and SINR,but the following lemma relates The throughput and delay in a network are dependent on the it to a simpler pairwise model.This alternative model is known specific scheduling and routing schemes.In Section V.we con- as the protocol model in literature and often plays the role as sider whether there is a class of scheduling or routing schemes interference model.However,here we use it as a tool to charac- to which the cognitive behaviors are benign.In other words,this terize the relative position of active primary nodes. implies that under the hybrid protocol model,both the primary Definition 3:Protocol Model for primary network:A trans- and secondary networks can achieve the same order of perfor- mission from Xi to Xi is feasible if mance as if they are separate without mutual interference.This is especially important for the secondary users because it indi- cates that though they are inferior in priority,their performance Xk-X≥(1+△p儿X-X k∈TD) is still guaranteed. In particular,we identify two classes of primary network where Ap defines the guard zone for the primary network.The communication schemes,one on scheduling and the other on corresponding feasible family is noted as p(Ap).Likewise. routing,that satisfy this property.The first class of primary we define protocol model s(As)for the secondary network. networks is scheduled in a generalized cell-partitioned TDMA First we need to consider the relation of inclusion between manner.In this case,due to the geometric property of the hybrid different feasible families. protocol model,every secondary user may associate itself with Lemma:IfSD∈(a+e)and△p≤(a+e)'/n-1, a certain primary cell at an appropriate distance away,such that whenever the cell is scheduled to be active,the secondary then S(p)∈2p(△p) user may transmit without causing(receiving resp.)destructive Proof:Let S(p)∈9，∀(Xi,Xi)∈S(p)and∀k≠i,k∈ interference to(from resp.)the primary network.In the second T(p).holds class of networks,every primary traffic flow (i.e.,a source destination pair of the primary network)shall make the routing X:-Xil-Y PlX:-Xil- decision independently of other flows.The main idea is that every primary transmission will not only intuitively mute the &-X万2N+P∑eoW-X之0十f secondary users nearby,but will also create certain"gap"such that the secondary users in these regions may be "riggered." therefore Xi-X≥(a+e)l/lX:-Xil.set△p≤(a+ Because the traffic is somewhat independently distributed e)1/7-1,then S(p)Ep. (relayed)in the primary network,if a secondary link is muted Since p i.e.,any feasible output of the primary for a long time w.h.p.,indicating the primary traffic nearby is intense,then this link will also be triggered for a considerable scheduler is also feasible under p as long as Ap <(a+ time w.h.p.. e/-1,and considering the simplicity of the protocol model, Lastly,because these two classes of schemes include most it motivates us to define a new hybrid protocol modelbased of those proposed or discussed in literature,numerous results on p ands to be the decision model for the secondary therein can be easily extended to the settings of cognitive network. networks,where Operation Rules 1 and 2 apply.These specific Definition 4:The Hybrid Protocol Model with feasible family examples are discussed in Section VI. 光（△p,△s,△sp,△s):S∈，let S(P)={(X,X)∈S} IV.IDENTIFYING OPPORTUNITIES:THE HYBRID PROTOCOL andS间={Ya,y)∈Sl,then S(）∈2p(△p),S间∈ MODEL 2s(△s).Furthermore,∀(Xi,X)eSp) In this section,we consider the problem of how to schedule links in the cognitive network under interference constraint. Y-Xl≥(1+△pX:-X k∈Ts)(2)

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 4 IEEE/ACM TRANSACTIONS ON NETWORKING However, though the two operation rules are ideal definitions for cognitive principles, they are not convenient from the per￾spective of analysis and practice because, despite their simple forms, they actually involve numerous underlying details such as the whole network topology, transmission power, and ag￾gregate interference in judging the eligibility of even a single link. Therefore, we introduce the hybrid protocol model, which loosely speaking is a subset of Operation Rules 1 and 2 in the sense that it is a somewhat “stricter” criterion. The hybrid pro￾tocol model is significantly simpler to analyze because it only relies on the geometry of node positions and conceals other details. To establish the correspondence between the operation rules and the hybrid protocol model is the main mission of Section IV, where we design the protocol parameters and the underlying power assignment schemes. Then, we may use the hybrid protocol model instead of the operation rules in later analysis of network performance, only at the cost of losing a marginal portion of secondary transmission opportunities due to the slight inequivalence between the two sets of criteria. The throughput and delay in a network are dependent on the specific scheduling and routing schemes. In Section V, we con￾sider whether there is a class of scheduling or routing schemes to which the cognitive behaviors are benign. In other words, this implies that under the hybrid protocol model, both the primary and secondary networks can achieve the same order of perfor￾mance as if they are separate without mutual interference. This is especially important for the secondary users because it indi￾cates that though they are inferior in priority, their performance is still guaranteed. In particular, we identify two classes of primary network communication schemes, one on scheduling and the other on routing, that satisfy this property. The first class of primary networks is scheduled in a generalized cell-partitioned TDMA manner. In this case, due to the geometric property of the hybrid protocol model, every secondary user may associate itself with a certain primary cell at an appropriate distance away, such that whenever the cell is scheduled to be active, the secondary user may transmit without causing (receiving resp.) destructive interference to (from resp.) the primary network. In the second class of networks, every primary traffic flow (i.e., a source destination pair of the primary network) shall make the routing decision independently of other flows. The main idea is that every primary transmission will not only intuitively mute the secondary users nearby, but will also create certain “gap” such that the secondary users in these regions may be “riggered.” Because the traffic is somewhat independently distributed (relayed) in the primary network, if a secondary link is muted for a long time w.h.p., indicating the primary traffic nearby is intense, then this link will also be triggered for a considerable time w.h.p.. Lastly, because these two classes of schemes include most of those proposed or discussed in literature, numerous results therein can be easily extended to the settings of cognitive networks, where Operation Rules 1 and 2 apply. These specific examples are discussed in Section VI. IV. IDENTIFYING OPPORTUNITIES: THE HYBRID PROTOCOL MODEL In this section, we consider the problem of how to schedule links in the cognitive network under interference constraint. Recall from operation rules that primary nodes are unmanage￾able, so in fact the key issue is the schedule strategy for the secondary network. Specifically, we will face two challenges: first, how to ensure that secondary transmissions are harmless to the primary network; second, how to establish a secondary link given uncontrollable interference from the primary net￾work. Our goal is to design a practical decision criteria for the secondary users to address these two seemingly contradictory challenges at the same time. Intuitively, that is to say we should find simpler rules for secondary nodes to hunt and exploit opportunities in the network subject to the operation rules. A. Hybrid Protocol Model Since we assume the primary network to be a general network that operates according to decision model , it is our starting point. is of physical concern and cares about the ag￾gregate interference and SINR, but the following lemma relates it to a simpler pairwise model. This alternative model is known as the protocol model in literature and often plays the role as interference model. However, here we use it as a tool to charac￾terize the relative position of active primary nodes. Definition 3: Protocol Model for primary network: A trans￾mission from to is feasible if where defines the guard zone for the primary network. The corresponding feasible family is noted as . Likewise, we define protocol model for the secondary network. First we need to consider the relation of inclusion between different feasible families. Lemma 1: If and , then . Proof: Let , and , holds therefore , set , then . Since , i.e., any feasible output of the primary scheduler is also feasible under as long as , and considering the simplicity of the protocol model, it motivates us to define a new hybrid protocol model based on and , to be the decision model for the secondary network. Definition 4: The Hybrid Protocol Model with feasible family , let and , then , . Furthermore, (2)

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination HUANG AND WANG:CAPACITY SCALING OF GENERAL COGNITIVE NETWORKS 5 O Proof:Let E and F be two arbitrary points on line segment ZiZi and ZiZi,by triangle inequality Zi-E+E-F+F-Z+Zk-F+F-E+E-Zil ≥|Z-Zl+lZ-Z (1+△)Rr ● (1+△)R Since Zi,E,Zi are collinear,substituting lemma condition IZ-Z+lZ-Z+2E-F≥lZ-Z团+Z-Zl Fig.1.Examples of the hybrid protocol model:Given an active primary link ≥(1+△21Z-Z+(1+△11Z-Z the left plot shows the guard zone regarding primary interferers,and the right plot for secondary interferers. therefore E-Fl≥（△1/2川Z:-Z+(△2/2川Zk-Z: Now we prove the lemma by contradiction.Suppose the two neighborhoods overlap,then there exist points P onZiZi and Q on Zi.ZI and Z such that |Z-P<(A1/2Zi-Zil and Z-Ql<(A2/2)Zk-Zil.Then,P-Q<IZ-P+ 1 Z-Ql<(△1/2lZ:-Zl+(△2/2)lZk-Z,which is a R2 contradiction. Corollary /Under the hybrid protocol model,we have the △2R2/2I following. 7 If (Xi,Xi)and (Xi Xi)are active primary links,the AplXi-Xil/2 neighborhood of line segment XiXi and △R1/21 ApXk:-Xi/2 neighborhood of XiXi are disjoint. If (Yi,Yi)and (Yi,Yi)are active secondary links,the Fig.2.Disjoint regions of two active transmissions. AsYi-Yil/2 neighborhood of line segment YiYi and As Y-Yil/2 neighborhood of Yiyi are disjoint. If (Xi Xi)is an active primary link and (Y,Yi)is an and∀Ya,y)∈Ss) active secondary link,the AspXi-Xil/2 neighborhood of line segment XiXi and Aps Y-Yi/2 neighborhood of YY are disjoint. Xk-Y引≥(1+△s)Y-Y k∈TP) (3) For active link (Xi,XRx()and (Yj,YRx()),where function Rx indicates the index of receiver,let Ri=X:-XRx(and where Asp,Aps define internetwork guard zones(Fig.1). rYj-Yx()Notice that Ri in general is a function of n The hybrid protocol model only depends on pairwise distance and ri is a function of m.We say the secondary network adopts between transmitters and receivers.Such simplicity will facili- power assignment scheme A(C)if for iE T(s),Pi=Cr?P. tate our analysis in the next section.Moreover,it is compatible The quadratic power assignment facilitates our effort to upper- with the classic protocol interference model.Thus,rich com- bound aggregate interference by converting it to an integral over munication schemes and results based on the protocol model the network area. can be easily extended to cognitive networks,as will be shown Theorem 1:Under power assignment A(C1)and the hy- in Section V. brid protocol model,if Aps As,then for any active primary In the following,we should prove that if is used as a deci- link(Xi,XRx()),the interference suffered by XRx()from the sion model for secondary nodes,it will comply with Operation secondary network is upper-bounded by CRP,for some Rule 2.This involves correctly tuning the parameters Ap,Ape, C2=Θ(C1) △p,△，and{P}jera Proof:Let B(X,r)be the disk centered at X with radius r.Then,all B(Yi,Asri/2),jET(s)should be mutually dis- joint according to Corollary 1.As well,B(Yi,Apsri/2),j B.Interference at Primary Nodes T(s)are disjoint with B(XRx(),ApRi/).Since ApA.. then all B(Y,△s/2),j∈Ta,B(XRx),△spR/2)are We first address the challenge that primary transmissions pairwise disjoint.Denote Dij=B(XRx(),XRx()-Yi)n should not be interrupted by secondary nodes.The main task is B(Yi;Asri/2).it is clear that all Dij are disjoint (see Fig.3). to bound the interference from the secondary network.We start Denote by E.F the two points where B(XRx(i),XRx(- with a useful property of the hybrid protocol model. Yil)intersects B(Yi,Asri/2).It is clear that FYjXRx(= Lemma 2:Given arbitrary Zi,Zi:Zk,ZIEO,if (Zi,Zi). ZEYjXR)≥T/3 because IXR⊙-YA>△s/2.Thus, (Zi,Z)are active links (primary or secondary),and Zk- the areaof Dij is at least one third of B(Yj,Asrj/2).Let Isp() Z1≥(1+△1Z-Z|Z-Z1≥(1+△2Zk-2 then the A1Zi-Zil/2 neighborhood of line segment ZiZ; 3More precisely,A is the asymptotic lens generated by the and the A2Z-Z/2 neighborhood of line segment ZiZi are h4lo码4"A intersection of two disks.Let disjoint (See Fig.2 for an example). 1)022)n(102)/（2=n1)(2=+1)0x

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. HUANG AND WANG: CAPACITY SCALING OF GENERAL COGNITIVE NETWORKS 5 Fig. 1. Examples of the hybrid protocol model: Given an active primary link, the left plot shows the guard zone regarding primary interferers, and the right plot for secondary interferers. Fig. 2. Disjoint regions of two active transmissions. and (3) where define internetwork guard zones (Fig. 1). The hybrid protocol model only depends on pairwise distance between transmitters and receivers. Such simplicity will facili￾tate our analysis in the next section. Moreover, it is compatible with the classic protocol interference model. Thus, rich com￾munication schemes and results based on the protocol model can be easily extended to cognitive networks, as will be shown in Section V. In the following, we should prove that if is used as a deci￾sion model for secondary nodes, it will comply with Operation Rule 2. This involves correctly tuning the parameters , , , , and . B. Interference at Primary Nodes We first address the challenge that primary transmissions should not be interrupted by secondary nodes. The main task is to bound the interference from the secondary network. We start with a useful property of the hybrid protocol model. Lemma 2: Given arbitrary , if , are active links (primary or secondary), and , , then the neighborhood of line segment and the neighborhood of line segment are disjoint (See Fig. 2 for an example). Proof: Let and be two arbitrary points on line segment and , by triangle inequality Since are collinear, substituting lemma condition therefore . Now we prove the lemma by contradiction. Suppose the two neighborhoods overlap, then there exist points on and on and such that and . Then, , which is a contradiction. Corollary 1: Under the hybrid protocol model, we have the following. • If and are active primary links, the neighborhood of line segment and neighborhood of are disjoint. • If and are active secondary links, the neighborhood of line segment and neighborhood of are disjoint. • If is an active primary link and is an active secondary link, the neighborhood of line segment and neighborhood of are disjoint. For active link and , where function indicates the index of receiver, let and . Notice that in general is a function of and is a function of . We say the secondary network adopts power assignment scheme if for . The quadratic power assignment facilitates our effort to upper￾bound aggregate interference by converting it to an integral over the network area. Theorem 1: Under power assignment and the hy￾brid protocol model, if , then for any active primary link , the interference suffered by from the secondary network is upper-bounded by , for some . Proof: Let be the disk centered at with radius . Then, all should be mutually dis￾joint according to Corollary 1. As well, are disjoint with . Since , then all , are pairwise disjoint. Denote , it is clear that all are disjoint (see Fig. 3). Denote by , the two points where intersects . It is clear that because . Thus, the area of is at least one third3 of . Let 3More precisely, ￾ is the asymptotic lens generated by the intersection of two disks. Let ￾ ￾  ￾  , then ￾￾ ￾￾   ￾ ￾          .