基于排隊論的CAN總線消息響應時間建模與分析

陳 曦，劉魯源，呂偉杰，李 芳

基于排隊論的CAN總線消息響應時間建模與分析

陳 曦1，劉魯源1，呂偉杰1，李 芳2

(1. 天津大學電氣與自動化工程學院，天津 300072；2. 中國科學院電工研究所，北京 100190)

CAN總線消息響應時間是評價CAN總線系統(tǒng)實時性高低的重要性能指標之一，與最糟糕響應時間分析關注極端條件下響應時間計算不同，研究了均值意義下的響應時間建模與分析．在分析CAN總線CSMA/CD協(xié)議的基礎上，建立了消息響應時間的非強占優(yōu)先級的M/G/1排隊模型．針對CAN總線獨有的位填充機制，給出了相應的填充位概率分布函數(shù)，計算了均值意義下的消息響應時間．將其用于電動汽車的CAN總線消息響應時間均值計算，印證了響應時間的均值遠小于最糟糕響應時間．上述結果從排隊論角度對CAN總線系統(tǒng)進行了建模，所提供的模型和方法不僅可用于響應時間的計算和分析，也為CAN總線通信系統(tǒng)的設計與優(yōu)化提供了理論指導．

CAN總線；響應時間；排隊論；優(yōu)先權；填充位

CAN總線消息響應時間(簡稱響應時間)分析是評價CAN總線系統(tǒng)實時性高低的重要性能指標之一．目前普遍采用的是最糟糕響應時間分析方法[1-4]，該方法是利用上限函數(shù)描述CAN總線帶沖突檢測的載波偵聽多路訪問協(xié)議(CSMA/CD)，給出極端條件下即最糟糕條件下的響應時間．然而響應時間的均值是公認的另外一個反映通信系統(tǒng)性能的重要量化指標[5]，在基于CAN總線的網絡控制系統(tǒng)設計與性能評估、可靠性估計等工程中都有應用．筆者根據(jù)CSMA/CD協(xié)議，把CAN總線視為一個排隊系統(tǒng)，建立非強占優(yōu)先級的M/G/1排隊模型，并以此模型為基礎分析計算了消息響應時間的均值．

1 基于排隊論的CAN總線消息響應時間建模

排隊系統(tǒng)由要求得到服務的“顧客”和給予服務的“服務臺”2部分構成．如果把消息占據(jù)總線進行數(shù)據(jù)傳輸視為“服務”，那么因為CAN總線中的節(jié)點在消息傳輸過程中要占據(jù)總線，所以可視其為“顧客”，CAN總線提供消息傳輸?shù)奈锢斫橘|并依據(jù)CSMA/CD協(xié)議進行消息傳輸?shù)闹俨门c管理，所以可視其為“服務臺”．一個排隊系統(tǒng)主要由3部分構成：輸入過程、排隊規(guī)則和服務機構．就由CAN總線構成的排隊系統(tǒng)的輸入過程而言，通常CAN總線系統(tǒng)中消息是持續(xù)不斷發(fā)送的，所以認為顧客總數(shù)是無限的，且設相繼顧客到達的間隔時間服從Poisson分布(M)．CAN總線采用CSMA/CD協(xié)議進行消息仲裁，簡而言之即當?shù)蛢?yōu)先級消息發(fā)送時高優(yōu)先級的消息必須等待低優(yōu)先級消息發(fā)送完畢才能發(fā)送，高優(yōu)先級消息發(fā)送時低優(yōu)先級消息不能發(fā)送[1]，這符合非強占優(yōu)先級的服務規(guī)則．CAN總線中的消息只有在全部比特位發(fā)送完畢之后才可認為傳輸結束，所以可以把消息的傳輸時間視為“服務時間”，因為CAN總線消息的傳輸時間因填充位的不同而呈一定的概率分布[6-7]，所以服務時間是服從一般概率分布G．由于多個CAN節(jié)點接在同一條總線上，任意一個時刻只有一個CAN節(jié)點的消息可以在總線上傳輸，所以只有一個服務臺(1)．由分析可知CAN總線上消息的傳輸符合非強占優(yōu)先級的M/G/1的排隊論模型．

因為排隊論主要研究統(tǒng)計平衡下的各種性能指標的概率性質，以下將基于排隊論模型研究均值條件下的CAN總線消息響應時間．由于消息的傳輸時間χ和等待時間Wq是統(tǒng)計獨立的，所以消息i響應時間的均值為

2 位填充機制與傳輸時間的概率分布

由于把消息傳輸時間視為“服務時間”，所以需要求取服務時間即CAN總線消息傳輸時間概率分布．根據(jù)CAN協(xié)議[6]，CAN總線采用NRZ碼進行編碼，為了實現(xiàn)位同步，采用了位填充機制，即發(fā)送節(jié)點在連續(xù)檢測到5個相同極性位如11111或00000后就加入一個相反極性位．接收節(jié)點在接收消息時會相應地檢測相同極性位數(shù)，并去除填充位．位填充機制使得總線上實際傳輸消息位數(shù)大于原始的位數(shù)．

如果沒有位填充，那么一個CAN消息的總長度可以表示為式中：Li是消息中數(shù)據(jù)的字節(jié)數(shù)，0≤Li≤8；g是消息中控制位的總位數(shù)，標準格式的消息g=34，擴展格式的消息g=54．參與位填充的共有8Li+g位，剩余的包含CRC界定位、應答位、幀結束和幀間隙在內共13位不進行位填充操作．

進行位填充之后，一個消息的總長度為

式中T是填充位的總數(shù)．最糟糕響應時間分析考慮最糟糕情況下即填充位T最多時的消息傳輸時間，此時每隔4位就插入一個相反極性的填充位，因為參與位填充的只有8Li+g位，所以T的最大值為

可知最糟糕情況下一個消息所用的傳輸時間是

式中τbit是傳輸一位所需的時間．

事實上因為消息的填充位往往會小于最糟糕情況下的位數(shù)，即T值會小于如式(4)所示的最大值，所以消息的傳輸時間通常會小于式(5)的值，且因各個比特位的排列不同會導致傳輸時間呈隨機變化，因此需要研究傳輸時間的概率分布函數(shù)，即確定排隊模型中服務時間的分布類型．

構造一個位填充模型P(Si，m)，該模型由隨機生成的5×104個二進制位流序列Si組成，m是位流Si的長度．每個Si滿足：①Si中每一位出現(xiàn)0或1的概率相同；②Si中位與位之間相互獨立[7-8]．

Si的長度m由不同長度的CAN消息中參與位填充機制的位數(shù)而定，根據(jù)式(2)，標準格式消息的m取值范圍Ms是{5，9，13，17，··，25，29，34，42， 50，58，66，74，82，90，98}，擴展格式消息的m取值范圍Ms是{5，9，13，17，··，45，49，54，62，70，78，86，94，102，110，118}，標有下劃線的數(shù)字對應于0～8個數(shù)據(jù)字節(jié)消息幀中參與位填充機制的位數(shù)．

在得到位填充模型P(Si，m)之后，就可以針對不同長度的位流Si統(tǒng)計填充位出現(xiàn)的概率值．圖1～圖9給出了m分別為54、62、70、78、86、94、102、110、118時(即包含0個、1個、2個、3個、4個、5個、6個、7個和8個數(shù)據(jù)字節(jié)的擴展格式消息)填充位的概率分布(圖中位于下方的橫坐標)．由于消息傳輸時間Ci與填充位T滿足

所以可得到消息傳輸時間Ci的概率分布，例如圖2中1個數(shù)據(jù)字節(jié)的擴展格式消息當填充位為0時的概率是0.05，即傳輸時間Ci=(8×1+54+13+0)τbit= 75τbit的概率是0.05．圖1～圖9中上方的橫坐標中列出了傳輸時間．

由圖1～圖9計算得到的不同數(shù)據(jù)字節(jié)擴展格式消息傳輸時間的均值和方差如表1所示．

圖1 0個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.1 Probability distribution of bit-stuffing and transmission time of extended format messages with 0 byte of data

圖2 1個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.2 Probability distribution of bit-stuffing and transmission time of extended format messages with 1 byte of data

圖3 2個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.3 Probability distribution of bit-stuffing and transmission time of extended format messages with 2 bytes of data

圖4 3個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.4 Probability distribution of bit-stuffing and transmission time of extended format messages with 3 bytes of data

圖5 4個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.5 Probability distribution of bit-stuffing and transmission time of extended format messages with 4 bytes of data

圖6 5個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.6 Probability distribution of bit-stuffing and transmission time of extended format messages with 5 bytes of data

圖7 6個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.7 Probability distribution of bit-stuffing and transmission time of extended format messages with 6 bytes of data

圖8 7個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.8 Probability distribution of bit-stuffing and transmission time of extended format messages with 7 bytes of data

表1 不同數(shù)據(jù)字節(jié)擴展格式消息傳輸時間的均值和方差Tab.1 Mean and variance of transmission time of extended format messages with different bytes of data

圖9 8個數(shù)據(jù)字節(jié)擴展格式消息填充位和傳輸時間概率分布Fig.9 Probability distribution of bit-stuffing and transmission time of extended format messages with 8 bytes of data

3 CAN總線消息等待時間均值的計算

設某CAN總線消息系統(tǒng)共由k條消息構成，其優(yōu)先級分別是1，2，··，k，并規(guī)定優(yōu)先級數(shù)越小優(yōu)先級越高，即如果i＜j，那么priority(i)＞priority (j)．消息i(i=1，2，··，k)等待發(fā)送時間由3部分構成，即

(1) 當前正在總線上進行傳輸?shù)南⑺枋Ｓ嗟膫鬏敃r間S0．

(2) 其他所有已處于發(fā)送窗口、優(yōu)先級為r的消息所需傳輸時間的總和．設Sr為第r優(yōu)先級中所有nr個消息的全部傳輸時間(r=1，2，··，i)．

求式(7)的均值，即消息i的平均等待時間為

首先計算E(S0)．由于當前正在總線上進行傳輸?shù)南的優(yōu)先級并不知道，所以用ρr/ρ表示消息r屬于第r優(yōu)先級的概率，消息r的剩余傳輸時間為Rr，同時考慮到總線處于正在傳輸狀態(tài)的概率是ρ，則可得文獻[9]指出在一個有k優(yōu)先級的排隊系統(tǒng)中，優(yōu)先級為r的消息的剩余傳輸時間的均值為

因為其他已處于發(fā)送窗口的消息有nr條，所以這些消息的平均傳輸時間為

式中E(nr)表示平均隊長．由于消息的數(shù)量和消息的傳輸時間是統(tǒng)計獨立的，且對于任意的概率分布，Little公式都成立[10]，即平均隊長為到達速率與等待時間之積，所以式(12)可表示為

即

式(16)是一個遞推公式，考慮到ρ0=0，可得優(yōu)先級為1的消息等待時間為

由式(16)可得優(yōu)先級為2的消息等待時間為

用數(shù)學歸納法[11]證明滿足

將式(19)代入式(15)可得

比較式(16)和式(20)可得

由式(16)可得

即式(19)在i+1時也成立，由此可證消息i的等待時間為

4 計算實例

將第3節(jié)論述方法用于CAN消息響應時間的計算．取電動汽車消息模型[11]如表2～表7所示，比特率為250,kb/s，即τbit=4,μs．利用式(22)計算得到的消息等待時間、響應時間均值如表8所示，由文獻[1-4]計算的最糟糕響應時間也列在表8中．

由表8可知消息的等待時間隨優(yōu)先級的降低而增大，這是符合客觀規(guī)律的，因為消息優(yōu)先級越低，意味著此消息需等待更多、更高優(yōu)先級消息的概率增大，即式(8)等號右側后兩項的數(shù)值在增大，必然會造成等待時間均值的增大．全部消息的響應時間的均值都小于最糟糕響應時間，這與實際相符，因為最糟糕響應時間計算的是極端條件下的響應時間最大值，其值必然要遠遠大于響應時間的均值．此外最糟糕響應時間和響應時間均值之間的差別隨優(yōu)先級的降低而不斷增大，如優(yōu)先級1的消息，其最糟糕響應時間是消息響應時間均值的2.3倍，而優(yōu)先級為40的消息即最低優(yōu)先級消息的最糟糕響應時間是消息響應時間均值的39.7倍．

為了考察消息響應時間均值隨總線負載率變化的規(guī)律，采用了改變CAN總線的比特率τbit來改變總線負載率，觀察消息響應時間變化情況的方法．根據(jù)文獻[12]，τbit依次設定為125,kb/s、250,kb/s、500,kb/s、800,kb/s、1,Mb/s，相應的網絡負載率為71.84%、35.92%、17.96%、11.23%、8.98%，圖10是優(yōu)先級分別為1、20、40的消息響應時間均值變化情況．從圖10中可以看出優(yōu)先級越低，消息響應時間隨總線負載率增長而變化的幅度也越大，如優(yōu)先級為1的消息在負載率為71.84%下的響應時間均值是負載率為8.98%下的10.32倍，而同樣條件下優(yōu)先級為40的消息變化倍數(shù)為21.29．從圖10中也可以看出在負載率不大于35.92%的情況下，消息響應時間的均值與總線負載率近似成線性變化，而當負載率大于35%時，如圖10所示，各優(yōu)先級的消息響應時間陡然增大．

表2 主控制器消息(節(jié)點號1，共12個消息)Tab.2 Messages of main controller(Node1，12 messages)

表3 電機ECU消息(節(jié)點號2，共8個消息)Tab.3 Messages of motor ECU(Node2，8 messages)

表4 回饋制動ECU消息(節(jié)點號4，共3個消息)Tab.4 Messages of regenerative braking ECU(Node4，3 messages)

表5 車載記錄儀消息(節(jié)點號5，共4個消息) Tab.5 Messages of recorder (Node5，4 messages)

表6 電池ECU消息(節(jié)點號3，共10個消息)Tab.6 Messages of battery ECU(Node3，10 messages)

表7 整車故障消息(節(jié)點號6，共3個消息)Tab.7 Messages of fault(Node 6，3 messages)

表8 消息的傳輸時間、等待時間和響應時間的均值及最糟糕響應時間(共40個消息)Tab.8 Mean value and worst case values of transmission time，queuing time and response time(40 messages)

圖10 基于網絡負載率的消息響應時間均值分析Fig.10 Analysis of mean value of response time based on bus load

5 結 語

采用非強占優(yōu)先級的M/G/1排隊論模型研究了CAN總線消息響應時間均值的計算方法．針對CAN總線獨有的填充位機制，采用數(shù)值模擬的方法得到了消息傳輸時間的概率分布．將上述方法用于電動汽車CAN總線消息響應時間均值的計算，分析了響應時間均值與總線負載率之間的關系，結果表明在負載率不大于35.92%的情況下，消息響應時間的均值與總線負載率近似成線性變化．

在利用排隊論模型研究CAN總線響應時間均值的過程中，為簡化計算，把離散概率分布的消息傳輸時間用連續(xù)概率分布來近似描述，這必然會帶來一定的建模誤差，今后擬采用離散時間排隊理論對此問題進行更為深入的研究．

［1］ Davis R I Burns A，Bril R J，et al. Controller area network(CAN)schedulability analysis：Refuted，revisited and revised[J]. Real-Time Systems，2007，35(3)：239-272.

［2］ Tindell K，Burns A. Guaranteeing message latencies on controller area network[C]// Proceedings of 1st International CAN Conference．Wiesbaden，Germany，1994： 2-11.

［3］ Tindell K，Burns A，Wellings A J. An extendible approach for analysing fixed priority hard realtime systems[J]. Journal of Real-Time Systems，1994，6(2)：133-152.

［4］ Burns A. Preemptive priority based scheduling：An appropriate engineering approach[J]. Advances in Real-Time Systems，1994：222-245.

［5］ Giambene G．Queuing Theory and Telecommunications：Networks and Applications[M]. New York，USA：Springer，2005.

［6］ Nolte T，Hansson H，Norstom C. Using bit-stuffing distributions in CAN analysis[C]//IEEE Real-Time Embedded Systems Workshop. London，UK，2001：256-262.

［7］ Nolte T，Hansson H，Norstom C. Probabilistic worstcase response time analysis for the controller area network[C]// Proceedings of Real-Time and Embedded Technology and Applications Symposium. Toronto，Canada，2003：200-207.

［8］ International Organization for Standardization. 11898-1 Road Vehicles-Controller Area Network(CAN)-Part 1：Data Link Layer and Physical Signalling[S]. 2003.

［9］ Cobham A．Priority assignment in waiting line problems[J]. Operation Research，1954，2(1)：70-76.

［10］ 唐應輝，唐小我. 排隊論基礎與分析技術[M]. 北京：科學出版社，2006．

Tang Yinghui，Tang Xiaowo. Introductory and Analysis to the Queueing Theory[M]. Beijing：Science Press，2006(in Chinese).

［11］ Narayan B U. An Introduction to Queueing Theory：Modeling and Analysis in Applications[M]．Boston，USA：Birkhauser，2007.

［12］ CiA Draft Standard 102．CAN Physical Layer for Industrial Applications[EB/OL]. http：//www．can-cia．Org，2008-04-10．

Modeling and Analysis of Response Time of CAN Bus Based on Queueing Theory

CHEN Xi1，LIU Lu-yuan1，Lü Wei-jie1，LI Fang2
(1. School of Electrical Engineering and Automation，Tianjin University，Tianjin 300072，China；2. Institude of Electrical Engineering，Chinese Academy of Sciences，Beijing 100190，China)

Response time of message of CAN is used to evaluate the real-time performance of CAN bus. Compared with the worst case response time analysis which focuses on the response time under extreme condition, analysis and modeling of mean value of response time were presented. According to the CSMA/CD protocol of CAN bus, a nonpreemptive priority M/G/1 model was introduced. Because bit-stuffing was adopted in CAN bus, the probability distribution function was calculated. Accordingly the mean value of response time was educed and the presented method was applied to a message dataset of electric vehicle. Results show that the mean value of response time is far less than the worst case response time. The above conclusions model the CAN bus based on queueing theory, which is available for the calculation of response time and theoretically helps the design and optimization of CAN based network system．

CAN bus；response time；queueing theory；priority；bit-stuffing

TP393.1

A

0493-2137(2012)03-0228-08

2010-10-11；

2011-03-15.

陳 曦（1980— ），男，博士研究生，講師，chenxi@tju.edu.cn.

劉魯源，liuly@tju.edu.cn.