[發明專利]一種無線移動網絡路由選擇的優化方法

有效

• 申請號: 201310128022.1
• 申請日: 2013-04-12
• 公開（公告）號: CN103200642A
• 公開（公告）日: 2013-07-10
• 發明（設計）人: 廖丹;楊曉玲;孫化松;陸川;許都;虞紅芳
• 申請（專利權）人: 電子科技大學
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W80/04
• 代理公司: 電子科技大學專利中心 51203
• 代理人: 周劉英

技術領域

本發明涉及無線移動網絡，尤其涉及高動態的無線移動網絡中，路由選擇的優化方法。

背景技術

隨著無線移動網絡的發展，各種無線移動網絡在人們生活中被廣泛應用，如車載自組織網絡，車載自組織網絡作為一種高動態的無線移動網絡，具備以下幾個方面的顯著特點：

（1）節點密度分布不均勻，不同位置區域，不同時段內，節點的密度分布不同，例如在城市繁華區、上下班高峰期節點密度很大，而在高速公路、郊區等區域節點密度很小；

（2）網絡拓撲變化頻繁，各節點的位置變化速率取決于其所處區域的節點密度，如節點高速移動，位置變化很快；

（3）各節點能實時獲取其所在位置信息，如通過節點（如車輛）上所配備的GPS設備；

（4）由于通信障礙物（如高樓建筑等）的存在，會導致節點雖然在彼此間的通信范圍內，但是不能通信的情況；

針對上述特點的高動態無線移動網絡，一般很難建立比較穩定的端到端的通信，所以如何能夠快速而準確的進行路由選擇成為該類無線網絡（如車載自組織網絡）的一個至關重要的任務，它直接決定了從源節點到目的節點的路由跳數、數據投遞率、時延等重要性能指標。當前，針對高動態的無線移動網絡的路由協議主要有基于拓撲的路由協議和基于地理位置的路由協議。

在基于拓撲的路由協議中，當兩個節點的距離小于無線信號通信范圍時，互為鄰居節點，所有的路由學習完全依靠鄰居節點之間交換路由項，節點通過鏈路狀態協議向鄰居節點通告鏈路狀態。基于拓撲的路由方法主要分成兩大類：主動路由和被動路由。主動路由基本思想是主動地定期進行路由表的廣播和更新，在主動路由中，可以實時更新路由表，信息轉發時延小，投遞成功率高，但是頻繁更新路由表會占用大量網絡資源，利用率低，特別在節點密度很大時很容易造成網絡擁塞。被動路由是只有源節點在有通信需求時才創建路由，通信結束后不維護路由，直到收到下一次需求，被動路由模式下總的路由開銷較小，但是實時性不好而導致時延較大，成功率低的缺點。

在基于拓撲的路由協議中，需要知道全網的鏈路信息，目前MOPR（MOvement?Prediction?based?Routing，運動預測算法）算法是使用較多的一種，它通過節點的位置、速度和方向等信息來改善路由算法。該算法通過節點現在的位置來預測節點未來可能出現的位置，從而估計一條鏈路的生存時間。源點可以根據生存時間估計報文的傳輸時間從而選出一條最穩定的鏈路。

由此可見，基于拓撲的路由協議存在以下兩個不容克服的缺陷：

（1）雖然處理過程快速收斂，找出的路徑也是源點到目的點的比較短的路徑，但是在應用于高動態的無線移動網絡時，由于其網絡拓撲變化非常頻繁，特別是節點密度不是很大的情況下，節點移動速度很快，往往在報文還沒有從源點轉發到目的點時，鏈路節點已經移動，鏈路頻繁斷裂，在轉發報文時找不到節點，造成丟包；

（2）在網絡拓撲結構較大或者節點密度很大時，想要實時知道整個網絡的拓撲是不現實的，也將造成相當大的網絡負載，導致網絡擁塞嚴重影響網絡性能。

在基于地理位置的路由協議中，只需要知道本節點、鄰居節點和目的節點的位置信息就可以進行路由轉發，大大降低了路由開銷。基于地理位置的路由投遞策略思想幾乎都遵循貪婪算法，即每一次總是選擇距離目的點更近的鄰居節點，因為基于位置的路由只知道本地的位置信息，并不知道全網的位置信息，所以很容易陷入局部最優，即在發送節點的通信范圍內的所有節點中，發送節點距離目的節點最近，而陷入死循環中，一般來說基于位置的路由都有針對于局部最優的修復策略。

目前使用比較廣泛的就是GPSR（Greedy?Perimeter?Stateless?Routing，貪婪周邊無狀態路由）算法，GPSR算法的核心思想是貪婪路由和修復策略。所謂的貪婪路由就是永遠朝著離目的節點更近的下一個節點投遞報文，如圖1所示，D為目的節點，當節點S有報文要向節點D發送時，節點S會在自己的所有鄰居節點中選擇一個距離節點D最近的節點作為下一跳節點，此時是節點B；修正策略，就是指當節點要向目的節點發送數據時，節點在其鄰居節點中找不到比本節點距離目的節點更近的節點時，則采用修復策略——右手定則，如圖2所示，當節點F從鄰居節點E收到一個報文時，根據右手定則把報文轉發給節點F的第一個逆時針反向上的鄰居節點H。