Longevity is one the key design goals in the wireless sensor networks. In many applications, longevity of all the sensor nodes in the network is equally important. Therefore, it is imperative to design network protocols that would keep the maximum number of nodes alive for longest possible duration. Towards this goal we study the lexicographic maximum lifetime (Lex-max-life) routing scheme. The objective of Lex-max-life routing is to maximize the time until the lirst set of sensor nodes deplete their battery energies (among all the nodes), then maximize the depletion time for the second set of sensor nodes if the depletion time for the first set of nodes is as long as possible, and then maximize the depletion time for the third set of nodes if the depletion times for the first and second set of nodes are as long as possible and so on. In our previous work by M. Patel et al. (2006), we have shown that if sensor nodes are equipped with non-adaptive transmitters then the Lex-max-life routing problem can be reduced to a min-cost flow or a convex-cost flow problem using a novel cost scaling technique. Hence, we obtain an integral optimal solution in polynomial time. However, the cost scaling technique is not suitable for large problem instances because the cost numbers grow very fast. In this paper, we propose a novel vectorial representation of link costs. The Lex-max-life routing problem is solved by a vectorial version of min-cost flow or convex-cost flow algorithm which (i) Improves running time complexity and (ii) Circumvents the number explosion phenomenon. Thus, developed algorithm is computationally very efficient, scalable and easy to implement.

We consider a wireless sensor network made of sensor nodes capable of sensing and communication, relay nodes capable of communication, and base stations responsible for collecting data generated by sensor nodes, to be deployed in sensor field. We address the problem of placing the sensor nodes, relay nodes and base stations in the sensor field such that (i) each point of interest in the sensor field is covered by a subset of sensors of desired cardinality (ii) the resulting sensor network is connected and (iii) the sensor network has sufficient bandwidth. We propose several deployment strategies to determine optimal placements of sensor nodes, relay nodes and base stations for guaranteed coverage, connectivity, bandwidth and robustness. We study several different objectives such as minimizing the number of sensor nodes deployed, minimizing the total cost, minimizing the energy consumption, maximizing the network lifetime and maximizing the network utilization. The placement problems for reliable as well as unreliable/probabilistic detection models are formulated as integer linear programs (ILPs). The practicality, effectiveness and performance of the proposed strategies are illustrated through simulations.

Path restoration is an important approach for building survivable telecommunication backbone networks. Path restoration is known for high restoration efficiency and its ability to protect against single link, multiple link and node failures. Path restoration can be formulated as the well-known multi-commodity network flow (MCNF) problem. While many centralized algorithms have been proposed for solving the MCNF problem, distributed algorithms have received very little attention. This paper presents an online distributed multi-commodity flow approximation algorithm specifically tailored for path restoration. Our algorithm uses O(|E|diam/sup 2/) messages and O(diam/sup 2/) time in the worst case, and substantially fewer messages and less time in practical networks. When simulated on a sample real-life backbone network similar to those used by the telecommunication service providers, our algorithm finds a solution significantly faster than many published algorithms.

This paper presents the results of a comparative study of spare capacity assignment for original quasipath restoration (OQPR), improved quasipath restoration (IQPR), link restoration (LR), path restoration (PR) and link-disjoint path restoration (LDPR) schemes. Numerical results indicate that the restoration schemes studied can be sorted from most expensive to least expensive (spare capacity assignment cost) in the following order: LR, OQPR, IQPR, LDPR and PR. Since IQPR is computationally very efficient, simpler than PR, scalable, and economical in spare capacity assignment, it provides a good alternative to PR when quick restoration is desired. However, due to the potential difficulty in rapid failure isolation coupled with the increasing importance of restoration speed and simplicity, LDPR is an attractive scheme. A number of networks with different topologies and projected traffic demand patterns are used in the experiments to study the effect of various network parameters on spare capacity assignment cost. The experimental analysis shows that network topology, demand patterns and the average number of hops per primary route have a significant impact on the spare capacity assignment cost savings offered by one scheme over the other.