выбор маршрута в беспроводных сетях

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

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

2. Способ по п.1, в котором упомянутый этап ответа устанавливает временный маршрут между упомянутым узлом источника и упомянутым узлом назначения упомянутой беспроводной сети.

3. Способ по п.1, в котором упомянутой беспроводной сетью является беспроводная ячеистая сеть.

4. Способ по п.1, в котором упомянутое сообщение ответа маршрута упомянутого этапа приема передается в режиме одноадресной передачи в упомянутый узел источника.

5. Способ по п.1, в котором адрес упомянутого узла назначения является одним из адреса Интернет-протокола и адреса управления доступом к среде передачи.

6. Способ по п.1, в котором упомянутый узел назначения включает в себя узлы назначения, которые ассоциированы с одним из прокси и точки доступа.

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

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

9. Способ по п.2, в котором упомянутый временный маршрут доступен для передачи данных после приема упомянутого сообщения ответа маршрута посредством упомянутого узла источника.

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

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

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

13. Устройство по п.12, в котором упомянутое средство для ответа устанавливает временный маршрут между упомянутым узлом источника и упомянутым узлом назначения упомянутой беспроводной сети.

14. Устройство по п.12, в котором упомянутой беспроводной сетью является беспроводная ячеистая сеть.

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

16. Устройство по п.12, в котором адрес упомянутого узла назначения является одним из адреса Интернет-протокола и адреса управления доступом к среде передачи.

17. Устройство по п.12, в котором упомянутый узел назначения включает в себя узлы назначения, которые ассоциированы с одним из прокси и точки доступа.

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

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

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

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

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

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

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

25. Способ по п.23, в котором упомянутый этап ответа устанавливает временный маршрут между упомянутым узлом источника и упомянутым узлом назначения упомянутой беспроводной сети.

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

27. Способ по п.23, в котором упомянутой беспроводной сетью является беспроводная ячеистая сеть.

28. Способ по п.23, в котором упомянутое сообщение ответа маршрута упомянутого этапа ответа передается в режиме одноадресной передачи в упомянутый узел источника.

29. Способ по п.23, в котором адрес упомянутого узла назначения является одним из адреса Интернет-протокола и адреса управления доступом к среде передачи.

30. Способ по п.23, в котором упомянутый узел назначения включает в себя узлы назначения, которые ассоциированы с одним из прокси и точки доступа.

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

32. Способ по п.25, в котором упомянутый временный маршрут доступен для передачи данных после приема упомянутого сообщения ответа маршрута упомянутым узлом источника.

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

34. Устройство по п.33, дополнительно содержащее: средство для обновления упомянутого сообщения запроса маршрута; и средство для лавинообразной рассылки в упомянутую беспроводную сеть упомянутого сообщения запроса маршрута.

35. Устройство по п.33, в котором упомянутое средство для ответа устанавливает временный маршрут между упомянутым узлом источника и упомянутым узлом назначения упомянутой беспроводной сети.

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

37. Устройство по п.33, в котором упомянутой беспроводной сетью является беспроводная ячеистая сеть.

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

39. Устройство по п.33, в котором адрес упомянутого узла назначения является одним из адреса Интернет-протокола и адреса управления доступом к среде передачи.

40. Устройство по п.33, в котором упомянутый узел назначения включает в себя узлы назначения, которые ассоциированы с одним из прокси и точки доступа.

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

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

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

Область техники

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

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

Протоколы маршрутизации по требованию, например протокол маршрутизации с самоорганизующимся вектором расстояния по требованию (AODV), определенный рабочей группой MANET в IETF, использует механизм запросов маршрута и ответов маршрута, чтобы устанавливать маршруты между двумя узлами в беспроводных ячеистых/произвольно организующихся (ad hoc) сетях. Когда узел источника хочет передать пакеты/кадры данных в узел назначения, узел источника обнаруживает маршрут к месту назначения посредством широковещательной лавинообразной рассылки сообщения запроса маршрута (RREQ) по сети, если узел источника не имеет и требует действительного маршрута до узла назначения. Обратный маршрут назад к источнику создается посредством узлов в сети по мере того, как они принимают и перенаправляют RREQ. Когда узел принимает RREQ, принимающий узел отвечает на этот запрос посредством формирования сообщения ответа маршрута (RREP), если: (1) либо принимающий узел сам является назначением, (2) либо принимающий узел имеет действительный маршрут до узла назначения и флаг "только узел назначения" (D) в RREQ НЕ установлен. RREP посылается в режиме одноадресной передачи в узел источника посредством установленного обратного маршрута, и тем самым создается прямой маршрут к узлу назначения в промежуточных узлах и в конечном счете в узле источника. Установленные маршруты прекращаются с истечением срока, если они не используются в течение данного времени существования маршрута.

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

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

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

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

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

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

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

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

Фиг.1 - примерный формат сообщения RREQ.

Фиг.2 - схематичное представление беспроводной ячеистой сети в соответствии с принципами настоящего изобретения.

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

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

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

Фиг.6 - блок-схема узла в соответствии с принципами настоящего изобретения.

Подробное описание предпочтительных вариантов осуществления

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

Фиг.1 - это примерный формат сообщения RREQ, при этом возможны другие форматы. Сообщение RREQ содержит, например, адрес узла начала/источника, порядковый номер создателя, адрес узла назначения и порядковый номер назначения (или число назначений и список адресов назначений и их порядковых номеров), идентификатор RREQ, идентификатор сообщения, длину сообщения, время существования (TTL), число транзитных участков, метрику маршрутизации, флаги и другую информацию. Помимо флагов "только узел назначения" (D) и "добровольный RREP" (G), новый флаг, называемый флагом "промежуточный ответ" (IR) в данном документе, содержится в сообщении RREQ. Флаги D и G содержатся в качестве унаследованных от традиционного AODV. Эти два флага не устанавливаются/используются посредством узла источника и игнорируются промежуточными узлами и узлами назначения. Один альтернативный вариант осуществления заключается в том, что сообщение RREQ вообще не содержит флаги D и G. Если сообщение RREQ переносит список адресов назначения, то несколько флагов "промежуточный ответ" включаются в сообщение RREQ, каждый из которых соответствует адресу назначения. Когда узел источника хочет обнаружить маршрут к одному или более адресов назначения, он устанавливает флаг(и) "промежуточный ответ" (IR), соответствующий адресу(ам) назначения. Следует отметить, что адрес(а) узла назначения может быть адресом(ами) Интернет-протокола (IP) или адресом(ами) уровня 2 (управление доступом к среде передачи передачи, MAC). Чтобы адаптироваться к изменениям в состояниях сети и поддерживать маршрут с оптимальной метрикой между узлами, каждый активный узел источника факультативно может лавинообразно рассылать в беспроводную ячеистую/произвольно организующуюся сеть периодическое сообщение RREQ (обслуживающее RREQ) для адреса(ов) назначения, с которым(и) он осуществляет связь. Флаг IR в обслуживающем RREQ не установлен. Промежуточные узлы и узлы назначения обрабатывают обслуживающее RREQ в соответствии с теми же правилами, что и используемые для того, чтобы обрабатывать необслуживающее RREQ в фазе обнаружения.

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

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

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

На фиг.2 иллюстрируется лавинная рассылка в беспроводную ячеистую/произвольно организующуюся сеть сообщения запроса маршрута (RREQ) и промежуточный узел В с действительным маршрутом к узлу назначения Е, отвечающий на сообщение RREQ сообщением RREP. Рассмотрим пример, при котором узел источника А пытается обнаружить маршрут к узлу назначения Е. Узел источника А лавинообразно рассылает сообщения запроса маршрута (RREQ) с флагом IR, установленным в беспроводной ячеистой/произвольно организующейся сети. Допустим, что промежуточный узел В уже имеет действительный маршрут B-C-D-E к узлу назначения Е. Когда промежуточный узел В принимает RREQ, он создает обратный маршрут к узлу источника, от которого он принимает RREQ в качестве следующего транзитного участка (узла источника А) обратного маршрута/пути. Промежуточный узел В отвечает на RREQ RREP в режиме одноадресной передачи, поскольку он имеет действительный маршрут к назначению Е, и флаг IR в RREQ установлен.

RREP устанавливает прямой маршрут к узлу назначения Е в узле источника А. Как только узел источника А создает маршрут/путь к узлу назначения Е с помощью RREP от промежуточного узла В, узел источника А может начать передачу пакетов/кадров данных в узел назначения Е посредством маршрута A-B-C-D-E. Промежуточный узел В сбрасывает флаг IR в сообщении RREQ и отсылает его дальше. Причина сброса флага IR заключается в ограничении ответов на лавинную рассылку RREQ только первым промежуточным узлом с действительным путем к узлу назначения. Другие промежуточные узлы далее, к примеру, С и D, не должны отвечать на это RREQ с помощью RREP, поскольку флаг IR не установлен. Предположим, что промежуточные узлы F, G и Н не имеют действительных маршрутов к узлу назначения Е. Когда промежуточные узлы F, G и Н принимают лавинообразно разосланные сообщения RREQ, они создают обратный маршрут к узлу источника А с помощью узла, от которого каждый из промежуточных узлов F, G и Н принимает RREQ в качестве следующего транзитного участка обратного маршрута. Каждый из промежуточных узлов F, G и Н затем отсылает сообщения RREQ далее.

В этом примере узел назначения Е принимает две копии данного RREQ, каждая из которых проходит различный путь: A-B-C-D-E, A-F-G-H-E. При условии, что два RREQ достигли узла назначения Е в следующем порядке: A-B-C-D-E и затем A-F-G-H-E, узел назначения Е сначала создает маршрут к узлу источника А посредством промежуточного узла D, как только узел назначения Е принимает RREQ по маршруту/пути A-B-C-D-E. В этой точке обратный маршрут к узлу источника А установлен в промежуточных узлах В, С и D. Узел назначения Е отправляет RREP по маршруту E-D-C-B-A. RREP просто обновляет маршрут A-B-C-D-E. Если есть еще какой-либо узел(лы) назначения в списке назначения RREQ, например узел I, узел назначения Е удаляет себя из списка назначения и затем отсылает RREQ далее (к примеру, в узел I). Если нет другого узла(ов) назначения в списке назначения RREQ, то RREQ не отсылается.

На фиг.3 иллюстрируется беспроводная локальная ячеистая сеть, показывая, что узел назначения Е отвечает RREP (1) при приеме RREQ посредством A-B-C-D-E и передает новый RREP, (2) чтобы установить более оптимальный прямой маршрут/путь после приема RREQ посредством A-F-G-H-E. Когда узел назначения Е принимает RREQ, который прошел по A-F-G-H-E, узел назначения Е определяет то, что этот RREQ прошел по пути с более оптимальной метрикой к А, чем временная отсылка маршрута/пути A-B-C-D-E. Следовательно, узел назначения Е модифицирует/обновляет следующий транзитный участок от промежуточного узла D к промежуточному узлу Н и обновляет метрику. После этого узел назначения Е передает RREP в режиме одноадресной передачи обратно в узел источника А посредством промежуточного узла Н, а также обновляет и отсылает RREQ, если есть один или более других узлов назначения в списке назначения RREQ. RREP устанавливает маршрут к узлу источника А посредством промежуточных узлов Н, G и F. Когда узел источника А принимает этот RREP, он модифицирует/обновляет следующий транзитный участок для узла назначения Е от промежуточного узла В к промежуточному узлу F. Маршрут к узлу назначения Е изменяется на A-F-G-H-E.

На фиг.4 показана блок-схема последовательности операций обработки сообщения RREQ. Когда узел принимает сообщение RREQ, он сначала создает/устанавливает или обновляет обратный маршрут к предыдущему транзитному участку, от которого узел принял сообщение RREQ, при необходимости, на этапе 410. Промежуточный/принимающий узел далее может создавать или обновлять обратный маршрут к создателю RREQ следующим образом. Если обратный маршрут к создателю сообщения RREQ отсутствует в таблице маршрутизации или является недействительным на этапе 415 и 420, он создается или обновляется. Следующий транзит в таблице маршрутизации для обратного маршрута для создателя RREQ становится предыдущим транзитным участком (узлом, от которого принято сообщение RREQ). Если действительный обратный маршрут к создателю RREQ существует, порядковый номер источника в сообщении RREQ сравнивается с порядковым номером записи маршрута в таблице маршрутизации на этапе 425 для обратного маршрута. Если порядковый номер в сообщении RREQ старше, он отбрасывается, и дополнительная обработка не выполняется на этапе 445. В противном случае текущий обратный маршрут к создателю модифицируется, если новая метрика более оптимальная, чем метрика текущего маршрута к создателю в таблице маршрутизации на этапе 430. Новая метрика определяется как метрика в сообщении RREQ плюс связывающая метрика между узлом, от которого он принял сообщение RREQ, и собой. Если новая метрика не является более оптимальной, чем метрика текущего обратного маршрута в записи таблицы маршрутизации, но порядковый номер источника в RREQ больше (новее) порядкового номера в таблице маршрутизации для обратного маршрута на этапе 435, промежуточный узел проверяет то, поддерживаются ли факультативные функции обработки гистерезиса и кэширования маршрута кандидата с оптимальной метрикой посредством ячеистой сети, на этапе 450. Если эти факультативные функции обработки не поддерживаются, обратный маршрут к создателю RREQ обновляется на этапе 455. Когда обратный маршрут создан или модифицирован, порядковый номер в таблице маршрутизации для обратного маршрута установлен на порядковый номер источника в сообщении RREQ, следующий транзит становится узлом, от которого принято сообщение RREQ, метрика устанавливается на новую метрику, и число транзитных участков устанавливается равным на один больше числа транзитных участков в сообщении RREQ.

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

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

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

На фиг.5 представлена блок-схема последовательности операций, иллюстрирующая способ отсылки RREQ и формирования RREP по настоящему изобретению, в котором узел определяет то, является ли он узлом назначения, т.е. соответствует ли один или более адресов узла (self_addr) запрошенному адресу назначения в списке назначений сообщения RREQ rreq.dest, на этапе 505. Следует отметить, что сам узел может иметь несколько адресов или может выступать в качестве прокси (посредника) для других узлов. Например, узел может быть точкой доступа и формировать/управлять сообщениями маршрутизации от имени устаревших станций, связанных с ней (прокси для станций). Функциональность для этого случая аналогична ситуации, когда узел имеет несколько адресов. Адреса назначения связанных станций могут рассматриваться как адреса-псевдонимы для точки доступа. Узел - это узел назначения, если один или более адресов, указанных в списке назначений сообщения RREQ, принадлежит ему или одному из узлов, использующему его в качестве прокси. Когда узел принимает сообщение RREQ, в котором узел назначения является узлом, использующим его в качестве прокси, он должен обработать сообщение RREQ, как если бы адрес узла назначения был его адресом. Более того, узел может быть узлом назначения для запрошенных адресов в списке назначения сообщений RREQ, но промежуточным узлом для другого запрошенного адреса в списке назначения сообщений RREQ.

Если один или более адресов узла соответствует запрошенным адресам назначения в списке назначений сообщения RREQ, узел формирует и передает сообщение RREP в режиме одноадресной передачи создателю сообщения RREQ для этих совпадающих адресов назначения на этапе 510. Узел назначения удаляет собственный/используемый для прокси адрес(а) из списка назначения сообщений RREQ на этапе 515. После этого, если нет оставшихся запрошенных адресов в списке назначений сообщения RREQ на этапе 520, сообщение RREQ отбрасывается на этапе 525. Если узел не является узлом назначения для любого запрошенного адреса в списке назначений сообщения RREQ (505) или есть другие запрошенные адреса назначения в списке назначений сообщения RREQ, помимо адресов узла, т.е. если узел является промежуточным узлом для одного или более адресов в списке назначений сообщения RREQ, узел проверяет оставшиеся адреса в списке назначений сообщения RREQ следующим образом. Допустим, что rreq.dest[i] представляет (i+1)-й адрес в списке назначений сообщения RREQ. Узел инициализирует индекс (к примеру, i) на этапе 545 и проверяет rreq.dest[i], т.е. первый адрес в списке назначений сообщения RREQ, чтобы определить то, есть ли активный прямой маршрут к узлу назначения, представленному посредством rreq.dest [i], на этапе 550. Если промежуточный узел имеет активный маршрут к назначению, маршрут к узлу назначения является действительным (555), порядковый номер, по меньшей мере, такой большой, как указанный в исходном сообщении RREQ (560), и флаг "промежуточный ответ (IR)" задан (570), промежуточный узел формирует сообщение RREP для запрошенного адреса назначения на этапе 575 и передает сформированное сообщение RREP в режиме одноадресной передачи создателю сообщения RREQ по текущему обратному маршруту. Флаг IR для этого запрошенного назначения в сообщении RREQ сбрасывается на этапе 580. Узел увеличивает индекс (например, на один) и проверяет то, есть ли какие-либо дополнительные адреса в списке назначений сообщения RREQ, на этапе 590. Если есть какие-либо дополнительные адреса в списке назначений сообщения RREQ, то выполнение вышеописанного цикла повторяется начиная с этапа 550. Т.е. цикл повторяется, если сообщение RREP должно быть отправлено для следующего запрошенного назначения. Цикл повторяется до тех пор, пока все адреса в списке назначений сообщения RREQ не будут проверены.

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

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

Фиг.6 - это блок-схема, иллюстрирующая подробности узла 600 настоящего изобретения. Узел включает в себя модуль 605 измерения качества и нагрузки линии связи, модуль 610 вычисления метрик маршрутизации, модуль 615 выбора маршрута и модуль 620 связи. Модуль 605 измерения качества и нагрузки линии связи измеряет качество и нагрузку линии связи/канала с каждым из своих соседей. Он предоставляет результаты измерений в модуль 610 вычисления метрик маршрутизации, с тем чтобы модуль 610 вычисления метрик маршрутизации мог определить стоимость/метрику линии связи для каждого из своих соседей. Отметим, что узел может иметь несколько соседей, несколько радиоинтерфейсов и несколько физических/логических каналов/линий связи. Все из них должны быть измерены. Модуль 610 вычисления метрик маршрутизации каждого узла использует измерения, выполняемые посредством модуля измерения качества и нагрузки линии связи, наряду с другой информацией, чтобы вычислять метрику маршрутизации для каждого узла, с которым он осуществляет связь. Метрика маршрутизации обновляется периодически. Модуль 615 выбора маршрута определяет/выбирает маршрут/путь, чтобы отсылать/передавать данные в узел назначения, на основе вычисленных метрик маршрутизации. Модуль 615 выбора маршрута обменивается сообщениями управления маршрутизацией и данными с другими узлами в ячеистой сети посредством модуля 620 связи. Следует отметить, что узел может иметь один или более интерфейсов радиосвязи и других интерфейсов связи. Следует понимать, что модуль выбора маршрута может фактически быть составлен из нескольких меньших блоков или комбинирован с другими модулями, описываемыми в данном документе. Дополнительно следует понимать, что процессы, описанные в данном документе (особенно относительно фиг.3 и 4), могут быть программным обеспечением, аппаратными средствами, микропрограммным обеспечением или любой комбинацией вышеозначенного, приводимой в исполнение в или посредством модуля выбора маршрута.

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

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