Пронумеруем уровни дерева на рис. 4.10 — узел 1 на уровне 0, узлы 2 и 3 на уровне 1 и т. д. Обратите внимание на то, что каждый узел на уровне i включает 2-i часть от всех станций. Если q готовых станций распределены равномерно, то ожидаемое их число ниже узла на уровне i равно 2-iq. Интуитивно ясно, что оптимальным уровнем для начала поиска будет тот, на котором среднее число конкурирующих в интервале станций равно 1, то есть уровень, на котором 2-iq = 1. Отсюда i = log2q.
Были разработаны многочисленные усовершенствования базового алгоритма — в частности, некоторые детали обсуждаются у Бертсекаса (Bertsekas) и Галлагера (Gallager) в издании 1992 года. Например, рассмотрим случай, при котором передавать хотят только станции G и H. На узле 1 произойдет конфликт, поэтому будет проверен узел 2. Он окажется пустым. Узел 3 проверять нет смысла, так как там гарантированно будет столкновение. (Нам известно, что под узлом 1 находятся 2 или более станций, а так как под узлом 2 нет ни одной станции, то все они должны быть под узлом 3.) Поэтому проверку узла 3 можно пропустить и сразу проверить узел 6. Поскольку под узлом 6 ничего не оказалось, то проверку узла 7 также можно пропустить и проверить узел G.
4.2.5. Протоколы беспроводных локальных сетей
Систему, состоящую из портативных компьютеров, общающихся по радио, можно рассматривать как беспроводную локальную сеть — мы уже обсуждали это выше. Такая локальная сеть — пример сети на базе широковещательного канала. Ее свойства отличаются от свойств проводных локальных сетей, поэтому здесь требуются специальные протоколы управления доступом к среде (MAC). В данном разделе мы познакомимся с некоторыми из этих протоколов. Далее мы также подробнее поговорим о стандарте 802.11 (WiFi).
Распространенная конфигурация беспроводных локальных сетей подразумевает наличие офисного здания с заранее размещенными в нем точками доступа. Все точки доступа соединены друг с другом медным проводом или оптоволоконным кабелем; они рассылают данные на пользовательские станции. Если мощность передатчиков точек доступа и переносных компьютеров настроена так, что диапазон приема составляет около десятка метров, то соседние комнаты становятся единой сотой, а все здание превращается в большую сотовую систему, подобную традиционной сотовой телефонной системе, описанной в главе 2. В отличие от обычной сотовой системы, у каждой соты в данном случае всего один канал, работающий со всеми станциями, находящимися в нем, включая точку доступа. Обычно пропускная способность такого канала составляет от несколько мегабит в секунду до 600 Мбит/с.
Мы уже говорили выше, что обычно беспроводные системы не имеют возможности распознавать коллизии в тот момент, когда они происходят. Принимаемый сигнал на станции может быть очень слабым, возможно, в миллион раз слабее излучаемого. Искать его — то же самое, что искать иголку в стоге сена. Для обнаружения уже случившихся коллизий и других ошибок применяются подтверждения.
Есть и еще одно очень важное различие между проводными локальными сетями и беспроводными. В беспроводной сети у станций иногда нет возможности передавать или получать кадры с других станций из-за ограниченного диапазона радиопередачи. В проводных сетях, если одна станция отправляет кадры, все остальные его получают. Такая особенность приводит к различным сложностям.
Для простоты мы допустим, что каждый передатчик работает в некой фиксированной области, которую можно представить как регион покрытия, имеющий форму круга. Внутри него другая станция может слышать и принимать данные с этой станции. Важно понимать, что на практике регион покрытия будет неправильной формы, так как распространение радиосигналов зависит от среды. Стены и другие препятствия, ослабляющие и отражающие сигналы, приводят к тому, что сила сигнала в разных направлениях меняется. Однако модель с окружностью для наших целей вполне подходит.
Можно наивно попытаться применить в локальных беспроводных сетях протокол CSMA (Carrier-Sense Multiple Access — множественный доступ с опросом несущей) — просто прослушивать эфир и осуществлять передачу только тогда, когда он никем не занят. Однако проблема заключается в том, что в действительности имеет значение интерференция на приемнике, а не на передатчике, поэтому этот протокол для беспроводных сетей подходит не очень хорошо. Чтобы наглядно увидеть суть проблемы, рассмотрим рис. 4.11, где показаны четыре беспроводные станции. Для нашей
проблемы не имеет значения, какая из них является точкой доступа, а какая — переносной. Мощность передатчиков такова, что взаимодействовать могут только соседние станции, то есть A с B, C с B и D, но не с A.
Рис. 4.11. Беспроводная локальная сеть: а — A и C — скрытые станции во время пересылки данных на B; б — B и C — засвеченные станции во время пересылки данных на A и D
Сначала рассмотрим, что происходит, когда станции A и C передают данные станции B, как изображено на рис. 4.11, а. Если станция A отправляет данные, а станция C сразу же опрашивает канал, то она не будет слышать станцию A, поскольку та расположена слишком далеко, и может прийти к неверному выводу о том, что канал свободен и что можно посылать данные станции B. Если станция C начнет передавать, она будет конфликтовать со станцией B и исказит кадр, передаваемый станцией A. (Мы предполагаем, что никакая схема по типу CDMA не используется для предоставления нескольких каналов, поэтому из-за коллизий сигналы искажаются и оба кадра разрушаются.) Нам необходим MAC-протокол, который предотвратит такой тип коллизий, ведь это лишняя трата полосы пропускания. Проблема, заключающаяся в том, что одна станция не может слышать возможного конкурента, поскольку конкурент расположен слишком далеко от нее, иногда называется проблемой скрытой станции (hidden terminal problem).
Теперь рассмотрим другую ситуацию: станция B передает данные станции A в то же время, когда станция С хочет начать передачу станции D, как показано на рис. 4.11, б. Станция С при опросе канала слышит выполняемую передачу и может ошибочно предположить, что она не может передавать данные станции D (пунктирная стрелка на рисунке). В действительности такая передача создала бы помехи только в зоне от станции B до станции C, где в данный момент не ведется прием. Нам необходим MAC-протокол, который предотвратит такой тип задержек, ведь это лишняя трата полосы пропускания. Такая ситуация иногда называется проблемой засвеченной станции (exposed terminal problem).
Сложность заключается в том, что перед тем как начать передачу, станции необходимо знать, есть ли какая-нибудь активность в радиодиапазоне вблизи приемника. Протокол CSMA же всего лишь может сообщить об активности вокруг передатчика путем опрашивания несущей. В случае передачи по проводу все сигналы достигают всех станций, поэтому такого различия не наблюдается. Однако во всей системе одновременно только одна станция может вести передачу. В системе с использованием радиосвязи, радиус передачи и приема которой ограничен небольшими зонами, одновременно могут передавать данные несколько станций, если только они передают различным принимающим станциям, находящимся достаточно далеко друг от друга. Нам нужно, чтобы даже в растущей ячейке одновременная передача не прекращалась — точно так же гости на вечеринке не ждут, пока все замолчат, чтобы начать говорить. Одновременно в большом помещении может происходить несколько разговоров, если только не все пытаются пообщаться с одним и тем же собеседником.
Одним из первых значительных протоколов, разработанных для беспроводных локальных сетей и умеющих справляться с этими проблемами, является MACA (Multiple Access with Collision Avoidance — множественный доступ с предотвращением коллизий) (Karn, 1990). Идея, лежащая в основе этого протокола, заключается в том, что отправитель заставляет получателя передать короткий кадр, чтобы окружающие станции могли услышать эту передачу и воздержаться от действий на время, требуемое для приема большого информационного кадра. Эта техника заменяет технику прослушивания несущей.
