Delaunay Triangulation based Spanners for MANET

Abstract

Many position based routing protocols use Unit Disk Graph (UDG) as an underlying network topology for routing. Due to large number of edges in UDG, these protocols suffer from channel contention overhead, frequent packet collisions, and heavy resource consumption. To overcome these problems, many researchers proposed various local topology control algorithms to retain only linear number of links in the underlying network graph based on geometric neighborhood. These graphs are called geometric spanners. In this thesis, we study these spanners under various network requirements like less number of transmissions, frequent node failure, mobility, and fault tolerance. Geometric spanners, like planarized local Delaunay triangulation (PLDel), relative neighborhood graph (RNG), and gabriel graph (GG) which are based on neighborhood properties contain shorter edges. Because of these shorter edges the number of transmissions between source and destination increases which in turn increases the end-to-end packet delay and jitter. We present three planar constrained based geometric graphs called constrained local Delaunay triangulation (CDT), constrained relative neighborhood graph (CRNG), and constrained Gabriel graph (CGG), to reduce the number of hops by introducing longer constraint edges.In adhoc networks, nodes can go down due to various reasons, such as insuf cient battery power, environmental effects like eruption of volcano, cyclones, and oods, and accidents like landslides and debris. Moreover, to conserve the energy, nodes can switch off their transmitter or go to the sleep mode. There will be heavy packet loss if these nodes exist in any routing path. Similarly, a new node can join the network or an existing node wakes up from sleep mode. We have proposed three dynamic spanners called dynamic local Delaunay triangulation (DLDel), dynamic relative neighborhood graph (DRNG), and dynamic Gabriel graph (DGG), which change their network topology dynamically to preserve the spanner properties and reduce heavy packet loss.Various resource limitations and environmental constraints make frequent link and node failures in adhoc networks, which make the network unreliable. For example, the edge disconnections occur due to buildings, walls, mountains, and obstacles between the wireless nodes. Similarly, the node failures occur due to the exhausted battery power, accidents, landslides, debris, eruption of volcano, and cyclones. So, network topology should be fault tolerant to take care of these failures. In this thesis, we have proposed the algorithms for fault tolerant versions of PLDel, RNG and GG called fault tolerant local Delaunay triangulation (FTLDel), fault tolerant relative neighborhood graph (FTRNG), and fault tolerant Gabriel graph (FTGG), respectively, by choosing most stable nodes. The existing spanners assume that the nodes in the network are static. The frequent topology change due to node mobility disturbs various geometric properties of the spanner such as neighborhood relations, spanning ratio, and planarity. Moreover, some of the edges may become invalid links and may lead to disconnected network. In this thesis, we propose the algorithms for mobile local Delaunay triangulation (MLDel), mobile relative neighborhood graph (MRNG), and mobile Gabriel graph (MGG), to maintain their counter part spanners PLDel, RNG, and GG, respectively, under mobility. These proposed spanners are simulated...