Please wait a minute...
浙江大学学报(工学版)  2018, Vol. 52 Issue (8): 1431-1443    DOI: 10.3785/j.issn.1008-973X.2018.08.001
计算机技术     
基于弹性碰撞优化算法的传感云资源调度
刘洲洲1,2, 李士宁1, 李彬1, 王皓3, 张倩昀2, 郑然1
1. 西北工业大学 计算机学院, 陕西 西安 710072;
2. 西安航空学院 电子工程学院, 陕西 西安 710077;
3. 挪威科技大学奥勒松校区工程与科学学院 挪威 8730
New elastic collision optimization algorithm and its application in sensor cloud resource scheduling
LIU Zhou-zhou1,2, LI Shi-ning1, LI Bin1, WANG Hao3, ZHANG Qian-yun2, ZHENG Ran1
1. School of Computer Science, Northwestern Polytechnical University, Xi'an 710072, China;
2. School of Electronic Engineering, Xi'an Aeronautical University, Xi'an 710077, China;
3. Norwegian University of Science and Techchnology Aalesund, Norway 8730
 全文: PDF(1577 KB)   HTML
摘要:

针对当前智能优化算法普遍存在收敛精度不高、容易“早熟”的缺陷,提出全新的智能优化算法—弹性碰撞优化(ECO)算法.算法基于弹性碰撞物理学现象,通过模拟碰撞过程中物理属性相互影响的变化过程,抽象出“与种群最优碰撞”、“与自身历史最优碰撞”和“随机碰撞”3种粒子更新机制.为了有效提升复杂高维优化问题的寻优能力,设计自适应核模糊C-均值聚类(AKFCM)算法,利用AKFCM对ECO种群进行聚类分析,通过迭代比对策略实现种群自动最佳聚类划分,确保粒子学习对象的合理性与多样性.种群样本多样性定量分析表明ECO在运算后期具有较好的种群多样性.将ECO应用于传感云资源调度问题,为了满足传感云系统管理多样性需求,构建多目标优化传感云资源调度模型,设计符合调度问题的ECO粒子编码方式,实现传感云资源高效率调度优化.多维复杂测试函数以及传感云资源调度实例仿真结果表明,ECO具有较高的收敛精度和成功率,有效降低了传感云资源调度的能耗和任务长度.

Abstract:

Aiming at the low convergence accuracy and precocity of current intelligent optimization algorithms, a new intelligent optimization algorithm, elastic collision optimization (ECO) algorithm was proposed. Considering the elastic collision physics phenomenon, the changes of physical properties of objects during collision process were simulated, and three kinds of particle renewal mechanism were proposed, namely, collision with optimal individuals, collision with history optimal, and random collision. In order to effectively improve the optimization ability of complex and high dimensional optimization problems, an adaptive kernel fuzzy C-means (AKFCM) algorithm was designed and the ECO population was analyzed by AKFCM. By using the iterative comparison method, the automatic optimal clustering of the swarm was realized, and the rationality and diversity of the particle learning object were ensured. Quantitative analysis of population sample diversity showed that ECO still had good population diversity at the later stage. ECO was applied to the sensing cloud resource scheduling problem. The resource scheduling model of sensing cloud based on multi-objective optimization was constructed for the diversity management of sensing cloud systems, and the ECO particle coding was designed for the scheduling problem, which helped realize efficient scheduling and optimization of sensing cloud resources. The simulation results of multidimensional complex test function and sensor cloud resource scheduling show that ECO has higher convergence accuracy and success rate, and effectively reduces the energy consumption and task length of sensing cloud resource scheduling.

收稿日期: 2017-09-25 出版日期: 2018-08-23
CLC:  TP391  
基金资助:

国家自然科学基金资助项目(61871313,61601365);中国博士后科学基金资助项目(2018M633573);陕西省自然科学基础研究计划资助项目(2017JM6096);西安市科技计划资助项目(2017076CG/RC039(XAHK001));西安航空学院校级科研基金资助项目(2017KY1112)

作者简介: 刘洲洲(1981-),男,教授,主要从事传感器网络及智能优化算法研究.orcid.org/0000-0001-7532-9749.E-mail:nazi2005@126.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  

引用本文:

刘洲洲, 李士宁, 李彬, 王皓, 张倩昀, 郑然. 基于弹性碰撞优化算法的传感云资源调度[J]. 浙江大学学报(工学版), 2018, 52(8): 1431-1443.

LIU Zhou-zhou, LI Shi-ning, LI Bin, WANG Hao, ZHANG Qian-yun, ZHENG Ran. New elastic collision optimization algorithm and its application in sensor cloud resource scheduling. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1431-1443.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2018.08.001        http://www.zjujournals.com/eng/CN/Y2018/V52/I8/1431

[1] 李智勇, 陈少淼, 杨波, 等. 异构云环境多目标Memetic优化任务调度方法[J]. 计算机学报, 2016, 39(2):377-390 LI Zhi-yong, CHEN Shao-miao, YANG Bo, et al. Multi-objective Memetic algorithm for task scheduling on heterogeneous cloud[J]. Chinese Journal of Computers, 2016, 39(2):377-390
[2] 王晓辉, 吴禄慎, 陈华伟, 等. 应用改进的粒子群优化模糊聚类实现点云数据的区域分割[J]. 光学精密工程, 2017, 25(4):563-573 WANG Xiao-hui, WU Lu-shen, CHEN Hua-wei, et al. Region segmentation of point cloud data based on improved particle swarm optimization fuzzy clustering[J]. Optics and Precision Engineering, 2017, 25(4):563-573
[3] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]//Proceedings of the First European Conference on Artificial Life. France:Elsevier Publishing, 1991:134-142
[4] KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks. Perth:IEEE, 1995:1942-1948
[5] TAN Y, ZHU Y. Fireworks algorithm for optimization[C]//Proceedings of the 1st International Conference on Advances in Swarm Intelligence. Springer-Verlag, 2010:355-364
[6] 李淑英, 潘亚, 费薇, 等. 基于分组遗传算法的虚拟机放置方法[J]. 南京理工大学学报, 2016, 40(6):322-327 LI Shu-ying, PAN Ya, FEI Wei, et al. Virtual machine placement method based on grouping genetic algorithm[J]. Journal of Nanjing University of Science and Technology, 2016, 40(6):322-327
[7] LIANG J J, QIN A K, SUGANTHAN P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3):281-295.
[8] 田瑾. 高维多峰函数的量子行为粒子群优化算法改进研究[J]. 控制与决策, 2016, 31(11):1967-1972 TIAN Jin. Improvement of quantum-behaved particle swarm optimization algorithm for high-dimensional and multi-modal functions[J]. Control and Decision, 2016, 31(11):1967-1972
[9] 马卫, 孙正兴. 采用搜索趋化策略的布谷鸟全局优化算法[J]. 电子学报, 2015, 43(12):2429-2439 MA Wei, SUN Zheng-xing. A global cuckoo optimization algorithm using coarse-to-fine search[J]. Chinese Journal of Electronics Acta Electronica Sinica, 2015, 43(12):2429-2439
[10] 崔晓晖, 印桂生, 董红斌. 面向服务匹配问题的协同演化算法[J]. 软件学报, 2015, 26(7):1601-1614 CUI Xiao-hui, YIN Gui-sheng, DONG Hong-bin. Co-evolutionary algorithm for Web service matching[J]. Journal of Software, 2015, 26(7):1601-1614
[11] EBRAHIMI D, ASSI C. Network coding-aware compressive data gathering for energy-efficient wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2015, 11(4):1-24.
[12] 曾建电, 王田, 贾维嘉, 等. 传感云研究综述[J]. 计算机研究与发展, 2017, 54(5):925-939 ZENG Jian-dian, WANG Tian, JIA Wei-jia, et al. A survey on sensor-cloud[J]. Journal of Computer Research and Development, 2017, 54(5):925-939
[13] MADRIA S, KUMAR V, DALVI R. Sensor cloud:a cloud of virtual sensors[J]. IEEE Software, 2014, 31(2):70-77.
[14] TIAN F G, CHEN K K. Towards optimal resource provisioning for running mapreduce programs in public clouds[C]//Proceedings of IEEE International Conference on Cloud Computing, Washington:IEEE, 2011:155-162
[15] CHohan N, Castillo C, Spreitzer M, et al. See spot run:using spot instances for map-reduce workflows[C]//Proceeding of the 2nd Usenix Conference on Hot Topics in Cloud Computing. USENIX Association, 2011:7
[16] MA A L, ZHONG Y F, ZHANG L P. Adaptive multiplicative memetic fuzzy clustering algorithm for remote sensing imagery[J]. IEEE Transactions on Geoscience and Remote Sensing, 2015, 53(8):4202-4217.
[17] TAN K L. What's next?:sensor+cloud?[C]//Proceedings of the 7th ACM International Workshop on Data Management for Sensor Network. New York:ACM, 2010:1
[18] KUNCHEVA L. Clustering date[DB/OL].[2014-09–10]. http://pages.bangor.ac.uk/~mas00a/activities/artificial_data.html
[19] 陈海鹏, 申铉京, 龙建武, 等. 自动确定聚类个数的模糊聚类算法[J]. 电子学报, 2017, 45(3):687-694 CHEN Hai-peng, SHEN Xuan-jing, LONG Jian-wu, et al. Fuzzy clustering algorithm for automatic identification of clusters[J]. Acta Electronica Sinica, 2017, 45(3):687-694
[20] 林济铿, 刘露, 张闻博, 等. 基于随机模糊聚类的负荷建模与参数辨识[J]. 电力系统自动化, 2013, 37(14):50-57 LIN Ji-keng, LIU Lu, ZHANG Wen-bo, et al. Load modeling and parameter identification based on random fuzziness clustering[J]. Automation of Electric Power Systems, 2013, 37(14):50-57
[21] 朴尚哲, 超木日力格, 于剑. 模糊C均值算法的聚类有效性评价[J]. 模式识别与人工智能, 2015, 28(5):452-461 PIAO Shang-zhe, CHAOMURILIGE, YU Jian. Cluster validity indexes for FCM clustering algorithm[J]. Pattern Recognition and Artificial Intelligence, 2015, 28(5):452-461
[22] 魏蔚, 刘扬, 杨卫东. 一种通用云计算资源调度问题的快速近似算法[J]. 计算机研究与发展, 2016, 53(3):697-703 WEI Wei, LIU Yang, YANG Wei-dong. A fast approximation algorithm for the general resource placement problem in cloud computing platform[J]. Journal of Computer Research and Development, 2016, 53(3):697-703
[23] XU Y, LI K, HE L, et al. A DAG scheduling scheme on heterogeneous computing systems using double molecular structure based chemical reaction optimization[J]. Journal of Parallel and Distributed Computing, 2013, 73(9):1306-1322.
[24] CAO J, LI K, STOJMENOVIC I. Optimal power allocation and load distribution for multiple heterogeneous multicore server processors across clouds and data centers[J]. IEEE Transactions on Computers, 2014, 63(1):45-58.

[1] 韩勇, 宁连举, 郑小林, 林炜华, 孙中原. 基于社交信息和物品曝光度的矩阵分解推荐[J]. 浙江大学学报(工学版), 2019, 53(1): 89-98.
[2] 郑洲, 张学昌, 郑四鸣, 施岳定. 基于区域增长与统一化水平集的CT肝脏图像分割[J]. 浙江大学学报(工学版), 2018, 52(12): 2382-2396.
[3] 赵丽科, 郑顺义, 王晓南, 黄霞. 单目序列的刚体目标位姿测量[J]. 浙江大学学报(工学版), 2018, 52(12): 2372-2381.
[4] 何杰光, 彭志平, 崔得龙, 李启锐. 局部维度改进的教与学优化算法[J]. 浙江大学学报(工学版), 2018, 52(11): 2159-2170.
[5] 李志, 单洪, 马涛, 黄郡. 基于反向标签传播的移动终端用户群体发现[J]. 浙江大学学报(工学版), 2018, 52(11): 2171-2179.
[6] 王硕朋, 杨鹏, 孙昊. 听觉定位数据库构建过程优化[J]. 浙江大学学报(工学版), 2018, 52(10): 1973-1979.
[7] 魏小峰, 程承旗, 陈波, 王海岩. 基于独立边数的链码方法[J]. 浙江大学学报(工学版), 2018, 52(9): 1686-1693.
[8] 陈荣华, 王鹰汉, 卜佳俊, 于智, 高斐. 基于KNN算法与局部回归的网站无障碍采样评估[J]. 浙江大学学报(工学版), 2018, 52(9): 1702-1708.
[9] 张承志, 冯华君, 徐之海, 李奇, 陈跃庭. 图像噪声方差分段估计法[J]. 浙江大学学报(工学版), 2018, 52(9): 1804-1810.
[10] 王勇超, 祝凯林, 吴奇轩, 鲁东明. 基于局部渲染的高精度模型自适应展示技术[J]. 浙江大学学报(工学版), 2018, 52(8): 1461-1466.
[11] 孙念, 李玉强, 刘爱华, 刘春, 黎威威. 基于松散条件下协同学习的中文微博情感分析[J]. 浙江大学学报(工学版), 2018, 52(8): 1452-1460.
[12] 郑守国, 崔雁民, 王青, 杨飞, 程亮. 飞机装配现场数据采集平台设计[J]. 浙江大学学报(工学版), 2018, 52(8): 1526-1534.
[13] 毕晓君, 王朝. 基于超平面投影的高维多目标进化算法[J]. 浙江大学学报(工学版), 2018, 52(7): 1284-1293.
[14] 张廷蓉, 滕奇志, 李征骥, 卿粼波, 何小海. 岩心三维CT图像超分辨率重建[J]. 浙江大学学报(工学版), 2018, 52(7): 1294-1301.
[15] 于勇, 周阳, 曹鹏, 赵罡. 基于MBD模型的工序模型构建方法[J]. 浙江大学学报(工学版), 2018, 52(6): 1025-1034.