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