Design and analysis of medium access control protocols for ad hoc and cooperative wireless networks

Abstract

La presente tesis doctoral contribuye a la incesante evolución de las comunicaciones inalámbricas. Se centra en el diseño de protocolos de acceso al medio (MAC) para redes ad hoc y redes inalámbricas cooperativas. En una primera parte introductoria se presenta un minucioso estado del arte y se establecen las bases teóricas de las contribuciones presentadas en la tesis. En esta primera parte introductoria se definen las principales motivaciones de la tesis y se plantean los objetivos. Después, las contribuciones de la tesis se organizan en dos grandes bloques, o partes. En la primera parte de esta tesis se diseña, analiza y evalúa el rendimiento de un novedoso protocolo MAC de alta eficiencia llamado DQMAN (Protocolo MAC basado en colas distribuidas para redes ad hoc). Este protocolo constituye la extensión y adaptación del protocolo DQCA, diseñado para redes centralizadas, para operar en redes sin infraestructura. En DQMAN se introduce un nuevo paradigma en el campo del acceso al medio para redes distribuidas: la integración de un algoritmo de clusterización espontáneo y dinámico basado en una estructura de master y esclavo junto con un protocolo MAC de alta eficiencia diseñado para redes centralizadas. Tanto el análisis teórico como las simulaciones por ordenador presentadas en esta tesis muestran que DQMAN mejora el rendimiento del actual estándar IEEE 802.11. La principal característica de DQMAN es que se comporta como un protocolo de acceso aleatorio cuando la carga de tráfico es baja y cambia automática y transparentemente a un protocolo de reserva a medida que el tráfico de la red aumenta. Además, su rendimiento es prácticamente independiente del número de usuarios simultáneos de la red, lo cual es algo deseable en redes que nacen para cubrir una necesidad espontánea y no pueden ser planificadas. El hecho de que algoritmo de clusterización se base en un acceso aleatorio permite la coexistencia e intercomunicación de usuarios DQMAN con usuarios basados en el estándar IEEE 802.11. Este estudio se presenta en esta primera parte de la tesis y es fundamental de cara a una posible explotación comercial de DQMAN. La metodología presentada en esta tesis mediante el cual se logra extender la operación de DQCA a entornos ad hoc sin infraestructura puede ser utilizada para adaptar cualquier otro protocolo centralizado. Con el objetivo de poner de manifiesto esta realidad, la primera parte de la tesis concluye con el diseño y evaluación de DPCF como una extensión distribuida del modo de coordinación centralizado (PCF) del estándar IEEE 802.11 para operar en redes distribuidas. La segunda parte de la tesis se centra en el estudio de un tipo específico de técnicas cooperativas: técnicas cooperativas de retransmisión automática (C-ARQ). La idea principal de las técnicas C-ARQ es que cuando un paquete de datos se recibe con bits erróneos, se solicita retransmisión, no a la fuente de datos, si no a cualquiera de los usuarios que escuchó la transmisión original. Estos usuarios se convierten en espontáneos retransmisores que permiten mejorar la eficiencia de la comunicación. A pesar de que este tipo de esquema puede obtener diversidad de cooperación, el hecho de implicar a más de un usuario en una comunicación punto a punto requiere una coordinación que hasta ahora ha sido obviada en la literatura, asumiendo que los retransmisores pueden coordinarse perfectamente para retransmitir uno detrás de otro. En esta tesis se analiza y evalúa el coste de coordinación impuesto por la capa MAC y se identifican los principales retos de diseño que las técnicas C-ARQ imponen al diseño de la capa MAC. Además, se presenta el diseño y análisis de dos novedosos protocolos MAC para C-ARQ: DQCOOP y PRCSMA. El primero se basa en DQMAN y constituye una extensión de este para operar en esquemas C-ARQ, mientras que el segundo constituye la adaptación del estándar IEEE 802.11 para poder ejecutarse en un esquema C-ARQ. El rendimiento de estos esquemas se compara en esta tesis tanto con esquemas no cooperativos como con esquemas ideales cooperativos donde se asume que el MAC es ideal. Los resultados principales muestran que el diseño eficiente de la capa MAC es esencial para obtener todos los beneficios potenciales de los esquemas cooperativos.

This thesis aims at contributing to the incessant evolution of wireless communications. The focus is on the design of medium access control (MAC) protocols for ad hoc and cooperative wireless networks. A comprehensive state of the art and a background on the topic is provided in a first preliminary part of this dissertation. The motivations and key objectives of the thesis are also presented in this part. Then, the contributions of the thesis are divided into two fundamental parts. The first part of the thesis is devoted to the design, analysis, and performance evaluation of a new high-performance MAC protocol. It is the Distributed Queueing MAC Protocol for Ad hoc Networks (DQMAN) and constitutes an extension and adaptation of the near-optimum Distributed Queueing with Collision Avoidance (DQCA) protocol, designed for infrastructure-based networks, to operate over networks without infrastructure. DQMAN introduces a new access paradigm in the context of distributed networks: the integration of a spontaneous, dynamic, and soft-binding masterslave clustering mechanism together with a high-performance infrastructure-based MAC protocol. Theoretical analysis and computer-based simulation show that DQMAN outperforms IEEE 802.11 Standard. The main characteristic of the protocol is that it behaves as a random access control protocol when the traffic load is low and it switches smoothly and automatically to a reservation protocol as the traffic load grows. In addition, its performance is almost independent of the number of users of a network. The random-access based clustering algorithm allows for the coexistence and intercommunication of stations using DQMAN with the ones just based on the legacy IEEE 802.11 Standard. This assessment is also presented in this first part of the dissertation and constitutes a key contribution in the light of the commercial application of DQMAN. Indeed, the rationale presented in this first part of the thesis to extend DQCA and become DQMAN to operate over distributed networks can be used to extend the operation of any other infrastructure-based MAC protocol to ad hoc networks. In order to exemplify this, a case study is presented to conclude the first part of the thesis. The Distributed Point Coordination Function (DPCF) MAC protocol is presented as the extension of the PCF of the IEEE 802.11 Standard to be used in ad hoc networks. The second part of the thesis turns the focus to a specific kind of cooperative communications: Cooperative Automatic Retransmission Request (C-ARQ) schemes. The main idea behind C-ARQ is that when a packet is received with errors at a receiver, a retransmission can be requested not only from the source but also to any of the users which overheard the original transmission. These users can become spontaneous helpers to assist in the failed transmission by forming a temporary ad hoc network. Although such a scheme may provide cooperative diversity gain, involving a number of users in the communication between two users entails a complicated coordination task that has a certain cost. This cost has been typically neglected in the literature, assuming that the relays can attain a perfect scheduling and transmit one after another. In this second part of the thesis, the cost of the MAC layer in C-ARQ schemes is analyzed and two novel MAC protocols for C-ARQ are designed, analyzed, and comprehensively evaluated. They are the DQCOOP and the Persistent Relay Carrier Sensing Multiple Access (PRCSMA) protocols. The former is based on DQMAN and the latter is based on the IEEE 802.11 Standard. A comparison with non-cooperative ARQ schemes (retransmissions performed only from the source) and with ideal CARQ (with perfect scheduling among the relays) is included to have actual reference benchmarks of the novel proposals. The main results show that an efficient design of the MAC protocol is crucial in order to actually obtain the benefits associated to the C-ARQ schemes.