王文 弢，卿利

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

1 引 言

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

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

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

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

2.1 網(wǎng)絡(luò)運(yùn)行過程

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

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

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

(3)簇首節(jié)點(diǎn):通過動(dòng)態(tài)選擇,簇首節(jié)點(diǎn)負(fù)責(zé)維護(hù)簇內(nèi)路由表和鄰接簇表;

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

運(yùn)行過程中,主要處理以下7 種類型消息:

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

(2)本地拓?fù)渫ǜ嫦?通過本地拓?fù)渫ǜ嫦⒃诖貎?nèi)部交互,用于創(chuàng)建簇內(nèi)全網(wǎng)路由表,包括本節(jié)點(diǎn)地址、鄰居數(shù)目、鄰居節(jié)點(diǎn)地址列表、鄰居節(jié)點(diǎn)身份、鄰居節(jié)點(diǎn)狀態(tài)等;

(3)簇拓?fù)渫ǜ嫦?在簇首與簇首之間進(jìn)行拓?fù)渫ǜ?包括簇首地址、中繼簇首地址、簇成員數(shù)、簇成員地址等;

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

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

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

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

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

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

2.1.1 搜索網(wǎng)絡(luò)

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

2.1.2 入網(wǎng)運(yùn)行

站點(diǎn)只要加入網(wǎng)絡(luò),則可與網(wǎng)絡(luò)中成員進(jìn)行通信,并維護(hù)路由和簇拓?fù)浣Y(jié)構(gòu)。

2.1.3 簇首維護(hù)拓?fù)?/p>

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

2.1.4 簇成員維護(hù)拓?fù)?/p>

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

2.1.5 靜默

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

2.1.6 退網(wǎng)

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

2.2 簇首形成與維護(hù)

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

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

簇形成是指在網(wǎng)絡(luò)建立時(shí),網(wǎng)絡(luò)形成多個(gè)簇的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)過程。主要步驟如下:

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

(2)根據(jù)消息觸發(fā)機(jī)制,發(fā)送hello 消息或者本地拓?fù)渫ǜ嫦?

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

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

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

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

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

2.3 全網(wǎng)簇拓?fù)?/h3>

全網(wǎng)簇簇拓?fù)浒l(fā)現(xiàn)通過接收處理簇拓?fù)渫ǜ嫦?獲取一定跳數(shù)范圍內(nèi)簇首及其成員的可達(dá)信息,簇拓?fù)湫畔诖赝負(fù)浔碇小Ｖ饕藢?duì)兩個(gè)表的建立與維護(hù)。

(1)鄰接簇表

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

(2)簇拓?fù)浔?/p>

簇拓?fù)浔碛擅總€(gè)簇的簇首建立和維護(hù),通過發(fā)送簇拓?fù)渫ǜ嫦?互相通告每個(gè)簇的節(jié)點(diǎn),簇間網(wǎng)關(guān)節(jié)點(diǎn)記錄網(wǎng)絡(luò)中的簇首和成員信息,包括目的簇首地址、下一跳簇首地址、當(dāng)前簇首到目的簇首的簇跳數(shù)、下一跳簇間網(wǎng)關(guān)節(jié)點(diǎn)地址、簇內(nèi)成員地址列表。

2.4 路由計(jì)算

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

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

(1)簇間網(wǎng)關(guān)節(jié)點(diǎn)接收到hello 消息后,將其納入鄰居節(jié)點(diǎn)表,如果該節(jié)點(diǎn)是成員節(jié)點(diǎn),并通過簇間拓?fù)湎⒒蛘弑镜赝負(fù)湎⒐芾淼弥摮蓡T節(jié)點(diǎn)對(duì)應(yīng)的簇首節(jié)點(diǎn),則將其與簇首對(duì)應(yīng),否則簇首為未知;如果該節(jié)點(diǎn)是簇首節(jié)點(diǎn),并且是已知簇首節(jié)點(diǎn)則將其更新周期重置,如果是未知簇首則新增加簇表項(xiàng);

(2)簇間網(wǎng)關(guān)節(jié)點(diǎn)接收到本地拓?fù)湎⒑?將本地簇首對(duì)應(yīng)的成員地址全部更新,簇間網(wǎng)關(guān)節(jié)點(diǎn)會(huì)連接有多個(gè)簇首;

(3)簇間網(wǎng)關(guān)節(jié)點(diǎn)接收到簇拓?fù)湎⒑?將簇拓?fù)湎l(fā)送到簇首節(jié)點(diǎn),并將本地維護(hù)的簇首和簇成員表進(jìn)行更新。

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

圖3 端到端時(shí)延Fig.3 End-to-end delay

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

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

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

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

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

4 結(jié) 論

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

[1] 史美林, 英春.自組網(wǎng)路由協(xié)議綜述[ J] .通信學(xué)報(bào),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)絡(luò)的體系結(jié)構(gòu)及其設(shè)計(jì)[ 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.