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

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

?

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

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

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

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

2.1 鄰居管理操作?

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

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

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

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

???

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

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

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

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

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

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

?

?

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

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

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

2.2 實(shí)現(xiàn)方案?

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

?

?

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

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

?

?

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

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

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

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

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

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

3 功能測(cè)試?

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

?

?

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

?

?

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

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