跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.86) 您好!臺灣時間:2025/02/08 01:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林書平
研究生(外文):Shu-Ping Lin
論文名稱:具資料集縮能力之無線感測網路節能路由演算法
論文名稱(外文):An Energy-Efficient Data-Centric Routing Algorithm in Wireless Sensor Networks
指導教授:林永松林永松引用關係顏宏旭顏宏旭引用關係
指導教授(外文):Yeong-Sung LinHong-Hsu Yen
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊管理學研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:101
中文關鍵詞:資料集縮資料中心路由高效率節能路由最佳化拉格蘭日鬆弛法混合式整數線性規劃無線感測網路
外文關鍵詞:Data AggregationData-Centric RoutingEnergy-Efficient RoutingOptimizationLagrangean Relaxation MethodMixed Integer Linear ProgrammingWireless Sensor Networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:255
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
近年來無線感測網路在諸多領域上具有高度應用價值,已被視為下一階段無線通訊技訊的殺手級應用。然而受限於硬體以及應用環境,使感測器對於能源消秏具有高度的限制性,因此在感測網路中降低感測器於運作過程所消秏的能源已成為一個重要的研究議題。結合資料集縮 (data aggregation) 能力於感測器中藉此減少資料傳輸量能有效降低感測器的能源消秏,而具備資料集縮能力之感測網路需有以資料為中心 (data-centric) 之路由演算法來充份利用此能力以達到節省能源消秏的目的。

本篇論文研究在感測器具有資料集縮能力之無線感測網路中,建立兼具最小能源消秏量及服務品質之資料集縮樹 (data aggregation tree) 的問題,在考量感測器之路由指定、傳輸半徑 (communication radius) 及資料重傳 (data retransmission) 限制下,透過集縮樹的方式盡可能減少資料的傳輸總量,使感測網路回報資料時所需消秏之總能量最小化,藉此提高感測網路的系統生存時間。此外,為了使問題能更符合應用環境,在考量資料集縮所帶來的集縮延遲時間限制下,我們將最大端對端延遲 (maximum end-to-end delay) 的概念考慮進來,並加以定義為感測器所消秏之集縮等待能源消秏,藉以更精確的描述感測網路的總能源消秏。

我們將整個問題數學模式化為一個嚴謹的混合式整數線性最佳化數學模型,目標函式為最小化資料傳輸所需之總能源消秏,此數學問題在本質上是一個整數非線性規劃問題,問題本身具有高度的複雜性和困難度。本論文採用以拉格蘭日鬆弛法為基礎的方法來處理此一複雜問題,並根據所得到的結果改良演算法以得到較佳的資料集縮樹。實驗結果顯示,我們不但能有效率地求得此問題解,且在問題解的效能上亦比其它既有的演算法更為優越。
Recently wireless sensor networks (WSNs) have attracted a great deal of attention due to their potential for numerous military, environmental detection, and civil applications. Sensor nodes in WSNs are highly energy-constrained, because of the limitations of hardware and the infeasibility of recharging sensor nodes under a severe environment. When a sensor is in operation, therefore, reducing energy consumption during the forwarding and sensing of data is a crucial issue in WSNs. Incorporating sensor nodes with data aggregation capabilities to transmit less data in WSNs could reduce total energy consumption. However, this calls for an efficient and effective data-centric routing algorithm to facilitate this potential advantage.

In this thesis, our work emphasizes on the construction of an energy-efficient data aggregation tree that possesses good QoS and minimizes the total energy consumption of sensor nodes simultaneously. In the first part of this thesis, we model the data-centric routing problem based on a rigorous mixed integer linear mathematical formulation, where the objective function is to minimize the total transmission cost, subject to multicast tree and data aggregation constraints. With the advances in sensor network technology, sensor nodes with configurable transmission radius capability would further reduce energy consumption. Thus, the second part of this paper considers the transmission radius assignment of each sensor node and the data-centric routing assignment jointly. The objective function is to minimize the total power consumption together with consideration of construction of a data aggregation tree and sensor node transmission radius assignment. Finally, the effects of data retransmission and maximum end-to-end delay due to data aggregation delay are also considered in order to reflect the tradeoff between the advantages and the costs of data aggregation. We take the properties of QoS in wireless sensor networks as a new energy consumption metric that can not only maintain the traditional transmission delay, but also simultaneously reduce the energy consumption of sensor nodes operating in idle mode. How to construct a data aggregation tree that is energy-efficient and has QoS properties is a complicated problem that needs to be investigated. We conceive a rigorous mathematical formulation, where the objective function is to minimize the total energy consumption of data transmission subject to tree, data retransmission, and maximum end-to-end delay constraints.

The solution approach is based on Lagrangean relaxation in conjunction with novel optimization-based heuristics. With the exceptional properties of Lagrangean relaxation we are able to efficiently solve this complicated optimization problem, and derive an effective algorithm for routing assignments and construct a data aggregation tree simultaneously. Through our computational experiments, we show that the proposed algorithms calculate better solutions than other existing heuristics. When considering QoS routing in WSNs, the proposed algorithms can not only construct a better data aggregation tree in terms of energy consumption, but also maintain good maximum end-to-end delay.
謝 誌 I
論文摘要 III
THESIS ABSTRACT V
Table of Contents IX
List of Tables XII
List of Figures XIV
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 7
1.3 Literature Survey 9
1.3.1 Data Aggregation Tree without QoS 9
1.3.2 Data Aggregation Tree with QoS 12
1.4 Proposed Approach 15
1.5 Thesis Organization 16
Chapter 2 Problem Formulation of DCR and EDCR 17
2.1 Problem Description 17
2.2 Problem Formulation 18
2.2.1 DCR Problem 18
2.2.2 EDCR Problem 24
Chapter 3 Data Aggregation Tree with QoS Routing 27
3.1 Problem Description 27
3.2 Problem Formulation 31
3.3 Extension to the Model without Aggregation 40
Chapter 4 Solution Approach 41
4.1 Lagrangean Relaxation Method 41
4.2 DCR Problem 44
4.2.1 Solution Approach 44
4.2.2 Lagrangean Relaxation 44
4.2.3 The Dual Problem and the Subgradient Method 47
4.3 EDCR Problem 48
4.3.1 Solution Approach 48
4.3.2 Lagrangean Relaxation 48
4.3.3 The Dual Problem and the Subgradient Method 51
4.4 Data Aggregation Tree with QoS Routing 53
4.4.1 Solution Approach 53
4.4.2 Lagrangean Relaxation 53
4.4.3 The Dual Problem and the Subgradient Method 61
Chapter 5 Getting Primal Feasible Solutions 63
5.1 Getting Primal Feasible Solutions of DCR 63
5.2 Getting Primal Feasible Solutions of EDCR 67
5.3 Getting Primal Feasible Solutions for Data Aggregation Tree with QoS Routing 70
Chapter 6 Computational Experiments 75
6.1 Computational Experiments of DCR 75
6.1.1 Experiment Environments 75
6.1.2 Experiment Results 76
6.2 Computational Experiments of EDCR 80
6.2.1 Experiment Environments 80
6.2.2 Experiment Results 81
6.3 Computational Experiments of Data Aggregation Tree with QoS Routing 84
6.3.1 Experiment Environments 84
6.3.2 Experiment Results 86
Chapter 7 Conclusion and Future Works 94
7.1 Summary 94
7.2 Future Works 96
Reference 97
Appendix 99
[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Networks Flows—Theory, Algorithms, and Applications”, Prentice Hall, 1993.
[2] K. Akkaya, M. Younis and M. Youssef, “Efficient Aggregation of Delay-Constrained Data in Wireless Sensor Networks”, Internet Compatible QoS in Ad Hoc Wireless Networks, 2005.
[3] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, August 2002.
[4] V. Annamalai, S. Gupta, and L. Schwiebert, “On tree-based converge-casting in wireless sensor networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference, Vol. 3, 2003, pp. 1942.
[5] J. Carle and D. Simplot, “Energy Efficient Area Monitoring by Sensor Networks”, IEEE Computer, Vol. 37, No 2 (2004) 40-46.
[6] J.-H. Chang and L. Tassiulas, “Energy Conserving Routing in Wireless Ad-hoc Networks”, Proc. IEEE INFOCOM 2000, pp. 22–31, Tel Aviv, Israel, Mar. 2000.
[7] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-completeness”, Freeman, San Francisco, 1979.
[8] J. Heidemann, F. Silve, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, “Building Efficient Wireless Sensor Networks with Low-Level Naming”, 18th ACM Symposium on Operating Systems Principles, October 21-24, 2001.
[9] C. Intanagonwiwat, R. Govindan and D. Estrin, “Directed Fiffusion: A Scalable and Robust Communication Paradigm for Sensor Networks”, ACM/IEEE MOBICOM August 2000.
[10] 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.
[11] Koushik Kar, Murali Kodialam, T. V. Lakshman, Leandros Tassiulas, "Routing for network capacity maximization in energy-constrained ad-hoc networks", IEEE INFOCOM 2003 - The Conference on Computer Communications, vol. 22, no. 1, Mar 2003 pp. 673-681.
[12] B. Krishnamachari, D. Estrin, and S.Wicker, "Modelling Data-Centric Routing in Wireless Sensor Networks", IEEE INFOCOM 2002.
[13] V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava, “Energy-aware Wireless Microsensor Networks”, IEEE Signal Processing Magazine, March 2002.
[14] V. Rodoplu, and Teresa H. Meng, “Minimum Energy Mobile Wireless Networks”, IEEE Journal on Selected Areas in Communications (JSAC), Vol. 17, No. 8, August 1999.
[15] S.T. Sheu, T.-H Tsai and JH Chen, “MR 2 RP : The Multi-Rate and Multi-Range Routing Protocol for IEEE 802.11 Wireless Ad Hoc Networks”, ACM/Kluwer Wireless Networks, Volume 9, Number 3, May 2003 pp. 165-177.
[16] S. Singh, M. Woo, and C. S. Raghavendra, “Power-Aware Routing in Mobile Ad Hoc Networks”, ACM/IEEE MOBICOM 1998.
[17] I. Solis and K. Obraczka, “The Impact of Timing in Data Aggregation for Sensor Networks”, IEEE International Conference on Communications (ICC), Paris, France, June 2004.
[18] 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.
[19] C.-K. Toh, ”Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks”, IEEE Communications Magazine, June 2001.
[20] S. Upadhyayula, V. Annamalai, and S. K. S. Gupta,” A Low-Latency and Energy-Efficient Algorithm for Convergecast in Wireless Sensor Networks”, IEEE GLOBECOM, 2003.
[21] M. Younis, K. Akkaya, M. Eltowiessy and A. Wadaa, “On Handling QoS Traffic in Wireless Sensor Networks”, HAWAII International Conference on System Sciences (HICSS-37), Big Island, Hawaii, January 2004.
[22] Moustafa A. Youssef, Mohamed F. Younis, Khaled A. Arisha, "A Constrained Shortest-path Energy-aware Routing Algorithm for Wireless Sensor Networks", WCNC 2002 - IEEE Wireless Communications and Networking Conference, vol. 3, no.1, March 2002 pp. 682-687.
[23] Y. Yu, B. Krishnamachari, and V. K. Prasanna, “Energy-Latency Tradeoffs for Data Gathering in Wireless Sensor Networks”, IEEE INFOCOM, March 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top