异质无线传感器网络虚拟骨干重构

何 峰，梁家荣，3，黎昌珍

（1.广西大学 计算机与电子信息学院，南宁 530004；2.广西大学 公共管理学院，南宁 530004；3.广西多媒体通信与网络技术重点实验室，南宁 530004）

0 概述

无线传感器网络（Wireless Sensor Network，WSN）由许多无线结点组成，这些结点通常由数据处理单元、通信模块和有限的能源设备等组成。随着大规模集成电路、嵌入传感器及无线通信技术的发展，无线结点的成本将不断下降而其性能变得越来越好。同时，无线传感器结点一旦有机地分布在应用区域，它们不需要任何的基础设施支撑就能自发地连接成一个通信网络。因此，人们认为无线传感器网络将会在下一代互联网中起到极为关键的作用，目前已被广泛地应用于灾难 救援［1］、自动驾驶［2］、环境监测［3］、智能家居［4］等诸多领域。

无线传感器网络的结点通常是电池供能的，是一个有限的能源供能。这意味着能耗效率是无线传感器网络中一个非常重要的问题。在无线通信中任意两个传感器间传输数据所消耗的能量与它们之间的距离呈超线性增加。为了节约电池能量，多数无线传感器网络采用多跳通信而非长距离直接通信模式。然而，多跳通信往往会导致网络中增加大量的冗余信息及巨量的无线信号冲突和干扰，进而使得结点消耗能量来转发这些信息而造成不必要的巨量能耗。此外，网络中大量的冗余信息及巨量的无线信号冲突和干扰也容易导致广播风暴问题。针对这个问题，一个有效的办法是在无线传感器网络中选择部分结点来承担网络的路由通信任务［5］，这些承担路由任务的结点称为虚拟骨干（Virtual Backbone，VB）。

在无线传感器网络中采用较小虚拟骨干承担路由任务，可以产生较少的路由开销，延长网络的寿命。理论上，无线传感器网络的虚拟骨干可以建模为单位圆盘图的一个连通控制集（Connected Dominating Set，CDS）。传感器网络中的最小虚拟骨干问题就转化成单位圆盘图的最小连通控制集（Minimal Connected Dominating Set，MCDS）问题。然而，单位圆盘图的MCDS 问题已被证明是一个NP-hard 问题［6］。研究者们更多的是关注设计近似算法求解单位圆盘图的MCDS 问题以获得这个问题的次优解，通常可采用下述方法构造一个连通控制集：1）构造一个极大独立集；2）在极大独立集中添加结点使得它是一个连通控制集。因此，为了获得更小的连通控制集，一部分研究者考虑如何构造更小的极大独立集［7-9］，也有一部分研究者考虑如何在方法2）中添加更少的点［10-12］。

在实际应用中，并非所有的无线传感器网络都是同质网络，也就是并非每一个传感器结点的传输半径都是相同的。在更多的情况下，不同的传感器结点有不同的传输范围，如果仍把这样的无线传感器网络建模成单位圆盘图，明显是不合适的。对于这种具有不同传输范围的结点组成的传感器网络（称为异质传感器网络），使用圆盘图来抽象更为合适［13］。注意到单位圆盘图的MCDS 问题是圆盘图的MCDS 问题的特例，这就意味圆盘图的MCDS 问题也是一个NP-hard 问题［14］。

在无线传感器网络通信中，由于电池剩余容量减少和自然环境变化等因素的影响，传感器结点之间的直接通信可能会失效，这可能会导致整个网络的路由通信不畅甚至瘫痪。因此，在无线传感器网络中如何设计一个虚拟骨干来承担网络的路由任务以应对无线结点故障的影响显得非常重要。

目前，基于容错的要求，一些研究者研究了无线传感器网络的容错虚拟骨干［被建模为(k,m)-CDS，能够容纳至多(k-1)个故障结点，其中，m≥k≥1］的构建问题并取得了一些研究成果。例如：文献［15］提出一个在圆盘图中构建(3,m)-CDS 的常数近似算法，其中，m≥3；文献［16］研究了圆盘图中最小(4,m)-CDS的构建问题，其中，m≥4；文献［17］研究了圆盘图中最小(k,m)-CDS 的构建问题，其中，m≥k≥1。

然而，在一个给定的无线传感器网络中，尽管构建一个(k,m)-CDS 能实现容错功能，但往往这样的连通控制集的基数较大，并且随着k值的增加而增加［18-19］。为了降低连通控制集的基数，文献［20］提出一种称为连通控制集重构的策略，并基于这一策略，对于给定的具有故障结点的同质无线传感器网络，设计了集中式的近似算法重构连通控制集，并获得了较为理想的效果。然而，文献［20］策略有两个不足：一是重构的连通控制集只具有结点容错性，不具有链路容错性；二是考虑的无线传感器网络是同质网络。为了进一步拓展无线传感器网络虚拟骨干的构建理论，需要研究如何在异质无线传感器网络中构建具有链路容错性的连通控制集，但目前还鲜见这方面的研究成果。

针对文献［20］策略的两个不足，本文研究具有链路失效的异质无线传感器网络的连通控制集重构问题，设计虚拟骨干重构近似算法（ZREA22），由该算法重构的连通控制集可实现在链路失效情况下网络路由通信不但不受影响，而且路由通信的开销不会过多增加。

1 预备知识

1.1 网络模型

假设一个异质无线传感器网络传输半径为r∊[rmin,rmax]，其中，rmin、rmax分别表示传输范围最小、最大的结点的传输半径。对于这样的一个异质无线传感器网络，可以使用一个圆盘图G=(V,E)来抽象，其中，V表示网络中所有传感器结点组成的集合，E表示网络中所有链路组成的集合。对于任意的一对结 点t和w∊V，当dist(t,w)≤rt，那 么G=(V,E)中有一条从t指向w的有向边（dist(t,w)表示rt和rw的欧氏距离）；特别地，当dist(t,w)≤min{rt,rw}时，rt和rw之间就有一条双向边，记为(t,w)∊E。为了讨论方便，仅考虑抽象圆盘图G=(V,E)的边都是双向边的异质无线传感器网络的虚拟骨干的重构问题，这种抽象圆盘图G=(V,E)事实上是双向链路圆盘图（Disk Graph with Bidirectional links，DGB）。一个双向链路圆盘图示例如图1 所示。

图1 双向链路圆盘图示例Fig.1 Example of a disk graph with bidirectional links

1.2 符号和定义

假设G=(V,E)表示一个双向链路圆盘图，S⊂V，t和w∊V。文中用到的一些符号具体如下：

1）G[S]，集合S中的点所产生的诱导子图。

2）N(w)，顶点w的所有邻居结点组成的集合。

3）N[w]，N(w)∪{w}。

4）N[S]，

5）Sopt，图G的一个最小连通控制集。

6）Iw,d，顶点w的Id。

7）A(S)，N[S]-S。

8）dh(t,w)，顶点t和w之间的最短路径长度。

9）rmax(rmin)，最大（最小）传输半径。

10）ρ，传输半径比率

文中用到的相关定义具体如下：

定义1假设集合S⊂V，对于任意的顶点u∊V-S，均有w∊S使得(u,w)∊E，那么称集合S是图G的一个控制集。

定义2假设集合S⊂V，S中任意一对顶点u和w均有(u,w)∉E，那么集合S是图G的一个独立集。

定义3假设集合S⊂V是图G的一个独立集，若对于任意的顶点w∊V-S均有S∪{w}不是一个独立集，则称集合S是图G的一个极大独立集。

定义4假设集合S是图G的一个极大独立集，若子图G[S]是连通的，则称集合S是图G的一个连通控制集。

定 义5若对于 任意的(x1,y1),(x2,y2)∊ℝ2，W(x1,y1)>W(x2,y2)，当且仅当下述条件之一成立，则函数W：ℝ2→ℝ 称为权函数，其中，ℝ 表示实数集，ℝ2表示二维实向量空间：

1）x1>x2。

2）x1=x2且y1>y2。

在本文中，图G的顶点r的权函数定义为W(N(r),Ir,d)。

定义6假设一个连通图G=(V,E)中的所有结点已被染成了白色、红色、蓝色或者灰色，S⊆V。若下述任意一个条件成立，则称G[S]是图G的一个红蓝连通分支：

1）集合S中仅包含红色结点且G[S]是连通的，同时对于任意的不属于S的红色结点w，G[S∪{w}]是不连通的。

2）集合S中仅包含红色结点和蓝色结点且G[S]是连通的。对于任意的不属于S的红色或蓝色结点w，G[S∪{w}]是不连通的。

为了方便起见，用Cblock表示红蓝连通分支。

定义7假设一个连通图G=(V,E)中的所有结点已被染成了白色、红色、蓝色或者灰色，共有k个Cblock：B1,B2,…,Bk，k≥1。若图G的一条路径P满足下述条 件，则 称P是图G的一条Ln路径，其中，n是一个非负整数：

1）P的两个端点属于集合A，其他结点不属于集合A，并且P的不属于集合A的结点数不超过n，其中，

2）P的两个端点不属于同一个Cblock。

2 ZREA22 算法

2.1 算法原理

为了更好地理解算法执行过程，对其做一个简短的介绍。在算法准备阶段，对于任意输入的连通的双向链路圆盘图G=(V,E)、故障边集M以及图G的一个连通控制集C（可通过现有最新且性能最好的算法［21］得到），计算得到图Gf=(V,Ef)，其中，Ef=E-M。该算法主要分为以下3 个步骤：

1）在图G中，将集合C和A(C)中的点分别染成红色和灰色。接着，在图Gf中计算集合W，一个由图中所有非C及其邻居结点组成的集合，并将W中的点染成白色。选择一个根结点，并计算出图Gf中每个点到根结点的跳数，将图中每个点分层。

2）通过逐层遍历的方式，在图GGf[W]中构造一个极大独立集K。将K中所有点染成红色、K的所有位于子图GGf[W]中的白色邻居染成灰色。

3）对于每一层中的点Vi，迭代地选择一条Ln（1 ≤i≤2）路径以连接图中2 个不同的Cblock，同时将Ln路径的所有中间结点染成蓝色。重复执行上述操作，直到图中仅有一个Cblock，它的所有结点形成图中重构的连通控制集Cr。

2.2 算法流程

为了直观地展现算法执行过程，给出ZREA22算法流程，如图2 所示。

图2 ZREA22 算法流程Fig.2 Procedure of the ZREA22 algorithm

2.3 算法伪代码

算法1ZREA22 算法

3 算法正确性分析

下面证明算法1 的正确性，即通过算法1 可以输出一个重构的连通控制集Cr。

引理1集合K是子图GGF[W]的一个极大独立集。

证明为了证明K是子图GGF[W]的一个极大独立集，首先证明集合W是一个由图Gf中所有未被控制的点组成的集合，即集合W中的点均不是集合C中点的邻居，需要注意的是集合C和M分别是图G的一个连通控制集和故障边集，由算法1 的第1 和2 行可知，集合W中的点均不是集合C中任何一个点的邻居；接着证明集合K是子图GGF[W]的一个极大独立集，当W=∅时讨论是没有意义的，因此考虑当W≠∅时的情况，根据算法1 的第7～12 行的循环可知，任何新加入集合K的点均不是K中其他点的邻居。因此，K是图GGF[W]的一个极大独立集。

定理1集合C∪K是图Gf的一个控制集。

证明由于C是图G的一个连通控制集，考虑如下2 种情况：

1）u∊W-K，根据引理1，集合K是图GGF[W]的一个极大独立集，一定存在一个顶点v∊W使得(u,v)∊Ef。

2）u∊V-W∪C，由算法1 的第1 和2 行可知，一定存在一个顶点v∊C使得(u,v)∊Ef。

因此，对于任意的顶点u∊C∪K，一定存在一个顶点v∊V-C∪K使得(u,v)∊Ef，进而得到集合C∪K是图G的一个控制集。

引理2在算法1 的第14～23 行的每次循环中，对于任意的i∊[0,kmax]，子 图中仅有一个Cblock。

证明由推断法可得：当i=0 时，根据算法1 的第3 行，根结点r即为该Cblock，因此该结论是正确的；当i=1 时，如果存在一个由红色结点集合S⊆V1，则S∪{r}是子图中唯一的Cblock，否则{r}为子图中唯一的Cblock，因此该结论也是正确的；假设当i=k时，该结论是正确的；当i=k+1 时，对于该结论的证明类似于i=1 的情况，因此该结论也是正确的。

定理2算法1 执行结束后，Cr是图Gf的一个重构的连通控制集。

证明由定理1 可知，C∪K是图Gf的一个控制集，那么Cr=C∪K∪H也是图G的一个控制集，因此只须证明Cr是连通的。由引理2 可知，在算法1 的第14～23 行的每次循环中，对于任意的i∊[0,kmax]，子图中仅有一个CblockT。对于Vi中的每个红色结点t，如果T∪{t}不是一个新的Cblock，则图中一定会存在一条Ln路径连接t和w∊T使得T∪X∪{t}是一个新的Cblock。因此，在第14～23 行的while 循环结束后，T∪H一定会是一个新的Cblock，进而得到集合T∪H=C∪K∪H是图Gf的一个重构的连通控制集。

4 算法性能分析

本节给出算法1 的性能分析，包括以下2 个部分：1）算法1 所产生的连通控制集的大小的上界；2）算法1 的时间复杂度。由算法1 可知，在第12 行执行完成后集合包含了图Gf中所有的红色结点。由引理2可知，算法1的第14～23行的每次循环中子图中仅有一个CblockT，进而得到对于任意的t∊Vi∩(C∪K)(2 ≤i≤kmax)，图Gf中一定会存在一条Ln路径连接t和v∊T。因此，当算法的第14～23 行执行完成后有|H|≤n|C∪K|≤n(|C|+|K|)。

引理3在算法1 中路径Ln的中间结点数量为n≤2。

证明该结论的证明与文献［22］中的引理2.3类似，则该结论也是正确的。

因此，当算法1 的第14～23 行执行完成后有|H|≤n(|C|+|K|)≤2(|C|+|K|)。

假 设M1={(t,w)∊M|t,w∊C}、M2={(t,w)∊Ef|t∊C,w∊(V-C)}、M3={(t,w)∊Ef|t,w∊(V-C)}、mi=|Mi| 和m=m1+m2（1 ≤i≤2）。由引理1 可知，集合W是一个由非连通控制集C及其邻居结点组成的集合，集合K是由W产生的诱导子图的极大独立集。根据图论知识可得，|K|≤|W|≤m2。

假设算法1 中输入的连通控制集C的大小不超过αSopt+γ，其中，α>0 是原连通控制集的近似比，γ是一个常数，那么算法1 产生的连通控制集的大小如下：

定理3算法1 能够输出一个大小上界为3αSopt+3(γ+m)的连通控制集，其中，α>0 是原虚拟骨干的近似比，γ是一个常数，m是故障链路的数量，Sopt是最小虚拟骨干的大小。

定理4算法1 的时间复杂度为O(n3)，其中，n表示算法输入图的顶点总数。

证明在算法1 的第1～5 行中，挑选根结点、计算集合W和Vk所需的时间为O(n)。在算法1的第7～12行中，在集合W形成的子图中构造一个极大独立集K需要的时间为O(n2)。在算法第14～23 行的while 循环中，迭代地寻找唯一的一个CblockT、选择一条Ln路径所需的时间花费都是O(n2)。因此，在第14～23 行的循环中，迭代地选择Ln路径连接图Gf中所有的Cblock以形成一个重构的连通控制集所需花费的时间是O(n3)，进而得到算法1 的时间复杂度为O(n3)。

5 仿真实验

为了验证所提ZREA22 算法的性能，通过仿真实验将其与文献［23-24］中构建(2,1)-CDS 和(2,2)-CDS 的算法进行对比。为了对比方便，两个对比算法分别被记为WFSK09 和SHLO14。对于WFSK09算法，首先运行文献［21］中的算法构造一个连通控制集C，然后将C作为WFSK09 的输入以获得一个(2,1)-CDS。对于SHLO14 算法，使用上述相同的C作为文献［25］中算法的输入以获得一个(1,2)-CDS，然后将获得的(1,2)-CDS 作为SHLO14 算法的输入以获得一个(2,2)-CDS。对于ZREA22 算法，随机产生一个故障边集M。如果在网络中移除M中的边后剩余网络仍然是连通的，但原来的连通控制集C不再是剩余图的一个连通控制集，那么将M作为候选故障边集，否则舍弃它并重复上述操作直到产生一个候选的M。随后，使用上述相同的连通控制集C和故障边集M作为该算法的输入以得到一个重构的连通控制集。仿真实验主要包括连通控制集的大小和算法的运行时间两个部分的性能比较。

5.1 参数设置

在实验准备阶段，假设n个传感器被随机地分布在一个大小为100 m×100 m 的虚拟空间中，其中，n从10 变化到100，增量为10。设置每个传感器的传输半径为r∊[rmin,rmax]，其中，最小传输半径rmin固定为20 m，最大传输半径rmax为30 m、35 m 和40 m。在相同仿真参数设置下，随机产生具有不同网络设置的候选网络，即传输半径比率分别为1.5、1.75 和2 的2 连通的双向链路圆盘图。一旦随机产生一个网络，判断它是否为2 连通的双向链路磁盘图，如果它是一个2 连通的双向链路磁盘图，则将其作为实验的候选网络，否则舍弃它。重复执行上述操作，直到产生100 个候选网络。在每个候选网络中分别运行3 个算法并取100 次结果的平均值作为最终的仿真实验结果。

5.2 连通控制集的大小比较

图3 给出了在结点传输半径比率为1.5、1.75 和2时，网络规模变化对连通控制集的大小的影响。由图3 可以看出，对于任意的传输半径比率，随着网络规模的增加，ZREA22、WFSK09 和SHLO14 算法所产生的连通控制集的大小也会相应增加，这是因为在一个固定大小的区域中，随着网络规模的增加，相应会需要更多的点来控制其他的结点，因此将产生一个更大的连通控制集。此外，在网络规模相同时，随着结点传输半径比率的增加，3 个算法所产生的连通控制集的大小也会相应减小，这是因为结点的半径越大，它的邻居结点的数量越多，需要更少的点来控制其他的结点，连通控制集也会更小。此外，ZREA22 算法在应对结点失效且减小连通控制集方面具有较好的效果。具体地，对于每个传输半径比率，ZREA22 算法所产生的连通控制集的大小均会小于WFSK09 和SHLO14 算法所产生的连通控制集的大小。需要注意的是，由图3 可得，相比于WFSK09 和SHLO14算法，ZREA22 算法产 生的连 通控制集的大小分别至少减少了9%和31%。这是因为ZREA22 算法是基于原连通控制集添加结点进行重构，WFSK09 和SHLO14 算法需要在原连通控制集的基础上添加结点使得它是2 连通的。正如上文所述，(k,m)-CDS 往往比较大并且随着k值的增加而增加，这意味着它需要添加大量的结点，然而ZREA22 算法仅是重新构造一个新的连通控制集，所需添加的结点数量会比较少。因此，ZREA22算法所产生的连通控制集的大小远小于另外两种算法。

图3 不同传输半径比率下连通控制集的大小比较Fig.3 Comparison of connected dominating set size under different transmission radius ratios

5.3 算法运行时间比较

图4 给出了在结点传输半径比率为1.5、1.75 和2的情况下，网络规模变化对3 种算法运行时间的影响，表1 给出了具体数据。由图4 和表1 可以看出，对于任意的传输半径比率，随着网络规模的增加，3 种算法的运行时间也相应增加，这是因为在一个固定的区域中，随着网络规模的增加，需要更多的时间来处理一个更大的数据集。另外，对于每一个传输半径比率，在任意网络规模下，ZREA22 算法的运行时间均小于WFSK09 和SHLO14 算法，这是因为ZREA22 算法基于原连通控制集重构新的连通控制集，导致其在寻找极大独立集时所需的搜寻空间变小，所以这一过程所需的时间也会减少。同时，根据算法1，在极大独立集中添加结点以形成连通控制集时，只需迭代地选择一条最短路径，这意味着ZREA22 算法需要相对较少的时间实现连通。然而，WFSK09 算法不但需要构造一个连通控制集，而且需要采用贪婪策略不断地添加结点到所获得的连通控制集中，使其成为2 连通，这就意味着它需要相对较多的时间开销。与WFSK09 算法相比，SHLO14 算法通过势函数计算所有结点的势函数值，并将其中具有最大势函数值的结点加入原连通控制集中，该过程被执行多轮直到所得到的结果是一个(1,2)-CDS，随后使用类似的方法把最大势函数值的结点加入所获得的(1,2)-CDS 中，直至扩充成一个(2,2)-CDS。由于势函数的计算是非常复杂的且每次迭代中均需要计算所有非连通控制集中结点的势函数值，因此SHLO14 比WFSK09 算法需要更多的时间开销。

表1 不同传输半径比率下的算法运行时间结果 Table 1 Results of algorithm running time under different transmission radius ratios

图4 不同传输半径比率下算法运行时间比较Fig.4 Comparison of algorithm running time under different transmission radius ratios

6 结束语

本文主要研究存在故障通信链路的异质无线传感器网络的虚拟骨干重构问题，这一问题可以抽象为双向链路圆盘图G=(V,E)的连通控制集的重构问题。针对给定的双向链路圆盘图G=(V,E)及其连通控制集和相应的故障边集，设计一个连通控制集重构算法。首先计算没有被原连通控制集控制的点组成的集合W，然后计算W的生成子图的极大独立集，最后对该极大独立集中的每个顶点，寻找一条最短路径将它与原连通控制集中的点连接起来，并将这些最短路径中的点加入原连通控制集中形成一个新的连通控制集。该算法可以产生一个新的连通控制集，大小的上界为3α∙Sopt+3(γ+m)。仿真实验结果表明，相比于已有的容错虚拟骨干构建算法，所提算法在虚拟骨干的大小和运行时间上更具优势。下一步将研究存在结点和链路混合故障的异质无线传感器网络虚拟骨干重构问题。