Optimal Secrecy Capacity-Delay Tradeoff in Large-Scale Mobile Ad Hoc Networks

Optimal Secrecy Capacity-Delay Tradeoff in Large-Scale Mobile Ad Hoc Networks Xuanyu Cao,Jinbei Zhang,Luoyi Fu,Weijie Wu,Xinbing Wang Abstract-In this paper,we investigate the impact of paper,i.e.,safety is ensured even though the eavesdroppers information-theoretic secrecy constraint on the capacity and delay have infinite computational and decoding power. of mobile ad hoc networks (MANETs)with mobile legitimate nodes and static eavesdroppers whose location and channel state The study of information-theoretic secrecy originates from information (CSI)are both unknown.We assume n legitimate the seminal works of Shannon [1].Wyner [2],Csiszar and nodes move according to the fast i.i.d.mobility pattern and each Korner [3],where the secrecy requires the receiver to have desires to communicate with one randomly selected destination better channel than eavesdroppers.Recently,a few schemes node.There are also n'static eavesdroppers located uniformly in the network and we assume the number of eavesdroppers are proposed to guarantee the secret communication.Geol is much larger than that of legitimate nodes,i.e,>1.We and Negi [4]exploit artificial noise to suppress the SNR at propose a novel simple secure communication model,i.e.,the the eavesdroppers so as to ensure security.Independence of secure protocol model,and prove its equivalence to the widely wireless fading channels are also used to generate noise with accepted secure physical model under a few technical assumptions. cooperation [5]and multiple antennas [6,7]. Based on the proposed model,a framework of analyzing the secrecy capacity and delay in MANETs is established.Given a While the above mentioned works all focus on proposing delay constraint D,we find that the optimal secrecy throughput various techniques to ensure information-theoretic security,a capacity is'(W(),where W is the data rate of each link. few papers also investigate the impact of the secrecy constraint We observe that:1)the capacity-delay tradeoff is independent on the network capacity and delay.For example,Vasudevan of the number of eavesdroppers,which indicates that adding et al.[8]study the secrecy-capacity tradeoff in large-scale more eavesdroppers will not degenerate the performance of the wireless networks and introduce helpers around the transmitters legitimate network as long as>1;2)the capacity-delay tradeoff of our paper outperforms the previous resultin[11]. to generate noise to suppress the SNR at the eavesdroppers. Capar et al.[9]propose a new secrecy communication scheme where e=n"1=w(1)is the density of the eavesdroppers. that can tolerateeavesdroppers while keeping the network throughput not affected.To transmit a single bit,the I.INTRODUCTION authors proposed to generate multiple bits and transmit all of Though having the advantage of convenience and low cost, them to the desired destinations through different paths.The wireless networks are vulnerable to attacks such as eavesdrop- original bit can be decoded if and only if all of the generated ping and jamming due to its broadcast nature.Most of existing bits are obtained and the authors present a routing/scheduling solutions are based on cryptographic methods,e.g.,RSA public protocol to make sure no eavesdroppers could get all those bits. key crypto-system.However,there two major drawbacks of A very related work is a recent paper by Zhang et al.[10].The the cryptographic solutions.First,the key distribution can be authors let every receiver generate artificial noise in order to very costly in terms of both energy consumption and compu- degrade the SNR at the eavesdroppers and study the impact of secrecy constraints on the capacity scaling in static networks. tation/decoding capability because of the rapid growth of the size of today's wireless networks,which makes the traditional However,most existing works such as [9,10]focus on cryptographic methods infeasible.Second,the cryptographic secrecy capacity scaling in static networks,yet little is known schemes essentially guarantee security by imposing hard math- about the secrecy capacity-delay tradeoff in MANETs.As an ematical problems on the eavesdroppers,whose computational exception,Liang et al.[11]first attempt to study the secrecy- ability are not high enough to solve the problems.But the capacity-delay tradeoff in MANETs.But,[11]has its limitation. eavesdroppers do obtain the data information and the enemy The authors do not allow receivers to generate artificial noise will decode the message with enough time and computational so as to degenerate the channel at the eavesdroppers.Instead, power.Therefore,to avoid the limitations of the cryptographic they just let each transmitter wait until the intended receiver is solutions,we focus on information theoretic security in this sufficiently near.This turns out to be very inefficient compared to the artificial noise methods adopted in [10]and leads to low IThroughout this paper.for functions f(n)and g(n).we denote f(n)= throughput and high delay.Observing this limitation,we are f(n】 o(g(m)if limn-→eg=0:f(m）=w(gn）ifg(n）=ofn motivated to investigate the impact of secrecy constraint on the f(n)=O(g(n))if there is a positive constant c such that f(n)<cg(n)for sufficiently large n:f(n)=(g(n))if g(n)=O(f(n)):f(n)=e(g(n))if capacity and delay tradeoffs in MANETs with more efficient both f(n)=O(g(n))and f(n)=(g(n))hold.Besides.the order notation secrecy scheme.By MANETs,we mean that the legitimate omits the polylogarithmic factors for better readability. nodes are mobile while the eavesdroppers are static.This is

1 Optimal Secrecy Capacity-Delay Tradeoff in Large-Scale Mobile Ad Hoc Networks Xuanyu Cao, Jinbei Zhang, Luoyi Fu, Weijie Wu, Xinbing Wang Abstract—In this paper, we investigate the impact of information-theoretic secrecy constraint on the capacity and delay of mobile ad hoc networks (MANETs) with mobile legitimate nodes and static eavesdroppers whose location and channel state information (CSI) are both unknown. We assume n legitimate nodes move according to the fast i.i.d. mobility pattern and each desires to communicate with one randomly selected destination node. There are also n ν static eavesdroppers located uniformly in the network and we assume the number of eavesdroppers is much larger than that of legitimate nodes, i.e., ν > 1. We propose a novel simple secure communication model, i.e., the secure protocol model, and prove its equivalence to the widely accepted secure physical model under a few technical assumptions. Based on the proposed model, a framework of analyzing the secrecy capacity and delay in MANETs is established. Given a delay constraint D, we find that the optimal secrecy throughput capacity is1 Θe  W ￾ D n
2 3  , where W is the data rate of each link. We observe that: 1) the capacity-delay tradeoff is independent of the number of eavesdroppers, which indicates that adding more eavesdroppers will not degenerate the performance of the legitimate network as long as ν > 1; 2) the capacity-delay tradeoff of our paper outperforms the previous result Θ  1 nψe  in [11], where ψe = n ν−1 = ω(1) is the density of the eavesdroppers. I. INTRODUCTION Though having the advantage of convenience and low cost, wireless networks are vulnerable to attacks such as eavesdrop￾ping and jamming due to its broadcast nature. Most of existing solutions are based on cryptographic methods, e.g., RSA public key crypto-system. However, there two major drawbacks of the cryptographic solutions. First, the key distribution can be very costly in terms of both energy consumption and compu￾tation/decoding capability because of the rapid growth of the size of today’s wireless networks, which makes the traditional cryptographic methods infeasible. Second, the cryptographic schemes essentially guarantee security by imposing hard math￾ematical problems on the eavesdroppers, whose computational ability are not high enough to solve the problems. But the eavesdroppers do obtain the data information and the enemy will decode the message with enough time and computational power. Therefore, to avoid the limitations of the cryptographic solutions, we focus on information theoretic security in this 1Throughout this paper, for functions f(n) and g(n), we denote f(n) = o(g(n)) if limn→∞ f(n) g(n) = 0; f(n) = ω(g(n)) if g(n) = o(f(n)); f(n) = O(g(n)) if there is a positive constant c such that f(n) ≤ cg(n) for sufficiently large n; f(n) = Ω(g(n)) if g(n) = O(f(n)); f(n) = Θ(g(n)) if both f(n) = O(g(n)) and f(n) = Ω(g(n)) hold. Besides, the order notation Θe omits the polylogarithmic factors for better readability. paper, i.e., safety is ensured even though the eavesdroppers have infinite computational and decoding power. The study of information-theoretic secrecy originates from the seminal works of Shannon [1], Wyner [2], Csiszar and Korner [3], where the secrecy requires the receiver to have better channel than eavesdroppers. Recently, a few schemes are proposed to guarantee the secret communication. Geol and Negi [4] exploit artificial noise to suppress the SNR at the eavesdroppers so as to ensure security. Independence of wireless fading channels are also used to generate noise with cooperation [5] and multiple antennas [6, 7]. While the above mentioned works all focus on proposing various techniques to ensure information-theoretic security, a few papers also investigate the impact of the secrecy constraint on the network capacity and delay. For example, Vasudevan et al. [8] study the secrecy-capacity tradeoff in large-scale wireless networks and introduce helpers around the transmitters to generate noise to suppress the SNR at the eavesdroppers. Capar et al. [9] propose a new secrecy communication scheme that can tolerate o  n log n  eavesdroppers while keeping the network throughput not affected. To transmit a single bit, the authors proposed to generate multiple bits and transmit all of them to the desired destinations through different paths. The original bit can be decoded if and only if all of the generated bits are obtained and the authors present a routing/scheduling protocol to make sure no eavesdroppers could get all those bits. A very related work is a recent paper by Zhang et al. [10]. The authors let every receiver generate artificial noise in order to degrade the SNR at the eavesdroppers and study the impact of secrecy constraints on the capacity scaling in static networks. However, most existing works such as [9, 10] focus on secrecy capacity scaling in static networks, yet little is known about the secrecy capacity-delay tradeoff in MANETs. As an exception, Liang et al. [11] first attempt to study the secrecy￾capacity-delay tradeoff in MANETs. But, [11] has its limitation. The authors do not allow receivers to generate artificial noise so as to degenerate the channel at the eavesdroppers. Instead, they just let each transmitter wait until the intended receiver is sufficiently near. This turns out to be very inefficient compared to the artificial noise methods adopted in [10] and leads to low throughput and high delay. Observing this limitation, we are motivated to investigate the impact of secrecy constraint on the capacity and delay tradeoffs in MANETs with more efficient secrecy scheme. By MANETs, we mean that the legitimate nodes are mobile while the eavesdroppers are static. This is

reasonable since the eavesdroppers may be detected easily show that the per-node unicast capacity for random uniform if they move drastically.To see the impact of the secrecy networks with n nodes is under the protocol √n logn constraint,we assume that the number of eavesdroppers is model.Under this framework,multicast traffic pattern [24]. larger than that of the legitimate nodes in this paper.The heterogeneity in nodes'distribution [25,26],hybrid networks physical layer method that we adopt to achieve information- [27]and MIMO cooperation [28]are also studied in the theoretic security is the same as that of [10].Specifically, literature. each intended receiver generates artificial noise to suppress the Another important trend,which is quite related with this SNR at the eavesdroppers and distinguishes its own channel by paper,is to introduce mobility to improve the network capacity. adopting the self-interference cancelation techniques proposed Grossglauser and Tse [14]first take the mobility of wireless in [12.Thus,each receiver will not be interfered by the noise nodes into consideration and find that capacity can be enhanced generated by itself,i.e.,the channel at the receiver can be much significantly by exploiting the nodes'mobility.In their i.i.d. better than that at the eavesdroppers. mobility model and two-hop transmission scheme,each source The primary contributions of this work are summarized as broadcasts the packets to its neighbors which serve as relays, follows: and then the packets are delivered to the destination whenever We propose a novel simple secure communication model, it is within the transmission range of the one of those relays. i.e.,the secure protocol model,to analyze the performance However,the major drawback of this scheme is large delay of wireless networks with secrecy constraint.We show since the destination may not meet with the relays until a long that the secure protocol model is equivalent to the widely time has passed.Hence,since then,great efforts have been accepted secure physical model under a few technical made to improve capacity delay tradeoffs,i.e.,to achieve rela- assumptions.Thus,a framework to analyze wireless net- tively high capacity with acceptable delay [15-19].Particularly, works with secrecy constraint is established. for a variety of mobility models,given a delay constraint D, We apply the secure protocol model to MANETs with Ying er al.[19]provides matching (except for poly-log terms) mobile legitimate nodes and static eavesdroppers.Given upper bounds and lower bounds on the throughput capacity. a delay constraint D,we derive upper bound for the se- In addition,various mobility models are also investigated in crecy capacity and then present the corresponding capacity [20,21].Motioncast,i.e.,multicast traffic over MANETs,is achieving scheme.We find that as long as the eavesdropper also studied by Wang et al.[22]and Zhang et al.[23]. density e=w(1),the optimal capacity delay tradeoff is alwaysW(.which is independent of the specific III.SYSTEM MODEL value of ve.This significantly improves the previous result In this paper,we assume that the network area is a square in [11]and shows the great advantage of our scheme. with size√a×√元，where n is the number of legitimate nodes. We remark that although the focus of this paper is on networks with i.i.d.mobile legitimate nodes,the secure protocol model we develop is suitable for any wireless networks where the A.Legitimate Network number of eavesdroppers are larger than that of the legitimate There are n legitimate nodes in total in the network area. nodes.The proposed secure protocol model can be applied to Denote Xi the position of legitimate node i.Dividing time networks with different mobility patterns and traffic patterns into constant duration time slots,we adopt the well known i.i.d. (e.g.,unicast,multicast,converge-cast)and is thus quite general mobility model to characterize the drastic topology change of and extendable. the MANETs.Specifically,the initial position of each legitimate The rest of this paper is organized as follows.In Section node is equally likely to be any point in the network area. II we review some related works on the scaling laws of At the beginning of each time slot,every node randomly and wireless networks.In Section III,we formulate the system uniformly chooses a point i.i.d.in the network area to be its model formally while in Section IV,an overview of the solution new position.Throughout this paper,we assume a fast mobility idea and the main results are presented.In Section V,we model [19,23]for the legitimate nodes,i.e.,only one-hop propose the secure protocol model and prove its correspondence transmission is allowed in each time slot.Although the i.i.d. with the widely accepted secure physical model.In Section mobility is an oversimplified model to some extent,it is widely VI,we derive an upper bound for the secrecy capacity-delay adopted in the literature due to its mathematical tractability.In tradeoff while the corresponding capacity achieving scheme is addition,i.i.d.mobility can be viewed as the mobility with very presented in Section VII.Some discussions are presented in large speed and hence we could use this model to characterize Section VIII and we conclude this work in Section IX. the fundamental impact of mobility on network performance. With the help of mobility,packets could reach the destinations II.RELATED WORKS without being relayed for many times,which decreases the In this paper,we provide the asymptotic analysis for the traffic load of the network,and larger capacity is expected. optimal secrecy capacity-delay tradeoffs in MANETs.The fun- We assume that the traffic pattern of between legitimate damental scaling law analysis of wireless networks is initiated nodes is unicast.Equivalently speaking,source-destination by the ground-breaking work of Gupta and Kumar [13].They pairs are randomly chosen such that each node is the destination

2 reasonable since the eavesdroppers may be detected easily if they move drastically. To see the impact of the secrecy constraint, we assume that the number of eavesdroppers is larger than that of the legitimate nodes in this paper. The physical layer method that we adopt to achieve information￾theoretic security is the same as that of [10]. Specifically, each intended receiver generates artificial noise to suppress the SNR at the eavesdroppers and distinguishes its own channel by adopting the self-interference cancelation techniques proposed in [12]. Thus, each receiver will not be interfered by the noise generated by itself, i.e., the channel at the receiver can be much better than that at the eavesdroppers. The primary contributions of this work are summarized as follows: • We propose a novel simple secure communication model, i.e., the secure protocol model, to analyze the performance of wireless networks with secrecy constraint. We show that the secure protocol model is equivalent to the widely accepted secure physical model under a few technical assumptions. Thus, a framework to analyze wireless net￾works with secrecy constraint is established. • We apply the secure protocol model to MANETs with mobile legitimate nodes and static eavesdroppers. Given a delay constraint D, we derive upper bound for the se￾crecy capacity and then present the corresponding capacity achieving scheme. We find that as long as the eavesdropper density ψe = ω(1), the optimal capacity delay tradeoff is always Θe  W ￾ D n
2 3  , which is independent of the specific value of ψe. This significantly improves the previous result in [11] and shows the great advantage of our scheme. We remark that although the focus of this paper is on networks with i.i.d. mobile legitimate nodes, the secure protocol model we develop is suitable for any wireless networks where the number of eavesdroppers are larger than that of the legitimate nodes. The proposed secure protocol model can be applied to networks with different mobility patterns and traffic patterns (e.g., unicast, multicast, converge-cast) and is thus quite general and extendable. The rest of this paper is organized as follows. In Section II, we review some related works on the scaling laws of wireless networks. In Section III, we formulate the system model formally while in Section IV, an overview of the solution idea and the main results are presented. In Section V, we propose the secure protocol model and prove its correspondence with the widely accepted secure physical model. In Section VI, we derive an upper bound for the secrecy capacity-delay tradeoff while the corresponding capacity achieving scheme is presented in Section VII. Some discussions are presented in Section VIII and we conclude this work in Section IX. II. RELATED WORKS In this paper, we provide the asymptotic analysis for the optimal secrecy capacity-delay tradeoffs in MANETs. The fun￾damental scaling law analysis of wireless networks is initiated by the ground-breaking work of Gupta and Kumar [13]. They show that the per-node unicast capacity for random uniform networks with n nodes is Θ  √ 1 n log n  under the protocol model. Under this framework, multicast traffic pattern [24], heterogeneity in nodes’ distribution [25, 26], hybrid networks [27] and MIMO cooperation [28] are also studied in the literature. Another important trend, which is quite related with this paper, is to introduce mobility to improve the network capacity. Grossglauser and Tse [14] first take the mobility of wireless nodes into consideration and find that capacity can be enhanced significantly by exploiting the nodes’ mobility. In their i.i.d. mobility model and two-hop transmission scheme, each source broadcasts the packets to its neighbors which serve as relays, and then the packets are delivered to the destination whenever it is within the transmission range of the one of those relays. However, the major drawback of this scheme is large delay since the destination may not meet with the relays until a long time has passed. Hence, since then, great efforts have been made to improve capacity delay tradeoffs, i.e., to achieve rela￾tively high capacity with acceptable delay [15–19]. Particularly, for a variety of mobility models, given a delay constraint D, Ying et al. [19] provides matching (except for poly-log terms) upper bounds and lower bounds on the throughput capacity. In addition, various mobility models are also investigated in [20, 21]. Motioncast, i.e., multicast traffic over MANETs, is also studied by Wang et al. [22] and Zhang et al. [23]. III. SYSTEM MODEL In this paper, we assume that the network area is a square with size √ n× √ n, where n is the number of legitimate nodes. A. Legitimate Network There are n legitimate nodes in total in the network area. Denote Xi the position of legitimate node i. Dividing time into constant duration time slots, we adopt the well known i.i.d. mobility model to characterize the drastic topology change of the MANETs. Specifically, the initial position of each legitimate node is equally likely to be any point in the network area. At the beginning of each time slot, every node randomly and uniformly chooses a point i.i.d. in the network area to be its new position. Throughout this paper, we assume a fast mobility model [19, 23] for the legitimate nodes, i.e., only one-hop transmission is allowed in each time slot. Although the i.i.d. mobility is an oversimplified model to some extent, it is widely adopted in the literature due to its mathematical tractability. In addition, i.i.d. mobility can be viewed as the mobility with very large speed and hence we could use this model to characterize the fundamental impact of mobility on network performance. With the help of mobility, packets could reach the destinations without being relayed for many times, which decreases the traffic load of the network, and larger capacity is expected. We assume that the traffic pattern of between legitimate nodes is unicast. Equivalently speaking, source-destination pairs are randomly chosen such that each node is the destination

of exactly one source.We denote T(R)as the sets of legitimate receiver,node j,since we adopt self-interference cancelation nodes simultaneously transmitting (receiving)at a given time techniques. slot.As in [10],we assume each legitimate node is equipped On the other hand,Pr.i do interfere with the eavesdroppers with three antennas.When a legitimate node acts as a receiver. and the SINR at the eavesdropper e cab be represented by: one antenna is used for message reception while the other SINRie two are devoted to simultaneous artificial noise generation to suppress the eavesdroppers'channels.The distances between Pil(Xi,Ye) the receive antenna and the other two respective transmit an- O+∑KET\i)P.Al(Xk,Yg)+∑keRP,klXk,Ya' tennas should satisfy a difference of half of the wavelength.The (2) interference can thus be eliminated by invoking the techniques As in [9,11],we say a transmission is secret if none of of self-interference cancelation proposed in [12].Thus,each each eavesdropper could decode the messages.Specifically,we receiver will not be interfered by the artificial noise generated define a transmission to be successful and secret if the following by itself. two conditions hold. ·SINR≥r. B.Eavesdropper Network ·For each eavesdropper e∈E,SINRie≤Ye. There are n eavesdroppers located in the same network Here r,Ye are two positive constants indicating the SINR area.Denote E as the set of all the eavesdroppers and ye the thresholds for successful reception of information.The first position of eavesdropper e E&.We assume that the number of condition assures that the receiver,node j,can decode the eavesdroppers is much larger than that of legitimate nodes,i.e., message successfully while the second condition guarantees >1.Thereby,the density of the eavesdroppers ve=n"-1 is that none of each eavesdropper could decode the message.We much larger than 1,i.e.,ve =w(1).Different from legitimate remark that,in practice,to ensure the transmissions between nodes,the eavesdroppers are assumed to be static,i.e.,the legitimate nodes are reliable and all the eavesdroppers cannot position of each eavesdropper does not change with time.This get any useful information,one may requirer to be large and is reasonable since the eavesdroppers may be detected easily Ye to be low in the secure physical model. if they move drastically.More precisely,each eavesdropper We assume that the data rate for successful secure transmis- independently and uniformly select a point in the network area sion is W bit per time slot.We call a couple of nodes a link as its fixed position.The eavesdroppers always keep silent since if they form a transmitter-receiver pair,e.g..(Xi,Xj).Given they may be detected otherwise.Hence,instead of jamming the a communication (interference)model,in general there are a signal,the eavesdroppers can only overhear messages in our number of subsets of links that can be active simultaneously. setup.The eavesdroppers have infinite computational capability We call such subsets of links together with the corresponding and thus information-theoretic security is needed.We also power management and node positions a feasible state,and assume that both CSI and location information of eavesdroppers define the set of all feasible states as feasible family [29].We are unknown to the legitimate nodes. use (r,Ye)to denote the feasible family of the secure physical model. C.Secure Physical Model D.Definitions of Performance Metrics The secure physical model is widely accepted in the literature We consider hard delay constraints as [19]in this paper. and we describe it in the following.Denote Pi the transmission Given a delay constraint D,a packet is said to be successfully power of node i if i T.Similarly,denote Prj the noise delivered if the destination obtains the packet within D time generation power of node j if jE R.The path loss between slots after it is sent out from the source. node i and node j is denoted by I(Xi,Xj)with l(Xi,Xi)= The asymptotic per-node secure throughput capacity A(n)is I(XiXjl)=min {1,XiXi).Here,Xi is the position said to be achievable if there is a scheduling and routing scheme of node i while a is the path loss exponent.We assume that such that every legitimate node can transmit A(n)bps securely 2<a<4,which is a typical value range for outdoor path loss on average to its destination in the long term. exponent.When node i is transmitting messages to node j.the The frequently used parameters are listed in Table I. signal to interference and noise ratio (SINR)at the receiver node j is given by: IV.OVERVIEW OF IDEA AND MAIN RESULTS SINRij A.Solution Idea Pil(Xi,Xj) Our system model begins with the widely accepted secure No+P+X)'physical model,i.e..the SINR at the receiver should be larger (1)than a threshold to guarantee a successful transmission while the SINR at all the eavesdroppers should be smaller than where No denotes the ambient noise power of the network another threshold to ensure security.Hence,compared to the environment.Note that P is not an interference to the insecure physical model proposed in [13],the secure physical

3 of exactly one source. We denote T (R) as the sets of legitimate nodes simultaneously transmitting (receiving) at a given time slot. As in [10], we assume 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 the eavesdroppers’ channels. The distances between the receive antenna and the other two respective transmit an￾tennas should satisfy a difference of half of the wavelength. The interference can thus be eliminated by invoking the techniques of self-interference cancelation proposed in [12]. Thus, each receiver will not be interfered by the artificial noise generated by itself. B. Eavesdropper Network There are n ν eavesdroppers located in the same network area. Denote E as the set of all the eavesdroppers and ye the position of eavesdropper e ∈ E. We assume that the number of eavesdroppers is much larger than that of legitimate nodes, i.e., ν > 1. Thereby, the density of the eavesdroppers ψe = n ν−1 is much larger than 1, i.e., ψe = ω(1). Different from legitimate nodes, the eavesdroppers are assumed to be static, i.e., the position of each eavesdropper does not change with time. This is reasonable since the eavesdroppers may be detected easily if they move drastically. More precisely, each eavesdropper independently and uniformly select a point in the network area as its fixed position. The eavesdroppers always keep silent since they may be detected otherwise. Hence, instead of jamming the signal, the eavesdroppers can only overhear messages in our setup. The eavesdroppers have infinite computational capability and thus information-theoretic security is needed. We also assume that both CSI and location information of eavesdroppers are unknown to the legitimate nodes. C. Secure Physical Model The secure physical model is widely accepted in the literature and we describe it in the following. Denote Pt,i the transmission power of node i if i ∈ T . Similarly, denote Pr,j the noise generation power of node j if j ∈ R. The path loss between node i and node j is denoted by l(Xi , Xj ) with l(Xi , Xj ) = l(|Xi−Xj |) = min {1, |Xi − Xj | −α}. Here, Xi is the position of node i while α is the path loss exponent. We assume that 2 < α < 4, which is a typical value range for outdoor path loss exponent. When node i is transmitting messages to node j, the signal to interference and noise ratio (SINR) at the receiver node j is given by: SINRij = Pt,il(Xi , Xj ) N0 + P k∈T \{i} Pt,kl(Xk, Xj ) + P k∈R\{j} Pr,kl(Xk, Xj ) , (1) where N0 denotes the ambient noise power of the network environment. Note that Pr,j is not an interference to the receiver, node j, since we adopt self-interference cancelation techniques. On the other hand, Pr,j do interfere with the eavesdroppers and the SINR at the eavesdropper e cab be represented by: SINRie = Pt,il(Xi , Ye) N0 + P k∈T \{i} Pt,kl(Xk, Ye) + P k∈R Pr,kl(Xk, Ye) , (2) As in [9, 11], we say a transmission is secret if none of each eavesdropper could decode the messages. Specifically, we define a transmission to be successful and secret if the following two conditions hold. • SINRij ≥ γr. • For each eavesdropper e ∈ E, SINRie ≤ γe. Here γr, γe are two positive constants indicating the SINR thresholds for successful reception of information. The first condition assures that the receiver, node j, can decode the message successfully while the second condition guarantees that none of each eavesdropper could decode the message. We remark that, in practice, to ensure the transmissions between legitimate nodes are reliable and all the eavesdroppers cannot get any useful information, one may require γr to be large and γe to be low in the secure physical model. We assume that the data rate for successful secure transmis￾sion is W bit per time slot. We call a couple of nodes a link if they form a transmitter-receiver pair, e.g., (Xi , Xj ). Given a communication (interference) model, in general there are a number of subsets of links that can be active simultaneously. We call such subsets of links together with the corresponding power management and node positions a feasible state, and define the set of all feasible states as feasible family [29]. We use PH (γr, γe) to denote the feasible family of the secure physical model. D. Definitions of Performance Metrics We consider hard delay constraints as [19] in this paper. Given a delay constraint D, a packet is said to be successfully delivered if the destination obtains the packet within D time slots after it is sent out from the source. The asymptotic per-node secure throughput capacity λ(n) is said to be achievable if there is a scheduling and routing scheme such that every legitimate node can transmit λ(n) bps securely on average to its destination in the long term. The frequently used parameters are listed in Table I. IV. OVERVIEW OF IDEA AND MAIN RESULTS A. Solution Idea Our system model begins with the widely accepted secure physical model, i.e., the SINR at the receiver should be larger than a threshold to guarantee a successful transmission while the SINR at all the eavesdroppers should be smaller than another threshold to ensure security. Hence, compared to the insecure physical model proposed in [13], the secure physical

TABLE I NOTATIONS mobility patterns.Indeed,as long as the eavesdropper density e=w(1).the secure protocol model is always effective. Notations Definitions The total number of legitimate nodes in the network. B.Main Results ny The total number of eavesdroppers in the network, where>1. Supposing the four technical assumptions in Section V hold, te The density of eavesdroppers,ve=n -1. we list the main results of this paper as follows. a The path loss exponent,2<a 4. Correspondence between secure protocol model and X(n) The per-node secure throughput capacity of legitimate nodes. secure physical model: D The delay constraint imposed on the packets. The secure physical model is shown to be equivalent to P The common transmission power at a given time. the proposed secure protocol model.By equivalence,we 公 The common noise generation power at a given time. mean the capacity-delay scaling law is the same.For any y光(Yr,Ye) The feasible family of secure physical model. given secure physical model,we can find a secure protocol 呼(C) The feasible family of secure protocol model. model such that the feasible family of the secure protocol T The set of simultaneously active transmitters at a given time slot. model is a subset of the feasible family of the given secure R The set of simultaneously active receivers at a physical model (Theorem 5.1).Meanwhile,we can also given time slot. find a secure protocol model such that the feasible family E The set of eavesdroppers. Xi The position of legitimate node i. of the given secure physical model is a subset of the secure Ye The position of eavesdropper node e. protocol model (Theorem 5.2).This equivalence allows us H The Euclidean length or the number of elements to analyze the secure physical model by transforming it of a set. D(t,r) The disk with radius r centered at z. into the proposed secure protocol model without changing I(Xi.Xi)or the scaling law results. I(Xi-Xil) The path loss function min{1,X;-Xjl). Optimal secrecy-capacity-delay tradeoffs in MANETs: V The data rate for successful secure transmission. -Under the secure physical model,the secrecy per-node throughput capacity A with delay constraint D is no model in Subsection III-C poses another SINR constraint on those eavesdroppers.The key issue that we aim to address is more than: how this secrecy constraint may influence the network capacity and delay. -o(w() ogn (3) Though the secure physical model is quite ideal and general for networks with eavesdroppers,it is not convenient from the Under the secure physical model,if D perspective of analysis because it involves many underlying (na(logn)号）andD=O(m),then there existsa details such as the network topology,transmission power, feasible scheme achieving a per-node throughput of: noise generation power and SINR judgement for checking the eligibility of a link.Therefore,we propose the secure protocol D (log n)-12 (4) model (Definition 5.2),which has one parameter C:and is shown to be equivalent to the secure physical model under a few technical assumptions. V.THE SECURE PROTOCOL MODEL The proposed secure protocol model is significantly simpler to analyze because it only relies on the geometry of the nodes' In this section,we propose the secure protocol model for- positions and conceals other factors such as power,noise and mally.Throughout this section,we assume that the eavesdrop- interference.In Section V,we present the secure protocol model pers are located uniformly and randomly while the positions and establish its equivalence to the secure physical model based of the legitimate nodes are arbitrary.We then establish the on a few assumptions formally. equivalence between the proposed secure protocol model and Thanks to the secure protocol model,a framework of analyz- the secure physical model under a few technical assumptions. ing the secrecy capacity-delay tradeoff is formed for MANETs. Thus,a tractable framework of analyzing the secrecy capacity- Under the secure protocol model,we derive an upper bound delay tradeoff is formed.Before introducing these assumptions, on the secrecy capacity given a delay constraint.Afterwards, we define the parameter d*of a state as follows. we show a capacity-achieving scheme which could obtain the Definition 5.1:For a certain state (with at least two si- optimal throughput capacity up to poly-log factors.Since the multaneously active transmitters),we denote d*the minimum secure protocol model is equivalent to the secure physical distance between any two simultaneously active transmitters, model under several assumptions,our results immediately apply 1.e. to the secure physical model under those assumptions.Note ={-xeT,i≠} (5) that the proposed secure protocol model is quite general and is applicable to wireless networks with other traffic patterns and Now we list four assumptions of a state in the following

4 TABLE I NOTATIONS Notations Definitions n The total number of legitimate nodes in the network. n ν The total number of eavesdroppers in the network, where ν > 1. ψe The density of eavesdroppers, ψe = n ν−1 . α The path loss exponent, 2 < α < 4. λ(n) The per-node secure throughput capacity of legitimate nodes. D The delay constraint imposed on the packets. Pt The common transmission power at a given time. Pr The common noise generation power at a given time. PH (γr, γe) The feasible family of secure physical model. PR(Ct) The feasible family of secure protocol model. T The set of simultaneously active transmitters at a given time slot. R The set of simultaneously active receivers at a given time slot. E The set of eavesdroppers. Xi The position of legitimate node i. Ye The position of eavesdropper node e. |·| The Euclidean length or the number of elements of a set. D(x, r) The disk with radius r centered at x. l(Xi, Xj ) or l(|Xi − Xj |) The path loss function min{1, |Xi − Xj |−α}. W The data rate for successful secure transmission. model in Subsection III-C poses another SINR constraint on those eavesdroppers. The key issue that we aim to address is how this secrecy constraint may influence the network capacity and delay. Though the secure physical model is quite ideal and general for networks with eavesdroppers, it is not convenient from the perspective of analysis because it involves many underlying details such as the network topology, transmission power, noise generation power and SINR judgement for checking the eligibility of a link. Therefore, we propose the secure protocol model (Definition 5.2), which has one parameter Ct and is shown to be equivalent to the secure physical model under a few technical assumptions. The proposed secure protocol model is significantly simpler to analyze because it only relies on the geometry of the nodes’ positions and conceals other factors such as power, noise and interference. In Section V, we present the secure protocol model and establish its equivalence to the secure physical model based on a few assumptions formally. Thanks to the secure protocol model, a framework of analyz￾ing the secrecy capacity-delay tradeoff is formed for MANETs. Under the secure protocol model, we derive an upper bound on the secrecy capacity given a delay constraint. Afterwards, we show a capacity-achieving scheme which could obtain the optimal throughput capacity up to poly-log factors. Since the secure protocol model is equivalent to the secure physical model under several assumptions, our results immediately apply to the secure physical model under those assumptions. Note that the proposed secure protocol model is quite general and is applicable to wireless networks with other traffic patterns and mobility patterns. Indeed, as long as the eavesdropper density ψe = ω(1), the secure protocol model is always effective. B. Main Results Supposing the four technical assumptions in Section V hold, we list the main results of this paper as follows. • Correspondence between secure protocol model and secure physical model: The secure physical model is shown to be equivalent to the proposed secure protocol model. By equivalence, we mean the capacity-delay scaling law is the same. For any given secure physical model, we can find a secure protocol model such that the feasible family of the secure protocol model is a subset of the feasible family of the given secure physical model (Theorem 5.1). Meanwhile, we can also find a secure protocol model such that the feasible family of the given secure physical model is a subset of the secure protocol model (Theorem 5.2). This equivalence allows us to analyze the secure physical model by transforming it into the proposed secure protocol model without changing the scaling law results. • Optimal secrecy-capacity-delay tradeoffs in MANETs: – Under the secure physical model, the secrecy per-node throughput capacity λ with delay constraint D is no more than: λ = O W  D n 2 3 log n ! . (3) – Under the secure physical model, if D = Ω  n 2 5 (log n) 21 5  and D = O(n), then there exists a feasible scheme achieving a per-node throughput of: λ = Ω W  D n 2 3 (log n) −12! . (4) V. THE SECURE PROTOCOL MODEL In this section, we propose the secure protocol model for￾mally. Throughout this section, we assume that the eavesdrop￾pers are located uniformly and randomly while the positions of the legitimate nodes are arbitrary. We then establish the equivalence between the proposed secure protocol model and the secure physical model under a few technical assumptions. Thus, a tractable framework of analyzing the secrecy capacity￾delay tradeoff is formed. Before introducing these assumptions, we define the parameter d ∗ of a state as follows. Definition 5.1: For a certain state (with at least two si￾multaneously active transmitters), we denote d ∗ the minimum distance between any two simultaneously active transmitters, i.e., d ∗ = min i,j  |Xi − Xj |     i, j ∈ T , i 6= j  . (5) Now we list four assumptions of a state in the following

1)There are at least two simultaneously active transmitters.can only have one intended receiver:2)the distance between For any point P in the network area,there is at least one simultaneously active transmitters is much larger compared to active transmitter within the disk D(P,2d*). the protocol model in [13],i.e.,if the transmission range of a 2)For any transmitter-receiver pair (Xi,Xi),we have2d*> link is d,then loosely speaking,any other simultaneously active 8(X;-Xi+1).In addition,for the secure physical transmitters must be d2 distance away from this transmitter. model:d >1447ea220-1 Conventional protocol model only needs to guarantee success- 0-2 ful transmissions between Tx and Rx,while the secure protocol 3)For the secure physical model,all the transmitters utilize model needs to further suppress the SINR at the eavesdroppers the same transmission power,i.e.,P.i=P,Vi E T and to ensure security,which makes it stricter. all the receiver utilize the same noise generation power, i.e,Pr,i=Pr,j∈R. Now,we show in the following theorem that,under Assumption 4)For the secure physical model,>23+1e. 1,the secure protocol model implies the secure physical model. We note that the above four assumptions are all reasonable Theorem 5.1:For any two positive constants r,Ye,there and are satisfied by most of the scheduling/routing schemes for exists a positive constant C such that,provided Assumption homogeneous networks.The Assumption 13 is satisfied by most 1 holds,if a state is feasible under the secure protocol model TDMA-based schemes to exploit the network radio resources (C:),then it must be feasible under the secure physical efficiently.It basically states that the distances between different model(,Ye)by exploiting some uniform transmission adjacent transmitters are in the same order.The Assumption 2 power P and some uniform noise generation power P i.e., requires that the distance between two simultaneously active Assumption 3 holds. transmitters is larger than both some constant times of the Proof:We define two positive constants c1,c2 as cI transmission range and another certain constant,in order to 2Noyr and .Then,there exists a positive constant Ye avoid interference.Since the network distribution of both the Cr >8 large enough such that: legitimate nodes and the eavesdroppers is homogeneous,it is natural to assume that the transmission power and noise No generation power are respectively uniform as in Assumption 3. a-2c92 (7a This assumption is also made in [10].The Assumption 4 keeps a certain gap between the SINR at the receivers and that at the 12a24a-1c2 No eavesdroppers so as to guarantee reliable (high value for Yr) cga-2分≤ (7b) and secret (low value for ye)transmissions.The four technical assumptions are satisfied by most of the scheduling/routing We denote d largest transmission range,i.e., schemes (such as TDMA)in homogeneous networks in the literature of scaling law analysis.We have not optimized the constants involved in these four assumptions to make the d= max(,)is a transmitter-receiver pair assumptions as weak as possible.Hence,an improvement on (8) these assumptions,though not being the focus of this paper,is Next,we prove that with power assignment P=c1(1+ possible. d),P=c2(1+d)20,the statement in the theorem holds,i.e., Now,we propose the secure protocol model as follows. the secure protocol model(C:)implies the secure physical Definition 5.2:The Secure Protocol Model with feasible model(r,Ye).We begin from an arbitrary feasible family (C):for any feasible state,we have: state in (C).Let's consider two arbitrary links,(Xi,Xj) 1)All transmissions are unicast,i.e.,one transmitter can and (Xp,X).Suppose (Xio,Xjo)is the link that gives the only have one intended receiver. maximization in the definition of d,i.e.,d =Xio-Xjol. 2)For any transmitter-receiver pair (Xi,Xi),and any other According to Assumption 1,there is a simultaneously active simultaneously active transmitter Xp(pi): transmitter Xi such that Xi-Xiol 2d".Hence,recalling the definition of d*,we have: X-Xl≥C(1+X-X02 (6 Remark 5.1:Compared with the conventional protocol 2X:-Xpl≥lX1-Xiol≥C(1+|Xio-Xo)2=C(1+d)2 model in [13],the proposed secure protocol model here is (9) stricter:1)broadcast is not permitted,i.e.,one transmitter Thus,the disks centered at the transmitters D(X (1+d)2),iT are disjoint.We further have: 2In real-world wireless communications,the typical SINR of a 'relatively good signal condition'is 30dB.i.e..SNR=1000.Besides,the typical value of outdoor path loss exponent is about 3.Suppose the distance between a transmitter-receive pair is d.Then,the nearest simultaneously active transmitter 1Xp-Xl≥lX-Xl-lX:-Xl (10a) should be at least(1000)1/3d=10d away.Thus,the first requirement of the assumption 2 is satisfied. ≥受1+-d (10b) 3Throughout this paper,we use Assumption 1.2.3 and 4 to denote the above four assumptions respectively. ≥1+d. (10c)

5 1) There are at least two simultaneously active transmitters. For any point P in the network area, there is at least one active transmitter within the disk D(P, 2d ∗ ). 2) For any transmitter-receiver pair (Xi , Xj ), we have2 d ∗ ≥ 8(|Xi − Xj | + 1). In addition, for the secure physical model: d ∗ ≥  144γeα·2 2α−1 α−2  1 α . 3) For the secure physical model, all the transmitters utilize the same transmission power, i.e., Pt,i = Pt, ∀i ∈ T and all the receiver utilize the same noise generation power, i.e., Pr,j = Pr, ∀j ∈ R. 4) For the secure physical model, γr > 2 3α+1γe. We note that the above four assumptions are all reasonable and are satisfied by most of the scheduling/routing schemes for homogeneous networks. The Assumption 13 is satisfied by most TDMA-based schemes to exploit the network radio resources efficiently. It basically states that the distances between different adjacent transmitters are in the same order. The Assumption 2 requires that the distance between two simultaneously active transmitters is larger than both some constant times of the transmission range and another certain constant, in order to avoid interference. Since the network distribution of both the legitimate nodes and the eavesdroppers is homogeneous, it is natural to assume that the transmission power and noise generation power are respectively uniform as in Assumption 3. This assumption is also made in [10]. The Assumption 4 keeps a certain gap between the SINR at the receivers and that at the eavesdroppers so as to guarantee reliable (high value for γr) and secret (low value for γe) transmissions. The four technical assumptions are satisfied by most of the scheduling/routing schemes (such as TDMA) in homogeneous networks in the literature of scaling law analysis. We have not optimized the constants involved in these four assumptions to make the assumptions as weak as possible. Hence, an improvement on these assumptions, though not being the focus of this paper, is possible. Now, we propose the secure protocol model as follows. Definition 5.2: The Secure Protocol Model with feasible family PR(Ct): for any feasible state, we have: 1) All transmissions are unicast, i.e., one transmitter can only have one intended receiver. 2) For any transmitter-receiver pair (Xi , Xj ), and any other simultaneously active transmitter Xp(p 6= i): |Xi − Xp| ≥ Ct(1 + |Xi − Xj |) 2 . (6) Remark 5.1: Compared with the conventional protocol model in [13], the proposed secure protocol model here is stricter: 1) broadcast is not permitted, i.e., one transmitter 2 In real-world wireless communications, the typical SINR of a ‘relatively good signal condition’ is 30dB, i.e., SNR=1000. Besides, the typical value of outdoor path loss exponent is about 3. Suppose the distance between a transmitter-receive pair is d. Then, the nearest simultaneously active transmitter should be at least (1000)1/3d = 10d away. Thus, the first requirement of the assumption 2 is satisfied. 3Throughout this paper, we use Assumption 1, 2, 3 and 4 to denote the above four assumptions respectively. can only have one intended receiver; 2) the distance between simultaneously active transmitters is much larger compared to the protocol model in [13], i.e., if the transmission range of a link is d, then loosely speaking, any other simultaneously active transmitters must be d 2 distance away from this transmitter. Conventional protocol model only needs to guarantee success￾ful transmissions between Tx and Rx, while the secure protocol model needs to further suppress the SINR at the eavesdroppers to ensure security, which makes it stricter. Now, we show in the following theorem that, under Assumption 1, the secure protocol model implies the secure physical model. Theorem 5.1: For any two positive constants γr, γe, there exists a positive constant Ct such that, provided Assumption 1 holds, if a state is feasible under the secure protocol model PR(Ct), then it must be feasible under the secure physical model PH (γr, γe) by exploiting some uniform transmission power Pt and some uniform noise generation power Pr i.e., Assumption 3 holds. Proof: We define two positive constants c1, c2 as c1 = 2N0γr and c2 = 2 αc1 γe . Then, there exists a positive constant Ct > 8 large enough such that: 192α2 α−1 c1 (α − 2)C2 t ≤ N0 2 , (7a) 12α2 4α−1 c2 Cα t (α − 2) ≤ N0 2 . (7b) We denote d largest transmission range, i.e., d = max i,j  |Xi − Xj |     (Xi, Xj ) is a transmitter − receiver pair . (8) Next, we prove that with power assignment Pt = c1(1 + d) α, Pr = c2(1 +d) 2α, the statement in the theorem holds, i.e., the secure protocol model PR(Ct) implies the secure physical model PH (γr, γe). We begin from an arbitrary feasible state in PR(Ct). Let’s consider two arbitrary links, (Xi , Xj ) and (Xp, Xq). Suppose (Xi0 , Xj0 ) is the link that gives the maximization in the definition of d, i.e., d = |Xi0 − Xj0 |. According to Assumption 1, there is a simultaneously active transmitter Xi1 such that |Xi1 − Xi0 | ≤ 2d ∗ . Hence, recalling the definition of d ∗ , we have: 2|Xi−Xp| ≥ |Xi1−Xi0 | ≥ Ct(1+|Xi0−Xj0 |) 2 = Ct(1+d) 2 . (9) Thus, the disks centered at the transmitters D ￾ Xi , Ct 4 (1 + d) 2
, i ∈ T are disjoint. We further have: |Xp − Xj | ≥ |Xi − Xp| − |Xi − Xj | (10a) ≥ Ct 2 (1 + d) 2 − d (10b) ≥ 1 + d. (10c)

6 The reason of (10c)is C>8.Then,we divide the set Tfi} R,1≤k≤ into the following subsets,l≤k≤g R T={pk(1+d)≤lXp-X引<(k+1)(1+d),p∈T,p≠i gk×号1+d2≤x,-x1<k+) (11a 1+d02,geR,g≠j} × 8 (16a) 82五 T八{i=U T (11b) c(1+d)7 k=1 R\i}U Rk. (16b) k=1 Noting that each transmitter consumes radio resource of a disk area yields the following upper bound for: Each receiver consumes a radio resource of a disk area,hence we obtain: 团≤π【(k+1)d+12, (12) l=1 r[+'风≤r+u+ which is equivalent to the following: (17 which could be simplified to: 481 团≤a++ (13) l=1 ∑R≤3(k+1)2 (18) =1 Hence,the interference caused by other transmitters at Xj. which we denote as I(X;),can be bounded as follows. Thus,the interference at the receiver X;caused by the artificial noise generated by other receivers can be bounded as follows: 20P I(X)≤ a+m (14a) P )≤2停+9R (19a) k-1 =2rr∑ 1 (d+1m (14b) s指a=(店-会 2P 1 ∑团 19b) (14c) 2aPt 1 答a信-+会 ≤(d+1 k=1 C受a+k+12(14d (19c) 192a20P 1 8 P C a+i0a夜∑k1- (14e) ≤ a+∑ak-1-3张+12 (19d) k=1 192a2a-1c1 12a24a-1 No ≤a-2)c7 (14D ≤ Cg(a-29≤2 (19e) 52 (14g) The last step(19e)utilizes the power management Pr =c2(1+ d)2 and (7b).Thereby,the SINR at Xj can be bounded as: (14d)utilizes both (13)and the fact that ak--1.(14f)utilizes the power management P:=ci(1+d) C1 while (14g)follows from(7a).Next,we endeavor to bound the SINR(X)≥0+学+受= (20) interference from other receivers'artificial noise.We have: x,-X引≥1x,-X-21≥受1+a2-2a≥1+a02 For any eavesdropper e,whose position is denoted as Ye,the interference at it is at least: (15) Hence,the disks D(j,(d)2),jR are disjoint. P P Similarly,we also divide the set Rj}into following subsets 1≥0X-a+1≥0+d+-X产 (21)

6 The reason of (10c) is Ct > 8. Then, we divide the set T \{i} into the following subsets Tk, 1 ≤ k ≤ √ 2n 1+d . Tk =  p     k(1 + d) ≤ |Xp − Xj | < (k + 1)(1 + d), p ∈ T , p 6= i  (11a) T \{i} = √ 2n 1+[d k=1 Tk (11b) Noting that each transmitter consumes radio resource of a disk area yields the following upper bound for |Tk|: 1 3 π  Ct 4 (1 + d) 2 2 X k l=1 |Tl | ≤ π [(k + 1)(d + 1)]2 , (12) which is equivalent to the following: X k l=1 |Tl | ≤ 48 C2 t 1 (d + 1)2 (k + 1)2 . (13) Hence, the interference caused by other transmitters at Xj , which we denote as It(Xj ), can be bounded as follows. It(Xj ) ≤ √ 2n Xd+1 k=1 2 αPt [k(d + 1)]α |Tk| (14a) = 2αPt X k 1 [k(d + 1)]α X k l=1 |Tl | − k X−1 l=1 |Tl | ! (14b) = 2 αPt (d + 1)α X k  1 k α − 1 (k + 1)α X k l=1 |Tl | (14c) ≤ 2 αPt (d + 1)α X∞ k=1 αk−α−1 48 C2 t 1 (d + 1)2 (k + 1)2 (14d) = 192α2 αPt C2 t 1 (d + 1)α+2 X∞ k=1 k 1−α (14e) ≤ 192α2 α−1 c1 (α − 2)C2 t (14f) ≤ N0 2 (14g) (14d) utilizes both (13) and the fact that 1 kα − 1 (k+1)α ≤ αk−α−1 . (14f) utilizes the power management Pt = c1(1+d) α while (14g) follows from (7a). Next, we endeavor to bound the interference from other receivers’ artificial noise. We have: |Xq −Xj | ≥ |Xp −Xi |−2d ≥ Ct 2 (1+d) 2 −2d ≥ Ct 4 (1+d) 2 . (15) Hence, the disks D(Xj , Ct 8 (1 + d) 2 ), j ∈ R are disjoint. Similarly, we also divide the set R\{j} into following subsets Rk, 1 ≤ k ≤ 8 √ 2n Ct(1+d) 2 : Rk =  q     k × Ct 8 (1 + d) 2 ≤ |Xp − Xj | < (k + 1) × Ct 8 (1 + d) 2 , q ∈ R, q 6= j  , (16a) R\{j} = 8 √ 2n Ct(1+ [d)2 k=1 Rk. (16b) Each receiver consumes a radio resource of a disk area, hence we obtain: 1 3 π  Ct 8 (1 + d) 2 2 X k l=1 |Rl | ≤ π  (k + 1)Cr 8 (1 + d) 2 2 , (17) which could be simplified to: X k l=1 |Rl | ≤ 3(k + 1)2 (18) Thus, the interference at the receiver Xj caused by the artificial noise generated by other receivers can be bounded as follows: Ir(Xj ) ≤ X k Pr kCt 8 (1 + d) 2 α |Rk| (19a) ≤ 8 α Cα t Pr (1 + d) 2α X k 1 k α X k l=1 |Rl | − k X−1 l=1 |Rl | ! (19b) = 8 α Cα t Pr (1 + d) 2α X k  1 k α − 1 (k + 1)α X k l=1 |Rl | (19c) ≤ 8 α Cα t Pr (1 + d) 2α X∞ k=1 αk−α−1 · 3(k + 1)2 (19d) ≤ 12α2 4α−1 Cα t (α − 2) c2 ≤ N0 2 . (19e) The last step (19e) utilizes the power management Pr = c2(1+ d) 2α and (7b). Thereby, the SINR at Xj can be bounded as: SINR(Xj ) ≥ c1 N0 + N0 2 + N0 2 = γr. (20) For any eavesdropper e, whose position is denoted as Ye, the interference at it is at least: Ie ≥ Pr (|Xj − Ye| + 1)α ≥ Pr (1 + d + |Ye − Xi |) α . (21)

> Hence,the SINR at e is at most: Y1.Recalling the definition of the path loss 2“P function l(),we have: SINR(Y)2.Without and their intended receivers are far away from Xi and Xi12-l(Xi-Xil).So,we have: (24b) e≥SINR(Ye)≥2-3a-1STNR(Xa)≥2-3a-1r. (31) Furthermore, This contradicts to Assumption 4,indicating that every Xi X1+X2 cannot have more than 1 receiver,i.e.,every link should be 2 unicast. (25a) Now,we start to prove(6)in the definition of the secure pro- XXjal. (25b) tocol model.Consider one arbitrary unicast link pair (Xi,Xj). Recall that the density of the eavesdroppers is n-1,where Let Xp be the nearest simultaneously active transmitter to Xi and Xa be the intended receiver of Xp.According to >1.So,asymptotically almost surely,for every point in the network area,there is an eavesdropper within a distance Assumption 1,we know Xp -Xil<2d*.As previously of o(1).Hence,there exists an eavesdropper e such that mentioned,there should be an eavesdropper Ye such that Ye-Xil 1,a.a.s..Hence, 4a.a.s.stands for asymptotically almost surely.We say an event series An happens asymptotically almost surely if limno Pr(An)=1. x,-≥x,--1x-1≥心-1≥，62

7 Hence, the SINR at e is at most: SINR(Ye) ≤ 2 αPt (1+|Ye−Xi|)α Pr (1+d+|Ye−Xi|)α (22a) = 2 αPt Pr  1 + d 1 + |Ye − Xi | α (22b) ≤ 2 αPt Pr (1 + d) α (22c) = 2 αc1 c2 = γe (22d) Thus, SINR constraint at receivers and eavesdroppers are both satisfied, indicating that the state is feasible under the secure physical model PH (γr, γe). We further assert in the next theorem that, under the previously presented four assumptions, the secure physical model implies the secure protocol model, which is converse to Theorem 5.1. Theorem 5.2: For any two positive constants γr, γe satisfy￾ing Assumption 4, there exists a positive constant Ct such that, provided Assumption 1, 2 and 3 all hold, if a state is feasible under the secure physical model PH (γr, γe), then it must be feasible under the secure protocol model PR(Ct), a.a.s.4 . Proof: Given a state satisfying PH (γr, γe) and the four assumptions, we first show that all its links are unicast, i.e., one transmitter has only one receiver. Consider an arbitrary active transmitter Xi . Suppose it has multiple receivers Xj1 , Xj2 , ..., Xjm where m ≥ 2. Without loss of generality, we let |Xj1 −Xj2 | be the minimum distance between any two receivers of Xi , i.e., ∀1 ≤ k, l ≤ m, k 6= l, we have |Xjk − Xjl | ≥ |Xj1 − Xj2 |. We further assume that Xj2 is nearer to Xi than Xj1 does, i.e., |Xj2 − Xi | ≤ |Xj1 − Xi |. Then, for any other receiver of Xi , say Xj3 , we have: |Xj3 − Xj1 | ≥ |Xj2 − Xj1 | = 2     Xj1 − Xj1 + Xj2 2     . (23) Hence,     Xj3 − Xj1 + Xj2 2     ≥ |Xj3 − Xj1 | −     Xj1 − Xj1 + Xj2 2     (24a) ≥     Xj1 − Xj1 + Xj2 2     . (24b) Furthermore, 2     Xj3 − Xj1 + Xj2 2     ≥     Xj1 − Xj1 + Xj2 2     +     Xj3 − Xj1 + Xj2 2     (25a) ≥ |Xj1 − Xj3 |. (25b) Recall that the density of the eavesdroppers is n ν−1 , where ν > 1. So, asymptotically almost surely, for every point in the network area, there is an eavesdropper within a distance of o(1). Hence, there exists an eavesdropper e such that 4 a.a.s. stands for asymptotically almost surely. We say an event series An happens asymptotically almost surely if limn→∞ Pr(An) = 1.    Ye − Xj1+Xj2 2    ≤ 1. Recalling the definition of the path loss function l(·), we have: l(|Xj1 − Xj3 |) ≥ l  2     Xj3 − Xj1 + Xj2 2      (26a) ≥ 2 −α l     Xj3 − Xj1 + Xj2 2      (26b) ≥ 2 −α l(|Xj3 − Ye| + 1) (26c) ≥ 4 −α l(|Xj3 − Ye|) (26d) Due to the arbitrariness of Xj3 , we actually have: Xm k=3 l(|Xjk − Ye|) ≤ 4 αXm k=3 l(|Xjk − Xj1 |) (27) Besides, we can easily show that l(|Xj2 − Ye|) ≤ 4 αl(|Xj1 − Xj2 |). Adding it onto (27) yields: Xm k=2 l(|Xjk − Ye|) ≤ 4 αXm k=2 l(|Xjk − Xj1 |). (28) Because l(|Xj1 − Ye|) ≤ 4 αl(|Xj1 − Xj2 |), we have: Xm k=1 l(|Xjk − Ye|) ≤ 2 · 4 αXm k=2 l(|Xjk − Xj1 |). (29) According to Assumption 2, other simultaneous transmitters and their intended receivers are far away from Xi and Xjk , 1 ≤ k ≤ m, i.e., for eavesdroppers Ye and the receivers of Xi , the interference caused by Xi’s receivers dominates. So, we just ignore the interference from other nodes. A rigorous proof of the above argument is nothing more than some tedious bounding using Assumption 2 and is omitted here. From the above analysis and (29), we obtain I(Ye) ≤ 2 · 4 αI(Xj1 ). Furthermore, |Ye − Xi | ≤     Ye − Xj1 + Xj2 2     +     Xj1 + Xj2 2 − Xi     (30a) ≤ 1 + 1 2 |Xj1 − Xi | + 1 2 |Xj2 − Xi | (30b) ≤ 1 + |Xj1 − Xi | (30c) Hence, l(|Ye − Xi |) ≥ 2 −αl(|Xj1 − Xi |). So, we have: γe ≥ SINR(Ye) ≥ 2 −3α−1SINR(Xj1 ) ≥ 2 −3α−1 γr. (31) This contradicts to Assumption 4, indicating that every Xi cannot have more than 1 receiver, i.e., every link should be unicast. Now, we start to prove (6) in the definition of the secure pro￾tocol model. Consider one arbitrary unicast link pair (Xi , Xj ). Let Xp be the nearest simultaneously active transmitter to Xi and Xq be the intended receiver of Xp. According to Assumption 1, we know |Xp − Xi | ≤ 2d ∗ . As previously mentioned, there should be an eavesdropper Ye 0 such that |Ye 0 − Xi | ≤ 1, a.a.s.. Hence, |Xp − Ye 0 | ≥ |Xp − Xi | − |Xi − Ye 0 | ≥ d ∗ − 1 ≥ 1 2 d ∗ , (32)

i.e.,every transmitter other than Xi is at least d*away from Thus,we conclude that the current state is feasible under the eavesdropper Ye.We also know that the distance between secure protocol model(C:). ■ any two transmitters is at least d*.Hence,the interference at Remark 5.2:Theorem 5.1 together with Theorem 5.2 es- eavesdropper Ye from other simultaneously active transmitters tablishes equivalence between the secure physical model and is at most4 I(Ye）≤O()-The strict proof of this the proposed secure protocol model under the four technical statement is similar to that of Theorem 5.1 and is omitted here.assumptions.By equivalence,we mean that the capacity delay To bound the interference from receivers other than Xi,we scaling law results under the two models are the same.Actually, have: by using Theorems 5.1 and 5.2,we can easily convert the X,-≥lx-Xl-Xp-Xgl-1≥4r capacity scaling results obtained under the secure protocol 2 (33a) model into results under the secure physical model.This works x,-X1≥x,-x-x,-X1-x-g1≥5 as follows.Suppose under any secure protocol model(C), we could always find a feasible scheduling scheme such that (33b) the per-node throughput is A(this is exactly what we will do in where we utilize Assumption 2.Hence,the interference Section VII).According to Theorem 5.1,for any given secure at eavesdropper Ye,from receivers other than X;is at physical model(r,Ye)we can find C:large enough such most ( P while the interference from Xi is at most that(C)(Yr,Ye).Then the aforementioned A- throughput scheduling scheme feasible under (C:)turns P 0(x4-+ Thus,the total interference at eavesdropper out to be also feasible under(,Ye).So.we can conclude e is at most: that any secure physical model could reach a throughput of A. Similarly,if we have got an upper bound for the throughput IYe)≤O Pt P (d+0x-X+1)9 (34) capacity under the secure protocol model (Section VD).by using Theorem 5.2,we could assert that the upper bound also holds Since the current state is feasible under the secure physical for the secure physical model. model(Yr,Ye),at the eavesdropper Ye,we have: Remark 5.3:We can see from the secure protocol model P that the secrecy constraint does have great impacts on network ≤Ye (35) N6+0(步+-+ behaviors.Compared to the insecure protocol model presented in [13],the secure protocol model is clearly stricter.This will We also know that P>Noyr.Note that the notation O() definitely degenerate the network performance such as capacity only contains some constants terms related to a.Hence,under and delay,which we will discuss quantitatively in Section VI Assumption 2 and Assumption 4,the third (last)term of the and Section VII.An interesting thing is that the secure protocol denominator must dominate the value of the denominator in model is independent of the eavesdropper density =n-1, (35).Thereby,(35)can be simplified to: as long as it is much larger than one,i.e.,ve =w(1)or v>1. This indicates that adding more eavesdroppers into the network 0 (36) will not further degenerate the network capacity. P (X,-X+1)a where we absorb the term Ye into the notation O(). Next,we turn to the interference at the receiver Xj.We have: VI.AN UPPER BOUND ON THE SECRECY CAPACITY-DELAY TRADEOFF Xg-X引≤Xp-X+Xp-Xgl+X:-X≤3d*.(37) Thus,the interference at the receiver Xi is at least I(Xi)> In this section,we derive the upper bound for the network ca- (3).Hence, pacity under certain secrecy and delay constraints in MANETs, 24P (1) by using the proposed secure protocol model(C:).Since P ≥Yr (38) the secure protocol model is shown to be equivalent to the Bd-o secure physical model if the four technical assumptions hold, which is equivalent to: the derived upper bound in this section is also suitable for a majority of feasible schemes (or more precisely,schemes P Xi-Xj+ (39) satisfying the four technical assumptions)under the secure P d* physical model.In Section VII,we present a capacity achieving Combining (36)and (39),we obtain: (except for poly-log gap)scheme satisfying those assumptions. d*≥2(0X-X引+1)2) This indicates that the upper bound derived in this section is (40) essentially tight. Recall that d*is the smallest distance between any two trans- Denote D the delay of bit b,i.e.,the number of time slots mitters.By choosing the positive constant Ct small enough,we it takes for bit b to reach its destination after it enters into have: the network system.Denote Lo the capture range of bit b,i.e., 1Xp-X≥C(0X-X引+1)2. (41) the distance between the last mobile relay of bit b and the final

8 i.e., every transmitter other than Xi is at least 1 2 d ∗ away from eavesdropper Ye 0 . We also know that the distance between any two transmitters is at least d ∗ . Hence, the interference at eavesdropper Ye 0 from other simultaneously active transmitters is at most It(Ye 0 ) ≤ O  Pt (d∗)α  . The strict proof of this statement is similar to that of Theorem 5.1 and is omitted here. To bound the interference from receivers other than Xj , we have: |Xq − Ye 0 | ≥ |Xi − Xp| − |Xp − Xq| − 1 ≥ 1 2 d ∗ , (33a) |Xq − Xj | ≥ |Xp − Xi | − |Xp − Xq| − |Xi − Xj | ≥ 1 2 d ∗ , (33b) where we utilize Assumption 2. Hence, the interference at eavesdropper Ye 0 from receivers other than Xj is at most O  Pr (d∗)α  while the interference from Xj is at most O  Pr (|Xi−Xj |+1)α  . Thus, the total interference at eavesdropper e is at most: I(Ye 0 ) ≤ O  Pt (d ∗) α + Pr (|Xi − Xj | + 1)α  . (34) Since the current state is feasible under the secure physical model PH (γr, γe), at the eavesdropper Ye 0 , we have: Pt N0 + O  Pt (d∗)α + Pr (|Xi−Xj |+1)α  ≤ γe. (35) We also know that Pt ≥ N0γr. Note that the notation O(·) only contains some constants terms related to α. Hence, under Assumption 2 and Assumption 4, the third (last) term of the denominator must dominate the value of the denominator in (35). Thereby, (35) can be simplified to: Pt Pr ≤ O  1 (|Xi − Xj | + 1)α  , (36) where we absorb the term γe into the notation O(·). Next, we turn to the interference at the receiver Xj . We have: |Xq − Xj | ≤ |Xp − Xi |+|Xp − Xq|+|Xi − Xj | ≤ 3d ∗ . (37) Thus, the interference at the receiver Xj is at least I(Xj ) ≥ Pr (3d∗)α . Hence, 2 αPt (|Xi−Xj |+1)α Pr (3d∗)α ≥ γr, (38) which is equivalent to: Pt Pr ≥ Ω |Xi − Xj | + 1 d ∗ α . (39) Combining (36) and (39), we obtain: d ∗ ≥ Ω ￾ (|Xi − Xj | + 1)2
. (40) Recall that d ∗ is the smallest distance between any two trans￾mitters. By choosing the positive constant Ct small enough, we have: |Xp − Xi | ≥ Ct(|Xi − Xj | + 1)2 . (41) Thus, we conclude that the current state is feasible under the secure protocol model PR(Ct). Remark 5.2: Theorem 5.1 together with Theorem 5.2 es￾tablishes equivalence between the secure physical model and the proposed secure protocol model under the four technical assumptions. By equivalence, we mean that the capacity delay scaling law results under the two models are the same. Actually, by using Theorems 5.1 and 5.2, we can easily convert the capacity scaling results obtained under the secure protocol model into results under the secure physical model. This works as follows. Suppose under any secure protocol model PR(Ct), we could always find a feasible scheduling scheme such that the per-node throughput is λ (this is exactly what we will do in Section VII). According to Theorem 5.1, for any given secure physical model PH (γr, γe) we can find Ct large enough such that PR(Ct) ⊆ PH (γr, γe). Then the aforementioned λ- throughput scheduling scheme feasible under PR(Ct) turns out to be also feasible under PH (γr, γe). So, we can conclude that any secure physical model could reach a throughput of λ. Similarly, if we have got an upper bound for the throughput capacity under the secure protocol model (Section VI), by using Theorem 5.2, we could assert that the upper bound also holds for the secure physical model. Remark 5.3: We can see from the secure protocol model that the secrecy constraint does have great impacts on network behaviors. Compared to the insecure protocol model presented in [13], the secure protocol model is clearly stricter. This will definitely degenerate the network performance such as capacity and delay, which we will discuss quantitatively in Section VI and Section VII. An interesting thing is that the secure protocol model is independent of the eavesdropper density ψe = n ν−1 , as long as it is much larger than one, i.e., ψe = ω(1) or ν > 1. This indicates that adding more eavesdroppers into the network will not further degenerate the network capacity. VI. AN UPPER BOUND ON THE SECRECY CAPACITY-DELAY TRADEOFF In this section, we derive the upper bound for the network ca￾pacity under certain secrecy and delay constraints in MANETs, by using the proposed secure protocol model PR(Ct). Since the secure protocol model is shown to be equivalent to the secure physical model if the four technical assumptions hold, the derived upper bound in this section is also suitable for a majority of feasible schemes (or more precisely, schemes satisfying the four technical assumptions) under the secure physical model. In Section VII, we present a capacity achieving (except for poly-log gap) scheme satisfying those assumptions. This indicates that the upper bound derived in this section is essentially tight. Denote Db the delay of bit b, i.e., the number of time slots it takes for bit b to reach its destination after it enters into the network system. Denote Lb the capture range of bit b, i.e., the distance between the last mobile relay of bit b and the final

destination in the final time slot of bit b3.Denote Ro the number Cauchy-Schwartz inequality twice yields: of duplicates of bit b,i.e.,the number of mobile relays holding λnT bit b before it reaches the destination.Since the legitimate nodes 1 AnT move according to an i.i.d.pattern,there is a tradeoff between E(R6)2 (46a) E(D6) h Do,Lo and Ro,which is stated as the following lemma.This logn b=1 lemma has been proved in [16]. 1 Lemma 6.1:The following inequality holds for any causal 1 scheduling policy, 加婴安+点 (46b) logn ∑E(D】 1 2 cE(D6)logn≥ (42) λ4nT4 1 1 E(Rb) 2 logn ∑TE(D λnT E(LB)+ where c is a positive constant. (46c) Under the secure protocol model(C:),every transmission is unicast.Hence,to make R duplicates in the network,we From (43)in Lemma 6.2,we obtain: need R transmissions.According to (6),every transmission AnT λnT will consume at least (1)area of radio resource.Thus,in a long period of time,say T time slots,the total area of radio ∑E(R)+∑E(L哈)≤O(nWT). (47) b= b=1 resource consumed by duplication is at leastR where A is the per-node throughput.On the other hand,because Bringing (46c)into (47)yields: the capture range is Lo and only one-hop transmission is AiniT4 allowed in a time slot(fast mobility),the capture phase of bit b will consume (L)area of radio resource.The reason is 而(+中+加E( ≤O(nWT).(48) that,according to (6),disks centered at simultaneously active transmitters with radius e(L)must be disjoint.Meanwhile, Now.there are two cases we need to consider. the total radio resource of T time slots is an area of nWT. From the above analysis,we obtain the following lemma. Case I:If∑T≥g,then(48)can be rewriten as: Lemma 6.2:The following inequality holds for any causal XiniT4 scheduling policy. logn 2ot+∑TE(亿) ≤O(nWT).(49) 区+( O(nWT). (43) Since f(z)=z4 is a convex function on R+,by applying Jenson's inequality,we have: Now,we are ready to derive the upper bound of the secure 入n AnT capacity for MANETs.We assume that D=O(n)since a delay ∑E(L8)≥∑E(I4. (50) constraint of e(n)is already sufficient to ensure a constant per- b= b=1 node throughput,as we will see later.Hence,a weaker delay constraint D =(n)cannot improve the capacity any more Invoking Holder's inequality yields: and is ignored. Theorem 6.1:Under the secure protocol model,if D O(n),the following upper bound holds for any causal schedul- (51) ing policy, a=o(r()e which could be simplified to: (44) 入n Proof:(42)in Lemma 6.1 can be rewritten as: h=1 e (52) 1 1 E(w)≥gn(=+}D (45) Bringing (50)and(52)into (49),we obtain: 4n4T4 1 where we omit the constant cI since this will not change our logn result in order sense.Summing over all the bits and invoking ∑IE(D)[∑TE(L AnT SBy final time slot,we mean the time slot when the desired destination gets +(AnT E(Lb) ≤O(nWT), (53) bit b

9 destination in the final time slot of bit b 5 . Denote Rb the number of duplicates of bit b, i.e., the number of mobile relays holding bit b before it reaches the destination. Since the legitimate nodes move according to an i.i.d. pattern, there is a tradeoff between Db, Lb and Rb, which is stated as the following lemma. This lemma has been proved in [16]. Lemma 6.1: The following inequality holds for any causal scheduling policy, c˜E(Db) log n ≥ 1  E(Lb) √ n + 1 n2 2 E(Rb) , (42) where c˜ is a positive constant. Under the secure protocol model PR(Ct), every transmission is unicast. Hence, to make Rb duplicates in the network, we need Rb transmissions. According to (6), every transmission will consume at least Ω(1) area of radio resource. Thus, in a long period of time, say T time slots, the total area of radio resource consumed by duplication is at least Ω PλnT b=1 Rb  , where λ is the per-node throughput. On the other hand, because the capture range is Lb and only one-hop transmission is allowed in a time slot (fast mobility), the capture phase of bit b will consume Ω ￾ L 4 b
area of radio resource. The reason is that, according to (6), disks centered at simultaneously active transmitters with radius Θ ￾ L 2 b
must be disjoint. Meanwhile, the total radio resource of T time slots is an area of nW T. From the above analysis, we obtain the following lemma. Lemma 6.2: The following inequality holds for any causal scheduling policy, Ω λnT X b=1 Rb ! + Ω λnT X b=1 L 4 b ! ≤ O(nW T). (43) Now, we are ready to derive the upper bound of the secure capacity for MANETs. We assume that D = O(n) since a delay constraint of Θ(n) is already sufficient to ensure a constant per￾node throughput, as we will see later. Hence, a weaker delay constraint D = Ω(n) cannot improve the capacity any more and is ignored. Theorem 6.1: Under the secure protocol model, if D = O (n), the following upper bound holds for any causal schedul￾ing policy, λ = O W  D n 2 3 log n ! . (44) Proof: (42) in Lemma 6.1 can be rewritten as: E(Rb) ≥ 1 log n 1  E(Lb) √ n + 1 n2 2 1 E(Db) , (45) where we omit the constant c1 since this will not change our result in order sense. Summing over all the bits and invoking 5By final time slot, we mean the time slot when the desired destination gets bit b. Cauchy-Schwartz inequality twice yields: λnT X b=1 E(Rb) ≥ 1 log n λnT X b=1 1  E(Lb) √ n + 1 n2 2 1 E(Db) (46a) ≥ 1 log n PλnT b=1 1 E(Lb ) √n + 1 n2 2 PλnT b=1 E(Db) (46b) ≥ λ 4n 4T 4 log n 1 PλnT b=1 E(Db)   1 PλnT b=1  E(Lb) √ n + 1 n2    2 (46c) From (43) in Lemma 6.2, we obtain: λnT X b=1 E(Rb) + λnT X b=1 E ￾ L 4 b
≤ O(nW T). (47) Bringing (46c) into (47) yields: λ 4n 4T 4 log n P 1 λnT b=1 E(Db) 1 hPλnT b=1  E(Lb ) √n + 1 n2 i2 + PλnT b=1 E ￾ L 4 b
≤ O (nW T). (48) Now, there are two cases we need to consider. Case I: If PλnT b=1 ≥ √ λT n , then (48) can be rewritten as: λ 4n 4T 4 log n P 1 λnT b=1 E(Db) n [ PλnT b=1 E(Lb)] 2 + PλnT b=1 E ￾ L 4 b
≤ O (nW T). (49) Since f(x) = x 4 is a convex function on R+, by applying Jenson’s inequality, we have: λnT X b=1 E ￾ L 4 b
≥ λnT X b=1 [E(Lb)]4 . (50) Invoking Holder’s inequality yields: (λnT X b=1 [E(Lb)]4 )1 4 λnT X b=1 1 !3 4 ≥ λnT X b=1 E(Lb), (51) which could be simplified to: λnT X b=1 [E(Lb)]4 ≥ (λnT) −3 " λnT X b=1 E(Lb) #4 (52) Bringing (50) and (52) into (49), we obtain: λ 4n 4T 4 log n 1 PλnT b=1 E(Db) n hPλnT b=1 E(Lb) i2 +(λnT) −3 " λnT X b=1 E(Lb) #4 ≤ O (nW T), (53)

10 which could be rewritten as: λ4n4T4 1ogn∑TE(D】 w sourn.da Cell Exploiting Young's inequality in(54)yields: 2) Feasible Super-cell (XnT) n ≤O(nWT) (55) (log n) ∑TE(D) Noting that D >E(D),we could simplify (55)as follows: (56 Case重：f∑TE(Lb)<,then(48)can be rewritten as: Fig.1.An illustration of the capture phase in the proposed capacity achieving λ4n4T41 1 scheme.The small squares with side length L are called cells while the big logn AnTD(点·n≤OmwT, (57) squares with side length L2 are called super-cells.(1)percent of the super- cells are feasible super-cells,which are located regularly in the network.Each pair of red circle and blue circle depicted in the cell is an active link.In the which is further simplified to: capture phase,as the figure indicates,we only allow transmissions inside the feasible super-cell and in a single feasible super-cell,only one transmission λ≤O(WDm-4logn). (58) can occur.The transmitter-receiver pair must reside in the same cell. Combining (56)(58)and noticing that D=O(n),we always have: Specifically,we choose a common number of duplications R and common capture range L for all the bits as follows: A≤0 gn (59) R=Θ (分)=6 logn (60) We thus conclude the proof. ■ Remark 6.1:Because,under the four assumptions,the se- In (60),we add log factor so as to ensure that the proposed cure protocol model is equivalent to the secure physical model, scheme is successful asymptotically almost surely.The scheme the result in Theorem 6.1 applies to the latter immediately under consists of two phases:duplication phase and capture phase.In the four assumptions.This is exactly a major result we have duplication phase,we schedule source-to-relay transmissions to guarantee that each bit is duplicated (R)times.In cap- mentioned in (3)in Section IV.From the theorem,we observe that the upper bound is independent of the eavesdropper density ture phase,we arrange relay-to-destination transmissions to e.This is not surprising since the secure protocol model is guarantee that each bit generated in the previous duplication also independent of v.. phase can be delivered to its desired destination successfully asymptotically almost surely.The duplication phase consists D VII.CAPACITY ACHIEVING SCHEME of time slots while the capture phase consists of e(D)time slots.Thus,if we can schedule each bit generated in In this section,under the secure protocol model,assuming the duplication phase to reach its destination in the next capture that D=(n(logn))and D=O(n).we present and phase,the delay of each bit is upper bounded by O(D).Now, analyze an efficient scheme which can obtain the capacity upper we present the detailed scheme as follows. bound derived in Theorem 6.1 up to poly-log factors. 1)Duplication Phase:Tessellate the network area into small squares with area 7log n.We call those small squares duplication cells.Then,asymptotically almost A.Scheme surely,there are e(logn)legitimate nodes in each du- In this subsection,we present the capacity-achieving scheme plication cell.Under the secure protocol model,in or- explicitly.In order to achieve the upper bound,we require that der to avoid interference,we invoke traditional TDMA the inequalities involved in the derivation of Theorem 6.1 all scheme:simultaneously active duplication cells are at hold with equality.This gives the best choice for Ro and Lo. least e((logn)2)away as (6)indicates.Hence,each

10 which could be rewritten as:    " λ 4n 4T 4 log n n PλnT b=1 E(Db) # 2 3 1 hPλnT b=1 E(Lb) i 4 3    3 2 +    (λnT) −1 " λnT X b=1 E(Lb) # 4 3    3 ≤ O (nW T). (54) Exploiting Young’s inequality in (54) yields: (λnT) 5 3 (log n) 2 3 n 2 3 hPλnT b=1 E(Db) i 2 3 ≤ O (nW T). (55) Noting that D ≥ E(Db), we could simplify (55) as follows: λ ≤ O W  D log n n 2 3 ! . (56) Case II: If PλnT b=1 E(Lb) < √ λT n , then (48) can be rewritten as: λ 4n 4T 4 log n 1 λnT D 1 ￾ 1 n2 · λnT
2 ≤ O(nW T), (57) which is further simplified to: λ ≤ O ￾ W Dn−4 log n
. (58) Combining (56)(58) and noticing that D = O (n), we always have: λ ≤ O W  D n 2 3 log n ! . (59) We thus conclude the proof. Remark 6.1: Because, under the four assumptions, the se￾cure protocol model is equivalent to the secure physical model, the result in Theorem 6.1 applies to the latter immediately under the four assumptions. This is exactly a major result we have mentioned in (3) in Section IV. From the theorem, we observe that the upper bound is independent of the eavesdropper density ψe. This is not surprising since the secure protocol model is also independent of ψe. VII. CAPACITY ACHIEVING SCHEME In this section, under the secure protocol model, assuming that D = Ω  n 2 5 (log n) 21 5  and D = O(n), we present and analyze an efficient scheme which can obtain the capacity upper bound derived in Theorem 6.1 up to poly-log factors. A. Scheme In this subsection, we present the capacity-achieving scheme explicitly. In order to achieve the upper bound, we require that the inequalities involved in the derivation of Theorem 6.1 all hold with equality. This gives the best choice for Rb and Lb. 2 L L Feasible Super-cell Cell   2 4 L Fig. 1. An illustration of the capture phase in the proposed capacity achieving scheme. The small squares with side length L are called cells while the big squares with side length L2 are called super-cells. Θ(1) percent of the super￾cells are feasible super-cells, which are located regularly in the network. Each pair of red circle and blue circle depicted in the cell is an active link. In the capture phase, as the figure indicates, we only allow transmissions inside the feasible super-cell and in a single feasible super-cell, only one transmission can occur. The transmitter-receiver pair must reside in the same cell. Specifically, we choose a common number of duplications R and common capture range L for all the bits as follows: R = Θ  n D  2 3  , L = Θ  n D  1 6 log n  . (60) In (60), we add log factor so as to ensure that the proposed scheme is successful asymptotically almost surely. The scheme consists of two phases: duplication phase and capture phase. In duplication phase, we schedule source-to-relay transmissions to guarantee that each bit is duplicated Θ(R) times. In cap￾ture phase, we arrange relay-to-destination transmissions to guarantee that each bit generated in the previous duplication phase can be delivered to its desired destination successfully asymptotically almost surely. The duplication phase consists of Θ  D (log n) 7  time slots while the capture phase consists of Θ(D) time slots. Thus, if we can schedule each bit generated in the duplication phase to reach its destination in the next capture phase, the delay of each bit is upper bounded by O(D). Now, we present the detailed scheme as follows. 1) Duplication Phase: Tessellate the network area into small squares with area 7 log n. We call those small squares duplication cells. Then, asymptotically almost surely, there are Θ(log n) legitimate nodes in each du￾plication cell. Under the secure protocol model, in or￾der to avoid interference, we invoke traditional TDMA scheme: simultaneously active duplication cells are at least Θ((log n) 2 ) away as (6) indicates. Hence, each