Delay and Capacity Tradeoff Analysis for MotionCast

1354 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.19.NO.5.OCTOBER 2011 Delay and Capacity Tradeoff Analysis for MotionCast Xinbing Wang,Member;IEEE,Wentao Huang,Shangxing Wang,Jinbei Zhang,and Chenhui Hu Abstract-In this paper,we define multicast for an ad hoc net- for other mobile nodes.With the fast progress of computing and work through nodes'mobility as MotionCast and study the delay wireless networking technologies,there are increasing interests and capacity tradeoffs for it.Assuming nodes move according and uses of MANETs.Examples where they may be employed to an independently and identically distributed (i.i.d.)pattern and each desires to send packets to k distinctive destinations,we are the establishment of connections among handheld devices compare the delay and capacity in two transmission protocols: or between vehicles. one uses 2-hop relay algorithm without redundancy;the other Multicast is a fundamental service for supporting infor- adopts the scheme of redundant packets transmissions to improve mation communication and collaborative task completion delay while at the expense of the capacity.In addition,we obtain among a group of users and enabling cluster-based system the maximum capacity and the minimum delay under certain constraints.We find that the per-node delay and capacity for the design in a distributed environment [2].Different from in the 2-hop algorithm without redundancy are (1/k)and (nlog k). wired networks.multicast in MANETs is faced with a more respectively;for the 2-hop algorithm with redundancy,they are challenging environment.In particular,one needs to deal with (1/kvnlogk)and (Vnlog k),respectively.The capacity node mobility and thus frequent and possible drastic topology of the 2-hop relay algorithm without redundancy is better than the multicast capacity of static networks developed by Li [IEEE/ACM changes [1].Numerous protocols have then been proposed Trans.Netw.,vol.17,no.3,pp.950-961,Jun.2009]as long as k is for multicast in MANETs.They include traditional tree-or strictly less than n in an order sense,while when k=(n),mo- mesh-based protocols [3]-[6],stateless protocols [7],[8]. bility does not increase capacity anymore.The ratio between delay flooding-based protocols [9].location-based protocols [10]. and capacity satisfies delay/rate O(nklog k)for these two and hybrid protocols [11].Some of them have already pointed protocols,which are both smaller than that of directly extending out that because links can be shared by several destinations, the fundamental tradeoff for unicast established by Neely and Modiano [IEEE Trans.Inf.Theory,vol.51,no.6,pp.1917-1937, multicast is beneficial to improve performance compared to Jun.2005]to multicast,i.e.,delay/rate O(nk2).More im- multiple unicast. portantly,we have proved that the fundamental delay-capacity However,the feasible performance gains,in terms of both tradeoff ratio for multicast is delay/rate O(nlog k),which throughput capacity and delay,that can be achieved by ex- would guide us to design better routing schemes for multicast. ploiting multicast,as well as the resulting scaling laws in a Index Terms-Capacity,delay,multicast,scaling law. network with an increasing number of nodes,have not been investigated so far.In this paper,we bridge the theoretical analysis of fundamental scaling laws in multicast mobile ad hoc I.INTRODUCTION networks with the insights already gained through practical protocol development.By doing so,we provide a theoretical MOBILE ad hoc network (MANET)consists of a collec- foundation to the design of intelligent communication schemes tion of wireless mobile nodes dynamically forming a tem- that exploit multicast,analytically showing the potential of porary network without the support of any network infrastruc- such schemes in terms of capacity delay tradeoffs. ture or centralized control.In these networks,nodes often op- The theoretical analysis of scaling laws in wireless networks erate not only as sources,but also as relays,forwarding packets is initiated by the seminal work of Gupta and Kumar [4].Sev- eral interesting studies have later emerged aimed at establishing Manuscript received October 09,2009;revised August 13,2010 and the fundamental scaling laws for networks with multicast traffic November 26,2010;accepted January 16,2011:approved by IEEE/ACM Li et al.[3],[22],[23]study the capacity of a static random TRANSACTIONS ON NETWORKING Editor B.N.Levine.Date of publication wireless ad hoc network for multicast where each node sends March 03,2011;date of current version October 14,2011.This work was sup- ported by the National Basic Research Program of China(973 Program)under packets to k-1 destinations.They show that the per-node mul- Grant 2011CB302701,NSF China under Grant 60832005,the China Ministry ticast capacity is ( of Education Fok Ying Tung Fund under Grant 122002,and a Qualcomm gn)whenO(on).and is Research Grant.An earlier version of this paper appeared in the Proceedings ()when).Their results generalize previous ca- of the ACM International Symposium on Mobile Ad Hoc Networking and pacity bounds on unicast [4]and broadcast [5].Under a more Computing (MobiHoc),New Orleans,LA,May 18-21,2009. X.Wang.W.Huang.S.Wang,and J.Zhang are with the Department general Guassian channel model,multicast capacity is investi- of Electric Engineering.Shanghai Jiao Tong University.Shanghai 200240. gated in [6]using percolation theory.Jacquet et al.7]consider China (e-mail:xwang8@sjtu.edu.cn:wht@sjtu.edu.cn:wsx@sjtu.edu.cn: multicast capacity by accounting the ratio of the total number zib@sjtu.edu.cn). C.Hu was with the Department of Electric Engineering,Shanghai Jiao Tong of hops for multicast and the average number of hops for uni- University,Shanghai 200240,China.He is now with the School of Engineering cast.Shakkottai et al.[8]propose a comb-based architecture for and Applied Sciences,Harvard University,Cambridge,MA 02138 USA multicast routing that achieves the upper bound for capacity in (e-mail:hch@sjtu.edu.cn). an order sense. Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. In contrast to the discussed static networks,Gossglauser and Digital Object Identifier 10.1109/TNET.2011.2109042 Tse [9]for the first time have shown that a constant unicast 1063-6692/S26.00©2011EEE

1354 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 5, OCTOBER 2011 Delay and Capacity Tradeoff Analysis for MotionCast Xinbing Wang, Member, IEEE, Wentao Huang, Shangxing Wang, Jinbei Zhang, and Chenhui Hu Abstract—In this paper, we define multicast for an ad hoc net￾work through nodes’ mobility as MotionCast and study the delay and capacity tradeoffs for it. Assuming nodes move according to an independently and identically distributed (i.i.d.) pattern and each desires to send packets to distinctive destinations, we compare the delay and capacity in two transmission protocols: one uses 2-hop relay algorithm without redundancy; the other adopts the scheme of redundant packets transmissions to improve delay while at the expense of the capacity. In addition, we obtain the maximum capacity and the minimum delay under certain constraints. We find that the per-node delay and capacity for the 2-hop algorithm without redundancy are ￾  and ￾  , respectively; for the 2-hop algorithm with redundancy, they are    and ￾  , respectively. The capacity of the 2-hop relay algorithm without redundancy is better than the multicast capacity of static networks developed by Li [IEEE/ACM Trans. Netw., vol. 17, no. 3, pp. 950–961, Jun. 2009] as long as is strictly less than in an order sense, while when ￾ , mo￾bility does not increase capacity anymore. The ratio between delay and capacity satisfies delay/rate   for these two protocols, which are both smaller than that of directly extending the fundamental tradeoff for unicast established by Neely and Modiano [IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1917–1937, Jun. 2005] to multicast, i.e., delay/rate ￾. More im￾portantly, we have proved that the fundamental delay–capacity tradeoff ratio for multicast is delay/rate  , which would guide us to design better routing schemes for multicast. Index Terms—Capacity, delay, multicast, scaling law. I. INTRODUCTION A MOBILE ad hoc network (MANET) consists of a collec￾tion of wireless mobile nodes dynamically forming a tem￾porary network without the support of any network infrastruc￾ture or centralized control. In these networks, nodes often op￾erate not only as sources, but also as relays, forwarding packets Manuscript received October 09, 2009; revised August 13, 2010 and November 26, 2010; accepted January 16, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor B. N. Levine. Date of publication March 03, 2011; date of current version October 14, 2011. This work was sup￾ported 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, and a Qualcomm Research Grant. An earlier version of this paper appeared in the Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), New Orleans, LA, May 18–21, 2009. X. Wang, W. Huang, S. Wang, and J. Zhang are with the Department of Electric Engineering, Shanghai Jiao Tong University, Shanghai 200240, China (e-mail: xwang8@sjtu.edu.cn; wht@sjtu.edu.cn; wsx@sjtu.edu.cn; zjb@sjtu.edu.cn). C. Hu was with the Department of Electric Engineering, Shanghai Jiao Tong University, Shanghai 200240, China. He is now with the School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138 USA (e-mail: 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.2109042 for other mobile nodes. With the fast progress of computing and wireless networking technologies, there are increasing interests and uses of MANETs. Examples where they may be employed are the establishment of connections among handheld devices or between vehicles. Multicast is a fundamental service for supporting infor￾mation communication and collaborative task completion among a group of users and enabling cluster-based system design in a distributed environment [2]. Different from in the wired networks, multicast in MANETs is faced with a more challenging environment. In particular, one needs to deal with node mobility and thus frequent and possible drastic topology changes [1]. Numerous protocols have then been proposed for multicast in MANETs. They include traditional tree- or mesh-based protocols [3]–[6], stateless protocols [7], [8], flooding-based protocols [9], location-based protocols [10], and hybrid protocols [11]. Some of them have already pointed out that because links can be shared by several destinations, multicast is beneficial to improve performance compared to multiple unicast. However, the feasible performance gains, in terms of both throughput capacity and delay, that can be achieved by ex￾ploiting multicast, as well as the resulting scaling laws in a network with an increasing number of nodes, have not been investigated so far. In this paper, we bridge the theoretical analysis of fundamental scaling laws in multicast mobile ad hoc networks with the insights already gained through practical protocol development. By doing so, we provide a theoretical foundation to the design of intelligent communication schemes that exploit multicast, analytically showing the potential of such schemes in terms of capacity delay tradeoffs. The theoretical analysis of scaling laws in wireless networks is initiated by the seminal work of Gupta and Kumar [4]. Sev￾eral interesting studies have later emerged aimed at establishing the fundamental scaling laws for networks with multicast traffic. Li et al. [3], [22], [23] study the capacity of a static random wireless ad hoc network for multicast where each node sends packets to destinations. They show that the per-node mul￾ticast capacity is when , and is when . Their results generalize previous ca￾pacity bounds on unicast [4] and broadcast [5]. Under a more general Guassian channel model, multicast capacity is investi￾gated in [6] using percolation theory. Jacquet et al. [7] consider multicast capacity by accounting the ratio of the total number of hops for multicast and the average number of hops for uni￾cast. Shakkottai et al. [8] propose a comb-based architecture for multicast routing that achieves the upper bound for capacity in an order sense. In contrast to the discussed static networks, Gossglauser and Tse [9] for the first time have shown that a constant unicast 1063-6692/$26.00 © 2011 IEEE

WANG et al:DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1355 per-node capacity can be achieved in mobile ad hoc networks Answering these questions would provide helpful funda- by exploiting the store-carry-forward communication para- mental insights on the understanding and design of large-scale digm,i.e..by allowing nodes to store the packets and physically multicast MANETs. carry them while moving around the network.Although this In this paper,we study the scaling laws in a cell-partitioned communication scheme incurs a tremendous average delay MANET with multicast traffic.To begin,we propose a 2-hop of (n)[1],[10],it has laid the foundation of an entire new relay algorithm without redundancy.This algorithm is a gener- area of research,usually referred to as delay-tolerant or dis- alized version of the algorithm presented in [1]and corresponds ruption-tolerant networks(DTNs),which has recently attracted to a decoupled queuing model.Because k:destinations are asso- a lot of attention.A typical DTN consists of a set of fixed or ciated with a source,the delay for a packet is defined as the total mobile nodes and is characterized by intermittent connectivity time needed to deliver it to all destinations.For a specific packet, and frequent network partitioning,such that node mobility we first divide nodes other than the source into relays and des- is essential to ensure end-to-end communication.Many in- tinations (referred to as noncooperative mode).In this case,the teresting applications of DTN have been already envisioned packet may be carried to the destinations either through the re- and experimented upon,such as vehicular networks based lays or via the source,but will not be passed from one destina- on WiFi [13]-[16],networks based on human mobility [17], tion to another.Once a packet is sent to a relay,the relay will disaster-relief networks [18],and Internet access to remote be in charge of delivering it to all its destinations.Otherwise,if villages [19]. the source encounters a destination before a relay,it will take The asymptotic capacity delay tradeoff in MANETs ex- full responsibility of the rest multicast session.The MotionCast ploiting store-carry-forward schemes has attracted significant delay and capacity are calculated under this model. attention and is studied by many authors under various Then,we loosen the constraints of our initial model by per- mobility models.The most studied model is arguably the mitting information dissemination among destinations(cooper- independently and identically distributed (i.i.d.)mobility ative mode).In this scheme,we do not discriminate destinations model,where all nodes are reshuffled in a new time slot, due to its mathematical tractability.With this assumption. against the remnant nodes except the source.We define the first node that a source meets as the "designated relay,"which in Neely and Modiano [1]present a strategy utilizing redun- dant packets transmissions along multiple paths to reduce fact may possibly be an intended destination.Likewise,the des- delay at the cost of capacity.They establish the necessary ignated relay should carry the packet from the source until it tradeoff of delay/capacity >O(n)and propose schemes delivers this packet to all the destinations that have not received to achieveΘ(1)，Θ(1/vm,andΘ(1/(n log n)per-node the message.Notice that only one relay is associated to a specific capacity when the delay constraint isΘ(m),Θ（√，and packet in the 2-hop relay algorithm,and therefore after a relay e(logn),respectively.In [16],Toumpis and Goldsimth con- is designated,other destinations will merely act as receivers for struct a better scheme that can achieve a per-node capacity the packet and do not help transmit the packet to other nodes. of O(n(d-1)/2/log5/2n)under fading channels when the Quite counterintuitively,we find that there would be no gain in delay is bounded by O(nd).Lin and Shroff [2]later study performance for the cooperative scheme compared to the non- the fundamental capacity-delay tradeoff and identify the lim- cooperative one from an order sense. iting factors of the existing scheduling schemes in MANETs. Next,we employ redundant packets transmissions to reduce Recently,Ying et al.[15]propose joint coding-scheduling the delay.In a 2-hop relay strategy with redundancy,a source algorithms to improve capacity-delay tradeoffs,while Garetto sends a packet to multiple relays before all the destinations re- and Leonardi [24]show that it is possible to exploit node ceive the packet,which increases the chance that a destination heterogeneity under a restricted i.i.d.mobility model to achieve meets some of the relays at the expense of reduced capacity. both constant capacity and constant delay. If,in each time slot,only one transmission from a sender to To the best of our knowledge,this is the first work to study ca-a receiver is permitted in a cell,we show that the expected pacity and delay tadeoffs in MANETs with multicast traffic.Be-delay in the network is no less than (nog).Moreover, cause a key feature of multicast in MANETs is that packets can delay of O(vnlog)is achievable with per-node capacity of be delivered via nodes'mobility,we refer it as MotionCast.In-(1/kyn log). tuitively.delay and capacity tradeoffs still exist for MotionCast. The main results of this paper are summarized as follows. but are more complicated than unicast scenarios.Since packets For the 2-hop relay algorithm without redundancy,the capacity can be delivered through the mobility of relay nodes,a higher for MotionCast is (1/k)with an average delay of (nlog) per-node multicast capacity than in static networks is expected. Notice that the per-node capacity is better than the results of a However,the scheduling design becomes more difficult because static multicast scenario in [3]as long as k:is strictly less than of the permanent change of the network topology as well as the n in an order sense,i.e.,k=o(n).For the 2-hop relay algo- fact that multiple destinations for a packet will imply a larger rithm with redundancy,the capacity is (1/kvn log)with the delay.Hence,some challenging issues raised naturally in this delay scaling as (Vn logk).Thus,delay and capacity trade- context are the following. offs emerge between these two algorithms,i.e.,we can utilize re- What is the maximum per-node MotionCast capacity? dundant packets transmissions to reduce delay,but the capacity What is the delay for maximal capacity achieving schemes.will also decrease.The tradeoff obtained by us is better than and what is the minimum possible delay? that of directly extending the tradeoff for unicast to multicast. What is the delay and capacity tradeoff for MotionCast? We have also studied the fundamental delay-capacity tradeoff

WANG et al.: DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1355 per-node capacity can be achieved in mobile ad hoc networks by exploiting the store–carry–forward communication para￾digm, i.e., by allowing nodes to store the packets and physically carry them while moving around the network. Although this communication scheme incurs a tremendous average delay of [1], [10], it has laid the foundation of an entire new area of research, usually referred to as delay-tolerant or dis￾ruption-tolerant networks (DTNs), which has recently attracted a lot of attention. A typical DTN consists of a set of fixed or mobile nodes and is characterized by intermittent connectivity and frequent network partitioning, such that node mobility is essential to ensure end-to-end communication. Many in￾teresting applications of DTN have been already envisioned and experimented upon, such as vehicular networks based on WiFi [13]–[16], networks based on human mobility [17], disaster-relief networks [18], and Internet access to remote villages [19]. The asymptotic capacity delay tradeoff in MANETs ex￾ploiting store–carry–forward schemes has attracted significant attention and is studied by many authors under various mobility models. The most studied model is arguably the independently and identically distributed (i.i.d.) mobility model, where all nodes are reshuffled in a new time slot, due to its mathematical tractability. With this assumption, Neely and Modiano [1] present a strategy utilizing redun￾dant packets transmissions along multiple paths to reduce delay at the cost of capacity. They establish the necessary tradeoff of delay/capacity and propose schemes to achieve , and per-node capacity when the delay constraint is , and , respectively. In [16], Toumpis and Goldsimth con￾struct a better scheme that can achieve a per-node capacity of under fading channels when the delay is bounded by . Lin and Shroff [2] later study the fundamental capacity–delay tradeoff and identify the lim￾iting factors of the existing scheduling schemes in MANETs. Recently, Ying et al. [15] propose joint coding-scheduling algorithms to improve capacity–delay tradeoffs, while Garetto and Leonardi [24] show that it is possible to exploit node heterogeneity under a restricted i.i.d. mobility model to achieve both constant capacity and constant delay. To the best of our knowledge, this is the first work to study ca￾pacity and delay tadeoffs in MANETs with multicast traffic. Be￾cause a key feature of multicast in MANETs is that packets can be delivered via nodes’ mobility, we refer it as MotionCast. In￾tuitively, delay and capacity tradeoffs still exist for MotionCast, but are more complicated than unicast scenarios. Since packets can be delivered through the mobility of relay nodes, a higher per-node multicast capacity than in static networks is expected. However, the scheduling design becomes more difficult because of the permanent change of the network topology as well as the fact that multiple destinations for a packet will imply a larger delay. Hence, some challenging issues raised naturally in this context are the following. • What is the maximum per-node MotionCast capacity? • What is the delay for maximal capacity achieving schemes, and what is the minimum possible delay? • What is the delay and capacity tradeoff for MotionCast? Answering these questions would provide helpful funda￾mental insights on the understanding and design of large-scale multicast MANETs. In this paper, we study the scaling laws in a cell-partitioned MANET with multicast traffic. To begin, we propose a 2-hop relay algorithm without redundancy. This algorithm is a gener￾alized version of the algorithm presented in [1] and corresponds to a decoupled queuing model. Because destinations are asso￾ciated with a source, the delay for a packet is defined as the total time needed to deliver it to all destinations. For a specific packet, we first divide nodes other than the source into relays and des￾tinations (referred to as noncooperative mode). In this case, the packet may be carried to the destinations either through the re￾lays or via the source, but will not be passed from one destina￾tion to another. Once a packet is sent to a relay, the relay will be in charge of delivering it to all its destinations. Otherwise, if the source encounters a destination before a relay, it will take full responsibility of the rest multicast session. The MotionCast delay and capacity are calculated under this model. Then, we loosen the constraints of our initial model by per￾mitting information dissemination among destinations (cooper￾ative mode). In this scheme, we do not discriminate destinations against the remnant nodes except the source. We define the first node that a source meets as the “designated relay,” which in fact may possibly be an intended destination. Likewise, the des￾ignated relay should carry the packet from the source until it delivers this packet to all the destinations that have not received the message. Notice that only one relay is associated to a specific packet in the 2-hop relay algorithm, and therefore after a relay is designated, other destinations will merely act as receivers for the packet and do not help transmit the packet to other nodes. Quite counterintuitively, we find that there would be no gain in performance for the cooperative scheme compared to the non￾cooperative one from an order sense. Next, we employ redundant packets transmissions to reduce the delay. In a 2-hop relay strategy with redundancy, a source sends a packet to multiple relays before all the destinations re￾ceive the packet, which increases the chance that a destination meets some of the relays at the expense of reduced capacity. If, in each time slot, only one transmission from a sender to a receiver is permitted in a cell, we show that the expected delay in the network is no less than . Moreover, delay of is achievable with per-node capacity of . The main results of this paper are summarized as follows. For the 2-hop relay algorithm without redundancy, the capacity for MotionCast is with an average delay of . Notice that the per-node capacity is better than the results of a static multicast scenario in [3] as long as is strictly less than in an order sense, i.e., . For the 2-hop relay algo￾rithm with redundancy, the capacity is with the delay scaling as . Thus, delay and capacity trade￾offs emerge between these two algorithms, i.e., we can utilize re￾dundant packets transmissions to reduce delay, but the capacity will also decrease. The tradeoff obtained by us is better than that of directly extending the tradeoff for unicast to multicast. We have also studied the fundamental delay–capacity tradeoff

1356 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.19.NO.5.OCTOBER 2011 the nodes from 1 to n.We uniformly and randomly divide the network into different groups with each of them having k+1 nodes.Assume packets from each node i in a specific group must be delivered to all the other nodes within the group.Nodes not belonging to the group can serve as relays.Hence,each node i is a source node associated with k randomly and inde- pendently chosen destination nodes D1,D2,...,D over all the other nodes in the network.The relationships do not change as nodes move around.Then,the sources will communicate data to their k:destinations respectively through a common wireless channel. (a) b Definition of Capacity:First,we define stability of the Fig.1.Cell-partitioned MANET model with c cells and n mobile nodes under network.Packets are assumed to arrive at node i with proba- multicast traffic patter.(a)Network model.(b)Traffic pattern. bility Ai during each slot,i.e.,as a Bernoulli process of arrival rate Ai packets/slot.For the fixed Ai rates,the network is stable if there exists a scheduling algorithm so that the queue in each for MotionCast and shown that the fundamental tradeoff ratio is node does not increase to infinity as time goes to infinity.Thus, delay/capacity (n logk). the per-node capacity of the network is the maximum rate A The rest of the paper is organized as follows.In Section II,that the network can stably support.Note that sometimes the we describe the network model.In Section III,we introduce per-node capacity is called capacity for brief. the 2-hop relay algorithm without redundancy.In Section IV, Definition of Delay:The delay for a packet is defined as the the 2-hop relay algorithm with redundancy is presented.In Sec- time it takes the packet to reach all its k destinations after it tion V,we discuss the results and figure out the fundamental arrives at the source.The total network delay is the expectation tradeoff for multicast.Finally,we conclude in Section VI. of the average delay over all packets and all random network configurations in the long term. II.NETWORK MODEL Definition of Redundancy:At each time slot,if more than Cell-Partitioned Network Model:The system model is based one node is performing as a relay for a packet,we say there on the cell-partitioned network model exploited in [1]and [18]. is redundancy in the network.Furthermore,we say the corre- Suppose the network is a unit square and there are n mobile sponding scheduling scheme is with redundancy or redundant. nodes in it.Then,we divide it into c nonoverlapping cells with Otherwise,it is without redundancy. equal size as depicted in Fig.1.We assume nodes can commu- Definition of Cooperative:We adopt the term"cooperative" nicate with each other only when they are within a same cell (to here to refer to a destination that can relay a packet from the locate the nodes,please refer to [17]and the references therein), source to other destinations.Otherwise,the destinations merely and to avoid interference,different frequencies are employed accept packets destined for them,but do not forward to others, among the neighboring cells.1 Additionally,to bound the inter- which is called noncooperative mode. ference inside each cell.we assume that the number of the cells Notations:In our paper,we adopt the following widely used is on the same order as that of the nodes throughout this paper. order notations in a sense of probability.We say that an event Thus,node-per-cell density d=n/c scales as (1).2 occurs with high probability (w.h.p.)if its probability tends to Mobility Model:Dividing time into constant duration slots, 1 as n goes to infinity.Given two functions f(n)and g(n),we we adopt the following ideal i.i.d.mobility to model the some- say that f(n)=O(g(n))w.h.p.if there exists a constant c such times drastic topology changes in MANETs and investigate that their impact.The initial position of each node is equally likely to be any of the c cells independent of others.At the beginning limP(f(n)≤cg(n)=1. (1) of each time slot,nodes randomly choose and move to a new cell i.i.d.over all cells in the network.Although the ideal i.i.d. If the above sign of inequality is strict,we denote f(n)= mobility model may appear to be an oversimplification,it has o(g(n)).Moreover,we say that f(n)=(g(n))w.h.p. been widely adopted in the literature because of its mathemat- if g(n)=O(f(n))w.h.p.If both f(n)=(g(n))and ical tractability,which could provide meaningful bounds on f(n)=O(g(n))w.h.p.,then we say that f(n)=(g(n)) performance.Note that the i.i.d.model also characterizes the w.h.p. maximum degree of mobility.With the help of mobility,packets can be carried by the nodes until they reach the destinations. Traffic Pattern:We first define the source-destination rela- III.DELAY AND CAPACITY IN THE 2-HOP RELAY ALGORITHM WITHOUT REDUNDANCY tionships before the transmissions start.In particular,we as- sume the number of users n is divisible by k:+1 and number all In this section,we propose 2-hop relay algorithms without redundancy and compute the achievable delay and capacity both It is clear that only four frequencies are enough for the whole network. under noncooperative mode and cooperative mode.Then,we 2Theorems 3 and 4 will show this assumption does not vitiate our result and can lead us to design a more simple and practical scheduling algorithm with the explore the maximum capacity and the minimum delay in these purpose to achieve a good tradeoff between throughput and delay. situations

1356 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 5, OCTOBER 2011 Fig. 1. Cell-partitioned MANET model with ￾ cells and mobile nodes under multicast traffic pattern. (a) Network model. (b) Traffic pattern. for MotionCast and shown that the fundamental tradeoff ratio is delay/capacity . The rest of the paper is organized as follows. In Section II, we describe the network model. In Section III, we introduce the 2-hop relay algorithm without redundancy. In Section IV, the 2-hop relay algorithm with redundancy is presented. In Sec￾tion V, we discuss the results and figure out the fundamental tradeoff for multicast. Finally, we conclude in Section VI. II. NETWORK MODEL Cell-Partitioned Network Model: The system model is based on the cell-partitioned network model exploited in [1] and [18]. Suppose the network is a unit square and there are mobile nodes in it. Then, we divide it into nonoverlapping cells with equal size as depicted in Fig. 1. We assume nodes can commu￾nicate with each other only when they are within a same cell (to locate the nodes, please refer to [17] and the references therein), and to avoid interference, different frequencies are employed among the neighboring cells.1 Additionally, to bound the inter￾ference inside each cell, we assume that the number of the cells is on the same order as that of the nodes throughout this paper. Thus, node-per-cell density scales as .2 Mobility Model: Dividing time into constant duration slots, we adopt the following ideal i.i.d. mobility to model the some￾times drastic topology changes in MANETs and investigate their impact. The initial position of each node is equally likely to be any of the cells independent of others. At the beginning of each time slot, nodes randomly choose and move to a new cell i.i.d. over all cells in the network. Although the ideal i.i.d. mobility model may appear to be an oversimplification, it has been widely adopted in the literature because of its mathemat￾ical tractability, which could provide meaningful bounds on performance. Note that the i.i.d. model also characterizes the maximum degree of mobility. With the help of mobility, packets can be carried by the nodes until they reach the destinations. Traffic Pattern: We first define the source–destination rela￾tionships before the transmissions start. In particular, we as￾sume the number of users is divisible by and number all 1It is clear that only four frequencies are enough for the whole network. 2Theorems 3 and 4 will show this assumption does not vitiate our result and can lead us to design a more simple and practical scheduling algorithm with the purpose to achieve a good tradeoff between throughput and delay. the nodes from 1 to . We uniformly and randomly divide the network into different groups with each of them having nodes. Assume packets from each node in a specific group must be delivered to all the other nodes within the group. Nodes not belonging to the group can serve as relays. Hence, each node is a source node associated with randomly and inde￾pendently chosen destination nodes over all the other nodes in the network. The relationships do not change as nodes move around. Then, the sources will communicate data to their destinations respectively through a common wireless channel. Definition of Capacity: First, we define stability of the network. Packets are assumed to arrive at node with proba￾bility during each slot, i.e., as a Bernoulli process of arrival rate packets/slot. For the fixed rates, the network is stable if there exists a scheduling algorithm so that the queue in each node does not increase to infinity as time goes to infinity. Thus, the per-node capacity of the network is the maximum rate that the network can stably support. Note that sometimes the per-node capacity is called capacity for brief. Definition of Delay: The delay for a packet is defined as the time it takes the packet to reach all its destinations after it arrives at the source. The total network delay is the expectation of the average delay over all packets and all random network configurations in the long term. Definition of Redundancy: At each time slot, if more than one node is performing as a relay for a packet, we say there is redundancy in the network. Furthermore, we say the corre￾sponding scheduling scheme is with redundancy or redundant. Otherwise, it is without redundancy. Definition of Cooperative: We adopt the term “cooperative” here to refer to a destination that can relay a packet from the source to other destinations. Otherwise, the destinations merely accept packets destined for them, but do not forward to others, which is called noncooperative mode. Notations: In our paper, we adopt the following widely used order notations in a sense of probability. We say that an event occurs with high probability (w.h.p.) if its probability tends to 1 as goes to infinity. Given two functions and , we say that w.h.p. if there exists a constant such that (1) If the above sign of inequality is strict, we denote . Moreover, we say that w.h.p. if w.h.p. If both and w.h.p., then we say that w.h.p. III. DELAY AND CAPACITY IN THE 2-HOP RELAY ALGORITHM WITHOUT REDUNDANCY In this section, we propose 2-hop relay algorithms without redundancy and compute the achievable delay and capacity both under noncooperative mode and cooperative mode. Then, we explore the maximum capacity and the minimum delay in these situations.

WANG et al:DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1357 A.Under Noncooperative Mode Here,we describe a 2-hop relay algorithm without redun- dancy.Usually,a source sends a packet to one of the relays,then the relay will distribute the packet to all its destinations.While as an initial step,we consider the noncooperative mode,which means a destination cannot be a relay. 2-Hop Relay Algorithm Without Redundancy I:During a time slot,for a cell with at least two nodes: 1)If there exists a source-destination pair within the cell,ran- domly select such a pair uniformly over all possible pairs in the cell.If the source has a new packet in the buffer in- tended for the destination,transmit.If all its destinations have received this packet,3 then it will delete the packet from the buffer.Otherwise,stay idle. 2)If there is no such pair,randomly assign a node as sender and independently choose another node in the cell as re- Fig.2.A decoupled queuing model of the network as seen by the packets trans- ceiver.With equal probability,choose from the following mitted from a single source to multiple destinations. two options4: Source-to-Relay Transmission:If the sender has a new packet,one that has never been transmitted before.send 3) the packet to the receiver and delete it from the buffer. [生(-+-产 Otherwise,stay idle. Relay-to-Destination Transmission:If the sender has a When n tends to infinity,it follows p1-(d+1)e-d and new packet from another node destined for the receiver, q→1-e-市(1+)h.Thus,ifk=o(n),q→05 else if transmit.If all the destinations that want to get this k=e(n),g-1-(d+1)e-d.Intuitively,when k approaches packet have received it,it will be dropped from the the same order as n,the multicast will reduce to a broadcast, buffer in the sender.Otherwise,stay idle. and the events corresponding to p and g will gradually become Intuitively,since there are no redundant transmissions and the identical.Then,we have the following theorem. cell partition with constant density scheme guarantees maximal Theorem 1:Consider a cell-partitioned network (with spatial reuse,the algorithm could achieve maximal throughput. n nodes and c cells)under the 2-hop relay algorithm without The only reason that a constant throughput cannot be achieved redundancy I,and assume that nodes change cells i.i.d.and is that a single packet needs to be transmitted repetitively for uniformly over each cell every time slot.If the exogenous input about k times to different destinations,and therefore a (1/) stream to node i that makes the network stable is a Bernoulli throughput is feasible.Considering delay,it is intuitive for us to stream of rate Ai=O(u/)and =o(n),then the average loosely model the network as a queueing system such that every delay Wi for the traffic of node i satisfies source-destination pair corresponds to an M/M/I queue.The service time for a single packet,which follows exponential dis- E{W份=O(mlog) (4) tribution,has an expectation of (n),i.e.,the average waiting time that two specific nodes meet.Then,the total delay for a whereu= D+0 2d complete multicast session will roughly equal the maximum of Proof:A decoupled view of the network as seen by a single k such i.i.d.random delays and turns out to be (n log).We source i is shown in Fig.2.Due to the i.i.d.mobility model,the formally derive the performance of the above algorithm. source user can be represented as a Bernoulli/Bernoulli queue, The algorithm has an advanced decoupling feature between where in every time slot a new packet arrives with probabilityAi, all n multicast sessions,as illustrated in Fig.2,where nodes and a service opportunity arises with some fixed probability u are divided into destinations and relays for the packets from a when the packet is handed over a relay or transmitted to a des- single source,and the packets transmissions for other sources tination.We first show that the expressionstill holds. are modeled just as random ON/OFF service opportunities. The Bernoulli nature of the server process implies that the Let p represent the probability of finding at least two nodes transmission probability u is equal to the time average rate of in a particular cell,and g represent the probability of finding transmission opportunities of source i.6 Letr represent the rate a source-destination pair within a cell.From Appendix I,we at which the source is scheduled to transmit directly to one of the obtain that destinations,and r2 represent the rate at which it is scheduled to transmit to one of its relays.The same as ur equals the =1-(-)-(-)” probability that the source is scheduled to transmit directly to (2) the destination,and r2 equals the probability that the source is We assume that nodes can be aware of this from the control information SBecause when nc n and=o(n.qc1-e-行(1+)中c passed over a reserved bandwidth channel. 1-e-de4=0. ANote that because of the traffic patter we assume and the probabilities 6A transmission opportunity arises when a user is selected to transmit to an- of source-destination and source-relay (or relay-destination)transmissions other user and corresponds to a service opportunity in the Bernoulli/Bernoulli we calculate,source-destination transmission does not have priority over queue.Such opportunities arise with probability u every time slot,independent non-source-destination transmission,i.e.,they happen independently. of whether or not there is a packet waiting in the queue

WANG et al.: DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1357 A. Under Noncooperative Mode Here, we describe a 2-hop relay algorithm without redun￾dancy. Usually, a source sends a packet to one of the relays, then the relay will distribute the packet to all its destinations. While as an initial step, we consider the noncooperative mode, which means a destination cannot be a relay. 2-Hop Relay Algorithm Without Redundancy I: During a time slot, for a cell with at least two nodes: 1) If there exists a source–destination pair within the cell, ran￾domly select such a pair uniformly over all possible pairs in the cell. If the source has a new packet in the buffer in￾tended for the destination, transmit. If all its destinations have received this packet,3 then it will delete the packet from the buffer. Otherwise, stay idle. 2) If there is no such pair, randomly assign a node as sender and independently choose another node in the cell as re￾ceiver. With equal probability, choose from the following two options4: • Source-to-Relay Transmission: If the sender has a new packet, one that has never been transmitted before, send the packet to the receiver and delete it from the buffer. Otherwise, stay idle. • Relay-to-Destination Transmission: If the sender has a new packet from another node destined for the receiver, transmit. If all the destinations that want to get this packet have received it, it will be dropped from the buffer in the sender. Otherwise, stay idle. Intuitively, since there are no redundant transmissions and the cell partition with constant density scheme guarantees maximal spatial reuse, the algorithm could achieve maximal throughput. The only reason that a constant throughput cannot be achieved is that a single packet needs to be transmitted repetitively for about times to different destinations, and therefore a throughput is feasible. Considering delay, it is intuitive for us to loosely model the network as a queueing system such that every source–destination pair corresponds to an M/M/1 queue. The service time for a single packet, which follows exponential dis￾tribution, has an expectation of , i.e., the average waiting time that two specific nodes meet. Then, the total delay for a complete multicast session will roughly equal the maximum of such i.i.d. random delays and turns out to be . We formally derive the performance of the above algorithm. The algorithm has an advanced decoupling feature between all multicast sessions, as illustrated in Fig. 2, where nodes are divided into destinations and relays for the packets from a single source, and the packets transmissions for other sources are modeled just as random ON/OFF service opportunities. Let represent the probability of finding at least two nodes in a particular cell, and represent the probability of finding a source–destination pair within a cell. From Appendix I, we obtain that (2) 3We assume that nodes can be aware of this from the control information passed over a reserved bandwidth channel. 4Note that because of the traffic pattern we assume and the probabilities of source–destination and source–relay (or relay–destination) transmissions we calculate, source–destination transmission does not have priority over non-source–destination transmission, i.e., they happen independently. Fig. 2. A decoupled queuing model of the network as seen by the packets trans￾mitted from a single source to multiple destinations. (3) When tends to infinity, it follows and . Thus, if ;5 else if . Intuitively, when approaches the same order as , the multicast will reduce to a broadcast, and the events corresponding to and will gradually become identical. Then, we have the following theorem. Theorem 1: Consider a cell-partitioned network (with nodes and cells) under the 2-hop relay algorithm without redundancy , and assume that nodes change cells i.i.d. and uniformly over each cell every time slot. If the exogenous input stream to node that makes the network stable is a Bernoulli stream of rate and , then the average delay for the traffic of node satisfies (4) where . Proof: A decoupled view of the network as seen by a single source is shown in Fig. 2. Due to the i.i.d. mobility model, the source user can be represented as a Bernoulli/Bernoulli queue, where in every time slot a new packet arrives with probability , and a service opportunity arises with some fixed probability when the packet is handed over a relay or transmitted to a des￾tination. We first show that the expression still holds. The Bernoulli nature of the server process implies that the transmission probability is equal to the time average rate of transmission opportunities of source .6 Let represent the rate at which the source is scheduled to transmit directly to one of the destinations, and represent the rate at which it is scheduled to transmit to one of its relays. The same as equals the probability that the source is scheduled to transmit directly to the destination, and equals the probability that the source is 5Because when ￾ ￾ and ￾ ￾  ￾     ￾    ￾ . 6A transmission opportunity arises when a user is selected to transmit to an￾other user and corresponds to a service opportunity in the Bernoulli/Bernoulli queue. Such opportunities arise with probability  every time slot, independent of whether or not there is a packet waiting in the queue.

1358 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.19.NO.5.OCTOBER 2011 header payload D .......DD P阴…IB (a) heade payload D 3 4 payload D header Relay (b) Fig.3.More delicate view of a relay-destinations transmission.(a)Each packet delivered to a relay node has a similar form that contains its destinations'infor- mation in the header.(b)Each relay can make a packet into n similar copies and can be modeled as a node having =n=1 parallel subqueues buffering packets intended for different destinations.n subqueues associated with n destinations of the current source are shaded in the figure scheduled to transmit to one of its relay users.Then,we have given by Is=,wherep.From Little's theorem, L=71+r2.Since the relay algorithm schedules transmissions 10 into and out of the relay nodes with equal probability,hencer2 the average waiting time in the source isEW= Furthermore,this queue is reversible,so the output process is is also equal to the rate at which the relay nodes are scheduled also a Bernoulli stream of rate Ai. to transmit to the destinations.Every time slot,the total rate of transmission opportunities over the network is thus n(1+2r2). Notice that our traffic pattern has defined every disjointk+1 Meanwhile,a transmission opportunity occurs in any given cell nodes as a group,and every node in this group is the source with probability p,hence for the other nodes.From a more delicate point of view,a packet delivered from a source to a relay contains not only nec- cp=n(Tr1+22). (5) essary payload,but also redundant data in its header that tells the relay which k destinations this packet should be transmitted Recall that g is the probability that a given cell contains a to,shown in Fig.3(a).Based on this information,the relay can source-destination pair.Since the algorithm schedules the make k:similar copies,each of which contains less redundant single-hop source-to-destination transmissions whenever pos- data in its header just indicating its own corresponding destina- sible,the rate rI satisfies tion.Also,since a node can act as a relay to transmit packets to cq=nT1. (6) other n-k-1 destinations,we model a relay as a node that has n-k-1 parallel subqueues (each of them buffers the packets It follows from(⑥)and(8)thatr=号，2="z.The total intended for a certain destination),shown in Fig.3(b).Next,we rate of transmissions out of the source node is thus given by will compute the input rate and output rate of a subqueue =1+r2=」 21 A given packet from a source is transmitted to the first relay Next,we compute the average delay for the traffic of node i. node with probability pi and rate(be. There are two possible routings from a source to its destinations:cause with probabilitythe packet is delivered to a relay,and one is the 2-hop path along "source-relay-destinations";the each of the n-k-1 relay nodes are equally likely).Since there other is the single-hop path from source to destinations directly.are k:sources for each subqueue,every time slot,a subqueue As for the first routing,packet delay is composed of the waiting in this relay receives a packet with probability 1-(1-pi), time at source and relay.In this case,since the source can be which can be expressed as kp;+akp:).The latter one will not viewed as a Bernoulli/Bernoulli queue with input rate Ai and influence our results,so we omit it.Hence,the input rate of a service rate u,it has an expected number of occupancy packets subqueue is Ar.On the other hand,the subqueue in the relay

1358 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 5, OCTOBER 2011 Fig. 3. More delicate view of a relay–destinations transmission. (a) Each packet delivered to a relay node has a similar form that contains its destinations’ infor￾mation in the header. (b) Each relay can make a packet into ￾ similar copies and can be modeled as a node having ￾ ￾ ￾ ￾ parallel subqueues buffering packets intended for different destinations. ￾ subqueues associated with ￾ destinations of the current source are shaded in the figure. scheduled to transmit to one of its relay users. Then, we have . Since the relay algorithm schedules transmissions into and out of the relay nodes with equal probability, hence is also equal to the rate at which the relay nodes are scheduled to transmit to the destinations. Every time slot, the total rate of transmission opportunities over the network is thus . Meanwhile, a transmission opportunity occurs in any given cell with probability , hence (5) Recall that is the probability that a given cell contains a source–destination pair. Since the algorithm schedules the single-hop source-to-destination transmissions whenever pos￾sible, the rate satisfies (6) It follows from (6) and (8) that . The total rate of transmissions out of the source node is thus given by . Next, we compute the average delay for the traffic of node . There are two possible routings from a source to its destinations: one is the 2-hop path along “source–relay–destinations”; the other is the single-hop path from source to destinations directly. As for the first routing, packet delay is composed of the waiting time at source and relay. In this case, since the source can be viewed as a Bernoulli/Bernoulli queue with input rate and service rate , it has an expected number of occupancy packets given by , where . From Little’s theorem, the average waiting time in the source is . Furthermore, this queue is reversible, so the output process is also a Bernoulli stream of rate . Notice that our traffic pattern has defined every disjoint nodes as a group, and every node in this group is the source for the other nodes. From a more delicate point of view, a packet delivered from a source to a relay contains not only nec￾essary payload, but also redundant data in its header that tells the relay which destinations this packet should be transmitted to, shown in Fig. 3(a). Based on this information, the relay can make similar copies, each of which contains less redundant data in its header just indicating its own corresponding destina￾tion. Also, since a node can act as a relay to transmit packets to other destinations, we model a relay as a node that has parallel subqueues (each of them buffers the packets intended for a certain destination), shown in Fig. 3(b). Next, we will compute the input rate and output rate of a subqueue. A given packet from a source is transmitted to the first relay node with probability and rate (be￾cause with probability the packet is delivered to a relay, and each of the relay nodes are equally likely). Since there are sources for each subqueue, every time slot, a subqueue in this relay receives a packet with probability , which can be expressed as . The latter one will not influence our results, so we omit it. Hence, the input rate of a subqueue is . On the other hand, the subqueue in the relay

WANG et al:DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1359 node is scheduled for a potential packet transmission to a desti-above calculation of the delay through 2-hop route,we have the nation node with probability(because when it acts expected waiting time for the packet to reach all k:-1 remnant as a relay,it can transmit packets to n-1 destinations except destinations as EWsd}=(log(-1)/(). the source of the given packet and itself with equal probability). Finally,by weighting the delay that occurs in both routings, Notice that packet arrivals and transmission opportunities in a we achieve the total network delay as subqueue of the relay node are mutually exclusive events.It fol- lows that the discrete-time Markov chain for queue occupancy E{W}= (EW)+EWa))+(EW}+EWra}) in the relay node can be written as a simple birth-death chain that is identical to a continuous-time M/M/I queue with input rate入and service rate r.Each destinationi(l≤i≤k) obtains the packet from the relay through such a queue,thus the waiting time for it is an exponential distributed variable with an 1- expectation of EWrd}=1/(r-Ar). The resulting waiting time Wrd for multicast is deter- -k-1)logk:k log(k:-1) mined by the maximum value among all the waiting times W,W,...,W of thesek destinations.Due to the fact u-k入 4-k入 that:1)all k:destinations share the same arrival process,and 2) (7) the interference constraint that a relay node can communicate with only one destination in one time slot,W are corre- To ensure the stability of the network.the incoming rate lated over k.However,we can construct a set of dual random should be less than the service rate at any stage of the network. variables {W such that they are ii.d.They provide a slightly Thus alternated view of the queueing system depicted in Fig.3,with u-入>0 multidestination reception enabled,i.e.,if a source encounters ->0 more than one destination,the packet will be transmitted to all k入：2 of them.Additionally,we hypothesize that the arrival processes nR与-二>0 of different destinations are independent,each with rate A..In the following.we shall show W=W w.h.p. i.e.,Ai<u/k.Moreover,the total network delay is in the order Condition on the event that the relay encounters one or more of (o)for a fixed traffic loading valueat each destinations,and denote 1,1 as the probability that exactly relay and source. one or more than one destinations are reached,respectively.It From the above discussion,we conclude the theorem. ■ is clear that o1=w(1)ifk =o(n)and o=e(p1) if k =e(n).Therefore,r=(),which indicates that B.Under Cooperative Mode multireception does not affect the service process in an order sense.Similarly,also notice that the input process for a sub- In Section III-A,we proposed a 2-hop relay algorithm without redundancy obtaining per-node capacity (1/k)with queue in the two queueing systems,though constructed on in- dependent probability spaces,is the samer and does not rely delay O(nlogk).Here,we bring forward a more general algorithm that does not discriminate destinations and the nodes on network scale n.Due to the nature of the M/M/I queue,the waiting time Wra or W only depends on the input and the other than the source,i.e..under cooperative mode.This algo- service process,and it is clear that W=(W)w.h.p.In rithm achieves the same performance as the first one.Since the other words,there exists constant ci such that W=ciW second algorithm is simpler than the first one,we adopt this w.h.p.By Lemma 2(see the proof in Appendix II),we obtain algorithm and refer to it as the 2-hop relay algorithm without that E(Wrd}=e(EWrd})=e(logk/(ur-kr)).Thus,if redundancy for briefness in the rest of the paper.It is described the packet is delivered through the path "source-relay-destina- as follows. tions,"the average delay is EfWs+EfWrdt. 2-Hon relay Algorithm without redundancy l:For each cell While if the packet is directly sent to the destinations by the with at least two nodes in a time slot,a random sender and a source,it will wait at the source for a time Ws first,then the random receiver are picked with uniform probability over all source distributes this packet to the remnant k:-1 destinations. nodes in the cell.With equal probability,the sender is scheduled At this time,the source can be treated as a node having k parallel to operate in the following two options. M/M/1 subbuffers corresponding to its k:destinations similarly. 1)Source-to-Relay Transmission:If the sender has a new The source will copy this packet into-1similar duplicates and packet,one that has never been transmitted before,send the add them into respective subbuffers associated with the remnant packet to the receiver and delete it from the buffer.Other- :-1 destinations.Also,at this time,the source can be treated as wise,stay idle. a continuous-time M/M/1 queue.Since the probability that the 2)Relay-to-Destination Transmission:If the sender has source needs to send packets directly to destinations is "L,the packets received from other nodes that are destined for the incoming data rate is thus for such a queue.Meanwhile,the receiver and have not been transmitted to the receiver yet, service rate at each equals to the transmission rate between then choose the latest one,transmit.If all the destinations a source-destination pair.Hence,the expectation of the waiting that want to get this packet have received it,it will be time for each one of the k-1 destinations through such a queue dropped from the buffer in the sender.Otherwise,stay is 1/().By Lemma 2 and the same method in the idle

WANG et al.: DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1359 node is scheduled for a potential packet transmission to a desti￾nation node with probability (because when it acts as a relay, it can transmit packets to destinations except the source of the given packet and itself with equal probability). Notice that packet arrivals and transmission opportunities in a subqueue of the relay node are mutually exclusive events. It fol￾lows that the discrete-time Markov chain for queue occupancy in the relay node can be written as a simple birth–death chain that is identical to a continuous-time M/M/1 queue with input rate and service rate . Each destination obtains the packet from the relay through such a queue, thus the waiting time for it is an exponential distributed variable with an expectation of . The resulting waiting time for multicast is deter￾mined by the maximum value among all the waiting times of these destinations. Due to the fact that: 1) all destinations share the same arrival process, and 2) the interference constraint that a relay node can communicate with only one destination in one time slot, are corre￾lated over . However, we can construct a set of dual random variables such that they are i.i.d. They provide a slightly alternated view of the queueing system depicted in Fig. 3, with multidestination reception enabled, i.e., if a source encounters more than one destination, the packet will be transmitted to all of them. Additionally, we hypothesize that the arrival processes of different destinations are independent, each with rate . In the following, we shall show w.h.p. Condition on the event that the relay encounters one or more destinations, and denote as the probability that exactly one or more than one destinations are reached, respectively. It is clear that if and if . Therefore, , which indicates that multireception does not affect the service process in an order sense. Similarly, also notice that the input process for a sub￾queue in the two queueing systems, though constructed on in￾dependent probability spaces, is the same and does not rely on network scale . Due to the nature of the M/M/1 queue, the waiting time or only depends on the input and the service process, and it is clear that w.h.p. In other words, there exists constant such that w.h.p. By Lemma 2 (see the proof in Appendix II), we obtain that . Thus, if the packet is delivered through the path “source–relay–destina￾tions,” the average delay is . While if the packet is directly sent to the destinations by the source, it will wait at the source for a time first, then the source distributes this packet to the remnant destinations. At this time, the source can be treated as a node having parallel M/M/1 subbuffers corresponding to its destinations similarly. The source will copy this packet into similar duplicates and add them into respective subbuffers associated with the remnant destinations. Also, at this time, the source can be treated as a continuous-time M/M/1 queue. Since the probability that the source needs to send packets directly to destinations is , the incoming data rate is thus for such a queue. Meanwhile, the service rate at each equals to the transmission rate between a source–destination pair. Hence, the expectation of the waiting time for each one of the destinations through such a queue is . By Lemma 2 and the same method in the above calculation of the delay through 2-hop route, we have the expected waiting time for the packet to reach all remnant destinations as . Finally, by weighting the delay that occurs in both routings, we achieve the total network delay as (7) To ensure the stability of the network, the incoming rate should be less than the service rate at any stage of the network. Thus i.e., . Moreover, the total network delay is in the order of for a fixed traffic loading value at each relay and source. From the above discussion, we conclude the theorem. B. Under Cooperative Mode In Section III-A, we proposed a 2-hop relay algorithm without redundancy obtaining per-node capacity with delay . Here, we bring forward a more general algorithm that does not discriminate destinations and the nodes other than the source, i.e., under cooperative mode. This algo￾rithm achieves the same performance as the first one. Since the second algorithm is simpler than the first one, we adopt this algorithm and refer to it as the 2-hop relay algorithm without redundancy for briefness in the rest of the paper. It is described as follows. 2-Hop Relay Algorithm Without Redundancy II: For each cell with at least two nodes in a time slot, a random sender and a random receiver are picked with uniform probability over all nodes in the cell. With equal probability, the sender is scheduled to operate in the following two options. 1) Source-to-Relay Transmission: If the sender has a new packet, one that has never been transmitted before, send the packet to the receiver and delete it from the buffer. Other￾wise, stay idle. 2) Relay-to-Destination Transmission: If the sender has packets received from other nodes that are destined for the receiver and have not been transmitted to the receiver yet, then choose the latest one, transmit. If all the destinations that want to get this packet have received it, it will be dropped from the buffer in the sender. Otherwise, stay idle

1360 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.19,NO.5.OCTOBER 2011 The algorithm simply designates the first node a source meets Looking upon the asymptotic behaviors of the network delay as the relay,no matter if it is a destination.Thus,according to whenn-o,we have=2一→l-ae-,Toensure the )月 the scheduling scheme,all the packets will be delivered along stability of the network,the incoming rate should be less than a 2-hop path"source-relay-destinations."Then,we summarize the service rate at any stage of the network.Thus the next theorem Theorem 2:Consider the same assumptions for the network L-入>0 as Theorem 1,under the 2-hop relay algorithm without redun- 台2-咎>0 dancy II.The resulting per-node capacity and the average delay are (1/)and O(n logk),respectively,for all k <n. i.e,λi< a-二x一/k(n一.Furthermore,.the total Proof:Since all the packets will be delivered along a 2-hop network delay is governed by (9),which is on the order of "source-relay-destinations"path,by using the same analytical O(nlog)for a fixed traffic loading valuepr=2)at each n-1 method,we can know r=0 and=r2.Meanwhile,a trans- relay. mission opportunity occurs in any given cell with probability p. From this discussion.we conclude the theorem. ◆ hence C.Maximum Capacity and Minimum Delay cp=244. (8) Although we have constructed the achievable delay and ca- pacity if no redundancy is used,open questions are still left for It follows from (8)that 2 the maximum capacity and the minimum delay of this network. Thus,following the same analytical steps as Theorem I when We address these problems here by presenting the following k:is strictly less than n in an order sense.we can know that theorems. packet delay is composed of the waiting time at source and Theorem 3:The multicast capacity of a cell-partitioned net- relay.Since the source can be viewed as a Bernoulli/Bernoulli work is O()if only a pair of a sender and receiver is active in queue with input rate Ai and service rate u,the average waiting each cell per time slot.In particular,if d=(1),the multicast time in the source isWs.Moreover,this queue is capacity is O(1/). reversible,so the output process is also a Bernoulli stream of Proof:We use hop argument to prove this result.Since rate入i for any interval [0,T],the less hops the source needs to send A given packet from this output process is transmitted to a packet to its k:destinations,the more capacity it can achieve. the first relay node with probabilityHence.every time Thus,we assume a packet is delivered directly from a source to slot,this relay independently receives a packet with probability one of its destinations via the 1-hop route"Source-destination." Ar=I.On the other hand,the relay node is scheduled 入 Let Xs(T)represent the total number of packets transferred over for a potential packet transmission to a destination node with the network from sources to destinations via the 1-hop route probability(because when it acts as a relay,it can during the interval [0,T].Fix e 0.For network stability,there transmit packets to n-2 destinations except the source of must be arbitrarily large values Tsuch that the sum output rate the given packet and itself with equal probability).Notice that is within e of the total input rate packet arrivals and transmission opportunities are mutually exclusive events in the relay node. XsT之nk入-6. (10) T When taking the 2-hop algorithm without redundancy II,the first node a source meets is as the relay,no matter if it is a desti- If this were not the case,the total number of packets in the nation.The difference is that if the relay is a destination node,it network would grow to infinity,and hence the network would needs only to relay the packet to the rest-1 destinations.Oth-be unstable.Since every transmission just needs 1 hop,the total erwise,it needs to relay the packet to all destinations.Since we number of packet transmissions in the network during the first focus on the performance in an order sense,we omit this differ- T slots is also Xs(T).This value must be less than or equal to ence between these two cases and assume a relay is responsible the total number of transmission opportunities Y(T),and hence for delivering a new packet to its corresponding k destinations for simplicity. Xs(T)≤Y(T) (11) At this time,when receiving a new packet from the source,the relay node will make it into k similar duplicates.Thus,a relay where Y(T)represents the total number of cells containing at can be viewed as an M/M/I queue with input rate Ar and ser- least two users in a particular time slot,summed over all time vice rate ur.Hence,the expectation of the waiting time of each slots 1,2,...,T.By the law of large numbers,it is clear that destination is 1/().By Lemma 2.we have that the ÷Y(T)→cp as T→oo,where p is the steady-state proba- expected waiting time for the packet to reach all k:destinations bility that there are two or more users within a particular cell is EWa}=Θ0ogk2-倍》 and is given by (2). Finally,we achieve the total network delay as From(10)and (11),it follows that λ<宁+p EWi=EWs+EW a (12) 1-i+日 log K (9)Notice thatk=O(n),thus we have =O().Additionally, 一入 ifd=⊙(1)，λ=O(1/k)

1360 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 5, OCTOBER 2011 The algorithm simply designates the first node a source meets as the relay, no matter if it is a destination. Thus, according to the scheduling scheme, all the packets will be delivered along a 2-hop path “source–relay–destinations.” Then, we summarize the next theorem. Theorem 2: Consider the same assumptions for the network as Theorem 1, under the 2-hop relay algorithm without redun￾dancy II. The resulting per-node capacity and the average delay are and , respectively, for all . Proof: Since all the packets will be delivered along a 2-hop “source–relay–destinations” path, by using the same analytical method, we can know and . Meanwhile, a trans￾mission opportunity occurs in any given cell with probability , hence (8) It follows from (8) that . Thus, following the same analytical steps as Theorem 1 when is strictly less than in an order sense, we can know that packet delay is composed of the waiting time at source and relay. Since the source can be viewed as a Bernoulli/Bernoulli queue with input rate and service rate , the average waiting time in the source is . Moreover, this queue is reversible, so the output process is also a Bernoulli stream of rate . A given packet from this output process is transmitted to the first relay node with probability . Hence, every time slot, this relay independently receives a packet with probability . On the other hand, the relay node is scheduled for a potential packet transmission to a destination node with probability (because when it acts as a relay, it can transmit packets to destinations except the source of the given packet and itself with equal probability). Notice that packet arrivals and transmission opportunities are mutually exclusive events in the relay node. When taking the 2-hop algorithm without redundancy II, the first node a source meets is as the relay, no matter if it is a desti￾nation. The difference is that if the relay is a destination node, it needs only to relay the packet to the rest destinations. Oth￾erwise, it needs to relay the packet to all destinations. Since we focus on the performance in an order sense, we omit this differ￾ence between these two cases and assume a relay is responsible for delivering a new packet to its corresponding destinations for simplicity. At this time, when receiving a new packet from the source, the relay node will make it into similar duplicates. Thus, a relay can be viewed as an M/M/1 queue with input rate and ser￾vice rate . Hence, the expectation of the waiting time of each destination is . By Lemma 2, we have that the expected waiting time for the packet to reach all destinations is . Finally, we achieve the total network delay as (9) Looking upon the asymptotic behaviors of the network delay when , we have , To ensure the stability of the network, the incoming rate should be less than the service rate at any stage of the network. Thus i.e., . Furthermore, the total network delay is governed by (9), which is on the order of for a fixed traffic loading value at each relay. From this discussion, we conclude the theorem. C. Maximum Capacity and Minimum Delay Although we have constructed the achievable delay and ca￾pacity if no redundancy is used, open questions are still left for the maximum capacity and the minimum delay of this network. We address these problems here by presenting the following theorems. Theorem 3: The multicast capacity of a cell-partitioned net￾work is if only a pair of a sender and receiver is active in each cell per time slot. In particular, if , the multicast capacity is . Proof: We use hop argument to prove this result. Since for any interval [0, T], the less hops the source needs to send a packet to its destinations, the more capacity it can achieve. Thus, we assume a packet is delivered directly from a source to one of its destinations via the 1-hop route “Source–destination.” Let represent the total number of packets transferred over the network from sources to destinations via the 1-hop route during the interval [0, T]. Fix . For network stability, there must be arbitrarily large values such that the sum output rate is within of the total input rate (10) If this were not the case, the total number of packets in the network would grow to infinity, and hence the network would be unstable. Since every transmission just needs 1 hop, the total number of packet transmissions in the network during the first slots is also . This value must be less than or equal to the total number of transmission opportunities , and hence (11) where represents the total number of cells containing at least two users in a particular time slot, summed over all time slots . By the law of large numbers, it is clear that as , where is the steady-state proba￾bility that there are two or more users within a particular cell and is given by (2). From (10) and (11), it follows that (12) Notice that , thus we have . Additionally, if

WANG et al:DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1361 Theorem 4:Algorithms permitting at most one transmission Finally,noticing that 1/p=c=4,we obtain that EfWmin}= in a cell at each time slot that do not use redundancy cannot ()In particular,if d=(1),EWin}=(nlogk). achieve an average delay of ()In particular,ifd- Since at any time slot,if there is more than one destination in a O(1),E{Win}=Θ(nlog. same cell as the source,only one destination could be selected Proof:The minimum delay of any packet is calculated by as the receiver,and the actual delay EWmin}for the packet to considering the situation where the network is empty and node be delivered to all the destinations will be larger or equal than 1 sends a single packet to k destinations.7 Since relaying the EWmin},which points out the theorem. packet cannot help reduce delay,it can be treated as having no Combining these results with the delay and capacity relay at all.Denote pand Wn as the chance that node I meers achieved by the 2-hop relay algorithm without redundancy,we (i.e.,two nodes move into a same cell)one of the destinations in find the exact order of the delay and capacity are (1/k)and a time slot and the minimum amount of time it takes the source e(nlog),respectively to meet all the destinations,respectively.We have that p'=1/c. Since Wnimeans that at the (1)th time slot the source has met k:-1 destinations and at the ith time slot it meets the IV.DELAY AND CAPACITY IN THE 2-HOP RELAY ALGORITHM last one,the probability Wmin=ican thus be written as WITH REDUNDANCY In this section,we adopt redundancy to improve delay.The Pw==[-01-()a-2 idea originates from a basic notion that if we send a particular packet to many nodes of the network,the chances that some +(22)-3y-1- node holding the packet reaches a destination will increase.This 13 approach is also implemented in [1]and [19].We first consider the minimum delay of 2-hop relay algorithms with redundancy. Therein the factor kp denotes that the last destination D meets Then,we design a protocol using redundancy to achieve the by the source can be any one of the k:destinations.The first term minimum delay. in the latter factor infers that D has not been met in the former i-1 time slots.Because the first term also includes the prob- A.Lower Bound of Delay ability that the source has not met D and any one of the other Here,we obtain lower bound of delay if only one transmission nodes from Di to D1.this value should be subtracted from from a sender to a receiver is permitted in a cell in the following the first term,so the second term is attached,and similarly we theorem have the following terms.Hence,the expectation of EWin} Theorem 5:There is no 2-hop algorithm with redundancy is that can provide an average delay lower than O(vnlog)if only one transmission from a sender to a receiver is permitted in a cell. Proof:To prove this result,we consider an ideal situation -2-0-()0-2 where the network is empty and only node 1 sends a single packet to destinations.Clearly,the optimal scheme for the +(22）a-31-… source is to send duplicate versions of the packet to new relays whenever possible,and if there is a destination within the same cell as the source,it will choose a destination as relay.For a =空0--(：)20- duplicate-carrying relay,it sends the packet to be relayed to the destinations as soon as it enters the same cell as a destination. Denote TN as the time required to reach thek destinations under this optimal strategy for sending a single packet. In order to avoid the interdependency of the probability that [-()+()… different destinations obtain a packet from the source or the relay nodes,we additionally assume that all the destinations within a same cell as the source or a relay node can obtain the -()+(21)-… packet during the transmission.which is referred to as a mul- tidestination reception style.Note that our assumption differs og from the multiuser reception ([1])in that usually each cell is per- (14) mitted to have a single reception,except there is more than one intended destination within a the cell.while [1]allows a trans- wherein Lemma 1 and the following identical relation for any mitted packet to be received by all other users in the same cell xET}. Then,let K:represent the total number of nodes that act as intermediate relays (including the source)at the beginning of 7By saying the network is empty,we mean only node I has packets to send slot t.Because of the limitation of 2-hop transmission,a new and other nodes have no packet and stay idle. relay can only be generated by the source.Hence,every time

WANG et al.: DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1361 Theorem 4: Algorithms permitting at most one transmission in a cell at each time slot that do not use redundancy cannot achieve an average delay of . In particular, if . Proof: The minimum delay of any packet is calculated by considering the situation where the network is empty and node 1 sends a single packet to destinations.7 Since relaying the packet cannot help reduce delay, it can be treated as having no relay at all. Denote and as the chance that node 1 meets (i.e., two nodes move into a same cell) one of the destinations in a time slot and the minimum amount of time it takes the source to meet all the destinations, respectively. We have that . Since means that at the th time slot the source has met destinations and at the th time slot it meets the last one, the probability can thus be written as (13) Therein the factor denotes that the last destination meets by the source can be any one of the destinations. The first term in the latter factor infers that has not been met in the former time slots. Because the first term also includes the prob￾ability that the source has not met and any one of the other nodes from to , this value should be subtracted from the first term, so the second term is attached, and similarly we have the following terms. Hence, the expectation of is (14) wherein Lemma 1 and the following identical relation for any are exploited: 7By saying the network is empty, we mean only node 1 has packets to send, and other nodes have no packet and stay idle. Finally, noticing that , we obtain that . In particular, if . Since at any time slot, if there is more than one destination in a same cell as the source, only one destination could be selected as the receiver, and the actual delay for the packet to be delivered to all the destinations will be larger or equal than , which points out the theorem. Combining these results with the delay and capacity achieved by the 2-hop relay algorithm without redundancy, we find the exact order of the delay and capacity are and , respectively. IV. DELAY AND CAPACITY IN THE 2-HOP RELAY ALGORITHM WITH REDUNDANCY In this section, we adopt redundancy to improve delay. The idea originates from a basic notion that if we send a particular packet to many nodes of the network, the chances that some node holding the packet reaches a destination will increase. This approach is also implemented in [1] and [19]. We first consider the minimum delay of 2-hop relay algorithms with redundancy. Then, we design a protocol using redundancy to achieve the minimum delay. A. Lower Bound of Delay Here, we obtain lower bound of delay if only one transmission from a sender to a receiver is permitted in a cell in the following theorem. Theorem 5: There is no 2-hop algorithm with redundancy that can provide an average delay lower than if only one transmission from a sender to a receiver is permitted in a cell. Proof: To prove this result, we consider an ideal situation where the network is empty and only node 1 sends a single packet to destinations. Clearly, the optimal scheme for the source is to send duplicate versions of the packet to new relays whenever possible, and if there is a destination within the same cell as the source, it will choose a destination as relay. For a duplicate-carrying relay, it sends the packet to be relayed to the destinations as soon as it enters the same cell as a destination. Denote as the time required to reach the destinations under this optimal strategy for sending a single packet. In order to avoid the interdependency of the probability that different destinations obtain a packet from the source or the relay nodes, we additionally assume that all the destinations within a same cell as the source or a relay node can obtain the packet during the transmission, which is referred to as a mul￾tidestination reception style. Note that our assumption differs from the multiuser reception ([1]) in that usually each cell is per￾mitted to have a single reception, except there is more than one intended destination within a the cell, while [1] allows a trans￾mitted packet to be received by all other users in the same cell as the transmitter. Denote as the time to reach the destina￾tions when we add the multidestination reception assumption. It is easy to see that . Then, let represent the total number of nodes that act as intermediate relays (including the source) at the beginning of slot . Because of the limitation of 2–hop transmission, a new relay can only be generated by the source. Hence, every time

1362 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.19.NO.5.OCTOBER 2011 slot,at most one node can be a new relay.Thus,we have for all then be e(nlog/A).To minimize delay,clearly we should t≥1 let (A)=(n logk/A),which yields A=(vn log).In- Kt≤t terestingly,this is exactly the lower bound of delay established (15) in Theorem 5. Observe that during slots f1,2,...,t there are at most 2-Hop Relay Algorithm With Redundancy:In every cell Kt nodes holding the packet and willing to help forward it to with at least two nodes,randomly select a sender and a re- the destinations.Hence,during this period,the probability that ceiver with uniform probability over all nodes in the cell. a destination meets at least a relay is at most 1-(1-. With equal probability,the sender is scheduled to operated in Moreover,note that since we take the multidestination recep- either“source-to-relay”transmission or“relay-to-destination' tion style,the events in which different destinations meet the transmission as described as follows. source or a relay node every time slot are independent.Thus, 1)Source-to-Relay Transmission:The sender transmits the probability that all the k destinations meet at least a relay packet SN,and does so upon every transmission oppor- during this period (1,2....t}is at most [1-(1 tunity until vnlogk duplicates have been delivered to We thus have distinct relay nodes(possibly be some of the destinations) or until the k destinations have entirely obtained SN.After such a time,the sender number is incremented to SN1. P>4≥1--(-)] If the sender does not have a new packet to send,stay idle. 2)Relay-to-Destination Transmission:When a node is sched- uled to transmit a relay packet to its destinations,the fol- 21--(-9] lowing handshake takes place. The receiver delivers its current RN number for the =1-(1-e-)(m→o. packet it desires. (16 The transmitter sends packet RN to the receiver.If the transmitter does not have the requested packet RN,it Choosingt=vn logk/d and letting k-oo,it yields that stays idle for that slot. P{T>t}≥1-(1-e-1gk If all k destinations have already received RN,the trans- mitter will delete the packet that has a SN number equal to RN in its buffer. Next,we present the performance of this algorithm. =1-e-1 (17) Theorem 6:The 2-hop relay algorithm with redundancy achieves the O(vnlogk)delay bound,with a per-node ca- Thus pacity of (1/(kvnlogk). ETw}≥E{T}≥E{T|T>t}P{T>} Proof:For the purpose of proving this theorem,we con- sider an extreme case of the packets transmissions.Note that ≥(1-e-1)Vn log k/d (18) when a new packet arrives at the head of its source queue,the as k,n-oo.From (18),we prove the theorem. time required for the packet to reach its k destinations is at most TN =T1+72,where T1 represents the time required for the B.Scheduling Scheme source to distribute vnlogk:duplicates of the packet,and 75 In Section IV-A,we considered the minimum delay of the net- represents the time required to reach all the k:destinations given work if we implement redundant packets transmissions.Here, that vn logk relay nodes hold the packet.The reason behind for acquiring the upper bound of the delay,we propose a 2-hop this claim is the submemoryless property of the random vari- relay algorithm with redundancy to achieve the minimum delay. able Ty [1],which means the residual time of Ty given that a Assume each packet is labeled with a Sender Number SN. certain number of slots have already passed before it expires is and a request number RN is delivered by the destination to the stochastically less than the original time 7N. transmitter just before transmission.In the following algorithm, Now we bound the expectations of T and T28 by taking into we let each packet be retransmitted vn logk times to distinct account the collisions among the multiple sessions. relay nodes. The ET Bound:For the duration of T1,there are at least Denoting redundancy as A,to better understand the reason n-Vnlogk nodes that do not have the packet.Let G repre- we let A=O(Vnlogk),it is intuitive to simplify a multicast sent the event that every time slot at least one of these nodes session into two phases,duplication of relays and delivery to visits the cell of the source.Hence,the probability of event G destinations,and assume they happen in sequence.Clearly,the is at least 1-(1-1)n-vngk.Given this event,the prob- duration of the first phase is (A).Consider the duration of ability that the source is chosen by the 2-hop relay algorithm the second phase,again it is convenient for us to loosely model with redundancy to transmit is expressed by the product oo2. the network as a queueing system such that every source-des- representing probabilities for the following conditionally inde- tination pair corresponds to an M/M/I queue,where the pendent events given event G:Under the condition that at last exponentially distributed service time has the average 6(n/A), one of these n-vn log k nodes visits the cell of the source,o i.e.,the expected time that a generic relay meets a specific SNote that the bounds on c(and c(are computed under suitably destination.The overall delay for a multicast session would large-values

1362 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 5, OCTOBER 2011 slot, at most one node can be a new relay. Thus, we have for all (15) Observe that during slots there are at most nodes holding the packet and willing to help forward it to the destinations. Hence, during this period, the probability that a destination meets at least a relay is at most . Moreover, note that since we take the multidestination recep￾tion style, the events in which different destinations meet the source or a relay node every time slot are independent. Thus, the probability that all the destinations meet at least a relay during this period is at most . We thus have (16) Choosing and letting , it yields that (17) Thus (18) as . From (18), we prove the theorem. B. Scheduling Scheme In Section IV-A, we considered the minimum delay of the net￾work if we implement redundant packets transmissions. Here, for acquiring the upper bound of the delay, we propose a 2-hop relay algorithm with redundancy to achieve the minimum delay. Assume each packet is labeled with a Sender Number , and a request number is delivered by the destination to the transmitter just before transmission. In the following algorithm, we let each packet be retransmitted times to distinct relay nodes. Denoting redundancy as , to better understand the reason we let , it is intuitive to simplify a multicast session into two phases, duplication of relays and delivery to destinations, and assume they happen in sequence. Clearly, the duration of the first phase is . Consider the duration of the second phase, again it is convenient for us to loosely model the network as a queueing system such that every source–des￾tination pair corresponds to an M/M/1 queue, where the exponentially distributed service time has the average , i.e., the expected time that a generic relay meets a specific destination. The overall delay for a multicast session would then be . To minimize delay, clearly we should let , which yields . In￾terestingly, this is exactly the lower bound of delay established in Theorem 5. 2-Hop Relay Algorithm With Redundancy: In every cell with at least two nodes, randomly select a sender and a re￾ceiver with uniform probability over all nodes in the cell. With equal probability, the sender is scheduled to operated in either “source-to-relay” transmission or “relay-to-destination” transmission as described as follows. 1) Source-to-Relay Transmission: The sender transmits packet , and does so upon every transmission oppor￾tunity until duplicates have been delivered to distinct relay nodes (possibly be some of the destinations) or until the destinations have entirely obtained . After such a time, the sender number is incremented to . If the sender does not have a new packet to send, stay idle. 2) Relay-to-Destination Transmission: When a node is sched￾uled to transmit a relay packet to its destinations, the fol￾lowing handshake takes place. • The receiver delivers its current number for the packet it desires. • The transmitter sends packet to the receiver. If the transmitter does not have the requested packet , it stays idle for that slot. • If all destinations have already received , the trans￾mitter will delete the packet that has a number equal to in its buffer. Next, we present the performance of this algorithm. Theorem 6: The 2-hop relay algorithm with redundancy achieves the delay bound, with a per-node ca￾pacity of . Proof: For the purpose of proving this theorem, we con￾sider an extreme case of the packets transmissions. Note that when a new packet arrives at the head of its source queue, the time required for the packet to reach its destinations is at most , where represents the time required for the source to distribute duplicates of the packet, and represents the time required to reach all the destinations given that relay nodes hold the packet. The reason behind this claim is the submemoryless property of the random vari￾able [1], which means the residual time of given that a certain number of slots have already passed before it expires is stochastically less than the original time . Now we bound the expectations of and 8 by taking into account the collisions among the multiple sessions. The Bound: For the duration of , there are at least nodes that do not have the packet. Let repre￾sent the event that every time slot at least one of these nodes visits the cell of the source. Hence, the probability of event is at least . Given this event, the prob￾ability that the source is chosen by the 2-hop relay algorithm with redundancy to transmit is expressed by the product , representing probabilities for the following conditionally inde￾pendent events given event : Under the condition that at last one of these nodes visits the cell of the source, 8Note that the bounds on ￾￾ and ￾￾ are computed under suitably large values.

WANG et al:DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1363 is the probability that the source is selected from all other nodes TABLE I in the cell to be the transmitter,and o2 represents the probability DELAY AND CAPACITY TRADEOFFS IN DIFFERENT ALGORITHMS that this source is chosen to operate in"source-to-relay"trans- scheme capacity delay mission.From [1,Lemma 6],we have a1 >1/(2+d). 2-hop relay w.o.redund Θ(】 Θ(n logk) The probability a2 that the source operates in "source-to- 2-hop relay w.redund S(kynlogE) Θ（√/n log k) relay"transmission is 1/2.Thus,every time slot during the in- multi-hop relay w.redund ( Θ(logn) terval Ti,the source delivers a duplicate packet to a new node with probability of at least o,where gorithm without and with redundancy,together with the mul- --》 n log k 1 1-e-d tihop relay algorithm with redundancy,can be summarized as 2(2+d 4+2d in Table I. Compared to the multicast capacity of static networks devel- The average time until a duplicate is transmitted to a new oped in [3],we find that capacity of the 2-hop relay algorithm node is thus a geometric variable with mean less than or equal without redundancy is better when k:=o(n).Otherwise,ca- to 1/.It is possible that two or more duplicates are delivered pacity remains the same as that of static networks,i.e.,mobility in a single time slot if we enable multiuser reception.However. cannot increase capacity.Moreover,compared to the results of in the worst case,Vn logk of these times are required,so the unicast in [1],we find that capacity diminishes by a factor of 1/ average time EfTi}is upper-bounded by vn log/. and 1/kvlog k for the 2-hop relay algorithm without and with The EfT2}Bound:To prove the bound on EfT2,let H rep- redundancy,respectively;delay increases by a factor of logk resent the event that every time slot in which there are at least and vlogk for the 2-hop relay algorithm without and with re- vnlog nodes that possess the duplicates of the packet,and dundancy,respectively.This is because we need to distribute note that event h is already a certainty with a probability of a packet to k:destinations during MotionCast.Particularly,if 1.The probability that one of these nodes transmits the packet k:=e(1),we find the results of unicast are a special case of to one of the destinations is given by the chain of probabilities our paper. 00010203.The values represent probabilities for the following Furthermore,we see that delay of the 2-hop algorithm with conditionally independent events given event H:Under the con- redundancy is better than that of the 2-hop algorithm without re- dition that there are at least vn log k:nodes that possess the du- dundancy,but its capacity is also smaller than that of the no-re- plicates of the packet in every time slot,0o represents the prob- dundancy algorithm when k:=o(vn).This suggests that re- ability that there is at least one other node in the same cell as dundant packets transmissions can reduce delay at an expense the destination (0o 1-(1-1)n-1-1-e-d),01 rep- of the capacity.The ratio between delay and capacity satisfies resents the probability that the destination is selected as the re- delay/rate >O(nk logk)for both of these two protocols.How- ceiver (similar to a1,we have 01>1/(2+d)).02 represents ever,if we fulfill the job of MotionCast by multiple unicast from the probability that the sender is operates in"relay-to-destina- the source to each of the k destinations,we find that capacity will tion"transmission (2=1/2),and 03 represents the proba- diminish by a factor of 1/k and delay will increase by a factor bility that the sender is one of the vn logk nodes that possess of k for both algorithms without and with redundancy,which in- a duplicate of the packet intended for the destination (where fers that the fundamental tradeoff for unicast established in [1] 03 =vnlogk/(n-1)>vlogk/n).Thus,every time slot, becomes delay/rate >O(nk2)in MotionCast.Thus,it turns out the probability that each destination receives a desired packet is our tradeoff is better than that of directly extending the tradeoff at leastog/n.Similar to Theorem 4.since T com- for unicast to multicast. pletes when all k:destinations receive the packet,the value of E[T2}is thus less than or equal to the logk times of the inverse B.Fundamental Delay and Capacity Tradeoff for Multicast of that quantity.Hence,.we have EfT}≤t√nog. Observing Table I,we see that the delay-capacity ratio Finally,according to [1,Lemma 21.we bound the total under these three schemes are (nklog),O(nk log),and network delay EW}=O(vnlog)and obtain that O(n(logn)2)respectively,which leads us to suppose the gen- the achievable per-node capacity under this algorithm is eral relationship between delay and capacity is that their ratio 2(1/kn log). is larger than O(nlogk). Consider a network with n users,and suppose all users re- V.FUNDAMENTAL DELAY AND CAPACITY TRADEOFF ceive packets at the same rate A.A control protocol that makes In Sections III and IV,we presented algorithms both without decisions about scheduling,routing,and packet retransmissions and with redundancy to fulfill the task of MotionCast.In this is used to stabilize the network and deliver all packets to their re- section,we first draw a comparison of the delay and capacity spective k:destinations while maintaining an average delay less with the former results.Then,we derive the fundamental delay than some threshold W.We have the following theorem. and capacity tradeoff for multicast. Theorem 7:A necessary condition for any conceivable routing and scheduling protocol with k:destinations for trans- A.Results Comparison mitting that stabilizes the network with input rates A while Recall that the multihop algorithm in [1]is based on flooding maintaining bounded average delay W is given by the message among the network.It could also serve for mul- ticast.The delay and capacity tradeoffs in the 2-hop relay al- W≥Θ(nog)1-k (19)

WANG et al.: DELAY AND CAPACITY TRADEOFF ANALYSIS FOR MotionCast 1363 is the probability that the source is selected from all other nodes in the cell to be the transmitter, and represents the probability that this source is chosen to operate in “source-to-relay” trans￾mission. From [1, Lemma 6], we have . The probability that the source operates in “source-to￾relay” transmission is . Thus, every time slot during the in￾terval , the source delivers a duplicate packet to a new node with probability of at least , where The average time until a duplicate is transmitted to a new node is thus a geometric variable with mean less than or equal to . It is possible that two or more duplicates are delivered in a single time slot if we enable multiuser reception. However, in the worst case, of these times are required, so the average time is upper-bounded by . The Bound: To prove the bound on , let rep￾resent the event that every time slot in which there are at least nodes that possess the duplicates of the packet, and note that event is already a certainty with a probability of 1. The probability that one of these nodes transmits the packet to one of the destinations is given by the chain of probabilities . The values represent probabilities for the following conditionally independent events given event : Under the con￾dition that there are at least nodes that possess the du￾plicates of the packet in every time slot, represents the prob￾ability that there is at least one other node in the same cell as the destination rep￾resents the probability that the destination is selected as the re￾ceiver (similar to , we have ), represents the probability that the sender is operates in “relay-to-destina￾tion” transmission , and represents the proba￾bility that the sender is one of the nodes that possess a duplicate of the packet intended for the destination (where ). Thus, every time slot, the probability that each destination receives a desired packet is at least . Similar to Theorem 4, since com￾pletes when all destinations receive the packet, the value of is thus less than or equal to the times of the inverse of that quantity. Hence, we have . Finally, according to [1, Lemma 2], we bound the total network delay and obtain that the achievable per-node capacity under this algorithm is . V. FUNDAMENTAL DELAY AND CAPACITY TRADEOFF In Sections III and IV, we presented algorithms both without and with redundancy to fulfill the task of MotionCast. In this section, we first draw a comparison of the delay and capacity with the former results. Then, we derive the fundamental delay and capacity tradeoff for multicast. A. Results Comparison Recall that the multihop algorithm in [1] is based on flooding the message among the network. It could also serve for mul￾ticast. The delay and capacity tradeoffs in the 2-hop relay al￾TABLE I DELAY AND CAPACITY TRADEOFFS IN DIFFERENT ALGORITHMS gorithm without and with redundancy, together with the mul￾tihop relay algorithm with redundancy, can be summarized as in Table I. Compared to the multicast capacity of static networks devel￾oped in [3], we find that capacity of the 2-hop relay algorithm without redundancy is better when . Otherwise, ca￾pacity remains the same as that of static networks, i.e., mobility cannot increase capacity. Moreover, compared to the results of unicast in [1], we find that capacity diminishes by a factor of and for the 2-hop relay algorithm without and with redundancy, respectively; delay increases by a factor of and for the 2-hop relay algorithm without and with re￾dundancy, respectively. This is because we need to distribute a packet to destinations during MotionCast. Particularly, if , we find the results of unicast are a special case of our paper. Furthermore, we see that delay of the 2-hop algorithm with redundancy is better than that of the 2-hop algorithm without re￾dundancy, but its capacity is also smaller than that of the no-re￾dundancy algorithm when . This suggests that re￾dundant packets transmissions can reduce delay at an expense of the capacity. The ratio between delay and capacity satisfies delay/rate for both of these two protocols. How￾ever, if we fulfill the job of MotionCast by multiple unicast from the source to each of the destinations, we find that capacity will diminish by a factor of and delay will increase by a factor of for both algorithms without and with redundancy, which in￾fers that the fundamental tradeoff for unicast established in [1] becomes delay/rate in MotionCast. Thus, it turns out our tradeoff is better than that of directly extending the tradeoff for unicast to multicast. B. Fundamental Delay and Capacity Tradeoff for Multicast Observing Table I, we see that the delay–capacity ratio under these three schemes are and respectively, which leads us to suppose the gen￾eral relationship between delay and capacity is that their ratio is larger than . Consider a network with users, and suppose all users re￾ceive packets at the same rate . A control protocol that makes decisions about scheduling, routing, and packet retransmissions is used to stabilize the network and deliver all packets to their re￾spective destinations while maintaining an average delay less than some threshold . We have the following theorem. Theorem 7: A necessary condition for any conceivable routing and scheduling protocol with destinations for trans￾mitting that stabilizes the network with input rates while maintaining bounded average delay is given by (19)