BRPI0520882B1

BRPI0520882B1 - sistema para descobrir uma rota entre um nó de origem e um nó de destino em uma rede sem fio

Info

Publication number: BRPI0520882B1
Application number: BRPI0520882A
Authority: BR
Inventors: Liu Hang
Original assignee: Thomson Licensing
Priority date: 2005-11-09
Filing date: 2005-11-09
Publication date: 2018-11-27
Also published as: RU2682930C2; PL2296325T3; PL2296326T3; RU2017116747A3; EP2296325B1; BRPI0520670A2; US8064416B2; RU2010120573A; TW201001989A; KR20090116808A; US20090135824A1; BRPI0520873B1; TW200729836A; AU2005338057B2; KR101225274B1; KR20100103678A; CA2627432C; TWI430619B; PT1952588E; PH12012502208A1

Abstract

método e sistema para descobrir uma rota entre um nó de origem e um nó de destino em uma rede sem fio. são descritos um sistema e um método para descobrir uma rota entre um nó de origem e um nó de destino em uma rede sem fio que incluem configurar um sinalizador de resposta intermediário de uma mensagem de solicitação de rota através do nó de origem, inundando a rede sem fio com a mensagem de solicitação de rota e respondendo a esta com a mensagem de resposta de rota através de um primeiro nó intermediário que tem uma rota válida ao nó de destino. também são descritos um sistema e um método para descobrir uma melhor rota na qual a mensagem de resposta de rota torna-se uma mensagem de resposta de rota. o sistema e o método para descobrir uma melhor rota incluem selecionar através do destino na melhor rota entre ele mesmo e o nó de origem baseado em métricas acumulativas recebidas nas mensagens de solicitação de rota recebidas através do nó de destino, criar uma mensagem de resposta de rota adicional e transmitir a mensagem de resposta de rota adicional ao nó de origem.

Description

(54) Título: SISTEMA PARA DESCOBRIR UMA ROTA ENTRE UM NÓ DE ORIGEM E UM NÓ DE DESTINO EM UMA REDE SEM FIO (73) Titular: THOMSON LICENSING, Sociedade Francesa. Endereço: 46, Quai A. Le Gallo, F-92100, BoulogneBillancourt, FRANÇA(FR) (72) Inventor: HANG LIU.

Prazo de Validade: 10 (dez) anos contados a partir de 27/11/2018, observadas as condições legais

Expedida em: 27/11/2018

Assinado digitalmente por:

Alexandre Gomes Ciancio

Diretor Substituto de Patentes, Programas de Computador e Topografias de Circuitos Integrados “SISTEMA PARA DESCOBRIR UMA ROTA ENTRE UM NÓ DE ORIGEM E UM NÓ

DE DESTINO EM UMA REDE SEM FIO”

Dividido do pedido de patente de invenção PI 0520670-7, depositado em

09/11/2005.

Campo da Invenção

A presente invenção refere-se a redes sem fio e, em particular, a redes em malha sem fio. Mais especificamente a presente invenção refere-se ao processamento de mensagens de solicitação de rota em protocolos de roteamento sob demanda.

Fundamentos da Invenção

Os protocolos de roteamento sob demanda, por exemplo, o protocolo de roteamento de Vetor de Distância Sob Demanda Ad Hoc (AODV) definido pelo grupo de trabalho MANET no IETF, usam um mecanismo de Solicitação de Rota e de Resposta de Rota para estabelecer rotas entre dois nós em redes sem fio em malha/de computador a computador. Quando um nó de origem deseja enviar pacotes/estruturas de dados a um nó de destino, o nó de origem descobre a rota até o destino inundando uma mensagem de Solicitação de Rota (RREQ) pela rede se o nó de origem não tem uma rota válida ao nó de destino e necessita dela. Uma rota reversa de retorno à origem é criada pelos nós na rede à medida que eles recebem e encaminham a RREQ. Quando um nó recebe uma RREQ, o nó de recebimento responde a essa solicitação gerando uma mensagem de Resposta de Rota (RREP) se ou: (1) o nó de recebimento é o próprio destino, ou (2) o nó de recebimento tem uma rota válida ao destino e o sinalizador “somente destino” (‘D’) na RREQ é configurado NÃO. A RREP é encaminhada em transmissão única ao nó de origem através da rota reversa estabelecida e uma rota encaminhada ao destino nos nós intermediários e eventualmente no nó de origem é assim criada. As rotas estabelecidas expiram se elas não são usadas dentro de uma dada vida útil de rota.

No AODV, o sinalizador “somente destino” da mensagem RREQ é configurado pelo nó de origem e não é mudado pelos nós intermediários. Se o sinalizador “somente destino” é configurado na RREQ pelo nó de origem, o nó intermediário não responde à RREQ com uma mensagem RREP mesmo se o nó de recebimento/intermediário tem uma rota válida ao nó de destino. Ele encaminha/re-direciona a RREQ aos seus vizinhos. Somente o nó de destino responde a essa RREQ. Nesse modo de operação, a latência de descoberta de rotas pode ser grande, embora a melhor rota atualizada entre o nó de origem e o nó de destino é eventualmente descoberta no processo. Baixa latência é muito importante para aplicações em tempo real tal como comunicações de voz e de vídeo.

Se o sinalizador “somente destino” não é configurado pelo nó de origem, então qualquer nó intermediário com uma rota válida ao nó de destino responde à mensagem RREQ e à RREP. A mensagem RREP é enviada de volta ao nó de origem em transmissão

Petição 870180138051, de 05/10/2018, pág. 10/24 única e estabelece uma rota de encaminhamento ao nó de destino. Se o sinalizador “RREP Gratuita” (‘G’) no RREQ é configurado, esse nó intermediário também transmite uma RREP gratuita ao nó de destino tal que o nó de destino descobre rotas para o nó de origem. Entretanto, no AODV, se um nó intermediário não gera uma RREP (devido ao nó intermediário ter uma rota válida até o nó de destino), então o nó intermediário descarta a RREQ. Com esta aproximação, o nó de origem pode descobrir uma rota ao nó de destino mais rapidamente devido ao nó de origem não ter que esperar pela resposta do nó de destino. Entretanto, a melhor rota ponto a ponto pode não ser descoberta porque a rota armazenada em cache no nó intermediário pode não ser a melhor rota ao nó de destino. As métricas podem ter mudado devido às dinâmicas de redes sem fio que tornam a rota armazenada em cache menos desejável. Isto é, devido às mudanças na topologia de rede, métrica de roteamento, etc. é possível que a rota armazenada em cache no nó intermediário possa se tornar pior ou que outras rotas com uma melhor métrica ponto a ponto possam se tornar disponíveis criando outras rotas mais desejáveis.

O problema resolvido pela presente invenção é como usar os mecanismos RREQ e RREP para rapidamente descobrir a melhor rota entre um nó de origem e um ou mais nós de destino.

Sumário da Invenção

A presente invenção descreve um método e um sistema para processar/encaminhar mensagens de Solicitação de Rota (RREQ) e gerar mensagens de Resposta de Rota (RREP) em protocolos de roteamento sob demanda, das quais o AODV é um exemplo, tal que a melhor rota pode ser descoberta sem causar significativo atraso/latência de descoberta de rota em redes sem fio em malha/de computador a computador. Especificamente, quando um nó de origem deseja descobrir a rota a um nó de destino, o nó de origem inunda a rede com uma mensagem RREQ com o nó de destino especificado na lista de destinos e o campo de métrica inicializado em 0. A mensagem RREQ contém um novo sinalizador “Resposta Intermediária (IR)” para cada nó de destino. O nó de origem configura o sinalizador correspondente ao nó de destino na RREQ quando ele inicia a inundar a RREQ para descobrir uma rota ao(s) nó(s) de destino(s). Durante o fluxo RREQ, o primeiro nó intermediário com uma rota válida ao nó de destino responde à RREQ com uma mensagem RREP. A mensagem RREP é enviada em transmissão única em direção ao nó de origem e desse modo estabelece rapidamente uma rota de encaminhamento temporário ao destino. Assim, o nó de origem pode usar essa rota de encaminhamento temporário para enviar pacotes/estruturas de dados com um baixo atraso/latência de descoberta de rota. O primeiro nó intermediário zera/limpa o sinalizador “IR” na mensagem RREQ e encaminha o fluxo descendente da mensagem RREQ atualizada em direção ao nó de destino. Visto que o sinalizador “IR” na RREQ foi zerado, os nós intermediários de fluxo descendente não responPetição 870180138051, de 05/10/2018, pág. 11/24 deriam a essa RREQ e somente propagam-na se os nós intermediários de fluxo descendente têm uma rota válida ao(s) nó(s) de destino. As RREQs eventualmente alcançam o(s) nó(s) de destino. O(s) nó(s) de destino pode selecionar a melhor rota/caminho baseado em métricas ponto a ponto e envia uma nova RREP de volta ao nó de origem para estabelecer a melhor rota entre o nó de origem e esse nó de destino. Se o melhor caminho é diferente do caminho de encaminhamento temporário que foi estabelecido via RREP a partir do nó intermediário, o nó de origem trocará para o melhor caminho, uma vez que o melhor caminho está estabelecido.

Um sistema e um método para descobrir uma rota entre um nó de origem e um nó de destino em uma rede sem fio que inclui configurar um sinalizador de resposta intermediária de uma mensagem de solicitação de rota através do nó de origem, inundar a rede sem fio com a mensagem de solicitação de rota e responder à mensagem de solicitação de rota com uma mensagem de resposta de rota através de um primeiro nó intermediário que tem uma rota válida ao nó de destino, são descritos. O sistema e o método então atualizam a mensagem de solicitação de rota e redirecionam a rede sem fio com a mensagem de solicitação de rota. A ação de responder à dita ação de responder desse modo estabelece uma rota de encaminhamento temporário entre o nó de origem e o nó de destino da rede sem fio. Também são descritos um sistema e um método para descobrir uma melhor rota na qual a mensagem de resposta de rota torna-se uma primeira mensagem de resposta de rota. O sistema e o método para descobrir uma melhor rota incluem selecionar através do nó de destino a melhor rota entre ele mesmo e o nó de origem baseado em métricas acumulativas recebidas em mensagens de solicitação de rota recebidas pelo nó de destino, criar uma mensagem de resposta de rota adicional e transmitir a mensagem de resposta de rota ao nó de origem. Se a rota de encaminhamento temporário é a melhor rota, então a mensagem de resposta de rota adicional serve como uma confirmação, e se a rota de encaminhamento temporário não é a melhor rota, então a mensagem de resposta de rota adicional serve para estabelecer a melhor rota mediante o recebimento da mensagem de resposta de rota adicional através do nó de origem.

Breve Descrição dos Desenhos

A presente invenção é melhor entendida a partir da seguinte descrição detalhada quando lida em conjunto com os desenhos em anexo. Os desenhos incluem as seguintes figuras brevemente descritas abaixo:

A Fig. 1 é um formato de mensagem RREQ exemplificado.

A Fig. 2 é um diagrama esquemático de uma rede em malha sem fio de acordo com os princípios da presente invenção.

A Fig. 3 é um diagrama esquemático de uma rede em malha sem fio de acordo com os princípios da presente invenção.

Petição 870180138051, de 05/10/2018, pág. 12/24

A Fig. 4 é um fluxograma de um protocolo de roteamento sob demanda que mostra onde a presente invenção é usada.

A Fig. 5 é um fluxograma do método da presente invenção.

A Fig. 6 é um diagrama de bloco de um nó de acordo com os princípios da presente invenção.

Descrição Detalhada das Modalidades Preferenciais

Quando um nó de origem/ponto em malha deseja enviar pacotes/estruturas de dados para algum nó de destino, ele verifica sua tabela de roteamento para uma rota. Se existe uma rota válida, ele transmite os pacotes/estruturas ao próximo salto especificado na ta10 bela de roteamento para este nó de destino. Se não existe uma rota válida, o nó de origem inicia a descoberta de rota direcionando uma mensagem de Solicitação de Rota (RREQ) pela rede sem fio em malha/de computador a computador. Os pacotes/estruturas de dados podem ter originado no nó ou com o nó ou a partir das estações associadas com o nó se o nó é um ponto de acesso sem fio. É possível que o nó de origem necessite descobrir ro15 tas/caminhos a múltiplos nós de destino. O nó de origem pode disseminar uma RREQ para cada um dos destinos ou, reduzir a sobrecarga de roteamento, inundar a rede com uma única mensagem RREQ que tem uma lista de múltiplos endereços de nós de destino embutidos nesta.

A Fig. 1 é um formato de mensagem RREQ exemplificado com outros possíveis 20 formatos. A mensagem RREQ contém, por exemplo, o endereço do nó de origem/fonte, o número de seqüência do originador, o endereço do nó de destino e o número de seqüência do destino (ou o número de destinos e a lista de endereços de destinos e seus números de seqüência), o ID de RREQ, o ID de mensagem, o comprimento da mensagem, de tempo de vida (TTL), a contagem de saltos, métrica de roteamento, os sinalizadores, e outras informa25 ções. Além dos sinalizadores “Somente Destino” (‘D’) e “RREP Gratuita” (‘G’), um novo sinalizador, chamado aqui de sinalizador de “Resposta Intermediária” (IR), está contido na mensagem RREP. Os sinalizadores ‘D’ e ‘G’ são carregados como um legado do AODV convencional. Esses dois sinalizadores não são configurados/usados pelo nó de origem e são ignorados pelos nós de destino e intermediários. Uma modalidade alternativa é que a mensagem 30 RREQ não contém sinalizadores ‘D’ e ‘G’ também. Se a mensagem RREQ carrega uma lista de endereços de destino, então múltiplos sinalizadores de “Resposta Intermediária” são incluídos na mensagem RREQ, cada um correspondente a um endereço de destino. Quando o nó de origem deseja descobrir uma rota para um ou mais endereços de destino, ele configura os sinalizadores de “Resposta Intermediária” (IR) correspondendo aos endereços 35 de destino. Dever-se-ia notar que o(s) endereço(s) do nó de destino pode ser endereço(s) de protocolo de internet (IP) ou endereço(s) de camada 2 (controle de acesso à mídia MAC). Para se adaptar às mudanças em condições de rede e para manter a melhor rota

Petição 870180138051, de 05/10/2018, pág. 13/24 métrica entre nós, cada nó de origem ativo pode opcionalmente direcionar a rede em maIha/de computador a computador sem fio com uma mensagem RREQ periódica (RREQ de manutenção) para o(s) endereço(s) de destino com o qual ela se comunica. O sinalizador “IR” na RREQ de manutenção não é configurado. Os nós de destinos e os intermediários 5 processam a RREQ de manutenção seguindo as mesmas regras que são usadas para processar uma RREQ de não manutenção na fase de descoberta.

Assim, pode-se ver que a disseminação de mensagens RREQ de não manutenção e de manutenção em uma rede sem fio em malha/de computador a computador resulta em estabelecer/atualizar uma rota reversa para o originador (nó de origem) da RREQ nos nós 10 intermediários e nos nós de destino. A disseminação de mensagens RREQ de não manutenção também dispara as mensagens RREP a partir dos nós de destino e provavelmente dos nós intermediários. A disseminação de mensagens RREQ de manutenção dispara as mensagens RREP a partir dos nós de destino.

Quando um nó de destino ou nó intermediário recebe uma mensagem RREQ, ele 15 cria uma rota reversa ao nó de origem ou atualiza sua rota reversa atual ao nó de origem. Dever-se-ia notar que cada nó pode receber múltiplas cópias da mesma mensagem RREP (originando com o mesmo nó de origem e tendo o mesmo ID de RREQ), cada mensagem RREQ atravessando um caminho diferente a partir do nó de origem ao nó de destino/intermediário/recebimento. Se uma rota reversa é criada ou modificada ou essa é a “pri20 meira cópia” de uma mensagem RREQ, a mensagem RREQ é encaminhada (redirecionada). Uma “primeira cópia” é usada aqui para ter em vista que essa cópia desta mensagem RREQ é a primeira cópia ou a primeira vez que esse nó de destino/intermediário/recebimento recebeu ou viu essa mensagem RREQ particular identificada pelo seu endereço originador e ID de RREQ. Quando um nó intermediário encaminha uma 25 mensagem RREQ, o campo métrico na mensagem RREQ é atualizado para refletir a métrica acumulativa da rota ao nó de origem da RREQ a partir do nó intermediário. Além disso, se o sinalizador “IR” para um nó de destino na lista de nós de destino da mensagem RREQ recebida é configurado e o nó intermediário tem uma rota válida ao nó de destino, o nó intermediário responde à mensagem RREQ com uma mensagem de resposta de rota RREP. 30 Esta mensagem de resposta de rota é enviada ao nó de origem em transmissão única e estabelece um caminho de encaminhamento ao nó de destino. O nó de origem pode então usar essa rota e enviar imediatamente estruturas/pacotes de dados ao nó de destino. Se o nó intermediário responde à mensagem RREQ com uma mensagem RREP para um nó de destino na lista de nós de destino RREQ, ele zera/limpa o sinalizador “IR” para esse nó de 35 destino na mensagem RREQ antes do re-inundação da rede com a mensagem RREQ atualizada. A razão para zerar o sinalizador “IR” depois que uma mensagem RREQ é enviada é suprimir quaisquer mensagens RREP a partir dos nós intermediários de fluxo descendente.

Petição 870180138051, de 05/10/2018, pág. 14/24

Somente o primeiro nó intermediário com uma rota válida ao nó de destino ao longo da rota cruzada pelo re-direcionamento de mensagem RREQ, responde com uma mensagem

RREQ para esse nó de destino. Se o sinalizador “IR” para um destino é zerado/limpo na mensagem RREQ, um nó intermediário não deveria responder com uma mensagem RREP mesmo se ele tem uma rota válida ao nó de destino.

Depois de criar/estabelecer ou atualizar uma rota reversa ao nó de origem, o nó de destino envia uma mensagem RREP de transmissão única de volta ao nó de origem. Os nós intermediários criam rotas de encaminhamento ao(s) nó(s) de destino mediante o recebimento da mensagem RREP, e também encaminha a mensagem RREP em direção ao nó de 10 origem. Quando o nó de origem recebe a mensagem RREP, ele cria uma rota de encaminhamento ao nó de destino. Se o nó de destino recebe mensagens RREQ adicionais com métricas melhores, então o nó de destino atualiza sua rota ao nó de origem para a nova rota e também envia uma nova mensagem RREP de volta ao nó de origem ao longo da rota atualizada. A nova mensagem RREP estabelece uma rota de encaminhamento melhor (atuali15 zada) a partir do nó de origem ao nó de destino nos nós intermediários e eventualmente no nó de origem. Uma vez que essa melhor rota de encaminhamento é estabelecida, o nó de origem a usa para enviar dados. Eventualmente, uma melhor rota de métrica ponto a ponto, bidirecional, é estabelecida entre o nó de origem e o nó de destino. Usando essa aproximação, o nó de origem pode rapidamente obter uma rota ao nó de destino que é estabelecida 20 com a mensagem RREP respondida pelo nó intermediário com uma rota válida ao nó de destino. Se essa rota não é a melhor rota de métrica ponto a ponto entre o nó de origem e o nó de destino, a rota é atualizada para a melhor rota, portanto.

Com relação agora à Fig. 2, que descreve o re-inundação da rede sem fio em maIha/de computador a computador com a mensagem de Solicitação de Rota (RREQ) e o nó 25 intermediário B, com uma rota válida ao nó de destino E, respondendo à mensagem RREQ com uma mensagem RREP. Considera-se um exemplo no qual o nó de origem A tenta descobrir uma rota ao nó de destino E. O nó de origem A redireciona as mensagens de Solicitação de Rota (RREQ) com o sinalizador “IR” configurado na rede sem fio em malha/de computador a computador. Assume-se que o nó intermediário B já tem uma rota válida B-C-D-E 30 ao nó de destino E. Quando o nó intermediário B recebe a RREQ, ele cria uma rota reversa ao nó de origem do qual ele recebe a RREQ como o próximo salto (nó de origem A) da rota/caminho reverso. O nó intermediário B responde à RREQ com uma RREP de transmissão única devido a ele ter uma rota válida ao destino E e o sinalizador “IR” na RREQ é configurado. A RREP estabelece uma rota de encaminhamento ao nó de destino E no nó de origem 35 A. Tão logo o nó de origem A crie a rota/caminho ao nó de destino E com a RREP do nó intermediário B, o nó de origem A pode iniciar o envio de pacotes/estruturas de dados ao nó de destino E via rota A-B-C-D-E. O nó intermediário B zera o sinalizador “IR” na mensagem

Petição 870180138051, de 05/10/2018, pág. 15/24

RREQ e o encaminha adiante. A razão para zerar o sinalizador “IR” é limitar as respostas ao fluxo RREQ a somente o primeiro nó intermediário com um caminho válido ao nó de destino. Os outros nós intermediários de fluxo descendente, por exemplo, C e D, não necessitam responder a essa RREQ com uma RREP porque o sinalizador “IR” não está configurado. Assume-se que os nós intermediários F, G e H não têm rotas válidas ao nó de destino E. Quando os nós intermediários F, G e H recebem as mensagens RREQ redirecionadas, eles criam o rota reversa ao nó de origem A com o nó do qual cada um dos nós intermediários F, G e H recebe a RREQ como o próximo salto da rota reversa. Cada um dos nós intermediários F, G, e H então encaminha as mensagens RREQ adiante.

Neste exemplo, o nó de destino E recebe duas cópias dessa RREQ, cada uma cruzando com um caminho diferente: A-B-C-D-E, A-F-G-H-E. Assumindo que as duas RREQs alcançaram o nó de destino E na seguinte ordem: A-B-C-D-E e então A-F-F-G-E, o nó de destino E primeiro cria uma rota ao nó de origem A através do nó intermediário D tão logo o nó de destino E receba a RREQ ao longo da rota/caminho A-B-C-D-E. Neste ponto, a rota reversa ao nó de origem A foi estabelecida nos nós intermediários B, C e D. O nó de destino E envia uma RREP ao longo da rota E-D-C-B-A. A RREP somente renova a rota A-B-C-D-E. Se existem quaisquer outros nós de destino na lista de destino da RREQ, por exemplo, nó I, o nó de destino E se remove da lista de destinos e então encaminha a RREQ adiante (por exemplo, para o nó I). Se não existem outros nós de destino na lista de destinos da RREQ, então a RREQ não é encaminhada.

Com relação agora à Fig. 3, que descreve uma rede em malha de área local sem fio que mostra a resposta do nó de destino E, uma RREP (1) mediante o recebimento da RREQ através de A-B-C-D-E e envia uma nova RREP (2) para estabelecer uma melhor rota/caminho de encaminhamento depois de receber a RREQ através de A-F-G-H-E. Quando o nó de destino E recebe a RREQ que vem ao longo de A-F-G-H-E, o nó de destino E determina que essa RREQ vem ao longo de um caminho com uma melhor métrica para A do que a rota/caminho de encaminhamento temporário A-B-C-D-E. Então, o nó de destino E modifica/atualiza o próximo salto a partir do nó intermediário D ao nó intermediário H e atualiza a métrica. O nó de destino E então envia uma RREP de transmissão única de volta ao nó de origem A através do nó intermediário H, bem como atualiza e encaminha a RREQ se não existem um ou mais outros nós de destino na lista de destinos RREQ. A RREP estabelece a rota ao nó de origem A via os nós intermediários H, G e H. Quando o nó de origem A recebe essa RREP, ele modifica/atualiza o próximo salto para o nó de destino E do nó intermediário B ao nó intermediário F. A rota ao nó de destino E é mudada para A-F-G-H-E.

Com relação agora à Fig. 4, que é um fluxograma para processamento de uma mensagem RREQ. Quando um nó recebe uma mensagem RREQ, ele primeiro cria/estabelece ou atualiza uma rota reversa para o salto anterior a partir do qual o nó recePetição 870180138051, de 05/10/2018, pág. 16/24 beu a mensagem RREQ se necessário em 410. O nó intermediário/recebimento pode então criar ou atualizar a rota reversa para o originador da RREQ como segue. Se a rota reversa ao originador da mensagem RREQ não existe na tabela de roteamento ou é inválida em 415 e 420, ela é criada ou atualizada. O próximo salto na tabela de roteamento para a rota re5 versa para o originador da RREQ torna-se o salto anterior (o nó a partir do qual a mensagem RREQ foi recebida). Se uma rota reversa válida ao originador da RREQ existe, o número de seqüência de origem na mensagem RREQ é comparado ao número de seqüência da entrada de rota na tabela de roteamento em 425 para a rota reversa. Se o número de seqüência na mensagem RREQ é mais antigo, ele é abandonado e nenhum processamento 10 adicional é realizado em 445. De outra forma, a rota reversa atual ao originador é modificada se a nova métrica é melhor que a métrica da rota atual ao originador na tabela de roteamento em 430. A nova métrica é definida como a métrica na mensagem RREQ mais a métrica de ligação entre o nó a partir do qual ela recebeu a mensagem RREQ e ela mesma. Se a nova métrica não é melhor do que a métrica da rota reversa atual na entrada de tabela de 15 roteamento, mas o número de seqüência de origem na RREQ é maior (mais novo) que o número de seqüência na tabela de roteamento para a rota reversa em 435, o nó intermediário verifica se as funções de processamento opcionais de histerese e armazenamento em cache de melhor rota candidata são suportadas pela rede em malha em 450. Se essas funções de processamento opcionais não são suportadas, a rota reversa ao originador de 20 RREQ é atualizada em 455. Quando uma rota reversa é criada ou modificada, o número de seqüência na tabela de roteamento para a rota reversa é configurado para o número de seqüência de origem na mensagem RREQ, o próximo salto torna-se o nó a partir do qual a mensagem RREQ foi recebida, a métrica é configurada para a nova métrica, e a contagem dos saltos é configurada para um mais do que a contagem de saltos na mensagem RREQ.

Se uma rota reversa ao nó de origem foi criada ou modificada, ou a mensagem

RREQ foi a primeira cópia de uma nova mensagem RREQ (o ID de RREQ não foi visto antes da origem) em 420 e 440, a rotina de encaminhamento de RREQ e de geração de RREP descrita aqui é executada em 475. Podem haver outros casos quando a rotina de encaminhamento de RREQ e de geração de RREP descrita aqui é executada por um nó. Por 30 exemplo, em algum método de armazenamento em cache de melhor rota candidata, as mensagens RREQ podem ser armazenadas em uma fila de espera com um temporizador durante o armazenamento em cache da rota candidata. Quando o temporizador da fila de espera expira, a rotina de encaminhamento de RREQ e de geração de RREP é executada.

O nó de origem pode enviar as mensagens RREQ de manutenção periódica para 35 renovar suas rotas de encaminhamento ativo e rotas reversas. Cada vez que a origem envia uma mensagem RREQ de manutenção é chamada de turno de renovação de rota. É possível que os nós que já tenham a melhor rota reversa ao nó de origem recebam uma mensaPetição 870180138051, de 05/10/2018, pág. 17/24 gem RREQ com um número de seqüência mais novo, mas uma rota de pior métrica ao nó de origem antes de receber a mensagem RREQ através da rota de melhor métrica atual. Adicionalmente, a cópia da mensagem RREQ propagada ao longo da rota de melhor métrica atual pode ser perdida durante a re-inundação. Estes eventos podem resultar em oscila5 ção de rota. Para reduzir a oscilação de rota e selecionar a melhor rota durante cada turno de renovação de rota, um tipo de histerese e mecanismo de armazenamento em cache de melhor rota candidata podem ser usados. Se é determinado em 460 que a histerese e a opção de armazenamento em cache de melhor rota candidata são implementadas por uma rede em malha, um nó intermediário atualiza a tabela de roteamento e modifica a rota rever10 sa se o número de seqüência de origem na mensagem RREQ é maior (mais novo) do que o número de seqüência na entrada da tabela de roteamento por um valor maior do que um valor limite. De outra forma, a rota reversa pode ser armazenada em cache como uma rota alternativa candidata potencial em 465.

Se o nó subseqüentemente aprende que a rota reversa atual foi degradada e tor15 nou-se pior do que a rota reversa candidata, ele é capaz de mudar para a rota candidata aprendida anteriormente no mesmo turno de renovação. A presente invenção descreve um método e um sistema para encaminhar uma mensagem RREQ e gerar uma mensagem RREP para descobrir a melhor rota sem causar um grande atraso/latência de descoberta de rota em redes em malha sem fio. O método da presente invenção trabalha com ou sem his20 terese e armazenamento em cache de rota candidata/alternativa.

Com relação agora à Fig. 5, que é um fluxograma que descreve o método de encaminhamento de RREQ e de geração de RREP da presente invenção, um nó determina se ele é um nó de destino, isto é, se um ou mais endereços do nó (self_addr) combinam com os endereço de destino solicitados na lista de destinos da mensagem RREQ rreq.dest em 25 505. Dever-se-ia notar que um próprio nó pode ter múltiplos endereços ou ele pode ser um proxy para os outros nós. Por exemplo, um nó pode ser um ponto de acesso e gerar/gerenciar as mensagens de roteamento em favor das estações de legado associadas com ele (um proxy para as estações). A funcionalidade para este caso é similar à situação quando um nó tem múltiplos endereços. Os endereços de destino das estações associadas 30 podem ser tratados como endereços de réplica para o ponto de acesso. Um nó é um nó de destino se um ou mais endereços especificados na lista de destinos de mensagem RREQ pertence a ele ou um dos nós o usa como proxy. Quando um nó recebe uma mensagem RREQ na qual o nó de destino é este do nó proxy por ele, ele deveria processar a mensagem RREQ como se o endereço do nó de destino fosse seu próprio endereço. Além disso, 35 um nó pode ser um nó de destino para endereços solicitados na lista de destinos de mensagem RREQ, mas o nó intermediário para um outro endereço solicitado na lista de destino de mensagem RREQ.

Petição 870180138051, de 05/10/2018, pág. 18/24

Se um ou mais endereços do nó combinam com os endereços de destino solicitados na lista de destinos da mensagem RREQ, o nó gera e envia a mensagem RREQ de transmissão única ao originador da mensagem RREQ para esses endereços de destino combinados em 510. Um nó de destino remove seu(s) endereço(s) próprio(s)/proxy da lista 5 de destinos da mensagem RREQ em 515. Depois disso, se não existem endereços solicitados restantes na lista de destinos da mensagem RREQ em 520, a mensagem RREQ é descartada em 525. Se o nó não é um nó de destino para qualquer endereço solicitado na lista de destinos da mensagem RREQ (505) ou existem outros endereços de destinos solicitados na lista de destinos da mensagem RREQ além dos endereços do nó, isto é, o nó é um nó 10 intermediário para um ou mais endereços na lista de destinos da mensagem RREQ, o nó verifica os endereços restantes na lista de destinos da mensagem RREQ como segue. Assume-se que rreq.dest[i] representa o (i+1)o endereço na lista de destinos da mensagem RREQ. O nó inicia um índice (por exemplo, i) em 545 e verifica rreq.dest[1], isto é, o primeiro endereço na lista de destinos da mensagem RREQ para determinar se existe uma rota de 15 encaminhamento ativa até o nó de destino representado por rreq.dest[1] em 550. Se um nó intermediário tem uma rota ativa até o destino, a rota ao nó de destino é válida (555), o número de seqüência no mínimo equivalente àquele indicado na mensagem RREQ original (560) e o sinalizador de “Resposta Intermediária” (IR)” é configurado (570), o nó intermediário gera uma mensagem RREP para esse endereço de destino solicitado em 575 e envia a 20 mensagem RREP gerada em transmissão única ao originador da mensagem RREQ ao longo da rota reversa atual. O sinalizador “IR” para esse destino solicitado na mensagem RREQ é zerado em 580. O nó aumenta o índice (por exemplo, em um) e verifica se existem quaisquer endereços adicionais na lista de destinos da mensagem RREQ em 590. Se existem quaisquer endereços adicionais na lista de destinos da mensagem RREQ, então a exe25 cução do ciclo descrito acima se repete iniciando em 550. Isto é, o ciclo é repetido se uma mensagem RREP necessita ser enviada para o próximo destino solicitado. O ciclo é repetido até que todos os endereços na lista de destinos da mensagem RREQ tenham sido verificados.

A mensagem RREQ de chegada original é verificada para determinar se o valor de 30 vida útil (TTL) é maior que 1 em 530. Se o valor TTL é maior que um, então a informação na mensagem RREQ original é atualizada, incluindo a diminuição do valor de TTL na mensagem RREQ de saída, por exemplo, em um em 535. O número de seqüência de origem, a métrica e a contagem de saltos são também configurados para a informação correspondente na entrada de rota atualizada para a origem em 535. A mensagem RREQ atualizada é 35 encaminhada em 540.

Nota-se que um nó de destino pode possuir/proxy um ou mais endereços e um nó intermediário pode ter rota(s) válida(s) para um ou mais endereços de destino. Uma mensaPetição 870180138051, de 05/10/2018, pág. 19/24 gem RREQ pode carregar um ou mais endereços de destino em sua lista de endereços de destino. Um nó de processamento/intermediário/destino pode satisfazer as condições acima e enviar uma mensagem RREP para múltiplos endereços solicitados na lista de destinos da mensagem RREQ. Se um nó envia uma mensagem RREP para múltiplos destinos, ele pode 5 enviar múltiplas mensagens RREP, uma para cada destino, ou ele pode enviar uma única mensagem RREP agregada com múltiplos endereços de destino na lista de endereços.

A Fig. 6 é um diagrama de bloco que ilustra os detalhes de um nó 600 da presente invenção. O nó inclui um módulo de medição de carga e de qualidade de conexão 605, um módulo de cálculo da métrica de roteamento 610, um módulo de seleção de rota 615 e um 10 módulo de comunicações 620. módulo de medição de carga e de qualidade de conexão 605 mede a qualidade e a carga da conexão/canal com cada um de seus vizinhos. Ele fornece os resultados de medição ao módulo de cálculo da métrica de roteamento 610 tal que módulo de cálculo da métrica de roteamento 610 possa determinar o custo/métrica da conexão com cada um dos seus vizinhos. Nota-se que um nó pode ter múltiplos vizinhos, múltiplas 15 interfaces de rádio, e múltiplos canais/conexões físicos/lógicos. Todos eles necessitam ser medidos. O módulo de cálculo da métrica de roteamento 610 de cada nó usa medidas obtidas pelo módulo de medição de qualidade e de carga junto com outra informação para calcular a métrica de roteamento para cada nó com o qual ele se comunica. A métrica de roteamento é atualizada periodicamente. O módulo de seleção de rota 615 determina/seleciona 20 uma rota/caminho para encaminhar/comunicar dados a um nó de destino baseado nas métricas de roteamento calculadas. O módulo de seleção de rota 615 troca as mensagens de controle de roteamento e os dados com outros nós na rede em malha via o módulo de comunicações 620. Dever-se-ia citar que um nó pode ter uma ou mais interfaces de comunicação por rádio e outras interfaces de comunicação. Entende-se que o módulo de seleção de 25 rota pode realmente ser feito de várias unidades menores ou combinado com outros módulos aqui descritos. Entende-se adicionalmente que os processos descritos aqui (especialmente com relação às Figs. 3 e 4) podem ser software, hardware, suporte lógico inalterado ou qualquer combinação destes executados no módulo de seleção de rota ou por ele.

Entende-se que a presente invenção pode ser implementada em várias formas de 30 hardware, software, suporte lógico inalterado, processadores de propósito especial, ou combinação desses, por exemplo, em um terminal móvel, ponto de acesso, ou rede celular. Preferencialmente, a presente invenção é implementada como uma combinação de hardware e software. Além disso, o software é preferencialmente implementado como um programa aplicativo tangivelmente incorporado em um dispositivo de armazenamento de programa. O 35 programa aplicativo pode ser carregado, e executado através de uma máquina que compreende qualquer arquitetura adequada. Preferencialmente, a máquina é implementada em uma plataforma de computador que tem hardware, tal como uma ou mais unidades de proPetição 870180138051, de 05/10/2018, pág. 20/24 cessamento centrais (CPU), memória de acesso aleatório (RAM), e interface(s) de entrada/saída (l/O). A plataforma de computador também inclui um sistema operacional e código de micro-instrução. Os vários processos e funções descritos aqui podem também ser parte do código de micro-instrução ou parte do programa aplicativo (ou uma combinação deles), 5 que é executada via o sistema operacional. Em adição, vários outros dispositivos periféricos podem ser conectados à plataforma de computador, tal como dispositivos de armazenamento de dados adicionais e um dispositivo de impressão.

Entende-se adicionalmente que, devido a alguns dos componentes do sistema constituinte e etapas de método descritas nas figuras em anexo serem preferencialmente 10 implementados em software, as conexões reais entre os componentes do sistema (ou as etapas do processo) podem diferir dependendo da maneira pela qual a presente invenção é programada. Dados os ensinamentos aqui fornecidos, um versado na técnica pode ser capaz de observar essas e outras implementações ou configurações similares da presente invenção.

Petição 870180138051, de 05/10/2018, pág. 21/24

Claims

REIVINDICAÇÕES

1. Sistema para descobrir uma rota entre um nó de origem (A) e um nó de destino (E) em uma rede sem fio, compreendendo:

dispositivos para receber uma mensagem de solicitação de rota (RREQ) enviada pelo dito nó de origem (A);

dispositivos para responder à dita mensagem de solicitação de rota (RREQ) com uma mensagem de resposta de rota (RREP) por um primeiro nó intermediário (B) possuindo uma rota válida ao dito nó de destino (E);

dispositivos para atualizar a dita mensagem de solicitação de rota (RREQ); e dispositivos para re-inundar a dita rede sem fio com a dita mensagem de solicitação de rota atualizada;

CARACTERIZADO pelo fato de que:

o dito primeiro nó intermediário (B) compreende dispositivos para responder as ditas mensagens de solicitação de rota (RREQ) quando um indicador (IR) na dita mensagem de solicitação de rota (RREQ) é configurado, e o dito primeiro nó intermediário (B) compreende adicionalmente dispositivos para re-inundar a dita rede sem fio com a dita mensagem de solicitação de rota (RREQ) com o dito indicador (IR) reconfigurado.
2. Sistema, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que o dito dispositivo para atualizar adicionalmente compreende dispositivos para limpar um indicador (IR) e dispositivos para atualizar uma métrica (METRIC) na dita mensagem de solicitação de rota (RREQ) com uma métrica cumulativa da dita rota entre o dito nó de origem (A) e o dito nó de destino (E) da dita rede sem fio.
3. Sistema, de acordo com a reivindicação 1 ou 2, CARACTERIZADO pelo fato de que o dito dispositivo para responder assim estabelece uma rota de encaminhamento temporário entre o nó de origem (A) e o dito nó de destino (E) da dita rede sem fio.
4. Sistema, de acordo com a reivindicação 3, CARACTERIZADO pelo fato de que a dita rota de encaminhamento temporário está disponível para transmissão de dados mediante o recebimento da dita mensagem de resposta de rota (RREP) pelo dito nó de origem (A), em que a dita rota é a rota em resposta à métrica ponto a ponto e adicionalmente em que a dita mensagem de resposta de rota (RREP) é uma primeira mensagem de resposta da rota.
5. Sistema, de acordo com a reivindicação 4, CARACTERIZADO pelo fato de que adicionalmente compreende dispositivos para receber uma mensagem de resposta de rota adicional do dito nó de destino, a dita mensagem de resposta de rota adicional incluindo a dita rota em resposta à métrica ponto a ponto entre o dito nó de destino e o dito nó de origem com base em métricas cumulativas em mensagens de solicitação de rota recebidas pelo dito nó de destino, em que se a dita rota de encaminhamento temporário é a dita rota

Petição 870180138051, de 05/10/2018, pág. 22/24 em resposta à métrica ponto a ponto, então a dita mensagem de resposta de rota adicional serve como uma confirmação, e se a dita rota de encaminhamento temporário não é a dita rota em resposta à métrica ponto a ponto, então a dita mensagem de resposta de rota adicional serve para estabelecer a dita rota em resposta à métrica ponto a ponto mediante o re5 cebimento da dita mensagem de resposta de rota adicional pelo dito nó de origem.
6. Sistema, de acordo com qualquer uma das reivindicações 1 a 5, CARACTERIZADO pelo fato de que a dita rede sem fio é uma rede sem fio em malha, em que a dita mensagem de resposta de rota dos ditos dispositivos para responder são transmissões para o dito nó origem, em que um endereço do dito nó de destino é um dentre um 10 endereço de protocolo de internet e um endereço de controle de acesso à mídia, em que o dito nó de destino inclui nós de destino que são associados a um dentre um proxy e um ponto de acesso.

Petição 870180138051, de 05/10/2018, pág. 23/24

g< ai R gz < z o o □ S?ui 3 ζωαο

CC zju ui a α

gç (5 / /

CC