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 eavesdropping 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 computation/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 mathematical 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 secrecycapacity-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 informationtheoretic 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 networks 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 secrecy 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 fundamental 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 relatively 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 antennas 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 transmission 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 analyzing 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 formally. Throughout this section, we assume that the eavesdroppers 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 capacitydelay 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 simultaneously 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 successful 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)