Multicast Capacity with Max-Min Fairness for Heterogeneous Networks

Multicast Capacity with Max-Min Fairness for Heterogeneous Networks Yixuan Li,Qiuyu Peng,Xinbing Wang Department of Electronic Engineering Shanghai Jiao Tong University,China Email:[lyx1990116,pqy,xwang8}@sjtu.edu.cn Abstract-In this paper,we investigate the multicast capacity Routing scheme.Their results generalize both unicast and for static ad hoc networks with heterogeneous clusters.We study broadcast [5]capacity.In [6].Shakkottai,et al.studied a the effect of heterogeneous cluster traffic (HCT)on the achievable different multicast framework where there are n multicast capacity.HCT means cluster clients are more likely to appear near the cluster head,instead of being uniformly distributed sources and nl-destinations per flow.Their network can across the network.Such property is commonly found in real support a rate of for each flow.Later on,the networks.By adopting max-min fairness,the minimum among multicast capacity under Gaussian channel is obtained in [7]. all individual multicast capacities of clusters can be maximized. [8].The achievable capacity in mobile multicast(motioncast) Since this minimal individual multicast capacity will not be is explored in [9]and optimal mobile multicast capacity is maximized unlimitedly,our work focuses on deriving the upper bound of the minimum individual multicast capacity(we refer it presented in [10],which is a generalization of [11],[12].And as minimum capacity for simplicity)in HCT,which provides the in [13],[14],MIMO cooperations are introduced to improve best performance for the minimum multicast capacity to attain multicast capacity. in the whole network.We find that HCT increases minimum Since nodes in the same multicast session can be treated as capacity for ad hoc networks.Further,the multicast capacity members of a cluster,multicast networks can also be viewed achieving scheme is provided to justify the derived asymptotic upper bound for the minimum capacity.Our work can generalize as clustered networks.However,there are few works con- various results obtained under non-heterogeneous networks in cerning the cluster behavior of multicast networks.Uniformly previous literature. distributed cluster (muticast session)traffic is assumed and Index Terms-Static Clustered Network,Multicast Capacity, cluster heterogeneities are rarely involved in previous works. Heterogeneous Cluster. Actually,most real networks are characterized by various clustered heterogeneities and some aspects have already been investigated in unicast networks,which includes: I.INTRODUCTION Spatial heterogeneity:Wireless nodes are not likely to be A wireless network is modeled as a set of nodes that send uniformly distributed across the deployed region in realistic and receive messages over a common wireless channel.Since networks e.g.,wireless users may cluster in urban areas so the seminal work done by P.Gupta,P.R.Kumar [1],there there are less users in suburban areas.Since spontaneous is significant interest toward the asymptotic capacity of the grouping of the nodes around a few attraction points occurs network when the number of nodes n grows.The authors of commonly in wireless network,G.Alfano,et al.[15],[16] [1]prove that the per-node capacity!is e(W/n logn)in extended the capacity scaling to networks with inhomogeneous a static network.Later in [2],the capacity result is analyzed node density.In their work,nodes are generated according to under more general fading channel condition and a similar a specified point process and they show that the bottleneck result is given.Then M.Franceschetti,et al.[3]design an is in the node sparse region because the network capacity is optimal routing protocol with capacity achieving e(W/vn)related to the minimum node intensity. via percolation theory. Pattern heterogeneity:It is likely that there exists more than The multicast network,which generalizes the above unicast one type of traffic pattern in the network and nodes of the network,received more attention recently and the estimation same traffic pattern constitute a cluster.In [17],Wang,et al. of the achievable multicast capacity is required in many studied a unified modeling framework composed of unicast, applications like sensor networks and TV streaming [25]. multicast,broadcast traffic.Later in [18].Ji,et al.explored Li,et al.[4]studied the achievable capacity in multicast networks composed of both unicast and converge-cast traffic networks.In their work,there are n multicast sessions,each and show that MIMO cooperation can be applied to increase comprised of 1 source and k destinations and they find that the capacity for both types of traffic.Li,et al.[19]dealt with capacity scales as e(1/vkn log n)based on the Manhattan networks containing some helping nodes for packet delivery. Using this method,the normal nodes and helping nodes can IGiven two functions f(n)>0 and g(n)>0:f(n)= be viewed as two clusters. o(g(n))means limn f(n)/g(n)=0:f(n)=O(g(n))mean- The primary incentive motivates us to investigate clustered s limn-→sup f(n)/g(n）≤oo;、f(n）=w(g(n),is equivalent to g(n)=o(f(n)):f(n)=2(g(n))is equivalent to g(n)=O(f(n)); networks is because of its practical use in real life.For f(n)=e(g(n))means f(n)=O(g(n))and g(n)=O(f(n)). instance,in military battlefield,commanders from different

1 Multicast Capacity with Max-Min Fairness for Heterogeneous Networks Yixuan Li, Qiuyu Peng, Xinbing Wang Department of Electronic Engineering Shanghai Jiao Tong University, China Email: {lyx1990116, pqy, xwang8}@sjtu.edu.cn Abstract—In this paper, we investigate the multicast capacity for static ad hoc networks with heterogeneous clusters. We study the effect of heterogeneous cluster traffic (HCT) on the achievable capacity. HCT means cluster clients are more likely to appear near the cluster head, instead of being uniformly distributed across the network. Such property is commonly found in real networks. By adopting max-min fairness, the minimum among all individual multicast capacities of clusters can be maximized. Since this minimal individual multicast capacity will not be maximized unlimitedly, our work focuses on deriving the upper bound of the minimum individual multicast capacity (we refer it as minimum capacity for simplicity) in HCT, which provides the best performance for the minimum multicast capacity to attain in the whole network. We find that HCT increases minimum capacity for ad hoc networks. Further, the multicast capacity achieving scheme is provided to justify the derived asymptotic upper bound for the minimum capacity. Our work can generalize various results obtained under non-heterogeneous networks in previous literature. Index Terms—Static Clustered Network, Multicast Capacity, Heterogeneous Cluster. I. INTRODUCTION A wireless network is modeled as a set of nodes that send and receive messages over a common wireless channel. Since the seminal work done by P. Gupta, P. R. Kumar [1], there is significant interest toward the asymptotic capacity of the network when the number of nodes n grows. The authors of [1] prove that the per-node capacity1 is Θ(W/√ n log n) in a static network. Later in [2], the capacity result is analyzed under more general fading channel condition and a similar result is given. Then M. Franceschetti, et al. [3] design an optimal routing protocol with capacity achieving Θ(W/√ n) via percolation theory. The multicast network, which generalizes the above unicast network, received more attention recently and the estimation of the achievable multicast capacity is required in many applications like sensor networks and TV streaming [25]. Li, et al. [4] studied the achievable capacity in multicast networks. In their work, there are n multicast sessions, each comprised of 1 source and k destinations and they find that the capacity scales as Θ(1/ √ kn log n) based on the Manhattan 1Given two functions f(n) > 0 and g(n) > 0: f(n) = o(g(n)) means limn→∞ f(n)/g(n) = 0; f(n) = O(g(n)) mean￾s limn→∞ sup f(n)/g(n) < ∞; f(n) = ω(g(n)) is equivalent to g(n) = o(f(n)); f(n) = Ω(g(n)) is equivalent to g(n) = O(f(n)); f(n) = Θ(g(n)) means f(n) = O(g(n)) and g(n) = O(f(n)). Routing scheme. Their results generalize both unicast and broadcast [5] capacity. In [6], Shakkottai, et al. studied a different multicast framework where there are n ϵ multicast sources and n 1−ϵ destinations per flow. Their network can support a rate of Θ( √ 1 nϵ log n ) for each flow. Later on, the multicast capacity under Gaussian channel is obtained in [7], [8]. The achievable capacity in mobile multicast (motioncast) is explored in [9] and optimal mobile multicast capacity is presented in [10], which is a generalization of [11], [12]. And in [13], [14], MIMO cooperations are introduced to improve multicast capacity. Since nodes in the same multicast session can be treated as members of a cluster, multicast networks can also be viewed as clustered networks. However, there are few works con￾cerning the cluster behavior of multicast networks. Uniformly distributed cluster (muticast session) traffic is assumed and cluster heterogeneities are rarely involved in previous works. Actually, most real networks are characterized by various clustered heterogeneities and some aspects have already been investigated in unicast networks, which includes: Spatial heterogeneity: Wireless nodes are not likely to be uniformly distributed across the deployed region in realistic networks e.g., wireless users may cluster in urban areas so there are less users in suburban areas. Since spontaneous grouping of the nodes around a few attraction points occurs commonly in wireless network, G. Alfano, et al. [15], [16] extended the capacity scaling to networks with inhomogeneous node density. In their work, nodes are generated according to a specified point process and they show that the bottleneck is in the node sparse region because the network capacity is related to the minimum node intensity. Pattern heterogeneity: It is likely that there exists more than one type of traffic pattern in the network and nodes of the same traffic pattern constitute a cluster. In [17], Wang, et al. studied a unified modeling framework composed of unicast, multicast, broadcast traffic. Later in [18], Ji, et al. explored networks composed of both unicast and converge-cast traffic and show that MIMO cooperation can be applied to increase capacity for both types of traffic. Li, et al. [19] dealt with networks containing some helping nodes for packet delivery. Using this method, the normal nodes and helping nodes can be viewed as two clusters. The primary incentive motivates us to investigate clustered networks is because of its practical use in real life. For instance, in military battlefield, commanders from different

places must send requirements through a common wireless 1c channel to their respective soldiers around them.In sensor (4C 4 4© 4© networks,local schedulers also need to send packets to their (2c adjacent client sensors.In addition,the study of capacity (1c) performance in clustered networks under multicast traffic is 1H w2C） still not sufficient yet and that is another reason why we set the 1c) 2H model.Since clients of the same data flow are non-uniformly 1© (2c) distributed,the open question is: (2c) (2c) What are the impacts of heterogeneous traffic on multi- cast capacity in clustered networks? (3C 5c (5c) In this paper,nodes in each multicast session are comprised Fig.1:Demonstration of Network topology.Nodes in the same of a cluster and heterogeneous cluster traffic (HCT)is defined cluster are labeled with the same number.H and C represent by:clients of the same cluster (data flow)are likely to be head(source)and clients (destination),respectively. deployed around a cluster head specified by an inhomogeneous Poisson process (IPP).We describe this clustering behavior with a variable oo,which describes the extent of HCT. analysis and bounds the value of minimum capacity using ex- Our asymptotic analysis for multicast capacity is based on plicit formulations rather than iterative computing procedures. the max-min fairness,through which the minimum among all In other words,the seminar work [20]can help validate the individual multicast capacities of clusters can be maximized. max-min fairness for multicast traffic,our work then goes a The formal definition of max-min fairness will be provided in step further to provide a scalable analysis for the best capacity the next section.Typically,there are more than one criterion in performance that the minimum capacity can attain.We find evaluating the efficiency of a certain scheduling policy.Most that the minimum capacity increases in HCT because the total previous literature such as [4][15][16]aims at deriving the transmission length is shortened and we offer a quantitative bounds for total throughput.However,maximizing the total relationship between the minimum capacity and oo. throughput is sometimes not desirable because it may cause The rest of the paper is organized as follows.In section imbalance among individual multicast capacities of clusters II,we outline some preliminaries of the network and our and cannot avoid the abnormal minimum value of individual main results.In section III and IV,close forms of the upper multicast capacity.For example,consider a network of 100 bound for minimum capacity with distribution function and clusters,among which 99 clusters have equal rates of 100Mbps distribution variance are derived respectively.In section V, and one cluster has a rate of 1Mpbs.Such abnormal individual we provide a routing scheme for achieving the upper bound multicast rate of 1Mbps can be regarded as service outage of minimum capacity in uniform random cluster model.A comparing with other large rates,and should be improved discussion of the results is presented in section VI.Finally, if possible.By adopting max-min fairness,such rate gap we conclude this paper in section VII. among different clusters can be narrowed and potential ser- vice outages can be reduced.The relative unfair individual II.PRELIMINARIES AND MAIN RESULTS multicast capacity of IMbps caused by traffic congestion or unreasonable rate allocation can be enhanced to a higher value. A.Network Topology As we know,this minimal individual multicast capacity will We consider extended networks composed of ns=na not be maximized unlimitedly,so there must exist an upper (0 <a 1)clusters distributed over a 2-dimensional torus limit that the minimum capacity cannot exceed.Our paper, region of edge2L=nP(0≤B≤a/2).We specify being set upon the max-min metric,focuses on deriving the a homogeneous Poisson process (HPP)to generate cluster upper bound of the minimum multicast capacity.Investigating head vi,whose position is denoted by kj for cluster Ci(1< the minimum capacity is meaningful because it provides the j<ns).Then,vj generates its cluster members according to best performance for the minimum multicast capacity to attain an IPP whose intensity atξis given by Clo(k,ξ)，where in the whole network.Note that for the purpose of brevity, ICl<p nl-is the expected size of the cluster and we will use the notion "minimum capacity"to represent ()is the dispersion density function.In order to investigate the "minimum individual multicast capacity"throughout the the impact of HCT on minimum capacity,we will discuss in paper. detail here what further assumptions should be made for both Previously,researchers had established a framework for (and C;l.Because the dispersion density function() multicast rate allocation with max-min fairness in wired net- determines the client distribution of each multicast session, works [20][21].In [20],the authors not only justified the intuitively,HCT is mainly described by the characteristics max-min fairness for multicast traffic,but also gave efficient of ()In addition,HCS deals with the cardinality of each algorithms to compute the rate allocation vector based on the cluster,so it is strongly related to Cil (1<j<ns). metric.Nevertheless,providing algorithms is sometimes not a straightforward way of showing the capacity performance of 2A cluster dense regime is assumed,which means the distance between networks,although it does help in practical congestion control adjacent clusterstends towhennapproaches infinity.We will assume computing.Our work,instead,directly shows a quantitative =0(1)throughout the paper

2 places must send requirements through a common wireless channel to their respective soldiers around them. In sensor networks, local schedulers also need to send packets to their adjacent client sensors. In addition, the study of capacity performance in clustered networks under multicast traffic is still not sufficient yet and that is another reason why we set the model. Since clients of the same data flow are non-uniformly distributed, the open question is: • What are the impacts of heterogeneous traffic on multi￾cast capacity in clustered networks? In this paper, nodes in each multicast session are comprised of a cluster and heterogeneous cluster traffic (HCT) is defined by: clients of the same cluster (data flow) are likely to be deployed around a cluster head specified by an inhomogeneous Poisson process (IPP). We describe this clustering behavior with a variable σO, which describes the extent of HCT. Our asymptotic analysis for multicast capacity is based on the max-min fairness, through which the minimum among all individual multicast capacities of clusters can be maximized. The formal definition of max-min fairness will be provided in the next section. Typically, there are more than one criterion in evaluating the efficiency of a certain scheduling policy. Most previous literature such as [4] [15] [16] aims at deriving the bounds for total throughput. However, maximizing the total throughput is sometimes not desirable because it may cause imbalance among individual multicast capacities of clusters and cannot avoid the abnormal minimum value of individual multicast capacity. For example, consider a network of 100 clusters, among which 99 clusters have equal rates of 100Mbps and one cluster has a rate of 1Mpbs. Such abnormal individual multicast rate of 1Mbps can be regarded as service outage comparing with other large rates, and should be improved if possible. By adopting max-min fairness, such rate gap among different clusters can be narrowed and potential ser￾vice outages can be reduced. The relative unfair individual multicast capacity of 1Mbps caused by traffic congestion or unreasonable rate allocation can be enhanced to a higher value. As we know, this minimal individual multicast capacity will not be maximized unlimitedly, so there must exist an upper limit that the minimum capacity cannot exceed. Our paper, being set upon the max-min metric, focuses on deriving the upper bound of the minimum multicast capacity. Investigating the minimum capacity is meaningful because it provides the best performance for the minimum multicast capacity to attain in the whole network. Note that for the purpose of brevity, we will use the notion “minimum capacity” to represent the “minimum individual multicast capacity” throughout the paper. Previously, researchers had established a framework for multicast rate allocation with max-min fairness in wired net￾works [20] [21]. In [20], the authors not only justified the max-min fairness for multicast traffic, but also gave efficient algorithms to compute the rate allocation vector based on the metric. Nevertheless, providing algorithms is sometimes not a straightforward way of showing the capacity performance of networks, although it does help in practical congestion control computing. Our work, instead, directly shows a quantitative 4C 4H 4C 4C 4C 3H 3C 3C 3C 5H 5C 5C 5C 5C 2H 2C 2C 2C 2C 2C 1H 1C 1C 1C 1C 1C Fig. 1: Demonstration of Network topology. Nodes in the same cluster are labeled with the same number. H and C represent head (source) and clients (destination), respectively. analysis and bounds the value of minimum capacity using ex￾plicit formulations rather than iterative computing procedures. In other words, the seminar work [20] can help validate the max-min fairness for multicast traffic, our work then goes a step further to provide a scalable analysis for the best capacity performance that the minimum capacity can attain. We find that the minimum capacity increases in HCT because the total transmission length is shortened and we offer a quantitative relationship between the minimum capacity and σO. The rest of the paper is organized as follows. In section II, we outline some preliminaries of the network and our main results. In section III and IV, close forms of the upper bound for minimum capacity with distribution function and distribution variance are derived respectively. In section V, we provide a routing scheme for achieving the upper bound of minimum capacity in uniform random cluster model. A discussion of the results is presented in section VI. Finally, we conclude this paper in section VII. II. PRELIMINARIES AND MAIN RESULTS A. Network Topology We consider extended networks composed of ns = n α (0 ≤ α ≤ 1) clusters distributed over a 2-dimensional torus region O of edge2 L = n β (0 ≤ β ≤ α/2). We specify a homogeneous Poisson process (HPP) to generate cluster head vj , whose position is denoted by kj for cluster Cj (1 ≤ j ≤ ns). Then, vj generates its cluster members according to an IPP whose intensity at ξ is given by |Cj |ϕ(kj , ξ), where |Cj | ≤ p = n 1−α is the expected size of the cluster and ϕ(·) is the dispersion density function. In order to investigate the impact of HCT on minimum capacity, we will discuss in detail here what further assumptions should be made for both ϕ(·) and |Cj |. Because the dispersion density function ϕ(·) determines the client distribution of each multicast session, intuitively, HCT is mainly described by the characteristics of ϕ(·). In addition, HCS deals with the cardinality of each cluster, so it is strongly related to |Cj | (1 ≤ j ≤ ns). 2A cluster dense regime is assumed, which means the distance between adjacent clusters √L ns tends to 0 when n approaches infinity. We will assume √L ns = O(1) throughout the paper

First,we outline the properties of the dispersion density 1)a minta1:a2,...,ak-1;ak=a1. function ()as follows: 2)There are con (0<co 1)clusters in SC1.and the 1)(kj,)is invariant under both translation and rotation other(1-co)ns clusters are randomly allocated to SC; with respect to ki,therefore (j,)can be rewritten (2≤i≤). as (-and it is a non-increasing,non-negative, The second assumption indicates that the number of clusters bounded,and continuous function with respect to the with size e(p)is the same order as the total number of clus- Euclidean distance-E. ters.Although it is somewhat restrictive here,it is constructive 2)Integration (kj,)of over the whole torus O is equal when we design our capacity achieving scheme and allows us to1,∫o(k,)d=1. to gain important insight into the structure of the problem. The first property restricts the dispersion density function to Under the above assumptions.cluster clients are likely to be a regime that clients are more likely to distribute around the distributed near the cluster head and the cluster size conforms cluster head,that is to say there are more clients around the to a poisson distribution with rate C.In addition,there are cluster head and less clients in remote areas with respect to the e(ns/k)clusters in SCi for 2i<k applying the Chernoff cluster head.The second property can be derived by defining bound.In order to simplify our analysis,we take both Cil and a non-negative,non-increasing continuous function s(p)such n as the cluster size and n/k as the number of clusters in that ops(p)dp<and then normalizing it over the whole SC;for 2<i<k.Such simplification does not influence our area results in order sense.Figure 1 is an example of the network (k,)= s(-kjl) topology. Jo s(IS-kjl)ds Notice that (kj,)=e(s(k))in asymptotic analysis fterference Reglon if we neglect the factor fos(I-kjl)dc=e(1). Now we need to offer a quantitative value for a given disper- +△)R sion density function ()to depict its degree of heterogeneity, then we can analyze the relationship between the minimum R capacity and the degree of HCT.As we know,the expectation .Jy can describe the average value of a function and in this case, it corresponds to the average density distribution, R +AR Elo()=() 1 And variance can describe the fluctuation level of a function around its expectation.In this case,we define the variance of Fig.2:Demonstration of two successful transmissions. ()as distribution variance oo,which can be utilized to depict HCT. 6=()-E(e2d&=n2()c- 1 B.Transmission Protocol All wireless transceivers can communicate over a common We omit the term kj due to the wrap around property channel with limited bandwidth W.We adopt the protocol of a torus and it can liberate us from the border effect.In model for interference proposed in [1].In each time slot,a case of uniform traffic,(therefore oo=0 and sender i can successfully transmit at W bit/second to a desti- larger heterogeneity results in larger oo.Finally,we specify nation j when the Euclidean distance between any other active a special point process as uniform cluster random model transmitters and j is larger than (1+A)Rij,where Ri.j is the (UCRM)whose dispersion density function is as follows: Euclidean distance between i and j;A is a positive constant I|≤R independent of the position of i,j,k and it specifies a guard φ“()= zone for a successful transmission.Note that in broadcast 0 otherwise cases,the interference radius is defined as (1+A)times the where R=- is defined as cluster radius.It means length between the furthest nodes and the source.In this paper, we assume that the minimal transmission range is denoted by clients of each cluster are randomly and uniformly distributed r and we will prove that nearest neighbor transmission is also in a disk of radius R centered at its cluster head.We prove dominant.Figure 2 illustrates two concurrent transmissions. that this topology can achieve the largest value of the minimum capacity given a fixed oo in section IV. We classify these ns clusters into k super clusters (SC) C.Traffic Model based on their cluster size,in order to explain the effect of A multicast traffic pattern is assumed where each cluster cluster size.For each cluster CjE SCi(1<i<k),its size head generates data flows to their respective clients,e.g.in ICil=e(n-),where oi is an increasing sequence over i Figure 1.The one to many data flow in Cj can be modeled and the clusters in SC possess the largest size.In addition,as a multicast tree 7 spanning 1 head and Ci clients.In some further assumptions are shown below. [4],Euclidean minimal spanning tree(EMST)is employed to

3 First, we outline the properties of the dispersion density function ϕ(·) as follows: 1) ϕ(kj , ξ) is invariant under both translation and rotation with respect to kj , therefore ϕ(kj , ξ) can be rewritten as ϕ(|kj − ξ|) and it is a non-increasing, non-negative, bounded, and continuous function with respect to the Euclidean distance |kj − ξ|. 2) Integration ϕ(kj , ξ) of ξ over the whole torus O is equal to 1, ∫ O ϕ(kj , ξ)dξ = 1. The first property restricts the dispersion density function to a regime that clients are more likely to distribute around the cluster head, that is to say there are more clients around the cluster head and less clients in remote areas with respect to the cluster head. The second property can be derived by defining a non-negative, non-increasing continuous function s(ρ) such that ∫ ∞ 0 ρs(ρ)dρ < ∞ and then normalizing it over the whole area ϕ(kj , ξ) = s(|ξ − kj |) ∫ O s(|ζ − kj |)dζ . Notice that ϕ(kj , ξ) = Θ(s(|ξ − kj |)) in asymptotic analysis if we neglect the factor ∫ O s(|ζ − kj |)dζ = Θ(1). Now we need to offer a quantitative value for a given disper￾sion density function ϕ(·) to depict its degree of heterogeneity, then we can analyze the relationship between the minimum capacity and the degree of HCT. As we know, the expectation can describe the average value of a function and in this case, it corresponds to the average density distribution, E[ϕ(x)] = ∫ O ϕ(ξ) L2 dx = 1 L2 . And variance can describe the fluctuation level of a function around its expectation. In this case, we define the variance of ϕ(·) as distribution variance σO, which can be utilized to depict HCT. σ 2 O = ∫ O (ϕ(ξ) − E[ϕ(ξ)])2 dξ = ∫ O ϕ 2 (ξ)dξ − 1 L2 . We omit the term kj due to the wrap around property of a torus and it can liberate us from the border effect. In case of uniform traffic, ϕ(ξ) ≡ 1 L2 therefore σO = 0 and larger heterogeneity results in larger σO. Finally, we specify a special point process as uniform cluster random model (UCRM) whose dispersion density function is as follows: ϕ u (ξ) = { 1 πR2 |ξ| ≤ R 0 otherwise where R = √ L π(1+(LσO) 2) is defined as cluster radius. It means clients of each cluster are randomly and uniformly distributed in a disk of radius R centered at its cluster head. We prove that this topology can achieve the largest value of the minimum capacity given a fixed σO in section IV. We classify these ns clusters into k super clusters (SC) based on their cluster size, in order to explain the effect of cluster size. For each cluster Cj ∈ SCi (1 ≤ i ≤ k), its size |Cj | = Θ(n 1−αi ), where αi is an increasing sequence over i and the clusters in SC1 possess the largest size. In addition, some further assumptions are shown below. 1) α = min{α1, α2, . . . , αk−1, αk} = α1. 2) There are c0ns (0 < c0 < 1) clusters in SC1, and the other (1 − c0)ns clusters are randomly allocated to SCi (2 ≤ i ≤ k) . The second assumption indicates that the number of clusters with size Θ(p) is the same order as the total number of clus￾ters. Although it is somewhat restrictive here, it is constructive when we design our capacity achieving scheme and allows us to gain important insight into the structure of the problem. Under the above assumptions, cluster clients are likely to be distributed near the cluster head and the cluster size conforms to a poisson distribution with rate |Cj |. In addition, there are Θ(ns/k) clusters in SCi for 2 ≤ i ≤ k applying the Chernoff bound. In order to simplify our analysis, we take both |Cj | and n 1−αi as the cluster size and ns/k as the number of clusters in SCi for 2 ≤ i ≤ k. Such simplification does not influence our results in order sense. Figure 1 is an example of the network topology. k , (1 ) + ∆ Rk.l Interference Region l Rk,l, 1 Ri j , 2 Ri j , i 2 j 1 j 1 , (1 ) + ∆ Ri j 2 , (1 ) + ∆ Ri j Fig. 2: Demonstration of two successful transmissions. B. Transmission Protocol All wireless transceivers can communicate over a common channel with limited bandwidth W. We adopt the protocol model for interference proposed in [1]. In each time slot, a sender i can successfully transmit at W bit/second to a desti￾nation j when the Euclidean distance between any other active transmitters and j is larger than (1+∆)Ri,j , where Ri,j is the Euclidean distance between i and j; ∆ is a positive constant independent of the position of i, j, k and it specifies a guard zone for a successful transmission. Note that in broadcast cases, the interference radius is defined as (1 + ∆) times the length between the furthest nodes and the source. In this paper, we assume that the minimal transmission range is denoted by r and we will prove that nearest neighbor transmission is also dominant. Figure 2 illustrates two concurrent transmissions. C. Traffic Model A multicast traffic pattern is assumed where each cluster head generates data flows to their respective clients, e.g. in Figure 1. The one to many data flow in Cj can be modeled as a multicast tree Tj spanning 1 head and |Cj | clients. In [4], Euclidean minimal spanning tree (EMST) is employed to

bound the length of transmission for each multicast session find out how large can the minimum capacity attain at most. in non-clustered networks with uniform node distribution. The rest of the paper will focus on this A,i.e.,the minimum We employ new techniques to study heterogenous clustered capacity.Since the main purpose of our paper lies in deriving networks,which generalizes uniform cases.Let EMST(Cj) the upper limit for minimum capacity,we omit the detailed denote the EMST for C;and the definition is given below. proof of the max-min fairness properties to avoid redundancy. Definition of EMTS:Assume that cluster head vj generates its cluster members according to an E.Mathematical Notations IPP.The EMST for Ci in 2-dimensional space R2 connects points using lines such that the Throughout our paper,we denote he as the number of total Euclidean length of all the lines is minimized and any hops required for transmitting bit b to all clients in Cj. point can be reached from any other by following the lines. is the length of transmission of bit b in its hth(1≤h≤he,） Note that the communication between any SD pairs can also hop.h.6 is the number of nodes that can overhear a packet go through multiple relays from other clusters. during a transmission of bit b in its hth hop.D(,R)is the Since the network topology defined above is fundamentally circular region centered at with radius R.R is the radius of related to both the number of clusters ns and the network the influential region centered at the head.Nodes outside the physical extension L,we hope to find out how the minimum influential region cannot act as relays for that cluster.is capacity asymptotically scales.Now we give the definition of the total Euclidean length of a multicast tree 7i,which can be capacity. calculated by summing up the Euclidean length of all edges Definition of Asymptotic Capacity:Let入y(1≤j≤ns） belonging to the tree. denote the individual multicast capacity for cluster Cj.The multicast rate vector入g=(dl,2,,入na-l,入na)consists F Useful Known Results of the individual multicast capacity of all clusters,and it is Throughout the paper,the following two known result- also identified as network capacity.The minimum multicast s would be used for proving theorems.In particular,the capacity is defined as入=min{入1,2，，入na-l,入n.}, Chernoff bound is applied to bound the probability of sums which is the minimal achievable data rate in these clusters. Then A=e(f(n))is defined as the asymptotic minimum of independent variables and the Holder's inequality will be consulted for deriving the bound for minimum capacity. capacity if there exist constants c >c'>0,such that Lemma 2.1:Chernoff bound:Given a Poisson random lim Pr(A=cf(n)is achievable)0,the Chernoff n→ bound is given by lim Pr(=c'f(n)is achievable)=1. Let B,(t)denote the number of data units already generated in Pr(X>(1+6)n)Ai then there must exists some Given the dispersion density function ()the upper cluster j such that入y<入andj<入y bound of minimum capacity is given as follows: In [20],the authors justified the properties of max-min cWL fairness for multicast service in a wired network.In their 入≤min{W. model,the rate allocation for different multicast sessions Vn.Jo v(ξd was also denoted by a rate vector,in which an element where c is some constant represents the individual multicast capacity for one cluster. HCT increases the upper bound of minimum capacity A The properties can be adapted to the wireless networks since and a universal relationship between A and oo is obtained our mathematical model is almost the same as the single-rate as: multicast service model shown in [20].That is to say,max- min fairness can be applied in multicast traffic to enhance the minimum capacity.Based on this,our major concern is to ≤mm{om.o(o")}

4 bound the length of transmission for each multicast session in non-clustered networks with uniform node distribution. We employ new techniques to study heterogenous clustered networks, which generalizes uniform cases. Let EMST(Cj ) denote the EMST for Cj and the definition is given below. Definition of EMTS: Assume that cluster head vj generates its cluster members {v (1) j , v (2) j , . . . , v (|Cj |) j } according to an IPP. The EMST for Cj in 2-dimensional space R 2 connects points vj ∪ {v (1) j , v (2) j , . . . , v (|Cj |) j } using lines such that the total Euclidean length of all the lines is minimized and any point can be reached from any other by following the lines. Note that the communication between any SD pairs can also go through multiple relays from other clusters. Since the network topology defined above is fundamentally related to both the number of clusters ns and the network physical extension L, we hope to find out how the minimum capacity asymptotically scales. Now we give the definition of capacity. Definition of Asymptotic Capacity: Let λj (1 ≤ j ≤ ns) denote the individual multicast capacity for cluster Cj . The multicast rate vector λs = (λ1, λ2, . . . , λns−1, λns ) consists of the individual multicast capacity of all clusters, and it is also identified as network capacity. The minimum multicast capacity is defined as λ = min{λ1, λ2, . . . , λns−1, λns }, which is the minimal achievable data rate in these clusters. Then λ = Θ(f(n)) is defined as the asymptotic minimum capacity if there exist constants c > c′ > 0, such that limn→∞ Pr(λ = cf(n) is achievable) λi then there must exists some cluster j such that λj 0, the Chernoff bound is given by Pr(X > (1 + δ)η) < ( e δ (1 + δ) (1+δ) )η . (1) Lemma 2.2: Holder’s inequality ¨ : If S is a measurable subset of Rn with the Lebesgue measure, and f and g are measurable real- or complex-valued functions on S, then Holder inequality is ∫ S |f(ξ)g(ξ)|dξ ≤ ( ∫ S |f(ξ)| p dξ) 1 p ( ∫ S |g(ξ)| q dξ) 1 q , (2) where 1/p + 1/q = 1. G. Main Results Our main results are summarized as follows: • Given the dispersion density function ϕ(·), the upper bound of minimum capacity is given as follows: λ ≤ min { W, cW L √ ns ∫ O √ ϕ(ξ)dξ } , where c is some constant. • HCT increases the upper bound of minimum capacity λ and a universal relationship between λ and σO is obtained as: λ ≤ min { O(W), O ( max{1, LσO}W √ ns )}

III.UPPER BOUND TO MINIMUM CAPACITY D In this section,we will provide an upper bound of the minimum capacity,which is a crucial step for deriving the 10 10 10 relationship between the capacity and the distribution variance. First,we will prove several key results inherent to the static 3.( network with multicast traffic.There are some tradeoffs that must be tolerated among which are the number of hops,trans- mission range,limited radio resources.Therefore,a thorough comprehension of the implicit relationships among them is Fig.3:Demonstration of the two conditions for MTTL constructive for deriving the upper bound of the achievable capacity. It consumes radio resources to forward a bit b to relays bit b in each cluster C;.Since at most WT bits can be carried or destinations.The following lemma captures the tradeoffs in time T with bandwidth W,for area L2,the upper bound among number of hops,transmission range and limited radio of total transmission resource is WT.L2 WTL2.This resources. inequality cannot only be used in our heterogeneous case,but Lemma 3./:Constraint of Protocol model:Under the pro- tocol model,the following inequality must be held for any also in homogeneous case as well since it is derived regardless of node distribution.In static network.there is a minimal routing scheme when the simulation time T is sufficiently transmission range r to guarantee full network connectivity.In large. nyTh能 networks with uniform node distribution.It is proved that the transmission range r=(vlog n/n)is sufficient for network (3) connectivity w.h.p.in [1].Now we need to characterize a j=1b=1h=1 feasible transmission range r,below which the transmission Proof:When T is sufficiently large,the total number of is not possible in our framework.In other words,we want to bits communicated from the head to its clients in cluster Ci derive r such that the number of nodes in D(E,r)is nonzero is入iT.Assume two SD pairs Xi-→Xk and X;→Xi are all the time. active in the given time slot,then according to the transmission Lemma 3.2:Let N(r)represent the number of nodes with- protocol model. in the transmission range r when a node wants to transmit its x-X≥会0x-X1+X-XD。 Dackets,then N(r)=8(巴2)whenr=(高a) Proof:In our cluster dense regime,whenr=(). 1 whichsderivedin.Thus disks of radius会times the (r）≤2红∑ael≤2 based on Cheroff bound 2 transmission radius centered at the receiver can be viewed and Riemann sum (one can refer to Theorem 1 in [15]). as an "exclusion region"that rejects transmitters from other Similarly,.the lower bound of(r)is asN(r）≥o data flows.Such a property also holds for broadcast that the Then we come tor)case.Note that the node transmission range is defined as the furthest node that can receive the packets.Let be the transmission radius centered density is upper bounded by a HPP with ratethe at the receiver for the h-th hop of bit b,and S be the overlap probability that the number of nodes inside the disk exceeding no is area between the "exclusion region"of bit b's hth hop and the 00 deployed region O.Note that at least a quarter of the disk is within the given region(the extreme situation happens when Pr(W(r)>no)≤e-“ 》A≤+1 (no+1)！ the node is near the periphery of the region).Then ≥(4鉴)P=422 During the above derivation,we used the Lagrange form of the remainder term and 0 no)=0w.hp.Note that N(r)）≥1 Therefore,radio resources can be viewed as the limited is a prerequisite for any transmissions and we complete our bandwidth W times the simulation time T and the network proof. area L2,such that the following inequality is satisfied: Therefore we know a necessary condition for the trans- nyTh论 n2AyTh绝 mission range r is().Now we need to 16 characterize the total length for transmiting a bit j=1b=1h=1 j=1b=1h=1 In 4,they prove that nearest neighbor transmission can achieve optimal multicast capacity in uniform traffic distribu- The above inequality is a basic requirement for multihop tion.They obtain that the number of hops required is vkn transmission type and the cooperative MIMO as in [14]is for k destinations.The situation is complicated here since not considered here.For simplicity,we define the area of the traffic is not uniformly distributed across the network.Clients exclusion region consumed by one bit in a certain hop as a in the same multicast session are more clustered around the single unit of transmission resources.The left side sums up head and a larger transmission range can cover more clients all the transmission resources consumed by each hop of each in a cluster when the transmission happens near the cluster

5 III. UPPER BOUND TO MINIMUM CAPACITY In this section, we will provide an upper bound of the minimum capacity, which is a crucial step for deriving the relationship between the capacity and the distribution variance. First, we will prove several key results inherent to the static network with multicast traffic. There are some tradeoffs that must be tolerated among which are the number of hops, trans￾mission range, limited radio resources. Therefore, a thorough comprehension of the implicit relationships among them is constructive for deriving the upper bound of the achievable capacity. It consumes radio resources to forward a bit b to relays or destinations. The following lemma captures the tradeoffs among number of hops, transmission range and limited radio resources. Lemma 3.1: Constraint of Protocol model: Under the pro￾tocol model, the following inequality must be held for any routing scheme when the simulation time T is sufficiently large. ∑ns j=1 ∑ λjT b=1 h b∑Cj h=1 π 16 ∆2 (ℓ h b ) 2 ≤ W T L2 . (3) Proof: When T is sufficiently large, the total number of bits communicated from the head to its clients in cluster Cj is λjT. Assume two SD pairs Xi → Xk and Xj → Xl are active in the given time slot, then according to the transmission protocol model, |Xk − Xl | ≥ ∆ 2 (|Xi − Xk| + |Xj − Xl |), which is derived in [1]. Thus disks of radius ∆ 2 times the transmission radius centered at the receiver can be viewed as an “exclusion region” that rejects transmitters from other data flows. Such a property also holds for broadcast that the transmission range is defined as the furthest node that can receive the packets. Let ℓ h b be the transmission radius centered at the receiver for the h-th hop of bit b, and S h b be the overlap area between the “exclusion region” of bit b’s hth hop and the deployed region O. Note that at least a quarter of the disk is within the given region (the extreme situation happens when the node is near the periphery of the region). Then S h b ≥ π 4 ( ∆ℓ h b 2 ) 2 = π∆2 (ℓ h b ) 2 16 . Therefore, radio resources can be viewed as the limited bandwidth W times the simulation time T and the network area L 2 , such that the following inequality is satisfied: ∑ns j=1 ∑ λjT b=1 h b∑Cj h=1 π 16 ∆2 (ℓ h b ) 2 ≤ ∑ns j=1 ∑ λjT b=1 h b∑Cj h=1 S h b ≤ W T L2 . The above inequality is a basic requirement for multihop transmission type and the cooperative MIMO as in [14] is not considered here. For simplicity, we define the area of the exclusion region consumed by one bit in a certain hop as a single unit of transmission resources. The left side sums up all the transmission resources consumed by each hop of each S D D D 10 3 5 S D D R 10 10 7 3 8 Fig. 3: Demonstration of the two conditions for MTTL. bit b in each cluster Cj . Since at most W T bits can be carried in time T with bandwidth W, for area L 2 , the upper bound of total transmission resource is W T · L 2 = W T L2 . This inequality cannot only be used in our heterogeneous case, but also in homogeneous case as well since it is derived regardless of node distribution. In static network, there is a minimal transmission range r to guarantee full network connectivity. In networks with uniform node distribution. It is proved that the transmission range r = Ω(√ log n/n) is sufficient for network connectivity w.h.p. in [1]. Now we need to characterize a feasible transmission range r, below which the transmission is not possible in our framework. In other words, we want to derive r such that the number of nodes in D(ξ, r) is nonzero all the time. Lemma 3.2: Let N (r) represent the number of nodes with￾in the transmission range r when a node wants to transmit its packets, then N(r) = Θ( nspr2 L2 ) when r = Ω( √ L nsp ). Proof: In our cluster dense regime, when r = ω( √ 1 nsp/L ), N (r) ≤ 2π ∑ns j=1 |Cj |r 2 L2 ≤ 2πnspr2 L2 based on Chernoff bound and Riemann sum (one can refer to Theorem 1 in [15]). Similarly, the lower bound of N (r) is as N (r) ≥ c0πnspr2 2L2 . Then we come to r = Θ( √ L nsp ) case. Note that the node density is upper bounded by a HPP with rate µ = πr2nsp L2 , the probability that the number of nodes inside the disk exceeding n0 is Pr(N (r) > n0) ≤ e −µ ∑∞ i=n0+1 µ i i! ≤ e (θ−1)µµ n0+1 (n0 + 1)! . During the above derivation, we used the Lagrange form of the remainder term and 0 ≤ θ ≤ 1. Therefore when n0 = ω( nspr2 L2 ), Pr(N (r) > n0) = 0 w.h.p. Note that N (r) ≥ 1 is a prerequisite for any transmissions and we complete our proof. Therefore we know a necessary condition for the trans￾mission range r is ℓ h b ≥ r = Ω(√ L nsp ). Now we need to characterize the total length for transmitting a bit ∑ h b Cj h=1 ℓ h b . In [4], they prove that nearest neighbor transmission can achieve optimal multicast capacity in uniform traffic distribu￾tion. They obtain that the number of hops required is √ kn for k destinations. The situation is complicated here since traffic is not uniformly distributed across the network. Clients in the same multicast session are more clustered around the head and a larger transmission range can cover more clients in a cluster when the transmission happens near the cluster

head (source)than other places.Therefore,it is unknown p-Cj.lp->EMST(p-C;)according to the definition whether the many more destinations involved in a larger of EMST.After the thinning process following lemma 3.3,we transmission range can compensate for the sacrifice of radio specify two regions according to ()Let '(denote the resources.Unfortunately,the following analysis reveals that point intensity after Algorithm 1. nearest neighbor transmission is also optimal in HCT. Dense Region (S1.;)Nodes in this region are populous In [4],EMST is investigated in multicast traffic and it and we specify a radius can help us obtain the upper bound of minimum capacity 1 in non-heterogeneous networks.To obtain the results under heterogeneous cluster traffic,we first introduce the following =sup{p,p）≥p1C lemma.Theorem 1 in [24]as follows. for this circular region S1.j because ()is invariant Lemma 3.3:If f is the density of the probability function under rotations.After the thinning process,()> for picking points,then for large n and d1,the size of the on the basis of Chemof bound. EMST is approximately c(d)n f()dr,where c(d) Sparse Region (S2.j=O/S1.)Nodes in this region are is a constant depending only on the dimension d. relatively sparse such that there are at most a constant Our case corresponds to d=2 and such that number of nodes in D(ξ，p)ifξ∈S2,.After the thinning process,the node density is at least a constant fraction of IEMST(C训=6(VIC;l Va( the original density.Therefore ()>(()) Lemma 3.4:There exists a constant c2 0 such that EMST(p-Ci)can be lower bounded as Algorithm 1 Generation of p-simplified EMST from EMST. Input:Cj.) Output:P-Cj EMST(p-C)I≥2VICl + √(ξ)d 52 :Specify two point sets S←0，S'←-Cy. 2:Randomly label each node in S'with numbers Proof:The length of EMST is determined by the point 1,2,...,lCjl-1,Cjl. intensity according to lemma 3.3,thus there exists a constant c>0.such that 3:Choose nodes with the smallest label number in S'. 4:Add the chosen nodes to S and discard all the nodes within D(',p)in S',where is the position of the chosen node. EMST(P-cj)(E)de 5:Back to step 3 until no node is left in S',(p-Cj)S'. -( V®)+ It reveals that the length of the Euclidean minimum mul- ticast spanning tree constitutes two terms,the square root ≥c2WCl of the number of nodes vlCjl and fov()de.Note that we eliminate the constant c(d)for simplicity.Intuitively,the minimum length for connecting all the nodes is the minimum where c2 is also a constant.Note that our result holds even total transmission length (MTTL).For a given graph,MTTL when S1.j or S2.j is empty. ■ can be counted by summing all the irredundant transmission Now we come to the second question.The following lemma lengths with extra intermediate nodes and edges.Although tells us that EMST(p-C)is at most times larger than MTTL is superficially similar to the EMST problem,the length MTTL when relays are utilized,which is proved in [23]. of MTTL is far less than EMST for the following reasons. Lemma 3.5:Given k nodes U,any multicast tree spanning these k nodes (may be using some additional relay nodes) Larger transmission range can cover more than one node, will have an Euclidean length of at least oEMST(U),where but only the length of the longest SD pair is counted.For instance,if a node broadcast its message to all the other =V3/2 and |EMST(U)is the EMST spanning U. nodes in one time,the MTTL is at most L.Therefore Then we obtain the lower bound of MTTL for Cj as MTTL is related to the transmission range r. MTTL(C)≥ΘEMST(r-C). Nodes from other clusters can act as relays to help forward information.We must consider the impact of Based on the above inequality,we obtain a lower bound of relays on the MTTL. h形，as: Figure 3 illustrates two examples of the above two question- %,≥MTTL2≥9 EMST(-CD (4) s,respectively.In order to answer the first question (derive the T relationship between the transmission range r and MTTL),we Note that what we are interested in is the order sense of construct a new concept p-simplified cluster p-Cj.Algorithm the result,therefore we directly regard r as the transmission 1 illustrates how to generate p-Ci given Ci and the dispersion length.Now we will investigate the upper bound of minimum density function o(.). capacity A based on the previous analysis of the restrictions Let p-7 denote the multicast tree spanning p-Ci.The imposed by the network.The results obtained here are some length of each branch in p-T;is larger than p and all the fundamental limits that cannot be violated by any routing abandoned nodes are within a distance p from the nodes in protocols

6 head (source) than other places. Therefore, it is unknown whether the many more destinations involved in a larger transmission range can compensate for the sacrifice of radio resources. Unfortunately, the following analysis reveals that nearest neighbor transmission is also optimal in HCT. In [4], EMST is investigated in multicast traffic and it can help us obtain the upper bound of minimum capacity in non-heterogeneous networks. To obtain the results under heterogeneous cluster traffic, we first introduce the following lemma. Theorem 1 in [24] as follows. Lemma 3.3: If f is the density of the probability function for picking points, then for large n and d ̸= 1, the size of the EMST is approximately c(d)n d−1 d ∫ Rd f(x) d−1 d dx, where c(d) is a constant depending only on the dimension d. Our case corresponds to d = 2 and such that |EMST(Cj )| = Θ (√ |Cj | ∫ O √ ϕ(ξ)dξ) . Algorithm 1 Generation of ρ-simplified EMST from EMST. Input: Cj , ϕ(·) Output: ρ − Cj 1: Specify two point sets S ← ∅, S ′ ← Cj . 2: Randomly label each node in S ′ with numbers 1, 2, . . . , |Cj | − 1, |Cj |. 3: Choose nodes with the smallest label number in S ′ . 4: Add the chosen nodes to S and discard all the nodes within D(ξ ′ , ρ) in S ′ , where ξ ′ is the position of the chosen node. 5: Back to step 3 until no node is left in S ′ , (ρ − Cj ) ← S ′ . It reveals that the length of the Euclidean minimum mul￾ticast spanning tree constitutes two terms, the square root of the number of nodes √ |Cj | and ∫ O √ ϕ(ξ)dξ. Note that we eliminate the constant c(d) for simplicity. Intuitively, the minimum length for connecting all the nodes is the minimum total transmission length (MTTL). For a given graph, MTTL can be counted by summing all the irredundant transmission lengths with extra intermediate nodes and edges. Although MTTL is superficially similar to the EMST problem, the length of MTTL is far less than EMST for the following reasons. • Larger transmission range can cover more than one node, but only the length of the longest SD pair is counted. For instance, if a node broadcast its message to all the other nodes in one time, the MTTL is at most L. Therefore MTTL is related to the transmission range r. • Nodes from other clusters can act as relays to help forward information. We must consider the impact of relays on the MTTL. Figure 3 illustrates two examples of the above two question￾s, respectively. In order to answer the first question (derive the relationship between the transmission range r and MTTL), we construct a new concept ρ-simplified cluster ρ−Cj . Algorithm 1 illustrates how to generate ρ−Cj given Cj and the dispersion density function ϕ(·). Let ρ − Tj denote the multicast tree spanning ρ − Cj . The length of each branch in ρ − Tj is larger than ρ and all the abandoned nodes are within a distance ρ from the nodes in ρ−Cj . |ρ−Tj | ≥ |EMST(ρ−Cj )| according to the definition of EMST. After the thinning process following lemma 3.3, we specify two regions according to ϕ(·) . Let ϕ ′ (ξ) denote the point intensity after Algorithm 1. • Dense Region (S1,j ) Nodes in this region are populous and we specify a radius ρej = sup{ρj , ϕ(ρj ) ≥ 1 πρ2|Cj | } for this circular region S1,j because ϕ(·) is invariant under rotations. After the thinning process, ϕ ′ (ξ) ≥ Θ( 1 πρ2|Cj | ) on the basis of Chernoff bound. • Sparse Region (S2,j = O/S1,j ) Nodes in this region are relatively sparse such that there are at most a constant number of nodes in D(ξ, ρ) if ξ ∈ S2,j . After the thinning process, the node density is at least a constant fraction of the original density. Therefore ϕ ′ (ξ) ≥ Θ(ϕ(ξ)). Lemma 3.4: There exists a constant c2 > 0 such that |EMST(ρ − Cj )| can be lower bounded as |EMST(ρ − Cj )| ≥ c2 √ |Cj | (√ πρej 2 ρ + ∫ S2,j √ ϕ′(ξ)dξ) . Proof: The length of EMST is determined by the point intensity according to lemma 3.3, thus there exists a constant c ′ > 0, such that |EMST(ρ − Cj )| ≥ c ′ ∫ O √ |Cj |ϕ′(ξ)dξ = c ′ √ |Cj | (∫ S1,j √ ϕ′(ξ)dξ + ∫ S2,j √ ϕ′(ξ)dξ) ≥ c2 √ |Cj | ( √ πρej 2 ρ √ |Cj | + ∫ S2,j √ ϕ(ξ)dξ) , where c2 is also a constant. Note that our result holds even when S1,j or S2,j is empty. Now we come to the second question. The following lemma tells us that |EMST(ρ − Cj )| is at most √ 3 2 times larger than MTTL when relays are utilized, which is proved in [23]. Lemma 3.5: Given k nodes U, any multicast tree spanning these k nodes (may be using some additional relay nodes) will have an Euclidean length of at least ϱ|EMST(U)|, where ϱ = √ 3/2 and |EMST(U)| is the EMST spanning U. Then we obtain the lower bound of MTTL for Cj as MT T L(Cj ) ≥ Θ(|EMST(r − Cj )|). Based on the above inequality, we obtain a lower bound of h b Cj as: h b Cj ≥ MT T L(Cj ) r ≥ Θ(|EMST(r − Cj )|) r (4) Note that what we are interested in is the order sense of the result, therefore we directly regard r as the transmission length. Now we will investigate the upper bound of minimum capacity λ based on the previous analysis of the restrictions imposed by the network. The results obtained here are some fundamental limits that cannot be violated by any routing protocols

Theorem 3.1:Under the assumptions of the proposed wire-where less networks,the following tradeoffs must be satisfied by all scheduling policies. (,s)= EMST(r-Cj) √ nspWL (5) j=1 ov(Edξ Then by substituting Eqn.(7)into Eqn.(8),we can obtain wherej=O(W)and c is a constant. T Proof:Using the Cauchy-Schwartz inequality and ∑∑总 Eqn.(3),we have =1b=1 4V2WL2 λ，The △/cocsr((,S1) (9) According to the definition of minimum capacity, 入 16WTL ≤ π△2 (6) 空网i何 i=1b= =(∑VCl+∑VCD (10) Because r is the minimal transmission range in the network, CiESC1 Cj建SC1 the following inequality is satisfied. Recalling the previous assumption that the number of clusters in SCi with size e(p)is the same order with total cluster numbersna,we have∑√Ci=O(ns√p).Hence,there Ci∈SC1 and substitute it into inequality (6),we can obtain that exists a constant c6 such that n#入yT 16WTL2 ∑∑，≤A (7) VGI+∑VCD≥c6Amvn CESC1 CSc1 j=1b=1 On the other hand,we will get a lower bound on the left +λVnl-k(1-co)ng side of the above inequality.First we divide ns clusters into ≥c6 AnsVp (11) two sets S1,S2 as: Combine Eqn.(9)and Eqn.(10),we obtain 4v2WL2 S1={CiDense Region S1,i≠0}， S2={Cj Dense Region S1.i=0). λ≤△Vmc6nsVr(0.ST Based on Eqn.(4)and the fact that EMsr(c) Else if S1=0: VIC;l n入T ns AyT de)given in Lemma 3.3.we obtain that if S0,there exists a constant ca,c,c >0,such that i=1b=1 n。入yT T j=1b=1 入3T ≥ ∑∑EMST(r-C》 Ce316=1 λT Substitute Egn.(7)and Egn.(11)into(12),we obtain +∑∑EMST(r-C na入T C∈S2b=1 c6 AnsVp≤ ∑∑ CaT Jo vo(E)de台台 ((),S1) 4v2WL2 ≤△Vme4roVo)d& 4WL√2nsP ((),S) (13) △cVoc4Jo√p)k During the above derivation.is a necessary ψ(()，S), (8) condition to guarantee network connectivity,where c>0 is a constant.After comparing the results in the two cases,the

7 Theorem 3.1: Under the assumptions of the proposed wire￾less networks, the following tradeoffs must be satisfied by all scheduling policies. ∑ns j=1 λj √ |Cj | ≤ c √nspW L ∫ O √ ϕ(ξ)dξ , (5) where λj = O(W) and c is a constant. Proof: Using the Cauchy-Schwartz inequality and Eqn.(3), we have   ∑ns j=1 ∑ λjT b=1 h b∑Cj h=1 ℓ h b   2 ≤   ∑ns j=1 ∑ λjT b=1 h b∑Cj h=1 (ℓ h b ) 2     ∑ns j=1 ∑ λjT b=1 h b∑Cj h=1 1   ≤ 16W T L2 π∆2   ∑ns j=1 ∑ λjT b=1 h b Cj   (6) Because r is the minimal transmission range in the network, the following inequality is satisfied. h b Cj ≤ ∑ h b Cj h=1 ℓ h b r , and substitute it into inequality (6), we can obtain that ∑ns j=1 ∑ λjT b=1 h b Cj ≤ 16W T L2 π∆2r 2 . (7) On the other hand, we will get a lower bound on the left side of the above inequality. First we divide ns clusters into two sets S1, S2 as: S1 = {Cj |Dense Region S1,j ̸= ∅} , S2 = {Cj |Dense Region S1,j = ∅} . Based on Eqn. (4) and the fact that |EMST √ (Cj )| |Cj | = Θ (∫ O √ ϕ(ξ)dξ) given in Lemma 3.3, we obtain that if S1 ̸= ∅, there exists a constant c4, c′ 4 , c5 > 0, such that ∑ns j=1 ∑ λjT b=1 h b Cj ≥ c4 r ∑ns j=1 ∑ λjT b=1 |EMST(r − Cj )| ≥ c4 r   ∑ Cj∈S1 ∑ λjT b=1 |EMST(r − Cj )| + ∑ Cj∈S2 ∑ λjT b=1 |EMST(r − Cj )|   ≥ c4T r   ∑ Cj∈S1 λj √ |Cj |   ψ (ϕ(·), S1) + c ′ 4T r   ∑ Cj∈S2 λj √ |Cj |   ψ (ϕ(·), S1) ≥ c5T r   ∑ns j=1 λj √ |Cj |   ψ (ϕ(·), S1), (8) where ψ (ϕ(·), S1) = min Cj∈S1 { |EMST(r − Cj )| √ |Cj | } . Then by substituting Eqn. (7) into Eqn. (8), we can obtain ∑ns j=1 λj √ |Cj | ≤ r c5T ψ (ϕ(·), S1) ∑ns j=1 ∑ λjT b=1 h b Cj ≤ 4 √ 2W L2 ∆ √ c0c5rψ (ϕ(·), S1) . (9) According to the definition of minimum capacity, ∑ns j=1 λj √ |Cj | ≥ λ ∑ns j=1 √ |Cj | = λ( ∑ Cj∈SC1 √ |Cj | + ∑ Cj∈SC / 1 √ |Cj |) (10) Recalling the previous assumption that the number of clusters in SC1 with size Θ(p) is the same order with total cluster numbers ns, we have ∑ Cj∈SC1 √ |Cj | = Θ(ns √p). Hence, there exists a constant c6 such that λ( ∑ Cj∈SC1 √ |Cj | + ∑ Cj∈SC / 1 √ |Cj |) ≥ c6λns √ p + λ √ n1−αk (1 − c0)ns ≥ c6λns √ p. (11) Combine Eqn. (9) and Eqn. (10), we obtain λ ≤ 4 √ 2W L2 ∆ √ c0c5c6ns √prψ (ϕ(·), S1) . Else if S1 = ∅: ∑ns j=1 ∑ λjT b=1 h b Cj ≥ c4 r ∑ns j=1 ∑ λjT b=1 |EMST(r − Cj )| ≥ c4 r ∑ns j=1 ∑ λjT b=1 √ |Cj | ∫ O √ ϕ(ξ)dξ = c4T r ∫ O √ ϕ(ξ)dξ   ∑ns j=1 λj √ |Cj |   . (12) Substitute Eqn. (7) and Eqn.(11) into (12), we obtain c6λns √ p ≤ r c4T ∫ O √ ϕ(ξ)dξ ∑ns j=1 ∑ λjT b=1 h b Cj ≤ 4 √ 2W L2 ∆ √ c0c4r ∫ O √ ϕ(ξ)dξ ≤ 4W L√ 2nsp ∆c ′√ c0c4 ∫ O √ ϕ(ξ)dξ . (13) During the above derivation, r ≥ c ′ √ L nsp is a necessary condition to guarantee network connectivity, where c ′ > 0 is a constant. After comparing the results in the two cases, the

only thing required to do is to prove that there exists a constant Theorem 4.2:Define a real variable function T(())= c7>0 such that fg√o(ξ)d'.Then we can prove that“()can minimize L√nsp CrL2 (o())among all (with distribution variance oo. ≥r地(，s Proof:We will refer to Holder's inequality for the proof cJoVξ账 of this theorem as follows. Recalling Lemma 3.4,it is equivalent to prove Letand we can obtain that () np≤22+r V(ξ)d Jo 62()dE≤πR2 Therefore our minimization problem is transformed as fol- Note thatr≥dL/Vnsp and()≤8=o(1/L2)(See lows: Section III.B),and there exists a constant c7 that can meet the above inequality and c satisfies Eqn.(5). min r(()=V()d Theorem 3.2:The achievable minimum capacity A in our network is upper bounded as follows: s.t (ξ)d=1 cWL 入≤min (14) o2()d≤R肥 1 vmJo√ξd (l5l）≤(l52l)for all≥l2 Proof:Since we assume that the number of clusters with size e(p)is in the same order with total number of clusters We substitute f(ξ)=2/3（ξ），g()=中1/B(),p=3and g=3/2 into Egn.(2).Then we can obtain the following n.we have inequality in space O. 会y网i22gi=6avm 3/2 =1 v()d≥ o()d返 Combining with Theorem 3.1,the term p can be eliminated. (U62())3 ◆ ≥V示R. IV.UPPER BOUND OF MINIMUM CAPACITY WITH Note that (is a monotonously decreasing function and DISTRIBUTION VARIANCE CONSTRAINED the inequality will become an equation when In the previous section,we have completed our analysis of 元夜l≤R 1 the relationship between the upper bound of minimum capacity ()= 0 otherwise A and the dispersion density function ()However,we cannot tell what the impact is on the minimum capacity.Therefore which means that ou()can achieve the minimal value of a quantitative value oo is needed to describe the degree of r(() 日 heterogeneity of each dispersion density function ()There Recalling Theorem 3.2,we complete the proof of Theorem are two reasons for studying their relationship.First,we cannot 4.1.In this case,the node distribution conforms exactly to see whether heterogeneity increases or decreases minimum the proposed UCRM.In this model,cluster members are capacity A based on Eqn.(14).oo is a good indicator of the uniformly and randomly distributed in a disk of radius R degree of heterogeneity.Second,we can predict the achievable centered at the cluster head.In the next section,we will minimum capacity just by knowing the distribution variance. provide the capacity achieving scheme to approach this bound The exact point process is not needed using this model.This and verify the upper bound of minimum capacity is achievable is useful because it is often difficult to obtain the dispersion in order sense. density function. Recalling the definition of oo.there are various dispersion V.CAPACITY ACHIEVING SCHEME FOR UNIFORM density functions (satisfied given a fixed oo.Below we CLUSTER RANDOM MODEL will show how to find the point process that achieve the largest value of minimum capacity. We have already derived upper bound of minimum capacity when two types of heterogeneities are involved.In this section, Theorem 4.1:Given the distribution variance oo,the min- we will provide a capacity achieving scheme for UCRM based imum capacity A is bounded as follows: on percolation theory.We prove that the minimum capacity achieved by our scheme matches the asymptotic upper bounds 入≤min O(W).(1.Loow (15) when the number of sessions ns is large enough. We find that only when the length of the multicast spanning The respect dispersion function is identical to () tree l is on the same order with |EMST(Ci)l,the indi- According to Theorem 3.1,a smaller |EMST(Cj)results vidual multicast capacity can approach the theoretical upper in a larger capacity.Therefore we will derive the minimum bound in order sense.Intuitively,when the degree of HCT is EMST(Cj)|given a fixed ao. high enough,the nodes in each cluster are only overlapped

8 only thing required to do is to prove that there exists a constant c7 > 0 such that L √nsp c ′ ∫ O √ ϕ(ξ)dξ ≥ c7L 2 rψ (ϕ(·), S1) . Recalling Lemma 3.4, it is equivalent to prove c ′ c7 ∫ O √ ϕ(ξ) nsp/L2 dξ ≤ c2ρej 2 + r ∫ S2,j √ ϕ(ξ)dξ. Note that r ≥ c ′L/√nsp and ϕ(ξ) ≤ 2p pL2 = Θ(1/L2 ) (See Section III.B) , and there exists a constant c7 that can meet the above inequality and c satisfies Eqn. (5). Theorem 3.2: The achievable minimum capacity λ in our network is upper bounded as follows: λ ≤ min { W, cW L √ ns ∫ O √ ϕ(ξ)dξ } . (14) Proof: Since we assume that the number of clusters with size Θ(p) is in the same order with total number of clusters ns. we have ∑ns j=1 λj √ |Cj | ≥ λ ∑ns j=1 √ |Cj | = Θ(λns √ p). Combining with Theorem 3.1, the term √p can be eliminated. IV. UPPER BOUND OF MINIMUM CAPACITY WITH DISTRIBUTION VARIANCE CONSTRAINED In the previous section, we have completed our analysis of the relationship between the upper bound of minimum capacity λ and the dispersion density function ϕ(·). However, we cannot tell what the impact is on the minimum capacity. Therefore a quantitative value σO is needed to describe the degree of heterogeneity of each dispersion density function ϕ(·). There are two reasons for studying their relationship. First, we cannot see whether heterogeneity increases or decreases minimum capacity λ based on Eqn. (14). σO is a good indicator of the degree of heterogeneity. Second, we can predict the achievable minimum capacity just by knowing the distribution variance. The exact point process is not needed using this model. This is useful because it is often difficult to obtain the dispersion density function. Recalling the definition of σO, there are various dispersion density functions ϕ(·) satisfied given a fixed σO. Below we will show how to find the point process that achieve the largest value of minimum capacity. Theorem 4.1: Given the distribution variance σO, the min￾imum capacity λ is bounded as follows: λ ≤ min { O(W), O ( max{1, LσO}W √ ns )} . (15) The respect dispersion function is identical to ϕ u (ξ). According to Theorem 3.1, a smaller |EMST(Cj )| results in a larger capacity. Therefore we will derive the minimum |EMST(Cj )| given a fixed σO. Theorem 4.2: Define a real variable function Υ(ϕ(·)) = ∫ O √ ϕ(ξ)dξ. Then we can prove that ϕ u (·) can minimize Υ(ϕ(·)) among all ϕ(·) with distribution variance σO. Proof: We will refer to Holder’s inequality for the proof ¨ of this theorem as follows. Let σ 2 O = 1 πR2 − 1 L2 and we can obtain that ∫ O ϕ 2 (ξ)dξ ≤ 1 πR2 . Therefore our minimization problem is transformed as fol￾lows: min Υ(ϕ(·)) = ∫ O √ ϕ(ξ)dξ s.t. ∫ O ϕ(ξ)dξ = 1 ∫ O ϕ 2 (ξ)dξ ≤ 1 πR2 ϕ(|ξ1|) ≤ ϕ(|ξ2|) for all |ξ1| ≥ |ξ2| We substitute f(ξ) = ϕ 2/3 (ξ), g(ξ) = ϕ 1/3 (ξ), p = 3 and q = 3/2 into Eqn. (2). Then we can obtain the following inequality in space O. ∫ O √ ϕ(ξ)dξ ≥ ( ∫ O ϕ(ξ)dξ (∫ O ϕ2(ξ)dξ)1/3 )3/2 ≥ √ πR. Note that ϕ(·) is a monotonously decreasing function and the inequality will become an equation when ϕ(ξ) = { 1 πR2 |ξ| ≤ R 0 otherwise which means that ϕ u (·) can achieve the minimal value of Υ(ϕ(·)). Recalling Theorem 3.2, we complete the proof of Theorem 4.1. In this case, the node distribution conforms exactly to the proposed UCRM. In this model, cluster members are uniformly and randomly distributed in a disk of radius R centered at the cluster head. In the next section, we will provide the capacity achieving scheme to approach this bound and verify the upper bound of minimum capacity is achievable in order sense. V. CAPACITY ACHIEVING SCHEME FOR UNIFORM CLUSTER RANDOM MODEL We have already derived upper bound of minimum capacity when two types of heterogeneities are involved. In this section, we will provide a capacity achieving scheme for UCRM based on percolation theory. We prove that the minimum capacity achieved by our scheme matches the asymptotic upper bounds when the number of sessions ns is large enough. We find that only when the length of the multicast spanning tree |Tj | is on the same order with |EMST(Cj )|, the indi￾vidual multicast capacity can approach the theoretical upper bound in order sense. Intuitively, when the degree of HCT is high enough, the nodes in each cluster are only overlapped

9 Downlink >SD pair Proof:Let A(d,r1,r2)denote the overlapping area of two ☐：Percolation cell circles of radius r1,r2 with centers of distance d away,and Destination ◆：Representing Node C(r)denotes number of nodes within radius r.Note that the distribution of cluster clients is HPP within a circle of radius R,thus we can obtain ◆`Hgwa Pr(W(r)=k) =>Pr(N(r)=klC(r+R)=m)Pr(C(r+R)=m) m=0 R+T Uplink 3 e紧 m S i=1 Source (∑em:m4 CR+r e-u2 (u2)m 2x Jo k! m!()2da cR+r (e-h12) 2x Fig.4:Demonstration of routing protocol. (R+r)zd R+r = e (n) Jo k (Rr)dz. with a constant number of clusters,which corresponds to During the above derivation,we utilize the following notations o =()We denote such a case as trivial cluster to simplify our calculations: overlapping.On the contrary,when the degree of HCT is relatively low when o =O().We denote such a case as A(,R,r)p 41= TBt3,2=T中sand>h=k fully cluster overlapping.The network topology between these L2 two extreme cases is denoted by partial cluster overlapping. The capacity achieving scheme for uniform cases has been S={o,nl∑=k developed in [4]and we discuss the other two cases in this i=1 section. The overlapping area of two circles is smaller than the area of the small circle therefore A.When ao=('平) πr2x∈0，R+r） In this case,R=- (1+L2(0o)2) =O(六).There are at A,Rr)≤ 0 x∈[R+T,o) most a constant number of clusters inside D(ξ，R)forξ∈O and a simple TDMA scheme can achieve e(W)capacity for Then we substitute it into Pr(N(r)=k)and obtain each cluster. Pr(W()=)≤2e-(r2 k! B.When ao=O() In this case,R=- (()=(L).All the nodes Lemma 5.2:There exists a constant r such that if we parti- tion the square into cells with equal side length TL/nsp. are fully overlapped and we find that the achievable minimum the probability that at least one node resides in a cell is larger capacity is identical to the uniform case. than1-2exp(于). Proof:Each cell of edge lengthL/np contains a disk of radiussuch that the probability that at least one node T C.When ao=o(平) resides in a cell can be lower bounded as follows: In this case.R)w()and the traffic in each cluster is not so aggregated because oo is relatively smaller. DrW≥1)≥1-2ep-r0P)=1-2ep-T7 In [3],an information highway is proposed to approach the capacity upper bound for unicast non-clustered networks based ■ on percolation theory and we apply this concept to our routing Now we outline the definition of an information highway: scheme.Before we outline the definition of an information ChooseT large enough so that 1-2exp()>5/6 and we highway,some useful lemmas are provided. equally partition the square O into cells of edge TL/nsp. Lemma 5.1:Let N(r)denote the number of nodes within Thus there are cells and each cell in ith row a disk of radius r=e(L/nsp).Then if the cluster radius and jth column is denoted by sij.si.i is open if it contains at R=(L/vns),the following inequality is satisfied. least one node.A horizontal (vertical)cross path is defined as a set of open cells that cross O from left to right (top to bottom). PrW)=利≤2ep-r2n22少 The gray cell in Figure 4 is an example of percolation path, which represents a wireless backbone that is used to multihop

9 Uplink Downlink Highway Destination Source Destination Downlink : Percolation cell : Representing Node : SD pair Fig. 4: Demonstration of routing protocol. with a constant number of clusters, which corresponds to σO = Ω( √ns L ). We denote such a case as trivial cluster overlapping. On the contrary, when the degree of HCT is relatively low when σO = O( 1 L ). We denote such a case as fully cluster overlapping. The network topology between these two extreme cases is denoted by partial cluster overlapping. The capacity achieving scheme for uniform cases has been developed in [4] and we discuss the other two cases in this section. A. When σO = Ω( √ns L ) In this case, R = √ L π(1+L2(σO) 2) = O( √ L ns ). There are at most a constant number of clusters inside D(ξ, R) for ξ ∈ O and a simple TDMA scheme can achieve Θ(W) capacity for each cluster. B. When σO = O( 1 L ) In this case, R = √ L π(1+L2(σO) 2) = Ω(L). All the nodes are fully overlapped and we find that the achievable minimum capacity is identical to the uniform case. C. When σO = o( √ns L ) In this case, R = Θ( 1 σO ) = ω( √ L ns ) and the traffic in each cluster is not so aggregated because σO is relatively smaller. In [3], an information highway is proposed to approach the capacity upper bound for unicast non-clustered networks based on percolation theory and we apply this concept to our routing scheme. Before we outline the definition of an information highway, some useful lemmas are provided. Lemma 5.1: Let N (r) denote the number of nodes within a disk of radius r = Θ(L/√nsp). Then if the cluster radius R = Ω(L/√ ns), the following inequality is satisfied. Pr(N (r) = k) ≤ 2 exp(− πr2nsp L2 ) ( πr2nsp L2 ) k k! . Proof: Let A(d, r1, r2) denote the overlapping area of two circles of radius r1, r2 with centers of distance d away, and C(r) denotes number of nodes within radius r. Note that the distribution of cluster clients is HPP within a circle of radius R, thus we can obtain Pr(N (r) = k) = ∑ns m=0 Pr(N (r) = k|C(r + R) = m)Pr(C(r + R) = m) = ∑ns m=0 ( ∫ R+r 0 ∑ S ( ∏m i=1 (e −µ1 µ υi 1 υi ! )) 2x (R + r) 2 dx)e −µ2 µ m 2 m! = ∫ R+r 0 ( ∑ns m=0 e −mµ1 (mµ1) k k! e −µ2 (µ2) m m! ) 2x (R + r) 2 dx ≤ ∫ R+r 0 (e −µ1µ2 (µ1µ2) k k! ) 2x (R + r) 2 dx = ∫ R+r 0 e − A(x,R,r)nsp L2 ( A(x,R,r)nsp L2 ) k k! 2x (R + r) 2 dx. During the above derivation, we utilize the following notations to simplify our calculations: µ1 = A(x, R, r)p π(R + r) 2 , µ2 = π(R + r) 2ns L2 and ∑m i=1 υi = k S = {υ0, υ1 . . . υm| ∑m i=1 υi = k} The overlapping area of two circles is smaller than the area of the small circle therefore A(x, R, r) ≤ { πr2 x ∈ [0, R + r) 0 x ∈ [R + r,∞) Then we substitute it into Pr(N (r) = k) and obtain Pr(N (r) = k) ≤ 2e − πr2nsp L2 ( πr2nsp L2 ) k k! . Lemma 5.2: There exists a constant τ such that if we parti￾tion the square O into cells with equal side length τL/√nsp, the probability that at least one node resides in a cell is larger than 1 − 2 exp( πτ2 4 ). Proof: Each cell of edge length τL/√nsp contains a disk of radius τL 2 √nsp such that the probability that at least one node resides in a cell can be lower bounded as follows: Pr(N (r) ≥ 1) ≥ 1 − 2 exp(− πr2nsp L2 ) = 1 − 2 exp(− πτ 2 4 ). Now we outline the definition of an information highway: Choose τ large enough so that 1−2 exp(− πτ 2 4 ) > 5/6 and we equally partition the square O into cells of edge τL/√nsp. Thus there are ⌊ √nsp τ ⌋×⌊ √nsp τ ⌋ cells and each cell in ith row and jth column is denoted by si,j . si,j is open if it contains at least one node. A horizontal (vertical) cross path is defined as a set of open cells that cross O from left to right (top to bottom). The gray cell in Figure 4 is an example of percolation path, which represents a wireless backbone that is used to multihop

10 data across the network[3].According to Theorem 5 in [3],if Algorithm 2 Capacity Achieving Scheme for UCRM the probability that a cell contains at least I node is larger than 1:Access Point Mapping:Establish mappings Fh(X)and there are w.h.p.(np)disjoint paths crossing from left to F(X)for each node X.Horizontally divide the L xL right(top to bottom).A set containing these e(nap)horizontal square into slices of sizeL(o()c).Then and vertical paths are called information highways.Note that there are at least 6log(nsp)paths in each slice.Denote the cells composed of the highway are called percolated cells, each path in the slice as pathi(1 <i<6log(nsp)). and the nodes are called representing nodes.The following We further divide each slice into 6log(np)sub-slices of properties are proved in [3]via percolation theory. In each horizontal (vertical)rectangle of size3 L x size each.If nodeX is in theih sub-slice. Fh(X)denotes the percolated cell on pathi with the same (log(np)eL).there are at least 6log(n.p) ordinate.Mapping ofF(X)is the dual ofFh(X),and is horizontal (vertical)highway paths w.h.p.It indicates mapped by applying the above algorithm to vertical paths. there are e(nsp)disjoint crossing paths from left to 2:Medium Access in Highway:Each representing node can right and top to bottom,respectively.(Theorem 5) be active for a constant portion of time in a cell partitioned The length of each crossing path is bounded by e(L). network based on Lemma 6 in [11].Therefore there exists The distance between two adjacent horizontal (vertical) a spatial and temporal accessing policy such that each paths is at most O(L log(np)/vnp). representing node can deliver O(W)bits to its adjacent There exists a spatial and temporal scheme that can representing node as [3]. achieve e(W)throughput on the highway.It means 3: Routing Protocol:A multicast spanning tree 7i is con- that each cell composing the highway can be considered structed in Lemma 5.3.Each time slot is divided into 3 linked by optical wires to its neighbors with bandwidth mini-slot and corresponds to 3 phases as in Figure 4.For 日(W).(Theorem3) each branch in T linking nodes X1 and X2,the 3 phases The information highway is an infinitely large component are as follows: such that each node in the deployed region can connect to it within a hop of length O().Now we need to Uplink:X1 drains its data to Fh(X1). Highway:This phase corresponds to step 2 and uti- construct a multicast spanning tree 7 for Ci to route its lizes multihop transmission along the horizontal path packets. fromF(X1)to the intersection with the vertical path Lemma 5.3:The Prim's algorithm is utilized to construct in which F(X2)resides then forwards to F(X2). an Ti for cluster Ci and we prove that Til<6v2CiR. .Downlink:X2 downloads the data from F(X2). Proof:Prim's algorithm:Initially,each node is a separate part,then we iteratively find the shortest edge to compose a lager part until one part is left.Each member in C;is confined Lemma 5.4:In the uplink and downlink phase,a data rate in a disk of radius R.We utilize a square of edge 2R to cover the whole circle.At each ith(1<j<Cil)step,there are of (log(np))can be sustained for each transmission. Proof:According to Algorithm 2,for each node X, C+1-i parts remaining.We equally partition the square both()X and F(X)-X is upper bound- into LvICjl +1-i]2 cells with edge length 2R Vc+i-可and ed by og()It means that if we equally divide there exists at least one cell which contains more than 2 parts, which means the shortest edge connecting two parts in ith step the region into sub-squares of size 2 log(np) is at most 2√2R og(np)Xand(X)must reside in the same cell. L√C+1-j Therefore,the upper bound of is: The same is true for X and F(X).Then according to Lemma IC,I 6 in [11,each cell can be allocated a constant time to be T≤ 2v2R active within the mini-slot.According to Lemma 3.2,there 台L√C引+1-到 are at most 82log2(nsp)nodes in each cell,which means there are at most 8k2log2(nsp)SD pair.Thus,each SD pairs =2V2h can be allocated-log2()fraction of a time slot for transmission. Then we begin to analyze the second phase.Although the ≤6V2ClR highway can be virtually considered as a wired network with (16) bandwidth (W),each path must help relay data for many ◆ clusters.Therefore the allocated radio resources for a cluster Based on the above analysis,a capacity routing scheme is is limited.In the following part,we will study the maximum provided in Algorithm 2. number of clusters a percolated cell can serve. According to Algorithm 2,the average number of nodes a Lemma 5.5:Each percolated cell cannot relay data for percolated cell has to serve is The next lemma illustrates cluster with head at a distance of (R)away the minimum achievable data rate in the uplink and downlink from the cell,therefore R≤√2(R+2 log (nsp)L)】 phases. √np Proof:We refer to Figure 5 for the proof.Each path 3kand&is some ca红=o(log(m-pl高）andmkesconstrined within a strip of widtho,p）点p·Thus elog(nsp）√a-红an integer. D is upper bounded by (log(n)).Recalling that

10 data across the network[3]. According to Theorem 5 in [3], if the probability that a cell contains at least 1 node is larger than 5 6 , there are w.h.p. Θ(nsp) disjoint paths crossing from left to right (top to bottom). A set containing these Θ(nsp) horizontal and vertical paths are called information highways. Note that the cells composed of the highway are called percolated cells, and the nodes are called representing nodes. The following properties are proved in [3] via percolation theory. • In each horizontal (vertical) rectangle of size3 L × (κ log(nsp) √ L nsp − ϵL), there are at least δ log(nsp) horizontal (vertical) highway paths w.h.p. It indicates there are Θ(√nsp) disjoint crossing paths from left to right and top to bottom, respectively. (Theorem 5) • The length of each crossing path is bounded by Θ(L). • The distance between two adjacent horizontal (vertical) paths is at most O(Llog(nsp)/ √nsp). • There exists a spatial and temporal scheme that can achieve Θ(W) throughput on the highway. It means that each cell composing the highway can be considered linked by optical wires to its neighbors with bandwidth Θ(W). (Theorem 3) The information highway is an infinitely large component such that each node in the deployed region can connect to it within a hop of length O( L log(nsp) √nsp ). Now we need to construct a multicast spanning tree Tj for Cj to route its packets. Lemma 5.3: The Prim’s algorithm is utilized to construct an Tj for cluster Cj and we prove that |Tj | ≤ 6 √ 2|Cj |R. Proof: Prim’s algorithm: Initially, each node is a separate part, then we iteratively find the shortest edge to compose a lager part until one part is left. Each member in Cj is confined in a disk of radius R. We utilize a square of edge 2R to cover the whole circle. At each ith (1 ≤ j ≤ |Cj |) step, there are |Cj | + 1 − i parts remaining. We equally partition the square into ⌊ √ |Cj | + 1 − i⌋ 2 cells with edge length 2R ⌊ √ |Cj |+1−i⌋ , and there exists at least one cell which contains more than 2 parts, which means the shortest edge connecting two parts in ith step is at most 2 √ 2R ⌊ √ |Cj |+1−i⌋ . Therefore, the upper bound of |Tj | is: |Tj | ≤ ∑ |Cj | i=1 2 √ 2R ⌊ √ |Cj | + 1 − i⌋ = 2√ 2R   ⌊√ |Cj | ⌋ + ⌊√ |Cj | ⌋ ∑ i=1 1 i + |Cj | ⌊√ |Cj | ⌋ − 2   ≤ 6 √ 2|Cj |R. (16) Based on the above analysis, a capacity routing scheme is provided in Algorithm 2. According to Algorithm 2, the average number of nodes a percolated cell has to serve is κ δ . The next lemma illustrates the minimum achievable data rate in the uplink and downlink phases. 3κ and δ is some constant, ϵL = o(log(nsp) √L nsp ) and is to make κ log(nsp) √L nsp − ϵL an integer. Algorithm 2 Capacity Achieving Scheme for UCRM 1: Access Point Mapping: Establish mappings Fh(X) and Fv(X) for each node X. Horizontally divide the L × L square into slices of size L×(κ log(nsp) √ L nsp −ϵL). Then there are at least δ log(nsp) paths in each slice. Denote each path in the slice as pathi(1 ≤ i ≤ δ log(nsp)). We further divide each slice into δ log(nsp) sub-slices of size L × ( κL δ √nsp ) each. If node X is in the ith sub-slice, Fh(X) denotes the percolated cell on pathi with the same ordinate. Mapping of Fv(X) is the dual of Fh(X), and is mapped by applying the above algorithm to vertical paths. 2: Medium Access in Highway: Each representing node can be active for a constant portion of time in a cell partitioned network based on Lemma 6 in [11]. Therefore there exists a spatial and temporal accessing policy such that each representing node can deliver O(W) bits to its adjacent representing node as [3]. 3: Routing Protocol: A multicast spanning tree Tj is con￾structed in Lemma 5.3. Each time slot is divided into 3 mini-slot and corresponds to 3 phases as in Figure 4. For each branch in Tj linking nodes X1 and X2, the 3 phases are as follows: • Uplink: X1 drains its data to Fh(X1). • Highway: This phase corresponds to step 2 and uti￾lizes multihop transmission along the horizontal path from Fh(X1) to the intersection with the vertical path in which Fv(X2) resides then forwards to Fv(X2). • Downlink: X2 downloads the data from Fv(X2). Lemma 5.4: In the uplink and downlink phase, a data rate of Ω(log−2 (nsp)) can be sustained for each transmission. Proof: According to Algorithm 2, for each node X, both |Fh(X) − X| and |Fv(X) − X| is upper bound￾ed by κ log(nsp) √ L nsp . It means that if we equally divide the region O into sub-squares of size 2κ log(nsp) √ L nsp × 2κ log(nsp) √ L nsp , X and Fh(X) must reside in the same cell. The same is true for X and Fv(X). Then according to Lemma 6 in [11], each cell can be allocated a constant time to be active within the mini-slot. According to Lemma 3.2, there are at most 8κ 2 log2 (nsp) nodes in each cell, which means there are at most 8κ 2 log2 (nsp) SD pair. Thus, each SD pairs can be allocated 1 O(log2(nsp)) = Ω(log−2 (nsp)) fraction of a time slot for transmission. Then we begin to analyze the second phase. Although the highway can be virtually considered as a wired network with bandwidth Θ(W), each path must help relay data for many clusters. Therefore the allocated radio resources for a cluster is limited. In the following part, we will study the maximum number of clusters a percolated cell can serve. Lemma 5.5: Each percolated cell cannot relay data for cluster with head at a distance of √ 2(R+ 2κ log (nsp)τL √nsp ) away from the cell, therefore R ≤ √ 2(R + 2κ log (nsp))τL √nsp ). Proof: We refer to Figure 5 for the proof. Each path is constrained within a strip of width κ log(nsp) √ L nsp . Thus D is upper bounded by (κ log(nsp) √ L nsp ). Recalling that