Recently, many new types of wireless networks have emerged, such as mobile ad hoc networks (MANETs), cognitive radio networks (CRNs) and large scale wireless sensor networks. To get better performance in these wireless networks, various schemes, e.g., metrics, policies, algorithms, protocols, etc., have been proposed. Among them, optimal schemes that can achieve optimal performance are of great importance. On the theoretical side, they provide important design guidelines and performance benchmarks. On the practical side, they guarantee best communication performance with limited network resources. In this dissertation, we focus on the modeling and optimization of routing in wireless networks, including both broadcast routing, unicast routing, and convergecast routing. We study two aspects of routing: algorithm analysis and Qos analysis. In the algorithmic work, we focus on how to build optimal broadcast trees. We investigate the optimality compatibility between three tree-based broadcast routing algorithms and routing metrics. The Qos work includes three parts. First, we focus on how to optimally repair broken paths to minimize impact of path break in MANETs. We propose a provably optimal cached-based route repair policy for real-time traffic in MANETs. Second, we focus on the impact of secondary user (SU) node placement on SU traffic delay in CRNs. We design SU node placement schemes that can minimize the multi-hop delay in CRNs. Third, we analyze the convergecast delay of a large scale sensor network which coexists with WiFi nodes. We derive a closed form delay formula, which can be used to estimate sensor packet convergecast delay given the distance between a sensor node and the sink node together with other networking setting parameters. The main contributions of this dissertation are summarized as follows:

Optimality compatibility study between tree-based broadcast routing algorithms and routing metrics: Broadcast routing is a critical component in the routing design. While there are plenty of routing metrics and broadcast routing schemes in current literature, arbitrary combination of broadcast routing metrics with broadcast tree construction (BTC) algorithms may not result in optimal broadcast trees. In this work, we study the requirement on the combination of routing metrics and BTC algorithms to ensure optimal broadcast tree construction. When a BTC algorithm fails to find the optimal broadcast tree, we define that the BTC algorithm and the metric are not optimality compatible. We show that different BTC algorithms have different requirements on the properties of broadcast routing metrics. The metric properties for BTC algorithms in both undirected network topologies and directed network topologies are developed and proved. They are successfully used to verify the optimality compatibility between broadcast routing metrics and BTC algorithms.

Optimal cache-based route repair policy for real-time traffic in mobile ad hoc networks: Real-time applications in ad hoc networks require fast route repair mechanisms to minimize the interruptions to their communications. Cache-based route repair schemes are popular choices since they can quickly resume communications using cached backup paths after a route break. In this work, through thorough theoretical modeling of the cache-based route repair process, we derive a provably optimal cache-based route repair policy. This optimal policy considers both the overhead of the route repair schemes and the promptness of the repair action. The correctness and advantages of our optimal policy are validated by extensive simulations.

Optimal secondary user node placement study in cognitive radio networks: Information propagation speed (IPS) in a multi-hop CRN is an important factor that affects the network's delay performance and needs to be considered in network planning. The impact of primary user (PU) activities on IPS makes the problem of analyzing IPS in multi-hop CRNs very challenging and hence unsolved in existing literature. In this work, we fill this technical void. We establish models of IPS in multi-hop CRNs and compute how to maximize IPS in two cases. The first case, named the maximum network IPS, maximizes IPS across a network topology over an infinite plane. The second case, named the maximum flow IPS, maximizes the IPS between a given pair of source and destination nodes separated by a fixed distance. We reveal that both maximum IPSs are determined by the PU activity level and the placement of SU relay nodes. We design optimal relay placement strategies in CRNs to maximize these two IPS under different PU activity levels. The correctness of our analytical results is validated by simulations and numerical experiments.

Convergecast delay analysis of large scale sensor networks coexisting with WiFi networks: Due to the increasing popularity of wireless devices, such as WiFi (IEEE 802.11) and ZigBee (IEEE 802.15.4), the ISM bands have become more and more crowded. Since ZigBee is the de facto radio technology of sensor networks, coexistence of WiFi networks and sensor (ZigBee) networks is challenging because of the great heterogeneity between WiFi and ZigBee technologies. In the presence of interference from WiFi and other sensor nodes, the performance of sensor networks is not clearly understood. In this work, we study delay performance of a large scale sensor network which coexists with WiFi networks. Given the distance from the sensor node to the sink node, we are interested in the expected delay of sensor packets to reach the sink node in the presence of both WiFi and sensor interference. We formulate the delay analysis problem as a two priority M/G/1 preemptive repeat identical queueing system, and analyze the delay using queueing theory and probability theory. First, we use a path probabilistic approach to derive the expected delay. Second, we develop a simplified linear approximation model for delay analysis. The correctness of both models is validated by NS2 simulations.Recently, many new types of wireless networks have emerged, such as mobile ad hoc networks (MANETs), cognitive radio networks (CRNs) and large scale wireless sensor networks. To get better performance in these wireless networks, various schemes, e.g., metrics, policies, algorithms, protocols, etc., have been proposed. Among them, optimal schemes that can achieve optimal performance are of great importance. On the theoretical side, they provide important design guidelines and performance benchmarks. On the practical side, they guarantee best communication performance with limited network resources. In this dissertation, we focus on the modeling and optimization of routing in wireless networks, including both broadcast routing, unicast routing, and convergecast routing. We study two aspects of routing: algorithm analysis and Qos analysis. In the algorithmic work, we focus on how to build optimal broadcast trees. We investigate the optimality compatibility between three tree-based broadcast routing algorithms and routing metrics. The Qos work includes three parts. First, we focus on how to optimally repair broken paths to minimize impact of path break in MANETs. We propose a provably optimal cached-based route repair policy for real-time traffic in MANETs. Second, we focus on the impact of secondary user (SU) node placement on SU traffic delay in CRNs. We design SU node placement schemes that can minimize the multi-hop delay in CRNs. Third, we analyze the convergecast delay of a large scale sensor network which coexists with WiFi nodes. We derive a closed form delay formula, which can be used to estimate sensor packet convergecast delay given the distance between a sensor node and the sink node together with other networking setting parameters. The main contributions of this dissertation are summarized as follows:

Optimality compatibility study between tree-based broadcast routing algorithms and routing metrics: Broadcast routing is a critical component in the routing design. While there are plenty of routing metrics and broadcast routing schemes in current literature, arbitrary combination of broadcast routing metrics with broadcast tree construction (BTC) algorithms may not result in optimal broadcast trees. In this work, we study the requirement on the combination of routing metrics and BTC algorithms to ensure optimal broadcast tree construction. When a BTC algorithm fails to find the optimal broadcast tree, we define that the BTC algorithm and the metric are not optimality compatible. We show that different BTC algorithms have different requirements on the properties of broadcast routing metrics. The metric properties for BTC algorithms in both undirected network topologies and directed network topologies are developed and proved. They are successfully used to verify the optimality compatibility between broadcast routing metrics and BTC algorithms.

Optimal cache-based route repair policy for real-time traffic in mobile ad hoc networks: Real-time applications in ad hoc networks require fast route repair mechanisms to minimize the interruptions to their communications. Cache-based route repair schemes are popular choices since they can quickly resume communications using cached backup paths after a route break. In this work, through thorough theoretical modeling of the cache-based route repair process, we derive a provably optimal cache-based route repair policy. This optimal policy considers both the overhead of the route repair schemes and the promptness of the repair action. The correctness and advantages of our optimal policy are validated by extensive simulations.

Optimal secondary user node placement study in cognitive radio networks: Information propagation speed (IPS) in a multi-hop CRN is an important factor that affects the network's delay performance and needs to be considered in network planning. The impact of primary user (PU) activities on IPS makes the problem of analyzing IPS in multi-hop CRNs very challenging and hence unsolved in existing literature. In this work, we fill this technical void. We establish models of IPS in multi-hop CRNs and compute how to maximize IPS in two cases. The first case, named the maximum network IPS, maximizes IPS across a network topology over an infinite plane. The second case, named the maximum flow IPS, maximizes the IPS between a given pair of source and destination nodes separated by a fixed distance. We reveal that both maximum IPSs are determined by the PU activity level and the placement of SU relay nodes. We design optimal relay placement strategies in CRNs to maximize these two IPS under different PU activity levels. The correctness of our analytical results is validated by simulations and numerical experiments.

Convergecast delay analysis of large scale sensor networks coexisting with WiFi networks: Due to the increasing popularity of wireless devices, such as WiFi (IEEE 802.11) and ZigBee (IEEE 802.15.4), the ISM bands have become more and more crowded. Since ZigBee is the de facto radio technology of sensor networks, coexistence of WiFi networks and sensor (ZigBee) networks is challenging because of the great heterogeneity between WiFi and ZigBee technologies. In the presence of interference from WiFi and other sensor nodes, the performance of sensor networks is not clearly understood. In this work, we study delay performance of a large scale sensor network which coexists with WiFi networks. Given the distance from the sensor node to the sink node, we are interested in the expected delay of sensor packets to reach the sink node in the presence of both WiFi and sensor interference. We formulate the delay analysis problem as a two priority M/G/1 preemptive repeat identical queueing system, and analyze the delay using queueing theory and probability theory. First, we use a path probabilistic approach to derive the expected delay. Second, we develop a simplified linear approximation model for delay analysis. The correctness of both models is validated by NS2 simulations.