一種改進(jìn)的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法

李經(jīng)安徐志平

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

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

一種改進(jìn)的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法

李經(jīng)安1徐志平2

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

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

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

無線自組網(wǎng) 鄰節(jié)點(diǎn)發(fā)現(xiàn) 定向天線 波束掃描

1 引言

當(dāng)今，由于移動通信、無線網(wǎng)絡(luò)和因特網(wǎng)技術(shù)的高速發(fā)展，當(dāng)前信息領(lǐng)域的研究方向便轉(zhuǎn)向了如何更好的運(yùn)用通信及網(wǎng)絡(luò)技術(shù)為人們提供便利的服務(wù)。無線網(wǎng)絡(luò)自身具有靈活性和方便性等特點(diǎn)，這些特點(diǎn)引起了研究者的關(guān)注，它的應(yīng)用范圍也得到了擴(kuò)展。

鄰節(jié)點(diǎn)發(fā)現(xiàn)是無線網(wǎng)絡(luò)初始化過程中的關(guān)鍵步驟之一，有效的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法對于大部分的基于無線網(wǎng)絡(luò)的MAC協(xié)議、路由算法和拓?fù)淇刂扑惴ㄊ潜夭豢缮俚腫1]，鄰節(jié)點(diǎn)發(fā)現(xiàn)算法的效率的高低是網(wǎng)絡(luò)性能的制約。以定向天線模式下的無線Ad Hoc網(wǎng)絡(luò)為研究對象，討論現(xiàn)有鄰節(jié)點(diǎn)算法存在的不足，并提出一種改進(jìn)的鄰節(jié)點(diǎn)算法。

2 定向天線的Ad Hoc鄰節(jié)點(diǎn)發(fā)現(xiàn)算法

2.1 定向鄰節(jié)點(diǎn)發(fā)現(xiàn)(DND)算法

鄰節(jié)點(diǎn)發(fā)現(xiàn)在采用全向天線的Ad Hoc網(wǎng)絡(luò)中是一件簡單的事情，但是在采用定向天線的Ad Hoc網(wǎng)絡(luò)中，并不如此。由于定向天線在一段時間內(nèi)只能向某個扇區(qū)中發(fā)射信號，而在這段時間中只有恰好在定向天線覆蓋區(qū)域內(nèi)的鄰節(jié)點(diǎn)才能收到信號，其他收不到信號的鄰節(jié)點(diǎn)，也就不可能被發(fā)現(xiàn)。同樣，當(dāng)鄰節(jié)點(diǎn)收到信號向源節(jié)點(diǎn)回復(fù)信息時，只有天線對準(zhǔn)源節(jié)點(diǎn)，才能收到回復(fù)。為了將定向天線運(yùn)用于Ad Hoc網(wǎng)絡(luò)，對定向鄰節(jié)點(diǎn)發(fā)現(xiàn)(DND)機(jī)制及算法進(jìn)行了研究。

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

在軍事領(lǐng)域中，戰(zhàn)術(shù)網(wǎng)絡(luò)依賴于GPS是不可取的。因此提出了非輔助TD模式和TRD模式的定向鄰節(jié)點(diǎn)發(fā)現(xiàn)算法。

慢速掃描院天線以角速度贅沿一定的方向?qū)?60毅范圍內(nèi)各個覆蓋區(qū)進(jìn)行慢速掃描。它在每個波束覆蓋區(qū)的停留時間大于，即天線的波束在1個覆蓋區(qū)停留的時間應(yīng)大于快掃描時天線波束掃描1周的時間。設(shè)天線的波束寬度也是琢（弧度），則天線的慢掃描周期s。例如：

3 改進(jìn)的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法

3.1 現(xiàn)有算法存在的問題

2.2 非輔助TD模式的定向鄰節(jié)點(diǎn)發(fā)現(xiàn)算法

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

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

該算法有主動發(fā)現(xiàn)算法和被動發(fā)現(xiàn)算法，根據(jù)不同應(yīng)用環(huán)境，鄰節(jié)點(diǎn)發(fā)現(xiàn)算法可以按周期執(zhí)行，也可以根據(jù)事件觸發(fā)。

在上一章中詳細(xì)介紹了非輔助鄰節(jié)點(diǎn)發(fā)現(xiàn)算法DND[5]。該算法體現(xiàn)了定向天線的優(yōu)勢，但同時也有一些不足之處：會產(chǎn)生“聽不見”問題[6]，從而降低鄰節(jié)點(diǎn)發(fā)現(xiàn)性能。

3.2 改進(jìn)的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法的提出

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

改進(jìn)算法下的2種天線波束掃描方式如下：

快速掃描：天線波束以角速度棕沿一定的方向?qū)?60毅范圍內(nèi)各個覆蓋區(qū)進(jìn)行快速掃描。設(shè)天線波束寬度為琢（弧度），在每個覆蓋區(qū)停留時間為子s，則掃描角速度應(yīng)滿足等式單位是弧度/s；快速掃描周期位是s。例如：

慢速掃描：天線以角速度贅沿一定的方向?qū)?60毅范圍內(nèi)各個覆蓋區(qū)進(jìn)行慢速掃描。它在每個波束覆蓋區(qū)的停留時間大于，即天線的波束在1個覆蓋區(qū)停留的時間應(yīng)大于快掃描時天線波束掃描1周的時間。設(shè)天線的波束寬度也是琢（弧度），則天線的慢掃描周期

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

2.3 非輔助TRD模式的定向鄰節(jié)點(diǎn)發(fā)現(xiàn)算法

非輔助TRD模式的定向鄰節(jié)點(diǎn)發(fā)現(xiàn)算法也是不需要GPS和其他信息輔助，收發(fā)分組均采用定向天線的DND算法。在Ad Hoc網(wǎng)絡(luò)中如何利用定向天線的優(yōu)勢對定向天線進(jìn)行合理的控制是非常重要的。

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

快速掃描：天線波束以角速度棕沿一定的方向?qū)?60毅范圍內(nèi)各個覆蓋區(qū)進(jìn)行快速掃描。設(shè)天線波束寬度為琢（弧度），在每個覆蓋區(qū)停留時間為子s，則掃描角速度應(yīng)滿足等式

主動鄰節(jié)點(diǎn)發(fā)現(xiàn)過程流程圖如圖2所示。參數(shù)定義如下：

圖2 主動鄰居發(fā)現(xiàn)過程流程表

3.3 算法實(shí)現(xiàn)狀態(tài)圖

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

圖3 鄰節(jié)點(diǎn)發(fā)現(xiàn)過程狀態(tài)轉(zhuǎn)移表

4 仿真結(jié)果分析

根據(jù)狀態(tài)轉(zhuǎn)移圖即可編寫仿真程序，采用Xilinx公司的ISE 14.3集成開發(fā)環(huán)境作為平臺對以上算法進(jìn)行仿真實(shí)現(xiàn)，仿真結(jié)果如圖4耀圖6所示。

圖4中，相同顏色的波形代表同一個波束扇區(qū)的波形，上方為輸入波形，下方為輸出波形，第一條黑色波形為時鐘信號，第二條黑色波形為復(fù)位信號，接下來的第3至第8條綠色、紅色、淺藍(lán)色、黃色、棕色、深綠色、藍(lán)色波形分別為6個扇區(qū)的輸入波形，第9至第14條波形分別為6個扇區(qū)的輸出波形?？梢钥吹皆趯?yīng)扇區(qū)內(nèi)，如果有Hello數(shù)據(jù)包被接收到，則節(jié)點(diǎn)隨機(jī)等待一段時間后會發(fā)送回復(fù)信息，仿真結(jié)果符合預(yù)期期望。

圖4 每個扇區(qū)輪流收到Hello數(shù)據(jù)包仿真圖

如圖5所示，其中各波形含義同上所述?？梢钥闯觯?dāng)掃描波束位于第4扇區(qū)時，第三扇區(qū)和第四扇區(qū)方向都有Hello數(shù)據(jù)包，但由于掃描波束位于第四扇區(qū)，所以只能接收到第四扇區(qū)的Hello數(shù)據(jù)包，不能接收到第三扇區(qū)的數(shù)據(jù)包，所以第四扇區(qū)有回復(fù)信息，而第三扇區(qū)沒有回復(fù)信息。第五扇區(qū)和第六扇區(qū)同樣如此，可見仿真結(jié)果符合定向天線的特征，仿真結(jié)果符合預(yù)期結(jié)果。

圖5 定向天線同時收到Hello數(shù)據(jù)包狀態(tài)仿真圖

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

圖6 主動鄰居發(fā)現(xiàn)過程仿真圖

5 結(jié)束語

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

[1]王金龍,王呈貴,吳啟暉,等.Ad Hoc移動無線網(wǎng)絡(luò)[M].北京:國防工業(yè)出版社,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鄰節(jié)點(diǎn)發(fā)現(xiàn)算法與分析[J].西安電子科技大學(xué)學(xué)報(bào)（自然不科學(xué)版）,2007,34(3):343-344.

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

[6]李瑞睿,鄭相全,王靖,等.一種基于定向天線的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法[J].現(xiàn)代電子技術(shù),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