定向毫米波網絡鄰居發現協議

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

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

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

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

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

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

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

在定向的毫米波網絡中,鄰居發現階段各個節點可能沒有任何鄰居交互信息。因此一個很重要的問題是如何在沒有公共控制信道和任何先驗信息的情況下發現鄰居。定向通信的鄰居發現需要收發雙方的波束交匯,因此在沒有公共控制信道和任何先驗信息的條件下如何引導波束轉向,實現收發雙方的波束交匯是一個重要的課題。定向波束的鄰居發現本質上是一個交匯(rendezvous)問題[23],當兩節點的定向波束均指向對方并建立通信鏈路實現信號的發送與接收時,才可以實現鄰居發現。在沒有交互信息的情況下實現定向通信的鄰居發現是一個盲交匯(blind rendezvous)問題[17-18, 23]。文獻[17]提出了無協調定向鄰居發現(oblivious directional neighbor discovery, ODND)協議,該協議能夠在沒有任何先驗信息的條件下實現波束盲交匯并完成鄰居發現,但問題是鄰居發現時間較長。為了縮短ODND協議中的鄰居發現時間,文獻[18]進一步提出了基于連續掃描定向天線模型的波束盲交匯算法,并根據該算法設計出基于搜索的定向鄰居發現(hunting-based directional neighbor discovery, HDND)協議實現鄰居發現。然而,HDND協議的連續掃描定向天線模型較為理想,在工程中難以實現[24]。

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

1 定向鄰居發現盲交匯問題描述

鄰居發現是實現網絡媒體訪問控制、拓撲控制等功能的關鍵技術之一。定向通信的鄰居發現和全向通信的鄰居發現不同,定向通信只能覆蓋一個方位角,因此其鄰居發現的復雜性遠大于全向天線的鄰居發現。在實際環境中,節點之間可能是異步的,鄰居發現協議應該在沒有公共控制信道和先驗信息的情況下實現鄰居發現。

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

1.1 系統模型

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

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

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

假設節點A和節點B均按照逆時針方向旋轉且時間同步,當前節點A指向波束4的方向記作PA=4,節點B指向波束3方向記作PB=3。假設節點A指向波束1,節點B指向波束4才能實現鄰居發現,記作(dA-B=1,dB-A=4)。若節點A和節點B按照逆時針順序切換下一個波束,根據PA、N可以得到節點A的掃描序列uA。根據PB、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)

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

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

通過圖2中的uA和uB可以得知:在這種情況下兩個節點只能搜索出{(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)這個解;無法實現節點A指向波束1同時節點B指向波束4,無法實現鄰居發現。兩個節點波束個數均為6時,共有36種交匯情況,因而無法搜索到所有解。

1.2 問題模型

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

保證交匯:在有限的時間范圍內,保證兩個節點實現波束交匯。

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

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

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

在毫米波網絡中,節點可能是不斷移動的,因此兩個節點交匯的方向dA-B和dB-A可能是任意組合,即?dA-B∈[1,N],dB-A∈[1,N],其初始波束的位置也是隨機的,即?PA∈[1,N],PB[1,N],ua表示節點A根據PA和N生成的序列,ub是節點B根據PB和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)表示的意思是:通過設計節點A的掃描序列ua和節點B的掃描序列ub最小化全交匯時間,保證節點A和節點B當前任意波束指向的組合(PA,PB)∈[1,N]×[1,N],節點A和節點B波束交匯的組合(dA-B,dB-A)∈[1,N]×[1,N],可以使節點A和節點B在t≤Tbr時刻分別指向dA-B和dB-A從而實現節點A和節點B的波束交匯。

2 基于位置預測的鄰居發現算法

2.1 定向波束盲交匯算法

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

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

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

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

□

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

□

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

圖3 N=6,(MT=2,MR=3)時節點A和 節點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)時節點A和 節點B波束掃描序列Fig.4 Beam scan sequence of node A and node B when N=6,(MT=1,MR=6)

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

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

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

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

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

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

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

(4)

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

(5)

2.2 基于盲交匯算法的鄰居發現協議

在利用2.1節實現波束交匯后,需要兩個節點執行鄰居發現協議實現鄰居發現。

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

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

(6)

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

圖8 BARTS和BACTS結構Fig.8 Structure of BARTS and BACTS

2.3 基于位置預測的鄰居發現協議

通過2.1節和2.2節的協議實現全網鄰居發現后,每個節點可以發現本節點的鄰居和本節點鄰居的ID號、位置、速度、方向和時鐘同步信息。

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

(7)

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

圖9 RTS結構Fig.9 Structure of RTS

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

圖10 CTS結構Fig.10 Structure of CTS

完成RTS/CTS鄰居發現后,用戶A進行數據傳輸。

基于預測的鄰居發現協議的RTS和CTS結構比BARTS和BACTS結構長,增大了對信道的占用時間,但是預測算法減少了波束交匯時間,對信道的占用時間減少。基于位置預測算法的鄰居發現協議與基于盲交匯算法的鄰居發現協議的信道占用時間之比如式(8)所示,式中:TRTS,TCTS,TBARTS,TBACTS分別表示RTS,CTS,BARTS,BACTS時間;TP-BA表示基于預測算法鄰居發現協議的平均鄰居發現時間,如式(9)所示,其中i表示搜索次數。

(8)

(9)

2.4 旁瓣效應下的鄰居發現協議性能評估

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

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

(10)

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

旁瓣對于鄰居發現的影響:

1)主瓣-旁瓣通信實現鄰居發現;

2)旁瓣-旁瓣通信實現鄰居發現。

在情況1的條件下,主瓣-主瓣同樣也可以實現鄰居發現,在情況2的條件下,主瓣-主瓣、主瓣-旁瓣也可以實現鄰居發現。

2.4.1 主瓣-旁瓣通信實現鄰居發現

當兩個節點的主瓣-旁瓣之間的通信距離可以滿足兩個節點的通信距離需求時,可以提高鄰居發現的速度。

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

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

2.4.2 旁瓣-旁瓣通信實現鄰居發現

當兩個節點的旁瓣-旁瓣之間的通信距離可以滿足兩個節點的通信距離需求時,可以提高鄰居發現的速度。

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

3 仿真分析

3.1 盲交匯算法計算復雜度性能對比

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

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

采用MATLAB對三個算法進行算法復雜度仿真,設置仿真次數為10 000,統計算法的累計運行時間,結果如圖11所示。

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

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

2n-11,n∈Z

(13)

3.2 基于盲交匯算法的鄰居發現協議最長鄰居 發現時間和平均鄰居發現時間性能對比

為了驗證盲交匯算法的鄰居發現性能,對盲交匯算法鄰居發現的最長發現時間和平均發現時間進行了仿真,并和文獻[17]的ODND算法進行了對比。設置仿真次數為10 000,統計10 000次鄰居發現的最長發現時間和10 000次鄰居發現的平均發現時間。

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

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

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

圖13 不同算法平均鄰居發現時間對比Fig.13 Average neighbor discovery delay comparison of different algorithms

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

為了對上述分析的結論進行更詳細的說明,對基于盲交匯算法的鄰居發現協議和ODND協議的平均發現時間進行對比。考慮波束個數為8～16和波束個數為16～32情況下,基于盲交匯算法的鄰居發現協議和ODND協議得到的平均發現時間如圖14和圖15所示。

圖14 波束個數為8到16時的平均發現時間對比Fig.14 Average discovery delay comparison under different number of sectors ranging from 8 to 16

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

圖15 波束個數為16到32時的平均發現時間對比Fig.15 Average discovery delay comparison under different number of sectors ranging from 16 to 32

3.3 基于位置預測的鄰居發現算法性能

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

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

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

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

4 結論

本文提出了一種基于盲交匯算法的毫米波網絡鄰居發現協議。通過推導鄰居發現過程中掃描間隔、波束個數與鄰居發現時間之間的理論關系,提出了一種定向波束盲交匯算法。在沒有任何交匯信息的情況下,兩個節點通過基于盲交匯算法的鄰居發現協議實現鄰居發現。基于盲交匯算法的鄰居發現協議只需按照波束盲交匯算法順序掃描實現波束交匯,每個波束掃描時隙執行鄰居發現協議便可以實現鄰居發現。仿真驗證得知基于盲交匯算法的鄰居發現協議最長鄰居發現時間小于ODND協議。各個節點通過基于盲交匯算法的鄰居發現協議獲得鄰居位置、時間同步信息等信息后采用位置預測算法快速實現鄰居發現。仿真驗證結果表明,采用位置預測的算法后,鄰居發現時間迅速減少。