Система и способ установления очередности бесконфликтной передачи с использованием информации о соседних узлах и объявленных значений времени передачи
В настоящем изобретении предложен протокол управления доступом к среде передачи, обеспечивающий бесконфликтную передачу пакетов в канал связи, при этом выделение временных интервалов узлам сети для обеспечения бесконфликтной передачи осуществляют на основании получаемых ими сведений о соседних узлах, образующих их локальную окрестность, и об объявленных временных интервалах, в течение которых соседние узлы, расположенные в локальной окрестности, будут снова пытаться осуществить передачу. В процедуре установления очередности могут быть использованы данные о сроке пребывания в сети вместе с уникальными идентификаторами узлов. Определяют возможные значения времени передачи для каждого узла с использованием перечня значений времени последующих передач, объявленных другими узлами. Узел исключает объявленные значения времени передачи из перечня потенциально возможных значений времени передачи и вычисляет свои собственные возможные значения времени передачи с использованием функции, обеспечивающей различное (псевдослучайное) распределение выходных данных для различных наборов входных данных. Эта функция может представлять собой хеш-функцию, функцию шифрования или функцию таблицы перекодировки. Вычисление возможных значений времени передачи осуществляют с использованием идентификаторов тех узлов, для которых не были получены сведения об объявленном времени передачи. Техническим результатом является ослабление конкуренции между узлами сети и уменьшение задержки доступа к каналу связи для конкретного узла. 5 н. и 21 з.п. ф-лы, 9 ил.
Настоящее изобретение относится к установлению очередности передач без возникновения конфликтных ситуаций в сетях произвольной структуры, в которых маршрутизаторы могут быть подвижными и иметь связанные с ними хост-узлы и сети.
ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ
Для сетей беспроводной связи было разработано множество протоколов управления доступом к среде передачи (УДС) (MAC). Первым из них, который был использован в сетях пакетной радиосвязи с многократным переприемом, являлся протокол множественного доступа с контролем несущей (МДКН) (CSMA). Использование МДКН в сетях с многократным переприемом имеет ограничение, заключающееся в том, что источники, являющиеся скрытыми по отношению друг к другу, не могут обнаруживать их передачи, что ухудшает характеристики МДКН по сравнению просто с протоколом ALOHA. Для решения проблемы МДКН, обусловленной скрытыми терминалами, было предложено и реализовано множество протоколов УДС. Протоколы МДКН имеют очень хорошую пропускную способность до тех пор, пока приемники множества передатчиков, расположенные в пределах их радиуса действия, могут воспринимать сигналы, передаваемые другими передатчиками. К сожалению, проблемы "скрытых терминалов" существенно ухудшают характеристики МДКН, поскольку в этом случае контроль несущей не может предотвратить возникновение конфликтных ситуаций.
Первым предложением, направленным на решение проблем скрытых терминалов МДКН, являлся протокол множественного доступа с тональным сигналом занятости (МДТСЗ) (BTMA) (раскрытый в публикации F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part II- the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution," IEEE Trans. Commun., vol. COM-23, no. 12, pp. 1417-1433, 1975). Протокол МДТСЗ (BTMA) предназначен для сетей на основе базовых станций и разделяет канал на канал передачи сообщений и канал передачи тонального сигнала "занято". Базовая станция передает тональный сигнал "занято" по каналу передачи тонального сигнала "занято", пока она обнаруживает несущую в канале передачи данных. Поскольку базовая станция находится в зоне прямой видимости для всех терминалов, то каждый терминал может обнаруживать канал передачи сигнала "занято" для определения состояния канала передачи данных. МДТСЗ (BTMA) имеет ограничения, состоящие в использовании выделенного канала для передачи сведений о состоянии канала передачи данных, в необходимости наличия приемника для передачи тонального сигнала "занято" при обнаружении несущей в канале передачи данных и в сложности обнаружения тонального сигнала "занято" в узкополосном канале.
Также для сетей пакетной радиосвязи был предложен протокол множественного доступа с тональным сигналом занятости, инициируемым приемником (раскрытый в публикации: C. Wu and V. О. K. Li, "Receiver-initiated busy-tone multiple access in packet radio networks," ACM SIGCOMM 87 Workshop: Frontiers in Computer Communications Technology, Stowe, VT, USA, 11-13 Aug. 1987). В этой схеме передатчик перед передачей пакета данных передает в приемник запрос на передачу (ЗНП) (RTS). Когда приемник получает надлежащий ЗНП, то он передает по выделенному каналу тональный сигнал "занято" для уведомления других источников, что они должны подождать. Надлежащий источник всегда уведомляется, что он может приступить к передаче пакета данных. Эта схема имеет ограничения, состоящие в том, что она по-прежнему требует наличия отдельного канала передачи тонального сигнала "занято" и дуплексного режима работы приемника.
Было предложено несколько протоколов, основанных на различные типах квитирования установления связи "с предотвращением конфликтных ситуаций" посредством малых управляющих пакетов и предназначенных для предотвращения конфликтных ситуаций на уровне данных в том случае, когда источники пакетов данных не могут "слышать" друг друга. Принцип предотвращения конфликтных ситуаций из известного уровня техники является логическим следствием основных философских принципов, впервые введенных Тобаги и Кляйнроком (Tobagi и Kleinrock) в протоколе множественного доступа с резервированием разделенного канала (МДРРК) (SRMA) (раскрытого в публикации: F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part III - polling and (dynamic) split-channel reservation multiple access," IEEE Trans. Commun., vol. COM-24, no. 8, pp. 832-845, 1976). В протоколе МДРРК (SRMA) и в последующих наиболее новых протоколах, обеспечивающих предотвращение конфликтов, сетевой узел-отправитель посылает пакет, содержащий запрос на передачу (ЗНП) (RTS), намеченному получателю либо посредством контроля канала перед передачей ЗНП, либо без контроля канала перед передачей ЗНП. Получатель, "слышащий" ЗНП без помех, отвечает на него сигналом готовности к передаче (ГП) (CTS) и после того, как отправителем "услышан" сигнал ГП без помех, он может передать пакет данных.
В патенте США №5319641, права на который принадлежат фирме "Echelon Systems Corp.", раскрыт способ усовершенствования протоколов МДКН с постоянной пропускной способностью, осуществляемый путем введения случайного времени ожидания, в течение которого станции в случае наличия в них пакетов, предназначенных для передачи, должны ожидать, прослушивая канал. Раскрытый способ не работает в сетях со скрытыми терминалами.
В патенте США №4661902, права на который принадлежат фирме "Apple Computer, Inc.", раскрыт способ, обеспечивающий реализацию протокола МДРРК (SRMA) в одиночном канале, при этом в данном способе перед передачей запросов ЗНП (RTS) в станциях используют контроль несущей.
Способ управления доступом к среде, именуемый MACA(?) (раскрытый в публикации: P. Karn, "MACH - a new channel access method for packet radio," in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL, 1990), обеспечивает функционирование протокола МДРРК в одиночном канале, при этом в данном способе пакет, содержащий запрос на передачу (ЗНП), передается без контроля несущей. При этом не описано, каким образом передавать последовательность пакетов. В патенте США №5231634, права на который принадлежат фирме "Proxim, Inc", раскрыт способ, в котором также используют основной принцип реализации МДРРК в одиночном канале. ЗНП указывает длину пакета данных, ожидающего передачи.
В патенте США №5502724, права на который принадлежат фирме "International Business Machines Corporation (IBM)", раскрыт способ, расширяющий квитирование установления связи для предотвращения конфликтных ситуаций, чтобы обеспечить прохождение множества пакетов данных через две станции, поддерживающие связь друг с другом. Станция, намеревающаяся установить связь со второй станцией, контролирует канал. Если канал свободен, то она посылает в намеченную принимающую станцию пакет, содержащий запрос на установление соединения, ЗУС (CR). В ЗУС указано количество пакетов данных для передачи по этому соединению. Намеченная станция-получатель передает в передающую станцию пакет подтверждения установления соединения, ПУС (CC). В ПУС также указано количество пакетов, передаваемых по этому соединению. После обмена надлежащими пакетами ЗУС и ПУС передающая станция может передать один или множество пакетов данных, а принимающая станция может передать пакет подтверждения приема, в котором указано, какие пакеты данных были приняты правильно. Для завершения сеанса связи передающая станция передает запрос на разъединение, ЗНР (DR), а принимающая станция выдает подтверждение разъединения, ПР (DC). Станции, получающие пакет ЗУС, задерживают свои передачи на некоторый промежуток времени, достаточный для передачи объявленного количества пакетов данных получателю. После получения ЗУС или ПУС станция может предпринять попытку доступа к каналу по истечении заданного таймером времени, которое пропорционально количеству пакетов, передаваемых по соединению, или случае получения ею пакета, содержащего ЗНР или СПР. Способ, раскрытый в патенте США №5502724, имеет ограничение, состоящее в том, что данный способ не может обеспечить бесконфликтную передачу пакетов данных даже в случае передачи получателем пакетов ПУС. Необходимость наличия обратной связи между получателем и соседними по отношению к нему узлами, обеспечиваемой для каждого пакета, была продемонстрирована в публикации: C. L. Fullmer and J J. Garcia Luna-Aceves, "Solutions to Hidden Terminal Problems in Wireless Networks", Proc. ACM SIGCOMM 97, Cannes, France, September 14-18, 1997). Поскольку в узле, являющемся соседним по отношению к получателю, может возникнуть конфликтная ситуация между пакетом ПУС, переданным получателем, и другим пакетом, то пакет ПУС не обеспечивает достаточную обратную связь со скрытыми узлами; кроме того, необходимость того, чтобы пакеты обратной связи имели большую длину, чем пакеты с запросами, была продемонстрирована в публикации C. L. Fullmer and J J. Garcia-Luna-Aceves, "Floor Acquisition Multiple Access (FAMA) for Packet-Radio Networks," Proc. ACM SIGCOMM 95, Cambridge, MA, Aug. 28-Sept. 1, 1995. Однако хотя раскрытый способ ссылается на широковещательную передачу пакетов во все соседние станции, этот способ не обеспечивает условий, гарантирующих прием пакетов широковещательной или групповой многоадресной передачи, без помех всеми узлами сети, являющимися соседними по отношению к передающей станции. В патенте США №5721725, права на который принадлежат фирме "Xerox Corp.", раскрыт способ, аналогичный МДРРК, являющийся усовершенствованным по сравнению со способом MACH. Расширение возможностей способа MACH обеспечивается за счет указания в пакетах ЗНП желательной скорости передачи пакетов данных и предоставления отправителю и получателю возможности согласования скорости передачи данных. Этот способ не может гарантировать бесконфликтные передачи в сетях со скрытыми терминалами, поскольку не предприняты меры, обеспечивающие то, чтобы длина ГП была большей, чем длина любого ЗНП, для гарантированного обнаружения конфликтов между ЗНП и ГП скрытыми станциями.
Тремя дополнительными примерами новых протоколов предотвращения конфликтных ситуаций являются следующие: протокол распределенного базового управления доступом к среде передачи в беспроводных сетях согласно стандарту IEEE802.11 Института инженеров по электротехнике и электронике (ИИЭР), США, именуемый DFWMAC (K.C. Chen, "Medium Access Control of Wireless LANs for Mobile Computing," IEEE Network, vol. 8, no. 5, pp. 50-63, 1994), протокол множественного доступа с захватом нижнего уровня для сетевых компьютерных систем, именуемый FAMA-NCS (C. L. Fullmer and J.J. Garcia-Luna-Aceves, "Solutions to Hidden Terminal Problems in Wireless Networks", Proc. ACM SIGCOMM 97, Cannes, France, September 14-18, 1997), и протокол множественного доступа RIMA (J J. Garcia-Luna-Aceves and A. Tzamaloukas, "Reversing the Collision Avoidance Handshake in Wireless networks," Proc. ACM/IEEE Mobicom 99, August 1999). Способ, используемый в протоколе стандарта IEEE802.11, очень похож на протокол МДРРК с контролем несущей для передачи ЗНП. Протокол FAMA-NCS предназначен для того, чтобы станция, имеющая данные, которые нужно передать, получила управление каналом поблизости от получателя (который здесь называется "нижним уровнем") перед передачей любого пакета данных, и для гарантии отсутствия конфликтных ситуаций между любыми пакетами данных в станции-получателе. Для обеспечения обнаружения конфликтов между ЗНП и ГП протокол FAMA-NCS делает длину ГП намного большей, чем длина ЗНП, что не может быть принудительно сделано в предшествующих протоколах предотвращения конфликтов. Протокол RIMA содержит семейство протоколов, предусматривающих реверсивный способ квитирования, предотвращения конфликтных ситуаций, впервые введенного в протоколе МДРРК, и заставляющих получателя осуществлять опрос отправителя данных. Было предложено несколько иных протоколов управления доступом к среде передачи (УДС) как для одноканальных сетей беспроводной связи, так и для локальных сетей проводной связи, которые основаны на аналогичном обмене ГП и ЗНП или на передаче ЗНП (RTS), сопровождаемой паузами. Однако несмотря на популярность в течение последних лет протоколов предотвращения конфликтных ситуаций и систем на основе таких протоколов, все протоколы УДС, предотвращающие возникновение конфликтных ситуаций, имеют два основных ограничения их характеристик: (а) они не могут обеспечить гарантированную задержку доступа к каналу, что представляет собой большую проблему для приложений реального масштаба времени; и (б) в них отсутствует явная поддержка бесконфликтной широковещательной или групповой многоадресной передачи, что означает, что либо узел сети должен осуществить многократную передачу одного и того же многоадресного пакета, по одному разу каждому соседу многоадресной группы, либо пакеты передаются с такой же низкой вероятностью приема, как и в протоколе ALOHA. Кроме того, для протоколов предотвращения конфликтных ситуаций требуется операция контроля несущей, правильная реализация которой в сетях радиосвязи расширенного спектра с прямой передачей последовательности с очень высокими скоростями передачи кодовых элементов является трудновыполнимой задачей с технической или с экономической точки зрения.
Для того чтобы обойти проблемы, связанные с помехами от скрытых терминалов, получателям или отправителям могут быть присвоены уникальные коды (коды расширения спектра или последовательности скачкообразного изменения частоты).
Примером такого подхода является сеть фирмы "Metricom". Однако для присвоения кода, ориентированного на приемник, (ROCA) и для присвоения кода, ориентированного на передатчик, (TOCA) требуется либо предварительное конфигурирование устройств радиосвязи с отображениями типа «узел-код», либо обнаружение кодов, используемых соседними передатчиками или приемниками. Кроме того, просто использование принципа TOCA не гарантирует эффективность широковещательной передачи, поскольку все узлы, являющиеся соседними по отношению к передатчику, должны согласованно одновременно прослушивать передатчик, чтобы свести к минимуму количество передач.
Другим способом доступа к каналу, используемым в сетях беспроводной связи с многократным переприемом, является способ, содержащий операцию установления графиков очередности передачи, то есть выделение станциям различным промежутков времени и каналов передачи данных (например, частот, кодов расширения спектра или их совокупности) таким способом, чтобы не возникали конфликтные ситуации. График очередности передачи может быть статическим или динамическим; протоколы УДС, основанные на динамическом графике очередности передачи, анализируют степень повторного пространственного использования канала радиосвязи и, следовательно, обеспечивают намного более высокий коэффициент использования канала, чем подобные способы с неизменной очередностью передач, такие как способ множественного доступа с временным разделением, МДВР (TDMA), и способ множественного доступа с частотным разделением, МДЧР (FDMA).
В протоколах МДВР время разделяется на кадры, содержащие временные интервалы. Временные интервалы выделены конкретным узлам сети, или используется централизованная станция для распределения временных интервалов. Ограничениями, присущими способу МДВР с древовидной структурой вследствие фиксированного выделения временных интервалов для узлов сети, является их медленная адаптация к изменениям в сети и неэффективное использование канала в том случае, если узлы являются пульсирующими источниками трафика, а также использование централизованных распределений.
В известном уровне техники существует множество подходов к решению этих проблем, основанных на использовании динамических способов МДВР, в которых станции используют протокол ALOHA, протокол ALOHA с разделением на временные интервалы или иные конкурентные протоколы в восходящем канале связи для запросов временных интервалов в базовой станции. Примером такого подхода является система, раскрытая в патенте США №5638371, права на который принадлежат фирме "NEC USA, Inc.". Настоящее изобретение устраняет необходимость в наличии базовой станции для распределения временных интервалов.
Недавно были предложены протоколы динамического выделения временных интервалов, не требующие центральных базовых станций. Эти протоколы могут быть классифицированы как протоколы установления очередности передач по времени, не зависящие от топологии и зависящие от топологии.
Не зависящие от топологии протоколы установления очередности передач по времени описаны в следующих публикациях: T. Shepard, "A Channel Access Scheme for Large Dense Packet Radio Networks," Proc. SIGCOMM 96, 1996; патент США №5682382 от 28 октября 1997 г. на «Масштабируемую самоконфигурирующуюся сеть пакетной радиосвязи с децентрализованным управлением каналами, обеспечивающим бесконфликтную передачу пакетов»; I. Chlamtac et al, "Time-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks," IEEE/ACM Transactions on Networking, Vol. 5, no. 6, Dec. 1997; Ji-Her Ju, Victor O.K. Li, "An Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks," IEEE/ACM Transactions on Networking, Vol. 6, no. 3, June 1998. В этих протоколах для узлов сети заранее задан (например, посредством их собственных идентификаторов сетевых узлов) или назначен по согласованию с ними график очередности передачи, который они придают огласке, и этот график очередности передачи определяет те моменты времени, в которые узел сети осуществляет передачу и прием. Эти протоколы гарантируют или обеспечивают высокую вероятность того, что, по меньшей мере, в один момент времени передачи в имеющемся в узле сети графике очередности передачи отсутствуют конфликты с любым узлом сети, отстоящим от него на расстояние одного или двух участков ретрансляционного переприема на пути следования сообщения. В технических решениях, предложенных Chlamtac и Ju, узлы сети не способны определять то, какие именно данные переданы успешно, что усложняет работу протоколов более высокого уровня (например, канального уровня). Эти технические решения также требуют наличия количественных данных об общем количестве узлов в сети и о максимальном количестве соседних узлов для каждого узла сети, которые служат в качестве входных параметров для алгоритма, а это, следовательно, приводит к тому, что они предназначены для наиболее неблагоприятных условий (и, следовательно, являются неэффективными в том случае, если сеть является менее плотной, чем ожидается) или являются чувствительными к фактическому состоянию сети (если сеть является более крупной или более плотной, чем ожидается). В техническом решении, предложенном Shepard, предотвращение конфликтных ситуаций обеспечивают с учетом того предположения, что узлы сети являются синхронизированными с соседними по отношению к ним узлами, имеют сведения о графиках очередности передачи соседних узлов и способны производить одновременный прием из множества соседних узлов, осуществляющих передачу. Это последнее предположение требует наличия весьма сложной радиоаппаратуры. В публикациях C. Zhu, M.S. Corson, "A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks," Proc. IEEE INFOCOM '98); Z. Tang and J J. Garcia-Luna-Aceves, "A Protocol for Topology-Dependent Transmission Scheduling," Proc. IEEE Wireless Communications and Networking Conference 1999 (WCNC 99), New Orleans, Louisiana, September 21-24, 1999; и Z. Tang and J J. Garcia-Luna-Aceves, "Hop-Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networks", Proc. IEEE IC3N '98: Seventh International Conference on Computer Communications and Networks, Lafayette, Louisiana, October 12-15, 1998) описаны зависящие от топологии протоколы установления очередности передачи, в которых узел сети получает график очередности передачи, позволяющий узлу сети осуществлять передачу без помех со стороны тех узлов сети, которые отстоят от него самого на расстояние одного или двух участков ретрансляционного переприема на пути следования сообщения, и обеспечивающий увеличение коэффициента повторного использования канала по мере уменьшения количества соседних узлов по отношению к каждому узлу сети. В этих протоколах необходима взаимная конкуренция узлов сети для резервирования временных интервалов без возникновения конфликтных ситуаций, и эта конкуренция обеспечивается для каждого временного подинтервала. Кроме того, в них предполагается наличие возможности разделения каждого временного интервала на несколько временных подинтервалов. Все это ограничивает минимальную возможную продолжительность временных интервалов. В настоящем изобретении отсутствует необходимость в подразделении временных интервалов на более мелкие подинтервалы и необходимость в том, чтобы узлы сети посылали ответы в соседние узлы быстрее, чем за время кадра.
Были предложены технические решения, основанные на способе МДВР и требующие наличия исходного не зависящего от топологии графика очередности передачи и последующего обмена информацией между узлами сети для согласования окончательного графика очередности передачи. В публикации I. Chlamtac, "Fair Algorithms for Maximal Link Activation in Multihop Radio Networks," IEEE Transactions on Communications, Vol. COM-35, no. 7, July, 1987 описан алгоритм на основе повторяющегося графика очередности передачи по каналу связи, который может быть приспособлен к требованиям информационного обмена после некоторого количества итераций по вышеупомянутому алгоритму. Алгоритм начинается с графика очередности передачи "в одном временном интервале по каждому каналу связи", например созданного путем выделения каждому узлу сети временного интервала для передачи согласно его идентификатору узла сети. При каждой итерации информация о графике очередности передачи и "маркер" установления очередности направляются вверх и вниз по дереву маршрутизации (созданному посредством ранее существовавших алгоритмов) для выделения дополнительных временных интервалов узлам сети или каналам связи в соответствии со степенью их неудовлетворенных потребностей в отношении потока информационного обмена. В публикации A. Ephremides, T. Truong, "Scheduling Broadcasts in Multihop Radio Networks," IEEE Transactions on Communications, Vol. COM-38, № 4, April, 1990 описан аналогичный алгоритм, в котором каждому узлу сети первоначально выделяется временной интервал, соответствующий его собственному идентификатору узла сети, а затем каждый узел сети использует выделенный ему временной интервал для передачи "скелетных" графиков очередности передачи в соседние по отношению к нему узлы. В течение следующих двух кадров (две итерации обмена информацией о графиках очередности передачи) и в соответствии с неизменными приоритетами узла сети узлы сети становятся способными осуществить захват имеющихся временных интервалов до тех пор, пока не будут захвачены все имеющиеся временные интервалы (то есть больше не останется временных интервалов, которые могут быть распределены без возникновения конфликтных ситуаций). Вследствие необходимости получения постоянных графиков очередности передачи, для чего требуется несколько сходящихся итераций, и того, чтобы размер кадра установления графика очередности соответствовал максимальному размеру сети, эти технические решения обеспечивают лишь ограниченную масштабируемость и ограниченную устойчивость к изменчивости или к иной динамике. В публикации C. D. Young, "USAP: A Unifying Dynamic Distributed Multichannel TDMA Slot Assignment Protocol," Proc. IEEE MILCOM 96 OCTOBER 1996 описано решение, в котором также требуется первоначальное выделение одного временного интервала для каждого узла сети с последующим согласованием пакетов установления очередности для распределения других временных интервалов. Однако первоначально выделенный временной интервал ограничен первым временным интервалом в каждом "кадре". Следовательно, временной интервал, выделенный каждому узлу сети, появляется через каждые N кадров, где N - максимальный размер сети. Вследствие этого данное техническое решение не обеспечивает масштабирование. К тому же, данное техническое решение обеспечивает лишь относительно медленную адаптацию к динамическим изменениям условий информационного обмена, поскольку узел сети должен находиться в режиме ожидания в течение N кадров до момента поступления из соседнего узла подтверждения предложенного добавления к графику очередности передачи.
Большую часть вышеописанных ограничений для протоколов УДС из известного уровня техники устраняют посредством протокола адаптивной линии связи, устойчивой к окружающим условиям/УДС (именуемого REALM), предложенного D. Beyer, J. J. Garcia-Luna-Aceves и C. Fullmer в заявке на патент США от 10 февраля 1999 года, зарегистрированной в реестре под номером 003867.P001, на «Адаптивный протокол связи для беспроводных сетей», используемого в совокупности с протоколом очередности передачи, устанавливаемой соседними узлами (именуемым NETS), предложенным J. J. Garcia-Luna-Aceves, D. Beyer и C. Fullmer в заявке на патент США от 15 октября 1999, зарегистрированной в реестре под номером 003867.P005 на «Протокол очередности передачи, устанавливаемой соседними узлами».
Протокол REALM представляет собой протокол УДС, обеспечивающий предотвращение конфликтных ситуаций без необходимости квитирования установления связи между отправителями и получателями. В протоколе REALM предполагают наличие синхронизированной сети связи, упорядоченной в виде временных кадров, разделенных на временные интервалы. Степень синхронизации, наличие которой предполагает протокол REALM, представляет собой синхронизацию того же самого типа, которая необходима в любой сети, в которой работают радиостанции со скачкообразным изменением частоты, например, предназначенные для работы в диапазонах частот, отведенных для промышленных, научных и медицинских целей, и серийно выпускаемые в настоящее время. Узел сети, работающий согласно протоколу REALM, должен иметь сведения об идентификаторах соседних по отношению к нему узлов, расположенных в пределах одного или двух участков ретрансляционного переприема, и о текущем моменте времени в сети (например, номер текущего кадра). Исходя из этой информации и вспомогательной информации, каждый узел сети осуществляет оценочное вычисление функции (например, хеш-функции), которая детерминировано определяет то, какой именно узел сети должен осуществить передачу в конкретный временной интервал кадра. Протокол REALM обеспечивает равноправие путем операции изменения приоритета, с которым заданный узел сети может осуществлять передачу во временном интервале кадра, которую выполняют в каждом кадре. Предотвращение конфликтных ситуаций обеспечено после того, как все узлы сети, расположенные по соседству с некоторым узлом сети в пределах двух участков ретрансляционного переприема, получают непротиворечивую информацию о соседних по отношению к ним узлах, поскольку все узлы сети используют одинаковый детерминированный алгоритм выбора "победителя", получившего заданный временной интервал.
В публикациях L. Bao and J J. Garcia-Luna-Aceves, "A New Approach to Channel Access Scheduling for Ad Hoc Networks," Proc. ACM MobiCom 2001-Seventh Annual International Conference on Mobile Computing and networking, July 16-21, 2001, Rome, Italy; L. Bao and J J. Garcia-Luna-Aceves, "Channel Access Scheduling in Ad Hoc Networks with Unidirectional Links," Proc. ACM DialM 2001 - Fifth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, July 21, 2001 Rome, Italy; L. Bao and J J. Garcia-Luna-Aceves, "A New Collision-Free Medium Access Control Protocol" Proc. IEEE MILCOM 2000, Los Angeles, California, October 22-25, 2000 описаны алгоритмы доступа к каналу, обеспечивающие предотвращение возникновения конфликтных ситуаций без необходимости осуществлять особое квитирование установления связи между отправителем и получателем способом, аналогичным протоколу REALM. Эти алгоритмы требуют, чтобы каждый узел сети имел идентификаторы всех узлов сети, расположенных в пределах двух участков ретрансляционного переприема, и присваивают узлу сети приоритет передачи, действующий в течение заданного временного интервала, исходя из этой информации о соседних узлах. Предполагают, что распространение информации о соседних узлах осуществляется с использованием произвольного алгоритма.
Ограничения при использовании самого протокола REALM или алгоритмов, предложенных ВаО и Garcia-Luna-Aceves, состоят в том, что эти технические решения основаны на том, что все соседние узлы сети, расположенные в пределах двух участков ретрансляционного переприема, являются конкурирующими за право на передачу в каждом временном интервале кадра, предназначенного для такого типа бесконфликтного доступа. Более эффективное использование канала связи может быть достигнуто в том случае, когда те узлы сети, которые были способны осуществлять передачу в течение предшествующего кадра, уведомляют соседние по отношению к ним узлы о том, что они не будут вести конкурентную борьбу за временные интервалы передачи в течение некоторого промежутка время, что фактически ослабляет конкуренцию между узлами сети и уменьшает задержку доступа к каналу связи для конкретного узла сети.
СУЩНОСТЬ ИЗОБРЕТЕНИЯ
Настоящее изобретение направлено на преодоление вышеупомянутых недостатков, затруднений и проблем и поясняется в приведенном описании.
В настоящем изобретении предложен протокол управления доступом к среде передачи, УДС (MAC), обеспечивающий бесконфликтную передачу пакетов в канал связи, при этом выделение временных интервалов узлам сети для обеспечения бесконфликтной передачи осуществляют на основании получаемой ими информации о соседних узлах, образующих их локальную окрестность, и об объявленных временных интервалах, в течение которых соседние узлы, расположенные в локальной окрестности, будут снова пытаться осуществить передачу.
Согласно одному из аспектов настоящего изобретения, в процедуре установления очередности могут быть использованы данные о "сроке пребывания в сети" вместе с уникальными идентификаторами, поставленными в соответствие узлам сети.
Согласно другому аспекту настоящего изобретения, определяют возможные значения времени передачи для каждого узла сети с использованием перечня значений времени последующих передач, объявленных другими узлами сети. Узел сети изымает объявленные значения времени передачи из перечня потенциально возможных значений времени передачи и вычисляет свои собственные возможные значения времени передачи с использованием функции, обеспечивающей различное (псевдослучайное) распределение выходных данных для различных наборов входных данных. Эта функция может представлять собой хеш-функцию, функцию шифрования или функцию таблицы перекодировки. Вычисление возможных значений времени передачи осуществляют с использованием идентификаторов тех узлов сети, для которых не были получены сведения об объявленном времени передачи.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
На Фиг. 1 показана сеть произвольной структуры, в которой может функционировать настоящее изобретение;
на Фиг. 2 показан приведенный в качестве примера кадр, состоящий из временных интервалов, выделенных для Интернет-радиостанций (ИР) A-E;
на Фиг. 3 показана процедура, используемая для выбора перечня физических соседей, передаваемого в сжатом виде в разделе информации о соседних узлах пакета данных о конфигурации сети;
на Фиг. 4 показана процедура установления очередности передачи;
на Фиг. 5 показана процедура выбора базисной окрестности;
на Фиг. 6 показана процедура передачи данных о конфигурации сети;
на Фиг. 7 показана процедура приема пакета данных о конфигурации сети из соседнего узла;
на Фиг. 8 показана процедура "устаревания" физического соседнего узла;
на Фиг. 9 показано содержимое пакета данных о конфигурации сети согласно настоящему изобретению.
ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНОГО ВАРИАНТА
ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ
В приведенном подробном описании вариантов осуществления настоящего изобретения, которые приведены в качестве примеров, делаются ссылки на чертежи, являющиеся частью описания и иллюстрируют примерные варианты осуществления настоящего изобретения, которые могут быть реализованы на практике. Каждый вариант осуществления изобретения описан достаточно подробно, что предоставляет специалистам в данной области техники возможность практической реализации настоящего изобретения и следует понимать, что могут быть использованы и иные варианты его осуществления, а также могут быть выполнены другие его изменения без отклонения от сущности или объема настоящего изобретения. Следовательно, приведенное подробное описание не следует рассматривать как ограничивающее, а объем настоящего изобретения определяется только приложенной формулой изобретения.
Приведенные термины во всем описании и во всей формуле изобретения имеют те значения, которые поставлены им здесь в соответствие в явном виде, если в контексте явно не указано иное. На всех чертежах одинаковыми номерами позиций обозначены одинаковые узлы. Кроме того, ссылка на единственное число содержит ссылку на множественное число, если не указано иное или если это не противоречит раскрытию сущности изобретения.
Ниже приведено описание системы и способа установления очередности передач в сетях произвольной структуры. В приведенном описании многочисленные конкретные подробности изложены для того, чтобы обеспечить доскональное понимание настоящего изобретения. Однако для специалистов в данной области техники очевидно, что эти конкретные подробности не обязательно следует использовать для практической реализации настоящего изобретения. В иных случаях, подробное описание известных устройств и схем не приведено во избежание излишнего затруднения понимания настоящего изобретения.
В кратком изложении, настоящее изобретение направлено на создание протокола управлением доступом к среде передачи (УДС), служащего для обеспечения бесконфликтной передачи пакетов в канал связи, при этом выделение временных интервалов узлам сети для обеспечения бесконфликтной передачи осуществляют на основании получаемой ими информации о соседних узлах, образующих их локальную окрестность, и об объявленных временных интервалах, в течение которых соседние узлы, расположенные в локальной окрестности, будут снова пытаться осуществить передачу.
I. ОПРЕДЕЛЕНИЯ, БАЗОВЫЕ УСЛУГИ И ДОПУЩЕНИЯ
Рассмотренные в описании устройства радиосвязи, используемые в сети связи, являются полудуплексными и в конкретный момент времени настроены на один канал, хотя устройства радиосвязи могут быть переключены на любой из имеющихся каналов. Подобно предшествующим протоколам УДС, основанным на установлении очередности передачи, в настоящем изобретении предполагается, что время разделено на временные интервалы и что временные интервалы сгруппированы в виде кадров. Кадры дополнительно упорядочены в виде "сверхкадров". Однако следует обратить внимание на то, что даже для тех протоколов, которые основаны на предотвращении конфликтных ситуаций (например, для протокола стандарта IEEE 802.11), может потребоваться разделение времени на временные интервалы и упорядочение в виде кадров, что зависит от устройств радиосвязи, используемых в сети. Это имеет место для устройств радиосвязи со скачкообразным изменением частоты, поскольку все устройства радиосвязи должны согласовать начальные моменты времени скачкообразных изменений частоты и длину последовательности скачкообразного изменения.
В настоящем изобретении основное внимание сосредоточено на выделении временных интервалов для широковещательных передач по общему каналу таким образом, чтобы узлы сети могли осуществлять передачу управляющих пакетов, используемых для установления графиков очередности передачи, по множеству каналов передачи данных или в виде пакетов данных. Настоящее изобретение предполагает наличие двунаправленных физических каналов передачи данных между соседними узлами сети; это также справедливо и для протоколов УДС, обеспечивающих предотвращение конфликтных ситуаций.
В одном из вариантов осуществления настоящего изобретения временные интервалы идентифицируются с использованием уникального идентификатора, определяющего положение временного интервала в кадре и положение кадра в сверхкадре. Сверхкадр может быть идентифицирован с использованием текущего времени, согласованного между узлами сети посредством алгоритма временной синхронизации. В описании настоящего изобретения термином "идентификатор временного интервала" обозначен идентификатор временного интервала, основанный на «возрасте сети». Каждый сверхкадр содержит фиксированное количество кадров, а каждый кадр содержит фиксированное количество временных интервалов.
Узлы сети, выполняющие способ, описанный в настоящем изобретении, определяются как устройства радиосвязи протокола Интернет или Интернет-радиостанциями (ИР). Используемые в описании настоящего изобретения термины "узел сети" и "Интернет-радиостанция" являются взаимозаменяемыми.
В одном из вариантов осуществления настоящего изобретения узел сети идентифицирует каждый из узлов, являющихся соседними по отношению к этому узлу сети, с использованием присвоенного передатчику идентификатора локальной линии связи, который обозначен здесь как XLID. В другом варианте осуществления настоящего изобретения узлы могут идентифицироваться их адресами УДС (MAC-адресами). В представленном здесь описании настоящего изобретения для обозначения как идентификаторов XLID, так и адресов УДС (MAC-адресов) узлов сети, использован термин "идентификатор узла". Протокол АТОМ работает корректно с обоими типами идентификаторов узлов. Каждый узел может иметь вплоть до максимального количества активных соседних узлов, расположенных в пределах одного участка ретрансляционного переприема. Каждому активному соседнему узлу, расположенному в пределах одного участка ретрансляционного переприема, присвоен идентификатор узла и предполагается, что узел присваивает последовательные идентификаторы узлов активным соседним узлам. Присвоение идентификатора узла соседнему узлу осуществляют способом, не входящим в объем настоящего изобретения.
На Фиг. 1 показан пример сети произвольной структуры, в которой может функционировать настоящее изобретение. Сеть произвольной структуры состоит из нескольких подсетей 20, 30, 40 и 50, которые обеспечивают продление сети Интернет через несколько ИР (100, 110, 120, 130, 140, 150, 160, 170 и 180). Каждая ИР 100-180 представляет собой беспроводной маршрутизатор с IP-адресом и адресом УДС (MAC-адресом). Сеть 20 произвольной структуры соединена с сетью 900 Интернет через ИР 110 точки доступа. ИР 110 соединена с маршрутизатором 200 сети Интернет через локальную сеть 40.
По истечении конечного промежутка времени ИР (100-180), находящиеся в сети 20 произвольной структуры, имеют одинаковый перечень ИР, имеющихся в сети. Другими словами, ИР имеют сведения о соседних по отношению к ним узлах.
Согласно одному из вариантов осуществления настоящего изобретения каждая ИР имеет сведения об уникальных идентификаторах узлов, которыми являются ИР, отстоящие от нее на заранее заданное количество участков ретрансляционного переприема и образующие соседнюю с ней окрестность. Например, ИР могут иметь сведения о соседних по отношению к ним узлах, отстоящих от нее на расстоянии одного, двух, трех или более участков ретрансляционного переприема. Согласно одному из вариантов осуществления настоящего изобретения ИР получает сведения о наличии непосредственно соседствующих с ней узлов (в пределах одного участка ретрансляционного переприема) посредством протокола обнаружения соседних узлов и управления ими, возможно, в совокупности с использованием управляющих пакетов. Получение сведений о соседних узлах, расположенных на расстоянии двух участков ретрансляционного переприема и о соседних узлах, отстоящих от данного узла на расстояние большее, чем два участка ретрансляционного переприема, осуществляют посредством управляющих пакетов.
Для передачи информации о маршрутизации по сети произвольной структуры могут быть использованы различные протоколы.
II. ОБМЕН И СОХРАНЕНИЕ ИНФОРМАЦИИ
На Фиг. 2 показан пример кадра, содержащего временные интервалы, выделенные для ИР A-E в соответствии с настоящим изобретением. Как показано на чертеже, кадр 230 содержит временные интервалы 220 (s0-s11). Каждый временной интервал (См. 220) выделен для соответствующей ИР. В иллюстративных целях ИР A-F размещены по порядку под временными интервалами s0-s11. Временные интервалы ИР A-F выделяются таким образом, чтобы предотвратить возникновение конфликтных ситуаций. ИР в сети являются синхронизированными и согласовывают промежутки времени, именуемые "кадрами", в пределах которых будет установлена очередность передачи пакетов (например, управляющих пакетов). Каждому кадру поставлен в соответствие "возраст сети" (NetAge), который изменяется от кадра к кадру и является известным во всей сети. Например, сеть может быть синхронизирована по сверхкадрам, кадрам и временными интервалам, при этом каждый кадр содержит постоянное целое число (S) временных интервалов, а каждый сверхкадр содержит постоянное целое число (F) кадров. В каждом сверхкадре кадры последовательно пронумерованы с 1 до F ("номер кадра"). Сверхкадры также являются последовательно пронумерованными, в конечном счете, после E сверхкадров возвращаются обратно к сверхкадру номер 1. Вышеуказанный параметр "возраст сети" может представлять собой либо номер кадра, связанный с номером сверхкадра, либо просто лишь номер кадра в том случае, если количество кадров в сверхкадре является достаточно большим.
В описании настоящего изобретения управляющие пакеты, обмен которыми осуществляют между узлами, именуют "пакетами данных о конфигурации сети".
Согласно одному из вариантов осуществления настоящего изобретения каждый узел хранит перечень соседних узлов, находящихся в физической окрестности, каждая запись которого содержит следующие поля:
Адрес - 32-разрядный адрес УДС (MAC-адрес)
Расстояние - указано расстояние от данного узла до этого соседнего узла, выраженное через количество участков ретрансляционного переприема. Если за последнее время был успешно принят пакет, поступивший из этого соседнего узла (что более подробно описано ниже), то полагают, что он находится на расстоянии, равном одному участку ретрансляционного переприема.
Идентификатор узла - номер (или набор чисел), используемый для более эффективной идентификации этого узла сети в пакетах данных о конфигурации сети. Для непосредственно соседних узлов (находящихся на расстоянии, равном одному участку ретрансляционного переприема):
Идентификатор соседнего узла (Nbr ID) - номер, указывающий номер соседнего узла, который данный узел присвоил этому соседнему узлу.
Для узлов, не являющихся непосредственно соседними, которые находятся на расстоянии, равном двум участкам ретрансляционного переприема:
Идентификатор сообщившего узла (Rep ID) - номер, указывающий соседний узел, сообщивший об этом соседнем узле, находящемся на расстоянии, равном двум участкам ретрансляционного переприема.
Идентификатор узла, являющегося соседним по отношению к сообщившему узлу (Rep Nbr ID) - идентификатор соседнего узла (Nbr ID), используемый непосредственно соседним узлом (передавшим сообщение) для распознавания этого соседнего узла, находящегося на расстоянии, равном двум участкам ретрансляционного переприема.
Для узлов, не являющихся непосредственно соседними, которые находятся на расстоянии, равном трем участкам ретрансляционного переприема (если поддерживается эта возможность):
Идентификатор сообщившего узла (Rep ID) - номер, указывающий соседний узел, сообщивший об этом соседнем узле, находящемся на расстоянии, равном трем участкам ретрансляционного переприема.
Идентификатор узла, передавшего сообщение в сообщивший узел (Rep Rep ID) - идентификатор соседнего узла (Nbr ID), используемый соседним узлом, передавшим сообщение, для распознавания соседнего по отношению к нему узла, сообщившего ему об этом соседнем узле, находящемся на расстоянии, равном трем участкам ретрансляционного переприема.
Идентификатор узла сети, являющегося соседним по отношению к узлу, передавшему сообщение в сообщивший узел (Rep Rep Nbr ID) - идентификатор соседнего узла (Nbr ID), используемый непосредственно соседним узлом для идентификации этого соседнего узла, находящегося на расстоянии, равном трем участкам ретрансляционного переприема.
Время задержки передачи (Xmt Holdoff Time) - минимальное количество кадров между передачами пакета данных о конфигурации сети этим узлом сети. Узел может увеличить это время задержки и начать передачу сообщения об увеличенном количестве кадров. Для уменьшения времени задержки он должен сначала объявить о новом времени задержки в течение заданного количества кадров, а в это время использовать старое время задержки перед переключением на уменьшенное время.
Время следующей передачи (Next Xmt Time) - номер кадра и временного интервала, до которого этот узел гарантированно не будет осуществлять передачу пакета данных о конфигурации сети. Исходным значением этого параметра является NEXT_XMT_TIME_NOW (временем следующей передачи является текущий момент времени). Поскольку параметр "время следующей передачи (Next Xmt Time)" является частью процедуры "устаревания" и для предотвращения проблем возникновения "поворота в обратном направлении" этот параметр также возвращают в исходное состояние, равное этому значению, всякий раз, когда сумма этого времени следующей передачи (Next Xmt Time) и времени задержки передачи (Xmt Holdoff Time) для узла сети является равной или меньшей, чем текущее время.
Флаг переданного сообщения (Reported Flag) - его значение устанавливают как "ИСТИННОЕ" в том случае, если сообщение об этом времени следующей передачи (Next Xmt Time) было передано этим узлом в пакете данных о конфигурации сети, в противном случае его значение устанавливают как "ЛОЖНОЕ".
СОДЕРЖИМОЕ ПАКЕТА ДАННЫХ О КОНФИГУРАЦИИ СЕТИ
На Фиг. 9 показано содержимое пакета данных о конфигурации сети согласно одному из вариантов осуществления настоящего изобретения.
В поле 901 "Тип управляющего сообщения" указан тип сообщения.
NumNbrEntries 902 - количество соседних узлов, данные о которых переданы в сообщении. Количеством соседних узлов, данные о которых переданы в сообщении, может являться часть полного набора соседних узлов, известных данному узлу. Узел может сообщить о дальнейших подмножествах соседних узлов в передаваемых им последующих сообщениях о конфигурации сети.
NumBSEntries 903 - количество соседних БС (базовых станций) ячеек, данные о которых переданы в этом сообщении.
Поле 904 "Флаг внедренного пакета" указывает наличие пакета, внедренного в пакет данных о конфигурации сети.
В поле 905 "Мощность передачи" (Xmt Power) указана мощность передачи, которую изменяют ступенчато на 2 дБ мВт, начиная с 8 дБ мВт (то есть значение 1111 означает 38 дБ мВт).
В поле 906 "Передающая антенна" (Xmt Antenna) указана логическая антенна, используемая для передачи этого сообщения. Это позволяет адаптивным антенным системам (ААС) обеспечивать поддержку вплоть до 8 направлений антенн.
В поле 907 "Флаг адреса УДС (MAC-адреса) точки входа в сеть" (NetEntry MAC Address Flag) указано, присутствует ли этот элемент данных или нет.
В поле 908 "Основной канал сети" указаны данные об основном канале, используемом в сети этого узла, которые представляют собой логический номер физического канала, используемого для широковещательной передачи управляющей информации об установлении очередности передачи. Соответствие между подмножеством возможных номеров физических каналов и логическими каналами отображено в дескрипторе сети.
Поле 909 "Зарезервировано" является зарезервированным.
Поле 910 "Отсчет пакетов данных о конфигурации сети" (Netconfig count) представляет собой счетчик пакетов данных о конфигурации сети, переданных этим узлом.
Поле 911 "Отметка времени" (Timestamp) используется соседними узлами для обнаружения пропущенных передач. Этот отсчет увеличивается на 1 для каждой передачи данных о конфигурации сети, осуществляемой этим узлом. Отсчет шагов синхронизации используется для определения преимущественного права узлов на передачу при синхронизации сети. Узлам может быть присвоено право быть хранителями главного временного кода, синхронизацию которых осуществляют извне (например, с использованием глобальной системы определения местоположения (GPS)). Эти узлы сети передают отсчет шагов синхронизации, равном 0. Узлы синхронизируются с узлами, имеющими меньший отсчет шагов синхронизации, а если эти отсчеты являются одинаковыми, то с узлом, имеющим более низкое значение идентификатора узла.
Поле 912 "Информация об очередности передачи данных о конфигурации сети" (Netconfig schedule info) используется для хранения параметров "Mx следующей передачи" (Next Xmt Mx) и "экспонента задержки передачи" (Xmt Holdoff Exponent). Время задержки передачи (Xmt Holdoff Time) представляет собой количество возможностей передачи данных о конфигурации сети после времени следующей передачи (Next Xmt Time) (количество возможностей того, что этот узел не имеет право на передачу пакетов данных о конфигурации сети в каждом подкадре управления сетью связи, равно количеству узлов в конфигурации сети -1).
"Время задержки передачи" =2("экспонента задержки передачи"+4) (Xmt Holdoff Time=2(Xmt Holdoff Exponent+4)). Параметр "Mx следующей передачи" (Next Xmt Mx) содержит параметр "время следующей передачи" (Next Xmt Time), который представляет собой следующий промежуток времени, в котором этому соседнему узлу представлено право передачи данных о конфигурации сети, и его вычисляют как следующий интервал: 2"экспонента задержки передачи" * "Mx следующей передачи" < "время следующей передачи" < 2"экспонента задержки передачи" * ("Mx следующей передачи"+1), то есть 2Xmt Holdoff Exponent * Next Xmt Mx < Next Xmt Time < 2Xmt Holdoff Exponent * (Next Xmt Mx+1).
Например, если параметр "Mx следующей передачи"=3 (Next Xmt Mx=3), а параметр "экспонента задержки передачи"=4 (Xmt Holdoff Exponent=4), то узел рассматривается как имеющий право на следующую передачу данных о конфигурации сети между 49 и 64 возможностями передачи (что обусловлено степенью детализации) и не имеющий права на ее осуществление до этого времени. Если в поле "Mx следующей передачи" (Next Xmt Mx) установлено значение 0x1F (все единицы), то соседний узел рассматривается как имеющий право осуществлять передачу с момента времени, указанного этим значением, и при каждой последующей возможности передачи данных о конфигурации сети после этого (то есть, полагают, что время задержки передачи=0 (Xmt Holdoff Time=0)).
В поле 913 "Адрес УДС (MAC-адрес) точки входа в сеть" (NetEntry MAC Address) указано наличие или факт поддержки нового узла. Идентификатор узла БС (BS) представляет собой идентификатор узла БС ячейки, о наличии которого указано в переданном сообщении.
В поле 914 "Количество участков ретрансляционного переприема" указано количество участков ретрансляционного переприема между узлом, из которого поступило сообщение, и узлом БС ячейки, о наличии которого указано в переданном сообщении.
В поле 915 показателя "Энергия передачи на бит" (Xmt energy/bit) указано значение энергии на бит, которое необходимо для достижения БС ячейки через этот узел. Значение энергии передачи на бит (Xmt energy/bit) вычисляется по формуле:
мВт*мкс (милливатт*микросекунда), где N - совокупность соседних узлов, сообщающих о наличии БС ячейки, а 
где PTx - мощность передачи в милливаттах (мВт) из i-того узла в j-тый узел, а 
- скорость передачи данных в мегабитах в секунду (Мбит/с) из i-того узла в j-тый узел. Ej - энергия передачи на бит (Xmt energy/bit), указанная в сообщении, поступившем из соседнего j-того узла. Указанный в сообщении показатель "энергия передачи на бит" (Xmt energy/bit) представляет собой вычисленное значение энергии передачи на бит (Xmt energy/bit), разделенное на величину 2(XmtEnergyUnitExponent-4). Параметр "XmtEnergyUnitExponent" ("экспонента единичной энергии передачи") представляет собой 4-битовое поле, информацию о котором передают в дескрипторе сети.
В поле 916 "Идентификатор соседнего узла" (Nbr node ID) указан идентификатор соседнего узла, сведения о котором содержатся в сообщении.
Согласно другому варианту осуществления настоящего изобретения пакет данных о конфигурации сети содержит следующую информацию:
Собственный адрес УДС (My MAC Adr) - 32-разрядный адрес УДС (являющийся частью заголовка TSync)
Время следующей передачи (Next Xmt Time) - время следующей собственной передачи (My Next Xmt Time)
Время задержки передачи (Xmt Holdoff Time) - время задержки собственной передачи (My Xmt Holdoff Time)
Каждый пакет данных о конфигурации сети также содержит перечень (длиной Y, подлежит определению) записей, содержащий описанные ниже поля. Согласно одному из вариантов осуществления настоящего изобретения выбор из этого перечня производится по круговой системе из соседних узлов, расположенных относительно данного узла на расстоянии, равном одному участку ретрансляционного переприема (а также из соседних узлов, расположенных на расстоянии, равном двум участкам ретрансляционного переприема, если используют режим установления очередности с учетом соседних узлов, расположенных в пределах трех участков ретрансляционного переприема). Выбор этого перечня может быть осуществлен и другими способами.
Адрес УДС соседнего узла(Nbr MAC Adr) - 32-разрядный адрес УДС (MAC-адрес).
Расстояние - (непосредственно) соседний узел, расположенный на расстоянии, равном одному участку ретрансляционного переприема, или соседний узел, расположенный на расстоянии, равном двум участкам ретрансляционного переприема.
Идентификатор узла - идентификатор соседнего узла (Nbr ID) либо (идентификатор соседнего узла (Nbr ID) и идентификатор узла, из которого поступило сообщение (Rep ID)).
Время следующей передачи (Next Xmt Time).
Время задержки передачи (Xmt Holdoff Time).
К тому же, каждый пакет данных о конфигурации сети содержит перечень (длиной Z, подлежит определению) записей, содержащий следующие поля, представленные в сжатом виде:
Расстояние - (непосредственно) соседний узел, расположенный на расстоянии, равном одному участку ретрансляционного переприема, или соседний узел, расположенный на расстоянии, равном двум участкам ретрансляционного переприема.
Идентификатор узла - идентификатор соседнего узла (Nbr ID) либо (идентификатор соседнего узла (Nbr ID) и идентификатор узла, из которого поступило сообщение (Rep ID)).
Время следующей передачи (Next Xmt Time).
Время задержки передачи (Xmt Holdoff Time).
На Фиг. 3 показана процедура, используемая для выбора перечня физических соседей, которым осуществляют передачу сообщения в представленном в сжатом виде разделе информации о соседних узлах пакета данных о конфигурации сети. После начального этапа логическая процедура переходит на этап 310, где исключаются соседние узлы, сообщенные в вышеописанном перечне, полученном по круговой системе. На этапе 320 исключают все записи соседних узлов, расположенных на расстоянии, равном трем участкам ретрансляционного переприема, в том случае, если установление очередности осуществляют в режиме, учитывающем два участка ретрансляционного переприема. Затем на этапе 330 исключают все записи соседних узлов, имеющие установленный "флаг переданного сообщения". Затем на этапе 340 оставшиеся записи соседних узлов упорядочивают по времени следующей передачи (Next Xmt Time) и в этом пакете данных о конфигурации сети передают сведения о Z записях с наиболее отдаленным временем следующей передачи (Next Xmt Time). В общем случае, получение сведений об узлах с наиболее отдаленным временем следующей передачи (Next Xmt Time) более важно, чем получение сведений об узлах с близким временем следующей передачи (Next Xmt Time), так как соседние будут иметь больше времени на использование этой информации, прежде чем она устареет. На этапе 350 после передачи пакета данных о конфигурации сети значение "флага переданного сообщения" для всех соседних узлов в любом из вышеуказанных перечней устанавливают как "ИСТИННОЕ". Затем процедура переходит к конечному этапу и возвращается к обработке других операций.
III. УСТАНОВЛЕНИЕ ОЧЕРЕДНОСТИ ПЕРЕДАЧИ
На Фиг. 4 показана процедура установления очередности передачи в соответствии с настоящим изобретением. В течение текущего времени передачи ("Xmt"), осуществляемой узлом (то есть, в течение временного интервала, в котором узел передает свой пакет данных о конфигурации сети), этот узел использует следующую процедуру для определения времени его следующей передачи (Next Xmt Time).
После начального этапа логическая процедура переходит на этап 410, где осуществляется упорядочение таблицы соседних физических узлов по отношению к времени следующей передачи. На этапе 420 для каждой записи из таблицы соседних узлов к указанному для узла времени следующей передачи (Next Xmt Time) добавляют соответствующее этому узлу время задержки передачи для получения наиболее раннего времени последующей передачи из этого узла. На этапе 430 процедура устанавливает параметр "временное значение времени передачи" (TempXmtTime) равным объявленной узлом сумме времени задержки передачи (Xmt Holdoff Time) и текущему значению времени передачи. На этапе 440 значение флага успешного выполнения устанавливается как ЛОЖНОЕ. На этапе 450 принятие решения определяет, является ли значение флага успешного выполнения ЛОЖНЫМ. Если это так, то процедура переходит к блоку 455, в котором в том случае, если значение параметра "временное значение времени передачи" (TempXmtTime) равно времени следующей передачи (Next Xmt Time) любого узла из перечня соседних физических узлов, то процедура устанавливает значение параметра "временное значение времени передачи" (TempXmtTime) соответствующим следующему кадру/временному интервалу пакета данных о конфигурации сети. В противном случае процедура переходит на этап 460, где определяются приемлемые конкурирующие узлы, которыми является множество всех узлов из перечня соседних физических узлов, для которых наиболее раннее время последующей передачи является равным или меньшим, чем "временное значение времени передачи" (TempXmtTime). На этапе 465 из этого множества приемлемых конкурирующих узлов осуществляется выбор соседних узлов с использованием параметра "временное значение времени передачи" (TempXmtTime) в качестве начального значения и адресов УДС (MAC-адресов) всех приемлемых конкурирующих узлов. После этого на этапе 470 определяется, является ли узел "победителем" в результате выбора. Если этот узел не является "победителем" в результате выбора соседних узлов, то процедура переходит на этап 475, где значение параметра "временное значение времени передачи" (TempXmtTime) для узла устанавливается соответствующим следующему кадру/временному интервалу пакета данных о конфигурации сети. В противном случае процедура переходит на этап 480, где значение флага успешного выполнения устанавливается как ИСТИННОЕ, после чего на этапе 485 время следующей передачи (Next Xmt Time) для узла устанавливается равным "временному значению времени передачи" (TempXmtTime).
В одном из вариантов осуществления настоящего изобретения выбор окрестности в вышеописанной процедуре осуществляется тем же самым способом, которым осуществляется выбор в протоколе REALM, раскрытом в совместно поданной заявке №09/248738 от 10 февраля 1999 года на "Протокол адаптивной связи для беспроводных сетей связи".
На Фиг. 5 показан процесс выбора базисной окрестности согласно настоящему изобретению. После начального этапа на этапе 510 каждый узел (i) вычисляет свой собственный возможный временной интервал передачи (CS(i)) в каждом кадре с использованием глобально-известной функции (SlotFunc), входными данными для которой являются "возраст сети" (NetAge) и идентификатор узла. Это может быть выражено в следующем виде: CS(i)=SlotFunc (идентификатор(i), возраст сети (NetAge)).
Затем на этапе 520 каждый узел вычисляет возможный временной интервал передачи для каждого из узлов (j), расположенных в его окрестности в пределах двух участков ретрансляционного переприема, с использованием их идентификаторов узла, глобально известного возраста сети и той же самой функции SlotFunc (CS(j)=SlotFunc (идентификатор (j), возраст сети (NetAge)).
Конечно же, CS(k) для каждого узла даст тот же самый результат вне зависимости от того, каким именно узлом выполнено вычисление (локальным узлом или одним из узлов, расположенных в его окрестности в пределах двух участков ретрансляционного переприема). Следовательно, каждый узел способен определить, какой из узлов, при их наличии, расположенных в его окрестности в пределах двух участков ретрансляционного переприема, совместно используют один и тот же возможный временной интервал для передачи. Идентификаторы этих узлов помещают в группу претендентов на этот кадр i-того узла (CG(i)) согласно следующему условию: CG(i)=(j: CS(i)=CS(j)).
Затем на этапе 530 каждый узел (i) вычисляет приоритет PR(j) каждого узла из его группы претендентов для определения того, какой именно узел из этих претендентов имеет преимущественный приоритет на использование этого кадра, что осуществляют с использованием идентификатора узла, номера кадра установления очередности и, возможно, но не обязательно, смещения приоритета (PB) узла, служащих в качестве входных данных для глобально известной функции установления приоритетов (PriorityFunc). Это может быть выражено следующим образом: PR(j)=PriorityFunc (идентификатор(j), возраст сети (NetAge))+PB(j). В результате применения функции установления приоритетов PriorityFunc (a, b) получают число, являющееся уникальным для каждых возможных входных данных "a". Если смещения приоритетов не используют, то значение PB(j) устанавливают равным 0.
На этапе 540 узел (i) сети рассматривается в качестве победителя в соперничестве в том случае, если значение PR(i) превышает любое значение PR(j) из группы претендентов или если значение PR(i) является одним из наибольших равных между собой значений, но являлось бы самым большим в том случае, если бы все смещения приоритетов были равны 0.
Узел (i) может осуществлять передачу в своем возможном временном интервале CS(i) передачи в текущем кадре в том случае, если он является "победителем" в своей группе претендентов и если значение его PR(i) равно или превышает величину параметра "пороговое значение приоритета" (PriorityThreshold). Затем процедура переходит на заключительный этап и возвращается к обработке других операций.
На Фиг. 6 показана процедура передачи данных о конфигурации сети согласно настоящему изобретению. Процедуру, показанную на Фиг. 6, система выполняет по достижении времени следующей передачи (Next Xmt Time) для данного узла.
После начального этапа процедура переходит на этап 610, где определяется время следующей передачи (Next Xmt Time) с использованием процедуры установления очередности передачи для узла (Xmit_Scheduling). Затем на этапе 615 для него определяется следующее время задержки (Next Holdoff Time) (функция, зависящая от объема его таблицы соседних физических узлов, с наличием некоторых вышеописанных ограничений на то, каким образом следует осуществлять обработку при его уменьшении). Затем на этапе 620 определяется установлен ли флаг "ПРОПУСК ЭТОЙ ПЕРЕДАЧИ ДАННЫХ О КОНФИГУРАЦИИ СЕТИ". В том случае, когда этот флаг установлен, процедура пропускает остальные операции и переходит к заключительному этапу, возвращаясь к обработке других операций. При переходе к этапу 625 процедура создает (как описано выше) пакет данных о конфигурации сети. Затем на этапе 630 значение "флага переданного сообщения" устанавливается как ИСТИНОЕ для всех записей о соседних узлах, сведения о которых сообщены либо в перечне, полученном по круговой системе, либо в перечне, представленном в сжатом виде. На этапе 635 осуществляется передача пакета данных о конфигурации сети в пределах границ соответствующего кадра/временного интервала.
На Фиг. 7 показана процедура получения пакета данных о конфигурации сети из соседнего узла согласно настоящему изобретению. После начального этапа процедура переходит на этап 710, где по мере необходимости осуществляется обновление данных о расстоянии до передающего узла таким образом, чтобы это расстояние было равно одному участку ретрансляционного переприема (непосредственно соседний узел). Затем на этапе 720 для каждого узла, о котором сообщены сведения, находящегося на расстоянии минимального количества участков ретрансляционного переприема от соседнего узла, обновляются данные о расстоянии до узлов, о которых поступили сведения, таким образом, чтобы это расстояние было равно 1 плюс то расстояние, которое указано в поступивших сообщениях. Затем на этапе 730 обновляется время следующей передачи (Next Xmt Time) и время задержки передачи (Xmt Holdoff Time) для передающего узла и всех тех узлов, о которых поступили сведения. Затем на этапе 740 устанавливается флаг "ПРОПУСК ЭТОЙ ПЕРЕДАЧИ ДАННЫХ О КОНФИГУРАЦИИ СЕТИ" (который был использован выше), если обнаружен соседний узел, о котором поступили сведения и для которого время следующей передачи (Next Xmt Time) совпадает с временем следующей передачи (Next Xmt Time) данного узла. Это может произойти из-за наличия переходного состояния при изменении топологии, обусловленном динамикой или подвижностью канала связи. Затем на этапе 750, если идентификатор узла для любого сообщенного узла в сжатом перечне соседних узлов не может быть преобразован в запись соседнего узла (с адресом УДС (MAC-адресом)) с использованием информации, содержащейся в таблице соседних физических узлов, то эта запись пропускается. На Фиг. 8 показана процедура устаревания соседнего физического узла согласно настоящему изобретению. Эта процедура выполняется периодически применительно к перечню соседних физических узлов. После начального этапа процедура переходит на этап 810, где для любых соседних узлов, для которых сумма времени следующей передачи (Next Xmt Time) и собственного времени задержки передачи (Xmt Holdoff Time) является равной или меньшей, чем текущее время, время следующей передачи (Next Xmt Time) устанавливается равным NEXT_XMT_TIME_NOW (временем следующей передачи является текущий момент времени). Затем на этапе 820 устанавливается исходное значение времени устаревания записи, равное текущему моменту времени. После этого на этапе 830 для любых соседних узлов, у которых временем следующей передачи является текущий момент времени (NEXT_XMT_TIME_NOW), а время устаревания (Aging Time) равно некоторому (подлежащему определению) времени в прошлом, расстояние до этих соседних узлов увеличивают на единицу. Затем на этапе 840 запись соседнего узла удаляется, если в результате увеличения расстояние возросло до трех участков ретрансляционного переприема (или до четырех участков ретрансляционного переприема в случае использования режима установления очередности с учетом трех участков ретрансляционного переприема). В противном случае процедура переходит на этапе 850, где снова устанавливается исходное значение времени устаревания записи, равное текущему моменту времени.
СПОСОБЫ СЖАТИЯ
В пакетах данных о конфигурации сети параметр "время следующей передачи" (Next Xmt Time) может быть сжат до 3-4 бит, в результате чего получают время следующей передачи (Next Xmt Time), округленное в меньшую сторону до границы некоторого полного блока (при этом каждый блок содержит несколько возможностей передачи данных о конфигурации сети). Может быть осуществлена дискретизация времени задержки передачи (Xmt Holdoff Time), возможно до 3 бит в диапазоне от 16 до 2048 кадров/временных интервалов с использованием следующей формулы:
Время задержки передачи=2(x +4) (или Xmt Holdoff Time=2(x +4))
Изложенное описание, приведенные примеры и данные обеспечивают полное описание реализации и использования изобретения. Поскольку может быть создано множество вариантов осуществления настоящего изобретения без изменения сущности и объема изобретения, то объем изобретения определяется приложенной формулой изобретения.
1. Система распределенного установления очередности передачи пакетов узлами сети произвольной структуры, содержащая сеть произвольной структуры, включающую в себя множество узлов, причем каждый узел сети содержит средство для формирования и хранения перечня соседнего окружения в виде набора структурированных элементов данных, относящихся к соседним узлам, причем каждый элемент данных содержит параметр, характеризующий время передачи, и средство для формирования и передачи управляющего пакета, причем управляющий пакет предназначен для передачи данным узлом, по меньшей мере, одному другому узлу в сети произвольной структуры в соответствии с упомянутым параметром, характеризующим время передачи.
2. Система по п.1, отличающаяся тем, что каждый узел дополнительно содержит средство сжатия, предназначенное для сжатия перечня соседнего окружения.
3. Система по п.1, отличающаяся тем, что управляющий пакет представляет собой пакет данных о конфигурации сети.
4. Система по п.1, отличающаяся тем, что параметр, характеризующий время передачи, представляет собой время задержки передачи.
5. Система по п.1, отличающаяся тем, что параметр, характеризующий время передачи, представляет собой время следующей передачи.
6. Система по п.1, отличающаяся тем, что параметр, характеризующий время передачи, содержит время задержки передачи и время следующей передачи.
7. Система по п.1, отличающаяся тем, что перечень соседнего окружения содержит флаг переданного сообщения, связанный с упомянутым параметром, характеризующим время передачи.
8. Способ распределенного установления очередности передачи пакетов узлами сети произвольной структуры, включающий в каждом узле сети произвольной структуры формирование и сохранение перечня соседнего окружения в виде набора структурированных элементов данных, относящихся к соответствующим соседним узлам, причем каждый упомянутый элемент данных содержит идентификатор узла и параметр, характеризующий время передачи, формирование управляющего пакета на основе информации в перечне соседнего окружения и передачу управляющего пакета, по меньшей мере, одному другому узлу в сети произвольной структуры в соответствии с упомянутым параметром, характеризующим время передачи.
9. Способ по п.8, отличающийся тем, что управляющий пакет представляет собой пакет данных о конфигурации сети для сети произвольной структуры.
10. Способ по п.8, отличающийся тем, что управляющий пакет содержит параметр, характеризующий расстояние от первого узла до, по меньшей мере, одного другого узла в сети произвольной структуры, идентификатор узла для упомянутого первого узла, время следующей передачи для передачи управляющего пакета первым узлом и время задержки передачи для задержки передачи управляющего пакета первым узлом.
11. Способ по п.8, отличающийся тем, что управляющий пакет имеет перестраиваемую конфигурацию.
12. Способ по п.8, отличающийся тем, что управляющий пакет является адаптивным.
13. Способ по п.10, отличающийся тем, что управляющий пакет дополнительно содержит адрес управления доступом к среде (МАС-адрес).
14. Способ по п.8, отличающийся тем, что информация перечня соседнего окружения дополнительно содержит флаг переданного сообщения, связанный с упомянутым параметром, характеризующим время передачи.
15. Способ по п.8, отличающийся тем, что упомянутым параметром, характеризующим время передачи, является время задержки передачи.
16. Способ по п.8, отличающийся тем, что упомянутым параметром, характеризующим время передачи, является время следующей передачи.
17. Способ по п.8, отличающийся тем, что упомянутый параметр, характеризующий время передачи, содержит время задержки передачи и время следующей передачи.
18. Способ сжатия множества элементов данных соседних узлов в перечне соседнего окружения, содержащемся в пакетах данных о конфигурации сети, передаваемых узлами сети произвольной структуры, включающий в себя формирование сжатого перечня соседнего окружения из множества элементов данных соседних узлов путем исключения элемента данных соседнего узла из перечня соседнего окружения, если элемент данных соседнего узла сообщен в перечне кругового опроса или если он относится к соседнему узлу, находящемуся на расстоянии трех участков ретрансляционного переприема, при работе в режиме установления очередности с учетом двух участков ретрансляционного переприема, или если для элемента данных соседнего узла установлен флаг переданного сообщения, и включения оставшихся не исключенными элементов данных соседних узлов в сжатый перечень соседнего окружения.
19. Способ по п.18, отличающийся тем, что после передачи пакета данных о конфигурации сети значение флага переданного сообщения устанавливают как "истинное".
20. Способ по п.18, отличающийся тем, что дополнительно включает упорядочение элементов данных соседних узлов в сжатом перечне соседнего окружения в соответствии с параметрами времени передачи для соседних узлов.
21. Способ передачи пакета данных о конфигурации сети от узла сети произвольной структуры, включающий определение для узла времени следующей передачи; определение для узла соответствующего времени задержки передачи; оценку состояния флага пропуска передачи, и если флаг пропуска передачи установлен, то формирование пакета данных о конфигурации сети, установку флага переданного сообщения, относящегося к элементу данных соседнего узла, в пакете данных о конфигурации сети, с учетом того, было ли передано сообщение об этом элементе данных соседнего узла, и передачу пакета данных о конфигурации сети.
22. Способ установления очередности передачи пакета данных о конфигурации сети узлом в сети произвольной структуры, включающий формирование перечня соседнего окружения в виде набора структурированных элементов данных, относящихся к соседним узлам, причем каждый упомянутый элемент данных включает в себя время следующей передачи и время задержки передачи в качестве параметров, характеризующих время передачи соответствующих соседних узлов, упорядочение элементов данных соседних узлов в перечне соседнего окружения согласно значениям времени следующей передачи, относящимся к соответствующим элементам данных соседних узлов; для каждого элемента данных соседнего узла вычисляют наиболее раннее время следующей передачи и устанавливают временное значение времени передачи равным сумме значений времени задержки передачи и текущего времени передачи; осуществление выбора соседнего окружения и установление очередности по времени следующей передачи, на основе результатов выбора соседнего окружения.
23. Способ по п.22, отличающийся тем, что вычисление наиболее раннего времени последующей передачи включает в себя суммирование упомянутого времени следующей передачи, соответствующего элементу данных соседнего узла, с временем задержки передачи, соответствующим элементу данных соседнего узла.
24. Способ по п.22, отличающийся тем, что упомянутый выбор соседнего окружения включает в себя определение приемлемых конкурирующих узлов сети, и если приемлемый конкурирующий узел сети не является "победителем" в результате операции выбора, то установление упомянутого временного значения времени передачи соответствующим следующему временному интервалу передачи данных о конфигурации сети.
25. Способ по п.24, отличающийся тем, что приемлемые конкурирующие узлы включают в себя те соседние узлы из перечня соседнего окружения, у которых наиболее раннее время последующей передачи равно или меньше, чем временное значение времени передачи.
26. Способ по п.25, отличающийся тем, что если временное значение времени передачи, соответствующее узлу, равно времени следующей передачи узла из перечня соседнего окружения, то временное значение времени передачи устанавливают соответствующим следующему временному интервалу передачи пакета данных о конфигурации сети.
