No description available.

Wireless sensor networks are widely applied to many fields such as animal habitat monitoring, air traffic control, and health monitoring. One of the current problems with wireless sensor networks is the ability to overcome communication failures due to hardware failure, distributing sensors in an uneven geographic area, or unexpected obstacles between sensors. One common solution to overcome this problem is to place a minimum number of relay nodes among sensors so that the communication among sensors is guaranteed. This is called Relay Node Placement Problem (RNP). This problem has been proved as NP-hard for a simple connected graph. Therefore, many algorithms have been developed based on Steiner graphs. Since RNP for a connected graph is NP-hard, the RNP for a survivable network has been conjectured as NP-hard and the algorithms for a survivable network have also been developed based on Steiner graphs. In this study, we show the new approximation bound for the survivable wireless sensor networks using the Steiner graphs based algorithm. We prove that the approximation bound is guaranteed in an environment where some obstacles are laid, and also propose the newly developed algorithm which places fewer relay nodes than the existing algorithms. Consequently, the main purpose of this study is to find the minimum number of relay nodes in order to meet the survivability requirements of wireless sensor networks.

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.

Network coding refers to the implementation of coding methods to utilize network connections more efficiently. Network coding is commonly researched in the information theory field, but very little research is being done on the physical implementation thereof. One exception is COPE where network coding is implemented in wireless networks for unicast transmission sessions. In this dissertation, we discuss the physical arrangement of wireless nodes to form topologies suitable for the implementation of network coding. We implement linear network coding in wireless ad hoc networks for multicast transmission sessions. We calculate the areas in which each wireless node must be located for a specific network coding suitable topology to be formed. The identified topologies are simulated in OPNET Modeler and then implemented on a six node testbed, to analyse the effect of implementing network coding in these topologies. We provide results indicating the trade-off between reduced network load and higher end-to-end delay when our developed network coding algorithm is active in the respective topologies. The results indicate that the developed network coding scheme will produce better overall performance when implemented in sensor networks or highly congested ad hoc networks. / Thesis (M.Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2011.

Network coding refers to the implementation of coding methods to utilize network connections more efficiently. Network coding is commonly researched in the information theory field, but very little research is being done on the physical implementation thereof. One exception is COPE where network coding is implemented in wireless networks for unicast transmission sessions. In this dissertation, we discuss the physical arrangement of wireless nodes to form topologies suitable for the implementation of network coding. We implement linear network coding in wireless ad hoc networks for multicast transmission sessions. We calculate the areas in which each wireless node must be located for a specific network coding suitable topology to be formed. The identified topologies are simulated in OPNET Modeler and then implemented on a six node testbed, to analyse the effect of implementing network coding in these topologies. We provide results indicating the trade-off between reduced network load and higher end-to-end delay when our developed network coding algorithm is active in the respective topologies. The results indicate that the developed network coding scheme will produce better overall performance when implemented in sensor networks or highly congested ad hoc networks. / Thesis (M.Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2011.