基于改进NSGA-Ⅱ的无线Ad-hoc网络任务调度算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (9): 61-63.

基于改进NSGA-Ⅱ的无线Ad-hoc网络任务调度算法

杨红丽,郭华

西安工业大学电子信息工程学院西安710032;西安邮电大学电子工程学院西安710010

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(60972047),陕西省教育厅科研项目(11JK0927),高等学校学科创新引智计划(B08038)资助

Task Scheduling Algorithm Based on Improved NSGA-Ⅱ for Wireless Ad-hoc Networks

YANG Hong-li and GUO Hua

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对无线Ad-hoc节点的移动性和易失效性导致的任务完成效率降低的问题,提出了一种无线Ad-hoc网络任务调度的多目标优化算法(MOTA)。该算法在追求最短的任务完成时间的同时,还考虑到节点的失效概率和能耗。它避免将任务分配到失效率较高的节点上执行,从而有效地降低了节点的失效对任务执行的影响。仿真分析表明,该算法能够有效地平衡任务完成时间最小化、任务完成概率最大化及能耗最小化的目标。与传统任务调度算法相比,其仿真实验取得了更好的结果。

关键词: 无线Ad-hoc网络,任务调度,多目标优化,任务完成时间中图法分类号TP393文献标识码A

Abstract: To solve the problem of the lower efficiency of task-performing caused by the mobility and failure-prone of Ad-hoc nodes,a multi-object optimization task scheduling algorithm(MOTA)was proposed for wireless Ad-hoc networks．This algorithm tries its best to make less make span,but meanwhile,it also pays much more attention to the fai-lure probability and the energy-consuming of nodes．MOTA avoids the task assigned to the failure-prone node,which effectively reduces the effect of failed nodes on task-performing.Simulation results show that the proposed algorithm can trade off these three objectives well．Compared with the traditional task scheduling algorithms,the simulation experiments obtain better results．

Key words: Wireless Ad-hoc networks,Task scheduling,Multi-object optimization,Make span

杨红丽,郭华. 基于改进NSGA-Ⅱ的无线Ad-hoc网络任务调度算法[J]. 计算机科学, 2013, 40(9): 61-63. https://doi.org/

YANG Hong-li and GUO Hua. Task Scheduling Algorithm Based on Improved NSGA-Ⅱ for Wireless Ad-hoc Networks[J]. Computer Science, 2013, 40(9): 61-63. https://doi.org/

参考文献

[1] Hu Z,Tang X S,Wang X．A Distributed Algorithm for DAG-Form Service Composition Over MANET[C]∥International Conference on Wireless Communications,Networking and Mobile Computing．2007:1664-1667
[2] Xie T,Qin X．An Energy-Delay Tunable Task Allocation Strategy for Collaborative Applications in Networked Embedded Systems[J]．IEEE Transactions on Computers,2008,57(3):329-343
[3] Moges M,Ramirez L A,Gamboa C．Monetary Cost and Energy Use Optimization in Divisible Load Processing[C]∥Proceedings of the 2004Conference on Information Sciences and Systems.Princeton University,March 2004
[4] Kim J K,Siegel H J,Maciejewski A A．Dynamic Resource Mana-gement in Energy Constrained Heterogeneous Computing Systems Using Voltage Scaling[J]．IEEE Transactions on Parallel and Distributed Systems,2008,19(11):1445-1457
[5] Thakkar A,Pradhan S N．Power aware scheduling for AdhocSensor Network nodes[C]∥Proceedings of 3rd International Conference on Signal Processing and Communication Systems．2009:1-7
[6] Shivle S,Castain R,Siegel H J,et al．Static mapping of subtasks in a heterogeneous Ad Hoc grid environment[C]∥Proceedings of the 18thInternational Parallel and Distributed Processing Symposium.Santa Fe:IEEE Computer Society,2004:110-123
[7] Wang Z,Chen Q,Gao C S．Implementing grid computing over mobile Ad Hoc networks based on mobile agent[C]∥Procee-dings of the Fifth International Conference on Grid and Cooperative Computing Workshops．Washington:IEEE Computer Society,2006:321-326
[8] Lu X S,Hassanein H,Akl S．Energy aware dynamic task allocation in mobile ad hoc networks[C]∥Proceedings of the International Conference on Wireless Networks,Communications and Mobile Computing．2005:534-539
[9] Bokar A,Bozyigit M,Sener C．Scalable Energy-Aware Dynamic Task Allocation[C]∥ Proceedings of International Conference on Advanced Information Networking and Applications Workshops．2009:371-376
[10] Xu M．Research of Task Scheduling of Ad-hoc Cluster Computing Based on Genetic Algorithm[C]∥Proceedings of International Conference on Wireless Networks and Information Systems．2009:137-139
[11] Alsalih W,Akl S,Hassanein H．Energy-aware task allocationover MANETs[C]∥Proceedings of International Conference on Wireless and Mobile Computing,Networking and Communications．2005:315-322
[12] Iverson M A,Ozguner F,Potter L．Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment[J]．IEEE Transactions on Computers,1999,48(12):1374-1379
[13] Gong L,Sun X H,Waston E．Performance modeling and predic-tion of non-dedicated network computing[J]．IEEE Transactions on Computers,2005,51(9):1041-1055
[14] Kalyanmoy D,Amrit P,Sameer A．A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed