Skip to content

README.md

Latest commit

 

History

History
105 lines (70 loc) · 5.5 KB

README.md

File metadata and controls

105 lines (70 loc) · 5.5 KB
Raw

COBRA and MDTA algorithms

This repository provides MATLAB implementations of two algorithms:

  • MDTA constructs fully link-disjoint multicast trees.
  • COBRA constructs arc-disjoint multicast trees and can use bypass edges during construction.

Both algorithms share an exploration phase that derives source-rooted cost and hop information, followed by a construction phase that produces the multicast trees.

Requirements

  • MATLAB with support for graph, digraph, tables, and string arrays.
  • The core MDTA and COBRA implementations need no additional toolboxes.
  • The reference MILP requires Optimization Toolbox (intlinprog).
  • Parallel dynamic experiments require Parallel Computing Toolbox and a process-based pool.

Getting started

From the repository root, add the project to the MATLAB path:

root = pwd;
addpath(genpath(root));

Load a topology and run either algorithm:

[~, ~, G] = load_graph("topologies/Usnet", ...
    "/MatlabFileEdges.txt", "/MatlabFileNodes.txt");

mdta_results = RunMDTAorCobra(G, 1, [2 3], "MDTA", 2);
cobra_results = RunMDTAorCobra(G, 1, [2 3], "Cobra", 2);

RunMDTAorCobra returns a table containing the generated trees, route costs, number of routes found per destination, success metrics, and execution time.

Repository layout

  • functions/ contains the algorithm entry point, exploration phase, construction phase, topology loader, and shared helpers.
  • functions/ILP/ contains the three-stage reference MILP and an independent validator for its returned trees.
  • class/ contains the mobility-model configuration class, including the 3D Gauss--Markov parameters.
  • topologies/ contains the Usnet and Rand static topology data.
  • test/static/ contains reproducible static experiments and their evaluator.
  • test/dynamic_rwp/ contains the continuous Random Waypoint experiment and its evaluator.
  • test/dynamic_network/ contains the original continuous-simulation logic adapted to the public algorithm entry point, the 3D drone model, sequential and parallel launchers, and MATLAB tests.

Experiments

Run static experiments on Usnet and Rand:

run("test/static/s_static_test.m")
run("test/static/t_eval_static.m")

Run the Random Waypoint experiment:

run("test/dynamic_rwp/s_dynamic_rwp.m")
run("test/dynamic_rwp/t_eval_dynamic_rwp.m")

The experiment scripts use fixed random seeds for reproducibility. Results are written to the corresponding results/ directory.

Drone mobility and reference MILP

The drone scenario uses the same 50-node, 700 m by 700 m by 50–150 m, 3D Gauss--Markov configuration as MDP-TFM-NICO. Its radio range is 140 m, time step is 0.1 s, mean speed is 20 m/s, and Gauss--Markov coefficient is 0.85. The mobility update, 3D connectivity graph, independent MILP validator, and three-stage MILP are copied from the executed project. The continuous runner retains its session seeds, topology snapshots, lifetime and right-censoring rules, and MAT schema. MDP-partial and MDP call this repository's RunMDTAorCobra entry point in Cobra and MDTA mode, respectively.

From this repository's root, after addpath(genpath(pwd)), run the sequential campaign:

files = run_dynamic_network_continuous("drone", ...
    "Algorithms", ["MDP-partial", "MDP", "Cobra-ILP"], ...
    "RequestedTrees", [2, 3, 4]);

The defaults match the original campaign: ten independent 3600 s repetitions, seed 123, and session sizes from 1 to 49 destinations. This is computationally expensive, especially for the MILP. For a brief installation check:

files = run_dynamic_network_continuous("drone", ...
    "Repetitions", 1, "Duration", 0.2, ...
    "Algorithms", ["MDP-partial", "MDP", "Cobra-ILP"], ...
    "RequestedTrees", 2, "SessionSizes", 1, "Progress", false);
results = runtests('test/dynamic_network/tests');
assertSuccess(results);

For parallel execution, call run_dynamic_network_continuous_parallel("drone", ...) with the same options and optionally "NumWorkers", 4. Both launchers write one MAT per algorithm in test/dynamic_network/results/; a later run with the same scenario and algorithm replaces the earlier MAT. Each MAT contains metadata, sessionResults, and pathsMat_complete. sessionResults retains unavailable or unsuccessful sessions, while pathsMat_complete contains installed tree families with observed lifetimes and RightCensored flags. Parallel and sequential scientific outputs use the same seeds; wall-clock solve times and creation timestamps differ.

The standalone MILP can also be called as cobra_maximally_disjoint_ilp(G, root, destinations, maxTrees). Its result includes the chosen trees, optimization status, solver information, and an independent validation report. See the model notes for mobility equations and boundary handling.

Research-code notice

This software is provided for research and reproducibility. Validate results and parameter choices for the topology and scenario under study before relying on them.

Citation

If you use this software, please cite the release-specific software record and the associated article when available. Citation metadata is provided in CITATION.cff.

Manso, N., Lopez-Pajares, D., Carral, J. A., Carrascal, D., and Martinez-Yelmo, I. (2026). COBRA: Constructive Backtracking for Rooted Arc-Disjoint Trees in Mobile Ad Hoc Networks (Version 1.0.0). Zenodo. https://doi.org/10.5281/zenodo.21491835

License

This software is licensed under the Apache License 2.0. See LICENSE for details.