引用本文
曲建峰, 陈进, 李鲍, 陈嘉懿. 超高频RFID标签压缩算法的实现与应用研究* ——以条码压缩为例. 现代图书情报技术, 2013, 29(3): 83-88
Qu Jianfeng, Chen Jin, Li Bao, Chen Jiayi. Implementation and Application of UHF-RFID Compression Algorithm——Based on Barcode Compression. New Technology of Library and Information Service, 2013, 29(3): 83-88  
Permissions
超高频RFID标签压缩算法的实现与应用研究*——以条码压缩为例
曲建峰, 陈进, 李鲍, 陈嘉懿
上海交通大学图书馆 上海 200240
修回日期:2013-03-14
基金:本文系上海交通大学文理交叉项目“基于RFID技术的智慧型图书馆服务研究”(项目编号:11JCY07)的研究成果之一。
摘要
现阶段市场上超高频RFID标签的存储容量有限,因此对存入标签中的信息必须进行压缩。然而目前国内还没有统一的压缩算法标准。针对该问题,以标签存储中最常用的图书馆馆藏条码为例,研制在不同的条码长度与字符情况下存储在超高频RFID标签中的压缩方法和不同情况下所应当采用的算法原理与数据结构,并将该方法应用于不同的厂家进行测试,真正实现互相间无障碍的读写。
关键词: 超高频RFID; 数据模型; 压缩算法
Implementation and Application of UHF-RFID Compression Algorithm——Based on Barcode Compression
Qu Jianfeng, Chen Jin, Li Bao, Chen Jiayi
Shanghai Jiaotong University Library, Shanghai 200240, China
Abstract
Since the storage of UHF-RFID label is limited, the information stored in the label has to be compressed. However, there is not a uniform compression algorithm in China. Focused on the kinds of barcode length and character, the compression algorithm principle and data structure are developed. This method is tested in some customers,and accessible read-write among customers is realized.
Keyword: UHF-RFID; Data model; Compression algorithm
1 引 言

近年来,图书馆提供的物质资源越来越丰富,实体馆藏量也越来越大,为了方便读者应用实体馆藏资源,许多图书馆开始研究使用先进的RFID技术来实现实体馆藏的智能化管理,如厦门市图书馆、华东理工大学图书馆等。图书馆按照自身侧重点的不同选择高频RFID标签或超高频RFID标签。随着超高频RFID标签(UHF-RFID)技术的飞速发展,由于其具有体积小、成本低、识别距离长、读取速度快等优点,相比高频标签其更符合图书馆对图书标签的需求,因此随着超高频RFID标签技术的成熟,选择超高频RFID标签的图书馆呈逐年上升的趋势[ 1]。通过对市场上超高频RFID芯片供应商ALIEN[ 2]、NXP[ 3]、 IMPINJ[ 4]、 Quanray[ 5]目前投入应用的产品调研发现:超高频RFID标签的用户可用的数据区容量通常比较小(一般为96bit-496bit), 无法存放在国际标准ISO28560-1[ 6, 7]
所定义的所有数据元素(该标准主要针对高频RFID标签制定),而实际应用中需要存储至标签中的内容很多,如物品唯一标识符、安全位等,因此必须对存放在标签中的信息进行压缩。由于超高频RFID标签的国际通用标准尚未完全建立[ 8],超高频RFID标签供应商都是采用自定义的压缩算法来实现标签中所需数据的存储,压缩算法都不一致,而且对外保密,给用户的选择与使用带来不利。

(1)各个供应商的超高频RFID硬件设备不可通用,在购买设备时只能持续购买同一家的产品,如复旦大学、厦门大学等图书馆所有的RFID相关设备都只使用一家的产品。

(2)无法实现各图书馆间RFID图书的馆际互借工作[ 9]。如果各个供应商可以统一压缩算法,那么只要通过读取存储在超高频RFID标签中的内容就可以实现各个供应商的硬件设备的通用以及实现图书馆际互借的功能。

因此本文以目前必须存储在标签中的馆藏唯一标识符——图书条码为例,通过对大多数图书馆条码编码方式和超高频RFID标签存储容量的调研确定了三种条码的压缩算法,并实现了其编码方式。

2 压缩算法的应用分析
2.1 压缩算法的原理

压缩算法包含可逆压缩和不可逆压缩[ 10]。对于存储在超高频RFID标签中的数据必须应用可逆压缩算法,这类压缩算法已经在航天、通信、医疗等领域应用较为普遍。典型的可逆压缩算法很多,如:算术编码、哈夫曼(Huffman)编码等。在ISO/IEC 15962中提到的算法有:整形数压缩、数字压缩、5-bit压缩、6-bit压缩等。本文用到的压缩算法有数字压缩和6-bit压缩。数字压缩用于编码任何十进制数字字符串,含以‘0’开头的字符串,字符串的长度可以是2个或2个以上,所有编码的字节值在‘0’(30HEX)到‘9’(39HEX)之间;6-bit压缩用于编码大写拉丁字母、数字及一些标点符号,所编码的字符值在20HEX到5FHEX之间,字符串的长度应在4个或4个以上,用这种压缩模式,可节省25%以上的存储空间[ 11, 12]。

2.2 条码的分析

通过对多家图书馆所应用的条码编码方式的调研分析,可知:条形码使用的码制是三九条形码(简称Code39码)。Code 39码表示的资料内容,包括A-Z大写英文字母,0-9数字,以及一些特殊符号,即编码可选字符集为ISO/IEC 646 IRV[ 13]中的任意字符。Code 39码除结束符的最后一位是校验位,它由公式计算而得,可打印也可不打印。各家图书馆在实际应用时,有选择不打印校验位的,也有选择打印校验位的,因此各图书馆或采用“字母+数字”或采用“字母+数字+校验位”的方式构成本馆条码,其中字母部分大多数为大写字母1-3位(本文均为十进制字符串的长度),极个别图书馆使用的字母数量更多或者字母所在位置不确定且有小写字母。条码的长度多为5位、7位、8位、14位等,目前所调研到的条码最长的为14位。

2.3 超高频RFID标签存储容量的分析

从逻辑上说,一个UHF-RFID电子标签有4个存储体[ 14, 15],用户在实际应用中可使用的是EPC存储体和用户存储体。鉴于EPC存储体的读写速度较快,而用户存储体的读写速度慢,因此一般常用信息都放置在EPC存储体中,本文研究的条码就存放于EPC存储体中。目前市场上的UHF-RFID标签的EPC存储体可写入的数据容量大多数为96bit或128bit,也有256bit等容量的产品。随着UHF-RFID技术的发展以及应用的深入,大容量EPC存储体的UHF-RFID标签陆续出现,可见到的最高容量是496bit EPC存储体。但是,从成本和当前读写技术的可靠性等因素考虑,大多数图书馆选择小容量EPC存储体的UHF-RFID标签。因此本文以96bit、128bit以及144bit以上的EPC存储容量作为研究对象,来设计存储其中的条码压缩算法。

2.4 条码压缩算法的分析

根据图书馆所应用的条码和UHF-RFID标签存储容量的分析,在应用不同长度和不同编码方式的条码时,对EPC的存储容量也会有不同的要求。由于在EPC区中除了存储作为馆藏唯一标识符的馆藏条码外,还必须存储一些其他字段,如:安全位、索引字段、分拣信息、压缩方式等。因此EPC区在存储馆藏条码后,还必须剩余至少30bit来存储其他信息。

由于各标签的EPC数据区容量并不相同,而且所能容纳的数据元素长度也很有限,因此针对不同的EPC容量,并结合不同馆藏条码的组成方式,制定了三种编码方式,它们在编码时都保留低4bit来保存条码长度。

(1)编码方式1:标签的EPC容量为96bit ,适用于馆藏标识符总长度为1-14位字符,但长度为8位以上的条码仅有前3位可以出现大写字母,14位条码将压缩至64bit。

(2)编码方式2:标签的EPC容量为128bit,适用于馆藏标识符总长度为1-14位字符,但长度为12位以上的条码如有小写字母需转换为大写字母(除最后1位),14位条码压缩至96bit。

(3)编码方式3:标签的EPC容量为144bit或以上,适用于馆藏标识符总长度不大于14个字符,可选字符集为ISO/IEC 646 IRV中的任意字符。

3 压缩算法的具体实现

鉴于之前调研得出的结果:图书馆大多采用条形码作为馆藏标识符,其长度范围在5-14位字符(字母+数字组成)范围之内,本文研究的编码与解码算法适用于总长度为1-14位字符条形码(馆藏唯一标识符)的情况,并利用C语言[ 16]来实现具体的压缩算法。由于编码方式3不压缩,因此本文只介绍编码方式1和编码方式2的压缩算法的实现。编码的具体实现思路是根据条码中所出现的字符类型、条码长度和EPC存储体的容量,来决定所采用的压缩算法。编码的变量定义为:

inti, iBarCodeLen;

unsigned char ucCompressedBarCode[4], ucTmpChar;

unsigned char *pucTmpDat;

union

{

unsigned char ucStr[4];

unsigned int uiDat;

} unWorkDat;

其中,i为计数器,iBarCodeLen为条码长度,ucCompressedBarCode为压缩后的字符串,ucTmpChar为存放字符串的临时变量,pucTmpDat为临时指针变量,unWorkDat为存放原始字符串数据的共同体。

3.1 编码方式1

编码方式1可分为条码长度为1-7和条码长度为8-14的两种不同的压缩方式,因此在编码时可根据条码长度分成两部分来进行编码。

(1)当条码长度为1-7:可选字符集为ISO/IEC 646 IRV中的任意字符,由于存储区域的长度够用,因此不压缩。其存储方式如表1所示:《、平》
(2)当条码长度为8-14:第1至3位字符的可选字符集为A-Z(大写)字母或0-9数字(如有小写字母需转换为大写再传入),使用6-bit压缩;第4至倒数第2位的可选字符集为0-9数字,使用数字压缩;最后1位(常被用作校验位)的可选字符集为ISO/IEC646IRV中的任意字符,不压缩。编码后数据的统一长度为8字节。当条码总长度小于7位字符时,编码后数据长度为不定值,不足部分的高位字节可用任意数值补齐8字节。其存储方式如表2所示:

表1 条码长度为1-7

表2 条码长度为8-14

在编码过程中,需要注意的是由于各图书馆条码的长度不一,在存储后所得到的编码长度就不一样,因此必须将条码长度放在低4位,即最后放入编码字段中,否则位置不固定,给解码带来不便,其关键代码为:

ucTmpChar = ucBarCode[iBarCodeLen - 1]; // 临时存放BarCode校验位.

ucBarCode[iBarCodeLen - 1] = 0; // 校验位清零.

pucTmpDat = ucBarCode[4]; // 处理压缩后的高4字节.

// 采用数字压缩从第5位起除最后1位的2-9位数字.

unWorkDat.uiDat = atoi( (char *)pucTmpDat);

unWorkDat.uiDat <<= 2;

// 将BarCode的第4位数字压缩后的高2bit存入.

unWorkDat.uiDat |= ( ( (unsigned int)ucBarCode[3] - 0x30) 0x0C) >> 2;

for(i=0; i<4; ++i) // 临时保存压缩后的高4字节.

{.

ucCompressedBarCode[i] = unWorkDat.ucStr[i];

}.

//处理压缩后的低4字节.

// 压缩第4位数字压缩后的低2bit存入.

unWorkDat.uiDat = ( (unsigned int)ucBarCode[3] - 0x30) 0x03 ;

// 采用6-bit压缩最前面3位字母或数字.

unWorkDat.uiDat = (unWorkDat.uiDat << 6) | ((unsigned int)ucBarCode[0] - 0x30);

unWorkDat.uiDat = (unWorkDat.uiDat << 6) | ((unsigned int)ucBarCode[1] - 0x30);

unWorkDat.uiDat = (unWorkDat.uiDat << 6) | ((unsigned int)ucBarCode[2] - 0x30);

// 压缩BarCode最后1位字符,通常为校验码.

unWorkDat.uiDat = (unWorkDat.uiDat << 8) | ((unsigned int)ucTmpChar);

// 记录原BarCode编码长度.

unWorkDat.uiDat = (unWorkDat.uiDat << 4) | (unsigned int)iBarCodeLen;

// 构成输出压缩后的BarCode.

for(i=0; i <4; ++i).

{.

ucBarCode[i] = unWorkDat.ucStr[i];

ucBarCode[i + 4] = ucCompressedBarCode[i];

}.

3.2 编码方式2

编码方式2可分为条码长度为1-11和条码长度为12-14的两种不同的压缩方式。

(1)当条码长度为1-11:可选字符集为ISO/IEC 646 IRV中的任意字符,所有字符都不进行压缩,其存储方式如表3所示:

表3 条码长度为1-11
(2)当条码长度为12-14:第1至倒数第2位的可选字符集为A-Z字母或0-9数字(如有小写字母需转换为大写再传入),使用6-bit压缩;最后1位的可选字符集为ISO/IEC 646 IRV中的任意字符,不压缩。编码后数据的统一长度为12字节。当条码总长度小于11位字符时,编码后数据长度为不定值,不足部分的高位字节可用任意数值补齐12字节,其存储方式如表4所示。
表4 条码长度为12-14
.
4 算法应用的测试效果分析

HKC、远望谷、科晶、艾迪讯、阿法迪共5家厂商参与了这次算法测试的工作。首先根据三种编码方式分别给出统一的取值样例,如编码方式1(96bit)的馆藏条码为“ABC0123456789?”,按照其对应的压缩算法存储后的十六进制值是“FE33491154346F1DHEX”;编码方式2(128bit)的馆藏条码为“ABCDEFGHIJKLM)”,按照其对应的压缩算法存储后的十六进制值是“9ED2711B5A865D1615354911HEX” ;编码方式3(144bit及以上)的馆藏条码为“ZZZZZZZZZZ?*_)”,按照其对应的压缩算法存储后的十六进制值是“5A5A5A5A5A5A5A5A5A5A3F2A5F29HEX”。然后各个厂商都应用这个压缩算法将馆藏条码利用自己的读写器写入自己标签上的用户数据区(EPC区),并使用读取设备读取标签中的数据,完成以下检测:

(1)检查各厂商写入的标签信息是否一致;

(2)写入后生成的字符串是否一致;

(3)不同厂商的标签使用其他厂商的硬件设备互相读取标签是否能够正确解析。

5家厂商按照取值样例进行标签写入工作后,经测试各厂商写入的字符串信息均一致;写入后生成的字符串信息也是一致的;各厂商写入的标签在其他厂商的工作站等设备上均能解析出正确信息。通过以上的测试可判断5家厂商只要存入标签中的内容压缩算法和字段格式一致,就可以实现标签与硬件设备的相互兼容。

5 结 语

通过对国内图书馆所应用馆藏条码编码方式的分析,结合目前市场所普遍应用的UHF-RFID标签的EPC存储体的容量,本文描述了三种条码压缩方式,涵盖目前国内大多数图书馆所采用的条码编码方式。在实际应用中,建议尽量采用紧凑的编码方式。例如:

(1)当条码最多前3位可能出现大写字母时,可采用编码方式1;

(2)当条码各位均有可能出现大写字母时,可采用编码方式2;

(3)当条码各位均有可能出现ISO/IEC 646 IRV所定义的任意字符时(例如,14位字符中具有可能出现小写字母或特殊字符的情况),无法使用统一的压缩方式,因此只能采用编码方式3,即不压缩。

笔者希望通过该研究能对统一目前各个UHF-RFID供应商混乱的编码方式起到抛砖引玉的作用,从而达到UHF-RFID供应商的标签与设备可以通用的目的,并实现应用UHF-RFID的图书馆可以完成馆际互借等互操作功能,从而真正实现智能化的大流通。

参考文献
[1] 刘绍荣, 杜也力, 张丽娟. RFID在图书馆使用现状分析[J]. 大学图书馆学报, 2011, 29（1）: 85-88. （Liu Shaorong, Du Yeli, Zhang Lijuan. The Analysis of the Implementation of RFID Technology in Library[J]. Journal of Academic Libraries, 2011, 29（1）: 85-88. ） [本文引用:1] [CJCR: 3.739]
[2] RFID IC[EB/OL]. [2013-03-01]. http://www.alientechnology.com/ic [本文引用:1]
[3] A Complete Range of ICs for Smart Cards, Tags, Labels and Readers [EB/OL]. [2013-03-01]. http://www.cn.nxp.com/products/identification_and_security/. [本文引用:1]
[4] Monza X UHF RFID Chips[EB/OL]. [2013-03-01]. http://www.impinj.com/Monza_X_RFID_Chips.aspx. [本文引用:1]
[5] 产品中心-超高频-芯片[EB/OL]. [2013-03-01]. http://www.quanray.com/product_class.asp?ParentID=149OwnId=154.(Product-UHF-Chips[EB/OL].[2013-03-01]. http://www.quanray.com/product_class.asp?ParentID=149OwnId=154. [本文引用:1]
[6] ISO 28560-1, 第1部分: 数据元素与实施总则[S]. 2011. ( ISO 28560-1, The First Part: The Data Elements and the Implementation of General Principles[S]. 2011. ) [本文引用:1]
[7] ISO 28560-2, 第2部分: 基于ISO/IEC 15962规则编码RFID数据元素[S]. 2011. ( ISO 28560-2, The Second Part: The ISO/IEC 15962 Encoding Rules Based on RFID Data Elements[S]. 2011. ) [本文引用:1]
[8] 董曦京, 孙一钢, 孙卫, 等. 中国图书馆RFID应用标准化方案研究[J]. 现代图书情报技术, 2008（9）: 21-29. （Dong Xijing, Sun Yigang, Sun Wei, et al. Study on the Stand ardization Proposal of China Library RFID Application[J]. New Technology of Library and Information Service, 2008（9）: 21-29. ） [本文引用:1] [CJCR: 1.073]
[9] 景祥祜, 蔡孟欣, 戴淑儿, 等. 图书馆导入RFID的标准与互操作探讨——以香港高校图书馆为例[J]. 大学图书馆学报, 2009, 27（6）: 32-38. （Jing Xianghu, Cai Mengxin, Dai Shuer, et al. RFID Stand ards for Library Applications and Interoperability: Taking Hong Kong Academic Libraries as the Example[J]. Journal of Academic Libraries, 2009, 27（6）: 32-38. ） [本文引用:1]
[10] 苏仕华. 数据结构与算法解析[M]. 合肥: 中国科学技术大学出版社, 2004. (Su Shihua. Data Structure and Algorithm Analysis[M]. Hefei: University of Science Technology of China Press, 2004. ) [本文引用:1]
[11] ISO/IEC 15962, 信息技术-项目管理用射频识别(RFID). 数据协议: 数据编码规则和逻辑存储功能[S]. (ISO/IEC 15962, Information Technology-Project Management for Radio Frequency Identification(RFID). Data Protocol: Data Encoding Rules and Logical Storage Function[S]. ) [本文引用:1]
[12] WH/T 44-2012, 中华人民共和国文化行业标准, 图书馆-射频识别-数据模型-第2部分: 基于ISO/IEC 15962的数据元素编码方案[S]. (WH/T 44-2012, Cultural Industry Stand ard of the People’s Republic of China, Library-RFID-Data Model-The Second Part: The Data Elements Coding Scheme Based on ISO/IEC 15962[S]. ) [本文引用:1]
[13] ISO/IEC 646 IRV, 信息技术: ISO信息交换七位编码字符集[S]. (ISO/IEC 646 IRV, Information Technology: Seven-Bit Coded Character Set ISO Information Exchange[S]. ) [本文引用:1]
[14] ISO 18000-6C, 射频识别协议-第1类第2代UHF-RFID 860兆赫-960兆赫通讯协议[S]. (ISO 18000-6C, Radio Frequency Identification Protocol-First Kinds of Second Generations UHF-RFID 860MH-960MH Protocol[S]. ) [本文引用:1]
[15] EPC G2 UHF中文说明书[EB/OL]. [2013-03-11]. http://www.3rfid.com.(EPCG2UHFChineseDescription[EB/OL].[2013-03-11].http://www.3rfid.com. [本文引用:1]
[16] 陈进. 科学与工程计算常用算法程序库C语言版[M]. 上海: 上海交通大学出版社, 1995. (Chen Jin. Commonly Used Algorithm Library C Language Version of Computational Science and Engineering [M]. Shanghai: Shanghai Jiaotong University Press, 1995. ) [本文引用:1]