車輛自組織網絡中基於預測的交叉路口處的路由方法
2023-06-11 07:31:11
專利名稱：車輛自組織網絡中基於預測的交叉路口處的路由方法
技術領域：
本發明屬於通信技術領域，主要涉及車輛自組織網絡VANET中的路由方法，可用 於對城市場景中道路交叉口處的路由決策。
背景技術：
VANET的一個重要應用是提高交通效率及乘客出行的便利性，這些應用一般都需 要進行遠距離的數據傳輸，由於無線傳輸距離的限制，就需要用到多跳傳輸。如何設計高效 的路由協議，將數據成功發送到目的地是VANET領域中一個重要的研究方向。VANET與移動自組織網絡MANET具有相似的特性，它們都是無固定基礎設施支撐、 由分散的移動節點組成的自組織無線網絡。因此，VANET最初採用的路由協議是MANET中 成熟的路由協議，如AODV、GSR等，並針對其中的不足加以改進。由於VANET中節點的高速 運動和網絡拓撲的快速變化，加上GPS等定位技術的快速發展及普及，無狀態的地理路由 技術是其中最適用的技術。由Brad Karp等提出的GPSR協議(GPSR :Greedy Perimeter Stateless Routing for Wireless Networks)是一種應用最廣的基於地理位置的路由協 議，它結合貪婪轉發和基於右手準則的邊界轉發，在節點選擇下一跳時，根據鄰節點列表中 記錄的鄰節點位置和分組中存儲的目的地位置信息，選擇位於自己一跳傳輸範圍內距目的 地最近的節點。在遇到局部最優問題時，即在當前節點的一跳傳輸範圍內沒有比自己距目 的地更近的節點存在，轉為邊界轉發。該邊界轉發是先將網絡的拓撲構造成平面圖，這個平 面圖中的邊只在端點處相交，然後按右手準則將分組沿著平面圖的邊界轉發到目的節點。 Fan Li 等在文獻 Routing in Vehicular Ad Hoc Networks :A Survey 中對 GPSR 做出了如 下評價GPSR在節點均勻分布的自由開放空間中表現很好，但在障礙物較多的城市場景中 性能急劇下降。導致性能下降的因素有城市中的高大建築物和樹木造成節點間不能直接 通信，貪婪轉發因此受限；構造平面圖時會導致網絡的割裂，致使分組無法發送；節點的高 度移動性會造成路由環路等。針對城市中障礙物影響的問題，Lochert等提出了採用基於道路拓撲的分組轉發 協議GPCR(Geographic Routing in City Scenarios)。該轉發協議利用了地圖構成的自 然平面圖道路是圖的邊，交叉口是圖的結點。分組在這個平面圖上沿著道路轉發，交叉路 口是分組進行路由決策的唯一地方。為了不錯過任何一條能將分組發往目的地的道路，分 組在傳輸的過程中必須在經過的每個交叉口停留以做路由決策，確定下一條傳輸分組的路 段。這種方法在一定程度上提高了分組的傳遞率，減小了分組進入局部最優問題的概率。但 實際上分組並不需要轉發到沿途的各個交叉口處，若分組不需改變傳輸方向就可以繼續採 用貪婪轉發，此時將分組轉發到交叉口有可能會增加路由跳數，如圖1所示，實線所示的傳 輸過程比虛線所示的多了一跳。另外，當大量分組都同時發送到同一交叉口時，還有可能造 成網絡阻塞、分組碰撞、增加時延。只有當需要改變傳輸方向時才應轉發到交叉口處。針對上述問題，KevinC. Lee 等提出了 GpsrJ+協議(Enhanced Perimeter Routing for Geographic Forwarding Protocols in Urban Vehicular Scenarios),主要改進了交叉路口處的路由策略，使得分組只在需要改變傳輸方向時才在交叉口處停留，否則仍採用 貪婪模式將分組轉發到距離目的地最近的下一跳，以減少跳數。其主要思想為如果當前節 點的鄰節點中存在交叉口節點，即位於交叉口處的節點，就讓當前節點做出如下預測若該 交叉口節點接收到分組，它將會選擇哪個節點作為下一跳，如果預測所得下一跳節點與當 前節點的最遠鄰節點在同一路段上，則直接將分組轉發給最遠鄰節點；否則，轉發給相鄰的 交叉口節點進行路由決策。這樣分組只會發送到關鍵的交叉口節點上，該節點必然會改變 分組原來的傳輸方向。GpsrJ+的預測方法是利用道路拓撲圖計算各相鄰路段的中心點，再 計算出前節點與哪條路段的中心點連線符合右手準則，符合的路段就是分組將發往的路段 方向。圖1說明了 GPCR和GpsrJ+協議在交叉口處的數據傳輸過程，圖中實線箭頭是GPCR 的轉發過程，虛線箭頭是GpsrJ+的轉發過程，可見GpsrJ+較GPCR能有效地減少傳輸跳數。為了進行預測，GpsrJ+採用了增強的信標每個節點需要在Hello分組中加入鄰 節點所在的路段信息，即路段ID。通過這個信息當前節點可以知道交叉口節點在哪個方向 的路段上有鄰節點，從而預測交叉口節點將會把分組發往哪個方向。這樣，每個節點的鄰居 列表存儲的信息有一跳鄰居節點的位置信息，兩跳鄰居節點所在的路段ID。GpsrJ+能夠提高分組的傳遞率，減少分組傳輸的跳數，縮短分組陷入局部最優問 題的時間。但存在以下幾個問題①僅根據交叉口的一跳鄰居節點選擇轉發方向，沒有考 慮路段上的節點密度情況，有可能將分組轉發到車輛密度低的路段上，造成分組無法傳輸， 如圖2所示，A節點攜帶目的地為D的數據分組，交叉口節點根據自己一跳鄰節點的信息將 分組發送到B節點，但B所在路段車輛密度很低，導致了網絡分裂，致使分組不能繼續轉發。 ②選擇下一跳節點時沒有考慮車輛的行駛方向，這樣會出現兩輛行駛方向相反的車輛傳輸 數據的情況，這有可能造成路由環路，同時由於車輛高速行駛，在選擇時刻處於節點傳輸範 圍邊界的車輛，由於它離目的地最近，會被選擇作為下一跳，但數據傳輸結束之前，該節點 有可能已經移出了這個範圍。③改進的信標會造成額外的網絡開銷，依協議的運行方式，兩 跳鄰居信息只在交叉路口預測的時候用，所有節點發送的信標都攜帶兩跳鄰居路段信息會 加重網絡負載，非交叉口節點發送兩跳鄰居信息完全沒有必要。J. Nzouonta等提出的RBTV和M. Jerbi等提出的GyTAR路由協議都用到了實時車 輛密度信息作為路由選擇的參考因素，後者詳細介紹了流量信息的獲取方法。如圖3所示， 該方法首先將道路分成固定的小區域單元，區域單元的面積取決於車輛的無線傳輸範圍， 根據其位置坐標每個單元被分配一個唯一的標識號ID。每個單元內的車輛組成一個簇，最 靠近單元中心的車輛作為簇頭，由簇頭節點計算本簇內的節點密度，然後通過在簇間傳遞 單元密度分組CPD來獲得整條路段的密度。CPD分組由即將離開本路段的節點發起，然後這 個分組由各單元的簇頭更新密度信息並繼續傳遞，直到到達交叉路口，這時廣播CPD分組， 以使交叉路口中的車輛都能收到密度信息，這個過程如圖3所示。GyTAR對節點密度的分析 包括平均每單元的車輛數和單元密度分布的標準偏差，通過這兩個值和下一個交叉路口到 目的地的距離為每條路段計算一個權值。GyTAR和很多其它考慮車輛密度的協議都是認為 密度越大越好，單從路由的角度考慮這是合理的，但綜合MAC層來考慮，節點密度越大，發 送節點和分組數就會越多，從而節點接入信道的時間就越長，這樣就會增加分組的傳輸時 延，反而不利用分組的快速發送。因此，對密度信息需進行合理的利用。
發明內容
本發明的目的在於克服上述已有技術的不足，提出一種車輛自組織網絡中基於預 測的交叉路口處的路由方法，在當前節點進行預測時考慮整條路段的密度信息和路徑長 度，避免把分組發送到網絡連接中斷的路段上，並綜合考慮MAC層節點接入信道的時延，對 密度信息做出合理利用，為分組選擇最佳的傳輸路徑，減小分組的傳輸時延。實現本發明目的的技術思路是在當前節點進行預測時，根據交叉口節點提供的 各相鄰路段的密度信息和下個交叉口到目的地的距離，為各相鄰交叉口計算一個權值，選 擇權值最大的交叉口作為傳輸分組的下一臨時目的地。為了進行預測分析，在交叉口節點 的Hello分組中加入各相鄰路段的密度信息。當節點在路段上採用貪婪轉發時，若所選節 點是位於傳輸範圍邊界且與發送節點行駛方向相反的車輛，則選擇距目的地次近的節點， 也就是選擇質量穩定的鏈路發送數據。其具體步驟包括如下 (1)車輛自組織網絡中的節點根據其位置檢測自己是否位於交叉路口，若是，用自 己的節點標識號、位置、行駛方向和已知的密度信息構造成Hello分組，並做周期性廣播； 否則，只用自己的節點標識號、位置和行駛方向構造成Hello分組並做周期性廣播，位於廣 播節點無線傳輸範圍內的節點都能收到這個分組，接收到Hello分組的節點把分組中包含 的信息存儲於自己的鄰居列表中；(2)當車輛自組織網絡中的任一節點接收到數據分組時，檢查分組中的目的地址 域，若目的節點是自己，直接提交給上層，路由協議運行結束；否則，檢查鄰居列表中存儲的 數據格式，判斷鄰節點中是否存在交叉口節點，若存在，執行步驟⑶；否則，轉到步驟(5)；(3)提取鄰居列表中存儲的密度信息，結合下個交叉口到目的地的距離，分別計算 各相鄰交叉口的權值，並選權值最大交叉口的標識號填入分組的動態地址域，替代原標識 號；(4)比較所選交叉口的相應路段是否與當前節點所在路段的方向一致，若一致，執 行步驟(5)；否則，將分組發送給交叉口節點，該交叉口節點根據分組中的交叉口標識號發 送分組，返回步驟⑵；(5)獲取當前節點傳輸範圍內距目的地最近的節點，檢查其行駛方向是否與當前 節點一致，若一致，發送分組給此節點，返回步驟O)；否則，執行步驟(6)；(6)檢測該節點是否處於當前節點傳輸範圍的邊界，若是，重新選擇距目的地次近 的節點，並發送分組給此節點；否則，直接發送分組給該節點，返回步驟(2)重新開始。本發明與現有技術相比，具有如下優點(1)本發明由於在交叉口選擇傳輸路段時，綜合考慮路徑長度和道路節點密度對 數據傳輸的影響，使得所選傳輸路徑既具有儘量短的傳輸距離，又具有穩定的網絡連接性 保證分組的有效傳輸；(2)本發明由於採用貪婪算法獲取當前節點傳輸範圍內距目的地最近的節點時， 同時還檢查所選節點是否位於當前節點傳輸範圍邊界且與當前節點行駛方向相反，能夠避 免將分組發送到質量不穩定的鏈路上，減少了數據傳輸出錯的概率。(3)本發明由於考慮到密度對分組傳輸的雙重影響，通過選擇權值最大的交叉口 作為下個臨時目的地，即選擇最優的傳輸路徑，這樣既能避免選擇節點密度稀疏的路段傳 輸數據，又能避免選擇密度過大的路段，從而可以提高數據的傳遞率，減少數據傳輸時延。
圖1是GPCR協議和GpsrJ+協議在交叉口處傳輸分組示意圖；圖2是GpsrJ+協議運行時將傳輸分組發送到網絡連接中斷路段的示意圖；圖3是GyTAR協議獲取密度信息的示意圖；圖4是本發明的流程圖；圖5是本發明具體實施的應用場景示意圖。
具體實施例方式假設車輛S要發送一個數據分組給位於交叉口 J4的停車場預約一個停車位，在當 前時刻，分組傳輸到節點A，此時進行路由決策。其應用場景如圖5所示，它是一個城市交通 概況圖。由圖可知，Jl是當前交叉口，與之相鄰的交叉口有J2、J3和J5，其中J2和J3是候 選交叉口，與J2相應的路段是R2，與J3相應的路段是R3。在本場景中節點B位於當前交叉口，節點A運行路由協議的具體實施步驟參照圖 4，描述如下:步驟1 構造Hello分組並廣播。車輛自組織網絡中的節點通過GPS定位技術和車載道路地圖，確定自己是否位於 交叉口，若是位於交叉口的節點，其構造並廣播的Hello分組中包含自己的節點標識號、位 置、行駛方向已知的各相鄰路段的密度信息，該密度信息是指路段中每個單元的節點密度 值；若是道路上的一般節點，其構造並廣播的Hello分組中只包含自己的節點標識號、位置 和行駛方向。由於城市道路中車輛的行駛速度較慢，本發明中Hello分組的廣播周期設為 ls，接收到Hello分組的所有節點複製其中的數據存儲於鄰居列表中，更新鄰居列表中的 fn息ο步驟2 =A節點檢查分組的目的地址，並檢測鄰節點中是否存在交叉口節點。
A節點檢查分組的目的地址域，該目的地址標識的是停車場，而非A節點，A節點確 定目的不是自己之後，查詢鄰居列表中存儲的數據是否有包含密度信息的條目，由於A節 點的鄰節點B位於交叉口，因此A節點檢測到節點B的信息中存在包含密度信息的條目，從 而確定鄰節點中存在交叉口節點。步驟3 計算各相鄰交叉口的權值，並選權值最大的交叉口作為下個臨時目的地。在圖5所示的應用場景中當前交叉口 Jl到目的地J4的距離Di = 1.8km，相鄰交 叉口 J2到J4的距離Dj2 = 1. 5km, J3到J4的距離Dj3 = Ikm ；R2路段有3個單元，即Nc2 = 3，密度信息為=N21 = 16，N22 = 8，N23 = 6，R3路段有兩個單元，即Nc3 = 2，密度信息為=N31 =14，N32 = 16 ；首先，根據平均單元密度計算公式Μ =，把R2路段的密度值代入到該
丄、C Z=I
平均單元密度計算公式中，得到R2路段的平均單元密度巡=1/3X (16+8+6) = 10，把 R3路段密度值代入到該平均單元密度計算公式中，得到R3路段的平均單元密度為= 1/2 X (14+16) = 15 ；
然後，根據單元密度的標準偏差計算公式
權利要求
1.一種車輛自組織網絡中基於預測的交叉路口處的路由方法，包括如下步驟(1)車輛自組織網絡中的節點根據其位置檢測自己是否位於交叉路口，若是，用自己的 節點標識號、位置、行駛方向和已知的密度信息構造成Hello分組，並做周期性廣播；否則， 只用自己的節點標識號、位置和行駛方向構造成Hello分組並做周期性廣播，位於廣播節 點無線傳輸範圍內的節點都能收到這個分組，接收到Hello分組的節點把分組中包含的信 息存儲於自己的鄰居列表中；(2)當車輛自組織網絡中的任一節點接收到數據分組時，檢查分組中的目的地址域，若 目的節點是自己，直接提交給上層，路由協議運行結束；否則，檢查鄰居列表中存儲的數據 格式，判斷鄰節點中是否存在交叉口節點，若存在，執行步驟⑶；否則，轉到步驟(5)；(3)提取鄰居列表中存儲的密度信息，結合下個交叉口到目的地的距離，分別計算各相 鄰交叉口的權值，並選權值最大交叉口的標識號填入分組的動態地址域，替代原標識號；(4)比較所選交叉口的相應路段是否與當前節點所在路段的方向一致，若一致，執行步 驟(5)；否則，將分組發送給交叉口節點，該交叉口節點根據分組中的交叉口標識號發送分 組，返回步驟⑵；(5)獲取當前節點傳輸範圍內距目的地最近的節點，檢查其行駛方向是否與當前節點 一致，若一致，發送分組給此節點，返回步驟；否則，執行步驟(6)；(6)檢測該節點是否處於當前節點傳輸範圍的邊界，若是，重新選擇距目的地次近的節 點，並發送分組給此節點；否則，直接發送分組給該節點，返回步驟(2)重新開始。
2.根據權利要求1所述的車輛自組織網絡中基於預測的交叉路口處的路由方法，其中 步驟(1)所述的密度信息，是通過GyTAR協議中規定的方法獲取，其獲取步驟如下首先，將道路分成固定的小區域單元，每個單元內的車輛組成一個簇，將最靠近單元中 心的車輛作為簇頭，由簇頭節點計算本簇內的節點密度；然後，用計算所得本簇內節點密度的結果構造成單元密度分組CPD，通過在簇間傳遞並 更新CPD中的密度值獲得整條路段的節點密度。
3.根據權利要求1所述的車輛自組織網絡中基於預測的交叉路口處的路由法，其中步 驟(5)中所述的動態地址域，是指用於填寫在傳輸過程中由於傳輸路段的不斷改變而隨之 改變的變化的交叉口地址標識號。
4.根據權利要求1所述的車輛自組織網絡中基於預測的交叉路口處的路由方法，其中 步驟中所述的判斷鄰節點中是否存在交叉口節點，是通過檢測鄰居列表中是否存在包 含密度信息的條目判定，若存在，則判定鄰節點中存在交叉口節點；否則，判定不存在。
5.根據權利要求1所述的車輛自組織網絡中基於預測的交叉路口處的路由方法，其中 步驟中所述的檢測該節點是否處於當前節點傳輸範圍的邊界，是利用GPS定位技術提 供的位置信息，通過計算該節點與當前節點的距離獲得，車輛的無線傳輸範圍是250m，當該 節點與當前節點的距離大於230m時，判定所選節點處於傳輸範圍的邊界。
6.根據權利要求1所述的車輛自組織網絡中基於預測的交叉路口處的路由方法，其中 步驟(5)中所述的分別計算各相鄰交叉口的權值W(J)，計算公式如下
全文摘要
本發明公開了一種車輛自組織網絡中基於預測的交叉路口處的路由方法，主要解決現有技術中存在的當分組在道路交叉口路由時，會出現鏈路不穩定的問題。其實現方案是當分組到達交叉口前一跳節點時，該節點預測分組傳輸的下一交叉口，根據各相鄰路段的密度和下個交叉口到目的地的距離，計算各相鄰交叉口的權值，選擇權值最大的交叉口作為傳輸分組的下一臨時目的地；當分組在路段上採用貪婪轉發時，若所選節點位於傳輸範圍邊界且與發送節點行駛方向相反，則選擇距目的地次近的節點；否則，直接將分組轉發給所選節點。本發明與GPCR協議和GpsrJ+協議相比增加了分組的傳遞率，減少分組的傳輸時延，可用於車輛自組織網絡。
文檔編號H04W48/10GK102137462SQ20111009818
公開日2011年7月27日 申請日期2011年4月19日 優先權日2011年4月19日
發明者朱麗娜, 李建東, 李長樂, 林航, 蔡雪蓮, 趙春春 申請人:西安電子科技大學