[發(fā)明專利]一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510927383.1
• 申請(qǐng)日: 2015-12-14
• 公開（公告）號(hào): CN105578575B
• 公開（公告）日: 2019-02-26
• 發(fā)明（設(shè)計(jì)）人: 胡海峰;何杰芳;吳建盛
• 申請(qǐng)（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號(hào): H04W52/02
• 分類號(hào): H04W52/02;H04W84/18
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 田凌濤

本發(fā)明涉及一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法，針對(duì)無線傳感網(wǎng)絡(luò)中傳感節(jié)點(diǎn)之間相互傳輸?shù)母呔S數(shù)據(jù)，設(shè)計(jì)采用低維的局部敏感哈希指紋，有效降低了傳感節(jié)點(diǎn)的傳輸能耗，增加了網(wǎng)絡(luò)生命周期；而且本發(fā)明整個(gè)設(shè)計(jì)的分布式相似性查詢方法，有效克服了傳統(tǒng)數(shù)據(jù)查詢過程中，向量計(jì)算量隨維度增加呈現(xiàn)指數(shù)倍增的問題，解決了原始局部敏感哈希表數(shù)量需求過大的問題，提高了空間利用率；且相似性權(quán)重機(jī)制的引入，有效地剔除了非相似性數(shù)據(jù)，使驗(yàn)證過程中需要驗(yàn)證的數(shù)據(jù)量變少，大大提高了算法的效率，并有效地提高了相似性查詢的效率。

技術(shù)領(lǐng)域

本發(fā)明涉及一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法，屬于無線傳感網(wǎng)絡(luò)下的相似查詢技術(shù)領(lǐng)域。

背景技術(shù)

無線傳感網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是當(dāng)前在國(guó)際上備受關(guān)注、涉及多學(xué)科高度交叉、知識(shí)高度集成的前沿?zé)狳c(diǎn)研究領(lǐng)域，被認(rèn)為是21世紀(jì)最重要的技術(shù)之一。WSN系統(tǒng)通常包括傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)，大量傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域，通過自組織的方式形成網(wǎng)絡(luò)，負(fù)責(zé)收集監(jiān)測(cè)區(qū)域的數(shù)據(jù)；匯聚節(jié)點(diǎn)收集傳感節(jié)點(diǎn)的數(shù)據(jù)，經(jīng)過數(shù)據(jù)整合，提交給管理節(jié)點(diǎn)；用戶可以通過管理節(jié)點(diǎn)對(duì)傳感器網(wǎng)絡(luò)進(jìn)行配置管理、發(fā)布監(jiān)測(cè)任務(wù)以及收集監(jiān)測(cè)數(shù)據(jù)。WSN將邏輯上的信息世界和客觀上的物理世界融合在一起，它在工業(yè)、農(nóng)業(yè)、交通、軍事、安全、醫(yī)療、空間探測(cè)等眾多領(lǐng)域都有著廣泛的應(yīng)用。

由于WSN的傳感節(jié)點(diǎn)通常由電池供電，可用能量有限，因此能耗是WSN的一個(gè)重要問題，特別是在相似數(shù)據(jù)查詢時(shí)，匹配所有節(jié)點(diǎn)的數(shù)據(jù)將消耗大量能量，縮短網(wǎng)絡(luò)的生命周期。

局部敏感哈希(Locality Sensitive Hashing，LSH)是最近非常流行的一種相似性搜索算法，因其不錯(cuò)的搜索效率以及較強(qiáng)的高維適應(yīng)性而被廣泛應(yīng)用于各個(gè)領(lǐng)域。其基本思想是通過一組特殊的哈希函數(shù)，對(duì)數(shù)據(jù)進(jìn)行哈希，使距離近的點(diǎn)沖突的概率遠(yuǎn)大于距離遠(yuǎn)的點(diǎn)沖突的概率；在查詢時(shí)，使用相同的函數(shù)，將查詢點(diǎn)哈希到桶中，選取桶中數(shù)據(jù)作為候選點(diǎn)進(jìn)行距離判斷，最終確定相似數(shù)據(jù)。

傳統(tǒng)LSH技術(shù)的主要問題是為了保證足夠的召回率和精確率通常需要數(shù)以百計(jì)的哈希表，這就給索引的存儲(chǔ)帶來很大的壓力，龐大的哈希表占用過多的內(nèi)存，在海量文件系統(tǒng)中，LSH的應(yīng)用遇到瓶頸。

發(fā)明內(nèi)容

針對(duì)上述技術(shù)問題，本發(fā)明所要解決的技術(shù)問題是提供一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法，解決了無線傳感網(wǎng)絡(luò)的能耗問題，以及數(shù)據(jù)相似性查詢的效率問題。

本發(fā)明為了解決上述技術(shù)問題采用以下技術(shù)方案：本發(fā)明設(shè)計(jì)了一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法，針對(duì)無線傳感網(wǎng)絡(luò)中各個(gè)數(shù)據(jù)項(xiàng)進(jìn)行L組K維局部敏感哈希映射，構(gòu)建各個(gè)數(shù)據(jù)項(xiàng)分別所映射的L組K維局部敏感哈希指紋值，即一個(gè)數(shù)據(jù)項(xiàng)對(duì)應(yīng)L組局部敏感哈希指紋值集合，各組局部敏感哈希指紋值集合分別包括K維局部敏感哈希指紋值，L和K為預(yù)設(shè)整數(shù)值；所述分布式相似性查詢方法包括如下步驟：

步驟001.針對(duì)查詢數(shù)據(jù)項(xiàng)V_查詢，獲得其進(jìn)行L組K維局部敏感哈希映射時(shí)，各組各維按預(yù)設(shè)切割寬度W進(jìn)行分割取整前的映射值進(jìn)入步驟002；其中，l＝1、…、L，k＝1、…、K，A_l,k和B_l,k為無線傳感網(wǎng)絡(luò)中各數(shù)據(jù)項(xiàng)進(jìn)行L組K維局部敏感哈希映射時(shí)，各組各維所對(duì)應(yīng)的隨即參數(shù)，且無線傳感網(wǎng)絡(luò)中各個(gè)數(shù)據(jù)項(xiàng)之間所對(duì)應(yīng)各組各維的A_l,k和B_l,k彼此對(duì)應(yīng)相同，A_l,k為查詢數(shù)據(jù)項(xiàng)V_查詢對(duì)應(yīng)第l組第k維局部敏感哈希映射時(shí)，與查詢數(shù)據(jù)項(xiàng)V_查詢維數(shù)相同，且每一維服從P穩(wěn)態(tài)分布的隨機(jī)高維向量；B_l,k為查詢數(shù)據(jù)項(xiàng)V_查詢對(duì)應(yīng)第l組第k維局部敏感哈希映射時(shí)，屬于[0,W]之間的隨機(jī)數(shù)；