一種定向無線自組網(wǎng)鄰居發(fā)現(xiàn)算法*

胡鄭峰，王 建

(中國船舶重工集團(tuán)公司第七二四研究所，南京 211106)

0 引 言

采用定向天線波束掃描的無線移動自組網(wǎng)技術(shù)，空間復(fù)用度和信道利用率高，節(jié)點(diǎn)間通信距離遠(yuǎn)，同時節(jié)點(diǎn)間的定向傳輸信道大大降低了通信信號被截獲與干擾的風(fēng)險，是現(xiàn)代無線移動自組織網(wǎng)絡(luò)技術(shù)研究的重點(diǎn)[1]。

節(jié)點(diǎn)鄰居發(fā)現(xiàn)是無線移動自組網(wǎng)建網(wǎng)的第一步，組網(wǎng)前首先需要開機(jī)進(jìn)行各節(jié)點(diǎn)鄰居搜索，建立鄰居節(jié)點(diǎn)表之后，才能申請加入已有網(wǎng)絡(luò)或新建網(wǎng)絡(luò)。采用定向天線時，由于節(jié)點(diǎn)搜索波束很窄，相鄰節(jié)點(diǎn)如何在短時間內(nèi)完成波束對準(zhǔn)成為鄰居發(fā)現(xiàn)過程中的難點(diǎn)[2]?，F(xiàn)有基于定向天線的鄰居發(fā)現(xiàn)算法的研究中，通常假定節(jié)點(diǎn)攜帶GPS等同步設(shè)備，可預(yù)先完成時間同步[3-4]，這對節(jié)點(diǎn)組網(wǎng)設(shè)備要求較高，在許多實際應(yīng)用場景中難以實現(xiàn)。而針對節(jié)點(diǎn)時鐘異步的發(fā)現(xiàn)算法，節(jié)點(diǎn)的波束方向與收發(fā)模式大多采用隨機(jī)選取的方式[5]，這對節(jié)點(diǎn)初始協(xié)調(diào)要求較低，但各節(jié)點(diǎn)隨機(jī)選取波束方向與收發(fā)狀態(tài)容易導(dǎo)致發(fā)現(xiàn)總時長波動較大，有時會造成嚴(yán)重的時長拖尾問題。文獻(xiàn)[6-7]通過構(gòu)建特殊的節(jié)點(diǎn)波束掃描方向序列，可以在確定周期內(nèi)完成任意兩節(jié)點(diǎn)的波束對準(zhǔn)，但都沒有同時確定相應(yīng)的節(jié)點(diǎn)收發(fā)模式，在隨機(jī)收發(fā)模式下不具有穩(wěn)定的搜索時長上界。文獻(xiàn)[8]研究了基于網(wǎng)格式quorum系統(tǒng)的確定性鄰居發(fā)現(xiàn)算法，利用quorum系統(tǒng)的旋轉(zhuǎn)封閉特性，可以實現(xiàn)異步網(wǎng)絡(luò)中的節(jié)點(diǎn)波束穩(wěn)定交會，其發(fā)現(xiàn)時長與天線波束數(shù)量成正比。但該算法需采用多波束天線，要求節(jié)點(diǎn)天線能同時進(jìn)行發(fā)送與接收，這對節(jié)點(diǎn)設(shè)備要求較高。此外，在節(jié)點(diǎn)間時延差較大時，該算法性能較差。文獻(xiàn)[9]對常用的SAND協(xié)議進(jìn)行改進(jìn)，通過令牌判定當(dāng)前進(jìn)行鄰居發(fā)現(xiàn)的主節(jié)點(diǎn)，主節(jié)點(diǎn)經(jīng)過輪詢完成鄰居發(fā)現(xiàn)后將令牌傳遞給下一節(jié)點(diǎn)，直到遍歷完所有節(jié)點(diǎn)。該算法通過引入扇區(qū)方位信息，減少扇區(qū)組合數(shù)目，提高了節(jié)點(diǎn)發(fā)現(xiàn)效率。但由于令牌傳遞機(jī)制，其完成鄰居發(fā)現(xiàn)所需時長與全網(wǎng)節(jié)點(diǎn)數(shù)成正比，在節(jié)點(diǎn)數(shù)較多時耗時仍然較長。

針對這些問題，文獻(xiàn)[10]提出了一種確定性鄰居發(fā)現(xiàn)算法，將基于二進(jìn)制編碼的收發(fā)序列應(yīng)用于采用定向發(fā)送、全向接收天線的無線組網(wǎng)系統(tǒng)，通過規(guī)律性改變收發(fā)序列的方法，使其可以在異步系統(tǒng)中完成節(jié)點(diǎn)的鄰居發(fā)現(xiàn)。本文將二進(jìn)制編碼序列收發(fā)模式擴(kuò)展應(yīng)用到發(fā)送和接收全部采用定向天線的無線移動自組網(wǎng)系統(tǒng)中，針對不同時延情況下對編碼序列的選擇要求，給出了確定的天線掃描策略和采用一種二進(jìn)制編碼序列的收發(fā)狀態(tài)切換模式，可以滿足節(jié)點(diǎn)不同時間差的異步發(fā)現(xiàn)要求。與未確定收發(fā)模式的異步鄰居發(fā)現(xiàn)算法相比，本文所提算法具有更短的平均搜索時間與更小的搜索時間上界。

1 鄰居發(fā)現(xiàn)過程

在本文中，假設(shè)無線自組網(wǎng)中的節(jié)點(diǎn)具有如下性質(zhì)：

(2)所有節(jié)點(diǎn)采用半雙工方式通信，每個時刻節(jié)點(diǎn)只能處于發(fā)送或接收中的一個模式。只有當(dāng)兩個節(jié)點(diǎn)處于通信距離內(nèi)，波束扇區(qū)互相指向?qū)Ψ?，且一個處于發(fā)送模式，另一個處于接收模式，才能進(jìn)行通信。節(jié)點(diǎn)以特定的方式選擇其發(fā)送與接收狀態(tài)，稱為收發(fā)模式。

(3)節(jié)點(diǎn)無需GPS等同步設(shè)備進(jìn)行提前時間同步，節(jié)點(diǎn)在開機(jī)時處于時間異步狀態(tài)。

(4)節(jié)點(diǎn)采用頻分多址，各節(jié)點(diǎn)隨機(jī)在M個載頻上選擇一個載頻發(fā)送信息。

如圖1(a)所示，A、B兩節(jié)點(diǎn)當(dāng)且僅當(dāng)其波束相互對準(zhǔn)且收發(fā)狀態(tài)互異時可以成功發(fā)現(xiàn)。圖1(b)中兩節(jié)點(diǎn)未處于一發(fā)一收狀態(tài)或圖1(c)中兩節(jié)點(diǎn)波束未相互對準(zhǔn)都會導(dǎo)致發(fā)現(xiàn)失敗。同時，如圖1(d)所示，當(dāng)同一時隙有兩個發(fā)送節(jié)點(diǎn)向同一接收節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時，數(shù)據(jù)包會發(fā)生碰撞，如果未采用頻分多址或碼分多址等方式進(jìn)行規(guī)避，會使兩個發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)發(fā)現(xiàn)失敗。

圖1 節(jié)點(diǎn)鄰居發(fā)現(xiàn)示意圖

從圖1可以看出，鄰居發(fā)現(xiàn)問題的關(guān)鍵在于設(shè)計節(jié)點(diǎn)收發(fā)模式與天線波束掃描策略，使其從開機(jī)掃描到相互發(fā)現(xiàn)的時間更短，同時盡可能減少節(jié)點(diǎn)之間的碰撞。

2 基于二進(jìn)制編碼序列的鄰居發(fā)現(xiàn)算法

2.1 算法原理

2.1.1 收發(fā)模式編碼序列

規(guī)定每個節(jié)點(diǎn)配備獨(dú)立的二進(jìn)制編碼，節(jié)點(diǎn)隨時間順序按位選擇二進(jìn)制編碼序列的碼字，一個碼字持續(xù)時間為tcode，以此確定每個時隙的節(jié)點(diǎn)收發(fā)模式：碼字為 1 時，節(jié)點(diǎn)進(jìn)入發(fā)送模式，發(fā)送鄰居發(fā)現(xiàn)信息；編碼為0時，節(jié)點(diǎn)處于接收狀態(tài)。不同編碼示例對應(yīng)的收發(fā)模式如表1所示。

表1 節(jié)點(diǎn)編碼對應(yīng)收發(fā)模式

在節(jié)點(diǎn)時間同步情況下，當(dāng)任意兩節(jié)點(diǎn)二進(jìn)制編碼間的漢明距離大于1時，必定存在一個碼字時間，節(jié)點(diǎn)對處于一發(fā)一收狀態(tài)。

2.1.2 波束掃描策略

在基于二進(jìn)制編碼序列確定收發(fā)模式基礎(chǔ)上，引入天線波束掃描策略。設(shè)編碼長度為L，天線扇區(qū)數(shù)為K，用時隙tslot表示波束指向最短駐留時間切片的長度，一個碼字持續(xù)時間tcode為K×K個時隙。當(dāng)節(jié)點(diǎn)進(jìn)入接收狀態(tài)時，接收波束按逆時針方向掃描，每個扇區(qū)內(nèi)駐留K個時隙。當(dāng)節(jié)點(diǎn)進(jìn)入發(fā)送狀態(tài)時，發(fā)送波束同樣按逆時針掃描，每個扇區(qū)內(nèi)駐留1個時隙。

在一個碼字持續(xù)時間內(nèi)，發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的波束掃描方式如表2所示。

表2 節(jié)點(diǎn)波束掃描方式

在節(jié)點(diǎn)時間同步情況下，由于接收節(jié)點(diǎn)的接收波束在一個方向駐留時間內(nèi)，發(fā)送節(jié)點(diǎn)的發(fā)送波束可以完成所有方向的掃描，因此在接收節(jié)點(diǎn)的接收波束進(jìn)行全方位掃描過程中，發(fā)送節(jié)點(diǎn)的波束覆蓋扇區(qū)與接收節(jié)點(diǎn)的波束覆蓋扇區(qū)完成相互對準(zhǔn)的遍歷，收發(fā)波束相互波束對準(zhǔn)概率為1。結(jié)合二進(jìn)制編碼收發(fā)模式，可以確保任意節(jié)點(diǎn)對相互發(fā)現(xiàn)的最大時長tsyn為

tsyn=L×K×K×tslot。

(1)

2.2 異步收發(fā)編碼設(shè)計

在定向收發(fā)無線網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)之間時間異步時，僅兩兩間漢明距離大于1的二進(jìn)制編碼序列，無法滿足節(jié)點(diǎn)間收發(fā)模式互異的要求，需要對序列組做出改進(jìn)。下面對節(jié)點(diǎn)間不同異步情況分別進(jìn)行分析。

2.2.1 旋轉(zhuǎn)相似性

當(dāng)節(jié)點(diǎn)之間的時鐘差Δt為一個編碼時間長度的整數(shù)倍時，即

Δt=m×tcode=m×K×K×tslot。

(2)

式中：m為任意整數(shù)；K為節(jié)點(diǎn)天線扇區(qū)數(shù)目。引入旋轉(zhuǎn)相似的定義：設(shè)序列A長度為L，定義rotate(A,i)為

rotate(A,i)={A((i+1)modL),A((i+2)modL),…,

A((i+L)modL)}。

(3)

對長度為L的序列A和B，若

?i∈{0,1,…,L-1}:rotate(A,i)=B，

(4)

則稱序列A與B旋轉(zhuǎn)相似，記為Rsimilar(A,B)=1；若序列組M中任意序列都不旋轉(zhuǎn)相似，記Rsimilar(M)=0。

當(dāng)兩節(jié)點(diǎn)的收發(fā)模式編碼序列旋轉(zhuǎn)相似時，可能會因為時延導(dǎo)致兩節(jié)點(diǎn)的碼字在同一碼字時間內(nèi)始終相同，無法進(jìn)入收發(fā)互異狀態(tài)，從而導(dǎo)致永遠(yuǎn)無法相互發(fā)現(xiàn)。因此收發(fā)編碼序列設(shè)計時，要避免序列組內(nèi)任意兩序列出現(xiàn)旋轉(zhuǎn)相似，才能作為節(jié)點(diǎn)的收發(fā)編碼序列。

2.2.2 旋轉(zhuǎn)互異性

當(dāng)節(jié)點(diǎn)間時鐘相差Δt為時隙長度的整數(shù)倍時，即

Δt=m×tslot。

(5)

式中：m為任意整數(shù)。引入旋轉(zhuǎn)互異性的定義：對二進(jìn)制序列A和B，令A(yù)r=rotate(A,i)，其中i∈{0,1,…,L-1}。令A(yù)r(l)表示序列Ar第l個碼字，若?l1,l2∈{0,1,…,L-1}，滿足

(6)

則稱序列A與序列B旋轉(zhuǎn)互異，記為Rdiffer(A,B)=1；若序列組M中任意序列都旋轉(zhuǎn)互異，記Rdiffer(M)=1。

對時鐘異步且編碼長度為L的兩個節(jié)點(diǎn)I、J，不妨設(shè)節(jié)點(diǎn)J在一個收發(fā)編碼內(nèi)進(jìn)入掃描扇區(qū)時間滯后于節(jié)點(diǎn)I，令I(lǐng)(tcode_n)、J(tcode_n) 分別表示兩節(jié)點(diǎn)原本在碼字時間tcode_n內(nèi)的碼字。當(dāng)兩節(jié)點(diǎn)序列相互旋轉(zhuǎn)互異時，?tcode_1,tcode_2∈{0,1,…,L-1}，滿足

(7)

由于兩節(jié)點(diǎn)開始進(jìn)行波束掃描的時間差Δt以I節(jié)點(diǎn)時鐘為時間基準(zhǔn)，在編碼時間tcode_1內(nèi)，雖然I節(jié)點(diǎn)由于節(jié)點(diǎn)間時差導(dǎo)致天線波束掃描扇區(qū)的前n個扇區(qū)未能與J節(jié)點(diǎn)交會，但J節(jié)點(diǎn)原本應(yīng)在tcode_2-tcode碼字時間內(nèi)掃描的后n個扇區(qū)，卻因滯后可以在tcode_2碼字時間內(nèi)與節(jié)點(diǎn)I的前n個扇區(qū)交會。當(dāng)序列滿足該性質(zhì)時，無論節(jié)點(diǎn)間時延相差多少，總能實現(xiàn)掃描扇區(qū)的交會，如圖2所示。

圖2 旋轉(zhuǎn)互異序列扇區(qū)交會示意圖

2.2.3 一種二進(jìn)制編碼序列構(gòu)建方法

當(dāng)序列組同時滿足旋轉(zhuǎn)相似與旋轉(zhuǎn)互異性時，可以選擇其作為二進(jìn)制編碼異步鄰居發(fā)現(xiàn)的收發(fā)編碼序列組。一種滿足兩條性質(zhì)的序列組的構(gòu)建方法如下：

(1)設(shè)節(jié)點(diǎn)數(shù)為N，為每個節(jié)點(diǎn)配置唯一且長度相同的數(shù)字ID，設(shè)其大小為nnode；再將ID轉(zhuǎn)為二進(jìn)制，長度為L,L>2。如數(shù)字6，二進(jìn)制表示為110，此時序列組雖然相互漢明距離大于0，但不滿足之前討論的兩種性質(zhì)。

(2)在已生成的二進(jìn)制編碼序列后增加L位，新增的L位序列取值為節(jié)點(diǎn)數(shù)字編號加2的二進(jìn)制形式，當(dāng)nnode+2>2L時，新增編碼為(nnode+2)mod(2L)，新序列長度為2L，新生成的序列組記為[N|N+2]。例如ID為6的節(jié)點(diǎn)，其二進(jìn)制編碼為110000。

通過仿真驗證，序列組[N|N+2]滿足旋轉(zhuǎn)互異性，同時序列組內(nèi)所有序列兩兩間都不旋轉(zhuǎn)相似，因此在節(jié)點(diǎn)時間異步情況下，可以采用該編碼方法產(chǎn)生節(jié)點(diǎn)鄰居發(fā)現(xiàn)的收發(fā)編碼序列。

2.3 波束掃描策略設(shè)計

針對上述收發(fā)編碼鄰居發(fā)現(xiàn)算法，相應(yīng)的天線波束掃描策略需進(jìn)行如下調(diào)整：

(1)節(jié)點(diǎn)在開機(jī)后，隨機(jī)選擇兩個方向，分別作為發(fā)送波束起始方向與接收波束起始方向，之后按逆時針方向掃描，在完整的2L×K2×tslot編碼周期內(nèi)，每次進(jìn)入發(fā)送或接收狀態(tài)的起始波束方向不變。

(2)節(jié)點(diǎn)每經(jīng)過長為2L×K2×tslot的收發(fā)編碼周期，重新選擇發(fā)送波束與接收波束的起始方向。

節(jié)點(diǎn)i在時隙tslot_n內(nèi)扇區(qū)方向S(i,t)滿足

(8)

式中：tslot_n為最先開機(jī)節(jié)點(diǎn)的時隙，作為時鐘基準(zhǔn)；delayi為i節(jié)點(diǎn)與時鐘基準(zhǔn)的開機(jī)時間差；kt、kr分別為節(jié)點(diǎn)隨機(jī)選擇的初始發(fā)送接收扇區(qū)方向，每隔一個編碼周期重新隨機(jī)選擇；u(i,t)為tslot_n時隙內(nèi)節(jié)點(diǎn)i的編碼。

采用該序列的節(jié)點(diǎn)一個完整的收發(fā)編碼周期為2L×K2×tslot，其中，K為節(jié)點(diǎn)扇區(qū)數(shù)目，tslot為時隙長度。在不考慮碰撞情況下，以先開機(jī)節(jié)點(diǎn)的開機(jī)時間為起始，節(jié)點(diǎn)間開機(jī)時間差為Δt，任意兩節(jié)點(diǎn)發(fā)現(xiàn)時長的上界tdiscover_max為

tdiscover_max=Δt+2L×K2×tslot。

(9)

2.4 碰撞概率分析

當(dāng)接收節(jié)點(diǎn)同時收到多個發(fā)送節(jié)點(diǎn)的數(shù)據(jù)包時會產(chǎn)生沖突，造成接收失敗，稱為波束碰撞。在任意時隙，由于其發(fā)送節(jié)點(diǎn)初始波束方向隨機(jī)，所以相鄰發(fā)送節(jié)點(diǎn)間波束方向同時指向同一接收節(jié)點(diǎn)的概率為1/K，當(dāng)扇區(qū)數(shù)越大時，相鄰節(jié)點(diǎn)之間波束碰撞的概率越小。

由于節(jié)點(diǎn)組合不同的空間分布以及各節(jié)點(diǎn)在空間中處于不同位置，其每個扇區(qū)內(nèi)包含的節(jié)點(diǎn)數(shù)目不同，節(jié)點(diǎn)在每個扇區(qū)內(nèi)發(fā)生波束碰撞的概率也不相同。為簡化場景，設(shè)在同一時刻，一個接收節(jié)點(diǎn)在其接收扇區(qū)范圍內(nèi)有c個相鄰節(jié)點(diǎn)處于發(fā)送狀態(tài)，c的大小與節(jié)點(diǎn)的空間分布形狀、節(jié)點(diǎn)密度以及通信距離有關(guān)。設(shè)c個節(jié)點(diǎn)隨機(jī)分布于接收節(jié)點(diǎn)周圍，節(jié)點(diǎn)采用頻分多址，載頻數(shù)為M，扇區(qū)數(shù)為K,則一個接收節(jié)點(diǎn)A在與其中一發(fā)送節(jié)點(diǎn)B進(jìn)行扇區(qū)交會時，與其他發(fā)送節(jié)點(diǎn)不發(fā)生碰撞的條件如下：

(1)其他發(fā)送節(jié)點(diǎn)位于其他扇區(qū)，此時不會發(fā)生碰撞，令psector(0)為該情況發(fā)生的概率，則有

(10)

(2)其他c-1個節(jié)點(diǎn)中有v個節(jié)點(diǎn)與發(fā)送節(jié)點(diǎn)B位于一個扇區(qū)內(nèi)，v≤c-1，令psector(v)為該情況發(fā)生的概率，則有

(11)

此時，其余v個節(jié)點(diǎn)的載頻都與發(fā)送節(jié)點(diǎn)B不同，發(fā)送節(jié)點(diǎn)B的信息傳輸不會發(fā)生碰撞。令pf(v)為該情況發(fā)生概率，則有

(12)

綜上所述，節(jié)點(diǎn)A在一次波束交會中，正確發(fā)現(xiàn)的概率p(c,K,M)為

(13)

以c=4，K=16，M=4為例，在相鄰節(jié)點(diǎn)的一次發(fā)現(xiàn)過程中，成功發(fā)現(xiàn)的概率為95.39%。節(jié)點(diǎn)每過一個編碼周期，初始波束掃描方向會重新隨機(jī)選擇，避免前一周期波束碰撞的兩個發(fā)送節(jié)點(diǎn)在下一周期繼續(xù)發(fā)生碰撞。令一個周期內(nèi)碰撞概率為pcollide，連續(xù)n個周期都發(fā)生碰撞的概率為pncollide，當(dāng)pcollide較小時，兩個周期同時發(fā)生碰撞的概率很低。

2.5 節(jié)點(diǎn)工作流程

節(jié)點(diǎn)開機(jī)后，首先選擇初始收發(fā)波束方向，并判斷第一位編碼碼字：碼字為1，進(jìn)入發(fā)送狀態(tài)，每個時隙旋轉(zhuǎn)一次發(fā)送波束方向；碼字為0，進(jìn)入接收狀態(tài)，每K個時隙旋轉(zhuǎn)一次接收波束方向。每過K2個時隙，節(jié)點(diǎn)進(jìn)入下一位編碼，直到經(jīng)過2L位編碼碼字后，結(jié)束一個波束掃描搜索周期。若要繼續(xù)進(jìn)行掃描搜索，則重新選擇初始收發(fā)波束方向后，開始下一個周期的波束掃描搜索，直到搜索時間超過預(yù)定搜索時長上限，結(jié)束搜索。節(jié)點(diǎn)的搜索流程如圖3所示，St與Sr分別為發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的初始波束方向，t為當(dāng)前搜索時隙，k為波束方向計數(shù)，K為扇區(qū)總數(shù)，i為碼字位數(shù)標(biāo)記，t_end為搜索時間上限。

圖3 節(jié)點(diǎn)搜索方式流程圖

3 仿真結(jié)果分析

為了驗證基于二進(jìn)制編碼的鄰居發(fā)現(xiàn)算法的性能，采用Matlab仿真平臺對節(jié)點(diǎn)的單次發(fā)現(xiàn)概率、發(fā)現(xiàn)的平均時長和總時長等性能進(jìn)行仿真分析，并與文獻(xiàn)[7]提出的確定性發(fā)現(xiàn)算法(簡稱算法1)進(jìn)行比較。算法1通過節(jié)點(diǎn)ID規(guī)定了確定的扇區(qū)掃描序列，異步狀態(tài)下可以在固定周期內(nèi)完成節(jié)點(diǎn)間任意扇區(qū)對的匯聚，但其未對節(jié)點(diǎn)的收發(fā)狀態(tài)做出約束。在下列仿真中采用隨機(jī)選擇的方式來確定收發(fā)狀態(tài)，進(jìn)入接收與發(fā)送狀態(tài)的概率都為0.5，同時假定節(jié)點(diǎn)的分布隨機(jī)且時間同步誤差隨機(jī)。兩種算法均進(jìn)行1 000次蒙特卡洛仿真，然后取結(jié)果的平均值進(jìn)行比較分析。主要仿真參數(shù)如表3所示。

表3 主要仿真參數(shù)設(shè)置

3.1 波束交會時長

兩種算法的波束交會時長隨扇區(qū)數(shù)變化和隨ID位數(shù)變化情況的仿真結(jié)果分別如圖4(a)和圖4(b)所示。兩種算法都基于節(jié)點(diǎn)唯一ID確定波束掃描策略，節(jié)點(diǎn)的初始ID均從0開始選取，N個節(jié)點(diǎn)的ID的二進(jìn)制編碼長度L取最小值?lbN」。

(a)扇區(qū)交會時長隨扇區(qū)數(shù)變化(ID位數(shù)為4)

(b)扇區(qū)交會時長隨ID位數(shù)變化(扇區(qū)數(shù)為8)圖4 波束交會時長比較

由圖4可以看出，在節(jié)點(diǎn)初始ID長度相同時，兩種算法的波束交會時長都隨扇區(qū)數(shù)K的增大而增大，且增長的速度與K2近似成正比關(guān)系，本文的算法在波束交會平均時長與最大交會時長上都小于算法1。在節(jié)點(diǎn)扇區(qū)數(shù)相同時，兩種算法的波束交會時長都近似與節(jié)點(diǎn)初始ID位數(shù)成正比，本文算法在ID位數(shù)為3～7位時，波束交會時長性能優(yōu)于算法1。這是由于當(dāng)ID位數(shù)較大時，本文的交會時長與2L成正比，算法1波束交會時長近似與1.5L+3成正比，當(dāng)ID位數(shù)更大且扇區(qū)數(shù)相同時，其波束交會時長可能更短。

3.2 單次交會發(fā)現(xiàn)成功概率

由于兩算法在各自掃描周期內(nèi)完成波束交會的概率都為1，但在不同扇區(qū)數(shù)目與鄰居節(jié)點(diǎn)數(shù)目下，當(dāng)兩相鄰節(jié)點(diǎn)波束交會時，兩種算法可以成功發(fā)現(xiàn)的概率(即處于收發(fā)互異狀態(tài)且未發(fā)生節(jié)點(diǎn)碰撞的概率)存在較大差異，如圖5所示。

(a)發(fā)現(xiàn)概率隨扇區(qū)數(shù)變化(Nnei=8)

(b)發(fā)現(xiàn)概率隨鄰居節(jié)點(diǎn)數(shù)變化(扇區(qū)數(shù)為8)圖5 波束交會時發(fā)現(xiàn)成功率比較

設(shè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)為Nnei，由圖5可以看出，當(dāng)Nnei固定時，相鄰節(jié)點(diǎn)在一次波束交會中發(fā)現(xiàn)成功的概率隨扇區(qū)數(shù)的增大而增大。各發(fā)送節(jié)點(diǎn)發(fā)送波束方向隨機(jī)，扇區(qū)數(shù)的增加會使得其余發(fā)送節(jié)點(diǎn)波束方向與當(dāng)前通信節(jié)點(diǎn)沖突的概率降低，從而使得發(fā)現(xiàn)成功率上升。而當(dāng)扇區(qū)數(shù)K固定時，空間中鄰居節(jié)點(diǎn)數(shù)越大，發(fā)生碰撞的概率越大，一對節(jié)點(diǎn)在一次波束交會中能夠成功發(fā)現(xiàn)的概率將變得越低。

同時可以看出，本文算法鄰居節(jié)點(diǎn)對在一次交會中成功發(fā)現(xiàn)的概率約為算法1的2倍。這是由于算法1在扇區(qū)交會時未確定節(jié)點(diǎn)收發(fā)狀態(tài)，采用隨機(jī)收發(fā)模式，扇區(qū)交會時收發(fā)狀態(tài)互異的概率期望為0.5；本文算法由于首先確定收發(fā)模式，再進(jìn)行掃描策略設(shè)計，收發(fā)互異的概率為1。

3.3 鄰居發(fā)現(xiàn)時長

對多節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行完整的鄰居發(fā)現(xiàn)所需時長的仿真結(jié)果如圖6所示，其中分別給出了在不同扇區(qū)數(shù)與節(jié)點(diǎn)數(shù)目下網(wǎng)絡(luò)中各個節(jié)點(diǎn)分別完成所有鄰居發(fā)現(xiàn)的平均時長與網(wǎng)絡(luò)完成所有節(jié)點(diǎn)鄰居發(fā)現(xiàn)的總時長。假定節(jié)點(diǎn)間通信距離與扇區(qū)數(shù)K成正比，節(jié)點(diǎn)波束越窄，通信距離越遠(yuǎn)，其可發(fā)現(xiàn)的鄰居節(jié)點(diǎn)越多，扇區(qū)數(shù)為32時通信距離為最大。

(a)鄰居發(fā)現(xiàn)時長隨扇區(qū)數(shù)變化(節(jié)點(diǎn)數(shù)為32)

(b)鄰居發(fā)現(xiàn)時長隨節(jié)點(diǎn)數(shù)變化(扇區(qū)數(shù)為12)圖6 鄰居發(fā)現(xiàn)時長比較

由圖6仿真結(jié)果可見，本文算法在完成全網(wǎng)鄰居發(fā)現(xiàn)的最大時長和各節(jié)點(diǎn)平均時長上，性能均較算法1有較大提升，在不同扇區(qū)數(shù)和不同節(jié)點(diǎn)數(shù)目下，都能將發(fā)現(xiàn)時長縮短一倍左右。這是因為本文提出的方法在波束交會間隔略優(yōu)于算法1的情況下，通過聯(lián)合設(shè)計確定節(jié)點(diǎn)收發(fā)模式，將每次交會時的節(jié)點(diǎn)發(fā)現(xiàn)概率較采用隨機(jī)收發(fā)模式提升了近一倍，仿真結(jié)果與理論推導(dǎo)一致。

4 結(jié)束語

本文針對定向天線無線自組織網(wǎng)絡(luò)的特點(diǎn)，提出一種適用于定向發(fā)送定向接收天線無線移動網(wǎng)絡(luò)，具有確定性搜索時間上界的鄰居發(fā)現(xiàn)算法。該算法通過每個節(jié)點(diǎn)獨(dú)立ID生成的二進(jìn)制編碼來確定節(jié)點(diǎn)收發(fā)模式，同時給出收發(fā)節(jié)點(diǎn)的波束掃描策略，可以實現(xiàn)時隙異步節(jié)點(diǎn)的鄰居發(fā)現(xiàn)。仿真結(jié)果表明，通過設(shè)計特定編碼序列和波束掃描策略，可以實現(xiàn)節(jié)點(diǎn)間確定時間內(nèi)的波束交會，同時通過與收發(fā)模式聯(lián)合設(shè)計，在存在時間異步與相鄰節(jié)點(diǎn)碰撞情況下，較隨機(jī)收發(fā)模式下的鄰居發(fā)現(xiàn)算法在發(fā)現(xiàn)耗時性能上有較大提升。

由于本文算法要求網(wǎng)絡(luò)中各節(jié)點(diǎn)的天線初始配置相同，在各節(jié)點(diǎn)天線波束寬度或最大通信距離不同時，基于二進(jìn)制編碼序列確定的網(wǎng)絡(luò)節(jié)點(diǎn)收發(fā)模式及天線掃描策略有待進(jìn)一步研究。