一種基于軌跡預(yù)測(cè)的機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議

王桐，單欣，鄭欣蕊

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

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

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

1 軌跡分析

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

表1 節(jié)點(diǎn)軌跡分析的符號(hào)定義

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

在當(dāng)節(jié)點(diǎn)i的前一個(gè)位置 Lm?1已知的情況下，節(jié)點(diǎn)在位置 Lm的 概率以及隨機(jī)變量 L的條件熵為

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

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

圖1 軌跡分析仿真

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

2 軌跡預(yù)測(cè)

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

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

圖2 軌跡預(yù)測(cè)流程

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

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

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

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

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

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

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

2.2 路徑選擇

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

圖5 軌跡預(yù)測(cè)段的可能情況

2.3 概率計(jì)算

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

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

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

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

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

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

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

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

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

3.1 仿真環(huán)境

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

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

3.2 結(jié)果分析

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

3.2.1 節(jié)點(diǎn)數(shù)量對(duì)算法性能的影響

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

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

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

3.2.2 節(jié)點(diǎn)緩存大小對(duì)算法性能的影響

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

圖8 節(jié)點(diǎn)緩存對(duì)路由協(xié)議的影響

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

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

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

由圖9 可得，SimBet 和TDOR 協(xié)議的傳遞率隨消息生存周期的增加而增加，因?yàn)橄⑸嬷芷诘脑黾涌梢允瓜⒂懈蟮臋C(jī)會(huì)到達(dá)目的節(jié)點(diǎn)，從而提高了傳遞率，但同時(shí)也增大了平均傳輸延遲。在EA-Prophet 和TPBOR 協(xié)議中，中繼節(jié)點(diǎn)的選擇更為明確，所以部分生存周期較小的消息副本會(huì)被直接丟棄，因此消息生存周期對(duì)這2種協(xié)議性能的影響不大。

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

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

4 結(jié)論

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