BRPI0712202A2

BRPI0712202A2 - representação de uma trajetória de demora em redes móveis

Info

Publication number: BRPI0712202A2
Application number: BRPI0712202-0A
Authority: BR
Inventors: Augustin Chaintreau
Original assignee: Thomson Licensing
Priority date: 2006-05-22
Filing date: 2007-05-16
Publication date: 2012-01-10
Also published as: EP2020127B1; US20090175219A1; US8509084B2; EP2020127A2; WO2007135325A3; JP2009538077A; JP5132675B2; WO2007135325A2; CN101455039B; CN101455039A

Abstract

REPRESENTAçãO DE UMA TRAJETóRIA DE DEMORA EM REDES MóVEIS A presente invenção refere-se a um dispositivo de comunicação em uma rede de comunicação compreendendo pelo menos dois dispositivos de comunicação caracterizado em que compreende meios para: - armazenar para cada par (fonte, destino) dos dispositivos de rede, trajetórias na forma de listas de pares (LD, EA), EA sendo a Chegada Mais Precoce e LD sendo a última Partida, para qualquer seqúência de contatos entre os dispositivos, e - transmitir dados para outro dispositivo por um nó selecionado usando história das trajetórias anteriores observadas. A presente invenção também refere-se a um método de comunicação.

Description

"REPRESENTAÇÃO DE UMA TRAJETÓRIA DE DEMORA EM REDES MÓVEIS"

ESCOPO DA INVENÇÃO

A presente invenção refere-se ao campo de redes sem fios.

A presente invenção mais especificamente refere-se a um dispositivo de comunica- ção e a um método de comunicação entre dispositivos diferentes.

TÉCNICA ANTERIOR

A presente invenção enquadra-se no escopo de redes, por exemplo, do tipo ad-hoc sem fios ou PAN (Redes de Área Pessoal), notavelmente Bluetooth. A rede é mostrada co- mo um gráfico em que um terminal móvel é um nó (pico) do gráfico, identificado, por exem- plo, por um endereço MAC em que as bordas correspondem aos contatos entre os pares dos terminais, e em que uma trajetória é uma seqüência de bordas cronologicamente orde- nadas. Entre todas as possíveis trajetórias, uma é considerada como ótima se, partindo de uma fonte em um tempo dado, alcançar o destino na possível data de chegada mais preco- ce. Para cada par (fonte, destino), a função de chegada dá, a cada instante, o tempo de chegada mais prematuro para um pacote criado. Uma solução "genuína" consistiria repre- sentar as demoras de tempo observadas com um valor para cada instante. Um algoritmo de cálculo da trajetória ótima atualizaria o conjunto de valores toda vez que uma possível traje- tória nova fosse encontrada. Esta solução é cara em espaço e operações.

A técnica anterior já sabe, através do artigo científico uShortest-Path and Minimum- Delay Algorithms in Networks with Time-Dependent Edge-Lenght' (A. Orda e R. Rom), um método para solucionar o problema da trajetória mais curta em redes em que a demora (ou peso) das bordas altera com tempo de acordo com as funções aleatórias. O método de a- cordo com a presente invenção é diferente à medida que calcula a trajetória mais curta ao mesmo tempo para todas as fontes.

A técnica anterior também sabe, através do artigo científico "An efficient on-line al- gorithm for the shortest mobile path problem" (Syrotiuk) um método para solucionar o pro- blema da trajetória mais curta na rede mostrada na forma de gráficos móveis.

SUMÁRIO DA INVENÇÃO

Para qualquer seqüência admissível de contatos (uma trajetória cronologicamente ordenada), a Chegada Mais Precoce (EA) e a Última Partida (LD) são definidas. O método de acordo com a presente invenção constrói funções de chegada para todos os pares (fonte, destino), por indução nos conjuntos de contatos, ou bordas do gráfico temporal. As funções são representadas com base nos conjuntos de pares (LD, EA). Para cada par (fonte, desti- no), é possível representar todas as trajetórias ótimas por uma lista de pares (LD, EA).

O processo de chegada em cada tempo (função de chegada) é representado por uma seqüência de pares de tempo-valor.

A presente invenção pretende superar as desvantagens da técnica anterior propon- do uma metodologia de extrair rápida e eficientemente as trajetórias ótimas.

Para este propósito, a presente invenção refere-se, em seu sentido mais em geral aceito, um dispositivo de comunicação em uma rede de comunicação compreendendo pelo menos dois dispositivos de comunicação, caracterizado em que compreende meios para:

- armazenar para cada par (fonte, destino) dos dispositivos de rede, trajetórias na forma de listas de pares (LD, EA), EA sendo a Chegada Mais Precoce e LD sendo a Última Partida, para qualquer seqüência de contatos entre os dispositivos, e

- transmitir os dados para outro dispositivo por meio de um nó selecionado usando história das trajetórias anteriores observadas.

Preferivelmente, a dita rede de comunicação é do tipo de troca de pacotes, e o dis- positivo compreende meios para:

- criar, para os pares (fonte, destino) da dita rede, funções que forneçam, em cada tempo, o tempo de chegada mais prematuro para cada pacote criado, e

- representar estas funções com base nos conjuntos de pares (LD, EA).

De acordo com uma variante, a dita rede é do tipo PAN (Rede de Área Pessoal).

De acordo com uma modalidade particular, a dita rede é do tipo ad-hoc sem fios.

De acordo com uma modalidade, a dita rede é do tipo Bluetooth.

De acordo com outra modalidade, a dita rede é do tipo Wi-Fi.

De acordo com uma variante, um dispositivo de comunicação da dita rede é identifi- cado por um endereço MAC (Controle de Acesso à Mídia).

A presente invenção também refere-se a um método de comunicação em uma rede de comunicação compreendendo pelo menos dois dispositivos de comunicação, caracteri- zado em que compreende etapas que consistem em:

- armazenar cada par (fonte, destino) dos dispositivos de rede, trajetórias na forma de listas de pares (LD, EA), EA sendo a Chegada Mais Precoce e LD sendo a Última Parti- da, para qualquer seqüência de contatos entre os dispositivos, e

- transmitir os dados para outro dispositivo por um nó selecionado usando a história de trajetórias anteriores observadas.

Preferivelmente, a dita rede de comunicação é do tipo de troca de pacotes, e o dito método compreende as etapas que consistem em:

- representar estas funções com base nos conjuntos de pares (LD, EA).

BREVE DESCRIÇÃO DOS DESENHOS

A invenção será melhor entendida da descrição a seguir de uma modalidade da in- venção fornecida como um exemplo em referência às figuras anexadas, em que:

- Figura 1 ilustra o método de acordo com a presente invenção, - Figura 2 é um diagrama cronológico que descreve as trajetórias ótimas em cada tempo, para um dado par (fonte, destino),

- Figura 3 ilustra um exemplo de trajetórias com respeito ao tempo, usando o mes- mo contato, e que não pode ser concatenado, e

- Figura 4 mostra um exemplo de cenário para uma rede móvel.

DESCRIÇÃO DETALHADA DAS MODALIDADES DA INVENÇÃO

O método de acordo com a presente invenção reduz a memória requerida para rea- lizar um cálculo em traços grandes, ou um cálculo em tempo real.

Além disso, o método de acordo com a presente invenção é a representação mais compacta destas trajetórias ótimas (2N números para N trajetórias ótimas). Além disso, au- tomaticamente adapta-se a duas situações:

- a convenção de codificação usada é bem adaptada para trajetórias simultâneas,

- um grau muito alto de heterogeneidade na granularidade da trajetória (muitas tra- jetórias em alguns segundos, depois períodos longos de tempo sem qualquer evento).

Os resultados da invenção podem ser usados para tomar decisões de transmissão para um terminal móvel.

Uma seqüência de bordas que formam uma trajetória na topologia de gráfico é chamada admissível se uma trajetória com respeito ao tempo puder ser definida usando a seqüência destes contatos:

(ei,e2..... en) onde

<formula>formula see original document page 4</formula>

é admissível se uma seqüência não-

decrescente de tempos existe (ti.....tn) de modo que ti beg <t, <t,end.

Por indução, obtemos o fato que uma condição equivalente é:

<formula>formula see original document page 4</formula>

As seqüências admissíveis não podem sempre ser concatenadas, até mesmo se o último contato para uma seqüência for o primeiro contato da outra. Isto é devido ao fato que as trajetórias com respeito ao tempo para a primeira seqüência podem chegar após as traje- tórias com respeito ao tempo da segunda ter passado.

Figura 3 ilustra um exemplo deste caso: a seqüência (e1,e2,e3,e4) é admissível, por- que pode ser associada à seqüência aumentando no tempo (3, 5, 5, 5). Similarmente, a se- qüência (e4,e5) pode ser associada à seqüência de tempo (4, 4). Porém, (e1,2,3,e4,5e) não é admissível, porque não define trajetórias com respeito ao tempo. Nesta Figura 3, o primei- ro traço curto vertical em cada linha horizontal representa o primeiro contato e o segundo traço vertical em cada linha horizontal representa a extremidade do contato.

Para qualquer seqüência admissível de contatos e = e1 e2,..., en), a chegada mais precoce é definida: EA ou Chegada mais Precoce: EA(e) = max1t1beg9}. Similarmente, a última partida: LD ou Última Partida é definida como LD(e) = min{t-,end}. Os fatos a seguir são simples para se obter. Eles mostram que as definições prece- dentes permitem a descrição geral de uma classe grande de trajetórias com respeito ao tempo, e manipulação de uma seqüência admissível.

(i)Todas as trajetórias com respeito ao tempo associado a e deixam a fonte antes de LD (e) e chegam após EA(e).

(ii)Há trajetórias com respeito ao tempo associado a e que partem da fonte no tem- po LD(e) e que chegam no tempo EA(e).

(iii)Duas seqüências (e), (e') de contatos tais como vn = v'0 podem ser concatenadas em uma seqüência admissível simples eoe' se e apenas se EA(e) ≤LD(e').

(iii) proposto é uma construção simples e útil da caracterização das seqüências admissíveis (1) previamente apresentadas. É simples para verificar que EA (eo') = max(EA(e),EA(e')) e que LD(eoeO = min(LD(e),LD(e')).

Em (ii), não é necessariamente a mesma trajetória que deixa a fonte no tempo LD(e) e que chega no tempo EA(e). Tome por exemplo uma seqüência e realizada com um único contato (a -> b) para o intervalo de tempo [t'beg,t'end] com tbeg <tend. Uma trajetória com respeito ao tempo e usando este contato vai de a -> b no tempo feg, uma trajetória diferente no tempo fnd. Porém, quando LD(e) ≤EA(e), como usualmente é o caso com trajetórias do tipo de multi-salto, uma trajetória pode ser construída partindo no tempo LD(e) que chega no tempo EA(e). Entre todas as trajetórias com respeito ao tempo associado a esta seqüência, esta aqui é ótimo no sentido que é mais eficiente que as outras, em termos de demora.

Uma trajetória com respeito ao tempo, deixando o nó a no tempo tdep, chegando no nó b no tempo tarr, é chamada ótima se nenhuma outra trajetória existir que seja estritamente melhor em termos de tempo de partida/chegada. Em outras palavras, outra trajetória que inicia depois necessariamente chega mais tarde, e outra trajetória que chega mais cedo ne- cessariamente deve ter iniciado antes.

t' dep > t'dep → t arr> tarr e

t' arr < tarr → t' dep < tdep

onde t'deP, t'arr correspondem aos tempos de partida e chegada de outra trajetória indo de a para b.

Dentro de um subconjunto dado de trajetórias com respeito ao tempo, uma trajetó- ria é chamada ótima para este subconjunto se nenhuma outra trajetória do subconjunto for estritamente melhor de acordo com a definição dada acima.

Como um exemplo, o subconjunto de todas as trajetórias associadas a uma se- qüência de contatos e pode ser considerado. As trajetórias ótimas para este subconjunto são caracterizadas uma vez (EA(e),LD(e)) é conhecida. Se LD(e) ≤EA(e), então uma traje- tória que partindo no tempo LD(e) pode ser construída que chega no tempo EA(e), como debatido acima. Está ótimo e todas as trajetórias ótimas partem e chegam necessariamente ao mesmo tempo exatamente.

Se, inversamente, EA(e) < LD(e), isto resulta das definições que, todos os interva- los associados aos contatos em e reconhecem uma interseção em [EA(e);LD(e)]. As trajetó- rias ótimas que partem e chegam a cada tempo selecionado t neste intervalo comum podem depois ser construídas. Estas são as únicas.

A função de chegada é introduzida, para cada fonte a e destino b, que fornece a chegada mais precoce de uma mensagem como uma função de tempo onde pode ser envi- ada pela fonte. Esta função é definida em geral por: del(í) = min {tarr(rT>· t <tdep(TT>}

onde π representa todas as trajetórias com respeito ao tempo, quem pode ser tra- çadas entre a e b no gráfico temporal. Por convenção, é assumida como infinita se nenhuma trajetória existir. Nesta definição, o mínimo pode ser restringido a incluir apenas trajetórias ótimas, sem isto modificando o valor da função.

As características das trajetórias ótimas para uma seqüência dada de contatos e são explicitamente conhecidas e elas são fornecidos por EA(e), LD(e). A expressão a seguir da função de chegada pode ser deduzida daquela que precede: del(t)=max(t, min[EA(e) |t<LD(e)]),(2)

onde o mínimo é tirado entre toda a seqüência de contatos admissível, e, conduzin- do da fonte ao destino.

Em outras palavras, todos os valores e descontinuidades da função de chegada podem ser descritos com base na seqüência de contatos admissíveis, que são diretamente construídos no gráfico temporal. Além disso, esta função depende apenas dos pares (EA1LD) associados a todas estas seqüências.

A função de chegada, e sua representação pela seqüência de pares, é ilustrada pe- Ia figura 2. O tempo t é representado no eixo χ e o valor da função de chegada que pode ser infinito é representado no eixo y. Este esquema é chamado um diagrama cronológico. O esquema na esquerda mostra os pontos com coordenadas associadas aos pares que no meio apresenta o valor tirado pelo mínimo em (2) e à direita, a função de chegada é mostra- da. Três casos complementares são mostrados: os pares 1 e 3 correspondem a um intervalo de conectividade simultânea entre a fonte e o destino, o par 2 mostra um caso similar onde o contato dura apenas um intervalo de tempo, o par 4 não corresponde a uma conectividade simultânea, como os dados têm que partir da fonte e permanecer por um tempo em uma substituição antes de serem liberados. Casos similares são encontrados na prática.

Nos algoritmos apresentados, a função de chegada é sempre mostrada, não dire- tamente como uma função, mas usando sua seqüência associada de pares (LD1EA). De acordo com esta representação, uma coletânea vazia corresponde naturalmente a um par de fonte-destino para o qual nenhuma trajetória existe, e a função de chegada é uma cons- tante de um valor sempre infinito.

O método de acordo com a presente invenção eficientemente processa e mostra o desempenho de todas as trajetórias ótimas em um gráfico temporal, para todos os pares de fonte-destino, em cada tempo de partida. Estas trajetórias ótimas correspondem à melhor possível escolha de transmissão, com base nos contatos oportunistas em uma rede móvel. Como estudo, apenas as trajetórias ótimas podem ser muito restritivas, para isto é mostrado que o mesmo método permite identificação de todas as trajetórias ótimas dentro de certas classes. A noção de optimalidade pode ser desse modo colocada em parâmetro.

O método de acordo com a presente invenção constrói funções de chegada para todos os pares de fonte-destino por indução no conjunto de contatos, ou bordas do gráfico temporal. As funções serão representadas com base nos conjuntos de par (LD, EA).

Duas observações aplicam-se a cada par de fonte-destino:

Muitos pares (LD, EA) associados à seqüência admissível não são requeridos para caracterizar a função de chegada dada por (2). A função pode ser completamente caracteri- zada por um número pequeno de pares, que iguala ao número de descontinuidades e ao número de trajetórias ótimas este par de fonte-destino.

Se o conjunto de pares for organizado na forma de uma lista que é classificada de acordo com a primeira coordenada, esta lista pode ser eficientemente atualizada para incluir outro par (LD, EA) que captura o efeito de outra seqüência de contatos.

Com base nestas técnicas, dois algoritmos foram desenvolvidos:

1) Pesquisa não restritiva:

Para capturar o efeito de todas as trajetórias ótimas, os contatos no gráfico tempo- ral são somados um após outro. A partir de coletâneas vazias e um conjunto de contatos vazios, as coletâneas que representam as funções de chegada para o subgráfico estendido são atualizadas para cada estágio. Quando um contato, uma borda a -> b no gráfico tempo- ral for adicionado, o par associado (LD, EA) é incluído inicialmente na coletânea que corres- ponde à fonte a e ao destino b. Para representar todas as trajetórias que podem passar por esta borda em uma ótima trajetória nova, todas as coletâneas com uma fonte s e um destino a, e as coletâneas com uma fonte b e todos os destinos d são examinados. Não há nenhu- ma necessidade para considerar todos os pares (LD, EA) nestas coletâneas. Alguns entre eles podem não ser completados com a borda nova em uma seqüência admissível, de acor- do com a regra de concatenação previamente apresentada, outros não resultam na defini- ção de trajetórias ótimas novas.

Todas estas operações (concatenação, optimalidade, inclusão em uma função de chegada existente) podem ser decididas na base de valores de pares associados (LD, EA). Afinal de contas estes contatos foram incluídos, a melhor função de chegada é obtida, que particularmente descreve as características de demora de trajetória ótima vistas em cada tempo.

2) Pesquisa com saltos limitados:

Neste algoritmo, uma única concatenação é iterada à direita de todos os contatos com o mesmo conjunto de referências fixas. É iniciado com um conjunto vazio, de forma que a primeira repetição produz todas as trajetórias ótimas de tamanho 1 (como cada contato direto entre os dois terminais é de fato uma ótima trajetória). Na etapa a seguir, o conjunto destas trajetórias é considerado como o novo conjunto de referências, e cada contato é con- catenado novamente com este conjunto, sem modificação. Os resultados são reunidos para obter todas as trajetórias ótimas com um tamanho de pelo menos dois. Conservando o pri- meiro conjunto de trajetórias na memória é depois desnecessário os estágios seguintes.

De acordo com a presente invenção, o dispositivo de comunicação é tipicamente um terminal móvel que compreende um processador, uma memória e meios de comunica- ção com outros dispositivos de comunicação.

O método distribuído de acordo com a presente invenção calcula a posteriori as tra- jetórias que apresentam uma demora ótima de cada fonte para cada destino.

Em uma modalidade, este método compreende dois componentes:

- um roteamento retrógrado que é um cálculo exato da informação relativa às traje- tórias ótimas de demora até o presente, e

- uma transmissão com base em um Iog de evento que é um mecanismo carregado com a extração da informação passada para tomar uma decisão de transmissão.

ROTEAMENTO RETRÓGRADO:

Nesta parte, um estado atual da rede em termos de oportunidades passadas de to- das as fontes para si mesmo é mantido.

Cada nó de rede está agora em uma tabela de roteamento retrógrado, a última tra- jetória de demora ótima de todas as fontes s em direção a si mesmo. Esta trajetória é defini- da como aquela que permite um pacote divergir no último tempo possível de s e chegar ao nó antes do tempo atual t.

Todas as tabelas estão inicialmente vazias. Quando dois nós chegam ao contato, eles trocam o conteúdo de suas tabelas em um tal modo para atualizar seu estado para re- presentar este contato. Isto também permite cada nó seja informado da presença de outras fontes.

Pode parecer excessivo capturar informação que concerne todas as fontes de rede, como um nó pode não ser particularmente interessado por outro nó. Porém, realização de uma seleção por nó terá um impacto na trajetória de uma fonte para este destino particular e isto também eliminará todas as trajetórias que poderiam usar este destino como uma substi- tuição para trocar dados.

Quando dois nós encontrarem um com o outro repetidamente, é possível evitar a troca de entradas redundantes.

ENVIO COM BASE EM HISTÓRIA

Inicialmente, a informação é extraída das tabelas de roteamento retrógrado em um estado de evolução constante: estatísticas podem ser colhidas concernindo àquelas que tinham sido uma substituição para as trajetórias ótimas de demora.

Secundariamente, a informação é usada para realizar a transmissão dos pacotes de dados.

Figura 4 mostra um cenário com sete nós. Cinco nós são estáticos durante este pe- ríodo: eles são distribuídos em dois agrupamentos AeB contendo dois e três nós respecti- vãmente. Dois nós estão em movimento em regiões diferentes. Um dos dois, em particular, entra em contato com os dois agrupamentos estáticos em vários tempos diferentes.

O estágio de roteamento retrógrado apresentado acima opera como segue neste exemplo:

No tempo t = 1, as tabelas de roteamento retrógrado contêm apenas nós estáticos e os nós móveis contêm trajetórias de todos os nós do agrupamento B.

No tempo t = 2, os nós móveis no meio entram em contato com o outro agrupamen- to. Eles transmitem desse modo através da transitividade uma ótima trajetória de demora de todos os nós no agrupamento B para todos os nós no agrupamento A. Este é refletido ime- diatamente pelo nó no agrupamento A.

No tempo t = 3, os nós móveis em contato com B atualizam todas suas trajetórias na partida deste agrupamento, e cria trajetórias novas de todos os nós do agrupamento A no tempo t = 2, para os nós de agrupamento B. Além disso, o nó mais à esquerda entra em contato com os nós do agrupamento A: ele herda as trajetórias do agrupamento A inteiro com um tempo de partida igual a t =3, e as trajetórias do agrupamento B com um tempo de partida f = 1.

No tempo t = 4, o nó móvel repete um segundo contato em A. Ele atualiza todas as trajetórias e obtém uma entrada que corresponde ao nó móvel mais à esquerda pela primei- ra vez.

No tempo t = 5, cada nó móvel entra em contato com um agrupamento, em particu- lar o agrupamento B. Este agrupamento compreende pela primeira vez uma trajetória inicia- da do nó móvel mais à esquerda.

Naquele momento, a rede é conectada, que é uma trajetória que foi encontrada pa- ra todos os pares (fonte, destino).

Certas operações com base na história podem tornar a transmissão mais eficiente.

Se um pacote usado para criar no nível do nó móvel mais à esquerda deve ser en- viado para o agrupamento B, ele pode decidir, com base no contato realizado no tempo t = 3, deixar uma cópia no agrupamento A, porque viu pela primeira vez uma trajetória de B para si mesmo, passando por meio de A. De fato, seguindo a mesma regra, os nós do agru- pamento A dão o pacote ao nó móvel no meio de tempo t = 4, que depois dão ao destino no tempo t = 5.

Muito rapidamente, os nós dos dois agrupamentos podem identificar que o nó mó- vel no meio é uma opção boa para a transmissão de pacotes para o outro agrupamento.

FORMATO DE TABELA DE ROTEAMENTO RETRÓGRADO

Dois campos são necessários para cada entrada: a fonte (identificada pelo endere- ço MAC ou por outra assinatura exclusiva), e o tempo que foi identificado como a última par- tida desta fonte. Esta informação é suficiente para manter a tabela em um estado atualizado, mas esta não permite seleção de uma ou mais substituições particulares, como apenas a distância (ou demora da ótima trajetória) entre cada fonte e um nó é descrita. Outro campo pode ser adicionado. Ele pode conter, por exemplo:

-a identidade do último transmissor,

-a lista completa de substituições em uma trajetória,

-o tempo quando a trajetória foi registrada (correspondendo ao último contato usa- do por esta trajetória),

-a lista de substituições usadas e o tempo de transição entre elas, para esta traje- tória.

Uma tabela de exemplo é fornecida na tabela a seguir:

<table>table see original document page 10</column></row><table>

Tabela 1 - Exemplo de uma tabela de roteamento retrógrado.

A tabela está inicialmente vazia. Quando /'e j se encontram, eles inicialmente inicia- lizam ou atualizam a entrada relativa uma ao outro.

<table>table see original document page 10</column></row><table>

Tabela 2

Secundariamente, eles trocam suas tabelas de roteamento retrógrado atuais.

Quando um nó recebe uma entrada nova, para uma fonte s e uma última partida t':

-se não houver nenhuma entrada para esta fonte, ele a adiciona a sua tabela: -se já houver uma entrada para esta fonte, ele compara o tempo da última partida e atualiza-a com o valor mais alto. Quando uma entrada for inicializada ou atualizada, a informação relativa à trajetória usada é concatenada com aquela recebida.

É possível restringir o número de entradas trocadas, por exemplo, não enviando certas entradas.

A invenção é descrita no texto precedente como um exemplo. É entendido que a- queles versados na técnica são capazes de produzir variantes da invenção sem abandonar o escopo da patente.

Claims

1. Dispositivo de comunicação em uma rede de comunicação compreendendo pelo menos dois dispositivos de comunicação, CARACTERIZADO pelo fato de que compreende meios para: - armazenar para cada par (fonte, destino) dos dispositivos de rede, trajetórias na forma de listas de pares (LD, EA), EA sendo a Chegada Mais Precoce e LD sendo a Última Partida, para qualquer seqüência de contatos entre os dispositivos, e - transmitir dados para outro dispositivo por um nó selecionado usando história das trajetórias anteriores observadas.

2. Dispositivo de comunicação, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que a dita rede de comunicação é do tipo de troca de paco- tes, em que compreende meios para: - criar, para os pares (fonte, destino) da dita rede, funções que forneçam, em cada tempo, o tempo de chegada mais prematuro para cada pacote criado, e - representar estas funções com base nos conjuntos de pares (LD, EA).

3. Dispositivo de comunicação, de acordo com a reivindicação 1 ou 2, CARACTERIZADO pelo fato de que a dita rede é uma rede do tipo PAN (Rede de Área Pessoal).

4. Dispositivo de comunicação, de acordo com a reivindicação 1 ou 2, CARACTERIZADO pelo fato de que a dita rede é do tipo ad-hoc sem fios.

5. Dispositivo de comunicação, de acordo com a reivindicação 3, CARACTERIZADO pelo fato de que a dita rede é do tipo Bluetooth.

6. Dispositivo de comunicação, de acordo com a reivindicação 1 ou 2, CARACTERIZADO pelo fato de que a dita rede é do tipo Wi-Fi.

7. Dispositivo de comunicação de acordo com qualquer uma das reivindicações pre- cedentes, CARACTERIZADO pelo fato de que um dispositivo de comunicação da dita rede é identificado por um endereço MAC (Controle de Acesso à Mídia).

8. Método de comunicação em uma rede de comunicação compreendendo pelo menos dois dispositivos de comunicação, CARACTERIZADO pelo fato de que compreende as etapas que consistem em: - armazenar para cada par (fonte, destino) dos dispositivos de rede, trajetórias na forma de listas de pares (LD, EA), EA sendo a Chegada Mais Precoce e LD sendo a Última Partida, para qualquer seqüência de contatos entre os dispositivos, e - transmitir os dados para outro dispositivo por um nó selecionado usando história das trajetórias anteriores observadas.

9. Método de comunicação, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de que a dita rede de comunicação é do tipo de troca de pacotes, em que compre- ende as etapas que consistem em: - criar, para os pares (fonte, destino) da dita rede, funções que forneçam, em cada tempo, o tempo de chegada mais prematuro para cada pacote criado, e - rpresentar estas funções com base nos conjuntos de pares (LD, EA).