Incorporating physical layer capture in the modeling, analysis and design of wireless access mechanisms.

摘要

While physical layer capture has been observed in real implementations of 802.11 devices, accurate models that describe the behavior of the phenomenon have been scarce. Physical layer capture describes the phenomenon when a transmitted frame gets through a collision with neighbors. Even when multiple neighbors access the channel simultaneously, a receiver can receive the frame without errors if the interference strength from the neighbors is less than a threshold. Our experiments in a real 802.11 wireless testbed also support this, demonstrating that modern 802.11 wireless devices may capture frames among concurrent transmissions.;However, the previous models and fair scheduling algorithms only consider absolute conflicts between two neighbors. If transmissions from any two neighbors overlap, the transmissions is assumed to fail and the transmitted frames are lost. Frames can be received only when all neighbors around the receivers hold off their transmissions during the entire of the transmission time. This link-layer model, although simplifying the analysis and design of scheduling protocols, cannot be applied in general, especially when senders and receivers are close and frame capture occurs frequently.;In this thesis, a general analytical framework is first presented to analyze the error probability and throughput of frame transmissions in present of physical layer capture. The framework, consisting of MAC and physical layer protocol models, is completely open to any kind of physical channel models. Introducing the concept of interference function, defined according to a given physical channel model, the framework can accommodate any of the physical layer models and also allows the empirical measurements as a basis of the models. To describe the interaction and interference among the MAC and physical layer protocols, an iterative method is presented. The model offers a more accurate prediction than previous work by taking real channel models into account. This permits the analysis of frame reception at any transmission rate with interference from neighbors at any set of locations.;As the second part of this work, utility fairness is explored in presence of physical layer capture. Using the analytical model proposed above, the general formulation of fairness problem is presented and the feasible allocation space is proven to be non-convex under physical layer capture. This non-convexity shows the previous techniques may not achieve fair throughput allocations and motivates a new fair scheduling algorithm.;For a new fair allocation scheme, a log-utility fair algorithm is presented. Widely known as a less egalitarian approach to max-min fairness, log-utility fair scheduling is a good compromise between the effective utilization of the channel and the fairness of individual senders. Based on the proposed analytical model, decentralized log-utility fair allocation algorithms are designed incorporating the phenomena of physical layer capture. The efficient algorithms, linear in complexity to the number of nodes, achieve throughput allocations close to the optimal in log-utility fairness as opposed to previously proposed ones that suffer from node throughput starvation in real environments by ignoring physical layer capture.;To verify the proposed analytical model and scheduling algorithms, real experiments as well as extended simulations are performed in the Orbit testbed, a large grid consisting of 400 nodes with 802.11 wireless interfaces. Extensive experiments demonstrate that using the proposed model, the difference between the analyzed and measured error probability for a single sender is just 1.65% on average. On the other hand, the proposed fair algorithm improves the aggregate utility by more than 22.4% and the minimum node throughput by almost 6.3 times compared to the results of previously proposed algorithms.