基于海洋潜标观测数据压缩的数据预处理算法
时间：2023-01-23 08:25:05 来源：柠檬阅读网 本文已影响 人 
伍汉青，周 伟，杨群慧，3，季福武，3
（1.同济大学海洋地质国家重点实验室/海洋与地球科学学院，上海 200092；
2.同济大学电子与信息工程学院，上海 201804；
3.同济大学国家海底科学观测系统项目办公室，上海 200092）
海洋潜标通过锚泊系留系统固定于特定海域和水深，通过搭载各种观测设备实现海面以下的海洋环境要素的长期观测，布放回收机动灵活，被认为是海洋环境监测中最可靠、最准确的手段之一，得到了广泛的应用[1-2]。长期以来，海洋潜标多以自带电源的自容式模式工作，观测周期短则数月、长则可达一年以上。自容式潜标搭载各种传感器采集的海洋环境观测数据，早期主要通过回收潜标后导出数据；
近年来，伴随水声通信技术、感应耦合式数据传输技术的发展，潜标数据实现了准实时的传输，定期传输到海面，再通过卫星传输到岸基[3]。但是水声通信和感应耦合式数据传输能力极其有限，水声通信的数据率和通信距离成反比，通信距离超过10 km时，数据传输速率不超过10 kbps[4]；
感应耦合式数据传输速率最高仅为9.6 kbps[5]。综合考虑海洋无线通信的物理局限性与海洋环境的高复杂度，海洋潜标原始观测数据的存储和实时传输面临挑战，而将观测数据压缩处理好之后再存储和传输，不仅可以有效节省存储空间，提高无线数据传输能力，而且可以降低系统功耗，进而延长潜标自主工作时间，增强系统性能。
常用的海洋传感器数据无损压缩算法可分为基于统计模型的算法和基于字典模型的算法两大类，比较具有代表性的分别为动态Huffman算法、LZW算法（Lempel-Ziv-Welch Encoding）和Mini-LZO算法（Mini-Lempel-Ziv-Oberhumer）。动态Huffman算法的核心思想是通过动态地调整Huffman树，用前面n-1个字符出现的频率对第n个出现的字符进行编码，使原数据变成一个以0、1为形式的新的数据串，从而有效地实现数据压缩[6]。动态Huffman编码的特点是任何一个编码绝不会是其他编码的前缀，保证了对编码解码时的唯一性。LZW算法的核心思想是在原始数据中不同字符的基础上建立字典，然后用字典中字符的编码索引来替代原始数据中相应的字符，从而实现数据压缩[7]。LZW算法的特点是压缩后的编码是自解释的，解压缩时可以通过编码后的数据生成字典。Mini-LZO算法是为嵌入式系统中仅需要简单压缩和解压缩功能的程序而设计的，它的特点是牺牲了压缩效率换来了较快的压缩速度[8]。
上述无损压缩算法主要利用字符出现频率的冗余度对数据进行压缩，且编码可实时进行，提高了数据处理时效。但是这些算法的压缩率受统计冗余度的理论限制，而且当数据中各字段出现频率不高时，无法有效处理冗余的字符串信息，导致整体压缩效果大打折扣。若想要以更高效的方式将这些算法用于海洋传感器的数据压缩，可以利用数据特点对数据进行预处理，从而突破压缩率的理论限制[9]。本文根据海洋潜标经常搭载的温盐深（Conductivity-Temperature-Depth，CTD）传感器、溶解氧（Dissolved Oxygen，DO）传感器、甲烷传感器、单点海流计等传感器的数据格式特点，设计了一种通用的数据预处理算法，该算法通过数据筛选、数据差分计算、数据去重等步骤对传感器数据进行预处理，可以大幅提高压缩算法的数据压缩效率。
表1展现了潜标上最常搭载的美国海鸟公司生产的含溶解氧的温盐深（CTD-DO）传感器SBE 37-SMP-ODO MicroCAT和德国Frantech公司生产的METS甲烷传感器的数据格式。可以看出，CTD-DO传感器的数据特点为：各参数数据均为美国信息交换标准代码（American Standard Code for Information Interchange，ASCII）表示的十进制数据，数据高位无有效数据时用空格补充，小数点前一位及低位无有效数据时用“0”补充；
所有数据通过逗号隔开，日期和时间前面有一个空格，每条数据以回车、换行符作为结束标志。METS甲烷传感器数据的特点为：前两个数据为有效数据，均为ASCII码表示的十六进制数据；
后六个数据为预留位，无实际意义；
所有数据通过空格隔开，每条数据以回车符作为结束标志。单点海流计的原始数据格式由于篇幅较长，未在表1中展示，其数据格式特点为：各参数数据均以ASCII码表示（包括数字、字母和符号），每条数据有固定的起始位和结束位，数据文件以可扩展标记语言（Extensible Markup Language，XML）格式传输。
表1 SBE 37-SMP-ODO MicroCAT传感器及METS甲烷传感器数据格式
综上所述，海洋潜标搭载的传感器所采集的数据通常以ASCII码表示的数字、英文字符和控制字符为主，且每个字符均有概率出现。
从海洋潜标通常搭载的传感器的数据格式特征可知，传感器输出的原始数据，除观测要素数值外，还有不少表示采集参数或传感器配置的英文字符及个别控制字符，省略这些字符并不影响观测数据的研究[10]。另外，传感器长期处于固定水域工作，采集的数据往往具有时间或空间的相关性[11]。
根据海洋传感器的上述数据特点，本文提出了一种数据预处理算法，其实现流程如图1所示。首先对海洋传感器数据进行数据筛选，去除冗余数据，筛选出重要的传感器数据；
然后再进行数据差分运算，利用观测数据的相关性实现数据压缩；
最后通过数据去重运算进一步降低数据冗余，完成传感器观测数据的预处理。利用无损压缩算法对预处理后的传感器数据进一步压缩，从而大幅提高数据压缩效率。在海洋传感器数据预处理过程中，由于数据筛选算法为有损压缩算法，因此将同步建立解压缩协议，以确保解压缩后测量数据的无损还原。
图1 数据预处理算法实现流程
2.1 数据筛选算法
针对潜标搭载的海洋传感器输出的原始观测数据特点，通过删除数据中冗余的格式化字符，筛选出有意义的数值，随后对数据进行重组变换等处理，从而实现数据筛选，该算法实现的具体步骤如下。
（1）对观测时间数据进行压缩。以按天为单位采集与存储的传感器为例，只记录起始时间和停止时间的年、月、日信息；
期间采集数据的时间信息则用十六进制数序号1、2、3……代替，表示距离起始时间之后的第一天、第二天、第三天……；
通过数字间隔表示数据采集时间。
（2）保留传感器直接观测量，删除观测数据参数中的冗余值。
（3）更换数据表示方式，如负数表示方法，降低数据占有量。
（4）将浮点数运算改为整数运算。将各浮点数测量值的整数位部分与小数位部分分离，分别进行运算，从而将浮点数的运算转换为整数运算，具体计算方法见式（1）和式（2）；
同时省略非字母数字字符（如小数点和分隔符）。最后按各参数的传输顺序先排列整数部分、再排列各参数小数部分，形成一串新的数据流。
式中，A为某参数的原始数据；
Int为该数据的整数部分；
Dec为该数据的小数部分；
n为该参数小数部分的位数。
筛选出传感器原始数据中的关键数值、删除数据冗余部分不仅可以节省存储空间，还能在一定程度上简化计算过程、提高计算精度。
2.2 差分压缩算法
海洋潜标布放于特定海域开展海洋环境参数的长期连续监测，当采集的数据变化较小时，可使用差分压缩算法降低数据量，实现数据压缩。差分压缩算法通过采用采样数据间的变化量代替原有数据实现数据压缩。
差分压缩算法的主要步骤如下。
（1）设原始数据序列X0，X1，…，Xn，首先对数据进行差分计算，见式（3）至式（5）。
式（5）中，当Xn-Xn-1>0时，Sn=01；
Xn-Xn-1<0时，Sn=00。
经差分处理后得到的编码为：A0，S1+A1，…，Sn+An。
（2）为了避免差分算法产生累积误差并且适应观测点数据变化，每隔若干个采样数据，参考点An变化1次。将新的采样数据作为新的参考数据进行差分计算。图2为每隔20个采样点更换新的参考数据进行差分压缩的算法流程图。
图2 差分压缩算法流程图
由于差分压缩算法只涉及减法、不涉及乘除法，因此计算过程简单、执行效率高，有利于减少嵌入式系统的工作负担和工作时间、降低系统功耗。
2.3 数据去重算法
海洋传感器输出的原始观测数据经过数据筛选和差分处理后得到的编码会存在较多重复0值，去重算法对数据序列中重复的0进行编码进一步降低数据长度。
去重算法的主要步骤如下。
（1）设原始数据序列X1，X2，X3，…，Xn。
（2）如果该序列中有一段数据：Xi=Xi+1=…=Xi+N=0，其中N≤15，则将这段数据编码记录为“0N”，表示有N个重复的0，N为十六进制表示的数字。
（3）此时原始数据序列变为：X1，X2，…，0N，…，Xn
（4）重复上述步骤，就可以得到对原数据序列去重处理后的编码。
2.4 数据预处理算法的解压缩过程
在对数据预处理算法得到的原数据文件进行解压缩时，按照程序逆推运行的思想进行处理。首先对压缩数据进行去重算法的解压缩处理，将编码中的“0N”还原为N个连续的0；
随后进行差分压缩算法的解压缩处理，根据标志位进行相邻数据的加和处理，即可得到经数据筛选算法处理后的传感器数据编码。由于去重算法和差分算法均属于无损压缩算法，因此数据可以完整复原；
虽然数据筛选算法部分属于有损压缩，但是删除的数据都是格式化字符和冗余字符，结合压缩过程中同步建立的解压缩协议仍可以完整恢复。最终将压缩后的传感器数据恢复为包含完整测量信息的数据，保证海洋观测数据的完整性。
3.1 数据预处理算法的算法复杂度
算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，衡量一个算法复杂度的标准包括时间复杂度和空间复杂度。算法中程序重复执行的次数T（n）是问题规模n的某个函数，记作T（n）=O（f（n））。一般情况下，主要用算法时间复杂度的数量级评价一个算法的时间性能，算法的时间复杂度越大，算法的执行效率越低。算法的空间复杂度同样是问题规模n的某个函数，记作S（n）=O（f（n））。算法的空间复杂度只考虑运行过程中为局部变量分配的临时空间的大小，空间复杂度越大，运算时需要的内存资源越多。
数据筛选算法涉及数据的解析与重构，该算法会顺序读取原始数据，并按位进行判断与处理，代码运行的次数随数据长度n的变化而变化，数据筛选算法的时间复杂度属于线性阶量级，记为式（6）。
数据筛选算法在进行数据读取和解析的同时会把相关的冗余信息删除，执行期间几乎不需要临时空间，因此，其空间复杂度可以记为式（7）。
数据差分算法的计算过程只涉及加减法，不涉及乘除法等复杂运算，其代码运行的次数随数据长度n的变化而变化，因此，其时间复杂度属于线性阶量级，记为式（8）。
数据差分算法执行期间，需要定义临时存储单元来存放差分运算中的被减数与减数，因此所需的临时空间与数据长度n无关，其空间复杂度属于常数阶量级，记为式（9）。
去重算法首先读取待压缩数据，随后通过判断原始数据序列中重复0的个数来完成压缩，该算法代码的总执行次数随数据长度n的变化而变化，因此，其时间复杂度属于线性阶量级，记为式（10）。
由于去重算法只针对数据中重复的0进行处理，不处理其他数据，因此执行去重算法时所需的临时空间只与待压缩数据中重复0的个数有关，而与数据长度n无关，其空间复杂度属于常数阶量级，记为式（11）。
将式（6）、（8）、（10）加和，即可得到数据预处理算法的时间复杂度，记为式（12）。
将式（7）、（9）、（11）加和，即可得到数据预处理算法的空间复杂度，记为式（13）。
由式（12）、（13）可知，数据预处理算法的时间复杂度为线性阶、空间复杂度为常数阶。对于嵌入式系统的微控制器而言，经过预处理后的数据再利用无损压缩算法进行压缩，既可以降低临时内存资源的占用消耗，又可以减少算法整体的运算量，提升计算速度。
3.2 数据预处理算法的应用效果分析
海洋潜标最常搭载的美国海鸟公司生产的CTD-DO传感器SBE 37-SMP-ODO MicroCAT输出的数据示例如下，参数从左到右分别代表温度、电导率、压力、盐度、声速和时间信息（数据格式见表1）。
在Matlab平台按数据预处理算法的步骤对示例数据依次进行压缩，分析数据预处理算法对传感器原始数据的压缩能力，图3所示为实验结果。
图3 数据预处理算法压缩效果
数据表明：对长度为146 B的传感器原始数据进行数据筛选处理，得到长度为51 B的编码，数据长度压缩为原始数据的35%，这一结果说明数据筛选算法通过删除冗余数据、保留关键数据能够大幅降低原始数据长度。经数据筛选后的编码再通过差分和去重复处理后，得到长度为38 B的编码，数据长度压缩为原始数据的26%，这一结果说明差分算法和去重算法可以进一步压缩数据长度。该实验证明了数据预处理算法可以逐步降低原始数据的数据量，为后续应用其他无损压缩算法更快速、高效地压缩数据打下基础。
选取10组长度不同的SBE 37-SMP-ODO MicroCAT传感器数据，在Matlab平台分别使用动态Huffman算法、LZW算法和Mini-LZO算法对其进行压缩；
随后同样的数据先经过本文设计的数据预处理算法进行处理，再利用上述三种压缩算法进行压缩，对比这两种情况下的压缩表现和压缩率（压缩后的数据长度/原始数据长度×100%[12]）并进行对比，结果如图4至图6所示。
对图4至图6进行分析可知：
图4 动态Huffman算法有无数据预处理的压缩效果对比
图6 Mini-LZO算法有无数据预处理的压缩效果对比
（1）未使用数据预处理算法时，动态Huffman算法对传感器数据的压缩率在45%左右，并没有随原始数据量的增加而发生波动，均保持在相对稳定的状态，最大差值不超过2%；
LZW算法对传感器数据的压缩率在50%~70%范围内，压缩率随原始数据量的增长而小幅下降；
Mini-LZO算法对传感器数据的压缩率在10%~90%范围内，压缩率随原始数据量的增长而大幅下降。数据经预处理后，三种压缩算法中，动态Huffman算法的压缩效果最好。其中，动态Huffman算法对传感器数据的压缩率稳定在6.5%左右，相较于不使用数据预处理算法时的压缩效果提升了86%左右；
LZW算法对传感器数据的压缩率较为稳定，保持在15%左右，相较于不使用数据预处理算法时的压缩效果提升了72%左右；
Mini-LZO算法对传感器数据的压缩率相较于不使用数据预处理算法时改善不明显，但压缩效果仍有小幅度提升，最高提升了约25%。
图5 LZW算法有无数据预处理的压缩效果对比
（2）对动态Huffman算法而言，数据预处理算法有效降低了原始数据的冗余度，在保持原算法稳定性的同时降低了压缩率，提升了压缩效果。对LZW算法而言，单个字符的重复次数随着数据量增大而提升，使得压缩率随着测试数据量的增大而减小最后趋于稳定；
数据预处理算法可以有效降低原始数据冗余度，同时还能将数据转化为由固定字符组成的编码，既提升了LZW算法的压缩效果，又增强了算法的稳定性。Mini-LZO算法需要对数据进行分块压缩，每次压缩都会构建新的字典，相当于丢掉了数据之间的关联性信息，因此压缩率稳定性较差；
数据预处理算法可以基于数据之间的关联性信息进行压缩，从而小幅度提升算法的压缩效率。
Matlab仿真实验结果证明了数据预处理算法的价值，即它可以有效对传感器原始数据进行压缩且适用于多种无损压缩算法。数据经过预处理后，各无损压缩算法的压缩效率和压缩稳定性均有不同程度的提升，有利于增强通信网络在单位时间内的吞吐传输能力，从而提高潜标的无线传输能力。对于同一组观测数据而言，由于数据中包含冗余信息，直接使用压缩算法进行压缩，耗费的工作量大、工作时间长；
数据预处理算法剔除观测数据中的冗余信息后，再利用压缩算法进行压缩，可以减少压缩算法的工作量和计算时间，从而提升了算法的计算速度。
为了验证数据预处理算法应用于其他海洋传感器观测数据压缩是否具备通用性，本文还分别对潜标通常搭载的挪威安德拉公司的单点海流计和德国Franatech公司的METS甲烷传感器的原始数据，使用动态Huffman算法和结合数据预处理的动态Huffman算法进行压缩，压缩结果见表2、表3。
由表2、表3可知，长度为350 B的METS甲烷传感器原始数据经动态Huffman算法压缩后得到的编码长度为164 B，压缩率约为46.85%；
经数据预处理后再使用动态Huffman算法压缩后得到的编码长度为28 B，压缩率约为8%，压缩效果提升了约82.9%。长度为4818 B的单点海流计原始数据经动态Huffman算法压缩后得到的编码长度为2199 B，压缩率约为45.64%；
经数据预处理后再使用动态Huffman算法压缩后得到的编码长度为307 B，压缩率约为6.37%，压缩效果提升了约86%。实验数据表明，针对单点海流计和METS甲烷传感器的原始观测数据，数据预处理算法对无损压缩算法的压缩效果也有明显的提升，具备传感器观测数据的通用性。
表2 METS甲烷传感器数据压缩结果对比
表3 单点海流计数据压缩结果对比
本文根据海洋潜标搭载的海洋传感器所输出的观测数据特点，提出了一种数据预处理算法，通过数据筛选、差分和数据去重，去除原始数据中的冗余信息，完成对传感器数据的预处理。从算法复杂度方面来看：数据预处理算法通过将浮点数运算转换成整数运算、只进行减法运算而不进行乘除运算等操作，降低微控制器的运算量，提升运算速度，而且执行时所需的临时内存资源较少，适用于海洋潜标嵌入式系统。从Matlab仿真试验结果中的压缩率表现来看：结合数据预处理算法，动态Huffman算法对于CTD-DO传感器观测数据的压缩率在所有算法中最低，可达6.5%左右，压缩效率较之前提高了约86%；
LZW算法对于CTD-DO传感器观测数据的压缩率可达15%左右，压缩效率较之前提高了约72%；
Mini-LZO算法对于CTD-DO传感器观测数据的压缩率较之前最多提高了约25%。针对海流计和甲烷传感器数据的压缩实验证明，对于输出以ASCII码表示的数字、英文字符和控制字符为主的海洋传感器数据，数据预处理算法具备通用性。
综上所述，数据预处理算法不仅能够大幅提高无损压缩算法对于常用海洋传感器观测数据的压缩效率，从而有效节省数据存储空间、提高通信网络在单位时间内的吞吐传输能力；
而且有利于提高海洋潜标嵌入式系统的计算速度，降低系统功耗，进而延长潜标系统工作周期，具有广阔的应用前景。
