Mobility Weakens the Distinction between Multicast and Unicast Yi Qin,Xiaohua Tian,Weijie Wu,Xinbing Wang Dept.of Electronic Engineering Shanghai Jiao Tong University,China Email:fqinyi 33,xtian,wwj,xwang8@sjtu.edu.cn Abstract-Comparing with the unicast technology,multiple node speed (random i.i.d.mobility model).There are also flows from the same source in multicast scenario can be aggregat- some studies focusing on other mobility models with different ed even if their destinations are different.This paper evaluates node speeds,e.g.,random walk models [4].restricted mobility such distinction by the multicast gain on per-node capacity and delay,which are defined as the per-node capacity and models [1][5][6].heterogeneous mobility models [7].In [5]. delay ratios between multi-unicast and multicast(m destinations the network is divided into squares,where the nodes obey i.i.d. for each multicast session).Particularly,the restricted mobility mobility model in each square and follow random walk model model [1]is proposed,which is a representative mobility model when moving among different squares.Moreover,[6 studies characterizing a class of mobility models with different average moving speeds.The theoretical analysis of this model indicates the case that each node's home-point can only be located in that the mobility significantly decreases the multicast gain on one of m clusters.This model indicates the fact that people are per-node capacity and delay,though the per-node capacity of more likely to be within the region where they live.However, both unicast and multicast can be enhanced by mobility.This the event of long distance movement happens with low proba- finding suggests that mobility weakens the distinction between bility in our real world.which is demonstrated in the mobility multicast and unicast.Finally,a general framework of multicast model in [1].In this model,each node has its own home-point, study is constituted by analyzing the upper-bound (e(m)),the lower-bound((1))and the main determinants of the multicast and the distance between it and its home-point follows power- gain on both per-node capacity and delay regardless of mobility law distribution.Although this model cannot well describe model. the continuity of node's mobility,it is suitable for the fast Index Terms-Restricted mobility,Multicast,Unicast,Capac- mobile networks.M.Garetto,et al.in [1]adopt a multi-hop ity,Delay scheme for the unicast scenario,which can enhance the per- node throughput and delay by optimizing the configuration of their scheme.For example,when the exponent of the power- I.INTRODUCTION law distribution parameter a equals to 2,constant per-node Network scaling laws for large-scale wireless ad hoc net- throughput and delay can be obtained simultaneously except works have been extensively studied since the seminal work for poly-logarithmic factors.Furthermore,some researchers by P.Gupta and P.R.Kumar [2].They focus on the unicast study the heterogeneous mobility model which is feasible for scenario of random wireless networks with n static nodes. the nodes with different mobility models [7]. This work shows that the per-node throughput upper-bound can be achieved by their scheme.However.thereare The studies above drill down into the impact of mobility on unicast per-node capacity,and their results indicate that the a large number of wireless mobile devices in the real world. mobility enhances the unicast per-node capacity performance. Thus,many researchers focus on the network scaling laws However,unicast is only a special case of multicast standing of mobile networks [3]-[10].With the help of mobility,long for a more general traffic pattern.Therefore,the impact of distance transmission can be realized,which is not allowed in mobility on multicast becomes a hot topic 8]-101.In [81.J.J. static networks because of the limitation of transmission power Garcia-Luna-Aceves et al.focus on the multicast scenario for and interference.Hence,in contrast with static networks, the static networks.In their study,there are n static nodes in node mobility can improve the per-node throughput and delay the network,and each node has m(m n)destinations.The performance.In [3].D.Shah,et al.show that e(1)per-node results demonstrate that the achievable per-node throughput throughput is obtained in random i.i.d.mobility model for upper-bound is e （Vmn logn)】 when m o n log and unicast scenario. Nevertheless,[2]and [3]only analyze two extreme cases the upper-bound is (for the case m )By of mobility,i.e.lowest node speed (static model)and highest introducing the mobility into multicast networks,9 analyzes the multicast per-node capacity under random i.i.d.mobility We use standard asymptotic notations in our paper.Consider t model,which proves that mobility can also increase the mul- wo nonnegative function f()and g():(1)f(n)=o(g(n)) means limnoo f(n)/g(n)=0.(2)f(n)= O(g(n)）mean- ticast per-node capacity.Another mobility model with limited s limno f(n)/g(n)0.(5)f(n)=e(g(n))means f(n)=O(g(n)) is limited by R,and the per-node capacity of the network is and g(n)=O(f(n)).(6)f(n)=e(g(n))means f(n)=e(g(n))when a non-decreasing function of R.The theoretical results also ignoring poly-logarithmic factor. demonstrate that mobility can enhance the multicast per-node
1 Mobility Weakens the Distinction between Multicast and Unicast Yi Qin, Xiaohua Tian, Weijie Wu, Xinbing Wang Dept. of Electronic Engineering Shanghai Jiao Tong University, China Email: {qinyi 33, xtian, wwj, xwang8}@sjtu.edu.cn Abstract—Comparing with the unicast technology, multiple flows from the same source in multicast scenario can be aggregated even if their destinations are different. This paper evaluates such distinction by the multicast gain on per-node capacity and delay, which are defined as the per-node capacity and delay ratios between multi-unicast and multicast (m destinations for each multicast session). Particularly, the restricted mobility model [1] is proposed, which is a representative mobility model characterizing a class of mobility models with different average moving speeds. The theoretical analysis of this model indicates that the mobility significantly decreases the multicast gain on per-node capacity and delay, though the per-node capacity of both unicast and multicast can be enhanced by mobility. This finding suggests that mobility weakens the distinction between multicast and unicast. Finally, a general framework of multicast study is constituted by analyzing the upper-bound (Θ(m)), the lower-bound (Θ(1)) and the main determinants of the multicast gain on both per-node capacity and delay regardless of mobility model. Index Terms—Restricted mobility, Multicast, Unicast, Capacity, Delay I. INTRODUCTION Network scaling laws for large-scale wireless ad hoc networks have been extensively studied since the seminal work by P. Gupta and P. R. Kumar [2]. They focus on the unicast scenario of random wireless networks with n static nodes. This work shows that the per-node throughput upper-bound Θ √ 1 n 1 can be achieved by their scheme. However, there are a large number of wireless mobile devices in the real world. Thus, many researchers focus on the network scaling laws of mobile networks [3]-[10]. With the help of mobility, long distance transmission can be realized, which is not allowed in static networks because of the limitation of transmission power and interference. Hence, in contrast with static networks, node mobility can improve the per-node throughput and delay performance. In [3], D. Shah, et al. show that Θ(1) per-node throughput is obtained in random i.i.d. mobility model for unicast scenario. Nevertheless, [2] and [3] only analyze two extreme cases of mobility, i.e. lowest node speed (static model) and highest 1We use standard asymptotic notations in our paper. Consider two nonnegative function f(·) and g(·): (1) f(n) = o(g(n)) means limn→∞ f(n)/g(n) = 0. (2) f(n) = O(g(n)) means limn→∞ f(n)/g(n) 0. (5) f(n) = Θ(g(n)) means f(n) = O(g(n)) and g(n) = O(f(n)). (6) f(n) = Θ( e g(n)) means f(n) = Θ(g(n)) when ignoring poly-logarithmic factor. node speed (random i.i.d. mobility model). There are also some studies focusing on other mobility models with different node speeds, e.g., random walk models [4], restricted mobility models [1][5][6], heterogeneous mobility models [7]. In [5], the network is divided into squares, where the nodes obey i.i.d. mobility model in each square and follow random walk model when moving among different squares. Moreover, [6] studies the case that each node’s home-point can only be located in one of m clusters. This model indicates the fact that people are more likely to be within the region where they live. However, the event of long distance movement happens with low probability in our real world, which is demonstrated in the mobility model in [1]. In this model, each node has its own home-point, and the distance between it and its home-point follows powerlaw distribution. Although this model cannot well describe the continuity of node’s mobility, it is suitable for the fast mobile networks. M. Garetto, et al. in [1] adopt a multi-hop scheme for the unicast scenario, which can enhance the pernode throughput and delay by optimizing the configuration of their scheme. For example, when the exponent of the powerlaw distribution parameter α equals to 2, constant per-node throughput and delay can be obtained simultaneously except for poly-logarithmic factors. Furthermore, some researchers study the heterogeneous mobility model which is feasible for the nodes with different mobility models [7]. The studies above drill down into the impact of mobility on unicast per-node capacity, and their results indicate that the mobility enhances the unicast per-node capacity performance. However, unicast is only a special case of multicast standing for a more general traffic pattern. Therefore, the impact of mobility on multicast becomes a hot topic [8]-[10]. In [8], J.J. Garcia-Luna-Aceves et al. focus on the multicast scenario for the static networks. In their study, there are n static nodes in the network, and each node has m(m < n) destinations. The results demonstrate that the achievable per-node throughput upper-bound is Θ √ 1 mn log n when m = o n log n , and the upper-bound is Θ 1 n for the case m = Ω n log n . By introducing the mobility into multicast networks, [9] analyzes the multicast per-node capacity under random i.i.d. mobility model, which proves that mobility can also increase the multicast per-node capacity. Another mobility model with limited node speed is given in [10]. In this paper, the node speed is limited by R, and the per-node capacity of the network is a non-decreasing function of R. The theoretical results also demonstrate that mobility can enhance the multicast per-node
3 capacity. mainly determined by the difference of delay for different In order to further understand the above phenomenon. nodes. the distinction between the performance enhancements by Differences from previous work:This work is the first mobility is analyzed for unicast and multicast.In particular, study on the optimal capacity and delay performance this paper focuses on a class of mobility models proposed for the restricted mobility model in both unicast and by M.Garetto,et al.[1],i.e.restricted mobility model, multicast scenarios.Moreover,different from previous which includes mobility models such as static model,random work,this paper mainly focuses on the performance ratios i.i.d.mobility model,etc.Furthermore,the node speed is a between the two scenarios in order to investigate the decreasing function of a,which is the exponent of the power- impact of mobility on multicast gain.Additionally,some law distribution in this restricted mobility model.Therefore, other essential factors determining the multicast gain are the impact of mobility on the network per-node capacity also analyzed. can be investigated by adjusting o.In this model,the per- The rest of this paper is organized as follows.In Section node capacity and delay are analyzed for both unicast and II,the network model and definitions are introduced.The multicast,respectively.The results demonstrate that mobility per-node capacity is analyzed for both unicast and multicast can increase the per-node capacity for both of them.However, scenarios in Section III.In Section IV,the delay performance it weakens the distinction between multicast and unicast since is studied for the two scenarios.In Section V.the multicast the opportunity of flow aggregation is reduced by mobility. gain on per-node capacity and delay are investigated.Finally, Moreover,the delay of unicast and multicast are the same in conclusion is summarized in Section VI. order sense in the restricted mobility model.and the mobility only reduces the multicast delay gain in constant order. II.SYSTEM MODEL AND DEFINITIONS To support the above conclusion,the main contributions of this paper are summarized as follows: A.Network Model Contribution on capacity:This paper focuses on the There are n nodes in the networks.In order to simplify the multicast capacity gain2 for the restricted mobility mod- performance analysis,the shape of network is assumed to be a el in two traffic patterns,i.e.,unicast and multicas- torus defined as O with size√mXv元，and all of the n nodes t.The bottleneck of network per-node throughput is (users)are moving on its surface.Hence,the node density is considered,and the per-node capacity is derived for 1,and edge effect is ignored in this model. the two traffic patterns,which shows the enhancement of per-node capacity by increasing the moving speed. Denoting the number of destinations as m and the B.Mobility Model total number of nodes as n,and the multicast gain In our system,time is divided into slots with equal duration. on per-node capacity under different circumstances sat- The fast mobility case is considered.in which the node isfies (1)(m)(m for the mobility is of the same time-scale as packet transmission. cases{0≤a3},respective Under such time division,one node can only transmit one ly,where a is the exponential coefficient of restricted packet to another node in one hop when they are connected. mobility model.These results demonstrate that mobility The position of node i(i=1,...,n)at time slot t(t= significantly decreases the multicast capacity gain.More- 0.1....)is denoted as X;(t).In random i.i.d.mobility model. over,the results also indicate that m enhances the dis- the Xi(t)is randomly,uniformly and independently selected tinction as the secondary determinant.Additionally,this in the network in each time slot.Therefore,the moving speed paper further studies the upper-bound and lower-bound of of nodes in the network isθ（√m)per--timeslot,,which cannot multicast capacity gain regardless of the mobility model, be adjusted.In this paper,the restricted mobility model in [1] which are e(m)and e(1),respectively.Based on these is adopted instead.In this model,for any i and t,the Xi(t) is independently distributed in O.This assumption is widely results,the factors determining the multicast capacity gain are summarized,which form a general framework of the introduced in network performance research as in [11]-[14]. multicast capacity. However,the mobility of nodes in the network is restricted. Contribution on delay:The impact of mobility on i.e.,the Xi(t)is not uniformly distributed in the networks, multicast delay gain is studied by adopting the flooding which is different from the random i.i.d.mobility model. scheme,which is capable of achieving the delay lower- In this model,for each node i,there is a corresponding bound of the two traffic patterns.By considering the home-point located at H;which is the mobility center of i. information expansion speed,it can be derived that the Moreover,the home-point is static and uniformly,independent- multicast gain of optimal delay with limited transmission ly distributed in the network.Although the uniform density range is (m),and the mobility strength reduces it in may appear to be idealized,it can be a good scenario for the constant order.In the further study,this paper investigates initial study of the impact of mobility due to its mathematical the upper-bound ((m))and lower-bound ((m))of tractability.In this model,three kinds of distance are defined. multicast delay gain in a more general network.Accord- The distance between nodes (users)i and j at time slot t ing to the theoretical results,the multicast delay gain is is defined as pi,(t)=lXi(t)-X(t)l,where‖·l‖is the operation of Euclidean distance.The distance between home- 2The ratio of the capacity of multicast and multi-unicast.See Definition 3. points Hi and Hj is represented as p=H
2 capacity. In order to further understand the above phenomenon, the distinction between the performance enhancements by mobility is analyzed for unicast and multicast. In particular, this paper focuses on a class of mobility models proposed by M. Garetto, et al. [1], i.e. restricted mobility model, which includes mobility models such as static model, random i.i.d. mobility model, etc. Furthermore, the node speed is a decreasing function of α, which is the exponent of the powerlaw distribution in this restricted mobility model. Therefore, the impact of mobility on the network per-node capacity can be investigated by adjusting α. In this model, the pernode capacity and delay are analyzed for both unicast and multicast, respectively. The results demonstrate that mobility can increase the per-node capacity for both of them. However, it weakens the distinction between multicast and unicast since the opportunity of flow aggregation is reduced by mobility. Moreover, the delay of unicast and multicast are the same in order sense in the restricted mobility model, and the mobility only reduces the multicast delay gain in constant order. To support the above conclusion, the main contributions of this paper are summarized as follows: • Contribution on capacity: This paper focuses on the multicast capacity gain2 for the restricted mobility model in two traffic patterns, i.e., unicast and multicast. The bottleneck of network per-node throughput is considered, and the per-node capacity is derived for the two traffic patterns, which shows the enhancement of per-node capacity by increasing the moving speed. Denoting the number of destinations as m and the total number of nodes as n, and the multicast gain on per-node capacity under different circumstances satisfies n Θ(1), Θ log n log n m , Θ m α 2 −1 , Θ (√ m) o for the cases {0 ≤ α 3}, respectively, where α is the exponential coefficient of restricted mobility model. These results demonstrate that mobility significantly decreases the multicast capacity gain. Moreover, the results also indicate that m enhances the distinction as the secondary determinant. Additionally, this paper further studies the upper-bound and lower-bound of multicast capacity gain regardless of the mobility model, which are Θ(m) and Θ(1), respectively. Based on these results, the factors determining the multicast capacity gain are summarized, which form a general framework of the multicast capacity. • Contribution on delay: The impact of mobility on multicast delay gain is studied by adopting the flooding scheme, which is capable of achieving the delay lowerbound of the two traffic patterns. By considering the information expansion speed, it can be derived that the multicast gain of optimal delay with limited transmission range is Θ(m), and the mobility strength reduces it in constant order. In the further study, this paper investigates the upper-bound (Θ(m)) and lower-bound (Θ(m)) of multicast delay gain in a more general network. According to the theoretical results, the multicast delay gain is 2The ratio of the capacity of multicast and multi-unicast. See Definition 3. mainly determined by the difference of delay for different nodes. • Differences from previous work: This work is the first study on the optimal capacity and delay performance for the restricted mobility model in both unicast and multicast scenarios. Moreover, different from previous work, this paper mainly focuses on the performance ratios between the two scenarios in order to investigate the impact of mobility on multicast gain. Additionally, some other essential factors determining the multicast gain are also analyzed. The rest of this paper is organized as follows. In Section II, the network model and definitions are introduced. The per-node capacity is analyzed for both unicast and multicast scenarios in Section III. In Section IV, the delay performance is studied for the two scenarios. In Section V, the multicast gain on per-node capacity and delay are investigated. Finally, conclusion is summarized in Section VI. II. SYSTEM MODEL AND DEFINITIONS A. Network Model There are n nodes in the networks. In order to simplify the performance analysis, the shape of network is assumed to be a torus defined as O with size √ n× √ n, and all of the n nodes (users) are moving on its surface. Hence, the node density is 1, and edge effect is ignored in this model. B. Mobility Model In our system, time is divided into slots with equal duration. The fast mobility case is considered, in which the node mobility is of the same time-scale as packet transmission. Under such time division, one node can only transmit one packet to another node in one hop when they are connected. The position of node i(i = 1, · · · , n) at time slot t(t = 0, 1, · · ·) is denoted as Xi(t). In random i.i.d. mobility model, the Xi(t) is randomly, uniformly and independently selected in the network in each time slot. Therefore, the moving speed of nodes in the network is Θ(√ n) per-timeslot, which cannot be adjusted. In this paper, the restricted mobility model in [1] is adopted instead. In this model, for any i and t, the Xi(t) is independently distributed in O. This assumption is widely introduced in network performance research as in [11]-[14]. However, the mobility of nodes in the network is restricted, i.e., the Xi(t) is not uniformly distributed in the networks, which is different from the random i.i.d. mobility model. In this model, for each node i, there is a corresponding home-point located at Hi which is the mobility center of i. Moreover, the home-point is static and uniformly, independently distributed in the network. Although the uniform density may appear to be idealized, it can be a good scenario for the initial study of the impact of mobility due to its mathematical tractability. In this model, three kinds of distance are defined. The distance between nodes (users) i and j at time slot t is defined as ρi,j (t) = kXi(t) − Xj (t)k, where k · k is the operation of Euclidean distance. The distance between homepoints Hi and Hj is represented as ρ H i,j = kHi − Hjk
Furthermore,the distance between node (user)i and its home- one of the cells is denoted as cell (1,1),i.e.C1.1.Then,all the point Hi at time t is pi(t)=i(t)-Hill.In this model,the cells in the network can be denoted as Ca,b(1≤a,b≤√冗)， distribution of p;(t)is modeled as a non-increasing function respectively. f(p)to ensure that the node is more likely to be close to its home-point.Many papers focus on the distribution function D.Traffic Models f(p)[1][6][15]-[17].In our paper,according to [1],the f(p) is expressed as follow Two traffic patterns are studied in this paper,which are Unicast and Multicast.Firstly,in the unicast scenario,each f(p)= s(p) (1) node randomly selects another node as its destination.The ∫∫os(p) transmission from one source to its destination(maybe through where s(p)=min{1,p-}and a >0.Consequently,the multi-hop)is denoted as one unicast session. f(p)can be further calculated as For the multicast scenario,each node i randomly selects m different nodes as its destinations.Node i needs to transmit 日s(p)n 0≤a2. Although this mobility model is not accurate enough com- E.Network Performance Metrics and Some Notations paring with the practical user movement,it is proved to be Some definitions of the performance metrics are listed as appropriate for modeling human and vehicular mobility [1], follows. which is supported by many measurements papers [16][17]. Definition 1:(Per-node Throughput)For a given scheme, Moreover,it can be found in (2)that the averaged moving the per-node throughput is defined as the maximum achievable distance in each time slot is determined by o.Therefore,the transmission rate as in [2.In t time slots,there are M(i,t) moving speed of nodes in the network can be adjusted by a, packets transmitted from node i to its destination(s).Firstly, and hence this is an appropriate model for the study of the the long term per-node throughput is defined by Ai(n)as impact of mobility on network performance. 入o=四6， (5) C.Communication Model Afterwards,the per-node throughput of this model for a given In this paper,the protocol model is adopted,which is a scheme is defined by the maximum T(n)that satisfies simplified version of physical model since it ignores the long distance interference and transmission.Moreover,it is shown limP(入(n)≥T(n)for all i)=l. (6 门→G0 in [2]that the physical model can be treated as the protocol model on scaling law when the transmission is allowed for This paper studies the random networks instead of arbitrary the case that the Signal to Interference Noise Ratio (SINR)is ones.The transport throughput,which is defined as the rate greater than a given threshold.In this model,a transmission timing the distance,is not appropriate in our networks since between node i and j is successful if the following inequality it is just defined for arbitrary networks [2]. Definition 2:(Per-node Capacity)For a given network,the is satisfied IX2-X≤r(n), (3) per-node capacity of it is defined as where r(n)is the maximum transmission range of each node. C(n)=maxT(n), (7) σE Moreover,any other transmitting node k must satisfy the where o is a scheme for the network,is the set of all possible inequality as schemes,and T(n)is the per-node throughput of scheme a. IXk-Xl≥(1+△)r(n): (4) Definition 3:(Multicast Capacity Gain)For a given net- work,the per-node capacity of multicast is assumed to be where A >0 is a constant factor that depends on the Cmulti(n).Moreover,if each node has m destinations,each acceptable SINR of the network.Furthermore,the bandwidth multicast session can be treated as m unicast sessions (multi- of the network is finite and constant.In this model,the unicast),and the corresponding sum per-node capacity is transmission range r(n)is assumed to be r(n)=e(1)[2]. denoted as Cm_uni(n).Comparing the capacity of multicast and therefore each node can meet another node within its and multi-unicast,the multicast capacity gain is defined as transmission range with constant probability. Furthermore,the TDMA scheme is employed to guaran- (n)= Cmulti(n) (8) tee that each transmission is successful.In the K2-TDMA Cm_uni(m） scheme,the network is divided intocells with equal The multicast capacity gain (n)indicates the enhancement size r2(n).and only one of the K2 cells nearby is allowed to of per-node capacity by multicast transmission. be active,i.e.,K2-TDMA scheme allows each K2 adjacent Definition 4:(Network Delay)For a given scheme,assuming cells to be active with a round-robin fashion.K is a constant that the source sends the packet to the network at time slot and satisfies (K-1)r(n)/v2>(1+A)r(n).Hence,K is ts and the destination receives the packet at time slot ta,the defined as K =[1+(1+A)v27.Without loss of generality, delay is defined as the average value of ta-t,i.e.,Eftd-t}
3 Furthermore, the distance between node (user) i and its homepoint Hi at time t is ρi(t) = kXi(t)− Hik. In this model, the distribution of ρi(t) is modeled as a non-increasing function f(ρ) to ensure that the node is more likely to be close to its home-point. Many papers focus on the distribution function f(ρ) [1] [6] [15]-[17]. In our paper, according to [1], the f(ρ) is expressed as follow f(ρ) = s(ρ) R R O s(ρ) , (1) where s(ρ) = min{1, ρ−α} and α ≥ 0. Consequently, the f(ρ) can be further calculated as f(ρ) = Θ s(ρ)n α−2 2 0 ≤ α 2. (2) Although this mobility model is not accurate enough comparing with the practical user movement, it is proved to be appropriate for modeling human and vehicular mobility [1], which is supported by many measurements papers [16] [17]. Moreover, it can be found in (2) that the averaged moving distance in each time slot is determined by α. Therefore, the moving speed of nodes in the network can be adjusted by α, and hence this is an appropriate model for the study of the impact of mobility on network performance. C. Communication Model In this paper, the protocol model is adopted, which is a simplified version of physical model since it ignores the long distance interference and transmission. Moreover, it is shown in [2] that the physical model can be treated as the protocol model on scaling law when the transmission is allowed for the case that the Signal to Interference Noise Ratio (SINR) is greater than a given threshold. In this model, a transmission between node i and j is successful if the following inequality is satisfied kXi − Xjk ≤ r(n), (3) where r(n) is the maximum transmission range of each node. Moreover, any other transmitting node k must satisfy the inequality as kXk − Xjk ≥ (1 + ∆)r(n), (4) where ∆ > 0 is a constant factor that depends on the acceptable SINR of the network. Furthermore, the bandwidth of the network is finite and constant. In this model, the transmission range r(n) is assumed to be r(n) = Θ(1) [2], and therefore each node can meet another node within its transmission range with constant probability. Furthermore, the TDMA scheme is employed to guarantee that each transmission is successful. In the K2 -TDMA scheme, the network is divided into n r 2(n) cells with equal size r 2 (n), and only one of the K2 cells nearby is allowed to be active, i.e., K2 -TDMA scheme allows each K2 adjacent cells to be active with a round-robin fashion. K is a constant and satisfies (K − 1)r(n)/ √ 2 ≥ (1 + ∆)r(n). Hence, K is defined as K = d1 + (1 + ∆)√ 2e. Without loss of generality, one of the cells is denoted as cell (1, 1), i.e. C1,1. Then, all the cells in the network can be denoted as Ca,b(1 ≤ a, b ≤ √ n), respectively. D. Traffic Models Two traffic patterns are studied in this paper, which are Unicast and Multicast. Firstly, in the unicast scenario, each node randomly selects another node as its destination. The transmission from one source to its destination (maybe through multi-hop) is denoted as one unicast session. For the multicast scenario, each node i randomly selects m different nodes as its destinations. Node i needs to transmit the same packet to all of its destinations. The multicast session is defined as the transmission from the source to all of its destinations (maybe through multi-hop). E. Network Performance Metrics and Some Notations Some definitions of the performance metrics are listed as follows. Definition 1: (Per-node Throughput) For a given scheme, the per-node throughput is defined as the maximum achievable transmission rate as in [2]. In t time slots, there are M(i, t) packets transmitted from node i to its destination(s). Firstly, the long term per-node throughput is defined by λi(n) as λi(n) = lim inf t→∞ 1 t M(i, t). (5) Afterwards, the per-node throughput of this model for a given scheme is defined by the maximum T(n) that satisfies limn→∞ P(λi(n) ≥ T(n) for all i) = 1. (6) This paper studies the random networks instead of arbitrary ones. The transport throughput, which is defined as the rate timing the distance, is not appropriate in our networks since it is just defined for arbitrary networks [2]. Definition 2: (Per-node Capacity) For a given network, the per-node capacity of it is defined as C(n) = max σ∈Σ Tσ(n), (7) where σ is a scheme for the network, Σ is the set of all possible schemes, and Tσ(n) is the per-node throughput of scheme σ. Definition 3: (Multicast Capacity Gain) For a given network, the per-node capacity of multicast is assumed to be Cmulti(n). Moreover, if each node has m destinations, each multicast session can be treated as m unicast sessions (multiunicast), and the corresponding sum per-node capacity is denoted as Cm uni(n). Comparing the capacity of multicast and multi-unicast, the multicast capacity gain is defined as ξ(n) = Cmulti(n) Cm uni(n) . (8) The multicast capacity gain ξ(n) indicates the enhancement of per-node capacity by multicast transmission. Definition 4: (Network Delay) For a given scheme, assuming that the source sends the packet to the network at time slot ts and the destination receives the packet at time slot td, the delay is defined as the average value of td−ts, i.e., E{td−ts}
TABLE I this paper focuses on the scaling law of the performance,the NOTATIONS AND DEFINITIONS order of pi.k satisfies Notation Definition n The total number of nodes in the network. pi,k=日 f(llX:-Hll)f(llX-Hll) m The number of destinations for each source in multicast scenario. X,Xk∈Ca.b,1≤a,bsvm (11) E(n) The multicast capacity gain s(n) The multicast delay gain. where So is the size of one cell and So =e(1).The pi.k The parameter of restricted mobility model. can be calculated in the similar way to that in [1],and it is Cn)】 The per-node capacity performance. D(n) The delay performance. expressed as DSDT The delay for the case that data is only 0≤a≤1 delivered by short distance transmission 12. It should be noted that the queuing delay at source is not considered here,which is the same as in many important work where p =Va+b is the distance between two home- [1][4].Moreover,for wireless networks,the operation time points.It can be found from(12)that the probability is similar spent in coding/decoding is assumed to be negligible compared to random i.i.d.mobility model when 03. The multicast delay gain (n)indicates the enhancement of delay performance by multicast transmission. Proof:The proof of this theorem can be divided into Finally,some essential notations and definitions are listed two parts.Firstly,(13)is proved to be the upper-bound of in Table I3. the unicast capacity.Afterwards,the corresponding upper- bound achieving scheme is proposed to demonstrate that (13) is achievable.Finally,according to the definition of capacity, III.CAPACITY ANALYSIS FOR UNICAST AND MULTICAST the per-node capacity for unicast scenario under restricted mobility model satisfies (13).The detailed proof can be found In this section,the capacity performance is analyzed for both unicast and multicast scenarios.Moreover,the multicast in Appendix A,and the capacity achieving scheme is proposed as follows. capacity gain based on the results of this section will be Scheme I:In this scheme,the transmission range satisfies discussed in Section V. r(n)=e(1),and there are three kinds of transmissions: source to relay (S-R)transmission,relay to relay transmission A.Per-node Capacity of Unicast Scenario (R-R)as well as relay to destination (R-D)transmission.In each time slot,when one cell is active according to TDMA Different from the random i.i.d.mobility model,the prob- scheme,each kind of transmission will be selected with the ability that two nodes meet each other is related with the same probability.Furthermore,one transmission pair belongs distance between them.Considering two arbitrary nodes i and to the selected transmission kind will be chosen to be active k,the probability that i meets k can be expressed as equiprobably. Pi,k ·If0≤a≤3，R-R transmission is not allowed.For any source-destination pair,denoting their home-points f(H) f(Xk-Hkll)dxkdxi. distance as p and the middle point of their home-points X∈Ca.b as C,the source is only permitted to transmit packet to (10) one relay with home-point located in the circle centered Without loss of generality,we assume that node i's home- at C with radius p.Afterwards,the relay will send the point is in C1.1 and node k's home-point is in Cax.b Since packet to the destination when they are in the same cell. If a 3,three kinds of transmissions are allowed. 3The detailed discussion of Dspr and DLDT can be found in Section Considering the straight line which connects the home- IV points of source and destination,the set of the cells it
4 TABLE I NOTATIONS AND DEFINITIONS Notation Definition n The total number of nodes in the network. m The number of destinations for each source in multicast scenario. ξ(n) The multicast capacity gain. ζ(n) The multicast delay gain. α The parameter of restricted mobility model. C(n) The per-node capacity performance. D(n) The delay performance. DSDT The delay for the case that data is only delivered by short distance transmission. DLDT The delay for the case that data is only delivered by long distance transmission. It should be noted that the queuing delay at source is not considered here, which is the same as in many important work [1] [4]. Moreover, for wireless networks, the operation time spent in coding/decoding is assumed to be negligible compared to the transmission time. Definition 5: (Multicast Delay Gain) For a given network, the network delay of multicast is assumed to be Dmulti(n). Moreover, if each node has m destinations, the sum delay of the transmissions from the source to them by unicast is denoted as Dm uni(n). Comparing the delay of multicast and multi-unicast, the multicast delay gain is defined as ζ(n) = Dm uni(n) Dmulti(n) . (9) The multicast delay gain ζ(n) indicates the enhancement of delay performance by multicast transmission. Finally, some essential notations and definitions are listed in Table I3 . III. CAPACITY ANALYSIS FOR UNICAST AND MULTICAST In this section, the capacity performance is analyzed for both unicast and multicast scenarios. Moreover, the multicast capacity gain based on the results of this section will be discussed in Section V. A. Per-node Capacity of Unicast Scenario Different from the random i.i.d. mobility model, the probability that two nodes meet each other is related with the distance between them. Considering two arbitrary nodes i and k, the probability that i meets k can be expressed as pi,k = X Ca,b Z Xi∈Ca,b f(kXi − Hik) Z Xk∈Ca,b f(kXk − Hkk)dXkdXi. (10) Without loss of generality, we assume that node i’s homepoint is in C1,1 and node k’s home-point is in Cak,bk . Since 3The detailed discussion of DSDT and DLDT can be found in Section IV. this paper focuses on the scaling law of the performance, the order of pi,k satisfies pi,k = Θ S 2 0 X Xi,Xk∈Ca,b,1≤a,b≤ √n f(kXi − Hik)f(kXk − Hkk) , (11) where S0 is the size of one cell and S0 = Θ (1). The pi,k can be calculated in the similar way to that in [1], and it is expressed as p(ρ) = Θ n −1 0 ≤ α ≤ 1, Θ ρ 2−2αn α−2 1 2, (12) where ρ = p a 2 k + b 2 k is the distance between two homepoints. It can be found from (12) that the probability is similar to random i.i.d. mobility model when 0 ≤ α ≤ 1. However, for other cases, the probability becomes different. Based on this mobility model, the per-node capacity of the network is derived in the following theorem. Theorem 1: The per-node capacity for unicast scenario under restricted mobility model is C(n) = Θ (1) 0 ≤ α 3. (13) Proof: The proof of this theorem can be divided into two parts. Firstly, (13) is proved to be the upper-bound of the unicast capacity. Afterwards, the corresponding upperbound achieving scheme is proposed to demonstrate that (13) is achievable. Finally, according to the definition of capacity, the per-node capacity for unicast scenario under restricted mobility model satisfies (13). The detailed proof can be found in Appendix A, and the capacity achieving scheme is proposed as follows. Scheme I: In this scheme, the transmission range satisfies r(n) = Θ(1), and there are three kinds of transmissions: source to relay (S-R) transmission, relay to relay transmission (R-R) as well as relay to destination (R-D) transmission. In each time slot, when one cell is active according to TDMA scheme, each kind of transmission will be selected with the same probability. Furthermore, one transmission pair belongs to the selected transmission kind will be chosen to be active equiprobably. • If 0 ≤ α ≤ 3, R-R transmission is not allowed. For any source-destination pair, denoting their home-points distance as ρ and the middle point of their home-points as C, the source is only permitted to transmit packet to one relay with home-point located in the circle centered at C with radius 1 3 ρ. Afterwards, the relay will send the packet to the destination when they are in the same cell. • If α > 3, three kinds of transmissions are allowed. Considering the straight line which connects the homepoints of source and destination, the set of the cells it
lines across can be defined as Path Set of this source- IV.DELAY ANALYSIS FOR UNICAST AND MULTICAST destination pair.The cells in the path set are denoted as Ci which is numbered according to the distance between In this section,the optimal delay performance is analyzed for both unicast and multicast scenarios,and the corresponding Ci and source's home-point.In addition,Co denotes the source's home-point cell.Based on such definition,if the multicast delay gain will be discussed in Section V. packet is hold by the node with home-point in Ci,it will be transmitted to node whose home-point is in cell Ci+ A.Optimal Delay of Unicast Scenario and deleted from the previous relay. To optimize the delay,it is necessary to utilize all the ◆ possible hops for one unicast.Therefore,a multi-hop scheme named flooding scheme is employed,which is shown as B.Per-node Capacity of Multicast Scenario follows. Scheme III:(Flooding Scheme)Four kinds of transmissions In multicast scenario,there are n sources and m destinations (S-R.R-R.R-D.D-R)are allowed in this scheme and will be for each source.which is different from the unicast scenario. selected equiprobably in any active cell.When S-R,R-R or The following lemma is proposed to show the number of D-R transmission is permitted,randomly choose a source (or corresponding sources for each destination. a relay)and broadcast the packet to all the nodes in the cell Lemma I:In multicast scenario,any node,when acting as simultaneously.Besides,if R-D transmission is selected,an a destination,has m sources with probability 1 when n goes R-D pair will be randomly chosen to be active. to infinity. In [1],the authors propose a multi-hop scheme without Proof:The proof can be found in Appendix B. redundancy.However,the redundancy is introduced in our Based on Lemma 1,the per-node capacity for multicast paper for flooding scheme which is different from theirs.It scenario is derived in the following theorem. is well studied in [4][18]that redundancy can decrease the Theorem 2:The per-node capacity for multicast scenario delay of networks because packet can be transmitted to the under restricted mobility model is destination through all of the possible paths,and the delay is Θ(1) determined by the shortest one.Moreover,it is obvious that if 03. therefore the transmission range is assumed as r(n)=e(1). √nm As introduced in [11],in order to achieve optimal delay.this Proof:Similar to Theorem 1,the proof can also be paper considers the situation that a single packet is delivered divided into two parts:1)C(n)in (14)is proved to be the over an empty network,which is analyzed in many work about upper-bound of multicast per-node capacity.2)The following the optimal delay [4.Therefore,only one source is allowed to Scheme II is proposed to achieve the capacity upper-bound. transmit its packet to the network until this packet is received The detailed proof can be found in Appendix C. by the destination Scheme II:In this scheme,the transmission range satisfies However,the flooding scheme in the restricted networks is r(n)=e(1),and there are four kinds of transmissions:S-R, quite different from the random i.i.d.mobile networks.In the R-D.R-R and destination to relay (D-R)transmission.In each restricted mobility model,the PDF of packet-holding nodes in time slot,one kind of transmission is selected with the same the next time slot is determined by the packet-holding nodes probability.Afterwards,one transmission pair belonging to it in current time slot.Therefore,the transmission process in restricted mobility model can be treated as a Markov chain is chosen equiprobably. with 2n-1 states.Moreover,there are 2n-2 target states and 1 。f0≤a<2,R-R and D-R transmissions are not al- initial state.Hence,it is too complex to obtain the exact order lowed.Traditional 2-hop relay scheme without redun- of delay. dancy [9]is employed here.In particular,the source Instead,this paper analyzes the upper-bound of the opti- transmits the packet to each relay within its transmission mal delay.In particular,the transmissions are divided into range.Afterwards,the relay will send the packet to the two groups,i.e.,long distance transmission (LDT)and short destinations when it is within the transmission range of distance transmission(SDT).The distance between two nodes' them. home-points is e(vn)for each LDT,and the distance is ·fa≥2，Four kinds of transmissions are allowed.Firstly,. o(vn)for each SDT.In this network,if a is small,the a Euclidean Minimum Spanning Tree (EMST)of the probability of LDT is large,and the probability of SDT multicast session is generated among the home-points of is small,and vice versa.In order to reduce the analysis source and destinations as in [19].The packet can be complexity,the packet is assumed to be transmitted to the transmitted to all the destinations based on the EMST, destination through only LDT or only SDT.Therefore,the and it is sent through each edge of the EMST as unicast cooperation between LDT and SDT is ignored,which causes by employing Scheme I. the derived delay greater than the actual delay,and thus it is ■ the delay upper-bound of flooding scheme
5 lines across can be defined as Path Set of this sourcedestination pair. The cells in the path set are denoted as Ci which is numbered according to the distance between Ci and source’s home-point. In addition, C0 denotes the source’s home-point cell. Based on such definition, if the packet is hold by the node with home-point in Ci , it will be transmitted to node whose home-point is in cell Ci+1 and deleted from the previous relay. B. Per-node Capacity of Multicast Scenario In multicast scenario, there are n sources and m destinations for each source, which is different from the unicast scenario. The following lemma is proposed to show the number of corresponding sources for each destination. Lemma 1: In multicast scenario, any node, when acting as a destination, has m sources with probability 1 when n goes to infinity. Proof: The proof can be found in Appendix B. Based on Lemma 1, the per-node capacity for multicast scenario is derived in the following theorem. Theorem 2: The per-node capacity for multicast scenario under restricted mobility model is C(n) = Θ 1 m 0 ≤ α 3. (14) Proof: Similar to Theorem 1, the proof can also be divided into two parts: 1) C(n) in (14) is proved to be the upper-bound of multicast per-node capacity. 2) The following Scheme II is proposed to achieve the capacity upper-bound. The detailed proof can be found in Appendix C. Scheme II: In this scheme, the transmission range satisfies r(n) = Θ(1), and there are four kinds of transmissions: S-R, R-D, R-R and destination to relay (D-R) transmission. In each time slot, one kind of transmission is selected with the same probability. Afterwards, one transmission pair belonging to it is chosen equiprobably. • If 0 ≤ α < 2, R-R and D-R transmissions are not allowed. Traditional 2-hop relay scheme without redundancy [9] is employed here. In particular, the source transmits the packet to each relay within its transmission range. Afterwards, the relay will send the packet to the destinations when it is within the transmission range of them. • If α ≥ 2, Four kinds of transmissions are allowed. Firstly, a Euclidean Minimum Spanning Tree (EMST) of the multicast session is generated among the home-points of source and destinations as in [19]. The packet can be transmitted to all the destinations based on the EMST, and it is sent through each edge of the EMST as unicast by employing Scheme I. IV. DELAY ANALYSIS FOR UNICAST AND MULTICAST In this section, the optimal delay performance is analyzed for both unicast and multicast scenarios, and the corresponding multicast delay gain will be discussed in Section V. A. Optimal Delay of Unicast Scenario To optimize the delay, it is necessary to utilize all the possible hops for one unicast. Therefore, a multi-hop scheme named flooding scheme is employed, which is shown as follows. Scheme III: (Flooding Scheme) Four kinds of transmissions (S-R, R-R, R-D, D-R) are allowed in this scheme and will be selected equiprobably in any active cell. When S-R, R-R or D-R transmission is permitted, randomly choose a source (or a relay) and broadcast the packet to all the nodes in the cell simultaneously. Besides, if R-D transmission is selected, an R-D pair will be randomly chosen to be active. In [1], the authors propose a multi-hop scheme without redundancy. However, the redundancy is introduced in our paper for flooding scheme which is different from theirs. It is well studied in [4] [18] that redundancy can decrease the delay of networks because packet can be transmitted to the destination through all of the possible paths, and the delay is determined by the shortest one. Moreover, it is obvious that if the transmission range is large enough (e.g. r(n) = √ n), the delay could be Θ(1). However, it is not reasonable to assume the transmission range to be related with network scale n, and therefore the transmission range is assumed as r(n) = Θ(1). As introduced in [11], in order to achieve optimal delay, this paper considers the situation that a single packet is delivered over an empty network, which is analyzed in many work about the optimal delay [4]. Therefore, only one source is allowed to transmit its packet to the network until this packet is received by the destination. However, the flooding scheme in the restricted networks is quite different from the random i.i.d. mobile networks. In the restricted mobility model, the PDF of packet-holding nodes in the next time slot is determined by the packet-holding nodes in current time slot. Therefore, the transmission process in restricted mobility model can be treated as a Markov chain with 2 n−1 states. Moreover, there are 2 n−2 target states and 1 initial state. Hence, it is too complex to obtain the exact order of delay. Instead, this paper analyzes the upper-bound of the optimal delay. In particular, the transmissions are divided into two groups, i.e., long distance transmission (LDT) and short distance transmission (SDT). The distance between two nodes’ home-points is Θ(√ n) for each LDT, and the distance is o( √ n) for each SDT. In this network, if α is small, the probability of LDT is large, and the probability of SDT is small, and vice versa. In order to reduce the analysis complexity, the packet is assumed to be transmitted to the destination through only LDT or only SDT. Therefore, the cooperation between LDT and SDT is ignored, which causes the derived delay greater than the actual delay, and thus it is the delay upper-bound of flooding scheme
Firstly,the delay of LDT is calculated in the following Fig.1 shows an example of flow aggregation.In this figure, lemma. the source needs to transmit a packet to all of its destinations Lemma 2:Considering the transmission from source i to It can be found that 11 hops are required for multi-unicast its destination j by flooding scheme,the average delay from case,and only 5 hops are needed in multicast scenario instead. source to destination by LDT can be expressed as The flows are aggregated in multicast scenario,which is the 日(1ogn) 0≤a2. gain on capacity and delay,respectively. Proof:The proof can be found in Appendix D. ■ Number of flows In Lemma 2,it shows that delay is great when o is large. Source Source The reason is that there are very few LDTs when a is large, and therefore SDT becomes the main issue.The delay of packet transmitted by SDT for the case a >2 is shown in the following lemma.The Dsor for 03 packets can also be transmitted in the network in the same way as unicast.However,with the help of flow aggregation, 4There is capacity hopping when a=2 because the convergence of series is changed in this case.The same phenomenon can be found in Fig.3. multicast may perform better than multi-unicast in some con- SThe mobility strength in this figure can be evaluated by the average moving ditions,which is considered to be the advantage of multicast. distance per-timeslot in the restricted mobility model
6 Firstly, the delay of LDT is calculated in the following lemma. Lemma 2: Considering the transmission from source i to its destination j by flooding scheme, the average delay from source to destination by LDT can be expressed as DLDT = Θ (log n) 0 ≤ α 2. (15) Proof: The proof can be found in Appendix D. In Lemma 2, it shows that delay is great when α is large. The reason is that there are very few LDTs when α is large, and therefore SDT becomes the main issue. The delay of packet transmitted by SDT for the case α ≥ 2 is shown in the following lemma. The DSDT for 0 ≤ α 3. (18) 4There is capacity hopping when α = 2 because the convergence of series is changed in this case. The same phenomenon can be found in Fig. 3. 5The mobility strength in this figure can be evaluated by the average moving distance per-timeslot in the restricted mobility model
Multicast In fact,the multicast brings about per-node capacity gain C(n) Multi-unicast due to the cooperation among destinations and relays,i.e.flow Mobility strength increases aggregation.However,the effect of cooperation is determined by the certainty of node location,namely,nodes will cooperate o(/m) effectively if their relative locations are certain with high ⊙(mog'(ml ⊙(nm-2)】 probability in each time slot.For this mobility model,if a3.the destinations'locations are approximately The impacts of a and m on (n)are illustrated in Fig.3 and fixed.Therefore,the multicast capacity gain is independent Fig.4,respectively. from a,and the cooperation among nodes has a strong impact on the per-node capacity gain.Consequently,this paper 5n)4 Mobility strength increases considers the mobility to be the first determinant since it determines the form of multicast capacity gain growth,but ⑨(m吹- m only determines the increasing speed. a(√m) The above results are specialized for the restricted mobility ⊙logn model.However,the further study of multicast capacity gain logn/m should include more mobility models.Thus,this paper will an- ©(1) alyze the upper-bound and lower-bound of multicast capacity gain regardless of mobility model. 0 2 For the upper-bound,since each destination is randomly selected.at least one unicast is contained in each multicast. Fig.3.The impact of o on multicast capacity gain Thus,if the multicast session can be finished during the unicast transmission,the per-node capacity of unicast and 5(n) multicast will be the same,and therefore the multicast gain on per-node capacity is e(m),which is the upper-bound.A O(n network achieving the upper-bound is proposed as follows. ⊙(m)Upper-bound The network size is vn x vn.All of the nodes are static, (m)One-dimensional static and their locations are (cossin).where i is the label of each node.This network is illustrated in Fig. Restricted mobilitya>3 Random walk 5,the unicast per-node capacity is derived by analyzing the (step length / maximum per-node throughput of the cut in this figure.If 2≤a≤3 the transmission range satisfies(n)it can be easily Random i.i.d.mobility obtained that only e(1)packets can be transmitted across the cut due to the interference.Therefore,the per-node throughput 0≤a3.In Fig.4,it is shown that (n)is a non-decreasing directions,which means the per-node capacity of multicast function of m.In particular,there is no multicast capacity gain is also e().Consequently,the multicast capacity gain for as long as 02.Furthermore,the increasing speed is determined by For the lower-bound,one multicast session can be treated a.The upper-bound,lower-bound and other mobility cases in as m unicast sessions no matter what the mobility model is. this figure will be analyzed later. Therefore,the per-node capacity of multicast is no less than
7 D C n( ) 4 1 m 1 1 m n m log 4 4(1 ) nm 1 2 2 2 ( ) n m D D 4 Multicast Multi-unicast 4(1 ) m n 1 m n log § · 4¨ ¸ © ¹ 1 2 1 ( ) n m D 4 Mobility strength increases Fig. 2. Per-node capacity comparison between multi-unicast and multicast scenarios The impacts of α and m on ξ(n) are illustrated in Fig. 3 and Fig. 4, respectively. D [ ( ) n 4(1) log ( ) log n n m 4 4 m 2 1 ( ) m D 4 Mobility strength increases Fig. 3. The impact of α on multicast capacity gain Restricted mobility m [ ( ) n 4(1) 0 D 4 0 2 d D 2 3 d d D D ! 3 Upper-bound Lower-bound 4 m 2 4( ) n l n Multicast capacity gain range of restricted mobility Random i.i.d. mobility Random walk (step length l) 4 m One-dimensional static 4( ) n Fig. 4. The impact of m on multicast capacity gain In Fig. 3, for a given m, the multicast capacity gain increases with α when 2 ≤ α ≤ 3. Otherwise, the multicast capacity gain is not related with α for the case 0 ≤ α 3. In Fig. 4, it is shown that ξ(n) is a non-decreasing function of m. In particular, there is no multicast capacity gain as long as 0 ≤ α 3, the destinations’ locations are approximately fixed. Therefore, the multicast capacity gain is independent from α, and the cooperation among nodes has a strong impact on the per-node capacity gain. Consequently, this paper considers the mobility to be the first determinant since it determines the form of multicast capacity gain growth, but m only determines the increasing speed. The above results are specialized for the restricted mobility model. However, the further study of multicast capacity gain should include more mobility models. Thus, this paper will analyze the upper-bound and lower-bound of multicast capacity gain regardless of mobility model. For the upper-bound, since each destination is randomly selected, at least one unicast is contained in each multicast. Thus, if the multicast session can be finished during the unicast transmission, the per-node capacity of unicast and multicast will be the same, and therefore the multicast gain on per-node capacity is Θ(m), which is the upper-bound. A network achieving the upper-bound is proposed as follows. The network size is √ n × √ n. All of the nodes are static, and their locations are ( √ n 2 cos 2πi n , √ n 2 sin 2πi n ), where i is the label of each node. This network is illustrated in Fig. 5, the unicast per-node capacity is derived by analyzing the maximum per-node throughput of the cut in this figure. If the transmission range satisfies r(n) > √ 2π n , it can be easily obtained that only Θ(1) packets can be transmitted across the cut due to the interference. Therefore, the per-node throughput upper-bound is Θ( 1 n ), which can be achieved by following scheme: setting r(n) = √ 3π n , for each source destination pair i, j (assuming i < j), the packet is relayed by i+1, i+2, · · · , j. For the multicast scenario, if the packet is transmitted to the two farthest destinations of both directions, all the other destinations must have already received the packets for the reason that they are relays or within the transmission range of relays. Hence, the multicast can be treated as two unicast between source and the two farthest destinations of both directions, which means the per-node capacity of multicast is also Θ( 1 n ). Consequently, the multicast capacity gain for this network is m, and it is the upper-bound. For the lower-bound, one multicast session can be treated as m unicast sessions no matter what the mobility model is. Therefore, the per-node capacity of multicast is no less than
The cut Source Destination n Center Fig.6.The transmission path from source to a destination B.The Multicast Delay Gain In order to investigate the multicast delay gain,a general network is considered,and the flooding scheme is employed. In fact,the flooding scheme utilizes all of the possible trans- n missions to deliver one packet,and therefore the delay of it is optimal for a given transmission range.Defining the Fig.5.The network with upper-bound of multicast capacity gain flooding scheme delay of the multicast with m destinations m-multi-unicast.which means the lower-bound of multicast as Dmulti(n)and the flooding scheme delay of each unicast capacity gain is e(1).To achieve the lower-bound,there must of its corresponding m-multi-unicast as Dm_uni.i(n),(i= be no cooperation among nodes,and the multicast session is 1,...,m),the relation between them satisfies equivalent to m unicast sessions.The case 0e is constant.Additionally, The number of destinations the distance between two parts is greater than the transmission The node distribution range.Moreover,with probability,one node in one part can move to another part in one time slot,and then it moves back to its initial part.Therefore,Dm_uni.im(n)= 6The multicast capacity gain for one-dimensional static model is (m). e(n)where poly-logarithmic factors are ignored.Howev- and it can be obtained in the similar as the network in Fig.5 ec,∑i=l,…inat-l,imax1,…,mDm.umi(n）=O(n3,which
8 The cut n n Center Fig. 5. The network with upper-bound of multicast capacity gain m-multi-unicast, which means the lower-bound of multicast capacity gain is Θ(1). To achieve the lower-bound, there must be no cooperation among nodes, and the multicast session is equivalent to m unicast sessions. The case 0 ≤ α e is constant. Additionally, the distance between two parts is greater than the transmission range. Moreover, with probability 1 n3 , one node in one part can move to another part in one time slot, and then it moves back to its initial part. Therefore, Dm uni,imax (n) = Θ(n 3 ) where poly-logarithmic factors are ignored. However, P i=1,··· ,imax−1,imax+1,··· ,m Dm uni,i(n) = O(n 3 ), which
9 means(20)is satisfied,and therefore the multicast delay gain The cut- is e(1)in this network. Consequently,the achievable bounds of multicast delay gain are proved,which form a general framework of multicast delay gain.However,the multicast delay gain is not mainly determined by the mobility strength in order sense but by the difference of delay for different nodes in flooding scheme,i.e., the difference between Dm_uni.i(n). VI.CONCLUSION This paper mainly focuses on the impact of mobility on multicast gain.The analysis of per-node capacity shows that mobility weakens the per-node capacity distinction between multicast and unicast.In particular,the per-node capacity for both unicast and multicast are derived,and two schemes based on restricted relay selection are proposed to achieve the Fig.7.The packet is transmitted across the cut per-node capacity.Afterwards,the multicast capacity gain is the cut with endpoint i as Wi,the sum weight of the edges calculated,which is utilized to evaluate the distinction between across the cut can be expressed as the per-node capacity enhancements for unicast and multicast. Moreover,the essential role of mobility and m in multicast is w=工W. (21) analyzed.Additionally,the upper-bound and lower-bound of iis in 1 multicast capacity gain are also studied regardless of mobility model,which may guide the multicast study in the future. According to the probability that two nodes happen to be Three factors which determine the multicast capacity gain are within distance e(1)in Eg.(11),the Wi can be further listed in order to form a general framework of multicast capac- expressed as ity.Furthermore,the multicast delay gain is also investigated. The upper-bound and lower-bound of it are derived and proved Wi=>p(p). (22) to be achievable.Moreover,it can be found that the multicast jis in Oz delay gain is not mainly determined by the mobility strength in Since the home-points in 2 are uniformly distributed and the order sense but by the difference of delay for different nodes size of the network is元x元，the order of Wi in(22)can in flooding scheme. be computed as APPENDIX A:THE PROOF OF THEOREM 1 rarccos(pi/p) 2 pp(p)d0dp In order to derive the per-node capacity,a contact graph is considered,in which the nodes are allocated at their home- points respectively.Moreover,an edge can be put between any =日 2 parccos(pi/p)p(p)dp two-nodes,whose weight is defined as the probability that they happen to be within distance e(1)of each other.Moreover, since this paper focuses on the fast mobility model,the node =0 2 Vo2-pip(e)de can only transmit one packet to any other node within distance e(1)of it.Due to the unit density of the network,the contact Vn graph can be treated as a virtual capacitated graph. = VPivp Pip(Pi)dp+ pp(p)dp Considering a cut dividing the contact graph into two parts with the same size,there are (n)nodes in each part in Θ(1) 0≤a≤2， average.The two parts are defined as O1 and 02,which 6(p-a) a>2. are illustrated in Fig.7.Furthermore,the length of the cut is (23) θ（√a).If the source and destination is within different parts, the packet must be transmitted through the cut.Therefore the Moreover,since the home-points in O1 are also uniformly distributed,the order of W in(21)can be computed as sum per-node throughput of these pairs is bounded by the sum weight of the edges across the cut.Since the number W=Wi of such kind of source-destination pairs is e(n),the per- iis in O1 node throughput upper-bound of the network can also be Vn derived from this bound according to the definition of per- Widpi node throughput. Jo (24) In order to derive the sum probability of the edges across the Θ(n) 0≤a≤2， cut,a node i belonging to is considered,and its distance 日(n2-)23
9 means (20) is satisfied, and therefore the multicast delay gain is Θ(1) in this network. Consequently, the achievable bounds of multicast delay gain are proved, which form a general framework of multicast delay gain. However, the multicast delay gain is not mainly determined by the mobility strength in order sense but by the difference of delay for different nodes in flooding scheme, i.e., the difference between Dm uni,i(n). VI. CONCLUSION This paper mainly focuses on the impact of mobility on multicast gain. The analysis of per-node capacity shows that mobility weakens the per-node capacity distinction between multicast and unicast. In particular, the per-node capacity for both unicast and multicast are derived, and two schemes based on restricted relay selection are proposed to achieve the per-node capacity. Afterwards, the multicast capacity gain is calculated, which is utilized to evaluate the distinction between the per-node capacity enhancements for unicast and multicast. Moreover, the essential role of mobility and m in multicast is analyzed. Additionally, the upper-bound and lower-bound of multicast capacity gain are also studied regardless of mobility model, which may guide the multicast study in the future. Three factors which determine the multicast capacity gain are listed in order to form a general framework of multicast capacity. Furthermore, the multicast delay gain is also investigated. The upper-bound and lower-bound of it are derived and proved to be achievable. Moreover, it can be found that the multicast delay gain is not mainly determined by the mobility strength in order sense but by the difference of delay for different nodes in flooding scheme. APPENDIX A: THE PROOF OF THEOREM 1 In order to derive the per-node capacity, a contact graph is considered, in which the nodes are allocated at their homepoints respectively. Moreover, an edge can be put between any two-nodes, whose weight is defined as the probability that they happen to be within distance Θ(1) of each other. Moreover, since this paper focuses on the fast mobility model, the node can only transmit one packet to any other node within distance Θ(1) of it. Due to the unit density of the network, the contact graph can be treated as a virtual capacitated graph. Considering a cut dividing the contact graph into two parts with the same size, there are Θ(n) nodes in each part in average. The two parts are defined as O1 and O2, which are illustrated in Fig. 7. Furthermore, the length of the cut is Θ(√ n). If the source and destination is within different parts, the packet must be transmitted through the cut. Therefore the sum per-node throughput of these pairs is bounded by the sum weight of the edges across the cut. Since the number of such kind of source-destination pairs is Θ(n), the pernode throughput upper-bound of the network can also be derived from this bound according to the definition of pernode throughput. In order to derive the sum probability of the edges across the cut, a node i belonging to O1 is considered, and its distance from the cut is ρi . Denoting the sum weight of the edges across '1 '2 The cut Fig. 7. The packet is transmitted across the cut the cut with endpoint i as Wi , the sum weight of the edges across the cut can be expressed as W = X i is in O1 Wi . (21) According to the probability that two nodes happen to be within distance Θ(1) in Eq. (11), the Wi can be further expressed as Wi = X j is in O2 p(ρ H i,j ). (22) Since the home-points in O2 are uniformly distributed and the size of the network is √ n × √ n, the order of Wi in (22) can be computed as Wi = Θ 2 Z √ n ρi Z arccos(ρi/ρ) 0 ρp(ρ)dθdρ! = Θ 2 Z √ n ρi ρ arccos(ρi/ρ)p(ρ)dρ! = Θ 2 Z √ n ρi q ρ 2 − ρ 2 i p(ρ)dρ! = Θ Z 2ρi ρi √ ρi √ ρ − ρip(ρi)dρ + Z √ n 2ρi ρp(ρ)dρ! = Θ (1) 0 ≤ α ≤ 2, Θ ρ 2−α i α > 2. (23) Moreover, since the home-points in O1 are also uniformly distributed, the order of W in (21) can be computed as W = X i is in O1 Wi = Θ √ n Z √ n 0 Widρi ! = Θ (n) 0 ≤ α ≤ 2, Θ n 2− α 2 2 3, (24)
10 where the poly-logarithmic factors are ignored for brevity Therefore,there are (n)active transmission pairs in each when a =3.Considering that there are e(n)source- time slot..Furthermore,.it takesθ（√m)hops to transmit one destination pairs,the per-node throughput of these pairs can packet from source to destination.Hence,the total throughput be limited by of the network is e(n/vn)=e(vn)and the per-node 日(1) 0≤a≤2， throughput).Thus,the upper-bound is achieved when 23. (25) Consequently,the upper-bound is achievable,which means a>3. that this per-node throughput upper-bound is the per-node According to the definition of per-node throughput (i.e.,Def- capacity of the unicast scenario. inition 1),(25)is also the per-node throughput bound of the network.Based on Definition 2,in order to prove that the per- APPENDIX B:THE PROOF OF LEMMA 1 node capacity of unicast scenario equals to(25),it is necessary to testify that the per-node throughput in(25)is achievable. Since each source randomly selects m destinations,the Thus,the Scheme I will be proved to be the capacity achieving probability that a given destination i is selected by the given scheme in the following part. source is m.Thus,defining the number of node i's sources as Firstly,if a e (e is the base of the natural logarithm),the probability that cim< =日 2(vn) d<cam satisfies (26 Pr{cim <d<cam} Θ(1) 0≤a<2, ( a=2, 1、 cim n! (30) 日n1-号) 2<a≤3. To calculate the per-node throughput of the network,we 三(-男 n! assume that M(i,t)packets are transmitted from source ito destination j at time slot t.The average delay of Denote g()()(1-i,therefore, the first hop is Pr-fi meets a relay}.Moreover,if t= (Prti meets a relay),there are (n)relays hold packets in 是-（兴）'(1-晋)n- n! g(i) the circle.Therefore,the destination will meet a relay g(i+1) with probability Prj meets a relay}=Prfi meets a relay}. +--(g)2+1(1-兴)n-i可 Moreover,since there are e(n)relays in the circle and 位+1)1-咒) (31) the number of source-destination pairs is e(n),the prob- (n-)咒 ability that one source-relay is selected to be active is s e(1)when they are in the same cell.Thus,when t m the source will send a packet to relay in According to (31),denoting I =c2m,the last item of (30) Prfi meets a relay}time slots,and the relay will receive a can be bounded as follow packet in Pr-j meets a relay}time slots.Hence,the long term per-node throughput for this source-destination pair is n! (m）=li巴inf7M6,)=e(Pr1 jmeets a relay)).( (n-) '-) (27) =c2m Consequently,the per-node throughput of the network for this 一9(T) scheme is 日(1) 0≤a<2 @e) T(n) 1 logn a=2 (28) ()'v (32) 日(n1-) 2<a≤3， which achieves the upper-bound of per-node throughput in(13) =6 ()， when0≤a≤3，and there is gap ofθ(logn)when a=2. For the case a 3,the scheme is different.From (12),it is obvious that each node will meet the node whose home- =o(()） point is p=e(1)from its home-point with probability (1). =O(g(I):
10 where the poly-logarithmic factors are ignored for brevity when α = 3. Considering that there are Θ(n) sourcedestination pairs, the per-node throughput of these pairs can be limited by Θ W n = Θ (1) 0 ≤ α ≤ 2, Θ n 1− α 2 2 3. (25) According to the definition of per-node throughput (i.e., Definition 1), (25) is also the per-node throughput bound of the network. Based on Definition 2, in order to prove that the pernode capacity of unicast scenario equals to (25), it is necessary to testify that the per-node throughput in (25) is achievable. Thus, the Scheme I will be proved to be the capacity achieving scheme in the following part. Firstly, if α ≤ 3, for the source i and its destination j, the probability that source meets a relay node whose home-point is in the circle O1 3 ρH i,j centered at C with radius 1 3 ρ H i,j is P r{i meets a relay} = Z Z O 1 3 ρH i,j p(ρ)dO = Θ p( √ n) Z Z O 1 3 ρH i,j dO = Θ (1) 0 ≤ α 3, the scheme is different. From (12), it is obvious that each node will meet the node whose homepoint is ρ = Θ(1) from its home-point with probability Θ(1). Therefore, there are Θ(n) active transmission pairs in each time slot. Furthermore, it takes Θ(√ n) hops to transmit one packet from source to destination. Hence, the total throughput of the network is Θ(n/√ n) = Θ(√ n) and the per-node throughput Θ( √ 1 n ). Thus, the upper-bound is achieved when α > 3. Consequently, the upper-bound is achievable, which means that this per-node throughput upper-bound is the per-node capacity of the unicast scenario. APPENDIX B: THE PROOF OF LEMMA 1 Since each source randomly selects m destinations, the probability that a given destination i is selected by the given source is m n . Thus, defining the number of node i’s sources as d, the probability that d = d0 can be expressed as Pr{d = d0} = n! (n − d0)!d0! m n d0 1 − m n m−d0 . (29) Therefore, for two constants 0 e (e is the base of the natural logarithm), the probability that c1m i + 1 m . (31) According to (31), denoting I = c2m, the last item of (30) can be bounded as follow Xn i=c2m n! (n − i)!i! m n i 1 − m n n−i < Xn i=I mi−I I! i! g(I) (a) = Θ Xn i=I mi−I I e I √ I i e i √ i g(I) ! = Θ Xn i=I I i i+ 1 2 e c2 i−I g(I) ! = O g(I) Xn i=I e c2 i−I ! = O(g(I)), (32)