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

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

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

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

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

在異構(gòu)移動自組織網(wǎng)絡(luò)中，為滿足多樣的用戶需求，提高網(wǎng)絡(luò)容量，節(jié)點往往配備了多種信道。傳統(tǒng)的廣播機制(如洪泛、基于節(jié)點的連通支配集和信道向量等)往往采用基于節(jié)點的轉(zhuǎn)發(fā)方式，即對節(jié)點所擁有的多個信道采取一視同仁的態(tài)度，在收到消息后將直接在其所有信道上進行轉(zhuǎn)發(fā)，導(dǎo)致其無法充分利用各個信道的性能優(yōu)勢，以及在某些不必要信道上的冗余轉(zhuǎn)發(fā)。為了充分發(fā)揮多信道網(wǎng)絡(luò)的優(yōu)勢，降低冗余轉(zhuǎn)發(fā)帶來的開銷，提出了一種基于信道的連通支配集構(gòu)造機制，該機制采用了基于信道的轉(zhuǎn)發(fā)方式，在選擇轉(zhuǎn)發(fā)節(jié)點的同時也將對轉(zhuǎn)發(fā)信道進行選擇，并以此為基礎(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)運而生[1]。實際應(yīng)用過程中，多信道移動自組織網(wǎng)絡(luò)的異構(gòu)性特征主要體現(xiàn)在以下兩個方面：一是網(wǎng)絡(luò)中的信道性能各異，異構(gòu)特征明顯；二是可能存在單個節(jié)點同時擁有多個信道的情況。

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

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

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

1 相關(guān)工作

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

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

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

2 基于信道的連通支配集

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

圖1 多信道MANETs網(wǎng)絡(luò)拓撲實例

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

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

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

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

(1)

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

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

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

(2)

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

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

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

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

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

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

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

規(guī)則1：若圖G′中存在兩個被標記為T的節(jié)點v和u。節(jié)點v將被重新標記為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)

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

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

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

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

規(guī)則2：假設(shè)節(jié)點u和w是節(jié)點v的兩個被標記為T的鄰居。v可以被標記為F并從現(xiàn)有的連通支配集中被移除，當且僅當以下情況出現(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)

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

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

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

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

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

算法輸入: 網(wǎng)絡(luò)圖G(V,E); 未被覆蓋的節(jié)點集合Ucov;之前選出的轉(zhuǎn)發(fā)節(jié)點集合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é)果的能力?！?/p>

2: for eachv∈V′ do

3: ifN(v) ≠ ? then

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

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

5: 將信道c及其節(jié)點加入到集合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進行性能分析。首先，假設(shè)仿真過程中使用格式固定的廣播數(shù)據(jù)包，由兩個部分組成：首部和數(shù)據(jù)部，分別用常數(shù)hLen和dLen來表示。然后，假設(shè)網(wǎng)絡(luò)中存在L種信道和V個節(jié)點。為了簡化廣播過程，假設(shè)仿真過程中的拓撲情況穩(wěn)定。

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

(3)

其中，Li表示節(jié)點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é)果進行分析，并將C-CDS機制的性能與其他兩種廣播策略，N-CDS和CV進行比較。仿真參數(shù)如表1所示。

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

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

表1 仿真參數(shù)

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

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

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

圖4 廣播開銷

此外，相較于CV機制使用的貪心策略，C-CDS方法采用了本文提出的轉(zhuǎn)發(fā)節(jié)點選擇規(guī)則，從而使得轉(zhuǎn)發(fā)節(jié)點的選擇更加精確。與N-CDS和基于CV的廣播機制相比，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機制相同的信息交互方式，即用簡要的信道向量信息代替完整的節(jié)點和信道信息，C-CDS機制有效降低了鄰居發(fā)現(xiàn)開銷。因此，與基于N-CDS和CV的廣播機制相比，基于C-CDS的廣播機制明顯降低了總開銷。

圖5 總開銷

圖6 吞吐量

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

5 結(jié)束語

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

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

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

TP393.0

：A

10.19358/j.issn.1674- 7720.2017.17.005

張茂，王海，董超，等.適用于異構(gòu)移動自組織網(wǎng)絡(luò)的多信道廣播算法[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-)，男，博士，副教授，主要研究方向：無線通信，計算機網(wǎng)絡(luò)。