||Date Collection in Low Duty-Cycled Wireless Sensor Networks
||Master's Program in Networking and Communications, Department of Computer Science and Information Engineering
wireless sensor network
||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.
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
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
|| 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.
 H. Choi, J. Wang, and E. A. Hughes. Scheduling for information gathering on sensor network. ACM/Kluwer Wireless Networks, 15(1):127–140, 2009.
 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.
 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.
 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.
 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.
 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.
 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.
 M. Li and Y. Liu. Underground coal mine monitoring with wireless sensor networks. ACM Trans. on Sensor Networks,5(2):1–29, 2009.
 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.
 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.
 B. Malhotra, I. Nikolaidis, and M. A. Nascimento. Aggregation convergecast scheduling in wireless sensor networks. ACM/Kluwer Wireless Networks, 17(2):319–335, 2011.
 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.
 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.
 S. Nikoletseas and J. D. Rolim. Theoretical Aspects of Distributed Computing in Sensor Networks. Springer, 2011.
 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.
 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.
 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.
 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.
 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.
 Y.-C. Tseng, M.-S. Pan, and Y.-Y. Tsai. Wireless sensor networks for emergency navigation. IEEE Computer, 39(7):55–62, 2006.
 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.
 D. B. West. Introduction to Graph Theory. Prentice Hall, 2001.
 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.
 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.