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

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.