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

  • Authors

    • A Felix Arokya Jose Assistant Professor, Department of Computer Science and Engineering,Karunya Institute of Technology and Sciences,Coimbatore
    • C Anand Deva Durai Assistant Professor, King Khalid University, Abha, Saudi Arabia
    • S John Livingston Assistant Professor, Department of Computer Science and Engineering,Karunya Institute of Technology and Sciences,Coimbatore
    2018-08-27
    https://doi.org/10.14419/ijet.v7i3.14522
  • Data Collection, Deadline, Earliest Deadline First (EDF)Scheduling, Mobile Sink, Wireless Sensor Networks (WSN).

  • 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.

     

     

  • References

    1. [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.

  • Downloads

  • How to Cite

    Felix Arokya Jose, A., Anand Deva Durai, C., & John Livingston, S. (2018). DBac: deadline based data collection using CSMA/CD and earliest deadline first (EDF) scheduling in wireless sensor network. International Journal of Engineering & Technology, 7(3), 1956-1961. https://doi.org/10.14419/ijet.v7i3.14522

    Received date: 2018-06-22

    Accepted date: 2018-08-05

    Published date: 2018-08-27