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

基于排隊(duì)論的CAN總線消息響應(yīng)時(shí)間建模與分析

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

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

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

CAN總線；響應(yīng)時(shí)間；排隊(duì)論；優(yōu)先權(quán)；填充位

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

1 基于排隊(duì)論的CAN總線消息響應(yīng)時(shí)間建模

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

因?yàn)榕抨?duì)論主要研究統(tǒng)計(jì)平衡下的各種性能指標(biāo)的概率性質(zhì)，以下將基于排隊(duì)論模型研究均值條件下的CAN總線消息響應(yīng)時(shí)間．由于消息的傳輸時(shí)間χ和等待時(shí)間Wq是統(tǒng)計(jì)獨(dú)立的，所以消息i響應(yīng)時(shí)間的均值為

2 位填充機(jī)制與傳輸時(shí)間的概率分布

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

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

進(jìn)行位填充之后，一個(gè)消息的總長(zhǎng)度為

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

可知最糟糕情況下一個(gè)消息所用的傳輸時(shí)間是

式中τbit是傳輸一位所需的時(shí)間．

事實(shí)上因?yàn)橄⒌奶畛湮煌鶗?huì)小于最糟糕情況下的位數(shù)，即T值會(huì)小于如式(4)所示的最大值，所以消息的傳輸時(shí)間通常會(huì)小于式(5)的值，且因各個(gè)比特位的排列不同會(huì)導(dǎo)致傳輸時(shí)間呈隨機(jī)變化，因此需要研究傳輸時(shí)間的概率分布函數(shù)，即確定排隊(duì)模型中服務(wù)時(shí)間的分布類(lèi)型．

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 CAN總線消息等待時(shí)間均值的計(jì)算

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

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

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

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

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

因?yàn)槠渌烟幱诎l(fā)送窗口的消息有nr條，所以這些消息的平均傳輸時(shí)間為

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

即

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

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

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

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

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

由式(16)可得

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

4 計(jì)算實(shí)例

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

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

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

表2 主控制器消息(節(jié)點(diǎn)號(hào)1，共12個(gè)消息)Tab.2 Messages of main controller(Node1，12 messages)

表3 電機(jī)ECU消息(節(jié)點(diǎn)號(hào)2，共8個(gè)消息)Tab.3 Messages of motor ECU(Node2，8 messages)

表4 回饋制動(dòng)ECU消息(節(jié)點(diǎn)號(hào)4，共3個(gè)消息)Tab.4 Messages of regenerative braking ECU(Node4，3 messages)

表5 車(chē)載記錄儀消息(節(jié)點(diǎn)號(hào)5，共4個(gè)消息) Tab.5 Messages of recorder (Node5，4 messages)

表6 電池ECU消息(節(jié)點(diǎn)號(hào)3，共10個(gè)消息)Tab.6 Messages of battery ECU(Node3，10 messages)

表7 整車(chē)故障消息(節(jié)點(diǎn)號(hào)6，共3個(gè)消息)Tab.7 Messages of fault(Node 6，3 messages)

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

圖10 基于網(wǎng)絡(luò)負(fù)載率的消息響應(yīng)時(shí)間均值分析Fig.10 Analysis of mean value of response time based on bus load

5 結(jié) 語(yǔ)

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

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

［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］ 唐應(yīng)輝，唐小我. 排隊(duì)論基礎(chǔ)與分析技術(shù)[M]. 北京：科學(xué)出版社，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.