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