Sensor networks are deployed to gather some useful data from a field and forward it toward a set of base stations or sinks for data analysis and decision making. Each sensor node is endowed with a finite amount of energy, and each byte transmission or reception costs a certain fixed fraction of energy as well as a variable fraction that depends on the distance between sender and receiver for transmissions. The trad-itional approach of designing energy-aware routing algorithms for sensor networks by maximizing the so-called lifetime; the time until the first node exhausts its limited bat-tery; is not a panacea because of the expected high level of node redundancy in sensor networks. Instead, maximizing the volume of data collected at the sinks until some particular set of nodes exhaust t...[ Read more ]

Sensor networks are deployed to gather some useful data from a field and forward it toward a set of base stations or sinks for data analysis and decision making. Each sensor node is endowed with a finite amount of energy, and each byte transmission or reception costs a certain fixed fraction of energy as well as a variable fraction that depends on the distance between sender and receiver for transmissions. The trad-itional approach of designing energy-aware routing algorithms for sensor networks by maximizing the so-called lifetime; the time until the first node exhausts its limited bat-tery; is not a panacea because of the expected high level of node redundancy in sensor networks. Instead, maximizing the volume of data collected at the sinks until some particular set of nodes exhaust their battery and partition the network is more desir-able. However, doing so, results in an optimized network throughput at the expense of fairness, some nodes may suffer from starvation. Therefore, data collection maximiza-tion and fairness should be always considered together. We call this problem the fair data collection problem.

In this thesis, we formulate the problem of fair data collection for sensor networks as a utility maximization problem subject to energy constraints, and invoke Lagrange relaxation, duality and sub-gradient technique to solve the problem. Different perfor-mance aspects of the obtained algorithms are considered, particularly the problem of path oscillation, which is well known to happen in any routing algorithm where the link costs are functions of the traffic load. In order to derive an asynchronous algorithm, the proximal optimization method is also considered. Both convergence and energy overhead of the asynchronous algorithm are studied.