无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法*

郑 婵，尹 令，孙世新

(1.电子科技大学计算机学院，成都610054;2.华南农业大学信息学院，广州510642)

无线传感器网络是由大量具有感知、数据处理和通信能力的传感器节点组成的网络，具有低功耗、低成本、智能化、分布式、自组织等特点，在军事、环保、医疗、商业、农业、灾害预测及救援等领域都有着广阔的应用前景。由于没有类似蜂窝通信中基站的骨干基础，且受到传感器无线收发装置传输半径和节点能量的限制，多数的节点之间都不能直接进行通信，只能通过若干中间节点形成的虚拟骨干网进行多跳交换数据和通信。在无线传感器网络中构造虚拟骨干网是优化网络结构的一个重要手段，而构建虚拟骨干网最常用的技术就是计算网络的连通支配集CDS(Connected Dominating Set)。CDS中的支配节点构成高一级的骨干节点控制着全网的路由、维护和管理。在单位圆盘图UDG(Unit Disk Graph)的网络模型中构造最小连通支配集MCDS(Minimum CDS)早已被证明是NP完全问题［1］，在节点具有中等规模以上(一般节点数量大于40)时，只能构造近似的最小连通支配集。近十年来，关于构造最小连通支配集已经有较为深入而成熟的研究，研究学者们提出了各种算法来构造近似的最小连通支配集［2］。

随着无线传感器网络规模的增大和密集程度的增加，采用近似的最小连通支配集算法获得的支配集节点数目依然较大。为了解决这一问题，很多学者［3-8］提出d-hop连通支配集(d-hop CDS)来大大减少支配集节点数量。d-hop CDS指的是受支配节点和支配节点之间的跳数最多可达d跳。当d≥2时，d-hop CDS具有比CDS少得多的支配节点数，可提高网络容量和网络性能，因为d-hop CDS将无线传感器网络划分为更大的簇(Cluster)，整个网络收缩为以d-hop簇头(Clusterhead)为超级节点的多层次网络，簇内其余节点都通过d-hop簇头和别的节点通信。Nguyen等［9］证明了在 UDG中寻找最小 dhop CDS依然是NP完全问题。

另一方面，由于传感器节点存在能量、存储和计算等资源约束，节点的失效、链路的断裂会导致网络失败，因此构造容错性好、可靠性高的虚拟骨干网是一个非常有意义的课题。构造具有一定冗余度的k-连通支配集来充当虚拟骨干网可提高网络的容错性和可靠性。k-连通指虚拟骨干网中任意k-1个骨干节点出错，虚拟骨干网仍然是连通的。当k较小(k=2，3等)，k-连通骨干网相对简单并且具有容错能力，可在少量节点失效的情况下依然能够保持骨干网的拓扑连通。

基于上述两个目的需构建一个既精简又具有容错能力的连通支配集作为虚拟骨干网，可结合连通支配集的多跳性质和k-连通性质。

近十年来，关于1-hop的MCDS的构造研究已经较为成熟而深入，提出了多种分布式算法来构造近似的最小连通支配集，其中以基于贪心［10］、Steiner tree［11］、剪枝［12］、最大独立集［13］、多点中继集［14］和簇构造［15］等一系列方法的研究为最多。而后从单跳MCDS向d-hop CDS扩展，比较有代表性的是基于簇构造［3-4］、基于贪心［16］、基于剪枝［5-6］的d-hop CDS构造法，以及能量均衡的 CDS构造［17］。Gao等人［7］提出在 UDG 或 UBG(Unit Ball Graph)图中构造d-hop CDS的多项式近似算法并给出了详尽的证明。在文献［3］和文献［4］中，采用基于Cluster构造来构造d-hop CDS，通信代价和算法时间都依赖于跳数d和节点平均度。Yang等［5］提出了不同一般做法的剪枝策略，初始i=0时所有节点都是ihop CDS，而后对 i=0，1，…d-1 需经过 d次删减，每次删减i-hop CDS被剪枝成为(i+1)-hop CDS。文献［8］更有新意的从青虫产卵中得到启示，模拟生物行为构建d-hop CDS，使算法性能能独立于跳数d和节点平均度，此法适合大规模和超大规模的传感器网络的d-hop CDS的构建。

在提高连通支配集的容错性可靠性方面，学者们也做了许多研究［18-24］，这其中大部分都结合了 k-Vertex连通性和m-支配性。Dai等［18］采用基于概率的、确定的和混合的3种方法构造k-连通k-支配集，文献［19］也提出k-连通m-支配集的构造法。关于2-连通多支配集也有特定研究［20-21］，Wang等［22］专门研究了2-连通的骨干网构造方法，同时Li等［23］提出两种中心式的构造2-连通d-hop支配集的方法。据笔者所知，目前研究2-连通d-hop支配集的分布式构造方法鲜少，本文基于单位圆盘图网络模型提出d-hop 2-连通支配集的分布式构造算法，d-hop 2-CDS算法(d-hop 2-Connected Domination Set Construction)，主要策略分多步构造，先分簇构造d-hop独立支配集，后添加路径节点形成2-连通支配集。

1 问题定义

1.1 定义1 单位圆盘图UDG(Unit Disk Graph)

一般地，无线传感器网络可以抽象为无向单位圆盘图，网络中每个传感器节点在图中可用单位圆盘中的顶点来表示，如果两个传感器节点能相互直接通信则在图中对应为一条边。为便于描述，以下将单位圆盘图简称为G=(V，E)。V和E分别表示节点集和边集。这里只考虑连通的单位圆盘图G。

1.2 定义2 连通支配集CDS(Connected Dominating Set)

图 G=(V，E)中，设D⊆V，∀u∈V，u∈D 或 u 与 D中某一节点相邻，称D为图G的支配集(Dominating Set，DS)，DS中的节点称为支配节点，不在该集中的节点则被称为受支配节点。若由D导出的子图为连通图，则称D为CDS。若∀u∈D，D-{u}不是一个连通支配集，则称D为图G的极小连通支配集(MCDS)。

1.3 定义3 极大独立集MIS(Maximal Independent Set)

图 G=(V，E)中，设 U⊆V，若对∀u，v∈U，(u，v)∉E，即点集中任意2个节点不相邻，则称U为图G的独立集。若对∀u∈V-U，U∪{u}不是一个独立集，则称U为图G的极大独立集(MIS)。

1.4 定义 4 d-hop CDS［9］

图 G=(V，E)中，顶点子集 D⊆V，对∀u∈D，v∉D，可以找到一条从u到v跳数为d的一条通路(或者说节点u和v之间有d-1个中间节点)，而且由子集D导出的子图是连通的，则称顶点子集D为d-hop CDS。特别地，当d=1时，1-hop CDS就是一般意义的CDS。

1.5 定义 5 d-hop 2-连通支配集［22-23］

图G=(V，E)中，顶点子集D⊆V，若满足①D为d-hop CDS;②由子集D导出的子图是2-连通的，即子集D任意一对顶点间都存在至少2条点不相同的路径，则称顶点子集D为d-hop 2-CDS。

1.6 定义6 割点、块、叶子块和块-割点图

连通图G中，若移去某个顶点u导致图G不连通，则u称为割点(Cut-Vertices)。图G的不含割点的最大连通子图称为块(block)。图G的仅含一个割点的连通子图称为叶子块(Leaf Block)。割点示例如图1所示。明显地，至少含有3个顶点的块是2-连通图。

图1 割点的示例图

块-割点图是个二部图H，其中一个部集由G的割点构成，另一部集每个点bi对应于G的一个块Bi，vbi作为H的一条边当且仅当v∈bi。

2 算法描述

本文总体上分3个步骤分布式构造d-hop 2-CDS:

第1步 每个节点给周围d-hop邻居泛洪Hello消息，建立d-hop邻居发现，收集d-hop范围的邻居节点状态信息。根据收集的信息确定自己着色状态，所有节点确认完毕即建立d-hop支配集，即d-hop DS。

第2步 从一个支配节点出发，在(d+1)跳范围内和另一个支配节点之间寻找最短路径，路径上的节点作为支配节点的连接点。每个支配节点重复这一过程，直至整个支配集连通。

第3步 对连通支配集导出的块-割点图，若存在叶子块，在叶子块和其余块之间寻找最短路径，并将路径节点扩充入连通支配集中。重复这一过程，直至块的个数为1。

2.1 d-hop 邻居发现

每个节点要发现周围d-hop邻居信息，就要先向周围d-hop范围的邻居节点发送泛洪的Hello消息。泛洪的过程如下:

(1)每个节点在首轮信息交换时，向所有一跳邻居发送Hello消息。收到消息的节点将一跳邻居保存在本节点的邻居列表NList中，直至该节点从所有一跳邻居处都收到Hello消息。

(2)在第 i∈［2，d］轮的信息交换时，每个节点在广播Hello消息捎带(i-1)hop邻居列表信息。

(3)经过(1)和(2)共d轮的消息交换每个节点都可以汇集周围d-hop范围的邻居节点状态信息(包括邻居的ID和着色状态等信息)，这些邻居信息都保存在该节点的邻居列表NList中。

2.2 第1步 构造d-hop MIS

节点用3种颜色(黑色、灰色和白色)来分别代表3种状态。

(1)支配节点(黑色):支配集的成员

(2)受支配节点(灰色):被支配节点支配的节点

(3)未定状态(白色):指空闲或初始的状态

节点的状态变化基于以下原则:

原则1 未定状态(白色)→受支配节点状态(灰色):如果一个白色节点收到一条来自于黑色节点v的消息，该白色节点将自己变为灰色，并成为支配节点v的受支配节点。

原则2 未定状态(白色)→支配节点状态(黑色):如果一个白色节点发现在它及它周围d-hop的所有白色节点中，自己拥有最大ID，且这一结果状态维持一个时间Iτ。该白色节点将自己变为黑色。

将d-hop 2-CDS算法的第1步具体过程归纳如下:

算法1:构造d-hop簇，所有簇头构成d-hop MIS

(1)计算并发现所有节点的d-hop邻居，每个节点将邻居信息(包括邻居ID和着色状态等)保存在本节点邻居列表中;

(2)初始时所有节点都为白色。选择所有d-hop白色邻居中有最大ID的白色节点，将它变为黑色，和该黑色节点相邻的所有d-hop白色邻居们皆标为灰色。将此黑色节点加入支配节点集合D。在这一轮着色中，黑色和灰色构成了d-hop Cluster，簇节点加入集合C，黑色节点为Clusterhead;

(3)考虑点集合C的所有一跳邻域中，计算并发现拥有最大ID的白色节点，将之着黑色，同时将被黑色节点支配的节点都着灰色。黑色节点继续加入支配节点集合D，黑色和灰色也加入集合C。如此不断扩充支配节点D和簇节点集合C，直至C为全顶点集合V或者说找不到白色节点为止;

(4)返回独立的支配节点集合D作为d-hop Dominating Set。算法1完毕。

2.3 第2步 构造d-hop连通支配集

构造d-hop连通支配集的过程就是将算法1得到的d-hop DS中的支配节点寻找连接节点(Connector)连接起来。支配节点和连接节点共同构成了 d-hop的 CDS。

每个黑色簇头管理和维护着一个本地表T，表T用来记录到达另一个黑色簇头的路径。如果一个黑色簇头v收到另一个簇头w发来的INVITE消息，若w没有在表T中，这时将w和INVITE。PathList加入表T中。否则，若表T中已经含有w，但是由消息IN-VITE。PathList获知的v和w之间的新路径比表T中的老路径更短，则用更短的新路径替换老路径。消息的PathList中的节点是连接节点Connector。

算法2:将d-hop独立支配集连通起来

(1)每个黑色簇头节点向周围(d+1)-hop广播INVITE消息，消息中包含路径列表PathList;

(2)从某个指定簇头根节点开始，根据簇头本地表T来构建局部最小生成树，仅向其具有最大 ID的儿子广播DISTANCE消息(消息中包含父亲簇头生成的局部最小生成树节点)，当儿子簇头节点收到DISTANCE消息，继续扩充最小生成树(须避免和父亲节点形成环路)，向具有最大ID的孙子广播，这一过程直至DISTANCE消息传遍全网的簇头节点并已无法扩充最小生成树为止。此时所有簇头节点位于最小生成树顶点，而连接点位于最小生成树路径上;

(3)获得的连接点加入d-hop CDS集合D中，返回集合D。算法2完毕。

2.4 第3步 扩充d-hop 2-连通支配集

由算法的前两步获得的d-hop连通支配集为D。第3步对D导出的块-割点图G［D］只要存在叶子块L，寻找将L和D-L连接的路径P，P须满足:(1)该路径两端点是L和D-L中，路径的中间节点必须是原始网路图G中非D集合的节点;(2)该路径是最短的，即中间节点个数最少的路径。

这里假设前3步获得的d-hop连通支配集D导出块-割点图为G［D］，对G［D］块的个数记为B［D］，路径P的中间节点集合为I。

算法3 继续扩充路径，将d-hop支配集2-连通

(1)采用Depth First Search(DFS)法对 G［D］计算块个数 B［D］;

(2)若B［D］＞1，计算叶子块和G［D］中其余部分的最短路径P，P的中间节点不属于D，将P中间节点集合I扩充入D，即 D=D∪I;

(3)重新计算 B［D］，重复执行上述2)过程，直至 B［D］=1。返回集合D。算法3完毕。

2.5 d-hop 2-CDS算法实例展示

在100×100的矩形区域内，随机放置100个传感器节点，每个节点通信半径为15。对d=2，3和4，本文算法前两步获得2-hop，3-hop和4-hop CDS分别如图2(a)、2(b)和2(c)所示。这里d-hop CDS被连通为树状。

图2 生成的d-hop CDS示例图

初始UDG网络图如图3(a)所示。以d=3为例，运行算法的第1和第2步骤可生成3-hop CDS，如图3(b)和3(c)所示。运行第3步可生成3-hop 2-CDS，如图3(d)所示。

图3 d-hop 2-CDS算法在各阶段后实例场景图(以d=3为例)

3 性能评价

3.1 算法理论分析

定理1 本文d-hop 2-CDS算法时间复杂度为O(d(mn+n2))，其中d为跳数，m为网络图边数，n为网络节点个数;消息复杂度为O(d2Δ(mn+n2))，其中Δ为最大节点度。

证明 事实上此算法时间最大消耗在第3步。(1)先考虑算法的前2步构造时间，含有 d-hop或(d+1)-hop的泛洪步骤，虽每个节点的泛洪消息是并行的，但由于消息跳数为d或(d+1)，因此发送消息的时间和d成正比。另外，构造时间也和网络节点数量n成正比，这由于在算法第1步(§3.2)每个节点须确定自己的着色状态，算法第2步(§3.3)每个距离为(d+1)的支配节点互连，这两个过程都类似:连续而非并行。最坏时间复杂度发生在当所有节点以优先级链状递增排列或递减排列时，节点最大的节点度为2。此时，每个节点都必须在等所有具有较大优先级的节点确定之后才能确认自己。因此，算法的前两步时间复杂度为O(dn)，其中d为跳数，n为网络节点个数。

(2)在算法第3步，深度优先搜索(DFS)块个数的计算需O(m+n)，m为网络图边数。每次循环中最短路径计算需O((2d+1)×n)，因为所扩充的2-连通路径长度不超过(2d+1)。因此算法第3步需O((m+n)(2d+1)n)，可简化为 O(d(mn+n2))，综合(1)(2)得证。

另外，关于算法的消息数量的分析，每个节点d-hop泛洪消息的数量是和跳数d的平方成比例关系;节点个数n和总泛洪消息数量成正比;不考虑丢包等通信损失，每个节点都的和周围所有邻接点交换消息，因此消息代价还和平均节点度成正比关系。综上前述(1)(2)的循环次数分析，算法的消息复杂度为O(d2Δ(mn+n2))，其中Δ为最大节点度。

引理 1［24］UDG 图 G=(V，E)中，定义 I为r-hop IS，对G中任意一顶点 u，|Nr(u)∩I|≤β，其中:

引理2 算法第2步，连通节点使得所有独立支配节点连通而形成生成树的顶点，这样插入的连接节点个数不超过d(|I|-1)，d为跳数，I同引理1定义。

证明 算法第2步，将第1步生成的|I|个节点组织成生成树，树的顶点就是支配节点，而树的路径就是连接节点。树的路径个数为|I|-1，由于是最短路径每条路径长度不超过d，因此，插入的连接节点个数不超过d(|I|-1)。

引理3［23］算法第3步，插入连通节点使得算法第2步已连通的d-hop CDS能具有2-Connect性质，每次循环计算块个数后插入的路径节点个数不超过2β+2d，d为跳数，β同引理1定义。

引理1和引理3证明略，参阅文献［23-24］。

定理2 本文d-hop 2-CDS算法是一个(2β+2d+1)(d+1)β的近似算法，这里d为跳数，β同引理1定义。

证明 令|MCDS|表示G中最小连通支配集内顶点的个数，OPT(G)表示最优d-hop 2-连通支配集中顶点的个数，显然，d-hop 2-连通支配集也是CDS，D，I，D2和D3分别是本算法输出的d-hop 2-连通支配集，本算法第1步产生的d-hop IS，第2步添加的连接点集合以及第3步再次添加的使2-连通的连接点集合。其中第3步循环次数(即块的个数)最多|I|+|D2|-1次，则由引理1至引理3，有:

所以，本算法的近似比为:

3.2 算法仿真分析

仿真环境1:100×100的矩形区域，传感器节点随机布置，通信半径 r=15时，本文算法产生的 d-hop独立支配集和2-连通支配集(d=1，2，3，4)随节点个数 n(n=80，100，150，200，250，300)的变化关系如图4(a)和4(b)所示。从图中可得:随着d的增大，支配集或连通支配集的大小急剧缩小，即可选取更少的节点作为虚拟骨干网以支配其余节点，这验证了支配集的d-hop性质可以大大减小支配集节点数目。另外，随着节点个数n的增大，d-hop DS缓慢增加，这是由于节点密度虽增加，原本的支配节点依然可支配新增加的大多数节点。

图4 当通信半径r=15时，随n的变化关系

仿真环境2:100×100的矩形区域，传感器节点随机布置，节点个数n=100时，本文算法产生的d-hop支配集和2-连通支配集(d=1，2，3，4)随通信半径 r(r=12，14，15，16，18，20)的变化关系如图5(a)、5(b)所示。半径r增大，平均节点度增加，网络图也更加密集，支配节点数量下降。说明在密集网络图中本算法具有较好性能。

图5 当n=100，通信半径为r时，随r的变化关系

4 结论

本文提出了基于UDG网络模型的d-hop 2-连通支配集的分布式构造算法。先构造d-hop独立支配集，然后连通形成 d-hop连通支配集(d-hop CDS)，最后再次扩充路径形成2-连通集。理论和实验都表明:d-hop CDS有着比单跳CDS少得多的连通支配节点个数，因而采用d-hop CDS作为虚拟骨干网也就可以大大减少骨干节点的个数，增加了网络的可扩展性和网络容量。另外2-连通的性质也可以增加虚拟骨干网容错性和可靠性。下一阶段的研究将着重在节点自由运动模式下d-hop连通支配集的维护代价的探讨。

［1］ Garey M R，Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness［M］.New York:W.H.Freeman and Company，1990:71-72.

［2］ Zheng C，Sun S X，Huang T Y.Constructing Distributed Connected Dominating Sets in Wireless Ad Hoc and Sensor Networks［J］.Journal of Software，2011，22(5):1053-1066.

［3］ Yang S H，Wu T，Cao J N.Connected k-Hop Clustering in Ad Hoc Networks［C］//Proceedings of ICPP:2005 International Conference on Parallel Processsing.Oslo，Norway，2005:373-380，649.

［4］ Theoleyre F，Valois F.A Self-Organization Structure for Hybrid Networks［J］.Ad Hoc Networks，2008，6(3):393-407.

［5］ Yang H Y，Lin C H，Tsai M J.Distributed Algorithm for Efficient Construction and Maintenance of Connected k-Hop Dominating Sets in Mobile Ad Hoc Networks［J］.Mobile Computing，2008，7(4):444-457.

［6］ Rieck M，Pai S，Dhar S.Distributed Routing Algorithms for Multi-Hop Ad Hoc Networks Using d-Hop Connected d-Dominating Sets［J］.Computer Networks，2005，47(6):785-799.

［7］ Gao X F，Wang W，Zhang Z，et al.A PTAS for Minimum d-Hop Connected Dominating Set in Growth-Bounded graphs［J］.Optimization Letters，2010，4(3):321-333.

［8］ Janacik P，Kujat A.Biologically-Inspired Construction of Connected k-Hop Dominating Sets in Wireless Sensor Networks［C］//Proceedings of SASO:2009 Third IEEE International Conference on Self-Adaptive and Self-Organizing Systems.San Francisco，California，USA，2009:103-114，294.

［9］ Nguyen T N，Huynh D T.Connected d-Hop Dominating Sets in Mobile Ad Hoc Networks［C］//Proceedings of 2006 4th International Symposium on Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks.2006:138-145，734.

［10］ Das B，Bharghavan V.Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets［C］//Proceedings of ICC’97:1997 IEEE International Conference on Communications-Towards the Knowledge Millennium.Montreal，1997，1-3:376-380，1743.

［11］ Min M K，Du H W，Jia X H，et al.Improving Construction for Connected Dominating Set With Steiner Tree in Wireless Sensor Networks［J］.Journal of Global Optimization，2006，35(1):111-119.

［12］ Dai F，Wu J.An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2004，15(10):908-920.

［13］ Alzoubi K M，Wan P J，Frieder O.Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks［C］//Proceedings of MOBIHOC.EPFL Lausanne，Switzerland，2002:157-164.

［14］ Adjih C，Jacquet P，Viennot L.Computing Connected Dominated Sets with Multipoint Relays［C］//Proceedings of Ad Hoc ＆ Sensor Wireless Networks(AHSWN)2005:27-39.

［15］ Gerla M，Tsai J T C.Multicluster，Mobile，Multimedia Radio Network［J］.Wireless Networks，1995，1(3):255-265.

［16］ Sausen P S，Spohn M A，Lima A M N，et al.Boundeddistance Multi-Coverage Backbones in Wireless Sensor Networks［C］//Proceedings of SAC:2007 ACM Symposium on Applied Computing.Seoul，Korea，2007:203-208.

［17］付永生，李善平，周波.无线传感网络中能量均衡的连通支配集算法［J］.传感技术学报，2010，23(8):1142-1145.

［18］ Dai F，Wu J.On Constructing k-Connected k-Dominating Set in Wireless Networks［C］//Proceedings of Special Issue 19th International Parallel and Distributed Processing Symposium(IPDPS).2005.

［19］ Wu Y，Li Y.Construction Algorithms for k-Connected m-Dominating Sets in Wireless Sensor Networks［C］//Proceedings of MobiHoc’08 Proceedings of the 9th ACM international Symposium on Mobile Ad Hoc Networking and Computing.New York，2008:83-90.

［20］ Liu Z L，Tian F，Xu J M.Probabilistic Analysis of upper Bounds for 2-Connected Distance k-Dominating Sets in Graphs［J］.Theoretical Computer Science，2009，410(38-40):3804-3813.

［21］ Schleich J，Danoy G，Bouvry P，et al.Blackbone2，an Efficient Deterministic Algorithm for Creating 2-Connected m-Dominating Set-Based Backbones in Ad Hoc Networks［C］//Proceedings of the Seventh Acm International Symposium on Mobility Management and Wireless Access，Mobiwac09，2009:91-98.

［22］ Wang F，Thai M T，Du D Z.On the Construction of 2-Connected Virtual Backbone in Wireless Networks［J］.IEEE Transactions on Wireless Communications，2009，8(3):1230-1237.

［23］ Li X Y，Zhang Z.Two Algorithms for Minimum 2-Connected r-Hop Dominating set［J］.Information Processing Letters，2010，110(22):986-991.

［24］ Zahng Z，Liu Q，Li D.Two Algorithms for Connected r-Hop k-Dominating Set ［J］. Discrete Mathematics， Algorithms and Applications，2009，1(4):485-498.