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


  查詢圖書館館藏目錄
系統識別號 U0002-1707201317271400
中文論文名稱 適用於低功耗無線感測網路之資料收集協定
英文論文名稱 Date Collection in Low Duty-Cycled Wireless Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系資訊網路與通訊碩士班
系所名稱(英) Master's Program in Networking and Communications, Department of Computer Science and Information En
學年度 101
學期 2
出版年 102
研究生中文姓名 劉炳麟
研究生英文姓名 Ping-Lin Liu
學號 600420391
學位類別 碩士
語文別 英文
口試日期 2013-06-07
論文頁數 56頁
口試委員 指導教授-潘孟鉉
委員-廖文華
委員-洪麗玲
委員-潘孟鉉
中文關鍵字 資料收集  圖論  排程  建樹演算法  無線感測網路 
英文關鍵字 Convergecast  graph theory  scheduling  tree construction  wireless sensor network 
學科別分類 學科別應用科學資訊工程
中文摘要 先前許多於無線感測網路(WSNs)的研究,提出使用睡醒機制來支援低耗能的運作,時間被分隔為許多的時間槽,而時間槽的分配可分為link-based和receiver-based。本篇研究主要採用receiver-based的分配方法,在網路中各節點已樹狀結構連結,並各自分配到所屬的時間槽,每個周期於自己和父節點的時間槽醒來進行資料收集與資料回報,其餘時間進入省電模式。本篇提出集中式與分散式的時槽分配演算法來達到低延遲匯集資料傳輸,我們發現可藉由更換樹狀結構中節點的連線來進一步降低延遲,具體說明,通過設計我們允許節點可以更換鄰居節點的父節點,以便使用更佳的時間槽來達到降低延遲的目的,模擬與實作結果顯示我們的設計可以有效率的降低延遲。然而這些過去的研究只針對常規模式下的資料收集,我們則進一步考慮事件發生時資料回報的場景,網路中可能會隨機有緊急突發事件的數據報告持續一段時間。我們分配給每個路由器一個常規模式下的時間槽和多個事件模式下的時間槽。我們提出建樹的演算法來支援事件模式下時間槽的分配。模擬的結果顯示我們的設計的確可以同時支援常規模式和事件模式下的資料回報。
英文摘要 Many previous studies propose to use wake-up scheduling to support energy efficient operations in wireless sensor networks (WSNs). In those studies, time is divided into slots, and the proposed wake-up scheduling (or say slot assignment) algorithms can be categorized into link-based and receiver-based. In this thesis, we focus on the scenario that nodes are scheduled in the receiver-based fashion. In the network, nodes are connected by a tree structure, and each node is assigned to a slot. A node wakes up at its slot and its parent’s slot to collect data from its children and to report data to its parent, respectively. Then, it can go to sleep to save energy. This thesis proposed a centralized and a distributed slot assignment schemes to support low latency convergecast. We observe that when assigning slots, the latency can be further reduced by reconnecting some tree links. More specifically, by the designed rules, a node is allowed to locally modify some of its neighbors’ parents. Then, the node can be assigned to a better slot, and will have the benefit of reducing its report latencies. Simulation and implementation results show that using the proposed schemes, convergecast latencies can be effectively reduced. However, these pervious works schedule network nodes with regular patterns to support regular data reporting. In this work, we further consider the event data reporting scenario, where the network may randomly have urgent events. Each network node is assigned to a regular mode slot and several event mode slots. We design tree formation algorithms to facilitate assigning event mode slots. Simulation results show that our designs can indeed support both regular and event data reporting.
論文目次 Contents
Chapter 1 Introduction 1
Chapter 2 Preliminaries 5
2.1 Related Works 5
2.2 Network Model 7
Chapter 3 Low Latency convergecast 11
3.1 Observations 11
3.2 A Centralized Scheme 13
3.3 A Distributed Scheme 18
3.4 Simulation Results 23
Chapter 4 Event data convergecast 27
4.1 Concept 27
4.2 Tree Formation Scheme 27
4.3 The Slot Assignment Rules 31
4.4 Event Mode Operations 32
4.5 Simulation Results 33
Chapter 5 Conclusions and future direction 36
Bibliography 38
Appendix 41

List of Figures
Figure 1.1: The scenario of the receiver-based wake-up scheduling. 2
Figure 2.1: (a) Node v’s one-hop and two-hop neighbor relationships. (b) Example of a node locates in multiple sets. 8
Figure 3.1: Examples of effects on changing of tree links. 12
Figure 3.2: An example of reconnecting nodes in phase 2. 15
Figure 3.3: An example of violating interference-free slot assignment. 21
Figure 3.4: Slot assignment results by pCEN, pDIS, rDTD, and rDSA. 24
Figure 3.5: Simulation results of averaged L(G) with varied (a) network sizes, (b) network density ratio N, (c) transmission ranges, and (d) C values of
Section 3.3. 25
Figure 4.1: The system flow of event data convergecast. 28
Figure 4.2: An example of our centralized tree formation algorithm. 30
Figure 4.3: Simulation results on averaged I(T). 33
Figure 4.4: Simulation results on averaged Lr(G). 34
Figure 4.5: Simulation results on averaged received event data reports (in unit of KB) per superframe. 35  
參考文獻 [1] P.-Y. Chen, W.-T. Chen, Y.-C. Tseng, and C.-F. Huang.Providing group tour guide by RFIDs and wireless sensor networks. IEEE Trans.Wireless Communications,8(6):3059–3067, 2009.
[2] H. Choi, J. Wang, and E. A. Hughes. Scheduling for information gathering on sensor network. ACM/Kluwer Wireless Networks, 15(1):127–140, 2009.
[3] J. Elson, L. Girod, and D. Estrin. Fine-grained network time synchronization using reference broadcasts. In Proc. of the USENIX Symposium on Operating Systems Design and Implementation(OSDI), 2002.
[4] J. Hayes, S. Beirne, K.-T. Lau, and D. Diamond. Evaluation of a low cost wireless chemical sensor network for environmental monitoring. In Proc. of IEEE Sensors Conference,2008.
[5] B. Hohlt, L. Doherty, and E. Brewer. Flexible power scheduling for sensor networks. In Proc. of ACM/IEEE Int’l Conference on Information Processing in Sensor Networks(IPSN), 2004.
[6] H. Huo, Y. Xu, H. Zhang, Y.-H. Chuang, and T.-C.Wu. Wireless-sensor-networks-based healthcare system: a survey on the view of communication paradigms. International Journal of Ad Hoc and Ubiquitous Computing(IJAHUC), 8(3):135–154, 2011.
[7] IEEE standard for information technology - telecommunications and information exchange between systems - local and metropolitan area networks specific requirements part 15.4: wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs), 2003.
[8] O. D. Incel, A. Ghosh, B. Krishnamachari, and K. Chintalapudi. Fast data collection in tree-based wireless sensor networks. IEEE Trans. Mobile Computing, 11(1):86–99,2012.
[9] M. Li and Y. Liu. Underground coal mine monitoring with wireless sensor networks. ACM Trans. on Sensor Networks,5(2):1–29, 2009.
[10] C.-Y. Lin, W.-C. Peng, and Y.-C. Tseng. Efficient in-network moving object tracking in wireless sensor networks. IEEE Trans. Mobile Computing, 5(8):1044–1056, 2006.
[11] G. Lu, B. Krishnamachari, and C. S. Raghavendra. An adaptive energy-efficient and low-latency MAC for tree-based data gathering in sensor networks. Wireless Commununications and Mobile Computing (WCMC), 7(7):863–875, 2007.
[12] B. Malhotra, I. Nikolaidis, and M. A. Nascimento. Aggregation convergecast scheduling in wireless sensor networks. ACM/Kluwer Wireless Networks, 17(2):319–335, 2011.
[13] A. Marco, R. Casas, J. L. S. Ramos, V. Coarasa, A. Asensio, and M. S. Obaidat. Synchronization of multihop wireless sensor networks at the application layer. IEEE Wireless Communications, 18(1):82–88, 2011.
[14] N.-H. Nguyen, Q.-T. Tran, J.-M. Leger, and T.-P. Vuong. A real-time control using wireless sensor network for intelligent energy management system in buildings. In Proc. of IEEE Workshop on Environmental Energy and Structural Monitoring Systems (EESMS),2010.
[15] S. Nikoletseas and J. D. Rolim. Theoretical Aspects of Distributed Computing in Sensor Networks. Springer, 2011.
[16] M.-S. Pan, H.-W. Fang, Y.-C. Liu, and Y.-C. Tseng. Address assignment and routing schemes for ZigBee-based long-thin wireless sensor networks. In Proc. of IEEE Int’l Conference on Vehicular Technology Conference (VTC), 2008.
[17] M.-S. Pan and Y.-C. Tseng. Quick covergecast in ZigBee beacon-enabled tree-based wireless sensor networks. Computer Communications (ComCom), 31(5):999–1011,2008.
[18] M.-S. Pan, L.-W. Yeh, Y.-A. Chen, Y.-H. Lin, and Y.-C. Tseng. A WSN-based intelligent light control system considering user activities and profiles. IEEE Sensors Journal, 8(10):1710–1721, 2008.
[19] Y. Sun, O. Gurewitz, and D. B. Johnson. RI-MAC: A receiver-initiated asynchronous duty cycle mac protocol for dynamic traffic loads in wireless sensor networks. In Proc. of ACM Int’l Conference on Embedded Networked Sensor Systems (SenSys), 2008.
[20] L. Tang, Y. Sun, O. Gurewitz, and D. B. Johnson. PW-MAC: An energy-efficient predictive-wakeup mac protocol for wireless sensor networks. In Proc. of IEEE INFOCOM, 2011.
[21] Y.-C. Tseng, M.-S. Pan, and Y.-Y. Tsai. Wireless sensor networks for emergency navigation. IEEE Computer, 39(7):55–62, 2006.
[22] G. Werner-Allen, K. Lorincz, M. Welsh, O. Marcillo, J. Johnson, M. Ruiz, and J. Lees. Deploying a wireless sensor network on an active volcano. IEEE Internet Computing, 10(2):18–25, 2006.
[23] D. B. West. Introduction to Graph Theory. Prentice Hall, 2001.
[24] F.-J. Wu and Y.-C. Tseng. Distributed wake-up scheduling for data collection in treebased wireless sensor networks. IEEE Communications Letters, 13(11):850–852, 2009.
[25] L.-H. Yen, Y. W. Law, and M. Palaniswami. Risk-aware distributed beacon scheduling for tree-based ZigBee wireless networks. IEEE Trans. Mobile Computing, 11(4):692–703, 2012.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-07-23公開。
  • 同意授權瀏覽/列印電子全文服務,於2018-07-23起公開。


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