Mobility Weakens the Distinction between Multicast and Unicast

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)<oo.(3)f(n) w(g(n))mean- node speed is given in [10].In this paper,the node speed s limn→g f(n)/g(n)=oo.(4)f(n)=(g(n))means limn 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 aggregat￾ed 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, Capac￾ity, Delay I. INTRODUCTION Network scaling laws for large-scale wireless ad hoc net￾works 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 t￾wo nonnegative function f(·) and g(·): (1) f(n) = o(g(n)) means limn→∞ f(n)/g(n) = 0. (2) f(n) = O(g(n)) mean￾s limn→∞ f(n)/g(n) < ∞. (3) f(n) = ω(g(n)) mean￾s limn→∞ f(n)/g(n) = ∞. (4) f(n) = Ω(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 proba￾bility 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 power￾law 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 per￾node throughput and delay by optimizing the configuration of their scheme. For example, when the exponent of the power￾law 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 mul￾ticast 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≤a<2,a=2,2<a≤3，a>3},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 power￾law 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 per￾node 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 mod￾el in two traffic patterns, i.e., unicast and multicas￾t. 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 sat￾isfies n Θ(1), Θ  log n log n m  , Θ ￾ m α 2 −1
, Θ (√ m) o for the cases {0 ≤ α < 2, α = 2, 2 < α ≤ 3, α > 3}, respective￾ly, where α is the exponential coefficient of restricted mobility model. These results demonstrate that mobility significantly decreases the multicast capacity gain. More￾over, the results also indicate that m enhances the dis￾tinction 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 lower￾bound 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. Accord￾ing 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, independent￾ly 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 home￾points 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≤a<2, the same packet to all of its destinations.The multicast session is defined as the transmission from the source to all of its f(p (2 a=2, (2) destinations(maybe through multi-hop). θ(s(p) a>2. 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 home￾point 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, Θ  s(ρ) log n  α = 2, Θ(s(ρ)) α > 2. (2) Although this mobility model is not accurate enough com￾paring 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 guaran￾tee 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 net￾work, 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 (multi￾unicast), 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 1<a<2. DLDT The delay for the case that data is only delivered by long distance transmission a=2 (12) a>2. 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 0<a 1.However, to the transmission time. for other cases,the probability becomes different.Based on Definition 5:(Multicast Delay Gain)For a given network, this mobility model,the per-node capacity of the network is the network delay of multicast is assumed to be Dmulti(n). derived in the following theorem. Moreover,if each node has m destinations,the sum delay Theorem I:The per-node capacity for unicast scenario of the transmissions from the source to them by unicast is under restricted mobility model is denoted as Dmuni(n).Comparing the delay of multicast and Θ(1) multi-unicast,the multicast delay gain is defined as 0≤a<2, Dm_uni(n） C(n)= 日1ogn 1 a=2, (13) (m）=Dmul( (9) 日(n1-号） 2<a≤3， 1 a>3. 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 prob￾ability 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 home￾point 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, Θ  ρ−2 log ρ log2 n  α = 2, Θ ￾ ρ −α
α > 2, (12) where ρ = p a 2 k + b 2 k is the distance between two home￾points. 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 ≤ α < 2, Θ  1 log n  α = 2, Θ ￾ n 1− α 2
2 < α ≤ 3, Θ  √ 1 n  α > 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 upper￾bound 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 home￾points 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 0<a<2. m the transmission range is large enough (e.g.r(n)=vn),the 1 0=2. delay could be e(1).However,it is not reasonable to assume C(n)= mlog高 日(nl-号m号 -2 2<a≤3， (14) the transmission range to be related with network scale n,and 1 a>3. 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 source￾destination 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 ≤ α < 2, Θ  1 m log n m  α = 2, Θ ￾ n 1− α 2 m α 2 −2
2 < α ≤ 3, Θ  √ 1 nm  α > 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 al￾lowed. Traditional 2-hop relay scheme without redun￾dancy [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 opti￾mal 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