 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：87 、訪客IP：52.15.86.184
姓名 楊家俊(Jia-Jiun Yang) 查詢紙本館藏 畢業系所 資訊工程學系 論文名稱 無線感測網路圓碟覆蓋旅途問題
(The Disk Covering Tour Problem for Wireless Sensor Networks)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 在無線感測網路(Wireless Sensor Network, WSN) 中利用行動裝置來增進網路效能的議題十分熱門，例如利用行動資料騾(data mule)協助蒐集資料，或利用行動無線充電器(mobile wireless charger)進行無線充電等，但是行動裝置的自身電量上限往往成為限制其運作能力的因素之一。本篇論文主要目的為減少行動裝置在無線感測網路中運作過程的移動電量成本，我們提出圓碟覆蓋旅途問題(Disk Covering Tour Problem, DCTP)。此問題定義為在給定平面點及起始點的條件下，找出一條最小成本(cost)的旅途(tour)，此旅途由起始點出發經過多個停駐點(tour stop)回到起始點。停駐點不需在給定的點上，但每一個給定的點至少要能與旅途中的某個停駐點的距離在給定的範圍內。旅途成本為行動裝置行加速、減速以離開或進入停駐點，以及定速經過兩個旅途中相鄰停駐點所耗費的電量，一般而言，停駐點個數與旅途長度均會影響旅途成本。文獻中與DCTP最為相關的議題莫非是旅行推銷員問題(Traveling Salesman Problem, TSP)和其變形問題，然而此問題限制旅途停駐點必須在給定的點上，此種限制不太貼切於一些感測網路的應用場景。我們認為停駐點個數越少可能會減少旅途成本，將減少停駐點個數問題視為圓碟覆蓋問題(Disk Covering Problem, DCP)，提出Decreasing K-means (DK-means)演算法嘗試找出近似(nearly)最少圓碟來覆蓋所有給定點，再透過得到的停駐點以Lin-Kernighan heuristic(LKH)找出近似最短的旅途。透過實驗模擬我們比較其他相關方法(Covering Salesman Problem演算法與QI-Ferry方法)，發現我們的方法具有旅途成本較小的優勢，而且當給定點個數越多時，我們方法的優勢會越來越明顯。 摘要(英) Using mobile devices to enhance functions of wireless sensor networks (WSN) is a hot topic. For example, mobile devices can act as chargers to help with wireless charging or as data mules to help with data collection. However, energy consumption caused by mobility is the main factor to affect the use of mobile devices. In this thesis, we proposed Disk Covering Tour Problem (DCTP) addressing how to reduce the energy consumption caused by mobility. DCTP is concerned with how to find a minimum cost tour to cover a given set of points in the Euclidean plane. A tour starts from the starting position given, passes through several tour stops, and goes back to the starting point. A tour stop is not necessary on a given point, and a mobile device can stop at a tour stop to cover sensors within a specific distance. We consider the energy consumed by the acceleration, deceleration, and cruise between adjacent tour stops as the cost in DCTP. In general, the number of tour stops and tour length affect the cost significantly. Traveling Salesman Problem (TSP) and its variants are related to DCTP. But the tour stops in TSP should be on all given points. This may not be practical for some application of WSN. It is likely that fewer tour stops lead to lower costs. Disk Covering Problem (DCP) considers using the minimum number of disk (or equivalently tour stops) to cover given points is also related DCTP. We propose the Decreasing K-means (DK-means) algorithm to find nearly minimum number of tour stop to cover all given points and then find a nearly shortest tour passing through all tour stops with Lin-Kernighan heuristic (LKH). We simulate the proposed algorithm and compare it with related method, the Covering Salesman Problem algorithm and the QI-Ferry method. It is show that tours returned by the proposed algorithm lower costs than those returned by the related method. The proposed algorithm becomes more efficient when the given points are increasing. 關鍵字(中) ★ 無線感測網路
★ 覆蓋推銷員問題
★ 圓碟覆蓋問題
★ K-means演算法關鍵字(英) ★ Wireless Sensor Networks
★ Covering Salesman Problem
★ Disk Covering Problem
★ K-means algorithm論文目次 目錄
中文摘要 i
Abstract ii
目錄 iii
圖目錄 iv
表目錄 v
一、緒論 1
二、相關研究 5
2.1 啟發式方法解覆蓋推銷員問題 5
2.2啟發式途程規劃演算法解 QI-Ferry 7
2.3 LKH演算法解旅行推銷員問題 10
2.4貪婪演算法(Greedy Algorithm)解部分節點覆蓋問題 12
三、問題定義與應用場景 15
3.1 圓碟覆蓋旅途問題(Disk Covering Tour Problem, DCTP) 15
3.2應用無線感測場景 16
四、提出方法 17
4.1 使用K-means演算法解覆蓋問題 17
4.2透過最小包含圓(Smallest Enclosing Circle Problem)修正群集中心 20
4.3 Decreasing K-means (DK-means) Method 21
五、實驗模擬 23
5.1 模擬環境 23
5.2 效能分析 25
5.3 效能評估 26
六、結論 30
參考文獻 31
參考文獻 [1]Tzung-Shi Chen, Ping-Wen Wu, “On Data Collection Using Mobile
Robot in Wireless Sensor Networks,” IEEE Transactions on
Systems, Man and Cybernetics, Part A: Systems and Humans, Vol.41,
pp. 1213–1224, 2011.
[2]A.M. Zungeru, Li-Minn Ang, Kah Phooi Seng, “Termite-Hill: Routing
towards a Mobile Sink for Improving Network Lifetime in Wireless
Sensor Networks,” 2012 Third International Conference on
Intelligent Systems, Modelling and Simulation (ISMS), pp. 622–
627, 2012.
[3]J. Current, D. Schilling, “The Covering Salesman Problem,”
Transportation Sciences, vol. 23, pp. 208–213, 1989.
[4]Ke Li, Hao Luan, Chien-Chung Shen, “QI-Ferry: Energy-Constrained
Wireless Charging in Wireless Sensor Networks,” IEEE Wireless
Communications and Networking Conference, pp. 2515–2520, 2012.
[5]K. Helsgaun, “An effective implementation of the Lin-Kernighan
traveling salesman heuristic,” European Journal of Operational
Research, vol. 126, no. 1, pp. 106–130, 2000.
[6]Guiling Wang, Mary Jane Irwin , Piotr Berman , Haoying Fu , and
Tom La Porta, “Optimizing Sensor Movement Planning for Energy
Efficiency,” in Proceedings of the 2005 International Symposium on
Low Power Electronics and Design, pp. 215–220, 2005.
[7]Bin Xiao, Jiannong Cao, Qingfeng Zhuge, Yi He, Edwin H.-M.
Sha,“Approximation algorithms design for disk partial covering
problem, ”in Proceedings. 7th International Symposium on Parallel
Architectures, Algorithms and Networks, pp.104– 109, 2004.
[8]Li-Wen Chen, Chi-Chang Chen, “The partial coverage problems in
wireless sensor networks,” The Fourth Workshop on Wireless Ad Hoc
and Sensor Networks, pp. 95–102, 2008.
[9]Wasim El-Hajj, Mohsen Guizani, “A Fast Distributed and Efficient
Virtual Backbone Election in Large Scale MANETs,” Global
Telecommunications Conference, pp. 1–6, 2006.
[10]S. Lin, B. W. Kernighan, “An Effective Heuristic Algorithm for
the Traveling-Salesman Problem,” Operation Research, vol. 21,
pp. 498–516, 1973.
[11]J. Elzinga and D.W. Hearn, “The Minimum Covering Sphere
Problem,” Management Science, Vol. 19, 96–104, 1972.
[12]J. R.CURRENT, C. S. REVELLE AND J. L. COHON, “The Minimum
Covering/ Shortest Path Problem,” Decision Sci. 19, pp.490–503,
1954.
指導教授 江振瑞(Jehn-Ruey Jiang) 審核日期 2012-11-30 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit