Search

[ES] El objetivo del TFG es realizar un análisis de prestaciones comparado de dos protocolos de acceso al medio (MAC) utilizados en redes de sensores: Frame Slotted-ALOHA with Reservation and Data Packets (FSA-RDP) y FSA-DQ (Distributed Queuing). El protocolo FSA-RDP requiere un mecanismo de access barring adaptativo con la carga que, en caso de congestión, excluya una parte de los nodos que contienden enviando de paquetes de reserva, consiguiendo así maximizar el número de éxitos en el acceso. El ajuste de este mecanismo debe ser realizado por el controlador de la red y puede ser complejo. En cambio, el protocolo FSA-DQ utiliza un mecanismo de cola distribuida que, por sí mismo, se adapta a las condiciones de carga. Los parámetros de mérito que se utilizarán para la evaluación son: la probabilidad de pérdida de paquetes, el caudal cursado y el retardo de acceso. El estudio se realizará mediante simulación por eventos discretos., [EN] The objective of the TFG is to perform a comparative performance analysis of two medium access protocols (MAC) used in sensor networks: Frame Slotted-ALOHA with Reservation and Data Packets (FSA-RDP) and FSA-DQ (Distributed Queuing). The FSA-RDP protocol requires an adaptive access barring mechanism with the load that, in case of congestion, excludes part of the nodes that contend sending reservation packets, thus managing to maximize the number of access successes. The adjustment of this mechanism is done by the network controller and can be complex. Instead, the FSA-DQ protocol uses a distributed queuing mechanism that adapts to load conditions by itself. The performance parameters of merit that will be used for the evaluation are: the packet loss probability, the packet throughput and the access delay. Discrete-event simulation will be used for the study.

Internet of Things and Machine-to-Machine communications have contributed significantly on our daily life. Nevertheless, from the networking aspect they introduced a huge challenge for the performance and quality of services of networks. In this paper, a Distributed Queuing Access for LTE protocol was analyzed to enhance the random access performance for Machine to machine (M2M) applications. The M2M communications presented countless solicitations that can over-burden the access channel of the present LTE network. This prompts to an expansion in the collision probability and results in a noteworthy access delay. The introduced protocol does improve the performance of Medium access layer in terms of blocking probability, access delay, energy utilization and number of re-transmissions attempts in comparison with the standard LTE protocol without altering the existing LTE outline structure. The new protocol is intended to ensure that the random access procedure of the ordinary UE gadget will not be affected bringing about consistent implementation for the proposed convention.

In this paper we propose a cutoff hypercube queuing model to analyze server-to-customer emergency services operating with server reservation. We are motivated by certain SAMU’s (Systeme d’Aide Medicale Urgente) that give assistance to different classes of emergency requests, including specialized transfer of patients, and use the reservation strategy to improve the probability that ambulances will be available to high priority calls. The aim is to show how this cutoff priority service discipline can be handled by the cutoff hypercube queuing model to evaluate relevant system performance measures, and the main impacts of this policy to the different classes of users.

This is the peer reviewed version of the following article: Vazquez-Gallego F, Tuset-Peiró P, Alonso L, Alonso-Zarate J. Combining distributed queuing with energy harvesting to enable perpetual distributed data collection applications. Trans Emerging Tel Tech. 2017;e3195 , which has been published in final form at https://doi.org/10.1002/ett.3195. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving. This paper presents, models, and evaluates energy harvesting–aware distributed queuing (EH-DQ), a novel medium access control protocol that combines distributed queuing with energy harvesting (EH) to address data collection applications in industrial scenarios using long-range and low-power wireless communication technologies. We model the medium access control protocol operation using a Markov chain and evaluate its ability to successfully transmit data without depleting the energy stored at the end devices. In particular, we compare the performance and energy consumption of EH-DQ with that of time-division multiple access (TDMA), which provides an upper limit in data delivery, and EH-aware reservation dynamic frame slotted ALOHA, which is an improved variation of frame slotted ALOHA. To evaluate the performance of these protocols, we use 2 performance metrics: delivery ratio and time efficiency. Delivery ratio measures the ability to successfully transmit data without depleting the energy reserves, whereas time efficiency measures the amount of data that can be transmitted in a certain amount of time. Results show that EH-DQ and TDMA perform close to the optimum in data delivery and outperform EH-aware reservation dynamic frame slotted ALOHA in data delivery and time efficiency. Compared to TDMA, the time efficiency of EH-DQ is insensitive to the amount of harvested energy, making it more suitable for energy-constrained applications. Moreover, compared to TDMA, EH-DQ does not require updated network information to maintain a collision-free schedule, making it suitable for very dynamic networks.

The Energy Harvesting-aware Distributed Queuing access protocol (EH-DQ) is presented in this paper as a novel Medium Access Control protocol for wireless Machineto-Machine networks with energy harvesting capabilities. EHDQ is theoretically modeled to analyze its performance. A performance comparison with a Time Division Multiple Access (TDMA) and an EH-aware Reservation Dynamic Frame SlottedALOHA (EH-RDFSA) shows its superior performance. While TDMA requires updated network information to maintain a collision-free schedule and EH-RDFSA requires to estimate the number of contenders per frame to dynamically adjust the frame length, EH-DQ uses short and fixed frame lengths and does not require knowledge of the network topology or the number of end-devices in advance.

Distributed queuing collision avoidance (DQCA) is a hybrid medium access control (MAC) protocol that can inherently accommodate large node densities; however it may not be capable of handling the order of magnitude of devices in Machine-to-Machine (M2M) networks, which is an order higher than the existing WLANs. To address this issue, we propose a hybrid MAC protocol that uses orthogonal codes for channel contention, coupled with a power based priority assignment scheme for scheduling the data transmissions. The simulation results show that the proposed protocol is well suited for M2M networks and outperforms DQCA.

In this paper, we present an approximate method for solution of load-dependent, closed queuing networks having general service time distributions with low variability. The proposed technique is an extension of Marie’s (1980) method. In the methodology, conditional throughputs are obtained by an iterative procedure. The iterations are repeated until an invalid result is detected or no improvements are found. We demonstrate the performance of the technique with 10 different examples. On average, the solutions have 5% or lower deviations when compared to simulation results.

Distributed Queuing Collision Avoidance (DQCA) is an efficient MAC protocol designed for infrastructure Wireless LANs. In this paper, four algorithms are proposed that alter the FIFO scheduling order of DQCA in order to meet specific network requirements. The proposed schemes combine the efficiency of opportunistic scheduling with the QoS provisioning through service differentiation. The opportunistic policy encourages transmissions at higher rates when the channel condition is good and is implemented through a cross-layer dialogue between the PHY and the MAC layers. The key idea of service differentiation is to assign priorities to traffic flows with different requirements in order to provide QoS guarantees. The throughput, delay and jitter performance of the proposed schemes has been evaluated through simulations for a scenario with heterogeneous traffic of voice, video, best-effort and background data traffic flows.

Machine-to-machine (M2M) communications allow multiple devices to communicate directly without human intervention. There will be a huge number of devices in the M2M communications which results in enormous congestion in the current Random Access Channel (RACH) of LTE based cellular systems. This paper presents a protocol for improving the performance of the LTE RACH for M2M applications. This protocol, the Distributed Queuing Access for LTE (DQAL), is based on the Distributed Queuing (DQ) algorithm. One of the benefits of using that algorithm is minimizing the collision in the access phase for the M2M communications. The reduction in the collision will turn in enhancing both the access success probability and the access delay for M2M devices (MDs). Furthermore, the protocol is designed to guarantee that the normal User Equipment (UE) device can access the system using the traditional RACH procedures without any modification. This will assure a seamless implementation of the proposed protocol over the existing LTE cellular systems. The simulation results show how the access delay obtained by the proposed DQAL protocol outperforms the Extended Access Baring (EAB) which is the baseline solution recommended by the 3 GPP for M2M communication.

In this paper, we propose a solution to efficiently handle the initial access contention for highly dense LTE networks, which still represents a challenge in terms of the high number of devices associated to Machine Type Communications. The analysis is based on the fact that, as the radius of a LTE cell is larger, the number of available preambles generated from a single root sequence is reduced. The current access mechanism, based on frame-slotted ALOHA, does not operate efficiently under these conditions, negatively affecting the access delay and collision probability. We show how the access procedure can be improved by implementing tree-splitting algorithms in order to cope with high number of simultaneous arrivals in large cells, above 5 km in radius. The implementation achieves as much as 85% reduction on the access delay and 54% reduction on energy consumption for cells with radius larger than 39 km.

In this paper, we address the challenge of high device density performing simultaneous transmissions by proposing and evaluating a solution to efficiently handle the initial access contention for highly dense LTE networks. We present the implementation of a tree-splitting algorithm in the access procedure of LTE, which is capable to cope with high number of simultaneous arrivals. Based on simulations we show a feasible implementation capable to achieve, under certain network configuration conditions, up to 85% average access delay reduction and 40% reduction on the average energy consumption, while maintaining a consistently low blocking probability, regardless of the number of initial simultaneous access attempts.

Machine-to-Machine (M2M) area networks aim at connecting an M2M gateway with a large number of energy-constrained devices that must operate autonomously for years. Therefore, attaining high energy efficiency is essential in the deployment of M2M networks. In this paper, we consider a dense M2M area network composed of hundreds or thousands of devices that periodically transmit data upon request from a gateway or coordinator. We theoretically analyse the devices’ energy consumption using two Medium Access Control (MAC) protocols which are based on a tree-splitting algorithm to resolve collisions among devices: the Contention Tree Algorithm (CTA) and the Distributed Queuing (DQ) access. We have carried out computer-based simulations to validate the accuracy of the theoretical models and to compare the energy performance using DQ, CTA, and Frame Slotted-ALOHA (FSA) in M2M area networks with devices in compliance with the IEEE 802.15.4 physical layer. Results show that the performance of DQ is totally independent of the number of contending devices, and it can reduce the energy consumed per device in more than 35% with respect to CTA and in more than 80% with respect to FSA.

O modelo hipercubo é um modelo de filas espacialmente distribuídas baseado em aproximações Markovianas para analisar a configuração e operação de sistemas emergenciais servidor-para-cliente, em que os servidores se deslocam até os clientes. Neste estudo adaptamos este modelo para tratar sistemas de atendimento médico emergenciais (SAEs) em rodovias com políticas particulares de despacho, em que somente algumas ambulâncias do sistema podem atender chamadas em uma dada região (backup parcial), e duas ou mais ambulâncias idênticas ou diferenciadas podem atender uma única chamada (múltiplo despacho). Também consideramos situações em que uma ambulância pode se encontrar ocupada em sua própria base atendendo uma chamada não emergencial, isto é, sem ter que se deslocar na rodovia. Resultados computacionais da aplicação do modelo num estudo de caso de um SAE de uma concessionária de rodovias no interior de São Paulo são apresentados e analisados.The hypercube is a spatially distributed queuing model based on Markovian analysis approximations to analyze the configuration and operation of server-to-customer emergency systems, in which servers travel to the locations of the customers. In the present study we adapt the model to analyze emergency medical systems (EMS) on highways operating with particular dispatching policies, which considers that only certain ambulances in the system can service calls in a given region (partial backup), and two or more identical or distinct ambulances can simultaneously service a single call (multiple dispatch). We also consider the situations in which an ambulance is busy in its base servicing a non-emergency call (i.e. it does not need to travel along the highway). Computational results of the model application to a case study of an EMS operating on highways in São Paulo state are presented and analyzed.

Machine-to-Machine (M2M) area networks must provide connectivity between an M2M gateway and a large number of energy-constrained M2M devices. Attaining high energy efficiency is essential in order to prolong devices lifetime. In this paper, we consider a wireless M2M area network composed of hundreds or even thousands of dormant devices that wake up periodically to transmit data upon request from a gateway. We theoretically analyze the energy efficiency of a Medium Access Control (MAC) protocol that uses a tree-splitting algorithm to resolve the collisions among devices: the Distributed Queuing (DQ) access. Computer-based simulations have been carried out to validate the accuracy of the analytical model and to evaluate and compare the energy consumption of devices using also a basic Contention Tree Algorithm (CTA) and Frame Slotted-ALOHA (FSA). Results show that DQ can reduce energy consumption in more than 35% with respect to CTA and in more than 80% with respect to FSA in dense M2M area networks with devices in compliance with the IEEE 802.15.4 physical layer.

Best Demo Runner-up Award, a la 33rd. Annual IEEE International Conference on Computer and Communications, INFOCOM 2014 This paper presents a demonstrator of Low-Power Distributed Queuing (LPDQ), a MAC protocol targeted at active RFID systems operating at 433 MHz. LPDQ is based on a packet-based Preamble Sampling for network synchronization and Distributed Queuing for channel access. Compared to the MAC protocol defined in the ISO 18000-7 standard, based on an analog Preamble Sampling and Frame Slotted ALOHA, LPDQ represents a major breakthrough in terms of system performance and energy consumption. At the MAC layer system performance is close to the optimal, e.g., no collisions during data packet transmission, and tag energy consumption can be reduced by more than 10% compared to FSA. Peer Reviewed Award-winning

The Huberman-Hogg model of computational ecosystems is applied to resources with queues. The previous theoretical results indicate that instabilities, due to delayed information, can be controlled by adaptive mechanisms, particularly schemes which employ diverse past horizons. A stochastic learning automaton, with rewards based on queuing parameters, is implemented to test the theoretical results. The effects of the learning step size and horizon are shown for systems with various delays and traffic intensities. The instabilities are controlled with appropriate choices of parameters and reward mechanism. Long horizons permit nonadaptive agents to achieve similar results, with the possible loss of responsiveness to dynamic environments.

Machine-to-Machine (M2M) networks must be energy-ef¿cient to operate autonomously for years, or even decades. In this paper, we consider a synchronized duty-cycled M2M network composed of a huge number of dormant devices that periodically wake up to transmit data to a coordinator. We propose the use of Distributed Queuing (DQ) tree-splitting algorithms to optimize the shared access to the channel among the high number of devices, in order to improve the energy ef¿ciency and thus extend the network lifetime. We evaluate the energy performance of DQ access in this kind of dense M2M networks, and we compare it to traditional access schemes based on variations of Frame Slotted-ALOHA (FSA) and the Contention Tree Algorithm (CTA). Computer-based simulations show that DQ can reduce the energy consumption in more than a 50% with respect to FSA and CTA. Results show that there is an optimum number of contention slots which maximizes the energy ef¿ciency of DQ regardless of the number of devices. The performance evaluation presented in this paper also compares the energy consumption of DQ using low power Wi-Fi and IEEE 802.15.4 devices

Lock-based synchronization on multiprocessors is inherently non-scalable, non-composable, and error-prone. These problems are exacerbated in distributed systems due to an additional layer of complexity: multinode concurrency. Transactional memory (TM) is an emerging, alternative synchronization abstraction that promises to alleviate these difficulties. With the TM model, code that accesses shared memory objects are organized as transactions, which speculatively execute, while logging changes. If transactional conflicts are detected, one of the conflicting transaction is aborted and re-executed, while the other is allowed to commit, yielding the illusion of atomicity. TM for multiprocessors has been proposed in software (STM), in hardware (HTM), and in a combination (HyTM). This dissertation focuses on supporting the TM abstraction in distributed systems, i.e., distributed STM (or D-STM). We focus on three problem spaces: cache-coherence (CC), conflict resolution, and replication. We evaluate the performance of D-STM by measuring the competitive ratio of its makespan --- i.e., the ratio of its makespan (the last completion time for a given set of transactions) to the makespan of an optimal off-line clairvoyant scheduler. We show that the performance of D-STM for metric-space networks is O(N^2) for N transactions requesting an object under the Greedy contention manager and an arbitrary CC protocol. To improve the performance, we propose a class of location-aware CC protocols, called LAC protocols. We show that the combination of the Greedy manager and a LAC protocol yields an O(NlogN s) competitive ratio for s shared objects. We then formalize two classes of CC protocols: distributed queuing cache-coherence (DQCC) protocols and distributed priority queuing cache-coherence (DPQCC) protocols, both of which can be implemented using distributed queuing protocols. We show that a DQCC protocol is O(NlogD)-competitive and a DPQCC protocol is O(log D_delta)-competitive for N dynamically generated transactions requesting an object, where D_delta is the normalized diameter of the underlying distributed queuing protocol. Additionally, we propose a novel CC protocol, called Relay, which reduces the total number of aborts to O(N) for N conflicting transactions requesting an object, yielding a significantly improvement over past CC protocols which has O(N^2) total number of aborts. We also analyze Relay's dynamic competitive ratio in terms of the communication cost (for dynamically generated transactions), and show that Relay's dynamic competitive ratio is O(log D_0), where D_0 is the normalized diameter of the underlying network spanning tree. To reduce unnecessary aborts and increase concurrency for D-STM based on globally-consistent contention management policies, we propose the distributed dependency-aware (DDA) conflict resolution model, which adopts different conflict resolution strategies based on transaction types. In the DDA model, read-only transactions never abort by keeping a set of versions for each object. Each transaction only keeps precedence relations based on its local knowledge of precedence relations. We show that the DDA model ensures that 1) read-only transactions never abort, 2) every transaction eventually commits, 3) supports invisible reads, and 4) efficiently garbage collects useless object versions. To establish competitive ratio bounds for contention managers in D-STM, we model the distributed transactional contention management problem as the traveling salesman problem (TSP). We prove that for D-STM, any online, work conserving, deterministic contention manager provides an Omega(max[s,s^2/D]) competitive ratio in a network with normalized diameter D and s shared objects. Compared with the Omega(s) competitive ratio for multiprocessor STM, the performance guarantee for D-STM degrades by a factor proportional to s/D. We present a randomized algorithm, called Randomized, with a competitive ratio O(sClog n log ^{2} n) for s objects shared by n transactions, with a maximum conflicting degree C. To break this lower bound, we present a randomized algorithm Cutting, which needs partial information of transactions and an approximate TSP algorithm A with approximation ratio phi_A. We show that the average case competitive ratio of Cutting is O(s phi_A log^{2}m log^{2}n), which is close to O(s). Single copy (SC) D-STM keeps only one writable copy of each object, and thus cannot tolerate node failures. We propose a quorum-based replication (QR) D-STM model, which provides provable fault-tolerance without incurring high communication overhead, when compared with the SC model. The QR model stores object replicas in a tree quorum system, where two quorums intersect if one of them is a write quorum, and ensures the consistency among replicas at commit-time. The communication cost of an operation in the QR model is proportional to the communication cost from the requesting node to its closest read or write quorum. In the presence of node failures, the QR model exhibits high availability and degrades gracefully when the number of failed nodes increases, with reasonable higher communication cost. We develop a protoytpe implementation of the dissertation's proposed solutions, including DQCC and DPQCC protocols, Relay protocol, and the DDA model, in the HyFlow Java D-STM framework. We experimentally evaluated these solutions with respective competitor solutions on a set of microbenchmarks (e.g., data structures including distributed linked list, binary search tree and red-black tree) and macrobenchmarks (e.g., distributed versions of the applications in the STAMP STM benchmark suite for multiprocessors). Our experimental studies revealed that: 1) based on the same distributed queuing protocol (i.e., Ballistic CC protocol), DPQCC yields better transactional throughput than DQCC, by a factor of 50% - 100%, on a range of transactional workloads; 2) Relay outperforms competitor protocols (including Arrow, Ballistic and Home) by more than 200% when the network size and contention increase, as it efficiently reduces the average aborts per transaction (less than 0.5); 3) the DDA model outperforms existing contention management policies (including Greedy, Karma and Kindergarten managers) by upto 30%-40% in high contention environments; For read/write-balanced workloads, the DDA model outperforms these contention management policies by 30%-60% on average; for read-dominated workloads, the model outperforms by over 200%. Ph. D.

In distributed transactional memory (TM) systems, both the management and consistency of a distributed transactional object are ensured by a cache-coherence protocol. We formalize two classes of cache-coherence protocols: distributed queuing cache-coherence (DQC) protocols and distributed priority queuing cache-coherence (DPQC) protocols, both of which can be implemented based on a given distributed queuing protocol. We analyze the two classes of protocols for a set of dynamically generated transactions and compare their time complexities against that of an optimal offline clairvoyant algorithm. We show that a DQC protocol is O(Nlog Dδ)-competitive and a DPQC protocol is O(log Dδ)-competitive for a set of N transactions, where Dδ is the normalized maximum communication latency provided by the underlying distributed queuing protocol.

In this paper, we present an approximate method for solution of load-dependent, closed queuing networks having general service time distributions with low variability. The proposed technique is an extension of Marie's (1980) method. In the methodology, conditional throughputs are obtained by an iterative procedure. The iterations are repeated until an invalid result is detected or no improvements are found. We demonstrate the performance of the technique with 10 different examples. On average, the solutions have 5% or lower deviations when compared to simulation results. © 2010 Elsevier B.V. All rights reserved.

An application of a spatially distributed queuing model to an ambulance system is presented. The purpose of this research was to assess the usefulness of a variation of the “hypercube” queuing model developed specifically for modeling an ambulance system. The model was applied to the emergency medical system of Greenville County, South Carolina using historical data. Results indicate that the model provides reasonably accurate estimates of system performance measures when the input parameters can be accurately specified.

Distributed queuing collision avoidance (DQCA) is a distributed MAC protocol for WLAN systems that offers near optimum performance. The protocol implements a reservation scheme that ensures collision-free data transmissions for high traffic load and switches smoothly and automatically to a random access mechanism when the traffic load is light, improving the delay performance for this situation. In this article the DQCA protocol operation is thoroughly described, and its algorithm rules are given. Furthermore, an enhanced cross-layer scheduling mechanism is also proposed for inclusion in the protocol procedure. This mechanism employs a virtual priority function to reschedule transmissions according to a cross-layer design. Two possible configurations are described in this article by including a PHY-MAC dialog involving channel stale information and the waiting time of the packets in the system, offering a trade-off between throughput maximization and fairness. The performance in terms of throughput and mean delay of DQCA and the two cross-layer schemes has been evaluated through simulations, and a significant enhancement over legacy IEEE 802.11 operation is achieved. The obtained results emphasize the advantages of the proposed schemes and the importance of cross-layer design in wireless communication systems.

This article proposes two scheduling algorithms based on the Distributed Queuing Collision Avoidance MAC protocol for WLAN systems with heterogeneous voice and data traffic. The proposed schemes implement service differentiation and an opportunistic transmission policy by means of a PHY-MAC cross-layer dialog. In particular, transmissions are scheduled taking into account the service class, the state of the wireless channel, and the waiting time of messages at the MAC. Both schemes achieve significant performance improvement in terms of throughput and mean message delay, and increase the number of supported voice nodes in the system. The two mechanisms have different performance behavior as they present a trade-off between efficiency and fairness among the nodes. The obtained results emphasize the advantages of the proposed schemes and the importance of cross-layer design in wireless communication systems.

Since 1987 the standards committee IEEE 802.6 is defining a new metropolitan area network based on a dual bus. It is called Distributed Queue Dual Bus (DQDB) and is highly compatible with the ATM switch technology. This paper deals with the evolution of the DQDB protocol from the performance point of view. First a review of the modifications and protocol enhancements for the Distributed Queuing Protocol is given. Based on detailed simulation models for the various protocols some results are presented, which depict the impact of the protocol modifications on the performance. Furthermore, two strategies of connecting an ATM link to a DQDB backbone are considered in order to reflect the performance behaviour of the DQDB system under asymmetric load conditions and to point out the influence of different priority classes.