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

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

Розглянуто модель комунікаційної мережі на основі марковських полів і задача ідентифікації прихованих поломок мережі на основі байєсівського принципу розпізнавання. Запропоновано рекурсивний алгоритм ідентифікації прихованих першопричин неполадок комунікаційної мережі при наявності повідомлень про з...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2016
Hauptverfasser: Самосьонок, О.С., Біла, Г.Д., Кнопов, О.П.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schriftenreihe:Теорія оптимальних рішень
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/113012
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Застосування інструментарію марковських полів для пошуку причини мережевого збою / О.С. Самосьонок, Г.Д. Біла, О.П. Кнопов // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 3-10. — Бібліогр.: 2 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-113012
record_format dspace
spelling irk-123456789-1130122017-02-01T03:02:26Z Застосування інструментарію марковських полів для пошуку причини мережевого збою Самосьонок, О.С. Біла, Г.Д. Кнопов, О.П. Розглянуто модель комунікаційної мережі на основі марковських полів і задача ідентифікації прихованих поломок мережі на основі байєсівського принципу розпізнавання. Запропоновано рекурсивний алгоритм ідентифікації прихованих першопричин неполадок комунікаційної мережі при наявності повідомлень про збій, які зареєстровані в сусідніх вузлах топологічного графа мережі. Рассмотрено модель коммуникационной сети на основе марковских полей и задача идентификации скрытых поломок сети на основе байесовского принципа распознавания. Предложен рекурсивный алгоритм идентификации скрытых первопричин неполадок работоспособности коммуникационной сети при наличии сообщений о сбое, которые зарегистрированы в соседних узлах топологического графа сети. The model of the communication network based on Markov fields is considered along with the problem of identification of hidden network’s fault based on Bayesian principle of recognition. A recursive algorithm for identifying the root causes of communication system faults is suggested based on analysis of the fault messages registered in the neighboring nodes of the network topological graph. 2016 Article Застосування інструментарію марковських полів для пошуку причини мережевого збою / О.С. Самосьонок, Г.Д. Біла, О.П. Кнопов // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 3-10. — Бібліогр.: 2 назв. — укр. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/113012 519.21 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
description Розглянуто модель комунікаційної мережі на основі марковських полів і задача ідентифікації прихованих поломок мережі на основі байєсівського принципу розпізнавання. Запропоновано рекурсивний алгоритм ідентифікації прихованих першопричин неполадок комунікаційної мережі при наявності повідомлень про збій, які зареєстровані в сусідніх вузлах топологічного графа мережі.
format Article
author Самосьонок, О.С.
Біла, Г.Д.
Кнопов, О.П.
spellingShingle Самосьонок, О.С.
Біла, Г.Д.
Кнопов, О.П.
Застосування інструментарію марковських полів для пошуку причини мережевого збою
Теорія оптимальних рішень
author_facet Самосьонок, О.С.
Біла, Г.Д.
Кнопов, О.П.
author_sort Самосьонок, О.С.
title Застосування інструментарію марковських полів для пошуку причини мережевого збою
title_short Застосування інструментарію марковських полів для пошуку причини мережевого збою
title_full Застосування інструментарію марковських полів для пошуку причини мережевого збою
title_fullStr Застосування інструментарію марковських полів для пошуку причини мережевого збою
title_full_unstemmed Застосування інструментарію марковських полів для пошуку причини мережевого збою
title_sort застосування інструментарію марковських полів для пошуку причини мережевого збою
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2016
url http://dspace.nbuv.gov.ua/handle/123456789/113012
citation_txt Застосування інструментарію марковських полів для пошуку причини мережевого збою / О.С. Самосьонок, Г.Д. Біла, О.П. Кнопов // Теорія оптимальних рішень: Зб. наук. пр. — 2016. — № 2016. — С. 3-10. — Бібліогр.: 2 назв. — укр.
series Теорія оптимальних рішень
work_keys_str_mv AT samosʹonokos zastosuvannâínstrumentaríûmarkovsʹkihpolívdlâpošukupričinimereževogozboû
AT bílagd zastosuvannâínstrumentaríûmarkovsʹkihpolívdlâpošukupričinimereževogozboû
AT knopovop zastosuvannâínstrumentaríûmarkovsʹkihpolívdlâpošukupričinimereževogozboû
first_indexed 2025-07-08T05:02:47Z
last_indexed 2025-07-08T05:02:47Z
_version_ 1837053738817159168
fulltext Теорія оптимальних рішень, 2016 3 ТЕОРIЯ ОПТИМАЛЬНИХ РIШЕНЬ Розглянуто модель комунікаційної мережі на основі марковських полів і задача ідентифікації при- хованих поломок мережі на основі байєсівського принципу розпізна- вання. Запропоновано рекурсивний алгоритм ідентифікації прихова- них першопричин неполадок кому- нікаційної мережі при наявності повідомлень про збій, які зареєст- ровані в сусідніх вузлах топологі- чного графа мережі.  О.С. Самосьонок, Г.Д. Біла, О.П. Кнопов, 2016 УДК 519.21 О.С. САМОСЬОНОК, Г.Д. БIЛА, О.П. КНОПОВ ЗАСТОСУВАННЯ ІНСТРУМЕНТАРІЮ МАРКОВСЬКИХ ПОЛІВ ДЛЯ ПОШУКУ ПРИЧИНИ МЕРЕЖЕВОГО ЗБОЮ Вступ. Сучасний етап розвитку суспільства характеризується суттєвим збільшенням обсягу та цінності інформації, що передаєть- ся інформаційно-комунікаційними мережами зв’язку, відповідно, навіть незначний мере- жевий збій може призвести до втрати важли- вої інформації та появи недовіри користува- чів. Методи діагностики несправності кому- нікаційних мереж [1] залежать від повідом- лень про збій, рівня мережевої взаємодії та степеня критичності несправності, а побудо- ва швидких та ефективних механізмів для виявлення поломок системи є однією з важ- ливих областей застосування математичних алгоритмів. Саме тому в статті розглянуто задачу забезпечення якості функціонування системи, зокрема – задачу виявлення неспра- вностей комунікаційної мережі та ідентифі- кації їх прихованих причин при наявності зареєстрованих повідомлень про збій, що є актуальною проблемою сучасності. Розглянемо комунікаційну мережу, яка представлена у вигляді неорієнтованого гра- фа  ,G V E із скінченною кількістю вер- шин V і дуг Е. Множину індексів вершин S будемо вважати двохвимірною { , }S i j , ,i j і, таким чином, вершинами графа ijs st t V  будемо вважати точки трьохви- мірної цілочислової решітки, де за індексом і можна ідентифікувати «географічне» розта- шування вузла, а за j індексом рівень мере- жевої взаємодії (логічний чи фізичний у най- простішому випадку). У кожній компоненті мережі Хs реєструються повідомлення про О.С. САМОСЬОНОК, Г.Д. БIЛА, О.П. КНОПОВ 4 Теорія оптимальних рішень, 2016 неполадки kx , тобто розглядається багатовимірна випадкова величина  1 1 | | | |,..., V VX X x X x   , де kx A , А – скінченна множина можливих непола- док. Будемо вважати, що всі Хs дискретні та визначені на одному ймовірнісному просторі. Поточну ситуацію працездатності мережі характеризує конкретна реа- лізація  1 | |,..., Vx x x випадкової величини Х. Припустимо, що в деякий момент часу в результаті деякої невідомої події  1 | |,..., Vy y y отримано повідомлення про збій і здійснена їх топологічна прив’язка до елементів мережі, кожна компонента sy Y приймає значення із скінченної множини можливих причин збою Y. У загальному випадку для розв’язку задачі ідентифікації неполадки у* достатньо оцінити функцію апосте- ріорних ймовірностей * argmax ( | ) V y Y y p y x   . Отже, при наявності розподілу апріорних ймовірностей P(y) й умовного ро- зподілу P(x |y) , який характеризує зв’язок між повідомленнями, що спостеріга- ються, і причиною неполадки, розв’язок задачі може бути знайдений з міркувань байєсовського правила в цілому ( ) ( | ) * argmax argmax ( ) ( | ) ( )V V y Y y Y p y p x y y p y p x y p x     , і для кожного об’єкта, зокрема  * argmax | i i i y Y y p y X x    . Тепер сформулюємо деякі припущення щодо структури ймовірнісної моде- лі, що розглядається. Припущення 1. Будемо вважати, що поле  1 | |,..., Vx x x складається з ви- падкових величин, умовно незалежних відносно прихованого поля першопричин Y, тобто    | |i i ip x y p x y . У цьому випадку ймовірнісні властивості поля Х, що спостерігається визначаються спільним умовним розподілом 1 ( | ) ( | ). V j j j j p x y p X x y    Іншими словами, повідомлення хі, що отримане з вузла іV, залежить лише від стану цього конкретного вузла yi і не залежить від повідомлень з інших об’єктів мережі. Підмножину вершин графа  ( ) :s s S    назвемо околом вершини s, якщо s s і для будь-якої вершини t s t тоді і тільки тоді, коли t s . Поз- начимо s множину «горизонтальних» сусідів вершини s, тобто ЗАСТОСУВАННЯ ІНСТРУМЕНТАРІЮ МАРКОВСЬКИХ ПОЛІВ … Теорія оптимальних рішень, 2016 5  ,ij kj kjs s s s s   . Розглядаючи деяку фіксовану вершину t, розіб’ємо її окіл на три підмножини: горизонтальних сусідів t , сусідів нижчого рівня t (  , ,ij kl klt t s s t l j      ) і, відповідно, сусідів вищого рівня t . У такому випадку t будемо розуміти лише сусідні до t елементи, що знаходяться на тому ж або нижчих рівнях (без врахування вищих), тобто t t t   (рисунок). t t1 t L1 L2 L3 РИСУНОК. Графічне зображення структури графа Припущення 2. Будемо вважати, що випадкове поле прихованих неполадок Y є одностороннім марковським, тобто для будь-якої вершини s V умовний розподіл ймовірностей ( | )sp y y на множині значень ys залежить лише від станів елементів поля, які належать околу s вершини s: ( | ) ( | )s s sp y y p y y . Перераховані вище припущення щодо структури ймовірнісної моделі кому- нікаційної мережі дозволяють сформулювати базовий алгоритм пошуку прихо- ваних першопричин неполадок. Пропонується рекурсивний алгоритм прохо- дження вершин графа, на кожному кроці якого для деякої вершини s розгляда- ється вплив на неї сусідніх елементів, розташованих на тому ж і нижчих рівнях. Перед тим як сформулювати алгоритм розглянемо допоміжну лему, необ- хідну для подальших розрахунків. Лема 1. Якщо випадкові величини  1 | |,..., Vx x , які спостерігаються, є умов- но незалежними відносно прихованого поля першопричин Y, а випадкове поле  1 | |,..., Vy y y є одностороннім марковським за відношенням до вершин нижчо- го рівня, тоді для умовного розподілу ймовірностей станів деякої вершини t справедливо О.С. САМОСЬОНОК, Г.Д. БIЛА, О.П. КНОПОВ 6 Теорія оптимальних рішень, 2016 1 ( | ) ( | ) ( | ) ( | ) ( | ) ( | )... ( | ) ( ) s s n s s t t t t t t s s st s z z sy Ys t p y y p y x p y x p y x p y x p x y p x y p y              , де 1 sz , 2 sz , …, s nz – горизонтальні сусіди вузла s. Доведення. Нехай для деякого прихованого стану yt елемента tV відомі ро- зподіли ймовірностей ( | )s sp y x , ysY, s t його сусідніх вузлів і отримано нове повідомлення про поломку yt. Застосуємо до вузла t формулу Байєса відно- сно гіпотез ( | )t tp y x , які утворюють повну групу подій після повідомлення xt: ( | ) ( | ) ( | , ) ( | ) ( | ) t t t t t t t t t t t t y Y p y x p x y p y x x p y x p x y        . (1) Також згідно з припущеннями моделі, в точці tV відомі апостеріорні роз- поділи ймовірностей ( | )t tp y x і апріорні ( )tp y . Застосуємо формулу Байєса до гіпотез yt після реєстрації повідомлень xt: ( ) ( | ) ( | ) ( ) ( | ) t t t t t t t t t y Y p y p x y p y x p y p x y     . Знайдемо звідси ( | )t tp y x і підставивши отримане значення в (1), з ураху- ванням того що 1 2 ( | ) ( | ) ( | ) ( | )... ( | ) kt t t t t t t t ttp y x p y x p y x p y x p y x  , де t1, t2, tk – горизонтальні сусіди t, отримаємо: ( | ) ( | ) ( ) ( | ) ( ) ( | , ) ( | ) ( | ) ( ) ( | ) ( ) t t t t t t t t t t t y Y t t t t t t t t t t ty Y y Y p y x p y x p y p x y p y p y x x p y x p y x p y p x y p y                         ( | ) ( | ) ( ) , ( | ) ( | ) ( ) t t t t t t t t t t ty Y p y x p y x p y p y x p y x p y            1 ( | )1 ( | , ) ( | ) ( | )... ( | ) ( ) k t t t t t t t t t tt t p y x p y x x p y x p y x p y x A p y   , (2) де ( | ) ( | ) ( ) t t t t t ty Y p y x A p y x p y           . ЗАСТОСУВАННЯ ІНСТРУМЕНТАРІЮ МАРКОВСЬКИХ ПОЛІВ … Теорія оптимальних рішень, 2016 7 Знайдемо ймовірність ( | )t tp y x . Зафіксувавши повідомлення , t x  застосу- ємо формулу Байєса до гіпотез ( ),tp y що створюють повну групу подій: ( ) ( | ) ( ) ( | ) ( | ) . ( ) ( | ) ( ) t t t t tt t t t t tt t y Y p y p x y p y p x y p y x p y p x y p x           (3) Так як ,st s t x x    то з урахуванням умовної незалежності спостережень спільний розподіл може бути записаний у наступному вигляді: 1 2 1 ( | ) ( | ) ( ,... | , ) ( | ) nt s t s s t s s tt s t p x y p x y p x x y x p x y        , (4) де s1, s2,…, sn – сусіди вузла t, що знаходяться на рівень нижче. Ймовірність ( | )s tp x y знайдемо з спільного розподілу ( , ) ( ) ( | ) :s t t s tp x y p y p x y  ( | ) ( , ) / ( ).s t s t tp x y p x y p y  (5) З іншого боку ( , ) ( , , ) ( ) ( , | ) ( ) ( | ) ( | ). s s s s t s t s s s t s s s s t s y Y y Y y Y p x y p x y y p y p x y y p y p x y p y y            Враховуючи останню рівність, (5) прийме наступний вигляд: 1 ( | ) ( ) ( | ) ( | ) ( ) s s t s t s s s t y Y p x y p y p y y p x y p y      ( ) ( | ) ( | ) ( | ) ( | ) ( ) s s s t s s s s t s s ty Y y Y p y p y y p x y p y y p x y p y        . (6) Для ( | ),s sp x y з урахуванням «горизонтального сусідства», справедлива наступна рівність: 1 2 1 2 ( | ) ( , , | ) ( | ) ( | )... ( | ) ( | ),s s s n s s z z s s s s ss sz z z p x y p x x x y p x y p x y p x y p x y     де 1 sz , 2 sz , …, s nz – горизонтальні сусіди вузла s. Щоб знайти останній множник ( | ),ss p x y  розглянемо апостеріорний роз- поділ ( | ),s s p y x  .s t Нехай sx – нові спостереження, запишемо формулу Байєса для спостережень у вузлі s: ( ) ( | ) ( | ) . ( ) s ss s s s p y p x y p y x p x     Звідси ( | ) ( ) ( | ) ( ) s s s ss s p y x p x p x y p y     . О.С. САМОСЬОНОК, Г.Д. БIЛА, О.П. КНОПОВ 8 Теорія оптимальних рішень, 2016 Підставивши отримані результати в (6), отримаємо 1 ( | ) ( ) ( | ) ( | ) ( | )... ( | ) ( ) s s n s s s s s t s t s sz z sy Y p y x p x p x y p y y p x y p x y p y       , 1 ( | ) ( | ) ( ) ( | ) ( | )... ( | ) ( ) s s n s s s s t s t s ss z z sy Y p y x p x y p x p y y p x y p x y p y       . (7) Тоді вираз (4) прийме наступний вигляд: 1 ( | ) ( | ) ( | ) ( ) ( | ) ( | )... ( | ) ( ) s s n s s s t s t s t s sst z z sy Ys t s t p y x p x y p x y p x p y y p x y p x y p y                 і, враховуючи останню рівність, перепишемо (3) як 1 ( ) ( | ) ( | ) ( ) ( | ) ( | )... ( | ) ( ) ( ) s s n s t s t t s s ss st z z sy Ys tt p y p y y p y x p x p y x p x y p x y p x p y            , 1 ( ) ( ) ( | ) ( | ) ( | )... ( | ) ( | ) ( ) ( ) s s n s s s t t t s s s s tst z z sy Ys tt p x p y p y x p y x p x y p x y p y y p x p y               .(8) Для ( )tp x враховуючи рівність (3) справедливо наступне:  ( ) ( ) ( | ) ( ) ( | ) t t t t t s ttt y Y y Y s t p x p y p x y p y p x y                . Підставимо сюди значення ( | )s tp x y з (7), отримаємо 1 ( | ) ( ) ( ) ( ) ( | ) ( | )... ( | ) ( ) s s n t s s s t s t s sst z z sy Y y Ys t p y x p x p y p x p y y p x y p x y p y                    1 ( | ) ( ) ( ) ( | ) ( | )... ( | ) ( ) s s n t s s t t s s ss s z z sy Y y Ys t s t p y y p y p x p y x p x y p x y p y                     1 ( | ) ( ) ( ) ( | ) ( | )... ( | ) ( ) s s n t s s t t s s ss s z z sy Y y Ys t s t p y y p x p y p y x p x y p x y p y                    . Отриманий вираз підставимо у (8): 1 1 ( | ) ( ) ( | ) ( | )... ( | ) ( ) ( | ) . ( | ) ( ) ( | ) ( | )... ( | ) ( ) s s n s s s n t s s t t s s ss z z sy Ys t t t s t t s s ss z z sy Y s t y Y p y y p y p y x p x y p x y p y p y x p y y p y p y x p x y p x y p y                                 ЗАСТОСУВАННЯ ІНСТРУМЕНТАРІЮ МАРКОВСЬКИХ ПОЛІВ … Теорія оптимальних рішень, 2016 9 І тоді (2) прийме остаточний вигляд 1 1 ( | , ) ( | )... ( | ) ( | ) kt t t t t t t t tp y x x p y x p y x p y x B    1 ( | ) ( | ) ( | )... ( | ) ( ) s s n s s t s s ss z z sy Ys t p y y p y x p x y p x y p y           , де 1 ( | ) ( ) ( | ) ( | )... ( | ) ( ) s s n t s s t t s s ss z z sy Y y Ys t p y y B p y p y x p x y p x y p y                 . Лему доведено. Перейдемо до рекурсивного алгоритму пошуку причини мережевого збою. 1. Розглянемо елемент мережі t ( ty Y ), в якому зафіксовано повідомлення про збій. Вважається, що для таких вузлів на цьому етапі розподіл ( ) ( | ).t t tp y p y x Далі для всіх iV, починаючи з сусідів елемента t, розрахову- ються апріорні розподіли: ( ) ( | ) ( ), j i i j j y Y p y p y y p y    iy Y , i j . 2. На другому етапі, починаючи з елементів найнижчого рівня, рекурсивно підіймаючись до елемента t розраховуємо апостеріорні розподіли ( | ) ( | ) ( | )i i i i ip y x p y x p y x , iy Y , iV, де згідно леми 1 1 1 ( | ) ( | ) ( | )... ( | ) ( | ) ( | )... ( | ) ( ) s s m n s s t t t t t t t s s ss z z sy Ys t p y y p y x p y x p y x p y x p x y p x y p y             . Припускається, що апостеріорні розподіли ймовірностей ( | )i ip y x , ( | ),i jp y x i j відомі. 3. Таким чином, у результаті проходженні по всіх вузлах графа, розподіл ймовірностей станів вершини t враховує всі повідомлення ( | ) ( | )t t tp y x p y x  , .ty Y Такий апостеріорний розподіл ймовірності станів деякого елемента дозволяє прийняти рішення про поломку *( ) argmax ( | ) t t t y Y y x p y x   . 4. Далі для всіх інших вершин jV топологічного графа розраховуємо апос- теріорні розподіли ( | )ip y x ( | ) ( | , ) ( | ) j i i j j y Y p y x p y y x p y x    , iy Y , i j , О.С. САМОСЬОНОК, Г.Д. БIЛА, О.П. КНОПОВ 10 Теорія оптимальних рішень, 2016 ( | ) ( | , ) ( | ) ( ) ( ) i j i j i i j i p y y p y y x p y x p x p y  , і приймаємо рішення про їх приховані стани yi: *( ) argmax ( | ) i i i y Y y x p y x   . Аналогічний байєсівський підхід для задачі розпізнавання образів вико- ристано в статті [2]. Висновок. У роботі запропоновано рекурсивний алгоритм проходження вершин графа, на кожному кроці якого для деякої вершини розглядається вплив на неї сусідніх елементів, розташованих на тому ж і нижчих рівнях. Цей резуль- тат дає можливість ідентифікувати приховані першопричини збоїв у роботі ко- мунікаційної мережі. А.С. Самосенок, Г.Д. Била, А.П. Кнопов ПРИМЕНЕНИЕ ИНСТРУМЕНТАРИЯ МАРКОВСКИХ ПОЛЕЙ ДЛЯ ПОИСКА ПРИЧИНЫ СЕТЕВОГО СБОЯ Рассмотрено модель коммуникационной сети на основе марковских полей и задача иденти- фикации скрытых поломок сети на основе байесовского принципа распознавания. Предложен рекурсивный алгоритм идентификации скрытых первопричин неполадок работоспособности коммуникационной сети при наличии сообщений о сбое, которые зарегистрированы в сосед- них узлах топологического графа сети. O.S. Samosonok, G.D. Bila, A.P. Knopov USAGE OF MARKOV RANDOM FIELDS FOR ROOT COUSE DETERMINATION OF NETWORK FAULT The model of the communication network based on Markov fields is considered along with the problem of identification of hidden network’s fault based on Bayesian principle of recognition. A recursive algorithm for identifying the root causes of communication system faults is suggested based on analysis of the fault messages registered in the neighboring nodes of the network topological graph. 1. Самосёнок А.С. Методы автоматической обработки неполадок в компьютерных сетях // Компьютерная математика. – Киев: Ин-т кибернетики имени В.М. Глушкова НАН Украи- ны, 2011. – № 2. – С. 74 – 80. 2. Голодников А.Н., Кнопов П.С., Пепеляев В.А. Некоторые подходы к задаче распознавания образов // Кибернетика и системный анализ. – 2007. – № 6. – С. 55 – 69. Одержано 01.04.2016

Ähnliche Einträge