arXiv CSopen access

Scheduling Mechanisms in Wireless Sensor-Actuator Networks for Multi-rate Periodic Control in Industry 4.0

arXiv:2605.30520v1 [cs.NI] 28 May 2026

© 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

2

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

Scheduling Mechanisms in Wireless Sensor-Actuator Networks for Multi-rate Periodic Control in Industry 4.0 Dingwen Yuan, Luis F. Abanto-Leon, and Matthias Hollick Abstract— This paper investigates scheduling strategies for wireless sensor-actuator networks (WSANs) in Industry 4.0 scenarios. In particular, we address the problem of real-time scheduling for multi-rate control systems by proposing a novel framework. Our framework features four strategies that improve reliability, schedulability and execution time, and reduce communication and storage costs. Two-phase scheduling is our first strategy, devised to improve communication reliability. Our second strategy is the least-laxity-first with remaining conflicts (LLFRC) scheduling algorithm, which has high schedulability and affordable execution time. LLF-RC also keeps the maximum queue length at a moderate level, making it suitable for storage-constrained devices. Our third and fourth strategies are opportunistic aggregation and repetitive scheduling. Opportunistic aggregation performs simple and effective packet aggregation, enhancing schedulability by up to 97% and reducing execution time by up to 29%, in our simulation. Repetitive scheduling has negligible execution time, and contributes to minimize communication and storage costs. It reduces the maximum execution time by 92% and the maximum communication and storage cost by 99%, in our simulation. We compare our proposed framework against existing approaches, and evaluate the advantages of our strategies in realistic scenarios. Index Terms— TDMA, scheduling, opportunistic aggregation, periodic control, multi-rate systems, repetitive scheduling, wireless sensor-actuator networks.

I. I NTRODUCTION Sensor Actuator Industry 4.0 has become a major research focus, Controller promising to revolutionize the industrial landscape by Relay enhancing efficiency, productivity, adaptability, resilience, – Wireless link and overall process performance. A key aspect of this transformation is the shift from wired communication Fig. 1: WSAN consisting of one controller and multiple technologies, such as Fieldbus and real-time Ethernet [1], sensors, actuators, and relays. [2], to wireless alternatives, including time-slotted channel hopping (TSCH) [3], WirelessHART [4], and ISA100.11a As technology advances, industrial processes become [5]. Wireless connectivity overcomes the technical and increasingly demanding and sophisticated. The most chaleconomic constraints of wired systems, enabling rapid facillenging scenarios will require complex automation relyity reconfiguration, reduced deployment and maintenance ing on numerous sensors and actuators communicating costs, and support for mobility-driven applications such as wirelessly, as illustrated in Fig. 1. Such a collection of mobile robots [6], thereby paving the way for autonomous, interconnected devices, known as wireless sensor-actuator smarter factories. network (WSAN), forms the communication backbone for While wireless technologies offer substantial advantages, industrial processes. they also introduce challenges. Unlike the physical isoA cornerstone of industrial automation is real-time lation of wired networks, wireless systems share the periodic control, implemented through control loops that propagation medium, leading to potential interference and continuously sense, compute, and actuate at fixed inreliability concerns. Wireless solutions also tend to have tervals, as shown in Fig. 2. Particularly, the network lower throughput and higher latency due to retransmiscontroller computes and broadcasts the data flow schedule sions, power limitation, and bandwidth constraints. to all motes (sensors, relays, and actuators) via gateways. This work has been supported in part by the German Science Foun- Control packets (controller → actuators) and sensor packdation (DFG) within the project CRUST (Grant 503199853) and by the LOEWE initiative (Hesse, Germany) within the emergenCITY ets (sensors → controller) are then transmitted according center [LOEWE/1/12/519/03/05.001(0016)/72]. to this schedule, often relayed through relays.

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

The heterogeneity of data rates produced by control loops in WSANs significantly increases the risk of packet collisions and complicate the wireless data flow scheduling, ultimately impacting communication performance. Therefore, ensuring reliable, real-time communication is critical. At the same time, there is a pressing need for scheduling algorithms that are not only efficient but also lightweight, minimizing both storage requirements and communication overhead to maintain the scalability of the network. Storage is particularly vital due to the memory constraints of sensors and actuators, while communication costs impact time and frequency resources. These challenges highlight the need for lightweight and efficient scheduling strategies. Based on the above motivation, it is essential to design a WSAN scheduling framework that ensures high schedulability, high reliability, low execution time, low storage constraints, and low communication overhead. To the best of our knowledge, the scheduling of WSANs for multi-rate periodic control systems remains an open problem. Motivated by this, the present work introduces a framework with several novel strategies to meet these objectives. Our contributions are summarized below: • We propose a centralized time-division multiple access

(TDMA)-based WSAN scheduling framework, drawing inspiration from multiprocessor scheduling principles. It adapts these principles to address the unique challenges of WSANs. Our framework includes two-phase (2P) scheduling, which is a novel idea that improves reliability compared to traditional scheduling, referred to as onephase (1P) scheduling in this paper. We demonstrate analytically, and through simulations that 2P scheduling has higher reliability, albeit with an increased delay compared to 1P scheduling. • We propose the least-laxity-first with remaining constraints (LLF-RC) algorithm, which improves the scheduling performance by accounting for laxity to scheduling deadline and link bottleneck. Through extensive simulations, we demonstrate that LLF-RC has higher schedulability and lower execution time compared to other scheduling algorithms. • We propose opportunistic aggregation (OA), a mechanism that interfaces seamlessly with any scheduling algorithm, and significantly increases the schedulability of WSANs. • We propose repetitive scheduling (RS), a mechanism that can be integrated with any scheduling algorithm on condition that harmonic periods are employed. It is very effective in reducing communication and storage costs, with minimal penalty to schedulability. These characteristics make RS ideal for resource-constrained wireless nodes. • We adapt existing scheduling algorithms to work within the framework we propose in order to perform a fair comparison. This paper is organized as follows: Section II reviews related work on wireless scheduling algorithms. Section III details the system model, including topology, communica-

3

tion, and routing. Section IV introduces our 2P scheduling framework, along with the LLF-RC algorithm, OA, and RS. Section V adapts various multiprocessor scheduling algorithms to our framework. Section VI discusses simulation results, Section VII discusses applicability to largescale real-world WSANs and Section VIII presents our conclusions. Notation: In this paper, Z+ denotes the set of positive integers. The functions max {S} and min {S} return the maximum and minimum value of set S, respectively. The product operator is denoted by Π (·) and the logarithm in base 10 of a real number x > 0 is represented by log10 (x). II. R ELATED W ORK The most prominent WSAN protocols, including TSCH [3], WirelessHART [4], and ISA100.11a [5], build on the IEEE 802.15.4 standard [22], which uses TDMA across multiple channels. While similar at the physical layer, they differ in channel reuse policies. Specifically, TSCH allows it, whereas WirelessHART and ISA100.11a do not. All three protocols allow custom scheduling designs, which have led to a broad literature on scheduling algorithms. Scheduling approaches can be categorized as centralized, distributed, or autonomous. Centralized algorithms (e.g., [11], [13], [23]) rely on a controller with global knowledge. Distributed solutions (e.g., [24]–[29]) requires individual nodes to compute partial schedules by exchanging information with neighbors. Autonomous methods (e.g., [30], [31]) let nodes derive schedules locally, often based on routing information. Centralized algorithms excel at optimizing periodic traffic, while distributed and autonomous algorithms are more resilient to changes in network topology and traffic patterns. In the following, we revisit the most relevant works. Early works in networked control, such as [9], addressed deadline-aware scheduling in cell-based networks, combining earliest deadline first (EDF) scheduling within cells and priority-based inter-cell coordination. Unused slots from hard-deadline flows were opportunistically reassigned to aperiodic traffic. Similarly, real-time query scheduling (RTQS) [10] tackled scheduling over arbitrary interference graphs, introducing three variants, namely, preemptive (PQS), non-preemptive (NQS), and slack stealing query scheduling (SSQ), that balanced throughput and deadline compliance. Closer to our focus, a large body of work has investigated scheduling multiple real-time flows, where each flow carries deadline constraints [11], [12], [14]–[21], [31]–[33]. Specifically, [11] mapped control loops to flows, proving WirelessHART scheduling is NP-hard and proposing an optimal branch-and-bound method. However, its computational complexity limited scalability. The lower-complexity conflict-aware least-laxity-first (CLLF) algorithm was subsequently introduced, offering a better performancecomplexity tradeoff than [11], and significantly outperforming deadline monotonic (DM) and proportional deadline monotonic (PDM) algorithms. Later, [12] proposed

4

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

Fig. 2: Block diagram of WSAN and control loop. Control loops form the core of periodic real-time systems, continuously executing sensing, computation, and actuation cycles. Industrial processes often involve multiple loops with heterogeneous rates, where feedback controllers manage actuators. A network controller schedules the wireless network according to each loop’s timing requirements, which is the focus of this paper. We propose novel scheduling algorithms LLF-RC, opportunistic aggregation and repetitive scheduling, which work in synergy and significantly improve network schedulability, algorithm execution time, and memory and communication overhead. TABLE I: Categorization of relevant related work Approach Type Sch.

Use case

Algorithm

Optional features

Spatial reuse

Number of flows

Traffic

Deadline

Performance

Periodic Aperiodic Hard Soft Throughput Reliability Schedulability

St

[9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]

C D C C C C C A C A C C C

1P 1P 1P 1P 1P 1P 1P 1P 1P 1P 1P 1P 1P

Generic EDF N/A Generic RTQS & DCQS PQS, NQS, SSQ Industry CLLF N/A Industry PC-LLF N/A Industry Matching and coloring N/A Industry SPRF N/A Industry HSA N/A Generic SRCA N/A Industry CBPF N/A Industry SmarTiSCH N/A Industry AdaptiveHART N/A Industry RSP N/A Industry ASAP N/A

Yes Yes No Yes Yes Yes No Yes Yes Yes No Yes No

Single Single Multiple Multiple Multiple Multiple Multiple Single Single Single Few Many Many

Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes

Yes No No No No No No No No No No No No

Yes Yes Yes Yes Yes Yes Yes No No No Yes Yes Yes

Yes No No No No No No Yes Yes Yes No No No

High High Medium Low Low Low Low Low Very high Low High High High

Medium High High High High High High High High High High High High

Medium Medium Very high High High High High Medium Very high High High Very high Medium

M H H H M H H M Ver H M H H

Proposed Proposed Proposed Proposed

C C C C

2P 2P 2P 2P

Industry Industry Industry Industry

No No No No

Multiple Multiple Multiple Multiple

Yes Yes Yes Yes

No No No No

Yes Yes Yes Yes

No No No No

Low High Low High

High High High High

Medium High Medium High

H H

C: Centralized

D: Distributed

LLF-RC LLF-RC LLF-RC LLF-RC

OA RS OA+RS

A: Autonomous

path-collision aware least-laxity-first (PC-LLF), prioritiz- enhancing adaptability, AdaptiveHART [19] dynamically ing path-level conflicts over next-link conflicts, achieving adjusted scheduling and transmission priorities in response higher schedulability than CLLF. Besides, [32] analyzed to changing traffic conditions. Unlike traditional static end-to-end delays for fixed-priority DM and PDM, while WirelessHART, it optimized time slot allocation, reduc[33] presented worst-case delay analysis and a heuristic to ing latency and packet loss while improving resource minimize scheduling overhead. utilization. Similarly, resource sharing path (RSP) [20] Traffic-aware scheduling algorithm (TASA) [13] min- enhanced efficiency by allowing flows to share paths imized slots through matching and coloring, inspiring without interference, minimizing delays and contention. scheduling of periodic real-time flow (SPRF) [14], which For finer-grained adaptation, adaptation of slot-size and prioritized periodic flows but incurred high computation aggregation of packets (ASAP) [21] dynamically adjusted slot sizes and aggregateed smaller packets when feasible. overhead due to repeated matchings. By prioritizing critical data and reducing overhead, ASAP Other works tackled flow delay minimization. For inallowed balancing efficiency and reliability, making it stance, hop-wise scheduling algorithm (HSA) [15] modeled particularly effective in highly dynamic environments. scheduling as a multi-dimensional conflict graph problem, Together, these algorithms, CBPF, SmarTiSCH, Adaptivesolved via approximations but at growing computational HART, RSP, and ASAP, demonstrated a progression from cost. In contrast, slot reallocation for collision avoidance collision mitigation to adaptive scheduling, addressing key (SRCA) algorithm [16] autonomously updated schedules challenges in real-time industrial wireless networks. at each node using parent-child relations. By preemptively changing a child node’s slot after a successful transmission, While settings like vehicular networks and smart grids SRCA avoided future collisions, boosting reliability. share some similarities with industrial WSANs, they often Efforts like contention-based proportional fairness differ in complexity and specific requirements. These (CBPF) [17] applied convex optimization to reduce colli- environments may lack actuators, omit multi-rate control sions, while SmarTiSCH [18] enabled passive interference loops, or impose less stringent demands. Nevertheless, we detection without additional control overhead. Further revisit relevant works in these domains to provide broader

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

context. In vehicular safety networks, vehicles broadcast messages to share location and maneuver data. Several studies have explored such scenarios [34]–[37], where scheduling plays a crucial role in ensuring high reliability and schedulability. While received messages may influence actuator control within vehicles, resembling certain aspects of WSAN, scheduling is typically centralized at base stations with substantially greater computational resources than industrial gateways. Moreover, safety-critical vehicular networks operate as single-hop systems to minimize latency, eliminating the need for onboard scheduling storage. Based on these facts, execution time and storage cost are less critical considerations compared to WSANs. Additionally, unlike WSANs, vehicle controllers and actuators usually connect via wired interfaces, reducing failure points and improving overall reliability. Smart grids employ WSANs under stringent operational constraints, comparable to industrial settings. In these scenarios, WSANs are used to monitor and control critical grid infrastructure, enabling seamless communication between distributed nodes for fault detection, load balancing, and real-time control. As such, effective scheduling mechanisms are essential for ensuring reliability and performance [38]–[40]. However, due to the critical nature of smart grids, wireless technology is typically limited to small subnetworks, while the most critical functions are still predominantly managed through wired connections. While inspired by industrial applications, our proposed framework addresses challenges not tackled by prior works, including those in vehicular and smart grid contexts. For clarity, Table I summarizes the discussed studies, highlighting their advantages and disadvantages. Other relevant works worth mentioning include [41]–[45].

5

where Ptx is the transmit power. Additionally, the signalto-noise ratio (SNR) is defined as γ = P (d) − Pn ,

(3)

where Pn is the noise floor. Furthermore, the symbol error rate (SER) is expressed as ( ) β1 (γ − β2 ) 1 √ SER = erfc , (4) 2 2 based on the empirically determined TOSSIM model [50], which is employed to characterize the packet reception rate (PRR), given by PRR = (1 − SER)

2L

,

(5)

where L is the packet length measured in bytes. B. Network Topology Model We model the topology of the wireless network as an undirected simple graph G = (V, E), meaning the graph has no loops nor parallel edges. Set V indexes the nodes while set E indexes the undirected edges, representing the links between every pair of nodes. The nodes in the graph can represent gateways or motes. A mote can be a sensor, an actuator, or a pure relay, with the ability to relay packets. Thus, the set of nodes V is defined as V = N ∪M, where N is the set of motes, and M is the set of gateways. Specifically, every edge e ∈ E has a link quality given by the PRR, defined in (5) and denoted by PRR(e) ∈ [0, 1].

C. Communication Model In the following, we define relevant aspects of the communication model. Multiplexing and duplexing. We represent the communication model as a discrete-time system as we rely on TDMA. We assume that a unit time is equal to the III. S YSTEM M ODEL duration of a slot, and that transmitting a packet via This section introduces the link quality, network topol- a link requires one slot. Also, each gateway or mote is ogy, communication, and routing models for the consid- equipped with a half-duplex radio that cannot transmit ered WSAN. and receive simultaneously. Link. We assume that gateways are connected with perfect link quality and zero delay. This is a realistic A. Link Quality Model Simulating link quality requires the use a realistic radio assumption, since gateways in industrial settings are access propagation model. Therefore, we employ the log-normal points connected via fast and redundant wired links. Howpath-loss model due to its accuracy to depict large-scale ever, the link between a gateway and a mote, or between fading, which is typical in industrial environments [46]– two motes, is assumed to be imperfect because it is [48]. The model, expressed in decibels (dB), is defined as wireless. Specifically, the link e between two wireless nodes is viable only if its quality is greater than a threshold Γth , ( ) d PL(d) = PL(d0 ) + 10η · log10 + Xσ , (1) i.e. PRR(e) ≥ Γth . In addition, spatial reuse of channels d0 is disabled as in WirelessHART, facilitating interference where PL(d) is the path-loss of the signal strength at mitigation by preventing concurrent transmissions over distance d, PL(d0 ) is the path-loss at reference distance the same channels. Flow. We consider a system with multiple control loops. d0 , η is the path-loss exponent, and Xσ is a zero-mean The controllers governing the control loops are located at Gaussian random variable, which represents shadowing, the gateways, and the communication of a loop is called a and has standard deviation σ [49]. The received power flow. Each flow is activated periodically, and has a sensor P (d) at distance d is given by and an actuator. In particular, the sensor samples, and P (d) = Ptx − PL(d), (2) transmits at times k · pf , where k = {0, 1, 2, ...}, and pf

6

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

π0sc sensor

πisc sc πn−1

π0ca any controller

πjca

actuator

ca πm−1

Fig. 3: A flow from sensor to actuator with n sc-paths sc ca π0sc , . . . , πn−1 and m ca-paths π0ca , . . . , πm−1 . The number of paths n and m are not necessarily equal. is the period of flow f . A flow can have multiple routing paths, each starting at a sensor and ending at an actuator, going through a controller as shown in Fig. 3. Specifically, πisc , i = {0, . . . , n − 1}, represents the i-th sensor-tocontroller path (sc-path) whereas πjca , j = {0, . . . , m − 1}, represents the j-th controller-to-actuator path (ca-path). In addition, n and m denote the number of sa- and capaths, respectively. Flow delay. We employ the constant network-induced delay model [51]. In this model, there is no need to differentiate the sensor-to-controller delay dsc and the controller-to-actuator delay dca , if the control laws are time-invariant, which is true for our system. Hence, we use the sum flow delay d = dsc + dca for analyzing the communication schedulability. The flow delay needs to satisfy d ≤ dmax , where dmax is the maximum allowable delay, determined by stability analysis and feedback loop performance. Flow reliability. To guarantee stability and satisfactory performance for a feedback loop, the flow reliability rf of flow f needs to be greater than a lower bound rmin , i.e. rf ≥ rmin . For control applications, usually rmin does not need to be as high as in monitoring applications [51], [52]. D. Routing Model We consider multi-path routing for flow forwarding. In particular, when the reliability requirement of a flow f cannot be satisfied by a single sensor-to-actuator path (sa-path), i.e., rf ≤ rmin , multi-path routing helps to address this limitation. A flow f is split into two parts: one comprises the paths starting at the sensor and ending at a controller, and the other comprises the paths starting at a controller and ending at the actuator. Specifically, a flow f is divided into a sensor-to-controller subflow (sc-flow), denoted by f sc , and a controller-to-actuator subflow (caflow), denoted by f ca . The paths for f sc are called sc-paths, while the paths for f ca are called ca-paths, as shown in Fig. 3. When the sensor data arrives at the controller through an sc-path, the control algorithm is ready to be executed. Once the control algorithm is executed, the output is ready to be sent to the actuator via a ca-path. IV. P ROPOSED S CHEDULING F RAMEWORK In this section, we first present our proposed framework. Then, we introduce 2P scheduling and LLF-RC algorithm, devised to improve reliability and schedulability, respectively. In addition, we present OA (Opportunistic Aggregation) and RS (Repetitive Scheduling). Specifically,

OA improves schedulability, whereas RS reduces execution time, and communication and storage costs. In the end, we discuss the implications of applying the scheduling framework to industrial networks. A. Proposed Scheduling Framework Our proposed scheduling framework draws inspiration from the multiprocessor scheduling literature. Specifically, multiprocessor scheduling deals with the problem of assigning a set of tasks to a number of processors such that each task meets a given deadline. In particular, if there are C processors, the maximum number of tasks that can be simultaneously supported is C. Inspired by this, our TDMA scheduling problem can be formulated as a multiprocessor scheduling problem, where tasks can be of different granularity. This means that a task is mapped to a flow, an sc- or ca-path, or a link, while a processor is mapped to to an available frequency channel. Thus, given C channels, TDMA scheduling allows at most C transmissions in parallel if spatial reuse is disabled, as assumed in this work. Our TDMA scheduling framework has one constraint that makes it different from multiprocessor scheduling: any two links scheduled in the same slot cannot be in primary conflict [53], meaning the links cannot share a common node1 . There are two types of algorithms in the multiprocessor scheduling literature: partitioned and global. The former assigns a task statically to a processor, while the latter allows tasks to migrate freely between processors [54]. In our framework, we adopt global scheduling due to its better performance in deadline satisfaction. Making an analogy to multiprocessor scheduling, task migration is equivalent to scheduling two consecutive transmissions on two different channels, as a processor is mapped to a channel. Therefore, the cost of performing task migration is negligible, as a transceiver can receive a packet on one channel, and send the packet on another channel with almost no additional cost. Algorithm 1, summarizes the proposed scheduling framework, which we explain in more detail in the following. First, a schedulability test is performed (see line 1), which consists of a deadline check and a utilization check. Deadline check. The deadline of a flow cannot be smaller than the minimum flow delay d2P . Utilization check. The utilization of a flow f is defined hops(f ) as uf = . Specifically, hops(f ) is the number of pf transmissions needed for each activation of flow f , and pf is the period of flow f . The total utilization of all flows∑ should not be larger than the channel count C [55], i.e., f uf ≤ C, which is a necessary condition for the existence of a feasible scheduling. Note that we do not apply this check when OA is employed. If the schedulability test is passed (see line 2), scheduling is attempted (see lines 4-6) assuming that for one activation of a flow, the transmissions on the ca-flow are not 1 This constraint is relaxed if OA is employed, as explained in Section IV-D.

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

Algorithm 1: Proposed scheduling framework Input: C: Number of available channels B: Maximum queue length Output: H: Scheduling table 1 Perform necessary schedulability test, including deadline check and utilization check; 2 if schedulability test is passed then 3 Set the hyperperiod length to the least common multiple of all flow periods, H = lcm{pf : f ∈ all flows}; 4 for i = 0 to H − 1 do 5 Define the set Ji with all released transmissions in slot i, whose receiver queue length is lower than B, and ordered by priority; 6 Perform a scheduling Hi with at most C non-conflicting transmissions from Ji , in descending order of priority; 7 if deadline is missed then 8 return H = ∅; if scheduling is complete then { }i return H = Hj j=0 ;

9 10 11 12

else

return H = ∅;

7

control algorithm only after the transmissions on all or some sc-paths have arrived to the controller by a given time. Then, the controller output is sent on all ca-paths, as shown in Fig. 4a. On the contrary, 1P scheduling manages the communication of each sa-path independently, without synchronization of the controller, as shown in Fig. 4b. Specifically, each sa-path is composed of a sc-path and a ca-path, i.e., πi = πisc ∪ πica . The sa-path concept is not needed in 2P scheduling, and bears no meaning when the number of sc-paths and ca-paths are different. However, we keep the concept of sa-path in 2P scheduling only for consistency with 1P scheduling. In 2P scheduling, the gateway end-points of the two paths may be different, since we assume full connectivity between gateways. path 1

sensor-to-controller transmissions

path 2

sensor-to-controller transmissions

controller-to-actuator transmissions control algorithm controller-to-actuator transmissions

time

(a) 2P scheduling path 1

sensor-to-controller transmissions

path 2

sensor-to-controller transmissions

control algorithm

control controller-to-actuator transmissions algorithm controller-to-actuator transmissions

time

The maximum queue length B is, in practice, related to the RAM size. Also, lcm {S} represents the least common multiple operation of a set S whereas H = ∅ indicates that a feasible scheduling was not found.

(b) 1P scheduling

Fig. 4: 2P scheduling and 1P scheduling are depicted for a WSAN with two gateways.

Assuming that a flow has n sa-paths, denoted by released until all transmissions on the sc-flow are finished. If the scheduling is complete, then a feasible solution has π0 , π1 , ..., πn−1 , we will show that 2P scheduling provides been found (see lines 9-10). If the scheduling has not been higher communication reliability than 1P scheduling. Theorem 1: Given a flow with n ≥ 1 sa-paths, the achieved by the deadline, the scheduling is infeasible (see lines 7-8). Although it is theoretically possible for a control end-to-end communication reliability of 2P scheduling loop to have a deadline larger than the period, we impose is greater than or equal to that of 1P scheduling, i.e., that the deadline is not larger than the period, because r2P ≥ r1P . Proof: The reader is referred to Appendix I. of the following two reasons. • If a control loop is feasible for a deadline larger than the r0sc r0ca period, it is also feasible for a larger period (see Fig. 7 of [51] which shows the relation between stability region, sensor controller actuator risc rica period, and delay). sc ca rn−1 rn−1 • A set of synchronized periodic tasks is schedulable if it is feasible for a hyperperiod, which is defined as the least common multiple of all task periods [56]. Otherwise, Fig. 5: A flow with n sa-paths π0 , . . . , πi , ..., πn−1 , where sc ca even though the scheduling may still be periodic from ri and ri are the reliabilities of the sc-path and the casome point in time, the point cannot be accurately path of the sa-path πi , respectively. determined [57]. To illustrate the difference in flow reliability between Remark: Our proposed framework can be applied with 1P scheduling and 2P scheduling, we consider the special any scheduling algorithm. The main difference is how case in which all sc- and ca-paths have the same reliability released transmissions are prioritized (see lines 5-6). In r. We illustrate the difference r2P − r1P = [1 − (1 − particular, each scheduling algorithm handles released n 2 r) ] − [1 − (1 − r2 )n ] in Fig. 6, varying r ∈ [0, 1] transmissions in a different way, resulting in different and n ∈ {2 . . . 10}. We observe that as the number of performances. paths increases, the difference in reliability changes. In particular, the difference increases for smaller values of B. Proposed 2P Scheduling r, whereas it decreases for larger values of r. Despite 2P Fig. 4 illustrates 1P scheduling and the proposed 2P scheduling being more reliable than 1P scheduling, the scheduling. In particular, 2P scheduling executes the minimum delay of the former is larger, as shown next.

8

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

difference in flow reliability

0.5 ← n = 10 0.4 0.3 0.2 0.1 ←n=2 0

0

0.2

0.4

0.6

0.8

1

path reliability r

Fig. 6: Difference in flow reliability, r2P − r1P , showing that 2P scheduling outperforms 1P scheduling.

Theorem 2: Given the same multi-path routing of a flow, the minimum end-to-end flow delay of 2P scheduling is greater than or equal to that of 1P scheduling, i.e., d2P ≥ d1P . Proof: The reader is referred to Appendix II. Remark: Although scheduling feasibility is related to both reliability (see Theorem 1) and delay (see Theorem 2), reliability is more relevant when deadlines are not overly tight, especially in control applications such as our case. In particular, if the scheduling achieves a delay within the required deadline, it fulfills the control objectives without affecting performance. C. Proposed LLF-RC Algorithm The least-laxity-first (LLF) algorithm was developed in [58], being its core idea the prioritization of jobs with smaller laxity. We propose the LLF-RC algorithm, which extends LLF’s idea by prioritizing flows based on the number of remaining conflicts when laxities are equal. In particular, the laxity a(·) of a released transmission τ is defined as its absolute deadline dabs (τ ) minus the current time t, as shown below a(τ ) = dabs (τ ) − t.

(6)

The absolute deadline of a released transmission τ is computed as the absolute deadline of the k-th activation x of path dpath abs (πi , k) minus the number of hops ahead on that path, i.e., nahead (πix ). Mathematically, we express it as x x dabs (τ ) = dpath abs (πi , k) − nahead (πi ) x x = k · pf + dpath rel (πi ) − 1 − nahead (πi ),

(7)

where x ∈ {sc, ca} and pf is the flow period. The relative x path deadline dpath rel (πi ) for sc- and ca-paths are defined below sc flow ca dpath rel (πi ) = drel (f ) − max{hops(πj )},

(8)

ca flow dpath rel (πi ) = drel (f ).

(9)

j

If two released transmissions have the same laxity, LLFRC assigns a higher priority to the transmission that has a larger number of remaining conflicting transmissions. The reason is that such links are likely to become bottlenecks, which may impair transmission parallelism [45]. We denote the number of remaining conflicting transmissions by nrem (τ ), and define it as the total number of unscheduled transmissions in the set of conflicting links of τ . The set of conflicting links of τ is composed of all links that share at least one node with the link of τ , including the link of τ itself. To illustrate LLF-RC algorithm, we provide an example in Fig. 7. We assume a network with 13 motes and 2 gateways. In particular, the motes consist of 2 sensors denoted by s0 , s1 ; 2 actuators denoted by a0 , a1 ; and 9 relays denoted by r0 , . . . , r8 . The gateways are denoted by g0 , g1 . There are two scheduled flows, f0 (from sensor s0 to actuator a0 ) and f1 (from sensor s1 to actuator a1 ). Here, sc ca sc ca f0 has two sa-paths (π00 = π00 ∪ π00 and π01 = π01 ∪ π01 ), sc ca whereas f1 has one sa-path (π10 = π10 ∪ π10 ). The periods and deadlines of f0 and f1 are p0 = 10, d0 = 10 and p1 = 20, d1 = 9, respectively. Also, two channels are available, i.e., C = 2. s0

r0

r1

r2

s1

r3

g0

r4

g1

r5

a1

r6

r7

r8

a0

sc ca f0 , π00 : π00 + π00 sc ca f0 , π01 : π01 + π01 sc ca f1 , π10 : π10 + π10

Fig. 7: Example of a scheduling problem. The scheduling performed by LLF-RC algorithm is sc illustrated in Fig. 8. At the beginning of slot 3, π00 has sc completed the transmissions, but π01 has not. Note that → sc the released transmission of π01 is − r− 2 g1 , which has absolute → sc deadline 5. The released transmission of π10 is also − r− 2 g1 , but its absolute deadline is 6. The two transmissions have laxities 2 and 3, respectively, while the number of remaining conflicting transmissions for both is 6, equal to → −−→ −−→ the sum of unscheduled transmissions on − r− 2 g 1 , r1 r2 , s 1 r2 , − − → sc and g1 r5 . As a result, π01 is scheduled due to its smaller laxity. D. Opportunistic Aggregation We propose OA mechanism, which can be integrated to work seamlessly with any scheduling algorithm. In general, scheduling problems can be infeasible due to tight deadlines or limitations on the total utilization. For instance, when the total utilization is greater than the number of channels C, scheduling problems are infeasible. Even if there are enough available channels, scheduling can still be infeasible due to strict deadlines. OA can alleviate the schedulability issue in either case by combining packets. Specifically, OA can be applied to most control applications as control packets are shorter compared to

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

sc transmissions

ca transmissions

release time (upwards)

deadline (downwards)

9

packets from different flows are aggregated and sent on → link − r− 2 g1 . In slot 5, two packets from different flows are → −−→ aggregated on node r6 and sent on links − r− 6 a1 and r6 r7 .

π00

sc transmissions

ca transmissions

release time (upwards)

deadline (downwards)

π01 π00

π10 0

2

4

6

8 10 12 14 16 18 20

Fig. 8: Scheduling with LLF-RC

the slot length, which is long enough to accommodate a packet of maximum size, as defined in WirelessHART [4] and TSCH [3] standards. To leverage OA, we replace line 6 in Algorithm 1 with Algorithm 2, which determines the packets to be scheduled and aggregated. The logic of Algorithm 2 is as follows. When the sender of a released transmission is already scheduled but the receiver is not or the link itself is scheduled, the packets are aggregated (see lines 3-6). When the sender and the receiver are both unscheduled, and there is at least one unused channel, then an unused channel is employed for the transmission (see lines 8-12). Algorithm 2: Proposed OA mechanism Input: C : number of channels J : set of released transmissions ordered by priority Output: S : set of scheduled senders R : set of scheduled receivers L : set of scheduled links Initialize: m = 0, S = ∅, R = ∅, L = ∅; 1 foreach t ∈ J do 2 if t.sender ∈ S then 3 if (t.receiver ∈ / S and t.receiver ∈ / R) or (t.sender → t.receiver) ∈ L then 4 Schedule t and perform aggregation; 5 R = R ∪ t.receiver; 6 L = L ∪ (t.sender → t.receiver); 7 8 9 10 11 12

else

if m < C and t.sender ∈ / R and t.receiver ∈ / S ∪ R then Schedule t; S = S ∪ t.sender, R = R ∪ t.receiver; L = L ∪ (t.sender → t.receiver); m = m + 1;

Note that t.sender denotes the sender of released transmission t, and t.receiver denotes the receiver of released transmission t. To use OA, we disable the utilization check in the schedulability test.

To illustrate OA’s principle, we use the same example as in Fig. 7 with LLF-RC algorithm, and show the resulting scheduling in Fig. 9. We observe that OA takes effect in slots 0, 3, 4, 5, and 10. In slot 0, the same packet is sent → −−→ on both links − s− 0 r0 and s0 r1 , simultaneously. In slot 3, two

π01 π10 0

2

4

6

8 10 12 14 16 18 20

Fig. 9: Scheduling with LLF-RC and OA

E. Repetitive Scheduling Centralized TDMA usually requires a network manager to (i) compute the scheduling, and (ii) distribute it to each mote. Since each node needs to store at least the partial scheduling related to itself, the communication cost (to disseminate the scheduling) and the storage cost (to retain the scheduling) cannot be ignored. Assuming that the communication and storage costs for every entry of the scheduling table is constant, the total cost of either is O(H · U ), where H is the hyperperiod, U is the total utilization, and H · U is the total number of entries in the scheduling table. In addition, H ∏ can be as large as the product of all periods, i.e., H = i pi , which occurs when the periods are co-prime. However, if the periods are harmonic, meaning a period is divisible by any period smaller than itself, then H is equal to the maximum period, i.e., H = maxi {pi }, thus leading to a smaller cost. If a system has harmonic periods, communication and storage costs can be reduced by enforcing that scheduling of each flow is repeated for each flow period. Therefore, we call this strategy RS. In contrast, hyperperiod scheduling (HS) is the procedure by which all time slots of a hyperperiod are scheduled. Both RS and HS behave similarly in terms of execution time. However, HS has a much ∑ larger communication and storage cost O(H · U )∑ = O( i pHi · Li ), whereas RS has a more affordable cost O( i Li ), where Li is the total number of hops in a flow, and is independent of H. The trade-off between these two types of scheduling is that RS is less costly but also less flexible, which can affect scheduling performance, while HS is more costly but more flexible, and generally offers higher schedulability. In Algorithm 3, we describe the proposed RS. In particular, RS uses as input the scheduling result of a HS algorithm, for instance, LLF-RC presented in Section IVC. Then, it finds the periods of all flows (see line 2). Subsequently, it identifies the distinct values for the periods, and sort them in increasing order (see line 3). Afterwards, it schedules the flows of a certain period (see

10

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

line 5). If the scheduling of a flow meets the deadline for one period, it will always do so for the entire hyperperiod since the periods are harmonic. Note that RS can be combined with OA. Algorithm 3: Proposed RS mechanism Input: A: A HS algorithm Output: H: Scheduling table, infeasible if H = ∅ 1 H = ∅; 2 Find the periods of all F flows, listed as p0 , p1 . . . pF −1 ; 3 Find distinct values from pi , and sort them, such that p′0 < p′1 < ... < p′M −1 , M ≤ F ; 4 for j = 0 to M − 1 do 5 Schedule all flows having the same period p′j for one period using A, considering the current scheduling table H; let the resulting scheduling table be Hj ; 6 if Hj = ∅ then 7 return H = ∅; 8 9

H = H ∪ {(p′j , Hj )}; return H;

convergecasts the measurements to the central unit is needed [45]. The details are out of the scope of this paper. Scheduling. After routing is done, the central unit is ready to run scheduling algorithms, e.g. LLF-RC + RS + OA. Then the computed scheduling table needs to be distributed to each node in the network, which stores a relevant partial scheduling table. We show in Section VI-F that the distribution of scheduling table takes less than one second for a network of 100 nodes and 50 flows with the Ripple protocol [59]. Periodic Control. Now control loops are formed, and should be activated periodically according to the scheduling table. To further increase control quality, the control algorithm may compute the actuating packet even if the related sensing packet is not delivered to any of the gateways in time, by applying an control algorithm that can estimate the sensing data. Some intelligence may even be applied at an actuator which can tolerate sporadic sensing packet and actuating packet loss. The details are out of the scope of this paper. V. A DAPTATION OF E XISTING S CHEDULING A LGORITHMS In this section we adapt several existing scheduling algorithms to be compatible with our framework.

Considering the example in Fig. 7, the scheduling that results from using LLF-RC with RS is shown in Fig. 10. A. Existing Scheduling Algorithms Contrary to what occurs in Fig. 8, where LLF-RC is In [58], various multiprocessor scheduling algorithms employed without RS, the scheduling of f0 is repeated were proposed, namely, rate monotonic (RM), DM, PDM, throughout the periods. CLLF, EDF, and earliest proportional deadline (EPD). In addition, in [60], the earliest deadline zero laxity (EDZL) sc transmissions ca transmissions algorithm was proposed. All these multiprocessor schedulrelease time (upwards) deadline (downwards) ing algorithms can be classified into two categories, fixedpriority and dynamic-priority. We adapt these algorithms to our case by introducing the following changes. π00 • We use the 2P scheduling instead of 1P scheduling, which is used by [11], [60], etc. π01 • The transmissions of a sa-path is mapped to a task. However, in our work, these transmissions are mapped to two tasks, which correspond to the transmissions of π10 sc- and ca-paths. In the following, we briefly revisit the aforementioned 0 2 4 6 8 10 12 14 16 18 20 algorithms, adapting the terminology to our context. Fig. 10: Scheduling with LLF-RC and RS Remark: Following the terminology of real-time scheduling, we use the term ‘task’ to denote a repeated work to be scheduled, and the term ‘job’ to denote an instance of a task. F. Implications of Applying the Scheduling Framework to Industrial Networks B. Fixed-Priority Scheduling Algorithms The following practical implications are essential for Fixed-priority scheduling algorithms assign priorities applying the proposed scheduling framework to industrial to tasks in advance. Hence, runtime information is not networks. required for comparing flow priorities. In general, the Routing. Routing is the prerequisite for applying the performance of fixed-priority algorithms is inferior to that scheduling framework. The central unit of a network of dynamic-priority algorithms [54]. Rate monotonic (RM). To be able to use RM for flow computes a multi-path routing scheme periodically (c.f. Section III-D and VI-B). The routing algorithm requires scheduling, we map the transmissions of a flow to a task. as input the link quality measurement of the network. Specifically, RM assigns each flow a priority inversely A mechanism that measures link quality locally, and proportional to its period [58].

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

11

Deadline monotonic (DM). Analogous to RM, we map where k is the current period index, t is the current slot the transmissions of a flow to a task. However, DM assigns index, and nrem (πix ) is the number of remaining transmiseach flow a priority inversely proportional to its relative sions. Recall that nahead (πix ) was defined in Section IV-C. Earliest deadline zero laxity (EDZL). It yields the same deadline [58]. The relative deadline of a flow is denoted by scheduling as EDF until the instant when a job has a (f ), and is determined by the control system design. dflow rel Proportional deadline monotonic (PDM). Compared to laxity of zero [60]. At this instant, EDZL gives the job the RM and DM, the tasks in PDM have finer granularity. highest priority. We implement EDZL as a combination In PDM, we map transmissions of a sc- or ca-path to a of EDF and LLF. If two jobs have laxity greater than 0 task. PDM assigns each sc- or ca-path a priority inversely and unequal deadlines, EDZL works as EDF, otherwise, x it works as LLF. proportional to its proportional deadline dpath prop (πi ), which Conflict-aware least-laxity-first (CLLF). It is an extenis calculated as, sion of the LLF algorithm adapted to WirelessHART by dsubflow (πix ) x taking into account conflicts among remaining transmisdpath (π ) = , (10) prop i l(πix ) sions. Since it needs to search for unreleased transmissions, where dsubflow (πix ) is the subflow deadline, and l(πix ) is the it is computationally expensive. The authors report that path length, i.e., the number of hops of πix . The subflow its performance is significantly higher than other scheduldeadline dsubflow (πix ) of an sc- or ca-path is defined as the ing algorithms evaluated in [11]. To be compatible with relative flow deadline minus the path length of the longest 2P scheduling, we adapted CLLF by properly calculating the deadline of a transmission according to (12). ca- or sc-path, as shown below, y dsubflow (πix ) = dflow rel (f ) − max{l(πj )}, j

(11)

where (x, y) ∈ {(sc, ca), (ca, sc)}. C. Dynamic-Priority Scheduling Algorithms Compared to fixed-priority algorithms, which employ a predefined priority for the whole scheduling process, dynamic-priority algorithms determine the flows priority at runtime. Earliest deadline first (EDF). It prioritizes the jobs with earlier absolute deadlines [58]. We map the transmissions of a sc- or ca-path in one period to a job. Assuming that a flow f has sc-paths πisc , ca-paths πica , and a relative flow deadline of dflow rel (f ), the relative deadlines of a sc- and path sc ca ca-path are dpath rel (πi ) and drel (πi ), respectively, which were defined in (8) and (9). Thus, the absolute deadline of the k-th activation of an sc- or ca-path (namely, the absolute deadline of the transmissions of the k-th packet of flow f on the path) is calculated as path x x dpath abs (πi , k) = k · pf + drel (πi ) − 1, x ∈ {sc, ca},

=

x dpath abs (πi , k) − t + 1 nrem (πix ) x dpath abs (πi , k) − t + 1 , x ∈ {sc, ca}, nahead (πix ) + 1

A. Performance Metrics To evaluate the algorithms’ performance, we use the following metrics: Schedulability ratio. It is related to schedulability performance. It denotes the percentage of instances in which all deadlines are met. A higher value is desirable. Execution time. It is the time an algorithm needs to return a scheduling solution. A smaller value is desirable. Maximum queue length. It is related storage costs. It is the maximum number of packets stored by a node during network operation. A smaller value is desirable. Scheduling table size. It is related to communication and storage costs. It is the size of the table that contains a schedule. A smaller value is desirable.

(12)

x where pf is the flow period. Here, dpath abs (πi , k) is used to dynamically assign priorities to jobs. Earliest proportional deadline (EPD). It prioritizes jobs with small sub-deadlines. A sub-deadline is defined as the time left until the deadline of a job, divided by the processing cost needed to finish the job. In our case, the transmissions in a sc- or ca-path are mapped to a job. Therefore, we define a sub-deadline as the remaining slots left until the path deadline, divided by the number of remaining transmissions on the path, which is given by

spath (πix , k) =

VI. S IMULATIONS We evaluate the performance of several scheduling algorithms using randomly generated networks based on the model described in Section III-A. We also evaluate the impact of OA and RS 2 .

(13)

B. Generation of Scenarios In order to evaluate a large variety of scenarios, we examine different settings of topology, number of flows, total utilization, period length, deadline type, and number of channels, as explained next. We summarize the most relevant parameters in Table II. Topology. We randomly generate each topology3 with N motes uniformly distributed within a square space of size s × s, which corresponds to medium-sized networked control systems. In addition, we place two gateways at the centers of the left and right half-planes of the square space. 2 The source code and dataset for the simulations in this paper are available at: https://github.com/pdvyuan/WSAN_periodic_control_scheduling 3 The generated networks are dense with an average node degree of approximately 10.

12

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

TABLE II: Simulation parameters Description

Value and Units Parameter

Side of the square

s

1200 m

Number of motes

N

100

Transmit power

Ptx

0 dBm

Packet length

L

133 bytes

Number of flows

F

{1, 2, . . . , Fmax }

Maximum number of flows

Fmax

50

Expected total utilization

U exp

[0, Umax ]

Maximum total utilization

Umax

25 (with OA) or 16 (without OA)

Number of channels

C

{1, . . . , 16}

Number of topologies

Ntop

100

Parameter model)

(TOSSIM

β1

0.9794

Parameter model)

(TOSSIM

β2

2.3851

Γth

0.5

PPR threshold 1 1P scheduling 2P scheduling

0.5

0 0

20

40

60

80

100

(a) Link quality [20, 100]% 1 1P scheduling 2P scheduling

0.5

0 20

30

40

50

60

70

80

90

100

(b) Link quality [40, 100]% 1 1P scheduling 2P scheduling

0.5

0 50

60

70

80

90

100

95

100

(c) Link quality [60, 100]% 1 1P scheduling 2P scheduling

0.5

0 70

75

80

85

90

(d) Link quality [80, 100]%

Fig. 11: Empirical CDFs of communication reliability of 1P scheduling and 2P scheduling.

The link qualities are calculated with the model presented in Section III-A. In total, Ntop topologies are evaluated. Number of flows. We generate a random number of flows F ∈ {1 . . . Fmax }, and for each topology, we evaluate 5 different flow settings. We enforce each flow to have at least two vertex-disjoint paths. Total utilization. We randomly choose an expected total utilization U exp ∈ [0, Umax ] for the whole network, where Umax denotes the maximum total utilization value. We use the UUniFast algorithm [61], [62] to uniformly distribute U exp among all flows, and for each configuration of flows, we evaluate 10 different values of U exp . Let flow f have an expected utilization uexp f , and contain hops(f ) links, then the period of f is set to the minimum integer pf ≥ ⌈hops(f )/uexp f ⌉, which satisfies the constraint of period length. Thus, the actual utilization of the flow is uf = hops(f )/pf . Period length. To compare RS and HS, we use harmonic periods pf = 2k , k ∈ {1 . . . 13}. Otherwise, pf is a factor of 10000, meaning 10000 is divisible by the positive integer pf . Deadline type. We choose between implicit and restricted deadline. The former implies that the deadline and the period are equal, and the latter one implies that the period is larger than the deadline. Number of channels. In IEEE 802.15.4, the maximum number of orthogonal channels is 16. Therefore, we consider C = {1, 2, 4, 8, 16}. Path-loss model. We choose d0 = 15 m, PL(d0 ) = 71.84 dBm, η = 2.16, and σ = 8.13, according to [48]. These are widely adopted values for 2.4 GHz frequency in indoor factory environments, for both line-of-sight (LOS) and non-line-of-sight (NLOS). A typical IEEE 802.15.4 radio chip CC2420 [63] has a transmit power Ptx in the range [−25, 0] dBm. We choose Ptx = 0 dBm since higher transmit power yields higher packet reliability when spatial reuse is disabled. Also, the noise floor of the CC2420 radio chip is −98 dBm. Communication model. We choose maximum packet length L = 133 bytes to account for the worst case. Specifically, an IEEE 802.15.4 frame contains a preamble of 4 bytes, 1 SFD byte, 1 byte of frame length, and PSU of variable length up to 127 bytes. Routing model. We use two vertex-disjoint reliable paths for every flow. First, the sc-routing is performed by finding the most reliable path. Then, we remove all nodes on the path except the sensor, and again find the most reliable path from the sensor to the other gateway. These two routes are disjoint except at the sensor node. Next, we restore the original topology, and find two disjoint caroutes in the same way. The routing method does not cause any single point of failure because the failure of a node (except for a sensor or actuator) will not break the connectivity of a flow. Software. The simulation is implemented in Java, and runs on a computer with an Intel Core [email protected] GHz CPU and 16 GB RAM. Remark: In the following sections, we evaluate the

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

13

performance of the proposed LLF-RC algorithm and the an implicit or restricted deadline. Besides, EDZL also adapted RM, DM, PDM, CLLF, EDF, EPD, EDZL algo- shows a high schedulability ratio, being only outperformed rithms. To evaluate the performance of the above multi- by LLF-RC. In Table III, we show the execution time of all processor scheduling algorithms, we include the random benchmarked algorithms, where we observe that LLF-RC links scheduling algorithm (RANDOM), which randomly needs approximately twice the execution time compared to select a maximal set of released transmissions for the the fastest algorithm RANDOM with either an implicit or schedule of each slot. In addition, we include algorithms constrained deadline. Yet, the execution time of LLF-RC ALICE [31] and TASA [13] as baselines, which have also with either deadline type is still small enough to allow been adapted to our framework4 . Further, we compare the frequent online rescheduling, which can further improve performance of HS and RS, with and without OA. the schedulability performance. For 1P scheduling, [11] reported that CLLF outperforms EDF and EPD in terms of schedulability ratio. But C. Reliability of 1P Scheduling and 2P Scheduling for 2P scheduling, this is not the case, especially for To evaluate how much 2P scheduling increases commu- restricted deadlines. We observe that the schedulability nication reliability over 1P scheduling, we generate several ratio of CLLF for restricted deadlines may decrease when topologies and flows as described in Section VI-B. Specif- the number of channels increases, as shown Fig. 12b ically, we generate the link qualities following uniform with C = 8 and C = 16. Another drawback is that distributions. In Fig. 11, we evaluate the communication CLLF is significantly more time-consuming than the other reliability of 1P scheduling and 2P scheduling for four algorithms, and is between 8 to 26 times slower than LLFcases where the link quality varies in different ranges. RC. Fig. 11a to Fig. 11d show the empirical cumulative disFor implicit deadlines, fixed-priority scheduling algotribution function (CDF) of the communication reliability rithms, such as RM, DM, and PDM, perform slightly of 1P scheduling and 2P scheduling. In this scenario, the worse than the dynamic ones, such as CLLF, EDF, EPD, links qualities are randomly selected from the sets [0.2, 1], EDZL, and LLF-RC. For instance, RM, DM, and PDM [0.4, 1], [0.6, 1], and [0.8, 1], respectively. We observe that are up to 4.56%, 4.56%, and 10.62% less efficient than the communication reliability of 2P scheduling is superior LLF-RC, respectively, in terms of schedulability ratio. to that of 1P scheduling. In particular, it exhibits an Fixed-priority scheduling algorithms should be avoided for approximate increment with respect to the median value, restricted deadlines as their performance is significantly between 13% (in Fig. 11a) and 2% (in Fig. 11d). The worse than the dynamic ones. For instance, RM, DM, and performance gap is smaller in Fig. 11d since all link PDM are up to 26.28%, 7.22%, and 14.89% less efficient qualities are very high. than LLF-RC, respectively, in terms of schedulability Remark: Via simulations we have shown that the ratio. The various multi-processor scheduling algorithms proposed 2P scheduling has higher reliability than the outperform RANDOM by 2 to 11 times, in terms of 1P scheduling that is commonly used in the literature, schedulability ratio, which demonstrates the power of confirming our theoretical analysis in Theorem 1. In the applying ideas drawn from the research on multi-processor remainder of scenarios, we focus on 2P scheduling. scheduling to WSAN scheduling. Although ALICE, TASA and RANDOM are competitive in terms of execution time, they are outperformed by the other algorithms in D. Schedulability Ratio of Several Algorithms using HS terms of schedulability ratio, showing that these bestIn this section, our goal is to find the best scheduling effort algorithms are not suitable for real-time schedulalgorithm without considering optional features, such as ing, especially when restricted deadlines are considered. RS or OA. In particular, we investigate the performance RANDOM arbitrarily selects a maximal transmission set of several algorithms in terms of schedulability ratio and to be scheduled per slot; TASA optimizes schedule length execution time. while ALICE aims to minimize scheduling overhead by In Fig. 12, we show the schedulability ratio for varcomputing the schedule locally at every node. None of ious configurations of number of channels and deadline them strives to meet the deadlines. ALICE performs the type. We observe that the schedulability ratio generally worst among the evaluated algorithms, because it is an increases with the number of channels available for any autonomous algorithm for which a link is only allowed scheduling algorithm, because with more channels, it to be scheduled in slots pre-determined by the source and allows more links to be scheduled simultaneously, and destination IDs of the link. Thus, ALICE cannot guarantee thus it is more likely for the scheduling problem to meet to schedule a maximal set of transmissions per slot while the deadlines. The proposed LLF-RC algorithm has the all the other algorithms can. highest schedulability ratio in almost all cases, either with Remark: Given our findings, which highlight the superior schedulability ratio of the proposed LLF-RC algo4As shown in [31], a shorter slot-frame length favors higher performance of ALICE, as it leads to a decreased delay. Therefore, rithm, which we identify as the most relevant criterion. for optimal performance, we choose a slot-frame length of 3. To Our subsequent analysis is focused on conducting a comimplement TASA, we find in each slot a maximal matching of no prehensive evaluation of LLF-RC in various scenarios. more than C links from the released transmissions favoring links with longer sender queue.

14

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

Algorithm Implicit deadline Restricted deadline

LLF-RC (Proposed) 15.4 5.4

RM 7.5 3.0

DM 7.5 2.9

PDM 8.0 3.1

CLLF 396.4 43.8

EDF 7.3 2.9

EPD 7.8 3.0

EDZL 7.7 3.0

ALICE 7.7 3.1

TASA 7.6 2.9

RANDOM 6.6 2.7

Schedulability ratio (%)

Schedulability ratio (%)

TABLE III: Execution time (in ms) of the algorithms using HS.

60

40

20

0

40 30 20 10 0

RM

DM PDM CLLF EDF F-RC EPD DZL LICE ASA DOM E T A N LL RA

RM

DM PDM CLLF EDF F-RC EPD DZL LICE ASA DOM E T A N LL RA

(a) Implicit deadline

(b) Restricted deadline

Fig. 12: Schedulability ratio performance of various algorithms for 2P scheduling.

100

Schedulability ratio (%)

Schedulability ratio (%)

100 80 60 40 20 0

60 40 20 0

0

2

4

6

8

10

12

14

0

2

4

6

8

10

12

Total utilization

Total utilization

(a) HS without OA (Implicit deadline)

(b) HS without OA (Restricted deadline) 100

Schedulability ratio (%)

100

Schedulability ratio (%)

80

80 60 40 20 0

80 60 40 20 0

0

5

10

15

20

25

0

2

4

6

8

10

12

14

16

Total utilization

Total utilization

(c) HS with OA (Implicit deadline)

(d) HS with OA (Restricted deadline)

18

Fig. 13: Schedulability ratio of LLF-RC using HS with and without OA for various numbers of channels and total utilization. A point (x, y) on the curves corresponds to the schedulability ratio y of all scheduling problems which have its total utilization in the range of (x − 0.25, x + 0.25]. The separation of two neighboring points on a curve is 0.5 in the x-axis.

E. Performance of LLF-RC using HS with and without OA

parameter settings5 . Impact of number of channels and total utilization. Fig. 13 shows the schedulability ratio of LLF-RC using HS without OA (in Fig. 13a and Fig. 13b) and with OA (in Fig. 13c and Fig. 13d), considering different numbers

We investigate the performance of LLF-RC using HS with and without OA, in terms of schedulability ratio, execution time, and maximum queue length, under various

5 The results for HS without OA are obtained using Algorithm 1 whereas the results for HS with OA are obtained using both Algorithm 1 and Algorithm 2 in tandem. For the latter case, line 6 of Algorithm 1 is replaced by Algorithm 2.

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

15

of channels and total utilization. Throughout Fig. 13a to transmissions, leading to a more dynamic behavior of the Fig. 13d, we observe that the schedulability ratio decreases maximum queue length. This leads to more flows and monotonically when the total utilization increases, for a more transmissions ready to be scheduled per slot, and given number of channels. This occurs because busier consequently to a higher number of potential contentions networks are less schedulable. In addition, the use of per link. Therefore, packets are more likely to be queued implicit deadlines results in a larger feasible utilization at a node. From Fig. 15a and Fig. 15b, we observe that region than with restricted deadlines. The reason is that the maximum queue length is higher when OA is used, scheduling with deadlines smaller than periods is more since the higher throughput provided by OA causes more likely to be infeasible than scheduling with equal deadlines packets to be buffered at intermediate nodes. and periods, especially in busier networks, which have In Fig. 15a, we observe that the median value of the higher utilization. maximum queue length is approximately 5 for implicit From Fig. 13a to Fig. 13d, we observe that using HS and restricted deadlines. However, the worst-case occurs with OA significantly improves the schedulability ratio for for restricted deadlines, where up to 24 packets are queued. both implicit and restricted deadlines, compared to using Since a packet has a payload size of at most 127 bytes, this HS without OA. In particular, the relative improvement requires less than 3 KBytes, which can fit into the RAM of obtained by OA is greater when implicit deadlines are a commercial sensor node. In Fig. 15b, we show a similar considered. The reason is that implicit deadlines are less case, where the maximum queue length has a median value restrictive, which gives more possibilities for aggregation. of less than 6 for implicit and restricted deadlines. The For instance, considering C = 8 and implicit deadlines, worst-case occurs for implicit deadlines, where up to 26 we observe that the use of OA contributes to increasing packets are queued. However, this is also small enough to the schedulability ratio from 16% to 97%. For restricted fit into the RAM of a sensor node. deadlines, the use of OA improves the schedulability ratio We observe that the penalty in maximum queue length from 3% to 46%. Thus, using HS with OA is very effec- incurred by the use of OA is affordable in exchange tive in combating conflicts, pushing the maximum total for a significant improvement in schedulability ratio and utilization far beyond the number of channels, especially reduction of execution time. for implicit deadlines. Remark: Simulation results confirm that the proposed OA’s aggregation rate, i.e. the percentage of combined OA mechanism increases the schedulability ratio for packets among all packets, is on average 23% and 17%, scheduling problems, and shortens the execution time of for implicit and restricted deadlines, respectively. Thus, scheduling algorithm, with only slight increase in buffer we note that with a moderate aggregation of packets, we size at nodes. can increase the schedulability ratio significantly. Execution time. In Fig. 14, we show the execution time of LLF-RC using HS with and without OA. We observe F. Performance of LLF-RC using HS or RS We evaluate the performance of LLF-RC using RS or that the execution time increases almost linearly with the HS, in terms of schedulability ratio, scheduling table size, number of transmissions in both cases. Moreover, for the and execution time. same number of transmissions, implicit deadline requires Schedulability ratio. In Fig. 16, we show the schedulabila relatively larger execution time. It is worth noting that the adoption of OA results in ity ratio of RS and HS, respectively. For implicit deadlines, a reduction in execution time ranging from 14% to 29% we observe that RS decreases the schedulability ratio only compared to the case without OA. The shorter execution slightly compared to HS. For restricted deadlines, however, time achieved when using OA is attributed to a higher RS causes a large decrement in the schedulability ratio, throughput, which is consequence of a more compact approximately 50%. In practice, most control systems scheduling table with fewer slots containing non-empty operate under implicit deadline requirements, thus making schedules. Still, it is important to recognize that OA RS still highly attractive due to its reduced scheduling requires more time to schedule a single slot due to the table size and execution time, which are discussed next. higher complexity of Algorithm 2. Scheduling table size. Fig. 17 shows the number of Maximum queue length. As sensor nodes usually have used entries in the scheduling table when RS or HS is very limited memory resources, it is vital to investigate employed. Because the communication and storage costs the memory consumption during network operation, for are proportional to the number of used entries, we observe which we use the maximum queue length metric. When a tremendous cost reduction with RS. We realize from evaluating this metric, we only take into account the motes, Fig. 17a and Fig. 17b that the maximum number of used without considering the gateways, since the latter usually entries are 1284 and 150396, for RS and HS, respectively. have sufficient storage capacity. Each entry in the scheduling table contains the fields: slot From our evaluation, we found that the maximum queue ID (2 bytes), channel ID (4 bits), sender ID (1 byte), length increases linearly with the number of flows and total receiver ID (1 byte) and flow ID (6 bits). In total, the utilization. Also, the maximum queue length increases size of each entry is about 5 bytes. Thus, the maximum almost linearly with the number of channels. This oc- scheduling table size for RS and HS are 51.4 kbits and curs because more channels allows for more simultaneous 6015.8 kbits, respectively. As shown by [59], the Ripple

16

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

400 Implicit Restricted

200

Execution time [ms]

Execution time [ms]

250

150 100 50 0

300

Implicit Restricted

200 100 0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

Transmissions in a hyperperiod

(a) HS without OA

0.8

0.9

0.5 105

1

1.5

Transmissions in a hyperperiod

2 105

(b) HS with OA

Fig. 14: Execution time of LLF-RC using HS with and without OA. A point (x, y) on the curves corresponds to the mean execution time (y) of all schedulable problems with number of transmissions in (x − 0.5 · 104 , x + 0.5 · 104 ), x = {0.5, 1.5, . . . } · 104 . The error bars denote ± one standard deviation.

(a) HS without OA

(b) HS with OA

Fig. 15: Maximum queue length of LLF-RC using HS with and without OA. Box plots for various values of maximum queue length.

protocol can achieve a flooding throughput of about 90 of scheduling algorithm tremendously, with only slight kbit/s. Therefore, the scheduling table for RS can be decrease in schedulability ratio. downloaded in less that 0.6s, allowing frequent schedule VII. E XTENSION TO L ARGE - SCALE R EAL - WORLD refresh. On the other hand, with HS, more than 66s I NDUSTRIAL N ETWORKS would be required, making it less practical. In addition, since the scheduling table has to be transmitted and So far, the algorithms proposed in this paper are only stored at the wireless nodes, there are significant savings suitable for small to medium size industrial networks, in communication and storage costs, which is especially because frequency (communication channel) reuse is discritical for wireless nodes with limited resources, such as allowed. Therefore, the network capacity is limited, and sensors and relays. will not scale with network size (number of nodes). To Execution time. In Fig. 18, we compare the execution extend the proposed algorithms to large-scale real-world time of HS and RS. We observe that when HS is employed, industrial networks, we have to leverage frequency reuse the execution time grows linearly for an increasing number in the manner of cellular networks. of transmissions. In contrast, the execution time remains As illustrated in Fig. 19, a large-scale network can be almost constant when RS is employed, showing its poten- divided into many cells. Each cell has a base station, tial for real-time control applications. and all nodes in the cell can only use a certain set of For a network of 100 nodes and up to 50 flows, the communication channels. Two neighboring cells must use execution time of scheduling algorithm RS is in most cases different sets of communication channels to reduce mutual below 10ms. By applying OA, the execution time can be interference. The base stations are connected by a wired further reduced by half. Thus, the scheduling scheme LLF- backbone network. RC + RS + OA proposed in this paper is practical for Routing. A sensing packet must be routed from a medium-size industrial networks. sensor to the base station of the cell using communication Remark: Simulation results confirm that for scheduling channels that are allowed by the cell. An actuating packet problems of implicit deadline, the proposed RS mechanism must be routed to an actuator from the base station of the reduces the scheduling table size and the execution time cell using communication channels that are allowed by the

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

50

60

Schedulability ratio (%)

Schedulability ratio (%)

70

50 40 30 20 10 0

40 30 20 10 0

1

2

4

8

16

1

(a) Without OA (Implicit deadline)

2

4

8

16

(b) Without OA (Restricted deadline) 60

Schedulability ratio (%)

100

Schedulability ratio (%)

17

80 60 40 20

50 40 30 20 10 0

0 1

2

4

8

1

16

(c) With OA (Implicit deadline)

2

4

8

16

(d) With OA (Restricted deadline)

1400

1200

1200

Repetitive scheduling

1400

1000 800 600 400 200 0 101

102

103

104

1000 800 600 400 200 0 101

105

102

Hyperperiod scheduling

103

104

105

Hyperperiod scheduling

(a) Without OA (Implicit deadline)

(b) With OA (Implicit deadline)

102

10

Hyperperiod scheduling Repetitive scheduling

0

1

2

3

4

5

6

7

Transmissions in a hyperperiod

(a) Without OA (Implicit deadline)

8 104

Execution time [ms]

Fig. 17: Number of used entries in the scheduling table using LLF-RC with RS or HS.

Execution time [ms]

Repetitive scheduling

Fig. 16: Schedulability ratio of LLF-RC using RS or HS.

102 Hyperperiod scheduling Repetitive scheduling

100 1

2

3

4

5

6

Transmissions in a hyperperiod

(b) With OA (Implicit deadline)

Fig. 18: Execution time of LLF-RC using HS or RS.

7

8 104

18

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

Fig. 19: Illustration of a large-scale network divided into cells. We have 4 types of cells (C1, C2, C3, C4). Each cell uses 4 communication channels.

scheduling table size and the maximum execution time by 99% and 92% respectively in our simulation, leading to high energy savings at wireless nodes. We evaluated these techniques in various scenarios, demonstrating that LLF-RC, in combination with OA and RS, provides an effective and efficient solution for real-time TDMA scheduling in industrial WSANs. Finally, we extended the proposed scheduling algorithms to support large-scale networks by exploiting cellular frequency reuse. There, network throughput increases linearly with network size, flow reliabilities and delays remain independent of network size, and the scheduling algorithms can be parallelized.

cell. Hence, the hop distance from a sensor to an actuator A PPENDIX A: R ELIABILITY OF 1P AND 2P is in the worst case twice the cell diameter, irrespective of S CHEDULING the network size. Cell diameter is defined at the largest hop distance of two nodes in a same cell. So the flow reliability and the flow delay are independent of network size. The same multi-path routing model in Section III-D Let us introduce li ≥ 0 and mi ≥ 0 such that li = can be applied for large-scale networks. (1 − risc ) and mi = (1 − rica ). Therefore, r1P and r2P are Scheduling algorithms. The scheduling algorithms pro- equivalently expressed as posed in Section IV can be easily extended to support large-scale networks. The only needed modification is that links in different cells can be scheduled in a same slot. In n−1 ∏ this way, the network throughput is linear to the number r1P = 1 − (1 − (1 − li )(1 − mi )) of cells, and thus, it is proportional to the network size. i=0 n−1 Execution time. The execution time of scheduling algo∏ (li + mi − li mi ) = 1 − rithms should be linear to network size and number of i=0 flows if a central unit performs the scheduling in a serial way. Yet, the execution time can be reduced significantly since the link scheduling per slot can be parallelized. This is due to the fact that any two links from different cells can always be scheduled in a same slot because of the cellular ( )( ) n−1 n−1 division of a large network. Thus, the link scheduling per ∏ ∏ 2P r = 1− li 1− mi slot can be done in parallel for each cell. VIII. C ONCLUSION In this paper, we investigated centralized TDMA scheduling of WSANs for multi-rate periodic control systems in Industry 4.0. We proposed 2P scheduling, a new scheduling framework with higher reliability than conventional WSAN scheduling. Drawing from multiprocessorscheduling, we further proposed LLF-RC, an efficient scheduling algorithm that prioritizes flows based on link conflicts. Simulations showed LLF-RC has the highest schedulability ratio among benchmarked algorithms. It has low execution time (in most cases below 10ms for a network of 100 nodes and up to 50 flows) and low maximum queue length, making it practical for realworld systems. We also proposed OA and RS, two new scheduling strategies that can be easily integrated with any scheduling algorithm. OA increases schedulability ratio by up to 97% in our simulation, and pushes total utilization beyond the number of channels in the system, suitable for congested networks. RS reduces the maximum

=1−

i=0 n−1 ∏

n−1 ∏

i=0

i=0

li −

i=0 n−1 ∏

mi +

li mi

i=0

Let us introduce c1P ≤ 0 and c2P ≤ 0, defined below,

c1P = − c2P = −

n−1 ∏ i=0 n−1 ∏ i=0

(li + mi − li mi ), li −

n−1 ∏ i=0

mi +

n−1 ∏

li mi ,

i=0

yielding r1P = 1 + c1P and r2P = 1 + c2P . Hence, proving that r2P ≥ r1P is equivalent to proving that c1P ≤ c2P . For notation simplicity, let us assume that k = n − 1.

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

19

min{hops(πisc ) + hops(πica )}, which is equal to the hop i k count of the shortest sa-path. ∏ c1P = − (li + mi − li mi ), To prove that d2P ≥ d1P , we derive a first inequality, n−1 n−1 i=0 which we refer to as I1 . Let {xi }i=0 , {yi }i=0 ∈ Z+ ∪ {0} k−1 be nonnegative integers, since the hop count has the same ∏ (li + mi − li mi )(lk + mk − lk mk ), =− nature. Note that min{xi } ≤ xi and min{yi } ≤ yi hold i i i=0 true for all i. Using these inequalities, we obtain that ( k−1 ) k−1 k−1 ∏ ∏ ∏ min{xi } + min{yi } ≤ xi + yi , which also holds for all i, = − li − mi + li mi · (lk + mk − lk mk ) , i i including the index i′ that attains xi′ + yi′ = min{xi′ + i=0 i=0 i=0 i k k k k−1 k−1 yi′ }. Therefore, we have obtained our first inequality I1 : ∏ ∏ ∏ ∏ ∏ =− li − mi − li mi − li mk + l i l k mk min{xi } + min{yi } ≤ min{xi + yi }. i i i i=0 i=0 i=0 i=0 i=0 Now, we derive a second inequality, which we refer to as k−1 k−1 k−1 k−1 n−1 n−1 ∏ ∏ ∏ ∏ I2 . Let {wi }i=0 , {zi }i=0 ∈ Z+ ∪{0}, such that xi = wi +zi . − mi lk + mi lk mk + l i mi l k + li mi mk , Replacing this equivalence in I1 leads to min{wi + zi } + i=0 i=0 i=0 i=0 i ( ) min{yi } ≤ min{wi + zi + yi }. Note than an upper bound k k k k ∏ ∏ ∏ ∏ i i =− li − mi + li mi − 2 l i mi for wi is max{wi }, which we can use to obtain a looser i i=0 i=0 i=0 i=0 inequality min{wi + zi } + min{yi } ≤ min{max{wi } + zi + k−1 k−1 k−1 i i i i ∏ ∏ ∏ yi }. Because, max{xi } is constant for all i, the inequality − l i mk + li lk mk − mi l k i i=0 i=0 i=0 can be equivalently expressed as min{wi +zi }+min{yi } ≤ i i k−1 k−1 k−1 ∏ ∏ ∏ max{wi } + min{zi + yi }. By setting yi = 0, we obtain our i i + mi lk mk + l i mi l k + li mi mk , second inequality I2 : min{wi + zi } ≤ max{wi } + min{zi }. i=0 i=0 i=0 i i i k k k Finally, with the changes of variables, wi = hops(πisc ) and ∏ ∏ ∏ =− li − mi + li mi zi = hops(πica ), we obtain that d2P ≥ d1P , which completes i=0 i=0 i=0 the proof. k−1 k−1 ∏ ∏ − li mi (lk mk − mk ) − li mi (lk mk − lk ) R EFERENCES

Thus, c1P can be expressed as follows,

−

i=0 k−1 ∏

i=0

li mk (1 − lk ) −

i=0

=− − −

k ∏

mi lk (1 − mk ),

i=0

li −

i=0 k−1 ∏ i=0 k−1 ∏ i=0

k−1 ∏

k ∏ i=0

mi +

k ∏

li mi

i=0

li mk (1 − lk )(1 −

k−1 ∏

mi )

i=0 k−1 ∏

mi lk (1 − mk )(1 −

li ).

i=0

From the above equality, we obtain that c1P = c2P + ′ c∏ + c′′ , where c′ < 0∏and c′′ < 0 are defined ∏k−1 as c = k−1 k−1 ′′ k (1 − lk )(1 − i=0 li m∏ i=0 mi ) and c = i=0 mi lk (1 − k−1 mk )(1 − i=0 li ). Thus, we conclude that c2P ≥ c1P , and consequently we claim that r2P ≥ r1P , thus completing the proof. ′

A PPENDIX B: L ATENCY OF 1P AND 2P S CHEDULING Assuming that hops(πi ) denotes the hop count of a given path πi , the minimum flow delay of 2P scheduling is d2P = max{hops(πisc )} + min{hops(πica )}, which is equal to the i i sum hop count of the longest sc-path and the shortest ca-path. We need to make sure that the sensor packet can be delivered to the controller even via the longest sc-path when 2P scheduling is employed. On the other hand, the minimum flow delay of 1P scheduling is d1P =

[1] J.-P. Thomesse, “Fieldbus technology in industrial automation,” Proc. of IEEE, vol. 93, no. 6, pp. 1073–1101, 2005. [2] J. R. Moyne and D. M. Tilbury, “The emergence of industrial control networks for manufacturing control, diagnostics, and safety data,” Proc. of IEEE, vol. 95, no. 1, pp. 29–47, 2007. [3] “IEEE std 802.15.4e. IEEE standards association,” IEEE Computer Society, Tech. Rep., 2012. [4] “WirelessHART specifications,” http://www.hartcomm.org, HART Foundation, Tech. Rep., 2007. [5] “The ISA100 standards, overview and status,” http://www.isa.org, International Society of Automation, Tech. Rep., 2008. [6] I. Rodriguez, R. S. Mogensen, A. Schjørring, M. Razzaghpour, R. Maldonado, G. Berardinelli, R. Adeogun, P. H. Christensen, P. Mogensen, O. Madsen, C. Møller, G. Pocovi, T. Kolding, C. Rosa, B. Jørgensen, and S. Barbera, “5G swarm production: Advanced industrial manufacturing concepts enabled by wireless automation,” IEEE Commun. Mag., vol. 59, no. 1, pp. 48–54, 2021. [7] A. Tangirala, D. Li, R. Patwardhan, S. Shah, and T. Chen, “Issues in multirate process control,” in Proc. ACC, vol. 4, 1999, pp. 2771–2775 vol.4. [8] W. Haddad and V. Kapila, “A periodic fixed-structure approach to multirate control,” IEEE Trans. Autom. Control, vol. 40, no. 2, pp. 301–307, 1995. [9] M. Caccamo, L. Y. Zhang, L. Sha, and G. C. Buttazzo, “An implicit prioritized access protocol for wireless sensor networks,” in Proc. of IEEE RTSS, 2002, pp. 39–48. [10] O. Chipara, C. Lu, and G.-C. Roman, “Real-time query scheduling for wireless sensor networks,” in Proc. of IEEE RTSS, 2007, pp. 389–399. [11] A. Saifullah, Y. Xu, C. Lu, and Y. Chen, “Real-time scheduling for WirelessHART networks,” in Proc. of IEEE RTSS, 2010, pp. 150–159. [12] A. Darbandi and M. K. Kim, “Path collision-aware real-time link scheduling for TSCH wireless networks,” KSII Trans. Internet Inf. Syst., vol. 13, no. 9, pp. 4429–4445, 2019.

20

[13] M. R. Palattella, N. Accettura, M. Dohler, L. A. Grieco, and G. Boggia, “Traffic aware scheduling algorithm for reliable lowpower multi-hop IEEE 802.15.4e networks,” in Proc. of PIMRC, 2012, pp. 327–332. [14] K. Shi, L. Zhang, Z. Qi, K. Tong, and H. Chen, “Transmission scheduling of periodic real-time traffic in IEEE 802.15.4e TSCH-based industrial mesh networks,” Wirel. Commun. Mob. Comput., 2019. [15] G. Chen, X. Cao, L. Liu, C. Sun, and Y. Cheng, “Joint scheduling and channel allocation for end-to-end delay minimization in industrial WirelessHART networks,” IEEE Internet Things J., vol. 6, no. 2, pp. 2829–2842, 2019. [16] H.-B. Park and J. Joung, “Slot reallocation and rejection for collision avoidance in autonomous TSCH networks,” IEEE Access, vol. 9, pp. 93 816–93 830, 2021. [17] L. Bommisetty and T. G. Venkatesh, “Contention-based proportional fairness (CBPF) transmission scheme for time slotted channel hopping networks,” IEEE Trans. Ind. Inform., vol. 19, no. 2, pp. 1289–1300, 2023. [18] Z. Yu, X. Na, C. A. Boano, Y. He, X. Guo, P. Li, and M. Jin, “SmarTiSCH: An interference-aware engine for IEEE 802.15.4ebased networks,” in Proc. of IPSN, 2022, pp. 350–362. [19] S. Moon, H. Park, H. S. Chwa, and K.-J. Park, “AdaptiveHART: An adaptive real-time MAC protocol for industrial Internet-ofThings,” IEEE Syst. J., vol. 16, no. 3, pp. 4849–4860, 2022. [20] D. Seo, K. Jung, H. Roh, S. Kim, and S. Oh, “High-efficiency resource allocation scheme introducing the concept of resource sharing paths in industrial IoT,” IEEE Access, vol. 11, pp. 63 821–63 833, 2023. [21] H. Kim, G. Lee, J. Shin, J. Paek, and S. Bahk, “Slot-size adaptation and utility-based packet aggregation for IEEE 802.15.4e time-slotted communication networks,” IEEE Internet Things J., vol. 11, no. 9, pp. 16 382–16 397, 2024. [22] “IEEE standard 802.15.4,” IEEE Computer Society, Tech. Rep., 2006. [23] Y. Jin, P. Kulkarni, J. Wilcox, and M. Sooriyabandara, “A centralized scheduling algorithm for IEEE 802.15.4e TSCH based industrial low power wireless networks,” in Proc. of IEEE WCNC, 2016, pp. 1–6. [24] A. Tinka, T. Watteyne, K. S. J. Pister, and A. M. Bayen, “A decentralized scheduling algorithm for time synchronized channel hopping,” EAI Endorsed Trans. Mobile Commun. and Appl., vol. 11, no. 1, 9 2011. [25] N. Accettura, M. R. Palattella, G. Boggia, L. A. Grieco, and M. Dohler, “Decentralized traffic aware scheduling for multi-hop low power lossy networks in the internet of things,” in Proc. of IEEE WoWMoM, 2013, pp. 1–6. [26] M. R. Palattella, T. Watteyne, Q. Wang, K. Muraoka, N. Accettura, D. Dujovne, L. A. Grieco, and T. Engel, “On-the-fly bandwidth reservation for 6TiSCH wireless industrial networks,” IEEE Sensors J., vol. 16, no. 2, pp. 550–560, 2016. [27] P. H. Gomes, T. Watteyne, and B. Krishnamachari, “MABOTSCH: Multihop and blacklist-based optimized time synchronized channel hopping,” Trans. Emerg. Telecommun. Technol., vol. 29, no. 7, 2018. [28] T. Hamza and G. Kaddoum, “Enhanced minimal scheduling function for IEEE 802.15.4e TSCH networks,” in Proc. of IEEE WCNC, 2019, pp. 1–6. [29] M. Domingo-Prieto, T. Chang, X. Vilajosana, and T. Watteyne, “Distributed PID-based scheduling for 6TiSCH networks,” IEEE Commun. Lett., vol. 20, no. 5, pp. 1006–1009, 2016. [30] S. Duquennoy, B. A. Nahas, O. Landsiedel, and T. Watteyne, “Orchestra: Robust mesh networks through autonomously scheduled TSCH,” in Proc. of ACM SenSys, 2015, pp. 337–350. [31] S. Kim, H.-S. Kim, and C. Kim, “ALICE: Autonomous linkbased cell scheduling for TSCH,” in Proc. of IPSN, 2019, pp. 121–132. [32] A. Saifullah, Y. Xu, C. Lu, and Y. Chen, “End-to-end delay analysis for fixed priority scheduling in WirelessHART networks,” in Proc. of IEEE RTAS, 2011, pp. 13–22. [33] ——, “Priority assignment for real-time flows in WirelessHART networks,” in Proc. of ECRTS, 2011, pp. 35–44. [34] L. F. Abanto-Leon, A. Koppelaar, and S. Heemstra de Groot, “Network-assisted resource allocation with quality and conflict constraints for V2V communications,” in Proc. of IEEE VTC Spring, 2018, pp. 1–5.

IEEE SENSORS JOURNAL, VOL. XX, NO. XX, XXXX 2024

[35] T. Şahin, R. Khalili, M. Boban, and A. Wolisz, “Scheduling out-of-coverage vehicular communications using reinforcement learning,” IEEE Trans. Veh. Technol., vol. 71, no. 10, pp. 11 103– 11 119, 2022. [36] J. Wu, Y. Guo, and S. Zhou, “A reliable self-adaptive scheduling control protocol for cellular V2X mode 4,” IEEE Access, vol. 10, pp. 63 991–64 003, 2022. [37] D. M. Mughal, J. S. Kim, H. Lee, and M. Y. Chung, “Performance analysis of V2V communications: A novel scheduling assignment and data transmission scheme,” IEEE Trans. Veh. Technol., vol. 68, no. 7, pp. 7045–7056, 2019. [38] M. Alonso, H. Amaris, D. Alcala, and D. M. Florez R., “Smart sensors for smart grid reliability,” Sensors, vol. 20, no. 8, 2020. [39] A. Afzaal, F. Kanwal, A. H. Ali, K. Bashir, and F. Anjum, “Agent-based energy consumption scheduling for smart grids: An auction-theoretic approach,” IEEE Access, vol. 8, pp. 73 780– 73 790, 2020. [40] F. R. Albogamy, M. Y. I. Paracha, G. Hafeez, I. Khan, S. Murawwat, G. Rukh, S. Khan, and M. U. A. Khan, “Realtime scheduling for optimal energy optimization in smart grid integrated with renewable energy sources,” IEEE Access, vol. 10, pp. 35 498–35 520, 2022. [41] H.-J. Lee and S.-H. Chung, “Link-based autonomous cell scheduling for IEEE 802.15.4e TSCH with improved traffic throughput,” IEEE Sensors J., vol. 21, no. 19, pp. 22 104–22 112, 2021. [42] D. Sinha and R. Roy, “Deadline-aware scheduling for maximizing information freshness in industrial cyber-physical system,” IEEE Sensors J., vol. 21, no. 1, pp. 381–393, 2021. [43] H. Kim, G. Lee, J. Shin, J. Paek, and S. Bahk, “Slot-size adaptation and utility-based packet aggregation for IEEE 802.15.4e time-slotted communication networks,” IEEE Internet of Things J., pp. 1–15, 2024. [44] S. C. Ergen and P. Varaiya, “TDMA scheduling algorithms for wireless sensor networks,” Wirel. Netw., vol. 16, no. 4, pp. 985– 997, 2010. [45] D. Yuan and M. Hollick, “Tree-based multi-channel convergecast in wireless sensor networks,” in Proc. of IEEE WoWMoM, 2012, pp. 1–9. [46] T. S. Rappaport and C. D. McGillem, “UHF fading in factories,” IEEE J. Sel. Areas Commun., vol. 7, no. 1, pp. 40–48, 1989. [47] M. Zuniga and B. Krishnamachari, “Analyzing the transitional region in low power wireless links,” in Proc. of IEEE SECON, 2004, pp. 517–526. [48] E. Tanghe, W. Joseph, L. Verloock, L. M., H. Capoen, K. V. Herwegen, and W. Vantomme, “The industrial indoor channel: large-scale and temporal fading at 900, 2400, and 5200 MHz,” IEEE Trans. Wireless Commun., vol. 7, no. 7, pp. 2740–2751, 2008. [49] T. Rappaport, Wireless Communications: Principles and Practice. Upper Saddle River, NJ, USA: Prentice Hall PTR, 2001. [50] P. Levis, N. Lee, M. Welsh, and D. Culler, “TOSSIM: Accurate and scalable simulation of entire tinyOS applications,” in Proc. of ACM SenSys, 2003, pp. 126–137. [51] W. Zhang, M. S. Branicky, and S. M. Phillips, “Stability of networked control systems,” IEEE Control Syst. Mag., vol. 21, pp. 84–99, 2001. [52] P. D. Marco, P. G. Park, C. Fischione, and K. H. Johansson, “TREnd: a timely, reliable, energy-efficient and dynamic WSN protocol for control applications,” in Proc. of IEEE ICC, 2010, pp. 1–6. [53] I. Chlamtac and A. Faragó, “Making transmission schedules immune to topology changes in multi-hop packet radio networks,” IEEE/ACM Trans. Netw., vol. 2, no. 1, pp. 23–29, 1994. [54] R. I. Davis and A. Burns, “A survey of hard real-time scheduling for multiprocessor systems,” ACM Comput. Surv., vol. 43, no. 4, pp. 1–44, 2011. [55] W. A. Horn, “Some simple scheduling algorithms,” Naval Research Logistics Quarterly, vol. 21, no. 1, pp. 177–185, 1974. [56] L. Cucu and J. Goossens, “Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors,” in Proc. of IEEE ETFA, 2006, pp. 397–404. [57] ——, “Feasibility intervals for multiprocessor fixed-priority scheduling of arbitrary deadline periodic systems,” in Proc. of IEEE DATE, 2007, pp. 1–6. [58] J. W. S. Liu, Real-Time Systems. Upper Saddle River, NJ, USA: Prentice Hall, 2000.

AUTHOR et al.: PREPARATION OF PAPERS FOR IEEE TRANSACTIONS AND JOURNALS (MAY 2024)

[59] D. Yuan and M. Hollick, “Ripple: High-throughput, reliable and energy-efficient network flooding in wireless sensor networks,” in Proc. of IEEE WoWMoM, 2015, pp. 1–9. [60] S. K. Lee, “On-line multiprocessor scheduling algorithms for real-time tasks,” in Proc. of IEEE TENCON, 1994, pp. 607– 611. [61] E. Bini and G. C. Buttazzo, “Measuring the performance of schedulability tests,” Real-Time Syst., vol. 30, no. 1-2, pp. 129– 154, 2005. [62] R. I. Davis and A. Burns, “Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems,” Real-Time Syst., vol. 47, no. 1, pp. 1–40, 2011. [63] “CC2420 datasheet,” Texas Instrument, Tech. Rep., 2007.

Dingwen Yuan He received his Bachelor of Engineering degree from the Department of Automation, Shanghai Jiao Tong University in 2002. In 2010 and 2016, he got his Master of Science and Ph.D. degrees from Technische Universität Darmstadt. Currently he works as an engineer at Nokia. His research interests include the QoS guarantee in wireless sensor networks (WSN), and the scheduling and optimization of millimeter-wave networks and cellular networks in general.

Luis F. Abanto-Leon earned his master’s degree in Communications Engineering from Tohoku University, Japan, in 2015 and completed his Ph.D. in Computer Science at Technische Universität Darmstadt, Germany, in 2023. He is currently a postdoctoral researcher at Ruhr-Universität Bochum, Germany. His research interests include optimization theory, signal processing, and algorithm design for radio resource management in wireless networks.

Matthias Hollick received the Ph.D. degree from Technische Universität (TU) Darmstadt in 2004. He is currently the Head of the Secure Mobile Networking Lab, Department of Computer Science, TU Darmstadt, Germany. He has been researching and teaching at TU Darmstadt, Universidad Carlos III de Madrid, and the University of Illinois at Urbana–Champaign. His research focus is on resilient, secure, privacy-preserving, and quality-of-service-aware communication for mobile and wireless systems and networks.

21