Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід

В роботі розглянуто еволюційно-ігрову модель мережевої взаємодії. На сьогодні в мережі Інтернет існує велика кількість протоколів передачі даних, що різняться за якістю сервісу для кінцевого користувача. Процес вибору оптимального протоколу може бути розглянутий як математична гра, в якій гравці (ко...

Full description

Saved in:

Bibliographic Details
Date:	2014
Main Authors:	Ігнатенко, О.П., Синецький, О.Б.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2014
Series:	Проблеми програмування
Subjects:	Прикладні засоби програмування та програмне забезпечення
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/113608
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід / О.П. Ігнатенко, О.Б. Синецький // Проблеми програмування. — 2014. — № 4. — С. 67-77. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-113608
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1136082025-02-10T00:07:21Z Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід Conflict controlled network modeling: evolutionary games approach Ігнатенко, О.П. Синецький, О.Б. Прикладні засоби програмування та програмне забезпечення В роботі розглянуто еволюційно-ігрову модель мережевої взаємодії. На сьогодні в мережі Інтернет існує велика кількість протоколів передачі даних, що різняться за якістю сервісу для кінцевого користувача. Процес вибору оптимального протоколу може бути розглянутий як математична гра, в якій гравці (користувачі) прагнуть до максимізації свого виграшу (пропускної здатності). В даній статті представлена модель мережевої взаємодії, що базується на диференційних рівняннях з розривною правою частиною, сформульовано матрицю виграшів для гри та знайдено умови існування рівноваги у вигляді обмежень на параметр чутливості до помилок. Результати підтверджено за допомогою симуляції. 2014 Article Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід / О.П. Ігнатенко, О.Б. Синецький // Проблеми програмування. — 2014. — № 4. — С. 67-77. — Бібліогр.: 12 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/113608 004.7 uk Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення
spellingShingle	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення Ігнатенко, О.П. Синецький, О.Б. Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід Проблеми програмування
description	В роботі розглянуто еволюційно-ігрову модель мережевої взаємодії. На сьогодні в мережі Інтернет існує велика кількість протоколів передачі даних, що різняться за якістю сервісу для кінцевого користувача. Процес вибору оптимального протоколу може бути розглянутий як математична гра, в якій гравці (користувачі) прагнуть до максимізації свого виграшу (пропускної здатності). В даній статті представлена модель мережевої взаємодії, що базується на диференційних рівняннях з розривною правою частиною, сформульовано матрицю виграшів для гри та знайдено умови існування рівноваги у вигляді обмежень на параметр чутливості до помилок. Результати підтверджено за допомогою симуляції.
format	Article
author	Ігнатенко, О.П. Синецький, О.Б.
author_facet	Ігнатенко, О.П. Синецький, О.Б.
author_sort	Ігнатенко, О.П.
title	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід
title_short	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід
title_full	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід
title_fullStr	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід
title_full_unstemmed	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід
title_sort	моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід
publisher	Інститут програмних систем НАН України
publishDate	2014
topic_facet	Прикладні засоби програмування та програмне забезпечення
url	https://nasplib.isofts.kiev.ua/handle/123456789/113608
citation_txt	Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід / О.П. Ігнатенко, О.Б. Синецький // Проблеми програмування. — 2014. — № 4. — С. 67-77. — Бібліогр.: 12 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT ígnatenkoop modelûvannâkonflíktnoívzaêmodíívmerežahevolûcíinoígroviipídhíd AT sinecʹkiiob modelûvannâkonflíktnoívzaêmodíívmerežahevolûcíinoígroviipídhíd AT ígnatenkoop conflictcontrollednetworkmodelingevolutionarygamesapproach AT sinecʹkiiob conflictcontrollednetworkmodelingevolutionarygamesapproach
first_indexed	2025-12-02T00:20:19Z
last_indexed	2025-12-02T00:20:19Z
_version_	1850353721628688384
fulltext	Прикладні засоби програмування та програмне забезпечення © О.П. Ігнатенко, О.Б. Синецький, 2014 ISSN 1727-4907. Проблеми програмування. 2014. № 4 67 УДК 004.7 О.П. Ігнатенко, О.Б. Синецький МОДЕЛЮВАННЯ КОНФЛІКТНОЇ ВЗАЄМОДІЇ В МЕРЕЖАХ: ЕВОЛЮЦІЙНО-ІГРОВИЙ ПІДХІД В роботі розглянуто еволюційно-ігрову модель мережевої взаємодії. На сьогодні в мережі Інтернет іс- нує велика кількість протоколів передачі даних, що різняться за якістю сервісу для кінцевого користу- вача. Процес вибору оптимального протоколу може бути розглянутий як математична гра, в якій гравці (користувачі) прагнуть до максимізації свого виграшу (пропускної здатності). В даній статті представ- лена модель мережевої взаємодії, що базується на диференційних рівняннях з розривною правою час- тиною, сформульовано матрицю виграшів для гри та знайдено умови існування рівноваги у вигляді об- межень на параметр чутливості до помилок. Результати підтверджено за допомогою симуляції. Вступ Теорія ігор широко застосовується для дослідження інформаційних мереж. Існуючі застосування ігрових моделей до розв’язання проблем у мережах охоплю- ють задачі маршрутизації, розподілу ресурсів, пошуку точки рівноваги мережі та аналізу стійкості роботи протоколів. Такого роду системи, як правило, надають послуги великій кількості користувачів, при цьому їх ресурси (пропускна здат- ність, буфери, потужність вузлів) обме- жені. Користувачі (люди, програми, сер- віси) є неоднорідними у своїх запитах і можуть діяти непередбачуваним чином. Необхідність розділяти ресурси між кон- куруючими користувачами ефективним (максимально використовуючи можливо- сті системи) та справедливим (максима- льно задовольняючи користувачів) чином ставить перед дослідниками складні про- блеми. Математичний апарат теорії ігор, розроблений для аналізу взаємодії декіль- кох учасників виявився виключно придат- ним для опису процесів, які відбуваються у мережах, зокрема транспортній або теле- комунікаційній – в першу чергу через те, що сама предметна область у цьому випа- дку припускає наявність незалежних аген- тів, що прагнуть максимізувати власний виграш – чи то якомога швидше дістатися до пункту призначення, чи найбільш шви- дко і надійно передати дані. Відомі застосування ігрового підхо- ду у комп’ютерних мережах до таких проблем як керування потоками даних [1, 2], мережева маршрутизація [3, 4], балансування навантаження [5], розподіл ресурсів [6] та забезпечення якості обслу- говування [7]. Втім, оскільки при аналізі взаємодії користувачів мережі набагато частіше мова йде про підмножини агентів зі спільними ознаками, що співіснують в одному середовищі природно формалізо- вувати цю задачу в термінах теорії еволю- ційних ігор. Еволюційна гра – різновид матема- тичної ігри, в якій розглядається взаємодія не окремих гравців, а цілих популяцій, або ж груп у межах однієї популяції. Уперше така термінологія була введена Дж. Смітом у роботі [8] для дослідження біологічних процесів, звідки й була успадкована термі- нологія: «популяція», «еволюція», «мутан- ти». Як аналог рівноваги за Нешем в ево- люційних іграх запропоновано поняття «еволюційно стабільної стратегії» (ЕСС) – такого розподілу стратегій окремих осіб, що є сталим за часом і стійким до мутацій, тобто поява невеликої кількості гравців з незвичною стратегією не призводить до зміни структури популяції. Формалізм еволюційних ігор ви- явився зручним для моделювання проце- сів за межами біології, зокрема, в еко- номіці [9]. Дана робота пов’язана з засто- сування апарату теорії еволюційних ігор до розв’язання задачі знаходження поло- ження рівноваги в комп’ютерній мережі. Справа в тому, що множину користувачів мережі можна розглядати як популя- цію, члени якої конкурують за спільний Прикладні засоби програмування та програмне забезпечення 68 ресурс (в даному випадку – пропускну здатність), використовуючи при цьому одну з визначених стратегій поведінки (алгоритмів передачі даних). В такому випадку рівновага може бути описана як ЕСС популяції. Проблемі пошуку такого стану та умов його існування присвячено роботи [10–12]. Зокрема, в [10] розглядається еволюційно-ігровий підхід до вибору оптимального алгоритму контролю заван- таженості в бездротових мережах на прик- ладі конкуренції двох користувачів, кожен з яких має змогу обирати з двох AIMD- алгоритмів – «агресивного» і «мирного». Доведено наявність ЕСС в такій грі для різних співвідношень виграшів і дослідже- но вплив параметрів мережі на швидкість досягнення рівноваги. В даній роботі поглиблюється та узагальнюється результат, отриманий у [10], в частині знаходження умов існу- вання рівноваги в змішаних стратегіях для моделі взаємодії багатьох типів AIMD-з’єднань. Успішне розв’язання цієї задачі дозволить оптимізувати роботу протоколу TCP і характеристики можли- вих станів мережі за умов конкуренції користувачів. В результаті побудовано модель еволюційної гри і знайдено точку рівно- ваги, яку досліджено на предмет відпо- відності умовам еволюційної стабільнос- ті. Виявляється, що тип рівноваги сильно залежить від параметрів, що характери- зують протоколи і поведінку користува- чів. В роботі представлено умови, що пов’язують ці параметри. Основною ди- намічною характеристикою системи в даній моделі є частка користувачів, що використовують певний вид протоколу. Значення 1 або 0 цієї величини відповідає стану рівноваги у чистих стратегіях, вод- ночас як інші значення з проміжку (0, 1) – рівновазі у змішаних стратегіях. Дина- міка зміни кількості користувачів у часі залежить від їх функції корисності і моде- люється реплікаційним рівнянням. Для ілюстрації теоретичних результатів у ро- боті представлений чисельний розв’язок цього рівняння для різних значень пара- метрів, виконаний у системі Wolfram Mathematica. 1. Модель Розглянемо мережу, що складаєть- ся з M робочих вузлів, з’єднаних у певну топологію. Кожен вузол має принаймні одну сервісну ланку, причому сумарна потужність сервісних ланок обмежена константою. Позначимо сервісну потуж- ність вузлів ip , Mi ,...,1 , де I , K – множини індексів вузлів },...,1{ M та сер- вісних ланок },...,1{ L відповідно. Розгля- немо N користувачів, з’єднаних з мере- жею. Ми вважаємо, що мета користу- вачів полягає у передачі певного обсягу даних через мережу. Позначимо )(tx j швидкість передачі j -го користувача, де },...,1{ NJj  . Оскільки швидкість пе- редачі даних не може бути від’ємною, то для вектора швидкостей  Nxxx ,...,1 виконується x NR . Якщо сума швид- костей потоків даних, що використову- ють ланки певного вузла перевищать йо- го потужність відбудеться переповнення (подія, наслідком якої буде втрата паке- ту користувача). Ця схема є ідеалізацією відомого алгоритму Droptail. Будемо вважати, також, що маршрутизація є детерміністичною, а інформація про втра- ту пакету надходить до користувача мит- тєво. Позначимо )(tuk , Kk швидкість обслуговування k -ої ланки. Визначимо матрицю C наступним чином: ijc дорів- нює 1 якщо i -а ланка належить j -му вузлу і 0 в іншому разі. Використовуючи цю матрицю визначимо множину U як  1\|   CuRu K . Множина U містить всі можливі набори швидкостей обслугову- вання мережі. Нехай P = },...,{ 1 Mppdiag – діагональна матриця. Матриця маршрути- зації R – це матриця розмірності MM  , елемент ijr , Pji , дорівнює 1 якщо вихід i -ї ланки є входом j -ї ланки і 0 в іншому разі. Матриця A є матрицею розмірності NL , елемент ija , ,Ki Jj дорівнює 1 якщо j користувач Прикладні засоби програмування та програмне забезпечення 69 використовує i ланку і 0 в іншому разі. Важливим результатом є визначення умов які б гарантували стабільну роботу систе- ми, тобто умови за яких у системі не виникають переповнення. Твердження 1.1. (Умова стабільно- сті) Якщо вектор швидкостей )(tx , ],[ 10 ttt задовольняє умові 1)(  tx , де матриця   ARCP M k kT     1 0 1 , то в системі не виникає переповнення. Доведення. Нехай )(tx – вектор швидкостей користувачів. Мережа намага- ється розподілити власні ресурси (вектор )(tu ) так, щоб найкраще обслужити кори- стувачів: 0)()()(  tuPRItAx T . Це завжди можливо, якщо UxARIPtu T   11 )()( , де обернена матриця визначена як степеневий ряд      1 0 1][ M k kRRI (відома властивість матриці маршрутизації). Умова стійкості є формальним виразом наступного вклю- чення: UxARIP T int)( 11   , границя множини U була виключена з розгляду щоб попередити подію переповнення. Проілюструємо цей результат на деяких класичних прикладах. 1.1. Приклади Single server. Найпростіша можли- ва топологія мережі. Розглянемо один вузол з потужністю p , 1 LM . До мережі під’єднані N користувачів з швид- костями T N txtxtx ))(),...,(()( 1 . A  11  , множина  RpU ],0[ . Для даної системи        p 1 і умова стабільно- сті записується у вигляді )(1 tx ptxN  )( . Klimov model. Розглянемо модель, показана на рис. 1. N користувачів з век- тором швидкостей T N txtxtx ))(),...,(()( 1 використовують N ланок, розташованих на одному вузлі. Кожна ланка має макси- мальну швидкість обробки jp , Nj ,..,1 та )(tu j – відсоток використання спільно- го ресурсу (напр., час CPU, пропускна здатність). Враховуючи, що  11 C ,            Np p P    0 01 отримуємо:  1\| 1    uCPRuU K =         1\| 1 1 N NK p u p u Ru  . )(1 tx )(txN )(1 tu )(tuN  Рис. 1. Топологія мережі Klimov model Матриця IA  , тому        Npp 11 1  і умова стабільності задається формулою 1 )()( 1 1  N N p tx p tx  . Re-entrant line. Розглянемо більш складну топологію, показану на рис 2. )(1 tx )(txN )(1 tu )(3 tu )(2 tu  Рис. 2. Топологія мережі Re-entrant line В даній моделі N користувачів з вектором швидкостей ),...(()( 1 txtx  T N tx ))(..., надсилають свої пакети на першу ланку першого вузла з максималь- Прикладні засоби програмування та програмне забезпечення 70 ною пропускною здатністю 1p та парамет- ром керування ]1,0[)(1 tu . Після цього пакети потрапляють на другий вузол з однією ланкою потужності 2p та парамет- ром керування ]1,0[)(2 tu . Після обробки пакети повертаються на другу ланку пер- шого вузла (з параметрами 3p та ]1,0[)(3 tu ) та покидають систему. Ланки 1 та 2 розташовані на одному вузлі, тому їх сумарна потужність обмежена. Визначимо матриці і множину U для даної мережі:            3 2 1 00 00 00 p p p P ,        010 101 C ,            00 00 11    A ,         22 3 3 1 13 ,1\| pu p u p u RuU . Матриця маршрутизації дорівнює            010 001 000 TR , і             111 011 001 )( 1 TT RIRI . Нарешті,               22 3131 11 1111 pp pppp   і умова стабільності складається з двох нерівностей:   1)()( 11 1 31        txtx pp N ,   21 )()( ptxtx N  . Якщо вектор x задовольняє цим не- рівностям, втрат у мережі не виникатиме. 1.2. Динамічна модель AIMD Існують різні реалізації TCP алго- ритму. Найбільш вживаний на сьогодні варіант, що називається New Reno ТСР. Його поведінка досить близька до AIMD. New Reno збільшує розмір вікна лінійно на  пакетів за кожен період і, якщо виявле- на подія переповнення, зменшує розмір вікна в  раз. Константи  та  дорів- нюють 1 та 1/2, відповідно. Специфікація TCP не забороняє користувачам використовувати інші ме- ханізми контролю перевантажень. Напри- клад, при використанні AIMD схеми ко- ристувач може змінювати значення  та  . Очевидно, якщо визначити  та  більшими за стандартні налаштування (1, 1/2), можна отримати перевагу над з’єднаннями інших користувачів. Це призведе до несправедливого розподілу ресурсів і тому не є бажаним. Така взає- модія протоколів називається «недруж- ньою» при цьому говорять, що перший протокол є більш «агресивним», а інші – більш «миролюбними». Під агресивністю у даному контексті розуміється можли- вість захопити більшу частку ресурсів мережі ніж належить даному користувачу за справедливого розподілу. Питання взаємодії протоколів є достатньо склад- ним, тому побудова аналітичної моделі, яка б передбачала поведінку мережі є нагальною проблемою. Останнім часом виникли більш аг- ресивні версії TCP такі як: HSTCP (High Speed TCP) та Scalable TCP. HSTCP мо- же моделюватись AIMD схемою, де  і  не константи: мінімальні значення  і  дорівнюють 1 і 1/2, відповідно. Зі збі- льшенням вікна вони додатково збільшу- ються. Scalable TCP є MIMD (Multiplicative Increase Multiplicative Decrease) протоко- лом, де розмір вікна збільшується експо- ненціально, а не лінійно, і тому більш агресивно. Існують також версії TCP, які менш агресивні за New-Reno, наприклад Vegas. Побудуємо динамічну модель AIMD з’єднання на основі теорії диферен- ціальних рівнянь з розривною правою частиною. Нехай 0x початковий вектор Прикладні засоби програмування та програмне забезпечення 71 швидкостей,  ,  вектори параметрів протоколу. Відповідно до AIMD схеми швидкості користувачів зростають між подіями переповнення з швидкістю  . При переповненні відбувається стрибок швидкості в сторону зменшення, новий набор дорівнює x . Визначимо it , 1i – перший момент часу 1 ii tt , такий, що існує індекс Jj :   1)(  jitx . Будемо вва- жати, що всі з’єднання знаходяться у рів- них умовах, втрати синхронізовані і коли сумарна швидкість досягає обмеження, падіння відбувається у всіх з’єднань. Розглянемо рівняння     tN i ii tttxBItx 1 )()()(  , (1) де  – Діраковська дельта-функція, },...,{ 1 NdiagB  , }:max{ ttnN nt  . Рівняння (1) є рівнянням Каратеодорі з розривною правою частиною (імпульсною правою частиною). Відомо, що це рівняння має майже неперервний розв’язок (непере- рвний скрізь окрім множини міри нуль)     tN i ii tttxBIttx 1 )()()(  , (2) де  – функція Хевісайда. Явна формула (2) не надто практична, але надає важливу інформацію щодо існування розв’язку та його властивостей. 2. Основний результат Введемо множину V за формулою   JjvRv j N   ,1min\|  та множину W =  1\|   wRw N  . Зрозуміло, що V – компакт, W – опуклий компакт, і WV  . Умова 1. Для будь-якої точки Vx виконується WBx int . Ця умова означає, що після застосу- вання оператора B швидкості гравців не покидають допустиму множину. Для фор- мулювання та доведення головного ре- зультату нагадаємо необхідні визначення. Множина nRX  гомеоморфна множині mRY  , якщо існує бієктивне неперервне відображення YXh : , таке, що 1h існує і також неперервне. Множина точок mn Rxx },...,{ 0 називається афінно неза- лежною, якщо з виконання рівностей 0 0   i n i ix та 0 0   n i i випливає, що 0...0  n . N-вимірним симплексом називаєть- ся множина всіх додатних опуклих комбі- націй 1n афінно незалежних точок. Позначимо n замикання стандартного n- вимірного симплексу:           1;,...,0,0\| 0 1 n i ii n yniyRy . Теорема (Брауер) [12]. Нехай множина nRX  є гомеоморфною симплексу 1n і відображення XXf : є неперервним. Тоді f має нерухому точку, тобто існує Xx така, що xxf )( . Тепер сформулюємо основний резуль- тат – про існування та єдність граничного розв’язку. Твердження 2. Розглянемо допустиму пару векторів  ,  . Якщо виконується умова 1, то для будь-якого Wx 0 розв’язок існує та сходиться до єдиного періодичного розв’язку )(ˆ tx . Доведення. Розглянемо відображення VVf : , визначене за формулою  ytBvtVyvf  :0\|)( . Умова 1 виконується, тому )(f визначене для будь-якої точки з V і не виводить за межі цієї множини. За визначенням )(f – непе- рервне відображення. Розглянемо симп- лекс 1N побудований на точках Nee ,...,1 , де ie – це вектори стандартного базису. Для кожної точки Vx існує єдиний вектор 1 N , такий, що ax  для деякого числа Ra . Це озна- чає, що V гомеоморфна 1N , тому вико- нані умови теореми Брауера і існує неру- хома точка Vx * відображення )(f . Позначимо  вектор з компонентами Прикладні засоби програмування та програмне забезпечення 72 i i i      1 . За визначенням нерухомої точки виконується рівність ** xTxB  , де }:min{ * VtxtT   . Обчислимо x : TTBIx   1 )( . Умова VTx * може бути перепи- сана як   1min *  i i x або 1)(min  i i T , тому T визначається однозначно і неру- хома точка єдина. Розв’яжемо рівняння (1) з початкового стану xB . Зрозуміло, що )(ˆ xBttx  для ),0[ Tt і )0(ˆ)(ˆ xTx  . Отже, розв’язок )(ˆ tx є періодичним з періодом T . Розглянемо довільний розв’язок з початкового стану Wx )0( . Нехай )( 1tx – перший момент часу, коли Vtx )( 1 , визначимо )( 1 nn zfz , ))(( 10 txfz  . Всі елементи послідовності }{ nz ,  ,...,0n належать компакту V , отже існує гранична точка Vx~ , )~(~ xfx  . Єдиний можливий розв’язок, пов’язаний з цією граничною точкою – )(ˆ tx . Отже, будь-який розв’язок сходиться до )(ˆ tx . Застосуємо теорему до розв’язку прикладів. Позначимо T – період коли- вань розв’язку, x – нерухома точка. Single server. Зауважимо, що        pp 11  , тому умова Vx перепи- сується у вигляді 11  p x p x N . Нехай Vx  нерухома точка, тоді Tx T N N             11 1 1*  , і 1)( *  TBxA  . Розв’язуючи систему лінійних рівнянь, отримуємо: N N p T         11 1 1  . Зауважимо, якщо всі  i ,  i , то   N p T )1(   , N p xi  * . Klimov model. Матриця        Npp 11 1  , тому умова Vx переписується у вигляді 1 1 1  N N p x p x  . Нерухома точка є розв’язком системи рівнянь: 1)( 1          N i i i i ii T pp x TBx   , Tx T N N             11 1 1  . Результат: NN N pp T )1()1( 1 11 1          ,            NN N i i i pp x )1()1( )1( 11 1 *        . Re-entrant line.               22 3131 11 1111 pp pppp    . Нерухома точка є розв’язком сис- теми рівнянь: 1)(  TBx  , Tx T N N             11 1 1  . Результат           i i i ppp T 312 11 , 1 max )1( 1   , Tx i i i )1( *     . Прикладні засоби програмування та програмне забезпечення 73 3. Ігрова модель Розглянемо тепер конкуренцію між користувачами та побудуємо ігрову мо- дель їх взаємодії. скільки було доведе- но існування періодичного рішення для мереж, що розглядаються, то при побудо- ві гри будемо вважати, що мережа зада- на потужністю c . Визначимо N стратегій is з параметрами ),( ii  , Ni ,...,1 . Не- хай S – множина всіх допустимих страте- гій. Будемо розглядати функцію виграшу у вигляді )()()( sRsThpsJ ii  , де ),...,( 1 Nsss  – вектор стратегій, )1(5.0)( iii xsThp  – усереднена швид- кість i -го гравця;  – параметр чутливо- сті до втрат; )( 1 )( sT sR  – інтенсивність втрат. Приклад. Обчислимо виграші для двох стратегій: c cssJssJ ii iiii    2 4 )1( ),(),( 21    ,  21 21 11 211 )(2 )1( ),(         c c ssJ ,  21 21 22 121 )(2 )1( ),(         c c ssJ , ),(),( 121212 ssJssJ  , ),(),( 211122 ssJssJ  . 3.1. Рівновага у грі з N протоколами Розглянемо гру, в якій кожен кори- стувач може вибирати одну з N AIMD стратегій, після чого його виграш обчис- люється у залежності від усього вектору s . Будемо вважати, що всі is впорядковані таким чином Nsss  ...21 , де ji ss  означає, що ji   і ji   . Іншими словами стратегії відсортовані у порядку зменшення агресивності. Твердження 3.1. Якщо  достат- ньо мале, агресивний протокол є доміную- чою стратегією. Доведення. Нехай i 1 , i 1 для всіх Ni ,...,2 . Розглянемо виграші першого гравця для різних стратегій – ),( 111 ssJ і ),( 11 ssJ j . Обчислимо виграші для кожного з випадків: A c ssT   1 11 ),(  , де  k kA  – сума, визначена множиною стратегій ),..,( 21 Nsss  , A c ssT j j    ),( 1 . Зрозуміло, що ),(),( 111   ssTssT j .    2 )1( ),( 11 111 x ssThp  )/1(2 )1( )(2 )1( 1 1 1 11     A c A c       , )/1(2 )1( 2 )1( ),( * 11 j jjj j A cx ssThp        .  A c ssThpssJ   1111111 ),(),(   ,  A c ssThpssJ jjj     ),(),( 1111 . Запишемо умову домінування пер- шої стратегії:   A c ssThp 1111 ),(    A c ssThp jj     ),( 11 , 1 11 1 )/1(2 )1( )/1(2 )1(       cA c A c j       ,               )/1(2 )1( )/1(2 )1( 1 1 1 2 j j A c A cc       . Оскільки вираз праворуч більше за нуль, то твердження доведене. Прикладні засоби програмування та програмне забезпечення 74 3.2. Рівновага за Нешем у грі з двома протоколами З визначення функцій виграшу ви- пливає, що ),(),( kkjkki ssJssJ  , тому в цьому випадку будемо опускати індекс і позначати виграш ),( kk ssJ . Аналогічно .\}2,1{),,(),(),( ijssJssJssJ pkkpjpki  Матриця виграшів цієї гри наведена в таблиці. Таблиця Strategy 1s 2s 1s ),( 11 ssJ , ),( 11 ssJ ),( 21 ssJ , ),( 12 ssJ 2s ),( 12 ssJ , ),( 21 ssJ ),( 22 ssJ , ),( 22 ssJ Використовуючи стандартні мето- ди обчислення рівноваги за Нешем отри- муємо: ),()1(),()( 211111 ssJpsspJsJ  , ),()1(),()( 221221 ssJpsspJsJ  , де p – ймовірність використання другим гравцем першої стратегії. Система пере- буває в точці рівноваги за Нешем, якщо ці дві величини рівні, що призводить до наступного рівняння: ),()1(),( 2111 ssJpsspJ  = ).,()1(),( 2212 ssJpsspJ  Розв’язуючи яке ми отримуємо: . ),(),(()),(),( ),(),( 11122221 2221 ssJssJssJssJ ssJssJ p    Враховуючи, що p – це ймовір- ність, потрібно накласти природні обме- ження 10  p , де крайні випадки 1p або 0p відповідають рівновазі у чистих стратегіях (з домінуючою стратегією 1s та 2s , відповідно), а 10  p відповідає рів- новазі у змішаних стратегіях. Записуючи умови для останньої нерівності: c ssJssJ )( ),(),( 21 2221    + )(2 )1( 12 11      c + c 22 + )1( 4 1 2c . c ssJssJ )( ),(),( 12 1112    + + )(2 )1( 21 22    c + c 12 + )1( 4 1 1c . Підставляючи, отримуємо,     )1()1( )1(2 1 2112 12   p ))(1( )1()(4 211 2 2 1 2 21      c c + )1)(1( 4 21 2 2     c . Розглядаючи випадок, коли гра має рівновагу у чистих стратегіях, потрібно записати дві рівності: 1p і 0p , одна з яких має виконуватися. Розв’язуючи дані рівняння ми зна- ходимо  , які забезпечують домінуючу стратегію. Твердження 3.2. Якщо параметр  за- довольняє нерівності       )(4 ))12()1(( 2 1 2 2 2 2 2 1 211212121 2c )(4 ))1()21(( 2 1 2 2 2 2 2 1 212212121 2      c , то в грі існує рівновага за Нешем у зміша- них стратегіях. Якщо досягається рівність, то існує рівновага за Нешем у чистих стратегіях. 4. Чисельне моделювання 4.1. Моделювання динамічної системи Чисельне моделювання виконано у се- редовищі Wolfram Mathematica. На рис. 3 показана збіжність розв’язку AIMD систе- ми до стаціонарного стану для двох і трьох вимірів. Прикладні засоби програмування та програмне забезпечення 75 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 Рис. 3. Результати моделювання 4.2. Реплікаційна динаміка Реплікаційна динаміка дозволяє до- слідити динамічні властивості протікання гри та досягнення точки рівноваги. Мно- жина користувачів представлена певною популяцією, що вибирає між стратегіями поведінки. Частка популяції, що вибрала певну стратегію відповідає змішаній стра- тегії у матричній грі. При цьому частка, що вибирає певну стратегію змінюється з часом відповідно до різниці між виграша- ми від використання даної стратегії і сере- днім за популяцією. Більш формально розглянемо N стратегій. Нехай ix – часта загальної популяції, що використовує стратегію is . Отже, 1)(  i i tx , 0)( txi . Реплікаційне рівняння визначається як:             j jk kj ij jii xkjJtxxjiJKtxtx ),()(),()()( Дослідимо випадок 3N , який ге- нерує досить нетривіальну динаміку і водночас може бути добре ілюстрова- ний. Рівняння динаміки мають наступний вигляд:  ),()())(,( 1111 ssJtxtXsJ  ),,()(),()( 313212 ssJtxssJtx    )(,(()()( tXiJKtxtx ii  )())(,()( 211  txtXsJtx ))).(,()()(,( 121   tXsJtxtXsJ На рис. 4–8 далі показані графіки відносних часток популяції, що викори- стовують відповідну стратегію для гри, що визначається табличними парамет- рами: 1 2 3 1 2 3  K c  1.5 1.25 1 0.75 0.5 0.25 168 0.2 50 0.25 10 20 30 40 50 0.0 0.2 0.4 0.6 0.8 Рис. 4. )(1 tx , )(2 tx , )(3 tx 1 2 3 1 2 3  K c  1.5 1.25 1 0.75 0.5 0.25 140 0.2 50 0.25 10 20 30 40 50 0.0 0.2 0.4 0.6 0.8 1.0 Рис. 5. )(1 tx , )(2 tx , )(3 tx Прикладні засоби програмування та програмне забезпечення 76 1 2 3 1 2 3  K c  1.5 1.25 1 0.75 0.5 0.25 168 0.2 50 15 20 40 60 80 100 0.0 0.2 0.4 0.6 0.8 Рис. 6. )(1 tx , )(2 tx , )(3 tx Розширимо динаміку на більш загаль- ний випадок:   p q qp qpAJtxtxtXsJ ),,()()())(,( 1  1 2 3 1 2 3  K c  1.3 1.5 1.1 0.25 0.4 0.85 140 0.25 50 5 50 100 150 200 0.2 0.4 0.6 0.8 Рис. 7. )(1 tx , )(2 tx , )(3 tx 1 2 3 1 2 3  K c  1.5 1.25 1 0.75 0.5 0.25 140 0.25 50 5 50 100 150 200 0.0 0.2 0.4 0.6 0.8 Рис. 8. )(1 tx , )(2 tx , )(3 tx Висновки В роботі розглядається підхід до моделювання конфліктних процесів у мережі на основі еволюційно-ігрового підходу. Запропонована динамічна ігро- ва модель з використанням рівнянь з розривною правою частиною та доведе- но існування та єдність розв’язку. Для гри AIMD з’єднань побудована платіжна матриця та знайдені умови існування рівноваги за Нешем в залежності від па- раметру чутливості до помилок. Резуль- тати підтверджено за допомогою чисель- ного моделювання. 1. Chiu, Dah-Ming, and Raj Jain. Analysis of the increase and decrease algorithms for con- gestion avoidance in computer networks. Computer Networks and ISDN systems 17.1 (1989): 1–14. 2. Kelly, Frank P., Aman K. Maulloo, and Da- vid KH Tan. "Rate control for communica- tion networks: shadow prices, proportional fairness and stability" // Journal of the Oper- ational Research society. 1998. – P. 237–252. 3. Mo J., Walrand J. Fair end-to-end window- based congestion control // IEEE/ACM Transactions on Networking. – 2000. – 8. – P. 556–567. 4. Paganini F., Doyle J.C., Low S.H. Scalable laws for stable network congestion control // Proc. of IEEE Conference on Decision and Control. – 2001. – 1. – P. 185–190. 5. Low S.H., Srikant R. A Mathematical Frame- work for Designing a Low-Loss, Low-Delay Internet // Network and Spatial Economics. – 2004. – 4 (1). – P. 75–102. 6. Altman E. et al. The evolution of transport protocols: An evolutionary game perspective // Computer Networks. – 2009. – Т. 53. – N 10. – С. 1751–1759. 7. Smith, John Maynard. Evolution and the Theory of Games. Cambridge university press, 1982. 8. Altman E., Bonneau N., Debbah M., Caire G. An evolutionary game perspective to ALOHA with power control, in // Proceed- ings of the 19th International Teletraffic Congress, Beijing, 29 August–2 September, 2005. Прикладні засоби програмування та програмне забезпечення 77 9. Han, Zhu, et al. Game theory in wireless and communication networks. Cambridge Univer- sity Press, 2012. 10. Meyn, Sean P. Control techniques for com- plex networks. Cambridge University Press, 2008. 11. Filippov, Aleksei Fedorovich, and Felix Medland Arscott, eds. Differential Equations with Discontinuous Righthand Sides: Con- trol Systems. Vol. 18. Springer, 1988. 12. Border, Kim C. Fixed point theorems with applications to economics and game theory // Cambridge university press. – 1989. Одержано 18.11.2013 Про авторів: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, Синецький Олександр Борисович, аспірант. Місце роботи авторів: Інститут програмних систем НАН України, 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: 526 6025. E-mail: o.ignatenko@gmail.com mailto:o.ignatenko@gmail.com

Моделювання конфліктної взаємодії в мережах: еволюційно-ігровий підхід

Institution

Similar Items