Выбор синхронизирующих станций в одноранговой сетевой среде

Изобретение относится к области связи. Технический результат - повышение гибкости сетевых технологий для поддержки одноранговой связи. Предложены система, устройство и способ выбора одной или более синхронизирующих станций, или ведущих станций, в среде одноранговой связи. Синхронизирующие станции передают в режиме широкого вещания периодические синхронизирующие кадры для объявления будущих окон доступности, во время которых устройства взаимодействуют для обнаружения и связи. Устройства, которые могут действовать в качестве синхронизирующих станций, объявляют свои параметры предпочтительности, указывающие степень предпочтительности этих устройств или пригодности их для этой роли. Все устройства применяют один и тот же алгоритм для сортировки параметров предпочтительности и идентификации первичной синхронизирующей станции и любого числа вторичных синхронизирующих станций; конечные устройства синхронизируются с первичной или вторичной синхронизирующей станцией. Такой способ пассивной синхронизации позволяет индивидуальным устройствам сберегать энергию, поскольку им не нужно активно обнаруживать другие устройства и сервисы, так что они могут выключать свои радиоприемопередатчики на целые периоды времени без ущерба для обнаруживаемости. 4 н. и 16 з.п. ф-лы, 20 ил., 1 табл.

 

Уровень техники

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

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

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

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

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

Кроме того, некоторые сетевые протоколы или технологии, поддерживающие одноранговую связь, не слишком хорошо сосуществуют с другими технологиями. Например, в среде радиосвязи типичные одноранговые протоколы связи не обладают достаточной гибкостью, чтобы совместно использовать радиооборудование, антенну или частотный спектр с другими протоколами или между приложениями (например, для поддержки соединения Bluetooth^®). Некоторые одноранговые технологии не допускают также многоадресной связи, а требуют, чтобы устройство поддерживало связь с каждым из множества одноранговых ему устройств (узлов) индивидуально, и/или не обладают хорошей масштабируемостью, когда среда становится более плотно «заселенной».

Раскрытие изобретения

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

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

Каждая синхронизирующая станция периодически передает синхронизирующие кадры по одному или нескольким социальным каналам. Эти синхронизирующие кадры идентифицируют каналы и моменты времени для одного или нескольких приближающихся окон взаимодействия между станциями. Такое окно взаимодействия может также именоваться «окном доступности» ("availability window").

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

Описание чертежей

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

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

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

Фиг. 4 представляет диаграмму, демонстрирующую внеполосный обмен сигналами, согласно некоторым вариантам настоящего изобретения.

Фиг. 5A-D иллюстрирует процедуру выбора синхронизирующих станций в коллективе одноранговых устройств связи согласно некоторым вариантам настоящего изобретения.

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

Фиг. 7А-Е иллюстрирует реализацию способа, показанного на Фиг. 6, согласно некоторым вариантам настоящего изобретения.

Фиг. 8 представляет собой блок-схему однорангового устройства согласно некоторым вариантам настоящего изобретения.

Фиг. 9А-В иллюстрирует создание группы в иерархической совокупности устройств связи в одноранговой среде связи согласно некоторым вариантам настоящего изобретения.

Фиг. 10А-С иллюстрирует слияние нескольких групп согласно некоторым вариантам настоящего изобретения.

Осуществление изобретения

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

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

Введение

Среда радиосвязи может характеризоваться произвольным числом устройств связи одного и того же типа и/или различных типов - таких как смартфоны, планшеты, персональные цифровые помощники, портативные и настольные компьютеры и другие устройства. Различные устройства могут иметь разные признаки, в них могут работать различные приложения, они могут иметь различные уровни мощности (например, запас энергии и мощность аккумуляторов), разные потребности в связи, различные нагрузки (например, на процессор или на антенну), и могут слышать другие устройства с различными уровнями сигнала и т.п. Кроме того, среда связи может быть подвижной, «текучей», так что устройства все время входят в пространственную область, занимаемую этой средой связи, проходят через эту область и выходят из нее.

Несколько вариантов настоящего изобретения, описываемых здесь, предлагают протокол, механизм и/или процедуру, которые должны позволить устройствам в такой среде обнаруживать одно другое и устанавливать связь одно с другим непосредственно, в одноранговом режиме. Эти варианты: способствуют уменьшению потребления энергии, даже притом, что они делают устройства и сервисы легко обнаруживаемыми; сосуществуют с другими технологиями связи (например, Bluetooth^®); поддерживают многодиапазонную работу (например, 2,4 ГГц и 5 ГГц); предотвращают деградацию пропускной способности и увеличение задержки, обычно отмечаемых в сетевой инфраструктуре (например, точки доступа) при сохранении совместимости с технологиями на основе инфраструктуры; обеспечивают легкое и быстрое восстановление, если и когда устройство, служащее синхронизирующей станцией (или ведущим) покидает среду; и обладают масштабируемостью для работы в насыщенных средах, где работает много устройств. Эти и другие признаки и преимущества рассмотрены ниже.

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

Параметры одного или нескольких ближайших окон взаимодействия (например, время и канал) сообщают посредством передачи периодических синхронизирующих кадров (Periodic Synchronization Frame (PSF)) в режиме широкого вещания по одному или нескольким социальным каналам. Устройства предварительно программируют с целью периодического прослушивания по меньшей мере одного социального канала в течение промежутка времени, достаточно протяженного, чтобы принять («услышать») по меньшей мере один такой кадр PSF.

Таким образом, когда устройство загружается или входит в среду одноранговых устройств, оно должно настроиться на заданный социальный канал и быстро узнать, где и когда оно может вступить во взаимодействие («встретиться») с другими устройствами. Если устройство не «слышит» кадр PSF, оно может предположить, что оно должно действовать в качестве ведущего, и начать передавать свои собственные кадры PSF, чтобы способствовать синхронизации с другими устройствами, которые могут уже присутствовать, либо могут появиться позднее.

В некоторых вариантах параметры синхронизации (например, график приближающихся окон доступности) могут быть также объявлены во время одного из таких окон доступности, сберегая тем самым устройствам затраты на переключение своих радио приемопередатчиков в социальный канал, чтобы принять эти параметры. Устройство может даже выключать свой радио приемопередатчик, когда оно не прослушивает кадры PSF, не участвует в окне доступности или не использует приемопередатчик для каких-то других целей. Устройство, участвующее в синхронизированной иерархической структуре, может, поэтому, использовать радио приемопередатчик, антенну и/или другие ресурсы связи совместно с какой-либо другой функцией, такой как соединение с инфраструктурой или с каналом Bluetooth^®.

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

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

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

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

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

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

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

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

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

Хотя все члены группы обычно принадлежат также иерархической структуре «по умолчанию», индивидуальные члены иерархической структуры по умолчанию могут быть или могут не быть какой-либо группой иерархической структуры. Идентификаторы структуры по умолчанию и идентификаторы группы отличаются от других идентификаторов устройств (например, IP-адрес, адрес доступа к среде (МАС-адрес), номер международного идентификатора аппаратуры мобильной связи (номер IMEI), международный идентификатор абонента мобильной связи (номер IMSI)).

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

Синхронизация устройств

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

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

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

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

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

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

В этих вариантах периодические синхронизирующие кадры 110 (например, кадры 110а, 110b, 110n) передают на регулярной основе по одному или нескольким социальным каналам 120 (например, каналам 120а, 120b, 120n).

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

Хотя на Фиг. 1 показаны несколько социальных каналов 120, в некоторых вариантах все ведущие станции в одной и той же среде связи и иерархической структуре могут использовать один и тот же социальный канал. Социальные каналы и/или другие каналы, обсуждаемые здесь, могут представлять собой каналы радиосвязи по стандарту IEEE 802.11.

Ответственные синхронизирующие станции передают по социальным каналам 120а, 120b, 120n на периодической основе в режиме широкого вещания соответствующие периодические синхронизирующие кадры 110а, 110b, 110n. Каждый из этих кадров PSF, передаваемых в режиме вещания одной синхронизирующей станцией по одному каналу (например, кадры 110а) может быть идентичен другим кадрам или может в чем-то отличаться, например, в передаваемом графике окон доступности.

Хотя на Фиг. 1 период кадров PSF в каждом канале (P_A, P_B, P_N) отличается от других каналов, в некоторых вариантах настоящего изобретения, в которых используются несколько социальных каналов, периоды передачи кадров PSF в двух или более каналах могут быть идентичными. В качестве иллюстрации, период между кадрами PSF в одном канале может иметь величину порядка 100 мс. Разные синхронизирующие станции могут использовать одинаковые или различные периоды кадров PSF. В некоторых вариантах длина или продолжительность периода кадров PSF может быть обратно пропорциональна общему числу синхронизирующих станций (или числу синхронизирующих станций в конкретной области), передающих кадры PSF.

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

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

В различных вариантах настоящего изобретения кадр PSF может содержать подмножество или расширенное множество элементов иллюстративного кадра PSF 110х, либо полностью отличный набор информационных элементов. Параметры синхронизации (или параметры окон доступности) кадра PSF 110х - сочетание канала 130, момента 132 времени и продолжительности 134, - определяют одно окно доступности, во время которого может произойти встреча и взаимодействие синхронизируемых устройств. Канал 130 идентифицирует канал (например, канал радиосвязи согласно стандарту 802.11), в котором произойдет встреча и взаимодействие между станциями, момент 132 времени идентифицирует момент времени, когда эти станции «встретятся» для взаимодействия, и продолжительность 134 указывает минимальную продолжительность окна.

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

Элемент 132 времени в составе параметров синхронизации в кадре PSF 110х может идентифицировать абсолютный начальный момент времени (например, на основе синхронизированных часов, UTC (универсальное глобальное время) или какого-либо другого общего опорного времени) и/или относительный момент времени. В некоторых вариантах поле меток времени содержит элемент TSF (функция синхронизации времени (Time Sync Function)) станции, передавшей кадр PSF 110х.

В некоторых вариантах настоящего изобретения указание момента 132 времени содержит несколько величин, которые синхронизирующее устройство использует для вычисления начального момента времени окна доступности. В этих вариантах указание момента 132 времени может содержать «целевую» ("target") метку времени, конфигурированную для индикации, когда кадр PSF 110х был сформирован и поставлен в очередь для передачи на передающей синхронизирующей станции (например, когда этот кадр PSF был помещен в буфер передачи), и «фактическую» ("actual") метку времени, конфигурированную для индикации, когда этот кадр PSF был фактически передан через антенну станции. Кадр PSF считается сформированным в момент времени, когда синхронизирующая станция вычислила параметр «сдвиг ведущего» ("master offset").

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

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

Сдвиг = Сдвиг ведущего - (фактическая метка времени - целевая метка времени)

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

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

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

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

Максимальная продолжительность присутствия синхронизирующей станции во время окна доступности может быть задана в кадре PSF 110x и/или может быть анонсирована в ходе этого окна доступности. Например, синхронизирующей станции может потребоваться выйти из окна с целью передать кадр PSF по другому каналу, использовать свой радио приемопередатчик для другой функции связи или по какой-либо другой причине. Что касается индивидуальных устройств, они могут выходить из окна доступности по истечении продолжительности 134, если у них нет ничего для передачи, и если никакое другое устройство не поддерживало связи с рассматриваемым индивидуальным устройством в течение некоторого периода времени в пределах окна.

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

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

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

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

Метрические показатели 138 вторичной синхронизирующей станции включают в себя разнообразные метрические показатели и атрибуты синхронизирующей станции, передавшей кадр PSF 110х, и возможно включают в себя метрические показатели, использованные для вычисления параметра предпочтительности 136 вторичной синхронизирующей станции. Аналогично метрические показатели 142 первичной синхронизирующей станции включают в себя метрические показатели и атрибуты первичной синхронизирующей станции в иерархической структуре по умолчанию. Помимо данных, перечисленных выше, метрические показатели 138 и/или метрические показатели 142 могут включать имя и/или адрес станции (например, МАС-адрес), имя или адрес первичной синхронизирующей станции в иерархической структуре по умолчанию, которой принадлежит рассматриваемая станция, (или число интервалов с переприемом от первичной станции), периодичность передачи кадров PSF станцией, социальный канал, используемый станцией, и т.п.

Когда кадр PSF 110х передан первичной синхронизирующей станцией в иерархической структуре по умолчанию, параметры 136 и 140 предпочтительности совпадут один с другим и метрические показатели 138 и 142 также совпадут один с другим. В альтернативном варианте одно из полей параметра предпочтительности и одно из полей метрических показателей могут быть опущены.

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

В некоторых вариантах настоящего изобретения, в которых метрические показатели 138, 142 содержат данные, используемые для вычисления параметров предпочтительности 136, 140, эти параметры предпочтительности могут быть исключены из периодического синхронизирующего кадра. Напротив, метрические показатели 138, 142 могут быть исключены, если параметры предпочтительности 136, 140 предоставляют всю информацию, необходимую устройствам, получающим кадр PSF 110х (например, для целей идентификации или выбора синхронизирующих станций).

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

В некоторых вариантах настоящего изобретения идентификатор по умолчанию для всех устройств в какой-либо иерархической структуре обычно равен 0, и только ведущее устройство, желающее поддерживать синхронизацию с точкой доступа или с другим инфраструктурным устройством, будет использовать идентификатор по умолчанию, величина которого отлична от 0. В этом случае ведущее устройство может вывести свой идентификатор по умолчанию из, например, идентификатора базового набора сервисов (BSSID (Base Service Set Identifier)) точки доступа с использованием заданного алгоритма. В этой ситуации ведущее устройство может быть способно синхронизироваться только с одноранговыми устройствами, которые также поддерживают синхронизацию с той же самой точкой доступа.

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

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

Кроме того, когда синхронизирующая станция, являющаяся членом какой-либо группы, передает кадры PSF, эти кадры могут содержать информационные элементы, специфичные для этой группы, в дополнение или вместо описанных выше параметров предпочтительности/метрических показателей, специфичных для этой группы. Например, кадр PSF, переданный станцией, может содержать специфичный для группы набор элементов, куда входят некоторые или все из следующего списка: параметр предпочтительности станции, ее уровень или страта в группе (или число интервалов переприема от первичной станции («корня») группы), имя или адрес первичной синхронизирующей станции группы, идентификатор группы и/или какие-либо другие данные, относящиеся к групповой иерархической структуре и/или к иерархической структуре по умолчанию, к которым принадлежит рассматриваемая станция.

Хотя синхронизирующая станция может иметь установленный период передачи указанных периодических синхронизирующих кадров, этот период является гибким и может иметь широкие допустимые пределы изменений. Конкретный кадр PSF может быть «сдвинут» вперед или задержан по времени из-за каких-либо других требований радио приемопередатчика станции, из-за перегрузки канала связи или по какой-нибудь другой причине. В некоторых вариантах интервалы между кадрами PSF могут изменяться в пределах ±20 мс каждые 100 мс.

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

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

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

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

Окна 230 доступности, показанные на Фиг. 2, пронумерованы и осуществляются в виде повторяющейся последовательности. В частности, пакетный синхронизирующий кадр 210 содержит параметры синхронизации, описывающие график для n окон доступности, пронумерованных от 230 (0) до 230 (n-1). После каждой итерации последовательность номеров окон доступности повторяется (т.е. от 0 до n-1). Периодический синхронизирующий кадр может задавать любое число окон доступности.

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

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

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

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

В некоторых вариантах настоящего изобретения, имеет место более узкий допуск на период окон доступности, чем на период следования периодических синхронизирующих кадров, возможен допуск порядка ±100 мкс за секунду (по сравнению с допуском ±200 мс за секунду для кадров PSF). Тогда как кадры PSF очень коротки (например, короче 1 мс), но их передают часто, окна доступности имеют относительно большую продолжительность (например, длиннее 50 мс) и назначаются не часто (например, приблизительно один раз в секунду). Кадры PSF можно планировать по ситуации, поскольку они коротки, а окна доступности конфигурируют для обнаружения устройств и для связи, так что их, в общем случае, нельзя планировать по ситуации.

Хотя и нечастые, окна доступности могут монополизировать радио интерфейс на значительное время; вследствие этого следование жесткому графику является предпочтительным, особенно если здесь же присутствует радиосвязь с использованием других технологий (например, Bluetooth). Кроме того, другие (синхронизированные) устройства зависят от объявленного графика окон для обнаружения других устройств и/или одноранговой связи с ними, что оставляет меньше пространства для каких-либо вариаций.

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

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

Указанные n окон доступности, объявленные посредством кадра PSF 210, показанного на Фиг. 2, осуществляют по двум разным каналам 220x, 220y (т.е. канал X и канал Y, соответственно), которые обычно не являются социальными каналами, но могут быть таковыми. В качестве альтернативы, окна доступности, планируемые синхронизирующей станцией, могут иметь место в одном и том же канале, либо могут быть распределены по более чем двум каналам.

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

В некоторых вариантах настоящего изобретения устройство может задать для себя «режим присутствия» и объявить эту величину своей синхронизирующей станции и/или другим одноранговым устройствам, чтобы указать, как часто оно будет настраиваться на или входить в объявленные окна доступности. В некоторых вариантах признак режима присутствия (или РМ) может иметь целочисленное значения, такое как 1, 2, 4, и т.п. Величина, обратная признаку РМ для устройства, представляет долю, указывающую, как много окон доступности в последовательности устройство собирается посетить. Например, если для устройства признак РМ=1, устройство будет посещать каждое окно доступности; если признак РМ=2, устройство посетит каждое окно, номер которого в последовательности кратен 2 (т.е. ½ всех окон); если признак РМ=4, устройство посетит каждое окно, номер которого в последовательности кратен 4 (т.е. ¼ всех окон).

Более высокое значение признака режима присутствия позволяет устройству пропускать больше окон и выключать свой радио приемопередатчик, тем самым сберегая энергию. В конечном итоге, признак режима присутствия, равный числу окон доступности в последовательности (т.е. n на Фиг. 2), означает, что устройство будет посещать только одно окно доступности в последовательности. Величина признака РМ, равная нулю, может указывать, что устройство доступно всегда (т.е. не только во время окон доступности).

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

Длина последовательности окон доступности обычно равна степени 2 (например, 8, 32, 256). Как показано на Фиг. 2, номера в последовательности окон доступности, передаваемых ведущей станцией, начинаются с нуля и увеличиваются каждый раз на единицу, пока не будет достигнута величина, равна длина-1 (например, 7, 31, 255), после чего все повторяется. Вторичная синхронизирующая станция должна принять и повторить (в своем синхронизирующем кадре) текущий номер в последовательности от своей ведущей станции (т.е. первичной синхронизирующей станции или другой вторичной синхронизирующей станции). Поэтому все устройства, синхронизируемые с одной и той же первичной синхронизирующей станцией, должны согласовать, какое именно из окон доступности имеет номер 0 в последовательности.

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

Например, рассмотрим иерархическую структуру, в которой последовательности окон доступности с длинами 8, 16 и 64 используются различными множествами устройств (например, устройствами, синхронизированными с разными синхронизирующими станциями). Среди устройств, применяющих последовательность из восьми окон, каждое восьмое окно известно под номером 0 в последовательности окон доступности. При этом каждое окно доступности, имеющее для этих устройств номер 0 в последовательности, будет известно как окно доступности с номером 0 или 8 в последовательности для тех устройств, которые используют последовательность длиной 16 окон, и как окно доступности с номером 0, 8, 16, 24, 32, 40, 48 или 56 в последовательности для тех устройств, для которых последовательность имеет 64 окна доступности.

Устройство может посещать больше окон доступности, чем указывает его признак РМ, однако в результате объявления им величины своего признака режима присутствия (например, посредством многоадресного сообщения, переданного в окне доступности с номером 0 в последовательности) другие устройства будут знать, когда они смогут «встретиться» и взаимодействовать с этим устройством. И, как описано ранее, до тех пор, пока какое-либо другое устройство передает сообщения связи устройству, имеющему максимальную величину признака РМ (равную длине последовательности окон доступности), во время окна, которое посетило принимающее устройство, это устройство продлит свое присутствие в таком канале, чтобы продолжать связь.

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

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

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

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

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

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

В некоторых вариантах настоящего изобретения во время окна доступности на канале взаимодействия синхронизирующая станция или другое устройство (например, невыбранная ведущая станция) может передавать синхронизирующий кадр другого типа, называющийся «кадр индикации ведущей станции» (master indication frame (MIF)). В этих вариантах кадры индикации ведущей станции предоставляют информацию, помогающую одноранговым устройствам достигнуть или поддерживать синхронизацию - либо с синхронизирующей станцией, передающей обычные регулярные кадры PSF, либо с невыбранной ведущей станцией, так что устройства могут синхронизироваться для прямого обмена данными. Кадр индикации ведущей станции может быть передан во время окна доступности, но в общем случае его не передают по социальному каналу, если только, например, такой кадр не передают во время окна доступности, имеющего место на социальном канале.

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

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

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

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

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

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

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

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

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

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

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

В ходе операции 310 устройство задает свой режим присутствия, если необходимо или желательно (например, если устройство не может посетить всю последовательность окон доступности). Во время по меньшей мере первого окна доступности, которое оно посетило, и/или первого окна доступности, имеющего номер 0 в последовательности, устройство идентифицирует себя (например, сообщает адрес, имя, информацию о сервисах) в сообщении, передаваемом в режиме широкого вещания всем синхронизируемым устройствам. Оно может объявлять о своем режиме присутствия в одно и то же время.

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

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

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

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

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

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

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

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

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

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

Шкала 410 времени запроса отражает активность в запрашивающем устройстве, тогда как шкала 430 времени ответа отражает активность в отвечающем устройстве. При передаче запроса запрашивающее устройство должно выбрать срок 450 действия запроса таким образом, чтобы отвечающее устройство имело время принять запрос, обработать и ответить на него.

В показанном примере запроса и ответа запрос помещают в очередь, чтобы передать от устройства в целевой момент 412 времени передачи. Из-за конкуренции в антенне или в линии связи и/или какой-либо другой задержки (коллективно представленных в виде времени 414 конкуренции на Фиг. 4) запрос физически не передают до фактического момента 416 времени передачи.

Время 418 операции представляет собой остаточную часть срока действия запроса, в течение которого отвечающее устройство должно принять запрос и затем сформировать и передать свой ответ. Продолжительность времени 418 операции зависит от срока действия запроса, заданного запрашивающим устройством и продолжительности времени 414 конкуренции. Отвечающее устройство может также иметь задержку между целевым моментом 432 времени передачи и фактическим моментом 436 передачи ответа; эта задержка представлена в виде времени 434 конкуренции.

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

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

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

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

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

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

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

Все ведущие станции продолжают передавать кадры PSF для поддержания синхронизации в своих областях и могут делать это с периодичностью, представляющей собой функцию уровня или страты, занимаемой соответствующей станцией в иерархической структуре. Например, первичная синхронизирующая станция в страте О может передавать кадры PSF примерно через каждые 100 мс, вторичная синхронизирующая станция в страте 1 может передавать кадры PSF примерно через каждые 150 мс, вторичная синхронизирующая станция в страте 2 может передавать кадры PSF через каждые 500 мс и т.д. Эти величины являются всего лишь примерами и никоим образом не ограничивают возможные продолжительности периодов передачи кадров PSF; синхронизирующие станции в разных стратах могут использовать один и тот же период, а синхронизирующие станции в одной и той же страте могут применять различные периоды.

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

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

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

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

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

Когда включенное устройство входит в среду связи и слушает ее для обнаружения кадров PSF, то если оно слышит кадры только от вторичной синхронизирующей станции, находящейся в самой глубокой или максимальной страте, это устройство может синхронизироваться с такой станцией в качестве конечного устройства («листа»). Если, однако, рассматриваемое устройство может также слышать другую синхронизирующую станцию из другой иерархической структуры (например, как это определяется по атрибутам первичной синхронизирующей станции, передаваемым в периодическом синхронизирующем кадре), оно может предпочесть присоединиться к этой иерархической структуре, если указанная другая синхронизирующая станция находится не в самой глубокой или максимальной страте или если эта другая синхронизирующая станция имеет лучший параметр предпочтительности для выбора.

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

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

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

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

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

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

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

Выбор синхронизирующих станций

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

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

Параметр предпочтительности каждого устройства получают одним и тем же способом с использованием одинаковых метрических показателей («метрические показатели выбора») или атрибутов устройства. Примерами таких метрических показателей выбора являются доступный запас энергии (например, запас энергии в аккумуляторах), соединено ли устройство с источником питания переменного тока, тип устройства, конфигурация устройства (например, свойства, ресурсы), имеются ли (и как много) приложения или утилиты, требующие использования радио приемопередатчика устройства, имеет ли устройство несколько антенн и приемопередатчиков, может ли устройство работать в нескольких диапазонах (например, 2,4 ГГц и 5 ГГц), нагрузка процессора, конкуренция передач, режим присутствия и т.д.

В простейшей реализации параметр предпочтительности устройства может быть целочисленной величиной, пропорциональной остаточному запасу энергии в аккумуляторах. Особенная, большая величина может указывать, что устройство соединено с сетью переменного тока. Ситуация совпадения («связки)» параметров предпочтительности нескольких устройств может быть разрешена посредством сравнения сетевых (например, MAC) адресов, номеров международного идентификатора абонента мобильной связи (IMSI (International Mobile Subscriber Identity)), номеров международного идентификатора аппаратуры мобильной связи (IMEI (International Mobile Equipment Identity)) или некоторых других уникальных характеристик устройств.

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

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

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

Измерения или оценки дальности могут быть получены на основе индикаторов уровня принимаемого сигнала (received signal strength indication (RSSI)) и/или других индикаторов расстояния (например, данных GPS). В качестве примера, а не для ограничения, «малая дальность» может быть определена радиусом приблизительно 5 м, «средняя дальность» - приблизительно 10 м и «большая дальность» - приблизительно 15 м или более.

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

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

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

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

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

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

Когда устройства 510a-510j включаются в режим онлайн, они начинают слушать по меньшей мере один назначенный социальный канал. Этот канал может быть запрограммирован во встроенном программном обеспечении устройства, может быть запрограммирован провайдером услуг связи как часть процесса регистрации или может стать известен устройствам каким-либо другим способом.

Каждая станция слушает эфир в продолжение промежутка времени не меньше одного известного или определяемого по умолчанию периода кадров PSF (например, 100 мс), в течение которого синхронизирующая станция (вторичная или первичная) должна обычно (если она присутствует) передать один периодический синхронизирующий кадр. Поскольку в изображенной на чертеже среде не было никаких других устройств до появления устройств 510, они не услышат кадр PSF. В некоторых вариантах устройство может слушать несколько разных социальных каналов и/или может слушать в течение более продолжительного времени (например, несколько периодов кадров PSF) прежде, чем предположить, что синхронизирующих станций нет.

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

Для описания настоящего изобретения, на Фиг. 5А устройство 51 Of имеет наилучший (например, наивысший) параметр предпочтительности, а следующее после него - устройство 510d. Максимальная глубина иерархии равна двум, что означает наличие двух уровней или страт ведущих станций - первичная синхронизирующая станция (в страте 0) и один уровень вторичных синхронизирующих станций ниже первичной станции (в страте 1). Все остальные одноранговые устройства будут конечными устройствами, синхронизируемыми с этими синхронизирующими станциями.

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

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

В варианте, показанном на Фиг. 5А, устройство может быть запрограммировано для автоматического прекращения передачи кадров PSF, если оно слышит пороговое число синхронизирующих станций (например, в целом, в конкретной страте, в пределах конкретной дальности), особенно если эти другие устройства имеют лучший или более высокий параметр предпочтительности ведущей станции. В частности, все устройства предполагают, что они были первыми ведущими станциями, и поэтому их кадры PSF будут указывать, что устройства находятся в страте 0 (т.е. у корня, являются первичными станциями). Поскольку пороговое число синхронизирующих станций на этом уровне конфигурировано равным единице (т.е. может быть только одна первичная (корневая) синхронизирующая станция), как только устройство услышит один кадр PSF от однорангового устройства, которое работает в страте 0 и имеет лучший, чем рассматриваемое устройство параметр предпочтительности, это рассматриваемое устройство должно прекратить передачи кадров PSF.

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

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

За счет синхронизации сначала с «ближней» ведущей станции среда связи стремится, по крайней мере первоначально, собраться в локальные кластеры. Это может помочь ослабить помехи, а также отражает реальные ситуации, в которых пользователь устройства часто использует данные совместно с другим пользователем, расположенным близко от него, а не с кем-то далеким. Просматривая затем пространство все дальше, можно обнаружить кластеры устройств и синхронизировать их в среде большего размера.

В среде, изображенной на Фиг. 5А, рассматривают две зоны дальности - «малой» дальности и «большой» дальности. Как обсуждалось ранее, классификация устройств как близких или далеких может зависеть от уровня сигнала между этими двумя устройствами и/или других факторов. В других вариантах могут рассматриваться другие зоны дальности.

На Фиг. 5А, изображены кольца зоны «малой» дальности для двух устройств, имеющих наилучшие параметры предпочтительности ведущей станции (устройства 510f, 510d). Кольцо малой дальности показано также для устройства, которое не станет синхронизирующей станцией - устройства 510a.

Продолжая приведенное выше описание, поскольку каждое устройство понимает, что может быть только одна первичная синхронизирующая станция (в страте 0), все они прекращают передавать кадры PSF, если в зоне малой дальности имеется устройство с более высоким параметром. Это означает, что только устройства 510f и 510d продолжают передавать периодические синхронизирующие кадры в своих зонах малой дальности; каждое из них, таким образом, становится первичной синхронизирующей станцией в своей собственной зоне малой дальности. Поэтому в таком иллюстративном сценарии временно существуют по меньшей мере две раздельные иерархические структуры по умолчанию - «корнем» одной из них является устройство 510f, а «корнем» другой - устройство 510d. Как вскоре будет видно, они сольются.

Другие устройства, находящиеся в пределах зон дальности связи этих двух первичных синхронизирующих станций, синхронизируются с ними и могут начать посещать их окна доступности. Отметим, что устройство 510i, находящееся в зоне малой дальности обеих первичных синхронизирующих станций, синхронизируется с устройством 510f, поскольку оно объявило лучший параметр предпочтительности ведущей станции, чем устройство 510d.

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

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

В примере, изображенном на Фиг. 5A-D, в страте 1 и при максимальной глубине иерархии, равной 2 (например, два уровня синхронизирующих станций, в стратах 0 и 1), возможно устройство может претендовать только на то, чтобы стать вторичной синхронизирующей станцией в страте 1, если оно не слышит какой-либо другой синхронизирующей станции в этой страте (или какой-либо другой вторичной синхронизирующей станции в пределах конкретной дальности). Другими словами, в страте 1 может быть только одна вторичная синхронизирующая станция в пределах дальности любого другого устройства. Любое устройство, которое слышит кадры PSF от синхронизирующей станции страты, будет воздерживаться от передачи собственных кадров PSF и от претензий на то, чтобы стать ведущей станцией в страте 1, до тех пор, пока синхронизирующая станция, которую оно слышит, имеет более высокий параметр предпочтительности ведущей станции.

Поэтому на Фиг. 5А, некоторые устройства, отличные от устройств 510f и 510d, будут объявлять те же самые окна доступности, как их первичные синхронизирующие станции (510f, 510d), но при этом сообщать свою собственную страту (например, 1) и свои параметры предпочтительности. Устройства, которые слышат кадры PSF от этих одноранговых устройств, перестанут претендовать на то, чтобы стать ведущей станцией на уровне 1, если их параметры предпочтительности хуже, но продолжат, если эти параметры лучше.

Поэтому по меньшей мере одно из устройств 510g, 510h, 510i станет вторичной синхронизирующей станцией страты 1 «под» первичной синхронизирующей станцией 510f. Аналогично, по меньшей мере одно из устройств 510a, 510b, 510c, 510e станет вторичной синхронизирующей станцией страты 1 «под» устройством 510d. Поскольку эти устройства в текущий момент являются всего лишь выбираемыми станциями зоны малой дальности и с учетом расстояний между одноранговыми устройствами, реально в раздельных иерархических структурах могут быть выбраны больше одной вторичной синхронизирующей станции страты 1.

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

Например, устройство 510j, которое находится за пределами зоны малой дальности обоих устройств 510f и 510d, может установить свою собственную одноузловую иерархическую структуру. Вспомним, что все устройства 510 включаются одновременно и начинают передавать кадры PSF, номинирующие их в качестве первичных синхронизирующих станций. Предположим, что устройство 510j имеет более высокий параметр предпочтительности ведущей станции, чем какое-либо из близких к нему устройств (например, устройства 510a, 510h), оно продолжит действовать в качестве синхронизирующей станции даже после того, как эти устройства откажутся и прекратят передавать кадры PSF. Предположим далее, что параметр предпочтительности устройства 510j ниже параметров предпочтительности устройств 510d и 510f, тогда ближние устройства (например, устройства 510а, 510h) будут синхронизироваться с устройствами 510d и 510f, а не с устройством 510j. Таким образом, устройство 510j временно образует свою собственную среду и иерархическую структуру.

Теперь, если одно или оба устройства 510а, 510h станут ведущими станциями страты 1, они начнут передавать кадры PSF, объявляющие параметры предпочтительности их первичных синхронизирующих станций. Устройство 510j услышит эти кадры PSF, поймет, что в пределах его дальности связи находится иерархическая структура, «корнем» которой является «лучшая» первичная синхронизирующая станция, и поэтому синхронизируется с устройством, объявляющим наилучшую первичную синхронизирующую станцию (т.е. с устройством 510h, если оно может слышать оба устройства - и 510h, и 510a).

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

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

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

Хотя несколько устройств могут действовать в качестве вторичных синхронизирующих станций страты 1 и передавать кадры PSF, на Фиг. 5В только одно из них (устройство 510h) реально продлило свою иерархическую структуру за пределы дальности связи своей первичной синхронизирующей станции. Синхронизация и организация устройств, изображенных на Фиг. 5В, могут достигнуть установившегося состояния за время порядка одной секунды или продолжительности одного окна доступности от момента включения всех устройств в режим онлайн. Продолжительность промежутка времени, необходимого, чтобы все одноранговые устройства достигли установившегося состояния в своих соответствующих ролях и стратах, различается от варианта к варианту в зависимости от числа устройств, частоты и продолжительности окон доступности, во время которых выполняется алгоритм выбора ведущей станции, и/или других факторов.

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

После завершения синхронизации в зоне малой дальности, в иллюстрируемом варианте настоящего изобретения, первичные синхронизирующие станции (т.е. станции на уровне 0 - устройства 510f, 510d) «заглядывают» дальше, чтобы определить, не должны ли они синхронизироваться с другой синхронизирующей станцией. Для иллюстрации предположим, что большая дальность приблизительно вдвое больше малой дальности.

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

На Фиг. 5С показаны устройства, изображенные на Фиг. 5А, в момент, когда начинается процедура выбора ведущей станции в зоне большой дальности и синхронизации. Хотя на Фиг. 5С кольца равной дальности показаны не полностью, можно предположить, что зона большой дальности для устройства 510f охватывает все устройства за исключением устройств 510b, 510c, и что зона большой дальности для устройства 510d содержит все устройства за исключением устройства 510g. Таким образом, все устройства находятся в зоне большой дальности по меньшей мере одного из двух главных устройств.

Первичная синхронизирующая станция 510f продолжит передавать кадры PSF и объявлять свою последовательность окон доступности без ослаблений, поскольку даже в зоне большой дальности она не услышит какие-либо синхронизирующие кадры, сообщающие о синхронизирующей станции, имеющей более высокий параметр предпочтительности ведущей станции. Первичная синхронизирующая станция 510d, однако, быстро определит, что устройство 510f имеет лучший параметр предпочтительности ведущей станции. Устройство 510d может узнать это непосредственно из кадра PSF от устройства 510f или из кадра PSF, переданного одним из устройств 510h, 510i, действующим в качестве вторичной синхронизирующей станции под управлением первичной синхронизирующей станции 510f.

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

Другие устройства в зоне малой дальности устройства 510d, которые могли действовать в качестве вторичной синхронизирующей станции страты 1, услышат устройство 510d и прекратят передачи кадров PSF в качестве вторичных синхронизирующих станций уровня 1, поскольку устройство 510d имеет второй наивысший параметр предпочтительности ведущей станции, превзойденный только параметром первичной синхронизирующей станции 510f, и поскольку пороговое число лучших ведущих станций, при котором эти другие устройства обязаны перестать действовать в качестве ведущих станций, равно единице. В этом примере среды связи, поскольку максимальная глубина иерархии равна двум (т.е. страты 0 и 1), не будет никаких ведущих станций в страте 2.

Устройства 510а, 510b, 510с, 510е останутся синхронизированными с устройством 510d в качестве конечных устройств (ни одно из них не может быть ведущей станцией), но будут следовать графику окон доступности, распространяемому устройством 510f и теперь объявляемому устройством 510d. В этом иллюстративном варианте устройства 510a, 510b, 510c, 510e не слушают другие устройства, находящиеся на большой дальности, поскольку ни одно из них не было первичной синхронизирующей станцией, и поэтому они не синхронизируются непосредственно с устройством 510f. В других вариантах, в которых эти устройства прослушивают эфир для обнаружения наилучшей синхронизирующей станции в зоне большой дальности, они могут синхронизироваться прямо с устройством 510f.

Устройство 510j синхронизировалось с устройством 510h, действующим в качестве вторичной синхронизирующей станции уровня 1. Поскольку устройство 510h не слушает устройства, находящиеся на большой дальности, (оно не было первичной синхронизирующей станцией), оно не слышит устройства 510d, и поэтому может по-прежнему быть наилучшим кандидатом на роль вторичной синхронизирующей станции уровня 1 в зоне малой дальности устройства 510j. В таком случае устройство 510j остается синхронизированным с устройством 510h.

Это оставляет устройство 510g в качестве единственного устройства, которое не слышит пороговое число вторичных синхронизирующих станций страты 1. Поскольку оно не было первичной синхронизирующей станцией, оно по-прежнему слушает только устройства, находящиеся в зоне малой дальности. Поэтому оно будет оставаться синхронизированным с устройством 510f и начнет передавать кадры PSF аналогично устройству 510d, поместив себя в страту 1 и объявляя свой параметр предпочтительности ведущей станции.

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

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

Как показано на Фиг. 5A-D, в некоторых вариантах настоящего изобретения одноранговые устройства сначала самоорганизуются в виде иерархической структуры в зоне малой дальности. Вскоре после этого образовавшиеся локальные кластеры сливаются в единую синхронизированную среду связи по умолчанию. В приведенном в качестве иллюстрации варианте только первичные синхронизирующие станции зоны малой дальности «заглядывают» (или слушают) за пределы зоны малой дальности, вследствие чего только небольшому числу устройств может потребоваться перейти от синхронизации с одним устройством к синхронизации с другим устройством. В другом варианте, где большее число (или все) устройств «заглядывают» дальше, большему числу устройств может потребоваться перейти от синхронизации со своей локальной или расположенной в зоне малой дальности ведущей станцией к синхронизации с ведущей станцией, расположенной в зоне большой дальности.

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

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

В некоторых вариантах настоящего изобретения одноранговое устройство не может произвольно номинировать себя (например, посредством передачи кадров PSF) в качестве синхронизирующей станции на любом уровне иерархической структуры. Когда устройство слышит синхронизирующую станцию, независимо от страты S этой станции и в предположении, что синхронизирующая станция имеет более высокий параметр предпочтительности ведущей станции, чем рассматриваемое устройство, это устройство может стать конечным устройством под управлением этой станции или, если рассматриваемое устройство не слышит порогового числа вторичных синхронизирующих станций более низкого уровня страты S+1, оно может стать вторичной синхронизирующей станцией на уровне S+1.

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

В вариантах настоящего изобретения, отраженных в логической схеме, показанной на Фиг. 6, конечное (или ведомое) устройство будет синхронизироваться с наилучшей синхронизирующей станцией, которую она слышит с уровнем сигнала, превышающим уровень сигнала, соответствующий дальности, называемой “closeLeaf”. Вторичная синхронизирующая станция будет синхронизироваться с наилучшей синхронизирующей станцией, которую она слышит в пределах дальности "closeMaster", которой соответствует другой уровень сигнала; эта станция может быть первичной синхронизирующей станцией.

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

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

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

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

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

Таким образом, один набор зон дальности (например, closeLeaf, closeMaster, midLeaf, midMaster, большая) может быть использован для определения, с каким ведущим устройством должно синхронизироваться рассматриваемое конкретное устройство. Другой набор зон дальности (например, shortRange, midRange) может быть использован для идентификации роли устройства.

В ходе операции 604 устройство определяет, приняло ли оно недавно синхронизирующий кадр (например, кадр PSF, кадр MIF) от синхронизирующей станции, с которой оно синхронизировано. Если один такой кадр был принят в пределах последнего периода кадров PSF или в пределах какого-либо другого применимого периода времени (например, периода окон доступности), способ переходит к операции 610; в противном случае способ переходит к операции 606.

В ходе операции 606 устройство определяет, прошло ли пороговое число окон доступности или периодов окон доступности (или других применимых периодов времени) без приема синхронизирующих кадров. Если это так, способ переходит к операции 608; а в противном случае устройство сохраняет свое текущее состояние и текущую синхронизацию и прекращает реализацию иллюстрируемого способа без выполнения процедуры выбора ведущей станции. Хотя здесь не требуется производить каких-либо существенных корректирующих действий (поскольку число потерянных кадров PSF не превысило порог), устройство не было недавно синхронизировано и может не иметь текущих параметров предпочтительности ведущей станции для использования при выборе синхронизирующей станции.

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

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

Как описано выше, синхронизирующие станции могут быть проверены на разных дальностях. В этих вариантах для определения дальностей до таких станций может быть использован индикатор RSSI уровня принимаемого сигнала для синхронизирующих кадров, принятых от синхронизирующих станций-кандидатов, или результаты некоторых других измерений уровней других сигналов устройств, такие как индикатор мощности принимаемого канала (RCPI (Received Channel Power Indicator)).

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

bestFarMaster	Идентификатор (например, адрес) наилучшей синхронизирующей станции в зоне большой дальности
bestCloseLeaf	Идентификатор (например, адрес) наилучшей синхронизирующей станции в зоне дальности closeLeaf

bestCloseMaster	Идентификатор (например, адрес) наилучшей синхронизирующей станции в зоне дальности closeMaster
numHigherM	Число синхронизирующих станций в зоне дальности midRange, имеющих более высокие параметры предпочтительности ведущей станции
numHigherS	Число синхронизирующих станций в зоне дальности shortRange, имеющих более высокие параметры предпочтительности ведущей станции

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

Правило 1: Если рассматриваемое устройство является первичной синхронизирующей станцией, а другое устройство находится в дереве, «исходящем» от этой первичной станции, (или наоборот), либо если рассматриваемое устройство является конечным устройством, а другое устройство является текущей синхронизирующей станцией для рассматриваемого устройства (или наоборот), тогда сравнивают параметры предпочтительности ведущей станции для этих устройств. Устройство с более высоким параметром предпочтительности побеждает и получает более высокий ранг; если параметры равны, сравнивают МАС-адреса, и побеждает больший (или меньший) МАС-адрес.

Правило 2: Если Правило 1 неприменимо и ни одно из устройств не является первичной синхронизирующей станцией, но все эти устройства принадлежат к одному и тому же дереву, сравнение зависит от страт, в которых находятся сравниваемые устройства. Если устройства находится в разных стратах, устройство из страты с меньшим номером (т.е. расположенное ближе к «корню» дерева) побеждает. Если устройства находятся в одной и той же страте, побеждает устройство с более высоким параметром предпочтительности ведущей станции; если эти параметры равны, сравнивают МАС-адреса.

Правило 3: Если устройства принадлежат к разным иерархическим структурам (т.е. они не связаны с одной и той же первичной синхронизирующей станцией), сравнивают параметры предпочтительности ведущей станции для соответствующих первичных синхронизирующих станций. Устройство, первичная синхронизирующая станция которого имеет более высокий параметр предпочтительности, побеждает; если эти параметры равны, сравнивают МАС-адреса этих устройств или МАС-адреса первичных синхронизирующих станций для этих устройств.

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

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

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

В ходе операции 612 устройство определяет, является ли оно ведущей станцией категории bestFarMaster (т.е. имеет наивысший параметр предпочтительности ведущей станции среди всех устройств, находящихся в пределах зоны большой дальности относительно рассматриваемого устройства). Если это так, способ возвращается к операции 608; в противном случае способ переходит к операции 614.

В ходе операции 614 устройство определяет, является ли параметр numHigherM (т.е. число синхронизирующих станций в зоне дальности midRange, имеющих более высокие параметры предпочтительности ведущей станции) меньше порогового или максимального числа синхронизирующих станций в зоне дальности midRange (maxM), и является ли параметр numHigherS (т.е. число синхронизирующих станций в зоне дальности shortRange, имеющих более высокие параметры предпочтительности ведущей станции) меньше порогового или максимального числа синхронизирующих станций в зоне дальности shortRange (maxS). Если это так, способ переходит к операции 630; в противном случае способ переходит к операции 620.

В некоторых вариантах настоящего изобретения способ может перейти к операции 630 от операции 614, если либо параметр numHigherM меньше числа maxM, либо параметр numHigherS<maxS (т.е. выполняется операция «ИЛИ» вместо операции «И»).

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

В ходе операции 622 рассматриваемое устройство определяет, имеется ли наилучшее устройство в зоне дальности closeLeaf (т.е. наилучший кандидат в зоне дальности closeLeaf). Если это так, способ переходит к операции 640; а в противном случае переходит к операции 624.

В ходе операции 624 рассматриваемое устройство синхронизируется со станцией категории bestCloseLeaf (т.е. с находящей в зоне дальности closeLeaf синхронизирующей станцией, имеющей наивысший параметр предпочтительности ведущей станции). Затем способ завершает работу.

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

В ходе операции 632 рассматриваемое устройство определяет, является ли оно наилучшим устройством в зоне дальности closeMaster (т.е. находящимся в зоне дальности closeMaster устройством, обладающим наивысшим параметром предпочтительности ведущей станции). Если это так, способ переходит к операции 640; в противном случае он переходит к операции 634.

В ходе операции 634 устройство синхронизируется со станцией категории bestCloseMaster (т.е. с наилучшей синхронизирующей станцией в зоне дальности closeMaster). Затем способ завершает работу.

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

Фиг. 7А-Е иллюстрирует выполнение процедуры выбора ведущей станции, показанной на Фиг. 6, согласно некоторым вариантам настоящего изобретения.

Фиг.7А иллюстрирует коллектив одноранговых устройств, распределенных в среде связи. Ярлыки устройств указывают их ранжирование в порядке, обратном порядку величин параметров предпочтительности ведущей станции для этих устройств (и их МАС-адреса, если метрические показатели двух устройств совпадают), где устройство 710a < устройство 710b < устройство 710c < … < устройство 710i < устройство 710j. Таким образом, из всех устройств, присутствующих в среде связи, устройство 710j имеет наивысший параметр предпочтительности ведущей станции и считается «наилучшим» устройством в рассматриваемой среде.

Как обсуждается выше, к выбору синхронизирующих станций и синхронизации устройств имеют отношение несколько различных величин дальностей. Границы зон «большой» дальности для трех верхних (по рангу) устройств (устройства 710h, 710i, 710j) показаны на Фиг. 7А-Е вместе с масштабом 702, иллюстрирующим «малую» дальность. В иллюстрируемом варианте дальности closeLeaf и closeMaster (как описано выше применительно к Фиг. 6) равны, а масштаб 702 представляет совпадение этих малых дальностей.

Фиг. 7В иллюстрирует соединения малой дальности, устанавливаемые, когда каждое устройство синхронизируется с ближайшей к нему синхронизирующей станцией, которую оно может слышать (например, в ходе операции 634). В иллюстрируемом сценарии большинство устройств находятся в пределах зоны малой дальности от одного из трех верхних (по рангу) устройств и потому синхронизируется с одним из этих устройств. Устройства 710с, 710d, однако, не находят других устройств в пределах зоны малой дальности и потому остаются несинхронизированными до настоящего момента (т.е. каждое в своей собственной иерархической структуре, содержащей только одно устройство).

Можно отметить, что некоторые устройства (например, устройства 710b, 710е, 710f) могут слышать лучшие синхронизирующие станции, чем те, с которыми они первоначально синхронизировались, но они ищут только ближайшую синхронизирующую станцию, не самую лучшую из тех, какие они могут слышать. Кроме того, все эти устройства могут по-прежнему передавать синхронизирующие кадры, поскольку ни одно из этих устройств еще не нашло причин, чтобы стать конечным устройством.

Фиг. 7С изображает среду связи, прослушиваемую синхронизирующими станциями, и соединение. с лучшей синхронизирующей станцией в зоне большой дальности. Например, и согласно способу, иллюстрируемому на Фиг. 6, устройства 710с, 710d, 710i стали синхронизирующими станциями в ходе операции 630, обнаружили, что они являются наилучшими синхронизирующими станциями в зоне малой дальности, в ходе операции 632 и затем выполнили операцию 640, в ходе которой они синхронизировались с наилучшей синхронизирующей станцией в пределах зоны большой дальности. Таким образом, устройство 710i синхронизируется с устройством 710j, а устройства 710c, 710d синхронизируются с устройством 710i.

Кроме того, некоторые устройства теперь переходят в статус конечных устройств, поскольку они слышат пороговые числа синхронизирующих станций, обладающих лучшими параметрами предпочтительности для выбора в пределах зон малой и/или средней дальности. Например, следуя способу, изображенному на Фиг. 6, устройства 710a, 710b (и/или другие) достигают операции 614 и определяют, как много ведущих станций они слышат в зонах малой и средней дальности. Одна или обе эти величины превосходят соответствующие пороговые значения, вследствие чего устройства выполняют операции 620, 622 и 624, что стать конечными устройствами, синхронизированными с наилучшей синхронизирующей станцией в зоне дальности closeLeaf. В качестве иллюстрации, и короткая дальность, и средняя дальность больше малой дальности, но меньше большой дальности.

Штриховые контуры устройств 710а, 710b и 710f обозначают, что они теперь являются конечными устройствами. В качестве конечных устройств они прекращают передачи периодических синхронизирующих кадров.

Кроме того, на Фиг. 7С, «неконечные» устройства начинают или продолжают передавать синхронизирующие кадры, сообщающие величины их параметров предпочтительности ведущей станции и параметров предпочтительности их первичных синхронизирующих станций. Например, устройство 710E будет сообщать параметры предпочтительности для устройств 710e и 710h, а устройство 710g будет сообщать параметры предпочтительности для устройств 710g и 710j.

Фиг. 7D показывает среду связи после того, как устройство 710g физически переместилось ближе к устройству 710е, но по-прежнему остается за пределами зоны большой дальности вокруг устройства 710h. В частности, устройство 710g перемещается в пределах зоны малой дальности вокруг устройства 710е.

Через свои синхронизирующие кадры устройство 710g объявляет свой параметр предпочтительности ведущей станции и параметр предпочтительности устройства 710j. Когда устройство 710е сравнивает эти величины в ходе выполнения процедуры выбора ведущей станции, оно отдает предпочтение устройству 710j перед устройством 710h. Поэтому устройство 710е будет теперь синхронизироваться с устройством 710g.

На Фиг. 7Е устройство 710е начало передавать синхронизирующие кадры, сообщающие его параметр предпочтительности и такой же параметр его новой первичной синхронизирующей станции, т.е. устройства 710j. Устройство 710h сравнит параметр предпочтительности ведущей станции для устройства 710j со своим собственным и увидит, что устройство 710j является предпочтительной первичной станцией.

Устройство 710h может, поэтому синхронизироваться с расширенной иерархической структурой устройства 710j, если, как показано на Фиг. 7E, параметр максимальной глубины иерархической структуры это позволяет. Если устройство 710e было на максимальной глубине в иерархической структуре, тогда устройство 710h могло синхронизироваться с устройством 710e, но могло действовать только в качестве конечного устройства. Если устройство 710g было на максимальной глубине, устройство 710e могло быть только конечным устройством, а устройство 710h могло начать свою собственную иерархическую структуру, если в пределах дальности связи нет других одноранговых устройств.

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

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

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

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

В этих вариантах, если данные о мощности передач/дальности недоступны (или если они совпадают для каких-то устройств), устройство с более высоким остаточным запасом энергии аккумулятора будет иметь более высокий параметр предпочтительности. Если и дальность передач, и запас энергии аккумуляторов неизвестны (или совпадают), можно сравнить МАС-адреса устройств (или другие адреса/идентификаторы).

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

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

Частные группы

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

Как описано в предыдущем разделе, в передаваемых устройством синхронизирующих кадрах (например, кадрах PSF или кадрах MIF), это устройство может объявлять несколько идентификаторов - таких, как идентификатор «по умолчанию» для иерархической структуры, с которой устройство синхронизировано или было синхронизировано, и «групповой» идентификатор для группы, к которой принадлежит устройство. В некоторых вариантах настоящего изобретения все иерархические структуры используют один и тот же идентификатор по умолчанию, например, 0, для отражения обычных одноранговых операций. Устройство, находящееся рядом с несколькими иерархическими структурами по умолчанию, может просто присоединиться к той из них, которая заявляет лучшие параметры первичной синхронизирующей станции или главной ведущей станции. Поэтому использование одного и того же идентификатора по умолчанию для разных иерархических структур не вызывает конфликтов.

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

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

Групповой идентификатор, равный 0, или отсутствие группового идентификатора может обозначать устройство, не участвующее ни в одной группе. Величины больше нуля могут быть зарезервированы для использования активными группами. В разных вариантах групповой идентификатор может иметь различные величины (например, 16 бит, 32 бит).

В вариантах настоящего изобретения конкретную величину, принимаемую в качестве группового идентификатора, выбирает, возможно случайным образом, приложение или сервис, выполняемый всеми членами группы, (например, приложения AirPrint™, Арр Game Kit™, утилита совместного использования файлов) или протокол более высокого уровня, поддерживающий такое приложение. Приложение идентифицирует членов группы для протоколов более низких уровней (например, посредством МАС-адреса или другого идентификатора) и распространяет групповой идентификатор среди членов группы.

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

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

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

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

Правило 1: Член группы синхронизируется с наилучшим устройством (отличным от него самого) в зоне малой дальности, являющимся членом этой же группы (т.е. объявляющим тот же самый групповой идентификатор). Это устройство будет либо групповой первичной синхронизирующей станцией, либо групповой вторичной синхронизирующей станцией.

Правило 2: Если устройство является наилучшим устройством в зоне малой дальности и является членом группы, оно синхронизируется с наилучшим устройством в пределах зоны большой дальности (отличным от самого рассматриваемого устройства), являющимся членом этой группы.

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

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

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

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

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

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

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

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

Хотя ведомое или конечное устройство в иерархической структуре обычно молчит (т.е. не передает синхронизирующие кадры), оно может объявить о создании частной группы в кадрах индикации ведущей станции, передаваемых этим устройством в режиме широкого вещания во время окон доступности. Такое объявление может быть передано посредством протокола уровня конкретного приложения, поддерживающего сетевые или многопользовательские социальные приложения, такие как Арр Game Kit™ от компании The Game Creators, или некоторые другие игровые приложения и приложения для совместного использования контента. Когда другие устройства входят в контакт с первым устройством, приложение получает и принимает их заявки на присоединение.

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

Фиг. 9А-В иллюстрирует создание частной группы в иерархически организованной среде одноранговых устройств согласно некоторым вариантам настоящего изобретения.

На этих чертежах устройства 910a-910m маркированы в порядке их параметров предпочтительности ведущей станции, т.е. устройство 910a > устройство 910b > устройство 910c > … > устройство 910m. Изображение выбранного в качестве иллюстрации устройства 910е увеличено; как показано на увеличенном изображении пара идентификаторов под ярлычком устройства обозначает идентификаторы устройства - идентификатор по умолчанию и групповой идентификатор в форме x/y, где x - идентификатор по умолчанию, и y - групповой идентификатор. Масштаб 902 показывает расстояние, соответствующее зоне малой дальности в среде связи.

На Фиг. 9А совокупность одноранговых устройств организована в две иерархические структуры, «корнем» одной из них является устройство 910а, «корнем» другой - устройство 910с. Все устройства в текущий момент пассивны, как это указывает пара 0/0 из идентификатора по умолчания и группового идентификатора для этих устройств.

Можно отметить, что устройство 910g, для которого показаны границы зоны малой дальности, синхронизировано с деревом, «корнем» которого является устройство 910c, а не с деревом, «корнем» которого является устройство 910a, даже хотя это устройство 910g находится в зоне малой дальности относительно устройств 910f, 910j, таких, что одно из них или оба заявили параметры предпочтительности ведущей станции (относительно устройства 910a), превосходящие соответствующие параметры, объявленные устройством 910i (относительно устройства 910c).

Это может произойти, если, например, ни одно из устройств 910f и 910j не может действовать в качестве синхронизирующих станций, возможно из-за максимальной глубины иерархии, заданной применяемым протоколом. В этом варианте под максимальной глубиной иерархии подразумевают максимальное число интервалов с переприемом между первичной синхронизирующей станцией и самым дальним из конечных устройств. Поэтому, при максимальной глубине 3 могут быть самое большое 3 уровня ведущих устройств (одна первичная синхронизирующая станция в страте 0 и вторичные синхронизирующие станции в стратах 1 и 2) и затем один уровень конечных устройств. Иными словами, максимальная глубина иерархии может идентифицировать максимальное число страт или уровней, в которых могут быть найдены синхронизирующие станции, а конечные устройства могут быть найдены в этих стратах (за исключением «корневой» страты 0) и в одной дополнительной страте.

В среде, показанной на Фиг. 9А, если устройства 910g, 910h, 910i и 910j выбраны для обмена данными (например, для игры или для совместного использования документа), они будут применять другой групповой идентификатор, например, 1. Используя применимые правила и подходящую процедуру выбора (например, процедуру, описанную в одном из предыдущих разделов), эти устройства выберут устройство 910g в качестве групповой первичной синхронизирующей станции, поскольку оно имеет наилучший параметр предпочтительности ведущей станции среди этих устройств.

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

На Фиг. 9В изображена среда и устройства, показанные на Фиг. 9А, после того, как частная группа приняла групповой идентификатор 1, и ее члены синхронизировались внутри группы. Устройства 910h, 910i и 910j синхронизировались со своей групповой первичной синхронизирующей станцией, т.е. устройством 910g (например, как этого требует приведенное выше Правило 1 (или 2)), а устройство 910g синхронизировалось с устройством 910c, как с наилучшим ведущим устройством из состава иерархической структуры по умолчанию, находящимся в зоне большой дальности (например, как этого требует приведенное выше Правило 4).

Устройство 910g будет передавать регулярные синхронизирующие кадры (например, кадры PSF) для поддержания синхронизации членов группы, а также будет посещать окна доступности, объявленные устройством 910c, для сохранения синхронизации с иерархической структурой, к которой принадлежит устройство 910c. В результате планирования одного или нескольких своих окон доступности таким образом, чтобы совместить их с графиком, объявленным устройством 910c, устройство 910g сможет также ввести устройства 910h и 910i в синхронизм с иерархической структурой, «корнем» которой является устройство 910c.

В среде, изображенной на Фиг. 9В, устройство 910m может оставаться синхронизированным с устройством 910h, пока группа 1 активна, поскольку устройство 910h является наилучшим ведущим устройством в пределах зоны малой дальности, имеющим такой же идентификатор по умолчанию. Когда частная группа распадается, индивидуальные устройства из этой группы возобновляют обычное выполнение своих алгоритмов выбора ведущей станции и, если одноранговые устройства в среде связи не меняли своего расположения, конфигурация устройств может вернуться к состоянию, изображенному на Фиг. 9А, или к аналогичной конфигурации.

В некоторых вариантах настоящего изобретения группа обладает своей собственной максимальной глубиной иерархии, причем эта максимальная глубина групповой иерархии может быть использована для увеличения глубины иерархии в иерархической структуре по умолчанию (например, когда первичная синхронизирующая станция группы синхронизируется с не принадлежащим группе устройством, которое является членом иерархической структуры по умолчанию). Например, обратившись к Фиг. 9В, предположим, что устройство 910d имело более высокий параметр предпочтительности ведущей станции, чем устройство 910c (или предположим, что они поменялись местами), и что оба эти устройства находятся в зоне большой дальности вокруг групповой первичной синхронизирующей станции 910g, но не в зоне малой дальности. Изложенные выше правила синхронизации должны диктовать, что устройство 910g синхронизируется с устройством 910d, но это обычно не допускается из-за максимальной глубины иерархической структуры по умолчанию (т.е. трех).

В этих вариантах настоящего изобретения, однако, максимальная величина глубины структуры по умолчанию повышена на величину параметра максимальной глубины группы. Поэтому, если максимальная глубина иерархии в иерархической структуре по умолчанию, изображенной на Фиг. 9В, равна трем, и если максимальная глубина групповой иерархии равна двум, наибольшая длина пути от первичной синхронизирующей станции структуры по умолчанию до конечного устройства, который проходит по меньшей мере через одного члена группы, равна пяти. В этом иллюстративном сценарии устройство 910g может синхронизироваться с устройством 910d, например, а максимальная длина пути тогда может быть показана между первичной синхронизирующей станции 910a в структуре по умолчанию 910 т (т.е., 910a→910b→910d→910g→910h→910m).

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

Фиг. 10А-С иллюстрирует слияние нескольких частных групп согласно некоторым вариантам настоящего изобретения. В этих вариантах устройства могут применять одни и те же или совместимые приложения для совместного использования файлов, игр, использования распределенного ресурса и т.п. Например, устройства из состава одной частной группы могут перемещаться ближе к другой частной группе, в которой работает то же самое приложение, а протокол более низкого уровня может информировать протокол более высокого уровня (например, приложение) о доступности других устройств. Приложение может (или не может) добавлять другие устройства в эту группу в зависимости от конфигурации или ограничений наложенных на это приложение.

На Фиг. 10А устройства маркированы в порядке, соответствующем их параметрам предпочтительности, а именно устройство 1010a > устройство 1010b > … > устройство 1010e. Устройства 1010а и 1010b образуют одну частную группу, имеющую групповой идентификатор 1, тогда как устройства 1010c, 1010d и 1010е образуют вторую группу, имеющую групповой идентификатор 2. Групповые первичные синхронизирующие станции этих групп (т.е. устройства 1010a, 1010c) могут быть синхронизированы с одной и той же иерархической структурой или с разными иерархическими структурами и даже могут быть синхронизированы с одним и тем же устройством в иерархической структуре по умолчанию.

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

Фиг. 10 В изображает устройства, показанные на Фиг. 10А, после того, как устройство 1010d услышало синхронизирующий кадр устройства 1010b. Поскольку групповая первичная синхронизирующая станция 1010a имеет более высокий параметр предпочтительности, чем устройство 1010c, устройство 1010d принимает групповой идентификатор этой группы и разрывает синхронизацию с устройством 1010c.

Переданный устройством 1010b синхронизирующий кадр, побуждающий устройство 1010d сменить группу, может представлять собой кадр индикации ведущей станции (MIF), переданный по социальному каналу. В варианте настоящего изобретения, иллюстрируемом на Фиг. 10A-C, устройства запрограммированы время от времени настраиваться на социальный канал, что позволяет им слышать и другие устройства, отличные от тех, с которыми рассматриваемые устройства уже синхронизированы. В таком случае устройство 1010d получает возможность услышать кадр MIF, переданный устройством 1010b.

Во время большинства окон доступности, наблюдаемых группой или другим множеством синхронизируемых устройств, эти устройства будут взаимодействовать в канале, который не является широко используемым каналом, (например, не является социальным каналом). Однако во время некоторых окон доступности (например, окон с номерами 0, 15, 31 и 47 в последовательности из 64 окон доступности) взаимодействие происходит по социальным каналам. Поэтому, хотя устройство 1010d обычно не будет слышать устройство 1010b, поскольку две раздельные группы большую часть своего времени проводят в других (не социальных) каналах, периодические вещательные передачи кадров MIF по одному или нескольким социальным каналам позволяют рассматриваемым устройствам узнать об устройствах, находящихся за пределами их собственного кластера синхронизируемых устройств.

Фиг. 10C изображает среду связи после того, как устройства 1010c, 1010e услышали устройство 1010d, объявляющее группу 1 и параметр предпочтительности ведущей станции устройства 1010a. Эти устройства также отменяют группу 2 и синхронизируются с новой группой.

В варианте изобретения, показанном на Фиг. 10A-C, процедура слияния двух раздельных групп, использующих общее приложение, может содержать больше взаимодействия. В этом варианте, когда группы впервые сближаются на такую дальность, что устройство из одной группы может слышать устройство из другой группы, устройства обеих групп сначала синхронизируются со своей общей иерархической структурой по умолчанию. Это приводит обе группы к общему графику окон доступности, что позволяет им легко обнаружить одна другую и их сервисы (например, они могут теперь использовать протокол Bonjour). Например, поскольку устройства обеих групп могут теперь применять один и тот же график окон доступности, они будут периодически «встречаться» и взаимодействовать в одном и том же социальном канале (например, по меньшей мере во время окна доступности с номером 0 в последовательности).

Посредством кадров MIF, передаваемых во время таких периодических «встреч» в социальном канале, и/или кадров протокола Bonjour устройство 1010d (и/или другие устройства) обнаружит свою близость к одноранговым устройствам, использующим то же самое приложение, но имеющим другие групповые идентификаторы, и наоборот. В этих устройствах решение о том, что один из групповых идентификаторов необходимо отбросить, чтобы устройства обеих групп могли работать совместно, принимает указанное общее приложение (или какая-либо программная утилита протокола связи более высокого уровня).

В предположении, что группа 2 ликвидируется, устройство 1010d примет групповой идентификатор 1 и применит ряд правил для синхронизации с группой, таких как сформулированные выше. Указанное выше Правило 1 побудит устройство 1010d синхронизироваться с устройством 1010b, поскольку оно является наилучшим устройством или синхронизирующей станцией группы в пределах малой дальности.

Устройства 1010c, 1010e затем изучат другую группу (например, посредством кадра MIF во время окна доступности в социальном канале и посредством протокола Bonjour), заменят групповой идентификатор 2 на групповой идентификатор 1 и воспользуются применимыми правилами синхронизации в группе. Набор правил синхронизации, таких как сформулированные выше, может указать, что устройство 1010e должно синхронизироваться с устройством 1010c (например, согласно Правилу 1). Однако рабочий набор правил для этого сценария может придать больший вес и подчеркнуть важность синхронизации с устройствами, находящимися в более низких стратах иерархической структуры (т.е. ближе к «корню»). Таким образом, поскольку устройство 1010d находится в страте 1 и при этом в пределах зоны малой дальности, то, так как устройство 1010c находится в страте 2, устройство 1010e выберет устройство 1010d в качестве своей ведущей станции.

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

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

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

Одноранговое устройство

Фиг. 8 представляет блок-схему однорангового устройства связи согласно некоторым вариантам настоящего изобретения. На Фиг. 8 изображены два главных уровня протокола или рабочих уровня, а именно - Уровень логических соединений (Logical Link Layer) и Уровень передачи данных (Data Link Layer). Выше уровня логических соединений могут работать одно или несколько приложений и/или утилит (например, mDNS, Bonjour); ниже уровня передачи данных находится Физический уровень (Physical Layer), отвечающий за передачу кадров в линию передачи и прием кадров из этой линии.

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

На уровне передачи данных синхронизирующие кадры (например, периодические синхронизирующие кадры или PSF, кадры индикации ведущей станции или MIF) передают и/или принимают посредством синхронизационного конечного автомата 810. Входящие синхронизирующие кадры направляют в базу 820 данных ведущих станций и затем пропускают выше на уровень логических соединений. Кадры данных обрабатывают в пакетных очередях 822.

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

Конечный автомат отвечает за синхронизацию однорангового устройства с его текущей синхронизирующей станцией (например, если устройство является конечным («листом»)). Если устройство является ведущим, конечный автомат 810 управляет передачей периодических синхронизирующих кадров и/или кадров индикации ведущей станции этим устройством, а также управляет его присутствием в окнах доступности.

Сканирующий конечный автомат 812 сканирует социальные каналы для обнаружения периодических синхронизирующих кадров. Блок 814 управления радиоканалами управляет распределением радио ресурсов (например, совместно используемой антенной) вместе с другими объектами (например, инфраструктурным модулем) и между различными радио приемопередатчиками (например, Wi-Fi, Bluetooth). Синхронизационный конечный автомат взаимодействует с блоком 814 управления радиоканалами для переключения радио приемопередатчика устройства в правильный канал для окна доступности в подходящий момент времени. Сканирующий конечный автомат 812 и/или другие компоненты устройства могут взаимодействовать с блоком управления радиоканалов для других целей (например, сканирование канала для обнаружения новых устройств).

Кэш 816 одноранговых устройств сохраняет релевантную информацию об ограниченном числе других устройств, с которыми рассматриваемое одноранговое устройство поддерживает связь или близко к поддержанию связи. Использование этого кэша может помочь уменьшить проблемы, связанные с ограниченностью памяти в некоторых аппаратных/программно-аппаратных вариантах реализации. Например, уровень передачи данных может быть реализован посредством специализированного чипсета Wi-Fi, который обычно не имеет доступа к большим банкам памяти. Информация в кэше 816 одноранговых устройств синхронизирована с информацией в базе 836 данных одноранговых устройств.

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

База 820 данных ведущих станций сохраняет данные, относительно всех ведущих станций, о которых знает рассматриваемое одноранговое устройство. Такие данные могут быть использованы для синхронизации и/или выбора ведущей станции и могут содержать, не ограничиваясь этим, индикатор RSSI (например, для самого последнего по времени кадра, усредненный по нескольким кадрам, минимальный, максимальный), параметры предпочтительности ведущей станции, метрические показатели выбора и параметры синхронизации.

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

Пакетные очереди 822 на уровне передачи данных сохраняют входящие и/или исходящие кадры данных. Пакетные очереди 832 на уровне логических соединений сохраняют трафик, входящий от других одноранговых устройств или исходящий к другим устройствам.

Планировщик 830 пакетов данных планирует многоадресный, широковещательный и одноадресный трафик к синхронизируемым устройствам и внеполосные запросы/ответы ведущим станциям, с которыми рассматриваемое одноранговое устройство не синхронизировано, («несинхронизированным ведущим станциям») и к устройствам, синхронизированным с такими несинхронизированными ведущими станциями. База данных одноранговых устройств сохраняет информацию относительно окон доступности, режимов присутствия и другую, связанную с временем информацию относительно несинхронизированных ведущих станций.

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

База 836 данных одноранговых станций идентифицирует все устройства, известные одноранговому устройству, показанному на Фиг. 8, и сохраняет информацию относительно каждого устройства. В состав этой информации могут входить, не ограничиваясь, сведения о первичной («корневой») ведущей станции для рассматриваемого устройства, о других ведущих станциях, о метрических показателях выбора ведущей станции, о возможностях (например, поддерживаемые частотные диапазоны, ширина полос пропускания каналов, скорости модуляции/передачи данных), о режиме присутствия, о сервисах, поддерживаемых устройством, о соглашениях относительно блокирования выпадающих квитанций (АСК) и т.д. База 836 данных одноранговых устройств может, таким образом, помочь в процедуре выбора ведущей станции путем создания списка устройств-кандидатов, который может быть упорядочен по параметру предпочтительности.

К прикладным интерфейсам 838 относятся интерфейсы для сопряжения с более высокими системными уровнями и модулями, к которым могут относиться, не ограничиваясь: управление конфигурированием и сетью, графический интерфейс пользователя (GUI (Graphical User Interface)), объявления о сервисах и обнаружение их и т.д. Графический интерфейс пользователя может представлять пользователю устройства список окружающих одноранговых станций, степень их физической близости, дальность или уровни сигналов, список сервисов этих устройств и/или другую информацию.

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

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

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

Таким образом, в некоторых вариантах настоящего изобретения, термин «модуль связи» или «модуль радиосвязи» в составе однорангового устройства может обозначать надежный и устойчивый процессор видеодиапазона, описанный непосредственно выше. В некоторых других вариантах модуль связи может содержать процессор видеодиапазона и соответствующий приемопередатчик для работы и управления антенной устройства и, возможно, запоминающее устройство, используемое процессором видеодиапазона. В других вариантах модуль связи может содержать компоненты уровня логических соединений и уровня передачи данных, показанных на Фиг. 8, а также другие компоненты, необходимые для передачи и приема данных к и от одноранговых устройств.

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

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

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

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

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

Структуры данных и программы, рассматриваемые в настоящем описании, обычно хранятся на компьютерном носителе записи, который может представлять собой любое устройство или носитель записи, способный сохранять программу и/или данные для использования компьютерной системой. К таким компьютерным носителям записи относятся, не ограничиваясь, энергонезависимое запоминающее устройство, магнитные и оптические запоминающие устройства, такие как дисководы, магнитные ленты, CD (компакт-диски), DVD (цифровые универсальные диски или цифровые видеодиски), либо какие-либо другие известные сегодня или созданные позднее носители, способные сохранять читаемые компьютером данные.

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

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

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

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

2. Устройство по п. 1, в котором параметр предпочтительности устройства вычислен на основе набора показателей устройства.

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

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

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

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

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

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

9. Устройство связи по п. 8, характеризующееся тем, что выполнено с возможностью вычислять параметр предпочтительности на основе показателя доступного запаса мощности в соответствующем одноранговом устройстве.

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

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

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

13. Сеть связи по п. 12, в которой один или более показателей выбора для данного устройства включают в себя показатель доступного запаса энергии в указанном данном устройстве.

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

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

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

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

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

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

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