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.     

Fairness of medium access control protocols for multi-hop ad hoc wireless networks

It is an undisputed fact that fairness is an important element of a well-designed medium access control (MAC) protocol for multi-hop ad hoc networks. However, most popular MAC protocols still fail to attain an acceptable level of fairness in media access although several enhancements have been proposed in the past. These proposed enhancements are effective only in limited scenarios. It is our objective in this paper to do the following: (i) analyze the fairness problem; (ii) identify and analyze the three main causes leading to the fairness problem, namely, the lack of synchronization problem (LSP), the double contention areas problem (DCP) and the lack of coordination problem (LCP); (iii) based on the analysis, propose a new MAC protocol named the extended hybrid asynchronous time division multiple access (EHATDMA) as a solution. For better assessment of fairness, we have designed an index named max–min fairness index, which is scenario-independent and reflects the difference between the fair sharing provided by a protocol and the ideal max–min fair sharing. Comprehensive simulations have been carried out to compare the fairness of our protocol with the existing ones. Simulation results show that although the existing protocols employ various enhancements meant to improve the fairness property, most of them are still strongly biased towards throughput when a conflict between throughput and fairness arises. In addition, the fairness performance of these protocols varies widely from one scenario to another. On the other hand, EHATDMA strikes a good balance between throughput and fairness. It delivers a consistently high level of fairness regardless of network topology, traffic load and radio parameters, yet maintains high throughput whenever possible. Our simulation results also reveal that the most important mechanism affecting the fair sharing of radio channels among flows is the non-work-conserving mechanism.     

Firing rate optimization of cyclic timed event graphs by token allocations

In this paper, we deal with the problem of allocating a given number of tokens in a cyclic timed event graph (CTEG) so as to maximize the firing rate of the net. We propose three different approaches. The first one is a “greedy” incremental procedure that is computationally very efficient. The only drawback is that the convergence to the optimum is guaranteed only when the set of places where tokens can be allocated satisfies given constraints. The other two procedures involve the solution of a mixed integer linear programming problem. The first one needs the knowledge of the elementary circuits, thus it is convenient only for those classes of CTEG whose number of elementary circuits is roughly equal to the number of places, such as some kanban-systems. On the contrary, the second one enables one to overcome this difficulty, thus providing an efficient tool for the solution of allocation problems in complex manufacturing systems like job-shop systems.     

A detailed review of energy-efficient medium access control protocols for mobile sensor networks

This article reviews the state-of-the-art energy-efficient contention-based and scheduled-based medium access control (MAC) protocols for mobile sensor networks (MSNs) by first examining access schemes for wireless sensor networks (WSNs). Efficient and proper mobility handling in sensor networks provides a window of opportunity for new applications. Protocols, such as S-MAC, reduce energy consumption by putting nodes to sleep after losing to channel contention or to prevent idling. Sleeping is a common method for energy-efficient MAC protocols, but delay depends on sleep duration or frame time, and longer delays lead to higher packet lost rate when nodes are unsynchronized due to network mobility. MS-MAC extends S-MAC to include mobility-awareness by decreasing this sleep duration when mobility is detected. S-MAC with extended Kalman filter (EKF) reduces mobility-incurred losses by predicting the optimal data frame size for each transmission. MMAC utilizes a dynamic mobility-adaptive frame time to enhance TRAMA, a scheduled-based protocol, with mobility prediction. Likewise, G-MAC utilizes TDMA for cluster-based WSNs by combining the advantages of contention and contention-free MACs. Z-MAC also combines both methods but without clustering and allows time slot re-assignments during significant topology changes. All of the above MAC protocols are reviewed in detail.     

Guaranteeing hard real-time traffic with legitimately short deadlines with the timed token protocol

Synchronous bandwidth, defined as the maximum time a node is allowed to send its synchronous messages while holding the token, is a sensitive parameter for deadline guarantees of synchronous messages in any timed token network. In order to offer such guarantees, synchronous bandwidth has to be allocated carefully to each individual node. This paper studies the synchronous bandwidth allocated to those synchronous message streams whose deadlines are less than twice the Target Token Rotation Time (TTRT). A new approach for allocating synchronous bandwidth to such streams, which can be used with any previously published local synchronous bandwidth allocation (SBA) for guaranteeing a general synchronous message set with its minimum deadline (D_min) no less than 2 · TTRT, is proposed. The proposed scheme can be applied efficiently in practice to any general synchronous message set with D_min > TTRT. Numerical examples are presented to demonstrate the enhanced performance of this new local scheme over any of the previously published local SBA schemes.     

Deciding properties of timed transition models

Real-time distributed systems are modeled by a times transition model (TTM). For any finite-state TTM, decision procedures are provided for checking a small but important class of properties (specified in real-time temporal logic). The procedures are linear in the size of the system reachability graph. The class of properties includes invariance, precedence, eventuality and real-time response specifications     

Performance study of SRMA multiple access protocols

In this paper we are concerned with packet broadcast networks in which users communicate with the central station. The key problem is multiple access of a shared broadcast channel. The performance of a family of SRMA (split-channel reservation multiple access) protocols for multiple access proposed by Tobagi and Kleinrock (1976) is studied. We analyse the performance of SRMA-RM (request message) and modified SRMA-RAM (request answer message) protocols in terms of the throughput and the average packet delay. Bounds on the throughput are also established for both protocols.     

Some optimization problems for timed marked graphs

Discrete event dynamic systems are frequently encountered in complex man-made systems. Such a system is often described in terms of a timed Petri net. For periodic behaviour of such a system, a timed marked graph provides a convenient and powerful tool of modelling and analysis. In this paper we define three optimization problems for such a system. All of these problems are formulated as mixed integer linear programming (MIP) problems. To improve computational efficiency, we introduce ‘cuts’ to these MIP problems, and the effect of such cuts is examined through computational experiments on some test problems.     

Queueing analysis of buffered slotted multiple access protocols

Much of the literature on the performance evaluation of multiple access protocols has assumed a buffer capacity of one unit. This assumption is not realistic. In practice the buffer capacities used are larger than one unit in order to reduce the probability of packet rejection. This is more crucial for multiple access protocols, which allow moderate to high values of the expected throughput (URN, Random TDMA etc.).In this paper, a model appropriate for the analysis of buffered slotted multiple access schemes is proposed. The method can be applied to several multiple access protocols such as the URN protocol, the ALOHA protocol, Random TDMA etc. The cases of infinite and finite buffer capacity are examined separately but under the same basic assumptions. The analysis is based on the assumption that each user process can be modelled as an M/G/1 queueing system. The proposed method requires a small amount of computation and is characterized by a high speed, a fact that simplifies the buffer's design as well. The solution obtained is extremely accurate and exhibits excellent agreement with simulation results, which corroborate the accuracy of the model. The special case when the buffer capacity is equal to 1 is examined. In that case, the present approach also allows for computation of the packet delay distribution.     

Analysis and performance evaluation of HYPERchannel access protocols

HYPERchannel [1,3,5,7] is a local network configuration with random access to the global transmission medium and with ‘Carrier Sense’ techniques. Conflicts are resolved by a fixed priority scheduling of retransmissions.This paper presents a performance evaluation of HYPERchannel access protocols for different types of user systems. Analytical results and asymptotic relations are obtained for the throughput of HYPERchannel under different load characteristics.The fixed priority rule for retransmissions discriminates against low priority users; a modification of the access scheme (‘Fair HYPERchannel’) is proposed which compensates for this undesirable effect. The performance of this new protocol version is also evaluated.In a final section, the access schemes of HYPERchannel are compared with similar access protocols.     

Asymptotic properties of stochastic timed event graphs

This paper addresses the asymptotic properties of stochastic timed event graphs. The transition firing times are random variables with general distribution. Asymptotic properties with respect to the net structure, the transition firing times and the initial marking are established on the basis of some new performance bounds. Applications to manufacturing systems are presented. We prove in particular a conjecture which claims that the throughput rate of a transfer line decreases to a positive value when the number of machines increases.     

Customer access protocols for integrated services digital networks

After an introduction to the latest trends in the conception of local digital networks offering a variety of services including data and telephony, the interaction between customer access protocols and network architectures are discussed. The basic features of a customer-to-network signalling scheme that allows the full treatment of circuit-switched data calls at 64 kbit/s by the PCM local and trunk exchanges are presented, and the processing of packet-switched data calls by specialized network nodes accessed on demand via PCM facilities are discussed.     

Checking timed automata for linear duration properties

It is proved in this paper that checking a timed automaton M with respect to a linear duration property D can be done by investigating only the integral timed states of M,An equivalence relation is introduced in this paper to divide the infinite number of integral timed states into finite number of equivalence classes.Based on this,a method is proposed for checking whether M satisfies D.In some cases,the number of equivalence classes is too large for a computer to mainpulate,A technique for reducing the search-space for checking linear duration propoerty is also described.This technique is more suitable for the case in this paper than those in the literature because most of those techniques are designed for reachablility analysis.     

A local area network with ordered bus access by low level token passing

In local area networks with token-controlled access to the physical medium, the access rights are passed from one station (or node) to another by transferring a token. There is only one token owner at a time which controls the packet generation onto the physical medium. Token-controlled systems are deterministic, in contrast with systems controlled by carrier sense multiple access with collision detection (CSMA/CD), and therefore worst case access times or transaction times can be defined, which is an important characteristic in distributed process control systems. In this paper a token-passing scheme is described which may be added below a commercially available data link controller with CSMA/CD control. The performance of the two access protocols is compared.     

Performance investigation of a token passing access protocol for a multichannel optical fibre LAN

An alternative approach to multichannel local area network access is described. The new multichannel access scheme or protocol is based on a token passing arbitration policy. It is specifically intended for use with a starconfigured optical fibre LAN employing wavelength division multiplexing technology in order to provide a multichannel transmission medium. The multichannel network architecture comprises a single reservation channel and several equivalent speed data channels. Delay versus throughput performance characteristics for the network obtained by both analysis and discrete event simulation are shown. The multichannel token passing protocol is found to significantly improve these characteristics in comparison with a conventional single channel token passing approach using the same overall network transmission rate (i.e. the sum of the individual channel bit rates in the multichannel case). Furthermore, when the end-to-end propagation delay for an individual channel on the network becomes large, the multichannel token passing protocol is shown to exhibit an improved delay versus throughput performance over a multichannel protocol employing carrier sense multiple access with collision detection.     

基于随机时间自动机和统计模型检验技术的无线传感网络协议建模与分析

近年来,传感器技术得到了长足而有效的提升,无线传感网络(WSN)以其开放、动态的特征获得了极大的关注,并成为了互联网计算的一个重要组成.WSN系统行为复杂,经常面临信息丢失、节点动态变化等不确定因素,且网络中的节点一旦部署将很难更改、维护.因此,为了保证相关应用的正常工作,在系统设计阶段对WSN中的底层协议进行质量保障就成为了一项非常重要的研究问题.系统设计人员不仅需要保证协议功能上的正确性,还应该评估协议在目标工作环境下的性能,以保证其可以胜任相应的工作需求.针对以上问题,本文提出了一种基于随机时间自动机和统计模型检验技术的WSN协议建模、分析和评估途径.在建模阶段,首先将采用时间自动机对协议在理想环境下的基本业务流程进行建模.考虑到WSN系统实际工作中会遇到的各种不确定性因素,将用带权分枝来对模型进行扩展,生成协议的随机时间自动机.在验证阶段,首先采用经典模型检验技术,在理想时间自动机上检验相关功能性质,保证协议工作逻辑的正确性.为评估协议在不同条件下的具体性能,则在随机时间自动机上用统计模型检验技术对其进行数值分析,以进行参数配置、性能预测、协议比较等工作.为展示该途径的可用性及其技术细节,本文对两种著名的WSN时间同步协议,TPSN和FTSP分别进行了完整的建模与评估.     

Collision detection technique for multiple access protocols on radio channels

The carrier sense multiple access with collision detection protocol (CSMA/CD) has already gained wide commercial acceptance and is used in cable and optical-fibre based local computer networks. However, its use in radio channels is inhibited by the difficulty of sensing remote carriers in the presence of local transmission. A new collision detection technique for radio channels called time-split collision detection is introduced. Collision is detected by a sequence of carrier sense, preamble transmission and carrier sense again at the beginning of a packet transmission. Throughput analysis of a new multiple access protocol using time-split collision detection is also presented. The proposed protocol has throughput performance between those of the CSMA and CSMA/CD.     

On properties of RDT communication-induced checkpointing protocols

Rollback-dependency trackability (RDT) is a property stating that all rollback dependencies between local checkpoints are online trackable by using a transitive dependency vector. The most crucial RDT characterizations introduced in the literature can be represented as certain types of RDT-PXCM-paths. Here, let the U-path and V-path be any two types of RDT-PXCM-paths. We investigate several properties of communication-induced checkpointing protocols that ensure the RDT property. First, we prove that if an online RDT protocol encounters a U-path at a point of a checkpoint and communication pattern associated with a distributed computation, it also encounters a V-path there. Moreover, if this encountered U-path is invisibly doubled, the corresponding encountered V-path is invisibly doubled as well. Therefore, we can conclude that breaking all invisibly doubled U-paths is equivalent to breaking all invisibly doubled V-paths for an online RDT protocol. Next, we continue to demonstrate that a visibly doubled U-path must contain a doubled U-cycle in the causal past. These results can further deduce that some different checkpointing protocols actually have the same behavior for all possible patterns. Finally, we present a commendatory systematic technique for comparing the performance of online RDT protocols.