Font Size: a A A

Research On Key Technologies Of Connectivity And Routing In Wireless Networks

Posted on:2011-01-03Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y J LiFull Text:PDF
GTID:1118360308965870Subject:Computer system architecture
Abstract/Summary:PDF Full Text Request
Wireless networks can gather, process and disseminate information in a decentralized and self-organized manner without fixed infrastructure, which makes them suitable to a variety of application scenarios. In many of these application scenarios, nodes that are apart more than a radio's transmission range can communicate with each other through packet relaying. To ensure the success of such packet relaying, the network must maintain a certain level of connectivity, and a routing algorithm is needed to forward packets from the source node to the destination node. Hence, the connectivity and routing problems in wireless networks have received significant attention since wireless networks were originally proposed.This dissertation mainly focuses on some fundamental connectivity and routing problems to be solved in wireless networks, including the radio propagation model's impact on the connectivity of wireless networks, connectivity analysis for dynamic spectrum access networks, the compatibilities between routing metrics and geographic routing protocols, and the design of new geographic routing algorithms.The major contributions of this dissertation are as follows:1. We study the log-normal shadowing model's impact on the connectivity in wireless networks, and an analytical upper bound on the critical node density for the percolated wireless network is derived.The log-normal shadowing model has been confirmed empirically to accurately capture the variation in received signal power in radio propagation environments. Based on this model, a connection function is first introduced, and then the connectivity of a wireless network is modeled as a percolation problem of a special kind of random graph. From a percolation-based perspective, an analytical upper bound on the critical node density for the percolated wireless network is derived. Furthermore, we also provide a more accurate estimation for the upper bound based on the previous empirical studies on purely random geometric graph, called the experiment-based upper bound. The correctness and tightness of these two upper bounds are verified by extensive simulations, and the simulation results show that the experiment-based upper bound is tight enough for practical network deployment.2. For dynamic spectrum access networks, the concept of starved link is first introduced, and then the random properties of starved links are used to quantify primary users'impact on the connectivity of secondary user network. Further, the existence of percolated secondary user network is proved, and the corresponding necessary condition is derived.In dynamic spectrum access networks, primary users have privilege to use the spectrum and hence may potentially starve some secondary users if primary users use up all available spectrums in certain crowded areas. Based on this characteristic, a starved link is defined as a link between two secondary users which are in each other's radio range but cannot communicate directly due to the lack of spectrum. The random properties of starved link quantitatively reflect primary users'impact on the connectivity of secondary user network. The probability of starved link, the expectation of the number of starved links and the lower bound of the cumulative distributed function of the number of starved links in a limited region are derived. Based on percolation theory, the dissertation further proves that secondary users can form the percolated network when there are less primary users or the load of primary users is light. On the other hand, secondary user network cannot be percolated when there are many primary users and the load is heavy. The necessary condition of the existence of percolated secondary user network is derived when the primary users and secondary users share one channel. All above conclusions are examined by extensive simulations.3. To investigate the compatibilities between routing metrics and geographic routing protocols, the sufficient and necessary conditions for the loop-freeness, delivery-guarantee and consistency of greedy routing, face routing and combined greedy-face routing are derived.Arbitrary design of routing metrics may greatly degrade network performance and even create routing loops, which is called the compatibilities between routing metric and routing protocols. The dissertation proposes a novel routing algebra system and introduces three compatibilities, respectively named loop-freeness, delivery-guarantee and consistency, to investigate the compatibilities between routing metrics and geographic routing protocols. Based on defined algebra properties, the sufficient and necessary conditions for the loop-freeness, delivery-guarantee and consistency of greedy routing, face routing and combined greedy-face routing are derived. This work provides essential criteria for evaluating and designing geographic routing protocols.4. We study the routing problem in non-UDG network models, and a novel geographic routing algorithm, named DGA, is proposed.Combined greedy-face routing can ensure delivery guarantees, but usually cannot be used in non-UDG network models or is complicated to implement. Hence, DGA is proposed in this dissertation. DGA handles the routing hole problem by greedy routing based on the virtual coordinates, which makes DGA is applicable for practical network deployment. The performance and scalability of DGA are examined by extensive simulations.
Keywords/Search Tags:Wireless networks, Connectivity, Dynamic spectrum access, Geographic routing, Routing algebra, Virtual coordinates
PDF Full Text Request
Related items