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