无人值守传感器网络的高性能分布式存储算法

doi:10.3969/j.issn.1001-2400.2014.04.029

J4 ›› 2014, Vol. 41 ›› Issue (4): 173-178+185.doi: 10.3969/j.issn.1001-2400.2014.04.029

无人值守传感器网络的高性能分布式存储算法

肖宜龙^1,3;蒋海波^2,3

(1. 中煤平朔集团有限公司，山西朔州 036006；
2. 中国科学院成都生物研究所，四川成都 610041;
3. 中国科学院成都计算机应用研究所，四川成都 610041)

收稿日期:2013-04-29 出版日期:2014-08-20 发布日期:2014-09-25
通讯作者: 肖宜龙
作者简介:肖宜龙(1983-)，男，博士，E-mail: yilongxiao@foxmail.com．
基金资助:
国家高技术研究发展计划资助项目(2008AAO1Z402)；国家自然科学基金资助项目(61003034)

Distributed storage algorithm with high performance for the UWSN

XIAO Yilong^1,31,3;JIANG Haibo^2,3

(1. China Coal Pingshuo Group Ltd., Shuozhou 036006, China;
2. Chengdu Institute of Biology, Chinese Academy of Sciences, Chengdu 610041, China;
3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China)

Received:2013-04-29 Online:2014-08-20 Published:2014-09-25
Contact: XIAO Yilong

摘要/Abstract

摘要：

为解决无人值守传感器网络的数据存储可靠性问题，提出了一种具有低通信成本和低访问成本的分布式存储算法．算法采用步数为cn的并行定向随机游走机制，将网络中的k个源数据包按照一定的接收概率分散存储到网络中所有的n个节点，在每个节点形成一个存储数据包．理论分析和实验结果表明，基于该算法的存储过程完成之后，即使有部分传感器节点损坏，Sink节点只要随机收集到k+ε，ε大于等于11个存储数据包，就能成功地计算出原来的k个源数据包．与具有代表性的基于LT码的算法相比，文中算法将存储每个源数据包的通信次数从约3nlnn降至约3n；将读取源数据包的节点访问次数从大于k+100降至约k+11．

关键词: 传感器网络, 数据存储, 分布式算法, 随机游走

Abstract:

To solve the data storage reliability problem of the unattended wireless sensor network consisting of n sensor nodes, this paper proposes a new distributed storage algorithm based on parallel directional random walk with length cn. The proposed algorithm disseminates each of k source data packets in the network according to a given probability and formes a stored data packet in every node. Simulation results show that, after the storage process based on the proposed algorithm is completed, even if some stored data packets are missing, the data collector node can successfully recover the k source data packets from any survival k+ε, ε≥11 stored data packets. Compared with the LT codes based algorithm, the proposed algorithm reduces Sink node's query cost from k+100 to k+11 and reduces the network's communication cost from 3nlnn to 3n.

Key words: sensor network, data storage, distributed algorithm, random walk

肖宜龙;蒋海波. 无人值守传感器网络的高性能分布式存储算法[J]. J4, 2014, 41(4): 173-178+185.

XIAO Yilong;JIANG Haibo. Distributed storage algorithm with high performance for the UWSN[J]. J4, 2014, 41(4): 173-178+185.

参考文献

［1］ Reddy S K V L, Ruj S, Nayak A. Distributed Data Survivability Schemes in Mobile Unattended Wireless Sensor Networks ［C］//Proceedings of IEEE GLOBECOM. Piscataway: IEEE, 2012: 979-984.
［2］郭江鸿, 马建峰, 张留美, 等. 高效的无线传感器网络加密数据汇聚方案［J］. 西安电子科技大学学报, 2013, 40(3): 95-101.
Guo Jianghong, Ma Jianfeng, Zhang Liumei, et al. Efficient Encrypted Data Aggregation Scheme for Wireless Sensor Networks ［J］. Journal of Xidian University, 2013, 40(3): 95-101.
［3］ Mitra S, De Sarkar A, Ray S. A Review of Fault Management System in Wireless Sensor Network ［C］//Proceedings of the CUBE International Conference on Information Technology. New York: ACM, 2012: 144-148.
［4］ Vitali D, Spognardi A, Mancini L V. Replication Schemes in Unattended Wireless Sensor Networks ［C］//Proceedings of 4th IFIP International Conference on New Technologies, Mobility and Security. Piscataway: IEEE, 2011: 1-5.
［5］任伟, 任毅, 张慧, 等. 无人值守无线传感器网络中一种安全高效的数据存活策略［J］. 计算机研究与发展, 2009, 46(12): 2093-2100.
Ren Wei, Ren Yi, Zhang Hui, et al. A Secure and Efficient Data Survival Strategy in Unattended Wireless Sensor Network ［J］. Journal of Computer Research and Development, 2009, 46(12): 2093-2100.
［6］ Kong Z, Aly S A, Soljanin E. Decentralized Coding Algorithms for Distributed Storage in Wireless Sensor Networks ［J］. IEEE Journal on Selected Areas in Communications, 2010, 28(2): 261-267.
［7］ Cooper C, Frieze A. The Cover Time of Random Geometric Graphs ［J］. Random Structures and Algorithms, 2011, 38(3): 324-349.
［8］ Avin C, Krishnamachari B. The Power of Choice in Random Walks: An Empirical Study ［J］. Computer Networks, 2008, 52(1): 44-60.
［9］ Tzevelekas L, Oikonomou K, Stavrakakis I. Random Walk with Jumps in Large-scale Random Geometric Graphs ［J］. Computer Communications, 2010, 33(13): 1505-1514.
［10］ Cooper C, Frieze A, Radzik T. Multiple Random Walks in Random Regular Graphs ［J］. SIAM Journal on Discrete Mathematics, 2009, 23(4): 1738-1761.

[1]	李明,胡江平,曹晓莉. 异构传感网成本优化的节点部署策略[J]. 西安电子科技大学学报, 2021, 48(4): 11-19.
[2]	黄影,华雨晴. 能量与路径约束的无线传感网络路由优化[J]. 西安电子科技大学学报, 2020, 47(3): 113-120.
[3]	周杰,徐梦颖,王娇娇,卢毅. 认知无线传感器网络频谱分配的一种改进方法[J]. 西安电子科技大学学报, 2020, 47(3): 80-85.
[4]	杨杰,蒋俊正. 利用联合图模型的传感器网络数据修复方法[J]. 西安电子科技大学学报, 2020, 47(1): 44-51.
[5]	田强,冯大政,李进,胡豪爽. 一种利用声音能量的两步SDR定位算法[J]. 西安电子科技大学学报, 2019, 46(4): 16-21.
[6]	甄岩,赵虎. 层次型软件定义无线传感器网络资源调度策略[J]. 西安电子科技大学学报, 2019, 46(4): 87-98.
[7]	卢毅,周杰,万连城. 一种无线传感器网络二维目标覆盖的改进方法[J]. 西安电子科技大学学报, 2019, 46(2): 101-106.
[8]	王建伟;张海林. 上行小小区网络采用累计分布函数的资源分配[J]. 西安电子科技大学学报, 2018, 45(3): 163-168.
[9]	周彦果;张海林;陈瑞瑞. 毫微微小区网络中采用双层博弈的资源分配[J]. 西安电子科技大学学报, 2017, 44(4): 62-68.
[10]	方德亮;冉晓旻;李鸥. 一种能量有效的分布式传感器管理算法[J]. 西安电子科技大学学报, 2017, 44(2): 171-177.
[11]	乔俊峰;刘三阳;齐小刚. 无线传感器网络中基于鲁棒优化的功率控制[J]. 西安电子科技大学学报, 2016, 43(5): 81-87.
[12]	王爱民;刘永强;张婧;刘衍珩. WSNs中一种寻找最小工作节点集的覆盖算法[J]. 西安电子科技大学学报, 2016, 43(4): 141-146.
[13]	王晶;张帅;高丹;王营冠. 无线传感器网络分布式同步协议[J]. 西安电子科技大学学报, 2016, 43(4): 105-110+134.
[14]	岳婧;白宝明. 无线传感器网络码分复用方案性能分析[J]. 西安电子科技大学学报, 2016, 43(3): 6-12.
[15]	魏声云;张静;郭虹;李鸥. 改进二进制粒子群优化的节点选择算法[J]. 西安电子科技大学学报, 2016, 43(2): 150-156.

无人值守传感器网络的高性能分布式存储算法

Distributed storage algorithm with high performance for the UWSN

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0