《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 業(yè)界動態(tài) > 一種無線Ad Hoc網(wǎng)絡(luò)中鄰居管理協(xié)議的設(shè)計與實現(xiàn)

一種無線Ad Hoc網(wǎng)絡(luò)中鄰居管理協(xié)議的設(shè)計與實現(xiàn)

2009-03-06
作者:馮文江, 楊文靜

??? 摘? 要: 針對無線Ad Hoc網(wǎng)絡(luò)系統(tǒng)的需求,,基于VxWorks操作系統(tǒng),,設(shè)計并實現(xiàn)了一種基于多信道的鄰居管理協(xié)議,用于實現(xiàn)鄰居的發(fā)現(xiàn),、刪除以及全網(wǎng)節(jié)點的連通性維護(hù)。測試結(jié)果表明,,該協(xié)議能確保網(wǎng)絡(luò)節(jié)點之間高效可靠地完成鄰居管理功能,。?

??? 關(guān)鍵詞: 無線Ad Hoc; 多信道,; 鄰居管理,; 連通表

?

??? 在無線Ad Hoc網(wǎng)絡(luò)中,鄰居管理[1]是網(wǎng)絡(luò)正常工作的基礎(chǔ),。唯有通過與鄰居節(jié)點的信息交互,,無線自組網(wǎng)才能通過路由控制消息的交換建立正確的路由,從而在網(wǎng)絡(luò)中實現(xiàn)多跳通信?,F(xiàn)有的鄰居管理協(xié)議大多作為其他協(xié)議的子模塊為主協(xié)議提供支持,,如典型的DSDV(Destination-Sequenced Distance-Vector)路由協(xié)議[2],通過周期性地交換HELLO消息檢測鄰居節(jié)點,。除了基于定時消息的鄰居管理協(xié)議之外,,事件驅(qū)動的鄰居管理協(xié)議是另一類分支[3],其主要特點為:(1)僅在需要維護(hù)更新拓?fù)湫畔r才發(fā)送HELLO消息,;(2)使用序列號檢測鄰居信息的新舊程度與拓?fù)涞淖兓癄顟B(tài),。在上述協(xié)議中,由于每個節(jié)點都需要實時維護(hù)鄰居信息,,這樣在拓?fù)渥兓^快的環(huán)境中,,大量的拓?fù)涓孪加眠^多的信道資源,使得系統(tǒng)效率下降,。比較方便的解決方法是:采用基于多信道的方式,,使用多個信道即可在物理上增加信道帶寬,又能降低節(jié)點沖突的機(jī)會,,顯著提高了網(wǎng)絡(luò)性能,。針對某特定環(huán)境對無線Ad Hoc網(wǎng)絡(luò)的需要,本文設(shè)計并實現(xiàn)了一種基于多信道的鄰居管理協(xié)議,。?

1 基于多信道的NM協(xié)議功能需求?

??? 傳統(tǒng)的無線自組網(wǎng)吞吐量不高,,尤其隨著網(wǎng)絡(luò)規(guī)模的增大,節(jié)點吞吐量下降,。近年來通過在MAC層使用多個信道,,無線自組網(wǎng)的吞吐量得到顯著提高[4]。本文研究的無線Ad Hoc網(wǎng)絡(luò),針對某特定應(yīng)用環(huán)境的需要,,采用TDMA的信道接入機(jī)制,,節(jié)點分為物理層、鏈路層,、網(wǎng)絡(luò)層,。由于網(wǎng)絡(luò)規(guī)模比較小(節(jié)點數(shù)不超過12),,采用固定信道分配方式,,每個節(jié)點分配固定的控制信道和業(yè)務(wù)信道,使控制報文和數(shù)據(jù)報文相分離,,這使得在TDMA模式下,,幀的發(fā)送具有無沖突、周期性,、固定幀長等特點,。雖然鏈路層并不關(guān)心鄰居信息,,但是由于鏈路層可以比網(wǎng)絡(luò)層更有效地偵測到鄰居信息,,能減少網(wǎng)絡(luò)層的路由開銷,提高信道利用率,?;谏鲜鎏攸c,使得在鏈路層完成NM功能極具優(yōu)勢,。本文針對無線Ad Hoc網(wǎng)絡(luò)的功能需求,,在VxWorks嵌入式系統(tǒng)下設(shè)計并實現(xiàn)了一種基于多信道的鄰居管理NM(Neighbor Management)協(xié)議。該協(xié)議針對網(wǎng)絡(luò)初始化的鄰居發(fā)現(xiàn)和全網(wǎng)的鏈路維護(hù)兩個場景,。在鄰居發(fā)現(xiàn)階段,,采用時間驅(qū)動方式,定時與鄰居節(jié)點交換HELLO消息,,查詢鄰居鏈路的雙向連通,,檢測鄰居鏈路的變化;在全網(wǎng)鏈路維護(hù)階段,采用事件驅(qū)動方式,,泛洪鄰居變化信息,,建立和維護(hù)全網(wǎng)活動節(jié)點的拓?fù)浞植迹ㄟB通表)。?

2 NM協(xié)議的設(shè)計與實現(xiàn)?

2.1 鄰居管理操作?

??? 基于多信道的NM機(jī)制,,采用TDMA的方式,,將信道劃分為M個控制信道和多個業(yè)務(wù)信道,每個節(jié)點分配固定的控制信道,,節(jié)點在控制信道公告NM信息分組,,同時監(jiān)聽鄰居節(jié)點的公告信息。?

??? 為了不影響節(jié)點的正常信道接入,每個節(jié)點建立一個幀號,,幀號取16位(0~65 535),在達(dá)到最大值時從0開始循環(huán)取值,。控制信道每發(fā)送一個時幀,,幀號就增1,,并把該幀號添加到鏈路分組中,剛?cè)刖W(wǎng)的節(jié)點收到鄰居節(jié)點的鏈路分組,,修改本地幀號使之與鄰居節(jié)點一致,,從而達(dá)到全網(wǎng)節(jié)點在同一時間幀號一致。對于HELLO信息的公告,,全網(wǎng)節(jié)點在幀號范圍(1 024×n~1 024×n+10)發(fā)送,,避免了在控制信道的HELLO信息與其他控制報文的沖突,并使節(jié)點在統(tǒng)一時間段內(nèi)進(jìn)行HELLO消息廣播,,縮短了鄰居發(fā)現(xiàn)時間,。另外,公告鄰居變化表時,,如果節(jié)點有控制報文等待發(fā)送,,節(jié)點將其緩沖,等待公告發(fā)送結(jié)束后,,再繼續(xù)發(fā)送,。由于只有鄰居發(fā)現(xiàn)和刪除時才廣播鄰居變化表,占用控制信道時間比較少,,所以造成的控制報文延遲很小,。?

??? HELLO消息的格式為ID號、鄰居數(shù),、鄰居列表,。鄰居列表是一個動態(tài)的一維數(shù)組,列出了它最近檢測到的與它單向連通的鄰居節(jié)點的ID號,。鄰居變化表的格式為源節(jié)點ID號,、節(jié)點ID號、鏈路狀態(tài)和序列號SEQ,。鏈路狀態(tài)‘1’表示連通,,‘0’表示不連通。為了重復(fù)分組檢測,,每個節(jié)點維護(hù)一個序列號SEQ,,節(jié)點每次發(fā)送一個鄰居變化分組其維護(hù)的SEQ單調(diào)增1,其他節(jié)點收到一個信息分組依靠序列號和源節(jié)點ID號來判斷自己是否轉(zhuǎn)發(fā)過該分組,。?

??? 每個節(jié)點維護(hù)一個連通表,,表示全網(wǎng)節(jié)點鏈路的雙向連通性,,用矩陣A[i][j]表示。?

???

其中,,i,、j表示節(jié)點的ID號,構(gòu)成矩陣的行和列,,行數(shù)和列數(shù)等于網(wǎng)內(nèi)活動節(jié)點數(shù),,對應(yīng)的元素表示雙向連通狀態(tài)。?

??? 基于多信道的鄰居管理的操作主要分為以下三步:?

??? (1) 初始連通表的建立?

??? 連通表的初始值為全零,,當(dāng)節(jié)點入網(wǎng)成功后,,以請求的方式從鄰居節(jié)點得到全網(wǎng)最新的連通表,建立初始連通表,。當(dāng)節(jié)點第一個開始組網(wǎng)時,,連通表為初始值全零。?

??? (2) 鄰居發(fā)現(xiàn)和刪除?

??? 節(jié)點通過幀號的范圍,,周期性地廣播HELLO消息,,同時監(jiān)聽鄰居節(jié)點的HELLO信息,圖1是一個鄰居發(fā)現(xiàn)的例子,。假設(shè)兩個節(jié)點A與B分別處于不同的控制信道Ta和Tb,。首先節(jié)點A在Ta上公告的HELLO消息被B接收,B將A的ID號添加到其維護(hù)的鄰居列表NLb中,,同時在信道Tb上公告HELLO消息(NLb),,A收到公告后,,將B的ID號添加到NLa中,,同時查看NLb,發(fā)現(xiàn)B已經(jīng)接收到之前A所發(fā)出的公告,,A認(rèn)定兩者是鄰居關(guān)系,。在下一次公告時,B收到A的公告信息,,同樣也可以判斷與A為鄰居關(guān)系,。通過這種握手機(jī)制完成了相互發(fā)現(xiàn)過程。容易推導(dǎo),,節(jié)點在前兩次公告后即可實現(xiàn)相互發(fā)現(xiàn)過程,。?

?

?

??? 實現(xiàn)鄰居發(fā)現(xiàn)后,節(jié)點通過鏈路監(jiān)測機(jī)制,,當(dāng)在一連續(xù)時間段內(nèi)沒有收到鄰居節(jié)點的HELLO消息時,,表示鏈路斷開,則從鄰居列表中將鄰居節(jié)點ID號刪除,。?

??? (3) 泛洪鄰居變化信息?

??? 節(jié)點通過鄰居的發(fā)現(xiàn)與刪除機(jī)制,,修改連通表,,并全網(wǎng)廣播鄰居變化信息,使全網(wǎng)節(jié)點的連通表達(dá)到同步,。節(jié)點收到鄰居變化信息分組后,,查看分組中的源節(jié)點ID號和SEQ,判斷是否有該ID和SEQ的記錄,,如果沒有則更新連通表,,轉(zhuǎn)發(fā)該分組,否則丟棄,。?

2.2 實現(xiàn)方案?

??? 在本系統(tǒng)中,,鏈路層設(shè)計采用“底層驅(qū)動軟件+嵌入式實時多任務(wù)操作系統(tǒng)+協(xié)議棧”的設(shè)計結(jié)構(gòu),,主要完成TDMA信道接入?yún)f(xié)議與NM協(xié)議的設(shè)計,,本文主要實現(xiàn)NM協(xié)議。鏈路層總體軟件結(jié)構(gòu)如圖2所示,。硬件平臺采用S3C2510的32位網(wǎng)絡(luò)處理器和相應(yīng)的外設(shè)構(gòu)成硬件平臺,,RTOS采用VxWorks,使用I/O口進(jìn)行NM數(shù)據(jù)分組的收發(fā),,使用串口將連通表發(fā)送給網(wǎng)絡(luò)層,。?

?

?

  VxWorks操作系統(tǒng)是一種嵌入式實時操作系統(tǒng)(RTOS),是嵌入式開發(fā)環(huán)境的主要組成部分,,具有可靠性高,、實時性強(qiáng)、可裁減等特點,。VxWorks為程序員提供了高效的實時任務(wù)調(diào)度,、中斷管理、實時的系統(tǒng)資源以及任務(wù)間通信,。?

基于NM的功能需求和VxWorks操作系統(tǒng)的實時性,,遵循H.Gomma原則[5],將系統(tǒng)劃分為六個任務(wù),,如圖3所示,。?

?

?

??? 圖3中,每一個虛線框圖對應(yīng)一個獨立的任務(wù),,并建立鄰居列表和連通表兩個全局變量,。其設(shè)計思想如下:?

??? (1) 首先從接收任務(wù)I/O口中檢測到鏈路數(shù)據(jù),取出其中的NM消息包,,通過消息隊列Msg發(fā)送到數(shù)據(jù)處理任務(wù),。?

??? (2) 數(shù)據(jù)處理任務(wù)對不同的NM信息進(jìn)行不同的處理。首先通過鄰居連通表的接收,,建立初始的連通表,。通過HELLO消息包實現(xiàn)鄰居的發(fā)現(xiàn),,維護(hù)鄰居列表和連通表;通過鄰居變化信息包來判斷兩跳范圍外的節(jié)點鏈路變化情況,,若第一次收到,,則修改連通表,轉(zhuǎn)發(fā)鄰居變化信息,。 ?

??? (3) 鏈路檢測任務(wù)通過taskdelay(int ticks)函數(shù),,每30s查看鄰居HELLO消息的接收情況,監(jiān)測鄰居鏈路的變化,,若在連續(xù)30s內(nèi)沒有收到鄰居節(jié)點的HELLO消息,,則在鄰居列表中刪除鄰居ID號,修改連通表,,泛洪鄰居變化信息,。?

??? (4) 數(shù)據(jù)處理任務(wù)產(chǎn)生二進(jìn)制信號量Sem1和Sem2,分別觸發(fā)I/O口發(fā)送任務(wù)和串口發(fā)送任務(wù),,完成任務(wù)的同步,,泛洪鄰居變化信息和發(fā)送連通表到網(wǎng)絡(luò)層。?

??? (5) 通過硬件定時器,,設(shè)定時幀的幀號,,在幀號為(1 024×n~1 024×n+10)范圍內(nèi)廣播HELLO消息。?

3 功能測試?

??? NM協(xié)議模塊位于無線Ad Hoc網(wǎng)絡(luò)系統(tǒng)體系結(jié)構(gòu)框架內(nèi),,現(xiàn)有的網(wǎng)絡(luò)節(jié)點已研制成功,,本文在真實的網(wǎng)絡(luò)節(jié)點上對NM模塊功能進(jìn)行設(shè)計開發(fā)和測試,如圖4所示為測試環(huán)境,。?

?

?

??? 在該測試場景中,,節(jié)點1(ID號為1)開始組網(wǎng),節(jié)點2(ID號為2)通過節(jié)點1接入網(wǎng)絡(luò)中,,節(jié)點3(ID號為3)通過節(jié)點2接入網(wǎng)絡(luò)中,,節(jié)點1與節(jié)點2互為鄰居,節(jié)點2與節(jié)點3互為鄰居,。測試的目的是檢驗NM的功能,PC機(jī)與鏈路控制器中的VxWorks平臺通過控制臺串口相連,,用于觀測節(jié)點NM數(shù)據(jù)包的收發(fā)和處理,,通過超級終端從節(jié)點1抓包如圖5:節(jié)點1周期性地發(fā)送HELLO數(shù)據(jù)(-1-0-0-0),當(dāng)?shù)谝淮螜z測到節(jié)點2的HELLO消息包(-2-1-0-0)時,,在鄰居列表中添鄰居ID號(-1-2-0-0),,并更新連通表,泛洪鄰居變化信息(-1-2-1-1),。節(jié)點1第一次收到節(jié)點2發(fā)送的鄰居變化信息(-2-3-1-1)后,,發(fā)現(xiàn)節(jié)點2和節(jié)點3為鄰居,,修改連通表,并轉(zhuǎn)發(fā)該鄰居變化信息包(-2-3-1-1)時,,對于再次收到同樣的鄰居變化信息包(判斷SEQ,,仍為1)時,不作處理,。?

?

?

??? 根據(jù)NM的功能測試結(jié)果可以看出:此方案能提供實時,、充分的鄰居節(jié)點信息,建立全網(wǎng)統(tǒng)一的連通表,,有助于提高上層應(yīng)用的性能,。?

??? 本文針對某工作于特定環(huán)境的無線Ad Hoc網(wǎng)絡(luò)的需要,在鏈路層設(shè)計了一種基于多信道的鄰居管理協(xié)議,,該協(xié)議不僅能準(zhǔn)確地掌握鄰居節(jié)點信息,,還能維護(hù)全網(wǎng)節(jié)點統(tǒng)一的連通表,有效地服務(wù)于網(wǎng)絡(luò)層,,并在VxWorks操作系統(tǒng)下對該協(xié)議進(jìn)行了設(shè)計,,功能測試結(jié)果表明,該協(xié)議穩(wěn)定,、可靠,、準(zhǔn)確。本文提出的鄰居管理協(xié)議適用于網(wǎng)絡(luò)規(guī)模較小的無線Ad Hoc網(wǎng)絡(luò),。?

參考文獻(xiàn)?

[1] 鄭少仁,王海濤,趙志峰,等. Ad Hoc網(wǎng)絡(luò)技術(shù). 北京:人民郵電出版社, 2005.?

[2]?PERKINS C E, BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile?computers. In: Proceedings of SIGCOMM 4. NEW York:ACM Press, 1994:234-244.?

[3]?MOSKO M, GARCIA-LUNA-ACEVES. A self-correcting?neighbor protocol for mobile Ad Hoc wireless networks.Proc. IEEE ICCCN′02, 2002:556-560.?

[4]?KYASANUR P, VAIDYA N H. Capacity of multi-channel ? wireless networks: impact of number of channels and?interfaces. ACM MOBICOM'O5, Cologne,Germanv:43- 57.?

[5]?風(fēng)河公司. VxWorks開發(fā)人員指南叢書VxWorks程序員指南. 北京:清華大學(xué)出版社, 2003

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點,。轉(zhuǎn)載的所有的文章,、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者,。如涉及作品內(nèi)容、版權(quán)和其它問題,,請及時通過電子郵件或電話通知我們,,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失,。聯(lián)系電話:010-82306118,;郵箱:[email protected],。