基于嵌入式Linux的AODV路由協議設計與實現*

周錦陽 宋 廣

（92785部隊 葫蘆島 125200）

1 引言

隨著信息技術的不斷發展，人們對移動通信的需求越來越強。傳統移動通信網絡一般基于預設基礎設施，對于某些特殊場合，預設基礎設施不可能存在。比如，戰場上部隊快速展開和推進、地震或水災后的營救、野外科學考察等［1]。這就需要一種能夠快速部署、無需基礎設施、組網便捷的移動通信網絡，即移動自組織網絡。

移動自組織網絡作為一種無中心、分布式和自組織的無線移動通信網絡，源自美國夏威夷大學于1968年構建的無線自組織網絡—ALOHA系統［2]，其應用領域包括傳感器網絡［3]、災后緊急救援［4]、車輛通信和無線局域網等［5～6]。移動自組織網絡的一種重要研究領域就是路由技術，為了適應不同應用場合，研究人員設計了許多路由協議［7]。其中AODV路由協議是IETF推薦的無線自組織路由協議之一，它簡單實用且性能優越［8]。

本文依托嵌入式平臺，提出了一種基于Linux系統的AODV路由協議實現方法，并將AODV路由協議應用于移動自組織網絡視頻通信中。通過路由協議測試，驗證了所設計AODV路由協議通信的穩定性和及時性，為進一步探索和研究相關內容提供有益參考，具有重要的工程應用價值。

2 AODV路由協議

AODV路由協議作為按需路由協議［9]，該協議依據通信需求按需啟動路由發現過程，其節點路由表和網絡拓撲結構按需建立，所以節點路由表內容可能僅為整個網絡拓撲結構的一部分。相對于先應式路由協議，按需路由協議具有路由開銷小、節省網絡帶寬資源等優點，缺點為傳播時延較大［10]。

AODV路由協議可分為路由建立和路由維護兩個過程［11]。當源節點需要與目的節點通信，但路由表無到目的節點路由時，源節點啟動路由建立過程。路由建立過程采用洪范方式，向全網廣播路由請求分組。當發現通信鏈路中斷時，節點啟動路由維護過程。

3 AODV路由協議設計

本文設計的AODV路由協議包括四種控制報文：路由請求（RREQ）報文、路由應答（RREP）報文、HELLO報文和路由出錯（RERR）報文。RREQ報文和RREP報文用于自組織網絡的路由建立，HELLO報文和RRER報文用于自組織網絡的路由維護。

3.1 控制報文設計

1）RREQ報文

RREQ報文格式如圖1所示，包括Type字段、跳數、目的節點IP地址、源節點IP地址、源節點序列號及保留字段，總共16個字節。

圖1 RREQ報文格式

2）RREP報文

RREP報文報文格式如圖2所示，包括Type字段、跳數、目的節點IP地址、源節點IP地址、目的節點序列號及保留字段，總共16個字節。

3）HELLO報文

HELLO報文格式如圖3所示，包括Type字段和保留字段，總共4個字節。

4）RERR報文

RERR報文格式如圖4所示，包括Type字段、失效IP個數及失效IP地址。

圖2 RREP報文格式

圖3 HELLO報文格式

圖4 RERR報文格式

3.2 報文處理策略設計

3.2.1 RREQ報文處理策略

RREQ報文用于建立從目的節點到源節點的反向路由，其處理策略包括報文發送策略和報文接收處理策略。

圖5 RREQ報文發送策略

1）RREQ報文發送策略

當源節點需與目的節點進行通信，但其路由表中沒有到達目的節點的路由時，源節點會啟動RREQ報文的發送策略。RREQ報文發送策略如圖5所示。如果在規定時間內收到目的節點回復的RREP報文，則建立從目的節點到源節點的反向路由。

2）RREQ報文接收處理策略

當節點收到RREQ報文時，啟動RREQ報文接收處理策略，建立到源節點的反向路由。RREQ報文接收處理策略如圖6所示。節點收到RREQ報文，則添加或更新到源節點的反向路由。如果本節點是RREQ報文的目的節點，則本節點向RREQ報文源節點單播回復RREP報文；如果本節點不是RREQ報文的目的節點，則廣播轉發該RREQ報文。

圖6 RREQ報文接收處理策略

3.2.2 RREP報文處理策略

RREP報文用于建立從源節點到目的節點的正向路由。當目的節點收到有效RREQ報文時，則沿著新建立的反向路由單播回復RREP報文。收到RREP報文的節點，啟動RREP報文處理策略，建立到目的節點的正向路由。RREP報文處理策略如圖7所示。節點收到RREP報文時，添加或更新到目的節點的正向路由，如果本節點不是RREP報文的目的節點，則單播轉發RREP報文。

3.2.3 HELLO報文處理策略

HELLO報文用于向鄰居節點通報自身節點的存在，每一個收到HELLO報文的鄰居節點，如果存在到此節點的路由，都會更新此路由條目的本地時間。如果路由條目的本地時間長期不更新，路由表就認為此路由條目為失效路由條目。當節點路由表中有需要維護的路由條目時，節點周期性廣播HELLO報文，收到HELLO報文的鄰居節點啟動HELLO報文處理策略，進行路由維護。HELLO報文處理策略如圖8所示。

圖7 RREP報文處理策略

圖8 HELLO報文處理流程

3.2.4 RERR報文處理策略

RERR報文用于向網絡通報已失效的路由條目，每一個收到RERR報文的下一跳節點，都會檢查本地路由表是否存在相關失效路由條目，如存在失效路由條目，則轉發此RERR報文。當節點本地路由表發現超時路由條目（即認為失效）時，節點會廣播發送RERR報文。接收到RERR報文的節點啟動RERR報文處理策略，進行路由維護。RERR報文處理策略如圖9所示。

4 AODV路由協議實現

AODV路由協議的實現基于嵌入式Linux操作系統，利用Linux內核netfilter框架的包過濾功能，在PRE_ROUTING及LOCAL_OUT兩個HOOK點設置鉤子函數，對流出（發送數據）和流入（接收數據）節點的數據包進行抓包，針對數據包的不同類型，加載不同報文處理策略，實現AODV路由協議的路由建立、路由維護和數據傳輸功能。

圖9 RERR報文處理流程

4.1 netfilter框架

netfilter框架是Rusty Russell提出的新一代Linux防火墻，該框架基于Linux內核2.4版本，可實現數據包的過濾及處理、地址偽裝和網絡地址轉換等功能［12]。為實現對流經TCP/IP協議棧的數據包進行檢測和控制處理，在數據包流經協議棧的線路上，netfilter框架定義了五個鉤子點（即HOOK點），如圖10所示。在此五個HOOK點上，netfilter框架分別定義了五個鉤子函數，用戶可設置封裝好的鉤子函數實現數據包的抓取和處理。

圖10 netfilter框架的HOOK點（IPv4）

針對流出平臺的發送數據，在LOCAL_OUT鉤子點設置鉤子函數，進行發送數據的抓包和處理；針對流入平臺的接收數據，在PRE_ROUTING鉤子點設置鉤子函數，進行接收數據的抓包和處理。

4.2 發送數據處理

發送數據作為平臺自身產生的數據包，其處理流程如圖11所示。依據平臺節點是否存在目的路由，決定是否生成RREQ報文，并啟用RREQ發送策略。

圖11 發送數據處理流程

4.3 接收數據處理

接收數據作為外部節點流入平臺節點的數據，其處理流程如圖12所示。本文設計數據包類型包括數據報文和控制報文兩種，其中控制報文包括RREQ報文、RREP報文、HELLO報文和RERR報文四種。依據數據包的不同類型，調用不同報文處理策略，從而實現AODV路由協議的路由建立、路由維護和數據傳輸功能。

5 AODV路由協議測試

5.1 靜態測試

在靜態多跳實驗場景下，針對網絡時延和丟包率兩方面進行性能測試，驗證AODV路由協議通信穩定性。靜態測試如圖13所示，平臺S、M1和D均靜止。通過平臺S發送到平臺D的ping擴展指令，記錄網絡時延和丟包率。

經測試及結果統計，靜態測試時延如圖14所示，靜態測試丟包率如圖15所示。依據統計結果可知，對于2跳S-M1-D鏈路，當發送1KB大小的數據包時，鏈路平均時延穩定在61ms左右，上下波動不超過3ms。隨著測試時間的增加，丟包率從1.6%逐步趨近于0。由此可見，針對節點靜止的多跳自組織網絡，鏈路時延穩定性良好，數據包丟失僅出現在路由建立的初始階段，隨著測試時間的增長，丟包率趨近于0，鏈路通信狀態良好。

圖12 接收數據處理流程

圖13 AODV路由協議靜態測試圖

圖14 靜態測試時延

圖15 靜態測試丟包率

5.2 動態測試

在動態多跳路由切換實驗場景下，針對網絡時延、丟包率和路由切換時間進行性能測試，驗證AODV路由協議通信穩定性和及時性。動態測試如圖16所示，平臺S、M1和M2均靜止，平臺D勻速往返運動。通過源節點S發送到目的節點D的ping擴展指令，記錄網絡時延、丟包率和路由切換時間。

圖16 AODV路由協議態測試圖

圖17 路由切換時延

經測試及結果統計，路由切換時延如圖17所示，路由切換丟包率如圖18所示。依據統計結果可知，對于多節點路由切換鏈路，當發送1KB大小的數據包時，鏈路平均時延在61.5ms左右，上下波動不超過2ms；丟包率穩定在4.7%左右，最大不超過5%。由此可見，針對多節點自組織網絡的路由切換，鏈路時延穩定性良好，數據丟包率較小。

圖18 路由切換丟包率

路由切換時間統計結果如圖19所示，其中“S-D→S-M1-D”表示路由切換由鏈路S-D切換到鏈路S-M1-D，其它路由切換采用相同的表示方式。依據統計結果可知，路由切換平均時長約2.9s，最大不超過3.1s。由此可見，針對多節點自組織網絡的路由切換，路由切換及時，上下波動較小，鏈路通信狀態良好。

圖19 路由切換時間統計結果

綜上所述，分析可知：鏈路平均時延與所經跳數相關，跳數越多，時延越大；丟包率與路由切換頻率相關，路由切換越頻繁，丟包率越大；路由切換時間與自組織路由協議路由維護周期相關，維護周期越短，越容易發現失效路由，從而越早重新建立路由，縮短路由切換時間，但路由節點維護成本相應增大。

6 結語

本文基于嵌入式Linux操作系統，利用Linux內核netfilter框架，通過對路由協議報文處理策略的加載，實現了AODV路由協議的自組織路由和數據傳輸功能。測試結果表明，所設計的AODV路由協議具有良好的通信的穩定性和及時性。隨著嵌入式技術的發展和移動自組織網絡的應用，未來還需要對自組織路由協議和工程應用進一步研究，使之更廣泛應用于車聯網、物聯網及無線傳感器網絡等方向。