車聯網環境下基于節點認知交互的路由算法

樊娜 朱光源 康軍 唐蕾 朱依水

摘 要：針對車聯網（IoV）環境下消息傳輸效率低下、網絡資源開銷較大等諸多問題，提出一種適用于城市交通場景下基于車輛節點認知交互的路由算法。首先，依據信任理論提出節點認知交互度的概念，并在此基礎上對車聯網中的車輛節點進行分類，賦予它們不同的認知交互度初值;同時還引入車輛節點交互時間、交互頻率、車輛節點物理間隔距離、間隔跳數以及消息生存時間等影響因子，進而構建了車輛節點認知交互評估模型。基于該模型計算并更新節點的認知交互度，并通過比較對應車輛節點間的認知交互度值來選取認知交互度相對較高的鄰居節點作為中繼節點進行消息轉發。仿真實驗結果表明，與Epidemic和Prophet路由算法相比，所提路由算法有效提高了消息投遞率并降低了消息投遞時延，同時顯著降低了網絡資源的開銷，有助于提升車聯網環境的消息傳輸質量。

關鍵詞：車聯網;延遲容忍網絡;路由算法;消息轉發

中圖分類號： U491

文獻標志碼：A

Abstract： In order to solve the problems such as low transmission efficiency and high network resource overhead in Internet of Vehicles （IoV） environment， a new routing algorithm based on node cognitive interaction， which is suitable for urban traffic environment， was proposed. Firstly， based on trust theory， a concept of cognitive interaction degree was proposed. Then， based on this， the vehicle nodes in IoV were classified and given with different initial values of cognitive interaction degree. Meanwhile， the influence factors such as interaction time， interaction frequency， physical distance， hops between nodes and the Time-To-Live of message were introduced， and a cognitive interaction evaluation model of vehicle nodes was constructed. The cognitive interaction degrees of vehicle nodes were calculated and updated by using the proposed model， and a neighbor node with higher cognitive interaction degree than others could be selected as relay node to forward the messages after the comparison between the nodes. Simulation results show that compared with Epidemic and Prophet routing algorithms， the proposed algorithm effectively increases the message delivery rate and reduces the message delivery delay， while significantly reducing the overhead of network resources and helping to improve the quality of message transmission in IoV environment

Key words： Internet of Vehicles （IoV）; Delay Tolerant Network （DTN）; routing algorithm; message forwarding

0 引言

隨著近年來物聯網技術的迅猛發展，車聯網已經成為城市智能交通的重要組成部分。同其他開放動態網絡類似，城市車聯網具有拓撲結構動態多變、車輛交互時間短暫以及車輛節點分布不均勻等特點[1]，經常會出現網絡連接和消息通信的中斷以及消息難以通過合適的中繼到達目的節點等現象[2-3]，因此，車聯網對通信鏈路的魯棒性和延遲容忍性提出了較高的要求。而延遲容忍網絡（Delay Tolerant Network，DTN） 能夠在缺少端到端連接的情況下以“存儲攜帶轉發”的形式完成消息投遞，其本質是一種位于區域網絡之上的覆蓋（overlay）網絡，其特點主要包括網絡拓撲時變性和網絡連通間歇性[4-6]，因此將DTN技術加以擴展并在城市交通環境下的車聯網中進行應用，將有效提高消息投遞的可達性和可靠性[7]。

路由的選擇將極大程度地影響消息傳輸的效率和網絡資源的開銷，而現有的許多DTN 路由協議在設計上并未考慮城市交通環境中車輛的移動特性和分布特點，且對于中繼節點的篩選指標單一。因此本文在考慮城市交通環境固有特點的情況下，提出一種基于車輛節點認知交互的路由算法，以有效提高消息傳輸的效率并降低網絡資源開銷。

1 相關工作

目前國內外學者對應用于DTN中的路由策略進行了深入的研究。其中Vahdat[8]提出了Epidemic路由策略，在該策略中，每當兩個節點相遇，會觸發彼此間的反熵會話，期間雙方互相交換各自的摘要向量（Summary Vector，SV），對比各自緩存中的消息，并把對方缺少的消息發送給對方。該策略在大規模隨機移動模型中以及網絡資源充足時能夠表現出較好的性能。然而，從本質上而言Epidemic協議是一種以犧牲網絡資源為代價獲得較高投遞率和較低時延的洪泛策略[9]。相比較而言，Spray and Wait[10-11] 策略是一種限制性洪泛路由策略，其過程分為Spray階段和Wait階段，在Spray階段源節點中的消息以拷貝副本的形式被擴散到鄰居節點，若該階段沒有發現目標節點，則攜帶消息副本的中繼節點進入Wait階段，即不再借助中繼節點而采用直接傳遞（Direct Delivery）的方式將消息交付給目的節點，該方式通過減少網絡中的包副本數，能有效減少網絡開銷。但上述兩種策略均依賴拷貝副本轉發，因此節點的信息冗余度高。為了避免消息的盲目轉發并進一步減少開銷，Lindgren等[12]提出了Prophet路由策略，該路由策略利用節點間相遇的歷史信息，將節點間的相遇頻繁程度量化為節點間的相遇概率，并以此來預測相遇節點作為中繼遇到目的節點的概率[13-14]。通過對中繼節點的篩選，可有效減少低效副本的產生，以此提高網絡資源的利用率[15]。

雖然Prophet路由在一定程度上緩解了網絡資源的消耗，但該策略并未考慮真實城市交通路網中不同車輛節點具備不同分布特點和移動特性的情況[16];且僅僅以節點建立連接頻率作為相遇概率更新的依據，同時也沒有考慮中繼節點對于消息成功投遞的有效性以及連接過程的穩定性等因素。例如，若某節點多次協助消息成功投遞，又或是某節點的連接行為較穩定等，那么對于該節點的評估值應該更高。

本文針對城市交通路網環境，借鑒Prophet這類預測路由的設計思路，以消息傳輸過程中的多元因素為依據，將歷史相遇情況和歷史投遞情況融入評價指標，綜合連接建立和消息投遞完成兩個階段中的節點行為，并將其量化為節點間的認知交互度（Cognitive Interaction， CI），以此表示消息投遞的可達性，以便攜包轉發節點于中繼節點篩選階段作出合理的下一跳轉發選擇，從而提高消息的投遞率，并有效降低時延和開銷。

2 基于節點認知交互的路由策略

為了清楚地闡明本文所提出的路由策略算法，首先需要對路由設計過程中所涉及的相關定義進行解釋和說明。

4 結語

針對城市交通車聯網應用環境中的DTN，為了提高消息的傳輸性能，本文定義了車輛節點交互新鮮度、節點交互參與度、消息效用度等相關概念，同時引入車輛節點距離及跳數等因素，提出了一種基于車輛節點認知交互的路由策略，全面客觀地刻畫和描述了節點間的歷史交互行為，并將其量化組合用于中繼節點篩選。由于綜合考慮了影響中繼節點選擇的多種因素，因此本文所提出的路由策略算法能顯著提高消息投遞率，同時有效地降低時延和開銷。

在后續的研究中，本文將考慮引入車輛節點社交信息，評估社交屬性對中繼節點選擇的影響，進一步優化路由算法，提高消息的傳輸效率。

參考文獻：

[1]?FLOREA A R， COSTEA I M. Analisys of improvements the urban transport conditions by using electronic intelligent transports systems case study： urban transportation [C]// Proceedings of the 2014 International Conference on Electronics， Computers and Artificial Intelligence. Piscataway， NJ： IEEE， 2014： 73-78.

[2]?WANG T， CAO Y， ZHOU Y， et al. A survey on geographic routing protocols in Delay/Disruption Tolerant Networks （DTNs） [J]. International Journal of Distributed Sensor Networks， 2016（6）： 3174670. DOI：？10.1155/2016/3174670; https：//journals.sagepub.com/doi/full/10.1155/2016/3174670

[3]?DOERING M， PGEL T， WOLF L. DTN routing in urban public transport systems [C]// CHANTS 10： Proceedings of the 5th ACM Workshop on Challenged Networks. New York： ACM， 2010： 55-62.

[4]?FALL K， FARRELL S. DTN： an architectural retrospective [J]. IEEE Journal on Selected Areas in Communications， 2008， 26（5）： 828-836.

[5]?VOYIATZIS A G. A survey of delay- and disruption-tolerant networking applications [J]. Journal of Internet Engineering， 2012， 5（1）： 331-344.

[6]?WU J， YANG S， DAI F. Logarithmic store-carry-forward routing in mobile Ad Hoc networks [J]. IEEE Transactions on Parallel and Distributed Systems， 2007， 18（6）： 735-748.

[7]?BENAMAR M， AHNANA S， SAIYARI F Z， et al. Study of VDTN routing protocols performances in sparse and dense traffic in the presence of relay nodes [J]. Journal of Mobile Multimedia， 2014， 10（1/2）： 78-93.

[8]?VAHDAT A BECKER D. Epidemic routing for partially-connected Ad Hoc networks， Handbook of Systemic Autoimmune Diseases [R]. Durham： Duke University， Department of Computer Science， 2000.， 2000.

[9]?TORNELL S M， CALAFATE C T， CANO J-C， et al. DTN protocols for vehicular networks： an application oriented overview [J]. IEEE Communications Surveys & Tutorials， 2017， 17（2）： 868-887.

[10]?SPYROPOULOS T， PSOUNIS K， RAGHAVENDRA C S. Spray and wait： an efficient routing scheme for intermittently connected mobile networks [C]// WDTN 05： Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York：ACM， 2005： 252-259.

[11]?AL-HINAI A， ZHANG H， CHEN Y， et al. TB-SnW： trust-based spray-and-wait routing for delay-tolerant networks [J]. Journal of Supercomputing， 2014， 69（2）： 593-609.

[12]?LINDGREN A， DORIA A， SCHELéN O. Probabilistic routing in intermittently connected networks [C]// SAPIR 2004： Proceedings of the 2004 International Workshop on Service Assurance with Partial and Intermittent Resources. Berlin： Springer-Verlag， 2004： 239-254.

[13]?QIN S， FENG G， ZHANG Y. How the contact-probing mechanism affects the transmission capacity of delay-tolerant networks [J]. IEEE Transactions on Vehicular Technology， 2011， 60（4）： 1825-1834.

[14]?SHINKO I， ODA T， SPAHO E， et al. A simulation system based on ONE and SUMO simulators： performance evaluation of First Contact， Prophet and Spray-and-Wait DTN protocols [C]// BWCCA 15： Proceedings of the 2015 10th International Conference on Broadband and Wireless Computing， Communication and Applications. Washington， DC：IEEE Computer Society， 2015： 137-142.

[15]?LIM H H， DONG Y S， YUN W C. An improved PRoPHET routing protocol through the restriction of message duplication [J]. Journal of Korean Institute of Information Technology， 2016， 14（6）： 81.

[16]?GAITO S， MAGGIORINI D， ROSSI G P， et al. Bus switched networks： An Ad Hoc mobile platform enabling urban-wide communications [J]. Ad Hoc Networks， 2012， 10（6）： 931-945.