先前許多於無線感測網路(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.