一種適于波束切換移動(dòng)自組網(wǎng)的鄰居發(fā)現(xiàn)改進(jìn)算法

李 麗，鄭博文，劉麗哲

(1.海軍參謀部，北京 100000；2.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

0 引言

隨著人們對(duì)業(yè)務(wù)需求的快速增長(zhǎng)，對(duì)無(wú)線通信系統(tǒng)的通信速率、工作頻段以及組網(wǎng)節(jié)點(diǎn)數(shù)量均提出了更高的要求，有學(xué)者預(yù)測(cè)每秒兆位鏈路在未來(lái)十年內(nèi)將成為現(xiàn)實(shí)[3]，有學(xué)者建議第六代通信技術(shù)應(yīng)用于太赫茲頻段(0.1～10 THz)[4]。更高的載波頻率帶來(lái)了更高的空間損耗，全向天線通信系統(tǒng)也越來(lái)越無(wú)法滿足通信覆蓋要求；節(jié)點(diǎn)數(shù)量的增加，或者節(jié)點(diǎn)通信容量的增加都對(duì)移動(dòng)自組網(wǎng)的容量提出了挑戰(zhàn)。

綜上所述，采用定向天線能夠顯著提高移動(dòng)自組網(wǎng)網(wǎng)絡(luò)容量，更好地滿足業(yè)務(wù)對(duì)移動(dòng)自組網(wǎng)提出的要求。

在定向天線移動(dòng)自組網(wǎng)中，鄰居發(fā)現(xiàn)是進(jìn)行任何通信的前提，是指節(jié)點(diǎn)開(kāi)機(jī)后，在沒(méi)有鄰節(jié)點(diǎn)任何先驗(yàn)信息的條件下，通過(guò)基于一定的互盲或自盲算法協(xié)議發(fā)現(xiàn)其一跳范圍內(nèi)的其他節(jié)點(diǎn)，同時(shí)被其他節(jié)點(diǎn)發(fā)現(xiàn)并建立通信連接的過(guò)程。由于定向天線的窄波束特性，節(jié)點(diǎn)必須在正確的時(shí)間、將正確的波束指向?qū)Ψ?，而且彼此收發(fā)模式相反，才能有效通信，這給鄰居發(fā)現(xiàn)算法帶來(lái)了很大的挑戰(zhàn)。另外，節(jié)點(diǎn)的移動(dòng)、入網(wǎng)和離開(kāi)網(wǎng)絡(luò)等動(dòng)作都會(huì)增加鄰居發(fā)現(xiàn)算法的難度，因此研究定向天線移動(dòng)自組網(wǎng)鄰居發(fā)現(xiàn)算法十分有必要。

文中，首先討論定向天線移動(dòng)自組網(wǎng)鄰居發(fā)現(xiàn)算法的研究現(xiàn)狀[9-18]，然后指出現(xiàn)有基于波束掃描的鄰居發(fā)現(xiàn)算法在波束切換移動(dòng)自組網(wǎng)中存在的問(wèn)題，并提出一種適于波束切換移動(dòng)自組網(wǎng)的鄰居發(fā)現(xiàn)改進(jìn)算法。

1 定向天線鄰居發(fā)現(xiàn)算法

定向天線移動(dòng)自組網(wǎng)鄰居發(fā)現(xiàn)算法可分為隨機(jī)算法和同步算法兩大類，隨機(jī)算法是網(wǎng)絡(luò)節(jié)點(diǎn)沒(méi)有時(shí)鐘同步情況下，每個(gè)節(jié)點(diǎn)收發(fā)波束、發(fā)送和接收狀態(tài)獨(dú)立隨機(jī)選擇；同步算法是在網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘同步的前提下，設(shè)計(jì)了一種機(jī)制讓多個(gè)節(jié)點(diǎn)協(xié)同地進(jìn)行收發(fā)波束、發(fā)送和接收狀態(tài)選擇。研究證明，同步算法的鄰居發(fā)現(xiàn)性能優(yōu)于隨機(jī)算法，因此，基于同步的鄰居算法研究文獻(xiàn)居多，其中Xiong W[17]等人提出的基于掃描的鄰居發(fā)現(xiàn)算法(Scan-Based Algorithm，SBA)性能優(yōu)越，較為經(jīng)典。該算法有如下假設(shè)：

① 每個(gè)節(jié)點(diǎn)配備定向掃描天線，波束寬度為α(0≤α≤2π)；

② 半雙工通信方式，節(jié)點(diǎn)或處于發(fā)送模式，或處于接收模式；

③ 所有節(jié)點(diǎn)均通過(guò)GPS或其他方法精準(zhǔn)同步，分為多個(gè)時(shí)隙，每個(gè)時(shí)隙又分為3個(gè)子時(shí)隙，用以實(shí)現(xiàn)3次握手；

④ 如果一個(gè)節(jié)點(diǎn)同時(shí)從多個(gè)鄰居節(jié)點(diǎn)接收到信號(hào)，則認(rèn)為發(fā)生沖突。

SBA算法的基本思想是：將掃描定義為一系列方向，并且每個(gè)掃描周期應(yīng)覆蓋全部天線方向，且不得重復(fù)。在每次掃描起始，節(jié)點(diǎn)以概率pt隨機(jī)進(jìn)入發(fā)送狀態(tài)，并以概率1-pt進(jìn)入偵聽(tīng)狀態(tài)，節(jié)點(diǎn)保持收發(fā)狀態(tài)不變，直到完成一次掃描；在發(fā)送時(shí)，節(jié)點(diǎn)通過(guò)在每個(gè)指定的方向上發(fā)送廣播包；偵聽(tīng)時(shí)，節(jié)點(diǎn)也在指定方向上接收廣播包，如果接收到廣播包，則回復(fù)確認(rèn)包。掃描時(shí)發(fā)射波束指向與接收波束指向相對(duì)，令θ表示發(fā)送節(jié)點(diǎn)波束指向，則θ′=(θ+π)mod2π表示接收節(jié)點(diǎn)波束指向，SBA算法掃描方案的一個(gè)例子如圖1所示[17]。在時(shí)隙t1，節(jié)點(diǎn)1和節(jié)點(diǎn)2在0°方向上發(fā)送，節(jié)點(diǎn)3和節(jié)點(diǎn)4在180°方向上接收；在時(shí)隙t2，節(jié)點(diǎn)1和節(jié)點(diǎn)2在45°方向上發(fā)送，節(jié)點(diǎn)3和節(jié)點(diǎn)4在135°方向上接收，在時(shí)隙t2，節(jié)點(diǎn)2和節(jié)點(diǎn)3能夠彼此發(fā)現(xiàn)。在一次掃描中完成360°掃描覆蓋。

SBA算法以概率的方式選擇收發(fā)狀態(tài)，能夠在一定程度上緩解一個(gè)定向波束中存在多個(gè)節(jié)點(diǎn)時(shí)，鄰居發(fā)現(xiàn)幀沖突所引起的鄰居發(fā)現(xiàn)失敗和發(fā)現(xiàn)時(shí)間過(guò)長(zhǎng)的問(wèn)題。為了更好地解決該問(wèn)題以縮短鄰居發(fā)現(xiàn)時(shí)間，王昕羽[18]等人在SBA算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種使用定向天線的Ad Hoc網(wǎng)絡(luò)鄰居發(fā)現(xiàn)算法，即引入靜默機(jī)制，減小了同一波束角內(nèi)節(jié)點(diǎn)握手信息碰撞的概率。經(jīng)王昕羽等人改進(jìn)后的鄰居發(fā)現(xiàn)算法可使節(jié)點(diǎn)有效地發(fā)現(xiàn)鄰居，節(jié)點(diǎn)間順利建立一跳網(wǎng)絡(luò)，同時(shí)，可根據(jù)節(jié)點(diǎn)的入網(wǎng)時(shí)間或已掃描次數(shù)，動(dòng)態(tài)調(diào)整該節(jié)點(diǎn)進(jìn)入靜默狀態(tài)的概率，使得鄰居發(fā)現(xiàn)效率提高，節(jié)點(diǎn)入網(wǎng)建立網(wǎng)絡(luò)連接的速度加快[18]。

圖1 SBA算法收發(fā)方向示意圖Fig.1 Overview of SBA

2 SBA算法的改進(jìn)

2.1 現(xiàn)有SBA算法的問(wèn)題

針對(duì)一個(gè)定向波束覆蓋多個(gè)節(jié)點(diǎn)的情況，已有研究學(xué)者進(jìn)行了深入研究[17-18]，但是在實(shí)際工程應(yīng)用中，采用多波束切換實(shí)現(xiàn)全方位掃描是一種常見(jiàn)實(shí)現(xiàn)形式。為了保證多個(gè)定向天線能實(shí)現(xiàn)360°的覆蓋以及波束邊緣時(shí)的通信容量，定向天線波束寬度α(0≤α≤2π)與定向天線數(shù)量B，應(yīng)滿足α·B>2π。當(dāng)鄰居節(jié)點(diǎn)位于兩個(gè)定向天線波束相重合的位置時(shí)，若采用基于掃描的方法會(huì)出現(xiàn)多個(gè)定向天線波束發(fā)現(xiàn)同一個(gè)鄰居節(jié)點(diǎn)的情況，如圖2所示，采用基于隨機(jī)方法的情況如圖3所示。

基于掃描的傳統(tǒng)方法[17-18]在上述情況下會(huì)以波束掃描中最后一次實(shí)現(xiàn)握手的定向天線波束作為該鄰居節(jié)點(diǎn)的通信波束，但是該波束不一定是信道質(zhì)量最好的波束，從而影響通信質(zhì)量。

圖2 SBA方法多個(gè)定向天線波束發(fā)現(xiàn)同一個(gè) 鄰居節(jié)點(diǎn)的情況示意圖Fig.2 Problem of SBA when multiple beams find the same node

圖3 基于隨機(jī)方法多個(gè)定向天線波束發(fā)現(xiàn)同一個(gè) 鄰居節(jié)點(diǎn)的情況示意圖Fig.3 Problem of generic random neighbor discovery algorithm when multiple beams find the same node

2.2 改進(jìn)算法

為了解決基于掃描的傳統(tǒng)方法在多個(gè)定向天線波束發(fā)現(xiàn)同一個(gè)鄰居節(jié)點(diǎn)時(shí)，無(wú)法選取最優(yōu)波束的問(wèn)題，本文提出了一種適于波束切換移動(dòng)自組網(wǎng)的鄰居發(fā)現(xiàn)改進(jìn)算法。改進(jìn)算法的基本思想是在王昕羽等人提出的SBA算法基礎(chǔ)上增加接收信號(hào)質(zhì)量評(píng)估機(jī)制，針對(duì)波束交疊區(qū)域，節(jié)點(diǎn)通過(guò)判定接收特征參數(shù)決定是否繼續(xù)進(jìn)行握手，選擇最佳波束，從而避免當(dāng)節(jié)點(diǎn)處于兩個(gè)波束共同覆蓋區(qū)域時(shí)選擇了差的波束，增強(qiáng)網(wǎng)絡(luò)的穩(wěn)定性，改進(jìn)后的算法與原算法鄰居發(fā)現(xiàn)時(shí)間相同。

與SBA算法[17-18]一樣，本文作出如下假設(shè)：

① 每個(gè)節(jié)點(diǎn)配備一副基于波束切換的多波束天線，實(shí)現(xiàn)360°覆蓋，波束數(shù)目為B，每個(gè)波束的寬度為α(0≤α≤2π)，滿足α·B>2π；

② 每個(gè)節(jié)點(diǎn)配備測(cè)向和授時(shí)設(shè)備，例如GPS/北斗或電子羅盤(pán)等；

③ 半雙工通信方式，節(jié)點(diǎn)或處于發(fā)送模式，或處于接收模式；

④ 如果一個(gè)節(jié)點(diǎn)同時(shí)從多個(gè)鄰居節(jié)點(diǎn)接收信號(hào)，則會(huì)發(fā)生沖突。

本文提出的改進(jìn)算法時(shí)隙設(shè)計(jì)如下：整個(gè)時(shí)隙周期包含鄰居發(fā)現(xiàn)階段和數(shù)據(jù)階段，其中鄰居發(fā)現(xiàn)階段包括3次掃描過(guò)程，每次掃描由B個(gè)時(shí)隙構(gòu)成，完成對(duì)360°范圍內(nèi)的掃描，每個(gè)時(shí)隙進(jìn)一步分為3個(gè)子時(shí)隙。時(shí)隙結(jié)構(gòu)如圖4所示。

鄰居發(fā)現(xiàn)階段掃描方式設(shè)計(jì)如下：在一次掃描起始之前，每個(gè)節(jié)點(diǎn)以pt的概率作為主動(dòng)掃描節(jié)點(diǎn)進(jìn)行主動(dòng)發(fā)送，以概率1-pt作為被動(dòng)收聽(tīng)節(jié)點(diǎn)對(duì)信道進(jìn)行偵聽(tīng)接收。選擇主動(dòng)掃描的節(jié)點(diǎn)將在后續(xù)B個(gè)時(shí)隙，于每一個(gè)時(shí)隙的第一子時(shí)隙發(fā)送鄰居發(fā)現(xiàn)幀1(Neighbor Discovery 1,ND1)，其中ND1中包含本機(jī)節(jié)點(diǎn)號(hào)；選擇被動(dòng)收聽(tīng)的節(jié)點(diǎn)將在后續(xù)B個(gè)時(shí)隙，于每一個(gè)時(shí)隙的第一子時(shí)隙收聽(tīng)信道。以B=16時(shí)為例，圖5為鄰居發(fā)現(xiàn)階段主動(dòng)掃描節(jié)點(diǎn)和被動(dòng)掃描節(jié)點(diǎn)的掃描流程詳細(xì)說(shuō)明。

圖4 時(shí)隙結(jié)構(gòu)Fig.4 Time slots

圖5 動(dòng)態(tài)鄰居發(fā)現(xiàn)示意圖Fig.5 Overview of the proposed modified SBA

對(duì)16個(gè)定向天線進(jìn)行編號(hào)，與電子羅盤(pán)參考基線方向?qū)R的波束定為1波束，按照逆時(shí)針?lè)较驅(qū)?6個(gè)定向天線依次編號(hào)；根據(jù)正北方向與電子羅盤(pán)的參考基線方向的順時(shí)針夾角計(jì)算主動(dòng)掃描節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙發(fā)送ND1幀的定向天線編號(hào)，并通過(guò)此定向天線發(fā)送ND1幀；計(jì)算主動(dòng)掃描節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙發(fā)送ND1幀的定向天線編號(hào)為：

式中，S為主動(dòng)掃描節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙發(fā)送ND1幀的定向天線編號(hào)，θ為電子羅盤(pán)參考基線方向與正北方向的順時(shí)針夾角，i代表定向天線編號(hào)。

具體發(fā)現(xiàn)過(guò)程如下：

步驟1：根據(jù)發(fā)送ND1幀的定向天線編號(hào)計(jì)算被動(dòng)收聽(tīng)節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙偵聽(tīng)ND1幀的定向天線編號(hào)，并通過(guò)此定向天線偵聽(tīng)ND1幀，如果被動(dòng)收聽(tīng)節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙偵聽(tīng)到了ND1幀，則計(jì)算ND1幀的接收功率并解析ND1幀中的節(jié)點(diǎn)號(hào)，執(zhí)行步驟2；如果被動(dòng)收聽(tīng)節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙未偵聽(tīng)到ND1幀，則轉(zhuǎn)入步驟5；被動(dòng)收聽(tīng)節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙偵聽(tīng)ND1幀的定向天線編號(hào)為K=(S+8)mod16，其中，K為被動(dòng)收聽(tīng)節(jié)點(diǎn)在當(dāng)前時(shí)隙的第一子時(shí)隙偵聽(tīng)ND1幀的定向天線編號(hào)，AmodB代表A除以B的余數(shù)。

步驟2：將接信噪比(SNR)和當(dāng)前TDMA周期內(nèi)該節(jié)點(diǎn)的累計(jì)接收SNR最大值進(jìn)行比較，如果接收SNR不小于該節(jié)點(diǎn)的累計(jì)接收SNR最大值，則更新該節(jié)點(diǎn)的累計(jì)接收SNR最大值，并在當(dāng)前時(shí)隙的第二子時(shí)隙回復(fù)ND2幀，執(zhí)行步驟3；如果接收功率小于該節(jié)點(diǎn)的累計(jì)接收SNR最大值，則轉(zhuǎn)入步驟5；其中，該節(jié)點(diǎn)為當(dāng)前時(shí)隙接收到的ND1幀中的節(jié)點(diǎn)號(hào)所對(duì)應(yīng)的節(jié)點(diǎn)，ND2幀中包含自身節(jié)點(diǎn)號(hào)，累計(jì)接收SNR最大值的初始值設(shè)置為零。

步驟3：如果主動(dòng)掃描節(jié)點(diǎn)在當(dāng)前時(shí)隙的第二子時(shí)隙收到ND2幀，則在當(dāng)前時(shí)隙的第三子時(shí)隙回復(fù)ND3幀，執(zhí)行步驟4；如果主動(dòng)掃描節(jié)點(diǎn)在當(dāng)前時(shí)隙的第二子時(shí)隙未收到ND2幀，則轉(zhuǎn)入步驟5。

步驟4：被動(dòng)收聽(tīng)節(jié)點(diǎn)在當(dāng)前時(shí)隙的第三子時(shí)隙接收并讀取ND3幀。

步驟5：判斷當(dāng)前時(shí)隙的時(shí)隙號(hào)是否為16，如果是，則累計(jì)接收功率最大值所對(duì)應(yīng)的波束即為所選波束，結(jié)束本流程；如果不是，則等待進(jìn)入下一時(shí)隙，轉(zhuǎn)入步驟4。

現(xiàn)以具體實(shí)例對(duì)改進(jìn)算法進(jìn)行說(shuō)明，如圖6所示，節(jié)點(diǎn)1為主動(dòng)掃描節(jié)點(diǎn)，節(jié)點(diǎn)2為被動(dòng)偵聽(tīng)節(jié)點(diǎn)。在時(shí)隙1，節(jié)點(diǎn)2收到節(jié)點(diǎn)1的ND1幀，接收信噪比為snr1，記錄當(dāng)前節(jié)點(diǎn)1的累計(jì)最大接收信噪比為Max1=snr1，并在接下來(lái)的時(shí)隙ND2和時(shí)隙ND3完成與節(jié)點(diǎn)1的3次握手；在時(shí)隙2，節(jié)點(diǎn)2收到節(jié)點(diǎn)1的ND1幀，接收信噪比為snr2，其中snr2Max1，并在接下來(lái)的時(shí)隙ND2和時(shí)隙ND3完成與節(jié)點(diǎn)1的3次握手。

圖6 一種適于波束切換移動(dòng)自組網(wǎng)的鄰居發(fā)現(xiàn)改進(jìn)算法舉例Fig.6 Example of the proposed algorithm

3 改進(jìn)算法性能仿真及分析

為了驗(yàn)證本文提出的適于波束切換移動(dòng)自組網(wǎng)的鄰居發(fā)現(xiàn)改進(jìn)算法的有效性，用python對(duì)該算法進(jìn)行了仿真，仿真中心頻率為4 GHz，發(fā)射機(jī)輸出功率40 dBm，仿真中用于鄰居發(fā)現(xiàn)的信令幀接收靈敏度為-105 dBm，仿真場(chǎng)景采用20 km×20 km的正方形區(qū)域，隨機(jī)在20 km×20 km的區(qū)域產(chǎn)生16個(gè)節(jié)點(diǎn)，隨機(jī)產(chǎn)生每個(gè)節(jié)點(diǎn)的基線方向，仿真節(jié)點(diǎn)分布如圖7所示。

圖7 仿真節(jié)點(diǎn)分布圖Fig.7 Scatter of nodes in 20 km×20 km square

天線采用4陣元、6陣元和8陣元平面天線，天線方向圖如圖8所示，可以看出4陣元天線3 dB波束寬度約為35°，6陣元天線3 dB波束寬度約為23°，8陣元天線3 dB波束寬度為17°。下面分別在4陣元、6陣元和8陣元平面天線，用α代表交疊波束和波束寬度比值，在α為1/4和1/8情況下，對(duì)本文提出的鄰居發(fā)現(xiàn)改進(jìn)算法的累計(jì)平均接收電平與傳統(tǒng)SBA[18]算法進(jìn)行比較。

圖8 單波束天線方向圖Fig.8 Radiation pattern of single antenna beam

在上述仿真場(chǎng)景和參數(shù)設(shè)置情況下，將本文提出的鄰居發(fā)現(xiàn)改進(jìn)算法的接收電平累計(jì)概率分布與傳統(tǒng)SBA[18]算法進(jìn)行比較，如圖9、圖10和圖11所示。其中橫坐標(biāo)為接收信號(hào)強(qiáng)度，縱坐標(biāo)為累計(jì)分布函數(shù)(Cumulative Distribution Function,CDF)。

圖9 4陣元累計(jì)平均接收電平對(duì)比Fig.9 Cumulative reception level equipped with 4-element antenna

圖10 6陣元累計(jì)平均接收電平對(duì)比Fig.10 Cumulative reception level equipped with 6-element antenna

圖11 8陣元累計(jì)平均接收電平對(duì)比Fig.11 Cumulative reception level equipped with 8-element antenna

由圖 9、圖 10和圖 11可以看出，本文提出的鄰居發(fā)現(xiàn)改進(jìn)算法的累計(jì)平均接收電平相較于傳統(tǒng)SBA算法提高約15 dB，可支撐更高的通信容量、或增強(qiáng)網(wǎng)絡(luò)的穩(wěn)定性；隨著天線陣元數(shù)量增多，天線增益變大，傳統(tǒng)SBA算法選擇的非最優(yōu)波束的概率在逐漸增加，例如，在交疊波束占波束寬度1/8時(shí)，在4陣元、6陣元和8陣元時(shí)分別為60%，80%，90%，而本文提出的改進(jìn)算法始終能選擇最優(yōu)波束，具有更高的網(wǎng)絡(luò)容量，且隨著天線陣元數(shù)量增多，網(wǎng)絡(luò)吞吐量的提升越大。

4 結(jié)束語(yǔ)

本文針對(duì)基于多波束切換的移動(dòng)自組網(wǎng)在波束交疊的情況下，鄰居發(fā)現(xiàn)過(guò)程無(wú)法選擇最優(yōu)通信波束的問(wèn)題，提出了一種適于波束切換移動(dòng)自組網(wǎng)的鄰居發(fā)現(xiàn)改進(jìn)算法，該算法在基于掃描的鄰居發(fā)現(xiàn)算法的基礎(chǔ)上通過(guò)接收信號(hào)質(zhì)量評(píng)估選擇最佳波束。仿真結(jié)果表明，在波束交疊情況下，采用本文提出的改進(jìn)算法，系統(tǒng)能夠選擇最優(yōu)通信波束，累計(jì)平均接收電平優(yōu)于傳統(tǒng)的基于掃描的鄰居發(fā)現(xiàn)算法，并且單波束寬度越窄、波束交疊占波束寬度的比例越大，網(wǎng)絡(luò)吞吐量提升越明顯。