鬼佬大哥大
  • / 13
  • 下載費用:30 金幣  

一種基于網絡編碼的車載自組織網絡區域內容分發方法.pdf

關 鍵 詞:
一種 基于 網絡 編碼 車載 組織網絡 區域 內容 分發 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201210165800.X

申請日:

2012.05.25

公開號:

CN102694859B

公開日:

2015.01.28

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):H04L 29/08申請日:20120525|||公開
IPC分類號: H04L29/08; H04L12/18 主分類號: H04L29/08
申請人: 浙江工業大學
發明人: 王萬良; 李桂森; 姚信威; 岑躍峰; 蔣一波; 趙燕偉
地址: 310014 浙江省杭州市下城區潮王路18號
優先權:
專利代理機構: 杭州天正專利事務所有限公司 33201 代理人: 王兵;王利強
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201210165800.X

授權公告號:

102694859B||||||

法律狀態公告日:

2015.01.28|||2012.11.21|||2012.09.26

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

一種基于網絡編碼的車載自組織網絡區域內容分發方法,包括以下步驟:(1)廣播HELLO消息,聲明分發內容與請求數據;(2)HELLO請求消息處理;(3)廣播數據提供本地響應服務;(4)數據接收處理;當接收到的數據和節點緩存的數據線性相關時,丟棄該數據并把發送節點添加進黑名單,在獲得新數據之前禁止向本節點傳輸數據;若接收到的數據線性無關,就在黑名單中檢查發送節點是否存在,若存在就刪除;接收到了一個線性無關的數據時,除了發送節點外,所有和鄰居對應的數據有效性都增加1,然后保存數據包。本發明能降低內容分發延遲、提高效率、提升分發成功率。

權利要求書

1.一種基于網絡編碼的車載自組織網絡區域內容分發方法,其特征在于,所述車
載自組織網絡區域內容分發方法包括以下步驟:
(1)廣播HELLO消息,聲明分發內容與請求數據:
數據源節點在一跳范圍內周期廣播HELLO消息聲明待分發內容的ID,所有位
于分發區域內的節點接收到此HELLO消息后自動成為緩存節點,同樣在一跳范圍
內周期廣播HELLO消息進行待分發內容的聲明以及本地的數據請求;
(2)HELLO請求消息處理,具體包括如下過程:
2a)合格服務節點判斷:節點接收到請求消息后,判斷自己是否為一個合格
服務節點,合格服務節點需同時滿足如下條件:
1)請求節點請求的數據量大于零,對該請求節點的數據有效性大于零;
2)比請求節點更靠近數據源節點,或者請求節點是一個感興趣節點;
3)請求節點沒有接收到本節點發送出去的數據包,或者本節點不在黑名單內;
若節點是一個合格服務節點,則傳輸相應的數據作為一個數據請求的回應,
否則忽略該請求;
2b)緩存內容更新:當本節點接收到一個比自己離數據源節點更遠的節點的
數據請求,且數據有效性為零時,若節點為一個緩存節點且已獲得的數據量已經
達到需要緩存的最大數目,需要進行緩存內容的更新,更新的方法是隨機刪除一
些數據包以騰出空間來請求一些新的數據;
(3)廣播數據提供本地響應服務;
當一個節點接收到數據請求并且為合格服務節點時,就計算需要發送的數據
包個數,計算的方法和緩存節點計算隨機刪除數據包個數的方法相同;根據計算
到的需要發送的數據包個數,節點連續廣播自己所擁有的數據包的線性組合,如
下式所示:
p = Σ i = 1 s c i p i ]]>
其中,p′為新的編碼包,pi為節點當前已經接收到的數據包,ci是從伽羅華
域GF(28)中隨機選取的編碼系數;合格服務節點在廣播數據時,都根據與請求節
點的接近程度分配一個隨機的退避時延窗口,距離越短,退避時延窗口就越小,
如下式所示:

其中,D是發送節點與請求節點之間的距離,MaxRange是節點間最大的一
跳通信距離,而MaxDelay則是最大的回復時延,節點的回復時延就在退避時延
窗口范圍內隨機選取;
給對應的請求節點保存發送出去的數據包ID;
(4)數據接收處理;
當接收到的數據和節點緩存的數據線性相關時,丟棄該數據并把發送節點添
加進黑名單,在獲得新數據之前禁止向本節點傳輸數據;若接收到的數據線性無
關,就在黑名單中檢查發送節點是否存在,若存在就刪除;接收到了一個線性無
關的數據時,除了發送節點外,所有和鄰居對應的數據有效性都增加1,然后保
存數據包。
2.如權利要求1所述的基于網絡編碼的車載自組織網絡區域內容分發方法,其特
征在于:所述步驟(1)中,HELLO消息的內容包括:待分發內容的ID、大小、分
發區域、擁有者、擁有者的地理位置、發送節點的類型、發送節點的地理位置、
請求的數據量、禁止傳輸數據的節點黑名單和最近接收到的數據包ID,其中,黑
名單和最近接收到的數據包ID用Bloom?Filter結構存儲。
3.如權利要求2所述的基于網絡編碼的車載自組織網絡區域內容分發方法,其特
征在于:所述HELLO消息的內容中,請求的數據量q對于不同的節點使用不同的
計算方法,對于感興趣節點q=m-c,其中m為整個分發內容的數據量,c為節
點已經獲得的數據量;對于緩存節點q=Need_Cache-c,其中Need_Cache為
緩存節點需緩存的數據量,動態計算如下:
Need_Cache=m/n
其中n是分發區域內的一跳鄰居數,通過收集周期的HELLO消息動態估計。
4.如權利要求1~3之一所述的基于網絡編碼的車載自組織網絡區域內容分發方
法,其特征在于:所述步驟(2)中,數據的有效性計算規則如下:如果從某個鄰
居節點接收到一個線性無關的數據包,則除了這個鄰居節點之外,此節點相對所
有鄰居節點的數據有效性都增加1;如果從HELLO消息中判斷對方接收到k個本
節點發送的數據包,則相對對方的數據有效性減去k。
5.如據權利要求1所述的基于網絡編碼的車載自組織網絡區域內容分發方法,其
特征在于:所述步驟(2)中,緩存內容更新時應該刪除的數據包個數用下式表達:
min{q/n′,utility(v)}
其中,v是請求節點,utility(v)是本節點對于v的數據有效性,q是v的請求數據
量,當v是緩存節點時,n′=n/2,當v是感興趣節點時n′=n。

說明書

一種基于網絡編碼的車載自組織網絡區域內容分發方法

技術領域

本發明屬于車載自組織網絡內容分發領域,具體涉及一種應用于車載自組織
網絡的基于網絡編碼的區域內容分發方法。

背景技術

隨著無線網絡、電子和車輛技術的迅速發展,車載自組織網絡已經引起了學
術界和工業界的重視。通過車載節點之間、車載節點與路旁基礎設施的無線交互,
可以為車輛提供交通預警信息,降低事故發生的概率;為車輛提供實時交通信息
輔助駕駛與交通管理,提升現有交通道路的運輸效率。

然而,車載自組織網絡的部署是一個逐步的過程,在市場滲透率達到一定程
度之前,很多的交通安全相關的應用由于需要每一輛車都參與而無法有效實施。
而非交通安全相關的數據分發應用,例如停車位置獲取,出租車預定,商業廣告
分發等,不要求道路中所有的車輛都必須參與,因此在車載自組織網絡的發展初
期階段具有很大的應用前景。上述這些非交通安全相關的數據分發應用,都需要
將數據分發到特定的地理區域。

車載自組織網絡中由于節點的高速移動,使得網絡拓撲信息難以準確獲取,
不能依靠維護網絡拓撲信息來傳輸數據。當分發區域較大時,需要多跳傳輸才能
把內容從分發節點傳輸到接收節點,使得分發的時延較大,尤其是分發內容較大
時,造成分發區域邊界的節點難以在離開分發區域前獲取一份完整的分發內容。
同時,在區域分發中,車載節點會頻繁進入與離開指定的分發區域,意味著需要
隨時給新進入分發區域的節點提供分發內容,同時也要容忍輔助節點的隨時離開。
然而,車載自組織網絡業具有能量不受限,信息處理與獲取能力強等特點。因此,
如何結合車載自組織網絡的這些特點,找到一種高效的區域內容分發方法是一個
需要解決的重要技術問題。

發明內容

為了克服已有區域內容分發存在較大延遲、效率較低、分發成功率較低的不
足,本發明提供一種降低內容分發延遲、提高效率、提升分發成功率的基于網絡
編碼的車載自組織網絡區域內容分發方法。

本發明解決其技術問題所采用的技術方案是:

一種基于網絡編碼的車載自組織網絡區域內容分發方法,所述車載自組織網
絡區域內容分發方法包括以下步驟:

(1)廣播HELLO消息,聲明分發內容與請求數據:

數據源節點在一跳范圍內周期廣播HELLO消息聲明待分發內容的ID,所有
位于分發區域內的節點接收到此HELLO消息后自動成為緩存節點,同樣在一跳
范圍內周期廣播HELLO消息進行待分發內容的聲明以及本地的數據請求;

(2)HELLO請求消息處理,具體包括如下過程:

2a)合格服務節點判斷:節點接收到請求消息后,判斷自己是否為一個合格
服務節點,合格服務節點需同時滿足如下條件:

1)請求節點請求的數據量大于零,對該請求節點的數據有效性大于零;

2)比請求節點更靠近數據源節點,或者請求節點是一個感興趣節點;

3)請求節點沒有接收到本節點發送出去的數據包,或者本節點不在黑名單內;

若節點是一個合格服務節點,則傳輸相應的數據作為一個數據請求的回應,
否則忽略該請求;

2b)緩存內容更新:當本節點接收到一個比自己離數據源節點更遠的節點的
數據請求,且數據有效性為零時,若節點為一個緩存節點且已獲得的數據量已經
達到需要緩存的最大數目,需要進行緩存內容的更新,更新的方法是隨機刪除一
些數據包以騰出空間來請求一些新的數據;

(3)廣播數據提供本地響應服務;

當一個節點接收到數據請求并且為合格服務節點時,就計算需要發送的數據
包個數,計算的方法和緩存節點計算隨機刪除數據包個數的方法相同;根據計算
到的需要發送的數據包個數,節點連續廣播自己所擁有的數據包的線性組合,如
下式所示:

p = Σ i = 1 s c i p i ]]>

其中,p′為新的編碼包,pi為節點當前已經接收到的數據包,ci是從伽羅華
域GF(28)中隨機選取的編碼系數;合格服務節點在廣播數據時,都根據與請求節
點的接近程度分配一個隨機的退避時延窗口,距離越短,退避時延窗口就越小,
如下式所示:


其中,D是發送節點與請求節點之間的距離,MaxRange是節點間最大的一跳
通信距離,而MaxDelay則是最大的回復時延,節點的回復時延就在退避時延窗
口范圍內隨機選取;

給對應的請求節點保存發送出去的數據包ID;

(4)數據接收處理;

當接收到的數據和節點緩存的數據線性相關時,丟棄該數據并把發送節點添
加進黑名單,在獲得新數據之前禁止向本節點傳輸數據;若接收到的數據線性無
關,就在黑名單中檢查發送節點是否存在,若存在就刪除;接收到了一個線性無
關的數據時,除了發送節點外,所有和鄰居對應的數據有效性都增加1,然后保
存數據包。

進一步,所述步驟(1)中,HELLO消息的內容包括:待分發內容的ID、大
小、分發區域、擁有者、擁有者的地理位置、發送節點的類型、發送節點的地理
位置、請求的數據量、禁止傳輸數據的節點黑名單和最近接收到的數據包ID,其
中,黑名單和最近接收到的數據包ID用Bloom?Filter結構存儲。

再進一步,所述HELLO消息的內容中,請求的數據量q對于不同的節點使
用不同的計算方法,對于感興趣節點q=m-c,其中m為整個分發內容的數據量,
c為節點已經獲得的數據量;對于緩存節點q=Need_Cache-c,其中
Need_Cache為緩存節點需緩存的數據量,動態計算如下:

Need_Cache=m/n

其中n是分發區域內的一跳鄰居數,通過收集周期的HELLO消息動態估計。

更進一步,所述步驟(2)中,數據的有效性計算規則如下:如果從某個鄰居
節點接收到一個線性無關的數據包,則除了這個鄰居節點之外,此節點相對所有
鄰居節點的數據有效性都增加1;如果從HELLO消息中判斷對方接收到k個本節
點發送的數據包,則相對對方的數據有效性減去k。

所述步驟(2)中,緩存內容更新時應該刪除的數據包個數用下式表達:

min{q/n′,utility(v)}

其中,v是請求節點,utility(v)是本節點對于v的數據有效性,q是v的請求數據
量,當v是緩存節點時,n′=n/2,當v是感興趣節點時n′=n。

本發明的技術構思為:利用隨機線性網絡編碼技術,把分發內容變成無差異、
地位對等的編碼包,然后把這些編碼包根據網絡節點密度隨機、動態地緩存在指
定分發區域的所有節點上,為在分發區域中新出現的節點提供迅速的本地響應服
務,使得所有的數據請求都能夠在一跳范圍內得到服務,獲取完整的分發內容。

本發明的有益效果主要表現在:1.自適應車載自組織網絡頻繁的節點密度變
化,能根據節點密度動態調整數據緩存數量,對分發區域內節點的頻繁進入與離
開不敏感;2.數據請求可以在一跳范圍內得到服務,避免了多跳傳輸,降低了內
容分發延遲;3.遠離數據源節點的分發區域邊界的服務質量得到有效的提高,即
使只從分發區域邊界附近快速經過的節點也能以較高的概率獲得完整的分發內
容,提高了整個系統的內容分發成功率。

附圖說明

圖1為區域內容分發系統示意圖;

圖2為分發內容聲明與數據請求流程圖;

圖3為請求消息處理流程圖;

圖4為緩存內容更新流程圖;

圖5為數據發送處理流程圖;

圖6為數據接收處理流程圖。

具體實施方式

下面結合附圖對本發明作進一步的描述。

圖1是一個區域內容分發系統示意圖,數據源節點需要將分發內容分發到兩
跳范圍內的分發區域。從圖1可以看到,A、B、C和D四個感興趣節點都能從鄰
近的一跳范圍內獲得響應服務。

參照圖1-圖6,本發明的具體實施步驟如下:

(1)廣播HELLO消息,聲明分發內容與請求數據

數據源節點在一跳范圍內周期廣播HELLO消息聲明待分發內容的ID,所有
位于分發區域內的節點接收到此HELLO消息后自動成為緩存節點,同樣在一跳
范圍內周期廣播HELLO消息進行待分發內容的聲明以及本地的數據請求。

如圖2所示,首先計算本節點需要請求的數據包數量。對于數據源節點,不
必獲取更多的數據,請求的數據包數量必然為零。對于感興趣節點,總共需要的
數據包數量為整個分發內容的數據量m。為了令任意一個感興趣節點都可以從一
跳鄰居中獲取一份完整的分發內容,對于緩存節點,總共需要緩存的數據包數量
Need_Cache動態計算如下:

Need_Cache=m/n

其中n是分發區域內的一跳鄰居數,可通過收集周期的HELLO消息動態估計。

設c為節點已經獲得的數據量,q為節點請求的數據量,則對于感興趣節點
q=m-c,對于緩存節點q=Need_Cache-c。

若q=0,則HELLO消息包的廣播周期間隔為1秒,否則為α秒,α取值0.03
以便在更短的時間內發送數據請求。在計時器超時前若接收到新的數據包,則取
消計時器。計時器超時后,則添加相應的信息到HELLO消息包中并廣播,HELLO
消息包的內容包括:待分發內容的ID、大小、分發區域、擁有者、擁有者的地理
位置、發送節點的類型、發送節點的地理位置、請求的數據量、禁止傳輸數據的
節點的黑名單和最近接收到的數據包ID。然后判斷節點是否離開分發內容的分發
區域,若沒有離開,則繼續重新設定計時器周期廣播HELLO消息。

某個節點需要禁止傳輸數據的黑名單和最近接收到的數據包ID可能有多個,
它們分別以IP地址和正整數的形式出現,若保存此原始信息,HELLO消息消息
數據包的大小將會變得較大,從而造成很大的通訊負載,效率較為低下。因此,
本發明使用一個大小被固定為32字節的Bloom?Filter結構來保存這些信息。

(2)HELLO請求消息處理

如圖3所示,節點接收到一個HELLO消息后,先判斷發送節點請求的數據
量。若此數據量為零,則表示發送節點僅僅是聲明分發區域內要分發的內容,忽
略該請求即可。若此數據量不為零,則需要計算數據的有效性進一步判斷本節點
是否是一個合格的服務節點。

2a)合格服務節點判斷

節點接收到請求消息后,判斷自己是否為一個合格服務節點,合格服務節點
需同時滿足如下條件:

1)請求節點請求的數據量大于零,對該請求節點的數據有效性大于零

2)比請求節點更靠近數據源節點,或者請求節點是一個感興趣節點

3)請求節點沒有接收到本節點發送出去的數據包,或者本節點不在黑名單內
?若節點是一個合格服務節點,則傳輸相應的數據作為一個數據請求的回應,
否則忽略該請求。

其中,數據的有效性計算規則如下:如果從某個鄰居節點接收到一個線性無關
的數據包,則除了這個鄰居節點之外,此節點相對所有鄰居節點的數據有效性都
增加1。如果從HELLO消息中判斷對方接收到k個本節點發送的數據包,則相對
對方的數據有效性減去k。

如圖3所示,根據已發送的數據包ID和HELLO消息中保存的已接收數據包
ID,可以得出對方接收到的數據包個數k,則除了本節點是數據源節點的情況外,
本節點對于對方的數據有效性需要減去k,若數據有效性小于零,則轉到2b)處
理,否則繼續判斷。若請求節點不是感興趣節點且本節點離數據源節點更遠,則
不需要請求響應,直接結束本次處理,這么處理是為了使數據能從數據源節點向
分發區域的邊界擴散。若請求節點是感興趣節點或者本節點離數據源節點更近,
就繼續判斷對方接收到的數據包個數。若k=0,即對方沒有接收到本節點發送的
數據包,本節點就是一個合格服務節點,被允許繼續發送數據包,轉步驟(3)。
若k>0,則清空為對方保存的已發送數據包ID。若此時本節點不在黑名單內,則
也允許繼續發送數據,轉步驟(3),否則可認為對方接收到本節點發送的數據包
是線性相關的,那么需要設定本節點的數據有效性為零,轉2b)。

2b)緩存內容更新

如圖3所示,有兩種情況本節點相對數據請求節點的數據有效性為零。一種情
況是節點在接收到數據請求前的數據有效性就已經為零,另一種情況是雖然在接
收到請求前數據有效性不為零,但請求節點已經收到本節點發送的數據包卻仍然
指定本節點為黑名單,這說明本節點的數據與請求節點的數據線性相關,為此主
動設置數據有效性為零。

為了盡可能在每一次數據請求中都能提供本地響應服務,數據有效性為零時需
要對緩存的內容進行更新,其更新過程如圖4所示。節點依次判斷如下三個條件:
本節點更接近數據源節點;本節點是緩存節點;節點已達緩存限制。若節點滿足
這全部三個條件,就隨機刪除一些緩存的編碼包以便騰出空間接收新編碼包,應
該刪除的數據包個數可用下式表達:

min{q/n′,utility(v)}

其中v是請求節點,utility(v)是本節點對于v的數據有效性,q是v的請求數
據量,當v是緩存節點時,n′=n/2,當v是感興趣節點時n′=n。

(3)廣播數據提供本地響應服務

當一個節點接收到數據請求并且為合格服務節點時,就計算需要發送的數據
包個數,計算的方法和緩存節點計算隨機刪除數據包個數的方法相同。

根據計算到的需要發送的數據包個數,節點連續廣播自己所擁有的數據包的
線性組合,如下式所示:

p = Σ i = 1 s c i p i ]]>

其中p′為新的編碼包,pi為節點當前已經接收到的數據包,ci是從伽羅華域
GF(28)中隨機選取的編碼系數。

如圖5所示,為了減少沖突,合格服務節點在廣播數據時,都根據與請求節點
的接近程度分配一個隨機的退避時延窗口,距離越短,退避時延窗口就越小,如
下式所示。


其中D是發送節點與請求節點之間的距離,根據請求節點在HELLO消息包中
聲明的位置和本節點的位置計算得到,MaxRange是節點間最大的一跳通信距離,
而MaxDelay則是最大的回復時延。節點的回復時延就在退避時延窗口范圍內隨
機選取。

另外,為了利用數據包ID作為一個數據接收的確認,還需要給對應的請求節
點保存發送出去的數據包ID。

服務節點循環上述過程直到指定的數據包個數被發送完畢。

(4)數據接收處理

如圖6所示,當一個節點位于分發區域內時可以接收數據,即使此節點沒有
發出數據請求,也必須偵聽所有的數據發送來處理緩存內容線性相關的情況。如
果此節點不是一個感興趣節點,則為了保證數據從數據源節點向分發區域邊界擴
散,還需要發送節點比接收節點更靠近數據源節點。當接收到的數據和節點緩存
的數據線性相關時,丟棄該數據并把發送節點添加進黑名單,在獲得新數據之前
禁止向本節點傳輸數據。若接收到的數據線性無關,就在黑名單中檢查發送節點
是否存在,若存在就刪除。由于接收到了一個線性無關的數據,所以除了發送節
點外,所有和鄰居對應的數據有效性都增加1,然后保存數據包。

關于本文
本文標題:一種基于網絡編碼的車載自組織網絡區域內容分發方法.pdf
鏈接地址:http://www.wwszu.club/p-6420780.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大