Transmission scheduling for mixed-critical multi-user multiple-input and multiple-output industrial cyber-physical systems

Abstract

Wireless sensor networks are widely used in industrial cyber-physical system installations, where high reliability and the need for real-time data are the two main characteristics. A large amount of real-time data can be transmitted to its destination on time using a reasonable periodic allocation of a node’s transmission slots. However, a flow may miss its deadline when flow conflicts occur. When such missed deadlines occur regularly, system performance may degrade, and when the flow is critical, such data losses can result in errors or cause disasters. To address this issue, we introduce multi-user multiple-input and multiple-output technology and a mixed-critical system into an industrial cyber-physical system. When an error occurs or when demand changes, the multi-user multiple-input and multiple-output nodes can switch their transmission mode, changing to a high-criticality configuration to meet the system’s new needs. Hence, we first propose a heterogeneous multi-user multiple-input and multiple-output system model. Based on this model, we propose a slot analyzing algorithm that guarantees system schedulability by reallocating slots for each node after replacing conflict nodes with multi-user multiple-input and multiple-output nodes. By considering both system schedulability and cost, the slot analyzing algorithm also reduces the number of multi-user multiple-input and multiple-output nodes required. Then, to further reduce the number of multi-user multiple-input and multiple-output nodes in an industrial cyber-physical system, we propose a priority inversion algorithm that improves schedulability by adjusting slot allocations before replacing conflict nodes with multi-user multiple-input and multiple-output nodes. By reducing the use of multi-user multiple-input and multiple-output nodes, the priority inversion algorithm achieves better performance than the slot analyzing algorithm when the system is in a high-criticality mode. Evaluation results show the effectiveness and efficacy of our approaches.

Keywords

Cyber-physical system mix-critical multi-user multiple-input and multiple-output industrial networks scheduling

Introduction

Industrial cyber-physical systems (ICPSs) are emerging as the fourth industrial revolution for industrial system.^1–3 Compared to a conventional process control system, an ICPS mainly focused on system costs and reliability.^4,5 Based on the features of ICPS, industrial standards are used extensively, such as ISA100,⁶ WirelessHART,⁷ and WIA-PA.⁸

High degree of reliability and real-time communication requirements are two primary indicators in industrial network, and traditional cyber-physical systems (CPSs) cannot be applied directly. Instead, transmission slots and channels must be allocated for each node before the system works. Numerous studies have focused on this issue and attempted to improve the schedulability of ICPSs.^9,10 However, the current scheduling methods cannot always guarantee the schedulability of an ICPS; for example, when several flows conflict at one node, lower-priority flows may miss their deadlines.

To ensure the schedulability of ICPSs, we introduce multi-user multiple-input and multiple-output (MU-MIMO) technology into ICPSs. A MU-MIMO node with two antennas can both receive and send packets simultaneously.^11–13 By replacing conflict nodes with MU-MIMO nodes, several flows can transmit without delays. If we were to replace all the conflict nodes with MU-MIMO nodes, that would eliminate transmission conflicts in the system; consequently, when the number of MU-MIMO nodes is sufficient, we can guarantee system schedulability. However, considering the energy consumption and cost of MU-MIMO nodes, it is advantageous to be able to guarantee ICPS schedulability using fewer MU-MIMO nodes.¹⁴

Furthermore, we must also consider schedulability when an error occurs or system demands change (usually, one ICPS involves several demands). Therefore, we introduce a mixed-critical system into ICPSs to address this issue.^15–17 The existing works mainly consider the systems with single criticality, and these systems only reflect important by their priority. However, in many situations, the priority cannot represent importance. For example, as shown in Figure 1, the cement production process requires capturing temperature and detecting excessive pressure. The nodes in this system communicate through wireless mesh network. For tasks such as measuring temperature, which has a low criticality but high priority, only a general quality certification is required. In contrast, tasks such as excessive pressure detection require a strict safety certification (excessive steam pressure may cause boiler explosions); however, such pressure measurements have a lower priority than temperature measurements. When an accident or unusually sensor date occurs, we must improve schedulability of flows in high-criticality mode. Hence, we need to consider both the characters of priority and criticality to guarantee the ICPS schedulability. Therefore, it is necessary to introduce a mixed-criticality concept into ICPSs and analyze system schedulability under different criticality modes. Here, we assume that there are two criticality modes (low and high).

Figure 1.

An example of a mixed-critical system.

There are two main challenges in our work: (1) reducing the number of MU-MIMO nodes required to guarantee the schedulability of an ICPS and (2) analyzing the schedulability of our algorithms for ICPSs in different criticality modes. To solve these problems, we propose two algorithms, a slot analyzing algorithm (SAA) and a priority inversion algorithm (PIA), to improve ICPS schedulability. The SAA first allocates slots without considering transmission conflicts and replaces conflict nodes with MU-MIMO nodes to guarantee future schedulability in low-criticality mode. In contrast, the PIA first optimizes slots allocation to reduce the number of transmission conflicts; then, we replace conflict nodes with MU-MIMO nodes only when the system cannot be scheduled. This study makes the following key contributions:

To the best of our knowledge, this is the first study to solve the transmission conflict problem in ICPSs using MU-MIMO technology.

We first propose an algorithm to obtain the candidate node set (CNSA) and then propose the SAA to improve system schedulability. The SAA can guarantee that a system can be scheduled when it satisfies Theorem 1. Furthermore, the SAA also reduces the number of MU-MIMO nodes in a candidate node set through slot analysis.

We propose the PIA to reduce the number of transmission conflicts before replacing the overlap nodes with MU-MIMO nodes. When a flow cannot be scheduled, priority inversion occurs when it satisfies Theorem 3.

We analyze system schedulability in high-criticality mode and prove that the PIA achieves better schedulability than SAA in Theorem 4.

Simulation results show that our algorithms can guarantee the schedulability of an ICPS with MU-MIMO nodes and that the PIA achieves a better performance than the SAA in high-criticality mode.

The rest of the article is organized as follows. Section “Related works” reviews previous works. Section “System model” presents the system model, which includes a network model, a mixed-critical system, and a fixed-priority (FP) scheduling policy in an ICPS. Section “Problem statement” states the problem, and we present our methods and describe the analysis in section “Scheduling algorithms.” Finally, section “Experiments” provides performance evaluation results, and section “Conclusion” concludes the article.

Related works

The first real-time transmission scheduling in ICPSs was studied in Saifullah et al.¹⁸ This approach first formulated the end-to-end real-time transmission scheduling problem based on the characteristics of WirelessHART networks; then, the authors proved that the problem is NP-hard. Finally, they proposed several scheduling algorithms. Based on this study, Saifullah et al.⁹ and Wu et al.¹⁰ analyzed the end-to-end delay of WirelessHART networks. The schedulability of mixed-criticality industrial networks was analyzed in Xia et al.¹⁹ In addition, Zheng et al.²⁰ proposed a new network model aiming at improving user experience by pushing the scheduling problem to the task layer; the work in Cheng et al.⁵ improves the performance of wireless sensor network (WSN) by extracting kernel dateset form big sensory date. However, all these studies are based on traditional nodes. The sensor nodes in these networks can receive or send only one packet at a time in a single time slot.

In Kong and Liu,²¹ the authors proposed an m-zig technique to improve the performance of sensor node. Based on m-zig, a sensor node can receive several packets during a single time slot. Later, a prototype of Cross-Zig was implemented for the low-power IEEE 802.15.4 specification in a software-defined radio platform.²² L Cheng et al.²³ proposed an incast-collision-free data collection protocol named i-Core to address the many-to-one collision problem in low-duty-cycle WSNs. However, m-zig cannot both receive and send several packets at the same time.

The feasibility of employing MIMO techniques in WSNs was envisioned in Yuan et al.²⁴ To reduce the transmission time for mobile data collection,²⁵ the concept of incorporating MU-MIMO nodes into WSNs is introduced. However, only a few studies have focused on applying MU-MIMO technology to WSNs. Our research, therefore, addresses the schedulability of ICPSs using MU-MIMO technology.

Mixed-criticality systems have led to new research direction for real-time ICPSs. S Vestal²⁶ first proposed the concept of mixed criticality and then mixed criticality rapidly becoming a significant concept in CPSs.^27–31 However, these works have mainly focused on Sandy Bridge, which is a kind of intel microprocessor architecture. For communication media, only a few related works on mixed criticality. X Jin et al.³² studied real-time communication in industrial networks by mixed criticality. Xia et al.¹⁹ proposed a resource analysis method based on an earliest deadline first (EDF) scheduling approach. However, all these existing works on mixed-criticality systems were performed using traditional CPSs; consequently, ICPSs may not be scheduled. Thus, existing solutions cannot be used in our model. Instead, there is an urgent need to propose scheduling methods under MU-MIMO for ICPSs to solve this issue.

System model

We consider a heterogeneous ICPS consisting of field devices (both MU-MIMO sensor nodes and traditional sensor nodes), one centralized controller and one gateway. Our system includes three aspects. First, we propose a network model and then we introduce MU-MIMO technology and mixed-criticality system into ICPSs. Finally, we derive FP scheduling scheme in ICPS.

Network model

In this subsection, we propose our system model based on ISA100 and WIA-PA. There are several features as follows: (1) limiting network size, (2) time division multiple access (TDMA), (3) route and spectrum diversity, and (4) handling internal interference.³³ The number of channels is denoted as $m$ , and there are $N$ fixed nodes in our system.

Industrial systems are a form of CPS applications that have higher requirements of real-time performance and reliability. Here, we introduce the MU-MIMO technique into ICPS. MU-MIMO nodes are promising for wireless transmissions because they can improve the average user spectral efficiency.³⁴ By mounting multiple antennas on a single sensor node, the node can receive and transmit simultaneously (or improve the packet acceptance ratio when all the antennas work on the same channel). The feasibility of employing MU-MIMO technology in ICPSs was envisioned in Zhao et al.²⁵

Hence, our model includes two types of sensor nodes: ordinary nodes and MU-MIMO nodes. Each ordinary node in our system is equipped with a half-duplex omni-directional radio transceiver whose status can alternate between transmitting and receiving. In contrast, a MU-MIMO node has two working modes: (1) when the antennas work on different channels, the node can both receive and transmit packets from several paths (the transmission capacity of a MU-MIMO node depends on the number of antennas it has); and (2) when the antennas work on the same channel, the node can reduce signal interference and improve the acceptance ratio because several antennas receive a packet from the same flow. Each packet in our system is transmitted through the network under source routing.

Figure 2 shows an example of a MU-MIMO node in the first mode (where antennas work on different channels) to address a transmission conflict in which $F_{1}$ and $F_{2}$ send packets to the same destination simultaneously. We introduce MU-MIMO to solve this issue. The flows can be scheduled by replacing $V 3$ with a MU-MIMO node. MU-MIMO nodes can also be used as a method to increase the packet acceptance ratio when two or several antennas receive packets on the same channel. For the second mode of a MU-MIMO node (where the antennas work on the same channel), when the links around $V 3$ have poor signal quality (such as from co-channel interference, intermodulation interference, spurious emissions, or adjacent-channel interference), node $V 3$ can switch its antenna receiving frequencies to the same channel to improve the acceptance ratio. However, considering that the power consumption and cost of MU-MIMO nodes is considerably higher than the cost of a normal node, we cannot deploy MU-MIMO nodes throughout the entire system.

Figure 2.

An example of MU-MIMO with a node handling a transmission conflict.

Mixed-critical system

The flow is a periodic end-to-end communication between a source and its destination. There are $n$ flows in our system, denoted by $F = {F_{1}, F_{2}, \dots, F_{n}}$ . $F_{i}$ is characterized by $< t_{i}, d_{i}, ξ, c_{i}, p_{i} >$ , a number between $1 \leq i \leq n$ , where the period is $t_{i}$ , the deadline is $d_{i}$ , the criticality level is $ξ$ (we focus on a dual-criticality system ${LO, HI}$ ) in which $ξ = 2$ , meaning the system has two critical levels. The superframe as the lowest common multiple of the flow periods is denoted as T. Initially, the system works at a low critical level, and the MU-MIMO nodes receive packets on different channels. The system switches to the high-critical level to enhance system reliability, and the MU-MIMO nodes reconfigure their antennas to receive high-critical flow packets on the same channels when accident occurs. Here, $c_{i}$ is the number of hops requirement from a source to a destination, and the routing path is $p_{i}$ . When the system critical level switches from low to high, the MU-MIMO node’s work pattern changes from receiving on different channels to receiving on the same channels to improve the schedulability of high-critical flows. In addition, the characteristics of high-criticality flows switch to high-criticality mode. In this article, the system reduces the sampling period of a high-criticality flow to $ℵ_{i} t_{i}$ to improve the sampling rate of high-critical flow, where $ℵ_{i}$ is a value that satisfies $(c_{i} / t_{i}) \leq ℵ_{i} < 1$ . To simplify the calculation we assume that $d_{i} = t_{i}$ . Hence, $ℵ_{i}$ satisfies $(c_{i} / d_{i}) \leq ℵ_{i} < 1$ . The details of the mode switch are outside the scope of this article. Therefore, we only model the duration of the mode switch as $γ$ , which is used to calculate the delay of packets delivered during the mode change.

At the beginning, packets are transmitted in low critical mode. To provide more resources, each MU-MIMO node’s antennas work on different channels. The system switches when accident occurs. To enhance system reliability in high-criticality mode, each MU-MIMO node’s antennas are reconfigured to work on the same channel.

FP scheduling in ICPS

We provide a summarization of FP scheduling under ICPS to analyze the schedulability of system in this subsection. FP scheduling is a commonly adopted scheme in practice for CPSs and real-time CPU scheduling.³⁵ Each job priority is pre-allocated by the network controller, and transmissions are scheduled based on this priority.

We assume that the priority of each flow is the same as its number. That is, $F_{1}$ has the highest priority and $F_{n}$ has the lowest priority in the system. There are two types of delays in industrial wireless sensor systems: (1) channel contention and (2) transmission conflicts, and the definitions can be obtained in Saifullah et al.¹⁹

We define a system as schedulable when all the flows in a system can be scheduled (reach the destination before its deadline). Then, the definition of network schedulability is whether or not all flows in a network are schedulable. It is worth noting that when the system is in high-criticality mode, we no longer focus on the schedulability of low-criticality flows. When we repeat Z experiments, and only z experiments the emergency flow can be scheduled, then, the schedulability ratio is $z / Z$ .

Problem statement

Given the flow set $F$ , a wireless ICPS, and the FP scheduling policy, our objective is to improve the schedulability of mixed-critical ICPS in MU-MIMO industrial networks. We first analyze the schedulability of mixed-critical ICPSs. Initially, the system is working in low-criticality mode. To improve system schedulability, we introduce MU-MIMO technology to provide more resources (the resources such as slots and channels are increased since MU-MIMO nodes can receive and send packets simultaneously). Hence, we replace nodes at several intersections with MU-MIMO nodes and propose a PIA to guarantee that the system can be scheduled. However, when accident occurs, we must guarantee high-criticality flows schedulability; consequently, the system switches to high-criticality mode and the transmission mode of MU-MIMO node changes. We then analyzed the schedulability of our method to evaluate the quality of the PIA. The challenges in this situation are listed below:

When the system is deployed, we can easily determine flows that miss their deadlines. However, each flow’s schedulability is interrelated with others. Thus, how should we decide which nodes should be replaced with MU-MIMO nodes?

As described in the previous section, the power consumption and cost of a MU-MIMO node are much higher than those of a normal node. Therefore, it is unreasonable and not cost-effective to deploy many MU-MIMO nodes when the system can be scheduled. Hence, the problem of determining the smallest number of MU-MIMO nodes that can meet the system requirements in low-criticality mode is another challenge.

The MU-MIMO nodes’ transmission mode changes when the system switches to high-criticality mode. Therefore, the scheduling algorithm also needs to consider schedulability in high-criticality mode.

We need to analyze the system’s schedulability under our proposed method.

Scheduling algorithms

In this section, we first study the issue of how to improve system schedulability with a small number of MU-MIMO nodes. First, we identify the nodes that may be replaced with MU-MIMO nodes to define candidate nodes as follows.

Definition 1 (Candidate Node)

We define a candidate node as a node at which transmission conflicts (intersection or overlap nodes) can occur. As Figure 2 shows, the paths of $F_{1}$ and $F_{2}$ intersect at $V 3$ ; consequently, a transmission conflict may occur at this node. Thus, $V 3$ is a candidate node.

Flows may conflict when they have path overlaps. To facilitate candidate node identification, we assume that, at most, one part of a path overlaps between two flows. As Figure 3 shows, two periodic flows transmit in an ICPS that conflict at the second and third slots in the first period. There are two methods for addressing transmission conflicts. The first method is to reallocate the slots for each node after replacing the conflict nodes with MU-MIMO nodes (as Figure 3 shows, the system can be scheduled when we replace node $V 5$ with a MU-MIMO node, where CH is the abbreviation of Channel); the other method is to adjust slot allocation, as shown in Figure 4. By rationally allocating each flow’s transmission slots, we can reduce the number of MU-MIMO nodes and the signal interference caused by coexistence of multiple channels, which can also improve the schedulability when the ICPS is in high-criticality mode. However, this is unsuitable for a system which cannot be scheduled (in this example, the system cannot be scheduled if the deadline of $F_{i}$ is $4$ ).

Figure 3.

The analysis of conflicts.

Figure 4.

An example for un-schedulable conflict.

Therefore, for a system in which each link’s transmission slot has been allocated, we propose the SAA to improve system schedulability under a traditional FP policy. When the system cannot be scheduled by MU-MIMO nodes, the SAA reallocates system resources to guarantee system schedulability (increase the transmission speed of unscheduled data flows). By considering the characteristics of mixed-critical systems and MU-MIMO nodes, we then propose the PIA algorithm, which adjusts slot allocations before replacing intersection nodes with MU-MIMO nodes (the second method to address transmission conflict). By optimizing slots allocation, PIA can guarantee system schedulability with fewer MU-MIMO nodes. To guarantee the schedulability of the ICPS, PIA will also reallocate slots when the system cannot be scheduled. It is important to note that initially both the SAA and PIA algorithms work in low-criticality mode. We will analyze the schedulability of these two algorithms later.

Finding candidate nodes

An ICPS consists of numerous sensor nodes. In this subsection, we study how to select candidate nodes to guarantee the system can be scheduled. Transmission conflicts occur at the path overlaps of flows. As Figure 5 shows, there are two types of overlaps (without considering the flow’s direction).

Figure 5.

Transmission conflict.

Lemma 1

When flow paths have an overlapping region, the overlap nodes are candidates for MU-MIMO nodes. We denote the candidate node set as $Λ$ , and the node set on each flow’s path can be denoted as $λ_{i}$ .

Proof

Transmission conflict can obviously only occur at an overlapping region. We can solve this issue by MU-MIMO nodes. We can account for the conflicts caused by the first type as shown in Figure 2. For the transmission conflict caused by the second type, as shown in Figure 5, there are two nodes ( $V 1$ and $V 2$ ) on both $F_{1}$ and $F_{2}$ involved in the second type of overlap. When this type of transmission conflict occurs, we can improve the schedulability by replacing both $V 1$ and $V 2$ with MU-MIMO nodes. Hence, when flow paths have an overlapping region, the overlap nodes are candidates for MU-MIMO nodes.

Hence, we propose a Candidate Node Searching Algorithm (CNSA) to search for the set of candidate node as follows.

Algorithm 1 Candidate node searching algorithm
Require:F; Ensure: the candidate node set $Λ = {λ_{i}}$ , $i \in F$ ; 1: for each flow $F_{i}$ do 2: if node $n_{k}$ is the overlap node then 3: $n_{k}$ join $Λ$ ; 4: end if 5: end for 6: return $Λ$ ;

We search the candidate nodes by traversing the flow paths of the entire system. Nodes on more than one flow path are added to the candidate node set $Λ$ . The time complexity of CNSA is $O (F^{2})$ .

SAA

After obtaining the candidate node set, we reduce the number of nodes in this set to reduce the system’s cost. Because not all the candidate nodes can experience transmission conflicts, we propose the SAA to analyze the schedulability of the ICPS under a traditional FP policy in one superframe (a superframe is the lowest common multiple of $t_{i}$ , $i \in F$ ). The SAA improves system schedulability by replacing some of the nodes in $Λ$ with MU-MIMO nodes.

Since SAA is used after the CNSA, we do not consider the slot allocations for each flow; we just replace conflict nodes with MU-MIMO nodes when a transmission conflict occurs.

When the system cannot be scheduled, we need to improve the schedulability using MU-MIMO nodes. Because MU-MIMO nodes can both receive and send packets in a single time slot, we first allocate slots for each node without considering transmission conflicts (the network controller allocates the channel for each transmission using the FP scheduling policy). Then, we replace conflict nodes with MU-MIMO nodes to guarantee system schedulability. Obviously, it is both unnecessary and not cost-effective to replace all the nodes in the candidate node set with MU-MIMO nodes. Therefore, SAA reduces the number of MU-MIMO nodes in $Λ$ through slot analysis. The pseudo code of the SAA algorithm is as follows.

Algorithm 2 Slot analyzing algorithm
Require: the characters for each flow $F_{i}$ ; the candidate node set $Λ = {λ_{i}}$ , $i \in F$ ; Ensure: the schedulability of ICPS; 1: reallocation the slot for each node. 2: for each flow $i$ do 3: if the flow cannot be scheduled then 4: find the intersection nodes and reallocate slots for $F_{i}$ without considering transmission conflicts. 5: else 6: retain the original allocation. 7: end if 8: end for 9: for each node $λ_{i} \in Λ$ do 10: if $λ_{i}$ has two or more than two transmissions in the same time slot in one superframe then 11: $λ_{i}$ needs to be replaced; 12: end if 13: end for 14: if the system also cannot be scheduled then 15: for each unscheduled flow do 16: enhance the unscheduled flow’s transmission speed; 17: if $λ_{i}$ has two or more than two transmissions in the same time slot in one superframe then 18: $λ_{i}$ needs to be replaced; 19: end if 20: end for 21: end if 22: update $λ_{i}$ and $Λ = {λ_{i}}$ ; 23: return $Λ$ ;

Algorithm 2 Slot analyzing algorithm

Require: the characters for each flow

F_{i}

; the candidate node set

Λ = {λ_{i}}

i \in F

;
Ensure: the schedulability of ICPS;
1: reallocation the slot for each node.
2: for each flow

i

do
3: if the flow cannot be scheduled then
4: find the intersection nodes and reallocate slots for

F_{i}

without considering transmission conflicts.
5: else
6: retain the original allocation.
7: end if
8: end for
9: for each node

λ_{i} \in Λ

do
10: if

λ_{i}

has two or more than two transmissions in the same time slot in one superframe then
11:

λ_{i}

needs to be replaced;
12: end if
13: end for
14: if the system also cannot be scheduled then
15: for each unscheduled flow do
16: enhance the unscheduled flow’s transmission speed;
17: if

λ_{i}

has two or more than two transmissions in the same time slot in one superframe then
18:

λ_{i}

needs to be replaced;
19: end if
20: end for
21: end if
22: update

λ_{i}

and

Λ = {λ_{i}}

;
23: return

Λ

;

We reallocate the transmission time slots for each node by the schedulability of each flow (lines 1–8). If the flow cannot be scheduled, we find the intersection nodes and reallocate the slots for this flow without considering transmission conflicts. Otherwise, we retain the original allocation. Then, we analyze the transmission slot for each node in $Λ$ (lines 9–23). When a node in $Λ$ has more than one transmission at the same time slot, that means a transmission conflict occurs at this node, and we need to replace the node with a MU-MIMO node (lines 9–13). When the system also cannot be scheduled, SAA then reallocates slots to accelerate the transmission speed of unscheduled flows until the flows can be scheduled (lines 14–21). Finally, SAA updates $λ_{i}$ and returns $Λ$ the set of nodes that need to be replaced (lines 22–23). The theorem is as follows.

Theorem 1

ICPS can be scheduled with SAA when the number of channels is no less than the number of flows $(m \geq n)$ .

Proof

When $k$ flows conflict at node $A$ , we denote the flow with the highest priority as $F_{1}$ , and the flow with the lowest priority as $F_{k}$ . $F_{1}$ transmits first and cannot be delayed at node $A$ . The other flows must wait on $F_{1}$ , consequently, this generates delay. When the number of channels is no less than the number of flows, no delay is caused by transmission conflicts. Hence, flow $F_{i} i \in k$ will miss its deadline and cannot be scheduled when $c_{i} + de l_{i} > d_{i}$ , where $del$ is the delay slots. Using SAA, we can eliminate the delays caused by transmission conflicts. $k$ flows can transmit simultaneously when $m > n$ because the number of hops in each flow’s transmission $c$ is no larger than its deadline $d$ . Thus, we can guarantee all the flows can be scheduled and, therefore, the system can be scheduled using SAA when the number of channels is no less than the number of flows.

PIA

In this section, we study how to reduce the number of MU-MIMO nodes by the second method, the PIA scheduling algorithm, which performs optimal allocation of resources before the system runs. Through optimal allocation, PIA can decrease the number of transmission conflicts at intersection nodes and further reduce the number of required MU-MIMO nodes. As shown in Figure 6, $V 5$ does not need to be replaced by a MU-MIMO node when $d_{i} = 6$ in Figure 3(a).

Figure 6.

Another slot allocation for the example in Figure 3.

Initially, the PIA allocates slots based on the traditional FP policy. If the system cannot be scheduled, the network controller obtains each flow’s arrival time at its destination, which can be denoted as $r_{i}$ . Then, we can obtain the following theorem.

Theorem 2

When $F_{i}$ and $F_{j}$ conflict at node set $V = V_{1}, V_{2}, \dots, i < V_{h} (i < j)$ , we denote the length of the overlap as $Len (ij)$ , and its conflict delay is $D (ij)$ . The schedulability of $F_{i}$ is unaffected by the priority inversion of $F_{i}$ and $F_{j}$ when it satisfies: (1) $r_{i} + D (ij) \leq d_{i}$ and (2) $V$ is the last part of the overlapping nodes of $F_{i}$ .

Proof

The priority of $F_{i}$ is higher than that of $F_{j}$ based on the assumption that $i < j$ . When transmission conflict occurs at node set $V = V_{1}, V_{2}, \dots, V_{h}$ , $F_{j}$ must be delayed by $F_{i}$ . We can accelerate the transmission speed by transmitting $F_{j}$ first when the schedulability of $F_{i}$ does not be changed. We introduce the result proposed by Saifullah et al.,⁹ in which the upper bound $Δ (i, j)$ of the delay that $F_{j}$ can experience from an instance of $F_{i}$ is

Δ (ij) = \sum_{k = 1}^{δ (ij)} Le n_{k} (ij) - \sum_{k' = 1}^{δ' (ij)} (Le n_{k'} (ij) - 3)

(1)

where $δ (ij)$ is the number of path overlaps, $Le n_{k} (ij)$ is length of the $k th$ overlap on $F_{i}$ and $F_{j}$ , $δ' (ij)$ is the number of path overlaps larger than 3. Hence, the problem is transformed into one of calculating the delay $F_{i}$ must bear while waiting for $F_{j}$ to transmit. By simplifying equation (2), we can obtain the delay in $V$ as follows

D (ij) = {\begin{matrix} Len (ij), & Len (ij) < 4 \\ Len (ij) - 3, & Len (ij) \geq 4 \end{matrix}

(2)

When $V$ is the last part of the overlap nodes of $F_{i}$ , no other factors can cause additional delay to $F_{i}$ . Hence, the schedulability of $F_{i}$ is unaffected by the priority inversion of $F_{i}$ and $F_{j}$ when it satisfies (1) $r_{i} + D (ij) \leq d_{i}$ and (2) $V$ is the last part of the overlap nodes of $F_{i}$ .

Based on Theorem 2, PIA accelerates the unscheduled flow until it can be scheduled or no longer influences the other flow’s schedulability. However, Theorem 2 is not suitable for all overlaps. When $F_{i}$ involves several parts of overlaps, we can only guarantee the acceleration of the low priority flow on the last overlap. For the flow’s intersections with $F_{i}$ in the other parts of the overlaps, we define an effective overlap region (EOR) as follows.

Definition 2 (EOR)

When $F_{i}$ and $F_{j}$ conflict in node set $V = V_{1}, V_{2}, \dots, V_{h} (i < j)$ , the overall node set $V$ is the EOR. If $F_{i}$ and $F_{j}$ have an overlap but do not conflict, then $V$ is not an EOR.

Hence, Theorem 2 can be extended as follows.

Theorem 3

When $F_{i}$ and $F_{j}$ conflict at node set $V = V_{1}, V_{2}, \dots, V_{h} (i < j)$ , the schedulability of $F_{i}$ is unaffected by the priority inversion of $F_{i}$ and $F_{j}$ when it satisfies (1) $r_{i} + D (ij) \leq d_{i}$ , (2) it does not change the character of non-EORs after $V$ , and (3) $V$ is the last EOR of $F_{i}$ .

Proof

Based on Theorem 2, we extend priority inversion to the last part of the EOR of $F_{i}$ . When the operation satisfies (1) $r_{i} + D (ij) \leq d_{i}$ , (2) it does not change the character of non-EORs after $V$ , and (3) $V$ is the last part of the EOR of $F_{i}$ . Then, the schedulability of $F_{i}$ and its intersection flows are unaffected by the wait for $F_{j}$ to transmit. Hence, when $F_{i}$ and $F_{j}$ conflict at node set $V = V_{1}, V_{2}, \dots, V_{h} (i < j)$ , the schedulability of $F_{i}$ is unaffected by the priority inversion of $F_{i}$ and $F_{j}$ when it satisfies (1) $r_{i} + D (ij) \leq d_{i}$ , (2) it does not change the character of non-EORs after $V$ , and (3) $V$ is the last part of the EOR of $F_{i}$ .

To guarantee the second constraint condition in Theorem 3, we denote the number of overlaps after the last EOR in $F_{i}$ as $o_{i}$ . For any flow $k$ , when $F_{k}$ and $F_{i}$ have a path overlap after the last EOR in $V$ , we denote this overlap path as $o_{ik}$ . Hence, the fact that the second condition in Theorem 3 can be translated into the priority inversion operation does not affect the schedulability of $F_{i}$ and $F_{k}$ . Obviously, $F_{k}$ and $F_{i}$ cannot conflict when the packets generated by the two flows arrive such that $o_{ik}$ satisfies

∥ r_{i}^{o_{ik}} - r_{k}^{o_{ik}} ∥ > Dij

(3)

where $r_{i}^{o_{ik}}$ is the time at which the packet generated by $F_{i}$ reaches $o_{ik}$ (it is easy to obtain $o_{ik}$ from the network controller). When the arrival time difference of $F_{i}$ and $F_{k}$ is larger than $Dij$ , $o_{ik}$ is not an EOR. By updating $r_{i}^{o_{ik}}, i \in F$ , we can determine whether to invert the priority of $F_{i}$ and $F_{j}$ .

Based on the above discussion, the PIA can reduce the number of transmission conflicts before adding MU-MIMO nodes to the system. Furthermore, the PIA can also improve the schedulability of ICPSs under a high-criticality mode. When the system cannot be scheduled under the PIA, the nodes at flow intersections will be replaced by MU-MIMO nodes to guarantee the schedulability of ICPS. The pseudo code of the PIA is as follows.

Algorithm 3 Priority inversion algorithm
Require: the characters for each flow $F_{i}$ ; the candidate node set $Λ = {λ_{i}}$ , $i \in F$ . Ensure: reduce the number of transmission conflicts by optimal slot allocations; 1: reallocation slots for each node by FP. 2: the number of MU-MIMO nodes $τ = 0$ . 3: while the system cannot be scheduled do 4: for each flow $i$ do 5: obtain each flow’s $o_{i}$ , $Len$ and the corresponding $o_{ik}$ , $i, k \in F$ ; 6: end for 7: for each unscheduled flow $j$ do 8: if flow $i$ satisfies Theorem 3 then 9: invert the priority between $F_{i}$ and $F_{j}$ ; 10: else 11: replace the overlap nods with MU-MIMO nodes; 12: $τ + +$ ; 13: end if 14: end for 15: end while 16: return $τ$ ;

Algorithm 3 Priority inversion algorithm

Require: the characters for each flow

F_{i}

; the candidate node set

Λ = {λ_{i}}

i \in F

.
Ensure: reduce the number of transmission conflicts by optimal slot allocations;
1: reallocation slots for each node by FP.
2: the number of MU-MIMO nodes

τ = 0

.
3: while the system cannot be scheduled do
4: for each flow

i

do
5: obtain each flow’s

o_{i}

Len

and the corresponding

o_{ik}

i, k \in F

;
6: end for
7: for each unscheduled flow

j

do
8: if flow

i

satisfies Theorem 3 then
9: invert the priority between

F_{i}

and

F_{j}

;
10: else
11: replace the overlap nods with MU-MIMO nodes;
12:

τ + +

;
13: end if
14: end for
15: end while
16: return

τ

;

PIA first allocates slots under the FP policy (line 1) and initializes the number of MU-MIMO nodes (line 2). Then, it judges whether the system can be scheduled or not. If the system can be scheduled, it returns $τ$ , otherwise, PIA accelerates the transmission speed of unscheduled flows by Theorem 3. When the flows do not satisfy the conditions, PIA replaces the overlap nodes with MU-MIMO nodes, similar to the SAA, and increments $τ$ by one (lines 3–16).

When the system performs the priority inversion operation at the last EOR, the conflict is removed. Hence, that part of the overlap is no longer an EOR. The system repeats this process until either the system can be scheduled or no flow satisfies Theorem 3.

Algorithm analysis in high-criticality mode

In this section, we analyze the schedulability of the SAA and the PIA. Since both the SAA and PIA can be scheduled by adding MU-MIMO nodes in low-criticality mode, we analyze only the schedulability in high-criticality mode.

Theorem 4

PIA has a higher schedulability than SAA when the system is in high-criticality mode.

Proof

When the system switches to high-criticality mode, low-criticality flows are abandoned and the high-criticality flow period changes to $ℵ_{i} t_{i}, (c_{i} / t_{i}) \leq ℵ_{i} < 1$ . Because $t_{i} = d_{i}$ , the flow must arrive at its destination before $ℵ_{i} d_{i}$ . We analyze the schedulability by a discussion of classification. The flows are classified into two categories: (1) those in which the flow does not overlap other high-criticality flows and (2) those in which the flow overlaps other high-criticality flows. For $F_{i}$ in the first category, the schedulability of both the SAA and the PIA are identical. When a flow is not blocked by other flows it can be scheduled when

r_{i} \leq ℵ_{i} d_{i}

(4)

For $F_{j}$ in the second category, $F_{j}$ is delayed by other flows in $D (j)$ slots. Then, $F_{j}$ can be scheduled when

r_{j} + D (j) \leq ℵ_{j} d_{j}

(5)

We denote the number of MU-MIMO nodes in the SAA and PIA as $τ_{j}^{SAA}$ and $τ_{j}^{PIA}$ , respectively. Because the PIA reduces the number of transmission conflicts before replacing intersection nodes to MU-MIMO nodes, $τ_{j}^{SAA} \geq τ_{j}^{PIA}$ . By Theorem 2, we can obtain

D (j) = \sum_{k = 1}^{τ_{j}} D (ij)

(6)

when $F_{i}$ and $F_{j}$ conflict, $D (ij) = {\begin{matrix} Len (ij), & Len (ij) < 4 \\ (Len (ij) - 3), & Len (ij) \geq 4 \end{matrix}$ , which is determined only by the length of the overlap. Then, we can obtain the relationship between SAA and PIA as follows

r_{j}^{PIA} + D (j)^{PIA} \leq r_{j}^{SAA} + D (j)^{SAA}

(7)

Hence, the PIA has a higher schedulability than does the SAA when the system is in high-criticality mode.

Experiments

We evaluate the performance of our proposed methods by experiments. We compare our approaches with the traditional FP algorithm without MU-MIMO nodes. We compare both the acceptance rate and the number of MU-MIMO nodes for each criticality mode. We use the acceptance rate to represent the schedulability of an ICPS. When all flows can be scheduled, the acceptance rate is $1$ ; otherwise, it is $0$ . To control the workload of the entire system, the simulations use the UUniFast algorithm, which can make the flows neither pessimistic nor optimistic for the analysis.³⁶ All algorithms are implemented in C language. These programs run on a Windows machine with 3.2 GHz CPU and 8 GB memory. Some simulation parameters are summarized in Table 1.

Table 1.

Simulation parameters.

Parameter	Description
$n$	The number of flows
$N$	The number of nodes
$m$	The number of channels
$U$	Network utilization
$u_{i}$	Flow i’s utilization
$t$	The period of flow
$d$	The deadline of flow
$c$	The number of transmission hops

Low-critical mode

We first compare the performances of the algorithms in low-critical mode. As shown in Figure 7(a), the system acceptance rate is decreased by the FP scheduling policy (n = 15, N = 50, m = 16), which occurs because the idle resources decrease as the system utilization increases. The latency tolerance of a packet is reduced along with the idle resources. The ICPS can be scheduled under both SAA and PIA in any situations by increasing the number of MU-MIMO nodes when $m \geq n$ . Figure 7(b) shows the relationship between the number of MU-MIMO nodes and utilization. Obviously, both the SAA and the PIA can reduce the number of MU-MIMO nodes under the premise that the system is schedulable. Because the PIA optimizes slots allocation before the node replacement operation, the PIA uses fewer MU-MIMO nodes than does the SAA. However, none of the curves have an obvious tendency because system utilization involves not only the flow period $(t)$ but also the number of transmission hops $(c)$ . We need to regenerate the transmission path for each flow to satisfy the system utilization requirements. Hence, the number of candidate nodes goes up and down. Because a MU-MIMO node is selected from the candidate node set, the number of MU-MIMO nodes is always less than the number of candidate nodes.

Figure 7.

(a) Relationship between the acceptance rate system utilization and (b) relationship between the number of MU-MIMO nodes and system utilization.

We repeat this simulation for the situation in which all flows can be scheduled as shown in Figure 8. The number of candidate nodes is fixed when we increase system utilization by only adjusting the flow period (because there is only one test in this simulation, and the flow transmission paths do not vary). Initially, no MU-MIMO nodes exist in the system because it can be scheduled without any MU-MIMO nodes. However, when we increase the system utilization, transmission conflict occurs. To guarantee the schedulability of system, we need to add MU-MIMO nodes to the system. In addition, the number of MU-MIMO nodes required by the PIA is always less than the number required by the SAA. This occurs because by optimizing slots allocation, the PIA can reduce the number of transmission conflicts. Hence, the number of MU-MIMO nodes required by the PIA is always less than the number required by the SAA.

Figure 8.

Relationship between the number of MU-MIMO nodes and system utilization.

The relationship between the acceptance rate/number of MU-MIMO nodes and the number of flows is shown in Figure 9 (U = 0.3, N = 50, m = 16). The acceptance rate is reduced along with the number of flows under the FP scheduling policy. The acceptance rates of the SAA and PIA are reduced when the number of flows becomes larger than the number of channels. This result occurs because when $m < n$ , delays are caused by channel contention. The PIA achieves a better performance than the SAA when $n > 16$ because it uses fewer MU-MIMO nodes. In addition, both the number of candidate nodes and the number of MU-MIMO nodes increase as the number of flows increase. This result occurs because the number of intersections increases when the number of flows increase, causing more transmission conflicts in the system. Thus, the system requires more MU-MIMO nodes to guarantee its schedulability, and the number of MU-MIMO nodes always satisfies $τ^{FP} > τ^{SAA} > τ^{PIA}$ .

Figure 9.

(a) Relationship between the acceptance rate/number of MU-MIMO nodes and the number of flows and (b) relationship between the number of MU-MIMO nodes and the number of flows.

Figure 10 shows the relationship between the acceptance rate/number of MU-MIMO nodes and the number of nodes (U = 0.3, n = 15, m = 16). All these results indicate that the SAA and the PIA can guarantee the schedulability of the system. The number of MU-MIMO nodes in both the SAA and the PIA is no larger than the number of candidate nodes regardless of the conditions. In addition, when the number of nodes increases to 90, the number of MU-MIMO nodes in the PIA and the SAA is identical because the PIA transmutes into the SAA when it cannot resolve the conflict.

Figure 10.

(a) Relationship between the acceptance rate and the number of flows and (b) relationship between the number of MU-MIMO nodes and the number of flows.

High-critical mode

When the system switches to high-critical mode, the number of MU-MIMO nodes is no longer our main concern (the number of MU-MIMO nodes is the same as in low-critical mode). Instead, we are more concerned with the performances of SAA and PIA in high-critical mode.

Figure 11 shows the relationship between the system acceptance rate and system parameters such as the number of nodes and the number of flows. In these conditions, we set $ℵ = 0.9 > max {(c_{i} / t_{i}), i \in F}$ . If $max {(c_{i} / t_{i}), i \in F} \geq 0.9$ , we will regenerate the system. Figure 11 illustrates (as Theorem 4 proves) that the acceptance rate in the PIA is always better than that in the SAA.

Figure 11.

(a) Relationship between the acceptance rate and the number of nodes in high-critical mode and (b) relationship between the acceptance rate and the number of flows in high-critical mode.

Figure 12 shows the relationship between the system acceptancerate and system utilization. To study the relationship between these two elements, we increase system utilization by adjusting only the flow period. Subsequently, we obtain the same result as Figure 11, which also verifies the correctness of Theorem 4.

Figure 12.

Relationship between the number of MU-MIMO nodes and system utilization in high-critical mode.

Conclusion

In this article, we make key contributions to real-time transmission scheduling in ICPSs. We first introduce MU-MIMO technology and the concept of a mixed-critical system into ICPSs and discuss the characteristics of these two features. Then, we analyze the transmission paths and obtain the candidate node set. Next, based on the characteristics of MU-MIMO nodes, we propose the SAA and the PIA to guarantee the schedulability of ICPS in low-criticality mode. By considering system cost, these two algorithms help to reduce the number of MU-MIMO nodes used. Finally, we analyze the schedulability of these two algorithms when the system switches to high-criticality mode. The simulation results show that our scheduling algorithms and analysis perform better than the existing scheduling policy. In future work, we plan to study ICPS schedulability under conditions with limited numbers of antennas and to implement our approach in a real-world ICPS.

Footnotes

Handling Editor: Zhipeng Cai

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was partially supported by the National Natural Science Foundation of China (grants 61502474, 61233007, and 61672349) and by the Youth Innovation Promotion Association CAS.

ORCID iD

Jintao Wang

References

Saifullah

et al . Real-time wireless sensor-actuator networks for industrial cyber-physical systems. P IEEE 2016; 104(5): 1013–1024.

Lee

Seshia

. Introduction to embedded systems: a cyber-physical systems approach. Cambridge, MA: MIT Press, 2016.

Kong

Yuan

Xiao

et al . Stochastic optimization model and solution algorithm for blending procedure of process industrial. Inform Control 2016; 45(1): 40–44.

Zheng

Cai

et al . Follow but no track: privacy preserved profile publishing in cyber-physical social systems. IEEE Internet Things. Epub ahead of print 8 March 2017. DOI: 10.1109/JIOT.2017.2679483.

Cheng

Cai

et al . Extracting kernel dataset from big sensory data in wireless sensor networks. IEEE T Knowl Data En 2017; 29(4): 813–827.

ISA100, http://www.isa.org/isa100

Chen

Nixon

Mok

. Why WirelessHART. Boston, MA: Springer, 2010.

Liang

Zhang

Xiao

et al . Survey and experiments of WIA-PA specification of industrial wireless network. Wirel Commun Mob Com 2011; 11(8): 1197–1212.

Saifullah

et al . End-to-end communication delay analysis in industrial wireless networks. IEEE T Comput 2015; 64(5): 1361–1374.

10.

Sha

Gunatilaka

et al . Analysis of EDF scheduling for wireless sensor-actuator networks. In: Proceedings of the 2014 IEEE 22nd international symposium of quality of service (IWQoS), Hong Kong, China, 26–27 May 2014, pp.31–40. New York: IEEE.

11.

Gesbert

Shafi

Shiu

et al . From theory to practice: an overview of MIMO space-time coded wireless systems. IEEE J Sel Area Comm 2003; 21(3): 281–302.

12.

Hoydis

ten Brink

Debbah

. Massive MIMO in the UL/DL of cellular networks: how many antennas do we need? IEEE J Sel Area Comm 2013; 31(2): 160–171.

13.

Swindlehurst

et al . An overview of massive MIMO: benefits and challenges. IEEE J Sel Top Signa 2014; 8(5): 742–758.

14.

Ngo

Larsson

Marzetta

. Energy and spectral efficiency of very large multiuser MIMO systems. IEEE T Commun 2013; 61(4): 1436–1449.

15.

Bolchini

Miele

. Reliability-driven system-level synthesis for mixed-critical embedded systems. IEEE T Comput 2013; 62(12): 2489–2502.

16.

Kritikakou

Pagetti

Baldellon

et al . Run-time control to increase task parallelism in mixed-critical systems. In: Proceedings of the 2014 26th Euromicro conference on real-time systems (ECRTS), Madrid, 8–11 July 2014, pp.119–128. New York: IEEE.

17.

Izosimov

Levholt

. Mixed criticality metric for safety-critical cyber-physical systems on multi-core architectures. Methods 2015; 2: 8.

18.

Saifullah

et al . Real-time scheduling for WirelessHART networks. In: Proceedings of the 2010 IEEE 31st real-time systems symposium (RTSS), San Diego, CA, 30 November–3 December 2010, pp.150–159. New York: IEEE.

19.

Xia

Jin

Kong

et al . Bounding the demand of mixed-criticality industrial wireless sensor networks. IEEE Access 2017; 5: 7505–7516.

20.

Zheng

Cai

et al . A study on application-aware scheduling in wireless networks. IEEE T Mobile Comput 2017; 16(7): 1787–1801.

21.

Kong

Liu

. mZig: enabling multipacket reception in zigbee. In: Proceedings of the 21st annual international conference on mobile computing and networking, Paris, 7–11 September 2015, pp.552–565. New York: ACM.

22.

Hithnawi

Shafagh

et al . CrossZig: combating cross-technology interference in low-power wireless networks. In: Proceedings of the 2016 15th ACM/IEEE international conference on information processing in sensor networks (IPSN), Vienna, 11–14 April 2016, pp.1–12. New York: IEEE.

23.

Cheng

Niu

et al . Taming collisions for delay reduction in low-duty-cycle wireless sensor networks. In: Proceedings of the 35th annual IEEE international conference on computer communications (INFOCOM 2016), San Francisco, CA, 10–14 April 2016, pp.1–9. New York: IEEE.

24.

Yuan

Chen

. Virtual MIMO-based cross-layer design for wireless sensor networks. IEEE T Veh Technol 2006; 55(3): 856–864.

25.

Zhao

Yang

Wang

. Mobile data gathering with load balanced clustering and dual data uploading in wireless sensor networks. IEEE T Mobile Comput 2015; 14(4): 770–785.

26.

Vestal

. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proceedings of the 28th IEEE international real-time systems symposium, 2007 (RTSS 2007), Tucson, AZ, 3–6 December 2007, pp.239–243. New York: IEEE.

27.

Baruah

Stougie

. Towards the design of certifiable mixed-criticality systems. In: Proceedings of the 2010 16th IEEE real-time and embedded technology and applications symposium (RTAS), Stockholm, 12–15 April 2010, pp.13–22. New York: IEEE.

28.

Baruah

Bonifaci

D’Angelo

et al . Scheduling real-time mixed-criticality jobs. IEEE T Comput 2012; 61(8): 1140–1152.

29.

Ekberg

. Bounding and shaping the demand of mixed-criticality sporadic tasks. In: Proceedings of the 2012 24th Euromicro conference on real-time systems (ECRTS), Pisa, 11–13 July 2012, pp.135–144. New York: IEEE.

30.

Wolf

. High-performance embedded computing: applications in cyber-physical systems and mobile computing. Amsterdam: Newnes, 2014.

31.

Huang

Yang

Thiele

. On the scheduling of fault-tolerant mixed-criticality systems. In: Proceedings of the 51st annual design automation conference, San Francisco, CA, 1–5 June 2014, pp.1–6. New York: ACM.

32.

Jin

Wang

Zeng

. End-to-end delay analysis for mixed-criticality WirelessHART networks. IEEE/CAA J Automat Sin 2015; 2(3): 282–289.

33.

Herms

Schemmer

Lukas

. Real-time mesh networks for industrial automation. In: Proceedings of the SPS/IPC/DRIVES, Elektrische Automatisierung, Systeme und Komponenten, Nürnberg, 28–30 November 2006, vol. 7. Springer.

34.

De Lamare

Haardt

. Multi-branch Tomlinson-Harashima precoding design for MU-MIMO systems: theory and algorithms. IEEE T Commun 2014; 62(3): 939–951.

35.

Huang

W-H

Chen

. Self-suspension real-time tasks under fixed-relative-deadline fixed priority scheduling. In: Proceedings of the 2016 conference on design, automation & test in Europe conference & exhibition (DATE) (EDA consortium), Dresden, 14–18 March 2016, pp.1078–1083. New York: IEEE.

36.

Bini

Buttazzo

. Measuring the performance of schedulability tests. Real-Time Syst 2005; 30(1–2): 129–154.