Jacek Cichoń

Katedra Podstaw Informatyki ● WIT ● PWr
Strona główna Moje badania

OPUS 5: Algorytmika Dynamicznych Sieci

  1. Numer decyzji: 2013/09/B/ST6/02258
  2. Okres realizacji: 03.04.2014 - 02.04.2017
  3. Planowane nakłady: 753 480 zł
  4. Główni wykonawcy projektu:
    • prof. dr hab. Jacek Bronisław Cichoń (kierownik projektu)
    • prof. dr inż. Wojciech Marek Szpankowski
    • dr hab. inż. Marek Dariusz Klonowski
    • dr inż. Zbigniew Gołębiewski
    • dr Mirosław Korzeniowski

Cel prowadzonych badań/hipoteza badawcza

Fragment z opisu wniosku:

Celem projektu jest opracowanie narzędzi służących do modelowania, badania oraz budowania algorytmów dla dynamicznie zmieniających się sieci. Jednym z tego typu sieci są sieci ad-hoc i one będą głównym celem planowanych badań. Narzędzia te mają służyć, miedzy innymi, do znalezienia "normalnego" zachowania się sieci danego typu, diagnostyki odchyleń od normalnego zachowania oraz reakcji na stwierdzone odchylenia. Algorytmy które zamierzamy zaprojektować i zbadać oparte będą o zmodyfikowane warianty techniki propagacji maksimów, dzięki czemu chcemy osiągnąć ich dużą odporność na zakłócenia i zmiany topologii sieci oraz stosunkowo małą złożoność energetyczna. Nie wymagają one budowy wewnątrz sieci żadnych kosztownych w utrzymaniu struktur typu drzewa rozpinające. Algorytmy te mają również charakter samo-stabilizujący się i nie wymagaja˛ żadnych dodatkowych mechanizmów wygaszania przesyłanych komunikatów (typu TTL) Oto lista głównych hipotez, które pragniemy zweryfikować w trakcie naszych badań:

  1. H1. Odpowiednio zmodyfikowana metoda max-propagation może zostać wykorzystana do wyznaczania szeregu ważnych charakterystyk sieci dynamicznych.
  2. H2. Istnieją rozproszone metody wyznaczania suboptymalnych strategii routingowych o przepustowości zbliżonej do dolnej granicy typu Kumara- Gupty uwzględniających specyficzną topologię sieci.
  3. H3. Odpowiednio zaproponowany mechanizm kooperacji pomiędzy wierzchołkami wewnątrz sieci może zwiększyć możliwości obliczeniowe sieci bez istotnego pogarszania złożoności komunikacyjnej.
  4. H4. Istnieje ilościowa metoda oceny maksymalnej dokładności eksploracji sieci uwzględniająca dynamikę zmian sieci.
  5. H5. Klasyczne modele probabilistyczne nie opisują właściwie dużej klasy sieci typu ad-hoc. Istnieją bardziej adekwatne modele.
  6. H6. Istnieją rozproszone samo-stabilizujące się algorytmy budujące wewnątrz sieci szybkie i niezawodne linie transmisyjne mogące służyć do przesyłania informacji w sytuacjach kryzysowych.

Publikacje

  • 2014
    1. Abram Magner and Svante Janson and Giorgos Kollias and Wojciech Szpankowski, On Symmetry of Uniform and Preferential Attachment Graphs, Electr. J. Comb., vol 21, number 3, 2014, [combinatorics], [pdf]
    2. Yuliy Baryshnikov and Jaroslaw Duda and Wojciech Szpankowski, Markov Field Types and Tilings, Proceedings of IEEE International Symposium on Information Theory (ISIT) 2014, [pdf]
    3. Marek Klonowski, Małgorzata Sulkowska, Energy-optimal algorithms for computing aggregative functions in random networks, Discrete Mathematics and Theoretical Computer Science DMTCS vol. 17:3, 2016, 285–306, [pdf]
    4. Joachim M. Buhmann, Alexey Gronskiy and Wojciech Szpankowski, Free Energy Rates for a Class of Very Noisy Optimization Problems, AofA'2014, Discrete Mathematics and Theoretical Computer Science, Paris 2014, [pdf]
  • 2015
    1. Abram Magner, Daisuke Kihara,Wojciech Szpankowski, Phase Transitions in a Sequence-Structure Channel, 2015 Information Theory and Applications Workshop, {ITA} 2015, San Diego, CA, USA, February 1-6, 2015 [pdf]
    2. Marek Klonowski, Dominik Pajk, Electing a Leader in Wireless Networks Quickly Despite Jamming, 27th ACM Symposium on Parallelism in Algorithms and Architectures, Portland, Oregon, USA, June 13 - 15, 2015, [pdf]
    3. Joachim M. Buhmann, Julien Dumazert, Alexey Gronskiy, Wojciech Szpankowski, A Validation Criterion for a Class of Combinatorial Optimization Problems via Helmholtz Free Energy and its Asymptotics, JMLR: Workshop and Conference Proceedings vol 40:1, 19, 2015, [pdf]
    4. Abram Magner, Wojciech Szpankowski, Daisuke Kihara, On the Origin of Protein Superfamilies and Superfolds, SCIENTIFIC REPORTS, 5:8166, DOI: 10.1038/srep08166, [pdf]
  • 2016
    1. Abram Magner and Daisuke Kihara and Wojciech Szpankowski, A Study of the Boltzmann Sequence-Structure Channel, Proceedings of the IEEE 105(2): 286-305 (2017), [pdf]
    2. Krzysztof Grining, Marek Klonowski, Piotr Syga, Practical Fault-Tolerant Data Aggregation, Applied Cryptography and Network Security - 14th International Conference, ACNS 2016, Guildford, UK, June 19-22, 2016, Proceedings, [pdf]
    3. Philippe Jacquet, Wojciech Szpankowski, Average Size of a Sufix Tree for Markov Sources, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asumptotic Methods for the Analysis of Algorithms [pdf]
    4. Michael Drmota, Abram Magner, Wojciech Szpankowski, Asymmetric Renyi Problem and PATRICIA Tries, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asumptotic Methods for the Analysis of Algorithms, [pdf]
    5. Jacek Cichon, Rafal Kapelko, Dominik Markiewicz, On Leader Green Election, AofA'16, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asumptotic Methods for the Analysis of Algorithms, [pdf], [arxiv]
    6. Jacek Cichoń, Karol Gotfryd, Average Counting via Approximate Histograms - Preliminary Report, IEEE 7th International Conference on Intelligent Systems, Modelling and Simulation, Bangkok (Thailand), 25-27 January, 2016, [pdf], [IEEE Xplore]
    7. Marcin Bienkowski, Leszek Gąsieniec, Marek Klonowski, Mirosław Korzeniowski, Bernard Mans, Stefan Schmid and Roger Wattenhofer, Distributed Alarming in the On-Duty and Off-Duty Models, IEEE/ACM Trans. Netw., vol. 24, number 1, 2016, [pdf]
    8. Zbigniew Gołębiewski, Abram Magner, Wojciech Szpankowski, Entropy of Some General Plane Trees, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, June 25-30, 2017, [pdf]
  • 2017
    1. Jacek Cichoń, Abram Magner, Wojciech Szpankowski, Krzysztof Turowski, On Symmetries of Non-Plane Trees in a Non-Uniform Mode, SODA'17 (Analco) 2017, [pdf]
    2. Abram Magner, Ananth Grama, Jithin Sreedharan, Wojciech Szpankowski, Recovery of Vertex Orderings in Dynamic Graph, 2017 IEEE International Symposium on Information Theory (ISIT), [pdf]
    3. Krzysztof Grining, Marek Klonowski, Towards Extending Noiseless Privacy - Dependent Data and More Practical Approach, Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, ASIA CCS '17 [pdf]
    4. Tomasz Łuczak Abram Magner Wojciech Szpankowski, Asymmetry and Structural Information in Preferential Attachment Graphs [pdf]
    5. Tomasz Łuczak Abram Magner Wojciech Szpankowski, Structural Information and Compression of Scale-Free Graphs [pdf]
    6. Karol Gotfryd, Marek Klonowski, and Dominik Pająk, On Location Hiding in Ad Hoc Systems (Extended Version), SIROCCO 2017, 24th International Colloquium on Structural Information and Communication Complexity, 19-22 June 2017 [pdf]
    7. Zbigniew Golebiewski, Marcin Kardas, Jakub Lemiesz Krzysztof Majcher, On structural entropy of uniform random intersection graphs, {IEEE} International Symposium on Information Theory, 2017, Aachen, Germany, June 25-30, 2017, [pdf]
    8. Jacek Cichoń, Maciej Gebala, Marcin Zawada, Fault Tolerant Protocol for Data Collecting in Wireless Sensor Networks, The 22nd IEEE Symposium on Computers and Communications, , Heraklion, Crete, Greece, [pdf]
    9. Marek Klonowski, Dominik Pająk, Broadcast in radio networks: time vs. energy tradeo's., [pdf]
  • 2018
    1. Patryk Kozieł, Małgorzata Sulkowska, Uniform random posets, [pdf]
    2. Zbigniew Gołębiewski, Abram Magner, Wojciech Szpankowski, Entropy and Optimal Compression of Some General Plane Trees, [pdf]
    3. Tomasz Łuczak, Abram Magner, Wojciech Szpankowski, Structural Information in Graphs: Symmetries an Admissible Relabelings, [pdf]
    4. Philippe Jacquet, Wojciech Szpankowski, Towards LZ’78 Analysis for Markov Sources: Distribution of Tail Symbols in DST, [pdf]
    5. Jacek Cichoń, Karol Godfryd, Average Counting via Approximate Histograms, ACM Transactions on Sensor Networks (TOSN), Volume 14 Issue 2, March 2018, [TOSN], [pdf]
    6. Dominik Bojko, Jacek Cichoń, Bogdan Węglorz, A Note on Leader Election Algorithms, [pdf]
    7. Dominik Bojko, Jacek Cichoń, Taking snapshots from a stream - preliminary report, [pdf]

Osoby które chcą się zapoznać z tymi pracami do których nie ma linków, proszę o kontakt e-mailowy.