Ad Hoc分布式虚拟骨干网构建算法＊

狄元博 陶 凯 叶永安

（1.海军装备研究院 北京 100161）（2.武汉船舶通信研究所 武汉 430079）（3.73141部队 南安 362301）

1 引言

现实的分层结构为有线和计算机通信中的网管、资源利用等方面带来了极大的便利，因此人们期望在Ad Hoc网中也能构建这样一种骨干网，称为虚拟骨干网，缓解Ad Hoc自组网因其动态特性造成的网管和资源利用不便的情况。研究表明，虚拟骨干网在无线自组网的路由、广播以及连通控制中起着至关重要的作用［1～4］。

单位原模型［5］和图论中的连通支配集（CDS）模型常被用于Ad Hoc自组网的虚拟骨干网。为了简化连通控制，总希望找到一个规模最小的CDS，然而图论中已经证明，求解最小连通支配集是一个NP完全难题，所以只能用近似的算法求解最小连通支配集［6～9］。

近似算法分为集中式构建算法和分布式构建算法。集中式构建算法需要获得整个网的拓扑结构，这对成员规模较大时是一笔不小的开销。分布式构建算法无线获得整个网的拓扑结构，具有较好的拓扑动态适应性。

WAN算法是分布式构造最小连通支配集的典型近似算法之一，本文基于WAN算法［10］提出了一种基于拓扑分层的极小连通支配集的构造算法LMCDS算法，结果显示LMCDS算法不但可以生成节点数目较少的连通支配集，而且在消息复杂度方面有明显改善。

2 LMCDS算法描述

LMCDS算法的流程如图1所示。在LMCDS算法开始之前，所有节点需要探索外部的拓扑，其过程如下：所有节点广播VISIT访问消息，消息中附带其节点编号。通过接收邻居节点的VISIT消息节点可以构造出邻居节点表。而后每个节点将邻居节点表附入VISIT消息中再次广播，通过接收相邻节点发送的VISIT消息，每个节点可以计算出邻居节点的度（deg）以及邻居节点表等信息。所谓节点的度是指节点的邻居节点的数目，假设网内节点的最大度为△。

图1 LMCDS算法流程

2.1 生成树的构建

构建极大独立集之前首先要建立一棵生成树，这样做的目的是将一个网分为若干层，并确立节点之间的父子关系。生成树的构建是通过广播HELLO消息来实现的。每个节点都设有一个变量Level，Level初始值均为0。节点的Level值代表该节点位于网内的第几层，即节点所处层的层号。规定层号为奇数的为支配层，其余的层为被支配层。广播HELLO消息的规则如下

规则1：选择节点号最小的节点作为根节点，并将根节点的Level值设置为1。由根节点开始广播HELLO消息，HELLO消息中包含自己的ID和Level值。

规则2：每个节点只能接收一次HELLO消息。任意收到HELLO消息的节点将发送消息的节点设置为自己的父节点，并将自己的Level值设置为发送节点Level值加1，然后将自己的ID和Level值添加到HELLO消息中，并转发HELLO消息。

规则3：同时收到HELLO消息的节点，按时隙转发HELLO消息，节点度大的节点优先转发。按时隙转发保证了每个节点只有唯一的父节点。

当所有节点的Level值均不为零时，生成树构建完成。此时，所有节点的Level值和父节点都已确定。

2.2 极小支配集的构建

生成树构建完毕之后，该网随之分层完毕。接下来开始构建该网的极小支配集。根据图论的知识，一个图的极大独立集（MIS）都是它的极小支配集（MDS），所以可以通过构建MIS的方法实现MDS的构建。

构建MIS开始之前，首先给出一个键值（Key）的概念，对任意节点u，定义其键值为 K（u）＝（deg（u），ID（u）），即一个节点的键值是其节点度与节点号的有序组合。给定任意两个节点u和v，只要deg（u）＞deg（v），则 K（u）＞K（v）；deg（u）＜deg（v），则 K（u）＜K（v）；若 deg（u）＝deg（v），ID（u）＞ID（v），则 K（u）＞K（v）。

LMCDS算法采用染色法构建MIS。初始时所有节点均为白色，然后按照如下操作逐步对各个节点进行染色，直至所有的节点都被染成黑色或灰色，则停止染色。

规则1：每个支配层首先选择该层Key值最大的白色节点并将其染黑。黑色节点广播BLACK消息，白色节点收到BLACK消息就将自己染灰。

规则2：若支配层中还存在白色节点就按照规则1继续染色。

规则3：若支配层无白色节点，被支配层仍有白色节点，则从被支配层选择Key值最大的白色节点并将其染黑，然后广播BLACK消息。

染色完成之后，所有的黑色节点构成了极大独立集，证明如下。

命题1：LMCDS算法生成的所有黑色节点构成极大独立集。

证明：由染色规则易知，若黑色节点处于网内同一层，则它们必不相邻；若黑色节点处于网内的不同层，则它们至少相隔两跳的距离，故黑色节点构成独立集。又因为染色完成之后，所有的灰色节点均被黑色节点覆盖，即所有的灰色节点至少和一个黑色节点相邻，若任选一个灰色节点染黑，所有的黑色节点将不再构成独立集，所以该独立集为极大独立集。

2.3 连通极小支配集

极小支配集构建完毕之后，要将其连通以实现极小连通支配集的构建。在LMCDS算法中，所有的支配节点之间是相互独立的，所以只能从被支配节点中选择若干节点来实现MDS的连通。而生成树和MIS的构建完成之后，根据节点之间的连通及父子关系，只需将支配节点的父节点加入极小支配集即可实现极小支配集的连通。极小支配集及其支配节点的父节点一起构成了极小连通支配集，证明如下。

以图2（a）的拓扑为例，图2（b）～2（g）演示了 MIS的构建过程。图2（g）中所有的黑色节点构成了MIS，图2（h）中所有的黑色节点构成了CDS。

图2 LMCDS算法构建CDS的应用举例

3 LMCDS算法性能分析

假设网内节点数目为n，在探索阶段，每个节点探索邻居信息，只需发送一次VISIT消息，因为每个节点周围最多有△个邻居节点，因此消息复杂度为O（n）。第一阶段构建生成树的过程中最坏情况下的时间复杂度为O（n），消息复杂度为O（n）。构造MIS过程和连通MCDS过程的时间复杂度和消息复杂度都是线性的，所以最坏情况下LMCDS算法的时间复杂度为O（n），消息复杂度为O（n）。

设M为一个拓扑的最小连通支配集，S为该网任意一个连通支配集，并假设网内所有的黑色节点集合为S1，黑色节点父节点集合为S2，所以LMCDS算法中构建的连通支配集S的节点数目为｜S｜＝｜S1｜＋｜S2｜。由于几个黑色节点可能有共同的父节点，且根节点无父节点，所以有｜S2｜≤｜S1｜－1，根据最大独立集的性质［10］，｜S1｜≤4｜M｜＋1，故｜S｜≤2｜S1｜－1≤8｜M｜＋1。即LMCDS构建的极小连通支配集的数目最多为8｜M｜＋1。

LMCDS算法和WAN算法的性能比较见表1。

表1 两种算法的性能比较

4 结语

本文基于WAN算法提出了一种分布式极小连通支配集构建方法LMCDS，该算法不但可以生成规模较小的连通支配集，而且与WAN算法相比，本算法具有较小的消息复杂度，因此在动态性高、开销要求小的实时数据传输方面具有一定应用价值。

［1］I.Cidon，O.Mokryn.Propagation and leader election in multihop broadcast environment［C］／／Proc.of 12th International Symposium on DIStributed Computing（DISC98），Greece，1998，9：104－119.

［2］Stojmenovic I，Seddigh M，Zunic J.Dominating Sets and Neighbor Elimination Based Broadcasting Algorithms in Wireless Networks［C］／／Proc.of IEEE International Conf.on System Sciences.New Tersey：IEEE Press，2002：14－25.

［3］R.Sivakumar，B.Das，V.Bharghavan.An improved spinebased infrastructure for routing in ad hoc networks［C］／／Proc.of IEEE Symposium on Computers and Communications'98，Athens，Greece，1998.

［4］Wang Yuming，Zhao Dasheng.Construction and analysis of connected dominting set based on serial maximum independent set［J］.J.Huazhong Univ.of Sci.＆Tech.Natural Science E－dition，2011，39（3）：66－70.

［5］B.N.Clark，C.J.Colbourn，D.S.Johnson.Unit disk graphs［J］.Discrete Mathmatics，1990，86：165－177.

［6］Bharghavan V，Das B.Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets［C］／／Proceedings of International Conference on Communications.Montreal，Canada，1997：376－380.

［7］PENG Wei，LU Xichen.A Novel Distribute Approximation Algorithm for Minimum Dominating Set［J］.CHINESE J.COMPUTER，2001，24（3）：254－258.

［8］D.－Z.Du，M.T.Thai，Y.Li，et al.Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links［C］／／Proc.APWEB06，2006：13－24.

［9］唐勇，周明天.基于极大独立集的最小连通支配集的分布式算法［J］.电子学报，2007，37（5）：868－874.TANG Yong，ZHOU Mingtian.Maximal Independent Set Based Distributed Algorithm for Minimum Connected Dominating Set［J］.ACTA ELECTRONICA SINICA，2007，37（5）：868－874.

［10］PENG－JUN WAN.Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks［C］／／Proc.of INFOCOM02，2002：1597－1604.