梁仕杰,趙海濤,張 姣,陳海濤,魏急波,王俊芳

(1. 中國電子科技集團公司 第五十四研究所, 河北 石家莊 050081; 2. 國防科技大學(xué) 電子科學(xué)學(xué)院, 湖南 長沙 410073)

隨著5G移動通信、物聯(lián)網(wǎng)與人工智能等技術(shù)的快速發(fā)展,增強/虛擬現(xiàn)實、自動駕駛、自然語言等新型資源密集型應(yīng)用迅速占領(lǐng)移動互聯(lián)網(wǎng)市場,這些應(yīng)用往往需要進行高速率的連續(xù)采樣與傳輸,對現(xiàn)有的通信資源提出了極大的挑戰(zhàn)。毫米波具有大量可用頻段,可作用于帶寬密集型應(yīng)用[1-3]。因此,近年來越來越多的研究人員將研究方向轉(zhuǎn)向毫米波通信的研究。

毫米波通信的研究潛力巨大,但廣泛的應(yīng)用仍面臨很多的挑戰(zhàn)。毫米波通信的衰減要比S波段、C波段等低頻段嚴重[4]。因此,一般要采用定向天線(相控陣天線)來對抗信號的高衰減特性,從而實現(xiàn)高速率的傳輸[5-6]。

在定向無線網(wǎng)絡(luò)中,快速高效的鄰居發(fā)現(xiàn)是個重要問題。目前,定向毫米波通信主要采用全向天線輔助進行鄰居發(fā)現(xiàn)[7-9]。然而,全向天線的增益小于定向天線的增益,導(dǎo)致全向和定向的通信距離不同,因此采用全向天線輔助鄰居發(fā)現(xiàn)的方法會導(dǎo)致某些鄰居無法被發(fā)現(xiàn)。而且,基于全向天線輔助的方法還要求通信節(jié)點具備額外的全向射頻模塊。如何單純利用節(jié)點已經(jīng)具備的定向通信能力完成鄰居發(fā)現(xiàn)就成為一個亟待解決的問題。

采用純定向的鄰居發(fā)現(xiàn)協(xié)議,可以分為隨機類和確定類。隨機類鄰居發(fā)現(xiàn)算法[10-12]隨機選擇一個定向天線的波束指向方向,具有無記憶、平穩(wěn)和健壯性的優(yōu)勢,可以用于沒有任何先驗信息和同步信息的環(huán)境中。但是,該算法得到的系統(tǒng)性能沒有上界,導(dǎo)致其可能會需要非常長的鄰居發(fā)現(xiàn)時間。確定類鄰居發(fā)現(xiàn)協(xié)議[13-18]按照事先預(yù)定好的序列切換天線的方向或波束搜索方式實現(xiàn)波束交匯和鄰居發(fā)現(xiàn),有鄰居發(fā)現(xiàn)時間的上界。

根據(jù)收發(fā)端時間的同步性,定向鄰居發(fā)現(xiàn)協(xié)議還分為同步類鄰居發(fā)現(xiàn)協(xié)議和異步類鄰居發(fā)現(xiàn)協(xié)議。同步類鄰居發(fā)現(xiàn)協(xié)議[19-20]需要收發(fā)雙方的同步信息。異步類鄰居發(fā)現(xiàn)協(xié)議[21-22]不需要雙方的同步信息,但是發(fā)現(xiàn)時間會變長。

在定向的毫米波網(wǎng)絡(luò)中,鄰居發(fā)現(xiàn)階段各個節(jié)點可能沒有任何鄰居交互信息。因此一個很重要的問題是如何在沒有公共控制信道和任何先驗信息的情況下發(fā)現(xiàn)鄰居。定向通信的鄰居發(fā)現(xiàn)需要收發(fā)雙方的波束交匯,因此在沒有公共控制信道和任何先驗信息的條件下如何引導(dǎo)波束轉(zhuǎn)向,實現(xiàn)收發(fā)雙方的波束交匯是一個重要的課題。定向波束的鄰居發(fā)現(xiàn)本質(zhì)上是一個交匯(rendezvous)問題[23],當(dāng)兩節(jié)點的定向波束均指向?qū)Ψ讲⒔⑼ㄐ沛溌穼崿F(xiàn)信號的發(fā)送與接收時,才可以實現(xiàn)鄰居發(fā)現(xiàn)。在沒有交互信息的情況下實現(xiàn)定向通信的鄰居發(fā)現(xiàn)是一個盲交匯(blind rendezvous)問題[17-18, 23]。文獻[17]提出了無協(xié)調(diào)定向鄰居發(fā)現(xiàn)(oblivious directional neighbor discovery, ODND)協(xié)議,該協(xié)議能夠在沒有任何先驗信息的條件下實現(xiàn)波束盲交匯并完成鄰居發(fā)現(xiàn),但問題是鄰居發(fā)現(xiàn)時間較長。為了縮短ODND協(xié)議中的鄰居發(fā)現(xiàn)時間,文獻[18]進一步提出了基于連續(xù)掃描定向天線模型的波束盲交匯算法,并根據(jù)該算法設(shè)計出基于搜索的定向鄰居發(fā)現(xiàn)(hunting-based directional neighbor discovery, HDND)協(xié)議實現(xiàn)鄰居發(fā)現(xiàn)。然而,HDND協(xié)議的連續(xù)掃描定向天線模型較為理想,在工程中難以實現(xiàn)[24]。

本文提出了一種異步的確定性的基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議。該協(xié)議不需要任何交互信息,并且在首次基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議后執(zhí)行基于位置預(yù)測的鄰居發(fā)現(xiàn)協(xié)議來提高后續(xù)鄰居發(fā)現(xiàn)速度,大量仿真實驗驗證了本文所提方法的有效性。

1 定向鄰居發(fā)現(xiàn)盲交匯問題描述

鄰居發(fā)現(xiàn)是實現(xiàn)網(wǎng)絡(luò)媒體訪問控制、拓撲控制等功能的關(guān)鍵技術(shù)之一。定向通信的鄰居發(fā)現(xiàn)和全向通信的鄰居發(fā)現(xiàn)不同,定向通信只能覆蓋一個方位角,因此其鄰居發(fā)現(xiàn)的復(fù)雜性遠大于全向天線的鄰居發(fā)現(xiàn)。在實際環(huán)境中,節(jié)點之間可能是異步的,鄰居發(fā)現(xiàn)協(xié)議應(yīng)該在沒有公共控制信道和先驗信息的情況下實現(xiàn)鄰居發(fā)現(xiàn)。

定向通信鄰居盲交匯問題定義為:在沒有任何公共控制信道和先驗信息,且沒有任何時鐘同步的情況下,實現(xiàn)有界的定向通信鄰居發(fā)現(xiàn)。

1.1 系統(tǒng)模型

在一個二維毫米波定向通信網(wǎng)絡(luò)中,每個節(jié)點配備定向天線,并且只在一個頻段運行,每個天線可以切換方向到需要的位置。每個節(jié)點有N個(N為正整數(shù))波束,忽略波束的切換時間,經(jīng)過N次切換可以掃描所有的方向。每個波束的夾角為2π/N,當(dāng)波束夾角為2π時,其退化成全向天線。

定向通信首先要保證發(fā)射端和接收端的波束交匯。為了便于說明,下面通過一個例子來描述定向通信波束交匯的過程,如圖1所示。節(jié)點A和節(jié)點B均采用定向通信,它們均有6個波束,編號順序按照逆時針編號,記為u={1,2,3,4,5,6},每個波束的夾角為π/3。節(jié)點A和節(jié)點B在彼此的定向-定向的通信范圍內(nèi),彼此進行鄰居發(fā)現(xiàn)需要雙方波束同時指向?qū)Ψ?波束交匯)。

圖1 天線波束模型Fig.1 Sectors of antenna model

假設(shè)節(jié)點A和節(jié)點B均按照逆時針方向旋轉(zhuǎn)且時間同步,當(dāng)前節(jié)點A指向波束4的方向記作PA=4,節(jié)點B指向波束3方向記作PB=3。假設(shè)節(jié)點A指向波束1,節(jié)點B指向波束4才能實現(xiàn)鄰居發(fā)現(xiàn),記作(dA-B=1,dB-A=4)。若節(jié)點A和節(jié)點B按照逆時針順序切換下一個波束,根據(jù)PA、N可以得到節(jié)點A的掃描序列uA。根據(jù)PB、N可以得到節(jié)點B的掃描序列uB。

uA={4,5,6,1,2,3,4,5,6,1,2,3,…}

(1)

uB={3,4,5,6,1,2,3,4,5,6,1,2,…}

(2)

根據(jù)掃描序列uA和uB按照每個時隙切換一次,如圖2所示。

圖2 節(jié)點A和節(jié)點B波束掃描序列圖Fig.2 Beam scan sequences of node A and node B

通過圖2中的uA和uB可以得知:在這種情況下兩個節(jié)點只能搜索出{(dA-B=1,dB-A=6)(dA-B=2,dB-A=1)(dA-B=3,dB-A=2)(dA-B=4,dB-A=3)(dA-B=5,dB-A=4)(dA-B=6,dB-A=5)}六組解,無法搜索到(dA-B=1,dB-A=4)這個解;無法實現(xiàn)節(jié)點A指向波束1同時節(jié)點B指向波束4,無法實現(xiàn)鄰居發(fā)現(xiàn)。兩個節(jié)點波束個數(shù)均為6時,共有36種交匯情況,因而無法搜索到所有解。

1.2 問題模型

在上述例子中,仍然存在一些無法完成波束交匯的情況。因此定向天線鄰居發(fā)現(xiàn)盲交匯算法需要滿足以下要求:

保證交匯:在有限的時間范圍內(nèi),保證兩個節(jié)點實現(xiàn)波束交匯。

全交匯:兩個用戶初始指向任何方向、交匯方向為任意方向,都可以保證波束交匯。

異步交匯:收發(fā)雙方不需要時鐘同步,也可完成盲交匯。

交匯時間:波束交匯必須至少保持一個時隙T(假設(shè)收發(fā)節(jié)點完成一次鄰居發(fā)現(xiàn)時間為T)才能實現(xiàn)鄰居發(fā)現(xiàn)。

在毫米波網(wǎng)絡(luò)中,節(jié)點可能是不斷移動的,因此兩個節(jié)點交匯的方向dA-B和dB-A可能是任意組合,即?dA-B∈[1,N],dB-A∈[1,N],其初始波束的位置也是隨機的,即?PA∈[1,N],PB[1,N],ua表示節(jié)點A根據(jù)PA和N生成的序列,ub是節(jié)點B根據(jù)PB和N生成的序列,因此定向天線的盲交匯數(shù)學(xué)優(yōu)化問題為:

minTbr

s.t.?dA-B∈[1,N],dB-A∈[1,N], ?PA∈[1,N],PB∈[1,N]

?t≤Tbr,ua(t)=dA-B,ub(t)=dB-A

(3)

式(3)表示的意思是:通過設(shè)計節(jié)點A的掃描序列ua和節(jié)點B的掃描序列ub最小化全交匯時間,保證節(jié)點A和節(jié)點B當(dāng)前任意波束指向的組合(PA,PB)∈[1,N]×[1,N],節(jié)點A和節(jié)點B波束交匯的組合(dA-B,dB-A)∈[1,N]×[1,N],可以使節(jié)點A和節(jié)點B在t≤Tbr時刻分別指向dA-B和dB-A從而實現(xiàn)節(jié)點A和節(jié)點B的波束交匯。

2 基于位置預(yù)測的鄰居發(fā)現(xiàn)算法

2.1 定向波束盲交匯算法

受圓形鐘表的時分速率不同但終會相交這一現(xiàn)象啟發(fā),文獻[25]提出了一種信道跳變的盲交匯算法,解決了無先驗頻譜信息條件下的多信道接入與通信問題。基于該思想,本文提出了一種定向天線波束盲交匯算法,該算法的主要思想是收發(fā)兩端無公共波束信息,但在周期性定向旋轉(zhuǎn)過程中仍然會實現(xiàn)波束交匯。但是,波束盲交匯算法和信道盲交匯算法仍然存在不同之處。在信道盲交匯過程中兩個節(jié)點可用信道相同,信道個數(shù)為P。信道盲交匯滿足兩個節(jié)點在同一時刻處于共同可用的任意一個信道中,也就是說在所有信道均可用的情況下共有P種解,即{(1,1),(2,2),(3,3),…,(P-1,P-1),(P,P)}。波束盲交匯指的是兩個節(jié)點的波束必須指向?qū)Ψ?在該時刻只有(dA-B,dB-A)一個解。

兩個節(jié)點按照逆時針的方向切換波束來掃描所有方向,設(shè)發(fā)送端在每個方向停留的時間為MTT,接收端在每個方向停留的時間為MRT。MT和MR為整數(shù)且互質(zhì),即gcd(MT,MR)=1。

定理1兩個用戶在進行波束交互時,兩個節(jié)點完成一個周期搜索的時間為MTMRNT。在一個周期內(nèi),兩個節(jié)點可以搜索完一次所有波束交匯的可能性,并在下一次搜索同時回到搜索初始波束位置。

證明:發(fā)射端經(jīng)過MTNT時間完成一次所有方向的掃描。接收端經(jīng)過MRNT完成所有方向的掃描。接收端和發(fā)射端掃描完所有方向,并到達共同掃描的初始位置時,發(fā)射端和接收端組成的系統(tǒng)實現(xiàn)了一個周期的掃描。那么該系統(tǒng)的一個周期為MTNT和MRNT的最小公倍數(shù),即MTMRNT。

□

定理2在同步狀態(tài)下,只有在(MT=1,MR=N)或(MT=N,MR=1)條件下才能在最短的時間內(nèi)實現(xiàn)全交匯,最短全交匯時間為N2T,最小盲交匯時間的上界為N2T。

□

在1.1節(jié)列舉的波束交匯場景中,若令(MT=2,MR=3),其波束掃描序列如圖3所示,在這種情況下無法搜索到(dA-B=1,dB-A=4)。若令(MT=1,MR=6),其波束掃描示意圖如圖4所示,在時隙9就可以搜索到(dA-B=1,dB-A=4)的情況從而實現(xiàn)波束交匯。在圖4中, 經(jīng)過36個時隙的時間,(MT=1,MR=6)條件下可以遍歷所有波束交匯,實現(xiàn)全交匯。該場景收發(fā)雙方的波束個數(shù)為6,至少經(jīng)過36T的時間才能實現(xiàn)全交匯,(MT=1,MR=6)時可以實現(xiàn)全交匯最短全交匯時間。

圖3 N=6,(MT=2,MR=3)時節(jié)點A和 節(jié)點B波束掃描序列Fig.3 Beam scan sequence of node A and node B when N=6,(MT=2,MR=3)

圖4 N=6,(MT=1,MR=6)時節(jié)點A和 節(jié)點B波束掃描序列Fig.4 Beam scan sequence of node A and node B when N=6,(MT=1,MR=6)

定理3在異步狀態(tài)下,只有(MT=1,MR=N+1)或者(MT=N+1,MR=1)條件下才能在最短的時間內(nèi)實現(xiàn)全交匯,最短全交匯時間為N(N+1)T,最小盲交匯時間的上界為N(N+1)T。

證明: 在同步狀態(tài)下,在最小最大交匯時間內(nèi)無法在異步狀態(tài)下實現(xiàn)全交匯,這是因為一定會存在若干個情況由于持續(xù)時間小于T從而導(dǎo)致無法實現(xiàn)波束盲交匯。由于一個搜索周期為N2T,在N2T時間內(nèi)有些情況搜索不到將會導(dǎo)致這些情況永遠無法搜索到。在同步狀態(tài)下(dA-B=1,dB-A=4)、(dA-B=3,dB-A=6)均可以搜索到并保持一個時隙,如圖5所示。在異步狀態(tài)下,(dA-B=1,dB-A=4)持續(xù)時間大于一個時隙,(dA-B=3,dB-A=6)持續(xù)時間小于一個時隙,無法實現(xiàn)異步狀態(tài)下的全交匯,如圖6所示。

圖5 同步狀態(tài)且N=6時依據(jù)定理2 設(shè)計的波束掃描序列Fig.5 Beam scan sequence according to theorem 2 when the system is synchronous and N=6

□

令(MT=1,MR=N+1)或(MT=N+1,MR=1),節(jié)點A搜索完畢所有方向后,節(jié)點B在節(jié)點A的每個方向持續(xù)時間均大于T。因此,盲交匯消耗時間為N(N+1)T。在定理2中,在(MT≠1,MR≠N)或者(MT≠N,MR≠1)條件下,最短全交匯時間為min(MT,MR)·NT+N2T,在異步狀態(tài)下最短全交匯時間至少為min(MT,MR)·NT+N2T。由于min(MT,MR)·NT+N2T大于N(N+1)T,因此在異步狀態(tài)下,(MT=1,MR=N+1)或(MT=N+1,MR=1)條件下才能在最短的時間內(nèi)實現(xiàn)全交匯,最短全交匯時間為N(N+1)T。在異步狀態(tài)下,(MT=1,MR=N+1)或(MT=N+1,MR=1)條件下可以實現(xiàn)最小盲交匯時間的上界,最小盲交匯時間的上界為N(N+1)T。

在圖7中,依據(jù)定理3設(shè)計的波束掃描序列可以搜索到(dA-B=3,dB-A=6)和(dA-B=1,dB-A=4)并保持一個時隙,改變了圖6中某些異步狀態(tài)搜索不到的情況。

圖6 異步狀態(tài)且N=6時依據(jù)定理2 設(shè)計的波束掃描序列Fig.6 Beam scan sequence according to theorem 2 when the system is asynchronous and N=6

圖7 異步狀態(tài)且N=6時依據(jù)定理3 設(shè)計的波束掃描序列Fig.7 Beam scan sequence according to theorem 3 when the system is asynchronous and N=6

在兩個節(jié)點進行波束交匯時,同步狀態(tài)下盲交匯的最短時間為T,盲交匯的最長時間為N2T。因此,兩個節(jié)點的同步狀態(tài)下的盲交匯平均時間如式(4)所示,其中Z表示整數(shù),i和j表示進行i次全方向搜索并在下一個全方向搜索j次可以實現(xiàn)波束交匯。

(4)

在異步狀態(tài)下兩個節(jié)點在進行波束交匯時,盲交匯最小時間為2T,盲交匯最大時間為N(N+1)T,因此在異步狀態(tài)下的平均盲交匯時間如式(5)所示。

(5)

2.2 基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議

在利用2.1節(jié)實現(xiàn)波束交匯后,需要兩個節(jié)點執(zhí)行鄰居發(fā)現(xiàn)協(xié)議實現(xiàn)鄰居發(fā)現(xiàn)。

兩個用戶發(fā)射一個波束對準請求發(fā)送(beam alignment request to send, BARTS)的時間定義為TT-BARTS,接收一個波束對準允許發(fā)送(beam alignment clear to send, BACTS)的時間為TT-BACTS,將時間T定義為:

T≥2(TT-BARTS+TT-BACTS)

(6)

BARTS和BACTS數(shù)據(jù)包的數(shù)據(jù)結(jié)構(gòu)如圖8所示,其中Type表示幀類型,0表示控制幀,1表示數(shù)據(jù)幀;Subtype表示子類型,在這里表示BARTS數(shù)據(jù)包或者BACTS數(shù)據(jù)包;ID表示發(fā)射數(shù)據(jù)包節(jié)點的ID號;Location數(shù)據(jù)表示發(fā)射數(shù)據(jù)包節(jié)點從GPS導(dǎo)航中獲取的位置信息;Time 表示發(fā)射數(shù)據(jù)包節(jié)點的時鐘同步信息;Speed表示發(fā)射節(jié)點的速度信息;Direction表示當(dāng)前該節(jié)點指向的方向。

圖8 BARTS和BACTS結(jié)構(gòu)Fig.8 Structure of BARTS and BACTS

2.3 基于位置預(yù)測的鄰居發(fā)現(xiàn)協(xié)議

通過2.1節(jié)和2.2節(jié)的協(xié)議實現(xiàn)全網(wǎng)鄰居發(fā)現(xiàn)后,每個節(jié)點可以發(fā)現(xiàn)本節(jié)點的鄰居和本節(jié)點鄰居的ID號、位置、速度、方向和時鐘同步信息。

通過這些信息,可以加快后續(xù)節(jié)點的鄰居發(fā)現(xiàn),其中第i個用戶的位置為(xi,yi),速度為vi,其運動方向與x軸正向的夾角為θi,節(jié)點發(fā)射上述信息的時間為ti。在tj時刻,節(jié)點j準備向節(jié)點i發(fā)射信息,此時節(jié)點i的位置表示為:

(7)

任意一個節(jié)點A在準備和其他用戶B進行通信時,采用式(7)對其位置進行預(yù)測,直接對節(jié)點B的方向發(fā)射請求發(fā)送(request to send, RTS)數(shù)據(jù)包。RTS的數(shù)據(jù)包結(jié)構(gòu)如圖9所示。Type,Location,Time,Speed和Direction表示的含義與BARTS數(shù)據(jù)包也相同。Subtype在這里表示RTS數(shù)據(jù)包。Receive ID表示節(jié)點B的ID,Transmitter ID表示用戶A的ID。Duration表示后續(xù)數(shù)據(jù)包需要的時間。

圖9 RTS結(jié)構(gòu)Fig.9 Structure of RTS

此時,節(jié)點A為發(fā)射狀態(tài),節(jié)點B為接收狀態(tài),雙方就可以實現(xiàn)本次鄰居發(fā)現(xiàn)。節(jié)點B最多進行N次波束切換就可以收到用戶A的RTS數(shù)據(jù)包。在用戶B接收到數(shù)據(jù)包后,可以獲得用戶A的位置速度方向時間信息。用戶B采用式(7)計算用戶A的位置,波束交匯用戶A并發(fā)射允許發(fā)送(clear to send, CTS)數(shù)據(jù)包給用戶A。CTS數(shù)據(jù)包結(jié)構(gòu)如圖10所示。

圖10 CTS結(jié)構(gòu)Fig.10 Structure of CTS

完成RTS/CTS鄰居發(fā)現(xiàn)后,用戶A進行數(shù)據(jù)傳輸。

基于預(yù)測的鄰居發(fā)現(xiàn)協(xié)議的RTS和CTS結(jié)構(gòu)比BARTS和BACTS結(jié)構(gòu)長,增大了對信道的占用時間,但是預(yù)測算法減少了波束交匯時間,對信道的占用時間減少?；谖恢妙A(yù)測算法的鄰居發(fā)現(xiàn)協(xié)議與基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的信道占用時間之比如式(8)所示,式中:TRTS,TCTS,TBARTS,TBACTS分別表示RTS,CTS,BARTS,BACTS時間;TP-BA表示基于預(yù)測算法鄰居發(fā)現(xiàn)協(xié)議的平均鄰居發(fā)現(xiàn)時間,如式(9)所示,其中i表示搜索次數(shù)。

(8)

(9)

2.4 旁瓣效應(yīng)下的鄰居發(fā)現(xiàn)協(xié)議性能評估

前面所提出的盲交匯算法是基于理想的定向天線模型提出的。為了研究所提出的算法在更一般的場景中的適應(yīng)性,對旁瓣效應(yīng)下的鄰居發(fā)現(xiàn)協(xié)議進行性能評估。

假設(shè)每個旁瓣的增益相同,主瓣和旁瓣的增益比為M。主瓣的增益為G(θ),因此天線增益模型[18]如式(10)所示,φ表示通信指向方向,θmain表示主瓣方向。

(10)

理想的單波束定向天線和考慮旁瓣的單波束定向天線的區(qū)別在于:在旁瓣可以覆蓋的通信距離范圍內(nèi),旁瓣可以發(fā)送和接收控制信息。因此可以提高鄰居發(fā)現(xiàn)的效率,同時也會增大碰撞的可能。在這里不考慮碰撞,僅分析旁瓣增加鄰居發(fā)現(xiàn)的效率。

旁瓣對于鄰居發(fā)現(xiàn)的影響:

1)主瓣-旁瓣通信實現(xiàn)鄰居發(fā)現(xiàn);

2)旁瓣-旁瓣通信實現(xiàn)鄰居發(fā)現(xiàn)。

在情況1的條件下,主瓣-主瓣同樣也可以實現(xiàn)鄰居發(fā)現(xiàn),在情況2的條件下,主瓣-主瓣、主瓣-旁瓣也可以實現(xiàn)鄰居發(fā)現(xiàn)。

2.4.1 主瓣-旁瓣通信實現(xiàn)鄰居發(fā)現(xiàn)

當(dāng)兩個節(jié)點的主瓣-旁瓣之間的通信距離可以滿足兩個節(jié)點的通信距離需求時,可以提高鄰居發(fā)現(xiàn)的速度。

在同步狀態(tài)下,最大盲交匯時間為NT,因此其平均盲交匯時間如式(11)所示,i表示搜索次數(shù)。

在異步狀態(tài)下,最大盲交匯時間為(N+1)T,因此平均盲交匯時間為:

2.4.2 旁瓣-旁瓣通信實現(xiàn)鄰居發(fā)現(xiàn)

當(dāng)兩個節(jié)點的旁瓣-旁瓣之間的通信距離可以滿足兩個節(jié)點的通信距離需求時,可以提高鄰居發(fā)現(xiàn)的速度。

旁瓣-旁瓣鄰居情況下,鄰居發(fā)現(xiàn)可以看作是全向天線的鄰居發(fā)現(xiàn),其同步異步狀態(tài)均相同。因此其最長的盲交匯時間為T。

3 仿真分析

3.1 盲交匯算法計算復(fù)雜度性能對比

本節(jié)對本文所提盲交匯算法和文獻[17]提出的ODND波束盲交匯算法的復(fù)雜度進行對比。這里將一個取余運算作為算法復(fù)雜度計算的單位。

在文獻[17]提出的ODND算法中,每個時隙要進行一次取余運算來計算其天線的指向方向,因此在最壞的情況下,其要進行Lmax{paqb,pbqa}次取余運算。本文提出的盲交匯算法不需要進行取余運算,只要按照設(shè)計的序列順序進行下次的天線選擇即可。位置預(yù)測算法會增加算法運行時間,因此通過仿真分析盲交匯算法、位置預(yù)測算法和ODND算法計算復(fù)雜度。

采用MATLAB對三個算法進行算法復(fù)雜度仿真,設(shè)置仿真次數(shù)為10 000,統(tǒng)計算法的累計運行時間,結(jié)果如圖11所示。

圖11 不同算法復(fù)雜度對比Fig.11 Complexity comparison of different algorithms

圖11可以看出,本文提出的盲交匯算法仿真時間遠小于ODND算法,盲交匯算法的時間隨波數(shù)個數(shù)增長而增長,并且不同的波束個數(shù)對應(yīng)得到的仿真時間均小于ODND算法。ODND算法序列生成方式見文獻[17]的式(2),根據(jù)該序列的生成方式可知:波束個數(shù)N接近滿足式(13)的2n時,ODND協(xié)議的隨機性大大降低,算法執(zhí)行較少的選擇語句,造成ODND算法的時間沒有隨著波速個數(shù)的增加而增加。波束個數(shù)為12的仿真時間大于波束個數(shù)為15的,波束個數(shù)為24的仿真時間大于波束個數(shù)為30的。但是其仿真時間均大于本文提出的算法。此外,位置預(yù)測算法增加位置預(yù)測會加大算法計算時間,因此在波束個數(shù)小于42時,位置預(yù)測算法的計算時間大于盲交匯算法。位置預(yù)測算法的解空間大小是N,而盲交匯算法和ODND算法的解空間是N2,隨著N增大,解空間指數(shù)倍增大導(dǎo)致其計算時間增加速度遠大于位置預(yù)測算法,在波束個數(shù)大于42時,其計算時間大于位置預(yù)測算法。

2n-11,n∈Z

(13)

3.2 基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議最長鄰居 發(fā)現(xiàn)時間和平均鄰居發(fā)現(xiàn)時間性能對比

為了驗證盲交匯算法的鄰居發(fā)現(xiàn)性能,對盲交匯算法鄰居發(fā)現(xiàn)的最長發(fā)現(xiàn)時間和平均發(fā)現(xiàn)時間進行了仿真,并和文獻[17]的ODND算法進行了對比。設(shè)置仿真次數(shù)為10 000,統(tǒng)計10 000次鄰居發(fā)現(xiàn)的最長發(fā)現(xiàn)時間和10 000次鄰居發(fā)現(xiàn)的平均發(fā)現(xiàn)時間。

不同算法的鄰居發(fā)現(xiàn)協(xié)議最長鄰居發(fā)現(xiàn)時間(時隙個數(shù))如圖12所示。從圖12中可以看出,在不同波束個數(shù)條件下,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議最長鄰居發(fā)現(xiàn)時間均小于ODND協(xié)議的最長鄰居發(fā)現(xiàn)時間。

圖12 不同算法最長鄰居發(fā)現(xiàn)時間對比Fig.12 Worst-case neighbor discovery delay comparison of different algorithms

不同算法的平均鄰居發(fā)現(xiàn)時間(時隙個數(shù))如圖13所示。在波束個數(shù)為15、24、30、60時,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的平均發(fā)現(xiàn)時間小于ODND協(xié)議,其他情況下,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的平均發(fā)現(xiàn)時間大于ODND協(xié)議。由于波束個數(shù)N接近滿足式(13)的2n時,ODND協(xié)議的隨機性大大降低,其平均發(fā)現(xiàn)時間高于本文所提算法的。當(dāng)節(jié)點波束個數(shù)N和滿足式(13)的2n之差越大時,其隨機發(fā)現(xiàn)的次數(shù)增加,從而降低了平均發(fā)現(xiàn)時間。若ODND算法的N僅滿足2n≥N,可以通過增大2n減少平均鄰居發(fā)現(xiàn)時間,但這會嚴重增加最長鄰居發(fā)現(xiàn)時間。

圖13 不同算法平均鄰居發(fā)現(xiàn)時間對比Fig.13 Average neighbor discovery delay comparison of different algorithms

從圖13中可以看出,在波束個數(shù)N接近滿足式(13)的2n時,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的平均發(fā)現(xiàn)時間小于ODND協(xié)議。例如:N為12時基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的平均發(fā)現(xiàn)時間大于ODND協(xié)議,當(dāng)N為15時基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的平均發(fā)現(xiàn)時間小于ODND協(xié)議。N為12和N為15時,符合式(13)的2n為16,因此當(dāng)N接近16時,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議的平均發(fā)現(xiàn)時間小于ODND協(xié)議。

為了對上述分析的結(jié)論進行更詳細的說明,對基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議和ODND協(xié)議的平均發(fā)現(xiàn)時間進行對比?？紤]波束個數(shù)為8～16和波束個數(shù)為16～32情況下,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議和ODND協(xié)議得到的平均發(fā)現(xiàn)時間如圖14和圖15所示。

圖14 波束個數(shù)為8到16時的平均發(fā)現(xiàn)時間對比Fig.14 Average discovery delay comparison under different number of sectors ranging from 8 to 16

從圖14得知,在波束個數(shù)為8時基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議平均發(fā)現(xiàn)時間小于ODND協(xié)議,在波束個數(shù)為9時基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議平均發(fā)現(xiàn)時間大于ODND協(xié)議。這是因為在N為8時滿足式(13)的2n為8,N和2n之差為0,由于ODND算法的隨機性下降,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議平均發(fā)現(xiàn)時間小于ODND算法。N為9時滿足式(13)的2n為16,N和2n之差為7,基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議平均發(fā)現(xiàn)時間大于ODND算法。當(dāng)波束個數(shù)大于等于13時滿足式(13)的2n為16,N接近2n(16),基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議平均發(fā)現(xiàn)時間小于ODND協(xié)議。圖15中可以得到相同的結(jié)論,在波束個數(shù)大于等于24時,N接近2n(32),基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議平均發(fā)現(xiàn)時間小于ODND協(xié)議。

圖15 波束個數(shù)為16到32時的平均發(fā)現(xiàn)時間對比Fig.15 Average discovery delay comparison under different number of sectors ranging from 16 to 32

3.3 基于位置預(yù)測的鄰居發(fā)現(xiàn)算法性能

為了分析位置預(yù)測對鄰居發(fā)現(xiàn)算法性能的影響,對比了采用位置預(yù)測和不采用位置預(yù)測情況下的鄰居發(fā)現(xiàn)時間。令每對節(jié)點鄰居發(fā)現(xiàn)100次,每次鄰居發(fā)現(xiàn)后兩個節(jié)點按照勻速直線運動,然后重新進行鄰居發(fā)現(xiàn)。設(shè)置仿真實驗次數(shù)為10 000,并取10 000次實驗的平均值作為鄰居發(fā)現(xiàn)的時間,結(jié)果如圖16所示。

在圖16中,通過對比不同波束下的鄰居發(fā)現(xiàn)時間可以得知,基于位置預(yù)測后鄰居發(fā)現(xiàn)的平均時間明顯減小。在基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議首次鄰居發(fā)現(xiàn)后,獲得時間同步、位置、速度等信息,基于位置預(yù)測的鄰居發(fā)現(xiàn)協(xié)議利用這些信息進行位置預(yù)測可以迅速降低鄰居發(fā)現(xiàn)的時間。

(a) 波束個數(shù)為15(a) Number of sectors is 15

(b) 波束個數(shù)為30(b) Number of sectors is 30

4 結(jié)論

本文提出了一種基于盲交匯算法的毫米波網(wǎng)絡(luò)鄰居發(fā)現(xiàn)協(xié)議。通過推導(dǎo)鄰居發(fā)現(xiàn)過程中掃描間隔、波束個數(shù)與鄰居發(fā)現(xiàn)時間之間的理論關(guān)系,提出了一種定向波束盲交匯算法。在沒有任何交匯信息的情況下,兩個節(jié)點通過基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議實現(xiàn)鄰居發(fā)現(xiàn)?；诿そ粎R算法的鄰居發(fā)現(xiàn)協(xié)議只需按照波束盲交匯算法順序掃描實現(xiàn)波束交匯,每個波束掃描時隙執(zhí)行鄰居發(fā)現(xiàn)協(xié)議便可以實現(xiàn)鄰居發(fā)現(xiàn)。仿真驗證得知基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議最長鄰居發(fā)現(xiàn)時間小于ODND協(xié)議。各個節(jié)點通過基于盲交匯算法的鄰居發(fā)現(xiàn)協(xié)議獲得鄰居位置、時間同步信息等信息后采用位置預(yù)測算法快速實現(xiàn)鄰居發(fā)現(xiàn)。仿真驗證結(jié)果表明,采用位置預(yù)測的算法后,鄰居發(fā)現(xiàn)時間迅速減少。