некоординированная беспроводная многопользовательская система с пикоячейками со скачкообразным изменением частоты

Формула изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание изобретения к патенту

Предшествующий уровень техники

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

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

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

Протоколы для доступа к проводной среде передачи стандартизованы Институтом инженеров по электротехнике и электронике в его серии IEEE 802. В типовом случае для получения доступа к среде передачи используются различные методы резервирования доступа, такие как контроль несущей (например, для сети Ethernet, соответствующий норме 802.3 метод множественного доступа с контролем несущей и исключения конфликта) или использование маркеров (например, соответствующие норме 802.4 маркерные шины или соответствующие норме 802.5 кольцевые сети с маркерным доступом). Эти протоколы могут быть использованы в распределенном смысле так, что пользователь, занимающий канал, резервирует среду своей текущей передачей или своим маркером. В таких схемах каждый пользователь может прослушивать весь трафик. Т.е. в единой локальной сети все пользователи совместно используют не только один канал, но и всю информацию, передаваемую по этому каналу. Если число участников возрастает, то локальная сеть может быть подразделена на меньшие локальные сети или сегменты, каналы которых работают независимо. Локальные сети могут быть взаимосвязаны посредством сетевых устройств, называемых мостами, или маршрутизаторов, которые образуют интерфейсы между различными локальными сетями. Такие конфигурации приводят к более сложным сетям (см., например, D. Bertsekas and R. Callager, Data Networks, 2^nd Edition, Prentice-Hall, London, 1992). При обсуждении резидентных, т.е. расположенных в помещениях, локальных сетей достаточно рассматривать одиночную локальную сеть. Локальная сеть в типовом случае обеспечивает обслуживание с коммутацией пакетов без установления соединения. Каждый пакет имеет адрес места назначения (и обычно также адрес источника), так что каждый пользователь может определить, предназначен ли передаваемый пакет для него или нет.

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

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

В течение последних нескольких лет организации по стандартам в США и в Европе проводили работы, касающиеся беспроводных локальных сетей (БЛС). В США в результате этих работ был создан стандарт IEEE 802.11 (Проект стандарта IEEE 802.11, P802.11/D1, Dec.1994), а в Европе - стандарт ETSI HIPERLAN (ETSI, RES10/96/etr, "Radio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLANs), July 1996).

Что касается стандарта IEEE 802.11, то, как указывает его название, он представляет собой расширение стандарта 802 для локальных сетей. Беспроводное соединение является линией радиосвязи или инфракрасной линией связи. Среде передачи радиосвязи соответствует полоса на частоте 2,4 ГГц, выделенная для промышленных, научных, медицинских применений (ISM-диапазон). Однако для одиночной локальной сети радиосвязи в каждый данный момент времени выделен только канал со скоростью передачи 1-2 Мбайт/с. Этот относительно узкополосный канал должен совместно использоваться всеми участниками сети радиосвязи. Определена как конфигурация, основанная на проводной инфраструктуре, так и конфигурация, основанная на произвольной (специально созданной) структуре. В случае проводной инфраструктуры система радиосвязи просто обеспечивает беспроводное расширение между проводной локальной сетью и пользовательским терминалом. Фиксированные пункты доступа обеспечивают сопряжение между проводной областью и беспроводной областью. В сети с произвольной структурой беспроводные блоки создают свою собственную беспроводную сеть. При этом не предусматривается вообще никакая проводная основная структура. Именно свойство создания произвольной структуры, обеспечиваемое беспроводными системами связи, дает беспроводным локальным сетям важное преимущество перед проводными локальными сетями в определенных областях применения.

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

В целом стандарт IEEE 802.11 весьма сходен со стандартом для проводной сети Ethernet, но в нем проводной канал заменен на радиоканал со скоростью передачи 1 Мбайт/с. Ясно, что эффективная пропускная способность для пользователя быстро снижается по мере увеличения количества участников. Кроме того, поскольку коэффициент расширения для метода расширения спектра с использованием прямой модуляции последовательностью составляет всего 11, а частота скачков для метода расширения спектра с использованием скачкообразного изменения частоты составляет всего от 10 до 20 скачков в секунду, то в ISM-диапазоне обеспечивается весьма невысокая устойчивость по отношению к взаимным помехам. Различные несущие частоты теоретически могут существовать в одной и той же области (различные сети либо используют различные несущие частоты из определенных семи частот при применении метода расширения спектра путем прямой модуляции последовательностью, либо используют различные последовательности скачкообразного изменения частоты при применении метода расширения спектра путем скачкообразного изменения частоты), увеличивая за счет этого суммарную пропускную способность. Реально отмечалось, что суммарная пропускная способность, определяемая как суммарная пропускная способность для пользователя, умноженная на количество находящихся рядом пользователей (не обязательно являющихся участниками одной и той же сети), никогда не может превысить 4-6 Мбайт/с при применении любого метода (см. А.Kamerman, "Spread-Spectrum Techniques Drive WLAN Performance," Microwaves & RF, Sept. 1996, p.109-114).

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

Стандарт HIPERLAN развивался тем же путем, что и стандарт IEEE 802.11. Система работает в диапазоне на частоте 5,2 ГГц (не предоставлен для использования в США). Стандарт находится все еще в стадии разработки и включает в себя семейство субстандартов HIPERLAN 1-4. Самая основная часть HIPERLAN 1 (ETSI, ETS 300652, "Radio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLAN) Type 1; Functional Specification", June 1996) подобна стандарту IEEE 802.11. И вновь используется один канал, но при более высокой максимальной скорости передачи данных 23,5 Мбайт/с. Используется специализированная схема протокола CSMA/CA, определяемая как множественный доступ с приоритизацией без вытеснения с исключением выхода (EY-NPMA), который предусматривает ряд конкурентных фаз, прежде чем канал будет зарезервирован. Хотя диапазон на частоте 5,2 ГГц является нелицензированным в Европе, разрешены только применения HIPERLAN-типа. Поэтому не реализуются специальные меры по отношению к неизвестным источникам помех. Различные сети могут сосуществовать в одной и той же области, при условии использования различных каналов шириной 23 МГц. Помимо частоты 5,2 ГГц, определены пять таких каналов.

Другая интересная деятельность в направлении разработок стандарта HIPERLAN связана со стандартизацией согласно HIPERLAN 2, которая концентрируется на беспроводном асинхронном режиме передачи (АТМ). Предполагается, что эта беспроводная сеть также будет использовать полосу на частоте 5,2 ГГц, будет поддерживать передачи с максимальными скоростями передачи данных порядка 40 Мбайт/с и использовать централизованную схему доступа с некоторой схемой протокола MAC назначения по требованию.

Общим для существующих беспроводных и проводных локальных сетей является то, что один канал совместно используется всеми участниками в локальной сети. Все пользователи совместно используют как собственно среду передачи, так и всю информацию, передаваемую в этой среде. В проводной локальной сети этот канал охватывает всю среду передачи. Однако это не имеет места в локальных сетях радиосвязи. В локальных сетях радиосвязи среда радиосвязи обычно имеет полосу от 80 до 100 МГц. Ввиду ограничений на практическую реализацию и стоимость приемопередатчиков радиосвязи и ввиду ограничений, устанавливаемых административными органами, подобными FCC и ETSI, представляется невозможным определить канал радиосвязи в локальной сети радиосвязи с той же шириной полосы, что и в среде радиосвязи. Поэтому лишь часть среды радиосвязи используется в одиночной локальной сети. В результате максимальная скорость передачи данных в канале снижается. Но более важным является то, что эффективная пропускная способность для пользователей снижается, так как все участники совместно используют этот канал, который теперь намного меньше, чем среда передачи. Хотя среда передачи подразделяется на различные каналы, каждый из которых может использоваться для установки отдельной локальной сети радиосвязи, на практике только одна сеть перекрывает определенную область, особенно если речь идет о сетях с произвольной структурой. В локальных сетях радиосвязи, базирующихся на проводной инфраструктуре, для создания ячеек могут использоваться различные каналы, причем каждая ячейка находится в своей собственной сети, которая не создает помех соседним ячейкам. Этот результат достигается ценой усилий, направленных на планирование распределения каналов. Таким путем создается сотовая структура, которая подобна сотовой структуре, встречающейся в сотовых мобильных системах. Использование различных сетей радиосвязи с произвольной структурой в одной и той же ячейке, однако, запрещено, что ограничивает достижимую суммарную пропускную способность на единицу зоны обслуживания.

Рассматривая теперь передачу речи с помощью каналов передачи данных, можно заключить, что это все еще представляет проблему в традиционных системах, так как стандарты беспроводных локальных сетей используют схемы множественного доступа, используемые в их проводных прототипах. Показано, что использование таких протоколов MAC для передачи речи также не является в полной мере подходящим (см. М.А. Visser, et al., "Voice and Data Transmission over 802.11 Wireless Network," Proc. of PIMRC"95, Toronto, Sept. 1995, p. 648-652).

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

Сущность изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткое описание чертежей

Задачи и преимущества изобретения поясняются в последующем подробном описании, иллюстрируются чертежами, на которых представлено следующее:

фиг.1 - блок-схема сети, имеющей звездообразную топологию;

фиг.2 - блок-схема сети, имеющей кольцевую топологию;

фиг.3 - блок-схема сети, имеющей ячеистую топологию;

фиг. 4 - иллюстрация беспроводной локальной сети, имеющей рассеянную топологию, соответствующей одному из аспектов изобретения;

фиг. 5а - изображение известной локальной сети, использующей один канал, идентичный среде передачи;

фиг. 5b - изображение известной локальной сети, в которой среда передачи разделена на несколько субканалов;

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

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

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

фиг. 7 - изображение примерной конфигурации, иллюстрирующей процедуру запроса, соответствующую одному из аспектов изобретения;

фиг. 8 - изображение расширенной процедуры запроса в соответствии с другим аспектом изобретения;

фиг. 9 - изображение дерева связности перового типа согласно одному из аспектов изобретения;

фиг.10 - изображение дерева связности второго типа согласно другому аспекту изобретения;

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

фиг. 12 - блок-схема системы, реализующей различные признаки, соответствующие изобретению.

Детальное описание

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

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

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

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

Пример рассеянной сети 401, соответствующей изобретению, показан на фиг. 4. На этом чертеже показаны четыре субсети 403-1,..., 403-4. В каждой субсети 403-х принимают участие только те устройства, которые на самом деле желают обмениваться информацией. Каждая субсеть 403-х имеет свой собственный виртуальный канал, и только участники пикосети соревнуются за получение соответствующего канала. Субсети 403-х функционируют независимо по отношению друг к другу. Устройства, для которых нет необходимости в информационном обмене (например, устройство 8 на фиг.4), не устанавливают соединения. Однако эти устройства периодически сканируют спектр на наличие пейджинговых сообщений, чтобы установить наличие другого устройства, которое желает установить с ним связь.

Для исключения взаимных помех между различными соединениями и субсетями 403-х применяется некоторая форма адаптивного распределения каналов или некоторая форма расширения спектра. Если применяется адаптивное распределение каналов, то устройства, желающие установить соединения, выполняют измерения в различных каналах и затем выбирают наилучший канал (т.е. канал с наименьшими помехами). Адаптивная схема имеет, однако, некоторые недостатки по сравнению с методами расширениями спектра, описанными ниже. Во-первых, может оказаться затруднительным получить надежные измерения в канале вследствие импульсного характера трафика данных. Во-вторых, должен использоваться некоторый механизм, обеспечивающий устройствам, желающим установить связь друг с другом, возможность выбора одного и того же наилучшего канала, что является нетривиальной задачей. Неизбежно использование центрального контроллера. В противоположность этому, расширение спектра, также требуемое Федеральной Комиссией по коммуникациям (FCC) в нелицензируемой полосе частот, подобной ISM-диапазону на частоте 2,4 ГГц, характеризует собой более привлекательный для использования метод.

В случае, когда используется метод расширения спектра, для растягивания спектра взаимных помех может применяться расширение спектра частот путем прямой модуляции последовательностью или скачкообразного изменения частоты. Соответствующий эфирный интерфейс, использующий медленное скачкообразное изменение частоты (СИЧ) описан в заявке на патент США 08/685069 на "Систему радиосвязи малой дальности действия и способ ее использования", поданной 23 июля 1996 на имя Paul W.Dent и Jacobus C.Haartsen, переуступленной заявителю настоящей заявки. В указанной заявке описан эфирный интерфейс, который обеспечивает устойчивость по отношению к взаимным помехам от находящихся рядом пользователей, а также к другим источникам помех путем применения режима скачкообразного изменения частоты и схемы быстрой повторной передачи пакетов.

Скачкообразное изменение частоты по сравнению с расширением спектра за счет прямой модуляции последовательностью является предпочтительным по целому ряду причин. Во-первых, желательно иметь возможность устанавливать множество находящихся в непосредственной близости, но некоординированных соединений. В такой среде расширение спектра за счет прямой модуляции последовательностью создало бы ряд проблем, связанных со степенью удаленности. Механизм управления мощностью не может быть реализован из-за некоординированности передатчиков. Наличие неизвестных источников помех также потребовало бы необходимости в относительно высоком выигрыше за счет обработки и высокой передаваемой мощности. Высокий коэффициент расширения спектра, который связан с получением высокого выигрыша при обработке, привел бы к удорожанию приемопередатчика. Что касается высокой передаваемой мощности, то это представляется нежелательным в условиях аппаратуры с батарейным питанием. Наконец, наилучшая устойчивость по отношению к взаимным помехам достигается путем использования всего располагаемого спектра, т.е. полосы 83,5 МГц на частоте 2,4 ГГц. Расширение спектра за счет прямой модуляции последовательностью может использовать только часть спектра ввиду ограничений по ширине полосы в приемопередатчике. В противоположность этому, системы со скачкообразным изменением частоты могут осуществлять перестройку частоты в среднем во всем спектре, но при этом иметь приемлемое мгновенное значение ширины полосы канала. Аналогично стандарту IEEE 802.11, настоящее изобретение предусматривает использование 79 скачков с шириной полосы 1 МГц. Виртуальный канал определен как псевдослучайная последовательность скачков, изменяющаяся в среднем по всем 79 значениям. Различные соединения могут устанавливаться одновременно путем применения различных виртуальных каналов. Случайным образом различные виртуальные каналы могут использовать одно и то же значение скачкообразно изменяющейся частоты, и в этом случае возникнет конфликт. Для исключения искажений в этом случае используется исправление ошибок и избыточность.

Совместное использование среды передачи в соответствии с настоящим изобретением по сравнению с другими системами поясняется далее со ссылками на фиг. 5а, 5b и 5с. Фиг.5а иллюстрирует известный одноканальный метод, при котором имеется только один канал 503, и этот канал 503 идентичен среде передачи 501, как это имеет место в проводных локальных сетях. Все пользователи конкурируют за получение одного и того же канала 503, и для обеспечения каждому пользователю возможности получить часть ресурсов передачи, используется мультиплексирование путем временного разделения каналов. Доступ к каналу 503 контролируется либо централизованно, либо распределенным образом. Фиг.5b иллюстрирует известную систему, в которой среда передачи 501 разделена на несколько субканалов 505-х, например, с использованием мультиплексирования путем частотного разделения каналов. Пользователи в пределах дальности действия устанавливают сеть с использованием одного из субканалов 505-х. Эти субканалы 505-х являются либо фиксированными (подобно тому, как в стандарте HIPERLAN) или осуществляют медленное скачкообразное изменение частоты в пределах всей среды передачи (подобно тому, как реализовано расширение спектра путем медленного скачкообразного изменения частоты согласно стандарту IEEE 802.11). Т.е. в различные моменты времени выбирается отличающийся субканал 505-х. Однако в любой момент времени все пользователи конкурируют за получение доступа к одному и тому же субканалу. Например, на фиг. 5b иллюстрируется момент времени, в который каждый из пользователей 1-9 конкурирует за получение доступа к субканалу 505-3.

Фиг. 5с иллюстрирует многоканальный подход, соответствующий изобретению. Вновь среда передачи 501 разделена на субканалы. Однако группа соединенных пользователей 507-х мультиплексируется (например, путем скачкообразного изменения частоты) во всех субканалах 509-х с относительно высокой частотой. Пакеты мультиплексируются с частотой скачков среди различных субканалов 509-х. Закон скачкообразного изменения представляет виртуальный канал. На фиг. 5с представлены три группы 507-х пользователей: первая группа 507-1 включает пользователей, идентифицированных как пользователи 2, 3 и 4; вторая группа 507-2 включает пользователей, идентифицированных как пользователи 6, 7 и 9. В соответствии с изобретением каждая из этих групп 507-х образует пикосеть. В данном примере дополнительный пользователь, т.е. пользователь 1 не включен ни в одну из групп 507-х пользователей и поэтому не соединен ни с одной из этих трех пикосетей.

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

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

Обсуждение далее будет фокусироваться на примерах способов, позволяющих устройствам устанавливать соединения произвольной пикосети, описанные выше. Описанная здесь система была оптимизирована для быстрой установки и завершения произвольных соединений между произвольными беспроводными устройствами, рассредоточенными в ограниченной области. Могут устанавливаться двухточечные соединения и соединения от одной точки к множеству точек. Все устройства являются одноранговыми устройствами, каждое из которых использует идентичную радиоприемную аппаратуру связи. В соответствии с одним из аспектов изобретения одному устройству временно придается функция ведущего устройства, когда инициируется установление соединения. Такое назначение продолжается только в течение длительности соединения. Если только не переопределено, ведущим устройством является устройство, которое инициировало соединение. Каждое устройство имеет уникальный адрес или код доступа, с помощью которого оно идентифицируется. В возможном варианте осуществления адрес имеет длительность 64 бита, но, разумеется, это не является обязательным для каждого варианта осуществления. Адрес определяет псевдослучайную последовательность скачкообразного изменения или виртуальный канал, который использует устройство, когда оно является ведущим устройством. Ведущее устройство, таким образом, должно распределять свой адрес среди подчиненных так, чтобы все они использовали тот же самый виртуальный канал со скачкообразным изменением. В течение длительности соединения используется очень длинная последовательность скачков, в которой каждый скачок из 79 возможных скачков реализуется с равной вероятностью. Фаза последовательности скачков определяется системным тактовым сигналом в приемопередатчике ведущего устройства.

Устройство, находящееся в дежурном режиме, активизируется с регулярными временными интервалами, например, каждые Т секунд (например, 1,28 с) для прослушивания пейджинговых сообщений, которые состоят из его адреса. Такое пейджинговое сообщение может рассматриваться как код последовательности прямой модуляции из 64 кодовых элементов: приемник осуществляет корреляционную обработку по отношению к этому коду и активизирует остальную часть блоков приемопередатчика только в том случае, если результат корреляции превышает определенный порог. С каждым новым моментом активизации устройство активизируется при новом значении скачка в соответствии с последовательностью активизации, состоящей из 32 скачков. Эти 32 скачка активизации являются уникальными и равномерно распределены в ISM-диапазоне на частоте 2,4 ГГц. Как скачки активизации, так и псевдослучайная последовательность скачков активизации определяются посредством адреса устройства, находящегося в дежурном режиме. Фаза последовательности определяется системным тактовым сигналом устройства, находящегося в дежурном режиме. Устройство, пытающееся установить соединение (устройство, посылающее пейджинговый вызов), повторно передает пейджинговое сообщение (которое является кодом расширения, представляющим адрес приемника вызова) с высокой частотой повторения на различных значениях скачков. Оно использует скачки активизации и последовательность скачков активизации приемника вызова и пытается соединиться с приемником вызова путем передачи пейджингового сообщения на возможно большем количестве значений скачков в последовательности скачков активизации. Имея оценку системного тактового сигнала приемника вызова, вызывающее устройство может осуществить начальную синхронизацию, поскольку оно знает, когда и на каком значении скачка приемник вызова будет активизирован. При условии известности тактового сигнала приемника вызова задержка начальной синхронизации для наихудшего случая равна Т (вследствие того, что устройство, находящееся в дежурном режиме, активизируется только каждые Т секунд). В случае неизвестности тактового сигнала приемника вызова задержка начальной синхронизации для наихудшего случая равна 2Т. Эти задержки получены в среде передачи без учета ошибок. При наличии ошибок время начальной синхронизации может увеличиться. Вышеописанные способы установления связи с устройством, находящимся в дежурном режиме более полно описаны в заявке на патент США 08/771692 на "Способ доступа в системе связи со скачкообразным изменением частоты", поданной 23 декабря 1996 на имя Haartsen et al.

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

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

Линия связи между устройствами использует дуплексную схему с разделением по времени, согласно которой приемопередатчик радиосвязи попеременно осуществляет передачу и прием. Кадр дуплексного режима с временным разделением состоит из выделенных временных интервалов передачи и приема. Сообщения, подлежащие передаче, разделяются на пакеты. Каждый временной интервал передачи и приема может содержать максимум один пакет передачи и один пакет приема соответственно. Последовательные временные интервалы используют различные значения скачкообразного изменения, как определено виртуальным каналом. Виртуальный канал обеспечивает синхронную линию связи: устройства, которые совместно используют один и тот же виртуальный канал скачкообразно перестраиваются по частоте синхронно и в строгом соответствии с хронированием дуплексного режима с временным разделением. Однако временной интервал не обязательно должен быть занят. Если отсутствуют данные, которые должны передаваться, то два соединенных устройства могут скачкообразно перестраиваться синхронно без обмена пакетами. Хотя услуга, обеспечиваемая такой линией связи, по своей природе является ориентированной на соединение, каждый пакет содержит адрес линии связи, соответствующий виртуальному каналу. Канал не является свободным от конкуренции. Различные виртуальные каналы могут случайным образом использовать одно и то же значение скачкообразного изменения. Следовательно, приемник вызова должен анализировать принятый адрес линии связи, чтобы идентифицировать, действительно ли принятый пакет предназначен для него, или пакет связан с другим виртуальным каналом, который случайно пришелся на то же самое значение скачкообразного изменения, что и в виртуальном канале приемника вызова. Использование адреса линии связи является достаточно важным вследствие того, что импульсный характер трафика может привести к пустым временным интервалам, которые случайным образом могут оказаться заполненными другими линиями связи, и вследствие того, что могут иметь место ситуации с ближним/дальним местонахождением, при которых мешающий пакет полностью вытесняет полезный пакет.

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

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

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

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

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

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

В альтернативном варианте, показанном на фиг.6b, промежуточное устройство, находящееся в пределах дальности действия двух других устройств, действует как мост между устройством-источником и устройством-адресатом. Мост представляет собой более сложное устройство, имеющее возможность соединения с двумя пикосетями. Как показано на фиг.6b, устройства А и В, которые находятся за пределами дальности действия относительно друг друга, принимают участие в различных пикосетях 603 и 605. Мост С принимает участие в каждой из пикосетей 603 и 605. Так как две пикосети 603 и 605 некоординированы, мост С по существу содержит два приемопередающих устройства, каждое из которых принимает участие в различной одной из сетей 603 и 605. Внутри моста С информация передается вперед и назад между двумя приемопередатчиками. Так как мост С использует два виртуальных канала (две пикосети) вместо одной, он обеспечивает более высокую пропускную способность между устройствами А и В, чем пропускная способность конфигурации соединения от точки к множеству точек по фиг.6а.

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

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

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

1) Если адресат находится за пределами дальности действия, каким образом устройство-источник может установить его существование?

2) Как определяется адрес устройства-адресата, если он не может быть определен как непосредственный результат процедуры запроса, осуществляемой устройством-источником?

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

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

Процедура запроса поясняется ниже со ссылками на пример конфигурации, представленной на фиг. 7. Одноранговые устройства 1,...,10 находятся в локальной области. Каждое устройство показано узлом и номером. Потенциальные соединения могут быть установлены между определенными устройствами, как показано пунктирными линиями. Можно видеть в данном примере, что не все устройства могут непосредственно соединяться друг с другом. Например, устройство 9 находится в зоне действия устройств 2, 8 и 10 и поэтому может соединяться с ними, но не может соединяться с другими устройствами 1, 3, 4, 5, 6 и 7. Это может быть вызвано дополнительными потерями распространения (затенением радиоволн) или иными условиями, которые блокируют возможные соединения радиосвязи. При широковещательной передаче запроса устройство 9 получит ответ от устройств 2, 8 и 10, которые сообщают свои адреса и классы обслуживания. Следовательно, список адресов "первого порядка" в устройстве 9 будет иметь вид {2, 8, 10}. Это адреса устройств в первом кольце связности устройства 9. (Разумеется, устройство 9 также сохраняет списки другой информации, такой как классы обслуживания, для соседних устройств. Для простоты вся такая информация условно обозначается далее в обобщенном виде как адреса. ) В дополнение к их собственным адресам, каждое устройство 2, 8 и 10 сообщает устройству 9 свой соответствующий список адресов первого порядка. Эти списки, разумеется, включают адрес устройства 9, если устройство 9 находится в данной локальной зоне достаточно длительное время, чтобы принять запрос и ответить на запрос от этих устройств. Например, устройство 2 выдаст свой список адресов первого порядка, включающий устройства 1, 3, 6, 7 и 9. С использованием списков адресов, полученных от устройств 2, 8 и 10, устройство 9 может сформировать список адресов второго порядка, который включает все устройства в списках первого порядка от других устройств, не охватываемые списком адресов первого порядка устройства 9 и исключающие само устройство 9.

Сравнивая список адресов {1, 3, 6, 7, 9} первого порядка устройства 2 со списком адресов {2, 8, 10} первого порядка устройства 9, можно видеть, что список адресов второго порядка для устройства 9 будет по меньшей мере включать устройства 1, 3, 6 и 7. С использованием списков адресов первого порядка устройств 8 и 10 окончательный список адресов второго порядка для устройства 9 будет иметь вид: { 1,3,6,7}. Ясно, что эту процедуру можно расширить на большее количество удаленных устройств, т.е. устройства могут выдавать свои списки второго порядка устройству 9, которые затем будут использоваться в качестве основы для формирования списка адресов третьего порядка, и т.д.

Эта расширенная процедура запроса иллюстрируется на фиг.8, на которой список адресов i-го порядка произвольного j-го устройства обозначен как L(i, j). На фиг. 8 рассматриваются только списки адресов, необходимые для устройства 9. Устройство 9 имеет список адресов первого порядка L(1,9) = {2, 8, 10}. Устройства 2, 8 и 10 сами имеют списки адресов первого порядка L(1, 2), L(1, 8), L(1,10), как показано на чертеже. Списки L(1, 2), L(1, 8), L(1,10) передаются к устройству 9 соответствующими устройствами 2, 8 и 10 в ответ на запрос устройства 9. Из этих списков устройство 9 может само сформировать список второго порядка L(2, 9) путем слияния списков L(1, 2), L(1, 8), L(1,10) и удаления ссылок на самого себя, а также ссылок на другие устройства, уже включенные в его список первого порядка Ц 1,9). В данном примере это приводит к получению списка второго порядка L(2, 9) = {1, 3, 6, 7}. К устройствам, идентифицированным в этом списке, для устройства 9 отсутствует прямой доступ, но имеется возможность доступа к ним с помощью одного устройства-моста. Таким образом, устройства, перечисленные в списке L(2, 9), образуют второе кольцо связности, как это наблюдается из места расположения устройства 9.

Вышеописанную процедуру можно расширить еще дальше, так как устройства 2, 8 и 10 могут сформировать списки адресов второго порядка L(2, 2), L(2, 8), L(2,10) и передать эти списки устройству 9. После слияния и фильтрации этих списков устройство 9 может получить список третьего порядка L(3, 9) = { 4, 5} . С использованием списков, показанных на фиг.8, можно сформировать дерево связности, которое включает в себя возможные соединения. Дерево связности 901 для устройства 9 показано на фиг.9. Каждый узел в дереве связности 901 представляет конкретное одно из устройств 1,..., 10, а ветвь представляет возможное соединение. На вершине дерева связности 901 находится устройство, для которого построено это дерево, в данном примере устройство 9.

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

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

Для того чтобы решить эту проблему, предложен альтернативный вариант, описанный ниже, который позволяет использовать другую структуру дерева. Как показано на фиг. 10, устройство 10 имеет возможность использовать только списки адресов первого порядка для создания второго дерева связности 1001. Как и в случае первого дерева связности 901, устройство 9 находится на вершине дерева связности 1001. Имеется три устройства, которые могут быть связаны с устройством 9 непосредственно, а именно устройства 2, 8 и 10. Эти устройства 2, 8 и 10 образуют первое кольцо связности 1003. В данном обсуждении, отношение между данным устройством и другими устройствами, с которыми оно может связываться "непосредственно, будет называться отношением порождающего элемента (родителя) и порождаемого элемента (потомка). Таким образом, например, устройство 9 является порождающим элементом, а элементы 2, 8 и 10 являются его порождаемыми элементами. Эти порождаемые элементы, рассматриваемые в свою очередь как порождающие, могут иметь свои собственные порождаемые элементы и т.д.

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

1) порождаемые элементы (т.е. "дети", "внуки", "правнуки" и т.д.) порождающего элемента ("родителя") не могут иметь то же самое имя (например, адрес устройства), что и имя порождающего элемента;

2) порождаемые элементы порождаемого элемента "родителя" не могут иметь то же самое имя, что и имя одного из порождаемых элементов данного "родителя";

3) любой порождаемый элемент "родителя" не может иметь то же самое имя, что и имя других порождаемых элементов этого "родителя".

Второе дерево связности 1001 является результатом соблюдения этих правил в отношении устройств, приведенных для примера на фиг.7. Например, рассмотрим любое появление устройства 5 в третьем кольце связности 1007. Как можно видеть из фиг.7, список связности первого порядка устройства 5 имеет вид L1, 5)={4, 6}. Однако если бы устройству 5 было позволено иметь порождающий элемент в виде устройства 4 в четвертом кольце связности 1009, то это нарушило бы второе правило, поскольку устройство 5, как порождаемый элемент устройства 6, также имело бы "братский" элемент (т.е. другой порожденный объект "родителя" 6), идентифицированный как устройство 4.

Также, если бы устройству 5 было позволено иметь порожденный элемент в виде устройства 6 в четвертом кольце связности 1009, то это привело бы к нарушению первого правила, так как этот порожденный элемент в виде устройства 6 имел бы "предка" (во втором кольце связности 1005), который также идентифицирован как устройство 6.

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

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

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

Можно видеть, что первое, второе и третье кольца связности 903, 905 и 907 первого дерева связности 901 (фиг.9) идентичны первому, второму и третьему кольцам связности 1003, 1005, 1007 второго дерева связности 1001 (фиг. 10). Однако второе дерево связности 1001 отличается от первого дерева связности 901 тем, что оно имеет дополнительное кольцо связности, а именно, четвертое кольцо связности 1009. Причиной того, что во втором дереве связности 1001 появляется это четвертое кольцо связности 1009 (и, следовательно, второе дерево связности 1001 содержит больше информации, чем первое дерево связности 901) является то, что критерии сокращения, которые были применены к построению второго дерева связности 1001, не предусматривали минимизации числа колец связности.

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

Для установления соединения к устройству в составе дерева, устройство, соответствующее вершине дерева (действующее как устройство-источник), может выбрать маршруты в направлении вниз для установления соединения с устройством-адресатом. Могут существовать различные маршруты. Например, предположим, что в примере по фиг.7 устройство 7 желает установить соединение с устройством 6. Возвращаясь к фиг.11, можно видеть из второго дерева связности 1001, что имеется три разных маршрута, которыми можно следовать: первый маршрут 1101, второй маршрут 1103 и третий маршрут 1105. Процедура выбора маршрутов может основываться на любой комбинации следующих факторов:

- число устройств-мостов, которые необходимо использовать для каждого из маршрутов 1101, 1103 и 1105;

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

- могут ли устройства-мосты для каждого из маршрутов 1101, 1103 и 1105 обеспечивать скорости передачи данных, желательные для соединения между устройством-источником и устройством-адресатом;

- имеют ли устройства-мосты для каждого из маршрутов 1101, 1103 и 1105 ресурсы радиосвязи, достаточные для поддержки функции ретрансляции;

- число ветвей, исходящих из устройств-мостов для каждого из маршрутов 1101, 1103 и 1105. Чем больше ветвей исходит из узла ветвления, тем больше взаимных помех может обусловить такое устройство-мост по отношению к другим устройствам. И наоборот, чем меньше ветвей исходят от устройства-моста, тем лучше, так как оно будет создавать меньше помех другим устройствам.

Первое условие (т.е. учет числа устройств-мостов на заданном маршруте) может быть проиллюстрировано при сравнении первого, второго и третьего маршрутов 1101, 1103 и 1105. Первый маршрут 1101 (т.е. 9-2-6) и второй маршрут 1103 (т.е. 9-8-6) потребуют каждый одно устройство-мост, в то время как третий маршрут 1105 (т.е. 9-10-1-4-6) потребует трех устройств-мостов. Предполагая, что каждое из устройств-мостов в данном примере может быть использовано в качестве моста с надлежащими характеристиками, предпочтительными будут первый и второй маршруты 1101 и 1103, ввиду меньшего количества требуемых устройств-мостов. Однако если к тому же важно число ветвей, исходящих из устройств-мостов, то второй маршрут 1003 является предпочтительным по отношению к первому маршруту 1101, так как устройство-мост 8 создаст меньше взаимных помех, чем устройство-мост 2. (Этот вывод основан на учете того факта, что из устройства-моста 2 исходят четыре ветви, в то время как из устройства моста 8 - только две ветви.)

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

Предполагая, что выбран второй маршрут 1103, соединение может быть установлено путем соединения устройства 9 сначала с устройством 8, с запросом к устройству 8 действовать в качестве устройства-моста, и затем установления мостового соединения с устройством 6. Устройство 8 будет затем устанавливать соединение с устройством 6 и затем связывать два соединения с устройствами 6 и 9 для обеспечения второго маршрута 1103 (т.е. 9- 8 - 6).

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

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

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

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

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

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

Для того чтобы ведущее устройство 1201 могло установить соединение с подчиненным устройством 1203, оно дополнительно снабжено средством поискового вызова 1219, которое передает пейджинговые сообщения, как описано выше. Пейджинговое сообщение содержит адрес подчиненного устройства, информация о котором получена от средства запроса 1209. (Разумеется, если топология требует, чтобы соединение было установлено через узел-мост (не показано), то пейджинговое сообщение должно включать в себя адрес узла-моста.) В одном из вариантов пейджинговое сообщение может включать в себя запрос на установление соединения с подчиненным устройством 1203. В другом варианте пейджинговое сообщение служит только для установления соединения с узлом-мостом. После установления соединения с узлом-мостом ведущее устройство 1201 выдает запрос для моста на установление соединения с подчиненным устройством 1203.

Если подчиненное устройство 1203 не используется, оно находится в дежурном режиме. Соответственно, в подчиненном устройстве 1203 имеется средство 1221 активизации. Средство 1221 активизации включает в себя таймер 1223, который обеспечивает периодическую активизацию подчиненного устройства 1203 для определения того, не предназначается ли принятое пейджинговое сообщение для данного подчиненного устройства 1203. Для этой цели предусмотрен блок 1225 сравнения адресов. Если адрес подчиненного устройства 1213 совпадает с адресом принятого пейджингового сообщения, то средство 1227 ответа в составе средства 1221 активизации генерирует и передает соответствующий ответ назад к ведущему устройству 1201.

Один из аспектов настоящего изобретения заключается в том, что как ведущее устройство 1201, так и подчиненное устройство 1203 используют систему связи со скачкообразным изменением частоты. Вследствие этого подчиненное устройство 1203 активизируется на любой одной из ряда предварительно определенных частот поискового вызова, изменяющихся по скачкообразному закону. Поскольку в ведущем устройстве 1201 не известно точно, на какой из скачкообразно меняющихся частот будет активизировано подчиненное устройство 1203, оно повторно передает пейджинговое сообщение с высокой частотой повторения на различных скачкообразно изменяющихся значениях частоты. Оно использует скачкообразно изменяющиеся значения активизации и последовательность скачкообразного изменения активизации приемника вызова и пытается установить связь с приемником вызова путем передачи пейджингового сообщения на максимально возможном количестве скачкообразно изменяющихся значений частоты. Последовательность скачкообразно изменяющихся значений активизации генерируется генератором 1229 пейджингового канала в составе средства 1219 поискового вызова. Предпочтительный способ установления связи с устройством, находящимся в дежурном режиме, более полно описан в вышеупомянутой заявке на патент США 08/771692 на "Способ доступа в системе связи со скачкообразным изменением частоты каналов", поданной 23 декабря 1997 на имя Haartsen et al.

После того как соединение установлено, ведущее устройство 1201 передает свой адрес 1205 ведущего устройства и тактовый сигнал 1207 ведущего устройства к подчиненному устройству 1203. Адрес 1205 ведущего устройства и тактовый сигнал 1207 ведущего устройства затем используются для определения виртуального канала со скачкообразным изменением частоты, который должен использоваться для осуществления связи между ведущим устройством 1201 и подчиненным устройством 1203. В ведущем устройстве 1201 средство связи ведущего устройства включает блок 1231 выбора канала, который генерирует скачкообразно изменяющиеся частоты в соответствующие моменты времени, основываясь на адресе 1205 ведущего устройства (который определяет последовательность скачкообразного изменения) и тактовом сигнале 1207 ведущего устройства (который определяет фазу последовательности скачкообразного изменения).

В подчиненном устройстве 1203, аналогичным образом, в состав средства связи 1233 подчиненного устройства включен блок 1235 выбора канала для генерирования скачкообразно изменяющихся частот в соответствующие моменты времени, основываясь на адресе 1205 ведущего устройства (который определяет последовательность скачкообразного изменения) и тактовом сигнале 1207 ведущего устройства. В предпочтительном варианте осуществления нет необходимости для подчиненного устройства 1203 переустанавливать его тактовый сигнал 1215 подчиненного устройства для обеспечения совпадения с тактовым сигналом ведущего устройства 1201. Вместо этого, когда тактовый сигнал 1207 ведущего устройства впервые принимается подчиненным устройством 1203, то определяется и запоминается разность между тактовым сигналом 1207 ведущего устройства и тактовым сигналом 1215 подчиненного устройства. Затем всякий раз, когда в подчиненном устройстве 1203 необходимо текущее значение тактового сигнала ведущего устройства, оно вычисляется на основе запомненной разности и текущего значения тактового сигнала 1215 подчиненного устройства.

Для того чтобы обеспечить возможность установления соединения более одного подчиненного устройства 1203 с одним и тем же ведущим устройством 1201, подчиненное устройство 1203 дополнительно включает в себя второй блок 1237 сравнения адресов. Как отмечено выше, каждая передача в пикосети включает адрес соответствующего приемника вызова. Поэтому назначением второго блока 1237 сравнения адресов является сравнение принятого адреса адресата вызова с адресом 1213 собственного подчиненного устройства для определения того, является ли оно предназначенным приемником принятой передачи.

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