傳感器網(wǎng)絡(luò)中基于LEACH算法的改進(jìn)分簇模型研究畢業(yè)設(shè)計(jì)(論文)

1、hunan university 畢業(yè)設(shè)計(jì)(論文) 設(shè)計(jì)論文題目：設(shè)計(jì)論文題目： 傳感器網(wǎng)絡(luò)中基于傳感器網(wǎng)絡(luò)中基于 leachleach 算法的改進(jìn)算法的改進(jìn) 分簇模型研究分簇模型研究 學(xué)學(xué)生生姓姓名名： 學(xué)學(xué)生生學(xué)學(xué)號(hào)號(hào)： 專專業(yè)業(yè)班班級(jí)級(jí)： 學(xué)學(xué)院院名名稱稱： 指指導(dǎo)導(dǎo)老老師師： 學(xué)學(xué)院院院院長(zhǎng)長(zhǎng)： 傳感器網(wǎng)絡(luò)中基于傳感器網(wǎng)絡(luò)中基于 leachleach 算法的改進(jìn)分簇模型研究算法的改進(jìn)分簇模型研究 摘 要 無(wú)線傳感器網(wǎng)絡(luò)是眾多的傳感器通過(guò)無(wú)線通信的方式，相互聯(lián)系，處理、傳遞信 息的網(wǎng)絡(luò)。該網(wǎng)絡(luò)綜合了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、分布式信息處理技術(shù)和通信 技術(shù)，可以實(shí)時(shí)監(jiān)測(cè)、感知和采集網(wǎng)絡(luò)分

2、布區(qū)域內(nèi)的各種對(duì)象的信息，并對(duì)這些信息 進(jìn)行處理，傳送給所需用戶。無(wú)線傳感器網(wǎng)絡(luò)在軍事、工業(yè)、交通、安全、醫(yī)療、探 測(cè)以及家庭和辦公環(huán)境等很多方面都有著廣泛的用途，其研究、開(kāi)發(fā)和應(yīng)用，關(guān)系到 國(guó)家安全、經(jīng)濟(jì)發(fā)展的各個(gè)方面，近年來(lái)在國(guó)際上引起了廣泛的重視和投入。由于外 界環(huán)境的不確定性，經(jīng)常導(dǎo)致需要部署成百上千的傳感器協(xié)同工作，故對(duì)由大量傳感 器構(gòu)成的大規(guī)模傳感器網(wǎng)絡(luò)的研究正逐漸引起關(guān)注，并被認(rèn)為是本世紀(jì)的一項(xiàng)具有挑 戰(zhàn)性的研究課題。目前，學(xué)術(shù)界的研究熱點(diǎn)主要集中在傳感器網(wǎng)絡(luò)分簇算法、通信路 由協(xié)議、網(wǎng)絡(luò)覆蓋等領(lǐng)域。 leach 算法是一種典型的層次路由算法，該算法提出了低功耗持續(xù)運(yùn)行的模型。

3、但 leach 算法也存在沒(méi)有考慮能量的消耗和傳感器拓?fù)浣Y(jié)構(gòu)的問(wèn)題。本文提出了一 種傳感器網(wǎng)絡(luò)中能量有效的分簇算法，該算法在經(jīng)典的分簇算法 leach 的基礎(chǔ)上， 通過(guò)引入平均能耗調(diào)節(jié)參數(shù)和密度調(diào)節(jié)參數(shù)，使得靠近簇結(jié)構(gòu)地理中心位置的節(jié)點(diǎn)以 及位于節(jié)點(diǎn)密集分布區(qū)域的節(jié)點(diǎn)有更高機(jī)率成為簇頭。采用該算法時(shí)，傳感器網(wǎng)絡(luò)簇 頭的選取更為合理，從而進(jìn)一步優(yōu)化了簇的結(jié)構(gòu)，均衡了網(wǎng)絡(luò)的能量消耗，與采用 leach 算法相比，傳感器網(wǎng)絡(luò)的生命周期有一定幅度的延長(zhǎng)。 關(guān)鍵詞：傳感器網(wǎng)絡(luò)；分簇算法；平均能耗；節(jié)點(diǎn)密度 leach-based improved clustering model research in

4、 the sensor network abstract wireless sensor networks are a kind of network which a lot of sensors interrelate, process and transmit information with each other through wireless communications. the network integrates sensor technology, embedded computing technology, distributed information processin

5、g and communication technology which can be real-time monitoring, sensing and acquisition the information of various environmental monitoring or targeting object within regional of distribution networks. such information will be processed and transmitted to the user. wireless sensor networks are wid

6、ely used in military, industrial, transportation, security, medical, detection, family and office environment. the research, development and application of it relates to national security, economic development and other important fields. in recent years the wireless sensor networks have been caused

7、much attention and investment. external uncertainty environment often leads to hundreds of sensors shall be deploymented to work together, so the large-scale sensor networks research is gradually aroused widespread interest and considered a challenging research topic of this century. against the abo

8、ve problems, the academic research mainly concentrated in the sensor clustering algorithm, communications routing protocols, network coverage and sensor data fusion technology. leach algorithm is a typical level routing algorithm. this algorithm put forward a continued operation of low-power model.

9、but leach algorithm did not consider the problem of energy consumption and topology of the sensor. this paper presents an energy efficient clustering algorithm in sensor network. on the basis of the classical leach algorithm, through the introduction of average energy consumption adjustable paramete

10、rs and density adjustment parameters. the new algorithm enable the nodes which near the geographic center of the cluster structure or in the node-intensive region has a higher probability to be a cluster head. and it also takes into account both the choice of the cluster heads location and the size

11、of the network, then further optimizes the structure of the cluster, balances energy consumption, elects more reasonable cluster head which makes the life cycle of sensor networks has a larger extension on the basis of in leach algorithm. key words: sensor networks; clustering algorithms; the averag

12、e energy consumption; node density 目 錄 1. 緒論緒論.1 1.1 課題研究背景與意義.1 1.2 國(guó)內(nèi)外研究現(xiàn)狀.2 1.3論文結(jié)構(gòu)和研究?jī)?nèi)容.3 1.4 小結(jié).3 2. 傳感器網(wǎng)絡(luò)概述傳感器網(wǎng)絡(luò)概述.4 2.1 傳感器網(wǎng)絡(luò)簡(jiǎn)介.4 2.1.1 傳感器網(wǎng)絡(luò)的概念.4 2.1.2 傳感器網(wǎng)絡(luò)的特點(diǎn).5 2.1.3 傳感器網(wǎng)絡(luò)的核心技術(shù).6 2.2 傳感器網(wǎng)絡(luò)的應(yīng)用.6 2.2.1 環(huán)境的檢測(cè)和保護(hù).6 2.2.2 醫(yī)療護(hù)理.7 2.2.3 其他應(yīng)用.7 2.3傳感器網(wǎng)絡(luò)的特點(diǎn)與挑戰(zhàn).8 2.4小結(jié).9 3. leachleach 算法簡(jiǎn)介及分析算法簡(jiǎn)介及分

13、析.10 3.1引言.10 3.2 leach 算法.10 3.3 leach 算法中存在的問(wèn)題分析.12 3.3.1 未考慮簇頭在簇結(jié)構(gòu)中位置時(shí)存在的問(wèn)題.12 3.3.2 頻繁動(dòng)態(tài)拓?fù)渥儞Q帶來(lái)的問(wèn)題.15 3.4 小結(jié).16 4. 能量有效的分布式簇頭選取算法能量有效的分布式簇頭選取算法.17 4.1引言.17 4.2 eechs 算法.17 4.3算法性能分析.18 4.4小結(jié).20 5. 算法仿真實(shí)驗(yàn)算法仿真實(shí)驗(yàn).21 5.1實(shí)驗(yàn)平臺(tái).21 5.2實(shí)驗(yàn)設(shè)計(jì).21 5.3實(shí)驗(yàn)過(guò)程.22 5.4實(shí)驗(yàn)結(jié)果.24 5.5小結(jié).26 結(jié)結(jié) 論論.27 致致 謝謝.29 參考文獻(xiàn)參考文獻(xiàn).30 附

14、錄附錄 a a 部分源程序部分源程序.32 1. 緒論緒論 1.1 課題研究背景與意義 隨著通訊技術(shù)，計(jì)算機(jī)技術(shù)和傳感技術(shù)的日益成熟，微型傳感器在世界范圍內(nèi)廣 泛出現(xiàn)。傳感器網(wǎng)絡(luò)的發(fā)展經(jīng)歷了幾個(gè)階段，它最早出現(xiàn)在二十世紀(jì)七十年代，這個(gè) 時(shí)期的傳感器網(wǎng)絡(luò)具有點(diǎn)對(duì)點(diǎn)的傳輸能力和簡(jiǎn)單的信息獲取能力。隨后便出現(xiàn)了使用 串/并接口與傳感器連接，可以獲取多種信息的傳感器網(wǎng)絡(luò)。到了二十世紀(jì)九十年代后 期，智能傳感器采用現(xiàn)場(chǎng)總線連接形成局域網(wǎng)絡(luò)。隨著無(wú)線通訊技術(shù)被引入傳感器， 傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展和應(yīng)用發(fā)生了革命性的變化，以無(wú)線傳感器網(wǎng)絡(luò)為標(biāo)志的全新 的傳感器網(wǎng)絡(luò)研究領(lǐng)域，在基礎(chǔ)理論和工程技術(shù)兩個(gè)層面向科技工

15、作者提供了大量的 具有挑戰(zhàn)性的課題1-6。 由于傳感器網(wǎng)絡(luò)的巨大應(yīng)用價(jià)值，它已經(jīng)引起了世界許多國(guó)家的軍事部門、工業(yè) 界和學(xué)術(shù)界的極大關(guān)注。美國(guó)自然科學(xué)基金委員會(huì) 2003 年制定計(jì)劃并投巨資支持傳感 器網(wǎng)絡(luò)相關(guān)基礎(chǔ)理論的研究。美國(guó)國(guó)防部和各軍事部門把傳感器網(wǎng)絡(luò)作為一個(gè)重要研 究領(lǐng)域，設(shè)立了一系列的軍事傳感器網(wǎng)絡(luò)研究項(xiàng)目7。主要的信息工業(yè)界巨頭也開(kāi)始了 傳感器網(wǎng)絡(luò)方面的工作，紛紛設(shè)立或啟動(dòng)相應(yīng)的行動(dòng)計(jì)劃。其它一些國(guó)家也對(duì)傳感器 網(wǎng)絡(luò)表現(xiàn)出了極大的興趣，并紛紛展開(kāi)了在該領(lǐng)域的研究工作。 由于傳感器網(wǎng)絡(luò)具有異于 manet 的獨(dú)特性質(zhì)13，因此傳統(tǒng) manet 協(xié)議不適用 于傳感器網(wǎng)絡(luò)，需要為傳感器

16、網(wǎng)絡(luò)研究新的有效的路由算法。目前，在傳感器網(wǎng)絡(luò)的 路由算法研究中，鑒于傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)稠密分布、節(jié)點(diǎn)的能量、存儲(chǔ)及數(shù)據(jù)處理能 力十分有限的特性，一般采用基于分簇的方法來(lái)進(jìn)行路由算法設(shè)計(jì)，以提高路由算法 的性能。分簇算法作為路由協(xié)議的研究基礎(chǔ)，對(duì)路由算法性能的優(yōu)劣具有重要的影響。 此外，在傳感器網(wǎng)絡(luò)中，要保障信息的完整性，數(shù)據(jù)匯聚節(jié)點(diǎn)首先要判定該感興 趣的區(qū)域是否被一組給定的傳感器節(jié)點(diǎn)覆蓋，覆蓋問(wèn)題也因此被看作是衡量傳感器網(wǎng) 絡(luò)服務(wù)質(zhì)量(quality of service)的一種標(biāo)準(zhǔn)10。而覆蓋算法也是以分簇算法為基礎(chǔ)進(jìn)行 研究的。由于為改善傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量而提出的許多覆蓋算法是以分簇算法

17、作為 其研究基礎(chǔ)的，因此分簇算法的改進(jìn)可以極大的促進(jìn)覆蓋算法的性能。 綜上所述，本文研究傳感器網(wǎng)絡(luò)中能量有效的分簇算法，具有重要的理論意義與 實(shí)用價(jià)值。 1.2 國(guó)內(nèi)外研究現(xiàn)狀 由于外界環(huán)境的不確定性經(jīng)常導(dǎo)致需要布置成百上千的傳感器協(xié)同工作，故對(duì)由 大規(guī)模傳感器構(gòu)成的傳感器網(wǎng)絡(luò)的研究正逐漸引起廣泛關(guān)注，并被認(rèn)為是本世紀(jì)的一 向具有挑戰(zhàn)性的研究課題。針對(duì)以上問(wèn)題，學(xué)術(shù)界的研究熱點(diǎn)主要集中在傳感器分簇 算法、通信路由協(xié)議、傳感器網(wǎng)絡(luò)覆蓋以及傳感器數(shù)據(jù)融合技術(shù)上的研究上。 傳感器分簇算法通常包括兩個(gè)階段。第一個(gè)階段是根據(jù)一定的機(jī)制算法選取某個(gè) 接點(diǎn)作為簇頭，用于管理或控制整個(gè)簇內(nèi)成員節(jié)點(diǎn)，協(xié)調(diào)成員節(jié)

18、點(diǎn)之間的工作，負(fù)責(zé) 簇內(nèi)信息的收集和數(shù)據(jù)的融合處理以及簇間轉(zhuǎn)發(fā)。第二個(gè)階段是在選取簇頭的基礎(chǔ)上， 選取具有某種關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點(diǎn)形成集合，也就是成簇。 在成簇算法中，網(wǎng)絡(luò)通常被劃分為簇（cluster） 。每個(gè)簇由一個(gè)簇頭（cluster head）和多個(gè)簇內(nèi)成員（cluster member）組成，由簇頭與基站 bs（base station）通 信。 網(wǎng)絡(luò)分布如圖 1 所示， 圖 1.1 簇集網(wǎng)絡(luò)示意圖 1、簇頭選取算法 簇頭的產(chǎn)生是簇形成的基礎(chǔ)，在一些算法中，比如 max-min zpmin，簇頭 是被預(yù)先指定部署的，且假設(shè)它們的能量并不受限。但這是理想的情況，在實(shí) 際應(yīng)用是不可能實(shí)現(xiàn)的。更

19、多的簇頭選取算法綜合考慮了節(jié)點(diǎn)的剩余能量，簇 頭到基站的距離，簇內(nèi)通信代價(jià)等問(wèn)題。目前提出的主流簇頭選取算法有 leach、leach-f、daea、head、cefl、dchs、defg 等。 2、成簇算法 成簇算法在簇頭產(chǎn)生后，形成簇的拓?fù)浣Y(jié)構(gòu)，將網(wǎng)絡(luò)劃分成相連的區(qū)域。良好 的簇拓?fù)浣Y(jié)構(gòu)有助于延長(zhǎng)傳感器網(wǎng)絡(luò)的使用周期。目前提出的成簇算法有 acmwn、hyenas、eecs、pegasis、gaf、ace、fbcc 等。 1.3 論文結(jié)構(gòu)和研究?jī)?nèi)容 目前，人們基于節(jié)能的考慮已提出了各種各樣的路由協(xié)議，本文對(duì)其中的 leach 算法進(jìn)行分析，主要研究?jī)?nèi)容如下： (1) 詳細(xì)分析了 leach

20、 的簇頭選取以及成簇算法，并對(duì) leach 在簇頭選取和成 簇過(guò)程中存在的問(wèn)題進(jìn)行了說(shuō)明。 (2) 針對(duì) leach 算法在簇頭選取過(guò)程中沒(méi)有考慮簇頭在簇結(jié)構(gòu)中位置和沒(méi)有考慮 節(jié)點(diǎn)實(shí)際部署情況而引發(fā)的問(wèn)題，將基于節(jié)點(diǎn)平均能耗的簇頭選取算法和節(jié)點(diǎn)密度數(shù) 學(xué)模型結(jié)合起來(lái)，提出了能量有效簇頭選取算法。 (3) 對(duì)算法進(jìn)行仿真實(shí)驗(yàn)，并借鑒傳感器網(wǎng)絡(luò)中節(jié)能評(píng)價(jià)指標(biāo)體系對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行 質(zhì)量評(píng)價(jià)，最后本文通過(guò)理論分析和大量實(shí)驗(yàn)證明了新算法較 leach 算法性能更優(yōu) 越。 論文主要由以下部分構(gòu)成： 第一章對(duì)本課題背景和國(guó)內(nèi)外研究現(xiàn)狀做了描述。 第二章對(duì)傳感器網(wǎng)絡(luò)的概念以及應(yīng)用進(jìn)行介紹。 第三章對(duì)傳統(tǒng)的 le

21、ach 算法進(jìn)行了介紹，并詳細(xì)分析了其存在的不足。 第四章將節(jié)點(diǎn)密度模型和平均能耗模型結(jié)合起來(lái)，進(jìn)一步對(duì) leach 算法的簇頭 選取過(guò)程進(jìn)行改進(jìn)，提出了能量有效的簇頭選取算法。 第五章對(duì)算法進(jìn)行仿真模擬實(shí)驗(yàn)。 最后為結(jié)論與展望，首先本文工作進(jìn)行了總結(jié)，然后對(duì)下一步的研究方向進(jìn)行了 展望。 1.4 小結(jié) 本章首先給出了課題的研究背景與意義、然后綜述了國(guó)內(nèi)外傳感器網(wǎng)絡(luò)覆蓋判定 算法的研究現(xiàn)狀、最后，給出了論文的結(jié)構(gòu)和研究?jī)?nèi)容簡(jiǎn)介。 2. 傳感器網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)概述概述 2.1 傳感器網(wǎng)絡(luò)簡(jiǎn)介 2.1.1 傳感器網(wǎng)絡(luò)的概念 傳感器網(wǎng)絡(luò)是由一組傳感器以 ad-hoc 方式構(gòu)成的有線或無(wú)線網(wǎng)絡(luò)，其目的是

22、協(xié)作 地感知、采集和處理網(wǎng)絡(luò)覆蓋的地理區(qū)域中感知對(duì)象的信息，并發(fā)布給觀察者。 從定義可以看出，傳感器、感知對(duì)象和觀察者是傳感器網(wǎng)絡(luò)的 3 個(gè)基本要素；有 線或無(wú)線網(wǎng)絡(luò)是傳感器之間、傳感器與觀察者之間的通信方式，用于在傳感器與觀察 者之間建立通信路徑；協(xié)作地感知、采集、處理、發(fā)布感知信息是傳感器網(wǎng)絡(luò)的基本 功能。一組功能有限的傳感器協(xié)作地完成大的感知任務(wù)是傳感器網(wǎng)絡(luò)的重要特點(diǎn)。傳 感器網(wǎng)絡(luò)中的部分或全部節(jié)點(diǎn)可以移動(dòng)。傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也會(huì)隨著節(jié)點(diǎn)的移動(dòng) 而不斷地動(dòng)態(tài)變化。節(jié)點(diǎn)間以 ad-hoc 方式進(jìn)行通信，每個(gè)節(jié)點(diǎn)都可以充當(dāng)路由器的角 色，并且每個(gè)節(jié)點(diǎn)都具備動(dòng)態(tài)搜索、定位和恢復(fù)連接的能力。

23、傳感器由電源、感知部件、嵌入式處理器、存儲(chǔ)器、通信部件和軟件這幾部分構(gòu) 成（如圖 2.1 所示） 。電源為傳感器提供正常工作所必需的能源。感知部件用于感知、 獲取外界的信息，并將其轉(zhuǎn)換為數(shù)字信號(hào)。處理部件負(fù)責(zé)協(xié)調(diào)節(jié)點(diǎn)各部分的工作。通 信部件負(fù)責(zé)與其他傳感器或觀察者的通信。軟件則為傳感器提供必要的軟件支持，如 嵌入式操作系統(tǒng)、嵌入式數(shù)據(jù)庫(kù)系統(tǒng)等。 圖 2.1 傳感器示意圖 典型的傳感器網(wǎng)絡(luò)由傳感器節(jié)點(diǎn)、接收發(fā)送器(sink)、internet 或通信衛(wèi)星、任務(wù)管 理節(jié)點(diǎn)等部分構(gòu)成。傳感器節(jié)點(diǎn)散布在指定的感知區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)都可以收集數(shù)據(jù)， 并通過(guò)“多跳”路由方式把數(shù)據(jù)傳送到 sink。sink

24、也可以用同樣的方式將信息發(fā)送給各 節(jié)點(diǎn)。sink 直接與 internet 或通信衛(wèi)星相連，通過(guò) internet 或通信衛(wèi)星實(shí)現(xiàn)任務(wù)管理節(jié) 點(diǎn)(即觀察者)與傳感器之間的通信。圖 2.2 描述了一個(gè)典型的傳感器網(wǎng)絡(luò)的結(jié)構(gòu)14。 2.2典型的傳感器網(wǎng)絡(luò)的結(jié)構(gòu) 2.1.2 傳感器網(wǎng)絡(luò)的特點(diǎn) 傳感器網(wǎng)絡(luò)除了具有 ad-hoc 網(wǎng)絡(luò)的移動(dòng)性、斷接性、電源能力有限等特征外，還 具有以下鮮明特點(diǎn)14： (1) 通信能力有限。傳感器網(wǎng)絡(luò)中的傳感器的通信帶寬較窄而且經(jīng)常變化，通信覆 蓋范圍只有幾十到幾百米。傳感器之間的通信斷接頻繁，經(jīng)常導(dǎo)致通信失敗。由于傳 感器網(wǎng)絡(luò)更多地受到高山、建筑物、障礙物等地勢(shì)地貌以及

25、風(fēng)雨雷電等自然環(huán)境的影 響，傳感器可能會(huì)長(zhǎng)時(shí)間離線工作。 (2) 計(jì)算能力有限。傳感器網(wǎng)絡(luò)中的傳感器都具有嵌入式處理器和存儲(chǔ)器。這些傳 感器都具有計(jì)算能力，可以完成一些信息處理工作。但是，由于嵌入式處理器和存儲(chǔ) 器的能力和容量有限，傳感器的計(jì)算能力十分有限。使用大量具有有限計(jì)算能力的傳 感器進(jìn)行協(xié)作分布式信息處理，是我們的選擇之一。 (3) 傳感器數(shù)量大、分布范圍廣。傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)密集，數(shù)量巨大，可能 達(dá)到幾百、幾千萬(wàn)，甚至更多。此外，傳感器網(wǎng)絡(luò)可以分布在很廣泛的地理區(qū)域。傳 感器的數(shù)量與用戶數(shù)量比通常也非常大。這就要求傳感器網(wǎng)絡(luò)的軟、硬件必須具有高 強(qiáng)壯性和容錯(cuò)性。 (4) 感知數(shù)據(jù)

26、流巨大。傳感器網(wǎng)絡(luò)中的每個(gè)傳感器通常都產(chǎn)生較大的流式數(shù)據(jù)，并 具有實(shí)時(shí)性。每個(gè)傳感器僅僅具有有限的計(jì)算資源，難以處理巨大的實(shí)時(shí)數(shù)據(jù)流。這 就需要研究強(qiáng)有力的分布式數(shù)據(jù)流管理、查詢、分析和挖掘方法。 2.1.3 傳感器網(wǎng)絡(luò)的核心技術(shù) 以數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)的基本思想是：把傳感器視為感知數(shù)據(jù)流或感知數(shù)據(jù) 源，把傳感器網(wǎng)絡(luò)視為感知數(shù)據(jù)空間或感知數(shù)據(jù)庫(kù)，把數(shù)據(jù)管理和處理作為網(wǎng)絡(luò)的應(yīng) 用目標(biāo)。傳感器網(wǎng)絡(luò)以數(shù)據(jù)為中心的特點(diǎn)使得其設(shè)計(jì)方法不同于其他計(jì)算機(jī)網(wǎng)絡(luò)(包括 internet)。傳感器網(wǎng)絡(luò)的設(shè)計(jì)必須以感知數(shù)據(jù)管理和處理為中心，把數(shù)據(jù)庫(kù)技術(shù)和網(wǎng)絡(luò) 技術(shù)緊密結(jié)合，從邏輯概念和軟、硬件技術(shù)兩個(gè)方面實(shí)現(xiàn)一個(gè)

27、高性能的以數(shù)據(jù)為中心 的網(wǎng)絡(luò)系統(tǒng)，為用戶或觀察者提供一個(gè)有效的感知數(shù)據(jù)空間或感知數(shù)據(jù)庫(kù)管理和處理 系統(tǒng)，使用戶如同使用通常的數(shù)據(jù)庫(kù)管理系統(tǒng)和數(shù)據(jù)處理系統(tǒng)一樣自如地在傳感器網(wǎng) 絡(luò)上進(jìn)行感知數(shù)據(jù)的管理和處理。 感知數(shù)據(jù)管理與處理技術(shù)是實(shí)現(xiàn)以數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)的核心技術(shù)17。感知 數(shù)據(jù)管理與處理技術(shù)包括感知網(wǎng)絡(luò)數(shù)據(jù)的存儲(chǔ)、查詢、分析、挖掘、理解以及基于感 知數(shù)據(jù)決策和行為的理論和技術(shù)。傳感器網(wǎng)絡(luò)的各種實(shí)現(xiàn)技術(shù)必須與這些技術(shù)密切結(jié) 合，融為一體，而不是像目前其他網(wǎng)絡(luò)設(shè)計(jì)那樣分而治之。只有這樣才能夠設(shè)計(jì)實(shí)現(xiàn) 高效率的以數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)系統(tǒng)。 對(duì)感知數(shù)據(jù)管理與處理的研究方向主要包括：感知數(shù)據(jù)管理

28、技術(shù)的研究、感知數(shù) 據(jù)查詢處理技術(shù)的研究、感知數(shù)據(jù)分析技術(shù)的研究、感知數(shù)據(jù)挖掘技術(shù)的研究以及感 知數(shù)據(jù)管理系統(tǒng)的研究。 2.2 傳感器網(wǎng)絡(luò)的應(yīng)用 2.2.1 環(huán)境的檢測(cè)和保護(hù) 隨著人們對(duì)于環(huán)境問(wèn)題的關(guān)注程度越來(lái)越高，需要采集的環(huán)境數(shù)據(jù)也越來(lái)越多， 無(wú)線傳感器網(wǎng)絡(luò)的出現(xiàn)為隨機(jī)性的研究數(shù)據(jù)獲取提供了便利，并且還可以避免傳統(tǒng)數(shù) 據(jù)收集方式給環(huán)境帶來(lái)的侵入式破壞。比如，2002 年英特爾研究實(shí)驗(yàn)室研究人員曾經(jīng) 將 32 個(gè)小型傳感器連進(jìn)互聯(lián)網(wǎng)，掌握緬因州大鴨島上的氣候，以此評(píng)價(jià)一種海燕巢 的條件。2003 年第二季度，他們換用 150 個(gè)安有 d 型微型電池的第二代傳感器，來(lái)評(píng) 估這些鳥(niǎo)巢的條件。另外

29、，無(wú)線傳感器網(wǎng)絡(luò)可以跟蹤候鳥(niǎo)和昆蟲(chóng)的遷移，研究環(huán)境變 化對(duì)農(nóng)作物的影響，監(jiān)測(cè)海洋、大氣和土壤的成分等。它也可以應(yīng)用在精細(xì)農(nóng)業(yè)中， 來(lái)監(jiān)測(cè)農(nóng)作物中的害蟲(chóng)、土壤的酸堿度和施肥狀況等。 2.2.2 醫(yī)療護(hù)理 無(wú)線傳感器網(wǎng)絡(luò)在醫(yī)療研究、護(hù)理領(lǐng)域同樣可以大展身手。它可以用于病區(qū)移動(dòng) 查房、床邊護(hù)理、呼叫通信、護(hù)理監(jiān)控、藥庫(kù)管理等方面。 羅徹斯特大學(xué)的科學(xué)家使用無(wú)線傳感器創(chuàng)建了一個(gè)智能醫(yī)療房間，使用微塵來(lái)測(cè) 量居住者的重要征兆（血壓、脈搏和呼吸） 、睡覺(jué)姿勢(shì)以及每天 24 小時(shí)的活動(dòng)狀況。 英特爾公司也推出了無(wú)線傳感器網(wǎng)絡(luò)的家庭護(hù)理技術(shù)。該技術(shù)是作為探討應(yīng)對(duì)老齡化 社會(huì)的技術(shù)項(xiàng)目 center for a

30、ging services technologies（cast）的一個(gè)環(huán)節(jié)開(kāi)發(fā)的18。 該系統(tǒng)通過(guò)在鞋、家具以家用電器等家中道具和設(shè)備中嵌入半導(dǎo)體傳感器，幫助老齡 人士、阿爾茨海默氏病患者以及殘障人士的家庭生活。利用無(wú)線通信將各傳感器聯(lián)網(wǎng) 可高效傳遞必要的信息從而方便接受護(hù)理。而且還可以減輕護(hù)理人員的負(fù)擔(dān)。英特爾 主管預(yù)防性健康保險(xiǎn)研究的董事 eric dishman 稱， “在開(kāi)發(fā)家庭用護(hù)理技術(shù)方面，無(wú)線 傳感器網(wǎng)絡(luò)是非常有前途的領(lǐng)域”。 2.2.3 軍事領(lǐng)域 由于無(wú)線傳感器網(wǎng)絡(luò)具有密集型、低成本、隨機(jī)分布的節(jié)點(diǎn)組成，自組織性和容 錯(cuò)能力使其非常適合應(yīng)用于惡劣的戰(zhàn)場(chǎng)環(huán)境中，包括偵察敵情、監(jiān)控

31、兵力、裝備和物 資，判斷生物化學(xué)攻擊等多方面用途1。美國(guó)國(guó)防部遠(yuǎn)景計(jì)劃研究局已投資幾千萬(wàn)美元， 幫助大學(xué)進(jìn)行智能塵埃傳感器技術(shù)的研發(fā)。哈伯研究公司總裁阿爾門丁格預(yù)測(cè)：智 能塵埃式傳感器及有關(guān)的技術(shù)銷售將從 2004 年的 1000 萬(wàn)美元增加到 2010 年的幾十億 美元。 2.2.3 其他應(yīng)用 無(wú)線傳感器網(wǎng)絡(luò)還被應(yīng)用于其他一些領(lǐng)域。比如一些危險(xiǎn)的工業(yè)環(huán)境如井礦、核 電廠等，工作人員可以通過(guò)它來(lái)實(shí)施安全監(jiān)測(cè)。也可以用在交通領(lǐng)域作為車輛監(jiān)控的 有力工具。此外和還可以在工業(yè)自動(dòng)化生產(chǎn)線等諸多領(lǐng)域，英特爾正在對(duì)工廠中的一 個(gè)無(wú)線網(wǎng)絡(luò)進(jìn)行測(cè)試，該網(wǎng)絡(luò)由 40 臺(tái)機(jī)器上的 210 個(gè)傳感器組成，這樣組成

32、的監(jiān)控系 統(tǒng)將可以大大改善工廠的運(yùn)作條件。它可以大幅降低檢查設(shè)備的成本，同時(shí)由于可以 提前發(fā)現(xiàn)問(wèn)題，因此將能夠縮短停機(jī)時(shí)間，提高效率，并延長(zhǎng)設(shè)備的使用時(shí)間。盡管 無(wú)線傳感器技術(shù)目前仍處于初步應(yīng)用階段，但已經(jīng)展示出了非凡的應(yīng)用價(jià)值，相信隨 著相關(guān)技術(shù)的發(fā)展和推進(jìn)，一定會(huì)得到更大的應(yīng)用。 無(wú)線傳感器網(wǎng)絡(luò)有著十分廣泛的應(yīng)用前景，它不僅在工業(yè)、農(nóng)業(yè)、軍事、環(huán)境、 醫(yī)療等傳統(tǒng)領(lǐng)域有具有巨大的運(yùn)用價(jià)值，在未來(lái)還將在許多新興領(lǐng)域體現(xiàn)其優(yōu)越性， 如家用、保健、交通等領(lǐng)域。我們可以大膽的預(yù)見(jiàn)，將來(lái)無(wú)線傳感器網(wǎng)絡(luò)將無(wú)處不在， 將完全融入我們的生活。比如微型傳感器網(wǎng)絡(luò)最終可能將家用電器、個(gè)人電腦和其他 日常用品同互

33、聯(lián)網(wǎng)相連，實(shí)現(xiàn)遠(yuǎn)距離跟蹤。家庭采用無(wú)線傳感器網(wǎng)絡(luò)負(fù)責(zé)家電協(xié)同工 作，進(jìn)行安全調(diào)控，并且可以節(jié)省電能。另外，用戶可以根據(jù)自己的個(gè)人喜好，可以 利用傳感器網(wǎng)絡(luò)設(shè)置智能生活環(huán)境，如依據(jù)傳感器檢測(cè)數(shù)據(jù)來(lái)調(diào)節(jié)室內(nèi)光線強(qiáng)度、音 樂(lè)聲音，以形成愜意的房間氛圍。無(wú)線傳感器網(wǎng)絡(luò)將是未來(lái)的一個(gè)無(wú)孔不入的十分龐 大的網(wǎng)絡(luò)，其應(yīng)用可以涉及到人類日常生活和社會(huì)生產(chǎn)活動(dòng)的所有領(lǐng)域。 2.3 傳感器網(wǎng)絡(luò)的特點(diǎn)與挑戰(zhàn) 傳感器網(wǎng)絡(luò)除了具有 ad-hoc 網(wǎng)絡(luò)的移動(dòng)性、斷接性、電源能力局限等共同特征以 外，還具有很多其他鮮明的特點(diǎn)。這些特點(diǎn)向我們提出了一系列挑戰(zhàn)性問(wèn)題14： (1)通信能力有限。傳感器網(wǎng)絡(luò)的傳感器的通信帶寬窄而且

34、經(jīng)常變化，通信覆蓋范 圍只有幾十到幾百米。傳感器之間的通信斷接頻繁，經(jīng)常導(dǎo)致通信失敗。由于傳感器 網(wǎng)絡(luò)更多地受到高山、建筑物、障礙物等地勢(shì)地貌以及風(fēng)雨雷電等自然環(huán)境的影響， 傳感器可能會(huì)長(zhǎng)時(shí)間脫離網(wǎng)絡(luò)，離線工作。 (2)電源能量有限。傳感器的電源能量極其有限。網(wǎng)絡(luò)中的傳感器由于電源能量的原 因經(jīng)常失效或廢棄。電源能量約束是阻礙傳感器網(wǎng)絡(luò)應(yīng)用的嚴(yán)重問(wèn)題。商品化的無(wú)線 發(fā)送接收器電源遠(yuǎn)遠(yuǎn)不能滿足傳感器網(wǎng)絡(luò)的需要。傳感器傳輸信息要比執(zhí)行計(jì)算更消 耗電能.傳感器傳輸 1 位信息所需要的電能足以執(zhí)行 3000 條計(jì)算指令。 (3)計(jì)算能力有限。傳感器網(wǎng)絡(luò)中的傳感器都具有嵌入式處理器和存儲(chǔ)器。這些傳 感器

35、都具有計(jì)算能力，可以完成一些信息處理工作。但是，由于嵌入式處理器和存儲(chǔ) 器的能力和容量有限，傳感器的計(jì)算能力十分有限。如何使用大量具有有限計(jì)算能力 的傳感器進(jìn)行協(xié)作分布式信息處理，是我們面臨的第 3 個(gè)挑戰(zhàn)。 (4)傳感器數(shù)量大、分布范圍廣。傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)密集，數(shù)量巨大，可能 達(dá)到幾百、幾千萬(wàn)，甚至更多。此外，傳感器網(wǎng)絡(luò)可以分布在很廣泛的地理區(qū)域。傳 感器的數(shù)量與用戶數(shù)量比通常也非常大。傳感器數(shù)量大、分布廣的特點(diǎn)使得網(wǎng)絡(luò)的維 護(hù)十分困難甚至不可維護(hù)，傳感器網(wǎng)絡(luò)的軟、硬件必須具有高強(qiáng)壯性和容錯(cuò)性。 (5)網(wǎng)絡(luò)動(dòng)態(tài)性強(qiáng)。傳感器網(wǎng)絡(luò)具有很強(qiáng)的動(dòng)態(tài)性。網(wǎng)絡(luò)中的傳感器、感知對(duì)象和 觀察者這三要素

36、都可能具有移動(dòng)性，并且經(jīng)常有新節(jié)點(diǎn)加入或已有節(jié)點(diǎn)失效。因此， 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化，傳感器、感知對(duì)象和觀察者三者之間的路徑也隨之變化。 傳感器網(wǎng)絡(luò)必須具有可重構(gòu)和自調(diào)整性。 (6)大規(guī)模分布式觸發(fā)器。很多傳感器網(wǎng)絡(luò)需要對(duì)感知對(duì)象進(jìn)行控制，如溫度控制。 這樣，很多傳感器具有回控裝置和控制軟件。 (7)感知數(shù)據(jù)流巨大。傳感器網(wǎng)絡(luò)中的每個(gè)傳感器通常都產(chǎn)生較大的流式數(shù)據(jù)，并 具有實(shí)時(shí)性。每個(gè)傳感器僅僅具有有限的計(jì)算資源，難以處理巨大的實(shí)時(shí)數(shù)據(jù)流。這 就需要研究強(qiáng)有力的分布式數(shù)據(jù)流管理、查詢、分析和挖掘方法。 2.4 小結(jié) 本章首先給出了傳感器網(wǎng)絡(luò)的定義、特點(diǎn)以及傳感器網(wǎng)絡(luò)管理核心技術(shù)的描述， 然后，

37、簡(jiǎn)要介紹了傳感器網(wǎng)絡(luò)的應(yīng)用領(lǐng)域，最后，簡(jiǎn)述了當(dāng)前傳感器網(wǎng)絡(luò)研究中所面 臨的挑戰(zhàn)。 3. leach 算法簡(jiǎn)介及分析算法簡(jiǎn)介及分析 3.1 引言 未來(lái)的計(jì)算裝置將越來(lái)越與環(huán)境融于一體，直至它們對(duì)于用戶是不可見(jiàn)的。而分布 式無(wú)線傳感器網(wǎng)絡(luò)正是這一思想的重要體現(xiàn)。不斷小型化是微型傳感器的設(shè)計(jì)目標(biāo)， 而傳感器的能源供應(yīng)則是傳感器小型化過(guò)程中最主要的限制。 傳統(tǒng)的能量供應(yīng)裝置是電池，然而縮小電池的體積，增加電池容量的工程技術(shù)發(fā) 展緩慢，這直接影響了無(wú)線傳感器網(wǎng)絡(luò)的發(fā)展。無(wú)法從能量存儲(chǔ)的硬件設(shè)備上獲得突 破，于是科研人員開(kāi)始尋求延長(zhǎng)傳感器網(wǎng)絡(luò)使用壽命的其它途徑。這就是通過(guò)各種優(yōu) 化應(yīng)用，完善操作系統(tǒng)和通信

38、協(xié)議來(lái)降低網(wǎng)絡(luò)的能量消耗，從而在總能量不變的情況 下增加傳感器網(wǎng)絡(luò)的使用時(shí)間。 在上述背景下，各種有關(guān)傳感器網(wǎng)絡(luò)的路由算法和通信協(xié)議紛紛被提出，其中 heinzelman 等人提出的 leach 算法是最具代表性和里程碑意義的。 3.2 leach 算法 leach 算法是一種典型的層次路由算法。相比較平面路由算法而言，leach 算 法具有以下的優(yōu)點(diǎn)： 成員節(jié)點(diǎn)大部分時(shí)間可以關(guān)閉通信模塊，由簇頭構(gòu)成一個(gè)更上一層的連通網(wǎng) 絡(luò)來(lái)負(fù)責(zé)數(shù)據(jù)的長(zhǎng)距離路由轉(zhuǎn)發(fā)。這樣既保證了原有覆蓋范圍內(nèi)的數(shù)據(jù)通信， 也在很大程度上節(jié)省了網(wǎng)絡(luò)能量。 簇頭融合了成員節(jié)點(diǎn)的數(shù)據(jù)之后再進(jìn)行轉(zhuǎn)發(fā)，減少了數(shù)據(jù)通信量，降低了數(shù) 據(jù)冗

39、余，在節(jié)省了通訊能量的同時(shí)也降低了傳感器網(wǎng)絡(luò)在數(shù)據(jù)計(jì)算方面的能 量開(kāi)銷。 成員節(jié)點(diǎn)的功能比較簡(jiǎn)單，無(wú)須維護(hù)復(fù)雜的路由信息。這大大減少了網(wǎng)絡(luò)中 路由控制信息的數(shù)量，減少了通信量。 分簇拓?fù)浣Y(jié)構(gòu)便于管理，有利于分布式算法的應(yīng)用，可以對(duì)系統(tǒng)變化作出快 速反應(yīng)，具有較好的可擴(kuò)展性，適合大規(guī)模網(wǎng)絡(luò)。 leach 算法首先作了如下的假設(shè)： 基站(bs)遠(yuǎn)離傳感器網(wǎng)絡(luò)節(jié)點(diǎn)并且是穩(wěn)定的。 傳感器網(wǎng)絡(luò)中的所有節(jié)點(diǎn)是同構(gòu)的，并且能量都受到限制。 所有節(jié)點(diǎn)可以直接和基站通訊。 節(jié)點(diǎn)都沒(méi)有位置信息。 簇頭節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)壓縮匯聚以及與基站進(jìn)行通訊。 該算法主要通過(guò)隨機(jī)選擇簇首領(lǐng)，平均分擔(dān)中繼通信業(yè)務(wù)來(lái)實(shí)現(xiàn)節(jié)能。同時(shí) le

40、ach 定義了“輪”(round)的概念，針對(duì)每個(gè)節(jié)點(diǎn) n 設(shè)定了一個(gè)閥值 t(n)： (2.1) ：否則 ：若 0 ) 1 mod(1 )( gn p rp p nt 式(2.1)中 p 表示簇頭節(jié)點(diǎn)占網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的百分比，r 表示重新挑選簇頭節(jié)點(diǎn)的輪 數(shù)，g 表示網(wǎng)絡(luò)中最近 1/p 輪未當(dāng)選簇頭的節(jié)點(diǎn)的集合。并根據(jù)該閥值從候選節(jié)點(diǎn)中挑 選簇頭，具體的步驟： step1： 若傳感器節(jié)點(diǎn) nig，則對(duì)于每個(gè) ni 獨(dú)立運(yùn)算(2.1)式，獲得閥值 t(n)。 step2： 若 ni 不屬于 g，則根據(jù)(2.1)式，t(n)為零。 step3： ni 產(chǎn)生一個(gè) 01 之間的隨機(jī)數(shù) radomnum

41、。 step4： 若 t(n)radomnum，則該節(jié)點(diǎn)當(dāng)選為簇頭，并廣播當(dāng)選消息。 step5： 其余節(jié)點(diǎn)選擇加入某簇頭所在的簇，形成穩(wěn)定的拓?fù)浣Y(jié)構(gòu)。 step6： 穩(wěn)定工作階段。 step7： 每隔時(shí)間 t，進(jìn)行下一輪簇頭選取，轉(zhuǎn) step1，重新選擇簇頭并成簇。 由以上步驟可知 leach 算法中的輪是指兩次簇頭選取之間的時(shí)間段，每一輪由初 始化和穩(wěn)定工作兩個(gè)階段組成。在初始化階段，隨機(jī)選擇節(jié)點(diǎn)為簇首領(lǐng)，成為簇首領(lǐng) 的節(jié)點(diǎn)向周圍廣播信息，其它節(jié)點(diǎn)根據(jù)接受到廣播信息的強(qiáng)度來(lái)選擇它所要加入的簇， 并告知相應(yīng)的簇首領(lǐng)，由于信息的強(qiáng)度和節(jié)點(diǎn)之間的距離是成正比的，因此，實(shí)際上 各非 簇頭節(jié)點(diǎn)是選擇

42、距離自己地理距離最短的簇頭所在的簇加入，并形成簇拓?fù)浣Y(jié)構(gòu)，如 圖 3.1 所示： 圖 3.1 成簇階段圖 傳感器網(wǎng)絡(luò)首先產(chǎn)生中心節(jié)點(diǎn)，其余節(jié)點(diǎn)加入距離自己最近的中心節(jié)點(diǎn)所在的簇， 然后由中心節(jié)點(diǎn)直接和 sink 節(jié)點(diǎn)進(jìn)行通訊。在穩(wěn)定工作階段，節(jié)點(diǎn)持續(xù)采集監(jiān)測(cè)數(shù) 據(jù)，傳送到簇頭，由簇頭對(duì)數(shù)據(jù)進(jìn)行必要的融合處理之后，發(fā)送到終端節(jié)點(diǎn)。每輪工 作周期結(jié)束后，重新選擇簇頭并重復(fù)前面的工作。 3.3 leach 算法中存在的問(wèn)題分析 在上述的 leach 算法描述中，我們仔細(xì)思考，不難發(fā)現(xiàn)其中存在著以下的諸 多 問(wèn)題。 (1) 算法沒(méi)有考慮簇頭節(jié)點(diǎn)在簇結(jié)構(gòu)中的位置對(duì)簇頭能耗的影響。在簇頭選取的過(guò)程中， 位

43、于簇中心位置的節(jié)點(diǎn)和位于簇邊緣位置的節(jié)點(diǎn)成為簇頭的機(jī)率是一樣的。由于位于 簇邊緣位置的簇頭其通訊能耗遠(yuǎn)大于位于簇中心位置的簇頭，因此將導(dǎo)致各簇頭能耗 不均 衡，使某些簇頭節(jié)點(diǎn)能量提前耗盡。 (2) leach 沒(méi)有考慮到傳感器網(wǎng)絡(luò)在進(jìn)行部署的時(shí)候，節(jié)點(diǎn)分布密度對(duì)簇頭能耗的影 響。由此導(dǎo)致在傳感器節(jié)點(diǎn)密集分布區(qū)域的簇頭能耗巨大，而在傳感器節(jié)點(diǎn)稀疏分布 區(qū)域的簇頭能耗較小，網(wǎng)絡(luò)中各簇頭的能耗極不均衡。 (3) 動(dòng)態(tài)分簇引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變換和大量廣播通信，從而帶來(lái)了額外的能量開(kāi)銷。 3.3.1 未考慮簇頭在簇結(jié)構(gòu)中位置時(shí)存在的問(wèn)題 為指出未考慮簇頭在簇結(jié)構(gòu)中位置時(shí) leach 算法中存在的問(wèn)題，

44、首先假定通過(guò) 飛機(jī)播撒等方式部署的傳感器網(wǎng)絡(luò)中已經(jīng)形成了若干個(gè)簇。其中有某個(gè)簇由 5 個(gè)傳感 器節(jié)點(diǎn)構(gòu)成，且簇中各節(jié)點(diǎn) a，b，c，d，e 的初始能量均為 40，該簇的 5 個(gè)傳感器 節(jié)點(diǎn)的具體分布情況如圖 3.2 所示。 圖 3.2 具有 5 個(gè)節(jié)點(diǎn)的傳感器網(wǎng)絡(luò) 為計(jì)算方便，且假定簇中各節(jié)點(diǎn) a，b，c，d，e 兩兩之間的距離如表 2.1 所示： 表 3.1 圖 2.2 中節(jié)點(diǎn) a,b,c,d,e 兩兩間的距離 距離abcde a01243 b10364 c23032 d46303 e34230 假定在每輪通信中，各簇成員分別發(fā)送一次數(shù)據(jù)給簇頭，則每輪通信中各節(jié)點(diǎn)的工作 能 耗如表 2.2

45、所示： 表 3.2 a,b,c,d,e 分別為簇頭時(shí)各節(jié)點(diǎn)的工作能耗 簇頭/能耗abcde a102486 b2146128 c461064 d8126166 e684612 基于式(2.1)可知：采用 leach 算法時(shí)整個(gè)網(wǎng)絡(luò)的生命周期可能如表 2.3 所示： 表 3.3 采用 leach 算法時(shí)整個(gè)網(wǎng)絡(luò)的生命周期 簇頭/剩余能量abcde 第 1 輪：a 為簇頭3038363234 第 2 輪：b 為簇頭2824302026 第 3 輪：c 為簇頭2418201422 第 4 輪：d 為簇頭16614-216 顯然，采用 leach 算法時(shí)，整個(gè)網(wǎng)絡(luò)的生命周期將小于 4 輪。從上面的分析

46、不 難看出，leach 算法進(jìn)行第四輪簇頭選取時(shí)，沒(méi)有考慮到節(jié)點(diǎn)的剩余能量及其工作能 耗，導(dǎo)致剩余能量小于工作能耗的節(jié)點(diǎn) d 當(dāng)選為簇頭，使節(jié)點(diǎn) d 的能量過(guò)早衰竭，網(wǎng) 絡(luò)的生命周期也隨之結(jié)束。若結(jié)合考慮節(jié)點(diǎn)的位置信息，使靠近簇結(jié)構(gòu)中心位置且剩 余能量 較多的節(jié)點(diǎn)有更多機(jī)會(huì)成為簇頭，無(wú)疑將有效延長(zhǎng)網(wǎng)絡(luò)的生命周期。 3.3.2 未考慮節(jié)點(diǎn)分布密度時(shí)存在的問(wèn)題 為考慮節(jié)點(diǎn)分布密度對(duì)網(wǎng)絡(luò)生命周期的影響，給出一個(gè)具有 8 個(gè)節(jié)點(diǎn)的傳感 器 絡(luò)，如圖 2.3 所示。 圖 3.3 具有 8 個(gè)節(jié)點(diǎn)的傳感器網(wǎng)絡(luò) 假定各節(jié)點(diǎn)的初始能量均為 20，各節(jié)點(diǎn)簇內(nèi)通訊半徑為 10。其中 d，f，h 三個(gè)節(jié)點(diǎn)為最近 1

47、/p 輪未當(dāng)選簇頭的節(jié)點(diǎn)。網(wǎng)絡(luò)中各節(jié)點(diǎn) a，b，c，d，e，f，g，h 兩兩之間的距離如表 2.4 所示： 表 3.4 圖 2.3 中節(jié)點(diǎn) a,b,c,d,e,f,g,h 兩兩間的距離 距離abcdefgh a0584791114 b50449101313 c8404761111 d4440671012 e797604611 f910674058 g111311106506 h1413111211860 根據(jù) leach 算法，則有可能出現(xiàn)以下的成簇情況，各種情況下簇頭的能量 消耗如表 2.5 所示。由表 2.5 知，顯然在第 2 種情形下，即當(dāng) d，f 當(dāng)選為簇頭時(shí)， 簇頭節(jié)點(diǎn)的工作能耗最接

48、近均衡。因此，應(yīng)盡可能使密集分布區(qū)域中的節(jié)點(diǎn)比稀 疏分布區(qū)域中的節(jié)點(diǎn)具有更大當(dāng)選為簇頭的概率(即讓 d，f 當(dāng)選為簇頭的概率最 大化)，使得密集分布區(qū)域比稀疏分布區(qū)域產(chǎn)生更多簇頭，并且每個(gè)簇中成員節(jié) 點(diǎn)數(shù)目大致相同，各簇頭的工作能耗也相對(duì)均衡。 表 3.5 圖 2.3 中節(jié)點(diǎn)當(dāng)選簇頭的能耗情況 序號(hào)簇頭選取情形簇頭簇成員 當(dāng)選簇頭工作能 耗 1f 當(dāng)選為簇頭fa，b，c，d，e，g，h49 da，b，c12 2d，f 均當(dāng)選為簇頭 fe，g，h17 da，b，c，e，f25 3d，h 均當(dāng)選為簇頭 hg6 fa，b，c，d，e，g49 4f，h 均當(dāng)選為簇頭 h無(wú)0 da，b，c12 fe，g

49、95d，f，h 均當(dāng)選為簇頭 h無(wú)0 3.3.3 頻繁動(dòng)態(tài)拓?fù)渥儞Q帶來(lái)的問(wèn)題 由于傳感器網(wǎng)絡(luò)在使用 leach 算法的時(shí)候存在輪的概念，并且每輪結(jié)束后， 都要重新產(chǎn)生新的簇頭節(jié)點(diǎn)，然后圍繞這些簇頭再產(chǎn)生新的簇。這使得傳感器網(wǎng) 絡(luò)的拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)變化的，并且為了維持這種拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)性，必須要耗費(fèi) 大量的能量進(jìn)行計(jì)算和通訊。 下面對(duì) leach 算法每輪動(dòng)態(tài)成簇耗費(fèi)的能量和簇結(jié)構(gòu)穩(wěn)定階段每次工作耗費(fèi) 的能量進(jìn)行一下對(duì)比。 1每輪動(dòng)態(tài)成簇的能量開(kāi)銷包括以下幾個(gè)方面 (1) 網(wǎng)絡(luò)中所有的節(jié)點(diǎn)獨(dú)立的進(jìn)行運(yùn)算，然后根據(jù)結(jié)果判斷自己是否能夠成為 簇頭節(jié)點(diǎn)所耗費(fèi)的能量。 (2) 當(dāng)選簇頭的節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播

50、自己當(dāng)選為簇頭并邀請(qǐng)其它節(jié)點(diǎn)加入簇所 耗費(fèi)的能量。 (3) 非簇頭節(jié)點(diǎn)收到邀請(qǐng)后同時(shí)向合適的簇頭節(jié)點(diǎn)發(fā)送成簇請(qǐng)求消息所耗費(fèi)的 能量。 (4) 簇頭節(jié)點(diǎn)接收成簇請(qǐng)求所耗費(fèi)的能量。 2傳感器網(wǎng)絡(luò)穩(wěn)定階段每輪工作耗費(fèi)的能量包括以下幾個(gè)方面 (1) 所有節(jié)點(diǎn)采集周圍數(shù)據(jù)所耗費(fèi)的能量。 (2) 非簇頭節(jié)點(diǎn)向簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)所耗費(fèi)的能量。 (3) 簇頭節(jié)點(diǎn)接受數(shù)據(jù)所耗費(fèi)的能量。 (4) 簇頭節(jié)點(diǎn)將接收到的數(shù)據(jù)進(jìn)行匯聚融合計(jì)算所耗費(fèi)的能量。 (5) 簇頭節(jié)點(diǎn)將處理后的數(shù)據(jù)發(fā)送給基站所耗費(fèi)的能量。 不難看出，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化一次的開(kāi)銷接近傳感器網(wǎng)絡(luò)工作一次的能量開(kāi) 銷。如果能盡可能的長(zhǎng)時(shí)間保持拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性

51、，則可以減少拓?fù)浣Y(jié)構(gòu)變化的 次數(shù)，使能量更多的消耗在更有意義的工作階段。 3.4 小結(jié) 針對(duì) leach 算法中存在的問(wèn)題，學(xué)術(shù)界展開(kāi)了廣泛的研究，并提出了許多基于 leach 的改進(jìn)算法。這些算法從不同的條件和需求出發(fā)，都是以延長(zhǎng)傳感器網(wǎng)絡(luò)的生 命周期為目的，為傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用提供了許多行之有效的解決方案。 4. 能量有效的分布式簇頭選取算法能量有效的分布式簇頭選取算法 4.1 引言 目前提出的很多路由算法都沒(méi)有考慮傳感器節(jié)點(diǎn)的實(shí)際分布情況。事實(shí)上，受到 自然界氣流、地形等因素的影響，傳感器網(wǎng)絡(luò)在實(shí)際部署的時(shí)候，節(jié)點(diǎn)可能在某個(gè)局 部分布非常的密集，而在其它的一些地方分布又非常稀疏。因此在

52、這種情況下，簡(jiǎn)單 的采用 leach 算法中的簇頭選取機(jī)制，那么選擇出來(lái)的簇頭就會(huì)出現(xiàn)如本文 3.3.2 節(jié) 中所描述的問(wèn)題，從而導(dǎo)致傳感器網(wǎng)絡(luò)生命周期的提前結(jié)束，這是不希望被看到的。 本章首先提出了密度調(diào)節(jié)參數(shù)數(shù)學(xué)模型，然后把其與上一章提出的平均能耗調(diào)節(jié) 參數(shù)結(jié)合起來(lái)，進(jìn)而提出了能量有效的分布式簇頭選取算法。實(shí)驗(yàn)證明采用該算法與 采用 leach 算法相比較，傳感器網(wǎng)絡(luò)的生命周期有一定幅度的延長(zhǎng)。 4.2 eechs 算法 為了解決上面的問(wèn)題，首先必須量化傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)分布密度，為方便描述， 不妨做如下的假設(shè)： (1) 傳感器的通信半徑 r 可以根據(jù)需求而改變，r0是基本通信半徑，r= r

53、0； (2) ni表示傳感器網(wǎng)絡(luò)中的第 i 個(gè)節(jié)點(diǎn)； (3) 任意節(jié)點(diǎn) ni坐標(biāo)為； (,) ii nn xy (4) dist(ni，nj)=f(signalintension) 22 ijij nnnn xxyy 根據(jù)上面的假設(shè)，可知 dist(ni，nj)表示傳感器網(wǎng)絡(luò)中任意兩點(diǎn)之間的直線距離，但是 由于在分布式路由算法中節(jié)點(diǎn)的位置信息都無(wú)法獲取，因此給出函數(shù) f(signalintension)， 其中 signalintension 表示 ni節(jié)點(diǎn)接收到的，由 nj節(jié)點(diǎn)發(fā)出的信號(hào)的強(qiáng)度，這個(gè)值可以 通過(guò) ni節(jié)點(diǎn)的通訊模塊獲得，而 f(signalintension)則表示接收信號(hào)的

54、強(qiáng)度與收發(fā)信號(hào)的 兩節(jié)點(diǎn)之間距離的映射關(guān)系。 對(duì)于任意節(jié)點(diǎn) ni，若 dist(ni，nj)r0，則稱 nj為 ni的鄰居節(jié)點(diǎn)。 從上面的描述不難看出，當(dāng)某個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)非常多的時(shí)候，意味著以該節(jié)點(diǎn) 為圓心，節(jié)點(diǎn)基本通信半徑為半徑的圓形區(qū)域分布的節(jié)點(diǎn)很多，單位區(qū)域節(jié)點(diǎn)的密度 很高。故可以把節(jié)點(diǎn)分布密度量化為關(guān)于其鄰居節(jié)點(diǎn)總數(shù)的正比例函數(shù)。 根據(jù)前面的分析，本節(jié)提出一種能量有效的分布式簇頭選取算法(eechs，energy efficient cluster heads selection)，該算法同時(shí)引入能量調(diào)節(jié)參數(shù)和密度調(diào)節(jié)參數(shù)，通過(guò) 能量調(diào)節(jié)參數(shù)可以使得剩余能量越大且每輪平均工作能耗越小

55、的節(jié)點(diǎn)有更多機(jī)會(huì)成為 簇頭。通過(guò)密度調(diào)節(jié)參數(shù)可以使得分布密度越大區(qū)域的節(jié)點(diǎn)有更多機(jī)會(huì)成為簇頭。 密度調(diào)節(jié)參數(shù)如式(4.1)；( )( )-1)( )f nnodedensity inodedensity i 其中 nodedensity(i)= ，n(j)neighborset(i)。neighborset(i)是節(jié)點(diǎn) 1 ( ) j m j n j ni 的鄰居節(jié)點(diǎn)集合。即 nodedensity(i)的值表示節(jié)點(diǎn) ni 的鄰居節(jié)點(diǎn)的總數(shù)，也就是以 n(i)為圓心，r0 為半徑的圓形區(qū)域的節(jié)點(diǎn)的個(gè)數(shù)。當(dāng) nodedensity(i)的值比較大時(shí)，意 味著該節(jié)點(diǎn)所在區(qū)域節(jié)點(diǎn)分布的密度比較大。故

56、，式(2.1)可修訂為式(4.2)： (4.2) *( ) 1 1( mod) ( ) 0 p f nng p r t n p ：若 ：否則 引入一個(gè)調(diào)節(jié)函數(shù)，通過(guò)該調(diào)節(jié)函數(shù)可以使得剩余能量越大且每輪平均() avg cur e f e 能耗越小的節(jié)點(diǎn)有更多機(jī)會(huì)成為簇頭。調(diào)節(jié)函數(shù)的定義如下：() avg cur e f e (i) 1 () 0 avg avgcur avg cur cur e eee f e e ：若 ：否則 在式(i)中，ecur表示節(jié)點(diǎn)當(dāng)前的剩余能量，eavg表示節(jié)點(diǎn)每輪的平均能耗。故，式(2.1) 可修訂為以下式(ii)： (ii) () 1 1( mod) ( ) 0

57、 avg cur pe fng e p r t n p ：若 ：否則 在上式(ii)中，當(dāng)整個(gè)網(wǎng)絡(luò)能量較低， 即 ecureavg且 ecur與 eavg接近時(shí)，值趨() ave cur e f e 近于零，則 t(n)的值接近 0，意味所有節(jié)點(diǎn)當(dāng)選為簇頭的概率均趨向于 0，顯然不符合 實(shí)際情況。為了保障在上述情形中各節(jié)點(diǎn)同樣能以較大概率當(dāng)選為簇頭，我們將式(ii) 進(jìn)一步改進(jìn)如式(iii)所示。 (iii) 1 ()1() 1 ( ) 1( mod) 0 avgavg s curcur pee fdivfng r t np ee p r p ：若 ：否則 其中，rs 為節(jié)點(diǎn)連續(xù)未當(dāng)選為簇頭的

58、輪數(shù)，一旦節(jié)點(diǎn)當(dāng)選簇頭，則 rs 重置為 0。 得出能量調(diào)節(jié)參數(shù)如式(4.3)： (4.3) 1 (1) ( ) 1 avg ave s avgcur curcur s e e divee r epe h n div r p ： ：否則 故 leach 算法的式(2.1)可以改進(jìn)為如式(4.4)所示： (4.4) *( )*( ) 1 ( ) 1( mod) 0 p a f nb h nng t n p r p ：若 ：否則 由于 f(n)和 h(n)都為純小數(shù)，并且要求 0t(n) 1，因此 的取*( )*( )a f nb h n 值范圍必須在 0 和 1 之間。故式(4.4)中的 a，b

59、 兩參數(shù)要滿足如下關(guān)系，如式(4.5)： a + b = 1 (4.5) 顯然，a=0，b=1 時(shí)，式(4.4)將簡(jiǎn)化為以下式(4.6)： (4.6) ( ) 1 1( mod) ( ) 0 p h nng p r t n p ：若 ：否則 即只在leach 算法中進(jìn)一步考慮剩余能量與工作能耗對(duì)網(wǎng)絡(luò)生命周期的影響。 而當(dāng) a=1，b=0 時(shí)，式(4.4)將簡(jiǎn)化為以下式(4.7)： (4.7) ( ) 1 1( mod) ( ) 0 p f nng p r t n p ：若 ：否則 即只在 leach 算法中進(jìn)一步考慮節(jié)點(diǎn)分布密度對(duì)網(wǎng)絡(luò)生命周期的影響。 4.3 算法性能分析 為了說(shuō)明上述算法的性

60、能，下面仍以第 3.3.1 節(jié)中圖 3.3 所示網(wǎng)絡(luò)為例，來(lái)計(jì)算采 用新算法時(shí)整個(gè)網(wǎng)絡(luò)的生命周期。 (1) 假設(shè)傳感器節(jié)點(diǎn)的基本通訊半徑設(shè)置為 10，所以可以很容易的計(jì)算出各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)總 數(shù)，如表 4.1 所示： 表 4.1 鄰居節(jié)點(diǎn)表 節(jié)點(diǎn)鄰居節(jié)點(diǎn)總數(shù) a6 b6 c6 d7 e8 f9 g5 h3 (2) 根據(jù)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)總數(shù)計(jì)算出各節(jié)點(diǎn)的密度調(diào)節(jié)參數(shù)f(n)，如表4.2 所示： 表 4.2 各節(jié)點(diǎn)密度調(diào)節(jié)參數(shù)表 c5/6 d6/7 e7/8 f8/9 g4/5 h2/3 (3) 由于只有 d，f，h 三個(gè)節(jié)點(diǎn)為最近 1/p 輪未當(dāng)選簇頭的節(jié)點(diǎn)，因此只需要計(jì) 算這 3 個(gè)候選簇頭節(jié)點(diǎn)