定向Ad Hoc網(wǎng)絡(luò)中鄰居發(fā)現(xiàn)與跟蹤技術(shù)研究

王 瑩， 王中武， 莫 嫻

（①海軍司令部信息化部，北京 100841；②中國電子科技集團(tuán)第30研究所，四川 成都 610041)

0 引言

最近幾年，采用高增益的定向鏈路實(shí)現(xiàn) ad hoc組網(wǎng)引起了強(qiáng)烈的關(guān)注。收、發(fā)兩端都使用定向天線能提供更長的傳輸距離和更高的數(shù)據(jù)率。通過將能量的發(fā)射與探測限定到指定的方向，能夠大大減小無用方向上的信號(hào)干擾，提高抗干擾能力。定向傳輸和接收提供的高增益使得較遠(yuǎn)節(jié)點(diǎn)之間也能夠通信，從而減小了網(wǎng)絡(luò)直徑。此外，由于可以調(diào)度多個(gè)節(jié)點(diǎn)之間的鏈路對同時(shí)進(jìn)行定向的傳輸，故可增加空間上的重用效率[1]。因此，采用定向傳輸?shù)囊苿?dòng)自組織網(wǎng)絡(luò)能夠在網(wǎng)絡(luò)服務(wù)質(zhì)量、吞吐量、抗敵方人為干擾和探測等方面獲得較大的性能提升，其程度取決于天線、收發(fā)器以及所采用MAC算法的能力。

在采用定向天線的無線ad hoc網(wǎng)絡(luò)的MAC控制算法方面，相關(guān)研究工作都假設(shè)在算法的某個(gè)階段采用了全向接收。但是，全向接收使得該協(xié)議面對人為干擾很脆弱，而且全向天線與定向天線的增益不匹配，極大影響了網(wǎng)絡(luò)性能的改善程度；現(xiàn)有的鄰居發(fā)現(xiàn)算法，包括隨機(jī)掃描探測算法、窮舉掃描方法以及令牌遍歷扇區(qū)掃描算法[2-3]，發(fā)現(xiàn)鄰居時(shí)間可能很長或不是確定的值。此外，在拓?fù)鋭?dòng)態(tài)變化的移動(dòng)自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)和信道質(zhì)量的變化給鏈路跟蹤帶來極大的難題。因此，開發(fā)完全采用定向傳輸/接收的快速鄰居發(fā)現(xiàn)與跟蹤算法是一個(gè)極具挑戰(zhàn)的問題。文中基于已有的技術(shù)基礎(chǔ)，描述一種完全基于定向波束傳輸?shù)目焖汆従影l(fā)現(xiàn)算法與持續(xù)跟蹤鏈路方向的控制方法，試圖解決該問題。

文中結(jié)構(gòu)安排如下。首先描述 MAC幀結(jié)構(gòu)設(shè)計(jì)與假設(shè)條件，然后描述一種完全采用定向傳輸/接收的、具有確定發(fā)現(xiàn)時(shí)間的快速鄰居發(fā)現(xiàn)方法，最后描述了移動(dòng)節(jié)點(diǎn)應(yīng)用數(shù)字光纖羅盤、北斗接收機(jī)等輔助導(dǎo)航系統(tǒng)模塊實(shí)現(xiàn)動(dòng)態(tài)跟蹤定向鏈路波束方向的方法。

1 MAC幀結(jié)構(gòu)與假設(shè)

在完全定向傳輸自組織網(wǎng)絡(luò)中，若采用基于時(shí)分多址訪問(TDMA)的MAC機(jī)制，則網(wǎng)絡(luò)節(jié)點(diǎn)能夠結(jié)合TDMA每幀的時(shí)隙和鏈路的傳輸/接收方向，以協(xié)作的方式實(shí)現(xiàn)鄰居鏈路上帶寬資源分配和調(diào)度。

將時(shí)間分割為連續(xù)的幀，且將每個(gè)幀分割為 3個(gè)子幀[4]。如圖 1所示，第一個(gè)探測子幀專門用于鄰居探測，即發(fā)現(xiàn)新的鄰居節(jié)點(diǎn)、節(jié)點(diǎn)離開等。第二個(gè)預(yù)約子幀用于兩個(gè)節(jié)點(diǎn)重新確認(rèn)它們在鄰居發(fā)現(xiàn)過程中探測到的連接，并且進(jìn)行數(shù)據(jù)通信預(yù)約。第三個(gè)數(shù)據(jù)傳輸子幀用于實(shí)際的數(shù)據(jù)傳輸。每個(gè)子幀分割為多個(gè)時(shí)隙。

在鄰居探測/預(yù)約期內(nèi)的每個(gè)子幀由多個(gè)時(shí)隙構(gòu)成。為了進(jìn)行功率量級協(xié)商和預(yù)約確認(rèn)，需要進(jìn)行一次 3-步/2步握手過程。鄰居探測(發(fā)現(xiàn))所使用的 3-步消息與預(yù)約所使用的2-步消息的內(nèi)容各不相同。為了易于實(shí)現(xiàn)，這兩種情況使用相同的消息格式（鄰居發(fā)現(xiàn)和時(shí)隙預(yù)約）。后者的消息長度可能大于前者的消息長度。每個(gè)時(shí)隙能夠容納下鄰居發(fā)現(xiàn)和預(yù)約所使用的3-步握手消息。假設(shè)第一個(gè)子幀包含n(n=3)個(gè)掃描時(shí)隙，第二個(gè)子幀包含r(r=2)個(gè)預(yù)約時(shí)隙。第三個(gè)子幀具有M個(gè)數(shù)據(jù)傳輸時(shí)隙(見圖1)。

圖1 TDMA幀結(jié)構(gòu)

假設(shè)每個(gè)節(jié)點(diǎn)裝備了一套收發(fā)器與一套波束指向可控(由選取的陣元方向確定)的天線。所有的節(jié)點(diǎn)都是時(shí)鐘同步的(通過北斗或其它方法)。每個(gè)節(jié)點(diǎn)都具有以下能力：

通信為半雙工，但每個(gè)節(jié)點(diǎn)能夠在傳輸與接收模式之間快速地切換。

每個(gè)節(jié)點(diǎn)能夠形成任意ω＜π弧度寬度的傳輸或接收單波束。因而，每個(gè)節(jié)點(diǎn)具有定向傳輸與接收的能力。

每個(gè)節(jié)點(diǎn)的定向天單元線采取相同的陣元編號(hào)順序，各節(jié)點(diǎn)陣元天線預(yù)先都經(jīng)過精確的初始安裝方向校對，使各節(jié)點(diǎn)指向正東的陣元編號(hào)都相同。

所有節(jié)點(diǎn)的當(dāng)前時(shí)刻都是 TDMA幀同步的(通過北斗或其它自組織TDMA同步方法[5])。

每個(gè)節(jié)點(diǎn)都安裝有北斗接收機(jī)、測速儀、數(shù)字方向儀、數(shù)字光纖陀螺模塊，能夠根據(jù)采集的實(shí)時(shí)運(yùn)動(dòng)參數(shù)通過運(yùn)算確定自己的地理位置、運(yùn)動(dòng)姿態(tài)(俯仰角、橫滾角)以及朝向。

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

鄰居發(fā)現(xiàn)過程在圖 1所示的第一個(gè)子幀內(nèi)進(jìn)行[3]。為了使每個(gè)節(jié)點(diǎn)都快速發(fā)現(xiàn)潛在定向鄰居，采用一種確定性的探測掃描鄰居發(fā)現(xiàn)算法。該算法的前提，是每個(gè)節(jié)點(diǎn)基于數(shù)字指北儀、數(shù)字陀螺，應(yīng)用導(dǎo)航計(jì)算軟件實(shí)時(shí)確定自己的俯仰、橫滾姿態(tài)與方向，在任何時(shí)刻都知道自己的哪一個(gè)天線陣元指向正東、哪一個(gè)天線陣元指向正南、哪一個(gè)天線陣元指向正西、哪一個(gè)天線陣元指向正北。

在進(jìn)行鄰居發(fā)現(xiàn)探測掃描時(shí)，所有處于探測掃描模式的節(jié)點(diǎn)，無論其姿態(tài)和朝向如何，都以平行的波束軸向向相同的方向發(fā)射；而所有處于偵聽模式的節(jié)點(diǎn)，無論其姿態(tài)和朝向如何，都以平行的波束軸向在相反的方向偵聽。

2.1 掃描尋找鄰居

為便于敘述，假設(shè)一對具有定向天線的節(jié)點(diǎn)，只要連接它們的直線在一個(gè)節(jié)點(diǎn)的當(dāng)前傳輸波束內(nèi)并且在另一個(gè)節(jié)點(diǎn)的當(dāng)前接收波束內(nèi)，就能夠直接進(jìn)行通信。因而，這兩個(gè)節(jié)點(diǎn)必須同時(shí)將它們的波束相互指向?qū)Ψ剑⑶冶仨毺幱趥鬏斉c接收互補(bǔ)的模式(即一個(gè)在發(fā)送時(shí)，另一個(gè)必須在接收)。在一個(gè)戰(zhàn)術(shù)網(wǎng)絡(luò)中，其通信可能發(fā)生在3維空間中。不僅在地面與空中節(jié)點(diǎn)之間將會(huì)進(jìn)行通信，而且位于不同海拔高度的地面節(jié)點(diǎn)之間以及在不同高度飛行的空中節(jié)點(diǎn)之間也會(huì)進(jìn)行通信。為了便于形式描述這種情況，設(shè)(θ’,φ’)和(θ’,φ’)分別為兩個(gè)節(jié)點(diǎn)傳輸與接收方向。對于窄波束天線，這兩個(gè)節(jié)點(diǎn)之間的通信需要將這兩個(gè)波束指向相反的方向，并且處于傳輸與接收互補(bǔ)的模式，即：

鄰居發(fā)現(xiàn)的關(guān)鍵思想，是執(zhí)行符合約束條件(1)的搜索過程。一次掃描為達(dá)到整個(gè)搜索空間的一次最小覆蓋的一個(gè)序列(天線指向的若干方向和若干模式)，由多個(gè)尖帽狀空間相交形成整個(gè)半球形的搜索空間，每個(gè)波束以其指向方向?yàn)橹行牡膶挾葹棣亍Ｔ诿看螔呙柚校鞴?jié)點(diǎn)遵循預(yù)定的順序，但傳輸與接收極性相反。當(dāng)進(jìn)行掃描時(shí)，節(jié)點(diǎn)在每個(gè)指定的方向上都傳輸一個(gè)通告。當(dāng)進(jìn)行偵聽時(shí)，節(jié)點(diǎn)等待鄰近節(jié)點(diǎn)的通告到來。如果一個(gè)偵聽節(jié)點(diǎn)收到一個(gè)通告，則定向地響應(yīng)它自己的通告，并且期待再接收一個(gè)確認(rèn)，這些步驟都是在一個(gè)很短的時(shí)間間隔內(nèi)進(jìn)行。這種3-步握手的每個(gè)部分，都可以交換傳輸功率量級信息和提取方向信息。

2.2 模式選擇

一個(gè)節(jié)點(diǎn)通過對方向序列的單次掃描，有可能探測到它的所有潛在鄰居，但通常需要經(jīng)過多次掃描才能發(fā)現(xiàn)它們[1]。網(wǎng)絡(luò)中所有節(jié)點(diǎn)要發(fā)現(xiàn)它們的所有潛在鄰居所需要的掃描次數(shù)下限和上限，取決于形成的網(wǎng)絡(luò)拓?fù)洹⒐?jié)點(diǎn)每次掃描中用來選擇其掃描或偵聽模式的算法。文中介紹一種確定性的模式選擇算法。每個(gè)節(jié)點(diǎn)的初始化參數(shù)為 N 和 j，這里 j∈{0,1,…,N-1}(為其獨(dú)一無二的標(biāo)識(shí))，且N為網(wǎng)絡(luò)中的最大節(jié)點(diǎn)數(shù)。每個(gè)節(jié)點(diǎn)的ID(即j)以二進(jìn)制形式編碼。如果其位數(shù)小于，則在其左邊添加 0直到位為止。例如，如果N=16并且j=3，則其二進(jìn)制形式為0011。對于一個(gè)掃描周期內(nèi)的第次掃描，如果第位為0則選擇偵聽模式，如果為1則選擇掃描(即主動(dòng)探測)模式。因此，在第一次掃描期間，一個(gè)節(jié)點(diǎn)有機(jī)會(huì)探測到它在網(wǎng)絡(luò)內(nèi)的一半鄰居(若它們在其可達(dá)范圍內(nèi))。很容易證明，任何兩個(gè)節(jié)點(diǎn)的二進(jìn)制編碼內(nèi)都至少含有一個(gè)不同的數(shù)字bit(位)，這又意味著這兩個(gè)節(jié)點(diǎn)只要在相互的可達(dá)范圍內(nèi)，最多經(jīng)過次掃描就能互相探測到對方。

2.3 3步握手機(jī)制

本節(jié)敘述一種 3-步握手的算法，包括鄰居發(fā)現(xiàn)過程中每個(gè)節(jié)點(diǎn)采取的行動(dòng)以及兩個(gè)節(jié)點(diǎn)(每個(gè)指向位置方向上的節(jié)點(diǎn)1和節(jié)點(diǎn)2)之間的消息交換。其消息內(nèi)容與具體的握手算法相關(guān)。

握手步驟 1：為使發(fā)現(xiàn)其傳輸覆蓋范圍內(nèi)任何潛在鄰居的機(jī)會(huì)最大化，節(jié)點(diǎn)1以收發(fā)器的最大傳輸功率量級傳輸鄰居探測消息，向潛在的鄰居們通告它自己的存在。

握手步驟 2：節(jié)點(diǎn) 2偵聽一次傳輸。如果什么也沒有接收到，則放棄這次握手。否則，如果節(jié)點(diǎn)2成功地接收到節(jié)點(diǎn) 1的鄰居探測消息，則知道了節(jié)點(diǎn)1的存在，并且它可以向節(jié)點(diǎn)1傳輸一個(gè)應(yīng)答消息通告它自己的存在。

握手步驟3：節(jié)點(diǎn)1偵聽一個(gè)返回的應(yīng)答消息。如果沒有收到，節(jié)點(diǎn)1放棄本次握手。否則，若節(jié)點(diǎn)1成功接收到節(jié)點(diǎn)2的應(yīng)答消息，它則知道節(jié)點(diǎn)2存在，節(jié)點(diǎn)1則繼續(xù)進(jìn)行握手操作，并向節(jié)點(diǎn)2響應(yīng)。

節(jié)點(diǎn)2偵聽節(jié)點(diǎn)1的響應(yīng)。如果沒有接收到，節(jié)點(diǎn)2則認(rèn)為節(jié)點(diǎn)1不同意建立一個(gè)連接。否則，如果節(jié)點(diǎn)2成功接收到節(jié)點(diǎn)1的響應(yīng)，它則知道節(jié)點(diǎn)1認(rèn)可建立鄰居關(guān)系。

3 執(zhí)行時(shí)隙預(yù)約

在鄰居探測階段中，兩個(gè)節(jié)點(diǎn)已探測到相互的存在，它們還需要確認(rèn)該連接并進(jìn)行鏈路帶寬分配預(yù)約。預(yù)約請求與確認(rèn)將在圖1所示的第二個(gè)子幀內(nèi)執(zhí)行，在預(yù)約子時(shí)隙中，節(jié)點(diǎn)1將開始一個(gè)2-步握手的過程。

節(jié)點(diǎn)1將向節(jié)點(diǎn)2發(fā)出一個(gè)預(yù)約請求消息，指出可用于預(yù)約的空閑時(shí)隙與期望的時(shí)隙數(shù)量。

在接收到節(jié)點(diǎn)1的預(yù)約請求消息后，節(jié)點(diǎn)2計(jì)算出兩個(gè)節(jié)點(diǎn)共同的空閑時(shí)隙的一個(gè)集合。如果共同的空閑時(shí)隙的數(shù)量小于所要求的數(shù)量，則不能作出任何預(yù)約，但這兩個(gè)節(jié)點(diǎn)保留它們最后相互聯(lián)系的方向，可以在隨后的那些幀內(nèi)的下一個(gè)約定的子時(shí)隙內(nèi)繼續(xù)進(jìn)行預(yù)約。如果兩個(gè)節(jié)點(diǎn)的可用共同空閑時(shí)隙數(shù)等于(或大于)節(jié)點(diǎn)1需要的時(shí)隙數(shù)，節(jié)點(diǎn)2則以預(yù)約的公共空閑時(shí)隙，向節(jié)點(diǎn)1應(yīng)答一個(gè)預(yù)約響應(yīng)消息。如果兩個(gè)節(jié)點(diǎn)的可用共同空閑時(shí)隙數(shù)小于節(jié)點(diǎn) 1需要的時(shí)隙數(shù)，則節(jié)點(diǎn)1應(yīng)答一個(gè)預(yù)約不成功消息。

當(dāng)接收到預(yù)約響應(yīng)消息，則鏈路帶寬資源預(yù)約成功，就可以開始在該定向鏈路上傳輸數(shù)據(jù)業(yè)務(wù)了。

4 鄰居發(fā)現(xiàn)探測掃描的參數(shù)選取

設(shè)一幀的長度為80 ms，前5 ms用于鄰居發(fā)現(xiàn)探測掃描和定向鏈路時(shí)隙預(yù)約，后75 ms包含15個(gè)5 ms寬度的數(shù)據(jù)時(shí)隙。采用由37個(gè)喇叭陣元構(gòu)成的半球形定向波束天線，每個(gè)波束的寬度為30o。

在掃描和預(yù)約子幀內(nèi)，考慮波束切換時(shí)間、保護(hù)時(shí)間以及消息長度，完成 3-步握手的每個(gè)子時(shí)隙長度設(shè)置為1 ms，完成預(yù)約子時(shí)隙長度設(shè)置為1 ms。那么每幀有3 ms專用于鄰居發(fā)現(xiàn)，每幀有另外2 ms專用于預(yù)約。其總開銷大約為6%。對于30o的波束寬度，需要 37個(gè)波束來完成一次完整的半球形掃描。如果N=64，對于采用確定性掃描算法的情形，它將需要(37×6)×0.1=17.76 s的時(shí)間來完成一次完整的掃描(探測完半球型空間內(nèi)的所有方向)。

5 鏈路方向跟蹤

由于車載或無人機(jī)(UAV)等移動(dòng)載體時(shí)刻處于運(yùn)動(dòng)狀態(tài)，節(jié)點(diǎn)的橫滾、俯仰和方位角的變化會(huì)造成已建立的定向鏈路的方向指向產(chǎn)生偏離[6]，需要基于周期的測量數(shù)據(jù)和運(yùn)算、在每個(gè)TDMA幀內(nèi)實(shí)時(shí)確定定向鏈路傳輸與接收應(yīng)該采用的最合適的天線陣元。

每個(gè)節(jié)點(diǎn)根據(jù)周期地(如1 s)從數(shù)字指北儀、數(shù)字光纖陀螺儀以及北斗讀取的位置、方向、速度、偏轉(zhuǎn)數(shù)據(jù)，利用北斗接收機(jī)測出載體所在地理經(jīng)度和緯度，利用載體上的慣性導(dǎo)航系統(tǒng)測出載體的姿態(tài)參數(shù)(包括載體相對正北方向的航向角、載體相對水平面的橫滾角和俯仰角)，根據(jù)定向鏈路鄰居在前一個(gè)TDMA幀內(nèi)報(bào)告的北斗位置經(jīng)度和緯度，通過計(jì)算確定最合適天線陣元，然后在鄰居表中記錄該鏈路的陣元方向矢量，驅(qū)動(dòng)天線實(shí)現(xiàn)對鄰居的跟蹤傳輸與接收。

6 結(jié)語

文中針對采用定向波束天線的無線 ad hoc網(wǎng)絡(luò)，結(jié)合TDMA幀結(jié)構(gòu)的時(shí)隙設(shè)計(jì)，介紹了一種完全采用定向傳輸/接收的快速鄰居發(fā)現(xiàn)與定向鏈路方向跟蹤算法。在給出的例子中，有大約6%的開銷用于鄰居發(fā)現(xiàn)和預(yù)約，用于預(yù)約和發(fā)現(xiàn)新節(jié)點(diǎn)所花費(fèi)的時(shí)間較為合理，所描述的方法在因抗干擾需求下全向天線不能使用或不符合要求時(shí)是很有用的。最后，需要特別指出，若在定向自組織網(wǎng)絡(luò)中融合頻譜動(dòng)態(tài)認(rèn)知技術(shù)與業(yè)務(wù)流優(yōu)化控制技術(shù)[7-8]，則可以大大提高定向空分網(wǎng)絡(luò)的抗干擾能力并進(jìn)一步提高帶寬資源的利用率。

[1] GELAL E,JAKLLARI G,KRISHNAMURTHY S V, et al, An Integrated Scheme for Fully-Directional Neighbor Discovery and Topology Management in Mobile Ad hoc Networks[C]. Canada: IEEE Mobile Ad Hoc and Sensor Systems, 2006:139-149.

[2] KHATIBI S,DEHGHAN M,POORMINA M.Quoram-based Pure directional Neighbor discovery in Self-organized ad hoc Networks[C]. Tehran: IEEE Telecommunications,2010:476-481.

[3] MURAWSKI R,FELEMBAN E,EKICI E, et al.Neighbor Discovery in Wireless Networks with Sectored Antennas[J].IEEE Ad Hoc Networks, 2012,1(10):1-18.

[4] ZHANG Zhensheng.Pure Directional Transmission and Reception Algorithms in Wireless Ad Hoc Networks with Directional Antennas[C]. USA:IEEE Communications,2005:3386-3390.

[5] 劉慶剛,李大雙,朱家成.多跳TDMA組網(wǎng)同步的分布式控制方法[J].通信技術(shù),2012,45(05):26-28.

[6] ZHANG Zhensheng, RYU B,NALLAMOTHU G, et al.Performance of All-Directional Transmission and Reception Algorithmsin Wireless Ad Hoc Networks with Directional Antennas[C]. USA: IEEE Military Communications, 2005:225-230..

[7] 梁燕芬,殷瑞祥.認(rèn)知無線電技術(shù)[J].信息安全與通信保密,2007 (03):121-124.

[8] 楊凌,張曉帆,諸愷,等.多跳對基于802.11的Ad Hoc網(wǎng)絡(luò) TCP流公平性的影響[J].通信技術(shù),2008,41(10):100-102.