一種基於社會網絡的車載自組織網絡路由方法
2023-04-30 17:40:26 1
一種基於社會網絡的車載自組織網絡路由方法
【專利摘要】本發明公開了一種基於社會網絡的車載自組織網絡路由方法，屬於車載無線網絡【技術領域】。該方法包括：（1）利用鄰居節點信息計算節點的方向角度和效用值；（2）路段上的節點採用加入緩存機制的貪婪算法，路口節點選擇在角度閾值範圍內效用值最大且大於當前節點效用值的鄰居節點作為下一跳轉發中繼；（3）通過Q學習算法輔助路由算法，使車輛節點從自身歷史轉發動作中學習，節點將選擇使獎勵函數取得最大收斂值的鄰居節點作為下一跳轉發器。本方法減小了路由算法的複雜度，降低了系統開銷，同時利用Q學習算法輔助路由選擇，使數據分組沿著具有最小跳數的路徑傳輸，從而減小了時延；提高了數據分組的投遞率，減小了端到端時延和系統資源的消耗。
【專利說明】—種基於社會網絡的車載自組織網絡路由方法
【技術領域】
[0001]本發明屬於車載無線網絡【技術領域】，涉及一種基於社會網絡的車載自組織網絡路由方法。
【背景技術】
[0002]延遲容忍網絡(Delay Tolerant Networks以下簡稱DTNs)中，從源到目的地通常不存在端到端的穩定路徑，網絡經常處於間斷連接的狀態。而車載自組織網絡(VehicularAd Hoc Networks以下簡稱VANETs)作為DTNs的一種典型範例，由於各種無線設備(例如，手機，GPS設備)快速普及和廣泛使用，近年來引起了越來越多的關注。社會網絡分析致力於研究社會實體之間的關係、模式以及這些關係的應用，利用節點之間的社會關係選擇合適的下一跳節點進行消息轉發，能建立一個更加可靠的路由機制。在VANETs中，在利用網絡基礎設施或端到端的連接的同時，也可以利用社會關係，使車輛之間也能夠實現相互通信，且能實現車輛與路邊設施相互通信，進而獲取網絡服務。儘管如此，間斷和不確定的連接使VANETs中的數據傳輸仍然是一個十分具有挑戰性的問題。因此，充分利用地理信息和車輛之間的社會關係，設計適用於車載自組織網絡的DTN路由也成為路由協議研究的一個熱點問題。
[0003]在車載自組織網中，若當前時刻不存在一條到目的地的路徑，傳統的路由協議在這種情況下將丟棄分組，而機會路由則使用延時容忍轉發策略傳輸數據分組，車載自組織網絡中典型的DTN路由包括VADD、SADV、MaxProp、STDFS等。在車載自組織網中，還常利用地理信息和社會關係進行路由選擇，常見的地理路由包括GPSR、GPCR等，而利用社會網絡的路由協議包括Label、SimBet、BubbleRap等。
[0004]車載自組織網絡中DTN路由協議的目的是為了減小數據分組的丟失，提高路由協議端到端的可靠性。而如何高效利用地理信息和社會關係使節點在進行下一跳轉發器選擇，使數據分組能夠沿著更加可靠的路徑快速傳輸到目的地，增加投遞率並降低時延和系統開銷是一個新的挑戰和機遇。
【發明內容】
[0005]有鑑於此，本發明的目的在於提供一種基於社會網絡的車載自組織網絡路由方法，在路口選擇效用值較高的鄰居節點作為下一跳轉發器，同時利用Q學習算法輔助路由選擇，從而減小路由的時延和跳數，提高數據分組的投遞率。
[0006]為達到上述目的，本發明提供如下技術方案:
[0007]—種基於社會網絡的車載自組織網絡路由方法，該路由方法包括以下步驟:步驟一:節點通過GPS定位系統和hello消息包獲取節點信息,並計算節點的方向角度Θ和兩個社會性的效用指標:中心度Bet和活躍度Act，其中鄰居節點的方向角度Θ利用餘弦定理求得，節點的中介中心度Bet利用自我網絡的概念求得，節點活躍度Act通過統計時間周期T內鄰居節點的變化情況求得；步驟二:將節點中心度Bet和活躍度Act加權求和計算得到節點的綜合效用值U，其中在活躍度基礎上考慮了速度因素，避免把數據分組傳輸給速度較小的車輛節點；
[0008]步驟三:路段節點工作在直路模式，採用改進的GPSR路由算法，即加入緩存機制的貪婪轉發；路口節點工作在路口模式，路口節點將選擇方向角度在角度閾值範圍內效用值最高且高於當前節點效用值的鄰居節點作為下一跳轉發節點；步驟四:採用基於歷史轉發動作的Q學習算法輔助路由選擇，將路由問題映射成強化學習框架中的狀態空間，在學習過程中，根據收斂後的Q值，選擇最佳的轉發動作。
[0009]進一步，在步驟一中，VANETs假設每輛車都配置了 GPS導航系統，可以獲得網絡中車輛節點的位置、方向和速度等基本信息，車輛節點通過周期性地發送Hello消息包來構建和更新鄰居列表，該鄰居列表用於記錄一跳範圍內的節點信息。根據當前節點M、鄰居節點N和目的節點D的坐標，利用餘弦定理計算方向角度
【權利要求】
1.一種基於社會網絡的車載自組織網絡路由方法，其特徵在於:該路由方法包括以下步驟: 步驟一:節點通過GPS定位系統和hello消息包獲取節點信息,並計算節點的方向角度和兩個社會性的效用指標:中心度和活躍度，其中方向角度利用餘弦定理求得，中心度利用自我網絡的概念求得，活躍度通過統計一段時間周期內鄰居節點的變化求得； 步驟二:將中心度和活躍度加權求和計算節點的綜合效用值U ; 步驟三:路段節點採用加入緩存機制的貪婪轉發，路口節點選擇在角度閾值範圍內效用值最高且高於當前節點效用值的鄰居節點作為下一跳轉發節點； 步驟四:採用基於歷史轉發動作的Q學習算法輔助路由選擇，將路由問題映射成強化學習框架中的狀態空間，在學習過程中，根據收斂後的Q值，選擇最佳的轉發動作。
2.根據權利要求1所述的一種基於社會網絡的車載自組織網絡路由方法，其特徵在於:在步驟一中，車載自組織網絡中的節點利用GPS定位系統和hello消息包獲取節點信息，節點通過周期性地發送hello消息進行信息交互，建立、維護並更新鄰居列表，根據當前節點M、鄰居節點N和目的節點D的地理位置，利用餘弦定理計算鄰居節點N的方向角度
3.根據權利要求1所述的一種基於社會網絡的車載自組織網絡路由方法，其特徵在於:在步驟二中，節點的綜合效用值利用中心度和活躍度加權相加求得，其中在活躍度的基礎上加上了速度因素，防止把數據分組傳輸給速度較小的車輛，節點m的效用值用下式確定:
4.根據權利要求1所述的一種基於社會網絡的車載自組織網絡路由方法，其特徵在於:在步驟三中，節點根據GPS導航系統和電子地圖判定自身的節點類型:路口節點、路段節點；節點通過以下步驟發送數據包: 1)若將要發送數據的節點是路口節點，則按路口模式轉發數據分組；若為路段節點，則按直路模式工作； 2)直路模式:在直路模式下，節點採用加入緩存機制的貪婪轉發方式，即節點採用貪婪算法尋找下一跳轉發節點，該轉發節點在當前節點所有鄰居節點中距離目的節點最近；若當前節點所有鄰居節點到目的節點的距離都比當前節點到目的節點的距離遠，則數據分組將由當前節點緩存，當前節點攜帶數據分組向前運動，直到遇到下一個貪婪節點； 3)路口模式: 31)路口節點按步驟2計算當前時刻本節點U值，提取數據分組中的目的地信息，遍歷鄰居列表，按步驟I計算鄰居節點的方向角度，從方向角度在規定角度閾值範圍內的鄰居節點中查找確定近期是否有到相同目的地且效用值U大於當前節點的鄰居節點，如果存在這樣的鄰居節點，則將數據分組發送到具有最大效用值U的鄰居節點；如果具有最大效用值U的節點為本節點，則將數據分組放入對應目的地地址的緩存表中，並進入步驟32)； 32)提取數據分組中的目的地地址，生成一個包含該地址的RREQ(路由請求消息)分組，並周期性地廣播RREQ ； 33)單跳鄰居車輛接收到RREQ，每隔5秒取一次中心度和活躍度，並統計5此的平均值，設置α，β的值，調整U，使其最大，並將包含U值的路由回復消息RREP返回給本車； 34)節點接收到RREP消息後，提取RREP中的「目的地地址，U，鄰居節點地址」對，對於每一個目的地地址，建立一個本地列表，在新建立的鄰居表項的時候，同時啟動一個定時器，定時器到期的路由表項將被刪除，按步驟31)的方式檢查鄰居列表，決定是發送數據分組到具有最大U的鄰居，還是啟動RREQ過程； 4)數據包在道路拓撲上根據攜帶數據的節點位置使用對應的模式，直到傳輸至目的或者因到期而丟棄。
5.根據權利要求1至4中任一項所述的一種基於社會網絡的車載自組織網絡路由方法，其特徵在於:在步驟四中，採用基於歷史轉發動作的Q學習算法輔助路由選擇，將路由問題映射成強化學習框架中的狀態空間，在VANETs中，將整個網絡看成是一個系統，系統狀態根據節點是否持有數據分組來定義。
【文檔編號】H04W40/24GK103702387SQ201410008349
【公開日】2014年4月2日 申請日期:2014年1月8日 優先權日:2014年1月8日
【發明者】唐倫, 古曉琴, 陳前斌 申請人:重慶郵電大學