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)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△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 ￾￾ ￾￾   ￾ ￾          .

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 YRx()should be larger than AspRmin/2+ApsTi/2;the distance 十 between any two primary transmitters is larger than ApRmin. ·YRxy Now consider the case that△sp Ap:Ips(i)will be smaller,and the upper bound still holds.) Xgx() Then,all XjjT(p)is at least ApRmin/2 away from Y() B时 except X.First,consider the interference contributed byX P Fig.3.Analyzing the interference.Left plot shows an example for≤ii,and right plot for 2 ij. Next,consider the interference from some other primary trans- mitter Xi.Let Bii=B(Xi:ApRmin/2)n B(YRx(),Xi- denote the interference at receiver XRx(i)from the secondary YRx()c,as shown in Fig.3,then network,and dA be the area element dA I(=∑ CiP Bii IBiil Xj-YRx( 4CP dA (where Bjl is the area of disk Bij) JBy,△/2)|Y-XRx)F ≤ dA B IBminl Xj-Yix(Y (because dA=πA2号/4 JBYi,△sr/2 where |Bminl =min|Bijl ≤∑2CP dA AgD,居-XR下 P dA [Bminl (-YRx)Y s∑ 12CP dA B:1 T) )TA2 JD,X-XRx下 (because Xj-YRx(>ApRmin/2) (where X is the position vector of dA, 2P dA andlX -XRx(<Yj-XRx(l for X E Dij) Bmin K-Yr间T 12C1P dA 2+3P π△2 儿eDX-XRx间f1 △m dAx -YRx(l. Since (UjT(Dij)B(XRx()AspRi/2)=0.we have 12C1P dA Tosum up,lets()=∑jerp叭{xw(P/X-Yx(lP) Ip() T△2 X-XRx(下 ()≤ 2+3P ∑ dA |X-XRx(l2△pR:/2 π△华F jET(D)\X')Bis X-YRx() 12C1P 2xrdr 2+3P dA π△2 △pR:/2 24C1P nU,erok(B X-Yx() 2 Y-2 C2PR2-7. (since [Bii}are disjoint) △2(Y-2) 2y+3P dA ≤△F隔 C.Interference at Secondary Nodes K-小p画 X-YRx() Now we focus on the interference at secondary nodes.The 2+3P 2mrdr main challenge is to bound the uncontrollable interference from the primary network.Let Rmax(n)=max Ri(n).Rmin(n)= 不A早a… T 2 min Ri(n),and rmax(m)=maxri(m). Theorem 2:Under power assignment A(C)and the hybrid Combining the contribution from X protocol model,for any active link (Yi,YRx(),the interfer- 22+2 ence at YRx()from the primary network is upper-bounded by Ips()≤ PRin(n). C3PRmin(n)-7,for some constant c3. (y-2)△g Proaf:Denote byIp()=∑jET(P/IXi-YRx())） the interference at YRx()from the primary network.Pick We should also take into account the interference between as the interfering primary transmitter closest to YRx().From secondary links.Power assignment scheme A is well designed Corollary 1,the distance between any primary transmitter and so that it not only restricts the interference from the secondary

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 6 IEEE/ACM TRANSACTIONS ON NETWORKING Fig. 3. Analyzing the interference. Left plot shows an example for ￾ , and right plot for . denote the interference at receiver from the secondary network, and be the area element because where is the position vector of and for Since , we have C. Interference at Secondary Nodes Now we focus on the interference at secondary nodes. The main challenge is to bound the uncontrollable interference from the primary network. Let , , and . Theorem 2: Under power assignment and the hybrid protocol model, for any active link , the interfer￾ence at from the primary network is upper-bounded by , for some constant . Proof: Denote by the interference at from the primary network. Pick as the interfering primary transmitter closest to . From Corollary 1, the distance between any primary transmitter and should be larger than ; the distance between any two primary transmitters is larger than . Now consider the case that . (Note that if will be smaller, and the upper bound still holds.) Then, all is at least away from except . First, consider the interference contributed by Next, consider the interference from some other primary trans￾mitter . Let , as shown in Fig. 3, then where is the area of disk where because To sum up, let since are disjoint Combining the contribution from We should also take into account the interference between secondary links. Power assignment scheme is well designed so that it not only restricts the interference from the secondary

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 1 network to the primary network,but also that between sec-schedule secondary network transmissions in the way such that ondary links,,as shown by the next theorem.Its proof is similar S(p)US句∈光，then S(p)US(a∈乎(a,g)holds. to Theorem 1 and is omitted for space concern. Proof:The first claim follows from Lemma 1.To prove the Theorem 3:Under power assignment scheme A(C1) second claim,first notice every active primary link is physically and the hybrid protocol model,for any active secondary feasible if the condition of Lemma 5 is verified,i.e., link (Yi,YRx(),the interference at YRx()from all other simultaneously active secondary links is upper-bounded by C2=Θ(C)=o(1/2ax(m). (5) Is()⑦≤C4Pr-(m),where C4=(242-2/y-2)△)C. On the other hand,consider the secondary network,if D.Physical Feasibility of the Hybrid Protocol Model C=w(Ra(n)/-Y(m)） (6) Lastly,we show under appropriate conditions that the hybrid protocol model is indeed physically feasible.We begin with a then according to Lemma 6,(4)holds for any positive con- lemma. stant cs.In combination with Lemma 7,it is clear that SINR at Lemma 3:Given A,B,C,a,b>0,if (C/A)a,where Ipp(i)is interference at XRx(i) transmission ranges and a simple decision model likedoes from other simultaneously active primary links. not suffice to identify transmission opportunities.Fortunately, Proof:Let A=PRY,B=N+Ipp(d),C=Isp(②)，a= this condition usually holds because Rmax(n)and Rmin(n)typ- a,b=e.Note that S()(+e)implies A/B>a+b.ically do not differ much in order and we usually tend to employ then the result holds from Lemma 3. ◆ a small r(m). Lema5:If△ps>△s,S∈光and S(P)∈9(a+e, then under power assignment A(C1)such that C2 to such constraints,it is intuitive that one should reduce the range of secondary links,and this fact is indeed verified by (cc(n)/(m)),if (p)then for any the hybrid protocol model and Theorem 4.This section will (Yi,YRx(),iT(s),it follows that further show that if rmax(m)=o(Rmin(n)),then for quite CP2m≥s general cases,such performance loss is insignificant and has no Ips(i) (4)impact in order sense.In other words,all secondary links have a constant ratio of time to be unconstrained as if they were in Lemma7:Under the condition of Lemma6,if△s≥ a standalone network,as long as they employ a transmission (48(2-2/-2)c6) )1/7,for any (Yi,YRx(i)),i T(),it range that is small enough.Moreover,note it is well known that follows that to achieve better scalability,a smaller range is also favorable. This coincidence implies that secondary networks can achieve CiPr2-7(m) the optimal scaling performance of a standalone network.Also N+Is(⑦) notice that by stating the secondary users as unconstrained,we mean that the secondary links activated by the scheduler can Then,we are ready to prove the final result. transmit without constraint subject to the dynamics of primary Theorem4:fr2a&(m)=o(in(m)/Rar(n),△p≤ network activities.However,the secondary scheduler itself (a+d)1/h-1,and Aps≥△s≥(242r/n-2)3)1/h,hen should comply with the constraint of rmax(m)=o(Rmin(n)). there exists power assignmentA(C).such that for any S(p)We remark that the other regime of(m)=w(min(). ()it follows that ()Apps,AspAs).If we which is not covered in this paper.is also a very interesting and

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 7 network to the primary network, but also that between sec￾ondary links, as shown by the next theorem. Its proof is similar to Theorem 1 and is omitted for space concern. Theorem 3: Under power assignment scheme and the hybrid protocol model, for any active secondary link , the interference at from all other simultaneously active secondary links is upper-bounded by , where . D. Physical Feasibility of the Hybrid Protocol Model Lastly, we show under appropriate conditions that the hybrid protocol model is indeed physically feasible. We begin with a lemma. Lemma 3: Given , if and , then . Then, first consider the primary network. Lemma 4: If , , and , then is feasible under physical model . That is to say, , where is interference at from other simultaneously active primary links. Proof: Let . Note that implies , then the result holds from Lemma 3. Lemma 5: If , and , then under power assignment such that , all primary links are feasible under physical model . Proof: For any , from Theorem 1, , thus the signal-to-inteference ratio (SIR) at satisfies Then, from Lemma 4, we have the assertion. Now turn to the secondary network. Similarly, it can be shown that Lemma 6 follows from Theorem 2, and Lemma 7 from Theorem 3, Lemma 6: Under power assignment with , if , then for any , it follows that (4) Lemma 7: Under the condition of Lemma 6, if , for any , it follows that Then, we are ready to prove the final result. Theorem 4: If , , and , then there exists power assignment , such that for any , it follows that . If we schedule secondary network transmissions in the way such that , then holds. Proof: The first claim follows from Lemma 1. To prove the second claim, first notice every active primary link is physically feasible if the condition of Lemma 5 is verified, i.e., (5) On the other hand, consider the secondary network, if (6) then according to Lemma 6, (4) holds for any positive con￾stant . In combination with Lemma 7, it is clear that SINR at any secondary receiver is greater than . Since , we can indeed find and , such that (5) and (6) hold, proving the theorem. The condition character￾izes the regime that primary links are homogeneous in range. In other words, if this condition fails, it implies that the sched￾uling of the primary network is excessively heterogeneous in transmission ranges and a simple decision model like does not suffice to identify transmission opportunities. Fortunately, this condition usually holds because and typ￾ically do not differ much in order and we usually tend to employ a small . V. AVAILABILITY OF TRANSMISSION OPPORTUNITIES Section IV addresses the problem of how to identify trans￾mission chances for secondary networks: Given a set of simultaneously active primary links, we allow a set of simultaneously active secondary links according to hybrid protocol model . This section, on the other hand, con￾siders the problem that for those secondary links that desire to transmit, how frequently do these opportunities occur. Of particular interest is to compare this result to an identical standalone network. Standalone networks provide trivial per￾formance upper bounds since cognitive secondary networks will suffer from additional transmission constraints imposed by primary networks. To alleviate the performance loss due to such constraints, it is intuitive that one should reduce the range of secondary links, and this fact is indeed verified by the hybrid protocol model and Theorem 4. This section will further show that if , then for quite general cases, such performance loss is insignificant and has no impact in order sense. In other words, all secondary links have a constant ratio of time to be unconstrained as if they were in a standalone network, as long as they employ a transmission range that is small enough. Moreover, note it is well known that to achieve better scalability, a smaller range is also favorable. This coincidence implies that secondary networks can achieve the optimal scaling performance of a standalone network. Also notice that by stating the secondary users as unconstrained, we mean that the secondary links activated by the scheduler can transmit without constraint subject to the dynamics of primary network activities. However, the secondary scheduler itself should comply with the constraint of . We remark that the other regime of , which is not covered in this paper, is also a very interesting and

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 important scenario to study and still needs further explorations X,thus any point Fthat belongs to a neighbor cell of V should in future works. lie within distance 4p(n)from X,then Now,we formally introduce the concept of unconstraint and analyze the unconstrained time period in the following.Let s.a. |Y-Fl≥(4+2△p)pm)-4(n) be the abbreviation of standalone: Definition 5:Given arbitrary Ss(As)and arbitrary =2△pp(m)≥(1+△p)4p(n) ≥(1+△spE-F (7) S(p)p(Ap),there exists a unique maximal S(s)C such that S(p)US(s)∈（△p,△ps,△sp,△p).We say a link Now consider another simultaneous active cell V.It is clear (Y,YRx@)∈is unconstrained if(Ya,YRo）∈Ss. that any point XE V/is at least(2+Ap)4p(n)away from Note the fraction of time that the link is constrained charac- X,then X'-Y≥(4+2△p)p(m)=lX-Y.Together terizes the performance loss relative to the corresponding stand- with (7),condition 2 is verified.Moreover,since r=o(Rmin). alone network condition 3 is obvious.This completes the proof. We observe that under hybrid protocol model.Ap >2 A.Cell-Partitioning Round-Robin Mode is critical to guarantee transmission opportunities for secondary We first consider the case that primary networks operate ac- nodes,as shown in Theorem 5.Equivalently,it implies a+e cording to a common scheduling paradigm:the cell-partitioning 27.This is an assumption about primary networks,and we as- sume it always holds from now on.However,we conjecture round-robin active scheme.It first spatially tessellates the net- this assumption is not fundamental and can be relaxed by in- work into cells,then assigns color to each cell such that cells with the same color,if limiting their transmissions to neigh- troducing a criterion with more flexible form,i.e.,allowing Asp bors,will not interfere with each other.Then,we allow cells and Aps to be dependent on n.Such decision models may have a better capability of digging into the potential of available gaps, with the same color to transmit simultaneously,and let different colors take turns to be active.A simple TDMA scheme will suf- at the cost of complexity.We leave for future work a more in-depth analysis of such cases. fice.This very widely employed scheme [4],[7],[13],14]fea- tures a high degree of spatial concurrency and thus frequency B.Independent Relay Mode reuse.It is deterministic and therefore simple.To the best of our knowledge,all previous works on asymptotic analysis of cog- Theorem 5 suffices to provide rich performance scaling re- nitive networks focused on some particular variants of such a sults on cognitive networks,for the scenario it considers,ie., TDMA scheme. the round-robin TDMA scheme,covers most centralized control Definition 6:A network tessellation is a set of disjoint cells networks.However,some other cases are also of interest such (Vi c O.A round-robin TDMA scheme is a scheduling as networks which employ distributed CSMA protocol [18].Ex- scheme that:1)tessellates the network into cells such that ceptions also exist in centralized control networks,such as the every cell is contained in a disk of radius p(n);2)allows protocol proposed in [19],which schedules the network in a noninterfering cells to be simultaneously active and transmit more generic and ideal manner without relying on the concept to neighbor cells,where two cells Vi,Vi are noninterfering if of cells.For that matter,Theorem 5 relies on the scheduling sup{E-Fl:E∈，F∈V}≥(2+△p)Ap(n):and of primary networks,.but sometimes it is desired to relax this 3)activates different groups of cells in a round-robin TDMA requirement.In the following,we show that some general as- fashion,and guarantees every cell can be active for at least c sumptions on the routing protocol of primary networks will suf- fraction of time in one round,for some constant c>0. ficiently lead to similar conclusions. The existence of round-robin TDMA schemes is a conse- Intuitively,according to the hybrid protocol model,on one quence of the well-known theorem about vertex coloring of hand primary transmissions will not be too dense spatially,thus graphs.Such a scheme is favorable to secondary networks be-leaving gaps for the secondary network.On the other hand,they cause it deterministically ensures transmission opportunities not also mute nearby secondary links.We shall show every primary only for every primary cell,but also for every secondary link. link can create some gap and mute some area.More formally, We now show for a generic primary scheduling policy that oper- given link (Xi,XRx())and (Yj,YRx()).we say the former ates in the round-robin fashion that the unconstrained time frac- triggers the latter if (Yj,YRx())is unconstrained as long as tion for any short range secondary link is constant,as a simple (Xi,XRx()is active and shades the latter conversely.Because consequence of the hybrid protocol model. nodes are i.i.d.,whether a primary link will trigger or shade Theorem 5:If the primary network operates according to a a secondary link is a random event.Then,if traffic is some round-robin TDMA scheme and△p>2,△p≤(Ap-2/2),what“independently”distributed(relayed)to primary links,ac then every secondary link with range r(m)=o(Rmin(n))has cording to the law of large numbers,if a secondary link is shaded at least c fraction of time to be unconstrained in one round. for a long time w.h.p.,i.e.,the primary traffic nearby is intense, Proof:Consider a generic link (Yi,YRx()),pick a point X it will also be triggered for considerable time. such that X-Yi =(4+2Ap)p(n),and denote by V the Lemma 8:Consider link (Xi,XRx(i))and (Yj,YRx(j)).If cell X belongs to..We claim whenever V is scheduled to be△p>2,△sp≤（△p-2/2)andT(m)=o(Ri(n),then active.(Y,Yx()is unconstrained.To that end,we first verify a sufficient condition that (x())triggers (YYx()) transmitter Yi will not upset transmissions in V.Indeed,any is that Yi lies in the ring of points with distance to line seg- point E that belongs to V should lie within distance 2p(n)from ment XiXRx(larger than(1+Asp)Ri(n)and less than

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 8 IEEE/ACM TRANSACTIONS ON NETWORKING important scenario to study and still needs further explorations in future works. Now, we formally introduce the concept of unconstraint and analyze the unconstrained time period in the following. Let s.a. be the abbreviation of standalone: Definition 5: Given arbitrary and arbitrary , there exists a unique maximal such that . We say a link is unconstrained if . Note the fraction of time that the link is constrained charac￾terizes the performance loss relative to the corresponding stand￾alone network. A. Cell-Partitioning Round-Robin Mode We first consider the case that primary networks operate ac￾cording to a common scheduling paradigm: the cell-partitioning round-robin active scheme. It first spatially tessellates the net￾work into cells, then assigns color to each cell such that cells with the same color, if limiting their transmissions to neigh￾bors, will not interfere with each other. Then, we allow cells with the same color to transmit simultaneously, and let different colors take turns to be active. A simple TDMA scheme will suf- fice. This very widely employed scheme [4], [7], [13], [14] fea￾tures a high degree of spatial concurrency and thus frequency reuse. It is deterministic and therefore simple. To the best of our knowledge, all previous works on asymptotic analysis of cog￾nitive networks focused on some particular variants of such a TDMA scheme. Definition 6: A network tessellation is a set of disjoint cells . A round-robin TDMA scheme is a scheduling scheme that: 1) tessellates the network into cells such that every cell is contained in a disk of radius ; 2) allows noninterfering cells to be simultaneously active and transmit to neighbor cells, where two cells are noninterfering if ; and 3) activates different groups of cells in a round-robin TDMA fashion, and guarantees every cell can be active for at least fraction of time in one round, for some constant . The existence of round-robin TDMA schemes is a conse￾quence of the well-known theorem about vertex coloring of graphs. Such a scheme is favorable to secondary networks be￾cause it deterministically ensures transmission opportunities not only for every primary cell, but also for every secondary link. We now show for a generic primary scheduling policy that oper￾ates in the round-robin fashion that the unconstrained time frac￾tion for any short range secondary link is constant, as a simple consequence of the hybrid protocol model. Theorem 5: If the primary network operates according to a round-robin TDMA scheme and , , then every secondary link with range has at least fraction of time to be unconstrained in one round. Proof: Consider a generic link , pick a point such that , and denote by the cell belongs to. We claim whenever is scheduled to be active, is unconstrained. To that end, we first verify transmitter will not upset transmissions in . Indeed, any point that belongs to should lie within distance from , thus any point that belongs to a neighbor cell of should lie within distance from , then (7) Now consider another simultaneous active cell . It is clear that any point is at least away from , then . Together with (7), condition 2 is verified. Moreover, since , condition 3 is obvious. This completes the proof. We observe that under hybrid protocol model , is critical to guarantee transmission opportunities for secondary nodes, as shown in Theorem 5. Equivalently, it implies . This is an assumption about primary networks, and we as￾sume it always holds from now on. However, we conjecture this assumption is not fundamental and can be relaxed by in￾troducing a criterion with more flexible form, i.e., allowing and to be dependent on . Such decision models may have a better capability of digging into the potential of available gaps, at the cost of complexity. We leave for future work a more in-depth analysis of such cases. B. Independent Relay Mode Theorem 5 suffices to provide rich performance scaling re￾sults on cognitive networks, for the scenario it considers, i.e., the round-robin TDMA scheme, covers most centralized control networks. However, some other cases are also of interest such as networks which employ distributed CSMA protocol [18]. Ex￾ceptions also exist in centralized control networks, such as the protocol proposed in [19], which schedules the network in a more generic and ideal manner without relying on the concept of cells. For that matter, Theorem 5 relies on the scheduling of primary networks, but sometimes it is desired to relax this requirement. In the following, we show that some general as￾sumptions on the routing protocol of primary networks will suf- ficiently lead to similar conclusions. Intuitively, according to the hybrid protocol model, on one hand primary transmissions will not be too dense spatially, thus leaving gaps for the secondary network. On the other hand, they also mute nearby secondary links. We shall show every primary link can create some gap and mute some area. More formally, given link and , we say the former triggers the latter if is unconstrained as long as is active and shades the latter conversely. Because nodes are i.i.d., whether a primary link will trigger or shade a secondary link is a random event. Then, if traffic is some￾what “independently” distributed (relayed) to primary links, ac￾cording to the law of large numbers, if a secondary link is shaded for a long time w.h.p., i.e., the primary traffic nearby is intense, it will also be triggered for considerable time. Lemma 8: Consider link and . If , and , then a sufficient condition that triggers is that lies in the ring of points with distance to line seg￾ment larger than and less than

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 uniformly distributed in Vi and V2,respectively.Denote by p the probability that (Xi,XRx()triggers(Yj,YRx().and g the probability of shading.Then,constant 61,62>0,among all primary links from Vi to V2,w.hp.,there are at least p(1- 61)(csn12)links that trigger (Yi,YRx()),and at most q(1+ 62)(con12)links that shade it. Proof:We only prove the first part of the lemma.From t+△R,. Lemma 10,there are at least cgnL2 nodes in each cell,denoted Rx(/) by Xug and Xu,k,l 1,...,canL2.Thus,we have at least (csnL2)candidate links from Vi to V2.Consider this subset of Fig.4.Active primary link)=can shade some area (the dark region) links,define I&.t as and trigger some area(the outside ring).Note the shading and triggering region of two links are disjoint according to Corollary 1. Ik,1= 1, if (Xuk,Xu)triggers(Yj,YRx(j)) 0,otherwise. ApRi(n)/2.A necessary condition that (Xi,XRx())shades Because nodes are i.i.d.,I are identically distributed and (Yi,YRx())is that Yi lies within the (1+Asp)Ri(n)neigh- with probability p equal to 1.Moreover,Ia,and Ii,t are inde- borhood of line segment XiXRx(),as shown in Fig.4. pendent if a≠kand b≠l.Construct Ik as Proof:The necessary condition is obvious.As to the suf- ficient condition,(3)holds forri=o(R).It is also clear that odd IYj-XRx(>(1+Asp)Ri.For any other active primary link (X,XRx()),i its receiver is at least ApR/2 away k:even. from Yi due to Corollary 1.Therefore,(2)also holds,proving the lemma. Then,/i is the sum of i.i.d.random variables.Applying the As a consequence.we can term (Xi,XRx())triggers law of large numbers,one can easily show that V630,the following holds w.h.p.: Definition 7:Consider a regular network tessellation of square cells.We assume every source route traffic to its des- ∫p1-6)(csnL2-号)， k odd tination along these cells in multihop fashion,such that at 1p1-61)(csnL2-), k even. every hop,a packet is transmitted to a relay node in a neighbor cell.We say the network routing operates in the independent Lastly,note the relationship of summing and} relay mode if,at each hop,flows choose relays randomly and independently among all nodes in the receiving cells. 2c8nL2-1 SacsnL The regular tessellation of square cells is only a technical ∑∑I= assumption for the ease of presentation.A similar result also holds for other topologies.By saying "independent,"we do ≥(p1-1)-(2-3》(csnL22 (w.h.p.). not mean the routes of two flows are independent.In fact,they could be highly related,such as choosing a same sequence Making o3 arbitrarily close to 2,we have the claim. ■ of cells to forward.Instead,we only require that two flows In the next step,we characterize the relation between p and independently choose relays for a certain cell.Intuitively, g.The main idea is to couple the triggering and shading events independently relaying implies there are no special designated through a continuous transformation in R.We first cite a prop- nodes in the network,and is in accord with the design principles erty of Lebesgue measure [21. of distributed systems such as ad hoc networks.It is notable Lemma 12:(Integration by change of variable)Let S CR that the class of independent relay protocol is quite general and be an open set,and let C be a Lebesgue measure on S.Let common[18,[19]. T(x)=((x),...,m(x)),x=(x1,...,n)E S be a given The next lemma follows from the well-known connectivity homeomorphism T:S-R with the continuous derivatives criterion [20],and Lemma 10 is a standard application of the (oui/orj),i,j=1,...,n on S,and we note with r(T,) Chernoff bound. ((oyi/orj))the nondegenerate Jacobian matrix for all t E S. Lemma 9:For an independent relay protocol,to ensure Then,for any nonnegative Borel function f defined on the open asymptotic connectivity of the overall network,the side set T(S),we have length L of square cells is at least (vlogn/n). Lemma 10:For an independent relay protocol,there exist f(y)dy= fTx)·r(T,xldz positive constants Cg and Co,such that w.h.p.every cell contains T(S) more than csnL2 and less than conL2 primary nodes. Now we characterize the shading/triggering events with a where dt,dy denote the integration with respect to C. Bernoulli-like probability model: Theorem 6:Define p,g as in Lemma 11,and under the con- Lemma 11:Consider arbitrary neighboring cells Vi,V2 and dition of Lemma 8.there exists constant cio >0,such that link(Yj,YRx()),and let Xi and XRx()be independently and p >ciog

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 9 Fig. 4. Active primary link ￾￾ ￾ can shade some area (the dark region) and trigger some area (the outside ring). Note the shading and triggering region of two links are disjoint according to Corollary 1. . A necessary condition that shades is that lies within the neigh￾borhood of line segment , as shown in Fig. 4. Proof: The necessary condition is obvious. As to the suf- ficient condition, (3) holds for . It is also clear that . For any other active primary link , its receiver is at least away from due to Corollary 1. Therefore, (2) also holds, proving the lemma. As a consequence, we can term triggers and triggers interchangeably. Definition 7: Consider a regular network tessellation of square cells. We assume every source route traffic to its des￾tination along these cells in multihop fashion, such that at every hop, a packet is transmitted to a relay node in a neighbor cell. We say the network routing operates in the independent relay mode if, at each hop, flows choose relays randomly and independently among all nodes in the receiving cells. The regular tessellation of square cells is only a technical assumption for the ease of presentation. A similar result also holds for other topologies. By saying “independent,” we do not mean the routes of two flows are independent. In fact, they could be highly related, such as choosing a same sequence of cells to forward. Instead, we only require that two flows independently choose relays for a certain cell. Intuitively, independently relaying implies there are no special designated nodes in the network, and is in accord with the design principles of distributed systems such as ad hoc networks. It is notable that the class of independent relay protocol is quite general and common [18], [19]. The next lemma follows from the well-known connectivity criterion [20], and Lemma 10 is a standard application of the Chernoff bound. Lemma 9: For an independent relay protocol, to ensure asymptotic connectivity of the overall network, the side length of square cells is at least . Lemma 10: For an independent relay protocol, there exist positive constants and , such that w.h.p. every cell contains more than and less than primary nodes. Now we characterize the shading/triggering events with a Bernoulli-like probability model: Lemma 11: Consider arbitrary neighboring cells , and link , and let and be independently and uniformly distributed in and , respectively. Denote by the probability that triggers , and the probability of shading. Then, constant , among all primary links from to , w.h.p., there are at least links that trigger , and at most links that shade it. Proof: We only prove the first part of the lemma. From Lemma 10, there are at least nodes in each cell, denoted by and . Thus, we have at least candidate links from to . Consider this subset of links, define as if triggers otherwise. Because nodes are i.i.d., are identically distributed and with probability equal to 1. Moreover, and are inde￾pendent if and . Construct as odd even. Then, is the sum of i.i.d. random variables. Applying the law of large numbers, one can easily show that , , , the following holds w.h.p.: odd even. Lastly, note the relationship of summing and w.h.p. Making arbitrarily close to 2, we have the claim. In the next step, we characterize the relation between and . The main idea is to couple the triggering and shading events through a continuous transformation in . We first cite a prop￾erty of Lebesgue measure [21]. Lemma 12: (Integration by change of variable) Let be an open set, and let be a Lebesgue measure on . Let be a given homeomorphism with the continuous derivatives on , and we note with the nondegenerate Jacobian matrix for all . Then, for any nonnegative Borel function defined on the open set , we have where denote the integration with respect to . Theorem 6: Define , as in Lemma 11, and under the con￾dition of Lemma 8, there exists constant , such that .

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 minwes(|EFler-|EFlmin/V5-EFler),then C(Ta(w)(S))> C(Ta(S)).Additionally EFler-EFlmin> dTa-(ww】_2d(Tomin()】 1+△sp △p V5-EFcr √5 E YRxD) 21 der 2der (EFlcr-EFmin) 1 0 5(1+△sp) V5△p Fig.5.Transformation4 o shrinks=[to=['such that←'['≤f]←[≤ △+4p-2 (f r Oin this figure)and ensures that 1'2 g. -2v5△p(1+△sp) Lastly,observe in the worst case that Yi lies in Vi or V2,and Proof:Without loss of generality,let Vi=[-1,0]x there are some Shd C Sshd,C(Shd)>1/8C(Sshd),such that [0,],2=0,1]×[0,1],and(2,多，C)be the probability ShdUES H(w）andw∈Sha,du2>1/4.Therefore,. space4 of interest,where =Vi x V2 and C is the Lebesgue der>l/4.Define0≌（△p+△p-2/8v5Ap(1+△sp),and it follows that measure restricted on2.Given W=(x1,h,x2,2）∈2， define Ta:as To(w)=w'=(1,1,2,3) g=PrfYi is shaded}=C(Sshd)2,△sp≤（△p-2/2),then every and Sshd=w e:Yi is shaded),Strg =w e:secondary link with ranger(m)=o(Rmin(n))has at least on Yi is triggered).Assume Ssha is not empty and consider any average cu fraction of time to be unconstrained,where constant wb∈Sshd and the set H(b)={W∈2：W=Ta(wo),0> C11>0. 0}.Define 0cr and min such that Proof:Intuitively,due to the fact that the triggering(suc- cess)probability p is at least of the same order as the shading d(Tsw】=:0alEF=EFler (failure)probability g,as shown in Theorem 6,then if a sec- 1+△p ondary link is shaded for a significant fraction of time,this in- 2d(Toma (=0minEF=EFlmin. dicates that primary transmissions nearby(Bernoulli trials)are Ap intense and the link will also be triggered for a substantial frac- tion of time with high probability.The formal proof is presented According to Lemma 8,it is clear that cr and Omin uniquely below. exist and0cr>Amim.Moreover,.d∈H(o),d∈Ssha→ Without loss of generality,consider a time interval of unit IEFI>EFler;EFlmin≤IEFI≤EFler→w∈ length and a particular secondary link(Yj,YRx()).We only dis- Strg Therefore,we can introduce a mapping from the set of cuss the case that Yi is shaded by transmissions from some cell line segments with length(EFl,v5)to those with length Vi to V2 for a least some constant fraction of time,otherwise (EFmin,EF).where v5 is an upper bound of Fi.e.,the proof is trivial.This implies that the shading probability gis lower-bounded by g=e(1).and CaAp=e(1),where Ca is the number of flows that choose this route,and Ap =O(1/vn) is the per-node throughput of primary network.Then,from The- (uo)= EFln+(EFlr-VEFl) orem 6 we have the triggering probability p>c1og1 =(1). According to Lemmas 10 and 11,the fraction of candidate EF links that trigger Yi is at least pi pcs/2c9. Let I be the logical indicator function,and define Then,Vw∈Sshd,Th(w)(u）∈Strg,i.e.,we construct a mapping J=Iflow i chooses a link that triggersY.then between Sshd and Strg,and by invoking Lemma 12,the relation J is sum of ii.d.Bernoullian random variables with mean betweenpand g can be established.To that end,we first simply p2>pi.Denote E as expectation,and by applying Chernoff (w).It is obvious on a little thought that VS C Ssbd,if bounds,we get 4With abuse of notation,we use to denote a set and 1 an element instead of order when no confusion is caused. Pr<-Cuh<e-cm/s, (8)

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 10 IEEE/ACM TRANSACTIONS ON NETWORKING Fig. 5. Transformation ￾ shrinks to such that ￾ ￾ ￾ ￾￾ ( ￾  in this figure) and ensures that  . Proof: Without loss of generality, let , and be the probability space4 of interest, where and is the Lebesgue measure restricted on . Given , define as Intuitively, let and , then linearly shrinks line segment to with , preserving its geometric topology. See Fig. 5 for an example. Let be the distance from to line segment and is shaded , is triggered . Assume is not empty and consider any and the set . Define and such that According to Lemma 8, it is clear that and uniquely exist and . Moreover, , ; . Therefore, we can introduce a mapping from the set of line segments with length to those with length , where is an upper bound of , i.e., Then, , , i.e., we construct a mapping between and , and by invoking Lemma 12, the relation between and can be established. To that end, we first simply . It is obvious on a little thought that , if 4With abuse of notation, we use  to denote a set and  an element instead of order when no confusion is caused. , then . Additionally Lastly, observe in the worst case that lies in or , and there are some , such that and . Therefore, . Define , and it follows that is shaded let and in Lemma 12 and because is triggered Let , and we complete the proof. Theorem 7: If the primary network employs an independent relay protocol and , , then every secondary link with range has at least on average fraction of time to be unconstrained, where constant . Proof: Intuitively, due to the fact that the triggering (suc￾cess) probability is at least of the same order as the shading (failure) probability , as shown in Theorem 6, then if a sec￾ondary link is shaded for a significant fraction of time, this in￾dicates that primary transmissions nearby (Bernoulli trials) are intense and the link will also be triggered for a substantial frac￾tion of time with high probability. The formal proof is presented below. Without loss of generality, consider a time interval of unit length and a particular secondary link . We only dis￾cuss the case that is shaded by transmissions from some cell to for a least some constant fraction of time, otherwise the proof is trivial. This implies that the shading probability is lower-bounded by , and , where is the number of flows that choose this route, and is the per-node throughput of primary network. Then, from The￾orem 6 we have the triggering probability . According to Lemmas 10 and 11, the fraction of candidate links that trigger is at least . Let be the logical indicator function, and define flow chooses a link that triggers , then is sum of i.i.d. Bernoullian random variables with mean . Denote as expectation, and by applying Chernoff bounds, we get (8)