Dissertation > Excellent graduate degree dissertation topics show

Research on Optimal Routing Tree in Wireless Sensor Networks

Author: LuoDiJun
Tutor: ChenGuiHai
School: Nanjing University
Course: Computer Software and Theory
Keywords: Wireless Sensor Network Routing Shortest Path Tree Network Flow Semi-Matching Lifetime
CLC: TP212.9
Type: Master's thesis
Year: 2011
Downloads: 57
Quote: 0
Read: Download Dissertation

Abstract


In many applications of wireless sensor networks, a sensor node senses the environment to get data and delivers them to the sink via a single hop or multi-hop path. Many systems use a tree rooted at the sink as the underlying routing structure. Since the sensor node is energy constrained, how to construct a good tree to prolong the lifetime of the network is an important problem. We consider this problem under the scenario where nodes have different initial energy, and they can do in-network aggregation. In previous works, it has been proved that finding a maximum lifetime tree from all feasible spanning trees is NP-complete. Since delay is also an important element in time-critical applications, and shortest path trees intuitively have short delay, it is imperative to find a shortest path tree with long lifetime.This paper studies the problem of maximizing the lifetime of data aggregation trees, which are limited to shortest path trees. We find that when it is restricted to shortest path trees, the original problem is in P. We transform the problem into a general version of semi-matching problem, and show that the problem can be solved by min-cost max-flow approach in polynomial time. Also we design a distributed solution. Simulation results show that our approach greatly improves the lifetime of the network and is more competitive when it is applied in a dense network.Additionally, the paper studies the counting problem of computing the number of the shortest path tree with maximum lifetime. We prove that this problem is #P-complete, therefore it is difficult to solve this problem, we also prove that when in-network aggregation is not considered, the problem of finding a shortest path tree with maximum lifetime is NP-complete.

Related Dissertations

  1. Power Aware Routing Protocal Based on OLSR in Ad Hoc Network,TN929.5
  2. Technology for Localization Attack Detection in Wireless Sensor Networks,TP212.9
  3. Ad hoc network routing protocol performance battlefield environment,TN929.5
  4. Drip Irrigation Control System Based on Pulse Width Modulation (PWM),S152.7
  5. An Adaptive Processing Node Selection Based Spatio-Temporal Query Alogrithm,TN929.5
  6. Study on Time Synchronization Method for Urban Lighting Management System,TM923
  7. The Study of Mine Gas Monitoring System Based on Wireless Sensor Networks,TN929.5
  8. The Research on Routing Protocol of Agricultural Environmental Monitoring System Based on Wir Eless Sensor Networks,TN915.04
  9. Node-based intelligent interaction IOT Data Processing,TP391.44
  10. More autonomous vehicle sensor network information transmission Optimal Allocation,TN929.5
  11. Wireless ad hoc network routing protocol AODV credible,TN929.5
  12. Research groups and evacuation simulation algorithm simulation system,TP391.9
  13. Based on Ad Hoc Networks zoning multipath routing protocol research,TN929.5
  14. Distributed target detection in wireless sensor network research,TP212.9
  15. Hysteresis -based optimization of vehicle routing problem,O224
  16. Text CPS technology combined with a sense of community radio and personal digital medical implement,TP399-C8
  17. Cognitive Radio Network Dynamic Spectrum Allocation and Routing Protocols,TN925
  18. DTN model based on multi- node multicast routing algorithm,TN929.5
  19. Based on wireless sensor network target tracking algorithm,TN929.5
  20. Ad hoc networks for reliable routing mechanism semi-physical simulation platform design and implementation,TN929.5
  21. Cross-layer Optimization for Video Coding in Wireless Sensor Networks,TN919.81

CLC: > Industrial Technology > Automation technology,computer technology > Automation technology and equipment > Automation components,parts > Transmitter ( converter),the sensor > Sensor applications
© 2012 www.DissertationTopic.Net  Mobile