Extended DCEL data structure for mobile computing

摘要

Face routing is one of the effective techniques for constructing source destination route in mobile ad-hoc networks (MANET). Face routing can always construct path if the MANET is connected. However, face routing can generate routes with large number of hops. We propose an improved face routing algorithm that constructs shorter routes even when the route is forced to go through a face with large number of edges. We propose a new data structure ExtDCEL that can be used to represent both planar and nonplanar networks. We present an implementation of several location based routing algorithms by using the proposed data structure.