2014, Vol. 25
2. 安徽师范大学 数学计算机科学学院, 安徽 芜湖 241003
2. College of Mathematics and Computer Science, Anhui Normal University, Wuhu 241003, China
无线传感器网络(wireless sensor networks,简称WSNs)是由大量部署在物理世界的传感节点通过无线通信方式形成的多跳自组织网络系统,在环境监控、医疗卫生、智能交通和国防等领域具有广泛的应用[1,2].传感节点一般具有能量、计算和存储等资源受限特征,特别是由电池供电,且难以更换,因此,节省能耗、延长网络使用寿命是WSNs研究所面临的重要挑战.WSNs一般通过数据聚集[3,4,5,6,7]减少通信量以节省能耗.然而在很多应用中,WSNs面临严重的隐私泄漏问题,例如在医疗卫生领域,监控病人的健康信息被恶意窥探等.如何保证感知数据的隐私性,是拓展WSNs应用领域的关键因素,是WSNs研究中的一个热点问题.
现有的隐私保护数据聚集算法一般基于某种网络拓扑结构(树或簇)实现聚集请求和数据聚集,由于传感节点的易损耗性,且易受周围环境的影响,节点容易发生失效、移动等情况,使得WSNs结构频繁发生变化,导致维护网络拓扑结构的代价太大.文献[8]提出了一种结构无关的基于路线的算法IWQE,能够有效地减少网络拓扑结构维护能耗,降低网络拓扑变化带来的影响,但IWQE没有考虑感知数据的隐私性.此外,已有算法主要通过加密来保证感知数据的隐私性,但过多的加/解密操作将造成严重的延迟和能量消耗.文献[9]提出了一种新的隐私保护的加聚集算法,其主要思想是:Sink与每个节点共享一个随机数(密钥),每个节点将随机数加到自身感知数据上,其余操作与基本的数据聚集算法一致,Sink通过减去与所有节点共享的随机数得到真实的聚集结果.虽然算法不需要进行加/解密操作,但部分节点由于通道冲突没有完成数据传输,而Sink又很难追踪到这些节点,因此,该算法的聚集结果可能由于减去多余的随机数而产生较大的偏差.
针对这些问题,本文提出一种安全而高效的空间数据聚集算法SESDA(secure and energy-efficient spatial data aggregation algorithm).SESDA在安全链接邻居节点之间建立安全通道(共享随机数),所有数据通过安全通道传输,因此数据不需要加/解密,节省了大量计算能耗.另外,根据聚集区域设定好理想路线,从起始聚集节点出发,广播聚集请求,聚集数据节点的感知数据,并将部分聚集结果沿着理想路线传给下一个聚集节点.如此继续,直到聚集区域的最后一个聚集节点,得到最终的聚集结果并传给Sink.由于在聚集过程中聚集节点是实时确定,且与网络拓扑结构无关,因此节省了网络拓扑结构维护能耗.聚集节点的部分聚集结果是由多个节点的感知数据构成,所以下一个聚集节点只能获得该部分聚集结果,而不能推导出任何节点的数据.同时,为了防止聚集节点获取数据节点感知数据,采用类似He等人[10]提出的切分-重组技术对感知数据进行切分操作,即,将数据分成J片,自身保留1片,其余的J-1片传输给J-1个安全链接邻居节点,保证感知数据的隐私性.SESDA只对数据节点进行切分,且在聚集过程中无任何加/解密操作,因此与SMART相比,SESDA不仅能够降低通信量,而且能够节省更多的能耗.同时,SESDA降低了数据传输发生冲突的几率,且不存在Sink减去失效节点的随机数情况,所以SESDA聚集结果的精确度较高.另外,SESDA与网络拓扑结构无关,节点之间不需要提前部署共有信息,使得网络具有良好的扩展性.理论分析和实验结果显示,该方案在安全性、能耗、精确度和扩展性方面都取得了较好的结果.
本文第1节介绍相关工作.第2节给出攻击模式、目标等预备知识.第3节详细描述本文提出的SESDA算法,分析其安全性、通信量和能耗等性能.第4节对路线失效和网络扩展性进行分析.第5节对SESDA算法进行模拟实验及分析.第6节对全文进行总结.
1 相关工作数据聚集的思想是聚集不同节点的感知数据,消除数据冗余,减少通信量,从而节省能耗延长网络生命周期.现有隐私保护的数据聚集算法主要有基于树或簇的网络拓扑结构.
基于树的隐私保护数据聚集算法是指将网络中的节点构造成一棵以Sink为根节点的树,节点将数据加密或扰乱后传输给其父节点,父节点对数据进行聚集,并将聚集结果传输给其父节点.如此继续,直至Sink,得到最终的聚集结果.文献[11]提出的SDAP算法采用分而治之的思想实现安全的数据聚集,即SDAP将拓扑树动态地划分成多个尺寸类似的子树(逻辑群),每个子树内执行逐跳的数据聚集.EEHA[12]算法与SMART算法类似,但EEHA只对叶子节点进行切分处理,使得EEHA算法具有更高的效率和精确度.
基于簇的隐私保护数据聚集算法是将网络分成若干个簇,节点将感知数据传给簇头节点,簇头对簇内数据进行聚集,再将聚集结果传给Sink.文献[10]提出的CPDA算法通过在数据中添加随机种子和随机数来隐藏真实数据,簇头节点利用多项式的代数性质求解出加聚集结果.文献[13]提出的IPHCDA算法采用基于椭圆曲线的同态加密模式实现隐私保护的数据聚集,将网络分成若干个区域,不同区域使用不同的公钥对数据进行加密,聚集节点对密文进行聚集,并将聚集结果传至基站,基站对数据进行解密.
由于WSNs结构变化频繁,为了保证聚集结果的正确性,基于树或簇的聚集算法需要维护网络的拓扑结构,因而产生大量的能耗.文献[8]提出了一种与网络拓扑结构无关的基于路线的数据聚集算法IWQE.该算法沿1条或多条动态生成的聚集路线聚集区域内节点的感知数据.如图 1所示,IWQE包括3个步骤:
 | Fig. 1 Itinerary route图 1 路线路由 |
(1) 利用位置路由协议[14],Sink将聚集请求传到聚集区域内的某个节点(起始聚集节点A1).
(2) 从该聚集节点开始,利用基于路线的聚集算法聚集区域内节点的感知数据,然后沿着理想路线(ideal itinerary)确定下一个聚集节点,并将聚集结果传输给该聚集节点.如此继续,直到聚集完区域内所有节点.
(3) 利用位置路由协议将聚集结果传回给Sink.文献[8]证明:当路线的宽度不超过节点通信半径的
/2倍时,能够保证聚集到区域内所有节点的感知数据.
WSNs在数据聚集过程中,沿着理想路线动态地确定聚集节点,其余节点为数据节点.典型的聚集函数包括加、平均值、计数、最大/小值等.本文只讨论加聚集,因为其他聚集函数都可以转化为加聚集函数[9].
2.1 攻击模式攻击者有以下攻击方式:
(1) 窃听攻击.由于WSNs采用无线通信,攻击者通过链路层窃听获取隐私数据.窃听攻击是WSNs最常见和容易发动的攻击,是本文研究的重点,本文假设攻击者能够窃听整个网络通信.
(2) 捕获传感节点.攻击者能够捕获1个或多个节点,获取节点中所有数据和密钥:一方面试图用获得的密钥对窃听到的数据进行解密以获取其他节点的感知数据,破坏数据的隐私性;另一方面,多个被捕获的节点串谋推测其相邻节点的感知数据.
2.2 设计目标隐私保护数据聚集算法的主要目标是保证节点感知数据的私有性,此外,算法还必须考虑能耗、聚集结果的精确性和网络的扩展性等特性.因此,好的隐私保护数据聚集算法应满足下列标准:
(1) 隐私性:保证节点感知数据的隐私性是很多WSNs应用领域的关键问题.算法应能保证数据的隐私性,使得节点只知自身感知数据.因此,一种好的隐私保护数据聚集算法能够防窃听攻击和串谋攻击.
(2) 能耗:为了保证数据的隐私性,数据聚集算法额外增加了通信和能量开销.因此,一个好的隐私保护数据聚集算法在保证数据隐私性的情况下,其额外增加的开销应尽可能地小.
(3) 精确性:聚集结果可能是做决策的关键因素,因此,保证聚集结果的精确非常重要.所以,聚集结果的精确性是隐私保护数据聚集算法的评价标准之一.
(4) 扩展性:传感节点低廉、易失效等特点,使得WSNs拓扑具有动态性.当网络产生失效节点、部署新节点或节点移动时,隐私保护的数据聚集算法应仍能继续正确执行,即算法应具有良好的扩展性.
2.3 密钥分配邻居节点之间安全通道的建立需要通过数据加密实现,密钥管理采用文献[15]中提出的随机密钥分配方法.该方法主要包括密钥预分配和邻居节点共享密钥链路建立.若两节点共享的密钥到期则进行密钥更新,则两节点移除该到期密钥,并重新建立邻居节点共享密钥链路.在建立过程中,节点不需要向其他节点广播任何信息,因此,密钥更新简单,对其他节点没有影响.
采用随机密钥分配方法,任意两邻居节点至少有1个相同密钥的概率为pconnect.当两个邻居节点通过相同的密钥进行通信时,第三方节点拥有该密钥的概率为poverhear.具体为[15]
类似于文献[8,16]的假设,所有节点维护其安全链接邻居节点(secure link neighbor,简称SLN)的位置信息,其中,安全链接指的是节点之间至少共享1个密钥.所有节点传输半径均为R,每个节点的SLN节点列表的平均大小为NS.节点传输和接收1bit的能耗分别为eT和eR.网络建立安全通道的能耗为Esc,聚集查询用AWQ(aw)表示,其中,aw表示矩形聚集区域,聚集区域内的节点数为N,处理聚集查询的总能耗为Etotal=Es+Ea+Eb,其中,Es表示将聚集请求发送到聚集区域内某个节点能耗,Ea表示在聚集区域内发送聚集请求、切片传输和聚集数据的能耗,Eb表示将最终的聚集结果返回给Sink的能耗.节点S1和S2之间的距离为fdist(S1,S2),感知数据范围为[0,...,Rd].本文假设在聚集时间周期T内进行快照聚集,同时假设网络是动态的,即可能存在添加新节点、节点遗失或移动,每个节点通过周期性交换信息来维护SLN列表.
3.2 算法思想为了避免现有算法所存在的问题,本文提出一种与网络拓扑结构无关的安全高效数据聚集算法SESDA. SESDA分为5个阶段:路线设计阶段、初始化阶段、聚集请求阶段、数据聚集阶段和聚集结果返回阶段.
· 路线设计阶段:根据聚集区域大小、位置和节点传输半径确定理想线路.
· 初始化阶段:在对已预设密钥的邻居节点之间建立安全通道;
· 聚集请求阶段:利用位置路由协议将聚集请求发送至聚集区域内的某个节点(起始聚集节点),如图 1中的节点A1.
· 数据聚集阶段:数据节点将感知数据传给聚集节点.聚集节点对收到的数据进行聚集并将聚集结果传给下一个聚集节点,直至遍历整个聚集区域.
· 聚集结果返回阶段:区域内最后一个聚集节点利用位置路由协议将最终的聚集结果通过加密传输返回至Sink.
3.2.1 路线设计阶段 根据聚集区域大小(不失一般性,区域为矩形),节点通信半径R,设置路线宽度WI,为了保证能够聚集区域内所有节点的感知数据,路线宽度满足WI≤R/2在此基础上设置理想路线,从起始聚集节点开始,沿着理想路线确定下一个聚集节点.如此继续,直到最后一个聚集节点为止,形成聚集节点序列,即实际路线(real itinerary).如图 1所示,3条黑色虚线将聚集区域分成4个子区域,灰色虚线表示理想路线,沿着理想路线的黑色圆点(聚集节点)形成实际路线;灰色圆点表示数据节点,每个聚集节点只聚集本子区域的数据节点.
根据前面介绍的密钥分配方案,每个节点从有K个密钥的密钥池中随机选取k个密钥,并通过共享密钥与邻居节点建立安全通道(共享随机数).例如,节点Di与邻居节点Dj拥有相同的密钥kij,两节点建立安全通道的过程是:不失一般性,Di选择一个随机数dij,并用密钥kij加密,再将密文传输给Dj,Dj通过密钥kij解密得到随机数dij,dij(dij=dji)即为Di和Dj的安全通道.节点之间通过安全通道进行数据传输能够防窃听攻击.本文将拥有安全通道的邻居节点称为SLN节点,每个节点维护自身的SLN节点列表.
3.2.3 数据聚集阶段从起始聚集节点(aggregator node,简称A-节点)开始,A-节点接收数据节点的感知数据,对所有数据(包括自身数据)进行聚集,并将聚集结果传输到下一个A-节点.如此继续,直至遍历整个聚集区域.最后一个A-节点得到最终的聚集结果.为了保证数据的隐私性,所有数据都通过安全通道进行传输,使得数据能够抗窃听攻击.同时,为使数据节点数据不泄露给A-节点,数据节点在传输给A-节点之前对数据进行切分,并将这些切片发送给SLN节点.该阶段具体操作如下:
Step 1. 聚集节点选择和聚集请求广播.
起始A-节点A1作为当前节点,根据SLN节点列表,选择在聚集路线方向上与理想线路尽可能贴近、前进距离尽量远的节点A2作为下一个A-节点.为了进一步量化选择标准,可设置公式
其中,g和d是系统参数.A-节点Ai选择SiAGG(j)值最大的节点Aj作为下一个A-节点.同时,Ai向邻居节点广播聚集请求信息,包括聚集标识、当前A-节点ID和下一个A-节点ID等.Ai完成聚集后,将当前聚集结果等信息传输给下一聚集节点,包括聚集标识、部分聚集结果等.
Step 2. 数据切分与重组.
当节点收到聚集请求信息后,符合响应请求的节点,称为数据节点(data node,简称D-节点)响应聚集请求. D-节点在将感知数据传输给A-节点之前对数据进行切分,即,将数据vi随机分成Ji片,
并将Ji-1片数据通过安全通道传输给SLN节点.
由于节点间的距离越大,其链路质量的期望越小[17],所以当D-节点接收到聚集请求后,可能有两个A-节点可供选择,如图 2(a)所示,D6和D7可选择A1或A2作为目的A-节点.为了降低因较低的链路质量而多次重传造成的能耗,D-节点选择距离较近min(fdist(Di,Ai),fdist(Di,Aj))的A-节点作为目的A-节点.例如,未考虑链路质量.D6和D7选择A1作为目的A-节点(如图 2(a)所示);当考虑链路质量后,则选择A2作为目的A-节点(如图 2(b)所示).
 | Fig. 2 D-Nodes select the destination A-nodes图 2 D-节点选择目的A-节点 |
由于多个D-节点可能同时传输数据,为了避免信道冲突,算法设定在每个确定时间内只有1个D-节点传输数据.主要有基于TDMA和基于环形的虚拟令牌两种方案.这两种方案需要D-节点之间或D-节点与A-节点之间进行通信.为了减少通信量,简化处理进程,本文采用类似基于环形的方案,具体如下:A-节点广播聚集请求信息中包括 参考线信息,D-节点根据参考线信息,通过简单运算得出其传输切片数据的时间为timer_slice= max_delayx(q/4p),其中,q是参考线与连接D-节点和A-节点的连线之间的夹角(不失一般性,按顺时针方向),如图 3所示.其中,max_delay指的是A-节点完成数据聚集的最大时间.由于每个D-节点需要进行切分操作并将切片传输给SLN节点和重组切片再将重组结果传输给A-节点,因此D-节点需要进行两轮传输,其中,timer_slice为第1轮D-节点切片传输时间.
 | Fig. 3 Time assignation图 3 时间分配 |
不同于SMART和EEHA算法将感知数据分成固定的片数,SESDA将D-节点感知数据分成J片,其中,J的值是变化的.由于感知数据的隐私性与节点数据的切片数和收到的切片数相关联,因此,SESDA中每个D-节点感知数据的切片数不是随机确定,而是根据已收到的切片数动态确定切片数,优点是在切片总数一定的情况下,使数据的平均隐私性尽可能地高.显然,切片数J越小,通信量就越少,能耗就越低,数据隐私性也就越低.为了保证数据隐私性的等级,D-节点数据切片数必须符合下面两个条件:
其中,Ji和Jirec分别表示D-节点感知数据的切片数和收到其他D-节点的切片数,JSecu是系统参数.由条件可知:D-节点的q值越大,执行切片并传输的时间越晚,所以可能收到的切片数越多,需要对自身感知数据的切片数就越小.因此,为了尽可能地均衡各节点的能耗,A-节点发送的参考线位置是随机产生的.后面安全性能分析小节,我们将详细阐述数据的隐私性,以及在切片总数(通信量)一定的情况下,如何总体提高数据的隐私性.
图 4具体描述了切分过程,D-节点Di将感知数据随机分成Ji片,自己保留1片,其余的Ji-1片通过安全通道随机发送给Di的SLN节点.例如,D1将数据切成4片,D1保留v11,将其余3片发送给SLN节点D2,D3和D5,即D1→ D2:v12+d12 mod r,D1→D3:v13+d13 mod r和D1→D5:v15+d15 mod r.在保证所有切片都被接收后,D-节点对切片进行重组(聚集),并得到新的结果vin图 4中,虽然A1聚集结果不包含切片v26和v27,但这两片数据将包含在A2聚集结果上.显然,只要保证D-节点不要将切片传输给上一个A-节点聚集范围内的D-节点,聚集结果就是准确的.
 | Fig. 4 Illustrative example of slicing图 4 切分实例 |
Step 3. 数据聚集.
当节点接收到其他D-节点切片后,对所有切片进行重组,再将重组结果传输给目的A-节点.为了避免传输冲突,每个D-节点传输时间为timer_Mix=max_delayx((q+2p)/4p),即timer_Mix为第 2轮D-节点将重组结果传输给A-节点时间.A-节点接收到D-节点数据后,对所有数据(包括自身感知数据)进行聚集操作,再将聚集结果传输给下一个A-节点.例如,图 5显示图 4中节点A1的接收、聚集和传输过程:
 | Fig. 5 Illustration of the three steps of A-nodes图 5 A-节点3步过程实例 |
当A2收到A1聚集结果后,A2作为当前A-节点,根据前面的规则选择下一个A-节点.如此继续,直到遍历完聚集区域内的所有节点,得到最终的聚集结果.
3.3 性能分析 3.3.1 安全性分析SESDA通过安全通道确保其他节点或攻击者不能获得传输的实际值,同时采用切分技术,使得A-节点不能获得任何D-节点感知数据.由于A-节点聚集多个D-节点重组数据或切片数据,保证A-节点原始数据没有泄漏给其他A-节点.在SESDA中,D-节点和A-节点隐私保护的策略不同.本文在分析安全通道安全性的基础上,分别分析D-节点和A-节点感知数据的隐私性能.
1) 安全通道
邻居节点Di和Dj的安全通道是两节点共享随机数dij,可以通过解密或猜测来获取随机数dij:(1) 对于其他节点来说,通过自身密钥解密获取随机数的概率为p=k/K[15];(2) 猜测随机数,由于随机数dij在范围[0,…,r]中是均匀分布,其中,r=RdxN,因此,正确猜测的概率是1/r.当节点Di向Dj传输数据时,由于dij在范围[0,…,r]中是均匀分布的,因此vi+dij mod r在范围[0,…,r]中也是均匀分布,即,窃听到该数据后是不能推导出vi.因此,随机数泄漏的概率为Pr=min((sxpxnnei),r),其中,nnei为邻居节点数,s是安全通道重建频率对安全性影响的系数.
2) D-节点
D-节点Di将数据vi切割成Ji片,并将Ji-1片通过安全通道发送(出度)给SLN节点,所以泄漏每片数据vij的概率为Pr.要获取vi值,必须得到Ji-1片数据和vin值,由安全通道隐私性能分析可知:获得Ji-1片数据的概率为
的值由第Ji片数据和接收到的切片数据重组得到.因此,获取值的概率为
,其中,
表示节点Di接收(入度)的切片数.所以,D-节点数据vi值泄漏的概率为
3) A-节点
A-节点Ai聚集D-节点聚集值、可能有的D-节点切片和自身感知数据,并将聚集结果传输给下一个A-节点.因此,获取Ai的vi值必须得到所有D-节点重组值和切片数据值.所以,vi泄漏的概率为
其中,表示向Ai节点传输数据的D-节点个数.
对于节点密度较大的网络,A-节点收集到的D-节点数据个数较多,因此A-节点数据隐私性较高.由公式(2)
可知:D-节点感知数据隐私性由切片数Ji和确定,其平均被泄漏的概率为
;切片总数为
，因此,切片总数越大,通信量就越大,数据的隐私性可能也就越高.由于D-节点的切片数是变化的,在总的通信量一定的情况下,如何使数据平均被泄漏的概率最低?由此得出定理1.
定理1(数据泄漏率). 在节点切片总数(通信量)一定的情况下,当所有D-节点出入度之和相等时,数据平均被泄漏的概率最低,隐私性最高.
证明:即证明当Jtotal一定时,当
时
最小,其中,
由于只有极少部分切片传输给A-节点,可忽略不计,因此可知
所以,
由于Jtotal是定值,所以
也是定值(Pr是定值);
由于算术平均数大于等于几何平均数,
即,
当且仅当
成立时等号成立,
即,
时,
为最小,隐私性最高.证毕.
由定理1可知:当切片总数为定值时,每个D-节点的出入度之和与平均值越接近,感知数据平均泄漏的概率就越低.因此,在实际执行过程中虽然很难使所有D-节点出入度之和相等,但每个D-节点根据接收到的切片数来动态地确定J值,在不增加通信量的情况下,可最大程度地提高数据的平均隐私性.同样地,在设置系统参数JSecu(隐私性)后,算法可动态地确定J值,在数据满足一定隐私性要求的前提下,可最大程度地降低通信量.另外,让所有D-节点的出、入度之和相近,使所有节点能耗(eT≈eR)相近,有利于延长网络的生命周期.
3.3.2 通信量 SESDA通信量包括两部分:建立安全通道和执行数据聚集.节点Di和Dj建立安全通道的过程是Di加密随机数dij并将密文输出给Dj,Dj解密dij并返回确认信息,加密数据的位长为
节点Di需要和
个节点建立安全通道,每对节点之间只需建立1条安全通道.因此,安全通道通信量为
所有数据通过安全通道进行传输,数据位数均为
.因此,感知数据、切片数据、部分聚集结果和最终聚集结果大小相等且均为
此外,A-节点和D-节点数据传输的机制不同,具体如下:
1) A-节点
广播聚集请求给所有一跳的D-节点,位长为
并将所有接收到的重组数据和可能的切片数据进行聚集,最后将聚集结果传输给下一个A-节点,具体为公式(5),其中,Anum表示A-节点个数,niDnum表示A-节点Ai接收到D-节点个数:
2) D-节点
Di需要将感知数据分成Ji片,并将Ji-1片传输给SLN节点,接收其他D-节点片数据,并将重组结果传输给A-节点,其通信量为公式(6),其中,Dnum表示D-节点个数:
由于节点总数为N,可知N=Dnum+Anum,且每个D-节点接收聚集请求消息,所有节点接收到的切片总数与A-节点接收到的重组数据(D-节点个数)之和与D-节点的切片总数相等.因此,总通信量可简化为
通过公式(7)可知:通信量与D-节点和A-节点所占比例有关,并与D-节点的切片总数有关.由于A-节点不需要进行切分操作,因此总体来说,D-节点数所占比例越高,通信量就越大.同时,为了提高安全性,每隔一个周期重建一次安全通道,假设每个周期进行b轮数据聚集,则每轮数据聚集的平均通信量为
能耗主要由通信和运算组成,其中,运算主要有加/解密运算和加模运算.与加/解密运算能耗相比,加模运算能耗可忽略不计,因此,本文只考虑加/解密运算的能耗.在SESDA中,所有加/解密操作只发生在安全通道建立阶段,每条安全通道需执行加密和解密操作各1次,因此,加/解密次数为
根据上面通信量的分析,ED-node,EA-node分别表示D-节点和A-节点通信量能耗,数据聚集能耗为Ea=ED-node+ EA-node,具体为
当WSNs是密集型网络时,A-节点能够找到下一个A-节点;但当网络节点分布是非均匀或节点密度较小时,则可能出现A-节点在当前区域找不到下一个A-节点.同时,由于传感节点易失效的特点,网络可能出现节点失效或部署新节点.下面具体阐述如何处理上述情况.
4.1 路线失效假设网络节点分布不均匀或节点密度较小,当聚集区域中的某个A-节点根据上述规则找不到下一个A-节点时,即出现路线失效,如图 6(a)所示,SESDA利用位置路由协议绕过该子区域继续执行.例如,图 6(b)中,A2在通信范围内找不到下一个A-节点,出现路线失效,聚集操作无法继续执行.为了避免该问题,本文采用如下处理方 法:A2找不到下一个A-节点时,继续广播聚集请求,并将下一个聚集节点ID设为-1;通信范围内所有D-节点收到聚集请求后,将A2作为目标节点,并进行切分聚集操作.A2聚集完该范围内所有D-节点数据后,以区域L2R2NM为目的位置(其中,fdist(L2,N)=fdist(R2,M)=R),利用位置路由协议将部分聚集结果和聚集消息发送至区域L2R2NM中的节点(即下一个A-节点)以保证路线失效时能继续完成聚集任务.当区域L2R2NM中没有节点时,A2将以区域MNM¢N¢为目的位置(其中,fdist(M,N¢)=fdist(N,M¢)=R),如果区域MNM¢N¢仍然没有任何节点,则以此类推,直到找到下一个A-节点,如图 6(c)所示.
 | Fig. 6 Illustrative example of itinerary void图 6 路线失效示意图 |
定理2(节点完全覆盖). 当路线失效时,SESDA能够覆盖聚集区域内所有节点.
证明:
(1) 区域IJL2R2内没有传感节点,否则,聚集节点A2将能够找到一下聚集节点,如图 6(c)所示,与假设矛盾.
(2) 如果区域L2R2NM内有节点,则A2根据路由协议选择该区域内某个节点A3作为下一个聚集节点(聚集节点选择规则与前面相同),于是,A3能够保证聚集区域L2R2NM内所有D-节点;如果区域L2R2NM内没有节点,则考虑区域MNM¢N¢并做同样处理,即可保证聚集区域MNM¢N¢内所有节点数据.
综合情形(1)和情形(2)可知,算法能够保证聚集任意两个聚集节点之间的所有D-节点.证毕.
4.2 扩展性由于传感器网路的动态性及传感节点的易失效性,网络运行过程中可能存在节点失效或部署新节点的情况.在已有的聚集查询算法中,当部署新节点时,需要对该节点与Sink/其父节点/子树根节点提前部署一些必要的信息,如密钥、随机数等,网路扩展比较困难.本文提出的算法具有很好的扩展性,当需要部署新节点时,只要提前将密钥池加载到该节点即可,具体是:
(1) 添加新节点:当节点Di部署到网络中时,确定其SLN节点列表并与列表中的节点建立安全通道;同时,SLN节点列表中的节点将Di添加到自身的SLN节点列表中,完成新节点的部署.
(2) 遗失节点:当Di的SLN节点列表中的某节点超过一定时间没有响应后,Di认为该节点失效,并将该节点从SLN节点列表中删除,防止Di将切片传输给该失效节点,保证网络正常工作.
5 仿真实验及分析为了对算法的通信量、能耗、精确度和隐私性等性能进行比较,本节在文献[18]的WSNs模拟器基础上,仿真实现SESDA,SMART和IWQE算法.为了更好地比较各算法的性能,3种算法采用同样的实验数据集Intel Lab Data[19].实验环境为Core i3-3220CPU,4G内存;软件环境为Win7操作系统,VS.NET 2010和Matlab.采用文献[20]给出的TelosB参数,传输和接收1bit的能耗分别为eT=0.72mJ和eR=0.81mJ.利用RC4对数据进行加/解密,10bit数据能耗为8.92mJ.实验结果是执行20轮的平均值,每轮随机产生一个WSNs拓扑.其他参数见表 1.
|
Table 1 Experimental paramaters 表 1 实验参数 |
测试SESDA,SMART和IWQE这3种算法在不同的节点数、不同的平均切片数和每周期不同数据聚集轮数情况下,算法总的通信量和能耗.
1) 通信量
图 7显示3种算法在不同参数下通信量的变化.因为SMART需要将所有节点感知数据切割成J片,并将J-1片加密传输给其邻居节点,因此,SMART算法数据传输的通信量为NxJx从图 7可以看出,IWQE的通信量最小,但IWQE没有考虑数据隐私性.除了每次聚集前都重新建立安全通道(b=1)的情况下,SESDA的通信量比SMART稍高以外,SESDA通信量比SMART要少;而且随着N和J的增大,SESDA通信量减少的幅度更大.当b值较大时,SESDA需要的通信量比SMART小很多,最多达到42%.
 | Fig. 7 Communication cost图 7 通信量 |
2) 能耗
由于SESDA只在安全通道建立阶段需要进行加/解密计算,而在数据聚集阶段没有任何加/解密计算,极大降低了计算能耗.因此,即使在不考虑网络拓扑结构维护开销的情况下,SESDA比SMART能耗减少幅度更大.
· 如图 8(a)所示,随着N的增大,降低幅度也随之增大,达到50%.
· 同时,随着J的变大,SMART由于切片数的增加,其加/解密次数随之增加,而SESDA的加/解密次数与切片数无关,所以SESDA比SMART节省更多能耗,如图 8(b)所示.
 | Fig. 8 Energy consumption图 8 能量消耗 |
· 从图 8(c)可知,b值越大,SESDA的能耗越接近IWQE算法.
5.2 隐私保护图 9显示SESDA,SMART和SESDA-NonOpt感知数据泄漏的概率(隐私性),其中,SESDA-NonOpt表示没有应用本文提出的切片数优化确定机制,即,D-节点切片数完全随机,不考虑节点出入度之和的均衡性.
 | Fig. 9 Privacy comparisons图 9 私有性比较 |
实验结果显示:在破解链路安全的概率PLP较低时,SESDA和SMART感知数据泄漏的概率近似,都具有较高的隐私性;但随着PLP的增大,SESDA的感知数据具有更好的隐私性,特别是当PLP大于等于0.8时,SESDA感知数据的隐私性比SMART具有明显的优势.同时,从图 9还可以看出,SESDA-NonOpt数据的隐私性没有SESDA和SMART高.主要原因是SESDA-NonOpt没有综合考虑节点的出度和入度,使得节点间隐私度相差较大,造成感知数据平均隐私性较低.因此,在没有增加通信量和能耗的情况下,综合考虑节点的出入度,动态确定节点的切片数,对提高感知数据的隐私性具有重要的影响.
图 10显示平均切片数Ave-J不同时,SESDA感知数据的隐私性.从图中可知:Ave-J值越大,感知数据的隐私性就越好,但其通信量和能耗也越高.因此,SESDA可以通过设置不同Ave-J值,在私有保护和通信/能耗之间取得平衡.
 | Fig. 10 Privacy with respect to the average number of slices图 10 不同平均切片数私有性比较 |
理想情况下,没有数据丢失,聚集结果精确性将是100%;但由于网络无线通道的冲突性、数据处理的延迟性导致传输信息的丢失和节点的失效性,使得聚集结果的精确性受到影响.精确性为算法聚集结果与实际的感知数据和之间的比率.由于本文研究的是加聚集,因此,精确度定义为公式:
图 11(a)显示了3种算法在不同时间周期下得到的聚集结果精确度,从图中可知:时间周期越长,聚集精确度越高,主要原因是:(1) 时间周期越长,使得在周期内传输的数据包之间发生碰撞的几率越小;(2) 时间周期越长,使得数据包有越大的概率在传输时间截止前完成传输.另外,因为SMART在聚集过程中需要对每片数据进行加/解密操作,而SESDA在聚集 过程中没有加/解密操作,节省了大量的时间,减少了延迟.因此,SESDA聚集结果的精确度比SMART更高(当时间周期相对较小时,精确度差距更大).由于IWQE不需要进行加/解密和切片操作,因此聚集精确度最高.从图 11(b)可知,不同的Ave-J值对SESDA精确度的影响不大.但更小的Ave-J值具有相对较高的精确度,主要原因是:随着Ave-J的增大,需要将更多的数据包传输给安全链接邻居节点,因此数据包有更大的概率发生碰撞,降低了聚集结果精确度.
 | Fig. 11 Aggregation accuracy图 11 聚集精确度 |
由实验结果可以看出:SESDA在通信量、能耗和聚集精确度方面比SMART具有明显的优势;在链路安全较低时,SESDA感知数据的隐私性能更好.因此,与SMART相比,SESDA需要更少的通信量和能耗,能够达到更高的聚集精确性和更好的数据隐私性.同时,SESDA通过调节b和Ave-J值,更便于在私有保护、聚集精确度和通信/能耗之间取得平衡.
6 总 结WSNs中提供具有隐私保护的高效的数据聚集算法是一个挑战性的问题.我们提出了一种安全数据聚集算法SESDA.SESDA采用基于路线的聚集请求和数据聚集,使得算法的执行与WSNs的拓扑结构无关,节省了维护网络拓扑结构的消耗,当部分传感节点发生失效或移动时,数据聚集能够继续正确执行,且在网络中容易部署新节点,即算法具有良好的扩展性.同时,感知数据通过安全通道进行传输,所以在保证数据隐私性的情况下,聚集过程无需任何加/解密操作,使得计算能耗可以忽略 不计,比较适合传感节点电池供电、难以维护的特点,且各节点能耗比较均衡,有利于延长整个网络生命周期.此外,SESDA能够极大地缩短数据处理时间,降低处理延迟,提高聚集精确度.因此,SESDA能够应用到部署在野外、网络结构动态变化、保证数据隐私和聚集结果精确度要求较高的网络场景.例如在军事领域,军队通过使用WSNs代替周边防务的哨兵,通过对潜在攻击的定位和识别来保证士兵的安全,并对打击敌人给予信息支持.这类WSNs部署在野外、网络难以维护、结构动态变化,且感知数据面临隐私泄露问题,SESDA适应于这类网络场景要求.实验结果显示:SESDA算法在增加少量通信量和能耗的情况下,保证了数据的隐私性.与已有的安全的数据聚集算法SMART相比,SESDA需要更少的通信量/能耗、更高的聚集精确度和更好的扩展性.
致谢 在此,我们向对本文的工作给予支持和建议的同行表示感谢.
| [1] | Culler D, Estrin D, Srivastava M. Overview of sensor networks. IEEE Computer, 2004,37(8):41-49 . |
| [2] | Xu N, Rangwala S, Chintalapudi KK, Ganesan D, Broad A, Govindan R, Estrin D. A wireless sensor network for structural monitoring. In: Stankovic JA, Arora A, Govindan R, eds. Proc. of the 2nd ACM Conf. on Embedded Networked Sensor Systems. Baltimore: ACM Press, 2004. 13-24 . |
| [3] | Zhang XW, Dai HP, Xu LJ, Chen GH. Mobility-Assisted data gathering strategies in WSNs. Ruan Jian Xue Bao/Journal of Software, 2013,24(2):198-214 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4349.htm |
| [4] | He W, Nguyen H, Liu X, Nahrstedt K, Abdelzaher T. iPDA: An integrity-protecting private data aggregation scheme for wireless sensor networks. In: Proc. of the IEEE Military Communication Conf. San Diego: IEEE Press, 2008. 1-7 . |
| [5] | Girao J, Westhoff D, Schneider M. CDA: Concealed data aggregation for reverse multicast traffic in wireless sensor networks. In: Proc. of the IEEE Int’l Conf. on Communications. Seoul: IEEE Press, 2005. 3044-3049 . |
| [6] | Yu Y, Krishnamachari B, Prasanna VK. Energy-Latency tradeoffs for data gathering in wireless sensor networks. In: Proc. of the 23rd IEEE Int’l Conf. on Computer Communications. Hong Kong: IEEE Press, 2004. 244-255 . |
| [7] | Madden S, Franklin MJ, Hellerstein JM, Hong W. TAG: A tiny aggregation service for ad-hoc sensor networks. In: Proc. of the ACM OSDI. Boston: ACM Press, 2002. 131-146 . |
| [8] | Xu Y, Lee WC, Xu J, Mitchell G. Processing window queries in wireless sensor networks. In: Liu L, Reuter A, Whang KY, Zhang JJ, eds. Proc. of the 22nd IEEE Conf. on Data Engineering. Atlanta: IEEE Press, 2006. 70-80 . |
| [9] | Castelluccia C, Mykletun E, Tsudik G. Efficient aggregation of encrypted data in wireless sensor networks. In: Proc. of the 2nd Annual Int’l Conf. on Mobile and Ubiquitous Systems. San Diego: IEEE Press, 2005. 109-117 . |
| [10] | He W, Liu X, Nguyen H, Nahrstedt K, Abdelzaher T. PDA: Privacy-Preserving data aggregation in wireless sensor networks. In: Proc. of the 26th IEEE Int’l Conf. on Computer Communications. Alaska: IEEE Press, 2007. 2045-2053 . |
| [11] | Yang Y, Wang X, Zhu S, Cao G. SDAP: A secure hop-by-hop data aggregation protocol for sensor networks. ACM Trans. on Information and System Security, 2008,11(4):18 . |
| [12] | Li HJ, Lin K, Li KQ. Energy-Efficient and high-accuracy secure data aggregation in wireless sensor networks. Computer Communications, 2011,34(4):591-597 . |
| [13] | Ozdemir S, Xiao Y. Integrity protecting hierarchical concealed data aggregation for wireless sensor networks. Computer Networks, 2011,55(8):1735-1746 . |
| [14] | Karp B, Kung HT. GPSR: Greedy perimeter stateless routing for wireless networks. In: Pickholtz RL, Das SK, Cáceres R, et al., eds. Proc. of the 6th Annual ACM Int’l Conf. on Mobile Computing and Networking. Boston: ACM Press, 2000. 243-254 . |
| [15] | Eschenauer L, Gligor VD. A key-management scheme for distributed sensor networks. In: Vijayalakshmi A, ed. Proc. of the 9th ACM Conf. on Computer and Communications Security. Washington: ACM Press, 2002. 41-47 . |
| [16] | Fu TY, Peng WC, Lee WC. Parallelizing itinerary-based KNN query processing in wireless sensor networks. IEEE Trans. on Knowledge and Data Engineering, 2010,22(5):711-729 . |
| [17] | Zuniga M, Krishnamachari B. Analyzing the transitional region in low power wireless links. In: Proc. of the 1st Annual IEEE Communications Society Conf. on Sensor and Ad Hoc Communications and Networks. Washington: IEEE Press, 2004. 517-526 . |
| [18] | Coman A, Nascimento MA, Sander J. A framework for spatio-temporal query processing over wireless sensor networks. In: Labrinidis A, Madden S, eds. Proc. of the 1st Workshop on Data Management for Sensor Networks, in Conjunction with VLDB. Toronto: ACM Press, 2004. 104-110 . |
| [19] | Samuel M. Intel lab data. 2004. http://db.csail.mit.edu/labdata/labdata.html |
| [20] | Groat MM, He W, Forrest S. KIPDA: k-Indistinguishable privacy-preserving data aggregation in wireless sensor networks. In: Proc. of the 30th IEEE Int’l Conf. on Computer Communications. Shanghai, 2011. 2024-2032 . |
| [3] | 张希伟,戴海鹏,徐力杰,陈贵海.无线传感器网络中移动协助的数据收集策略.软件学报,2013,24(2):198-214. http://www.jos.org. cn/1000-9825/4349.htm |