IEEE 802.11 WLAN has high data rates (e.g., 11 Mbps for 802.11b and 54 Mbps for 802.11g), while voice streams of VoIP typically have low-data-rate requirements (e.g., 29.2 Kbps). One may, therefore, expect WLAN to be able to support a large number of VoIP sessions (e.g., 200 and 900 sessions in 802.11b and 802.11g, respectively). Prior work by one of the authors, however, indicated that 802.11 is extremely inefficient for VoIP transport. Only 12 and 60 VoIP sessions can be supported in an 802.11b and an 802.11g WLAN, respectively. This paper shows that the bad news does not stop there. When there are multiple WLANs in the vicinity of each other-a common situation these days-the already low VoIP capacity can be further eroded in a significant manner. For example, in a 5 times 5, 25-cell multi-WLAN network, the VoIP capacities for 802.11b and 802.11g are only 1.63 and 10.34 sessions per AP, respectively. This paper investigates several solutions to improve the VoIP capacity. Based on a conflict graph model, we propose a clique-analytical call admission scheme, which increases the VoIP capacity by 52 percent from 1.63 to 2.48 sessions per AP in 802.11b. For 11g, the call admission scheme can also increase the capacity by 37 percent from 10.34 to 14.14 sessions per AP. If all the three orthogonal frequency channels available in 11b and 11g are used to reduce interferences among adjacent WLANs, clique-analytical call admission scheme can boost the capacity to 7.39 VoIP sessions per AP in 11b and 44.91 sessions per AP in 11g. Last but not least, this paper expounds for the first time the use of coarse-grained time-division multiple access (CoTDMA) in conjunction with the basic 802.11 CSMA to eliminate the performance-degrading exposed-node and hidden-node problems in 802.11. A two-layer coloring problem (which is distinct from the classical graph coloring problem) is formulated to assign coarse time slots and frequency channels to VoIP sessions, taking into account the intricacies of the carrier-sensing operation of 802.11. We find that CoTDMA can further increase the VoIP capacity in the multi-WLAN scenario by an additional 35 percent, so that 10 and 58 sessions per AP can be supported in 802.11b and 802.11g, respectively.

This paper investigates the many-to-one throughput capacity (and by symmetry, one-to-many throughput capacity) of IEEE 802.11 multihop networks, in which many sources send data to a sink. An example of a practical scenario is that of a multihop mesh network connecting source and relay nodes to an Internet gateway. In the trivial case where all source nodes are just one hop from the sink, the system throughput can approach Ls, where Lsis the throughput capacity of an isolated link consisting of just one transmitter and one receiver. In the nontrivial case where some source nodes are more than one hop away, one can still achieve a system throughput of Lsby sacrificing and starving the non-one-hop source nodes-however, this degenerates to an unacceptable trivial solution. We could approach the problem by the following partitioning: preallocate some link capacity aLs(0 les a les 1) at the sink to the one-hop source nodes and then determine the throughput for the source nodes that are two or more hops away based on the remaining capacity L = (1 - a)Ls. The throughput of the one-hop nodes will be around aLs. This paper investigates the extent to which the remaining capacity L can be used efficiently by the source traffic that is two or more hops away. We find that for such source traffic, a throughput of L is not achievable under 802.11. We introduce the notion of "canonical networks,rdquo a general class of regularly structured networks that allow us to investigate the system throughput by varying the distances between nodes and other operating parameters. When all links have equal length, we show that 2L/3 is the upper bound for general networks, including random topologies and canonical networks. When the links are allowed to have different lengths, we show that the throughput capacity of canonical networks has an analytical upper bound of 3L/4. The tightness of the bound is confirmed by simulations of 802.11 canonical networks, in which we obtain simulated throughputs of 0.74L when the source nodes are two hops away and 0.69L when the source nodes are many hops away. We conjecture that 3L/4 is also the upper bound for general networks. Our simulations show that 802.11 networks with random topologies operated with AODV routing typically achieve throughputs far below 3L/4. Fortunately, by properly selecting routes near the gateway (or by properly positioning the relay nodes leading to the gateway) to fashion after the structure of canonical networks, the throughput can be improved by more than 150 percent: indeed, in a dense network, deactivating some of the relay nodes near the sink can lead to a higher throughput.

It is well known that IEEE 802.11 WLAN is highly inefficient for transporting voice data. For example, if one simply takes the data rate of 802.11 b, 11 Mbps, and divide it by two times 13.2 Kbps (the bit rate of a typical voice stream in one direction), one comes to the conclusion that more than 400 voice sessions can be supported in an 802.11 b WLAN. As shown in previous work, it turns out that at most 12 sessions can be supported due to various header and protocol overheads inherent in 802.11. This paper points out that the "bad news" does not stop there, and that in practice the number of supportable voice sessions could be lower than 2 sessions per access point (AP)! This is so because as 802.11 WLAN gains popularity, it is common to have many WLANs being deployed in the same geographical area, and these WLANs share the common air medium. Our ns2 simulation experiments, for example, show that the capacity of a 5-by-5, 25-cell IEEE 802.11b WLAN, laid out in a square grid manner, is only 1.6 sessions per AP. The second contribution of this paper is the investigation of techniques to improve the dismal capacity. We show that a systematic call admission mechanism based on clique analysis of a conflict graph can increase the capacity to 2.12 sessions per AP. Adding a "restart mode" to the 802.11 protocol boosts the capacity further to 2.72 sessions per AP. We also briefly discuss the impact of higher data rates (e.g., 54 Mbps in 802.tig and 802.11 a), and careful assignment of available frequency channels (e.g., the three and twelve orthogonal frequency channels in 802.11 b/g and 802.11 a, respectively), on capacity. Although all the above techniques can improve the capacity somewhat, the huge penalty relative to the potential remains. Boosting the voice capacity over multiple WLANs is therefore an area that deserves further attention from the research community.

This paper examines how various carrier-sensing schemes affect the exposed-node (EN) and hidden-node (HN) phenomena. In the process, we identify a new carrier-sensing mechanism for alleviating EN and HN that is more effective than previously proposed schemes. This scheme, referred to as the MP scheme, uses MAC-address-based Physical carrier sensing to determine if the medium is busy. In MP, the addresses of transmitter and receiver of a packet are incorporated into the PHY header. Making use of this address information for its carrier-sensing operation, a node can drastically reduce the detrimental effects of EN and HN. In ns2 simulations, MP yields superior throughput and fairness performance that exceed our original expectation. Specifically, we find that the total network throughput achieved by MP is more than twice that of the 802.11b basic-access mode, and more than four times that of the 802.11b RTS/CTS mode, under various node-density and packet-size assumptions. At the same time, the Jains fairness index of MP is almost twice that of the 802.11b basic-access and RTS/CTS modes. We believe this is a first paper to propose and investigate the merit of cross-layer carrier sensing that jointly makes use of the attributes of the physical and MAC layers in its operation