Constraint-based structuring of network protocols

Summary. The complexity of designing protocols has led to compositional techniques for designing and verifying protocols. We propose a technique based on the notion of parallel composition of protocols. We view a composite protocol as an interleaved execution of the component protocols subject to a set of constraints. Using the constraints as building blocks, we define several constraint-based structures with each structure combining the properties of the component protocols in a different way. For instance, the component protocols of a multifunction protocol can be structured so that the composite protocol performs all the individual functions concurrently or performs only one of them depending on the order of initiation of the component protocols. We provide inference rules to infer safety and liveness properties of the composite protocol. Some properties are derived from those of the component protocols while others are derived from the structuring mechanism (the set of constraints) used to combine the component protocols. Received: October 1996 / Accepted: August 1998     

Validation of protocols with temporal constraints

Reachability analysis is the most popular and most used method in protocol validation. It consists in constructing a graph called a reachability graph, describing communication of machines exchanging messages through FIFO channels. The states and structure of this graph are then analysed according to given properties to validate the related communication protocol. In this paper, we deal with a generalization of reachability analysis to take into account quantitative temporal constraints in protocol validation. A temporal reachability graph is designed, and we show how it can be used to analyse new general properties of communication protocols submitted to temporal constraints.     

Performance evaluation of wireless sensor network protocols for industrial applications

Recently, distributed wireless microsensor systems have provided more flexible leverage to emerging industrial applications. The tiny distributed wireless microsensor network systems, however, should be designed to overcome various constraints such as limited energy, bandwidth limit, and unexpected failure of communication under disturbances. In addition, their network topologies need to be managed with designated communication protocols. Thus, design of microsensor network protocols still needs to be application-specific. It should be also evaluated through designated tools at each level of networking characteristics. This research describes essential factors that affect the performance of sensor network systems in the design of wireless microsensor network protocols, and presents effective time-based network protocol and performance evaluation tool which are applicable for various protocols in industrial applications. The developed network evaluation tool, called TIE/MEMS, also includes functional comparison with recent protocols proposed for wireless microsensor networks, and provides design guidelines for multi-sensor network systems needed for emerging industrial applications.     

Unicast routing protocols for urban vehicular networks: review,taxonomy, and open research issues

Over the past few years, numerous traffic safety applications have been developed using vehicular ad hoc networks（VANETs）. These applications represent public interest and require network-wide dissemination techniques. On the other hand, certain non-safety applications do not require network-wide dissemination techniques.Such applications can be characterized by their individual interest between two vehicles that are geographically apart. In the existing literature, several proposals of unicast protocols exist that can be used for these non-safety applications. Among the proposals, unicast protocols for city scenarios are considered to be most challenging.This implies that in city scenarios unicast protocols show minimal persistence towards highly dynamic vehicular characteristics, including mobility, road structure, and physical environment. Unlike other studies, this review is motivated by the diversity of vehicular characteristics and difficulty of unicast protocol adaption in city scenarios.The review starts with the categorization of unicast protocols for city scenarios according to their requirement for a predefined unicast path. Then, properties of typical city roads are discussed, which helps to explore limitations in efficient unicast communication. Through an exhaustive literature review, we propose a thematic taxonomy based on different aspects of unicast protocol operation. It is followed by a review of selected unicast protocols for city scenarios that reveal their fundamental characteristics. Several significant parameters from the taxonomy are used to qualitatively compare the reviewed protocols. Qualitative comparison also includes critical investigation of distinct approaches taken by researchers in experimental protocol evaluation. As an outcome of this review, we point out open research issues in unicast routing.     

High level communication functionalities for wireless sensor networks

In this paper we show how to establish a reliable and efficient high level communication system in a randomly deployed network of sensors equipped with directional antennas. This high level communication system enables the programming of the sensor network using high level communication functionalities without the burden of taking care of their physical capacities (low range, unidirectional links, single frequency, presence of collisions, etc.). The high level communication functionalities we offer include point-to-point communication, point-to-area communication, and one-to-all communication. The basic idea to implement this system is to simulate a virtual network that emerges from the ad-hoc network using self-organization, self-discovery and collaborative methods. We also analyse the efficiency, scalability and robustness of the proposed protocols.     

Design and analysis of dynamic leader election protocols in broadcast networks

Summary.  The well-known problem of leader election in distributed systems is considered in a dynamic context where processes may participate and crash spontaneously. Processes communicate by means of buffered broadcasting as opposed to usual point-to-point communication. In this paper we design a leader election protocol in such a dynamic context. As the problem at hand is considerably complex we develop the protocol in three steps. In the initial design processes are considered to be perfect and a leader is assumed to be present initially. In the second protocol, the assumption of an initial leader is dropped. This leads to a symmetric protocol which uses an (abstract) timeout mechanism to detect the absence of a leader. Finally, in the last step of the design processes may crash without giving any notification of other processes. The worst case message complexity of all protocols is addressed. A formal approach to the specification and verification of the leader election protocols is adopted. The requirements are specified in a property-oriented way and the protocols are denoted by means of extended finite state machines. It is proven using linear-time temporal logic that the fault-tolerant protocol satisfies its requirements. Received: September 1993 / Revised: September 1995     

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.     

A self-stabilizing transformer for population protocols with covering

Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in an extended population protocol model. Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication “speed”, which is reflected by their cover times. Second, we assume the existence of a special agent with an unbounded memory, the base station. The automatic transformer takes as an input an algorithm solving a static problem (and meeting some additional rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a re-execution approach (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.     

A full sensing window Random-Access algorithm for messages with strict delay constraints

We consider the Channel Multiple-Access problem for messages with strict delay constraints. The constraints are represented by an upper bound on the transmission delays. For this problem, and for binary collision-noncollision feedback per slot, we present a simple full sensing window Random-Access algorithm. We analyze the algorithm and we compute the fraction of maintained traffic and the expected delay for the successfully transmitted packet, for various input Poisson intensities and various values of the bound on the transmission delays.This work was supported by the U.S. Office of Naval Research, under Contract ONR-N14-86-K-0742.     

A wave propagation-based adaptive probabilistic broadcast containment strategy for reactive MANET routing protocols

The efficiency of broadcast propagation schemes can significantly condition the performance and effectiveness of mobile ad-hoc networks. Probabilistic forwarding strategies are considered between the most promising optimization approaches due to their inherent simplicity that makes them easy to implement on any platform, very fast and computationally inexpensive. In this work, we present a novel adaptive probabilistic approach for containing broadcast propagation in reactive network discovery based on modeling the broadcast propagation behavior as harmonic spherical waves generated by a single source, and hence determining the forwarding probability by considering how the intensity of a wave attenuates with its distance from the source. We used discrete event simulation to demonstrate how the proposed strategy can introduce appreciable benefits on the overall performance of modern broadcast-based reactive routing protocols, resulting in a real breakthrough in ad-hoc environments characterized by an high degree of mobility.