王 浩，吳禮華，周鵬程

(1.武漢第二船舶設(shè)計研究所，湖北 武漢 430000;2.武漢大學(xué) 電子信息學(xué)院，湖北 武漢 430000)

0 引言

無線Mesh網(wǎng)絡(luò)[1]是一種特別的多跳無中心的自組織無線網(wǎng)絡(luò)，廣播在無線Mesh網(wǎng)絡(luò)中是一種非常重要的通信方式，用于信息的全網(wǎng)發(fā)放，被廣泛應(yīng)用于應(yīng)急和軍事通信網(wǎng)絡(luò)中。

目前傳統(tǒng)無線Mesh網(wǎng)絡(luò)廣播過程大都是基于全向天線[2]結(jié)構(gòu)與CSMA接入?yún)f(xié)議設(shè)計的[3]，但因為全向天線的能量不集中、消息冗余和沖突再加上CSMA接入方式的退避等待，導(dǎo)致廣播過程中存在時延大、可靠性和信道利用率不高等問題。

許多學(xué)者對基于定向天線的廣播算法展開研究，例如TREE-BASED算法[4]較好地減少了冗余，TDMA-NNI算法[5]采用預(yù)約廣播包轉(zhuǎn)發(fā)以避免沖突，BSRN算法[6]是基于概率和鄰居信息的混合算法，提高了廣播的可靠性。但他們都只針對某一性能指標進行改善，本文在微時隙劃分的時分復(fù)用基礎(chǔ)上采用適合多接口定向天線的空分復(fù)用，去優(yōu)化廣播的可靠性、時延、耗時及冗余率等性能指標，以提高廣播過程的綜合性能。

1 應(yīng)用場景分析

隨著信息化發(fā)展，在各種應(yīng)急場景下，對于可快速部署的無線Mesh網(wǎng)絡(luò)廣播的應(yīng)用急劇增加。圖 1為某應(yīng)用場景視圖，此類場景中上級組織對下級組織廣播實時命令消息，應(yīng)具有較高的優(yōu)先級，而下級節(jié)點之間又相互通信，節(jié)點間的距離較大且節(jié)點數(shù)量繁多。故在此類場景下的無線Mesh網(wǎng)絡(luò)廣播需考慮到以下幾點：網(wǎng)絡(luò)展開迅速、魯棒性強、延時可控、較遠的通信距離與較高的傳輸速率、傳輸可靠性有保障、成本較低。

目前使用較多的無線Mesh網(wǎng)絡(luò)廣播是基于全向天線的，采用CSMA接入?yún)f(xié)議，其優(yōu)勢在于時隙和信道的利用率較高，但CSMA的退避等待延時不可控會使廣播的延時不確定性很大，這對于一些應(yīng)急場景是很致命的。全向天線因為輻射范圍廣、功率不集中導(dǎo)致其傳輸距離和傳輸速率不夠，且因為多節(jié)點使用全向天線發(fā)送消息會有較大的消息冗余和消息沖突，這些都會使廣播過程的性能受到影響。

圖1 應(yīng)用場景視圖Fig.1 Application scenario

本文采用TDMA接入?yún)f(xié)議結(jié)合定向天線，雖然在一些文獻中提出這種組合以在原有基礎(chǔ)上減少等待延時并提高通信距離和傳輸速率，但是因為TDMA只是按照規(guī)劃地為各節(jié)點分配時隙，沒考慮到實際場景，信道和時隙利用率不高。在鄰居發(fā)現(xiàn)的時候，因為定向天線扇區(qū)波束較窄，鄰居發(fā)現(xiàn)采用的輪流掃描一周的模式，天線的對準以及鄰居發(fā)現(xiàn)的速度和完整性沒有得到保障。

因此，采取微時隙劃分的TDMA和在微時隙基礎(chǔ)上使用的多接口定向天線。定向天線的多個接口同時工作實現(xiàn)空分復(fù)用以提高鄰居發(fā)現(xiàn)速度，對各接口的天線進行更加精確地微時隙分配以避免沖突。在信道分配中對各網(wǎng)絡(luò)節(jié)點和信道進行優(yōu)先級劃分，按需分配時隙和信道以提高其利用率。

2 基于多接口定向天線的鄰居發(fā)現(xiàn)

2.1 多接口的定向天線

傳統(tǒng)廣播過程中使用的一般是全向天線，可以較為迅速地廣播信息，但是由于全向天線輻射范圍廣，天線功率全向散布，能量不夠集中，故其單跳傳輸距離不遠。此外，多節(jié)點通過全向天線發(fā)布消息的時候會造成較大的消息冗余與消息沖突。定向天線雖然可以提升傳輸距離和傳輸速率，但是多個發(fā)送天線同時向一個接收天線發(fā)送消息時的沖突問題與天線掃描耗時問題也未得到較好的解決。

定向天線分為自適應(yīng)陣列天線[7]與多波束轉(zhuǎn)換天線[8]，前者設(shè)計天線精確度更高，可跟蹤目標移動，但無線Mesh網(wǎng)絡(luò)中節(jié)點相對靜止，無需精確地跟蹤節(jié)點位置，并且陣列天線結(jié)構(gòu)復(fù)雜、成本較高，其兼容性不強。多波束轉(zhuǎn)換天線使用多個并行的波束將節(jié)點四周覆蓋，需要通信時切換到對應(yīng)扇區(qū)即可，天線結(jié)構(gòu)較簡單，成本低，兼容性強。

本文在傳統(tǒng)的多波束轉(zhuǎn)換天線的基礎(chǔ)上，為每個節(jié)點物理層配置多個接口，每個接口都有完整的協(xié)議棧，獨立工作互不影響，其模型如圖 2所示。采用多接口定向天線并結(jié)合TDMA可實現(xiàn)在空分復(fù)用的基礎(chǔ)上進行時分，在后文對每個時隙結(jié)合角度劃分到微時隙，以確保天線對準，一定范圍內(nèi)只有一個節(jié)點的多接口天線在不同的方向發(fā)送hello包，有效避免了沖突問題的同時提升了天線掃描速度。

圖2 定向天線結(jié)構(gòu)Fig.2 Structure of directional antenna

定向天線每個終端節(jié)點配置M個接口，每個接口控制N根天線，共配置K=M*N根定向天線。K根天線均勻覆蓋360°范圍。每根天線指向的波束角度是不變的，K的數(shù)值越大，則天線波束角度越小，能量越集中。

這種天線有如下限制：

① 不同接口上的定向天線可以同時工作，相同接口上的定向天線同一時刻只能工作一根。

② 同一時刻天線只能處于三種工作狀態(tài)中的一種，分別為發(fā)送狀態(tài)、接收狀態(tài)、空閑狀態(tài)，處于空閑狀態(tài)的扇區(qū)既不發(fā)送也不接收信號。

2.2 鄰居發(fā)現(xiàn)過程

本文的鄰居發(fā)現(xiàn)過程在MAC層實現(xiàn)，重新設(shè)計了天線掃描方式，采取了更適用于多接口和微時隙的空分復(fù)用模式，將定向天線的發(fā)現(xiàn)方式選擇為規(guī)劃型方式，解決了發(fā)送hello包沖突問題，并且加快了鄰居發(fā)現(xiàn)速度。

鄰居發(fā)現(xiàn)過程實現(xiàn)在MAC層，MAC層更有利于控制天線狀態(tài)以及節(jié)點占用信道的順序。為了防止天線收發(fā)消息沖突，故鄰居發(fā)現(xiàn)時應(yīng)滿足以下幾個條件：

① 定向天線波束寬度很窄，一對鄰居節(jié)點天線波束夾角需要滿足如下公式才能互相通信。

θ=(θ′+π)mod(2π),

其中，θ′是發(fā)送節(jié)點天線方向的夾角，θ是接收節(jié)點天線方向的夾角，即θ′與θ相差180°。

② 由于節(jié)點是半雙工的，節(jié)點需要確定當前時隙自己的狀態(tài)。一對鄰居節(jié)點的天線同一時刻要分別處于一發(fā)一收狀態(tài)，才能正常通信。

③ 同一時刻不能有多個鄰居節(jié)點朝一個節(jié)點同一波束范圍發(fā)消息，會產(chǎn)生碰撞。

2.3 天線掃描和時隙分配

相較傳統(tǒng)定向天線在各方向都掃描的輪流掃描方式，本文重新設(shè)計的天線掃描方式，讓物理層配置的多接口同時工作，提升掃描效率的同時避免了沖突。

為網(wǎng)絡(luò)中N個節(jié)點各自分配一個時隙，每個節(jié)點的n個接口上分別配有m根天線，則可將每個時隙分為m個微時隙，多個接口同時工作，時隙分配如圖 3所示。

圖3 鄰居發(fā)現(xiàn)時隙分配圖Fig.3 Time slot distribution diagram of finding neighbors

掃描過程以第一個節(jié)點發(fā)送hello包為例：在第一個時隙T(Id1，n(1,2,3，…，n),m1(a))發(fā)送hello包，其中T(Idi，nj，mk(a))表示第i個節(jié)點的第j個接口的第k根天線，a表示當前天線的角度，例如在第四個時隙，第一個節(jié)點的所有接口上的第4根天線處于發(fā)送hello包狀態(tài)，T(Id(2,3,4,…，N),n(1,2,3，…，n),m(a+π))處于接收hello狀態(tài)，如圖4所示，其中第一個節(jié)點的3個接口上4、9、14號天線處于發(fā)送hello包狀態(tài)，其他節(jié)點的11,12號、1,2號以及6,7號天線處于接受hello包狀態(tài)。在第一個節(jié)點的4號天線波束范圍內(nèi)，節(jié)點a的11,12號天線可接收到hello包，節(jié)點b的12號天線可接收到hello包。

同理，第5個時隙第一個節(jié)點所有接口上的第5根天線處于發(fā)送hello包狀態(tài)，其余節(jié)點所有接口上與第一個節(jié)點工作天線相差180°的天線處于接收hello包狀態(tài)。

按照此掃描方式，由于節(jié)點每個接口控制m根天線，因此每個節(jié)點需要分配m個時隙可將自己的hello包廣播給周圍節(jié)點。這種機制可以避免hello的沖突問題，并且多個方向的天線在同時工作，能有效提升了掃描的效率。

圖4 定向天線掃描示意圖Fig.4 Scanning diagram of directional antenna

3 節(jié)點分簇的分布式控制信道分配

無線Mesh網(wǎng)絡(luò)是無中心節(jié)點控制的，廣播過程一般采取洪泛機制，會產(chǎn)生大量的消息冗余，容易在多個節(jié)點向同一節(jié)點轉(zhuǎn)發(fā)消息時發(fā)生沖突，并且信道是不考慮實際情況平均分配的，容易造成信道資源的浪費。本文通過著色算法構(gòu)造規(guī)模較小的連通支配集結(jié)構(gòu)，在此基礎(chǔ)之上分簇，進行簡化鏈路，最后對節(jié)點設(shè)置優(yōu)先級，以安排節(jié)點天線工作狀態(tài)切換與信道的按優(yōu)先級分配。這樣信道分配機制業(yè)務(wù)量多、優(yōu)先級高的節(jié)點可以較早的進行工作狀態(tài)切換并分配較多的信道資源，在此機制下，廣播過程的時隙和信道利用率大大提升，并能根據(jù)節(jié)點的優(yōu)先級安排工作狀態(tài)切換。

3.1 選取連通支配集

本文采用改進的著色算法，選取部分節(jié)點來構(gòu)成網(wǎng)絡(luò)規(guī)模較小的連通支配集結(jié)構(gòu)[9-12]。定向天線一般是半雙工，且雙方需要處于“一收一發(fā)”狀態(tài)，所以本文采取基于定時器的連通支配集算法。通過節(jié)點的度設(shè)計定時器，利用定時器的優(yōu)先級來控制各節(jié)點天線的工作狀態(tài)切換時間，完成信息正常交互，并且只需要一跳鄰居信息就可構(gòu)造出規(guī)模較小的連通支配集結(jié)構(gòu)。

3.2 控制信道分配

在已構(gòu)成的連通支配集結(jié)構(gòu)上將其劃分為多個簇的集合，簡化鏈路，僅保留獨立集節(jié)點與連接集節(jié)點、普通節(jié)點與獨立集節(jié)點間的鏈路。在多接口定向天線模型下，網(wǎng)關(guān)節(jié)點利用其一跳拓撲信息設(shè)置節(jié)點優(yōu)先級，利用節(jié)點優(yōu)先級在網(wǎng)關(guān)節(jié)點上完成簇間無沖突的信道分配過程，然后簇頭節(jié)點根據(jù)其相鄰網(wǎng)關(guān)節(jié)點的分配結(jié)果獨立地完成簇內(nèi)信道分配。

為保證節(jié)點正常通信，時隙分配需滿足：① 每個節(jié)點的時隙不同于其一跳鄰居范圍節(jié)點分配的時隙。② 同一接口下的多條鏈路不能分配相同的時隙，不同接口下鏈路可以。③ 通信鏈路間至少分配一個雙向時隙。

原始鏈路簡化至控制信道著色后的過程如圖5～圖 8 所示，其中時隙分配因為鏈路是雙向的，因此分配的時隙數(shù)目是著色數(shù)的兩倍。根據(jù)著色矩陣，為節(jié)點分配時隙矩陣的規(guī)則如下：假如鏈路著色號C(u,v)=p,如果ID(u)ID(v)，則節(jié)點v占用2p-1時隙號發(fā)送，節(jié)點u占用2p-1時隙號接收；節(jié)點u占用2p時隙號發(fā)送，節(jié)點v占用2p時隙號接收。

圖5 原始鏈路Fig.5 Original link

圖6 進行連通支配集構(gòu)建后的鏈路Fig.6 Link constructed by the connected dominating set

圖7 進行簡化后的鏈路Fig.7 Simplified link

圖8 進行著色分配后的鏈路Fig.8 Link handled by coloring algorithm

原始鏈路中冗余和沖突較大，發(fā)現(xiàn)全網(wǎng)節(jié)點所需的時隙遠超優(yōu)化后鏈路。在已簡化但未進行著色分配的鏈路下，一共有17個節(jié)點和16條鏈路，因為一個通信鏈路需要雙向時隙，從1號節(jié)點開始到發(fā)現(xiàn)全網(wǎng)節(jié)點共需要32個時隙。在進行著色分配后的鏈路中，有5種著色號，只需要10個時隙即可覆蓋全網(wǎng)。

在這種分配機制下，通信較多的網(wǎng)關(guān)節(jié)點和簇頭節(jié)點會分配更多的時隙和信道，并根據(jù)著色矩陣進行時隙占用優(yōu)先級分配，有效地提升了時隙復(fù)用率和信道的利用率。

4 仿真結(jié)果與分析

采用QualNet進行仿真，仿真節(jié)點為32個，參數(shù)如表1所示。

表1 仿真參數(shù)配置

圖 9 ～圖 13給出了本文的廣播過程和TREE-BASED、TDMA-NNI和BSRN算法在多種指標下的仿真結(jié)果對比，可以看出本文廣播過程具有較低的廣播耗時和廣播包冗余率，并且廣播可靠性更高，節(jié)點數(shù)目越多，本文的廣播算法優(yōu)勢更加明顯。

圖9 廣播成功率對比Fig.9 Comparison of broadcast success rate

如圖9所示，隨著源廣播節(jié)點數(shù)目增加，廣播成功率也呈下降趨勢。由于本文和DMA-NNI算法都是通過TDMA時隙分配方式，在廣播消息前預(yù)約時隙，對鏈路進行清晰的信道劃分，不會存在沖突問題，廣播成功率較高。TDMA-NNI算法中給每條通信鏈路分配時隙，由于物理信道質(zhì)量的影響，網(wǎng)絡(luò)中每條通信鏈路都會存在一定數(shù)量的丟包，而本文廣播過程通過分簇的方式只給有效的鏈路分配信道，因此廣播成功率比 TDMA-NNI要高。

圖10 平均轉(zhuǎn)發(fā)節(jié)點比例對比Fig.10 Comparison of average ratio of forwarding nodes

如圖10所示，本文選擇出的轉(zhuǎn)發(fā)節(jié)點個數(shù)最少，并且選擇轉(zhuǎn)發(fā)節(jié)點所花費的網(wǎng)絡(luò)開銷也更少。本文廣播過程在構(gòu)建連通支配集時只需要一跳鄰居信息，并且在選擇轉(zhuǎn)發(fā)節(jié)點的過程中總是選擇節(jié)點連接度最大的節(jié)點為轉(zhuǎn)發(fā)節(jié)點，這樣保證選擇出來的轉(zhuǎn)發(fā)節(jié)點個數(shù)最少。其他算法均出現(xiàn)重復(fù)轉(zhuǎn)發(fā)，故耗時和轉(zhuǎn)發(fā)比例較大。

圖11 廣播耗時對比Fig.11 Comparison of broadcast time consuming

如圖11所示，本文提出的廣播過程廣播耗時最少，BSRN算法廣播耗時最大。這是因為 BSRN算法在廣播過程中會頻繁的與鄰居節(jié)點交換信息，根據(jù)鄰居節(jié)點的廣播成功率來動態(tài)指定節(jié)點的轉(zhuǎn)發(fā)概率，增加了廣播時延。當源廣播節(jié)點數(shù)目較少時，TDMA-NNI比TREE-BASED算法廣播耗時更少，這是因為TREE-BASED需要額外的開銷選擇控制節(jié)點。本文在選擇轉(zhuǎn)發(fā)節(jié)點的基礎(chǔ)上進一步實現(xiàn)了信道復(fù)用，利用多接口定向天線的優(yōu)勢并行發(fā)送消息，提高了時隙復(fù)用率。此外，本文廣播過程選擇轉(zhuǎn)發(fā)節(jié)點以及分簇，只給部分節(jié)點和鏈路分配時隙，減少了消息轉(zhuǎn)發(fā)跳數(shù)也減少了消息轉(zhuǎn)發(fā)數(shù)目，從而減少了廣播耗時。

如圖 12所示，本文廣播過程的廣播包冗余率最少,這是因為本文通過選擇控制節(jié)點和分簇方式，獲得廣播消息的路徑已經(jīng)確定，簇內(nèi)節(jié)點只能從簇頭節(jié)點處獲得廣播消息，而簇頭節(jié)點從其相鄰的網(wǎng)關(guān)節(jié)點獲得廣播消息，廣播消息的冗余量最少。

圖12 廣播包冗余率對比Fig.12 Comparison of broadcast packet redundancy rate

如圖 13所示,相比較其他幾種算法，本文提出的廣播過程節(jié)點最大負載率最小。這是因為本文通過選擇控制節(jié)點減少了廣播消息的冗余，并且通過分簇的方式，約束了廣播消息轉(zhuǎn)發(fā)的路徑，進一步減少了節(jié)點收到的廣播消息總個數(shù)。

圖13 節(jié)點最大負載率對比Fig.13 Comparison of node maximum load rate

5 結(jié)論

本文對傳統(tǒng)無線Mesh廣播過程進行改進，綜合采用了多種現(xiàn)有研究中的方法以提升廣播過程性能，定向天線有效減少消息冗余，微時隙劃分可以避免使用定向天線會出現(xiàn)的消息沖突，相應(yīng)也使用控制信道劃分以提高TDMA的時隙利用率。仿真結(jié)果表明，這一技術(shù)有效提升了廣播過程的效率，并可以實現(xiàn)廣播中的按需分配。