文摘
A randomly deployed large-scale wireless ad hoc network is naturally represented by an r-disk graph over a random point set. Relative neighborhood graph (RNG) has been widely used in localized topology control and geographic routing in wireless ad hoc and sensor networks. If all the nodes have the same transmission radii, the maximum edge length of the RNG is the smallest transmission radius for constructing the RNG by using only 1-hop neighbor information and it is referred to as the critical transmission radius of the RNG. The critical transmission radius of the RNG is the minimum requirement on the maximum transmission radius by those applications of RNG. Greedy forward routing (GFR) is attractive in wireless ad hoc and sensor networks due to its efficiency and scalability. GFR may discard a packet before it reaches its destination if the transmission radii of the nodes are small. To ensure that every packet can reach its destination, all nodes should have sufficiently large transmission radii. The critical transmission radius of a planar node set V for greedy forward routing is the smallest transmission radius by V which ensures successful delivery of any packet from any source node in V to any destination node in V. In this thesis, we conduct probabilistic studies on the critical transmission radius for the RNG and GFR.