Теоретико-игровая постановка задачи контроля эгоистичного поведения узлов в многоагентных сетях передачи данных

Размещено на http://www.allbest.ru/

Теоретико-игровая постановка задачи контроля эгоистичного поведения узлов в многоагентных сетях передачи данных

Н.И. Базенков

Институт проблем управления РАН

им. В.А.Трапезникова, Москва, Россия

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

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

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

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

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

В [2] для уменьшения влияния эгоистичных узлов на сеть был предложен механизм pathrater, использующий систему рейтингов, чтобы исключить подобные узлы из путей передачи данных. Идея ранжирования узлов получила развитие в способах контроля, использующих понятие репутации [3,4]. За каждым узлом ведется наблюдение в течение определенного времени. Действия, оцениваемые как эгоистичные, понижают значение репутации узла, а действия, оцениваемые как кооперативные, повышают. Если репутация опускается ниже определенного порога, узел изолируется от сети и лишается возможности передавать данные.

Рассмотрим пример, иллюстрирующий идею, лежащую в основе контроля эгоистичных узлов. Есть узлы, объединенные в сеть, как показано на рисунке 1. Узлы B и С собираются передать в течение некоторого отрезка времени по путям rB='BCD' и rC='CBA' свои сообщения. В том случае, если данные успешно достигли получателя, узел получает выигрыш u. На передачу чужих данных узел несет затраты с.

Узлы А и D выступают только как приемники и не принимают активного участия в процессе передачи. Пусть узлам B и С доступны два возможных действия: передавать чужие данные (кооперативное поведение) или не передавать (эгоистичное поведение). Назовем узел В игроком P1, а узел С - игроком Р2. В матрице на рисунке 2 представлены возможные исходы игры. Кооперативное и эгоистичное поведение обозначено буквами C (Cooperate) и D (Defect) соответственно.

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

контроль эгоистичний поведение сеть

где ui - выигрыш узла i от успешной передачи его данных, ci - затраты узла i на передачу чужих данных. Величины представляют действия игрока i и его оппонента соответственно.

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

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

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

Литература

1. Abolhasan M., Wysocki T., Dutkiewicz E. A Review of Routing Protocols for Mobile Ad Hoc Networks //Ad Hoc Networks vol.2, no.1, Jan. 2004, pp. 1-22

2. Marti S, Giuli T.J., Lai K., Baker M. Mitigating Routing Misbehavior in Mobile Ad Hoc Networks //Proc. of the 6th annual international conference on Mobile computing and networking, 2000

3. Michiardi P., Molva R. CORE: A Collaborative Reputation Mechanism to enforce node cooperation in Mobile Ad hoc Networks //IFIP - Communication and Multimedia Security Conference, 2002

4. Buchegger S., Le Boudec J.-Y. Performance analysis of the CONFIDANT protocol//Proc. of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002

5. Urpi A., Bonuccelli M., Giodano S. Modelling cooperation in mobile ad hoc networks a formal description of selfishness//Proc. of WiOpt'03: Modeling and Optimization in Mobile, Ad hoc and Wireless Networks, 2003

6. Felegyhazi M., Buttyan L., Hubaux J.-P. Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks //IEEE Transactions on Mobile Computing, vol. 5, no. 4, Apr. 2006

7. Milan F., Jaramillo J.J., Srikant R. Achieving Cooperation in Multihop Wireless Networks of Selfish Nodes //GameNets '06 - Proc on. the 2006 workshop on Game theory for communications and networks, 2006

8. Altman E., Kherani A.A., Michiardi P., Molva R. Non-cooperative Forwarding in Ad-Hoc Networks //NETWORKING 2005, LNCS 3462, pp. 486-498, 2005

9. Axelrod R. The Evolution of Cooperation. - Basic Books, 1984

10. Mailath G.J., Samuelson L. Repeated Games and Reputation - Long-Run Relationships. - Oxford University Press, 2006

Размещено на Allbest.ru