A Data Aggregation Method for Balancing Load under Probabilistic Network Model (PNM)

Abstract — Data aggregation is a very crucial technique in WSNs. Data aggregation helps in reducing the energy consumption by eliminating redundancy. 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).Most of the existing DAT construction works are based on the ideal Deterministic Network Model (DNM), where any pair of nodes in a WSN is either connected or disconnected. Under this model, any specific pair of nodes are neighbors if their physical distance is less than the transmission range, while the rest of the pairs are always disconnected. However, in most real applications, the DNM cannot fully characterize the behaviors of wireless links due to the existence of the transitional region phenomenon. The load-balance factor is also neglected when constructing DATs in current systems. And most of the current literatures investigate the DAT construction problem under the DNM. In this paper we are discussing on load balancing factor and also on construction of DAT using Probabilistic Network Model (PNM). Therefore, it is focused 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