Содержание к диссертации
Введение
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.11
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] и построенных на их базе беспроводных сетей посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: A.B. Винеля, В.М. Вишневского, Д.В. Лаконцева, А.И. Ляхова, Д.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, проводится оценка эффективности только отдельной процедуры сжатия бикон-периода без учета присоединения устройств к сети. Таким образом, не существует моделей, позволяющих проводить всесторонний анализ механизмов синхронизации в современных персональных и локальных беспроводных сетях с распределенным управлением, в то время как от эффективности этих механизмов напрямую зависит производительность сетей в целом.
В связи с этим необходима разработка адекватных математических моделей для анализа эффективности существующих методов синхронизации в персональных и локальных беспроводных сетях, что позволит настраивать механизмы синхронизации так, чтобы они удовлетворяли требованиям других механизмов в этих сетях.
Целью диссертационной работы является разработка аналитических моделей для сравнительного анализа эффективности различных механизмов синхронизации в персональных и локальных беспроводных сетях с распределенным управлением.
Методы исследования. Для достижения поставленной цели в диссертационной работе используются методы теории вероятности, теории случайных процессов и комбинаторного анализа.
Основные положения, выносимые на защиту:
Метод предотвращения тупиковых ситуаций при рассылке синхрокадров в беспроводных персональных сетях с распределенным управлением.
Аналитические модели процесса присоединения устройств к беспроводной персональной сети с распределенным управлением.
Аналитические модели различных механизмов синхронизации в беспроводных 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 таблицы.
Синхронизация в беспроводных персональных сетях
Технологии беспроводной передачи данных сегодня прочно вошли в жизнь миллионов людей. Вряд ли кто-то сомневается, что бурное развитие и внедрение этих технологий продолжится - настолько удобен мир без проводов. Низкая стоимость, быстрота развертывания, широкие функциональные возможности по передаче данных, IP-телефонии, видеопотоков - все это делает беспроводные технологии одним из самых быстрорастущих телекоммуникационных направлений [18].
Одним из важнейших аспектов, определяющих успех современных сетей передачи информации, является их стандартизация. Стандартизация необходима всем: от производителей электронных компонентов и изготовителей аппаратуры до телекоммуникационных сервис-провайдеров и конечных пользователей, потому что означает массовость производства, и, в конечном счете, ведет к низким ценам и, значит, широкому распространению технологии. В области телекоммуникаций законодателем мировой моды является Институт инженеров по электротехнике и электронике - IEEE (Institute of Electrical and Electronics Engineers) [19]. Институт IEEE выполняет множество проектов по разработке стандартов во всех областях телекоммуникаций, среди которых особого внимания заслуживает проект IEEE 802 [20]. Он был всего лишь очередным по номеру проектом в череде других, запущенных IEEE, но оказался чрезвычайно успешным, и сегодня именно в его рамках разрабатываются и дорабатываются стандарты беспроводных сетей любых масштабов: от персональных до региональных. В частности, в рамках этого проекта оформились в виде стандартов такие технологии, как Ethernet, Token Ring, Wi-Fi, Bluetooth, WiMAX и др.
Построением региональных и городских сетей занимаются исключительно профессиональные операторы связи. Устройства же для построения локальных и персональных сетей дешевы и, следовательно, доступны широкому кругу потребителей, что позволяет использовать их в домашних и офисных приложениях. Самыми известными стандартами беспроводных персональных и локальных сетей являются IEEE 802.15.1, распространенный под маркой Bluetooth, и IEEE 802.11 в так называемом режиме hot spot, известный под маркой Wi-Fi, получившие массовое внедрение в современных ноутбуках, коммуникаторах и телефонах. Сети на основе этих технологий предполагают централизованное управление, когда все решения принимаются устройством-координатором. Чтобы довести команды (например, переключиться на другую рабочую частоту, зарезервировать капал для передачи данных конкретным устройством и т. д.) до других устройств в сети, координатор регулярно рассылает специальные синхронизирующие кадры.
В русскоязычной литературе беспроводным сетям уделяется немало внимания, однако практически все работы посвящены оценке производительности методов предачи данных, но не эффективности механизмов синхронизации, и поэтому общепринятого удобного названия таких специальных кадров еще не сложилось. В [17] их называют «сигнальными кадрами» или «кадрами синхронизации», что отражает назначение этих кадров отчасти, но звучит громоздко. В работах [3 - 5] используется более короткий термин "бикон", который по звучанию совпадает с английским термином «beacon» (буквально «сигнальный огонь», «маячок»), принятым в стандартах IEEE. В данной работе для обозначения синхронизирующих кадров также используется удобный в употреблении термин "бикон".
Важнейшей частью бикона является временная метка Timestamp, в которую координатор перед отправкой бикона копирует значение своих внутренних часов, чтобы другие устройства сети могли синхронизировать свои внутренние часы с часами устройства-координатора. Таким образом, в сетях с централизованным управлением механизм рассылки биконов напрямую связан с механизмом синхронизации часов устройств, и названия этих механизмов часто употребляются взаимозаменяемо. Однако, как показано далее, в сетях с распределенным управлением механизмы синхронизации выполняют гораздо больше функций, чем синхронизация часов устройств, а термин «синхронизация» понимается шире.
В сетях с централизованным управлением координатор является самым уязвимым устройством сети, и выход его из строя делает работу всех остальных устройств в сети невозможной или требует их переконфигурации специалистом. В то же время для дальнейшего распространения беспроводных технологий в домашних приложениях необходимо обеспечить бесперебойную работу сетей и минимизировать необходимость их технического обслуживания. Поэтому многие компании прогнозируют рост популярности сетей с распределенным управлением в ближайшем будущем. В рамках проекта IEEE 802 созданы отдельные группы 802.11s (Wi-Fi Mesh) и 802.15.5 (High Rate WPAN Mesh), разрабатывающие стандарты локальных и персональных mesh-сетей с распределенным управлением [20], а альянс WiMedia [21] ведущих телекоммуникационных компаний мира разработал стандарт высокоскоростных персональных сетей ЕСМА 368 для соединения, например, компьютера, монитора и периферийных устройств без проводов. Во всех этих сетях координатор как особо выделенное устройство со специальной функциональностью отсутствует. Вместо этого все устройства обязательно поддерживают определенный набор функций, который позволяет продолжить работу сети, если одно или даже несколько устройств выходят из строя. Распределенное управление позволяет сети лучше реагировать на такие события, как расширение сети и движение устройств, а также лучше поддерживать режим сохранения энергии по сравнению с сетью с централизованным управлением.
В сети с распределенным управлением необходимо координировать работу устройств для согласованного принятия решений и работы многих механизмов физического и канального уровня. Во введении уже приводился пример сетей WiMedia, в которых механизмы синхронизации обеспечивают согласованное принятие решений устройствами практически во всех возможных случаях: от простого резервирования канала до объединения нескольких сетей в одну.
Синхронизация работы устройств в сетях с распределенным управлением достигается посредством постоянного обмена биконами, в рассылке которых принимают участие все устройства. Эти кадры являются контейнерами, в которые другие механизмы сети, например, механизмы энергосбережения и резервирования канала, вкладывают свою служебную информацию. Поэтому без надежной рассылки биконов невозможна работа других механизмов, скажем, нельзя зарезервировать канал. Иными словами, в сетях с распределенным управлением механизмы синхронизации сложнее, чем в сетях с централизованным управлением, так как ряд других механизмов сети полагаются на рассылку биконов как на надежный способ доставки своей сигнальной информации.
В стандартах беспроводных сетей с распределенным управлением, под механизмом синхронизации в сети понимается механизм рассылки биконов. В связи с чрезвычайной важностью биконов для их передачи применяется модуляция и кодирование, обеспечивающие максимальную надежность и, соответственно, самую низкую скорость. В данной работе при анализе механизмов синхронизации в различных сетях предполагается, что помехоустойчивое кодирование надежно защищает передачу биконов от помех, и неудачной передача бикона может быть лишь из-за коллизии, когда два устройства передают одновременно.
Синхронизация в беспроводных локальных сетях
В данном разделе рассматриваются высокоскоростные беспроводные персональные сети - пикосети, в которых «область слышимости» устройств не превышает нескольких метров. Такие сети могут использоваться для организации рабочего места, соединяя компьютер, монитор и периферийные устройства. Другое возможное применение пикосетей - беспроводная связь между DVD-плеером, монитором и элементами акустической системы домашнего кинотеатра. Мобильные телефоны, смартфоны, видеокамеры и фотоаппараты, флеш-карты, МРЗ-плееры - все эти и многие другие устройства могут быть объединены в беспроводную пикосеть для высокоскоростного обмена данными, видео- и аудио-потоками. Скорость передачи данных, поддержка мобильности устройств, низкое потребление энергии, быстрое подключение устройств к сети — основные требования к таким персональным сетям [22].
Первый стандарт высокоскоростных беспроводных персональных сетей был опубликован в рамках проекта IEEE 802 в 2003 году. Этот стандарт, названный IEEE 802.15.3 [23], включает в себя описание физического (PHY) и канального (MAC) уровня персональных сетей. Оп определяет протокол создания и функционирования сетей, работающих на скоростях 11, 22, 33, 44 и 55 Мбит в секунду. Для современных мультимедийных приложений таких скоростей недостаточно.
Технология сверхширокополосной передачи (UWB) является современной технологией физического уровня, которая может быть использована в высокоскоростных персональных сетях. Во-первых, эту технологию отличает чрезвычайно широкий спектр передачи сигналов (до ЮГГц), обеспечивающий высокую скорость передачи данных (нескольких сотен мегабит в секунду) на расстоянии 4-5 метров; а во-вторых, поскольку эта технология характеризуется малым потреблением энергии, она идеально подходит для портативных устройств. К сожалению, протокол MAC-уровня для построения сетей на основе UWB, принятый IEEE, до сих пор не появился.
Однако, в 2005 году альянс более чем 170-ти крупнейших телекоммуникационных компаний мира — WiMedia Alliance [21] — разработал протокол МАС-уровня персональных сетей с распределенным управлением, названный ЕСМЛ 368 [2]. «USB без проводов» (Wireless USB) - одно из первых приложений, ориентированных на стандарт WiMedia, которое появится на рынке уже в ближайшее время. Так в 2007г. 12 компаний получили сертификацию WiMedia UWB и продемонстрировали свои устройства [24].
Позднее в комитете по стандартам IEEE была образована группа 802.15.5, которая разрабатывает рекомендации построения беспроводных персональных mesh- сетей, во многом заимствуя идеи ЕСМА 368, в том числе и распределенный механизм синхронизации устройств. На момент написания диссертации стандарт 802.15.5 далек от завершения, поэтому в данной диссертации в качестве примера беспроводных персональных сетей исследуются сети стандарта ЕСМА 368 (WiMedia). Названия ЕСМА 368 и WiMedia используются в литературе в равной степени часто. В данной работе преимущественно используется название WiMedia.
В сети WiMedia каждое устройство регулярно посылает свой бикон и «слушает» биконы других устройств, чтобы зафиксировать их присутствие и передачу данных в сети, а также получить информацию о сети с точки зрения соседних устройств. Пример топологии сети приведен на рис. 1, где цифрами показаны положения устройств, а кругами - соответствующие им области уверенного радиоприема («слышимости») устройства в центре круга. Если соседнее устройство находится в области слышимости, кадры этого устройства могут быть получены без ошибок. Эту область также называют ТХ-областью (от англ. transmit — передавать). В примере на рис. 1 устройства 2, 3, 4 и 6 находятся в ТХ-области устройства 1, в то время как кадры устройства 2 могут приниматься только устройствами 1 и 3.
Область, в которой устройство «слышит», что соседнее устройство передает кадр, но не может декодировать кадр без ошибок из-за того, что сигнал слишком слаб, называют зоной интерференции, или CS-областью (от англ. carrier sense — контроль несущей). Радиус этой области зависит от многих параметров и, как правило, по- крайней мере, в два раза больше радиуса ТХ-области. Суперкадр т-1 Суперкадр т Суперкадр т+1 Бикон- период Интервал передачи данных Рисунок 2. Структура суперкадра пикосети стандарта WiMedia
Базовой временной единицей пикосети WiMedia является суперкадр, который разделен на временные слоты. Структура суперкадра показана на рис. 2. Чтобы избежать фрагментации суперкадра, биконы всех устройств сгруппированы в его начале — во временном интервале, который называют бикон-периодом. Благодаря алгоритму синхронизации часов все устройства пользуются единым временем, нуль которого привязан к началу бикон-периода и обозначается моментом времени BPST (Beacon Period Start Time).
За бикон-периодом следует интервал времени, в котором устройства передают данные. Этот интервал разделен па части, в которых устройства получают доступ к среде на соревновательной основе или по предварительному резервированию с помощью биконов: соответственно интервалы РСА (Prioritized Contention Access) и
DRP (Distributed Reservation Protocol). В интервале PC А устройства могут передавать данные, получая доступ к каналу методом множественного доступа с детектированием несущей и предотвращением коллизий (Carrier Sense Multiple Access with Collision Avoidance. CSMA/CA). В каждом слоте интервала DRP только одна пара приемник-передатчик получает доступ к каналу, что обеспечивает передачу без коллизий. Бес коллизионная передача необходима для поддержки мультимедийных приложений, изохронный трафик которых чрезвычайно чувствителен к задержке и ее вариации. Для резервирования слотов в интервале DRP устройства включают специальные информационные элементы в свои биконы. Таким образом, в сетях WiMedia передача мультимедийных данных начинается с успешной передачи б и конов.
Проблемы существующего механима синхронизации
В сети ЕСМА-368 (\\ МесНа) устройства передают свои биконы каждый суперкадр. Бикои каждого устройства занимает отдельный бикон-слот, который должен быть незанятым как с точки зрения самого передающего устройства, так и с точки зрения соседей этого устройства, т.е. других устройств, которые могут получать кадры передающего устройства. Нарушение этого правила, т.е. передача нескольких биконов в одном слоте, приводит к коллизии. В результате ни один из биконов не может быть корректно принят другими устройствами.
Как уже упоминалось выше, чтобы устройство А могло получать кадры от устройства В напрямую, устройство В должно находится в ТХ-области устройства А. Однако устройства могут находится достаточно далеко друг от друга, и тогда передача кадра от А к В возможна только через промежуточные устройства, но не непосредственно. Назовем непосредственную пересылку кадра между устройствами шагом. Тогда сеть называется п-шаговой, если минимальное число шагов, необходимых для передачи кадра между самыми удаленными друг от друга устройствами в сети, равно п.
В общем случае «-шаговой сети устройство А может занимать тот же самый бикон-слот, что и устройство В, если В находится за пределами СБ-области устройства А и его соседей. В примере на рис. 1 устройство 5 находится в трех шагах от устройств 2, 3 и 4 и может использовать с одним из них один и тот же слог. Однако если устройства 2-4 находятся в СБ-области устройства 6, с которым устройство 5 общается непосредственно, и устройство 5 находится в СБ-области устройства 1, с которым устройства 2-4 общается непосредственно, то устройство 5 не может занимать тот же слот, что и устройства 2-4, потому что устройство 6 пометит бикон- слоты устройств 2-4 как занятые для устройства 5, а устройство 1 пометит бикон-слот устройства 5 как занятый для устройств 2-4.
Так как размер пикосети обычно невелик, в данной работе полагается, что для любого устройства X все остальные устройства находятся в пределах СБ-области либо самого устройства X, либо его соседей. В этом случае, любой бикон-слот может содержать только один бикон, как показано на рис. 3.
При присоединении устройств к сети, а также при разрешении коллизий, используется случайный выбор слотов, который может приводить к серьезным проблемам в случае присоединения к сети нескольких устройств в одном и том же или последовательных суперкадрах, что случается, например, при интерференции нескольких пикосетей. Различные пикосети могут оказаться в зоне взаимной слышимости из-за движения устройств, а также как следствие эффекта открывания/закрывания двери. В этом случае либо пикосети объединяются, либо одна из пикосетей меняет канал. Когда одно из устройств инициирует переключение на другой канал, оно посылает специальное кадр-объявление. Получив такой кадр остальные устройства переключаются на новый канал вслед за первым устройством в одном из последующих суперкадров.
Первая проблема - это блокирование пикосети. Введем определение: Определение 1 Блокирование пикосети - это ситуация, когда в течение некоторого времени устройства не могут присоединиться к пикосети или разрешить коллизию.
Пикосеть может оказаться заблокированной в следующей ситуации. Когда одно из устройств занимает слот с номером МахВР, т.е. самый старший слот в бикоп- периоде, бикон-период считается заполненным; следовательно, другие устройства не могут присоединиться к пикосети или выбрать новый слот, разрешая коллизию, пока самый старший слот не будет освобожден. Пример сценария, когда сеть оказывается заблокированной, приведен на рис. 5.
На рис. 5 устройства В и С присоединяются к пикосети в суперкадре S и попадают в один и тот же бикон-слот N МахВР (рис. 5, (а)). Устройство А присоединяется к пикосети в суперкадре S + к (0 к U) и занимает самый старший бикон-слот МахВР (рис. 5, (Ь)). В следующих суперкадрах S + 1,...,S + U устройства В и С получают биконы других устройств, сигнализирующие о коллизии в их бикон- слоте. Поэтому в суперкадре S + к +1 устройства В и С должны разрешить коллизию, выбрав новый бикон-слот среди незанятых после последнего занятого бикоп-слота HOBS. Однако они не могут этого сделать, потому что HOBS - это самый старший слот МахВР. Устройства, которые не могут разрешить коллизию, вынуждены покинуть сеть и ждать, пока самый старший бикон-слот не будет освобожден (рис. 5, (с)). (а) суперкадр 8
Чтобы разрешить коллизию, устройства В и С выбирают единственный свободный бикон-слот после HOBS - самый старший слот, снова попадая в коллизию (рис. 6, (с)). Так как слот устройства А теперь не последний занятый, А не может сдвинуть свой бикон в младший слот. Устройства В и С не могут разрешить коллизию и вынуждены временно покинуть пикосеть (рис. 6, (d)). В следующем суперкадре устройства В и С обнаружат, что в пикосети есть свободный слот - самый старший слот — и попытаются присоединиться к сети, попав в коллизию снова (рис. 6, (е)). Пока устройства В и С повторяют цепочку присоединение —» коллизия — отсоединение — присоединение —»..., самый старший бикон-слот не оказывается свободным U суперкадров подряд, и устройство А не может сдвинуть свой бикон в младший бикон-слот. Таким образом, сеть зависает — оказывается заблокированной навсегда.
Для решения проблемы зависания пикосети введем дополнительную задержку W между отсоединением устройств В и С от сети и повторной попыткой их присоединения. Цель введения этой задержки — дать устройству А достаточно времени, чтобы сдвинуть свой бикон в младший слот и уменьшить тем самым вероятность попадания устройств В и С в коллизию при повторном присоединении к сети. Сформулируем алгоритм WBR (Wait Before Rejoin — подождать перед повторным присоединением).
Алгоритм WBR. Устройства, которые не могут разрешить коллизию, должны: 1) перестать посылать биконы; 2) сканировать весь бикон-период W WQ=U + 2 суперкадров; 3) попытаться присоединиться к пикосети через Ж суперкадров.
В одношаговой сети в большинстве случаев, выполнив алгоритм WBR с W = W0, устройства присоединятся к пикосети успешно, так как старшие бикон-слоты освобождены. Однако в многошаговой пикосети задержки W0 может оказаться недостаточно. Этот случай подробно разобран в разделе 2.3.
Вероятность успешного или неуспешного присоединения к сети, а также время, необходимое для присоединения, зависит от размер окна EW. Если окно слишком коротко, то устройства с большой вероятностью попадают в коллизии, которые, возможно, повторяются; время присоединения к сети увеличивается, а пространство свободных бикон-слотов быстро сокращается, так как каждая коллизия сдвигает HOBS все ближе к МахВР, что увеличивает вероятность блокирования сети. Если же окно EW слишком длинно, то вероятность блокирования сети также резко возрастает, так как уже после первой коллизии слот МахВР может оказаться внутри окна EW. Как описано в разделе 2.3, влияние размера окна EW на успешность выбора бикон- слота в случае многошаговой сети резко увеличивается.
Для исследования влияния временного блокирования сети на качество работы сети, а также в поисках способов уменьшения этого влияния, в данной работе с помощью методов комбинаторного анализа построена математическая модель, изложенная в разделах 2.2 и 2.3 соответственно для случаев одношаговой и многошаговой сети. В модели размер окна EW, который имеет определяющее значение в схеме выбора бикон-слота, описан функцией R(M) общего вида, где М — количество свободных бикон-слотов, доступных для присоединения. В стандарте используется частный случай функции R(M), когда R(M) = R(M)„щд = min (D, М = МахВР — HOBS), где D — константа. В разделе 2.4 приведены численные результаты моделирования и, кроме функции R(M)Cтанд, рассмотрена альтернативная функция, предложенная автором.
Оптимистичная модель
В течение этих W суперкадров устройство В успевает переместить свой бикон в более младший слот, если таковой имеется (см. рис. (g)), изменив тем самым количество бикон-слотов, доступных для присоединения устройств Г и Ж. Очевидно, начиная с этого суперкадра, т.е. с суперкадра S = 2U+W+4+\, оптимистичная модель описывает процесс присоединения устройств, изображенный на рис. 16, с ошибкой, так как она не учитывает ни вероятности коллизии после сжатия бикон-периода, ни изменения количества бикон-слотов, доступных для присоединения устройств Г и Ж после сжатия.
Для того чтобы учесть сжатие бикон-периода и описать процесс присоединения устройств к сети точно в общем случае, необходимо ввести в определение состояния (2.4) случайного процесса J = {j,,t - 0,1,...}, введенного в разделе 2.2, дополнительные компоненты, описывающие процесс сжатия бикон-периода.
Для описания процесса сжатия бикон-периода удобно ввести вектор L(t). Нулевая компонента 10 этого вектора равна HOBS минут номер последнего успешно занятого слота. Она показывает, насколько увеличится количество слотов m(t), доступных для присоединения устройств к сети, когда устройства, находящиеся в коллизии перестанут посылать свои биконы, выполняя алгоритм WBR. Что касается остальных компонент, то i-я компонента вектора L принимает значение, равное количеству слотов, освобождающихся при i-м сжатии бикон-периода, если при этом не происходит присоединения/отсоединения устройств к сети.
Каждый раз, когда к сети присоединяются новые устройства или устройства покидают сеть, значения компонент вектора L меняются, так как происходит переход к следующему моменту времени процесса J. Количество компонент вектора L равно К+1, а количество ненулевых компонент является переменной величиной и ограничено количеством устройств, которые уже присоединились.
Для пояснения смысла компонент вектора L , рассмотрим ситуацию, когда с устройств в коллизиях перестали посылать свои биконы, выполняя алгоритм WBR, и затем произошло сжатие бикон-периода. Количество слотов, доступных для присоединения этих (/+1) = с устройств в следующий момент модельного времени f+1, равно m(/+l) = l0(t) + //(/), причем, очевидно. lo(t+1) = 0, а остальные компоненты сдвигаются: /,./( +1) = /,{/) для 1 i К, lK{t+1) = 0. Если в момент времени t+] хотя бы одно устройство присоединяется успешно, то компоненты вектора I пересчитываются.
Если к моменту времени t + xj, X/ 1, все эти с устройств по-прежнему оказываются в коллизиях и вновь занят самый старший б и кон-слот МахВР. то эти с устройств вновь перестают посылать биконы, происходит второе сжатие бикон- периода. и процесс J переходит к следующему моменту времени i+T/+l, когда с устройств выбирают слоты заново. При этом количество слотов ш(г+Г/+1), доступных для присоединения этих /:(/+т;+1) = с устройств, равно l t+xj) + lj(t+Tj) = ld.t)+ i;(t) + l2(t), и происходит дальнейший сдвиг компонент вектора 1.
Как и после первого сжатия, если хотя бы одно устройство присоединяется успешно, то компоненты вектора L пересчитываются. Если же моменту времени t + i , т2 1- все эти с устройств вновь оказываются в коллизиях и вновь занят самый старший бикон-слот МахВР, то происходит третье сжатие бикон-периода и так дат ее, пока все возможные сжатия бикон-периода не произойдут (их количество ограничено количеством устройств, которые уже присоединились успешно). А 3 д Е И Б В г.Ж /о Рисунок 17 - Вектор L описывает сжатие бикон-периода Рис. 17 поясняет смысл компонент вектора I . Вернемся к суперкадру Б = 2/+1+4, когда устройства Г и Ж попадают в коллизию (см. рис. 16 (0). Нулевая компонента /д = 3 показывает количество слотов, которые освободятся в суперкадре Б = 2и+И/+4+/+1. когда устройства Г и Ж, находящиеся в коллизии, выполняя алгоритм WBR, перестанут посылать свои биконы. Компонента 1; = 2 показывает, что после сжатия бикон-периода за счет перемещения своего бикона устройством В освободится ровно 2 слота. Если устройства Г и Ж. присоединяясь к сети через Ж суперкадров, попадут в коллизию и займут самый старший бикон-слот МахВР опять. они снова перестанут посылать биконы на W суперкадров, в течение которых произойдет второе сжатие бикон-периода за счет перемещения бикона устройством Б. Это сжатие высвободит дополнительный бикон-слот (/?= 1). В случае третьей подряд коллизии устройств Г и Ж в последнем возможном бикон-слоте МахВР произойдет еще одно сжатие бикон-периода за счет перемещения своего бикона устройством И, которое высвободит 13 = 2 бикон-слота. После этого бикон-период становится сформированным, и процесс присоединения устройств Г и Ж к сети не усложняется более процессом сжатия бикон-периода.
Итак, для описания процесса присоединения устройств к сети с учетом сжатий бикон-периода необходимо переопределить процесс J, добавив в определение состояния процесса вектор L : jt={m(t),k(t),L} где L = {/0, /,,..., (3.8)
Новые компоненты состояния процесса J делают его описание очень громоздким. Количество элементов в пространстве {m(t),k(t),L} чрезвычайно велико, и, к сожалению, выполнение всех необходимых вычислений на современном персональном компьютере требует очень большого количества времени. В то же время вероятность нескольких сжатий бикон-периода без присоединения хотя бы одного устройства невелика.
Таким образом, представляется разумным ограничить точность модели, а вместе с ней и объем необходимых вычислений, пересчитывая лишь первые две компоненты вектора L. При этом оказывается возможным найти не только оценку снизу функций распределений Qi(T) и Q iJ), введя оптимистичное предположение, как в разделе 3.1, но и оценку сверху функций распределений 0/(7) и QjiJ), доопределив неизвестные компоненты вектора L минимально возможными значениями. Доопределение именно минимальными значениями занижает количество свободных слотов после HOBS в следующий момент времени и, следовательно, занижает вероятность того, что хотя бы некоторые из устройств в коллизиях успешно разрешат коллизии и присоединятся. При этом время присоединения к сети как одного устройства, так и всех устройств, оценивается сверху.
