17-11-2012, 04:39 PM
Rateless Forward Error Correction for Topology-Transparent Scheduling
1Rateless Forward Error Correction.pdf (Size: 553.71 KB / Downloads: 21)
Abstract
Topology-transparent scheduling for mobile wireless
ad hoc networks has been treated as a theoretical curiosity. This
paper makes two contributions towards its practical deployment:
1) We generalize the combinatorial requirement on the schedules
and show that the solution is a cover-free family. As a result, a much
wider number and variety of constructions for schedules exist to
match network conditions. 2) In simulation, we closely match the
theoretical bound on expected throughput. The bound was derived
assuming acknowledgments are available immediately. We use
rateless forward error correction (RFEC) as an acknowledgment
scheme with minimal computational overhead. Since the wireless
medium is inherently unreliable, RFEC also offers some measure
of automatic adaptation to channel load. These contributions
renew interest in topology-transparent scheduling when delay is
a principal objective.
INTRODUCTION
Amobile ad hoc network (MANET) is a collection of mobile
wireless nodes that establish communication without
any centralized control or fixed infrastructure. Since the radio
transmission range of each node is limited, a packet may be forwarded
over multiple hops to reach its destination. This limitation
also introduces the potential for spatial channel reuse. Most
medium access control (MAC) protocols attempt to exploit this
potential in order to minimize delay and maximize throughput
on a per hop basis.
Scheduled approaches to channel access provide deterministic
rather than probabilistic delay guarantees. This is important
for applications sensitive to maximum delay. Furthermore, the
control overhead and carrier sensing associated with contention
MAC protocols can be considerable in terms of time and energy
[1]. The challenge with scheduling is to achieve a reasonable
throughput objective.
ACKNOWLEDGMENT SCHEMES
To approach the theoretical bound for expected throughput
of topology-transparent scheduling in practice an acknowledgment
scheme is required. Without an acknowledgment, a node
must transmit the same packet in each of its assigned slots to
guarantee reception to a specific neighbor. This is because while
the schedule guarantees a collision-free slot to each neighbor by
the end of the frame, it is not known which of its slots is successful
to a specific neighbor; this depends on the schedules of
the nodes currently in its neighborhood.
Rateless Forward Error Correction for Acknowledgment
Rateless FEC overcomes numerous concerns with acknowledgment
in topology-transparent schemes. Among the rateless
FEC codes currently available, we use Luby Transform (LT)
codes [7]. The LT process is capable of generating a potentially
infinite number of equally useful symbols from a given
input, giving the codes immunity to tolerate arbitrary losses in
the channel. This makes LT codes an effective coding technique
for wireless channels.
EXPERIMENTAL SET-UP AND RESULTS
In this section, simulations are described to compare
topology-transparent scheduling using an RFEC based acknowledgment
scheme with the performance using omniscient
acknowledgment (OMN). At least in simulation, the transmitter
can be omniscient about the outcome of its transmissions. This
has been colloquially referred to as magic acknowledgment.
For our purposes, while it cannot be implemented in practice,
it gives us an ideal situation with which any real acknowledgment
scheme can be compared to assess the overhead due to
acknowledgments.
ADAPTATION TO NETWORK DYNAMICS
Most of the analysis for topology-transparent scheduling has
focused on a single frame; while this is a reasonable view for
studying minimum throughput, it ignores what happens when
the design parameter is exceeded. Ju et al. [5] argue that by
selecting a larger frame length, their choice is (relatively) insensitive
to the degree limitation; essentially they “over-engineer”
the system to permit more neighbors than the design criteria
stipulate. Nevertheless, their scheme can fail totally when
the number of neighbors exceeds the capacity of their chosen
scheme, despite its continued operation for some number of
neighbors larger than the stipulated number.
CONCLUSION
Topology-transparent scheduling has suffered from many
drawbacks. In this paper, we have established that the combinatorial
construction of such schemes can be done much more
generally than previously suggested. The combinatorial characterization
leads not only to more general construction schemes
but also to analytic results suggesting that topology-transparent
schemes retain strong throughput and delay performance even
when in an environment with neighborhoods larger than anticipated.
The fundamental problem, from the beginning, has been to
develop a realistic acknowledgment model that realizes the performance
indicated by a theory based on omniscient acknowledgment
(OMN) and in which collision is the only cause of erasures.
Rateless forward error correction (RFEC) has been proposed
here as a solution, and a practical implementation using
LT codes described. We emphasize that LT codes is just one of
a number of schemes that could be used.