Routing ispirato alle falene

In questo post analizzeremo un algoritmo di routing progettato per reti wireless di grandi dimensioni, ispirato al volo compiuto dal maschio della falena Bombyx mori (comunemente noto come Baco da seta) quando cerca una femmina con cui accoppiarsi. Quando una femmina di questa specie è pronta per l'accoppiamento, emette un feromone; il maschio, intercettato il feromone, si mette alla ricerca della femmina.
La sua ricerca è riassumibile in tre step, che il maschio effettua uno dopo l'altro:

• Innanzitutto, vola seguendo una traettoria dritta;
• Successivamente, esegue una traettoria a zigzag verso la sorgente del feromone;
• Infine, esegue un volo circolare fino a quando non trova la femmina.

A sinistra, un esemplare di Bombyx mori; a destra, il volo eseguito dal maschio durante la ricerca della femmina.

L'algoritmo di routing si ispira principalemte ai primi due step, infatti interpreta il volo dritto della falena eseguendo un algoritmo shortest path e, prima di raggiungere la destinazione, effettua delle scelte di forwarding che ricordano l'andamento a zigzag. La fase finale, ovvero il volo circolare, viene invece ignorata.

Fase 1: traettoria dritta

In questa fase ogni nodo della rete wireless riceve dai nodi adiacenti le tabelle delle connessioni vicine. Ogni nodo, quindi, oltre a conoscere le proprie connessioni, è consapevole anche di quelle dei suoi vicini. Questa logica fa riferimento ai comuni algoritmi Distance Vector, in cui ogni nodo conosce solo lo stato dei nodi adiacenti e non di tutta la rete (come invece accade con gli algoritmi link state).

Una volta completata questa fase, ogni nodo sarà in grado di determinare il percorso più breve per raggiungere un nodo di destinazione. Tuttavia, il percorso più breve sarà percorso solo nella prima metà, per poi continuare con un andamento a zigzag. Ad esempio, se consideriamo un nodo A come sorgente e un nodo B come destinazione, e il percorso più breve tra A e B ha una lunghezza pari a 10, i primi cinque hop verranno effettuati seguendo il percorso più breve, mentre gli ultimi cinque seguendo la logica zigzag.

Fase 2: traettoria zigzag

Dopo aver completato la prima metà degli hop seguendo la logica shortest path, inizia il forwarding dei dati seguendo la logica zigzag. Quindi, ogni nodo della parte zigzag, quando deve scegliere il prossimo nodo a cui inviare i dati, lo fa tenendo in considerazione solo i nodi che non fanno parte del cammino minimo e che si trovano più vicini alla destinazione rispetto ad esso. Tale scelta è possibile perché ogni nodo ha a disposizione le informazioni ottenute dai propri vicini e il cammino minimo per raggiungere la destinazione.

Questo approccio potrebbe sembrare poco efficiente, siccome il percorso zigzag non rispetta il cammino minimo; tuttavia, è stato dimostrato che in alcune reti wireless, tale approccio garantisce una minore perdita di pacchetti e una migliore efficienza energetica. Infatti, quando un nodo destinazione riceve i dati durante il percorso, non vengono utilizzati sempre gli stessi nodi, ma il carico computazionale viene diviso tra più nodi grazie alla logica zigzag.