05-04-2012, 02:03 PM
Approaching Throughput-Optimality in Distributed CSMA Scheduling Algorithms with Collisions
Abstract:
It was shown recently that carrier sense multiple access (CSMA)-like distributed algorithms can achieve the maximal throughput in wireless networks (and task processing networks) under certain assumptions. One important but idealized assumption is that the sensing time is negligible, so that there is no collision.
In this paper, we study more practical CSMA-based scheduling algorithms with collisions. First, we provide a Markov chain model and give an explicit throughput formula that takes into account the cost of collisions and overhead. The formula has a simple form since the Markov chain is “almost” time-reversible. Second, we propose transmission-length control algorithms to approach throughput-optimality in this case. Sufficient conditions are given to ensure the convergence and stability of the proposed algorithms.
Finally, we characterize the relationship between the CSMA parameters (such as the maximum packet lengths) and the achievable capacity region.
Existing system:
In older days they used two types of algorithm.
1. MAC layer algorithm
2. LQF algorithm
MAC layer algorithm:
MAC-layer scheduling is the bottleneck of the problem.
In particular, it is not easy to achieve the maximal throughput through distributed scheduling, which in turn prevents full utilization of the wireless network. Scheduling is challenging since the conflicting relationships between different links can be complicated.
LQF algorithm:
On the other hand, a number of low-complexity but suboptimal scheduling algorithms have been proposed in the literature. By using a distributed greedy protocol similar to IEEE 802.11, shows that only a fraction of the throughput region can be achieved (after ignoring collisions). The fraction depends on the network topology and interference relationships. The algorithm is related to Maximal Scheduling, which chooses a maximal schedule among the nonempty queues in each slot.
Proposed System:
Our first contribution in this paper is to introduce a distributed adaptive carrier sense multiple access (CSMA) algorithm for a general interference model. It is inspired by CSMA, but maybe applied to more general resource sharing problems (i.e., not limited to wireless networks). We show that if packet collisions are ignored (as in some of the mentioned references), the algorithm can achieve maximal throughput. The algorithm may not be directly comparable to those throughput-optimal algorithms we have mentioned since it utilizes the carrier-sensing capability.
Advantages:
• Each node only uses its local information (e.g., its backlog). No explicit control messages are required among the nodes.
• It is based on CSMA random access, which is similar to the IEEE 802.11 protocol and is easy to implement.
• Time is not divided into synchronous slots. Thus, no synchronization of transmissions is needed.