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

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

作　　者：孙彦景[1] 钱建生[1] 顾相平[1] 陈光柱[1] 

机构地区：[1]中国矿业大学信电学院,江苏徐州221008

出　　处：《电子科技大学学报》2009年第2期231-235,共5页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金重点项目(70533050);中国博士后科学基金项目(20070411065);江苏省高新技术重大项目(BG2007012)

摘　　要：针对无线传感器网络连通支配集构建问题,基于(α,β)-tree定义了具有传输时延约束的连通支配树CDTT问题,并提出CDT算法构建有限总功率消耗的CDT-tree,同时符合传输时延约束要求。给出的分布式CDS算法分为两个阶段执行,首先基于单位圆图构建MIS,然后在双权值无向图上使用MST和SPT实现CDT算法,同时满足联合约束要求,具有O(n2)的时间和消息复杂度。理论分析和仿真结果表明提出的算法能正确地解决CDTT问题,构建联合约束的CDS。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. And 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 and undirected graph satisfying the requirements of energy consumption and transmission delays simultaneously with O（n^2） time and message complexity. The theoretical analysis and simulation results show that the CDT algorithm gives an effective solution to the CDTT problem and construct the CDS with combined constraints.

关 键 词：联合约束 连通支配集 最大独立集 传输延时 无线传感器网络 

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