跳到主要內容

臺灣博碩士論文加值系統

(44.211.26.178) 您好!臺灣時間:2024/06/16 01:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:郭文政
研究生(外文):Wen-Cheng Kuo
論文名稱:具資料集縮能力無線感測網路系統生命週期之最大化
論文名稱(外文):Maximization of System Lifetime for Data-Centric Wireless Sensor Networks
指導教授:林永松林永松引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊管理學研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:51
中文關鍵詞:生命週期資料集縮高效率節能資料中心路由最佳化拉格蘭日鬆弛法整數線性規劃無線感測網路。
外文關鍵詞:LifetimeData aggregationEnergy-EfficientData-centric RoutingOptimizationLagrangean Relaxation MethodInteger Linear ProgrammingWireless Sensor Network.
相關次數:
  • 被引用被引用:0
  • 點閱點閱:168
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,無線感測網路在於諸多應用上都具有其優越性。然而,在硬體和環境的限制下,感測器對於能源消耗具有高度限制性。採用資料集縮(data aggregation)能夠有效率地降低資料傳送量,以達到節省能耗的目的。

本篇論文研究在感測器具有資料集縮能力之無線感測網路中,使用集縮樹的適當路由分配以完成最大化系統生命週期。我們將問題化為一個數學模式,目的函式為最大化系統生命週期,並採用拉格蘭日鬆馳法獲得近似最佳解。
In recent years, wireless sensor networks have the advantages in a variety of applications. However, due to the limitations of hardware and the environment, the sensors are highly energy-constrained. By adopting data aggregation, we can effectively reduce the amount of data and thereby save energy consumption.

In this thesis, we adopt data aggregation trees to efficiently arrange routing assignments in order to maximize the system lifetime of data-centric WSNs. We model the problem a mathematical formulation, where the objective function is to maximize the system lifetime, and use Lagrangean Relaxation method to derive an optimal solution.
謝 詞 I
論文摘要 II
THESIS ABSTRACT III
Table of Contents IV
List of Tables VI
List of Figures VII
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Literature Survey 4
1.3.1 Data Aggregation Tree 4
1.3.2 Clustering 6
1.3.3 Genetic Algorithm 7
Chapter 2 Problem Formulation 9
2.1 Problem Description 9
2.2 Problem Notation (IP) 12
2.3 Problem Formulation (IP) 14
Chapter 3 Solution Approach 17
3.1 Introduction to Lagrangean Relaxation Method 17
3.2 Lagrangean Relaxation (LR) 19
3.4.1 Subproblem 1 (related to decision variable 、 ) 21
3.4.2 Subproblem 2 (related to decision variable ) 22
3.4.3 Subproblem 3 (related to decision variable 、 ) 23
3.4.4 Subproblem 4 (related to decision variable ) 24
3.3 The Dual Problem and the Subgradient Method (IP) 25
Chapter 4 Getting Primal Feasible Solutions 27
4.1 Lagrangean Relaxation Results 27
4.2 Getting Primal Feasible Solutions 27
4.3 Simple Heuristic Algorithms 30
Chapter 5 Computational Experiments 31
5.1 Experiment Environment 31
5.2 Random Network 33
5.2.1 Network Topology 33
5.2.2 Solution Quality 34
5.3 Grid Network 37
5.3.1 Network Topology 37
5.3.2 Solution Quality 38
5.4 Result Discussion 41
Chapter 6 Conclusion and Future Work 43
6.1 Conclusion 43
6.2 Future Work 44
References 47
[1] Bhaskar Krishnamachari and Fernando Ord´o˜nez, “Analysis of Energy-Efficient, Fair Routing in Wireless Sensor Networks through Non-linear Optimization”, Workshop on Wireless Ad hoc, Sensor, and Wearable Networks, in IEEE Vehicular Technology Conference, October 2003.[2] K. Kalpakis, K. Dasgupta and P. Namjoshi. “Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks.” Computer Networks Journal, 42(6):697–716, August 2003.

[3] H. O. Tan and I. Korpeoglu, “Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks”, ACM SIGMOD Record, vol. 32, no. 4, pp. 66-71, 2003.

[4] B. Krishnamachari, D. Estrin, and S.Wicker, "Modelling Data-Centric Routing in Wireless Sensor Networks." IEEE INFOCOM 2002.

[5] M.L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems,” Management Science, Volume 27, Number 1, pp. 1-18, January 1981.

[6] M.L. Fisher, “An Application Oriented Guide to Lagrangian Relaxation,” Interfaces, Volume 15, Number 2, pp. 10-21, April 1985.


[7] A.M. Geoffrion, “Lagrangean Relaxation and its Use in Integer Programming,” Mathematical Programming Study, Volume 2, pp. 82-114, 1974.

[8] M.S. Bazaraa, H.D. Sherali, and C.M. Shetty, “Lagrangian Duality and Saddle Point Optimality Conditions”, Nonlinear Programming: Theory and Algorithms, 2nd Edition, pp. 199-242, John Wiley & Sons, Inc, Singapore, 1993.

[9] B. Jourdan and Olivier L. de Weck, “Layout Optimization for a Wireless Sensor Network Using a Multi-Objective Genetic Algorithm” IEEE Semiannual Vehicular Technology Conference, Milan, Italy, May 17-19, 2004.
[10] James R. Yee and Frank Yeong-Sung Lin, “Routing Algorithms for Circuit Data Networks”, Computer Networks Journal, p185-p208, 1992.

[11] W. Heinzelman, A. Chandrakasan and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless Microsensor Networks", the 33rd Hawaii International Conference on System Sciences, Jan. 2000.

[12] Jamal N. Al-Karaki and Ahmed E. Kamal, "Routing Techniques in Wireless Sensor Networks: A Survey", IEEE Wireless Communication, Dec. 2004.

[13] S. Lindsey and C. S. Raghavendra, "PEGASIS: Power-Efficient Gathering in Sensor Information Systems", IEEE Aerospace Conference, March 2002.

[14] Hong-Hsu Yen, Frank Yeong-Sung Lin, “Near-optimal tree-based access network design”, Computer Communication 28(2) 236-245, 2005.
[15] H.S. Yen, F.Y.S. Lin and S.P. Lin, “Efficient Data-centric Routing in Wireless Sensor Networks”, IEEE ICC, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊