面向无线传感网络应用的改进LZW算法

doi:10.11896/jsjkx.190400108

摘要/Abstract

摘要： 在无线传感网络通信中,传感器数据需要通过无线设备发送给上位机。随着终端传感器传输数据量的增大,无线设备的发送能耗逐渐加大。在不便于及时维护的复杂环境中,这将导致无线通讯设备过早失效从而使得通讯中断。因此需要先将传感器采集到的数据进行压缩,减小发送数据量。在分析传感器数据特点和传统的LZW(Lempel-Ziv-Welch)压缩算法的基础上,提出了一种面向无线传感网络应用的改进LZW算法。该算法首先对采集到的传感器相邻数据进行差值预处理,以提高数据项的重复率;然后选择大小合适的字典,在字典上用哈希存储的方式代替传统的顺序存储,以改进字典更新方式,当检测到压缩率降低时更新字典,并保存常用单字符,释放字典空间,达到数据压缩的目的。实验数据显示,与传统的LZW算法相比,改进的LZW算法使得有序传感器数据的压缩率最高降低40%,减小了所需发送数据的数据量,压缩速度也提高了近10倍,证明了面向无线传感网络应用的改进LZW算法是有效可行的。

关键词: LZW算法, 数据预处理, 无线传感网络, 压缩率, 压缩算法

Abstract: In wireless sensor network communication,sensor data need to be sent to the host computer through the wireless device.With the increase of the amount of data needed to be transmitted by the terminal sensors,the energy consumption of wireless devices is gradually increasing.A complex environment that is not convenient for timely maintenance lead to premature failure of wireless communication equipment and communication interruption.Therefore,it is necessary to compress the data collected by the sensor to reduce the amount of data sent.Based on the analysis of sensor data characteristics and traditional LZW (Lempel-Ziv-Welch) compression algorithm,an improved LZW algorithm for wireless sensor network applications is proposed.Firstly,the algorithm preprocesses the adjacent data collected from sensor to calculate the difference,so as to improve the repetition rate of the data items.Then,the appropriate dictionary size is selected and the traditional order memory is replaced with the hash memory in the dictionary,so as to improve the way of dictionary updating.When the compression rate is decreased,the proposed algorithm updates the dictionary,and saves the common single character to release the dictionary space,for data compression.The experimental results show that compared with traditional LZW algorithm,the improved LZW algorithm reduces the compression rate of the ordered sensor data by up to 40%,and reduces the amount of data needed to send.The compression speed is also increased by nearly ten times,which proves that the improved LZW algorithm for wireless sensor network applications is effective and feasible.

Key words: Compression algorithm, Compression ratio, Data preprocessing, LZW algorithm, Wireless sensor network

中图分类号:

TP301.6

倪晓军, 佘戌豪. 面向无线传感网络应用的改进LZW算法[J]. 计算机科学, 2020, 47(5): 260-264. https://doi.org/10.11896/jsjkx.190400108

NI Xiao-jun, SHE Xu-hao. Improvement of LZW Algorithms for Wireless Sensor Networks[J]. Computer Science, 2020, 47(5): 260-264. https://doi.org/10.11896/jsjkx.190400108

参考文献

[1]CHUNAWALE A,SIRSIKAR S.Minimization of average energy consumption to prolong lifetime of Wireless Sensor Network[C]//2014 IEEE Global Conference on Wireless Computing & Networking (GCWCN).Lonavala,2014:244-248.
[2]IRMAK E,KÖSE A,GÖÇMEN G.Simulation and ZigBee based wireless monitoring of the amount of consumed energy at smart homes[C]//2016 IEEE International Conference on Renewable Energy Research and Applications (ICRERA).Birmingham,2016:1019-1023.
[3]KUMAR R,MALIK A,SINGH S,et al.Reversible data hiding scheme for LZW codes using even-odd embedding strategy[C]//2016 International Conference on Computing,Communication and Automation (ICCCA).Noida,2016:1399-1403.
[4]MARKSTEINER S,JIMENEZ V J E,VALIANT H,et al.An overview of wireless IoT protocol security in the smart home domain[C]//2017 Internet of Things Business Models,Users,and Networks.Copenhagen,2017:1-8.
[5]LI S,LIAN G,PENG Z.Research on the loss-less Compression algorithm of the ultrasonic testing of rail[C]//2015 Symposium on Piezoelectricity,Acoustic Waves,and Device Applications (SPAWDA).Jinan,2015:458-461.
[6]MANJULA Y,SHIVAKUMAR K B.Enhanced secure imagesteganography using double encryption algorithms[C]//2016 3rd International Conference on Computing for Sustainable Global Development (INDIACom).New Delhi,2016:705-708.
[7]SANGEETHA M,BETTY P,KUMAR G S N.A biometrie iris image compression using LZW and hybrid LZW coding algorithm[C]//2017 International Conference on Innovations in Information,Embedded and Communication Systems (ICIIECS).Coimbatore,2017:1-6.
[8]KAUR G,KAD S.Improved Bee-Inspired routing protocol using Lzw based lossless compression[C]//2015 2nd International Conference on Recent Advances in Engineering & Computatio-nal Sciences (RAECS).Chandigarh,2015:1-6.
[9]PAN G,HE J,WU Q,et al.Automatic stabilization of Zigbee network[C]//2018 International Conference on Artificial Intelligence and Big Data (ICAIBD).Chengdu,2018:224-227.
[10]ALAM M A,FAKHRUL A,ATEEQ-UR-RAHMAN S,et al.Faster Image Compression Technique Based on LZW Algorithm Using GPU Parallel Processing[C]//2018 Joint 7th International Conference on Informatics,Electronics & Vision (ICIEV) and 2018 2nd International Conference on Imaging,Vision & Pattern Recognition (icIVPR).Kitakyushu,Japan,2018:272-275.
[11]PRABU S,MAHESWARI R.Improving wireless sensor net-work lifespan by efficient routing algorithm and LZW compression[C]//International Conference on Information Communication and Embedded Systems (ICICES2014).Chennai,2014:1-5.
[12]MALIK A,KUMAR R,SINGH S.Reversible Data HidingScheme for LZW Codes using LSB Flipping Strategy[C]//Proceedings of the International Conference on Advances in Information Communication Technology & Computing (AICTC'16).New York:ACM,2016.
[13]NAGPURKAR A W,JAISWAL S K.An overview of WSN and RFID network integration[C]//2015 2nd InternationalConfe-rence on Electronics and Communication Systems (ICECS).Coi-mbatore,2015:497-502.
[14]LI Y M,LIANG Y.Temporal Lossless and Lossy Compression in Wireless Sensor Networks[J].ACM Transactions on Senser Networks,2016,37:1-35.
[15]KUMAR R,CHAND S,SINGH S.An optimal high capacity reversible data hiding scheme using move to front coding for LZW codes[J].Multimedia Tools and Applications,2019,78(16):22977-23001.
[16]LI S H,YEN D C,CHUANG Y P.A Real-Time Audit Mechanism Based on the Compression Technique[J].ACM Trans.Manage.Inf.Syst.,2016,4:1-25.
[17]SINGH S,PANDEY P.Enhanced LZW technique for medical image compression[C]//2016 3rd International Conference on Computing for Sustainable Global Development (INDIACom).New Delhi,2016:1080-1084.
[18]GALHOTRA K,KAUR K.Extending IAMCTD using data fusion and lossless data compression for UWSN[C]//2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE).Noida,2015:526-531.

相关文章 15

[1]	黄颖琦, 陈红梅. 基于代价敏感卷积神经网络的非平衡问题混合方法 Cost-sensitive Convolutional Neural Network Based Hybrid Method for Imbalanced Data Classification 计算机科学, 2021, 48(9): 77-85. https://doi.org/10.11896/jsjkx.200900013
[2]	张婕, 梁俊斌, 蒋婵. 广域复杂流体系统中基于无线传感网的数据保存关键技术研究进展 Research Progress on Key Technologies of Data Storage Based on Wireless Sensor Networks inWide-Area Complex Fluid Systems 计算机科学, 2020, 47(5): 242-249. https://doi.org/10.11896/jsjkx.190400025
[3]	陈佳,欧阳金源,冯安琪,吴远,钱丽萍. 边缘计算构架下基于孤立森林算法的DoS异常检测 DoS Anomaly Detection Based on Isolation Forest Algorithm Under Edge Computing Framework 计算机科学, 2020, 47(2): 287-293. https://doi.org/10.11896/jsjkx.190100047
[4]	倪晓军, 高雁, 李凌锋. 基于RSSI的混合滤波算法 Hybrid Filtering Algorithm Based on RSSI 计算机科学, 2019, 46(8): 133-137. https://doi.org/10.11896/j.issn.1002-137X.2019.08.022
[5]	韩宾, 张红红, 江虹, 丁一. 基于方位信息的改进LZW前缀编码方案 Improved LZW Prefix Coding Scheme Based on Azimuth Information 计算机科学, 2019, 46(8): 157-162. https://doi.org/10.11896/j.issn.1002-137X.2019.08.026
[6]	樊哲宁, 杨秋辉, 翟宇鹏, 万莹, 王帅. 重复数据中关键属性值缺失填补的改进ROUSTIDA算法 Improved ROUSTIDA Algorithm for Missing Data Imputation with Key Attribute in Repetitive Data 计算机科学, 2019, 46(2): 30-34. https://doi.org/10.11896/j.issn.1002-137X.2019.02.005
[7]	周蓓, 黄永忠, 许瑾晨, 郭绍忠. 向量数学库的向量化方法研究 Study on SIMD Method of Vector Math Library 计算机科学, 2019, 46(1): 320-324. https://doi.org/10.11896／j.issn.1002-137X.2019.01.050
[8]	徐新黎,陈琛,皇甫晓洁,崔永婷. 能量受限的单移动设备无线充电调度算法 Wireless Charging Scheduling Algorithm of Single Mobile Vehicle with Limited Energy 计算机科学, 2018, 45(3): 108-114. https://doi.org/10.11896/j.issn.1002-137X.2018.03.018
[9]	范兴刚, 刘涛, 胡凤丹, 蒿翔. 一种延长目标覆盖网络寿命的群智能算法 Swarm Intelligence Algorithm for Prolonging Target Coverage Network Lifetime 计算机科学, 2018, 45(12): 86-91. https://doi.org/10.11896／j.issn.1002-137X.2018.12.013
[10]	檀朝东,闵帆,吴霄,李欣伦. 带弱通配符的模式匹配及其在时序分析中的应用 Pattern Matching with Weak-wildcard in Application of Time Series Analysis 计算机科学, 2018, 45(1): 103-107. https://doi.org/10.11896/j.issn.1002-137X.2018.01.016
[11]	张晓潘,袁凌云. 具有时滞-扩散作用的无线传感网络病毒传播模型的振荡动力学研究 Oscillatory Behaviors of Malware Propagation Model in Wireless Sensor Networks with Time Delays and Reaction-diffusion Terms 计算机科学, 2017, 44(Z6): 390-394. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.088
[12]	梁路,龚奔龙,黎剑,滕少华. 一种缓解分类面交错的样本点扩散方法 Diffusion Method of Sample Points for Alleviating Staggered Situation of Classification 计算机科学, 2017, 44(9): 286-289. https://doi.org/10.11896/j.issn.1002-137X.2017.09.053
[13]	池云仙,赵书良,罗燕,高琳,赵骏鹏,李超. 基于词频统计规律的文本数据预处理方法 Text Data Preprocessing Based on Term Frequency Statistics Rules 计算机科学, 2017, 44(10): 276-282. https://doi.org/10.11896/j.issn.1002-137X.2017.10.050
[14]	田贤忠,肖赟. 一种能量捕获无线传感网络机会路由算法 Algorithm of Opportunistic Routing Based on Energy Harvesting Wireless Sensor Networks 计算机科学, 2016, 43(Z6): 288-290. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.069
[15]	袁利永,朱艺华,邱树伟. 无线传感mesh网络的分段地址分配策略及其路由 Segmented Address Assignment Policy and Routing for Wireless Sensor Mesh Networks 计算机科学, 2016, 43(6): 116-121. https://doi.org/10.11896/j.issn.1002-137X.2016.06.024

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed