微信服务号

微信订阅号

2025年3月24日 18:12 星期一
首页 > 过刊浏览>2007年第18卷第5期 >1198-1207
PDF HTML阅读 XML下载 导出引用 引用提醒
无线传感器网络中能源高效的任务分配算法
作者:
基金项目:

Supported by the Key Program of the National Natural Science Foundation of China under Grant No.60533110 (国家自然科学基金重点项目); the National Natural Science Foundation of China under Grant No.60473075 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0333 (新世纪优秀人才支持计划); the Key Program of the Natural Science Foundation of Heilongjiang Province of China under Grant No.ZJG03-05 (黑龙江省自然科学基金重点项目); the Heilongjiang Province Scientific and Technological Special Fund for Young Scholars of China under Grant No.QC06C033 (黑龙江省青年科技专项资金)


An Energy Efficient Algorithm for Task Allocation in Wireless Sensor Networks
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [17]
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    任务分配是高性能计算领域中的一个广泛研究的经典问题,然而,传感器网络资源严重受限,现有的算法不能直接应用.提出一种基于遗传算法的嵌套优化技术,在多跳聚簇网络中进行能源高效的任务分配.一般化的优化目标既可以满足应用的实时性要求,也可以实现能源的高效性.优化解通过结合基于遗传算法的任务映射、路由路径分配、任务调度以及动态电压调制(dynamic voltage scaling,简称DVS)这几个过程而获得.随机产生任务图模拟实验,结果表明,嵌套优化技术与随机优化技术相比,具有较好的实时性和能源高效性.

    Abstract:

    Task allocation is a typical problem in the area of high performance computing and has been extensively studied in the past. However, existing algorithms cannot be directly used in WSN (wireless sensor network) due to severe energy constraint. A nested optimization technique based on genetic algorithm is proposed for energy-efficient task allocation in multi-hop clusters. The general optimization object can meet application’s real-time requirement while realizing energy efficiency. Optimal solution can be achieved by incorporating GA-based task mapping, GA-based routing, communication scheduling and dynamic voltage scaling (DVS). Performance is evaluated through simulations with randomly generated task graphs and simulation results show better solution in terms of real-time and energy-efficiency compared with random optimization techniques.

    参考文献
    [1]Akyidiz IF,Su W,Sankarasubramaniam Y,Cayirci E.Wireless sensor networks:A survey.Elsevier Computer Networks Journal,2002,38(4):393-422.
    [2]Vercauteren T,Guo D,Wang X.Joint multiple target tracking and classification in collaborative sensor networks.IEEE Journal on Selected Areas in Communication,2005,23(4):714-723.
    [3]Dogan A,(O)zgüner F.Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing.IEEE Trans.on Parallel and Distributed Systems,2002,13(3):308-323.
    [4]Hu JC,Marculescu R.Energy-Aware communication and task scheduling for network-on-chip architectures under real-time constraints.In:Figueras J,ed.Proc.of the Design,Automation and Test in Europe Conf.Paris:IEEE Computer Society,2004.234-239.
    [5]Corrêa RC,Ferreira A,Rebreyend P.Scheduling multiprocessor tasks with genetic algorithms.IEEE Trans.on Parallel and Distributed Systems,1999,10(8):825-837.
    [6]Radulescu A,van Gemund AJC.Fast and effective task scheduling in heterogeneous systems.In:Proc.of the Heterogeneous Computing Workshop HCW.Cancun:IEEE Computer Society,2000.229-238.
    [7]Zhang Y,Hu X,Chen DZ.Task scheduling and voltage selection for energy minimization.In:Proc.of the 39th Design Automation Conf.New Orleans:ACM Press,2002.183-188.
    [8]Zhu D,Melhem R,Childers B.Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor real-time systems.In:Son S,ed.Proc.of IEEE the 22nd Real-Time System Symp.London:IEEE Computer Society,2001.84-94.
    [9]Giannecchini S,Caccamo M,Shih CS.Collaborative resource allocation in wireless sensor networks.In:Fohler G,ed.Proc.of the Euro Micro Conf.on Real-Time Systems (ECRTS 2004).Catania:IEEE Computer Society Press,2004.35-44.
    [10]Basu P,Ke W,Little TDC.Dynamic task-based anycasting in mobile ad hoc networks.Mobile Networks and Applications,2003,8(5):593-612.
    [11]Kumar R,Wolenetz M,Agarwalla B,Shin J,Hutto P,Paul A,Ramachandran U.DFuse:A framework for distributed data fusion.In:Akyildiz IF,Estrin D,Culler DE,Srivastava MB,eds.Proc.of the ACM Conf.on Embedded Networked Sensor Systems (SenSys 2003).Los Angeles:ACM Press,2003.114-125.
    [12]Shivle S,Castain R,Siegel HJ,Maciejewski AA,Banka T,Chindam K,Dussinger S,Pichumani P,Satyasekaan P,Saylor W,Sendek D,Sousa J,Sridharan J,Sugavanam P,Velazco J.Static mapping of subtasks in a heterogeneous ad hoc grid environment.In:Proc.of the Parallel and Distributed Processing Symp.Santa Fe:IEEE Computer Society,2004.
    [13]Yu Y,Prasanna VK.Energy-Balanced task allocation for collaborative processing in wireless sensor networks.Mobile Networks and Applications,2005,10(1-2):115-131.
    [14]Tian Y,Ekici E,(O)zgüner F.Energy-Constrained task mapping and scheduling in wireless sensor networks.In:Proc.of the Mobile Ad Hoc and Sensor Systems Conf.2005.8(16
    [15]Hou ESH,Ansari N,Ren H.A genetic algorithm for multiprocessor scheduling.IEEE Trans.on Parallel and Distributed Systems,1994,5(2):113-120.
    [16]Adam TL,Chandy KM,Dickson JR.A comparison of list schedules for parallel processing systems.Communications of the ACM,1974,17(12):685-689.
    [17]Schmitz MT,Al-Hashimi BM.Considering power variations of DVS processing elements for energy minimisation in distributed systems.In:Proc.of the Int'l Symp.on System Synthesis.Montréal:IEEE Computer Society,2001.250-255.
    相似文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

朱敬华,高宏.无线传感器网络中能源高效的任务分配算法.软件学报,2007,18(5):1198-1207

复制
分享
文章指标
  • 点击次数:7079
  • 下载次数: 7793
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2006-12-31
  • 最后修改日期:2007-02-14
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19728477位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号