一種改進的鄰節點發現算法

李經安徐志平

（1中國電子科技集團公司第五十四研究所，河北石家莊 050081）

（2中國人民解放軍96275部隊，河南洛陽 471003）

一種改進的鄰節點發現算法

李經安1徐志平2

（1中國電子科技集團公司第五十四研究所，河北石家莊 050081）

（2中國人民解放軍96275部隊，河南洛陽 471003）

鄰節點發現是無線Ad Hoc網絡自組織過程中的關鍵步驟之一，鄰節點發現效率的高低直接影響著網絡的性能。以定向天線模式下的無線Ad Hoc網絡為研究對象，對鄰居發現問題進行深入探討，通過歸納和總結現有鄰節點發現算法的實現機理，找出現有鄰節點算法的不足，適當改進算法，針對定向天線，提出一種采用慢掃描時多次發送Hello數據包的方案，并對算法進行了仿真，驗證了鄰節點發現算法的合理性且完全符合預期結果。

無線自組網 鄰節點發現 定向天線 波束掃描

1 引言

當今，由于移動通信、無線網絡和因特網技術的高速發展，當前信息領域的研究方向便轉向了如何更好的運用通信及網絡技術為人們提供便利的服務。無線網絡自身具有靈活性和方便性等特點，這些特點引起了研究者的關注，它的應用范圍也得到了擴展。

鄰節點發現是無線網絡初始化過程中的關鍵步驟之一，有效的鄰節點發現算法對于大部分的基于無線網絡的MAC協議、路由算法和拓撲控制算法是必不可少的[1]，鄰節點發現算法的效率的高低是網絡性能的制約。以定向天線模式下的無線Ad Hoc網絡為研究對象，討論現有鄰節點算法存在的不足，并提出一種改進的鄰節點算法。

2 定向天線的Ad Hoc鄰節點發現算法

2.1 定向鄰節點發現(DND)算法

鄰節點發現在采用全向天線的Ad Hoc網絡中是一件簡單的事情，但是在采用定向天線的Ad Hoc網絡中，并不如此。由于定向天線在一段時間內只能向某個扇區中發射信號，而在這段時間中只有恰好在定向天線覆蓋區域內的鄰節點才能收到信號，其他收不到信號的鄰節點，也就不可能被發現。同樣，當鄰節點收到信號向源節點回復信息時，只有天線對準源節點，才能收到回復。為了將定向天線運用于Ad Hoc網絡，對定向鄰節點發現(DND)機制及算法進行了研究。

從物理信道的區別，DND主要分為2種工作模式：定向發射模式TD和定向發射定向接收模式TRD[2,3]。TD模式下，定向天線用于發射，全向天線用于接收，而TRD模式下，收發都用定向天線，但收發掃描速度和方向性是不一樣的。從對其他信息的依賴性方面區分，DND分為輔助DND和非輔助DND。顧名思義，輔助DND需要借助定位系統或其他設施的輔助，而非輔助DND的實現過程具有很強的獨立性，不需要其他信息輔助。

在軍事領域中，戰術網絡依賴于GPS是不可取的。因此提出了非輔助TD模式和TRD模式的定向鄰節點發現算法。

慢速掃描院天線以角速度贅沿一定的方向對360毅范圍內各個覆蓋區進行慢速掃描。它在每個波束覆蓋區的停留時間大于，即天線的波束在1個覆蓋區停留的時間應大于快掃描時天線波束掃描1周的時間。設天線的波束寬度也是琢（弧度），則天線的慢掃描周期s。例如：

3 改進的鄰節點發現算法

3.1 現有算法存在的問題

2.2 非輔助TD模式的定向鄰節點發現算法

非輔助TD模式的定向鄰節點發現算法[4]是不用GPS和其他信息輔助，采用定向發送Hello分組，使用全向天線接收Hello分組的DND算法。定向天線和全向天線的方向圖如圖1所示，定向模式下，波束角為60°，6個定向天線覆蓋360°。每次只能在一個方向上發送Hello分組，全向模式下，可以接收所有方向上發送來的分組。

據彝良縣外宣辦介紹，此次滑坡塌方量達1萬立方米以上，并阻斷小河形成堰塞湖；油房小學教學樓全部被掩埋，據初查18名學生被埋在垮塌的教學樓內；學校附近2戶農戶房舍被掩埋，其中1戶農戶1家3口全部逃離，另1戶1人被掩埋。

該算法有主動發現算法和被動發現算法，根據不同應用環境，鄰節點發現算法可以按周期執行，也可以根據事件觸發。

在上一章中詳細介紹了非輔助鄰節點發現算法DND[5]。該算法體現了定向天線的優勢，但同時也有一些不足之處：會產生“聽不見”問題[6]，從而降低鄰節點發現性能。

3.2 改進的鄰節點發現算法的提出

本文針對現有算法存在的問題對算法進行了改進，第一假設每個節點都有自己的時鐘且不同步；第二假設所有節點均采用波束寬度為60毅的定向天線。

改進算法下的2種天線波束掃描方式如下：

快速掃描：天線波束以角速度棕沿一定的方向對360毅范圍內各個覆蓋區進行快速掃描。設天線波束寬度為琢（弧度），在每個覆蓋區停留時間為子s，則掃描角速度應滿足等式單位是弧度/s；快速掃描周期位是s。例如：

慢速掃描：天線以角速度贅沿一定的方向對360毅范圍內各個覆蓋區進行慢速掃描。它在每個波束覆蓋區的停留時間大于，即天線的波束在1個覆蓋區停留的時間應大于快掃描時天線波束掃描1周的時間。設天線的波束寬度也是琢（弧度），則天線的慢掃描周期

圖1 定向天線與全向天線方向示意圖

2.3 非輔助TRD模式的定向鄰節點發現算法

非輔助TRD模式的定向鄰節點發現算法也是不需要GPS和其他信息輔助，收發分組均采用定向天線的DND算法。在Ad Hoc網絡中如何利用定向天線的優勢對定向天線進行合理的控制是非常重要的。

這種非輔助TRD算法稱為盲TRD算法[4]。定義了以下2種天線波束掃描方式。

快速掃描：天線波束以角速度棕沿一定的方向對360毅范圍內各個覆蓋區進行快速掃描。設天線波束寬度為琢（弧度），在每個覆蓋區停留時間為子s，則掃描角速度應滿足等式

主動鄰節點發現過程流程圖如圖2所示。參數定義如下：

圖2 主動鄰居發現過程流程表

3.3 算法實現狀態圖

根據上一節中對算法的詳細描述可以得到如圖3所示的狀態圖。其中Idle為空閑狀態；Sniffer為快掃描偵聽狀態；Send為慢掃描發送狀態；Judge為判斷狀態，用來判斷時間是否超過門限值；為慢掃描周期。

圖3 鄰節點發現過程狀態轉移表

4 仿真結果分析

根據狀態轉移圖即可編寫仿真程序，采用Xilinx公司的ISE 14.3集成開發環境作為平臺對以上算法進行仿真實現，仿真結果如圖4耀圖6所示。

圖4中，相同顏色的波形代表同一個波束扇區的波形，上方為輸入波形，下方為輸出波形，第一條黑色波形為時鐘信號，第二條黑色波形為復位信號，接下來的第3至第8條綠色、紅色、淺藍色、黃色、棕色、深綠色、藍色波形分別為6個扇區的輸入波形，第9至第14條波形分別為6個扇區的輸出波形。可以看到在對應扇區內，如果有Hello數據包被接收到，則節點隨機等待一段時間后會發送回復信息，仿真結果符合預期期望。

圖4 每個扇區輪流收到Hello數據包仿真圖

如圖5所示，其中各波形含義同上所述。可以看出，當掃描波束位于第4扇區時，第三扇區和第四扇區方向都有Hello數據包，但由于掃描波束位于第四扇區，所以只能接收到第四扇區的Hello數據包，不能接收到第三扇區的數據包，所以第四扇區有回復信息，而第三扇區沒有回復信息。第五扇區和第六扇區同樣如此，可見仿真結果符合定向天線的特征，仿真結果符合預期結果。

圖5 定向天線同時收到Hello數據包狀態仿真圖

如圖6所示，當節點的某個扇區信道空閑時間大于慢掃描時在一個扇區停留時間時，該扇區進入主動鄰居發現程序，定向天線等間隔發送六次分組信息，發送間隔和節點快速掃描在一個扇區的停留時間是相同的，如果該節點收到鄰居的回復信息，則將此節點的相關信息寫入自己的鄰節點信息列表中，并將此節點標記為已發現。從圖中扇區輸出信號的第二、第四、第五、第六波形可以看到仿真結果和理論分析情況符合，仿真結果符合期望。

圖6 主動鄰居發現過程仿真圖

5 結束語

由以上幾幅仿真結果截圖以及分析可以看出，仿真程序符合上文所提出的鄰節點發現協議的流程要求，仿真結果完全符合預期結果。該改進算法避免“聽不見”問題，提高了鄰節點發現的速度和效率。仿真結果表明，此次基于FPGA的鄰節點發現協議的設計與實現是成功的，仿真結果符合預期期望。在DND鄰居發現算法的實驗中假設信道為理想信道，沒有考慮多徑效應、信道衰落等問題。如何使得鄰居發現方法以適用于非理想的信道條件下的應用是個待研究的問題。

[1]王金龍,王呈貴,吳啟暉,等.Ad Hoc移動無線網絡[M].北京:國防工業出版社,2004.

[2]Z.Zhang.DTRA:Directional Transmission and Reception Algorithms in WLANs with directional antennas for QoSsupport[J].In IEEE Networks,2005,19(3):27-32.

[3]Z.Zhang and B.Li.Neighbor discovery in mobile ad hoc self-onfiguring networks with directional antennas:algorithms and comparisons[J].In IEEE Transactions on Wireless Communications,2008,7(5-1):1540-1549.

[4]趙瑞琴,文愛軍,劉增基，等.有效支持智能天線的MANET鄰節點發現算法與分析[J].西安電子科技大學學報（自然不科學版）,2007,34(3):343-344.

[5]趙瑞琴,劉增基.采用定向天線的MANET鄰節點發現算法研究[J].無線電子通信技術,2006,32(4):30-31．

[6]李瑞睿,鄭相全,王靖,等.一種基于定向天線的鄰節點發現算法[J].現代電子技術,2011,34(5):36-30.

An Improved Neighbor Discovery Algorithm

LI Jing-an1,XU Zhi-ping2
（1 The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China）
（2 Unit 96275,PLA,Luoyang He爺nan 471003,China）

Neighbor discovery is one of the important steps in the process of self-organization of wireless Ad Hoc networks,which has significant impact on the network performance.Based on the directional antenna mode of wireless Ad Hoc network as the research object,through summarizing the existing implementation mechanism of the neighbor discovery algorithms,this paper points out the insufficiencies of the existing neighbor discovery algorithms,and proposes the appropriate modification of the existing algorithms.For directional antenna,a kind of wireless Ad Hoc network neighbor discovery algorithm is put forward in which Hello packets are sent multiple times duringslow scanning,the simulation of the algorithm verifies that the improved algorithm is reasonable and the simulation result is in accordance with the expected results.

Ad Hoc network;neighbor discovery;directional antenna;beam scanning

TP391.4

A

1008-1739（2015）12-47-3

定稿日期：2015-05-26