Lei Mo

Q I Zhou

Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems

Keywords: Networked Systems, Task Triplication and Mapping, DVFS, Problem Linearization and Decomposition

Energy efficiency, real-time response, and data transmission reliability are important objectives during networked systems design. This paper aims to develop an efficient task mapping scheme to balance these important but conflicting objectives. To achieve this goal, tasks are triplicated to enhance reliability and mapped on the wireless nodes of the networked systems with Dynamic Voltage and Frequency Scaling (DVFS) capabilities to reduce energy consumption while still meeting real-time constraints. Our contributions include the mathematical formulation of this task mapping problem as mixed-integer programming that balances node energy consumption, enhancing data reliability, under real-time and energy constraints. Compared with the State-of-the-Art (SoA), a joint-design problem is considered in this paper, where DVFS, task triplication, task allocation, and task scheduling are optimized concurrently. To find the optimal solution, the original problem is linearized, and a decomposition-based method is proposed. The optimality of the proposed method is proved rigorously. Furthermore, a heuristic based on the greedy algorithm is designed to reduce the computation time. The proposed methods are evaluated and compared through a series of simulations. The results show that the proposed triplication-based task mapping method on average achieves 24.84% runtime reduction and 28.62% energy saving compared to the SoA methods.

INTRODUCTION

Networked systems, e.g., Wireless Sensor and Actuator Networks (WSAN) or Cyber-Physical Systems (CPS), monitor and control the physical world using wireless nodes, equipped with sensors, controllers, and actuators, supporting several functions of system applications [START_REF] Khaitan | Design techniques and applications of cyber-physical systems: a survey[END_REF][START_REF] Mo | Event-driven joint mobile actuators scheduling and control in cyber-physical systems[END_REF]. From the hardware perspective, wireless nodes are usually energy-constrained, especially when they are supplied by batteries. To reduce energy consumption, modern hardware platforms are enhanced with Dynamic Voltage and Frequency Scaling (DVFS) [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF][START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF], able to adjust the supply voltage and the clock frequency of the processors, where task execution takes place. From the software perspective, system applications usually consist of several dependent tasks that exchange data. In-network processing is typically used to reduce network traffic [START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF]. Following the "Fog/Edgecomputing" model [START_REF] Aazam | Deploying fog computing in industrial Internet of things and industry 4.0[END_REF][START_REF] Guo | A mobile-assisted edge computing framework for emerging IoT applications[END_REF][START_REF] Liu | Data placement for multi-tenant data federation on the cloud[END_REF], instead of collecting and sending all data to a remote Base Station (BS), a part of the data processing is done on the wireless nodes, reducing the amount of data sent to the BS. Hence, sensing, processing, and controlling tasks, and data transmissions should be executed in a real-time and energy-efficient manner, meeting the time and the energy constraints of the system application, in order to improve the overall system performance (e.g., enhancing federated learning in mobile edge computing) [START_REF] Tariq | Energy-aware scheduling of streaming applications on edge-devices in IoT-based healthcare[END_REF][START_REF] Yao | Enhancing federated learning in fog-aided IoT by CPU frequency and wireless power control[END_REF].

Meanwhile, wireless nodes have become susceptible to attacks [START_REF] Sikder | A survey on sensor-based threats to Internet-of-Things (IoT) devices and applications[END_REF], and data transmissions should be reliable. During a False Data Injection (FDI) attack [START_REF] Manandhar | Detection of faults and attacks including false data injection attack in smart grid using Kalman filter[END_REF], an attacker compromises the data to obtain manipulated data that can bypass the basic "faulty data" detection mechanisms. An FDI attack can be implemented by compromising physical sensors and the sensor communication network [START_REF] Mode | Impact of false data injection attacks on deep learning enabled predictive analytics[END_REF]. Such attacks may lead to significant costs due to unplanned failures or loss of human lives in safety-critical applications, e.g., in predictive maintenance systems used in industry 4.0 the attack can propagate from the sensor to the machine learning part and fool the system by predicting a delayed asset failure or maintenance interval [START_REF] Mode | Impact of false data injection attacks on deep learning enabled predictive analytics[END_REF]. Common countermeasure methods for FDI are based on contingency analysis [START_REF] Mo | Cyber-physical security of a smart grid infrastructure[END_REF]. To analyze the contingencies, state estimation (e.g., Kalman filter) [START_REF] Chen | Evaluation of reinforcement learning-based false data injection attack to automatic voltage control[END_REF] is usually used to model the system's dynamics. Thus, the estimation errors are influenced by the accuracy of the system model and the length of the historical data (i.e., time window size). Considering a system is executed under real-time constraints, potentially only parts of the data can be analyzed within the available time. An alternative to the aforementioned methods is to apply task replication. By replicating tasks, data reliability is enhanced, while knowledge of the system model is not required. Executing task replicas on different wireless nodes provides redundant information on the receiver node, which can correct any information obtained by a compromised sensor or communication network due to the FDI.

Overall, energy efficiency, real-time application execution and reliable transmission are crucial goals in the networked systems [START_REF] Lin | A survey on energy-efficient strategies in static wireless sensor networks[END_REF], and they are significantly affected by way of deploying tasks over the wireless nodes. The way allocating tasks affects the number of required data transmissions. The fewer data is exchanged among the nodes, the lower the energy consumption and time for transmissions, and the probability of the data being attacked during the transmission. However, not all tasks can be assigned on the same node, due to task requirements for specific sensors or actuators, and the application's real-time constraint. Task replication can occur when tasks are not assigned on the same nodes to protect the data from attacks. However, task replication also affects energy consumption and real-time execution. Furthermore, an asymmetric task allocation will deplete the energy budget of some nodes, leading to network connectivity issues. Therefore, task replication and deployment should be jointly addressed to achieve energy balance, under real-time and energy constraints.

Mapping tasks on a single platform, with one or several processors, are the well-known problems, e.g., task mapping to minimize energy consumption considering DVFS [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF][START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF][START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF]] and to improve system reliability using task replication [START_REF] Haque | On reliability management of energy-aware real-time systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Zhang | Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[END_REF]. However, works to address task deployment over different platforms, e.g., wireless nodes, considering task mapping, DVFS, reliability, and real-time constraints are rare. On the one hand, networked approaches focusing on task mapping [START_REF] Billet | From task graphs to concrete actions: a new task mapping algorithm for the future Internet of Things[END_REF][START_REF] Edalat | An auction-based strategy for distributed task allocation in wireless sensor networks[END_REF][START_REF] Li | Efficient allocation of resources in multiple heterogeneous wireless sensor networks[END_REF][START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF][START_REF] Tian | Cross-layer collaborative in-network processing in multihop wireless sensor networks[END_REF] usually assume that the task results are reliable, as long as the task execution process is finished and the task data is transmitted to the destination, before the task deadline. On the other hand, networked approaches focusing on reliability use false data detection and correction, which are based on state estimation [START_REF] Chen | Evaluation of reinforcement learning-based false data injection attack to automatic voltage control[END_REF][START_REF] Manandhar | Detection of faults and attacks including false data injection attack in smart grid using Kalman filter[END_REF][START_REF] Mo | Detecting integrity attacks on SCADA systems[END_REF][START_REF] Ye | Summation detector for false data-injection attack in cyber-physical systems[END_REF]. Compared with the State-of-the-Art (SoA), this work addresses the problem of mapping dependent tasks on wireless nodes with DVFS to balance the energy consumption, under real-time and energy constraints. The main contributions of this paper are summarized as follows:

(1) Task triplication scheme and DVFS scheme are integrated into the task mapping process to enhance data transmission reliability and to exploit the trade-off between task execution time and energy consumption, respectively. We formulate the mapping of tasks on the wireless nodes as a Mixed-Integer Non-Linear Programming (MINLP), taking into account the application and the system constraints (e.g., task deadline, task dependencies, data routing, node type, and node energy). Nonlinear items are caused by the product of optimization variables related to frequency assignment, task allocation, and task triplication decisions. These items are replaced by auxiliary variables and additional linear constraints, so as to transform the MINLP problem into a Mixed-Integer Linear Programming (MILP), without degrading the quality of the solution. [START_REF] Bai | Collaborative actuation of wireless sensor and actuator networks for the agriculture industry[END_REF] We propose an Optimal Reliability Task Mapping (ORTM) algorithm based on Benders decomposition to efficiently and optimally solve the transformed problem. The ORTM algorithm decomposes the original problem into two smaller easier-to-solve problems. It solves them iteratively, by using the solution of one problem in the other. The first problem is an Integer

Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:3

Linear Programming (ILP) for task allocation, task triplication, and frequency assignment. The second problem is a Linear Programming (LP) for task scheduling. By iterating the problems, the optimality of the solution is guaranteed. We also design a novel Heuristic Reliability Task Mapping (HRTM) algorithm based on the greedy approach. Compared with the ORTM algorithm, the HRTM algorithm removes the iteration process and solves the problems sequentially. Therefore, the computation time of the HRTM algorithm is significantly reduced. (3) Finally, we perform extensive simulations to analyze the solution quality, the computation time, and the scalability of the proposed task mapping scheme and the proposed ORTM and HRTM algorithms. The results show that the proposed task mapping scheme outperforms other task mapping schemes in terms of data transmission reliability and node energy efficiency.

In addition, the ORTM algorithm finds the optimal solution with reduced computation time (24.84% on average), compared to SoA optimal methods, and the HRTM algorithm runs ∼100 times faster than the ORTM algorithm with an average cost of 26.35% in energy efficiency.

The remainder of this paper is organized as follows. Section 2 discusses the related work. Section 3 presents the system model, and Section 4 formulates the task mapping problem. Section 5 and Section 6 design the optimal and the heuristic algorithms, respectively. Finally, Section 7 shows the simulation results, and Section 8 concludes this work.

RELATED WORK

Table 1 depicts some representative SoA task mapping approaches targeting a single platform, i.e., an Embedded System (ES), and several distributed platforms, i.e., a Networked System (NS). The tasks can be Independent (I) or Dependent (D). The optimization variables include Task Allocation (TA), Task Scheduling (TS), Task Replicas (TR), and Frequency Assignment (FA). During the task mapping process, constraints regarding Energy Supply (E) and Real-Time (T) can exist. To enhance data reliability, methods based on task Replication (R) and State estimation (S) are used. According to different problem structures and system requirements, Optimal (O) and Heuristic (H) algorithms are designed to solve the corresponding problems.

For embedded systems, approaches exist that focus on minimizing the energy consumption or minimizing the task makespan under energy supply and real-time constraints [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF][START_REF] Emeretlis | Static mapping of applications on heterogeneous multi-core platforms combining logic-based Benders decomposition with integer linear programming[END_REF][START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF][START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF][START_REF] Raravi | Task assignment algorithms for heterogeneous multiprocessors[END_REF]. Since the optimization variables of task allocation and frequency assignment are binary, the corresponding task mapping problems are usually described as Mixed-Integer Programming (MIP). For independent tasks, the task mapping problem is modeled as an MINLP in [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF]. By relaxing the binary variables to continuous variables, the problem is transformed into a convex problem and is solved by the interior point method. A similar task mapping problem without DVFS but with task migration is studied in [START_REF] Raravi | Task assignment algorithms for heterogeneous multiprocessors[END_REF], where the MILP-based task mapping problem is first relaxed to two subproblems, and then the subproblems are solved by the polynomial-time methods. For dependent tasks, additional variables and constraints are introduced into the problem to describe the dependency between the tasks. The task mapping problem is described by an MINLP in [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. The nonlinear items, which are caused by the quadratic function, can be approximated by a linear function, and then the relaxed MILP problem is solved by the B&B method [START_REF] Boyd | Branch and bound methods[END_REF]. DVFS is combined with Dynamic Power Management (DPM) in [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF] to enhance energy efficiency. The task mapping problem is formulated as an MILP and is solved according to the commercial solver, such as CPLEX. In [START_REF] Emeretlis | Static mapping of applications on heterogeneous multi-core platforms combining logic-based Benders decomposition with integer linear programming[END_REF], each processor has a fixed frequency level, and, thus, the task mapping problem is an MILP, which can be optimally solved by a hybrid algorithm based on Benders decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF]. However, reliability is not considered in these works.

Task replication techniques have been widely used in embedded systems to deal with task reliability problems [START_REF] Haque | On reliability management of energy-aware real-time systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Zhang | Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[END_REF]. By replicating the tasks, the system's reliability can be improved as it is extremely unlikely to have errors on two or more copies at the same time. In [START_REF] Haque | On reliability management of energy-aware real-time systems through task replication[END_REF], full replication is used, i.e., each task is replicated once at least. With more tasks being replicated, higher reliability is achieved. To enhance task reliability and reduce energy consumption, energy-efficient fault-tolerant scheduling is designed in [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF] considering parallel task execution on processors. A similar problem is considered in [START_REF] Zhang | Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[END_REF] and a bi-objective genetic algorithm is proposed to balance two conflicting objectives: low energy consumption and high task reliability. However, task mapping approaches, focusing on a single platform (embedded systems), usually assume that the data communication cost is very small compared to the task execution cost. Thus, no data communication cost is considered during task replication and mapping. However, the approaches focusing on networked systems, where the platforms are distributed, additional energy and time are required by the nodes for data transmission and reception, which restricts DVFS and task replication options.

For the network systems, since the tasks are usually dependent [START_REF] Billet | From task graphs to concrete actions: a new task mapping algorithm for the future Internet of Things[END_REF][START_REF] Edalat | An auction-based strategy for distributed task allocation in wireless sensor networks[END_REF][START_REF] Li | Efficient allocation of resources in multiple heterogeneous wireless sensor networks[END_REF][START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF][START_REF] Tian | Cross-layer collaborative in-network processing in multihop wireless sensor networks[END_REF], it is crucial to reduce the communication and computation costs (energy and time) on the nodes. The energyaware task mapping problem is considered in [START_REF] Billet | From task graphs to concrete actions: a new task mapping algorithm for the future Internet of Things[END_REF][START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF] to minimize the energy consumption of the nodes, and the problem is described by an Integer Non-Linear Programming (INLP). The original problem is first transformed into an ILP, and then solved by the greedy algorithm. The problem of maximizing the overall network lifetime under energy supply or task deadline constraints is considered in [START_REF] Edalat | An auction-based strategy for distributed task allocation in wireless sensor networks[END_REF][START_REF] Li | Efficient allocation of resources in multiple heterogeneous wireless sensor networks[END_REF]. Based on the problem structure, a game-theoretic approach is proposed in [START_REF] Edalat | An auction-based strategy for distributed task allocation in wireless sensor networks[END_REF] to perform distributed computing, and a heuristic is designed in [START_REF] Li | Efficient allocation of resources in multiple heterogeneous wireless sensor networks[END_REF] to enhance system response time. However, DVFS is not taken into account in the above studies. Some works consider nodes with DVFS capabilities. In [START_REF] Tian | Cross-layer collaborative in-network processing in multihop wireless sensor networks[END_REF], the node energy consumption is optimized by determining the frequency-to-task assignment and the task-to-node allocation. This problem is formulated as an MINLP and solved by heuristics. The above studies mainly focus on minimizing the energy consumption of the nodes, without considering reliability. The task results are assumed to be corrected if the execution and transmission of the tasks are finished before the deadlines. Approaches exist that focus on detecting FDI attacks on networked systems, based on state estimation. In [START_REF] Manandhar | Detection of faults and attacks including false data injection attack in smart grid using Kalman filter[END_REF], a Kalman Filter (KF) is used to estimate system states and a 𝜒 2 -detector is employed to evaluate the discrepancies between the estimated data and the measured data, so as to detect the existence of FDI. In [START_REF] Mo | Detecting integrity attacks on SCADA systems[END_REF], based on the KF and 𝜒 2 -detector combination, a Linear-Quadratic-Gaussian (LQG) controller is used to improve the resilience of the system to against FDI. To improve the success rate of detecting the FDI attacks, a summation (SUM) detector is proposed in [START_REF] Ye | Summation detector for false data-injection attack in cyber-physical systems[END_REF]. Compared with the 𝜒 2 detector, the SUM detector not only utilizes the current compromise information but also collects all historical information to reveal the threat. The Probability Density Functions (PDF) of measurements and control commands, and their confidence intervals, are estimated using historical records in [START_REF] Chen | Evaluation of reinforcement learning-based false data injection attack to automatic voltage control[END_REF]. If the values exceed a certain level, the measurements/control commands are re-generated by a Maximum Likelihood Estimation (MLE). However, these methods are based on state estimation, requiring knowing the system model in advance (e.g., state transition matrix 𝑨, input matrix 𝑩, and measurement matrix 𝑪), and thus, the accuracy of the used system model affects the stability of the system. Furthermore, real-time and energy supply constraints are not considered, and task allocation and scheduling decisions are fixed, since a remote Base Station (BS) is employed for processing the data from the wireless nodes, with the aim to minimize the estimation/control errors.

The aforementioned works address task mapping either on single platforms, focusing on minimizing energy consumption for computation, potentially including task replication, or on distributed platforms, minimizing the computation and the communication costs of the nodes for the networked systems. This work belongs to the second category and enhances the existing approaches by proposing a task mapping method that considers task replication and DVFS, under real-time and energy constraints, without requiring knowledge of the system model.

APPLICATIONS AND SYSTEM MODEL

Motivational Example

We will use the example of Fig. 1 to describe and motivate our approach. Fig. 1 depicts a part of a networked control system with six wireless nodes {𝜃 1 , . . . , 𝜃 6 }, used for applications such as smart grid [START_REF] Li | Multicast routing for decentralized control of cyber physical systems with an application in smart grid[END_REF], fire detection [START_REF] Ota | ORACLE: mobility control in wireless sensor and actor networks[END_REF], home automation [START_REF] Yeh | Autonomous light control by wireless sensor and actuator networks[END_REF], and precision agriculture [START_REF] Bai | Collaborative actuation of wireless sensor and actuator networks for the agriculture industry[END_REF]. Nodes 𝜃 1 , 𝜃 2 and 𝜃 3 are equipped with sensors, while node 𝜃 4 is equipped with an actuator to monitor and control the physical variables, e.g., the voltage, current or phase in the grid [START_REF] Manandhar | Detection of faults and attacks including false data injection attack in smart grid using Kalman filter[END_REF], the temperature of POIs (points of interest) of the forest region [START_REF] Ota | ORACLE: mobility control in wireless sensor and actor networks[END_REF], the illumination intensity for the indoor environment [START_REF] Yeh | Autonomous light control by wireless sensor and actuator networks[END_REF], and the soil moisture in the agriculture [START_REF] Bai | Collaborative actuation of wireless sensor and actuator networks for the agriculture industry[END_REF]. The application needs to monitor the physical variables periodically, process the readings of the sensors to compute the required action, and adjust the outputs of the actuators to control the physical variables. In Fig. 1, 𝜏 1 corresponds to the sensing task, 𝜏 4 corresponds to the data processing task, and 𝜏 7 is the control task. 𝜏 4 requires the sensing data from 𝜏 1 to compute the action of the actuator. 𝜏 7 requires the output of 𝜏 4 to adjust the actuator's output. Therefore, allocating tasks 𝜏 1 and 𝜏 7 is restricted to the nodes equipped with sensors and actuators, respectively. However, the data processing task 𝜏 4 can be placed on any node. Note that, due to the network topology and the task dependencies, the task allocation decisions influence not only the communication and computation energy of the nodes but also the communication time between the tasks.

The FDI attack can be implemented by compromising the sensor communication network [START_REF] Mode | Impact of false data injection attacks on deep learning enabled predictive analytics[END_REF]. Therefore, when dependent tasks, e.g., 𝜏 1 and 𝜏 4 , are executed on different nodes, e.g., 𝜃 1 and 𝜃 5 , there is a possibility to attack the node and alternate 𝜏 1 's output, during its transmission to 𝜏 4 . This work combines the benefits of task mapping with task triplication to improve the reliability of the networked system against FDI attacks. Using task triplication, the data reliability is enhanced, and the influence caused by fault data can be mitigated [START_REF] Kang | Reliability-aware mapping optimization of multi-core systems with mixed-criticality[END_REF], while knowledge of the system model is not required. The redundant information on the receiver node can be used to correct the information obtained by a compromised communication link. For instance, in Fig. Similarly, task 𝜏 4 should be triplicated to enhance the reliability of the data that have to be transmitted to task 𝜏 7 . During the task mapping process, if dependent tasks 𝜏 4 and 𝜏 7 are executed on the same node (e.g., 𝜃 4 ), there is no need to triplicate task 𝜏 4 , since no wireless transmission takes place between 𝜏 4 and 𝜏 7 . However, not all dependent task can be assigned to the same node, due to the task requirements in specific sensors and actuators, e.g., {𝜏 1 → 𝜃 1 , 𝜏 2 → 𝜃 2 , 𝜏 3 → 𝜃 3 , 𝜏 7 → 𝜃 4 }, the energy supply of the nodes and the real-time response of the application. Based on the above discussion, the task allocation and the task triplication problems are coupled and affected by real-time and energy constraints.

System Model

Task

Model. We consider a real-time frame-based application that consists of a task set T with 𝑁 periodic real-time tasks {𝜏 1 , . . . , 𝜏 𝑁 }, which includes the original task, its second and third replicas. The tasks are considered dependent and non-preemptive [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF][START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. Each task 𝜏 𝑖 is described by a tuple {𝑒 𝑖 , 𝑡 𝑎 𝑖 , 𝑡 𝑠 𝑖 , 𝑑 𝑖 , 𝑝 𝑖 }. 𝑒 𝑖 is the number of execution cycles of task 𝜏 𝑖 , measured in Worst-Case Execution Cycles (WCEC). 𝑡 𝑎 𝑖 , 𝑡 𝑠 𝑖 , 𝑑 𝑖 and 𝑝 𝑖 are the arrival time, the start time, the deadline, and the period of task 𝜏 𝑖 , respectively. Without loss of generality, task arrival times are equal to the time instance 0. We assume that the deadline and the period of task 𝜏 𝑖 are equal to 𝐻 , which is given by the frame of the application. The proposed approach can be adapted for task sets with different periods, usually consisting of independent tasks. This can be achieved by unrolling the tasks in the hyper-period (i.e., the least common multiple of all task periods {𝑝 1 , . . . , 𝑝 𝑁 } [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF][START_REF] Mo | Controllable QoS for imprecise computation tasks on DVFS multicores with time and energy constraints[END_REF]), and setting the task arrival time and the task deadline, accordingly. The dependency between the tasks is given by a binary matrix 𝒐 = [𝑜 𝑖 𝑗 ] 𝑁 ×𝑁 . If 𝑜 𝑖 𝑗 = 1, 𝜏 𝑖 precedes 𝜏 𝑗 and 𝜏 𝑗 is the closest task of , respectively, where 𝐶 𝑠 , 𝜌 and 𝐶 𝑑 are the constants depending on the type of processor. We assume that a processor switches to the idle mode immediately when it has no task to execute, and the idle power is 𝑃 0 . The time and energy required for the transition are incorporated into the task execution time and energy [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF] since they are very small compared to the time and energy required for task execution.

PROBLEM FORMULATION

The aim of this work is to balance the energy consumption of the nodes, under real-time and energy constraints, exploiting task mapping, task triplication and DVFS. Therefore, we need to determine 1) which node the task should execute on (task allocation); 2) what voltage/frequency level should be used for the task (voltage/frequency assignment); 3) whether a task needs to be triplicated or not (task triplication); 4) when a task starts its execution (task scheduling). To formulate the task mapping problem, we introduce the following variables: 1) binary variable 𝑞 𝑖𝑘 = 1 if task 𝜏 𝑖 is allocated to node 𝜃 𝑘 , else, 𝑞 𝑖𝑘 = 0; 2) binary variable 𝑐 𝑖𝑙 = 1 if task 𝜏 𝑖 is executed with the voltage/frequency (𝑣 𝑙 , 𝑓 𝑙 ), else, 𝑐 𝑖𝑙 = 0; 3) binary variable ℎ 𝑖 = 1 if task 𝜏 𝑖 is triplicated, else, ℎ 𝑖 = 0; and 4) continuous variable 𝑡 𝑠 𝑖 represents the start time of task 𝜏 𝑖 . We assume that the system runs with a given routing protocol. Therefore, the routing energy cost matrix 𝒓 = [𝑟 𝑚𝑛𝑘 ] 𝑀×𝑀×𝑀 and the routing time matrix 𝒕 = [𝑡 𝑚𝑛 ] 𝑀×𝑀 are known in advance [START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF], where 𝑟 𝑚𝑛𝑘 is the energy consumed of node 𝜃 𝑘 , when routing a unit of data from 𝜃 𝑚 to 𝜃 𝑛 , while 𝑡 𝑚𝑛 is the time required to transmit unit of data from 𝜃 𝑚 to 𝜃 𝑛 . For presentation reasons, let L ≜ {1, . . . , 𝐿}, N ≜ {1, . . . , 𝑁 }, M ≜ {1, . . . , 𝑀 }, M 𝑠 = {1, . . . , 𝑀 𝑠 }, M 𝑎 = {𝑀 𝑠 + 1, . . . , 𝑀 𝑠 + 𝑀 𝑎 }, and G ≜ {1, . . . , 𝐺 }, where 𝐺 is the number of original tasks. The main parameters and variables used in the problem formulation are summarized in Table 2.

Preliminary

4.1.1 Task Triplication Scheme. Since we consider task triplication and task triplication acts on original tasks, we initially analyze the relationship between the allocation and the triplication of original tasks. Let 𝛼 𝑖 = 3𝑖 -2 (1 ≤ 𝑖 ≤ 𝐺) denote the subscript of the original task. Therefore, tasks 𝜏 𝛼 𝑖 +1 and 𝜏 𝛼 𝑖 +2 are the second and third replicas (duplication and triplication) of task 𝜏 𝛼 𝑖 , respectively. If ℎ 𝛼 𝑖 = 0, task 𝜏 𝛼 𝑖 is not triplicated, and thus, we have 𝑒 𝛼 𝑖 +1 = 𝑒 𝛼 𝑖 +2 = 0. As a result, tasks 𝜏 𝛼 𝑖 +1 and 𝜏 𝛼 𝑖 +2 do not exist. They can be removed from the task graph and will not generate any data for the successors or receive any data from the predecessors.

To determine the value of ℎ 𝛼 𝑖 , let's consider the simple example shown in Fig. 1, where 𝜏 1 , 𝜏 4 and 𝜏 7 are the original tasks. Let S 1 = {𝜏 1 , 𝜏 4 } and S 2 = {𝜏 4 , 𝜏 7 }. Based on the elements in the task sets S 1 and S 2 , we get the following four cases: 1) Tasks in S 1 are allocated to different nodes, while For 𝐶𝑎𝑠𝑒 1 , 𝜏 1 is triplicated, while 𝜏 4 is not triplicated (ℎ 1 = 1 and ℎ 4 = 0). For 𝐶𝑎𝑠𝑒 2 , 𝜏 1 and 𝜏 4 are triplicated (ℎ 1 = ℎ 4 = 1). For 𝐶𝑎𝑠𝑒 3 , 𝜏 1 and 𝜏 4 are not triplicated (ℎ 1 = ℎ 4 = 0). For 𝐶𝑎𝑠𝑒 4 , 𝜏 4 requires triplication, since 𝜏 4 and 𝜏 7 are allocated to different nodes. In addition, 𝜏 1 is triplicated, as 𝜏 4 , 𝜏 5 and 𝜏 6 are allocated to different nodes. The decision regarding the tasks in S 2 propagates to 𝜏 1 , which needs to be also triplicated, even if the tasks in S 1 are allocated to the same node. From the above Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:9

example, we observe that the triplication decision is not only related to the allocation of original tasks, but also to the allocation of the replicas.

To formulate the relation between task triplication and task allocation decisions, we introduce a parameter 𝑁 𝛼 𝑖 and an auxiliary variable 𝑀 𝛼 𝑖 for the original task 𝜏 𝛼 𝑖 , where 𝑁 𝛼 𝑖 represents the number of tasks that dependent on task 𝜏 𝛼 𝑖 , while 𝑀 𝛼 𝑖 represents the number of dependent tasks that are assigned to the same node as task 𝜏 𝛼 𝑖 . Based on the dependency between the tasks, the values of 𝑁 𝛼 𝑖 and 𝑀 𝛼 𝑖 are given by:

𝑁 𝛼 𝑖 = 𝑗 ∈N 𝑜 𝛼 𝑖 𝑗 , ∀𝑖 ∈ G, (1)
𝑀 𝛼 𝑖 = 𝑗 ∈N 𝑘 ∈M 𝑜 𝛼 𝑖 𝑗 𝑞 𝛼 𝑖 𝑘 𝑞 𝑗𝑘 , ∀𝑖 ∈ G, (2)
In Fig. 1, as 𝜏 1 and 𝜏 4 are original tasks, we have 𝑁 1 = 3 and 𝑁 4 = 1 for both cases due to

𝒐 =               0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0               .
For 𝐶𝑎𝑠𝑒 1 , we have 𝑀 1 ≤ 2 as 𝜏 1 and 𝜏 4 are assigned to different nodes, and 𝑀 4 = 1 as 𝜏 4 and 𝜏 7 are assigned to the same node. Similarly, we get 𝑀 1 ≤ 2 and 𝑀 4 = 0 for 𝐶𝑎𝑠𝑒 2 ; 𝑀 1 = 3 and 𝑀 4 = 1 for 𝐶𝑎𝑠𝑒 3 ; 𝑀 1 ≤ 2 and 𝑀 4 = 0 for 𝐶𝑎𝑠𝑒 4 . Since 𝑀 𝛼 𝑖 ≤ 𝑁 𝛼 𝑖 , based on the triplication decisions regarding the tasks 𝜏 1 and 𝜏 4 , we can get the following conclusion: if 𝑀 𝛼 𝑖 = 𝑁 𝛼 𝑖 , ℎ 𝛼 𝑖 = 0, else (i.e., 𝑀 𝛼 𝑖 ≤ 𝑁 𝛼 𝑖 -1), ℎ 𝛼 𝑖 = 1. Note that this 𝑖 𝑓 -𝑒𝑙𝑠𝑒 description is not a standard constraint and 𝑀 𝛼 𝑖 is changed with task allocation variable 𝑞 𝑖𝑘 . We introduce the following lemma to determine the value of ℎ 𝛼 𝑖 . Lemma 4.1. Let 𝑥 and 𝑦 denote an integer variable and a binary variable, respectively, where 𝑥 is bounded by 0 ≤ 𝑥 ≤ 𝑚. 𝑚 ≥ 0 and 𝑛 ≥ 0 are the positive integer constants. The case: if 𝑥 = 𝑛 → 𝑦 = 0, else (i.e., 𝑥 ≤ 𝑛 -1), 𝑦 = 1 can be given by the linear constraint 𝑥-𝑛+1 𝑚+1 ≤ 1 -𝑦 ≤ 𝑥+1 𝑛+1 . Proof. If 𝑥 = 𝑛, we have 𝑥-𝑛+1 𝑚+1 > 0 and 𝑥+1 𝑛+1 = 1. Therefore, we get 𝑦 = 0. On the other hand, if 𝑥 ≤ 𝑛 -1, since 𝑥-𝑛+1 𝑚+1 ≤ 0 and 𝑥+1 𝑛+1 < 1, we obtain 𝑦 = 1. □

According to Lemma 4.1, the task triplication decision ℎ 𝛼 𝑖 is determined by the following constraint:

𝑀 𝛼 𝑖 -𝑁 𝛼 𝑖 + 1 𝑁 + 1 ≤ 1 -ℎ 𝛼 𝑖 ≤ 𝑀 𝛼 𝑖 + 1 𝑁 𝛼 𝑖 + 1 , ∀𝑖 ∈ G, (3)
where 𝑁 𝛼 𝑖 and 𝑀 𝛼 𝑖 are given by Eq. ( 1) and Eq. ( 2), respectively.

4.1.2 Node Communication Cost. Let 𝒉 ′ = [ℎ ′ 1 , . . . , ℎ ′ 3𝐺 ] 𝑇 = [1, ℎ 1 , ℎ 1 , . . . ,
𝐸 𝑡 𝑘 = 𝑖 ∈N 𝑗 ∈N 𝑚 ∈M 𝑛 ∈M ℎ ′ 𝑖 ℎ ′ 𝑗 𝑠 𝑖 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 𝑟 𝑚𝑛𝑘 , ∀𝑘 ∈ M. (4)
To execute a task 𝜏 𝑗 , we must collect all the data generated from its previous dependent tasks. If task 𝜏 𝑖 is assigned to node 𝜃 𝑚 , while task 𝜏 𝑗 is assigned to node 𝜃 𝑛 , the time required to transmit the data with size ℎ ′ 𝑖 ℎ ′ 𝑗 𝑠 𝑖 𝑗 , from 𝜃 𝑚 to 𝜃 𝑛 , is ℎ ′ 𝑖 ℎ ′ 𝑗 𝑠 𝑖 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 𝑡 𝑚𝑛 . We assume that the used communication protocol prevents concurrent reception of messages from multiple nodes, avoiding data conflicts. Hence, the time required to collect the data for the execution of task 𝜏 𝑗 is

𝑡 𝑟 𝑗 = 𝑖 ∈N 𝑚 ∈M 𝑛 ∈M ℎ ′ 𝑖 ℎ ′ 𝑗 𝑠 𝑖 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 𝑡 𝑚𝑛 , ∀𝑗 ∈ N . (5)
4.1.3 Task Execution Cost. Since the voltage/frequency level is adjusted in a discrete manner, similar to the previously published work [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF], the time and the energy required to execute task

𝜏 𝑖 with ℎ ′ 𝑖 𝑒 𝑖 cycles are 𝑡 𝑐 𝑖 = 𝑙 ∈ L 𝑐 𝑖𝑙 ℎ ′ 𝑖 𝑒 𝑖 𝑓 𝑙 and 𝐸 𝑐 𝑖 = 𝑙 ∈ L 𝑐 𝑖𝑙 ℎ ′ 𝑖 𝑒 𝑖
𝑓 𝑙 𝑃 𝑐 𝑙 , respectively. On this basis, considering the task allocation decision 𝑞 𝑖𝑘 , the time and the energy required to execute the tasks assigned to node 𝜃 𝑘 are

𝑡 𝑛 𝑘 = 𝑖 ∈N 𝑞 𝑖𝑘 𝑡 𝑐 𝑖 = 𝑖 ∈N 𝑙 ∈L 𝑞 𝑖𝑘 𝑐 𝑖𝑙 ℎ ′ 𝑖 𝑒 𝑖 𝑓 𝑙 , ∀𝑘 ∈ M, (6)
𝐸 𝑛 𝑘 = 𝑖 ∈N 𝑞 𝑖𝑘 𝐸 𝑐 𝑖 = 𝑖 ∈N 𝑙 ∈L 𝑞 𝑖𝑘 𝑐 𝑖𝑙 ℎ ′ 𝑖 𝑒 𝑖 𝑓 𝑙 𝑃 𝑐 𝑙 , ∀𝑘 ∈ M. (7)
Therefore, the computation energy of node 𝜃 𝑘 is

𝐸 𝑑 𝑘 = 𝐸 𝑛 𝑘 + (𝐻 -𝑡 𝑛 𝑘 )𝑃 0 , ∀𝑘 ∈ M, (8)
where 𝐻 -𝑡 𝑛 𝑘 is the idle time of the processor during the scheduling horizon 𝐻 .

Primal Problem

To balance the energy consumption of the nodes and increase the system lifetime and connectivity, we can minimize the maximum energy consumption on a single node. Thus, the objective function is set to 𝐹 = max ∀𝑘 ∈M {(𝐸 The constraints of the problem are described as follows:

(1) Task Allocation Constraints: Note that each task 𝜏 𝑖 is assigned to one node (no task migration), and the tasks requiring nodes equipped with the sensor or actuator are restricted. The original task 𝜏 𝛼 𝑖 and its replicas 𝜏 𝛼 𝑖 +1 and 𝜏 𝛼 𝑖 +2 should not be assigned to the same node. Therefore, we have

𝑘 ∈M 𝑞 𝑖𝑘 = 1, ∀𝑖 ∈ N, (10)
𝑞 𝑖𝑘 = 1, ∀(𝑖, 𝑘) ∈ D, (11)
0 ≤ 𝑞 𝛼 𝑖 𝑘 + 𝑞 𝛼 𝑖 +1𝑘 + 𝑞 𝛼 𝑖 +2𝑘 ≤ 1, ∀𝑖 ∈ G, ∀𝑘 ∈ M, ( 12
)
where D is the set of task and node indexes that have restricted task allocation. (2) Frequency Assignment Constraint: Since each task 𝜏 𝑖 is executed with one voltage/frequency level, we get

𝑙 ∈ L 𝑐 𝑖𝑙 = 1, ∀𝑖 ∈ N . (13)
(3) Task Sequence Constraint: For the dependent tasks (e.g., tasks 𝜏 1 , 𝜏 4 and 𝜏 7 in Fig. 1), no matter if they are assigned to the same node or different nodes, the start time and the end time of tasks is bounded. Therefore, we have

𝑡 𝑠 𝑗 + (1 -𝑜 𝑖 𝑗 )𝐻 ≥ 𝑡 𝑠 𝑖 + 𝑜 𝑖 𝑗 (𝑡 𝑒 𝑖 -𝑡 𝑠 𝑖 ) + 𝑡 𝑟 𝑗 , ∀𝑖 ≠ 𝑗 ∈ N, (14)
J. ACM, Vol. 14) is always satisfied. (4) Task Non-Preemption Constraint: Note that some tasks can be independent in the task set (e.g., tasks 𝜏 1 , 𝜏 2 and 𝜏 3 in Fig. 1). When independent tasks are assigned to the same node, we need to determine their execution sequence. To this end, we introduce a binary variable 𝑢 𝑖 𝑗 . Since each node executes no more than one task at the same time, we get

𝑡 𝑒 𝑖 ≤ 𝑡 𝑠 𝑗 + (2 -𝑞 𝑖𝑘 -𝑞 𝑗𝑘 )𝐻 + (1 -𝑢 𝑖 𝑗 )𝐻, ∀𝑖 ≠ 𝑗 ∈ N, ∀𝑘 ∈ M. ( 15
)
If tasks 𝜏 𝑖 and 𝜏 𝑗 are assigned to the same node (e.g., 𝑞 𝑖𝑘 = 𝑞 𝑗𝑘 = 1), Eq. ( 15) is meaningful, else, Eq. ( 15) is always true. With 𝑞 𝑖𝑘 = 𝑞 𝑗𝑘 = 1, if 𝑢 𝑖 𝑗 = 1 (i.e., 𝜏 𝑖 precedes 𝜏 𝑗 ), we have 𝑡 𝑒 𝑖 ≤ 𝑡 𝑠 𝑗 , else (i.e., 𝑢 𝑖 𝑗 = 0), Eq. ( 15) is always satisfied.

(5) Task Deadline Constraint: The system is periodic, i.e., it operates in rounds [START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF] (scheduling horizon 𝐻 ), where in each round, all the tasks are executed once. Therefore, the constraint related to the task deadline is

𝑡 𝑒 𝑖 ≤ 𝐻, ∀𝑖 ∈ N . (16)
(6) Energy Constraints: Let 𝐸 𝑠 𝑘 , 𝐸 𝑎 𝑘 and 𝐸 𝑟 𝑘 denote the sensing energy of the sensor, the acting energy of the actuator, and the energy supply of the node at the 𝑟 𝑡ℎ round, respectively. Since the total energy consumed by node 𝜃 𝑘 , during the scheduling horizon 𝐻 , should not exceed its energy supply, we get

𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 + 𝐸 𝑠 𝑘 ≤ 𝐸 𝑟 𝑘 , ∀𝑘 ∈ M 𝑠 , (17)
𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 + 𝐸 𝑎 𝑘 ≤ 𝐸 𝑟 𝑘 , ∀𝑘 ∈ M 𝑎 , (18)
𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 ≤ 𝐸 𝑟 𝑘 , ∀𝑘 ∈ M, ∀𝑘 ∉ M 𝑠 , M 𝑎 . ( 19
)

Problem Linearization

Due to the products of binary variables (e.g., 𝑞 𝑖𝑚 𝑞 𝑗𝑛 in Eq. ( 3), ℎ ′ 𝑖 ℎ ′ 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 and 𝑞 𝑖𝑘 𝑐 𝑖𝑙 ℎ ′ 𝑖 in Eq. ( 14), Eq. ( 16)-Eq. ( 19)), the PP is an MINLP problem, which makes it challenging to solve. Theorem 4.1. The task mapping problem of the networked system (i.e., PP) is N P-hard.

Proof. Please refer to [START_REF] Burer | Non-convex mixed-integer nonlinear programming: a survey[END_REF] for the details. □

Linearization is an efficient way to simplify the structure of the problem. To linearize the nonlinear items, we introduce the following lemma. Proof. The inequalities 𝑧 ≤ 𝑥 and 𝑧 ≤ 𝑦 ensure that 𝑧 = 0 if either 𝑥 = 0 or 𝑦 = 0. The inequality 𝑧 ≥ 𝑥 + 𝑦 -1 makes sure that 𝑧 = 1 if both 𝑥 and 𝑦 are set to 1. □

According to Lemma 4.2, we first introduce an auxiliary (binary) variable 𝛽 𝑖𝑚 𝑗𝑛 to replace the nonlinear term 𝑞 𝑖𝑚 𝑞 𝑗𝑛 , and then add the following constraints into the PP:

{𝛽 𝑖𝑚 𝑗𝑛 ≤ 𝑞 𝑖𝑚 , 𝛽 𝑖𝑚 𝑗𝑛 ≤ 𝑞 𝑗𝑛 , 𝛽 𝑖𝑚 𝑗𝑛 ≥ 𝑞 𝑖𝑚 + 𝑞 𝑗𝑛 -1}, ∀𝑖 ≠ 𝑗 ∈ N, ∀𝑚, 𝑛 ∈ M. (20)
Therefore, we have

𝑀 𝛼 𝑖 = 𝑗 ∈N 𝑘 ∈M 𝑜 𝛼 𝑖 𝑗 𝛽 𝛼 𝑖 𝑘 𝑗 . ( 21
)
On this basis, to deal with the nonlinear item ℎ ′ 𝑖 ℎ ′ 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 , we reuse the auxiliary variable 𝛽 𝑖𝑚 𝑗𝑛 . Let 𝛾 𝑖 𝑗 = ℎ ′ 𝑖 ℎ ′ 𝑗 and 𝛿 𝑖𝑚 𝑗𝑛 = 𝛾 𝑖 𝑗 𝛽 𝑖𝑚 𝑗𝑛 . Therefore, if the following constraints are added to the PP:

{𝛾 𝑖 𝑗 ≤ ℎ ′ 𝑖 , 𝛾 𝑖 𝑗 ≤ ℎ ′ 𝑗 , 𝛾 𝑖 𝑗 ≥ ℎ ′ 𝑖 + ℎ ′ 𝑗 -1}, ∀𝑖 ≠ 𝑗 ∈ N, (22)
{𝛿 𝑖𝑚 𝑗𝑛 ≤ 𝛾 𝑖 𝑗 , 𝛿 𝑖𝑚 𝑗𝑛 ≤ 𝛽 𝑖𝑚 𝑗𝑛 , 𝛿 𝑖𝑚 𝑗𝑛 ≥ 𝛾 𝑖 𝑗 + 𝛽 𝑖𝑚 𝑗𝑛 -1}, ∀𝑖 ≠ 𝑗 ∈ N, ∀𝑚, 𝑛 ∈ M, (23)
Eq. ( 4) and Eq. ( 5) can be rewritten as follows:

𝐸 𝑡 𝑘 = 𝑖 ∈N 𝑗 ∈N 𝑚 ∈M 𝑛 ∈M 𝑠 𝑖 𝑗 𝑟 𝑚𝑛𝑘 𝛿 𝑖𝑚 𝑗𝑛 , ∀𝑘 ∈ M, (24)
𝑡 𝑟 𝑗 = 𝑖 ∈N 𝑚 ∈M 𝑛 ∈M 𝑠 𝑖 𝑗 𝑡 𝑚𝑛 𝛿 𝑖𝑚 𝑗𝑛 , ∀𝑗 ∈ N . (25)
Similarly, let 𝜀 𝑖𝑙 = ℎ ′ 𝑖 𝑐 𝑖𝑙 and 𝜂 𝑖𝑙𝑘 = 𝜀 𝑖𝑙 𝑞 𝑖𝑘 . The nonlinear items ℎ ′ 𝑖 𝑐 𝑖𝑙 and ℎ ′ 𝑖 𝑐 𝑖𝑙 𝑞 𝑖𝑘 can be replaced by the auxiliary (binary) variables 𝜀 𝑖𝑙 and 𝜂 𝑖𝑙𝑘 and the following constraints:

{𝜀 𝑖𝑙 ≤ ℎ ′ 𝑖 , 𝜀 𝑖𝑙 ≤ 𝑐 𝑖𝑙 , 𝜀 𝑖𝑙 ≥ ℎ ′ 𝑖 + 𝑐 𝑖𝑙 -1}, ∀𝑖 ∈ N, ∀𝑙 ∈ L, (26)
{𝜂 𝑖𝑙𝑘 ≤ 𝜀 𝑖𝑙 , 𝜂 𝑖𝑙𝑘 ≤ 𝑞 𝑖𝑘 , 𝜂 𝑖𝑙𝑘 ≥ 𝜀 𝑖𝑙 + 𝑞 𝑖𝑘 -1}, ∀𝑖 ∈ N, ∀𝑙 ∈ L, ∀𝑘 ∈ M. (27)
Therefore, Eq. ( 6) and Eq. ( 7) can be rewritten as follows:

𝑡 𝑛 𝑘 = 𝑖 ∈N 𝑙 ∈ L 𝜂 𝑖𝑙𝑘 𝑒 𝑖 𝑓 𝑙 , ∀𝑘 ∈ M, (28)
𝐸 𝑛 𝑘 = 𝑖 ∈N 𝑙 ∈ L 𝜂 𝑖𝑙𝑘 𝑒 𝑖 𝑓 𝑙 𝑃 𝑐 𝑙 , ∀𝑘 ∈ M. (29)
Based on the above analysis, the PP is linearized as follows:

PP1 : min

s.t.

       𝐸 𝑡 𝑘 +𝐸 𝑑 𝑘 𝐸 𝑖𝑛𝑖 𝑘 ≤ 𝜉, ∀𝑘 ∈ M, (3)
, ( 10) -( 19), ( 20), ( 22), ( 23), ( 26), [START_REF] Liu | Data placement for multi-tenant data federation on the cloud[END_REF],

where 𝜉 is an auxiliary variable, and 𝑀 𝛼 𝑖 , 𝐸 𝑡 𝑘 , 𝑡 𝑟 𝑗 , 𝑡 𝑛 𝑘 , and 𝐸 𝑛 𝑘 in constraints are given by Eqs. ( 21), ( 24), ( 25), ( 28) and (29), respectively.

OPTIMAL TASK DEPLOYMENT ALGORITHM

In this section, we propose an Optimal Reliability Task Mapping algorithm, referred to as ORTM, to find the optimal solution for PP1. The basic idea of the ORTM algorithm comes from the Benders decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF]. Instead of considering all the variables and constraints simultaneously, the ORTM algorithm separates the PP1 into smaller, easier-to-solve problems, the Master Problem (MP) and the Slave Problem (SP). Then, the PP1 is solved by iteratively solving the MP and the SP. Note that the PP1 has the following abstract form

PP2 : min 𝒙,𝒚 Φ = 𝒇 𝑇 𝒙 (31) s.t. 𝑨𝒙 ⪯ 𝒃 1 , 𝑪𝒙 + 𝑫𝒚 ⪯ 𝒃 2 ,
where 𝒙 ≜ (𝒒, 𝒄, 𝒖, 𝒉 ′ , 𝜷, 𝜸, 𝜹, 𝜺, 𝜼) and 𝒚 ≜ (𝒕 𝑠 , 𝜉) denote the vectors of binary and continuous variables, respectively. The vector 𝒇 represents the coefficients in the objective function. The matrices 𝑨, 𝑪 and 𝑫 are the coefficients in the constraints. 𝒃 1 (𝒃 2 ) is a 𝑢 (𝑣)-dimensional vector.

Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:13

Based on the structure of PP2, at the 𝑘 𝑡ℎ iteration, the MP and the SP are formulated as follows:

MP : Φ 𝑙 (𝑘) = min 𝒙, Φ Φ (32) s.t.          𝑨𝒙 ⪯ 𝒃 1 , 𝑪 1 : Φ ≥ (𝒇 𝑇 + 𝝀 𝑇 (𝑖)𝑪)𝒙 -𝝀 𝑇 (𝑖)𝒃 2 , 1 ≤ 𝑖 ≤ 𝑚, 𝑪 2 : 0 ≥ λ𝑇 ( 𝑗) (𝑪𝒙 -𝒃 2 ), 1 ≤ 𝑗 ≤ 𝑛, SP : Φ 𝑢 (𝑘) = min 𝒚 ⪰0 𝒇 𝑇 𝒙 (𝑘) (33)
s.t. 𝑪𝒙 (𝑘) + 𝑫𝒚 ⪯ 𝒃 2 ,
where Φ is an auxiliary variable to facilitate the iterations between MP and SP, and 𝒙 (𝑘) is the MP solution at the 𝑘 𝑡ℎ iteration. 𝑪 1 and 𝑪 2 are the sets of constraints called Benders cuts (𝑚 + 𝑛 = 𝑘).

By solving the MP and the SP, we obtain a lower bound, Φ 𝑙 (𝑘), and an upper bound, Φ 𝑢 (𝑘), of Φ * [START_REF] Qian | Joint base station association and power control via Benders' decomposition[END_REF], where Φ * is the optimal value of Φ. The iteration stops when Φ 𝑢 (𝑘) -Φ 𝑙 (𝑘) ≤ 𝜀.

The MP accounts for all the binary variables 𝒙 and the associated portion of the objective function and the constraints of the PP2. The SP includes all the continuous variables 𝒚 and the associated constraints in the PP2. By solving the Dual Slave Problem (DSP) (2) If DSP has a bounded solution 𝝀(𝑘), since 1) Φ(𝑘) < (𝒇 𝑇 + 𝝀 𝑇 (𝑘)𝑪)𝒙 (𝑘) -𝝀 𝑇 (𝑘)𝒃 2 , where Φ(𝑘) is the optimal solution of MP at the 𝑘 𝑡ℎ iteration, and 2) 𝒙 (𝑘) is not the optimal solution of PP2 due to Φ 𝑢 (𝑘) -Φ 𝑙 (𝑘) > 𝜀, the non-optimal solution 𝒙 (𝑘) is excluded by the constraint Φ ≥ (𝒇 𝑇 + 𝝀 𝑇 (𝑘)𝑪)𝒙 -𝝀 𝑇 (𝑘)𝒃 2 . (3) If DSP has an unbounded solution, the SP has no feasible solution under the given solution 𝒙 (𝑘).

DSP : max 𝝀 ⪰0 (𝒇 𝑇 + 𝝀 𝑇 𝑪)𝒙 (𝑘) -𝝀 𝑇 𝒃 2 (34)
However, the SP is feasible if positive variables 𝝃 ≜ [𝜉 𝑖 ] are introduced to relax the constraints.

Based on this idea, we construct a Feasibility Check Problem (FCP) and solve its dual problem (DFCP).

FCP : min

𝒚,𝝃 ⪰0 1 𝑇 𝝃 (35) s.t. 𝑪𝒙 (𝑘) + 𝑫𝒚 ⪯ 𝒃 2 + 𝝃 . DFCP : max λ ⪰0 λ𝑇 (𝑪𝒙 (𝑘) -𝒃 2 ) (36)
s.t.

1 -λ ⪰ 0, 𝑫 𝑇 λ ⪰ 0,
where λ ≜ [ λ𝑖 ] are the Lagrange multipliers. Let 𝝃 (𝑘) and λ(𝑘) be the optimal solutions of FCP and DFCP at the 𝑘 𝑡ℎ iteration, respectively. If the SP is infeasible, this implies that some constraints cannot be satisfied, and thus, their related relaxation variables are non-zero. We have 1 𝑇 𝝃 (𝑘) > 0, and further, 1 𝑇 𝝃 (𝑘) = λ𝑇 (𝑘) (𝑪𝒙 (𝑘) -𝒃 2 ) > 0 due to the strong duality [START_REF] Boyd | Convex optimization[END_REF].

Therefore, the infeasible solution 𝒙 (𝑘) can be excluded by the constraint 0 ≥ λ𝑇 (𝑘) (𝑪𝒙 -𝒃 2 ).

With the constraint Φ ≥ (𝒇 𝑇 + 𝝀 𝑇 (𝑘)𝑪)𝒙 -𝝀 𝑇 (𝑘)𝒃 2 added into 𝑪 1 , or the constraint 0 ≥ λ𝑇 (𝑘) (𝑪𝒙 -𝒃 2 ) added into 𝑪 2 , at the (𝑘 + 1) 𝑡ℎ iteration, the MP is solved again to obtain a new solution 𝒙 (𝑘 + 1) for the next iteration. Theorem 5.1. With a new constraint added to the MP at each iteration, the solution obtained by ORTM converges to the global optimal value Φ * within a finite number of iterations.

Proof. Since the non-optimal and the infeasible solutions of the binary variables 𝒙 are excluded by the constraints 𝑪 1 and 𝑪 2 , and the dimension of 𝒙 is finite, the solution converges to the global optimal value within a finite number of iterations. □

HEURISTIC APPROACH

Note that the ORTM algorithm generates a new constraint at each iteration and adds it to the ILP-based MP. With the number of iterations increasing, the computational complexity and the size of MP also increase. Therefore, the computational complexity of the ORTM algorithm is determined by the cost of solving the MP. Although the solution provided by the ORTM algorithm is optimal, this method cannot solve problems with large network sizes efficiently. To enhance the scalability of the proposed method, we propose a novel Heuristic Reliability Task Mapping algorithm, referred to as HRTM, to efficiently solve the PP. The reasons why we design the heuristic approach for PP, rather than PP1, are the following: 1) PP and PP1 are equivalent, 2) PP contains fewer variables, which makes the problem easier to solve, and 3) the heuristic approach determines the values of the variables sequentially, and thus, some nonlinear items, which are caused by the products of variables, can be omitted. Similar to the ORTM algorithm, the HRTM algorithm is also based on problem decomposition. However, the main difference is that the subproblems in the ORTM algorithm are solved iteratively, while the subproblems in the HRTM algorithm are solved sequentially without iteration. Therefore, the computation time of the HRTM algorithm can be largely reduced. Based on the structure of PP, the HRTM algorithm contains two steps. We first consider the frequency assignment problem, in order to balance the task execution energy. Based on the solution of the first step, we solve the task mapping problem to balance the nodes' computation and communication energy.

Frequency Assignment Problem

The processors of the nodes have the same voltage/frequency levels {(𝑣 1 , 𝑓 1 ), . . . , (𝑣 𝐹 , 𝑓 𝐿 )}. Therefore, the frequency-to-task assignment is independent of the task-to-node allocation, and thus, it can be considered as the first step; the solutions in the next heuristic step will not violate the solution of this step. Regarding task triplication, the task allocation decision 𝑞 𝑖𝑘 is unknown at this step, and according to Eq. ( 3), the task triplication decision ℎ ′ 𝑖 is determined by the value of 𝑞 𝑖𝑘 . Hence, we consider the worst case, where each original task 𝜏 𝛼 𝑖 is triplicated (ℎ 𝛼 𝑖 = 1), i.e., the number of tasks is 𝑁 .

Under the given frequency assignment decision 𝑐 𝑖𝑙 , the time and the energy required to execute task 𝜏 𝑖 with 𝑒 𝑖 cycles are

𝑡 𝑐 𝑖 = 𝑙 ∈ L 𝑐 𝑖𝑙 𝑒 𝑖 𝑓 𝑙 and 𝐸 𝑐 𝑖 = 𝑙 ∈L 𝑐 𝑖𝑙 𝑒 𝑖
𝑓 𝑙 𝑃 𝑐 𝑙 , respectively. If a lower voltage/frequency level is used to execute the tasks, the task execution energy will be reduced. However, it will have an impact on the real-time execution, since the task execution time increases. Therefore, at the current step, we aim to balance the task execution energy, while guaranteeing that the real-time task constraint is satisfied. On the one hand, minimizing the maximum energy consumption on a single task's execution (i.e., min(max ∀𝑖 ∈N 𝐸 𝑐 𝑖 )) facilitates the balance of node energy consumption through task allocation, which is the main purpose of next step. On the other hand, taking the task real-time constraint into account, we can choose the proper voltage/frequency to execute the tasks to avoid missing the task deadlines. Based on the objective function and the constraints mentioned above, the Frequency Assignment Problem (FAP) is formulated as 13), [START_REF] Guo | A mobile-assisted edge computing framework for emerging IoT applications[END_REF].

FAP : min 𝒄 max ∀𝑖 ∈N 𝐸 𝑐 𝑖 (37) s.t. (
By using the idea of Greedy Algorithm (GA) [START_REF] Liu | Two-phase scheduling for efficient vehicle sharing[END_REF][START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF], we propose Algorithms 1 and 2 to solve this problem. For presentation reasons, a frequency assignment symbol 𝑆 [𝑖] is introduced for each task 𝜏 𝑖 , where 𝑆 [𝑖] = 𝑙 represents frequency 𝑓 𝑙 is used to execute task 𝜏 𝑖 .

Before executing Algorithm 1, we need to determine the frequency assignment sequence of the tasks, 𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒, required for sorting the tasks (Line 2). Note that the task start time and the node communication costs (energy and time) are unknown. To take real-time constraint [START_REF] Guo | A mobile-assisted edge computing framework for emerging IoT applications[END_REF] into account, we divide the tasks into several layers; tasks in different layers are dependent, while the tasks in the same layer are independent. Each task can identify its parent tasks based on the dependency between the tasks. On this basis, we can determine the layer to which a task should belong. The sequence is obtained following the layer order, and when independent tasks exist within a layer, they are sorted in descending order of execution cycles. end if 9: end for To illustrate the above procedure, Fig. 2 shows a simple case with five dependent tasks. The task dependency is described by a binary matrix 𝒐 = [𝑜 𝑖 𝑗 ] 5×5 , where 𝑜 12 = 𝑜 13 = 𝑜 14 = 𝑜 23 = 𝑜 24 = 𝑜 35 = 𝑜 45 = 1. According to the matrix 𝒐, we can describe each task 𝜏 𝑖 with the sets 𝑃𝑇 𝐼𝑛𝑑𝑒𝑥 𝑖 and 𝑃𝑇 𝐿𝑎𝑦𝑒𝑟 𝑖 , where 𝑃𝑇 𝐼𝑛𝑑𝑒𝑥 𝑖 is the set of parent tasks and 𝑃𝑇 𝐿𝑎𝑦𝑒𝑟 𝑖 is the set of the layers assigned to parent tasks. For example, task 𝜏 3 has two parent tasks 𝜏 1 and 𝜏 2 , and the layers of tasks 𝜏 1 and 𝜏 2 are 𝐿 1 and 𝐿 2 , respectively. Hence, we have 𝑃𝑇 𝐼𝑛𝑑𝑒𝑥 3 = {1, 2} and 𝑃𝑇 𝐿𝑎𝑦𝑒𝑟 3 = {1, 2}, and thus, task 𝜏 3 is assigned to layer 𝐿 3 . On the other hand, the independent tasks 𝜏 3 and 𝜏 4 can be assigned to the same layer 𝐿 3 . For tasks 𝜏 3 and 𝜏 4 , assuming that the execution cycles of 𝜏 3 are higher than those of 𝜏 4 (i.e., 𝑒 3 > 𝑒 4 ), the 𝜏 3 is considered first. Therefore, we obtain a frequency assignment sequence:

𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 = {𝜏 1 → 𝜏 2 → 𝜏 3 → 𝜏 4 → 𝜏 5 }.
Since the original task 𝜏 𝛼 𝑖 and its replicas 𝜏 𝛼 𝑖 +1 and 𝜏 𝛼 𝑖 +2 are independent, they are assigned to the same layer. Note that 𝜏 𝛼 𝑖 , 𝜏 𝛼 𝑖 +1 and 𝜏 𝛼 𝑖 +2 have the same execution cycles (i.e., 𝑒 𝛼 𝑖 = 𝑒 𝛼 𝑖 +1 = 𝑒 𝛼 𝑖 +2 ). We assume that the frequency assignment sequence between them is 𝜏 𝛼 𝑖 → 𝜏 𝛼 𝑖 +1 → 𝜏 𝛼 𝑖 +2 . On the other hand, for the original tasks 𝜏 𝛼 𝑖 and 𝜏 𝛼 𝑗 (𝑖 ≠ 𝑗), if they are in the same layer and they have the same execution cycles (i.e., 𝑒 𝛼 𝑖 = 𝑒 𝛼 𝑗 ), we consider that their frequency assignment priorities can be randomly chosen.

Based on the frequency assignment sequence 𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒, Algorithm 1 finds the proper frequency for task 𝜏 𝑖 under the real-time constraint, i.e., the selected frequency should cause the minimum increase in task execution energy, among the tasks that have already been assigned their frequency. During this process, Algorithm 2 is used to calculate the maximum energy required to execute a task, i.e., 𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸. If the real-time constraint cannot be satisfied under the given assignment decision 𝑆 [𝑖] = 𝑙, this decision will be excluded (Lines 10-12). As the task allocation decision is unknown, we omit the communication time of the nodes and assume that there is no gap between two adjacent tasks when calculating the end time of each task (Line 8). As the example shown in Fig. 2, we have

𝑡 𝑠 1 = 0, 𝑡 𝑒 1 = 𝑡 𝑐 1 , 𝑡 𝑒 2 = 𝑡 𝑒 1 + 𝑡 𝑐 2 , 𝑡 𝑒 3 = max{𝑡 𝑒 1 , 𝑡 𝑒 2 } + 𝑡 𝑐 3 , 𝑡 𝑒 4 = max{𝑡 𝑒 1 , 𝑡 𝑒 2 } + 𝑡 𝑐 4 , and
𝑡 𝑒 5 = max{𝑡 𝑒 3 , 𝑡 𝑒 4 } + 𝑡 𝑐 5 , where 𝑡 𝑠 𝑖 , 𝑡 𝑐 𝑖 = 𝑙 ∈ L 𝑐 𝑖𝑙 𝑒 𝑖
𝑓 𝑙 and 𝑡 𝑒 𝑖 = 𝑡 𝑠 𝑖 + 𝑡 𝑐 𝑖 are the start time, execution time and end time of task 𝜏 𝑖 , respectively. By applying the above frequency selection process for each task 𝜏 𝑖 (Lines 3-28), the solution to the FAP is found.

Task Mapping Problem

From Eq. (4) and Eq. ( 7), we observe that when the frequency assignment decision 𝑐 𝑖𝑙 is fixed, the communication cost 𝐸 𝑡 𝑘 and the computation cost 𝐸 𝑛 𝑘 of each node 𝜃 𝑘 are determined by the task allocation decision 𝑞 𝑖𝑘 and the task triplication decision ℎ ′ 𝑖 . In addition, the task triplication decision ℎ ′ 𝑖 is influenced by the task allocation decision 𝑞 𝑖𝑘 . Therefore, the communication and computation energy of the nodes can be optimized by adjusting 𝑞 𝑖𝑘 . The task sequence constraint [START_REF] Fischetti | The feasibility pump[END_REF] and the task non-preemption constraint [START_REF] Gou | Reliability-aware energy optimization for throughputconstrained applications on MPSoC[END_REF] show that the value of 𝑞 𝑖𝑘 is also restricted by the task start Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:17

𝝉 𝟏 𝝉 𝟐 𝝉 𝟑 𝑠 !" 𝑠 "# 𝑠 !# 𝝉 𝟒 𝝉 𝟓 𝑠 !$ 𝑠 #% 𝑠 $% 𝐿 1 𝐿 2 𝐿 3 𝐿 4 𝑃𝑇𝐼𝑛𝑑𝑒𝑥 1 = 0 𝑃𝑇𝐿𝑎𝑦𝑒𝑟 1 = 0 𝑃𝑇𝐼𝑛𝑑𝑒𝑥 2 = 1 𝑃𝑇𝐿𝑎𝑦𝑒𝑟 2 = 1 𝑃𝑇𝐼𝑛𝑑𝑒𝑥 3 = 1,2 𝑃𝑇𝐿𝑎𝑦𝑒𝑟 3 = 1,2 𝑃𝑇𝐼𝑛𝑑𝑒𝑥 4 = 1,2 𝑃𝑇𝐿𝑎𝑦𝑒𝑟 4 = 1,2 𝑃𝑇𝐼𝑛𝑑𝑒𝑥 3 = 3,4 𝑃𝑇𝐿𝑎𝑦𝑒𝑟 3 = 3,3
𝑠 "$ Fig. 2. Determine frequency assignment sequence based on task layer.

time 𝑡 𝑠 𝑖 and the task sequence 𝑢 𝑖 𝑗 . Therefore, when making the task allocation decision 𝑞 𝑖𝑘 , the constraints ( 14) and ( 15) should be taken into account.

At this step, under the given frequency assignment decision 𝑐 𝑖𝑙 , we aim to determine task allocation 𝑞 𝑖𝑘 , task sequence 𝑢 𝑖 𝑗 , task triplication ℎ ′ 𝑖 , and task start time 𝑡 𝑠 𝑖 . Therefore, the Task Mapping Problem (TMP) is formulated as

TMP : min 𝒒,𝒖,𝒉 ′ ,𝒕 𝑠 max ∀𝑘 ∈M 𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 /𝐸 𝑖𝑛𝑖 𝑘 (38) s.t. (3)
, ( 10) -( 12), ( 14) -(

Since the binary variables 𝑞 𝑖𝑘 , ℎ ′ and 𝑢 𝑖 𝑗 and the continuous variable 𝑡 𝑠 𝑖 are coupled with each other linearly, and the nonlinear items 𝑞 𝑖𝑚 𝑞 𝑗𝑛 and ℎ ′ 𝑖 ℎ ′ 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 are included in constraints (3), ( 17)- [START_REF] Kang | Reliability-aware mapping optimization of multi-core systems with mixed-criticality[END_REF], TMP is a MINLP problem. Based on the structure of TMP, we propose Algorithms 3-4 to solve it.

Algorithm 3 first initializes the allocation index 𝑂 [𝑖] for each task 𝜏 𝑖 , where 𝑂 [𝑖] = 𝑘 represents that task 𝜏 𝑖 is allocated to node 𝜃 𝑘 . Then, it allocates tasks, one by one, to their proper nodes, causing the minimum increase in energy consumption among the nodes, under real-time and energy constraints (Lines 1-2). Different from the FAP, the allocations of dependent tasks on the wireless nodes are considered in TMP. Therefore, the real-time constraint in TMP includes the communication time of the nodes. The task allocation sequence is given by 𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒, as it can handle the problems of task start time and task sequence simultaneously (i.e., 𝑡 𝑠 𝑖 and 𝑢 𝑖 𝑗 ). To find the maximum energy consumption at a node (i.e., 𝑀𝑎𝑥𝐶𝑜𝑠𝑡 𝑁 ), under the given task allocation decision 𝑂 [𝑖] = 𝑘, we design Algorithm 4. During the allocation process, if tasks 𝜏 𝑖 and 𝜏 𝑗 (𝑖 ≠ 𝑗) are dependent and these tasks are allocated to the same node, there is no need to triplicate task 𝜏 𝑖 , since the data of 𝜏 𝑖 is directly transmitted to 𝜏 𝑗 within one node.

As shown in Fig. 1, 𝜏 1 , 𝜏 4 and 𝜏 7 are the original tasks, while 𝜏 2 , 𝜏 3 , 𝜏 5 and 𝜏 6 are the corresponding replicas. Based on task dependency 𝑜 𝑖 𝑗 and task execution cycles 𝑒 𝑖 , we follow the sequence:

𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 = {𝜏 1 → 𝜏 2 → 𝜏 3 → 𝜏 4 → 𝜏 5 → 𝜏 6 → 𝜏 7 }
to perform task allocation. Since the original task and the corresponding replicas are independent (e.g., 𝜏 1 , 𝜏 2 and 𝜏 3 ), they can be placed in the same layer. If the tasks 𝜏 1 , 𝜏 4 , 𝜏 5 and 𝜏 6 are allocated to the same node, there is no need to triplicate 𝜏 1 . Hence, tasks 𝜏 2 and 𝜏 3 can be removed from the task graph, and the execution time of tasks 𝜏 2 and 𝜏 3 can be set to 𝑡 𝑐 2 = 𝑡 𝑐 3 = 0, since 𝑒 2 = 𝑒 3 = 0. Based on the allocation of the original tasks 𝜏 4 and 𝜏 7 , we can use a similar method to decide the existence of tasks 𝜏 5 and 𝜏 6 . if 𝜏 𝑖 can be allocated 𝜃 𝑘 then 7:

𝑂 [𝑖] = 𝑘; 8:
if 𝜏 𝑖 is allocated to the same node as its previous dependent tasks then

Time Complexity

Finally, the time complexities of our frequency assignment and task mapping algorithms are discussed in terms of the number of variables [START_REF] He | UNISM: Unified scheduling and mapping for general networks on chip[END_REF]. The complexities of FAP and TMP are dominated by Algorithm 1 and Algorithm 3, respectively. Algorithm 2 is used to calculate the maximum energy required to execute a task, i.e., 𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸, under the given frequency assignment decision 𝑆 [𝑖] = 𝑙; and Algorithm 2 is used to calculate the maximum energy consumption at a node, i.e., 𝑀𝑎𝑥𝑁𝑜𝑑𝑒𝐸, under the given task allocation decision 𝑂 [𝑖] = 𝑘. In Algorithm 1 and Algorithm 3, the

SIMULATION RESULTS

To evaluate the performance of the proposed approaches, we consider a networked system with 20 nodes, where 10 nodes equipped with sensors and 5 nodes connected to actuators (i.e., 𝑀 = 20, 𝑀 𝑠 = 10, and 𝑀 𝑎 = 5). The modeling of the energy consumed by processors and wireless communication is based on [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM Combination[END_REF][START_REF] Tian | Cross-layer collaborative in-network processing in multihop wireless sensor networks[END_REF], and the characteristic of tasks is given by [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Yao | Enhancing federated learning in fog-aided IoT by CPU frequency and wireless power control[END_REF], which is based on the scenario of enhancing federated learning in Fog-aided IoT.

The First, we show the influence of system parameters on the problem solution (e.g., task allocation and the value of the objective function). Then, we compare the system performance (i.e., the energy consumption of the nodes, the reliability of the system, and the schedulability of the problem) of the proposed task mapping scheme (Reliability-Energy-Realtime -RER) (i.e., PP) and other stateof-the-art mapping schemes (i.e., Energy-Efficiency (EE) [START_REF] Pathak | Energy-efficient task mapping for data-driven sensor network macroprogramming[END_REF], Task Duplication (TD) [START_REF] Gou | Reliability-aware energy optimization for throughputconstrained applications on MPSoC[END_REF], and Task Triplication (TT) [START_REF] Kang | Reliability-aware mapping optimization of multi-core systems with mixed-criticality[END_REF]). Finally, we evaluate the algorithm performance (i.e., the solution quality, the computation time, and the problem feasibility) of the proposed ORTM and HRTM algorithms with the Branch and Bound (B&B) [START_REF] Boyd | Branch and bound methods[END_REF], which can find the optimal solution for MILP problems, and the heuristics based on As-Soon-As-Possible (ASAP) [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. The ASAP method estimates the as-soon-as-possible start time and uses it to limit the range of the task start time. The simulations are performed on a laptop with a quad-core 2.5 GHz Intel I7 processor and 16 GB RAM, and the algorithms are implemented in Matlab 2020b. Note that different processor platforms and task graphs will lead to different parameters for the PP. However, the problem structures under different parameters are the same; thus, the proposed methods are still applicable. In addition, different algorithms can be compared under the given system parameters.

Fig. 3(a) explores the influence of energy ratio between communication and computation on task allocation decision 𝑞 𝑖𝑘 . We set 𝐺 = 12, 𝜂 = 0.8, and change the value of 𝜇 from 1 to 10 with a step of 1. Let 𝜇 = 𝑒 𝑐𝑜𝑚𝑚 max /𝑒 𝑐𝑜𝑚𝑝 max and 𝑁 max = max ∀𝑘 {𝑁 𝑘 }, where 𝑒 𝑐𝑜𝑚𝑚 max = max ∀𝛽,𝛾,𝑘 {𝑒 𝛽𝛾𝑘 } is the maximum energy required for a node to relay task data, and 𝑒 𝑐𝑜𝑚𝑝 max = max ∀𝑖,𝑙 { 𝑒 𝑖 𝑓 𝑙 𝑃 𝑙 } is the maximum energy required for a node to execute a task. Therefore, the larger the value of 𝜇 is, the more energy is required to transmit task data, compared with the energy consumed for task execution. Since 𝑁 𝑘 is the number of tasks allocated to node 𝜃 𝑘 , 𝑁 max = max ∀𝑘 {𝑁 𝑘 } represents the maximum number of tasks assigned to a node. Fig. 3(a) shows that 𝑁 max increases with 𝜇. This is because, with larger communication energy compared to the computation energy, the trend is allocating dependent tasks to the same node to reduce the communication energy. 𝑘 + 𝐸 𝑑 𝑘 is the computation and the communication energy of node 𝜃 𝑘 , 𝜙 is the energy consumption gap between the nodes. The smaller the value of 𝜙 is, the better balance of node energy consumption can be achieved. We set 𝜂 = 0.8 and change the value of 𝐺 (the number of original tasks) from 8 to 18 with a step of 2. From Fig. 3(b), we observe that the total node energy consumption of RER-ME is lower than RER-BE. This is because by using RER-ME, the dependent tasks tend to be allocated to the same nodes, so as to reduce the communication energy of the nodes. On the other hand, Fig. 3(c) shows that the value of 𝜙 with RER-BE is lower than RER-ME. Hence, by using RER-BE, we can avoid some nodes depleting energy early, i.e., enhancing the lifetime of the networked system. Fig. 4(a) compares the energy consumption of the nodes with EE, TD, TT, and the proposed RER scheme. The aim of the EE scheme is to minimize the energy consumption of the nodes under real-time and energy constraints. With the TD scheme, each task is duplicated, while with the TT scheme each task is triplicated. We set 𝜂 = 0.8 and change the value of 𝐺 from 8 to 18 with a step of 2. From Fig. 4(a), we observe that for all mapping schemes, with the task number 𝐺 increasing, the energy consumption of the nodes increases as well, since more energy is required to execute the tasks and exchange the task data between the nodes. In addition, the simulation results show that under the given task number 𝐺, the EE scheme consumes the least energy, while the TT scheme consumes more energy than the other schemes. This is because EE aims to minimize the energy consumption of the nodes, and the tasks are not duplicated/triplicated. However, each task is triplicated in TT, which leads to more tasks being required to execute. Fig. 4(a) also shows that although the approaches achieve a similar reliability level, RER consumes less energy consumption than TT (28.62% on average), since only parts of tasks are triplicated in RER. Fig. 4(b) compares the probability of original tasks against the False Data Injection (FDI) under EE, TD, TT, and RER schemes. We introduce a reliability index 𝐺 𝑖=1 𝑤 𝛼 𝑖 /𝐺 for each task mapping scheme. With the EE scheme, since the tasks are not replicated, we have 𝑁 = 𝐺 (𝐺 and 𝑁 are the numbers of original tasks and total tasks, respectively), while with TD, TT, and RER schemes, we get 𝑁 = 2𝐺, 𝑁 = 3𝐺 and 𝑁 = 3𝐺, respectively. On the other hand, the value of parameter 𝑤 𝛼 𝑖 is determined as follows: 1) If the original task 𝜏 𝛼 𝑖 is an entry task since 𝜏 𝛼 𝑖 will not receive data from other tasks, we set 𝑤 𝛼 𝑖 = 1; 2) If the original task 𝜏 𝛼 𝑖 is a non-entry task, and this task receives three copies (i.e., the original, duplicated and triplicated tasks) from each previous dependent task or just one copy (i.e., the original task) from each previous dependent task, which is assigned to the same node as task 𝜏 𝛼 𝑖 , we set 𝑤 𝛼 𝑖 = 1, else, we set 𝑤 𝛼 𝑖 = 0. From Fig. 4(b), we observe that under the same value of 𝐺, the reliability indexes of TT and RER are higher than EE and TD, since compared with EE and TD, the tasks are triplicated in TT and RER. In addition, because the tasks are not triplicated in EE and TD, the reliability index of TD is not always higher than EE. Although the reliability indexes of TT and RER are the same, with TT the nodes consume more energy, as more tasks are triplicated.

Fig. 4(c) evaluates the schedulability of TT and RER schemes since both of them perform task triplication. To compare their schedulabilities, the problem feasible ratio is introduced as a metric. For TT and RER schemes, we construct and solve the corresponding task mapping problem 30 times (𝑛 𝑎 = 30), each time with fixed parameters 𝐺 and 𝜂, and tuned parameters 𝑜 𝑖 𝑗 and 𝑒 𝑖 . Let 𝑛 𝑡 and 𝑛 𝑟 denote the times that the task mapping problems in TT and RER are feasible, respectively. Hence, the problem feasible ratios for TT and RER schemes can be defined as 𝑛 𝑟 /𝑛 𝑎 and 𝑛 𝑟 /𝑛 𝑎 , respectively. We set 𝐺 = 14 and change the value of 𝜂 from 0.4 to 0.9 with a step of 0.1. From Fig. 4(c), we observe that with 𝜂 increasing, the problem feasible ratios of TT and RER both increase. In addition, the scheme with DVFS has a higher problem feasible ratio than the scheme without DVFS. This is because by introducing the frequency-to-task assignment variable 𝑐 𝑖𝑙 into the task mapping problem, the time and the energy regarding task execution can be further optimized. Hence, the real-time and energy constraints can be easier satisfied, especially when the energy factor 𝜂 is small. Fig. 4(c) also shows that under the given 𝐺 and 𝜂, RER has a higher problem feasible ratio than TT. This is because not all original tasks are triplicated in RER, and thus, the nodes in RER consume less energy for task execution and data exchange than the nodes in TT. From Fig. 4, we can observe that compared with EE, TD, and TT schemes, the proposed RER scheme makes better use of system resources to enhance system reliability.

The solution quality and the computation time of using B&B and the proposed ORTM and HRTM algorithms to solve the PP under different task numbers 𝐺 are compared in Fig. 5(a) and Fig. 5(b). The results show that the solutions found by ORTM and B&B are the same, i.e., the ORTM algorithm is also optimal. In addition, the ORTM algorithm achieves a lower objective function value than that of the HRTM algorithm (26.35% on average). With task number 𝐺 increasing, more variables and constraints are added to the PP. Therefore, the computation time required by B&B and ORTM both increases. However, the computation time of ORTM is lower than that of B&B (24.84% on average). This is because the computational complexity of an optimization problem is highly related to the number of variables and constraints. Solving the smaller problems with fewer variables and constraints iteratively is more efficient than solving a single large problem [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF]. In addition, compared with the ORTM, the HRTM has a negligible computation time, since this method only needs to solve two polynomial-time problems FAP and TMP in sequence. The schedulabilities of ORTM and HRTM algorithms to solve task mapping problem with the RER scheme are compared in Fig. 5(c). We use problem feasible ratio as a metric, and we set 𝑛 𝑎 = 30, 𝐺 = 14, and 𝜂 ∈ [0.3, 0.8]. Fig. 5(c) shows that the problem feasible ratios of ORTM and HRTM increase with 𝜂. Since the bounds of the constraints can be relaxed by 𝜂, the feasible region of the task mapping problem is enlarged. However, the problem feasibility ratio of ORTM is always higher than HRTM. This is because ORTM optimizes multiple variables at the same time, while HRTM optimizes these variables step by step.

Fig. 6(a) and Fig. 6(b) compare the solution quality and the computation time of HRTM and ASAP-based heuristic used to solve the PP. To solve this problem, the difficulty lies in the way of dealing with the continuous variable 𝑡 𝑠 𝑖 (task start time). This is because when the value of 𝑡 𝑠 𝑖 is fixed, the PP will reduce to an integer programming problem that contains only the binary variables 𝑞 𝑖𝑘 , 𝑐 𝑖𝑙 , 𝑢 𝑖 𝑗 and ℎ ′ 𝑖 . This problem is easier to solve than the MILP problem with continuous and binary variables. To perform the ASAP-based heuristic, in the first step, we assume that the start time of the entry task is 0. Then, for the adjacent dependent tasks, e.g., 𝜏 𝑖 and 𝜏 𝑗 (𝑜 𝑖 𝑗 = 1), we add a temporary communication time 𝜃 𝑖 𝑗 among them. The value of 𝜃 𝑖 𝑗 is set to (max ∀𝑚,𝑛 {𝑡 𝑚𝑛 } + min ∀𝑚,𝑛 {𝑡 𝑚𝑛 })/2, so as to model the communication time when tasks 𝜏 𝑖 and 𝜏 𝑗 are assigned to the different nodes. Therefore, the start time of task 𝜏 𝑗 can be replaced by 𝑡 𝑠 𝑗 = 𝑡 𝑒 𝑖 + 𝜃 𝑖 𝑗 . For example, as the task graph illustrated in Fig. 2 𝑖 is updated by ℎ ′ 𝑖 and 𝜃 𝑖 𝑗 . From the above statement, we can see that the computation time of the ASAP-based heuristic is mainly dominated by solving the integer programming problem. To solve this problem, we can use either the optimal method (e.g., B&B) or the heuristic method (e.g., Feasibility Pump (FP) [START_REF] Fischetti | The feasibility pump[END_REF]). Fig. 6(a) and Fig. 6(b) show that when using the optimal method to solve the integer programming problem in ASAP, the computation time of HRTM is lower than ASAP. However, ASAP achieve a higher solution quality than HRTM. This is because the binary variables 𝑞 𝑖𝑘 , 𝑐 𝑖𝑙 , 𝑢 𝑖 𝑗 , and ℎ ′ 𝑖 are solved simultaneously in ASAP, while they are solved sequentially in HRTM, according to two subproblems FAP and TMP. The variable 𝑐 𝑖𝑙 is first determined in FAP, and then, the variables 𝑞 𝑖𝑘 , 𝑢 𝑖 𝑗 and ℎ ′ 𝑖 are determined in TMP. In addition, the binary variables 𝑞 𝑖𝑘 , 𝑐 𝑖𝑙 and ℎ ′ 𝑖 are coupled with each other nonlinearly in ASAP. To deal with the nonlinear items, more auxiliary variables and additional constraints are involved in ASAP. Hence, compared with HRTM, ASAP has a longer computation time. On the other hand, when using the heuristic approach (e.g., FP) to solve the integer programming problem in ASAP, the solution quality and the computation time both decrease, since the FP only provides a feasible solution. In that case, the gap between the computation time (the solution quality) of HRTM and ASAP is small, compared with using the optimal method to solve the integer programming problem in ASAP.

CONCLUSION

In this paper, we study the task mapping problem on the wireless nodes of networked systems. To enhance the reliability of data transmission among the nodes, as well as to satisfy the real-time and energy constraints, we introduce the task triplication and the DVFS scheme into the task mapping problem. The aim is to decide task-to-node allocation, frequency-to-task assignment, task triplication, and task scheduling so that the energy consumption of the nodes is balanced. The problem is first formulated as MINLP, then transformed into an MILP by adding auxiliary variables and additional constraints. Based on the structure of the problem, we propose an ORTM algorithm to find the optimal solution. In addition, to deal with large network sizes, we also design an HRTM algorithm with reduced computation time. The simulation results show that the proposed reliability-energy-time aware task mapping scheme outperforms other schemes regarding transmission reliability and energy efficiency. In addition, the solution found by ORTM is guaranteed to converge to the optimal solution, while the HRTM is able to find a proper solution within a negligible computation time compared with ORTM.

Fig. 1 .

 1 Fig. 1. Motivational example.

Lemma 4 . 2 .

 42 Let 𝑥, 𝑦, and 𝑧 denote the binary variables. The nonlinear item 𝑧 = 𝑥𝑦 can be linearized as follows: 𝑧 ≤ 𝑥, 𝑧 ≤ 𝑦 and 𝑧 ≥ 𝑥 + 𝑦 -1.

  s.t. 𝑫 ′ 𝝀 ⪰ 0, we obtain the information about the SP portion of the PP2, and this information is communicated to the MP via Benders cuts, where 𝝀 ≜ [𝜆 𝑖 ] are the Lagrange multipliers.Based on the solution of the DSP, we have the following three cases. (1) If DSP is infeasible, PP2 has no feasible solution.

Algorithm 2 : 3 :

 23 Calculate 𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸 1: 𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸 = 0; 2: for ∀𝑖 ∈ N (𝑆 [𝑖] ≠ -1) do 𝐶𝑜𝑚𝑝𝐸 = 𝑒 𝑖 𝑓 𝑆 [𝑖 ]

Algorithm 3 :

 3 Task-to-node allocation 1: Initialize: 𝑂 [𝑖] = -1, ∀𝑖 ∈ N ; 2: Sort tasks {𝜏 1 , . . . , 𝜏 𝑁 } according to 𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒; 3: for ∀𝑖 ∈ N do

  end for variables regarding the assignment of frequency and the allocation of the task are 𝒄 = [𝑐 𝑖𝑙 ] 𝑁 ×𝐿 and 𝒒 = [𝑞 𝑖𝑘 ] 𝑁 ×𝑀 . Therefore, the complexities of FAP and TMP are O (𝑁 𝐿) and O (𝑁 𝑀), respectively.

  The influence of 𝜇 on task allocation decision 𝑞 𝑖𝑘 .

Fig. 3 .

 3 Fig. 3. System performance comparison under different parameters.

Fig. 3 (

 3 b) and Fig.3(c) compare the energy consumption of the nodes with two task mapping aims: 1) the PP with an objective function to Balance node Energy consumption (RER-BE), i.e., min[max ∀𝑘 {(𝐸

Fig. 4 .

 4 Fig. 4. System performance comparison with different task mapping schemes.

  Energy consumption of ORTM, HRTM and B&B with 𝐺 varying.

  Computation time of ORTM, HRTM and B&B with 𝐺 varying. Feasibility of task mapping problem with ORTM and HRTM.

Fig. 5 .

 5 Fig. 5. Algorithm performance comparison of ORTM, HRTM and B&B.

Table 1 .

 1 Classification of some task mapping approaches

	Ref.	Task I D ES NS TA TS TR FA E Platform Variables Constraints Reliability Solution T

  1, 𝜏 2 and 𝜏 3 are the second and the third replicas of 𝜏 1 , respectively. Under the task allocation{𝜏 1 → 𝜃 1 , 𝜏 2 → 𝜃 2 , 𝜏 3 → 𝜃 3 , 𝜏 4 → 𝜃 5 }, two routing paths exist {𝜃 2 → 𝜃 3 → 𝜃 4 → 𝜃 5 (blue), 𝜃 1 → 𝜃 5 (red)}.Therefore, 𝜃 5 will receive task data (𝜏 1 , 𝜏 2 and 𝜏 3 ) from 𝜃 1 and 𝜃 4 . If 𝜃 1 suffers from an FDI attack when it transmits the data of 𝜏 1 to 𝜏 4 , the data can be corrected by comparing with the results of 𝜏 2 and 𝜏 3 , before used as input to task 𝜏 4 . Executing task replicas on different nodes allows sending the information through different routing paths, dealing with FDI attacks with long duration. For instance, compared with the task allocation {𝜏 2 → 𝜃 3 , 𝜏 3 → 𝜃 3 }, the task allocation {𝜏 2 → 𝜃 2 , 𝜏 3 → 𝜃 3 } has a longer time interval when 𝜃 3 transmitting the data of 𝜏 2 and 𝜏 3 , since a node will receive and transmit the task data in sequence.

  Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:7 𝜏 𝑖 , else, 𝑜 𝑖 𝑗 = 0. Let 𝑠 𝑖 𝑗 denote the size of data that task 𝜏 𝑖 generates for task 𝜏 𝑗 . If tasks 𝜏 𝑖 and 𝜏 𝑗 are independent, we have 𝑠 𝑖 𝑗 = 0. 3.2.2 Node Model. We consider a networked system with 𝑀 wireless nodes {𝜃 1 , . . . , 𝜃 𝑀 }. The nodes have different capabilities, with {𝜃 1 , . . . , 𝜃 𝑀 𝑠 } describing the nodes equipped with sensors and {𝜃 𝑀 𝑠 +1 , . . . , 𝜃 𝑀 𝑠 +𝑀 𝑎 } describing the nodes equipped with actuators, and 𝑀 𝑠 +𝑀 𝑎 ≤ 𝑀. The processors of the nodes, where the computation takes place, use the same Instruction Set Architecture (ISA), and they support DVFS. Each processor has 𝐿 different discrete Voltage/Frequency (V/F) levels {(𝑣 1 , 𝑓 1 ), . . . , (𝑣 𝐿 , 𝑓 𝐿 )}. As the relationship between voltage and frequency is almost linear [8, 10], when the supply voltage is changed, the clock frequency is changed accordingly. The execution time of task 𝜏 𝑖 , when it is executed at frequency 𝑓 𝑙 on a processor, is given by 𝑒 𝑖 /𝑓 𝑙 . The power consumption of a processor is modeled as the sum of static power 𝑃 𝑠 and dynamic power 𝑃 𝑑 , that is 𝑃 𝑐 = 𝑃 𝑠 + 𝑃 𝑑 [8, 11]. The static power and dynamic power, under a given voltage/frequency level (𝑣 𝑙 , 𝑓 𝑙 ), are calculated as 𝑃 𝑠 𝑙 = 𝐶 𝑠 𝑣

𝜌 𝑙 and 𝑃 𝑑 𝑙 = 𝐶 𝑑 𝑓 𝑙 𝑣 2 𝑙

Table 2 .

 2 Symbols used in the problem formulation 𝜃 𝑘 the 𝑘 𝑡ℎ node 𝜏 𝑖 the 𝑖 𝑡ℎ task (𝑣 𝑙 , 𝑓 𝑙 ) the 𝑙 𝑡ℎ voltage/frequency level 𝐻 scheduling horizon 𝑃 𝑠 𝑙 static power of processor running on (𝑣 𝑙 , 𝑓 𝑙 ) 𝑃 𝑑 𝑙 dynamic power of processor running on (𝑣 𝑙 , 𝑓 𝑙 ) 𝑃 0 idle power of processor 𝐸 𝑟 𝑘 energy supply of node 𝜃 𝑘 𝑒 𝑖 execution cycles of task 𝜏 𝑖 𝑜 𝑖 𝑗 = 1 if task 𝜏 𝑖 proceeds 𝜏 𝑗 and 𝜏 𝑗 is the nearest task of 𝜏 𝑖 0 else 𝑁 𝛼 𝑖 number of tasks that dependent on task 𝜏 𝛼 𝑖 𝑠 𝑖 𝑗 size of data that task 𝜏 𝑖 produces for task 𝜏 𝑗 𝑟 𝛽𝛾𝑘 energy consumed of node 𝜃 𝑘 when routing unit of data from 𝜃 𝛽 to 𝜃 𝛾 𝑡 𝛽𝛾 time required to transmit unit of data from 𝜃 𝛽 to 𝜃 𝛾 𝜏 𝑖 tasks in S 2 are allocated to the same node; 2) Tasks in S 1 are allocated to different nodes and tasks in S 2 are allocated to different nodes; 3) Tasks in S 1 are allocated to the same node and tasks in S 2 are allocated to the same node; 4) Tasks in S 1 are allocated to the same node, while tasks in S 2 are allocated to different nodes.

	Parameters
	𝑀 𝑎	number of actuator nodes
	𝑀 𝑠	number of sensor nodes
	𝑀	number of wireless nodes
	𝐺	number of original tasks
	𝑁	number of original tasks and replicas
	𝐿	number of voltage/frequency levels
	Integer Variables
			1 if task 𝜏 𝑖 is allocated to node 𝜃 𝑘
	𝑞 𝑖𝑘	=
			0 else
			1 if task 𝜏 𝑖 is executed with frequency 𝑓 𝑙
	𝑐 𝑖𝑙	=
			0 else
			1 if task 𝜏 𝑖 proceeds task 𝜏 𝑗
	𝑢 𝑖 𝑗	=
			0 else
	ℎ ′ 𝑖	=	1 if task 𝜏 𝑖 exists 0 else
	Continuous Variables
	𝑖 𝑡 𝑠	start time of task

  1, ℎ 𝛼 𝑖 , ℎ 𝛼 𝑖 , . . . , 1, ℎ 𝐺 , ℎ 𝐺 ] 𝑇 . With the variable ℎ ′ 𝑖 , the number of execution cycles of task 𝜏 𝑖 is ℎ ′ 𝑖 𝑒 𝑖 and the size of data, that task 𝜏 𝑖 generate for task 𝜏 𝑗 , is ℎ ′ 𝑖 ℎ ′ 𝑗 𝑠 𝑖 𝑗 . If task 𝜏 𝑖 is assigned to node 𝜃 𝑚 , while task 𝜏 𝑗 (𝑖 ≠ 𝑗) is assigned to node 𝜃 𝑛 (𝑚 ≠ 𝑛), the communication energy consumed by node 𝜃 𝑘 (𝑘 ≠ 𝑚 ≠ 𝑛) to send the data from 𝜏 𝑖 to 𝜏 𝑗 is ℎ ′ 𝑖 ℎ ′ 𝑗 𝑠 𝑖 𝑗 𝑞 𝑖𝑚 𝑞 𝑗𝑛 𝑟 𝑚𝑛𝑘 . Therefore, the communication energy of node 𝜃 𝑘 is

  Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:11 where 𝑡 𝑠 𝑖 and 𝑡 𝑒 𝑖 are the start time and the end time of task 𝜏 𝑖 , respectively (0 ≤ 𝑡 𝑠 𝑖 ≤ 𝑡 𝑒 𝑖 ≤ 𝐻 ). Therefore, the task execution time is given by 𝑡 𝑐 𝑖 = 𝑡 𝑒 𝑖 -𝑡 𝑠 𝑖 . If 𝑜 𝑖 𝑗 = 1 (i.e., 𝜏 𝑖 precedes 𝜏 𝑗 and 𝜏 𝑗 is the closest task of 𝜏 𝑖 ), we have 𝑡 𝑠 𝑗 ≥ 𝑡 𝑒 𝑖 + 𝑡 𝑟 𝑗 , else (i.e., 𝑜 𝑖 𝑗 = 0), Eq. (

1, No. 1, Article 1. Publication date: January 2023.

  Initialize: 𝑆 [𝑖] = -1, ∀𝑖 ∈ N ; 2: Sort tasks {𝜏 1 , . . . , 𝜏 𝑁 } according to 𝐴𝑠𝑠𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒; 3: for ∀𝑖 ∈ N do

	Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems	1:15
	Algorithm 1: Frequency-to-task assignment
	1: 4:	𝑀𝑖𝑛𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸 = ∞;
	5:	𝑓 𝑙𝑎𝑔 = -1;
	6:	for ∀𝑙 ∈ L do
	7:	𝑆 [𝑖] = 𝑙;
	8:	Calculate 𝑡 𝑒 𝑖 based on 𝑐 𝑖𝑙 and 𝑜 𝑖 𝑗 ;
	9:	𝑀𝑎𝑥𝐶𝑜𝑚𝑝 = 𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸;
	10:	if 𝑡 𝑒 𝑖 > 𝐻 then
	11:	𝑐 𝑖𝑙 = 0;
	12:	Continue;
	13:	else
	14:	if 𝑀𝑎𝑥𝐶𝑜𝑚𝑝 < 𝑀𝑖𝑛𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸 then
	15:	𝑀𝑖𝑛𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸 = 𝑀𝑎𝑥𝐶𝑜𝑚𝑝;
	16:	𝑓 𝑙𝑎𝑔 = 𝑙;
	17:	else
	18:	𝑀𝑖𝑛𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸 = 𝑀𝑖𝑛𝑀𝑎𝑥𝐶𝑜𝑚𝑝𝐸;
	19:	𝑓 𝑙𝑎𝑔 = 𝑓 𝑙𝑎𝑔;
	20:	end if
	21:	end if
	22:	end for
	23:	if 𝑓 𝑙𝑎𝑔 == -1 then
	24:	Fail to assign frequency for task 𝜏 𝑖 ;
	25:	else
	26:	𝑆 [𝑖] = 𝑓 𝑙𝑎𝑔;
	27:	end if
	28: end for

29: Calculate 𝑐 𝑖𝑙 according to 𝑆 [𝑖];

  𝐸 𝑡 𝑘 and 𝐸 𝑑 𝑘 based on 𝑞 𝑖𝑘 , 𝑜 𝑖 𝑗 and {𝑡 𝑒 1 , . . . , 𝑡 𝑒 𝑖-1 }; Calculate 𝑞 𝑖𝑘 according to 𝑂 [𝑖];

	9:	Update {𝑡 𝑒 1 , . . . , 𝑡 𝑒 𝑖-1 };
	10:	else
	11:	Continue;
	12:	end if
	13: 𝑖 , 14: Calculate 𝑡 𝑒 Calculate 𝐸 𝑎𝑙𝑙 𝑘 based on 𝐸 𝑡 𝑘 , 𝐸 𝑑 𝑘 , 𝐸 𝑠 𝑘 and 𝐸 𝑎 𝑘 ;
	15:	𝑀𝑎𝑥𝐸 = 𝑀𝑎𝑥𝑁𝑜𝑑𝑒𝐸;
	16:	if 𝐸 𝑎𝑙𝑙 𝑘 > 𝐸 𝑙 𝑘 ||𝑡 𝑒 𝑖 > 𝐻 then
	17:	𝑞 𝑖𝑘 = 0;
	18:	Continue;
	19:	else
	20:	if 𝑀𝑎𝑥𝐸 < 𝑀𝑖𝑛𝑀𝑎𝑥𝐸 then
	21:	𝑀𝑖𝑛𝑀𝑎𝑥𝐸 = 𝑀𝑎𝑥𝐸;
	22:	𝑓 𝑙𝑎𝑔 = 𝑘;
	23:	else
	24:	𝑀𝑖𝑛𝑀𝑎𝑥𝐸 = 𝑀𝑖𝑛𝑀𝑎𝑥𝐸;
	25:	𝑓 𝑙𝑎𝑔 = 𝑓 𝑙𝑎𝑔;
	26:	end if
	27:	end if
	28:	else
	29:	𝑞 𝑖𝑘 = 0;
	30:	Continue;
	31:	end if
	32:	end for
	33:	if 𝑓 𝑙𝑎𝑔 == -1 then
	34:	Fail to allocate task 𝜏 𝑖 ;
	35:	else
	36:	𝑂 [𝑖] = 𝑓 𝑙𝑎𝑔;
	37:	end if
	38: end for
	39:

  energy supply of node 𝜃 𝑘 is set to 𝐸 𝑟 𝑘 = 𝜂𝐸 ℎ 𝑘 , where 𝜂 ∈ [0, 1] is an energy efficiency factor and 𝐸 ℎ 𝑘 is the minimum energy required to execute tasks {𝜏 1 , . . . , 𝜏 𝑁 }. In particular, 𝐸 ℎ 𝑘 = 𝐸 𝑡 𝑘,min + 𝐸 𝑑 𝑘,min , where 𝐸 𝑡 𝑘,min = 𝑁 min ∀𝑚,𝑛,𝑘 {𝑟 𝑚𝑛𝑘 } is the minimum energy required to transmit all the task data, while 𝐸 𝑑 𝑘,min = 𝑖 ∈N (min ∀𝑙 𝑒 𝑖 𝑓 𝑙 𝑃 𝑐 𝑙 ) is the minimum energy required to execute all the tasks. Since the nodes equipped with the sensors and the actuators consume more energy for executing sensing and control tasks, we set 𝐸 𝑟 𝑘 = 2𝜂𝐸 ℎ 𝑘 for the sensor nodes while 𝐸 𝑟 𝑘 = 3𝜂𝐸 ℎ 𝑘 for the actuator nodes. The scheduling horizon (i.e., task deadline) is set to 𝐻 = max ∀𝑗 {𝑑 𝑗 }, where 𝑑 𝑗 = max ∀𝑖,𝑜 𝑖 𝑗 =1 {𝑑 𝑖 } + t𝑟 𝑗 + d𝑗 . t𝑟 𝑗 and d𝑗 are the temporary data receiving time and the relative deadline of task 𝜏 𝑗 (the bound of task execution time), respectively. t𝑟 𝑗 is assumed within the range [𝑁 min ∀𝑚,𝑛 {𝑡 𝑚𝑛 }, 𝑁 max ∀𝑚,𝑛 {𝑡 𝑚𝑛 }], where 𝑁 min ∀𝑚,𝑛 {𝑡 𝑚𝑛 } and 𝑁 max ∀𝑚,𝑛 {𝑡 𝑚𝑛 } are the minimum and the maximum time required to transmit the data of 𝑁 tasks between two nodes, respectively. Similarly, d𝑗 is assumed within the range [min ∀𝑙 { 𝑒 𝑖 𝑓 𝑙 }, max ∀𝑙 { 𝑒 𝑖 𝑓 𝑙 }], where min ∀𝑙 { 𝑒 𝑖 𝑓 𝑙 } and max ∀𝑙 { 𝑒 𝑖 𝑓 𝑙 } are the minimum and the maximum time required to execute a task with 𝑒 𝑖 cycles, respectively.

  𝑡 𝑘 +𝐸 𝑑 𝑘 )/𝐸 𝑖𝑛𝑖 𝑘 }], and 2) the PP with an objective function to Minimize total node Energy consumption (RER-ME), i.e., min[ 𝑘 ∈M (𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 )]. To evaluate the performances of RER-BE and RER-ME, we introduce an index 𝜙 = (max ∀𝑘 {𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 })/(min ∀𝑘 {𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 }), where 𝐸 𝑡 𝑘 + 𝐸 𝑑 𝑘 ≠ 0. Since 𝐸 𝑡

  , we have 𝑡 𝑠 1 = 0, 𝑡 𝑠 2 = 𝑡 𝑒 1 + 𝜃 12 = 𝑙 ∈L 𝑐 1𝑙 ℎ ′ 1 𝑒 1 𝑓 𝑙 + 𝜃 12 , 𝑡 𝑠 3 = 𝑡 𝑒 1 + 𝜃 13 , 𝑡 𝑠 4 = 𝑡 𝑒 1 + 𝜃 14 and Energy Optimized Task Mapping for Reliable and Real-Time Networked Systems 1:23 Fig. 6. Algorithm performance comparison of HRTM and ASAP. 𝑡 𝑠 5 = 𝑡 𝑒 3 + 𝜃 35 = 𝑡 𝑠 3 + 𝑙 ∈ L 𝑐 3𝑙 ℎ ′ 3 𝑒 3 𝑓 𝑙 + 𝜃 35 . By replacing continuous variable 𝑡 𝑠 𝑖 with binary variables 𝑐 𝑖𝑙 and ℎ ′ 𝑖 , we next solve an integer programming problem with binary variables 𝑞 𝑖𝑘 , 𝑐 𝑖𝑙 , 𝑢 𝑖 𝑗 and ℎ ′ 𝑖 . Finally, when the solution is found, the temporary communication time 𝜃 𝑖 𝑗 is updated by 𝑞 𝑖𝑘 , and the task start time 𝑡 𝑠

	8000							40
			HRTM							HRTM
	4000 5000 6000 7000 Energy consumption (mJ)		ASAP, optimal ASAP, non-optimal			Computation time (s)	10 20 30		ASAP, optimal ASAP, non-optimal
	3000	8	10	12 Task number (G) 14	16	18		0	8	10	12 Task number (G) 14	16	18
	(a) Energy consumption of HRTM and	(b) Computation time of HRTM and
	ASAP with 𝐺 varying.			ASAP with 𝐺 varying.

J. ACM, Vol. 1, No. 1, Article 1. Publication date: January 2023.

J. ACM, Vol. 1, No. 1, Article 1. Publication date: January 2023.

√ √ √ √ √ √

9 ACKNOWLEDGEMENT This work was supported in part by the National Key Research and Development Program of China under Grant 2022YFF0902800, in part by the National Natural Science Foundation of China under Grant 92067111, in part by the Fundamental Research Funds for the Central Universities of China under Grants 2242021R10113 and 2242022K30038, in part by the Southeast University "Zhishan Scholars" Projects under Grant 2242021R40003, in part by Jiangsu Province Frontier Leading Project under Grant BK20202006, and in part by the Jiangsu Provincial Key Research and Development Program under Grant BE2022135.