Constructing Load-Balanced Data Aggregation Trees in Probabilistic Wireless Sensor Networks

doi:10.1109/TPDS.2013.160

Return

Constructing Load-Balanced Data Aggregation Trees in Probabilistic Wireless Sensor Networks

2014-07-01

PRE

DOI：10.1109/TPDS.2013.160

Original

Original request for help

Save

Abstract

En 中文

Data Gathering is a fundamental task in Wireless Sensor Networks (WSNs). Data gathering trees capable of performing aggregation operations are also referred to as Data Aggregation Trees (DATs). Currently, most of the existing works focus on constructing DATs according to different user requirements under the Deterministic Network Model (DNM). However, due to the existence of many probabilistic lossy links in WSNs, it is more practical to obtain a DAT under the realistic Probabilistic Network Model (PNM). Moreover, the load-balance factor is neglected when constructing DATs in current literatures. Therefore, in this paper, we focus on constructing a Load-Balanced Data Aggregation Tree (LBDAT) under the PNM. More specifically, three problems are investigated, namely, the Load-Balanced Maximal Independent Set (LBMIS) problem, the Connected Maximal Independent Set (CMIS) problem, and the LBDAT construction problem. LBMIS and CMIS are well-known NP-hard problems and LBDAT is an NP-complete problem. Consequently, approximation algorithms and comprehensive theoretical analysis of the approximation factors are presented in the paper. Finally, our simulation results show that the proposed algorithms outperform the existing state-of-the-art approaches significantly.

Keywords:

Probabilistic wireless sensor networks

load-balance

data aggregation tree

maximal independent set

minimum-sized connected dominating set

linear programming

integer programming

random rounding

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.