徐洪智+李仁发+曾理宁

收稿日期：2013-05-28

基金项目：国家核高基项目（2009ZX01038-001）；国家自然科学基金项目（60873047， 61173036）

作者简介：徐洪智（1974—）， 男， 湖南长沙人， 副教授， 博士研究生， 研究方向：嵌入式系统。

通讯联系人，E-mail：xuhongzhi9@163.com

文章编号：1003-6199（2014）03-0079-05

摘 要：驾驶者通过路边基础设施感知外部环境并根据经验作出反应是汽车信息物理融合系统的一个最基本的特点，研究汽车与路边基础设施信息交互对建设汽车信息物理融合系统具有重要意义。基于汽车与路边基础设施通信的场景，提出一种新的服务消息调度模型，设计了基于优先级的调度算法，采用贪心思想，优先调度效用值大的消息，将效用值小的消息进行插空调度，最后通过实验证明了本文算法的有效性。

关键词：汽车物理信息融合系统；服务调度；优先级；贪心算法

中图分类号：TP393 文献标识码：A

An Algorithm of Service Scheduling Based on Automotive CPS

XU Hong-zhi1，2， LI Ren-fa2， ZENG Li-ning2

（1.College of Software and Service Outsourcing， Jishou University， Zhangjiajie，Hunan 427000， China；

2.College of Information Science and Engineering， Hunan University， Changsha，Hunan 410082，China）

Abstract：One of the basic characteristics of Automotive Cyber-Physical System（ACPS） is that the driver perceive the external environment through the infrastructure aside the road， and then react based on experience， so it makes sense to research the interaction between the automotive and the infrastructure with the view of ACPS. In this paper， we proposed a new service message schedule model for the scene that automotive and basic infrastructure aside the road were interacting. We designed a Service Scheduling Algorithm Based on Priority（SSABP） with greedy strategy， the algorithm schedule the messages with bigger utility value， and then deal with the messages with lower utility value by fill-in scheduling mechanism. We proved that our algorithm have better performance by simulation.

Key words：automotive Cyber-physical system；service scheduling；priority；greedy algorithm

1 引 言

信息-物理融合系统（Cyber-Physical System，CPS）集成了计算系统与物理系统，并通过嵌入式计算机与网络实现了两者之间的协作与融合，具备“深度嵌入、泛在互联、智能感知和交互协同”的特点[1]，随着嵌入式系统变得越来越普遍，CPS可能将人、汽车、机器人或其他设备相互融合，形成一个统一高效的系统[2]。近年来，人们研究了CPS在电力[3-4]、医疗[5]、交通[6-7]等领域的应用，并已取得了一些极具价值的成果。随着城市智能交通系统的建设和人们对汽车性能要求的提高，汽车CPS（Vehicular Cyber-Physical Systems，VCPS）也受到了很多学者的关注。在汽车CPS中，实时输入传感器收集本车的实时信息或其他车辆的信息，通过一个统一的网络完成信息的交互和计算，并根据反馈的信息来完成对汽车的控制，使得汽车更易于驾驶，响应更快，更安全，更智能。由于汽车及驾驶者要与外部环境（或网络）进行交互，相关服务的调度在汽车CPS中是一个值得关注的问题。目前的研究主要侧重于两个方面，一是侧重于信息的传输，二是侧重于任务的调度。如Wang等人[8]考虑多个路边基础设施配合的情况下，研究了车对车（vehicle-to-vehicle）和车对物（vehicle-to-infrastructure）的信息调度问题；刘建航等人[9]研究了车辆通过路边接入点下载任务的方法；Zhang等人[10]研究了汽车与路边接入点之间的信息上传与下载的相关问题；Hansuk等人[11]提出了一种动态规划模型，考虑消息值随时间的变化，将最相关的信息显示给驾驶员，有助于提高道路安全性能；Li等人[12]提出了汽车CPS中面向人类驾驶的一种服务调度，设计了调度模型并证明了该调度问题是NP完全问题，同时该文还提出了几个启发式调度算法。另外还有一些学者考虑了任务调度过程中的能耗问题，如Abdulla等人[13]提出了路边基础设施和汽车通信过程中的节能调度算法。在未来的汽车CPS中，路边基础设施有必要根据历史数据和当前情况与汽车进行信息交互，所以路边基础设施与每辆汽车的通信内容必定会存在差异，而不同内容的重要程度通常也不同，如：关于行车安全的信息、关于到达目的地的路况信息或是其他广告信息等对于车辆而言具有不同的重要性，即不同的任务可能具有不同的优先级，而现有的研究成果中，基本都没有提及任务的优先级。基于以上分析，本文提出了汽车CPS中基于优先级的服务调度问题，并设计了一种新的启发式算法，通过和已有算法进行对比，验证了算法的性能。

2 问题描述

针对汽车CPS中需要车辆返回处理结果的情形[14]，设在某一段时间内（如：当前时刻到下一辆需要通信的汽车进入通信范围的时刻），路边接入点（以下称发送端）有n个服务消息S={s1， s2， …， sn}，在允许的通信范围内，每个消息可能会按多点传送的方式同时发给多个不同的接收车辆（以下称接收端）R={r1， r2， …， rm}。接收端有三种状态，分别为空闲、忙（正在处理消息）、忙（正在返回处理结果），空闲状态和忙状态分别用0和1表示。当接收端处在空闲状态时可以接受发送端发来的消息，如果接收端处在忙的状态，当新到达消息的优先级小于或等于正在处理的消息时则被拒绝接收，当新到达消息的优先级大于正在处理的消息时则中断正在处理的消息，接受新到消息进行处理。为保证实时性的需要，被中断了的消息以后也不再被处理，因为其处理结果可能对整个系统已没有效用。在发送端的n个消息中，按消息的重要性将消息的优先级设定为P={p0， p1， …pg}个等级，假设等级越低，优先级越高。用V={v1， v2， … ，vn}表示n个消息的效用，因为高优先级消息相对重要，所以具有更高的效用，低优先级消息的效用则低一些。由于发送端发送消息以及接收端处理消息都需要一定的时间，本文定义时隙为消息处理的时间单位，对于某一消息sk，接收端接收、处理、返回处理结果分别需要占用1、xk、yk个时隙。如表1所示，一段时间内共有6个服务消息要发送到7个接收端，本例中设xk=yk=1，k=1，2，…6。

表1 6个服务消息的相关信息

定义1：在第t个时隙中，将服务消息i发给第j个接收端时，如果接收端接受该消息，这时系统产生的效用为U=u（i， j， t）=vi，由于接收端中断正在处理的消息而损失的效用记为UIL=uil（j， t）=u（i-k， j， t-k），表示第t-k个时隙发给接收端j的服务消息到t时还没有完成，其中1≤k≤x+y。

定义2：在第t个时隙中，将服务消息i发给第j个接收端时，如果接收端拒绝该消息，则不产生任何效用。

基于优先级的服务调度问题是：在n个时隙内，发送端发送n个消息到相关的接收端，要求使整个系统的效用最大化。即

Max（∑nt=1∑mi=1∑j∈Ru（i，j，t）-uil（j，t））

3 基于优先级的服务调度算法

3.1 算法思想

定义3：sk的效用密度为VDk=vkl/（1+xk+yk），如表1中s1的效用密度为12/3=4。

基于优先级的服务调度算法（Service Scheduling Algorithm Based on Priority，SSABP）采用贪心算法的思想，在初始时给高效用密度的消息分配高优先级，然后按优先级从高至低安排消息，使高优先级的消息尽量不冲突，对于后面的低优先级消息则进行插空安排，尽量使每次安排的效用最大化。按此方法，表1中的消息调度结果如图1所示，消息的发送次序为s1， s3， s5， s2， s4， s6，6个服务消息调度后所得到的总效用为93。

3.2 算法描述

根据3.1节算法思想，设计基于优先级的服务调度算法SSABP如下：

算法1：SSABP（Service *s， int n，int m）

输入：n个服务消息（每个服务消息具有优先级、效用值和目的接收端属性）和m个接收端

输出：n个服务消息的发送序列和系统将产生的总效用

①SortService（s， n）； //根据优先级对服务消息进行排序

②for i=1to n //n个任务要发送

③ for k=1to n //在n个时隙中找发送服务消息i合适时隙

④ if（slot k is not occupied） //如果时隙k未被占用

⑤ v=Calculate（s[i]，k）；//计算第i个服务消息在时隙k所产生的效用

⑥ if（v>maxV）

⑦ maxV=v； Index=k；

⑧ endif

⑨ endif

⑩ endfor

totalValue+=maxV；

s[i] scheduling to the Index slot； //将s[i]调度到第Index个时隙

endfor

return totalValue； //返回总效用值

算法2：Calculate（Service s， int k）//第i个服务消息在时隙k发送所产生的效用

输入：1个服务消息和时隙k

输出：s调度到第k个时隙产生的效用

①r=GetFirstRecFromList（s）； //取接收s的第一个接收端

②while（r！=NULL）

③ for m=k to k+x+y

④ if（m时隙内r上都没有服务） //和其他服务消息没有冲突

⑤ v+=s.value；

⑥ endif

⑦ endfor

⑧r= GetNextRecFromList（s）

⑨endwhile

3.3 时间复杂度分析

SSABP的时间复杂度为O（n2m）。

证明：算法1第①行排序，时间复杂度为O（nlgn），第②-③行执行n2次，第④执行1次，第⑤行为Calculate函数，因为一个服务消息最多发送到m个接收端，所以该函数的内部最多执行m次。由此，SSABP的时间复杂度为O（n2m）。

4 实验及结果比较

本节通过两组实验来验证算法的性能，将其与按消息序号调度策略SIDS（Service Index-Dominant Strategy）、效用密度大者优先策略UDDS（Utility Density-Dominant Strategy）、效用丢失最小化策略ULDS（Utility Loss-Dominant Strategy）[12]和效用最大化策略UIDS（Utility Income-Dominant Strategy）[12] 四个算法比较，这四个算法的主要思想及时间复杂度如下。

SIDS：按服务消息的序号进行发送，该算法的时间复杂度为O（n）。

UDDS：效用密度大者优先发送，该算法的时间复杂度为O（nlogn）。

ULDS：每次发送的时候考虑效用丢失最小化。某个服务消息到达目的接收端时，接收端正好处在忙的状态时会丢失效用，该算法的时间复杂度为O（n2m）。

UIDS：每次发送的时候考虑效用最大化，该算法的时间复杂度为O（n2m）。

在以下实验中，设n为服务消息的个数，每个服务消息的效用为1-2.5n之间的随机数，每条服务消息以50%的概率随机发给1-m个接收端，以50%的概率随机发给1-m/2个接收端，我们根据消息处理时间的差异将实验分为2组。

第一组：沿用文献[12]的调度模型，每个服务消息的发送（接收）、处理、返回结果所需的时间是相同的，即x=y=z=1。

实验1：服务消息数n分别为10、20、30、40、50、60，接收端m=20，各算法产生的效用如图2所示。从图2可知，SIDS产生的效用最小，因为该算法可能会导致大量服务消息被拒绝或被抢占；SSABP产生的效用最大，因为该算法优先保证效用大的消息不被拒绝或抢占，和UIDS不同的是，UIDS每次发送服务消息时虽然也考虑效用最大化，但同时也可能导致大量效用大的服务消息被拒绝或被抢占，所以UIDS最后得到的总效用小于SSABP。UDDS优先发送效用密度大的，没有考虑该服务消息被拒绝的情况，而ULDS每次考虑效用丢失最小化，会导致效用大的消息推迟调度，最后损失的效用仍较多。

实验2：服务消息数n=60，接收端m分别为10、20、30、40、50、60，各算法产生的效用如图3所示。从图3可知，SSABP算法产生的效用最大，而且当接收端的数目越多时，其优势越明显，其原因是当接收端的数目更多时，其他几个算法因为服务消息被拒绝或被抢占导致的效用损失相对于SSABP更明显。

第二组：假定服务消息的处理时间有差异，而发送（接收）、返回结果所需的时间相同，即每个服务消息的y可能不同，假定y取1-3中的随机数。

实验3：服务消息数n分别为20、30、40、50、60、70，接收端m=20，各算法产生的效用如图4所示。从图4中可知，SSABP产生的效用大于其他几个算法，且随着消息数的增多，SSABP算法更具优势。

实验4：服务消息数n=100，接收端m分别为30、40、50、60、70、80，各算法产生的效用如图5所示。从图5可知，SSABP产生的效用最大，且明显大于其他几个算法。相对于前面几个实验而言，本实验的服务消息数和接收端数都有所增多，SSABP由于高效用的服务消息被拒绝或被抢占的可能性相对于其他几个算法少，所以该算法产生的总效用大于其他算法。

从以上两组实验可知，无论每个服务消息在接收端处理的时间是否存在差异，SSABP都优于另外几个算法，且随着服务消息数目或接收端数目的增加，SSABP具有更好的调度结果。在算法时间复杂度方面，本文算法和文献[12]的两个算法相同，大于另外两个算法，但由于一段时间内n的取值不会很大，故本文算法的复杂度在实际系统中是可被接受的。

5 结束语

汽车CPS不仅要关注本车的情况，如发动机温度、排气管状态等，还要关注与其他汽车的距离，所在位置的路况信息等，甚至每个汽车可以联合起来构建一个更大的CPS网络，它将整合驾驶者要求的行驶方向和以前的交通模型，来让驾驶者做更高级别的决定，如选最快的路线还是最短的路线。在汽车CPS中，路边基础设施有必要根据历史数据和当前情况与汽车进行信息交互，所以路边基础设施与每辆汽车的通信内容可能存在差异。考虑到该应用场景的需求，本文提出了一种基于优先级的服务消息调度模型，并设计了调度算法，通过和已有算法的对比，证明了本文算法的可行性。

参考文献

[1] 李仁发，谢勇，李蕊，李浪.信息-物理融合系统若干关键问题综述[J].计算机研究与发展， 2012，49（6）：1149-1161.

[2] Justin M Bradley， Ella M Atkins. Toward Continuous State-Space Regulation of Coupled Cyber-Physical Systems[J].Proceedings of the IEEE，2012，100（1）：60-74

[3] Sun Yan， McMillin B， Liu Xiaoqing，et al. Verifying Noninterference in a Cyber-Physical System The Advanced Electric Power Grid[C]// Seventh International Conference on Quality Software， Portland OR， IEEE，2007：363-369

[4] Tullio Facchinetti， Marco L Della Vedova. Real-Time Modeling for Direct Load Control in Cyber-Physical Power Systems[J] IEEE Transactions on Industrial Informatics，2011，7（4）：689-698

[5] Insup Lee， Oleg Sokolsky， Sanjian Chen，et al. Challenges and Research Directions in Medical Cyber-Physical Systems[J].Proceedings of the IEEE，2012，100（1）：75-90

[6] Qu Fengzhong， Wang Feiyue，Yang Liuqing. Intelligent Transportation Spaces： Vehicles， Traffic， Communications， and Beyond[J].IEEE Communications Magazine，2010（11）：136-142

[7] Wang Yaodong， Tan Guozhen， Wang Yuan， et al. Perceptual control architecture for cyber-physical systems in traffic incident management[J]. Journal of Systems Architecture，2012，58（10）：398-411

[8] Wang Qing， Fan Pingyi， Letaief K B. On the Joint V2I and V2V Scheduling for Cooperative VANETs With Network Coding[J]. IEEE Transactions on Vehicular Technology，2012，61（1）：62-73

[9] 刘建航，孙江明，毕经平等.基于动态时槽的车联网协助下载方法研究[J].计算机学报，2011，34（8）：1378-1386

[10]Zhang Yang， Zhao Jing， Cao Guohong. On scheduling vehicle-roadside data access[C]// Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks， New York：ACM，2007：9-18

[11]Hansuk Sohn， Lee J D， Bricker D L， et al. A Dynamic Programming Algorithm for Scheduling In-Vehicle Messages[J]. IEEE Transactions on Intelligent Transportation Systems，2008，9（2）：226-234

[12]Li Xu， Qiao Chunming， Yu Xuegang. Toward Effective Service Scheduling for Human Drivers in Vehicular Cyber-Physical Systems[J].IEEE Transactions on Parallel and Distributed Systems，2012，23（9）：1775-1789

[13]Abdulla A Hammad， Terence D Todd， George Karakostas. Downlink Traffic Scheduling in Green Vehicular Roadside Infrastructure[J]. IEEE Transactions on Vehicular Technology，2013，62（3）：1289-1302

[14]DEFLORIO F P. Simulation of requests in demand responsive transport systems[J]Intelligent Transport Systems，2011，5（3）：159-167.

[5] Insup Lee， Oleg Sokolsky， Sanjian Chen，et al. Challenges and Research Directions in Medical Cyber-Physical Systems[J].Proceedings of the IEEE，2012，100（1）：75-90

[6] Qu Fengzhong， Wang Feiyue，Yang Liuqing. Intelligent Transportation Spaces： Vehicles， Traffic， Communications， and Beyond[J].IEEE Communications Magazine，2010（11）：136-142

[7] Wang Yaodong， Tan Guozhen， Wang Yuan， et al. Perceptual control architecture for cyber-physical systems in traffic incident management[J]. Journal of Systems Architecture，2012，58（10）：398-411

[8] Wang Qing， Fan Pingyi， Letaief K B. On the Joint V2I and V2V Scheduling for Cooperative VANETs With Network Coding[J]. IEEE Transactions on Vehicular Technology，2012，61（1）：62-73

[9] 刘建航，孙江明，毕经平等.基于动态时槽的车联网协助下载方法研究[J].计算机学报，2011，34（8）：1378-1386

[10]Zhang Yang， Zhao Jing， Cao Guohong. On scheduling vehicle-roadside data access[C]// Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks， New York：ACM，2007：9-18

[11]Hansuk Sohn， Lee J D， Bricker D L， et al. A Dynamic Programming Algorithm for Scheduling In-Vehicle Messages[J]. IEEE Transactions on Intelligent Transportation Systems，2008，9（2）：226-234

[12]Li Xu， Qiao Chunming， Yu Xuegang. Toward Effective Service Scheduling for Human Drivers in Vehicular Cyber-Physical Systems[J].IEEE Transactions on Parallel and Distributed Systems，2012，23（9）：1775-1789

[13]Abdulla A Hammad， Terence D Todd， George Karakostas. Downlink Traffic Scheduling in Green Vehicular Roadside Infrastructure[J]. IEEE Transactions on Vehicular Technology，2013，62（3）：1289-1302

[14]DEFLORIO F P. Simulation of requests in demand responsive transport systems[J]Intelligent Transport Systems，2011，5（3）：159-167.

[5] Insup Lee， Oleg Sokolsky， Sanjian Chen，et al. Challenges and Research Directions in Medical Cyber-Physical Systems[J].Proceedings of the IEEE，2012，100（1）：75-90

[6] Qu Fengzhong， Wang Feiyue，Yang Liuqing. Intelligent Transportation Spaces： Vehicles， Traffic， Communications， and Beyond[J].IEEE Communications Magazine，2010（11）：136-142

[7] Wang Yaodong， Tan Guozhen， Wang Yuan， et al. Perceptual control architecture for cyber-physical systems in traffic incident management[J]. Journal of Systems Architecture，2012，58（10）：398-411

[8] Wang Qing， Fan Pingyi， Letaief K B. On the Joint V2I and V2V Scheduling for Cooperative VANETs With Network Coding[J]. IEEE Transactions on Vehicular Technology，2012，61（1）：62-73

[9] 刘建航，孙江明，毕经平等.基于动态时槽的车联网协助下载方法研究[J].计算机学报，2011，34（8）：1378-1386

[10]Zhang Yang， Zhao Jing， Cao Guohong. On scheduling vehicle-roadside data access[C]// Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks， New York：ACM，2007：9-18

[11]Hansuk Sohn， Lee J D， Bricker D L， et al. A Dynamic Programming Algorithm for Scheduling In-Vehicle Messages[J]. IEEE Transactions on Intelligent Transportation Systems，2008，9（2）：226-234

[12]Li Xu， Qiao Chunming， Yu Xuegang. Toward Effective Service Scheduling for Human Drivers in Vehicular Cyber-Physical Systems[J].IEEE Transactions on Parallel and Distributed Systems，2012，23（9）：1775-1789

[13]Abdulla A Hammad， Terence D Todd， George Karakostas. Downlink Traffic Scheduling in Green Vehicular Roadside Infrastructure[J]. IEEE Transactions on Vehicular Technology，2013，62（3）：1289-1302

[14]DEFLORIO F P. Simulation of requests in demand responsive transport systems[J]Intelligent Transport Systems，2011，5（3）：159-167.