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

(51) 04 3/26 (2006.01) КОМИТЕТ ПО ПРАВАМ ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ МИНИСТЕРСТВА ЮСТИЦИИ РЕСПУБЛИКИ КАЗАХСТАН ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ИННОВАЦИОННОМУ ПАТЕНТУ следующего ретранслятора, который минимально удален от адреса назначения пакета, вычисляется процессором каждого принимающего ретранслятора, который по результатам непрерывного контроля пакетов, проходящих по каналу радиосети,формирует собственный динамически изменяющийся список адресов других ретрансляторов. Затем процессор строит математическую модель относительных позиций всех ретрансляторов,потенциально способных участвовать в процессе доставки пакета конечному адресату и, в результате анализа их позиций, определяет адрес следующего ретранслятора минимально удаленного от адреса назначения пакета. Предлагаемый способ позволяет сократить время доставки сообщений, уменьшить загруженность радиоканала, увеличить пропускную способность радиосети и надежность доставки сообщения,снизить затраты на обслуживание радиосети.(56) Предварительный патент РК 10964, кл. 04 3/26, 15.11.2001(54) СПОСОБ АДАПТИВНОЙ АВТОМАТИЧЕСКОЙ МАРШРУТИЗАЦИИ ПАКЕТОВ ДАННЫХ В РАДИОСЕТЯХ(57) Изобретение относится к технике радиосвязи, а именно к многоканальным системам передачи информации с временным и пространственным разделением каналов и может быть использовано для создания радиосетей передачи данных высокой надежности и минимальной загруженностью радиоканала связи. Адрес назначения пакета и адреса принимающего и передающего ретрансляторов содержатся в каждом пакете данных. Адрес 22321 Изобретение относится к технике радиосвязи, а именно к многоканальным системам передачи информации с временным и пространственным разделением каналов и может быть использовано для создания радиосетей передачи данных высокой надежности и минимальной загруженностью радиоканала связи. Известен способ маршрутизации пакетов данных(заявка РФ 95108549, МПК Н 04 В 7/26, публ. 10.02.97),в котором пакеты информации направляются по маршрутам, проходящим между узлами системы связи, использующей группу спутников с распределением их систематическим образом. Для каждого из узлов рекуррентным методом заранее составлены маршрутные таблицы,которые учитывают условия работы линий связи и ожидаемую их нагрузку для различных моментов времени и состояний группы спутников. Маршрутные таблицы составляются централизованно, после чего распределяются по спутниковым узлам и поддерживаются в них. Маршрутные таблицы регулярно обновляются с учетом ожидаемой радиообменной нагрузки и физических изменений в связности узлов в пределах всей группы спутников, обусловленных движением спутников. Кроме того, эти таблицы обновляются также с учетом изменений в связности всей сети,которые могут происходить из-за отказов перекрестных линий связи или спутниковых узлов. В этом способе маршруты передачи данных не вычисляются в узлах сети, а передаются им в виде обновляемых таблиц с наземной службы управления системой. Наиболее близким к изобретению по техническому решению является способ маршрутизации пакетов в радиосети (Патент РК 10964, МПК 04 3/26, публ. 15.11.2001, бюл. 11). В этом способе определение маршрутов пересылки пользовательских пакетов осуществляют в устройствах передачи информации (УПИ) с использованием данных об адресе назначения,содержащемся в пакете, без преобразования информации из одного стандарта адресации в другой. Информация о реальном адресе назначения передается только в первом пакете из серии пакетов сообщения. В состав УПИ введен модуль памяти для временного хранения транзитных сообщений. В этом техническом решении при передаче данных через сеть,расчет маршрутов осуществляется только на участках пути от одного промежуточного УПИ к другому ближайшему УПИ. Ретрансляция сообщений от одного УПИ к другому ближайшему УПИ неизбежно приведет к увеличению количества ретрансляций, загруженности радиоканала и увеличению времени доставки сообщения. Кроме того, в этом решении не раскрывается алгоритм вычисления маршрута, а только указывается на то, что на выбор маршрута может оказывать влияние пользователь (вероятно маршрут определяет оператор или клиент сети). Задачей предлагаемого изобретения является полная автоматизация доставки сообщений от источника к конечному адресату, с учетом 2 постоянно изменяющихся условий прохождения радиоволн и физического состояния аппаратуры точек доступа радиосети. Технический результат, достигаемый при использовании изобретения, -уменьшение времени доставки сообщения, уменьшение загруженности радиоканала, увеличение пропускной способности радиосети, увеличение надежности доставки сообщения, снижение затрат на обслуживание радиосети. Указанный технический результат достигается тем, что в способе адаптивной автоматической маршрутизации пакетов данных в радиосетях включающий определение маршрутов ретрансляции пакетов данных в устройствах передачи информации с использованием данных об адресе назначения содержащимся в пакете,при определении маршрутов ретрансляции пакетов данных между точками доступа радиосети используется информация об адресе назначения пакета, адресе принимающего ретранслятора и адресе передающего ретранслятора имеющихся в структуре каждого пакета данных и собственном адресе дислокации каждой точки доступа. Каждый адрес отражает реальные координаты точки доступа, которой этот адрес принадлежит в принятой системе координат. Определение маршрута выполняется процессором точки доступа,который имеет собственный список адресов других точек доступа, с которыми потенциально эта точка доступа может установить связь. Список формируется по результатам непрерывного анализа всех пакетов проходящих по радиосети и находящихся в зоне радио-слышимости этой точки доступа. Собственный список адресов и адреса входящие в структуру пакета предоставляет процессору исходную информацию при вычислении адреса ретранслятора минимально удаленного от конечного адреса назначения пакета. Каждая ТД (далее по тексту ТД) имеет уникальный адрес в радиосети, соответствующий реальным координатам ее дислокации в пределах одного кластера. Размер кластера и его единицы измерения определяются требованиями к поставленной задаче и ограничиваются только мощностью используемого процессора и выходной мощностью передающего тракта трансивера ТД. Каждая ТД имеет собственный список адресов других ТД, с которыми она потенциально установить соединение по радиоканалу. Список формируется по результатам непрерывного анализа всех пакетов данных, проходящих по радиоканалу сети в месте установки этой ТД. В случае обнаружения активности новой (еще незарегистрированной) ТД в список добавляется информация о ней (координаты, уровень несущей и т.д.) и в дальнейшем выполняется контроль активности этой ТД. Каждый пакет содержит информацию об адресе назначения Ае - (ТД для которой пакет предназначен), адресе ретранслятора А - (ТД которой предписывается выполнить ретрансляцию пакета), адресе отправителя- (ТД передающей пакет). Дополнительно в пакете присутствуют 22321 идентификатор принадлежности пакета к данной системе , номер пакета , директивы пакета, времени жизни пакета Тр, контрольной суммы пакетаи вложенного блока данных,подлежащего доставке по адресу назначения. Способ допускает применение других форматов пакета,использование алгоритмов защиты информации и повышения помехоустойчивости и произвольных алгоритмов кодирования данных. В данном случае рассматривается формат пакетов с необходимой достаточностью для реализации указанного способа маршрутизации. Каждая ТД во время и после приема любого пакета, выполняет контроль его целостности и, в случае его нарушения отклоняет принимаемый пакет, иначе проверяет свой список зарегистрированных адресов ТД и в случае отсутствия в списке принятого , регистрирует е адрес и другую информацию, связанную с этой ТД в списке и активизирует контроль активности этой ТД в радиосети. В дальнейшем, при обнаружении отсутствия активности зарегистрированной ТД,она будет удалена из списка. Затем проверяется директивасообщения и, еслипредписывает передачу пакета по конкретному адресу назначения, то проверяются адреса Ае и А на соответствие собственному адресуЕсли Ае и А не совпадают с собственным адресом, то прием пакета отклоняется.Если Ае и А совпадают с собственным адресом, то передающей стороне возвращается подтверждение о принятом пакете. Далее, для предотвращения приема повторных пакетов,выполняется поиск информации о таком пакете в динамическом стеке идентификаторов принятых пакетов. Если такой идентификатор найден, то прием пакета отклоняется, иначе идентификатор принятого пакета сохраняется в стеке, а блок данных инкапсулируется из сообщения и подвергается дальнейшей обработке. Для предотвращения длительной блокировки приема идентичных пакетов, время хранения информации в стеке о каждом принятом пакете ограничено.Если Ае не совпадает, а А совпадает с собственным адресом, то выполняется процедура поиска адреса А в списке адресов ТД минимально удаленного от адреса Ае. Поиск ретранслятора выполняется методом построения математической модели относительных позиций всех ТД, которые потенциально могут участвовать в процессе доставки пакета конечному адресату с последующим анализом полученной модели и выбором ретранслятора минимально удаленного от конечного адреса назначения пакета. Все представления о расстояниях в примененном способе выражаются длиной вектора между двумя точками в принятой системе координат 1. вычисляется- расстояние между передающей ТД и ТД с адресом назначения. 2. Вычисляется- собственное расстояние до ТД с адресом назначения. 3. Еслибольше или равно , то прием пакета отклоняется. 4. Иначе выполняется поиск ТД в списке адресов по следующему условию- расстояние между предполагаемым ретранслятором А и Ае должно иметь минимальное значение среди всех зарегистрированных в списке адресов и должно быть меньше . Это условие гарантирует, что пакет при каждой ретрансляции будет продвигаться только в сторону конечного адреса назначения и на максимально возможное расстояние. 5. Если результат поиска отрицательный, то прием пакета отклоняется иначе, для предотвращения приема повторных пакетов, выполняется поиск информации о таком пакете в динамическом стеке принятых пакетов. Если такая информация найдена, то прием пакета отклоняется, иначе информация о нем сохраняется в стеке, а передающей стороне возвращается подтверждение о принятом пакете. 6. Если в результате операций 15 прием пакета не был отклонен, то в принятом пакете адрес А заменяется на адрес ,адресна собственный адрес. Затем вычисляется новое значение контрольной суммы пакетаи инициализируется передача пакета в эфир.Начало передачи пакета контролируется процедурой устранения коллизий в радиоканале,определяющую очередность использования канала и предотвращающую одновременную передачу пакетов от двух и более ретрансляторов. После завершения передачи, передающая сторона в течение ограниченного интервала времени ожидает получение подтверждения на переданный пакет. Если подтверждение не будет получено после нескольких циклов передач, то текущий адрес А в списке помечается флагомкак недоступный- и выполняется контроль времени жизни пакета Тр. Если лимит Тр исчерпан, то передача пакета прекращается, а пакет уничтожается, иначе в списке адресов ТД выполняется поиск альтернативного ретранслятора А не имеющего флаг ,корректируетсяи передача в эфир возобновляется. В случае если все адреса в списке будут отмечены флагами , или будет получено подтверждение на переданный пакет, то у всех адресов в списке будут сняты флаги . Способ осуществляется следующим образом Выбранная территория кластера (совокупность программных и аппаратных средств,рассредоточенных на ограниченной территории и обеспечивающих выполнение общей задачи системы) разделяется некоторое количество сегментов, образованных наложенной на кластер координатной сеткой (Фиг.1). Точка доступа или ТД - устройство или интегрированный в устройство модуль,реализующая механизм доступа к сети кластера со стороны внешних (относительно сети) клиентов кластера. Точка доступа ТД и ретранслятор объединены в единую конструкцию и дополнены радиочастотным модулем,обеспечивающим физический доступ к радиосети кластера. В связи с этим далее по тексту термины ТД и ретранслятор следует считать синонимами. 3 22321 В каждом сегменте может быть размещена только одна ТД, при этом в память ТД передаются координаты сегмента (,), которому принадлежит ТД. Каждая ТД имеет сетевой адрес, который отражает реальные координаты ТД в кластере. Каждая ТД может выполнять функцию ретранслятора пакетов данных в радиосети кластера. Каждая ТД периодически передает в эфир короткие служебные пакеты, подтверждающие свою активность и в реальном времени постоянно анализирует эфир на предмет активности других ТД. Результат анализа формируется в список адресов ТД, с которыми данный ретранслятор потенциально может установить связь. Если ТД обнаруживает в эфире новую, еще незарегистрированную ТД, то ее адрес заносится в список, а в случае длительного отсутствия активности зарегистрированной в списке ТД, она удаляется из списка. Таким образом, список динамически корректируется в зависимости от условий прохождения радиоволн, на которые могут повлиять погодные условия или другие факторы и (или) техническое состояние других ТД. К пакету данных, подлежащим передаче в радиосети добавляется конечный адрес ТД назначения пакета и информация о времени жизни пакета. Далее, через связной интерфейс, пакет передается в ТД сети, которая является отправителем пакета, где полученный пакет монтируется в блок данных транспортного протокола в радиосети. Для обеспечения доставки пакета конечному адресату, транспортный протокол содержит следующие информационные поля Длина пакета , номер пакета(в системе счисления отправителя пакета), время жизни пакета Тр,адрес конечного получателя Ае,адрес ретранслятора А, адрес отправителя ,директива пакетаопределяющая структуру и назначение пакета, блок данных подлежащий доставке конечному адресату , и контрольная сумма . Содержание полей Ае, Тр,иопределяет клиент сети, а все остальные поля вычисляет процессор ТД. После получения пакета, подлежащего передаче по радиосети, процессор ТД в списке выполняется поиск зарегистрированных адресов ТД адрес ретранслятора с минимальным удалением от адреса назначения и находящегося ближе к адресу назначения, чем собственный адрес. Если результат поиска положительный,то клиенту сети возвращается подтверждение на передачу пакета,иначе возвращается отказ в выполнении операции с указанием причины, а пакет уничтожается. Если пакет принят к передаче, то процессор формирует пакет к передаче устанавливает А равным найденному адресу ретранслятора, устанавливает адресравным собственному адресу, определяет значения полейи , вычисляети передает пакет в эфир. Принимающая ТД анализирует адреса в принятом пакете на предмет необходимости его приема для клиента сети или дальнейшей ретрансляции по сети. Если адрес назначения совпадает с собственным адресом, то 4 процессор принимающей ТД инкапсулирует из пакета блок данных и передает его связной интерфейс конечному получателю, а передающей стороне возвращает подтверждение, при этом передающая сторона прекращает передачу. Если адрес назначения не совпадает с собственным адресом, то в списке выполняется поиск зарегистрированных адресов ТД адрес ретранслятора с минимальным удалением от адреса назначения и находящегося ближе к адресу назначения, чем собственный адрес. Если результат поиска положительный, то передающей стороне передается подтверждение, при этом передающая сторона прекращает передачу пакета,а принимающая ТД выполняет аналогичные процедуры по дальнейшей ретрансляции пакета по радиосети. Если результат поиска отрицательный,то прием пакета отклоняется, а передающей стороне подтверждение не передается, что вынуждает передающую сторону изменить адрес ретранслятора. Если передающей стороне не удается установить связь ни с одной из ТД, то в зависимости от затребованного времени жизни пакета он или уничтожается или формируется новый цикл передач. Пример реализации способа В этом примере рассмотрен способ передачи пакета отк Т ретрансляторы Аи В. Результат анализа списка адресов ТД ретранслятором(Фиг.2) В списке присутствуют только адреса ТД 25 и А. Из них ретрансляторами не могут быть ТД 2 и 3, потому что они находятся большем расстоянии от Т относительно . В качестве ретранслятора выбрана точка А, т.к. она находится ближе к точке Т чем точки 4 и 5. Если от точки А не будет получено подтверждение, то в следующем цикле передач, в порядке приоритетов, пакет будет переадресован сначала к точке 5, а затем к точке 4. Результат анализа списка адресов ТД ретранслятором А (Фиг.3) В списке присутствуют только адреса ТД 46 и В. Из них ретрансляторами не могут быть ТД 4,5 и , потому что они находятся большем расстоянии от Т относительно А. В качестве ретранслятора выбрана точка В, т.к. она находится ближе к точке Т чем точка 6. Если от точки В не будет получено подтверждение, то в следующем цикле передач, в порядке приоритетов, пакет будет переадресован к точке 6. Результат анализа списка адресов ТД ретранслятором В (Фиг.4) В списке присутствуют только адреса ТД 6,7, А и Т. Из них ретрансляторами не могут быть ТД 6,7 и А, потому что они находятся большем расстоянии от Т относительно В. В качестве ретранслятора выбрана точка Т, т.к. других вариантов нет. Результат анализа списка адресов ТД ретранслятором Т (Фиг.4) Пакет будет принят точкой Т т.к. е адрес совпадает с адресом назначения пакета. Визуальный анализ продвижения пакета (Фиг.4) показывает, что маршрутв приведенном 22321 примере действительно является оптимальным, как с точки зрения выбора направления движения пакета, так и результирующего количества его ретрансляций. В предлагаемом способе в качестве ретранслятора выбирается адрес точки доступа,которая находится в минимальном удалении от конечного адреса назначения пакета. Это позволяет значительно сократить число количество ретрансляций при доставке пакета конечному адресату, и уменьшить нагрузку на радиосеть. Предлагаемый способ динамического контроля активности точек доступа в радиосети, позволяет каждой точке доступа автоматически адаптироваться к изменяющимся условиям прохождения радиоволн и изменениям технических параметров других точек доступа. Примененный механизм смены адресов ретрансляторов значительно повышает надежность доставки пакетов конечному адресату как в случае аппаратной неисправности одной или нескольких точек доступа, так и при ухудшении прохождения радиоволн в кластере или в случае возникновения случайных или преднамеренных локальных помех на выделенных частотах радиосети. Полностью автоматизированный процесс определения маршрутов и адаптации к изменяющимся условиям прохождения радиоволн,снижает затраты на обслуживание радиосети. ФОРМУЛА ИЗОБРЕТЕНИЯ Способ адаптивной автоматической маршрутизации пакетов данных в радиосетях включающий определение маршрутов ретрансляции пакетов данных в устройствах передачи информации с использованием информации об адресе назначения содержащимся в пакете, отличающийся тем, что адрес назначения пакета и адреса принимающего и передающего ретрансляторов содержатся в каждом пакете данных, а адрес следующего ретранслятора,минимально удаленного от адреса назначения пакета,вычисляется процессором каждого принимающего ретранслятора,который по результатам непрерывного контроля пакетов,проходящих по каналу радиосети, формирует собственный динамически изменяющийся список адресов других ретрансляторов и строит математическую модель относительных позиций всех ретрансляторов, потенциально способных участвовать в процессе доставки пакета конечному адресату и, в результате анализа их позиций,определяет адрес следующего ретранслятора минимально удаленного от адреса назначения пакета.