王 倩， 郭天昊， 郭大波， 岳文淵， 張 鋼

(山西大學(xué) 物理電子工程學(xué)院， 山西 太原 030006)

0 引 言

車聯(lián)網(wǎng)[1-2]是集安全、 移動(dòng)、 環(huán)境等多方面交通問題下的產(chǎn)物， 是構(gòu)建智能交通系統(tǒng)的解決思路. 車載容遲網(wǎng)絡(luò)作為一種新型的網(wǎng)絡(luò)， 在一些特定的網(wǎng)絡(luò)環(huán)境下， 網(wǎng)絡(luò)會(huì)經(jīng)常斷開， 導(dǎo)致節(jié)點(diǎn)間消息的傳輸成功率會(huì)受到影響. 而路由是影響車載容遲網(wǎng)絡(luò)傳輸成功率的問題之一， 其負(fù)責(zé)通信網(wǎng)絡(luò)中數(shù)據(jù)包傳輸路徑的選擇. 車載容遲互聯(lián)網(wǎng)正在興起， 并成為一個(gè)熱門的研究課題， 因此， 改進(jìn)車載容遲網(wǎng)絡(luò)[3-4]路由算法來提高傳輸效率、 降低網(wǎng)絡(luò)開銷一直是研究熱點(diǎn)之一.

近年來， 對(duì)于Prophet算法的改進(jìn)方式層出不窮. 崔建群等[10]提出了一種機(jī)會(huì)網(wǎng)絡(luò)中基于節(jié)點(diǎn)相似率的概率路由算法， 并添加了ACK確認(rèn)機(jī)制， 但是沒有考慮到消息調(diào)度對(duì)投遞率和網(wǎng)絡(luò)開銷的影響； 王艷玲等[11]提出對(duì)Prophet算法的緩沖區(qū)進(jìn)行設(shè)計(jì)， 通過限制副本數(shù)、 控制生存期和刪除冗余消息來節(jié)省緩存區(qū)， 從而減輕節(jié)點(diǎn)的負(fù)載. 雖然考慮了緩存管理， 但未討論消息調(diào)度對(duì)網(wǎng)絡(luò)開銷和投遞率的影響； Chao等[12]提出了針對(duì)DRN的能源意識(shí)的風(fēng)險(xiǎn)規(guī)避路由框架(EAR)， 通過限制分組副本數(shù)量的參數(shù)L和差異化服務(wù)模型用于提高分組傳遞效率(PDE)， 同時(shí)將其他指標(biāo)保持在適當(dāng)?shù)乃剑?但其并未討論消息調(diào)度和ACK確認(rèn)機(jī)制對(duì)緩存管理的影響； 鐘陳陳等[13]針對(duì)網(wǎng)絡(luò)擁塞的問題， 給出了一種基于歸一化的混合參數(shù)緩存管理策略， 以丟棄歸一化混合參數(shù)小的消息為代價(jià)， 以節(jié)省緩存空間， 減少擁塞， 但其未提及ACK機(jī)制對(duì)網(wǎng)絡(luò)開銷的影響； Wang等[14]提出了一種基于節(jié)點(diǎn)擁塞程度的改進(jìn)路由算法(PROPHET-CLN)， 不僅解決了根據(jù)傳遞概率進(jìn)行選擇的問題， 而且根據(jù)節(jié)點(diǎn)的能力分配了正確的消息大??； 施俊等[15]針對(duì)消息轉(zhuǎn)發(fā)策略， 提出消息的優(yōu)先級(jí)決定了副本數(shù)量的多少， 優(yōu)先級(jí)越高， 副本越多. Wang[14]和施俊[15]雖然分別考慮了節(jié)點(diǎn)與消息大小、 消息副本與消息優(yōu)先級(jí)的之間的關(guān)系， 但是沒有考慮消息調(diào)度和可以從根本上解決緩存太大的ACK確認(rèn)機(jī)制.

針對(duì)上述問題， 本文提出了一種基于消息調(diào)度和噴射等待的車載容遲網(wǎng)絡(luò)路由算法MSSW. 該算法采用增量平均方法， 改進(jìn)投遞預(yù)測(cè)概率相遇更新公式， 采用增強(qiáng)型方法， 改進(jìn)投遞預(yù)測(cè)概率衰減更新公式， 并且討論了副本控制、 消息調(diào)度和ACK確認(rèn)機(jī)制對(duì)投遞率和網(wǎng)絡(luò)開銷的影響. 主要貢獻(xiàn)如下：

1) 采用增量平均的方法， 改進(jìn)投遞預(yù)測(cè)概率的相遇更新公式， 采用增強(qiáng)型的方法， 改進(jìn)衰減更新的公式；

2) 采用消息調(diào)度機(jī)制， 對(duì)網(wǎng)絡(luò)中的消息進(jìn)行優(yōu)先級(jí)排序傳輸和刪除， 提高傳輸效率；

3) 采用噴射和等待的傳遞方式， 同時(shí)對(duì)副本定量控制， 有效緩解了Prophet算法沒有設(shè)置副本數(shù)量上限而導(dǎo)致的擁塞問題， 降低了網(wǎng)絡(luò)開銷；

4) 加入ACK確認(rèn)機(jī)制， 將已到達(dá)目的節(jié)點(diǎn)的消息確認(rèn)和刪除， 避免了消息在節(jié)點(diǎn)間重復(fù)轉(zhuǎn)發(fā)， 減少了不必要的轉(zhuǎn)發(fā)跳數(shù).

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

圖 1 消息的交換過程

1.2 相遇概率的計(jì)算與更新

Prophet(Probabilistic Routing in Intermittently Connected Networks)算法[8]利用車輛節(jié)點(diǎn)間相遇的歷史信息， 動(dòng)態(tài)地更新投遞預(yù)測(cè)概率.P(a,b)表示將消息從節(jié)點(diǎn)Va傳輸?shù)焦?jié)點(diǎn)Vb的投遞預(yù)測(cè)概率.假設(shè)節(jié)點(diǎn)Va要將消息msg傳輸?shù)侥康墓?jié)點(diǎn)Vd， 若節(jié)點(diǎn)Va與節(jié)點(diǎn)Vb相遇， 僅當(dāng)P(b,d)>P(a,d)時(shí)， 節(jié)點(diǎn)Va傳遞消息給節(jié)點(diǎn)Vb.P(a,b)的計(jì)算包括3個(gè)部分的更新， 具體如下：

相遇更新： 節(jié)點(diǎn)Va和節(jié)點(diǎn)Vb相遇頻繁， 則彼此都更新各自的投遞預(yù)測(cè)概率， 如式(1)所示

P(a,b)=P(a,b)old+(1-P(a,b)old)×Pinit,

(1)

式中：P(a,b)為本次的投遞預(yù)測(cè)概率；P(a,b)old為節(jié)點(diǎn)Va和節(jié)點(diǎn)Vb上次的投遞預(yù)測(cè)概率；Pinit為初始常量， 取值從0到1.

衰減更新： 如果一段時(shí)間內(nèi)， 節(jié)點(diǎn)Va和節(jié)點(diǎn)Vb沒有相遇， 則各自投遞預(yù)測(cè)概率通過式(2)進(jìn)行衰減更新

P(a,b)=P(a,b)old×γk,

(2)

式中：γ為衰減常數(shù)， 取值從0到1；k為節(jié)點(diǎn)Va和節(jié)點(diǎn)Vb最后一次衰減更新到目前的時(shí)間量化.

傳遞更新： 如果節(jié)點(diǎn)Va和節(jié)點(diǎn)Vb、 節(jié)點(diǎn)Vb和節(jié)點(diǎn)Vc相遇頻繁， 則說明節(jié)點(diǎn)Va和Vc相遇的概率也很高， 具有很高的傳遞消息可靠性. 傳遞更新如式(3)所示

P(a,c)=P(a,c)old+(1-P(a,c)old)×P(a,b)×

P(b,c)×β,

(3)

式中：β為放大常數(shù)， 表示傳遞性在投遞預(yù)測(cè)概率中的比重， 取值0到1.

2 MSSW算法

因?yàn)镻rophet算法中沒有對(duì)消息進(jìn)行調(diào)度和控制消息副本數(shù)量最大值， 消息的傳輸具有很大的隨機(jī)性， 哪個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)高， 消息就會(huì)轉(zhuǎn)發(fā)復(fù)制給優(yōu)先級(jí)高的節(jié)點(diǎn)， 因此， 網(wǎng)絡(luò)中會(huì)產(chǎn)生很多的副本， 隨著時(shí)間的增長， 副本數(shù)量越來越多， 會(huì)導(dǎo)致網(wǎng)絡(luò)堵塞.

本文提出MSSW算法， 采用增量平均的方法， 改進(jìn)投遞預(yù)測(cè)概率的相遇更新公式， 采用增強(qiáng)型的方法， 改進(jìn)投遞預(yù)測(cè)概率的衰減更新公式； 采用消息調(diào)度為動(dòng)態(tài)閾值區(qū)分的跳數(shù)優(yōu)先級(jí)排序和開銷優(yōu)先級(jí)排序機(jī)制； 同時(shí)將消息轉(zhuǎn)發(fā)模式分成噴射階段和等待階段， 初始化消息副本數(shù)量最大值為M， 在噴射階段， 以二叉樹的方式傳遞， 在等待階段， 以直接傳輸路由的方式傳遞； 并且加入ACK確認(rèn)機(jī)制. 這樣既提高了投遞率， 又減少了網(wǎng)絡(luò)中副本的冗余， 能夠很好地控制網(wǎng)絡(luò)中的副本數(shù)量， 具有較低的網(wǎng)絡(luò)開銷.

定義1： 增量平均相遇更新

節(jié)點(diǎn)相遇強(qiáng)度是節(jié)點(diǎn)之間建立連接后與下一次再次建立連接時(shí)的頻繁程度. 原來的prophet算法中沒有考慮節(jié)點(diǎn)間的相遇次數(shù)， 由于節(jié)點(diǎn)在車載容遲網(wǎng)絡(luò)中是不斷移動(dòng)的， 且移動(dòng)速度快， 不存在端到端穩(wěn)定的網(wǎng)絡(luò). 因此， 造成節(jié)點(diǎn)與其它節(jié)點(diǎn)的相遇次數(shù)可能不同， 如果節(jié)點(diǎn)與其它節(jié)點(diǎn)的相遇次數(shù)多， 說明這個(gè)節(jié)點(diǎn)活躍， 因此， 該節(jié)點(diǎn)的投遞預(yù)測(cè)概率就高. 在本文中， 相遇更新概率計(jì)算分為兩部分， 每一部分占50%， 一部分更新的是節(jié)點(diǎn)此刻的相遇概率更新， 另一部分受到節(jié)點(diǎn)歷史相遇次數(shù)的影響， 采用增量平均的方法， 加入增量平均偏置量， 每次遇到節(jié)點(diǎn)時(shí)， 概率值加1， 然后進(jìn)行歸一化處理， 所以， 原來的相遇概率更新式(1)變?yōu)槭?4)

P(a,b)=[P(a,b)old+(1-P(a,b)old)×Pinit]×0.5+

[(P(a,b)old+1)/(1+w)]×0.5,

(4)

式中：w為常量， 取值為1， 節(jié)點(diǎn)相遇越頻繁， 節(jié)點(diǎn)間越親密， 節(jié)點(diǎn)的投遞預(yù)測(cè)概率就越高.

定義2： 增強(qiáng)型衰減更新

由于傳統(tǒng)的prophet算法衰減更新的是節(jié)點(diǎn)此刻的衰減投遞預(yù)測(cè)概率， 可能存在路由抖動(dòng)的問題， 本文采用增強(qiáng)型的衰減更新方法， 在衰減更新的時(shí)候不只是更新此刻的投遞預(yù)測(cè)概率， 還將原投遞預(yù)測(cè)概率與衰減之后投遞預(yù)測(cè)概率求平均， 使得衰減投遞預(yù)測(cè)概率曲線更為平滑， 從而可以避免路由抖動(dòng). 所以原來的衰減更新概率式(2)變?yōu)槭?5)

(5)

2.1 消息調(diào)度

在傳統(tǒng)的Prophet算法中， 消息的傳輸具有隨機(jī)性， 沒有對(duì)網(wǎng)絡(luò)中的消息進(jìn)行調(diào)度， 可能會(huì)影響新消息的傳輸. 因此， MSSW算法中采用MaxProp算法[9]中的消息調(diào)度機(jī)制. MSSW算法的消息調(diào)度主要是管理通過動(dòng)態(tài)閾值區(qū)分的開銷優(yōu)先級(jí)隊(duì)列和跳數(shù)優(yōu)先級(jí)隊(duì)列. 跳數(shù)如果大于閾值， 會(huì)按照開銷進(jìn)行排序， 開銷越高， 優(yōu)先級(jí)越低； 跳數(shù)如果小于閾值， 會(huì)按照跳數(shù)進(jìn)行排序， 跳數(shù)越小， 優(yōu)先級(jí)越高. 通過消息調(diào)度， 發(fā)送和刪除消息都有了優(yōu)先級(jí)， 可以減少所需要的緩存空間， 提高投遞率. 消息調(diào)度示意圖如圖 2 所示.

圖 2 消息調(diào)度機(jī)制示意圖

2.1.1 動(dòng)態(tài)閾值

MSSW算法中使用動(dòng)態(tài)的方法獲取閾值Q， 閾值

(6)

式中：m為每次傳輸時(shí)所傳數(shù)據(jù)的位數(shù)；k為總緩存大小， 將m和k進(jìn)行比較獲取閾值Q， 得到閾值Q之后， 找出第一個(gè)溢出閾值的消息， 獲取它的跳數(shù)， 則該跳數(shù)即為跳數(shù)閾值Q.

2.1.2 消息傳輸開銷

2.2 消息轉(zhuǎn)發(fā)模式

在傳統(tǒng)Prophet算法中， 當(dāng)車輛節(jié)點(diǎn)遇到比自己優(yōu)先級(jí)高的節(jié)點(diǎn)就會(huì)復(fù)制副本給對(duì)方， 沒有對(duì)消息的副本數(shù)量設(shè)置上限， 在從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的傳輸過程中無法預(yù)估副本數(shù)量的多少， 網(wǎng)絡(luò)中的副本數(shù)量由源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間遇到優(yōu)先級(jí)高的節(jié)點(diǎn)數(shù)來決定. 如果網(wǎng)絡(luò)中的副本太多， 可能會(huì)產(chǎn)生網(wǎng)絡(luò)擁塞， 從而導(dǎo)致網(wǎng)絡(luò)的投遞率下降.

在MSSW算法中， 采用spray and wait[7]的傳遞方式， 將節(jié)點(diǎn)間消息的傳輸分為噴射階段和等待階段. 初始化消息副本數(shù)量最大值為M， 在噴射階段， 當(dāng)源節(jié)點(diǎn)遇到新的中繼節(jié)點(diǎn)的時(shí)候， 按照基于二叉樹的模式， 將消息副本的轉(zhuǎn)發(fā)任務(wù)分配給中繼節(jié)點(diǎn)， 接下來重復(fù)上述過程， 直到副本數(shù)量為1時(shí)， 消息如還沒有到達(dá)目的地， 則進(jìn)入等待階段， 消息將以直接傳輸路由的方式傳遞到目的節(jié)點(diǎn). 該轉(zhuǎn)發(fā)模式既有效地控制了網(wǎng)絡(luò)中的副本數(shù)量， 又實(shí)現(xiàn)了多路徑并行傳輸轉(zhuǎn)發(fā)， 降低了網(wǎng)絡(luò)中的消息冗余， 提高了傳輸效率.

圖 3 消息副本轉(zhuǎn)發(fā)示意圖

2.3 ACK確認(rèn)機(jī)制

因?yàn)榫W(wǎng)絡(luò)中有已成功投遞的消息還在網(wǎng)絡(luò)緩存中存在的問題， 所以， 在MSSW算法中加入ACK確認(rèn)機(jī)制. 在MSSW算法中， 每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)消息確認(rèn)列表， 用來維護(hù)已經(jīng)成功達(dá)到目的地的消息. 已經(jīng)成功到達(dá)目的地的消息ID會(huì)添加到消息確認(rèn)列表中. 當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)， 它們會(huì)交換彼此的消息確認(rèn)列表， 將已成功傳輸?shù)南淖约旱木彺嬷袆h除， 從而釋放網(wǎng)絡(luò)中的緩存， 從根本上減少網(wǎng)絡(luò)擁塞的問題.

3 實(shí)驗(yàn)仿真分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

基于對(duì)MSSW算法性能進(jìn)行分析， 仿真采用了6組數(shù)量相等的車輛節(jié)點(diǎn)， 每組40個(gè)車輛節(jié)點(diǎn)， 在one仿真軟件進(jìn)行實(shí)現(xiàn). 將MSSW與Prophet， Direct Delivery， Epidemic和First Contact在相同實(shí)驗(yàn)環(huán)境下進(jìn)行對(duì)比， 并且對(duì)MSSW算法中加入ACK確認(rèn)機(jī)制和不加ACK確認(rèn)機(jī)制兩種情況下進(jìn)行了性能對(duì)比. 仿真參數(shù)如表 1 所示.

表 1 仿真參數(shù)設(shè)置

3.2 評(píng)價(jià)指標(biāo)

3.2.1 投遞率

投遞率等于成功投遞到目的節(jié)點(diǎn)的消息數(shù)量除以網(wǎng)絡(luò)中源節(jié)點(diǎn)產(chǎn)生的消息數(shù)量. 如式(7)所示

(7)

式中：delivered為成功投遞到目的節(jié)點(diǎn)的消息數(shù)量；created為在源節(jié)點(diǎn)處生成的消息數(shù)量.

3.2.2 網(wǎng)絡(luò)開銷

網(wǎng)絡(luò)開銷等于冗余轉(zhuǎn)發(fā)跳數(shù)除以成功投遞到目的節(jié)點(diǎn)的消息數(shù)量. 如式(8)所示

(8)

式中：relayed為消息總轉(zhuǎn)發(fā)跳數(shù)；delivered為成功投遞到目的節(jié)點(diǎn)的消息數(shù)量.

3.2.3 平均時(shí)延

平均時(shí)延等于全部消息從源節(jié)點(diǎn)產(chǎn)生到目的節(jié)點(diǎn)接收到該消息所花費(fèi)的時(shí)間除以總的投遞成功的消息數(shù)量. 如式(9)所示

(9)

式中：tmg和tms分別為目的節(jié)點(diǎn)接收消息和源節(jié)點(diǎn)處生成消息的時(shí)刻；n為成功投遞到目的節(jié)點(diǎn)的消息數(shù)量.

3.3 仿真結(jié)果分析

3.3.1 網(wǎng)絡(luò)中緩存的性能

如圖 4 所示， MSSW的投遞率相比Prophet平均提高了115.29%； 相比Direct Delivery平均提高了134.40%； 相比Epidemic平均提高了105.50%； 相比First Contact平均提高了153.72%.

圖 4 不同緩存的投遞率

如圖 5 所示， MSSW的網(wǎng)絡(luò)開銷相比Prophet平均降低了96.85%； 相比Epidemic平均降低了97.16%； 相比First Contact平均 降低了93.75%. 網(wǎng)絡(luò)開銷能夠很好地維持在平均 5.79的水平， 表現(xiàn)良好， 具有很好的穩(wěn)定性.

圖 5 不同緩存的網(wǎng)絡(luò)開銷

如圖 6 所示， MSSW的平均時(shí)延相比Direct Delivery和First Contact平均分別降低了 31.06% 和32.52%， 雖然MSSW的平均時(shí)延略高于Prophet和Epidemic兩種路由算法， 這是由于MSSW算法改進(jìn)了投遞預(yù)測(cè)概率的公式， 考慮更加全面， 并且在消息傳輸時(shí)采用消息調(diào)度機(jī)制， 傳輸和刪除消息都具有優(yōu)先級(jí)， 分為噴射和等待階段傳輸消息， 保證消息的多路徑轉(zhuǎn)發(fā)， 并且設(shè)置初始副本數(shù)量， 將投遞預(yù)測(cè)概率作為轉(zhuǎn)發(fā)依據(jù)導(dǎo)致的結(jié)果， 避免浪費(fèi)網(wǎng)絡(luò)資源， 降低了網(wǎng)絡(luò)開銷.

圖 6 不同緩存的平均延時(shí)

3.3.2 網(wǎng)絡(luò)中消息生存周期的性能

如圖 7 所示， MSSW的投遞率相比Prophet平均提高了163.73%； 相比Direct Delivery平均提高了151.76%； 相比Epidemic平均提高了 161.55%； 相比First Contact平均提高了 218.48%.

圖 7 不同生存周期的投遞率

如圖 8 所示， MSSW的網(wǎng)絡(luò)開銷相比Prophet平均降低了97.10%； 相比Epidemic平均降低了97.42%； 相比First Contact平均降低了 94.17%. 網(wǎng)絡(luò)開銷能夠很好地維持在平均7.84的水平， 表現(xiàn)良好， 具有很好的穩(wěn)定性.

圖 8 不同生存周期的網(wǎng)絡(luò)開銷

如圖 9 所示， MSSW的平均時(shí)延相比Direct Delivery和First Contact平均分別降低了 20.77% 和17.24%， 雖然MSSW的平均時(shí)延略高于Prophet和Epidemic兩種路由算法， 但這是由于MSSW算法本身設(shè)置的結(jié)果.

圖 9 不同生存周期的平均時(shí)延

3.3.3 網(wǎng)絡(luò)中仿真時(shí)間的性能

如圖 10 所示， MSSW的投遞率相比Prophet平均提高了260.64%； 相比Direct Delivery平均提高了120.87%； 相比Epidemic平均提高了265.83%； 相比First Contact平均提高了 189.68%.

圖 10 不同仿真時(shí)間的投遞率

如圖 11 所示， MSSW的網(wǎng)絡(luò)開銷相比Prophet平均降低了97.87%； 相比Epidemic平均降低了98.12%； 相比First Contact平均降低了93.71%； MSSW的網(wǎng)絡(luò)開銷能夠很好地維持在平均6.98的水平， 表現(xiàn)良好， 具有很好的穩(wěn)定性.

圖 11 不同仿真時(shí)間的網(wǎng)絡(luò)開銷

如圖 12 所示， MSSW的平均時(shí)延相比Direct Delivery和First Contact平均分別降低了 27.88% 和21.60%， 雖然MSSW的平均時(shí)延略高于Prophet和Epidemic兩種路由算法， 但這是由于MSSW算法本身設(shè)置的結(jié)果.

圖 12 不同仿真時(shí)間的平均時(shí)延

3.3.4 MSSW算法中是否加入ACK確認(rèn)機(jī)制的性能對(duì)比

如圖 13 所示， 加入ACK確認(rèn)機(jī)制的MSSW算法在不同緩存下投遞率比不加入ACK確認(rèn)機(jī)制的MSSW算法平均提高了5.67%； 如圖 14 所示， 網(wǎng)絡(luò)開銷平均降低了6.42%； 如圖 15 所示， 平均時(shí)延整體平均略高于不加入ACK確認(rèn)機(jī)制的MSSW算法， 這是由于加入ACK確認(rèn)機(jī)制的MSSW算法將已到達(dá)目的節(jié)點(diǎn)的消息確認(rèn)和刪除， 避免了消息在節(jié)點(diǎn)間重復(fù)轉(zhuǎn)發(fā)， 減少了不必要的轉(zhuǎn)發(fā)跳數(shù).

圖 13 不同緩存的投遞率

圖 14 不同緩存的網(wǎng)絡(luò)開銷

圖 15 不同緩存的平均延時(shí)

如圖 16 所示， 加入ACK確認(rèn)機(jī)制的MSSW算法在不同生存周期下投遞率比不加入ACK確認(rèn)機(jī)制的MSSW算法平均提高了16.14%； 如圖 17 所示， 網(wǎng)絡(luò)開銷平均降低了9.56%； 如圖 18 所示， 平均時(shí)延略高于不加入ACK確認(rèn)機(jī)制的MSSW算法.

圖 16 不同生存周期的投遞率

圖 17 不同生存周期的網(wǎng)絡(luò)開銷

圖 18 不同生存周期的平均時(shí)延

如圖 19 所示， 加入ACK確認(rèn)機(jī)制的MSSW算法在不同仿真時(shí)間下投遞率比不加入ACK確認(rèn)機(jī)制的MSSW算法平均提高了20.47%； 如圖 20 所示， 網(wǎng)絡(luò)開銷平均降低了11.74%； 如圖 21 所示， 平均時(shí)延略高于不加入ACK確認(rèn)機(jī)制的MSSW算法.

圖 19 不同仿真時(shí)間的投遞率

圖 20 不同仿真時(shí)間的網(wǎng)絡(luò)開銷

圖 21 不同仿真時(shí)間的平均時(shí)延

綜上所述， MSSW在不同緩存、 不同生存周期和不同仿真時(shí)間下， MSSW相比其他4種路由算法均表現(xiàn)出較高的投遞率和非常低的網(wǎng)絡(luò)開銷， 并且MSSW的網(wǎng)絡(luò)開銷能夠控制在相對(duì)穩(wěn)定的水平， 這驗(yàn)證了MSSW改進(jìn)了投遞預(yù)測(cè)概率更新公式， 并以投遞預(yù)測(cè)概率為轉(zhuǎn)發(fā)依據(jù)的有效性， 以及對(duì)消息調(diào)度傳輸?shù)挠行? 控制消息副本數(shù)量以及采用二叉樹的方式傳輸消息， 保證了消息的多路徑轉(zhuǎn)發(fā)的有效性. 加入ACK確認(rèn)機(jī)制的有效性. 雖然MSSW的平均時(shí)延整體上略高于Prophet和Epidemic兩種路由算法， 但是用少量的平均時(shí)延來換取投遞率和網(wǎng)絡(luò)開銷性能上的提升是值得的.

4 結(jié) 語

本文針對(duì)車載容遲網(wǎng)絡(luò)消息傳輸路徑難建立、 間斷性的特點(diǎn)， 提出了一種基于消息調(diào)度和噴射等待的車載容遲網(wǎng)絡(luò)路由算法MSSW， 并在仿真工具ONE中進(jìn)行了仿真實(shí)現(xiàn). 該算法采用增量平均的方法， 改進(jìn)了投遞預(yù)測(cè)概率的相遇更新公式， 采用增強(qiáng)型的方法改進(jìn)了投遞預(yù)測(cè)概率的衰減更新公式并以投遞預(yù)測(cè)概率作為節(jié)點(diǎn)轉(zhuǎn)發(fā)依據(jù)， 根據(jù)消息優(yōu)先級(jí)排序， 使得傳輸消息和緩存區(qū)滿時(shí)刪除消息有序進(jìn)行， 有效緩解了緩存區(qū)的負(fù)載； 控制消息副本數(shù)量以及采用二叉樹的方式傳輸消息， 在限制副本數(shù)量的同時(shí)保證了消息的多路徑轉(zhuǎn)發(fā)； 加入ACK確認(rèn)機(jī)制， 刪除了網(wǎng)絡(luò)中冗余的緩存. 結(jié)果表明， MSSW算法能提高投遞率和降低網(wǎng)絡(luò)開銷， 有效地控制平均時(shí)延.