No / Providing a guaranteed quality-of-service (QoS) is essential to many real-time applications. The existing distributed QoS routing algorithms are based on either shortest path or flooding and both tend to have high message overhead. A new distributed unicast QoS routing algorithm based on Fano¿s decoding method is studied. Fano¿s decoding method is a technique used in error control coding and it attempts to trace an optimal path probabilistically. The similarity of various aspects of Fano¿s decoding method to a QoS routing algorithm and the benefits it can provide encourages us to investigate the possibility of using it in QoS routing. This is the first known attempt to modify an error control technique using Fano¿s decoding method for the purpose of QoS routing in fixed wired networks. Simulation results demonstrate the effectiveness of the proposed algorithm in terms of message overhead and success ratio (% of paths obtained that satisfy the given QoS constraints). It is shown that the message overhead in the proposed algorithm is reduced compared to flooding based algorithms while maintaining a similar success ratio. Message overhead is also reduced compared to distance vector based algorithms for all but very sparsely connected networks, while success ratio is not compromised. Nodal storage is also considerably lower than for most other contemporary QoS routing algorithms.

In order to save energy consumption in idle states, low duty-cycled operation is widely used in Wireless Sensor Networks (WSNs), where each node periodically switches between sleeping mode and awake mode. Although efficient toward saving energy, duty-cycling causes many challenges, such as difficulty in neighbor discovery due to asynchronous wakeup/sleep scheduling, time-varying transmission latencies due to varying neighbor discovery latencies, and difficulty on multihop broadcasting due to non-simultaneous wakeup in neighborhood. This dissertation focuses on this problem space. Specifically, we focus on three co-related problems in duty-cycled WSNs: wakeup scheduling, routing and broadcasting. We propose an asynchronous quorum-based wakeup scheduling scheme, which optimizes heterogenous energy saving ratio and achieves bounded neighbor discovery latency, without requiring time synchronization. Our solution is based on quorum system design. We propose two designs: cyclic quorum system pair (cqs-pair) and grid quorum system pair (gqs-pair). We also present fast offline construction algorithms for such designs. Our analytical and experimental results show that cqs-pair and gqs-pair achieve better trade-off between the average discovery delay and energy consumption ratio. We also study asymmetric quorum-based wakeup scheduling for two-tiered network topologies for further improving energy efficiency. Heterogenous duty-cycling causes transmission latencies to be time-varying. Hence, the routing problem becomes more complex when the time domain must be considered for data delivery in duty-cycled WSNs. We formulate the routing problem as time-dependent Bellman-Ford problem, and use vector representation for time-varying link costs and end-to-end (E2E) distances. We present efficient algorithms for route construction and maintenance, which have bounded time and message complexities in the worst case by ameliorating with beta-synchronizer. Multihop broadcast is complex in duty-cycled WSNs due to non simultaneous wakeup in neighborhoods. We present Hybrid-cast, an asynchronous multihop broadcast protocol, which can be applied to low duty-cycling or quorum-based duty-cycling schedules, where nodes send out a beacon message at the beginning of wakeup slots. Hybrid-cast achieves better tradeoff between broadcast latency and broadcast count compared to previous broadcast solutions. It adopts opportunistic data delivery in order to reduce the broadcast latency. Meanwhile, it reduces redundant transmission via delivery deferring and online forwarder selection. We analytically establish the upper bound of broadcast count and the broadcast latency under Hybrid-cast. To verify the feasibility, effectiveness, and performance of our solutions for asynchronous wakeup scheduling, we developed a prototype implementation using Telosb and TinyOS 2.0 WSN platforms. We integrated our algorithms with the existing protocol stack in TinyOS, and compared them with the CSMA mechanism. Our implementation measurements illustrate the feasibility, performance trade-off, and effectiveness of the proposed solutions for low duty-cycled WSNs. / Ph. D.

Evacuation planning is an important disaster management tool. A large-scale evacuation of a region by automobile is a difficult task, especially as demand is often greater than supply. This is made more difficult as the imbalance of supply and demand actually reduces supply due to congestion. Currently, most of the emphasis in evacuation planning is on supply management. The purpose of this dissertation is to introduce and study sophisticated demand management tools, specifically, staging and routing of evacuees. These tools can be used to produce evacuation strategies that reduce or eliminate congestion. A strategic planning model is introduced that accounts for evacuation dynamics and the non-linearities in travel times associated with congestion, yet is tractable and can be applied to large-scale networks. Objective functions of potential interest in evacuation planning are introduced and studied in the context of this model. Insights into the use of staging and routing in evacuation management are delineated and solution techniques are developed. Two different strategic approaches are studied in the context of this model. The first strategic approach is to control the evacuation at a disaggregate level, where customized staging and routing plans are produced for each individual or family unit. The second strategic approach is to control the evacuation at a more aggregate level, where evacuation plans are developed for a larger group of evacuees, based on pre-defined geographic areas. In both approaches, shelter requirements and preferences can also be considered. Computational experience using these two strategic approaches, and their respective solution techniques, is provided using a real network pertaining to Virginia Beach, Virginia, in order to demonstrate the efficacy of the proposed methodologies. / Ph. D.

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and unstable customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has increased significantly. In traditional job shops, tooling is usually assumed as a fixed resource. However, when tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling setup, hence allows parts to be processed in small batches. In this research, a dynamic scheduling problem under flexible tooling resource constraints is studied. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in Automated Manufacturing Systems. It decomposes the overall problem into a series of static sub-problems for each scheduling window, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. Two types of manufacturing system models are used in simulation studies to test the effectiveness of the proposed dynamic scheduling approach. First, hypothetical models are generated using some generic shop flow structures (e.g. flexible flow shops, job shops, and single-stage systems) and configurations. They are tested to provide the empirical evidence about how well the proposed approach performs for the general automated manufacturing systems where parts have alternative routings. Second, a model based on a real industrial flexible manufacturing system was used to test the effectiveness of the proposed approach when machine types, part routing, tooling, and other production parameters closely mimic to the real flexible manufacturing operations. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including Cost Over Time (COVERT), Apparent Tardiness Cost (ATC), and Bottleneck Dynamics (BD), on due-date related performance measures under both types of manufacturing systems models. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics. This research also investigates in what conditions (e.g. the number of machines, the number of operation steps, and shop load conditions) the proposed approach works the best, and how the performance of this proposed approach changes when these conditions change. When tooling resource is shared, parts can be routed to machines that do not have all the required tools. This may result in higher routing flexibility. However, research work to date in sharing of tooling resources often places more emphasis on the real-time control and manipulation of tools, and pays less attention to the loading of machines and initial tool allocation at the planning stage. In this research, a machine-loading model with shared tools is proposed to maximize routing flexibility while maintaining minimum resident tools. The performance of the proposed loading heuristic is compared to that of a random loading method using hypothetically generated single stage system models. The study result indicates that better system performances can be obtained by taking into account the resident tooling ratio in assigning part types and allocating tools to machines at the initial planning stage. / Ph. D.

A variety of practical network optimization problems arising in the context of public supply and commercial transportation, emergency response and risk management, engineering design, and industrial planning are addressed in this study. The decisions to be made in these problems include the location of supply centers, the routing, allocation and scheduling of flow between supply and demand locations, and the design of links in the network. This study is concerned with the development of optimization models and the analysis of five such problems, and the subsequent design and testing of exact and heuristic algorithms for solving these various network optimization problems. The first problem addressed is the time-dependent shortest pair of disjoint paths problem. We examine computational complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. It is shown that this problem, and many variations of it, are nP-Hard and a 0-1 linear programming model that can be used to solve this problem is developed. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. Next, we examine a minimum-risk routing problem and pursue the development, analysis, and testing of a mathematical model for determining a route that attempts to reduce the risk of low probability-high consequence accidents related with the transportation of hazardous materials (hazmat). More specifically, the problem addressed in this study involves finding a path that minimizes the conditional expectation of a consequence, given that an accident occurs, subject to the expected value of the consequence being lesser than or equal to a specified level n, and the probability of an accident on the path being also constrained to be no more than some value h. Various insights into related modeling issues are also provided. The values n and h are user-prescribed and could be prompted by the solution of shortest path problems that minimize the respective corresponding linear risk functions. The proposed model is a discrete, fractional programming problem that is solved using a specialized branch-and-bound approach. The model is also tested using realistic data associated with a case concerned with routing hazmat through the roadways of Bethlehem, Pennsylvania. The third problem deals with the development of a resource allocation strategy for emergency and risk management. An important and novel issue addressed in modeling this problem is the effect of loss in coverage due to the non-availability of emergency response vehicles that are currently serving certain primary incidents. This is accommodated within the model by including in the objective function a term that reflects the opportunity cost for serving an additional incident that might occur probabilistically on the network. A mixed-integer programming model is formulated for the multiple incident - multiple response problem, and we show how its solution capability can be significantly enhanced by injecting a particular structure into the constraints that results in an equivalent alternative model representation. Furthermore, for certain special cases of the MIMR problem, efficient polynomial-time solution approaches are prescribed. An algorithmic module composed of these procedures, and used in concert with a computationally efficient LP-based heuristic scheme that is developed, has been incorporated into an area-wide incident management decision support system (WAIMSS) at the Center for Transportation Research, Virginia Tech. The fourth problem addressed in this study deals with the development of global optimization algorithms for designing a water distribution network, or expanding an already existing one, that satisfies specified flow demands at stated pressure head requirements. The nonlinear, nonconvex network problem is transformed into the space of certain design variables. By relaxing the nonlinear constraints in the transformed space via suitable polyhedral outer approximations and applying the Reformulation-Linearization Technique (RLT), a tight linear lower bounding problem is derived. This problem provides an enhancement and a more precise representation of previous lower bounding relaxations that use similar approximations. Computational experience on three standard test problems from the literature is provided. For all these problems, a proven global optimal solution within a tolerance of 10 -4 % and/or within 1$ of optimality is obtained. For the two larger instances dealing with the Hanoi and New York test networks that have been open for nearly three decades, the solutions derived represent significant improvements, and the global optimality has been verified at the stated level of accuracy for these problems for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results on deriving global optimal solutions are presented. The final problem addressed in this study is concerned with a global optimization approach for solving capacitated Euclidean distance multifacility location-allocation problems, as well as the development of a new algorithm for solving the generalized lp distance location-allocation problem. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. Beginning with the Euclidean distance problem, we design depth-first and best-first branch-and-bound algorithms based on a partitioning of the allocation space that finitely converges to a global optimum for this nonconvex problem. For deriving lower bounds at node subproblems in these partial enumeration schemes, we employ two types of procedures. The first approach computes a lower bound via a simple projected location space lower bounding (PLSB) subproblem. The second approach derives a significantly enhanced lower bound by using a Reformulation-Linearization Technique (RLT) to transform an equivalent representation of the original nonconvex problem into a higher dimensional linear programming relaxation. In addition, certain cut-set inequalities generated in the allocation space, objective function based cuts derived in the location space, and tangential linear supporting hyperplanes for the distance function are added to further tighten the lower bounding relaxation. The RLT procedure is then extended to the.general lp distance problem for 1 < p < 2. Various issues related to the selection of branching variables, the design of heuristics via special selective backtracking mechanisms, and the study of the sensitivity of the proposed algorithm to the value of p in the lp - norm, are computationally investigated. Computational experience is also provided on a set of test problems to investigate both the PLSB and the RLT-lower bounding schemes. The results indicate that the proposed global optimization approach using the RLT-based scheme offers a promising viable solution procedure. In fact, among the problems solved, for the only two test instances previously available in the literature for the Euclidean distance case that were posed in 1979, we report proven global optimal solutions within a tolerance of 0.1% for the first time. It is hoped that the modeling, analysis, insights, and concepts provided for these various network based problems that arise in diverse routing, location, distribution, and design contexts, will provide guidelines for studying many other problems that arise in related situations. / Ph. D.

Wireless network devices, especially in ad hoc networks, are typically battery-powered. The growing need for energy efficiency in wireless networks, in general, and in mobile ad hoc networks (MANETs), in particular, calls for power enhancement features. The goal of this dissertation is to extend network lifetime by improving energy utilization in MANET routing. We utilize the ability of wireless network interface cards to dynamically change their transmission power, as well as the ability of wireless devices to read the remaining battery energy of the device to create a table of what we term "reluctance values," which the device uses to determine how to route packets. Choosing routes with lower reluctance values, on average and with time, leads to better utilization of the energy resources of the devices in the network. Our power-aware scheme can be applied to both reactive and proactive MANET routing protocols. As examples and to evaluate performance, the technique has been applied to the Dynamic Source Routing (DSR) protocol, a reactive routing protocol, and the Optimized Link State Routing (OLSR) protocol, a proactive routing protocol. Simulations have been carried out on large static and mobile networks. Results show improvements in network lifetime in static and certain mobile scenarios. Results also show better distribution of residual node energies at the end of simulations, which means that the scheme is balancing energy load more evenly across network nodes than the unmodified versions of DSR and OLSR. Average change in energy over time in the unmodified protocols show a steady increase with time, while the power-aware protocols show an increase in the beginning, then it levels for sometime before it starts to decrease. The power-aware scheme shows improvements in static and in coordinated mobility scenarios. In random mobility the power-aware protocols show no advantage over the unmodified protocols. / Ph. D.

Shorter product life-cycles, unpredictable demand, and customized products have forced manufacturing firms to operate more efficiently and effectively in order to adapt to changing requirements. Traditional manufacturing systems, such as job shops and flow lines, cannot handle such environments. Cellular manufacturing, which incorporates the flexibility of job shops and the high production rate of flow lines, has been seen as a promising alternative for such cases. Although cellular manufacturing provides great benefits, the design of cellular manufacturing systems is complex for real-life problems. Existing design methods employ simplifying assumptions which often deteriorate the validity of the models used for obtaining solutions. Two simplifying assumptions used in existing design methods are as follows. First, product mix and demand do not change over the planning horizon. Second, each operation can be performed by only one machine type, i.e., routing flexibility of parts is not considered. This research aimed to develop a model and a solution approach for designing cellular manufacturing systems that addresses these shortcomings by assuming dynamic and stochastic production requirements and employing routing flexibility. A mathematical model and an optimal solution procedure were developed for the design of cellular manufacturing under dynamic and stochastic production environment employing routing flexibility. Optimization techniques for solving such problems usually require a substantial amount of time and memory space, therefore, a simulated annealing based heuristic was developed to obtain good solutions within reasonable amounts of time. The heuristic was evaluated in two ways. First, different cellular manufacturing design problems were generated and solved using the heuristic. Then, solutions obtained from the heuristic were compared with lower bounds of solutions obtained from the optimal solution procedure. The lower bounds were used instead of optimal solutions because of the computational time required to obtain optimal solutions. The results show that the heuristic performs well under various circumstances, but routing flexibility has a major impact on the performance of the heuristic. The heuristic appears to perform well regardless of problem size. Second, known solutions of two CM design problems from literature were used to compare with those from the heuristic. The heuristic slightly outperforms one design approach, but substantially outperforms the other design approach. / Ph. D.

The vehicle routing problem (VRP), is a classic optimization problem that aims to determine the optimal set of routes for a fleet of vehicles to meet the demands of a set of customers. The VRP has been studied for many decades and as such, there are many variants and extensions to the original problem. The research presented here focuses on two different types of vehicle routing and scheduling planning problems: car shipping and fatigue-aware scheduling. In addition to modeling and solving the car shipping problem, this research presents a novel way for ways in which drivers can describe their route preferences in a decision support system. This work also introduces the first fatigue-aware vehicle scheduling problem called the Truck Driver Scheduling Problem with Fatigue Management (TDSPFM). The TDSPFM is utilized to produce schedules that keep the drivers more alert than existing commercial vehicle regulations. Finally, this work analyzes the effect of the starting alertness level on driver alertness for the remainder of the work week and examines a critical shortcoming in existing regulations. / Ph. D.

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.

The global energy requirement is increasing at a rapid pace and fossil fuels have been one of the major players in meeting this growing energy demand. However, the resources for fossil fuels are finite. Therefore, it is essential to develop renewable energy sources like biofuels to help address growing energy needs. A key aspect in the production of biofuel is the biomass logistics chain that constitutes a complex collection of activities, which must be judiciously executed for a cost-effective operation. In this thesis, we introduce a two-phase optimization-simulation approach to determine tactical biomass logistics-related decisions cost effectively in view of the uncertainties encountered in real-life. These decisions include number of trucks to haul biomass from storage locations to a bio-refinery, the number of unloading equipment sets required at storage locations, and the number of satellite storage locations required to serve as collection points for the biomass secured from the fields. Later, an operational-level decision support tool is introduced to aid the "feedstock manager" at the bio-refinery by recommending which satellite storage facilities to unload, how much biomass to ship, how to allocate existing resources (trucks and unloading equipment sets) during each time period, and how to route unloading equipment sets between storage facilities. Another problem studied is the "Bale Collection Problem" associated with the farmgate operation. It is essentially a capacitated vehicle routing problem with unit demand (CVRP-UD), and its solution defines a cost-effective sequence for collecting bales from the field after harvest. / Master of Science