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

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

Иллюстрации

Показать все

Реферат

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

ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ

Для сетей беспроводной связи было разработано множество протоколов управления доступом к среде передачи (УДС) (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-адресами). В представленном здесь описании настоящего изобрете