Large data set from experimentation with the worst-case behaviour of ad-hoc network protocols
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
CTP-delivery
CTP-energy
MHLQI-energy
README.md

README.md

This is a large data set from experimentation with the worst-case behaviour of ad-hoc network protocols. Current protocols analyzed: Collection Tree Protocol (CTP) and Multihop Link Quality Indicator (MHLQI) for ad-hoc wireless networks. We searched for network topologies which give (1) worst-case data delivery ratios, and, separately, (2) (worst-case) energy behaviour of these protocols, i.e., the number of packet transmission and reception, both for a single node and summed up for the entire network. These are called objectives or fitness functions.

The methodology exploits a stochastic optimization technique, i.e., an evolutionary algorithm, to generate a large set of network topologies over which the data delivery (as a percentage of the data sent) is lowest, or the amount of network traffic is the maximum that the algorithm found within a certain runtime. Statistics can then be performed upon this data set of counterexample topologies (i.e., counterexample to good performance), and a causal relation can be verified (through further experimentation) between particular topological features and particular performance factors, e.g., delivery in CTP.

Two articles describe this work:

  • D. Bucur, G. Iacca, A. Tonda, G. Squillero, The Impact of Topology on Energy Consumption for Collection Tree Protocols: an Experimental Assessment through Evolutionary Computation, Applied Soft Computing, Elsevier, Volume 16, Issue 1, Pages 210-222, March 2014 bib

  • D. Bucur, G. Iacca, P. T. De Boer, Characterizing Topological Bottlenecks for Data Delivery in CTP using Simulation-Based Stress Testing with Natural Selection, Ad Hoc Networks, Elsevier, Volume 30, Pages 22-45, July 2015 bib

The format of this dataset:

  • There is a root directory for each combination protocol-objective: CTP-delivery, CTP-energy, MHLQI-energy. Each such directory then has one or more subdirectories per configuration of experiment, e.g., "CTP-10n-div02-DDR-CONN" evaluates CTP over 10-node, 1/2-density connected networks for data delivery, and "CTP-evo-20n-s-div02" evaluates CTP over 20-node, 1/2-density networks, for total energy.

  • For each experiment, the subdirectory gives all the topology files resulted during the runtime of the algorithm (either with duplicates removed, or with duplicates left in). The topologies are directional, and encoded with one link per line, i.e., "gain 0 29 -16" models a link from node 0 to node 29 of signal gain -16. They can be used by TOSSIM as is.

For each delivery experiment, the data file named data-individuals.txt is a processed summary of the set of topologies. Each line describes one topology (i.e., 16 simulations of it). Line:

1 BJT 0.09722125 0.0367461785215 0.11111 0.0

says that topology BJT was found to have an average DDR of 0.097 (out of 1), with a standard deviation of 0.036, a maximum DDR found among simulations of 0.111, and minimum 0.

For each energy experiment, the data file is named data-..-individuals.txt. The following line:

5998 CU4 12665.9375 74.4231724247 12779 12540 D-edges 203
D-max-degree 15 D-min-degree 3 D-max-in-degree 9 D-min-in-degree 1
D-max-out-degree 9 D-min-out-degree 1 D-diameter-from0 4 UR-edges 18
UR-max-degree 3 UR-min-degree 0 UR-connected 0 UR-components 32 DD 18 NSUC.disc 0 CSUC.disc 0 min-CSUC.disc 0 all-sinkless_cycles 0
NSUC.conn 0 NSUC-D-max-degree 0 NSUC-D-max-in-degree 0 NSUC-D-max-out-degree 0

summarizes the behaviour and structure of topology CU4 (the identifier in column 2). This topology is found in file topoCU4.txt in the same subdirectory). The average fitness value and standard deviation (after 16 simulations) for the topology is in columns 3-4, with the maximum and minimum fitness among the 16 simulations in the following two columns. The remaining of the line holds the values of various topological metrics, starting with the number of network links and node degrees, and ending in values for the topological metrics DD, NSUC and CSUC (described in our ASOC 2014).