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

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

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

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

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

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

В диссертации рассматриваются и сравниваются два метода передачи потоковых данных, которые отличаются между собой тем, какая политика квитирования используется в интервалах резервирования, а именно – метод с подтверждениями и метод без подтверждений. При использовании метода с подтверждениями на каждом шаге i маршрута устанавливается одно резервирование с периодом Ti (Ti < T ) и длительностью каждого интервала, достаточной для осуществления одной попытки передачи, включая время передачи подтверждения. На шаге i пакет обслуживается до тех пор, пока он либо не будет передан успешно, т.е. будет получено подтверждение, лиQoS бо не истечет время Di, отведенное на его передачу. При использовании метода без подтверждений на каждом шаге устанавливается Ki одинаковых резервировавший с периодом T и длительностью каждого интервала, достаточной для осуществления одной попытки передачи, т.е. для каждого пакета осуществляется ровно Ki попыток передачи. Для каждого из методов показывается, как при заданных вероятностях qi неудачной попытки передачи разделить требования QoS между шагами передачи (т.е. назначить на кажQoS QoS QoS дом шаге ограничения P LRi и Di, чтобы i (1P LRi ) = 1P LRQoS и i Di = DQoS ) и выбрать параметры резервирований, чтобы на каждом шаге выполнялись найденные ограничения и при этом суммарный объем зарезервированных канальных ресурсов был минимален. Сравнение двух методов показывает, что в случае передачи пакетов малого размера (что имеет место при передаче голосовых потоков) и использования высоких скоростей передачи метод без подтверждений является более предпочтительным, так как он обеспечивает выполнение требований QoS, используя для этого меньший объем канальных ресурсов, чем метод с подтверждениями.

Рассмотрим один шаг передачи потока постоянной интенсивности, на котором заданы требования QoS (P LRQoS и DQoS, индекс i опущен для краткости записи), а для передачи используется метод без подтверждений. При использовании метода без подтверждений выполнение ограничения на задержку DQoS обеспечивается таким размещением интервалов резервирований, что последняя попытка передачи пакета расположена не далее, чем DQoS от времени поступления пакета в очередь. Таким образом, для выполнения требований QoS на данном шаге передачи необходимо установить такое число резервирований (число попыток передачи пакета), при котором будет выполнено ограничение на долю потерянных пакетов. Как уже отмечалось выше, попытки передачи пакетов в зарезервированных интервалах могут быть неудачными из-за помех, вызванных случайным шумом и интерференцией со стороны других станций. Так как интенсивность передач других станций сети может изменяться со временем, то интенсивность помех в интервалах резервирований также может изменяться. В связи с этим для выполнения требований QoS необходимо настраивать число резервирований, используемых для передачи потока, с учетом возможных изменений интенсивности помех, а также корреляции ошибок, вызванной наложением во времени передач других станций на соседние интервалы резервирований.

Для решения данной задачи в разделе 4.2 предлагается метод управления резервированиями, к которому предъявляются следующие требования. 1) Должно выполняться ограничение на долю потерянных пакетов с некоторой надежностью. Метод выполняет ограничение на долю потерянных пакетов с надежностью, если для любого интервала времени фиксированной длительности, за который передается W пакетов, доля потерянных пакетов L/W меньше заданного ограничения P LRQoS с вероятностью большей, либо равной, т.е. P L/W P LRQoS. 2) При условии выполнения ограничения на долю потерянных пакетов число используемых резервирований должно быть минимально. 3) Метод должен быть стабилен, т.е. частота установления резервирований F A должна быть много меньше порога F A0 = 1/tsetup, где tsetup – характерное время оповещения передатчиком и приемником своих соседей об установлении нового резервирования.

Суть предлагаемого метода заключается в периодическом запуске процедуры, состоящей из трех шагов. На первом шаге предполагается, что свойства канала существенно не меняются за интервал времени между двумя последовательными запусками процедуры. На основании этого предположения и с учетом информации X об успешных и неудачных попытках передачи последних h пакетов в каждом резервировании из текущего множества резервирований Rcur (X – бинарная матрица размером |Rcur | h, где |R| – размер множества R) строится функция PX (R), являющаяся оценкой вероятности успешной доставки пакета при использовании множества R резервирований. Данная функция определяется для любого множества R, которое можно получить из текущего множества Rcur только добавлением новых или только удалением некоторых из существующих резервирований. Для любого множества R Rcur вероятность PX (R) можно оценить как PX (R) = Для предсказания качества новых резервирований (т.е. для случая R R ) используются следующие предположения. 1) Вероятность возникновения ошибки при передаче пакета в интервале резервирования i зависит только от того, возникла ли ошибка при передаче этого пакета в соседнем интервале резервирования (i 1), причем вероятность возникновения ошибки в интервале резервирования i при условии, что возникла ошибка в интервале резервирования (i 1), определяется формулой i,i1 = qi + (1 qi )ei,i1, где qi – безусловная вероятность ошибки при передаче в интервале резервирования i, а i,i1 – расстояние между резервированиями i и i 1 (т.е. промежуток времени между началами двух соответствующих интервалов резервирований). 2) Вероятность qi ошибки при передаче в новых резервированиях (т.е. для i Rcur ) равна средней вероятности для уже установленных резервирований. Используя информацию X, оцениваются вероятности qi и i,i1 для всех резервирований из множества Rcur, и с помощью метода наименьших квадратов находится оценка параметра. Далее, используя введенные выше предположения, оцениваются вероятности i,i1 для тех пар резервирований (i, i 1), для которых резервирования i или i 1 не принадлежат множеству Rcur, и находится искомая оценка вероятности PX (R) = 1 q1 i=2 i,i1.

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

FW,PX (R) – функция распределения неудач в W испытаниях Бернулли с вероятностью успеха PX (R), · – округление снизу.

Чтобы повысить стабильность метода, на третьем шаге новое множество Rnew резервирований формируется с учетом истории решений, полученных за l последних запусков процедуры, т.е. с учетом множеств Rs, Rs1,..., Rsl+1, где s – порядковый номер текущего запуска процедуры.

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

Для анализа области применимости и настройки параметров метода в диссертации рассматривается синтетический сценарий, в котором интенсивность помех скачкообразно меняется в конце каждого интервала времени Tchange, т.е. 1/Tchange – характерная частота изменений условий в канале. В результате экспериментов были найдены диапазоны значений параметров, h и l, которые при любых значениях Tchange > Tchange позволяют удовлетворить заданным ограничениям P LRQoS, и F A0 при используемом числе резервирований, близком к минимальному. 1/Tchange – это характерная частота изменений условий в канале, выше которой метод не позволяет удовлетворить заданным ограничениям при любых значениях, h и l. Показано, что Tchange – величина порядка h/(1 ), где h – среднее значение из полученного диапазона значений параметра h. Сделанные выводы подтверждены с помощью имитационного моделирования применения метода управления резервированиями в реальном сценарии сети с решетчатой топологией, в котором передачи в интервалах резервирований подвержены интерференции со стороны других станций сети.

В разделе 4.3 метод управления резервированиями расширяется на случай, когда станции могут устанавливать резервирования двух типов: с одношаговым или двухшаговым методом защиты. Для этого любое множество резервирований представляется как объединение R = Roh Rth двух подмножеств, каждое из которых содержит резервирования одного типа. Предполагается, что ошибки при передаче в интервалах резервирований разных типов возникают независимо, поэтому PX (R) = 1(1PX (Roh ))(1PX (Rth )). Кроме того, резервированиям разных типов приписывается разная стоимость, чтобы учесть разницу в числе станций, блокируемых при установлении резервирований. Стоимость множества резервирований C(R) = |Roh | + cth |Rth |, Рис. 2. Средняя стоимость C множества резервирований в зависимости от доли времени Fth, когда передают двухшаговые соседи; cth = где cth – отношение числа станций, находящихся в двухшаговой окрестности от владельца и адресата резервирований, к числу станций в одношаговой окрестности. Таким образом, на втором шаге процедуры находится множество резервирований, которое минимизирует функцию стоимости C(R). На рис. 2 представлены результаты эксперимента, в котором передачи в интервалах резервирований подвержены интерференции, вызванной передачами двухшаговых соседей. Данные результаты показывают, что адаптивный выбор метода защиты для устанавливаемых резервирований позволяет существенно уменьшить объем блокируемых канальных ресурсов по сравнению со случаями использования только одношагового или только двухшагового метода защиты при выполнении требований QoS.

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

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

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

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

В разделе 5.2 разрабатывается аналитическая модель взаимодействия МСД и МДД, которая позволяет оценить пропускную способность станции, использующей МСД, при условии, что часть ресурсов канала зарезервирована с помощью МДД, а также сравнить эффективность двух предложенных способов. Рассматриваются два соединения: AB и CD. Станция A для передачи данных устанавливает резервирование с периодом T и длительностью DM каждого интервала. Станция С, работая в режиме насыщения, передает пакеты фиксированного размера L с помощью только МСД, причем время, необходимое для передачи одного пакета и подтверждения, равно Ttr. Ввиду отсутствия других станций, использующих МСД, значение конкурентного окна станции С постоянно и равно CWmin. Обозначим W = CWmin + 1.

Для нахождения пропускной способности S станции С рассматривается один период резервирования T ; тогда S = LK/T, где K – среднее число передач станции С за один период. Передача станции С рассматривается как марковский процесс, состояние которого описывается числом слотов i, которые станция C должна отсчитать после окончания интервала резервирования.

Чтобы найти значение K определяются вероятности pjk|i того, что система перешла из состояния i в состояние j и при этом было передано ровно k пакетов. Для нахождения данных вероятностей для каждого из способов отсчета слотов отсрочки рассматривается различные случаи h = {1, 2, 3}, которые отличаются между собой тем, в какой момент времени закончилась последняя передача станции С в рассматриваемом периоде, и определяются вероятности pjk|i для каждого случая h. Случай 1 возникает, когда после последней передачи станции С прошел цикл отсрочки (цикл отсрочки – интервал времени между началом и окончанием отсчета слотов отсрочки, содержащий случайное число слотов от 0 до W 1), но станция С не может начать передачу, так как передача пересечет интервал резервирования (см.рис.1 – «запрет передачи»); случай 2 – когда от окончания последней передачи до интервала резервирования остался интервал времени, меньший AIF S; случай 3 – когда отсчет слотов отсрочки был прерван интервалом резервирования. В частности, для способа 1 вероятность pjk|i вычисляется по формуле где s(k, l) = W k v=0 (1)v+l+W v k lW v – вероятность того, что за k цикk лов отсрочки был отсчитано ровно l слотов, l1 – максимальное число слотов отсрочки, которое может быть отсчитано за k циклов отсрочки, а условие R1 (l, i, k) проверяет, что при заданных l, i и k имеет место случай 1. В формуле для нахождения s(k, l) используется доопределение отрицательных биномиальных коэффициентов k = k(k1)···(kv+1) (при v > 0) согласно Феллеру.

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

Утверждение 1. Пусть s(n, j) – вероятность того, что сумма n случайных независимых целочисленных величин, равномерно распределённых на интервале [0, W 1], равна j. Тогда ряд uj = s(n, j) сходится и равен:

В диссертации получены формулы для pjk|i в остальных случаях h = {2, 3}, аналогичные (1) и справедливые для обоих способов. Далее находятся вероh) ятности перехода из состояния i в состояние j: pj|i = k pjk|i и стациh онарные вероятности i состояний i, позволяющие получить среднее число пакетов, переданных за один период резервирования K = i i k,j kpjk|i.

В разделе 5.3 приводится сравнение численных результатов, полученных с помощью имитационной и аналитической моделей, которое показывает высокую точность последней. С помощью аналитической модели сравнивается эффективность двух предложенных способов отсчета слотов отсрочки и показывается, что оба способа обладают одинаковой эффективностью (дают одинаковые пропускные способности) в широком диапазоне сценариев. Кроме того, с помощью имитационного моделирования данный вывод подтвержден для случая, когда в сети одновременно работают несколько станций, использующих МСД. Также аналитическая модель используется для сравнения различных способов размещения интервалов резервирования при фиксированной доле ресурсов M AF = DM /T, выделенных под МДД. Результаты показывают, что группировка интервалов резервирований (увеличение DM ) позволяет существенно увеличить пропускную способность станций, использующих МСД. Данный результат также позволяет сделать вывод, что использование величины M AF Limit, введенной в стандарте для ограничения доли ресурсов, выделенных под МДД, не гарантирует какой-либо минимальной пропускной способности для станций, использующих МСД, и требуется разработка другого механизма, обеспечивающие такие гарантии.

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

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

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

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

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

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

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

Список публикаций 1. А. Krasilov. Physical Model Based Interference Classication and Analysis // Lecture Notes in Computer Science, Vol. 6235. 2010. Pp. 1–2.

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

2013. № 9. С. 34–52.

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

4. E. Khorov, А. 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. Conf.

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. А.Н. Красилов. Физическая модель интерференции прямых соединений:

классификация и анализ возможных случаев // Тр. конф. «Информационные технологии и системы». 2009. С. 15–22.

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

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

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

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