(α,β)-constraints connected dominating set algorithm in wireless sensor network  

时延和功耗约束无线传感器网络连通支配集算法(英文)

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

机构地区：[1]中国矿业大学信息与电气工程学院,徐州221008 [2]中国矿业大学机械与电气工程学院,徐州221008

出　　处：《Journal of Southeast University(English Edition)》2008年第4期414-419,共6页东南大学学报（英文版）

基　　金：Major Program of the National Natural Science Foundation of China (No.70533050);High Technology Research Program ofJiangsu Province(No.BG2007012);China Postdoctoral Science Foundation(No.20070411065);Science Foundation of China University of Mining andTechnology(No.OC080303)

摘　　要：To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints is proposed. Based on the （α, β）-tree concept, a new connected dominating tree with bounded transmission delay problem（CDTT） is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases： The first phase constructs a maximum independent set（MIS）in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with（ α,β）-constraints balancing the requirements of power consumption and transmission delay.针对无线传感器网络虚拟骨干时延和功耗的约束问题,提出(α,β)-约束的连通支配集算法.根据(α,β)-约束定义了时延约束的连通支配树问题(CDTT),并给出构建同时符合时延约束和有限总功率消耗的连通支配树(CDT)算法.算法分为2个阶段执行:首先在单位圆图上构建网络的极大独立集,然后在无向图上基于不同权值的最小生成树和最短路径树,构造满足(α,β)-约束要求的支撑树.理论分析和仿真结果表明提出的算法能够正确地解决CDTT问题,并能够构建平衡功率消耗和传输时延要求的无线传感器网络虚拟骨干.

关 键 词：wireless sensor network connected dominating set transmission delay maximal independent set power consumption 

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