在無線感測網路中，感測器通常利用single-hop或是multi-hop的傳輸方式將感測到的資料傳送至匯集點，因此，越靠近匯集點的感測器，為了要轉傳其他節點的資料，會造成耗電量增加，使得感測器之間存在不均勻的能量消耗，從而導致能量空洞(Energy holes)的產生；而在近年來的研究當中顯示，使用移動收集器來蒐集無線感測網路中的資料，可以減緩能量空洞的問題並且大幅延長網路生命週期，而如何有效規劃移動收集器的路線，以便在限定時間內蒐集所有感測器的資料，此問題為NP-hard並決定性地影響系統效率，因此受到許多研究者重視，然而，過往的研究往往假設所有感測器產生的資料量相同且其緩衝區(Buffer)大小並無上限，而這些假設卻不符合現實環境的狀況，特別來講，倘若我們考量感測器緩衝區的大小且感測速率不同的條件下，那麼現有的方法將可能使得緩衝區發生溢位(Buffer overflow)，進而導致封包遺失的問題發生。
基於上述的考量，本論文在限制感測器緩衝區大小以及所偵測到資料量不同的現實考量下，提出兩套移動收集器路徑規劃的方法：Rendezvous planning for reliable data gathering algorithm (RP-RDGA)與Rendezvous planning for reliable data gathering with tour improvement algorithm (RP-RDGTIA)，其中，RP-RDGA會挑選出一部分的感測器作為會面點(Rendezvous point)，而非會面點的感測器則將資料傳送至最近的會面點，最後，移動收集器前往每個會面點來收集資料，而RP-RDGA在挑選會面點時，不但考慮到感測器透過multi-hop通訊所需的能量，同時也考量作為會面點之感測器的緩衝區容量，如此一來，RP-RDGA將可延長網路的生命週期，同時確保封包遺失不會發生，另一方面，RP-RDGTIA更進一步改良RP-RDGA方法，使得移動收集器的行走路線更加縮短。模擬結果顯示，我們所提的演算法幾乎不會發生封包遺失，並且在時間複雜度方面遠低於其他方法。

In a wireless sensor network (WSN), nodes transmit their sensing data to the remote sink via single-hop or multi-hop communications. Therefore, the sensors close to the sink consume more energy, because they are responsible for forwarding data from other nodes. Therefore, energy consumption of sensors is not uniform, and there will exist energy holes in the network. Recently, many research effort show that using a mobile data collector can efficiently deal with the energy hole problem and extend network lifetime. How to efficiently schedule the traveling path of the mobile data collector is NP-hard and significantly affects system performance. This problem thus attracts research attention. However, existing schemes usually assume that each sensor generates the same amount of sensing data, and there is no limitation on the buffer size. These assumptions are not practical. When they become invalid, existing schemes may force some sensors to drop packets due to buffer overflow.
Based on the above consideration, this paper proposes two path scheduling methods for the mobile data collectors, called rendezvous planning for reliable data gathering algorithm (RP-RDGA) and rendezvous planning for reliable data gathering with tour improvement algorithm (RP-RDGTIA). RP-RDGA selects a subset of sensors to be rendezvous point(RPs). Non-RP sensors forward their data to nearby RPs and the mobile data collector will visit each RP to gather data. The selection of RPs considers not only the amount of energy consumed by sensors due to multi-hop communications, but also the buffer capacity of RPs. In this way, we can extend network lifetime and prevent RPs form dropping packets, On the other hand, RP-RDGTIA further improves RP-RDGA by shortening the traveling path. Through simulation, we demonstrate that our proposed algorithms incur almost no packet loss at RPs, and has much less computation overhead than other methods.

論文審定書 i
誌謝 ii
摘要 iii
Abstract iv
圖次 viii
表次 x
第一章 導論 1
1.1 前言 1
1.2 研究動機 3
1.3 研究貢獻與章節架構 4
第二章 相關文獻探討 5
2.1 Direct communicating collection 5
2.2 Multi-hop communicating collection 6
第三章 問題定義 9
3.1 網路模型與假設 9
3.2 能量消耗模型 10
3.3 資料收集路徑規劃問題 10
第四章 研究方法 12
4.1 RP-RDGA 12
4.2 RP-RDGA設計原由 24
4.3 RP-RDGTIA 25
4.4 RP-RDGTIA設計原由 36
4.5 時間複雜度分析 37
第五章 模擬結果與分析 39
5.1 模擬環境與參數設定 39
5.2 感測器數量之影響 41
5.3 Buffer size之影響 47
第六章 結論與未來研究方向 51
參考文獻 52

[1]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102-114, 2002.
[2]N. Wang, N. Zhang, and M. Wang, “Wireless sensors in agriculture and food industry-recent development and future perspective,” Computers and Electronics in Agriculture, vol. 50, no. 1, pp. 1-14, 2006.
[3]L.W. Yeh, Y.C. Wang, and Y.C Tseng, “iPower: an energy conservation system for intelligent buildings by wireless sensor networks,” International Journal of Sensor Networks, vol. 5, no. 1, pp. 1-10, 2009.
[4]L.D. Xu, W. He, and S. Li, “Internet of things in industries: a survey,” IEEE Transactions on Industrial Informatics, vol. 10, no. 4, pp. 2233-2243, 2014.
[5]A. Pantelopoulos and N.G. Bourbakis, “A survey on wearable sensor-based systems for health monitoring and prognosis,” IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol. 40, no. 1, pp. 1-12, 2010.
[6]S.C. Hu, Y.C. Wang, C.Y. Huang, and Y.C. Tseng, “Measuring air quality in city areas by vehicular wireless sensor networks,” Journal of Systems and Software, vol. 84, no. 11, pp. 2005-2012, 2011.
[7]Y.C. Wang and C.C. Yang, “3S-cart: a lightweight, interactive sensor-based cart for smart shopping in supermarkets,” IEEE Sensors Journal, vol. 16, no. 17, pp. 6774-6781, 2016.
[8]J. Lian, K. Naik, and G.B. Agnew, “Data capacity improvement of wireless sensor networks using non-uniform sensor distribution,” International Journal of Distributed Sensor Networks, vol. 2, no. 2, pp. 121-145, 2006.
[9]O. Younis and S. Fahmy, “Heed: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366-379, 2004.
[10]L.A. Villas, A. Boukerche, H.S. Ramos, and H.A.B.F. de Oliveira, “DRINA: a lightweight and reliable routing approach for in-network aggregation in wireless sensor networks,” IEEE Transactions on Computers, vol. 62, no. 4, pp. 676-689, 2013.
[11]Y.C. Wang, Y.Y. Hsieh, and Y.C. Tseng, “Multiresolution spatial and temporal coding in a wireless sensor network for long-term monitoring applications,” IEEE Transactions on Computers, vol. 58, no. 6, pp.827-838, 2009.
[12]Y.C. Wang, F.J. Wu, and Y.C. Tseng, “Mobility management algorithms and applications for mobile sensor networks,” Wireless Communications and Mobile Computing, vol. 12, no. 1, pp. 7-21, 2012.
[13]Y. Yun and Y. Xia, “Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications,” IEEE Transactions on Mobile Computing, vol. 9, no.9, pp. 1308-1318, 2010.
[14]M. Zhao and Y. Yang, “Bounded relay hop mobile data gathering in wireless sensor networks,” IEEE Transactions on Computers, vol. 61, no. 2, pp. 265-277, 2012.
[15]M. Ma, Y. Yang, and M. Zhao, “Tour planning for mobile data-gathering mechanisms in wireless sensor networks,” IEEE Transactions on Vehicular Technology, vol. 62, no. 4, pp. 1472-1483, 2013.
[16]G. Xing, T. Wang, W. Jia, and M. Li, “Rendezvous design algorithms for wireless sensor networks with a mobile base station,” ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 231-240, 2008.
[17]K. Almi''ani, A. Viglas, and L. Libman, “Energy-efficient data gathering with tour length-constrained mobile elements in wireless sensor networks,” IEEE Conference on Local Computer Networks, pp. 582-589, 2010.
[18]H. Salarian, K.W. Chin, and F. Naghdy, “An energy-efficient mobile-sink path selection strategy for wireless sensor networks,” IEEE Transactions on Vehicular Technology, vol. 63, no. 5, pp. 2407-2419, 2014.
[19]Y.C. Wang, “Mobile sensor networks: system hardware and dispatch software,” ACM Computing Surveys, vol. 47, no. 1, pp. 12:1-12:36, 2014.
[20]Y.C. Wang, “A two-phase dispatch heuristic to schedule the movement of multi-attribute mobile sensors in a hybrid wireless sensor network,” IEEE Transactions on Mobile Computing, vol. 13, no. 4, pp. 709-722, 2014.
[21]P. Castiglione and G. Matz, “Energy-neutral source-channel coding with battery and memory size constraints,” IEEE Transactions on Communications, vol. 62, no. 4, pp.1373-1381, 2014.
[22]S. Padakandla, K.J. Prabuchandran, and S. Bhatnagar, “Energy sharing for multiple sensor nodes with finite buffers,” IEEE Transactions on Communications, vol. 63, no. 5, pp.1811-1823, 2015.
[23]R.C. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: modeling a three-tier architecture for sparse sensor networks,” IEEE International Workshop on Sensor Network Protocols and Applications, vol. 1, no. 2, pp. 215-233, 2003.
[24]J. Luo, Q. Zhang, and D. Wang, “Delay tolerant event collection for underground coal mine using mobile sinks,” International Workshop on Quality of Service, pp. 1-9, 2009.
[25]Z. Li, M. Li, J. Wang, and Z. Cao, “Ubiquitous data collection for mobile users in wireless sensor networks,” IEEE INFOCOM, pp. 2246-2254, 2011.
[26]K. Chebrolu, B. Raman, N. Mishra, P.K. Valiveti, and R. Kumar, “Brimon: a sensor network system for railway bridge monitoring,” ACM International Conference on Mobile Systems, Applications, and Services, pp. 2-14, 2008.
[27]R. Sugihara and R.K. Gupta, “Optimal speed control of mobile node for data collection in sensor networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 1, pp. 127-139, 2010.
[28]L. He, J. Pan, and J. Xu, “A progressive approach to reducing data collection latency in wireless sensor networks with mobile elements,” IEEE Transactions on Mobile Computing, vol. 12, no. 7, pp. 1308-1320, 2013.
[29]E. Welzl, “Smallest enclosing disks (balls and ellipsoids),” New Results and New Trends in Computer Science, pp. 359-370, 1991.
[30]J. Tang, S. Guo, and Y. Yang, “Delivery latency minimization in wireless sensor networks with mobile sink,” IEEE International Conference on Communications, pp. 6481-6486, 2015.
[31]X. Zhang, H. Bao, J. Ye, K. Yan, and H. Zhang, “A data gathering scheme for WSN/WSAN based on partitioning algorithm and mobile sinks,” IEEE International Conference on High Performance Computing and Communications, pp. 1968-1973, 2013.
[32]I. Amundson and X.D. Koutsoukos, “A survey on localization for mobile wireless sensor networks,” Mobile Entity Localization and Tracking in GPS-less Environnments, pp. 235-254, 2009.
[33]C. Nilsson, "Heuristics for the traveling salesman problem," 2003, URL: https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf.
[34]Z.M. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, “Exploiting sink mobility for maximizing sensor network lifetime,” IEEE Hawaii International Conference on System Sciences, pp. 1-9, 2005.