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

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

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

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

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

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

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

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

車載自組織網(wǎng)絡(luò)(VANET)是一個高度動態(tài)的通信網(wǎng)絡(luò)，設(shè)計穩(wěn)定的數(shù)據(jù)分發(fā)機制是一個很大的挑戰(zhàn)。將關(guān)注數(shù)據(jù)內(nèi)容的命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)應(yīng)用于車載自組織網(wǎng)絡(luò)中，能有效緩解網(wǎng)絡(luò)拓撲頻繁變化所帶來的問題。首先，優(yōu)化命名數(shù)據(jù)網(wǎng)絡(luò)的消息類型和數(shù)據(jù)結(jié)構(gòu)；然后，結(jié)合車載自組織網(wǎng)絡(luò)的特性，提出根據(jù)路段建立路由的方式，減少數(shù)據(jù)分發(fā)的開銷。仿真實驗結(jié)果表明，所提出的基于命名數(shù)據(jù)網(wǎng)絡(luò)的車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)機制與應(yīng)用于車載自組織網(wǎng)絡(luò)數(shù)據(jù)分發(fā)的傳統(tǒng)命名數(shù)據(jù)網(wǎng)絡(luò)算法對比，數(shù)據(jù)轉(zhuǎn)發(fā)平均命中率(AHR)提高大約53個百分點，平均轉(zhuǎn)發(fā)次數(shù)減少大約0.4。因此提出的基于命名數(shù)據(jù)網(wǎng)絡(luò)的車聯(lián)網(wǎng)數(shù)據(jù)分發(fā)機制，采用新的路由方式，能夠提高數(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]標準，實現(xiàn)車輛與車輛(Vehicle-to-Vehicle，V2V)或者車輛與路邊單元之間(Vehicle-to-Infrastructure，V2I)的通信[3]。車載自組織網(wǎng)絡(luò)繼承了移動無線自組織網(wǎng)絡(luò)的特性：分布式操作、寬帶有限、節(jié)點移動性與網(wǎng)絡(luò)拓撲動態(tài)性等[4]。除此之外，它還具有通信環(huán)境復(fù)雜、鏈路易斷的難點[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ò)中會有很大的應(yīng)用前景。

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

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

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

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

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

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

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

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

三種數(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é)點根據(jù)收到的消息，建立FIB。消費者需要某種數(shù)據(jù)時，發(fā)送興趣包請求數(shù)據(jù)。收到興趣包的節(jié)點，如果CS中有該數(shù)據(jù)，則直接回復(fù)數(shù)據(jù)包；如果沒有，則把興趣包信息加入到該節(jié)點的PIT中。然后查詢FIB，如果有相應(yīng)的數(shù)據(jù)表項，則從對應(yīng)接口發(fā)出去，否則就丟棄。收到數(shù)據(jù)包的節(jié)點，如果該節(jié)點的PIT有對應(yī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ā)算法

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

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

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

2.1.1 系統(tǒng)角色

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

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

消費者 請求資源的車輛節(jié)點。當車輛節(jié)點需要某資源且FIB中有對應(yīng)記錄時，發(fā)送興趣包請求資源。當FIB沒有記錄時，廣播探測包尋找該資源。

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

2.1.2 消息類型

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

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

圖4 興趣包格式

Fig.4 Format of interest packet

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

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

數(shù)據(jù)包的名字(Name)和跳數(shù)標簽(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é)點它擁有的資源數(shù)據(jù)，其結(jié)構(gòu)與數(shù)據(jù)包一樣。

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

圖6 探測包格式

Fig.6 Format of detect packet

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

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

圖7 確認包格式

Fig.7 Format of confirm packet

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

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

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

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

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

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

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

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

2.2 路由建立

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

算法的主要流程如下：

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

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

3)更新資源包中的必要信息，然后根據(jù)距離設(shè)置定時器，距離上一跳越遠定時器越短。計時結(jié)束之前，若沒有收到其他節(jié)點廣播的同樣的資源包，則將該資源包發(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 資源探測

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

算法的主要流程：

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

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

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

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

算法2 探測包轉(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 確認包轉(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ù)請求

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

算法的主要流程：

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

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

3)車輛節(jié)點收到數(shù)據(jù)包后查詢自己的PIT，如果沒有對應(yīng)表項，則不處理。若有，將數(shù)據(jù)緩存到CS，并刪除對應(yīng)PIT表項，設(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 對比實驗

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

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

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

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

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

3 實驗仿真結(jié)果與分析

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

3.1 仿真環(huán)境

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

要特別說明的是SUMO生成的車輛網(wǎng)絡(luò)拓撲中，道路是雙向的，命名彼此不相同，但是本文提出的改進算法將其視為同一路段，即不考慮道路的方向問題。對比實驗以節(jié)點作為建立路由依據(jù)，因此不考慮路段信息。

3.1.1 仿真配置

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

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

3.1.2 評價指標

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

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

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

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

3.2 仿真結(jié)果

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

3.2.1 平均命中率

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

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

圖11 平均命中率對比

3.2.2 平均延遲

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

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

圖12 平均延遲對比

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

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

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

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

4 結(jié)語

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

除此之外，對于命名數(shù)據(jù)網(wǎng)絡(luò)在車載自組織網(wǎng)絡(luò)中的應(yīng)用還有以下幾方面值得研究和探討：表格的設(shè)計和維護，包括更完善的表格設(shè)計與車輛進入了新路段時的表格建立；生產(chǎn)者的移動性；除了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] 陳林星，曾曦，曹毅.移動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。 基金項目:國家自然科學(xué)基金資助項目(61379157)；廣東省科技計劃項目(2015B010111001, 2015A010103007)；廣州市科技計劃項目(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—)，女，山東泰安人，高級工程師，主要研究方向：網(wǎng)絡(luò)及應(yīng)用； 張波(1975—)，男，山東泰安人，高級工程師，主要研究方向：網(wǎng)絡(luò)及應(yīng)用； 吳維剛(1976—)，男，山東泰安人，教授，博士，主要研究方向：車聯(lián)網(wǎng)、云計算。

1001-9081(2017)01-0073-06

10.11772/j.issn.1001-9081.2017.01.0073

TP393.01

A