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

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

作　　者：孙彦景[1,2] 钱建生[1] 马姗姗[1] 任鹏[1] 

机构地区：[1]中国矿业大学信息与电气工程学院,江苏徐州221116 [2]中国矿业大学煤炭资源与安全开采国家重点实验室,江苏徐州221116

出　　处：《通信学报》2012年第5期58-65,共8页Journal on Communications

基　　金：国家高技术研究发展计划("863"计划)基金资助项目(2008AA062200);国家自然科学基金资助项目(50904070);中国博士后基金资助项目(20100471412);中央高校基本科研业务费专项资金资助项目(2010QNA48)~~

摘　　要：针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。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） algo- rithm was also proposed to construct strongly connected dominating set balancing transmission delay and energy consump- tion. 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 SDTr problem and construct the connected dominating sets（CDS） with constraints to form virtual backbone

关 键 词：无线传感器网络 强连通支配集 传输延时 能量消耗 约束均衡 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]