In this paper, we propose a decentralized algorithm for the discovery and operation of reliability-constrained routes in wireless ad-hoc networks called dRmin-routing. The algorithm uses locally available network status information about network topology and link properties that is collected proactively in order to discover a preliminary route candidate. This is followed by a distributed, reactive search along this preselected route to remove imprecisions of the locally recorded network status before making a final route selection. During route operation, dRmin-routing monitors routes and performs different kinds of route repair actions to maintain route reliability in order to overcome varying link reliabilities. We have implemented dRmin- routing and assess its performance in simulation experiments. A simulative comparison with Optimized Link State Routing (OLSR) shows that route reliability in wireless networks should receive more attention.

Information about channel quality is essential for channel selection and channel hopping in wireless ad-hoc networks. In this paper, we present a sophisticated channel quality metric, its implementation on commodity 802.11 hardware, and results of real experiments in our testbed. The metric has the following properties. First, collection of channel busy times as raw data exploits customary hardware mechanisms, yielding accurate values. Second, the accuracy of raw data is further improved by determining and subtracting the effect of internal traffic of overlapping channels. Third, corrected raw data are aggregated, making the metric more stable. Fourth, an exponential weighted moving average is applied, providing for adaptivity. Fifth and finally, several candidates to measure the volatility of raw data in a moving window regarding downward fluctuations are defined and applied, yielding channel quality metrics that are more conservative without being overly pessimistic. We have implemented each of these steps and present experimental results.

High-quality information about the network status is essential for the discovery and operation of routes and clusters in wireless ad-hoc networks. This requires permanent observation and assessment of nodes, links, and link metrics, and the exchange of gathered status data. In this paper, we present cTEx, a configurable topology explorer for wireless ad-hoc networks that efficiently detects and exchanges high-quality network status information during operation. To establish accurate status data about individual links, nodes transmit unicast probe frames with sequence numbers, which are received and processed by neighbors operating in monitor mode. By checking sequence numbers, nodes can detect frame loss without providing feedback to senders, and determine accurate packet delivery ratios for incoming links, serving as a statistical basis for more sophisticated link metrics. Regular unicast frames are also interpreted as probe frames to reduce bandwidth usage. We have implemented cTEx in a Wi-Fi testbed, evaluate its accuracy, status exchange delay, and overhead, and compare it to existing approaches.

Reliability of end-to-end communication is crucial for applications such as wireless networked control systems. To discover routes that satisfy specified reliability requirements, adaptive, conservative, and stable link reliability estimates are required. Traditional metrics do not support these objectives well enough. In this paper, we propose OB-EWMA (Outlier Bounded Exponential Weighted Moving Average) as link metric for reliability-constrained routing in contention-based wireless networks. We have implemented OB-EWMA along with a topology explorer, evaluate its fidelity in a Wi-Fi testbed, and compare it to other link metrics.

Applications with Quality of Service (QoS) requirements such as networked control systems are not well supported by today's off-the-shelf wireless standards such as IEEE 802.11 (WiFi). Specifying a range of minimally required base QoS and preferred QoS combined with dynamic scaling in this range can help to support QoS while improving network utilization. However, scaling is typically happening in a greedy and therefore unfair way, with each node trying to maximize its throughput. In this paper, we present a cooperative algorithm for dynamical cooperative bandwidth scaling using a time token bucket approach. We show that our approach improves bandwidth utilization in a fair way. Furthermore, it dynamically reacts to topology changes, e.g. due to node mobility, as well as to traffic of uncooperative (external) nodes. Finally, it achieves stable bandwidth usage of participating nodes, even in networks with external traffic. We evaluate our approach in an IEEE 802.11 testbed.

In this paper, we propose a new approach for Quality-of-Service routing in wireless ad-hoc networks called rmin-routing, with the provision of statistical minimum route reliability as main route selection criterion. Discovery of rminroutes is based on a network model with statistical link reliabilities, which are combined into path reliabilities. To achieve specified minimum route reliabilities, we improve the reliability of individual links by well-directed retransmissions, to be applied during the operation of routes. To select among a set of candidate routes, we define and apply route quality criteria concerning network load. We have applied rmin-routing in sample topologies, and compare it to other routing approaches.

Cognitive radio networks provide solutions for the coexistence of primary users (license holders) and secondary users within a licensed spectrum. In this paper, we present and assess a three-dimensional stabilization protocol for cognitive radio networks, addressing the dimensions time, channel, and space. For stabilization in time and space, nodes agree on a global time structure consisting of superslots and macroslots. For stabilization of network-wide channel usage, nodes determine and share global schedules, which assign channels of sufficient quality to macroslots. The stabilization protocol realizes a conservative strategy, whereby nodes only transmit on channels that have a sufficient locally measured quality and have been assigned in a recent schedule. Furthermore, the protocol is robust against topology changes. To assess the stabilization capability of the protocol, we introduce the notion of schedule-consistency, and evaluate the protocol performance in a series of ns-3 simulations.

Spectrum sensing using energy detectors is a promising, simple and flexible approach for cognitive radio networks to detect primary users. In this paper, we present a new energy detector, called Selective Clustering Energy Detector (SCED. This detector determines dynamic thresholds based on clustering and aggregating selected sequences of energy measurements obtained from a software-defined radio. We assess SCED in a series of controlled experiments on real hardware, and compare its performance and reliability to reference cell based energy detectors reported in the literature. We show that SCED surpasses these detectors in all experiments, in particular in scenarios with non-transmission-free reference cells and during the startup phase.

For various applications such as formation of electronically coupled truck convoys, status monitoring of freight trains, and operation of production lines, a line topology is a natural and suitable network structure. It is natural, because the physical layout in these applications is linear; it is suitable, because it supports the functionality of these applications, e.g. fast detection of convoy splits, network clustering, and routing between network nodes. In this paper, we propose an approach for the dynamic establishment and repair of an overlay line topology in wireless networks. To form this topology, only stable bidirectional links, i.e. links that are sufficiently reliable in both directions, are selected. For this purpose, we present an approach for the dynamic detection and statistical assessment of links. We have devised a protocol for both approaches, and have implemented, deployed, and tested this protocol on an industrial hardware platform using Bluetooth Low Energy.

In industrial automation, there is strong interest in using wireless technologies to run production environments, and in particular to build networked control systems. To operate such networks effectively, sufficient control over the communication system is needed, regarding, e.g., bandwidth usage, frame latency, and frame loss. In this paper, we present an approach for traffic shaping that applies a variant of the token bucket algorithm, and an approach for traffic monitoring in order to determine network overload. In particular, we introduce and apply a metric called unusable wasted bandwidth ratio, which is derived from the number of unusable wasted tokens to detect network overload locally. We have implemented both approaches on a commercial platform with WLAN adapters, and have conducted real experiments to assess their performance.

In this paper, we present a novel QoS (quality of service) multicast routing protocol (QMRP) for partially mobile wireless TDMA (time division multiple access) networks. This protocol has been inspired by the typical requirements of industrial networked control systems, i.e., systems exhibiting real-time behavior and therefore requiring predictable communication bandwidths and transfer delays. QMRP is capable of iteratively constructing routing trees, and of assigning time slots along the branches of these trees such that a specific communication bandwidth is guaranteed and delays can be predicted. Special attention is given to mobile nodes, which require specialized QoS routing trees. A detailed evaluation gives insights into the operation and performance of QMRP.

In wireless networks, topology information is often of great importance. Knowledge about the communication and interference topology enables more efficient and reliable use of the wireless medium, and some wireless protocols even require knowledge about nodes in sensing range. Manually measuring and configuring topology information of ad hoc networks is very cumbersome. This paper presents ATDP (Automatic Topology Discovery Protocol), a protocol for the automatic detection of communication, interference, and sensing topologies in wireless TDMA networks. Furthermore, the gathered information is distributed across the network using exclusively assigned TDMA time slots, thus providing all nodes with a consistent view of the network topologies. Experiments with our implementation on Imote2 nodes show that ATDP reliably detects topologies of multihop networks. The experiments also show that consideration of the detected interference links in a TDMA schedule significantly improves packet delivery rates and thus reliability of the network.

In networked control systems, the Try-Once-Discard (TOD) protocol is of high interest because its properties can be characterized by Lyapunov functions. This feature makes it practical to incorporate TOD into Lyapunov-based design of linear and nonlinear control systems, yielding a self-contained theory for system stabilization. In previous work, candidates for TOD realizations for single-hop (wired and wireless) networks have been proposed. However, it has been a hitherto open question whether TOD can be realized in wireless multihop networks. In fact, it is far from obvious how dynamic value-based competition with deterministically bounded maximum delay, as required by TOD, is achievable in wireless multihop networks. In this paper, we give a positive answer to this question, by presenting a functionally complete realization of TOD in wireless multihop networks. Our solution is based on highly accurate multihop tick synchronization, and applies an algorithm for collision-protected network-wide value arbitration with deterministic delay. We provide experimental evidence for the feasibility of our solution on existing micro controller platforms, and assess our TOD realization in a batch reactor scenario.

SUMMARY In wireless networks formed of battery‐powered nodes, energy consumption is a major concern. On the communication side, energy can be saved by switching transceivers to idle or power‐down mode when not needed. To this end, duty cycling protocols located at medium access control level have been devised. These protocols have in common that they define modified carrier sense multiple access with collision avoidance schemes and that they assume the availability of some time synchronization mechanism. This strongly limits their potential to reduce energy consumption, as well as their flexibility regarding activity phases. In this paper, we propose a more flexible and energy‐efficient solution for duty cycling, which is based on our experimental wireless medium access control protocol MacZ. Flexibility is strengthened by the possibility to define weakly periodic activity periods. Energy efficiency is improved by the possibility to assign exclusive transmission slots, thereby switching transceivers to active mode only when needed. Both measures are supported by an underlying protocol for accurate, deterministic tick and time synchronization. We assess our solution and compare it to well‐known duty cycling protocols on the basis of real‐life scenarios. Copyright © 2012 John Wiley & Sons, Ltd.

We present the Arbitrating Value Transfer Protocol (AVTP), a deterministic binary countdown algorithm for multi-hop wireless networks. AVTP enables deterministic arbitration among contending nodes within a given hop radius, which may be chosen to reach network-wide arbitration, thereby exceeding the capabilities of existing protocols. In addition, the deterministic agreement on data values among all nodes is supported. Even taking into account the limitations of actual hardware devices, AVTP provides small and constant arbitration delays, and has low and bounded complexity. It does not require bidirectional links, and is robust against topology changes. Applications of AVTP include deterministic and robust leader election with bounded delay.Finally, we have implemented and evaluated AVTP on Imote2 sensor nodes.

Reservation-based wireless TDMA networks can provide deterministic quality-of-service guarantees to multi-hop data flows. The challenge is to route the flows and schedule appropriate transmission slots in a resource-efficient way. In this paper, we study the fundamental question whether multi-path routing, i.e. concurrent use of multiple paths for transmission of data belonging to the same flow, may yield better solutions to the joint routing and slot scheduling problem than single-path routing approaches. To answer this question, we first define an accurate network model. We then devise a branch-and-bound algorithm that computes optimal multi-path and single-path solutions to the joint routing and slot scheduling problem. We apply the algorithm to a large number of scenarios in randomly generated networks and compare optimal network load and end-to-end delay metric values in order to quantify the benefit of multi-path routing over the single-path approach. Our results show that in the studied settings, it is quite rare for multi-path solutions to surpass the optimal single-path solution. Multi-path routing should therefore not be considered an option to improve performance in reservation-based TDMA networks with random topologies.

In this paper, we present black burst synchronization (BBS), a novel protocol for decentralized network-wide tick synchronization in wireless ad hoc networks, located at MAC level. We argue that tick synchronization is sufficient for multi- hop medium slotting, and that it can be used as a basis for time synchronization. BBS is based on the exchange of synchronized tick frames, which are protected against collisions by a special encoding with black bursts. We deduce a deterministic bound for tick accuracy that depends linearly on maximum network diameter, clear channel assessment delay jitter, and transceiver switching time only. In an improved version of BBS, tick accuracy becomes independent of switching time. We show that BBS has low complexity in terms of communication, computation, storage, and energy consumption, provides a low and deterministic convergence delay, and is robust against node movements and node failures. We have implemented BBS on MICAz motes, and have experimentally validated its predicted behavior. In addition, we have simulated BBS to study its behavior in larger and denser networks.

In this paper, we present a new MAC layer called MacZ, specifically devised for flexible QoS support in mobile ad- hoc networks. MacZ provides multi-hop tick synchronization, network-wide medium slotting, contention-free transmission with global reservations, contention-based transmission with priorities, and is robust against topology changes. We describe the main functionalities of MacZ, show results of performance simulations that provide evidence for the effectiveness of the QoS mechanisms, and discuss related MAC layers.

A generic approach to the formal specification of system requirements is presented. It is based on a pool of requirement patterns, which are related to design patterns well-known in object-oriented software development. The application of such patterns enhances the reusability and genericity as well as the intelligibility of the formal requirement specification. The approach is instantiated by a tailored real-time temporal logic and by selecting building-automation systems as application domain. With respect to this domain, the pattern discovery and reuse tasks are explained and illustrated and a set of typical requirement patterns is presented. The approach has the potential of reducing the effort to formally specify system requirements.

Conformance is one of the key notions in the context of open systems and therefore must be precisely defined. Existing formalizations define conformance independently of the environment into which the open system will be embedded. It is argued that it is, in general, not adequate to guarantee conformance in an intuitive sense. Conformance should relate the visible behavior defined by two specifications, which conceptually occurs at external interaction points. Based on this assumption, an additional condition which is sufficient to overcome the difficulty is identified. The condition is based on compatibility between interaction points, a notion which is introduced and formally defined. An approach to verify this condition and some general results are presented. The application of this approach to open systems interconnection (OSI) is outlined.>

The service specification concept has acquired an increasing level of recognition by protocol designers. This architectural concept influences the methodology applied to service and protocol definition. Since the protocol is seen as the logical implementation of the service, one can ask whether it is possible to formally derive the specification of a protocol providing a given service. This paper addresses this question and presents an algorithm for deriving a protocol specification from a given service specification. It is assumed that services are described by expressions, where names identifying both service primitives and previously defined services are composed using operators for sequence, parallelism and alternative. Services and service primitives may have input and output parameters. Composition of services from predefined services and service primitives is also permitted. The expression defining the service is the basis for the protocol derivation process. The algorithm presented fully automates the derivation process. Future work will focus on the optimization of traffic between protocol entities and on applications.

Article Free Access Share on Deriving protocol specifications from service specifications Authors: G von Bochmann Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, Canada Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, CanadaView Profile , R Gotzhein Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, Canada Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, CanadaView Profile Authors Info & Claims SIGCOMM '86: Proceedings of the ACM SIGCOMM conference on Communications architectures & protocolsSeptember 1986Pages 148–156https://doi.org/10.1145/18172.18190Published:01 August 1986Publication History 33citation398DownloadsMetricsTotal Citations33Total Downloads398Last 12 Months22Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF