一種基于汽車CPS的服務調度算法

徐洪智+李仁發(fā)+曾理寧

收稿日期：2013-05-28

基金項目：國家核高基項目（2009ZX01038-001）；國家自然科學基金項目（60873047， 61173036）

作者簡介：徐洪智（1974—）， 男， 湖南長沙人， 副教授， 博士研究生， 研究方向：嵌入式系統(tǒng)。

通訊聯(lián)系人，E-mail：xuhongzhi9@163.com

文章編號：1003-6199（2014）03-0079-05

摘 要：駕駛者通過路邊基礎設施感知外部環(huán)境并根據(jù)經(jīng)驗作出反應是汽車信息物理融合系統(tǒng)的一個最基本的特點，研究汽車與路邊基礎設施信息交互對建設汽車信息物理融合系統(tǒng)具有重要意義。基于汽車與路邊基礎設施通信的場景，提出一種新的服務消息調度模型，設計了基于優(yōu)先級的調度算法，采用貪心思想，優(yōu)先調度效用值大的消息，將效用值小的消息進行插空調度，最后通過實驗證明了本文算法的有效性。

關鍵詞：汽車物理信息融合系統(tǒng)；服務調度；優(yōu)先級；貪心算法

中圖分類號：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 引 言

信息-物理融合系統(tǒng)（Cyber-Physical System，CPS）集成了計算系統(tǒng)與物理系統(tǒng)，并通過嵌入式計算機與網(wǎng)絡實現(xiàn)了兩者之間的協(xié)作與融合，具備“深度嵌入、泛在互聯(lián)、智能感知和交互協(xié)同”的特點[1]，隨著嵌入式系統(tǒng)變得越來越普遍，CPS可能將人、汽車、機器人或其他設備相互融合，形成一個統(tǒng)一高效的系統(tǒng)[2]。近年來，人們研究了CPS在電力[3-4]、醫(yī)療[5]、交通[6-7]等領域的應用，并已取得了一些極具價值的成果。隨著城市智能交通系統(tǒng)的建設和人們對汽車性能要求的提高，汽車CPS（Vehicular Cyber-Physical Systems，VCPS）也受到了很多學者的關注。在汽車CPS中，實時輸入傳感器收集本車的實時信息或其他車輛的信息，通過一個統(tǒng)一的網(wǎng)絡完成信息的交互和計算，并根據(jù)反饋的信息來完成對汽車的控制，使得汽車更易于駕駛，響應更快，更安全，更智能。由于汽車及駕駛者要與外部環(huán)境（或網(wǎng)絡）進行交互，相關服務的調度在汽車CPS中是一個值得關注的問題。目前的研究主要側重于兩個方面，一是側重于信息的傳輸，二是側重于任務的調度。如Wang等人[8]考慮多個路邊基礎設施配合的情況下，研究了車對車（vehicle-to-vehicle）和車對物（vehicle-to-infrastructure）的信息調度問題；劉建航等人[9]研究了車輛通過路邊接入點下載任務的方法；Zhang等人[10]研究了汽車與路邊接入點之間的信息上傳與下載的相關問題；Hansuk等人[11]提出了一種動態(tài)規(guī)劃模型，考慮消息值隨時間的變化，將最相關的信息顯示給駕駛員，有助于提高道路安全性能；Li等人[12]提出了汽車CPS中面向人類駕駛的一種服務調度，設計了調度模型并證明了該調度問題是NP完全問題，同時該文還提出了幾個啟發(fā)式調度算法。另外還有一些學者考慮了任務調度過程中的能耗問題，如Abdulla等人[13]提出了路邊基礎設施和汽車通信過程中的節(jié)能調度算法。在未來的汽車CPS中，路邊基礎設施有必要根據(jù)歷史數(shù)據(jù)和當前情況與汽車進行信息交互，所以路邊基礎設施與每輛汽車的通信內容必定會存在差異，而不同內容的重要程度通常也不同，如：關于行車安全的信息、關于到達目的地的路況信息或是其他廣告信息等對于車輛而言具有不同的重要性，即不同的任務可能具有不同的優(yōu)先級，而現(xiàn)有的研究成果中，基本都沒有提及任務的優(yōu)先級。基于以上分析，本文提出了汽車CPS中基于優(yōu)先級的服務調度問題，并設計了一種新的啟發(fā)式算法，通過和已有算法進行對比，驗證了算法的性能。

2 問題描述

針對汽車CPS中需要車輛返回處理結果的情形[14]，設在某一段時間內（如：當前時刻到下一輛需要通信的汽車進入通信范圍的時刻），路邊接入點（以下稱發(fā)送端）有n個服務消息S={s1， s2， …， sn}，在允許的通信范圍內，每個消息可能會按多點傳送的方式同時發(fā)給多個不同的接收車輛（以下稱接收端）R={r1， r2， …， rm}。接收端有三種狀態(tài)，分別為空閑、忙（正在處理消息）、忙（正在返回處理結果），空閑狀態(tài)和忙狀態(tài)分別用0和1表示。當接收端處在空閑狀態(tài)時可以接受發(fā)送端發(fā)來的消息，如果接收端處在忙的狀態(tài)，當新到達消息的優(yōu)先級小于或等于正在處理的消息時則被拒絕接收，當新到達消息的優(yōu)先級大于正在處理的消息時則中斷正在處理的消息，接受新到消息進行處理。為保證實時性的需要，被中斷了的消息以后也不再被處理，因為其處理結果可能對整個系統(tǒng)已沒有效用。在發(fā)送端的n個消息中，按消息的重要性將消息的優(yōu)先級設定為P={p0， p1， …pg}個等級，假設等級越低，優(yōu)先級越高。用V={v1， v2， … ，vn}表示n個消息的效用，因為高優(yōu)先級消息相對重要，所以具有更高的效用，低優(yōu)先級消息的效用則低一些。由于發(fā)送端發(fā)送消息以及接收端處理消息都需要一定的時間，本文定義時隙為消息處理的時間單位，對于某一消息sk，接收端接收、處理、返回處理結果分別需要占用1、xk、yk個時隙。如表1所示，一段時間內共有6個服務消息要發(fā)送到7個接收端，本例中設xk=yk=1，k=1，2，…6。

表1 6個服務消息的相關信息

定義1：在第t個時隙中，將服務消息i發(fā)給第j個接收端時，如果接收端接受該消息，這時系統(tǒng)產(chǎn)生的效用為U=u（i， j， t）=vi，由于接收端中斷正在處理的消息而損失的效用記為UIL=uil（j， t）=u（i-k， j， t-k），表示第t-k個時隙發(fā)給接收端j的服務消息到t時還沒有完成，其中1≤k≤x+y。

定義2：在第t個時隙中，將服務消息i發(fā)給第j個接收端時，如果接收端拒絕該消息，則不產(chǎn)生任何效用。

基于優(yōu)先級的服務調度問題是：在n個時隙內，發(fā)送端發(fā)送n個消息到相關的接收端，要求使整個系統(tǒng)的效用最大化。即

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

3 基于優(yōu)先級的服務調度算法

3.1 算法思想

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

基于優(yōu)先級的服務調度算法（Service Scheduling Algorithm Based on Priority，SSABP）采用貪心算法的思想，在初始時給高效用密度的消息分配高優(yōu)先級，然后按優(yōu)先級從高至低安排消息，使高優(yōu)先級的消息盡量不沖突，對于后面的低優(yōu)先級消息則進行插空安排，盡量使每次安排的效用最大化。按此方法，表1中的消息調度結果如圖1所示，消息的發(fā)送次序為s1， s3， s5， s2， s4， s6，6個服務消息調度后所得到的總效用為93。

3.2 算法描述

根據(jù)3.1節(jié)算法思想，設計基于優(yōu)先級的服務調度算法SSABP如下：

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

輸入：n個服務消息（每個服務消息具有優(yōu)先級、效用值和目的接收端屬性）和m個接收端

輸出：n個服務消息的發(fā)送序列和系統(tǒng)將產(chǎn)生的總效用

①SortService（s， n）； //根據(jù)優(yōu)先級對服務消息進行排序

②for i=1to n //n個任務要發(fā)送

③ for k=1to n //在n個時隙中找發(fā)送服務消息i合適時隙

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

⑤ v=Calculate（s[i]，k）；//計算第i個服務消息在時隙k所產(chǎn)生的效用

⑥ 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發(fā)送所產(chǎn)生的效用

輸入：1個服務消息和時隙k

輸出：s調度到第k個時隙產(chǎn)生的效用

①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），第②-③行執(zhí)行n2次，第④執(zhí)行1次，第⑤行為Calculate函數(shù)，因為一個服務消息最多發(fā)送到m個接收端，所以該函數(shù)的內部最多執(zhí)行m次。由此，SSABP的時間復雜度為O（n2m）。

4 實驗及結果比較

本節(jié)通過兩組實驗來驗證算法的性能，將其與按消息序號調度策略SIDS（Service Index-Dominant Strategy）、效用密度大者優(yōu)先策略UDDS（Utility Density-Dominant Strategy）、效用丟失最小化策略ULDS（Utility Loss-Dominant Strategy）[12]和效用最大化策略UIDS（Utility Income-Dominant Strategy）[12] 四個算法比較，這四個算法的主要思想及時間復雜度如下。

SIDS：按服務消息的序號進行發(fā)送，該算法的時間復雜度為O（n）。

UDDS：效用密度大者優(yōu)先發(fā)送，該算法的時間復雜度為O（nlogn）。

ULDS：每次發(fā)送的時候考慮效用丟失最小化。某個服務消息到達目的接收端時，接收端正好處在忙的狀態(tài)時會丟失效用，該算法的時間復雜度為O（n2m）。

UIDS：每次發(fā)送的時候考慮效用最大化，該算法的時間復雜度為O（n2m）。

在以下實驗中，設n為服務消息的個數(shù)，每個服務消息的效用為1-2.5n之間的隨機數(shù)，每條服務消息以50%的概率隨機發(fā)給1-m個接收端，以50%的概率隨機發(fā)給1-m/2個接收端，我們根據(jù)消息處理時間的差異將實驗分為2組。

第一組：沿用文獻[12]的調度模型，每個服務消息的發(fā)送（接收）、處理、返回結果所需的時間是相同的，即x=y=z=1。

實驗1：服務消息數(shù)n分別為10、20、30、40、50、60，接收端m=20，各算法產(chǎn)生的效用如圖2所示。從圖2可知，SIDS產(chǎn)生的效用最小，因為該算法可能會導致大量服務消息被拒絕或被搶占；SSABP產(chǎn)生的效用最大，因為該算法優(yōu)先保證效用大的消息不被拒絕或搶占，和UIDS不同的是，UIDS每次發(fā)送服務消息時雖然也考慮效用最大化，但同時也可能導致大量效用大的服務消息被拒絕或被搶占，所以UIDS最后得到的總效用小于SSABP。UDDS優(yōu)先發(fā)送效用密度大的，沒有考慮該服務消息被拒絕的情況，而ULDS每次考慮效用丟失最小化，會導致效用大的消息推遲調度，最后損失的效用仍較多。

實驗2：服務消息數(shù)n=60，接收端m分別為10、20、30、40、50、60，各算法產(chǎn)生的效用如圖3所示。從圖3可知，SSABP算法產(chǎn)生的效用最大，而且當接收端的數(shù)目越多時，其優(yōu)勢越明顯，其原因是當接收端的數(shù)目更多時，其他幾個算法因為服務消息被拒絕或被搶占導致的效用損失相對于SSABP更明顯。

第二組：假定服務消息的處理時間有差異，而發(fā)送（接收）、返回結果所需的時間相同，即每個服務消息的y可能不同，假定y取1-3中的隨機數(shù)。

實驗3：服務消息數(shù)n分別為20、30、40、50、60、70，接收端m=20，各算法產(chǎn)生的效用如圖4所示。從圖4中可知，SSABP產(chǎn)生的效用大于其他幾個算法，且隨著消息數(shù)的增多，SSABP算法更具優(yōu)勢。

實驗4：服務消息數(shù)n=100，接收端m分別為30、40、50、60、70、80，各算法產(chǎn)生的效用如圖5所示。從圖5可知，SSABP產(chǎn)生的效用最大，且明顯大于其他幾個算法。相對于前面幾個實驗而言，本實驗的服務消息數(shù)和接收端數(shù)都有所增多，SSABP由于高效用的服務消息被拒絕或被搶占的可能性相對于其他幾個算法少，所以該算法產(chǎn)生的總效用大于其他算法。

從以上兩組實驗可知，無論每個服務消息在接收端處理的時間是否存在差異，SSABP都優(yōu)于另外幾個算法，且隨著服務消息數(shù)目或接收端數(shù)目的增加，SSABP具有更好的調度結果。在算法時間復雜度方面，本文算法和文獻[12]的兩個算法相同，大于另外兩個算法，但由于一段時間內n的取值不會很大，故本文算法的復雜度在實際系統(tǒng)中是可被接受的。

5 結束語

汽車CPS不僅要關注本車的情況，如發(fā)動機溫度、排氣管狀態(tài)等，還要關注與其他汽車的距離，所在位置的路況信息等，甚至每個汽車可以聯(lián)合起來構建一個更大的CPS網(wǎng)絡，它將整合駕駛者要求的行駛方向和以前的交通模型，來讓駕駛者做更高級別的決定，如選最快的路線還是最短的路線。在汽車CPS中，路邊基礎設施有必要根據(jù)歷史數(shù)據(jù)和當前情況與汽車進行信息交互，所以路邊基礎設施與每輛汽車的通信內容可能存在差異。考慮到該應用場景的需求，本文提出了一種基于優(yōu)先級的服務消息調度模型，并設計了調度算法，通過和已有算法的對比，證明了本文算法的可行性。

參考文獻

[1] 李仁發(fā)，謝勇，李蕊，李浪.信息-物理融合系統(tǒng)若干關鍵問題綜述[J].計算機研究與發(fā)展， 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īng)平等.基于動態(tài)時槽的車聯(lián)網(wǎng)協(xié)助下載方法研究[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īng)平等.基于動態(tài)時槽的車聯(lián)網(wǎng)協(xié)助下載方法研究[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īng)平等.基于動態(tài)時槽的車聯(lián)網(wǎng)協(xié)助下載方法研究[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.