20-10-2012, 04:01 PM
Towards a Practical and Fair Rate Allocation forMultihop Wireless Networks based on a Simple Node Model
Towards a Practical.pdf (Size: 246.73 KB / Downloads: 22)
Abstract:
IEEE 802.11 is often considered as the underlying wireless technology of multihop wireless networks.
But the use of 802.11 in such networks raises issues, like efficiency and/or fairness issues. Different
kinds of solutions have been proposed to overcome these problems. One approach is to design new MAC protocols
that provide alternatives to the IEEE 802.11 MAC protocol. Although these solutions are of some interest,
it should probably take some time before new wireless network interface cards based on one of these solutions
are developed and released. Another approach is to consider that 802.11 will remain the underlying wireless
technology and to design solutions above it. Several solutions based on rate allocation have been proposed so
far. The main drawback of the proposed solutions is that they rely on a radio medium sharing model that is
difficult to compute in a wireless, distributed and mobile environment. Indeed, very few of these solutions have
been derived into a network protocol.
Introduction
IEEE 802.11 is often considered as the underlying wireless technology of multihop wireless networks. But the
use of 802.11 in such networks raises some issues. The two main problems concern fairness and efficiency [2].
With the fairness issue, some flows obtain very small throughput (even null in some cases), while some others
can almost use the whole capacity of the wireless medium. With the efficiency issue, a part of the network
capacity is not used and wasted, even if the flow rates are increased. These problems are mainly caused by the
MAC protocol of 802.11.
Different kinds of solutions have been proposed to overcome these problems. One approach is to design
new MAC protocols that provide alternatives to the IEEE 802.11MAC protocol and that try to increase fairness
or/and efficiency in the network. More and more solutions are now proposed. However, the main challenge,
when designing a MAC protocol for wireless multihop networks, is still to achieve a good trade-off between
efficiency and fairness. Some solutions are fair at the price of a low efficiency while the others are efficient but
achieve a low fairness. Although these solutions are of some interest, it should probably take some time before
new wireless network interface cards based on one of these solutions are developed and released. Moreover, as
these solutions try to be as simple and local as possible (important features for a MAC protocol), it is difficult
for them to tend towards a targeted fairness scheme.
Modeling the radio medium sharing
Few solutions have been proposed for rate allocation of multihop flows in multihop wireless networks. However,
modeling the radio medium sharing in such networks is a challenging task that has been addressed in
several studies. In this section, we describe the main models that have been used to represent the constraints
that arise in these networks. We also highlight the main references that deal with rate allocation of multihop
flows.
But before describing these models, we remind the different ranges that are used in IEEE 802.11. The
transmission range is the range within which a frame can be successfuly transmitted. The carrier sensing
range is the range within which a node detects a transmission (and thus it refrains itself from transmitting). The
interference range is the range within which a transmitting node (other than the associated source) will induce
collisions at the receiver, which happens as soon as the signal-to-interference ratio at the receiver is smaller
than a given threshold often called capture threshold.
The two seminal contention models
In [7], the authors introduce two contention models, i.e. the protocol model and the physical model. In the
protocol model, a node can successfully receive packets from another node if these two nodes are within
transmission range and no other node is transmitting within the interference range of the receiver. It is possible
to adapt this model to IEEE 802.11-style MAC protocols by also ensuring that no other node is transmitting
within the carrier sensing range and the interference range (in order to receive the ACKs successfully) of the
sender. In the physical model, a transmission is successfully received if the signal-to-interference ratio at the
receiver is not smaller than the capture threshold.
Row constraints
In the work of [8], the authors also propose another set of sufficient conditions based on the links contention
graph. These constraints, called row constraints, are obtained via the conflict graph incidence matrix: for
each node of the contention graph, then the sum of the rates on this link and on the neighbor links (in the
contention graph) should not exceed the radio medium capacity. The problem with such constraints is that they
are sufficient but not necessary and thus may lead to an allocation that is far to be optimal. Nonetheless, there
are some cases where the row constraints are less pessmistic than the scaled clique constraints. Therefore, these
constraints may be of some interest, because they are easier to obtain than the clique constraints.
Nodes contention graph
All the approaches described in the previous sub-section are rather difficult to use in practice. Indeed, they first
require to build the wireless links contention graph and then to compute either the maximal independent sets or
the maximal cliques, which is computationally expensive. The simplest solution, proposed so far, is to compute
the row constraints. But this solution still needs to know the links contention graph which implies extra time,
especially in a mobile environment.
A simple node-based model
In this work we propose to use a simpler model that can be usable in practice. But before describing this
model, let’s come back to the different ranges of IEEE 802.11. The values of these ranges are not easy to
obtain practically because they are variable and depend on several parameters (environment, wireless cards,
time, weather, etc.). For instance, in the simulator NS2, the default transmission range is equal to 250 m while
the carrier sensing range and the interference range are the same and equal to 550 m. But in practice, these
values may be very different. For instance, in [5, 1], the experiments show that these ranges are shorter and
variable: the transmission range depends on the data rate, the carrier sensing range is almost constant, while
the interference range depends on the distance between the sender and the receiver. Some conclusions that can
be of some interest for this work are: i) the carrier sensing range is around two times the communication range
obtained with slow data rates (2 or 1 Mb/s) and ii) the interference range may be larger than the carrier sensing
range.
A first evaluation
Before deriving a rate allocation protocol from this algorithm, we carry out a first evaluation in order to check
whether it is worth going further with this approach. To this end, we implement our algorithm in a C program.
For different configurations, we compute the rate allocation with our program and then inject the computed
rates into the same configurations simulated with the network simulator NS2 [15]. The parameters used in
NS2, especially for IEEE 802.11, are given in Table 4. We use AODV for the routing protocol. Thus, we obtain
an evaluation of our algorithm in terms of throughputs and convergence and we can check, at a first glance,
if the obtained rates are feasible in a more realistic context with IEEE 802.11 as the underlying technology.
In this part, we also implement a rate allocation algorithm based on the maximal cliques deduced from the
wireless links contention graph in order to compare the node-based model and the maximal cliques model.
This algorithm is based on different constraints but uses the same Lagrangian optimization method. For each
evaluation, the parameter is optimized according to the chosen model in order to maximize the convergence
speed in each of the two models. Due to space limitation, we only present three scenarii. The results are the
average of 20 simulations.