[發(fā)明專利]一種CAN總線主從應答模式協(xié)議的網(wǎng)絡調(diào)度算法

無效

• 申請?zhí)枺?/td>: 201310322857.0
• 申請日: 2013-07-29
• 公開（公告）號: CN103414624A
• 公開（公告）日: 2013-11-27
• 發(fā)明（設計）人: 孫本新;萬江文;黃健祥;馮仁劍
• 申請（專利權）人: 北京匯能精電科技有限公司
• 主分類號: H04L12/403
• 分類號: H04L12/403
• 代理公司: 北京思海天達知識產(chǎn)權代理有限公司 11203
• 代理人: 劉萍

1.一種CAN總線主從應答模式協(xié)議的網(wǎng)絡調(diào)度算法，其特征在于，包括以下步驟：

步驟一：網(wǎng)絡中所有節(jié)點廣播競爭主節(jié)點，標識符最低的節(jié)點將成為網(wǎng)絡主節(jié)點；

步驟二：網(wǎng)絡主節(jié)點廣播統(tǒng)計信息，所有節(jié)點返回本節(jié)點的請求和應答消息，存至主節(jié)點內(nèi)存中；

步驟三：網(wǎng)絡主節(jié)點根據(jù)統(tǒng)計收集的所有消息，采用“間隔式裝箱算法”構造調(diào)度表；

步驟四：網(wǎng)絡主節(jié)點采用遺傳算法優(yōu)化已構造的調(diào)度表；

步驟五：網(wǎng)絡主節(jié)點將優(yōu)化后的調(diào)度表信息發(fā)送至網(wǎng)絡中的每個節(jié)點后，再廣播參考消息開始網(wǎng)絡消息調(diào)度；

步驟六：網(wǎng)絡主節(jié)點在開始調(diào)度一段時間后，重復步驟二至步驟五，根據(jù)網(wǎng)絡中節(jié)點運行情況及時更新調(diào)度表。

2.如權利要求1所述的方法，其特征在于，在所述步驟二中統(tǒng)計信息包括每個節(jié)點的請求消息和對應的應答消息，這些消息的屬性包括消息個數(shù)、消息傳輸時間長度和消息傳輸周期。

3.如權利要求1所述的方法，其特征在于，在所述步驟三中間隔式裝箱算法在構造調(diào)度表時，放置請求消息MQ_i后需要將對應的應答消息MR_i進行間隔一列放置，而間隔的空閑列則用于下一個消息的分配。間隔式裝箱算法構造調(diào)度表的過程如下：

（1）主節(jié)點根據(jù)收集的所有消息，計算調(diào)度表的周期、基本周期、調(diào)度表行數(shù)；

（2）從存儲的消息中取出消息MQ_i和MR_i，遍歷調(diào)度表，判斷調(diào)度表中的某行長度是否能同時容下消息MQ_i和MR_i，能則放置消息MQ_i和MR_i；不能則繼續(xù)遍歷調(diào)度表，尋找可同時放下消息MQ_i和MR_i的位置；

（3）重復過程（2），直至所有的消息均放入調(diào)度表中。

4.如權利要求1所述的方法，其特征在于，在所述步驟四中的遺傳算法，步驟如下：

（1）將步驟三構造的調(diào)度表采用實數(shù)編碼后作為初始個體，剩余個體隨機產(chǎn)生；

（2）構造適應度函數(shù)，適應度函數(shù)由每個個體解碼后表示的總線利用率和懲罰因子組成；

（3）在每次進行選擇、交叉、變異三個操作之前，均需先計算所有個體的適應度函數(shù)，并保留最優(yōu)個體不參與選擇、交叉和變異三個操作；

（4）選擇采用輪盤賭算法進行選擇，采用單點交叉和兩點交叉的混合交叉算法，隨機數(shù)（0，1）的方式選擇交叉算法，隨機數(shù)為0采用單點交叉算法，隨機數(shù)為1采用兩點交叉算法；變異則采用隨機概率的方式進行隨機位的變異。

5.如權利要求4所述的方法，其特征在于，個體r的適應度函數(shù)fr由總線利用率和懲罰因子組成，表示為：其中p_r為個體r的懲罰因子，針對遺傳算法優(yōu)化過程中產(chǎn)生的某些個體解碼后列數(shù)可能超過原調(diào)度表列數(shù)總數(shù)的限制，若超過則個體為不合理，否則為合理，而引入的懲罰因子就是根據(jù)這些個體解碼后的調(diào)度表是否合理來影響該個體遺傳至下一代的概率；若個體r解碼后對應的調(diào)度表是合理的，則p_r為0，否則為一個很大的常數(shù)α，α選取為的1000倍以上；tr_i為相對編號為i的消息傳輸時間長度，T為調(diào)度表的調(diào)度周期，Q為獨占窗中總線利用率非最優(yōu)的時間窗個數(shù)，L_j為分配在第j列的時間窗長度，n_j分配在j列的消息個數(shù)，i為分配在優(yōu)化獨占窗的消息編號，k為分配在優(yōu)化獨占窗的消息個數(shù)；f_r代表個體的優(yōu)越程度。

6.如權利要求1所述的方法，其特征在于，在所述步驟五所述優(yōu)化后發(fā)送調(diào)度表信息，發(fā)送的調(diào)度表信息包括調(diào)度基本周期、調(diào)度表周期、調(diào)度表行數(shù)、調(diào)度表列數(shù)、調(diào)度表每列時間窗寬度和調(diào)度表每行每列分配發(fā)送的消息標識符。