Research On Energy Efficient Topology Control And Rate Control Algorithms

The construction of CDS (Connected Dominating Set) is a challenging andpractical NP-hard problem in graph theory and it is also the theoretical basis inthe constructing of the virtual backbones in wireless sensor networks, which is ofgreat significance in routing, clustering and energy-saving. As energy is limited insensor nodes, to maximize the performance of the network and extend thelifetime are two conflicting optimization goals. Recently, the network utilitybased modeling and cross-layer decomposition show a huge advantage on themulti-objective optimization in the network. It also provides a solution to theoptimization on the energy efficient rate and power control algorithm and MAClayer protocol design.This paper has carried on a thorough and systematic research on energyefficient network topology control and rate control algorithms, which mainlycontributed in the following four aspects:1. The traditional dominating set construction algorithm has beenimproved in this paper by introducing the greedy algorithm. It hasshown that the improved algorithm has a constant approximationratio. A topology control algorithm based on the weighted SteinerTree is proposed to construct the minimum connected dominatingset (MCDS) and a thorough analysis on the performance of thenovel algorithm is also provided to validate the effectiveness of thealgorithm;2. To build an energy efficient hierarchical network topology, the papergives a distributed clustering algorithm based on connecteddominating set. The connectivity of the spanning topology is provedtheoretically and the efficiency in energy saving are validated bysimulations;3. By applying the multi-objective optimization method, this articleintegrates the optimal rate control and energy efficient into anetwork utility maximization problem. A dual composition algorithm is adopted in the distributed approximate algorithm designand analysis. Compared with the traditional works in this field, thisalgorithm focuses on the multi-sink optimization and does not needany feedback factors in the implementations. A detailed analysis onthe optimality of the solution is conducted both theoretically andpractically.4. This article also provides a distributed and adaptive algorithmon the rate and power allocation problem in the Rayleigh fadingchannels. By introducing the concept of goodput, the rate controlproblem is built under the NUM framework. A successiveapproximating approach is applied to deal with the lack of convexityin the constraint equations. The sequence of the iterative solutions isproved to be convergent in the article. As the distributed parametersare estimated locally, the algorithm is also a dynamic and adaptivealgorithm in practice.