An optimal energy-saving real-time task-scheduling algorithm for mobile terminals

Abstract

This article discusses the principles, mechanisms, and strategy of hard real-time task scheduling appropriate for mobile terminal equipment. Mobile terminals have timeliness requirements for completing hard real-time tasks and also clear energy-management requirements. Therefore, this study attempts to schedule tasks under these two constraints to achieve an optimal level of energy savings. First, terminal equipment operating time and standby time should meet the maximum requirements, and second, all tasks should meet the constraints of real-time parallel scheduling. We propose a scheduling strategy based on grouping according to the latest cut-off time, with each group adopting a dynamic optimization strategy to make scheduling decisions. The feasibility and validity of this algorithm are demonstrated through experiments and simulations.

Research background

Research status of real-time task scheduling based on intelligent terminal systems

Mobile intelligent terminals that run a number of hard real-time tasks that must be completed within the specified time have relatively high requirements for real-time task scheduling. Failure to meet these requirements can result in the malfunction of systems such as traffic control systems and medical monitoring systems. Periodic real-time tasks must be executed once during each fixed period of time. For example, the signal analysis and diagnosis task of a medical monitoring system is a periodic real-time task. Given a task-scheduling algorithm, if the execution of each task can be completed within its deadline, the task scheduling is denoted as feasible. The earliest-deadline-first (EDF) scheduling algorithm determines the order in which tasks are run according to the deadline of task completion such that tasks with the earliest deadlines are run first. ¹ The least-leisure-time-first (LSF) algorithm assigns the highest priority to the task with the shortest deadline to ensure that the most urgent tasks are executed first. Based on the EDF algorithm, Vrimani et al. ² proposed a new scheduling strategy based on genetic algorithm to address the defects of the EDF algorithm.

Problem analysis and research objectives

Although the EDF algorithm has been improved, the algorithm is not appropriate for energy-sensitive devices such as mobile terminals because it does not consider the energy consumption of peripherals. Due to the rapid development and proliferation of on-chip processor systems and mobile intelligent terminals with advances in mobile computing and the Internet of Things, intelligent embedded real-time systems have become increasingly critical. For mobile intelligent terminals, the power standby time has become a critical performance index, making energy management an increasingly important issue in mobile real-time systems. The energy consumption of complementary metal oxide semiconductor (CMOS)-integrated processing chips has two main aspects: capacitor power consumption and leakage current power consumption.^3,4 Modern integrated chip technology generally uses voltage/frequency regulation and dynamic power management (DPM) technology to reduce power consumption. In general, the dynamic energy consumption decreases with decreasing central processing unit (CPU) frequency. However, for a mobile terminal, chip energy management is only one component in energy-management concern because the chip controls the external devices through the interface. In fact, most of the interrupted tasks processed by the system are interrelated with management of external equipment run states. ⁵

Generally, the energy consumption of these peripherals accounts for 25%–95% of the energy consumption of the entire system. In the working mode of intelligent mobile health-monitoring equipment, life detection sensors and life signal processing modules consume 50% of the energy of the overall system, whereas in standby mode, the energy consumption of the processor is 75% of the total system consumption. Operating data obtained from the MWatch health-monitoring wristwatch show that in the working mode, the operating current of the bi-signal front-end processing RC network and the active power amplifier chip is 17 mA, and the current consumption of the power regulation management module is 1.5 mA. The organic light-emitting diode (OLED) display consumes 25 mA, the average operating current of the capacitive touch screen is 2.5 mA, and the operating current of other external devices is approximately 0.5 mA. The peak current of the processor is 12 mA. Therefore, it can be estimated that the power consumption of the processor in the working state accounts for only 20.5% of the consumption of the overall system.

Figure 1.

Mobile health-monitoring watch developed in this article for scheduling hard real-time tasks.

Based on this background information, this study considers peripheral energy consumption as the primary factor in the energy consumption of the entire system. ⁶ During exploration of the principles, mechanisms, and strategy of hard real-time task scheduling appropriate for mobile terminal equipment, we establish a relevant system model composed of the processor, tasks, and the total energy consumption of the system. We propose a new optimal energy-saving algorithm for the hard real-time task scheduling of mobile terminals. The feasibility and validity of this algorithm is demonstrated through experiments and simulations that assess the power consumption of a mobile health-monitoring wristwatch that implements the proposed algorithm and the EDF algorithm.

Article structure

In this article, the algorithm is introduced in five main parts. The first part introduces the current situation and main research objectives, the second part reviews related work, and the third part describes the system model. Because the scheduling of tasks is a complicated process involving many factors in the hardware and software systems, it is necessary to establish a theoretical model to strictly define the quantity of and logical relationship between the components and to establish a theory for discussing the scheduling algorithms of the system. The fourth part focuses on the scheduling algorithm. Using three theorems, the theoretical basis of the scheduling algorithm and the correctness of the algorithm are presented, and the concrete algorithm is outlined. The fifth part is the experimental and simulation results that verify the correctness and feasibility of the algorithm. The sixth part provides the conclusions.

Related work

To improve the efficiency of real-time periodic task systems, a common real-time task model was proposed, ⁷ which allowed the end time and cycle time of a periodic task to be changed over a given period of time. The system efficiency was improved, and both the EDF and LSF algorithms were further optimized by accelerating the speed of task scheduling and reducing the waiting time through timely adjustment of task deadlines and periods under the condition of ensuring the normal operation of system scheduling. ⁸ Burns and other researchers proposed a scheduling strategy based on a weight (priority) value. ⁹ This strategy performed some tasks from the task set selectively to ensure that the system had the best overall weight value. To increase the unit weight value of the system, the task weight density was determined according to the maximum execution time and the task weight, and then the highest value density first (HVDF) algorithm was proposed, using the maximum weight density, to prioritize the execution of tasks in order to contribute the highest weights to the system. ⁸

J Liu and J Guo ¹⁰ studied the energy efficiency scheduling of periodic real-time tasks on multi-core processors with voltage islands and proposed a voltage maximum capacity first (voltage island largest capacity first (VILCF)) algorithm for energy-efficient scheduling of periodic real-time multi-core processors. This achieved better energy efficiency, by making full use of the remaining capacity of each island, before opening more islands or increasing the voltage level of the current active island. The experimental results show that VILCF is superior to the existing algorithm when there are multiple cores in the voltage island. K Li ¹¹ examined how the core allocates tasks and schedules tasks, when multiple processors of cloud computing data centers are shared by a large number of concurrent tasks, in order to minimize energy consumption. By adding the constant velocity method into the algorithm, the performance of the scheduling algorithm is improved further. M Fan et al. ⁶ proposed an on-line power management method to minimize the power consumption of single-processor real-time scheduling under reliability constraints. The simulation results show that using runtime kinetics, the proposed method can save more energy than using previous work under reliability constraints.

HE Zahaf et al. ¹² focus on real-time scheduling based on dynamic voltage and frequency scaling (DVFS). They present a model of the performance and energy consumption of parallel real-time tasks carried out on the ARM big LITTLE architecture. The optimization problem is first defined as an integer nonlinear programming (INLP) problem, and then, a heuristic method is proposed in order to find an effective solution to the problem. The results show that the method has a good energy-saving effect. M Akbari et al. ¹³ used a genetic algorithm to solve the static task-scheduling problem of processors in heterogeneous computing systems. The algorithm improves the performance of their genetic algorithm through a significant change to the genetic function, and the introduction of a new operator, ensuring consistent coverage of sample variety and the whole space. In addition, the random initial population has been replaced by some fixed initial population, with a partially optimized solution, to reduce the reproducibility of the genetic algorithm. Compared with other task-scheduling algorithms, the new algorithm is applicable to the practical application of heterogeneous computing systems with extensive characteristics. The results show that the proposed algorithm results in significant improvements. In order to deal with the scheduling of tasks on heterogeneous systems, M Akbari and H Rashidi ¹⁴ proposed an algorithm that reduces the execution time while allowing maximum parallelization. The algorithm is based on the multi-objective scheduling azalea optimization algorithm (MOSCOA). In this algorithm, each cuckoo represents a dispatch solution, which takes into account the tasks assigned to them, along with the order of the processors. By the target migration operator in the algorithm to complete global optimization, and push each repetitive plan to an optimized plan to protect the global optimal, MOSCOA realizes a large number of random graphs, and realistic applications, whose graphs possess extensive features and show that MOSCOA is superior to the previous task-scheduling algorithm. D Konar et al. ¹⁵ studied the efficient real-time task scheduling assisted by a hybrid quantum-inspired heuristic genetic algorithm (HQIGA) in a multiprocessor environment. The HQIGA method uses a revolving door operation to explore the variable chromosomes described in the qubit of the Hilbert hyperspace. Simulation results show that HQIGA is superior to both the classical genetic algorithm (CGA) and mixed particle swarm optimization (MPSO) in the use of numerous codes and achieves significant improvements in the scheduling time.

System model

The author is a core member of the mobile health-monitoring system key technology project research team and presided over the research and development of an intelligent health care watch. The developed intelligent health care watch is an intelligent terminal that offers real-time electrocardiography (ECG) monitoring in which ECG information can be extracted, detected, and analyzed and sent to a remote server through Wi-Fi for further processing. As shown in Figure 2, the optimal real-time scheduling problem is an important sub-task of the project. For intelligent mobile terminal equipment, certain external devices are driven by the firmware, such as the display, capacitive touch screen, FLASH, and medical sensors, among others. Each time that the device is initialized, the operating system needs only to perform an interrupt call on the line. Selected external devices have a single feature that does not require a firmware-driven peripheral, such as a power management chip similar to the power-gating header. However, for the system, the same calls to the firmware are made via external interrupts that can be abstracted into a class of external interrupt devices for unified management. ¹⁶

Figure 2.

System structure of the mobile health-monitoring watch.

Processor model

Assuming a single-processor system with an operating frequency v, we denote $p_d(v)$ as the dynamic power consumption at runtime, which primarily derives from the power consumption caused by the gate charge, the discharge capacitance, and the short-circuit power consumption caused by the short-circuit transient current. It is well known that $p_d(v)$ is proportional to the third power of v, which can be represented as $p_d(v)=\alpha v^3$ . This statement means the static power consumption $p_s(v)$ , which is independent of v, is primarily due to the leakage power consumption generated by the leakage current. In general, $p_s(v)$ is a constant, and we set $p_s(v)=\beta$ . Therefore, the processor power function is $p(v)=p_d(v)+p_s(v)=\alpha v^3+\beta$ , $\alpha >0,\beta \ge 0$ . This processor power consumption model applies to multiple dynamic voltage frequency scaling (DVFS) processors, and $p(v)$ is a strictly convex increasing function, as shown in Figure 3. The energy consumption of a processor that performs a single clock cycle at frequency v is $p(v)/v=\alpha v^2+\beta /v$ . The value of v for which $p(v)/v$ attains a minimum value is denoted as the critical frequency. Without consideration of processor performance, it is clear that the minimum energy consumption is obtained at the lower bound of v.

Figure 3.

Processor energy consumption versus clock frequency.

The processor has two states: the sleep state and the active state. When the processor is in the sleep state, DPM can turn off the processor clock to reduce the processor voltage to a very low level. At that time, the power consumption of the device is negligible. ¹⁷ A processor that is executing a task is in the active state. When the processor is idle in the active state, the minimum power consumption processor executes the idle operation instruction at a very low frequency. ¹⁸

We denote the idle power consumption as $p_{\mathrm{idle}}$ and assume that it is not less than the minimum possible power consumption of the processor at the lower bound of v, denoted in this work as $p_{min}$ such that $p_{\mathrm{idle}}\ge p_{min}$ . When the period during which the processor sits idle is greater than the maximum idle period $t_{\theta }$ , the processor is placed in the sleep state. Setting $E_{\mathrm{sw}}$ as the energy consumption required for the processor to switch between operating states and $t_{\mathrm{sw}}$ as the time cost of state switching, the process of switching the operating state is energy efficient when $(t_{\theta }-t_{\mathrm{sw}})P_{\mathrm{idle}}\ge E_{\mathrm{sw}}$ such that $t_{\theta }\ge E_{\mathrm{sw}}/{\mathrm{P}}_{\mathrm{idle}}+t_{\mathrm{sw}}$ . Obviously, if the energy savings increase, the longer the processor resides in the sleep mode.

Task model

Definition 1

$\mathrm{\Gamma }(R,T,P,C,D)$ represents a task model, where R is the time when the task is released, T is the time when the task is scheduled, P is the power consumed when the task is waiting, C is the time required to execute the task, and D is the final deadline for the task to be completed. We refer to Γ as a real-time task set, and $\xi \in \mathrm{\Gamma }$ indicates that $\xi$ is a task entity in the task set. According to Definition 1, each $\xi$ has five attribute components, where, for example, $\xi [R]$ represents the time component when the task is released.

Definition 2

Given a task set $\mathrm{\Gamma }(X,Y)$ , where X and Y are attribute fields of Γ, when $\xi [X]=\varsigma$ , the image set of $\varsigma$ in $Z$ is $Z_{\varsigma }=\{\xi [Z]|\xi \in \mathrm{\Gamma },\xi [X]=\varsigma \}$ .

Definition 3

The task projection operation $\pi$ forms a new task set from several attribute columns selected from Γ and is denoted as ${\pi }_A(\mathrm{\Gamma })=\{\xi [A]|\xi \in \mathrm{\Gamma }\}$ .

Definition 4

The task selection operation $\sigma$ forms tasks selected from Γ that satisfy a given condition and is denoted as ${\sigma }_F(\mathrm{\Gamma })=\{\xi |\xi \in \mathrm{\Gamma }\wedge \mathrm{F}(\xi )=“\mathrm{true}”\}$ .

Definition 5

${\mathrm{\Gamma }}_{\tau }$ is a subset of the tasks that enter the scheduling process at the moment $\tau$ and is denoted as

$${\mathrm{\Gamma }}_{\tau }={\sigma }_{R\ge \tau }(\mathrm{\Gamma })=\left\{\xi |\xi \in \mathrm{\Gamma }\wedge \xi \left[R\right]\ge \tau \right\}$$

(1)

Definition 6

${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ is the subset of tasks that enter the scheduling process at the moment ${\tau }_1$ and that have absolute deadlines greater than or equal to ${\tau }_2$ . It is denoted as

$$\begin{array}{l}{\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}={\sigma }_{R\ge {\tau }_1\wedge T+D\le {\tau }_2}(\mathrm{\Gamma })\\ =\left\{\xi |\xi \in \mathrm{\Gamma }\wedge \xi \left[R\right]\ge {\tau }_1\wedge \xi \left[\mathrm{T}\right]+\xi \left[\mathrm{D}\right]\le {\tau }_2\right\}\end{array}$$

(2)

Definition 7

${\xi }_{\mathrm{key}}\in {\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ if it satisfies ${\xi }_{\mathrm{key}}[R]+{\xi }_{\mathrm{key}}[D]=min\{{\xi }_j[R]+{\xi }_j[D]|0\le j\le s,{\xi }_j\in {\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}\}$ , and ${\xi }_{\mathrm{key}}$ is the key tuple of ${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ . If the subsequence $\xi {\prime }_1,\xi {\prime }_2,\dots ,\xi {\prime }_r$ of ${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ , which does not include ${\xi }_{\mathrm{key}}$ , satisfies ${\tau }_1\le {\xi }_i[T]+{\xi }_i[\mathrm{C}]\le {\xi }_{i+1}[T],{\xi }_r[T]+{\xi }_r[\mathrm{C}]\le {\tau }_2$ , then the subsequence is referred to as a feasible scheduling of ${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ that is relative to ${\xi }_{\mathrm{key}}$ and is denoted as $S{C}_{{\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}}({\xi }_{\mathrm{key}})$ .

This work considers two sets of tasks. One set is represented by the hard real-time periodic task set ${\mathrm{\Gamma }}_T(R,T,P,C,D)$ , where P indicates the power consumed by the peripherals of the task while waiting for a time Δt at idle for scheduling. Setting the peripheral operating current associated with the process as I and the operating voltage is U, $P=\mathrm{UI}\Delta t$ , and the total energy consumed by a hard-cycle task set peripheral during a super cycle of a task is $E_H=\sum _{k=1}^N{p}_k\Delta t_k$ . For the intelligent health-monitoring wristwatch developed in this study, most of the hard real-time tasks are related to peripherals or sensors. For example, in module-related ECG monitoring data acquisition tasks, the digital-to-analog converter generates a hard interrupt after the acquisition and conversion of a segment of data. At the same time, the ECG module remains in the active state and consumes 3.3 V × 17 mA of power at idle. The ECG module resides in a waiting mode until the CPU sets the general-purpose input/output (GPIO) control register state to turn off the power supply of the RC network. If each waiting time of this task is $\Delta t=500\mu \mathrm{s}$ and the ECG sampling frequency is 200 Hz, then the power consumption due to scheduling is P = (200 Hz × 0.5 ms × 3.3 V × 17 mA)/1000 =5.61 mW. The second hard real-time random task set ${\mathrm{\Gamma }}_O(R,T,P,C,D)$ does not consider cycles.

Energy consumption model

Definition 8

$P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)=\sum _{i=1}^r{\xi }_i[P]$ , where $P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ is denoted as the power output of the feasible scheduling $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ .

Definition 9

$P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ is denoted as the power loss of the feasible scheduling $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ if

$$\begin{array}{l}P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_r)={\displaystyle \sum _{i=2}^r({\xi }_i[P]}{\displaystyle \sum _{j=0}^{i-1}{\xi }_j[C])}\\ +{\displaystyle \sum _{{\xi }_i\in {\mathrm{\Gamma }}_{\tau ,\delta }\wedge {\xi }_i\notin S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}{\xi }_i[P]}{\displaystyle \sum _{j=0}^r{\xi }_j[C]}\end{array}$$

(3)

Definition 10

In addition to the condition of Definition 9, if $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ also satisfies

$$S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_r)=MIN(S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({{\xi }^{\prime }}_1,{{\xi }^{\prime }}_2,\mathrm{\dots },{{\xi }^{\prime }}_m),{{\xi }^{\prime }}_k\in {\mathrm{\Gamma }}_{\tau ,\delta })$$

(4)

then we denote this feasible scheduling as the optimal energy-saving scheduling $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ .

This work does not consider the energy consumption costs of switching between the active and sleep states of processors, and only a single-processor environment is considered. Based on this assumption, it is proposed that the $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ assigning all tasks in the task set to the same processor must satisfy the following properties.

Theorem 1

For $\mathrm{S}=(t_1,t_2,\dots ,t_k,t_{k+1}\dots )$ , where $t_k=(R_k,T_k,C_k,P_k,D_k)$ and $t_{k+1}=(R_{k+1},T_{k+1},C_{k+1},P_{k+1},D_{k+1})$ in a feasible scheduling sequence, the necessary and sufficient conditions are

1. $T_k+C_k\le R_k+D_k,T_{k+1}+C_{k+1}\le R_{k+1}+D_{k+1}$

2. $T_k+C_k\le R_{k+1}+D_{k+1}-C_{k+1}$

Proof

The necessity is obvious, and we only discuss the adequacy here. Because of the limitations $T_k+C_k\le R_k+D_k$ , each task can be completed by the deadline. Because $T_k+C_k\le R_{k+1}+D_{k+1}-C_{k+1}$ , we assume that the (k + 1)th task enters the scheduling operation immediately after the kth task is completed. The deadline of the (k + 1)th task is $T_k+C_k+C_{k+1}$ . Because the deadline of the (k + 1)th task is $R_{k+1}+D_{k+1}$ , the task-scheduling constraint condition must only satisfy $T_k+C_k+C_{k+1}\le R_{k+1}+D_{k+1}$ . This statement is exactly equivalent to equation (2) of Theorem 1. Therefore, the adequacy is proven.

Theorem 2

In the $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ , the condition ${\xi }_k[P]/{\xi }_k[C]\ge {\xi }_{k+1}[P]/{\xi }_{k+1}[C]$ must be satisfied.

Proof

Because ${\xi }_1\dots {\xi }_k,{\xi }_{k+1}\dots {\xi }_r$ is the optimal energy-saving scheduling of task set ${\mathrm{\Gamma }}_{\tau ,\delta }$ , ${\xi }_1\dots {\xi }_k,{\xi }_{k+1}\dots {\xi }_r$ must be a feasible scheduling, and the sequence ${\xi }_1\dots {\xi }_{k+1},{\xi }_k\dots {\xi }_r$ generated by the exchange in the orders of two elements is also a feasible scheduling $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1\dots {\xi }_{k+1},{\xi }_k\dots {\xi }_r)$ . By Definition 9, the power loss for optimal scheduling is given by equation (3). Compared with equation (3), the power loss of $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1\dots {\xi }_{k+1},{\xi }_k\dots {\xi }_r)$ has only two differences, which are described as follows: ${\xi }_{k+1}[P]\sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_k[P](\sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[C])$ .

Because $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ fulfills condition equation (4) by Definition 10, the condition

$$\begin{array}{l}{\xi }_k[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_{k+1}[P]\left({\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[C]}\right)\\ \le {\xi }_{k+1}[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_k[P]\left({\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[C]}\right)\end{array}$$

(5)

must be met. After expanding equation (5), we obtain the following inequality

$$\begin{array}{l}{\xi }_k[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_{k+1}[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[P]\xi [C]}\\ \le {\xi }_{k+1}[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_k[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_k[P]{\xi }_{k+1}[C]}\end{array}$$

(6)

The elimination of equivalent terms yields

$${\xi }_{k+1}[P]{\xi }_k[C]\le {\xi }_k[P]{\xi }_{k+1}[C]$$

(7)

This statement can also be written as ${\xi }_k[P]/{\xi }_k[C]\ge {\xi }_{k+1}[P]/{\xi }_{k+1}[C]$ , and therefore, the proposition is proven.

Energy-saving optimal scheduling algorithm

Theoretical basis of the algorithm

Definition 11

${\rho }_k={\xi }_k[P]/{\xi }_k[C]$ and is denoted as the power factor for a task item. Obviously, in the schedulable case, the priority of the scheduling increases with increasing ${\rho }_k$ .

Theorem 3

We use ${\rho }_k$ as the priority, ranging from high to low, for scheduling to be implemented in task set ${\mathrm{\Gamma }}_{\tau ,\delta }$ . If the resulting feasible scheduling sequence satisfies $P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)=\mathrm{MAX}(P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(\xi {\prime }_1,\xi {\prime }_2,\dots ,{\xi }_m)),\xi {\prime }_k\in {\mathrm{\Gamma }}_{\tau ,\delta }$ , then the scheduling sequence must also satisfy condition (4), and this scheduling represents the $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ .

Proof

We prove this statement by the method of counterevidence. Suppose $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ does not satisfy $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ , and when ${\xi }_r>\xi {\prime }_r$ , $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,\xi {\prime }_r)$ satisfies

$$P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)\ge P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,\xi {\prime }_r)$$

(8)

Thus, by definition, the following inequality is met

$$\begin{array}{c}\sum _{i=2}^{r-1}({\xi }_i[P])\sum _{j=1}^{i-1}({\xi }_j[C])+{\xi }_r[P]\sum _{j=1}^{r-1}{\xi }_j[C]\hfill \\ +{\xi \prime }_r[P]\sum _{j=1}^r{\xi }_j[C]+\sum _{{\xi }_i\ne {\xi \prime }_r\wedge {\xi }_i\in {\mathrm{\Gamma }}_{\tau ,\delta }\wedge {\xi }_i\notin S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}{\xi }_i[P]\sum _{j=1}^r{\xi }_j[C]\hfill \\ \ge \sum _{i=2}^{r-1}({\xi }_i[P])\sum _{j=1}^{i-1}({\xi }_j[C])+{\xi \prime }_r[P]\sum _{j=1}^{r-1}{\xi }_j[C]\hfill \\ +{\xi }_r[P]\sum _{j=1}^r{\xi }_j[C]+\sum _{{\xi }_i\ne {\xi }_r\wedge {\xi }_i\in {\mathrm{\Gamma }}_{\tau ,\delta }\wedge {\xi }_i\notin S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}{\xi }_i[P]\sum _{j=1}^r{\xi }_j[C]\hfill \end{array}$$

(9)

Eliminating equivalent terms on both sides of the inequality yields

$$({\xi }_r[P]-\xi {\prime }_r[P])\sum _{j=1}^{r-1}{\xi }_j[C]\ge ({\xi }_r[P]-\xi {\prime }_r[P])\sum _{j=1}^r{\xi }_j[C]$$

(10)

Setting ${\xi }_r[P]\ge \xi {\prime }_r[P]$ , we draw the conclusion

$$\sum _{j=1}^{r-1}{\xi }_j[C]\ge \sum _{j=1}^r{\xi }_j[C]$$

(11)

By definition, ${\xi }_j[C]>0,{\xi }_j\in {\mathrm{\Gamma }}_{\tau ,\delta }$ , and therefore, the above conclusion cannot be established, and the proposition is proven. Because $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ satisfies condition (4), the condition

$$\begin{array}{l}{\xi }_k[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_{k+1}[P]\left({\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[C]}\right)\\ \le {\xi }_{k+1}[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_k[P]\left({\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[C]}\right)\end{array}$$

(12)

must be met. After expanding the above, we obtain the following inequality

$$\begin{array}{l}{\xi }_k[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_{k+1}[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_{k+1}[P]\xi [C]}\\ \le {\xi }_{k+1}[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]}+{\xi }_k[P]{\displaystyle \sum _{i=0}^{k-1}{\xi }_i[C]+{\xi }_k[P]{\xi }_{k+1}[C]}\end{array}$$

(13)

Elimination of equivalent terms yields

$${\xi }_{k+1}[P]{\xi }_k[C]\le {\xi }_k[P]{\xi }_{k+1}[C]$$

(14)

This statement can also be written as ${\xi }_k[P]/{\xi }_k[C]\ge {\xi }_{k+1}[P]/{\xi }_{k+1}[C]$ . Therefore, the proposition is proven.

Inference 1

We assume ${\rho }_k$ as a fixed priority, and a schedule in task set ${\mathrm{\Gamma }}_{\tau ,\delta }$ is implemented according to the rate-monotonic scheduling (RM) algorithm. The sequence $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ obtained is not necessarily the $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ .

Proof

Let ${\xi }_r$ be the last element in the resulting scheduling sequence according to the RM algorithm, that is, ${\xi }_{r+1}\in {\mathrm{\Gamma }}_{\tau ,\delta },{\xi }_{r+2}\in {\mathrm{\Gamma }}_{\tau ,\delta }$ and ${\rho }_r\ge {\rho }_{r+1}\ge {\rho }_{r+2}$ . Depending on the definition, the following conditions might exist

$$\begin{array}{c}{\xi }_r[C]\le {\xi }_{r+1}[C]+{\xi }_{r+2}[C]\le \delta -{\xi }_r[T]\hfill \\ {\xi }_r[P]\le {\xi }_{r+1}[P]+{\xi }_{r+2}[P]\hfill \end{array}$$

(15)

This statement indicates that a new schedule can be constructed with a substitution of ${\xi }_{r+1},{\xi }_{r+2}$ for ${\xi }_r$ and that $P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_{r+1},{\xi }_{r+2})$ must be greater than $P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ . Therefore, an appropriate ${\xi }_{r+1}[C],{\xi }_{r+2}[C]$ exists such that

$$\begin{array}{l}P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_{r+1},{\xi }_{r+2})\ge P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}\\ ({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_r),{\xi }_k\in {\mathrm{\Gamma }}_{\tau ,\delta }\end{array}$$

(16)

Inference 2

Scheduling in task set ${\mathrm{\Gamma }}_{\tau ,\delta }$ is implemented according to the EDF algorithm, and the resulting $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ is not necessarily the $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ .

Verification

This inference is easily verified because from Definition 5, ${\mathrm{\Gamma }}_{\tau ,\delta }={\sigma }_{R\ge \tau \wedge \mathrm{D}\ge \delta }(\mathrm{\Gamma })=\{\xi |\xi \in \mathrm{\Gamma }\wedge \xi [R]\ge \tau \wedge \xi [D]\ge \delta \}$ . Because every task in task set ${\mathrm{\Gamma }}_{\tau ,\delta }$ can be completed within the deadline $\delta$ , the proposition becomes an RM scheduling problem.

As discussed, this study considers the optimal energy-saving scheduling process. After scheduling the task items from high to low priority according to the energy consumption factor, the optimal energy-saving solution is obtained by constructing a scheduling sequence in a step-by-step manner. Assuming an order of decisions ${\xi }_1,{\xi }_2,\dots ,{\xi }_n$ , after making the decision ${\xi }_i$ , the problem involves one of the following choices: ${\xi }_i$ is abandoned, and the state remains unchanged, or ${\xi }_i$ is retained as the solution element of the optimal sequence, and the state vector changes accordingly, as follows

$$\begin{array}{l}P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_i)=P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}\\ ({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_{i-1})+{\xi }_i[P]\end{array}$$

(17)

$$\begin{array}{l}P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_i)=P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}\\ ({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_{i-1})+{\xi }_i[P]{\displaystyle \sum _{j=0}^{i-1}{\xi }_j[C]}-{\xi }_i[P]{\displaystyle \sum _{j=0}^r{\xi }_j[C]}\end{array}$$

(18)

Definition 12

Let ${\mathrm{\Omega }}_i=\delta -\sum _{j=0}^i{\xi }_j[C]$ , ${\mathrm{\Omega }}_i={\mathrm{\Omega }}_{i-1}-{\xi }_i[C]$ . The resulting sequence from the decision of the kth step is $(\xi {\prime }_1,\xi {\prime }_2,\dots ,\xi {\prime }_r)$ , and $F{P}_k({\mathrm{\Omega }}_k)$ represents the subsequent power output value of the sequence, that is, $F{P}_k({\mathrm{\Omega }}_k)=P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(\xi {\prime }_1,\dots ,\xi {\prime }_k)$ . Each step requires two different decisions that must be integrated. According to Definition 9, this process can be expressed as

$$\begin{array}{c}\multicolumn{1}{c}{F{P}_k({\mathrm{\Omega }}_k)=\mathrm{MAX}(F{P}_{k-1}({\mathrm{\Omega }}_{k-1}),F{P}_{k-1}}\\ ({\mathrm{\Omega }}_{k-1}-{\xi }_k[C])+{\xi }_k[P])\hfill \end{array}$$

(19)

Obviously, this example is a process of optimal selection. If it can be guaranteed that $F{P}_{k-1}({\mathrm{\Omega }}_{k-1})$ is an optimal choice, then $F{P}_k({\mathrm{\Omega }}_k)$ can be treated as an optimal choice based on the previous optimal decision, and the result is obviously optimal.

Theorem 4

According to equation (19), and based on recursive relations, we make a dynamic decision from the sequence represented by $F{P}_0({\mathrm{\Omega }}_0)$ . The result must be optimal.

Proof

The following holds from Definition 9

$$\begin{array}{l}F{P}_k({\mathrm{\Omega }}_k)=P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({{\xi }^{\prime }}_1,\mathrm{\dots },{{\xi }^{\prime }}_k)\\ =\mathrm{MAX}(F{P}_{k-1}({\mathrm{\Omega }}_{k-1}),F{P}_{k-1}({\mathrm{\Omega }}_{k-1}-{\xi }_k[C])\\ +{\xi }_k[P])\end{array}$$

(20)

We define the maximization conditions for solving the problem $\mathrm{MAX}(P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(\xi {\prime }_1,\dots ,\xi {\prime }_k))$ and the problem constraints ${\mathrm{\Omega }}_i=\delta -\sum _{j=0}^i{\xi }_j[C]\ge 0$ . We specify the steps needed to solve the problem and make scheduling decisions according to the tuple sequence ${\rho }_k={\xi }_k[P]/{\xi }_k[C]$ from high to low priority. This method of solving problems is consistent with the principle of optimization, where regardless of the initial state of the process and whatever the initial decision, the remaining decision-making process constitutes an optimal decision sequence relative to the initial state. Thus, the result must be optimal. In other words, we can obtain a solution vector satisfying $\mathrm{MAX}(P{W}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(\xi {\prime }_1,\dots ,\xi {\prime }_k))$ . According to Theorem 2, this statement is equivalent to finding a solution

$${\mathrm{OPES}}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({\xi }_1,{\xi }_2,\mathrm{\dots },{\xi }_r)=\mathrm{MIN}(P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}({{\xi }^{\prime }}_1,{{\xi }^{\prime }}_2,\mathrm{\dots },{\xi }_m)),{{\xi }^{\prime }}_k\in {\mathrm{\Gamma }}_{\tau ,\delta }$$

(21)

This type of dynamic planning and scheduling algorithm is herein denoted as a decisive path scheduling (DPS) algorithm.

DPS algorithm

In this article, we clarify the function of the DPS algorithm using an example and present the main steps. Let a set of tasks ${\mathrm{\Gamma }}_{{\tau }_1=102,{\tau }_2=109}$ exist, as listed in Table 1.

Table 1.

Task set example.

Γ	R	T	C	P	D	ρ
${\xi }_1$	100	$\tau$	3	12	13	4.0
${\xi }_2$	100	$\tau$	2	5	11	2.5
${\xi }_3$	101	$\tau$	3	9	9	3.0
${\xi }_4$	101	$\tau$	1	2	8	2.0
${\xi }_5$	102	$\tau$	4	20	10	5.0
${\xi }_6$	102	$\tau$	10	15	9	1.5

Because ${\xi }_4$ is the deadline’s earliest critical tuple, ${\xi }_4$ must be scheduled at the time when ${\xi }_4[T]=\tau +\delta -{\xi }_4[C]=108$ . The prerequisite is to obtain the optimal energy-saving scheduling $S{C}_{{\mathrm{\Gamma }}_{\delta 1,\delta 2}}({\xi }_4)$ . Because ${\xi }_6$ is less than ${\rho }_4$ , the ${\xi }_6$ tuple is excluded from the scheduling. Therefore, we obtain the sequence $({\xi }_5,{\xi }_1,{\xi }_3,{\xi }_2)$ , which is scheduled in the time period ¹⁸ according to the value of ρ from high to low. In this example, we consider the following step-by-step process based on the initialization sequence $S_0=\{\{\varnothing \},F{P}_0(0)=0\}$ .

For the first step, we perform decision making on ${\xi }_5$ : abandon ${\xi }_5$ , $F{P}_1(0)=F{P}_1(0)=0$ ; accept ${\xi }_5$ , $F{P}_1({\xi }_5[C])=F{P}_1(4)=20$ ; merge them and obtain the solution set

$$S_1=\{\{\left\{\varnothing \right\},F{P}_1(0)=0)\},\{\left\{{\xi }_5\right\},F{P}_1(4)=20)\}\}$$

(22)

For the second step, we perform decision making on ${\xi }_1$ : abandon ${\xi }_5$ , $F{P}_2(0)=0,F{P}_2(4)=20$ ; accept ${\xi }_1$ , $F{P}_2(3)=12,F{P}_2(7)=32$ ; merge them and obtain the solution set

$$S_2=\left\{\begin{array}{c}\{\left\{\varnothing \right\},F{P}_2(0)=0)\},\{\left\{{\xi }_5\right\},F{P}_2(4)=20)\}\hfill \\ \multicolumn{1}{c}{\{\left\{{\xi }_1\right\},F{P}_2(3)=12)\},\{\{{\xi }_1,{\xi }_5\},F{P}_2(7)=32)\}}\end{array}\right\}$$

(23)

For the third step, we perform decision making on ${\xi }_3$ : abandon ${\xi }_3$ , the solution set is ${\xi }_3$ , and we obtain $s_2$ and accept ${\xi }_3$ to obtain the solution set

$$S{\prime }_3=\left\{\begin{array}{c}\{\left\{{\xi }_3\right\},F{P}_3(3)=9)\},\{\{{\xi }_3,{\xi }_5\},F{P}_3(7)=29)\}\hfill \\ \multicolumn{1}{c}{\{\{{\xi }_1,{\xi }_3\},F{P}_3(6)=21)\},\{\{{\xi }_1,{\xi }_5,{\xi }_3\},F{P}_3(10)=41)\}}\end{array}\right\}$$

(24)

where the solution set $\{\{{\xi }_1,{\xi }_5,{\xi }_3\},F{P}_3(10)=41)\}$ passes beyond the domain of the problem, $0\le \mathrm{\Omega }\le 7$ and is discarded. After merging $S_3$ and $S{\prime }_3$ , we obtain the solution set

$$S_3=\{\begin{array}{c}\{\left\{\varnothing \right\},F{P}_3(0)=0)\},\{\left\{{\xi }_5\right\},F{P}_3(4)=20)\},\{\left\{{\xi }_1\right\},F{P}_3(3)=12)\},\{\{{\xi }_1,{\xi }_5\},F{P}_3(7)=32)\}\hfill \\ \multicolumn{1}{c}{\{\left\{{\xi }_3\right\},F{P}_3(3)=9)\},\{\{{\xi }_3,{\xi }_5\},F{P}_3(7)=29)\},\{\{{\xi }_1,{\xi }_3\},F{P}_3(6)=21)\}}\end{array}\}$$

(25)

For the fourth step, we perform decision making on ${\xi }_2$ : abandon ${\xi }_2$ , the solution set is $S_3$ and accept ${\xi }_2$ and by excluding the solution that passes beyond the established domain, we obtain the solution set

$$S{\prime }_4=\{\begin{array}{c}\{\left\{{\xi }_2\right\},F{P}_3(2)=5)\},\{\{{\xi }_5,{\xi }_2\},F{P}_3(6)=25)\}\hfill \\ \multicolumn{1}{c}{\{\{{\xi }_1,{\xi }_2\},F{P}_3(5)=17)\}}\end{array}\}$$

(26)

After merging $S_3,S{\prime }_4$ , we obtain the solution set

$$S_4=\left\{\begin{array}{c}\{\left\{\varnothing \right\},F{P}_3(0)=0)\},\{\left\{{\xi }_2\right\},F{P}_4(2)=5)\}\hfill \\ \multicolumn{1}{c}{\{\left\{{\xi }_1\right\},F{P}_4(3)=12)\},\{\left\{{\xi }_5\right\},F{P}_4(4)=20)\}}\\ \multicolumn{1}{c}{\{\{{\xi }_1,{\xi }_2\},F{P}_3(5)=17)\},\{\{{\xi }_5,{\xi }_2\},F{P}_3(6)=25)\}}\\ \multicolumn{1}{c}{\{\{{\xi }_1,{\xi }_5\},F{P}_4(7)=32)\}}\end{array}\right\}$$

(27)

From $S_4$ , $F{P}_4(7)=32$ can be easily obtained as the optimal solution, and the optimal energy-saving solution set is $\{{\xi }_1,{\xi }_5\}$ . The main steps of the DPS algorithm are given as follows.

Algorithm 1

DPS.

(1)	For i = 1 to N− 1 do
(2)		$S\prime =S$ ;
(3)		u =  $|S\prime |$ ;
(4)		For j = 1 to u do
(5)			If ${\mathrm{\Omega }}_{i-1,j}+{\xi }_i[C]\le \mathrm{\Omega }$ then
(6)				${\mathrm{\Omega }}_{i-1,j}={\mathrm{\Omega }}_{i-1,j}+{\xi }_i[C];F{P}_i({\mathrm{\Omega }}_{i,j})=F{P}_i({\mathrm{\Omega }}_{i,j})+{\xi }_i[C]$
(7)				k = 0;
(8)				While ${\mathrm{\Omega }}_{i-1,k}\le {\mathrm{\Omega }}_{i,j}$ and $F{P}_{i-1}({\mathrm{\Omega }}_{i-1,k})<F{P}_i({\mathrm{\Omega }}_{i,j})$ do
(9)				k = k + 1;
(10)				End while
(11)				If k < u and ${\mathrm{\Omega }}_{i-1,k}\ge {\mathrm{\Omega }}_{i,j}$ $F{P}_{i-1}({\mathrm{\Omega }}_{i-1,k})<F{P}_i({\mathrm{\Omega }}_{i,j})$ then
(12)				$S\prime =S\prime -S{\prime }_k$ ;
(13)				Else if k = u then
(14)				$S{\prime }_j=S{\prime }_j\cup {\xi }_i$ ;
(15)				End if
(16)			End if
(17)		End for (j)
(18)		$S=\mathrm{Merge}(S\prime ,S)$ ;
(19)	End for (i)
(20)	Output(S);

Analysis of the DPS algorithm

We denote the power consumption of each task by ${\xi }_i[P]$ . The space complexity of the DPS algorithm is determined as $\sum _{0<i<n-1}\left|S_i\right|=\sum _{0<i<n-1}{2}^i=2^n-1$ and is $\mathrm{O}(2^n)$ . If the generation of $S_i$ by $S_{i-1}$ requires a time $\Phi \left(\left|S_{i-1}\right|\right)$ , then the calculated total time of $S_1,S_2,\dots ,S_{n-1}$ is $\Phi (\sum \left|S_{i-1}\right|)$ . However, there exists $\left|S_i\right|\le 2^i$ such that the total number of operations of the $S_i$ tuple ${\xi }_i$ and its time cost ${\xi }_i[C]$ are expressed as integers. Therefore, the elements in each of the ordered pairs $S_i$ should be integers, which yields $\left|S_i\right|\le 1+\sum _{0<i<n-1}{\xi }_i[P]$ and $\left|S_i\right|\le 1+min\{\sum _{0<i<n-1}{\xi }_i[C],\mathrm{\Omega }\}$ . In this case, the time and space complexity of DPS is

$$O(min\{2^n,n\sum _{0<i<n}{\xi }_i[C],n\mathrm{\Omega }\})$$

(28)

The above analysis indicates that the performance of the DPS algorithm is unsatisfactory when n is large. However, viewed from the perspective of practical use, the number of real-time scheduling tasks for mobile portable devices is limited. According to statistics obtained for the MWatch health-monitoring wristwatch in the working state, in a period of 1024 clock cycles, the hard real-time tasks generated by the system range from 0 to 7, which indicates that the most serious scheduling calculations for the current system are 2⁷ = 128, which is acceptable. In practice, a stricter and finer rule can eliminate a large number of unnecessary intermediate results in advance, and the algorithm converges rapidly. ¹⁹

We further discuss the functioning of hard real-time scheduling algorithms based on the DPS algorithm, as follows. First, we fully sort the hard real-time task set ${\mathrm{\Gamma }}_{\tau }({\xi }_1,{\xi }_2,\dots ,{\xi }_n)$ according to the deadline and obtain the scheduling tasks set ${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ . Second, we apply the DPS algorithm to process ${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}$ and obtain $\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ . Finally, we update $\mathrm{\Gamma }$ according to the scheduling result. If ${\mathrm{\Gamma }}_{\tau }$ is null, the algorithm ends; otherwise, the above-mentioned steps are repeated. This algorithm is denoted herein as the hierarchical reliability-driven scheduling (HRDS) algorithm. The steps of the HRDS algorithm are given as follows.

Algorithm 2

HRDS.

INPUT: ${\mathrm{\Gamma }}_{\tau }({\xi }_1,{\xi }_2,\dots ,{\xi }_n)$ , $S=\varnothing$
(1)	${\tau }_1=\tau$ , ${\tau }_2={\xi }_1[R]+{\xi }_1[D]-{\xi }_1[C]$ ;
(2)	${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}={\sigma }_{R\ge {\tau }_1\wedge T+D\le {\tau }_2}(\mathrm{\Gamma })=\left\{\xi |\xi \in \mathrm{\Gamma }\wedge \xi \left[R\right]\ge {\tau }_1\wedge \xi \left[\mathrm{T}\right]+\xi \left[\mathrm{D}\right]\le {\tau }_2\right\}$
(3)	$S=S\cup \mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)=\mathrm{DPS}({\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2})$
(4)	If ${\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}-\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)\ne \varnothing$
(5)		${\mathrm{\Gamma }}_{\tau }({\xi }_1,{\xi }_2,\dots ,{\xi }_n)={\mathrm{\Gamma }}_{{\tau }_1,{\tau }_2}-\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$
(6)		Repeat steps (1) to (4);
(7)	END IF
OUTPUT( $S$ )

Theorem 5

For the schedulable task set $S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ , the output S after completion of the HRDS algorithm is an optimal energy-saving scheduling, that is, $S=\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ .

Proof

From the arithmetic operation process, we observe that $S=S_1\cup S_2\cup ,\dots ,S_m$ and $S_k=\mathrm{OPE}{S}_{{\mathrm{\Gamma }}_{\tau ,\delta }}({\xi }_1,{\xi }_2,\dots ,{\xi }_r)$ . For any tuple, ${\xi }_i$ must appear in a subset $S_j$ assuming ${\xi }_i\in S{\prime }_j$ , $S\prime =S_1\cup S_2\cup ,\dots ,S{\prime }_j,\dots ,S_m$ exists, and $P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(S)\ge P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(S\prime )$ . This statement indicates that $P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(S)\ge P{C}_{S{C}_{{\mathrm{\Gamma }}_{\tau ,\delta }}}(S\prime )$ , which obviously contradicts the nature of the DPS algorithm discussed earlier, thus proving the energy-saving optimality of the HRDS algorithm from a negative perspective.

Experimental and simulation results

Through “Key technology of a mobile health-monitoring watch” project, we performed a number of comparative experiments using the proposed algorithm in the mobile-embedded platform shown in Figure 4 and fully verified its effectiveness and feasibility in this platform. The platform chip is based on the GainSpan GS2011M module, which uses an ARM^® Cortex^® M3 two-core CPU, where one core is used for Wi-Fi wireless communications and the other for Application processing. The hard real-time tasks listed in Table 2 were performed during stress testing of the algorithm.

Figure 4.

Real-time system energy consumptions of the GS2011M-based health wristwatch.

Table 2.

Real-time process of the GS2011M health-monitoring platform.

Task number	Task function	Operating time (µs)	Operating cycle (ms)	Deadline (µs)
T1	Touch screen driver	125	20	1000
T2	LED switches	150	10	1000
T3	Power supply monitoring	28	8000	9000
T4	Signal monitoring	10	8000	9000
T5	FASH driver	65	20	1000
T6	ECG module control	20	No	5000
T7	SpO2 module control	15	No	5000
T8	ECG data reading and writing	75	50	500
T9	SpO2 data reading and writing	75	50	500
T10	Infrared light driver	15	20	100
T11	Pulse driver	12	200	100
T12	Power supply voltage regulator	28	No	9000

LED: light-emitting diode; ECG: electrocardiography.

Table 3 shows the real-time process set abstract for the real-time task set. A portion of the task exists because the release time is random, and another portion of the task is released in accordance with the fixed operating cycle. Thus, the task of release time must be treated as a random time for dynamic processing. The system maintains a queue $S$ that has been scheduled and is waiting to run and an EDF queue $\mathrm{\Gamma }$ that waits for scheduling. When $\mathrm{\Gamma }$ is nonempty, the element $\xi$ is selected from the header of $\mathrm{\Gamma }$ to perform DPS scheduling. If the optimal scheduling is satisfied, $\xi$ is moved from $\mathrm{\Gamma }$ to $S$ and so on until it is empty. Because the task ${\xi }_6,{\xi }_7,{\xi }_{11}$ with a high-energy consumption factor always maintains priority in processing of the HRDS scheduling algorithm, although the energy consumption of ${\xi }_6,{\xi }_7,{\xi }_{11}$ accounts for nearly 1/2 of the total energy consumption of the system, the energy consumption of the system decreases rapidly, and thus, the advantages of HRDS scheduling algorithm are quite obvious.

Table 3.

Real-time process set abstracted as a real-time task set.

$\mathrm{\Gamma }$	R	T	C	P	D	$\rho$
${\xi }_1$	${\lambda }_1$	${\tau }_1$	125	25	1000	0.20
${\xi }_2$	${\lambda }_2$	${\tau }_2$	150	40	1000	0.27
${\xi }_3$	${\lambda }_3$	${\tau }_3$	28	4	9000	0.14
${\xi }_4$	${\lambda }_4$	${\tau }_4$	10	4	9000	0.40
${\xi }_5$	${\lambda }_5$	${\tau }_5$	65	4	1000	0.06
${\xi }_6$	${\lambda }_6$	${\tau }_6$	20	35	5000	1.75
${\xi }_7$	${\lambda }_7$	${\tau }_7$	15	40	5000	2.67
${\xi }_8$	${\lambda }_8$	${\tau }_8$	75	5	500	0.07
${\xi }_9$	${\lambda }_9$	${\tau }_9$	75	3	500	0.04
${\xi }_{10}$	${\lambda }_{10}$	${\tau }_{10}$	15	3	100	0.20
${\xi }_{12}$	${\lambda }_{11}$	${\tau }_{11}$	12	30	100	2.50
${\xi }_{13}$	${\lambda }_{12}$	${\tau }_{12}$	28	6	9000	0.21

Figure 4 shows the energy consumption curves of the GS2011M mobile platform environment in terms of the kernel implementing the EDF scheduling algorithm and the HRDS scheduling algorithm. According to the data, the energy consumption of the device is significantly reduced with the HRDS scheduling algorithm, and the average power consumption is only 37% of that with the EDF algorithm. The main reason for this result is the high power consumption of the external equipment of the operating environment, which accounts for 79% of the total system power consumption, and thus, the actual effect of using the HRDS algorithm is significant.

We simulated the above environment with the EDF scheduling algorithm and the HRDS scheduling algorithm on the MATLAB platform and increased the number of hard real-time processes to 100. Figure 5 presents a comparison of the simulation data. In this case, compared with the actual environment, the data effect is slightly worse, mainly because the number of tasks has increased, and therefore, CPU idle time is reduced and the ratio of peripheral power consumption to CPU power consumption is decreased. However, compared with the energy consumption when using the EDF algorithm, the average energy consumption with the HRDS algorithm is substantially less and is only 61% of that of the EDF algorithm. Relatively, the effect is highly significant. ²⁰

Figure 5.

MATLAB simulation of real-time system energy consumption.

Conclusion

The main goal of current hard real-time scheduling of periodic and non-periodic tasks is to save energy while ensuring the real-time completion of tasks. In this article, we discussed the nature and effect of the energy consumption factor in the case of peripheral energy loss sensitivity. In addition, we introduced the basic idea of the algorithm and its basic theory and proposed an energy-saving priority scheduling algorithm. The results from the experiments and simulations show that HRDS can ensure real-time scheduling and minimize energy consumption in the case of schedulable tasks. However, because the volume of the calculation is somewhat large, if the scale increases with the problem, it is expected to cause greater overhead to the system.