WSANs中基于蜂巢结构的移动容错恢复算法

杜景林; 郑若钦; 谢立

doi:10.7498/aps.64.018901

摘要

旨在研究无线传感器与执行器网络(WSANs)中节点失效情况下恢复执行器(actor)节点服务的算法. 首先说明了WSANs中的实时覆盖模型, 证明WSANs覆盖恢复问题是NP难问题, 给出了近似求解方案. 在此基础上, 提出了一种基于六边形蜂巢结构的移动容错算法HMFR用于恢复失效actor节点, HMFR 算法在限制网络初始部署的条件下拥有很好的性能. 通过实验与现有的恢复算法进行比较, 发现HMFR算法在actor覆盖sensor节点数和移动距离方面有更好的性能.

关键词:

Abstract

This paper aims at finding an algorithm in wireless sensor and actor networks (WSANs) to recover the failure actor. First, this paper describes the real-time coverage model in WSANs, proves WSAN's coverage recovery is NP-hard. A cell-based mobile fault-tolerant algorithm HMFR is presented to recover the failure actor, which has a good performance under a limited condition of initial deployment of network. Through simulation experiments, the results show that the algorithm is more effective than the present algorithms in terms of actor coverage and move distance.

Keywords:

wireless sensor and actor network (WSANs) /
deployment of nodes /
coverage recovery /
hexagonal cell

作者及机构信息

1.
南京信息工程大学电子与信息工程学院, 南京 210044;

2.
南京大学计算机科学与技术系, 南京 210023

基金项目: 国家自然科学基金面上项目(批准号: 61372128, 61471153)、江苏省科技支撑计划(工业)项目(批准号号: BE2011195)和江苏省高校自然科学基金重大项目(批准号: 14KJA510001)资助的课题.

Authors and contacts

1.
School of Electronic and Information Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, China;

2.
Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China

Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61372128, 61471153), the Science and Technology Support Program of Jiangsu Province, China (Grant No. BE2011195), and the Jiangsu Provincial Research Scheme of Nature Science for Higher Education Institute (Grant No. 14KJA510001).

参考文献

[1]	Akyildiz I F, Kasimoglu I H 2004 Ad Hoc Network Journal 2 351
[2]	Akkaya K, Janapala S 2008 Computer Networks 52 2779
[3]	Akyildiz I F, Su W, Sankarasubramaniam Y, Cayirci E 2002 Computer Networks 38 393
[4]	Petriu E M, Georganas N D, Petriu D C, Makrakis D, Groza V Z 2000 IEEE Instrumentation and Measurement Magazine 3 31
[5]	Gungor V C, Akan O B, Akyildiz I F 2008 IEEE/ACM Trans. on Networking 16 359.
[6]	Melodia T, Pompili D, Gungor V C, Akyildiz I F 2007 IEEE Trans. on Mobile Computing 6 1116
[7]	Liu H R, Yin W X, Han T, Dong M R 2014 Acta Phys. Sin. 63 040509 (in Chinese) [刘浩然, 尹文晓, 韩涛, 董明如2014物理学报 63 040509]
[8]	Liu B, Dong M R, Yin R R, Yin W X 2014 Chin. Phys. B 23 070510
[9]	Melodia T, Pompili D, Gungor V C, Akyildiz I F 2005 ACM Mobihoc, Urbana-Champaign, IL, May 2005 p99
[10]	Akkaya K, Younis M 2006 IEEE Vehicular Technology Conference (VTC), Montreal, CA, September 25-28, 2006 p25
[11]	Akkaya K, Younis M 2008 International Journal of Sensor Networks 3 152
[12]	Ban DS, Wen J, Jiang J, Dou WH 2011 Journal of Software 22 2089 (in Chinese) [班冬松, 温俊, 蒋杰, 窦文华 2011 软件学报 22 2089]
[13]	Che N, Li ZJ, Jiang SX 2011 Journal of Software 22 1361 (in Chinese) [车楠, 李治军, 姜守旭 2011 软件学报 22 1361]
[14]	Tuan CC, Wu YC 2014 Science China Information Sciences 57 1
[15]	Ranga V, Dave M, Kumar Verma A K 2013 Wireless Personal Communication 72 857
[16]	Kim H, Cobb J. A 2012 International Conference on Computing, Networking and Communications (ICNC) Jan 30-Feb 2 2012 p985
[17]	Erman A T 2011 Ph. D. Dissertation (University of Twente)
[18]	Cormen, T H, Leiserson, C E, Rivest R L, Stein, C (translated by Yin J P, Xu Y, Wang G, Liu X G, Su M, Zou H M, Wang H) 2013 Introduction to Algorithms Third Edition (China Machine Pres) pp640-641 (in Chinese) [科尔曼T H, C E, 李维斯特R L, 斯坦C 著(殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志译) 2013算法导论(机械工业出版社)第658–659页]

施引文献

[1]	Akyildiz I F, Kasimoglu I H 2004 Ad Hoc Network Journal 2 351
[2]	Akkaya K, Janapala S 2008 Computer Networks 52 2779
[3]	Akyildiz I F, Su W, Sankarasubramaniam Y, Cayirci E 2002 Computer Networks 38 393
[4]	Petriu E M, Georganas N D, Petriu D C, Makrakis D, Groza V Z 2000 IEEE Instrumentation and Measurement Magazine 3 31
[5]	Gungor V C, Akan O B, Akyildiz I F 2008 IEEE/ACM Trans. on Networking 16 359.
[6]	Melodia T, Pompili D, Gungor V C, Akyildiz I F 2007 IEEE Trans. on Mobile Computing 6 1116
[7]	Liu H R, Yin W X, Han T, Dong M R 2014 Acta Phys. Sin. 63 040509 (in Chinese) [刘浩然, 尹文晓, 韩涛, 董明如2014物理学报 63 040509]
[8]	Liu B, Dong M R, Yin R R, Yin W X 2014 Chin. Phys. B 23 070510
[9]	Melodia T, Pompili D, Gungor V C, Akyildiz I F 2005 ACM Mobihoc, Urbana-Champaign, IL, May 2005 p99
[10]	Akkaya K, Younis M 2006 IEEE Vehicular Technology Conference (VTC), Montreal, CA, September 25-28, 2006 p25
[11]	Akkaya K, Younis M 2008 International Journal of Sensor Networks 3 152
[12]	Ban DS, Wen J, Jiang J, Dou WH 2011 Journal of Software 22 2089 (in Chinese) [班冬松, 温俊, 蒋杰, 窦文华 2011 软件学报 22 2089]
[13]	Che N, Li ZJ, Jiang SX 2011 Journal of Software 22 1361 (in Chinese) [车楠, 李治军, 姜守旭 2011 软件学报 22 1361]
[14]	Tuan CC, Wu YC 2014 Science China Information Sciences 57 1
[15]	Ranga V, Dave M, Kumar Verma A K 2013 Wireless Personal Communication 72 857
[16]	Kim H, Cobb J. A 2012 International Conference on Computing, Networking and Communications (ICNC) Jan 30-Feb 2 2012 p985
[17]	Erman A T 2011 Ph. D. Dissertation (University of Twente)
[18]	Cormen, T H, Leiserson, C E, Rivest R L, Stein, C (translated by Yin J P, Xu Y, Wang G, Liu X G, Su M, Zou H M, Wang H) 2013 Introduction to Algorithms Third Edition (China Machine Pres) pp640-641 (in Chinese) [科尔曼T H, C E, 李维斯特R L, 斯坦C 著(殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志译) 2013算法导论(机械工业出版社)第658–659页]

[1]	许诗瑶, 吴祎玮, 周燕, 尹向阳, 甘梨, 李雅鹃, 刘铭彧, 宋宏甲, 王金斌, 钟向丽. 快速响应恢复的PI-SiO₂/NiI₂比色湿度传感器. 物理学报, 2022, 71(2): 020701. doi: 10.7498/aps.71.20211376
[2]	许诗瑶, 钟向丽, 吴祎玮. 快速响应恢复的 PI-SiO2/NiI2比色湿度传感器. 物理学报, 2021, (): . doi: 10.7498/aps.70.20211376
[3]	吴佳键, 龚凯, 王聪, 王磊. 相依网络上基于相连边的择优恢复算法. 物理学报, 2018, 67(8): 088901. doi: 10.7498/aps.67.20172526
[4]	蒋锐, 杨震. 基于质心迭代估计的无线传感器网络节点定位算法. 物理学报, 2016, 65(3): 030101. doi: 10.7498/aps.65.030101
[5]	杨雄, 黄德才, 张子柯. 推荐重要节点部署防御策略的优化模型. 物理学报, 2015, 64(5): 050502. doi: 10.7498/aps.64.050502
[6]	白占国, 刘富成, 董丽芳. 六边形格子态斑图的数值模拟. 物理学报, 2015, 64(21): 210505. doi: 10.7498/aps.64.210505
[7]	杨怀, 王春华, 郭小蓉. 基于正六边形多开口的新型双频带左手材料. 物理学报, 2014, 63(1): 014103. doi: 10.7498/aps.63.014103
[8]	宋佳, 罗清华, 彭喜元. 基于节点健康度的无线传感器网络冗余通路控制方法. 物理学报, 2014, 63(12): 128401. doi: 10.7498/aps.63.128401
[9]	方伟, 宋鑫宏. 基于Voronoi图盲区的无线传感器网络覆盖控制部署策略. 物理学报, 2014, 63(22): 220701. doi: 10.7498/aps.63.220701
[10]	王亚奇, 杨晓元. 一种无线传感器网络簇间拓扑演化模型及其免疫研究. 物理学报, 2012, 61(9): 090202. doi: 10.7498/aps.61.090202
[11]	佟晓筠, 左科, 王翥. 基于无线传感器网络的混合混沌新分组加密算法. 物理学报, 2012, 61(3): 030502. doi: 10.7498/aps.61.030502
[12]	王翥, 王祁, 魏德宝, 王玲. 无线传感器网络中继节点布居算法的研究. 物理学报, 2012, 61(12): 120505. doi: 10.7498/aps.61.120505
[13]	熊菲, 刘云, 司夏萌, 丁飞. 基于Web 2.0的边与节点同时增长网络模型. 物理学报, 2010, 59(10): 6889-6895. doi: 10.7498/aps.59.6889
[14]	张淳民, 孙明昭, 袁志林, 宋晓平. 基于三角谐振环的新型六边形谐振环金属线复合周期结构左手材料性质研究. 物理学报, 2009, 58(3): 1758-1764. doi: 10.7498/aps.58.1758
[15]	董丽芳, 谢伟霞, 赵海涛, 范伟丽, 贺亚峰, 肖红. 氩气/空气介质阻挡放电自组织超六边形斑图实验研究. 物理学报, 2009, 58(7): 4806-4811. doi: 10.7498/aps.58.4806
[16]	郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
[17]	董丽芳, 刘书华, 王红芳, 范伟丽, 高瑞玲, 郝雅娟. 介质阻挡放电中两种不同时空对称性的六边形发光斑图. 物理学报, 2007, 56(6): 3332-3336. doi: 10.7498/aps.56.3332
[18]	董丽芳, 李树锋, 刘峰, 刘富成, 刘书华, 范伟丽. 大气压氩气介质阻挡放电中的四边形斑图和六边形斑图. 物理学报, 2006, 55(1): 362-366. doi: 10.7498/aps.55.362
[19]	姚远, 赵晓鹏, 赵晶, 周欣. 非对称开口六边形谐振单环的微波透射特性. 物理学报, 2006, 55(12): 6435-6440. doi: 10.7498/aps.55.6435
[20]	贺亚峰, 董丽芳, 刘富成, 范伟丽. 介质阻挡放电中的局域态六边形结构. 物理学报, 2005, 54(9): 4236-4239. doi: 10.7498/aps.54.4236

计量

文章访问数: 4767
PDF下载量: 329
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板