Os protocolos de encaminhamento utilizados em redes ad-hoc m´oveis n˜ao tˆem no¸c˜ao de liga¸c˜ao f´ısica. Assim, para tomar conhecimento da sua vizinhan¸ca, e por forma a poder estabelecer uma liga¸c˜ao l´ogica, um n´o recorre ao envio/recep¸c˜ao peri´odico de mensagens em modo broadcast, tamb´em conhecidas por beacons1
. A dura¸c˜ao de uma liga¸c˜ao estabele- cida entre dois n´os ´e caracterizada pelo n´umero de beacons recebidos ininterruptamente. Por exemplo, se um n´o 𝑛𝑎 receber de uma forma sucessiva 15 beacons do n´o 𝑛𝑏, ent˜ao 𝑛𝑎 pode afirmar que a sua liga¸c˜ao l´ogica com 𝑛𝑏 tem a dura¸c˜ao de 15 per´ıodos de beacons.
Antes de se iniciar a descri¸c˜ao do algoritmo ´e necess´ario fazer a distin¸c˜ao entre vizinhan¸ca f´ısica apresentada no Cap´ıtulo 3 e o conceito de vizinhan¸ca l´ogica, tendo em conta que agora existe um meio l´ogico de identifica¸c˜ao de vizinhos f´ısicos. S˜ao ainda definidos alguns conceitos e assumidas liga¸c˜oes bidireccionais entre dois n´os.
Defini¸c˜ao 4.1. No¸c˜ao de Vizinhan¸ca L´ogica:
Seja 𝑁𝑥 o conjunto de n´os de quem o n´o 𝑛𝑥 recebe beacons durante um determinado intervalo de tempo. 𝑁𝑥 representa o conjunto de n´os vizinhos l´ogicos de 𝑛𝑥.
Note-se que a Defini¸c˜ao 3.1 se refere `as condi¸c˜oes necess´arias para o estabelecimento de comunica¸c˜ao f´ısica entre dois n´os. A no¸c˜ao de vizinhan¸ca l´ogica ´e mais restrita, pois dois n´os podem ser vizinhos (segundo a Defini¸c˜ao 3.1), mas, devido `a n˜ao recep¸c˜ao de beacons num dado intervalo de tempo, a rela¸c˜ao de vizinhan¸ca l´ogica pode n˜ao se verificar. Daqui em diante, a menos que seja dito algo em contr´ario, a utiliza¸c˜ao do termo vizinho refere-se `
a Defini¸c˜ao 4.1.
1Tramas de envio peri´odico normalmente utilizadas pelos protocolos de encaminhamento para desco-
O envio peri´odico de beacons ´e realizado com uma frequˆencia de 1/𝑇𝐵. Considera-se o instante 𝑡𝑖(𝑛𝑦) em que um n´o(𝑛𝑎) recebe o primeiro beacon transmitido pelo seu vizinho 𝑛𝑦, estabelecendo-se uma liga¸c˜ao l´ogica entre os n´os (𝑛𝑎 e 𝑛𝑦). Define-se, de seguida, o conceito de estabilidade da liga¸c˜ao l´ogica.
Defini¸c˜ao 4.2. Estabilidade da Liga¸c˜ao L´ogica:
Um n´o 𝑛𝑎que receba beacons de um n´o vizinho 𝑛𝑦 possui um determinado valor de estabi- lidade 𝜂 com esse vizinho. A estabilidade 𝜂(𝑛𝑦) afere a dura¸c˜ao da rela¸c˜ao de vizinhan¸ca entre os n´os. O valor de 𝜂(𝑛𝑦), determinado pelo n´o 𝑛𝑎 no instante temporal 𝑡, ´e dado pela express˜ao 𝜂(𝑛𝑦) = 1 + (𝑡− 𝑡𝑖(𝑛𝑦)) div 𝑇𝐵, onde 𝑎 div 𝑏 representa a opera¸c˜ao de divis˜ao inteira entre 𝑎 e 𝑏.
Os n´os mantˆem uma tabela de beacons (tamb´em denominada tabela de vizinhos l´ogicos) que descreve as liga¸c˜oes l´ogicas desse n´o com os seus n´os vizinhos. Os n´os vizinhos s˜ao representados por cada um dos registos da tabela de beacons, que nesta fase do algoritmo ´e constitu´ıda por:
∙ O endere¸co do n´o vizinho que envia o beacon (𝑛𝑦 ∈ 𝑁𝑥).
∙ Um campo tempor´ario utilizado pelo algoritmo contendo o valor da estabilidade da liga¸c˜ao com esse vizinho (𝜂(𝑛𝑦)), sendo actualizado no instante em que ´e executado o algoritmo.
∙ O instante 𝑡𝑖(𝑛𝑦) em que foi recebido o primeiro beacon. ∙ O intervalo de tempo 𝑇𝑂(𝑛𝑦) em que o registo ainda ´e v´alido
O n´umero de registos contidos na tabela ´e finito, e, ap´os atingir o limite m´aximo a- dmiss´ıvel, n˜ao ´e poss´ıvel adicionar novos registos `a tabela.
Tendo em conta a Defini¸c˜ao 4.2, ´e poss´ıvel ent˜ao determinar, quando ´e que uma liga¸c˜ao que apresente uma certa dura¸c˜ao pode ser considerada como uma liga¸c˜ao est´avel.
Defini¸c˜ao 4.3. Estabilidade de liga¸c˜ao:
𝑡 se:
𝜂(𝑛𝑦)≥ 𝑘𝑒𝑠𝑡,
onde 𝑘𝑒𝑠𝑡 ´e um limiar de estabilidade previamente definido, e 𝜂(𝑛𝑦) representa o valor da estabilidade da liga¸c˜ao.
Adaptando a Defini¸c˜ao 4.3 aos cen´arios de auto-estrada estudados no final do Cap´ıtulo 3, ao ser definido 𝑘𝑒𝑠𝑡 = 50, apenas 15% das liga¸c˜oes ser˜ao consideradas est´aveis sendo as restantes consideradas liga¸c˜oes inst´aveis. Tomemos por exemplo um cen´ario mais simples. Na Figura 4.1 ´e apresentada uma rede composta por 6 n´os onde as linhas a tracejado representam as rela¸c˜oes de vizinhan¸ca existentes.
Figura 4.1: Rede ad hoc constitu´ıda por 6 n´os (𝒩 = {𝑛1, 𝑛2, 𝑛3, 𝑛4, 𝑛5, 𝑛6}).
A Tabela 4.1 apresenta valores hipot´eticos para a tabela de beacons do n´o 𝑛3 representado na Figura 4.1. A tabela apresenta trˆes registos (linhas) relativos aos n´os vizinhos 𝑛1, 𝑛2 e 𝑛4. O n´o 𝑛3 possui uma liga¸c˜ao l´ogica com o vizinho 𝑛1 h´a 65 m´ultiplos do per´ıodo de beacon (𝑇𝐵) sem que o temporizador associado ao registo da tabela desse vizinho tenha expirado. Desta forma, diz-se que a liga¸c˜ao mais est´avel do n´o 𝑛3 ´e a que mant´em com o n´o 𝑛1. Se, por exemplo, considerarmos esta tabela de beacons retirada de algum n´o que perten¸ca aos cen´arios de auto-estrada, ent˜ao a ´unica liga¸c˜ao realmente est´avel que o n´o 𝑛3 tem com algum dos seus vizinhos ´e com o n´o 𝑛1, pois as liga¸c˜oes com o n´o 𝑛2 e o n´o 𝑛1 ainda n˜ao atingiram 𝑘𝑒𝑠𝑡 = 50.
Tabela 4.1: Exemplo do conte´udo da tabela de beacons do n´o 𝑛3 representado na Figura 4.1 no instante 𝑡 =102.5s, sendo 𝑇𝐵 = 1s. 𝑁3 ={𝑛1, 𝑛2, 𝑛4} 𝜂(𝑛𝑦),∀𝑛𝑦 ∈ 𝑁3 𝑡𝑖(𝑛𝑦) 𝑇𝑂(𝑛𝑦) 𝑛1 65 37.2 𝑘1 𝑛2 30 72.3 𝑘2 𝑛4 2 100.1 𝑘4
signadas de liga¸c˜oes est´aveis, ´e poss´ıvel ent˜ao excluir as liga¸c˜oes existentes entre ve´ıculos que circulam em sentidos opostos. Para tal, basta parametrizar o limiar de estabilidade, de forma a que os valores de estabilidade estejam directamente relacionados com a velocidade relativa dos ve´ıculos que circulam em sentidos opostos. Para 𝑘𝑒𝑠𝑡 = 50 todas as liga¸c˜oes que apresentem uma dura¸c˜ao inferior a 50 segundos ser˜ao consideradas liga¸c˜oes inst´aveis.
´
E importante ainda referir que, sendo um algoritmo que se baseia no n´umero de bea- cons recebidos por forma a caracterizar uma liga¸c˜ao, apresenta uma grande vantagem em cen´arios de elevada mobilidade. Nos cen´arios gerados, a parametriza¸c˜ao do limiar de es- tabilidade com o valor de 50 segundos ´e suficiente para distinguir os ve´ıculos que circulam em sentidos opostos. No entanto, se o algoritmo for aplicado, por exemplo num cen´ario citadino, o limiar de estabilidade vai necessariamente ser mais elevado, fazendo com que a caracteriza¸c˜ao das liga¸c˜oes relativamente `a sua estabilidade seja mais demorado.