ISSN 1991-3087
Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

НА ГЛАВНУЮ

Алгоритм маршрутизации для систем связи с динамической топологией сети

 

Сорокин Александр Александрович,

аспирант Астраханского государственного технического университета.

 

В период с 1998 по 1999 годы Satellite Working Group были сформулированы базовые рекомендации по разработке систем спутниковой связи. В одной из рекомендаций была поставлена задача интеграции систем космической связи с системами наземной связи при приоритетном использовании систем наземной связи [1]. Примером интеграции космических систем связи с наземными является развитие VSAT технологии. Рост объемов передаваемой информации повлек проблемы ограничения пропускной способности систем космической связи [2] и экологического ущерба от запусков ракет-носителей.

Одной из групп-потребителей услуг космической связи являются удаленные от наземных телекоммуникационных систем транспортные объекты (самолеты, корабли, поезда). Системным свойством данной категории объектов является установленные маршруты и графики перемещения. Для снижения нагрузки на системы спутниковой связи предлагаются способы построения систем передачи информации непосредственно между транспортными объектами [3]. Построение системы связи достигается за счет расположения сетевого оборудования на удаленных транспортных объектах. Таким образом, система связи приобретает динамическую топологию. Динамичность топологии вызывает трудности маршрутизации. Трудности маршрутизации вызывают ограничения скорости передачи информации.

Целью работы является разработка алгоритма построения таблиц маршрутизации для наземных высокоскоростных систем связи с динамической топологией сети (ДТС).

Для описания топологии систем связи с ДТС используется методы теории графов. При помощи теории графов топологии сети преобразуется в матричную форму. На основании полученных матриц производится расчет таблиц маршрутизации.

В системах спутниковой связи, применяются модели, основанные на периодическом повторении топологии группировки спутников. К классу данных моделей относится модель дискретного времени (МДВ). В МДВ изменения топологии сети представляются как периодически повторяющаяся последовательность S «снимков» топологии, разделенных интервалом длительности , где T – период повторения топологических состояний группировки. Каждому «снимку» сопоставляется граф , где  - постоянный набор узлов, а  набор каналов связи. Для конечного множества графов , повторяющихся, за период T, предварительно рассчитываются таблицы маршрутизации (ТМ). ТМ рассылаются по спутникам и используются в нужный момент времени . Предварительный расчет ТМ позволяет организовать высокоскоростные (более 2 Мбит/с) каналы связи [4].

Рассмотрим ограничения МДВ. Пусть существует конечное множество вершин  и ребер . Тогда справедливо, что периодически повторяющиеся множества графов будут одинаковы: , где N – порядковый номер периода повторения топологии. Если в течении T изменяется состав множества узлов , то получившееся новое множество . Тогда для периода повторения T множества графов между собой не равны . Таким образом, фактический период повторения группировки  и число снимков топологии . Тогда шаг  выражается неопределенным соотношением:

,                                                                                                     (1)

что указывает на невозможность определения длительности и количества интервалов  в МДВ при изменении состава множества узлов .

Для построения моделей локальных систем связи с ДТС (Ad hoc сети) нашли применение методы теории случайных графов [5]. Согласно моделей, разработанных с использованием теории случайных графов множество узлов сети  и множество ребер  образуют граф . При переходе графа  из состояния  в состояние n равновероятно появление любого графа  из множества возможных графов . При увеличении количества узлов  вероятность появления, какого либо графа  из множества графов  стремится к нулю . Для системы связи с ДТС это означает, что вероятность появления маршрутов, предварительно рассчитанных по этой модели, стремится к нулю. Отличительными особенностями моделей построенных с использованием случайных графов являются зависимости вероятности появления ребра между парой вершин от условий распространения сигнала.

Отсутствие условий определения однозначного перехода графа  из состояния  в состояние n привело к системному недостатку протоколов маршрутизации для Ad hoc сетей. Протоколы маршрутизации для данного класса систем могут только реагировать на изменения топологии и рассчитывать ТМ с определенным запаздыванием. Как показало моделирование в программном комплексе NS-2 время запаздывания превышает 0,3 сек при 20 узлах и скорости передачи информации в каналах между узлами 128 кбит/с для реактивных протоколов и 50 кбит/с для проактивных протоколов.

При увеличении зоны покрытия систем наземной связи за счет обслуживания транспортных объектов необходима организация связи между этими объектами и наземными системами передачи информации через высокоскоростные каналы. Пригодность высокоскоростных каналов нормируется параметрами качества, одним из которых является коэффициент неготовности . Следовательно, вероятность готовности канала должна находиться в пределах (). 

При обращении к модели это означает, что при переходе реального графа  в состояние  вероятность совпадения всех маршрутов в графе  с аналогичными маршрутами, в предварительно рассчитанном графе , должна быть не ниже 98,5 %. При большом числе узлов и ребер (), это противоречит принципу моделей построенных с использованием теории случайных графов.

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

Разрабатываемая математическая модель системы связи с ДТС должна: позволять представить непрерывные изменения топологии в виде последовательности стационарных состояний, описываемых при помощи графов:

 и  и                 (2)

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

                                                                  (3)

 прогнозировать будущее состояние топологии сети на определенное время – время прогноза.

                                                                                                        (4)

где  момент времени в течении которого считается, что параметры системы не ухудшаются;  граф сети в момент  с конечным множеством вершин V (подвижные объекты) и множеством ребер E (линии связи).  - время прогнозируемого состояния системы связи с ДТС.

С учетом критериев (2,3,4) основными входными параметрами модели является статистика перемещения транспортных объектов по заданным маршрутам и технические характеристики оборудования (пропускная способность, дальность установления соединения). На выходе модели получается последовательность таблиц маршрутизации. Структурная схема алгоритма предварительного расчета ТМ для систем связи с ДТС показана на рис. 1.

 

Рис. 1. Последовательность операций предварительного расчета таблиц маршрутизации.

 

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

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

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

 

Литература

 

1.                  Горностаев Ю.М., Соколов В.В., Невдяев Л.М. Перспективные спутниковые системы связи.– М.: «Горячая линия-Телеком» МЦНТИ, 2000.–132 с.

2.                  Кантор Л.Я. Расцвет и кризис спутниковой связи / Электросвязь, №7, 2007.- С. 19-23.

3.                  Способ мобильной связи между подвижными и стационарными объектами. Заявка на патент №2006127761/09 от 31.07.2006 / Дмитриев В.Н., Сорокин А.А.

4.                  M. Werner, C. Delucchi, H.-J. V¨ogel, G. Maral, and J.-J. De Ridder. ATM-based routing in LEO/MEO satellite networks with intersatellite links. IEEE Journal on Selected Areas in Communications, 15 (1):69–82, Jan. 1997.

5.                  Ramin Hekmat Ad-hoc networks: Fundamental properties and network topologies; Technology, The Netherlands and Rhyzen Information and Consulting Services, Zoetermeer, the Netherlands 2006. – 154 p.

 

Поступила в редакцию 27.06.2008 г.

2006-2019 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.