適用于異構移動自組織網絡的多信道廣播算法*

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

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

適用于異構移動自組織網絡的多信道廣播算法*

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

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

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

廣播；多信道；連通支配集；移動自組織網絡

0 引言

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

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

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

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

1 相關工作

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

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

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

2 基于信道的連通支配集

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

圖1 多信道MANETs網絡拓撲實例

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

2.1網絡模型

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

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

(1)

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

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

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

(2)

2.2基于信道的連通支配集的構造

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

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

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

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

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

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

規則1：若圖G′中存在兩個被標記為T的節點v和u。節點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的鄰居集合及其本身包含于其鄰居節點u的封閉鄰居集合時，若節點v的鄰居覆蓋能力值小于u，即ab(v)

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

圖2 規則1和2的舉例說明

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

規則2：假設節點u和w是節點v的兩個被標記為T的鄰居。v可以被標記為F并從現有的連通支配集中被移除，當且僅當以下情況出現：

(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中的任意一個節點的鄰居集合都不能被其他的兩個節點所覆蓋。在這種情況下，節點v就可以被標記為F并且從現有的連通支配集中移除，如圖2(c)中的節點v。

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

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

至此，轉發節點的選擇告一段落。基于新構造的轉發節點集合，下面開始基于信道的連通支配集的構造的第二步：轉發信道的選擇。在這個階段，本文提出了一個貪心算法來選擇連通度最高的信道作為轉發信道，并完成基于信道的連通支配集的構造。

算法1 基于信道的連通支配集的構造

算法輸入: 網絡圖G(V,E); 未被覆蓋的節點集合Ucov;之前選出的轉發節點集合V′,V′?V;

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

1: whileUcov≠? do

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

2: for eachv∈V′ do

3: ifN(v) ≠ ? then

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

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

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

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

(3)

其中，Li表示節點i所擁有的信道數量。

(2)總開銷。總開銷由兩部分組成，鄰居發現開銷和廣播開銷。公式中，使用kC-CDS來表示總轉發次數。因此總開銷的計算公式如下：

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

(4)

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

(5)

4 性能評估

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

4.1轉發節點集大小和轉發開銷

假設網絡拓撲中節點數量的取值從50～100。每個場景仿真200次，網絡拓撲隨機生成。通過計算并統計每一次的計算結果，求得轉發節點集大小(轉發節點數量)以及廣播開銷(總的轉發次數)的平均值。

表1 仿真參數

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

圖3 轉發節點集合的大小

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

圖4 廣播開銷

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

4.2總開銷和吞吐量

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

圖5 總開銷

圖6 吞吐量

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

5 結束語

本文提出了一種基于信道連通支配集的選擇機制，并以此為基礎提出了一種適用于異構多信道移動自組織網絡的高效廣播機制。相比于普通的基于節點的連通支配集機制，本機制不僅會選擇合適的節點作為轉發節點，同時也將在節點的多個信道中選擇合適的信道作為其轉發信道。

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

[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

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

2017-03-14)

張茂(1992-)男，碩士研究生，主要研究方向：異構網絡組網。王海(1973-)男，博士，教授，博士生導師，主要研究方向：無線通信，異構網絡。董超(1980-)，男，博士，副教授，主要研究方向：無線通信，計算機網絡。