??? 摘? 要： 針對無線Ad Hoc網絡系統的需求，基于VxWorks操作系統，設計并實現了一種基于多信道的鄰居管理協議，用于實現鄰居的發現、刪除以及全網節點的連通性維護。測試結果表明，該協議能確保網絡節點之間高效可靠地完成鄰居管理功能。?

??? 關鍵詞： 無線Ad Hoc； 多信道； 鄰居管理； 連通表

?

??? 在無線Ad Hoc網絡中，鄰居管理^[1]是網絡正常工作的基礎。唯有通過與鄰居節點的信息交互，無線自組網才能通過路由控制消息的交換建立正確的路由，從而在網絡中實現多跳通信。現有的鄰居管理協議大多作為其他協議的子模塊為主協議提供支持，如典型的DSDV（Destination-Sequenced Distance-Vector）路由協議^[2]，通過周期性地交換HELLO消息檢測鄰居節點。除了基于定時消息的鄰居管理協議之外，事件驅動的鄰居管理協議是另一類分支^[3]，其主要特點為：(1)僅在需要維護更新拓撲信息時才發送HELLO消息；(2)使用序列號檢測鄰居信息的新舊程度與拓撲的變化狀態。在上述協議中，由于每個節點都需要實時維護鄰居信息，這樣在拓撲變化較快的環境中，大量的拓撲更新消息會占用過多的信道資源，使得系統效率下降。比較方便的解決方法是：采用基于多信道的方式，使用多個信道即可在物理上增加信道帶寬，又能降低節點沖突的機會，顯著提高了網絡性能。針對某特定環境對無線Ad Hoc網絡的需要，本文設計并實現了一種基于多信道的鄰居管理協議。?

1 基于多信道的NM協議功能需求?

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

2 NM協議的設計與實現?

2.1 鄰居管理操作?

??? 基于多信道的NM機制，采用TDMA的方式，將信道劃分為M個控制信道和多個業務信道，每個節點分配固定的控制信道，節點在控制信道公告NM信息分組，同時監聽鄰居節點的公告信息。?

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

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

??? 每個節點維護一個連通表，表示全網節點鏈路的雙向連通性，用矩陣A[i][j]表示。?

???

其中，i、j表示節點的ID號，構成矩陣的行和列，行數和列數等于網內活動節點數，對應的元素表示雙向連通狀態。?

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

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

??? 連通表的初始值為全零，當節點入網成功后，以請求的方式從鄰居節點得到全網最新的連通表，建立初始連通表。當節點第一個開始組網時，連通表為初始值全零。?

??? (2) 鄰居發現和刪除?

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

?

?

??? 實現鄰居發現后，節點通過鏈路監測機制，當在一連續時間段內沒有收到鄰居節點的HELLO消息時，表示鏈路斷開，則從鄰居列表中將鄰居節點ID號刪除。?

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

??? 節點通過鄰居的發現與刪除機制，修改連通表，并全網廣播鄰居變化信息，使全網節點的連通表達到同步。節點收到鄰居變化信息分組后，查看分組中的源節點ID號和SEQ，判斷是否有該ID和SEQ的記錄，如果沒有則更新連通表，轉發該分組，否則丟棄。?

2.2 實現方案?

??? 在本系統中，鏈路層設計采用“底層驅動軟件＋嵌入式實時多任務操作系統＋協議棧”的設計結構，主要完成TDMA信道接入協議與NM協議的設計，本文主要實現NM協議。鏈路層總體軟件結構如圖2所示。硬件平臺采用S3C2510的32位網絡處理器和相應的外設構成硬件平臺，RTOS采用VxWorks，使用I/O口進行NM數據分組的收發，使用串口將連通表發送給網絡層。?

?

?

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

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

?

?

??? 圖3中，每一個虛線框圖對應一個獨立的任務，并建立鄰居列表和連通表兩個全局變量。其設計思想如下：?

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

??? (2) 數據處理任務對不同的NM信息進行不同的處理。首先通過鄰居連通表的接收，建立初始的連通表。通過HELLO消息包實現鄰居的發現，維護鄰居列表和連通表；通過鄰居變化信息包來判斷兩跳范圍外的節點鏈路變化情況，若第一次收到，則修改連通表，轉發鄰居變化信息。 ?

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

??? (4) 數據處理任務產生二進制信號量Sem1和Sem2，分別觸發I/O口發送任務和串口發送任務，完成任務的同步，泛洪鄰居變化信息和發送連通表到網絡層。?

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

3 功能測試?

??? NM協議模塊位于無線Ad Hoc網絡系統體系結構框架內，現有的網絡節點已研制成功，本文在真實的網絡節點上對NM模塊功能進行設計開發和測試，如圖4所示為測試環境。?

?

?

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

?

?

??? 根據NM的功能測試結果可以看出：此方案能提供實時、充分的鄰居節點信息，建立全網統一的連通表，有助于提高上層應用的性能。?

??? 本文針對某工作于特定環境的無線Ad Hoc網絡的需要，在鏈路層設計了一種基于多信道的鄰居管理協議，該協議不僅能準確地掌握鄰居節點信息，還能維護全網節點統一的連通表，有效地服務于網絡層，并在VxWorks操作系統下對該協議進行了設計，功能測試結果表明，該協議穩定、可靠、準確。本文提出的鄰居管理協議適用于網絡規模較小的無線Ad Hoc網絡。?

參考文獻?

[1] 鄭少仁,王海濤,趙志峰,等. Ad Hoc網絡技術. 北京：人民郵電出版社, 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]?風河公司. VxWorks開發人員指南叢書VxWorks程序員指南. 北京：清華大學出版社, 2003