Content area
Abstract
We investigate the problem of placing sensor nodes, relay nodes and base stations in the sensor field such that (i) each point of interest in the field is covered by a subset of sensors; (ii) resulting sensor network is connected; (iii) the sensor network has sufficient bandwidth; (iv) the network is optimal with respect to the chosen objective. We analyzed 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. The practicality, effectiveness and performance of proposed strategies have been studied through simulations.
We propose Minimum Cost Capacity-constrained Routing (MCCR) which minimizes the total energy consumed in routing without overloading nodes and links. We study the Maximum Lifetime Capacity-constrained Routing (MLCR) which balances the rate of energy consumption among sensor nodes such that the time until the first node drains-out its battery energy (among all the sensor nodes) is maximized. These protocols are derived from polynomial time network flow algorithms. Therefore, protocols are simple, scalable and efficient.
We study the Lexicographic Maximum Lifetime (Lex-max-life) routing scheme where the objective is to maximize the time until the first set of sensor nodes deplete their battery energies, then maximize the depletion time for the second set of sensor nodes, and so on. We develop a fast approximation algorithm for Lex-max-life routing using Linear Programming (LP) solution technique. We also propose an LP based iterative algorithm which finds the optimal solution in polynomial time.
When sensor nodes are equipped with non-adaptive transmitters, we show that Lax-max-life routing problem can be reduced to a convex-cost flow problem using a novel cost scaling technique. Since the convex-cost flow algorithms have polynomial time complexity and integrality property, the proposed algorithm is computationally very efficient and (practically) easy to implement. To the best of our knowledge, the proposed algorithm is the first algorithm that can find an integral optimal solution to Lex-max-life routing problem in polynomial time.
In the cost scaling technique the cost numbers grow very fast. To overcome this limitation, we propose a novel vectorial representation of the link costs which (i) Improves running time complexity and (ii) Circumvents the number explosion phenomenon.
