無線感測網路圓碟覆蓋旅途問題;The Disk Covering Tour Problem for Wireless Sensor Networks

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/58573

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/58573

Title:	無線感測網路圓碟覆蓋旅途問題;The Disk Covering Tour Problem for Wireless Sensor Networks
Authors:	楊家俊;Yang,Jia-Jiun
Contributors:	資訊工程學系
Keywords:	無線感測網路;覆蓋推銷員問題;圓碟覆蓋問題;K-means演算法;Wireless Sensor Networks;Covering Salesman Problem;Disk Covering Problem;K-means algorithm
Date:	2012-11-27
Issue Date:	2012-12-25 13:38:04 (UTC+8)
Publisher:	國立中央大學
Abstract:	在無線感測網路(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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	697	View/Open

社群 sharing

Loading...