跳到主要內容

臺灣博碩士論文加值系統

(3.235.174.99) 您好!臺灣時間:2021/07/24 19:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:李靜雅
研究生(外文):Li, Jingya
論文名稱:在無線感測網路中使用Fast Marching Method計算最小成本路徑
論文名稱(外文):To Determine Minimum Cost Routing Path in Wireless Sensor Networks Using the Fast Marching Method
指導教授:柯仁松
指導教授(外文):Ko, Rensong
口試委員:江為國蕭宏章紀光輝
口試委員(外文):Chiang, WeikuoHsiao, HungchangChi, Kuanghui
口試日期:2012-07-26
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:36
中文關鍵詞:快速推進法無線感測網路最小成本路徑
外文關鍵詞:Fast marching methodWireless sensor networkMinimum cost routing path
相關次數:
  • 被引用被引用:0
  • 點閱點閱:676
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
在無線感測網路(wireless sensor networks)中,對於每個使用者而言,存取無線感測網路資料傳輸的最小成本路徑是主要探討的議題之一,主要目的在於利用最短的時間將訊息從起始地傳送到目的地,除了時間的效益外,亦可有效控制傳輸的成本。著名的貪婪演算法(greedy algorithm)Dijkstra algorithm可以說是最小成本路徑的基礎,我們以Fast Marching Methods來求非線性方程式Eikonal Equations的近似解;並根據每個節點的距離值以Back-tracking來求其路徑座標得到路線,最後以這兩個演算法來做比較。
使用幾何光學(Geometrical Optics)的方法在宏觀的概念下,考慮在不同密度下,欲最佳化的網路模組,使用Fast Marching Method計算其成本函數,再針對不同的網路模組根據梯度向量找出最佳的繞送路徑。並期望能將此方法套用到更多不同模組上。

For each user in wireless sensor networks, the minimum cost routing path of wireless sensor networks is one of the main issues to explore. The main purpose is to use the shortest time to transfer messages from the beginning to the destination, in addition to the benefits of time, can effectively control the cost of transmission. A well-known greedy algorithm-Dijkstra algorithm can be said that the basis of the minimum cost path. We use Fast Marching Method to seek approximate solution of the non-linear equation-Eikonal Equation. According to the distance value of each node using the Back-tracking to find the coordinates to get the route, and finally to compare these two algorithms.
In the concept of macroscopic use the method of geometrical optics. When using the Fast Marching Method to calculate the cost function, the network module which you want to optimize must consider in different density. For different network modules based on the gradient vector to find the optimal routing path. Focusing on finding the best routing path on the basis of the gradient vector. It is expected to apply this method to a wide range of modules.

第一章 緒論
第二章 相關研究
第三章 計算距離值
3.1 Dijkstra演算法
3.2 Fast Marching Method
3.2.1 Fast Marching Method原理
3.2.2逆向有限差分法
3.2.3 Fast Marching Method架構
3.3 回溯法
第四章 成本函數
4.1 Optics Analogy
4.2套用網路模組
第五章 實驗模擬
5.1 最小成本路徑
5.2 成本函數網路模組
第六章 結論與未來展望
參考文獻

[1] B. Karp, H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, ACM, Boston, MA, US, pp.243–254,(2000).
[2]Coblenz, Ilten, Mooney, “Geodesics:Analytical and Numerical Solutions,” (May, 2007).
[3]C. Wook, S.K. Das and K. Basu, “Angle-Based Dynamic Path Construction for Route Load Balancing in Wireless Sensor Networks,” Wireless Communication and Networking Conference, vol. 4, pp.2474-2479,(Mar. 2004).
[4]D. Martinez, L. Velho, P. C. Carvalho, “Geodesic Paths on Triangular Meshes,” SIBGRAPI '04 Proceedings of the Computer Graphics and Image Processing, XVII Brazilian Symposium, pp.210-217,(2004).
[5]E.W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, pp.269-271,(1959).
[6]Garrido, Moreno, Blanco & Jurewicz, “Path Planning for Mobile Robot Navigation using Voronoi Diagram and Fast Marching,” Inter-national conference on Intelligent robots and systems, pp.2376–2381,(2006).
[7]G. G. Finn, “Routing and Addressing Problems in Large Metropolitan-Scale Internetworks,” Research ISI/RR-87-180,Information Sciences Institute,(March 1987).
[8]H. Tian, et al., “SPEED: a stateless protocol for real-time communication in sensor networks,” Proceedings of the 23rd International Conference on Distributed Computing Systems, pp.46, (May 2003).
[9]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. E. Cayirci, “A Survey on Sensor Networks,” IEEE Commun. Mag. 40 (8), pp.102–114,(2002).
[10]I. Stojmenovic, et al., “Depth First Search and Location Based Localized Routing and QoS Routing in Wireless Networks,” Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, pp.173,(August 2000)
[11]J. A. Sethian, “A fast marching level set method for monotonically advancing fronts,” Proc.Nat. Acad Sci. U.S.A., vol. 93, no. 4, pp.1591–1595, (1996).
[12]Long-Shyang Su, “3D Model Retrieval – Using Geodesic Distance,” National Cheng Kung University,(2002).
[13]M.G.Crandall, and P.-L.Lions, “Viscosity solutions of Hamilton-Jacobi equations,” Trans.Amer.Math.Soc., vol .277, pp.1-43,(1983).
[14]M. Kalantari, M. Shayman, “Routing in Wireless Ad Hoc Networks by Analogy to Electrostatic Theory,” IEEE International Conference on Communications, Vol. 7, Paris, France, pp.4028–4033,(2004).
[15]Nick Rawlinson, “Fast Marching Tomography Package:Instruction Manual,” Research School of Earth Sciences, Australian National University, Canberra ACT 0200
[16]Po-Liang Lin, Ren-Song Ko , “An Efficient Data-Gathering Scheme for Heterogeneous Sensor Networks viaMobile Sinks,” International Journal of Distributed Sensor Networks Volume,(2012).
[17]P. Jacquet, “Geometry of Information Propagation in Massively Dense Ad hoc Networks,” Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, Roppongi Hills, Tokyo, Japan, pp.157–162,(2004).
[18]P. Gupta, P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Trans.Inform. Theory 46 (2), pp.388–404, (2000).
[19]P. Bose, et al., “Routing with guaranteed delivery in ad hoc wireless networks,” Wirel. Netw., vol. 7, pp.609-616,(2001).
[20]Q. Fang, et al., “Locating and bypassing holes in sensor networks,” Mob. Netw. Appl., vol. 11, pp.187-200,(2006).
[21]R. Bellman and R. Kalaba, “Dynamic programming and modern control Theory,” London Mathematical Society Monographs,(1965).
[22]R. Catanuto, G. Morabito, S. Toumpis, “Optical Routing in Massively Dense Networks: Practical Issues and Dynamic Programming Interpretation,” in Wireless Communication Systems. ISWCS '06. 3rd International Symposium on, pp. 83-87,(2006).
[23]R. Catanuto, et al., “Optical/Optimal Routing in Massively Dense Wireless Networks,” IEEE International Conference on Computer Communications. IEEE, pp.1010-1018,(2007).
[24]R. Catanuto, et al., “On asymptotically optimal routing in large wireless networks and Geometrical Optics analogy,” Computer Networks, vol. 53, pp.1939-1955, (2009).
[25]R. Catanuto and G. Morabito, “Optimal Routing in Dense Wireless Multihop Networks as a Geometrical Optics Solution to the Problem of Variations,” IEEE ICC, Istanbul, Turkey, pp.134-139,( June 2006).
[26]W.-J. Liu and K.-T. Feng,“Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 8, pp. 910-922, (2009).

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top