MotionCast：On the Capacity and Delay Tradeoffs

上游充通大￥ SHANGHAI JIAO TONG UNIVERSITY MotionCast:On the Capacity and Delay Tradeoffs Chenhui Hul,Xinbing Wang1,Feng Wu2 1 Institute of Wireless Communication Technology(IWCT) Shanghai Jiao Tong University 2 Microsoft Research Asia

MotionCast: On the Capacity and Delay Tradeoffs Chenhui Hu1, Xinbing Wang1, Feng Wu2 1 Institute of Wireless Communication Technology (IWCT) Shanghai Jiao Tong University 2 Microsoft Research Asia

Outline 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY ▣Introduction Motivations Related works >Objectives Q Network Modeland Definition Q2-hop Relay Algorithm Without Redundancy Q2-hop Relay Algorithm With Redundancy ▣Discussion Q Conclusion and Future Work MotionCast:On the Capacity and Delay Tradeoffs 2

MotionCast: On the Capacity and Delay Tradeoffs 2 Outline ❑ Introduction ➢ Motivations ➢ Related works ➢ Objectives ❑ Network Model and Definition ❑ 2-hop Relay Algorithm Without Redundancy ❑ 2-hop Relay Algorithm With Redundancy ❑ Discussion ❑ Conclusion and Future Work

Motivations 上洋充通大￥ SHANGHAI JIAO TONG UNIVERSITY Multicast Multicast in MANETs One-to-many communication >Group communications in military networks,disaster alarming in sensor networks and mobile multimedia services Key feature of multicast in MANETs is that packets can be delivered via nodes'mobility,thus we refer it as MotionCast. Traditional works study the multicast capacity in static networks,while we have already known that mobility can increase capacity for unicast and there involves capacity and delay tradeoffs. R D mobility Mobile Routing Static Multicast Tree MotionCast:On the Capacity and Delay Tradeoffs 3

MotionCast: On the Capacity and Delay Tradeoffs 3 Motivations S R R R R D D D Static Multicast Tree ❑ Multicast & Multicast in MANETs ➢ One-to-many communication ➢ Group communications in military networks, disaster alarming in sensor networks and mobile multimedia services ❑ Key feature of multicast in MANETs is that packets can be delivered via nodes’ mobility, thus we refer it as MotionCast . ❑ Traditional works study the multicast capacity in static networks, while we have already known that mobility can increase capacity for unicast and there involves capacity and delay tradeoffs. S R D D D mobility Mobile Routing

Related works l/lI 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY Compared with multiple unicast,capacity gain can be obtained by using multicast. >In [3],Li et al.show that the per-node multicast capacity is When:the per-node multicast capacityis Θ( ⊙() whenk-2().These results generalize the previous capacity bound on unicast by Gupta and Kumar [4]and broadcast [5]. > In [6],Jacquet et al.consider multicast capacity by accounting the ratio of the total number of hops for multicast and the average number of hops for unicast. In [7],Shakkottai et al.propose a comb-based architecture for multicast routing. [3]X.Li,S.Tang and O.Frieder,"Multicast capacity for large scale wireless ad hoc networks,"in Proceedings of ACM MobiCom,Sept.2007. MotionCast:On the Capacity and Delay Tradeoffs 4

MotionCast: On the Capacity and Delay Tradeoffs 4 Related works – I/II ❑ Compared with multiple unicast, capacity gain can be obtained by using multicast. ➢ In [3], Li et al. show that the per-node multicast capacity is when ; the per-node multicast capacity is when . These results generalize the previous capacity bound on unicast by Gupta and Kumar [4] and broadcast [5]. ➢ In [6], Jacquet et al. consider multicast capacity by accounting the ratio of the total number of hops for multicast and the average number of hops for unicast. ➢ In [7], Shakkottai et al. propose a comb-based architecture for multicast routing. [3] X. Li, S. Tang and O. Frieder, ‘’Multicast capacity for large scale wireless ad hoc networks,'' in Proceedings of ACM MobiCom, Sept. 2007

Related works ll/ll 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY While the above studies are all based on static networks, the effect of mobility has been investigated in the following literatures: In [8],Grossglauser and Tse demonstrate that per-node unicast capacity does not vanish as the size of the network grows by implementing a 2-hop relay algorithm. Note that the price of this improving capacity is the increased delay. It has been shown in [1]that the 2-hop relay algorithm in [8]yields a tremendous average delay of.(n) > The relationships between capacity and delay are further investigated in the literatures of [1][2][9][10]. [1]M.J.Neely,and E.Modiano,"Capacity and delay tradeoffs for ad hoc mobile networks,"IEEE Transactions on Information Theory,vol.51,no.6,pp.1917-1937,Jun. 2005. [8]M.Grossglauser and D.N.C.Tse,"Mobility increases the capacity of ad hoc wireless networks,"IEEE/ACM Transactions on Networking,vol.10,no.4,pp.477-486,Aug 2002. MotionCast:On the Capacity and Delay Tradeoffs 5

MotionCast: On the Capacity and Delay Tradeoffs 5 Related works – II/II ❑ While the above studies are all based on static networks, the effect of mobility has been investigated in the following literatures: ➢ In [8], Grossglauser and Tse demonstrate that per-node unicast capacity does not vanish as the size of the network grows by implementing a 2-hop relay algorithm. ➢ Note that the price of this improving capacity is the increased delay. It has been shown in [1] that the 2-hop relay algorithm in [8] yields a tremendous average delay of . ➢ The relationships between capacity and delay are further investigated in the literatures of [1][2][9][10]. [1] M. J. Neely, and E. Modiano, ‘’Capacity and delay tradeoffs for ad hoc mobile networks,'' IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1917-1937, Jun. 2005. [8] M. Grossglauser and D. N. C. Tse, ‘’Mobility increases the capacity of ad hoc wireless networks,'' IEEE/ACM Transactions on Networking, vol. 10, no. 4, pp. 477-486, Aug. 2002

Objectives 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY In this paper,we answer the following questions: >What is the maximum per-node MotionCast capacity? >How long will be the induced delay to achieve this capacity and what is the minimum delay? How does the capacity and delay tradeoffs emerge for MotionCast? MotionCast:On the Capacity and Delay Tradeoffs 6

MotionCast: On the Capacity and Delay Tradeoffs 6 Objectives ❑ In this paper, we answer the following questions: ➢ What is the maximum per-node MotionCast capacity? ➢ How long will be the induced delay to achieve this capacity and what is the minimum delay? ➢ How does the capacity and delay tradeoffs emerge for MotionCast?

Outline 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY ▣Introduction Network Model and Definition Q2-hop Relay Algorithm Without Redundancy Q2-hop Relay Algorithm With Redundancy ▣Discussion Conclusion and Future Work MotionCast:On the Capacity and Delay Tradeoffs 7

MotionCast: On the Capacity and Delay Tradeoffs 7 Outline ❑ Introduction ❑ Network Model and Definition ❑ 2-hop Relay Algorithm Without Redundancy ❑ 2-hop Relay Algorithm With Redundancy ❑ Discussion ❑ Conclusion and Future Work

Network Model and Definition l/lll 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY Cell partitioned Network: The network is a unit square and there aren mobile nodes in it. Divide it intoc =e(n)cells with equal size. >Nodes can communicate with each other only when they are within a same cell. ▣Mobility Model: Divide time into constant duration slots. >1.I.D.mobility model. - The initial position of each node is equally likely to be any of the c cells independent of others.And 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. This model captures the characteristic of the infinite mobility.With the help of mobility,packets can be carried by the nodes until they reach the destinations. MotionCast:On the Capacity and Delay Tradeoffs 8

MotionCast: On the Capacity and Delay Tradeoffs 8 Network Model and Definition – I/III ❑ Cell partitioned Network: ➢ The network is a unit square and there are mobile nodes in it. Divide it into cells with equal size. ➢ Nodes can communicate with each other only when they are within a same cell. ❑ Mobility Model: ➢ Divide time into constant duration slots. ➢ I.I.D. mobility model. – The initial position of each node is equally likely to be any of the cells independent of others. And 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. ➢ This model captures the characteristic of the infinite mobility. With the help of mobility, packets can be carried by the nodes until they reach the destinations

Network Model and Definition ll/lll 上浒充通大粤 SHANGHAI JIAO TONG UNIVERSITY ▣ Traffic Pattern:Number all the nodes from 1 to n,we assume each node is a source node associated with=k(n)randomly and independently 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 destinations respectively through a common wireless channel. A cell partitioned MANET model with c cells and n mobile nodes under multicast traffic pattern. (a)Network model. (b)Traffic pattern MotionCast:On the Capacity and Delay Tradeoffs 9

MotionCast: On the Capacity and Delay Tradeoffs 9 Network Model and Definition – II/III ❑ Traffic Pattern: Number all the nodes from 1 to , we assume 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. A cell partitioned MANET model with c cells and n mobile nodes under multicast traffic pattern

Network Model and Definition lll/II 上游充通大 SHANGHAI JIAO TONG UNIVERSITY Definition of Capacity: For a fixed Ai,the network is stable if there exists a scheduling algorithm so that the queue in each node does not grow to infinity as time goes to infinity. The per-node capacity of the network is the maximum rate that it can stably support. 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. Definition of Redundancy: >At each timeslot,if more than one nodes performing as relays 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 a destination 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 non-cooperative mode. MotionCast:On the Capacity and Delay Tradeoffs 10

MotionCast: On the Capacity and Delay Tradeoffs 10 Network Model and Definition – III/III ❑ Definition of Capacity: ➢ For a fixed , the network is stable if there exists a scheduling algorithm so that the queue in each node does not grow to infinity as time goes to infinity. ➢ The per-node capacity of the network is the maximum rate that it can stably support. ❑ 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. ❑ Definition of Redundancy: ➢ At each timeslot, if more than one nodes performing as relays 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 a destination 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 non-cooperative mode