Помощь в написании студенческих работ
Антистрессовый сервис

Методы и алгоритмы автоматизированного проектирования проводных телекоммуникационных сетей минимальной стоимости

Диссертация: Методы и алгоритмы автоматизированного проектирования проводных телекоммуникационных сетей минимальной стоимости
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В существующих на данный момент алгоритмах построения сетей минимальной стоимости заданной топологии стоимость затрат на прокладку линий связи между узлами телекоммуникационной сети определяется либо экспертным путем, либо не учитывает неоднородность среды, по которой будет прокладываться трасса: предполагается, что стоимость прокладки единицы длины линии связи по всей территории является… Читать ещё >

Методы и алгоритмы автоматизированного проектирования проводных телекоммуникационных сетей минимальной стоимости (реферат, курсовая, диплом, контрольная)

Содержание

  • Стр
  • Общая характеристика работы
  • Глава 1. Анализ существующих методов и алгоритмов построения телекоммуникационных сетей минимальной стоимости
    • 1. 1. Описание алгоритмов построения сетей минимальной стоимости
      • 1. 1. 1. Алгоритмы построения минимальных остовных деревьев. 1.1.2 Алгоритмы построения деревьев Штейнера
      • 1. 1. 3. Алгоритмы построения минимальных гамильтоновых контуров
      • 1. 1. 4. Анализ предложенных алгоритмов
    • 1. 2. Алгоритмы определения маршрута трассы
      • 1. 2. 1. Конструкторская трассировка
  • Ь 1.2.2 Строительная трассировка
    • 1. 2. 3. Анализ алгоритмов трассировки
    • 1. 3. Анализ близких задач
  • Выводы по первой главе
    • Глава 2. Разработка математического аппарата соединения двух точек на взвешенной плоскости
    • 2. 1. Соединение точек, расположенных в соседних полуплоскостях с различной стоимостью прокладки
    • 2. 1. 1. Решение уравнений третьей степени (метод Кардано)
    • 2. 1. 2. Решение уравнений четвертой степени (метод Феррари)
    • 2. 2. Соединение точек, расположенных в полуплоскости с высокой стоимостью прокладки
    • 2. 3. Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных произвольной кривой
    • 2. 4. Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются параллельные прямые
    • 2. 5. Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются две непараллельные прямые
    • 2. 6. Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных тремя прямыми, сходящимися в одной точке
    • 2. 7. Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных двумя прямыми, сходящимися в одной точке
  • Выводы по второй главе
    • Глава 3. Разработка алгоритмов соединения точек на взвешенной плоскости и объединение п точек в сеть заданной топологии
    • 3. 1. Разработка алгоритма соединения двух точек на взвешенной плоскости
    • 3. 1. 1. Предварительный этап соединения двух точек на взвешенной плоскости
  • Вариант
  • Вариант
  • Вариант
    • 3. 1. 2. Улучшение пути, соединяющего две точки на взвешенной плоскости
    • 3. 2. Разработка алгоритма объединения точек на взвешенной плоскости в сеть заданной топологии
    • 3. 3. Разработка алгоритма построения телекоммуникационной ^ сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости
  • Выводы по третьей главе
    • Глава 4. Экспериментальная проверка работы разработанных алгоритмов
    • 4. 1. Разработка автоматизированной системы построения сети заданной топологии на взвешенной плоскости
    • 4. 2. Описание вычислительного эксперимента
    • 1. 4.3 Анализ полученных результатов
  • Выводы по четвертой главе

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

.

В последние годы в Российской Федерации наблюдается развитие рынка информационных и телекоммуникационных услуг. Новые технологии активно внедряются в различные сферы жизни. В связи с этим важной становится проблема передачи данных. Однако существующая на данный момент инфраструктура сетей недостаточно развита, а линии связи (особенно в регионах) не удовлетворяют пользователей ни по качеству, ни по скорости передачи данных, в связи с чем возникает задача проектирования новых и модернизация существующих линий связи. Примером активно развивающихся сетей являются некоммерческие научно-образовательные сети, такие как RUNNet, RBnet, FREEnet, RELARN-IP, RUHEP-Radio-MSU, РОСКОН и др.

Стоимость прокладки линий связи между узлами телекоммуникационной сети, которая складывается из затрат на кабель и стоимости работ по его прокладке, по сравнению с общей стоимостью сети составляет до 70% [38]. Отсюда следует, что снижение затрат на строительство и проектирование линий связи хотя бы на один процент даст экономический эффект в миллионы рублей.

В существующих на данный момент алгоритмах построения сетей минимальной стоимости заданной топологии стоимость затрат на прокладку линий связи между узлами телекоммуникационной сети определяется либо экспертным путем, либо не учитывает неоднородность среды, по которой будет прокладываться трасса: предполагается, что стоимость прокладки единицы длины линии связи по всей территории является постоянной, что не соответствует действительности. Стоимость работ по прокладке сети зависит от выбора трассы прокладки [45,46], например, монтаж линии связи по болотистой местности существенно дороже, чем монтаж вдоль автомобильных трасс. Однако в некоторых случаях дешевле проложить короткий кабель по более «дорогой» местности, чем в обход по более «дешевой». Предварительное определение трасс до начала монтажных работ принесет значительную экономию финансовых средств.

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

Цель работы.

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

1) минимизация затрат на соединение узлов телекоммуникационной сети на взвешенной плоскости;

2) минимизация затрат на объединение узлов телекоммуникационной сети на взвешенной плоскости в сеть заданной топологии.

Основные задачи.

В работе поставлены следующие основные задачи:

• исследование существующих способов определения трассы соединения узлов телекоммуникационной сети;

• исследование существующих методов построения минимальных топологий сети;

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

• определение предварительного направления трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

• определение минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

• объединение точек на взвешенной плоскости в минимальную по стоимости сеть заданной топологии.

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

Для решения поставленных задач использован аппарат вычислительной геометрии, теории графов и математического анализа.

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

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

• сформулирована и решена задача определения минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости;

• определено необходимое условие минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости, разделенных произвольной кривой;

• предложены графовые модели для определения направления трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

• предложен алгоритм определения минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

• доказаны метрические свойства минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

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

Достоверность.

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

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

Основным практическим результатом проведенных исследований стала разработка моделей и алгоритмов соединения точек, расположенных произвольно на взвешенной плоскости. Практическое применение разработанных моделей и алгоритмов показало снижение стоимости прокладки линий связи при построении телекоммуникационной сети 25−35%.

Результаты, полученные в диссертационной работе, внедрены и использованы при проектировании трасс линий связи между узлами телекоммуникационной сети в ОАО «Связьэлектромонтаж» (г.Мытищи, Московская обл.), ООО «Ремстроймост» (г. Рязань).

Апробация результатов диссертации.

Результаты, полученные в ходе работы над диссертацией, докладывались на VI Международной школе-семинаре аспирантов, магистров и студентов «Современные информационные технологии», Минск, июнь 2003 г.- 9-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 21−23 апреля 2004 г.- 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 20−22 апреля 2005 г.- VIII Международной школе-семинаре аспирантов, магистров и студентов.

Современные информационные технологии", Минск, июнь 2005 г.- 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 6−8 декабря 2005 г.- Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы», Москва, 14−16 декабря 2005 г.- 39-й научно-технической конференции РГРТА, 30 января — 4 февраля 2006 г.- 11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 19−21 апреля 2006 г.

Публикации.

Основные результаты диссертации опубликованы в 11 работах.

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

.

Диссертация состоит из введения, четырех глав, библиографического списка (90 источников), изложенных на 138 страницах (содержит 6 таблиц, 67 рисунков), и 2 приложений. Общий объем диссертации — 201 страница.

Выводы по четвертой главе.

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

ЗАКЛЮЧЕНИЕ

.

В диссертационной работе разработаны теоретические основы и прикладные методы построения телекоммуникационных сетей заданных топологий на взвешенной плоскости. Решены следующие основные задачи:

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

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

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

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

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

Разработанные в диссертационной работе модели и алгоритмы можно применять при построении новых и расширении существующих сетей, например, некоммерческих научно-образовательных сетей, таких как RUNNet, RBnet, FREEnet, RELARN-IP, RUHEP-Radio-MSU, РОСКОН и др.

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

Показать весь текст

Список литературы

  1. В.Б. Теорема Абеля в задачах и решениях М.: МЦНМО, 2001.- 192 е.: ил.
  2. А.Я. Программирование в C++Builder 5. М.: ЗАО «Издательство БИНОМ», 2000 г. — 1152 е.: ил.
  3. Г. Т. Топология регулярных вычислительных сетей и сред. -М.: Радио и связь, 1985. 192 с.
  4. А.В., Галкин С. В., Зарубин B.C. Методы оптимизации: Учеб. для вузов / Под ред. B.C. Зарубина, А. П. Крищенко. М.: Изд-во МГТУ им. Баумана, 2001.440 е.: ил.
  5. А.Ф., Араманович И. Г. Краткий курс математического анализа.-М.: Наука, 1973.-736 с.
  6. Бет Верити. Кабельные системы: проектирование, монтаж и обслуживание. М.: КУДИЦ-ОБРАЗ, 2004. — 400 е.: ил.
  7. В.М., Рублинецкий В. И., Качко Е. Г. Основы программирования- Ростов н/Д: Феникс, 1998. 368 е.: ил.
  8. В.М., Рублинецкий В. И., Сигалов B.JI. Точное решение задачи строительной трассировки ДАН УССР, 1988, № 6, сер. «А», с. 67−70.
  9. Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.- 120 е.: ил.
  10. Дейтел Харви, Дейтел Пол. Как программировать на С++: Пер. с англ. -М.: ЗАО «Издательство БИНОМ», 1999. 1024 е.: ил.
  11. М.Ерзин А. И. Задачи проектирования оптимальной сети сбора нефти // Труды школы-семинара «Физика нефтяного пласта», Новосибирск, 2002. -с. 101−104.
  12. Инструкция по проектированию линейно-кабельных сооружений связи -М.: Гипросвязь, 1993.
  13. Ч., Рейсдорф К. Borland C++Builder 5. Энциклопедия программиста: Пер. с англ. К.: Издательство «ДиаСофт», 2001. — 944 е.: ил.
  14. А.В., Мелихов А. Н., Курейчик В. М., Гузик В. Ф., Калашников В. А. Автоматизация проектирования вычислительных структур. Издательство Ростовского университета, 1983. 224с.: ил.
  15. В.Г. Математическое программирование 2-е изд., перераб. -М.: Наука, 1980. — 256 е.: ил.
  16. В.М., Рублинецкий В. И. О процедуре «иди в ближайший» в задаче коммивояжера. Выч. мат. и выч. техн., Харьков, 1973, вып. IV, с.40−41.
  17. Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. — 720 е.: ил.
  18. Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2005. -1296 е.: ил.
  19. Г. и Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1970.- 720 с.
  20. В.П., Курейчик В. М., Норенков И. П. Теоретические основы САПР. Учебник для ВУЗов М.: «Энергоатомиздат», 1987 г. — 400с.: ил.
  21. В.П., Митрошин А. А., Читаев И. В. Алгоритм проектирования кластерной системы узлов телекоммуникационной сети // Известия Белорусской инженерной академии. Минск, 2003 г, № 1(15)/1. с.255−259.
  22. Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.
  23. П.С. Курс истории физики. М.: Просвещение, 1982. — 448 с.
  24. М.В. Компьютерные сети: практика построения. 2-е изд. -СПб.: Питер, 2003. — 462 е.: ил.
  25. ЗЬЛипский В. Комбинаторика для программистов М.: Мир, 1988 — 319 с.
  26. Дж., Мурти К., Суини Д., Кэрел К. Алгоритм решения задачи коммивояжера. Экономика и мат. методы, 1965, № 1, с. 13−22.
  27. Дж. Основы современных алгоритмов. 2-е дополненное издание — М.: Техносфера, 2004. — 368 е.: ил.
  28. Зб.Оре О. Теория графов. М.: Наука, 1968. 352 е.: ил.
  29. М., Синклер Р. Б. Проектирование и внедрение компьютерных сетей. Учебный курс. 2-е изд., перераб. и доп.: Пер. с англ. — СПб.: БХВ-Петербург, 2004. — 752 е.: ил.
  30. В.К., Кауль С. Б., Нечепуренко М. И. и др. Методы оптимизации структур зоновых сетей связи. Отв. ред. Алексеев А. С. Новосибирск, 1983.-181 с.
  31. Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. — 478 с.
  32. Р.К. Кратчайшие связывающие сети и некоторые обобщения. -Кибернетич. сб., М.: Мир, 1961, вып. 2, с. 95−107.
  33. В.В. Об одном эвристическом параллельном алгоритме решения задачи Штейнера. Изв. вузов, М.: Приборостроение, 1997. — с. 53−60.
  34. Техническое зрение роботов / Под ред. Пью А.- Пер. с англ. Миронова Д.Ф.- Под ред. Катыса Г. П.- М.: Машиностроение, 1987. 320 е.: ил.
  35. Руководство по строительству линейных сооружений магистральных и внутризоновых кабельных линий связи М.: «Радио и связь», 1986.
  36. А.Б. Проектирование и расчет структурированных кабельных систем и их компонентов. М.: Компания АйТи- ДМК Пресс, 2005. — 416 е.: ил.
  37. Структурированные кабельные системы / Семенов А. Б., Стрижаков С. К., Сунчелей И. Р. 5-е изд. — М.: Компания АйТи- ДМК Пресс, 2004. -640+16 е.: ил.
  38. И.Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учебное пособие. Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 е.: ил.
  39. А.В. Обзор алгоритмов построения триангуляции Делоне. // Вычислительные методы и программирование. Т. З, 2002. с. 14−39.
  40. В.А. Примеры метрических пространств. М.: МЦНМО, 2002. -24с.: ил.
  41. Б. Я. Яковлев С.А. Построение сетей интегрального обслуживания. Л.: Машиностроение. Ленингр. отд-ние, 1990. — 332 е.: ил.
  42. Компьютерные сети. 4-е издание / Таненбаум Э. СПб.: Питер, 2003. -992 е.: ил. — (Серия «Классика computer science»)
  43. А.А., Фоменко А. Т. Элементы геометрии и топологии минимальных поверхностей. М., Наука, 1991. 176 е.: ил.
  44. Р. Введение в теорию графов. М.: Мир, 1977. — 207 с.
  45. Фень Юань Программирование графики для Windows. СПб.: Питер, 2002. — 1072 е.: ил.
  46. Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. М.: Мир, 1984.-496 е.: ил.
  47. П. С++: учебный курс СПб: ЗАО «Издательство «Питер», 1999. — 528 с: ил.
  48. Ф. Теория графов. М.: Мир, 1973. — 300 с.
  49. Ф., Пальмер Э. Перечисление графов. М.: Мир, 1977. — 324 с.
  50. Д., Баттерфилд Д., Сворт Б. C++Builder 5. Руководство разработчика, том 1. Основы: Пер. с англ. М.: Издательский дом «Вильяме», 2001. — 880 е.: ил.
  51. Д., Баттерфилд Д., Сворт Б. C++Builder 5. Руководство разработчика, том 2. Сложные вопросы программирования: Пер. с англ. -М.: Издательский дом «Вильяме», 2001. 832 е.: ил.
  52. И.В., Жошкин А. С. Разработка программного обеспечения соединения двух точек на взвешенной дискретной плоскости // Новыеинформационные технологии, Межвузовский сборник научных трудов, Рязань, 2006 г. с. 123−126.
  53. И.В. Построение линии связи минимальной стоимости между двумя узлами на взвешенных регионах, разделенных прямыми линиями // Новые информационные технологии, Межвузовский сборник научных трудов, Рязань, 2006 г. с. 120−123.
  54. Петербурга- Ряз. филиал Санкт-Петербургской академии управления и экономики. Рязань, 2005 г., с. 79−80.
  55. А., Буч Г., Рамбо Дж. Унифицированный процесс разработки программного обеспечения. СПб.: Питер, 2002. — 496 е.: ил.
  56. , R. S. 1989 (September). Construction of optimal-path maps for homogeneous-cost-region path-planning problems. Ph.D. thesis, Dept. of Computer Science, U.S. Naval Postgraduate School, Monterey, CA, USA.
  57. Chung S., Condon A. Parallel implementation of Boruvka’s minimum spanning tree algorithm. In Proc. 10th Int’l Parallel Processing Symp. (IPPS'96), pages 302−315, April 1996.
  58. Chazelle B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. Journal of the ACM, 47 (2000), 1028−1047.
  59. Dixon В., Rauch M. and Tarjan R. E. 1992. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21, 1184 -1192.
  60. Hakimi. S. L. Steiner’s Problem in Graphs and Its Implications. // Networks. 1971. V. l.P. 113−133.
  61. Jeff Erickson. Minimum spanning trees. Lecture notes: Fall 2002 — CS 373: Combinatorial Algorithms.
  62. Graham R. L. and Hell P. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1): 43−57, 1985.
  63. Kindl R., Rowe C. and Shing Man-Tak A Stochastic Approach to the Weighted-Region Problem: Design and Testing of a Path Annealing Algorithm, Monterey, 1991.
  64. Lucena A. and Beasley J. E. A Branch and Cut Algorithm for the Steiner Problem in Graphs. // Networks. 1998. V. 31. P. 39 59.
  65. Melzak Z.A. On the problem of Steiner //Canad. Math. Bull. 1960. V.4 P. 143 148
  66. Mitchell J. S. B. and Keirsey D. Planning Strategic Paths Through Variable Terrain Data, SPIE, Applications of Artificial Intelligence, volume 485, 172 179, 1984.
  67. Mitchell J. S. B. and Papadimitriou С. H. The weighted region problem, to appear in Journal of the ACM, 1990.
  68. Parodi A. M. Multi-goal real-time global path planning for an autonomous land vehicle using a high-speed graph search processor, Proceedings of the 1985 IEEE Conference on Robotics and Automation, 161−167, 1985.
  69. Rowe N. C. Roads, rivers, and rocks: optimal two-dimensional route planning around linear features for a mobile agent. To appear in International Journal of Robotics Research, 1990.
  70. Rowe N. C. and Richbourg R. F. An Efficient Snell’s-Law Method for Optimal-Path Planning Across Multiple Homogeneous-Cost Regions, accepted to International Journal of Robotics Research, to appear 1990.
  71. Rowe N. C. and Richbourg R. F. An efficient Snell’s-law method for optimal-path planning across multiple two-dimensional irregular homogeneous-cost regions. To appear in International Journal of Robotics Research, 1990.
  72. Rowe N. C. and Ross R. S. Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects. Accepted to IEEE Transactions on Robotics and Automation, January 1990.
  73. Warme D.M. Spanning Trees in Hypergraphs with Applications to Steiner Trees. // Ph.D. Thesis, Computer Science Dept., The University of Virginia, 1998.
Заполнить форму текущей работой

Сессия? Спокойно!