高動態(tài)無線自組網(wǎng)路由協(xié)議設(shè)計

王文 弢，卿利

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

1 引 言

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

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

2 路由協(xié)議設(shè)計

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

2.1 網(wǎng)絡運行過程

網(wǎng)絡運行過程中,節(jié)點根據(jù)網(wǎng)絡運行狀態(tài),分為以下4 種節(jié)點類型:

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

(2)成員節(jié)點:一般的網(wǎng)絡節(jié)點;

(3)簇首節(jié)點:通過動態(tài)選擇,簇首節(jié)點負責維護簇內(nèi)路由表和鄰接簇表;

(4)簇間網(wǎng)關(guān)節(jié)點:通過動態(tài)選擇,選擇原則是橫跨鄰接簇數(shù)目最多,為每個鄰接簇都要動態(tài)選擇一個簇間網(wǎng)關(guān)節(jié)點。

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

(1)Hello 消息:節(jié)點發(fā)送hello 消息,用于鄰居發(fā)現(xiàn)過程。Hello 消息包括本節(jié)點地址、本節(jié)點身份、本節(jié)點鄰居節(jié)點數(shù)目;

(2)本地拓撲通告消息:通過本地拓撲通告消息在簇內(nèi)部交互,用于創(chuàng)建簇內(nèi)全網(wǎng)路由表,包括本節(jié)點地址、鄰居數(shù)目、鄰居節(jié)點地址列表、鄰居節(jié)點身份、鄰居節(jié)點狀態(tài)等;

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

(4)路由請求消息:向未知路由的目的節(jié)點通信時,如果其節(jié)點類型是簇內(nèi)成員節(jié)點,則向簇首發(fā)送路由請求消息;如果節(jié)點類型是簇首節(jié)點,則向簇間網(wǎng)關(guān)節(jié)點發(fā)送路由請求消息;

(5)路由應答消息:用于簇首節(jié)點或者簇間網(wǎng)關(guān)節(jié)點對路由請求進行的應答;

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

(7)應用數(shù)據(jù):各類需要傳輸?shù)挠脩魯?shù)據(jù)。

在節(jié)點入網(wǎng)、拓撲維護等過程中,網(wǎng)絡會自動根據(jù)一定原則選取簇首,其狀態(tài)轉(zhuǎn)移圖如圖1 所示。

圖1 網(wǎng)絡運行過程Fig.1 The process of network running

2.1.1 搜索網(wǎng)絡

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

2.1.2 入網(wǎng)運行

站點只要加入網(wǎng)絡,則可與網(wǎng)絡中成員進行通信,并維護路由和簇拓撲結(jié)構(gòu)。

2.1.3 簇首維護拓撲

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

2.1.4 簇成員維護拓撲

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

2.1.5 靜默

成員靜默定義為只能接收數(shù)據(jù)包且不能發(fā)送數(shù)據(jù)包。成員靜默狀態(tài)通知到全網(wǎng),所有網(wǎng)絡成員保留靜默成員的路由信息,并正常轉(zhuǎn)發(fā)目的地址為靜默成員地址的數(shù)據(jù)包。成員靜默超時未收到解除靜默或繼續(xù)靜默通知,則刪除靜默成員路由信息。

2.1.6 退網(wǎng)

網(wǎng)絡管理站收到成員發(fā)送的退網(wǎng)消息視為成員退網(wǎng)。網(wǎng)絡管理站將成員退網(wǎng)消息傳輸?shù)骄W(wǎng)絡的所有網(wǎng)絡成員。網(wǎng)絡成員收到成員退網(wǎng)消息,則停止轉(zhuǎn)發(fā)所有發(fā)往該成員的數(shù)據(jù)包。

2.2 簇首形成與維護

網(wǎng)絡運行開始后,則進行簇形成,每個簇由若干節(jié)點構(gòu)成,每個簇由一個簇首節(jié)點,簇首節(jié)點與簇內(nèi)所有節(jié)點都是鄰居節(jié)點。簇形成過程如圖2 所示。

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

簇形成是指在網(wǎng)絡建立時,網(wǎng)絡形成多個簇的網(wǎng)絡拓撲結(jié)構(gòu)過程。主要步驟如下:

(1)節(jié)點發(fā)送hello 消息,初始狀態(tài)為未確定;

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

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

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

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

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

簇維護是當網(wǎng)絡拓撲結(jié)構(gòu)發(fā)生變化時進行的簇結(jié)構(gòu)維護過程,引起變化的原因包括有新節(jié)點加入簇、節(jié)點離開簇、簇首離開、成員節(jié)點取代簇首節(jié)點等情況。

2.3 全網(wǎng)簇拓撲

全網(wǎng)簇簇拓撲發(fā)現(xiàn)通過接收處理簇拓撲通告消息,獲取一定跳數(shù)范圍內(nèi)簇首及其成員的可達信息,簇拓撲信息包含在簇拓撲表中。主要包括了對兩個表的建立與維護。

(1)鄰接簇表

簇首維護鄰接簇表,記錄鄰接簇首信息,包括簇首地址、簇間網(wǎng)關(guān)地址、當前節(jié)點到鄰接簇首的跳數(shù)。

(2)簇拓撲表

簇拓撲表由每個簇的簇首建立和維護,通過發(fā)送簇拓撲通告消息,互相通告每個簇的節(jié)點,簇間網(wǎng)關(guān)節(jié)點記錄網(wǎng)絡中的簇首和成員信息,包括目的簇首地址、下一跳簇首地址、當前簇首到目的簇首的簇跳數(shù)、下一跳簇間網(wǎng)關(guān)節(jié)點地址、簇內(nèi)成員地址列表。

2.4 路由計算

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

簇首節(jié)點建立和維護簇內(nèi)路由表的過程類似主動式路由協(xié)議;簇間路由表的建立與維護是簇間數(shù)據(jù)傳輸時延能夠降低的關(guān)鍵,其主要過程如下:

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

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

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

3 仿真實驗及結(jié)果分析

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

應用層業(yè)務傳輸?shù)亩说蕉藭r延仿真結(jié)果如圖3所示。

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

從圖3 可以看出,簇內(nèi)端到端時延比簇間端到端時延明顯小很多,主要因為簇內(nèi)路由協(xié)議采用主動式路由協(xié)議,采取周期維護簇內(nèi)路由表,簇間路由表由簇間網(wǎng)關(guān)進行維護,端到端時延較大。

簇間端到端時延隨著網(wǎng)絡成員數(shù)增大變化較為明顯,主要是由于網(wǎng)絡成員變多以后,形成的簇較多,不同簇的節(jié)點之間跳數(shù)增加,簇間網(wǎng)關(guān)節(jié)點經(jīng)常發(fā)生變化,造成端到端時延較大。

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

圖4 網(wǎng)絡管理開銷Fig.4 Network management overhead

從圖4 可以看出,網(wǎng)絡管理開銷隨著節(jié)點數(shù)的增加有增大的趨勢,由于設(shè)計較為合理,節(jié)點數(shù)為200 個時,網(wǎng)絡管理開銷小于4%。并且當網(wǎng)絡節(jié)點數(shù)為80 個左右時,網(wǎng)絡管理開銷最低,通過合理控制網(wǎng)絡節(jié)點數(shù)目以及拓撲更新率,能夠?qū)崿F(xiàn)網(wǎng)絡管理開銷最小。

4 結(jié) 論

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

[1] 史美林, 英春.自組網(wǎng)路由協(xié)議綜述[ 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 網(wǎng)絡的體系結(jié)構(gòu)及其設(shè)計[ J] .中國數(shù)據(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.