一种带混合联盟的无线传感器网络任务分配策略

doi:10.11896/j.issn.1002-137X.2017.03.021

摘要/Abstract

摘要： 针对现有无线传感器网络任务分配策略通常不考虑任务内部结构,从而会影响网络生命周期、能耗及负载平衡等问题,基于逻辑依赖性提出一种新的无线传感器网络任务分配策略。该策略首先由选出的盟主根据任务本身具有的逻辑依赖性,逐层将任务分解为一系列的子任务,并依据逻辑依赖性赋予子任务优先级,最后运用矩阵的二进制编码设计一种基于位置加权的离散粒子群优化的带混合联盟的无线传感器网络任务分配算法,找到某个合适节点执行此子任务。引入虚拟节点以加强盟主间的交流；引入能量阈值对节点能量进行预测并决定子任务是否迁移；运用拓扑和逆拓扑排序法,根据子任务预期完成时间及权重系数求出关键子任务,选择优先分配能力强、执行效率高的节点执行相应子任务。仿真结果表明,该任务分配策略能有效延长网络生命周期、均衡网络负载和减少网络能耗等。

关键词: 无线传感器网络,任务分配,逻辑依赖,混合联盟,离散粒子群优化

Abstract: As most of the existing task allocation strategies for wireless sensor networks seldom considered the internal structure of tasks,which may largely affect the network lifetime,energy consumption and load balance,etc.The paper proposed a novel wireless sensor network (WSN) task allocation strategy based the logical dependencies.First,the task was decomposed step by step which was made of sub-tasks by the elected leaders according to the logical dependency,and at the same time gave sub-tasks priority based on the logical dependence.Last using the matrix a binary coding,the paper proposed a wireless sensor network (WSN) task allocation strategy about the discrete particle swarm optimization algorithm based on the weighted location with mixed coalition until they found a suitable node to perform the sub-task.To enhance the communication between the elected leaders,some virtual nodes were introduced.To estimate the residual node energy,the estimated energy value was introduced to decide whether the sub-task is migration or not.What’s more,according to the expected completion time and weight coefficient of sub-tasks,the paper sorted out the key sub-task by using topological sort and inverse topological,and also the key sub-task was assigned by strong ability,high execution nodes to complete.Finally,the experimental results showed that the novel task allocation strategy could effectively prolong the network lifetime,a steady balance of network load and reduce the energy consumption,etc.

Key words: Wireless sensor networks,Task allocation,Logical dependency,Mixed coalition,Discrete particle swarm optimization

曹义亲,陈宁霞,黄晓生. 一种带混合联盟的无线传感器网络任务分配策略[J]. 计算机科学, 2017, 44(3): 89-96. https://doi.org/10.11896/j.issn.1002-137X.2017.03.021

CAO Yi-qin, CHEN Ning-xia and HUANG Xiao-sheng. Task Allocation Strategy for Wireless Sensor Networks with Mixed Coalition[J]. Computer Science, 2017, 44(3): 89-96. https://doi.org/10.11896/j.issn.1002-137X.2017.03.021

参考文献

[1] AKYILDIZ I F,SUW,SANKARASUB R G LY,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(4):393-422.
[2] DAVDIC DEBORAH E,MANI S.Overview of sensor network[J].IEEE Computer,2004,7(8):41-49.
[3] SHANG H X.Research on Several Key Technologies of Wireless Sensor Networks[D].Nanjing:Nanjing University of Scien-ce & Technology January,2013.(in Chinese) 尚兴宏.无线传感器网络若干关键技术的研究[D].南京:南京理工大学,2013.
[4] GU H J.Research on Task Allocation and Switch for Dynamic Coalition in WSN[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2014.(in Chinese) 顾汉杰.基于动态联盟的WSN任务分配与切换研究[D].南京:南京航空航天大学,2014.
[5] ARMSTRONG R,HENSLEY D,KIDD T.The relative perfor-mance of various mapping algorithms is independent of sizable variances in runtime predictions[C]∥Proc of the 7th IEEE He-terogeneous Computing Workshop.Orlando,USA,1998:79-87.
[6] FREUND I L,GHERRITY M,AMBROSIAS S,et al.Scheduling resources in multi-user,heterogeneous,computing environments with smarmet [C]∥ Proc of the 7th IEEE Heteroge-neous Computing Workshop.Or-lando,USA,1998:184-199.
[7] LIU T,ZENG G X,WU C J.Autonomic computing approach for task distribution in heterogeneous computational grid[J].Journal of Communication,2006,27(11):139-143.(in Chinese) 刘涛,曾国荪,吴长俊.异构网格环境下任务分配的自主计算方法[J].通信学报,2006,27(11):139-143.
[8] BRAUN T,SIEGEL H,BECK N,et al.A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop.San Juan,Puerto Rico,1999:15-29.
[9] BRAUN T T,SIEGEL H,BECK N,et al.A Comparison Study of Static Mapping Heuristics for A Class of Meta-Tasks on He-terogeneous Computing Systems[C]∥Proceedings of the 8th IEEE Heterogeneous Computing Workshop.Washington,DC,USA:IEEE Press,1999:15-29.
[10] LI Z G,ZHOU X S,LI S N,et al.An Energy-Efficient Task Assignment Algorithm of Wireless Sensor Network[J].Journal of Computer Research and Development,2009,46(12):1994-2002.(in Chinese) 李志刚,周兴社,李士宁,等.传感器网络能源有效任务分配算法[J].计算机研究与发展,2009,46(12):1994-2002.
[11] YE J,CHEN G L,WU Y B,et al.Genetic algorithm for task allocation in Wireless Sensor Network[J].Computer Engineering and Applications,2010,6(35):119-122,128.(in Chinese) 叶菁,陈国龙,吴运兵,等.无线传感器网络任务分配的遗传优化算法[J].计算机工程与应用,2010,6(35):119-122,128.
[12] CHEN G L,GUO W Z,CHEN Y Z.Research on dynamic alliance of task allocation and its algorithm in wireless sensor network[J].Journal on Communications,2009,0(11):48-55.(in Chinese) 陈国龙,郭文忠,陈羽中.无线传感器网络任务分配动态联盟模型与算法研究[J].通信学报,2009,0(11):48-55.
[13] GUO W Z,SU J S,CHEN C T,et al.Self-adapted task allocation algorithm with complicated coalition in wireless sensor network[J].Journal on Communications,2014,5(3):1-10.(in Chinese)郭文忠,苏金树,陈澄宇,等.无线传感器网络中带复杂联盟的自适应任务分配算法[J].通信学报,2014,5(3):1-10.
[14] HEINZELMAN W B,CHANDRAKASN A P,BALAKRISH-NANH.An application specific protocol architecture for wireless micro-sensor networks [J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.
[15] CHEN J X,YU H B.An Updating Scheme of the Working Dynamic Coalition for Collaborative Task Allocation in Wireless Sensor Networks[J].Chinese Journal of Sensors and Actuators,2009(4):499-504.(in Chinese) 陈剑霞,于海斌.一种面向无线传感器网络协同任务分配的动态联盟更新机制[J].传感技术学报,2009(4):499-504.
[16] ZHANG J.Study of Agent Role Model and Construction Methodof Multi-agent System[D].Qingdao:Shangdong University,2012.(in Chinese) 张健.Agent角色模型与多agent系统构造方法研究[D].青岛:山东大学,2012.
[17] CHEN Y.Research on Adaptive Task Allocation Algorithm in Wireless Sensor Network[D].Fuzhou:Fuzhou University,2011.(in Chinese) 陈颖.无线传感器网络自适应任务分配算法的研究[D].福州:福州大学,2011.
[18] GENESERETH M R,KETCHET S P.Software Agents [J].Communication of the ACM,1993,37(7):48-53
[19] ZHENG B,LOU X Y,CUI B T.Energy Optimization Based on Position Weight PSO in WSNs[J].Journal of Jiang Nan University(Natural Science Edition),2014,3(5):568-571.(in Chinese) 郑波,楼旭阳,崔宝同.基于位置加权粒子群算法的WSNs能量优化[J].江南大学学报(自然科学版),2014,3(5):568-571.
[20] KENNY J,EBERHART R C.A Discrete Binary Version of the Particle Swarm Algorithm[C]∥Proc of the IEEE International Conference on Systems,Man and Cybernetics.Orlando,US,1997:4104-4108.
[21] ZHU T,LI X F,LU M W.Improved particle swarm optimization algorithm with position weighted[J].Computer Engineering and Applications,2011,7(5):4-6.(in Chinese) 朱童,李小凡,鲁明文.位置加权的改进粒子群算法[J].计算机工程与应用,2011,47(5):4-6.
[22] SHI Y,EBERHART R C.A modified particle swarm optimizer[C]∥Proc of the 1998 IEEE International Conference on Evolutionary Computation.Anchorage,Alaska,1998:69-73.
[23] HOU J B,FAN X G,WANG W L,et al.Cluttering strategy of wireless sensor networks based on improved discrete particle swarm optimization[C]∥Sixth International Conference on Natural Computation.Yantis,China:IEEE,2010:3866-3870.
[24] LESSER V,ORTIZ C L,TAMBE M.Distributed Sensor Networks:a Multi-agent Perspective [M].Kluwer Academic Publishers,2003.
[25] ARMSTRONG R,HENSGEN D,KIDD T.The relative performance of various mapping algorithms is independent of sizable variances in run time predictions [C]∥Proc of the 7th IEEE Heterogeneous Computing Workshop.Orlando,USA,1998:79-87.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed