电力线载波窄带通信报文压缩算法研究
|
摘要
随着国家加大力度提高电网自动化、信息化水平建设,电力线载波通信在我国通信领域的地位越来越重要。伴随着电力线载波通信网络的迅速发展,网络中产生了大量数据信息,使得电力线通信网络也会像互联网那样面临着海量数据处理的难题,大量数据的存储和传输成为了人们关注的课题。
本课题正是基于提高电力线载波通信报文的传输效率和准确率这种需求而提出的。本文首先分析了电力线载波通信报文特点,然后结合电力线载波通信报文特点研究并设计了电力线载波通信报文压缩、解压缩算法,最后在某公司研发生产的载波芯片上实现压缩、解压缩算法。
通过查阅大量文献以及相关的调查研究,本文总结出电力线载波通信报文两大重要特点:首先,在电力线通信中,由于报文传输速率低,用于传输的时间远远多于在本地处理报文所需要的时间。其次,电力线载波通信报文短小,长度一般不会超过256个字节,不易从统计模型角度进行压缩。
基于上述两大特点,在国内外已有研究成果的基础上,结合某公司研发生产的载波通信芯片设计方案,本文通过查阅相关文献,深入研究数据压缩本质及各种压缩算法,最终选定利用一种通用的顺序压缩算法——LZ77算法的压缩思想,深入研究其在电力线窄带通信报文压缩中的应用价值,设计并实现了一种朴素的电力线载波通信网络层报文的数据压缩、解压缩算法。
然后,本文结合理论分析以及相关的实验结果,从压缩粒度和数据结构两个角度不断地改进电力线载波通信报文压缩算法。在压缩粒度选择上,为提高压缩比,对比分析了在字节级别、位级别以及半字节级别进行压缩的优劣,并最终根据实际情况权衡选定在半字节级别进行数据压缩;在数据结构的改进上,为尽量缩减用于压缩表示的额外开销,从设置压缩标志位到前置压缩表示计数,用压缩计数加压缩表示来表示压缩报文;在压缩策略选择上,为提高压缩比,改进了LZ77顺序压缩的思路,打破LZ77顺序压缩的思想,不是随着滑动窗口的顺序滑动实时地进行数据压缩,而是在标记了每个位置起始的最长重复子序列之后从这些子序列中选择一组最优的压缩组合,从而达到最大程度的压缩;在算法的搜索步骤上,为提高算法执行效率,通过引入后缀数组这种数据结构改进了搜索字符串匹配的效率,从而改进了压缩算法。
最后,本文给出了电力线载波通信报文压缩算法,分析算法性能,并提出了今后继续改进的方向。
本课题研究所涉及的内容有着扎实的理论基础和相对完整的理论体系,选定的研究平台的研究开发公司在载波通信应用领域已取得令人鼓舞的成果,做出了比较好的产品,所有这些成果,都为本课题的开展奠定了基础。
As the State is increasing the efforts to accelerate the automation and informationization construction of the grid, the role of power line carrier communication (referred to as PLC) in the field of communication is becoming more and more important. But a lot of data is produced with the fast development of the power line carrier communication, which make the power line carrier communication network have to face the problem of massive data processing. Storage and transmission of large amount of data has become a subject of concern.
This subject is proposed to improve power line carrier communication packet transmission efficiency and accuracy. This paper first analyzes the power line carrier communication pacekt’s characteristics, which are put into consideration during the designing of the PLC packet compression and decompression algorithms. The compression and decompression algorithms are both implemented in the Power Line Carrier Communication chip of certain company.
Through access to a large number of documents and related research, this article summarizes the PLC packet, and gets the following two important features: First, the power line carrier communication packet is short, the length of which does not exceed 256 bytes, and thus it is not easy to be compressed from the perspective of statistic model. Second, the transmission rate of the PLC packet is low, so the time spent on transmission is far more than the time spent on the local processing of the packets.
Based on the above two features and the existing research results home and abroad, combined with the design of the PLC chip of certain company, this paper consults large amount of relative documents, and at the same time does deep research both on the nature of data compression and the variety of compression algorithms. At last this paper chooses to utilize a universal data compression algorithm-LZ77-to design and implement one plain compression/decompression algorithm on the PLC packet.
Then, with theoretical analysis and relative experiment results, this paper improves the designed compression algorithm from the following two aspects: compression scale and data structure. In the choice of compression scale, this paper compares the advantages and the disadvantages of compressing in byte degree, bit degree and semi-byte degree in order to improve compression ratio, and at last fix to compress in the scale of semi-byte. In the improvement of data structure, this paper tries to reduce the compression extra spending by firstly setting flag bit and then using a kind of compression count. In the implement of the algorithm, this paper breaks the sequence compressing order to improve compression ratio, which chooses the optimal compression combination after computing every position’s longest match rather than sequentially sliding the sliding-window. In the search step of the algorithm, this paper introduces suffix array to improve the search efficiency.
Finally, this paper presents and analyzes the latest power line carrier communication packet compression algorithm.
This subject has a solid theoretical foundation and a relatively complete theoretical system, and the company which develops the implementation environment this paper used has reached great achievements, and produces high quality products. All the fruits above make good foundation for this subject.
本课题正是基于提高电力线载波通信报文的传输效率和准确率这种需求而提出的。本文首先分析了电力线载波通信报文特点,然后结合电力线载波通信报文特点研究并设计了电力线载波通信报文压缩、解压缩算法,最后在某公司研发生产的载波芯片上实现压缩、解压缩算法。
通过查阅大量文献以及相关的调查研究,本文总结出电力线载波通信报文两大重要特点:首先,在电力线通信中,由于报文传输速率低,用于传输的时间远远多于在本地处理报文所需要的时间。其次,电力线载波通信报文短小,长度一般不会超过256个字节,不易从统计模型角度进行压缩。
基于上述两大特点,在国内外已有研究成果的基础上,结合某公司研发生产的载波通信芯片设计方案,本文通过查阅相关文献,深入研究数据压缩本质及各种压缩算法,最终选定利用一种通用的顺序压缩算法——LZ77算法的压缩思想,深入研究其在电力线窄带通信报文压缩中的应用价值,设计并实现了一种朴素的电力线载波通信网络层报文的数据压缩、解压缩算法。
然后,本文结合理论分析以及相关的实验结果,从压缩粒度和数据结构两个角度不断地改进电力线载波通信报文压缩算法。在压缩粒度选择上,为提高压缩比,对比分析了在字节级别、位级别以及半字节级别进行压缩的优劣,并最终根据实际情况权衡选定在半字节级别进行数据压缩;在数据结构的改进上,为尽量缩减用于压缩表示的额外开销,从设置压缩标志位到前置压缩表示计数,用压缩计数加压缩表示来表示压缩报文;在压缩策略选择上,为提高压缩比,改进了LZ77顺序压缩的思路,打破LZ77顺序压缩的思想,不是随着滑动窗口的顺序滑动实时地进行数据压缩,而是在标记了每个位置起始的最长重复子序列之后从这些子序列中选择一组最优的压缩组合,从而达到最大程度的压缩;在算法的搜索步骤上,为提高算法执行效率,通过引入后缀数组这种数据结构改进了搜索字符串匹配的效率,从而改进了压缩算法。
最后,本文给出了电力线载波通信报文压缩算法,分析算法性能,并提出了今后继续改进的方向。
本课题研究所涉及的内容有着扎实的理论基础和相对完整的理论体系,选定的研究平台的研究开发公司在载波通信应用领域已取得令人鼓舞的成果,做出了比较好的产品,所有这些成果,都为本课题的开展奠定了基础。
As the State is increasing the efforts to accelerate the automation and informationization construction of the grid, the role of power line carrier communication (referred to as PLC) in the field of communication is becoming more and more important. But a lot of data is produced with the fast development of the power line carrier communication, which make the power line carrier communication network have to face the problem of massive data processing. Storage and transmission of large amount of data has become a subject of concern.
This subject is proposed to improve power line carrier communication packet transmission efficiency and accuracy. This paper first analyzes the power line carrier communication pacekt’s characteristics, which are put into consideration during the designing of the PLC packet compression and decompression algorithms. The compression and decompression algorithms are both implemented in the Power Line Carrier Communication chip of certain company.
Through access to a large number of documents and related research, this article summarizes the PLC packet, and gets the following two important features: First, the power line carrier communication packet is short, the length of which does not exceed 256 bytes, and thus it is not easy to be compressed from the perspective of statistic model. Second, the transmission rate of the PLC packet is low, so the time spent on transmission is far more than the time spent on the local processing of the packets.
Based on the above two features and the existing research results home and abroad, combined with the design of the PLC chip of certain company, this paper consults large amount of relative documents, and at the same time does deep research both on the nature of data compression and the variety of compression algorithms. At last this paper chooses to utilize a universal data compression algorithm-LZ77-to design and implement one plain compression/decompression algorithm on the PLC packet.
Then, with theoretical analysis and relative experiment results, this paper improves the designed compression algorithm from the following two aspects: compression scale and data structure. In the choice of compression scale, this paper compares the advantages and the disadvantages of compressing in byte degree, bit degree and semi-byte degree in order to improve compression ratio, and at last fix to compress in the scale of semi-byte. In the improvement of data structure, this paper tries to reduce the compression extra spending by firstly setting flag bit and then using a kind of compression count. In the implement of the algorithm, this paper breaks the sequence compressing order to improve compression ratio, which chooses the optimal compression combination after computing every position’s longest match rather than sequentially sliding the sliding-window. In the search step of the algorithm, this paper introduces suffix array to improve the search efficiency.
Finally, this paper presents and analyzes the latest power line carrier communication packet compression algorithm.
This subject has a solid theoretical foundation and a relatively complete theoretical system, and the company which develops the implementation environment this paper used has reached great achievements, and produces high quality products. All the fruits above make good foundation for this subject.
引文
[1]杨宗剑等.低压电力线载波抄表系统现状及发展.湖北电力,2008,32 (5):62～70
[2]林其田.低压电力线载波抄表系统.福建建设科技,2006,No.01:52～54
[3]王学伟等.电力线载波DS扩频通信及数据压缩.中国住宅设施,2008,No.08:50～53
[4]毕研秋.电力系统数据压缩的算法研究及通信网络仿真:[博士学位论文].山东:山东大学,2007
[5]苗世洪,王少荣,刘沛,程时杰.数据压缩技术在电力系统通信中的应用.电力自动化设备, 1999,(03): 32～33
[6]苗世洪,孙扬声,吴小辰.基于电力系统故障信息远程通信的高效数据压缩与解压技术研究.电力系统自动化, 1996,(05):53～55
[7]孙金凤.电力数据压缩传输及解压算法的研究与实现:[硕士学位论文].北京:北京化工大学,2008
[8]张超,房若季.改进的Lzss压缩算法在故障信息文件远传中的应用.电网技术,2003,27(6):42～44
[9]吕海.电力线载波通信研究及应用:[硕士学位论文].甘肃:兰州大学,2008
[10]田宏伟.电力线通信技术应用研究及其在远程抄表中的应用:[硕士学位论文].江苏:苏州大学,2006
[11]汤效军.“十一五”期间电力线载波通信的发展对策.电力系统通信,27(168):75～79
[12]杨刚等.电力线通信技术.北京:电子工业出版社,2011:2～5
[13]李晓亮.PLC电力载波通信研究:[硕士学位论文].西安:西安电子科技大学,2009
[14]齐淑清.电力线通信(PLC)技术与应用.北京:中国电力出版社,2005:3～14
[15]孔英会.电力线载波通信的现状与发展.电力情报,1996,No.04:15～17
[16]孙彧.低压电力线载波通信技术的应用研究:[硕士学位论文].上海:上海海事大学,2005
[17]国内窄带电力载波通信技术发展现状
[18]孔令通.电力线通信关键技术研究:[硕士学位论文].北京:北京交通大学,2007
[19]王继业.宽带电力线通信应用的研究:[硕士学位论文].北京:华北电力大学,2003
[20]张蕊.电力系统数据压缩算法的研究与实现:[硕士学位论文].北京:北京化工大学,2009
[21]孙妙平.电力系统测量数据的压缩、传输及解压研究:[硕士学位论文].四川:西南交通大学,2003
[22]卢文冰等.载波抄表系统通信方案研究,东北电力学院学报,2002,22(2) :9～13
[23] Mark Nelson著,贾起东译,数据压缩技术原理与范例.科学出版社,1995.09:163～171
[24]吴乐南.数据压缩的原理与应用.北京:电子工业出版社,1995:1～2
[25] Guy E. Blelloch. Introduction to Data Compression. sept 25, 2010.
[26]缪志宏.数据压缩算法实现研究:[硕士学位论文].浙江:浙江大学,2003
[27]Mohammed Al-Laham and Ibrahiem M.M.EI Emary et. al., Comparitive study between various algorithms of Data Compression techniques, Proceedings of the World Congress on Engineering and Computer Science 2007, WCECS 2007 , October 24 -26 , 2007,U.S.A.
[28] Khalid Sayood. Introduction to Data Compression, Morgan Kaufmann publisher , 3 edition (December 15, 2005) 121～127
[29] J. Ziv,A. Lempel.A Universal Algorithm for Sequential Data Compression. IEEE TRANSACTIONS ON INFORMATION THEORY, MAY 1977,VOL. IT-23, NO. 3:337～343
[30]毕菲菲.LZ数据压缩算法分析及其在印章系统中的应用:[硕士学位论文].四川:电子科技大学,2008
[31]刘萌,丁香乾,侯军伟,王锐.电力线窄带通信报文压缩算法研究,微型机与应用,2010, 29(312) :65～68
[32]严蔚敏,吴伟民.数据结构(C语言版).北京:清华大学出版社,1997:79～84
[33] GiovanniManzini and Paolo Ferragina.Engineering a lightweight suffix array construction algorithm.Algorithmica,June 2004,40(1):33–50.
[34]郭海涛.用加强的后缀树组查找MUM:[硕士学位论文].西安:西安电子科技大学,2003
[35]D.Gusfield,Algorithms on Strings,Trees,and Sequences,Cambridge University Press, New York,1997.
[36] U. Manber and G. Myers, Suffix arrays: A new method for on-line string searches, SIAM J. Comput. 22 (1993), 935–938.
[37]许智磊.后缀数组.安徽省芜湖市第一中学
[38] J. Karkainen, P. Sanders, and S.Burkhardt. Linear work suffix array construction. Journal of the ACM,53(6):918–936, 2006.
[39] D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, June 2003.
[40] P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, June 2003.
[41]N.Jesper Larsson and Kunihiko Sadakane.Faster suffix sorting.Technical Report LUCS-TR:99-214,Dept.of Comp.Science,Lund University,Sweden,1999.
[42]GiovanniManzini and Paolo Ferragina.Engineering a lightweight suffix array construction algorithm.Algorithmica,40(1):33–50,June 2004.
[43]Stefan Burkhardt and Juha Karkkainen.Fast lightweight suffix array construction and checking.In Proc.14th Symp.on Combinatorial Pattern Matching(CPM), volume 2676 of Lecture Notes in Computer Science,pages 55–69.Springer,2003.
[44]J.Karkkainen,P.Sanders,Simple linear work suffix array construction,in:Proc.International Colloquium on Automata,Languages and Programming,in:LectureNotes in Computer Science,vol.2719,Springer-Verlag,Berlin,2003,pp.943–955.
[45] A. Ferreira, A. Oliveira, and M. Figueiredo. On the use of suffix arrays for memory-efficient Lempel-Ziv data compression. In DCC’09: Proc. of the IEEE Conference on Data Compression, page 444, 2009.
[46]. Ferreira, A. Oliveira, and M. Figueiredo. On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression",ICETE 2008, CCIS - Communications in Computer and Information Science, vol. 48, pp. 267-280
[2]林其田.低压电力线载波抄表系统.福建建设科技,2006,No.01:52～54
[3]王学伟等.电力线载波DS扩频通信及数据压缩.中国住宅设施,2008,No.08:50～53
[4]毕研秋.电力系统数据压缩的算法研究及通信网络仿真:[博士学位论文].山东:山东大学,2007
[5]苗世洪,王少荣,刘沛,程时杰.数据压缩技术在电力系统通信中的应用.电力自动化设备, 1999,(03): 32～33
[6]苗世洪,孙扬声,吴小辰.基于电力系统故障信息远程通信的高效数据压缩与解压技术研究.电力系统自动化, 1996,(05):53～55
[7]孙金凤.电力数据压缩传输及解压算法的研究与实现:[硕士学位论文].北京:北京化工大学,2008
[8]张超,房若季.改进的Lzss压缩算法在故障信息文件远传中的应用.电网技术,2003,27(6):42～44
[9]吕海.电力线载波通信研究及应用:[硕士学位论文].甘肃:兰州大学,2008
[10]田宏伟.电力线通信技术应用研究及其在远程抄表中的应用:[硕士学位论文].江苏:苏州大学,2006
[11]汤效军.“十一五”期间电力线载波通信的发展对策.电力系统通信,27(168):75～79
[12]杨刚等.电力线通信技术.北京:电子工业出版社,2011:2～5
[13]李晓亮.PLC电力载波通信研究:[硕士学位论文].西安:西安电子科技大学,2009
[14]齐淑清.电力线通信(PLC)技术与应用.北京:中国电力出版社,2005:3～14
[15]孔英会.电力线载波通信的现状与发展.电力情报,1996,No.04:15～17
[16]孙彧.低压电力线载波通信技术的应用研究:[硕士学位论文].上海:上海海事大学,2005
[17]国内窄带电力载波通信技术发展现状
[18]孔令通.电力线通信关键技术研究:[硕士学位论文].北京:北京交通大学,2007
[19]王继业.宽带电力线通信应用的研究:[硕士学位论文].北京:华北电力大学,2003
[20]张蕊.电力系统数据压缩算法的研究与实现:[硕士学位论文].北京:北京化工大学,2009
[21]孙妙平.电力系统测量数据的压缩、传输及解压研究:[硕士学位论文].四川:西南交通大学,2003
[22]卢文冰等.载波抄表系统通信方案研究,东北电力学院学报,2002,22(2) :9～13
[23] Mark Nelson著,贾起东译,数据压缩技术原理与范例.科学出版社,1995.09:163～171
[24]吴乐南.数据压缩的原理与应用.北京:电子工业出版社,1995:1～2
[25] Guy E. Blelloch. Introduction to Data Compression. sept 25, 2010.
[26]缪志宏.数据压缩算法实现研究:[硕士学位论文].浙江:浙江大学,2003
[27]Mohammed Al-Laham and Ibrahiem M.M.EI Emary et. al., Comparitive study between various algorithms of Data Compression techniques, Proceedings of the World Congress on Engineering and Computer Science 2007, WCECS 2007 , October 24 -26 , 2007,U.S.A.
[28] Khalid Sayood. Introduction to Data Compression, Morgan Kaufmann publisher , 3 edition (December 15, 2005) 121～127
[29] J. Ziv,A. Lempel.A Universal Algorithm for Sequential Data Compression. IEEE TRANSACTIONS ON INFORMATION THEORY, MAY 1977,VOL. IT-23, NO. 3:337～343
[30]毕菲菲.LZ数据压缩算法分析及其在印章系统中的应用:[硕士学位论文].四川:电子科技大学,2008
[31]刘萌,丁香乾,侯军伟,王锐.电力线窄带通信报文压缩算法研究,微型机与应用,2010, 29(312) :65～68
[32]严蔚敏,吴伟民.数据结构(C语言版).北京:清华大学出版社,1997:79～84
[33] GiovanniManzini and Paolo Ferragina.Engineering a lightweight suffix array construction algorithm.Algorithmica,June 2004,40(1):33–50.
[34]郭海涛.用加强的后缀树组查找MUM:[硕士学位论文].西安:西安电子科技大学,2003
[35]D.Gusfield,Algorithms on Strings,Trees,and Sequences,Cambridge University Press, New York,1997.
[36] U. Manber and G. Myers, Suffix arrays: A new method for on-line string searches, SIAM J. Comput. 22 (1993), 935–938.
[37]许智磊.后缀数组.安徽省芜湖市第一中学
[38] J. Karkainen, P. Sanders, and S.Burkhardt. Linear work suffix array construction. Journal of the ACM,53(6):918–936, 2006.
[39] D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, June 2003.
[40] P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. Springer, June 2003.
[41]N.Jesper Larsson and Kunihiko Sadakane.Faster suffix sorting.Technical Report LUCS-TR:99-214,Dept.of Comp.Science,Lund University,Sweden,1999.
[42]GiovanniManzini and Paolo Ferragina.Engineering a lightweight suffix array construction algorithm.Algorithmica,40(1):33–50,June 2004.
[43]Stefan Burkhardt and Juha Karkkainen.Fast lightweight suffix array construction and checking.In Proc.14th Symp.on Combinatorial Pattern Matching(CPM), volume 2676 of Lecture Notes in Computer Science,pages 55–69.Springer,2003.
[44]J.Karkkainen,P.Sanders,Simple linear work suffix array construction,in:Proc.International Colloquium on Automata,Languages and Programming,in:LectureNotes in Computer Science,vol.2719,Springer-Verlag,Berlin,2003,pp.943–955.
[45] A. Ferreira, A. Oliveira, and M. Figueiredo. On the use of suffix arrays for memory-efficient Lempel-Ziv data compression. In DCC’09: Proc. of the IEEE Conference on Data Compression, page 444, 2009.
[46]. Ferreira, A. Oliveira, and M. Figueiredo. On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression",ICETE 2008, CCIS - Communications in Computer and Information Science, vol. 48, pp. 267-280
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |