1

Multicast Capacity in MANET with Infrastructure Support
Zhenzhi Qian, Xiaohua Tian, Xi Chen, Wentao Huang and Xinbing Wang Department of Electronic Engineering Shanghai Jiao Tong University, China Email: {199012315171, xtian, qfbzcx, yelohuang, xwang8}@sjtu.edu.cn

!

Abstract—We study the multicast capacity under a network model featuring both node’s mobility and infrastructure support. Combinations between mobility and infrastructure, as well as multicast transmission and infrastructure, have already been showed effective ways to increase it. In this work, we jointly consider the impact of the above three factors on network capacity. We assume that m static base stations and n mobile users are placed in an ad hoc network. A general mobility model is adopted, such that each user moves within a bounded distance from its home-point with an arbitrary pattern. In addition, each mobile node serves as a source of multicast transmission, which results in a total number of n multicast transmissions. We focus on the situations in which base stations actually benefit the capacity improvement, and find that multicast capacity in a mobile hybrid network falls into several regimes. For each regime, reachable upper and lower bounds are derived. Our work contains theoretical analysis of multicast capacity in hybrid networks and provides guidelines for the design of real hybrid system combing cellular and ad hoc networks. 1 Index Terms—Wireless ad hoc network; multicast capacity; mobility; infrastructure; hybrid network; scaling law;

that each moving node is located within a circle of radius 1/f (n) [3]. By mapping the network to a generalized random geometric graph, they have proven that Θ(1/f (n)) per-node capacity is achievable. Infrastructure in an ad hoc network provides a more straightforward increase to the capacity. In [4], Liu et al. claim that infrastructure can offer a linear capacity increase in a hybrid network, when the number√of base stations increases asymptotically faster than n. In addition, Kozat and Tassiulas [5] prove that if the number of users served by each BS is bounded above, a per-node capacity of Θ(1/ log n) can be achieved. In [6], Agarwal and Kumar further extend this result to Θ(1). Multicast transmission refers to the transmission from a single node to other k − 1 nodes, so as to generalize both unicast and broadcast transmissions. In [7], Li proves that multicast transmission can obtain a per-flow √ 1 1 capacity of Θ( n log n · √k ), which is larger than that of k unicast transmissions. The gain of multicast transmission results from a merge of relay paths within a minimum spanning tree. In [8], Li et al. extend the multicast transmission to a Gaussian channel model and show similar capacity improvement under the corresponding protocol. Many existing studies focus on the combinations of the above characteristics. Some aim to further increase the network performance, while others try to present a more realistic scenario. In [9] and [10], Li et al. explore the multicast capacity in a static hybrid network with infrastructure support. Establishing a multicast tree with the help of infrastructure and employing a hybrid routing scheme, they have showed that the achievable multicast [ capacity in a hybrid network with ]) m ( ( √ √ √ ) WB√ m Wc m Wa m Wa √ · a BSs is Θ max min n k , ns k , ns k , n k r . s s On the other hand, Huang, Wang et al. study the unicast capacity of mobile hybrid networks in [11], and jointly consider the influences of node’s mobility and infrastructure ( support on ]) A per-node capacity is it. ) [ 2 ( m c m 1 for strong mobility, and Θ f (n) + Θ min n , n

1

I NTRODUCTION

Recent years witness a rapid development in wireless ad hoc networks, in both academic and industrial fields. Kumar and Gupta have showed in their ground breaking work [1] that, even with the optimal scheduling, routing and relaying of packets, the per-node capacity still √ decreases as Θ(1/ n) when n approaches the infinity. Many studies try to improve this disappointing scalability of throughput capacity by introducing different characteristics into ad hoc networks, such as mobility of nodes, an infrastructure of the network: a multicast transmission scheme. Mobility in ad hoc networks was considered firstly by Tse et al. in [2]. A store-carry-forward relaying scheme was proposed and proven to sustain a Θ(1) per-node capacity, if each node can visit the whole network area with an uniformly ergodic mobility process. Garetto et al. generalize the mobility model through a restriction
1. The early version of this paper appears in the Proceedings of IEEE Inter-national Conference on Computer Communications(IEEE INFOCOM), 2012. [18]

2

( [ 2 ]) Θ min m c , m for weak and trivial mobility. n n In this paper, we further study the multicast capacity scaling laws of a mobile hybrid network characterizing both mobility and infrastructure. In our model, each of the n users moves around a home-point within a bounded radius. m wire-connected base stations are placed in a wireless ad hoc network, of which the area scales with n as f 2 (n). There are totally nc clusters with radius r = Θ(n−R ) and the number of destinations in the multicast scheme is assumed as k. A multicast path can be generated with an infrastructure routing and a pure ad hoc routing, as well as a combination of both. Intuitively, in our hybrid routing scheme, we hope to circumvent the bottleneck of backbone transmission or wireless access for cellular networks and take the advantage of them, thus the capacity can be improved. Our main contributions: In this paper, we consider the effects of mobility and infrastructure in multicast capacity of a wireless mobile ad hoc network. We divide mobility into three regimes, and present reachable upper bounds and lower bounds for each regime. We assume that bandwidth is W for wireless channel , and WB for wired connections. In cellular routing, we further divide wireless frequency resource W into uplink bandwidth WA and downlink bandwidth WC .
•

Furthermore, the per-node capacity by cellular routing is: [ ( )] mWA nc m2 WB mnc WC Θ min , , n (nc − 1)nk nk Considering the nature of serial connection, the pernode capacity by hybrid routing scheme is: [ ( √ )] W nc mWA nc m2 WB mnc WC √ , Θ min , , n (nc − 1)nk nk nR k The third regime (trivial mobility regime) corre√ sponds to f (n) γ (n) = ω(1). In this regime, we can ˜ prove that mobility is trivial and the network acts as a static one. Previous conclusions in static hybrid networks, such as [4], [9],and [10], can be applied in this trivial mobility regime. Different from previous studies on hybrid networks [4]- [6], [9], [10], our work takes node’s mobility into account. Besides, our work is the first one to consider the effect of a general mobility on multicast transmission. Furthermore, we study multicast capacity in a more realistic network model featuring both mobility and infrastructure support. As a result, our work generalizes both unicast and broadcast capacity results in MANETs and hybrid networks. Comparing to the conference paper, we add some proofs and remarks in this paper. It is worth noticing that these are significant for providing a better understanding of the difference between MS-MS link capacity and MSBS link capacity, optimal ad hoc routing in uniformly dense networks, the derivation of multicast capacity lower bound, etc. Also, these proofs and remarks offer useful insights in the related topic, such as why we divide mobility into three regimes, the reason why scheduling S* is optimal, which makes the theoretical analysis smoother and more rigorous. This paper is organized as follows. We first introduce our network models and assumptions in Section II. Section III and Section IV define the uniformly dense networks, and derive multicast capacity in such networks under ad hoc routing and cellular routing, respectively. In Section V, we combine the results of previous two sections and derive multicast capacity under hybrid routing scheme. Capacity analysis of non-uniformly dense networks is carried out in Section VI. We discuss the proposed multicast routing strategy and protocol designs in Section VII. At last, we conclude our work in Section VIII.
•

For the first regime (strong mobility regime) where √ n f (n) γ(n) = o(1), (γ(n) = log c c ), the per-node n capacity by ad hoc routing is: ( ) W Θ √ kf (n) And per-node capacity by cellular routing is: mWA m2 WB mWC Θ min , , n kn kn ( [ ])

By always choosing a better routing, the per-node capacity of hybrid routing scheme is: { [ ( )]} W mWA m2 WB mWC Θ max √ , min , , n kn kn kf (n)
•

The second regime (weak mobility regime) stand√ s for the situation that f (n) γ(n)√= ω(1) and √ √ (n/n f (n) γ (n) = o(1), where γ (n) = 1 logn/nc c ) . We ˜ ˜ r prove that, in this regime, mobility is only helpful in delivering intra-cluster message. The inter-cluster message can only be transmitted through cellular routing. As a result, the optimal routing scheme is a serial connection of ad hoc routing (phase 1) and cellular routing (phase 2). We prove that the result in the first regime can be mapped to phase 1 here. Consequently, the per-node capacity by ad hoc routing is: √ W nc √ ) Θ( nR k

2

M ODELS

AND

A SSUMPTIONS

We consider a wireless network consisted of n mobile users (also referred as mobile stations, MSs) moving over a bidimensional surface. Communications are carried out in wireless channels with bandwidth W by ad hoc routing, or by cellular routing with the help of m = Θ(nM ) base stations (BSs), which are connected to each other by optical fibers with bandwidth WB .

3

We use Xi (t) to denote the position of ith MS at any given time t, and Yi (t) for ith BS. Since BSs are statically placed in the network, we have ∀t, Yi (t) ≡ Yi (0) Yi . When referring to both MSs and BSs, we adopt Zi (t), 1 ≤ h i ≤ n + m to denote their locations. Xi is used to denote the location of home-point for ith MS. We further define operator ∥ · ∥ as the distance between two points: dij = ∥Zi − Zj ∥. 2.1 Mobility Model Definition 1: (Network Extension) O is a Torus, or a square with wrap-around conditions. The side length of the network scales with n according to a non-decreasing function f (n) = nα , where α ∈ [0, 1/2]. We normalize the whole network to a unit Torus for convenience. Correspondingly, any value representing a distance in the network should be scaled down by 1/f (n). Remark 1: α = 0 corresponds to the dense network [1], of which the size remains constant while node density increases linearly with n. And α = 1/2 represents the extended network [12], in which network size increase linearly with n while node density remains constant. It is worth pointing out that ignoring the edge effect of a network is reasonable for avoiding tedious derivations, and is adopted in previous studies [3], [11]. At the same time, normalization of the network area is commonly used for convenience [1], [2]. The above assumptions will not influence the main results in this paper. Definition 2: (Home-Point Cluster Model) We assume there are nc = Θ(nC ) clusters with radius r = Θ(n−R ). All the clusters are independently and uniformly distributed in network O. Then each of the n home-points is randomly assigned to a cluster and placed in it uniformly and independently. Definition 3: (MS Mobility) We assume that {Xi (t)} are independent, stationary, ergodic and rotationinvariant processes with stationary distribution ϕi (X): h ϕi (X) = ϕi (X − Xi ) = ∫ h s(∥X − Xi ∥) h s(∥X − Xi ∥)dX O

i.i.d. mobility models [12], hybrid random walk models [14] and Brownian motion models [15], by setting nC = n and f (n) = Θ(1). n Definition 4: (Mobility Regimes) Let γ(n) = log c c and n (n/nc ) 1 γ (n) = r2 log n/nc . We say that MS’s mobility is strong ˜ √ if f (n) γ(n) = o(1). Weak mobility corresponds to √ √ f (n) γ(n) = ω(1) and f (n) √ (n) = o(1), while trivial γ ˜ mobility corresponds to f (n) γ (n) = ω(1) ˜ Remark 4: With strong mobility, MSs can exist on cluster boundaries and meet those in other clusters. Under weak mobility, MSs only move within their own clusters, and mobility only helps in delivering intracluster message. In the case of trivial mobility, mobility provides little help in forwarding packets, and the whole network acts like a static one. Also, the mobility regime is an attribute of network, rather than that of MSs. The determinants of mobility regimes are growing speed of network size and clustering level of home-points. Instead of regularly BS placing method in [4], [9] and [10], the distribution of BSs in this paper matches that of MSs, so as to achieve better utilization of BSs. For jth BS, we randomly select a point Qj according to the cluster model, then uniformly and independently placed the BS in this cluster with distribution ϕ(Y − Qj ). In this paper, we focus on the case that clusters do not overlap with each other w.h.p., which is guaranteed by M < 2R. Also, we assume 0 ≤ R ≤ α, so that clusters will not shrink with increasing n. In order to ensure that every cluster is served by BSs w.h.p., i.e. m = ω(nc ). An example network under cluster and mobility models is showed in 1.1 in supplementary file. 2.2 Communication and Interference Models

(1)

,where s(d) is an arbitrary non-decreasing function with finite range. Remark 2: s(d) describes MS’s presence around its home-point before network normalization. Since ∫ h s(∥X − Xi ∥)dX ∼ 1/f 2 (n)
O

we have:

h ϕi (X) ∼ f 2 (n)s(∥X − Xi ∥)

Remark 3: Our mobility model is similar to that of [3] and [11]. In order to characterize the non-uniform distribution and limited motion observed in the real mobility (see [13], etc.), home-points and s(d) are introduced in our work. Such model can better demonstrate the preferential attachment phenomena in real networks. Furthermore, our mobility and cluster model can generalize other classical mobility models, such as

Base stations communicate with each other through optical fiber with bandwidth WB . This kind of communication will not cause interference to themselves or wireless communications. We assume that the available bandwidth in all the wireless channels is W . In ad hoc routing, transmissions fully occupy the wireless bandwidth W . In cellular routing, bandwidth is further divided into uplink bandwidth WA and downlink bandwidth WC . All the communications in wireless channels are characterized by Protocol Model, which is defined as followed. Definition 5: (Protocol Model) Both BSs and MSs adopt the same transmission range RT (correspondingly, same transmission power). At each time slot t, a wireless transmission from node i to node j is successful only if: 1) ∥Zi (t) − Zj (t)∥ ≤ RT and 2)For any other node l that transmits at t, ∥Zl (t) − Zj (t)∥ ≥ (1 + ∆)RT , where ∆ is a constant defining protection zone. We assume all of the n MSs are source nodes, each of which randomly selects other k MSs as destinations

4

and transmits the same data to them. The selection of destinations is well-designed, such that every MS is the destination of other k MSs. Correspondingly, We define the Feasible Throughput and Asymptotic Multicast Per-node Capacity λ similar to previous works, such as [1], [7], etc..

Definition 8: (Link Capacity) Link capacity between node i and j is defined by the maximal long term data flow between them: µS (i, j) = E[1(i,j)∈πS (t) |Hn+m ] ,where S is any given scheduling under protocol model, and π S (t) denotes the set of transmission pairs scheduled by S. 3.2 Upper Bound in Uniformly Dense Networks by Ad Hoc Routing By ad hoc routing, we mean that MSs only exchange information in wireless channel with a bandwidth W , ignoring the effect of BSs. Definition 9: (Scheduling Scheme S ∗ ) S ∗ schedules node i transmit to node j at time slot t according to the protocol model defined in definition 5 with the c transmission range RT = √T , which is warrant by [11]. n The next lemma is provided by [3]. It establishes a relationship between link capacity and encounter probability considering mobility. Lemma 3: In an uniformly dense network with bandwidth W , under scheduling S ∗ , the link capacity between two nodes (at least contain one MS) is: ( { }) ∗ cT µS (i, j) = Θ W · P r dij ≤ √ |Hn+m (3) n Corollary 1: The link capacities between MSs i,j and BS l are: f 2 (n) h h h h µ(Xi , Xj ) = Θ(W · η(f (n)∥Xi − Xj ∥)) (4) n f 2 (n) h h µ(Xi , Ylh ) = Θ(W · s(f (n)∥Ylh − Xi ∥)) (5) n Proof: Provided in 2.1 in supplementary file. It is easy to prove that scheduling S ∗ is optimal in √ order sense. On one hand, ∀RT = o(1/ n) can not fully guarantee connectivity and results in a performance √ decline. On the other, ∀RT = ω(1/ n) will cause too much interference and decrease the link capacity, as well.1 By mapping the network into a Generalized Random Geometric Graph G(n, nc , r, µ), we can calculate the asymptotic capacity more conveniently. In G(n, nc , r, µ), we use n vertices to represent the home-points. For each pair of vertices (i, j), we connect them with an edge h h of capacity µ(∥Xi − Xj ∥). The following proposition provides an upper bound of multicast capacity in the network. Proposition 1: Define that dh is the length of miniD imum spanning tree that covers source node i and the corresponding home-points of its k destinations. If throughput λ is sustainable, we have: ∑ ∑ dh ≤ µh dh (6) λ sD ij ij s ij

3 M ULTICAST C APACITY IN U NIFORMLY D ENSE N ETWORKS BY A D H OC R OUTING
In this section, we firstly provide a definition of an uniformly dense network, as well as some characteristics in such network. We show that when a network falls into strong mobility regime, it is equivalent to classify it as an uniformly dense network. Then reachable upper and lower bounds are presented in both pure ad hoc routing and cellular routing for uniformly dense networks. For pure ad hoc routing, we map the mobile network into a random geometric graph, and derive reachable capacity bounds. For cellular routing, we divide the routing scheme into three phases and achieve reachable upper and lower bounds in each phase, as well. 3.1 Preliminary for Uniformly Dense Networks Definition 6: (Local Density) The local density of nodes at any given point X0 is defined as: ρn (X0 ) = n ∑ i=1

E[1X (n) ∈B(X0 ,1/√n) |Hn+m ] i √ ,where B(X0 , 1/ n) is the disk centering at X0 with √ h radius 1/ n. Hn+m = {Zi }n+m defines the Boreli=1 field of home-points. E[·] stands for expectation, and 1x represents the indicator function. Definition 7: (Uniformly Dense Networks) We say a network is uniformly dense if for any X ∈ O, there exist two positive constant q and Q, such that q < ρn (X0 ) < Q h Lemma 1: Suppose that Zi are placed on O according to cluster model. Let A be any given regular tessellation of O, with area |A| ≥ (16 + δ)γ(n), for some small δ > 0. Let N (A) be the number of home-points of both BSs and MSs inside A. Then it holds w.h.p. :

n|A| ≤ inf N (A) ≤ sup N (A) ≤ 2n|A|. (2) 2 √ Lemma 2: If f (n) γ(n) = o(1) and m = O(n), where (n γ(n) = lognc c ) , then the network is uniformly dense. The proof of Lemma 1 and Lemma 2 are available in both [11] and [16]. √ Remark 5: f (n) γ(n) = o(1) indicates that nodes can move outside their the home-point clusters, and may move into other clusters. In this sense, mobility plays a fundamental role in exchanging information. Otherwise, nodes cannot exit their cluster and communicate with those in other clusters. Therefore, clustering becomes a obstacle of connectivity.

1. A formal proof for the optimality of scheduling S ∗ is presented in [11].

5

Proof: For any source-destination pair (s, d), traffic λ must pass through relay pathes connecting (s, d) in graph G(n, nc , r, µ). By the definition of minimum spanning tree and triangle inequality, all the relay pathes connecting source s and destinations D = {d1 , d2 , ...dk } should have a total length larger than dh . sD Fortunately, we have a classic conclusion on dh . sD Lemma 4: In a d-dimensional cube of side length a, Euclidian minimum spanning tree of n randomly and uniformly distributed nodes has an asymptotic length d−1 of τ (d)n d , where τ (d) only depends√ d. on Corollary 2: ∀i, 1 ≤ i ≤ n, dh = Θ( k). iD Theorem 1: The upper bound of per-node multicast capacity in uniformly dense networks by ad hoc routing is: ( ) W λ=O √ (7) kf (n) Proof: In the first step, we try to simplify equation (6) and derive an preliminary expression of upper bound ∑ ∑ Proposition 1. We introduce a sum: using T n (d) = − i j µn 1dh >d , which represents the opij ij posite summation of link capacities provided by links By the satisfying dh > d. ∑ ∑ definition, it is obvious that ij T (d + ∆) − T (d) = i j µn 1dD xdT n (x). The S n (d) should satisfy 1) supS n (d) = 0 and 2) T n (d) ≥ S n (d). And this results in: ∫ ∫ xdT n (x) ≤ xdS n (x) x>D x>D

By the definition of transmission range, we have: { } dh − RT ij h P r{dij (t) ≤ RT } ≤P r ∥Xi (t) − Xi ∥ > 2 { } dh − RT ij h + P r ∥Xj (t) − Xj ∥ > 2 ∫ ϕn (x)1 dh −RT dx =2 ij
O x>
2

Considering the definition of T (d), we have: ] ∑ [ T (d) ≥W · − E 1∥Xi (t)−X h ∥> d−RT i ∫

i

2

≥ − 2nW ·

ϕn (x)1
O x>

Applying this to Proposition 1 results in: ∫ ∑ h λ dsD ≤ xdT n (x) s dh −RT ij 2

dx = S(d)

For any constant M , it follows: ∫ xdT n (x) x>D (∫ ) ∫ −W d n ≤ √ 2ny · ϕ (∥X∥)ξ(∥X∥)dX dy dy n k y> fM X∈O (n) where ξ(∥X∥) = 1
∥X∥>
dh −RT ij 2

Combining with Corollary 2, we have: ( ) ∫ 1 √ λ=O xdT n (x) (8) n k ∫ In the second step, we calculate xdT n (x) to finish ∫ the proof. Let D = Θ(1/f (n)), we can divide xdT n (x) ∫ ∫ into x≤D xdT n (x) and x>D xdT n (x). ∫ On one hand, x≤D xdT n (x) is the summation of link capacities whose home-points are within distance Θ(1/f (n)). This part of integration sums up link capacities only when two nodes are close to each other. In other words, there exists a constant y0 , such that h h P r{dij ≤ RT (n)} > 0 only when ∥Xi − Xj ∥ ≤ fy0 . (n) Meanwhile, considering the limited bandwidth for each ∑ n node, it is obvious that µn = j µij ≤ W . Assume that i there is a simple curve L dividing O into A0 and B0 . The ∑ ∑ information flow crossing L is i∈A0 j∈B0 µn . Define ij C0 as the set of nodes that are within fy0 away of L. (n) Combining with premise that x ≤ D, we have: ∑ ∑ ∑ ∑ µn = µn ij ij i∈A0 j∈B0 i∈C0 j∈B0

We take M = 10

(which does not affect the result in order sense), and when n is large enough, for any y ≥ f10 , it is true that (n) y−RT > y . So that: 2 3 ∫ xdT n (x) x>D (∫ ) ∫ −W d ϕn (∥X∥)ξ(∥X∥)dX dy ≤ √ 2ny · dy n k y> f10 X∈O (n) ∫ ( y )] [ 2W ≈ √ y 2πyϕn dy 3 k y> f10 (n) ) ( ∫ ( y) 4πW W f 2 (n)y 2 ϕ f (n)( )dy = Θ √ < √ 3 k y kf (n) Finally, we have: ( ) ( ) ( ) W W W λ=O √ +O √ =O √ kf (n) kf (n) kf (n)

≤

∑

(

µn i

≤ W · N (C0 ) ≤ Θ

i∈C0

W ·n f (n)

)

6 √

3.3 Lower Bound in Uniformly Dense Networks by Ad Hoc Routing In the following part of this section, we will derive asymptotically reachable lower bound on multicast capacity in uniformly dense networks by ad hoc routing. We have already mapped a mobile network into a static graph, which makes the establishment of a multicast routing possible and realistic. We employ the next algorithm from [7] to set up the multicast routing in graph G(n, nc , r, µ). Algorithm 1 Optimal ad hoc routing for multicast transmission Ui = {si , di,1 , di,2 , . . . , di,k } 1. Divide O into squarelets, of which the side length is c/f (n). And we will have f 2 (n)/c2 such squarelets. We denote the squarelet in row i column j as (i, j). 2. We use the following scheme to generate the Euclidian Spanning Tree EST (Ui ) (1) Let the k + 1 nodes form k + 1 connected components; (2) repeat (3) and (4) for g = 1, 2, 3, . . . , k; (3) in the gth step, divide O into at most k − g square 1 cells, each with side length √k−g ; (4) choose a cell that contain two nodes from different connected components, then connect them using Manhattan routing and merge the corresponding components. 3. For each link uv in EST (Ui ), assume that u and v are located inside squarelets (iu , ju ) and (iv , jv ). In squarelet (iu , jv ) or (iv , ju ), choose a node w, so that uwv is the Manhattan routing connecting u and v. Repeat this for each link in EST (Ui ), and merge the corresponding link into Manhattan tree M T (Ui ). 4. For each link uw, find a node in each of the squarelets that are crossed by line uw . Obtain a path P (u, w) by connecting all of this nodes. Then delete those not in Ui and obtain the multicast tree M T R(Ui ). 5. Return M T R(Ui ). Lemma 5: By Algorithm 1, the probability that a random multicast flow will be routed through a certain √ squarelet A is at most c′ kc/f (n), where c′ is a constant. Proof: Provided in 2.2 in supplementary file. Theorem 2: With the M T R generated by Algorithm 1, the sustainable per-node multicast capacity by ad hoc 1 routing in dense networks is λ = Θ( √kf (n) ). Proof: In a random geometric graph G, the number of edges from squarelet A to squarelet B is N (A)N (B). If a per-node capacity λ is sustainable, each of these edges should not be overloaded. Considering the maximum of flows crossing one node defined by Lemma 5, we have: √ ( √ ) ′ cn λ c f (n) k kf 3 (n) =Θ λ· N (A)N (B) n √ n ≤ W · µ (dA,B ) = W · g(n)η( 5c)

√ where dA,B = f 3 (n)5ck/n . To sum up, the sustainable per-node multicast capacity in uniformly dense networks by ad hoc routing is: ( √ ) ) ( W · g(n)η( 5c) W √ λ=Θ =Θ √ kf 3 (n) kf (n) n

4 M ULTICAST C APACITY IN U NIFORMLY D ENSE N ETWORKS BY C ELLULAR R OUTING
In this section, we consider the impact of infrastructure in multicast capacity of a mobile network. Multicast flows will be routed through BSs. We divide the bandwidth in air channels into uplink bandwidth WA and downlink bandwidth WC . We further assume that the bandwidth of optical fibers connecting BSs is WB . Definition 10: (Cellular Routing RC ) Cellular routing C R consists of three phases. In the first phase, a multicast source node routes the packets to a BS. In the second phase, the packets are routed to the cells that contain destinations. In the last phase, BSs of these cells broadcast packets to the destinations. It is worth pointing out that such a routing cannot be established directly in mobile networks. However, with the help of the mapping scheme presented in the previous section, it is possible to generate a cellular multicast route in a random geometric graph. 4.1 Upper Bounds in Uniformly Dense Networks by Cellular Routing Since cellular routing RC is divided into three phases, the capacity of cellular routing RC is restricted by the worst case among three phases. We firstly explore the upper bound in each phase, then combine them together to obtain the overall upper bound. 4.1.1 Upper Bound in Phase 1 In phase 1, n MSs act as sources, and try to forward their messages to one of the BSs. Scheduling policy S ∗ is applied in this phase, and the uplink bandwidth for each BS is WA . Lemma 6: The upper bound of per-node capacity in uniformly dense networks with m BSs and n MSs, in phase 1 of cellular routing RC , is : ) ( mWA λp1 = O n Proof: Because of the limited antennas, a BS can serve at most Θ(1) MSs in each time slot. That means one BS can at most receive Θ(WA ) traffic in each time slot. By applying a simple TDMA or FDMA scheme, the maximum of total available uplink resource is Θ(WA · m). All the n MSs share this resource equally, which means that ) ( per-node capacity of each MS can not exceed Θ mWA . n

7

4.1.2 Upper Bound in Phase 2 In phase 2, BSs exchange messages received from MSs through optical fibers, each of which has a bandwidth of WB . We map the network only consisting BSs into a random geometric graph GB (m, WB ). m vertices are used to represent the BSs. The capacities of edges connecting each pair of BSs (i, j) are WB . The next proposition holds in such graph. Definition 11: (Inner and outer tessellation) Consider a torus, which is regularly divided into multiple squarelets. Assume that, in this torus, there is a subset Ψ bounded by a closed and convex boundary L. The inner tessellation of this torus, denoting as Ψ, contains squarelets strictly within Ψ. And the outer tessellation is a union of Ψ and all the squarelets crossed by boundary L, denoting as Ψ. Proposition 2: In a random geometric graph, traffic λ is sustainable only if, for any partition (S, D) of vertices, it holds: ∑∑ ∑∑ λ λsd ≤ µn ij s∈S d∈D i∈S j∈D

Theorem 3: The upper bound of per-node multicast capacity in uniformly dense networks by cellular routing RC is: ( [ ]) mWA m2 WB mWC O min , , n kn kn 4.2 Lower Bounds in Uniformly Dense Networks by cellular routing RC Similar to the derivation of upper bounds by cellular routing RC , we derive lower bounds of cellular routing RC in 3 phases, respectively. Then a combination of the lower bounds is presented. 4.2.1 Lower Bound in Phase 1 ) ( Lemma 9: A traffic rate Θ mWA is sustainable from n any MS to infrastructure system in phase 1 of cellular routing RC . Proof: Provided in 2.5 in supplementary file. 4.2.2 Lower Bound in Phase ( 2

Lemma 7: The upper bound of per-node capacity in uniformly dense networks with m BSs and n MSs, in phase 2 of cellular routing RC , is : ( 2 ) m WB λp2 = O kn Proof: Provided in 2.3 in supplementary file. 4.1.3 Upper Bound in Phase 3 In phase 3, each BS transmits messages in its own cell. Optimal scheduling policy S ∗ is applied in this phase again, and the downlink bandwidth for each BS is WC . We map the network consisting of m BSs and n MSs into a random geometric graph GC (m + n, WC ). m vertices are used to represent the BSs, and the other n are for MSs. Edges only exist from BSs to MSs, with capacity h µ(Yih , Xj ). There is no link among BSs, as well as MSs. Proposition 3: Given an arbitrary non-increasing function s(x) with finite support and X ∈ O, it holds: ∫ 1 s(f (n)∥Y − X∥)dY ∼ 2 f (n) Y ∈O Lemma 8: The upper bound of per-node capacity in uniformly dense networks with m BSs and n MSs, in phase 3 of cellular routing RC , is : ) ( mWC λp3 = O kn Proof: Provided in 2.4 in supplementary file. As previously described, cellular routing RC is a serial connection of the above 3 phases. According to its characteristic , the overall capacity can not exceed the capacity of any element in the serial connection. With Lemma 6-8, we have the following theorem.

) 2 W Lemma 10: A traffic rate Θ m kn B is sustainable between BSs in phase 2 of cellular routing RC . Proof: Provided in 2.6 in supplementary file. 4.2.3 Lower Bound in Phase 3

Let fi denote the number of multicast flows, each of which has as least one destination inside ith BS’s cell (or transmission range). We borrow the next lemma from [10] to facilitate our proof. Lemma 11: When > ) ns ( log max 32m k m log 52m , 16m log(2n) is satisfied, the variable k k s maxm fj is Θ( nmk ) w.h.p., where ns is the number of j source nodes. ) ( Lemma 12: A traffic rate Θ mWC is sustainable from kn one BS to MSs in phase 3 of cellular routing RC . Proof: Provided in 2.7 in supplementary file An overall lower bound of cellular routing RC can be obtained by combining the lower bounds in 3 phases. With Lemma 9,10,12, we can draw the following conclusion: Theorem 4: The lower bound of per-node multicast capacity in uniformly dense networks by cellular routing RC is: ]) ( [ mWA m2 WB mWC , , Θ min n kn kn

5 M ULTICAST C APACITY IN U NIFORMLY D ENSE N ETWORKS BY H YBRID R OUTING
At the beginning of this section, we analyze the upper bound of multicast capacity for arbitrary hybrid routing. Then reachable lower bound and corresponding routing scheme are presented. The hybrid routing utilizes both ad hoc routing and cellular routing, with the purpose of further improving the network capacity and system throughput.

8

5.1 Upper and Lower Bounds by Hybrid Routing Theorem 5: In uniformly dense networks, the upper bound of per-node multicast capacity by any hybrid routing is: { [ ( )]} W mWA m2 WB mWC √ O max , min , , n kn kn kf (n) Proof: Combining Theorem 1 and 3, it is obvious that, in uniformly dense networks, per-node multicast capacity λ is upper-bounded by: ) [ ( )] ( mWA m2 WB mWC W + O min , , λ=O √ n kn kn kf (n) By the limit theory, we can rewrite the above expression as: { [ ( )]} W mWA m2 WB mWC λ = O max √ , min , , n kn kn kf (n) Definition 12: (Hybrid Routing Scheme RH ) Hybrid Routing Scheme RH evaluates both pure ad hoc routing and cellular routing RC , and adaptively selects a better scheme, which provides larger throughput, to route the packets. Applying Theorem 2 and 4 together, the following theorem holds beyond doubt. Theorem 6: By hybrid routing RH , the sustainable pernode multicast throughput in uniformly dense networks is: { [ ( )]} W mWA m2 WB mWC Θ max √ , min , , n kn kn kf (n) Theorem 6 shows that our hybrid routing scheme RH is optimal in order sense. Moreover, it proves that the upper bound purposed by Theorem 5 is tight. 5.2 Discussion on Capacity Regimes Proposition 4: The optimal frequency allocation between WA and WC is: WA = W , k+1 WC = kW k+1

However, if we allocate W as WA = results: mW λU D = (k + 1)n

W k+1 , WC

=

kW k+1 ,

it

The multicast capacity in uniformly dense networks by hybrid routing can be represented by the following parameters: m = Θ(nM ), k = Θ(nK ), WB = Θ(W · nφ ) and f (n) = nα . If φ > −M , the bottleneck of cellular routing falls in the wireless access. Otherwise, the backbone transmission becomes the limitation. Graphical illustration of capacity regimes is provided in 1.2 in supplementary file.

6 M ULTICAST C APACITY D ENSE N ETWORKS

IN

N ON -U NIFORMLY

In the previous sections, we discuss the multicast capacity of mobile uniformly dense networks, where √ f (n) γ(n) = o(1). Now we will present the results in mobile non-uniformly dense networks. In non-uniformly dense networks without the support of BSs, a larger transmission range should be adopted to guarantee connectivity. In [3], it is proved that this √ transmission range should be ( T = Ω(1/ n), which R ) nc only provides a capacity of Θ n2 log nc . The poor capacity is a consequence of more interferences brought by larger transmission range. Considering this, we propose to decrease the transmission range of nodes, and employ BSs to guarantee connectivity. A useful lemma is cited from [11], so as to facilitate our proof. Lemma 13: Nodes with transmission range RT = √ r nc will cause no interference to those in other clusn ters, with high probability. According to the new transmission range, we propose a new scheduling scheme. Definition 13: (Scheduling Scheme S) S schedules node i transmit to node j at time slot t, the transmission subjects to the restriction in definition 5 with the trans√ mission range RT = cT r nc . n 6.1 Multicast Capacity in Weak Mobility Regime

Proof: The optimal frequency allocation focuses on maximizing the uplink and downlink capacity between MSs and BSs. According to Theorem 6, the capacity λU D that can be provided by uplink and downlink )] [ ( transmissions is λU D = Θ min mWA , mWC . n kn If mWA > mWC , we have n kn λU D = If mWA n

mW mWC < kn (k + 1)n

<

mWC kn ,

we have mWA mW < n (k + 1)n

λU D =

Under scheduling scheme S, MSs in different clusters cannot communicate with each other directly in air channels. A hybrid routing is proposed to finish the transmission. Definition 14: (Hybrid Routing Scheme R) Hybrid Routing Scheme R consists of 2 phases. In phase 1, each source node transmits packets to destinations in its own cluster. In phase 2, each source node employs cellular routing (as defined in Definition 10) to transmit packets to destinations in other clusters. An example of hybrid routing scheme S in weak mobility regime is illustrated in 1.3 in supplementary file.

9

6.1.1 Multicast Capacity in Phase 1 of R Since there is no inter-cluster interference in phase 1, each cluster acts like a sub-network independently. Next, we will prove that these sub-networks are uniformly dense in weak mobility regime, and extend the results in uniformly dense networks into this phase. Theorem 7: In weak mobility regime, each cluster forms an independent sub-network, which is uniformly dense. Proof: By Lemma 13, it is obvious that ad hoc transmissions within one cluster are independent of those in other clusters, since the transmission range is less than the interference range. It is crucial to determine the key parameters ˜ (f (n), n, m, k, nc , RT ) of an arbitrary sub-network, if we ˜ ˜ ˜ ˜ ˜ want to prove it to be uniformly dense. A direct application of Chernoff bound results in the following expressions. For ∀ε > 0, these hold w.h.p.: (1 − ε)n nc (1 − ε)m nc (1 − ε)k nc