基于TDMA和定向天線的無線Mesh網絡廣播技術

王 浩，吳禮華，周鵬程

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

0 引言

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

目前傳統無線Mesh網絡廣播過程大都是基于全向天線[2]結構與CSMA接入協議設計的[3]，但因為全向天線的能量不集中、消息冗余和沖突再加上CSMA接入方式的退避等待，導致廣播過程中存在時延大、可靠性和信道利用率不高等問題。

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

1 應用場景分析

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

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

圖1 應用場景視圖Fig.1 Application scenario

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

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

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

2.1 多接口的定向天線

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

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

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

圖2 定向天線結構Fig.2 Structure of directional antenna

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

這種天線有如下限制：

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

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

2.2 鄰居發(fā)現過程

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

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

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

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

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

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

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

2.3 天線掃描和時隙分配

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

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

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

3.1 選取連通支配集

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

3.2 控制信道分配

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

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

原始鏈路簡化至控制信道著色后的過程如圖5～圖 8 所示，其中時隙分配因為鏈路是雙向的，因此分配的時隙數目是著色數的兩倍。根據著色矩陣，為節(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 進行連通支配集構建后的鏈路Fig.6 Link constructed by the connected dominating set

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

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

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

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

4 仿真結果與分析

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

表1 仿真參數配置

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

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

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

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

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

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

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

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

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

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

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

5 結論

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