無線自組網(wǎng)廣播通信方案綜述

魯頂柱 高靜

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

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

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

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

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

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

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

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

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

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

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

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

1.自減裁方法

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

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

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

（2）節(jié)點在構造連通支配集的過程中需要收集鄰居節(jié)點的中間狀態(tài)信息，產(chǎn)生大量通信開銷。

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

2.極大獨立集方法

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

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

3.鄰居指派方法

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

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

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

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

（一）基于概率的方案

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

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

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

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

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

（二） 基于計數(shù)的方案

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

（三）基于距離的方案

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

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

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

（3）count的值加1。

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

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

……

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

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

（4）廣播數(shù)據(jù)m開始，過程結束。

（5）節(jié)點v放棄轉發(fā)廣播數(shù)據(jù)m。如果已開始計時，中斷計時。退出。

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

（四） 基于位置的方案

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

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

三、仿真實驗與結果分析

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

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

（2）端到端平均時延：廣播數(shù)據(jù)從源節(jié)點發(fā)出到被所有節(jié)點接收的平均時間間隔。

（3）分組投遞率：收到廣播數(shù)據(jù)的節(jié)點數(shù)與網(wǎng)絡中所有節(jié)點數(shù)之比。

表1 模擬參數(shù)表

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

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

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

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

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

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

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

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

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

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

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

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

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

四、結論

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