車聯(lián)網(wǎng)環(huán)境下基于節(jié)點(diǎn)認(rèn)知交互的路由算法

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

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

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

中圖分類號(hào)： U491

文獻(xiàn)標(biāo)志碼：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 引言

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

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

1 相關(guān)工作

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

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

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

2 基于節(jié)點(diǎn)認(rèn)知交互的路由策略

為了清楚地闡明本文所提出的路由策略算法，首先需要對(duì)路由設(shè)計(jì)過(guò)程中所涉及的相關(guān)定義進(jìn)行解釋和說(shuō)明。

4 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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