Формализация и исследование живучести иерархических сетей связи тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

• Введение

• Глава 1. Иерархические сети связи (ИСС) и их свойства

1. Описание модели ИСС

2. Задача анализа допустимости ИСС

3. Эффективность функционирования ИСС

4. Суперконкурентное распределение потоков в ИСС

• Глава 2. Живучесть иерархических сетей при создании неуязвимого кольцевого резерва

1. Задача анализа живучести ИСС

2. Расчет резервного кольца иерархической сети связи

3. Расчет резервного кольца иерархической сети связи в симметричном случае

4. Гарантированная оценка величины резервного кольца

V7 6 (0,1)

• Глава 3. Общая задача анализа уязвимости симметричных иерархических сетей

1. Задача анализа живучести СИСС при разрушении кольца

2. Сравнение вариантов распределения резервной мощности между кольцевыми и радиальными ребрами СИСС

Общая характеристика работа

Актуальность темы

Многие сложные системы имеют структуру связей типа "звезда", так называемая иерархическая сеть связи. Речь пойдет об одноуровневой иерархии. Подобные сети возникают при моделировании сетей связи для иерархических систем управления (ИСУ) с веерной иерархической структурой. Предполагается, что управляющий центр ИСУ передает сообщения или получает их от подчиненных (или узлов нижнего уровня).

В веерной ИСУ подчиненные, как правило, не взаимозаменяемы — имеют разные функции, и сообщение одному из них ничего не значит для другого. Необходимость передачи сообщения конкретному подчиненному возникает в произвольный момент времени, а его потеря не компенсируется хорошими условиями связи с другими подчиненными.

Графовые структуры типа звезды обладают плохими характеристиками живучести. Необходимость создания резерва продиктована важностью поддержания живучести сети связи для нормального функционирования ИСУ, поскольку наличие связи между центром и подчиненными является ключевым моментом для иерархических систем. Вопрос заключается лишь в определении оптимального объема резерва и его структуры. В нашей работе исследуется кольцевая структура резерва и проводится ее сравнение со структурой типа звезды, когда дополнительная пропускная способность резервируется на исходных ребрах сети. Разработка соответствующих методов исследования операций является актуальной.

Целью диссертационной работы является исследование живучести иерархических сетей связи, разработка методов повытения их живучести и расчет гарантированных оценок живучести иерархических сетей.

Методы исследования

В работе используется аппарат линейного программирования, теория оптимизации и исследования операций.

Обоснованность научных положений

Теоретические положения диссертации сформулированы в виде лемм, утверждении и теорем и строго доказаны.

Научная новизна

В диссертации предложено создание резерва, позволяющего повысить живучесть иерархических сетей. Найдено условие живучести иерархических сетей при создании кольцевого резерва в предположении его неразрушаемости. Получены гарантированные оценки живучести симметричных иерархических сетей связи при создании кольцевого резерва и радиального резерва в условиях их разрушаемости.

Практическая ценность работы

Результаты, полученные в работе, могут быть использованы при повышении живучести иерархических сетей связи.

Апробация работы

Основные результаты диссертации докладывались на 3-й Московской международной конференции по исследованию операций (Москва, 2001), на 9-ом Иранском семинаре аспирантов в Европе (Бирмингем, 2002), на кафедре исследовании операций факультета ВМиК МГУ им. М. В. Ломоносова.

Публикации

Основные результате диссертации опубликованы в работах [1,2,30,31].

Структура и обьем диссертации

Диссертация состоит из введения и трех глав. Общий объем диссертации 105 страниц. Список цитируемой литературы содержит 52 наименований.

1. Ахмады М.Б., Малашенко Ю.Е., Новикова Н.М. Исследование живучести иерархической сети. //Вести, моек, ун-та. сер. 15, вычисл. матем. и киберн. 2001. № 3. С. 1823

2. Ахмады М.Б Расчет резервного кольца иерархической сети связи. // Прикладная математика и информатика. № 10, 2002 с.130-162.

3. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

4. Давыдов Э.Г. Игры, графы, ресурсы. М.: Радио и связь, 1981.

5. Давидсон М. Р. Условия устойчивости множества крайних точек полиэдра и их применение в сетевой оптимизации. М.: ВЦ РАН, 1996

6. Давидсон М. Р., Малашенко Ю. Е., Новикова Н. М. и др. Математические постановки задач восстановления и обеспечения живучести для многопродуктовых сетей. М.: ВЦ РАН, 1993.

7. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Новосибирск: изд-во Новосибирского ун-та, 1996.

8. Дудник Б. Я., Овчаренко В. Ф., Орлов В. К. и др. Надежность и живучесть систем связи (под ред. Б. Я. Дудника). М.: Радио и связь, 1984.

9. Жуковский В.И., Салуквадзе М.Е. Оптимизация гарантий в многокритериальных задачах управления. Тбилиси: Мецниереба, 1996.

10. Йенсен П., Барнес Д. Потоковое программирование. М.: Радио и связь, 1984.

11. Карзанов А. В. Комбинаторные способы решения разрезных о мультипотоках // Комбинаторные методы в потоковых Вып.З. М.: ВНИИСИ, 1979. С. 6-69.

12. Карманов В. Г., Федоров В. В. Моделирование в исследовании операций. М.: Твема, 1996.

13. Краснощекое П.С., Петров А.А. Принципы построения моделей. М.: МГУ, 1983.

14. Крапива А. И. О выделении независимых деревьев графа в задачах исследования живучести сетей связи / / Информационные системы и их анализ. М.: Наука, 1978. С. 99104.

15. Лочмелис Я. Я. Многокритериальные задачи оптимизации сетей связи // Радиоэлектроника и электросвязь / Ис-след. по электродинамике и теории цепей. Рига, 1981. С. 105-111.

16. Малашенко Ю.Е. Нормативный подход к анализу многопродуктовых сетей / / Изв. АН СССР. Техн. кибернетика, 1988 № 3. С. 117-122.

17. Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. М.: Эдиториал УР-СС, 1999.

18. Малашенко Ю.Е., Новикова Н.М., Поспелова И.И. Многокритериальный синтез потоковых сетей с гарантией живучести // Изв. РАН.Теория и системы управления. 2001. N.1 С.124-134.

19. Малашенко Ю.Е., Новикова Н.М. Анализ многопользова-тельскихсетевых систем с учетом неопределенности. VII. Задача нормативного анализауязвимости многопродуктовой потоковой сети // Изв. РАН. Теория и системыупра-вления. 1999. N.4 С.124-134.

20. Малашенко Ю.Е., Новикова Н. М. Потоковые задачи анализа уязвимости многопродуктовых сетей. М.: ВЦ АН СССР, 1989.

21. Малашенко Ю. Е., СтаневичюсА. -И. А. О решении многопродуктовой задачи с целочисленными потоками //Ж. вычисл. матем. и матем.физ.,1982. Т. 22. № 3. С.732-735.

22. Папернов Б. А. Массовое решение мультипотоковых задач // Комбинаторные методы в потоковых задачах. Вып.З. М.: ВНИИСИ, 1979. С. 81-89.

23. Подиновский В.В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982.

24. Поспелов Г. С. , Ириков В. А. Программно целевое планирование и управление. М.: Советское радио, 1976.

25. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

26. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.

27. Современное состояние теории исследования операций. Под ред. Н. М. Моисеева. М.: Наука, 1979.

28. Ahmadi М. В. Guarantee of survivability of symetrical hierarchical networks //Тезисы докладов 3 й Московской международной конференции по исследоаванию операций (Москва, 2001).

29. Ahmadi М. В. Guarantee of survivability of hierarchical networks // 9th Iranian Students Seminar in Europe (Birmingham 2002).

30. Assad A. A. Multicommodity network flows: A survey // Networks, 1978. V. 8. N. 1. P. 37-91.

31. Bellmore M., Ratlliff H. D. Optimal defence of multi-commodity networks // Managment Science, 1871. V. 18. N. 4. P.174-185.

32. Biswas J., Matula D. W. Two flow routing algorithms for the maximum concurrent flow problem // Fall Joint Comput. conf., Dallas, Tex., Nov. 2-6, 1986. Proc. Washington, D. C., 1986. P. 629-636.

33. Boesch F. T. Lower bounds on the vulnerability of a graph // Networks, 1972. V. 2. P. 329-340.

34. Cacetta L. Vulnerability of communication networks// 1984. V. 14, N. 1. P. 141-146.

35. Chen C. Garfinkel R. S. The generalised diameter of a graph//Networks, 1982. V.12, N. 3. P. 335-340.

36. Christofides N. Whitlock C. A. Network synthesis with connectivity constraints a survey // Operations Research

37. Proceedings of 9-th IFORS Conference, Hamburg. 1981. P. 705-723.

38. Darwish M. G., Younis M. I. Multicommodity network flow problems. Analysis and assesment under failure and/or structural perturbations // Operational Research -81. Proceedings of 9th IFORS International Conference. Hamburg, 1981. P. 725-731.

39. Ford L. R., Fulkerson D. R. Suggested computation for maximal multi-commodity network flows, Man. Sci. , 5, 1958.

40. Frederickson G. N., Joseph J. J. Approximation algorithms for several graph augmentation problems // SIAM J. comput., 1981. V. 10. N. 2. P. 270-283.

41. Habib M., Peroche B, A construction metod for minimally k-edge connected graphs // Combinatorics, 1980. Amsterdam е. a. V. 79. Part 2. P. 199-204.

42. Ни Т. С. On the feasibility of simultaneous flows in network // Oper. Res., 1964.V.12. P. 359-360.

43. Iri M. On the extention of the maximum flow minimum -cut theorem to multicommodity flows //J. Oper. Res. Soc. Japan, 1971. V.13. P. 129 - 135.

44. Kajitani Y., Ueno S. The minimum augmentation of a directed tree to a K-edge connected directed graph. // Networks, 1986. V. 16. N. 2. P. 181-197.

45. Leighton Т., Makedon F., Plotkin S., Stein C., Tardos E. Tragoudas S. Fast approximation algorithms for multicommodity flow problems// J. Computer and Syst. Sci., 1995. V. 50 N. 1 P. 228 243.

46. Leong Т., Shor P., Stein C. Implementation of a combinatorial multicommodity flow algoritm. DIMACS working paper. New Brunswick (NJ): Rutgers University, 1992.

47. Onaga K. A multicommodity flow theorem // Electronics Commun. Japan, 1970. V.53. N. 7. P. 16 22.

48. Plesnik J. The complexity of desining a network with minimum diameter // Networks, 1981. V. 11. P. 77-85.

49. Shahrokhi F., MatulaD. W. The maximum concurrent flow problem // J. Assoc. Comput. Math., 1990. V. 37 N. 2. P. 318 334.

50. Shoone A. A., Bodlaender H. L., van Leewen J. Diameter increase caused by edge deletion // J. of Graph Theory, 1987. V. 11. N. 3. P. 409-427.

51. Tomlin A. Minimum-cost multi-commodity network flows, J. ORSA, 1966.