基于CRC和可逆数字水印的无线传感器网络认证算法

吴海燕　陈　杨　季仲梅

(郑州大学西亚斯国际学院　河南 新郑 451150)



基于CRC和可逆数字水印的无线传感器网络认证算法

吴海燕陈杨*季仲梅

(郑州大学西亚斯国际学院河南 新郑 451150)

摘要针对无线传感器网络中的数据完整性认证问题，提出了一种新的基于循环冗余校验CRC和可逆数字水印的认证算法。算法提出由传感节点负责对数据流进行分组和水印嵌入处理，由汇聚节点实施对收到的数据组进行验证和恢复。为了尽可能减小传感节点的计算复杂度，水印通过计算数据组的CRC码获得，同时，采用基于奇偶不变性的可逆数字水印方法嵌入。算法的安全性由计算CRC码时选取的除数多项式的参数决定，减小了额外的传输代价。实验结果证明了该算法具有较好的认证成功率、较低的传输负载和更高的时间效率，适合于在实时性要求较高的传感器网络中进行数据认证。

关键词无线传感器网络可逆数字水印循环冗余检验认证

0引言

随着物联网技术的飞速发展，无线传感器网络WSNs(WirelessSensorNetworks)已经成为热门研究领域，广泛应用于环境监控、智能家居和远程控制等场景。无线传感器由于其开放性、自组成网、节点资源有限等特点，易受到外界干扰和攻击者恶意攻击，如攻击者篡改节点数据，将错误数据发送给汇聚节点，会使得控制中心做出错误的决策。所以，无线传感器网络的安全问题引起了越来越多的研究者们重视[1-3]。针对传感器网络安全问题的研究主要集中在节点身份认证[4-6]和安全数据融合[7,8]，前者研究节点在接入WSN时的可信身份认证，后者研究对传感器节点采集数据的完整性进行认证和融合，本文重点研究节点数据的完整性认证。

关于WSNs中的数据认证，研究者们提出两种方法：基于加密技术和基于数字水印方法[9]。基于加密方法具有代表性的如文献[10]，提出了一种基于动态密码的传感器网络认证策略，策略具有较高的安全性，并且在安全性和节点可用资源上进行了较好的折中，但策略引入了较大的通信负载。由于传感器节点有限的计算能力、存储空间和能量、加密方法带来的密钥管理、耗时的加解密操作和额外的通信负载，使得并不适合于WSNs。另外一种行之有效的方法是采用数字水印技术进行数据认证[11-14]，基于水印的认证方法将认证信息嵌入在资源有限的传感器节点采集的数据中，水印数据经中间节点传输到汇聚节点，由汇聚节点完成数据认证操作。相比加密技术，数字水印技术计算简单，并且不产生额外的通信负载。但传统的数字水印方法的一个最大弊端就是有损性，也就是说水印的嵌入会对传感器节点数据带来永久的失真，虽然这些失真不会影响如图像等高冗余数字载体的视觉质量，但对于医学和军事等关键应用领域，微小的数据变化都将是不可接受的。因此，研究者们提出利用无损数据水印技术进行数据认证，典型的方法如文献[15]提出了一种基于区域和无损数字水印的图像认证方法，首先将认证区域进行小尺寸的划分，得到每个区域数据的循环冗余检验码CRC作为认证水印，水印嵌入在互不重叠的其他区域中，方法证明了CRC码的计算效率高于Hash函数，减少了水印生成时间。文献[16]提出了一种基于像素对奇偶不变性的无损数字水印方法，方法利用像素对的奇偶不变特性和调整策略嵌入水印，在数据的嵌入和提取上具有计算简单和附加信息少的优点。

Shi等人[3]提出的基于可逆数字水印的认证方法采用数据组的hash认证码作为水印，另外采用基于预测的方法进行无损数字水印嵌入，存在的问题是hash认证码的计算效率偏低，另外基于预测的方法在水印嵌入前，需要引入预测函数对数据组进行计算，增大了计算开销。本文借鉴文献[15]和文献[16]的部分思想，对文献[3]方法进行了改进，采用CRC码代替hash认证码，改用奇偶不变性的嵌入方法实施水印嵌入。提出一种新的基于CRC和可逆数字水印的无线传感器网络认证算法，算法充分考虑对实时性要求较高的无线传感器网络应用场景下的数据认证需求，尽量减少传感节点自身的计算复杂度，提高认证效率。

1基于奇偶不变性的无损数字水印算法

1.1水印嵌入

基于奇偶不变性的无损数字水印算法的基本思想是在一个像素对中嵌入一位水印信息，设原始像素对为(x,y)，嵌入水印后的像素对为(x′,y′)，嵌入的水印位为w，则通过式(1)嵌入水印信息：

(1)

其中，d=x-y，通过式(1)可推导出如下结论：x+y=x′+y′，即嵌入水印前后的像素对的和不变。由d=x-y，将等式两边同时加上2y，推导出d+2y=x+y=x′+y′，由于2y为偶数，所以d与x+y和x′+y′具有相同的奇偶性。设d′=x′-y′，同理可推导出d′与x+y和x′+y′具有相同的奇偶性，d与d′也具有相同的奇偶性。

1.2水印提取与恢复

在提取端，首先计算x′+y′的值，同时也就得到了x+y的值。根据式(1)，计算d′如下：

(2)

(3)

因为x′和y′已知，那么d′和LSB(d′)已知，d′的奇偶性已知，由于d′与d具有相同的奇偶性，那么d的奇偶性确定，在式(3)中，已知d的奇偶性，并且w∈{0,1}，那么可以唯一得到d和w的值，完成水印提取。

在得知d的值后，也就是x-y值确定，同时由于x′和y′已知，也就是x′+y′已知，由于x+y=x′+y′得到x+y的值，当原始像素对的差和和都已知时，可以得到原始像素对的值。

2本文方法介绍

2.1认证模型

图1给出了一个简单的WSNs数据传输模型图，图中主要有三种类型的节点，分别为传感节点，负责采集原始数据；传输节点，仅负责对传感节点的数据经过单跳或多跳传输；汇聚节点，用来接收传输节点传输过来的数据。在本文方法中，传感节点负责水印的产生和嵌入，由于传感节点的计算资源和能量有限，水印的产生和嵌入操作必须尽量简单。汇聚节点作为WSNs的中心节点，具有极大的计算资源和能量，执行水印的提取和认证操作。

图1　WSNs数据传输示意图

设传感节点采集的数据流为S，数据流中的数据元素为Si，其中i∈[1,Max]，Max为数据流中数据元素的最大值。引入分组参数l，l<

图2　认证数据组示意图

2.2水印嵌入

1) 水印生成

根据2.1节中的认证模型，水印为当前数据组元素的CRC码，具体生成方式如下：

(1) 将数据元素Si序列化，如转换成二进制形式BSi，采用多项式表示，如“11011”表示为x4+x3+x1+1；

(2) 引入除数控制参数m，当m确定后，除数多项式取为xm+xm-1+x1+1；

(3) 将BSi左移m-1位作为被除数；

(4) 采用模2除法，求得被除数与除数多项式的m-1位余数作为Si的CRC码；

(5) 水印W为所有数据元素CRC码的异或结果，表示为下式：

W=CRCS1⊕CRCS2⊕…⊕CRCSl

(4)

其中⊕表示异或操作。

2) 嵌入算法

水印嵌入算法的伪码表示如下：

(1)whileS未处理完do

//传感节点记录先前数据值

(3)控制参数m赋初值;

(4)whileS未处理完andi<=ldo

(5)record(Si);

//传感节点记录当前数据值

(6)CRCSi=CRC(si,m);

// 计算Si的CRC码，m作为密钥

(7)CRC=CRC⊕CRCSi;

// 计算当前数据组的CRC码

(8)endwhile

(9)W=CRC;

// 水印为当前数组的CRC码

(10)whileS未处理完andi<=m-1do

//采用1.1节水印嵌入算法嵌入

(12)endwhile

//形成认证数据组进行传输

//清空传感节点记录的先前数据值

(15)endwhile

值得注意的是，为了保证认证码完全嵌入，一般情况下l≥m-1，当此条件不满足时执行重复嵌入确保水印嵌入完整。为了保证水印算法的安全，分组长度l和控制参数m的值作为密码安全传输给水印提取端，也就是汇聚节点。

2.3水印提取与认证

水印提取与认证算法的伪码表示如下：

(1)G1=record(TD);

//汇聚节点获取认证数据

(2)whileG1未处理完andi<=m-1do

//采用1.2节中的水印提取算法提取水印

(4)W=W·Wi;

//·表示拼接操作

(5)si=R(si);

//采用1.2节中的恢复算法还原Si的值

(6)endwhile

//还原后的当前数据值

(8)whileG2未处理完andi<=ldo

(9)CRCSi=CRC(si,m);

//计算Si的CRC码，m解码为密钥

(10)CRC=CRC⊕CRCSi;

//计算当前数据组的CRC码

(11)endwhile

(12)W′=CRC;

//重新计算出的水印信息

(13)if(W==W′)

(14)G1认证通过;

(15)RD=G1;

//记录认证通过后的数据组

(16)else

(17)G1认证未通过;

(18)endif

(19)recordclear(TD);

//清空处理完认证数据组

3方法性能分析

3.1理论分析

1) 空间复杂度

2) 时间复杂度

为了实施认证，传感器网络中的传感节点和汇聚节点会产生必然的计算开销，基于传感节点的计算资源和能量有限，本文方法在水印生成和嵌入上均采用了轻量级的算术和逻辑操作，包括数据流分组、CRC码计算、水印嵌入和提取操作。设数据流的总长度为N，那么数据流分组的时间复杂度是O(N)。CRC码计算复杂度与数据元素参数l和控制参数m直接相关，时间复杂度为O(l×m)。另外，根据2.2节和2.3节介绍的水印嵌入和提取算法的伪码，嵌入时间复杂度为O(l×N)，水印提取和恢复算法的时间复杂度为O(l×m)+O(N)。所以，算法总的时间复杂度为O(l×N)。

3) 检测效率

检测效率通常由正检率或负检率衡量，正检率指正确检测出数据元素是否发生篡改的概率，负检率是指错误检测出数据元素是否发生篡改的概率，包含错误肯定和错误否定，即没有发生篡改误认为有篡改发生和发生了篡改误认为无篡改发生。本文采用负检率衡量算法的检测效率，考虑三种情况下算法的负检率：增加数据元素、删除数据元素和修改数据元素。

(1) 考虑在一个数据组中的增加一个数据元素，增加有可能发生在当前数据组或者先前数据组中，如果数据元素仅发生在一端，则会造成两个组中的数据元素个数不匹配，则会检测出篡改，如果数据元素的增加同时发生在两组中，每一端增加的位置概率是1/(l+1)，假设增加数据元素后产生的CRC码刚好与之前一致，那么发生负检的概率为1/ (l+1)2。

(2) 同上，在一个数据组中删除一个数据元素的位置概率为1/l，发生负检的概率为1/l2。

(3) 修改数据元素更为复杂，仅考虑最简单的情况，仅修改数据组中的一个元素，发生修改位置的概率是1/2l，而发生的概率是1/2，那么修改数据元素发生负检的概率为1/4l。

3.2实验结果与分析

仿真实验环境如下：实验采用OMNET++仿真工具，OMNET++是一个开源的网络仿真平台适用于大型网络的模拟仿真，广泛被学术界使用[17]。图3给出了网络的实验部署图，在100m×100m的正方形区域随机部署传感器节点，节点总数为100(传感节点20个，传输节点79个，汇聚节点1个)。图中白色节点为传感节点，黑色节点为传输节点，中心位置三角形节点为汇聚节点，传感节点每隔固定时间采集当前节点所处位置的温度信息。所有实验结果利用Matlab7.0仿真得到，节点间的通信协议采取简单的RIP路由协议。为了收集平均数值，所有数据为在相同的条件下运行10次的结果。实验中随机对一个认证数据组中的数据进行分别插入、修改和删除操作。

图3　传感器网络部署示意图

图4给出了参数l对算法性能影响，m取4，参数l决定数据组中数据元素的个数，也直接决定了生成的水印。在进行水印生成时，首先将每个数据元素看成一个字节转换成8位二进制，也就是说l=2时，参与CRC计算的被除数为16位。参数l越大，参与CRC计算时的被除数位数越长，计算得到的CRC码越鲁棒，误检率越低，即以更大的概率能正确识别出数据元素是否篡改。从图4中数据可以得出如上结论。

图5给出了参数m对算法性能影响，其中l=4。从图5可以看出，随着参数m的增大，除数多项式位数越长，计算得到的水印位数越长，认证精度越高。在参数l确定情况下，算法的性能与CRC校验码的特性一致，除数多项式越复杂，得到的检验码越鲁棒。但值得注意的是参数m越大，CRC码计算量越大、并且需要重复嵌入的水印位越大，需要在计算开销和鲁棒性上取较好的折中。

图4　参数l对算法负检率的影响图5　参数m对算法负检率的影响

本文方法实质是对文献[3]方法进行改进，为了证明本文方法在计算效率上的优越性，比较了本文方法与文献[3]提出方法在传感节点所需存储空间、额外传输负载和水印嵌入算法时间效率。实验中，设传感器节点存储数据的基本空间是Base字节，认证数据流长度为10 000，本文方法中取l=5，m=4，文献[3]中取m=30。实验结果如表1所示。从表1可以看出，除了在传感节点存储空间上本文方法是文献[3]方法的两倍外，在额外传输负载和水印嵌入时间上具有明显优势。本文方法的额外传输负载仅为两个参数l和m，文献[3]方法也只需要两个Key(计算hash值的密钥)和m参数，但明显参数Key比参数l大得多。另外，文献[3]的水印嵌入时间几乎是本文方法的3倍，原因在于一方面文献[3]需要对数据进行不定长的分组，另外计算hash值和水印嵌入方法均比本文方法复杂。在实时性要求较高的无线传感器网络应用场景，牺牲空间换取时间效率是可行的。

表1　本文方法与文献[3]比较结果

4结语

本文提出了一种基于循环冗余校验码和无损数字水印的无线传感器网络认证算法，算法利用循环冗余校验计算方法得到传感器节点采集的原始数据的CRC码作为水印信息，然后利用基于奇偶不变性的无损数字水印方法将水印嵌入数据组中。算法改进了传统基于可逆水印认证方法的水印生成方法和嵌入方法，简化了计算复杂度，提高了认证效率。实验结果表明，本文算法具有较高的认证效率。另外，与相似方法的比较证明了本文方法在时间效率上的优势。该方法可用于在无线传感器网络中进行有效数据认证，减少数据在传输过程中受到篡改几率，提高无线传感器网络可靠性，具有较好的应用前景。

参考文献

[1] 范永健,陈红,张晓莹,等.无线传感器网络中隐私保护通用近似查询协议[J].计算机学报,2014,37(4):915-926.

[2]LiHJ,LiKQ,QuWY,etal.SecureandEnergy-efficientdataAggregationwithMaliciousAggregatorIdentificationinWirelessSensorNetworks[J].FutureGenerationComputerSystems,2014,37(1):108-116.

[3]ShiX,XiaoD.AReversibleWatermarkingAuthenticationSchemeforWirelessSensorNetworks[J].InformationSciences,2013,240(10):173-183.

[4]ShimKA,LeeYR,ParkCM.EIBAS:Anefficientidentity-basedbroadcastauthenticationschemeinwirelesssensornetworks[J].AdHocNetworks,2013,11(1):182-189.

[5] 黄海平,谭志刚,王汝传,等.采用投票机制的移动传感节点广播认证方案[J].北京邮电大学学报,2013,54(1):110-114.

[6]FanXX,GongG.AcceleratingSignature-basedBroadcastAuthenticationforWirelessSensorNetworks[J].AdHocNetworks,2012,10(4):723-736.

[7] 杨文文,马春光,黄予洛.基于分布式认证的完整性保护数据融合方案[J].计算机应用,2014,34(3):714-719.

[8] 曹晓梅,沈何阳.基于模式码比较的数据融合和认证协议[J].传感技术学报,2013,26(1):100-104.

[9]JrMA,OliveiraBT,MargiCB,etal.SurveyandComparisonofMessageAuthenticationSolutionsonWirelessSensorNetworks[J].AdHocNetworks,2013,11(3):1221-1236.

[10]DasAK,SharmaP,ChatterjeeS,etal.ADynamicPassword-basedUserAuthenticationSchemeforHierarchicalWirelessSensorNetworks[J].JournalofNetworkandComputerApplications,2012,35(5):1646-1656.

[11]ZhangW,LiuYH,DasSK,etal.SecureDataAggregationinWirelessSensorNetworks:aWatermarkbasedAuthenticationSupportiveApproach[J].PervasiveandMobileComputing,2008,4(5):658-680.

[12]GuoHP,LiYJ,JajodiaS.ChainingWatermarksforDetectingMaliciousModificationstoStreamingData[J].InformationSciences,2007,177(1):281-298.

[13]KamelI,GumaH.SimplifiedWatermarkingSchemeforSensorNetworks[J].InternationalJournalofInternetProtocolTechnology,2010,5(1):101-111.

[14]KamelI,GumaH.ALightweightDataIntegrityschemeforsensornetworks[J].Sensors,2011,11(4):4118-4136.

[15]GuoXT,ZhuangTG.ARegion-basedLosslessWatermarkingSchemeforEnhancingSecurityofMedicalData[J].JournalofDigitalImaging,2009,22(1):53-64.

[16]WengSW,ZhaoY,PanJS,etal.ReversibleWatermarkingBasedonInvariabilityandAdjustmentonPixelsPairs[J].IEEESignalProcessingLetters,2008,15(1):721-724.

[17]LouW,KwonY.H-Spread:ahybridmultipathschemeforsecureandreliabledatacollectioninwirelesssensornetworks[J].IEEETransactionsonVehicularTechnology,2006,55(4):1320-1330.

WIRELESS SENSOR NETWORKS AUTHENTICATION ALGORITHM BASED ONCRCANDREVERSIBLEDIGITALWATERMARKING

Wu HaiyanChen Yang*Ji Zhongmei

(SIAS International University,Zhengzhou University,Xinzheng 451150,Henan,China)

AbstractIn order to solve the data integrity authentication in wireless sensor networks, we presented a novel authentication algorithm which is based on cyclical redundancy check (CRC) technique and reversible watermarking. In the presented algorithm, the sensor node is in charge of the dataflow grouping and watermark embedding operation, and the sink node is responsible for the authentication and recovery of the received data group. In order to reduce the computation complexity of sensor nodes as much as possible, the watermark is generated by calculating the data group’s CRC code, and at the same time it is embedded by an odd-even invariability-based reversible digital watermarking method. The security of the algorithm is determined by the parameter of divisor polynomial selected when computing CRC code, this lowers the extra transmission overhead. Experimental results prove that the proposed algorithm has good authentication success rate, lower transmitting overhead and higher time efficiency. The presented algorithm is compatible to carrying out data authentication for WSNs with high real-time requirement.

KeywordsWireless sensor networksReversible digital watermarkingCyclical redundancy checkAuthentication

收稿日期：2015-01-22。国家自然科学基金项目(61272494)；河南省科技厅科技攻关项目(122102210570，152102310367)；河南省科技厅基础与前沿技术研究项目(122300410424)。吴海燕，讲师，主研领域：嵌入式系统。陈杨，讲师。季仲梅，教授。

中图分类号TP393

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.070