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 V63<2,k:< (Yj,YRx())and (Xi,XRx()triggers Yi interchangeably. 63csnL2,V61 >0,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 .