Network optimization: Algorithm design and analysis

We study two distinct aspects in network optimization for specific requirements of different types of networks.;In Part I, we consider optimization related to connectivity in wireless sensor networks (WSNs) that consist of sensors and base stations. In such a network, sensors cooperate to dynamically form a network to deliver information to base stations, and base stations provide centralized computation and data storage and may also serve as the gateways between the local wireless network and a wired network.;We address the problem of network connectivity in the context of power consumption, node mobility, limited resources, and fault tolerance. We first study topology control problems that utilize node power assignments to maintain a connected network. We focus on the Mobile Topology Control problem in Mobile Ad hoc Networks (MANETs). In such problems the major challenge comes from accommodating node movement. We develop algorithms (optimization and approximation) for topology control under the Simple Mobile Network model. An alternative to network connectivity in stationary WSNs is to introduce a small number of more costly but more powerful "relay" nodes that provide better support for sensor coverage and network connectivity. We study the Relay Node Placement problem with a limited number of relays and seek a placement so that the two-tiered network is connected and the maximum transmission power used by any sensor is minimized. We develop a polynomial time algorithm for the problem on a comb-grid and more generally, we develop a "bicriteria" approximation algorithm for the problem on the Euclidean plane. We also consider network connectivity in the context of fault tolerance. As an alternative to 2-connected networks, we study the Relay Network Recovery problem where failed nodes are replaced and the original network is re-configured so as to optimize the power consumption. We develop algorithms for three derivatives that vary in the degree of change that is allowed to the original network nodes.;In Part II, we consider optimization in large scale data dissemination networks (not necessarily wireless) that comprise a large number of information flows and information users and where individual users are interested in specific (not all!) flows. Here, instead of the costly broadcasting, multicasting is used. The channelization problem is to construct multicast groups in a way that the network cost is substantially less in comparison with using a single multicast group. We extend the multicast channelization problem with considerations on incremental changes and the total network traffic that it produced.;We first consider Incremental Channelization problems where flows, users and/or user preference may arrive and depart. The goal is to compute a good solution based on existing results in significantly less time than to compute "from scratch". We show that natural incremental approaches are NP-hard, and that approximating the optimal solution with less than a log factor is unlikely. Further, we develop incremental algorithms that produce solutions that are no more than a log factor larger than the optimal. We also consider Rendezvous Point Selection where multicast groups have been established based on user preferences for a set of available flows. This problem aims at minimizing the total network traffic without overloading any single host node. We derive two versions, BHA and HTCA, with different constraints on the hosts. We develop polynomial time algorithms for the BHA problem. For the HTCA problem, we show that it is NP-complete and develop several approximation algorithms.