定向Ad hoc網絡中一種帶沖突避免的鄰居發現算法*

2015-02-24 03:23:04景中源曾浩洋李大雙毛建兵

通信技術 2015年5期

景中源，曾浩洋，李大雙，毛建兵

(中國電子科技集團公司第三十研究所，四川成都 610041)

景中源，曾浩洋，李大雙，毛建兵

(中國電子科技集團公司第三十研究所，四川成都 610041)

定向天線應用于ad hoc網絡，一方面能顯著提升網絡性能，另一方面也需要新的MAC和路由協議來控制定向天線系統。鄰居發現算法作為其中最重要的協議之一，是定向ad hoc網絡組網的基礎和前提，針對現有文獻中提出的各種鄰居發現算法大多沒有考慮同一定向波束扇區內存在多個節點時的沖突情況，提出一種帶沖突避免的定向鄰居發現算法DAND/CA。DAND/CA通過隨機選擇發送控制消息占用的微時隙，能有效避免碰撞沖突的發生。仿真結果表明，提出的DAND/CA算法在鄰居發現時間和成功率等方面明顯優于現有算法。

定向天線；Ad hoc網絡；鄰居發現；沖突避免

0 引言

多跳無線自組織網絡中，節點鄰域信息在路由、分群和媒介訪問控制等方面起著至關重要的作用[1]。基于全向天線的ad hoc網絡中，節點傳輸范圍內的所有節點能很容易地偵聽到其發送的鄰居請求廣播消息，鄰居發現過程相對簡單，不需要專門為其設計相應的通信協議，而在基于定向天線的ad hoc網絡中，定向天線和定向通信自身特點使鄰居發現變得較為困難[2]：

(1)定向天線將射頻信號能量集中在特定的窄波束內進行輻射，只能覆蓋較小的局部空間范圍，必須多次重復調度切換定向波束才能覆蓋整個空間方位角，即定向天線難于實現廣播通信。

(2)節點必須在正確的時間、將正確的波束方向指向對方，且彼此收發模式相反，才能有效通信，即定向天線發生有效通信的條件十分苛刻。

本文首先介紹了定向鄰居發現原理，然后結合定向鄰居發現的特點，針對現有鄰居發現算法大多沒有考慮在同一個波束內同時存在多個節點時的沖突問題，提出一種基于TDMA協議的帶沖突避免的定向鄰居發現算法DAND/CA(Directional Antenna Neighbor Discovery with Collision Avoidance algorithm)，通過劃分微時隙和隨機選擇節點發送鄰居發現消息所占用的微時隙，允許同一波束扇區內的多個鄰居節點在不同微時隙內獨立完成鄰居發現過程，從而有效地避免了鄰居發現過程中的消息碰撞沖突，仿真結果顯示DAND/CA算法能有效縮短鄰居發現時間并提高鄰居發現成功率。

1 鄰居發現原理

鄰居發現是指節點開機后，在沒有鄰節點任何先驗信息的條件下，通過基于一定的互盲或自盲算法協議迅速發現其1跳范圍內的所有其他節點(同時被其他節點所發現)，并建立基本通信連接的過程[3]。

在全向天線系統中，節點通過廣播鄰居請求分組搜集鄰域信息，其一跳覆蓋范圍內的所有處于接收狀態的鄰居節點必定都能收到該廣播信號。在定向天線系統中，由于定向窄波束只能覆蓋空間局部區域，上述“必定”的條件并不存在，同時節點之間能有效通信的條件如圖1所示，即需要滿足發送和接收必須同時對準時隙和方向。

圖1 定向鄰居節點有效通信示例

因此相比于全向天線，在定向天線系統中解決鄰居發現問題時需要考慮更多的內容，具體包括天線模式選擇算法設計、多波束切換天線掃描圖案設計以及控制消息交互機制設計等。

其中，天線模式指節點天線的工作狀態，包括發送和接收2種。若天線工作狀態為發送，則在特定的空間波束方向上定向發送鄰居請求消息；若為接收，則在特定的空間波束方向上偵聽信道，等待接收鄰居請求消息。

在基于多波束切換天線的Ad hoc網絡中，由于定向天線難于實現廣播通信，當節點需要對多個節點廣播數據消息時，須按照某種調度順序對整個空間區域進行“掃描”。掃描過程，即多波束天線不斷切換其當前所使用定向波束扇區的過程，其中定向波束切換的順序和方法稱為定向天線的掃描圖案。

應當注意，天線模式和天線掃描圖案既相互關聯又相互約束，二者共同決定某次鄰居發現過程成功的統計特性，并直接影響鄰居發現過程的性能指標。

2 DAND/CA算法描述

2.1 系統模型和節點假設

圖2 理想的K扇區多波束切換天線

多波束切換天線通過選擇不同的天線單元就能實現波束扇區的切換，是定向天線中最簡單且最易于實現的一種，DAND/CA算法相關結論就是基于多波束切換天線得出的，但應當注意它同樣可以很容易地擴展到其他類型的定向天線系統中去。

節點還應當滿足以下假設條件：

(1)通信模式為半雙工，任何時刻節點只能處于收發工作模式中的一種，但能在傳輸與接收模式之間快速切換。

(2)任何時刻，節點最多只能在一個定向波束扇區內進行消息分組發送或接收，但能在不同扇區之間快速地切換。

(3)時間是基于時隙劃分的，所有節點通過GPS或北斗系統能夠達到精確的時鐘同步。

(4)傳輸功率固定不變，即所有節點定向天線增益完全相同，避免了天線增益不一致引發的通信距離不對稱等問題。

(5)同時收到2個及2個以上鄰居節點的消息分組時，將發生碰撞沖突而無法正確接收和解析消息分組[4]。

2.2 信道時幀結構

DAND/CA算法設計的TDMA時幀循環結構如圖3所示，將信道資源劃分為連續的、周期性重復的TDMA幀，每幀由鄰居發現子幀和業務數據傳輸子幀組成，其中業務數據傳輸子幀包含M個數據時隙，鄰居發現子幀包含探測、響應和確認3個階段，每個階段由N個持續時間更短的引導微時隙組成；每個時隙的持續時間為T，每個引導微時隙的持續時間為T/N。

圖3 TDMA幀結構示意

在周期性的TDMA幀結構內，與鄰居發現過程相關的各類時隙定義如下：

鄰居探測引導(NiDB，Neighbor Detect Bootstrap)時隙：為鄰居發現過程中隨機分派給各發送模式節點使用的時隙。鄰域探測引導時隙用于主動發起鄰居發現過程的節點在特定的波束扇區內發送鄰居請求消息分組，分組信息包含有節點的ID編號、1跳鄰域信息以及節點HRFS時隙分配信息。每幀中鄰域探測引導時隙NiDB配置數量為N。

鄰居應答引導(NiRB，Neighbor Reply Bootstrap)時隙：隨機分派給成功接收鄰居請求消息分組的節點，用于傳輸鄰居響應和HRFS時隙分配所需的信息。每幀中鄰居應答引導時隙NiRB配置數量為N。

鄰居確認引導(NiAB，Neighbor Acknowledge Bootstrap)時隙：為分派給成功接收鄰居響應消息分組節點使用的時隙，其分配情況與NiDB完全一致，用于傳輸鄰居發現確認及HRFS時隙分配結果等信息。每幀中鄰居響應引導時隙NiAB配置數量為N。

2.3 天線收發模式選擇

為了消除孤立節點和近在咫尺的節點無法發現等問題，DAND/CA采用基于節點ID二進制編碼的方法確定收發模式，將每個節點全網唯一的ID編號j和網絡節點數量N作為靜態參數在節點開機時進行自動加注，并根據圖4所示天線收發模式算法流程決定當前時刻天線是處于發送模式或偵聽模式，其中當前掃描周期數i計算公式為：

i=?Frame_sequence/K/w」

(1)

式中，Frame_sequence為信道幀序號，K為定向多波束天線扇區數，w表示在每個波束扇區內駐留的信道幀數。應當注意，1輪掃描周期內節點天線的收發模式將保持不變，并在每個波束扇區內重復執行w次收發操作后，順序切換至下一個波束扇區，當遍歷完所有的波束扇區后本輪掃描周期結束。

圖4 DAND/CA天線模式選擇流程

2.4 天線掃描圖案

確定節點工作模式后，DAND/CA算法將根據當前天線工作模式進行天線掃描圖案的設計。第i輪天線掃描周期開始時，主動發送模式的節點將在編號為i的波束扇區內定向發送鄰居請求消息，并在該波束扇區內駐留w個信道幀，即重復執行w次發送操作，然后節點順時針切換至編號為i+1的定向波束扇區內重復執行上述過程。

第i輪天線掃描周期開始時，被動偵聽節點將在編號為[(i+K/2) %K]的定向波束扇區內定向接收鄰居請求消息，其中K為多波束天線扇區數，節點在該波束扇區內駐留w個信道幀，即重復執行w次接收操作，然后節點切換至編號為[(i+1+K/2)%K]的定向波束扇區內重復執行上述過程。

DAND/CA算法中的天線掃描圖案，可以確保在具有相同的方向基準前提下，處于收發模式的鄰居節點盡可能將當前激活波束扇區互相指向對方，從而滿足定向節點有效通信的條件。

2.5 Hello-Reply-Ack 3步握手機制

DAND/CA算法采用一種3步握手機制確保節點之間發現的所有通信鏈路均為雙向鏈路[5]。下面以第i輪天線掃描周期過程為例，詳細介紹DAND/CA算法的3步握手過程，并對其鄰居發現過程中的消息碰撞沖突避免機制進行重點分析。

圖5為鄰居發現過程中同一個波束扇區內存在多個鄰居節點時的一種可能的沖突情形。圖中節點A、B為發送模式，其當前激活的波束扇區覆蓋范圍內有節點C、D、E和F為偵聽模式，且節點A、B和節點C、D、E、F的波束相互指向對方，即節點A、節點B和節點C、D、E之間滿足定向通信的條件，當節點A、節點B同時發送消息時，將在所有偵聽節點處發生消息碰撞沖突，導致鄰居發現過程失敗。現有的定向鄰居發現算法，如PRA[6]、SBA[6]等，沒有考慮圖5的沖突情形，因此它們僅適用于節點較少的稀疏網絡，當網絡內鄰居節點數增加時算法性能會明顯下降。

圖5 沖突情形：1個波束扇區內存在多個鄰居節點

DAND/CA算法，在充分考慮圖5所示沖突情形對鄰居發現過程影響的基礎上，將信道幀結構內的鄰居發現子幀劃分多個持續時間更短的引導微時隙，節點通過隨機選擇發送鄰居交互信息所占用的微時隙，允許同一波束扇區內的多個鄰居節點在不同的微時隙內獨立完成鄰居發現過程，從而有效地避免了鄰居發現過程中的消息碰撞沖突。

DAND/CA算法中實現鄰域信息交互、完成預約協商并初步建立定向通信鏈路的3步握手機制描述如下，為了便于描述，令參數w=3。

(1)鄰居發現階段1

鄰居發現過程的第1階段在信道幀的NiDB時隙內進行。主動發送模式節點A、B，分別從N個NiDB中隨機選取1個時隙，用于定向廣播發送鄰居請求消息hello_request；偵聽節點C、D、E和F在所有的NiDB時隙內處于信道監聽狀態，等待接收hello_request消息。沖突避免見圖6。

圖6 DAND/CA算法hello_request消息沖突避免

圖6中，節點A、B在第1個信道幀內，均隨機選擇在第1個NiDB時隙定向發送鄰居請求消息hello_request，將在鄰居節點C、D、E和F處發生消息沖突碰撞，宣告第1個信道幀內的鄰居發現過程失敗；在第2個信道幀內，節點A、節點B分別隨機選擇在第0個、第2個NiDB時隙內發送hello_request消息，可成功被幀聽節點接受并解析，而進入鄰居發現過程的第2階段。成功完成鄰居發現過程第1階段的節點A、節點B，將不再參與后續信道幀NiDB時隙的競爭使用，能進一步避免可能存在的消息沖突碰撞，并增加其他發送節點成功發送hello_request消息的概率。

(2)鄰居發現階段2

鄰居發現過程的第2階段在信道幀的NiRB時隙內進行。被動偵聽模式節點C、D、E和F，如果在NiDB時隙內成功接收并解析來自節點A、B的鄰居請求消息hello_request，則將從鄰居發現子幀的N個NiRB時隙中隨機選取1個時隙，用于定向廣播發送鄰居應答消息hello_reply；節點A、節點B在所有的NiRB時隙內處于信道監聽狀態，等待接收hello_reply消息。該過程見圖7。

圖7 DAND/CA算法reply消息沖突避免過程

圖7中，Discovery-Cycle的第1個信道幀內，節點A和節點B在同一個NiDB時隙發送而導致節點C、D、E和F處發生消息沖突碰撞，因此鄰居應答引導時隙NiRB內，節點C、D、E和F將不會發送hello_reply消息分組，而處于靜默狀態；在Discovery-Cycle的第2個信道幀內，成功接收并解析hello_request消息分組的節點C、D、E和節點F，將在該幀內的NiRB時隙對其進行響應應答，響應過程如下：

節點C、D、E和節點F，在[0，N-1]中隨機選取1個整數值作為其占用的NiRB時隙號。假設節點C占用0號NiRB時隙、節點D、E占用1號NiRB時隙、節點F占用N-1號NiRB時隙發送hello_reply消息分組，根據消息分組沖突碰撞規則分析，節點A、B能夠正確接收并解析節點C、節點F的hello_reply消息分組，但無法正確接收并成功解析節點D、節點E的hello_reply消息分組。

節點A、B解析節點C、F的hello_reply消息分組后，將節點C、F的節點標識、位置信息等添加到本地鄰居信息表項中，并進入鄰居發現過程的第3階段，即向節點C、節點F發送鄰居發現確認消息分組hello_ack，通知節點C、F已經成功被發現以及關于后續通信時隙預約的相關結果信息，hello_ack分組內還包含該波束扇區內已經被發現節點的ID標識；節點D、E通過分析接收到的hello_ack消息分組中攜帶的已經被發現節點的ID標識信息，知道其在NiRB時隙發送的hello _ reply消息分組可能由于沖突碰撞而未被正確接收和解析，將在Discovery-Cycle的第3個信道幀內，重復執行上述hello_reply消息分組發送過程。圖7中的第3個信道幀內，節點C、F將不再參與NiRB時隙的競爭使用，節點D、節點E分別隨機、無沖突地占用2號NiRB時隙和0號NiRB時隙發送hello_reply消息分組，消息分組能夠被節點A和節點B正確接收并解析，從而成功進入鄰居發現過程的第3階段。

(3)鄰居發現階段3

鄰居發現過程的第3階段在信道幀的NiAB時隙內進行。節點A、B在NiRB時隙內向成功發送hello_reply消息分組的節點定向廣播鄰居確認消息分組hello_ack，其占用的NiAB時隙號不是通過隨機方式產生的，而是與NiDB時隙的占用情況有關，即節點選取的NiAB時隙號和NiDB時隙號占用情況完全一致，這種方法可以進一步避免采用隨機占用時可能產生的消息沖突碰撞，確保消息分組hello_ack一定能被目標節點正確接收和解析。

對比分析圖6和圖8，節點A、B占用的NiDB時隙和NiAB時隙編號完全相同，確保了鄰居確認時隙一定無消息分組沖突碰撞的發生，這對提高鄰居發現成功概率有十分重要的作用和意義。

圖8 DAND/CA算法ack消息沖突避免過程

3 DAND/CA仿真分析

本節采用OPNET網絡仿真工具進行仿真實驗，對基于TDMA協議的帶沖突避免的定向鄰居發現算法DAND/CA的性能進行實驗驗證。在仿真實驗中，比較對象是PRA、SBA算法和一種增強型的SBA算法I- SBA[4]。現在以下仿真場景中對這4種定向鄰居發現算法進行性能仿真和比較。

3.1 仿真場景和參數設置

(1)仿真拓撲結構采用6×6網格拓撲，36個節點隨機分布在10 km×10 km的區域內，節點定向傳輸半徑為15 km，網絡的每個節點都互為1跳鄰居。

(2)多波束切換天線由12個波束構成，每個波束主瓣寬度為30°，可無縫覆蓋整個360°水平空間范圍。

(3)信道速率設為2 Mb/s，信道帶寬為10 kHz，傳輸頻率為30 MHz，調制方式為QAM64；N取值為8，T為0.125 ms。

同時，為了減小網絡仿真時仿真隨機數種子的選取對實驗結果的影響，在實驗中對每個數據點取5次不同隨機數種子情況下的實驗結果平均值作為最終結果[7]。

3.2 仿真結果分析

圖9給出了在PRA、SBA、I-SBA和DAND/CA算法下，定向鄰居節點平均發現時延的對比關系。

圖9 鄰居發現算法性能對比

由圖9可以看出，組網開始階段，所有節點都將嘗試發送鄰居發現控制消息，消息碰撞沖突嚴重，4種定向鄰居發現算法的性能差距較大，帶沖突避免的DAND/CA算法表現最好，能快速發現周圍所有鄰居節點，且算法收斂性好；I-SBA在SBA基礎上，在收發狀態間新添1個“空閑”狀態，處于空閑狀態的節點既不發送控制消息也不接收控制消息，在一定程度上避免了消息碰撞沖突；PRA是完全隨機的鄰居發現算法，無沖突避免機制，在開始階段沖突碰撞嚴重的情況下，算法性能較差，但隨著時間推移和消息碰撞沖突情況的緩解，PRA算法性能明顯變好。

需要注意的是，上述仿真給出了DAND/CA算法的性能結果，但未對算法中的參數N、K、w的不同取值對DAND/CA算法性能的影響進行仿真和分析，如何對參數進行優化設計是需要進一步研究和仿真的重點。

4 結語

本文詳細介紹了定向Ad hoc網絡鄰居發現原理，對其中的天線收發模式選擇、天線掃描圖案等關鍵技術進行了重點分析，在此基礎上，針對現有定向鄰居發現算法沒有充分考慮同一個波束內同時存在多個節點時的沖突問題，提出一種帶沖突避免的定向鄰居發現算法DAND/CA。仿真結果表明，DAND/CA算法在不顯著增加網絡控制復雜度的情況下，適用于從稀疏到密集的所有網絡場景，可快速、可靠地發現網絡內所有1跳鄰居節點并初步建立起定向通信鏈路，從而快速組建定向Ad hoc網絡。

[1] Murawski R, Felemban E,Ekici E,et al. Neighbor Discovery in Wireless Networks with Sectored Antennas[C].Ad Hoc Networks,2012(10):1-18.

[2] 景中源，曾浩洋，李大雙等.定向Ad hoc網絡MAC組網技術研究[J].通信技術，2014(09)：1041-1047. JING Zhong-yuan，ZENG Hao-yang，LI Da-shuang，et al. The MAC Layer Networking Technology Research in Ad hoc Network with Directional Antennas[J].Communications Technology,2014(09):1041-1047.

[3] 蔡浩，劉勃，歸琳.定向天線的Ad hoc網絡鄰居發現[J]. 信息安全與通信保密，2011(09)：63-66. CAI Hao,LIU Bo,GUI Lin. Neighbor Discovery in Ad Hoc Network using Directional Antennas [J]. Communications Technology,2011(09):63-66.

[4] CAI Hao,LIU Bo,GUI Lin,et al. Neighbor Discovery Algorthms in Wireless Networks Using Directional Antennas[C]//Ad hoc and Sensor Networking Symposium.[s.l.]: [s.n.],2012:767-772.

[5] Woongsoo Na, Laihyuk Park, Sungrae. Deafness-Aware MAC Protocol for Directional Antennas[C]//IEEE International Conference on Consumer Electornics(ICCE) .[s.l.]: [s.n.], 2013: 625-626.

[6] ZHANG Zhen-sheng, Ryu B,et al. Performance of All -Directional Transmission and Reception Algorithmsin Wireless Ad Hoc Networks with Directional Antennas[C]//IEEE MILCOM.[s.l.]:[s.n.],2005:225-230.

[7] 戴英.定向Ad hoc網絡的MAC協議研究[D].成都：西南交通大學,2013. DAI Ying. MAC Protocol Research in Ad hoc Network with Direction Antenna[D]. Chengdu: Southwest Jiaotong University, 2013.

A Neighbor Discovery Algorithm with Collision Avoidance in Ad hoc Networks Using Directional Antennas

JING Zhong-yuan，ZENG Hao-yang，LI Da-shuang ，MAO Jian-bing

(No.30 Institute of CETC, Chengdu Sichuan 610041, China)

Directional antennas applied in Ad hoc network, could obviously improve network performance, and however,also needs new MAC and routing protocols to control the directional antenna system. Neighbor discovery algorithm, as one of the most important protocols, is the basis and premise for ad hoc networking. In the light that most of the proposed neighbor discovery algorithms consider no the collision case that multiple nodes exist in the same directional beam sector, a new directional neighbor discovery algorithm with collision avoidance called DAND/CA (Directional Antenna Neighbor Discovery with Collision Avoidance) is proposed. DAND/CA algorithm could efficiently avoid collision case by randomly selecting mini-slot to transmit control messages. Simulation results indicate that the proposed DAND/CA is remarkably superior to the existing algorithms in terms of neighbor discovery time and success ratio.

directional antennas; ad hoc network; neighbor discovery; collision avoidance

10.3969/j.issn.1002-0802.2015.05.015

2014-11-10；

2015-03-07 Received date:2014-11-10；Revised date：2015-03-07

TP393

1002-0802(2015)05-0582-07