无线传感器网络中带复杂联盟的自适应任务分配算法

doi:10.3969/j.issn.1000-436x.2014.03.001

Abstract

Abstract:

Considering the real-time requirement and some specific limitations (e.g.insufficient computing resource,energy constraint,etc) in task scheduling of wireless sensor networks,different priorities were assigned to tasks according to their deadline,and an adaptive task allocation algorithm with complicated coalition was designed through analyzing historical information.Moreover,a discrete particle swarm optimization algorithm was designed via employing binary matrix coding form.The proposed optimization algorithm generates coalitions in parallel and then performs subtask allocation algorithm based on load and energy balance.Finally,the experimental results show that the proposed algorithm strikes a good balance between local solution and global exploration,and achieves a satisfactory result within a short period of time.

Key words: wireless sensor network, task allocation, complicated coalition, particle swarm optimization

Wen-zhong GUO,Jin-shu SU,Cheng-yu CHEN,Guo-long CHEN. Self-adapted task allocation algorithm with complicated coalition in wireless sensor network[J]. Journal on Communications, 2014, 35(3): 1-10.

Figures/Tables 12

References 25

[1]	AKYILDIZ I F , SU W , SANKARASUBRAMANIAM Y , et al. Wireless sensor networks:a survey[J]. Computer Networks, 2002,38(4): 393-422.
[2]	朱敬华，高宏．无线传感器网络中能源高效的任务分配算法[J]．软件学报， 2007,18(5):1198-1207. ZHU J H , GAO H . An energy efficient algorithm for task allocation in wireless sensor networks[J]. Journal of Sofware, 2007,18(5):1198-1207.
[3]	YU Y , VIKTOR K P . Energy-balanced task allocation for collaborative processing in wireless sensor networks[J]. Mobile Networks and Applications, 2005,10(12): 115-131.
[4]	TIAN Y , BOANGOAT J , EKICI E , et al. Real-time task mapping and scheduling for collaborative in-network processing in DVS-enabled wireless sensor networks[A]. Proc of the 20th International Parallel and Distributed Processing Symposium[C]. Island,Greece, 2006.
[5]	TIAN Y , GU Y Y , EKICI E , et al. Dynamic critical-path task mapping and scheduling for collaborative in network processing in multi-hop wireless sensor networks[A]. Proc of the 2006 International Conference on Parallel Processing Workshops[C]. Columbus,Ohio,USA, 2006. 215-222.
[6]	李志刚，周兴社，李士宁等．传感器网络能源有效任务分配算法[J]. 计算机研究与发展， 2009,46(12):1994-2002. LI Z , 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.
[7]	易军，石为人，唐云建等．无线传感器/执行器网络任务动态调度策略[J]．电子学报， 2010,38(6):1239-1244. YI J , SHI W R , TANG Y J , et al. A dynamic task scheduling for wireless sensor and actuator networks[J]. Acta Electronica Sinica, 2010,38(6):1239-1244.
[8]	ZENG Z W , LIU A F , LI D , et al. A highly efficient DAG task scheduling algorithm for wireless sensor networks[A]. Proc of the 9th International Conference for Young Computer Scientists[C]. 2008. 570-575.
[9]	代亮，沈中，常义林等．无线传感器网络任务调度双层规划方法[J]. 兵工学报， 2010,31(12):1697-1701. DAI L , SHEN Z , CHANG Y L , et al. Bilevel programming method for task scheduling in wireless sensor networks[J]. Acta Armamentarii, 2010,31(12):1697-1701.
[10]	刘梅，李海昊，沈毅．无线传感器网络空中目标跟踪任务分配技术的研究[J]．宇航学报， 2007,28(4):960-965. LIU M , LI H H , SHEN Y . Research on task allocation technique for aerial target tracking based on wireless sensor network[J]. Journal of Astronautics, 2007,28(4):960-965.
[11]	陈剑霞，于海斌 [J]．一种面向无线传感器网络协同任务分配的动态联盟更新机制．传感技术学报， 2009,22(4):499-504. 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,22(4):499-504.
[12]	ABDELHAK S , GURRAM C S , GHOSH S , et al. Energy balancing task allocation on wireless sensor networks for extending the lifetime[A]. Proc of the 2010 IEEE International 53rd Midwest Symposium on Circuits and Systems[C]. Seattle,Washington, 2010. 781-784.
[13]	陈国龙，郭文忠，陈羽中．无线传感器网络任务分配动态联盟模型与算法研究[J]．通信学报， 2009,30(11):48-55. 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,30(11):48-55.
[14]	GUO W Z , XIONG N X , CHAO H C , et al. Design and analysis of self-adapted task scheduling strategies in wireless sensor networks[J]. Sensors, 2011,11(7): 6533-6554.
[15]	HEINZELMAN W B , CHANDRAKASN A P , BALAKRISHNAN H . An application specific protocol architecture for wireless micro-sensor networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4): 660-670.
[16]	张国富，蒋建国，夏娜等．基于离散粒子群算法求解复杂联盟生成问题[J]．电子学报， 2007,35(2):323-327. ZHANG G F , JIANG J G , XIA N , et al. Solutions of complicated coalition generation based on discrete particle swarm optimization[J]. Acta Electronica Sinica, 2007,35(2):323-327.
[17]	CHETTO H , CHETTO M . Some results of the earliest deadline scheduling algorithm[J]. IEEE Transaction on Software Engineering, 1989,15(10): 1261-1269.
[18]	ZHU Z X , ZHOU J R , ZHEN J , et al. DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm[J]. IEEE Transaction on Evolutionary Computation, 2011,15(5): 643-658.
[19]	CHEN G L , GUO W Z , CHEN Y Z . A PSO-based intelligent decision algorithm for VLSI floor planning[J]. Soft Computing, 2010,14(12): 1329-1337.
[20]	郭文忠，陈国龙等．求解VLSI电路划分问题的混合粒子群优化算法[J]．软件学报， 2011,22(5):833-842. GUO W Z , CHEN G L , et al. Hybrid particle swarm optimization algorithm for VLSI circuit partitioning[J]. Journal of Software, 2011,22(5):833-842.
[21]	KULKARNI R V , VENAYAGAMOORTHY G K . Particle swarm optimization in wireless sensor networks:a brief survey[J]. IEEE Transactions on Systems,Man,and Cybernetics-Part C:Applications and Reviews, 2011,41(2): 262-267.
[22]	GUO W Z , GAO H L , CHEN G L , et al. Particle swarm optimization for the degree constrained MST problem in WSN topology control[A]. Proc of the 2009 International Conference on Machine Learning and Cybernetics[C]. 2009. 1793-1798.
[23]	SHI Y , EBERHART R C . A modified particle swarm optimizer[A]. Proc of the 1998 IEEE International Conference on Evolutionary Computation[C]. Anchorage,Alaska, 1998. 69-73.
[24]	LESSER V , ORTIZ C L , TAMBE M . Distributed Sensor Networks:a Multiagent 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[A]. Proc of the 7th IEEE Heterogeneous Computing Workshop[C]. Orlando,USA, 1998. 79-87.

Metrics

Recommended 0

No Suggested Reading articles found!

算法	生命周期(回合)	平均剩余能量/mJ
ERATA	138	125
MCTSAA	81	695
RSAA	105	451

节点数	ERATA	MCTSAA	RSAA
40	2.124 848 3	2.125 593 2	2.125 626 5
60	3.084 508 9	3.085 579 8	3.086 271 7
80	4.018 024 1	4.020 068 3	4.020 182 0
100	5.055 170 8	5.057 741 9	5.058 476 3
120	5.835 801 8	5.837 945 6	5.838 509 3
140	6.852 815 3	6.856 079 7	6.856 322 2

任务数	ERATA	MCTSAA	RSAA
50	5.020 861 7	5.029 535 3	5.022 969 3
100	5.023 456 9	5.025 205 7	5.025 519 2
150	5.326 662 8	5.328 785 2	5.328 263 9
200	6.625 630 7	6.828 373 3	6.728 785 1
250	6.850 689 1	7.008 411 7	6.956 149 9
300	6.925 392 8	7.029 262 2	6.969 912 3

Self-adapted task allocation algorithm with complicated coalition in wireless sensor network

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 12

References 25

Related Articles 15

Metrics

Recommended 0

[1]	Yue ZHAO, Zan LI, Bing LI, Benjian HAO. TDoA localization-refused area analysis and node placement strategy research [J]. Journal on Communications, 2023, 44(1): 1-13.
[2]	Cuiran LI, Xuejie WANG, Jianli XIE, Anqi LYU. Routing algorithm for railway monitoring linear WSN based on improved PSO [J]. Journal on Communications, 2022, 43(5): 155-165.
[3]	Yang CAO, Ye ZHONG, Chunling PENG, Xiaofeng PENG. Energy efficiency optimization algorithm of heterogeneous networks based on hybrid energy supply and energy cooperation [J]. Journal on Communications, 2022, 43(3): 135-147.
[4]	Xiujuan DU, Lijuan WANG, Jingping LIU, Long JIN. Ranging localization method for nodes in underwater wireless sensor network based on zeroing neural dynamics [J]. Journal on Communications, 2022, 43(10): 177-185.
[5]	Xin SU, Haoyang XUE, Yiqing ZHOU, Jinxiu ZHU. Research on computing offloading method for maritime observation monitoring sensor network [J]. Journal on Communications, 2021, 42(5): 149-163.
[6]	Aijing SUN, Shichang LI, Yicai ZHANG. WSN clustering routing algorithm based on PSO optimized fuzzy C-means [J]. Journal on Communications, 2021, 42(3): 91-99.
[7]	Jiazheng PEI,Yong HUANG,Yunlong DONG,Xiaolong CHEN. Improved SMC cardinality-balanced multi-Bernoulli forwardbackward smoothing track-before-detect algorithm [J]. Journal on Communications, 2019, 40(8): 102-113.
[8]	Cuiqin DAI,Huang TANG,Linfeng GUO. Contact plan design based on bi-directional particle swarm optimization in satellite network [J]. Journal on Communications, 2019, 40(8): 189-199.
[9]	Gang LI,Zhijun WU. Task scheduling algorithm for system-wide information management based on multiple QoS constraints [J]. Journal on Communications, 2019, 40(7): 27-37.
[10]	Tianjing WANG,Xiuqin LI,Guangwei BAI,Hang SHEN. Multi-target localization algorithm based on adaptive grid in wireless sensor network [J]. Journal on Communications, 2019, 40(7): 197-207.
[11]	Xiaochen HAO,Ning YAO,Lixia XIE,Jiaojiao WANG,Liyuan WANG. Research on WSN lifetime optimization game algorithm combined power and channel [J]. Journal on Communications, 2019, 40(4): 62-70.
[12]	Linlan LIU,Shengrong GAO,Jian SHU. Link quality prediction based on random forest [J]. Journal on Communications, 2019, 40(4): 202-211.
[13]	Xiaonian WU,Chuyun ZHANG,Runlian ZHANG,Yaping SUN. Clustering routing protocol based on improved PSO algorithm in WSN [J]. Journal on Communications, 2019, 40(12): 114-123.
[14]	Haoran LIU,Heyao ZHAO,Yujing DENG,Xingqi WANG,Rongrong YIN. Coverage control algorithm for wireless sensor networks based on non-cooperative game [J]. Journal on Communications, 2019, 40(1): 71-78.
[15]	Yuanhua FU,Zhiming HE. Distance criterion-based quantizer design for cooperative spectrum sensing [J]. Journal on Communications, 2018, 39(9): 49-56.