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

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

0 引 言

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

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

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

1) 采用增量平均的方法， 改進投遞預測概率的相遇更新公式， 采用增強型的方法， 改進衰減更新的公式；

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

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

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

1 系統(tǒng)模型

1.1 網(wǎng)絡模型

圖 1 消息的交換過程

1.2 相遇概率的計算與更新

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

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

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

(1)

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

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

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

(2)

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

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

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

P(b,c)×β,

(3)

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

2 MSSW算法

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

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

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

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

定義2： 增強型衰減更新

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

(5)

2.1 消息調(diào)度

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

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

2.1.1 動態(tài)閾值

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

(6)

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

2.1.2 消息傳輸開銷

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

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

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

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

2.3 ACK確認機制

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

3 實驗仿真分析

3.1 實驗參數(shù)設置

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

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

3.2 評價指標

3.2.1 投遞率

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

(7)

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

3.2.2 網(wǎng)絡開銷

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

(8)

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

3.2.3 平均時延

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

(9)

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

3.3 仿真結(jié)果分析

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

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

圖 4 不同緩存的投遞率

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

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

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

圖 6 不同緩存的平均延時

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

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

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

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

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

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

圖 9 不同生存周期的平均時延

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

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

圖 10 不同仿真時間的投遞率

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

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

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

圖 12 不同仿真時間的平均時延

3.3.4 MSSW算法中是否加入ACK確認機制的性能對比

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

圖 13 不同緩存的投遞率

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

圖 15 不同緩存的平均延時

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

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

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

圖 18 不同生存周期的平均時延

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

圖 19 不同仿真時間的投遞率

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

圖 21 不同仿真時間的平均時延

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

4 結(jié) 語

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