MotionCast: on the capacity and delay tradeoffs
MotionCast: on the capacity and delay tradeoffs
复制标题
DOI：
10.1145/1530748.1530789
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Chenhui Hu;Xinbing Wang;Feng Wu
中科院分区：
文献类型：
--
作者：
Chenhui Hu;Xinbing Wang;Feng Wu
本文将adhoc网络中基于节点移动性的组播定义为MotionCast，并研究了其容量和时延的权衡问题。模式，每个节点都希望将数据包发送到k个不同的目的地，我们比较了两种传输协议的容量和延迟：一种是采用无冗余的两跳中继算法，另一种是采用冗余数据包传输方案，以牺牲容量为代价来改善延迟。此外，我们还得到了在一定的约束条件下的最大容量和最小延迟。我们发现，无冗余的2跳算法的每节点容量和时延分别为Θ（1/k）和Θ（nlog k），有冗余的2跳算法的每节点容量和时延分别为Ω（1/（k <$nlog k））和Θ（<$nlog k）.当k在顺序意义上严格小于n时，无冗余的2跳中继算法的容量优于[3]中提出的静态网络的多播容量;而当k=Θ（n）时，移动性不再增加容量。对于这两种协议，延迟与容量之比满足延迟/速率≥ O（nklog k），这小于直接将[1]中建立的单播的基本折衷扩展到多播，即，时间复杂度为O（nk 2）。
In this paper, we define multicast for ad hoc network through nodes' mobility as MotionCast, and study the capacity and delay tradeoffs for it. Assuming nodes move according to an independently and identically distributed (i.i.d.) pattern and each desires to send packets to k distinctive destinations, we compare the capacity and delay 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 capacity and delay for 2-hop algorithm without redundancy are Θ(1/k) and Θ(nlog k), respectively; and for 2-hop algorithm with redundancy they are Ω(1/(k√nlog k)) and Θ(√nlog k), respectively. The capacity of the 2-hop relay algorithm without redundancy is better than the multicast capacity of static networks developed in [3] as long as k is strictly less than n in an order sense; while when k=Θ(n), mobility does not increase capacity anymore. The ratio between delay and capacity satisfies delay/rate ≥ O(nklog k) for these two protocols, which is smaller than that of directly extending the fundamental tradeoff for unicast established in [1] to multicast, i.e., O(nk2).