A performance analysis of block ACK scheme for IEEE 802.11e networks

The demand for the IEEE 802.11 wireless local-area networks (WLANs) has been drastically increasing along with many emerging applications and services over WLAN. However, the IEEE 802.11 medium access control (MAC) is known to be limited in terms of its throughput performance due to the high MAC overhead, such as interframe spaces (IFS) or per-frame based acknowledgement (ACK) frame transmissions. The IEEE 802.11e MAC introduces the block ACK scheme for improving the system efficiency of the WLAN. Using the block ACK scheme can reduce the ACK transmission overhead by integrating multiple ACKs for a number of data frames into a bitmap that is contained in a block ACK frame, thus increasing the MAC efficiency.In this paper, we mathematically analyze the throughput and delay performance of the IEEE 802.11e block ACK scheme in an erroneous channel environment. Our extensive ns-2 simulation results validate the accuracy of our analytical model and they further demonstrate that the block ACK scheme enhances the MAC throughput performance at the cost of the resequencing delay at the receiving buffer.     

TreeMAC: Localized TDMA MAC protocol for real-time high-data-rate sensor networks

Earlier sensor network MAC protocols focus on energy conservation in low-duty cycle applications, while some recent applications involve real-time high-data-rate signals. This motivates us to design an innovative localized TDMA MAC protocol to achieve high throughput and low congestion in data collection sensor networks, besides energy conservation. TreeMAC divides a time cycle into frames and each frame into slots. A parent node determines the children’s frame assignment based on their relative bandwidth demand, and each node calculates its own slot assignment based on its hop-count to the sink. This innovative 2-dimensional frame-slot assignment algorithm has the following nice theory properties. First, given any node, at any time slot, there is at most one active sender in its neighborhood (including itself). Second, the packet scheduling with TreeMAC is bufferless, which therefore minimizes the probability of network congestion. Third, the data throughput to the gateway is at least 1/3 of the optimum assuming reliable links. Our experiments on a 24-node testbed show that TreeMAC protocol significantly improves network throughput, fairness, and energy efficiency compared to TinyOS’s default CSMA MAC protocol and a recent TDMA MAC protocol Funneling-MAC. Partial results of this paper were published in Song, Huang, Shirazi and Lahusen [W.-Z. Song, R. Huang, B. Shirazi, and R. Lahusen, TreeMAC: Localized TDMA MAC protocol for high-throughput and fairness in sensor networks, in: The 7th Annual IEEE International Conference on Pervasive Computing and Communications, PerCom, March 2009]. Our new contributions include analyses of the performance of TreeMAC from various aspects. We also present more implementation detail and evaluate TreeMAC from other aspects.     

A survey on MAC protocols in OSA networks

Opportunistic spectrum access (OSA) networks have emerged as a hot research topic following the publication of Mitola’s seminal paper on cognitive radio network. Success of such networks will depend on efficient spectrum sensing techniques as well as effective medium access control protocols that will offer efficient mechanisms for dynamic spectrum allocation, coordination and management of spectrum heterogeneity. Work on such issues have just started and is still in a rudimentary stage. The main purpose of this paper is to provide a comprehensive review of the research done at the MAC layer of the OSA networks, especially with reference to ad hoc network design and spark more research in this area. A classification of the MAC layer protocols used in OSA networks is provided, and the essential features of the different MAC layer protocols for OSA networks are thoroughly analyzed and compared. Finally, open research issues for the MAC layer are discussed.     

CCS-MAC: Exploiting the overheard data for compression in wireless sensor networks

Both the overhearing and overhearing avoidance in a densely distributed sensor network may inevitably incur considerable power consumption. In this paper we propose a so-called CCS-MAC (collaborative compression strategy-based MAC) MAC protocol which facilitates to exploit those overheard data that is treated useless in traditional MAC protocols for the purpose of cost and energy savings. Particularly the CCS-MAC enables different sensor nodes to perform data compression cooperatively with regard to those overheard data, so that the redundancy of data prepared for the link layer transmission can be totally eliminated at the earliest. The problem of collaborative compression is analyzed and discussed along with a corresponding linear programming model formulated. Based on it a heuristic node-selection algorithm with a time complexity of (O(N²)) is proposed to the solve the linear programming problem. The node-selection algorithm is implemented in CCS-MAC at each sensor node in a distributed manner. The experiment results verify that the proposed CCS-MAC scheme can achieve a significant energy savings so as to prolong the lifetime of the sensor networks so far.     

Saving Support-Checks Does Not Always Save Time

Arc-consistency algorithms are the workhorse of backtrackers that maintain arc-consistency (MAC). This paper will provide experimental evidence that, despite common belief to the contrary, it is not always necessary for a good arc-consistency algorithm to have an optimal worst-case time-complexity. Sacrificing this optimality allows MAC solvers that (1) do not need additional data structures during search, (2) have an excellent average time-complexity, and (3) have a space-complexity that improves significantly on that of MAC solvers that have optimal arc-consistency components. Results will be presented from an experimental comparison between MAC-2001, MAC-3 _d and related algorithms. MAC-2001 has an arc-consistency component with an optimal worst-case time-complexity, whereas MAC-3 _d does not. MAC-2001 requires additional data structures during search, whereas MAC-3 _d does not. MAC-3 _d has a O(e+nd) of space-complexity, where n is the number of variables, d the maximum domain size, and e the number of constraints. We shall demonstrate that MAC-2001's space-complexity is O(edmin(n,d)). Our experimental results indicate that MAC-2001 was slower than MAC-3 _d for easy and hard random problems. For real-world problems things were not as clear.     

Performance evaluation of MAC transmission power control in wireless sensor networks

In this paper we provide a method to analytically compute the energy saving provided by the use of transmission power control (TPC) at the MAC layer in wireless sensor networks (WSN). We consider a classical TPC mechanism: data packets are transmitted with the minimum power required to achieve a given packet error probability, whereas the additional MAC control packets are transmitted with the nominal (maximum) power. This scheme has been chosen because it does not modify the network topology, since control packet transmission range does not change. This property also allows us to analytically compute the expected energy savings. Besides, this type of TPC can be implemented in the current sensor hardware, and it can be directly applied to several MAC protocols already proposed for WSN. The foundation of our analysis is the evaluation of L ratio, defined as the total energy consumed by the network using the original MAC protocol divided by the total energy consumed if the TPC mechanism is employed. In the L computation we emphasize the basic properties of sensor networks. Namely, the savings are calculated for a network that is active for a very long time, and where the number of sensors is supposed to be very large. The nodes position is assumed to be random – a normal bivariate distribution is assumed in the paper – and no node mobility is considered. In the analysis we stress the radio propagation and the distribution of the nodes in the network, which will ultimately determine the performance of the TPC. Under these conditions we compute the mean value of L. Finally, we have applied the method to evaluate the benefits of TPC for TDMA and CSMA with two representative protocols, L-MAC and S-MAC using their implementation reference parameters. The conclusion is that, while S-MAC does not achieve a significant improvement, L-MAC may reach energy savings up to 10–20%.     

The abstract MAC layer

A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network. We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks.     

A MAC protocol for low-rate UWB wireless sensor networks using directional antennas

Ultra-wideband (UWB) is a key solution for wireless connectivity, characterized by ultralow power consumption and a good degree of robustness to interference and multipath fading. Evidence of its significance, is its recent use in the IEEE 802.15.4a standard. UWB technology with joint consideration of directional antennas can benefit when compared to classical omni-directional antennas from the energy conservation viewpoint, which is of fundamental concern when it comes to wireless sensor networks (WSNs). However, exploiting directionality requires new approach in the design of a medium access control (MAC) protocol to be applied. In this work, idle nodes continuously rotate their receiving beams over 360° until a predefined preamble trailer is detected. The resulting scheme is a directional ultra-wideband MAC protocol, named DU-MAC, which deals effectively with the problem of deafness and the problem of determination of neighbors’ location. Simulation-based studies will demonstrate the effectiveness of the proposed protocol in many critical parameters, such as throughput and network lifetime.     

High throughput MAC layer multicasting over time-varying channels

Efficient, scalable and robust multicasting support from the MAC layer is needed for meeting the demands of multicast based applications over WiFi and mesh networks. However, the IEEE 802.11 protocol has no specific mechanism for multicasting. It implements multicasting using broadcasting at the base transmission rate. We identify two fundamental reasons for performance limitations of this approach in presence of interference and realistic time-varying channels: (a) Channel-state Indifference: irrespective of the current quality of the channel to the receivers, the transmission always uses the base transmission rate; (b) Demand Ignorance: packets are transmitted by a node even if children in the multicast tree have received those packets by virtue of overhearing. We propose a solution for MAC layer multicasting called HIMAC that uses the following two mechanisms: Unary Channel Feedback (UCF) and Unary Negative Feedback (UNF) to respectively address the shortcomings of 802.11. Our study is supported by measurements in simulations. We observe that the end-to-end throughput of multicast sessions using MAODV can be increased by up to 74% while reducing the end-to-end latency by up to a factor of 56.     

Orthogonal signaling-based queue status investigation method in IEEE 802.11

IEEE 802.11 specifies four different medium access control (MAC) protocols to coordinate multiple access in a wireless local area network (WLAN). Since several tens of stations can operate in a WLAN, the performance of MAC protocols is important for overall network efficiency. It has been observed that the IEEE 802.11 MAC protocols can be improved by knowing which station has a non-empty queue, i.e., queue status. The point coordination function (PCF) can use this information to avoid polling a station that has no pending data. The HCF controlled channel access can adapt polling parameters based on queue status information, especially when scheduling a bursty and variable bit-rate traffic. Previously suggested methods are rather limited in terms of accuracy and efficiency.In this paper, we propose a novel method to investigate the queue status of multiple stations by exploiting orthogonal signaling. With synchronous transmission of orthogonal codes and symbol level signal processing, the method allows all of the associated stations to report their queue status at the same time. Challenges that can arise in the implementation of the proposed method are identified, and their solutions are suggested. The feasibility of detecting orthogonal signals is thoroughly tested on a realistic channel model. To demonstrate the performance improvement of a MAC protocol, we applied the proposed method to PCF. Both analysis and simulation show that the modified PCF significantly outperforms not only the original PCF but also other previously suggested PCF enhancements.     

Receiver-initiated medium access control protocols for wireless sensor networks

One of the fundamental building blocks of a Wireless Sensor Network (WSN) is the Medium Access Control (MAC) protocol, that part of the system governing when and how two independent neighboring nodes activate their respective transceivers to directly interact. Historically, data exchange has always been initiated by the node willing to relay data, i.e. the sender. However, the Receiver-Initiated paradigm introduced by Lin et al. in 2004 with RICER and made popular by Sun et al. in 2008 with RI-MAC, has spawned a whole new stream of research, yielding tens of new MAC protocols. Within such paradigm, the receiver is the one in charge of starting a direct communication with an eligible sender. This allows for new useful properties to be satisfied, novel schemes to be introduced and new challenges to be tackled. In this paper, we present a survey comprising of all the MAC protocols released since the year 2004 that fall under the receiver-initiated category. In particular, keeping in mind the key challenges that receiver-initiated MAC protocols are meant to deal with, we analyze and discuss the different protocols according to common features and design goals. The aim of this paper is to provide a comprehensive and self-contained introduction to the fundamentals of the receiver-initiated paradigm, providing newcomers with a quick-start guide on the state of the art of this field and a palette of options, essential for implementing applications or designing new protocols.     

Aggregate message authentication codes (AMACs) with on-the-fly verification

Aggregate message authentication codes (AMACs) merge multiple authenticators for multiple receivers in multicast networks. We investigate this security notion, revise the definition, derive the lower bound, and present a generic construction through Bloom filters. Different from former research, we especially focus on the new property of AMACs: on-the-fly verification, which means that given the aggregated tag, each single message can be verified without obtaining other messages, i.e., the time for verifying a single message takes time complexity $\mathcal{O }(1)$ O ( 1 ) , compared to regular MAC schemes. We derive the security lower bound of such type of AMACs and present a generic approach to build them from essentially any standard MAC scheme by Bloom filter technique. Moreover, we achieve the theoretical lower bound on security strength by adopting optimal compressed Bloom filters.     

Optimal Hop Extended MAC protocol for wireless sensor networks

In wireless sensor MAC protocols, duty cycling has been exploited to put sensor nodes into sleeping state most of the time, thereby saving the limited battery efficiently. In this paper, we present a MAC protocol called Hop Extended MAC (HE-MAC) that enables a source node to transmit a data packet for multiple hops in a single duty cycle. It employs an EXP (Explorer) frame to set up the path for multiple hop transmission, which contains the information about the maximum number of hops that a packet can travel through in a single duty cycle. Using this information and an internal state of Ready-to-Receive (RTR), HE-MAC relays the packet beyond the termination of the data period. Along with our adaptive sleeping method, it additionally reduces power consumption. Then, we analytically obtain the packet latency of HE-MAC and find its optimal wakeup duration with respect to packet latency. Through ns-2 simulations, we observe that HE-MAC achieves 42.2% less power consumption and 23.6% less packet delay on average compared to RMAC [9] for a random topology of 300 nodes. With the allocated optimal wakeup duration, the latency of HE-MAC is reduced by 54.3% at maximum and 41.1% on average, compared to the case of default setting.     

SAM-MAC: An efficient channel assignment scheme for multi-channel ad hoc networks

Using multi-channel MAC protocols in mobile ad hoc networks (MANETs) is a promising way to improve the throughput performance. Channel assignment, which directly determines the efficiency of the frequency utilization, is the critical part of multi-channel schemes. Current 802.11-like schemes of multi-channel MAC do not efficiently use the multiple channels due to the overhead caused by channel assignment. Moreover, the control channel saturation problem limits the number of channels of these previous schemes. In this paper, we propose a new scheme called SAM-MAC (Self-Adjustable Multi-channel MAC), which features with one common channel and two half-duplex transceivers for each node. A method called self-adjustment is used to reassign the channels and balance the traffic on different channels. Due to less contention in common channel and smaller channel assignment overhead, this scheme increases the throughput compared with previous approaches. Control channels are free from saturation problem and can furthermore be used for data transmission.     

Towards estimating lifetime of ad hoc wireless networks

Ad hoc wireless networks possess highly constrained energy resources. The available energy resources should thus be used efficiently, in order to satisfy the requirements. Hence, the protocols at all the layers of the protocol stack should be energy aware and energy efficient. However, all the existing protocols are not energy aware and perform poorly in the presence of a limited power source. Even the energy aware protocols proposed for ad hoc networks do not consider all the characteristics of the underlying batteries. Hence, they fail to efficiently utilize the available energy. There also exist a few protocols, which, though battery unaware, unknowingly prove to be energy efficient. Thus, a mechanism is required to measure the efficiency of the protocols of ad hoc networks, in terms of the network lifetime. To the best of our knowledge, there has been no reported work till date for analyzing the lifetime of the ad hoc networks for various protocols.The protocols at all the layers of the protocol stack together decide the discharge of the battery source of a node. However, assuming that only the MAC protocols decide the battery performance, we focus on measuring the energy efficiency of MAC protocols. This paper primarily provides a novel generalized analytical model for estimating lifetime of ad hoc networks, in the presence of the following two kinds of MAC protocols: (i) reservation-based TDMA protocols and (ii) a specific class of CSMA protocols that try to follow a pattern, such as a round-robin scheduling, for packet transmission. Our model uses discrete-time Markov chain with probabilistic recovery to model the batteries of the ad hoc nodes. We found that our analytical model accurately estimates the lifetime of the network for various MAC protocols. We prove through analytical and simulation studies that energy awareness is crucial in deciding the performance of the MAC protocols for both homogeneous and heterogeneous ad hoc wireless networks.     

Energy efficient smart-relay-based cooperative MAC for wireless networks

An enormous number of papers investigated wireless cooperative networks over the last few years. Almost all have shown that cooperative transmission improves network performance significantly. However, none of these studies have considered the hidden and exposed terminal problems which appear due to the cooperative mechanisms of relay selection and transmission processes. The hidden terminal problems increase collisions and the exposed terminal problems increase bandwidth wastage, degrading the expected performance of cooperative networks. This paper addresses these problems of traditional wireless cooperative networks. We also propose a protocol called smart-relay-based-cooperative (SRcoop) MAC to optimally reduce the impacts of hidden and exposed terminal problems. We also illustrate an efficient relay selection mechanism that uses a back-up relay to increase transmission reliability. Our innovative model significantly improves the network throughput, end-to-end delay and energy efficiency over traditional cooperative MAC, 2rcMAC, LC-MAC, C-ARQ and Adere et al. protocols.     

Access delay in LonTalk MAC protocol

The study deals with the analysis of latency introduced by the media access control algorithm of LonTalk protocol registered as ANSI/CEA-709.1 standard and used in LonWorks control networking technology. The LonTalk protocol provides multicast communication which is a distinctive feature among control network protocols. The predictive p-persistent CSMA protocol built in the MAC sublayer uses the memoryless backoff, additive increase/additive decrease contention window adjustments, provides collision avoidance and optional collision detection.The behavior of the LonTalk MAC protocol, unlike of the other CSMA schemes, is forced not only by the traffic rate but also by the structure of the workload transmitted through the channel. Therefore, the predictive p-persistent CSMA performance depends on the load scenario defined as the specification of the input traffic generated to the network. In the study, a unified method of load scenario definition integrating various addressing and message service types, is used. The contribution of the paper is the adaptation of the analytical approach based on Markov chains to the evaluation of mean access delay of LonTalk protocol for any load scenario.     

DTSMA: Distributed time-spread multiple access for wireless mesh networks with IEEE 802.16d MAC protocol

This paper studies the use of IEEE 802.16d mesh MAC protocol for multi-hop networking in an indoor domestic environment. The mesh network is expected to support time-sensitive audio–video applications with stringent QoS requirement. In the literature, time-spread multiple access (TSMA) is a promising technology to provide a minimum throughput guarantee in a multi-hop mesh network with dynamic topology. However, existing TSMA schemes require the number of nodes in the entire network and their global maximum node degree, be known a priori to a central controller. The requirement is not practical. In view of this problem, this paper proposes a distributed time-spread multiple access (DTSMA) scheme. The proposed DTSMA has the following main contributions: (a) A method for each node to determine locally its polynomial coefficients without a priori global knowledge of node number and maximum node degree, and (b) A method to distribute to neighbours the locally determined polynomial coefficients, and to resolve collision between two sets of identical polynomial coefficients from two neighbouring nodes. The proposed DTSMA has been evaluated through extensive simulations to confirm that it can indeed preserve the capability of providing a minimum throughput guarantee in the absence of the a priori global knowledge. In benchmark against the de facto distributed coordinated scheduling (DCS) in the original IEEE 802.16d mesh MAC protocol under various domestic wireless channel conditions, DTSMA outperforms in terms of packet delivery ratio and average end-to-end packet delay which are important metrics for time-sensitive audio–video applications. Simulation results also show that DTSMA outperforms TSMA in terms of average end-to-end packet delay and average delay jitter when the severity of propagation impairment is high.     

Handling asymmetry in power heterogeneous ad hoc networks

Traditional MAC and routing protocols, which are primarily designed for homogeneous networks wherein all nodes transmit with the same power, suffer performance degradations when employed in power heterogeneous networks. The observed degradations are due to link asymmetry, which arises as high power nodes that do not sense the transmissions of low power nodes can potentially initiate transmissions that interfere with the low power communications. Link layer asymmetry in power heterogeneous networks not only disrupts the functioning of the routing protocol in use, but also results in unfairness in medium access. In this paper, we develop a cross-layer framework to effectively address the link asymmetry problem at both the MAC and the routing layers. At the MAC layer, the framework intelligently propagates low power control messages to the higher power nodes, so as to preclude them from initiating transmissions while there are low power communications in progress within their sensing range. At the routing layer, the framework facilitates the efficient use of unidirectional links. We perform extensive simulations to study the performance of our proposed framework in various settings, and show that the overall throughput in power heterogeneous networks is enhanced by as much as 25% over traditional layered approaches. In addition, we show that our schemes are also beneficial in power homogeneous settings, as they reduce the extent of false link failures that arise when the IEEE 802.11 MAC protocol is used. In summary, our framework offers a simple yet effective and viable approach for medium access control and for supporting routing in power heterogeneous ad hoc networks.     

On game theoretic DSA-driven MAC for cognitive radio networks

The game theoretic dynamic spectrum allocation (DSA) technique is an efficient approach to coordinate cognitive radios sharing the spectrum. However, existing game based DSA algorithms lack a platform to support the game process. On the other hand, existing medium access control (MAC) protocols for cognitive radio networks do not fully utilize the adaptability and intelligence of the cognitive radio (CR) to achieve efficient spectrum utilization, let alone fairness and QoS support. Therefore it is necessary to develop DSA-driven MAC protocols with the game theoretic DSA embedded into the MAC layer. In this paper, based on the analysis of challenges for the game theoretic DSA in realistic applications, we conclude that a unified game theoretic DSA-driven MAC framework should constitute of four integral components: (1) DSA algorithm, deriving the spectrum access strategy for data communication; (2) negotiation mechanism, coordinating players to follow the right game policy; (3) clustering algorithm, limiting the negotiation within one cluster for scalability; (4) collision avoidance mechanism, eliminating collisions among clusters. With our MAC framework, DSA-driven MAC protocols can be conveniently developed, as illustrated in the design process of a concrete QoSe-DSA-driven MAC protocol. The game theoretic DSA-driven MAC framework can fulfill merits of game theoretic DSA algorithms including high spectrum utilization, collision-free channel access for data communication, QoS and fairness support. Through simulations, the merits of the DSA-driven MAC framework are demonstrated.