Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs

The connected dominating set （CDS） problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs （UDGs）. This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set （IS） in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.

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

无线传感器网络的虚拟骨干是承担网络路由任务的结点组成的子集。当一个异质无线传感器网络故障时,原有的虚拟骨干可能就会失去部分功能,然而现有的容错虚拟骨干只能容纳顶点故障,无法解决只有链路故障但没有顶点故障的问题,且虚拟骨干大小会随故障顶点数量的增加呈超线性增加。针对上述问题,研究在异质无线传感器网络链路发生故障时的虚拟骨干重构问题。对于一个只有链路故障的异质无线传感器网络,设计一个虚拟骨干重构近似算法(ZREA22),寻找一个未被控制的点组成的集合,在该集合导出的子图中构造一个极大独立集,并向该极大独立集和原连通控制集中添加结点以形成一个重构的连通控制集。实验结果表明,ZREA22算法能够产生一个大小有界的连通控制集,且虚拟骨干大小相比于WFSK09和SHLO14算法至少减少了9%和31%,同时算法运行时间更短。

基于GSO算法的最小连通支配集问题求解

经典的最小连通支配集(MCDS)计算是NP难问题。为此,提出一种利用萤火虫优化算法求解该难题的新方法。把网络中的每个节点当作一个萤火虫个体,以节点度为基础构成荧光素,通过概率选择和荧光素调节机制,使个体被吸引向邻接的高亮度个体,从而由所选出的个体组成网络的支配集。经连接和修剪处理后,得到MCDS的近似解。在无线传感器网络模型的单位圆盘图上进行模拟实验,结果表明,该算法得到的连通支配集规模较小,更接近集中式算法的结果。

求解最小连通r-跳k-支配集的启发式算法

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定。

两跳支配集的高效近似算法

提出一种求解连通图2-hop支配集(2-DS)的贪心算法.首先将图中每个节点和其两跳邻居节点连接,然后在此基础上求图的2-hop支配集,最后采用修剪规则剔除支配集中的冗余节点.由于支配点支配2-hop内的邻居节点,从而构造出较小的支配集.仿真结果表明,新算法优于其他已有算法.

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。

一种高效的最小连通支配集贪心算法

连通支配集(CDS)在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法(GCDS),依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。

异质无线传感器网络中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)分别表示异质无线传感器网络中结点传输范围的最小值与最大值。