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 11 Equation (8)indicates Yi will be triggered for a constant throughput rate of link (Yi,Yi)as c and from Theorems 5 fraction of time.We need to show this fact holds uniformly and 7.cr.ci2c2,where constant c12 minfc7,c11). for all secondary links.To that end,we tessellate the net- Letting火=c2入=O(As),it follows that work into Con subsquares for some C=w(1),then it is clear that all secondary transmitters within a same subsquare share the same status of being unconstrained or not.Denote =owrq,then by the subaddi- ∑∑暗≤克 1≤i,j≤m. tivity of probability measure Therefore,no edge is overloaded,and throughput A is feasible. {>≥21-∑r{k< As to delay,the definition and calculation of it depend on specific network settings,such as packet size or mobility pat- ≥1-Cune-Car2/8→1 terns [13],[14].However,we note that a general baseline in prior works is that per-hop delay for a packet is at least (1) where the last limit holds for any C=n#,u R due to (this may include transmission delay.queueing delay and delay Cap2 =(1/Ap)=(vn).Then w.h.p.,every secondary link incurred by mobility,etc.).In secondary networks,packets will is triggered for at least(1/2)Cap2Ap=e(1)seconds,proving suffer from extra delay because at each hop,or at each time they the theorem ■ are transmitted by a link,they must wait until the link is uncon- strained.According to Theorems 5 and 7,such delay penalty is VI.OPTIMAL PERFORMANCE SCALING upper-bounded by the duration of one round or unit time,which is (1).Therefore,the order of overall delay is preserved. In this section,we present results on throughput and delay With Theorem 8,we can conveniently extend optimal scaling of general cognitive networks,as well as a number of schemes and results of standalone networks to cognitive net- corollaries under various specific settings. works.The optimality is preserved in cognitive networks unless Theorem 8:If the primary network operates in the we allow cooperation between primary and secondary nodes, round-robin TDMA or the independent relay fashion,which is beyond the scope of this paper.The following two for any protocol interference model based scheme that corollaries are straightforward from [13]and [14].For clarity, schedules and routes the secondary network such that we assume by convention that both networks are static and Tmax(m）=(Rmin(n).Tma(m）=o(Ehin(n)/a(m) operate at the same timescale unless further specifications are w.h.p.,and achieves per-node throughput As and delay Ds in the made. case that secondary network is standalone,there exists a corre- Corollary 2:The optimal throughput-delay tradeoff is Dp= sponding scheme that can achieve per-node throughput (As)e(nAp),Ap <e(1/vn)for the primary network and Ds and delay (Ds)when the primary network is present and (mAs).(nAp/m)<As (1/vm)for the secondary Operation Rules 1 and 2 apply. network,if (1/vm)>e(nXp/m). Proof:First,we hypothesize the secondary network Remark /In the primary networks (classic static wireless is standalone,and denote by c the throughput rate of ad hoc networks),optimal throughput-delay tradeoff can link Yi,Yi),then is determined by the scheduling be achieved by [13.Scheme 1].which is a cell-partitioned scheme.For example,if we assume slotted time,then a de- TDMA scheme with a squarelet of side length lp(n).Then, terministic scheduling scheme is characterized by a sequence Dp(n)=0(1/p(n))and Ap(n)=e(1/nlp(n)).Notice that (Sa.)E,Sga.∈2，and primary transmission range w.hp.is lp(n).Let the secondary networks also follow [13,Scheme 1],with Is(n)=o(lp(n)), and therefore入s(m)=Θ(l/mls(m)=2(m入p(m)/m).On the other hand,.Θ(l/√元)ando(l/√m)is the maximal achievable throughput in primary and secondary networks,respectively. The network can be mapped to a graph g.where m vertices Corollary 3:If primary nodes move according to the random stand for secondary nodes,and {compose edges.The net- walk model,then the optimal throughput-delay tradeoff for work traffic is represented as a multicommodity flow instance the primary network is Dp=Θ(mdp)ifλp≤Θ(l/√m, on g [22],and the routing scheme is defined by f,the av- and Dp=o(n log n)ifo(1/√冗<λp≤o(1).The op- erage fraction of traffic from Ys to Yd that is routed through timal throughput-delay tradeoff for the secondary network is link (Yi,Yi).Because the overall scheme achieves per-node Ds=Θ(m入s),o(nmin(1/√元，p)/m)<入≤Θ(1/vm), throughput As,it holds that ifo(1/vm)>Θ(nmin(1/v元，λp)/m). Remark 2:Our framework could well accommodate node ∑∑f爵≤点 1≤i,j≤m. mobility.Notice that neither the hybrid protocol model nor the unconstraint time analysis rely on mobility pattern.Specifically, if primary users move according to the random walk model,op- Now,let the primary network joins,and we stick the secondary timal throughput-delay tradeoff in the primary network can be network to the prior scheme except for only allowing the achieved by the cell-partitioned TDMA scheme [13,Scheme 3]. unconstrained links to be active.According to Theorem 4.such Therefore,the results in Corollary 3 can be obtained following scheduling is physically feasible.Denote the corresponding a similar argument as in Remark 1.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 11 Equation (8) indicates will be triggered for a constant fraction of time. We need to show this fact holds uniformly for all secondary links. To that end, we tessellate the net￾work into subsquares for some , then it is clear that all secondary transmitters within a same subsquare share the same status of being unconstrained or not. Denote , then by the subaddi￾tivity of probability measure where the last limit holds for any due to . Then w.h.p., every secondary link is triggered for at least seconds, proving the theorem. VI. OPTIMAL PERFORMANCE SCALING In this section, we present results on throughput and delay scaling of general cognitive networks, as well as a number of corollaries under various specific settings. Theorem 8: If the primary network operates in the round-robin TDMA or the independent relay fashion, for any protocol interference model based scheme that schedules and routes the secondary network such that , w.h.p., and achieves per-node throughput and delay in the case that secondary network is standalone, there exists a corre￾sponding scheme that can achieve per-node throughput and delay when the primary network is present and Operation Rules 1 and 2 apply. Proof: First, we hypothesize the secondary network is standalone, and denote by the throughput rate of link , then is determined by the scheduling scheme. For example, if we assume slotted time, then a de￾terministic scheduling scheme is characterized by a sequence , , and The network can be mapped to a graph , where vertices stand for secondary nodes, and compose edges. The net￾work traffic is represented as a multicommodity flow instance on [22], and the routing scheme is defined by , the av￾erage fraction of traffic from to that is routed through link . Because the overall scheme achieves per-node throughput , it holds that Now, let the primary network joins, and we stick the secondary network to the prior scheme except for only allowing the unconstrained links to be active. According to Theorem 4, such scheduling is physically feasible. Denote the corresponding throughput rate of link as , and from Theorems 5 and 7, , where constant . Letting , it follows that Therefore, no edge is overloaded, and throughput is feasible. As to delay, the definition and calculation of it depend on specific network settings, such as packet size or mobility pat￾terns [13], [14]. However, we note that a general baseline in prior works is that per-hop delay for a packet is at least (this may include transmission delay, queueing delay and delay incurred by mobility, etc.). In secondary networks, packets will suffer from extra delay because at each hop, or at each time they are transmitted by a link, they must wait until the link is uncon￾strained. According to Theorems 5 and 7, such delay penalty is upper-bounded by the duration of one round or unit time, which is . Therefore, the order of overall delay is preserved. With Theorem 8, we can conveniently extend optimal schemes and results of standalone networks to cognitive net￾works. The optimality is preserved in cognitive networks unless we allow cooperation between primary and secondary nodes, which is beyond the scope of this paper. The following two corollaries are straightforward from [13] and [14]. For clarity, we assume by convention that both networks are static and operate at the same timescale unless further specifications are made. Corollary 2: The optimal throughput–delay tradeoff is , for the primary network and , for the secondary network, if . Remark 1: In the primary networks (classic static wireless ad hoc networks), optimal throughput–delay tradeoff can be achieved by [13, Scheme 1], which is a cell-partitioned TDMA scheme with a squarelet of side length . Then, and . Notice that primary transmission range w.h.p. is . Let the secondary networks also follow [13, Scheme 1], with , and therefore . On the other hand, and is the maximal achievable throughput in primary and secondary networks, respectively. Corollary 3: If primary nodes move according to the random walk model, then the optimal throughput–delay tradeoff for the primary network is if , and if . The op￾timal throughput–delay tradeoff for the secondary network is , , if . Remark 2: Our framework could well accommodate node mobility. Notice that neither the hybrid protocol model nor the unconstraint time analysis rely on mobility pattern. Specifically, if primary users move according to the random walk model, op￾timal throughput–delay tradeoff in the primary network can be achieved by the cell-partitioned TDMA scheme [13, Scheme 3]. Therefore, the results in Corollary 3 can be obtained following a similar argument as in Remark 1