基于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]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[2]	沈涵, 王中生, 周舟, 王长元. 基于多应用场景的改进DV-Hop定位模型[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1219-1227.
[3]	张佩瑶, 付晓东. 防恶意竞价的众包多任务分配激励机制[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 261-268.
[4]	李大海, 詹美欣, 王振东. 基于多个改进策略的增强麻雀搜索算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2845-2854.
[5]	单飞桥, 王照伟, 沈跃. 基于精确时间协议的工业无线传感器网络时间同步方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2255-2260.
[6]	孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1551-1556.
[7]	邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3833-3839.
[8]	刘拥民, 杨钰津, 罗皓懿, 黄浩, 谢铁强. 基于双向循环生成对抗网络的无线传感网入侵检测方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 160-168.
[9]	田洪亮, 王佳玥, 李晨曦. 基于混合算法区块链和节点身份认证的数据存储方案[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2481-2486.
[10]	彭鹏, 倪志伟, 朱旭辉. 基于用户满意效用的空间众包任务分配方法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3235-3243.
[11]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2232-2241.
[12]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[13]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[14]	孙环, 陈宏滨. 基于萤火虫算法的无线传感器网络节点重部署策略[J]. 计算机应用, 2021, 41(2): 492-497.
[15]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.