Самоорганизующиеся беспроводные сети (часть 2)

Окончание. Начало статьи - читать.

Стратегии доставки
Трудности при решении проблем эффективной маршрутизации информации через постоянно изменяющуюся сеть возникают по нескольким причинам. В традиционной сотовой или иной беспроводной сети базовые станции отслеживают приблизительное местоположение отдельных устройств. Это позволяет им принять сообщение от отправителя и отослать его прямо адресату.
Коммуникационным устройствам динамической сети приходится самим определять лучший способ доставки информации. Отдельные приборы имеют ограниченные вычислительные ресурсы, память и возможности связи, поэтому ни одно подобное устройство не способно ни собрать, ни обработать всю информацию. В традиционных беспроводных сетях такие функции выполняет центральный компьютер.
Ситуацию можно проиллюстрировать следующим образом: представьте, что вы находитесь в мегаполисе, например в Лондоне, и вам нужно связаться с другом, который находится где-то на другом конце города. Допустим, в этом воображаемом мире элементы коммуникационной инфраструктуры смонтированы на крышах автомобилей-такси. Дальность прямой связи приемника на каждой такой машине не превышает мили (1,6 км), а движутся такси гораздо медленнее, чем передается информация, поэтому для доставки вашего сообщения они должны работать совместно. Пока такси протискиваются через город, приемники на близко расположенных машинах связываются между собой, а затем разъединяются на непредсказуемое время. Ваш вызов должен проскакать через город по этой постоянно изменяющейся сети, найти вашего друга и передать ему информацию.
Задача сложна даже для единичного сообщения, передаваемого через небольшую сеть.С увеличением числа устройств и передаваемых сообщений она намного усложняется. Чтобы технологию можно было внедрять, она должна быть эффективной, т.е. работать независимо от того, насколько большой или маленькой становится сеть.
Для решения этой задачи разрабатывается ряд методов. В их основе лежит множество направлений передачи запроса. Один приемник связывается со своими соседями, чтобы выяснить, какие из них находятся поблизости. Последние опрашивают своих соседей и т.д., пока сообщение не достигнет адресата. Ответ может следовать обратно по тому же пути, а может изыскать и другой маршрут. Таким образом, каждое промежуточное устройство создает свой перечень возможных путей передачи информации между отправителем и получателем. Эти перечни позволяют вашему сообщению дойти до вашего друга даже в том случае, когда ваше устройство не имеет сведений о его местоположении. Поскольку сеть находится в движении, устройства должны постоянно повторять этот процесс, чтобы перечни возможных путей не устаревали.
Полезно также передавать информацию одновременно по нескольким путям, что увеличивает вероятность того, что она дойдет до адресата. Вопрос в том, насколько избыточной должна быть подобная система. С одной стороны, сообщение может передаваться по каждому из возможных путей целиком. Но в таком случае сеть очень скоро окажется перегруженной. Альтернативный вариант — когда информация разбивается на поток блоков данных, каждый из которых отправляется по своему пути. Такой подход позволяет обойтись меньшим количеством сетевых ресурсов, но по дороге некоторые биты могут быть потеряны, и адресат получит лишь часть сообщения.
Метод сетевого кодирования имеет промежуточные характеристики. Он также основан на разбиении сообщения на блоки, но каждый блок передается вместе с некой информацией о нем, и вся эта метаинформация отправляется по нескольким путям таким образом, что на финальном этапе сообщение может быть реконструировано получателем даже в случае утери некоторых блоков.
Один из аспектов сетевого кодирования — выбор числа путей, по которым передается сообщение. При этом уменьшается влияние отказа каждого из путей, но увеличивается число устройств, участвующих в одном соединении. Эта стратегия распределяет нагрузку соединения по большему числу участников, уменьшая потребление мощности каждым из них, но требует большей координации.
С увеличением числа устройств, начинающих передачу — не важно, для обеспечения одного или нескольких разговоров, — растет и вероятность возникновения перекрестных помех. Так же, как трудно что-то понять, когда много людей говорят одновременно, и беспроводному устройству трудно выделить передаваемую информацию, когда поблизости идут другие передачи. В самоорганизующихся беспроводных сетях такие проблемы особенно сложны, поскольку нет центрального контроллера, который координировал бы работу.
Есть два пути борьбы с перекрестными помехами в беспроводных сетях. Первый состоит в том, чтобы предотвращать конфликты. Если передачи редки, вероятность взаимных помех между сообщениями мала. При использовании этой стратегии каждое устройство разбивает информацию на короткие части, которые передает небольшими пакетами. Поскольку вероятность того, что некоординируемые ближайшие соседи будут вести передачи в это же время, мала, то меньше и перекрестных помех, чем в случае, если бы пользователи передавали всю информацию медленным непрерывным потоком (на таком подходе основаны большинство стандартов беспроводных сетей, связывающих между собой персональные компьютеры).
Вторая стратегия позволяет двум передатчикам посылать информацию приемнику одновременно, но требует, чтобы один из них вел передачу менее «громко», чем другой. Если вы говорите громко, а другой человек шепчет, я обычно легко могу понять, что вы говорите. Если же у меня есть запись «разговора», я могу впоследствии вычесть ваше сообщение, чтобы реконструировать более слабое.
Второй подход хорошо себя зарекомендовал для сети с двумя передатчиками, посылающими сообщения, и третьим устройством, которое их принимает. С увеличением числа передатчиков сложности быстро возрастают. Система должна как-то регулировать, кто должен «говорить» громко, а кто тихо. Сам процесс координации требует организации связи, и чем больше усилий уделяется координации, тем меньшей становится ширина полосы для передачи сообщений. Именно поиск наилучшего возможного решения и представляет собой цель продолжающихся исследований.

Новые инструменты
Хотя динамические сети могут найти применение во многих областях, точно оценить, насколько полезными они могут быть, трудно. Даже на простые вопросы о пределах их возможностей ответить нелегко. Какова будет скорость передачи информации? Как она зависит от числа устройств в сети и, соответственно, от масштаба перекрестных помех? Что будет в случае, когда все устройства сети находятся в движении? И какими могут быть компромиссы между скоростью передачи информации, задержками ее доставки и надежностью системы?
Выявление предельных характеристик для самоорганизующихся сетей — первоочередная задача. Такие знания позволят разработчикам применить новые методы в создаваемых проектах, а исследователям — определить, как наилучшим образом модифицировать существующие сети. Кроме того, разработчики смогут решать, какой из показателей — скорость передачи, задержки или вероятность потерь — считать наиболее важным в каждом случае. Например, для телефонных разговоров и телеконференций очень важно минимизировать задержки. Большие промедления или несогласованное прибытие пакетов могут вызывать паузы или остановки в передаче аудиои видеоинформации, что очень затруднит разговор. Поняв структуру конкретной создаваемой сети, разработчики смогут запрограммировать каждое устройство на приоритизацию его потребностей — малые задержки в телефонных разговорах и малый процент потерь пакетов при пересылке важных документов.
В случае постоянно изменяющихся самоорганизующихся сетей такого понимания добиться трудно. Чтобы понять пределы их возможностей, недостаточно определить показатели работы сети в данный момент: нужно определить, как она будет работать в каждой возможной конфигурации.
Для решения этой проблемы мы применили новый подход: «проецирование» сетей ad hoc на нечто, известное нам гораздо лучше, т.е. на обычные проводные сети. Специалисты в области информационных технологий более чем за шесть десятилетий сумели накопить солидный багаж в этой области. В таких сетях перекрестные помехи отсутствуют, а узлы не движутся. Чтобы изучить некую беспроводную сеть, прежде всего необходимо создать ее модель на базе проводной сети, обладающей некоторыми общими с ней важными характеристиками поведения. Это позволит найти пределы рабочих характеристик сети ad hoc.
Такой подход позволит создавать более совершенные сети, поскольку мы можем понять последствия выбора того или иного решения, а также определить, где наши сегодняшние подходы работают хорошо, а где нужно изыскивать альтернативные пути.
Даже располагая соответствующим инструментарием, мы не ожидаем, что динамические беспроводные сети заменят существующую сотовую инфраструктуру. Однако в уникальных ситуациях этот инструментарий позволит нам понять, насколько эффективной может быть сеть, причем именно тогда, когда она нужнее всего.  
 
ОСНОВНЫЕ ПОЛОЖЕНИЯ
■ Динамические (или самоорганизующиеся, или ad hoc) беспроводные сети не требуют стационарной инфраструктуры. Информация в них передается непосредственно от устройства к устройству, при этом образуется паутина соединений.
■ Такие сети можно использовать в местах, где создание технической базы традиционных беспроводных сетей слишком затруднено или дорого, например в отдаленных районах или зонах боевых действий.
■ Поскольку любая такая сеть постоянно изменяется, для предотвращения потери данных и уменьшения перекрестных помех необходимо применять новаторские стратегии.   

ОБ АВТОРАХ
Андреа Голдсмит (Andrea Goldsmith), Мюриел Медар (Muriel Medard) и Мишель Эффрос (Michelle Effros) — давние друзья и сотрудники. Голдсмит — профессор электротехники в Стэнфордском университете и соучредитель компании Quantenna Сommunications, разрабатывающей технологии беспроводных сетей, Медар — преподаватель факультета электротехники и информатики Массачусетсского технологического института, Эффрос — профессор электротехники в Калифорнийском технологическом университете.  

Перевод: И.Е. Сацевич