CENS Technical Seminar Series

A Shortest Anypath Algorithm for Opportunistic Routing

Invited Speaker: Rafael Laufer, CS, UCLA
Date: February 15, 2008
Time: 1:00 PM - 2:00 PM
Venue: Boelter Hall 4760

Abstract

Opportunistic routing protocols have been recently proposed as a new paradigm to improve the performance of wireless networks. Instead of using a single next hop to reach a given destination, a packet is sent to multiple nodes simultaneously in order to increase the packet delivery rate. One of the receiving nodes then forwards the packet towards the destination. In this talk, we address the problem of selecting the best forwarding set that minimizes the cost of each node to the destination, the so-called shortest anypath problem. We introduce a shortest-anypath algorithm, which generalizes Dijkstra’s algorithm for the anypath case to find the least-cost set of neighbors to be used as next hops to a particular destination. We prove its correctness and show that the proposed algorithm always provides a lower cost than regular single-path routing. With optimizations, the proposed algorithm runs in the same polynomial time as Dijkstra’s algorithm, even though the search space is exponentially larger than the single-path routing case.

Biography

Rafael Laufer obtained his BS and MS in Electrical Engineering from Universidade Federal do Rio de Janeiro (UFRJ), Brazil in 2003 and 2005, respectively. He received the FAPERJ fellowship awarded to the top 2 students of the department. During 2002, he was with Cisco Systems, Inc. He is currently a PhD student in the Center for Embedded Networked Sensing (CENS) at UCLA. Recently, he is working with opportunistic routing in wireless networks and his major research interests are distributed systems, security, and networking.