高動態無線自組網路由協議設計

王文 弢，卿利

(中國西南電子技術研究所, 成都610036)

1 引 言

關于無線自組網的路由協議研究有很多,都是針對不同應用需求來設計不同的路由協議[1-3]。比如從路由發現策略出發,可分為先應式路由與反應式路由[4];從網絡邏輯視圖出發,可分為平面路由與分級路由;從是否使用GPS 系統出發,可分為地理定位輔助路由和無地理定位輔助路由[5]。

本文在充分研究現有各種路由協議的基礎上,針對高動態運動節點在進行自組織組網運行過程中,直接采用現有路由協議時將產生網絡建立時間較長、數據端到端傳輸時延無法得到可靠保障,并且由于維護動態網絡連接性造成網絡開銷較大等方面的問題[6],提出一種基于分簇的路由協議,該協議綜合借鑒了主動路由協議、被動路由協議和分級路由協議的優點,并能夠適應網絡節點高速運動、網絡拓撲結構快速變化。

2 路由協議設計

高動態無線網絡路由協議采用混合式路由協議,將主動式路由和被動式路由進行有機結合。在簇的內部,所有節點周期維護簇內的完整路由信息,保障在簇內通信的響應時間段,屬于主動式的路由維護;在簇的外部,采用了按需路由協議,即當節點有數據包發送但沒有該節點的路由時,由成員節點向簇首節點發送路由請求消息,簇首節點周期維護鄰接簇表,減少簇間通信時的響應時間;簇間網關節點實現簇間通信。

2.1 網絡運行過程

網絡運行過程中,節點根據網絡運行狀態,分為以下4 種節點類型:

(1)未明確節點:節點初始入網時,沒有明確身份的節點;

(2)成員節點:一般的網絡節點;

(3)簇首節點:通過動態選擇,簇首節點負責維護簇內路由表和鄰接簇表;

(4)簇間網關節點:通過動態選擇,選擇原則是橫跨鄰接簇數目最多,為每個鄰接簇都要動態選擇一個簇間網關節點。

運行過程中,主要處理以下7 種類型消息:

(1)Hello 消息:節點發送hello 消息,用于鄰居發現過程。Hello 消息包括本節點地址、本節點身份、本節點鄰居節點數目;

(2)本地拓撲通告消息:通過本地拓撲通告消息在簇內部交互,用于創建簇內全網路由表,包括本節點地址、鄰居數目、鄰居節點地址列表、鄰居節點身份、鄰居節點狀態等;

(3)簇拓撲通告消息:在簇首與簇首之間進行拓撲通告,包括簇首地址、中繼簇首地址、簇成員數、簇成員地址等;

(4)路由請求消息:向未知路由的目的節點通信時,如果其節點類型是簇內成員節點,則向簇首發送路由請求消息;如果節點類型是簇首節點,則向簇間網關節點發送路由請求消息;

(5)路由應答消息:用于簇首節點或者簇間網關節點對路由請求進行的應答;

(6)路由錯誤:用于向使用中斷路由的鄰居發送錯誤通告,以防后續數據包的發送失敗;

(7)應用數據:各類需要傳輸的用戶數據。

在節點入網、拓撲維護等過程中,網絡會自動根據一定原則選取簇首,其狀態轉移圖如圖1 所示。

圖1 網絡運行過程Fig.1 The process of network running

2.1.1 搜索網絡

站點完成初始加電,搜索當前網絡。如果收到網絡成員發送的消息,則網絡存在,建立簇首信息,獲取通信密鑰,完成成員入網。如果超時未收到網絡成員發送的消息,則網絡不存在,發起建立網絡,自己成為簇首,產生通信密鑰等安全參數。

2.1.2 入網運行

站點只要加入網絡,則可與網絡中成員進行通信,并維護路由和簇拓撲結構。

2.1.3 簇首維護拓撲

簇首進行以下拓撲維護處理:成員離開,即超時未收到成員消息或成員主動退網均視為離開本簇,簇首刪除成員信息;成員加入,即收到新節點消息,則增加該成員信息;競爭簇首,即有相鄰簇首存在,則根據簇首鄰居數決定是否放棄簇首身份。

2.1.4 簇成員維護拓撲

簇成員進行以下拓撲維護處理:簇首離開,若超時未收到簇首消息或簇首主動退網均視為簇首離開本簇,簇成員選擇新的簇首;取代簇首,當簇成員鄰居數大于簇首鄰居數一定門限,則自己成為簇首。

2.1.5 靜默

成員靜默定義為只能接收數據包且不能發送數據包。成員靜默狀態通知到全網,所有網絡成員保留靜默成員的路由信息,并正常轉發目的地址為靜默成員地址的數據包。成員靜默超時未收到解除靜默或繼續靜默通知,則刪除靜默成員路由信息。

2.1.6 退網

網絡管理站收到成員發送的退網消息視為成員退網。網絡管理站將成員退網消息傳輸到網絡的所有網絡成員。網絡成員收到成員退網消息,則停止轉發所有發往該成員的數據包。

2.2 簇首形成與維護

網絡運行開始后,則進行簇形成,每個簇由若干節點構成,每個簇由一個簇首節點,簇首節點與簇內所有節點都是鄰居節點。簇形成過程如圖2 所示。

圖2 簇首選擇過程Fig.2 The process of election of cluster head

簇形成是指在網絡建立時,網絡形成多個簇的網絡拓撲結構過程。主要步驟如下:

(1)節點發送hello 消息,初始狀態為未確定;

(2)根據消息觸發機制,發送hello 消息或者本地拓撲通告消息;

(3)節點接收到簇首發送的hello 消息后,將本節點狀態更改為成員,并加入簇;

(4)本節點鄰居數是最多的,則本節點為簇首節點;

(5)如果鄰居數同樣多,則節點ID 號偏小的為簇首節點;

(6)經過一段時間后,沒有接收到簇首或者其他節點的hello 消息,則將本節點身份改為簇首。

簇維護是當網絡拓撲結構發生變化時進行的簇結構維護過程,引起變化的原因包括有新節點加入簇、節點離開簇、簇首離開、成員節點取代簇首節點等情況。

2.3 全網簇拓撲

全網簇簇拓撲發現通過接收處理簇拓撲通告消息,獲取一定跳數范圍內簇首及其成員的可達信息,簇拓撲信息包含在簇拓撲表中。主要包括了對兩個表的建立與維護。

(1)鄰接簇表

簇首維護鄰接簇表,記錄鄰接簇首信息,包括簇首地址、簇間網關地址、當前節點到鄰接簇首的跳數。

(2)簇拓撲表

簇拓撲表由每個簇的簇首建立和維護,通過發送簇拓撲通告消息,互相通告每個簇的節點,簇間網關節點記錄網絡中的簇首和成員信息,包括目的簇首地址、下一跳簇首地址、當前簇首到目的簇首的簇跳數、下一跳簇間網關節點地址、簇內成員地址列表。

2.4 路由計算

通過建立并維護路由表來獲得目的節點的路由信息。路由表中主要包括以下信息:目的地址、目的簇首地址、下一跳地址、下一跳簇首地址、流水號、跳數、有效時間。

簇首節點建立和維護簇內路由表的過程類似主動式路由協議;簇間路由表的建立與維護是簇間數據傳輸時延能夠降低的關鍵,其主要過程如下:

(1)簇間網關節點接收到hello 消息后,將其納入鄰居節點表,如果該節點是成員節點,并通過簇間拓撲消息或者本地拓撲消息管理得知該成員節點對應的簇首節點,則將其與簇首對應,否則簇首為未知;如果該節點是簇首節點,并且是已知簇首節點則將其更新周期重置,如果是未知簇首則新增加簇表項;

(2)簇間網關節點接收到本地拓撲消息后,將本地簇首對應的成員地址全部更新,簇間網關節點會連接有多個簇首;

(3)簇間網關節點接收到簇拓撲消息后,將簇拓撲消息發送到簇首節點,并將本地維護的簇首和簇成員表進行更新。

3 仿真實驗及結果分析

為了在實際網絡中分析路由協議,采用OPNET進行了協議仿真,網絡節點數設置為200 個,節點移動模型設置為隨機移動,初始設置每個節點有3 ～7個鄰居節點,保持較好的網絡連通性,節點傳輸速率設置為2 Mbit/s,主要針對數據端到端傳輸時延和網絡管理開銷進行分析和評估。

應用層業務傳輸的端到端時延仿真結果如圖3所示。

圖3 端到端時延Fig.3 End-to-end delay

從圖3 可以看出,簇內端到端時延比簇間端到端時延明顯小很多,主要因為簇內路由協議采用主動式路由協議,采取周期維護簇內路由表,簇間路由表由簇間網關進行維護,端到端時延較大。

簇間端到端時延隨著網絡成員數增大變化較為明顯,主要是由于網絡成員變多以后,形成的簇較多,不同簇的節點之間跳數增加,簇間網關節點經常發生變化,造成端到端時延較大。

網絡管理開銷指網絡中路由及管理信息占總數據量的比例。仿真工作針對包括200 個節點的網絡控制開銷進行分析,通過改變簇拓撲管理消息維護周期和鄰居節點發現周期等參數,通過仿真得出各參數的最優值,實現網絡管理開銷滿足網絡設計要求。仿真結果如圖4 所示。

圖4 網絡管理開銷Fig.4 Network management overhead

從圖4 可以看出,網絡管理開銷隨著節點數的增加有增大的趨勢,由于設計較為合理,節點數為200 個時,網絡管理開銷小于4%。并且當網絡節點數為80 個左右時,網絡管理開銷最低,通過合理控制網絡節點數目以及拓撲更新率,能夠實現網絡管理開銷最小。

4 結 論

本文分析了無線自組織網絡路由協議的基本分類,著重針對高動態無線網絡中對于快速建立網絡、數據低時延傳輸等需求進行分析,并在此基礎上進行路由協議設計,提出了基于主動式和被動式相結合的路由協議算法,并針對端到端時延和網絡管理開銷這兩個主要指標進行了仿真分析。通過仿真表明,設計的路由協議在一定范圍內基本符合高動態無線自組網運行特點,其數據傳輸時延基本滿足業務需求。下一步還將優化簇間路由協議,使其受到網絡節點數的影響更小,同時還將對路由協議涉及到的其他指標進行更全面的仿真,完善路由協議設計。

[1] 史美林, 英春.自組網路由協議綜述[ J] .通信學報,2001,22(11):93-103.

SH I Mei-lin, YING Chun.Routing protocols for ad hoc networks:a survey[ J] .Journal on Communications, 2001, 22(11):93-103.(in Chinese)

[2] 王海濤.Ad hoc 網絡的體系結構及其設計[ J] .中國數據通信, 2003(8):70-76.

WANG Hai-tao.Architecture construction and design for ad hoc networks[ J] .China Data Communication, 2003(8):70-76.(in Chinese)

[3] Akkaya K, Younis M.A survey of routing protocols in wireless sensor networks[J] .Ad Hoc Networks,2005,3(3):325-349.

[4] IETF RFC 2328,OSPF Version 2[S] .

[5] Xu Kaixin, Hong Xiaoyan, Gerla M.Landmark Routing in Ad Hoc Networks with Mobile Backbones[ J] .Journal of Parallel and Distributed,2003, 63(2):110-122.

[6] Ghanadan R, Tufano P, Hsu J, et al.Flexible Access Secure Transfer(FAST)Tactical Communications Waveform for Airborne Networking[ C]//Proceedings of 2005 IEEE Military Communications Conference.Atlantic City, NJ:IEEE, 2005:1167-1173.