適用于異構(gòu)移動自組織網(wǎng)絡(luò)的多信道廣播算法*

張 茂，王 海，董 超，馬彥慶

(中國人民解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

適用于異構(gòu)移動自組織網(wǎng)絡(luò)的多信道廣播算法*

張 茂，王 海，董 超，馬彥慶

(中國人民解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

在異構(gòu)移動自組織網(wǎng)絡(luò)中，為滿足多樣的用戶需求，提高網(wǎng)絡(luò)容量，節(jié)點(diǎn)往往配備了多種信道。傳統(tǒng)的廣播機(jī)制(如洪泛、基于節(jié)點(diǎn)的連通支配集和信道向量等)往往采用基于節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式，即對節(jié)點(diǎn)所擁有的多個信道采取一視同仁的態(tài)度，在收到消息后將直接在其所有信道上進(jìn)行轉(zhuǎn)發(fā)，導(dǎo)致其無法充分利用各個信道的性能優(yōu)勢，以及在某些不必要信道上的冗余轉(zhuǎn)發(fā)。為了充分發(fā)揮多信道網(wǎng)絡(luò)的優(yōu)勢，降低冗余轉(zhuǎn)發(fā)帶來的開銷，提出了一種基于信道的連通支配集構(gòu)造機(jī)制，該機(jī)制采用了基于信道的轉(zhuǎn)發(fā)方式，在選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的同時也將對轉(zhuǎn)發(fā)信道進(jìn)行選擇，并以此為基礎(chǔ)提出了適用于異構(gòu)移動自組織網(wǎng)絡(luò)的廣播算法。仿真結(jié)果表明，與原有的基于連通支配集和信道向量的廣播算法相比，文中的算法分別降低了64.15%和13.95%的廣播開銷，并且，與信道向量相比，網(wǎng)絡(luò)吞吐量提升了14.1%。

廣播；多信道；連通支配集；移動自組織網(wǎng)絡(luò)

0 引言

在移動自組織網(wǎng)絡(luò)(MANETs)中，為了滿足用戶多樣的通信需求，盡可能地提高網(wǎng)絡(luò)容量，多信道移動自組織網(wǎng)絡(luò)應(yīng)運(yùn)而生[1]。實(shí)際應(yīng)用過程中，多信道移動自組織網(wǎng)絡(luò)的異構(gòu)性特征主要體現(xiàn)在以下兩個方面：一是網(wǎng)絡(luò)中的信道性能各異，異構(gòu)特征明顯；二是可能存在單個節(jié)點(diǎn)同時擁有多個信道的情況。

現(xiàn)有的廣播策略，如洪泛法[2]，以及基于連通支配集的廣播等，在網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)節(jié)點(diǎn)第一次收到廣播消息時，將會立即在其所有的信道上向全部鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，即基于節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式，進(jìn)而導(dǎo)致其不能適用于廣泛存在的多信道網(wǎng)絡(luò)環(huán)境。原因主要有兩個：首先，基于節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式將簡單地在節(jié)點(diǎn)的所有信道上進(jìn)行轉(zhuǎn)發(fā)，即對節(jié)點(diǎn)所擁有的多個信道采用一視同仁的態(tài)度，因而導(dǎo)致在不必要信道上的冗余傳輸，增大廣播開銷。同時，基于節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式不能有效地區(qū)分節(jié)點(diǎn)所配備的多個信道之間的性能差異，因而不能為路由消息的轉(zhuǎn)發(fā)選擇最優(yōu)的信道。因此，提出一種可用于多信道MANETs的高效廣播機(jī)制是很有必要的。

文獻(xiàn)[3]中已經(jīng)證明，如果將網(wǎng)絡(luò)拓?fù)涑橄蟪梢粋€圖，在單信道網(wǎng)絡(luò)中，求解最小轉(zhuǎn)發(fā)節(jié)點(diǎn)集合的問題等價于求圖的最小連通支配集問題。然而，連通支配集的求解已經(jīng)被證明是一個NP-hard問題[4-5]。為了解決這個問題并求得網(wǎng)絡(luò)中最小的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合，文獻(xiàn)[6-8]中提出了分布式的啟發(fā)式算法。這些算法基本上都是局限于單信道的網(wǎng)絡(luò)環(huán)境，而對多信道的環(huán)境中的廣播問題關(guān)注很少。這也是為什么傳統(tǒng)的基于連通支配集的廣播算法，往往只考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇，而不重視轉(zhuǎn)發(fā)信道的選擇的原因。本文將這種基于節(jié)點(diǎn)的連通支配集叫做Node-based CDS(N-CDS)。相比于其他廣播機(jī)制如隨機(jī)廣播[9]和基于計數(shù)器廣播[10]等，基于連通支配集的廣播能夠最大程度地減少轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量。如果能夠在此基礎(chǔ)上，對轉(zhuǎn)發(fā)節(jié)點(diǎn)的轉(zhuǎn)發(fā)信道進(jìn)行合理的選擇，就能夠解決由多信道環(huán)境帶來的冗余傳輸問題，從而將基于連通支配集的廣播策略的適用范圍從單信道環(huán)境拓展到多信道環(huán)境中。

為了減少由多信道環(huán)境帶來的冗余傳輸，降低廣播開銷并增加網(wǎng)絡(luò)吞吐量，本文提出了一種分布式的基于信道的連通支配集(Channel-based CDS, C-CDS)的構(gòu)建算法，并以此為基礎(chǔ)提出了一種適用于多信道MANETs的廣播機(jī)制。在構(gòu)建過程中，為了與多信道網(wǎng)絡(luò)環(huán)境相適應(yīng)，本文新提出了一種分布式的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇機(jī)制，并合理地選擇轉(zhuǎn)發(fā)信道，而不是簡單地在所有信道上進(jìn)行轉(zhuǎn)發(fā)。同時，為了減少M(fèi)ANETs動態(tài)場景中節(jié)點(diǎn)間的交互開銷，在C-CDS的構(gòu)造過程中，將引入信道向量(Channel Vector, CV)機(jī)制來完成節(jié)點(diǎn)間信息的交互。

1 相關(guān)工作

在多信道環(huán)境中，為了解決由多信道網(wǎng)絡(luò)環(huán)境帶來的冗余傳輸問題，文獻(xiàn)[11]提出了一個基于信道向量的廣播機(jī)制。這是一個簡單而又高效的機(jī)制，旨在通過與鄰居節(jié)點(diǎn)交換簡要的節(jié)點(diǎn)和信道信息來降低節(jié)點(diǎn)的鄰居發(fā)現(xiàn)開銷和廣播開銷。通過與其鄰居交互信道向量信息，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都能構(gòu)建一個信道向量矩陣，進(jìn)而幫助節(jié)點(diǎn)更加明智地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)及其轉(zhuǎn)發(fā)信道，減少冗余傳輸。然而，由于該機(jī)制的集中式特性使得基于信道向量的廣播機(jī)制的性能將會在一定程度上受限于中心節(jié)點(diǎn)的效率。

連通支配集的求解是一個NP-hard問題。因此，文獻(xiàn)[3，12]提出了一種分布式的連通支配集的近似求解算法，使得用相對簡單的方式來求解連通支配集問題的近似解成為可能。其他的一些工作則把重心放在了優(yōu)化連通支配集生成的方式以及生成過程中的計算復(fù)雜度上，進(jìn)而使其能夠適應(yīng)不同的用戶需求。但是，上述機(jī)制都是典型的基于節(jié)點(diǎn)的連通支配集機(jī)制。每個轉(zhuǎn)發(fā)節(jié)點(diǎn)將直接在其所有的信道上進(jìn)行消息轉(zhuǎn)發(fā)，而不會單獨(dú)考慮其每個信道上的連通狀況。

因此，如何改進(jìn)連通支配集的構(gòu)造過程使其能夠適應(yīng)多信道的網(wǎng)絡(luò)環(huán)境，是本文要解決的第一個問題。同時，連通支配集問題是一個NP-hard問題，因此本文提出了一種分布式的轉(zhuǎn)發(fā)節(jié)點(diǎn)及信道的選擇算法來減少轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量和由多信道環(huán)境造成的冗余傳輸，并以此為基礎(chǔ)新構(gòu)建了一個基于信道的連通支配集。為了進(jìn)一步減少節(jié)點(diǎn)間的信息交互開銷，本文引入了CV機(jī)制來完成節(jié)點(diǎn)間的信息交互。值得一提的是，CV消息將直接包含在Hello包中，這就意味著不再需要單獨(dú)地為其制定新的消息格式，增加了本機(jī)制的適用性。

2 基于信道的連通支配集

在多信道的網(wǎng)絡(luò)環(huán)境中，連通支配集的構(gòu)造將會更加復(fù)雜。如圖1所示，整個網(wǎng)絡(luò)都可以被D點(diǎn)或者E點(diǎn)(圖中灰色節(jié)點(diǎn))所覆蓋。根據(jù)現(xiàn)有的CDS構(gòu)造規(guī)則，這兩個點(diǎn)中的任意一個點(diǎn)都可以構(gòu)成一個該網(wǎng)絡(luò)的連通支配集。但是，不同的選擇可能會導(dǎo)致網(wǎng)絡(luò)性能上的差異。例如，如果選擇節(jié)點(diǎn)D作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，并構(gòu)成圖中所示網(wǎng)絡(luò)的連通支配集。當(dāng)節(jié)點(diǎn)D收到來自節(jié)點(diǎn)F的消息時，節(jié)點(diǎn)D將會在它所擁有的全部信道，信道1、2和3上進(jìn)行3次轉(zhuǎn)發(fā)，來對網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行覆蓋。但是，通過觀察后可以發(fā)現(xiàn)，如果選擇節(jié)點(diǎn)E作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，僅僅需要在信道1和2上進(jìn)行兩次轉(zhuǎn)發(fā)就可以達(dá)到同樣的效果。與節(jié)點(diǎn)D相比，節(jié)點(diǎn)E使用了更少的轉(zhuǎn)發(fā)信道去覆蓋相同或者更多的鄰居節(jié)點(diǎn)，因而產(chǎn)生了更少的廣播開銷。然而，現(xiàn)有的CDS構(gòu)造方法并不能區(qū)分節(jié)點(diǎn)D和E的不同，更不能在多信道環(huán)境中合理地選出轉(zhuǎn)發(fā)節(jié)點(diǎn)。本文提出的基于信道的連通支配集構(gòu)造機(jī)制可以很好地解決這個問題。在選擇合適的節(jié)點(diǎn)(如本例中的節(jié)點(diǎn)E)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的同時，會盡可能地將轉(zhuǎn)發(fā)節(jié)點(diǎn)集合中的冗余節(jié)點(diǎn)(如本例中的節(jié)點(diǎn)D)移除。

圖1 多信道MANETs網(wǎng)絡(luò)拓?fù)鋵?shí)例

雖然改進(jìn)后的CDS構(gòu)造機(jī)制以相對較低的廣播開銷完成了CDS的構(gòu)造，但是其基于節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式依然不適用于多信道網(wǎng)絡(luò)環(huán)境。因?yàn)椋诨诠?jié)點(diǎn)的連通支配集廣播機(jī)制中，節(jié)點(diǎn)不會考慮其所擁有的信道間的區(qū)別，并且僅僅會直接在其所有的信道上進(jìn)行轉(zhuǎn)發(fā)。事實(shí)證明，并不是每個信道上的消息轉(zhuǎn)發(fā)都是必要的，因此這種一視同仁的轉(zhuǎn)發(fā)方式可能會在多信道網(wǎng)絡(luò)中造成大量的冗余傳輸。如圖1所示，節(jié)點(diǎn)E僅僅使用信道2就可以完成對整個網(wǎng)絡(luò)的覆蓋。這也意味著，如果采用傳統(tǒng)的基于節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式，則會造成節(jié)點(diǎn)E在信道1上的冗余轉(zhuǎn)發(fā)，進(jìn)而增加廣播開銷并造成帶寬資源的浪費(fèi)。為了解決上述問題，本文提出了一種基于信道的連通支配集機(jī)制，并以此為基礎(chǔ)提出了一個適用于多信道MANETs的廣播算法。

2.1網(wǎng)絡(luò)模型

下面將對網(wǎng)絡(luò)模型進(jìn)行介紹。首先，將網(wǎng)絡(luò)視作一個無向圖G(V，E)，由節(jié)點(diǎn)集合V以及節(jié)點(diǎn)間邊的集合E組成。N(v)={i(v,i)∈E}，表示節(jié)點(diǎn)v的鄰居集合(不包括節(jié)點(diǎn)v本身)，集合N[v]=N(v)+v(包括節(jié)點(diǎn)v)被稱作節(jié)點(diǎn)v的封閉鄰居集合。

然后，本文定義了節(jié)點(diǎn)的一個全新的變量——ab(v)，來描述節(jié)點(diǎn)在多信道網(wǎng)絡(luò)中的鄰居覆蓋能力。通過計算比較網(wǎng)絡(luò)中每個節(jié)點(diǎn)的ab(v)值，可以有效地在多信道環(huán)境中選出合適的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。

(1)

其中，nc(v)表示節(jié)點(diǎn)v擁有的信道類型數(shù)量。N(v)代表節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)的數(shù)量。根據(jù)上述公式可知，當(dāng)節(jié)點(diǎn)v的信道類型少，鄰居數(shù)量多時，ab(v)值將會更大，節(jié)點(diǎn)的鄰居覆蓋能力也會越強(qiáng)。換句話說，節(jié)點(diǎn)用盡可能少的信道數(shù)量覆蓋更多的鄰居，這也是本機(jī)制將優(yōu)先選擇ab(v)大的節(jié)點(diǎn)(如圖1中的節(jié)點(diǎn)E)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的原因。

然后，定義了參數(shù)cnn(v)去描述節(jié)點(diǎn)v在其所有信道上的最大鄰居數(shù)量。其中Nc(v)是節(jié)點(diǎn)v在其信道c上的鄰居數(shù)量。

cnn(v)=max(Nc(v))

(2)

2.2基于信道的連通支配集的構(gòu)造

基于信道的連通支配集的構(gòu)造包含兩步。第一，本文提出了一個更為優(yōu)化的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇機(jī)制來完成連通支配集的構(gòu)造。第二，為了減少在不必要信道上的冗余傳輸，本文提出了一個轉(zhuǎn)發(fā)信道選擇算法，進(jìn)而完成了基于信道的連通支配集的構(gòu)造。

文獻(xiàn)[10]提出了一個簡單的分布式算法，用于移動自組織網(wǎng)絡(luò)中連通支配集的構(gòu)造。在算法運(yùn)行過程中，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都將會被標(biāo)記成T(標(biāo)記)或者F(未標(biāo)記)。標(biāo)記過程如下：

(1)在初始階段，將節(jié)點(diǎn)集合V中的每個節(jié)點(diǎn)都標(biāo)記為F；

(2)每個節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)交互鄰居信息；

(3)如果某個節(jié)點(diǎn)存在兩個互不連通的鄰居，則將其標(biāo)記為T。

將所有被標(biāo)記為T的節(jié)點(diǎn)組成的新的節(jié)點(diǎn)集合記作V′，V′={vv∈V,m(v)=T}，這些節(jié)點(diǎn)及其邊的集合將構(gòu)成一個新的圖G′(V′，E′)，且圖G′是原圖G的一個子圖。很容易證明，集合V′目前已經(jīng)是圖G的一個連通支配集，但是與最小連通支配集相去甚遠(yuǎn)。因此，基于這個簡單的構(gòu)造算法，本文提出了兩條規(guī)則來減少現(xiàn)有連通支配集的規(guī)模。下一步，將討論如何用下面的兩個規(guī)則去除現(xiàn)存CDS中的冗余節(jié)點(diǎn)。

規(guī)則1：若圖G′中存在兩個被標(biāo)記為T的節(jié)點(diǎn)v和u。節(jié)點(diǎn)v將被重新標(biāo)記為F如果下面的條件之一成立：

(1)N[v]?N[u] inG′且ab(v)

(2)N[v]?N[u] inG′且cnn(v)

(3)N[v]?N[u]inG′且id(v)

當(dāng)v的鄰居集合及其本身包含于其鄰居節(jié)點(diǎn)u的封閉鄰居集合時，若節(jié)點(diǎn)v的鄰居覆蓋能力值小于u，即ab(v)

如圖2(a)所示，按照前述規(guī)則，在標(biāo)記過程完成后，節(jié)點(diǎn)u和v都會被標(biāo)記為T。顯然，u的封閉鄰居節(jié)點(diǎn)集合包含于v的封閉鄰居節(jié)點(diǎn)集合。然后，通過分別計算節(jié)點(diǎn)v和u的鄰居覆蓋能力值，可以知道ab(v)

圖2 規(guī)則1和2的舉例說明

此外，在圖2(b)中，節(jié)點(diǎn)v和u的鄰居覆蓋能力相同。顯然，節(jié)點(diǎn)u僅僅需要在信道2上轉(zhuǎn)發(fā)1次就可以完成鄰居覆蓋，而節(jié)點(diǎn)u則需要在不同的信道上轉(zhuǎn)發(fā)兩次才能夠達(dá)到相同的效果。為了減少網(wǎng)絡(luò)的廣播開銷，需要盡可能的先選擇像u一樣的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，并且將與節(jié)點(diǎn)v類似的節(jié)點(diǎn)從現(xiàn)有連通支配集中移除。因此本文引入了參數(shù)cnn來解決兩個節(jié)點(diǎn)的鄰居覆蓋能力相同的情況。在本例中，cnn(u)>cnn(v)，所以節(jié)點(diǎn)v將被移除。

規(guī)則2：假設(shè)節(jié)點(diǎn)u和w是節(jié)點(diǎn)v的兩個被標(biāo)記為T的鄰居。v可以被標(biāo)記為F并從現(xiàn)有的連通支配集中被移除，當(dāng)且僅當(dāng)以下情況出現(xiàn)：

(1)N(v)?N(u)∪N(w)，但N(u)?N(v)∪N(w)且N(w)?N(v)∪N(u) inG′；

(2)N(v)?N(u)∪N(w)且N(u)?N(v)∪N(w)，但是N(w)?N(v)∪N(u) inG′，且如下條件之一成立:

① ab(v)

(3)N(v)?N(u)∪N(w),N(u)?N(v)∪N(w)，且N(w)?N(v)∪N(u) inG′，且如下條件之一成立:

① ab(v)

當(dāng)v的鄰居集合及其本身可以被它的另外兩個被標(biāo)記的鄰居u和w覆蓋時，在情況(1)中，u和w中的任意一個節(jié)點(diǎn)的鄰居集合都不能被其他的兩個節(jié)點(diǎn)所覆蓋。在這種情況下，節(jié)點(diǎn)v就可以被標(biāo)記為F并且從現(xiàn)有的連通支配集中移除，如圖2(c)中的節(jié)點(diǎn)v。

在情況(2)中，v和u的鄰居集合及其本身都可以分別地被其他兩個被標(biāo)記的鄰居u和w以及v和w覆蓋。但是，w不能被其他的兩個節(jié)點(diǎn)v和u覆蓋。在此情況中，節(jié)點(diǎn)u和v中至少有一個節(jié)點(diǎn)需要被標(biāo)記為F，并從現(xiàn)有的連通支配集中被移除，具體可以參照規(guī)則1。在情況(3)中，當(dāng)v、u和w中的任意一個節(jié)點(diǎn)的鄰居集合及其本身都可以分別地被其他兩個節(jié)點(diǎn)覆蓋，那么節(jié)點(diǎn)v可以被標(biāo)記為F并從現(xiàn)有的連通支配集中移除當(dāng)且僅當(dāng)下列情況之一成立：①節(jié)點(diǎn)v的鄰居覆蓋能力最弱(即ab(v)為三者中最小值)；②當(dāng)節(jié)點(diǎn)的鄰居覆蓋能力相同時，cnn(v)最??；③當(dāng)節(jié)點(diǎn)的鄰居覆蓋能力相同，cnn值也相同時，v具有最小的節(jié)點(diǎn)ID。

由于u和w都是節(jié)點(diǎn)v的鄰居，同時，v的鄰居集合及可以被u和w的鄰居集合所覆蓋，這就可以說明節(jié)點(diǎn)u和w是連通的。因此，現(xiàn)有的連通支配集在移除節(jié)點(diǎn)v過后仍然是原來網(wǎng)絡(luò)的一個連通支配集。

至此，轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇告一段落?；谛聵?gòu)造的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合，下面開始基于信道的連通支配集的構(gòu)造的第二步：轉(zhuǎn)發(fā)信道的選擇。在這個階段，本文提出了一個貪心算法來選擇連通度最高的信道作為轉(zhuǎn)發(fā)信道，并完成基于信道的連通支配集的構(gòu)造。

算法1 基于信道的連通支配集的構(gòu)造

算法輸入: 網(wǎng)絡(luò)圖G(V,E); 未被覆蓋的節(jié)點(diǎn)集合Ucov;之前選出的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合V′,V′?V;

算法輸出: 基于信道的連通支配集subc;

1: whileUcov≠? do

由于 “創(chuàng)造”是一個含義豐富、表現(xiàn)形式多樣的概念，因而創(chuàng)造力的定義也多種多樣[2]。狹義的創(chuàng)造力是 “首創(chuàng)前所未有的事物的能力”。廣義的創(chuàng)造力是“產(chǎn)生出一切相對于創(chuàng)造主體而言的、有益社會發(fā)展的新的思維、行動或結(jié)果的能力。”

2: for eachv∈V′ do

3: ifN(v) ≠ ? then

4: 找到節(jié)點(diǎn)v連通度最高的信道c

(即，鄰居數(shù)量最多的信道)

5: 將信道c及其節(jié)點(diǎn)加入到集合subc中

6:N(v)=N(v)-Nc(v)

7:Ucov=Ucov-Nc(v)

8:N(vc)=?

10: end for

11: end while

3 開銷和吞吐量分析

本章將會對C-CDS進(jìn)行性能分析。首先，假設(shè)仿真過程中使用格式固定的廣播數(shù)據(jù)包，由兩個部分組成：首部和數(shù)據(jù)部，分別用常數(shù)hLen和dLen來表示。然后，假設(shè)網(wǎng)絡(luò)中存在L種信道和V個節(jié)點(diǎn)。為了簡化廣播過程，假設(shè)仿真過程中的拓?fù)淝闆r穩(wěn)定。

(1)鄰居發(fā)現(xiàn)開銷。首先，節(jié)點(diǎn)間將會進(jìn)行hello數(shù)據(jù)包的交互。在此過程中，節(jié)點(diǎn)將會在其所有信道上，和1跳范圍內(nèi)的鄰居交互它們的IP地址(4 B)。在第二次交互時，由于采用了信道向量來進(jìn)行信息交互，該節(jié)點(diǎn)僅僅需要發(fā)送其1跳信道向量，長度也由4個直接縮短到L位(L為信道類型數(shù)量)。長度為L/8 B，不足1 B的部分，按1 B計算。最后，節(jié)點(diǎn)需要和所有鄰居節(jié)點(diǎn)交互其2跳信道向量信息(每條長度為L字節(jié)[13])。因此，可以得出C-CDS的鄰居發(fā)現(xiàn)開銷公式如下：

(3)

其中，Li表示節(jié)點(diǎn)i所擁有的信道數(shù)量。

(2)總開銷?？傞_銷由兩部分組成，鄰居發(fā)現(xiàn)開銷和廣播開銷。公式中，使用kC-CDS來表示總轉(zhuǎn)發(fā)次數(shù)。因此總開銷的計算公式如下：

TOC-CDS=NDOC-CDS+hLen×kC-CDS

(4)

(3)吞吐量。吞吐量是單位時間內(nèi)數(shù)據(jù)的有效接收量。假設(shè)在MANETs中的數(shù)據(jù)率為54 Mb/s，并且數(shù)據(jù)傳輸過程中不存在干擾和資源競爭的情況。同時，數(shù)據(jù)傳輸?shù)乃俾屎愣?。在此情況下，可以得到C-CDS的吞吐量計算公式如下：

(5)

4 性能評估

在本章中，將對仿真結(jié)果進(jìn)行分析，并將C-CDS機(jī)制的性能與其他兩種廣播策略，N-CDS和CV進(jìn)行比較。仿真參數(shù)如表1所示。

4.1轉(zhuǎn)發(fā)節(jié)點(diǎn)集大小和轉(zhuǎn)發(fā)開銷

假設(shè)網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)數(shù)量的取值從50～100。每個場景仿真200次，網(wǎng)絡(luò)拓?fù)潆S機(jī)生成。通過計算并統(tǒng)計每一次的計算結(jié)果，求得轉(zhuǎn)發(fā)節(jié)點(diǎn)集大小(轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量)以及廣播開銷(總的轉(zhuǎn)發(fā)次數(shù))的平均值。

表1 仿真參數(shù)

圖3描述了3種廣播機(jī)制：基于N-CDS、C-CDS以及CV的廣播機(jī)制，在不同的網(wǎng)絡(luò)規(guī)模下的轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量的平均值。顯然，這3種機(jī)制都在一定程度上減少了轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)量。從仿真結(jié)果上看，相對而言，本文提出的C-CDS方法的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合最小。

圖3 轉(zhuǎn)發(fā)節(jié)點(diǎn)集合的大小

圖4展示了這3種廣播機(jī)制的平均廣播開銷。從圖中可以看出，相比于其他兩種廣播機(jī)制，C-CDS的廣播開銷最小。這是因?yàn)镃-CDS方法擁有最小的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合，并且改進(jìn)后的轉(zhuǎn)發(fā)策略解決了由多信道環(huán)境帶來的冗余傳輸問題。

圖4 廣播開銷

此外，相較于CV機(jī)制使用的貪心策略，C-CDS方法采用了本文提出的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇規(guī)則，從而使得轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇更加精確。與N-CDS和基于CV的廣播機(jī)制相比，C-CDS分別減少了64.15%和13.95%的廣播開銷。

4.2總開銷和吞吐量

前面提到，數(shù)據(jù)包由首部(hLen)和數(shù)據(jù)部(dLen)兩部分組成。在開銷和吞吐量的仿真分析過程中，設(shè)dLen=1 000，hLen=20，然后可以分別得到仿真結(jié)果如圖5和圖6所示。圖5展示的是總開銷的仿真結(jié)果。從式(4)中知道，總開銷由鄰居發(fā)現(xiàn)開銷以及廣播開銷(如圖4)構(gòu)成。從圖4中可以看出，C-CDS擁有最低的的廣播開銷。同時，由于采取了與CV機(jī)制相同的信息交互方式，即用簡要的信道向量信息代替完整的節(jié)點(diǎn)和信道信息，C-CDS機(jī)制有效降低了鄰居發(fā)現(xiàn)開銷。因此，與基于N-CDS和CV的廣播機(jī)制相比，基于C-CDS的廣播機(jī)制明顯降低了總開銷。

圖5 總開銷

圖6 吞吐量

圖6展示了吞吐量這一性能指標(biāo)隨節(jié)點(diǎn)數(shù)量的變化情況。從圖中可以看出C-CDS機(jī)制的吞吐量有明顯的提升。與CV機(jī)制相比，C-CDS機(jī)制的吞吐量提升了14.1%。同時，本文中的方法有效地避免了由CV的集中式特性帶來的問題。

5 結(jié)束語

本文提出了一種基于信道連通支配集的選擇機(jī)制，并以此為基礎(chǔ)提出了一種適用于異構(gòu)多信道移動自組織網(wǎng)絡(luò)的高效廣播機(jī)制。相比于普通的基于節(jié)點(diǎn)的連通支配集機(jī)制，本機(jī)制不僅會選擇合適的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，同時也將在節(jié)點(diǎn)的多個信道中選擇合適的信道作為其轉(zhuǎn)發(fā)信道。

當(dāng)在異構(gòu)多信道移動自組織網(wǎng)絡(luò)中進(jìn)行廣播時，本文中的機(jī)制將合理地對轉(zhuǎn)發(fā)節(jié)點(diǎn)及其轉(zhuǎn)發(fā)信道進(jìn)行選擇，從而減少在不必要的節(jié)點(diǎn)和信道上的冗余傳輸。同時，本機(jī)制引入了CV來完成節(jié)點(diǎn)間的信息交互，從而進(jìn)一步降低了開銷。最后，本文對3種廣播算法進(jìn)行了大量的仿真分析。結(jié)果表明，相比于基于N-CDS和CV的廣播機(jī)制，基于C-CDS的廣播機(jī)制有效地減少了廣播過程中的開銷并且明顯地提高了網(wǎng)絡(luò)吞吐量。這也將使得本文中的機(jī)制在多信道網(wǎng)絡(luò)環(huán)境中更具競爭力。

[1] Li Deying, Jia Xiaohua, Liu Hai. Energy efficient broadcast routing in static ad hoc wireless networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(2):144-151.

[2] SASSON Y, CAVIN D, SCHIPER A. Probabilistic broadcast for flooding in wireless mobile ad hoc networks[J]. 2002,2(2):1124-1130.

[3] MNIF K, RONG B, KADOCH M. A distributed approach for computing the minimum connected dominating set in ad hoc networks[C]. Electrical and Computer Engineering. 2005. Canadian Conference on IEEE, 2005:2065-2068.

[4] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M].W.H.Freeman,1979.

[5] CLARK B N, COLBOURN C J, JOHNSON D S. Unit disk graphs[J]. Discrete Mathematics, 1990, 86(1-3):165-177.

[6] Peng Wei, Lu Xicheng. Efficient broadcast in mobile ad hoc networks using connected dominating sets[J]. Journal of Software, 2001,12(4): 529-536.

[7] BEIGEL R, EPPSTEIN D. 3-coloring in time O (1.3289 n)[J]. Journal of Algorithms, 2005, 54(2):168-204.

[8] BLUM J, Ding Min, THAELER A, et al. Connected dominating set in sensor networks and MANETs[M]. Springer US, 2006.

[9] Wu Zhijie, Zhao Qi. Sensing-throughput tradeoff of relay-assisted random broadcast based cognitive radio networks[C]. 2013 IEEE 77th Vehicular Technology Conference (VTC Spring) 2013, 14(6): 1-5.

[10] CHANG Y I, HWANG M H. A counter-based reliable broadcast protocol[C] Proceedings of Twentieth Euromicro Conference on System Architecture and Integration. IEEE, 1994:396-403.

[11] Tu Xiaoyu, Wang Hai, Li Zhimin. Channel vector: an overhead reduced broadcast in multichannel wireless mesh networks[C]. IEEE International Conference on Communications, 2015:3690-3695.

[12] Wu Jie, Li Hailan. On calculating connected dominating set for efficient routing in ad hoc wireless networks[C]. International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 1999:7-14.

[13] BUTENKO S, CHENG X, OLIVEIRA C A, et al. A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks[J]. World Academy of Science Engineering & Technology, 2012,3:61-73.

The channel-based CDS algorithm for broadcast in multichannel MANETs

Zhang Mao, Wang Hai, Dong Chao, Ma Yanqing

(College of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China)

In Mobile Ad-hoc Networks (MANETs), to meet users’ various requirements and improve the network capacity, nodes usually equipped with multiple channels. Traditional broadcast approaches like flooding, CDS and channel vector(CV) scheme often use nodes based forwarding, which means nodes can’t distinguish the difference among their different channels. Messages are forwarded on all of their channels after they receive new messages from others, leading to redundant transmissions on unnecessary channels. To make best use of network consisted of nodes with multi-channels and cut down the broadcast overhead, we proposed a new Channel-based CDS (C-CDS) formation scheme. Based on the newly selected C-CDS, an efficient broadcast protocols, which is suitable for multichannel scenarios was proposed. Simulation results indicate that, C-CDS based broadcast approach increased the throughput by 14.1% compared with CV, and the broadcast overhead was reduced by 64.15% and 13.95% compared with N-CDS and CV individually.

broadcast; multichannel; CDS; MANETs

國家自然科學(xué)基金(61371124, 61103224, 61472445，61571463)；江蘇省自然科學(xué)基金(BK2011118, BK20140076)

TP393.0

：A

10.19358/j.issn.1674- 7720.2017.17.005

張茂，王海，董超，等.適用于異構(gòu)移動自組織網(wǎng)絡(luò)的多信道廣播算法[J].微型機(jī)與應(yīng)用，2017,36(17)：15-20.

2017-03-14)

張茂(1992-)男，碩士研究生，主要研究方向：異構(gòu)網(wǎng)絡(luò)組網(wǎng)。王海(1973-)男，博士，教授，博士生導(dǎo)師，主要研究方向：無線通信，異構(gòu)網(wǎng)絡(luò)。董超(1980-)，男，博士，副教授，主要研究方向：無線通信，計算機(jī)網(wǎng)絡(luò)。