||Distributed Bus-based Data Collection Mechanisms for Maximizing Throughput and Lifetime in WSNs
||Department of Computer Science and Information Engineering
Wireless sensor network
||資料收集(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)為目的。
||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.
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
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
|| 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.