無線自組網廣播通信方案綜述

魯頂柱 高靜

（廣東開放大學，廣東廣州，510091）

無線自組網廣泛用于軍事、災害救援，以及車載網、無人駕駛、智能物流等重要領域。其自身的多跳性、節點移動且分布不均、拓撲變化快的特征使節點間通信變得困難，因而廣播被廣泛使用。無線自組網中的諸多應用都具有群組性通信特征，廣播不僅被用來傳遞用戶消息，還被用于進行資源調度、密鑰分發、控制信息發布、路由查找。

除簡單泛洪（ flooding）[1]方案外，無線自組網中的廣播通信方案按其提供的可靠性保證情況可分為兩類[2]：絕對可靠的方案（deterministic schemes）、提供某種概率可靠保證的方案（probabilistic schemes）。

泛洪是一種最簡單的廣播方案。在泛洪方案中，每個節點都把收到的廣播數據向所有的鄰居節點廣播一次。由于無線信號傳輸在空間區域具有廣播特性，因而那些在空間位置上接近的節點進行泛洪可能會引發大量的信道競爭。在無線自組網中，RTS/CTS控制分組交互不適用，簡單的泛洪還可能造成大量傳輸碰撞，引發廣播風暴[3]。絕對可靠的廣播通信方案一般需要構建一種全局的拓撲結構（分發樹、轉發組）來分發廣播數據，保證百分之百的分組投遞率。但在節點頻繁移動的動態網絡環境中，數據轉發所依賴的拓撲結構容易被破壞，因而需要使用大量的控制報文進行維護，浪費了網絡帶寬和節點的處理能力。提供某種概率可靠保證的方案只收集網絡局部信息，而不需要維護全局的拓撲結構，受節點移動的影響小，對節點移動的敏感度低，能適應快速變化的網絡環境。其缺點是無法保障絕對可靠，不適合可靠性要求高的應用。

以下對這兩種類型的廣播通信方案的基本原理進行闡述，并用NS2模擬器對典型方案進行仿真，對比各方案的可靠性、開銷和端到端時延，分析各自的優缺點，歸納不同類型方案各自合適的應用場景。

一、絕對可靠的廣播通信方案

絕對可靠的廣播通信方案按其分發結構來的不同可以分為：（1）基于樹結構的廣播通信方案，（2）基于連通支配集的廣播通信方案。

（一）基于樹結構的廣播通信方案

基于樹結構的廣播通信方案[4][5]一般包含三個過程：（1）節點獲取網絡的局部拓撲信息；（2）按某種原則構建廣播數據的分發樹；（3）優化并維護廣播數據分發樹。在分發樹形成后，網絡中的節點就分為兩類：樹干節點和葉子節點。在基于樹結構的廣播通信方案中，源節點的廣播數據從樹根沿著樹干向整個網絡傳輸，只有樹干節點才需要轉發廣播數據，而葉子不參與轉發。不同于傳統有線網絡集中式構建分發樹，在無線自組網中的分發樹構建需要所有節點分布式協作來完成。分發樹的路徑選擇標準有多種：基于路徑長度、基于鏈路穩定性、基于時延或帶寬等。

MRT[5]算法構建廣播樹的主要思想是：選擇鄰居多的節點作為廣播樹上的樹干節點，以減少轉發次數和轉發節點數目。算法首先選擇鄰居最多的節點作為樹根，樹根的鄰居節點就變成了樹葉加入樹。然后在這些樹葉中選擇鄰居節點（未加入樹的節點）數最多的作為樹的一級中間節點。接下來在所有樹葉節點中用同樣的方法迭代選出二級中間節點。中間節點的選擇一直迭代下去，直到全網節點被完全覆蓋。MRT構建的廣播樹易受節點移動影響而頻繁重構，維護開銷大。

（二） 基于連通支配集的廣播通信方案

大部分絕對可靠的廣播通信方案都是基于連通支配集方法的。在無線自組網中連通支配集構造方法主要有三種：自減裁（self-pruning）方法，極大獨立集（maximum independent set）方法，鄰居指派（neighbor-designating）方法。

1.自減裁方法

自減裁算法[6-8]的主要思想是：首先構造一個粗糙的連通支配集，然后減裁掉其中的冗余節點，最終形成較為精簡的連通支配集。算法根據一個簡單的啟發式規則構造粗糙的連通支配集：如果節點v的任意兩個鄰居u，w之間都沒有直接相鄰，那節點v是支配節點。為了剔除粗糙的連通支配集中的大量冗余支配節點，文獻[8]提出通用的冗余節點檢測算法：若支配節點v的非支配節點鄰居均可通過優先級更高的中間節點連接到其它支配節點，則v是冗余節點。

自減裁算法存在一些難以解決的缺點：

（1）計算復雜度與節點最大度的三次方成正比，當網絡節點密度大時，計算復雜度高。

（2）節點在構造連通支配集的過程中需要收集鄰居節點的中間狀態信息，產生大量通信開銷。

（3）算法得到的連通支配集冗余度大，容易形成環路。

2.極大獨立集方法

I.stojmenovic算法[9]的主要思想是：先構造極大獨立集，再將構造的極大獨立集連接為連通支配集。算法將網絡中所有的節點劃分為支配節點和邊界節點，在邊界節點中，其兩跳范圍內的鄰節點至少有兩個支配節點。這樣，算法可以挑選一個或兩個邊界節點將已選的支配節點連接起來，組成連通支配集。算法中分布式獨立集構造過程如下：在算法開始時，節點將自己的優先級同鄰居節點的優先級進行比較，若其鄰居節點優先級均低于自己的優先級，則該節點確定自己為簇頭，并通知鄰居節點。節點優先級確定可以根據節點唯一的ID或節點度等不易重復、便于排序的數值大小來進行。鄰居節點在接收到來自簇頭的通知后，向自己的鄰居節點發送廣播，宣布自己為非簇頭節點。一旦節點收到所有優先級比自己低的鄰居節點廣播的非簇頭節點消息，則正式成為簇頭，并向鄰居節點轉發廣播數據。

通過以上過程可以分布式的將網絡劃分為多個極大獨立集，再利用加權邊法、支配區擴展法或其它的生成樹算法將這些極大獨立集連接起來，最終構成連通支配集。

3.鄰居指派方法

LBA算法[10]的主要思想是：每個節點最多指定一個鄰居節點來轉發廣播數據，被指定的節點必須轉發接收到的廣播數據；其他沒有被指定的節點則根據自己的鄰居剪枝狀況（廣播數據覆蓋狀況）自行決定是否轉發。為了評估鄰居節點被廣播數據覆蓋的狀況，每個節點都需要為每個廣播數據m維護一個列表。當節點u第一次接收到廣播數據m時，初始化列表，將所有鄰居節點ID添加到列表，并設置一個轉發時延來收集鄰居覆蓋信息。在轉發時延結束之前，節點u根據接收到的兩跳鄰居信息來更新列表，將已接收到廣播數據的鄰居節點從列表中剔除。如果在轉發時延結束時，列表還不為空，那么節點u就轉發廣播數據m，并指派列表中的一個節點作為下一個轉發節點；如果在轉發時延結束時，列表為空，節點u將不再轉發廣播數據m。顯而易見，在節點快速頻繁移動的情況下，LBA算法很難讓節點u正確判斷自己的鄰居是否被廣播數據m完全覆蓋，因此會轉發大量冗余廣播數據。

不論利用哪種方法產生連通支配集，算法復雜度都相當高，而且通信開銷大。相對于樹結構方案，基于連通過支配集的廣播通信方案對節點移動的適應性更強。但網絡拓撲快速頻繁改變也會導致連通支配集的破壞，維護開銷大，因而在節點高速移動的環境中性能受限。

二、提供某種概率可靠保證的廣播通信方案

提供某種概率可靠保證的廣播通信方案分四種：基于概率的方案（probability-based scheme），基于計數的方案（counter-based scheme），基于距離的方案（distance-based scheme），基于位置的方案（location-based scheme）。

（一）基于概率的方案

在基于概率的gossip[11]方案中，根據一些基本的拓撲信息，每個節點以固定的概率將接收到廣播數據向自己的所有鄰居節點廣播一次。不同于簡單泛洪中每個節點都轉發廣播數據，在gossip方案中，只有部分節點隨機地參與廣播數據的轉發，節約了帶寬，減少了沖突。但在異構的變化的網絡環境中，固定的轉發概率不能適應變化的網絡狀況，方案性能表現不佳。在DPA[12]，NKVB[13]方案中，節點的轉發概率會根據網絡環境動態改變，性能顯著優于固定概率的方案。

NKVB方案通過hello報文收集一跳內的鄰居信息，并據此實時計算節點的未覆蓋鄰居集合U(ni)，密度系數d(ni)、鄰居節點未覆蓋率Ru(ni)、未覆蓋鄰居數影響因子Fu(ni)等參數，利用所獲參數動態實時調整節點的多播數據轉發時延Td(ni)、基于鄰居覆蓋信息的轉發概率pk(ni)，基于節點速度的轉發概率pv(ni)。

其中N(nj)為節點nj的鄰居節點集合，β和（1-β）分別是鄰居節點未覆蓋率和未覆蓋鄰居數影響因子對廣播數據轉發概率的影響系數。

其中Δ是一個較小的時延常數，N(r)、N(ni)分別為節點r（r為ni的上游節點）和ni的鄰居節點集合，Rc(nri)為節點r和ni的公共鄰居比率。

其中vi為節點ni的移動速度，為ni的鄰居節點的平均移動速度，σ(ni)為ni的鄰居節點移動速度的標準差，vmax(ni)為ni的鄰居節點的最大移動速度。

（二） 基于計數的方案

在基于計數的廣播通信方案DCB[14]中，節點根據自已的鄰居節點數目來推測自己所在區域的節點密度狀況（節點密集、節點密度中等、節點稀疏），并根據節點密度狀況來設置接收重復廣播數據次數閾值。如果節點處于密集區域，其閾值設為Cmax；如果節點處于密度中等區域，其閾值設為Cmid；如果節點處于稀疏區域其閾值設為Cmin，其中，Cmax＞Cmid＞Cmid。DCB的核心思想是：當一個節點在隨機時延內重復接收到某個廣播數據的次數大于所設置的閾值，那就意味自己的鄰居節點應該都收到該廣播數據，將不再進行轉發，以降低冗余；如果一個節點在隨機時延內重復接收到某個廣播數據的次數小于自己的閾值，那就意味著該節點的部分鄰居節點還沒有接收到該廣播數據，需要為這部分鄰居節點轉發這個廣播數據，以保證可靠性。節點的快速移動易導致節點密度狀況變化，閾值因不能實時更新而變得不準確，影響方案的性能。

（三）基于距離的方案

在基于距離的廣播通信方案[15]中，首先根據網絡環境預定義兩種閾值空間：消息計數閾值空間（C1，C2，…，Cn）和節點距離閾值空間（D1，D2，…，Dn），并初始化距離門限D=D1。節點的廣播數據轉發概率是由自己與上一跳發送節點之間的相對距離決定的。該方案執行過程如下：

（1）當節點u第一次接收到來自節點v的廣播數據m時，初始化dmin為節點u、v之間距離，并將計數器count的值設為1。如果dmin＜D，執行步驟（5）；如果dmin≥D，節點v設置一個隨機時間，啟動計時器，執行步驟（2）。

（2）等待計時結束。如果在等待的過程中收到重復的廣播數據m，執行步驟（3）。計時結束后提交廣播數據m，等待廣播數據m的傳輸真正開始。

（3）count的值加1。

如果count的值小于C1，那么D=D1；

如果count的值小于C2，那么D=D2；

……

如果count的值小于Cn，那么D=Dn；

如果dmin＜D，執行步驟（5）；如果dmin≥D，執行步驟（2）。

（4）廣播數據m開始，過程結束。

（5）節點v放棄轉發廣播數據m。如果已開始計時，中斷計時。退出。

基于距離的廣播通信方案[16][17]同樣會因為節點移動造成消息計數閾值和距離閾值不準確，最終導致做出錯誤的轉發決定。

（四） 基于位置的方案

基于位置的廣播通信方案[18-20]通過設置廣播轉發延時來收集足夠的鄰居節點廣播數據覆蓋信息，以獲得精確的額外覆蓋率。

NCPR[20]方案通過在鄰居節點之間周期性的交換hello報文來收集鄰居節點信息。另外它還通過RREQ報文來收集鄰居節點信息：在轉發時延結束前，節點每接收到一個重復的RREQ報文時都會通過報文中的鄰居節點列表來更新自己的未覆蓋鄰居集合。在NCPR方案中，節點的轉發時延與上下游節點的公共鄰居數成反比。那么，擁有較多鄰居的節點的轉發時延通常較小，而這些節點的轉發概率卻相對較大，因此與鄰居較少的節點相比，它們需要在更短的時間內承擔更多的業務流量，信道競爭加強，易引起沖突。當業務負載加重時，沖突就表現得更加明顯。NCPR定義了網絡連通系數和額外覆蓋率兩個參數，通過這兩個參數來計算節點的廣播數據轉發概率。當節點密集，額外覆蓋率較小時，轉發概率應該取較小值；當節點稀疏，額外覆蓋率較大時，轉發概率應該取較大值。也即，網絡連通系數與轉發概率成反比，額外覆蓋率與轉發概率成正比。

三、仿真實驗與結果分析

本節采用NS-2（v2.35）對 flooding，NKVB及LBA、DCB、NCPR進行仿真。實驗模擬了節點移動速度對各方案的開銷、端到端時延、分組投遞率的影響，通過分析模擬結果來比較各方案的性能優劣。方案的性能參數定義如下：

（1）歸一化廣播開銷：每個節點轉發的所有報文（包括廣播數據報文與控制報文）的字節數與所轉發的廣播報文字節數之比。歸一化廣播開銷綜合反映了每個節點上廣播數據傳輸開銷和控制開銷大小。

（2）端到端平均時延：廣播數據從源節點發出到被所有節點接收的平均時間間隔。

（3）分組投遞率：收到廣播數據的節點數與網絡中所有節點數之比。

表1 模擬參數表

仿真采用了隨機路點移動模型（Random Waypoint Model）來模擬節點的移動，節點被固定在1,000 × 1,000 m2的正方形區域內移動。置信度設定為95%，詳細的模擬參數如表1所示。

1.節點移動速度對歸一化廣播開銷的影響

圖1 節點移動速度對歸一化廣播開銷的影響

圖1展示了節點移動速度對歸一化廣播開銷的影響。實驗結果表明：除 flooding方案外，其他方案的開銷都隨節點移動速度的加快而增加。節點的移動速度加快會導致網絡拓撲變化隨之加快，鏈路的穩定性下降，因而需要更多的控制開銷來維護網絡拓撲結構，保證有效的轉發路徑。而且，網絡拓撲變化所導致的鏈路斷開還會引發數據的重傳。

當節點移動速度低于5m/s時，網絡拓撲結構穩定，LBA維護支配集所需的控制開銷小，傳輸開銷也小。但隨著節點移動速度的增大，拓撲變化也逐漸加快，維護支配集的控制開銷增加。LBA為保證絕對可靠而發送大量冗余數據，造成沖突，傳輸開銷同時增大，因而其歸一化廣播開銷遠高于其他方案。 flooding方案中每個節點都需將收到的數據廣播一次，并且無控制開銷，所以歸一化廣播開銷不受節點移動速度影響。但 flooding方案轉發的冗余數據是所有方案中最多的一個，所以其開銷最大。

節點移動使得DCB方案對接收到的重復數據包計數錯誤，廣播閾值定義不準確，從而導致冗余的轉發并產生沖突，開銷增加。與LBA不同，DCB的控制開銷受節點移動影響小，因為它同NCPR、NKVB一樣不需要維護全局的拓撲結構。

NCPR、NKVB僅需少量Hello報文維持松散的鄰居關系，受節點移動影響小，在節點移動速度小于15m/s時，它們的控制開銷變化小。除了低速度環境，它們的開銷均比LBA和DCB少。NCPR方案的轉發時延和轉發概率計算方法容易導致負載集中于一部分節點，造成這部分節點需要在短時間內轉發較多的業務流量，信道競爭加強，沖突增加。NKVB方案轉發時延計算方法更加合理，使各個節點的負載分布更合理，降低了排隊等待時間，緩解了信道的競爭，減少了沖突，使廣播數據的轉發更為有效。相比NCPR方案，NKVB方案的傳輸開銷小，因此歸一化廣播開銷小。

2.節點移動速度對端到端平均時延的影響

圖2展示了節點移動速度對端到端平均時延的影響。隨著節點移動速度的增加，拓撲的改變引起了分組的丟失，導致重傳，增加了端到端平均時延。相比其他方案，對拓撲信息要求最高的LBA方案時延最大，DCB其次。NKVB的端到端平均時延明顯小于NCPR，因為NKVB的轉發時延選擇方法更能有效獲取鄰居覆蓋信息，并且它還選取了高速度節點參與廣播數據的轉發，加速了數據的傳播。廣播數據傳輸沖突是造成 flooding方案的端到端平均時延增加的主要原因。 flooding方案受節點移動影響小，圖中曲線基本保持水平，但其時延是所有方案中最長的。

圖2 節點移動速度對端到端平均時延的影響

3.節點移動速度對分組投遞率的影響

圖3展示了節點移動速度對分組投遞率的影響。實驗結果表明所有方案的分組投遞率都隨著節點移動速度的加快而減小。節點移動速度的加快使網絡拓撲變化更加頻繁，鏈路更加不穩定，投遞率因而下降。LBA方案在獲知全部鄰居節點都接收到廣播數據的情況下才放棄轉發，故節點的移動會導致其轉發概率比實際所需的值大。在移動性強的網絡環境中，LBA方案轉發概率嚴重偏高，而冗余又導致了沖突，分組投遞率下降。節點的移動使得DCB方案的重復接收廣播數據次數閾值和實際接收到的重復廣播數據次數都變得不準確，因而引起了冗余的廣播數據轉發，并導致沖突和開銷的增加，端到端平均時延增長，分組投遞率下降。NCPR、NKVB只需維持松散的鄰居關系，分組投遞率受節點移動影響小。Flooding方案的分組投遞率曲線基本水平，它受節點移動的影響最小，沖突是造成其分組投遞率低于NCPR、NKVB方案的主要原因。

圖3 節點移動速度對分組投遞率的影響

四、結論

在低速環境中，絕對可靠的廣播通信方案能提供高可靠性，數據傳輸效率高，其性能要優于提供某種概率可靠的方案。隨著節點移動速度增大，絕對可靠的方案開銷和時延上升，可靠性下降，節點移動速度越快，方案的性能越差。在節點快速移動的網絡環境中，提供某種概率可靠保證的方案的可靠性、端到端平均時延和開銷均優于絕對可靠的方案，它對節點移動的適應性更好。 flooding方案基本不受節點移動影響，能保持高可靠性，但開銷和時延都是最大的，它適用于高移動性、高可靠性要求的網絡環境。