联合约束无线传感器网络连通支配集算法

Distributed Connected Dominating Set Algorithm with Combined Constraints in Wireless Sensor Network

  • 摘要: 针对无线传感器网络连通支配集构建问题,基于(α,β)-tree定义了具有传输时延约束的连通支配树CDTT问题,并提出CDT算法构建有限总功率消耗的CDT-tree,同时符合传输时延约束要求。给出的分布式CDS算法分为两个阶段执行,首先基于单位圆图构建MIS,然后在双权值无向图上使用MST和SPT实现CDT算法,同时满足联合约束要求,具有O(n2)的时间和消息复杂度。理论分析和仿真结果表明提出的算法能正确地解决CDTT问题,构建联合约束的CDS。

     

    Abstract: The connected dominating tree with bounded transmission delay problem (CDTT) is defined based on (α,β)-tree for the construction of connected dominating set (CDS) in wireless sensor network., distributed connected dominating tree (CDT) algorithm is proposed to construct a CDT-tree with limited total power while moderating the constraint of the transmission delays. Our distributed algorithm for CDS consists of two phases: firstly construct a maximal independent set (MIS) based on a unit disk graph,and then implement the CDT algorithm based on a double weighted, undirected graph satisfying the requirements of energy consumption, transmission delays simultaneously with O(n2) time, message complexity. The theoretical analysis, simulation results show that the CDT algorithm gives an effective solution to the CDTT problem, construct the CDS with combined constraints.

     

/

返回文章
返回