Networking communications play an important role to secure a dependable and timely operation of distributed and real-time embedded system applications; however, an e ective real-time support is not yet properly addressed in the wireless realm. This paper presents Wi-STARK, a novel architecture for resilient and real-time wireless communications within an one-hop communication domain. Low level reliable (frame) communications, node failure detection, membership management, and networking partition control are provided; since these low level services extend and build upon the exposed interface o ered by networking technologies, Wi-STARK is in strict compliance with wireless communication standards, such as IEEE 802.15.4 and IEEE 802.11p. The Wi-STARK service interface is then o ered as operating system primitives, helpful for building distributed control applications. The one-hop dependability and timeliness guarantees o ered by Wi-STARK are a fundamental step towards an e ective design of real-time wireless networks with multiple hops, including end-to-end schedulability analysis of networking operations.
This work was partially supported by the EC, through project IST-FP7-STREP-288195 (KARYON); by FCT/DAAD, through the transnational cooperation project PROPHECY; and by FCT, through project PTDC/EEI-SCR/3200/2012 (READAPT) and through LaSIGE Strategic Project PEst-OE/EEI/UI0408/2014.
Advances in microelectronics enable the development and integration of networking computing systems in environments with di erent levels of criticality, monitoring and controlling physical entities such as nuclear reactors, physical structure of buildings and bridges, and power grids. In these kind of environments, usually known as Cyber Physical Systems (CPS), communications may have safety-critical constrains, implying a mandatory provision of real-time communication guarantees to secure the dependable and timely operation of the entire system.
The literature addressing real-time support on the wireless realm can be classi ed into two distinct domains: (a) communication protocols and architectures, and (b) schedulability analysis.
The contributions to real-time communication protocols and
architectures, such as [
The schedulability analysis of wireless networking
communications [
Conjugating dependability and real-time message delivery guarantees with wireless communications is a di cult problem. Instead of following the classic approach described in the wireless communication literature, and trying to establish those guarantees end-to-end |using a traditional pointto-point communication model |we take a divide to conquer approach, which is motivated by the following statement: If no real-time guarantees can be o ered within communications at one-hop of distance, no real-time guarantees can be o ered within multiple hop communications at all.
That means, any dependable real-time message delivery guarantee has to be secured rst within the one-hop of distance wireless space, prior to be extended end-to-end, across multiple hops. Thus, this paper presents a design overview of a novel wireless communications architecture dubbed Wi-STARK, which has three main goals: (1) taking advantage of the intrinsic broadcast properties of the shared wireless communication medium within one-hop space, (2) providing dependability and real-time guarantees within such one-hop space, and (3) ensuring the feasibility of end-to-end schedulability analysis given the bounded transmission delay guarantees within each single hop. The Wi-STARK design is compliant with wireless communications standards, being able to o er at the lowest level of communications a set of useful and semantically rich services such as reliable and timely communications, node failure detection, membership management, and networking partition control. Since these services are built upon the exposed interface o ered by current networking technologies, the Wi-STARK architecture can be easily implemented using Commercial O -The-Shelf (COTS) components. The Wi-STARK service interface can easily be made available at the operating system Application Programming Interface (API).
To present the details concerning the design of the Wi-STARK architecture, this paper is organised as follows: section 2 presents a brief description of the system model, which is the foundation for the design of the Wi-STARK architecture; section 3 presents the main components and characteristics of the Wi-STARK architecture; section 4 presents the primitives and semantics of the Wi-STARK service interface; and nally, section 5 presents the conclusion and future directions of the design and applicability of the Wi-STARK architecture.
All networking communications described in this paper are performed within the scope of a physical and data link layer abstract networking model dubbed Wireless network Segment (WnS), which establishes a broadcast domain where all wireless nodes are one-hop of distance from one another. This simple approach empowers the achievement of a rst and fundamental result: the capability of exploiting the broadcast nature of the shared one-hop communication space. The formalisation of the WnS is expressed by a 4-Tuple, def W nS = hX; xm; C; W i, where X is the set of wireless nodes members of the WnS; xm is the WnS coordinator, xm 2 X; C represents a set of radio frequency (RF) communication channels; and W represents the set of networking access protocols utilised in the support of frame transmissions. As illustrated in the graphical representation of Fig. 1, the intersection of the communication range of all nodes within the WnS constitutes its broadcast domain, where each node xj 2 X is able to sense any transmission from any other node xq 2 X.
The failure of a networking component (a channel c 2 C or a node x 2 X) is identi ed using an omission fault model, where frame errors are transformed into omissions. The occurrence of frame errors may be originated by disturbances caused by the presence of electromagnetic interferences on the communication channel, or malfunction within the node machinery, being accounted as omissions for the purpose of monitoring networking components.
For each received frame, each node x 2 X locally accounts observed omissions. When the number of observed omissions exceeds the component's omission degree bound, fo, the failure of such component can be locally signed. Errors occurred at the wireless communication medium may a ect only some nodes, which implies omissions may be accounted inconsistently at the di erent nodes of the WnS. Both omissions with origin in the channel and at the channel end-points (i.e., the nodes) are accounted for. When successive frames are received with errors from a given channel input | i.e. a node x 2 X | exceeding a given omission degree bound, a node persistent failure is detected and signalled; when no tra c is received from node x 2 X within a bounded monitoring time interval, a node crash failure is detected and signalled.
Each node x 2 X may also inconsistently experience a
temporary loss of connectivity with the WnS, caused by a
phenomenon dubbed network inaccessibility [
Mobility may drive nodes to outside of the WnS, as illustrated in Fig. 1, where node x2 using channel c moves from the geographic position P (x2) to the geographic position P 0(x2). In despite of x2 transmissions at the new position may reach all nodes of the WnS, the transmissions from the WnS coordinator, xm 2 X, do not reach node x2 at position P 0(x2). The permanent mobility of a node to outside of the WnS broadcast domain is then transformed into a node crash failure in our fault model.
Communications at the lowest levels of the networking protocol stack can be abstracted by a set of correctness, dependability, and timeliness properties, which are not dependent on any particular networking technology. In the context of the WnS model such properties are seen as being provided by a single abstract communication channel dubbed WnS abstract channel, as illustrated in Fig. 2.
Property WnS1 (Broadcast ) formalises that it is physically
impossible for a node x 2 X to send con icting
information (in the same broadcast) to di erent nodes, within the
broadcast domain of the WnS [
Property WnS2 (Frame Order ) is common in network
technologies (wireless technologies included), being imposed by
the wireless communication medium of each channel c 2 C,
and resulting directly from the serialisation of frame
transmissions on the shared wireless communication medium.
Property WnS3 (Error Detection) has both detection and
signalling facets; the detection facet, traditionally provided
by classical MAC sublayers, derives directly from frame
protection through a frame check sequence (FCS) mechanism,
which most utilised algorithm is the cyclic redundancy check
(CRC); the signalling facet is provided by the FCS
extension introduced in [
Property WnS4 (Bounded Omission Degree) formalises for
a channel, c 2 C, the failure semantics introduced earlier in
the fault model de nition, being the abstract channel
omission degree bound, k fo. The omission degree of a WnS
abstract channel can be bounded, given the error
characteristics of its wireless transmission medium [
The time domain behaviour of a WnS is described by the
remaining properties. Property WnS6 (Bounded Transmission
Delay) speci es a maximum frame transmission delay, which
is Ttd in the absence of faults. The value of Ttd includes the
medium access and transmission delays and it depends on
message latency class and overall o ered load bounds [
The Wi-STARK is a new low level architecture that takes advantage of the intrinsic broadcast property of the shared wireless communication medium, and of the set of correctness, ordering, dependability, and timeliness properties offered by the WnS abstraction (Section 2.2) to establish a robust, resilient and real-time one-hop communication domain for wireless networks.
The Wi-STARK architecture design is open and exible, being composed by two layers dubbed Channel Layer and Mediator Layer. As shown in Fig. 3, these layers are by design wrapping the standard MAC sublayer to improve: the control and use of RF communication channels; and, the services o ered to high level protocol layers.
The Channel Layer (Fig. 4) is a thin layer that provides a common interface to transparently control the use of a given RF communication channel c 2 C for purposes of frame transmission and reception, incorporating useful extensions to enhance the dependability of communications. A RF communication channel c 2 C is an abstract representation of the wireless transmission medium plus a piece of hardware dubbed RF transceiver, which conjugates a residual part of the MAC sublayer, herein called, basicMAC and the physical (PHY) layer itself.
The Channel Layer extends the basicMAC to exploit the
exposed RF transceiver interface, and the parametrisation
features thereof. In particular, the Channel Layer
implements: the FCS extension (speci ed in [
The MAC sublayer illustrated in Fig. 3 is the standard MAC
sublayer present in the traditional wireless networking
protocol stack, such as those speci ed within the IEEE 802.15.4 [
The Mediator Layer is an extensible sublayer, specially designed to mediate the communication ow from (and to) the high level protocol layers, as illustrated in Fig. 3. The Mediator Layer is responsible for the semantically rich service interface o ered by Wi-STARK, e ectively augmenting the services o ered by the standard MAC sublayer. Three main components compose the Mediator Layer : the Real-Time Communication Suite, the Timeliness & Partition Control, and the Networking & Management Control.
The Real-Time Communication Suite (RTCS) is the component responsible for the data communication services o ered by the Wi-STARK architecture, as illustrated in Fig. 5. The RTCS includes a Message Request Dispatcher that forwards any high level message transmit request to the adequate instance of the RTCS protocol bundle. Messages submitted at the Wi-STARK service interface have a maximum length for allowing the encapsulation of their content in exactly one frame, without necessity of fragmentation.
The table of Fig. 5 speci es the fundamental properties (recipients, ordering, and reliability) characterising the di erent variants of the protocols to be included in the RTCS protocol bundle. For example: a totally ordered reliable message delivery targeting all correct nodes features the well known atomic broadcast primitive. This speci cation is open and extensible: other attributes (e.g., temporal order ) and other properties (e.g., urgency) can be included. The Wi-STARK architecture design provides two fundamental guarantees to the high level protocol layers and applications: Temporal-bounded communications: every transmitted message1 is successfully received by all relevant correct nodes of the WnS within a known temporal bound, TT x Data. The value of TT x Data is directly derived from the combination of four important properties of the WnS: WnS3 (Error Detection), WnS4 (Bounded Omission Degree), WnS5 (Bounded Inaccessibility ), and WnS6 (Bounded Transmission Delay). In the absence of errors, the Wi-STARK protocols execute in a single round and the upper bound for all correct nodes of the WnS receiving a message successfully is: TTwxc Dnaeta = 2:Ttd; being Ttd the maximum frame transmission delay in the absence of errors. 1A message is a high level protocol layer data service unit.
Real-Time Communication Suite Recipients
Multiple nodes (Multicast); Property Ordering Reliability
Attributes Single node (Unicast);
All nodes (Broadcast) Unordered; Totally ordered
Unreliable; Reliable
In the presence of errors, frames2 may have to be
retransmitted and the protocols within the Wi-STARK architecture
may require more than one round to be executed, up to a
limit given by k + i + 1 (as speci ed by properties WnS4 and
WnS5); all relevant correct nodes can successfully receive
any message transmitted with any reliable
communication protocol provided by the Wi-STARK architecture
in, at most, TTwxc Data = (k + i + 1) (2:Ttd) + Tina. The
timer utilised by reliable protocols to control protocol
execution is con gured with its optimal value (i.e., Ttd), and
extended (if needed) by the real value of the network
inaccessibility, tina, adding up to at most Tina [
A failure of the RF communication channel in use is detected by the violation of k, the channel omission degree bound (WnS4), being the Wi-STARK architecture able to switch to another channel to keep the networking communications operational; the duration of the \communication blackout" resultant from that channel failure is then incorporated in the network inaccessibility model through Tina.
Message delivery : every transmitted message is delivered to all relevant correct nodes of the WnS.
Message delivery guarantees emerge from reliable communication protocols of the Wi-STARK architecture, which exploit the nature of the shared wireless communication medium (properties WnS1 and WnS2) to o er totally ordered delivery guarantees. 2A frame is the MAC sublayer protocol data unit.
The Timeliness & Partition Control (TPC) presents the transversal components that deals with the temporal aspects of the service o ered by the Wi-STARK architecture. As shown in Fig. 6, the TPC component incorporates Time Services that include the management of protocol timers and other services used in the temporal control of Wi-STARK components.
The Partition Handler is focused to detect the occurrence,
and to be aware of any partitioning incidents caused by the
presence of periods of network inaccessibility. Controlling
networking inaccessibility allows the use of optimal timeout
values, which are automatically extended [
The Networking & Management Control component (illustrated in Fig. 7) incorporates all the functionalities of the Mediator Layer responsible for managing the dependable operation of each node x 2 X. The management responsibilities assigned to the Mediator Layer include controlling all internal con guration of the Wi-STARK architecture, the parameters of the MAC sublayer (basicMAC and serviceMAC included), and the provision of management services to support the WnS formation.
All con gurations can be performed statically or dynamically. The static con guration is target for hard real-time environments where all analyses of the tra c pattern, error conditions, and mobility models are performed o ine, being stored in the Wi-STARK Information Base (Fig. 7). The Mediator Layer (self-)adaptation and dynamic con guration capabilities are related with mixed-critical and soft real-time requirements, which are outside the scope of this paper.
The membership and node failure detection o ered by the Mediator Layer were designed to control and establish a consistent view of all members of the WnS, which is represented by the abstract set, X.
In the perspective of networking protocol developers, the dependability and timeliness guarantees o ered by the Wi-STARK architecture are represented by a set of fundamental primitives for transmission and reception of messages to/from the network, which are speci ed in Table 1. All of the primitives present in the Wi-STARK data service
Wi-STARK data service interface
Primitives MLA.Data.request MLA.Data.con rm
Description Requests a message transmission using one of the Wi-STARK communication protocols.
For reliable services, it con rms message delivery at recipients. Otherwise, it con rms only message transmission.
MLA.Data.indication Noti es the arrival of a message. interface are easily integrated into embedded and real-time operating systems, being available as system calls associated to the wireless networking protocol stack.
This paper presented the architectural design of Wi-STARK, a novel low level architecture for resilient and real-time onehop wireless communications. The de nition of Wi-STARK is based on the establishment of an abstract communication model dubbed Wireless network Segment (WnS), which o er a set of correctness, dependability, and timeliness properties to support the design of resilient communication services for wireless networks.
Wi-STARK is compliant with wireless standards such as IEEE 802.15.4 and IEEE 802.11p, being capable to o er support for low level reliable message communication, node failure detection and membership, and networking partition control. Future directions involves the incorporation of the Wi-STARK service interface in the API of embedded realtime operating systems, and the extension of one-hop guarantees for multi-hop networking scenarios.