魯頂柱 高靜

（廣東開(kāi)放大學(xué)，廣東廣州，510091）

無(wú)線自組網(wǎng)廣泛用于軍事、災(zāi)害救援，以及車載網(wǎng)、無(wú)人駕駛、智能物流等重要領(lǐng)域。其自身的多跳性、節(jié)點(diǎn)移動(dòng)且分布不均、拓?fù)渥兓斓奶卣魇构?jié)點(diǎn)間通信變得困難，因而廣播被廣泛使用。無(wú)線自組網(wǎng)中的諸多應(yīng)用都具有群組性通信特征，廣播不僅被用來(lái)傳遞用戶消息，還被用于進(jìn)行資源調(diào)度、密鑰分發(fā)、控制信息發(fā)布、路由查找。

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

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

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

一、絕對(duì)可靠的廣播通信方案

絕對(duì)可靠的廣播通信方案按其分發(fā)結(jié)構(gòu)來(lái)的不同可以分為：（1）基于樹(shù)結(jié)構(gòu)的廣播通信方案，（2）基于連通支配集的廣播通信方案。

（一）基于樹(shù)結(jié)構(gòu)的廣播通信方案

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

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

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

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

1.自減裁方法

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

自減裁算法存在一些難以解決的缺點(diǎn)：

（1）計(jì)算復(fù)雜度與節(jié)點(diǎn)最大度的三次方成正比，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度大時(shí)，計(jì)算復(fù)雜度高。

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

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

2.極大獨(dú)立集方法

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

通過(guò)以上過(guò)程可以分布式的將網(wǎng)絡(luò)劃分為多個(gè)極大獨(dú)立集，再利用加權(quán)邊法、支配區(qū)擴(kuò)展法或其它的生成樹(shù)算法將這些極大獨(dú)立集連接起來(lái)，最終構(gòu)成連通支配集。

3.鄰居指派方法

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

不論利用哪種方法產(chǎn)生連通支配集，算法復(fù)雜度都相當(dāng)高，而且通信開(kāi)銷大。相對(duì)于樹(shù)結(jié)構(gòu)方案，基于連通過(guò)支配集的廣播通信方案對(duì)節(jié)點(diǎn)移動(dòng)的適應(yīng)性更強(qiáng)。但網(wǎng)絡(luò)拓?fù)淇焖兕l繁改變也會(huì)導(dǎo)致連通支配集的破壞，維護(hù)開(kāi)銷大，因而在節(jié)點(diǎn)高速移動(dòng)的環(huán)境中性能受限。

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

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

（一）基于概率的方案

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

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

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

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

其中vi為節(jié)點(diǎn)ni的移動(dòng)速度，為ni的鄰居節(jié)點(diǎn)的平均移動(dòng)速度，σ(ni)為ni的鄰居節(jié)點(diǎn)移動(dòng)速度的標(biāo)準(zhǔn)差，vmax(ni)為ni的鄰居節(jié)點(diǎn)的最大移動(dòng)速度。

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

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

（三）基于距離的方案

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

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

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

（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開(kāi)始，過(guò)程結(jié)束。

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

基于距離的廣播通信方案[16][17]同樣會(huì)因?yàn)楣?jié)點(diǎn)移動(dòng)造成消息計(jì)數(shù)閾值和距離閾值不準(zhǔn)確，最終導(dǎo)致做出錯(cuò)誤的轉(zhuǎn)發(fā)決定。

（四） 基于位置的方案

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

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

三、仿真實(shí)驗(yàn)與結(jié)果分析

本節(jié)采用NS-2（v2.35）對(duì) flooding，NKVB及LBA、DCB、NCPR進(jìn)行仿真。實(shí)驗(yàn)?zāi)M了節(jié)點(diǎn)移動(dòng)速度對(duì)各方案的開(kāi)銷、端到端時(shí)延、分組投遞率的影響，通過(guò)分析模擬結(jié)果來(lái)比較各方案的性能優(yōu)劣。方案的性能參數(shù)定義如下：

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

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

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

表1 模擬參數(shù)表

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

1.節(jié)點(diǎn)移動(dòng)速度對(duì)歸一化廣播開(kāi)銷的影響

圖1 節(jié)點(diǎn)移動(dòng)速度對(duì)歸一化廣播開(kāi)銷的影響

圖1展示了節(jié)點(diǎn)移動(dòng)速度對(duì)歸一化廣播開(kāi)銷的影響。實(shí)驗(yàn)結(jié)果表明：除 flooding方案外，其他方案的開(kāi)銷都隨節(jié)點(diǎn)移動(dòng)速度的加快而增加。節(jié)點(diǎn)的移動(dòng)速度加快會(huì)導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓S之加快，鏈路的穩(wěn)定性下降，因而需要更多的控制開(kāi)銷來(lái)維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，保證有效的轉(zhuǎn)發(fā)路徑。而且，網(wǎng)絡(luò)拓?fù)渥兓鶎?dǎo)致的鏈路斷開(kāi)還會(huì)引發(fā)數(shù)據(jù)的重傳。

當(dāng)節(jié)點(diǎn)移動(dòng)速度低于5m/s時(shí)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)穩(wěn)定，LBA維護(hù)支配集所需的控制開(kāi)銷小，傳輸開(kāi)銷也小。但隨著節(jié)點(diǎn)移動(dòng)速度的增大，拓?fù)渥兓仓饾u加快，維護(hù)支配集的控制開(kāi)銷增加。LBA為保證絕對(duì)可靠而發(fā)送大量冗余數(shù)據(jù)，造成沖突，傳輸開(kāi)銷同時(shí)增大，因而其歸一化廣播開(kāi)銷遠(yuǎn)高于其他方案。 flooding方案中每個(gè)節(jié)點(diǎn)都需將收到的數(shù)據(jù)廣播一次，并且無(wú)控制開(kāi)銷，所以歸一化廣播開(kāi)銷不受節(jié)點(diǎn)移動(dòng)速度影響。但 flooding方案轉(zhuǎn)發(fā)的冗余數(shù)據(jù)是所有方案中最多的一個(gè)，所以其開(kāi)銷最大。

節(jié)點(diǎn)移動(dòng)使得DCB方案對(duì)接收到的重復(fù)數(shù)據(jù)包計(jì)數(shù)錯(cuò)誤，廣播閾值定義不準(zhǔn)確，從而導(dǎo)致冗余的轉(zhuǎn)發(fā)并產(chǎn)生沖突，開(kāi)銷增加。與LBA不同，DCB的控制開(kāi)銷受節(jié)點(diǎn)移動(dòng)影響小，因?yàn)樗琋CPR、NKVB一樣不需要維護(hù)全局的拓?fù)浣Y(jié)構(gòu)。

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

2.節(jié)點(diǎn)移動(dòng)速度對(duì)端到端平均時(shí)延的影響

圖2展示了節(jié)點(diǎn)移動(dòng)速度對(duì)端到端平均時(shí)延的影響。隨著節(jié)點(diǎn)移動(dòng)速度的增加，拓?fù)涞母淖円鹆朔纸M的丟失，導(dǎo)致重傳，增加了端到端平均時(shí)延。相比其他方案，對(duì)拓?fù)湫畔⒁笞罡叩腖BA方案時(shí)延最大，DCB其次。NKVB的端到端平均時(shí)延明顯小于NCPR，因?yàn)镹KVB的轉(zhuǎn)發(fā)時(shí)延選擇方法更能有效獲取鄰居覆蓋信息，并且它還選取了高速度節(jié)點(diǎn)參與廣播數(shù)據(jù)的轉(zhuǎn)發(fā)，加速了數(shù)據(jù)的傳播。廣播數(shù)據(jù)傳輸沖突是造成 flooding方案的端到端平均時(shí)延增加的主要原因。 flooding方案受節(jié)點(diǎn)移動(dòng)影響小，圖中曲線基本保持水平，但其時(shí)延是所有方案中最長(zhǎng)的。

圖2 節(jié)點(diǎn)移動(dòng)速度對(duì)端到端平均時(shí)延的影響

3.節(jié)點(diǎn)移動(dòng)速度對(duì)分組投遞率的影響

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

圖3 節(jié)點(diǎn)移動(dòng)速度對(duì)分組投遞率的影響

四、結(jié)論

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