定向毫米波網(wǎng)絡(luò)鄰居發(fā)現(xiàn)協(xié)議

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

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

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

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

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

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

根據(jù)收發(fā)端時(shí)間的同步性,定向鄰居發(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)時(shí)間會(huì)變長(zhǎng)。

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

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

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

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

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

1.1 系統(tǒng)模型

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

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

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

假設(shè)節(jié)點(diǎn)A和節(jié)點(diǎn)B均按照逆時(shí)針?lè)较蛐D(zhuǎn)且時(shí)間同步,當(dāng)前節(jié)點(diǎn)A指向波束4的方向記作PA=4,節(jié)點(diǎn)B指向波束3方向記作PB=3。假設(shè)節(jié)點(diǎn)A指向波束1,節(jié)點(diǎn)B指向波束4才能實(shí)現(xiàn)鄰居發(fā)現(xiàn),記作(dA-B=1,dB-A=4)。若節(jié)點(diǎn)A和節(jié)點(diǎn)B按照逆時(shí)針順序切換下一個(gè)波束,根據(jù)PA、N可以得到節(jié)點(diǎn)A的掃描序列uA。根據(jù)PB、N可以得到節(jié)點(diǎn)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按照每個(gè)時(shí)隙切換一次,如圖2所示。

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

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

1.2 問(wèn)題模型

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

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

全交匯:兩個(gè)用戶初始指向任何方向、交匯方向?yàn)槿我夥较?都可以保證波束交匯。

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

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

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

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

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

2.1 定向波束盲交匯算法

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

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

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

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

□

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

□

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

圖3 N=6,(MT=2,MR=3)時(shí)節(jié)點(diǎn)A和 節(jié)點(diǎn)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)時(shí)節(jié)點(diǎn)A和 節(jié)點(diǎn)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)條件下才能在最短的時(shí)間內(nèi)實(shí)現(xiàn)全交匯,最短全交匯時(shí)間為N(N+1)T,最小盲交匯時(shí)間的上界為N(N+1)T。

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

圖5 同步狀態(tài)且N=6時(shí)依據(jù)定理2 設(shè)計(jì)的波束掃描序列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é)點(diǎn)A搜索完畢所有方向后,節(jié)點(diǎn)B在節(jié)點(diǎn)A的每個(gè)方向持續(xù)時(shí)間均大于T。因此,盲交匯消耗時(shí)間為N(N+1)T。在定理2中,在(MT≠1,MR≠N)或者(MT≠N,MR≠1)條件下,最短全交匯時(shí)間為min(MT,MR)·NT+N2T,在異步狀態(tài)下最短全交匯時(shí)間至少為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)條件下才能在最短的時(shí)間內(nèi)實(shí)現(xiàn)全交匯,最短全交匯時(shí)間為N(N+1)T。在異步狀態(tài)下,(MT=1,MR=N+1)或(MT=N+1,MR=1)條件下可以實(shí)現(xiàn)最小盲交匯時(shí)間的上界,最小盲交匯時(shí)間的上界為N(N+1)T。

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

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

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

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

(4)

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

(5)

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

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

兩個(gè)用戶發(fā)射一個(gè)波束對(duì)準(zhǔn)請(qǐng)求發(fā)送(beam alignment request to send, BARTS)的時(shí)間定義為TT-BARTS,接收一個(gè)波束對(duì)準(zhǔn)允許發(fā)送(beam alignment clear to send, BACTS)的時(shí)間為TT-BACTS,將時(shí)間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é)點(diǎn)的ID號(hào);Location數(shù)據(jù)表示發(fā)射數(shù)據(jù)包節(jié)點(diǎn)從GPS導(dǎo)航中獲取的位置信息;Time 表示發(fā)射數(shù)據(jù)包節(jié)點(diǎn)的時(shí)鐘同步信息;Speed表示發(fā)射節(jié)點(diǎn)的速度信息;Direction表示當(dāng)前該節(jié)點(diǎn)指向的方向。

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

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

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

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

(7)

任意一個(gè)節(jié)點(diǎn)A在準(zhǔn)備和其他用戶B進(jìn)行通信時(shí),采用式(7)對(duì)其位置進(jìn)行預(yù)測(cè),直接對(duì)節(jié)點(diǎn)B的方向發(fā)射請(qǐng)求發(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é)點(diǎn)B的ID,Transmitter ID表示用戶A的ID。Duration表示后續(xù)數(shù)據(jù)包需要的時(shí)間。

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

此時(shí),節(jié)點(diǎn)A為發(fā)射狀態(tài),節(jié)點(diǎn)B為接收狀態(tài),雙方就可以實(shí)現(xiàn)本次鄰居發(fā)現(xiàn)。節(jié)點(diǎn)B最多進(jìn)行N次波束切換就可以收到用戶A的RTS數(shù)據(jù)包。在用戶B接收到數(shù)據(jù)包后,可以獲得用戶A的位置速度方向時(shí)間信息。用戶B采用式(7)計(jì)算用戶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進(jìn)行數(shù)據(jù)傳輸。

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

(8)

(9)

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

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

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

(10)

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

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

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

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

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

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

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

2n-11,n∈Z

(13)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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