MODIFIED RANDOM BIT CLIMBING (λ -MRBC) FOR TASK MAPPING AND SCHEDULING IN WIRELESS SENSOR NETWORKS

(Received: 2018-11-08, Revised: 2018-12-17 , Accepted: 2018-12-23)

Authors Yousef E. M. Hamouda,

Keywords #Application DAG #Optimization methods #Random bit climbing #Task mapping and scheduling #Wireless sensor networks.

Abstract This paper examines the problem of Task Mapping and Scheduling (TMS) in Wireless Sensor Networks (WSNs). The application, which is supposed to be executed in WSNs, can be divided into interdependent tasks. The key objectives of TMS in WSNs are the improvement of execution time, energy consumption and network lifetime. A modified version of Random Bit Climbing (RBC) optimization method, also called λ-Modified Random Bit Climbing (λ-mRBC), is developed to get better and faster optimal or near-optimal solution. In the proposed λ- mRBC method, a new operator, called transposition operator, is added to improve the exploration of search space and hence to escape from the local optima. The deepth of exploration is controlled by using a single parameter (λ). Firstly, a number of sensor nodes is selected to cooperatively execute the application with the purpose of improving the network lifetime. After that, the proposed λ-mRBC method is performed to get the optimal or near-optimal task/sensor pair solution, so that the execution time and energy consumption are minimized. The simulation results show that λ-mRBC method enhances the TMS performance. Compared with the traditional RBC method, the proposed λ-mRBC method converges to better fitness value, make-span and total energy consumption by 19.1%, 19.6% and 22.3%, respectively. Furthermore, the network lifetime is prolonged through using the proposed selection algorithm. The distribution of remaining energy among sensor nodes is improved about three times, compared with the random selection scheme. Furthermore, compared with the random selection, the number of neighbours for sensor nodes is improved by 20.1% using the proposed selection algorithm.

References

[1] B. Sharma and T. C. Aseri, "A Comparative Analysis of Reliable and Congestion-aware Transport Layer Protocols for Wireless Sensor Networks," International Scholarly Research Network (ISRN), Sensor Networks, 2012.

[2] M. Katiyar, H. P. Sinha and D. Gupta, "On Reliability Modeling in Wireless Sensor Networks-A Review," IJCSI International Journal of Computer Science, vol. 9, no. 6, pp. 134–146, 2012.

[3] H. Yetgin, K. T. K. Cheung, M. El-Hajjar and L.H. Hanzo, "A Survey of Network Lifetime Maximization Techniques in Wireless Sensor Networks," IEEE Communication Surveys & Tutorials, vol. 19, no. 2, pp. 828-854, 2017.

[4] P. R. Pereira, A. Grilo, F. Rocha, M. S. Nunes, A. Casaca, C. Chaudet, P. Almstrom and M. Johansson, "End to End Reliability in Wireless Sensor Networks: Survey and Research Challenges," Proceedings of the EuroFGI Workshop on IP QoS and Traffic Control, 2007.

[5] M. A. Kafi, J. B. Othman, M. Bagaa and N. Badache, "CCS_WHMS: A Congestion Control Scheme for Wearable Health Management System," Journal of Medical Systems, vol. 39, no. 12, 2015.

[6] Y. E. Hamouda and M. M. Msallam, "Smart Heterogeneous Precision Agriculture Using Wireless Sensor Network Based on Extended Kalman Filter," Neural Computing and Applications, pp.1-17, 2018.

[7] P. R. C. Araújo, R. H. Filho, J. J. Rodrigues, J. P. Oliveira and S. A. Braga, "Middleware for Integration of Legacy Electrical Equipment into Smart Grid Infrastructure Using Wireless Sensor Networks," Inter. Journal of Communication Systems, vol. 31, no. 1, pp. e3380, 2018.

[8] B. L. R. Stojkoska and K. V. Trivodaliev, "A Review of Internet of Things for Smart Home: Challenges and Solutions," Journal of Cleaner Production, vol. 140, no. 3, pp.1454-1464, 2017.

[9] Y. E. Hamouda and C. Phillips, "Adaptive Sampling for Energy-efficient Collaborative Multi-Target Tracking in Wireless Sensor Networks," IET Wireless Sensor Systems, vol. 1, no. 1, pp.15-25, 2011.

[10] J. Luo and S. Zou, "Strong k-barrier Coverage for One-way Intruders Detection in Wireless Sensor Networks," International Journal of Distributed Sensor Networks, vol. 12, no. 6, 2016.

[11] J. Manikannu and V. Nagarajan, "A Survey of Energy Efficient Routing and Optimization Techniques in Wireless Sensor Networks," IEEE International Conference on Communication and Signal Processing (ICCSP), 2018.

[12] M. Wolf, Smart Camera Design, Springer, 2018.

[13] M. Karakaya and H. Qi, "Coverage Estimation in Heterogeneous Visual Sensor Networks," Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), pp. 41-49, 2012.

[14] C. A. Navarro, N. Hitschfeld-Kahler and L. Mateu, "A Survey on Parallel Computing and Its Applications in Data-parallel Problems Using GPU Architectures," Communications in Computational Physics, vol. 15, no. 2, pp. 285-329, 2014.

[15] L. Dai, H. Xu, T. Chen, Q. Chao and L. Xie, "A Multi-Objective Optimization Algorithm of Task Scheduling in WSN," International Journal of Computers, Communications & Control, vol. 9, no. 2, pp. 160-171, 2014.

[16] Y. Yang, X. Qiu, L. Meng and K. Long, "Task Coalition Formation and Self-adjustment in the Wireless Sensor Networks,". Int J. Commun. Syst., vol. 27, no. 10, pp. 2241–2254, 2014.

[17] C. Blum and A. Roli,"Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison," ACM Computing Surveys (CSUR), vol. 35, no. 3, pp. 268-308, 2003.

[18] I. Boussaïd, J. Lepagnot and P. Siarry, "A Survey on Optimization Metaheuristics," Information Sciences, vol. 237, pp. 82-117, 2013.

[19] Y. Jin, J. Jin, A. Gluhak, K. Moessner and M. Palaniswami, "An Intelligent Task Allocation Scheme for Multihop Wireless Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 3, pp. 444-451, 2012.

[20] R. Shams and F. Khan, "Solving Wireless Network Scheduling Problem by Genetic Algorithm," IAMURE International Journal of Mathematics Engineering & Technology, vol. 2, no. 11, pp. 63-70, 2012.

[21] J. Yang, H. Zhang, Y. Ling, C. Pan and W. Sun, "Task Allocation for Wireless Sensor Network Using Modified Binary Particle Swarm Optimization," IEEE Sensors Journal, vol. 14, no. 13, pp. 882-892, 2014.

[22] A. A. Ferjani, N. Liouane and I. Kacem, "Task Allocation for Wireless Sensor Network Using Logic Gate-based Evolutionary Algorithm," International Conference on Control, Decision and Information Technologies (CoDIT), pp. 654-658, 2016.

[23] V. Papataxiarhis, "Optimal Task Assignment in Sensor Networks," Proc. of the 17th IEEE International Conference on Mobile Data Management (MDM), pp. 26-31, 2016.

[24] S. Abdelhak, C. S. Gurram, S. Ghosh and M. Bayoumi, "Energy-balancing Task allocation on Wireless Sensor Networks for Extending the Lifetime," Proceedings in the 53rd IEEE Int. MWSCAS, pp. 781- 784, 2010.

[25] X. Yin, W. Dai, B. Li, L. Chang and C. Li, "Cooperative Task Allocation in Heterogeneous Wireless Sensor Networks", Inter. Journal of Distributed Sensor Networks, vol. 13, no. 10, pp. 1-12, 2017.

[26] D. R. Bolla, J. J. Jijesh and M. S. Pramod, "Real-Time Data Fusion Applications in Embedded Sensor Network Using TATAS," Indian Journal of Science and Technology, vol. 10, no. 13, pp. 1-7, 2017.

[27] Y. Tian and E. Ekici, "Cross-Layer Collaborative in Network Processing in Multihop Wireless Sensor Networks," IEEE Trans. Mobile Comput., vol. 6, no. 3, pp. 297-310, 2007.

[28] Y. Tian, B. Jarupan, E. Ekici and F. Ozguner, "Real-Time Task Mapping and Scheduling for Collaborative in Network Processing in DVS-Enabled Wireless Sensor Networks," Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006), pp. 1-10, 2006.

[29] Y. E. M. Hamouda and C. Phillips, "Biological Task Mapping and Scheduling in Wireless Sensor Network," Proc. of the IEEE International Conference on Communications Technology and Applications, pp. 914 – 919, 2009.

[30] Y. E. M. Hamouda, "Light Allocation of Tasks in Clustered-based Wireless Sensor Networks", Al-Aqsa University Journal (Natural Sciences Series), vol. 21, pp. 90-119, 2017.

[31] K. N. Devi and R. Muthuselvi, "Parallel Processing of IoT Health Care Applications," Proc. of the 10th IEEE International Conference on Intelligent Systems and Control (ISCO), pp. 1-6, 2016

[32] J. Jiang, G. Han and C. Zhu, "A Complicated Task Solution Scheme Based on Node Cooperation for Wireless Sensor Networks," Proc. of the 22nd IEEE International Conference on Parallel and Distributed Systems (ICPADS), pp. 264-269, 2016.

[33] P. Skocir, M. Kusek and G. Jezic, "Energy-efficient Task Allocation for Service Provisioning in Machine-to-Machine Systems," Concurrency and Computation: Practice and Experience, vol. 29, no. 23, pp. e4269, 2017.

[34] X. Yin, K. Zhang, B. Li, A. K. Sangaiah and J. Wang, "A Task Allocation Strategy for Complex Applications in Heterogeneous Cluster–based Wireless Sensor Networks," International Journal of Distributed Sensor Networks, vol. 14, no. 8, 2018.

[35] E. A. Khalil, S. Ozdemir and S. Tosun, "Evolutionary Task Allocation in Internet of Things-based Application Domains," Future Generation Computer Systems, vol. 86, pp.121-133, 2018.

[36] W. Yu, Y. Huang, E. Ding and A. Garcia-Ortiz, "Joint Task Allocation Approaches for Hierarchical Wireless Sensor Networks," Proc. of the IEEE 7th International Conference on Modern Circuits and Systems Technologies (MOCAST), pp. 1-4, 2018.

[37] N. Bulusu, J. Heidemann and D. Estrin, "GPS-less Low-Cost Outdoor Localization for Very Small Devices," IEEE Personal Communications, vol. 7, no. 5, pp. 28-34, 2000.

[38] T. C. Karalar, S. Yamashita, M. Sheets and J. Rabaey, "A Low-Power Localization Architecture and System for Wireless Sensor Networks," IEEE Workshop on Signal Processing Systems, USA: Signal Processing Society, pp. 89-94, 2004.

[39] O. Sinnen, Task Scheduling for Parallel Systems, New Jersey: John Wiley & Sons, Inc., Hoboken, 2007.

[40] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, "Energy-efficient Communication Protocol for Wireless Microsensor Networks," Proceedings of the IEEE 33rd Annual Hawaii International Conference on System Sciences (HICSS '00), pp. 1-10, 2000.

[41] A. Wang and A. Chandrakasan, "Energy-efficient DSPs for Wireless Sensor Networks," IEEE Trans. Signal Process. Mag., pp. 68-78, 2002.

[42] L. Davis, "Bit-Climbing, Representational Bias and Test Suite Design," Proc. of the 4th International Conference on Genetic Algorithms, pp. 18-23, 1991.

[43] H. Aguirre and K. Tanaka, "Random Bit Climbers on Multiobjective MNK-Landscapes: Effects of 49 and Population Climbing," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 88, pp. 334-345, 2005.

[44] M. A. Abd, S. F. M. Al-Rubeaai, B. K. Singh, K. E. Tepe and R. Benlamri, "Extending Wireless Sensor Network Lifetime with Global Energy Balance," IEEE Sensors Journal, vol. 15, no. 9, pp. 5053–5063, 2015.

[45] I. Dietrich and F. Dressler, "On the Lifetime of Wireless Sensor Networks," ACM Trans. Sen. Netw., vol. 5, no. 1, 2009.

,abstract={This paper examines the problem of Task Mapping and Scheduling (TMS) in Wireless Sensor Networks (WSNs). The application, which is supposed to be executed in WSNs, can be divided into interdependent tasks. The key objectives of TMS in WSNs are the improvement of execution time, energy consumption and network lifetime. A modified version of Random Bit Climbing (RBC) optimization method, also called λ-Modified Random Bit Climbing (λ-mRBC), is developed to get better and faster optimal or near-optimal solution. In the proposed λ- mRBC method, a new operator, called transposition operator, is added to improve the exploration of search space and hence to escape from the local optima. The deepth of exploration is controlled by using a single parameter (λ). Firstly, a number of sensor nodes is selected to cooperatively execute the application with the purpose of improving the network lifetime. After that, the proposed λ-mRBC method is performed to get the optimal or near-optimal task/sensor pair solution, so that the execution time and energy consumption are minimized. The simulation results show that λ-mRBC method enhances the TMS performance. Compared with the traditional RBC method, the proposed λ-mRBC method converges to better fitness value, make-span and total energy consumption by 19.1%, 19.6% and 22.3%, respectively. Furthermore, the network lifetime is prolonged through using the proposed selection algorithm. The distribution of remaining energy among sensor nodes is improved about three times, compared with the random selection scheme. Furthermore, compared with the random selection, the number of neighbours for sensor nodes is improved by 20.1% using the proposed selection algorithm.},
keywords={Application DAG,Optimization methods,Random bit climbing,Task mapping and scheduling,Wireless sensor networks.},
ISSN={2413-9351},
month={April}}