Polina Kutsevol , Onur Ayan and Wolfgang KellererControl-Aware Scheduling over Multi-hop NetworksAbstract: With the proliferation of wireless networks as an indispensable component for a wide range of distributed CyberPhysical Systems applications, the paradigm of the networking algorithms design independent from application goals abolishes. Thus, the control-aware design of the wireless resource management for wireless networked control systems (WNCSs) is shown to be more effective from the application perspective than the conventional approaches. In WNCS, the controller monitors and actuates the plant through the status updates received from the sensor over the network. This work focuses on application-aware transmission scheduling over multi-hop networks for WNCSs. As an intermediate metric, we use age of information (AoI) that captures the freshness of the data on the controller. Being a widely adopted metric for real-time applications, AoI does not consider the particular goal of control applications. Nevertheless, AoI is tightly coupled with the estimation error at the controller that, in turn, directly impacts control performance. We derive the distribution of AoI in the multi-hop network that exploits a time-varying transmission schedule. Using this distribution, we expresstheexpectedestimationerrortoformulateaminimization objective for the scheduling. We propose exact and heuristic methods for solving the optimization and compare different approachestoresourceallocationwithrespecttoestimationerror and control costs. The proposed scheduling algorithm improves the control performance by at least 15% compared to the scheduling minimizing AoI. Introducing the schedule variability over time allows for further performance improvement by 30% in scenarios with scarce network resources. Keywords: Age of information (AoI) , goal-oriented networking , link scheduling , MAC protocol , multi-hop wireless networked control system (WNCS) 1. IntroductionEVOLVING applications in the fields of Industrial IoT, smart factory and smart city, telehealth, smart agriculture, unmanned aerial vehicles [1], [2] intertwine physical and digital worlds, representing distributed cyber-physical systems (CPS), in which digital components remotely sense and control physical entities. The wireless network becomes an inseparable component between the physical plant, the sensor, and the digital controller. Together they form a feedback loop of a wireless network control system (WNCS) as shown in Fig. 1, where the remote sensor sends the state measurements of the plant to the controller for further actuation. The network task shifts from error-free data delivery at a maximum rate to support the goals defined by control applications through the goal-oriented management of increasingly scarce network resources. Such use cases as wireless sensor networks, IoT, vehicular networks, and swarm intelligence imply the multihop structure of the underlying network. These applications are characterized by increased demand for wireless resources and amplified adverse effects of inefficient resource management on control performance [3], [4]. Thus, the goal-oriented scheduling of application data transmission through multi-hop networks that considers control performance is a critical design challenge. The network resource allocation in the context of WNCSs is extensively studied in existing works. Control-aware scheduling and event-triggering (ET) are some of the most prominent methods used in control theory. The control-aware scheduling policies are designed with the objective of control cost minimization [5], [6]. ET concept [7], [8] enhances resource utilization efficiency, as the status updates are filtered based on their importance for the control process, and only a part of them is transmitted over the network. Even though the control theory methods are theoretically proven to be efficient in terms of control performance, they may underperform in practice because they simplify or neglect the effects caused by network imperfections. Indeed, the transmission delays and packet losses should be considered, as they can result in the stale information available to the controller [9] impairing the accuracy of control decisions. The introduction of the age of information (AoI) metrics [10], [11] measuring the freshness of data on the receiver captures how the communication network affects the performance of control applications. AoI is defined as the time elapsed since the generation of the freshest update available at the receiver. This definition stems from real-time application requirements for timely status updates. Simultaneously, AoI is related to network performance since losses and delays of updates in the network directly affect age. Thus, AoI can be seen as a semantic metric within the semantic communication concept [11]–[15]. The semantic communications paradigm states that the network should be designed in a way to assists the application goals rather than targeting the applicationagnostic error-free transmission of bits. The definition of metrics such as AoI and beyond that capture value or relevance of the transmitted data and cross-layer design of network algorithms w.r.t. application goals are vital components of semantic communications. AoI can be used at the medium access control (MAC) for prioritization of data for scheduling [16] or distributed medium access [17]. Also, the average age can be part of the minimization objective for scheduling [16]. Such approaches enhance the performance of radio resources management w.r.t. application goals compared to conventional networking methods targeting throughput maximization or delays or packet loss minimization. Thus, pure age is often considered a metric to determine the relevance of transmitted data within WNCSs. However, in that case, the one-hour-old information on the drone position is seen to be as relevant as the one-hour-old measurement of the temperature in the office. The indifference of AoI to the purpose of communication stipulates the introduction of metrics beyond age, such as the age of incorrect information [18], the value of information [19], etc. Indeed, motivated by control theory approaches, the exploitation of application data, such that the dynamics of the control process, the mode of its operation, as well as the instantaneous state, can help to emphasize the most and the least relevant information, boosting the efficiency of network resources utilization. The works [20], [21] show that considering cross-layer metrics beyond age improves the control performance. The instantaneous knowledge of the state of all the system elements would allow for extracting the most information regarding the relevance of the communicated data. However, in most cases, especially in multi-hop scenarios, having such knowledge is unrealistic due to the delays and losses associated with transmission over the network between the components. Instead, one can consider the policies targeting improvement of the expected performance over some time horizon based on the average status of the receiver w.r.t. some semantic metrics. There exists an extensive analysis of expected AoI and AoI distribution at the receiver depending on the system structure and average network statistics such as packet loss rate [22]–[24]. It is worth mentioning that many application-aware metrics beyond age, e.g., the expected estimation error of the controller, can be defined as functions of age and parameters of a dynamic system. For instance, the work [25] uses the stationary distribution of AoI in a singlehop system and derives the scheduling for multi-loop WNCSs minimizing expected estimation error, focusing on a singlehop network scenario. Thus, the application-aware policies that optimize the expected performance of WNCSs can be designed using the distribution of age. A. Our ContributionOur main contributions can be split into two parts. The first one is the derivation of the age distribution over a multi-hop network with varying loss probabilities. The second main contribution is applying the derived distribution in the scheduling problem. For the first part, we extend the work [23] that considers AoI distribution for the constant packet loss probabilities. 1 In contrast, in our model, failure probabilities on the links of a multi-hop network are time-varying. Our analysis represents an important extension of the model in [23]. It enables conducting the performance analysis of real-time systems relying on the AoI distribution in more general scenarios compared to [23]. They include the cases when the loss probability of a single transmission is not constant or when the loss probability in a time slot depends on the chosen transmission strategy, e.g., scheduling decision. The accuracy of our analytical model is verified with the help of simulations. 1 Note that the work [23] does not consider any resource allocation problem. For the second part, we apply the obtained AoI distribution to design the scheduling mechanism over a multi-hop network that minimizes the expectation of the estimation error of the controller. We propose the exact and greedy heuristic methods for finding the optimal transmission schedule and demonstrate that the heuristics method shows the performance close to optimal. We analyze the control performance of different scheduling approaches, including age-minimizing scheduling, and show that the proposed policies outperform all alternative mechanisms w.r.t. application goal. Finally, we demonstrate that the time-varying schedule achieves further control performance improvement. B. Related WorkThe approaches to the network resource management of WNCSs in the control theory research consider applicationdefined metrics as an objective. Still, they often make unrealistic assumptions about the communication network. For instance, the work [26] derives central scheduling for minimizing the estimation error for single hop WNCSs, but it neglects packet dropouts in the network. The authors of [27] jointly design policies for sampling, scheduling, and control for multi-hop WNCSs that minimizes control cost but it considers negligible communication delays and no packet losses. The work [28] considered scheduling over multi-hop that is optimized w.r.t. control cost, but there are constant delays and no losses from the network side. On the other side, there exist networking algorithms for IoT and sensor networks designed for generic networks, but they do not consider the performance w.r.t. a particular application. For example, time division multiple access (TDMA)-based scheduling for multi-hop Industrial IoT and Wireless Sensor Networks are developed in [29] and [30]. Here, the authors focus on the networking metrics that are undoubtedly important for real-time control applications, such as cyclic delay, reliability, and energy consumption. However, these works do not consider the application-defined performance metrics, making the efficiency of proposed algorithms w.r.t. applications goals unclear. Within the concept of Semantic Communications introduced in [11]–[15], the network algorithms should prioritize the significance of the transmitted data for application goals. Moreover, they should consider the application performance to efficiently deliver end-to-end services under the constraints posed by the communication network.Works [10], [11] discuss AoI - the semantic metric for real-time applications that captures the timeliness of the transmitted information. It is tightly coupled with a sampling rate defined from the application side and with delays and losses of packets in the network. Thus, AoI can be considered a control- and network-aware metric for control applications, even though it does not take into account the dynamics of particular processes. The minimizations w.r.t. to AoI are widely exploited for resource management of real-time systems for single-hop [16], [22], [31], [32] and multi-hop [22], [24], [33]–[37] scenarios, where the network limitations intensify. The authors of [33], [34], [36] focus on average AoI minimization under interference constraints. First Come First Serve queueing on intermediate nodes is considered in [33], [36], whereas nodes transmit the last available to them updates in [34]. It is worth mentioning that [37] shows that preemptive last generated first served (LGFS) buffers are age-optimal if transmission times follow an exponential distribution. In addition, non-preemptive LGFS is optimal among non-preemptive strategies. Unfortunately, average AoI does not capture the actual AoI performance for many time-sensitive applications, including control. Indeed, short peaks in AoI can be particularly harmful to real-time applications without influencing average age. The works [24], [35] consider peak AoI metric. In particular, the authors of [24] derive the bounds on average and peak AoI depending on the network topology, and [35] considers distributed scheduling that targets low age within the battery limits of energy harvesting sensors. The probability distribution of AoI in a multi-hop network is derived in [23], providing a more meaningful description of the age performance of the system. Exploiting AoI distribution also allows inferring the performance of the system w.r.t. to metrics beyond the age that can be expressed as a function of AoI. As discussed in Section I, the exploitation of application information beyond AoI enhances the performance of network resource management algorithms w.r.t. applicationdefined metrics, with that supporting the ideas of semantic communications. Thus, the authors of [20] show that triggering updates based on the estimation error in combination with AoIbased scheduling results in better control cost performance than the system considering only AoI. Network-aware eventtriggering based on the estimation error in [21] outperforms the age-minimizing sampling policy. New metrics beyond age, such as age of actuation [38], age of incorrect information [18], age of deviation [39], value of information [19] are shown to be beneficial for control and monitoring real-time systems compared to age-minimizing approaches in terms of control costs, system utilization, energy efficiency, or average estimation error. Whereas all the works mentioned above consider singlehop network setup, the studies that evaluate the applicationdefined semantic metrics for network management in multihop scenarios are limited. The work [40] uses the model predictive control method and finds routes over a multi-hop network with delays and packet losses that minimize the control cost over some time horizon in the future. The search for the optimal route involves the consideration of all the channel realizations over the considered horizon, limiting the scalability of this approach. The authors of [41] demonstrate that triggering updates based on the estimation error combined with the reliable broadcasting of status updates over the whole multi-hop networks allows significant energy saving. However, the approach in [41] is designed for less demanding control applications with slow dynamics. Finally, the authors of [42] derive the scheduling minimizing average AoI or average cost that can be represented as a function of AoI in multihop networks with unreliable links using Lyapunov drifts. Unfortunately, this work does not consider the potential of considering control-defined metrics for the definition of the cost function. In addition, the scheduling algorithm from [42] requires instantaneous AoI knowledge over all the system components, which can be infeasible in practical scenarios. To the best of our knowledge, no prior works have designed the scheduling algorithms for WNCS in multi-hop scenarios that consider realistic network constraints and target the optimization of application-defined metrics beyond age. C. NotationsThroughout this paper, vectors and matrices are denoted with small and capital bold symbols, e.g., v and M. [TeX:] $$v^T \text { and } M^T$$ are transposes of the corresponding vector and matrix, and [TeX:] $$M^{-1} \text { and } M^p$$ denote the inverse and pth power of the matrix. The sign % represents a reminder of dividing one integer by another. The set of positive integer numbers is denoted with [TeX:] $$\mathbb{Z}_{+} \text {. }$$ II. SYSTEM MODELIn this work, we consider a WNCS as on Fig. 1, with a plant [TeX:] $$\mathcal{P}$$, the state of which is measured by a remote sensor [TeX:] $$\mathcal{S}$$. The sensor sends the plant status updates to a controller [TeX:] $$\mathcal{C}$$ over a multi-hop wireless communication network consisting of N hops. The controller [TeX:] $$\mathcal{C}$$ is assumed to be co-located with the plant [TeX:] $$\mathcal{P}$$. Thus, based on the received state observations, the controller can immediately apply the calculated control input to the plant. In contrast, the sensor measurements must traverse the network to reach the controller. The physical effects in the wireless medium can potentially result in packet losses, affecting the control decisions and the control performance. A. Control ModelThe plant is modeled in the discrete-time as a linear timeinvariant system with the following dynamic:
(1)[TeX:] $$\boldsymbol{x}[k+1]=\boldsymbol{A} \boldsymbol{x}[k]+\boldsymbol{B} \boldsymbol{u}[k]+\boldsymbol{w}[k],$$where [TeX:] $$x[k+1] \in \mathbb{R}^s$$ is the plant state measured by the sensor at a time step k + 1. It is affected by the state x[k] at the previous time step, i.e., measured [TeX:] $$T_s$$ before, through the time-invariant state matrix [TeX:] $$\boldsymbol{A} \in \mathbb{R}^{s \times s}$$ Here, [TeX:] $$T_s$$ is a constant sampling period. The control input [TeX:] $$\boldsymbol{u}[k] \in \mathbb{R}^g$$ calculated by the controller at time step k contributes to the next state through the time-invariant input matrix [TeX:] $$B \mathbb{R}^{s \times g}$$. Disturbance vectors w at each time step are independent and identically distributed according to the zero-mean Gaussian distribution with covariance matrix [TeX:] $$\boldsymbol{W} \in \mathbb{R}^{s \times s} \text {, i.e., } \boldsymbol{w} \in \mathcal{N}(\mathbf{0}, \boldsymbol{W}).$$ The set-point of the plant is [TeX:] $$0 \in \mathbb{R}^s$$, i.e., the controller goal is to drive the plant to zero and herewith spend minimum control effort. This goal is formalized with the introduction of the linear quadratic Gaussian (LQG) cost, also referred to as control cost that the controller should minimize:
(2)[TeX:] $$\mathcal{J} \triangleq \limsup _{\mathcal{T} \rightarrow \infty}\left(\frac{1}{\mathcal{T}} \sum_{k=0}^{\mathcal{T}-1}(\boldsymbol{x}[k])^T \boldsymbol{Q} \boldsymbol{x}[k]+(\boldsymbol{u}[k])^T \boldsymbol{R} \boldsymbol{u}_i[k]\right),$$where [TeX:] $$\mathcal{T}$$ is a time horizon for the considered control task, [TeX:] $$\boldsymbol{Q} \in \mathbb{R}^{s \times s} \text { and } \boldsymbol{R} \in \mathbb{R}^{g \times g}$$ are weighting matrices used to define how much the state dynamics is prioritized over the control effort or vise versa. If we suppose that the controller has access to the latest state measurement, following the widely used linear quadratic regulator (LQR) design described in [43], the control law is derived through the minimization of the control cost (2) as:
where [TeX:] $$\boldsymbol{K} \in \mathbb{R}^{g \times s}$$ is the optimal feedback matrix. [TeX:] $$\boldsymbol{K}$$ can be found through the solution [TeX:] $$\boldsymbol{P}$$ of discrete-time algebraic Ricatti equation:
(4)[TeX:] $$\boldsymbol{P}=\boldsymbol{A}^T \boldsymbol{P} \boldsymbol{A}-\left(\boldsymbol{A}^T \boldsymbol{P} \boldsymbol{B}\right)\left(\boldsymbol{R}+\boldsymbol{B}^T \boldsymbol{P} \boldsymbol{B}\right)^{-1}\left(\boldsymbol{B}^T \boldsymbol{P} \boldsymbol{A}\right)+\boldsymbol{Q} .$$Positive semi-definite [TeX:] $$P \in \mathbb{R}^{s \times s}$$ solving (4) is then used to obtain the optimal feedback matrix [TeX:] $$\boldsymbol{K}$$ as:
(5)[TeX:] $$\boldsymbol{K}=\left(\boldsymbol{R}+\boldsymbol{B}^T \boldsymbol{P} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^T \boldsymbol{P} \boldsymbol{A} .$$In our system, however, the actual plant state may not be available at the controller because of the packet losses in the network. Thus, the controller has to estimate the plant state based on the available observations. Similar to [25], the Kalman filter estimator that minimizes the mean squared estimation error (MSE) is given as follows:
(6)[TeX:] $$\hat{\boldsymbol{x}}[k]=\boldsymbol{A}^{\Delta_{\mathcal{C}}[k]} \boldsymbol{x}[\nu(k)]+\sum_{q=1}^{\Delta_{\mathcal{C}}[k]} \boldsymbol{A}^{q-1} \boldsymbol{B} \boldsymbol{u}[k-q],$$where [TeX:] $$\nu[k]$$ is the generation time step of the freshest update available at the controller, and [TeX:] $$\Delta_{\mathcal{C}}[k]=k-\nu(k)$$ is the time elapsed since this generation expressed in the number of sampling intervals. In other words, [TeX:] $$\Delta_{\mathcal{C}}$$ represents AoI at the controller. According to the separation principle defined in control theory, for the system with Gaussian observations, the estimator can be designed independently of the optimal feedback matrix. Thus, the combination of LQR from (3) with the Kalman filter from (6) leads to the following control law:
Note that the estimation error does not define the control performance but is tightly coupled with it. Indeed, faulty estimation results in sub-optimal control inputs, resulting in the inability of the controller to drive the plant to zero. The deviation of the plant state from equilibrium contributes to (2). Moreover, when the controller finally corrects its estimation, more efforts should be taken to enforce the plant stabilization, also increasing (2). Next, we introduce the MSE of the controller estimation, which is, as has been discussed, a vital metric for control applications. First, we define an estimation error as the difference between the instantaneous state and its estimation at the controller:
The MSE is then expressed as the expectation of a square of (8):
(9)[TeX:] $$M S E[k]=\mathbb{E}\left[e[k]^T e[k]\right]=\sum_{t=0}^{\Delta_{\mathcal{C}}[k]-1} \operatorname{tr}\left(\left(\boldsymbol{A}^T\right)^t \boldsymbol{A}^t \boldsymbol{W}\right),$$where the second equality can be derived as in [25] by subtracting (6) from (1) and taking the expectation as in the definition ofMSE. The instantaneousMSE can be expressed as a function of age at the controller, witnessing that AoI is a promising semantic metric for control applications. B. Network ModelIn this work, we exploit the network model from [23] with some modifications. In particular, we consider a line network consisting of N links that connect the sensor and the controller through relay nodes, as illustrated in Fig. 1. In our network model, the first node is a sensor that initiates the transmission of every state measurement in a single data packet. The packet should traverse N network links and N − 1 relay nodes [TeX:] $$\left\{\mathcal{R}_1, \mathcal{R}_2, \cdots, \mathcal{R}_{N-1}\right\}$$ to arrive to a controller representing (N + 1)th node. Note that we do not consider the design of the routing algorithm. That motivates the line network scenario because the path from the source to the destination constitutes a line network as soon as the routing decision is made. The transmissions over intermediate nodes are subject to potential failures due to fading in the wireless medium. We consider the Rayleigh fading model, with losses of packets on the given link being independent of each other. Additionally, as the positions of nodes are fixed at different points in space, each link is characterized by some constant loss probability. Thus, the sequence of transmissions on the link n can be modeled as a Bernoulli process with a constant failure probability [TeX:] $$p_n$$ as shown in Fig. 1. The interference among different links is avoided through time division multiplexing (TDM). In particular, the time is divided into transmission slots of a constant duration [TeX:] $$T_t$$, and only a single link is granted a transmission in each slot. Each transmission between two nodes starts at the beginning of a transmission slot and finishes within [TeX:] $$T_t$$ interval. In our model, the transmission rate is higher than the sampling rate, and [TeX:] $$T_s=m T_t,$$ i.e., there are m transmission slots within each sampling interval. Fig. 2 shows an example sequence of transmission slots and sampling intervals, each containing m = 4 transmission slots. A new state measurement is generated at the sensor at the beginning of every sampling interval. The sensor attempts to transmit this packet in every transmission slot within the next [TeX:] $$T_s$$ interval assigned to the link between [TeX:] $$\mathcal{S} \text { and } \mathcal{R}_1$$. Simultaneously, each relay node [TeX:] $$\mathcal{R}_n$$ attempts to transmit the most recent packet available at this node in each transmission slot, for which the link n between [TeX:] $$\mathcal{R}_n$$ and [TeX:] $$\mathcal{R}_{n+1}$$ is activated. As one can infer from (7) and (6), only the last generated updates available at the controller influences the control input, making older measurements not relevant for the control process. Thus, when a new update arrives at each relay node, it replaces the previous packet, which is, in turn, discarded. Therefore, we eliminate the queuing in the network, limiting the packets’ transmission times and, consequently, AoI and MSE (see (9)) at the controller, contributing to the decrease of the control cost. In this work, we focus on the design of the activation patterns of the links in transmission slots, i.e., on the transmission scheduling, w.r.t. the improvement of the control performance. The scheduling algorithm assigns the periodic distribution of transmission slots within links for L sampling intervals2. Similar to [23], we assume that the scheduler assigns the transmission slots to the links in the same order as they appear along the path. With such a design, if at least one transmission on each link is successful within a given sampling interval, the controller would receive a fresh state update generated by the sensor update in the end of the same time step. In this work, we assume m > N, meaning that at least one slot can be assigned to each link within every sampling interval. The example schedule of the length L = 2 for N = 3 is given in Fig. 2. Within the first scheduling slot, 2 transmission slots are assigned to the link from the sensor [TeX:] $$\mathcal{S}$$ to the first relay, and the links from [TeX:] $$\mathcal{R}_1$$ to [TeX:] $$\mathcal{R}_2$$ and from [TeX:] $$\mathcal{R}_2$$ to the controller are given following two consecutive transmission slots. In the second slot of the schedule, the activation order of links stays the same, but now the link from [TeX:] $$\mathcal{R}_1$$ to [TeX:] $$\mathcal{R}_2$$ gets two slots, and other links by 1 slot. The schedule is then repeated. 2 If the schedule length is L, the allocation of slots is repeated periodically after each L sampling intervals. We aim to design a scheduler that minimizes the average MSE of the controller estimation. As MSE can be represented as a function of the instantaneous age (see (9)), the average MSE over the control horizon can be expressed using the distribution of instantaneous age as in [25]. Given the constant loss probability on the link within a sampling interval, the age distribution in the similar multi-hop network scenario is derived in [23]. The introduction of the schedule of the length L greater than one sampling interval leads to the non-constant failure probability on the link3. In this work, we extend the analysis from [23] to the case when the loss probability on the link is not constant but follows a periodic pattern. 3 This is due to the varying number of transmission slots assigned to a link within different sampling intervals of a schedule. III. AOI DISTRIBUTION OVER MULTI-HOP NETWORKWe consider the distribution of AoI in the multi-hop network where the length of the schedule is L sampling intervals. That means that the sensor and each relay node are assigned with [TeX:] $$r_n^l, l \in\{1,2, \cdots, L\}$$ transmission slots in lth sampling interval of the schedule 4. Here n = 0 denotes the sensor node [TeX:] $$\mathcal{S}$$, and otherwise n refers to the relay node [TeX:] $$\mathcal{R}_n$$. If [TeX:] $$p_n$$ is the constant loss probability on the link n of the single transmission in a single transmission slot, the probability [TeX:] $$P_n^l$$ of a failure in the lth sampling period of a schedule can be expressed as: 4 In the following discussion, under the assigning a transmission slot to the node n we mean giving it to the link starting at node n. Also, the schedule with the sequence number l refers to the assignment in the lth sampling interval of the schedule.
i.e., the failure on the link n occurs if all [TeX:] $$r_n^l$$ transmissions fail, and the independence of the outcomes of the consecutive transmissions on one link is used. Note that each transmission slot should be assigned to a maximum of one link, such that the interference is avoided, i.e.:
Without loss of generality, assume that in the first time step k = 0, each link is initialized with the first schedule [TeX:] $$r_n^l$$. Thus the schedule with the sequence number k%L+1 is employed at the time step k. Let [TeX:] $$\Delta_n[k], \quad n \in\{1,2, \cdots, N\}$$ denote the age at the relay node [TeX:] $$\mathcal{R}_n$$ in the sampling interval k after the transmission on the link n−1. Recall that [TeX:] $$\Delta_N[k]$$ is AoI at the receiver, i.e., at the controller. The dynamics of AoI can be expressed in the following way:
(12)[TeX:] $$\Delta_n[k]= \begin{cases}\Delta_{n-1}[k], & \text { if } \gamma_{n-1}[k]=1 \\ \Delta_n[k-1]+1, & \text { if } \gamma_{n-1}[k]=0,\end{cases}$$where [TeX:] $$\gamma_{n-1}[k]=1$$ if at least one transmission on the link n−1 has been successful in kth sampling interval, i.e., the nth node has received a new update at time step k. We denote with [TeX:] $$\Delta_0[k]$$ the age at the transmitter side, i.e., at the sensor. Since the sensor always has access to the most recent observation, [TeX:] $$\Delta_0[k]=0 \forall k.$$ The example AoI evolution for N = 3 is given in Fig. 3. Like the control dynamics, AoI changes in the discrete time steps of [TeX:] $$T_s$$. If an outcome on the link n−1 is successful within the kth time step (denoted with a tick), the node n receives the update that has been available on the node n − 1 and [TeX:] $$\Delta_n[k]$$ equalized to the age [TeX:] $$\Delta_{n-1}[k]$$ on the previous link at the end of kth sampling interval. Otherwise, the information on the node n ages by 1 sampling interval, i.e., it is incremented by one. Similarly to [23], we derive AoI at the controller recursively. First, consider the aging process [TeX:] $$\Delta_1[k]$$ at the first relay node [TeX:] $$\mathcal{R}_1.$$ If [TeX:] $$\Delta_1[k]=\delta_1$$, that means that there has been a successful transmission on the link from the sensor that has resulted in a drop of AoI to zero [TeX:] $$\delta_1+1$$ sampling periods ago, followed by [TeX:] $$\delta_1$$ unsuccessful sampling periods incrementing [TeX:] $$\Delta_1$$. The probability of such a sequence depends on the loss probabilities [TeX:] $$P_0^l$$ at each time step, which is, in turn, defined by the sequence number l of each slot in the schedule. Since the first schedule is employed at k=0, the schedule with a sequence number k%L+1 is used in the kth sampling interval. This results in the following expression of AoI:
(13)[TeX:] $$\begin{aligned} \operatorname{Pr}\left[\Delta_1[k]=\delta_1\right] = & \\ & \left(1-P_0^{\left(k-\delta_1\right) \% L+1}\right) \prod_{d=k-\delta_1+1}^k P_0^{d \% L+1}, \end{aligned}$$where we iterate from the slot [TeX:] $$k-\delta_1$$ with the successful transmission with the probability [TeX:] $$1-P_0^{\left(k-\delta_1\right) \% L+1}$$ through further [TeX:] $$\delta_1$$ slots with failures with probabilities [TeX:] $$P_0^{d \% L+1}$$ till the current slot k. Next, we define the probability of AoI at the nth node being [TeX:] $$\sigma_n$$ given the age at the node n−1 as [TeX:] $$\sigma_{n-1}$$ at a time step when the nth node has received its the freshest update. Analogously to (13), provided that [TeX:] $$\delta_n \geq \delta_{n-1},$$ the AoI reaches [TeX:] $$\delta_n$$ on the node n, if there has been a successful transmission on the link n − 1 at the time step [TeX:] $$k-\left(\delta_n-\delta_{n-1}\right)$$ followed by [TeX:] $$\delta_n-\delta_{n-1}$$ failures on the same link. Thus, we get the following expression:
(14)[TeX:] $$\begin{aligned} & \operatorname{Pr}\left[\Delta_n[k]=\delta_n \mid \Delta_{n-1}\left[k-\left(\delta_n-\delta_{n-1}\right)\right]=\delta_{n-1}\right] \\ & =\left(1-P_{n-1}^{\left(k-\left(\delta_n-\delta_{n-1}\right)\right) \% L+1}\right) \prod_{d=k-\left(\delta_n-\delta_{n-1}\right)+1}^k P_{n-1}^{d \% L+1} . \end{aligned}$$Summing over all possible [TeX:] $$\delta_{n-1}$$, according to the law of total probabilities, we get:
(15)[TeX:] $$\begin{aligned} & \operatorname{Pr}\left[\Delta_n[k]=\delta_n\right] \\ & =\sum_{\delta_{n-1}=0}^{\delta_n} \operatorname{Pr}\left[\Delta_n[k]=\delta_n \mid \Delta_{n-1}\left[k-\left(\delta_n-\delta_{n-1}\right)\right]=\delta_{n-1}\right] \\ & \quad \times \operatorname{Pr}\left[\Delta_{n-1}\left[k-\left(\delta_n-\delta_{n-1}\right)\right]=\delta_{n-1}\right] . \end{aligned}$$To calculate the age distribution on the node n at a given time step k, one starts with (15) that depends on the conditional probabilities (14) and the distributions on the previous link n − 1. Thus, the distribution is defined recursively. Further, we would like to obtain an expression for the average AoI distribution over the control horizon, i.e., independent from the time step k. Note that (15) does not depend on the particular k but rather on the sequence number of a kth time step within a schedule, i.e., on k%L+1. We denote (15) for all k, s.t. k%L + 1 = l, with [TeX:] $$\operatorname{Pr}\left[\Delta_n=\delta_n\right](l),$$ where we omitted the dependence on k. The distribution of AoI averaged over the infinite horizon reads as:
(16)[TeX:] $$\begin{aligned} \operatorname{Pr}\left[\Delta_n=\delta_n\right] & =\limsup _{\mathcal{T} \rightarrow \infty} \frac{1}{\mathcal{T}} \sum_{k=0}^{\infty} \operatorname{Pr}\left[\Delta_n[k]=\delta_n \mid k\right] \\ & =\sum_{l=1}^L \frac{1}{L} \operatorname{Pr}\left[\Delta_n=\delta_n\right](l), \end{aligned}$$since [TeX:] $$\frac{1}{L}$$ part of the time steps over the infinite horizon is assigned with lth schedule [TeX:] $$\forall l \in\{1, \cdots, L\}.$$ IV. PROBLEM FORMULATIONUsing the AoI distribution (16) and instantaneous MSE expression (9), we can define the global average expected MSE over infinite time horizon as:
(17)[TeX:] $$\begin{aligned} C(\boldsymbol{P}) & =\limsup _{\mathcal{T} \rightarrow \infty} \frac{1}{\mathcal{T}} \sum_{k=0}^{\mathcal{T}-1} M S E[k] \\ & =\sum_{\delta_N=1}^{\infty} \operatorname{Pr}\left[\Delta_N=\delta_N\right] \sum_{t=0}^{\delta_N-1} \operatorname{tr}\left(\left(\boldsymbol{A}^T\right)^t \boldsymbol{A}^t \boldsymbol{W}\right), \end{aligned}$$where [TeX:] $$\boldsymbol{P}$$ is a matrix denoting loss probabilities of all the links in each sampling interval of the schedule, i.e., [TeX:] $$\boldsymbol{P}=\left\{\left\{P_0^1, P_0^2, \cdots, P_0^L\right\},\left\{P_1^1, P_1^2, \cdots, P_1^L\right\}, \cdots,\left\{P_{N-1}^1\right.\right.\left.\left.P_{N-1}^2, \cdots, P_{N-1}^L\right\}\right\} .$$ Since [TeX:] $$P_n^l$$ is defined by the slot allocation [TeX:] $$r_n^l$$ as in (10), the average estimation error (17) can be written as a function of [TeX:] $$\left\{\boldsymbol{r}_0, \boldsymbol{r}_1, \cdots, \boldsymbol{r}_{N-1}\right\},$$ where [TeX:] $$\boldsymbol{r}_n=\left\{r_n^1, r_n^2, \cdots, r_n^L\right\}$$ is the schedule for nth link. The optimization problem for the scheduling problem, i.e., allocation of transmission slots to N links over L sampling intervals, can be formulated as:
(18)[TeX:] $$\begin{array}{ll} \min _{\boldsymbol{r}_1, \boldsymbol{r}_2, \cdots, \boldsymbol{r}_N} C\left(\boldsymbol{r}_0, \boldsymbol{r}_1, \cdots, \boldsymbol{r}_{N-1}\right) \\ \text { s.t. } & \sum_{n=0}^{N-1} r_n^l \leq m \forall l \\ & r_n^l \in \mathbb{Z}_{+} \forall n \forall l. \end{array}$$Here, the first constraint ensures that each transmission slot is allocated at most to a single link at a time. We enforce that each link should be allocated with at least one slot within a sampling interval, i.e., [TeX:] $$r_n^l \geq 1.$$ A. Optimal SolutionThe optimization in (18) represents a non-linear integer problem (NLIP) since the variables are integers, and the probability distribution (16) involves the exponential functional from these variables. We use an IPOPT solver within the GEKKO optimization suite for Python [44] to obtain the optimal solution. Note that the optimization problem is not guaranteed to be convex for any set of parameters. Thus, the gradient descent method can result in finding the local minimum that is not globally optimal. We repeat the optimization with random initialization values to ensure that the solver does not terminate in the local minimum. The objective of the optimization is a recursive function with a time complexity of [TeX:] $$O\left(\left(\sigma_N+1\right) N L\right).$$ Thus, the solution time using GEKKO solver sharply increases for larger problems. As an alternative, we present a greedy heuristic approach that is more scalable. B. Heuristic ApproachThe distribution of the transmission slots within a schedule implies that when an additional slot is assigned to some link within some sampling interval, there is a lower probability of losing the packet on this link within a given time slot. This leads to a lower probability of having high age at the receiver and decreases total MSE (17). For the greedy approach, we use the fact that in total m ċ L slots should be distributed, and assigning each slot reduces the minimization objective. As specified in Algorithm 1, in the beginning, in each sampling interval l of a schedule, each link n is allocated with [TeX:] $$r_n^l=1$$ transmission slot. Each scheduling slot’s residual budget [TeX:] $$b_l \text { is } m-N \text {. }$$ Then, for each transmission slot that is to be scheduled, the algorithm probes the resulting MSE if this slot would be assigned to every sampling interval [TeX:] $$l_t$$ of a schedule that still has available slots in the budget and to every link [TeX:] $$n_t$$. The intermediate allocation [TeX:] $$\rho_n^l \forall n \in\{0, \cdots, N-1\} \text {, }$$ [TeX:] $$\forall l \in\{1, \cdots, L\}$$ that minimizes the average MSE is saved into [TeX:] $$r_n^l$$. The budget of available slots for this scheduling interval [TeX:] $$L^*$$ is decremented accordingly. The next allocation that includes the probing of the next slot is built on top of the new [TeX:] $$r_n^l$$. The procedure is repeated until m slots for each of L sampling intervals are distributed. Note that [TeX:] $$\rho_n^l \text { and } \zeta_n^l$$ [TeX:] $$\forall n \in\{0, \cdots, N-1\}, \forall l \in\{1, \cdots, L\}$$ are temporal variables storing currently the best allocation and the allocation being probed for a given transmission slot, respectively. To calculate the average MSE for each allocation, [TeX:] $$\rho_n^l \text { and } \zeta_n^l$$ are stacked to vectors [TeX:] $$\boldsymbol{\rho}_n \text { or } \boldsymbol{\zeta}_n$$ to derive cost C from (18). V. NUMERICAL RESULTSIn this section, we validate the analytical derivation of the AoI distribution with the help of the simulator. Furthermore, we present an analysis of the proposed scheduling schemes and a comparison with other approaches. The parameters chosen for the control system and the network are the following. The sampling period [TeX:] $$T_s=100 \mathrm{~ms}$$ consists of m = 10 transmission slots, each by [TeX:] $$T_T=10 \mathrm{~ms}$$5. The probabilities [TeX:] $$p_n$$ of the single transmission failure on each of N = 5 links are varied in different experiments. We consider the scalar control system, with state and input matrices in (1) being scalars and having the following values: [TeX:] $$\boldsymbol{A}=1.4, \boldsymbol{B}=1 \text {. }$$ In addition, [TeX:] $$\boldsymbol{W}=1.$$ The weights of the state deviation and control effort in the control cost (2) are equal: [TeX:] $$\boldsymbol{Q}=\boldsymbol{R}=1.$$ 5 The transmission slot of 10 ms is an option within the numerology of many communication standards for CPS, including WirelessHART, IEEE 802.15.4, etc. [1] Table I
First, we present a theoretical and simulated probability mass function (PMF) of AoI for the varying loss probabilities per link per sampling interval. Table I gives three sets of values [TeX:] $$S_1, S_2 \text {, and } S_3 \text {, }$$ for which the PMFs in Fig. 4 are shown. Three values for each link n and each set represent the loss probability over three consecutive slots in the schedule. Thus, there are two links with high loss probabilities (n = 0 and n = 3) for the first set [TeX:] $$S_1,$$ two more links (n = 1 and n = 4) have high loss probabilities in [TeX:] $$\S_2 \text {, }$$ and all links are lossy in [TeX:] $$S_3.$$ Fig. 4 shows that the derived PMF coincides with the simulation results for all sets of probabilities, witnessing the accuracy of the analytical distribution from (16). Note that for each set, we performed 100 simulation runs each by 10000 time steps. The resulting bars represent the average relative frequency for given [TeX:] $$\Delta_n$$ over these 100 runs. The PMFs shift towards higher age values when the failure rates over links increase. Note that long tails of the AoI distribution imply a non-negligible probability of facing high age at the controller and significantly contributing to the resulting estimation error (17), where the MSE terms exponentially grow with age as illustrated with the right axis on Fig. 4. To prevent drastic control performance degradation, the scheduler should distribute the resources over links in a way to eliminate the chances of significant age growth at the controller. Thus, the exact AoI distribution is critical for analyzing the control performance, especially in scenarios with constrained network resources and higher loss probabilities. TABLE II
With Fig. 5, we demonstrate how the particular distribution of transmission slots over links influences the estimation error of the controller. The constant loss probabilities on the links are set to [TeX:] $$\boldsymbol{p}_1$$ from Table II, i.e., [TeX:] $$p_0=0.1, p_1=0.25,$$ and so on. The schedule length L is one, i.e., the slots distribution is the same for all sampling intervals. Fig. 5 contains both theoretical expectation and simulation results, with the boxplots representing average MSE recorded in 100 runs each by 10000 time steps. The expected MSE is calculated according to (8), whereas the simulated MSE is calculated as:
(19)[TeX:] $$\overline{\mathcal{C}}=\frac{1}{\mathcal{T}} \sum_{k=0}^{\mathcal{T}-1}(\boldsymbol{x}[k]-\hat{\boldsymbol{x}}[k])^2,$$where [TeX:] $$\mathcal{T}$$ is the total duration of one experiment measured in sampling intervals, i.e., [TeX:] $$\mathcal{T}=10000$$. Note that the expectedMSE matches the simulation results. If most transmission slots are assigned to the link from the sensor with the highest success probability, more lossy links do not get enough resources. This results in the worst MSE performance of such allocation, almost 20 times worse than the optimal. Assigning more resources to the link 4 with the highest failure rate also shows poor performance. It is nearly 7 times worse than the optimal. Indeed, assigning the link 4 with 6 transmission slots results in a very low loss probability over the time step on the 5th link, i.e., [TeX:] $$P_4^1=0.4^6 \approx 0.004$$. At the same time, the loss probability on other links stays relatively high, negatively affecting the MSE performance. Among the considered options, the allocation [1, 2, 2, 2, 3] results in the best MSE. One can conclude that appropriate scheduling is vital for control performance. As discussed in Section IV-A, we derive the optimal slots allocation via solving (18), i.e., MSE minimization problem, with the help of the GEKKO optimization suite. Further, we compare the control performance of the optimal allocation for different schedule lengths L with other approaches, including the greedy heuristic that also targets (18). Also, we consider the scheduling approaches minimizing average AoI and the end-to-end packet loss probability. The latter represents a conventional networking approach agnostic to the application goal. Finally, with the self of the simulation, we analyze the performance of the random allocation of slots to infer how much improvement the proposed control-aware methods can bring. In the next evaluations, apart from MSE, we demonstrate the simulated LQG cost performance of the control loop, which is the ultimate performance metric of control applications. We calculate the average LQG cost similar to (2) for the limited time horizon:
(20)[TeX:] $$\overline{\mathcal{J}}=\frac{1}{K} \sum_{k=0}^{K-1}\left((\boldsymbol{x}[k])^T \boldsymbol{Q} \boldsymbol{x}[k]+(\boldsymbol{u}[k])^T \boldsymbol{R} \boldsymbol{u}_i[k]\right).$$Fig. 6(a) shows the performance of different scheduling approaches in terms of MSE for varying error rates of a single transmission per link that are given in Table II. In particular, [TeX:] $$\boldsymbol{p}_1$$ represents the most reliable network. Drop rates are moderate for [TeX:] $$\boldsymbol{p}_2$$ and the highest for [TeX:] $$\boldsymbol{p}_3$$, representing the most challenging scenario. From Fig. 6(a), we conclude that random allocation results in poor estimation performance for any network configuration, but the degradation is more significant for higher loss probabilities [TeX:] $$\boldsymbol{p}_3$$6. For [TeX:] $$\boldsymbol{p}_1$$, all other methods result in the same allocation and same performance. However, for [TeX:] $$\boldsymbol{p}_2$$, the estimation performance of the minimum AoI and minimum loss probability methods is 15% worse than the performance of the optimal solution minimizing MSE and a greedy heuristics for L = 1. Increasing the schedule length to L = 2 improves performance by 2%, which is a minor gain. Note that the heuristic is effective since it finds the allocation that results in the same MSE performance as the optimal solution for all the considered scenarios. 6 The results for random allocation for [TeX:] $$\boldsymbol{p}_3$$ are not shown due to high magnitude. The relative performance degradation of the methods not taking MSE into account increases for [TeX:] $$\boldsymbol{p}_3$$. The minimum AoI approach shows 2.5 times worse performance than the optimum solution and heuristics for L = 1. Indeed, as witnessed by Fig. 4, the PMF of AoI shifts towards higher values for higher loss probabilities. This introduces exponentially increasing terms in (8) corresponding to high age and contributing to resulting MSE. The approach of minimizing average AoI does not weigh this tail of the distribution as much as the optimal solution. Interestingly, for L = 2, the scheduler has more degrees of freedom, and the optimal allocation gives a further 25% improvement of the MSE. It is worth mentioning that although AoI minimizing scheduling does not minimize MSE, its performance is more than 13 times better than the approach minimizing loss probability over the path. Thus, freshness minimization is a promising approach in case it is not feasible to consider application-related aspects such as the particular control model and expected MSE. An important observation is that the simulation results confirm the theoretical values. For higher MSE values, the simulation shows slightly smaller results than expected. This is explained by the fact that the tail of the AoI distribution contributes a lot to MSE. However, these high AoI values have a very low probability, and there are not enough samples in the simulation corresponding to these high-AoI time steps. The result that the scheduling minimizingMSE leads to the lowest MSE is expected. Further, we analyze the LQG cost performance of the proposed scheduling approaches, which is the ultimate metric for control applications. Fig. 6(b) shows the simulated LQG cost for the same parameters as on Fig. 6(a). When comparing the control cost for different approaches, we see a similar trend for LQG cost as for MSE. In particular, for p1, all the methods show similar control cost performance, except for the random allocation that performs 2.3 times worse. For [TeX:] $$\boldsymbol{p}_1$$ and [TeX:] $$\boldsymbol{p}_3$$, the heuristic approach shows the same results as the minimum MSE scheduler, outperforming the second best-performing approach minimizing AoI by 10% and by 100%, respectively. Thus, control-aware scheduling shows the best performance in terms of control costs among all the considered methods. Further, we analyze how much control performance improvement can be achieved if the schedule length L increases. Note that increasing the schedule length increases the size of the optimization problem (18). Using the GEKKO scheduler is infeasible for large problems due to its scalability issues. However, as the heuristic has proven its efficiency, we can obtain the MSE-minimizing allocations for higher L with the greedy method. Since for [TeX:] $$\boldsymbol{p}_1$$ all the approaches show the same performance, and increasing L from 1 to 2 does not bring any benefits, we can conclude that the obtained allocation for L = 1 is the best performing. Fig. 7 and 8 show how theMSE and LQG performance vary with increasing schedule length for more challenging networks with blocking probabilities [TeX:] $$\boldsymbol{p}_2$$ and [TeX:] $$\boldsymbol{p}_2$$. For comparison, we also show the performance of the ageminimizing approach at a larger scale than in Figs. 4 and 6(b). Fig. 7 demonstrates that for [TeX:] $$\boldsymbol{p}_2$$, the schedule with L = 3 shows the best performance, with the improvement of 3% and in MSE and LQG cost compared to L = 1. The gains stagnate for higher schedule length. More significant improvements can be achieved for [TeX:] $$\boldsymbol{p}_3$$ as seen in Fig. 8. In particular, L = 3 achieves more than 30% gain in MSE and the control cost. Therefore, the additional scheduling flexibility is especially beneficial for lossy networks. The reason is that the AoI distribution has a longer tail towards higher age values for a more challenging network. Thus, a smaller decrease in the high AoI probability significantly changes overall MSE and LQG cost. This again proves that efficient resource management w.r.t. application goals is crucial for scenarios with more significant adverse effects from the network side. Thus, the comprehensive analysis of the influence of the actual network on the achievement of the application goals and adaptation of network resource management algorithms w.r.t. these goals enhance the efficiency of the network utilization. VI. CONCLUSIONIn this work, we demonstrated the benefits of the application-oriented design of networking algorithms for the use-case of control. In particular, we consider the transmission scheduling over a multi-hop network that connects the WNCS components. We derived the distribution of AoI on the receiver node for a time-varying scheduling pattern. Using AoI distribution, we formulated the optimization problem of minimizing global average controller estimation error that is tightly coupled with the control cost. Our approach shows at least 15% improvement in the estimation error and at least 10% in control cost compared to AoI-minimising allocations. More degrees of freedom in the time-varying scheduling enabled further estimation error and control cost improvement by up to 30% in the scenarios with low network resource availability. Thus, application-aware design of the network resource management enhances the efficiency of the network resources utilization under the constraints dictated by application goals, which are the ultimate objective of the current networks. BiographyPolina KutsevolPolina Kutsevol received the B.Sc. degree in Applied Mathematics and Physics from Moscow Institute of Physics and Technology, Moscow, Russia, in 2019, and the M.Sc. degree in Communication Engineering from Technical University of Munich, Munich, Germany, in 2021, where she is currently pursuing the Ph.D. degree with the Chair of Communication Networks. Her current research interests include resource management for wireless and mobile communication networks, cyber-physical systems and networked control systems. BiographyOnur AyanOnur Ayan (S’18) received his B. Sc. degree in Electrical Engineering in 2013, and his M. Sc. degree in 2017 at Technical University of Munich (TUM), Munich, Germany. He received his Ph.D. degree in Electrical Engineering at the Chair of Communication Networks from the same university in 2023. His research interests are design and evaluation of wireless networked control systems, cyberphysical systems and semantics of information. BiographyWolfgang KellererWolfgang Kellerer (M’96, SM’11) is a Full Professor with the Technical University of Munich (TUM), Germany, heading the Chair of Communication Networks at the School of Computation, Information and Technology. He received his Ph.D. degree in Electrical Engineering from the same university in 2002. He was a Visiting Researcher at the Information Systems Laboratory of Stanford University, CA, US, in 2001. Prior to joining TUM, Wolfgang Kellerer pursued an industrial career being for over ten years with NTT DOCOMO’s European Research Laboratories. He was the Director of the infrastructure research department, where he led various projects for wireless communication and mobile networking contributing to research and standardization of LTE-A and 5G technologies. In 2015, he has been awarded with an ERC Consolidator Grant from the European Commission for his research on flexibility in communication networks. He currently serves as an Associate Editor for IEEE Transactions on Network and Service Management and as the area editor for network virtualization for IEEE Communications Surveys and Tutorials. References
|