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

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

關鍵詞：車聯(lián)網(wǎng);延遲容忍網(wǎng)絡;路由算法;消息轉(zhuǎn)發(fā)

中圖分類號： 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 引言

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

路由的選擇將極大程度地影響消息傳輸?shù)男屎途W(wǎng)絡資源的開銷，而現(xiàn)有的許多DTN 路由協(xié)議在設計上并未考慮城市交通環(huán)境中車輛的移動特性和分布特點，且對于中繼節(jié)點的篩選指標單一。因此本文在考慮城市交通環(huán)境固有特點的情況下，提出一種基于車輛節(jié)點認知交互的路由算法，以有效提高消息傳輸?shù)男什⒔档途W(wǎng)絡資源開銷。

1 相關工作

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

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

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

2 基于節(jié)點認知交互的路由策略

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

4 結(jié)語

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

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

參考文獻：

[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.