多Sink无线传感器网络中最小时延数据汇集调度算法设计  

Minimum-latency Data Aggregation Scheduling Algorithm in Multi-sink Wireless Sensor Networks

作　　者：陈永燥 程红举[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108

出　　处：《小型微型计算机系统》2014年第4期734-739,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61370210)资助;福建省自然科学基金项目(2011J01345)资助;福建省教育厅科技项目(2012JA12027)资助;福建省科技创新平台项目(2009J1007)资助

摘　　要：数据汇集是无线传感器网络的一项重要技术,而汇集时延是评估其性能的重要指标.现有研究大多基于单Sink环境,较少考虑到网络规模扩大时需要部署多个Sink的情况.本文研究多Sink无线传感器网络中最小时延数据汇集调度问题(MSMLAS).提出了基于极大独立集的多Sink半结构拓扑汇集调度算法(MDAS-ST)与不使用极大独立集的多Sink无结构拓扑汇集调度算法(MDAS-UT).两种算法通过扩展父节点的选择范围,并根据节点分配的时隙序号以及该时隙的最大化利用来选取父节点,从而有效降低网络时延.文中分析并给出采用MDAS-ST算法网络数据汇集总时延的理论上限.实验结果表明,MDASST算法与MDAS-UT算法能够充分利用时隙,以低时延进行汇集调度.Data aggregation is an important technique used in wireless sensor networks, and aggregation latency is an important met- tic. Most of the current research works concern with only one single sink, and seldom study the case with multiple sinks deployed es- pecially when network size is increased. This paper focuses on the Multiple Sinks Minimum-Latency Aggregation Scheduling { MS- MLAS} problem in sensor networks. We propose two approximation algorithms, namely, the Multi-sink Data Aggregation Schedu- ling based on Semi-structured Topology algorithm （ MDAS-ST） with maximal independent set, and the Multi-sink Data Aggregation Scheduling based on Unstructured Topology algorithm { MDAS-UT }. Both algorithms expand the parent selection area for each node. The parent is selected according to the initial time-slot as well as the maximized time-slot reused. The upper bound of the aggregation latency using MDAS-ST is also analyzed. The experimental results show that both algorithms can make full use of time-slot and finish the data aggregation scheduling with low latency.

关 键 词：无线传感器网络 多Sink 数据汇集 最小时延调度 

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