一種基于歷史信息的社會機會網絡路由算法

楊云輝，王小明，張立臣，劉 森，林亞光

(1.陜西師范大學 現代教學技術教育部重點實驗室，陜西 西安 710119；2.陜西師范大學 計算機科學學院,陜西 西安 710119)

0 引 言

現如今隨著短距離無線通訊技術的飛速發展以及移動手持智能設備的大量普及，兩者之間的結合開始變得越來越成熟，移動無線網絡逐漸被人們所接受，移動手持智能設備所具有的功能也越來越豐富，這些設備附帶的功能不僅滿足了人們的日常需求，也改變了傳統移動網絡的通信方式。手持這些移動智能設備，利用設備附帶的Wi-Fi或藍牙接口使設備之間組成機會網絡，通過這些設備實現消息數據的傳輸服務。這種結合了人類活動的社會屬性和物理運動的移動屬性的社會機會網絡[1](social opportunistic networks)受到了研究學者的廣泛關注。由于該網絡不需要基礎通訊設施、網絡部署成本低、組網便捷，在一些網絡環境極端的條件下往往能發揮出較好的優勢，迎合了目前大量的區域性無線通信需求。相關的科研工作者利用社會機會網絡的網絡特性，已經應用在多個領域，例如極端環境下的自組織通訊網絡[2-4]、災后緊急救援網絡[5]、校園環境下的知識共享網絡[6]等等。社會機會網絡不僅彌補了有線網絡的缺陷，同時也給無線自組織網絡帶來了新的挑戰和機遇。

社會機會網絡以人為中心，人們的移動行為和社會特性影響著整個網絡路由的通信質量，相關學者利用網絡中節點的社會性[7-9]，提出了許多改善路由投遞性能的算法。例如，Prophet路由協議[10]利用時隙滑動窗口機制維護節點間相遇的細粒度實時統計數據，定義三個概率更新公式，通過概率更新公式來預測節點間的相遇概率，從而進行轉發決策，優化消息的轉發路徑。文獻[11-12]根據節點不同的社會屬性將節點進行社區劃分，同屬于一個社區的節點間相遇比較頻繁，由此為基礎提出了一種基于社區的路由策略。文獻[13]介紹了一種新的衡量標準—節點之間友誼的質量，據此周期性更新節點間的友誼關系，從而提出一種基于關系友好度的機會路由來進行轉發決策。文獻[14]通過社會網絡中節點的興趣屬性，將網絡中的節點劃分為不同的興趣組，不僅提高了社會機會網絡的路由效率，而且保護了節點的隱私。以上這些算法雖然在一定程度上考慮了節點的社會屬性，提高了網絡路由的通訊性能，但是由于其忽略了社會機會網絡中節點的移動規律和活躍度，未能考慮節點間相遇的歷史信息對節點通訊性能的影響，因此仍需要進行進一步的研究。

文中以節點的歷史相遇信息作為參考，根據其歷史相遇記錄，計算節點間相對社會關系強弱和其平均相遇持續時間，并分析其對路由性能的影響。然后，根據節點在網絡中的有效轉發能力，提出了一種基于歷史相遇信息的路由算法。在該算法中，消息始終轉發給與目的節點相遇概率更大且平均相遇持續時間更長的節點，直至消息達到目的節點或者消息失效。最后，通過仿真實驗對該路由算法進行驗證。

1 網絡模型

在這種以人為載體，通過手持移動智能設備不斷移動形成的通信機會來傳輸消息數據的社會機會網絡中，節點設備活動的區域和規律受到人類社會行為的影響，經常表現出“小世界”的現象并且具有一定的規律性，符合人類的日常生活習慣。如果記錄一個人長期的歷史軌跡，就可以得到這個人的生活規律，同理如果記錄網絡中所有節點的一個長期時間序列軌跡，就可以得到整個網絡的時間序列拓撲變化情況，從而根據節點的移動規律優化消息轉發策略。

為了刻畫社會機會網絡的網絡拓撲變化，便于分析網絡中節點間的關系，將有限的時間序列T以τ為時間單位劃分為l個時間間隔，則第m個時間間隔為τm(m≤l)，網絡中節點集合為V={v1,v2,…,vn}。在任意時刻t∈T，網絡的靜態拓撲圖可以表示為G=(V,E)，其中G為有向帶權圖，E為定義在G上的邊集。將τm內節點vi同節點vj的相遇次數表示為E(i,j)(τm)，則在時間間隔τm內，節點vi同其他節點相遇的次數Ni(τm)可表示為：

(1)

定義1(節點活躍度)：節點活躍度是指社會機會網絡中的節點在時間間隔τ內與不同節點相遇的頻繁程度。節點的活躍度越高，表示當前節點在整個社會機會網絡中與其他不同節點的聯系越密切，同時該節點的消息轉發效率也越高。假設在時間間隔τ內，節點vi相遇過的節點集合可表示為S={v1,v2,…,vn}，其中Si(τm-1)指在時間間隔τm-1內節點vi同其他相遇節點的集合，Si(τm)指在時間間隔τm內節點vi同其他節點相遇的集合，則節點vi在時間間隔τm內的活躍度Di(τm)可以表示為：

(2)

2 基于歷史相遇信息的路由算法

基于歷史相遇信息的路由算法遵循人類的常規思維，既要盡可能使消息在有效生存期內成功投遞給目的節點，又要保證消息的完整傳輸，避免由于節點間相遇持續時間過短，造成通信機會的浪費。

2.1 有效轉發能力計算

對一個人來說，他同朋友之間見面比較頻繁，同陌生人見面稀少，見面的頻率能夠反映他同此人的人際關系的強弱。同理在社會機會網絡中，可以根據節點間的歷史相遇次數，用以衡量節點間的社會關系強弱。節點間相遇的次數越多，表明節點間社會關系越強；反之，則表明節點間社會關系較弱。在時間間隔τm內，節點vi對節點vj的社會關系強度F(i,j)(τm)可以表示為：

(3)

其中，E(i,j)(τm)為在時間間隔τm內，節點vi與節點vj的相遇次數；Ni(τm)為節點vi在時間間隔τm內同其他任意節點的相遇次數。

節點活躍度反映的是在時間間隔τ內當前節點遇見不同新節點的個數占總個數的大小，而節點的社會關系強弱則反映的是在時間間隔τ內當前節點同某個特定節點相遇的次數占當前節點與其他節點相遇的總次數的大小。通過綜合考慮節點的活躍度和社會關系強弱，從而計算節點vi在時間間隔τm內對某個特定節點的有效轉發能力Q(i,k)(τm)：

Q(i,k)(τm)=F(i,k)(τm)*Di(τm)

(4)

2.2 平均相遇持續時間

在社會機會網絡中，絕大多數的路由算法都假設：一旦網絡中的兩個節點進行消息數據的轉發，其消息數據都可以成功投遞，而在實際路由過程中，若節點相遇的持續時間過短、網絡帶寬較小或者要傳輸的消息數據過大時，都可能無法保證消息數據的完整投遞。因此，將消息數據傳遞給節點間相遇持續時間更長的節點，更能保證消息數據的完整投遞，同時也從另一方面提高了消息的成功投遞率。

將節點間的相遇持續時間定義為相遇的兩個節點從彼此進入通訊范圍開始到離開相互的通訊范圍為止所經過的時間。每次相遇，節點都會將其相遇的經過記錄到一個ET(encounter table)表中，表中記錄相遇節點的id、通信連接的建立時間、通信連接的斷開時間。然后通過此ET表計算兩個節點間每次相遇的持續時間。

圖1為某對節點歷史相遇情況的時序表，每次相遇的持續時間記為{T1,T2,…,Tn}。

圖1 某對節點相遇歷史時序表

依據節點間歷史的相遇持續時間記錄，首先計算其在時間間隔τm內總的相遇持續時間，如下所示：

(5)

其中，Tk為節點vi與節點vj第k次相遇的持續時間。

(6)

節點每次相遇時，盡量將消息轉發給平均相遇持續時間較長的節點，保證消息的完整轉發,提高消息投遞的成功率。

2.3 相遇概率

根據節點的歷史相遇記錄以及節點的有效轉發能力預估節點間未來的相遇概率。當網絡中的任意節點vi與節點vj相遇時，其相遇概率P(i,j)按照式(7)進行更新。

P(i,j)=P(i,j)old+(1-P(i,j)old)*Q(i,j)(τx)

(7)

其中,P(i,j)表示當前節點vi與節點vj的相遇概率；P(i,j)old表示更新之前節點vi與節點vj的相遇概率；Q(i,j)(τx)表示根據歷史記錄計算的在當前的時間間隔τx內節點vi對節點vj的有效轉發能力。若在當前時間間隔τx內，節點vi對節點vj的有效轉發能力越強，則節點vi與節點vj未來相遇概率越大；反之，則未來相遇的概率越小。

節點間的相遇概率隨著時間動態變化，如果節點vi與節點vj在長時間內沒有再次相遇，則表明節點vi與節點vj在未來的相遇概率也會隨著時間變小。對于節點間的相遇概率，引入衰減函數，兩節點間的相遇概率會隨著時間變化而衰減。其衰減的過程如下所示：

P(i,j)=P(i,j)old*γk

(8)

其中，γ∈(0,1)表示一個衰減常數，γ值越小表示該衰減過程的衰減越快，也就是對節點間的相遇概率影響越大；k表示單位時間個數，表明兩節點多久未曾相遇。

同時節點間的相遇概率也應該具有傳遞性。如果節點vi想要把消息數據傳遞給節點vo，而節點vi在移動過程中又很少遇到節點vo，但是節點vi在移動過程中經常遇到節點vj，節點vj在移動過程中可以經常遇到節點vo，那么節點vi就可以通過節點vj把消息成功傳遞給節點vo。因此，節點vi與節點vo的相遇概率更新公式計算如下：

(9)

其中，P(i,j)表示節點vi與節點vj當前時間的相遇概率；P(i,j)old表示更新之前節點vi與節點vj的相遇概率；P(j,o)表示節點vj與節點vo當前時間的相遇概率；Q(i,j)(τx)和Q(j,o)(τx)分別為根據歷史記錄計算的在當前時間間隔τx內節點vi對節點vj的消息有效轉發能力和節點vj對節點vo的消息有效轉發能力。

2.4 轉發策略

在消息的轉發決策階段，節點根據有效轉發能力和節點間的相遇概率進行消息數據的轉發。為了將消息完整地傳遞，考慮了節點間的相遇持續時間。設定一個最小相遇持續時間閾值，當節點間的相遇持續時間大于此閾值時才進行消息的轉發活動，避免因節點間相遇持續時間過短而導致消息傳輸失敗，不僅浪費節點的通信機會，也造成網絡的路由性能下降。

提出的路由算法轉發策略的具體運行流程如圖2所示。

當網絡中兩個節點相遇時，首先判斷該相遇的節點是否為目的節點，若是，則將消息投遞給目的節點，完成此次消息投遞任務，若不是，則接著判斷兩節點間的平均相遇持續時間是否大于規定閾值，若不大于規定閾值則因節點間相遇持續時間過短而忽略此相遇節點，若大于規定閾值則進一步判斷兩節點同目的節點的相遇概率，從而最終決定是否進行消息轉發或者繼續持有該消息并更新這兩節點間的相遇概率，完成此次的消息轉發活動。

3 實驗與仿真

3.1 實驗設置

采用ONE(opportunistic network environment)[15]仿真工具進行路由算法的仿真實驗。為了更貼近實際應用環境，使用兩個真實移動軌跡數據集對路由算法的性能進行分析和評價。

(1)Infocom 2006[16]。

該數據集為參加Infocom2006大會的77個研究人員攜帶的iMotes設備在參加會議的3天產生的移動軌跡記錄數據，此數據集合時間跨度較短，但節點間連接比較頻繁。

(2)MIT reality mining[17]。

該數據集為97個麻省理工學院的學生通過攜帶的藍牙設備記錄大約9個月的相互之間的連接信息。此數據集時間跨度較長，但是節點間連接比較稀疏。

通過這兩個真實數據集，在ONE仿真工具上將文中提出的路由算法同現有的Epidemic、BubbleRap、Prophet等路由算法在多個路由評價指標上進行性能對比。為了更好地進行仿真實驗，在使用這兩個數據集之前將其進行簡單處理：對于Infocom 2006數據集，將其前48小時的數據記錄作為歷史相遇信息，后24小時的數據記錄作為仿真實驗的實驗信息。對于MIT reality mining數據集，由于該數據集時間跨度較大，歷史記錄較多，取其兩個月的歷史記錄數據進行仿真實驗。其中前30天的歷史記錄作為歷史相遇信息，后30天的歷史記錄作為仿真實驗的實驗信息。然后，分別對比分析在這兩種不同的數據集場景下各個路由算法的性能優劣。仿真實驗中，節點的初始相遇概率取0.8，γ=0.95，其他具體的網絡仿真實驗場景參數設置如表1和表2所示。

表1 Infocom 2006數據集仿真場景參數設置

表2 MIT數據集仿真場景參數設置

3.2 評價指標

文中主要從以下幾個方面評價路由算法的性能：

(1)消息的成功投遞率：指成功到達目標節點的消息數同源節點產生的消息總數的比值，是評價路由算法優劣的基本指標之一。

(2)消息的平均時延：指消息從源節點產生到成功投遞目標節點所花費的平均時間。該指標體現了路由算法的高效性。消息的平均時延越小，目標節點需要等待的時間越少，網絡資源的再利用率也會越高。

(3)消息冗余率：指網絡中存在的消息副本數同成功投遞到目標節點的消息數之比。消息冗余率越高，意味網絡中充斥著越多的待投遞的消息，不僅容易造成網絡擁塞，也浪費網絡資源。

3.3 實驗分析

在3.1節規定的實驗仿真場景設置下，分別采用不同的路由算法進行仿真，結果如圖3～5所示。

從圖3可以看出，隨著消息生命周期的增大，各個算法的投遞成功率都有不同的增長。不同的是，相較于MIT數據集，Infocom數據集中的各個路由算法消息成功投遞率相對較高，這是由于Infocom 2006數據集節點間連接頻繁，節點間相遇的機會更多。并且,從圖中也可以看出，文中提出的基于歷史相遇信息的機會路由算法同其他路由算法相比，在節點連接稀疏和頻繁的場景下消息投遞成功率都較高。

(a)Infocom數據集 (b)MIT數據集

(a)Infocom數據集 (b)MIT數據集

從圖4可以看出，當消息的生命周期較小時，各個算法的消息平均時延相差不大，但是當圖4(a)中消息的生命周期增大到3 h，圖4(b)中消息的生命周期增大到24 h時，各個算法的平均時延差異開始增大。這是由于基于歷史相遇信息的機會路由算法在提高消息投遞率的同時能有效控制消息的轉發途徑，盡量避免不必要的消息傳輸，將消息數據較快地轉發給目標節點。

(a)Infocom數據集 (b)MIT數據集

從圖5中可以看出，Epidemic路由算法消息冗余率最大，遠遠大于其他路由算法。相較于圖5(a)，圖5(b)中隨著消息的生命周期增大，網絡的冗余率變化更為緩慢，這是由于MIT數據集節點接觸時間間隔較大，節點接觸機會較少。同時也可以看出，在這兩個數據集中，基于歷史相遇的自適應路由算法的消息冗余率增長平穩，在保證消息投遞率的同時，其網絡中消息冗余較少。

4 結束語

提出了一種基于歷史相遇信息的社會機會網絡路由算法，該算法在消息的剩余生命周期時間內，通過歷史記錄的節點間相遇信息評價節點對之間的有效轉發能力，并且不斷更新節點對之間的相遇概率，始終將消息轉發給跟目的節點相遇概率高的中繼節點。此外，通過ET表中保存的節點間的相遇持續時間計算節點間的平均相遇持續時間，并設定一個最小平均相遇持續時間閾值來避免消息數據不必要的轉發活動，優化消息轉發決策。仿真實驗表明，提出的路由算法在節點通訊頻繁和節點通訊稀少的情況下都能夠有效地提升消息的成功投遞率、降低網絡通訊時延、減少網絡中消息的冗余率。

[1] MOREIRA W,MENDES P.Impact of human behavior on social opportunistic forwarding[J].Ad Hoc Networks,2015,25:293-302.

[2] YAO L,MAN Y,HUANG Z,et al.Secure routing based on social similarity in opportunistic networks[J].IEEE Transactions on Wireless Communications,2016,15(1):594-605.

[3] REINA D G,ASKALANI M,TORAL S L,et al.A survey on multihop ad hoc networks for disaster response scenarios[J].International Journal of Distributed Sensor Networks,2015,2015:3.

[4] LU Z,CAO G,PORTA T L.Networking smartphones for disaster recovery[C]//IEEE international conference on pervasive computing and communications.[s.l.]:IEEE,2016:1-9.

[5] 薛莉思,張 杰,杜 江.基于DTN的地震應急通信路由協議的研究[J].計算機技術與發展,2017,27(2):182-186.

[6] ELSHERIEF M,ELBATT T,ZAHRAN A,et al.An information-theoretic model for knowledge sharing in opportunistic social networks[C]//IEEE international conference on smart city/socialcom/sustaincom.[s.l.]:IEEE,2015:446-451.

[7] DZIEKONSKI A M,SCHOENEICH R O.DTN routing algorithm for networks with nodes social behavior[J].International Journal of Computers,Communications & Control,2016,11(4):457-471.

[8] ANTHRU S V,JAYAKUMAR T P.Opportunistic routing protocols in human working day model delay tolerant networks[J].International Journal of Engineering and Computer Science,2014,3(5):5960-5965.

[9] WANG X,LIN Y,ZHAO Y,et al.A novel approach for inhibiting misinformation propagation in human mobile oppor-

tunistic networks[J].Peer-to-Peer Networking and Applications,2017,10(2):377-394.

[10] PATEL D,SHAH R.Improved PROPHET routing protocol in DTN[J].International Research Journal of Engineering Technology,2016,3(6):503-509.

[11] GONDALIYA N,SHAH M,KATHIRIYA D.A node scheduling approach in community based routing in social delay tolerant networks[C]//International conference on advances in computing,communications and informatics.[s.l.]:IEEE,2015:594-600.

[12] XIAO M,WU J,HUANG L.Community-aware opportunistic routing in mobile social networks[J].IEEE Transactions on Computers,2014,63(7):1682-1695.

[13] BULUT E, SZYMANSKI B K. Exploiting friendship relations for efficient routing in mobile social networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(12):2254-2265.

[14] COSTANTINO G,MARTINELLI F,SANTI P.Privacy-preserving interest-casting in opportunistic networks[C]//Wireless communications and networking conference.[s.l.]:IEEE,2012:2829-2834.

[15] DIWAKER C,SAINI S.An enhanced cluster based movement model using multiple ferries nodes in VANET[J].International Journal of Management,IT and Engineering,2016,6(10):68-78.

[16] WU J,WANG Y.Hypercube-based multipath social feature routing in human contact networks[J].IEEE Transactions on Computers,2014,63(2):383-396.

[17] NUNES I O,DE MELO P O S V,LOUREIRO A A F.Leveraging D2D multihop communication through social group meeting awareness[J].IEEE Wireless Communications,2016,23(4):12-19.