定向Ad hoc網(wǎng)絡(luò)中一種帶沖突避免的鄰居發(fā)現(xiàn)算法*

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

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

?

定向Ad hoc網(wǎng)絡(luò)中一種帶沖突避免的鄰居發(fā)現(xiàn)算法*

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

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

定向天線應(yīng)用于ad hoc網(wǎng)絡(luò)，一方面能顯著提升網(wǎng)絡(luò)性能，另一方面也需要新的MAC和路由協(xié)議來控制定向天線系統(tǒng)。鄰居發(fā)現(xiàn)算法作為其中最重要的協(xié)議之一，是定向ad hoc網(wǎng)絡(luò)組網(wǎng)的基礎(chǔ)和前提，針對現(xiàn)有文獻(xiàn)中提出的各種鄰居發(fā)現(xiàn)算法大多沒有考慮同一定向波束扇區(qū)內(nèi)存在多個(gè)節(jié)點(diǎn)時(shí)的沖突情況，提出一種帶沖突避免的定向鄰居發(fā)現(xiàn)算法DAND/CA。DAND/CA通過隨機(jī)選擇發(fā)送控制消息占用的微時(shí)隙，能有效避免碰撞沖突的發(fā)生。仿真結(jié)果表明，提出的DAND/CA算法在鄰居發(fā)現(xiàn)時(shí)間和成功率等方面明顯優(yōu)于現(xiàn)有算法。

定向天線；Ad hoc網(wǎng)絡(luò)；鄰居發(fā)現(xiàn)；沖突避免

0 引 言

多跳無線自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)鄰域信息在路由、分群和媒介訪問控制等方面起著至關(guān)重要的作用[1]?；谌蛱炀€的ad hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)傳輸范圍內(nèi)的所有節(jié)點(diǎn)能很容易地偵聽到其發(fā)送的鄰居請求廣播消息，鄰居發(fā)現(xiàn)過程相對簡單，不需要專門為其設(shè)計(jì)相應(yīng)的通信協(xié)議，而在基于定向天線的ad hoc網(wǎng)絡(luò)中，定向天線和定向通信自身特點(diǎn)使鄰居發(fā)現(xiàn)變得較為困難[2]：

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

(2)節(jié)點(diǎn)必須在正確的時(shí)間、將正確的波束方向指向?qū)Ψ?，且彼此收發(fā)模式相反，才能有效通信，即定向天線發(fā)生有效通信的條件十分苛刻。

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

1 鄰居發(fā)現(xiàn)原理

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

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

圖1 定向鄰居節(jié)點(diǎn)有效通信示例

因此相比于全向天線，在定向天線系統(tǒng)中解決鄰居發(fā)現(xiàn)問題時(shí)需要考慮更多的內(nèi)容，具體包括天線模式選擇算法設(shè)計(jì)、多波束切換天線掃描圖案設(shè)計(jì)以及控制消息交互機(jī)制設(shè)計(jì)等。

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

在基于多波束切換天線的Ad hoc網(wǎng)絡(luò)中，由于定向天線難于實(shí)現(xiàn)廣播通信，當(dāng)節(jié)點(diǎn)需要對多個(gè)節(jié)點(diǎn)廣播數(shù)據(jù)消息時(shí)，須按照某種調(diào)度順序?qū)φ麄€(gè)空間區(qū)域進(jìn)行“掃描”。掃描過程，即多波束天線不斷切換其當(dāng)前所使用定向波束扇區(qū)的過程，其中定向波束切換的順序和方法稱為定向天線的掃描圖案。

應(yīng)當(dāng)注意，天線模式和天線掃描圖案既相互關(guān)聯(lián)又相互約束，二者共同決定某次鄰居發(fā)現(xiàn)過程成功的統(tǒng)計(jì)特性，并直接影響鄰居發(fā)現(xiàn)過程的性能指標(biāo)。

2 DAND/CA算法描述

2.1 系統(tǒng)模型和節(jié)點(diǎn)假設(shè)

圖2 理想的K扇區(qū)多波束切換天線

多波束切換天線通過選擇不同的天線單元就能實(shí)現(xiàn)波束扇區(qū)的切換，是定向天線中最簡單且最易于實(shí)現(xiàn)的一種，DAND/CA算法相關(guān)結(jié)論就是基于多波束切換天線得出的，但應(yīng)當(dāng)注意它同樣可以很容易地?cái)U(kuò)展到其他類型的定向天線系統(tǒng)中去。

節(jié)點(diǎn)還應(yīng)當(dāng)滿足以下假設(shè)條件：

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

(2)任何時(shí)刻，節(jié)點(diǎn)最多只能在一個(gè)定向波束扇區(qū)內(nèi)進(jìn)行消息分組發(fā)送或接收，但能在不同扇區(qū)之間快速地切換。

(3)時(shí)間是基于時(shí)隙劃分的，所有節(jié)點(diǎn)通過GPS或北斗系統(tǒng)能夠達(dá)到精確的時(shí)鐘同步。

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

(5)同時(shí)收到2個(gè)及2個(gè)以上鄰居節(jié)點(diǎn)的消息分組時(shí)，將發(fā)生碰撞沖突而無法正確接收和解析消息分組[4]。

2.2 信道時(shí)幀結(jié)構(gòu)

DAND/CA算法設(shè)計(jì)的TDMA時(shí)幀循環(huán)結(jié)構(gòu)如圖3所示，將信道資源劃分為連續(xù)的、周期性重復(fù)的TDMA幀，每幀由鄰居發(fā)現(xiàn)子幀和業(yè)務(wù)數(shù)據(jù)傳輸子幀組成，其中業(yè)務(wù)數(shù)據(jù)傳輸子幀包含M個(gè)數(shù)據(jù)時(shí)隙，鄰居發(fā)現(xiàn)子幀包含探測、響應(yīng)和確認(rèn)3個(gè)階段，每個(gè)階段由N個(gè)持續(xù)時(shí)間更短的引導(dǎo)微時(shí)隙組成；每個(gè)時(shí)隙的持續(xù)時(shí)間為T，每個(gè)引導(dǎo)微時(shí)隙的持續(xù)時(shí)間為T/N。

圖3 TDMA幀結(jié)構(gòu)示意

在周期性的TDMA幀結(jié)構(gòu)內(nèi)，與鄰居發(fā)現(xiàn)過程相關(guān)的各類時(shí)隙定義如下：

鄰居探測引導(dǎo)(NiDB，Neighbor Detect Bootstrap)時(shí)隙：為鄰居發(fā)現(xiàn)過程中隨機(jī)分派給各發(fā)送模式節(jié)點(diǎn)使用的時(shí)隙。鄰域探測引導(dǎo)時(shí)隙用于主動發(fā)起鄰居發(fā)現(xiàn)過程的節(jié)點(diǎn)在特定的波束扇區(qū)內(nèi)發(fā)送鄰居請求消息分組，分組信息包含有節(jié)點(diǎn)的ID編號、1跳鄰域信息以及節(jié)點(diǎn)HRFS時(shí)隙分配信息。每幀中鄰域探測引導(dǎo)時(shí)隙NiDB配置數(shù)量為N。

鄰居應(yīng)答引導(dǎo)(NiRB，Neighbor Reply Bootstrap)時(shí)隙：隨機(jī)分派給成功接收鄰居請求消息分組的節(jié)點(diǎn)，用于傳輸鄰居響應(yīng)和HRFS時(shí)隙分配所需的信息。每幀中鄰居應(yīng)答引導(dǎo)時(shí)隙NiRB配置數(shù)量為N。

鄰居確認(rèn)引導(dǎo)(NiAB，Neighbor Acknowledge Bootstrap)時(shí)隙：為分派給成功接收鄰居響應(yīng)消息分組節(jié)點(diǎn)使用的時(shí)隙，其分配情況與NiDB完全一致，用于傳輸鄰居發(fā)現(xiàn)確認(rèn)及HRFS時(shí)隙分配結(jié)果等信息。每幀中鄰居響應(yīng)引導(dǎo)時(shí)隙NiAB配置數(shù)量為N。

2.3 天線收發(fā)模式選擇

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

i=?Frame_sequence/K/w」

(1)

式中，F(xiàn)rame_sequence為信道幀序號，K為定向多波束天線扇區(qū)數(shù)，w表示在每個(gè)波束扇區(qū)內(nèi)駐留的信道幀數(shù)。應(yīng)當(dāng)注意，1輪掃描周期內(nèi)節(jié)點(diǎn)天線的收發(fā)模式將保持不變，并在每個(gè)波束扇區(qū)內(nèi)重復(fù)執(zhí)行w次收發(fā)操作后，順序切換至下一個(gè)波束扇區(qū)，當(dāng)遍歷完所有的波束扇區(qū)后本輪掃描周期結(jié)束。

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

2.4 天線掃描圖案

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

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

DAND/CA算法中的天線掃描圖案，可以確保在具有相同的方向基準(zhǔn)前提下，處于收發(fā)模式的鄰居節(jié)點(diǎn)盡可能將當(dāng)前激活波束扇區(qū)互相指向?qū)Ψ?，從而滿足定向節(jié)點(diǎn)有效通信的條件。

2.5 Hello-Reply-Ack 3步握手機(jī)制

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

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

圖5 沖突情形：1個(gè)波束扇區(qū)內(nèi)存在多個(gè)鄰居節(jié)點(diǎn)

DAND/CA算法，在充分考慮圖5所示沖突情形對鄰居發(fā)現(xiàn)過程影響的基礎(chǔ)上，將信道幀結(jié)構(gòu)內(nèi)的鄰居發(fā)現(xiàn)子幀劃分多個(gè)持續(xù)時(shí)間更短的引導(dǎo)微時(shí)隙，節(jié)點(diǎn)通過隨機(jī)選擇發(fā)送鄰居交互信息所占用的微時(shí)隙，允許同一波束扇區(qū)內(nèi)的多個(gè)鄰居節(jié)點(diǎn)在不同的微時(shí)隙內(nèi)獨(dú)立完成鄰居發(fā)現(xiàn)過程，從而有效地避免了鄰居發(fā)現(xiàn)過程中的消息碰撞沖突。

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

(1)鄰居發(fā)現(xiàn)階段1

鄰居發(fā)現(xiàn)過程的第1階段在信道幀的NiDB時(shí)隙內(nèi)進(jìn)行。主動發(fā)送模式節(jié)點(diǎn)A、B，分別從N個(gè)NiDB中隨機(jī)選取1個(gè)時(shí)隙，用于定向廣播發(fā)送鄰居請求消息hello_request；偵聽節(jié)點(diǎn)C、D、E和F在所有的NiDB時(shí)隙內(nèi)處于信道監(jiān)聽狀態(tài)，等待接收hello_request消息。沖突避免見圖6。

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

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

(2)鄰居發(fā)現(xiàn)階段2

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

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

圖7中，Discovery-Cycle的第1個(gè)信道幀內(nèi)，節(jié)點(diǎn)A和節(jié)點(diǎn)B在同一個(gè)NiDB時(shí)隙發(fā)送而導(dǎo)致節(jié)點(diǎn)C、D、E和F處發(fā)生消息沖突碰撞，因此鄰居應(yīng)答引導(dǎo)時(shí)隙NiRB內(nèi)，節(jié)點(diǎn)C、D、E和F將不會發(fā)送hello_reply消息分組，而處于靜默狀態(tài)；在Discovery-Cycle的第2個(gè)信道幀內(nèi)，成功接收并解析hello_request消息分組的節(jié)點(diǎn)C、D、E和節(jié)點(diǎn)F，將在該幀內(nèi)的NiRB時(shí)隙對其進(jìn)行響應(yīng)應(yīng)答，響應(yīng)過程如下：

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

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

(3)鄰居發(fā)現(xiàn)階段3

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

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

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

3 DAND/CA仿真分析

本節(jié)采用OPNET網(wǎng)絡(luò)仿真工具進(jìn)行仿真實(shí)驗(yàn)，對基于TDMA協(xié)議的帶沖突避免的定向鄰居發(fā)現(xiàn)算法DAND/CA的性能進(jìn)行實(shí)驗(yàn)驗(yàn)證。在仿真實(shí)驗(yàn)中，比較對象是PRA、SBA算法和一種增強(qiáng)型的SBA算法I- SBA[4]?，F(xiàn)在以下仿真場景中對這4種定向鄰居發(fā)現(xiàn)算法進(jìn)行性能仿真和比較。

3.1 仿真場景和參數(shù)設(shè)置

(1)仿真拓?fù)浣Y(jié)構(gòu)采用6×6網(wǎng)格拓?fù)洌?6個(gè)節(jié)點(diǎn)隨機(jī)分布在10 km×10 km的區(qū)域內(nèi)，節(jié)點(diǎn)定向傳輸半徑為15 km，網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)都互為1跳鄰居。

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

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

同時(shí)，為了減小網(wǎng)絡(luò)仿真時(shí)仿真隨機(jī)數(shù)種子的選取對實(shí)驗(yàn)結(jié)果的影響，在實(shí)驗(yàn)中對每個(gè)數(shù)據(jù)點(diǎn)取5次不同隨機(jī)數(shù)種子情況下的實(shí)驗(yàn)結(jié)果平均值作為最終結(jié)果[7]。

3.2 仿真結(jié)果分析

圖9給出了在PRA、SBA、I-SBA和DAND/CA算法下，定向鄰居節(jié)點(diǎn)平均發(fā)現(xiàn)時(shí)延的對比關(guān)系。

圖9 鄰居發(fā)現(xiàn)算法性能對比

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

需要注意的是，上述仿真給出了DAND/CA算法的性能結(jié)果，但未對算法中的參數(shù)N、K、w的不同取值對DAND/CA算法性能的影響進(jìn)行仿真和分析，如何對參數(shù)進(jìn)行優(yōu)化設(shè)計(jì)是需要進(jìn)一步研究和仿真的重點(diǎn)。

4 結(jié) 語

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

[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網(wǎng)絡(luò)MAC組網(wǎng)技術(shù)研究[J].通信技術(shù)，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網(wǎng)絡(luò)鄰居發(fā)現(xiàn)[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網(wǎng)絡(luò)的MAC協(xié)議研究[D].成都：西南交通大學(xué),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

A

1002-0802(2015)05-0582-07

景中源(1988—)，男，碩士研究生，主要研究方向?yàn)閼?zhàn)術(shù)網(wǎng)絡(luò)組網(wǎng)；

曾浩洋1968—)，男，碩士，研究員，主要研究方向?yàn)閼?zhàn)術(shù)通信網(wǎng)絡(luò)；

李大雙(1963—)，男，博士，研究員，主要研究方向?yàn)閼?zhàn)術(shù)網(wǎng)絡(luò)組網(wǎng)與路由技術(shù)；

毛建兵(1981—)，男，博士，高級工程師，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。