VLSI Implementation of Greedy based Distributed Routing Schemes for Ad Hoc Networks

We describe a VLSI implementation based on a FPGA of a new greedy algorithm for approximating minimum set covering in ad hoc wireless network applications. The implementation makes the algorithm suitable for embedded and real-time architectures. The algorithm, while not randomized, is based on a probability distribution that leads the greedy choice. The algorithm has been specifically tailored to run on platforms with minimal computational hardware.

Descriviamo un'implementazione VLSI basata su FPGA di un nuovo algoritmo greedy per approssimare il minimum set cover per applicazioni in reti wireless ad hoc. L'implementazione rende l'algoritmo adatto per architetture embedded e real-time. L'algoritmo, sebbene non randomizzato, si basa su una distribuzione di probabilità che guida la scelta greedy. L'algoritmo è stato studiato appositamente per funzionare su piattaforme con un hardware computazionale minimo.