Asymptotic Analysis on Secrecy Capacity in Large-Scale Wireless Networks

Asymptotic Analysis on Secrecy Capacity in Large-Scale Wireless Networks Jinbei Zhang,Luoyi Fu,Xinbing Wang Dept.of Electronic Engineering Shanghai Jiao Tong University,China Email:{abelchina,yiluofu,xwang8}@sjtu.edu.cn Abstract-Since wireless channel is vulnerable to eavesdrop- nodes and that of eavesdroppers,which requires the intend- pers,the secrecy during message delivery is a major concern ed receiver to have a stronger channel than eavesdroppers. in many applications such as commercial,governmental and military networks.This paper investigates information-theoretic Recently,securing wireless communications at the physical secrecy in large-scale networks and studies how capacity is layer is intriguing renewed interests among research area affected by the secrecy constraint where the locations and channel Haenggi [4]and Pinto et al.[5]study the in-degree and out- state information (CSI)of eavesdroppers are both unknown.We degree distributions under the security constraints.As is shown consider two scenarios:1)non-colluding case where eavesdrop- in both papers,even a small number of eavesdroppers will pers can only decode messages individually;and 2)colluding case cause dramatic decreasing in nodes'connectivity.To guarantee where eavesdroppers can collude to decode a message.For the non-colluding case,we show that the network secrecy capacity is the secret transmission,Geol and Negi [6]propose artificial not affected in order-sense by the presence of eavesdroppers.For noise generation to suppress eavesdroppers'receiving signal the colluding case,the per-node secrecy capacity of ()can The independence of fading channels is exploited to generate be achieved when the eavesdropper density(n)is O(n) noise to suppress eavesdroppers'channels taking advantage for any constant B>0 and decreases monotonously as of cooperative schemes [7]and multiple antennas [8].[9]. the density of eavesdroppers increases.The upper bounds on Furthermore,Barros et al.[10]show that theoretic information network secrecy capacity are derived for both cases and shown to be achievable by our scheme when ve(n)=O(nP)or secrecy can be achieved by fading alone if channel state (n)=(log),where ar is the path loss gain.We show information (CSI)is available. that there is a clear tradeoff between the security constraints However,so far the research about information theoretic and the achievable capacity.Furthermore,we also investigate the security mainly focuses on distinctive techniques to enhance impact of secrecy constraint on the capacity of dense network, the security,yet little is known about their impact on network the impact of active attacks and other traffic patterns as well as performance such as capacity,delay,etc,especially in large mobility models in the context. scale wireless networks.As some exceptions,Vasudevan et al. [12]study the secrecy capacity issue in a large-scale network. Specifically,they introduce helper nodes around transmitters to I.INTRODUCTION generate noise to degrade eavesdroppers'channel and utilize Although facilitating communications through quick de- channel fading gain of receivers to enhance secure commu- ployment and low cost,the broadcast nature of wireless nications.The impact of secrecy guard zone on capacity is channel makes it vulnerable to attacks such as eavesdropping investigated by Koyluoglu et al.[13]and Zhou et al.[14] and jamming,which are important concerns for commercial, On the other hand,what is the upper bound of secrecy capacity governmental and military networks.Traditional solutions are is unknown.Furthermore,some of pre-known information based on cryptographic methods such as the well-known RSA is needed in the previous works,such as pre-known CSI public key cryptosystem.However,due to the expensive key information of receivers or some pre-known location informa- distribution,the rapid growth of computation power and im- tion of eavesdroppers.These pre-known information can be provement on decoding technology,cryptographic techniques used by transmitters to differentiate receivers'channels from encounter some limitations,especially as the network size eavesdroppers'.And,in real applications it is difficult to obtain increases.Hence,to avoid such limitations,this paper focuses such information a prior,especially in large scale wireless on information theoretic security where eavesdroppers are networks.Therefore,a fundamental question arises:what will assumed to have infinite computational power. be the performance of secrecy capacity,if both the CSI and The basis for information theoretic security stems from location information are unknown to legitimate nodes? Shannon's notion of perfect secrecy [1],which is then ex- We are thus motivated to investigate this issue in static tended to noisy channels by Wyner [2]and later by Csiszar wireless networks.Our main idea to solve the aforementioned and Korner [3].Information theoretic security is achieved problem is to let a receiver distinguish its own channel by exploiting the difference between channels of legitimate by adopting self-interference cancelation.More precisely,we assume each receiver is equipped with three antennas,one for An earlier version of this paper appeared in the Proceedings of IEEE message reception and the other two for simultaneous artificial Infocom 2012(mini)[15]. noise generation to suppress eavesdroppers'channels.Since

1 Asymptotic Analysis on Secrecy Capacity in Large-Scale Wireless Networks Jinbei Zhang, Luoyi Fu, Xinbing Wang Dept. of Electronic Engineering Shanghai Jiao Tong University, China Email: {abelchina, yiluofu, xwang8}@sjtu.edu.cn Abstract—Since wireless channel is vulnerable to eavesdrop￾pers, the secrecy during message delivery is a major concern in many applications such as commercial, governmental and military networks. This paper investigates information-theoretic secrecy in large-scale networks and studies how capacity is affected by the secrecy constraint where the locations and channel state information (CSI) of eavesdroppers are both unknown. We consider two scenarios: 1) non-colluding case where eavesdrop￾pers can only decode messages individually; and 2) colluding case where eavesdroppers can collude to decode a message. For the non-colluding case, we show that the network secrecy capacity is not affected in order-sense by the presence of eavesdroppers. For the colluding case, the per-node secrecy capacity of Θ( √1 n ) can be achieved when the eavesdropper density ψe(n) is O(n−β), for any constant β > 0 and decreases monotonously as the density of eavesdroppers increases. The upper bounds on network secrecy capacity are derived for both cases and shown to be achievable by our scheme when ψe(n) = O(n−β) or ψe(n) = Ω(log α−2 α n), where α is the path loss gain. We show that there is a clear tradeoff between the security constraints and the achievable capacity. Furthermore, we also investigate the impact of secrecy constraint on the capacity of dense network, the impact of active attacks and other traffic patterns as well as mobility models in the context. I. INTRODUCTION Although facilitating communications through quick de￾ployment and low cost, the broadcast nature of wireless channel makes it vulnerable to attacks such as eavesdropping and jamming, which are important concerns for commercial, governmental and military networks. Traditional solutions are based on cryptographic methods such as the well-known RSA public key cryptosystem. However, due to the expensive key distribution, the rapid growth of computation power and im￾provement on decoding technology, cryptographic techniques encounter some limitations, especially as the network size increases. Hence, to avoid such limitations, this paper focuses on information theoretic security where eavesdroppers are assumed to have infinite computational power. The basis for information theoretic security stems from Shannon’s notion of perfect secrecy [1], which is then ex￾tended to noisy channels by Wyner [2] and later by Csisza´r and Ko¨rner [3]. Information theoretic security is achieved by exploiting the difference between channels of legitimate An earlier version of this paper appeared in the Proceedings of IEEE Infocom 2012(mini) [15]. nodes and that of eavesdroppers, which requires the intend￾ed receiver to have a stronger channel than eavesdroppers. Recently, securing wireless communications at the physical layer is intriguing renewed interests among research area. Haenggi [4] and Pinto et al. [5] study the in-degree and out￾degree distributions under the security constraints. As is shown in both papers, even a small number of eavesdroppers will cause dramatic decreasing in nodes’ connectivity. To guarantee the secret transmission, Geol and Negi [6] propose artificial noise generation to suppress eavesdroppers’ receiving signal. The independence of fading channels is exploited to generate noise to suppress eavesdroppers’ channels taking advantage of cooperative schemes [7] and multiple antennas [8], [9]. Furthermore, Barros et al. [10] show that theoretic information secrecy can be achieved by fading alone if channel state information (CSI) is available. However, so far the research about information theoretic security mainly focuses on distinctive techniques to enhance the security, yet little is known about their impact on network performance such as capacity, delay, etc, especially in large scale wireless networks. As some exceptions, Vasudevan et al. [12] study the secrecy capacity issue in a large-scale network. Specifically, they introduce helper nodes around transmitters to generate noise to degrade eavesdroppers’ channel and utilize channel fading gain of receivers to enhance secure commu￾nications. The impact of secrecy guard zone on capacity is investigated by Koyluoglu et al. [13] and Zhou et al. [14]. On the other hand, what is the upper bound of secrecy capacity is unknown. Furthermore, some of pre-known information is needed in the previous works, such as pre-known CSI information of receivers or some pre-known location informa￾tion of eavesdroppers. These pre-known information can be used by transmitters to differentiate receivers’ channels from eavesdroppers’. And, in real applications it is difficult to obtain such information a prior, especially in large scale wireless networks. Therefore, a fundamental question arises: what will be the performance of secrecy capacity, if both the CSI and location information are unknown to legitimate nodes? We are thus motivated to investigate this issue in static wireless networks. Our main idea to solve the aforementioned problem is to let a receiver distinguish its own channel by adopting self-interference cancelation. More precisely, we assume each receiver is equipped with three antennas, one for message reception and the other two for simultaneous artificial noise generation to suppress eavesdroppers’ channels. Since

the three antennas are all equipped on one node,the noise gain on capacity can increase linearly with the number of base generated by the receiver itself can be eliminated through station under certain circumstances.Multicast is a common the technique of antenna cancelation proposed in [17].This traffic pattern in real networks which makes the analysis much differs our noise generation pattern from previous works and more difficult.Li [24]proposes a tree-based routing scheme we will show in later part that such difference can dramatically to deal with it.More recently.Wang et al.[25]and Tang et improve network secrecy capacity. al.[26]study multicast capacity in hybrid networks.Mobility Our main contributions are summarized as follows: pattern plays an important part in wireless networks and Neely In the non-colluding case,the optimal per-node secrecy [19]uses queuing theory to study the delay and capacity.Hu capacity e()is achievable in the presence of eaves- [11]further study the multicast capacity in mobile large scale droppers.This result holds even in the scenario where networks.Brownian motion is an important mobility pattern there are more eavesdroppers than legitimate nodes in which is studied in [30]by Lin et al..Homogeneous mobility the network. pattern and uniform node density is the first step for the In the colluding case,we establish the relationship be- study on mobile networks.Garetto et al.[21]investigate the tween the secrecy capacity and the tolerable number heterogeneous cases which include a large body of mobility of eavesdroppers.More importantly,we first derive the models. upper bound for secrecy capacity which is achievable. We identify the underlying interference model to capture the fundamental impact of secrecy constraints.This mod- II.NETWORK MODELS AND DEFINITIONS el relies weakly on the specific settings such as traffic pattern and mobility models of legitimate nodes.Hence. In this paper,we consider a static ad hoc network in an our study can be flexibly applied to more general cases extended network男=[0，v问×O,√冗. and shed insights into the design and analysis of future Legitimate Nodes:Legitimate nodes follow a Poisson dis- wireless networks. tribution with unit intensity over the whole network.And transmitter-receiver pairs are randomly chosen such that each The rest of this paper is organized as follows.In Section II, node is the destination of exactly one source.We denote T we present the system model.Asymptotic analysis on different scenarios is carried out in Section III and IV.We investigate and R as the subsets of nodes simultaneously transmitting and receiving at a given time-slot.We assume that each legitimate the effect of dense network in Section V.Jamming as a node is equipped with three antennas.When a legitimate node different kind of network attacking is investigated in Section acts as a receiver,one antenna is used for message reception VI.Discussions and concluding remarks are given in Section while the other two are devoted to simultaneous artificial noise VII and VIII,respectively. generation to suppress eavesdroppers'channels.The distances between the receive antenna and the two respective transmit A.Related Works antennas should satisfy a difference of half the wavelength. Asymptotic analysis can provide fundamental insight on The interference can therefore be eliminated using the tech- network performance as the network size increases.The nique of self-interference cancelation proposed in [17]. ground-breaking work is initiated by Gupta and Kumar [18]. Eavesdroppers:Independently of legitimate nodes,eaves- who study capacity performance in a network with n randomly droppers also follow a Poisson distribution in the network distributed nodes.They show that the per-node capacity is with intensity Ae.Let be the set of eavesdroppers.We lower bounded by )and upper bounded by assume eavesdroppers always keep silent since they will be easily detected if active.In order to have an insight on This gap is closed later by Franceschetti et al.[20]using the fundamental information theoretical secrecy capacity,we percolation theory.The fundamental difference behind these assume eavesdroppers have infinite computation ability which two works is the underlying connectivity.The communication means that traditional cryptography method can not be applied range in [1]should be to guarantee full connec- here.We also assume that both CSI and location information tivity whereas it only needs to be (in [20]to guarantee of eavesdroppers are unknown to legitimate nodes. partial connectivity at the bottleneck.Later on,Grossglauser The Physical Model:For simplicity,we denote uniform and Tse [23]further indicate the capacity can be improved transmission power as P:and uniform noise generation power to e(1)when mobility is introduced to nodes,at the expense as Pr.The path loss between node i and node j is denoted by of increased delay [19].Since then,asymptotic analysis has I(zi,j).which can be expressed as l(xi,rj)=min(1,dij). drawn considerable attention in research area and we will give Here di;is the transmission distance and the loss exponent a brief introduction in the following. o >2.When node i is transmitting messages to node j,the While interference always has an negative effect on wireless signal to interference and noise ratio (SINR)received by node communication,MIMO technology turns it into useful signal j over a channel of unit bandwidth can be given by: and hence greatly enhance the communication.In [28].Ozgur et al.propose an iterative MIMO scheme to obtain a constant Pl(xi,Ej) per-node capacity which is a great improvement compared to hop-by-hop transmissions.Infrastructure is another effective SINR)=+∑en间PIr,)+2keR)P(k,' way to overcome the interference.Liu et al.[27]prove that the where No denotes the ambient noise power at the receiver

2 the three antennas are all equipped on one node, the noise generated by the receiver itself can be eliminated through the technique of antenna cancelation proposed in [17]. This differs our noise generation pattern from previous works and we will show in later part that such difference can dramatically improve network secrecy capacity. Our main contributions are summarized as follows: • In the non-colluding case, the optimal per-node secrecy capacity Θ( √ 1 n ) is achievable in the presence of eaves￾droppers. This result holds even in the scenario where there are more eavesdroppers than legitimate nodes in the network. • In the colluding case, we establish the relationship be￾tween the secrecy capacity and the tolerable number of eavesdroppers. More importantly, we first derive the upper bound for secrecy capacity which is achievable. • We identify the underlying interference model to capture the fundamental impact of secrecy constraints. This mod￾el relies weakly on the specific settings such as traffic pattern and mobility models of legitimate nodes. Hence, our study can be flexibly applied to more general cases and shed insights into the design and analysis of future wireless networks. The rest of this paper is organized as follows. In Section II, we present the system model. Asymptotic analysis on different scenarios is carried out in Section III and IV. We investigate the effect of dense network in Section V. Jamming as a different kind of network attacking is investigated in Section VI. Discussions and concluding remarks are given in Section VII and VIII, respectively. A. Related Works Asymptotic analysis can provide fundamental insight on network performance as the network size increases. The ground-breaking work is initiated by Gupta and Kumar [18], who study capacity performance in a network with n randomly distributed nodes. They show that the per-node capacity is lower bounded by Ω(√ 1 n log n ) and upper bounded by O( √ 1 n ). This gap is closed later by Franceschetti et al. [20] using percolation theory. The fundamental difference behind these two works is the underlying connectivity. The communication range in [18] should be Θ(￾log n n ) to guarantee full connec￾tivity whereas it only needs to be Θ(￾ 1 n ) in [20] to guarantee partial connectivity at the bottleneck. Later on, Grossglauser and Tse [23] further indicate the capacity can be improved to Θ(1) when mobility is introduced to nodes, at the expense of increased delay [19]. Since then, asymptotic analysis has drawn considerable attention in research area and we will give a brief introduction in the following. While interference always has an negative effect on wireless communication, MIMO technology turns it into useful signal and hence greatly enhance the communication. In [28], Ozg ¨ ur¨ et al. propose an iterative MIMO scheme to obtain a constant per-node capacity which is a great improvement compared to hop-by-hop transmissions. Infrastructure is another effective way to overcome the interference. Liu et al. [27] prove that the gain on capacity can increase linearly with the number of base station under certain circumstances. Multicast is a common traffic pattern in real networks which makes the analysis much more difficult. Li [24] proposes a tree-based routing scheme to deal with it. More recently, Wang et al. [25] and Tang et al. [26] study multicast capacity in hybrid networks. Mobility pattern plays an important part in wireless networks and Neely [19] uses queuing theory to study the delay and capacity. Hu [11] further study the multicast capacity in mobile large scale networks. Brownian motion is an important mobility pattern which is studied in [30] by Lin et al.. Homogeneous mobility pattern and uniform node density is the first step for the study on mobile networks. Garetto et al. [21] investigate the heterogeneous cases which include a large body of mobility models. II. NETWORK MODELS AND DEFINITIONS In this paper, we consider a static ad hoc network in an extended network B = [0, √n] × [0, √n]. Legitimate Nodes: Legitimate nodes follow a Poisson dis￾tribution with unit intensity over the whole network. And transmitter-receiver pairs are randomly chosen such that each node is the destination of exactly one source. We denote T and R as the subsets of nodes simultaneously transmitting and receiving at a given time-slot. We assume that each legitimate node is equipped with three antennas. When a legitimate node acts as a receiver, one antenna is used for message reception while the other two are devoted to simultaneous artificial noise generation to suppress eavesdroppers’ channels. The distances between the receive antenna and the two respective transmit antennas should satisfy a difference of half the wavelength. The interference can therefore be eliminated using the tech￾nique of self-interference cancelation proposed in [17]. Eavesdroppers: Independently of legitimate nodes, eaves￾droppers also follow a Poisson distribution in the network with intensity λe. Let E be the set of eavesdroppers. We assume eavesdroppers always keep silent since they will be easily detected if active. In order to have an insight on the fundamental information theoretical secrecy capacity, we assume eavesdroppers have infinite computation ability which means that traditional cryptography method can not be applied here. We also assume that both CSI and location information of eavesdroppers are unknown to legitimate nodes. The Physical Model: For simplicity, we denote uniform transmission power as Pt and uniform noise generation power as Pr. The path loss between node i and node j is denoted by l(xi, xj ), which can be expressed as l(xi, xj ) = min(1, d−α ij ). Here dij is the transmission distance and the loss exponent α > 2. When node i is transmitting messages to node j, the signal to interference and noise ratio (SINR) received by node j over a channel of unit bandwidth can be given by: SINRij = Ptl(xi, xj ) N0 + k∈T \{i} Ptl(xk, xj ) + k∈R\{j} Prl(xk, xj ) , where N0 denotes the ambient noise power at the receiver.

3 The SINR received by eavesdropper e can be represented by:where dr is the Euclidean distance between legitimate node Pl(x,xe） t and node r and dte is the distance between legitimate node SNRe=NO+∑kenP(,)+2keRP,7,万 t and eavesdropper e. Proof:First we prove the maximum SINR that eaves- Secrecy Throughput Per Hop:As is defined in [3].the secure droppers can obtain is(+dt).Consider the following throughput between any active transmitter-receiver pair is: four cases. Case 1:When dte and dre are both greater than 1,then RijRij Rie log2(1 SINRij)-log2(1+SINRie) where SINRie maxeEe SINRie. SINR= Pl(xt,xe】 Asymptotic Capacity:Asymptotic per node capacity A(n) NO+∑ke八ePl(rk,Ee)+∑keRP,(zk,e】 is said to be achievable if there is a scheduling and routing scheme such that every node can transmit A(n)bits per second Pl(rt,xe） Pidieo < on average to its destination in the long term. Pl(Er,Ie) Prdre Knuth Notations:Denote A(n)=O(f(n))if there is a Pidie positive constant c such that limP( ≤c)=1 ≤p,.(dt+de and (n)=(f(n))if f(n)=O((n)).A(n)is said to be e(f(n))if both (n)=O(f(n))and (n)=(f(n))hold. P. dte s层a*n In Table 1,we list the parameters that will be frequently (2) used in later analysis,proofs and discussions. Case 2:When dte 1 and dre <=1,it is obvious to see that eavesdroppers's interference is more severe than that in TABLE I:Notations case 1 while the signal received is not stronger than that in case 1.So the bound still holds. Notation Definition Case 3:When dte <1 and dre 1,we can easily see n The total number of legitimate nodes in the network. that the path loss gain of T-E pair is 1 when the bound derived 入s(n) The per-node secrecy capacity. in case I holds,which means that the bound cannot be broken ve(n The expected density of poisson distributed eaves- by condition dte <=1. droppers. Case 4:When dte <1 and dre <1,the SINR at P The power to transmit packets. eavesdroppers will not be greater than that in case 3 since P The power to generate noise. eavesdroppers in case 4 suffer more interference.Hence the bound still holds. R(d) The rate that a transmitter can transmit to an intend- ed receiver which is located d distance away. Notice that SINR maller thanHence.sinee Re The rate that an eavesdropper can obtain from a Re log(1+max(SINRe)),it is straightforward to conclude transmitting node. this lemma. Ra(d) The rate that a transmitter can securely transmit to an From the analysis,we can see that the rate is tight in order intended receiver which is located d distance away. sense when dir=e(1).And according to our following analysis,the bottleneck of secrecy capacity lies in the highway phase where dtr=e(1).Hence,from this point of view,this III.SECURITY CAPACITY FOR INDEPENDENT rate is tight. EAVESDROPPERS CASE A.The Highway System In this section,we investigate secrecy capacity for indepen- dent eavesdroppers.We use percolation theory to construct The network is divided into non-overlapping cells with side the routing scheme which contains three phases,e.g.,draining length of c.where c is a constant.We say that a cell is open phase,highway transmission and delivery phase.Since our if there is at least one node in it.Hence cells are open with scheme should guarantee the secrecy communication,it seems probability p=1-e-independently. that the capacity should be degraded.However,we show For ease of exposition,denote m as vn/v2c and we assume m to be an integer,which will not change our results in that regardless of the fact that the capacity will be sacrificed to ensure secrecy in draining phase and delivery phase,the order sense.As is shown in [20],when the constant c is large bottleneck still lies in the highway phase where the secrecy enough,there are a lot of crossing paths in the network which capacity remains the same as that in the network without behave almost as straight lines.For any >0,partition the eavesdroppers. network into rectangles of size m x(K log m-em)and choose We present the following lemma which will be quoted em=o(1)as the smallest value such that the side length is an throughout this paper. integer.Denote Ri as the ith rectangle and Ci as the number Lemma 1:When a legitimate node t is transmitting to a of edge-disjoint crossings of Ri.Then the minimal number of legitimate receiver r,the maximum rate that an independent disjoint crossing paths Np=min;Ci can be upper bounded by eavesdropper e can obtain is upper-bounded by 6logm when m goes to infinity and 6 is a constant.Further, to make sure that there are at least as many paths as slices Re≤min Pidie P(+du) inside each rectangle,each rectangle is sliced into horizontal No P. (1) strips with constant w=k log m/Np

3 The SINR received by eavesdropper e can be represented by: SINRie = Ptl(xi, xe) N0 + ￾ k∈T \{i} Ptl(xk, xe) + ￾ k∈R Prl(xk, xe) . Secrecy Throughput Per Hop: As is defined in [3], the secure throughput between any active transmitter-receiver pair is: Rs ij = Rij − Rie = log2(1 + SINRij ) − log2(1 + SINRie) where SINRie = maxe∈E SINRie. Asymptotic Capacity: Asymptotic per node capacity λ(n) is said to be achievable if there is a scheduling and routing scheme such that every node can transmit λ(n) bits per second on average to its destination in the long term. Knuth Notations: Denote λ(n) = O(f(n)) if there is a positive constant c1 such that limn→∞ P( λ(n) f(n) ≤ c1)=1 and λ(n) = Ω(f(n)) if f(n) = O(λ(n)). λ(n) is said to be Θ(f(n)) if both λ(n) = O(f(n)) and λ(n) = Ω(f(n)) hold. In Table 1, we list the parameters that will be frequently used in later analysis, proofs and discussions. TABLE I: Notations Notation Definition n The total number of legitimate nodes in the network. λs(n) The per-node secrecy capacity. ψe(n) The expected density of poisson distributed eaves￾droppers. Pt The power to transmit packets. Pr The power to generate noise. R(d) The rate that a transmitter can transmit to an intend￾ed receiver which is located d distance away. Re The rate that an eavesdropper can obtain from a transmitting node. Rs(d) The rate that a transmitter can securely transmit to an intended receiver which is located d distance away. III. SECURITY CAPACITY FOR INDEPENDENT EAVESDROPPERS CASE In this section, we investigate secrecy capacity for indepen￾dent eavesdroppers. We use percolation theory to construct the routing scheme which contains three phases, e.g., draining phase, highway transmission and delivery phase. Since our scheme should guarantee the secrecy communication, it seems that the capacity should be degraded. However, we show that regardless of the fact that the capacity will be sacrificed to ensure secrecy in draining phase and delivery phase, the bottleneck still lies in the highway phase where the secrecy capacity remains the same as that in the network without eavesdroppers. We present the following lemma which will be quoted throughout this paper. Lemma 1: When a legitimate node t is transmitting to a legitimate receiver r, the maximum rate that an independent eavesdropper e can obtain is upper-bounded by Re ≤ min Ptd−α te N0 , Pt Pr (1 + dtr) α , (1) where dtr is the Euclidean distance between legitimate node t and node r and dte is the distance between legitimate node t and eavesdropper e. Proof: First we prove the maximum SINR that eaves￾droppers can obtain is Pt Pr (1 + drt)α. Consider the following four cases. Case 1: When dte and dre are both greater than 1, then SINRe = Ptl(xt, xe) N0 + ￾ k∈T \{t} Ptl(xk, xe) + ￾ k∈R Prl(xk, xe) < Ptl(xt, xe) Prl(xr, xe) = Ptd−α te Prd−α re ≤ Ptd−α te Pr(drt + dte)−α = Pt Pr  1 + drt dte α ≤ Pt Pr (1 + drt) α. (2) Case 2: When dte > 1 and dre <= 1, it is obvious to see that eavesdroppers’s interference is more severe than that in case 1 while the signal received is not stronger than that in case 1. So the bound still holds. Case 3: When dte <= 1 and dre > 1, we can easily see that the path loss gain of T-E pair is 1 when the bound derived in case 1 holds, which means that the bound cannot be broken by condition dte <= 1. Case 4: When dte <= 1 and dre <= 1, the SINR at eavesdroppers will not be greater than that in case 3 since eavesdroppers in case 4 suffer more interference. Hence the bound still holds. Notice that SINRe is also smaller than Ptd−α te N0 . Hence, since Re = log(1 + max(SINRe)), it is straightforward to conclude this lemma. From the analysis, we can see that the rate is tight in order sense when dtr = Θ(1). And according to our following analysis, the bottleneck of secrecy capacity lies in the highway phase where dtr = Θ(1). Hence, from this point of view, this rate is tight. A. The Highway System The network is divided into non-overlapping cells with side length of c, where c is a constant. We say that a cell is open if there is at least one node in it. Hence cells are open with probability p = 1 − e−c2 independently. For ease of exposition, denote m as √n/√2c and we assume m to be an integer, which will not change our results in order sense. As is shown in [20], when the constant c is large enough, there are a lot of crossing paths in the network which behave almost as straight lines. For any κ > 0, partition the network into rectangles of size m×(κ log m−m) and choose m = o(1) as the smallest value such that the side length is an integer. Denote Ri as the ith rectangle and Ci as the number of edge-disjoint crossings of Ri. Then the minimal number of disjoint crossing paths Np = mini Ci can be upper bounded by δ log m when m goes to infinity and δ is a constant. Further, to make sure that there are at least as many paths as slices inside each rectangle, each rectangle is sliced into horizontal strips with constant w = κ log m/Np.

Note that Iw 2,8ilc）-converges to a constant when≥ 2. Since the distance from the transmitter to the designated receiver is at most c(d+1),the receiving signal S(d)can be lower-bounded by S(d≥Pl(c(d+1) (4) =P(c(d+1)-a Notice that l(c(d+1))=(c(d+1))-since d is an integer and c is greater than 1. Fig.1:There are at least 6logm disjoint highways in each Now the accurate rate that the legitimate receiver may rectangle.Nodes in i-th slice will transmit to nodes located in achieve can be derived as follows: the i-th highway and crosses denote eavesdroppers. R(d)=log1+ S(d) No+I(d) Our packet routing scheme includes three steps: P(c(d+1)-a Step 1:Each source in the i-th slice transmits directly to a ≥1og)1+No+4B+Pk@- (5 legitimate relay located on the i-th path.The relay is chosen in a way such that it is closest to the source among all other 2c2P(c(d+1)-a nodes on the i-th path,as is shown in Fig.1. ≥c2Pdra Step 2:Packets are relayed horizontally through the high- way and then along a vertical highway until it arrives at an when choosing k=(P,)and c2 is a constant. ◆ exit point closest to the destination in a multi-hop fashion. Now we will show that secrecy communication can be as- Step 3:Packets are directly delivered from the highway to sured for any T-R pairs by appropriately spacing for concurrent the destination similar to the first step. transmissions. Theorem 1:For any legitimate transmitter-receiver pair B.Analysis of Secrecy Capacity which is spaced at a distance of d cells apart,there exists Next we present our scheduling scheme and compute the an Ra(d)=(d--4).so that the receiver can receive at a lower bound of the legitimate receiver's rate.Note that our rate of Rs(d)securely from the transmitter. scheduling scheme is different from that proposed in [20], Proof:According to the definition of secure rate and since we should take the issue of secrecy into account.And combining with Lemma I and Lemma 2,the secrecy rate the basic idea is to space concurrent transmission sufficiently R.(d)each cell can transmit can be denoted as: far away so that the interference is tolerable Lemma 2:When a legitimate node is transmitting to a 1 legitimate receiver which is located d cells apart,the minimum R,间=k+(R④-R) (6 rate that the legitimate node can receive is lower-bounded by 1 P c2Pid-,where c2 is a constant. ≥依+)eaRd“-esgr( Proof:First we compute the interference at the receiver. Divide the network into disjoint subsquares of (k+d)x ( where is the time utilization factor,ca and ca are both constants. d)cells,where k will be explained later.Every cell in each subsquare takes turn to transmit.Consider a given transmitter- Let P,=2d20.Hence,to bound the interference in- receiver pair,the eight closest transmitters and receivers are curred to the intended receiver,according to Equation (5) located at distance of at least ck and c(k+d-1)from the k=e(p)=e(d2).Therefore,the secrecy rate each cell receiver.The sixteen next closest transmitters and receivers can receive is (d--4). ◆ are located at distance at least c(2k+d)and c(2k+2d-1) Theorem 1 indicates positive secrecy rate is achievable even away from the receiver and so on.Taking into consideration under the worst attack.In order to calculate per-node secrecy all the interferences in the whole network,the interference at capacity,we first compute the number of legitimate nodes in the intended destination can be upper-bounded as follows: each cell and then derive the traffic load that each node in Id≤∑8i(P,lc(ik+d-d)+P,lc(ik+d-1)》 the highway should relay,as are shown in the following two lemmas. i=1 Lemma 3:There are at most log n legitimate nodes in each ≤28R+Plea cell of constant size c=w.h.p.. =1 =(P+P)(kc)-8i(ci)-a. i=1 In this paper,w.h.p stands for with high probability.which means the (3)probability tends to 1 as n goes to infinity

4   Fig. 1: There are at least δ log m disjoint highways in each rectangle. Nodes in i-th slice will transmit to nodes located in the i-th highway and crosses denote eavesdroppers. Our packet routing scheme includes three steps: Step 1: Each source in the i-th slice transmits directly to a legitimate relay located on the i-th path. The relay is chosen in a way such that it is closest to the source among all other nodes on the i-th path, as is shown in Fig. 1. Step 2: Packets are relayed horizontally through the high￾way and then along a vertical highway until it arrives at an exit point closest to the destination in a multi-hop fashion. Step 3: Packets are directly delivered from the highway to the destination similar to the first step. B. Analysis of Secrecy Capacity Next we present our scheduling scheme and compute the lower bound of the legitimate receiver’s rate. Note that our scheduling scheme is different from that proposed in [20], since we should take the issue of secrecy into account. And the basic idea is to space concurrent transmission sufficiently far away so that the interference is tolerable. Lemma 2: When a legitimate node is transmitting to a legitimate receiver which is located d cells apart, the minimum rate that the legitimate node can receive is lower-bounded by c2Ptd−α, where c2 is a constant. Proof: First we compute the interference at the receiver. Divide the network into disjoint subsquares of (k + d) × (k + d) cells, where k will be explained later. Every cell in each subsquare takes turn to transmit. Consider a given transmitter￾receiver pair, the eight closest transmitters and receivers are located at distance of at least ck and c(k + d − 1) from the receiver. The sixteen next closest transmitters and receivers are located at distance at least c(2k + d) and c(2k + 2d − 1) away from the receiver and so on. Taking into consideration all the interferences in the whole network, the interference at the intended destination can be upper-bounded as follows: I(d) ≤ ￾∞ i=1 8i(Ptl(c(i(k + d) − d)) + Prl(c(i(k + d) − 1))) ≤ ￾∞ i=1 8i(Pt + Pr)l(cik) = (Pt + Pr)(kc) −α￾∞ i=1 8i(ci) −α. (3) Note that ∞ i=1 8i(ci)−α converges to a constant c 1 when α ≥ 2. Since the distance from the transmitter to the designated receiver is at most c(d + 1), the receiving signal S(d) can be lower-bounded by S(d) ≥ Ptl(c(d + 1)) = Pt(c(d + 1))−α. (4) Notice that l(c(d + 1)) = (c(d + 1))−α since d is an integer and c is greater than 1. Now the accurate rate that the legitimate receiver may achieve can be derived as follows: R(d) = log 1 + S(d) N0 + I(d)  ≥ log  1 + Pt(c(d + 1))−α N0 + c 1(Pt + Pr)(kc)−α  ≥ c 2Pt(c(d + 1))−α ≥ c2Ptd−α, (5) when choosing k = Θ(P 1 α r ) and c2 is a constant. Now we will show that secrecy communication can be as￾sured for any T-R pairs by appropriately spacing for concurrent transmissions. Theorem 1: For any legitimate transmitter-receiver pair which is spaced at a distance of d cells apart, there exists an Rs(d) = Ω(d−α−4), so that the receiver can receive at a rate of Rs(d) securely from the transmitter. Proof: According to the definition of secure rate and combining with Lemma 1 and Lemma 2, the secrecy rate Rs(d) each cell can transmit can be denoted as: Rs(d) = 1 (k + d)2 (R(d) − Re) ≥ 1 (k + d)2 c2Ptd−α − c3 Pt Pr dα  (6) where 1 (k+d)2 is the time utilization factor, c2 and c3 are both constants. Let Pr = 2 c3 c2 d2α. Hence, to bound the interference in￾curred to the intended receiver, according to Equation (5), k = Θ(P 1 α r ) = Θ(d2). Therefore, the secrecy rate each cell can receive is Ω(d−α−4). Theorem 1 indicates positive secrecy rate is achievable even under the worst attack. In order to calculate per-node secrecy capacity, we first compute the number of legitimate nodes in each cell and then derive the traffic load that each node in the highway should relay, as are shown in the following two lemmas. Lemma 3: There are at most log n legitimate nodes in each cell of constant size c2 w.h.p.1. 1In this paper, w.h.p stands for with high probability, which means the probability tends to 1 as n goes to infinity.

Proof:Let A;be the number of legitimate nodes in cell Theorem 1.According to the routing scheme,each source i and A be the maximum number of A;.Hence,we have in the i-th slice transmit packets to the i-th highway in the P(A≥logn)=P(maxA.≥logn) same rectangle.Since the density of legitimate nodes is 1 and the size of each slice is wvn,which satisfy the conditions ≤P(U(A:≥logn) given by Lemma 4,we obtain that the maximum number of ≤P(A:≥logn) legitimate nodes inside each slice is no larger than 2wvn. Hence,the traffic load on each relay node in the highway is ne-c e2 logn at most 2wn nodes.Therefore,the secrecy capacity of the ≤2e logn highway phase is). Based on the results above,we conclude that per-node 1 c2e1+1/c2 secrecy capacity is(). ■ →0. log n Note that the third inequality follows from union bounds and C.The Optimality of Our Scheme the fourth one follows from Chernoff bounds [31]. We first consider the case where no eavesdropper exists in Lemma 4:If nodes are poisson distributed with intensity the network.Due to the broadcast nature of wireless channel, (n)in the network,partition the network into disjoint every concurrent transmission will incure interference to other regions with same size f(n),let Ni be the number of nodes transmissions.The following lemma shows that there is a inside region i.We have constraint on the total network throughput underlying this P(传foe回≤≤2f回.i）=1 fundamental physical model. Lemma 5:When n nodes are identically and randomly located in a wireless network and source-destination pairs when f(n)v(n)>logale n and f(n)=(1). are randomly chosen,the per-node throughput A(n)is upper Proof:The number of nodes inside each region N;is a poisson variable and denote its expectation as Hence,we bounded by () Proof:Let L be the expected distance between all source- have =E(Ni)=f(n)(n).Letting N be the maximum destination pairs.Hence L=θ（√m）l8l.Denote r and number of Ni,for all i.Under similar derivation of Lemma T(r)as the average transmission range and rate of each hop 3,we can get that respectively.Let I be the average distance that simultaneous 12 PN≥2fmm)≤fPN≥2fm)w(n) transmissions can occure.Since the expected number of hops that a packet should travel is L/r,the total traffic load eψ 、2g the network should carry is nA(n)L/r.And the total traffic ≤e中 2b/ that the network can carry is (r).Hence,we obtain f(n)(n)】 (7) n thatn(m)Lr≤T(rl,which means(n)≤只 Substituting T(r)into the equation,we have ≤m→0 .T(r) Pmin(1,r-a)） Am）≤P√7=NO+ZAE同P,写BV7 when f(n)v(n)>logale n and f(n)=(1). where T denotes the set of concurrent transmission nodes and Similarly,we can show that min;Ni is greater than I(k,)denotes the path loss gain. f(n)(n)w.h.p.when conditions hold. ■ It is easily verified that min(r,r1-)=O(1).Next We Theorem 2:With n legitimate nodes randomly distributed in the achievable per-node secrecy throughput under the show that (No+)l(k))2=(1).If (1),the result is straightforward.If I=o(1).there would be existence of independent eavesdroppers is () e()concurrent transmission nodes inside unit area around Proof:As is shown in the routing scheme,the maximum the receiver and the path loss gain between these nodes and distance between source and relay on the highway is no larger the intended receiver is e(1).Therefore,the result holds. than klogm+2c in the first step.Applying Theorem 1.we Since the per-node throughput without the secrecy constraint obtain that one node in the cell can transmit securely at rate is O().the per-node secrecy capacity can also be bounded (log-n)to the relay.Since there may be multiple nodes inside the cell,they should share the transmission chances.The by O()which indicates the optimality of our scheme. number of nodes inside each cell can be bounded as O(logn) according to Lemma 3.Hence,the achievable secrecy capacity IV.COLLUDING EAVESDROPPERS is (log-5n)in the draining phase.Note that since the In previous section,the maximum SINR received by an delivery phase is a reverse process of the draining phase,the independent eavesdropper can be suppressed by artificial noise secrecy capacity of the delivery phase is the same as that of generation.And it has already been shown that the per-node draining phase. throughput does not entail lost,regardless of how many eaves- In the highway phase,the transmission range between T-R droppers are present in the network.However,if eavesdroppers pairs is at most 2v2c.Hence each node on the highway can are equipped with multiple antennas or multiple eavesdroppers transmit securely at rate (1)to the next relay by applying can collude to decode the messages,is it still possible to

5 Proof: Let Ai be the number of legitimate nodes in cell i and A be the maximum number of Ai. Hence, we have P(A ≥ log n) = P (max Ai ≥ log n) ≤ P (∪i(Ai ≥ log n)) ≤ ￾ i P(Ai ≥ log n) ≤ n c2 e−c2 c2e log n c2 log n = 1 c2 e−c2 c2e1+1/c2 log n c2 log n → 0. Note that the third inequality follows from union bounds and the fourth one follows from Chernoff bounds [31]. Lemma 4: If nodes are poisson distributed with intensity ψ(n) in the network B, partition the network into disjoint regions with same size f(n), let Ni be the number of nodes inside region i. We have P 1 2 f(n)ψ(n) ≤ Ni ≤ 2f(n)ψ(n), ∀i  = 1 when f(n)ψ(n) ≥ log4/e n and f(n) = Ω(1). Proof: The number of nodes inside each region Ni is a poisson variable and denote its expectation as ψ. Hence, we have ψ = E(Ni) = f(n)ψ(n). Letting N be the maximum number of Ni, for all i. Under similar derivation of Lemma 3, we can get that P(N ≥ 2f(n)ψ(n)) ≤ n f(n) P(Ni ≥ 2f(n)ψ(n)) ≤ n f(n) e−ψ eψ 2ψ 2ψ = n f(n) e 4 f(n)ψ(n) ≤ 1 f(n) → 0 (7) when f(n)ψ(n) ≥ log4/e n and f(n) = Ω(1). Similarly, we can show that mini Ni is greater than 1 2 f(n)ψ(n) w.h.p. when conditions hold. Theorem 2: With n legitimate nodes randomly distributed in B, the achievable per-node secrecy throughput under the existence of independent eavesdroppers is Ω( √ 1 n ). Proof: As is shown in the routing scheme, the maximum distance between source and relay on the highway is no larger than κ log m + 2c in the first step. Applying Theorem 1, we obtain that one node in the cell can transmit securely at rate Ω(log−α−4 n) to the relay. Since there may be multiple nodes inside the cell, they should share the transmission chances. The number of nodes inside each cell can be bounded as O(log n) according to Lemma 3. Hence, the achievable secrecy capacity is Ω(log−α−5 n) in the draining phase. Note that since the delivery phase is a reverse process of the draining phase, the secrecy capacity of the delivery phase is the same as that of draining phase. In the highway phase, the transmission range between T-R pairs is at most 2 √2c. Hence each node on the highway can transmit securely at rate Ω(1) to the next relay by applying Theorem 1. According to the routing scheme, each source in the i-th slice transmit packets to the i-th highway in the same rectangle. Since the density of legitimate nodes is 1 and the size of each slice is w√n, which satisfy the conditions given by Lemma 4, we obtain that the maximum number of legitimate nodes inside each slice is no larger than 2w√n. Hence, the traffic load on each relay node in the highway is at most 2w√n nodes. Therefore, the secrecy capacity of the highway phase is Ω( √ 1 n ). Based on the results above, we conclude that per-node secrecy capacity is Ω( √ 1 n ). C. The Optimality of Our Scheme We first consider the case where no eavesdropper exists in the network. Due to the broadcast nature of wireless channel, every concurrent transmission will incure interference to other transmissions. The following lemma shows that there is a constraint on the total network throughput underlying this fundamental physical model. Lemma 5: When n nodes are identically and randomly located in a wireless network and source-destination pairs are randomly chosen, the per-node throughput λ(n) is upper bounded by O( √ 1 n ). Proof: Let L be the expected distance between all source￾destination pairs. Hence L = Θ(√n) [18]. Denote r and T(r) as the average transmission range and rate of each hop respectively. Let l be the average distance that simultaneous transmissions can occure. Since the expected number of hops that a packet should travel is L/r, the total traffic load the network should carry is nλ(n)L/r. And the total traffic that the network can carry is n l2 T(r). Hence, we obtain that nλ(n)L/r ≤ n l2 T(r), which means λ(n) ≤ rT(r) l2√n . Substituting T(r) into the equation, we have λ(n) ≤ rT(r) l2√n = Pt min(1, r−α) N0 + k∈T \{i} Ptl(xk, xj ) r l2√n where T denotes the set of concurrent transmission nodes and l(xk, xr) denotes the path loss gain. It is easily verified that min(r, r1−α) = O(1). Next We show that (N0 + k∈T \{i} Ptl(xk, xr))l 2 = Ω(1). If l = Ω(1), the result is straightforward. If l = o(1), there would be Θ( 1 l2 ) concurrent transmission nodes inside unit area around the receiver and the path loss gain between these nodes and the intended receiver is Θ(1). Therefore, the result holds. Since the per-node throughput without the secrecy constraint is O( √ 1 n ), the per-node secrecy capacity can also be bounded by O( √ 1 n ) which indicates the optimality of our scheme. IV. COLLUDING EAVESDROPPERS In previous section, the maximum SINR received by an independent eavesdropper can be suppressed by artificial noise generation. And it has already been shown that the per-node throughput does not entail lost, regardless of how many eaves￾droppers are present in the network. However, if eavesdroppers are equipped with multiple antennas or multiple eavesdroppers can collude to decode the messages, is it still possible to