Multicast Performance With Hierarchical Cooperation

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination IEEE/ACM TRANSACTIONS ON NETWORKING Multicast Performance With Hierarchical Cooperation Xinbing Wang,Member;IEEE,Luoyi Fu,and Chenhui Hu Abstract-It has been shown in a previous version of this paper ()for arbitrary networks,assuming there are n nodes in that hierarchical cooperation achieves a linear throughput scaling a unit disk area. for unicast traffic,which is due to the advantage of long-range The results on network capacity provide us not only the- concurrent transmissions and the technique of distributed mul- tiple-input-multiple-output(MIMO).In this paper,we investigate oretical capacity bounds,but also insights into the protocol the scaling law for multicast traffic with hierarchical cooperation, design and architecture of wireless networks.Therefore. where each of the n nodes communicates with k randomly chosen great efforts are devoted to understanding the scaling laws in destination nodes.Specifically,we propose a new class of sched- wireless ad hoc networks.One important stream of work is uling policies for multicast traffic.By utilizing the hierarchical improving the unicast capacity.With the percolation theory, cooperative MIMO transmission,our new policies can obtain an aggregate throughput of ()1-for any>0.This achieves Franceschetti er al.[4]show that a rate of)is at- tainable in random ad hoc networks under the Generalized a gain of nearly compared to the noncooperative scheme in Physical Model.However,it still vanishes as the number of Li et al.'s work (Proc.ACM MobiCom,2007,pp.266-277).Among nodes goes to infinity.To achieve linear capacity scaling. all four cooperative strategies proposed in our paper,one is supe- rior in terms of the three performance metrics:throughput,delay, Grossglauser et al.[5]exploit nodes'mobility to increase the and energy consumption.Two factors contribute to the optimal network throughput,but at the cost of induced delay.Tradeoff performance:multihop MIMO transmission and converge-based between the capacity and the delay is studied in [10]-[12]. scheduling.Compared to the single-hop MIMO transmission An alternative methodology is adding infrastructure to the strategy,the multihop strategy achieves a throughput gain of -1 network.It is shown in [13]-[17]that when the number of ()(21)and meanwhile reduces the energy consumption base stations grows linearly as that of the nodes (implying bytimes approximately,where h1 is the number of a huge investment),the network capacity will scale linearly the hierarchical layers,and a 2 is the path-loss exponent. Moreover,besides letting nodes perform traditional operations Moreover,to schedule the traffic with the converge multicast such as storage,replication,and forwarding,[18]and [19] instead of the pure multicast strategy,we can dramatically reduce introduce coding into the network,which also brings about the the delay by a factor of about ()Our optimal cooperative strategy achieves an approximate delay-throughput tradeoff throughput gain. D(n,k)/T(n,k)=(k)when hoo.This tradeoff ratio is Another line of research deals with more generalized identical to that of noncooperative scheme,while the throughput traffic patterns.Reference [33]studies the scalability of wire- is greatly improved. less sensor networks.In [20],Toumpis develops asymptotic Index Terms-Capacity, multiple-iput-multiple-output capacity bounds for nonuniform traffic networks.In [21], (MIMO),scaling law. broadcast capacity is discussed.Then,a unified perspective on the capacity of networks subject to a general form of infor- mation dissemination is proposed in [22.As a more efficient I.INTRODUCTION way for one-to-many data distribution than multiple unicast, YAPACITY of wireless ad hoc networks is constrained multicast fits the applications well such as group communi- by interference between concurrent transmissions.Ob- cations and multimedia services.Thus,it draws great interest serving this,Gupta and Kumar adopt the Protocol and the in the research community and has been studied by different Physical Model to define a successful transmission and study manners in [23]-[30].Specifically,in [24],the authors derive the asymptotically achievable throughput of the network in the asymptotic upper and lower bounds for multicast capacity their seminal work [3].They show that the per-node throughput by focusing on data copies and area argument in the routing tree capacity scales asθ√nlogm 1 for random networks,and established in the paper.In [25]and [34],multicast capacity is studied under a more realistic channel model,physical-layer model instead of a simplified protocol model assumed in many Manuscript received February 21,2010;revised September 15,2010;April previous works.In [26],through mathematical derivations and 03,2011;September 02,2011;and September 09,2011;accepted September simulations,the authors demonstrate that multicast achieves 17,2011.This work was supported by the National Basic Research Program of China(973 Program)under Grant 2011CB302701,NSF China under Grant 8 gain compared to unicast when information is dissemi- 60832005,the China Ministry of Education Fok Ying Tung Fund under Grant nated to n destinations in mobile ad hoc networks.In [27],a 122002,the China Ministry of Education New Century Excellent Talent under comb-based architecture is proposed instead of a routing tree Grant NCET-10-0580,and a Qualcomm Research Grant.An earlier version of for multicast,and this is shown to achieve an order-optimal this paper appeared in the Proceedings of the IEEE Conference on Computer Communications (INFOCOM),San Diego,CA,March 15-19,2010. multicast capacity in static networks.In [28],Wang et al.prove The authors are with the Department of Electronic Engineering,Shanghai that network coding cannot necessarily bring about gain in Jiao Tong University,Shanghai 200240,China (e-mail:xwang8@sjtu.edu.cn; multicast capacity,which is a counterintuitive result.Recently, yiluofu@sjtu.edu.cn;hch@sjtu.edu.cn). Color versions of one or more of the figures in this paper are available online Niesen et al.31 characterize the multicast capacity region in at http://ieeexplore.ieee.org. an extended network.Additionally,capacity-delay tradeoff for Digital Object Identifier 10.1109/TNET.2011.2170584 mobile multicast is inquired in [32]. 1063-6692/$26.00©2011IEEE

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING 1 Multicast Performance With Hierarchical Cooperation Xinbing Wang, Member, IEEE, Luoyi Fu, and Chenhui Hu Abstract—It has been shown in a previous version of this paper that hierarchical cooperation achieves a linear throughput scaling for unicast traffic, which is due to the advantage of long-range concurrent transmissions and the technique of distributed mul￾tiple-input–multiple-output (MIMO). In this paper, we investigate the scaling law for multicast traffic with hierarchical cooperation, where each of the nodes communicates with randomly chosen destination nodes. Specifically, we propose a new class of sched￾uling policies for multicast traffic. By utilizing the hierarchical cooperative MIMO transmission, our new policies can obtain an aggregate throughput of for any . This achieves a gain of nearly compared to the noncooperative scheme in Li et al.’s work (Proc. ACM MobiCom, 2007, pp. 266–277). Among all four cooperative strategies proposed in our paper, one is supe￾rior in terms of the three performance metrics: throughput, delay, and energy consumption. Two factors contribute to the optimal performance: multihop MIMO transmission and converge-based scheduling. Compared to the single-hop MIMO transmission strategy, the multihop strategy achieves a throughput gain of and meanwhile reduces the energy consumption by times approximately, where is the number of the hierarchical layers, and is the path-loss exponent. Moreover, to schedule the traffic with the converge multicast instead of the pure multicast strategy, we can dramatically reduce the delay by a factor of about . Our optimal cooperative strategy achieves an approximate delay-throughput tradeoff when . This tradeoff ratio is identical to that of noncooperative scheme, while the throughput is greatly improved. Index Terms—Capacity, multiple-iput–multiple-output (MIMO), scaling law. I. INTRODUCTION CAPACITY of wireless ad hoc networks is constrained by interference between concurrent transmissions. Ob￾serving this, Gupta and Kumar adopt the Protocol and the Physical Model to define a successful transmission and study the asymptotically achievable throughput of the network in their seminal work [3]. They show that the per-node throughput capacity scales as for random networks, and Manuscript received February 21, 2010; revised September 15, 2010; April 03, 2011; September 02, 2011; and September 09, 2011; accepted September 17, 2011. This work was supported by the National Basic Research Program of China (973 Program) under Grant 2011CB302701, NSF China under Grant 60832005, the China Ministry of Education Fok Ying Tung Fund under Grant 122002, the China Ministry of Education New Century Excellent Talent under Grant NCET-10-0580, and a Qualcomm Research Grant. An earlier version of this paper appeared in the Proceedings of the IEEE Conference on Computer Communications (INFOCOM), San Diego, CA, March 15–19, 2010. The authors are with the Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200240, China (e-mail: xwang8@sjtu.edu.cn; yiluofu@sjtu.edu.cn; hch@sjtu.edu.cn). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TNET.2011.2170584 for arbitrary networks, assuming there are nodes in a unit disk area. The results on network capacity provide us not only the￾oretical capacity bounds, but also insights into the protocol design and architecture of wireless networks. Therefore, great efforts are devoted to understanding the scaling laws in wireless ad hoc networks. One important stream of work is improving the unicast capacity. With the percolation theory, Franceschetti et al. [4] show that a rate of is at￾tainable in random ad hoc networks under the Generalized Physical Model. However, it still vanishes as the number of nodes goes to infinity. To achieve linear capacity scaling, Grossglauser et al. [5] exploit nodes’ mobility to increase the network throughput, but at the cost of induced delay. Tradeoff between the capacity and the delay is studied in [10]–[12]. An alternative methodology is adding infrastructure to the network. It is shown in [13]–[17] that when the number of base stations grows linearly as that of the nodes (implying a huge investment), the network capacity will scale linearly. Moreover, besides letting nodes perform traditional operations such as storage, replication, and forwarding, [18] and [19] introduce coding into the network, which also brings about the throughput gain. Another line of research deals with more generalized traffic patterns. Reference [33] studies the scalability of wire￾less sensor networks. In [20], Toumpis develops asymptotic capacity bounds for nonuniform traffic networks. In [21], broadcast capacity is discussed. Then, a unified perspective on the capacity of networks subject to a general form of infor￾mation dissemination is proposed in [22]. As a more efficient way for one-to-many data distribution than multiple unicast, multicast fits the applications well such as group communi￾cations and multimedia services. Thus, it draws great interest in the research community and has been studied by different manners in [23]–[30]. Specifically, in [24], the authors derive the asymptotic upper and lower bounds for multicast capacity by focusing on data copies and area argument in the routing tree established in the paper. In [25] and [34], multicast capacity is studied under a more realistic channel model, physical-layer model instead of a simplified protocol model assumed in many previous works. In [26], through mathematical derivations and simulations, the authors demonstrate that multicast achieves a gain compared to unicast when information is dissemi￾nated to destinations in mobile ad hoc networks. In [27], a comb-based architecture is proposed instead of a routing tree for multicast, and this is shown to achieve an order-optimal multicast capacity in static networks. In [28], Wang et al. prove that network coding cannot necessarily bring about gain in multicast capacity, which is a counterintuitive result. Recently, Niesen et al. [31] characterize the multicast capacity region in an extended network. Additionally, capacity-delay tradeoff for mobile multicast is inquired in [32]. 1063-6692/$26.00 © 2011 IEEE

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING Recently,Aeron et al.[6]introduce a multiple-input-mul-Hence,we propose two kinds of scheduling strategies:multi- tiple-output (MIMO)collaborative strategy achieving a cast-based strategy and converge-based strategy. throughput of (n-1/3).Different from Gupta and Kumar's Comparing these two kinds of strategies,we find that they results,they use a cooperative scheme to obtain capacity gain make no difference in terms of throughput and energy con- by turning mutually interfering signals into positive factors. sumption of the network.However,the converge-based strategy Ozgur et al.[1],[2]utilize hierarchical schemes relying on can dramatically reduce the delay by approximately (()) distributed MIMO communications to achieve linear capacity where h>1 is the number of hierarchical layers in the net- scaling.The optimal number of hierarchical stages is studied work.We further divide the cluster into"subclusters"and still in [7],while multihop and arbitrary networks are investigated use distributed MIMO to realize the communication between in [8]and [91,respectively each other.When using multicast-based strategy,each source The capacity shown in all the work above is largely bot- node must distribute data within its subcluster first,which ac- tlenecked by adjacent interference caused by the concurrently counts for the major part of the delay.In contrast,utilizing the transmitting nodes nearby,which is the bottleneck for the ca- converge nature of the traffic,converge-based strategy omits the pacity of traditional ad hoc networks.This motivates us to in- distribution procedure and significantly reduces the delay vestigate multicast scaling laws with hierarchical MIMO in this Our main contributions are as follows. paper.We jointly consider the effect of traffic patterns and co- We propose a class of hierarchical cooperative scheduling operative strategies on the asymptotic performance of networks, policies for the multicast traffic,which can achieve the aiming to break the bottleneck.To this end,the following fun- throughput close to the information-theoretic upper bound. damental issues should be addressed. We reschedule the traffic of our cooperative transmission How to hierarchically schedule multicast traffic to opti- and dramatically reduce the delay. mize the achievable multicast throughput? The cooperative multicast scheme proposed in this paper Is it possible to achieve optimal throughput while main- greatly improves the network throughput,while it achieves taining good delay performance and energy efficiency in the same delay-throughput tradeoff as the noncooperative the network? multicast scheme,and the cooperative multicast tradeoff What is the delay-throughput tradeoff with hierarchical co- even outperforms that of unicast in some special cases. operative multicast strategies? Main results in the paper are as follows. To help answer the questions above,we propose a class of We achieve a throughput of(()),which has a gain hierarchical cooperative scheduling strategies for the multicast of nearly compared to the noncooperative scheme. traffic.Specifically,we divide the network into clusters:nodes ·The delay of our optimal strategy is合(n0=÷kza)。 in the same cluster cooperate to transmit data for each other.In this way,all transmissions in the network consist of two parts: which achieves a delay-throughput tradeoff ratio intercluster communication and intracluster communication. ⊙(k()÷). The energy-per-bit consumption isn) A.Intercluster Communication The remainder of this paper is organized as follows.In Section II.we introduce our network models and definitions The transmissions between clusters are conducted by dis- tributed MIMO.When a cluster acts as a sender,all nodes in of terms.In Section III,we outline the multicast hierarchical cooperative scheme.The analysis of throughput,delay,and the cluster transmit a distinct bit at the same time.Then,each node in the receiving cluster can observe a signal containing in- energy consumption are presented in Sections IV,V-A,and formation of all transmitted bits. V-B,respectively.All the results are discussed in detail in We propose two kinds of transmission method:direct and Section VI.Finally,we conclude the paper in Section VII. multihop MIMO transmission,which are more general than II.NETWORK MODELS AND DEFINITIONS that in [35].For the communication between clusters,the direct method uses MIMO transmission only once from the source A.Network Models cluster to all destination clusters,while the multihop method conducts MIMO transmissions for many hops,with each time a We consider a set of n nodes in V {v1,v2,...,Un uni- formly and independently distributed in a unit square Each cluster only transmits to the neighboring cluster.We will show node v;acts as a source node of a multicast session. in this paper that multihop MIMO transmission can increase Multicast Traffic:For a source node vi,we randomly and the throughput and reduce the energy consumption due to better spatial reuse and power management. independently choose a set ofk:nodes inU:={i1 0.Intu- of the data flows,it can also be regarded as converge multicast. itively,this means f(n )=e(g(n )with logarithmic terms ignored

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 2 IEEE/ACM TRANSACTIONS ON NETWORKING Recently, Aeron et al. [6] introduce a multiple-input–mul￾tiple-output (MIMO) collaborative strategy achieving a throughput of . Different from Gupta and Kumar’s results, they use a cooperative scheme to obtain capacity gain by turning mutually interfering signals into positive factors. Özgür et al. [1], [2] utilize hierarchical schemes relying on distributed MIMO communications to achieve linear capacity scaling. The optimal number of hierarchical stages is studied in [7], while multihop and arbitrary networks are investigated in [8] and [9], respectively. The capacity shown in all the work above is largely bot￾tlenecked by adjacent interference caused by the concurrently transmitting nodes nearby, which is the bottleneck for the ca￾pacity of traditional ad hoc networks. This motivates us to in￾vestigate multicast scaling laws with hierarchical MIMO in this paper. We jointly consider the effect of traffic patterns and co￾operative strategies on the asymptotic performance of networks, aiming to break the bottleneck. To this end, the following fun￾damental issues should be addressed. • How to hierarchically schedule multicast traffic to opti￾mize the achievable multicast throughput? • Is it possible to achieve optimal throughput while main￾taining good delay performance and energy efficiency in the network? • What is the delay-throughput tradeoff with hierarchical co￾operative multicast strategies? To help answer the questions above, we propose a class of hierarchical cooperative scheduling strategies for the multicast traffic. Specifically, we divide the network into clusters; nodes in the same cluster cooperate to transmit data for each other. In this way, all transmissions in the network consist of two parts: intercluster communication and intracluster communication. A. Intercluster Communication The transmissions between clusters are conducted by dis￾tributed MIMO. When a cluster acts as a sender, all nodes in the cluster transmit a distinct bit at the same time. Then, each node in the receiving cluster can observe a signal containing in￾formation of all transmitted bits. We propose two kinds of transmission method: direct and multihop MIMO transmission, which are more general than that in [35]. For the communication between clusters, the direct method uses MIMO transmission only once from the source cluster to all destination clusters, while the multihop method conducts MIMO transmissions for many hops, with each time a cluster only transmits to the neighboring cluster. We will show in this paper that multihop MIMO transmission can increase the throughput and reduce the energy consumption due to better spatial reuse and power management. B. Intracluster Communication To decode MIMO transmissions, the destination nodes in each destination cluster must observe results from all other nodes in the same cluster. Since each cluster may act as a destination cluster of multiple source clusters, there are several sets of destination nodes in it. For each set, every node in the cluster sends one identical bit to all nodes in the set. This traffic can be seen as multicast, but considering the “converge” nature of the data flows, it can also be regarded as converge multicast. Hence, we propose two kinds of scheduling strategies: multi￾cast-based strategy and converge-based strategy. Comparing these two kinds of strategies, we find that they make no difference in terms of throughput and energy con￾sumption of the network. However, the converge-based strategy can dramatically reduce the delay by approximately , where is the number of hierarchical layers in the net￾work. We further divide the cluster into “subclusters” and still use distributed MIMO to realize the communication between each other. When using multicast-based strategy, each source node must distribute data within its subcluster first, which ac￾counts for the major part of the delay. In contrast, utilizing the converge nature of the traffic, converge-based strategy omits the distribution procedure and significantly reduces the delay. Our main contributions are as follows. • We propose a class of hierarchical cooperative scheduling policies for the multicast traffic, which can achieve the throughput close to the information-theoretic upper bound. • We reschedule the traffic of our cooperative transmission and dramatically reduce the delay. • The cooperative multicast scheme proposed in this paper greatly improves the network throughput, while it achieves the same delay-throughput tradeoff as the noncooperative multicast scheme, and the cooperative multicast tradeoff even outperforms that of unicast in some special cases. Main results in the paper are as follows.1 • We achieve a throughput of , which has a gain of nearly compared to the noncooperative scheme. • The delay of our optimal strategy is , which achieves a delay-throughput tradeoff ratio . • The energy-per-bit consumption is . The remainder of this paper is organized as follows. In Section II, we introduce our network models and definitions of terms. In Section III, we outline the multicast hierarchical cooperative scheme. The analysis of throughput, delay, and energy consumption are presented in Sections IV, V-A, and V-B, respectively. All the results are discussed in detail in Section VI. Finally, we conclude the paper in Section VII. II. NETWORK MODELS AND DEFINITIONS A. Network Models We consider a set of nodes in uni￾formly and independently distributed in a unit square . Each node acts as a source node of a multicast session. Multicast Traffic: For a source node , we randomly and independently choose a set of nodes in other than in the deployment square as its destination nodes. We define a multicast session as the collection of transmissions from one source node to destination nodes and use to denote an -session multicast problem with each node acting as a source node for a session. We then define another traffic that helps our analysis. Converge Multicast Traffic: We randomly and independently choose a set of nodes as destinations. 1We use Knuth’s notation in this paper. Also, we use to indicate and , for any . Intu￾itively, this means with logarithmic terms ignored

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. WANG et al.:MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION B.Definition of Performance Metrics Definition of Throughput:A per-node throughput of A(n,k)bits/s is feasible if there is a spatial and temporal trans- mission scheme,such that every node can send A(n,k:)bits/s on average to its k:randomly chosen destination nodes.The aggre- gate multicast throughput of the system is I'(n,)=nA(n,k). Step2 When k=1,it degenerates to aggregate unicast throughput. Definition of Delay:The delay D(n.k:)of a communication scheme for the network is defined as the average time it takes for a bit to reach its k destination nodes after leaving its source node.The averaging is over all bits transmitted in the network. Definition of Energy-Per-Bit:We introduce energy-per-bit E(n,k)to define the average energy required to carry one bit from a source node to one of its k:destination nodes. (a) III.TRANSMISSION STRATEGY Fig.1.Transmission strategy of hierarchical cooperation.(a)Three-step struc- ture.(b)Multihop MIMO transmission.(c)Converge multicast transmission frame. A.General Multicast Structure The key idea of our multicast structure is dividing the network into clusters with equal numbers of nodes,then the traffic can Each of the n nodes in the network acts as a source node and be transformed into intra-and intercluster transmissions.In this sends one identical bit to all nodes in U:.This is a"converge" way.we divide the network into two lavers:the clusters and the transmission because the overall data flow is from all n nodes to whole network.We call the former lower laver,and the latter the set of k nodes,as shown in Fig.1(c);we define it as a con- upper layer,and let n and n2 be the number of nodes in the verge multicast frame.Denoting CMP(n,m,k:)as an m-frame lower and upper layer,respectively.In each multicast session, converge multicast problem,for each frame we choose a set of there is a source node as well as k randomly chosen destination k:destination nodes nodes.Let k be the number of destination nodes in a cluster Wireless Channel Model:We assume that the communica- and k:2=k:be that in the network.We term the cluster con- tion is over a channel of limited bandwidth W.Each node has taining the source node source cluster,and clusters containing a power budget of P.For the transmission from v;to vi,the at least one destination node destination clusters.Each multi- channel gain between them at time t is given by cast session is realized by a three-step structure [see Fig.1(a)]. i=VGd2 Step 1)The source node distributes n bits to n nodes in (1) the cluster,one bit for each node.The traffics in this step are unicasts from the source node to n-1 other where dij is the distance between v;and v,t]is the random nodes in the same cluster. phase at time t,uniformly distributed in [0,2).]12 sion to convey data to the destination clusters.There are constants,where o is called the path-loss exponent.The are two means for MIMO transmissions. signal received by node v;at time t thus can be expressed as Multihop MIMO transmission:Each source Y=∑9X+Zd+1 (2) cluster uses MIMO to transmit to a neighboring cluster called relay cluster.After each node in jETt] the relay cluster receives a MIMO observation,it where Yat]is the signal received by node v;at time t,T[t]rep- amplifies the received signal to a desirable power resents the set ofactive senders that can be added constructively. and retransmits it to the following relay cluster in Zit]is the Gaussian noise at node v:of variance No per symbol, the next chance according to the routing protocol. and I[t]is the interference from the nodes which are destruc- This process is repeated until all the destination tive to the reception of node v:. clusters receive MIMO observations,as shown When conducting the cooperative transmission,we assume in Fig.1(b). that the full channel state information(CSI)is available at each .Direct MIMO transmission:The nodes in the node.2 Also,we assume the far-field condition holds for all source cluster broadcast the data in the network nodes,1.e.,the minimum distance between any two nodes is simultaneously,and then all nodes in the destina- larger than the wavelength of the carrier.3 tion clusters can receive a MIMO observation. In this paper,we only consider the dense network,which Step 3)After each destination cluster receives the MIMO means that the network area is a unit square.Our hierarchical transmissions,each node in the cluster holds an ob- cooperative scheme can also be applied to the extended network, servation.The k destination nodes in the cluster with a vn x vn square network area. must collect all n observations to decode the n transmitted bits.Thus,the traffics in this step are 2This assumption is also made in [1]. n multicast sessions,with each node in the cluster The assumption is proved to be reasonable in the first paragraph of [1,p.3]. acting as a source node.Also,the k destination

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. WANG et al.: MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION 3 Fig. 1. Transmission strategy of hierarchical cooperation. (a) Three-step struc￾ture. (b) Multihop MIMO transmission. (c) Converge multicast transmission frame. Each of the nodes in the network acts as a source node and sends one identical bit to all nodes in . This is a “converge” transmission because the overall data flow is from all nodes to the set of nodes, as shown in Fig. 1(c); we define it as a con￾verge multicast frame. Denoting as an -frame converge multicast problem, for each frame we choose a set of destination nodes. Wireless Channel Model: We assume that the communica￾tion is over a channel of limited bandwidth . Each node has a power budget of . For the transmission from to , the channel gain between them at time is given by (1) where is the distance between and , is the random phase at time , uniformly distributed in . is a collection of independently and identically dis￾tributed (i.i.d.) random processes. The parameters and are constants, where is called the path-loss exponent. The signal received by node at time thus can be expressed as (2) where is the signal received by node at time , rep￾resents the set of active senders that can be added constructively, is the Gaussian noise at node of variance per symbol, and is the interference from the nodes which are destruc￾tive to the reception of node . When conducting the cooperative transmission, we assume that the full channel state information (CSI) is available at each node.2 Also, we assume the far-field condition holds for all nodes, i.e., the minimum distance between any two nodes is larger than the wavelength of the carrier.3 In this paper, we only consider the dense network, which means that the network area is a unit square. Our hierarchical cooperative scheme can also be applied to the extended network, with a square network area. 2This assumption is also made in [1]. 3The assumption is proved to be reasonable in the first paragraph of [1, p. 3]. B. Definition of Performance Metrics Definition of Throughput: A per-node throughput of bits/s is feasible if there is a spatial and temporal trans￾mission scheme, such that every node can send bits/s on average to its randomly chosen destination nodes. The aggre￾gate multicast throughput of the system is . When , it degenerates to aggregate unicast throughput. Definition of Delay: The delay of a communication scheme for the network is defined as the average time it takes for a bit to reach its destination nodes after leaving its source node. The averaging is over all bits transmitted in the network. Definition of Energy-Per-Bit: We introduce energy-per-bit to define the average energy required to carry one bit from a source node to one of its destination nodes. III. TRANSMISSION STRATEGY A. General Multicast Structure The key idea of our multicast structure is dividing the network into clusters with equal numbers of nodes, then the traffic can be transformed into intra- and intercluster transmissions. In this way, we divide the network into two layers: the clusters and the whole network. We call the former lower layer, and the latter upper layer, and let and be the number of nodes in the lower and upper layer, respectively. In each multicast session, there is a source node as well as randomly chosen destination nodes. Let be the number of destination nodes in a cluster, and be that in the network. We term the cluster con￾taining the source node source cluster, and clusters containing at least one destination node destination clusters. Each multi￾cast session is realized by a three-step structure [see Fig. 1(a)]. Step 1) The source node distributes bits to nodes in the cluster, one bit for each node. The traffics in this step are unicasts from the source node to other nodes in the same cluster. Step 2) The nodes in the source cluster transmit simultane￾ously by implementing distributed MIMO transmis￾sion to convey data to the destination clusters. There are two means for MIMO transmissions. • Multihop MIMO transmission: Each source cluster uses MIMO to transmit to a neighboring cluster called relay cluster. After each node in the relay cluster receives a MIMO observation, it amplifies the received signal to a desirable power and retransmits it to the following relay cluster in the next chance according to the routing protocol. This process is repeated until all the destination clusters receive MIMO observations, as shown in Fig. 1(b). • Direct MIMO transmission: The nodes in the source cluster broadcast the data in the network simultaneously, and then all nodes in the destina￾tion clusters can receive a MIMO observation. Step 3) After each destination cluster receives the MIMO transmissions, each node in the cluster holds an ob￾servation. The destination nodes in the cluster must collect all observations to decode the transmitted bits. Thus, the traffics in this step are multicast sessions, with each node in the cluster acting as a source node. Also, the destination

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING nodes are identical for all n sessions.Hence,the DMM.or the number of converge multicast frames at layer traffic can also be treated as a converge multicast when considering the CMMM/CDMM problem,where all source nodes "converge"4 their data to a set of destination nodes. IV.ANALYSIS OF MULTICAST THROUGHPUT Following the steps above,we can build a hierarchical In this section,we first present the information-theoretic scheme in a network with multiple layers to achieve the desired upper bound of the multicast throughput.Then,we provide throughput.At the lowest layer,we use simple TDMA protocol strategies that can almost achieve the upper bound by utilizing to exchange bits for setting up cooperation among small clus- cooperation in the network.When analyzing the throughput, ters.Combining this with multihop MIMO transmissions,we we use an "assume-and-verify"method,i.e.,we first make get a higher throughput scheme for cooperation among nodes some assumptions on the network;after we obtain the results, in larger clusters at the next layer.Finally,at the top layer,the we verify these assumptions.Using this method,we make our size of the cooperation clusters is maximum,and the MIMO analysis both strict and easy to follow. transmissions are almost over the global scale to meet the desired traffic demands. A.Upper Bound of Multicast Throughput B.Four Strategies for Cooperative Multicast To prove the upper bound,we need to set the lower bound of the pairwise distance between nodes,which is provided in the Following the three-step multicast structure,we propose four following lemma. strategies that can realize the steps.A multilayer solution is in- Lemma 4.1:In a network with n nodes randomly and uni- volved in each of the strategies. formly distributed on a unit-square,the minimum distance be- Multihop MIMO multicast(MMM):Step 3 is formulated tween any two nodes iswhp.,s for any0. as a multicast problem with multihop MIMO transmis- Proof:Consider a specific node v;,proving the distance be- sions.The multicast delivery in Step 3 can also be han- tween v:and all other nodes is larger than is equivalent to dled using the same three-step structure.Implementing the proving that there are no other nodes inside a circle ofarea three-step structure recursively,we can get a hierarchical solution to the multicast problem. around v:.The probability of such an event is (1-) The minimum distance between any two nodes in the network Direct MIMO multicast(DMM):Step 3 is formulated as a multicast problem with direct MIMO transmissions. is larger than only if this condition is satisfied for all nodes Converge-based multihop MIMO multicast (CMMM): in the network.Thus,by union bound we have 1 Step 3 is formulated as a converge multicast problem P4≤n中s:orai,and≠j≤n(-(（ n2+26 with multihop MIMO transmissions,and the converge multicast problem can also be solved with the multilayer which diminishes to zero when n tends to infinity ■ manner. Theorem 4.1:In the network with n nodes and each sending Converge-based direct MIMO multicast(CDMM):Step 3 packets to k:randomly chosen destination nodes,the aggregate is formulated as a converge multicast problem with direct multicast throughput is bounded by MIMO transmissions n logn For the hierarchical schemes with multiple layers,we give the T(n,k)≤p1 more detailed definition of the converge multicast frame intro- duced in the CMMM and CDMM schemes as following w.h.p.,where pi>0 is a constant independent of n and k. 1)Converge Multicast:Consider the cooperative hierar- Proof:For each source node in the network,we have ran- chical scheme with two layers.At layer i,for any destination domly assigned k:destination nodes to it.If the sets of desti- nation nodes for each source node do not intersect with each cluster,there are n1 nodes in that cluster,with k of them being destinations.The converge multicast frame here refers to other,there will be totally nk nodes acting as destination nodes the traffic pattern where all the n:nodes in this destination However,there are only n nodes in the whole network.Thus,by cluster transmit their data to those k:1 destinations.Here, considering the source-destination pairing from a reverse view. there are n multicast sessions,with each node in the cluster for each node d,there are k nodes s1,s2:...,s on average, which choose d as one of its destination nodes.Assume each acting as a source node. source node transmits data to d at the same rate A(n,k:),the C.Notations total ratek入(n,k)from the source nodes s:(l≤i≤k)to the We use the following notations throughout this paper.First, destination node d is upper-bounded by the capacity of a mul- let h be the number of layers that is independent of n and k. tiple-input-single-output (MISO)channel between d and the Then,we label each layer with a unique number i(1 <i<h). rest of the network.Using a standard formula for this channel, indicating the ith layer from the bottom up. we get Given a layer i,let n;be the number of nodes and k;be that of destination nodes for each source node;apparently,n=n kλ(n,k)≤ and ki=k.We use ne=ni/n:-1 to denote the number of clusters,and ke;the number of destination clusters at layer i. When analyzing strategies,we use mi to denote the number of multicast sessions at layer i when considering the MMM/ +Note that the traffic mode is similar to converge-cast in Step 3.Our multicast analysis can well cover converge-cast case,where sources transmit information 5In this paper,w.hp."stands for"with high probability,"which means the to the destination with distinctive data rates. probability tends to I as n -oo

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 4 IEEE/ACM TRANSACTIONS ON NETWORKING nodes are identical for all sessions. Hence, the traffic can also be treated as a converge multicast problem, where all source nodes “converge”4 their data to a set of destination nodes. Following the steps above, we can build a hierarchical scheme in a network with multiple layers to achieve the desired throughput. At the lowest layer, we use simple TDMA protocol to exchange bits for setting up cooperation among small clus￾ters. Combining this with multihop MIMO transmissions, we get a higher throughput scheme for cooperation among nodes in larger clusters at the next layer. Finally, at the top layer, the size of the cooperation clusters is maximum, and the MIMO transmissions are almost over the global scale to meet the desired traffic demands. B. Four Strategies for Cooperative Multicast Following the three-step multicast structure, we propose four strategies that can realize the steps. A multilayer solution is in￾volved in each of the strategies. • Multihop MIMO multicast (MMM): Step 3 is formulated as a multicast problem with multihop MIMO transmis￾sions. The multicast delivery in Step 3 can also be han￾dled using the same three-step structure. Implementing the three-step structure recursively, we can get a hierarchical solution to the multicast problem. • Direct MIMO multicast (DMM): Step 3 is formulated as a multicast problem with direct MIMO transmissions. • Converge-based multihop MIMO multicast (CMMM): Step 3 is formulated as a converge multicast problem with multihop MIMO transmissions, and the converge multicast problem can also be solved with the multilayer manner. • Converge-based direct MIMO multicast (CDMM): Step 3 is formulated as a converge multicast problem with direct MIMO transmissions. For the hierarchical schemes with multiple layers, we give the more detailed definition of the converge multicast frame intro￾duced in the CMMM and CDMM schemes as following. 1) Converge Multicast: Consider the cooperative hierar￾chical scheme with two layers. At layer , for any destination cluster, there are nodes in that cluster, with of them being destinations. The converge multicast frame here refers to the traffic pattern where all the nodes in this destination cluster transmit their data to those destinations. Here, there are multicast sessions, with each node in the cluster acting as a source node. C. Notations We use the following notations throughout this paper. First, let be the number of layers that is independent of and . Then, we label each layer with a unique number ( ), indicating the th layer from the bottom up. Given a layer , let be the number of nodes and be that of destination nodes for each source node; apparently, and . We use to denote the number of clusters, and the number of destination clusters at layer . When analyzing strategies, we use to denote the number of multicast sessions at layer when considering the MMM/ 4Note that the traffic mode is similar to converge-cast in Step 3. Our multicast analysis can well cover converge-cast case, where sources transmit information to the destination with distinctive data rates. DMM, or the number of converge multicast frames at layer when considering the CMMM/CDMM. IV. ANALYSIS OF MULTICAST THROUGHPUT In this section, we first present the information-theoretic upper bound of the multicast throughput. Then, we provide strategies that can almost achieve the upper bound by utilizing cooperation in the network. When analyzing the throughput, we use an “assume-and-verify” method, i.e., we first make some assumptions on the network; after we obtain the results, we verify these assumptions. Using this method, we make our analysis both strict and easy to follow. A. Upper Bound of Multicast Throughput To prove the upper bound, we need to set the lower bound of the pairwise distance between nodes, which is provided in the following lemma. Lemma 4.1: In a network with nodes randomly and uni￾formly distributed on a unit-square, the minimum distance be￾tween any two nodes is w.h.p.,5 for any . Proof: Consider a specific node , proving the distance be￾tween and all other nodes is larger than is equivalent to proving that there are no other nodes inside a circle of area around . The probability of such an event is . The minimum distance between any two nodes in the network is larger than only if this condition is satisfied for all nodes in the network. Thus, by union bound we have for all and which diminishes to zero when tends to infinity. Theorem 4.1: In the network with nodes and each sending packets to randomly chosen destination nodes, the aggregate multicast throughput is bounded by w.h.p., where is a constant independent of and . Proof: For each source node in the network, we have ran￾domly assigned destination nodes to it. If the sets of desti￾nation nodes for each source node do not intersect with each other, there will be totally nodes acting as destination nodes. However, there are only nodes in the whole network. Thus, by considering the source–destination pairing from a reverse view, for each node , there are nodes on average, which choose as one of its destination nodes. Assume each source node transmits data to at the same rate , the total rate from the source nodes ( ) to the destination node is upper-bounded by the capacity of a mul￾tiple-input–single-output (MISO) channel between and the rest of the network. Using a standard formula for this channel, we get 5In this paper, “w.h.p.” stands for “with high probability,” which means the probability tends to 1 as

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. WANG et al.:MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION According to Lemma 4.1,the distance between s;(12,one Lemma 4.2:Consider n;nodes uniformly distributed in the node in each cluster has a chance to exchange data at a con- network area.We divide the network into ne identical square- stant transmission rate.Also,when a >2,the interfering power shaped clusters.Then,the number of nodes in each cluster is received by a node from the simultaneously active clusters is ni-1=mw.h.p.when Assumption 1:ni=(ne,log ne,is upper-bounded by a constant. satisfied. Proof:We divide the network into groups,each of which Proof The number of nodes in a cluster at layer i is the contains nine subsquares.The nine squares in each group are sum of i.i.d.Bernoulli random variables Xi,such that P[Xj= numbered from I to 9 the same way as in the 9-TDMA scheme. 1]=1/nc,.Using Chernoff bounds We further divide time into sequences of successive slots,de- noted by t(=0,1,2,3,...).During a particular slot t,one ≥(1+6)西 0 is a constant depending only on 6, thus-1=∑1X=O(）w.hp, ◆ n/M GP(n,k】 Remark 4.1:Note that the purpose of Lemma 4.2 is to show the relationship between the number of nodes at layer i,denoted 11 [3-1)VA% by ni,and the number of cells at layer i,namely,ne.Actually, how ne varies at each layer depends on not only n,but also 8GP(n,k) n/M ≤ the number of total layers h and the property of the cooperative A号 1+∑8-)l- 1=2 scheme adopted as well.Different hierarchical divisions at each 8GP(n,k) layer will lead to different throughput results.In our following A受 1+3j+2)1-od山 =0 MMM,CMMM,DMM,and CDMM schemes,the detailed de- pendency of nc:on n can be revealed during the analysis on 8GP(n,k) throughput and delay. Λ÷ 1+3a-2 As mentioned earlier,we solve the MP(n.k:)in the network 8GP(n,k)3a-5 (3) area with a three-step approach.Since the problems in Steps I A号 3a-6 and 3 are also multicast problems,o we can apply the three steps recursively and build an h-layer solution. If we choose the transmission power P(n,k)=e(A), 1)Solution to Multicast Problem:We consider the ith layer the interfering power will be upper-bounded by a constant in the network(2 <i<h)and follow the three steps. independent ofn.Since the maximum distance for a transmitter Step 1:Preparing for Cooperation:Given the total number of multicast sessions mi at layer i,each node holds 7This assumption is also needed in other strategies,so we will not repeat. Also note that negligible channel interference is one of the basic catches that bits tomulticast.In this step,each node must distribute make both our work and analysis go through.Without the guarantee of constant bounded interference,we cannot ensure the high decoding probability at the 6We view unicast as a special case of multicast problem. receiving nodes

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. WANG et al.: MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION 5 According to Lemma 4.1, the distance between ( ) and is larger than w.h.p. With this fact, we obtain w.h.p. for some constant independent of and . The the￾orem then follows. B. Throughput Analysis With MMM To ensure successful MIMO transmissions, each cluster must have the same number of nodes. The following lemma ensures the number of nodes in each cluster at layer has the same order. For simplicity, we consider the number of nodes in each cluster is exactly . Lemma 4.2: Consider nodes uniformly distributed in the network area. We divide the network into identical square￾shaped clusters. Then, the number of nodes in each cluster is w.h.p. when Assumption 1: is satisfied. Proof: The number of nodes in a cluster at layer is the sum of i.i.d. Bernoulli random variables , such that . Using Chernoff bounds with When if . Here, is a constant depending only on , thus w.h.p. Remark 4.1: Note that the purpose of Lemma 4.2 is to show the relationship between the number of nodes at layer , denoted by , and the number of cells at layer , namely, . Actually, how varies at each layer depends on not only , but also the number of total layers and the property of the cooperative scheme adopted as well. Different hierarchical divisions at each layer will lead to different throughput results. In our following MMM, CMMM, DMM, and CDMM schemes, the detailed de￾pendency of on can be revealed during the analysis on throughput and delay. As mentioned earlier, we solve the in the network area with a three-step approach. Since the problems in Steps 1 and 3 are also multicast problems,6 we can apply the three steps recursively and build an -layer solution. 1) Solution to Multicast Problem: We consider the th layer in the network ( ) and follow the three steps. Step 1: Preparing for Cooperation: Given the total number of multicast sessions at layer , each node holds bits to multicast. In this step, each node must distribute 6We view unicast as a special case of multicast problem. all its data to other nodes in the same cluster, with bits for each. As there are source nodes in each cluster, the traffic load is bits. Since the data exchanges only involve intracluster communication, they can work according to the 9-TDMA scheme. We divide time into slots; at each time slot, let the neighboring eight clusters keep silent when the centric cluster is exchanging data. According to the channel model (2), we assume that the received interference signal is a collection of uncorrelated zero-mean stationary and ergodic random processes with power upper-bounded by a constant.7 This assumption is also adopted in the proof of Lemma 3.1 [2]. Thus, the power of destructive interference is bounded, en￾abling clusters to operate simultaneously according to the 9-TDMA scheme, which is ensured by Lemma 4.3. Lemma 4.3: By the 9-TDMA scheme, when , one node in each cluster has a chance to exchange data at a con￾stant transmission rate. Also, when , the interfering power received by a node from the simultaneously active clusters is upper-bounded by a constant. Proof: We divide the network into groups, each of which contains nine subsquares. The nine squares in each group are numbered from 1 to 9 the same way as in the 9-TDMA scheme. We further divide time into sequences of successive slots, de￾noted by ( ). During a particular slot , one node in subsquares that are numbered is allowed to transmit packets. In a slot, if a node inside the subsquare is allowed to transmit to another node inside , those nodes that may in￾terfere with the current transmission must be located along the perimeters of concentric subsquares centered at . The interfering nodes can be grouped based on their distances to such that the th group contains interfering nodes or less (near the boundary of the network) and the shortest distance from the receiver in is , where is the area of the subsquare. Assuming that all nodes use the same transmission power , with the power propagation model in (1), the cumulative interference at subsquare , denoted by , can be bounded by (3) If we choose the transmission power , the interfering power will be upper-bounded by a constant independent of . Since the maximum distance for a transmitter 7This assumption is also needed in other strategies, so we will not repeat. Also note that negligible channel interference is one of the basic catches that make both our work and analysis go through. Without the guarantee of constant bounded interference, we cannot ensure the high decoding probability at the receiving nodes

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING to a receiver is v2A,the reception power can be lower-bounded Step 3:Cooperative Decoding:Now that each MT has by kc,destination clusters,after Step 2,every cluster receives MIMO transmissions.For each MIMO transmis- sion,every node in a destination cluster obtains an observation Ra≥ GP(n,k) (4) that the n:1 bits are transmitted from the source node.To (V2A) decode the original n:-1 bits,all nodes in the destination cluster must quantify each observation into Q bits,where Q As a result,the signal-to-interference-plus-noise ratio (SINR) for the transmission in si,denoted by SINR,is is a constant.After that,each node conveys the bits to all :1 destination nodes in the cluster.Obviously,this procedure can be formulated as an MP(ni-1,i-1).After all observa- SINR= Rs No +Ix tion results reach the destination nodes,they can decode the GP(n,k) transmitted ni1 bits. (2A) Assume that an aggregate multicast throughput(n1) V0+sGPn,☒ 5) 3a-5 is achievable at layer(i-l)w.h.p.,where0≤a≤l,-l≤ A营 3n-6 b≤0，anda+b≤0，then the MP(ni-1,ki-i)can be solved Note that P(n,k)=(A),and the SINR is a constant irrela- htime slots Note that each cluster reives tive to n and k.Therefore,a fixed transmission rate independent )MIMO transmissions and needs to perform this de- of n and k:can be achieved,according to Shannon's channel coding process for each transmission.By utilizing the 9-TDMA capacity formula,i.e.,R(n,k)=W log(1 SINR),where scheme,we can finish all m:1=mike,multicast sessions in R(n.is the feasible rate and W is the channel bandwidth. Under the assumption of an aggregate unicast throughput )rounds.Consequently,Step 3 costs n:k9-1 of (n2),0 <a 1 can be achieved for every possible time slots. source-destination pair at layer (i-1).Given a traffic load Finally,the transmission should be performed at the bottom of)bits,this step can be completed in layer.Since every node broadcasts its data in each session,all destination nodes can receive one bit,and a multicast session time slots. can be completed in one time slot. Step 2:Multihop MIMO Transmissions:In this step,each 2)Division of the Network:By minimizing the total time source cluster starts a series of MIMO transmissions to reach cost during the three steps at layer i,we present the throughput- all its corresponding destination clusters using the multihop optimal division of the network. method.To achieve the asymptotically optimal multicast Lemma 4.5:Given k:independently and uniformly dis- throughput,we construct a multicast tree (MT)by adopting tributed destination nodes in the network at layer i,the number 26,Algorithm 1,spanning over a source cluster S;and its of destination clusters ke is given by corresponding destination clusters Dij,where 1 j<ke,. Algorithm I is briefly described as follows to make this paper ⊙(k), whenki=O(ne;) self-contained. Kc:= (- whenki=(ne ) For a set of nodes P={Si,Dij,1 <j<ke:}containing a super source node and its super destination nodes,we first Proof:Let Xi be a random variable build a Euclidean spanning tree,denoted as ES'l(P),to con- nect them.For each link uv in EST(P:),we decompose it into 1, X if cluster j contains at least one destination node a Manhattan path connecting u and v to form Manhattan routing 0.else tree MRT(P).Then,for each edge uw in MRT(P),we con- nect super nodes crossed by uw in sequence.The final tree is then c= Since the destination nodes at layeri called multicast tree MT. are uniformly and independently distributed in ne clusters,the The constructed MT owns the following properties, with probability that a destination node is in clusterj is 1/nc,and the which we can acquire by Lemma 4.4. probability that none of the ki destination nodes is in cluster j ·The maximum length of each hop at layer i is曰( ni-1 is(1- which gives ·The total length of MT(P)is at most O(Vke× Lemma 4.4:The number of hops in the MT is O X=1 For all m;multicast sessions,at layer i there are and the total number of hops is Using the Sinceis a sequence of i.i.d.random variables,using the law of large numbers,we obtain w.h.p.that 9-TDMA scheduling,each cluster is allowed to take MIMO transmission in every nine time slots.Ifa cluster serves as a relay cluster for multiple multicast sessions,it will deliver the packets X→1 when ne:一o.(6) nc: --) of different sessions including its own packets with equal prob- ability.According to our protocol,clusters can transmit simul- taneously at each time slot().Therefore,the total amount Consequently,the number of clusters that contain at least one of time to accomplish all m:sessions'MIMO transmissions is destination node is ke =ne (1-(1).Ifk;=(ne). (miTn-1 8This is valid under Assumption 3 in Lemma 4.7,which we present later

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 6 IEEE/ACM TRANSACTIONS ON NETWORKING to a receiver is , the reception power can be lower-bounded by (4) As a result, the signal-to-interference-plus-noise ratio (SINR) for the transmission in , denoted by , is (5) Note that , and the SINR is a constant irrela￾tive to and . Therefore, a fixed transmission rate independent of and can be achieved, according to Shannon’s channel capacity formula, i.e., , where is the feasible rate and is the channel bandwidth. Under the assumption of an aggregate unicast throughput of can be achieved for every possible source–destination pair at layer . Given a traffic load of bits, this step can be completed in time slots. Step 2: Multihop MIMO Transmissions: In this step, each source cluster starts a series of MIMO transmissions to reach all its corresponding destination clusters using the multihop method. To achieve the asymptotically optimal multicast throughput, we construct a multicast tree (MT) by adopting [26, Algorithm 1], spanning over a source cluster and its corresponding destination clusters , where . Algorithm 1 is briefly described as follows to make this paper self-contained. For a set of nodes containing a super source node and its super destination nodes, we first build a Euclidean spanning tree, denoted as , to con￾nect them. For each link in , we decompose it into a Manhattan path connecting and to form Manhattan routing tree . Then, for each edge in , we con￾nect super nodes crossed by in sequence. The final tree is called multicast tree MT. The constructed MT owns the following properties, with which we can acquire by Lemma 4.4. • The maximum length of each hop at layer is . • The total length of is at most . Lemma 4.4: The number of hops in the MT is . For all multicast sessions, at layer there are MTs, and the total number of hops is . Using the 9-TDMA scheduling, each cluster is allowed to take MIMO transmission in every nine time slots. If a cluster serves as a relay cluster for multiple multicast sessions, it will deliver the packets of different sessions including its own packets with equal prob￾ability. According to our protocol, clusters can transmit simul￾taneously at each time slot . Therefore, the total amount of time to accomplish all sessions’ MIMO transmissions is . Step 3: Cooperative Decoding: Now that each MT has destination clusters, after Step 2, every cluster receives MIMO transmissions.8 For each MIMO transmis￾sion, every node in a destination cluster obtains an observation that the bits are transmitted from the source node. To decode the original bits, all nodes in the destination cluster must quantify each observation into bits, where is a constant. After that, each node conveys the bits to all destination nodes in the cluster. Obviously, this procedure can be formulated as an . After all observa￾tion results reach the destination nodes, they can decode the transmitted bits. Assume that an aggregate multicast throughput is achievable at layer w.h.p., where , , and , then the can be solved within time slots. Note that each cluster receives MIMO transmissions and needs to perform this de￾coding process for each transmission. By utilizing the 9-TDMA scheme, we can finish all multicast sessions in rounds. Consequently, Step 3 costs time slots. Finally, the transmission should be performed at the bottom layer. Since every node broadcasts its data in each session, all destination nodes can receive one bit, and a multicast session can be completed in one time slot. 2) Division of the Network: By minimizing the total time cost during the three steps at layer , we present the throughput￾optimal division of the network. Lemma 4.5: Given independently and uniformly dis￾tributed destination nodes in the network at layer , the number of destination clusters is given by when when . Proof: Let be a random variable if cluster contains at least one destination node else then . Since the destination nodes at layer are uniformly and independently distributed in clusters, the probability that a destination node is in cluster is , and the probability that none of the destination nodes is in cluster is , which gives Since is a sequence of i.i.d. random variables, using the law of large numbers, we obtain w.h.p. that when (6) Consequently, the number of clusters that contain at least one destination node is . If , 8This is valid under Assumption 3 in Lemma 4.7, which we present later

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. WANG et al:MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION 7 ene(1-(1)=()w.h.p.;if=(n),timal result cannot be achieved Thus,the maximum achiev- k=r(（1-（1-）=6(nr)whp able throughput in Case 1 is n when we choose Lemma 4.6:When Assumption 2:mn=O((ne.))holds ni-1=na/ki,which is not superior to the throughput at the for all2≤i≤h with a constant p2>0: (i-1)th layer. （(aifk=(ne log ne),then:-l=6(年）w.hp In Case 2,the throughput in (9)can be (b)if ki=O(ne;log ne,)then ki1 =O(log ne:w.h.p. In Lemma 4.7,we use l;to denote the number of destina- T(n,k)=⊙ nini-1 (11) tion sets in each cluster.More specifically,let each source node Vniki/ni-1+nki choose a set of destination nodes in the network,and l;be the number of source nodes that choose at least one destination node which is optimized when ni-1 =()Since the in- in the layer i of the network.We havel=mi/for equality ()0,Assumption 1 is also satisfied. which is optimized when().However,since b)Then,we consider the number of destination nodes at each Case 1 requires that ne:=O(),or ni-1=(),the op- layer.By Lemma 4.6 The network division is equivalent to power control.By optimal network k O(1og(是)▣)：1≤i≤h-2 division,a node does not need to transmit with full power.This can well solve the problem of limited power. O(logk(共)m÷),i=h-1

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. WANG et al.: MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION 7 w.h.p.; if , w.h.p. Lemma 4.6: When Assumption 2: holds for all with a constant : (a) if , then w.h.p.; (b) if , then w.h.p. In Lemma 4.7, we use to denote the number of destina￾tion sets in each cluster. More specifically, let each source node choose a set of destination nodes in the network, and be the number of source nodes that choose at least one destination node in the layer of the network. We have for MMM/DMM, in which is the number of multicast sessions, and for CMMM/CDMM, in which is the number of converge multicast frames. Lemma 4.7: When , the number of destination sets at the th layer is: (a) when Assumption 3: is satisfied, then w.h.p.; (b) when , then w.h.p. Now we are ready to present our network division scheme. Lemma 4.8: When for a small , the number of nodes at each layer to achieve optimal throughput with the MMM strategy is . (7) Proof: Still, we consider the three steps at layer . When Assumptions 1 and 3 are satisfied, combining the three steps, the total time to complete multicast sessions is (8) Since the time cost of Step 3 is always higher than that of Step 1 in order of magnitude, the throughput at layer is given by (9) To optimize the network division at layer , we consider two cases: and .9 We suppose Assumption 2 is satisfied, then the properties of two cases are summarized as follows, according to Lemmas 4.5 and 4.6. Case 1) When , then , . Case 2) When , then , . In Case 1, the throughput in (9) can be (10) which is optimized when . However, since Case 1 requires that , or , the op- 9The network division is equivalent to power control. By optimal network division, a node does not need to transmit with full power. This can well solve the problem of limited power. timal result cannot be achieved. Thus, the maximum achiev￾able throughput in Case 1 is when we choose , which is not superior to the throughput at the th layer. In Case 2, the throughput in (9) can be (11) which is optimized when . Since the in￾equality holds, we can achieve a throughput of , which is better than the throughput at the th layer as . Therefore, we can improve the throughput by adopting Case 2. At the bottom layer, the aggregate multicast throughput is . When network is divided in the optimal way at each layer, the relationship among , and throughput in each layer is as follows: . . . (12) Substituting into (12), we obtain the results in (7). This finishes the proof. Remark 4.2: Now, the number of sessions at each layer is . Under this condition, when (7) is satisfied, the time spent at each layer is in the same order of mag￾nitude, i.e., it takes the same amount of time for the broadcast transmission at the bottom layer and for the multihop MIMO transmission at every other layer. However, when does not exactly hold, the throughput of the network is de￾termined by the layer with the maximum number of sessions . This conclusion also holds for the CMMM strategy, with denoting the number of frames at each layer. To get the precise throughput result of the MMM strategy, we must further calculate the number of multicast sessions at each layer. 3) Verification of Assumptions: To calculate the accurate throughput result, there are three conditions that need justifica￾tion. We now consider these factors under (7). a) First we consider Assumptions 1 and 2. With the multicast traffic pattern described earlier, the number of multicast sessions at the top layer is , which is smaller than for , thus Assumption 2 holds. As for Assumption 1, it is obvious that for , and if at the top layer. Since we only consider the case for a small , Assumption 1 is also satisfied. b) Then, we consider the number of destination nodes at each layer. By Lemma 4.6

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING This will change the number of sessions to Step 2:Multihop MIMO Transmission:After Step 1. all source nodes in the chosen subcluster have distributed mh =n their nn bits to the nodes in the same cluster.To use mh-1 =nk multihop MIMO transmission,we must build MTs, h-I with each corresponding to a source node.According to mh-2 =nk log Lemma 4.4 and the 9-TDMA scheme,Step 2 can be completed hck）time slots. imΘnk-2Vnh-i mi =nk logh-2 ( Step 3:Cooperative Decoding:Each destination cluster (13) works in parallel and decodes the original n2 bits from MIMO observations.The decoding process can be formulated c)In our scheme,Lemma 4.7(a)must be applied recursively, as a CMP(nh-1,mh-1;kh-1),with mh-1 nh-2ken.This and we have to ensure Assumption 3 is satisfied at each conclusion is based on Assumption 3. recursion.Recall that the number of destination sets is 1)Solution to Converge Multicast Problem:We start by mi mi studying a two-layer network.Given a CMP(n2,m2,k2),we l:= Π=+1ne, (n/) divide the network into clusters of n nodes,where a frame of transmission includes the following steps. Step 1:After the division of clusters,there are desti- combining (13),we obtain l;=(()).Note that nation clusters.Since all n2 nodes must send one bit to k2 des- in our network division =日()m可) tination nodes,all nclusters must act as source clusters and for2≤i≤h-l,thus与=R(glog会)，and transmit to ke destination clusters using MIMO. Assumption 3 is satisfied for all layers. For each of the nez source clusters,build an MT connecting 4)Calculation of Throughput:From the analysis above, the source and destination clusters.By Lemma 4.4,we can finish plus the conclusion of Remark 4.2,the throughput is deter- all the transmissions on MTs inslots.Considering mined by the number of sessions at the bottom layer because m1 maxisish-1{mi}nk log"-2().Followed by (9), ma frames,the time cost in Step 1 isma the throughput is Step 2:After a destination cluster receives a MIMO trans- mission,all n nodes must quantify the observation and con- I(n,k)= log-(-2) (14) verge them to the destination nodes in the cluster,which is a converge multicast problem.When Assumption 3 is satisfied, Then,the following theorem naturally holds. there are m()frames that choose a cluster as the co Theorem 4.2:By using the MMM strategy,we can achieve destination cluster.Thus,there is a CMP(n,mk)to handle an aggregate throughput of in each cluster. Since the problem in Step 2 is also a converge multicast T(n,k)= 10g(h-2) problem,our two-step scheme can be applied recursively to (15) construct a hierarchical solution.In our CMMM strategy,we build an(h-1)-layer strategy for Step 3,plus the top layer, hence there is a total of h layers. C.Throughput Analysis With the CMMM At last,we specify the transmission of the bottom layer.For Consider three top layers h,h-1,and h-2,with layer each frame,every node broadcasts its data,and all destination h-1 and h-2 termed as“clusters”and“subclusters,”respec- nodes can receive one bit per time slot.The frame can be com- tively.We organize "rounds of transmission,and choose a pleted in n time slots. h三2 subcluster in every cluster for each round (source nodes 2)Division of the Network:Similar to MMM strategy,we nh-1 per round).Only nodes in the chosen subclusters serve as source first present the throughput-optimal network division. Lemma 4.9:When k =O(n-)for a small e>0,the nodes at each round,and each round is divided into three steps. number of nodes at each layer to achieve optimal throughput Step I:Preparing for Cooperation:Each source node in the in the CMMM strategy is chosen subclusters must deliver n1 bits to nodes in the same cluster for cooperation,one bit for each node.This includes two substeps. ni= ()号，i<h (16) Substep I:MIMO Transmissions:In a specific cluster, i=h. each node acts as a destination node.For each destination node d,the chosen subcluster uses direct MIMO trans- Proof:We consider two layers i and i-1,with 2<i< missionlo to communicate with the subcluster where d h-1.As the CMP(ni1,mi1,i_1)at the (i-1)th layer can locates.This takes n time slots to accomplish. be solved in (min)time slots,and we assume that Substep 2:Cooperate Decoding:All subclusters in the net- Assumptions 1-3 are satisfied as in the analysis of the MMM work perform decoding in parallel,which makes this sub- strategy,we then have mi-1=(mike,)Still,we consider step a CMP(nh-2,nn-2,1). two cases:ne,=O(ki)and ne:=(ki),with the properties still holding. Because the time cost in Step 1 is not the dominating factor on throughput, this will not affect the result.The reason we do not use multihop is that the traffic Case 1)When ne =O(ki),then ke;=e(nc.)ki-1 is not uniformly distributed and is hard to schedule by TDMA scheme. ()

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 8 IEEE/ACM TRANSACTIONS ON NETWORKING This will change the number of sessions to . . . (13) c) In our scheme, Lemma 4.7(a) must be applied recursively, and we have to ensure Assumption 3 is satisfied at each recursion. Recall that the number of destination sets is combining (13), we obtain . Note that in our network division for , thus , and Assumption 3 is satisfied for all layers. 4) Calculation of Throughput: From the analysis above, plus the conclusion of Remark 4.2, the throughput is deter￾mined by the number of sessions at the bottom layer because . Followed by (9), the throughput is (14) Then, the following theorem naturally holds. Theorem 4.2: By using the MMM strategy, we can achieve an aggregate throughput of (15) C. Throughput Analysis With the CMMM Consider three top layers , , and , with layer and termed as “clusters” and “subclusters,” respec￾tively. We organize rounds of transmission, and choose a subcluster in every cluster for each round ( source nodes per round). Only nodes in the chosen subclusters serve as source nodes at each round, and each round is divided into three steps. Step 1: Preparing for Cooperation: Each source node in the chosen subclusters must deliver bits to nodes in the same cluster for cooperation, one bit for each node. This includes two substeps. • Substep 1: MIMO Transmissions: In a specific cluster, each node acts as a destination node. For each destination node , the chosen subcluster uses direct MIMO trans￾mission10 to communicate with the subcluster where locates. This takes time slots to accomplish. • Substep 2: Cooperate Decoding: All subclusters in the net￾work perform decoding in parallel, which makes this sub￾step a . 10Because the time cost in Step 1 is not the dominating factor on throughput, this will not affect the result. The reason we do not use multihop is that the traffic is not uniformly distributed and is hard to schedule by TDMA scheme. Step 2: Multihop MIMO Transmission: After Step 1, all source nodes in the chosen subcluster have distributed their bits to the nodes in the same cluster. To use multihop MIMO transmission, we must build MTs, with each corresponding to a source node. According to Lemma 4.4 and the 9-TDMA scheme, Step 2 can be completed in time slots. Step 3: Cooperative Decoding: Each destination cluster works in parallel and decodes the original bits from MIMO observations. The decoding process can be formulated as a , with . This conclusion is based on Assumption 3. 1) Solution to Converge Multicast Problem: We start by studying a two-layer network. Given a , we divide the network into clusters of nodes, where a frame of transmission includes the following steps. Step 1: After the division of clusters, there are desti￾nation clusters. Since all nodes must send one bit to des￾tination nodes, all clusters must act as source clusters and transmit to destination clusters using MIMO. For each of the source clusters, build an MT connecting the source and destination clusters. By Lemma 4.4, we can finish all the transmissions on MTs in slots. Considering frames, the time cost in Step 1 is . Step 2: After a destination cluster receives a MIMO trans￾mission, all nodes must quantify the observation and con￾verge them to the destination nodes in the cluster, which is a converge multicast problem. When Assumption 3 is satisfied, there are frames that choose a cluster as the destination cluster. Thus, there is a to handle in each cluster. Since the problem in Step 2 is also a converge multicast problem, our two-step scheme can be applied recursively to construct a hierarchical solution. In our CMMM strategy, we build an -layer strategy for Step 3, plus the top layer, hence there is a total of layers. At last, we specify the transmission of the bottom layer. For each frame, every node broadcasts its data, and all destination nodes can receive one bit per time slot. The frame can be com￾pleted in time slots. 2) Division of the Network: Similar to MMM strategy, we first present the throughput-optimal network division. Lemma 4.9: When for a small , the number of nodes at each layer to achieve optimal throughput in the CMMM strategy is . (16) Proof: We consider two layers and , with . As the at the th layer can be solved in time slots, and we assume that Assumptions 1–3 are satisfied as in the analysis of the MMM strategy, we then have . Still, we consider two cases: and , with the properties still holding. Case 1) When , then ,

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination WANG et al.:MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION 9 Case 2)When ne:=(ki),then ke;=e(i),ki-1 same as that for the MMM strategy,so we omit the O(1ogne.)=Θ(1). details here. In case 1,the CMP(ni,mi,ki)can be solved in b)Then,we consider the number of destination nodes at each h- layer.Since mh1=()and ki1 log ne,for +m-1n11=+m,nn- 2≤i≤h ni-1 ni-1 (17) time slots.The result is optimized by choosing=() However,(<which contradicts with the require- ment n=()ofCase 1.Thus,the minimum time to solve the CMP(ni,mi,)is min,which is achieved when ni1=ni/ki.This is not superior to the solving time at the (i-1)th layer. (22) In Case 2,the CMP(ni,mi,k:)can be solved in c)In our scheme,Lemma 4.7(a)must be applied recursively. We need to ensure that Assumption 3 is satisfied at each ke+m-1n-1-1=mi\ niki +m:k:ng-1(18) recursion.Recall that the number of destination sets is 7-1 -1 li= mi m time slots.The result is optimized by choosing ni1 Π+1ne,《(n/kA平 (关)中.Since(e)2a-<装holds,.CMP(n:m,k)can be solved in time slots,which is better tham and the equation still holds under the network division the solving time at the ith layer.Therefore,we can reduce the (16).Combining (22),we obtain l=2(())= solving time by adopting Case 2. (om1 for3≤i≤h2l,and At the bottom layer,a frame can be finished in n time slots. Assumption 3 is satisfied.However,when i=2 When we divide the network in the optimal way at each layer, the relationship of n;,k;and the solving time in each layer from =()1g-() I to h-1 is shown as follows: 41=M号，宁器 Comparing 12 to ()we find there exists a threshold!1 (N-3X2h-12 kh=O(n齐l0gn）=白(nt). (23) na=ng,nlsk5 2=n,n/3/3 (19) Whenk=(kth),Assumption 3 holds for layer 2;other- wise it does not.Thus the number of frames at the bottom layer is Thus,the minimum solving time of CMP(nh-1;mh1:1) is6(m-1nTk） ()兰1og(), whenk=O(kth), With all procedures put together,we deliver n-1x nh-2 x m1= 2h- (24) bits to their destination nodes in k(失)号log-2(关)，when:=2(kh). 4)Calculation of Throughput:With the analysis above +m-2n宁 (20) and the conclusion of Remark 4.2,the throughput is deter- nk-1+nh-2° nh-2 h-1 mined by the number of frames at the bottom layer because m1 maxisish-1{mi).Thus,followed by (21)and (24),the time slots at every round of transmission.Therefore,the aggre- throughput is given by gate throughput is h-1 X 1h-2X mt T(n,k)= ∫o(n六号log1),when=O(kh) e(爱)号log-2)),when/=2(k 2h4 nk-1+nh-2+n-2Vh- /+m-2knk (25) based on which we have the following theorem. (21) Theorem 4.3:With the CMMM strategy,we can achieve an which can be optimized by choosing(Com- aggregate throughput of bining with(19),we obtain(16).This finishes the proof. ◆ 3)Verification of Assumptions:Before presenting the 日(n导k六log1),when=O(m本) throughput result,the three conditions in Section IV-B.3 also T(n,&) need justification. o(发)号logh-2)),when=(n六) (26) a)To begin with,the verification procedure of Assumptions 1 and 2 and the assumptions are the We will discuss the influence of it in Section VI-C

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. WANG et al.: MULTICAST PERFORMANCE WITH HIERARCHICAL COOPERATION 9 Case 2) When , then , . In case 1, the can be solved in (17) time slots. The result is optimized by choosing . However, , which contradicts with the require￾ment of Case 1. Thus, the minimum time to solve the is , which is achieved when . This is not superior to the solving time at the th layer. In Case 2, the can be solved in (18) time slots. The result is optimized by choosing . Since holds, can be solved in time slots, which is better than the solving time at the th layer. Therefore, we can reduce the solving time by adopting Case 2. At the bottom layer, a frame can be finished in time slots. When we divide the network in the optimal way at each layer, the relationship of , and the solving time in each layer from 1 to is shown as follows: . . . (19) Thus, the minimum solving time of is . With all procedures put together, we deliver bits to their destination nodes in (20) time slots at every round of transmission. Therefore, the aggre￾gate throughput is (21) which can be optimized by choosing . Com￾bining with (19), we obtain (16). This finishes the proof. 3) Verification of Assumptions: Before presenting the throughput result, the three conditions in Section IV-B.3 also need justification. a) To begin with, the verification procedure of Assumptions 1 and 2 and the assumptions are the same as that for the MMM strategy, so we omit the details here. b) Then, we consider the number of destination nodes at each layer. Since and for . . . (22) c) In our scheme, Lemma 4.7(a) must be applied recursively. We need to ensure that Assumption 3 is satisfied at each recursion. Recall that the number of destination sets is and the equation still holds under the network division (16). Combining (22), we obtain for , and Assumption 3 is satisfied. However, when Comparing to , we find there exists a threshold11 (23) When , Assumption 3 holds for layer 2; other￾wise it does not. Thus the number of frames at the bottom layer is when , when . (24) 4) Calculation of Throughput: With the analysis above and the conclusion of Remark 4.2, the throughput is deter￾mined by the number of frames at the bottom layer because . Thus, followed by (21) and (24), the throughput is given by when when (25) based on which we have the following theorem. Theorem 4.3: With the CMMM strategy, we can achieve an aggregate throughput of when when . (26) 11We will discuss the influence of it in Section VI-C

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination. 10 IEEE/ACM TRANSACTIONS ON NETWORKING D.Broadcast Case MT at layer i is( niki Using the 9-TDMA scheme, So far,we have only proven the throughput result when k= we can accomplish白(_ hops per time slot,and thus O(n1)for an arbitrarily small e>0.Another case is (n),which we refer to as the broadcast case. can complete the second step inB: /:k）time slots. According to Theorem 4.2,the network cannot be divided 3)For Step 3,the traffic loads are nik;multicast sessions into more than (ni)clusters at layer i.Therefore,we can only in every cluster.Recall that we use D(ni1,:-1)to de- note the amount of time to finish the transmission of n divide the network as nc;=O(k:)for the broadcast case.This multicast sessions at layer i-1;therefore,Step 3 takes division has been discussed in the proof of Lemmas 4.8 and 4.9(see Case 1),and the throughput performance does not in- kiD(ni1,i1)time slots. These three steps cost D(ni,k:)time slots,thus crease as the number of layers becomes larger.Consequently, there is no gain on the throughput when utilizing our coopera- tive scheme in the broadcast case,and the throughput results in D(n,k)=Θ niki B +k:D(n-1,ki-1) (29) Theorems 4.2 and 4.3 still hold. 7i1 In the rest of this paper,we do not distinguish=O(n) and =(n)because the conclusions hold for both cases. where B,=()发for 1≤i≤For the bottom--lyer transmission scheme,D(n1,)=n1=().Substituting E.Throughput Analysis With Direct MIMO Transmission these into (29)and iterating the equation fori=1.2,...,h,we The DMM and CDMM operate in the similar way to the then obtain the final result MMM and CMMM,respectively.The only difference is that we use direct MIMO transmission in the former two strategies. D,)=6(m学k-号普学 (30) Due to the similarity,we only present some important conclu- sions and results under the DMM and CDMM strategies. Remark 5.1:According to the result above,the delay is de- In the DMM and CDMM,we perform direct MIMO trans- termined by the number of nodes at each layer,and the trans- missions at each layer,which takes one time slot for each source mission time at the top layer is the dominating factor on delay, cluster.This difference leads to another optimized network di- which implies that we can just calculate the time cost at the top vision for both DMM and CDMM layer. Combining(15)with(30),we obtain the delay-throughput ()，i<h (27) tradeoff i=h. Dm,k)/T(m,)=日(n学k学1og-2 Under this division,the throughput results are given by the (31) following theorem 2)Delay Analysis With the CMMM:In the CMMM strategy, Theorem 4.4:With either the DMM or the CDMM strategy, the delay is the amount of time a transmission round spends. we can achieve an aggregate throughput and it is calculated in the throughput analysis.The time cost to log-(h-1) finish each round is given by (20).By Lemma 4.9,substituting T(n,k)= 28) all parameters with n and k:in(20),we obtain the delay D(n,k)= 日（货）号1og) when=O(th) V.DELAY AND ENERGY CONSUMPTION ANALYSIS 日(m号klog-2),whenk=(k (32) which is simplified as A.Delay Analysis 1)Delay Analysis With the MMM:As mentioned in when=O(n亦) D(n.k)= 6()号) (33) Section IV,delay performance of the MMM is poor.Intu- 6(n熟=号k与)，when k:=2(n亦) itively,at the ith layer,a source node must divide the data into m-1 parts of the same size and distribute to other nodes for Combining(33)with(26),we find the delay-throughput tradeoff cooperation.This division is repeated at each layer.Since the IS smallest part of data at the bottom later is one bit,the minimum size of data packets at layer i is Bi=nj bits. D(n,k) 日(k-1log), when=O(n) For the ith layer,let D(ni,ki)be the average time to accom- T(n,k) ⊙(k)厂log--2),when=2(n亦)， plish a multicast session for each of n;nodes.To analyze the (34) delay,we consider the three steps separately. 3)Delay Analysis With the DMM:The delay analyzing pro- 1)For Step 1,each source node distributes B;bits to other cedure of DMM is similar to that of MMM.Thus,we can easily nodes within the same cluster.Because in this step,all obtain the delay result by the conclusion of Remark 5.1. traffic is unicast,the distribution process takes D(ni-1,1) time slots.We ignore the time spent in Step I since it is (ethe及 smaller than that in Step 3. bit/s using MIMO.Then,we derive the delay as 2)For Step 2,to transmit B;bits for all n;source nodes,there are niBi/nMTs at layer i.The number of hops on each D(n,k=(nk (35)

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 10 IEEE/ACM TRANSACTIONS ON NETWORKING D. Broadcast Case So far, we have only proven the throughput result when for an arbitrarily small . Another case is , which we refer to as the broadcast case. According to Theorem 4.2, the network cannot be divided into more than clusters at layer . Therefore, we can only divide the network as for the broadcast case. This division has been discussed in the proof of Lemmas 4.8 and 4.9 (see Case 1), and the throughput performance does not in￾crease as the number of layers becomes larger. Consequently, there is no gain on the throughput when utilizing our coopera￾tive scheme in the broadcast case, and the throughput results in Theorems 4.2 and 4.3 still hold. In the rest of this paper, we do not distinguish and because the conclusions hold for both cases. E. Throughput Analysis With Direct MIMO Transmission The DMM and CDMM operate in the similar way to the MMM and CMMM, respectively. The only difference is that we use direct MIMO transmission in the former two strategies. Due to the similarity, we only present some important conclu￾sions and results under the DMM and CDMM strategies. In the DMM and CDMM, we perform direct MIMO trans￾missions at each layer, which takes one time slot for each source cluster. This difference leads to another optimized network di￾vision for both DMM and CDMM . (27) Under this division, the throughput results are given by the following theorem. Theorem 4.4: With either the DMM or the CDMM strategy, we can achieve an aggregate throughput (28) V. DELAY AND ENERGY CONSUMPTION ANALYSIS A. Delay Analysis 1) Delay Analysis With the MMM: As mentioned in Section IV, delay performance of the MMM is poor. Intu￾itively, at the th layer, a source node must divide the data into parts of the same size and distribute to other nodes for cooperation. This division is repeated at each layer. Since the smallest part of data at the bottom later is one bit, the minimum size of data packets at layer is bits. For the th layer, let be the average time to accom￾plish a multicast session for each of nodes. To analyze the delay, we consider the three steps separately. 1) For Step 1, each source node distributes bits to other nodes within the same cluster. Because in this step, all traffic is unicast, the distribution process takes time slots. We ignore the time spent in Step 1 since it is smaller than that in Step 3. 2) For Step 2, to transmit bits for all source nodes, there are MTs at layer . The number of hops on each MT at layer is . Using the 9-TDMA scheme, we can accomplish hops per time slot, and thus can complete the second step in time slots. 3) For Step 3, the traffic loads are multicast sessions in every cluster. Recall that we use to de￾note the amount of time to finish the transmission of multicast sessions at layer ; therefore, Step 3 takes time slots. These three steps cost time slots, thus (29) where for . For the bottom-layer transmission scheme, . Substituting these into (29) and iterating the equation for , we then obtain the final result (30) Remark 5.1: According to the result above, the delay is de￾termined by the number of nodes at each layer, and the trans￾mission time at the top layer is the dominating factor on delay, which implies that we can just calculate the time cost at the top layer. Combining (15) with (30), we obtain the delay-throughput tradeoff (31) 2) Delay Analysis With the CMMM: In the CMMM strategy, the delay is the amount of time a transmission round spends, and it is calculated in the throughput analysis. The time cost to finish each round is given by (20). By Lemma 4.9, substituting all parameters with and in (20), we obtain the delay when when (32) which is simplified as when when . (33) Combining (33) with (26), we find the delay-throughput tradeoff is when when . (34) 3) Delay Analysis With the DMM: The delay analyzing pro￾cedure of DMM is similar to that of MMM. Thus, we can easily obtain the delay result by the conclusion of Remark 5.1. For DMM, each time a source node must transmit bits. The transmission rate at the top layer is bit/s using MIMO. Then, we derive the delay as (35)