COVERAGE AND ROUTING IN DYNAMIC NETWORKS

Dynamic networks have become ubiquitous in the current technological framework. Such networks have widespread applications in commercial, public safety and military domains. Systems utilizing these networks are deployed in scenarios influencing critical aspects of human lives, e.g. connecting first responders to command center in disasters, wildlife monitoring, vehicular communication, and health care systems. %Dynamicity of a communication network can be either due to network dynamics or input dynamics. Network dynamics means the topology of the network changes over time. In these networks, nodes and edges may come and go. Input dynamics refers to changes in load of the network. In this dissertation, we explore two significant aspects of dynamic networks. In the first part of the dissertation, we study coverage problem in dynamic networks such as public safety networks. Networking infrastructure can partially (or sometimes fully) breakdown during a catastrophe. At the same time, unusual peaks in traffic load could lead to much higher blocking probability or service interruptions for critical communication. Lack of adequate communication among emergency responders or public safety personnel could put many lives at risks. One possible solution to deal with such scenarios is through the use of mobile/portable infrastructures, commonly referred to as Cells on Wheels (COW) or Cells on Light Trucks (COLT). These mobile cells can effectively complement the existing undamaged infrastructure or enable a temporary emergency network by themselves. Given the limited capacity of each cell, variable and spatially non-uniform traffic across the disaster area can make a big impact on the network performance. Not only judicious deployment of the cells can help to meet the coverage and capacity demands across the area, but also intelligent relocation strategies can optimally match the network resources to potentially changing traffic demands. Assuming that each cell can autonomously change its location, in this dissertation, we investigate such opportunities and constraints. We propose strategies for autonomous relocation of the mobile resource to adapt network coverage and increase the supported user traffic. We demonstrate the performance improvement for several scenarios via simulations using our algorithms. In practical scenarios, typically there are some areas in the field where mobile base stations cannot move into. Structural obstacles, areas with outstanding water or other hazardous materials, or surfaces with debris are examples of prohibited areas that mobile cells are expected to avoid. Such prohibited areas introduce additional constraints on designing intelligent relocation strategies. We propose a decentralized relocation algorithm that enables mobile cells to adapt their positions in response to potentially changing traffic patterns in a field with such prohibited areas. In the second part of dissertation, we study routing problem in dynamic networks. Routing is critical when there is no direct link connecting source to its destination. Performance of this algorithm is critical in many different applications. Two important metrics in routing are delay and throughput. We propose a throughput-optimal routing and scheduling algorithm that improves delay performance by accounting for the network topology. First, we propose algorithm for the fixed topology scenario. We improve delay performance by solving an optimization problem which aims to send packets mostly to greedy neighbors, subject to throughput-optimality constraints. Next, we consider the network with dynamic topology, where routers or links may be added or removed during time. We propose variations of the proposed algorithm for networks with dynamic topology. We identify key design parameters and illustrate the performance of our schemes through simulations