SCI论文（www.lunwensci.com）:
摘要：在讨论静态和自适应哈夫曼数据压缩算法的优点和不足后,借助于引进两个参数和一个节点符号频数表,提出了按相同频率进行分组的自适应哈夫曼数据压缩算法,减少哈夫曼树的层数。通过对高尔夫球场草坪温湿度的监测,实验表明该算法的压缩比比自适应哈夫曼算法有明显改善,这种算法编码简单、编码速度较快,适合用在能量有限的无线传感器网络的传感器节点。
关键词：无线传感器网络；数据压缩算法；自适应分组哈夫曼算法；节点符号频数表
One of Adaptive Grouping Huffman Data Compression Algorithm Based on Same Frequency
WANG Wenjuan,LUO Jing,HE Fen
(Guangzhou Nanyang Polytechnic College,Guangzhou Guangdong 510900)
【Abstract】：After this paper discussed advantages and disadvantages of static Huffman data compression algorithm and adaptive Huffman data compression algorithm,two parameters and one NFT list were introduced.By these one novel adaptive grouping Huffman data compression algorithm based on same frequency emerged.This new approach has simple coding and reduces levels of Huffman tree.The new algorithm not only makes up for static Huffman coding,but it also overcomes defects in adaptive Huffman coding.The experiment shows that the compression ratio of new algorithm gets to improve.It could apply in sensor's node.
【Key words】：WSN;data compression;adaptive grouping huffman coding;NFT
0引言
智能化领域主要涉及的是自动化系统和机器人技术,其中的关键部件是传感器。大量的传感器构成无线传感器网络,通过传感器节点获取数据,再经模数转换器转化成数字形式,后续才能进行数字化存储、传输、处理等工作。然而,当模拟信号转换为数字信号时数据量呈爆炸性增长,不仅占用大量的存储空间、数据传输量非常大,而且造成通信信道及网络压力很大,与此同时对节点的电池的电量消耗巨大,因此上如果要延长传感器节点生命周期,降低能耗是无线传感器网络从物理层到应用层设计的最主要目标之一,解决上述问题的关键技术之一就是减少数据量的数据压缩技术[1]。
达到减少数据存储的容量,较快地传输各种信号的数据压缩算法,通俗地说就是用最少的数码来表示信号。数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩。本文探讨的是无损压缩的哈夫曼编码数据压缩算法,在分析指出静态和自适应哈夫曼数据压缩算法之不足之处的基础上,提出了一种按相同频率进行分组的自适应哈夫曼数据压缩算法,该算法编码简单,尤其重要的是减少了哈夫曼树的层数,因此可以推广到传感器的节点。通过对高尔夫球场草坪温湿度的监测,表明该算法的压缩比比自适应哈夫曼算法有明显改善,可以降低网络的传送压力适合用在能量有限的传感器节点上。
1静态和自适应哈夫曼数据压缩算法存在的问题
无论静态哈夫曼数据压缩算法还是自适应哈夫曼数据压缩算法首先解决的问题就是减少数据编码冗余。
静态哈夫曼数据压缩算法采用的方法是对输入的符号流进行编码,通过第一次扫描统计字符出现的概率,并创建哈夫曼树,然后第二次扫描是按照哈夫曼树的字符进行编码。这种编码的前提是在编码前可以精确地统计或估计信息中符号出现概率,因而缺点是显而易见的,一是对于数据量较大的信息,静态统计要消耗大量的时间；二是必须保存统计出的结果以便解码时构造相同的编码树,或者直接保存编码树本身；如果每次静态统计结果不同,都要保存,这就占用了大量的空间。实际上,大部分情况下不能预先得知符号出现概率,况且静态哈夫曼编码的数据压缩也不能解决数据的实时传输问题,因此产生了自适应哈夫曼编码。自适应哈夫曼编码采取了一边扫描数据,一边编码的方式,也就是一边采集统计数据,一边建树的方式,扫描完成后编码也完成。在扫描的过程中就可以同时传输数据,这就解决了实时传输的问题。
评价数据压缩的一个重要标准是压缩比。虽然自适应哈夫曼算法可以解决数据等实时传输问题,但代价也是很大的,即每读取一个数据就更新哈夫曼树的结构,构造一个新的子树,使得自适应哈夫曼算法变得复杂,层次较多,这就增加了编码和解码的复杂,因此这种方法效率低,需要消耗更多的节点能量。
要解决上述问题与不足,需要考虑如何降低这种算法的复杂性,减少哈夫曼树的层数,提高压缩比,新的算法既要弥补了静态哈夫曼算法的不足,也要克服自适应哈夫曼算法的缺点。
2同频率分组自适应哈夫曼数据压缩算法
2.1算法策略
考虑到静态哈夫曼数据压缩算法数据压缩较好,而自适应哈夫曼数据压缩算法可以解决实时数据传输问题这两个方面,我们需要在数据压比和哈夫曼树的层数之间寻找合适的方法,通过对出现频率相同的信源符号集进行分组,然后再进行自适应哈夫曼编码的新方法,从根本上改变原有的哈夫曼编码的机制,即利用建立哈夫曼树时都要计算出每个节点符号出现的频率[2],根据出现的频率给每个符号赋予权值,然后按照相同频率划分为一组的方式来构建哈夫曼树,当有相同频率的数据再出现的时候,不用再构造新的节点,这样二进制树的叶子便是同频率的一个信源符号集而不是单一信源符号,于是便可以减少二进制树的层数。
这样构建的哈夫曼树将按照各分组构建树的各节点,使用自适应哈夫曼算法对其进行编码,得到分组的节点编码,组内信源符号的编码使用静态哈夫曼算法,这就是基于同频率分组的自适应哈夫曼数据压缩算法[3,5]。
2.2算法设计
在传感器的节点,针对第i次测量的值用mi代表,这个直接测量所得的结果是模拟数据,需要用ADC将其转换为二进制数据,对于第i次的模拟数据转换为相应的二进制数据用ri描述,第i-1次与第i次数据的差用di描述,即di=ri-ri-1差值将作为传输的数据[5]。
在实际的算法设计中,引进两个参数和一个记录每个节点符号出现频率的节点符号频数表[6]。两个参数,一是节点的权重,二是节点编码。这里每个外部节点的权重可以简单地表示为出现符号的次数,每个内部节点的权重表示为它的子节点权重的和,节点编码唯一,可表示为2n-1,2n-2,2n-3…(n表示符号集的大小)。数据开始发射时,发送端和接受端的哈夫曼树初始时节点符号频数表,权值设为0,一旦遇到新数据,节点将输出符号频数表编码,然后导出节点符号频数表,该表记录每个符号出现的频率,每次出现增加1。更新点则依据外部节点的权重,具有较高权重的节点占据树的较前端,即最大概率的元素移至树的顶层。以下是同频率分组自适应哈夫曼编码的数据压缩算法：
Createroot()
初始化：将每个符号的频率设置为0；
只要读取的符号不是最后一个,则该符号的使用频率均加1；
If符号的使用频率为1,
Then向节点符号频数表NFT(Node frequency table)节点发送代码并为节点符号频数表NFT建立索引
Else
查找 (di,bitree)
If 节点数不是该 block 中的最大值
Then 通过交换将最大节点数移动并增加权重 Endif
If 符号使用频率相同
prefix=traverse(node)
Suffix=arrayindex(di)
Else
Prefix=traverse(nyt)
Nyt->leftchild=createNFT() Nyt->rightchild=createnode(di) Nyt=nyt->leftchild
[page]
Code=<>
Endif
Endif
Update(bitree)
3实验结果
将静态的哈夫曼算法、自适应哈夫曼算法以及按频率分组算法分别应用到高尔夫球场草坪温湿度传感器中,对di进行无损压缩编码[7]。实验主要考虑的是三种压缩算法的数据压缩比,其公式为：
压缩比=100×(1-数据压缩后的大小/原始数据大小)
图1是三种方法结果的压缩比的比较。从实验结果看,从自适应哈夫曼数据压缩算法只提供约20%压缩,静态哈夫曼数据压缩算法提供的数据压缩比自适应哈夫曼数据压缩算法要好。静态哈夫曼算法虽然有较好的压缩比,但不能解决实时传输数据的问题,而自适应哈夫曼算法虽然解决了实时数据传输的问题,但由于构造哈夫曼树的过程复杂,不适合用在能量有限的传感器节点中[8]。基于同频率分组的自适应哈夫曼数据压缩算法结合前两种算法的优点,数据压缩比比自适应哈夫曼算法有明显的改进,但是由于改变了传统哈夫曼算法每读取一个数据就更新哈夫曼树的机制,因而构建哈夫曼树的方法简单,正是减少了哈夫曼树的层次,减少了哈夫曼编码和解码中队更新过程的调用,因而这种算法速度快,可提供较好的数据效果,更适用于传感器节点。
4结语
通过无线传感器网络能够获得大量的实时数据,应用前景十分可观,被认为是全球四大高技术产业之一,与我国的智能制造领域关系密切。但是目前在传感器节点获取数据、转换、传输仍然存在很多不足,这里我们探讨的仅仅是由温湿度传感器组成的无线传感网中的数据压缩问题,目的是减少哈夫曼数据压缩算法的构造层数,提高编码速度。
参考文献
[1]王琦,基于WSN的节能型数据压缩方法研究[D].兰州:兰州理工大学,2017.
[2]鄢涛,彭海峰,李浩,基于哈夫曼编码的多线程无损压缩库的设计与实现[J].成都科技大学学报,2019(9):287-290.
[3]徐林,邱敏华,高昌淑,等.一种基于小波变换的图像压缩编码方法[J].复旦学报(自然科学版),2004(2):115-118.
[4]邱敏华,徐林,邵谦明.基于小波分析的医学超声图像压缩及分组霍夫曼算法[J].复旦学报(自然科学版),2004(2):62-67.
[5]蒋婵等,移动低占空比传感网中基于分段拟合压缩的数据容灾存储算法[J],电子学报,2020(12):2376-2383.
[6]乔雨,嵇浩.一种基于缓冲窗口的双哈夫曼压缩算法[J].物联网技术,2021(2):90-94.
[7]梁玉芬,高德云,牛延超,等.无线传感器网络应用系统综述[J].电子技术应用,2007(09):3-5+9.
[8]包冬梅.数据压缩算法研究[J].无线互联科技,2019,16(21):112-113.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/40391.html
