鄧 健，董柏宏，曹 慧，吳麗娟，張 波，吳維剛

(1.中山大學(xué) 數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣州 510006； 2.國(guó)家電網(wǎng) 萊蕪供電公司，山東 萊蕪 271100)

(*通信作者電子郵箱1003932334@qq.com)

基于命名數(shù)據(jù)網(wǎng)絡(luò)的車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)機(jī)制

鄧 健1*，董柏宏1，曹 慧1，吳麗娟2，張 波2，吳維剛1

(1.中山大學(xué) 數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣州 510006； 2.國(guó)家電網(wǎng) 萊蕪供電公司，山東 萊蕪 271100)

(*通信作者電子郵箱1003932334@qq.com)

車載自組織網(wǎng)絡(luò)(VANET)是一個(gè)高度動(dòng)態(tài)的通信網(wǎng)絡(luò)，設(shè)計(jì)穩(wěn)定的數(shù)據(jù)分發(fā)機(jī)制是一個(gè)很大的挑戰(zhàn)。將關(guān)注數(shù)據(jù)內(nèi)容的命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)應(yīng)用于車載自組織網(wǎng)絡(luò)中，能有效緩解網(wǎng)絡(luò)拓?fù)漕l繁變化所帶來的問題。首先，優(yōu)化命名數(shù)據(jù)網(wǎng)絡(luò)的消息類型和數(shù)據(jù)結(jié)構(gòu)；然后，結(jié)合車載自組織網(wǎng)絡(luò)的特性，提出根據(jù)路段建立路由的方式，減少數(shù)據(jù)分發(fā)的開銷。仿真實(shí)驗(yàn)結(jié)果表明，所提出的基于命名數(shù)據(jù)網(wǎng)絡(luò)的車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)機(jī)制與應(yīng)用于車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)的傳統(tǒng)命名數(shù)據(jù)網(wǎng)絡(luò)算法對(duì)比，數(shù)據(jù)轉(zhuǎn)發(fā)平均命中率(AHR)提高大約53個(gè)百分點(diǎn)，平均轉(zhuǎn)發(fā)次數(shù)減少大約0.4。因此提出的基于命名數(shù)據(jù)網(wǎng)絡(luò)的車聯(lián)網(wǎng)數(shù)據(jù)分發(fā)機(jī)制，采用新的路由方式，能夠提高數(shù)據(jù)分發(fā)效率。

車載自組織網(wǎng)絡(luò)；路段信息；路由；數(shù)據(jù)分發(fā)；命名數(shù)據(jù)網(wǎng)絡(luò)

0 引言

車載自組織網(wǎng)絡(luò)(Vehicular Ad Hoc Network， VANET)[1]，采用IEEE 802.11p[2]標(biāo)準(zhǔn)，實(shí)現(xiàn)車輛與車輛(Vehicle-to-Vehicle，V2V)或者車輛與路邊單元之間(Vehicle-to-Infrastructure，V2I)的通信[3]。車載自組織網(wǎng)絡(luò)繼承了移動(dòng)無線自組織網(wǎng)絡(luò)的特性：分布式操作、寬帶有限、節(jié)點(diǎn)移動(dòng)性與網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性等[4]。除此之外，它還具有通信環(huán)境復(fù)雜、鏈路易斷的難點(diǎn)[5]。因此，關(guān)注轉(zhuǎn)發(fā)內(nèi)容的數(shù)據(jù)分發(fā)方式將比規(guī)定目的地址的網(wǎng)絡(luò)傳輸方式更適用于車載自組織網(wǎng)絡(luò)。而命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking，NDN)[6]關(guān)注的就是消息內(nèi)容，因此命名數(shù)據(jù)網(wǎng)絡(luò)技術(shù)在車載自組織網(wǎng)絡(luò)中會(huì)有很大的應(yīng)用前景。

對(duì)命名數(shù)據(jù)網(wǎng)絡(luò)的研究也隨著它的興起越來越多，一些研究從優(yōu)化興趣列表入手[7]，另外也有關(guān)注消息存儲(chǔ)列表的訪問速度[8]。但是這些都只是關(guān)注命名數(shù)據(jù)網(wǎng)絡(luò)本身，對(duì)于它的應(yīng)用還沒有進(jìn)行太多討論。關(guān)于命名數(shù)據(jù)網(wǎng)絡(luò)技術(shù)在車載自組織網(wǎng)絡(luò)的應(yīng)用，近年來已經(jīng)出現(xiàn)了相關(guān)的研究成果[9-11]：文獻(xiàn)[9]提出了根據(jù)距離選擇生產(chǎn)者發(fā)送數(shù)據(jù)的消息分發(fā)算法，文獻(xiàn)[10]提出了通過針對(duì)不同類型的消息設(shè)置不同的定時(shí)器從而減少?zèng)_突的命名數(shù)據(jù)網(wǎng)絡(luò)消息分發(fā)算法，文獻(xiàn)[11]則提出了一種結(jié)合生產(chǎn)者地理位置的命名數(shù)據(jù)網(wǎng)絡(luò)分發(fā)算法來提高分發(fā)效率。但是這些工作還只是簡(jiǎn)單地將NDN的方法應(yīng)用到車載網(wǎng)絡(luò)中，對(duì)于車載自組織網(wǎng)絡(luò)與NDN結(jié)合之后影響數(shù)據(jù)分發(fā)的因素考慮得還不夠全面，相關(guān)的算法和協(xié)議還不能很好地發(fā)揮車載自組織網(wǎng)絡(luò)的特性。

本文設(shè)計(jì)并改進(jìn)了基于命名數(shù)據(jù)網(wǎng)絡(luò)的車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)機(jī)制，其主要?jiǎng)?chuàng)新在于結(jié)合了車載自組織網(wǎng)絡(luò)的特點(diǎn)，根據(jù)路段建立路由，并根據(jù)車輛的自主接包功能實(shí)現(xiàn)建立和重建表格。另外，算法中消息的分發(fā)還綜合采用了最遠(yuǎn)距離優(yōu)先轉(zhuǎn)發(fā)和設(shè)置定時(shí)器的思想，并且增加消息類型確保消息分發(fā)的穩(wěn)定性。最后進(jìn)行實(shí)驗(yàn)仿真，并與根據(jù)文獻(xiàn)[12]提出的算法進(jìn)行對(duì)比，分析算法性能。由于本文考慮的是一個(gè)連通的車載自組織網(wǎng)絡(luò)之間的通信，而文獻(xiàn)[12]中提出的“data mule”這一角色，是在兩個(gè)不連通的網(wǎng)絡(luò)中實(shí)現(xiàn)消息的傳遞，以達(dá)到資源共享的作用?！癲ata mule”轉(zhuǎn)發(fā)數(shù)據(jù)所帶來的開銷和延遲對(duì)于本文所有車輛都在一個(gè)連通的網(wǎng)絡(luò)狀態(tài)下來說，是沒有意義的。因此，“data mule”這一角色不在本文的算法討論范圍內(nèi)。

1 命名數(shù)據(jù)網(wǎng)絡(luò)簡(jiǎn)介

在基于TCP/IP協(xié)議的網(wǎng)絡(luò)中，數(shù)據(jù)分組是以通信末端的IP地址命名的。但是隨著互聯(lián)網(wǎng)的發(fā)展，人們更注重于信息的獲取，而不是僅僅關(guān)注兩點(diǎn)之間的通信。命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)不關(guān)心消息存放的位置，而是關(guān)注消息的內(nèi)容，因此很好地滿足了人們對(duì)于信息檢索的需求。圖1展示了IP協(xié)議架構(gòu)和NDN架構(gòu)的不同之處。從圖中可以看出，在沙漏的細(xì)腰處，NDN的架構(gòu)使用了內(nèi)容模塊替代了IP架構(gòu)的IP地址。

圖1 IP協(xié)議與NDN架構(gòu)的細(xì)腰沙漏模型

命名數(shù)據(jù)網(wǎng)絡(luò)架構(gòu)包括兩種消息類型、三種節(jié)點(diǎn)角色以及三種數(shù)據(jù)結(jié)構(gòu)。

兩種消息類型 興趣包(Interest Packet)和數(shù)據(jù)包(Data Packet)。圖2展示了兩種消息類型的數(shù)據(jù)結(jié)構(gòu)。節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)時(shí)，會(huì)發(fā)送興趣包，其中記錄著需要的數(shù)據(jù)的名字。如果節(jié)點(diǎn)收到興趣包，且有對(duì)應(yīng)的數(shù)據(jù)包，則會(huì)回復(fù)數(shù)據(jù)包，并根據(jù)興趣包的轉(zhuǎn)發(fā)路徑原路返回到請(qǐng)求該數(shù)據(jù)的節(jié)點(diǎn)。

三種節(jié)點(diǎn)角色 生產(chǎn)者(Producer)、消費(fèi)者(Consumer)和轉(zhuǎn)發(fā)者(Forwarder)。生產(chǎn)者是產(chǎn)生并擁有某資源的節(jié)點(diǎn)，它定時(shí)廣播信息告知其他節(jié)點(diǎn)自己擁有的資源。消費(fèi)者是請(qǐng)求某資源的節(jié)點(diǎn)。而轉(zhuǎn)發(fā)者是負(fù)責(zé)轉(zhuǎn)發(fā)各種信息的節(jié)點(diǎn)。

三種數(shù)據(jù)結(jié)構(gòu) 轉(zhuǎn)發(fā)信息表(Forwarding Information Base, FIB)、待處理興趣表(Pending Interest Table, PIT)和數(shù)據(jù)分組緩存(Content Store, CS)。FIB用于記錄資源的路由信息，PIT用于記錄收到的興趣包及其轉(zhuǎn)發(fā)路徑上的上一跳，CS用于緩存數(shù)據(jù)包。

在命名數(shù)據(jù)網(wǎng)絡(luò)中，生產(chǎn)者首先廣播已有的資源，其他節(jié)點(diǎn)根據(jù)收到的消息，建立FIB。消費(fèi)者需要某種數(shù)據(jù)時(shí)，發(fā)送興趣包請(qǐng)求數(shù)據(jù)。收到興趣包的節(jié)點(diǎn)，如果CS中有該數(shù)據(jù)，則直接回復(fù)數(shù)據(jù)包；如果沒有，則把興趣包信息加入到該節(jié)點(diǎn)的PIT中。然后查詢FIB，如果有相應(yīng)的數(shù)據(jù)表項(xiàng)，則從對(duì)應(yīng)接口發(fā)出去，否則就丟棄。收到數(shù)據(jù)包的節(jié)點(diǎn)，如果該節(jié)點(diǎn)的PIT有對(duì)應(yīng)的興趣包表項(xiàng)，則緩存下來，并按照PIT中記錄的接口發(fā)出去，否則就丟棄該數(shù)據(jù)包。圖3展示了以上路由形式。

圖2 興趣分組與數(shù)據(jù)分組的數(shù)據(jù)結(jié)構(gòu)

圖3 命名數(shù)據(jù)網(wǎng)絡(luò)路由示意圖

2 基于命名數(shù)據(jù)網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)算法

本章將詳細(xì)介紹基于命名數(shù)據(jù)網(wǎng)絡(luò)的車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法。算法分設(shè)計(jì)分為三個(gè)方面：路由建立、資源探測(cè)以及數(shù)據(jù)請(qǐng)求。

2.1 基于命名數(shù)據(jù)網(wǎng)絡(luò)技術(shù)的消息轉(zhuǎn)發(fā)模型

算法根據(jù)路段信息建立路由，并根據(jù)建立的路由轉(zhuǎn)發(fā)數(shù)據(jù)。為了更好地理解該算法，首先對(duì)算法的模型進(jìn)行介紹。

2.1.1 系統(tǒng)角色

本文提出的算法沿用了命名數(shù)據(jù)網(wǎng)絡(luò)中的三種節(jié)點(diǎn)角色：生產(chǎn)者(Producer)、消費(fèi)者(Consumer)和轉(zhuǎn)發(fā)者(Forwarder)。

生產(chǎn)者 產(chǎn)生并擁有某資源的車輛節(jié)點(diǎn)。當(dāng)車輛產(chǎn)生并擁有了某個(gè)資源時(shí)，就會(huì)廣播告訴其他車輛。當(dāng)收到消費(fèi)者發(fā)來的興趣包時(shí)，回復(fù)對(duì)應(yīng)數(shù)據(jù)包。當(dāng)收到探測(cè)包時(shí)，回復(fù)確認(rèn)包。

消費(fèi)者 請(qǐng)求資源的車輛節(jié)點(diǎn)。當(dāng)車輛節(jié)點(diǎn)需要某資源且FIB中有對(duì)應(yīng)記錄時(shí)，發(fā)送興趣包請(qǐng)求資源。當(dāng)FIB沒有記錄時(shí)，廣播探測(cè)包尋找該資源。

轉(zhuǎn)發(fā)者 轉(zhuǎn)發(fā)消息的車輛節(jié)點(diǎn)。收到資源包時(shí)，根據(jù)資源包信息建立FIB。收到興趣包時(shí)，根據(jù)FIB轉(zhuǎn)發(fā)興趣包，并建立PIT。收到數(shù)據(jù)包時(shí)，根據(jù)PIT轉(zhuǎn)發(fā)出去，并按照規(guī)定緩存數(shù)據(jù)包到CS。同時(shí)還負(fù)責(zé)轉(zhuǎn)發(fā)探測(cè)包和確認(rèn)包。

2.1.2 消息類型

除了沿用NDN中的興趣包和數(shù)據(jù)包，本文提出的算法還包括另外3種消息類型：探測(cè)包(Detect Packet)、確認(rèn)包(Confirm Packet)、心跳包(Hello Packet)。在本算法中，所有消息類型的最大轉(zhuǎn)發(fā)跳數(shù)(Time To Live, TTL)均為15，即TTL不大于15，當(dāng)轉(zhuǎn)發(fā)的路段數(shù)到達(dá)15時(shí)，消息將不再被轉(zhuǎn)發(fā)。

興趣包 消費(fèi)者需要某數(shù)據(jù)時(shí)，就會(huì)發(fā)送興趣包請(qǐng)求該數(shù)據(jù)。格式如圖4所示。

圖4 興趣包格式

Fig.4 Format of interest packet

Name域保存的是數(shù)據(jù)名字；序列號(hào)(Nonce)保證興趣包的唯一性；跳數(shù)標(biāo)簽(Hop Count Tag)保存的是該興趣包被轉(zhuǎn)發(fā)的次數(shù)，當(dāng)?shù)竭_(dá)最大值，該興趣包將不會(huì)再被轉(zhuǎn)發(fā)；當(dāng)前路段(Current Section)保存的是興趣包轉(zhuǎn)發(fā)過來的路段；下一跳路段(Next Section)保存的是興趣包即將發(fā)送到的路段，通過查詢FIB得到。

數(shù)據(jù)包 生產(chǎn)者會(huì)根據(jù)收到的興趣包回發(fā)數(shù)據(jù)包。格式如圖5所示。

數(shù)據(jù)包的名字(Name)和跳數(shù)標(biāo)簽(Hop Count Tag)的作用與上述興趣包的一樣。簽名(Signature)用于保證數(shù)據(jù)包的唯一性；下一跳路段(Next Section)通過查詢PIT得到該數(shù)據(jù)包的下一跳路段；載荷(Payload)保存了數(shù)據(jù)的內(nèi)容。

圖5 數(shù)據(jù)包格式

Fig.5 Format of data packet

資源包 資源包屬于一種特殊的數(shù)據(jù)包，用于生產(chǎn)者廣播告知其他車輛節(jié)點(diǎn)它擁有的資源數(shù)據(jù)，其結(jié)構(gòu)與數(shù)據(jù)包一樣。

探測(cè)包 當(dāng)消費(fèi)者想要某資源數(shù)據(jù)，但是它的FIB沒有記錄該資源時(shí)，廣播探測(cè)包，尋找對(duì)應(yīng)資源。格式如圖6所示。

圖6 探測(cè)包格式

Fig.6 Format of detect packet

其中名字、序列號(hào)、跳數(shù)標(biāo)簽、當(dāng)前路段與上文興趣包的作用一樣。路段列表(Section List)記錄探測(cè)包走過的路段。

確認(rèn)包 當(dāng)有生產(chǎn)者收到探測(cè)包并擁有對(duì)應(yīng)資源時(shí)，回復(fù)確認(rèn)包。格式如圖7。

圖7 確認(rèn)包格式

Fig.7 Format of confirm packet

TTL保存的是消費(fèi)者到資源擁有者的跳數(shù)，用于判斷并找出跳數(shù)最小的路徑。其他數(shù)據(jù)域與探測(cè)包的數(shù)據(jù)域作用一樣。

心跳包 節(jié)點(diǎn)通過廣播心跳包與通信距離內(nèi)的車輛節(jié)點(diǎn)建立鄰居關(guān)系，交換車輛的坐標(biāo)、速度等信息。

2.1.3 數(shù)據(jù)結(jié)構(gòu)

本文提出的算法擁有三種數(shù)據(jù)結(jié)構(gòu)：轉(zhuǎn)發(fā)信息表(Forwarding Information Base, FIB)、待處理興趣表(Pending Interest Table, PIT)和數(shù)據(jù)分組緩存(Content Store，CS)。

轉(zhuǎn)發(fā)信息表(FIB) 當(dāng)節(jié)點(diǎn)收到資源包時(shí)，根據(jù)資源包的信息建立FIB。轉(zhuǎn)發(fā)信息表主要包含下一跳路段(next section)和到達(dá)該路段所需要的跳數(shù)(TTL)。當(dāng)節(jié)點(diǎn)收到興趣包時(shí)，根據(jù)FIB的記錄，轉(zhuǎn)發(fā)出去。數(shù)據(jù)結(jié)構(gòu)如圖8所示。

圖8 轉(zhuǎn)發(fā)信息表結(jié)構(gòu)

待處理興趣表(PIT) 當(dāng)車輛節(jié)點(diǎn)收到興趣包并且需要轉(zhuǎn)發(fā)出去時(shí)，就在PIT中記錄興趣包的相關(guān)信息，包括資源名字、上一跳路段等。當(dāng)該節(jié)點(diǎn)收到了興趣包所對(duì)應(yīng)的數(shù)據(jù)包時(shí)，就根據(jù)對(duì)應(yīng)PIT表項(xiàng)記錄的路段信息轉(zhuǎn)發(fā)出去并刪除該P(yáng)IT表項(xiàng)。數(shù)據(jù)結(jié)構(gòu)如圖9所示。

圖9 待處理興趣表結(jié)構(gòu)

數(shù)據(jù)分組緩存(CS) 數(shù)據(jù)分組用于緩存節(jié)點(diǎn)收到的數(shù)據(jù)，并可以在需要的時(shí)候發(fā)送給消費(fèi)者。本算法的緩存技術(shù)采用先進(jìn)先出(First In First Out, FIFO)的替換策略，當(dāng)緩存空間存滿數(shù)據(jù)時(shí)，就采用FIFO的策略調(diào)整緩存數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)如圖10所示。

圖10 數(shù)據(jù)分組緩存結(jié)構(gòu)

2.2 路由建立

當(dāng)生產(chǎn)者產(chǎn)生了某資源時(shí)，主動(dòng)廣播資源包，告知其他車輛節(jié)點(diǎn)所擁有的資源。為了保證網(wǎng)絡(luò)的連通性，資源包的轉(zhuǎn)發(fā)在每個(gè)十字路口的每個(gè)方向都存在，并且要求每個(gè)路段都有車輛參與轉(zhuǎn)發(fā)。

算法的主要流程如下：

1)生產(chǎn)者產(chǎn)生某資源時(shí)，廣播資源包。

2)車輛收到資源包，如果資源包無效(序列號(hào)重復(fù)且TTL大于或等于15)則丟棄。否則查看自己的FIB，如果有對(duì)應(yīng)的資源表項(xiàng)，則保存TTL更小的資源包信息；否則新建FIB表項(xiàng)。

3)更新資源包中的必要信息，然后根據(jù)距離設(shè)置定時(shí)器，距離上一跳越遠(yuǎn)定時(shí)器越短。計(jì)時(shí)結(jié)束之前，若沒有收到其他節(jié)點(diǎn)廣播的同樣的資源包，則將該資源包發(fā)送出去。

算法偽代碼如算法1所示。

算法1 路由建立算法(資源包轉(zhuǎn)發(fā))。

Input: resource packet Initialize: none Function ForwardResourcePacket (ResourcePacket) if repeat or TTL>15 return if (!FIB.Find(ResourcePacket.GetName())) FIB.Add(ResourcePacket) else FIB.Update(ResourcePacket) set waiting timer if no such forwarded package received from others in this section forward(ResourcePacket) return

end function

2.3 資源探測(cè)

探測(cè)資源算法主要兩個(gè)部分：探測(cè)包的轉(zhuǎn)發(fā)和確認(rèn)包的轉(zhuǎn)發(fā)。

算法的主要流程：

1)消費(fèi)者發(fā)送探測(cè)包尋找資源。

2)車輛收到探測(cè)包后，若無效將其丟棄。否則，查詢自己的CS和FIB，如果有對(duì)應(yīng)資源的記錄，則回復(fù)確認(rèn)包。否則將自己所在的路段加入探測(cè)包，并根據(jù)轉(zhuǎn)發(fā)資源包的方法設(shè)置定時(shí)器轉(zhuǎn)發(fā)該探測(cè)包。

3)當(dāng)車輛收到確認(rèn)包時(shí)，如果FIB沒有該確認(rèn)包對(duì)應(yīng)的資源表項(xiàng)，則建立FIB表項(xiàng)；否則，如果自己路段不在確認(rèn)包中保存的下一跳路段上，則丟棄；若在，則設(shè)置定時(shí)器，按照轉(zhuǎn)發(fā)探測(cè)包的方法轉(zhuǎn)發(fā)。

探測(cè)包的轉(zhuǎn)發(fā)算法偽代碼如算法2，確認(rèn)包的轉(zhuǎn)發(fā)算法偽代碼如表算法3。

算法2 探測(cè)包轉(zhuǎn)發(fā)算法。

Input: detect packet Initialize: none Function ForwardDetectingPacket (DetectPacket) if repeat or TTL>15 return if (FIB.Find(DetectPacket.GetName()) or CS.Find(DetectPacket.GetName())) send(ConfirmPacket) else add this->section into packet set waiting timer if no such forwarded package received from others in this section forward (DetectPacket) return

end function

算法3 確認(rèn)包轉(zhuǎn)發(fā)算法。

Input: confirming packet Initialize: none Function ForwardConfirmingPacket (ConfirmPacket) if (!FIB.Find(ConfirmPacket.GetName())) FIB.Add(ConfirmPacket) if this->section==next section set waiting timer if no such forwarded package received from others forward (ConfirmPacket) return

end function

2.4 數(shù)據(jù)請(qǐng)求

數(shù)據(jù)請(qǐng)求算法主要包括興趣包轉(zhuǎn)發(fā)和數(shù)據(jù)包轉(zhuǎn)發(fā)兩個(gè)方面。

算法的主要流程：

1)消費(fèi)者需要某資源時(shí)，根據(jù)FIB記錄發(fā)送興趣包請(qǐng)求數(shù)據(jù)。

2)車輛收到興趣包后，判斷是否有效。然后查詢自己的CS，如果保存有該資源，則回復(fù)數(shù)據(jù)包；否則，判斷路段信息，如果彼此路段不同，則丟棄。如果相同就檢查PIT，若有對(duì)應(yīng)資源記錄則更新對(duì)應(yīng)表項(xiàng)；否則查詢FIB，如果存在對(duì)應(yīng)的FIB表項(xiàng)，則根據(jù)該FIB表項(xiàng)記錄設(shè)置定時(shí)器把興趣包發(fā)送出去，并新建PIT表項(xiàng)。否則，丟棄該興趣包。

3)車輛節(jié)點(diǎn)收到數(shù)據(jù)包后查詢自己的PIT，如果沒有對(duì)應(yīng)表項(xiàng)，則不處理。若有，將數(shù)據(jù)緩存到CS，并刪除對(duì)應(yīng)PIT表項(xiàng)，設(shè)置定時(shí)器，轉(zhuǎn)發(fā)該數(shù)據(jù)包。

興趣包的轉(zhuǎn)發(fā)算法偽代碼如算法4，數(shù)據(jù)包的轉(zhuǎn)發(fā)算法偽代碼如算法5。

算法4 興趣包的轉(zhuǎn)發(fā)算法。

Input: interest packet Initialize: none Function ForwardInterestPacket (InterestPacket) if repeat or TTL > 15 return if (CS.Find(InterestPacket.GetName()) send(DataPacket) return

if this->section==next section if PIT.Find(InterestPacket.GetName()) PIT.Update() return else PIT.Add(InterestPacket) set waiting timer if no sunch forward package received from others forward Interest Packet return

end function

算法5 數(shù)據(jù)包轉(zhuǎn)發(fā)算法。

Input: data packet Initialize: none Function ForwardDataPacket (DataPacket) if PIT.Find(DataPacket.GetName()) CS.Add(DataPacket) PIT.Delete(DataPacket) Set waitint timer Forward(DataPacket) return end function

2.5 對(duì)比實(shí)驗(yàn)

由于命名數(shù)據(jù)網(wǎng)絡(luò)是近年新興的技術(shù)，對(duì)于其在車載自組織網(wǎng)絡(luò)中的應(yīng)用還是比較有限的。為了驗(yàn)證改進(jìn)算法的有效性，采用了根據(jù)文獻(xiàn)[12]提出的傳統(tǒng)的命名數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法作為對(duì)比。值得一提的是，文獻(xiàn)[12]提出了“data mule”這一節(jié)點(diǎn)角色，該角色的主要作用是使得兩個(gè)不連通的網(wǎng)絡(luò)能夠進(jìn)行數(shù)據(jù)共享和傳輸，但是，本文的重點(diǎn)在于考慮一個(gè)連通網(wǎng)絡(luò)中車輛之間的通信，“data mule”轉(zhuǎn)發(fā)數(shù)據(jù)所帶來的開銷和延遲對(duì)于本文所有車輛都在一個(gè)連通的網(wǎng)絡(luò)狀態(tài)下來說，是沒有意義的。所以，算法不考慮這一角色。本文主要將該算法與本文提出的改進(jìn)算法應(yīng)用于車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)中，并在相同的仿真環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，從而得出結(jié)論。

傳統(tǒng)命名數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)(Traditional Named Data Networking, TRA-NDN)分發(fā)算法與提出的改進(jìn)算法(Improved Named Data Networking, Improved-NDN)最大的不同在于：TRA-NDN的FIB和PIT中記錄的下一跳為某一節(jié)點(diǎn)，因此是以節(jié)點(diǎn)信息作為建立路由依據(jù)的；但是Improved-NDN是以路段為依據(jù)建立路由的。而且傳統(tǒng)的命名數(shù)據(jù)網(wǎng)絡(luò)的消息類型還不包括本文提出的改進(jìn)算法中包含的探測(cè)包(Detect Packet)、確認(rèn)包(Confirm Packet)和心跳包(Hello Packet)。但是為了實(shí)驗(yàn)在同一條件下進(jìn)行，本文將這三種消息類型也加入到對(duì)比實(shí)驗(yàn)中。

2.6 網(wǎng)絡(luò)連通性

本文所提出的算法是假設(shè)網(wǎng)絡(luò)始終聯(lián)通的。在路由建立階段，算法假設(shè)資源包的轉(zhuǎn)發(fā)在每個(gè)十字路口的每個(gè)方向都存在。因?yàn)楸疚牡乃惴紤]的是在一個(gè)密集而且連通的車載自組織網(wǎng)絡(luò)中，任意兩個(gè)節(jié)點(diǎn)都能彼此進(jìn)行通信。

為了應(yīng)對(duì)網(wǎng)絡(luò)斷連的情況，可以在本文算法中引入一些附加機(jī)制。一種方案是引入重傳機(jī)制。根據(jù)鏈路的斷開情況，重傳數(shù)據(jù)包。如果斷開的時(shí)間會(huì)比較久，可以考慮采用延容忍網(wǎng)絡(luò)(Delay Tolerant Network，DTN)的存儲(chǔ)—轉(zhuǎn)發(fā)機(jī)制。由斷連處的車輛節(jié)點(diǎn)攜帶數(shù)據(jù)包，遇到鄰居節(jié)點(diǎn)后再進(jìn)行轉(zhuǎn)發(fā)。這方面已經(jīng)有大量的研究和解決算法，就不具體討論。

3 實(shí)驗(yàn)仿真結(jié)果與分析

為了驗(yàn)證本文提出的基于命名數(shù)據(jù)網(wǎng)絡(luò)技術(shù)的數(shù)據(jù)分發(fā)算法的性能，本章將對(duì)算法進(jìn)行實(shí)驗(yàn)仿真。本次仿真采用基于ns-3模擬器的ndnSIM(Named Data Networking Simulator)仿真工具和SUMO(Simulation of Urban MObility)仿真器結(jié)合的方法在Linux系統(tǒng)下進(jìn)行仿真實(shí)驗(yàn)。

3.1 仿真環(huán)境

ns-3是一個(gè)離散時(shí)間模擬器，而ndnSIM是為了給NDN研究提供一個(gè)通用的仿真平臺(tái)而開發(fā)的基于ns-3的模塊化的仿真工具。SUMO是一個(gè)道路交通仿真軟件。本實(shí)驗(yàn)通過SUMO產(chǎn)生車輛移動(dòng)模型，并將其導(dǎo)入到ndnSIM仿真環(huán)境中，模擬出車載自組織網(wǎng)絡(luò)中的車輛移動(dòng)，并基于ndnSIM工具實(shí)現(xiàn)轉(zhuǎn)發(fā)策略。

要特別說明的是SUMO生成的車輛網(wǎng)絡(luò)拓?fù)渲校缆肥请p向的，命名彼此不相同，但是本文提出的改進(jìn)算法將其視為同一路段，即不考慮道路的方向問題。對(duì)比實(shí)驗(yàn)以節(jié)點(diǎn)作為建立路由依據(jù)，因此不考慮路段信息。

3.1.1 仿真配置

本次的仿真實(shí)驗(yàn)，采用的是6×6的方格網(wǎng)狀路網(wǎng)結(jié)構(gòu)。在路網(wǎng)中，有7條垂直的道路和7條水平的道路。每條都是標(biāo)準(zhǔn)的8車道道路。兩條道路的交叉點(diǎn)為十字路口。兩個(gè)相鄰的十字路口之間的道路為一個(gè)路段，長(zhǎng)度固定為500 m。仿真選定9個(gè)固定節(jié)點(diǎn)作為生產(chǎn)者，產(chǎn)生10種資源，隨機(jī)選擇67個(gè)節(jié)點(diǎn)作為消費(fèi)者對(duì)某一隨機(jī)資源發(fā)送請(qǐng)求。所有節(jié)點(diǎn)都作為轉(zhuǎn)發(fā)者。車輛移動(dòng)的相關(guān)參數(shù)如表1所示。

表1 車輛移動(dòng)仿真關(guān)鍵參數(shù)

3.1.2 評(píng)價(jià)指標(biāo)

結(jié)合本章的數(shù)據(jù)轉(zhuǎn)發(fā)算法的特點(diǎn)，仿真實(shí)驗(yàn)采用以下的指標(biāo)評(píng)價(jià)算法性能。

1)平均命中率(Average Hit Rate， AHR)。表示在發(fā)送興趣包請(qǐng)求數(shù)據(jù)的節(jié)點(diǎn)中收到數(shù)據(jù)包的節(jié)點(diǎn)的比率，用來衡量轉(zhuǎn)發(fā)算法的穩(wěn)定性。該值越高，則說明所有請(qǐng)求數(shù)據(jù)的節(jié)點(diǎn)中收到對(duì)應(yīng)數(shù)據(jù)包的節(jié)點(diǎn)越多，則算法越穩(wěn)定。

2)平均延遲(Average Delay， AD)。表示消費(fèi)者發(fā)送興趣包之后，收到對(duì)應(yīng)的數(shù)據(jù)包所用的平均時(shí)間，用來衡量算法的轉(zhuǎn)發(fā)速度。該值越小，說明接收數(shù)據(jù)所需的延遲越小，算法路由的速度越快。

3)平均轉(zhuǎn)發(fā)次數(shù)(Average Forward Times，AFT)。表示在一次數(shù)據(jù)請(qǐng)求的過程中，所有消息的轉(zhuǎn)發(fā)次數(shù)，包括探測(cè)包、確認(rèn)包、興趣包以及數(shù)據(jù)包，用以衡量請(qǐng)求數(shù)據(jù)的平均開銷。該值越小，則說明每次請(qǐng)求數(shù)據(jù)消息的轉(zhuǎn)發(fā)次數(shù)越小，表示該算法的開銷越小。

3.2 仿真結(jié)果

根據(jù)兩個(gè)算法的仿真實(shí)驗(yàn)得到的結(jié)果，對(duì)比分析出算法的優(yōu)劣。

3.2.1 平均命中率

平均命中率表示在發(fā)送興趣包請(qǐng)求數(shù)據(jù)的節(jié)點(diǎn)中收到數(shù)據(jù)包的節(jié)點(diǎn)的比率。命中率越高，表示算法越穩(wěn)定。

如圖11所示，傳統(tǒng)NDN(TRA-NDN)算法在該實(shí)驗(yàn)中的命中率為14%左右，而本文改進(jìn)的NDN算法(Improved-NDN)的命中率為66.7%。由于車載自組織網(wǎng)絡(luò)鏈路的穩(wěn)定性不好，車與車輛之間的鄰居關(guān)系無法一直維持，所以傳統(tǒng)NDN算法的命中率會(huì)明顯偏低，僅為14%左右。但是基于路段建立路由的改進(jìn)的NDN算法會(huì)找到固定的路段尋找到相關(guān)的資源，命中率較高。車輛移動(dòng)速度也會(huì)影響命中率，車速越快，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越不穩(wěn)定，車輛鄰居關(guān)系越難維持，命中率也就越低。

圖11 平均命中率對(duì)比

3.2.2 平均延遲

平均延遲表示所有消費(fèi)者發(fā)送興趣包之后，直到收到對(duì)應(yīng)的數(shù)據(jù)包所需要的平均時(shí)間，平均延遲時(shí)間越短，表示算法路由速度越快。

實(shí)驗(yàn)結(jié)果如圖12，傳統(tǒng)NDN算法平均延遲大約為0.4 s，而改進(jìn)后的算法延遲為1.27 s。這是由于傳統(tǒng)NDN算法是直接指定下一跳節(jié)點(diǎn)發(fā)送信息，沒有設(shè)置優(yōu)先級(jí)隊(duì)列和定時(shí)器。但是改善后的算法，設(shè)置了轉(zhuǎn)發(fā)的定時(shí)器，減少路由開銷，所以延遲會(huì)稍高。這個(gè)實(shí)驗(yàn)結(jié)果符合預(yù)期。

圖12 平均延遲對(duì)比

3.2.3 平均轉(zhuǎn)發(fā)次數(shù)

平均轉(zhuǎn)發(fā)次數(shù)表示一次數(shù)據(jù)請(qǐng)求的過程中，所有消息的轉(zhuǎn)發(fā)次數(shù)，包括探測(cè)包、確認(rèn)包、興趣包以及數(shù)據(jù)包的轉(zhuǎn)發(fā)次數(shù)。平均轉(zhuǎn)發(fā)次數(shù)越少，表示用于請(qǐng)求數(shù)據(jù)的平均開銷越小。

實(shí)驗(yàn)結(jié)果如圖13所示，傳統(tǒng)NDN算法在實(shí)驗(yàn)中平均一次數(shù)據(jù)請(qǐng)求的消息轉(zhuǎn)發(fā)次數(shù)為2.67，而改進(jìn)后的算法為2.29，改進(jìn)后平均消息轉(zhuǎn)發(fā)次數(shù)明顯降低，這是算法設(shè)計(jì)的路段路由及最遠(yuǎn)距離優(yōu)先轉(zhuǎn)發(fā)的策略能減少路由開銷的體現(xiàn)。

圖13 平均轉(zhuǎn)發(fā)次數(shù)對(duì)比

4 結(jié)語

本文將命名數(shù)據(jù)網(wǎng)絡(luò)應(yīng)用于車載自組織網(wǎng)絡(luò)中，并根據(jù)車載自組織網(wǎng)絡(luò)的特點(diǎn)對(duì)其進(jìn)行改進(jìn)，在命名數(shù)據(jù)網(wǎng)絡(luò)的基礎(chǔ)上，設(shè)計(jì)了新的消息類型，提出了以路段信息作為建立路由的依據(jù)，基于命名數(shù)據(jù)網(wǎng)絡(luò)技術(shù)的車載網(wǎng)數(shù)據(jù)分發(fā)算法。與文獻(xiàn)[12]提出的算法進(jìn)行實(shí)驗(yàn)仿真。從結(jié)果可以看出，本文的優(yōu)化算法具有更高的穩(wěn)定性，能夠使得數(shù)據(jù)訪問及獲取的效率更高，轉(zhuǎn)發(fā)數(shù)據(jù)的開銷更低。

除此之外，對(duì)于命名數(shù)據(jù)網(wǎng)絡(luò)在車載自組織網(wǎng)絡(luò)中的應(yīng)用還有以下幾方面值得研究和探討：表格的設(shè)計(jì)和維護(hù)，包括更完善的表格設(shè)計(jì)與車輛進(jìn)入了新路段時(shí)的表格建立；生產(chǎn)者的移動(dòng)性；除了FIFO之外的緩存策略等。

References)

[1] LIU Y, BI J, YANG J.Research on vehicular Ad Hoc networks [C]// CCDC’ 09: Chinese Control and Decision Conference 2009.Piscataway, NJ, IEEE, 2009: 4430-4435.

[2] JIANG D, DELGROSSI L.IEEE 802.11 p: Towards an international standard for wireless access in vehicular environments [C]// VTC 2008: Proceedings of the 2008 Vehicular Technology Conference.Piscataway, NJ, IEEE, 2008.2036-2040.

[3] HARTENSTEIN H, LABERTEAUX K P.A tutorial survey on vehicular Ad Hoc networks [J].IEEE Communications Magazine, 2008, 46(6): 164-171.

[4] 陳林星，曾曦，曹毅.移動(dòng)Ad Hoc網(wǎng)絡(luò)——自組織分組無線網(wǎng)絡(luò)技術(shù)[M].2版.北京：電子工業(yè)出版社，2012:6-7.(CHEN L X, ZENG X, CAO Y.Mobile Ad Hoc Network—Self-Organized Packet Radio Network Technology [M].2nd ed.Beijing: Publishing House of Electronics Industry, 2012: 6-7.)

[5] LI F, WANG Y.Routing in vehicular Ad Hoc networks: a survey [J].IEEE Vehicular Technology Magazine, 2007, 2(2): 12-22.

[6] ZHANG L, AFANASYEV A, BURKE J, et al.Named data networking [J].ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66-73.

[7] YUAN H, CROWLEY P.Scalable pending interest table design: From principles to practice [C]// INFOCOM 2014: Proceedings of the 2014 IEEE Conference on Computer Communications.Piscataway, NJ: IEEE, 2014: 2049-2057.

[8] SO W, NARAYANAN A, ORAN D, et al.Toward fast NDN software forwarding lookup engine based on hash tables [C]// Proceedings of the Eighth ACM/IEEE Symposium on Architectures for Networking and Communications Systems.New York: ACM, 2012: 85-86.

[9] AMADEO M, CAMPOLO C, MOLINARO A.Enhancing content-centric networking for vehicular environments [J].Computer Networks, 2013, 57(16): 3222-3234.

[10] WANG L, AFANASYEV A, KUNTZ R, et al.Rapid traffic information dissemination using named data [C]// Proceedings of the 1st ACM Workshop on Emerging Name-Oriented Mobile Networking Design—Architecture, Algorithms, and Applications.New York: ACM, 2012: 7-12.

[11] GRASSI G, PESAVENTO D, WANG L, et, al.ACM HotMobile 2013 poster: vehicular inter-networking via named data [J].ACM SIGMOBILE Mobile Computing and Communications Review, 2013, 17(3): 23-24.

[12] GRASSI G, PESAVENTO D, PAU G, et al.VANET via named data networking [C]// INFOCOM 2014: Proceedings of the 2014 IEEE Conference on Computer Communications Workshops.Piscataway, NJ: IEEE, 2014: 410-415.

This work is partially supported by the National Natural Science Foundation of China (61379157), the Science and Technology Planning Project of Guangdong Province (2015B010111001, 2015A010103007), the Science and Technology Program of Guangzhou (201510010068).

DENG Jian, born in 1993, M.S.candidate.His research interests include vehicular Ad Hoc network, named data networking.

DONG Baihong, born in 1993.His research interests include vehicular Ad Hoc network.

CAO Hui, born in 1992, M.S.Her research interests include Ad Hoc network, named data networking.

WU Lijuan, born in 1974, senior engineer.Her research interests include network and application.

ZHANG Bo, born in 1975, senior engineer.His research interests include network and application.

WU Weigang, born in 1976, Ph.D., professor.His research interests include vehicular Ad Hoc network, cloud computing.

Named data networking based data dissemination mechanism for vehicular Ad Hoc network

DENG Jian1*, DONG Baihong1, CAO Hui1, WU Lijuan2, ZHANG Bo2, WU Weigang1

(1.SchoolofDataandComputerScience,SunYat-senUniversity,GuangzhouGuangdong510006,China;2.LaiwuElectricityCorporation,StateGridCorporationofChina,LaiwuShandong271100,China)

Vehicular Ad Hoc Network (VANET) is a highly dynamic communication network, which means it’s a great challenge to design a stable data dissemination mechanism.Applying Named Data Networking (NDN), which focused on the content of the data, to VANET could effectively relive the problems brought by the frequent change of network topology.Firstly, the message types and data structure of NDN were improved.Secondly, the way of establishing routes according to section was put forward with the combination of characteristics of VANET so as to reduce the cost of data dissemination.The simulation results show that compared to the traditional NDN algorithm which is applied to VANET data dissemination, Average Hit Rate (AHR) and Average Forward Times (AFT) can be significantly improved by VANET data dissemination mechanism based on NDN.Therein, the average increase of AHR is about 53 percent points, while the average reduction of AFT is about 0.4 times.Therefore, the improved VANET data dissemination mechanism can improve the efficiency of data dissemination by using the new routing method.

Vehicular Ad Hoc Network (VANET); section information; routing; data dissemination; Named Data Networking (NDN)

2016-07-30;

2016-09-27。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61379157)；廣東省科技計(jì)劃項(xiàng)目(2015B010111001, 2015A010103007)；廣州市科技計(jì)劃項(xiàng)目(201510010068)。

鄧健(1993—)，男，廣東茂名人，碩士研究生，主要研究方向：車聯(lián)網(wǎng)、命名數(shù)據(jù)網(wǎng)絡(luò)； 董柏宏(1993—)，男，廣東茂名人，主要研究方向：車聯(lián)網(wǎng)； 曹慧(1992—)，女，山東青島人，碩士，主要研究方向：車聯(lián)網(wǎng)、命名數(shù)據(jù)網(wǎng)絡(luò)； 吳麗娟(1974—)，女，山東泰安人，高級(jí)工程師，主要研究方向：網(wǎng)絡(luò)及應(yīng)用； 張波(1975—)，男，山東泰安人，高級(jí)工程師，主要研究方向：網(wǎng)絡(luò)及應(yīng)用； 吳維剛(1976—)，男，山東泰安人，教授，博士，主要研究方向：車聯(lián)網(wǎng)、云計(jì)算。

1001-9081(2017)01-0073-06

10.11772/j.issn.1001-9081.2017.01.0073

TP393.01

A