一種定向無線自組網鄰居發現算法*

胡鄭峰，王 建

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

0 引 言

采用定向天線波束掃描的無線移動自組網技術，空間復用度和信道利用率高，節點間通信距離遠，同時節點間的定向傳輸信道大大降低了通信信號被截獲與干擾的風險，是現代無線移動自組織網絡技術研究的重點[1]。

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

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

1 鄰居發現過程

在本文中，假設無線自組網中的節點具有如下性質：

(2)所有節點采用半雙工方式通信，每個時刻節點只能處于發送或接收中的一個模式。只有當兩個節點處于通信距離內，波束扇區互相指向對方，且一個處于發送模式，另一個處于接收模式，才能進行通信。節點以特定的方式選擇其發送與接收狀態，稱為收發模式。

(3)節點無需GPS等同步設備進行提前時間同步，節點在開機時處于時間異步狀態。

(4)節點采用頻分多址，各節點隨機在M個載頻上選擇一個載頻發送信息。

如圖1(a)所示，A、B兩節點當且僅當其波束相互對準且收發狀態互異時可以成功發現。圖1(b)中兩節點未處于一發一收狀態或圖1(c)中兩節點波束未相互對準都會導致發現失敗。同時，如圖1(d)所示，當同一時隙有兩個發送節點向同一接收節點發送數據包時，數據包會發生碰撞，如果未采用頻分多址或碼分多址等方式進行規避，會使兩個發送節點與接收節點發現失敗。

圖1 節點鄰居發現示意圖

從圖1可以看出，鄰居發現問題的關鍵在于設計節點收發模式與天線波束掃描策略，使其從開機掃描到相互發現的時間更短，同時盡可能減少節點之間的碰撞。

2 基于二進制編碼序列的鄰居發現算法

2.1 算法原理

2.1.1 收發模式編碼序列

規定每個節點配備獨立的二進制編碼，節點隨時間順序按位選擇二進制編碼序列的碼字，一個碼字持續時間為tcode，以此確定每個時隙的節點收發模式：碼字為 1 時，節點進入發送模式，發送鄰居發現信息；編碼為0時，節點處于接收狀態。不同編碼示例對應的收發模式如表1所示。

表1 節點編碼對應收發模式

在節點時間同步情況下，當任意兩節點二進制編碼間的漢明距離大于1時，必定存在一個碼字時間，節點對處于一發一收狀態。

2.1.2 波束掃描策略

在基于二進制編碼序列確定收發模式基礎上，引入天線波束掃描策略。設編碼長度為L，天線扇區數為K，用時隙tslot表示波束指向最短駐留時間切片的長度，一個碼字持續時間tcode為K×K個時隙。當節點進入接收狀態時，接收波束按逆時針方向掃描，每個扇區內駐留K個時隙。當節點進入發送狀態時，發送波束同樣按逆時針掃描，每個扇區內駐留1個時隙。

在一個碼字持續時間內，發送節點與接收節點的波束掃描方式如表2所示。

表2 節點波束掃描方式

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

tsyn=L×K×K×tslot。

(1)

2.2 異步收發編碼設計

在定向收發無線網絡內各節點之間時間異步時，僅兩兩間漢明距離大于1的二進制編碼序列，無法滿足節點間收發模式互異的要求，需要對序列組做出改進。下面對節點間不同異步情況分別進行分析。

2.2.1 旋轉相似性

當節點之間的時鐘差Δt為一個編碼時間長度的整數倍時，即

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

(2)

式中：m為任意整數；K為節點天線扇區數目。引入旋轉相似的定義：設序列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旋轉相似，記為Rsimilar(A,B)=1；若序列組M中任意序列都不旋轉相似，記Rsimilar(M)=0。

當兩節點的收發模式編碼序列旋轉相似時，可能會因為時延導致兩節點的碼字在同一碼字時間內始終相同，無法進入收發互異狀態，從而導致永遠無法相互發現。因此收發編碼序列設計時，要避免序列組內任意兩序列出現旋轉相似，才能作為節點的收發編碼序列。

2.2.2 旋轉互異性

當節點間時鐘相差Δt為時隙長度的整數倍時，即

Δt=m×tslot。

(5)

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

(6)

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

對時鐘異步且編碼長度為L的兩個節點I、J，不妨設節點J在一個收發編碼內進入掃描扇區時間滯后于節點I，令I(tcode_n)、J(tcode_n) 分別表示兩節點原本在碼字時間tcode_n內的碼字。當兩節點序列相互旋轉互異時，?tcode_1,tcode_2∈{0,1,…,L-1}，滿足

(7)

由于兩節點開始進行波束掃描的時間差Δt以I節點時鐘為時間基準，在編碼時間tcode_1內，雖然I節點由于節點間時差導致天線波束掃描扇區的前n個扇區未能與J節點交會，但J節點原本應在tcode_2-tcode碼字時間內掃描的后n個扇區，卻因滯后可以在tcode_2碼字時間內與節點I的前n個扇區交會。當序列滿足該性質時，無論節點間時延相差多少，總能實現掃描扇區的交會，如圖2所示。

圖2 旋轉互異序列扇區交會示意圖

2.2.3 一種二進制編碼序列構建方法

當序列組同時滿足旋轉相似與旋轉互異性時，可以選擇其作為二進制編碼異步鄰居發現的收發編碼序列組。一種滿足兩條性質的序列組的構建方法如下：

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

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

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

2.3 波束掃描策略設計

針對上述收發編碼鄰居發現算法，相應的天線波束掃描策略需進行如下調整：

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

(2)節點每經過長為2L×K2×tslot的收發編碼周期，重新選擇發送波束與接收波束的起始方向。

節點i在時隙tslot_n內扇區方向S(i,t)滿足

(8)

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

采用該序列的節點一個完整的收發編碼周期為2L×K2×tslot，其中，K為節點扇區數目，tslot為時隙長度。在不考慮碰撞情況下，以先開機節點的開機時間為起始，節點間開機時間差為Δt，任意兩節點發現時長的上界tdiscover_max為

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

(9)

2.4 碰撞概率分析

當接收節點同時收到多個發送節點的數據包時會產生沖突，造成接收失敗，稱為波束碰撞。在任意時隙，由于其發送節點初始波束方向隨機，所以相鄰發送節點間波束方向同時指向同一接收節點的概率為1/K，當扇區數越大時，相鄰節點之間波束碰撞的概率越小。

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

(1)其他發送節點位于其他扇區，此時不會發生碰撞，令psector(0)為該情況發生的概率，則有

(10)

(2)其他c-1個節點中有v個節點與發送節點B位于一個扇區內，v≤c-1，令psector(v)為該情況發生的概率，則有

(11)

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

(12)

綜上所述，節點A在一次波束交會中，正確發現的概率p(c,K,M)為

(13)

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

2.5 節點工作流程

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

圖3 節點搜索方式流程圖

3 仿真結果分析

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

表3 主要仿真參數設置

3.1 波束交會時長

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

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

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

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

3.2 單次交會發現成功概率

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

(a)發現概率隨扇區數變化(Nnei=8)

(b)發現概率隨鄰居節點數變化(扇區數為8)圖5 波束交會時發現成功率比較

設節點的鄰居節點數為Nnei，由圖5可以看出，當Nnei固定時，相鄰節點在一次波束交會中發現成功的概率隨扇區數的增大而增大。各發送節點發送波束方向隨機，扇區數的增加會使得其余發送節點波束方向與當前通信節點沖突的概率降低，從而使得發現成功率上升。而當扇區數K固定時，空間中鄰居節點數越大，發生碰撞的概率越大，一對節點在一次波束交會中能夠成功發現的概率將變得越低。

同時可以看出，本文算法鄰居節點對在一次交會中成功發現的概率約為算法1的2倍。這是由于算法1在扇區交會時未確定節點收發狀態，采用隨機收發模式，扇區交會時收發狀態互異的概率期望為0.5；本文算法由于首先確定收發模式，再進行掃描策略設計，收發互異的概率為1。

3.3 鄰居發現時長

對多節點網絡進行完整的鄰居發現所需時長的仿真結果如圖6所示，其中分別給出了在不同扇區數與節點數目下網絡中各個節點分別完成所有鄰居發現的平均時長與網絡完成所有節點鄰居發現的總時長。假定節點間通信距離與扇區數K成正比，節點波束越窄，通信距離越遠，其可發現的鄰居節點越多，扇區數為32時通信距離為最大。

(a)鄰居發現時長隨扇區數變化(節點數為32)

(b)鄰居發現時長隨節點數變化(扇區數為12)圖6 鄰居發現時長比較

由圖6仿真結果可見，本文算法在完成全網鄰居發現的最大時長和各節點平均時長上，性能均較算法1有較大提升，在不同扇區數和不同節點數目下，都能將發現時長縮短一倍左右。這是因為本文提出的方法在波束交會間隔略優于算法1的情況下，通過聯合設計確定節點收發模式，將每次交會時的節點發現概率較采用隨機收發模式提升了近一倍，仿真結果與理論推導一致。

4 結束語

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

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