Bilkent University
Department of Computer Engineering

Implementation Issues of Trajectory-Based

Routing in Ad-Hoc Networks


Murat Yüksel

Rensselaer Polytechnic Institute,

Troy, NY


Routing in ad-hoc networks is a complicated task because of many reasons. The nodes are low-memory, low-powered; and they cannot maintain routing tables large enough for well-known proactive routing protocols. Because of that, greedy forwarding at intermediate nodes is desirable in ad-hoc networks. Also, for traffic engineering, multi-path capabilities are important. So, it is desirable to define routes at the source like in Source Based Routing (SBR) while performing greedy forwarding at intermediate nodes. We investigate Trajectory-Based Routing (TBR) which was proposed as a middle-ground between SBR and greedy forwarding techniques. In TBR, the source node encodes trajectory to be traversed and embeds it into each packet's header. Upon the arrival of each packet, intermediate nodes decode the trajectory and employ greedy forwarding techniques such that the packet follows its trajectory as much as possible. In particular, we address various issues regarding implementation of TBR. We also provide techniques to efficiently forward packets along a trajectory defined as a parametric curve. We use the well-known Bezier parametric curves for encoding trajectories into packets at source. Based on this trajectory encoding, we develop and evaluate various greedy forwarding algorithms. We also propose a methodology to implement long and/or complex trajectories that cannot be encoded in a small size packet header.

DATE: April 22, 2004, Thursday @ 13:40