# Multiprocessor Scheduling of Sensor Transactions for Real-Time Data Quality Maintenance

Authors: Tian Bai; Zhijie Li; Bo Fan
Journal: Mobile Information Systems
 (2020)

---

## Abstract

In cyber-physical systems, sensor transactions should be effectively scheduled to maintain the temporal validity of real-time data objects. Previous studies on sensor transaction scheduling mainly focus on uniprocessor systems. In this paper, we study the problem of data quality-based scheduling of sensor transactions on multiprocessor platforms. The data quality is defined to describe the validity degree of real-time data objects. Two methods, named the Partitioned Scheduling for Quality Maximization (P-QM) and the improved P-QM scheduling (IP-QM), are proposed. P-QM maximizes the data quality by judiciously determining the preallocated computation time of each sensor transaction and assigns the transactions to different processors. IP-QM improves the data quality obtained from P-QM by adaptively executing transaction instances on each processor based on the current status of the system. It is demonstrated through experiments that IP-QM can provide higher data quality than P-QM under different system workloads.


---

## Body

## 1. Introduction

Cyber-physical systems (CPS) feature a tight combination of the computational and physical elements of the systems [1–3]. They are widely used in applications that need to process real-time data in a timely manner. Example applications include road traffic control and industry process control [4–6]. The real-time data objects model the current status of entities in a system environment. Different from the traditional data objects, their values may become invalid with the passage of time. Associated with each real-time data object is a validity interval that specifies the lifetime of its current value. If this lifetime does not expire, the data object is temporally valid. Otherwise, it becomes invalid and a new data value needs to be installed.In CPS, sensor transactions are generated to sample the status of external entities and update the corresponding data values. They should be effectively scheduled to maintain the temporal validity of real-time data objects. This scheduling problem consists of two issues. That is, the determination of the release time and the deadline of each transaction instance and the scheduling of these instances. Various methods have been proposed to solve this problem. Some examples are the More-Less scheme (ML), the deferrable scheduling algorithm with fixed priority (DS-FP), and HSEDF[7–9]. These methods aim to reduce the update workload while providing a complete guarantee on temporal validity, i.e., guaranteeing that the data objects are valid all the time. The update workload reduction allows a system to consume less energy. In addition, it leaves more processor resources to other types of transactions, such as user transactions and triggered transactions.For many systems, providing completely guaranteed temporal validity for real-time data objects could be difficult. At first, the user transactions in the system may have strict timeliness requirements. They compete with the sensor transactions for the same set of resources for execution. To guarantee temporal validity, more resources should be given to sensor transactions. This could lead to high deadline miss ratio of user transactions. Secondly, the system workload can be highly dynamic. The computation time of a transaction in the worst case can be much larger than that in the normal case. The arrivals of transaction instances may be aperiodical and unpredictable. As a result, data validity violations may occur during system overloads. To tackle these problems, several quality of service- (QoS-) based methods have been proposed to schedule sensor transactions and user transactions to maintain the quality of real-time data objects and the quality of transactions [10–22].Current methods for sensor transaction scheduling are mainly restricted to uniprocessor systems. In this paper, we study the problem of data quality-based scheduling of sensor transactions on multiprocessor platforms. We consider the partitioned scheduling approach. On each processor, the earliest deadline first (EDF) scheme is adopted. The major contributions of the paper are as follows:(i)
A definition of data quality is presented to describe the validity degree of real-time data objects. The definition considers the validity of individual data objects and the validity of correlated data object sets.(ii)
Two scheduling methods, named the Partitioned Scheduling for Quality Maximization (P-QM) and the improved P-QM scheduling (IP-QM), are proposed to maximize the data quality.(iii)
Experiments are conducted to evaluate the performance of the proposed methods. The results show that IP-QM outperforms P-QM in terms of the average quality of individual data objects and the average quality of correlated sets.The rest of the paper is organized as follows. Section2 reviews previous studies on temporal validity maintenance. Section 3 describes the system model. The definition of data quality is also presented in this section. The details of the P-QM method and the IP-QM method are presented in Section 4 and Section 5, respectively. Performance studies are given in Section 6. Finally, Section 7 concludes the paper.


## 2. Related Studies

In recent years, there have been a number of studies on maintaining temporal validity of real-time data.ML adopts the periodic task model and the deadline monotonic scheme (DM) [7]. In ML, a sensor transaction’s period is set to be no shorter than its relative deadline. The sum of the period and the deadline is equal to the validity interval. The Half-Half scheme (HH) can be viewed as a special case of ML [23]. DS-FP adopts a sporadic task model [8]. It reduces the processor workload by judiciously deferring the release times of transaction instances. Two extensions of DS-FP were presented in [24] to reduce the online scheduling overhead. The basic idea is to produce a hyperperiod of the DS-FP schedule and repeat the hyperperiod infinitely. A necessary and sufficient schedulability condition for DS-FP in discrete time systems was proposed in [25]. The problem of temporal validity maintenance under dynamic priority scheduling was first studied in [9]. Three algorithms were proposed to derive the periods and deadlines of sensor transactions under the earliest deadline first scheme (EDF). A two-phase algorithm was proposed in [26] to reduce the searching cost of period and deadline assignment under EDF. Li et al. [27] presented two methods to maintain temporal validity for EDF when transmission delays are considered. DS-FP was extended in [25] to be a dynamic priority scheduling algorithm by applying EDF to schedule update instances. The problem of scheduling tasks with both maximum distance constraints (i.e., temporal validity constraints) and minimum distance constraints was investigated in [28]. Jha et al. [29] investigated how to maintain the mutual temporal consistency of real-time data objects. Han et al. studied the problem of maintaining temporal validity in the presence of mode changes [30]. Two algorithms were presented to search for proper mode switch points. These studies are all limited to uniprocessor systems.In [31], Li et al. proposed several algorithms to partition a set of sensor transactions on multiprocessors under EDF and DM. The resource augmentation bounds of these algorithms were also derived. The global EDF algorithm and the half-half principle were applied in [32] to satisfy the data validity constraints. The energy-aware real-time data processing problem on multicore platforms was studied in [33]. Efficient techniques were proposed to maintain temporal validity while reducing energy cost.The studies described above focus on providing a complete guarantee on temporal validity. The co-scheduling problem of periodic application transactions and update transactions was investigated in [10–12]. The aim is to meet the deadlines of all the application transactions while maximizing the quality of data objects. The algorithms based on fixed priority scheduling scheme, EDF and DS-LALF, were presented, respectively. In [13], a set of extensions of ML was proposed to achieve the trade-off between QoS of temporal validity and the number of supported transactions. Labrinidis and Roussopoulos studied the problem of maintaining the freshness of views on a web server [14]. A quality-aware update scheduling algorithm was proposed based on the popularity of views. In [15], a QoS management architecture was proposed to support the desired QoS by applying feedback control, admission control, and flexible freshness management. On-demand schemes were proposed in [16] to skip the updates with similar data object values. Amirijoo et al. employed the notion of imprecise computation for QoS specification and management [17]. Differentiated data service approaches for transaction classes with diverse importance and QoS requirements were proposed in [18]. An effective approach was presented in [19] to decrease both the deadline miss ratio and power consumption by real-time query aggregation and data freshness adaptation. All the above QoS-based methods are designed for uniprocessor systems.In [20], a scheduling framework was presented to assign update jobs to multiple tracks and schedule them on each track, with the objective of minimizing the total staleness of data objects in a streaming warehouse. A track here represents a fraction of the computing resources. Bateni et al. proposed an update scheduling algorithm upon multiprocessors that has bounded stretch and weighted staleness under the quasiperiodic model [21]. In [22], Kang and Chung proposed a multiple inputs/multiple outputs (MIMO) feedback control method to support the timeliness of data-intensive tasks running on multicore-based embedded platforms. Although these studies have also studied the data quality maintenance upon multiprocessors, their definitions of data quality are different from ours. In [20, 21], the data quality is defined in terms of the data staleness. A data value will become stale after its generation. The staleness increases linearly with the passage of time until a new value is installed. In [22], the data quality is defined as the ratio of the number of fresh data objects to the total number of data objects. In our work, however, a data value remains valid during its validity interval. The data quality is then defined based on the validity of individual data objects and the validity of correlated data object sets.


## 3. System Model

LetX=Xii=1n denote a set of real-time data objects and Γ=τii=1n a set of sensor transactions. The data object Xi1≤i≤n is associated with a validity interval Vi. It is value is updated by transaction τi1≤i≤n. τi consists of a sequence of instances (update jobs), in which each samples a value of Xi and installs it. The jth instance of τi is denoted as τi,j. We assume that the jitter between the sampling time and the release time of an instance is zero. git is the probability density function that describes the distribution of the actual computation times of τi’s instances. Transactions in Γ are indexed according to nondecreasing order of their validity intervals, i.e., Vi≤Vi+1 for all i, 1≤i<n.The transaction setΓ is scheduled upon a multiprocessor platform Π=πii=1m. In general, there are three approaches to schedule Γ: partitioned approach, global approach, and hybrid approach [34]. In the partitioned approach, each transaction is assigned to a processor and is always executed on it. In the global approach, an instance that has been preempted on one processor can resume its execution on a different processor. The hybrid approach is the combination of partitioned and global approach. It can be further classified into semipartitioned approach and cluster-based approach. In this paper, the partitioned approach is adopted. On each processor, the EDF scheme is used to schedule the transaction instances.Definition 1.
Xi is temporally valid at time t if, for its update job finished latest before t, the sampling time of this job tr plus Vi is not less than t, i.e., tr+Vi≥t[7].
According to Definition1, if Xi’s current value is sampled at tc, it should be updated before tc+Vi. Otherwise, it will become invalid. However, when the actual computation time of the corresponding update job is large, the update may not be finished before tc+Vi due to the lack of processor resources. Consider a time period 0,T. Let vit denote the valid state of Xi at time t0≤t≤T. vit is 1 if Xi is valid at t and is 0 otherwise. The quality of Xi, qXi, is defined as follows:(1)qXi=1T∫0Tvitdt.
A correlated data object set is a set of real-time data objects whose values are used together to compute the corresponding derived data or to make decisions. It is often required that a certain percentage of the data objects in the correlated set are valid to produce the result with sufficient accuracy. LetY=YkYk⊆Xk=1nc denote the correlated sets in the system. For each Yk1≤i≤nc, let NthYk denote the valid threshold of Yk. If the number of data objects in Yk that are valid at time t is no less than NthYk, then Yk is considered to be valid at t. NthYk is set by users based on application requirements. The quality of Yk, qYk, is defined as follows:(2)qYk=1T∫0TI∑Xi∈Ykvit≥NthYkdt.
The overall data quality of the system,qX, is defined as follows:(3)qX=∑Xi∈XqXi+∑Yk∈YqYk.
Sensor transactions should be effectively scheduled onΠ to maximize qX. This scheduling problem consists of two subproblems. The first is to assign the sensor transactions to processors in a data quality-aware manner. Notice that, different from the traditional real-time tasks, the periods and deadlines of sensor transactions are unknown. They must also be derived during the assignment. The second is to determine which instances can be executed in the system and how to execute them. Table 1 summarizes the major symbols that are used in the paper.Table 1
Definition of symbols.
SymbolDefinitionXiTheith real-time data objectViThe validity interval ofXiπiTheith processorτiThe sensor transaction used to updateXiτi,jThejth instance of τiPiThe period ofτiDiThe deadline ofτiCipThe preallocated computation time ofτiYkThekth correlated data object setqXiThe quality ofXiqYkThe quality ofYkqXThe overall data quality of the systemλiThe density ofτiΔiThe cumulative density ofτiλmaxThe maximum density amongλ1, λ2, …, λn


## 4. The P-QM Method

In this section, we present the P-QM method. Instead of maximizingqX directly, P-QM tries to maximize an approximated overall data quality. Let Cp=Cipi=1n denote the preallocated computation times of transactions in Γ. The actual computation time of instance τi,j is denoted as ci,j. The quality of Xi with respect to Cip, qXiCip, is defined as the probability that ci,j is no larger than Cip, i.e., Prci,j≤Cip. For a correlated set Yk, let Cpk denote the preallocated computation times of the corresponding transactions. The quality of Yk with respect to Cpk, qYkCpk, is defined as follows:(4)qYkCpk=∑S∈Skv∏Xi∈SPrci,j≤Cip∏Xi∈Yk/S1−Prci,j≤Cip.In equation (4), Skv=SS⊆Yk,S≥NthYk. qYkCpk can be viewed as the probability that the number of data objects in Yk that are valid at a time instant is no less than NthYk under Cpk. The overall data quality of the system with respect to Cp, qXCp, is defined as follows:(5)qXCp=∑Xi∈XqXiCip+∑Yk∈YqYkCpk.P-QM maximizesqXCp by judiciously determining Cp and assigning the transactions to processors. A transaction assignment method under the given Cp is presented at first. Then, based on this method, a greedy heuristic is presented to determine Cp in order to maximize qXCp.


### 4.1. Assigning Transactions to Processors

In P-QM, sensor transactions are assigned to processors in a way that the temporal validity of data objects inX is completely guaranteed under the given Cp. Let Pi and Di denote the period and the deadline of transaction τi, respectively. The assignment problem is described as follows.Given the transaction setΓ with Cp and the multiprocessor platform Π, assign each τi to a processor in Π and derive Pi and Di, such that the following constraints are satisfied:(1)
Validity constraints:∀i,1≤i≤n,Pi+Di≤Vi(2)
Deadline constraints:∀i,1≤i≤n,Cip≤minPi,Di(3)
Feasibility constraints:∀j,1≤j≤m, the transactions assigned to πj with given preallocated computation times and derived deadlines and periods are feasible by using EDF schedulingNotice that if the above constraints are all satisfied, then the temporal validity of data objects is guaranteed. This is because for eachXi, its jth j≥2 value sampled at j−1Pi is updated by instance τi,j which will finish before j−2Pi+Vi. This means a value is certain to be refreshed before its validity interval expires.Next, we present the algorithm used in P-QM to solve the assignment problem. LetΔi and λi denote the cumulative density and the density of τi with respected to Cip, respectively. Δi=∑1≤j<iVj−2CjpCjp/Vj−CjpVi, λi=Cip/Vi. Let λmax=maxλi1≤i≤n, λsum=∑1≤i≤nλi, and Δmax=maxΔi1≤i≤n. The following conditions are checked at first:(6)m≥2Δmax+λsum−λmax1−2λmax,(7)Δmax+λsum≤12.If equation (6) or equation (7) holds, the assignment mode is set to be the restricted mode. In this mode, transaction τi’s deadline is restricted to be no larger than Vi/2. Otherwise, it is set to be the unrestricted mode. In this mode, τi’s deadline can be larger than Vi/2 but should be no larger than Vi. Suppose the first i transactions have been successfully assigned to processors. Let Γk denote the set of transactions that are assigned to processor πk. The utilization of τi is ui=Cip/Pi. If Γk=0, the deadline of τi on πk is set to be Cip. Otherwise, it is computed as follows:(8)Di=maxDjτj∈Γk+Cip1−∑τj∈Γkuj.The period ofτi is set to be Vi−Di. τi is assigned to the first processor πk such that the following conditions are satisfied:(1)
Di≤Vi/2 if the assignment mode is restricted mode, or Di≤Vi−CiP if the assignment mode is unrestricted mode.(2)
∑τj∈Γkuj+ui≤1.The assignment fails if no such processor exists. This process is described in Algorithm1. Notice that both the calculation of τi’s deadline and the check of condition 2 can be carried out in an incremental way. Thus, the time required to assign τi to a processor is Om. The check of equations (6) and (7) takes On time. Therefore, the time complexity of Algorithm 1 is Omn+n. The following theorem shows the correctness of the algorithm.Algorithm 1: Transaction assignment.
Input： Γ, Cp, mOutput： The assigned processor of each transaction1. assignment mode⟵ restricted if equation (6) or (7) holds. Otherwise assignment mode ⟵ unrestricted;2.fori=1tondo3.forj=1tomdo4.Di⟵Cip if Γk=0. Otherwise compute Di using equation (8);5.Pi⟵Vi−Di;6.if condition 1 and condition 2 are satisfied then7.Γk⟵Γk∪τi;8.    break;9.end if10.end for11.ifj=m+1then12.Γ is infeasible on Π under Cp, return failure;13.end if14.end for15. return success;Theorem 1.
If Algorithm1 succeeds, then the temporal validity of data objects in X is completely guaranteed.Proof.
For eachτi∈Γ, when it is assigned to a processor, its deadline Di is set to be no less than Cip and no larger than Vi−Cip due to equation (8) and condition 1 of the algorithm. Its period Pi is set to be Vi−Di. Thus, the validity constraints and the deadline constraints are satisfied. We only need to show the feasibility constraints are also satisfied.
The first transactionτ1 is assigned to processor π1 with deadline C1p and period V1−C1p. Obviously, it is EDF-schedulable. Suppose that the first i−1 transactions have been assigned to processors and the transactions on each processor are EDF-schedulable. Consider that transaction τi is assigned to processor πk. The transaction set on processors except πk are not affected by τi; thus, they are still EDF-schedulable. If τi is the first transaction assigned to πk, then obviously it is EDF-schedulable. Let h∗τi,t denote the approximated demand bound of τi in 0,t. h∗τi,t is Cip+ui⋅t−Di if t≥Di and is 0 otherwise. Notice that Di is larger than the deadlines of transactions that are assigned to πk prior to τi. According to [35], Γk∪τi is EDF-schedulable if ∑τj∈Γkuj+ui≤1 and(9)Di−∑τj∈Γkh∗τj,Di≥Cip.
LetΓk,j denote the transactions in Γk∪τi that are assigned to πk before τj. Based on equation (8), one has(10)∑τj∈Γkh∗τj,Di=∑τj∈ΓkCjp+∑τl∈Γk∪τiClpuj1−∑τs∈Γk,lus−∑τl∈Γk,j∪τjClpuj1−∑τs∈Γk,lus=∑τj∈ΓkCjp1−∑τl∈Γk,jul+Cip1−∑τj∈Γkuj∑τj∈Γkuj=Di−Cip.
Equation (10) means the transaction set on πk is EDF-schedulable after τi is added. By induction, the feasibility constraints are satisfied when all transactions have been assigned to processors.Theorem 2.
Algorithm1 succeeds if equation (6) or equation (7) holds.Proof.
At first, we consider the case in which equation (6) holds and equation (7) does not hold. Suppose in this case, transaction τi fails to be assigned to any processor. Then, on each processor, one or both of the conditions of the algorithm are not satisfied. Let Π1 denote the set of processors on which condition 1 is not satisfied and Π2 denote the set of processors on which condition 1 is satisfied and condition 2 is not satisfied. Π1+Π2=m. The transactions assigned to processors in Π1 and Π2 are denoted as Γ1 and Γ2, respectively. For each πk∈Π1, it must be(11)maxDjτj∈Γk+Cip1−∑τj∈Γkuj>Vi2.
According to Theorem1, equation (11) implies(12)Cip+∑τj∈ΓkCjp+CjpPjVi2−Dj>Vi2.
Notice that, for eachτj∈Γk, Vj/2≤Pj≤Vj−Cjp. Summing over all processors in Π1 and making some transformations, we obtain(13)Π1<2∑τj∈Γ1Cjp/Vi−1/Vi∑τj∈Γ1CjpCjp/Vj−Cjp+∑τj∈Γ1Cjp/Vj1−2Cip/Vi.
For eachπk∈Π2, it must be(14)∑τj∈Γkuj+2CipVi>1.
Summing over all processors inΠ2 and making some transformations, we obtain(15)Π2<∑τj∈Γ22Cjp/Vj1−2Cip/Vi.
If bothΠ1 and Π2 are larger than zero, then based on equations (13) and (15) and the definition of Δmax and λsum, we obtain(16)m<2Δmax+λsum−λj1−2λj.
Since equation (7) does not hold, it must be(17)m<2Δmax+λsum−λmax1−2λmax.
IfΠ2=0, we also obtain equation (17). If Π1=0, then λsum>1/2, otherwise equation (15) does not hold. We then obtain(18)m<2λsum−λmax1−2λmax.
Both equations (17) and (18) contradict the assumption that equation (6) holds.
Then, we consider the case in which equation (7) holds. Suppose that the first i−1 transactions have been successfully assigned to processors. For each πk∈Π, it must be(19)Cip+∑τj∈ΓkCjp+CjpPjVi2−Dj≤2Δmax+2λsumVi2≤Vi2.
Equation (19) means the deadline of τi is not larger than Vi/2; thus, condition 1 of the algorithm holds. Condition 2 of the algorithm also holds since equation (7) holds implies λsum≤1/2. Therefore, each transaction can be assigned to a processor.
Notice that there may exist some transactions inΓ with λi=1/2. Let Γh denote the set of such transactions. If Γh>m, or Γh=m and n≥Γh+1, then Γ is infeasible on Π since a processor can only accommodate just one transaction from Γh. If Γh<m, then Theorem 2 can be applied to Γ/Γh and m−Γh.


### 4.2. Determining the Preallocated Computation Times

The problem of determining the preallocated computation timesCp is formulated as an optimization problem:(20)maxqXCp,subject to(1)
Feasibility constraint: the transactions inΓ can be successfully assigned to processors under Cp by Algorithm 1(2)
Computation time constraint:∀i,1≤i≤n,Cimin≤Cip≤CimaxTheorem 3.
LetXlk denote the lth data object in Yk, Clk,p the preallocated computation time of Xlk. Given two sets of pre-allocated computation times Cp1k and Cp2k of Yk. If for each l, 1≤l≤Yk, Clk,p1≤Clk,p2, then qYkCp1k≤qYkCp2k.Proof.
Letqi,j,1 and qi,j,2 denote the quality of Xlkl=1i with a valid threshold of j under Cp1k and Cp2k, respectively. For each i, 1≤i≤Yk, it must be(1)
For allj, 1≤j≤i, qi,j,1<qi,j−1,1 and qi,j,2<qi,j−1,2(2)
qXikCik,p1≤qXikCik,p2(3)
qi,0,1=qi,0,2=1 and qi,j,1=qi,j,2=0 if i<j
ForX1k, q1,1,1=qX1kC1k,p1 and q1,1,2=qX1kC1k,p2; therefore, q1,1,1≤q1,1,2. Suppose for Xlkl=1i−1, qi−1,j,1≤qi−1,j,2 holds for all j, 1≤j≤i−1. Now, consider Xlkl=1i. For each j,1≤j≤i, let qXjkCjk,p2=qXjkCjk,p1+φj, qi−1,j,2=qi−1,j,1+Δi−1,jand qi−1,j−1,2=qi−1,j−1,1+Δi−1,j−1. qi,j,1 can be calculated as follows:(21)qi,j,1=qi−1,j−1,1⋅qXjkCjk,p+qi−1,j,1⋅1−qXjkCjk,p.
qi,j,2 can also be calculated in the same way. By applying equation (21), we obtain(22)qi,j,2−qi,j,1=qi−1,j−1,1−qi−1,j,1φj+Δi−1,j−1qXjkCjk,p2+Δi−1,j1−qXjkCjk,p2.
In equation (22), qi−1,j−1,1−qi−1,j,1>0 and φj≥0 due to (1) and (2), respectively. Δi−1,j−1 and Δi−1,j are no smaller than 0 due to the assumption on Xlkl=1i−1 and (3). Therefore, qi,j,2≥qi,j,1. By induction, we know that qYk,NthYk,2≥qYk,NthYk,1.
According to Theorem3, qXCp will increase by increasing the preallocated computation times of some transactions. Based on this observation, P-QM adopts a greedy heuristic to determine Cp. For each τi, the heuristic sets the initial value of Cip to be its minimum computation time at the start. It then selects one transaction at a time to increase its preallocated computation time.
LetΔqi denote the increase in the overall data quality due to an increase of current Cip by the step size of δ. Δqi is computed as follows:(23)Δqi=qXiCip+δ−qXiCip+∑Xi∈YkqYkCpk/Cip∪Cip+δ−qYkCpk.
In every step, transactionτi is selected to increase Cip if Δqi=maxΔqjCp/Cjp∪Cjp+δis feasible.
To determine whether increasingCip by δ is feasible, the following condition is checked at first:(24)∑1≤j≤n,j≠iCjpVj−Cjp+Cip+δVi−Cip−δ>m.
If equation (24) holds, then increasing Cip by δ is infeasible. To see why, let us suppose increasing Ckp by δ is feasible; then, for each τjj≠i, there must exist at least one instance of τj finished in any interval with length Vj−Cjp, otherwise the data object Xj will be invalid at some time points. This is also true for τi with Cip+δ. The total time required to execute the instances should not exceed the platform capacity. Thus, it must be(25)mVi−Cip−δ∏1≤l≤n,l≠iVl−Clp≥Cip+δ∏1≤l≤n,l≠iVl−Clp+∑1≤j≤n,j≠iCjpVi−Cip−δ∏1≤l≤n,l≠i,l≠jVl−Clp.
Dividing both sides of the negation of equation (25) by Vi−Cip−δ∏1≤l≤n,l≠iVl−Clp, we obtain equation (24).
Notice that if equation (24) holds, then τi cannot be selected to increase Cip in the future. Equation (24) can be evaluated in constant time since the value of the sum term in it can be obtained in the previous step.
If equation (24) does not hold, the following condition is checked:(26)4δVi+2m−2maxλmax,λi+δVi≤m−4λsum.
If equation (26) holds, then increasing Cip by δ is feasible according to equation (6) and Theorem 2. Equation (26) can be checked in an incremental way; thus, the time required is O1. If equation (26) does not hold, Algorithm 1 is applied. If no transaction can be selected in a step or every transaction’s preallocated computation time has reached its maximum value, the algorithm terminates and returns the current Cp. The selection process is described in Algorithm 2.
More sophisticated optimization algorithms can be used for our optimization problem to obtain better solutions, such as the evolutionary algorithm and particle swarm optimization [36, 37]. However, as the number and the worst case computation times of sensor transactions can be large, these optimization algorithms may coverage slowly. The usage of these algorithms for our optimization problem will be left as our future work. In addition, as will be illustrated in the experiment section, by applying the adaptive instance execution method on the transactions with preallocated computation times obtained from the greedy heuristic, the data quality can be greatly improved.
After determining the preallocated computation times and assigning transactions to processors, the system will execute the transaction instances to update the corresponding real-time data objects. In P-QM, when instanceτi,l arrives, if ci,l is no larger than Cip, then τi,l is admitted, otherwise it is dropped. The admitted instances are scheduled using the EDF scheme.Algorithm 2: Preallocated computation time determination.
Input: Γ, mOutput: The preallocated computation time for each transaction1.Cp⟵Cimini=1n,Γc⟵Γ;2.if Algorithm 1 fails for Γc under Cpthen3.Γ is infeasible on Π, return failure;4.end if5.while true do6.Δqmax⟵0,pos⟵0;7.for each τi∈Γcdo8.if equation (24) holds for Γc under Cp/Cip∪Cip+δ and Δqi>Δqmaxthen9.Γc⟵Γc/τi;10.else if equation (26) holds for Γc under Cp/Cip∪Cip+δ and Δqi>Δqmaxthen11.pos⟵i,Δqmax⟵Δqi;12.else if Algorithm 1 succeeds for Γc under Cp/Cip∪Cip+δthen13.pos⟵i,Δqmax⟵Δqi;14.end if15.end for16.ifpos=0then17.   The assignment is finished, return success;18.else19.Cposp⟵Cposp+δ;20.end if21.ifCip=Cimaxthen22.Γc⟵Γc/τi;23.end if24.end while


## 4.1. Assigning Transactions to Processors

In P-QM, sensor transactions are assigned to processors in a way that the temporal validity of data objects inX is completely guaranteed under the given Cp. Let Pi and Di denote the period and the deadline of transaction τi, respectively. The assignment problem is described as follows.Given the transaction setΓ with Cp and the multiprocessor platform Π, assign each τi to a processor in Π and derive Pi and Di, such that the following constraints are satisfied:(1)
Validity constraints:∀i,1≤i≤n,Pi+Di≤Vi(2)
Deadline constraints:∀i,1≤i≤n,Cip≤minPi,Di(3)
Feasibility constraints:∀j,1≤j≤m, the transactions assigned to πj with given preallocated computation times and derived deadlines and periods are feasible by using EDF schedulingNotice that if the above constraints are all satisfied, then the temporal validity of data objects is guaranteed. This is because for eachXi, its jth j≥2 value sampled at j−1Pi is updated by instance τi,j which will finish before j−2Pi+Vi. This means a value is certain to be refreshed before its validity interval expires.Next, we present the algorithm used in P-QM to solve the assignment problem. LetΔi and λi denote the cumulative density and the density of τi with respected to Cip, respectively. Δi=∑1≤j<iVj−2CjpCjp/Vj−CjpVi, λi=Cip/Vi. Let λmax=maxλi1≤i≤n, λsum=∑1≤i≤nλi, and Δmax=maxΔi1≤i≤n. The following conditions are checked at first:(6)m≥2Δmax+λsum−λmax1−2λmax,(7)Δmax+λsum≤12.If equation (6) or equation (7) holds, the assignment mode is set to be the restricted mode. In this mode, transaction τi’s deadline is restricted to be no larger than Vi/2. Otherwise, it is set to be the unrestricted mode. In this mode, τi’s deadline can be larger than Vi/2 but should be no larger than Vi. Suppose the first i transactions have been successfully assigned to processors. Let Γk denote the set of transactions that are assigned to processor πk. The utilization of τi is ui=Cip/Pi. If Γk=0, the deadline of τi on πk is set to be Cip. Otherwise, it is computed as follows:(8)Di=maxDjτj∈Γk+Cip1−∑τj∈Γkuj.The period ofτi is set to be Vi−Di. τi is assigned to the first processor πk such that the following conditions are satisfied:(1)
Di≤Vi/2 if the assignment mode is restricted mode, or Di≤Vi−CiP if the assignment mode is unrestricted mode.(2)
∑τj∈Γkuj+ui≤1.The assignment fails if no such processor exists. This process is described in Algorithm1. Notice that both the calculation of τi’s deadline and the check of condition 2 can be carried out in an incremental way. Thus, the time required to assign τi to a processor is Om. The check of equations (6) and (7) takes On time. Therefore, the time complexity of Algorithm 1 is Omn+n. The following theorem shows the correctness of the algorithm.Algorithm 1: Transaction assignment.
Input： Γ, Cp, mOutput： The assigned processor of each transaction1. assignment mode⟵ restricted if equation (6) or (7) holds. Otherwise assignment mode ⟵ unrestricted;2.fori=1tondo3.forj=1tomdo4.Di⟵Cip if Γk=0. Otherwise compute Di using equation (8);5.Pi⟵Vi−Di;6.if condition 1 and condition 2 are satisfied then7.Γk⟵Γk∪τi;8.    break;9.end if10.end for11.ifj=m+1then12.Γ is infeasible on Π under Cp, return failure;13.end if14.end for15. return success;Theorem 1.
If Algorithm1 succeeds, then the temporal validity of data objects in X is completely guaranteed.Proof.
For eachτi∈Γ, when it is assigned to a processor, its deadline Di is set to be no less than Cip and no larger than Vi−Cip due to equation (8) and condition 1 of the algorithm. Its period Pi is set to be Vi−Di. Thus, the validity constraints and the deadline constraints are satisfied. We only need to show the feasibility constraints are also satisfied.
The first transactionτ1 is assigned to processor π1 with deadline C1p and period V1−C1p. Obviously, it is EDF-schedulable. Suppose that the first i−1 transactions have been assigned to processors and the transactions on each processor are EDF-schedulable. Consider that transaction τi is assigned to processor πk. The transaction set on processors except πk are not affected by τi; thus, they are still EDF-schedulable. If τi is the first transaction assigned to πk, then obviously it is EDF-schedulable. Let h∗τi,t denote the approximated demand bound of τi in 0,t. h∗τi,t is Cip+ui⋅t−Di if t≥Di and is 0 otherwise. Notice that Di is larger than the deadlines of transactions that are assigned to πk prior to τi. According to [35], Γk∪τi is EDF-schedulable if ∑τj∈Γkuj+ui≤1 and(9)Di−∑τj∈Γkh∗τj,Di≥Cip.
LetΓk,j denote the transactions in Γk∪τi that are assigned to πk before τj. Based on equation (8), one has(10)∑τj∈Γkh∗τj,Di=∑τj∈ΓkCjp+∑τl∈Γk∪τiClpuj1−∑τs∈Γk,lus−∑τl∈Γk,j∪τjClpuj1−∑τs∈Γk,lus=∑τj∈ΓkCjp1−∑τl∈Γk,jul+Cip1−∑τj∈Γkuj∑τj∈Γkuj=Di−Cip.
Equation (10) means the transaction set on πk is EDF-schedulable after τi is added. By induction, the feasibility constraints are satisfied when all transactions have been assigned to processors.Theorem 2.
Algorithm1 succeeds if equation (6) or equation (7) holds.Proof.
At first, we consider the case in which equation (6) holds and equation (7) does not hold. Suppose in this case, transaction τi fails to be assigned to any processor. Then, on each processor, one or both of the conditions of the algorithm are not satisfied. Let Π1 denote the set of processors on which condition 1 is not satisfied and Π2 denote the set of processors on which condition 1 is satisfied and condition 2 is not satisfied. Π1+Π2=m. The transactions assigned to processors in Π1 and Π2 are denoted as Γ1 and Γ2, respectively. For each πk∈Π1, it must be(11)maxDjτj∈Γk+Cip1−∑τj∈Γkuj>Vi2.
According to Theorem1, equation (11) implies(12)Cip+∑τj∈ΓkCjp+CjpPjVi2−Dj>Vi2.
Notice that, for eachτj∈Γk, Vj/2≤Pj≤Vj−Cjp. Summing over all processors in Π1 and making some transformations, we obtain(13)Π1<2∑τj∈Γ1Cjp/Vi−1/Vi∑τj∈Γ1CjpCjp/Vj−Cjp+∑τj∈Γ1Cjp/Vj1−2Cip/Vi.
For eachπk∈Π2, it must be(14)∑τj∈Γkuj+2CipVi>1.
Summing over all processors inΠ2 and making some transformations, we obtain(15)Π2<∑τj∈Γ22Cjp/Vj1−2Cip/Vi.
If bothΠ1 and Π2 are larger than zero, then based on equations (13) and (15) and the definition of Δmax and λsum, we obtain(16)m<2Δmax+λsum−λj1−2λj.
Since equation (7) does not hold, it must be(17)m<2Δmax+λsum−λmax1−2λmax.
IfΠ2=0, we also obtain equation (17). If Π1=0, then λsum>1/2, otherwise equation (15) does not hold. We then obtain(18)m<2λsum−λmax1−2λmax.
Both equations (17) and (18) contradict the assumption that equation (6) holds.
Then, we consider the case in which equation (7) holds. Suppose that the first i−1 transactions have been successfully assigned to processors. For each πk∈Π, it must be(19)Cip+∑τj∈ΓkCjp+CjpPjVi2−Dj≤2Δmax+2λsumVi2≤Vi2.
Equation (19) means the deadline of τi is not larger than Vi/2; thus, condition 1 of the algorithm holds. Condition 2 of the algorithm also holds since equation (7) holds implies λsum≤1/2. Therefore, each transaction can be assigned to a processor.
Notice that there may exist some transactions inΓ with λi=1/2. Let Γh denote the set of such transactions. If Γh>m, or Γh=m and n≥Γh+1, then Γ is infeasible on Π since a processor can only accommodate just one transaction from Γh. If Γh<m, then Theorem 2 can be applied to Γ/Γh and m−Γh.


## 4.2. Determining the Preallocated Computation Times

The problem of determining the preallocated computation timesCp is formulated as an optimization problem:(20)maxqXCp,subject to(1)
Feasibility constraint: the transactions inΓ can be successfully assigned to processors under Cp by Algorithm 1(2)
Computation time constraint:∀i,1≤i≤n,Cimin≤Cip≤CimaxTheorem 3.
LetXlk denote the lth data object in Yk, Clk,p the preallocated computation time of Xlk. Given two sets of pre-allocated computation times Cp1k and Cp2k of Yk. If for each l, 1≤l≤Yk, Clk,p1≤Clk,p2, then qYkCp1k≤qYkCp2k.Proof.
Letqi,j,1 and qi,j,2 denote the quality of Xlkl=1i with a valid threshold of j under Cp1k and Cp2k, respectively. For each i, 1≤i≤Yk, it must be(1)
For allj, 1≤j≤i, qi,j,1<qi,j−1,1 and qi,j,2<qi,j−1,2(2)
qXikCik,p1≤qXikCik,p2(3)
qi,0,1=qi,0,2=1 and qi,j,1=qi,j,2=0 if i<j
ForX1k, q1,1,1=qX1kC1k,p1 and q1,1,2=qX1kC1k,p2; therefore, q1,1,1≤q1,1,2. Suppose for Xlkl=1i−1, qi−1,j,1≤qi−1,j,2 holds for all j, 1≤j≤i−1. Now, consider Xlkl=1i. For each j,1≤j≤i, let qXjkCjk,p2=qXjkCjk,p1+φj, qi−1,j,2=qi−1,j,1+Δi−1,jand qi−1,j−1,2=qi−1,j−1,1+Δi−1,j−1. qi,j,1 can be calculated as follows:(21)qi,j,1=qi−1,j−1,1⋅qXjkCjk,p+qi−1,j,1⋅1−qXjkCjk,p.
qi,j,2 can also be calculated in the same way. By applying equation (21), we obtain(22)qi,j,2−qi,j,1=qi−1,j−1,1−qi−1,j,1φj+Δi−1,j−1qXjkCjk,p2+Δi−1,j1−qXjkCjk,p2.
In equation (22), qi−1,j−1,1−qi−1,j,1>0 and φj≥0 due to (1) and (2), respectively. Δi−1,j−1 and Δi−1,j are no smaller than 0 due to the assumption on Xlkl=1i−1 and (3). Therefore, qi,j,2≥qi,j,1. By induction, we know that qYk,NthYk,2≥qYk,NthYk,1.
According to Theorem3, qXCp will increase by increasing the preallocated computation times of some transactions. Based on this observation, P-QM adopts a greedy heuristic to determine Cp. For each τi, the heuristic sets the initial value of Cip to be its minimum computation time at the start. It then selects one transaction at a time to increase its preallocated computation time.
LetΔqi denote the increase in the overall data quality due to an increase of current Cip by the step size of δ. Δqi is computed as follows:(23)Δqi=qXiCip+δ−qXiCip+∑Xi∈YkqYkCpk/Cip∪Cip+δ−qYkCpk.
In every step, transactionτi is selected to increase Cip if Δqi=maxΔqjCp/Cjp∪Cjp+δis feasible.
To determine whether increasingCip by δ is feasible, the following condition is checked at first:(24)∑1≤j≤n,j≠iCjpVj−Cjp+Cip+δVi−Cip−δ>m.
If equation (24) holds, then increasing Cip by δ is infeasible. To see why, let us suppose increasing Ckp by δ is feasible; then, for each τjj≠i, there must exist at least one instance of τj finished in any interval with length Vj−Cjp, otherwise the data object Xj will be invalid at some time points. This is also true for τi with Cip+δ. The total time required to execute the instances should not exceed the platform capacity. Thus, it must be(25)mVi−Cip−δ∏1≤l≤n,l≠iVl−Clp≥Cip+δ∏1≤l≤n,l≠iVl−Clp+∑1≤j≤n,j≠iCjpVi−Cip−δ∏1≤l≤n,l≠i,l≠jVl−Clp.
Dividing both sides of the negation of equation (25) by Vi−Cip−δ∏1≤l≤n,l≠iVl−Clp, we obtain equation (24).
Notice that if equation (24) holds, then τi cannot be selected to increase Cip in the future. Equation (24) can be evaluated in constant time since the value of the sum term in it can be obtained in the previous step.
If equation (24) does not hold, the following condition is checked:(26)4δVi+2m−2maxλmax,λi+δVi≤m−4λsum.
If equation (26) holds, then increasing Cip by δ is feasible according to equation (6) and Theorem 2. Equation (26) can be checked in an incremental way; thus, the time required is O1. If equation (26) does not hold, Algorithm 1 is applied. If no transaction can be selected in a step or every transaction’s preallocated computation time has reached its maximum value, the algorithm terminates and returns the current Cp. The selection process is described in Algorithm 2.
More sophisticated optimization algorithms can be used for our optimization problem to obtain better solutions, such as the evolutionary algorithm and particle swarm optimization [36, 37]. However, as the number and the worst case computation times of sensor transactions can be large, these optimization algorithms may coverage slowly. The usage of these algorithms for our optimization problem will be left as our future work. In addition, as will be illustrated in the experiment section, by applying the adaptive instance execution method on the transactions with preallocated computation times obtained from the greedy heuristic, the data quality can be greatly improved.
After determining the preallocated computation times and assigning transactions to processors, the system will execute the transaction instances to update the corresponding real-time data objects. In P-QM, when instanceτi,l arrives, if ci,l is no larger than Cip, then τi,l is admitted, otherwise it is dropped. The admitted instances are scheduled using the EDF scheme.Algorithm 2: Preallocated computation time determination.
Input: Γ, mOutput: The preallocated computation time for each transaction1.Cp⟵Cimini=1n,Γc⟵Γ;2.if Algorithm 1 fails for Γc under Cpthen3.Γ is infeasible on Π, return failure;4.end if5.while true do6.Δqmax⟵0,pos⟵0;7.for each τi∈Γcdo8.if equation (24) holds for Γc under Cp/Cip∪Cip+δ and Δqi>Δqmaxthen9.Γc⟵Γc/τi;10.else if equation (26) holds for Γc under Cp/Cip∪Cip+δ and Δqi>Δqmaxthen11.pos⟵i,Δqmax⟵Δqi;12.else if Algorithm 1 succeeds for Γc under Cp/Cip∪Cip+δthen13.pos⟵i,Δqmax⟵Δqi;14.end if15.end for16.ifpos=0then17.   The assignment is finished, return success;18.else19.Cposp⟵Cposp+δ;20.end if21.ifCip=Cimaxthen22.Γc⟵Γc/τi;23.end if24.end while


## 5. The IP-QM Method

IP-QM also uses Algorithms1 and 2 to determine Cip and assign transactions to processors. It further improves the data quality by executing transaction instances adaptively on each processor. Figure 1 shows the adaptive execution of instances on a processor.Figure 1
Adaptive execution of transaction instances on a processor.As shown in Figure1, when instance τi,l arrives at processor πk, the instance dropper determines whether τi,l is admitted or not. If τi,l’s actual computation time ci,l is no larger than Cip, then τi,l is admitted. Otherwise, the following condition is checked:(27)∑τs∈Γkcrs,ri,l+∑τs∈Γk,s≠iEs⋅Ns,ri,l+ci,l≤Di.In equation (27), crs,ri,l is the total remaining computation time of τs’s instances with release times no larger than ri,l and deadlines no larger than di,l. di,l is the (absolute) deadline of τi,l, di,l=l−1Pi+Di. Es is the average computation time of an instance of τs:(28)Es=∫t<Cspt⋅gstdt+Prt≥CspCsp.Ns,ri,l is the number of τs’s instances with release times larger than ri,l and deadlines no larger than di,l:(29)Ns,ri,l=maxdi,l−DsPs−ri,lPs+1,0.τi,l is admitted if equation (27) is satisfied and is dropped otherwise. The remaining computation times of instances are obtained from the scheduler. Es can be precomputed in stage one. Ns,ri,l can be computed in constant time. Thus, the time required to check equation (27) is OΓk. The check is only required when ci,l>Cip.Two queuesQp and Qa are maintained for πk. The instances in each queue are arranged in nondecreasing order of their absolute deadlines. The admitted instance τi,l is put into Qp if ci,l≤Cip. Otherwise, τi,l is spitted into two instances: τi,lp with computation time Cip and τi,la with computation time ci,l−Cip. τi,lp and τi,la are put into Qp and Qa, respectively. Both of them have the deadline Di. τi,la can only be executed after τi,lp finishes. Each time the scheduler selects the instance at the head of Qp for execution. If Qp is empty, the instance at the head of Qa is selected. An instance is aborted if it cannot be finished before its deadline.In addition to admit the arriving instances, the instance dropper is also used to drop some instances that are already in the system. Letci,lut denote the computation time of the finished part of τi,l at time instant t. The following rules are used for dropping:(1)
Whenτi,l arrives, if τi,l−1 is not finished and ci,l−1uri,l+ci,l≤minci,l−1,Cip, then τi,l−1 is dropped. The deadline of τi,l is set to be di,l−1.(2)
Whenτs,j arrives, if τii≠s’s latest two instances τi,l and τi,l−1 are not finished, τi,l−2 has been finished, ds,j≤di,l−1 and ci,l−1urs,j+ci,l≤Cip+maxCsp−cs,j,0, then τi,l−1 is dropped. The deadline of τi,l is set to be di,l−1. If ci,l>Cip, then τi,la is removed from Qa and put into Qp with deadline di,l−1.For rule 2, if there are more than one transaction satisfying the dropping condition, the transaction with the largest skippable computation time, i.e.,ci,l−1−ci,l−1urs,j, is selected for dropping. If Csp>cs,j, τs,j will not be considered as an dropping candidate in the future. The time required to evaluate the condition of rule 1 and rule 2 are O1 and OΓk, respectively.The instance dropping does not affect the validity of data objects. Consider rule 1. Ifτi,l−1 is dropped, then τi,l is certain to be finished before di,l−1. The corresponding data object Xi is valid in the time interval t1,di,l+1. t1 is the finish time of τi,l. If τi,l−1 is not dropped and finished before di,l−1, then Xi is valid in t2,di,l+1. t2 is the minimum of the finish time of τi,l−1 and τi,l. Otherwise, Xi is valid in t3,di,l+1. t3 is the finish time of τi,l. It can be seen that t2 and t3 are no smaller than t1 since the remaining part of τi,l−1 may be executed and ci,l is no larger than ci,l−1−ci,l−1uri,l. Consider rule 2. Xi is valid from the finish time of τi,l−2 to di,l−1. If τi,l−1 is dropped, then the unused computation time of τs,j, i.e., Csp−cs,j, will be used by τi,l. Thus, τi,l is certain to be finished before di,l−1 and Xi is valid in di,l−1,di,l+1. If τi,l−1 is not dropped, then τi,l−1 and τi,l may not be finished before their deadlines if their actual computation times are larger than Cip; thus, Xi may be invalid in some intervals in di,l−1,di,l+1.


## 6. Experiment Evaluation

This section presents the results obtained from performance studies on the proposed methods.The performance metrics used in the experiments are the average quality of individual data objects (ADQ_IND), the average quality of correlated sets (ADQ_COR), and the average update workload (AUW). The definition of ADQ_IND and ADQ_COR are given by equations (1) and (2). Let W denote the simulation time and Lp the total time that processor πp is busy executing the transaction instances:(30)AUW=∑1≤p≤mLp/Wm.The parameters and default settings used in the experiments are presented in Table2. The validity interval of a data object is uniformly distributed in [2000, 4000]. The computation time of a sensor transaction is generated following the normal distribution with mean computation time ECi and standard deviation DC given in Table 2. ECi itself is uniformly selected in [10, 20]. The number of data objects in a correlated set is uniformly distributed in [2, 8]. These objects are randomly selected from the data object set. The threshold of a correlated set is set to be Nkc⋅Pth, where Pth indicates the percentage of data objects in Yk that are permitted to be invalid at a time point.Table 2
Parameters and settings.
ParametersMeaningValueNcpuNumber of processors2, 4ViValidity interval of a data object (ms)[2000, 4000]ECiMean computation time of a sensor transaction (ms)[10, 20]DCStandard deviation of computation time3NcNumber of correlated sets8NkcNumber of data objects in a correlated set[2, 8]Figure2 shows the average quality of individual data objects when the number of sensor transactions varies from 100 to 200. The number of processors is 2. Pth is set to be 0.4. When the number of transactions is no larger than 120, the ADQ_IND of P-QM and IP-QM are equal to 1. Both methods’ ADQ_IND decrease as the number of transactions increases. However, the ADQ_IND of IP-QM keeps higher than that of P-QM. This is because for an incoming instance with actual computation time larger than the preallocated computation time, IP-QM will accept it for execution if equation (27) is satisfied, while P-QM always drops it. In addition, IP-QM will drop some instances that are already in the system. As discussed in Section 5, this kind of dropping does not affect the validity of data objects. However, it can leave more processor resources to instances with long execution times. Notice that the difference in the data quality between the two methods increases as the number of transactions increases. When the number reaches 200, the difference goes to about 0.37.Figure 2
Average quality of individual data objects comparison (2 processors).Figure3 shows the average quality of correlated sets. It can be seen that the ADQ_COR of IP-QM is constantly higher than that of P-QM. For example, when the number of transactions is 180, the ADQ_COR of IP-QM is about 0.98, while the ADQ_COR of P-QM is about 0.87. Both methods’ ADQ_COR decrease with the increase in the number of transactions. However, IP-QM’s ADQ_COR drops much slower than P-QM. One observation from Figures 2 and 3 is that the ADQ_COR is higher than the ADQ_IND under both methods. The reason is that the threshold of a correlated set is not large, which leads to a high probability that the correlated set is valid at a time point while the individual data objects in it are not. In addition, since the data objects in a correlated set are selected randomly from the whole data object set, the average valid ratio of them is very close to the average valid ratio of all data objects.Figure 3
Average quality of correlated sets comparison (2 processors).Figure4 shows the average update workload. It can be seen that when the number of sensor transactions is larger than 120, the AUW of IP-QM is higher than that of P-QM. In addition, the AUW of IP-QM always goes up when the number of transactions increases, while the AUW of P-QM goes up before the number reaches 140 and drops slowly after that. This is because in P-QM, when there are a large number of transactions in the system, to accommodate them, the preallocated computation times of them are decreased. This leads to more rejected instances which cancel out the increase in the system workload. In IP-QM, however, many of the instances rejected by P-QM can be accepted and finished due to the admission and dropping rules. These extra instances contribute to the higher average quality of individual data objects and correlated sets.Figure 4
Average update workload comparison (2 processors).Figures5 and 6 show the average quality of individual data objects and correlated sets under different setting of Pth, respectively. The number of sensor transactions is fixed at 200. It can be seen that the ADQ_IND and the ADQ_COR of IP-QM are higher than that of P-QM. For example, when Pth is 0.3, the ADQ_IND and the ADQ_COR of IP-QM are about 0.87 and 0.92, while the ADQ_IND and the ADQ_COR of P-QM are about 0.53 and 0.58. There is not much changes in the ADQ_IND of both methods since the average system workload under different values of Pth are very close to each other when the number of transactions is fixed. Meanwhile, both methods’ ADQ_COR increase as the value of Pth increases. This is because a larger Pth means fewer data objects in a correlated set are required to be valid; thus, there are more chances to access a correlated set that is valid under both methods.Figure 5
Average quality of individual data objects comparison (2 processors and 200 transactions).Figure 6
Average quality of correlated sets comparison (2 processors and 200 transactions).Experiments were repeated for systems with 4 processors. Figures7 and 8 show partial results. The number of transactions varies from 220 to 320. Pth is set to be 0.4. It can be seen that IP-QM still outperforms P-QM in terms of ADQ_IND and ADQ_COR. In addition, the performance degradation of both methods becomes much slower when more processor resources are available.Figure 7
Average quality of individual data objects comparison (4 processors).Figure 8
Average quality of correlated sets comparison (4 processors).


## 7. Conclusions

This paper studies the problem of data quality-based scheduling of sensor transactions on multiprocessor platforms. A definition of data quality is given to describe the validity degree of real-time data objects. Two methods, P-QM and IP-QM, are proposed. P-QM maximizes the data quality by judiciously determining the preallocated computation times of sensor transactions and assigning the transactions to processors. IP-QM improves the data quality obtained from P-QM by adaptively executing transaction instances on each processor. Experiment results show that IP-QM outperforms P-QM in terms of the average quality of individual data objects and the average quality of correlated sets. In this work, the partitioned approach is adopted for transaction scheduling. In the future, we will study how to use the global approach and the hybrid approach to schedule the transactions so that the real-time data quality can be effectively maintained.



---

*Source: 8834383-2020-09-21.xml*