首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Constructing Load-Balanced Data Aggregation Trees in Probabilistic Wireless Sensor Networks
【24h】

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.
机译:数据收集是无线传感器网络(WSN)中的一项基本任务。能够执行聚合操作的数据收集树也称为数据聚合树(DAT)。当前,大多数现有工作集中于在确定性网络模型(DNM)下根据不同的用户要求构造DAT。但是,由于WSN中存在许多概率有损链路,因此在实际的概率网络模型(PNM)下获得DAT更为实用。此外,在当前文献中构造DAT时,负载平衡因子被忽略。因此,在本文中,我们着重于在PNM下构造负载平衡数据聚合树(LBDAT)。更具体地说,研究了三个问题,即负载平衡最大独立集(LBMIS)问题,连通最大独立集(CMIS)问题和LBDAT构造问题。 LBMIS和CMIS是众所周知的NP难题,而LBDAT是NP完全的难题。因此,本文提出了近似算法和近似因子的综合理论分析。最后,我们的仿真结果表明,所提出的算法明显优于现有的最新方法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号