一種基于軌跡預測的機會網(wǎng)絡路由協(xié)議

王桐，單欣，鄭欣蕊

1. 哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001 2. 加拿大多倫多大學 機械與工業(yè)工程系，安大略 多倫多 M5S 1A1

機會網(wǎng)絡[1]是一種可以允許消息源和目的節(jié)點之間的通信鏈路不完整，甚至不具備通信鏈路的自組織網(wǎng)絡。其與傳統(tǒng)的TCP/IP 網(wǎng)絡相比不同的是，ONs 可以解決由于缺乏基礎設施而引起的通信鏈路頻繁斷開的通信問題。ONs 采用“存儲?攜帶?轉(zhuǎn)發(fā)”的消息傳輸模式，利用節(jié)點移動相遇中繼消息，直到與目的節(jié)點相遇。

消息傳遞是機會網(wǎng)絡研究的熱門問題之一，較高的消息傳遞成功率建立在為每個消息找到最佳的中繼節(jié)點之上。近年來，越來越多的研究人員提出了各類ONs 路由算法，例如基于拓撲的路由協(xié)議：Epidemic[2]、Spray and Wait[3]，這類路由協(xié)議策略比較簡單，選擇中繼節(jié)點的盲目性較強，實現(xiàn)較高傳遞成功率的代價是較低的資源利用率；為避免盲目選擇中繼節(jié)點，提出基于社會性的路由協(xié)議：SimBet[4]、EBR[5]，這類路由協(xié)議結(jié)合節(jié)點的社會屬性選擇中繼節(jié)點，具有減少網(wǎng)絡資源消耗，限制消息副本分發(fā)等優(yōu)點，但同時增大了消息的傳輸延時；針對現(xiàn)有大多數(shù)協(xié)議都忽視的消息傳遞過程中的能耗問題，提出基于能量效用轉(zhuǎn)發(fā)策略的路由協(xié)議：EA-Prophet[6]、SPARE[7]，這類路由協(xié)議根據(jù)節(jié)點的剩余能量選擇中繼節(jié)點，以實現(xiàn)消息的有效傳遞，但存在著降低網(wǎng)絡開銷的同時卻增加了傳輸延遲的風險；基于地理的路由協(xié)議：GeoDTN[8]、GeoSpray[9]，這類路由協(xié)議考慮到在不同的地理環(huán)境中，節(jié)點移動所表現(xiàn)的不同特征，采用最短路徑的方式選擇中繼節(jié)點，但容易受到局部最大值的影響，從而降低成功率；基于軌跡的路由協(xié)議：TBF[10]、TDOR[11]，這類路由協(xié)議根據(jù)消息傳遞路線與節(jié)點位置的相關(guān)性選擇中繼節(jié)點，但通常需要在消息傳遞開始前獲得消息傳遞路線，且消息傳遞性能受傳遞路線形狀影響較大，針對該問題，本文提出通過歷史數(shù)據(jù)與節(jié)點的社會性，預測節(jié)點移動軌跡選擇中繼節(jié)點，從而確定消息傳遞路線的方法，仿真結(jié)果表明了算法的有效性。

1 軌跡分析

在對節(jié)點軌跡進行分析時，可以把節(jié)點在不同時刻所處的位置看作是隨機變量L，根據(jù)前k(0≤k

表1 節(jié)點軌跡分析的符號定義

針對某一節(jié)點i，其歷史軌跡集可以由一系列的位置點表示成 Ti={L1,L2,···,Ln}，分別對應第1 ～n個時刻節(jié)點的位置。由此，我們可以得到節(jié)點i在 位置 Lm的概率以及隨機變量 L的熵為

在當節(jié)點i的前一個位置 Lm?1已知的情況下，節(jié)點在位置 Lm的 概率以及隨機變量 L的條件熵為

以此類推，可以得到在已知節(jié)點 i的 前 k個位置的情況下，節(jié)點在隨機變量 L的條件熵為：H(L|Lm?1,Lm?2,···,Lm?k)。

利用所采集的2015 年12 月1 日—2015 年12 月31 日北京市500 輛出租車軌跡數(shù)據(jù)集，通過上述方法分析節(jié)點移動的可預測性。得到如圖1 所示的仿真結(jié)果。

圖1 軌跡分析仿真

我們知道隨機變量的條件熵越小，則該隨機變量的不確定性越小。本文中，節(jié)點隨機變量 L的條件熵越小，則說明節(jié)點位置的不確定性越小，即節(jié)點軌跡的可預測性越強。如圖1 所示，隨機變 量 L 的 條 件 熵 H(L|Lm?1,Lm?2,···,Lm?k) 的 值 隨 k的增加而減小，并逐漸趨于穩(wěn)定，說明當已知節(jié)點之前的位置狀態(tài)時，可以更準確地預測出節(jié)點的下一位置。

2 軌跡預測

針對城市中主干道路的分布，將城市地圖中的路口、路段以網(wǎng)格的形式呈現(xiàn)，將道路網(wǎng)絡建模為G =〈C,S〉 ， 其中C ,S分別表示路口和路段的集合。

圖2 為軌跡預測流程，通過分析節(jié)點的歷史軌跡數(shù)據(jù)，劃分節(jié)點的單位活動區(qū)域，計算節(jié)點移動到不同位置的概率，并分別提取出不同節(jié)點的興趣區(qū)域分布情況，從而根據(jù)節(jié)點當前及上一刻的位置預測節(jié)點下一時間單元的位置，由此串聯(lián)成一段節(jié)點移動軌跡。

圖2 軌跡預測流程

2.1 單位活動區(qū)域劃分

節(jié)點的軌跡數(shù)據(jù)可以整理為包含N個位置、速度和時間信息的集合

式中： (si,ci)表 示節(jié)點的位置信息，即在路段 si上，并向著路口 ci的 方向； (vi,ti)表示節(jié)點的速度和時間信息。時間增量 ?t=tn?tn?1,0 ≤n ≤N ?1可以看作一個預測周期，即一個時間單元。

定義單位活動區(qū)域為以該節(jié)點在一個預測時間單元內(nèi)可以移動到的位置為邊界的區(qū)域。如圖3(a)所示。實際上由于節(jié)點移動時具有不同的速度，該區(qū)域應呈現(xiàn)不規(guī)則形狀，為計算簡單，本文將節(jié)點在短時間內(nèi)的運動近似看作是勻速運動，則該區(qū)域可看作是一個以該節(jié)點當前位置為圓心的圓形，且半徑為該節(jié)點在一個預測時間單元內(nèi)的移動距離，如圖3(b)所示。

在道路網(wǎng)絡上，單位活動區(qū)域所覆蓋的范圍可以由 G′=〈C′,S′〉表示，如圖4 中的陰影部分所示。單位活動區(qū)域與路段相交的點稱為出口點，由e表示。節(jié)點從當前位置Li-1到達任一出口點的軌跡可以看作是一個軌跡預測段，如Li?1→c13→e3。

圖3 單位活動區(qū)域

圖4 模擬城市道路網(wǎng)絡

2.2 路徑選擇

在軌跡分析中可以得到結(jié)論：當已知節(jié)點的前2 個位置狀態(tài)時，可以更準確地預測出節(jié)點的下一位置。因此，考慮節(jié)點的前2 個位置 Li?2、 Li?1，從而得到節(jié)點的移動方向 Li?2→Li?1，進而將Gˊ縮小，得到幾種可能軌跡預測段，如圖5。

圖5 軌跡預測段的可能情況

2.3 概率計算

根據(jù)節(jié)點的長期歷史軌跡數(shù)據(jù)推測出不同節(jié)點的興趣點，并以R為半徑劃分成不同的興趣點區(qū)域，如圖6 所示。并為不同的興趣點區(qū)域設定不同的移動概率 PI，即節(jié)點移動進入到興趣點區(qū)域的概率。

圖6 興趣點區(qū)域分布

定義節(jié)點興趣因子I ，表示節(jié)點單位活動區(qū)域與路段相交的出口點是否落入該節(jié)點的興趣點區(qū)域中。

在實際場景中，節(jié)點的軌跡與日常生活息息相關(guān)。在不同時段內(nèi)，軌跡的數(shù)量和位置分布有很大不同，因此，節(jié)點移動軌跡的預測考慮時間因素很有必要。本文將每天均勻劃分為N=4 個時段，并分別計算4 個時段內(nèi)的概率轉(zhuǎn)移矩陣M(S,tN)，以達到最佳的軌跡預測效果。

式中：tN表示4 個時段，N=1,2,3,4；概率 P(Sn|S0)表示節(jié)點由路段S0到路段Sn的概率，可由在歷史軌跡數(shù)據(jù)中提取的該節(jié)點在該路段處出現(xiàn)的次數(shù)計算：

式中： U0表示在歷史軌跡數(shù)據(jù)中，該節(jié)點出現(xiàn)在路段S0的次數(shù)； U0,n表示在歷史軌跡數(shù)據(jù)中，該節(jié)點前一路段狀態(tài)為S0，下一路段狀態(tài)為Sn的次數(shù)，即節(jié)點經(jīng)歷軌跡段 S0→Sn的次數(shù)。

定義預測參數(shù) Y表示該路段是節(jié)點下一路段的可能性， Y越大，說明節(jié)點在下一時間單元到達該路段的可能性越大，本文選取具有 Ymax的路段作為一個預測軌跡段的終點。

式中：Sc表示當前時刻節(jié)點所在的路段，即圖3 中的S11，Se表示出口點所在的路段，即圖3 中出口點e1、e2、e3、e4、e5分 別 所 在 的 路 段S14、S19、S20、S21、S17。分別求]出每個Se的 Y 值，則Ymax=max[YS19,YS20,YS21,YS17

3 仿真結(jié)果及分析

3.1 仿真環(huán)境

本文基于機會網(wǎng)絡的常用仿真工具opportunistic network environment[13](ONE)仿真平臺，選用Helsinki 道路地圖驗證分析TPBOR 算法的性能。在仿真過程中，節(jié)點采用最短路徑移動模型，同時運行了SimBet、Prophet、EA-Prophet、TDOR和TPBOR 算法，用于對比分析。各項參數(shù)設置見表2。

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

3.2 結(jié)果分析

本文主要從投遞率、網(wǎng)絡開銷和平均傳輸延遲3 個方面對比各個算法傳輸性能的優(yōu)劣。投遞率指仿真過程中，目的節(jié)點接收的消息總數(shù)與網(wǎng)絡中創(chuàng)建的消息總數(shù)的比值。網(wǎng)絡開銷指未成功傳輸?shù)南⒏北緮?shù)與成功傳輸?shù)南⒏北緮?shù)的比值。平均傳輸延遲指消息從創(chuàng)建到成功被目的節(jié)點接收的時間。仿真中，分別從不同移動節(jié)點數(shù)量、不同節(jié)點緩存大小和不同消息生存周期3 個方面分析對算法性能的影響。

3.2.1 節(jié)點數(shù)量對算法性能的影響

由圖7 可以看出，隨著節(jié)點數(shù)量的增加，除Prophet 協(xié)議外，其他協(xié)議的傳遞率都有所提高，同時減少了平均傳輸延遲，這是因為節(jié)點數(shù)量增加，使網(wǎng)絡密度變大，節(jié)點間相遇的概率變大，所以成功傳遞的消息副本數(shù)也隨之增加，且傳遞的延遲降低。而Prophet 協(xié)議不限制消息副本數(shù)，當節(jié)點數(shù)量增加時，會導致部分消息副本被丟棄，因此傳遞率下降并大幅度增加網(wǎng)絡開銷。

對比其他算法，TPBOR 協(xié)議實現(xiàn)了較低的平均傳輸延遲和較高的傳遞率，說明TPBOR 協(xié)議適應網(wǎng)絡密度變化的能力更強。

圖7 節(jié)點數(shù)量對路由協(xié)議的影響

3.2.2 節(jié)點緩存大小對算法性能的影響

由圖8 可知，隨著節(jié)點緩存的增加，Prophet協(xié)議的傳遞率呈現(xiàn)上升的趨勢，因為節(jié)點緩存的增加使得Prophet 協(xié)議的緩存能力增強，節(jié)點可以儲存更多的消息副本，從而提高了傳遞率。SimBet協(xié)議的傳遞率在節(jié)點緩存達到20 MB 后趨于穩(wěn)定，是因為在稀疏的網(wǎng)絡環(huán)境中，節(jié)點生成的消息副本數(shù)有限，所以繼續(xù)增加節(jié)點緩存大小對消息的成功傳遞影響不大。

圖8 節(jié)點緩存對路由協(xié)議的影響

在TPBOR、EA-Prophet 協(xié)議中，網(wǎng)絡初始化階段節(jié)點就已經(jīng)創(chuàng)建出多個消息副本，所以節(jié)點緩存大小并不會明顯影響節(jié)點能夠攜帶的消息副本數(shù)，因此對這2 種協(xié)議的影響不大。TDOR 屬于單副本協(xié)議，在路由過程中不再生成新的消息副本，所以節(jié)點緩存大小對該協(xié)議的性能沒有影響。

通過以上對比可以得出，TPBOR 協(xié)議能夠穩(wěn)定保持較高傳遞率和較低的平均傳輸延遲，說明TPBOR 協(xié)議對不同節(jié)點的適應能力更強。

3.2.3 不同消息生存周期對算法性能的影響

由圖9 可得，SimBet 和TDOR 協(xié)議的傳遞率隨消息生存周期的增加而增加，因為消息生存周期的增加可以使消息有更大的機會到達目的節(jié)點，從而提高了傳遞率，但同時也增大了平均傳輸延遲。在EA-Prophet 和TPBOR 協(xié)議中，中繼節(jié)點的選擇更為明確，所以部分生存周期較小的消息副本會被直接丟棄，因此消息生存周期對這2種協(xié)議性能的影響不大。

圖9 消息生存周期對路由協(xié)議的影響

對比其他算法，TPBOR 協(xié)議實現(xiàn)了較低的平均傳輸延遲和較高的傳遞率，說明TPBOR 協(xié)議對不同消息的適應能力更強，TPBOR 協(xié)議應用范圍更廣。

4 結(jié)論

本文提出一種基于軌跡預測的機會網(wǎng)絡通信協(xié)議，通過ONE 仿真平臺，利用真實地圖對路由算法進行實驗仿真，以傳遞率、網(wǎng)絡開銷和平均傳輸延遲為評價指標。仿真結(jié)果說明對比其他各類型路由協(xié)議，基于軌跡預測的路由協(xié)議能夠明顯提高消息傳遞的成功率，同時降低平均傳輸延遲，但相對增加了網(wǎng)絡開銷，在一定程度上造成網(wǎng)絡負載過重。未來可以針對網(wǎng)絡開銷對該協(xié)議進行優(yōu)化。