IEEE/CAA Journal of Automatica Sinica  2015, Vol.2 Issue (3): 282-289   PDF    
End-to-end Delay Analysis for Mixed-criticality WirelessHART Networks
Xi Jin , Jintao Wang1, Peng Zeng2,3    
1. Laboratory of Networked Control Systems, Shenyang Institute of Automation, Chinese Academy of Science, Shenyang 110016, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China;
3. Shenyang Institute of Automation, Chinese Academy of Science, Shenyang 110016, China
Abstract: WirelessHART, as a robust and reliable wireless protocol, has been widely-used in industrial wireless sensoractuator networks. Its real-time performance has been extensively studied, but limited to the single criticality case. Many advanced applications have mixed-criticality communications, where different data flows come with different levels of importance or criticality. Hence, in this paper, we study the real-time mixedcriticality communication using WirelessHART protocol, and propose an end-to-end delay analysis approach based on fixed priority scheduling. To the best of our knowledge, this is the first work that introduces the concept of mixed-criticality into wireless sensor-actuator networks. Evaluation results show the effectiveness and efficacy of our approach.
Key words: WirelessHART networks     mixed-criticality     endto- end delay     delay analysis    
Ⅰ. INTRODUCTION

WirelessHART[1] is a robust and reliable wireless sensor-actuator network (WSAN) protocol,and has been widely-used in industrial process monitoring and control. It is based on centralized network management and multi-channel time division multiple access (TDMA). These special features have attracted researchers' attentions,and they have done some works about real-time performance of WirelessHART networks,e.g.,[2, 3, 4, 5]. However,all these works focus on the single criticality case.

Advanced real-life applications come with mixed-criticality data communications. Different data flows not only own different priorities but also have different levels of importance or criticality. For example,Fig. 1 shows different sensor and actuator nodes installed for cement manufacturing. In cement manufacturing,the current data of motors have more importance or higher criticality than the pressure data of pre-heater. Motor current data must be sent to destinations within their end-to-end deadlines,otherwise production inefficiency or even explosions may happen. By contrast,the less important preheater pressure data can miss their deadlines occasionally without causing any serious accidents. However,preheater pressure data usually have the highest priority due to their frequent state change and urgent transmission requirement. Hence,criticality levels are not equivalent to priorities and are independent of real-time requirements. Mixed-criticality combined with priority provides a way to guarantee both the importance and real-time requirement of data flows. During normal operations,all data flows are scheduled according to their priorities. During errors or exceptions,the important data are more frequently delivered and more network resources are needed. In this situation,if there are not enough network resources to serve all data,the less important data will be discarded.

Download:
Fig. 1 The wireless network for cement manufacturing industry

The key difference between mixed- and single-criticality systems is that the importance of data in mixed-criticality systems must be considered together with real-time performance. This leads to the problem that directly using traditional priority-based scheduling theory of single-criticality systems to mixed-criticality systems is infeasible due to independence between criticality and priority. So the traditional real-time theory needs a revision to support mixed-criticality. The end-to-end delay analysis is the foundation of the real-time theory. In this paper,we propose an end-to-end delay analysis approach for fixed priority scheduling in mixed-criticality real-time WirelessHART networks. To the best of our knowledge,this paper is the first work that introduces the concept of mixed-criticality into real-time WSANs. The end-to-end delay is used to test whether the data flows can meet their special requirements at design time,i.e.,analyzing end-to-end delay is the effective way to guarantee systems' reliability. This paper covers the first stage of our study for mixed-criticality real-time WSANs.

In this paper,our contributions are listed as follows:

1) We introduce the concept of mixed-criticality into real-time wireless networks and propose a formulated system model,which is the common platform for mixed-criticality real-time theories of wireless networks.

2) We propose an end-to-end delay analysis approach. It is a fast feasible approach to test the reliability of mixed-criticality systems.

3) Evaluation results show that our approach is very effective and only incurs little pessimism comparing with simulation results and a real testbed.

The rest of this paper is organized as follows: Section II introduces related works. Section III describes the system model. Section IV presents our end-to-end delay analysis. Section V shows evaluation results. And Section VI concludes this paper.

Ⅱ. RELATED WORK

The mixed-criticality concept is first introduced to real-time community in [6],and then many works address how to adapt existing uniprocessor/multiprocessor scheduling theories to support both criticality and priority under a single scheduling framework,e.g., [7, 8, 9, 10, 11, 12, 13]. But these works do not consider the communication media.

For the communication media,there are a few related works on mixed-criticality. References [14, 15, 16] study Network-on-Chips for mixed-criticality multiprocessor systems. [17] proposes mixed-criticality protocols for the controller area network (CAN), and then a response-time analysis method and an optimal priority assignment scheme are provided. [18] designs a virtual CAN controller to provide differentiated services for different criticality levels. [19, 20, 21] focus on the wired network --- TTEthernet. They propose some scheduling algorithms to guarantee messages' time constraints. To the best of our knowledge,the reference [22] is the only work about wireless networks,which considers mixed-criticality. It introduces mixed-criticality scheduling method to JPEG2000 video systems based on the IEEE 802.11 standard. But WirelessHART networks are based on the IEEE 802.15.4 standard and are quite different from the wireless video system. So existing system models and solutions cannot be used in our model.

Ⅲ. SYSTEM MODEL A. Mixed-Criticality WirelessHART Network Model

We consider a WirelessHART network characterized by $G$ $=$ $\langle V,E,m\rangle$:

1) A WirelessHART network consists of sensor/actuator nodes and a gateway with centralized network manager. We use $n$ nodes $V=\{v_1,v_2,\ldots,v_n\}$ to denote these devices,such as,in Fig. 1,the gateway is $v_1$ and the pressure sensor node of the cooler is $v_2$. Each node is equipped with a transmitter,so it cannot send and receive in the same time slot.

2) $E: V \times V$ is the set of links. Each element $e_{ij}$ in $E$ represents existing reliable communication between $v_i$ and $v_j$. Transmitting a packet through one link is called transmission.

3) We use $m$ to denote the number of available channels. WirelessHART networks support 16 non-overlapping channels. But not all of these channels can always be accessed,since they may suffer from persistent external interference. Hence,$0 < m \le 16$. Each channel supports a transmission in one time slot.

The data flow set is denoted by $F$. Each flow ${{F}_{i}}$ is characterized by $F_i=\langle \chi_i,c_i,t_i(x),p_i,\phi_i\rangle$. $p_i$ denotes the distinct fixed priority. $\phi_i$ ($\phi_i \subseteq E$) is an ordered sequence of links and denotes the routing path of the flow ${{F}_{i}}$. The centralized manager of the WirelessHART network collects sensor data and distributes actuator data,so the gateway is the source or destination for each flow. For TDMA protocol,each time slot allows a one-hop data transmission and its acknowledgement to be transmitted. We use ${{c}_{i}}$ to denote the number of time slots required to deliver a packet from the source to the destination,i.e.,${{c}_{i}}$ is equal to the number of hops of the flow ${{F}_{i}}$.

$\chi_i$ denotes the criticality level of the flow ${{F}_{i}}$. For ease of presentation,we only focus on dual-criticality system,in which there are only two criticality levels $L$ (low) and $H$ (high). However,it can be easily extended to systems with an arbitrary number of criticality levels. Correspondingly,the network also has dual-criticality modes $\{H,L\}$. If the criticality level of the flow ${{F}_{i}}$ is not less than the current network mode $x$,it can be delivered; otherwise,the flow is discarded. The network starts in the low criticality mode ($x$ $=L$),in which all flows are served. When the error or the exception occurs in a node,the node will trigger the changing of the network mode from low criticality to high criticality ($x$ $=$ $H$). Then only the flows with high criticality level can be delivered,and the low criticality flows are discarded. Note that the mode change will introduce additional time to the delay of the high criticality flow and the message of mode change should be broadcast to the entire network as soon as possible. There are some methods used to solve this problem. For example,one channel and one transmitter of each node can be reserved to serve the message. The detail of mode change is out of the range of this paper. Therefore,we only model the duration of the mode change as $C$,which is used to calculate the delay of the packet delivered during the mode change.

When errors and exceptions occur,workers will handle problems and change the mode from high criticality to low criticality. We do not consider this process due to the unpredictability of workers' behavior,i.e.,we do not study the mode change from high criticality to low criticality. The assumption is also widely adopted in existing works ([9, 10, 12, 14] et al.).

In mixed-criticality uniprocessor/multiprocessor systems,the execution time of a task is a function of the system mode. In wireless networks,the number of time slots required to deliver a packet is equal to the number of hops and fixed. However,the period $t_i$ is dependent on the network criticality mode. Since the important flow is more frequently delivered when the network mode is changed to high criticality due to exceptions,hence, $t_i(H) < t_i(L)$.

According to the period $t_i(x)$,the flow $F_i$ periodically releases a packet,which is assigned the parameters specified in $F_i$. Our system adopts the implicit-deadline,i.e.,the packet's relative deadline is equal to the flow's period corresponding with the network mode of generating the packet. For example,if the packet is released in the network mode $L$,then its relative deadline is $t_i(L)$. So in a stable network,at most one packet of each flow is active at any time. But when the network mode is changed from $L$ to $H$,there may exist two active packets belonging to one flow because of the change of the flow's period. In this case,the packet released in the network mode $H$ has higher priority than another.

A packet is released at time slot $s_1$,and arrives its destination at time slot $s_2$,then its end-to-end delay is ($s_2 - s_1 +1$). The end-to-end delay of a flow is the maximum delay among all its packets. If a scheduling algorithm can schedule all flows such that all packets' end-to-end delays are less than or equal to their deadlines,the flow set is called schedulable under the scheduling algorithm.

Note that not all of the above assumptions are supported by the original WirelessHART protocol. But they can be implemented in the application layer[[2, 3, 4]. In Section V,our real testbed is introduced.

B. Fixed Priority Scheduling

We focus on the end-to-end delay analysis for fixed priority scheduling,which is the most commonly used real-time scheduling in real-life systems. In fixed priority scheduling,transmissions are scheduled within a hyper-period $T$,which is equal to the least common multiple of periods of all flows,since after that all schedulings are cyclically repeated. The period supported by the WirelessHART protocol is $2^i$,where $i$ $\ge$ $0$. So the hyper-period $T$ is equal to the maximum period among all flows. At each time slot of $T$,if there exist unused channels,the transmission with the highest priority is scheduled. But,if the released transmission shares nodes with the transmissions that have been scheduled at this time slot,it cannot be scheduled since one node cannot serve more than one transmission at one time slot. So there are two factors influencing the transmission scheduling: channel contention (there are no unused channels assigned to the transmission) and transmission conflicts (a transmission cannot be scheduled,if it shares a node with a transmission that has been scheduled in this time slot)[[3]. In other words,the two factors introduce extra delays. In the following,we analyze delays introduced by two factors separately.

Problem Statement. Given the mixed-criticality WirelessHART network $G$,the flow set $F$ and the fixed priority scheduling algorithm,our objective is to analyze the end-to-end delay for each flow,such that the schedulability of the flow set can be determined.

Table I summarizes the key notations used in this paper.

Ⅳ. END-TO-END DELAY ANALYSIS

Our analysis is based on the end-to-end delay analysis (EDA) method[[2],which is the state-of-the-art end-to-end delay analysis for fixed priority scheduling in single-criticality real-time WirelessHART networks. To make our paper self-contained, we first introduce EDA. Then we present our end-to-end delay analysis for mixed-criticality WirelessHART networks.

A. Analysis for Single-criticality WirelessHART Networks The EDA analysis contains two steps. The first step calculates the delay due to channel contention,which is called pseudo upper bound of the worst case end-to-end delay and denoted by $R^{ch}_k$. Then the second step incorporates the delay due to transmission conflicts into the result of the first step.

Table Ⅰ
KEY NOTATIONS

1) Pseudo delay

The flow $F_k$ experiences the worst case delay when the level-$k$ busy period occurs. The level-k busy period is the maximum continuous time interval during which all channels are occupied by flows of priority higher than the priority of $F_k$,until $F_k$ finishes its active packet transmitting. The notation $hp(F_k)$ is used to denote the set of flows whose priorities are higher than $F_k$. If the flow $F_i$ ($F_i \in hp(F_k)$) has a packet with release time earlier than the level-$k$ busy period and deadline in the level-$k$ busy period,it is said to have carry-in workload in the busy period. Then two types of workload are presented as follows:

a) $W^{NC}_k(F_i,\alpha)$ denotes the workload upper bound in the level-$k$ busy period of $\alpha$ slots,if $F_i$ has no carry-in workload:

$ W_k^{NC}({F_i},\alpha ) = \left\lfloor {\frac{\alpha }{{{t_i}}}} \right\rfloor \times {c_i} + \min (\alpha \bmod {t_i},{c_i}),$
where $t_i$ denotes the period of $F_i$ in single-criticality networks.

b) $W^{CI}_k(F_i,\alpha)$ denotes the workload upper bound in the level-$k$ busy period of $\alpha$ slots,if $F_i$ has a carry-in workload:

$W_k^{CI}({F_i},\alpha ) = \left\lfloor {\frac{{\max (\alpha - {c_i},0)}}{{{t_i}}}} \right\rfloor \times {c_i} + {c_i} + {\mu _i},$
where ${\mu _i} = \min (\max (\max (\alpha - {c_i},0) - ({t_i} - {R_i}),0),{c_i} - 1)$ and $R_i$ denotes the worst case end-to-end delay of $F_i$ in single-criticality networks.

Similarly,there are two types of interference between $F_i$ and $F_k$ during $\alpha$ slots:

$I_{k}^{NC}({{F}_{i}},\alpha )=\min (W_{k}^{NC}({{F}_{i}},\alpha ),\alpha -{{c}_{k}}+1)$ (1)
$I_{k}^{CI}({{F}_{i}},\alpha )=\min (W_{k}^{CI}({{F}_{i}},\alpha ),\alpha -{{c}_{k}}+1)$ (2)

At most $m-1$ higher priority flows have carry-in workload in the network with $m$ channels. So $F_k$'s total delay due to channel contention is

$\begin{align*} {\Omega _k}(\alpha ) = \sum\limits_{{F_i} \in hp({F_k})} {I_k^{NC}({F_i},\alpha )} + {U_k}(\alpha ), \end{align*}$
where $U_k(\alpha)$ is the sum of the $\min (\left| {hp({F_k})} \right|,m - 1)$ largest values of the differences $I_k^{CI}({F_i},\alpha ) - I_k^{NC}({F_i},\alpha )$ among all $F_i$ $\in$ $hp(F_k)$.

The WirelessHART network contains $m$ channels,so (3) shows the delay due to channel contention. And the pseudo upper bound $R^{ch}_k$ is the minimal value of $\alpha$ that solves (3). $\alpha$ can be found using the iterative fixed-point algorithm[[23],which is widely used in the delay analysis of real time systems. The iterative calculation of $\alpha$ starts at $\alpha = c_k$. During the iterations,if $\alpha$ is larger than the deadline of the flow $F_k$,the algorithm terminates and the flow set is unschedulable; if the value of $\alpha$ is fixed and less than the deadline,the fixed-point is $R^{ch}_k$.

$\begin{align} \alpha = \left\lfloor {\frac{{{\Omega _k}(\alpha )}}{m}} \right\rfloor + {c_k}. \end{align}$ (3)

2) Worst case delay

This step incorporates the delay due to transmission conflicts into $R^{ch}_k$ to calculate the actual end-to-end delay $R_k$. First, we introduce some definitions.

a) $Q(k,i)$: the total number of $F_i'$s transmissions that share nodes with $F_k'$s transmissions.

b) $\delta_j(k,i)$: the number of nodes along the $j{\rm th}$ maximal common path between $F_k$ and $F_i$. $\delta {'_j}(k,i)$ is the length of the maximal common path with length at least 4. The delay caused by a maximal common path is at most 3, so the extra length is specially marked using $\delta {'_j}(k,i)$.

c) $\Delta(k,i)$: the upper bound of end-to-end delay due to transmission conflicts that $F_i$ contributes to $F_k$,

$\Delta (k,i) = Q(k,i) - \sum\limits_{j = 1}^\sigma {(\delta {'_j}(k,i) - 3),}$
where $\sigma$ is the number of maximal common paths between $F_k$ and $F_i$.

Thus the upper bound of the actual delay $R_k$ is the minimal solution of (4) by running the iterative fixed point algorithm starting at $\beta = R^{ch}_k$.
$\begin{align} \beta = R_k^{ch} + \sum\limits_{{F_i} \in hp({F_k})} {\left\lceil {\frac{\beta }{{{t_i}}}} \right\rceil } \times \Delta (k,i). \end{align}$ (4)
B. Analysis for Mixed-criticality WirelessHART Networks

Mixed-criticality networks dynamically change the network mode, which results in three types of packets transmitted in the network:

1) The release time and deadline of a packet are all in the network mode $L$. The end-to-end delay of this packet is denoted by $R_k(L)$.

2) The release time and deadline of a packet are all in the network mode $H$. The notation $R_k(H)$ is used to present the upper bound of its delay.

3) When the network mode is changed, the packet, which is released by high criticality flow in the network mode $L$, cannot be dropped. In this situation, the packet's release time is in the network mode $L$, but its deadline is in the $H$ mode. Flows formed by these packets are delivered only once. The notation $ {F}'$ presents the set of these flows and $R_k(L2H)$ denotes the upper bound of the delay.

$R_k(L)$ is unaffected by the mode change and is equal to the delay $R_k$ calculated in single-criticality networks. So we only analyze $R_k(H)$ and $R_k(L2H)$.

1) Analyzing $R_k(H)$: In the network mode $H$, packets belonging to the high criticality flow are delivered, no matter when they are released. So $R_k(H)$ is interfered by two flow sets $hpL({F_k})$ $=$ $\{ {F_i}|{F_i} \in {F}',{p_i} > {p_k},{\chi_i}=H\}$ and $hpH({F_k})$ $=$ $\{ {F_i}|{F_i} \in {F},{p_i} > {p_k},{\chi _i} = H\}$. From these, we can derive that the delay due to channel contention is

$\begin{align*} {\Omega _k}(\alpha ) = \sum\limits_{{F_i} \in hpH({F_k}) \cap hpL({F_k})} {I_k^{NC}({F_i},\alpha )} + {U_k}(\alpha ), \end{align*}$
where $U_k(\alpha)$ is also for the interferences of $hpH(F_k)$ and $hpL(F_k)$. Note that the interferences of flows in $hpH(F_k)$ are the same with (1) and (2), since the flows release packets periodically. But the flow $F_i$ ($F_i \in hpL(F_k)$) is delivered only once. In the worst case, its workload in the level-$k$ busy period is $\text{min}\{\alpha, c_i\}$. So
$\begin{align*} \begin{aligned} I_k^{CI}({F_i},\alpha ) = I_k^{NC}({F_i},\alpha )= \min (\min (\alpha ,{c_i}),\alpha - {c_k} + 1),\\ \forall\, {F_i} \in hpL({F_k}). \end{aligned} \end{align*}$
Then the pseudo upper bound $R^{ch}_k(H)$ can be derived based on (3).

For the delay due to transmission conflicts, similarly, besides the periodic flows in $hpH(F_k)$, the flows in $hpL(F_k)$ delivered only once will introduce $\Delta (k,i)$ to $R_k(H)$. So

$ \begin{align} \beta = &\ R_k^{ch}(H) +\sum\limits_{{F_i} \in hpH({F_k})} {\left\lceil {\frac{\beta }{{{t_i}(H)}}} \right\rceil \times \Delta (k,i)} \notag\\ &\ + \sum\limits_{{F_i} \in hpL({F_k})} {\Delta (k,i)}. \end{align}$ (5)
According to (5), the iterative algorithm is used to find the fixed $\beta$, i.e., $R_k(H)$.

2) Analyzing $R_k(L2H)$: The flow $F_k$ ($F_k \in {F}'$) is divided into two flows. The first flow $F_{kL}$ is delivered in the $L$ mode, and the second flow $F_{kH}$ is in the $H$ mode. We use $R^r_k(L)$ and $R^r_k(H)$ to denote the delays of $F_{kL}$ and $F_{kH}$, respectively, where $r$ means that the packet has passed through $r$ hops before the mode change, and $r \in [0,c_k-1]$. Correspondingly, $c_{kL}$ $=$ $r$ and $c_{kH} = c_k-r$. And priorities of $F_{kL}$ and $F_{kH}$ are assigned as $p_k$.

The calculation of $R^r_k(L)$ is the same with that of $R_k(L)$, since they are all in the stable network. But $R^r_k(H)$ is different from $R_k(H)$. According to our system model, packets released by $F_k$ in the network mode $H$ have higher priority than the packets of $F_{kH}$. Therefore, the delay contributed by these higher priority packets must be added to $R^r_k(H)$, i.e., $F_{kH}$ is interfered by $hpL(F_k)$, $hpH(F_k)$ and $\{F_k\}$ in the network mode $H$. From these, we can derive

$\begin{align*} &{\Omega _{kH}}(\alpha ) \\&\qquad = \sum\limits_{{F_i} \in hpH({F_k}) \cap hpL({F_k}) \cap \{ {F_k}\} }{I_{kH}^{NC}({F_i},\alpha )} + {U_{kH}}(\alpha ), \end{align*}$
where $U_{kH}$ is for $hpL(F_k)$, $hpH(F_k)$ and $\{F_k\}$. For the flow $F_{kH}$, $F_k$ releases higher priority packets periodically. The interference introduced by $F_k$ is the same with that by $hpH(F_k)$. So (1) and (2) also can be used to calculate it.

For the delay due to transmission conflicts, the packets released by $\{F_k\}$ must be considered. Then the actual end-to-end delay is shown as follows:

$\begin{align*} \beta =&\ R_{kH}^{ch}(H) + \sum\limits_{{F_i} \in hpH({F_k}) \cap \{ {F_k}\} } {\left\lceil {\frac{\beta }{{{t_i}(H)}}} \right\rceil \times \Delta (kH,i)} \\ &\ + \sum\limits_{{F_i} \in hpL({F_k})} {\Delta (kH,i)}. \end{align*}$
And $R^r_k(H)$ is also solved by the iterative algorithm.

The range of $r$ is from $0$ to $c_k-1$. If $r=0$, it means that the packet has been released but not been delivered before the network mode is changed to $H$. Thus, $c_{kL}=0$. This will cause the failure of the iterative algorithm. So if $\exists\, F_i$ and $p_i > p_k$, $\alpha$ starts with 1; otherwise, there are no interferences for $F_k$ and $R_k^r(L)=0$. If $r=c_k$, it means that the packet has been delivered to its destination in the $L$ network mode. So the delay of the packet is $R_k(L)$.

The delay of $F_k$ is the sum of $R^r_k(L)$ and $R^r_k(H)$. But different values of $r$ lead to different $R^r_k(L)$ and $R^r_k(H)$. Therefore, the upper bound of $F_k'$s delay is

$\begin{align*} {R_k}(L2H) = {\max _{r \in [0,{c_k} - 1]}}\{ R_k^r(L) + R_k^r(H)\} + C, \end{align*}$
where $C$ is the additional time introduced by the mode change (shown in Section III).

To sum up, if the flow $F_k$ satisfies $R_k(L) \le t_k(L)$, $R_k(H)$ $\le$ $t_k(H)$ and $R_k(L2H) \le t_k(L)$, then it is schedulable. In a flow set, if all the flows are schedulable, the flow set is schedulable. The calculation of our analysis is in pseudo polynomial time because our analysis is based on the iterative fixed-point algorithm.

Ⅴ. EVALUATION

Our approach is the first end-to-end delay analysis in mixed-criticality WirelessHART networks. There are no previous works to compare our analysis' performance. Therefore, we compare our analysis with simulations and a real testbed.

A. Simulations

In order to illustrate the applicability of our approach, for each parameter configuration, 100 test cases are generated randomly. For each test case, the gateway is placed at the center and other nodes are placed randomly in the playground area $A$. According to the suggestion in [24], the number of nodes $n$ and the playground area $A$ should satisfy

$\begin{align*} \frac{n}{A} = \frac{{2\pi }}{{{d^2}\sqrt {27} }}, \end{align*}$
where the transmitting range $d$ is set as $40$ m. Then each node connects to the nearest node, which must be in its transmitting range and have been connected to the gateway. If some nodes cannot connect to the gateway, their locations are generated randomly again.

The flow set $F$ contains $ 0.8 n $ flows. Other parameters are set as follows. We use the utilization $u$ ($u = \sum\nolimits_{\forall {F_i} \in {F}} {{c_i}}/ {{t_i}}$) to control the workload of the entire network,and UUniFast algorithm[25] is used to generate each flow's utilization $u_i$ ($u_i$ $=$ ${{c_i}}/ {{t_i}}$). The result generated by UUniFast algorithm follows a uniform distribution and is neither pessimistic,nor optimistic for the analysis. For the flow $F_i$,its criticality level is assigned randomly. If $\chi_i=H$,then ${t_i}(L) = {2^{\lceil {\log _2^{ti}} \rceil }}$ and ${t_i}(H)$ $=$ ${2^{\lfloor {\log _2^{ti}} \rfloor }}$; otherwise,${t_i}(L) = {2^{\lceil {\log _2^{ti}} \rceil }}$ and ${t_i}(H)=+ \infty $. The mode change duration $C$ is set as the maximum number of hops between any two nodes of the network. If one channel and one transmitter of each node are reserved to serve the mode change,the change command can be broadcast to all of nodes in the duration $C$. The fixed priority assignment follows the two classical algorithms[26]: 1) Deadline monotonic (DM),in which the flow with the shorter deadline is assigned the higher priority; 2) Proportional deadline monotonic (PD),in which the flow with the shorter subdeadline is assigned the higher priority. {Subdeadline} is defined for its deadline divided by the total number of its transmissions.

The mode change can occur at any time slot. So the simulation should list all cases. But for the complex state space, the execution time of simulations is unacceptable. So if the execution time exceeds $30$ minutes, the simulation is suspended and the maximum delay is chosen as the worst case end-to-end delay. We use {pessimism ratio} (the proportion of our analyzed delay to the maximum delay observed in simulations) and {acceptance ratio} (the percentage of flow sets that are schedulable) as the performance metrics.

Fig. 2 plots the pessimism ratios with different number of nodes. We set that m=12 and u=1. In order to make test cases simulated in an acceptable time, the number of nodes is only up to 110. From the figures, we can see that the 75th percentile of the pessimism ratios is less than 2.1 and 2.2 for DM and PD, respectively. And in [2], the result of the state-of-the-art analysis EDA for single-criticality networks is 1.5 and 1.6, respectively. Comparing with them, our analysis only introduces a small degree of pessimism, even through the mode change increases the complexity of the end-to-end delay analysis. Therefore, our analysis is highly effective.

Download:
Fig. 2 Pessimism ratio under varying network sizes with m = 12.

In order to evaluate the performance of our analysis for the larger scale networks in an acceptable time, we set $m=6$ and $u$ $=$ $1$. Fig. 3 shows the boxplots of the pessimism ratios under varying network sizes. From the experimental results, we know that our analysis is stable under different network sizes. Comparing with Fig. 2, Fig. 3 is more pessimistic. Because the less number of channels introduces more contentions, and the delay analysis is to consider the worst case scenario. So all of additional contentions are considered in the delay analysis, but not all of them appear in simulations. Therefore, the analysis with less channels is more pessimistic.

Download:
Fig. 3 Pessimism ratio under varying network sizes with m = 12.

We compare acceptance ratios of our analysis and simulations, and the utilization $u$ is increased to $3.2$. Fig. 4 shows the comparison, in which $AMC$ is our analysis for mixed-criticality networks and $SIM$ is the result of simulations. We observe that our results are close to those of simulations. Therefore, our analysis can be used to verify whether flows can meet their deadlines before implementing the real system.

Download:
Fig. 4 Acceptance ratio under varying utilizations with m = 6.

Comparing Fig. 4(a) and Fig. 4(b), we observe that the acceptance ratio of the policy PD is less than that of the policy DM. It is because that, comparing with the policy DM, the policy PD introduces more interferences for the flow with short path, which leads to longer delay. Similarly, all of interferences are considered in the delay analysis, but not all of them appear in simulations. So in Fig. 2 and Fig. 3, the analysis of PD is more pessimistic than that of DM.

B. The Real Testbed

We implement a real testbed that contains threes types of physical devices: the gateway device, routing devices and field devices. The gateway device manages the network and adopts a low power SoC (system of chip) AT91RM9200 and a CC2420 transceiver chip. The routing device is implemented on a MSP430 and a CC2420. The field device is equipped with a temperature and humidity sensor SHT15 besides a MSP430 and a CC2420. Our testbed supports the IEEE 802.15.4 protocol, which is the physical and MAC (medium access control) layers of WirelessHART networks, and an improved WirelessHART network according to our requirements. The improved WirelessHART implements the specific requirements in the application layer, and it is compatible with the original WirelessHART. Channel 23 is used to broadcast mode change messages and configuration messages. Six schedulable channels are 15$-$20. Additionally, six devices are configured as sniffers to monitor packets transmitted on the six channels. Then the sniffed packet with a timestamp is sent to a PC via a 8-port RS-232 PCI express serial board.

Fig. 5 shows our testbed. The network is deployed in a building. For each parameter configuration, 100 test cases are implemented. The generation of configurations is the same as in simulations. The configuration message is sent to devices via the gateway. Fig. 6 shows pessimism ratios in a certain scope under different parameters. The point of the pessimism ratio 1.4 reports the number of test cases, whose pessimism ratios are between $1.4$ and $1.6$. When the utilization is set as 1 and the number of channels is 12, comparing with PD and DM, our average pessimism ratio of 100 test cases is about 2.5 and 2.4, respectively. The result is more pessimistic than simulations. It is because that real cases only cover a little state space. The delay observed in the real testbed is not the worst case delay, while our analysis focuses on the worst case. So for the end-to-end delay, our analysis approach is more reliable than real tests.

Download:
Fig. 5 Our testbed.

Download:
Fig. 6 Pessimism ratio on the testbed
VI. CONCLUSION

Nowadays, multiple criticality levels co-exist in real-life wireless network. But previous works only focus on the single criticality network. We propose an end-to-end delay analysis approach for fixed priority scheduling in mixed criticality WirelessHART networks, which can be used to determine whether all flows can be delivered to destinations within their deadlines. In evaluations, we compare our analysis results with simulations and a testbed. The results show that the pessimism of our analysis is acceptable and reliable.

In the further work, we will propose a fixed priority assignment algorithm based on our delay analysis, and a revision for the dynamic priority assignment will be designed to deal with the dynamic systems.

References
[1] WirelessHART specificatioin[Online], available: September 30, 2014
[2] Saifullah A, Xu Y, Lu C Y, Chen Y X. End-to-end delay analysis for fixed priority scheduling in WirelessHART networks. In:Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium. Chicago, United States:IEEE, 2011. 13-22
[3] Saifullah A, Xu Y, Lu C Y, Chen Y X. Real-time scheduling for WirelessHART networks. In:Proceedings of the 31st IEEE Real-Time Systems Symposium. San Diego, United States:IEEE, 2010. 150-159
[4] Saifullah A, Xu Y, Lu C Y, Chen Y X. Priority assignment for real-time flows inWirelessHART networks. In:Proceedings of the 23rd Euromicro Conference on Real-Time Systems. Porto, Portugal:IEEE, 2011. 35-44
[5] Soldati P, Zhang H B, Johansson M. Deadline-constrained transmission scheduling and data evacuation in WirelessHART networks. In:Proceedings of the 10th European Control Conference. Budapest, Hungary:IEEE, 2009. 1-7
[6] Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In:Proceedings of the 28th IEEE Real-Time System Symposium. Tucson, United States:IEEE, 2007. 239-243
[7] de Niz D, Lakshmanan K, Rajkumar R. On the scheduling of mixedcriticality real-time task sets. In:Proceedings of the 30th IEEE Real-Time Systems Symposium. Washington, United States:IEEE, 2009. 291-300
[8] Baruah S, Li H H, Stougie L. Towards the design of certifiable mixed-criticality systems. In:Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium. Stockholm, Sweden:IEEE, 2010. 13-22
[9] Baruah S, Bonifaci V, D'Angelo G, Li H H, Marchietti-Spaccamela A, Megow N, Stougie L. Scheduling real-time mixed-criticality jobs. IEEE Transactions on Computers, 2012, 61(8):1140-1152
[10] Li H H, Baruah S. Global mixed-criticality scheduling on multiprocessors. In:Proceedings of the 24th Euromicro Conference on Real-Time Systems. Pisa, Italy:IEEE, 2012. 166-175
[11] Baruah S K, Bonifaci V, D'Angelo G, Marchietti-Spaccamela A, Van Der Ster S, Stougie L. Mixed-criticality scheduling of sporadic task systems. In:Proceedings of the 2011 European Conference on Algorithms. Berlin, Germany:Springer, 2011. 555-566
[12] Guan N, Ekberg P, Stigge M, Wang Y. Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In:Proceedings of the 32nd IEEE Real-Time Systems Symposium. Vienna, Austria:IEEE, 2011. 13-23
[13] Huang H M, Gill C, Lu C Y. Implementation and evaluation of mixedcriticality scheduling approaches for sporadic tasks. ACM Transactions on Embedded Computing Systems, 2014, 13(4):1-25
[14] Tobuschat S, Axer P, Ernst R, Diemer J. IDAMC:a NoC for mixed criticality systems. In:Proceedings of the 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Taipei, China:IEEE, 2013. 149-156
[15] Diemer J, Ernst R. Back suction:service guarantees for latency-sensitive on-chip networks. In:Proceedings of the 4th ACM/IEEE International Symposium on Networks-on-Chip. Grenoble, France:IEEE, 2010. 155-162
[16] Audsley N. Memory architectures for NoC-based real-time mixed criticality systems. In:Proceedings of the 1st Workshop on Mixed Criticality Systems. Vancouver, Canada:IEEE, 2013. 37-42
[17] Burns A, Davis R I. Mixed criticality on controller area network. In:Proceedings of the 25th Euromicro Conference on Real-Time Systems. Paris, France:IEEE, 2013. 125-134
[18] Herber C, Richter A, Rauchfuss H, Herkersdorf A. Spatial and temporal isolation of virtual CAN controllers. In:Proceedings of the 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Taipei, China:IEEE, 2013. 1-7
[19] Tamas-Selicean D, Pop P, Steiner W. Synthesis of communication schedulers for TTEthernet-based mixed-criticality systems. In:Proceedings of the 9th International Conference on Hardware/software Codesign and System Synthesis. New York, United States:IEEE, 2011. 473-482
[20] Suethanuwong E. Scheduling time-triggered traffic in TTEthernet systems. In:Proceedings of the 17th Conference on Emerging Technologies and Factory Automation. Krakow, Poland:IEEE, 2012. 1-4
[21] Steiner W. Synthesis of static communication schedules for mixedcriticality systems. In:Proceedings of the 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshop. Newport Beach, United States:IEEE, 2011. 11-18
[22] Addisu A, George L, Sciandra V, Agueh M. Mixed criticality scheduling applied to JPEG2000 video streaming over wireless multimedia sensor networks. In:Proceedings of the 1st Workshop on Mixed Criticality Systems. Vancouver, Canada:IEEE, 2013. 1-6
[23] Joseph M, Pandya P. Finding response times in a real-time system. The Computer Journal, 1986, 29(5):390-395
[24] Camilo T, Silva J S, Rodrigues A, Boavida F. Gensen:a topology generator for real wireless sensor networks deployment. In:Proceedings of the 2007 International Conference on Software Technologies for Embedded and Ubiquitous Systems. Santorini Island, Greece:Springer, 2007. 436-445
[25] Bini E, Buttazzo C C. Measuring the performance of schedulability tests. Real-Time Systems, 2005, 30(1):129-154
[26] Liu J. Real-Time Systems. United States:Prentice Hall, 2000. 42-49