文摘

一个控制任务的性能很大程度取决于其采样频率和sensing-to-actuation延迟。更频繁的取样,短周期,提高了控制性能。同样,更短的延迟也有积极的影响。此外,调度性也是时间的函数和最后期限。通过考虑控制性能和调度性同时,本文定义了一个时间和期限选择几个最系统的问题。我们的问题是找到的最佳时期和特定任务的最后期限最大化总体系统性能。作为我们的解决方案,提出了一种新的启发式算法,找到高质量的次优的解决方案非常低的复杂性,使得该算法几乎适用于大尺寸的任务集。

1。介绍

在cyberphysical系统(CPS)、实时控制系统监视和控制物理系统(即。目标工厂),精确控制性能要求和严格的资源约束。在设计这样一个系统时,可以应用两种不同的方法。首先,传统的方法分离控制设计阶段和实现阶段这样安排抽样率等参数确定在控制设计阶段没有考虑调度问题。第二种方法,称为控调度合作设计,考虑控制性能和任务调度同时为了提高控制性能与有限的资源(1- - - - - -4]。本文主张当设计一个CPS第二种方法。

CPS的实时控制系统的性能不仅取决于其功能的正确性,还安排等参数采样频率。更频繁的传感和驱动,可以获得更精确的控制结果(5]。当然,这种性能增强,增加的成本计算的要求。另一个重要但往往忽略时间属性是传感和驱动之间的延迟,也就是说,输入输出延迟。因为更短的延迟意味着最近的传感数据被用来产生驱动价值,它可以提供更高的控制性能(5]。一个有趣的观察是,任务的时期,也就是说,逆的采样频率,可以延长不伤害控制性能如果我们能减少延迟。维护任务的延时在一定范围内,应该使用所需的最大延迟相对期限的调度性检查。如果调度性检查通过,任务的输入-输出延迟保证小于相对期限。我们要讨论的是一个时间属性抖动,这是不确定采样时间或输入输出延迟的变化,称为采样抖动和输入-输出抖动,分别。一般来说,大的抖动有负面影响控制性能虽然效果不显著的输入输出延迟(6]。关于神经过敏、甚至更短的相对期限也给了更严格的上界的采样抖动和输入-输出抖动,这样可以产生更好的控制结果6]。因此,控制性能可以通过短期的方式或增强较短的期限,时间和期限平衡关系控制性能。

除了控制性能,调度性也严重影响时间和期限的任务。一般来说,更长时间和更长的期限都使系统更可调度的,然而,在成本降低控制性能。换句话说,可以获得更好的控制性能和较低的可调度的机会。此外,类似于控制性能的情况下,时间和最后期限是相互维护调度性交易。因此,重要的是要选择适当的时间和期限,满足控制性能和调度性。这个控调度合作设计问题,制定一个优化问题可以找到最好的可行的时期和特定任务的最后期限,最大化总体系统性能。

在文献中,类似的动机,时间选择问题已被广泛研究[7- - - - - -10)动态和几个调度算法。然而,时间和期限选择的问题本文处理,只有相对较少的关注和收集研究了动态优先级情况下(6,11]。这个动机,针对几个系统,本文提出了一种新颖的任务集合成算法,找到合适的时间和期限最大化总体系统性能,同时保证系统调度性。以来,即使少量的任务,找到最优的解决方案是棘手的,由于巨大的搜索解空间,我们的算法基本上是结构化的基于搜索的启发式算法。将部分所示6,我们的算法具有线性复杂度和找到一个高质量的次优方案即使一项大任务集。

控制性能的定量分析不同时间和最后期限,我们还与汽车控制应用程序进行测量研究。测量控制性能的任务是定义为一个非线性和非凸函数的周期和期限。使用这个函数作为输入到我们的启发式算法。

本文的贡献可以概括如下:(我)我们识别和演示阶段之间的权衡关系并通过实际期限控制性能的实验研究与汽车控制应用程序。(2)利用上面的权衡关系,小说任务合成算法,启发式的发现算法可行(周期和延迟)组合整体控制性能最大化。

我们的论文的其余部分组织如下。第二部分简要解释了相关工作。部分3提出了简短的背景知识和正式描述我们的问题。节4控制性能的权衡关系是正式描述。部分5提出了启发式算法的时间和期限选择的问题。并给出了实验结果6。最后,部分7本文总结道。

2。相关工作

控调度合作设计问题一直得到广泛的研究在文献中。濑户等。7]首先定义时期选择问题假设控制性能可以表示为一个指数衰减函数的采样周期和任务将使用动态优先级的方法。问题是扩展到几个系统濑户et al。8)通过有限的一组可行的时间范围使用分支和的界整数规划方法。在他们的工作,成本函数被认为是任务的单调递增函数。后,比尼人,Di Natale [9]提出了一种快速算法,找到一个理想周期作业,可用于一组任务的实际大小是由之前的方法由于其高计算棘手的要求。最近,Du et al。12)提出了一个使用拉格朗日乘数法的解析解和一个在线算法的超载情况。

上述研究的共同假设关于时间选择问题是控制性能只是受采样率的影响,也就是说,任务期间,控制器。然而,传感和驱动之间的延迟控制性能也有显著的影响。这个动机,比尼人,Cervin10)将每个任务的传感驱动延迟成本函数。在他们的工作,以找到最优周期任务,成本函数近似为线性函数的周期和延迟,延迟也近似假设流体模型调度程序。通过这些近似,他们提出了一个分析的解决方案。

吴et al。6)进一步提高该算法通过EDF调度系统的完全任务时间和期限。结果,问题已成为一段和最后期限选择的问题。他们表明,通过调节相对期限的任务,我们可以无风险的延迟和抖动量每个任务可以体验。在他们的工作,成本函数为非线性函数增加时间和期限的任务。提出了一种两步方法首次修复期和试图最小化期限使用未使用的资源。最近,谭et al。11)提出了一种新的算法,同时调整时间和期限假设EDF调度和LGQ控制器的任务。他们表明,新算法比以前更健壮的和不同的工作负载的方法。

尽管上述研究,然而,相比时间选择问题,这段时间和期限选择问题已获得的关注更少,尽管它有更大的灵活性和稀缺资源提高控制性能。此外,只有EDF调度被认为是在和期限选择问题由于其易于调度性分析,尽管几个调度更常用于实践。相反,本文处理时间和期限选择几个最下调度问题。

3所示。背景和问题描述

3.1。系统模型

本文认为系统独立的周期性实时任务控制分别不同的植物。几个计划的任务调度器和优先级分配根据截止时间单调(DM)秩序。每一个特点是调度参数如下:(我) :最坏执行时间(WCET)。(2) :采样周期。(3) :相对的最后期限。从上面的,是一个已知的参数决定的控制代码,而和操作参数可由系统设计师。关于期限,本文只考虑限制期限在哪里总是小于或等于。在系统执行,生成无限序列的周期性工作与它的周期控制相应的目标工厂(我)传感装置的状态,(2)计算驱动值,(3)驱动。

3.2。控制性能作为时间的函数和期限

当定义一个控制器的性能,可以使用各种指标,如瞬态响应时间和稳态精度6,13]。在某些情况下,即使能源消耗可以控制性能指标(7]。在各种控制性能指标,本文选择了系统误差作为优化目标。系统误差被定义为理想状态与实际状态之间的差异的植物6]。这可以认为是工厂代理控制器后的意图。

更具体地说,让我们把车道保持辅助系统(党的)作为一个例子。在现代汽车中,党的控制车辆的转向角,这样能够遵循其车道的中心。然后,系统误差之间的横向误差可以定义为中心的车辆和车道的中心,见图1。因为这个系统误差也随着时间的变化,我们进一步定义最糟糕的系统误差作为最大的横向误差车辆可以在其驾驶经验。更有兴趣的读者被称为(14]。

在[标记后6),每个任务的控制性能被定义为一个函数的时间和最后期限,这是用 一般来说,被定义为一个非线性成本函数既增加和;如果时间或期限的增加,系统误差总是增加。这种假设背后的直觉将节中讨论4。我们假设都不是连续的,而是离散和,这也是限制内和,分别。

除了每个任务的系统误差,用整个系统错误 在哪里的向量的年代,的向量的年代。符号的简单,是缩短在以下: 在哪里被定义为一个加权和的的年代,是一个用户定义的重量恒定为目的的正常化所需的范围。现在,系统的总体系统误差可以通过给每个任务的时间和期限。

3.3。问题描述

假设上述概念和符号,本节描述了我们的时间和期限的选择问题,可以正式定义如下。

问题描述。对于一个给定的任务集,每个的和给出一个优先级。然后,我们的问题是找到最优和这样,整个系统错误最小化,同时保证每一个吗调度性。

因为它是假定不是连续的,我们不要试图做一个优化问题的解析解。相反,我们制定我们的问题是一个组合优化问题。图2显示一个图形表示的一个例子有10个离散组合。注意,因为我们只考虑限制期限,左边的上三角矩阵是不考虑。

4所示。调度影响控制性能如何

本节涉及的定义背后的基本原理介绍了部分3.2。据称在许多文献的控制性能任务可以被定义为一个函数的时间和期限6,10,11]。如果只有一个的控制系统是由周期性的任务,它应该严格周期性和输入输出延迟是有界的。因此,应该定义为一个函数的控制性能和。然而,当多个实现控制任务和安排在一个共享的处理器,它们的执行也受制于以下调度效果(6]:(我)采样延迟。虽然发布的一份工作是在一个特定的时间点,实际开始工作可以推迟由于执行高优先级的工作。释放时间之间的时间距离和实际开始工作是定义为一个采样延迟。(2)输入输出延迟。之间的时间距离的开始和完成的工作定义为输入输出延迟,这是由工作的实际执行时间是有限的和截止时间高优先级的工作。(3)采样抖动。作为一个任务生成连续的工作,其采样延迟不是恒定的,而是根据不同调度模式每个工作经历。之间的差异最小和最大采样延迟定义为任务的采样抖动。(iv)输入-输出抖动。之间的差异最小和最大输入输出延迟的任务是定义为任务的输入-输出抖动。

通过上述调度的影响,一个控制任务的实际执行不严格的周期性和输入输出延迟显著变化因不同的调度方案。因此,上述调度的影响以及控制时期集体影响控制性能。注意,对于每个任务,唯一可调调度参数和在我们的系统模型。控制时间本身对控制性能有很大的影响,因为它决定了控制频率。除此之外,上述四个调度影响,吴et al。6]分析了最糟糕的情况在以下条件下,每一个任务可调度:(我)采样延迟是有界的,当一开始的工作是延迟尽可能不伤害调度性,以及工作执行高优先级的工作一旦开始没有任何干扰。(2)输入输出延迟是有界的,当一份工作开始后它被释放之前,完成工作的最后期限。(3)采样抖动是有界的。最短采样延迟是0,最大可能的采样延迟。因此,最大和最小采样延迟之间的差异。(iv)输入-输出抖动是有界的,在那里是最好的执行时间,可以简单地认为是0时不可用。最低可能的输入输出延迟和最大可能的输入输出延迟。因此,最大和最小输入-输出延迟之间的差异。

上述分析表明,较短的期限短的采样延迟和较短的输入-输出延迟。甚至可以控制的紧张更短的期限。上述分析的含义是,可以通过缩短获得更好的控制性能以及(6]。从上面观察,我们可以得出结论,控制性能普遍增加或减少。换句话说,系统错误,在这两方面都是一个单调递增函数和。请注意,也反映出恐慌的影响以及延误和采样频率。为了占上述调度效果评估控制性能时,跳吉特巴舞(15),这是一个MATLAB工具箱,可以用来分析延迟和抖动的成本控制性能。此外,视时(16)提供一个仿真环境,促进cosimulation控制器的任务执行和实时调度。

尽管分析和仿真方法非常有用当估计控制性能,本文提出了一种不同的方法,当发现。在部分将进一步解释6.1汽车控制,测量环境开发应用程序。在实践中,和不能被任意数量,但应选用的参数软件平台提供了预定义的候选人。因此,它是实际可行的测量系统错误和每个控制任务的任意组合最糟糕的情况。使用这些离散函数的年代,优化算法部分5可以用来找到最优和,减少。

5。任务集合成算法

为了找到和的最低,最简单的解决方案是探索整个解决方案的每一个空间结合检查调度性和计算整个系统错误。这个穷举搜索方法,然而,过高的复杂性,它不适用于一组任务即使少量的任务像五六任务。穷举搜索算法的计算可行性将进一步讨论部分6.2。相反,本节提出了一种启发式算法,找到一个理想的结果,然而,一个非常低的计算复杂度。即使采取了低复杂度,我们的解决方案可以找到一个高质量的解决方案非常大的任务集,它将显示在部分6.2。

轻松的解释,让我们定义以下函数: 在哪里和向量的选择期和最后期限。是一个向量的每个任务的吗的年代。假设是一个常数向量。在这个函数,根据DM任务排序顺序,最短的任务得到指数1和最长的任务被索引。然后,Audsley后et al。17),准确的执行调度性检查。,下面的递归方程计算最坏响应时间每一个: 在哪里。一直持续到递归方程和聚合值作为最终的。然后,因为我们知道每一个,我们可以简单地检查每一个的调度性进行比较与。如果每个小于为,系统是可调度的,每个的输入输出延迟保证。从调度性检查的结果,返回以下值:(我) :如果系统是可调度的。(2) :如果系统没有可调度。这个调度性检查函数内部使用启发式搜索算法的外层循环检查的可行性选择和。

一开始我们的启发式算法,将最初的解决方案 也就是说,所有的时间和期限都等于零。当然,这个最初的最低可能的解决方案但绝对不是可调度。然后,我们的启发式算法迭代选择(i)任务和(2)方向移动,直到选择任务。我们的经验选择适当的任务是选择最低的任务为了防止某个任务移动过快的更高。选择每个迭代的移动方向,基本的想法是选择的方向降低坡度,以减少由此产生的后移动。

在应用上述基本思想,然而,它可以受到以下最坏的情况。开始一个新的迭代算法选择任务需要移动。通过观察的当前位置相比,正确的方向有较低的斜坡上的方向。自然,我们的算法到正确的方向。然而,想象,即使上方向需要更高的斜率,可以移动后立即可调度的任务集到上面的方向。如果这种情况下发生了多次,将正确的方向太多次,但仍使系统unschedulable。

为了防止这样的场景,我们稍微调整算法调度性以及通过查看系统的斜率在确定移动方向。图3显示了四种情况下,我们的算法时应该考虑任务的当前位置:(我)图3(一个)显示了一个例子两个方向使系统可调度。在这种情况下,它是可取的选择方向的斜率较低。(2)图3 (b)显示两个方向不是可调度的一个例子。然后,我们的选择也与低斜率选择方向。(3)图3 (c)显示情况下斜坡方向是可调度的,但较高的斜坡方向不是可调度。然后,选择较低的斜坡方向,使系统可调度的立即。(iv)图3 (d)显示了一个情况下边坡不是可调度,但较高的斜率是可调度的。在这种情况下,它是不可能确定正确的方向从当前可用的信息。如果我们把上面的方向,该系统将立即可调度。然而,如果我们搬到正确的方向上两次,它也将使系统可调度与更低。一个有趣的观察是,右边的细胞使总是大于0.07。因此,如果有一个更好的解决方案相比细胞中,它必须在右边的位置,也就是说,。我们快速解决,遇到这种情况,每一个细胞都在较低的斜坡方向快速访问比较结果与当采取高坡度方向选择更好的方向。

过程1显示我们的启发式迭代搜索算法的伪代码。后定位每一个在初始解,while循环迭代选择下一个移动和方向考虑4例图3直到系统成为可调度。然后使用打破,while循环终止和输出是最终决定。

6。实验

6.1。控制性能度量研究

在本节内,控制性能测量研究的实验结果。首先,我们解释了如何设计和实现测量环境。然后,实测数据为例提出了控制应用程序。在测量研究中,作为目标控制应用程序中,我们用党的,系统误差被定义为最大横向误差在测量车辆的经验。

图4显示的是测量环境,它包含一个车辆动力学仿真器和两个汽车电子控制单元(ecu)由控制器区域网络连接(可以)总线。在ecu控制应用程序代码被部署在我们专门调实时操作系统(RTOS),这是一个修改版的艾丽卡企业(18]。我们专门调RTOS,最坏的工作发布和延迟模式总是发生在最坏的情况模拟车辆可以体验。在两个ecu,第一个包含党的代码,第二个了巡航控制(CC)的代码。CC算法控制油门和刹车,使车辆在一个预定义的恒速运行。在下面,每个组件更详细地解释:(我)汽车模拟器。对于模拟车辆的实时动态,我们使用一种修改版的开源金属饰环(19模拟器与ubuntu PC - 14.04)。金属饰环有一个精确的车辆动力学引擎和三维可视化功能。(2)ECU(党的)。这ECU包含党的代码接收传感数据(例如,车辆速度、转向角、偏航,和横向距离)从汽车模拟器和发出转向驱动值。英飞凌TC1797单片机(20.)是使用180 MHz CPU、4 MB的闪存,1 MB内存。(3)ECU(巡航控制)。这ECU踩油门和刹车的车辆的启动模拟器将车辆保持在一个恒定的速度。因为我们只对党的性能感兴趣,我们设置这个ECU 100 km / h的速度在整个实验过程中保持与1毫秒。英飞凌TC1796单片机(21与150 MHz处理器),2 MB的闪存,使用512 KB的RAM。(iv)操作和测量控制台。我们做了一个控制面板使用虚拟仪器(22),它可以控制时间和期限ecu的运营商。同时,它可以收集产生的系统误差和可视化使用实时绘制屏幕。(v)CAN总线接口。汽车模拟器之间的实时通信,ecu,操作和测量控制台,使用500 kbps CAN总线。对于电脑,UBS-CAN接口(23使用)。ecu的机载控制器使用。(iv)Human-Vehicle接口。驱动轮、油门和刹车安装手动驾驶。罗技G25模型(24用于界面。

使用测量环境,我们实际测量系统误差的最大值作为不同时期和延迟。时间范围内0女士,120 ms和截止日期范围从0 ms。时间粒度是10毫秒的周期和延迟。图5显示系统错误随着不同时期固定期限20毫秒。如图所示,系统误差单调增加随着时间的增加,这意味着更大的时期对控制性能产生负面影响。女士比较短的时期(20)和最长(120毫秒),系统误差几乎翻了一倍。图6显示了一个不同的配置,其中周期是固定在100 ms和延迟是女士从0变化时期,也就是说,100 ms。通过查看趋势,我们可以得出结论,更大的最后期限也产生负面影响。比较数据5和6测量数据显示,截止日期比时间更重要的对性能的影响。图7显示系统错误的不同时期和期限在3 d图形。地板上的两个轴段和延迟,分别。纵轴是测量的系统误差。从图,清楚地表明,系统误差是单调递增期和延迟和延迟对控制性能的影响有一个更重要的比。

6.2。评估我们的算法

本节评估我们的启发式算法的最优性和计算可行性与合成任务集。当生成任务集,为每一个任务,以下被认为是:(我) 是一个整数值均匀分布的随机选择的女士从1到10 ms的积分。(2) 生成的单调递增的函数和。的最小值和最大值和分别为0和100女士,女士,10 ms的粒度。因为我们只有假设情况下,共有66个值应该为每个生成和一对,随机选择的实际值均匀分布区间从0到1。

图8任务设置一个例子吗与= 3。对于每个人,仅仅是设置为10 ms。在图中,注意细胞不是因为我们只考虑约束产生的最后期限。图中还描述了我们如何启发式算法迭代找到解决方案的一个例子。最初的解决方案是将 每个元组在哪里对。然后,对于每一次迭代,最低的任务选择和任务转到正确的方向解释节吗5。每个圆圈意味着连续的运动搜索迭代次数。此举将继续,直到系统成为可调度。在这个例子中,16个动作后,找到最终的解决方案,也就是说, 在最后的解决方案,。注意,当决定整个系统错误,权重的仅仅是1在整个实验中。

与上述例证任务集生成方法和启发式算法,我们比较以下三种方法:(我)搜索所有可能的时间和期限检查调度性和整体的系统误差。结果是最佳的整个解空间。这种方法用详尽的。(2)只搜索的组合相比,大大减少了解空间详尽的。结果是唯一最优解空间与隐含的最后期限。这种方法用隐式的。(3)搜索的引导下,我们作为部分中解释的启发式算法5。结果可能不是最优的相比详尽的。这种方法用我们的。

图9显示了整个系统误差与上述三种方法。任务的数量是不同的从1到6。对于每一个实验,100任务集生成的结果是100年的平均任务集。如图,详尽的展示了最好的结果即使算法几乎从未结束当任务的数量超过4。5和6的结果是近似与二次方程使用曲线拟合方法。比较隐式的和我们的,我们的赢得每六个实验。尽管不同的是边际小数量的任务时,请注意,不同的是增加任务数量的增加。

表1显示了三种方法所需的计算时间当任务的数量从1到10不等。括号中的数字是估算值,而其他数字实际上是测量。从表中,详尽的需要一年多当任务的数量只有7。即使对于隐式的当任务的数量是10,这是在实践中相对较小,所需的计算时间超过2天。因此,我们可以得出这样的结论:详尽的和隐式的而不能作为实际使用大小任务集我们的发现解决方案甚至更大的任务集。

为了证明我们的启发式算法产生一个高质量的解决方案与其他方法相比,我们也比较我们的用下面的两个其他启发式算法:(我)在每个迭代中,方法选择坡度越高的方向移动。这种方法用更高的。(2)在每个迭代中,方法选择较低的斜坡的方向移动。这种方法用较低的。请注意,我们的是一个扩展的较低的,另外考虑由此产生的调度性以及斜率在决定移动方向。

图10比较的性能我们的与更高的和较低的。结果是100年的平均合成任务设置为每个任务数量从1到6。如图,我们的显示最好的结果相比更高的和较低的。通过比较更高的和较低的,较低的显示一个更好的结果比更高的。首先解释说,采取降低边坡产生一个更好的结果比高斜率。与此同时,我们的进一步提高了性能,考虑到调度性以及斜率在每个迭代。

7所示。结论

通过利用任务时间和期限的权衡关系,本文提出了一种新颖的任务集合成算法最大化总体系统性能。关于控制性能进行测量研究,仿真开发环境,可以很容易地收集汽车控制应用程序的性能变化而应用各种任务时间和期限。从测量数据,证实了权衡关系,我们的问题是正式定义为一段和最后期限选择的问题。我们的问题的输入是每个任务的WCET及其测量控制性能矩阵各个时期和最后期限。调度,DM几个调度。因为它很快变得棘手的找到最优解,甚至相对较少的任务,提出了一种启发式算法的线性复杂度找到高质量的次优的解决方案。我们的启发式算法是基于梯度下降法的初始解的最小周期和每个任务的最后期限。从最初的解决方案,我们的算法迭代增加时间或期限一次,直到任务集可调度。每次迭代的任务及其移动方向选择比较控制性能降低。

在未来的工作中,我们考虑一个新系统配置多个隐期限定期任务共同控制一个工厂。对于这样的系统,一连串的任务实际上从传感控制装置驱动。通过控制每个任务的采样周期,我们需要间接控制采样频率和输入输出延迟工厂实际经验。

相互竞争的利益

作者宣称没有利益冲突有关的出版。