一種基于軌跡預測的機會網絡路由協議

王桐，單欣，鄭欣蕊

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

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

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

1 軌跡分析

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

表1 節點軌跡分析的符號定義

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

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

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

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

圖1 軌跡分析仿真

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

2 軌跡預測

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

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

圖2 軌跡預測流程

2.1 單位活動區域劃分

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

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

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

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

圖3 單位活動區域

圖4 模擬城市道路網絡

2.2 路徑選擇

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

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

2.3 概率計算

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

圖6 興趣點區域分布

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

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

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

式中： U0表示在歷史軌跡數據中，該節點出現在路段S0的次數； U0,n表示在歷史軌跡數據中，該節點前一路段狀態為S0，下一路段狀態為Sn的次數，即節點經歷軌跡段 S0→Sn的次數。

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

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

3 仿真結果及分析

3.1 仿真環境

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

表2 仿真參數設置

3.2 結果分析

本文主要從投遞率、網絡開銷和平均傳輸延遲3 個方面對比各個算法傳輸性能的優劣。投遞率指仿真過程中，目的節點接收的消息總數與網絡中創建的消息總數的比值。網絡開銷指未成功傳輸的消息副本數與成功傳輸的消息副本數的比值。平均傳輸延遲指消息從創建到成功被目的節點接收的時間。仿真中，分別從不同移動節點數量、不同節點緩存大小和不同消息生存周期3 個方面分析對算法性能的影響。

3.2.1 節點數量對算法性能的影響

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

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

圖7 節點數量對路由協議的影響

3.2.2 節點緩存大小對算法性能的影響

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

圖8 節點緩存對路由協議的影響

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

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

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

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

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

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

4 結論

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