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

•We propose an efficient evolutionary methodology for analyzing the performance of wireless sensor networks routing protocols.•We applied the methodology to two ad hoc collection tree protocols: MHLQI and CTP.•We ran extensive experiments and obtained large sets of topologies (of up to 50 nodes) showing abnormally high traffic.•We empirically extracted predictive topological metrics that were shown to statistically correlate with high network traffic.•We verified with a posteriori experiments that these metrics are also a sufficient cause of high traffic.

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.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide