| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Energy-Efficient Wake-Up Scheduling for Data Collection and Aggregation
February 2010 (vol. 21 no. 2)
pp. 275-287
Yanwei Wu, Minnesota State University, Mankato
YunHao Liu, Hong Kong University of Science and Technology, Hong Kong
Wei Lou, The Hong Kong Polytechnic University, Hong Kong
A sensor in wireless sensor networks (WSNs) periodically produces data as it monitors its vicinity. The basic operation in such a network is the systematic gathering (with or without in-network aggregation) and transmitting of sensed data to a base station for further processing. A key challenging question in WSNs is to schedule nodes' activities to reduce energy consumption. In this paper, we focus on designing energy-efficient protocols for low-data-rate WSNs, where sensors consume different energy in different radio states (transmitting, receiving, listening, sleeping, and being idle) and also consume energy for state transition. We use TDMA as the MAC layer protocol and schedule the sensor nodes with consecutive time slots at different radio states while reducing the number of state transitions. We prove that the energy consumption by our scheduling for homogeneous network is at most twice of the optimum and the timespan of our scheduling is at most a constant times of the optimum. The energy consumption by our scheduling for heterogeneous network is at most \Theta (\log {\frac{R_{\rm max}}{R_{\rm min}}}) times of the optimum. We also propose effective algorithms to construct data gathering tree such that the energy consumption and the network throughput is within a constant factor of the optimum. Extensive simulation studies show that our algorithms do considerably reduce energy consumption.
[1] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, “Wireless Sensor Networks for Habitat Monitoring,” Proc. First ACM Int'l Workshop Wireless Sensor Networks and Applications (WSNA '02), pp. 88-97, 2002.
[2] M.J. Miller and N.H. Vaidya, “Efficient Bounds for the Stable Set, Vertex Cover, and Set Packing Problem,” Proc. Wireless Comm. and Networking Conf., vol. 4, pp. 2335-2340, 2004.
[3] M. Buettner, G. Yee, E. Anderson, and R. Han, “X-mac: A Short Preamble mac Protocol for Duty-Cycledwireless Sensor Networks,” Proc. First ACM Conf. Embedded Networked Sensor Systems (SenSys), 2006.
[4] M. Alicherry, R. Bhatia, and L.E. Li, “Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks,” Proc. ACM MobiCom, pp. 58-72, 2005.
[5] V.S.A. Kumar, M.V. Marathe, S. Parthasarathy, and A. Srinivasan, “Algorithmic Aspects of Capacity in Wireless Networks,” SIGMETRICS Performance Evaluation Rev., vol. 33, no. 1, pp. 133-144, 2005.
[6] W. Wang, Y. Wang, X.-Y. Li, W.-Z. Song, and O. Frieder, “Efficient Interference Aware tdma Link Scheduling for Static Wireless Mesh Networks,” Proc. ACM MobiCom, 2006.
[7] G. Călinescu, “Computing 2-Hop Neighborhoods in Ad Hoc Wireless Networks,” Proc. Int'l Conf. AD-HOC Networks and Wireless (AdHoc-Now '03), 2003.
[8] P.-J. Wan, K.M. Alzoubi, and O. Frieder, “Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” Proc. IEEE INFOCOM, 2002.
[9] S.C. Ergen and P. Varaiya, “TDMA Scheduling Algorithms for Sensor Networks,” technical report, Univ. of California, Berkley, 2005.
[10] J. Polastre, J. Hill, and D. Culler, “Versatile Low Power Media Access for Wireless Sensor Networks,” Proc. ACM Conf. Embedded Networked Sensor Systems (SenSys), 2004.
[11] I. Rhee, A. Warrier, M. Aia, and J. Min, “ZMAC: A Hybrid MAC for Wireless Sensor Networks,” Proc. ACM Conf. Embedded Networked Sensor Systems (SenSys), 2005.
[12] G.-S. Ahn, E. Miluzzo, A.T. Campbell, S.G. Hong, and F. Cuomo, “Funneling-mac: A Localized, Sink-Oriented MAC for Boosting Fidelity in Sensor Networks,” Proc. ACM Conf. Embedded Networked Sensor Systems (SenSys), 2006.
[13] L. Bao and J.J. Garcia-Luna-Aceves, “Channel Access Scheduling in Ad Hoc Networks with Unidirectional Links,” Proc. Fifth Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm. (DIALM '01), pp. 9-18, 2001.
[14] S. Ramanathan and E.L. Lloyd, “Scheduling Algorithms for Multi-Hop Radio Networks,” Proc. ACM SIGCOMM, pp. 211-222, 1992.
[15] S. Ramanathan, “A Unified Framework and Algorithm for Channel Assignment in Wireless Networks,” Wireless Network, vol. 5, no. 2, pp. 81-94, 1999.
[16] R. Liu and E.L. Lloyd, “A Distributed Protocol for Adaptive Link Scheduling in Ad-Hoc Networks,” Proc. IASTED Int'l Conf. Wireless and Optical Comm. (WOC), 2001.
[17] L. Bao and J. Garcia-Luna-Aceves, “Transmission Scheduling in Ad Hoc Networks with Directional Antennas,” Proc. ACM MobiCom, pp. 48-58, 2002.
[18] X. Yu, S. Mehrotra, and N. Venkatasubramanian, “Sensor Scheduling for Aggregate Monitoring in Wireless Sensor Networks,” Proc. Int'l Conf. Scientific and Statistical Database Management, p. 24, 2007.
[19] S.S. Kulkarni and M. Arumugam, “Infuse: A TDMA Based Data Dissemination Protocol for Sensor Networks,” Int'l J. Distributed Sensor Networks, vol. 2, pp. 55-78, 2006.
[20] K.A. Arisha, M.A. Youssef, and M.F. Younis, “Energy-Aware TDMA-Based MAC for Sensor Networks,” Proc. IEEE Workshop Integrated Management of Power Aware Comm., Computer and Networking, 2002.
[21] S. Cui, R. Madan, A. Goldsmith, and S. Lall, “Energy-Delay Tradeoffs for Data Collection in tdma-Based Sensor Networks,” Proc. 40th Ann. IEEE Int'l Conf. Comm., 2005.
[22] J. Degesys, I. Rose, A. Patel, and R. Nagpal, “DeSync: Self-Organizing Desynchronization and TDMA on Wireless Sensor Networks,” Proc. Sixth Int'l Conf. Information Processing in Sensor Networks (IPSN), pp. 11-20, 2007.
[23] I. Solis and K. Obraczka, “In-Network Aggregation Trade Offs for Data Collection in Wireless Sensor Networks,” Int'l J. Sensor Networks, vol. 1, pp. 200-212, 2006.
[24] X. Dai, F. Xia, Z. Wang, and Y. Sun, “An Energy-Efficient In-Network Aggregation Query Algorithm for Wireless Sensor Networks,” Proc. Int'l Conf. Innovative Computing, Information and Control, vol. 3, pp. 255-258, 2006.
[25] R. Rajagopalan and P. Varshney, “Data-Aggregation Techniques in Sensor Networks: A Survey,” IEEE Comm. Surveys and Tutorials, vol. 8, no. 4, pp. 48-63, Quarter 2006.
[26] A. Keshavarzian, H. Lee, and L. Venkatraman, “Wakeup Scheduling in Wireless Sensor Networks,” Proc. ACM MobiHoc, pp. 322-333, 2006.
[27] P. Djukic and S. Valaee, “Link Scheduling for Minimum Delay in Spatial Re-Use tdma,” Proc. IEEE INFOCOM, pp. 28-36, May 2007.
[28] E. Arikan, “Some Complexity Results about Packet Radio Networks,” IEEE Trans. Information Theory, vol. IT-30, no. 4, pp. 681-685, July 1984.
[29] A. Ephremedis and T. Truong, “Scheduling Broadcasts in Multihop Radio Networks,” IEEE Trans. Comm., vol. 38, no. 4, pp. 456-460, Apr. 1990.
[30] R. Ramaswami and K.K. Parhi, “Distributed Scheduling of Broadcasts in a Radio Network,” Proc. IEEE INFOCOM, pp. 497-504, 1989.
[31] S. Krumke, M. Marathe, and S. Ravi, “Models and Approximation Algorithms for Channel Assignment in Radio Networks,” ACM Wireless Networks, vol. 7, no. 6, pp. 575-584, 2001.
[32] C.Y. Ngo and V.O.K. Li, “Centralized Broadcast Scheduling in Packet Radio Networks via Genetic-Fix Algorithms,” IEEE Trans. Comm., vol. 51, no. 9, pp. 1439-1441, Sept. 2003.
[33] A. Panconesi and A. Srinivasan, “Improved Distributed Algorithms for Coloring and Network Decomposition Problems,” Proc. ACM Symp. Theory of Computing, pp. 581-592, 1992.
[34] A. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan, “End-to-End Packet-Scheduling in Wireless Ad-Hoc Networks,” Proc. ACM Symp. Discrete Algorithms (SODA), pp. 1021-1030, 2004.
[35] T. Moscibroda and R. Wattenhofer, “Coloring Unstructured Radio Networks,” Proc. 17th Ann. ACM Symp. Parallelism in Algorithms and Architectures (SPAA '05), pp. 39-48, 2005.
Index Terms:
Energy consumption, MAC, TDMA, scheduling, routing, WSN.
Citation:
Yanwei Wu, Xiang-Yang Li, YunHao Liu, Wei Lou, "Energy-Efficient Wake-Up Scheduling for Data Collection and Aggregation," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 2, pp. 275-287, Feb. 2010, doi:10.1109/TPDS.2009.45
