請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/35939
標題: | 具資料集縮能力之無線感測網路節能路由演算法 An Energy-Efficient Data-Centric Routing Algorithm in Wireless Sensor Networks |
作者: | Shu-Ping Lin 林書平 |
指導教授: | 林永松(Yeong-Sung Lin),顏宏旭(Hong-Hsu Yen) |
關鍵字: | 資料集縮,資料中心路由,高效率節能路由,最佳化,拉格蘭日鬆弛法,混合式整數線性規劃,無線感測網路, Data Aggregation,Data-Centric Routing,Energy-Efficient Routing,Optimization,Lagrangean Relaxation Method,Mixed Integer Linear Programming,Wireless Sensor Networks, |
出版年 : | 2005 |
學位: | 碩士 |
摘要: | 近年來無線感測網路在諸多領域上具有高度應用價值,已被視為下一階段無線通訊技訊的殺手級應用。然而受限於硬體以及應用環境,使感測器對於能源消秏具有高度的限制性,因此在感測網路中降低感測器於運作過程所消秏的能源已成為一個重要的研究議題。結合資料集縮 (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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/35939 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 1.27 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。