DBac: deadline based data collection using CSMA/CD and earliest deadline first (EDF) scheduling in wireless sensor network

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    Wireless Sensor Network (WSN) has an enormous scope of utilizations in detecting different parameters such as temperature, pressure, sound, pollution, etc. The sensed data in each sensor node are a valuable one. To communicate the information to the base station for further processing, a lot of strategies are available. Each sensor senses the data in different sampling rate depending upon the sudden raise in the sensing parameters. Data communication to the base station is very critical due to the dynamicity of the environment during the stipulated time.The sensed data should reach the base station before the data becomes invalid due to the violation of the deadline. In order to avoid deadline violation so that the sensed data becomes useless, this paper proposing a novel data collection algorithm based on the popular Earliest Deadline First (EDF) scheduling algorithm. The various simulation parameters are taken into account to verify the performance of the proposed method and the result shows that it achieves high throughput, low delay, high Packet Delivery Ratio (PDR) and low energy consumption.



  • Keywords

    Data Collection; Deadline; Earliest Deadline First (EDF)Scheduling; Mobile Sink; Wireless Sensor Networks (WSN).

  • References

      [1] O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis, “Collection tree protocol ” , Proc. 7th ACM Conf. Embedded Netw. Sensor Syst., pp. 1–14, 2009.https://doi.org/10.1145/1644038.1644040.

      [2] E. Lee, S. Park, F. Yu, and S.-H. Kim, “Data gathering mechanism with local sink in geographic routing for wireless sensor networks”, IEEE Trans. Consum. Electron. vol. 56, no. 3, pp. 1433– 1441, 2010.https://doi.org/10.1109/TCE.2010.5606280.

      [3] Y. Wu, Z. Mao, S. Fahmy, and N. Shroff , “Constructing maximum- lifetime data-gathering forests in sensor networks”, IEEE/ ACM Trans. Netw., vol. 18, no. 5, pp.1571–1584,2010.https://doi.org/10.1109/TNET.2010.2045896.

      [4] K. Xu, H. Hassanein, G. Takahara, and Q. Wang, “Relay node deployment strategies in heterogeneous wireless sensor networks ”, IEEE Trans. Mobile Comput., vol. 9, no. 2, pp. 145–159,2010.https://doi.org/10.1109/TMC.2009.105.

      [5] X.Tang and J. Xu, “Adaptive data collection strategies for lifetime constrained wireless sensor networks”, IEEE Trans. Parallel Distrib. Syst., vol. 19, no. 6, pp. 721–7314, 2010.https://doi.org/10.1109/TPDS.2008.27.

      [6] D. Gong, Y. Yang, and Z. Pan, “Energy-efficient clustering in lossy wireless sensor networks”, J. Parallel Distrib. Comput. vol. 73, no. 9, pp. 1323–1336, 2013.https://doi.org/10.1016/j.jpdc.2013.02.012.

      [7] M. Ma, Y. Yang, and M. Zhao, “Tour planning for mobile data gathering mechanisms in wireless sensor networks”, IEEE Trans. Veh. Technol., vol. 62, no. 4, pp. 1472–1483, 2013.https://doi.org/10.1109/TVT.2012.2229309.

      [8] Z. Zhang, M. Ma, and Y. Yang, “Energy efficient multi-hop polling in clusters of two-layered heterogeneous sensor networks”, IEEE Trans. Comput., vol. 57. No. 2, pp. 231–245, 2008.https://doi.org/10.1109/TC.2007.70774.

      [9] B. Gedik, L. Liu, and P. S. Yu, “ASAP: An adaptive sampling approach to data collection in sensor networks”, IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 12, pp. 1766–1783, 2007.https://doi.org/10.1109/TPDS.2007.1110.

      [10] C. Liu, K. Wu, and J. Pei, “An energy-efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation”, IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 7, pp. 1010–1023, 2007.https://doi.org/10.1109/TPDS.2007.1046.

      [11] M. Zhao, M. Ma, and Y. Yang, “Efficient data gathering with mobile collectors and space-division multiple access technique in wireless sensor networks”, IEEE Trans. Comput., vol. 60, no. 3, pp. 400–417, 2011.https://doi.org/10.1109/TC.2010.140.

      [12] Madhumathy P, Sivakumar D, “Enabling Energy Efficient Sensory Data Collection Using Multiple Mobile Sink“, IEEE Trans. Trans. Technol., vol. 56, no. 5, pp. 1372–1383, 2014.https://doi.org/10.1109/CC.2014.6969791.

      [13] D. Jea, A. A. Somasundara, and M. B. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in sensor networks”, Proc. IEEE/ACM Int. Conf. Distrib. Comput. Sensor Syst., pp. 244–257, 2005.https://doi.org/10.1007/11502593_20.

      [14] M. Zhao, M. Ma, and Y. Yang, “Mobile data gathering with space division multiple access in wireless sensor networks,” Proc. IEEE Conf. Comput. Commun. pp. 1283–1291, 2008. https://doi.org/10.1109/INFOCOM.2008.185.

      [15] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, “Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization”, John Wiley & Sons, 1990.

      [16] M. R. Garey and D. S. Johnson (1979) “Computers and Intractability: A Guide to the Theory of NP Completeness”, San Francisco: W. H. Freeman.

      [17] J. A. Stankovic, M. Spuri, K. Ramamritham, and G. C. Buttazzo, “Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms,” Kluwer Academic Publishers, 1998.https://doi.org/10.1007/978-1-4615-5535-3.

      [18] X. Song and J. W. S. Liu, “Maintaining Temporal Consistency: Pessimistic vs. Optimistic Concurrency Control”, IEEE Transactions on Knowledge and Data Engineering, Vol. 7, No. 5, pp. 786-796, October 1995.https://doi.org/10.1109/69.469820.

      [19] D. Rosenkrantz, R. E. Sterns, and P. M. Lewis, “An analysis of several heuristics for the travelling salesman problem. SIAM Journal on Computing”, 6:563-581, 1977.https://doi.org/10.1137/0206041.

      [20] L. D. Bodin, B. L. Golden, A. A. Assad, and M. Ball, “Routing and scheduling of vehicles and crews”, the state of art. Computers and Operations Research, 10:63212, 1983.

      [21] G. Laporte, “The travelling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research”, 59:231-247, 1992.https://doi.org/10.1016/0377-2217(92)90138-Y.

      [22] P. Toth and D. Vigo, “The Vehicle Routing Problem. Society for Industrial and Applied Mathematics”, Philadelphia, PA, USA, ISBN 0-89871-498-2, 1991.

      [23] M. Solomon, “Algorithms for the vehicle routing and scheduling problem with time window constraints”, Operations Research, 35(2), 1987.https://doi.org/10.1287/opre.35.2.254.

      [24] G. Ghiani, F. Guerriero, G. Laporte, and R. Musmanno, “Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies”, European Journal of Operational Research, 151(1):1-11, 2003.https://doi.org/10.1016/S0377-2217(02)00915-3.

      [25] C. Liu and J. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”, J. ACM, vol. 20, no. 1, 1973.https://doi.org/10.1145/321738.321743.

      [26] Arun A. Somasundara, Aditya Ramamoorthy, and Mani B. Srivastava, “Mobile Element Scheduling with Dynamic Deadlines”, IEEE transactions on mobile computing, vol.6,no. 4, 2007.https://doi.org/10.1109/TMC.2007.57.

      [27] Po-Liang Lin and Ren-Song Ko, “An Efficient Data-Gathering Scheme for Heterogeneous Sensor Networks via Mobile Sinks”, International Journal of Distributed Sensor Networks, Article ID 296296, 2012.https://doi.org/10.1155/2012/296296.

      [28] IEEE Web Page http://www.ieee802.org/3.

      [29] Davood Izadi, Sara Ghanavati, Jemal Abawajy, Tutut Herawan, An alternative data collection-scheduling scheme in wireless sensor networks, Springer, 2016.




Article ID: 14522
DOI: 10.14419/ijet.v7i3.14522

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.