（信號與信息處理專業(yè)論文）容錯模式下ttcan總線中系統(tǒng)矩陣的實行時設度算法研究.pdf

b yx i ez h i q i a n g s u p e r v i s o r a s s o c i a t ep r o f e s s o rd i n gs h a n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 9 中取得的 撰寫過的 一同工作 表示誠摯表不城掣 學位論文作者簽名 竹列致 簽字日期 d 7 d6 學位論文版權使用授權書 本學位論文作者和指導教師完全了解東北大學有關保留 使用學位論 文的規(guī)定 即學校有權保留并向國家有關部門或機構送交論文的復印件和 磁盤 允許論文被查閱和借閱 本人同意東北大學可以將學位論文的全部 或部分內(nèi)容編入有關數(shù)據(jù)庫進行檢索 交流 如作者和導師同意網(wǎng)上交流 請在下方簽名 否則視為不同意 學位論文作者簽名 諜怎強 導師簽名 丁扒 簽字日期 c 7 6 簽字日期 啊 東北大學碩士學位論文摘要 容錯模式下t t c a n 總線中系統(tǒng)矩陣的實時調(diào)度算法研究 摘要 傳統(tǒng)c a n 采用的是事件觸發(fā)機制 在總線負荷率上限 實時性和處理多控制器總 線沖突方面略顯不足 而b o s c h 公司推出的t t c a n 協(xié)議采用時間觸發(fā)機制與事件觸 發(fā)機制相結合的方式 基本解決了上述問題 t t c a n 協(xié)議是c a n 協(xié)議的一種擴展 它 提高了總線利用率和消息的實時性 滿足對安全性要求苛刻的實時系統(tǒng)以及總線日益增 長的信息負載的需求 由于t t c a n 是基于時間觸發(fā)的 必然帶來了消息的調(diào)度問題 本論文基于t t c a n 總線研究應用系統(tǒng)的實時調(diào)度問題 首先 學習了t t c a n 協(xié)議及其一些關鍵技術 為 后面問題的提出以及優(yōu)化做了準備 其次根據(jù)消息組構建系統(tǒng)矩陣 采用遺傳算法對其 優(yōu)化 目的是為了最大限度的減少獨占窗的時間 并且采用最大公約數(shù)算法 g r e a t e s t c o m n l o r ld i v i s o r g c d 解決不滿足t t c a n 總線系統(tǒng)矩陣限制因素的消息組 第三 進行 了系統(tǒng)矩陣容錯的研究與設計 本文采用仲裁窗容錯技術方案對系統(tǒng)矩陣進行容錯設 計 并且提出后面優(yōu)先原則 較好的達到了容錯的效果 最后以兩個經(jīng)典消息組s a e 和p s a 作為應用實例 結合了遺傳算法和g c d 算法 對t t c a n 總線中系統(tǒng)矩陣的調(diào) 度算法進行了驗證 實驗結果較好的驗證了該算法在t t c a n 協(xié)議在通信實時性和總線利用率方面的優(yōu) 勢 并且有效的提高了在實際應用中的靈活性 而且 容錯性的設計大大降低了消息傳 輸失敗率 驗證結果為t t c a n 協(xié)議應用在通信可靠性要求較高的硬實時通信環(huán)境中提 供了重要的參考價值 關鍵詞 t t c a n 時間觸發(fā) 實時調(diào)度 遺傳算法 t j 東北大學碩士學位論文 a b s t r a c t r e s e a r c ho nr e a l t i m es c h e d u l i n ga l g o r i t h m f o rt i m e t r i g g e r e dc a n s y s t e m a t i cm a t r i x w i t hf a u l t t o l e r a n tm o d e l a b s t r a c t t h et r a d i t i o n a lc a ni sb a s e do ne v e n t t r i g g e r e dm e c h a n i s m i th a ss o m ed i s a d v a n t a g e s s u c ha sl o a dl i m i t r e a l t i m ep e r f o r m a n c ea n dm u l t i p r o c e s s o rc o n f l i c t i no r d e rt os o l v et h o s e p r o b l e m s b o s c hc o m p a n yi n t r o d u c e st t c a n w h i c hi sac o m b i n a t i o no ft i m e t r i g g e r e d a n de v e n t t r i g g e r e dm e c h a n i s m t t c a ni se x t e n s i o n so fc a n w h i c hi m p r o v e st h er e a l t i m e p e r f o r m a n c eo ft h en e t w o r ka n dm a k e st h ec o m m u n i c a t i o nn o to n l ym e e t i n g t h ed e m a n do f s e c u r i t yc r i t i c a lr e a l t i m es y s t e mb u ta l s oi n c r e a s i n gb u s l o a d s i n c et t c a ni sb a s e do nt i m e t r i g g e r e d i tw i l li n e v i t a b l yl e a dt ot h es c h e d u l i n g p r o b l e m so fm e s s a g e s t h i sp a p e rr e s e a r c h e so nr e a l t i m es c h e d u l i n gp r o b l e m b a s e dt t c a n t h ef i r s ts t e p i ti n t r o d u c e sw h a tt t c a ni sa n ds o m eo fk e yt e c h n o l o g i e sa b o u tt t c a n w h i c hc a n h e l pp e o p l ec l e a r l yu n d e r s t a n dt h ep r o b l e ms t a t e m e n ta n do p t i m i z a t i o n a f t e rt h a t a c c o r d i n gt ot h es e to fm e s s a g e s s y s t e mm a t r i xi sc o n s t i t u t e d g e n e t i ca l g o r i t h mi su s e df o r o p t i m i z a t i o nt h a ta i m st o m i n i m i z et h et i m eo fe x c l u s i v ew i n d o w l a r g e s tc o m m o n d e n o m i n a t o r g c d a l g o r i t h m sa r et a k e na d v a n t a g eo fs o l v i n gt h es c h e d u l i n gp r o b l e mw h i c h m e s s a g es e ti sn o ts a t i s f i e dw i t ht h ec o n s t r a i n t so ft t c a n t h e n i tf o c u s e so ns t u d y i n ga n d d e s i g n i n gt h ef a u l t t o l e r a n tm o d e lo fs y s t e mm a t r i x t h i sp a p e ru s e st h ea r b i t r a t i o nw i n d o w f a u l t t o l e r a n tt e c h n o l o g yt od e s i g ns y s t e mm a t r i x m e a n w h i l e i ta l s ot a k e sa d v a n t a g eo f f o r w a r dl a t t e rp r i o r i t yp r i n c i p l ef o ra r b i t r a t i o nw i n d o wf a u l t t o l e r a n tm o d e l a tl a s t t h ea u t h o r t a k et w oc l a s s i cm e s s a g es e t ss a ea n dp s aa se x a m p l e s c o m b i n eo fg e n e t i ca l g o r i t h ma n d t h eg c d a l g o r i t h mi no r d e rt ov a l i d a t et h es c h e d u l i n ga l g o r i t h mf o rs y s t e mm a t r i x t h ee x p e r i m e n t a lr e s u l t sp r o v et h a tt h ea l g o r i t h mw ep r o p o s e dh a st h ea d v a n t a g eo f r e a l t i m et r a n s m i s s i o no fs i g n a la n db a n d w i d t hu t i l i z a t i o nr a t i o a n da l s oe n h a n c et h e f l e x i b i l i t yo fp r a c t i c a la p p l i c a t i o ne f f e c t i v e l yi nt t c a np r o t o c l i na d d i t i o n f a u l t t o l e r a n t g r e a t l yr e d u c e st h ef a i l u r er a t eo fm e s s a g e st r a n s m i s s i o n f i n a l l y t h es u c c e s s f u le s t a b l i s h m e n t o fm o d e lp r o v i d e sa ni m p o r t a n tr e f e r e n c ev a l u ef o rt t c a np r o t o c o lw h i c hi sa p p l i e di nt h e h a r dr e a l t i m ec o m m u n i c a t i o ne n v i r o n m e n tt h a tr e q u i r i n gh i g h e rc o m m u n i c a t i o nr e l i a b i l i t y k e y w o r d s t t c a n t i m e t r i g g e r e d r e a l t i m es c h e d u l i n g g e n e t i ca l g o r i t h m t i t f 東北大學碩士學位論文 目錄 目錄 獨創(chuàng)性聲明 i 摘要 i i a bs t r a c t i i i 第1 章緒論 1 1 1t t c a n 協(xié)議的產(chǎn)生背景 1 1 1 1c a n 協(xié)議分析 1 1 1 2t t c a n 協(xié)議的應用研究與優(yōu)勢 2 1 2 實時調(diào)度理論在t t c a n 總線中的必要性 3 1 3 論文研究的內(nèi)容及意義 5 1 3 1 論文研究的內(nèi)容 5 1 3 2 論文研究的意義 6 第2 章t t c a n 總線協(xié)議及關鍵技術 9 2 1t t c a n 總線底層協(xié)議 9 2 1 1c a n 總線的拓撲結構 9 2 1 2c a n 總線的分層結構 1 0 2 1 3c a n 總線的報文格式 1 2 2 1 4c a n 總線的非破壞性 逐位仲裁 機制 1 5 2 2t t c a n 總線協(xié)議 1 5 2 2 1t t c a n 總線的時間觸發(fā)機制 1 5 2 2 2t t c a n 總線的時間基準 1 6 2 2 3t t c a n 總線的主節(jié)點 18 2 3 本章小結 19 i v 東北大學碩士學位論文 第3 章容錯模式下t t c a n 總線系統(tǒng)矩陣的調(diào)度分析 3 1t r c a n 總線的系統(tǒng)矩陣 3 1 1t t c a n 總線系統(tǒng)矩陣的結構 3 1 2 系統(tǒng)矩陣的基本周期 3 1 3t t c a n 總線系統(tǒng)矩陣的設計 3 1 4t t c a n 總線利用率 2 5 3 2t t c a n 總線系統(tǒng)矩陣的容錯 2 7 3 2 1 系統(tǒng)容錯的概述 2 7 3 2 2t t c a n 總線協(xié)議的容錯機制 2 7 3 2 3t t c a n 總線系統(tǒng)矩陣的容錯方法 2 8 3 3t t c a n 總線系統(tǒng)矩陣的調(diào)度問題 3 0 3 3 1 消息的分析 一3 0 3 3 2t t c a n 總線系統(tǒng)矩陣的限制因素 3 l 3 3 3t t c a n 總線系統(tǒng)矩陣調(diào)度的可行性分析 3 1 3 3 4 系統(tǒng)矩陣的調(diào)度問題分析 3 2 3 4 本章小結 3 4 第4 章容錯模式下t t c a n 總線系統(tǒng)矩陣的調(diào)度算法研究 3 5 4 1 遺傳算法簡介 3 5 4 2 基于遺傳算法的t t c a n 總線系統(tǒng)矩陣的實時調(diào)度 3 7 4 2 1 時間觸發(fā)消息的系統(tǒng)矩陣構造 3 7 4 2 2 時間觸發(fā)消息的系統(tǒng)矩陣實時調(diào)度 4 0 4 2 3 事件觸發(fā)消息系統(tǒng)矩陣的實時調(diào)度 4 4 4 3t t c a n 總線系統(tǒng)矩陣的容錯理論及改進 4 5 4 1m a i l b o xm e t h o d 4 5 4 3 2a r b i t r a t i o nw i n d o wm e t h o d 及其改進 4 9 4 4 本章小結 5 1 v 東北大學碩士學位論文 目錄 第5 章t t c a n 總線系統(tǒng)矩陣的實時調(diào)度算法的驗證 5 3 5 1 系統(tǒng)矩陣的實時調(diào)度算法驗證 5 3 5 1 1 系統(tǒng)矩陣的構造實驗 5 3 5 1 2 系統(tǒng)矩陣優(yōu)化實驗結果的分析 5 6 5 2 系統(tǒng)矩陣容錯的設計驗證 5 9 5 3 本章小結 6 0 第6 章結論與展望 6 1 6 1 結論 6 l 6 2 展望 6 2 參考文獻 6 3 致謝 6 7 作者攻讀碩士學位期間發(fā)表的論文 6 9 v i 東北大學碩士學位論文第1 章緒論 第1 章緒論 1 1t t c a n 協(xié)議的產(chǎn)生背景 1 1 1c a n 協(xié)議分析 c a n c o n t r o l l e ra r e an e t w o r k 是由德國b o s c h 公司開發(fā)的有效支持分布式實時 控制的串行通信網(wǎng)絡 由于其成本低 可靠性高 抗干擾能力強和實時性強等特點而得 到廣泛的應用 卜2 c a n 總線作為汽車中微控制器 m c u 的通信總線 能夠為車載電子 控制裝置e c u 之間提供交換信息服務 并可以形成汽車電子控制網(wǎng)絡 比如 發(fā)動機 管理系統(tǒng) 變速箱控制器 儀表設備 電子主干系統(tǒng)中均嵌入c a n 控制裝置 作為國 際上應用最廣泛的總線之一 c a n 總線在汽車行業(yè)已經(jīng)成為很多相關的行業(yè)標準或國 際標準 1 9 9 1 年 b o s c h 公司制定并發(fā)布了c a n 技術規(guī)范 v e r s i n n 2 o 1 9 9 3 年 c a n 總線成為了國際標準1 5 0 1 1 5 9 5 高速應用 和1 5 0 1 1 5 1 9 低速應用 在網(wǎng)絡控制系統(tǒng)中 存在兩種不同的消息傳輸機制 3 卅 事件觸發(fā)機制和時間觸發(fā) 機制 c a n 總線的通信方式本質(zhì)上屬于事件觸發(fā)機制 介質(zhì)訪問控制采用帶沖突檢測 的基于優(yōu)先級的非破壞性仲裁機制 c s m a c d 方式 總線沖突時具有最高優(yōu)先權的節(jié)點 贏得仲裁 可以進行數(shù)據(jù)發(fā)送 當通信負載較輕時 可以滿足系統(tǒng)實時性要求 而通信 負載較重時 將不能保證通信的實時性以及確定性 由于普通c a n 總線協(xié)議缺乏決定機制 同步和容錯等特性 其不可避免地存在以 下一些問題 5 j 1 c a n 總線的通信方式本質(zhì)上屬于事件觸發(fā)機制 介質(zhì)訪問控制采用帶沖突檢測 的基于優(yōu)先級的非破壞性仲裁機鉗 c s m a c d 當通信負載較輕時 可以滿足系統(tǒng)實時 性要求 而通信負載較重時 消息間的沖突會引起延遲時間的不確定性 將不能保證通 信的實時性及確定性 2 c a n 協(xié)議采用事件觸發(fā)機制進行通信 只有當總線上的一個模塊有事件發(fā)生時 才會向總線發(fā)送數(shù)據(jù) 這樣如果一個節(jié)點有連續(xù)變化的數(shù)據(jù)需要記錄或顯示時 數(shù)據(jù)就 會有丟失的可能 3 c a n 總線協(xié)議的位速率最高可達1 m b p s 而且此時最大總線長度只能是4 0 m 傳輸時也不夠穩(wěn)定 實際應用中 波特率最高只能用到5 0 0 k b p s 由于允許的頻帶和最 大總線長度的限制 c a n 總線不能滿足快速增長的多對象 高靈敏 高穩(wěn)定及高容錯 1 東北大學碩士學位論文第1 章緒論 性能的要求 因此 對一些實時性要求很高的控制系統(tǒng) c a n 總線并不能滿足其要求 4 c a n 網(wǎng)絡拓撲結構是總線型的 而且各節(jié)點是平等的 沒有主從節(jié)點之分 任 何一個節(jié)點都可以接收或者發(fā)送數(shù)據(jù) 沒有任何的限制 如果一個節(jié)點惡意重復的發(fā)送 數(shù)據(jù)到總線上 可能就會導致其它節(jié)點無法發(fā)送數(shù)據(jù) 對于這種惡意節(jié)點 c a n 協(xié)議 沒有辦法進行解決 5 因為報文的優(yōu)先權是根據(jù)標識符來判別的 而標識符一般是根據(jù)內(nèi)容來制定的 所以當系統(tǒng)擴充時 有可能會牽扯到優(yōu)先權的重新排序問題 這樣就給系統(tǒng)的擴充帶來 了一定的復雜度 在硬實時應用中 可靠性要求極高 確?？深A知的通信以及減少消息 的傳輸延遲是至關重要的 為了達到這一目的 可以將基于事件觸發(fā)的c a n 和時間觸 發(fā)機制相結合 充分發(fā)揮兩種機制的優(yōu)勢 為此 i s 0 118 9 8 4 在c a n 協(xié)議棧的會話層 中提出了一種基于時間觸發(fā)機制t t c a n t t i m e t r i g g e r e dc c o m r o l l e ra a r e an n e t w o r k 協(xié) 議 5 1 b o s c h 公司開發(fā)了t t c a n 總線協(xié)議 t t c a n 協(xié)議在c a n 協(xié)議事件觸發(fā)基礎上引 入了時間觸發(fā)協(xié)議機制 采用了時間觸發(fā)和時分多路 t i m ed i v i s i o nm u l t i p l ea c c e s s t d m a 方式進行通信 其消息的傳輸可預測 可管理 并且總線利用率高 通信延時低 提高了總線的實時性能 并使得總線利用率大大提高 目前 t t c a n 協(xié)議主要的研究 工作是t t c a n 協(xié)議調(diào)度算法以及其控制芯片的研究 1 1 2t t c a n 協(xié)議的應用研究與優(yōu)勢 自從i s o 將t t c a n 協(xié)議作為國際標準后 全球領先的幾家制造商就開始采用 t t c a n 協(xié)議 許多公司也在其c a n 控制器中嵌入了時間觸發(fā)操作 但總的來說 t t c a n 仍處于研發(fā)階段 b o s c h 公司在其生產(chǎn)的硅片f p g a f i e l dp r o g r a m m a b l eg a t ea r r a y 現(xiàn)場可編程門陣 列 中嵌入了t t c a n 協(xié)議的l e v e l l 和l e v e l 2 功能 6 1 生產(chǎn)出t t c a n 協(xié)議評估芯片 t t c a n t c 其封裝為l q f p 4 4 最大波特率為10 0 0 k b s 有3 2 個可單獨配置的信息 體 t t c a n t c 與c p u 實現(xiàn)無縫聯(lián)接 并提供t t c a ni pm o d u l e 集成開發(fā)系統(tǒng) a t m e l 半導體公司在t 8 9 c 5 1 8 0 5 1 中植入了t t c a n 協(xié)議的l e v e l l 功能 n e c 公司開發(fā)的所 有c a n 微控制器系列已經(jīng)可以支持t t c a n 協(xié)議的l e v e l l 功能 對t t c a n 協(xié)議的 l e v e l 2 功能的研究仍處于研發(fā)階段 h i t a c h i 公司也己經(jīng)開展了t t c a n 硬件支持的研究 工作 m i c r o c h i p 公司在其推出的m c p 2 5 1 5 中增加了與t t c a n 相關的硬件資源 一2 一 o 東北大學碩士學位論文第1 章緒論 t t c a n 協(xié)議是對c a n 協(xié)議的一種改進方法 b o s c h 公司在2 0 0 3 年發(fā)布了t t c a n 協(xié)議的i p 模塊 根據(jù)對所查閱資料的分析與研究 t t c a n 協(xié)議較c a n 協(xié)議具有以下 一些優(yōu)勢 6 1 1 t t c a n 協(xié)議將消息交換設定在預先安排好的獨占時間窗口內(nèi) 避免消息的競 爭 當消息在仲裁窗發(fā)生競爭時 采用c a n 的非破壞性仲裁機制 不管是時間觸發(fā)還 是事件觸發(fā)類型消息 它都能較理想的保證消息傳輸?shù)膶崟r性 2 對于實時性通信來說 傳統(tǒng)的c a n 協(xié)議當總線利用率較低時可以滿足實時性的 要求 但當利用率較高時將產(chǎn)生不確定的傳輸延時 對于t t c a n 協(xié)議雖然其響應有一 定的延時 但該延時的上界限是可以得到的 因此可以設計合理的方案滿足消息的截止 期 3 c a n 網(wǎng)絡的同步質(zhì)量要受到各個節(jié)點之間的時鐘容差以及網(wǎng)絡傳輸延遲等諸多 因素的影響 t t c a n 協(xié)議在矩陣周期的每個基本周期開始時都利用參考消息進行一次 時鐘同步 比傳統(tǒng)c a n 網(wǎng)絡有更高的同步質(zhì)量 4 t t c a n 協(xié)議在錯誤檢測機制方面有了提高 其在會話層定義了消息狀態(tài)計數(shù) m s c 寄存器 它實現(xiàn)的錯誤檢測機制可以避免傳輸失敗的消息對網(wǎng)絡的阻塞 實現(xiàn)了 節(jié)點的自診斷功能 5 t t c a n 網(wǎng)絡的最大總線利用在理想情況下可以達到1 0 0 m b p s 通常可以達到 8 0 m b p s 9 0 m b p s 對于傳統(tǒng)的c a n 協(xié)議 在非嚴格實時的控制系統(tǒng)中 總線利用率通 常推薦為2 0 3 0 t t c a n 協(xié)議中最主要的研究工作就是要確定矩陣周期的整體結構 并將消息合理的安排到各個時間窗口中 1 2 實時調(diào)度理論在t t c a n 總線中的必要性 1 實時調(diào)度 在分布式控制系統(tǒng)中的調(diào)度器依據(jù)各個實時應用任務對時間要求的緊迫程度等因 素對多個實時應用任務的執(zhí)行時刻和次序的統(tǒng)籌安排上 在多任務并發(fā)運行的控制系統(tǒng) 中 調(diào)度器在何時選擇某個任務 直接關系到該任務能否在截止期之前完成計算 若給 定一個包含多個實時任務的集合 那么對這一組消息來說 它們按照什么樣的次序被調(diào) 度 直接關系到這組任務的時間約束能否都被滿足 調(diào)度的問題處理起來較為靈活 但 容易對計算結果造成根本性影響 需要在理論和技術上做深入的研究 本小節(jié)對實時調(diào) 度及其在t t c a n 總線中的必要性做專門的介紹 3 東北大學碩士學位論文第1 章緒論 實時系統(tǒng)在調(diào)度策略層面的問題是關系到時間約束能否得到滿足的關鍵問題之一 實時計算任務與普通系統(tǒng)中只要求邏輯正確性的計算任務之間的最大不同之處就是要 滿足執(zhí)行與時間的關系 特別是在多任務并發(fā)的系統(tǒng)中 如果要保證各個實時計算任務 的時問約束都能夠得到滿足 就需要對并發(fā)運行的任務集合在處理器上的運行時序做出 合理的安排 這樣才能達到充分利用系統(tǒng)計算資源完成實時處理的目的 這就引出了實 時計算研究領域中的一個關鍵技術 即實時調(diào)度 調(diào)度的實質(zhì)是資源的分配 包括處理器和其他運算 交互 存儲資源 調(diào)度就是來 用來將這些資源合理地分配給各個實時任務的一種方法 調(diào)度算法決定系統(tǒng)如何進行資 源分配 它是一種服務于系統(tǒng)目標的策略 對于不同的系統(tǒng)及系統(tǒng)目標 應設計不同的 調(diào)度算法 實時調(diào)度面臨著與原來的非實時系統(tǒng)中的調(diào)度所不同的設計目標 這是因為實時計 算的成功除了依賴于結果的邏輯正確性外 還要確保結果產(chǎn)生的時間滿足預定需求 所 以 它同時還要強調(diào)任務的時間約束 為一系列任務決定何時得到何種資源運行 有效 地保障系統(tǒng)中的每個實時任務的實時性能是實時調(diào)度的一個重要目標 這里的實時性能 是指響應時間 截止期等與時間相關的指標 學術界對在使用t t c a n 總線中分布式控 制系統(tǒng)中實時調(diào)度問題與總線容錯問題進行了大量的研究工作 下面做簡單介紹 2 t t c a n 總線系統(tǒng)矩陣調(diào)度算法的研究 t t c a n 總線的調(diào)度本質(zhì)上是對其系統(tǒng)矩陣的實時調(diào)度 目前主要的研究者是針對 t t c a n 總線系統(tǒng)矩陣的實時調(diào)度算法的研究 有的從提高時間觸發(fā)消息的實時性能出 發(fā) 有的則從提高事件觸發(fā)消息的實時性能出發(fā) 提出有基于遺傳算法的靜態(tài)調(diào)度算法 和基于裝箱問題的靜態(tài)調(diào)度算法 f o n s e c a 等人提出一種調(diào)度系統(tǒng)矩陣的方法 它的目標是為了減少所有消息抖動之 和 7 j 提高了時間觸發(fā)消息的實時性能 但是它沒有考慮事件觸發(fā)消息的實時性能 a l b e r t 等人較大的提高了事件觸發(fā)消息實時性能 8 但是他為了簡單 把系統(tǒng)矩陣中所 有列的寬度都設為等長 但實際上 各個消息的傳輸時間可以不同 因此列寬可以不同 x i nq i a o 根據(jù)a l b e r t 研究的缺陷 提出了優(yōu)化時間觸發(fā)消息 減少它們傳輸時間和 提 高了事件觸發(fā)消息的實時性能 9 但是他只考慮滿足系統(tǒng)矩陣限制因素消息組的情況 對于不滿足限制因素的消息組 把其中大于矩陣周期的消息放入仲裁窗里調(diào)度 然而對 于重要的 關鍵性的消息可能會導致危險發(fā)生 本文基于此做了下一步的研究 本文對系統(tǒng)矩陣調(diào)度的創(chuàng)新點是 在遺傳算法中嵌入采用g c d 通過對時間觸發(fā) 4 東北大學碩士學位論文第1 章緒論 消息的在時間窗里的調(diào)度 減少時間窗的浪費 提高系統(tǒng)矩陣的總線利用率 從而保證 了事件觸發(fā)消息有更多的執(zhí)行時間 從而保證了它們的實時性 3 t t c a n 總線容錯的研究 與c a n 不同的是在t t c a n 中 如果有錯誤發(fā)生 禁止消息重傳 這導致可能丟 失關鍵的消息 b m u l l e r 等人是通過提供多通道 2 3 個 達到容錯 1 0 1 這個技術主要的 缺點是需要多條系統(tǒng)總線 這就帶來了這些總線同步的問題 另一個缺點是這個方法 的多余總線要與主總線的速度十分接近 m a t j ac o l n a r i c 等人提出了利用多余的總線來 分擔負載 在正常的條件下每條總線有它自己的時間表 在一般情況下 總線利用 率是非常低的 另外 當負載轉向另一條總線 一些信息在時間表上被清除了 因為 降低了總線效率同時也影響了實時性能 l a nb o s t e r 等人提出系統(tǒng)矩陣里每個獨占窗被 重復兩次 1 2 每個獨占窗被它下一個窗重復 研究結果表明發(fā)送失敗概率降低 但是 每個消息傳輸兩遍 導致發(fā)送效率大幅度較低 a a k a s h 等人提出了m a i l b o xm e t h o d 和a r b i t r a t i o nw i n d o wm e t h o d t l3 1 但是a r b i t r a t i o nw i n d o wm e t h o d 里是針對所有的列寬 都相等的情況下 并且沒有考慮仲裁窗是否能夠為每個獨占窗分配等寬窗口 本文基 于此做了下一步的研究 本文在容錯方面的創(chuàng)新點是對于a r b i t r a t i o nw i n d o wm e t h o d 提出了基于后面優(yōu)先 原則的仲裁窗方法 有效的解決了仲裁窗為獨占窗分配窗口的問題 達到了較好的容 錯效果 1 3 論文研究的內(nèi)容及意義 1 3 1 論文研究的內(nèi)容 本文通過對t t c a n 協(xié)議總線技術的分析和研究 針對t t c a n 協(xié)議調(diào)度算法研究 不足的現(xiàn)狀 以具體經(jīng)典消息組為應用實例 研究t t c a n 協(xié)議的調(diào)度算法與容錯技術 算法研究的實驗平臺是v i s u a ls t u d i oc 6 0 實驗結果驗證了t t c a n 協(xié)議的通信特性 以及本文調(diào)度算法的優(yōu)勢 本文主要的研究內(nèi)容如下 第一章主要介紹了t t c a n 協(xié)議產(chǎn)生的背景 研究現(xiàn)狀及實時調(diào)度理論在t t c a n 總線總的必要性 第二章介紹t t c a n 協(xié)議在繼承c a n 協(xié)議的基礎上的一些特征 包括時間觸發(fā)機 制 時間同步機制 主節(jié)點以及一些基本概念 通過對t t c a n 協(xié)議基本概念的介紹為 后面t t c a n 總線系統(tǒng)矩陣的實時調(diào)度算法的研究打下基礎 5 東北大學碩士學位 第三章主要 定義以及如何提 時性能 針對這 的容錯機制進行 第四章主要 消息和非周期性 總線中系統(tǒng)矩陣 窗來分別進行時 息的影響 然后 因素的消息組 究與改進 在a r b i t r a t i o nw i n d o wm e t h o d 的基礎上提出了基于后面優(yōu)先的仲裁窗容錯原 則 第五章主要通過兩個經(jīng)典消息組p s a 與s a e 對調(diào)度算法與容錯技術進行驗證 通 過對驗證結果中對總線傳輸?shù)膶崟r性以及總線的利用率的分析 驗證了本文系統(tǒng)矩陣調(diào) 度算法的實用性以及t t c a n 總線在通信實時性和總線利用率方面的優(yōu)勢 第六章是結論與展望 1 3 2 論文研究的意義 當通信負載較輕時 可以滿足系統(tǒng)實時性要求 而通信負載較重時 消息間的沖 突會引起延遲時間的不確定性 將不能保證通信的實時性及確定性 如果一個c a n 節(jié) 點有連續(xù)快變的消息或記錄需要顯示時 數(shù)據(jù)會有延遲時間不確定的可能 會造成系統(tǒng) 的不穩(wěn)定和增加控制的難度 如果一個站點惡意重復地發(fā)送信號就有可能導致其他結點 無法發(fā)送數(shù)據(jù) c a n 協(xié)議無法判斷總線上的某個結點是否出現(xiàn)故障 對于傳統(tǒng)的c a n 協(xié)議 在非嚴格實時的控制系統(tǒng)中 總線利用率通常推薦為2 0 3 0 帶寬浪費嚴重 針對c a n 的這些問題 t i c a n 做了一些改進 既有時間觸發(fā) 又保留了事件觸 發(fā) 一定程度上提高了總線的實時性能 本文分析了t t c a n 協(xié)議產(chǎn)生的背景 學習了 t t c a n 協(xié)議的一些關鍵技術 研究了t t c a n 總線的系統(tǒng)矩陣的實時調(diào)度算法與容錯 技術 同時對原有調(diào)度算法與容錯技術都做了一些改進 在理論上研究t t c a n 總線中 系統(tǒng)矩陣的優(yōu)化算法后 又通過具體實例驗證改進的調(diào)度算法的系統(tǒng)性能 包括可靠性 事件觸發(fā)消息的實時性和時間觸發(fā)消息的總線利用率 由于t t c a n 總線的系統(tǒng)矩陣主 6 東北大學碩士學位論文第1 章緒論 要有仲裁窗口和獨占窗口構成 本文通過盡可能的減少獨占窗傳輸時間的辦法來增長獨 占窗的傳輸時間 這樣不僅可以提高獨占窗消息傳輸?shù)目偩€利用率 同時也提高了仲裁 窗口消息傳輸實時性能 t t c a n 協(xié)議通過提供了潛在時間主節(jié)點為全局時鐘提供容錯機制 這些潛在主節(jié) 點在真正主節(jié)點失敗的情況下變成時間主節(jié)點 然而與c a n 不同的是在t f c a n 總線 系統(tǒng)矩陣的獨占窗中消息傳輸時 如果有傳輸錯誤發(fā)生時 不允許消息的重傳 這導致 丟失安全的關鍵的消息 在汽車駕駛中可能會危及乘客的生命 另外 t t c a n 網(wǎng)絡在 惡劣環(huán)境下誤碼率較高 傳送的可靠性下降 容錯的研究對提高網(wǎng)絡性能有很重要的意 義 7 東北大學碩士學位論文第 8 東北大學碩士學位論文第2 章t t c a n 總線協(xié)議及關鍵技術 第2 章t t c a n 總線協(xié)議及關鍵技術 t t c a n 協(xié)議是標準c a n 協(xié)議的的高層協(xié)議 它們在物理層和數(shù)據(jù)鏈路層具有相同 的原理和功能 數(shù)據(jù)鏈路層均采用總線非破壞性 逐位仲裁 機制完成通信 l 4 1 t t c a n 總線節(jié)點完全兼容c a n 節(jié)點 它們使用相同的網(wǎng)絡拓撲結構和總線收發(fā)器 然而它們 不同的是 c a n 協(xié)議是基于事件觸發(fā)機制的通信協(xié)議 僅僅依靠總線的非破壞性 逐 位仲裁 機制實現(xiàn)網(wǎng)絡節(jié)點間的信息交互 而t t c a n 在c a n 協(xié)議之上引入會話層 增加了時間觸發(fā)機制 在仲裁機制的基礎上采用了t d m a 的方式來實現(xiàn)總線通信 本 章首先介紹了t t c a n 協(xié)議的底層協(xié)議 也就是c a n 總線協(xié)議 然后介紹與分析了 t t c a n 總線協(xié)議在c a n 協(xié)議基礎上新增加的一些關鍵技術 2 1t t c a n 總線底層協(xié)議 2 1 1c a n 總線的拓撲結構 t t c a n 協(xié)議下通信系統(tǒng)的網(wǎng)絡拓撲結構與c a n 協(xié)議下的相同 在應用中一般采用 總線型拓撲結構 如圖2 1 所示 1 4 該拓撲結構中 傳輸線可為雙絞線 同軸電纜或光 纖 直接通信距離最遠可達到1 0 k m 速率5 k b p s 以下 通信速率最高可達i m b p s 此時 通信距離最長為4 0 m 網(wǎng)絡上節(jié)點數(shù)主要取決于總線驅(qū)動電路 最多可達1 1 0 個 報 文標識符可達2 0 3 2 種 c a n 2 0 a 擴展幀格式 c a n 2 o a 的報文標識符幾乎不受限制 圖2 1t t c a n c a n 拓撲結構 f i g 2 1t o p o l o g y s t r u c t u r eo ft t c a no rc a n 總線型拓撲結構是多節(jié)點網(wǎng)絡最簡單的形式 在總線拓撲結構中 所有的節(jié)點都直 接連接到同一條傳輸線上 并在傳輸線兩端配上端接器 對c a n 協(xié)議下的總線節(jié)點而 9 東北大學碩士學位論文第2 章t t c a i q 總線協(xié)議及關鍵技術 言 每個節(jié)點都是對等的 因此c a n 總線構成的網(wǎng)絡又可看作是多主節(jié)點的總線網(wǎng)絡 當總線上的節(jié)點發(fā)送消息時 電信號便會從起始點向傳輸?shù)膬啥税l(fā)送直到被端接器所接 收 當電信號在傳輸線上通過時 傳輸線上的每個節(jié)點都會檢查該數(shù)據(jù) 并根據(jù)網(wǎng)絡協(xié) 議的規(guī)定 只接收自己所需要的報文 由于c a n 總線采用多主的工作方式 總線上任 一節(jié)點均可在任意時刻主動地向總線上其他節(jié)點發(fā)送信息 各節(jié)點通過報文濾波實現(xiàn)點 對點 一點對多點及全局廣播等方式傳送接收數(shù)據(jù) c a n 總線采用了專用的集成電路 塊 將諸如數(shù)據(jù)的c r c 校驗 出錯初步處理 接收濾波等等功能都在集成電路中完成 節(jié)省了主機很多時間并且提高了可靠性 2 1 2c a n 總線的分層結構 t t c a n 協(xié)議與c a n 協(xié)議的物理層以及數(shù)據(jù)鏈路層結構相同 并且在c a n 協(xié)議的 基礎上增加了會話層 o s i 七層體系結構里的最低兩層 數(shù)據(jù)鏈路層和物理層其結構如 圖2 2 所示 1 5 j 數(shù)據(jù)鏈路層又劃分為 邏輯鏈路控制l l c l o g i cl i n kc o n t r 0 1 子層和媒體訪問控制 m a c m e d i u m a c c e s sc o n t r 0 1 子層 邏輯鏈路控制l l c 子層的主要功能是 為數(shù)據(jù)傳送 和遠程數(shù)據(jù)請求提供服務 確認l l c 子層接收的報文實際已經(jīng)被接收 并為恢復管理 和通知超載提供信息 媒體訪問控制m a c 子層的功能主要是 傳送規(guī)則 即控制幀結 構 執(zhí)行仲裁 錯誤檢測 出錯標定和故障界定 m a c 子層還要確定為開始一次新的 發(fā)送 總線是否開放或者是否馬上開始接收 m a c 子層是c a n 協(xié)議的核心 它描述由 l l c 子層接收到的報文和對l l c 子層發(fā)送的認可報文 媒體訪問控制子層m a c 的控制功能模型如圖2 3 所示 可劃分為完全獨立工作的 兩個部分 即發(fā)送部分和接收部分 發(fā)送部分的功能包括 1 發(fā)送數(shù)據(jù)封裝 接收l l c 幀和接口控制信息 c r c 循環(huán)計算 通過向l l c 幀附加s o f r t r 位 保留位 c r c a c k 和e o f 構造m a c 幀 2 發(fā)送媒體訪問管理 確認總線空閑后 開始發(fā)送過程 m a c 幀串行化 插入填充位 位填充 在丟失仲裁的情況下 退出仲裁并轉入接收方式 錯誤檢測 監(jiān)控 格式校驗 應答校驗 確認超載條件 構造超載并開始發(fā)送 構造錯 誤指示幀并開始發(fā)送 輸出串行位流至物理層準備發(fā)送 接收部分功能包括 1 接收媒體訪問管理控制 由物理層接收串行位流 解除串 行結構并重新構筑幀結構 檢測填充位 解除位填充 錯誤檢鋇i c r c 格式校驗 填充 規(guī)則校驗 發(fā)送應答 構造錯誤指示幀并開始發(fā)送 確認超載條件 構造超載幀并開 一10 東北大學碩士學位論文第2 章t t c a n 總線協(xié)議及關鍵技術 始發(fā)送 2 接收數(shù)據(jù)拆裝 從接收幀中取出m a c 特定信息 輸出l l c 幀和接口控制 信息至l l c 子層 圖2 2 c a n 的分層結構和功能 f i g 2 2h i e r a r c h i c a ls t r u c t u r ea n df u n c t i o no fc a n l l c 子層 對l l c 子層的訪問 i 發(fā)送數(shù)據(jù)封裝接收數(shù)據(jù)拆分 上 十 發(fā)送媒體訪問管理接收媒體訪問管理 j i 對物理層訪問接口 r 發(fā)送數(shù)據(jù)編碼接收數(shù)據(jù)解碼 物理信令 圖2 3 媒體訪問控制功能模瓔 f i g 2 3f u c t i o nm o d e lo fm a c 物理層是將節(jié)點接至總線的電路實現(xiàn) 定義信號怎樣進行發(fā)送 涉及位定時 位編 碼和同步的描述 物理層主要分為三個部分 1 物理信令p s p h y s i c a ls i g n a l i n g 實現(xiàn)與 1 1 東北大學碩士學位論文第2 章t t c a n 總線協(xié)議及關鍵技術 位表示 定時和同步相關的功能 2 物理媒體附屬裝置p m a p h y s i c a lm e d i u m a t t a c h m e n t 實現(xiàn)總線發(fā)送 接收的功能電路并可提供總線故障檢測方法 3 媒體相關接 口m d i m e d i u md e p e n d e n ti n t e r f a c e 實現(xiàn)物理媒體和媒體訪問單元m a u m e d i u ma c c e s s u n i o 之間機械和電氣接口 2 1 3c a n 總線的報文格式 c a n 總線上節(jié)點問的數(shù)據(jù)均按照報文的格式進行傳輸 報文中包含了與報文一一 對應的標識符i d 它反映了消息特征 也標志了報文的優(yōu)先級 c a n 總線上各個節(jié)點 都可以主動發(fā)送報文 如果同時有兩個或多個節(jié)點開始發(fā)送報文 采用標識符i d 進行 仲裁 具有高優(yōu)先級的報文贏得總線使用權 而其它節(jié)點自動停止發(fā)送 當總線再次空 閑后 這些節(jié)點將自動重新發(fā)送原報文 總線再次進行仲裁 c a n 總線網(wǎng)絡中 報文 傳送不使用有關系統(tǒng)結構的任何信息 如節(jié)點地址等 網(wǎng)絡中的所有節(jié)點根據(jù)報文標識 符i d 對報文進行過濾 自動判斷并決定是否接收該報文 每個節(jié)點都有接收碼寄存器 和屏蔽寄存器 接收到的報文的標識符i d 只有與該節(jié)點的接收碼寄存器內(nèi)容經(jīng)屏蔽寄 存器屏蔽后的數(shù)據(jù)相同 該節(jié)點才開始j 下式接收報文 否則它將不理睬標識符i d 后面 的報文 這使c a n 總線系統(tǒng)非常靈活 可任意擴展或改變節(jié)點組成情況 c a n 采用事件觸發(fā)方式發(fā)送和接收消息 它屬于封裝在芯片內(nèi)的協(xié)議 基于以下 幾條基本規(guī)則進行通信協(xié)調(diào) 總線訪問和仲裁 編碼和解碼 出錯標注和超載標注 c a n 通信協(xié)議規(guī)定了4 種不同的幀格式 數(shù)據(jù)幀 d a t af r a m e 遠程幀 r e m o t ef r a m e 出錯 幀 e r r o rf r a m e 和超載幀 o v e r l o a df r a m e 數(shù)據(jù)幀攜帶數(shù)據(jù)由發(fā)送器至接收器 遠程幀 通過總線節(jié)點發(fā)送 以請求源節(jié)點發(fā)送具有相同標識符的數(shù)據(jù)幀 出錯幀由檢測出總線 錯誤的任何單元發(fā)送 超載幀用于提供當前和后續(xù)的數(shù)據(jù)幀的附加延遲 數(shù)據(jù)幀及遠程 幀與其前面一幀信息 數(shù)據(jù)幀 遠程幀 出錯幀或超載幀 之間均以幀間空間分隔 而超 載幀和出錯幀前面不存在幀間空間 并且多個超載幀前面也不用幀間空間分割 幀間空 間由間歇場和總線空閑場組成 在實際通信中 遠程幀 出錯幀以及超載幀都是為 數(shù) 據(jù)幀 服務的 作為數(shù)據(jù)接收器的節(jié)點可以通過發(fā)送一個 遠程幀 啟動源節(jié)點發(fā)送需 要的數(shù)據(jù) 遠程幀結構與數(shù)據(jù)幀相似 但不包括數(shù)據(jù)場 當某節(jié)點檢測到與c a n 協(xié)議 不相符的錯誤時 該節(jié)點就向總線上發(fā)送 出錯幀 當一個節(jié)點需要更長的時問用于 處理所接收到的消息時 該節(jié)點就會向總線上發(fā)送 超載幀 根據(jù)c a n 技術規(guī)范2 0 a 和2 0 b 以及c a n 國際標準i s o l l 8 9 8 遵循c a n 2 0 a 協(xié) 12 東北大學碩士學位論文 第2 章t t c a n 總線協(xié)議及關鍵技術 議的c a n 控制器只能發(fā)送和接收l l 位標識符的標準報文 而遵循c a n 2 0 b 協(xié)議的c a n 控制器可以發(fā)送和接收l1 位標識符的標準報文或2 9 位標識符的擴展格式報文 兩種標 識符對應的仲裁場格式不同 標準幀的仲裁場由1 1 位標識符和遠程發(fā)送請求位r t r 組 成 擴展幀的仲裁場由2 9 位標識符和替代遠程請求s r r 位 標志位和遠程發(fā)送請求位 r t r 組成 擴展格式數(shù)據(jù)幀的前1 1 位標識符的最后兩位為s r r 和i d e 它們均為隱性 位 這使他們的優(yōu)先級低于具有相同1 1 位標識符的標準格式的數(shù)據(jù)幀 按照數(shù)據(jù)幀中 每5 位就進行一次位填充的原則 可得到最糟糕情況下的數(shù)據(jù)幀長度計算公式 其中標 準格式下的數(shù)據(jù)幀所占用的總線位數(shù)如公式 2 1 所示 擴展格式下的數(shù)據(jù)幀所占用的 總線位數(shù)如公式 2 2 所示 其中 f r a m e l e n g t h 表示消息的位數(shù) 品表示消息幀數(shù)據(jù)場 中的數(shù)據(jù)字節(jié)數(shù) j 旁a m e l e n g t h 摯 4 7 8 氏歸 億 f r a m e l e n g t h i 學 6 7 8 s m 歸 億2 標準格式和擴展格式的數(shù)據(jù)幀結構如圖2 4 所示 c a n 協(xié)議數(shù)據(jù)幀由7 個不同的位場組成 即幀起始 仲裁場 控制場 數(shù)據(jù)場 校驗場 應答場和幀結束 1 幀起始 s o f s o f 標志數(shù)據(jù)幀和遠程幀的開始 它僅由一個顯性位構成 只有 在總線處于空閑狀態(tài)時 才允許節(jié)點開始發(fā)送 所有節(jié)點都必須同步于首先開