基于定向天線無線自組網的快速隨機鄰居發現算法

劉巖　劉成朋　楊健

摘要：為了減少無線自組網的組網所需時間，提升隨機發現算法鄰居發現的概率，提出了一種基于定向天線的隨機鄰居發現算法。根據相控陣天線能夠自由切換寬波束和窄波束的特點，發揮寬波束搜索能力強、窄波束傳輸能力強的優勢，使用寬波束和窄波束來進行鄰居發現，并結合碰撞重傳機制和鄰居節點輔助發現機制，對碰撞重傳的最優競爭窗口值進行了計算。仿真實驗表明，算法降低了鄰居再發現的時間開銷，增加了鄰居的發現概率，滿足快速組網和高速通信的需求。在不同節點數下，鄰居發現所需時隙數均少于基于碰撞避免的隨機發現算法，具備更快的鄰居發現速度。所提算法可為無線自組網提供一種高效的鄰居發現方案，提高無線自組織網絡性能，在飛行器組網等應用場景中具有一定的實用價值。

關鍵詞：無線通信技術;無線自組網;定向天線;鄰居發現;隨機發現;波束寬度

中圖分類號：TN929.5文獻標識碼：A

DOI： 10.7535/hbgykj.2022yx02002

Fast random neighbor discovery algorithm based onwireless Ad hoc network of directional antennas

LIU Yan，LIU Chengpeng，YANG Jian

（The 54th Research Institution of CETC，Shijiazhuang，Hebei 050081，China）

Abstract：In order to reduce the time required for wireless Ad hoc network and improve the probability of neighbor discovery in random discovery algorithm，a fast random neighbor discovery algorithm based on directional antennas wireless Ad hoc network was proposedBased on the characteristics of the free switch between wide and narrow beams of phased array antenna，the proposed algorithm gave full play to the advantages of strong wide beam search ability and narrow beam transmission ability，used wide beam and narrow beam for neighbor discovery，and combined the collision retransmission mechanism and neighbor node auxiliary discovery mechanism to calculate the optimal competition window value of the collision retransmissionIt reduced the time cost of the neighbor rediscoveryThe simulation experiment shows that the algorithm increased the probability of neighbor discovery，and met the needs of fast networking and high-speed communication，and under different numbers of nodes，the number of time slots required for neighbor discovery of the proposed algorithm is less than that of the random discovery algorithm based on collision avoidance，and has a faster neighbor discovery speedThis design method can provide an efficient neighbor discovery scheme for wireless Ad hoc network，improve the performance of wireless Ad hoc network，and has certain practical value in application scenarios such as aircraft network

Keywords： wireless communication technology;wireless Ad hoc network;directional antenna;neighbor discovery;random discovery;beam width

隨著無線通信技術的高速發展，無線自組網由于具備自組織、抗毀性強和無中心等特點，引起了研究者們的廣泛關注[1]，其應用范圍也得到了擴展。目前傳統的無線自組織網絡大多采用全向天線模式[2]，該模式具有輻射無方向性的特點，存在節點間傳輸距離受限、信息易截獲和信道利用率低[3]等問題。為解決上述問題，研究人員將定向天線引入無線自組網中[4]。定向天線在特定方向具有很高的收發增益，而在其他方向上增益很小，故具備傳輸距離遠、抗截獲能力強和信道利用率高等優點[5-7]。然而，定向天線的引入使鄰居發現變得較為困難，鄰居互相發現必須滿足以下3個條件：1）通信的雙方必須滿足同一時間進行信息交互;2）同一時間通信雙方的波束必須彼此指向對方;3）2個節點的距離應該小于此場景下的最遠傳輸距離。目前，鄰居發現算法主要分為確定型發現算法[8-10]和隨機型發現算法[11-14]兩類。確定型發現算法協調了所有節點的發送和接收方向，增加了檢測概率，但同時增加了碰撞概率;相反，隨機型發現算法中收發狀態隨機和方向隨機的方案降低了檢測概率和碰撞概率。B43F9E47-26B5-44BC-8274-6197D0BDF388

近年來，為了提升鄰居發現算法的性能，鄰居輔助發現方法被許多研究者關注。文獻[15]通過引入DSN的鄰居協作發現機制，使節點在不同扇區交換輪詢消息，間接發現鄰居。然而，該算法只能保證在短時間內發現90%的鄰居。文獻[16]采用慢掃描模式，以較低的延遲將鄰居發現概率提高至接近100%。文獻[17]在相鄰節點之間尋找鄰居集合的發現交集，利用公共鄰居來提高發現效率，加快了鄰居發現的進程。

消息碰撞問題是影響鄰居發現速度的因素之一。當網絡中的節點數較少時，碰撞幾乎沒有出現，若采用節點以一定概率保持靜默的策略來降低碰撞概率，則會降低發現概率，反而影響發現速度。隨著網絡內節點數的增加，碰撞問題會隨之增加，合理的碰撞避免機制會降低碰撞概率，合理的碰撞解決機制會快速再發現，相比重新發現耗時短，從而加快發現速度。為了解決消息碰撞問題，文獻[18]提出SBA-PI算法引入了靜默狀態，使節點具備發送、接收以及靜默3種狀態，這一操作通過碰撞避免機制減少沖突。此外，文獻[19]在隨機發現的基礎上，引入選擇性回復機制，節點一次握手成功后，以概率ρ進行回復，減少了二次握手中的碰撞沖突，但是在碰撞較少的情況下，降低了鄰居發現的概率。文獻[20]通過隨機選擇發送控制消息的微時隙，有效避免了碰撞沖突的產生。以上算法都通過避免碰撞的方式來提升鄰居發現速度，但這會降低鄰居發現的概率。因此，文獻[21]在經典的隨機發現算法[22]的基礎上，結合鄰居輔助發現方法，提出了碰撞重傳機制來解決碰撞問題。[JP2]該方法在碰撞后重新預約時隙進行重傳，改善了碰撞帶來的影響。在隨機算法中，相比于碰撞避免的方式，碰撞解決機制能避免浪費此次波束對準的機會，快速再發現，從而加快發現速度。

然而，在實際應用中，定向天線的加入對無線自組網提出了快速組網和高速通信的需求。而普通的隨機發現算法已無法滿足性能要求，采用窄波束搜索、窄波束監聽的方式，導致鄰居發現概率較低，發現時間較長。因此本文提出一種基于定向天線無線自組網的快速隨機鄰居發現算法，根據相控陣天線能夠自由切換寬波束和窄波束的特點，發揮寬波束搜索能力強、窄波束傳輸能力強的優勢，采用窄波束搜索、寬波束監聽策略進行鄰居發現，增加鄰居的發現概率，滿足快速組網和高速通信的需求。

1網絡模型描述

假設每個節點都配備一副可以調整為寬波束和窄波束的一維相控陣天線，其中發送節點窄波束個數為K₁，接收節點寬波束個數為K₂。此外，節點還具有以下特點。

1）網絡節點總數為N，每個節點都有唯一的ID標識。

2）一個鄰居發現時隙可以分為2個子時隙，在每個子時隙中，節點可以完成握手的過程。鄰居發現時隙劃分如圖1所示。

3）假設2個具有定向天線的節點可以互相通信，需要一個節點處于接收狀態，另一個節點處于發射狀態，并且它們的收發波束相互覆蓋。因此，2個節點必須要同時指向其波束，并且發送和接收狀態相反。

4）如果有2個或者2個以上的波束到達一個節點的接收波束上，則會發生消息碰撞，碰撞之后，節點不會收到數據包。在子時隙1，A節點進行發送，B節點進行接收。在子時隙2，2個節點收發狀態相反，通信成功的案例如圖2所示。

當一個節點同時從其給定波束中的2個或多個鄰居接收發現數據包時，就會發生碰撞，碰撞案例如圖3所示。在這種情況下，節點無法解析信息，因此認為數據包丟失了。每個節點可以通過一個簡單的能量探測器區分空時隙和一個碰撞的時隙。

2基于定向天線無線自組網的快速隨機鄰居發現算法

2.1改進思路

為了在遠距離的條件下快速地發現鄰居，建立網絡，達到數據高速通信的目的。所提算法使用定向天線，采用兩次握手的工作機制完成鄰居發現，握手過程如圖4所示。一次握手階段發送節點使用窄波束掃描，接收節點使用寬波束監聽，二次握手階段接收節點使用窄波束回復，發送節點使用窄波束監聽，增大節點發現概率，并結合碰撞重傳機制和鄰居輔助發現機制，加快鄰居發現進程，滿足快速發現鄰居的需求。

相較于傳統隨機發現算法采用窄波束相互掃描的方式。所提算法使用窄波束掃描，寬波束監聽的策略，并采用低速率模式進行鄰居發現以提高可靠性，增加了接收靈敏度，如式（1）和式（2）所示，能夠提高鄰居發現概率，縮短鄰居發現的時間。

發射功率-接收靈敏度=LOS， （1）

S=10lg（kTB）+NF+SNR， （2）

式中：S代表接收靈敏度，接收靈敏度越小，則接收機的接收性能越好;k代表玻爾茲曼常數，T代表絕對溫度，B代表信號帶寬，kTB整體表示帶寬范圍內的熱噪聲功率;NF代表系統噪聲系數;SNR代表解調所需信噪比。由此可知，選擇低速率通信，則接收靈敏度越小，便于發現鄰居。

2.2工作流程

本文算法主要包括參數初始化、碰撞解決階段和鄰居輔助發現階段3個過程。其中參數初始化中主要完成節點收發狀態和天線方向的選取，碰撞解決階段完成碰撞節點的信息重傳過程，鄰居輔助發現階段根據收到的信息包，判斷是否有自身未含有的鄰居信息，間接進行鄰居發現，加快鄰居發現進程。綜上，所提算法的工作流程如圖5所示。

2.2.1算法步驟

步驟1：生成N個處于隨機位置的初始節點，所有節點已通過外部授時或自帶銣鐘進行時間同步。

步驟2：每個節點以一定概率成為發送節點或接收節點。1）成為發送節點概率p_t，在子時隙1向隨機方向用窄波束搜索，[JP2]在子時隙2向相同的方向用窄波束監聽。2）成為接收節點的概率為1-p_t，在子時隙1向隨機方向用寬波束監聽。如果子時隙1成功收到信息包，則在子時隙2判斷來時信息的方向，切換窄波束進行回復，否則需判斷是碰撞還是未收到信息包。若發生碰撞則進入碰撞解決機制，否則將在子時隙2保持靜默狀態，保存節點能量。B43F9E47-26B5-44BC-8274-6197D0BDF388

步驟3：若節點間在鄰居發現階段完成兩次握手，則2個節點成為鄰居，并且收到對方的鄰居列表。例如，節點A和B互為鄰居，節點B和C互為鄰居，A和C通過B節點提供的鄰居列表，進行間接鄰居發現。

步驟4：當發現網絡中全部節點間所有鏈路時，鄰居發現成功。

對參數初始化、碰撞解決階段和鄰居輔助發現階段進行詳細介紹。

2.2.2節點參數初始化

節點參數包括節點收發狀態和天線方向，若定義發送節點窄波束個數為K₁，接收節點窄波束個數為K₂。具體初始化步驟如下。

1）當節點啟動后，首先根據當前的時隙號搜索退避列表，判斷是否要進行退避。

2）如果不需要退避，則開始按照算法隨機選擇節點的收發狀態和天線方向。

3）如果需要退避則按照退避列表選擇節點的收發狀態和天線方向。

節點收發狀態的選取需要對發送概率進行研究。在每個時隙開始時，一跳鄰域中的每個節點分別以p_t和1-p_t的概率隨機選擇發送或者接收。如果節點發送概率p_t設置過高，將導致較多的碰撞，減慢鄰居發現速度。相反，如果節點發送概率p_t設置過低，將導致信道利用率不足，從而降低鄰居發現效率。因此，求解最優的發送概率才能獲得最大的鄰居發現概率。為了評估鄰居發現算法的性能，這里計算了節點i和節點j在給定時隙t中發現彼此的概率，用p_s表示。對于鄰居發現過程，節點應該在2個子時隙中成功傳輸。

假設節點i作為發送節點，節點j作為接收節點，二者互相發現彼此，需要滿足3個條件。

1）對于節點i，在子時隙1，節點i向節點j的方向發送消息的概率為A=（1/K₁）p_t，在子時隙2，節點j回復節點i的概率為1。

2）對于節點j，在子時隙1，節點j在節點i的方向接收消息的概率為B=（1/K₂）pt，在子時隙2，節點i指向原來發送方向保持接收的概率為1。

3）對于任意一個其他節點，假如此節點不干擾到節點i和節點j正常通信的概率可描述為C=p_t（1-1/K₁K₂）+（1-p_t）[1-（p_t/K₁²）]，第1部分表示在子時隙1，其他節點沒有選擇向節點j接收方向發送的概率，在子時隙2，節點不會再發送。第2部分表示在子時隙1，其他節點保持接收狀態，在子時隙2，沒有向節點i的方向回復信息的概率。

結合上述3點，同理可得，節點j作為發送節點，節點i作為接收節點的概率，故節點i和節點j在時隙t成功發現彼此的概率如式（3）：

p_s=2ABC^n-1， （3）

式中n-1為節點的鄰居節點個數。

2.2.3碰撞解決階段

碰撞解決流程如圖6所示，假定一跳的鄰域內有4個節點A，B，C，D，在子時隙1中，節點A，C和D處于發送模式，而節點B處于接收模式。在這種情況下，節點B可能接收到多個發現包，導致沖突，在子時隙2中，節點B使用相同的波束傳輸碰撞確認信息，4個節點進入碰撞解決階段[20]。

節點B一直保持接收模式，直到它成功接收到2個信息包為止，代表重傳成功。而節點A，C，D將在接下來的幾個時隙計劃重傳，在競爭窗口CW中隨機選擇一個重傳時隙，其他時隙節點可以進行發送或者接收。但是如果節點A進入了碰撞解決機制，那么它在接收到B的成功回復之前，不會再對B計劃新的重傳。如果多個節點選擇同一個時隙進行重傳，那么將根據競爭窗口值選取新的時隙進行重傳，保證碰撞解決。

在碰撞解決機制中，為了降低多個節點選取同一時隙進行重傳的概率，避免鄰居發現包再次碰撞，需要定義恰好一個節點選擇一個給定時隙進行重傳的概率，找到最優的競爭窗口值CW，使成功重傳的概率取最大值。

定義i個節點選擇同一個時隙進行重傳的概率為p_s（i）。每個節點周圍有n個鄰居節點，其中恰好有i個節點需要進行重傳，每個節點選擇重傳時隙的概率為1/CW，此時模型可以視為二項式分布n，1CW，可以得出：

綜上，所提算法在碰撞解決階段設置競爭窗口大小為n時最優。

2.2.4鄰居輔助發現階段

網絡時幀分為鄰居發現階段、管控階段及數據傳輸3個階段。鄰居發現階段進行互相發現，鄰居發現包攜帶自身鄰居信息，發現成功后將得知潛在的鄰居;管控階段完成所有節點的波束跟蹤，業務請求和時隙分配功能，兩兩節點彼此對準一次。若節點A和B在鄰居發現階段成為鄰居，則互相收到對方的鄰居發現包，記錄潛在的鄰居，將在管控階段進行對準，包括與潛在鄰居的對準，此為鄰居輔助發現過程[17]。節點拓撲關系如圖7所示。

3仿真結果分析

為了驗證所提算法的有效性，在Matlab平臺上進行仿真驗證。實驗中，在5 000×5 000的區域內隨機生成節點，本算法兩節點間的最大傳輸距離設置為1 000，以發現全部節點間所有鏈路所需時隙數為指標。仿真實驗結果表明，相較于文獻[21]中的算法以及經典的隨機算法，所提算法具有更高的鄰居發現概率，且發現全部鄰居所用時隙數更少，鄰居發現的效率更高。

3.1最佳發送概率選取的仿真及分析

由22節的式（3）可得，當節點發送概率p_t為05時，發現概率p_s取最大值。通過實驗對以上結論進行驗證，此處設置窄波束個數K₁=12，寬波束個數K₂=4，節點個數N分別設置為16，32，48以代表低密度、中密度、高密度3種情況。每個概率p_t重復10次實驗取p_s的平均值，仿真結果如圖8和圖9所示。其中圖8展示了發現概率p_s隨發送概率的變化圖，圖9展示了發送概率p_t對總時隙數的影響。B43F9E47-26B5-44BC-8274-6197D0BDF388

由圖8可知，在低密度、中密度、高密度3種情況下，當發送概率p_t取05時，發現概率p_s最大，可以達到最佳的發現效果，與式（3）推導結論相符。此外，由圖9可知，當p_t取05時，鄰居發現所需總時隙數slots最少，該趨勢與理論推導相符。

3.2算法性能對比

為了客觀驗證所提算法的有效性，本節將所提算法進行仿真，并與文獻[21]中的算法及經典的隨機算法進行對比，使用發現全部節點間所有鏈路所需時隙數slots作為性能指標。所提算法設置窄波束個數K₁=12，寬波束個數K₂=4，文獻[21]中的算法及經典的隨機算法，設置發節點和收節點窄波束個數均為K=12。鄰居發現時間性能進行對比如圖10所示。其中橫坐標表示節點個數N，縱坐標表示鄰居發現所需總時隙數slots。

由圖10可知，所提算法發現所有節點所需的時間均小于文獻[21]中隨機算法及經典的隨機算法所需時間，并且隨著節點數的增多，所提算法與其他算法相比，增長的時間較少，具備更優的性能。為了進一步考察所提算法的性能，將節點個數N增加到100個，如圖11所示。

由圖11可知，隨著節點個數的增大，所提算法完成鄰居發現所需時隙數為線性增長，當網絡節點數為100時，所需時隙數僅約為450個。

4結語

本文研究了基于定向天線的無線自組網鄰居發現問題，為了提升鄰居發現的效率，根據相控陣天線能夠自由切換寬波束和窄波束的特點，發揮寬波束搜索能力強，窄波束傳輸能力強的優勢，使用窄波束搜索，寬波束接收來進行鄰居發現，增加了鄰居的發現概率，滿足快速組網和高速通信的需求。仿真實驗表明，所提算法能計算出節點的最佳發送概率和碰撞重傳的最佳窗口值，從而取得最優的鄰居發現效果，加快鄰居發現速度，并且隨著節點數增加，所提算法性能更優。

鄰居發現階段使用低速率模式通信，實現鄰居發現和前期握手，這導致鄰居發現階段的信息傳輸速率受到了一定程度的限制。因此，如何在鄰居發現階段取得較好的發現效果，同時達到較高的鄰居傳輸速率，是未來可進一步研究的方向。

參考文獻/References：

[1]邵瑋璐移動自組網中混合接入協議的研究[D]上海：上海師范大學，2020SHAO WeiluResearch on Hybrid Access Protocol in Mobile Ad Hoc Network[D]Shanghai：Shanghai Normal University，2020.

[2]NICHOLS?RDirectional network discovery performance[C]//34th IEEE Sarnoff Symposium，PrincetonNJ：IEEE，2011：1-5

[3]李麗，鄭博文，劉麗哲一種適于波束切換移動自組網的鄰居發現改進算法[J].無線電通信技術，2020，46（3）：286-292LI Li，ZHENG Bowen，LIU LizheImproved neighbor discovery algorithm for beam switching mobile ad hoc network[J].Radio Communications Technology，2020，46（3）：286-292.

[4]伍蕓荻無人機通信系統中信息和能量傳輸優化研究[D]合肥：中國科學技術大學，2019WU YundiResearch on Information and Energy Transmission Optimization in UAV Communication System[D]Hefei：University of Science and Technology of China，2019.

[5]楊欣無線自組網MAC層協議及跨層協同技術研究[D]西安：西北工業大學，2018YANG XinResearch on Medium Access Control Protocol and Cross-Layer Cooperation Technology of Wireless Ad Hoc Networks[D]Xi′an：Northwestern Polytechnical University，2018.

[6]梁志公無線自組網定向天線鄰居發現技術研究[D]成都：電子科技大學，2020LIANG ZhigongResearch on Neighbor Discovery Technology for Directional Antenna Enabled Wireless Ad Hoc Networks[D]Chengdu：University of Electronic Science and Technology of China，2020.

[7]徐大鳳無線Ad hoc網絡定向MAC協議研究[D]成都：電子科技大學，2017XU DafengResearch on Directional MAC Protocol for Ad Hoc Networks[D]Chengdu：University of Electronic Science and Technology of China，2017.

[8]FELEMBAN?E，MURAWSKI R，EKICI E，et alSAND：Sectored-antennaneighbor discovery protocol for wireless networks[C]//2010 7th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks （SECON）Boston：IEEE，2010：1-9.B43F9E47-26B5-44BC-8274-6197D0BDF388

[9]GAMMARANO?N，SCHANDY J，STEINFELD LQ-SAND：A quick neighbor discovery protocol for wireless networks with sectored antennas[C]//2018 Ninth Argentine Symposium and Conference on Embedded SystemsCordoba：IEEE，2018：19-24.

[10]歐陽峰，劉強，郝琦，等基于定向天線的移動自組網技術研究綜述[J].電視技術，2017，41（sup1）：148-153OUYANG Feng，LIU Qiang，HAO Qi，et alResearch summary of MANETs based on directional antenna[J].Video Engineering，2017，41（sup1）：148-153.

[11]SUDEVAN?S，TOWSLEY D，GOECKEL D，et alNeighbor discovery in wireless networks and the coupon collector′s problem[C]//Proceedings of the 15th Annual International Conference on Mobile Computing and Networking[Sl]：[sn]，2009：181-192.

[12]TIAN?Feng，LIU Bo，CAI Hao，et alPractical asynchronous neighbor discovery in Ad hoc networks with directional antennas[J].IEEE Transactions on Vehicular Technology，2016，65（5）：3614-3627.

[13]DU?Jingzhe，KRANAKIS E，PONCE O M，et alNeighbor discovery?in a sensor network with directional antennae[J]Ad-Hoc?& Sensor Wireless Networks，2016，30（3/4）：261-286.

[14]MCGLYNN?M J，BORBASH S ABirthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks[C]//Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing[Sl]：[sn]，2001：137-145.

[15]NUR?F N，SHARMIN S，HABIB M A，et alCollaborative neighbor discovery in directional wireless sensor networks[C]//2016 IEEE Region 10 Conference （TENCON）Singapore：IEEE，2016：1097-1100.

[16]SOOD?N，NAGARAJU S，V S，et alCollaborative neighbor discovery with slow scan for directional sensor networks[C]//2018 28th International Telecommunication Networks and Applications?Conference （ITNAC）Sydney：IEEE，2018：1-3.

[17]洪亮，羅鵬濤，燕熊，等一種基于定向天線的蜂群組網鄰居發現算法[J].西北工業大學學報，2020，38（1）：191-198HONG Liang，LUO Pengtao，YAN Xiong，et alA neighbor discovery algorithm for UAV networking based on directional antennas[J].Journal of Northwestern Polytechnical University，2020，38（1）：191-198.

[18]LIU?Bo，RONG Bo，HU R Q，et alNeighbor discovery algorithms in directional antenna based synchronous and asynchronous wireless ad hoc networks[J].IEEE Wireless Communications，2013，20（6）：106-112.

[19]CAI?Hao，WOLF TOn 2-way neighbor discovery in wireless networks with directional antennas[C]//2015 IEEE Conference on Computer Communications （INFOCOM）Hong Kong：IEEE，2015：702-710.

[20]景中源，曾浩洋，李大雙，等定向Ad hoc網絡中一種帶沖突避免的鄰居發現算法[J].通信技術，2015，48（5）：582-588JING Zhongyuan，ZENG Haoyang，LI Dashuang，et alA neighbor discovery algorithm with collision avoidance in Ad hoc networks using directional antennas[J].Communications Techno-logy，2015，48（5）：582-588.

[21]el?KHAMLICHI B，NGUYEN D H N，el ABBADI J，et alCollision-aware neighbor discovery with directional antennas[C]//2018 International Conference on Computing，Networking and Communications （ICNC）Maui：IEEE，2018：220-225.

[22]ZHANG?Zhensheng，LI BoNeighbor discovery in mobile Ad hoc self-configuring networks with directional antennas：Algorithms and comparisons[J].IEEE Transactions on Wireless Communications，2008，7（5）：1540-1549..B43F9E47-26B5-44BC-8274-6197D0BDF388