无线传感器网络中新的最小暴露路径问题及其求解算法

doi:10.11959/j.issn.1000-436x.2016007

通信学报 ›› 2016, Vol. 37 ›› Issue (1): 49-60.doi: 10.11959/j.issn.1000-436x.2016007

无线传感器网络中新的最小暴露路径问题及其求解算法

叶苗^1,^2,^3,⁴,王宇平¹,代才¹,王晓丽¹

¹ 西安电子科技大学计算机学院，陕西西安 710071
² 桂林理工大学信息科学与工程学院，广西桂林541004
³ 桂林电子科技大学广西云安全与云服务工程技术研究中心，广西桂林 541104
⁴ 陕西师范大学计算机科学学院，陕西西安 710062

出版日期:2016-01-25 发布日期:2016-01-27
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;广西自然科学基金资助项目;广西自动检测技术与仪器重点实验室基金资助项目;广西自动检测技术与仪器重点实验室基金资助项目;广西教育厅基金资助项目

New minimum exposure path problem and its solving algorithm in wireless sensor networks

Miao YE^1,^2,^3,⁴,ping WANGYu¹,Cai DAI¹,li WANGXiao¹

¹ School of Computer Science and Technology, Xidian U iversity, Xi'an 710071, China
² College of Information Science and Engineering, Guilin University of Technology, Guilin 541004, China
³ Guangxi Cloud Security and Cloud Services Engineering Technology Research Center, Guilin niversity of Electronic Technology, Guilin 541104, China
⁴ College of Computer Science, Shaanxi Normal University, Xi'an 710062, China

Online:2016-01-25 Published:2016-01-27
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Natural Science Foundation of Guangxi;The Key Laboratory of Automatic Detecting Technology a Instru-ments of Guangxi;The Key Laboratory of Automatic Detecting Technology a Instru-ments of Guangxi;The General Programs of the Scientific Research Project of Guangxi Educational Committee

摘要/Abstract

摘要：

无线传感器网络中原始的最小暴露路径问题没有考虑对路径的实际限制条件，提出一种要求经过某一特别保护区域部分边界的最小暴露路径问题。由于无法建立相应的图模型，原有求解最小暴露路径问题的经典方法（网格法和维诺图法）对提出的新问题不再起效。先将该问题转化成带约束条件的优化问题，然后针对转化后的数学模型高度非线性、高维度而不好用确定性优化方法的特点，结合问题实际背景设计出混合人工蜂群求解算法。通过在多种情况下的仿真实验发现，设计的带约束条件优化模型和混合人工蜂群求解算法能有效解决提出的最小暴露路径问题。

关键词: 无线传感器网络, 最小暴露路径, 保护区域, 混合人工蜂群算法

Abstract:

Due to the original minimum exposure path (MEP) problem in wireless sensor network without considering the constrained conditions for paths in practice, a new MEP problem with the request along a part of the boundary of the special protection area (BPA-MEP) was put forwand. As unable to set up the corresponding graph model, the classic methods (such as grid-based method and Voronoi-based method) in solving MEP problem would no longer work to BPA-MEP problem. To solve BPA-MEP problem, a optimization model with constraints as highly nonlinear and higher dimensional problem was tailored and established and then taking the characteristic of the distribution of the sensor nodes, a hybrid artificial bee algo-rithm was proposed to solve this complex optimization model. The results of the proposed model and the designed algorithm, when implemented in many aspects, show that they can s A-MEP problem effectively.

Key words: wireless sensor networks, minimum exposure path, protect area, hybrid artificial bee algorithm

叶苗,王宇平,代才,王晓丽. 无线传感器网络中新的最小暴露路径问题及其求解算法[J]. 通信学报, 2016, 37(1): 49-60.

Miao YE,ping WANGYu,Cai DAI,li WANGXiao. New minimum exposure path problem and its solving algorithm in wireless sensor networks[J]. Journal on Communications, 2016, 37(1): 49-60.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 29

[1]	MEGERIAN S , KOUSHANFAR F , POTKONJAK M . Worst and best-case coverage in sensor networks[J]. IEEE Trans on Mob le Computing, 2005,4(1): 84-92.
[2]	MEGUERDICHIAN S , KOUSHANFAR F , QU G . Exposure in wireless ad hoc sensor networks[C]// Proc of MobiCom 2001. Rome,Italy, c2001:139-150.
[3]	CLOUQUEUR T , PHIPATANASUPHORN V , RAMANATHAN P , et al. Sensor deployment strategy for detection of targets traversing a region[J]. Mobile Network, 2003,8(4): 453-461.
[4]	GELFAND I M , FOMIN S N . Calculus of Variationd[R]. Dove publisher, 2000,1-14.
[5]	AUBIN J P . Applide Functional Analysis(2nd)[R]. New York,John Wiley, 2000,31-41.
[6]	HRISTO N , DJIDJE V . Approximation algorithms for computing minimum exposure paths in a sensor field[J]. ACM Transactions on Sensor Networks, 2010,7(23): 1-23.
[7]	HRISTO N , DJIDJEV L . Efficient computation of minimum exposure paths in a sensor network field[C]// DCOSS 2007. Santa Fe, NM, USA, c2007:259-308.
[8]	LIU L , ZHANG X , MA H . Minimal exposure path algorithms for directional sensor networks[C]// DCOSS 2007. Global Telecommunications Conference, c2009:1-6.
[9]	MEGERIAN S , KOUSHANFAR F , QU G , et al. Exposure in wireless sensor networks: theory and practical solutions[J]. Wi less Network, 2002,8(5): 443-454.
[10]	VELTRI G , HUANG Q , QU G , et al. Minimal and maximal expos path algorithms for wireless embedded sensor networks[C]// ACM Int'l Conf on Embedded Networked Sensor Systems (SenSys)Akyildiz IF, Estion D, c2003:40-50.
[11]	LIU D , NING P , LIU A , et al. Attack-resistant location estimation in wireless sensor networks[J]. ACM Transactions on Infor tion and System Security, 2008,11(4): 1-39.
[12]	JINGFANG JIANG , GUANGJIE HAN , CHUNAN ZHU , et al. Secure localization in wireless sensor networks: a survey[J]. Journal on Communications, 2011,6(6): 460-470.
[13]	王福豹，史龙，任丰．无线传感器网络中的自身定位系统和算法[J]. 软件学报, 2005,16(5):857-858. WANG F B , SHI L , REN F . Self-Localization Systems and Algorithms for Wireless Sensor Network[J]. Journal of Software, 2005,16(5):857-858.
[14]	WANG X , MA J J , WANG S . Prediction based dynamic power optimization in wireless sensor networks[J]. Sensors, 2007,7(3): 251-266.
[15]	WANG LM , GUO YB , ZHAN YZ . Security topology control method for wireless sensor networks with node-failure tolerance based on self-regeneration[J]. Eurasip Journal of Wireless Communica ions and Networking, 2010,(1):1-11.
[16]	宋超，刘明，龚海刚 , 等．基于蚁群优化解决传感器网络中的能量洞问题[J]. 软件学报, 2009,20(10):2729-2743. SONG C , LIU M , GONG H G , et al. ACO-based algorithm for solving energy hole problems in wireless sensor networks[J]. Journal of Software, 2009,20(10):2729-2743.
[17]	李青剑，王永，陈绍青 , 等．一种方向优化最小均方算法[J]. 电子学报, 2014,36(6):1348-1354. LI Q J , WANG Y , CHEN S Q , et al. A direction optimization least mean square algorithm[J]. Journal of Electronics ＆ Information Technology, 2014,36(6):1348-1354.
[18]	李彦，王丽娜．基于时间序列的时空插值算法改进研究[J] 2014,41(6):414-418. LI Y , WANG L N . Research of spato-temporal interpolation algorithm based on time series[J]. Computer Science, 2014,41(6):414-418.
[19]	HONGWEI LIN , YUPING WANG , LEI FAN , et al. A new discrete filled funciton method for finding global minimizer of the integer pro-gramiming[J]. Applied Mathematics and Computation, 2012,219:4371-4378.
[20]	KARABOGA D . An Idea Based on Honey Bee Swarm for Numerical Optimization[R]. Erciyes Univ, Kayseri, Turkey, Tech Rep-TR06, 2005.
[21]	KARABOGA D , OZTURK C . Neural networks training by artificial bee colony algorithm on pattern classification[J]. Neural Network World, 2009,19(3):279-292.
[22]	KARABOGA D , OZTURK C . A novel clustering approach: Artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2011,11(1):652-657.
[23]	OZTURK C , KARABOGA D , GORKEMLI B . Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algo-rithm[J]. Sensors, 2011,11(6):6056-6065.
[24]	LEUNG Y W , WANG Y . An orthogonal genetic algorithm wit quantization for global numerical optimization[J]. IEEE Transaction on Evolutionary Computing, 2001,5(1):41-53.
[25]	WANG Y P , DANG C Y . An evolutionary algorithm for global optimization based on level-set evolution and latin squares[J]. Transaction on Evolutionary Computing, 2007,11(5):579-595.
[26]	SHANG Y W , QIU Y H . A note on the extended rosenbrock function[J]. Evolutionary Computing, 2006,14(1):119-126.
[27]	SINGIRESU S , RAO S . Engineering Optimization: Theory and Practice[M]. New Jersy,John Wiley ＆ Sons Inc, 2009.
[28]	WOODFOR C , PHILLIPS C . Numerical Methods with Worked Examples: Matlab Edition(Second Edtion)[M]. Springer Dordrecht Heidelberg, 2011.
[29]	WENYU S , YAXIANG Y . Optimization Theory and Methods:Nonlinear Programming[M]. New York: Springer Science Business Media, 2006.

无线传感器网络中新的最小暴露路径问题及其求解算法

New minimum exposure path problem and its solving algorithm in wireless sensor networks

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 29

相关文章 15

Metrics

推荐阅读 0

[1]	赵越, 李赞, 李冰, 郝本建. TDoA定位盲区分析与节点部署策略研究[J]. 通信学报, 2023, 44(1): 1-13.
[2]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.
[3]	杜秀娟, 王丽娟, 刘静萍, 金龙. 基于归零神经动力学的水下无线传感器网络节点测距定位方法[J]. 通信学报, 2022, 43(10): 177-185.
[4]	孙爱晶, 李世昌, 张艺才. 基于PSO优化模糊C均值的WSN分簇路由算法[J]. 通信学报, 2021, 42(3): 91-99.
[5]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[6]	郝晓辰,姚宁,解力霞,王姣姣,王立元. 联合功率与信道的WSN生命期优化博弈算法[J]. 通信学报, 2019, 40(4): 62-70.
[7]	刘琳岚,高声荣,舒坚. 基于随机森林的链路质量预测[J]. 通信学报, 2019, 40(4): 202-211.
[8]	武小年,张楚芸,张润莲,孙亚平. WSN中基于改进粒子群优化算法的分簇路由协议[J]. 通信学报, 2019, 40(12): 114-123.
[9]	刘浩然,赵赫瑶,邓玉静,王星淇,尹荣荣. 基于非合作博弈的无线传感器网络覆盖控制算法[J]. 通信学报, 2019, 40(1): 71-78.
[10]	乐燕芬,汤卓,盛存宝,施伟斌. 基于多分布密度位置指纹的高效室内定位算法研究[J]. 通信学报, 2019, 40(1): 172-179.
[11]	舒坚,刘满兰,尚亚青,陈宇斌,刘琳岚. 基于高斯过程回归的链路质量预测模型[J]. 通信学报, 2018, 39(7): 148-156.
[12]	郝晓辰,王立元,刘金硕,解力霞,张文焕. WSN中基于双群体差分进化的资源分配优化算法[J]. 通信学报, 2018, 39(4): 68-75.
[13]	蒋婵,李陶深,梁俊斌. 移动低占空比无线传感器网络中低时延的数据持续性提高算法[J]. 通信学报, 2018, 39(3): 53-62.
[14]	王继红,石文孝. 认知无线传感器网络分簇路由协议综述[J]. 通信学报, 2018, 39(11): 156-169.
[15]	张晓莹,彭辉,陈红. 无线传感器网络隐私保护数据聚集技术[J]. 通信学报, 2018, 39(10): 130-142.