哈希算法在物聯(lián)網(wǎng)數(shù)據(jù)存儲中的應(yīng)用

王曦

摘要：物聯(lián)網(wǎng)是傳統(tǒng)互聯(lián)網(wǎng)在現(xiàn)代社會應(yīng)用的拓展和延伸，同時伴隨著大數(shù)據(jù)時代的到來。作為典型的分布式存儲系統(tǒng)，哈希算法完全適應(yīng)于物聯(lián)網(wǎng)的應(yīng)用環(huán)境。本文主要分析研究哈希算法在物聯(lián)網(wǎng)數(shù)據(jù)存儲方面的典型應(yīng)用，輔助完成物聯(lián)網(wǎng)分布式數(shù)據(jù)存儲。同時，通過定義吞吐量及響應(yīng)延時等性能指標，作者在OPNET Modeler仿真軟件中進行簡單的仿真驗證，進而對基于哈希算法的存儲器模型進行性能評估。

關(guān)鍵詞：物聯(lián)網(wǎng)；哈希算法；分布式存儲；數(shù)據(jù)存儲；

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）27-0226-03

傳統(tǒng)的互聯(lián)網(wǎng)應(yīng)用模式已經(jīng)不能滿足用戶種類繁多的需求及傳統(tǒng)行業(yè)的發(fā)展需要，物聯(lián)網(wǎng)應(yīng)運而生。“物聯(lián)網(wǎng)”被稱作是繼計算機和互聯(lián)網(wǎng)之后的又一次信息領(lǐng)域革命[1]。物聯(lián)網(wǎng)被定義為是利用射頻識別設(shè)備、紅外傳感設(shè)備、全球定位系統(tǒng)（GPS）、激光掃描儀等信息采集設(shè)備，根據(jù)設(shè)定的規(guī)則，把任何物品與互聯(lián)網(wǎng)相連接，使用各種通信方式進行信息交互，以實現(xiàn)智能化定位、識別、監(jiān)控和管理的特定網(wǎng)絡(luò)[2-3]。物聯(lián)網(wǎng)應(yīng)用涵蓋了日常生活的機會所有領(lǐng)域，包括建筑、交通、通信、農(nóng)業(yè)、工作及電商平臺等，具體應(yīng)用如圖1所示[4]。

物聯(lián)網(wǎng)是以互聯(lián)網(wǎng)技術(shù)為前提的條件下而建立起來的，并將其客戶端拓展到所有物品與所有物品之間，進行數(shù)據(jù)通信和信息交互的全新網(wǎng)絡(luò)應(yīng)用模式[5]。物聯(lián)網(wǎng)主要分為感知層、網(wǎng)絡(luò)層以及應(yīng)用層等三個層次[6]，其承載著海量用戶數(shù)據(jù)及其傳輸過程任務(wù)，優(yōu)秀的存儲模型至關(guān)重要。

物聯(lián)網(wǎng)系統(tǒng)作為典型的分布式存儲系統(tǒng)，是大量普通PC服務(wù)器通過Internet互聯(lián)，對外作為一個整體提供存儲服務(wù)，其具有可擴展性、低成本、高性能、易用性等優(yōu)點[7-8]。

本文主要分析研究哈希算法在物聯(lián)網(wǎng)數(shù)據(jù)存儲方面的典型應(yīng)用，輔助完成物聯(lián)網(wǎng)分布式數(shù)據(jù)存儲。同時，通過定義吞吐量及響應(yīng)延時等性能指標，作者在OPNET Modeler仿真軟件中進行簡單的仿真驗證，進而對基于哈希算法的存儲器模型進行性能評估。

1 哈希算法在物聯(lián)網(wǎng)中的應(yīng)用

1.1 物聯(lián)網(wǎng)系統(tǒng)結(jié)構(gòu)

物聯(lián)網(wǎng)是以互聯(lián)網(wǎng)技術(shù)為前提的條件下而建立起來的，并將其客戶端拓展到所有物品與所有物品之間，進行數(shù)據(jù)通信和信息交互的全新網(wǎng)絡(luò)應(yīng)用模式[9]。它也是互聯(lián)網(wǎng)應(yīng)用和發(fā)展的結(jié)果和總結(jié)。物聯(lián)網(wǎng)主要分為感知層、網(wǎng)絡(luò)層以及應(yīng)用層等三個層次。

（1）感知層涵蓋條形碼和識別設(shè)備、射頻標簽和識別器、圖像采集儀、全球定位設(shè)備及其他傳感器網(wǎng)絡(luò)設(shè)備，主要功能是感知環(huán)境，獲取數(shù)據(jù)信息，這與人體結(jié)構(gòu)中皮膚和五官的功能類似。

（2）網(wǎng)絡(luò)層類似于物聯(lián)網(wǎng)的神經(jīng)中樞系統(tǒng)，主要完成信息交互及處理。網(wǎng)絡(luò)層囊括了通信系統(tǒng)、網(wǎng)絡(luò)處理中心、信息處理中心以及智能事務(wù)應(yīng)用處理中心等。網(wǎng)絡(luò)層對感知層采集的信息進行分類處理，準備傳送到不同的應(yīng)用模式中。

（3）應(yīng)用層融合了物聯(lián)網(wǎng)的應(yīng)用模式與用戶需求，實現(xiàn)其智能化管理。應(yīng)用層結(jié)合了物聯(lián)網(wǎng)技術(shù)與傳統(tǒng)行業(yè)，完成行業(yè)多種態(tài)勢的運行機制，此過程類似于與社會職能分配，最終形成智能化人類社會。

1.2 哈希算法在物聯(lián)網(wǎng)存儲方面的應(yīng)用設(shè)計

物聯(lián)網(wǎng)系統(tǒng)區(qū)別于傳統(tǒng)單機系統(tǒng)在于能夠?qū)?shù)據(jù)分布到多個節(jié)點，并在多個節(jié)點之間實現(xiàn)負載均衡。將數(shù)據(jù)分散到多臺機器后，需要盡量保證多臺機器之間的負載是相對均衡的。影響和評價網(wǎng)絡(luò)存儲負載的因素有多種，包括設(shè)備的負載值、CPU運行情況、內(nèi)存容量以及網(wǎng)絡(luò)等資源占用情況、數(shù)據(jù)讀寫請求數(shù)等，物聯(lián)網(wǎng)系統(tǒng)需要可以判斷網(wǎng)絡(luò)是否負載過重，并且能夠自適應(yīng)地將其應(yīng)用服務(wù)遷移到負載壓力相對較小的設(shè)備中去，實現(xiàn)自動負載均衡[10]。

哈希數(shù)據(jù)分布采用典型的哈希算法。哈希算法的思想是：系統(tǒng)的所有節(jié)點均可被分配隨機值， 值組成哈希環(huán)。當(dāng)需要進行數(shù)據(jù)存儲時，根據(jù)計算得來的（主鍵）的哈希值，然后按照順時針方向?qū)⑵浯娣诺谝粋€與該哈希值的值匹配的所在的位置處。該哈希算法的優(yōu)點在于節(jié)點的加入或者刪除操作僅僅會對哈希環(huán)中相鄰節(jié)點產(chǎn)生影響，而對其他節(jié)點不會產(chǎn)生影響。

如圖2所示，將哈希空間的大小定義為，典型哈希算法如下：

Step1：首先求出每個服務(wù)器的值，將其配置到一個的圓環(huán)區(qū)間上；

Step2：其次使用同樣的方法求出待存儲對象的主鍵哈希值，也將其配置到這個圓環(huán)上；

Step3：然后從數(shù)據(jù)映射的位置開始順時針查找，將數(shù)據(jù)分布到找到的第一個服務(wù)器節(jié)點。

為了查找集群中的服務(wù)器，需要維護每臺機器在哈希環(huán)中位置信息，本文采用的復(fù)雜度的獲取位置信息的方法。

將哈希空間定義為（即），以典型的Chord數(shù)據(jù)存儲系統(tǒng)為例，為了提高查找的效率，其在所有服務(wù)器中維護一個長度為的路由表。

其中代表哈希環(huán)中某個服務(wù)器的表示ID，路由表中的第個元素描述了編號為的所有后繼節(jié)點。

如果位置信息占用的空間容量，每臺服務(wù)器均對其前一個以及后一個節(jié)點的位置信息有所記錄。由于其維護的節(jié)點位置信息的空間復(fù)雜度為，而且每一次查找均可能會遍歷整個哈希環(huán)中的所有服務(wù)器節(jié)點，因此時間復(fù)雜度為，其中，N表示服務(wù)器數(shù)量。本文通過維護的容量信息，查找的時間復(fù)雜度改進為。

2 哈希算法的物聯(lián)網(wǎng)應(yīng)用測試

為了驗證本文設(shè)計的應(yīng)用了哈希算法的物聯(lián)網(wǎng)存儲系統(tǒng)的通信效果，作者在OPNET Modeler仿真軟件中進行仿真驗證，分析存儲性能和網(wǎng)絡(luò)性能等相關(guān)指標。

2.1 衡量指標定義

物聯(lián)網(wǎng)數(shù)據(jù)存儲系統(tǒng)常見的評價指標主要包括系統(tǒng)的吞吐能力和系統(tǒng)的響應(yīng)時間。本文通過下式的平均值進行吞吐量定義，其中表示吞吐量，為仿真單位周期，和分別表示單位時間內(nèi)的讀操作數(shù)和寫操作數(shù)。

系統(tǒng)的響應(yīng)延遲，指從某個請求發(fā)出到接收到返回結(jié)果消耗的時間。為了體現(xiàn)系統(tǒng)整體性能，本文統(tǒng)計平均響應(yīng)延時，假設(shè)成功獲取組數(shù)據(jù)，則通過下式計算，

上式中，表示第個分組的響應(yīng)延時。

2.2 哈希算法存儲系統(tǒng)性能分析

在OPNET Modeler仿真實驗中，設(shè)計兩臺服務(wù)器節(jié)點，每臺服務(wù)器分別連接5個存儲單元，服務(wù)器之間能通過有線網(wǎng)絡(luò)進行通信，10個物聯(lián)網(wǎng)感知器通過用戶服務(wù)器對存儲單元進行讀操作和寫操作。讀操作即定時從存儲單元獲得信息，寫操作為定時將物聯(lián)網(wǎng)感知器采集的信息發(fā)送給存儲器進行保存，發(fā)送及接收頻率為10M/ms，且根據(jù)設(shè)定的哈希分布規(guī)則選取目標存儲器，仿真時間為20min，然后統(tǒng)計仿真結(jié)果進行對比分析。

通過測試10臺存儲單元所存儲的數(shù)據(jù)容量，由結(jié)果可知，各存儲器所存儲的信息含量基本相等，基本維持在11718M左右，體現(xiàn)了本文設(shè)計的存儲模型具有較好的公平性和一致性，不會對某一個存儲單元或者服務(wù)器造成應(yīng)用壓力。

平均吞吐量及響應(yīng)延時與順序分布的存儲器模型相比，性能有所改善，圖3的仿真結(jié)果表明本文設(shè)計的基于哈希分布的分布式存儲模型使系統(tǒng)的吞吐量增加了12.2%，響應(yīng)延時減少了9.8%。如果集群規(guī)模數(shù)量過多，不能保證所有的服務(wù)器在同一個機架下，系統(tǒng)設(shè)計以及性能分析都會有所不同。只有理解存儲系統(tǒng)的底層設(shè)計和實現(xiàn)，并在實踐中不斷地練習(xí)，性能估算才會更加準確。整體而言，哈希算法可以使存儲器的網(wǎng)絡(luò)性能有所提高。

3 結(jié)論

物聯(lián)網(wǎng)是傳統(tǒng)互聯(lián)網(wǎng)在現(xiàn)代社會應(yīng)用的拓展和延伸，同時伴隨著大數(shù)據(jù)時代的到來。作為典型的分布式存儲系統(tǒng)，哈希算法完全適應(yīng)于物聯(lián)網(wǎng)的應(yīng)用環(huán)境。本文主要分析研究哈希算法在物聯(lián)網(wǎng)數(shù)據(jù)存儲方面的典型應(yīng)用，輔助完成物聯(lián)網(wǎng)分布式數(shù)據(jù)存儲。同時，通過定義吞吐量及響應(yīng)延時等性能指標，作者在OPNET Modeler仿真軟件中進行仿真驗證，進而對基于哈希算法的存儲器模型進行性能評估。仿真結(jié)果表明本文設(shè)計的基于哈希分布的分布式存儲模型較順序存儲分布策略使系統(tǒng)在通信性能方面有了顯著的提高。作者也會在今后的研究工作中對哈希算法等數(shù)據(jù)結(jié)構(gòu)在物聯(lián)網(wǎng)中的應(yīng)用設(shè)計進行進一步的優(yōu)化。

參考文獻：

[1] Gubbi J， Buyya R， Marusic S， et al. Internet of Things （IoT）： A Vision， Architectural Elements， and Future Directions [J]. Future Generation Computer Systems， 2012， 29（7）：1645–1660.

[2] Zhu Q， Wang R， Chen Q， et al. IOT Gateway： BridgingWireless Sensor Networks into Internet of Things[C]// 2010 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing. IEEE Computer Society， 2010：347-352.

[3] Kopetz H. Internet of Things [M]// Real-Time Systems. Springer US， 2011：307-323.

[4] Chalkiadaki M， Magoutis K. Managing Service Performance in the Cassandra Distributed Storage System[C]// 2013 IEEE 5th International Conference on Cloud Computing Technology and Science. IEEE Computer Society， 2013：64-71.

[5] Trushkowsky B， Bod&#， Peter K， et al. The SCADS director： scaling a distributed storage system under stringent performance requirements[C]// Usenix Conference on File & Storage Technologies. USENIX Association， 2011：163-176.

[6] Vermeulen A H， Atlas A B， Barth D M， et al. Distributed storage system with web services client interface： US， US 7716180 B2[P]. 2010.

[7] Lubbers C E. Atomic cache transactions in a distributed storage system： US， US 20060294300 A1[P]. 2006.

[8] Rozsnyai S， Slominski A， Doganata Y. Large-Scale Distributed Storage System for Business Provenance[C]// 2011 IEEE 4th International Conference on Cloud Computing. IEEE Computer Society， 2011：516-524.

[9] Tanimura Y， Hidetaka K， Kudoh T， et al. A distributed storage system allowing application users to reserve I/O performance in advance for achieving SLA[C]// IEEE/ACM International Conference on Grid Computing. IEEE， 2010：193-200.

[10] Choi S C， Youn H Y， Choi J S. Symmetric tree replication protocol for efficient distributed storage system[C]// Computational Science - ICCS 2003， International Conference， Melbourne， Australia and St. Petersburg， Russia， June 2-4， 2003. Proceedings， Part III. 2003：474-484.