06-02-2013, 02:51 PM
Speed Improves Delay-Capacity Trade-Off in MotionCast
[attachment=49834]
Abstract
In this paper, we study a unified mobility model for mobile multicast (MotionCast) with n nodes, and k destinations for each
multicast session. This model considers nodes which can either serve in a local region or move around globally, with a restricted speed
R. In other words, there are two particular forms: Local-based Speed-Restricted Model (LSRM) and Global-based Speed-Restricted
Model (GSRM). We find that there is a special turning point when mobility speed varies from zero to the scale of network. As k increases from 1 to n 1, the region that mobility can improve delay-capacity trade-off is enlarged. When
R ¼ ð1Þ, the optimal delay-capacity trade-off ratio is achieved. This paper presents a general approach to study the performance of
wireless networks under more flexible mobility models.
INTRODUCTION
Delay-capacity trade-off was first studied by Bansal and
Liu [3]. They considered a mobile network with stationary
sources and destinations, and proposed a geographic
routing scheme to approach the optimal capacity. Later
studies, such as Perevalov and Blum [4], studied network
capacity in a delay-limited mobile ad hoc network. Recent
studies, for example, Neely and Modiano [5], presented a
strategy utilizing redundant packets transmissions to reduce
delay at the sacrifice of capacity.
NETWORK MODEL
Transmission Model
In our paper, we assume a similar transmission protocol
model raised in [1], it is derivative from a widely used
physical interference model as Shannmon Capacity:
C ¼ W log2ð1 þ SINRÞ;
where SINR is the signal to interference and noise ratio.
And our proposed model is identical to this famous model,
which is also proved in [1]. The whole network is placed in
a 1 1 sized square area, with totally n nodes. All of these
nodes are uniformly and randomly deployed at the very
beginning. We use protocol interference model, which
means node vi can transmit data to node vj, iff their mutual
distance satisfies dðvi; vjÞ < r. And any other node vk 6¼ vi; vj
that within vj’s transmission range, namely dðvk; vjÞ < r,
cannot transmit simultaneously. We assume that each node
transmits exactly one packet to exactly one receiver in a
single time slot, if this node is permitted to transmit and
transmission errors can be avoided if the transmission
protocol is satisfied. The sending node cannot transmit a
fraction of one packet. We also do not consider network
coding strategy so that a sender cannot transmit data to
various receivers in a same time slot.
GSRM
In LSRM, the centers of all circles where nodes move around
are fixed after the nodes have been initially deployed.
However, in GSRM, we also let the centers of these circles
move. They are the positions of the nodes in the previous
time slot. Since speed is restricted by R, the radius of these
circles are also R. Nodes can move to any point of the current
circles in uniform probability at each time slot.
Obviously, all the nodes can reach the whole network
region in this model, but the distance of each hop is
restricted by R. Notice that when R is zero, the network is
stationary treated as Markov Model;4 when R ¼ ð1Þ, the corresponding
mobility pattern comes to i.i.d again. Fig. 4 shows the
movement of three different nodes.
Definition of Redundancy
Redundancy is an important concept in wireless network.
The same packet maybe transmitted more than once. This
could be three reasons: multihop, data-copy, and multicast
scheme. We define redundancy as the average number of
transmissions for each packet in the network.
Multihop is commonly used in stationary network.
When the source and the destination are so far separated
that such distance exceeds the source’s transmission range,
relays are necessary. A group of relays are chosen from the
network and then form a chain route for the packet
traveling from the source to the destination. Actually, in
the network if nodes cannot traverse to every position in the
network area, multihop is necessary. When the chain is
composed of one source, one destination, and m 1 relays,
the packet will be transmitted for m times, and the
redundancy is therefore m.
Data-copy is another kind of redundancy, which is
widely used in mobility network, such as i.i.d network. In
MANET, if the source transmits data to the destination by
ceaseless moving until their separation distance is shorter
than transmission range, it takes very long time to finish a
session when the transmission range is small. To reduce the
delay, we choose a group of nodes as relays. The source
hands out its packet to all these relays. Since there is much
more chance for the destination to meet many relays than to
meet a single source, the overall delay decreases. Suppose
each source hands out its packet to m 1 relays, and the
packet is transmitted for m times, including m 1
transmissions for handing out and once for one of the
relays transmits the packet to the destination.
Generalized Transmission Range
Generalized transmission range is defined as the largest
range that nodes can communicate via mobility. This range
consists of radius of moving area and node’s transmission
range. Since the radius of active area is much larger than
transmission range itself, we simply regard the node’s
transmission range as the radius of active area.
When transmission range R is settled, we have to find
out how many nodes can this node communicate directly.
Since the network is deployed randomly and uniformly, the
average number of nodes inside an active area is nR2.
However, we cannot ensure there are nR2 nodes in the
area w.h.p for all active areas. Under this circumstance, it is
hard to determine how many nodes are available in
scheduling algorithm, and the network may not be
connected w.h.
CONCLUSION
In this paper, we study the relationship between mobility
speed R and delay-capacity trade-off ratio. We show that
increasing mobility speed R can improve delay-capacity
trade-off in multicast network when R is in a specified
region. Such region is larger or less than a certain turning
point, depending on k and n, which shows that the
increasing mobility speed does not always improve delaycapacity
trade-off.
We provide a general Speed-Restricted mobility Model,
including two particular forms LSRM and GSRM. In
different forms, the mobility speed R influences the delaycapacity
trade-off in different manners. Both two cases
converge to i.i.d when R ¼ ð1Þ, which has optimal D/C
trade-off ratio. In both LSRM and GSRM, as k increases, the
range of Improvement Region becomes larger so that the
impact of mobility is more significant. Such results of
MANET can explicitly explain the impact of velocity to
distributed system, thus can be utilized to understand the
asymptotic achievable capacity when we want to distribute
mobile sensors in a region. We have not studied the impact
of larger transmission range and the combination of LSRM
and GSRM, which could be future works.
[attachment=49834]
Abstract
In this paper, we study a unified mobility model for mobile multicast (MotionCast) with n nodes, and k destinations for each
multicast session. This model considers nodes which can either serve in a local region or move around globally, with a restricted speed
R. In other words, there are two particular forms: Local-based Speed-Restricted Model (LSRM) and Global-based Speed-Restricted
Model (GSRM). We find that there is a special turning point when mobility speed varies from zero to the scale of network. As k increases from 1 to n 1, the region that mobility can improve delay-capacity trade-off is enlarged. When
R ¼ ð1Þ, the optimal delay-capacity trade-off ratio is achieved. This paper presents a general approach to study the performance of
wireless networks under more flexible mobility models.
INTRODUCTION
Delay-capacity trade-off was first studied by Bansal and
Liu [3]. They considered a mobile network with stationary
sources and destinations, and proposed a geographic
routing scheme to approach the optimal capacity. Later
studies, such as Perevalov and Blum [4], studied network
capacity in a delay-limited mobile ad hoc network. Recent
studies, for example, Neely and Modiano [5], presented a
strategy utilizing redundant packets transmissions to reduce
delay at the sacrifice of capacity.
NETWORK MODEL
Transmission Model
In our paper, we assume a similar transmission protocol
model raised in [1], it is derivative from a widely used
physical interference model as Shannmon Capacity:
C ¼ W log2ð1 þ SINRÞ;
where SINR is the signal to interference and noise ratio.
And our proposed model is identical to this famous model,
which is also proved in [1]. The whole network is placed in
a 1 1 sized square area, with totally n nodes. All of these
nodes are uniformly and randomly deployed at the very
beginning. We use protocol interference model, which
means node vi can transmit data to node vj, iff their mutual
distance satisfies dðvi; vjÞ < r. And any other node vk 6¼ vi; vj
that within vj’s transmission range, namely dðvk; vjÞ < r,
cannot transmit simultaneously. We assume that each node
transmits exactly one packet to exactly one receiver in a
single time slot, if this node is permitted to transmit and
transmission errors can be avoided if the transmission
protocol is satisfied. The sending node cannot transmit a
fraction of one packet. We also do not consider network
coding strategy so that a sender cannot transmit data to
various receivers in a same time slot.
GSRM
In LSRM, the centers of all circles where nodes move around
are fixed after the nodes have been initially deployed.
However, in GSRM, we also let the centers of these circles
move. They are the positions of the nodes in the previous
time slot. Since speed is restricted by R, the radius of these
circles are also R. Nodes can move to any point of the current
circles in uniform probability at each time slot.
Obviously, all the nodes can reach the whole network
region in this model, but the distance of each hop is
restricted by R. Notice that when R is zero, the network is
stationary treated as Markov Model;4 when R ¼ ð1Þ, the corresponding
mobility pattern comes to i.i.d again. Fig. 4 shows the
movement of three different nodes.
Definition of Redundancy
Redundancy is an important concept in wireless network.
The same packet maybe transmitted more than once. This
could be three reasons: multihop, data-copy, and multicast
scheme. We define redundancy as the average number of
transmissions for each packet in the network.
Multihop is commonly used in stationary network.
When the source and the destination are so far separated
that such distance exceeds the source’s transmission range,
relays are necessary. A group of relays are chosen from the
network and then form a chain route for the packet
traveling from the source to the destination. Actually, in
the network if nodes cannot traverse to every position in the
network area, multihop is necessary. When the chain is
composed of one source, one destination, and m 1 relays,
the packet will be transmitted for m times, and the
redundancy is therefore m.
Data-copy is another kind of redundancy, which is
widely used in mobility network, such as i.i.d network. In
MANET, if the source transmits data to the destination by
ceaseless moving until their separation distance is shorter
than transmission range, it takes very long time to finish a
session when the transmission range is small. To reduce the
delay, we choose a group of nodes as relays. The source
hands out its packet to all these relays. Since there is much
more chance for the destination to meet many relays than to
meet a single source, the overall delay decreases. Suppose
each source hands out its packet to m 1 relays, and the
packet is transmitted for m times, including m 1
transmissions for handing out and once for one of the
relays transmits the packet to the destination.
Generalized Transmission Range
Generalized transmission range is defined as the largest
range that nodes can communicate via mobility. This range
consists of radius of moving area and node’s transmission
range. Since the radius of active area is much larger than
transmission range itself, we simply regard the node’s
transmission range as the radius of active area.
When transmission range R is settled, we have to find
out how many nodes can this node communicate directly.
Since the network is deployed randomly and uniformly, the
average number of nodes inside an active area is nR2.
However, we cannot ensure there are nR2 nodes in the
area w.h.p for all active areas. Under this circumstance, it is
hard to determine how many nodes are available in
scheduling algorithm, and the network may not be
connected w.h.
CONCLUSION
In this paper, we study the relationship between mobility
speed R and delay-capacity trade-off ratio. We show that
increasing mobility speed R can improve delay-capacity
trade-off in multicast network when R is in a specified
region. Such region is larger or less than a certain turning
point, depending on k and n, which shows that the
increasing mobility speed does not always improve delaycapacity
trade-off.
We provide a general Speed-Restricted mobility Model,
including two particular forms LSRM and GSRM. In
different forms, the mobility speed R influences the delaycapacity
trade-off in different manners. Both two cases
converge to i.i.d when R ¼ ð1Þ, which has optimal D/C
trade-off ratio. In both LSRM and GSRM, as k increases, the
range of Improvement Region becomes larger so that the
impact of mobility is more significant. Such results of
MANET can explicitly explain the impact of velocity to
distributed system, thus can be utilized to understand the
asymptotic achievable capacity when we want to distribute
mobile sensors in a region. We have not studied the impact
of larger transmission range and the combination of LSRM
and GSRM, which could be future works.