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

The construction of d-robust strongly connected dominating and absorbent set in heterogeneous wireless sensor network

无线传感器网络的一个虚拟骨干是由该网络中承担相关路由任务的结点组成的一个子网。一个异质无线传感器网络通常被建模成一个圆盘图(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)分别表示异质无线传感器网络中结点传输范围的最小值与最大值。

The virtual backbone(VB)of a wireless network is a subnetwork which consists of the nodes in the network undertaking the relevant routing tasks.A heterogeneous wireless sensor network is usually modeled as a disk graph(DG).Correspondingly,its virtual backbone is modeled as a strongly connected dominating and absorbent set(SCDAS)of the disk graph.The problem of constructing VBs for heterogeneous wireless sensor networks is equivalent to the problem of computing SCDASs for the corresponding DGs.Aiming at constructing VBs on heterogeneous wireless sensor networks under the interferences,the paper proposes the concept of d-robust strongly connected dominating and absorbent set for disk graphs,and designs an approximation algorithm d-SCDAS-C for the minimum SCDAS problem in DGs.The performance ratio of the algorithm is proved to be 4(ak^(2)+ak+1),where a=4/(1-d)^(2),k=r_(max)/r_(min).r_(min) and r_(max) represent the minimum value and the maximum value of the transmission range of nodes in the network,respectively.