Способ надежной рассылки синхрокадров (биконов) в беспроводной локальной mesh-сети

Способ надежной рассылки синхрокадров (биконов) в беспроводной локальной mesh-сети

Реферат

Область изобретения

Основные сведения о роли синхрокадров (биконов) и способе их рассылки в беспроводных локальных mesh-сетях

Беспроводная mesh-сеть - это сеть станций, в которой поддерживается автоматическое распознавание топологии и динамическое построение маршрутов. Назовем непосредственную пересылку пакета между станциями шагом. Тогда сеть называется n-шаговой, если минимальное число шагов, необходимых для передачи кадра между самыми удаленными друг от друга устройствами в сети, равно n. Также введем понятие h-шаговой окрестности станции сети как множества других станций, находящихся не более чем в h шагах от данной станции.

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

Наиболее распространенной на сегодняшний день спецификацией беспроводных локальных mesh-сетей является спецификация IEEE 802.11s [l]. Сети, технологию которых она описывает, называют Wi-Fi Mesh.

В сетях Wi-Fi Mesh, как и во многих других сетях с распределенным управлением, необходимо координировать работу станций для согласованного принятия решений и работы многих механизмов физического и канального уровня. Для координации своей работы станции регулярно обмениваются специальными пакетами, которые в русскоязычной литературе называют синхрокадрами [2] или биконами [3] (англ. beacon - «маячок»). В рассылке биконов принимают участие все станции mesh-сети, информируя друг друга о поддерживаемых сервисах и режимах работы. Кроме того, многие механизмы сети, например механизмы энергосбережения и резервирования канала, включают в биконы свою служебную информацию - так называемые информационные элементы. Обмениваясь биконами, станции обмениваются и информационными элементами, включенными в них. Поэтому биконы являются контейнерами для информационных элементов многих механизмов сети, и работа этих механизмов невозможна без надежной регулярной рассылки биконов каждой станцией сети Wi-Fi Mesh.

Основные сведения о способе рассылки биконов в беспроводных mesh-сетях

В сетях Wi-Fi Mesh для доступа к каналу используется механизм, основанный на методе множественного доступа с детектированием несущей и предотвращением коллизий (Carrier Sense Multiple Access with Collision Avoidance, CSMA/CA). Детектирование несущей частоты означает, что каждая станция сети прослушивает канал (среду). Если он занят, т.е. другая станция передает данные, то станция ждет, пока канал освободится. Для предотвращения коллизий (одновременной передачи несколькими станциями в радиусе слышимости друг друга), а точнее для снижения их вероятности, прежде чем передавать данные в освободившуюся среду, станция откладывает передачу на некоторое время. Для этого она случайным образом выбирает целое число временных слотов σ из некоторого временного промежутка и инициализирует счетчик отсрочки. Далее, если среда оказывается свободной в течение временного слота σ, то значение счетчика уменьшается на единицу. Если другая станция начинает передачу, то значение счетчика замораживается на время передачи плюс интервал времени, который называется Distribution Interframe Space (DIFS), если передача была успешной, или интервал времени Extended Interframe Space (EIFS), если при передаче случилась коллизия. Численное значение констант DIFS и EIFS определяются спецификацией [4]. Когда значение счетчика оказывается равным нулю, станция начинает передачу данных.

Время работы станций сети Wi-Fi Mesh делится на так называемые бикон-интервалы. Момент времени, обозначающий начало каждого бикон-интервала, называется планируемым временем отправки бикона (Target Beacon Transmission Time, TBTT). В каждый момент ТВТТ mesh-станция планирует передачу своего бикона. Как описано выше, для того чтобы получить доступ к среде, станция прослушивает среду в ожидании. Если в момент времени ТВТТ, когда станция запланировала начало передачи своего бикона, среда оказалась занята, эта станция откладывает передачу бикона. Станция начинает передачу запланированного бикона по истечении интервала времени Point Interframe Space (PIFS) после того, как среда освободится. Значение константы PIFS также определено спецификацией IEEE 802.11 [4], причем так, что PIFS<DIFS<EIFS.

Обозначим произвольно выбранную mesh-станцию как станцию X, и другую произвольно выбранную mesh-станцию как станцию Y. Поскольку интервал PIFS короче интервала DIFS, mesh-станция X, планирующая передать бикон, получает доступ к среде раньше, чем станция Y, планирующая передавать кадры данных или иные кадры, отличные от биконов и являющаяся соседней для станции X, т.е. воспринимающая занятость канала одинаково с ней. Поэтому описанный способ рассылки биконов обеспечивает более низкую вероятность их коллизии с кадрами данных и другими управляющими кадрами, чем вероятность коллизии кадров данных и других управляющих кадров между собой.

Для дальнейшего повышения надежности передачи биконов (защиты биконов) в сети Wi-Fi Mesh необходимо предотвращать коллизии между самими биконами, причем как для соседних устройств, так и устройств, находящихся в 2-х шагах друг от друга (т.е. не являющихся непосредственными соседями, но имеющими общих соседей). Известен способ разрешения коллизий биконов, раскрытый в патенте (publication number CN 101155101 (A), publication date 2008-04-02, application number CN 20061159674 20060930, Inventors: NA SHAN [CN]; KAI YANG [CN], Applicant: HUAWEI TECH CO LTD [CN]) и описанный в спецификации IEEE 802.11s [1] под названием Mesh Beacon Collision Avoidance (МВСА). Он состоит из двух компонентов: обмена mesh-станциями специальными информационными элементами Beacon Timing Element и алгоритма выбора нового значения ТВТТ, который выполняет каждая из mesh-станций в случае необходимости.

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

Каждая mesh-станция включает эту информацию, относящуюся к своим непосредственным соседям, в свой бикон в виде информационного элемента Beacon Timing Element для того, чтобы, во-первых, сообщить своим соседним станциям об успешном получении их биконов и, во-вторых, снабдить станции, только что присоединившиеся к сети, картой расположения биконов с тем, чтобы эти станции могли выбрать свой ТВТТ так, чтобы их биконы не пересекались во времени с биконами других устройств. Если в биконе, полученном от станции X, отсутствует бикон, переданный станцией Y, то последняя может сделать вывод, что ее бикон попал в коллизию. Если коллизии бикона Y по информации одного или нескольких соседей станции Y повторяются, эта станция может принять решение изменить свой ТВТТ, чтобы избежать коллизий своего бикона в будущем.

Однако рассылки информации о времени начала и периодичности передачи биконов соседей недостаточно для исключения коллизий биконов, так как требуется еще знать длительность передачи бикона, которая для каждой станции может меняться от бикона к бикону независимо. В текущей версии спецификации IEEE 802.11s [1] этот вопрос решен следующим образом: вводится ограничение на максимальную длительность передачи бикона в L_B микросекунд, и все станции сети считают, что длительность передачи биконов всех других станций равна в точности L_B. Это обстоятельство является существенным недостатком известного способа МВСА, так как значение величины L_B определить трудно. Более того, значение этой величины, применимое во всех возможных случаях, определить невозможно: малое значение L_B существенно ограничивает объем сетевой информации, рассылаемой с помощью биконов, а большое значение L_B часто ведет к простою канала, так как время, затрачиваемое на передачу бикона, в большинстве случаев оказывается значительно меньше L_B.

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

Для решения этой проблемы в последнюю версию спецификации IEEE 802.11s [1] была введена следующая рекомендация: все mesh-станции, поддерживающие работу с информационным элементом Beacon Timing Element, должны воздерживаться от начала передачи кадров, отличных от биконов, если эта передача пересекается во времени с моментом ТВТТ (планируемым началом передачи бикона) какой-либо станции из 2-х шаговой окрестности, как указано в информационном элементе Beacon Timing Element, полученном от любой из соседних станций. Mesh-станции могут возобновить задержанные передачи спустя время L_B после соответствующего момента ТВТТ.

Как уже было замечено, спецификации IEEE 802.11s [1] не предлагает способа назначения величины L_B, которая предполагается фиксированной (что само по себе является недостатком). Кроме того, значения этой величины, применимого во всех возможных случаях, не существует.

Наконец, спецификация [1] не описывает способа выполнения описанной выше рекомендации воздержания от начала передачи в случае ее пересечения во времени с ТВТТ соседних станций. Существует известный способ, применяемый в механизме расширения спектра методом частотных скачков (FHSS) [4], согласно которому станция, которой необходимо воздержаться от передачи кадров до наступления какого-то момента времени t, отсчитывает временные слоты времени отсрочки до нуля и остается в этом состоянии до момента времени t. При наступлении момента t станция начинает передачу. Этот способ обладает существенным недостатком: если станций, которым пришлось воздерживаться от передачи, несколько, то в момент времени t они начнут передачу одновременно, произойдет коллизия, и только после этого, выполняя стандартные процедуры CSMA/CA, станции смогут передать свои кадры.

Известен другой способ рассылки биконов в mesh-сети, отличный от способа, описанного в спецификации IEEE 802.11s и раскрытый в патенте (publication number US 2007014269 (A1), publication date 2007-01-18, application number US 20060424235 20060615, Inventors: SHERMAN ITAY [IL]; KANGUDE SHANTANU [US], Applicant: TEXAS INSTRUMENTS INC). Основная идея заключается в том, что все станции сети поддерживают единую шкалу времени, т.е. для всех станций сети моменты времени ТВТТ совпадают, и станции посылают свои биконы с отступом от моментов ТВТТ, которые они выбирают так, чтобы биконы соседних станций не пересекались во времени. Однако данный способ имеет существенные недостатки: во-первых, он не решает проблемы скрытых станций и не защищает биконы от коллизий с кадрами данных других станций; во-вторых, он требует поддержания во всей сети единого времени, что резко ограничивает масштабируемость сети.

Также известен другой способ рассылки биконов в mesh-сети, раскрытый в патенте (publication number CN 1013 26779 (A), publication date 2008-12-17, application number CN 20068046472 20061207, Inventors: LIUYANG YANG [US]; BAHAREH SADEGHI [US], Applicant: INTEL CORP [US]). Данный способ не требует поддержания единого времени в сети, в отличие от способа (patent publication number US 2007014269 (A1)), однако имеет следующий недостаток: не решает проблемы скрытых станций и не защищает биконы от коллизий с кадрами данных других станций.

Также известен другой способ рассылки биконов в mesh-сети, раскрытый в патенте (publication number KR 20080052034 (A), publication date 2008-06-11, application number KR 20060124024 20061207, Inventors: JEON НО IN [KR]; KIM YEON SOO [KR]; KOH YOUN SUK [KR], Applicant: KT CORP [KR]). Однако данный способ имеет следующий недостаток: он применим лишь в сенсорных сетях с централизованным управлением, т.е. сетях, использующих для организации своей работы специальное устройство-координатор.

Также известен другой способ рассылки биконов в mesh-сети, раскрытый в патенте (publication number US 2007064671 (A1), publication date 2007-03-22, application number US 20060516669 20060907, Inventors: KIM JAE-HOON [KR]; LEE JIN-HOON [KR]; CHOI YOUNG-GON [KR]; KIM JUNG-HO [KR]). Однако данный способ имеет следующий недостаток: он применим лишь в сетях, в которых для передачи биконов выделен специальный интервал времени, в котором передача кадров данных запрещена.

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

Предлагаемый способ надежной рассылки синхрокадров (битное) в беспроводной локальной mesh-сети

Предлагается способ надежной рассылки синхрокадров (биконов) в беспроводной локальной mesh-сети, в которой поддерживается автоматическое распознавание топологии, в общем случае многошаговой, и динамическое построение маршрутов в режиме самоорганизации. Этот способ позволяет предотвратить коллизии биконов с другими управляющими кадрами протокола IEEE 802.11, а также кадрами данных. В основе предлагаемого способа лежат: приостановка текущего процесса обратного отсчета задержки при передаче кадра данных, группы кадров данных или управляющего кадра, отличного от бикона; возобновление приостановленного ранее обратного отсчета задержки при передаче кадра данных, группы кадров данных или управляющего кадра, отличного от бикона, по истечении полученной в результате рассылки предыдущих биконов длительности передачи текущего бикона; ограничение числа кадров, передаваемых в группе кадров, при обнулении счетчика обратной задержки и рассылка с помощью биконов информации о планируемых временах начала передачи и длительностях передачи ее последующих биконов.

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

a) Каждый раз, когда завершается какая-либо передача, т.е. при каждом освобождении канала и по прошествии времени DIFS или EIFS (в случае, если только что завершенная передача была соответственно успешной или неуспешной), каждая станция оценивает минимальное время, обозначим его t_nb, оставшееся до ближайшего момента ТВТТ среди всех станций, находящихся в h-шаговой окрестности данной станции (h>1).

b) Далее станция вычисляет величину Т₁, равную сумме оставшегося времени отсрочки и полной длительности одной попытки передачи кадра, включая необходимый обмен служебными кадрами и необходимые межкадровые интервалы. Если планируется передача группы кадров, то T₁ вычисляется для первого кадра из группы, как если бы он передавался как одиночный кадр.

с) Станция сравнивает величины t_nb и Т₁, и если Т₁>t_nb, mesh-станция приостанавливает обратный отсчет времени отсрочки. В противном случае, отсчет продолжается.

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

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

Способ ограничения числа кадров, передаваемых в группе кадров, при обнулении счетчика обратной задержки состоит в следующем. В случае передачи группы кадров, когда счетчик обнуляется, станция оценивает длительность передачи всей группы из n кадров (обозначим ее T_n), включая необходимый обмен служебными кадрами и необходимые межкадровые интервалы, и, если T_n>t_nb, станция ограничивается передачей такого числа кадров m<n, что T_m≤t_nb; после этой передачи станция обычным образом выбирает новое время отсрочки, как предписывает метод CSMA/CA.

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

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

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

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

- если число TTL в принятом информационном элементе больше нуля, mesh-станция включает данный информационный элемент в свой ближайший по времени бикон, уменьшив значение TTL на единицу и исключив устаревшую информацию о передаче биконов станцией, которая инициировала данный информационный элемент;

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

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

Список литературы

[1] IEEE P802.11s/D3.0. Draft STANDARD for Information Technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment: Mesh Networking [Electronic resource] / IEEE Standards Activities Department. - [USA]: IEEE, 2009.

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

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

[4] IEEE Std 802.11 - 2007, Revision of IEEE Std 802.11 - 1999. IEEE Std 802.11 - 2007, IEEE Standard for Information Technology - Telecommunications and information exchange between systems - Local and metropolitan area network - Specific requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications. IEEE Computer Society, June 2007.

1. Способ надежной рассылки синхрокадров (биконов) в беспроводной локальной mesh-сети, в которой поддерживают автоматическое распознавание топологии, в общем случае многошаговой, и динамическое построение маршрутов в режиме самоорганизации, позволяющий предотвратить коллизии биконов с другими управляющими кадрами протокола IEEE 802.11, а также кадрами данных, отличаетсяспособом приостановки текущего процесса обратного отсчета задержки при передаче кадра данных, группы кадров данных или управляющего кадра, отличного от бикона;способом возобновления приостановленного ранее обратного отсчета задержки при передаче кадра данных, группы кадров данных или управляющего кадра, отличного от бикона, по истечении полученной в результате рассылки предыдущих биконов длительности передачи текущего бикона;способом ограничения числа кадров, передаваемых в группе кадров, при обнулении счетчика обратной задержки;способом рассылки с помощью бикона данной станции mesh-сети информации о планируемых временах начала передачи и длительностях передачи последующих биконов этой станции;

2. Способ по п.1, в котором способ приостановки текущего процесса обратного отсчета задержки при передаче кадра данных, группы кадров данных или управляющего кадра, отличного от бикона, состоит из следующих операций:каждая станция оценивает минимальное время t_nb, оставшееся до ближайшего момента ТВТТ среди всех станций, находящихся в h-шаговой окрестности данной станции, при каждом освобождении канала и по прошествии времени DIFS или EIFS (в случае, если только что завершенная передача была соответственно успешной или неуспешной);станции вычисляют величину T₁ как сумму оставшегося времени отсрочки и полной длительности одной попытки передачи кадра, включая необходимый обмен служебными кадрами и необходимые межкадровые интервалы; если станции планируют передачу группы кадров, то величину T₁ вычисляют для первого кадра из группы, как если бы он передавался как одиночный кадр;станции сравнивают величины t_nb и T₁ и, если T₁>t_nb, mesh-станции приостанавливают обратный отсчет времени отсрочки, в противном случае, продолжают отсчет.

3. Способ по п.1, в котором способ возобновления приостановленного ранее обратного отсчета задержки при передаче кадра данных, группы кадров данных или управляющего кадра, отличного от бикона, по истечении полученной в результате рассылки предыдущих биконов длительности передачи текущего бикона состоит в том, что станция X, приостановившая отсчет времени отсрочки, чтобы дать возможность передать бикон станции Y, возобновляет этот отсчет по истечении времени d_b, равного длительности передачи бикона станцией Y в ближайший момент ТВТТ и отсчитываемого от этого момента;

4. Способ по п.1, в котором способ ограничения числа кадров, передаваемых в группе кадров, при обнулении счетчика обратной задержки состоит из следующих операций:станции оценивают длительность Т_n передачи всей группы из n кадров, включая необходимый обмен служебными кадрами и необходимые межкадровые интервалы;станции ограничиваются передачей такого числа кадров m<n, что T_m≤t_nb, если T_n>t_nb,станции обычным образом (как предписывает метод CSMA/CA) выбирают новое время отсрочки после передачи определенного выше числа кадров.

5. Способ по п.1, в котором способ рассылки с помощью бикона данной станции mesh-сети информации о планируемых временах начала передачи и длительностях передачи последующих биконов этой станции состоит из следующих операций:станции регулярно включают в свои биконы информационные элементы, содержащие информацию о временах начала передачи их последующих J биконов, длительностях этих биконов, а также число TTL, значение которого равно h;mesh-станции включают данный информационный элемент в свои ближайшие по времени биконы, если число TTL в принятом информационном элементе больше нуля, при этом уменьшая значение TTL на единицу и исключая устаревшую информацию о передаче биконов станцией, которая инициировала данный информационный элемент.