IMPROVED ALGORITHM FOR MINIMUM DATA AGGREGATION TIME PROBLEM IN WIRELESS SENSOR NETWORKS

Jianming ZHU ;Xiaodong HU

系统科学与复杂性(英文) ›› 2008, Vol. 21 ›› Issue (4) : 626-636.

PDF(290 KB)
PDF(290 KB)
系统科学与复杂性(英文) ›› 2008, Vol. 21 ›› Issue (4) : 626-636.
论文

IMPROVED ALGORITHM FOR MINIMUM DATA AGGREGATION TIME PROBLEM IN WIRELESS SENSOR NETWORKS

    Jianming ZHU (1), Xiaodong HU (2)
作者信息 +

IMPROVED ALGORITHM FOR MINIMUM DATA AGGREGATION TIME PROBLEM IN WIRELESS SENSOR NETWORKS

    Jianming ZHU (1), Xiaodong HU (2)
Author information +
文章历史 +

摘要

Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a new approximation algorithm for this NP-hard problem with guaranteed performance ratio 7Δlog2|S|+c, which significantly reduces the current best ratio of Δ1, where S is the set of sensors containing source data, Δ is the maximal number of sensors within the transmission range of any sensor, and c is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.

Abstract

Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a new approximation algorithm for this NP-hard problem with guaranteed performance ratio 7Δlog2|S|+c, which significantly reduces the current best ratio of Δ1, where S is the set of sensors containing source data, Δ is the maximal number of sensors within the transmission range of any sensor, and c is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.

关键词

Approximation algorithm / data aggregation / wireless sensor network

Key words

Approximation algorithm / data aggregation / wireless sensor network

引用本文

导出引用
Jianming ZHU , Xiaodong HU . IMPROVED ALGORITHM FOR MINIMUM DATA AGGREGATION TIME PROBLEM IN WIRELESS SENSOR NETWORKS. 系统科学与复杂性(英文), 2008, 21(4): 626-636
Jianming ZHU , Xiaodong HU . IMPROVED ALGORITHM FOR MINIMUM DATA AGGREGATION TIME PROBLEM IN WIRELESS SENSOR NETWORKS. Journal of Systems Science and Complexity, 2008, 21(4): 626-636
PDF(290 KB)

104

Accesses

0

Citation

Detail

段落导航
相关文章

/