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 thanThis 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