戴 華 秦小麟 劉 亮 季一木 付 雄 孫 研

①(南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210003)

②(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210016)

1 引言

目前，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)已被廣泛用于諸如環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生、智能交通、國(guó)防軍事等各種重要領(lǐng)域。而兩層WSNs(Two-tiered Wireless Sensor Networks)[1]是一種以存儲(chǔ)節(jié)點(diǎn)(storage nodes)為中間層的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，其中存儲(chǔ)節(jié)點(diǎn)為計(jì)算、存儲(chǔ)和能量資源充足的傳感器節(jié)點(diǎn)，其上層為Sink節(jié)點(diǎn)，下層為資源受限的一般感知節(jié)點(diǎn)(sensor nodes)，存儲(chǔ)節(jié)點(diǎn)與查詢(xún)區(qū)域內(nèi)其負(fù)責(zé)管理的所有感知節(jié)點(diǎn)構(gòu)成查詢(xún)單元(query cells)。由于兩層WSNs的拓?fù)浣Y(jié)構(gòu)的簡(jiǎn)單性和中間層存儲(chǔ)節(jié)點(diǎn)的資源充裕性，使得兩層WSNs具有鏈路質(zhì)量穩(wěn)定、路由結(jié)構(gòu)簡(jiǎn)單、查詢(xún)高效和負(fù)載均衡等優(yōu)點(diǎn)[1,2]。然而，由于存儲(chǔ)節(jié)點(diǎn)所處位置的重要性，不僅存儲(chǔ)著大量感知數(shù)據(jù)，同時(shí)還負(fù)責(zé)執(zhí)行上層的查詢(xún)請(qǐng)求，這就使得存儲(chǔ)節(jié)點(diǎn)往往成為各種攻擊的主要目標(biāo)。研究和解決兩層WSNs中的安全和隱私保護(hù)問(wèn)題，對(duì)于促進(jìn)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)的大規(guī)模應(yīng)用具有重要的現(xiàn)實(shí)意義。

在面向兩層 WSNs的隱私保護(hù)查詢(xún)處理技術(shù)中，現(xiàn)有研究重點(diǎn)關(guān)注范圍(range)查詢(xún)中的隱私保護(hù)技術(shù)[3-6]，對(duì)于最值(MAX/MIN)查詢(xún)處理的研究相對(duì)較少，目前僅有文獻(xiàn)[7]提出了初步的解決方法，該方法利用前綴編碼驗(yàn)證(Prefix Membership Verification, PMV)機(jī)制[3]，給出了一種無(wú)需感知數(shù)據(jù)明文參與的數(shù)值線(xiàn)性關(guān)系比較方法，進(jìn)而實(shí)現(xiàn)滿(mǎn)足隱私保護(hù)要求的最值查詢(xún)處理方法(記為 PMVMQP)。然而，該方法采用的前綴編碼機(jī)制產(chǎn)生的數(shù)據(jù)量較大，并且每一個(gè)感知節(jié)點(diǎn)都需要加密感知數(shù)據(jù)并傳送密文數(shù)據(jù)，導(dǎo)致該查詢(xún)處理過(guò)程需要較大的能耗開(kāi)銷(xiāo)。此外，文獻(xiàn)[8]提出了工作于多跳WSN中基于k-隱藏的最值聚集查詢(xún)方法，但該方法只能查詢(xún)最值數(shù)據(jù)，無(wú)法查詢(xún)產(chǎn)生最值數(shù)據(jù)的傳感器節(jié)點(diǎn)位置信息。

本文以?xún)蓪覹SNs為研究背景，重點(diǎn)討論面向兩層WSNs的隱私保護(hù)最值查詢(xún)處理技術(shù)，即在實(shí)現(xiàn)最值查詢(xún)處理的過(guò)程中，確保感知數(shù)據(jù)和最值查詢(xún)結(jié)果不泄露，以保證感知數(shù)據(jù)和最值查詢(xún)結(jié)果的隱私安全性?；诖?，本文提出了基于Z-O編碼的兩層WSNs隱私保護(hù)最值查詢(xún)處理協(xié)議。通過(guò)引入安全多方計(jì)算中的Z-O編碼技術(shù)[9]，并結(jié)合Hash消息身份驗(yàn)證編碼機(jī)制(Hashed Message Authentication Code, HMAC)[10]，對(duì)感知數(shù)據(jù)進(jìn)行HMAC數(shù)值化Z-O編碼處理，然后利用Z-O編碼集合的數(shù)值比較特性，實(shí)現(xiàn)在無(wú)需感知數(shù)據(jù)明文參與下的數(shù)值線(xiàn)性關(guān)系比較，并利用加密技術(shù)確保感知數(shù)據(jù)傳輸過(guò)程中的隱私安全性。在上述隱私保護(hù)措施的基礎(chǔ)上，給出基于Z-O編碼的隱私保護(hù)最值查詢(xún)處理協(xié)議(Z-O Encoding based Privacy Preserving Max/Min query process protocol, ZOPPM)，并對(duì)該協(xié)議進(jìn)行能耗和隱私安全性分析。實(shí)驗(yàn)結(jié)果表明，ZOPPM協(xié)議的能耗優(yōu)于現(xiàn)有的方法。

2 問(wèn)題描述

在兩層WSNs的查詢(xún)處理過(guò)程中，如果不對(duì)感知數(shù)據(jù)進(jìn)行處理，直接以明文形式參與查詢(xún)，當(dāng)存儲(chǔ)節(jié)點(diǎn)被俘獲，該節(jié)點(diǎn)將能夠獲取所有存儲(chǔ)在該節(jié)點(diǎn)，以及利用該節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)的感知數(shù)據(jù)，并且還能夠獲取由該節(jié)點(diǎn)計(jì)算出的部分查詢(xún)結(jié)果。與此同時(shí)，由于傳感器節(jié)點(diǎn)數(shù)據(jù)通信的廣播特性，在感知節(jié)點(diǎn)發(fā)送數(shù)據(jù)的一跳(hop)范圍內(nèi)，其他任何節(jié)點(diǎn)(存儲(chǔ)節(jié)點(diǎn)或感知節(jié)點(diǎn))都可以收到數(shù)據(jù)。因此，需要在查詢(xún)處理過(guò)程增加隱私保護(hù)措施，以確保感知數(shù)據(jù)和查詢(xún)結(jié)果的隱私安全性。

最值查詢(xún)即為獲取查詢(xún)區(qū)域內(nèi)的感知節(jié)點(diǎn)采集到的數(shù)據(jù)最大值(MAX)或最小值(MIN)及其位置信息的計(jì)算過(guò)程。最值的計(jì)算必然需要比較數(shù)值的線(xiàn)性關(guān)系，所以解決最值查詢(xún)問(wèn)題，首先需要解決如何在不泄露隱私的情況下比較兩個(gè)感知節(jié)點(diǎn)的數(shù)據(jù)大小問(wèn)題，該問(wèn)題類(lèi)似于安全多方計(jì)算研究中一個(gè)經(jīng)典問(wèn)題——百萬(wàn)富翁問(wèn)題[11]。

與文獻(xiàn)[3,7,8]類(lèi)似，本文也假設(shè)查詢(xún)發(fā)起節(jié)點(diǎn)Sink可信，并假設(shè)兩層WSNs中的存儲(chǔ)節(jié)點(diǎn)和感知節(jié)點(diǎn)都有試圖窺探其他節(jié)點(diǎn)數(shù)據(jù)的企圖，但仍然能夠遵循查詢(xún)處理協(xié)議進(jìn)行最值計(jì)算，即符合honestbut-curious威脅模型[12]。此外，假設(shè)兩層WSNs的拓?fù)浣Y(jié)構(gòu)穩(wěn)定，感知節(jié)點(diǎn)采集感知數(shù)據(jù)，存儲(chǔ)節(jié)點(diǎn)只負(fù)責(zé)計(jì)算和存儲(chǔ)；存儲(chǔ)節(jié)點(diǎn)擁有其負(fù)責(zé)的感知節(jié)點(diǎn)的位置和ID信息，而感知節(jié)點(diǎn)也擁有對(duì)應(yīng)存儲(chǔ)節(jié)點(diǎn)的位置和ID信息，Sink則擁有所有感知節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)的位置和ID信息。

在上述假設(shè)條件下，實(shí)現(xiàn)具有隱私保護(hù)能力的最值查詢(xún)，就必須確保查詢(xún)處理過(guò)程滿(mǎn)足：(1)對(duì)于網(wǎng)絡(luò)中的任一感知節(jié)點(diǎn)的感知數(shù)據(jù)，只有該感知節(jié)點(diǎn)本身和Sink可以讀取其明文數(shù)值；(2)對(duì)于最終的最值查詢(xún)結(jié)果(包含數(shù)值和位置信息)，只有Sink擁有，而其他任何節(jié)點(diǎn)都無(wú)法獲得。此外，存儲(chǔ)節(jié)點(diǎn)的能量資源充足，而感知節(jié)點(diǎn)的能耗有限，因此，降低感知節(jié)點(diǎn)的能耗開(kāi)銷(xiāo)也是兩層WSNs查詢(xún)處理技術(shù)研究的一個(gè)重要目標(biāo)。

3 基于Z-O編碼的數(shù)值比較方法

本節(jié)我們將在文獻(xiàn)[9]的基礎(chǔ)上，給出基于 Z-O編碼數(shù)值比較方法。

定義1Z-O編碼(Zero-One encoding)：設(shè)包含w個(gè)二進(jìn)制位的數(shù)值x=b1b2…bw-1bw(bi∈{0,1}且1≤i≤w)，對(duì)x進(jìn)行Z-O編碼，得到的Z編碼集合Z(x)和O編碼集合O(x)為

其中b1b2…bw-1bw是數(shù)值x的二進(jìn)制編碼表示，b1為最高位，bw為最低位。

性質(zhì)1設(shè)數(shù)值x為包含w個(gè)二進(jìn)制位，則Z(x)和O(x)滿(mǎn)足如下性質(zhì)：

由定義1容易得到性質(zhì)1成立(證略)。

性質(zhì)2若已知數(shù)值x的Z編碼集合或O編碼集合，不難反向逆推出數(shù)值x。

由定義1中的Z-O編碼方法及性質(zhì)1的內(nèi)容，易得性質(zhì)2成立。例如，若已知包含4個(gè)二進(jìn)制位的數(shù)值x的Z編碼集合Z(x)={1}，則x必定為0111。

定理1對(duì)于都包含w個(gè)二進(jìn)制位的數(shù)值x和y，當(dāng)且僅當(dāng)O(x)與Z(y)不相交時(shí)，x＞y成立；當(dāng)且僅當(dāng)O(x)與Z(y)存在非空交集時(shí)，x≤y成立，即有式(3)和式(4)成立。

定理1的證明詳見(jiàn)文獻(xiàn)[9]。由定理1可知，數(shù)值x和y的大小比較問(wèn)題，可以轉(zhuǎn)化為判斷Z編碼集合與O編碼集合是否存在交集的問(wèn)題。顯然，如果將Z編碼集合和O編碼集合中的元素都轉(zhuǎn)換為具體數(shù)值，則可以簡(jiǎn)化集合相交的計(jì)算過(guò)程。為了保持Z-O編碼的數(shù)值比較特性，對(duì)于Z-O編碼的數(shù)值化方法必須滿(mǎn)足定義2要求。

定義2若將任意Z-O編碼二進(jìn)制序列p的數(shù)值化方法記為N，得到的數(shù)值化Z-O編碼記為N(p)，則對(duì)于任意兩個(gè)Z-O編碼二進(jìn)制序列p1和p2，該數(shù)值化方法應(yīng)滿(mǎn)足：

(1)p1=p2?N(p1)=N(p2)；

(2)p1≠p2?N(p1)≠N(p2)。

顯然，針對(duì)Z-O編碼的數(shù)值化方法并不唯一。本文給出一種簡(jiǎn)單的數(shù)值化方法Ns：對(duì)于數(shù)值x的任一Z-O編碼序列p=b1b2…bi，則p數(shù)值化后得到Ns(p)=1b1b2…bi，即在二進(jìn)制序列b1b2…bi的最高位之前增加“1”。容易證明，該數(shù)值化方法Ns符合定義2要求。

4 基于 Z-O編碼的隱私保護(hù)最值查詢(xún)處理方法

4.1 基本思想

在介紹本文研究工作的基本思想之前，我們首先給出查詢(xún)單元的形式化定義。

定義3查詢(xún)單元(query cell)：存儲(chǔ)節(jié)點(diǎn)S與其在查詢(xún)區(qū)域內(nèi)的負(fù)責(zé)的所有感知節(jié)點(diǎn)?={s1,s2,…,sn}(?≠?)構(gòu)成一個(gè)查詢(xún)單元，記為 qcS=(S,?)。

根據(jù)定義3的要求，任一查詢(xún)單元只包含一個(gè)存儲(chǔ)節(jié)點(diǎn)，且至少包含一個(gè)感知節(jié)點(diǎn)。此外，由于存儲(chǔ)節(jié)點(diǎn)擁有其負(fù)責(zé)的感知節(jié)點(diǎn)的位置信息，因此，該存儲(chǔ)節(jié)點(diǎn)能夠計(jì)算出其所在的查詢(xún)單元或者不構(gòu)成查詢(xún)單元。為了方便討論，我們假設(shè)任一感知節(jié)點(diǎn)最多只存在于一個(gè)查詢(xún)單元中。

本文的面向隱私保護(hù)的最值查詢(xún)處理方法的基本思想主要包含如下兩個(gè)階段：

(1)查詢(xún)指令廣播階段首先 Sink將查詢(xún)指令MQ={t,qa, MAX/MIN}(表示查詢(xún)滿(mǎn)足時(shí)刻t和區(qū)域qa要求的最大/最小的感知數(shù)據(jù))廣播到所有存儲(chǔ)節(jié)點(diǎn)；存儲(chǔ)節(jié)點(diǎn)S收到MQ后，判斷是否構(gòu)成查詢(xún)單元qcS，若構(gòu)成，則S再將MQ轉(zhuǎn)發(fā)至qcS內(nèi)的所有感知節(jié)點(diǎn)，否則不參與查詢(xún)處理。

(2)最值查詢(xún)處理階段在每一個(gè)查詢(xún)單元 qcS=(S,{s1,s2,…,sn})中，si發(fā)送其感知數(shù)據(jù)的 HMAC數(shù)值化Z-O編碼數(shù)據(jù)給S；根據(jù)收到的qcS內(nèi)所有感知節(jié)點(diǎn)發(fā)來(lái)的編碼數(shù)據(jù)，S計(jì)算出qcS內(nèi)產(chǎn)生最值的節(jié)點(diǎn)sj，并通知sj發(fā)送感知數(shù)據(jù)；當(dāng)sj收到S的數(shù)據(jù)請(qǐng)求，sj立即加密其感知數(shù)據(jù)，并將密文發(fā)回給S；而S收到密文數(shù)據(jù)后，構(gòu)造qcS的局部查詢(xún)結(jié)果lqr(local query result)并發(fā)送給Sink；最后，Sink根據(jù)各個(gè)查詢(xún)單元發(fā)送的lqr，計(jì)算出最終的全局查詢(xún)結(jié)果gqr(global query result)，并返回給用戶(hù)。

在查詢(xún)處理階段，為了確保感知數(shù)據(jù)和查詢(xún)結(jié)果的隱私安全性，我們采取如下隱私保護(hù)措施：

(1)當(dāng)si需要發(fā)送其感知數(shù)據(jù)di給S時(shí)，首先利用對(duì)稱(chēng)加密方法(如RC4, RC5, IDEA等)對(duì)di進(jìn)行加密處理，生成密鑰為ki的加密數(shù)據(jù)(di)ki,si僅與Sink共享ki，然后將(di)ki發(fā)送給S；

(2)為了消除Z-O編碼的可逆推性，在編碼過(guò)程中增加HMAC處理。HMAC機(jī)制的單向性和抗沖突性，將使得感知數(shù)據(jù)di經(jīng)過(guò) HMAC數(shù)值化處理后，即可得到不可逆的 HMAC數(shù)據(jù)集合 HMACg(Ns(Z(di)))和HMACg(Ns(O(di)))，其中g(shù)為所有感知節(jié)點(diǎn)共享的HMAC密鑰。

4.2 具有隱私保護(hù)能力的最值查詢(xún)處理協(xié)議ZOPPM

下面，我們以最大值查詢(xún)處理為例，給出兩層WSN中基于Z-O編碼的隱私保護(hù)最值查詢(xún)處理協(xié)議。我們分別從查詢(xún)單元和Sink節(jié)點(diǎn)這兩個(gè)方面，討論ZOPPM協(xié)議的工作過(guò)程。

設(shè)lqrHMAC為存放HMAC數(shù)值化Z-O編碼數(shù)據(jù)的變量，lqrnode為存儲(chǔ)感知節(jié)點(diǎn)ID的變量，lqr(S)={id, cv}為存儲(chǔ)節(jié)點(diǎn)S所在查詢(xún)單元的局部查詢(xún)結(jié)果變量，gqr={id, pv}為存儲(chǔ)全局查詢(xún)結(jié)果的變量，其中id為感知節(jié)點(diǎn)ID, cv為密文數(shù)據(jù)，pv為明文數(shù)據(jù)，MD為密文傳送指令。則具體協(xié)議內(nèi)容如表1所示。

由ZOPPM協(xié)議內(nèi)容可知，兩層WSN中的最值查詢(xún)處理由Sink，存儲(chǔ)節(jié)點(diǎn)和感知節(jié)點(diǎn)共同協(xié)作完成。在查詢(xún)處理過(guò)程中，加密機(jī)制確保了感知數(shù)據(jù)在傳輸過(guò)程中的安全性，而HMAC機(jī)制的應(yīng)用，使得惡意節(jié)點(diǎn)無(wú)法利用Z-O編碼反向逆推原始感知數(shù)據(jù)，進(jìn)而保證了兩層 WSN中感知節(jié)點(diǎn)的隱私安全性。

表1 基于Z-O編碼的隱私保護(hù)最值查詢(xún)處理協(xié)議

4.3 協(xié)議分析

4.3.1隱私安全性分析我們主要從感知數(shù)據(jù)和查詢(xún)結(jié)果角度，分析ZOPPM協(xié)議的隱私安全性。

(1)感知數(shù)據(jù)的隱私安全性 在本文基于可信Sink節(jié)點(diǎn)的前提下，對(duì)于任意感知節(jié)點(diǎn)si及其本地感知數(shù)據(jù)di而言，僅當(dāng)查詢(xún)處理方法能夠確保其它感知節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)都無(wú)法獲取di時(shí)，di才是隱私安全的。而我們提出的ZOPPM協(xié)議能夠保證感知數(shù)據(jù)的隱私安全性：

首先，在最值查詢(xún)處理過(guò)程中，si在傳輸di時(shí)，需首先利用對(duì)稱(chēng)加密方法對(duì)di進(jìn)行加密處理(密鑰僅與 Sink共享)。因此，在無(wú)密鑰的情況下獲取di的復(fù)雜度與破解加密算法相同，從而確保任意傳輸路徑中的其它感知節(jié)點(diǎn)或存儲(chǔ)節(jié)點(diǎn)都無(wú)法獲取其明文數(shù)據(jù)。

其次，我們利用HMAC機(jī)制，對(duì)感知節(jié)點(diǎn)發(fā)送給存儲(chǔ)節(jié)點(diǎn)的數(shù)值化Z-O編碼集合進(jìn)行HMAC處理，使得存儲(chǔ)節(jié)點(diǎn)在無(wú)需感知數(shù)據(jù)明文參與的情況下，即可實(shí)現(xiàn)各感知數(shù)據(jù)的大小比較；同時(shí)也使得其它能夠獲得HMAC數(shù)據(jù)的節(jié)點(diǎn)，都無(wú)法反向逆推其對(duì)應(yīng)的感知數(shù)據(jù)。

(2)最值查詢(xún)結(jié)果的隱私安全性 最值查詢(xún)結(jié)果由最值數(shù)據(jù)和最值位置這兩方面組成。其中，最值數(shù)據(jù)同樣也是由某個(gè)感知節(jié)點(diǎn)產(chǎn)生的感知數(shù)據(jù)，由本節(jié)(1)中的討論可知，最值數(shù)據(jù)的隱私安全性同樣能夠保證。這里，我們重點(diǎn)分析ZOPPM協(xié)議對(duì)于最值位置的隱私保護(hù)能力。

對(duì)于最值查詢(xún)處理而言，產(chǎn)生最值的感知節(jié)點(diǎn)的位置信息同樣也需要保護(hù)。假設(shè)網(wǎng)絡(luò)中共有k個(gè)構(gòu)成查詢(xún)單元的存儲(chǔ)節(jié)點(diǎn)，則這些存儲(chǔ)節(jié)點(diǎn)將產(chǎn)生k個(gè)局部查詢(xún)結(jié)果(包含局部最值的位置信息)，而最終的全局查詢(xún)結(jié)果在其中產(chǎn)生，并由Sink負(fù)責(zé)計(jì)算?？梢?jiàn)，全局查詢(xún)結(jié)果的位置信息，隱藏在k個(gè)局部查詢(xún)結(jié)果中，任一存儲(chǔ)節(jié)點(diǎn)獲得全局查詢(xún)結(jié)果位置的概率僅為1/k。因此，ZOPPM協(xié)議對(duì)最值位置的隱私保護(hù)滿(mǎn)足k-隱藏(k-indistinguishable)特性，其中k為網(wǎng)絡(luò)中構(gòu)成查詢(xún)單元的存儲(chǔ)節(jié)點(diǎn)的數(shù)量。

由上述隱私安全性分析可知，ZOPPM 協(xié)議具有較好的隱私安全保護(hù)能力，不僅能夠確保感知數(shù)據(jù)的隱私安全，同樣能夠保護(hù)最值查詢(xún)結(jié)果的隱私安全性。

4.3.2能耗分析在兩層WSN中，由于存儲(chǔ)節(jié)點(diǎn)具有充足的存儲(chǔ)空間和能量?jī)?chǔ)備，因此，整個(gè)網(wǎng)絡(luò)的生命周期主要受感知節(jié)點(diǎn)的能耗影響。為了盡可能提高網(wǎng)絡(luò)的生命周期，我們以降低感知節(jié)點(diǎn)的能耗為主要目標(biāo)。

在本文的最值查詢(xún)處理方法中，感知節(jié)點(diǎn)的總能耗Etotal的計(jì)算公式如式⑸所示，

其中Ecomm表示感知節(jié)點(diǎn)接收和發(fā)送數(shù)據(jù)所帶來(lái)的通信能耗，Ecomp表示感知節(jié)點(diǎn)進(jìn)行加密和 HMAC計(jì)算所帶來(lái)的計(jì)算能耗。

由ZOPPM協(xié)議可知：每個(gè)感知節(jié)點(diǎn)收到存儲(chǔ)節(jié)點(diǎn)發(fā)送的MQ和MD各一次；并且，每個(gè)包含w位的感知數(shù)據(jù)對(duì)應(yīng)的 Z-O編碼集合將包含w個(gè)HMAC數(shù)據(jù)；此外，每個(gè)查詢(xún)單元中將有一個(gè)感知節(jié)點(diǎn)對(duì)本地感知數(shù)據(jù)進(jìn)行加密，并發(fā)送密文數(shù)據(jù)給存儲(chǔ)節(jié)點(diǎn)。因此，通信能耗Ecomm為

此外，計(jì)算能耗Ecomp為感知節(jié)點(diǎn)進(jìn)行加密和HMAC計(jì)算的能耗之和，則有

由式(6)，式(7)進(jìn)而可以得到感知節(jié)點(diǎn)的總能耗Etotal的最終計(jì)算公式為

而文獻(xiàn)[7]提出的基于前綴成員驗(yàn)證的兩層WSN最值查詢(xún)處理方法(PMV-MQP)，其基本思想為：對(duì)于任一感知節(jié)點(diǎn)si的感知數(shù)據(jù)di∈[dbot,dtop](dbot和dtop分別為感知數(shù)據(jù)的已知下界和上界)，si針對(duì)di和[di,dtop]分別計(jì)算相應(yīng)的HMAC數(shù)值化前綴編碼集合F和S，若di包含w個(gè)二進(jìn)制位，則F和S滿(mǎn)足|F|=w+1和 1≤|S|≤2w-2,si需要計(jì)算的HMAC數(shù)據(jù)總量為|F|+|S|∈[w+2, 3w-1]；同時(shí)，si還對(duì)di進(jìn)行加密處理，然后將 HMAC數(shù)據(jù)和加密數(shù)據(jù)都發(fā)送給存儲(chǔ)節(jié)點(diǎn)，以進(jìn)行后續(xù)的最值查詢(xún)處理?？梢?jiàn)，PMV-MQP總能耗在理論上存在上限和下限；并且，與本文提出的ZOPPM相比，在同等情況下PMV-MQP將消耗更多的通信和計(jì)算能耗。我們將在第5節(jié)對(duì)ZOPPM和PMV-MQP的能耗問(wèn)題作進(jìn)一步的實(shí)驗(yàn)對(duì)比分析。

5 實(shí)驗(yàn)分析

為了對(duì)協(xié)議的性能進(jìn)行比較和分析，本文在文獻(xiàn)[13]的仿真器上實(shí)現(xiàn)了ZOPPM與PMV-MQP。通過(guò)模擬仿真，我們對(duì)這兩種方法的能耗進(jìn)行對(duì)比試驗(yàn)，其中，PMV-MQP(top)和 PMV-MQP(bot)分別表示PMV-MQP的能耗上限和下限；同時(shí)，我們還對(duì)ZOPPM的通信和計(jì)算能耗進(jìn)行對(duì)比實(shí)驗(yàn)，以評(píng)測(cè)通信和計(jì)算能耗對(duì)總能耗的影響情況。本文的實(shí)驗(yàn)環(huán)境為Pentium E5700(雙核3.0 GHz)CPU,3 G內(nèi)存；軟件環(huán)境為 Windows XP操作系統(tǒng)，Eclipse和 Matlab；實(shí)驗(yàn)數(shù)據(jù)集為 Intel Lab Data[14]。

本文采用與文獻(xiàn)[15]相同的能耗計(jì)算方法：無(wú)線(xiàn)通信電路發(fā)送和接收1 byte的能量消耗公式為es=α+γ×dk和er=β，其中，α為通信發(fā)送電路消耗的能量，γ為傳輸放大器消耗的能量，d為傳輸距離，k為路徑損失因子，β為通信接收電路消耗的能量。我們采用文獻(xiàn)[13]的參數(shù)：γ=10 pJ/bit/m2,α=45 nJ/bit,β=135 nJ/bit,k=2。此外，感知數(shù)據(jù)長(zhǎng)度初始設(shè)置為10 bit，加密計(jì)算的初始能耗采用文獻(xiàn)[8]給出的TelosB中利用RC4對(duì)10 bit數(shù)據(jù)進(jìn)行加密的能耗數(shù)據(jù)8.92 μJ，并假設(shè)HMAC計(jì)算的能耗與加密計(jì)算相同。其它參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)

在每一組實(shí)驗(yàn)中，我們通過(guò)在網(wǎng)絡(luò)覆蓋區(qū)域中隨機(jī)分布感知節(jié)點(diǎn)，生成20組不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)(用不同的網(wǎng)絡(luò)ID標(biāo)識(shí))，進(jìn)而通過(guò)計(jì)算20組網(wǎng)絡(luò)的平均能耗值確定最值查詢(xún)的總能耗。具體實(shí)驗(yàn)結(jié)果及分析如下：

(1)在實(shí)驗(yàn)設(shè)置的初始參數(shù)條件下，隨機(jī)生成的20組網(wǎng)絡(luò)的能耗實(shí)驗(yàn)結(jié)果如圖1所示。

由圖1(a)可知，在不同拓?fù)涞木W(wǎng)絡(luò)中，ZOPPM和PMV-MQP的能耗均變化不大，且分布都較為均勻，但ZOPPM的能耗始終低于PMV-MQP。并且，與其能耗下限相比，ZOPPM平均節(jié)省約23.03%的能耗開(kāi)銷(xiāo)。由圖1(b)可知，在ZOPPM的總能耗中，計(jì)算能耗Ecomp和通信能耗Ecomm的變化都不大，但通信能耗占總能耗的絕大部分(約99.96%)?？梢?jiàn)，在隨機(jī)生成的不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)中，ZOPPM和PMV-MQP的能耗均變化不大，但ZOPPM的能耗表現(xiàn)明顯較優(yōu)，其能量消耗絕大部分由數(shù)據(jù)通信產(chǎn)生。

(2)以感知節(jié)點(diǎn)數(shù)量n為自變量，其它參數(shù)保持初始設(shè)置不變，得到如圖2所示的實(shí)驗(yàn)結(jié)果。

由圖2(a)可知，隨著感知節(jié)點(diǎn)數(shù)量n的增長(zhǎng)，感知節(jié)點(diǎn)發(fā)送的數(shù)據(jù)消息也增多，導(dǎo)致ZOPPM和PMV-MQP的總能耗都顯著增長(zhǎng)，其中PMV-MQP的增長(zhǎng)幅度較大，這是由于前者的任一查詢(xún)單元中，僅有一個(gè)感知節(jié)點(diǎn)需要發(fā)送密文數(shù)據(jù)，而后者所有的感知節(jié)點(diǎn)卻都需要發(fā)送。在本組實(shí)驗(yàn)設(shè)置下，ZOPPM的總能耗始終少于PMV-MQP，與后者的能耗下限相比，ZOPPM平均節(jié)省約23.05%的能耗開(kāi)銷(xiāo)。由圖2(b)可知，在ZOPPM的能量消耗中，隨著n的增長(zhǎng)，Ecomm有顯著增長(zhǎng)，雖然Ecomp也同步增長(zhǎng)，但由于其占總能耗的比重非常小(平均約占0.02%)，其增長(zhǎng)趨勢(shì)不明顯。

(3)以w為自變量，其它參數(shù)保持初始設(shè)置不變，得到如圖3所示的實(shí)驗(yàn)結(jié)果。

由圖3(a)可知，隨著感知數(shù)據(jù)長(zhǎng)度w的增大，ZOPPM和PMV-MQP的總能耗也隨之增大，這是由于查詢(xún)單元中的所有感知節(jié)點(diǎn)都需要傳送HMAC數(shù)據(jù)，而w的長(zhǎng)度與感知節(jié)點(diǎn)傳送HMAC數(shù)據(jù)的數(shù)量成正比，因此，兩者的總能耗都同步增長(zhǎng)，但ZOPPM的總能耗始終少于PMV-MQP，與后者的能耗下限相比，ZOPPM平均節(jié)省約17.1%的能耗開(kāi)銷(xiāo)。由圖3(b)可知，在ZOPPM消耗的總能量中，通信能耗占總能耗的絕大部分(平均約99.96%)，計(jì)算能耗所占比重則非常小。

綜合上述實(shí)驗(yàn)結(jié)果及分析可知：本文的ZOPPM的能耗優(yōu)于文獻(xiàn)[7]提出的PMV-MQP，在本文的實(shí)驗(yàn)設(shè)置條件下，ZOPPM比PMV-MQP的能耗下限平均節(jié)省近 20%的能量消耗；并且，在ZOPPM 協(xié)議中，收發(fā)數(shù)據(jù)的通信能耗占總能耗的絕大部分，而計(jì)算能耗所占的比重較小。

圖1 不同網(wǎng)絡(luò)拓?fù)湎碌哪芎膶?shí)驗(yàn)結(jié)果

圖2 以n為自變量時(shí)的能耗實(shí)驗(yàn)結(jié)果

圖3 以w為自變量時(shí)的能耗實(shí)驗(yàn)結(jié)果

6 總結(jié)

數(shù)據(jù)隱私保護(hù)問(wèn)題是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中具有共性要求的問(wèn)題，在諸如環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生、智能交通、國(guó)防軍事等各種重要領(lǐng)域都有著迫切的需求，是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)研究中的一個(gè)熱點(diǎn)問(wèn)題。然而，現(xiàn)有的兩層WSNs重點(diǎn)關(guān)注范圍等查詢(xún)處理方法，對(duì)最值查詢(xún)處理方法的研究相對(duì)較少。本文提出了一種基于Z-O編碼的兩層WSNs隱私保護(hù)最值查詢(xún)處理協(xié)議。在該協(xié)議中，感知節(jié)點(diǎn)利用Z-O編碼機(jī)制，并結(jié)合Hash消息身份驗(yàn)證編碼方法，對(duì)本地感知數(shù)據(jù)進(jìn)行HMAC數(shù)值化Z-O編碼處理，并發(fā)送至存儲(chǔ)節(jié)點(diǎn)；而存儲(chǔ)節(jié)點(diǎn)則利用Z-O編碼的數(shù)值比較特性，實(shí)現(xiàn)在無(wú)需感知數(shù)據(jù)明文參與下的數(shù)值線(xiàn)性關(guān)系比較，進(jìn)而獲得所在查詢(xún)單元中產(chǎn)生局部最值的感知節(jié)點(diǎn)，并通知該感知節(jié)點(diǎn)計(jì)算并傳送加密數(shù)據(jù)，然后構(gòu)造局部查詢(xún)結(jié)果并發(fā)送給Sink；最終由Sink完成最值查詢(xún)結(jié)果的計(jì)算，并返回給用戶(hù)。理論分析和實(shí)驗(yàn)結(jié)果表明，ZOPPM 協(xié)議能夠確保感知數(shù)據(jù)和最值查詢(xún)結(jié)果的隱私安全性，并且其能耗優(yōu)于現(xiàn)有的方法。

[1]Gnawali O, Jang K Y, Paek J,et al.. The tenet architecture for tiered sensor networks[C]. Proceedings of the 4th ACM Conference on Embedded Networked Sensor Systems,Boulder, Colorado, USA, 2006: 153-166.

[2]Yang D, Misra S, Fang X,et al.. Two-tiered constrained relay node placement in wireless sensor networks: computational complexity and efficient approximations[J].IEEE Transactions on Mobile Computing, 2012, 11(8): 1399-1411.

[3]Chen F and Liu A X. SafeQ: secure and efficient query processing in sensor networks[C]. 29th IEEE International Conference on Computer Communications, San Diego, CA,USA, 2010: 1-9.

[4]Sheng B and Li Q. Verifiable privacy-preserving range query in two-tiered sensor networks[C]. 27th IEEE International Conference on Computer Communications, Phoenix, AZ,USA, 2008: 46-50.

[5]Shi J, Zhang R, and Zhang Y. Secure range queries in tiered sensor networks[C]. 28th IEEE International Conference on Computer Communications, Rio de Janeiro, Brazil, 2009:945-953.

[6]Shi J, Zhang R, and Zhang Y. A spatiotemporal approach for secure range queries in tiered sensor networks[J].IEEE Transactions on Wireless Communications, 2011, 10(1):264-273.

[7]Yao Y, Xiong N, Park J H,et al.. Privacy-preserving max/min query in two-tiered wireless sensor networks[OL].Computers & Mathematics with Applications. http://www.sciencedirect.com/science/article/pii/S08981221120011 74. 2012, 2.

[8]Groat M M, Hey W, and Forrest S. KIPDA:kindistinguishable privacy-preserving data aggregation in wireless sensor networks[C]. 30th IEEE International Conference on Computer Communications, Shanghai, China,2011: 2024-2032.

[9]Lin H Y and Tzeng W G. An efficient solution to the millionaires’ problem based on homomorphic encryption[C].Proceedings of the 3rd International Conference on Applied Cryptography and Network Security, New York, NY, USA,2005: 97-134.

[10]Krawczyk H, Canetti R, and Bellare M. HMAC:keyed-hashing for message authentication[R]. RFC 2104,1997.

[11]Yao A C. Protocols for secure computations[C]. 23rd Annual Symposium on Foundations of Computer Science, Chicago,Illinois, USA, 1982: 160-164.

[12]Bozovic V, Socek D, Steinwandt R,et al.. Multi-authority attribute-based encryption with honest-but-curious central authority[J].International Journal of Computer Mathematics,2012, 89(3): 268-283.

[13]Coman A, Sander J, and Nascimento M A. Adaptive processing of historical spatial range queries in peer-to-peer sensor networks[J].Distributed and Parallel Databases, 2007,22(2): 133-163.

[14]Samuel M. Intel lab data[OL]. http://db.csail.mit.edu/labdata/labdata.html. 2004.6.

[15]Coman A, Nascimento A M, and Sander J. A framework for spatio-temporal query processing over wireless sensor networks[C]. Proceeedings of the 1st International Workshop on Data Management for Sensor Networks, Toronto, Canada,2004: 104-110.