Большинство теоретических анализов специальных сетей предполагают, что каналы связи внутри сети стабильны. Но это часто не относится к реальным беспроводным устройствам — это знает любой, кто пользовался мобильным телефоном.
На симпозиуме Ассоциации вычислительной техники по принципам распределенных вычислений в июле прошлые и нынешние исследователи из группы теории распределенных систем в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института представили новую структуру для анализа специальных сетей, в которых качество связи ссылки колеблются. В рамках этой структуры они обеспечивают математические границы эффективности, с которой сообщения могут распространяться по сети, и описывают новые алгоритмы, которые могут достичь максимальной эффективности.
«Было несоответствие между теорией с ее идеализированными моделями и реальностью беспроводных сетей», — говорит Нэнси Линч, профессор кафедры программного обеспечения и инженерии NEC в Массачусетском технологическом институте и глава группы теории распределенных систем. "Когда люди начинают разрабатывать теоретические алгоритмы, они, как правило, слишком сильно полагаются на конкретные допущения моделей. Таким образом, алгоритмы, как правило, нереалистичны и ненадежны."
В прошлом некоторые исследователи пытались смоделировать ненадежность сетевых соединений как случайные колебания. «Но если вы предполагаете реальную случайность, то можете рассчитывать на случайность», — говорит Линч. "Каким-то образом вы можете использовать это в своем алгоритме. Возможно, случайность сама по себе дает вам слишком сильное предположение."
Состязательные отношения
Итак, Линч и ее соавторы в новой статье — Мохсен Гаффари, аспирант в области электротехники и информатики, и Кэл Ньюпорт, бывший аспирант в группе Линча, который теперь является доцентом информатики в Джорджтаунском университете — вместо этого смоделировали колебания качества ссылок как умышленные манипуляции «злоумышленником»."Противник не может контролировать все ссылки в сети: некоторые из них останутся активными на протяжении всего выполнения алгоритма связи.
Но он может изменять пропускную способность других по своему желанию. И разработчик сети заранее не знает, какие ссылки надежны, а какие нет.
«Ваш алгоритм должен работать для всех возможных злоумышленников, некоторые из которых являются доброкачественными, а некоторые из них могут делать худшие из возможных вещей для вашего алгоритма», — говорит Ньюпорт. «Другими словами, он должен работать для всех возможных стратегий управления сетью."
В статье, появившейся два года назад, Ньюпорт, Линч и его коллеги предположили, что это действительно очень могущественный противник — тот, который заранее знал каждое решение, которое каждый узел в сети примет при попытке распространения сообщения. В этом контексте они доказали, что эффективное общение невозможно.
В новой статье они значительно ослабили противника. Он может точно знать, как работает алгоритм связи, и он может намеренно попытаться помешать ему, но он должен заранее определить свой образец манипулирования ссылками, прежде чем алгоритм начнет работать. Однако даже этот ослабленный противник может нанести гораздо больший ущерб, чем типы помех, с которыми могут столкнуться реальные беспроводные сети, — например, открытие и закрытие дверей, включение людьми микроволновых печей или выпадение дождя.
Линч, Ньюпорт и Гаффари исследовали два типа распространения сообщений.
В первом случае один узел сети пытается передать сообщение всем другим узлам. В этом случае они обнаружили, что эффективная коммуникация возможна даже в присутствии противника.
Геометрическое предположение
Во втором случае несколько узлов передают сообщения, и каждый из их непосредственных соседей должен получить сообщение, по крайней мере, от одного передатчика.
Как выясняется, многие общие проблемы при анализе ad hoc сетей сводятся к этой.
Здесь исследователи обнаружили, что присутствие злоумышленника может помешать эффективному общению, но только если сеть имеет странную форму, в которой центральный узел подключен ко многим соседним узлам, которые не связаны друг с другом. Такой тип схемы сети маловероятен в реальном мире: если два беспроводных устройства находятся достаточно близко к третьему, чтобы общаться с ним, они, вероятно, тоже смогут общаться друг с другом.
Как только исследователи добавили еще одно предположение — что два устройства, подключенные к третьему, хотя бы иногда смогут устанавливать связи друг с другом, — снова становится возможным эффективное общение.
В обоих случаях коммуникационные алгоритмы исследователей смогли помешать противнику, используя случайность. Одна из проблем при разработке протоколов связи для специальных беспроводных сетей заключается в том, что если два соседних узла начинают передачу одновременно на одной и той же частоте, они могут создавать помехи друг другу, предотвращая получение любой передачи.
Таким образом, наиболее эффективные протоколы назначают каждому узлу вероятность передачи в течение любого одного раунда связи (где раунд определяется временем, которое требуется узлу для отправки сообщения своим непосредственным соседям).
Алгоритмы исследователей Массачусетского технологического института придерживаются этой базовой схемы, но вместо того, чтобы циклически проходить через предписанную последовательность неуклонно сокращающихся вероятностей, они скремблируют последовательность вверх. В случае локальной трансляции каждое отдельное сообщение должно иметь свою уникальную последовательность вероятностей. Таким образом, кластеры узлов также временно избирают местных лидеров, которые координируют вероятности для разных передатчиков.
Однако исследователи смогли показать, что это дополнительное вычисление не сильно замедляло коммуникацию.
«Все это направление попыток уловить ненадежность с точки зрения враждебных эффектов — очень хорошее направление, к которому пока особо не обращались», — говорит Магнус Халлдорссон, профессор Школы компьютерных наук в Университете Рейкьявика и один организаторов Симпозиума по принципам распределенных вычислений. «И похоже, что это будет ключевой вопрос в исследовании беспроводных сетей."
Халлдорссон предупреждает, что предположения исследователей могут не применяться в некоторых возможных реальных сценариях. Например, помеха в одной специальной сети может быть вызвана передачей в другой, что может скорректировать ее стратегию вещания, когда она тоже обнаруживает конфликт. «Это не обязательно так, что он полностью игнорирует вашу операцию», — говорит он. "Нам, вероятно, нужно изучить это немного дальше.«Но, — добавляет он, — невнимательный противник» — все еще вполне естественное предположение во многих сценариях."