基于网络分层的连通支配集算法

基于网络分层的连通支配集算法 唐勇，张军，汪文勇，向渝，张骏，杨挺 (电子科技大学计算机科学与学院，成都 611731) 摘要:在无线传感器网络中，构造一个虚拟骨干网是优化网络性能的重要手段。虚拟骨干网 5 的构造在数学上等同于求图的最小连通支配集，最小连通支配集的求取问已经被证明是 NP 完全问题，因此采用启发式的方法求取一个最优解。本文提出了 LCDS 算法(A Layer Based CDS Construction Algorithm)，首先选取一个源节点(sink 或簇头节点)，然后以此节点 将网络按跳数划分成若干层。分层完成后，各层分布式的计算本层的支配节点集，所有层的 支配节点集的并即为网络的连通支配集。LCDS 算法的时间复杂度为 ，其中 示节点的平 10 均度。仿真结果表明，LCDS 算法获得了一个比 MTCDS[6]和 MISB[10]等算法小的 CDS，并且 随着网络密度快速增加，LCDS 算法获得的 CDS 尺寸增加很小，在密度很大的无线传感器网 络中，LCDS 算法仍然能得到一个较小的 CDS。 关键词:无线传感器网络;连通支配集;分层 中图分类号:TP393 15 A Layer Based CDS Construction Alogrithm Tang Yong, Zhang Jun, Wang Wenyong, Xiang yu, Zhang Jun, Yang Ting (School of Computing Science and Engineering,University of Electronic Science and Technology of China, ChengDu 611731) 20 Abstract: In Wireless Sensor Networks, Virtual Backbone is an important method to optimize network performance. In mathematics，the construction of Virtual Backbone equivalent to seeking the Minimum Connected Dominating Set(MCDS) which has been to proved to be NP-complete problem. A heuristic approach is an approximate solution. This paper presents LCDS algorithm (A Layer Based CDS Construction Algorithm) proposes a layer model. First, this algorithm selects 25 a source node (sink or cluster head), then it starts a broadcast from this node to divide networks into several layers according to hops. After layer is divided, each layer performing CDS construction algorithm computes dominating set separately, and the union of dominating set of all layers acts CDS of networks. The time complexity of LCDS is where represent average degree of nodes. Simulation results show that, LCDS algorithm gets a smaller CDS than other 30 algorithms which include MTCDS[6] and MISB[10] algorithm and with the rapid increase of network density, the increase of CDS is very slow. When nodes of WSN have a very large density, LCDS algorithm is still able to get a smaller CDS. Keywords: wireless sensor networks; CDS; Layer 35 0 引言 在无基础设施的无线传感器网络中，高效快速的构造一个虚拟骨干网无疑是非常有意义 [1-3] 的。在任意图中求解最小连通支配集是 NP 难[4]问题，因此常采用启发式算法近似求解， 其主要方法有集中式[5]和分布式[6]两种。采用集中式方法虽然能够得到较小的连通支配集， 但求解前需要知道整个图的拓扑信息，这对于动态性强的无线传感器网络并不适用，因此， 40 一般应采用分布式方法。连通支配集的构造作为著名的 NP 难问题，至今仍然无法证明存在 多项式时间内的求解算法。为了提高无线传感器网络的性能，有必要构造一个以连通支配集 表示的虚拟骨干网。因此，人们不断的探索各种方法来构造尽可能小的连通支配集，以接近 最优求解算法。MTCDS 算法[6]及其改进算法[7][8]提出了在每个节点设置反向定时器，从中心 基金项目:教育部博士点基金新教师项目(200806141110) 作者简介:唐勇，(1973-)，男，工学博士，电子科技大学副教授。主要研究方向为无线传感器网络、网 络管理. E-mail: worldgulit@uestc.edu.cn -1- 到边缘的广播扩散构造连通支配集的方法，但由于使用反向定时器的原因，算法的延迟太大， 45 对具有一定动态性的无线传感器网络并不适用。本文提出了一种分层 CDS 构造算法，将网 络从一个源(中心)节点按照不同的跳数划分成不同的层。网络的各层分布式的求取支配集， 所有层支配集的并即构成了网络的 CDS。仿真结果表明本算法在 CDS 大小上优于其它几个 算法。 1 问题描述 50 本文提出了一个网络分层模型，分层模型将网络划分成 n 层，每一层是一个闭合的环型 区域。如图 1 所示，以 s 为源节点的分层模型，图中箭头连接的节点形成了网络的虚拟骨干， 实际的分层边界是由圆弧相连的一条闭合曲线。 网络中的所有节点分布在各层中，每层选出若干骨干节点，作为转发节点。网络中的节 点转发数据包基于以下规则: 55 (a) 对于转发节点，当接收到节点广播来的数据包时，转发并仅转发一次。 (b) 对于非转发节点，当接收到转发节点广播来的数据时，不再转发。 s s 图 1 网络的分层 Fig. 1 Layers of WSN 60 若以 s 节点为源节点，广播数据包 P，则第 1 层的骨干节点必然转发此数据包 P 一次， 以此类推，若第 i 层的骨干节点广播数据包，则第 i+1 层必然收到数据包。所以，当网络中 选定一个源节点 s 后，从 s 开始广播数据包，则网络中的每个节点可以收到。源节点 s 可以 尽量选择靠近网络中心的节点，也可以选择 sink 节点。 65 基于以上的分层思路，本文提出一个基于分层的连通支配集构造算法，简称 LCDS (A Layer Based CDS Construction Algorithm)算法。LCDS 算法在每层选举骨干节点，所有层的 节点即构成了网络的骨干节点集。 2 网络分层模型与算法描述 2.1 网络分层模型 70 网络采用 Unit-disk 模型。网络中所有节点同质同材，配有全向天线。每个节点具有相 同的计算和通信能力，以及相同的通信半径。 在图 G , (V , E) 中，v V，若网络被划分成 n+1 层，则第 i 层用 Ni (v) 表示，其中 和 第 i=0,1,2,…,n 。 网 络 的 第 i i+1 层 满 足 关 系 N ( Ni (v)) = Ni，1 (v) n 75 = (v) ，其中 Ni (v) ={u1,u2,…,un}。 i 1 i i U N (u ) N (v ) N i ,1 -2- 引理 1:第 i 层节点的邻居仅在 i-1，i 或 i+1 层。 证明:首先证明第 i 层节点的邻居在第 i-1，i 或 i+1 层。 因为第 i 层的节点是第 i-1 层节点的邻居，因此，第 i-1 层节点是第 i 层的邻居。同理， 第 i+1 层节点是第 i 层节点的邻居。得证。 80 再次证明第 i 层节点的邻居仅在第 i-1，i 或 i+1 层。 Ni k (v) ，其中 k<1，节点 u 是 i 层节点的邻居。那 利用反证法，假设存在节点 u 属于 么必然存在 u, Ni (v) ，使得 u, N (u) 。因此，根据分层模型，有 u, Ni k ，1 (v)，而 k , 1， 所以 u, 不在第 i 层，这与题设矛盾，所以假设不成立，当 k , 1时， Ni k (v) 层不会有第 i 层节点的邻居。同理可证 k , 1 时, Ni k (v) 层不会有第 i 层节点的邻居，因此，原命题得 证。证毕。 85 网络分层的方法很多，本文提供一个基于标记的分层算法。每个节点在广播或转发分层 信标时，标记自己的层号。分层信标可以被认为是带有分层标记的 beacon 帧。规则如下: (a) 选定源节点 s V ，标记 ff=0，将 ff=0 放入分层信标 P 中，s 广播 P。 (b) 收到分层信标的节点标记自己为 ff+1，并将 ff+1 放入 P，广播分层信标 P。 90 此规则需要同步信标的发送时间。假定信道被划分成 n 个时隙，则规定在 n (k是一个正整数) 个时隙完成一次信标帧的广播。第(b)条规则需要递归调用，网络的分 k 层标记如图 2 所示。 图 2 网络的分层信标示意图 Fig. 2 Beacons for Layering 95 用 Bi (v) 表 示 第 i 层 被选 出 来 的骨 干 节 点 集合 ， 则第 0 层 有 一 个骨 干 节 点， B0 (v) N0 (v) , {v}。第 1 层的骨干节点为 B1 (v) N1 (v) ，第 i 层为 Bi (v) Ni (v) 。 n CDS , U Bi (v) 。因此，要解决的问题就是在每层中选取骨干节点。 i,0 2.2 算法描述 100 骨干节点的选取基于如下的贪心规则: (a)从 N(v)中选择覆盖了 N 2 (v) 中尚未被覆盖的节点最多的节点作为本层的骨干节点。 在 图 G , (V , E) 中 ， 选 定 s V 为 网 络 的 源 节 点 ， 第 i 层 的 节 点 表 示 为 Ni (v) , {uij | i , 0,1,..., n; j , 1, 2,...,| Ni (v) |} ，若第 i 层中已经选取了 ui1 ，ui 2 ，…，uik 为 骨 干 节 点 ， 其 中 k ,| Ni (v) | ， 那 么 选 取 uik ，1 为 骨 干 节 点 ， 则 需 满 足 105 -3- k k (v) N }) , max( N (u ) N (v) N ik ，1 ) Ni i 1 (v) U{uij ik ，l i i 1 (v) U{uij }) ，其 max( N (uj ,1 j ,1 k 中 l {1, 2,....,| Ni (v) |}。经过多轮选举后，当集合 N (uik ，1 ) Ni (v) Ni 1 (v) ij U{u }为空 j ,1 集时，即完成了本层的选举，所有被选举出来的节点即为本层的骨干节点集。 定义 1:若节点 v 广播数据包 Pa 后，u N(v)收到 Pa 后转发数据包 Pa，则 v 收到的 Pa 110 称为节点 v 的转发 Pa。 图 3 节点转发 Pa Fig. 3 Node forwarding Pa 图 3 给出了定义 1 的示例图，节点 a 广播数据包 Pa，节点 b 收到后广播数据包 Pa，节 115 点 a 收到 pa，由于这个 pa 是节点 b 收到节点 a 的数据包 Pa 后而发送的，因此，节点 a 收 到的 pa 称为节点 a 的转发 pa。据此，有一点可以肯定，即除了源节点外，所有的节点广播 数据包 Pa 都有一个先决条件:节点必须收到一个 Pa。 n n 定义 2:若 Ni (v) , UU j ，IU j , ，其中 n= | Ni (v) | ，若不存在节点 x Ni ，1 (v) ， j,1 j ,1 x N (U k ) 且满足 x N (U l ) ，其中 k , l 。令U k , {u1, u2 ,..., un} ，若 u j U k ，至少存 120 和在 u u, ，使得 w N (u) ， N (u j ) 且 w N (u,) ， N (u j ) ，其中 w Ni，1 (v) ，则称U k 是 基于 i+1 层的独立集。表示为 I i，1,i (v) , {uk1 , uk 2 ,..., ukn}。 图 4 独立集示意图 Fig. 4 Independent set 125 图 4 给出了定义 2 的一个示例，(1)，(2)中第二层三个节点互不相邻，且三个节点不能 通过第三层的一个节点连通，(2)中需要 2 个第三层节点才能连通两个第二层节点，因此(1)， (2)均为三个独立集。(3)由于存在一个 4 节点可以通过第三层节点相连通的独立集，因此有 两个独立集。 130 LCDS 算法首先需要选定源节点 s(默认为 sink 节点或簇头节点)，并应用分层规则对 网络分层。当网络被划分成若干层后，支配节点集求取算法分布式的在各层运行，计算出本 层的支配节点集，第 i 层支配节点集的计算步骤如下: 第 i 层支配节点求取算法: (1) 第 i 层的非骨干节点广播数据包 Pa。 135 (2) 第 i+1 层的节点收到 Pa 后，若发现 Pa 来自第 i 层，且自己不属于支配节点的邻居， 则广播 Pa。 -4- (3) 第 i 层的节点收到 Pa 后，若发现是来自第 i+1 层的，且是自己的转发 Pa，则此节 点计数接收到的 pa 个数。 140 (4) 若节点未收到非自己的转发 Pa，则确定自己为骨干节点。 I i，1,i (v) 中，收到 Pa 个数最多且不为 0 的节点，确定自己为骨干节点，转入第 1 (5) 在 步。 (6) 结束。 算法的第 5 步需要以下规则保证: (a)若第 i 层有几个节点收到的 Pa 个数相同，则选择最小 ID 的节点为骨干节点。 145 算法的第 5 步需要从第 i 层的一个或多个独立节点集中选择节点，每个独立集互不影响， 单独完成骨干节点的求取。求取需要比较独立集中的节点收到 Pa 的个数，这需要借助于集 合 Ni，1 (v) 中的节点作为路由节点来通信。最终每个独立集选取完自己的骨干节点，则所有 独立集的骨干节点的并即为本层的骨干节点集。如图 5 所示，节点 1 为源节点，节点 2,12,18 为第 1 层骨干节点，节点 9,15 为第 2 层骨干节点。 150 图 5 不同层次中的骨干节点 Fig. 5 Backbone nodes in different layers 以上算法基于广播，并且假定在理想的通信环境下进行。算法在每层运行，每层分别计 155 算出本层的骨干节点。第 0 层仅有源节点 s，因此 s 即为骨干节点。算法的执行如图 6 所示。 A 为初始状态。B 是第 0 层节点开始算法。C 是在第 0 层节点已确定骨干节点后，第 1 层节 点开始求取算法。D 是在第 1 层节点已确定骨干节点后，第 2 层节点开始求取。E-1 和 E-2 是第 3 层可能的两种结果集。 -5- 1 1 2 2 1 1 2 2 1 1 2 2 160 图 6 每层骨干节点的求取 Fig. 6 Selecting backbone nodes in each layer 当网络上的所有层都选举出了支配节点后，所有层的支配节点集的并集即为网络的连通 支配集。连通支配集构成了网络的虚拟骨干网。 165 3 算法 3.1 正确性证明 令 CDS (i) 表示 i 层的骨干节点集合，根据本算法，CDS (i) 完全覆盖 Ni，1(v) 中的节点， 即对于任何 CDS (i ， 1) ，都 u CDS (i) ，使得 uv E ，其中 E 图 G 中的边集。因此，每 个 i+1 层的骨干节点，都至少存在一个第 i 层的骨干节点与它相连，即 CDS 是连通的。又因 170 为第 i 层骨干节点完全覆盖了第 i+1 层的节点，所以 CDS 是图 G 的支配集。 综上所述，本算法计算出的 CDS 是连通支配集。 3.2 性能及复杂度分析 本算法由网络分层和各层选举骨干节点两个阶段构成，第一阶段是第二阶段的基础，没 有分层，本算法就无法进行;当完成网络分层后，第二阶段的每一层的计算不依赖于其他层， 175 本层的计算也不会影响其他层。因此，从局部来看，本算法是基于层的分布式算法。若从全 局来看，因为层的划分是以节点 s 为源节点，所以，本算法是源依赖的。当然，若源节点 s 的选择按照某种具体的规则，则对于任何节点来说，本算法不依赖于源，这可以作为进一步 的研究工作。 n 令 L 为网络的分层数，每个节点在 (k是一个正整数) 的时间内完成有效通信任务， 180 k 则分层所用的时间TL 为: n TL , (L ， 1) k 公式(1) 若节点的平均度为 , ，则第 i 层的平均节点数为: La(0) , 1 -6- La(1) , , 公式(2) 185 La(i) , (, 1)La(i 1) 公式(3) 展开公式(3)， La(i) , (, 1) 2 , La(i 2) , La(1) , (, 1)i 1 带入公式(2)后有: La(i) , ,(, 1)i 1 190 公式(4) 若网络的节点数为 N，则: i N , La( j) i,0 带入公式(4)式: N , 1， , ， ,(, 1) ， ... ， ,(, 1)i 1 (, 1)i 1 , 1 ， , 195 , 2 N 1 ) 。 因此， i , log , 1 ( N 2 , , N 1 , 公式(5) L , ,log , 1 ( N 2 ), , , , 将公式(5)带入公式(1)，得到网络的分层所用时间为: n , N 1 , TL , (,log , 1 ( N 2 ), ， 1) k , , , 200 令网络的计算时间为TT ，第 i 层的计算时间为TLi ，则有 公式(6) TT , max(TL 0 ,TL1,..., TLi ,...,TLL ) 2n kLa(i) 设骨干节点选举的每轮需要耗费 个时间来选 个时间用来计数 Pa，需要耗费 k n 举最大计数的 Pa 节点，则第 i 层选举完所有骨干节点所需的时间为: 2n ， nLa(i) TLi , La(i) k 205 因此，TLi 是随自变量 i 增加的函数，于是有 n( N , 2 N ， 3)2 1 TT , TLL , k 因此，算法实施所需要的总的时间为: 2 1 n( N , 2N ， 3)n , N 1 , T , TL ， TT , (,log , 1 ( N 2 ), ， 1) ， k k , , , T , , 2 210 本算法的时间复杂度为 O(, 2 ) 。 -7- 4 仿真与结果分析 [7]， 为测试 LCDS 算法的性能，仿真比较了 LCDS 算法与 MTCDS 算法[6]，MI-CDS 算法 Wan’s 算法[9]以及 MISB 算法[10]求得的 CDS 大小。 网络拓扑随机产生在100m ,100m 的正方形区域上，节点的位置服从均匀分布，如果 产生的网络不是连通的，则重新产生直到整个网络连通为止。按照不同的网络密度，安排两 215 个实验如下: 实验 1:网络中的每个节点带有相同的通信半径 25m，实验随机产生 100 个不同的网络 拓扑。网络的节点数分别从 20 个到 100 个，间隔为 10 个，从 100 到 1000 个，间隔为 100 个。实验结果为 100 个不同网络的平均值。 220 图 7 通信半径为 25m，节点数从 20 到 100 时，LCDS 算法与其他算法 CDS 大小的比较 Fig. 7 Compare CDS size of LCDS and other algorithms with 25m communication radius, nodes from 20 to 100 图 7 描述了节点数为 20 到 100 个(稀疏网络)时 LCDS 算法与其他几个算法 CDS 大小 的比较。从图中可以看出，几个曲线随着网络密度的增加，其趋势都是上升的，LCDS 与 225 MISB 算法表现良好并且优于其他几个算法，在节点数为 23 和 75 时，LCDS 和 MISB 算法 有几乎相同的 CDS 个数。Wan’s 算法 CDS 个数随着网络密度的增加而增加较快，MTCDS 算法和 MI-CDS 算法几乎具有相同的增长趋势，但 CDS 个数比 LCDS 和 MISB 算法稍多， LCDS 算法的 CDS 个数增长较为平稳，因此与其他几个算法相比，更能适应各种网络密度 下的连通支配集构造。 230 图 8 通信半径为 25m，节点数从 100 到 1000 时，LCDS 算法与其他算法 CDS 大小的比较 Fig. 8 Compare CDS size of LCDS and other algorithms with 25m communication radius, nodes from 100 to 1000 -8- 图 8 描述了网络密度比较大时的情况，节点数按 100 的间隔从 100 到 1000 个(稠密网 235 络)。从图中可以看出，当网络密度越来越大时，LCDS 算法的曲线逐渐趋于水平，MISB 算法的 CDS 个数不断增长，因此，LCDS 对于相同区域下网络密度的变化没有 MISB 敏感。 当在网络密度非常大时，LCDS 算法能表现的比 MISB 算法更好的性能。MTCDS 与 MI-CDS 算法的 CDS 尺寸始终有一致的增长幅度，当节点数为在 500 个左右时，MTCDS 与 MI-CDS 算法的曲线接近水平，因此在大密度网络环境中，这两个算法都有良好的性能。Wan’s 算法 240 的 CDS 尺寸增长较快，在节点为 1000 时接近 30 个，而 LCDS 算法的 CDS 仅有 23 个节点。 当网络非常稠密时，LCDS 算法的 CDS 个数略大于 MTCDS 算法，但优于其他几个算法。 实验 2:网络中的每个节点带有相同的通信半径 50m，实验随机产生 100 个不同的网络 拓扑。网络的节点数分别从 20 个到 100 个，间隔为 10 个，从 100 到 1000 个，间隔为 100 个。实验结果为 100 个不同网络的平均值。 245 图 9 通信半径为 50m，节点数从 20 到 100 时，LCDS 算法与其他算法 CDS 大小的比较 Fig. 9 Compare CDS size of LCDS and other algorithms with 50m communication radius, nodes from 20 to 100 图 9 给出了通信半径为 50m，节点数从 20 到 100 个时 LCDS 算法与其他算法在 CDS 大 250 小上的对比结果。LCDS 算法的曲线与 MISB 算法的曲线几乎一致，且都小于其他三个算法， Wan’s 算法的 CDS 相比较其他三个算法较大，MI-CDS 和 MTCDS 算法的 CDS 个数也非常 接近，但由于采用多个发起节点的原因，MI-CDS 算法 CDS 的个数要略多于 MTCDS 算法。 图 10 通信半径为 50m，节点数从 100 到 1000 时，LCDS 算法与其他算法 CDS 大小的比较 255 Fig. 10 Compare CDS size of LCDS and other algorithms with 50m communication radius, nodes from 100 to 1000 图 10 描述当节点数从 100 增加到 1000 时这几个算法的性能表现，LCDS 算法仍然有与 MISB 算法非常接近的 CDS 个数，但 LCDS 算法的 CDS 个数略少于 MISB 算法。随着网络 密度的增大，MTCDS 算法与 LCDS 算法的 CDS 个数趋于稳定，MISB 算法的 CDS 个数以 260 -9- 非常小幅度增加。从图中可以看出，LCDS 算法具有优于其他四个算法的 CDS 个数。 从实验 1 和实验 2 可以看出，对于均匀布点的无线传感器网络，LCDS 算法求得了一个 较为理想的连通支配集。且随着网络密度的增加，LCDS 算法求得的 CDS 个数增加较缓慢。 5 结束语 本文提出了一个基于分层划分的分布式连通支配集构造算法，该算法将网络从一个源 265 (中心)节点按照不同的跳数划分成不同的层。网络的各层分布式的求取支配集，所有层支配 集的并即构成了网络的 CDS。经过仿真实验，LCDS 算法具有很好的性能，无论在何种网络 密度下，算法构造的 CDS 都比较理想，而且随着网络密度的增加，算法求得的 CDS 个数趋 于平稳，这非常有利于虚拟骨干网性能的管理和控制。由于本算法的分层划分依赖于源节点 的选择，因此，对于移动网络，算法的运行成本会有所上升，但若选取 sink 节点作为源节 270 点，可以有效的避免这种情况出现。 [参考文献] (References) [1] B. Das, R. Sivakumar, V. Bharghavan. Routing in Ad Hoc Networks Using a Spine[A]. Proceedings of 6th International Conference on Computer Communications and Networks[C].Las Vegas: Institute of Electrical & 275 Electronics Enginee,1997.34-34. [2] B. Chen, K. Jamieson, H. Balakrishnan, et al. Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks[J]. Wireless Networks,2002,8(5):481-494. [3] B. An, S. Papavassiliou. A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks[J]. International Journal of Network Management,2001,11(6):387-395. 280 [4] MR Garey, DS Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco, CA: Freeman, 1979. [5] S. Guha, S. Khuller. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica,1998,20(4):374-387. [6] D. Zhou, MT Sun, TH Lai. A Timer-based Protocol for Connected Dominating Set Construction in IEEE 285 802.11 Wireless Networks[C]. Proceedings of 2005 Symposium on Applications and the Internet (SAINT '05)[A].2-8. [7] K. Sakai, F. Shen, KM Kim, et al. Multi-Initiator Connected Dominating Set for Mobile Ad Hoc Networks[J]. Proceedings of International Conference on Communications (ICC '08)[A]. 2008. [8] K. Sakai, MT Sun, WS Ku. Fast Connected Dominating Set Construction in Mobile Ad Hoc Networks[C]. 290 Proceedings of IEEE International Conference on Communications (ICC '09)[A]. 2009, 1-6. [9] PJ Wan, KM Alzoubi, O Frieder. Distributed Construction of Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks[J]. Mobile Networks and Applications, 2004, 9(2): 141-149. [10] 唐勇,周明天.基于极大独立集的最小连通支配集的分布式算法[J].电子学报,2007,37(5):868-874. 295 - 10 -