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)<1, variable X with expectation n,for any 6>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)< 、(1+)1+可 (1) C;which have not yet been delivered to all of its members at time t.Then A must guarantee a non-backlog network,which Lemma 2.2:Holder's inequality:If S is a measurable means limt-→o∞sup1≤≤n,Bj(t)<oo. subset of Rn with the Lebesgue measure,and f and g are measurable real-or complex-valued functions on S,then Holder inequality is D.Max-min Fairness A feasible multicast rate vector As is max-min fair if and only if an increase of any individual multicast capacity within egeldc≤(rePdE)tat&a the domain of feasible allocations must be at the cost of a (2) decrease of some already smaller individual multicast capacity. where 1/p+1/g=1. Formally,we have the following. Definition of Max-min Fairness:[22]A multicast rate vector G.Main Results A is max-min fair if and only if,for any other feasible Our main results are summarized as follows: multicast rate vector As,if the individual multicast capacity of cluster i satisfies Ai>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) < 1, limn→∞ Pr(λ = c ′ f(n) is achievable) = 1. Let Bj (t) denote the number of data units already generated in Cj which have not yet been delivered to all of its members at time t. Then λ must guarantee a non-backlog network, which means limt→∞ sup1≤j≤ns Bj (t) < ∞. D. Max-min Fairness A feasible multicast rate vector λs is max-min fair if and only if an increase of any individual multicast capacity within the domain of feasible allocations must be at the cost of a decrease of some already smaller individual multicast capacity. Formally, we have the following. Definition of Max-min Fairness: [22] A multicast rate vector λs is max-min fair if and only if, for any other feasible multicast rate vector λˆs, if the individual multicast capacity of cluster i satisfies λˆ i > λi then there must exists some cluster j such that λj < λi and λˆ j < λj . In [20], the authors justified the properties of max-min fairness for multicast service in a wired network. In their model, the rate allocation for different multicast sessions was also denoted by a rate vector, in which an element represents the individual multicast capacity for one cluster. The properties can be adapted to the wireless networks since our mathematical model is almost the same as the single-rate 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 find out how large can the minimum capacity attain at most. The rest of the paper will focus on this λ, i.e., the minimum capacity. Since the main purpose of our paper lies in deriving the upper limit for minimum capacity, we omit the detailed proof of the max-min fairness properties to avoid redundancy. E. Mathematical Notations Throughout our paper, we denote h b Cj as the number of hops required for transmitting bit b to all clients in Cj . ℓ h b is the length of transmission of bit b in its hth(1 ≤ h ≤ h b Cj ) hop. δh,b is the number of nodes that can overhear a packet during a transmission of bit b in its hth hop. D(ξ, R) is the circular region centered at ξ with radius R. R is the radius of the influential region centered at the head. Nodes outside the influential region cannot act as relays for that cluster. |Tj | is the total Euclidean length of a multicast tree Tj , which can be calculated by summing up the Euclidean length of all edges belonging to the tree. F. Useful Known Results Throughout the paper, the following two known result￾s would be used for proving theorems. In particular, the Chernoff bound is applied to bound the probability of sums of independent variables and the Holder’s inequality will be ¨ consulted for deriving the bound for minimum capacity. Lemma 2.1: Chernoff bound: Given a Poisson random variable X with expectation η, for any δ > 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 <0<1.Therefore when no 42 16 w(),PrW(r)>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