徐進(jìn)權(quán)， 王宏志， 胡黃水

（長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長(zhǎng)春 130012）

0 引 言

多功能車輛總線是一種用于列車車輛內(nèi)部各功能設(shè)備之間實(shí)現(xiàn)互連的網(wǎng)絡(luò)總線，是應(yīng)用于車輛控制這一特定場(chǎng)合的現(xiàn)場(chǎng)總線［1－2］。列車通信網(wǎng)絡(luò)標(biāo)準(zhǔn)IEC61375－1是國(guó)際電工委員會(huì)為車載數(shù)據(jù)通信制定的一項(xiàng)國(guó)際標(biāo)準(zhǔn)，其明確指出MVB網(wǎng)絡(luò)通信必須滿足列車對(duì)數(shù)據(jù)傳輸提出的實(shí)時(shí)性要求，實(shí)時(shí)性直接影響著整個(gè)列車的控制性能。因此，認(rèn)真研究MVB網(wǎng)絡(luò)實(shí)時(shí)性相關(guān)技術(shù)是十分必要的，以便形成MVB網(wǎng)絡(luò)實(shí)時(shí)調(diào)度機(jī)制、實(shí)時(shí)性能評(píng)價(jià)等方面的理論模型和分析方法。在國(guó)際標(biāo)準(zhǔn)中對(duì)MVB數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性要求有明確規(guī)定。如何保證網(wǎng)絡(luò)傳輸?shù)膶?shí)時(shí)性要求，學(xué)術(shù)界進(jìn)行了研究，并提出了許多相應(yīng)的算法［3－5］。

文中對(duì)當(dāng)前關(guān)于MVB網(wǎng)絡(luò)實(shí)時(shí)性算法的研究現(xiàn)狀和存在的問題與發(fā)展方向等方面進(jìn)行了闡述。

1 MVB網(wǎng)絡(luò)

1.1 周期掃描表

周期掃描表定義了周期發(fā)送的主幀，以及在輪回中每一基本周期內(nèi)留給偶發(fā)相的剩余時(shí)，在周期查詢中，主設(shè)備按照周期掃描表發(fā)送一個(gè)預(yù)先定義好的主幀序列［6］。在周期輪詢中，主設(shè)備按照周期掃描表發(fā)送一個(gè)預(yù)先定義好的主幀序列。

1.2 過程數(shù)據(jù)和消息數(shù)據(jù)

周期數(shù)據(jù)主要是過程數(shù)據(jù)；非周期數(shù)據(jù)主要是消息數(shù)據(jù)。過程數(shù)據(jù)幀的長(zhǎng)度較短，但實(shí)時(shí)性要求強(qiáng)，傳輸時(shí)間確定有界，周期性發(fā)送，沒有流控制和差錯(cuò)恢復(fù)，是無(wú)需確認(rèn)的廣播通信。過程數(shù)據(jù)一般用于列車控制［7］。過程數(shù)據(jù)是基于時(shí)間觸發(fā)的周期性數(shù)據(jù)，而消息數(shù)據(jù)是基于事件觸發(fā)的偶發(fā)性數(shù)據(jù)。由于消息數(shù)據(jù)的偶發(fā)性和MVB總線的主從工作方式，消息數(shù)據(jù)的通信分為3個(gè)步驟：設(shè)備事件掛起；主設(shè)備輪詢；主設(shè)備指定的設(shè)備開始傳輸消息數(shù)據(jù)。

1.3 MVB幀格式

MVB主幀長(zhǎng)度固定，共33位：9位主起始分界符，16位幀數(shù)據(jù)，8位校驗(yàn)序列，終止分界符［8］。主幀格式如圖1所示。

圖1 主幀格式圖

MVB從幀長(zhǎng)度不固定，存在5種類型：9位從起始分界符，接著為16、32、64、128和256位幀數(shù)據(jù)。通信過程是主設(shè)備發(fā)出主幀，從設(shè)備發(fā)出從幀響應(yīng)該主幀［9］，從幀格式如圖2所示。

圖2 從幀格式圖

1.4 MVB實(shí)時(shí)性要求

MVB數(shù)據(jù)傳輸實(shí)時(shí)性的目標(biāo)是在可靠性、準(zhǔn)確性的情況下盡可能快速地傳輸數(shù)據(jù)。

根據(jù)國(guó)際標(biāo)準(zhǔn)IEC61375－1［10］，信號(hào)產(chǎn)生速度應(yīng)為1.5Mbit±0.01%／s。任何兩個(gè)設(shè)備之間的響應(yīng)延時(shí)都不應(yīng)大于42.7μs。兩個(gè)相鄰主幀之間的時(shí)間間隔應(yīng)大于9.0BT。對(duì)于MVB總線上所有重要變量，從一個(gè)應(yīng)用到另一應(yīng)用的確定性傳送必須保證在16ms內(nèi)完成。周期掃描表中最長(zhǎng)的特征周期不能超過1 024.0ms。

2 實(shí)時(shí)性算法研究現(xiàn)狀

根據(jù)MVB網(wǎng)絡(luò)傳輸數(shù)據(jù)的類型，將現(xiàn)有的實(shí)時(shí)算法分為周期數(shù)據(jù)實(shí)時(shí)性算法和非周期數(shù)據(jù)實(shí)時(shí)性算法。

2.1 周期數(shù)據(jù)傳輸實(shí)時(shí)算法

對(duì)于周期數(shù)據(jù)，主要是過程數(shù)據(jù)，MVB網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)闹饕绞绞侵髟O(shè)備根據(jù)周期掃描表尋址源設(shè)備。周期數(shù)據(jù)傳輸實(shí)時(shí)算法依據(jù)周期掃描表的輪詢方式分為3類，如圖3所示。

圖3 周期數(shù)據(jù)傳輸實(shí)時(shí)算法

2.1.1 實(shí)時(shí)調(diào)度算法

調(diào)度的實(shí)質(zhì)是資源的分配，而實(shí)時(shí)調(diào)度強(qiáng)調(diào)的是任務(wù)的時(shí)間約束［11］。實(shí)時(shí)調(diào)度算法中常見的是基于優(yōu)先級(jí)驅(qū)動(dòng)的調(diào)度算法，一般分為靜態(tài)優(yōu)先級(jí)調(diào)度和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度［12］。靜態(tài)優(yōu)先級(jí)調(diào)度算法的代表是單調(diào)速率算法（Rate Monotonic，RM）［13－14］；動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法的代表是最早截止期優(yōu)先算法（Earliest Deadline First，EDF）［15］。不論是何種調(diào)度算法，在進(jìn)行實(shí)時(shí)調(diào)度時(shí)都要在周期輪詢之前進(jìn)行可調(diào)度性能分析，即判斷調(diào)度算法是否能夠滿足系統(tǒng)的實(shí)時(shí)性、可靠性［16］?，F(xiàn)在常采用基于系統(tǒng)利用率和任務(wù)響應(yīng)兩種方法進(jìn)行可調(diào)度算法性能分析。前者計(jì)算精確度不夠，但計(jì)算開銷小，可以用于新任務(wù)的接入控制；后者計(jì)算開銷大，但可以得到每個(gè)任務(wù)的響應(yīng)時(shí)間。

RM算法是一種靜態(tài)固定分配算法。RM算法根據(jù)任務(wù)執(zhí)行周期的長(zhǎng)短來(lái)決定優(yōu)先級(jí)高低，執(zhí)行周期短的任務(wù)優(yōu)先級(jí)高，執(zhí)行周期長(zhǎng)的任務(wù)優(yōu)先級(jí)低。即速率越高，優(yōu)先級(jí)越高。EDF算法是一種基于動(dòng)態(tài)優(yōu)先級(jí)的調(diào)度算法［17］，按照數(shù)據(jù)的截止時(shí)間來(lái)確定優(yōu)先級(jí)。任務(wù)的截止時(shí)間越小，優(yōu)先級(jí)越高；任務(wù)的截止時(shí)間越大，優(yōu)先級(jí)越低［18］。在每一個(gè)可調(diào)度時(shí)刻，數(shù)據(jù)任務(wù)的優(yōu)先級(jí)都需要?jiǎng)討B(tài)調(diào)整。

對(duì)于RM算法，前文中提到的兩種調(diào)度性能分析的方法都無(wú)法直接應(yīng)用，且靈活性、自適應(yīng)性較差。對(duì)于EDF算法，適應(yīng)性強(qiáng)，但調(diào)度工作量大。有專家提出，將RM算法和EDF算法合理結(jié)合，可以得到一種含閾值的多處理器實(shí)時(shí)任務(wù)調(diào)度方法［19］，該方法可以使任務(wù)在閾值范圍內(nèi)在各處理器上進(jìn)行遷移，避免了部分處理器處于空閑，部分處理器過于繁忙導(dǎo)致的任務(wù)被掛起現(xiàn)象，保證各處理器利用率相對(duì)平衡，從而實(shí)現(xiàn)提高系統(tǒng)的實(shí)時(shí)性。

2.1.2 報(bào)文定時(shí)無(wú)關(guān)的周期掃描表優(yōu)化設(shè)計(jì)

列車通信網(wǎng)絡(luò)協(xié)議指出，如果在周期輪詢中能夠均勻地安排循環(huán)周期，就能得到更好的實(shí)時(shí)性。而要想實(shí)現(xiàn)均勻的安排循環(huán)，就要盡可能減低周期掃描表的陡度和寬度。利用基本規(guī)則［6］生成的周期掃描表陡度較大，周期數(shù)據(jù)分布不夠均勻。利用逐步填空法［6］可以生成報(bào)文定時(shí)無(wú)關(guān)的周期掃描表，陡度較小，周期數(shù)據(jù)較為均勻，從而實(shí)時(shí)性更好。

2.1.3 報(bào)文定時(shí)相關(guān)的周期掃描表優(yōu)化設(shè)計(jì)

分析報(bào)文定時(shí)的周期掃描表時(shí)，隨著數(shù)據(jù)數(shù)量的不斷增加，如何快速合理地分配周期數(shù)據(jù)在周期掃描表中的位置是一個(gè)很難解決的問題，基本規(guī)則和逐步填空算法都達(dá)不到理想要求。報(bào)文定時(shí)相關(guān)的周期掃描表優(yōu)化的實(shí)質(zhì)是典型的組合優(yōu)化問題［20］。為了找到求解組合優(yōu)化問題的最合適方法，相關(guān)學(xué)者提出了近似算法（Approximate Algorithm，AA）［21］、啟發(fā)式算法（Heurisc Algorithm，HA）［22］、群體智能優(yōu)化算法（Population－based Intelligent Optimization，PIO）［23－24］等方法。AA算法的計(jì)算結(jié)果與最優(yōu)結(jié)果之間是有最優(yōu)度保證的，但近似算法沒有可遵循的框架，設(shè)計(jì)復(fù)雜，實(shí)際操作較為困難；HA算法比較容易實(shí)現(xiàn)，可以應(yīng)用在非常廣泛的問題上，但是該算法要求對(duì)每一個(gè)問題都要建立一個(gè)特殊的啟發(fā)式規(guī)則，此類規(guī)則不具備通用性，不能保證效率；PIO算法是基于群體智能理論的一種新型演化計(jì)算技術(shù)，具有較強(qiáng)的通用性和全局尋優(yōu)的特點(diǎn)。

遺傳算法是群體智能優(yōu)化算法的一種，是一種全局搜索算法。其局部搜索能力較差，具有“早熟”問題，所以比較費(fèi)時(shí)，在進(jìn)化后期搜索效率較低?；旌线z傳算法［25－26］是在遺傳算法的基礎(chǔ)上引入其它優(yōu)化算法（如局部搜索能力強(qiáng)的算法），以保證遺傳算法在全局性能的基礎(chǔ)上大大減小計(jì)算量來(lái)提高收斂速度，以保證周期通信的實(shí)時(shí)性。

2.1.4 算法比較分析

對(duì)于MVB周期數(shù)據(jù)的實(shí)時(shí)性優(yōu)化，實(shí)際是周期掃描表的優(yōu)化。對(duì)周期掃描表進(jìn)行優(yōu)化的目標(biāo)是使周期數(shù)據(jù)能夠均勻分布在周期掃描表中，這就要求周期掃描表的寬度和陡度很小。無(wú)論是RM算法還是EDF算法，在實(shí)現(xiàn)調(diào)度之前，需要進(jìn)行調(diào)度性分析。RM算法和EDF算法都有其局限性，如何結(jié)合兩種算法的優(yōu)勢(shì)，揚(yáng)長(zhǎng)避短，是未來(lái)研究的一個(gè)重要方向。

靜態(tài)優(yōu)先級(jí)調(diào)度算法可以依靠時(shí)間屬性分配優(yōu)先級(jí)，可控性較強(qiáng)，而動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法在資源分配和調(diào)度時(shí)，靈活性較強(qiáng)。AA算法實(shí)際操作困難、HA算法通用性較差、遺傳算法不具備全局收斂性。鑒于此，有學(xué)者又提出了改進(jìn)的混合遺傳算法，但是混合遺傳算法也有不足，如計(jì)算量很大。對(duì)于周期掃描表的優(yōu)化，群體智能優(yōu)化統(tǒng)一框架下的算法是未來(lái)研究實(shí)時(shí)性的一個(gè)重要方向和領(lǐng)域。算法具體性能對(duì)比見表1。

表1 算法性能對(duì)比

2.2 非周期數(shù)據(jù)傳輸實(shí)時(shí)性算法

非周期數(shù)據(jù)主要是消息數(shù)據(jù)，是按需傳送的，屬偶發(fā)性數(shù)據(jù)，一般用于任務(wù)診斷。消息數(shù)據(jù)的傳遞是通過MVB主設(shè)備發(fā)送事件請(qǐng)求來(lái)實(shí)現(xiàn)的。在偶發(fā)相中，總線主設(shè)備告知有事件的設(shè)備。主設(shè)備發(fā)布一個(gè)一般事件輪詢開始事件巡回，要求所有設(shè)備報(bào)告事件，當(dāng)幾個(gè)設(shè)備同時(shí)掛起時(shí)，會(huì)有多個(gè)響應(yīng)產(chǎn)生，發(fā)生碰撞。因此需要采用MVB事件仲裁機(jī)制對(duì)事件進(jìn)行仲裁分辨［27］。在IEC協(xié)議中，說(shuō)明了3種仲裁方法：首次仲裁、向下仲裁、向上仲裁。仲裁調(diào)度的過程是系統(tǒng)資源分配的過程，也就是對(duì)消息數(shù)據(jù)按照一定規(guī)則進(jìn)行合理調(diào)度的過程。消息數(shù)據(jù)傳輸實(shí)時(shí)算法根據(jù)縮短延時(shí)的方法，可以分成3類，如圖4所示。

2.2.1 典型事件搜索算法

典型事件仲裁算法按照折半查找法對(duì)網(wǎng)絡(luò)設(shè)備進(jìn)行搜索查找。折半查找是一種簡(jiǎn)單常用的方法，并且當(dāng)每個(gè)記錄的查找概率相等時(shí)，折半查找算法的性能是最優(yōu)的［28］，由于折半查找法是將查找的范圍不斷縮小一半，所以查找效率較高，但計(jì)算開銷大。當(dāng)主設(shè)備發(fā)送組事件請(qǐng)求之后，如果收到單個(gè)響應(yīng)，則主設(shè)備返回此響應(yīng)；主設(shè)備將組地址的最低有效位取反并發(fā)送組事件請(qǐng)求。如果產(chǎn)生碰撞，主設(shè)備將對(duì)具有公共地址的上次組中的半數(shù)設(shè)備形成一個(gè)新組，發(fā)送一個(gè)組事件請(qǐng)求。如果組事件請(qǐng)求響應(yīng)為寂靜主設(shè)備再次發(fā)送的組事件請(qǐng)求尋址范圍為前一次的一半。具體流程如圖5所示。

圖4 非周期數(shù)據(jù)傳輸實(shí)時(shí)算法

圖5 事件仲裁流程圖

針對(duì)查找范圍變化很大而又相對(duì)穩(wěn)定的查找對(duì)象，人們又提出了一種改進(jìn)的基于區(qū)間控制的折半查找算法，當(dāng)后一個(gè)查找對(duì)象在前一個(gè)查找對(duì)象附近時(shí)，在最壞狀態(tài)和平均狀態(tài)下，該算法查找速度更快，實(shí)現(xiàn)代價(jià)更?。?9］。

2.2.2 二叉樹仲裁

首先明確兩個(gè)概念：當(dāng)節(jié)點(diǎn)數(shù)目相同時(shí)，完全二叉樹的路徑長(zhǎng)度最短；樹的帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為最優(yōu)二叉樹，即哈夫曼樹，相應(yīng)的算法稱為哈夫曼算法［30］。根據(jù)組地址的定義及相關(guān)特點(diǎn)，可以引入仲裁二叉樹來(lái)實(shí)現(xiàn)事件仲裁。引入仲裁二叉樹后，根據(jù)連續(xù)分配地址方式，生成了一顆完全二叉樹。連續(xù)分配方式產(chǎn)生的完全二叉樹的缺點(diǎn)是此類二叉樹不是任意條件下的最優(yōu)二叉樹。當(dāng)設(shè)備延時(shí)相同，連續(xù)分配方式生成的是最優(yōu)二叉樹；當(dāng)設(shè)備延時(shí)不同，只有通過最優(yōu)二叉樹算法分配地址才能保證時(shí)間仲裁時(shí)延最優(yōu)化。

最優(yōu)二叉樹通常有兩種生成算法，分別是哈弗曼算法和逆推調(diào)位算法［31］。逆推調(diào)位算法利用遞推算法的逆推原理，根據(jù)被處理結(jié)點(diǎn)位置移動(dòng)產(chǎn)生的權(quán)的變化值確定各個(gè)結(jié)點(diǎn)的精確位置。由于逆遞推調(diào)位算法在運(yùn)算過程中的比較次數(shù)少，所以使得運(yùn)算的整體速度比哈夫曼算法更快。即在空間復(fù)雜度上，哈弗曼算法比逆推調(diào)位算法簡(jiǎn)單；在時(shí)間復(fù)雜度上，逆推調(diào)位算法比較簡(jiǎn)單。因?yàn)橹俨枚鏄涫怯邢奚疃鹊?，所以仲裁二叉樹的生成算法一般選擇哈弗曼算法［32－33］。

2.2.3 優(yōu)先級(jí)配置算法

想要滿足非周期數(shù)據(jù)傳輸?shù)膶?shí)時(shí)要求，也可以利用優(yōu)先級(jí)配置方法［2］，即利用物理地址優(yōu)先級(jí)和事件優(yōu)先級(jí)兩種方法來(lái)縮短仲裁延時(shí)。

物理地址優(yōu)先級(jí)：仲裁過程一般是從設(shè)備的物理地址最低位開始逐位搜索，因此在安排設(shè)備物理地址時(shí)，從1開始定義，逐位增加，連續(xù)分配。這樣地址越小，則其優(yōu)先級(jí)越高。

事件類型優(yōu)先級(jí)：在一般事件請(qǐng)求幀中有4位用來(lái)定義事件類型，可以最多定義16種優(yōu)先級(jí)類型。但國(guó)際標(biāo)準(zhǔn)中僅使用最低位定義了兩種事件優(yōu)先級(jí)類型：高優(yōu)先級(jí)和低優(yōu)先級(jí)。當(dāng)設(shè)備較多時(shí)，發(fā)生沖突碰撞的概率就會(huì)增加。因此，可以根據(jù)事件的重要性設(shè)置多種優(yōu)先級(jí)，以減小碰撞發(fā)生的概率。

2.2.4 算法比較分析

事件仲裁是事件輪詢機(jī)制的核心部分。提高消息數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性，實(shí)質(zhì)上是對(duì)沖突事件進(jìn)行合理調(diào)度，從而減少仲裁時(shí)延。經(jīng)典算法和典型時(shí)間搜索算法是比較基礎(chǔ)的仲裁算法，在此基礎(chǔ)上，可以提出諸多改進(jìn)算法，以提升數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性能。折半查找算法是一種常見的算法，計(jì)算開銷大，不適宜大范圍查找。改進(jìn)的折半查找算法相對(duì)來(lái)講在速度和計(jì)算復(fù)雜度方面有所提高。二者都適用于過程控制中的實(shí)時(shí)查找。仲裁二叉樹算法的提出為仲裁過程的分析實(shí)現(xiàn)提供了又一方法思路。對(duì)二叉樹模型進(jìn)一步改進(jìn)優(yōu)化，即利用設(shè)備地址分配方式提出的有限深度最優(yōu)二叉樹算法得到的分配方式比連續(xù)分配方式有明顯的優(yōu)勢(shì)，有限深度最優(yōu)二叉樹算法改進(jìn)了連續(xù)分配方式產(chǎn)生的二叉樹的不足，進(jìn)一步減少了仲裁延時(shí)。

算法的性能對(duì)比見表2。

表2 算法性能對(duì)比

3 結(jié) 語(yǔ)

按照周期數(shù)據(jù)傳輸和非周期數(shù)據(jù)傳輸兩個(gè)方面對(duì)MVB網(wǎng)絡(luò)實(shí)時(shí)性算法研究的現(xiàn)狀進(jìn)行了總結(jié)，并對(duì)當(dāng)前研究中存在的普遍問題進(jìn)行了分析和概括。從目前的研究現(xiàn)狀來(lái)看，已經(jīng)提出了許多有效算法來(lái)改善系統(tǒng)的實(shí)時(shí)性，如遺傳算法、最優(yōu)二叉樹算法等。

總體來(lái)說(shuō)，提高M(jìn)VB網(wǎng)絡(luò)實(shí)時(shí)性要盡量使周期掃描表中數(shù)據(jù)分布均勻、減小算法復(fù)雜度、提高計(jì)算精確度、提高介質(zhì)傳輸速率、減少仲裁延時(shí)。同時(shí)，通過減少響應(yīng)時(shí)間、提高反應(yīng)速率、縮小仲裁延時(shí)，改善MVB網(wǎng)絡(luò)實(shí)時(shí)性?？梢?，MVB網(wǎng)絡(luò)實(shí)時(shí)性算法還有許多領(lǐng)域可以進(jìn)一步研究。

［1］ 周俊，姬長(zhǎng)英.智能車輛橫向控制研究［J］.機(jī)器人，2003，25（1）：26－30.

［2］ 聶曉波，王立德，申萍.軌道車輛MVB網(wǎng)絡(luò)實(shí)時(shí)性能分析與優(yōu)化研究［J］.鐵道學(xué)報(bào)，2011，33（9）：40－44.

［3］ 王濤，王立德，周潔瓊.MVB網(wǎng)絡(luò)周期輪詢算法優(yōu)化與仿真研究［J］.機(jī)車電傳動(dòng)，2013（6）：40－45.

［4］ 朱俊，李芳，王麗芳.基于蟻群算法的多功能車輛周期掃描表的優(yōu)化設(shè)計(jì)［J］.鐵道學(xué)報(bào)，2013，35（7）：57－62.

［5］ 戴嘉瑋，韋巍.基于多功能車輛總線事件仲裁的優(yōu)化設(shè)計(jì)［J］.鐵道學(xué)報(bào)，2013，35（4）：66－70.

［6］ 王永翔，王立德.多功能車輛總線周期掃描表的最優(yōu)化設(shè)計(jì)［J］.鐵道學(xué)報(bào)，2009，31（6）：46－52.

［7］ 王永翔，王立德.基于廣義隨機(jī)Petri網(wǎng)的MVB網(wǎng)絡(luò)吞吐性能分析［J］.北京交通大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，32（5）：98－101.

［8］ 陳特放，曾秋芬.列車微機(jī)與網(wǎng)絡(luò)控制技術(shù)及應(yīng)用［M］.北京：科學(xué)出版社，2012.

［9］ 劉建偉，王蕾，譚南林，等.軌道車輛MVB通信網(wǎng)絡(luò)的實(shí)施特性［J］.中國(guó)鐵道科學(xué)，2006，27（6）：79－82.

［10］ International electrotechnical commission.IEC61375－1：1999，part 1：Train communication network［S］.Genva，1999.

［11］ 夏家莉，陳輝，楊兵.一種動(dòng)態(tài)優(yōu)先級(jí)實(shí)時(shí)任務(wù)調(diào)度算法［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（12）：2684－2694.［12］ 吳星.多處理器實(shí)時(shí)任務(wù)調(diào)度策略的研究［D］.昆明：昆明理工大學(xué)，2013.

［13］ 王愛平，張功營(yíng)，劉方.一個(gè)基于R M的弱硬實(shí)時(shí)調(diào)度算法［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，27（7）：743－746.

［14］ Giorgio C Buttazzo.Rate monotonic vs.EDF：judgmentn Day［J］.Real－Time Systems，2005，29（1）：5－26.

［15］ 程禹，趙宏偉，龍曼麗，等.最早截止期優(yōu)先調(diào)度算法的改進(jìn)［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2013，43（5）：1338－1342.

［16］ 朱琴躍，謝偉達(dá)，譚喜堂，等.MVB周期信息的實(shí)時(shí)調(diào)度［J］.計(jì)算機(jī)應(yīng)用，2007，27（12）：3108－3115.

［17］ 張惠娟，周利華.一種基于EDF算法的多處理器實(shí)時(shí)調(diào)度算法［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39（30）：16－17.

［18］ 袁暋，檀明，周晶晶.EDF調(diào)度算法可調(diào)度性分析方法的改進(jìn)研究［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（8）：2429－2431.

［19］ 王異奇.多處理器實(shí)時(shí)調(diào)度算法實(shí)現(xiàn)及模擬框架研究［D］.大連：遼寧師范大學(xué)，2011.

［20］ 王永翔，王立德.多功能車輛總線周期掃描表的最優(yōu)化設(shè)計(jì)［J］.鐵道學(xué)報(bào)，2009，31（6）：46－52.

［21］ Zi Xu，Xinming Wu.A new hybrid stochastic approximation algorithm［J］.Optimization Letters，2013，7（3）：5593－5606.

［22］ 江有福，吳偉志.動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)最短路徑啟發(fā)式算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2008，25（5）：36－44.

［23］ Schmitt，Lothar M.Theory of genetic algorithm［J］.Theoretical Computer Science，2001，259（1）：51－61.

［24］ Wang Yan，Shan Xin－xin，Sun Yan－ming.Study on the application of genetic algorithms in the optimization of wireless network［J］.Procedia Engineering，2011，16：181－231.

［25］ 樊春天.基于經(jīng)典優(yōu)化算法的混合遺傳算法的研究與應(yīng)用［D］.合肥：安徽理工大學(xué)，2013.

［26］ G Vivó－Truyols，J R Torres－Lapasió，A Garrido－Frenich，et al.A hybrid genetic algorithm with local search［J］.Chemometrics and Intelligent Laboratory Systems，2001，59（1）：107－120.

［27］ 朱琴躍，謝偉達(dá)，譚喜堂.MVB協(xié)議一致性測(cè)試研究與實(shí)現(xiàn)［J］.鐵道學(xué)報(bào)，2007，29（4）：115－120.

［28］ 時(shí)百勝.基于概念的折半查找算法［J］.計(jì)算機(jī)科學(xué)，2009，36（6）：235－158.

［29］ 王靜，譚祥爽，宋現(xiàn)鋒，等.一種GPS航跡線的自適應(yīng)折半查找化簡(jiǎn)算法［J］.西安電子科技大學(xué)學(xué)報(bào)，2014，41（5）：176－182.

［30］ Hiroshi Fujiwara，Tobias Jacobs.On the Huffman and alphabetic tree problem with general cost functions［J］.Algorithmica，2014，69（3）：582－604.

［31］ 楊琳，王從慶，繆鵬，等.基于Huffman最優(yōu)二叉樹支持向量機(jī)的艙音記錄器背景信號(hào)識(shí)別［J］.宇航學(xué)報(bào)，2011，32（6）：1428－1434.

［32］ 郭建光，張衛(wèi)杰，楊健，等.基于廣義規(guī)范Huffman樹的高效編解碼算法［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，49（1）：73－77.

［33］ Yih－Kai Lin，Shu－Chien Huang，Cheng－Hsing Yang.A fast algorithm for Huffman decoding based on a recursion Huffman tree［J］.The Journal of Systems ＆Software，2012，85（4）：974－980.