A feedback-based decentralised coordination model for distributed open real-time systems

Moving towards autonomous operation and management of increasingly complex open distributed real-time systems poses very significant challenges. This is particularly true when reaction to events must be done in a timely and predictable manner while guaranteeing Quality of Service (QoS) constraints imposed by users, the environment, or applications. In these scenarios, the system should be able to maintain a global feasible QoS level while allowing individual nodes to autonomously adapt under different constraints of resource availability and input quality. This paper shows how decentralised coordination of a group of autonomous interdependent nodes can emerge with little communication, based on the robust self-organising principles of feedback. Positive feedback is used to reinforce the selection of the new desired global service solution, while negative feedback discourages nodes to act in a greedy fashion as this adversely impacts on the provided service levels at neighbouring nodes. The proposed protocol is general enough to be used in a wide range of scenarios characterised by a high degree of openness and dynamism where coordination tasks need to be time dependent. As the reported results demonstrate, it requires less messages to be exchanged and it is faster to achieve a globally acceptable near-optimal solution than other available approaches.

Using a prioritized medium access control protocol for incrementally obtaining an interpolation of sensor readings

This paper addresses sensor network applications which need to obtain an accurate image of physical phenomena and do so with a high sampling rate in both time and space. We present a fast and scalable approach for obtaining an approximate representation of all sensor readings at high sampling rate for quickly reacting to critical events in a physical environment. This approach is an improvement on previous work in that after the new approach has undergone a startup phase then the new approach can use a very small sampling period.

BANMAC: an opportunistic MAC protocol for reliable communications in body area networks

We consider reliable communications in Body Area Networks (BAN), where a set of nodes placed on human body are connected using wireless links. In order to keep the Specific Absorption Rate (SAR) as low as possible for health safety reasons, these networks operate in low transmit power regime, which however, is known to be error prone. It has been observed that the fluctuations of the Received Signal Strength (RSS) at the nodes of a BAN on a moving person show certain regularities and that the magnitude of these fluctuations are significant (5 - 20 dB). In this paper, we present BANMAC, a MAC protocol that monitors and predicts the channel fluctuations and schedules transmissions opportunistically when the RSS is likely to be higher. The MAC protocol is capable of providing differentiated service and resolves co-channel interference in the event of multiple co-located BANs in a vicinity. We report the design and implementation details of BANMAC integrated with the IEEE 802.15.4 protocol stack. We present experimental data which show that the packet loss rate (PLR) of BANMAC is significantly lower as compared to that of the IEEE 802.15.4 MAC. For comparable PLR, the power consumption of BANMAC is also significantly lower than that of the IEEE 802.15.4. For co-located networks, the convergence time to find a conflict-free channel allocation was approximately 1 s for the centralized coordination mechanism and was approximately 4 s for the distributed coordination mechanism.

Towards a flexible and dynamic replication control for distributed real-time embedded systems with QoS interdependencies

Replication is a proven concept for increasing the availability of distributed systems. However, actively replicating every software component in distributed embedded systems may not be a feasible approach. Not only the available resources are often limited, but also the imposed overhead could significantly degrade the system's performance. The paper proposes heuristics to dynamically determine which components to replicate based on their significance to the system as a whole, its consequent number of passive replicas, and where to place those replicas in the network. The results show that the proposed heuristics achieve a reasonably higher system's availability than static offline decisions when lower replication ratios are imposed due to resource or cost limitations. The paper introduces a novel approach to coordinate the activation of passive replicas in interdependent distributed environments. The proposed distributed coordination model reduces the complexity of the needed interactions among nodes and is faster to converge to a globally acceptable solution than a traditional centralised approach.

Estimating the number of nodes in wireless sensor networks

We propose an efficient algorithm to estimate the number of live computer nodes in a network. This algorithm is fully distributed, and has a time-complexity which is independent of the number of computer nodes. The algorithm is designed to take advantage of a medium access control (MAC) protocol which is prioritized; that is, if two or more messages on different nodes contend for the medium, then the node contending with the highest priority will win, and all nodes will know the priority of the winner.

A distributed algorithm for hexagonal topology formation in wireless sensor networks

Hexagonal wireless sensor network refers to a network topology where a subset of nodes have six peer neighbors. These nodes form a backbone for multi-hop communications. In a previous work, we proposed the use of hexagonal topology in wireless sensor networks and discussed its properties in relation to real-time (bounded latency) multi-hop communications in large-scale deployments. In that work, we did not consider the problem of hexagonal topology formation in practice - which is the subject of this research. In this paper, we present a decentralized algorithm that forms the hexagonal topology backbone in an arbitrary but sufficiently dense network deployment. We implemented a prototype of our algorithm in NesC for TinyOS based platforms. We present data from field tests of our implementation, collected using a deployment of fifty wireless sensor nodes.

A traffic differentiation add-on to the IEEE 802.15.4 protocol: implementation and experimental validation over a real-time operating system

The IEEE 802.15.4 is the most widespread used protocol for Wireless Sensor Networks (WSNs) and it is being used as a baseline for several higher layer protocols such as ZigBee, 6LoWPAN or WirelessHART. Its MAC (Medium Access Control) supports both contention-free (CFP, based on the reservation of guaranteed time-slots GTS) and contention based (CAP, ruled by CSMA/CA) access, when operating in beacon-enabled mode. Thus, it enables the differentiation between real-time and best-effort traffic. However, some WSN applications and higher layer protocols may strongly benefit from the possibility of supporting more traffic classes. This happens, for instance, for dense WSNs used in time-sensitive industrial applications. In this context, we propose to differentiate traffic classes within the CAP, enabling lower transmission delays and higher success probability to timecritical messages, such as for event detection, GTS reservation and network management. Building upon a previously proposed methodology (TRADIF), in this paper we outline its implementation and experimental validation over a real-time operating system. Importantly, TRADIF is fully backward compatible with the IEEE 802.15.4 standard, enabling to create different traffic classes just by tuning some MAC parameters.

WiDom: a dominance protocol for wireless medium access

In this paper, we address the problem of sharing a wireless channel among a set of sporadic message streams where a message stream issues transmission requests with real-time deadlines. We propose a collision-free wireless medium access control (MAC) protocol which implements static-priority scheduling, supports a large number of priority levels and is fully distributed. It is an adaptation to a wireless channel of the dominance protocol used in the CAN bus. But, unlike that protocol, our protocol does not require a node having the ability to receive an incoming bit from the channel while transmitting to the channel. The evaluation of the protocol with real embedded computing platforms is presented to show that the proposed protocol is in fact collision-free and prioritized. We measure the response times of our implementation and show that the response-time analysis developed for the protocol offers an upper bound on the response times.

H-NAMe: specifying, implementing and testing a hidden-node avoidance mechanism for wireless sensor networks

The hidden-node problem has been shown to be a major source of Quality-of-Service (QoS) degradation in Wireless Sensor Networks (WSNs) due to factors such as the limited communication range of sensor nodes, link asymmetry and the characteristics of the physical environment. In wireless contention-based Medium Access Control protocols, if two nodes that are not visible to each other transmit to a third node that is visible to the formers, there will be a collision – usually called hidden-node or blind collision. This problem greatly affects network throughput, energy-efficiency and message transfer delays, which might be particularly dramatic in large-scale WSNs. This technical report tackles the hidden-node problem in WSNs and proposes HNAMe, a simple yet efficient distributed mechanism to overcome it. H-NAMe relies on a grouping strategy that splits each cluster of a WSN into disjoint groups of non-hidden nodes and then scales to multiple clusters via a cluster grouping strategy that guarantees no transmission interference between overlapping clusters. We also show that the H-NAMe mechanism can be easily applied to the IEEE 802.15.4/ZigBee protocols with only minor add-ons and ensuring backward compatibility with the standard specifications. We demonstrate the feasibility of H-NAMe via an experimental test-bed, showing that it increases network throughput and transmission success probability up to twice the values obtained without H-NAMe. We believe that the results in this technical report will be quite useful in efficiently enabling IEEE 802.15.4/ZigBee as a WSN protocol.

Open-ZB: an open-source implementation of the IEEE 802.15.4/ZigBee protocol stack on TinyOS

The IEEE 802.15.4/ZigBee protocols are gaining increasing interests in both research and industrial communities as candidate technologies for Wireless Sensor Network (WSN) applications. In this paper, we present an open-source implementation of the IEEE 802.15.4/Zigbee protocol stack under the TinyOS operating system for the MICAz motes. This work has been driven by the need for an open-source implementation of the IEEE 802.15.4/ZigBee protocols, filling a gap between some newly released complex C implementations and black-box implementations from different manufacturers. In addition, we share our experience on the challenging problem that we have faced during the implementation of the protocol stack on the MICAz motes. We strongly believe that this open-source implementation will potentiate research works on the IEEE 802.15.4/Zigbee protocols allowing their demonstration and validation through experimentation.

Exploiting a prioritized MAC protocol to efficiently compute min and max in multihop networks

Consider a wireless sensor network (WSN) where a broadcast from a sensor node does not reach all sensor nodes in the network; such networks are often called multihop networks. Sensor nodes take sensor readings but individual sensor readings are not very important. It is important however to compute aggregated quantities of these sensor readings. The minimum and maximum of all sensor readings at an instant are often interesting because they indicate abnormal behavior, for example if the maximum temperature is very high then it may be that a fire has broken out. We propose an algorithm for computing the min or max of sensor reading in a multihop network. This algorithm has the particularly interesting property of having a time complexity that does not depend on the number of sensor nodes; only the network diameter and the range of the value domain of sensor readings matter.

A simulation model for the IEEE 802.15.4 protocol: delay/throughput evaluation of the GTS mechanism

The IEEE 802.15.4 protocol has the ability to support time-sensitive Wireless Sensor Network (WSN) applications due to the Guaranteed Time Slot (GTS) Medium Access Control mechanism. Recently, several analytical and simulation models of the IEEE 802.15.4 protocol have been proposed. Nevertheless, currently available simulation models for this protocol are both inaccurate and incomplete, and in particular they do not support the GTS mechanism. In this paper, we propose an accurate OPNET simulation model, with focus on the implementation of the GTS mechanism. The motivation that has driven this work is the validation of the Network Calculus based analytical model of the GTS mechanism that has been previously proposed and to compare the performance evaluation of the protocol as given by the two alternative approaches. Therefore, in this paper we contribute an accurate OPNET model for the IEEE 802.15.4 protocol. Additionally, and probably more importantly, based on the simulation model we propose a novel methodology to tune the protocol parameters such that a better performance of the protocol can be guaranteed, both concerning maximizing the throughput of the allocated GTS as well as concerning minimizing frame delay.

H-NAMe: a hidden-node avoidance mechanism for wireless sensor networks

The hidden-node problem has been shown to be a major source of Quality-of-Service (QoS) degradation in Wireless Sensor Networks (WSNs) due to factors such as the limited communication range of sensor nodes, link asymmetry and the characteristics of the physical environment. In wireless contention-based Medium Access Control protocols, if two nodes that are not visible to each other transmit to a third node that is visible to the formers, there will be a collision – usually called hidden-node or blind collision. This problem greatly affects network throughput, energy-efficiency and message transfer delays, which might be particularly dramatic in large-scale WSNs. This paper tackles the hiddennode problem in WSNs and proposes H-NAMe, a simple yet efficient distributed mechanism to overcome it. H-NAMe relies on a grouping strategy that splits each cluster of a WSN into disjoint groups of non-hidden nodes and then scales to multiple clusters via a cluster grouping strategy that guarantees no transmission interference between overlapping clusters. We also show that the H-NAMe mechanism can be easily applied to the IEEE 802.15.4/ZigBee protocols with only minor add-ons and ensuring backward compatibility with the standard specifications. We demonstrate the feasibility of H-NAMe via an experimental test-bed, showing that it increases network throughput and transmission success probability up to twice the values obtained without H-NAMe. We believe that the results in this paper will be quite useful in efficiently enabling IEEE 802.15.4/ZigBee as a WSN protocol

IEEE 802.15.4: a Federating Communication Protocol for Time-Sensitive Wireless Sensor Networks

Wireless Sensor Networks (WSNs) have been attracting increasing interests for developing a new generation of embedded systems with great potential for many applications such as surveillance, environment monitoring, emergency medical response and home automation. However, the communication paradigms in WSNs differ from the ones attributed to traditional wireless networks, triggering the need for new communication protocols. In this context, the recently standardised IEEE 802.15.4 protocol presents some potentially interesting features for deployment in wireless sensor network applications, such as power-efficiency, timeliness guarantees and scalability. Nevertheless, when addressing WSN applications with (soft/hard) timing requirements some inherent paradoxes emerge, such as power-efficiency versus timeliness, triggering the need of engineering solutions for an efficient deployment of IEEE 802.15.4 in WSNs. In this technical report, we will explore the most relevant characteristics of the IEEE 802.15.4 protocol for wireless sensor networks and present the most important challenges regarding time-sensitive WSN applications. We also provide some timing performance and analysis of the IEEE 802.15.4 that unveil some directions for resolving the previously mentioned paradoxes.

Using a prioritized MAC protocol to efficiently compute aggregated quantities

Consider a distributed computer system such that every computer node can perform a wireless broadcast and when it does so, all other nodes receive this message. The computer nodes take sensor readings but individual sensor readings are not very important. It is important however to compute the aggregated quantities of these sensor readings. We show that a prioritized medium access control (MAC) protocol for wireless broadcast can compute simple aggregated quantities in a single transaction, and more complex quantities with many (but still a small number of) transactions. This leads to significant improvements in the time-complexity and as a consequence also similar reduction in energy “consumption”.