• Algorithms and Networks
• Probabilistic Network Models

Greedy Embedding and Greedy Zone Routing

Despite various research efforts geographic routing has not made its way to become a protocol in real network settings. We identify that the most difficult thing in practice with respect to geographic routing is to build and maintain a globally consistent geographic structure. In order to overcome this barrier we propose a clustered approach, where the geometric structure is maintained in as an overlay between clusters as opposed to individual nodes. Therefore geographic routing performed between clusters, avoiding the use of routing tables.

Keywords: Graph embedding, Triangulated graphs, local algorithms

Publications:

Samarasinghe K, Leone P Greedy Zone Routing:Scalable Routing in Large Scale Wireless Ad-hoc Networks, IEEE SECON 2015

Samarasinghe K, Wehbe R, Leone P Greedy Zone Routing:Scalable Routing in Large Scale Wireless Ad-hoc Networks, IEEE AINA 2016

Keywords: Greedy Embedding, Planar Graphs, Delaunay Triangulation, Isometric Tree Embeddings

Combinatorial Approach for Geographic Routing

We investigate an alternative approach for characterizing geographic routing. Schnyder characterization of planar graphs and Schnyder coordinates are used for this. One of the aims of this work is to allow greedy routing to perform without explicitly computing a greedy embedding.

Publications:

Leone P, Samarasinghe K Greedy Routing on Virtual Raw Anchor Coordinate (VRAC) System, IEEE DCOSS 2016

Leone P, Samarasinghe K Geographic Routing on Virtual Raw Anchor Coordinate Systems, Elsevier Theoretical Computer Science 2015

Samarasinghe K, Leone P Combinatorial Approach for Geographic Routing with Delivery Guarantees, SENSORNETS 2014

Samarasinghe K, Leone P Geographic Routing with Minimum Local Geometry, IEEE ICPADS 2012

Keywords: Combinatorics, Planar Graphs