АЛГОРИТМ  ОПТИМИЗАЦИИ  ХАРАКТЕРИСТИК  ФУНКЦИОНИРОВАНИЯ  КОМПЬЮТЕРНЫХ  СЕТЕЙ  C   НЕЧЕТКО  ЗАДАННЫМИ  ПАРАМЕТРАМИ

Шапорина  Елена  Леонидовна

Ассистент,  кафедры  компьютерных  интеллектуальных  систем  и  сетей  Одесского  национального  политехнического  университета,  Украина,  г.  Одесса

Тишин  Петр  Метталинович

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

Милейко  Игорь  Генрикович

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

Шапорин  Руслан  Олегович

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

E-mail: 

ALGORITHM  OF  OPTIMIZATION  CHARACTERISTICS  OF  FUNCTIONING  COMPUTER  NETWORKS  WITH  FUZZY  SETS  PARAMETERS

Shaporina  Olena

assistant  department  of  computer  intelligent  systems  and  networks  Odessa  national  polytechnic  university,  Ukraine,  Odessa

Tishin  Petro

PhD,  associate  professor  department  of  computer  intelligent  systems  and  networks  Odessa  national  polytechnic  university,  Ukraine,  Odessa

Mileyko  Igor

associate  professor  department  of  computer  intelligent  systems  and  networks  Odessa  national  polytechnic  university,  Ukraine,  Odessa

Shaporin  Ruslan

PhD,  associate  professor  department  of  computer  intelligent  systems  and  networks  Odessa  national  polytechnic  university,  Ukraine,  Odessa

АННОТАЦИЯ

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

ABSTRACT

In  the  paper,  we  present  a  one-criterion  problem  of  optimal  distribution  of  information  flow  through  the  channels  of  communication  devices  with  clearly  specified  data.  The  description  of  the  algorithm  for  solving  the  optimization  problem  in  this  setting.

Ключевые  слова:  сети  массового  обслуживания;  среднее  время  задержки  сообщения;  нечеткие  множества.

Keywords:  queuing  network;  the  average  message  delay  time;  fuzzy  sets.

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

В  работе  коммуникационная  система  КС  представляется  в  виде  множества  узлов  коммутации  (УК)  [2,  3].  В  качестве  узлов  коммутации  рассматриваются  коммутаторы  и  маршрутизаторы,  на  базе  которых  строятся  коммуникационные  системы  современных  КС.  Для  узлов  коммутации  (УК)  сформированы  показатели  эффективности,  которые  используются  в  задачах  анализа  и  синтеза  рациональных  структур  КС.  Один  из  основных  показателей,  который  рассмотрен  в  данной  работе,  является  среднее  время  задержки  сообщений.

Моделью  УК  является  узел,  имеющий  один  входной  канал  по  которой  поступает  входной  поток  заявок  с  интенсивностью  l  и  n  каналов  связи  выходящих  из  УК.  При  этом  под  одним  входным  потоком  понимается  суперпозиция  всех  входных  потоков  УК.  Входной  поток  распределяется  по  n  каналам  связи  и  порождает  в  каждом  канале  трафик  с  интенсивностью  l_j,  j=1,n.

Каждый  канал  связи  рассматривается  как  система  массового  обслуживания  с  некоторой  интенсивностью  обслуживания  m_j,  что  позволяет  множество  каналов  связи  рассматривать  как  сеть  систем  массового  обслуживания.  Предполагается,  что  в  сети  действует  стохастический  алгоритм,  управляющий  распределением  пакетов  по  каналам  связи  так,  что  из  общего  трафика  l,  поступающего  на  узел  в  j-й  канал  связи,  выделяется  некоторая  доля  p_jl  (1)  и  выполняется  условие  (2):

  (1)

  (2)

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

  (3)

Параметры  в  выражении  (3)  определяются  следующим  образом:

    (4)

где:    —  средняя  эквивалентная  интенсивность  обслуживания  в  j-м  канале  связи; 

  —  средняя  интенсивность  обслуживания  в  j-м  канале  связи;

  —  средняя  эквивалентная  интенсивность  старения  информации  в  j-м  канале  связи;

  —  средняя  интенсивность  старения  информации  в  j-м  канале  связи;

  —  коэффициент  простоя  j-го  канала  связи;

  —  коэффициент  готовности  j-го  канала  связи;

  —  коэффициент  ненадежности  j-го  канала  связи;

—  среднее  время  простоя;

—  среднее  время  исправной  работы;

  —  среднее  время  старения  информации.

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

;

С  учетом  выражения,  приведённого  выше,  среднее  время  задержки  сообщения  через  узел  можно  рассчитывать  по  следующему  соотношению:

,                (5)

где  μ_эj  =  b_j  , 

Данные  выражения  дают  возможность  рассчитать  оптимальное  распределение  трафика  через  выходные  каналы  КУ  в  случае,  когда  все  исходные  данные  заданы  точно.  Однако  такие  параметры,  как  время  простоя  ,  время  исправной  работы    и  время  старения  информации    в  j-м  канале  связи  часто  не  могут  быть  определены  точно.  Некоторые  вопросы  по  решению  однокритериальных  оптимизационных  задач,  в  случае,  когда  характеристики  функционирования  компьютерных  или  телекоммуникационных  систем  являются  нечеткими,  рассматривались  в  работах  [4,  8,  9].  В  общем  случае  решение  этой  задачи  рассмотрено  ниже.

Для  учёта  нечеткости  исходных  данных  представим  их  в  виде  нечетких  величин,  которые  определены  каждая  на  своем  полном  ортогональным  семантическим  пространстве  (ПОСП)  [6],  с  функциями  принадлежности  трапецеидального  типа,  удовлетворяющими  соотношениям  [9]:

,  ,  ,  (6)

Здесь  через  ,  ,  ,  обозначаются  ПОСП  для  параметров  ,  ,  .  Вследствие  нечеткого  описания  величин,  функции  принадлежностей  которых  описаны  соотношением  (6),  величины,  описанные  соотношением  (4),  являются  нечеткими  переменными,  функции  принадлежностей  которых  можно  вычислить  с  помощью  математических  операций  приведенных  [4,  8,  9]. 

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

  (7)

При  этом  из  соотношений  (4)  получается  справедливость  следующих  зависимостей:

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

С  другой  стороны  для  решения  оптимизационной  задачи  с  нечеткими  величинами  требуется  ввести  ПОСП    и  ПОСП    для  параметров  b_j  и  β_j  ,  которые  могут  быть  рассчитаны  на  основании  формул  (7)  с  помощью  соотношений: 

         (9)

Термы  в  ПОСП  П_b  в  дальнейшем  обозначаем  через    а  термы  в  ПОСП  П_β  через  ,  где  N_b  —  число  термов  в  ПОСП  П_b,  а  N_β  —  число  термов  в  ПОСП  П_β  .

Для  оценки  величины    введем  величину  :

  (10)

для  которой,  в  свою  очередь,  вводится  соответствующий  ПОСП  .

Определим  метрику,  которая  позволяет  значениям    и    ставить  в  соответствие  термы  в  ПОСП  П_b  и  ПОСП  П_β  .  Для  этого,  аналогично  тому,  как  это  делалось  в  работе  [8]  введём  в  рассмотрение  функцию    следующим  соотношением:

                (11)

где  нечеткое  число    определяется  четверкой  ,  нечеткое  число    четверкой  ,  а  функции  ,  когда  ,  также  как  и  в  работе  [3].

В  этом  случае  значения  нечётких  параметров  b_j  и  β_j  можно  рассчитать  с  учетом  соотношений  (11).

Нечёткое  значение  среднего  времени  задержки  сообщений  будет  определяться  выражением:

                           (12)

Причем  согласно  свойствам  ПОСП  на  П_b,  П_β  и  П_T  естественно  вводится  отношения  частичного  порядка  ,  которое  упорядочивает  множества  термов  входящих  в  каждое  из  данных  ПОСП. 

Однокритериальную  оптимизационную  задачу,  в  рассматриваемом  случае  можно  сформулировать  следующим  образом: 

Определить  четкие  значения  p_j  для  которых  величина    принимает  минимальное  значение  в  смысле  отношения  частичного  порядка . 

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

1.  Ввод  исходных  параметров  ,,,  μ_j.

2.  Определить  нечёткие  значения  параметров ,  ,  .

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

4.  Построить  ,  , .

5.  Задать  количество  термов  и  параметры  трапецеидальных  функций  принадлежности  каждого  терма  на  ПОСП    и  ПОСП .

6.  Построить  ПОСП ,  .

7.  Выполнить  операции  дефаззификации  для  параметров    и  :    и  .

8.  Определить  величины    и  множества  .

9.  Задать  r=1.

10.                Для  даного  r  вычисляем  суммы: 

.

11.                Если  <1,  то  r=r+1  и  перейти  к  п.10,  иначе  к  п.  12

12.                Полагаем  .

13.                Вычислить  параметры  ,  при  этом  для  всех    справедливо  соотношение

14.                Расчет  трапецеидального  нечеткого  числа 

15.                Конец.

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

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

1.Дилигенский  Н.В.,  Дымова  Л.Г.,  Севастьянов  П.В.  Нечеткое  моделирование  и  многокритериальная  оптимизация  производственных  систем  в  условиях  неопределенности:  технология,  экономика,  экология  //  Москва:  «Издательство  Машиностроение  —  1»,  2004,  —  397  с.

2.Дымарский  Я.С.  Задачи  и  методы  оптимизации  сетей  связи.  СПб:  2005.

3.Захаров  Г.П.,  Симонов  М.В.  Методы  расчёта  многоканальных  двухполюсных  систем  передачи  данных.  —  Вопросы  радиоэлектроники.  Сер.  ТПС.  1974.  Вып.  5.

4.Копытчук  Н.Б.,  П.М.  Тишин,  К.В.  Ботнарь.  Решение  оптимизационных  задач  для  систем  массового  обслуживания  с  отказами  в  условиях  неопределенности. 

5.Метод  расчета  размеров  буферов  коммутаторов  /  Шапорин  Р.О.,  Шапорин  В.О.,  Милейко  И.Г.//  Труды  Одесского  политехнического  университета,  —  №  2(28),  —  2007  —  С.  116—119.

6.Метод  расчета  параметров  коммуникационного  оборудования  сети  передачи  данных  /  Шапорин  Р.О.,  Плачинда  О.Е.  //  Вісник  національного  технічного  університету  "ХПІ".  Збірник  наукових  праць.  Тематичний  випуск:  Нові  рішення  в  сучасних  технологіях,  м.  Харків,  —  №  23,  —  2011  —  С.  111—114.

7.Рыжов  А.П.  Элементы  теории  нечетких  множеств  и  ее  приложений.  М.:,  2003  г.

8.Тишин  П.М.  Нечеткие  модели  сетей  связи  /  П.М.  Тишин,  К.В.  Ботнарь.  //  Холодильная  техника  и  технология.  Одеса  :  ВЦ  ОДАХ,  —  2009.  —  №  8.  —  С.  60—67.

9.Шапорина  Е.Л.,  доц.  П.М.  Тишин,  проф.  С.А.  Нестеренко,  И.Г.  Милейко.  Модели  характеристик  функционирования  компьютерных  сетей  в  условиях  неопределённости.