利用行動資料收集器(mobile sink)於無線感測網路(Wireless Sensor Network, WSNs)中收集資料已被廣泛的使用，此做法雖然可以避免多步傳輸(multi-hop transmission)所帶來的電量消耗不平衡問題，但不可避免的將會帶來較長之資料延遲時間。因此在本研究當中，我們將探討如何縮短拜訪路徑之長度來降低資料延遲時間。本研究將藉由拜訪感測器通訊範圍重疊的區域，來取代逐一拜訪每一個感測器，然後再利用旅行業務員演算法(Traveling Salesperson Problem algorithm, TSP algorithm)，規劃出拜訪路徑。最後再針對規劃出來的拜訪路徑做進一步的縮減。我們提出一個路徑規劃演算法，名為CTR(Combine-TSP-Reduce)。此方法之好處在於，透過合併拜訪點，可以減少拜訪點的數量，如此一來不但可以縮短拜訪路徑長度，更可以降低利用TSP演算法於規劃拜訪路徑時所需之計算量。由於我們是從交集區域中取一點做為拜訪點，因此規劃出來的路徑將會還有縮短的可能性。故在執行完TSP演算法後，我們將針對規劃出來的拜訪路徑做進一步的優化，藉此進一步地縮短拜訪路徑長度。此外，我們也將加入資料傳輸速率考量，規劃出符合傳輸速率要求的拜訪路徑。經由實驗結果可以驗證，我們所提出的方法，在減少計算量以及縮短拜訪路徑長度上皆有著很好的表現。

Mobile sinks are extensively used for data gathering in Wireless Sensor Networks (WSNs). In this study, we focus on how to shorten the length of traveling path. We propose that the mobile sink visits the overlapping areas of communication regions of sensors instead of sensors one by one. We use the Traveling Salesperson Problem (TSP) algorithm to plan an optimal traveling path to reduce the delay time of data gathering. The benefit of the proposed method is that the number of visiting points is reduced after integration of the visiting points. Our experimental results show that the proposed algorithm delivers good results in terms of time complexity, space complexity, and length of traveling path.

目錄
圖目錄	IV
表目錄	V
第一章　簡介	1
第二章　相關研究	4
第三章　問題定義以及環境假設	6
第四章　方法概述	8
4.1	通訊範圍重疊區域之貢獻值計算	8
4.1.1重疊區域計算規則	10
4.1.2貢獻值分配規則	13
4.2	拜訪區域之代表點計算	18
4.3	拜訪路徑之規畫與調整	23
第五章　演算法與流程	29
第六章　實驗模擬	34
第七章　結論	39
參考文獻	40
附錄-英文論文	43

圖目錄
圖1. 位於多個感測器通訊範圍交集區域的行動資料收集器，可接收來自於這些感測器的訊息	2
圖2. 通訊覆蓋程度(coverage level of communication)	9
圖3. 區域貢獻值	9
圖4. 感測器位置關係示意圖	10
圖5. 重疊區域計算規則之虛擬碼	12
圖6. 交集區域計算之例外情形	13
圖7. 貢獻值分配規則之虛擬碼	14
圖8. 關聯性說明	15
圖9. 區域貢獻值之計算	17
圖10. 拜訪區域形狀	19
圖11. 凹多邊形示意圖	21
圖12. 代表點計算演算法之虛擬碼	22
圖13. 代表點計算	23
圖14. 拜訪路徑調整示意圖	24
圖15. 前後縮拉演算法之虛擬碼	26
圖16. 四個直角三角型	26
圖17. 交集圓與圓外直線之距離關係	27
圖18. CTR演算法之虛擬碼	29
圖19. 使用TSP以及CTR路徑規劃演算法	30
圖20. CTR演算法之執行示意圖	32
圖21. s1、s2、s3、s4透過廣度搜尋法(BFS)建構資料代傳路由樹	33
圖22. 不同數量的感測器對拜訪路長度的影響	35
圖23. 不同感測器數量對CTR路徑長度改進率的影響	35
圖24. 不同通訊範圍對拜訪路徑長度的影響	36
圖25. 不同通訊範圍對CTR路徑長度改進率的影響	36
圖26. 不同通訊範圍對拜訪點的影響	37
圖27. 不同通訊範圍對CTR拜訪點改進率的影響	37
圖28. 不同節點數對拜訪路徑長度的影響	38

表目錄
表1. 圖4之重疊區域關係表	10
表2. 圖6之重疊區域關係表	13
表3. 模擬參數設定	34

參考文獻
[1]	M. Berg, J. Gudmundsson, M.J. Katx, C. Levcopoulos, M.H. Overmars and A.F. Stappen, “TSP with neighborhoods of varying size,” J. Algorithms, vol. 57, pp. 22-36, 2005.
[2]	P. Cheong, K.F. Chang, Y.H. Lai, S.K. Ho, I.K. Sou and K.W. Tam, “A ZigBee-based wireless sensor network node for ultraviolet detection of flame,” IEEE Trans. Ind. Electron., vol. 58, no. 11, pp. 5271-5277, 2011.
[3]	Convex&ConcavePolygons,ttp://en.wikipedia.org/wiki/Convex_and_concave_polygons (accessed June 8, 2015)
[4]	M. Dunbabin and L. Marques, “Robots for environmental monitoring: significant advancements and applications,” IEEE J. Robot. Automat., vol. 19, no. 1, pp. 24-39, 2012.
[5]	D. Gong, and Y. Yang, “Low-latency SINR-based data gathering in wireless sensor networks,” IEEE Trans. Wirel. Commun., vol. 13, no. 6, pp. 3207-3221, 2014.
[6]	J. Gudmundsson and C. Levcopoulos, “A fast approximation algorithm for TSP with neighborhoods,” Nordic J. Computing, vol. 6, no. 4, pp. 469-488, 1999.
[7]	J. He, S. Ji, Y. Pan and Y. Li, “Constructing load-balanced data aggregation trees in probabilistic wireless Sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 7, pp. 1681-1690, 2014.
[8]	L. He, J. Pan, and J. Xu, “A progressive approach to reducing data collection latency in wireless Sensor networks with mobile elements,” IEEE Trans. Mobile Comput., vol. 12, no. 7, pp. 1308-1320, 2013.
[9]	H. Lin, and H. Üstert, “Extract and heuristic algorithms for data-gathering cluster-based wireless Sensor network design problem,” IEEE/ACM Trans. Networking, vol. 22, no. 3, pp. 903-916, 2014.
[10]	K. Lorincz, M. Ruiz, O. Marcillo, J. Johnson, J. Lees and M. Welsh, “Deploying a wireless Sensor network on an active volcano,” IEEE Internet Comput., vol. 10, no. 2, pp. 18-25, 2006.
[11]	M. Ma, Y. Yang and M. Zhao, “Tour planning for mobile data-gathering mechanisms in wireless Sensor networks,” IEEE Trans. Veh. Technol., vol. 62, no. 4, pp. 1472-1483, 2013.
[12]	F. Senel, M.F. Younis, and K. Akkaya, “Bio-inspired relay node placement heuristics for repairing damaged wireless Sensor networks,” IEEE Trans. Veh. Technol., vol. 60, no. 4, pp. 1835-1848, 2011.
[13]	A.A. Somasundara, A. Ramamoorthy, and M.B. Srivastava, “Mobile element scheduling with dynamic deadlines,” IEEE Trans. Mobile Comput., vol. 6, no. 4, pp. 395-410, 2007.
[14]	J. Tao, L. He, Y. Zhuang, J. Pan, and M. Ahmadi, “Sweeping and active skipping in wireless sensor networks with mobile elements,” Proc. IEEE GLOBECOM’12, pp. 106-111, 2012.
[15]	O. Tekdas, V. Isler, J.H. Lim, and A. Terzis, “Using mobile robots to harvest data from Sensor fields,” IEEE Wireless Comm., vol. 16, no. 1, pp. 22-28, 2009.
[16]	B. Wang, Coverage Control in Sensor Networks, Springer press, 2010.
[17]	E. Welzl, “Smallest enclosing disks (Balls and Ellipsoids),” New Results and New Trends in Computer Science, pp. 359-370, Springer, 1991.
[18]	G. Xing, T. Wang, W. Jia and M. Li, “Rendezvous design algorithms for wireless sensor networks with a mobile base station,” Proc. ACM MobiHoc’08, pp. 231-240, 2008.
[19]	J. Yick, B. Mukherjee, D. Ghosal, “Wireless Sensor network survey,” Computer Networks, vol. 52, no. 12, pp. 2292-2330, 2008.
[20]	B. Yuan, M. Orlowska, and S. Sadiq, “On the optimal robot routing problem in wireless Sensor networks,” IEEE Trans. Knowl. Data Eng., vol. 19, no. 9, pp. 1252-1261, 2007.
[21]	Y. Zhou, Y. Zhang, and Y. Fang, “Access control in wireless Sensor networks,” Ad Hoc Netw., vol. 5, no. 1, pp. 3-13, 2007.