Maximum lifetime routing and resource allocation in wireless sensor networks

Wireless Sensor NETworks (WSNETs) have emerged as a new paradigm of networks consisting of small, intelligent sensing devices that communicate wirelessly with each other and coordinate to monitor and control a plethora of physical systems. Such networks have found applications in many areas, most notably in building and industrial automation and environmental observation.;This dissertation considers two optimization problems arising in WSNETs. The first is a maximum lifetime routing problem which has been formulated as a linear programming problem in the literature. An optimal value of the linear program corresponds to a prediction of the optimal network lifetime. The thesis studies this problem under the natural assumption that uncertainty is present in the various network parameters (e.g., available energy stored at the nodes and energy depletion rates due to transmissions and receptions). It is proved that for specific, yet typical network topologies, the actual network lifetime will reach the predicted value with a probability that converges to zero as the number of nodes grows large. This suggests that the formulation available in the literature is not informative under uncertainty. A series of alternative robust problem formulations, ranging from pessimistic to optimistic, is developed. A set of parameters enable the tuning of the conservatism of the formulation to obtain network flows with a desirably high probability that the corresponding lifetime prediction will be achieved. A number of properties for the robust network flows and corresponding energy allocation is established. An illustrative set of numerical results highlight the trade-off between predicted lifetime and the probability it is achieved. In addition, a special limiting regime of massively deployed WSNETs with point sources and sinks is studied. This regime essentially corresponds to a continuous version of the maximum lifetime routing problem with energy allocation. In such a continuous setting, the optimal network flows follow a straight line from the traffic sources to their nearest sinks with the proper amount of energy allocated on that line segment.;The second problem considered by the thesis is a resource allocation problem. In WSNETs the sensor nodes collect and send information to sink nodes---via processes referred to as sessions---through potentially other nodes that act as relays. Sessions are admitted only if there are enough available resources (e.g., energy, buffer space, CPU time, sufficiently large wireless transmission rates) at relay nodes on a selected path from source to destination. Admitted sessions pay a "fee" for consuming these resources and session arrival rates are modulated by the prevailing "prices" issued by the WSNET. The nodes may select routes dynamically from multiple alternatives for admitted sessions. The optimal resource allocation problem is formulated as maximizing long-term average welfare for the whole WSNET. Identifying the globally optimal dynamic policy is hardly possible due to the well-known curse of dimensionality. Implementation of such a dynamic policy is also unattractive. The thesis develops an alternative "static pricing" policy which is asymptotically optimal in a limiting regime of many, relatively small, sessions. These asymptotically optimal prices can be found by solving a nonlinear optimization problem. A distributed and asynchronous iterative algorithm which utilizes only local information available (or measured) by the nodes is proposed and shown to converge to the optimal static prices under rather general assumptions. The convergence of the algorithm is proved by leveraging stochastic approximation techniques.