Data distribution optimization in a system of collaborative systems
Ronan Bocquillon9 mars 2017 - 14:00
Systems of systems are supersystems comprising elements which are themselves independent operational systems, all interacting to achieve a common goal. When the subsystems are mobile, these may suffer from a lack of continuous end-to-end connectivity. To address the technical issues in such networks, the common approach is termed delay-tolerant networking. Routing relies on a store-forward mechanism. Data are sent from one system to another – depending on the communication opportunities, termed contacts, that arise when two systems are close – and stored throughout the network in hope that all messages will reach their destination. If data are too large, these must be split. Each fragment is then transmitted separately.
In this work, we assume that the sequence of contacts is known. Thus, we focus on applications where it is possible to make realistic predictions about system mobility (e.g. satellite networks and public transportation systems). We study the problem of making the best use of knowledge about possibilities for communication when data need to be routed from a set of systems to another within a given time horizon. The fundamental question is: “Which elements of the information should be transferred during each contact, so that the dissemination length is minimized?”.
First I will formalize the so-called dissemination problem, and prove this is strongly NP-Hard. Then I will propose non-polynomial algorithms to solve it. These rely on different dominance rules, preprocessing procedures, integer-linear programming and constraint programming. In this talk, special emphasis will be put on constraint programming based approaches. Many experimental results will be reported to show the efficiency of these algorithms in practice.