資料收集(Data collection)是無線感測網路(wireless sensor network)中最重要的研究主題之一。在文獻中，許多研究提出了集中式解決方案來處理資料收集問題。在過去的幾年中，使用行動收集器(mobile sink)進行資料收集受到很多關注。然而，其中多數都認為行動收集器是可控制行動收集器，並由演算法控制其速度、路徑、停止位置，以及執行的任務。實際上，不可控制行動收集器也可以用於資料收集應用。許多研究假設收集器(sink)是固定的，並且所有感測器(sensor)都將其感測資料傳輸到收集器。但是，這將導致工作負載不平衡和網路斷線的問題。其他一些研究則進行可控制行動收集器排程工作。然而，開發於採用可控制行動收集器的演算法並不能移轉至採用不可控制行動收集器的場景。主要原因是不可控制行動收集器的停止和到達時間未知。此外，仍有高硬體成本和可控制行動收集器能量限制等問題尚需克服。本文提出了2個分散式資料收集機制，分別為Distributed Bus-based Data Collection（DBDC）及Energy Balanced Multi-hop Data Collection (EBMDC)，其以公車(bus)為行動收集器，並以無線感測網路達最大化傳輸量(throughput)及網路生命期(network lifetime)為目的。
在DBDC演算法，每個感測器都基於bidding程序與其鄰居協商，使暫存較多資料的感測器可以獲得更多的共享時槽(time slots)，而不用增加其傳輸功率。另為了延長網路生命期，具較多剩餘電量的感測器可以增強其傳輸功率，以釋放更多共享時槽，進而協作幫助暫存較多資料但剩餘電量較少的鄰居節點。在EBMDC演算法，每個感測器依據父節點權重(weight)將其資料分別傳給樹上的多個父節點，以延長網路生命期。然後，每個anchor依據其及其鄰居節點的資料量和剩餘電量，自行排程其傳輸時槽，以便可以將所有資料轉發到公車而不會發生碰撞，並且可以平衡每個anchor的生命期。由實驗結果顯示，所提出的DBDC及EBMDC演算法在傳輸量、網路生命期、時槽使用率、資料遺失率及公平性方面均優於相關工作。

Data collection is one of the most important research topics in WSNs. In literature, many studies have proposed centralized solutions to cope with the data collection problem. Data collection using mobile sink has received much attention in the past years. However, most of them considered controllable mobile sink which is controlled by an algorithm to determine its speed, path, stop locations as well as the performed task. In fact, the uncontrollable mobile sink can be also applied to collect data from a given set of deployed sensors. A number of studies assumed that the sink is fixed and all sensors transmit their data to the sink. However, it leads to the problems of unbalanced workload and network disconnection. Some other studies scheduled the controllable mobile sink. However, the algorithms developed by adopting the controllable mobile sink cannot be applied to the scenarios where the uncontrollable mobile sink is adopted. The main reason is that the stops and arrival time of the uncontrollable mobile sink are unknown. In addition, the problems including the high hardware cost and energy limitation of the controllable mobile sink are still needed to be overcome. This thesis proposes two distributed data collection mechanisms, called Distributed Bus-based Data Collection (DBDC) algorithm and Energy Balanced Multi-hop Data Collection (EBMDC) algorithm, which consider the bus as mobile sink aiming to maximize the amount of collected data and the network lifetime of wireless sensor networks. 
Applying the proposed DBDC, each sensor negotiates with its neighbors based on a bidding procedure such that the sensor that buffers more data can obtain more sharing slots instead of increasing its power level. To prolong the network lifetime, the sensor with higher remaining energy can enlarge its transmission power, aiming to release more sharing slots to cooperatively help the neighbor that buffers more data. In the proposed EBMDC algorithm, each sensor node distributes its data to its multiple parents in trees according to their remaining energies for prolonging the network lifetime. Then each anchor node locally schedules its transmission slots based on its and its neighbors’ data volumes and remaining energies such that all data can be forwarded to the bus without collision and the lifetime of each anchor can be balanced. Experimental study reveals that the proposed DBDC algorithm and EBMDC algorithm outperform related works in terms of throughput, network lifetime, slot utilization, data loss ratio and fairness.

Contents
Contents	V
List of Figures.	VII
List of Tables	IX
Chapter 1. Introduction	1
Chapter 2. Related Work	5
2.1 No-Data-Forwarding Using Controllable mobile sink	5
2.2 Partial-Data-Forwarding Using Controllable Mobile Sink	6
2.3 Uncontrollable Mobile Sink	7
Chapter 3. The Proposed DBDC Algorithm	10
3.1 The Introduction of the proposed DBDC	10
3.2 Network Environment and Problem Formulation	12
3.2.1 Network Environment	12
3.2.2 Problem Formulation	13
3.3 The DBDC Algorithm	19
3.3.1 Initial Phase	20
3.3.2 GTS Slots Scheduling Phase	22
3.3.3 STS Slots Bidding Phase	24
3.3.4 STS Slots and Power Level Adjustment Phase	29
3.4 The Pseudocode of DBDC Algorithm	36
3.5 Performance Evaluation	41
3.6 Summary	66
Chapter 4. The Proposed EBMDC Protocol	68
4.1 The Introduction of the proposed EBMDC	68
4.2 Network Environment and Problem Formulation	70
4.2.1 Network Environment	71
4.2.2 Problem Formulation	71
4.3 The EBMDC Algorithm	77
4.3.1 Initialization Phase	79
4.3.2 Bottom Up Requesting Phase	83
4.3.3 BDC Determining Phase	85
4.4 The Pseudocode of EBMDC Algorithm	94
4.5 Performance Evaluation	100
4.6 Summary	113
Chapter 5. Conclusions	115
References	119

List of Figures
3.1	The scenario considered in the proposed DBDC algorithm		14
3.2	Each round T_c of DBDC consists of beacon interval, DBDC scheduling peroid and data collection period.		20
3.3	An example of case  α_i=1		24
3.4	An example of case  β_i=1		29
3.5	An example of case  γ_i=1		33
3.6	The DBDC algorithm		36
3.7	Two scenarios considered in the experiments		42
3.8	Performance snapshots of selected 6 sensor nodes. Four algorithms are compared in terms of throughput in RCD and SLD scenarios		45
3.9	The comparisons of four algorithms in terms of the throughput in scenario RCD		47
3.10	The comparisons of four algorithms in terms of the throughput in SLD scenario		49
3.11	The comparisons of four algorithms in terms of slot utilization in RCD and SLD scenarios		51
3.12	The comparisons of three algorithms in terms of the network lifetime of the WSNs in RCD and SLD scenarios		53
3.13	The comparisons of four algorithms in terms of the data loss ratio in RCD scenario		56
3.14	The comparisons of four algorithms in terms of the data loss ratio in SLD scenario		58
3.15	The comparisons of four algorithms in terms of fairness index on data transmission in RCD scenario.		60
3.16	The comparisons of four algorithms in terms of fairness index of data transmission in SLD scenario		62
3.17	The comparisons of three algorithms in RCD scenario		64
4.1	An example to illustrate the operations of phase one		83
4.2	An example that sensor s_i transmits its data to three parents, aiming for balancing remaining energies		85
4.3	The EBMDC algorithm		96
4.4	Three algorithms are compared in terms of throughput by randomly selecting six anchor nodes		103
4.5	The comparisons of three algorithms in terms of the throughput		104
4.6	The comparisons of three algorithms in terms of slot utilization		106
4.7	The network lifetimes of the three algorithms are compared		107
4.8	The data loss ratios of three algorithms are compared		110
4.9	The three algorithms are compared in terms of fairness index on data transmission		112

List of Tables
3.1	The Simulation Settings		44
3.2	The performance between DBDC and DBDC-H in term of network lifetime in RCD scenario.		54
4.1	The main notations used in EBMDC Algorithm		94
4.2	The Simulation Settings		101
4.3	The performance between EBMDC and EBMDC-H in term of network lifetime		109

[1]	C. I. Weng, C. Y. Chang, C. Y. Hsiao, C. T. Chang, and H. B. Chen, “On-Supporting Energy Balanced k-Barrier Coverage in Wireless Sensor Networks,” IEEE ACCESS, vol. 6, pp. 13261–13274, Jan. 2018. 
[2]	C. Y. Chang, Y. W. Kuo, P. Xu, and H. Chen, “Monitoring Quality Guaranteed Barrier Coverage Mechanism for Traffic Counting in Wireless Sensor Networks,” IEEE ACCESS, vol. 6, pp. 30778-30792, May 2018.
[3]	Z. Sun, X. Xing, B. Song, Y. Nie and H. Shao, “Mobile Intelligent Computing in Internet of Things: An Optimized Data Gathering Method Based on Compressive Sensing,” IEEE ACCESS, vol. 7, pp. 66110-66122, May 2019.
[4]	S. Gao, H. Zhang, and S. K. Das, “Efficient data collection in wireless sensor networks with path-constrained mobile sinks,” IEEE Transactions on Mobile Computing, vol. 10, no. 4, pp. 592-608, Apr. 2011.
[5]	O. D. Incel, A. Ghosh, B. Krishnamachari, and K. Chintalapudi, “Fast data collection in tree-based wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 11, no. 1, pp. 86-99, Jan. 2012.
[6]	S. Chen, M. Huang, S. Tang, and Y. Wang, “Capacity of data collection in arbitrary wireless sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 52-60, Jan. 2012.
[7]	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, Feb. 2012. 
[8]	S. Ji, R. Beyah, and Z. Cai, “Snapshot and continuous data collection in probabilistic wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 13, no. 3, pp. 626-637, Mar. 2014. 
[9]	D. Kim, B. H. Abay, R. N. Uma, W. Wu, W. Wang, and A. O. Tokuta, “Minimum latency multiple data MULE trajectory planning in wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 13, no. 4, pp. 838-851, Apr. 2014. 
[10]	R. Velmani and B. Kaarthick, “An efficient cluster-tree based data collection scheme for large mobile wireless sensor networks,” IEEE Sensors Journal, vol. 15, no. 4, pp. 2377-2390, Apr. 2015. 
[11]	A. Mehrabi and K. Kim, “Maximizing data collection throughput on a path in energy harvesting sensor networks using a mobile sink,” IEEE Transactions on Mobile Computing, vol. 15, no. 3, pp. 690-704, Mar. 2016. 
[12]	W. M. Wen, S. H. Zhao, C. J. Shang, and C. Y. Chang, “EAPC: Energy-Aware Path Construction for Data Collection Using Mobile Sink in Wireless Sensor Networks,” IEEE Sensors Journal, vol. 18, no. 2, pp. 890–901, Jan. 2018. 
[13]	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, Jun. 2014. 
[14]	A. W. Khan, A. H. Abdullah, M. A. Razzaque, and J. I. Bangash, “VGDRA: A virtual grid-based dynamic routes adjustment scheme for mobile sink-based wireless sensor networks,” IEEE Sensors Journal, vol. 15, no. 1, pp. 526-534, Jan. 2015. 
[15]	K. L. M. Ang, J. K. P. Seng, and A. M. Zungeru, “Optimizing energy consumption for big data collection in large-scale wireless sensor networks with mobile collectors,” IEEE Sensors Journal, vol. 12, no. 1, pp. 616-626, Mar. 2018. 
[16]	R. Deng, S. He, and J. Chen,“An Online Algorithm for Data Collection by Multiple Sinks in Wireless-Sensor Networks,” IEEE Transactions on Control of Network Systems, vol. 5, no. 1, pp. 93 - 104, March 2018.
[17]	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, May 2013.
[18]	X. He, S. Liu, G. Yang, and N. Xiong, “Achieving Efficient Data Collection in Heterogeneous Sensing WSNs,” IEEE ACCESS, vol. 6, pp. 63187-63199, Oct. 2018.
[19]	M. D. Francesco, S. K. Das, and G. Anastasi, “Data collection in wireless sensor networks with mobile elements: a survey,” ACM Transactions on Sensor Networks, vol.8, no.1, pp. 1-31, Aug. 2011.
[20]	M. Ma and Y. Yang, “Data gathering in wireless sensor networks with mobile collectors,” IEEE International Symposium on Parallel and Distributed Processing, Jun. 2008, pp. 1-9.
[21]	R. Sugihara and R. K. Gupta, “Optimal speed control of mobile node for data collection in sensor networks,” IEEE Transactions Mobile Computing, vol. 9, no. 1, pp. 127-139, Jan. 2010.
[22]	A. A. Somasundara, A. Ramamoorthy, and M. B. Srivastava, “Mobile element scheduling with dynamic deadlines,” IEEE Transactions Mobile Computing, vol. 6, no. 4, pp. 395-410, Apr. 2007.
[23]	K. Almi’ani, A. Viglas, and L. Libman, “Energy-efficient data gathering with tour length-constrained mobile elements in wireless sensor networks,” IEEE Local Computer Network Conference, Mar. 2010, pp. 582-589.
[24]	C. Konstantopoulos, G. Pantziou, D, Gavalas, A, Mpitziopoulos, and B. Mamalis, “A rendezvous-based approach enabling energy-efficient sensory data collection with mobile sinks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 5, pp. 809-817, May 2012.
[25]	X. Ren, W. Liang, and W. Xu, “Data collection maximization in renewable sensor networks via time-slot scheduling,” IEEE Transactions on Computers, vol. 64, no. 7, pp. 1870-1883, Jul. 2015.
[26]	C. Wu, Y. Liu, F. Wu, W. Fan, and B. Tang, “Graph-based data gathering scheme in WSNs with a mobility-constrained mobile sink,” IEEE Access, vol. 5, pp. 19463-19477, Aug. 2017.
[27]	K. Shah, M. Di Francesco, G. Anastasi, and M. Kumar, “A framework for resource-aware data accumulation in sparse wireless sensor networks,” Computer Communications, vol. 34, no. 17, pp. 2094-2103, Nov. 2011.
[28]	A. Chakrabarti, A. Sabharwal, and B. Aazhang. “Communication power optimization in a sensor network with a path-constrained mobile observer,” ACM Transactions on Sensor Networks, vol.2, no. 3, pp. 297-324, Aug. 2006.
[29]	A. Ridha, “SEECH: Scalable Energy Efficient Clustering Hierarchy Protocol in Wireless Sensor Networks,” IEEE Sensors Journal, vol. 14, no. 11, pp 3944-3954, Nov. 2014.
[30]	M. Bakshi, B. Jaumard, and L. Narayanan, “Optimum ConvergeCast Scheduling in Wireless Sensor Networks,” IEEE Transactions on Communications, vol. 66, no. 11, pp. 5650-5661, Nov. 2018.
[31]	F. Zhou, Z. Z. Chen, S. Guo, and J. Li, “Maximizing Lifetime of Data-Gathering Trees with Different Aggregation Modes in WSNs,” IEEE Sensors Journal, vol. 16, no. 22, pp. 8167-8177, Nov. 2016.
[32]	C. Sha, D. Song, R. Yang, H. Gao, and H. Huang, “A Type of Energy-Balanced Tree Based Data Collection Strategy for Sensor Network with Mobile Sink,” IEEE ACCESS, vol. 7, pp. 85226-85240, Jun. 2019.
[33]	C. Zhu, S. Wu, G. Han, L. Shu, and H. Wu, “A Tree-Cluster-Based Data-Gathering Algorithm for Industrial WSNs with A Mobile Sink,” IEEE ACCESS, vol. 3, pp. 381-396, Apr. 2015.
[34]	Y.C. Wang and K.C. Chen, “Efficient Path Planning for A Mobile Sink to Reliably Gather Data from Sensors with Diverse Sensing Rates and Limited Buffers,” IEEE Transactions on Mobile Computing, vol. 18, no. 7, pp. 1527-1540, Jul. 2019.
[35]	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, Jul. 2013.
[36]	C. Qiu, H. Shen, and K. Chen, “An Energy-Efficient and Distributed Cooperation Mechanism for K-Coverage Hole Detection and Healing in WSNs,” IEEE Transactions Mobile Computing, vol. 17, no. 6, pp. 1247-1259, Jun. 2018.