淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0907202009033500
中文論文名稱 運用公車收集無線感測網路資料達最大化傳輸量及網路生命期的分散式機制
英文論文名稱 Distributed Bus-based Data Collection Mechanisms for Maximizing Throughput and Lifetime in WSNs
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 108
學期 2
出版年 109
研究生中文姓名 林崇智
研究生英文姓名 Chung-Chih Lin
學號 804410016
學位類別 博士
語文別 英文
口試日期 2020-06-12
論文頁數 124頁
口試委員 指導教授-張志勇
委員-陳宗禧
委員-石貴平
委員-廖文華
委員-陳裕賢
委員-張志勇
中文關鍵字 資料收集  無線感測網路  時槽排程  傳輸電量調整  資源公平性 
英文關鍵字 Data collection  Wireless sensor network  Slot scheduling  Power adjusting  Fairness 
學科別分類 學科別應用科學資訊工程
中文摘要 資料收集(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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2020-07-27公開。
  • 同意授權瀏覽/列印電子全文服務,於2020-07-27起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信