降低传感器网络数据聚集延迟的近似调度算法  

Approximate scheduling algorithm for reducing data aggregation latency in wireless sensor networks

作　　者：郭龙江[1,2] 任美睿[1,2] 李金宝[1,2] 范文彬[1] 

机构地区：[1]黑龙江大学计算机科学技术学院,哈尔滨150080 [2]黑龙江省数据库与并行计算重点实验室,哈尔滨150001

出　　处：《黑龙江大学工程学报》2011年第2期80-94,共15页Journal of Engineering of Heilongjiang University

基　　金：国家自然科学基金青年科学基金(60803015);中国博士后基金资助项目(20080430902);黑龙江省教育厅重点项目(1154Z1001);黑龙江省教育厅科学技术研究指导项目(11533045;11531276);黑龙江省博士后基金(LRB08-021);黑龙江省科技计划(QC04C40);黑龙江省研究生创新科研项目(YJSCX2009-019HLJ);哈尔滨市青年科技创新人才研究专项资金项目(2008RFQXG107;2009RFQXG080)

摘　　要：目前在无线传感器网络中,数据聚集大多数采用的都是单信道,导致有很高的延迟。尤其是在高密度无线传感器网络中,数据聚集是一个比较耗时的操作。人们已经证明了最小化数据聚集延迟问题是NP难问题。给出一个新的降低数据聚集延迟的近似算法,其近似比为16,并在理论上证明了该算法的延迟上界是15R+Δ-15,Δ是网络的最大度,R是网络半径。相对于现有的算法,该算法理论上具有更小的近似比和时间延迟。模拟结果也说明该算法平均延迟比现有的算法小。Existing works on data aggregation in wireless sensor networks（for short WSNs） usually use a single channel which results in a long latency due to high interference,especially in high-density WSNs.Therefore,data aggregation is a fundamental yet time consuming task in WSNs.Minimum data aggregation latency problem has been already proved NP-hard.This paper presents a new approximate algorithm with ratio bound 16 to reduce data aggregation latency and proves that this algorithm has a latency bound of 15R ＋ Δ-15,where Δ is the maximum degree and R is the network radius.This paper proves that the algorithm has lower time latency and ratio bound than other existing algorithms in theory.Simulation results show that this algorithm has lower average latency than previous works.

关 键 词：无线传感器网络 数据聚集延迟 调度算法 

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