|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
Ad hoc networks consist of small devices which are communicating wireless without using a fixed network infrastructure. Due to limited transmission range, communication between two nodes often requires collaborating intermediate nodes in order to route messages along a path connecting source and destination node. Exploring the faces of a planar graph is a scalable routing solution which guarantees message delivery while enabling routers to operate in a localized manner, i.e. the operation of the routing algorithm only requires location information about the current forwarding node, the nodes in vicinity, and the final destination. This presentation addresses the class of geographical cluster based routing algorithms which are a recently studied variant of planar graph routing. At this, face exploration is performed along the edges of an overlay graph connecting geographical clusters instead of using the network links directly. In order to define geographical clusters, the plane is partitioned by an infinite mesh of regular hexagons, while each hexagon defines one cluster. Two geographical clusters C and D are denoted as adjacent, if there are at least two connected network nodes with one located in C and the other located in D. The presentation will show some of the benefits of geographical cluster based routing compared to the original planar graph routing method. In general, the graph resulting from adjacent clusters is not necessarily planar. Thus, before face routing can be applied, a planar subgraph has to be constructed in advance. It has been observed that there exist node placements which result in a connected physical network while any planar overlay graph which is constructed by simply removing edges from that graph is disconnected. The talk discusses a recently discovered extension of the geographical clustering concept by means of virtual edges which provides a solution to this disconnection problem. Host: Peter Kornerup SDU HOME | IMADA HOME | Previous Page Last modified: Wed Nov 23 10:08:50 CET 2005 Joan Boyar (joan@imada.sdu.dk) |