Minimum cost dominating tree sensor networks under probabilistic constraints

详细信息    查看全文

• 作者：Pablo Adasme ; ^a ; ^{pablo.adasme@usach.cl}Author Vitae ; Rafael Andrade^b ; ^{rca@lia.ufc.br}Author Vitae ; Abdel Lisser^c ; ^{abdel.lisser@lri.fr}Author Vitae
• 关键词：Dominating tree ; Probabilistic constraints ; Compact formulation ; Mixed integer linear programming ; Sensor network design
• 刊名：Computer Networks
• 出版年：2017
• 出版时间：15 January 2017
• 年：2017
• 卷：112
• 期：Complete
• 页码：208-222
• 全文大小：901 K
• 卷排序：112

文摘

There is an increasing interest in planning sensor networks by considering both the impact of distances among sensors and the risk that power consumption leads to a very small network lifetime. A sensor failure can affect sensors in its neighborhood and compromise the network data communication. Weather conditions may cause the power consumption of data communication to vary with uncertainty. This work introduces a compact probabilistic optimization approach to handle this problem while considering jointly or separately dependence among power consumption of the links of the network in a unified framework. We explore the concept of copulas in a dominating arborescence (DA) model for directed graphs, extended accordingly to handle the uncertain parameters. We give a proof of the DA model correctness and show that it can solve to optimality some benchmark instances of the deterministic dominating tree problem. Numerical results for the probabilistic approach show that our model tackles randomly generated instances with up to 120 nodes.