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 network 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 , mobility 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 importantly, 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 collection of wireless mobile nodes dynamically forming a temporary network without the support of any network infrastructure or centralized control. In these networks, nodes often operate 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 supported by the National Basic Research Program of China (973 Program) under Grant 2011CB302701, NSF China under Grant 60832005, the China Ministry of Education Fok Ying Tung Fund under Grant 122002, 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 information 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 exploiting 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]. Several 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 multicast capacity is when , and is when . Their results generalize previous capacity bounds on unicast [4] and broadcast [5]. Under a more general Guassian channel model, multicast capacity is investigated 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 unicast. 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 paradigm, 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 disruption-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 interesting 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 exploiting 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 redundant 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 construct 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 limiting 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 capacity and delay tadeoffs in MANETs with multicast traffic. Because a key feature of multicast in MANETs is that packets can be delivered via nodes’ mobility, we refer it as MotionCast. Intuitively, 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 fundamental 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 generalized version of the algorithm presented in [1] and corresponds to a decoupled queuing model. Because destinations are associated 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 destinations (referred to as noncooperative mode). In this case, the packet may be carried to the destinations either through the relays or via the source, but will not be passed from one destination 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 permitting information dissemination among destinations (cooperative 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 designated 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 noncooperative 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 receive 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 algorithm with redundancy, the capacity is with the delay scaling as . Thus, delay and capacity tradeoffs emerge between these two algorithms, i.e., we can utilize redundant 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 Section 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 communicate 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 interference 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 sometimes 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 mathematical 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 relationships before the transmissions start. In particular, we assume 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 independently 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 probability 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 corresponding 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 redundancy. 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, randomly select such a pair uniformly over all possible pairs in the cell. If the source has a new packet in the buffer intended 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 receiver. 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 distribution, 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 transmitted 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 destination. 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 another 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’ information 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 possible, 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 necessary 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 destination. 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 (because 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