Title: GPS based routing in wireless networks Speaker: Professor Ivan Stojmenovic Computer Science, SITE, University of Ottawa Email: ivan@site.uottawa.ca Abstract: A broad variety of location dependent services will become feasible in the near future due to the use of the Global Position System (GPS), which provides location information (latitude, longitude and height) and global timing to sensors or mobile users. The task of sending a message from a source to destination in a wireless network is known as the routing problem. In a distributed (or localized) algorithm, each node forwards the message towards the destination solely based on the location of itself, its neighbors and destination. Recently, several distributed GPS based routing protocols for a mobile ad hoc network were reported in literature. They are variations of directional (DIR) routing methods, in which node A (the source or intermediate node) transmits a message m to one or several neighbors whose direction is closest to the direction of D. We also found an older, MFR (most forward progress within radius) method. We propose a new location based GEographic DIstance Routing (GEDIR) algorithm. When node A wants to send m to node D, it forwards m to it^Òs neighbor C which is closest to D among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. 2-hop, flooding, and multiple path GEDIR, DIR, and MFR methods are also suggested. We show that the directional routing methods are not loop-free, and prove that the GEDIR and MFR methods are inherently loop free. The power needed to route a message from source to destination is, perhaps, more important performance measure than the hop count between them. Based on any formula that finds the power needed to transmit or receive message between two nodes on the basis of distance between them, we propose efficient power, cost, and power-cost distributed routing algorithms, and prove that they are loop-free. Wireless networks are best modeled by unit graphs, where nodes are connected by an edge iff the distance between them is at most R (the radius of the graph). We show how to eliminate some edges from a connected unit graph and obtain its planar connected subgraph. A well known face tracing (FACE) algorithm that always finds a path between two nodes in a planar connected graph is then modified to reduce the path length and still guaranty the delivery (without memorizing the past traffic at any node, or making multiple copies of m in the network). An efficient routing algorithm that guaranties the delivery (called GFG) is then obtained by switching back and forth between GEDIR and FACE routing schemes. Routing starts with GEDIR algorithm until delivery or failure. In case of failure at a node X, it switches to FACE algorithm until a node closer to destination than X is detected, and returns back to GEDIR until delivery (or next failure). The performance of GFG algorithm can be improved if network is reduced to a set of internal nodes, so that each node is either internal or directly connected to an internal node. This reduces the frequency of invoking FACE scheme. Power, cost, and power-cost routing algorithms that guaranty the delivery can be similarly obtained by combining them with FACE algorithm that is invoked in case of failure of a basic method, called off when a chance for recovery emerges, and by running them on internal nodes only until destination is reached in the last hop. The performance of all mentioned routing algorithms is being measured on static networks, with plans to test the best of these methods for the case of moving nodes, by combining these routing algorithms with a novel scheme for periodic location updates of nodes. Joint research with several students and colleagues and (to be) published in several papers. --------------------------------------------------------------------- Short biography Professor Stojmenovic received the B.S. and M.S. degrees in 1979 and 1983, respectively, from the University of Novi Sad and Ph.D. degree in mathematics in 1985 from the University of Zagreb. He earned a third degree prize at International Mathematics Olympiad for high school students in 1976. In 1980 he joined the Institute of Mathematics, University of Novi Sad (Yugoslavia). In Fall 1988, he joined the faculty in the Computer Science Department at the University of Ottawa (Canada), where currently he holds the position of a Full Professor in SITE. He published three books and over 140 different papers in journals and conferences. His research interests are wireless networks, parallel computing, multiple-valued logic, evolutionary computing, neural networks, combinatorial algorithms, computational geometry and graph theory. He is currently a managing editor of Multiple-Valued Logic, an International journal, and an editor of the following journals: Parallel Processing Letters, IASTED International Journal of Parallel and Distributed Systems, Discrete Mathematics and Theoretical Computer Science, Parallel Algorithms and Applications, and Tangenta.