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. / Ph. D.

Communication in wireless networks elementally comprises of packet exchanges over individual wireless links and routes formed by these links. To this end, two problems are fundamental: assessment of link quality and identification of the least-cost (optimal) routes. However, little is known about achieving these goals without incurring additional overhead to IEEE 802.11 networks. In this thesis, I design and experimentally evaluate two frameworks that enable individual 802.11 nodes to characterize their wireless links and routes by employing only local and passively collected information. First, I enable 802.11 nodes to assess their links by characterizing packet delivery failures and failure causes. The key problem is that nodes cannot individually observe many factors that affect the packet delivery at both ends of their links and in both directions of 802.11 communication. To this end, instead of relying on the assistance of other nodes, I design the first practical framework that extrapolates the missing information locally from the nodes' overhearing, the observable causal relationships of 802.11 operation and characterization of the corrupted and undecodable packets. The proposed framework employs only packet-level information generally reported by commodity 802.11 wireless cards. Next, I design and evaluate routing primitives that enable individual nodes to suppress their poor route selections. I refer to a route selection as poor whenever the employed routing protocol fails to establish the existing least-cost path according to an employed routing metric. This thesis shows that an entire family of the state-of-the art on-demand distance-vector routing protocols, including the standards-proposed protocol for IEEE 802.11s mesh networks, suffers from frequent and long-term poor selections having arbitrary path costs. Consequently, such selections generally induce severe throughput degradations for network users. To address this problem, I design mechanisms that identify optimal paths locally by employing only the information readily available to the affected nodes. The proposed mechanisms largely suppress occurrence of inferior routes. Even when such routes are selected their durations are reduced by several orders of magnitude, often to sub-second time scales. My work has implications on several key areas of wireless networking: It removes systematic failures from wireless routing and serves as a source of information for a wide range of protocols including the protocols for network management and diagnostics.

abstract: The integration of passive optical networks (PONs) and wireless mesh networks (WMNs) into Fiber-Wireless (FiWi) networks has recently emerged as a promising strategy for providing flexible network services at relative high transmission rates. This work investigates the effectiveness of localized routing that prioritizes transmissions over the local gateway to the optical network and avoids wireless packet transmissions in radio zones that do not contain the packet source or destination. Existing routing schemes for FiWi networks consider mainly hop-count and delay metrics over a flat WMN node topology and do not specifically prioritize the local network structure. The combination of clustered and localized routing (CluLoR) performs better in terms of throughput-delay compared to routing schemes that are based on minimum hop-count which do not consider traffic localization. Subsequently, this work also investigates the packet delays when relatively low-rate traffic that has traversed a wireless network is mixed with conventional high-rate PON-only traffic. A range of different FiWi network architectures with different dynamic bandwidth allocation (DBA) mechanisms is considered. The grouping of the optical network units (ONUs) in the double-phase polling (DPP) DBA mechanism in long-range (order of 100~Km) FiWi networks is closely examined, and a novel grouping by cycle length (GCL) strategy that achieves favorable packet delay performance is introduced. At the end, this work proposes a novel backhaul network architecture based on a Smart Gateway (Sm-GW) between the small cell base stations (e.g., LTE eNBs) and the conventional backhaul gateways, e.g., LTE Servicing/Packet Gateway (S/P-GW). The Sm-GW accommodates flexible number of small cells while reducing the infrastructure requirements at the S-GW of LTE backhaul. In contrast to existing methods, the proposed Sm-GW incorporates the scheduling mechanisms to achieve the network fairness while sharing the resources among all the connected small cells base stations. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2016