单向链路无线传感器网络的强连通多跳控制集

强连通控制集常被用来代表具有不同传输范围的无线传感器网络的虚拟骨干,较小的虚拟骨干更能高效地进行数据收集和节约无线网络的能量。为了计算强连通控制集,提出了一种新的多跳宽度优先搜索树强连通控制集算法(d-hop BFS_SCDS)。该算法首先使用贪婪策略找到一个多跳控制集(d-DS),然后利用宽度优先搜索树连接d-DS中的节点形成一个强连通多跳控制集。该算法的近似比为(2.4d 2+3.6d+1.2)(dk+1/2)2,其中k是网络的传输范围比。仿真实验表明该算法是有效的,符合预期的结果。

异质无线传感器网络中d-鲁棒强连通控制吸收集的构造

无线传感器网络的一个虚拟骨干是由该网络中承担相关路由任务的结点组成的一个子网。一个异质无线传感器网络通常被建模成一个圆盘图(DG),相应地,其虚拟骨干被建模成该圆盘图的一个强连通控制吸收集(SCDAS)。构建异质无线传感器网络的虚拟骨干问题就等价于相应圆盘图的强连通控制吸收集的计算问题。针对受干扰的异质无线传感器网络虚拟骨干的构建问题,提出了圆盘图的d-鲁棒强连通控制吸收集(d-robust SCDAS)的概念,设计了一个近似算法d-SCDAS-C计算最小d-鲁棒强连通控制吸收集,并证明了该算法的近似比为4(ak^(2)+ak+1),a=4/(1-d)^(2),k=r_(max)/r_(min)。r_(min),r_(max)分别表示异质无线传感器网络中结点传输范围的最小值与最大值。

连通、几乎局部连通拟无爪图是完全圈可扩的

G是一个图 ,B(G)表示G中所有局部不连通的点构成的集合 .如果B(G)是独立集 ,并且对任意v∈B(G) , u∈V(G) ,使G[N(v)∪ {u}]连通 ,则称G是几乎局部连通的 .如果G中所有爪心构成的集合D(G)是独立集 ,并且对任意v∈D(G) ,G[N(v) ]是强 2 -控制的 ,则称G是拟无爪图 .本文证明 :连通、几乎局部连通的拟无爪图是完全圈可扩的 .