Heuristic solutions to multi-objective optimization problems in wireless networks.

详细信息   

• 作者：Li ; Ke.
• 学历：Doctor
• 年：2011
• 导师：Shen, Chien-Chung,eadvisorShen, Chien-Chungecommittee memberAmer, Paul D.ecommittee memberLloyd, Errol L.ecommittee memberRossi, Louis F.ecommittee member
• 毕业院校：University of Delaware
• Department：Department of Computer and Information Sciences
• ISBN：9781124883090
• CBH：3473696
• Country：USA
• 语种：English
• FileSize：1419250
• Pages：206

文摘

Ad hoc networks, useful in situations where the deployment of any communication infrastructure is difficult or impossible, are formed by autonomous nodes via multihop wireless communications. Wireless sensor networks consist of spatially distributed sensors with both sensing and communication capabilities. These sensors collaboratively form multi-hop networks to facilitate various monitoring tasks. As a critical functionality to facilitate multi-hop communications in both types of wireless networks, the operations of routing usually need to consider multiple desirable but competing performance objectives, e.g., power conservation vs. hop count reduction, path efficiency vs. path redundancy, and tour length minimization vs. sensor coverage maximization. Convoluted tradeoff relationships exist among these conflictive objectives. This dissertation investigates tradeoffs among multiple competing routing objectives in three different networking scenarios, and designs efficient and adaptive routing schemes that balance conflictive optimization objectives. In the first work, we formulate the tradeoff between reducing forwarding power and end-to-end hop count in ad hoc multicast routing as an NP-hard constrained Steiner tree CST) problem, and design a distributed heuristic algorithm termed CSTMAN that adopts the metaphor of Swarm Intelligence. CSTMAN concurrently constructs a CST, performs dynamic transmission power assignment at non-leaf forwarding nodes, and strives to minimize the total transmission power of the multicast tree subject to a given hop count constraint. We also address the similar tradeoff issue in ad hoc unicast routing and design a unicast routing protocol termed CEDAR. Realistic network simulations validate the effectiveness of both protocols and demonstrate the tradeoff relationship between the end-to-end hop count constraint and the total forwarding power. In the second work, we aim at the competing objectives of efficiency in terms of single path and hop count) and robustness in terms of path redundancy) in converge-cast routing from a large number of sensors to the data sinks) for wireless sensor networks, and design two localized protocols that draw inspirations from the biological system of slime mold. Specifically, the path growth protocol treats data sources and sinks as Singular Potentials, and establishes connectivity from the data sinks to all the data sources based on the singular potential model. In addition, by adapting an existing tube dynamics model, the path evolution protocol iteratively computes network connectivity based on local tube flux distributions. Through realistic network simulations and in comparison with ideal closed form or numerical solutions to the corresponding mathematical models, we validate the effectiveness of both protocols as well as the efficiency and robustness of the resulting network connectivity. In the final work, we formulate the tour planning for a data mule to collect sensor data in underwater wireless sensor networks as an NP-hard energy-constrained biobjective underwater data muling problem UDMP). UDMP has the two competing objectives of minimizing the length of a tour and maximizing the number of sensors contacted, while satisfying the energy constraint on the data mule at all times. We design three heuristic algorithms to address three UDMP cases of all-docking UDMP-AD), dockingon- demand UDMP-DoD), and non-confining-cover UDMP-NCC), respectively. Each algorithm computes a set of Pareto-efficient solutions addressing the tradeoff between the two optimization objectives to facilitate tour planning. Simulation results validate the effectiveness and reveal the characteristics of each algorithm. Specifically, UDMPAD can often outperform the optimal solutions of a closely related NP-hard problem by using line-cover, UDMP-DoD usually produces shorter tours than UDMP-AD by avoiding unnecessary docking-visits, and UDMP-NCC can further shorten the tour length by choosing any geometrically computed positions as tour stops rather than confining tour stops to the exact locations of the given sensors.