基于位置信息改進的AODV路由協議

王泰麟，張法全，葉金才，王國富

(桂林電子科技大學 信息與通信學院，廣西 桂林　541004)

?

基于位置信息改進的AODV路由協議

王泰麟，張法全，葉金才，王國富

(桂林電子科技大學 信息與通信學院，廣西 桂林541004)

為減少AODV路由協議的路由開銷，設計了一種基于位置信息改進的AODV路由協議——Im-AODV。改進的AODV路由協議通過在RREQ消息中添加節點位置信息來限制RREQ消息的洪泛區域，減少控制報文的轉發。位置信息則通過RREQ消息和RREP消息在網絡中擴散，并未增加額外的控制報文。通過NS2對改進的AODV路由協議進行仿真，仿真結果表明，改進的AODV路由協議減少了歸一化路由開銷，提高了分組投遞率。

路由開銷；AODV；位置信息；Im-AODV；NS2

無線自組織網絡(mobile Ad Hoc network，簡稱MANET)是一種多跳、無中心、自組織無線網絡，整個網絡無需固定基礎設施，網絡中各個節點均可移動，并且能夠與其他節點保持聯系[1-2]。網絡中各節點地位平等，拓撲可變，節點的移動、加入和退出并不影響整個網絡的正常工作。當節點需要與其通信覆蓋范圍之外的節點進行通信時，將由中間節點進行多跳轉發，各節點兼任路由器的角色。由于無線自組織網絡的以上特點，MANET已經得到廣泛應用。但由于無線網絡的帶寬資源、節點能源的限制，使得路由協議在設計時，除了滿足應用需求外，還應減少路由協議對網絡帶寬資源的占用和能源的消耗，提高協議的效率和網絡的吞吐率。

根據應用場景不同，人們提出了很多無線路由協議。根據觸發原理的不同，這些路由協議可分為3類：1)表驅動路由協議；2)按需驅動路由協議；3)混合式路由協議[3]。表驅動路由協議又稱先驗式路由協議，網絡中每個節點都保存一張包含到達其他節點的路由表，通過周期性廣播更新路由信息，但其無法適用于網絡拓撲變化較快的場景，且其周期性廣播帶來的帶寬資源占用往往是不可接受的。按需路由協議也稱后驗式路由協議，其主要特點是：當源節點需要時才進行路由查找，從而減小了路由開銷，保證路由信息的時效性，但傳送數據的時延相對較大。混合式路由協議是在表驅動路由協議和按需驅動路由協議都不能滿足應用需求時，研究人員結合兩類路由的優點和不同特點提出的路由協議。

AODV路由協議(Ad Hoc on-demand distance vector routing protocol)是MANET的一種經典按需路由協議，具有算法簡單、擴展性好的特點[4]。其工作流程為：當源節點需要與目標節點進行通信而路由表中無相應表項時，源節點發送路由請求RREQ消息，當RREQ消息逐跳廣播至目標節點或有目標節點路由表項的節點，則沿最先到達的路徑反向應答路由回復RREP消息至源節點，從而獲取達到目標節點的路由。此外，AODV路由協議采用HELLO消息及RERR消息維護鏈路[5-6]。AODV路由協議采用簡單洪泛機制[7]，雖然提高了路由的發現機率，但由此引起的路由請求廣播的無效轉發，往往帶來帶寬資源的大量消耗，造成信道擁塞，從而降低整個網絡的工作效率。

針對AODV路由協議的路由發現過程中簡單洪泛帶來的問題，提出一種基于位置信息改進的AODV路由協議(Im-AODV)，限制RREQ消息的廣播范圍，從而減少洪泛帶來的網絡開銷。

1　基于位置信息改進的AODV路由協議

為限制RREQ消息的廣播范圍，在AODV路由協議的基礎上，增加了一個稱為節點信息表的數據結構，用于存儲網絡中節點的位置信息。每個節點信息表的內容包括：節點IP地址、節點序列號、節點坐標有效標識、節點坐標。

為了將節點的坐標信息擴散到整個網絡，改進的AODV路由協議采用將節點的坐標信息附加到AODV路由協議的RREQ消息和RREP消息中的方式。改進的RREQ消息結構如表1所示，相對標準AODV路由協議的RREQ消息，在原保留區內增加了1位目標節點坐標標識位S，在RREQ消息后部增加了目標節點坐標和源節點坐標2個字段。改進的RREP消息結構如表2所示，在原保留字段內增加了1位回復節點坐標標識位S，并在RREP消息后部增加了目標節點坐標、回復節點IP地址、回復節點序列號和回復節點坐標4個字段。

表1　改進的RREQ消息結構

表2　改進的RREP消息結構

若源節點需要到達目標節點的路由，則向目標節點發起路由發現。源節點根據表1所示消息結構，生成一個RREQ消息，并對此RREQ消息進行廣播。中間節點接收到RREQ消息后，提取源節點和目標節點的坐標信息，更新本地的節點信息表，然后判斷本節點是否在允許洪泛區域內。若在區域內，則根據AODV路由協議的規定對RREQ消息進行響應或繼續轉發；若不在區域內，則在更新本地的節點信息表后，直接丟棄RREQ消息。

2　Im-AODV的實現

當源節點需要一條到目標節點的路由，而路由表中無路由時，源節點即發起路由發現。改進的AODV路由產生的RREQ消息，需要在標準AODV路由協議的RREQ消息中附加如下信息：1)若目標節點坐標對于源節點是已知的，則置目標節點坐標標識位S為1，否則置0；2)目標節點坐標(若未知，則置該字段為0)；3)源節點坐標。

源節點在生成RREQ消息后進行洪泛廣播，等待接收RREP消息。改進的AODV路由協議的不同之處在于中間節點收到RREQ消息后，首先根據RREQ消息中源節點和目標節點的坐標，更新本地的節點信息表中相應內容，然后根據標準AODV查看本節點是否有到目標節點的有效路由，從而決定是否產生RREP消息。若不產生RREP消息，則根據源節點和目標節點坐標信息判斷本節點是否在允許洪泛區域。若在，則繼續轉發該RREQ消息；若不在，則丟棄。

中間節點判斷本節點是否在允許洪泛區域內的方法為：

允許洪泛區域如圖1所示，由源節點坐標S(Xs,Ys)和目標節點坐標D(Xd,Yd)構成的矩形即為允許洪泛區域，中間節點N(Xn,Yn)根據RREQ消息的源節點和目標節點的坐標判斷其是否在允許洪泛區域內，即是否滿足：

(1)

(2)

因為節點N(Xn,Yn)滿足式(1)、(2)，所以判斷其在允許洪泛區域內；而節點I(Xi,Yi)不能同時滿足式(1)、(2)，則判定其不在允許洪泛區域。

為了進一步優化路由發現的成功率，將目標節點坐標擴展為一個半徑為R的圓形區域，優化后的允許洪泛區域如圖2所示。R的設定可根據網絡節點的密度調整，若節點分布較為密集，可設定一個較小的R，若節點分布較為稀疏，則設定一個較大的R。

圖1　允許洪泛區域Fig.1　Allowed flooding zone

圖2　優化后的允許洪泛區域Fig.2　Optimization of allowed flooding zone

以圖2為例，允許洪泛區域調整為X∈(Xs,Xd+R)，Y∈(Ys,Yd+R)的區域。

當RREQ消息成功轉發至目標節點或具有到達目標節點路由的節點時，則產生RREP消息，這與標準AODV路由協議是一致的。為了滿足網絡拓撲變化的需要，改進的AODV路由協議對RREP消息進行了修改，根據產生RREP消息節點的不同，RREP消息的內容也稍有區別。若產生RREP消息的是目標節點，則將回復節點標識位置1，并將目標節點IP地址和坐標寫到回復節點IP地址和坐標字段；若產生RREP消息的是具有到達目標節點路由的中間節點，則將回復節點標識位置0，將目標節點IP地址、坐標和回復節點IP地址、坐標分別寫入相應字段。

收到RREP消息的節點，判斷回復節點標識位。若為1，則更新本地的節點信息表中目標節點的相應信息；若為0，則更新本地節點信息表中產生RREP消息的節點相應信息和目標節點的相應信息。

3　仿真測試與結果分析

3.1仿真測試

利用NS2(network simulator version 2)仿真平臺對AODV路由協議和改進后的AODV路由協議(Im-AODV)進行仿真[8]。根據改進方法，對AODV路由協議進行修改。改進AODV所需的位置信息可用NS2提供的getLoc( )函數獲取的坐標，替代實際應用中GPS獲取的位置信息。分別利用AODV和改進的AODV在不同場景下進行3種性能測試：

1)路由發現時間。源節點發起路由發現進程到成功建立到達目標節點的路由所耗費的時間。

2)歸一化路由開銷。在整個網絡運行期間，路由控制報文數量和實際完成的數據報文數量的比值，這個比值可以較好地反映網絡的擁塞情況。

3)分組投遞率。目標節點接收的數據分組和源節點發送的數據分組的比值，主要反映網絡的可靠性。

路由發現時間測試方法：30個節點分布在250 m×300 m區域，節點間距50 m，節點有效通信距離55 m，MAC層協議為802.11，分別用不同節點以固定碼率(CBR)向目標節點發送數據分組，每秒4個分組，每個分組512 Byte，傳輸層協議采用UDP。在此場景下進行仿真，分別利用gawk對2種協議的多次仿真記錄文件trace進行分析統計。

歸一化路由開銷和數據分組投遞率測試方法：將20、40、60、80、100個節點分布在150 m×200 m、350 m×400 m、550 m×600 m、750 m×800 m、950 m×1000 m的區域，節點以不超過10 m/s的速度在區域內移動，停留80 s，以固定碼率(CBR)向目標節點發送數據分組，每秒4個分組，每個分組512 Byte，傳輸層協議為UDP。在對應場景下進行仿真，對2種協議的多次仿真記錄文件trace進行分析統計。

3.2結果分析

根據對仿真記錄文件的統計分析，得到圖3所示的2種路由發現時間。從圖3可看出，2種協議的路由發現時間基本一致，且隨著源節點到目標節點的跳數增加，2種協議路由發現時間也相應遞增。

歸一化路由開銷仿真測試結果如圖4所示。從圖4可看出，2種協議的歸一化路由開銷都隨網絡中節點數的增加而增加，但改進的AODV路由協議的路由開銷比標準AODV路由協議要小，且隨著節點數的增加，優勢更加明顯。這是因為改進的AODV路由協議對允許洪泛的區域進行了限制，只允許洪泛區域內的節點轉發RREQ，從而減少了控制報文的開銷。

圖3　AODV和Im-AODV的路由發現時間Fig.3　Roue discovery time of AODV and Im-AODV

圖4　AODV和Im-AODV歸一化路由開銷Fig.4　Normalized routing overhead of AODV and Im-AODV

分組投遞率仿真測試結果如圖5所示。從圖5可看出，隨著節點數的增加，路由跳數也隨之增加，2種協議的數據分組投遞率隨之降低，且改進的AODV協議的分組投遞率高于標準AODV協議。這是因為隨著鏈路的增長，鏈路的不穩定性增加，從而投遞率下降；同時，隨著控制報文的增加，數據報文與控制報文競爭有限的無線資源，也會導致分組傳送失敗增加；而由于減少了控制報文的數量，使得改進的AODV路由協議的分組投遞率略高于標準AODV路由協議的分組投遞率。

圖5　AODV和Im-AODV分組投遞率Fig.5　Packets delivery ratio of AODV and Im-AODV

4　結束語

仿真測試結果表明，基于位置信息改進的AODV路由協議大大減小了協議的路由開銷，并提高了數據分組投遞率。由于并未改變RREP消息的產生機制，在路由發現時間等性能方面相對于標準AODV路由協議并沒有變化。此外，基于位置信息改進的AODV路由協議只針對節點布置在一個平面或可近似為平面的無線自組織網絡，將平面的允許洪泛區域向立體空間拓展，即可使改進的AODV路由協議適用于節點立體分布的無線自組織網絡。

[1]張希婕.Ad Hoc網絡混合路由協議的研究[D].北京：北京郵電大學，2014:1-2.

[2]徐年，沙宏武.Ad Hoc技術在地震監測系統中的應用[J].電腦學習，2010(1):5-6.

[3]彭永祥.無線Adhoc網絡路由技術若干關鍵問題研究[D].成都：電子科技大學，2013:15-20.

[4]雷建棟.地理位置信息輔助的AODV路由協議[J].火力與指揮控制，2013(增刊1):59-62.

[5]謝世歡.Linux 系統上AODV路由協議的實現[D].成都：電子科技大學，2004：17-21.

[6]盧山，宋志群，周凌宇，等.無線自組織網絡按需路由協議研究[J].無線電工程，2015,45(11):5-8.

[7]何綿祿，褚偉，劉輝舟.AODV路由協議的研究和改進[J].計算機工程，2015,41(1):110-114.

[8]謝佳，徐山峰.AODV、AOMDV和AODV-UU路由協議性能仿真與分析[J].中國電子科學研究學院學報，2011,6(6):592-596.

編輯：翁史振

An improved AODV routing protocol based on position information

WANG Tailin, ZHANG Faquan, YE Jincai, WANG Guofu

(School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China)

The flooding request method of AODV routing protocol makes RREQ message forwarding across Ad Hoc network, which increases the routing overhead of protocol. To reduce the routing overhead of AODV routing protocol, an improved AODV routing protocol based on position information is proposed and called Im-AODV. In RREQ message of Im-AODV, the position information is added to limit the flooding zone of RREQ, which can reduce the forwarding of control packets. The position information diffuses in the network through RREQ and RREP, which does not add additional control packets. The improved AODV routing protocol is simulated by NS2, the simulation results show that the normalized routing overhead of the improved AODV routing protocol is effectively reduced, and the packets delivery ratio is improved.

routing overhead; AODV; position information; Im-AODV; NS2

2016-02-24

國家自然科學基金(61362020)；廣西自然科學基金(2013GXNSFAA019327，2013GXNSFFA019004)

張法全(1969-)，男，河南林州人，研究員，博士，研究方向為信號與信息處理。E-mail:zhangfq@guet.edu.cn

TN92

A

1673-808X(2016)04-0270-05

引文格式：王泰麟，張法全，葉金才，等.基于位置信息改進的AODV路由協議[J].桂林電子科技大學學報，2016,36(4):270-274.