The impact of topology on energy consumption for collection tree protocols: An experimental assessment through evolutionary computation

Doina Bucur, Giovanni Iacca, Giovanni Squillero, Alberto Tonda

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)

Abstract

The analysis of worst-case behavior in wireless sensor networks is an extremely difficult task, due to the complex interactions that characterize the dynamics of these systems. In this paper, we present a new methodology for analyzing the performance of routing protocols used in such networks. The approach exploits a stochastic optimization technique, specifically an evolutionary algorithm, to generate a large, yet tractable, set of critical network topologies; such topologies are then used to infer general considerations on the behaviors under analysis. As a case study, we focused on the energy consumption of two well-known ad hoc routing protocols for sensor networks: the multi-hop link quality indicator and the collection tree protocol. The evolutionary algorithm started from a set of randomly generated topologies and iteratively enhanced them, maximizing a measure of “how interesting” such topologies are with respect to the analysis. In the second step, starting from the gathered evidence, we were able to define concrete, protocol-independent topological metrics which correlate well with protocols’ poor performances. Finally, we discovered a causal relation between the presence of cycles in a disconnected network, and abnormal network traffic. Such creative processes were made possible by the availability of a set of meaningful topology examples. Both the proposed methodology and the specific results presented here – that is, the new topological metrics and the causal explanation – can be fruitfully reused in different contexts, even beyond wireless sensor networks.
Original languageEnglish
Pages (from-to)210 - 222
JournalApplied Soft Computing
Volume16
DOIs
Publication statusPublished - Mar 2014
Externally publishedYes

Keywords

  • Collection tree protocol (CTP), MultiHopLQI (MHLQI), Wireless sensor networks (WSN), Evolutionary algorithms (EA), Routing protocols, Verification, Energy consumption

Fingerprint Dive into the research topics of 'The impact of topology on energy consumption for collection tree protocols: An experimental assessment through evolutionary computation'. Together they form a unique fingerprint.

Cite this