автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгоритмы структурной оптимизации и методы анализа информационных процессов в современных телекоммуникационных системах

На правах рукописи

485Ь£ ю

Соловьев Антон Юрьевич

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

Специальность 05.13.17. - «Теоретические основы информатики»

автореферат

диссертации на соискание ученой степени кандидата технических наук

2 4 ОЕВ 2011

Воронеж-2011

4856216

Работа выполнена в Старооскольском технологическом институте (филиале) Национального исследовательского технологического университета Московского института стали и сплавов.

Научный руководитель: доктор физико-математических наук,

профессор

Семенов Михаил Евгеньевич

Официальные оппоненты: доктор технических наук,

профессор

Леденева Татьяна Михайловна

доктор технических наук, профессор

Буховец Алексей Георгиевич

Ведущая организация: Институт точной механики и

вычислительной техники им. С. А. Лебедева РАН

Защита состоится « (О » АгоуоТО. 2011 г. в часовЗ^минут на заседании диссертационного совета Д 212.038.24 при Воронежском государственном университете по адресу: 394006, г. Воронеж, ВГУ, Университетская пл., 1, зал конференций.

С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного университета.

Автореферат разослан « ^ » (Ф2л) КДЛ^ 2011 г,

Ученый секретарь

диссертационного совета Д 212.038.24 Чеботарев А.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Свойства временных рядов самоподобного трафика изучались в работах Городецкого А.Я., Заборовского B.C., Шелухина О.И., Петрова В.В., но анализируемый в этих работах трафик использовался с очень малым уровнем агрегирования, и прогноз совершался только на несколько секунд или минут вперед, что достаточно, например, для динамичного распределения полосы пропускания, но получить общую картину поведения пользовательской активности и сделать прогноз загрузки устройств хотя бы на час вперед невозможно. При этом исследуемые временные ряды в реальном времени сильно зашумлены и не дают целостной картины. Отметим также, что анализ наличия свойств самоподобия у временных рядов с дискретным временем снятия не проводился вообще. Кроме того, за прошедшие годы, характер информационного трафика, а так же его структура кардинально изменились, и ранние исследования могут оказаться некорректными в настоящее время.

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

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

Достижение цели потребовало решения следующих задач:

3

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

- анализ временных рядов трафика данных с дискретным временем снятия данных с целью выявления свойств самоподобия и построение на его основе прогнозных моделей;

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

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

Методы исследования. В работе использованы методы и средства системного анализа, теории графов, теории эвристических алгоритмов, имитационного моделирования, теории оптимизации, теории вероятности и математической статистики.

Научная новизна и значимость результатов диссертации:

В работе впервые разработаны:

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

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

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

Экспериментально выявлено преимущество метода сингулярно-спектрального анализа («Гусеница») над семейством традиционных авторегрессионных моделей (ЛИИМА) при прогнозировании временных рядов трафика телекоммуникационных систем с дискретным временем снятия данных, количественно выраженное в меньшей ошибке прогноза и большем проценте правильного распознавания направления эволюции временных рядов, описывающих информационный трафик.

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

Соответствие диссертации паспорту научной специальности.

Диссертационная работа соответствует паспорту специальности 05.13.17 - «Теоретические основы информатики» (технические науки), а именно:

п. 1 «Исследование, в том числе, с помощью средств вычислительной техники, информационных процессов, информационных потребностей коллективных и индивидуальных пользователей»;

п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»;

п. 16 «Общие принципы организации телекоммуникационных систем и оценки их эффективности. Разработка научных принципов организации информационных служб по отраслям народного хозяйства. Изучение социально-экономических аспектов информатизации и компьютеризации общества».

На защиту выносятся:

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

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

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

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

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

Апробация работы. Материалы диссертационной работы докладывались и обсуждались на международных и Всероссийских конференциях: И Всероссийской научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2010); VII Всероссийской научно-технической конференции «Приоритетные направления развития науки и технологий» (Тула, 2010); Международной научно-практической конференции «Образование, наука, производство и управление» (Старый Оскол, 2008-2009). Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2010); VII Всероссийской научно-практической школы-конференции «Управление большими системами» (Пермь, 2010).

Публикации. По результатам исследования опубликовано 11 печатных работ, в том числе 4 без соавторов; 2 в изданиях, рекомендованных ВАК РФ для публикации основных результатов диссертационных исследований.

Личный вклад автора в работах, опубликованных в соавторстве, состоит: в [I] - подготовка и организация эксперимента с целью выявления самоподобных свойств трафика; в [2,4,5] - разработка и реализация алгоритма на основе метода муравьиных колоний; в [3] - формулировка задачи в линейно-

5

целочисленном виде; в [8] - оценка возможности применения авторегрессионных моделей для анализа трафика данных; в [10] - обобщенный алгоритм структурной оптимизации телекоммуникационных систем.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Q{S) = ZQk ->min, (1)

Sc J, S*0, (2)

где Q^ - затраты на работы, на прокладку кабеля, на установку промежуточных

устройств и т.д. Согласно постановке, имея множество мест возможной установки промежуточных устройств J е{1,...,ш}, из всех возможных множеств формирующих структуру системы необходимо выбрать такое множество SczJ, чтобы суммарная функция затрат была минимальной и все абонентские устройства, принадлежащие множеству I е {1,...,«}, были подключены.

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

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

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

Обозначим через I = (1,...,п) - множество абонентских устройств, каждое из которых должно быть подключено только к одному промежуточному устройству; ./ = (1,..., т) - множество мест, в которых можно разместить промежуточные устройства; Ъ„ >0,ге/,7еУ - стоимость подключения у-ого промежуточного устройства к г'-му абонентскому устройству. Стоимость прямо пропорциональна стоимости укладки кабеля, стоимости кабеля и расстоянию между промежуточным и абонентским устройствами;^. >0,_/е 7 - емкость промежуточного устройства, выраженная в допустимом количестве подключаемых к нему абонентских устройств; с.>0,_/еУ - стоимость установки промежуточного устройства на _/-м месте-кандидате; е{0,1} принимает свои значепия в

зависимости от того, к какому промежуточному устройству подключено текущее абонентское устройство; у. е {0,1} принимает значения в зависимости от

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

Задача с ограниченным числом подключаемых абонентских устройств. Эта задача формализуется следующим образом:

IIЬх+^су

ЫГ ¡eJ У У jej J J

->min, (3)

Ix <q у jeJ. (4)

iel V J J

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

Задача с ограниченным числом промежуточных устройств. Имея множество мест возможной установки промежуточных устройств Je{l,...,m}, из всех возможных множеств, формирующих структуру системы, необходимо выбрать такое множество S с J, чтобы суммарная функция затрат была минимальной и все абонентские устройства, принадлежащие множеству ie{l,...,n}, были подключены, но при этом число промежуточных устройств не должно превышать заданного числа р. Теперь, задачу можно сформулировать так

Хштб.. —» min, (5)

iel У

SczJ, S*0,±y.<p. (6)

JeJ J

Для обеих задач выполняется ограничение

п т т

II*,,=«,I*7=Ue/- (7)

Ш jsJ У jeJ У

Ограничения (7) гарантируют, что все абонентские устройства будут подключены, и абонентское устройство может быть подключено только к одному промежуточному устройству.

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

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

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

Перечислим основные отличия разработанного алгоритма от классического муравьиного алгоритма:

■ 1 Гйииг^да^ц-л« |

*Г

»луравьез

Коиеу

Ла

¡^ор маршрут к | | сиечка его > стсямосга I

т—

К^гр^-рут 1к ремЬШёХ.

«Процесс сЪ^пенеч ) фероионэ

1 '

Н*т

Г" •• Ч^е^вФс^мумэ,''' ^ •

. ^ Г'рзсчт ¿шчс-сг&а

1 г.. фзрсмсизО ^ {н^^смого6?до'.««ка

1 ; ^ кэ маршрут *

Рис.1 Блок-схема алгоритмов для задач размещения

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

2. Формула оценки количества феромона имеет вид

'б

Ат.к =

V* . (8)

0,якж

здесь А гА количество наносимого виртуального феромона на итерации муравья к; <2 - регулируемый параметр, значение которого выбирают одного порядка с длиной оптимального маршрута; ^ - текущее оптимальное решение; К^ -

стоимость маршрута выбранным к-ым муравьем-агентом.

В отличие от классического муравьиного алгоритма в (8) введен критерий оценки количества наносимого феромона. Если стоимость маршрута к-го муравья больше текущего значения целевой функции, то количество наносимого феромона равно пулю. Кроме того, иначе определяется сама формула расчета количества наносимого феромона. Отметим, что первоначально, следуя идеи классического муравьиного алгоритма, количество наносимого феромона рассчитывалось по формуле

Лг/=|-, (9)

ч

где есть расстояние между ¡'-ым абонентским устройством и у'-ым промежуточным устройством, то есть параметр был заменен на- стоимость

маршрута к-го муравья.

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

-г .а /

'IV' <10)

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

г «Ц.Р

Р..= 1} 4 д, (11)

где ц» - величина, обратная расстоянию, или так называемая, видимость муравья, а и Р - два регулируемых параметра, задающие веса следа феромона и видимости при выборе маршрута. Как видим из (10), в формуле вероятности были убраны параметры г]у и Д. В самом классическом алгоритме данные параметры играли косвенную роль в минимизации расстояния, и их включение было необходимо. Для данной задачи эти параметры не являются обязательны-

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

Такие этапы, как нанесение количества феромона и процедура испарения феромона, остались без изменений. Обозначим коэффициент испарения феромона через р е [0,1]. Тогда правило обновления феромона примет вид

-rfi-p).

(12)

.i быбср m's^rir/' и ЛфИЗйтСЮ» CTpWfypW eel* j

, вбамекгсс* и ^омелугочмых ; __' _ ____'

iPBKU'«.'---^ >« ryiwpim :

Ш^-^ребуетгя г.-/"' ■

. .. ' w'SoriiP....... I

[ bp^oaiiu^ro ATeTOqsi н его i

: Да

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

Кольцевание промежуточных устройств. Зачастую, при построении Из^м \ телекоммуникационных систем

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

например, такие как метод ветвей и границ. Так как тот же метод ветвей и границ является вариацией полного перебора с отсевом подмножеств

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

j | On^iM .1? WVJTrxb'«

i 1" »^'{ГОМ__:

L

; vtflT ■

I JSffLL'&WWfl

...

Да.

. A. .. '"fpsSya'Tcn

¡: Прз«г*есп» юел ws po.

Tofcwoe

Йет.

-•V. yc^pyjwi,..^--'

ЖГ

.- С .'Kiwu;;

Рис.2 Блок-схема обобщенного алгоритма для генетического и муравьиного алгоритмов.

Разделение абонентских устройств на группы. При начальном построении телекоммуникационной системы и при большом количестве предполагаемых подключений абонентских устройств удобно разбить их на группы, объединенные по тем или иным признакам. В данном случае главным признаком будет расстояние между объектами. То есть, фактически задача разбиения на группы есть не что иное, как задача кластеризации. Для решения поставленной задачи использовались алгоритмы кластеризации k-means и fuzzy c-means.

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

На рис. 2 приведена блок-схема обобщенного алгоритма. Кластеризация и кольцевание применяется только при необходимости.

В Главе 3 проведено экспериментальное исследование временных рядов информационного трафика на предмет самоподобия и выбор моделей наиболее подходящих для анализа временных рядов трафика данных.

Рассмотрим стационарный случайный процесс дискретного аргумента

(времени) Х = (Х]3Х2,...,Х(). Обозначим через Х{т) ={X(f],х(т\...,х{т))

усредненный по блокам длины m процесс X, компоненты которого определяются равенством

Х№=-(Х „ п,.+...+Х X m,tsN. (13)

t m m(l-l)+l mr

Обозначим через г (к) и гт(к) коэффициенты автокорреляции рядов Хи соответственно.

Процесс X является строго самоподобным, если выполняется условие

гт{к) = г(к\те{ 2,3,...}, (14)

т.е. процесс не отличим от процесса X как минимум в отношении статистических характеристик до второго порядка.

Процесс X называется асимптотически самоподобным с параметром Хэрста H, если

lim r(k) = g(k),keN, (15)

BÎ-КЮ tri

где g(k) = ^[(k+X)^H -2k2H + (k-ï)2-H] - коэффициент автокорреляции строго

самоподобного процесса.

Типичные реализации самоподобного процесса визуально похожи независимо от масштаба времени, на котором они рассматриваются. Это означает, что наблюдается сходство статистических свойств. Параметр И, называемый показатель Хэрста, является индикатором самоподобия случайного процесса, характеризующий свойство долговременной зависимости.

Для выявления свойств самоподобия и доштельной памяти трафика телекоммуникационных систем с дискретным временем снятия данных были проведены экспериментальные исследования на данных, полученных при мониторинге узлов интернет-провайдера ООО «Радиотелеком» (г. Старый Оскол). Данные снимались сразу в трех точках системы. Данные собирались по протоколу SNMP с использованием системы мониторинга Zabbix с интервалом в одну и пять минут. Полученные данные представлены временным рядом о загрузке узла в течение суток, начиная с 0-00 часов и кончая 0-00 часов следующего дня. Съем данных осуществлялся три раза.

п

Как правило, для определения свойства самоподобия временные ряды исследуются на поведение автокорреляционной функции (АКФ) и на значение показателя Хэрста. Медленно убывающая по степенному закон)' АКФ ряда, а так же значение показателя Хэрста в пределах от 0.5 до 1, как правило, свидетельствуют о наличии у ряда свойства длительной памяти и самоподобия. На рис.3 показаны АКФ рядов в одной из точек съема информации. Кроме того, уже при небольших т, значения гт (к) стабилизируются и отличаются от г (к) статистически незначимо.

Рис.3 АКФ для реализаций трафика в одной из точек съема информации.

Далее для всех полученных реализаций был рассчитан показатель Хэрста. Расчет показателя проводился по трем различным методам: метод периодограмм, оценка Витла и метод изменения дисперсий. Расчет показал, что значение показателя Хэрста для всех реализаций достаточно велико и изменяется от 0,8 до 1. На основе расчетов показателя Хэрста, а так же выявленного медленного убывания АКФ, можно сделать вывод, что для временных рядов трафика данных с дискретным временем снятия данных характерно наличие свойств длительной памяти и самоподобия.

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

В работе рассмотрено две модели анализа временных рядов, ориентированных на учет самоподобия.

Семейство авторегрессионных моделей, имеющих вид

а(В)Х{=гп, п>0, (16)

где Х( - некоторый случайный процесс; а{В)-Л-а1В-а^В^-...-а^В^; В -

лаговый оператор, определяемый как = у) белый шум.

Так как временные ряды трафика данных обладают как кратковременной, так и долговременной памятью, то модель А1ШМА (р,с1,д) (модель фрактальной авторегрессии проинтегрированного скользящего среднего), является наиболее подходящей из всего семейства авторегрессионных моделей для анализа временных рядов трафика данных. В случае когда 0 < < 0,5, А1ШМА (рДд) -процесс проявляет свойство долговременной зависимости. Параметры р и <7 дают возможность гибкого моделирования кратковременных характеристик процесса.

Модель АШЧМА (р,с!,д) определяется соотношением

а(В)(1-В)с1Х(=р(В)гг (17)

где /3(В)=\-Р{В + р2В2 +...+.

Параметрическая оценка параметров модели включает в себя оценку р, с/ и Как правило, оценка параметра с1 определяется методами 11/8 статистики или анализом изменения дисперсий, при этом существует взаимосвязь коэффициента с/ и параметра Хэрста Н в виде

</ = Я- 0,5. (18)

Метод сингулярно-спектрального анализа (метод «Гусеница») состоит из двух дополняющих друг друга этапов: разложения (вложение и сингулярное разложение) и восстановления (группировка и восстановление).

Рассмотрим ряд /г = (/0,...,/Л,_]), N>2, длины N. Поясним некоторые

особенности этапов алгоритма.

Шаг. 1. Вложение. Пусть Ь - некоторое целое число (длина окна), \<Ь<М. Процедура вложения образует К = Ы-Ь-1 векторов вложения

г?'1****- <19>

имеющих размерность Ь, после этого строится траекторная матрица X, состоящая из векторов вложения в качестве столбцов.

Шаг 2. Сингулярное разложение. На этом шаге происходит сингулярное разложение траекторной матрицы. Обозначим собственные числа мат-

т

рицы 8 = XX и собственные вектора матрицы в. Тогда, если обо-

значить V. = Х^и. / , то сингулярное разложение матрицы примет вид:

Х = Х}+....+Х^ 1 = 1,(20) где . Набор и^, кТ | будем называть 1-й собственной трой-

кой сингулярного разложения.

Шаг 3. Группировка. На основе разложения (20) процедура группировки делит все множество индексов {1,...,£/} на пг непересекающихся подмножеств /р...,//и, тогда результирующая матрица соответствующая группе I имеет вид

Х = ХТ + ...+х, . (21)

1 т

На данном этапе происходит отбор из общего множества всех собственных троек, тех троек, которые войдут в восстановление ряда.

Шаг 4. Восстановление. На последнем этапе матрица сгруппированных собственных троек (21) переводится в новый ряд длины //при помощи диагонально усреднения. Применяя диагональное усреднение к результирующим

матрицам Х^ , получаем ряды , и, следовательно, исход-

ный ряд ^ = (/ ,...,/ ,) раскладывается в сумму рядов

/=£/(*), tf >2 . (22)

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

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

Реализация полученных муравьиных алгоритмов. Алгоритм муравьиной колонии для обеих задач структурной оптимизации, а именно с ограничением по мощности и с ограничением промежуточных устройств был реализован в среде AnyLogic. Реализация алгоритма проводилась на персональной ЭВМ под управлением операционной системы Windows ХР SP3 со следующей конфигурацией: CPU: Intel Core 2 Duo E2200 2,2 Ghz; ОЗУ: 2 Gb.

Наиболее важными параметрами в алгоритме муравьиной колонии помимо числа муравьев, являются а, ß, р. Параметры а и ß отвечают за веса следа феромона, тогда как р отвечает за скорость испарения феромона. Неверный выбор ключевых параметров может привести к слишком быстрому вырождению алгоритма и получению субоптимального решения. Увеличение или уменьшение параметра р, так же может повлиять на результат работы алгоритма. Излишне большое значение также может привести к получению одного субоптимального решения. При тестировании алгоритма были выработаны рекомендации по выбору значений ключевых параметров. Число муравьев-агентов должно изменяться в пределах от 40 до 60, параметры а и ß должны быть равными соответственно 0,5 и 3, параметр р - 0,12. Именно при использовании таких значений удалось добиться наилучших результатов работы алгоритма в поиске оптимального решения. Для каждой из задач размещения помимо алгоритма муравьиных колоний был реализован генетический алгоритм (GA). Алгоритмы тестировались на матрицах одинаковых размерностей, сгенерированных случайным образом. Координаты точек расположения промежуточных устройств и абонентских были идентичны для обоих алгоритмов.

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

В табл. 1-2 приведены результаты работ обоих алгоритмов для обеих задач. Здесь т — число возможных мест установки промежуточных устройств, п — число абонентских устройств, р - максимальное возможное число промежу-

точных устройств, которые можно установить, ц - емкость промежуточного устройства.

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

Таблица 1 .Сравнительная характеристика для задачи с ограничением подключаемых

абонентских устройств

п m Я Целевая функция Время, сек

Муравьиный алгоритм Генетический алгоритм Муравьиный алгоритм Генетический алгоритм

20 15 3 1297.307 1297.307 0,07 0,08

20 20 3 1345.097 1345.097 1,02 1,06

50 20 3 3707.201 3824.268 15,14 36,43

70 30 4 4629.368 4849.276 20,02 114,47

100 50 4 5240.651 5371.423 25,97 151,79

200 60 4 17040.116 19574.281 37,45 202,17

300 80 5 25867.954 26033.17 40,39 231,68

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

устройств.

m п Р Целевая >ункция Время, сек

Муравьиный алгоритм Генетический алгоритм Муравьиный алгоритм Генетический алгоритм

50 50 5 4234.961 4452.086 6,31 10,18

60 60 5 4924.604 5049.322 8,52 16,39

80 80 5 7034.218 7215.051 23,95 40,54

90 90 5 7875.932 8183.22 29,67 48,75

100 100 10 6261.307 6571.38 37,92 86,09

110 110 10 6870.509 6979.492 44,55 112,11

130 130 10 8132.323 8406.671 62,94 153,72

140 140 10 8643.922 9355.775 66,39 184,63

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

Прогнозирование временных рядов. Для проверки возможности прогнозирования были выбраны два временных ряда (в дальнейшем ряд «А» и ряд «В»), характеризующие загрузку каналов передачи данных. Данные для экспериментального прогнозирования были получены также путем мониторинга каналов передачи данных интернет-провайдера ООО «Радиотелеком» по протоколу SNMP. Полученные временные ряды содержали динамику изменения загрузки каналов связи в течение суток. Прогнозирование велось на трех участках каждого ряда длиной по 130 значений

Прогноз делался на 12 шагов вперед, что эквивалентно одному часу. Прогнозирование осуществлялось обоими методами, рассмотренными ранее. На рис. 4 изображен пример прогноза, полученного для одного из участков ряда «В» методом «Гусеница» и моделью ARFIMA(p,ii^).

| у -----------------------------Г......;•-•■.........—.....------—.....-.........

1 2 * 4 1]ё| ямпша* ' 10 " П I 12 3 * л? « Г <4* Ю Н 12

—-Прогко'; — -Исходный | -—Прогк") — ЧЬлдкып

Рис.4 Пример прогноза участка ряда В, слева метод «Гусеница», справа Л1ШМА(/».(<</) При анализе результатов прогнозирования, было отмечено, что метод «Гусеница» справился с поставленной задачей гораздо лучше, нежели модель АГШМА {р,<1,<1). В некоторых случаях значения прогноза по методу «Гусеница» гораздо ближе к действительным, нежели у модели АЯИМА (рЛд)- При этом во всех случаях, методом «Гусеница» более успешно угадано направление движения ряда, тогда как модель АЬШМА (рАд) не всегда показывает совпадения направления движения.

Следует отметить, что при использовании модели А1ШМА (р,с/,д), динамика изменения параметра с1 вкладывается в интервал, ограничивающий параметр Хэрста, при котором ряд обладает свойством самоподобия. Это подтверждает наличие свойств самоподобия у полученных временных рядов, а так же правильный выбор модели А№1МА (рЛу) из всего семейства авторегрессионных моделей. В табл. 3 представлены ошибки прогноза и процент угадывания направления движения для обеих моделей.

Таблица 3. Ошибка прогноза и процент угадывания направления движения

Средняя относительная ошибка Средний процент угадывания на-

Ряд прогноза, % правления движения

Метод «Гусеница» АЯИМЛ (рЛд) Метод «Гусеница» АКИМА (рЛя)

Ряд А, участок 1 3,65 12,06 75,0 50,0

Ряд А, участок 2 3,93 8,59 75,0 58,3

Ряд А, участок 3 4,14 10,46 66,6 50,0

Ряд В, участок 1 6,61 13,96 58,3 50,0

Ряд В, участок 2 19,3 24,47 75,0 58,3

Ряд В, участок 3 6,91 23,34 83,3 75

Из проведенных экспериментов видно, что метод «Гусеница» строит более адекватный и качественный прогноз на временных рядах информационного трафика с дискретным временем снятия данных, нежели модель АКИМА (рЛч)• Для построения прогнозов временных рядов трафика реального времени, а так же трафика с простой структурой, папример, видео-трафика, рекомендуется использовать семейство авторегрессионных моделей, в частности модель АШЧМ АО, £/,<?).

В заключении делаются выводы, излагаются основные результаты.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В диссертации получены следующие результаты:

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

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

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

4. Экспериментально выявлены признаки свойств самоподобия и длительной памяти при анализе временных рядов трафика данных с дискретным временем снятия. Проанализированы модели и методы для анализа временных рядов трафика данных. В частности семейство авторегрессионных моделей и метод «Гусеница»

5. Осуществлен анализ и прогнозирование временных рядов трафика данных посредством метода «Гусеница» и модели АКИМА (р,с1,д). В рассматриваемом случае, метод «Гусеница» показал лучшие результаты в прогнозировании, нежели модель АЮЧМА (р,с!,д).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК РФ

1. Семенов М.Е. Экспериментальные исследования трафика компьютерной сети на предмет самоподобия / М.Е. Семенов, А.Ю.Соловьев //Системы управления и информационные технологии, 2008. -№ 3(33).- С. 71-73.

2. Семенов М.Е. Алгоритмы структурной оптимизации сетей связи / М.Е. Семенов, А.Ю.Соловьев, О.В. Тимченко //Системы управления и информационные технологии, 2009.-№ 3.1(37).-С. 195-199.

Статьи, материалы конференций

3. Семенов М.Е. О задаче оптимального проектирования сетей передачи данных на примере пассивных оптических сетей связи / М.Е. Семенов, А.Ю.Соловьев //Труды пятой региональной научной конференции студентов, аспирантов и соискателей - Старый Оскол, 2009. - Т.З. - С.153-156.

4. Семенов М.Е. Алгоритм муравьиных колоний в задачах структурной оптимизации сетей связи с ограничениями по мощности / М.Е. Семенов, А.Ю.Соловьев // Труды международной научной конференции «Образование, наука, производство и управление». - Старый Оскол, 2009. - Т.З. - С.243-247.

5. Семенов М.Е. Использование муравьиных алгоритмов для различных задач структурной оптимизации, при построении сетей связи / М.Е. Семенов,

А.Ю.Соловьев // Труды Всероссийской конференции «Математическое обеспечение и моделирование в обеспечении оптимального функционирования Вооруженных сил Российской Федерации». - Воронеж, 2009. -Т.З. - С.186-188.

6. Соловьев А.Ю. О задаче прогнозирования самоподобных сетевых процессов / А.Ю.Соловьев // [Электронный ресурс]: Труды Второй Международной научной интернет-конференции «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях», 2009. URL: http://econf.rae.rn/pdf/2009/11 /7dcd340d84.pdf (дата обращения 02.11.2009).

7. Соловьев А.Ю. Сингулярно-спектральный анализ в исследованиях временных рядов сетевого трафика / А.Ю.Соловьев // Труды Второй Всероссийской научно-практической конференции «Перспективы развития информационных технологий».- Новосибирск, 2010. - С.117-122.

8. Соловьев А.Ю. О применении авторегрессиоиных моделей для анализа временных рядов сетевого трафика / А.Ю.Соловьев, М.Е. Семенов //Труды Шестой региональной научно-практической конференции студентов и аспирантов. Старый Оскол, 2010.-Т.2. - С.69-71.

9. Соловьев А.Ю. Применение фрактальной модели авторегрессии проинтегрированного скользящего среднего в исследованиях реализаций сетевого трафика / А.Ю.Соловьев // Труды Седьмой Всероссийской научно-практической конференции «Приоритетные направления развития науки и технологий» ».- Тула, 2010. - С.87-89.

10. Семенов М.Е. Обобщенный алгоритм решения задачи структурной оптимизации при построении крупных и территориально разнесенных сетей связи / М.Е. Семенов, А.Ю.Соловьев // Труды Седьмой Всероссийской научно-практической школы-конференции «Управление большими системами». -Пермь, 2010. -С.355-361.

П.Соловьев А.Ю. Идентификация трендовых и периодичных составляющих в трафике сетей связи / А.Ю.Соловьев // Труды Всероссийской конференции «Новые технологии в научных исследования, проектировании, управлении, производстве». -Воронеж, 2010. -С.59-61.

Подписано в печать 2.02.2011 г. Печать офсетная. Формат 30x42 'Аб. Бумага офсетная. Объем 2 п.л. Заказ 6. Тираж 100 экз.

Отпечатано в ООО «Оскольская типография», 309514, г. Старый Оскол, ул. Калинина, 2а.

Перечень сокращений.

Введение.

Глава 1. Современное состояние. Основные понятия и принципы.

1.1 Тенденция эволюции современных телекоммуникационных систем

1.2 Задачи, связанные с этапом проектирования.

1.2.1 Общая постановка задачи.

1.2.2 Математическая интерпретация задачи.

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

1.2.3.1 Метод ветвей и границ.

1.2.3.2 Генетический алгоритм.

1.2.4 Алгоритм муравьиной колонии как альтернатива существующим методам.

1.2.5 Постановка задачи структурной оптимизации.

1.3 Этап эксплуатации телекоммуникационных систем.

1.3.1 Общие задачи.

1.3.2 Самоподобие телекоммуникационных процессов.

1.3.2.1 Понятие фрактальности.

1.3.2.2 Проблема самоподобного телетрафика.

1.3.2.3 Определение самоподобного процесса.

1.3.2.4 Поведение автокорреляционной функции самоподобных процессов.

1.3.2.5 Понятие коэффициента Хэрста.

1.3.3 Предпосылки к прогнозированию и общая задача.

1.4 Выводы по Главе 1.

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

2.1 О задачах структурной оптимизации телекоммуникационных систем

2.2 Общее описание муравьиного алгоритма.

2.3 Задача с ограниченным числом подключаемых абонентских устройств.

2.3.1 Постановка задачи.

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

2.4 Задача с ограниченным числом промежуточных устройств.

2.4.1 Постановка задачи.

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

2.5 Кольцевание промежуточных устройств.

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

2.7 Обобщенный алгоритм для задачи структурной оптимизации.

2.8 Выводы по Главе 2.

Глава 3. Исследование временных рядов с длительной памятью.

3.1 Эксперимент по обнаружению свойств самоподобия у временных реализаций трафика с дискретным временем снятия данных.

3.1.1 Описание эксперимента.

3.1.2 Анализ полученных данных.

3.1.3 Тест на обоснованность оценки параметра Хэрста.

3.2 Методы и модели для описания временных рядов со свойством самоподобия.

3.2.1 О применении авторегрессионных моделей для анализа временных рядов.

3.2.1.1 Процессы линейной авторегрессии (АЯ) и скользящего среднего (МА).

3.2.1.2 Авторегрессионные модели скользящего среднего (ARMA).

3.2.1.3 Фрактальная модель ARFIMA.

3.2.2 Пример использования модели ARFIMA для анализа временных рядов трафика данных.

3.3 Альтернативный метод для исследования временных рядов трафика данных, метод сингулярно-спектрального анализа (метод «Гусеница»)

3.3.1 Описание базового алгоритма метода «Гусеница».

3.3.2 Пример анализа реализаций трафика данных.

3.3.2.1 Выбор длины окна и анализ главных компонент.

3.3.2.2 Отбор главных компонент и восстановление рядов.

3.4. Выводы по Главе 3.

Глава 4. Экспериментальные проверки предложенных методов структурной оптимизации и прогнозирования временных рядов в телекоммуникационных системах.

4.1 Этап проектирования. Моделирование разработанных алгоритмов.

4.1.1 Описание системы моделирования AnyLogic.

4.1.1.1 Среда моделирования системы AnyLogic.

4.1.1.2 Библиотеки AnyLogic.

4.1.2 Реализация алгоритма муравьиной колонии в среде AnyLogic.

4.1.3 Входные параметры алгоритма в среде AnyLogic. Подбор основных коэффициентов алгоритма.

4.1.4 Численный эксперимент. Сравнение работы муравьиного алгоритма с генетическим алгоритмом.

4.2 Проверка возможности прогнозирования временных рядов трафика данных предложенными моделями.

4.2.1 Выбор и описание исследуемых временных реализаций.

4.2.2 Прогноз временных рядов при помощи метода «Гусеница».

4.2.3 Прогноз временных рядов при помощи модели ARFIMA (p,d,q)

4.2.4 Сравнение результатов прогнозирования обоими методами.

4.3. Выводы по Главе 4.

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

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

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

Свойства временных рядов самоподобного трафика изучались в работах Городецкого А.Я., Заборовского B.C., Шелухина О.И., Петрова В.В., но анализируемый в этих работах трафик использовался с очень малым уровнем агрегирования, и прогноз совершался только на несколько секунд или минут вперед, что достаточно, например, для динамичного распределения полосы пропускания, но получить общую картину поведения пользовательской активности и сделать прогноз загрузки устройств хотя бы на час вперед невоз7 можно. При этом исследуемые временные ряды в реальном времени сильно зашумлены и не дают целостной картины. Отметим также, что анализ наличия свойств самоподобия у временных рядов с дискретным временем снятия не проводился вообще. Кроме того, за прошедшие годы, характер информационного трафика, а так же его структура кардинально изменились, и ранние исследования могут оказаться некорректными в настоящее время.

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

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

Достижение цели потребовало решения следующих задач:

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

- анализ временных рядов трафика данных с дискретным временем снятия данных с целью выявления свойств самоподобия и построение на его основе прогнозных моделей;

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

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

Методы исследования. В работе использованы методы и средства системного анализа, теории графов, теории эвристических алгоритмов, имитационного моделирования, теории оптимизации, теории вероятности и математической статистики.

Научная новизна и значимость результатов диссертации:

В работе впервые разработаны:

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

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

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

Экспериментально выявлено преимущество метода сингулярно-спектрального анализа («Гусеница») над семейством традиционных авторегрессионных моделей (АКИМА) при прогнозировании временных рядов трафика телекоммуникационных систем с дискретным временем снятия данных, количественно выраженное в меньшей ошибке прогноза и большем проценте правильного распознавания направления эволюции временных рядов, описывающих информационный трафик.

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

Соответствие диссертации паспорту научной специальности.

Диссертационная работа соответствует паспорту специальности 05.13.17 — «Теоретические основы информатики» (технические науки), а именно: п. 1 «Исследование, в том числе, с помощью средств вычислительной техники, информационных процессов, информационных потребностей коллективных и индивидуальных пользователей»; п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; п. 16 «Общие принципы организации телекоммуникационных систем и оценки их эффективности. Разработка научных принципов организации информационных служб по отраслям народного хозяйства. Изучение социально-экономических аспектов информатизации и компьютеризации общества».

На защиту выносятся:

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

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

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

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

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

10

Апробация работы. Материалы диссертационной работы докладывались и обсуждались на международных и Всероссийских конференциях: II Всероссийской научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2010); VII Всероссийской научно-технической конференции «Приоритетные направления развития науки и технологий» (Тула, 2010); Международной научно-практической конференции «Образование, наука, производство и управление» (Старый Оскол, 20082009). Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2010); VII Всероссийской научно-практической школы-конференции «Управление большими системами» (Пермь, 2010).

Публикации. По результатам исследования опубликовано 11 работ, в том числе 4 без соавторов; 2 в изданиях, рекомендованных ВАК РФ для публикации основных результатов диссертационных исследований.

Личный вклад автора в работах, опубликованных в соавторстве, состоит: в [48] — подготовка и организация эксперимента с целью выявления самоподобных свойств трафика; в [49,51,52] — разработка и реализация алгоритма на основе метода муравьиных колоний; в [50] - формулировка задачи в линейно-целочисленном виде; в [53] - оценка возможности применения авторегрессионных моделей для анализа трафика данных; в [54] — обобщенный алгоритм структурной оптимизации телекоммуникационных систем.

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

4.3 Выводы по Главе 4

1. Реализованы алгоритмы муравьиной колонии для поставленных задач структурной оптимизации телекоммуникационных систем в среде Апу-1о§ю.

2. Для полученных алгоритмов были проведены исследования для подбора оптимальных параметров алгоритма и его поведение при различных значениях параметра.

3. Было обнаружено, что при достаточно низком значении параметра /? и высоком значении параметра аир целевая функция алгоритма не достигает оптимального значения. Происходит преждевременное схождение алгоритма.

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

5. Произведен эксперимент по прогнозированию временных рядов трафика данных. Эксперимент производился на двух временных рядах на трех участках каждого ряда. Для прогноза использовались предложенные модели и методы.

6. Метод сингулярно-спектрального анализа показал лучшие результаты, нежели модель АКИМА (р,е^,д), во всех случаях было более успешно угадано направление ряда. Ошибка прогноза у метода «Гусеница» гораздо меньше, чем у модели АЯИМА (р,с1,д).

7. Не смотря на результаты прогнозирования, при использовании модели АЛИМА {рЛ,ц) было выявлено, что параметр с1 изменяется в диапазо

114 не (0, 0,5), что эвристически подтверждает значение параметра Хэрста больше 0,5. Это доказывает предположение о наличие у временных рядов трафика данных с дискретным временем снятия свойства самоподобия.

8. Определены сложности, возникающие при применении метода «Гусеница» для прогноза временных рядов. В первую очередь, это связано с необходимостью постоянного оценивая параметров модели, что приводит к большому числу вариантов отбора собственных троек и, следовательно, к большому числу вариантов прогноза. Чего не возникает при использовании традиционных моделей, где выбор модели и ее параметров происходит только на начальном этапе.

Заключение

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

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

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

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

4. Экспериментально выявлены признаки свойств самоподобия и длительной памяти при анализе временных рядов трафика данных с дискретным временем снятия. Проанализированы модели и методы для анализа временных рядов трафика данных. В частности семейство авторегрессионных моделей и метод «Гусеница»

5. Осуществлен анализ и прогнозирование временных рядов трафика данных посредством метода «Гусеница» и модели АИИМА (рДд). В рассматривае

116 мом случае, метод «Гусеница» показал лучшие результаты в прогнозировании, нежели модель АИПМА {р,с1,ц).

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

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

1. Айвазян С.А. Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-е изд. испр. —Т.2.: Айвазян С.А. Основы эконометрики. М.: ЮНИТИ-ДАНА, 2001. - 432 с.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. — Н.Новгород: Государственный комитет Российской Федерации по высшему образованию, Нижегородский государственный университет им. Н. И. Лобачевского, 1995.-71 с.

3. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. -300 с.

4. Береснев В.Л. Алгоритм неявного перебора для задачи типа размещения и стандартизации. Управляемые системы. Вып.12 (1974). Новосибирск, Институт математики Сиб.отд. АН СССР, С. 24-34.

5. Боровков А.А. Теория вероятностей: Учебное пособие для Вузов. — 2-е изд. перераб. и доп. М. Наука. Гл. ред. физ.-мат. лит. 1986. 423 с.

6. Босс В. Лекции по математике. Т.4 : Вероятность, информация, статистика. Изд. 2-е, испр. -М.Издательство ЛКИ, 2008. -216 с.

7. Бугров Д.А. Постановка задачи структурной оптимизации магистральной корпоративной телекоммуникационной сети // Информация и Космос. — 2005. -№ 2. -С. 42^17.

8. Вегешна Ш. Качество обслуживания в сетях 1Р.: Пер. с англ. М.: Изд. дом «Вильяме», 2003. -368 с.

9. Галеев Э.М. Оптимизация. Теория, примеры, задачи: Учебное пособие. Изд. 2-е, испр. и доп. -М.:КомКнига, 2006. 336 с.

10. Галямов В.А. О задаче оптимизации построения первичной сети свя-зи.//Труды ИВМ и МГ. Сер. Информатика. Новосибирск, 2005. -№5. — С. 68-79.

11. П.Гладков Л.А. Генетические алгоритмы / Л.А. Гладков В.В. Курейчик В.М.Курейчик. -М : Физматлит, 2006 г. -402 с.

12. Голяндина Н.Э. Метод «Гусеница»-88А: анализ временных рядов: Учеб. пособие. СПб: Изд-во СПбГУ, 2004. -76 с.

13. Гончаров E.H., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер.2, т.6 (1999). — №1. — С. 12-32.

14. Городецкий А.Я., Заборовский B.C. Информатика. Фрактальные процессы в компьютерных сетях: Учеб. пособие. /СПб.: Изд-во СПбГТУ, 2000. -102 с.

15. Гмурман В.Е. Теория вероятностей и математическая статистика. Учеб. пособие для вузов. 8-е изд., стер. М.: Высш. шк., 2002. -479 с.

16. Дж. Макконнелл Основы современных алгоритмов. 2-е дополненное издание Москва: Техносфера, 2004. 368 с.

17. Емельянов В.В. Теория и практика эволюционного моделирования/.В. Емельянов, В.В. Курейчик, В.М. Курейчик. -М : Физматлит, 2003. 431 с.

18. Заборовский B.C. Методы и средства исследования процессов в высокоскоростных компьютерных сетях: Диссертация на соискание ученой степени доктора технических наук -СПб., 1999 г.

19. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. К.: Техшка, 1986.-168 с.

20. Зембицкая A.C., Колеснык Е.В. Экспериментальные исследования трафика высокоскоростных сетей.//Проблемы информатизации и управления: 2006. С.65-71.

21. Карпов, Ю. Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5.- СПб: БХВ-Петербург, 2006 400 с.

22. Каширина И.JI. Генетический алгоритм решения квадратичной задачи о назначениях специального вида// Вестник ВГУ. Серия физика, о назначениях специального вида// Вестник ВГУ. Серия физика, математика , 2003. № 1.-С. 128-131.

23. Кендел М. Временные ряды: Пер. с англ. и предисл. Ю.П. Лукашина. М: Финансы и статистика, 1981. - 199 с.

24. Клейнрок Л. Теория массового обслуживания / Л. Клейнрок.- М.: Машиностроение, 1979. 432 с.

25. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.- 600 с.

26. Косолапова Л.Г., Ковров Б.Г. Эволюция популяций. Дискретное математическое моделирование. — Новосибирск: Наука, 1988. —93 с.

27. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Изд. 2-е, стереотипное. М.: Едиториал УРСС, 2003. -192 с.

28. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001. 960 с.

29. Крылов В.В., Самохвалова С.С. Теория телетрафика и ее приложения. -СПб.: БХВ-Петербург, 2005. 288 с.

30. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет. СПб.: Наука и Техника, 2004. - 336 с.

31. Лагутин B.C., Степанов С.И. Телетрафик мультисервисных сетей связи. М.: Радио и связь, 2000. -320 с.

32. Лимончелли Т., Хоган К., Чейлап С. Системное и сетевое администрирование. Практическое руководство. 2-е изд. М.:Символ-Плюс, 2009. -944 с.

33. Мандельброт Б. Фрактальная геометрия природы. М.: «Институт компьютерных исследований», 2002. -656 с.

34. М. Россарио Н., Ст. Г.Юджин Введение в эконофизику: Корреляции с ложность в финансах. Пер. с англ./Под ред. В.Я. Габескерия. -М. ¡Книжный дом «ЛИБРОКОМ», 2009. -192 с.

35. Матвеенко И.М., Бурковский A.B. Модели оптимизации параметров обслуживания в развивающихся корпоративных сетях специального назначения // Вестник Воронежского государственного технического университета. 2007. -Т.З. —№5. С.73-76.

36. Найденов В.И., Кожевникова И.А. Эффект Харста в геофизике // Природа.-2000. №1.

37. Олифер В.Г., Олифер H.A., Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд. — СПб.: Питер, 2007. —958 с.:ил.

38. Панченко, Т. В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. Астрахань: Издательский дом «Астраханский университет», 2007. - 87 с.

39. Пащенко М.Г. Лагранжевы эвристики для задачи размещения с ограничениями на мощности. Труды XI международной Байкальской школы-семинара Методы оптимизации и их приложения. Иркутск, т.1 (1998), С.175-178.

40. Петров В.В. Структура телетрафика и алгоритм обеспечения качества обслуживания при влиянии эффекта самоподобия. Автореферат диссертации. Москва. 2005. - 20 с.

41. Петров В.В., Платов В.В. Исследование самоподобной структуры телетрафика беспроводной сети // Радиотехнические тетради. 2004. -№ 30. - С. 58 -62.

42. Пятаев О.В. Применение генетического алгоритма для оптимизацииструктуры кампусной сети // Радиоэлектронные и телекоммуникацион121ные системы и устройства: Межвузовский тематический сборник научных трудов. 2000 г. - С. 55-61.

43. Рутковский JI., Пилиньский М., Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия-Телеком, 2004 г.-452 с.

44. Рындин H.A., Калмыков A.A. Постановка задачи оптимизации многосегментных кампусных сетей // Оптимизация и моделирование в автоматизи рованных системах: межвуз. сб. науч. тр. Воронеж; ВГТУ, 2005. С. 166171.

45. Семенов А.Б., Стрижаков С.К., Сунчелей И.Р. Структурированные кабельные системы.Стандарты, компоненты, проектирование, монтаж и техническая эксплуатация. М. КомпьютерПресс, 1999.— 482 с.

46. Семенов М.Е. Экспериментальные исследования трафика компьютерной сети на предмет самоподобия / М.Е. Семенов, А.Ю.Соловьев //Системы управления и информационные технологии, 2008. —№ 3(33).— С. 71-73.

47. Семенов М.Е. Алгоритмы структурной оптимизации сетей связи / М.Е. Семенов, А.Ю.Соловьев, О.В. Тимченко //Системы управления и информационные технологии, 2009.-№ 3.1(37).-С. 195-199.

48. Семенов М.Е. О применении авторегрессионных моделей для анализа временных рядов сетевого трафика / М.Е. Семенов, А.Ю.Соловьев //Труды Шестой региональной научно-практической конференции студентов и аспирантов. Старый Оскол, 2010. -т.2. -С.69-71.

49. Соловьев А.Ю. Сингулярно-спектральный анализ в исследованиях временных рядов сетевого трафика // Труды Второй Всероссийской научно-практической конференции «Перспективы развития информационных технологий» ».- Новосибирск, 2010. С. 117-122.

50. Соловьев А.Ю. Идентификация трендовых и периодичных составляющих в трафике сетей связи // Труды Всероссийской конференции «Новые технологии в научных исследования, проектировании, управлении, производстве». -Воронеж, 2010. С.59-61.

51. Столлингс В. Современные компьютерные сети: Питер, 2-е изд. (пер. с англ. Леонтьева А.), 2003. 784 с.

52. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей/ Пер. с англ. — М.: Мир, 1984.-496 с.

53. Шелухин, О. П., Осин А.В., Смольский С.М. Самоподобие и фракталы. Телекоммуникационные приложения. / Под ред. О.И.Шелухина. -М.:ФИЗМАТЛИТ, 2008. -386 с.

54. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Москва-Ижевск 2001. — 528 с.

55. Штовба С. Д. Муравьиные алгоритмы.//Ехропеп!а Pro. Математика в приложениях , 2003, №4, С. 70-75.

56. Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса // Радиотехника. 1999. —№ 5. — С. 24-31.

57. Э.Петерс Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка: Пер.с англ. -М.:Мир. 2000. -333 с. ил.

58. Aarts Е. Н. L, Korst J.H.M., van Laarhoven P. J. M. Simulated annealing. Local Search in Combinatorial Optimization. Chichester: Wiley. 1997. P. 91—120.

59. Akins U., Khumawala M. An efficient branch and bound algorithm for the capacitated warehouse location problem. Management Science v23 (1977), pp 585-594.

60. Beran J. Statistical Methods for Data with Long-Range Dependence // Statistical Science, Volume 7, Issue 4. 1992. P. 404-416.

61. Bonald T. Comparison of TCP Reno and TCP Vegas via Fluid Approximation. // Rapport de recherche N. 3563. INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE. -1998.

62. Buchstaber V.M. Time series analysis and grassmannians //Applied Problems of Radon Transform./ Ed. by S. Gindikin. Providence, RI: AMS, 1994. P. 117.

63. C. Assi, Y. Ye, S. Dixit, and M. Ali, "Dynamic Bandwidth Allocation for Quality-of-Service Over Ethernet PONs", IEEE Journal on Selected Areas in Communications 21(9), pp. 1467-1477, November 2003.

64. C. W. J. Granger and R. Joyeux. "An introduction to long-memory time series and fractional differencing", Journal of Time Series Analysis, 1980.

65. Colomi A., Dorigo M., Maniezzo V. Distributed optimization by Ant Colonies. Proceedings of the First European Conference on Artifical Life. Paris, France, 1991.-pp. 134-142.

66. Dang T. D., Sonkoly B., Molnar S. Fractal Analysis and Modelling of VoIP Traffic // NETWORKS2004, Vienna, Austria, June 13-16, 2004.

67. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System».- Budapest, Central European University, 2001. — P. 1-38.

68. Eisner J.B. and Tsonis A.A. Singular Spectrum Analysis. A New Tool in Time Series Analysis. New York and London: Plenum Press, 1996. 164 p.

69. F. Effenberger, et al., "An Introduction to PON Technologies." IEEE Comm. Magazine, vol. 45, no. 3, Mar. 2007, pp. 17-25.

70. Feng W., Tinnakornsrisuphap P. The Failure of TCP in High-Performance Computational Grids // SC2000: High-Performance Network and Computing Conference, Dallas, TX. November, 2000.

71. George Box, Gwilym M. Jenkins, and Gregory C. Reinsel. Time Series Analysis: Forecasting and Control, third edition. Prentice-Hall, 1994.

72. Goldberg G. Genetic algorithms in search. Optimization and machine learning. Adison Wesley: MA, 1989. - P. 32-^17.

73. Gusella R. A Measurement Study of Diskless Workstations Traffic on an Ethernet. // IEEE Trans, on Communications. 38(9). 1990. - p. 1557-1568.

74. Hansen, P. and Jaumard, B. Cluster Analysis and Mathematical Programming. Mathematical Programming 79 (1997), p. 191-215.

75. Hendry, D.F. and Nielsen, B. 2007. Econometric Modeling: A Likelihood Approach, Princeton University Press.

76. Holmberg K., Ronnqvist M., Yuan D. An exact algorithm for the capacitated facility location problems with single sourcing. European Journal of Operational Research, vl 13 (1999), pp 544-559.

77. J. Tang, B. Hao, and A. Sen. Relay node placement in large scale wireless sensor networks. Computer Communications, 29(4):490-501, 2006.

78. K. Kim, "On the evolution of PON-based FTTH solutions", Information sciences 149 21-30, 2003.

79. Khumawala B.M. An efficient heuristic procedure for the capacitated warehouse location problem. Naval Research Logistics Quarterly. v21 (1974), N4, pp 609-623.

80. Krarup J., Pruzan P.M. The simple plant location problem: Survey and synthesis. European Journal of Operational Research. vl2 (1983), pp 36-81.

81. Leland W.E., Taqqu M.S., Willinger W., and Wilson D.V. On the self-similar nature of ethernet traffic // IEEE/ACM Transactions of Networking, 2(1), 1994.-P. 1-15.

82. M. Hajducznia, et al., Optimized passive optical network deployment // Journal of Opt. Net., vol. 6, no. 9, Sep. 2007, pp. 1079-1104.

83. Mills, Terence C. Time Series Techniques for Economists. Cambridge University Press, 1990.

84. Mirchandani P.B., Francis R.L. Discrete Location Theory. John Wiley & Sons, 1990.

85. Olowoyeye G., Kim B., Chandra K. Modelling Spectral Features in TCP Traffic. Submitted to ITC'99, October 1998.

86. Ostring S., Sirisena H. The Influence the Long-Range Dependence on Traffic Prediction // Proceedings of ICC'01. -Helsinki, June 2001.

87. Pandit, Sudhakar M. and Wu, Shien-Ming. Time Series and System Analysis with Applications. John Wiley & Sons, Inc., 1983.

88. Petrowski D.,Taillard S. Metaheuristics for Hard Optimization. Methods and Case Studies. Springer. 2006.

89. Potapov A., Kurths J. Correlation integral as a tool for distinguishing between dynamics and statistics in time series data // Physics D. 120. —1998. -P.369-385.

90. S.Ilnickis, Research of the network server in self-similar traffic environment, RTU, Riga, 2003.

91. Sridharan R. The capacitated plant location problem. European Journal of Operational Research. v87 (1995), pp. 203-213.

92. Trajkovic L., Neidhardt A. Internet traffic prediction // Centre for Systems Science, Simon Fraser University, Vol. 12, Issue 1. Mar. 2000.

93. Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna. -Vienna, Austria, 2002. 149 p.

94. Riedi R., Vehel J. TCP traffic is multifractal: a numerical study. // INRIA research report 3129 March 1997.

95. Veres A., Boda M. The Chaotic Nature of TCP Congestion Control//Proceedings of IEEE INFOCOM'2000, March 2000.

96. Willinger W., Taqqu M.S., Sherman R., Wilson D.V., Self-Similarity Through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level, IEEE/ACM Transactions on Networking, Vol. 5, No. 1, 1997.

97. Компания Cisco, производитель сетевого оборудования, http://www.cisco.com/web/RU.

98. Компания D-Link, производитель сетевого оборудования, http://www.dlink.ru/.

99. Компания Huawei, производитель сетевого оборудования http://www.huawei.com/ru/ .

100. Компания Zyxel, производитель сетевого оборудования http://www.zyxel.ru

101. Программа Cartepillar SSA, для анализа временных рядом методом сингулярно-спектрального анализа. http://www.gistatgroup.eom/gus/detail.html#d3.

102. Selfis vO.lb -программа для анализа экспоненты Хэрста разработки Thomas Karagiannis: http://www.cs.ucr.edu/~tkarag .

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

104. Код блока функции start(i,j)for(i=0;i<numPlace;i++) {for(j=0;j<numSpliters;j++) {feromon1.j.=0.1;distance1.ü.=Math.sqrt((10*a|j]-10*xi])*(10*aD]-10*x[i])+(10*b(j]-10*y[i])*(10*b[j]-10*y[i]));redistance1. j.=l/distance[i] [j];

105. Функция start(ij) отвечает за расчет расстояний между промежуточными и абонентскими узлами.

106. Разработанный алгоритм в среде Anylogic, представлен следующими диаграммами состояний:

107. Функция ChoosePath отвечает за формирование маршрута, а так же расчета количества наносимого феромона на выбранный маршрут для каждого муравья-агента Блок «Обновление пути»:while(k! =num Ant) {1. UpdatePath();if(ant.item(k).fitness<CurrentFitness) {

108. CurrentFitness=ant.item(k).fitness; //Процедура выбора текущего наилучшего решения ind=k;for(i=0;i<numPlace;i++)for(j=0 у <numSpliters;j++) {var j . =ant .i tem(k). var 1 [j];

109. Prom 1 1. j . =ant. item(k). choose [i] [j ]; }}k++; }k=0;

110. Переход «Завершающий переход»:while(k! =num Ant) {ant.item(k). fitness=0; end();k++; }for(i=0;i<numPlace;i++) {for(j=0 ;j <n um Spl iters ;j ++) {feromon1.j.=feromon[i][j]*(l-rho); //Испарение феромона }sumver1.=0; }sumSpliters^O; counter++;

111. Переход отвечает за процедуру испарения феромонов, а так же обнуления всех нужных счетчиков. Функция EndQ:for(i=0;i<numPlace;i++) {for(j =0;j <numSpliters;j ++) {ant.item(k).choose1.j.=false;ant.item(k).SplitersCounterj.=0; }return 0;

112. После этого алгоритм переходит в блок «Начальное состояние» и запускается вновь, процедура повторяется, пока не будет найдено наилучшее решение.2.3адача размещения с ограниченным числом промежуточных устройств

113. Как видим, некоторые параметры претерпели изменение по сравнению с предыдущим алгоритмом. Это связано со спецификой задачи и установленными ограничениями