Abstract

We introduce a new approach in ad hoc networks for obtaining a sensing-covered network in the 2-D environment. This approach is based on a grid technique and the unit disk graph ( UDG ). This technique makes sure that a region is fully covered by a small number of sensor nodes. To experiment with variations of the generated graph, we introduce a new subgraph of the UDG. This graph is a generalization of the Yao graph in 2-D environment where the cones used are adaptively centered on a set of nearest neighbors for each node, thus creating a directed or undirected spanning subgraph. We also permit the apex of the cones to be positioned anywhere along the line segment between the node and its nearest neighbor, leading to a class of Yao -type subgraphs. We give an extension of the DAAY (both directed and undirected) from the 2-D environment to the 3-D environment. For routing on such a 2-D sensing-covered sensor network topology, we propose new routing protocols. Some of these new routing algorithms include hybrid routing algorithms which are based on the BVGF routing protocol of Xing et al. (2006) and our own protocols. The reason for these combinations is that we show that the BVGF routing protocol does not guarantee delivery all the time on general sensing covered networks. Our hybrid algorithms do guarantee delivery on such networks. We demonstrate through simulations that our proposed routing protocols perform much faster compared to some existing routing protocols. We also compare the routing protocols based on the path lengths (hops or Euclidean distances). Our routing protocols show good performance in terms of these metrics.