автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Анализ эффективности гибридного доступа к каналу в многошаговых беспроводных сетях

На правах рукописи

Красилов Артем Николаевич

Анализ эффективности гибридного доступа к каналу в многошаговых беспроводных сетях

05.12.13 - Системы, сети и устройства телекоммуникаций

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

31 ОКТ 2013

Москва - 2013

005536164

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем передачи информации им. A.A. Харкевича Российской академии наук (ИППИ РАН).

Научный руководитель:

Официальные оппоненты:

доктор технических наук, старший научный сотрудник Ляхов Андрей Игоревич

Степанов Сергей Николаевич, доктор технических наук, профессор, директор информационно-ана.1итического департамента ОАО <?Интеллект-телеком»

Осипов Дмитрий Сергеевич, кандидат технических наук, старший научный сотрудник лаб. №3 ИППИ РАН

Ведущая организация:

Федеральное государственное бюджетное учреждение науки. Институт проблем информатики Российской академии наук

Защита, состоится «2 2013 г. в & на заседании диссер-

тационного совета Д 212.156.04 ПРИ Федеральном государственном автономном образовательном учреждении высшего профессионального образования <гМосковском физико-техническом институте (государственном университете)» по адресу: 141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204 Нового корпуса.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).

Автореферат разослан ^ » 2013

Стрыгин Л. В.

'г * «»Й^-.-Л-Ч

Общая характеристика работы

Актуальность работы

В последние годы во веем мире наблюдается повышенный интерес к исследованию и разработке многошаговых беспроводных самоорганизующихся сетей (МБСС) с распределенным управлением. Примерами таких сетей являются высокоскоростные локальные сети Wi-Fi Mesh (стандарт IEEE 802.11s), персональные сети WiMedia (стандарт ЕСМА-368), а также сенсорные сети ZigBee (стандарт IEEE 802.15.4). По сравнению с беспроводными сетями с традиционной архитектурой «клиент-базовая станция» такие сети лучше масштабируются, обладают большей зоной покрытия за счет возможности использования нескольких шагов ретрансляции пакетов, более высокой отказоустойчивостью, а также адаптивны к условиям работы.

Одной из ключевых задач при построении МБСС является задача обеспечения множественного доступа станций к беспроводному каналу. В большинстве современных МВСС базовый механизм доступа к каналу обычно основан на методе случайного множественного доступа с детектированием несущей и предотвращением коллизий - CSMA/CA. Однако, как показывают многие исследования, в многошаговых сетях механизм случайного доступа не гарантирует надежную доставку данных из-за проблемы скрытых станций. Для решения этой проблемы недавно опубликованные стандарты МБСС в дополнение к базовому механизму случайного доступа предлагают опциональный механизм детерминированного доступа, основанный на заблаговременном резервировании интервалов времени для передачи данных и позволяющий существенно увеличить надежность их доставки. Таким образом, в современных МБСС предполагается использование механизма гибридного доступа, объединяющего в себе как случайный, так и детерминированный механизмы доступа к каналу.

Исследованию эффективности механизмов множественного доступа к каналу в беспроводных сетях посвящено значительное количество работ, среди которых следует особо отметить работы российских и зарубежных ученых: О.М. Брехова, A.B. Винеля, К.Ш. Зигангирова, В В. Зяблова, А.П. Кулешова, Д.В. Лаконцева, А.И. Ляхова, Д.Н. Мацнева, В.И. Неймана, Д.С. Осипова, A.A. Сафонова, С.Н. Степанова, A.M. Тюрликова, Е.М. Хорова, И.И. Цито-вича, М.Ю. Якимова, G. Bianchi, F. Cali. С. Ciccoiietti, М. Conti, М. Daneshi, J. Deng, G. Hiertz, E. Hossain, D. Malone, E. Mingozzi, J. Pan, I. Tinnirello, C. Wu, Y. Yang и др. Среди них большинство работ посвящено анализу эффективности только механизма случайного доступа. Другие работы предполагают, что в сети используется только механизм детерминированного доступа. Таким образом, остается открытой задача анализа производительности МБСС, в которых станции могут использовать одновременно два механиз-

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

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

Для достижения поставленной цели в диссертации ставятся и решаются следующие задачи.

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

2. Разработка методов борьбы с интерференцией и повышения эффективности использования канальных ресурсов при передаче данных с помощью механизма детерминированного доступа.

3. Разработка методов обеспечения качества обслуживания при передаче потоковых данных с использованием механизма детерминированного доступа в условиях переменной интенсивности помех.

4. Разработка аналитической модели сети с гибридным доступом для исследования взаимодействия механизмов случайного и детерминированного доступа.

Методы исследования

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

В данной работе получены следующие новые результаты:

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

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

• предложено улучшение процедуры резервирования канала для случая

передачи данных без использования подтверждений, позволяющее значительно увеличить пропускную способность сети:

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

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

Практическая ценность и реализация результатов. Результаты работы внедрены и используются па практике, а также в учебном процессе на кафедре МФТИ (ГУ) «Проблемы передачи и обработки информации» при ИППИ РАН, что подтверждено соответствующими актами. В частности, разработанные модели и методы использованы в НИР, выполняемых ИППИ РАН в рамках соглашений с Министерством образования и науки РФ и Российским фондом фундаментальных исследований, в международном исследовательском проекте FLAVIA, проводимом в рамках 7-й рамочной программы Евросоюза, а также при проектировании протоколов канального уровня МБСС, разрабатываемых ЗАО «Телум».

Основные положения, выносимые на защиту

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

2. Разработанный метод адаптивного управления резервированиями обеспечивает выполнение требований к качеству обслуживания при передаче потоковых данных в условиях переменной интенсивности помех, используя для этого минимальный объем канальных ресурсов.

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

Апробация работы. Основные результаты диссертации были представлены на ведущих международных и российских конференциях: 3rd Int. Workshop on Multiple Access Communications (Испания, 2010 г.), 8th IEEE Int. Conf. on Mobile Ad-hoc and Sensor Systems (Испания, 2011 г.), lst Int. Workshop on Wireless Access Flexibility (Россия, 2013 г.), Future Network and Mobile Summit (Португалия, 2013 г.), «Информационные технологии и системы» в 2009-2012

гг.. а также на семинарах ИППИ РАН.

Публикации. Материалы диссертации опубликованы в 12 печатных работах. из них 7 статей ([1-7]) в рецензируемых изданиях, 4 из которых ([1-1]) входят в перечень ВАК, 5 статей ([8-12]) в сборниках трудов конференций. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим.

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения, библиографии и приложения. Общий объем диссертации 130 страниц, включая 43 рисунка и б таблиц. Библиография включает 69 наименований.

Содержание работы

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

В первой главе описывается архитектура многошаговых беспроводных самоорганизующихся сетей (МБСС) с распределенным управлением на примере технологии Wi-Fi Mesh (стандарт IEEE 802.11s), которая на сегодняшний день является наиболее перспективной технологией построения МБСС. Особое внимание уделено описанию механизма гибридного доступа к каналу, используемому в таких сетях. Термин «гибридный доступ» означает, что для доступа к каналу станции сети могут использовать два механизма: механизм случайного доступа (МСД) и механизм детерминированного доступа (МДЦ).

В основе работы МСД лежит метод множественного доступа с детектированием несущей и предотвращением коллизий (CSMA/CA). Прежде чем начать передачу, каждая станция сети, убедившись, что канал был свободен в течение интервала времени AIFS, выжидает случайно выбранный интервал отсрочки. Интервал отсрочки состоит из слотов постоянной длительности а, а количество этих слотов равновероятно выбирается из множества [0, CW], где величина CW называется конкурентным окном. Значение счетчика отсрочки уменьшается на единицу, если в течение всего предшествующего слота канал воспринимался как свободный. Отсчет слотов отсрочки приостанавливается, когда канал становится занят. При этом в следующий раз значение счетчика отсрочки уменьшится на единицу, когда канал окажется свободным в течение интервала AIFS, если прием последнего кадра, зафиксированного данной станцией, был успешен, или EIFS, если прием неудачен. Когда счетчик отсрочки достигает нулевого значения, станция предпринимает очередную попытку передачи. Если станция-приемник успешно получила кадр данных, то она отвечает передачей кадра подтверждения. Отсутствие под-

□

- передача с использованием случайного досту па

□

интервал резервирования

"Период резервирования-

1Щ_

-0Т1М-интервал-

ПИЦ

о.

Счетчик отсрочки: 5

Запрет передачи

Рис. 1. Механизм гибридного доступа к каналу

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

МДД позволяет станциям заблаговременно резервировать интервалы времени работы канала для получения в них бесконкурентного доступа. Каждое резервирование представляет собой строго периодическую последовательность интервалов времени одинаковой длительности. Для определения положения всех интервалов, относящихся к одному резервированию, станция делит время на равные промежутки, называемые БТМ-интервалами. Каждое резервирование задается 3 параметрами: 1) длительностью каждого интервала; 2) периодичностью - числом зарезервированных интервалов в одном БТШ-интервале; 3) смещением первого зарезервированного интервала относительно начала ОТШ-интервала. При установлении нового резервирования станция-передатчик (владелец резервирования) и станция-приемник (адресат резервирования) должны убедиться, что оно не пересекается во времени с уже установленными резервированиями их соседей, и оповестить своих соседей, которые, в свою очередь, должны воздерживаться от передачи в зарезервированных интервалах и также оповестить своих соседей о новом резервировании. Таким образом, информация о каждом резервировании распространяется в двухшаговой окрестности от владельца и адресата резервирования.

Для обеспечения совместной работы двух механизмов доступа вводятся следующие правила. Доля временных ресурсов канала МАГ, которая может быть зарезервирована станциями с помощью МДД, ограничена величиной МАРЫтИ. В интервалах времени, не занятых резервированиями, станции могут осуществлять доступ с использованием МСД (см.рис. 1). При этом станции запрещается начинать передачу с использованием МСД, если планируемая передача пересекает во времени интервал резервирования, владельцем или адресатом которого является соседняя станция или сама эта станция.

В последнем разделе главы проводится анализ существующих работ по исследованию МСД и МДД и ставятся задачи диссертации. В частности, показано, что в существующих работах предполагается, что в сети исполь-

зуется либо только МСД, либо только МДД, н не рассматривается случай, когда в сети могут использоваться одновременно два механизма. Кроме того, в литературе отсутствуют решения, позволяющие обеспечить в многошаговых сетях передачу мультимедийных потоков с заданными требованиями к качеству обслуживания в условиях переменной интенсивности помех.

Во второй главе анализируется эффективность работы МСД в многошаговых сетях. Особенностью работы беспроводных сетей является то, что все станции разделяют одну общую среду, и поэтому передачи сигналов одними станциями оказывают влияние на передачи сигналов других станций. Данное явление называется интерференцией.

Рассмотрим два прямых соединения станций сети Wi-Fi Mesh: А—>В и С—>D, в которых передающие станции А и С работают в режиме насыщения и используют для передачи данных механизм случайного доступа. Если все станции находятся в зоне радиоприема друг друга, то они одинаково воспринимают занятость канала, поэтому одновременная передача станций А и С возможна только, когда эти станции одновременно закончат отсчет интервалов отсрочки, причем вероятность такого события мала. В многошаговых сетях передатчики разных соединений могут быть скрыты друга от друга, например, когда станции располагаются в цепочку A-B-C-D и каждая из них слышит только соседей. Так как станции А и С не слышат передачу друг друга, а длительность слота а значительно меньше длительности передачи, то с вероятностью, близкой к единице, станция С может отсчитать слоты отсрочки за время передачи станции А и начать свою передачу. Интерференция, вызванная передачей станции С, будет приводить к тому, что станщи В не сможет декодировать данные, передаваемые станцией А, в то время как передача станции С всегда будет успешна. Таким образом, в рассматриваемом случае интерференция приводит к существенно неравномерному распределению пропускной способности канала между соединениями. Представляет интерес исследовать, насколько часто возникают такие случаи интерференции в сети при произвольном расположении станций и к каким иным эффектам может приводить интерференция при других расположениях станций.

Для решения данной задачи в диссертации используется физическая модель интерференции, детально учитывающая особенности работы протоколов канального и физического уровней сетей Wi-Fi. Для каждой пары станций передатчика (ТХ) и приемника (RX) данная модель позволяет определить три зоны: 1) зону уверенного приема, в которой все станции в отсутствии интерференции успешно принимают кадры данных от станции ТХ; 2) зону блокировки, в который все станции регистрируют физическую занятость среды при передаче станции ТХ; 3) зону интерференции приемника, в которой передача любой станции приведет к тому, что станция RX не сможет декодировать кадр, передаваемый станцией ТХ. Используя данную модель, опре-

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

Основные результаты второй главы опубликованы в [1, 8].

В третьей главе анализируется эффективность работы МДД.

В разделе 3.1 исследуется проблема интерференции при использовании МДД. Согласно стандарту IEEE 802.11s для защиты передач внутри интервалов резервирований от интерференции, вызванной передачами других станций, одношаговые соседи владельца и адресата резервирования не могут начинать передачу с использованием как МСД, так и МДД, если она пересекается во времени с зарезервированными интервалами. Такой метод защиты резервирований действительно позволяет снизить интерференцию и, в частности, решить проблему скрытых станций, возникающую при использовании МСД, однако не решает проблему интерференции полностью. Детальный анализ, проведенный в разделе 3.1, показывает, что передачи внутри интервалов резервирования подвержены интерференции в следующих двух случаях. Во-первых, когда сосед адресата резервирования отвечает кадром подтверждения на кадр данных, переданный двухшаговым соседом с помощью МСД. Во-вторых, интерференция может быть вызвана передачами двухшаговых соседей владельца и адресата резервирования, которые для доступа к каналу могут использовать как МСД, так и МДД. С помощью' имитационного моделирования в среде iis-З показывается, что описанные выше случаи интерференции могут приводить к существенному снижению вероятности доставки данных в интервалах резервирований. В частности, в типичных сценариях развертывания многошаговых сетей, например, в сценарии с решетчатой топологией, при передаче пакетов только в интервалах резервирований доля потерянных пакетов может достигать 40%, что сводит на нет все преимущества от заблаговременного резервирования ресурсов капала.

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

С помощью имитационного моделирования показывается, что использование описанных выше методов защиты позволяет существенно увеличить вероятность доставки данных в интервалах резервирования. В частности, в случае решетчатой топологии использование двухшаговой защиты позволяет полностью решить проблему интерференции, т.е. обеспечить вероятность успешной доставки в интервалах резервирования, близкую к единице, при отсутствии других источников помех. Однако, если для всех резервирований использовать только двухшаговую защиту, это приводит к существенному снижению (более чем на 40%) числа резервирований, которые могут быть установлены в сети, по сравнению со случаем использования только одноша-говой защиты. Для достижения компромисса между надежностью передачи данных и емкостью сети каждая станция должна адаптивно выбирать одно-шаговый или двухшаговый метод защиты в зависимости от текущих условий в канале. Алгоритм такого выбора разработан в главе 4.

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

В диссертации описывается, как модифицировать поля передаваемых служебных сообщении, чтобы обеспечить соседние станции такой информацией, а также описываются правила их обработки. С помощью метода Монте-Карло проведен численный анализ предлагаемого улучшения, который показал, что для сети с произвольной топологией в случае, когда не используются подтверждения, предлагаемое улучшение позволяет более чем на 30% увеличить максимальное число установленных в сети резервирований, т.е. более чем на 30% увеличить емкость сети.

Результаты, полученные в третьей главе, опубликованы в [5, 6, 9].

В четвертой главе рассматривается задача обеспечения качества обслуживания при передаче потоковых данных в МБСС. Проведенный в главах 2 и 3 анализ МСД и МДД показал, что ввиду явления интерференции приемлемое качество обслуживания при передаче потоковых данных может быть достигнуто только с использованием МДД. Стандарт IEEE 802.11s лишь описывает правила установления резервирований, но не регламентирует, когда устанавливать резервирования и как выбирать параметры резервирований.

В разделе 4.1 анализируются различные способы организации передачи потоковых данных в многошаговой ссти с помощью МДД. Рассматривается передача потока постоянной интенсивности, для которого заданы размер пакета L, интервал поступления пакетов Т, а также требования к качеству обслуживания (требования QoS). Требования QoS представляют собой два ограничения: D®oS - максимально допустимая задержка при передаче пакетов от станции-источника до станции-получателя, PLE9oS - максимально допустимая доля пакетов, которая может быть не доставлена станции-получателю или доставлена не вовремя. Предполагается, что для потока найден маршрут, состоящий из N шагов. Как уже было показано в главе 3, передачи пакетов в интервалах резервирования могут быть неудачны из-за интерференции или случайного шума. Поэтому при резервировании ресурсов на каждом шаге маршрута следует учитывать повторные попытки передачи пакетов, необходимые для выполнения требований QoS. При этом объем ресурсов, который необходимо зарезервировать для выполнения требований QoS, зависит от используемой в интервалах резервирования политики квитирования.

В диссертации рассматриваются и сравниваются два метода передачи потоковых данных, которые отличаются между собой тем, какая политика квитирования используется в интервалах резервирования, а именно - метод с подтверждениями и метод без подтверждений. При использовании метода с подтверждениями на каждом шаге г маршрута устанавливается одно резервирование с периодом Тг (Т, < Т) и длительностью каждого интервала, достаточной для осуществления одной попытки передачи, включая время передачи подтверждения. На шаге i пакет обслуживается до тех пор, пока он либо не будет передан успешно, т.е. будет получено подтверждение, ли-

бо не истечет время , отведенное на его передачу. При использовании метода без подтверждений на каждом шаге устанавливается К, одинаковых резервировавший с периодом Т и длительностью каждого интервала, достаточной для осуществления одной попытки передачи, т.е. для каждого пакета осуществляется ровно Кг попыток передачи. Для каждого из методов показывается, как при заданных вероятностях д; неудачной попытки передачи разделить требования Оой между шагами передачи (т.е. назначить на каждом шаге ограничения РЬВ?* и Д1?"5, чтобы ГШ"РЬГ^аЯ) = 1 -РЫР"* и £>?0,? = Б®"3) и выбрать параметры резервирований, чтобы на каждом шаге выполнялись найденные ограничения и при этом суммарный объем зарезервированных канальных ресурсов был минимален. Сравнение двух методов показывает, что в случае передачи пакетов малого размера (что имеет место при передаче голосовых потоков) и использования высоких скоростей передачи метод без подтверждений является более предпочтительным, так как он обеспечивает выполнение требований С^оБ, используя для этого меньший объем канальных ресурсов, чем метод с подтверждениями.

Рассмотрим один шаг передачи потока постоянной интенсивности, на котором заданы требования С5оЭ (РЬВ9°5 и О0"5, индекс г опущен для краткости записи), а для передачи используется метод без подтверждений. При использовании метода без подтверждений выполнение ограничения на задержку £)<?°5 обеспечивается таким размещением интервалов резервирований, что последняя попытка передачи пакета расположена не далее, чем от времени поступления пакета в очередь. Таким образом, для выполнения требований С^оБ на данном шаге передачи необходимо установить такое число резервирований (число попыток передачи пакета), при котором будет выполнено ограничение на долю потерянных пакетов. Как уже отмечалось выше, попытки передачи пакетов в зарезервированных интервалах могут быть неудачными из-за помех, вызванных случайным шумом и интерференцией со стороны других станций. Так как интенсивность передач других станций сети может изменяться со временем, то интенсивность помех в интервалах резервирований также может изменяться. В связи с этим для выполнения требований С^оБ необходимо настраивать число резервирований, используемых для передачи потока, с учетом возможных изменений интенсивности помех, а также корреляции ошибок, вызванной наложением во времени передач других станций на соседние интервалы резервирований.

Для решения данной задачи в разделе 4.2 предлагается метод управления резервированиями, к которому предъявляются следующие требования. 1) Должно выполняться ограничение на долю потерянных пакетов с некоторой надежностью а. Метод выполняет ограничение на долю потерянных пакетов с надежностью а, если для любого интервала времени фиксированной длительности, за который передается IV пакетов, доля потерянных пакетов Ь/\¥

меньше заданного ограничения РЬЯ.^"3 с вероятностью большей, либо равной а:, т.е. Р { [./]¥ < РЬП9о!1} > а. 2) При условии выполнения ограничения на долю потерянных пакетов число используемых резервирований должно быть минимально. 3) Метод должен быть стабилен, т.е. частота установления резервирований FЛ должна быть много меньше порога РАо = где tsetu¡) - характерное время оповещения передатчиком и приемником своих соседей об установлении нового резервирования.

Суть предлагаемого метода заключается в периодическом запуске процедуры, состоящей из трех шагов. На первом шаге предполагается, что свойства канала существенно не меняются за интервал времени между двумя последовательными запусками процедуры. На основании этого предположения и с учетом информации X об успешных и неудачных попытках передачи последних Л пакетов в каждом резервировании из текущего множества резервирований Ясиг (X - бинарная матрица размером |ЯС"Г| х к, где |Я| -размер множества Я) строится функция Рх{й), являющаяся оценкой вероятности успешной доставки пакета при использовании множества Л резервирований. Данная функция определяется для любого множества Я, которое можно получить из текущего множества Итт только добавлением новых или только удалением некоторых из существующих резервирований. Для любого множества И С Яспг вероятность Рх(Щ можно оценить как Рх{Щ =

Для предсказания качества новых резервирований (т.е. для случая В. Э Яс"г) используются следующие предположения. 1) Вероятность возникновения ошибки при передаче пакета в интервале резервирования г зависит только от того, возникла ли ошибка при передаче этого пакета в соседнем интервале резервирования (г — 1), причем вероятность возникновения ошибки в интервале резервирования г при условии, что возникла ошибка в интервале резервирования (г — 1), определяется формулой = <?г + (1 — «з^е-^'-1, где qi - безусловная вероятность ошибки при передаче в интервале резервирования г, а Рг,г-1 - расстояние между резервированиями г и г — 1 (т.е. промежуток времени между началами двух соответствующих интервалов резервирований). 2) Вероятность ql ошибки при передаче в новых резервированиях (т.е. для г ^ Яп") равна средней вероятности для уже установленных резервирований. Используя информацию X, оцениваются вероятности ф и 7Г{Л. 1 для всех резервирований из множества Ясиг, и с помощью метода наименьших квадратов находится оценка параметра Л. Далее, используя введенные выше предположения, оцениваются вероятности 7Ги-1 для тех пар резервирований (г, г — 1), для которых резервирования г или г — 1 не принадлежат множеству /¿С"Г, и находится искомая оценка вероятности Рх{Я) = 1 — 91 П!=2 7г»,»-1-

На втором шаге процедуры с помощью построенной функции Рх(Я) определяется минимальное множество Я* резервирований, для которого бу-

дет выполнено ограничение на долю доставленных пакетов с надежностью а: Fwwm (|W7 • PLR9°s\) > а, где Fmm(k) = £ (тр%(1 -Р* (Л))'

i—O

- функция распределения неудач в W испытаниях Бернулли с вероятностью успеха Р.\(Щ, L'J ~ округление спизу.

Чтобы повысить стабильность метода, на третьем шаге новое множество Rncw резервирований формируется с учетом истории решений, полученных за I последних запусков процедуры, т.е. с учетом множеств R's, R"s_j, ..., R¡_l+V где s - порядковый номер текущего запуска процедуры.

Если в результате выполнения процедуры не были установлены новые резервирования, то в следующий раз процедура запускается после того, как будет передано т пакетов. Если были установлены новые резервирования, то процедура запускается через т' = + h пакетов, так как необходи-

мо время tsetup для их установления и время для получения информации об успехах/неудачах в новых резервированиях.

Для анализа области применимости и настройки параметров метода в диссертации рассматривается синтетический сценарий, в котором интенсивность помех скачкообразно меняется в конце каждого интервала времени Tchange, т.е. 1 /TciMnge - характерная частота изменений условий в канале. В результате экспериментов были найдены диапазоны значений параметров г, h и I, которые при любых значениях Tchange > T'¿hanrjc позволяют удовлетворить заданным ограничениям PLR9oS, а и FA0 при используемом числе резервирований, близком к минимальному. 1 /T¡?Uange это характерная частота изменений условий в канале, выше которой метод не позволяет удовлетворить заданным ограничениям при любых значениях т, h и /. Показано, что Change ~ величина порядка h/( 1 - о), где h - среднее значение из полученного диапазона значений параметра h. Сделанные выводы подтверждены с помощью имитационного моделирования применения метода управления резервированиями в реальном сценарии сети с решетчатой топологией, в котором передачи в интервалах резервирований подвержены интерференции со стороны других станций сети.

В разделе 4.3 метод управления резервированиями расширяется на случай, когда станции могут устанавливать резервирования двух типов: с одно-шаговым или двухшаговым методом защиты. Для этого любое множество резервирований представляется как объединение R = Rah U Rth двух подмножеств, каждое из которых содержит резервирования одного типа. Предполагается, что ошибки при передаче в интервалах резервирований разных типов возникают независимо, поэтому Рх(R) = 1 — (1 — Px{Roh))0- — Px(Rth))- Кроме того, резервированиям разных типов приписывается разная стоимость, чтобы учесть разницу в числе станций, блокируемых при установлении резервирований. Стоимость множества резервирований C(R) = |üo/i| + Cth\Rth\,

Метод защиты:

Рис. 2. Средняя стоимость С множества резервирований в зависимости от доли времени когда передают двухшаговые соседи; с^, = 4

где С(Л - отношение числа станций, находящихся в двухшаговой окрестности от владельца и адресата резервирований, к числу станций в одношаговой окрестности. Таким образом, на втором шаге процедуры находится множество резервирований, которое минимизирует функцию стоимости С {К). На рис. 2 представлены результаты эксперимента, в котором передачи в интервалах резервирований подвержены интерференции, вызванной передачами двухшаговых соседей. Данные результаты показывают, что адаптивный выбор метода защиты для устанавливаемых резервирований позволяет существенно уменьшить объем блокируемых канальных ресурсов по сравнению со случаями использования только одношагового или только двухшагового метода защиты при выполнении требований С^оБ.

Основные результаты четвертой главы опубликованы в [2, 4, 11].

В пятой главе анализируется взаимодействие МСД и МДД.

В разделе 5.1 рассматриваются различные способы организации взаимодействия двух механизмов. Согласно стандарту станции, использующие для передачи данных МСД, не могут начинать передачу, если планируемая передача пересекает во времени интервал резервирования соседней станции. Однако стандарт не регламентирует, что должна делать станция (например, станция А), которая отсчитала слоты отсрочки, но не может начать передачу по причине, описанной выше. Для восполнения данного пробела в диссертации предлагаются и сравниваются два способа отсчета слотов отсрочки. Согласно способу 1 станция А выбирает новое значение счетчика отсрочки при том же значении конкурентного окна и «замораживает» отсчет до окончания интервала резервирования. Согласно способу 2, если станция А не может начать передачу, то она выбирает новое значение счетчика отсрочки и продолжает отсчет.

В разделе 5.2 разрабатывается аналитическая модель взаимодействия МСД и МДД, которая позволяет оценить пропускную способность станции, использующей МСД, при условии, что часть ресурсов канала зарезервирована с помощью МДД, а также сравнить эффективность двух предложенных

способов. Рассматриваются два соединения: А—»В п С—»D. Станция А для передачи данных устанавливает резервирование с периодом Т и длительностью D_\i каждого интервала. Станция С, работая в режиме насыщения, передаст пакеты фиксированного размера L с помощью только МСД, причем время, необходимое для передачи одного пакета и подтверждения, равно Ttr. Ввиду отсутствия других станций, использующих МСД, значение конкурентного окна станции С постоянно и равно СИ"т;п. Обозначим W = CWmm + 1.

Для нахождения пропускной способности S станции С рассматривается один период резервирования Т; тогда S = LK/T, где К - среднее число передач станции С за один период. Передача станции С рассматривается как марковский процесс, состояние которого описывается числом слотов г, которые станция С должна отсчитать после окончания интервала резервирования. Чтобы найти значение К определяются вероятности Pjk\i того, что система перешла из состояния i в состояние j и при этом было передано ровно к пакетов. Для нахождения данных вероятностей для каждого из способов отсчета слотов отсрочки рассматривается различные случаи h = {1,2,3}, которые отличаются между собой тем, в какой момент времени закончилась последняя передача станции С в рассматриваемом периоде, и определяются вероятности

Л-пя каждого случая h. Случай 1 возникает, когда после последней передачи станции С прошел цикл отсрочки (цикл отсрочки - интервал времени между началом и окончанием отсчета слотов отсрочки, содержащий случайное число слотов от 0 до W — 1), но станция С не может начать передачу, так как передача пересечет интервал резервирования (см.рис.1 - «запрет передачи»); случай 2 - когда от окончания последней передачи до интервала резервирования остался интервал времени, меньший AIFS; случай 3 когда отсчет слотов отсрочки был прерван интервалом резервирования. В частности, для способа 1 вероятность р'.^ вычисляется по формуле

1 (l г=о

где s(k, I) = фи Soior'('~1)"+WV"(S) G-v») ~ веРоятность того, что за к циклов отсрочки был отсчитано ровно I слотов, 1\ максимальное число слотов отсрочки, которое может быть отсчитано за к циклов отсрочки, а условие R\(l, i, к) проверяет, что при заданных I, i и к имеет место случай 1. В формуле для нахождения s(k, I) используется доопределение отрицательных биномиальных коэффициентов (*) = *(*-1Ы<=-"+1) (при v > 0) согласно Феллеру.

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

вероятность для способа 2 приобретает другой вид

р% = ^ Е<к> ^ *)} £ Е ь, к, г)),

1=0 6=0 п2=0

где Ь - число слотов, которые отсчитаны в последнем цикле отсрочки, прерванном интервалом резервирования. Для нахождения суммы внутреннего ряда данной формулы в диссертации с применением аппарата производящих функций доказывается следующее утверждение.

Утверждение 1. Пусть а(п,]) - вероятность того, что сумма п случай-пых независимых целочисленных величин, равномерно распределённых на ин-

оо

тервале [0, IV - 1], равна Тогда ряд «у = ^(п,.?') сходится и равен:

п=О

" Ш

г(т,з - \Ут + т) — 2 г(т<3 ~ 1 ~ ^т + т)> 3 >

т=0 т—0

и,- =

И"

IV-!'

7 = 0,

где г(т,9) =

В диссертации получены формулы для р^. в остальных случаях к — {2, 3}, аналогичные (1) и справедливые для обоих способов. Далее находятся веро-

. . ^ V-, (И)

ятности перехода из состояния г в состояние р^ = 2_,к и стационарные вероятности а^ состояний г, позволяющие получить среднее число пакетов, переданных за один период резервирования К = ^ аг X

В разделе 5.3 приводится сравнение численных результатов, полученных с помощью имитационной и аналитической моделей, которое показывает высокую точность последней. С помощью аналитической модели сравнивается эффективность двух предложенных способов отсчета слотов отсрочки и показывается, что оба способа обладают одинаковой эффективностью (дают одинаковые пропускные способности) в широком диапазоне сценариев. Кроме того, с помощью имитационного моделирования данный вывод подтвержден для случая, когда в сети одновременно работают несколько станций, использующих МСД. Также аналитическая модель используется для сравнения различных способов размещения интервалов резервирования при фиксированной доле ресурсов МАЕ = £>м/Т, выделенных под МДД. Результаты показывают, что группировка интервалов резервирований (увеличение Бм) позволяет существенно увеличить пропускную способность станций, использующих МСД. Данный результат также позволяет сделать вывод, что использование величины MAFLim.it, введенной в стандарте для ограничения

доли ресурсов, выделенных под МДД, не гарантирует какой-либо минимальной пропускной способности для станций, использующих МСД, и требуется разработка другого механизма, обеспечивающие такие гарантии.

Результаты пятой главы опубликованы в [3, 10, 12].

В Заключении приводятся основные результаты диссертационной работы.

Основные результаты

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

1. Проведена классификация возможных случаев интерференции для двух прямых соединений станций сети Wi-Fi Mesh, использующих механизм случайного доступа. Среди них выявлены случаи интерференции, которые приводят к существенно неравномерному распределению пропускной способности канала между соединениями, и получена оценка вероятности возникновения таких случаев.

2. Разработаны новые методы защиты резервирований канала, устанавливаемых с помощью механизма детерминированного доступа, от интерференции, вызванной передачами других станций сети, позволяющие существенно увеличить вероятность успешной доставки данных в интервалах резервирований. Разработанные методы были представлены на заседаниях комитета IEEE 802 LMSC по стандартам локальных и городских сетей.

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

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

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

Список публикаций

1. A. Krasilov. Physical Model Based Interference Classification and Analysis // Lecture Notes in Computer Science, Vol. 6235. 2010. Pp. 1-2.

2. A.H. Красилов, А.И. Ляхов, Д.М. Островский, Е.М. Хоров. Метод динамического резервирования канальных ресурсов при передаче мультимедийных потоков в сетях Wi-Fi Mesh // Автоматика и телемеханика. 2013. № 9. С. 34-52.

3. А.Н. Красилов, А.И. Ляхов, Ю.И. Мороз. Аналитическая модель взаимодействия механизмов случайного и детерминированного доступа к каналу в сетях Wi-Fi Mesh // Автоматика и телемеханика. 2013. № 10. С. 119-136.

4. Е. Khorov, A. Krasilov, A. Lyakhov, D. Ostrovsky. Dynamic Resource Allocation for MCCA-Based Streaming in Wi-Fi Mesh Networks // Lecture Notes in Computer Science, Vol. 8072. 2013. Pp. 93-111.

5. A. Krasilov, A. Lyakhov, A. Safonov. Interference, even with MCCA channel access method in IEEE 802.11s mesh networks // Proc. 8th IEEE Int. Gonf. on Mobile Adhoc and Sensor Systems. 2011. Pp. 752-757.

6. P. Gallo, A. Krasilov, A. Lyakhov, et.al. Breaking layer 2: A new architecture for programmable wireless interfaces // Proc. Int. Conf. ICT Convergence (ICTC). 2012. Pp. 342 347.

7. E. Khorov, A. Krasilov, A. Safonov, et.al. Making IEEE 802.11 Wireless Access Programmable /'/' Proc. Future Network and Mobile Summit. 2013.

8. A.H. Красилов. Физическая модель интерференции прямых соединений: классификация и анализ возможных случаев // Тр. конф. «Информационные технологии и системы». 2009. С. 15-22.

9. А.Н. Красилов, А.И. Ляхов. Использование МССА для предоставления QoS в сетях IEEE 802.11s // Тр. конф. «Информационные технологии и системы». 2011. С. 282-293.

10. А.Н. Красилов, А.И. Ляхов, Ю.И. Мороз. Анализ взаимодействия механизмов EDCA и МССА в сетях IEEE 802.11s // Тр. конф. «Информационные технологии и системы». 2011. С. 294-301.

11. А.Н. Красилов, Е.А. Щвец. Анализ методов передачи потоковых данных с использованием МССА // Тр. конф. «Информационные технологии и системы». 2012.

12. А.Н. Красилов, А.И. Ляхов, Ю.И. Мороз. Аналитическая модель взаимодействия механизмов EDCA и МССА в сетях 802.11s // Тр. конф. «Информационные технологии и системы». 2012.

Подписано в печать:

22.10.2013

Заказ № 8946 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. A.A. Харкевича Российской академии наук (ИППИ РАН)

На правах рукописи

04201364689 Красилов Артем Николаевич

Анализ эффективности гибридного доступа к каналу в многошаговых беспроводных сетях

05.12.13 - Системы, сети и устройства телекоммуникаций

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель

д. т. н., с. н. с.

Ляхов Андрей Игоревич

Москва - 2013

Содержание

Введение ......................................................................................4

Глава 1. Механизмы доступа к каналу в многошаговых беспроводных самоорганизующихся сетях ............................................................8

1.1. Технологии многошаговых беспроводных самоорганизующихся сетей .... 8

1.2. Механизм гибридного доступа к каналу в сетях Wi-Fi Mesh ..................10

1.3. Анализ существующих работ по исследованию мехапизхмов доступа к каналу

is многошаговых беспроводных сетях. Постановка задач диссертации .... 22

Глава 2. Анализ эффективности механизма случайного доступа............29

2.1. Модели интерференции ............................................................29

2.2. Классификация случаев интерференции..........................................32

2.3. Анализ случаев интерференции....................................................36

2.4. Вероятности возникновения случаев долгосрочной и краткосрочной неравномерности ............................................................................51

2.5. Выводы ко второй главе ............................................................54

Глава 3. Анализ эффективности механизма детерминированного доступа 55

3.1. Анализ методов защиты резервирований от интерференции ..................55

3.2. Улучшение процедуры резервирования канала при использовании политики квитирования без подтверждений..................................................65

3.3. Выводы к третьей главе ............................................................68

Глава 4. Использование механизма детерминированного доступа для обеспечения качества обслуживания....................................................70

4.1. Организация передачи потоковых данных с помощью МДД в многошаговой сети....................................................................................70

4.2. Метод динамического управления резервированиями ..........................79

4.3. Управление резервированиями с адаптивным выбором метода защиты ... 97

4.4. Выводы к четвертой главе.............................100

Глава 5. Анализ взаимодействия механизмов случайного и детерминиро-

ванного доступа ....................................102

5.1. Взаимодействие механизмов случайного и детерминированного доступа . . 102

5.2. Аналитическая модель ...............................103

5.3. Численные результаты ...............................113

5.4. Выводы к пятой главе ...............................119

Заключение .........................................120

Литература .........................................121

Приложение А. Акты о внедрении результатов диссертации ........128

Введение

Актуальность работы

В последние годы во всем мире наблюдается повышенный интерес к исследованию и разработке многошаговых беспроводных самоорганизующихся сетей (МБСС) с распределенным управлением. Примерами таких сетей являются высокоскоростные локальные сети Wi-Fi Mesh (стандарт IEEE 802.11s), персональные сети WiMedia (стандарт ЕСМА-368), а также сенсорные сети ZigBee (стандарт IEEE 802.15.4). По сравнению с беспроводными сетями с традиционной архитектурой «клиент-базовая станция» такие сети лучше масштабируются, обладают большей зоной покрытия за счет возможности использования нескольких "шагов ретрансляции пакетов, более высокой отказоустойчивостью, а также адаптивны к условиям работы.

Одной из ключевых задач при построении МБСС является задача обеспечения множественного дос тупа станций к беспроводному каналу. В большинстве современных МБСС базовый механизм доступа к каналу обычно основан па методе случайного множественного доступа с детектированием несущей и предотвращением коллизий - CSMA/CA. Однако, как показывают многие исследования, в многошаговых сетях механизм случайного доступа не гарантирует падежную доставку данных из-за проблемы скрытых станций. Для решения этой проблемы недавно опубликованные стандарты МБСС в дополнение к базовому механизму случайного доступа предлагают опциональный механизм детерминированного доступа, основанный на заблаговременном резервировании интервалов времени для передачи данных и позволяющий существенно увеличить надежность их доставки. Таким образом, в современных МБСС предполагается использование механизма гибридного доступа, объединяющего в себе как случайный, так и детерминированный механизмы доступа к каналу.

Исследованию эффективности механизмов множественного доступа к каналу в беспроводных сетях посвящено значительное количество работ, среди которых следует особо отметить работы российских и зарубежных ученых: О.М. Брехова, A.B. Винеля, К.Ш. Зи-гангирова, В.В. Зяблова, A.II. Кулешова, Д.В. Лакопцсва, А.И. Ляхова, Д.П. Мацнева, В.И. Неймана, Д.С. Осипова, A.A. Сафонова, С.Н. Степанова, A.M. Тюрликова, Е.М. Хо-рова, И.И. Цитовича, М.Ю. 51кимова, G. Bianchi, F. Cali, С. Cicconetti, М. Conti, М. Daneshi, J. Deng, G. Hiertz, E. Hossain, D. Malone, E. Mingozzi, J. Pan, I. Tinnii-ello, C. Wn, Y. Yang и

др. Среди них большинство работ посвящено анализу эффективности только механизма случайного доступа. Другие работы предполагают, что в сети используется только механизм детерминированного доступа. Таким образом, остается открытой задача анализа производительности МБСС, в которых станции могут использовать одновременно два механизма доступа. Кроме того, представляет интерес исследовать, как, используя механизм гибридного доступа, увеличить надежность доставки различных типов трафика в многошаговых сетях, в том числе, мультимедийного трафика, предъявляющего определенные требования к качеству обслуживания, и обеспечить выполнение этих требований.

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

Для достижения поставленной цели в диссертации ставятся и решаются следующие задачи.

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

2. Разработка методов борьбы с интерференцией и повышения эффективности использования канальных ресурсов при передаче данных с помощью механизма детерминированного доступа.

3. Разработка методов обеспечения качества обслуживания при передаче потоковых данных с использованием механизма детерминированного доступа в условиях переменной интенсивности помех.

4. Разработка аналитической модели сети с гибридным доступом для исследования взаимодействия механизмов случайного и детерминированного доступа. Методы исследования

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

В данной работе получены следующие новые результаты:

• проведена классификация возможных случаев интерференции для двух прямых соединений станций многошаговой беспроводной сети, использующих механизм случай-

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

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

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

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

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

Практическая ценность и реализация результатов. Результаты работы внедрены и используются на практике, а также в учебном процессе на кафедре А'1ФТИ (ГУ) «Проблемы передачи и обработки информации» при ИГШИ РАН, что подтверждено соответствующими актами. В частности, разработанные модели и методы использованы в НИР, выполняемых ИППИ РАН в рамках соглашений с Министерством образования и науки РФ и Российским фондом фундаментальных исследований, в международном исследовательском проекте FLAVIA, проводимом в рамках 7-й рамочной программы Евросоюза, а гтакже при проектировании прот околов канального уровня МБСС, разрабатываемых ЗАО «Телум».

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

2. Разработанный метод адаптивного управления резервированиями обеспечивает выполнение требований к качеству обслуживания при передаче потоковых данных в условиях переменной интенсивности помех, используя для этого минимальный объем канальных ресурсов.

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

Апробация работы. Основные результаты диссертации были представлены на ведущих меж/(упародиых и российских конференциях: 3rd Int. Workshop on Multiple Access Communications (Испания, 2010 г.), 8th IEEE Int. Conf. on Mobile Ad-hoc and Sensor Systems (Испания, 2011 г.), 1st Int. Workshop on Wireless Access Flexibility (Россия, 2013 г.), Future Network and Mobile Summit (Португалия, 2013 г.), «Информационные технологии и системы» в 2009-2012 гг., а также на семинарах ИГ1ПИ РАН.

Публикации. Материалы диссертации опубликованы в 12 печатных работах, из них 7 статей ([1-7)) в рецензируемых изданиях, 4 из которых ([1-4]) входят в перечень ВАК, 5 статей ([8-12]) в сборниках трудов конференций. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим.

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения, библиографии и приложения. Общий объем диссертации 130 страниц, включая 43 рисунка и 6 таблиц. Библиография включает 69 наименований.

Глава 1

Механизмы доступа к каналу в многошаговых беспроводных самоорганизующихся сетях

1.1. Технологии многошаговых беспроводных самоорганизующихся сетей

Беспроводные сети передачи информации прочно вошли в жизнь многих предприятий и миллионов людей. Связано это с такими их достоинствами как: гибкость архитектуры, т.е. возможность динамического изменения топологии сети при подключении, передвижении и отключении мобильных пользователей, быстрота проектирования и развертывания сети, а также высокая скорость передачи информации, сопоставимая па сегодняшний день с проводными сетями.

Традиционным подходом к построению беспроводных сетей в настоящее время является создание стационарной инфраструктуры базовых станций, к которой подключаются мобильные абоненты. По такому принципу, например, строятся сотовые сети GSM, UMTS, LTE, а также сети YVÏMAX. Для обеспечения совместной работы устройств в таких сетях и, в частности, для организации доступа устройств к беспроводному каналу применяется централизованное управление, когда базовая станция монопольно координирует передачи все подключенных к пей устройств. К сожалению, такой подход к построению сети имеет ряд недостатков. Во-первых, для построения и обслуживания сети требуется значительные капиталовложения, которые включают в себя высокую стоимость оборудования базовых станций и затраты па построение и поддержание проводной инфраструктуры. Во-вторых, в пределах одной соты базовая станция является «узким местом» сети: передача любых двух устройств, даже находящихся в непосредственной близости друг от друга, возможна только через базовую станцию, что, в свою очередь, приводит к удвоению объема переданной информации. В-третьих, сети с централизованным управлением обладают низкой отказоустойчивостью, так как выход; из строя базовой станции или ее перегрузка делает невозможным работу всех подключенных к пей устройств.

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

сетей - сетей класса ad hoc. В таких сетях отсутствует какая-либо заранее развернутая инфраструктура, а все устройства являются равнозначными и подчиняются одним и тем же правилам ¡заботы. Одним из наиболее ярких представителей технологий такого рода являются беспроводные локальные сети Wi-Fi acl hoc, построенные на базе стандарта IEEE 802.11 [13] и работающие в режиме распределенного управления.

Изначально связь в сетях Wi-Fi ad hoc могла осуществляться только между устройствами, находящимися в зоне непосредственного радиоприема друг друга. Ввиду этого ограничения сети Wi-Fi ad hoc обладали сравнительно невысокой зоной покрытия. Для расширения зоны покрытия была предложена архитектура многошаговых беспроводных самоорганизующихся сетей (МБСС), в которых передача пакетов между устройствами, находящимися вне зоны радиоприема друг друга, может быть осуществлена путем последовательной передачи (ретрансляции) пакетов по цепочке соседних устройств. Возможность построения МБСС па базе технологии Wi-Fi (сетей Wi-Fi Mesh), была оформлена в виде стандарта IEEE 802.11s [14j. принятого в 2011 г. и являющегося дополнением к базовому стандарту [13].

Следует отметить, что создание МБСС возможно не 'только на базе технологии Wi-Fi. В рамках международного комитета IEEE 802 LAN/MAN Standards Committee (LMSC) по стандартам локальных и городских сетей был разработаны стандарт IEEE 802.15.4 [15], в котором регламентируется возможность организации сенсорных многошаговых сетей ZigBee. Кроме того, организацией ЕСМА (European Computer Manufacturers Association) была создана технология многошаговых персональных сетей WiMedia (стандарт ЕСМА-368 [16]).

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

может принести к неудачной передаче обеих станций. Механизм детерминированного доступа, наоборот, позволяет станциям заблаговременно резервировать интервалы времени работы капала для получения в них бесконкурентного доступа. Более подробное описание механизма гибридного доступа приведено в разделе 1.2.

Другими важными задачами, которые должны быть решены для обеспечения работы МБСС, являют ся задача координации станций и задача маршрутизации. Решению данных задач посвящено множество работ, среди которых следует отметить |17-23|. Результаты данных работ используются в данной диссертации, однако основной целыо диссертации является анализ эффективности работы механизма гибридного доступа в МБСС. Под эффективностью работы механизма доступа будем понимать достижение определенных показателей качества таких, как пропускная способность или емкость сети, выраженная в числе одновременно передаваемых потоков, задержка, т.е. время, необходимое для передачи пакета, и вероятность потери пакета.

Так как реализации механизма гибридного доступа в различных технологиях построения МБСС отличаются между собой, то в качестве основного объекта исследования выбраны сети Wi-Fi Mesh как сети, обеспечивающие одновременно высокие скорости передачи и большую зону покрытия. Однако многие результаты, полученн�