时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。

Strongly connected dominating set construction algorithm balancing time delay and energy consumption

To the asymmetry of link in wireless sensor networks,a problem about the strongly connected dominating tree with bounded transmission delay(SDTT) was put forward.The distributed strongly connected dominating tree(SCDT) algorithm was also proposed to construct strongly connected dominating set balancing transmission delay and energy consumption.Firstly,it constructed a maximal independent set(MIS) based on a unit disk graph,and then implemented the SCDT algorithm based on a double weighted and directed graph fulfilling the requirements of energy consumption and transmission delays simultaneously.The theoretical analysis and simulation results show that the presented algorithm can correctly solve the SDTT problem and construct the connected dominating sets(CDS) with constraints to form virtual backbone.