автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Анализ механизмов синхронизации в персональных и локальных беспроводных сетях

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

00345367Т

Сафонов Александр Александрович

Анализ механизмов синхронизации в персональных и локальных беспроводных сетях

Специальность 05.13.13 - Телекоммуникационные системы и компьютерные сети

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

2 1 НОЯ 2008

Москва-2008

003453677

Работа выполнена в Институте проблем передачи информации им. А.А. Харкевича

РАН

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

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

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

доктор технических наук, с.н.с. Ляхов Андрей Игоревич доктор технических наук, профессор, Зяблов Виктор Васильевич кандидат технических наук, Винель Алексей Викторович Институт проблем управления им. В.А. Трапезникова РАН, г.Москва

Защита состоится_декабря 2008 г. в~tL часов на заседании диссертационного

совета Д.002.077.01 при Учреждении Российской академии наук Институт проблем передачи информации им. A.A. Харкевича РАН по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, 19.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Институт проблем передачи информации им. А.А. Харкевича РАН.

Автореферат разослан '^"ноября 2008 г.

Ученый секретарь

диссертационного совета Д. 002.077.01, доктор физико-математических наук И.И. Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Беспроводные технологии вытесняют проводные повсюду, где могут обеспечить приемлемые скорость и качество связи. Они прочно вошли в жизнь многих предприятий и миллионов людей, потому что позволяют решать широкий круг задач: от организации персональных и локальных сетей до построения сетей масштаба региона. Массовое внедрение в современных ноутбуках, коммуникаторах и телефонах получили локальные сети стандарта IEEE 802.11 под торговой маркой Wi-Fi и персональные сети IEEE 802.15.1 под торговой маркой Bluetooth, предполагающие централизованное управление сетью на канальном уровне устройством-координатором. В таких сетях под синхронизацией понимается в основном синхронизация внутренних часов устройств с часами координатора.

Координатор является самым уязвимым устройством сети, и выход его из строя делает работу всех остальных устройств в сети невозможной. В связи с этим в последние годы во всем мире наблюдается повышенный интерес к сетям с распределенным управлением сетью на канальном уровне. Например, в комитете IEEE по стандартам созданы группы 802.11s (Wi-Fi Mesh) и 802.15.5 (High Rate WPAN Mesh), разрабатывающие протоколы локальных и персональных mesh-сетей, а альянс ведущих телекоммуникационных компаний мира WiMedia разработал стандарт персональных сетей ЕСМА 368 для соединения, например, компьютера, монитора и периферийных устройств без проводов. Все эти стандарты предполагают распределенное управление на канальном уровне: все устройства равноправны и подчиняются одним и тем же правилам работы, благодаря чему сеть лучше масштабируется и поддерживает режим энергосбережения и мобильность устройств по сравнению с сетью с централизованным управлением. Кроме того, отсутствие координатора делает сеть надежнее: выход из строя одного или даже нескольких устройств оставляет возможность непрерывной работы оставшихся устройств без изменений настроек сети, что было бы невозможно в сети с централизованным управлением.

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

В данной работе под синхронизацией в сети понимается обмен между устройствами сети специальными синхрокадрами для координации их распределенной работы. Эти кадры, называемые бйконами (от англ. beacon, букв, «маячок»), являются контейнерами, в которые многие механизмы сети вкладывают свою сигнальную информацию, что избавляет их от необходимости рассылать свои

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

Анализу работ, посвященных исследованию протоколов IEEE 802.11 и WiMedia и построенных на их базе беспроводных сетей, посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: А.В.Винеля, В.М.Вишневского, Д.В.Лаконцева, А.И. Ляхова, Д.Н. Мацнева, М.Ю. Якимова, G. Bianchi, F. Cali, M. Conti, E. Gregory, G.R. Hiertz, Q. Ni, Y.Zang и др. Однако большая часть этих работ посвящена оценке производительности методов передачи данных, но не эффективности механизмов синхронизации. В работах же, посвященных оценке эффективности механизмов синхронизации в сетях IEEE 802.11, например, в работах L. Huang, Т. Lai, D. Zhou, под синхронизацией понимают исключительно синхронизацию внутренних часов станций, и при этом охватываются лишь сети IEEE 802.11 в режиме ad hoc, но не mesh-сети. В работах, посвященных оценке эффективности механизмов синхронизации в сетях WiMedia, например, в работах Q. Wu, Y. Xiong, Z. Guo, проводится оценка эффективности только отдельной процедуры сжатия бикон-периода без учета присоединения устройств к сети. Таким образом, не существует моделей, позволяющих проводить всесторонний анализ механизмов синхронизации в современных персональных и локальных беспроводных сетях с распределенным управлением, в то время как от эффективности этих механизмов напрямую зависит производительность сетей в целом.

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

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

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

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

1. Метод предотвращения тупиковых ситуаций при рассылке сИнхрокадров в беспроводных персональных сетях с распределенным управлением.

2. Аналитические модели процесса присоединения устройств к беспроводной персональной сети с распределенным управлением.

3. Аналитические модели различных механизмов синхронизации в беспроводных mesh-сетях стандарта IEEE 802.1 Is.

Научная новизна. Впервые разработаны математические модели для анализа эффективности механизмов рассылки синхрокадров устройствами в персональных и локальных беспроводных сетях с распределенным управлением стандартов Wi-Fi Mesh и WiMedia, позволяющие оценивать следующие вероятностные и временные показатели: средние значения и распределения времен присоединения устройства к сети и смены сетью канала; вероятность блокирования сети; вероятность успешной передачи синхрокадра.

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

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на:

о Межд. конференциях по проблемам управления (Москва, 2006г. и 2008г.).

о IEEE Consumer Communications and Networking Conférence (USA, 2006r.).

о 15th IST Mobile & Wireless Summit (Greece, 2006r.).

о IEEE Int. Symposium on Consumer Electronics (С.-Пб., 2006r.).

о Конференциях молодых ученых и специалистов "Информационные технологии и системы" (Звенигород, 2007г. и Геленджик, 2008г.).

о IEEE Int. Symposium on Computers and Communications (Portugal, 2007r.).

о IEEE Int. Symposium on Personal, Indoor and Mobile Radio Communications (Greece, 2007 и France, 2008).

о Int. Workshop on Multiple Access Communications (С.-Пб., 2008г.).

о Семинарах ИППИ РАН.

Публикации. По теме диссертации опубликовано 15 научных работ. Из них 4 статьи [1 - 4] опубликованы в рецензируемых научных журналах, 2 из которых утверждены в перечне ВАК. 11 работ [5 - 15] опубликованы в трудах ведущих международных и российских научно-технических конференций.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 42 наименования. Работа изложена на 110 страницах и содержит 37 рисунков и 2 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе описаны механизмы синхронизации в высокоскоростных беспроводных сетях с распределенным управлением стандартов WiMedia (прототип стандарта IEEE 802.15.5), IEEE 802.11 в режиме ad hoc и IEEE 802.11s, основанные на регулярной рассылке специальных широковещательных кадров, называемых биконами (от англ. beacon). С помощью биконов устройства обозначают свое присутствие в сети, рассылают информацию о своих возможностях, синхронизируют внутренние часы с часами других устройств. Кроме того, биконы используются некоторыми механизмами в качестве контейнеров для рассылки своих сигнальных пакетов, например, механизмами энергосбережения и резервирования канала.

В связи с большой функциональной нагрузкой на биконы их рассылку стараются сделать более надежной, чем рассылку прочих широковещательных кадров. В данной работе предполагается, что помехоустойчивое кодирование защищает передачу биконов от помех, и передача бикона может быть неудачной только из-за коллизии, когда два устройства передают одновременно. Для того же, чтобы снизить вероятность коллизии биконов, под их рассылку выделяют специальное время, в течение которого передача кадров данных запрещена. В частности, в сетях WiMedia время работы сети разделено на суперкадры, в начале которых расположен так называемый бикон-период, содержащий слоты для передачи биконов. Похожим образом в сетях IEEE 802.11 в режиме ad hoc, а также в синхронном режиме mesh-сетей IEEE 802.11s под рассылку биконов выделено специальное окно передачи биконов.

Максимальная возможная длина бикон-периода Текущая длина бикон-периода

Занятая часть Окно Я

бикон-периода

0 1 2 3 4 5 6 7 8 9 10

Мах BP

HOBS

Рис. 1. - Структура бикон-периода в сети WiMedia

В разделе 1.2 основное внимание уделено механизму синхронизации в персональных сетях WiMedia. На рис. 1 показана структура суперкадра. За последним занятым бикон-слотом HOBS (Highest Occupied Beacon Slot), следуют R слотов, которые называют окном присоединения устройств. Текущая длина бикон-периода зависит от количества устройств в сети, но она не может превышать максимально допустимого числа бикон-слотов МахВР. Если разница М между МахВР и HOBS меньше обычного размера окна, то R полагается равным оставшемуся числу слотов в бикон-периоде М.

Для присоединения к сети устройство равновероятно выбирает бикон-слот из R(M) слотов окна и посылает свой бикон в выбранный слот в следующем суперкадре. Если в результате случайного выбора слотов биконы нескольких устройств оказались в одном и том же слоте, то говорят о коллизии биконов. Чтобы ее разрешить, устройства заново выбирают слоты в окне, которое отсчитывается от нового значения HOBS, если они получают сигналы от других устройств, что их биконы оказались в коллизии, в течение V суперкадров.

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

В разделе 1.3 описаны механизмы рассылки биконов в ad hoc сетях IEEE 802.11 и mesh-сетях IEEE 802.1 Is. Станция, организующая сеть ad hoc, задает серию моментов времени ТВТТ (Target Beacon Transmission Time), каждый из которых обозначает начало так называемого бикон-интервала. В каждый момент ТВТТ начинается окно передачи биконов, во время которого для уменьшения вероятности коллизии передача данных запрещена. Чтобы передать бикон, станция выбирает случайную задержку, равную целому числу слотов длиной а (базовая единица времени метода CSMA/CA), по истечении которой начинает передачу своего бикона. При получении бикона от любой из станций в сети ad hoc все остальные станции отменяют передачу своих биконов.

В текущей версии IEEE 802.11s mesh-сетей протокол синхронизации вынесен за пределы стандарта и может подключаться как внешний модуль, когда это необходимо, что связано с чрезвычайно высокой вариативностью сценариев применения технологии Wi-Fi Mesh. В настоящее время самым проработанным является протокол синхронизации, описанный в первой версии IEEE 802.1 ls/D1.0. Синхронные устройства в mesh-сети передают биконы по тому же алгоритму, что и станции в сетях ad hoc, но не отменяют собственную передачу, если получили бикон от соседнего устройства mesh-сети. Некоторые механизмы mesh-сетей, в частности, механизм детерминированного доступа MDA, накладывают на биконы дополнительную функциональность, поэтому одного бикона от случайно выбранного mesh-устройства оказывается недостаточно.

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

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

В разделе 2.1 описаны проблемы описанной в стандарте схемы выбора бикон-слотов. Первая проблема - это блокирование сети. Когда одно из устройств занимает самый старший слот в бикон-периоде МахВР, бикон-период считается заполненным; следовательно, другие устройства не могут присоединиться к сети или выбрать новый слот, разрешая коллизию, пока самый старший слот не будет освобожден. Иными словами, в течение некоторого времени устройства не могут присоединиться к сети или разрешить коллизию, что приводит к существенным задержкам при передаче данных.

Другой проблемой является потенциальное зависание сети, которое происходит, например, в следующей ситуации: некоторое устройство А занимает предпоследний слот МахВР-1, в то время как устройства В и С находятся в коллизии, то покидая сеть, то вновь присоединяясь к ней, не давая устройству А сдвинуть свой бикон в младший слот.

Для решения проблемы зависания сети автор предлагает алгоритм WBR (Wait Before Rejoin - ждать перед повторным присоединением), заключающийся в введении дополнительной задержки W>W0=U+1 между отсоединением устройств В и С от сети и повторной попыткой их присоединения, дающую устройству А достаточно времени, чтобы сдвинуть свой бикон в младший слот и дать устройствам В и С шанс избежать коллизии при повторном присоединении. В разделе 2.3 доказано, что величина W для //-шаговой сети (Н < 4) должна удовлетворять следующему соотношению:

W>Wm(H) = (2H-l)(U + \) + l.

В разделе 2.2 анализируются два сценария работы сети, состоящей из Л"+1 устройства. Одно из устройств А переключается на новый канал, например, из-за того, что вблизи А работает другая сеть, интерферирующая с А. На новом канале устройство А создает новую сеть (сценарий а) или присоединяется к уже существующей сети (сценарий б). В обоих сценариях остальные К устройств переключают канал вслед за А.

Разрабатывается аналитическая модель для оценки следующих интегральных показателей для одношаговой сети: вероятность блокирования сети на новом канале Pf, среднее время присоединения устройства к сети Tw и среднее время смены сетью канала Гс. При этом для упрощения анализа предполагается, что устройства, вынужденные покинуть сеть из-за того, что она оказалась заблокированной, используют алгоритм WBR и после ожидания в течение W суперкадров присоединяются к сети без коллизий. Такой исход является наилучшим, поэтому это предположение названо оптимистичным.

Процесс смены канала К устройствами, которые присоединяются к сети, созданной устройством А, представляется случайным процессом У = {у,,/= 0,1,...} с дискретным временем. Состояния процесса j, = {m(t),k(t)} соответствуют началу суперкадров, когда устройства выбирают новые бикон-слоты. В определении состояния m(t) = МахВР- HOBS; k(t) - количество устройств, еще не завершивших присоединение в данном состоянии процесса. Так как все К устройств начинают процесс присоединения в суперкадре 1, они могут выбирать новые слоты, разрешая возникающие коллизии, только в суперкадрах l+(i/+l)/, где i= 1,2,...Поэтому за единицу времени процесса J выбирается интервал U+1, т.е. t = i соответствует началу суперкадра 1 +(U +l)i. Процесс J является марковским по определению, потому что вероятность перехода из состояния j, в состояние зависит только от состояния j, в момент времени t и не зависит от предыдущих состояний.

Доказана лемма: число способов, каким можно разместить к устройств по г слотам при условии, что последний выбранный бикон-слот имеет номер z такой, что 1 <z<r, равноПц = где С] = х\1[у\(х-у)\], если ни одно из устройств не

попачо в коллизии. Если же число устройств в коллизиях с >2, то число mama размещений равно

n?=Ct(z- 1)!У (v + k~c) V(v,c),

' tiv\(z-v-k+c)l

где V(v,k) = vi-fic:(y,h-fic:-j^—ficr,v(y,k-u) при v<k / 2, и

v=l " и=1 (k -ujl v=l

V{v,k) = 0 при v>k/2.

Для оценки вероятности блокирования сети Pf, рассматриваются три возможные ситуации в начале суперкадра 5, = l + (f/ + l)f, первые две из которых означают завершение процесса J:

1. Все устройства присоединились успешно, коллизий не произошло.

2. После выбора устройствами новых слотов последний слот в бикон-периоде оказался занят, т.е. HOBS = МахВР, с устройств попали в коллизии, и сеть оказалась заблокированной.

3. После выбора устройствами бикон-слотов новое значение HOBS меньше, чем МахВР, и с устройств попали в коллизии. Процесс продолжается, и в следующий момент времени f+1, соответствующий суперкадру , количество свободных слотов, доступных для присоединения устройств и разрешения коллизий, составляет m(t+\) = m(t) - z, и k(t+\) = c устройств выбирают новые бикон-слоты.

Продолжение процесса J представляет собой тот же процесс J, но с другими начальным условиями: т = m{t+\) и k = k(t+1). Следовательно, можно записать:

Шш) i

Pf(m,k) = Kf(m,k)+ ^^^c(m,k,z,c)Pf(m-z,c),

<=2

где 7if(m,k) - это вероятность того, что сеть окажется заблокированной; ftL(m,k,z,c) - вероятность того, что процесс J продолжится.

Так как общее число вариантов разместить к устройств по R(m) слотам равно [R{m)]k, то, используя лемму, можно найти яг(т,к) и nc{m,k,z,c)\

к

К¡(т,к) = 1 (R{m) = т)т~к^пк;", Kc(m,k,z,c) = \(z*m)[R{m)Yk«cfc,

с=2

где 1 (ВЫРАЖЕНИЕ) обозначает булев индикатор истинности ВЫРАЖЕНИЯ.

Вместо Гш удобнее оценить Ts\ - сумму 7\„ по всем устройствам. Очевидно, что Ти = т;и(m = M0,к = К)/К И Тс =Тс(т = Ма,к = К), где аргументы т = М0 и к = К показывают, что и TL и Т'и зависят от начальных значений процесса У.

В момент времени t, когда m = m(t) и к = k(t), все к устройств выбирают бикон-слоты и посылают свой бикон, затрачивая на это один суперкадр. Если реализована ситуация 1, то процесс присоединения завершается немедленно. В ситуации 2 с устройств затрачивают U суперкадров для того, чтобы зафиксировать коллизию, затем покидают сеть на W суперкадров, и, наконец, успешно присоединяются, затрачивая еще один суперкадр. В ситуации 3 с устройств затрачивают U суперкадров для того, чтобы зафиксировать коллизию, и в следующий момент времени Г+1 с устройств повторяют выбор слотов, и, соответственно, вновь попадают в одну из трех описанных ситуаций. Таким образом, имеем следующие рекуррентные соотношения для Т'и и Тс:

к R(m) I

Т;„ (m,k) = k + \(R(m) = m)(U + W +1 )>пк £enkw + £ (m, к, z, c)[cU + 7„l, (m - z, c)],

t'=2 ;=1 £=2 KU«) «.

Tc (m,k) = 1 + (U + W + \)Kf (m,к) z,c)[U +TC (m-z,c)].

;=1 c=2

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

Разработанные модели позволяют находить исследуемые временные характеристики Тс и Тш для функции R(M) общего вида. В данной работе численное моделирование было проведено для двух классов функций:

о стандартная схема выбора с фиксированным окном: Л(М)станд = min (D, M =

МахВР - HOBS), где D - константа (по стандарту D = 8) о пропорциональная схема выбора, предложенная автором: R{M) = ceil(аМ), где О < а < 1, a ceil(jc) обозначает наименьшее целое, не меньшее х.

При вариации исследуемого сценария, количества устройств в сети, числа шагов сети, топологии сети были найдены оптимальные значения параметров D„pl и «„,,„ минимизирующие среднее время присоединения одного или нескольких устройств, соответственно Tsu и Тс.

Исследования показали, что оптимальное значение а„р, гораздо менее чувствительно к изменению числа устройств в сети и других параметров, чем D„p, в схеме с фиксированным окном. Поэтому пропорциональная схема выбора оказывается более универсальной и, следовательно, предпочтительнее для реализации.

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

L = {/„,/,,/,,...}, т.е. ],={т,к,Ц. Компонента вектора /«>0 принимает значение, равное разнице номеров самого старшего занятого слота HOBS и самого старшего успешно занятого слота. Тогда, если сеть заблокирована, то 10 описывает количество слотов, которые освободятся, когда устройства, находящиеся в коллизии, покинут заблокированную сеть. Компонента вектора где j > 0, описывает, сколько слотов освободится в результате j-го сжатия.

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

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

0,000001 0,00001 0,0001 0,001 0,01 0,1

D = 8, К = 12 D = 80, К = 12 а = 0.8, К = 12

-Г

it«*1

| Т, суперкадров

0 5 10 15 20 25 30 35 40

Рис. 2. Вероятность того, что за время Гсеть не переключится на новый канал

На рис. 2 показаны графики вероятности того, что переключение сети на новый канал не завершится за время Т, полученные для стандартной схемы с рекомендованным значением О = 8 и для оптимизированных схем с фиксированным и пропорциональным окном. Видно, что с вероятностью 99% гарантируется

переключение сети в течение 21 суперкадров (почти 1.5 секунды) при использовании стандартной схемы, и за 9 суперкадров (около 0.5 секунды) при использовании оптимизированных схем, при одном и том же числе устройств в сети К.

Сравнивая оптимизированные фиксированную и пропорциональную схемы выбора, можно отметить, что вероятность того, что за время 8 < 7 < 40 сеть не переключится на новый канал, при использовании первой из них больше, чем при использовании второй. Это означает, что пропорциональная функция выбора размера окна R{M) дает лучшую гарантию, что сеть успеет переключиться на новый канал за определенное время, приемлемое для пользователя.

В четвертой главе рассмотрены механизмы синхронизации в mesh-сетях стандарта IEEE 802.Ils.

В разделе 4.1 описаны возможные алгоритмы рассылки биконов mesh-сетях IEEE 802.1 Is. Самый простой способ заключается в использовании метода множественного доступа к каналу с контролем несущей и предотвращением коллизий (CSMA/CA), как и для передачи данных. Однако при этом с ростом числа устройств в mesh-cera и интенсивности трафика вероятность коллизии биконов друг с другом и с другими кадрами в сети быстро растет. Станция не может проверить, был ли бикон передан успешно или попал в коллизию (в отличие от кадров данных), так как биконы являются широковещательными кадрами, получение которых ни одна из станций в сети не подтверждает. Соответственно, невозможна повторная передача бикона в случае коллизии. Это означает, что если бикон mesh-устройства попал в коллизию с другим биконом или вообще с любым другим кадром, то информация от этого mesh-устройства не будет получена другими mesh-устройствами, по крайней мере, в течение бикон-интервала. В большой mesh-сети с интенсивным обменом данными между устройствами вероятность повторных, т.е. в течение нескольких бикон-интервалов подряд, коллизий бикона для каждого устройства становится настолько высокой, что синхронизация сети может нарушиться.

Чтобы исключить коллизии биконов с кадрами других типов, в сетях IEEE 802.11 в режиме ad hoc для рассылки биконов зарезервировано специальное временное окно, которое повторяется каждый бикон-интервал. В нем передача кадров данных запрещена. Этот подход был принят в первой версии стандарта mesh-сетей IEEE 802.11s.

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

о Алгоритм без прослушивания: Задержка выбирается равновероятно из окна передачи биконов и отсчитывается безотносительно занятости канала: значение таймера обратного отсчета уменьшается на единицу каждый раз по прошествии временного слота а. После истечения задержки станция начинает передачу бикона, если канал свободен, или отменяет передачу своего бикона, если канал оказывается занят.

о Алгоритм с прослушиванием: задержка равновероятно выбирается из конкурентного окна и отсчитывается, как и при передаче данных. Если среда не занята в течение слота а, станции уменьшают значение своих таймеров на единицу. Если одна из станций начинает передачу, другие станции замораживают свои таймеры на время передачи плюс интервал времени DIFS. Если происходит коллизия, то вместо времени DIFS используется более длинный интервал EIFS. После истечения задержки станция начинает передачу бикона.

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

о h{N) - среднее число биконов, успешно переданных в течение одного окна передачи биконов, в зависимости от числа N устройств в сети;

о a(N) - вероятность успешной передачи бикона в течение одного окна передачи конкретным устройством. Так как все устройства сети считаются идентичными, то, очевидно, а = h{N)/N.

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

Пустые Начинается передача слоты бикона(ов). Она длится /в течение Ь слотов

: начало передачи бикона

Ьслотов-

i+b-1

-b слотов-

-h слотов-

— БлокУ-1 ----------Блок/ БлокУ+1 »

Рис. 3. - Разбиение окна передачи биконов на блоки слотов

Получено следующее основное рекуррентное соотношение модели:

й(л, п0 = £ £ А, {к, 0 + 22 {А, (к,«) + /г, (*, 0}И(п - к, п - / - Ь +1),

1=1 4=1 1=1 (=1

где и - соответственно вероятности успешной передачи бикона и

коллизии в текущем блоке J с заданными текущими значениями к (число станций, запланировавших начать передачу бикона в блоке У) и / (номер слота, в котором начинается передача бикона в блоке У); п - число устройств, которые запланировали

передачи своих биконов в блоках J, J + 1, и т. д.; w - текущий остаток окна передачи биконов, который начинается с 7-го блока и длится до конца текущего окна.

В первой сумме отражен тот факт, что вероятность успешной передачи бикона равна hs(k,i). Вторая сумма отражает переход к следующему блоку до тех пор, пока не будет достигнут конец окна передачи биконов. Процесс переходит к следующему блоку с вероятностью hs{k,i), если передача была успешной, и с вероятностью hL(k,i), если несколько станций запланировали передачу своих биконов в слоте i, т.е. была коллизия. Далее находятся вероятности hs(k,i) и hc(k,i) и приводятся результаты численного моделирования для различных количеств устройств в сети и размеров окна передачи биконов.

В разделе 4.4 построена аналитическая модель рассылки биконов по алгоритму с прослушиванием среды. Как и в предыдущей модели, в каждый момент ТВТТ все устройства сети соревнуются за передачу бикона в специальном окне передачи биконов, которое состоит из W слотов длиной а. Чтобы передать свой бикон, каждое устройство устанавливает начальное значение своего таймера равным случайному целому числу d, которое равновероятно выбирается из конкурентного окна, представляющего собой интервал [О, М - 1], причем М < W. Обратный отсчет таймера идет по алгоритму с прослушиванием среды.

Далее вводится следующее определение: виртуальный слот - это промежуток времени между последовательными отсчетами таймера передачи биконов. Процесс передачи биконов представлен последовательностью виртуальных слотов, которая начинается в каждый момент ТВТТ, см. рис. 4. Если в течение виртуального слота ни одно из устройств не начинает передачу бикона, то длина этого виртуального слота равна единице, т.е. одному слоту длиной а. Если ровно одно устройство начинает передачу бикона в начале виртуального слота, то длина ts этого виртуального слота равна времени передачи бикона плюс DIFS. В случае, если несколько устройств начинают передачи своих биконов в начале виртуального слота, происходит коллизия биконов и длина tL виртуального слота равна времени передачи бикона плюс EIFS.

12 3 4 5 6 7 8 9 1011 12 1314

Рис. 4. Последовательность виртуальных слотов

При рассмотрении последовательности виртуальных слотов в предположении, что длительности успешного и коллизионного виртуальных слотов кратны а, т.е. = /<т и /с = /с - целые числа, получено следующее выражение для /¡(¿V, М, IV):

Н(п,т,ю) = р(0,п,т)\{т > I & уу> 1)/г(/2,«г-1, п>-1) +

+ /г(1,л,/л){1 + 1(н'>?* & т> 1)Л(п — 1,т — 1, IV -'*)}+

+ ХрО',/1,т)[1(»у>г*&т> 1)й(п — 7,т — 1, IV —г*)1

где рЦ, п, т) - вероятность того, что ровно у из п теэЬ-устройств начнут передачу своего бикона в текущем виртуальном слоте. Слагаемые этой формулы соответствуют трем случаям: текущий виртуальный слот пуст; ровно одно тевЬ-устройство передает свой бикон в текущем виртуальном слоте; коллизия биконов, когда7 = {2,..., п} техН-устройств передают свои биконы в текущем виртуальном слоте. Рекурсия завершается, когда окно передачи биконов заканчивается или все М виртуальных слотов оказываются реализованными, в зависимости от того, какое из этих двух событий наступает первым.

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

Рис. 5. - вероятность успешной передачи бикона в бикон-интервале шезЬ-

устройством

На рис. 5 изображены вероятности а{Н) успешной передачи бикона выбранным гг^И-устройством за один бикон-интервал в зависимости от количества устройств в сети. Очевидно, что с ростом числа устройств в сети вероятность передать бикон успешно для каждого устройства падает. Однако кривая «без прослушивания» падает медленнее, и видно, что передача с прослушиванием среды показывает лучшие результаты в сетях с малым количеством устройств, в больших же сетях передача без прослушивания среды оказывается более выигрышной.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В данной диссертации разработан комплекс аналитических моделей для анализа механизмов синхронизации в беспроводных персональных и локальных сетях. В частности:

1. Предложен метод разрешения тупиковых ситуаций в одношаговых и многошаговых беспроводных персональных сетях стандартов IEEE 802.15.5 и WiMedia.

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

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] В.М. Вишневский, А.И. Ляхов, А.А. Сафонов. Исследование эффективности механизмов синхронизации в беспроводных персональных сетях со сложной структурой. // Информационные технологии и вычислительные системы, №3, 2008, с. 63-77.

[2] В.Вишневский, ДЛаконцев, А.Сафонов, С.Шпилев. Mesh-ссти. В ожидании стандарта IEEE 802.1 Is. // Электроника: Наука, Технологии, Бизнес, №3, 2008, с. 98-106

[3] В.Вишневский, ДЛаконцев, А.Сафонов, С.Шпилев. Mesh-сети стандарта IEEE 802.11s - технологии и реализация. // Первая миля (Приложение к журналу «Электроника: Наука, Технология, Бизнес»), №2-3, 2008, с. 26-31

[4] Vishnevsky V.M., Lyakhov A.I., Safonov А.А, Mo S.S., Gelman A.D. Study of Beaconing in Multi-Hop Wireless PAN with Distributed Control. // IEEE Trans, on Mobile Computing, V. 7, N 1, Jan 2008, p.l 13-126

[5] Alexander Safonov, Andrey Lyakhov, Evgeny Khorov. Channel Switch Time Distribution in ECMA-368 Networks. // Proc. of IEEE Int. Symposium on Personal, Indoor and Mobile Radio Communications, France, 2008

[6] Alexander Safonov, Andrey Lyakhov, Stanislav Sharov. Synchronization and Beaconing in IEEE 802.11s Mesh Networks. // Proc. Int. Workshop on Multiple Access Communications, Saint-Petersburg, 2008

[7] Александр Сафонов. Обзор вопросов синхронизации в сетях IEEE 802.11. // Труды Межд. конференции по проблемам управления, Москва, 2008, с. 279-280

[8] Александр Сафонов, Евгений Хоров. Распределение времени присоединения устройств к сети ECMA-368 (WiMedia). // Конференция «Информационные технологии и системы», Геленджик, 2008, с. 23-29

[9] Vladimir Vishnevsky, Andrey Lyakhov, Alexander Safonov, Sergey Shpilev. Beaconing for MDA support in IEEE 802.11s mesh networks. // Proc. of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Greece, 2007

[10] Vladimir Vishnevsky, Andrey Lyakhov, Alexander Safonov. New Aspect of Beaconing in IEEE 802.11s Mesh Networks. // Proc. of IEEE International Symposium on Computers and Communications, Portugal, 2007, p. 263-268

[И] C.IO. Шаров, А.А. Сафонов. Особенности передачи синхрокадров в mesh-сетях IEEE 802.11s. // Конференция «Информационные технологии и системы», Звенигород, 2007, с. 44-49

[12] В.М.Вишневский, А.И. Ляхов, А.А. Сафонов, М.Ю. Якимов. Распределенный МАС-уровень высокоскоростных беспроводных персональных сетей. // Труды Международной конференции по проблемам управления, Москва, 20-22 июня 2006 г., т.2, с. 148.

[13] S.S. Mo, A.D. Gelman, V.M. Vishnevsky, A.I. Lyakhov, A.A Safonov. Distributed Medium Access Control for High Data Rate Wireless Personal Area Networks. // Proc. of the 10th IEEE International Symposium on Consumer Electronics, St. Petersburg, 2006, p. 448-452

[14] V.M. Vishnevsky, A.I. Lyakhov, A.A Safonov, S.S. Mo, A.D. Gelman. Study of Beaconing in Multi-hop Distributed Control Wireless PAN. // Proc. of the 15th 1ST Mobile & Wireless Summit, Greece, 2006

[15] V.M. Vishnevsky, A.I. Lyakhov, A.A Safonov, S.S. Mo, A.D. Gelman. Beaconing in Distributed Control Wireless PAN: Problems and Solutions. // Proc. of IEEE Consumer Comm. and Networking Conference, USA, 2006

Тираж 100 экз. Отпечатано в ИППИ РАН г.Москва, Большой каретный пер. 19, стр.1 http://www.iitp.ru/

Введение

1. Синхронизация в беспроводных сетях

1. Задачи синхронизации

2. Синхронизация в беспроводных персональных сетях

3. Синхронизация в беспроводных локальных сетях

4. Анализ существующих методов исследования и постановка задач диссертации

2. Оценка эффективности методов синхронизации в беспроводных персональных сетях WiMedia

1. Проблемы существующего механима синхронизации

2. Математическая модель для одношаговой сети

3. Математическая модель для многошаговой сети

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

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

1. Оптимистичная модель

2. Общая модель

3. Консервативная модель

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

4. Анализ алгоритмов синхронизации в беспроводных сетях Wi-Fi Mesh

1. Возможные алгоритмы рассылки биконов в mesh-сетях IEEE 802.

2. Требования беспроводных локальных mesh-сетей к синхронизации

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

4. Анализ алгоритма рассылки биконов с прослушиванием среды

Беспроводные технологии вытесняют проводные повсюду, где могут обеспечить приемлемые скорость и качество связи. Они прочно вошли в жизнь многих предприятий и миллионов людей, потому что позволяют решать широкий круг задач: от организации персональных и локальных сетей до построения сетей масштаба региона. Массовое внедрение в современных ноутбуках, коммуникаторах и телефонах получили локальные сети стандарта IEEE 802.11 под торговой маркой Wi-Fi и персональные сети IEEE 802.15.1 под торговой маркой Bluetooth, предполагающие централизованное управление сетыо на канальном уровне устройством-координатором. В таких сетях под синхронизацией понимается в основном синхронизация внутренних часов устройств с часами координатора.

Координатор является самым уязвимым устройством сети, и выход его из строя делает работу всех остальных устройств в сети невозможной. В связи с этим в последние годы во всем мире наблюдается повышенный интерес к сетям с распределенным управлением сетью на канальном уровне. Например, в комитете IEEE по стандартам созданы группы 802.11s (Wi-Fi Mesh) и 802.15.5 (High Rate WPAN Mesh), разрабатывающие протоколы локальных и персональных mesh-сетей, а альянс ведущих телекоммуникационных компаний мира WiMedia разработал стандарт персональных сетей ЕСМА 368 для соединения, например, компьютера, монитора и периферийных устройств без проводов. Все эти стандарты предполагают распределенное управление на канальном уровне: все устройства равноправны и подчиняются одним и тем же правилам работы, благодаря чему сеть лучше масштабируется и поддерживает режим энергосбережения и мобильность устройств по сравнению с сетью с централизованным управлением. Кроме того, отсутствие координатора делает сеть надежнее: выход из сгроя одного или даже нескольких устройств оставляет возможность непрерывной работы оставшихся устройств без изменений настроек сети, что было бы невозможно в сети с централизованным управлением.

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

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

В данной работе под синхронизацией в сети понимается обмен между устройствами сети специальными синхрокадрами для координации их распределенной работы. Эти кадры, называемые бйконами (от англ. beacon, букв, «маячок»), являются контейнерами, в которые многие механизмы сети вкладывают свою сигнальную информацию, что избавляет их от необходимости рассылать свои собственные сигнальные кадры. Например, с помощью биконов устройства сигнализирует соседним устройствам, находящимся в режиме энергосбережения, о новых данных для этих устройств; вложив в бикон другой информационный элемент, устройства распределенным образом резервируют канал для передачи данных и поддерживают уже созданные резервирования.

Исследованию протоколов IEEE 802.11 [1] и WiMedia [2] и построенных на их базе беспроводных сетей посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: А.В. Винеля, В.М. Вишневского, Д.В. Лаконцева, А.И. Ляхова, Д.II. Мацнева, М.Ю. Якимова, G. Bianchi, F. Cali, М. Conti, Е. Gregory, G.R. Hiertz, Q. Ni, Y.Zang и др. Однако большая часть этих работ посвящена оценке производительности методов передачи данных, но не эффективности механизмов синхронизации. В работах же, посвященных оценке эффективности механизмов синхронизации в сетях IEEE 802.11, например, в работах L. Huang, Т. Lai, D. Zhou, под синхронизацией понимают исключительно синхронизацию внутренних часов станций, и при этом охватываются лишь сети IEEE 802.11 в режиме ad hoc, но не mesh-сети. В работах, посвященных оценке эффективности механизмов синхронизации в сетях WiMedia, например, в работах Q. Wu, Y. Xiong, Z. Guo, проводится оценка эффективности только отдельной процедуры сжатия бикои-периода без учета присоединения устройств к сети. Таким образом, не существует моделей, позволяющих проводить всесторонний анализ механизмов синхронизации в современных персональных и локальных беспроводных сетях с распределенным управлением, в то время как от эффективности этих механизмов напрямую зависит производительность сетей в целом.

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

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

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

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

1. Метод предотвращения тупиковых ситуаций при рассылке синхрокадров в беспроводных персональных сетях с распределенным управлением.

2. Аналитические модели процесса присоединения устройств к беспроводной персональной сети с распределенным управлением.

3. Аналитические модели различных механизмов синхронизации в беспроводных mesh-сетях стандарта IEEE 802.1 Is.

Научная новизна. Впервые разработаны математические модели для анализа эффективности механизмов рассылки синхрокадров устройствами в персональных и локальных беспроводных сетях с распределенным управлением стандартов Wi-Fi Mesh и WiMedia, позволяющие оценивать следующие вероятностные и временные показатели: средние значения и распределения времен присоединения устройства к сети и смены сетью канала; вероятность блокирования сети; вероятность успешной передачи синхрокадра.

Практическая ценность и реализация результатов. Результаты работы внедрены и используются на практике, а также в учебном процессе на базовой кафедре МФТИ (ГУ) в И1ШИ РАН «Проблемы передачи и обработки информации», что подтверждено соответствующими актами. В частности, предложенные и изученные механизмы синхронизации использованы при разработке технологии транспортных mesh-сетей в рамках Государственного контракта, выполняемого ИППИ РАН в 2007-2009 гг., № 02.524.11.4002 «Разработка интегрированной технологической платформы для мониторинга элементов и систем жизненно важной инфраструктуры на основе информационно-коммуникационных технологий - расширенного Интернета», а также при разработке НИР, проводимой ИППИ РАН, по программе Отделения нанотехнологий и информационных технологий РАН «Новые физические структурные решения в инфокоммуникациях».

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на: о Межд. конференциях по проблемам управления (Москва, 2006г. и 2008г.). о IEEE Consumer Communications and Networking Conference (USA, 2006r.). о 15th 1ST Mobile & Wireless Summit (Greece, 2006r.). о IEEE Int. Symposium on Consumer Electronics (С.-Пб., 2006r.). о Конференциях молодых ученых и специалистов "Информационные технологии и системы" (Звенигород, 2007г. и Геленджик, 2008г.). о IEEE Int. Symposium on Computers and Communications (Portugal, 2007r.). о IEEE Int. Symposium on Personal, Indoor and Mobile Radio Communications (Greece, 2007 и France, 2008). о Int. Workshop on Multiple Access Communications (С.-Пб., 2008г.). о Семинарах ИППИ РАН.

Публикации. По теме диссертации опубликовано 15 научных работ [3 - 17]. Из них 4 статьи опубликованы в рецензируемых научных журналах [3 - 6], 2 из которых утверждены в перечне ВАК. 11 работ [7 - 17] опубликованы в трудах ведущих международных и российских научно-технических конференций.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 42 наименования. Работа изложена на 110 страницах и содержит 37 рисунков и 2 таблицы.

Заключение

В данной диссертации разработан комплекс аналитических моделей для анализа механизмов синхронизации в беспроводных персональных и локальных сетях. В частности:

1. Предложен метод разрешения тупиковых ситуаций в одношаговых и многошаговых беспроводных персональных сетях стандартов IEEE 802.15.5 и WiMedia.

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

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

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

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

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

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

1. 1.EE Std 802.11-2007, Revision of IEEE Std 802.11-1999. "Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)" specification, June 2007

2. European Computer Manufactures Association. High Rate Ultra Wideband PHY and MAC Standard, Standard ECMA-368, December 2005

3. B.M. Вишневский, А.И. Ляхов, А.А. Сафонов. Исследование эффективности механизмов синхронизации в беспроводных персональных сетях со сложной структурой. // Информационные технологии и вычислительные системы, №3, 2008г., с. 63-77

4. В.Вишпевский, Д.Лаконцев, А.Сафонов, С.Шпилев. Mesh-cera. В ожидании стандарта IEEE 802.1 Is. // Электроника: Наука, Технологии, Бизнес, №3, 2008г., с. 98106

5. В.Вишневский, Д.Лаконцев, А.Сафонов, С.Шпилев. Mesh-cera стандарта IEEE 802.11s технологии и реализация. // Первая миля (Приложение к журналу «Электроника: Наука, Технология, Бизнес»), №2-3, 2008г., с. 26-31

6. Vishnevsky V.M., Lyakhov A.I., Safonov А.А, Mo S.S., Gelman A.D. Study of Beaconing in Multi-Hop Wireless PAN with Distributed Control. // IEEE Trans, on Mobile Computing, V. 7, N 1, Jan 2008, p.l 13-126

7. Alexander Safonov, Andrey Lyakhov, Evgeny Khorov. Channel Switch Time Distribution in ECMA-368 Networks. // Proc. of IEEE Int. Symposium on Personal, Indoor and Mobile Radio Communications, France, 2008

8. Alexander Safonov, Andrey Lyakhov, Stanislav Sharov. Synchronization and Beaconing in IEEE 802.11s Mesh Networks. // Proc. Int. Workshop on Multiple Access Communications, Saint-Petersburg, 2008

9. Александр Сафонов. Обзор вопросов синхронизации в сетях IEEE 802.11. // Труды Межд. конференции по проблемам управления, Москва, 2008, с. 279-280

10. Ю.Александр Сафонов, Евгений Хоров. Распределение времени присоединения устройств к сети ECMA-368 (WiMedia). // Конференция «Информационные технологии и системы», Геленджик, 2008, с. 23-29

11. I.Vladimir Vishnevsky, Andrey Lyakhov, Alexander Safonov, Sergey Shpilev. Beaconing for MDA support in IEEE 802.1 Is mesh networks. // Proc. of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Greece, 2007

12. Vladimir Vishnevsky, Andrey Lyakhov, Alexander Safonov. New Aspect of Bcaconing in IEEE 802.11s Mesh Networks. // Proc. of IEEE International Symposium on Computers and Communications, Portugal, 2007, p. 263-268

13. С.Ю. Шаров, А.А. Сафонов. Особенности передачи синхрокадров в mesh-сетях IEEE 802.11s. // Конференция «Информационные технологии и системы», Звенигород, 2007, с. 44-49

14. V.M. Vishnevsky, A.I. Lyakhov, A.A Safonov, S.S. Mo, A.D. Gelman. Study of Beaconing in Multi-hop Distributed Control Wireless PAN. // Proc. of the 15th 1ST Mobile & Wireless Summit, Greece, 2006

15. V.M. Vishnevsky, A.I. Lyakhov, A.A Safonov, S.S. Mo, A.D. Gelman. Beaconing in Distributed Control Wireless PAN: Problems and Solutions. // Proc. of IEEE Consumer Comm. and Networking Conference, USA, 2006

16. Вишневский B.M., Ляхов А.И., Сафонов A.A., Якимов М.Ю. Распределенный МАС-уровень высокоскоростных беспроводных персональных сетей. // Труды Международной конференции "Проблемы управления' 06", Москва, 2006г.

17. В.М. Вишневский, А.И. Ляхов, С. Л. Портной, И. Л. Шахпович. Широкополосные беспроводные сети передачи информации. М.: Техносфера, 2005г.

18. Института Инженеров Электротехники и Электроники (Institute of Electrical and Electronics Engineers, IEEE), официальный сайт: http://www.ieee.org

19. IEEE LAN/MAN Standardization Committee, официальный сайт: http://www.ieee802.org/

20. WiMedia Alliance, официальный сайт: http://www.wimedia.org

21. IEEE 802.15-03/276r0. CE-SIG (Panasonic/Philips/Samsung/Sharp/Sony), Consumer Electronic Requirements for TG3a, July 2003

22. Part 15.3: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for High Rates Wireless Personal Networks (WPANs). // IEEE Computer Society, 2003

23. Daily Digital Digest News, http://www.3dnews.ru/news/pervie12uwbreshcniipoluchilisertifikatwimediaallianc e/ 12 октября 2007г.

24. IEEE Std 802.11, 1999 Edition, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specification, August 1999

25. IEEE P802.11s/D1.0, Draft Amendment to Standard, ESS Mesh Networking, November 2006

26. IEEE P802.1 ls/D2.0, Draft Amendment to Standard, Mesh Networking, March 2008

27. G.R. Hiertz, Y. Zang, J. Habetha, H. Sirin. IEEE 802.15.3a Wireless Personal Area Networks The MBOA Approach. // Proc. of the 1 llh European Wireless Conference 2005, Vol. 1, p. 204 - 210, Nicosia, Cyprus, April 2005

28. Hiertz, G. and Zang, Y. and Habetha, J. and Sirin, H. Multiband OFDM Alliance -The next generation of Wireless Personal Area Networks. // Proc. of the 2005 IEEE Sarnoff Symposium, Princeton, New Jersey, USA

29. Q. Wu, Y. Xiong, H. Wu, Z. Guo, X.-G. Xia, Q. Zhang, and Z. Li. Performance Evaluation of the Beacon Period Contraction Algorithm in UWB MBOA MAC. // IEEE Communication Letters, Vol. 9, N. 10, p. 933-935, Oct. 2005

30. Yuan Zhang, Xiqi Gao, and Xiaohu You. Superframe Synchronization in Distributed ECMA-368 Wireless Personal Area Networks. // Submitted to IEEE Trans, on Mobile Computing before January 2008

31. Lamport. Time, clocks and the ordering of events in distributed systems. // Communications of the ACM, 21(7):558.565, 1978

32. L. Huang и Т. Lai. On the scalability of IEEE 802.11 ad hoc networks. // Proc. of ACM MobiHoc, 2002

33. D. Zhou, T. Lai. Analysis and Implementation of Scalable Clock Synchronization Protocols in IEEE 802.11 Ad Hoc Networks. // Proc. of MASS, 2004

34. D. Zhou, T. Lai. A Scalable and Adaptive Clock Synchronization Protocol in IEEE 802.11-Based Multihop Ad Hoc Networks. // Proc. of MASS 2005

35. Dong Zhou, Lifei Huang, and Ten H. Lai. On the scalability of IEEE 802.11 ad-hoc-mode timing synchronization function. // Wireless Networks, Vol. 14, N. 4, 2008

36. GPSS: имитационное моделирование систем, http://www.gpss.ru/

37. Network Simulator 2, http://isi.edu/nsnam/ns/

38. G. Bianchi. Performance Analysis of the IEEE 802.11 Distributed Coordination Function. // IEEE Journal on Selected Areas in Communications, Vol. 18, p. 535-547, March 2000.

39. F. Call, M. Conti, and E. Gregory. Dynamic Tuning of the IEEE 802.11 Protocol to Achieve a Theoretical Throughput Limit. // IEEE/ACM Trans, on Networking, Vol. 8, p. 785-799, December 2000