基于0-1规划的异构传感器网络任务分配策略

计算机应用 ›› 2012, Vol. 32 ›› Issue (04): 913-916.

基于0-1规划的异构传感器网络任务分配策略

蒋志强¹,廖晓峰²,刘群¹

1. 重庆邮电大学计算机科学与技术学院,重庆 400065
2. 重庆大学计算机学院,重庆 401331

收稿日期:2011-09-21 修回日期:2011-12-02 发布日期:2012-04-20 出版日期:2012-04-01
通讯作者: 蒋志强
作者简介:蒋志强(1984-)，男，江西景德镇人，硕士研究生，主要研究方向：无线传感器网络资源优化；廖晓峰（1964-），男，四川成都人，教授，博士生导师，博士，主要研究方向：人工神经网络、混沌控制与同步；刘群（1969-），女，江西南昌人，教授，博士，主要研究方向：计算机仿真、多媒体信息处理、人工智能。
基金资助:
国家自然科学基金资助项目;重庆市自然科学基金资助项目;博士启动资金资助项目

Task allocation strategy in heterogeneous wireless sensor networks based on 0-1 programming

JIANG Zhi-qiang¹,LIAO Xiao-feng²,LIU Qun¹

1. College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
2. College of Computer Science, Chongqing University, Chongqing 401331, China

Received:2011-09-21 Revised:2011-12-02 Online:2012-04-20 Published:2012-04-01
Contact: JIANG Zhi-qiang

摘要/Abstract

摘要： 为了减少无线传感器网络节点处理任务的总体能耗、均衡网络节点的剩余能量以及减少网络中任务的调度时间，提出一种三目标任务分配算法。利用0-1非线性规划理论建立问题的代价函数，用能量方差表征节点处理任务后的剩余能量均衡度，并结合离散粒子群优化算法(DPSO)，以最小化代价函数为优化目的，从而得出经优化的任务分配策略。仿真实验表明基于0-1规划的任务分配策略能有效地减少网络总体能耗,均衡网络节点剩余能量(延长网络寿命)以及减少任务调度时间。

关键词: 无线传感器网络, 0-1规划, 任务分配, 任务图, 离散粒子群算法

Abstract: In order to reduce total energy consumption for processing task in Wireless Sensor Network (WSN), balance the residual energy of nodes and decrease the time of task scheduling, a task allocation algorithm for three targets was proposed. Cost function was built with the theory of 0-1 nonlinear programming and energy variance was utilized to show equilibrium degree of residual energy of nodes. Discrete Particle Swarm Optimization (DPSO) was used to solve cost function to obtain minimum and get optimized task allocation strategy. The simulation results verify that the task allocation strategy based on 0-1 programming with DPSO could decrease the energy consumption efficiently, balance the residual energy of nodes and reduce the time of task scheduling.

Key words: Wireless Sensor Network (WSN), 0-1 programming, task allocation, task graph, Discrete Particle Swarm Optimization (DPSO) algorithm

蒋志强廖晓峰刘群. 基于0-1规划的异构传感器网络任务分配策略[J]. 计算机应用, 2012, 32(04): 913-916.

JIANG Zhi-qiang LIAO Xiao-feng LIU Qun. Task allocation strategy in heterogeneous wireless sensor networks based on 0-1 programming[J]. Journal of Computer Applications, 2012, 32(04): 913-916.

参考文献

［1］崔莉，鞠海玲，苗勇，等.无线传感器网络研究进展［J］.计算机研究与发展，2005，42(1)：163-174. ［2］ YU Y, PRASANNA V. Energy-balanced task allocation for collaborative processing in wireless sensor network［J］. Journal of Mobile Networks and Applications,2005,10(1):115-131. ［3］ TIAN Y, EKICI E, OZGTINER F. Energy-constrained task mapping and scheduling in wireless sensor networks［C］// Proceedings of IEEE International Conference on Mobile Ad Hoc and Sensor Systems Conference. New York: IEEE,2005:8-16. ［4］ GIANNECCHINI S, CACCAMO M, SHIH C S. Collaborative resource allocation in wireless sensor networks［C］// ECRTS04: Proceedings of the 16th Euromicro Conference on Real-Time Systems. Washington, DC: IEEE Computer Society,2004:35-44. ［5］朱敬华，高宏.无线传感器网络中能源高效任务分配算法［J］.软件学报，2007,18(5)：1198-1207. ［6］李志刚，周兴社，李士宁，等.传感器网络能源有效任务分配算法［J］.计算机研究与发展，2009，46(12)：1994-2002. ［7］王雪,王晟,马俊杰.无线传感器网络任务分配的能效性控制策略［J］.控制理论与应用，2007，24(3)：490-493. ［8］陈国龙,郭文忠,陈羽中.无线传感器网络任务分配动态联盟模型与算法研究［J］.通信学报，2009，30(11)：48-55. ［9］卢开澄，卢华明.线性规划［M］.2版.北京:清华大学出版社，2008:245-267. ［10］刘美，徐小玲，黄道平. 应用粒子群优化分配WSN多目标跟踪节点任务［J］.传感技术学报，2010，23(9)：1334-1340. ［11］ PARK H, SRIVASTAVA M. Energy-efficient task assignment framework for wireless sensor networks, TR-UCLA-NESL 200309-03［R］. Los Angeles:Center for Embedded Network Sensing,2003. ［12］钟一文，蔡荣英.求解二次分配问题的离散粒子群优化算法［J］.自动化学报，2007，33(8)：871-874.

[1]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[2]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[3]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[4]	孙环, 陈宏滨. 基于萤火虫算法的无线传感器网络节点重部署策略[J]. 计算机应用, 2021, 41(2): 492-497.
[5]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[6]	胡润彦, 李翠然. 基于模糊控制的自供能无线传感器网络分簇算法[J]. 计算机应用, 2020, 40(9): 2691-2697.
[7]	韩雨涝, 房鼎益. 基于链路交点相对位置信息的轻量级覆盖空洞检测算法[J]. 计算机应用, 2020, 40(9): 2698-2705.
[8]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[9]	卢光跃, 周亮, 吕少卿, 施聪, 苏可可. 基于图信号处理的无线传感器网络异常节点检测算法[J]. 计算机应用, 2020, 40(3): 783-787.
[10]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[11]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[12]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[13]	吴三柱, 李鹏, 吴三斌. 移动无线传感器网络中抑制病毒传播模型[J]. 计算机应用, 2020, 40(1): 129-135.
[14]	任秀丽, 陈洋. 无线传感网中数据传输延时优化的路由协议[J]. 计算机应用, 2020, 40(1): 196-201.
[15]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.