Full-text of Yu Wang's dissertation is available in either PDF or gzipped postscript format. Below is the summary.
Yu Wang
Email: ywang@cse.ucsc.edu
URL:
http://www.cse.ucsc.edu/~ywang
In contention-based MAC protocols collision avoidance is very important, because simple MAC protocols such as carrier sense multiple access (CSMA) cannot combat the ``hidden terminal'' problem and performance can degrade to that of the ALOHA protocol in ad hoc networks [11,12,27].
Many collision-avoidance protocols [13,14,15,16] have been proposed and the most popular collision avoidance scheme today consists of a four-way sender-initiated handshake in which the transmission of a data packet and its acknowledgment is preceded by request-to-send (RTS) and clear-to-send (CTS) packets between a pair of sending and receiving nodes. Other nodes that overhear RTS or CTS packets will defer their access to the channel to avoid collisions. For the sake of simplicity, it can be also called RTS/CTS based scheme. Among all these proposed collision-avoidance protocols, the IEEE 802.11 distributed foundation wireless medium access control (DFWMAC) protocol [15] is very popular in the performance studies of routing protocols for ad hoc networks, even though it was originally intended for wireless LANs with no or very few hidden terminals. Though there has been considerable work on the performance evaluation of IEEE 802.11 and similar protocols [28,29,30,31,32,33,34], most of the analytical models are largely confined to single-hop networks [32,33,34] or cases when the number of hidden terminals is very small [28].
We deem it very important to investigate the performance of the four-way sender-initiated collision avoidance scheme with a truly multi-hop network model as potential interference from hidden nodes always exists, which is a salient characteristic of multi-hop ad hoc networks. Hence, in [35,36,37], we present the first analytical model to derive the saturation throughput of four-way sender-initiated collision avoidance protocols in multi-hop ad hoc networks. We show that the sender-initiated collision-avoidance scheme achieves much higher throughput than the idealized carrier sense multiple access scheme with an ideal separate channel for acknowledgments. More importantly, we show that the collision avoidance scheme can accommodate much fewer competing nodes within a region in a network infested with hidden terminals than in a fully-connected network, if reasonable throughput is to be maintained. This shows that the scalability problem of contention-based collision-avoidance protocols looms much earlier than people might expect. Simulations of the popular IEEE 802.11 MAC protocol validate the predictions made in the analysis. Simulation results also reveal the fairness problem in ad hoc networks which refers to the severe degradation in throughput experienced by some nodes due to location dependent contention and motivate our work on fairness in [38,39,40,41,42].
In recent years, there has been also increasing interest in using directional antennas to improve the performance of existing MAC protocols [43,44,45,46,47,48,49]. Some MAC protocols using directional antennas have been proposed in the past, which achieve tradeoff between spatial reuse and collision avoidance via a combination of omni-directional and directional transmission modes. Simulation-based studies of these proposed protocols show that they have improved performance over the existing omni-directional IEEE 802.11 MAC protocol. However, the majority of the performance analyses of directional collision avoidance schemes have been done via simulations, and there is little prior work on the analytical modeling of directional collision avoidance protocols. Hence, in [50,51,52,53] we investigate the interaction between spatial reuse, interference reduction and collision avoidance by extending the model used to analyze several typical MAC protocols using directional antennas. In our model, we consider both (a) the effect of directional transmitting and receiving on spatial reuse and collision avoidance, and (b) the effect of the differences in gains between omni-directional and directional transmissions. Analytical results show that, when the directional collision avoidance scheme in which all transmissions are directional is augmented with directional receiving, one-hop throughput does not decrease due to the increased spatial reuse, even when the number of competing nodes within a region increases. This is very desirable because the scalability problem shown in [35,36,37] is mitigated by the use of powerful directional antenna systems. It is also shown that, as expected, the performance of directional collision avoidance schemes degrades when directional transmissions have much higher gain than omni-directional transmissions. However, this degradation is relatively small. Simulations of the IEEE 802.11 protocol and its directional variants validate the results predicted in the analysis; and show that side lobes affect little on throughput if the gain of the main transmission lobe is reasonably higher than that of side lobes and the carrier sensing threshold is raised to make nodes less sensitive to channel activities.
In [54], we study via simulations both the performance of unicast traffic in the presence of broadcast traffic and the performance of broadcast traffic when mixed with unicast traffic, which is different from previous investigations reported in the literature in which broadcast traffic is investigated in isolation. The simulation results show that the presence of broadcast traffic does not degrade the performance of the all-directional collision avoidance scheme significantly, even for relatively large percentages of broadcast traffic. The work done in [50,51,52,53,54] indicates that the most attractive collision avoidance approach consists of using directional transmissions of control and data packets, together with the directional reception of packets whenever a node is expecting a particular packet. Given the high tolerance to broadcast traffic of directional collision avoidance schemes, it is argued that the periodic transmission of beacons omni-directionally suffices to provide such schemes with the relative locations of neighboring nodes.
In addition to enhancing throughput in MAC protocols, alleviation of fairness problems is also intensively investigated in the recent past [14,55,56,57,58,59,60,61,62,63]. The fairness problems usually result from location dependent contention which is very common in multi-hop ad hoc networks. Additionally, the commonly used binary exponential backoff (BEB) scheme, despite its robustness against repetitive collisions, can aggravate the fairness problem, because the node that succeeds in the last transmission period will gain access to the shared channel again with much higher probability while other nodes are denied access almost completely. We investigate the fairness problem in detail in [40]. We show that the required multi-hop coordination makes those backoff-based distributed fair queueing schemes less effective. Using extensive simulations of two competing flows with different underlying network configurations, it is shown that the commonly used flow contention graph is insufficient to model the contention among nodes and that various degrees of unfairness can take place. The fairness problem is more severe in TCP-based flows due to the required acknowledgment traffic, and TCP throughput is also negatively affected.
In [38,39,41], we propose a novel hybrid channel access scheme that combines both sender-initiated and receiver-initiated collision avoidance handshake. The new scheme is compatible with the popular IEEE 802.11 MAC protocol and involves only some additional queue management and book-keeping work. Simulation experiments show that the new scheme can alleviate the fairness problems existent for both UDP and TCP based applications with almost no degradation in throughput. However, it still cannot solve the fairness problem conclusively. This indicates that more explicit information exchange among contending nodes is mandatory to solve the fairness problem which motivates the further work done in [42,64].
In [42,64], we introduce a framework to address the fairness problem in ad hoc networks. The framework includes four key components: Exchanging flow contention information, using an adaptive backoff algorithm that does not aggravate the fairness problem like the binary exponential backoff (BEB) does, introducing a combination of sender-initiated and receiver-initiated collision avoidance handshake, and dealing with two-way flows. We explain the rationale for these components and then propose some algorithms to realize the framework. The resulting scheme, which we call topology aware fair access (TAFA) is compared through simulations with the IEEE 802.11 MAC protocol and the hybrid channel access scheme proposed in in [40,38,39,41]. Simulation results show that TAFA can solve the fairness problem in UDP-based applications with negligible degradation in throughput. It can also solve the notorious problem of the starvation of flows in TCP-based applications, while incurring only some throughput degradation. Hence, TAFA shows a much better overall tradeoff between throughput and fairness than other schemes previously proposed.
Papers [35,36,37,50,51,54,38,39,40,41,52,53,42] based on the above research work have been published or accepted for publication. Looking forward, the following topics are interesting and worth further investigation in our future work.
First, we have shown that the all-directional MAC scheme can achieve high throughput and low access delay and the use of omni-directional transmissions to broadcast neighbor information is enough to obtain necessary information for directing antennas without degrading much throughput. However, it will still be interesting to evaluate neighbor protocols that can track other nodes' locations (or directions) and see how well the all-directional MAC scheme works in an environment where nodes can be moving in and outside one another's transmission and reception range.
Second, the enhancements to broadcasting proposed in the literature have not been incorporated in our investigation of directional MAC schemes, it will be interesting to investigate how the use of directional antennas as another dimension in the solution space can help to enhance broadcasting in multi-hop ad hoc networks.
Third, the fairness framework may still be enhanced in several ways. For example, in all the schemes discussed so far, the MAC layer serves requests in a first-in-first-out (FIFO) manner, whether the request is an RTS to be sent for a data packet from upper routing layer, or an CTS to be replied to a neighbor in a sender-initiated or receiver-initiated mode. This may cause head-of-line (HOL) problems when the intended receiver faces severe contention and the HOL request cannot get through even though the requests behind the HOL packet may get through because their intended receivers are other nodes that face less contention. Hence, it may be advantageous for the MAC layer to maintain separate queues and achieve some prioritized or differentiated access. Other ways of enhancements include design of new adaptive backoff algorithm and new criteria to switch between sender-initiated and receiver-initiated collision avoidance to achieve better throughput and fairness tradeoffs.
Fourth, the work on fairness framework and mechanisms, though more inclined towards fair medium access among neighboring nodes, has already shown the benefits of more interactions between MAC layer and transport layer. It will be interesting to work on the integration of channel access with fair scheduling which can guard against misbehaved nodes and is a key component to provide QoS assurances. It is argued that such integration is necessary to provide services beyond best-effort and can facilitate the deployment of high profile applications in the future.