無線傳感器網(wǎng)絡(luò)分布式存儲(chǔ)策略的研究

1、無線傳感器網(wǎng)絡(luò)分布式存儲(chǔ)策略的研究姓 名 學(xué) 院 專 業(yè) 指導(dǎo)教師 職 稱 年 月 日設(shè)計(jì)任務(wù)書 題目無線傳感器網(wǎng)絡(luò)分布式存儲(chǔ)策略的研究學(xué)生姓名學(xué)院名稱專業(yè)班級課題類型實(shí)際課題課題意義對無線傳感器網(wǎng)絡(luò)的應(yīng)用多種多樣，范圍遍及科學(xué)數(shù)據(jù)收集、環(huán)境監(jiān)測、軍事等。早期的無線傳感器網(wǎng)絡(luò)在科學(xué)數(shù)據(jù)收集以及監(jiān)控往往采用多對一模型，即有專門的數(shù)據(jù)采集者去采集傳感器所產(chǎn)生的數(shù)據(jù)。這樣的方式突顯出的弊端有無線傳感器節(jié)點(diǎn)自組性差，不能夠提供實(shí)時(shí)的數(shù)據(jù)保障。因此分布式無線傳感器網(wǎng)絡(luò)的存儲(chǔ)策略成為本次論文的研究的主題，意在尋求優(yōu)秀的數(shù)據(jù)收集、數(shù)據(jù)存儲(chǔ)的方案。對無線傳感器網(wǎng)絡(luò)的研究有著十分重要的意義，無線傳感器網(wǎng)絡(luò)技術(shù)在

2、科學(xué)數(shù)據(jù)收集中十分重要，因此在無線傳感器網(wǎng)絡(luò)中選取數(shù)據(jù)的檢索與存儲(chǔ)路線成為本次課題的目的。最終實(shí)現(xiàn)更加正確、迅速、高效率地實(shí)現(xiàn)數(shù)據(jù)的傳輸。任務(wù)與進(jìn)度要求開題報(bào)告、任務(wù)書的填寫、提交、審核深入研究與課題相關(guān)國內(nèi)外文獻(xiàn)資料，熟悉Matlab仿真工具完成理論部分總結(jié)并進(jìn)行公式推導(dǎo)。完成Matlab主要公式調(diào)用演示模型模塊 完成核心模塊并進(jìn)行系統(tǒng)調(diào)試，在調(diào)試中進(jìn)一步完善系統(tǒng)的各項(xiàng)功能，同時(shí)開始撰寫畢業(yè)論文對系統(tǒng)進(jìn)行修改及調(diào)整，根據(jù)老師意見修改論文，并進(jìn)行畢業(yè)設(shè)計(jì)答辯的準(zhǔn)備答辯主要參考文獻(xiàn)1 R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, an

3、d D. Culler,“An analysis of a large scale habitat monitoring application,” in Proc.2nd Int. Conf. Embedded Netw. SenSys, New York, 2004, pp. 214226.2 C. Intanagonwiwat, R. Govindanj, and D. Estrin, “Directed diffusion:A scalable and robust communication paradigm for sensor networks,” in Proc. 6th An

4、nu. Int. Conf. MobiCom, Aug. 2000, pp. 5667.3 S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and D. Estrin, “Datacentric storage in sensornets,” Comput. Commun. Rev., vol. 33, no. 1,pp. 137142, 2003.起止日期備注院長 教研室主任 指導(dǎo)教師 開題報(bào)告表 姓名學(xué)院專業(yè)班級題目無線傳感器網(wǎng)絡(luò)分布式存儲(chǔ)策略的研究指導(dǎo)教師一、 與本課題有關(guān)的國內(nèi)外研究情況、課題研究的主要內(nèi)容、目的和意義：1. 國內(nèi)外研究情

5、況：無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks, WSN）是由按照一定拓?fù)浣Y(jié)構(gòu)的一定數(shù)量的靜止或移動(dòng)的廉價(jià)微型傳感器節(jié)點(diǎn)，以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)。它是當(dāng)前在國際上備受關(guān)注的、涉及多學(xué)科高度交叉、知識(shí)高度集成的前沿?zé)狳c(diǎn)研究領(lǐng)域。特別是隨著物聯(lián)網(wǎng)產(chǎn)業(yè)的快速興起，無線傳感器網(wǎng)絡(luò)作為物聯(lián)網(wǎng)中的核心產(chǎn)業(yè)，也隨之得到了更多的關(guān)注與研究。它擴(kuò)展了人們的信息獲取能力，將客觀世界的物理信息同傳輸網(wǎng)絡(luò)連接在一起，在下一代網(wǎng)絡(luò)中將為人們提供最直接、最有效、最真實(shí)的信息，廣泛應(yīng)用于環(huán)境監(jiān)測1、農(nóng)業(yè)生產(chǎn)2、定位跟蹤3、軍事4等領(lǐng)域中。國內(nèi)外的相關(guān)研究者針對特定的應(yīng)用需求，將無線傳感器網(wǎng)

6、絡(luò)的存儲(chǔ)模式分為以下三種策略：外部存儲(chǔ)（External Storage, ES）、本地存儲(chǔ)（Local Storage, LS）和分布式存儲(chǔ)（Data-Centric Storage, DCS）6。外部存儲(chǔ)是指每個(gè)傳感器節(jié)點(diǎn)將感知到的數(shù)據(jù)立即發(fā)送到 Sink 節(jié)點(diǎn)上進(jìn)行存儲(chǔ)，所有的查詢請求在 Sink 節(jié)點(diǎn)上執(zhí)行查詢。文獻(xiàn)7提出了著名的基于外部存儲(chǔ)策略的定向擴(kuò)散（Directed Diffusion）存儲(chǔ)方式。它是基于訂閱發(fā)布模式的以需求為中心的路由方式。在定向擴(kuò)散中，每個(gè)采集數(shù)據(jù)的Sink節(jié)點(diǎn)都向網(wǎng)絡(luò)中使用洪泛法發(fā)送出自己的請求，且在每一個(gè)請求中，都可以包含任意多的屬性來支持復(fù)雜數(shù)據(jù)的表達(dá)

7、和查詢。因此定向擴(kuò)散可以勝任任何類型的查詢。本地存儲(chǔ)是指傳感器將監(jiān)測到的數(shù)據(jù)直接保存在自身中，因此存儲(chǔ)數(shù)據(jù)不會(huì)花費(fèi)任何的通信代價(jià)。Cornell大學(xué)的COUGAR系統(tǒng)8即屬于基于本地的存儲(chǔ)策略。它是將整個(gè)傳感器網(wǎng)絡(luò)看成是一個(gè)大型分布式傳感器數(shù)據(jù)庫系統(tǒng)，每個(gè)傳感器對應(yīng)于該分布式數(shù)據(jù)庫的一個(gè)節(jié)點(diǎn)，其中傳感器感知獲得的數(shù)據(jù)用時(shí)間序列來表示，存儲(chǔ)數(shù)據(jù)用關(guān)系表示，在特定時(shí)間的查詢用相應(yīng)時(shí)間的視圖表示。它盡可能的將計(jì)算有用信息的工作留在傳感網(wǎng)絡(luò)中進(jìn)行。以數(shù)據(jù)為中心的存儲(chǔ)（Data-Centric Storage, DCS）也稱為分布式存儲(chǔ)，它是使用事件來表示節(jié)點(diǎn)感知的數(shù)據(jù)的屬性值及其范圍，所有的事件都被命

8、名，相同名稱的數(shù)據(jù)被映射到相同的地理位置，距離此地理位置最近的節(jié)點(diǎn)用來存儲(chǔ)數(shù)據(jù)。特定事件查詢被路由至合適的存儲(chǔ)節(jié)點(diǎn)。GEM(Graph Embedding，GEM)9 是一種基于嵌入地圖輔助路由的以數(shù)據(jù)為中心的分布式存儲(chǔ)方式。它的主要原理是在每一個(gè)傳感器中嵌入一幅地圖。為了能夠支持以數(shù)據(jù)為中心的分布存儲(chǔ),將每一個(gè)感應(yīng)到的數(shù)據(jù)對象都映射到一個(gè)標(biāo)識(shí)，并借此將不同的數(shù)據(jù)對象存儲(chǔ)到不同的節(jié)點(diǎn)中。文獻(xiàn)10提出了經(jīng)典的采用地理散列函數(shù)(Geographic Hash Table, GHT) 進(jìn)行數(shù)據(jù)存儲(chǔ)。GHT采用了基于數(shù)據(jù)命名的思想，將每種類型的事件映射到傳感器網(wǎng)絡(luò)中的一個(gè)地理位置，距離該地理位置最近的

9、節(jié)點(diǎn)成為此事件的存儲(chǔ)節(jié)點(diǎn)，因此查詢只需要發(fā)送到該查詢所包含事件的節(jié)點(diǎn)上而不需要泛洪查詢，這樣便可大大地節(jié)約查詢時(shí)所消耗的能量。2課題研究的主要內(nèi)容：本文參照GHT模式、簡單雙直紋模式和球面雙直紋模式的思想并用其算法模擬了不同情況下三種模式的表現(xiàn)，并且根據(jù)不同應(yīng)用環(huán)境分析了適用的檢索模式。在介紹檢索模式時(shí)根據(jù)分析例子中不同環(huán)境特點(diǎn)選取檢索模式，無線傳感器網(wǎng)絡(luò)在應(yīng)用球面雙直紋模式時(shí)根據(jù)不同環(huán)境特點(diǎn)的敘述選取合適的檢索模式。3目的和意義：對無線傳感器網(wǎng)絡(luò)的研究有著十分重要的意義，無線傳感器網(wǎng)絡(luò)技術(shù)例如在科學(xué)數(shù)據(jù)收集中十分重要，因此在無線傳感器網(wǎng)絡(luò)中選取數(shù)據(jù)的檢索與存儲(chǔ)路線成為本次課題的目的。最終實(shí)現(xiàn)

10、更加正確、迅速、高效率地實(shí)現(xiàn)數(shù)據(jù)的傳輸。主要參考文獻(xiàn)：1 Xianghui Cao, Jiming Chen, Yan Zhang, Youxian Sun, Development of an integrated wireless sensor network micro-environmental monitoring system, ISA Transactions, July 2008, 47(3):247-255 2 Vougioukas, S., et al., Influence of foliage on radio path losses (PLs) for wireles

11、s sensor network (WSN) planning in orchards, Biosystems Engineering, Special Issue: Sensing Technologies for Sustainable Agriculture, April 2013, 114(4):454465 3 Enrique Stevens-Navarro, Vijayanth Vivekanandan, Vincent W.S. Wong, Dual and Mixture Monte Carlo Localization Algorithms for Mobile Wirele

12、ss Sensor Networks, Wireless Communications and Networking Conference, 2007.WCNC 2007. IEEE4 Durisic M.P, Tafa Z, Dimic G, Milutinovic V, A survey of military applications of wireless sensor networks, Embedded Computing (MECO), 2012 Mediterranean Conference on Date 19-21 June 2012.5 R. Szewczyk, A.

13、Mainwaring, J. Polastre, J. Anderson, and D. Culler, “An analysis of a large scale habitat monitoring application,” in Proc. 2nd Int. Conf. Embedded Netw. SenSys, New York, 2004, pp. 214226.6 Gwo-Jong Yu. Adaptive Storage Policy Switching for Wireless Sensor Networks.Wireless Pers Commun Magzine, 20

14、09, 48:3273467 C.Inianagonwiwat,R.Govindan,and D.Estrin, Directed Diffusion:A scalable and robust communication Paradigm for sensor networks.In Proeeedings of the ACM SIGMOBILE Intemational Confereneeon Mobile ComPuting and Networking(MobiCom)C,2000,56一67.8 Gerhke J. COUGAR design and implementation

15、. /.9 J.Newsome and D.Song, GEM:Graph Embedding for routing and data-eentrie storage in sensor networks withthout geographic Information.In Proceedings of International Confereneeon Embedded Networked Sensor Systems(Sensys)C,2003,76-88.10 Shenker S, Ratnasamy S, Karp B, et

16、alData-centric storage in sensornetsACM SIGCOMM Computer Communication Review,2003,33(1): 137142二、進(jìn)度及預(yù)期結(jié)果：起止日期主要內(nèi)容預(yù)期結(jié)果開題報(bào)告、任務(wù)書的填寫、提交、審核深入研究與課題相關(guān)國內(nèi)外文獻(xiàn)資料，熟悉Matlab仿真工具完成理論部分總結(jié)并進(jìn)行公式推導(dǎo)。完成Matlab主要公式調(diào)用演示模型模塊完成核心模塊并進(jìn)行系統(tǒng)調(diào)試，在調(diào)試中進(jìn)一步完善系統(tǒng)的各項(xiàng)功能，同時(shí)開始撰寫畢業(yè)論文對系統(tǒng)進(jìn)行修改及調(diào)整，根據(jù)老師意見修改論文，并進(jìn)行畢業(yè)設(shè)計(jì)答辯的準(zhǔn)備答辯完成完成完成完成完成完成完成課題的現(xiàn)有條件 通

17、過本科四年的學(xué)習(xí)，具備了計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)的知識(shí)，掌握了高等數(shù)學(xué)、線性代數(shù)、概率與統(tǒng)計(jì)學(xué)等數(shù)學(xué)工具，學(xué)會(huì)使用Matlab，有一定的編程基礎(chǔ)及查閱國內(nèi)外相關(guān)領(lǐng)域文獻(xiàn)的自學(xué)能力。審查意見指導(dǎo)教師： 年 月 日學(xué)院意見主管領(lǐng)導(dǎo)： 年 月 日摘 要本文的主要研究內(nèi)容是根據(jù)無線傳感器網(wǎng)絡(luò)中分布式存儲(chǔ)數(shù)據(jù)與檢索數(shù)據(jù)策略，包括GHT模式、簡單雙直紋模式和球面雙直紋模式進(jìn)行模擬實(shí)驗(yàn)與應(yīng)用分析。與采用基于地理位置哈希表（GHTs）模式的路由策略相比，球面雙直紋模式在不同傳感器節(jié)點(diǎn)之間是支持地理位置感知的。并且由于在原始的雙直紋策略（Double Rulings）中數(shù)據(jù)的復(fù)制路線與檢索路線只有一條，而球面雙直紋模式對

18、相同數(shù)據(jù)類型數(shù)據(jù)的復(fù)制不止一條，因此在數(shù)據(jù)聚集檢索模式中可以大大提高檢索的效率。在本文中我們主要介紹球面雙直紋模式的基本思想，相同數(shù)據(jù)類型的數(shù)據(jù)多重復(fù)制作為改進(jìn)基本雙直紋策略模式中的缺點(diǎn)和不足之一。在無線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用環(huán)境中，不同數(shù)據(jù)類型的數(shù)據(jù)聚集所帶來的優(yōu)點(diǎn)不容忽視。球面雙直紋模式引入哈希節(jié)點(diǎn)的概念因此數(shù)據(jù)聚集也成為了該模式的優(yōu)點(diǎn)之一。在論文的仿真部分通過實(shí)驗(yàn)數(shù)據(jù)證明了球面雙直紋提出的方法擁有更少的節(jié)點(diǎn)通訊消耗與更好的負(fù)載平衡。關(guān)鍵詞：傳感器網(wǎng)絡(luò)；信息的存儲(chǔ)與檢索；雙直紋策略；以數(shù)據(jù)為中心的路由策略；ABSTRACTThe main research of this dissertat

19、ion is that we simulate the GHTs, the Double Ruling Scheme and the Spherical Double Ruling scheme to store and retrieve data in a wireless sensor network. The details are as follows. First of all, the method based on the spherical double ruling scheme can be distance-sensitive compared to geographic

20、al hash table (GHT). Second, the spherical double ruling scheme enhances the probability of successful retrieval because there is only one way of a producer to retrieve the desirable data in the double ruling scheme. In this dissertation, we explain the basic idea of the spherical double ruling sche

21、me that the replica curves of the specific data in the sensor field are multiple instead of only one curve in the double rulings scheme. And the spherical double ruling scheme also has the capacity to aggregate the data in a specific sensor node due to the existence of hash node, which combine the G

22、HTs primary idea. The aggregation of data can provide various advantages in practical circumstance. Furthermore, by the flexibility of the retrieval mechanism, the robustness of sensor networks is much better than the sensor networks that use the original double rulings and the geographical hash tab

23、le. We prove the aforementioned advantages by the simulation that the double rulings scheme modified has ability to provide reduced communication costs and balanced traffic load on sensor nodes.Key words：Sensor networks；Information storage and retrieval；Double rulings；Data-centric routing；目 錄第一章 前 言

24、11.1背景11.2相關(guān)研究11.3本文結(jié)構(gòu)3第二章 分布式存儲(chǔ)與檢索策略52.1GHT模式52.2簡單雙直紋模式62.3球面雙直紋模式72.4三種模式對比92.5本章小結(jié)10第三章 相關(guān)算法設(shè)計(jì)113.1數(shù)據(jù)復(fù)制113.2數(shù)據(jù)復(fù)制的路由算法143.3數(shù)據(jù)檢索173.4傳感器節(jié)點(diǎn)的參數(shù)設(shè)計(jì)203.5對非理想環(huán)境的傳感器網(wǎng)絡(luò)處理203.6本章小結(jié)21第四章 仿真實(shí)驗(yàn)與結(jié)果分析224.1模擬環(huán)境224.2地理位置感知查詢224.3時(shí)間表現(xiàn)244.4負(fù)載均衡274.5本章小結(jié)29第五章 總 結(jié)30參考文獻(xiàn)31附 錄34謝 辭44第一章 前 言1.1 背景無線傳感器網(wǎng)絡(luò)（Wireless Sensor

25、 Networks, WSN）是由按照一定拓?fù)浣Y(jié)構(gòu)的一定數(shù)量的靜止或移動(dòng)的廉價(jià)微型傳感器節(jié)點(diǎn)，以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)。它是當(dāng)前在國際上備受關(guān)注的、涉及多學(xué)科高度交叉、知識(shí)高度集成的前沿?zé)狳c(diǎn)研究領(lǐng)域。特別是隨著物聯(lián)網(wǎng)產(chǎn)業(yè)的快速興起，無線傳感器網(wǎng)絡(luò)作為物聯(lián)網(wǎng)中的核心產(chǎn)業(yè)，也隨之得到了更多的關(guān)注與研究。它擴(kuò)展了人們的信息獲取能力，將客觀世界的物理信息同傳輸網(wǎng)絡(luò)連接在一起，在下一代網(wǎng)絡(luò)中將為人們提供最直接、最有效、最真實(shí)的信息，廣泛應(yīng)用于環(huán)境監(jiān)測1、農(nóng)業(yè)生產(chǎn)2、定位跟蹤3、軍事4等領(lǐng)域中。對于計(jì)算機(jī)網(wǎng)絡(luò)來說，保證數(shù)據(jù)的實(shí)時(shí)性一直作為人們建設(shè)計(jì)算機(jī)網(wǎng)絡(luò)不可少的條件之一，無線傳感器網(wǎng)絡(luò)也不例外

26、。早期的傳感器網(wǎng)絡(luò)數(shù)據(jù)的收集與傳輸主要采用多對一模型，即數(shù)個(gè)傳感器節(jié)點(diǎn)產(chǎn)生的原始數(shù)據(jù)均由一個(gè)數(shù)據(jù)收集器去收集5。隨著傳感器網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大以及對數(shù)據(jù)實(shí)時(shí)性的要求越來越高，這種方法逐漸變得不切合實(shí)際。因此研究更為高效的無線傳感器網(wǎng)絡(luò)路由算法就顯得越發(fā)重要。對于一些給定限制條件的分布式數(shù)據(jù)存儲(chǔ)和查詢問題，目前存在一些給定的解決算法，但在這些已存在的算法中，很少研究在無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)存儲(chǔ)和查詢的平衡優(yōu)化問題。在實(shí)際網(wǎng)絡(luò)應(yīng)用中，一些功能所需要的特性必須存在于無線傳感器網(wǎng)絡(luò)的路由算法中，例如數(shù)據(jù)聚集。如何能夠在無線傳感器網(wǎng)絡(luò)中優(yōu)化數(shù)據(jù)的存儲(chǔ)和查詢，使得在的減少整個(gè)網(wǎng)絡(luò)的能量消耗的前提下均衡網(wǎng)絡(luò)的

27、能量負(fù)載，是解決無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)存儲(chǔ)和查詢問題的主要任務(wù)。首先就數(shù)據(jù)存儲(chǔ)方面，隨著物聯(lián)網(wǎng)大數(shù)據(jù)的提出，無線傳感器網(wǎng)絡(luò)中傳感器收集的信息量將會(huì)越來越大。但是采用分布式存儲(chǔ)方式是將數(shù)據(jù)存儲(chǔ)到本地傳感器節(jié)點(diǎn)中，一般傳感器的存儲(chǔ)空間是有限的，如何把日益增多的數(shù)據(jù)存儲(chǔ)到存儲(chǔ)空間極度有限的傳感器中成為亟待解決的問題之一。另外就數(shù)據(jù)查詢方面，在傳感器網(wǎng)絡(luò)中如何設(shè)計(jì)路由策略，在減少整個(gè)網(wǎng)絡(luò)的能量消耗（這里主要指通信能耗）的前提下很好地均衡網(wǎng)絡(luò)的能量負(fù)載以及保證較高數(shù)據(jù)查詢成功率成為無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)查詢階段必須要考慮的問題。1.2 相關(guān)研究國內(nèi)外的相關(guān)研究者針對特定的應(yīng)用需求，將無線傳感器網(wǎng)絡(luò)的存儲(chǔ)模式

28、分為以下三種策略6：外部存儲(chǔ)（External Storage, ES）、本地存儲(chǔ)（Local Storage, LS）和分布式存儲(chǔ)（Data-Centric Storage, DCS）。外部存儲(chǔ)是指每個(gè)傳感器節(jié)點(diǎn)將感知到的數(shù)據(jù)立即發(fā)送到 Sink 節(jié)點(diǎn)上進(jìn)行存儲(chǔ)，所有的查詢請求在 Sink 節(jié)點(diǎn)上執(zhí)行查詢。文獻(xiàn)7提出了著名的基于外部存儲(chǔ)策略的定向擴(kuò)散（Directed Diffusion）存儲(chǔ)方式。它是基于訂閱發(fā)布模式的以需求為中心的路由方式。在定向擴(kuò)散中，每個(gè)采集數(shù)據(jù)的Sink節(jié)點(diǎn)都向網(wǎng)絡(luò)中使用洪泛法發(fā)送出自己的請求，且在每一個(gè)請求中，都可以包含任意多的屬性來支持復(fù)雜數(shù)據(jù)的表達(dá)和查詢。因此

29、定向擴(kuò)散可以勝任任何類型的查詢。本地存儲(chǔ)是指傳感器將監(jiān)測到的數(shù)據(jù)直接保存在自身中，因此存儲(chǔ)數(shù)據(jù)不會(huì)花費(fèi)任何的通信代價(jià)。Cornell大學(xué)的COUGAR系統(tǒng)8即屬于基于本地的存儲(chǔ)策略。它是將整個(gè)傳感器網(wǎng)絡(luò)看成是一個(gè)大型分布式傳感器數(shù)據(jù)庫系統(tǒng)，每個(gè)傳感器對應(yīng)于該分布式數(shù)據(jù)庫的一個(gè)節(jié)點(diǎn)，其中傳感器感知獲得的數(shù)據(jù)用時(shí)間序列來表示，存儲(chǔ)數(shù)據(jù)用關(guān)系表示，在特定時(shí)間的查詢用相應(yīng)時(shí)間的視圖表示。它盡可能的將計(jì)算有用信息的工作留在傳感網(wǎng)絡(luò)中進(jìn)行。以數(shù)據(jù)為中心的存儲(chǔ)（Data-Centric Storage, DCS）也稱為分布式存儲(chǔ)，它是使用事件來表示節(jié)點(diǎn)感知的數(shù)據(jù)的屬性，所有的事件都被命名，相同屬性的數(shù)據(jù)被映

30、射到相同的地理位置，距離此地理位置最近的節(jié)點(diǎn)用來存儲(chǔ)數(shù)據(jù)。特定事件查詢被路由至合適的存儲(chǔ)節(jié)點(diǎn)。GEM(Graph Embedding，GEM)9 是一種基于嵌入地圖輔助路由的以數(shù)據(jù)為中心的分布式存儲(chǔ)方式。它的主要原理是在每一個(gè)傳感器中嵌入一幅地圖。為了能夠支持以數(shù)據(jù)為中心的分布存儲(chǔ),將每一個(gè)感應(yīng)到的數(shù)據(jù)對象都映射到一個(gè)標(biāo)識(shí)，并借此將不同的數(shù)據(jù)對象存儲(chǔ)到不同的節(jié)點(diǎn)中。文獻(xiàn)10提出了經(jīng)典的采用地理散列函數(shù)(Geographic Hash Table, GHT) 進(jìn)行數(shù)據(jù)存儲(chǔ)。GHT采用了基于數(shù)據(jù)命名的思想，將每種類型的事件映射到傳感器網(wǎng)絡(luò)中的一個(gè)地理位置，距離該地理位置最近的節(jié)點(diǎn)成為此事件的存儲(chǔ)節(jié)

31、點(diǎn)，因此查詢只需要發(fā)送到該查詢所包含事件的節(jié)點(diǎn)上而不需要泛洪查詢，這樣便可大大地節(jié)約查詢時(shí)所消耗的能量。文獻(xiàn)11提出了分布式的基于時(shí)空相似性的數(shù)據(jù)存儲(chǔ)策略。它是以事件為驅(qū)動(dòng)，在數(shù)據(jù)存儲(chǔ)是按照事件的發(fā)生時(shí)間（縱向）和地理位置（橫向）建立的平面映射將發(fā)生在相應(yīng)時(shí)間、相應(yīng)地點(diǎn)的時(shí)間映射到相應(yīng)位置，并將其存儲(chǔ)到離此位置最近的傳感器節(jié)點(diǎn)上進(jìn)行存儲(chǔ)。在數(shù)據(jù)查詢時(shí)，算法采用設(shè)定的相似度值的大小來衡量查詢到的數(shù)據(jù)與原數(shù)據(jù)的相似性。文獻(xiàn)12與文獻(xiàn)13關(guān)注了GHT模式中的能量消耗優(yōu)化問題。Sarkar, Rik, X. Zhu, J. Gao等人在14文獻(xiàn)中提出了一種新的方法稱作基于地標(biāo)的梯度分布式路由（Grad

32、ient Landmark-Based Distributed Routing , GLIDER）。這種方法將雙直紋模式與GHT模式相結(jié)合，將傳感器網(wǎng)絡(luò)平面劃分為塊的拓?fù)浣Y(jié)構(gòu)。如圖1.1所示，塊與塊之間為上層結(jié)構(gòu)，塊內(nèi)為下層。GHT模式在上層使用并且數(shù)據(jù)哈希化之后得到的是塊的位置而不是單個(gè)節(jié)點(diǎn)的位置。在每一個(gè)塊內(nèi)，雙直紋模式被使用規(guī)劃具體的傳輸路徑，為的是保證復(fù)制曲線與檢索曲線能夠相交。當(dāng)某節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)時(shí)，通過調(diào)用自身的哈希函數(shù)確定數(shù)據(jù)集結(jié)節(jié)點(diǎn)所在的塊的位置，使用雙直紋模式在塊內(nèi)進(jìn)行數(shù)據(jù)的傳輸，之后根據(jù)數(shù)據(jù)集結(jié)節(jié)點(diǎn)所在的塊進(jìn)行塊間傳輸。檢索時(shí)的策略類似，如果請求提前與復(fù)制曲線相交則立即查詢數(shù)據(jù)

33、并返回而不必要傳輸?shù)綌?shù)據(jù)集結(jié)塊內(nèi)的集結(jié)節(jié)點(diǎn)。圖1.1 一個(gè)GLIDER示例141.3 本文結(jié)構(gòu)無線傳感器網(wǎng)絡(luò)分布式存儲(chǔ)與檢索策略有GHT模式、簡單雙直紋模式、球面雙直紋模式15等。球面雙直紋模式是一種無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)和檢索方式，實(shí)現(xiàn)思路是使用球面投影與簡單雙直紋模式相結(jié)合的特殊地理位置哈希表模式（GHT）。本文根據(jù)不同的應(yīng)用場景敘述了多種的復(fù)制和檢索方案，并且詳細(xì)闡述了在應(yīng)用分布式存儲(chǔ)與檢索策略時(shí)一些具體的實(shí)施細(xì)節(jié)，例如數(shù)據(jù)在節(jié)點(diǎn)的存儲(chǔ)方式、復(fù)制和檢索時(shí)路徑的路由和低密度傳感器網(wǎng)絡(luò)的應(yīng)對方法等。同時(shí)模擬了在擁有2048個(gè)傳感器節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)中復(fù)制和檢索的消耗情況。本文的組織方式如下。在第

34、二章中，我們詳細(xì)介紹了GHT模式、簡單雙直紋模式、球面雙直紋模式具體設(shè)計(jì)原理與方法以及球面雙直紋模式的數(shù)學(xué)模型。在第三章中我們詳細(xì)地介紹了GHT模式、簡單雙直紋模式、球面雙直紋模式時(shí)一些具體的實(shí)施細(xì)節(jié)，包括三種模式的數(shù)據(jù)復(fù)制機(jī)制以及應(yīng)用與不同環(huán)境下的復(fù)制策略以及檢索策略、數(shù)據(jù)在節(jié)點(diǎn)的存儲(chǔ)方式、復(fù)制和檢索時(shí)路徑的路由、對傳感器網(wǎng)絡(luò)邊界的處理和低密度傳感器網(wǎng)絡(luò)的應(yīng)對方法細(xì)節(jié)等。在第四章中我們對這三種模式進(jìn)行仿真實(shí)驗(yàn)。模擬環(huán)境采用Matlab。與球面雙直紋模式對比的是GHT模式與簡單雙直紋模式。通過對比不同模式在地位位置感知查詢和時(shí)間表現(xiàn)下的數(shù)據(jù)復(fù)制與數(shù)據(jù)檢索的性能表現(xiàn)來突出球面雙直紋模式相對與簡單

35、雙直紋模式和GHT模式的優(yōu)勢。第五章包括本文總結(jié)和對無線傳感器網(wǎng)絡(luò)存儲(chǔ)和檢索策略的未來展望。第二章 分布式存儲(chǔ)與檢索策略22.1 GHT模式在GHT模式中，數(shù)據(jù)根據(jù)自身的類型哈希化為無線傳感器網(wǎng)絡(luò)中某個(gè)位置的坐標(biāo)，最靠近這個(gè)位置的節(jié)點(diǎn)選為哈希節(jié)點(diǎn)（Hash nodes）。產(chǎn)生這一數(shù)據(jù)類型的數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)所產(chǎn)生的數(shù)據(jù)都將向該數(shù)據(jù)類型的哈希節(jié)點(diǎn)聚集。聚集的過程是指某個(gè)節(jié)點(diǎn)擁有的該類型數(shù)據(jù)向其鄰近節(jié)點(diǎn)中最靠近哈希節(jié)點(diǎn)的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，之后在自身的鄰居節(jié)點(diǎn)中重復(fù)這一過程，最終哈希節(jié)點(diǎn)存儲(chǔ)該數(shù)據(jù)類型的所有數(shù)據(jù)，如圖2.1。圖2.1 一個(gè)GHT模式的實(shí)例10GHT模式的缺點(diǎn)也隨著相關(guān)研究的不斷深入而逐漸暴露出

36、來。GHT是一個(gè)基本的數(shù)據(jù)存儲(chǔ)方案，可以從以下幾個(gè)方向提高其消耗表現(xiàn)。在GHT模式下，某些數(shù)據(jù)節(jié)點(diǎn)可能會(huì)儲(chǔ)存熱門數(shù)據(jù)，這樣檢索會(huì)受到數(shù)據(jù)集結(jié)節(jié)點(diǎn)傳輸瓶頸限制，并且數(shù)據(jù)集結(jié)節(jié)點(diǎn)的負(fù)載很有可能高于其他節(jié)點(diǎn)，最終造成附近節(jié)點(diǎn)過早死亡，而這樣必定會(huì)影響整個(gè)網(wǎng)絡(luò)壽命。并且數(shù)據(jù)集結(jié)節(jié)點(diǎn)與其附近的存有數(shù)據(jù)的節(jié)點(diǎn)對該區(qū)域的影響不可忽視，若數(shù)據(jù)集結(jié)節(jié)點(diǎn)死亡會(huì)極大地造成該類型數(shù)據(jù)檢索失敗的概率。為了解決這樣的問題就需要設(shè)定不同的鏡像節(jié)點(diǎn)存儲(chǔ)集結(jié)節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)，這樣做雖然可以提高整個(gè)網(wǎng)絡(luò)的健壯程度，但通訊造成的額外消耗也是不容小視的。另外數(shù)據(jù)的檢索是不支持地理位置感知的，即有可能數(shù)據(jù)的產(chǎn)生節(jié)點(diǎn)與需要這種數(shù)據(jù)的檢索

37、節(jié)點(diǎn)地理位置相聚很近而在檢索時(shí)檢索節(jié)點(diǎn)卻向該種數(shù)據(jù)的集結(jié)節(jié)點(diǎn)檢索數(shù)據(jù)，造成多余的傳輸消耗。為了獲得數(shù)據(jù)存儲(chǔ)平衡數(shù)據(jù)集結(jié)節(jié)點(diǎn)應(yīng)該均勻分散在網(wǎng)絡(luò)中，但是設(shè)計(jì)可以產(chǎn)生均勻位置的哈希函數(shù)比較困難。2.2 簡單雙直紋模式另一種分布式存儲(chǔ)與檢索策略是雙直紋模式（Double Rulings scheme），在目前的研究中有較多的方法是基于該模式的，例如文獻(xiàn)14和15。而雙直紋模式的基本原理如下。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)均勻分布在平面上，將每一個(gè)傳感器節(jié)點(diǎn)的橫、縱方向的鄰居傳感器節(jié)點(diǎn)相連接構(gòu)成Mesh網(wǎng)格，如圖2.2所示。圖2.2 簡單雙直紋模式14在圖2.2中，復(fù)制路徑（圖中帶箭頭橫線）在網(wǎng)格中是數(shù)

38、據(jù)產(chǎn)生節(jié)點(diǎn)所在網(wǎng)格中的橫向曲線，曲線中所有節(jié)點(diǎn)內(nèi)均存儲(chǔ)該行內(nèi)數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)的數(shù)據(jù)；檢索曲線（圖中帶箭頭豎線）在網(wǎng)格中是數(shù)據(jù)檢索節(jié)點(diǎn)所在網(wǎng)格中的縱向曲線。網(wǎng)絡(luò)中的某一檢索節(jié)點(diǎn)要檢索某一消息時(shí)，將檢索請求消息發(fā)送至它所在橫向位置的檢索曲線上的每一個(gè)節(jié)點(diǎn)上直至網(wǎng)絡(luò)部署區(qū)域邊界節(jié)點(diǎn)完成數(shù)據(jù)檢索。在整個(gè)檢索過程中，數(shù)據(jù)請求消息將經(jīng)過整個(gè)網(wǎng)絡(luò)的每條數(shù)據(jù)復(fù)制曲線上的存儲(chǔ)節(jié)點(diǎn)，因此它的數(shù)據(jù)查詢成功率為100%。盡管這雙直紋模式的優(yōu)點(diǎn)很突出，但與之而來的缺點(diǎn)也是非常明顯的。大多數(shù)無線傳感器網(wǎng)絡(luò)的形狀并沒有那么標(biāo)準(zhǔn)，甚至有的網(wǎng)絡(luò)中由于障礙物或其他原因網(wǎng)絡(luò)平面中會(huì)有洞的出現(xiàn)14。這樣就很大程度限制了雙直紋模式在實(shí)際情

39、況中的應(yīng)用。而且雙直紋模式要求每一橫向曲線的每一個(gè)節(jié)點(diǎn)都存儲(chǔ)本橫向曲線的數(shù)據(jù)生產(chǎn)者所采集的數(shù)據(jù)，這對于大規(guī)模無線傳感器網(wǎng)絡(luò)來說大大增加了數(shù)據(jù)的存儲(chǔ)量。2.3 球面雙直紋模式文獻(xiàn)15所提出的球面雙直紋模式主要是受到GHT模式與雙直紋模式的啟發(fā)。在本文中我們依然使用球面雙直紋模式但更注重?cái)?shù)據(jù)復(fù)制傳輸時(shí)的靈活性。如圖2.3所示，數(shù)據(jù)復(fù)制時(shí)與檢索時(shí)采用的圓環(huán)。圖2.3 一個(gè)球面雙直紋模式示例15在球面雙直紋模式中主要思想就是將無線傳感器平面通過投影幾何映射成為一個(gè)球面，數(shù)據(jù)復(fù)制與檢索的路徑都將在球面上定義。利用球的特性來保證復(fù)制路線與檢索路線相交即保證檢索的成功率。在復(fù)制與檢索數(shù)據(jù)時(shí)我們依然使用GHT

40、模式中的思想，即數(shù)據(jù)根據(jù)其自身的類型向網(wǎng)絡(luò)中該數(shù)據(jù)集結(jié)節(jié)點(diǎn)復(fù)制。但與GHT思想不同的是，數(shù)據(jù)產(chǎn)生者產(chǎn)生的數(shù)據(jù)的復(fù)制路徑是經(jīng)過其自身與數(shù)據(jù)集結(jié)節(jié)點(diǎn)的圓環(huán)，不是GHT中使用貪心算法得到的距離數(shù)據(jù)集結(jié)節(jié)點(diǎn)最近的路徑。節(jié)點(diǎn)在檢索數(shù)據(jù)時(shí)也是沿著某一個(gè)圓環(huán)形成的圓弧。使用這樣的方式檢索請求不必要傳輸?shù)郊Y(jié)節(jié)點(diǎn)只需要與該數(shù)據(jù)的復(fù)制曲線相交。對某類數(shù)據(jù)進(jìn)行復(fù)制時(shí)，復(fù)制路徑也不局限與一種，提升了復(fù)制時(shí)的靈活性。由于復(fù)制時(shí)靈活性較高，我們提供了幾種檢索策略可以根據(jù)不同的需求來使用，例如當(dāng)前網(wǎng)絡(luò)負(fù)載情況或當(dāng)前網(wǎng)絡(luò)能源情況。球面雙直紋模式數(shù)學(xué)模型的詳細(xì)介紹如下，文中的公式、定義、推論引用于文獻(xiàn)15。作為球面雙直紋模式

41、的核心思想，將傳感器平面通過投影幾何中的球面投影映射成為球面。如圖所示2.4，一個(gè)矩形平面通過球面投影映射成為一個(gè)球面，這個(gè)球面的頂端帶有空洞。球面與平面的切點(diǎn)稱為南極，球面的頂端成為北極。過北極和平面上的某一點(diǎn)就可以得到該點(diǎn)在球面上的投影點(diǎn)，并且這種對應(yīng)關(guān)系是唯一的。平面上邊界的邊界在球面北極形成北極空洞的邊界?？斩吹男螤詈推矫娴男再|(zhì)對應(yīng)，空洞的大小與平面的扭曲程度和球體的半徑有關(guān)16。假設(shè)此時(shí)平面S投影得到球體H。區(qū)域S的面積是有限的且平面上的每一個(gè)節(jié)點(diǎn)的位置是已知的，因此S上的任何點(diǎn)在球面上的點(diǎn)H(x,y,z)都可以計(jì)算得到，其中zk ，0<k<2r 。公式2.1定義了球體，

42、p是球體的球心，r是它的半徑。x-px-p=r2(2.1)平面上的點(diǎn)定義為q，球面上北極定義為n，那么過q與n的直線定義為lt=q+t，其中t是參數(shù)并且v=n-q。那么這條直線可以定義公式2.2t2vv+t2vq-p+q-pq-p-r2=0(2.2)因此只要給出球面與平面上點(diǎn)的位置，就可以計(jì)算出這個(gè)點(diǎn)映射在球面上的位置17。若給出球面上的位置和球體，公式2.3便求得球面上的這點(diǎn)在平面上的位置。h*=h=h+o-hzwzw(2.3)其中h 球面上的一點(diǎn)，經(jīng)過h與北極的直線定義為l't=h+tw，其中w=h-n。我們定義平面為x-oz=0，其中o為平面的原點(diǎn)，即南極，z是平面上的一個(gè)單位向

43、量。因?yàn)閭鞲衅髌矫媸且阎模覀兛梢詫⑶蝮w放在平面的正中央。假設(shè)最遠(yuǎn)的傳感器距離原點(diǎn)距離為D，參數(shù)k，即球面上最高點(diǎn)的坐標(biāo)的z值，最大為2rD24r2+D2。我們可以根據(jù)平面投影時(shí)平面扭曲的程度來選取r的值，即r 為D2,>0 ，k=2r1+。根據(jù)投影幾何的內(nèi)容可知，球面上的圓環(huán)在平面上依然是圓環(huán)，接下來的理論證明了球面上圓環(huán)的長度與該圓環(huán)投影在平面上的長度相差不大。定義2.115：考慮到任何在球面上的點(diǎn)p1和p2投影至平面上的點(diǎn)p1和p2。如果p1和p2在球面上圓環(huán)的長度為d，那么p1和p2在平面上圓環(huán)的長度為l，那么我們將會(huì)有公式2.4。ld2r2r-k=1+(2.4)當(dāng)=1，平面上

44、的所有節(jié)點(diǎn)均映射到球面的下半球面。我們通常設(shè)大于1。我們使用,代表球面上任意兩點(diǎn)的最短測地距并且使用|代表在平面上的歐幾里德距離，因此我們有推論2.1。推論2.115：|p*q*|1+p,q。證明：球面上圓弧p,q的最短距離，對應(yīng)投影在平面上p*, q*的兩點(diǎn)的距離受到約束為1+p,q。并且，這兩點(diǎn)的歐幾里德距離總是小于這兩點(diǎn)在圓弧的距離。因此，|p*q*|1+p,q。圖2.4 球面投影示例172.4 三種模式對比本小節(jié)內(nèi)容主要介紹GHT模式、簡單雙直紋模式與球面雙直紋模式之間的對比。本文側(cè)重點(diǎn)之一是無線傳感器網(wǎng)絡(luò)的檢索策略。評判檢索策略的條件有檢索消耗、延時(shí)和檢索的成功率等。而傳感器網(wǎng)絡(luò)的復(fù)

45、制策略直接影響了檢索的那些條件。因此選取一個(gè)優(yōu)秀的復(fù)制和檢索效率是十分重要的。在簡單雙直紋模式中，完整的無線傳感器網(wǎng)絡(luò)的檢索成功的幾率是100%，這是因?yàn)闄z索時(shí)可以探測到該網(wǎng)絡(luò)的所有數(shù)據(jù)。在GHT模式中由于存有數(shù)據(jù)的點(diǎn)只有一個(gè)所以檢索的成功率受到很多因素制約。對于球面雙直紋模式來說，擴(kuò)大了實(shí)際存有數(shù)據(jù)的節(jié)點(diǎn)數(shù)量，并且檢索只要與復(fù)制曲線相交便可保證成功的檢索，因此在檢索上球面雙直紋模式繼承了簡單雙直紋的優(yōu)點(diǎn)。球面雙直紋模式的優(yōu)點(diǎn)總結(jié)如下。球面雙直紋模式可以看作是GHT模式和雙直紋模式的特殊擴(kuò)展，故擁有這兩種方法所具有的優(yōu)點(diǎn)。第一，支持地理位置感知與結(jié)構(gòu)化的檢索只需要增加一部分?jǐn)?shù)據(jù)復(fù)制開銷。第二，

46、在部分節(jié)點(diǎn)死亡時(shí)整個(gè)網(wǎng)絡(luò)依然擁有較好的健壯程度。第三，由于復(fù)制時(shí)的靈活性，數(shù)據(jù)集結(jié)節(jié)點(diǎn)不在是整個(gè)網(wǎng)絡(luò)的傳輸瓶頸。第四，相比起鏡像復(fù)制的GHT模式或論文11中的方法，該方法可以降低復(fù)制時(shí)的傳輸消耗。原因是復(fù)制曲線是一條易于相交的封閉圓環(huán)。數(shù)據(jù)聚集的特性對需要進(jìn)行數(shù)據(jù)分類收集、數(shù)據(jù)計(jì)算的無線傳感器網(wǎng)絡(luò)應(yīng)用十分重要。例如在氣候應(yīng)用18中收集該地區(qū)的溫度、濕度信息需要無線傳感器網(wǎng)絡(luò)對數(shù)據(jù)進(jìn)行分類。在GHT模式中使用對數(shù)據(jù)哈?；玫讲煌瑪?shù)據(jù)的地理位置信息從而實(shí)現(xiàn)數(shù)據(jù)聚集。在球面雙直紋模式中，哈希節(jié)點(diǎn)作為不同數(shù)據(jù)類型的集結(jié)節(jié)點(diǎn)與GHT模式中的哈希節(jié)點(diǎn)行使相同的職責(zé)。因此球面雙直紋模式同樣支持?jǐn)?shù)據(jù)聚集。在簡

47、單雙直紋模式中，因?yàn)椴淮嬖跀?shù)據(jù)分類的概念因此若需要某一類型的數(shù)據(jù)需要檢索整個(gè)網(wǎng)絡(luò)，對于之前提及的無線傳感器網(wǎng)絡(luò)在氣候方面的應(yīng)用是十分不利的?？偨Y(jié)來說，球面雙直紋模式在數(shù)據(jù)聚集方面既克服了簡單雙直紋模式的缺點(diǎn)又吸收了GHT模式的優(yōu)點(diǎn)。2.5 本章小結(jié)在本章中主要介紹了GHT模式、簡單雙直紋模式和球面雙直紋模式的數(shù)學(xué)模型，從檢索成功率與數(shù)據(jù)聚集的方面詳細(xì)對比了簡單雙直紋模式與GHT模式、球面雙直紋模式的優(yōu)缺點(diǎn)。通過對以上內(nèi)容的介紹為下文中算法設(shè)計(jì)和仿真實(shí)驗(yàn)奠定下了基礎(chǔ)。第三章 相關(guān)算法設(shè)計(jì)33.1 數(shù)據(jù)復(fù)制在GHT模式中，數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)總是要傳輸?shù)綌?shù)據(jù)集結(jié)節(jié)點(diǎn)（哈希節(jié)點(diǎn)），這樣對于某一種數(shù)

48、據(jù)來說實(shí)際存有該數(shù)據(jù)的位置只在某一個(gè)節(jié)點(diǎn)之中。這樣的設(shè)計(jì)模式對于存儲(chǔ)與檢索來說都是不利的。對于檢索來說，無線傳感器網(wǎng)絡(luò)中存有該數(shù)據(jù)的備份越多意味著檢索成功的幾率越大。因?yàn)樵跓o線傳感器網(wǎng)絡(luò)中，成功的檢索不只意味著檢索路徑最終到達(dá)存有數(shù)據(jù)的節(jié)點(diǎn)。若存有數(shù)據(jù)的節(jié)點(diǎn)死亡或者存有數(shù)據(jù)的節(jié)點(diǎn)周圍的生存節(jié)點(diǎn)的密度較少均會(huì)導(dǎo)致檢索的失敗。這樣的情況存在于密度稀疏的網(wǎng)絡(luò)或者經(jīng)過一段時(shí)間后網(wǎng)絡(luò)中一部分節(jié)點(diǎn)死亡的情況。對于復(fù)制來說，雖然對某一數(shù)據(jù)只復(fù)制一份所需要的開銷很小，但對該節(jié)點(diǎn)的生存和檢索數(shù)據(jù)都是十分不利的。在第四章仿真實(shí)驗(yàn)和結(jié)果分析中，我們模擬了GHT模式的負(fù)載情況。數(shù)據(jù)的不斷產(chǎn)生對數(shù)據(jù)集結(jié)節(jié)點(diǎn)的生存是十分

49、不利的。因此綜合考慮傳感器網(wǎng)絡(luò)的壽命，適當(dāng)?shù)膶?shù)據(jù)進(jìn)行復(fù)制是十分必要的。雙直紋模式在數(shù)據(jù)復(fù)制中解決了GHT模式中的不足，即對于某一數(shù)據(jù)來說復(fù)制多份來平衡負(fù)載與提升檢索成功率。因此在數(shù)據(jù)復(fù)制的機(jī)制我們采用雙直紋模式。在簡單雙直紋模式中，無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)總是沿傳感器網(wǎng)絡(luò)中緯線進(jìn)行復(fù)制。也就是說在傳感器網(wǎng)絡(luò)中的某一條緯線上存有該緯線上數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)所有的數(shù)據(jù)。這樣做的好處之前已經(jīng)提到，但在實(shí)際情況中這樣做會(huì)導(dǎo)致傳感器網(wǎng)絡(luò)中的復(fù)制開銷特別大。為解決這個(gè)問題復(fù)制時(shí)可選擇性進(jìn)行復(fù)制，即復(fù)制時(shí)只復(fù)制指向?qū)嶋H存有該數(shù)據(jù)的位置信息，即根據(jù)實(shí)際情況定義某一數(shù)據(jù)的實(shí)際復(fù)制數(shù)目。簡單雙直紋模式克

50、服了GHT模式中數(shù)據(jù)復(fù)制機(jī)制的不足。提供了一種數(shù)據(jù)復(fù)制的新機(jī)制。雙直紋模式在數(shù)據(jù)復(fù)制機(jī)制中雖然有很好的特性，但由于其對無線傳感器網(wǎng)絡(luò)的形狀要求十分苛刻導(dǎo)致其應(yīng)用并不廣泛。因此球面雙直紋模式的提出就是為了解決簡單雙直紋模式中對網(wǎng)絡(luò)形狀要求苛刻的缺點(diǎn)。在球面雙直紋模式中，無線傳感器平面被投影為一個(gè)球面，平面上的任何點(diǎn)或者曲線都可以在球面上找到對應(yīng)的位置。詳細(xì)的證明以及數(shù)學(xué)模型已經(jīng)在第二章中介紹。數(shù)據(jù)聚集在實(shí)際的應(yīng)用中十分重要，而數(shù)據(jù)聚集指的是對于無線傳感器網(wǎng)絡(luò)產(chǎn)生的數(shù)據(jù)必定可以根據(jù)其數(shù)據(jù)類型進(jìn)行分類，例如傳感器網(wǎng)絡(luò)產(chǎn)生的數(shù)據(jù)可以分為溫度、濕度、風(fēng)向等。那么在實(shí)際應(yīng)用中自然需要根據(jù)某一類型的數(shù)據(jù)進(jìn)行

51、統(tǒng)計(jì)而得到對應(yīng)的結(jié)果。比如說在天氣應(yīng)用18中，我需要統(tǒng)計(jì)整個(gè)區(qū)域的濕度情況但收集不同類型信息的傳感器分別布置是不現(xiàn)實(shí)的。因此我們需要對數(shù)據(jù)進(jìn)行分類并分別傳輸。在傳感器網(wǎng)絡(luò)中不同的節(jié)點(diǎn)分別進(jìn)行處理。GHT模式會(huì)將數(shù)據(jù)哈希化為網(wǎng)絡(luò)區(qū)域的位置分別傳輸19，這樣的特性便能夠很好的支持上文中的應(yīng)用環(huán)境，也就是說可以很好的支持?jǐn)?shù)據(jù)聚集。在簡單雙直紋模式中，不存在數(shù)據(jù)類型的概念，因此在使用了簡單雙直紋模式的傳感器網(wǎng)絡(luò)中，想要獲取某一類型的數(shù)據(jù)需要檢索整個(gè)網(wǎng)絡(luò)，所需要的開銷自然不言而喻?？偨Y(jié)以上內(nèi)容，數(shù)據(jù)聚集在傳感器路由來說不是必要的，但支持?jǐn)?shù)據(jù)聚集的無線傳感器網(wǎng)絡(luò)的應(yīng)用范圍更廣，實(shí)用價(jià)值更高。而實(shí)現(xiàn)數(shù)據(jù)聚集

52、最簡單的方法就是使用GHT模式中采用的思路，對數(shù)據(jù)哈?；a(chǎn)生不同地理位置信息作為最終的目標(biāo)位置。文獻(xiàn)15中介紹了球面雙直紋模式的復(fù)制機(jī)制，我們在這里做簡單闡述。在一個(gè)球面上，任意兩個(gè)不重合的大圓在球面上必定有兩個(gè)交點(diǎn)，而球面上的大圓也必定能在傳感器平面上找到對應(yīng)的位置。在球面上，我們將數(shù)據(jù)哈?；癁閿?shù)據(jù)集結(jié)節(jié)點(diǎn)位置，做一條過數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)與數(shù)據(jù)集結(jié)節(jié)點(diǎn)的大圓。這條大圓我們就把它作為該數(shù)據(jù)的復(fù)制曲線，在復(fù)制該數(shù)據(jù)時(shí)我們就把它當(dāng)作標(biāo)準(zhǔn)，使用貪心算法對該數(shù)據(jù)進(jìn)行復(fù)制。如圖3.1所示，在球面上數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)記作p，數(shù)據(jù)集結(jié)節(jié)點(diǎn)記作h，數(shù)據(jù)復(fù)制曲線記作C(p,h)。對于產(chǎn)生該類型數(shù)據(jù)的另一個(gè)傳感器節(jié)點(diǎn)來說，我

53、們記為p'。同樣的，數(shù)據(jù)集結(jié)節(jié)點(diǎn)記為h，數(shù)據(jù)復(fù)制曲線記為C(p',h)。那么當(dāng)p和p'分布產(chǎn)生某類型的數(shù)據(jù)時(shí)，通過調(diào)用傳感器節(jié)點(diǎn)自身的哈希函數(shù)得到不同的數(shù)據(jù)集結(jié)節(jié)點(diǎn)h和h。分別過h和h得到對于數(shù)據(jù)的數(shù)據(jù)復(fù)制曲線C(p,h)和C(p',h)。根據(jù)球面投影和平面的一一對應(yīng)關(guān)系，球面上的數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)p和p'、數(shù)據(jù)集結(jié)節(jié)點(diǎn)h和h、對應(yīng)數(shù)據(jù)的復(fù)制曲線C(p,h)和C(p',h)都將在平面上找到對應(yīng)位置。在平面上，h和h對應(yīng)的節(jié)點(diǎn)我們記為h*和h*。圖3.1 數(shù)據(jù)復(fù)制曲線的球面投影15球面投影和平面上的唯一對應(yīng)關(guān)系奠定了球面雙直紋模式的基礎(chǔ)。雙直紋模式的復(fù)制

54、機(jī)制我們已經(jīng)介紹，但其體現(xiàn)的數(shù)據(jù)聚集特性是十分隱晦的，我們在這里詳細(xì)說明。不同數(shù)據(jù)的復(fù)制曲線都是經(jīng)過數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)與數(shù)據(jù)集結(jié)節(jié)點(diǎn)的大圓。那么哈?；嗤瑪?shù)據(jù)類型的數(shù)據(jù)所得到的地理位置必定是同一節(jié)點(diǎn)。舉例來說，對于某無線傳感器網(wǎng)絡(luò)中，兩個(gè)產(chǎn)生相同數(shù)據(jù)類型的傳感器節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)的數(shù)據(jù)復(fù)制曲線必定相交于兩點(diǎn)。因?yàn)檫@兩條曲線有公共點(diǎn)，那么這兩個(gè)相交的點(diǎn)就是這兩條復(fù)制曲線的數(shù)據(jù)集結(jié)節(jié)點(diǎn)，即哈希節(jié)點(diǎn)。在平面上這兩條復(fù)制曲線也同樣會(huì)有兩個(gè)相交的公共節(jié)點(diǎn)，即數(shù)據(jù)集結(jié)節(jié)點(diǎn)，如圖3.2所示。圖3.2 相同數(shù)據(jù)類型數(shù)據(jù)的復(fù)制曲線15圖3.2所示實(shí)心圓環(huán)代表數(shù)據(jù)的復(fù)制曲線，實(shí)心曲線代表數(shù)據(jù)的復(fù)制路徑，矩形代表數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)，

55、三角形代表數(shù)據(jù)集結(jié)節(jié)點(diǎn)。由于圖中兩個(gè)數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)是同一數(shù)據(jù)類型的，因此它們會(huì)在數(shù)據(jù)集結(jié)節(jié)點(diǎn)聚集。在檢索時(shí)檢索路徑只要檢索該數(shù)據(jù)集結(jié)節(jié)點(diǎn)就能獲取到這兩個(gè)數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)。不必像簡單雙直紋模式那樣檢索全部網(wǎng)絡(luò)才能獲取。因此總結(jié)如下，我們將簡單雙直紋模式中的復(fù)制緯線對應(yīng)球面雙直紋模式中的復(fù)制曲線，將GHT模式中的哈希節(jié)點(diǎn)對應(yīng)于球面雙直紋模式復(fù)制曲線中的某一節(jié)點(diǎn)，不同的數(shù)據(jù)復(fù)制曲線依然經(jīng)過哈希節(jié)點(diǎn)。不同的是這些復(fù)制曲線實(shí)際是存有一部分?jǐn)?shù)據(jù)的，就與簡單雙直紋模式中數(shù)據(jù)復(fù)制緯線一樣。在球面雙直紋模式中，復(fù)制曲線和簡單雙直紋模式相同。在傳輸某一數(shù)據(jù)時(shí)會(huì)在數(shù)據(jù)復(fù)制路徑上留下對應(yīng)數(shù)據(jù)的副本，但考

56、慮到復(fù)制消耗我們不在所有節(jié)點(diǎn)都進(jìn)行復(fù)制。也就是說，復(fù)制路徑中的一部分節(jié)點(diǎn)實(shí)際是存有指向該數(shù)據(jù)類型實(shí)際位置的信息。但檢索路徑檢索到這些節(jié)點(diǎn)時(shí)根據(jù)其提供的信息到對應(yīng)節(jié)點(diǎn)檢索。具體全部復(fù)制數(shù)據(jù)的間隔是由當(dāng)時(shí)的網(wǎng)絡(luò)能耗情況和數(shù)據(jù)及時(shí)性的要求決定的，例如及時(shí)性要求高的網(wǎng)絡(luò)復(fù)制間隔短一些。當(dāng)我們需要改變復(fù)制間隔時(shí)通過廣播修改信息使的整個(gè)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù)據(jù)間隔保持一致。3.2 數(shù)據(jù)復(fù)制的路由算法在無線傳感器網(wǎng)絡(luò)中，使用GHT模式和球面雙直紋模式的無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)之后必然傳輸?shù)焦９?jié)點(diǎn)。在GHT模式中，數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)使用貪心策略選擇距離哈希節(jié)點(diǎn)最近的節(jié)點(diǎn)作為該節(jié)點(diǎn)下一跳的傳輸對象，如此接替循環(huán)直到數(shù)據(jù)復(fù)制到哈希節(jié)點(diǎn)。使用GHT模式產(chǎn)生的數(shù)據(jù)復(fù)制路徑是數(shù)據(jù)產(chǎn)生節(jié)點(diǎn)到哈希節(jié)點(diǎn)的最短路徑。而在球面雙直紋模式中，無線傳感器網(wǎng)絡(luò)中的每一個(gè)