基于转发节点集的连通支配集分布式算法
唐勇，张军，汪文勇，向渝，张骏，杨挺*
基金项目：教育部博士点基金新教师项目(200806141110)
作者简介：唐勇，（1973-），男，工学博士，电子科技大学副教授。主要研究方向为无线传感器网络、网
络管理. E-mail: worldgulit@uestc.edu.cn
（电子科技大学计算机科学与工程学院，成都 611731）
5 摘要：在无线传感器网络中，构造一个虚拟骨干网是优化网络性能的重要手段。虚拟骨干网
的构造在数学上等同于求图的最小连通支配集，最小连通支配集的求取问题已经被证明是
NP 完全问题，因此采用启发式的方法求取一个最优解。本文提出了FWCDS 算法(A Forward set
Based CDS Distributed Construction Algorithm)，仅利用了1-hop 的邻节点信息，在每
个节点上分布式的构造一个转发集，然后采用一个广播染色算法，从这些转发集中选择一部
10 分节点作为支配节点，构造一个连通支配集。FWCDS 算法改进了OHDC 算法[9]。仿真结果表
明，FWCDS 算法有约等于支配节点数的额外消息数，同时有约等于网络直径的收敛时间，而
且得到了一个较小的CDS。
关键词：无线传感器网络；连通支配集；分布式算法
 0 引言
在无基础设施的无线传感器网络中，高效快速的构造一个虚拟骨干网无疑是非常有意义
35 的[1-3]。在任意图中求解最小连通支配集是NP 难[4]问题，因此常采用启发式算法近似求解，
其主要方法有集中式[5]和分布式[6]两种。采用集中式方法虽然能够得到较小的连通支配集，
但求解前需要知道整个图的拓扑信息，这对于动态性强的无线传感器网络并不适用，因此，
一般应采用分布式方法。在过去的几年中，许多机构和研究组织已经着手这一方面的研究，
并且出现了一些喜人的研究成果，其中几个经典的算法有Dai’s 算法[7]，MISB 算法[8]以及
40 OHDC 算法[9]。本章在OHDC 算法的基础上，提出了一个简化的算法，称为FWCDS （A
Forward set Based CDS Distributed Construction Algorithm）算法。同OHDC 算法相似，FWCDS
算法仍然采用区域覆盖的思想，但与OHDC 算法不同，FWCDS 算法仅仅判断哪些节点在
1-hop 邻居所覆盖区域的边缘，然后直接确定这些边缘节点为转发节点。FWCDS 算法思想
 简单，易于实现，并且改进了CDS 尺寸。算法分析与仿真结果表明，算法完成了设计的目
45 标：良好的CDS 尺寸，极少的通信量以及快速的收敛时间。
1 问题描述
1.1 网络模型
本算法采用Unit-disk 图无线传感器网络模型。在Unit-disk 模型中，若网络拓扑图表示
为G=(V,E)，则图的顶点集V 表示网络的传感器节点集合，图的边集E 表示网络的通信
50 链路集合。若∃u,v∈V ，且uv ∈ E ，则称节点u，v 之间有一条通信链路，节点u 和v 可
以互相通信。此时u 和v 的直线距离小于等于R。假定算法在理想的网络环境中执行，即所
有传感器节点同质同材，配有全向天线。每个节点具有相同的计算和通信性能，以及相同的
通信半径。通信过程无信道干扰，障碍物遮挡，忽略无线信道延迟。
1.2 问题提出及分析
55 在无向Unit-disk 图G=(V,E) 中， 对于节点v ∈ V ， 若v 的邻居节点集
1 2 [ ] { , , ,..., |n } n v N v = v u u u ≤Δ ，则以节点v，u1，…，un 为圆心，以R 为半径的圆形成的圆
形区域相互交叠， 并形成了一个新的区域
[ ]
( [ ]) ( )
u N v
A N v A u
∈
= U 。若[ ] k ∃u ∈Nv ，
( [ ] { }) ( [ ]) k A N v − u =A N v ，则说明节点v 的邻居节点k u 位于区域A(N[v])内。若集合
( ) { | [ ], 1,2,..., 1} ki ki v E v = u u ∈N v i= Δ + 是位于区域A(N[v])内的全部节点的集合，令
60 B(v)=N[v]−E(v)，则B(v)是位于A(N[v])区域上的节点的集合。A(B(v))=A(N[v])。图1 说
明了以节点v 和v 的8 个边缘邻居节点构成的区域覆盖， 1 2 3 4 5 6 7 8 B(v)={v,v ,v ,v ,v ,v ,v ,v}。
图1 节点v 及其N(v)覆盖的一个区域
Fig. 1 v with an area covered by v
65
令{ |1 | |} i V= v ≤i≤V ，若求得了B(vi)，则
| |
1
( ) ( ( ))
V
i
i
A V A B v
=
= U ，因此，节点V 中所
有节点在R 的通信半径下所覆盖的区域面积，等于节点V 中的所有节点的B(vi)所覆盖面积
的并。所以，在传感器网络中，若在源节点s 开始广播数据包，B(vi)中的节点参与转发数据
包，所有节点都可以收到数据包。于是，网络的虚拟骨干节点可以由B(vi)中的节点担任。
引理1：在图G=(V,E)中，
| |
1
( ) ( ( ))
V
i
i
A V A B v
=
70 = U 。
 证明： 因为A(B(vi))= A(N[vi]), 而
1
( [ ]) ( )( [ ])
vi
i ij i
j
ij A N v A u u N v
=
Δ
=U ∈ 。于是，
1
| |
( ( )) i
i
V
A B v
= U
=
1
| |
( [ ])
V
i
i
A N v
= U
=
|
1 1
|
( )
V vi
ij
i j
A u
=
Δ
= U
U =
| |
1
( )
V
i
i
A v
= U
，又因为
| |
1
( ) ( )
V
i
i
A V A v
=
= U ，所以，
| |
1
( ) ( ( ))
V
i
i
A V A B v
=
= U 。命题得证。
引理2：B(v)是由位于区域A(N[v])边界上的圆的圆心构成的集合。
75 证明：因为A(B(v))= A(N[v])，若删去在区域A(N[v])内的节点，如果区域A(N[v])没有空
洞，则可以证明B(v)是由位于区域A(N[v])边界上的圆的圆心构成的集合。
假设点e 是空洞中的一点，连接点e 与点v，则必然存在圆C(v′)与线段ve 或ve 的延
长线交于a 点，因为线段vv′ 的长度D(v,v′) ≤ R，即点v 在圆C(v′)内（上）,又因为点a
在C(v′)上，所以线段va 在圆C(v′)内，因此，va 上的任一点都在圆C(v′)内（上）。又因
80 为点e 在线段va 上，所以点e 也在C(v′)内，因此点e 不在空洞内，因此不存在这样的空洞，
这与假设矛盾，所以假设不成立，即删去区域A(N[v])内的节点，不会形成空洞，因此，原
命题得证。证毕。
本文基于以上所述的思路，把算法过程分为两个阶段，第一阶段在全网内的每个节点
v∈V，求取v 的转发集B(v)。第二阶段从B(v)中选取一部分节点做为骨干节点，放入CDS
85 中，算法过程在每个节点实施后，既可以算出整个网络的CDS，求得网络的虚拟骨干网。
为了描述方便，算法分为主算法和次算法。主算法完成第一阶段的工作，次算法完成第
二阶段的工作。主算法采用覆盖的思路，将节点的1-hop 邻居节点集合的区域边界上的节点
放入集合B(v)，构成节点的转发集，主算法分布式的在每个节点独立运行。次算法使用颜色
标记法，从源节点s 开始广播特殊的数据包，将收到数据包和尚未收到数据包的节点标记为
90 灰色和白色，将被确定为骨干节点的节点标记为黑色，算法逐步的从节点的转发集中选择出
被标记为黑色的节点。经过主次算法，成功求得图G 的CDS，实现虚拟骨干网的构造。
2 算法描述
2.1 FWCDS 主算法
问题：节点v∈V，求节点v 的转发集B(v)。
在图G=(V,E)中，对于任意节点v∈V，令1 2 ( )={ , ,..., |n≤ ( )} n 95 N v u u u K v 。根据引
理2，算法采用覆盖的思想，初始时，令B(v) = ∅ ，从节点v 开始，首先从v 邻居节点集
N(v)中选取节点u1，比较u1 的通信范围所形成的圆形区域A(u1)与区域A(N[v])的关系，若
A(u1)在区域A(N[v])上，则将节点u1 放入集合B(v)中， 1 B(v) ={u}。同理，从N(v)中选取节
点2 3 , ..., n u u u ，比较A(ui)(2 ≤ i ≤ n)是否在区域A(N[v])内，若在A(N[v])上，则将节点ui 放入
100 B(v)，当遍历完整个集合N(v)后，即可计算出节点v 的转发集B(v)。
 图2 包含3 个节点的区域覆盖过程
Fig. 2 Coverage process with 3 nodes
若令n=3，则有N[v]={v,u1,105 u2,u3}，如图2 所示。首先从N[v]中取出节点v，因为
N[v] − {v} = {u1,u2,u3}，A(N[v]) − {v}) ≠ A(N[v])，图中阴影区域表示A(N[v])，因此，节点v
加入集合B(v)中。同理，节点u1， u2 也被加入集合B(v) 中。对于节点u3，因为
N[v] − {u3} = {v,u1,u2}，A({v,u1,u2}) =A(N[v])，所以节点u3 不在集合B(v)中，经过选举，最终
B(v) = {v,u1,u2}，于是得到节点v 的转发集B(v)。
110 从以上思路可以看出，若节点v 广播数据包Pa，节点v 的转发集中的节点再转发此数
据包，那么节点v 的任何两跳以内的邻居都能收到数据包Pa，因此，不难看出，若节点v
作为sink 节点，B(v)中的节点作为骨干节点，此算法在N[v]上是最优解。这也是本文采用此
方法计算连通支配集的原因。
引理3：节点u∈N[v]，且N[v] − {u} ≠ ∅ ，若u∈B(v)，则必然∃ u′ ∈N[v]，C(u)与C(u′ )
115 的交点至少有一个位于区域A(N[v])的边界上。
证明：因为u∈B(v)，因此A(u)在区域A(N[v])上，若N[v] − u ≠ ∅ ，则必然存在圆C(u)
的一段弧位于A(N[v])的边界上。所以，必然∃ u′ ∈N[v]，C(u′ )截取圆C(u)位于边界上的一
段弧，因此，C(u)与C(u′ )至少有一个交点位于A(N[v])的边界上。证毕。
引理4：在引理3 的条件下，若C(u′ )与C(u)相交于点a，且N[v]中仅有以u′ 和u 为圆
120 心，R 为通信半径的圆交于点a，则u′ 位于区域A(N[v])上。
证明：因为a 在区域A(N[v])的边界上，因此，若a 仅是u′ 和u 的交点，则必然有圆C(u′ )
的一段弧在区域A(N[v])的边界上，所以，u′ 位于区域A(N[v])上。证毕。
引理5：在引理3 的条件下，若∃ 1 2 , ,..., k u u u ∈N[v]，圆C(u1)，C(u2)，…，C(uk)与C(u)
交于同一点a，则仅能推出距离u 最远的节点(1 ) iu ≤i≤k在区域A(N[v])上。
125 证明：反证法。假设ui 是距离u 最远的节点，存在节点uj ≠ ui，uj 在区域A(N[v])上。因
为点a 是A(N[v])边界上弧的交点。因此，与点a 相连的弧仅有两段在A(N[v])的边界上，又
因为圆C(u)的一段弧在A(N[v])的边界上，因此，在节点1 2 , ,..., k u u u 中，仅能确定存在一个
节点在区域A(N[v])上。
根据假设，因为uj 在区域A(N[v])上，所以ui 不在区域A(N[v])上，又因为C(ui)与C(uj)
130 交于点a，所以，A(uj)必然覆盖了A(ui)的一部分。因此，节点uj 距离节点u 比节点ui 距离
学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表