Characterizing Topological Bottlenecks for Data Delivery in CTP using Simulation-Based Stress Testing with Natural Selection

Routing protocols for ad-hoc networks, e.g., the Collection Tree Protocol (CTP), are designed with simple node-local behaviour, but are deployed on testbeds with uncontrollable physical topology; exhaustively verifying the protocol on all possible topologies at design time is not tractable. We obtain topological insights on CTP performance, to answer the question: Which topological patterns cause CTP data routing to fail? We stress-test CTP with a quantitative testing method which searches for topologies using evolutionary algorithms combined with protocol simulation. The method iteratively generates new test topologies, such that the execution of the protocol over these topologies shows increasingly worse data-delivery ratios (DDR). We obtain a large set of example topologies of different network sizes up to 50 nodes, network densities, data rates, table sizes, and radio-frequency noise models, which, although connected, trigger a data delivery of nearly zero.