适用于异构移动自组织网络的多信道广播算法*

张 茂，王 海，董 超，马彦庆

(中国人民解放军理工大学 通信工程学院，江苏 南京 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-)，男，博士，副教授，主要研究方向：无线通信，计算机网络。