Deterministic Algorithms in Dynamic Networks – Formal Models and Metrics

PDF

Authors
  1. Casteigts, A.
  2. Flocchini, P.
Corporate Authors
Defence R&D Canada - Ottawa, Ottawa ONT (CAN);OTTAWA UNIV, OTTAWA ON (CAN) SCHOOL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE
Abstract
The number of telecommunication networks deployed in a dynamic environment is quickly growing. This trend exists both in everyday life (e.g., smartphones, vehicles, and commercial satellites) and in a military context (e.g., dismounted soldiers or swarms of UAVs). Unfortunately, few theoretical tools to date have enabled the study of dynamic networks in a formal and rigorous way. As a result, it is hard and sometimes impossible to guarantee, mathematically, that a given algorithm will reach its objectives once deployed in real conditions. In this report, we identify a collection of recent theoretical tools whose purpose is to model, describe, and leverage dynamic networks in a formal way. These tools include a dynamic graph formalism, various computational models, and communication models for distributed networks. We extend many graph theoretical concepts towards a dynamic variant and show how these new variants impact the solution of classical distributed problems. The report also presents a hierarchy of dynamic networks based on dynamic graph properties, thereby offering a combinatorial alternative to the well-known mobility models typically used in simulations.

Il y a un résumé en français ici.

Report Number
DRDC-OTTAWA-CR-2013-020 — Contractor Report
Date of publication
01 Apr 2013
Number of Pages
82
DSTKIM No
CA037819
CANDIS No
537586
Format(s):
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: