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 <j<k} other than v;in the deployment square as its destination nodes We define a multicast session as the collection of transmissions B.Intracluster Communication from one source node to k:destination nodes and use MP(n,k) To decode MIMO transmissions,the destination nodes in to denote an n-session multicast problem with each node acting each destination cluster must observe results from all other as a source node for a session. nodes in the same cluster.Since each cluster may act as a We then define another traffic that helps our analysis. destination cluster of multiple source clusters,there are several Converge Multicast Traffic:We randomly and independently sets of destination nodes in it.For each set,every node in the choose a set of k:nodes U:=u1 <j<k}as destinations. cluster sends one identical bit to all nodes in the set.This traffic We use Knuth's notation in this paper.Also,we use f(n)=(g(n))to can be seen as multicast,but considering the "converge"nature indicate f(n)=O(n'g(n))and f(n)=(n-"g(n)),for any e >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).]1< Step 2)The nodes in the source cluster transmit simultane- i,j<n}is a collection of independently and identically dis- ously by implementing distributed MIMO transmis- tributed(i.i.d.)random processes.The parameters G and >2 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;(1<i<) all its data to other nodes in the same cluster,with mi—bits and d is larger thanw.hp.With this fact,we obtain for each.As there are n;source nodes in each cluster,the traffic load is ()bits.Since the data exchanges only ni λM,)≤log（1+ GP a(1+)+1 Pi logn involve intracluster communication,they can work according No to the 9-TDMA scheme.We divide time into slots:at each time slot,let the neighboring eight clusters keep silent when the w.h.p.for some constant pi independent of n and k.The the- ◆ centric cluster is exchanging data.According to the channel orem then follows. model(2).we assume that the received interference signal /,( is a collection of uncorrelated zero-mean stationary and ergodic B.Throughput Analysis With MMM random processes with power upper-bounded by a constant.7 To ensure successful MIMO transmissions,each cluster must This assumption is also adopted in the proof of Lemma 3.1 [2] have the same number of nodes.The following lemma ensures Thus,the power of destructive interference is bounded,en- the number of nodes in each cluster at layer 2<i<h has the abling clusters to operate simultaneously according to the same order.For simplicity,we consider the number of nodes in 9-TDMA scheme,which is ensured by Lemma 4.3. each cluster is exactly ni1. Lemma 4.3:By the 9-TDMA scheme,when a>2,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)西 <ef品 node in subsquares that are numbered (t mod 9)+1 is allowed to transmit packets. In a slot,if a node inside the subsquare s;is allowed to with f(6)=(1+6)log(1+6)-6 transmit to another node inside s;,those nodes that may in- terfere with the current transmission must be located along ∑x≤1- the perimeters of concentric subsquares centered at s:.The ne. interfering nodes can be grouped based on their distances to i1 s;such that the jth group contains 8j interfering nodes or less (near the boundary of the network)and the shortest distance When ni=2(ne;log ne:） from the receiver in s;is(3.j-1)vA,where A is the area of the subsquare.Assuming that all nodes use the same transmission ≥6% e÷9一0 power P(n,k),with the power propagation model in (1),the cumulative interference at subsquare si,denoted by Is,can be bounded by if n-+o0.Here,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