路由约束下的高效可靠虚拟骨干网构建算法

罗锦晖，刘春颜，王越涛，李洋，赵蕴龙

南京航空航天大学，计算机科学与技术学院，江苏 南京 211106

无线传感器网络(wireless sensor network,WSN)因为其成本低、易部署、使用方便等特性被广泛应用于环境监测、健康应用、灾难救援、战场监控、交通控制、移动计算以及军事行动等各场景中。在大规模无线传感器部署过程中，特别是野外环境监测场景，无线传感器常被大量且随机地投掷在覆盖区域内，由此构建的无线传感器网络在信息收集与传输过程中极易造成拥塞、骨干节点过度消耗、网络拓扑不稳定、网络生命周期短等问题。为解决以上问题，常采取分层分簇路由和虚拟骨干路由等策略来引导信息定向传输。其中虚拟骨干网技术由Ephremides 等[1]于1987 年提出，并得到学术界广泛支持和采用。在虚拟骨干网中，每个节点将消息发送到临近虚拟骨干网中的骨干节点，信息沿这些骨干节点组成的虚拟路由网转发至其目的节点。因此，当路由路径搜索空间被限制在虚拟骨干网中，可以得到更短的路由路径搜索时间、更小的路由表以及更便捷的路由维护，从而大大提高无线传感器网络转发效率，延长网络生命周期。

在虚拟骨干网络中，通常以平均骨干路径长度(the average backbone path length，ABPL)[2]来衡量网络中节点间传输路径的长度，间接反映网络中信息传输的成本或能耗。无线传感器网络中虚拟骨干网构建问题已转化为图论中的连通控制集(connected dominating set，CDS)问题，学者们针对路由约束、最小权重、错误容忍等特性的虚拟骨干网开展研究，设计了一系列可推导、可验证的近似算法，为通过连通控制集构建特定约束下的极小虚拟骨干网提供了理论方法。

在一些特定无线传感器网络中，因为节点的移动、失效等原因导致网络的拓扑结构不稳定，因此需要构建具有容错性的虚拟骨干网。在图论中此问题可通过以k-连通m-控制集算法构建连通控制集的方法来解决，即要求虚拟骨干网C以外的任一点都至少被C中m个点所控制，而C导出的子图的连通度至少为k。采用(k,m)-CDS 作为虚拟骨干，即使min{k-1，m-1}个节点发生故障，虚拟骨干仍能正常工作。

本文提出同时考虑网络容错性和平均路由长度的虚拟骨干网构建问题，并将该问题转化为（1，m）-α路由约束的最小连通控制集(minimum connected dominating set, MCDS)问题，同时给出时间复杂度为O(n3)的构建算法，最后通过仿真实验验证其有效性。

1 国内外研究现状

1.1 考虑路径长度的连通控制集

在虚拟骨干网络中，骨干节点越少，整个网络的架设成本也越低，同时也能保证较高的通信效率。因此学者们从大量节点中选择MCDS 组成骨干网络，构造MCDS 是一个非确定性多项式(non-deterministic polynomial， NP)完全问题[3]。2005 年Mohammed 等[4]首次提出了以直径和为附加因子生成控制集的算法，实验结果表明，该算法在不增加解的规模的情况下，可以生成直径较小的控制集。2007 年Li 等[5]开始研究无线网络中直径有界的虚拟骨干网构造问题，并提出了一种启发式算法，该算法的时间复杂度为O(n2)。Kim 等[6]改进自己的原有算法，提出一个分布式CDS 构造算法，使近似比减少到6.906。

2010 年，Ding 等[7]发现在之前的研究中只是意识到路由路径长度的重要性，没有考虑最小路由约束(minimum routing cost，MOC)，不能保证通过其CDS 的路由路径是原始网络的最短路径。在文献[7]中提出了MOC-CDS，MOC-CDS 路由可以保证任意一对节点之间的每一条路由路径也是网络中的最短路径，所以可以大大降低能耗和延迟，该算法的近似比为(1-ln2)+2lnδ，δ为网络中的最大节点度。数值实验显示MOC-CDS 的尺寸非常大，为了平衡虚拟骨干的尺寸和路由成本，Du 等[8-10]又提出了α倍路由约束问题(αMOCCDS)。对于α≥5，他们给出了单位圆盘图中αMOC-CDS 的常数近似算法。该算法首先以贪婪的方式构造图G（V，E）的极大独立集I，然后把集合I中的元素都放入集合D。对于每一对属于I的节点u,v，若它们满足其经过D的路径长度dD(u,v)≤4，那么找到它们之间的一条最短路径，并把该路径上的所有点放入D中，最终得到|D|≤121|I|。Liu 等[11]针对各节点传输半径不同的异构网络提出了α-MOC-强联通双向控制集（ strongly connected bidirectional dominating set，

SCBDS）问题，并给出了近似比为(3(8ρ+1)2(2ρ+1)2/2)Mopt（1,m）的近似算法，其中ρ为最大与最小传输半径之比，Mopt（1,m）为二维空间下最小m重连通控制集问题的最优解。Putwattana 等[12]改进了Liu 的算法，验证了对于任意在I中并且d(u,v)≤3 的一对点u,v，计算出连通u,v的最短路径，并把最短路径的中间节点全部放入C集合中，α倍路由约束连通控制集D=C∪I，D的导出子图是连通的，同时满足dD(u，v)≤5d(u，v)。改进过后的α-MOCSCBDS 近似比为2(6ρ+1)2(2ρ+1)2。

1.2 考虑容错性的连通控制集

Dai 等[13]最先提出将k-连通m-控制集问题引入容错性虚拟骨干网的研究中。他们提出了最小(k，m)-CDS 的3 种启发式算法。但是生成的连通控制集的大小没有给出上限。Wu 等[14]提出了一个构造k-连通m-控制集的分布式算法，这个算法的优点就在于它的信息开销很低。THAI 等[15]研究了k-连通m-控制集并且首次提出了1-连通m-控制集和k-连通k-控制集的近似算法。基于这2 个算法，提出了对于k-连通m-控制集的一般算法。Wang 等[16]提出了增强连通控制集(connecting dominating set augmentation，CDSA)，构造一个能够克服无线节点故障的2-连通CDS。其主要思想是首先构造一个连通控制集，然后通过在主干中添加新的节点将其扩充为2-连通，通过证明CDSA 具有72 的恒定近似比， 从而保证了CDSA 的质量。Shang 等[17]指出考虑容错的虚拟骨干网中，利用单位圆盘图和一个较小的m(m≤2)，迭代地选取m个极大独立集，它们的并集构成一个m-控制集，同时也给出了(1，m)-CDS 的常数近似比，并讨论了如何设计具有任意大m问题的近似算法。Kim 等[18]得到了单位圆盘图中最小(3，m)-CDS 问题的常数近似算法，但该算法非常复杂，近似比也很大，如(3，3)-CDS 的近似比为280。Wang 等[19]扩展了文献[17]中容错虚拟骨干网的研究，运用2-连通但非3-连通图的Tutte-分解简化了该算法，并改进了近似比到5α，特别当k=m=3 时，近似比可以降到62.3，其中α为(2,m)-CDS 的近似比。Shi 等[20]提出基于单位圆盘图上最小节点加权Steiner 网络问题的常数近似算法，这个算法是k-连通m-控制集的虚拟骨干网，其中k和m为m≥k的2 个固定常数，得到(k，m)-CDS 问题常数近似比。当k≥3 时，该近似比为(α+5ρ)；当k=2 时，该近似比为(α+2.5ρ)，其中α为最小m控制-CDS 的近似比，ρ为最小k-连通CDS 的近似比。Zhou 等[21]把容错性和异构网络结构同时考虑进去，提出了异构无线传感器网络(3，m)-CDS 的近似算法。文中性能比最大为γ，其中α≥4 时，γ=α+8+2ln(2α-6)；α＜4 时，γ=3α+2ln2，α是极小(2，m)-CDS 问题的近似比。如果将算法应用到单位圆盘图上，则近似比将小于27。

2 问题描述

利用图G=(V，E)描述网络拓扑结构，V为网络中所有节点，E为网络中的所有边。假设C为V的一个子集，如果含有V/C中的每个顶点都在C中有邻点，则子集C称为控制集。如果由C导出的子图GC是连通的，则称C为连通控制集。为了进一步解决传感器网络中由于网络节点失效等原因导致的网络拓扑不稳定问题，使用图论中k-连通m-控制集解决网络的容错性问题；同时通常使用α倍路由约束来体现虚拟骨干网的高效。为此本文给出以下定义。

定义1k-连通m-控制集：给定图G=(V,E)中的1 个连通控制集D是k-连通m-控制的，当且仅当任意大小不超过k-1 的子集D′⊂D使得GD-D′仍然是连通的，同时存在1 个连通控制集D是G的m控制集，当且仅当对于任意的节点u∈VD，则u在D中至少存在m个邻居。

定义2最小路由约束连通控制集：MOCCDS 是寻找一个最小的点集合D⊆V，这个集合D有以下特性：

1)∀u∈VD，∃v∈D，使(u, v)∈E。

2) 导出子图GD是连通的。

3) ∀u,v∈V， 若Dist(u, v)＞1， 那么∃pi(u,v)∈Pi(u,-v),pi(u,v){u,v}⊆D。其中pi(u, v)={u,w1,w2,···,wk,v}，表示点u, v之间第i条最短路径；Dist(u,v)表示点u, v间的最短路径跳数；Pi(u, v)表示u,v间所有的最短路径。

定义3α倍路由约束连通控制集：αMOCCDS 为点集合D⊆V，这个集合D有以下特性：

1) ∀u∈VD，∃v∈D，使(u, v)∈E。

2) 导出子图GD是连通的。

3) ∀u,v∈V，若Dist(u, v)＞1，那么pD(u, v)上的所有中间节点都属于D并且dD(u, v)≤αd(u,v)。其中pD(u, v)表示u, v间在D上的最短路径；P(u,v)表示u, v间的最短路径；dD(u, v)和d(u, v)分别表示pD(u, v)和P(u, v)上中间节点的数量。

定义4考虑容错性的α倍路由约束问题(1,m)-αMOC-CDS：给定1 个单位圆盘图G=(V,E)，子集S被称为G的1 个考虑容错性α-路由约束的连通控制集，则S必须满足以下4 个个条件：

1）S是G的1 个控制集。

2）由S导出的子图GS是连通的，即GS中的任意2 点之间都至少存在1 条路径，使得2 点之间可以相互传输信息。

3）对于给定的常数α≥1，任意u, v点都满足dD(u, v)≤αd(u, v)。

4）G中所有非骨干节点都至少被m个骨干节点所支配。

3 算法与理论分析

3.1 理论分析

寻找最小路由约束连通控制集的问题已经被证明是NP 难问题，部分文献提出了通过寻找MOC-CDS 的近似算法来解决这个问题。这些近似算法一般分为2 个阶段：第1 阶段构造一个极大独立集；在第2 阶段，添加其他节点作为连接节点连通极大独立集来构成一个完整的最小路由约束连通控制集。引理1～3 将为算法第2 阶段提供理论支撑。

引理1G为一个连通的图，D为G的一个连通控制集。d(u, v)为图G中u, v这2 点的最短路长度，dD(u, v)为连接u, v这2 点的中间节点全在D中的最短路长度。假设任意满足d(u, v)=2 的一对节点u, v都有dD(u, v)-1≤α，那么dD(u, v)-1≤α(d(u, v)-1)。

引理2G为一个连通的图，D为G的一个连通控制集。假设任意满足d(u, v)=2 的一对节点u,v都有dD(u, v)-1≤α，那么dD(u,v)≤αd(u,v)。

证明：根据引理1，

引理3[8]I为图G的一个极大独立集，D为包含I的一个连通控制集。假设对任意满足d(u,v)≤4 且u,v都在I中的一对节点u,v，都有dD(u,v)≤4，那么dD(u,v)≤5d(u,v)。

Du 等[8]证明了引理1～3。根据这3 个引理，可以得知在无向图G中，求出G的控制集C后，将C中的所有节点放入D中。若任意一对节点u,v∈D并且d(u,v)＜4，把u和v之间最短路径的所有节点都加到D上，可以得到dD(u,v)≤5d(u,v)。Putwattana 等[12]对异构网络中的路由约束提出了改进。受此改进的启发，我们可以考虑无向图G和G的控制集C，如果任意一对节点u, v∈D和d(u,v)＜3，把u和v之间最短路径的所有节点都加到D上，同样可以得到dD(u,v)≤5d(u,v)，理论分析过程如引理4。

引理 4I为由第1 阶段构造的极大独立集，D为包含I的1 个连通控制集，如果对于每一对属于I的节点u,v，若满足dD(u,v)≤3，那么找到它们之间的一条最短路径，并把该路径上的所有点放入S中，它们的诱导子图GS是连通的，并且对于图中任意一对节点u,v，都满足dD(u,v)≤5d(u,v)。

证明：考虑V中一对节点u,v，它们在图G中的最短路径为k，假设这条路径为(u=w0,w1,· ··,wk-1,v=wk)(如图1 所示)，已知GS是连通的，对该路径中每一对相邻的wi和wi+1：

图1 连接u, v 的最短路径

1）若wi和wi+1其中一个是I中的节点，不失一般性假设wi不是I中的节点，那么在原图G中Ddom(wi)domD(wi)和wi之间必有1 条只经过D中的点同时小于等于3 的路径。（Ddom(wi)为I中支配wi的节点）。

2）若wi和wi+1都不是I中的节点，那么存在Ddom(wi)和Ddom(wi+1)分别支配w1和w2。 无论Ddom(wi)和Ddom(wi+1)是否为同一个点，均有图G中Ddom(wi)和Ddom(wi+1)之间必有1 条只经过D中的点同时小于等于3 的路径。又因为由已知条件可得原图G中存在1 条长度为3 的路径(Ddom(wi),wi,wi+1,Ddom(wi+1))。那么可以得出：

式中：k≥1，Ddom(u)为集合C中控制u的的点。

3.2 算法设计与分析

本节设计一个3 阶段算法(1,m)-αMOCCDS 构建基于最小权重连通控制集的α倍路由约束虚拟骨干网，该算法是一种基于极大独立集的连通控制集构建方法，算法过程简述如下。

第1 阶段：构建极大独立集I1作为骨干节点。

第2 阶段：以动态规划思想连接I1中的节点构建连通控制集。

第3 阶段：通过一个迭代算法构建m-控制集。不断求解普通节点集中的极大独立集Im，并加入第2 阶段所求的连通控制集中，通过m-1 次迭代，确保网络中任意一个普通节点都被至少m个骨干节点所控制。

算法1构建αMOC-CDS。引用文献[8]中的Algorithm 2 作为第1 阶段构造极大独立集（maximum independent set, MIS）的算法1，该算法贪婪地寻找节点间度最小的节点作为骨干节点，最终构成一个极大独立集。

算法2构建连通集合C。 对控制集(dominating set, DS)中任意一对满足d(u,v)≤3的节点u, v，求出u, v间在图G中的最短路径，并把路径中的点都加入集合C中，算法如下。

输入：一个连通单位圆盘图G= (V,E)，求出图G的极大独立集I

输出：连通集合C

NodeNumber←|V|

D←I←Construct-MIS(G,V,NodeNumber)

W[v] ←0 for allv∈I

W[v] ←1 for allv∈VI

for allu∈I

w[u][L] ←∞, for allu∈Vand 0 ≤L≤2

w[u][0] ←0

p[u][0] ←Ø

Used←{u}

forL= 0 to 2 do

newUsed←Ø

for allv∈ Used do

for allx∈ Neighbor[v] do

ifw[v][L]+W[x] ＜w[x][L+1]

w[v][L+1]←w[v][L]+W[x]

p[x][L+1] ←v

newUsed←newUs∪{x}

end if

end for

end for

Used←newUsed

end for

for allv∈Isuch thatd(u,v) ≤ 3 do

ifw[v][l] is minimum inw[v][L] then

Path←Path ∪p[v][l]

end if

end for

C←C∪ Path

W[v]←0 for allv∈C

end for

引理5[13]无向图G=(V，E)是一个单位圆盘图，m是一个自然数并且δ(G)≥m-1，使Dm*为图G的最小（1，m）-CDS，S为图G的一个MIS，那么可以得到

具体证明过程在文献[17]中给出。

算法3构建基于(1,m)-连通控制集的α倍路由约束虚拟骨干网构建算法。该算法的基本思想是首先使用算法1 和算法2 中提出的方法生成αMOC-CDS，然后依次使用算法1 产生一个(m-1)个MIS，使得每个非骨干节点都由m个以上骨干节点中的顶点控制，算法如下。

输入：一个连通单位圆盘图G=(V,E)

输出：基于(1,m)-连通控制集的α倍路由约束虚拟骨干网D

NodeNumber←|V|

I1←Construct-MIS(G,V,NodeNumber)

C←Construct Connected Set (G,I1)

S1←VI1

D←I1∪C

fori=2 tomdo

Ii← Construct-MIS(G,Si-1, NodeNumber)

Si←Si-1Ii

D←D∪Ii

end for

returnD

3.3 算法近似比分析

引理6若I为极大独立集，那么对于任意u∈I，|{v∈I|0 ＜d(u,v)≤3}|≤48。

证明：对于每个节点v∈I，且d(u,v)≤3，构建中心为v、半径为0.5 的圆盘，再构建一个中心为u、半径为3.5 的大圆盘，在这个大圆盘中能容纳的互不相交的半径为0.5 的圆盘数量，即为

因为u点也在其中，所以

引理7由第2 阶段构成连通集合具有以下性质|C|≤48|I|，其中I是第1 阶段构建的极大独立集。

证明：构造一个图G，它的节点集为I，边集为{(u, v)|u, v∈I，0＜d(u, v)≤3}。根据引理5 可知，G中节点最大的度为48，所以G包含最多24 |I|条边。第2 阶段中，因为d(u, v)≤3，每对极大独立集节点对之间最多加2 个点，所以|C′|≤2×24|I|=48|I|。

引理8通过算法3 构成的（1，m）-αMOCCDS 中， 当m≤5时，当m＞5时其中为1 个图G的最小(1,m)-CDS。

继而可以推出

引理9算法3 中构造的(1，m)-αMOCCDS 构建的连通控制集D的上界大小如下：当m≤5时，为(240/m+5)Mopt（1,m），其中Mopt（1,m）指极小(1，m)-CDS 的最优解；m＞5时，为54Mopt（1,m）。同时对于任意一对节点u,v，都有dD(u,v)≤5d(u,v)。

证明：根据引理7、引理8 可知：当m≤5时，当m＞5时，

根据引理4 可知，在D中，任意一对节点u,v都有dD(u,v)≤5d(u,v)，同时每个非骨干节点都被m个以上的骨干节点支配。

4 仿真结果与分析

本节主要介绍了(1，m)-αMOC-CDS 的仿真实验结果以及与相关算法的对比分析。

4.1 实验环境

4.1.1 计算机平台性能

处理器：AMD Ryzen 5 3500X 6-Core Processor，4.00 GHz；RAM，16.0 GB；系统类型：64 位操作系统，基于x64 的处理器；编程IDE：MATLAB。

4.1.2 无线传感器网络参数

在仿真中，具有不同传输范围的无线传感器网络的参数设置如下。传感器由一组随机部署在以100×100 为边界的欧几里得平面上的节点来模拟，节点总数分别为100、200、300、400 个，传输半径分别为15、20 和25，针对每组参数构造100个随机图，每个随机图进行100 次实验取平均值。

4.2 对比算法

目前只有分别考虑容错性的(k,m)-连通控制集问题和α倍路由约束连通控制集问题的解决方案，没有同时考虑容错性和α倍路由约束问题解决方案。仿真实验在参数m=1、2、3 时，分别用(1,m)-MOC-CDS 算法在随机网络图中构建虚拟骨干网，并进行多次试验分别统计MOC-CDS、(1,2)-αMOC-CDS 和(1, 3)-MOC-CDS的规模大小。其中当m=1 时，(1, 1)-MOC-CDS 就是一个普通的αMOC-CDS。

4.3 仿真结果

最后利用不同传输半径CDS 的大小比较仿真结果。传输半径为15 情况下的仿真结果如图2 所示，传输半径为20 情况下的仿真结果的描述如图3 所示，传输半径为25 情况下的仿真结果如图4 所示。

图2 传输距离为15 时3 种算法CDS 大小

图3 传输距离为20 时3 种算法CDS 的大小

图4 传输距离为25 时3 种算法CDS 大小

4.4 仿真结果比较分析

图2～图4 给出了MOC-CDS、(1,2)-MOC-CDS和(1,3)-MOC-CDS 算法生成的CDS 大小的仿真结果，由这3 个图中可以看到，随着传感器节点的总数量从100 个增加到400 个，每个算法生成的CDS 的平均大小略有增加，这是合理的。因为所有的算法都需要在最短路径上有更多的中间节点连接更多的控制节点来构建CDS。同时随着传感器节点的总数量从100 个增加到400 个，3 种算法骨干节点增长速度在降低，这也是合理的。因为画布总大小不变的情况下，随着节点个数的增加，整个传感器网络变得十分稠密，执行算法1 和算法2 所需要增加的节点变少，骨干网节点数随着网络变得稠密逐渐趋于饱和。此外，我们还可以看到由算法MOC-CDS 生成的CDS 的平均大小受到引理8 近似比的限制。通过对比实验可以得出，在传输半径为15、20 和25 时，构建(1,2)-MOC-CDS和(1,3)-MOC-CDS 所需要增加的CDS 大小不超过15%和30%，这是一个可以接受的范围，验证了(1,m)-MOC-CDS 算法的可行性。

综上所述，(1,m)-MOC-CDS 算法有效地解决了考虑容错性的α倍路由约束问题，在满足了α倍路由约束(α≥5)的情况下，充分考虑了整个网路的容错性问题。通过实验可以验证(1,m)-αMOC-CDS 的有效性，同时由引理3 证明可得，对于任意一对节点u,v都有dD(u, v)≤5d(u, v)。

5 结束语

本文研究了无线传感器网络中具有容错的虚拟骨干网构建算法，该算法同时考虑容错性和路由约束两方面约束。

关于如何有效延长网络生命周期问题，还有一种方法是动态更新骨干节点，形成轮换来实现网络中节点的负载均衡，从而延长网络生命周期。这种动态更新虚拟骨干节点方法的正确性和有效性有待进一步研究和验证。关于网络鲁棒性问题，可使用基于k-连通m-控制集和α 倍路由约束的方法构建虚拟骨干网，通过双重约束来保证虚拟骨干网的鲁棒性，其近似比和虚拟骨干网性能有待进一步研究和论证。