無線傳感器網(wǎng)絡(luò)分簇算法研究

PAGE裝訂線裝訂線本科生畢業(yè)論文（設(shè)計(jì)）題目：無線傳感器網(wǎng)絡(luò)分簇算法研究系部計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科門類工科專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)姓名指導(dǎo)教師

無線傳感器網(wǎng)絡(luò)分簇算法研究摘要無線傳感器網(wǎng)絡(luò)是大量傳感器節(jié)點(diǎn)以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)一般都被安置在野外甚至是人們無法到達(dá)的地方，只能靠自帶的電池供電，網(wǎng)絡(luò)節(jié)點(diǎn)的能量極其有限，因此所有的信息處理策略都必須考慮到盡可能地降低節(jié)點(diǎn)能耗。分簇算法是將無線傳感器網(wǎng)絡(luò)分成若干個(gè)簇，每個(gè)簇選出一個(gè)簇頭，簇頭作為本地基站將簇內(nèi)節(jié)點(diǎn)傳給它的數(shù)據(jù)進(jìn)行融合后再傳給基站，因而大大降低了節(jié)點(diǎn)消耗的能量，延長(zhǎng)了網(wǎng)絡(luò)壽命。本文闡述典型的無線傳感器網(wǎng)絡(luò)，著重對(duì)LEACH算法進(jìn)行分析。在windows系統(tǒng)中搭建NS2無線傳感器網(wǎng)絡(luò)模擬平臺(tái)，并對(duì)LEACH算法進(jìn)行仿真模擬，觀察此算法的運(yùn)行過程，分析LEACH算法的優(yōu)缺點(diǎn)，論證了LEACH算法的可行性與高效性。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)LEACH算法NS2分簇

ABSTRACTThewirelesssensornetworkconsistsofalargenumberofsensornodesinthewayofself-organizingandmulti-hop.Sensornodesaregenerallyplacedinthewild,orevenintheplacewherepeoplecannotreach.Itcanonlyrelyonthebuilt-inbattery-powered.Networknodeenergyisextremelylimited,soalloftheinformationprocessingstrategiesmusttakereducingnodepowerconsumptionintoaccountasmuchaspossible.Clusteringalgorithmistodividewirelesssensornetworkintoseveralclusters,thenelectaclusterheadfromeachcluster.Theclusterheadfunctionsasalocalbasestation,integratingthedatawhichtheclusternodehaspassedtoitandthenpasstheresulttothebasestation.Thus,thenodeenergyconsumptionisreducedgreatly,thiscanhelptoprolongthelifetimeofthenetwork.Thispaperelaboratesatypicalwirelesssensornetwork,itfocusesonanalyzingtheLEACHalgorithm.SettingupaNS2wirelesssensornetworksimulationplatforminthewindowssystemanddoingtheLEACHalgorithmsimulationtoobservetherunningofthisalgorithm;besides,analyzingtheadvantagesanddisadvantagesofLEACHalgorithmanddemonstratingthefeasibilityandefficiencyoftheLEACHalgorithm.Keywords:wirelesssensornetworksLEACHalgorithmNS2clustering

目錄第1章緒論 11.1課題研究背景與意義 11.2國(guó)內(nèi)外研究現(xiàn)狀 11.3本文研究?jī)?nèi)容 21.4本文組織結(jié)構(gòu) 2第2章無線傳感器網(wǎng)絡(luò)概述 32.1無線傳感器網(wǎng)絡(luò)基本概念 32.1.1無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu) 32.1.2傳感器網(wǎng)絡(luò)的特征 32.2無線傳感器網(wǎng)絡(luò)的應(yīng)用 32.3無線傳感器的關(guān)鍵技術(shù) 4第3章無線傳感器網(wǎng)絡(luò)拓?fù)淇刂?63.1拓?fù)淇刂聘攀?63.2功率控制 73.2.1概述 73.2.2基于節(jié)點(diǎn)度的算法 73.2.3基于鄰近圖的算法 83.3層次型拓?fù)浣Y(jié)構(gòu)控制 103.3.1LEACH算法 103.3.2GAF算法 10第4章LEACH算法協(xié)議 124.1LEACH算法原理 124.2LEACH算法的分析與實(shí)現(xiàn) 124.3LEACH算法的特點(diǎn) 134.4算法中存在的問題分析及改進(jìn) 134.4.1算法中的問題 134.4.2LEACH算法的改進(jìn) 13第5章LEACH算法仿真 165.1NS2仿真軟件 165.1.1NS2仿真軟件概述 165.1.2NS2擴(kuò)展功能 175.1.3NS2軟件構(gòu)成 175.1.4使用方法 185.2LEACH算法仿真 195.2.1LEACH算法實(shí)現(xiàn) 195.2.2核心代碼分析 255.2.3NSG2可視化工具介紹 305.2.4LEACH算法仿真結(jié)果分析 31第6章結(jié)論 34致謝 35參考文獻(xiàn) 36附錄 37PAGE57第1章緒論1.1課題研究背景與意義傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量極其有限，所有的信息處理策略都必須考慮到盡可能地降低節(jié)點(diǎn)能耗，以便延長(zhǎng)網(wǎng)絡(luò)和整個(gè)系統(tǒng)的壽命。將傳感器節(jié)點(diǎn)組織成簇的形式能有效減少網(wǎng)絡(luò)的能量消耗，許多能量有效的路由協(xié)議都是在簇結(jié)構(gòu)的基礎(chǔ)上進(jìn)行設(shè)計(jì)的。分簇算法也可以用于執(zhí)行數(shù)據(jù)融合，將無線傳感器感測(cè)的大量數(shù)據(jù)組合成少量有意義的信息集合。在簇結(jié)構(gòu)下，算法只在一個(gè)簇范圍內(nèi)執(zhí)行而不需要等待控制消息傳遍整個(gè)網(wǎng)絡(luò)。在大型網(wǎng)絡(luò)中，這一特點(diǎn)使得局部化算法比在整個(gè)全局結(jié)構(gòu)中執(zhí)行的中心化算法具有更好的擴(kuò)展性。同時(shí)，分簇算法的研究對(duì)于信息廣播和數(shù)據(jù)查詢也非常有用，簇頭可以在簇內(nèi)協(xié)助廣播消息和搜集用戶需要的數(shù)據(jù)。無線傳感器網(wǎng)絡(luò)是新興的下一代傳感器網(wǎng)絡(luò)。最早的代表性論述出現(xiàn)在1999年，題為“傳感器走向無線時(shí)代”。隨后在美國(guó)的移動(dòng)計(jì)算和網(wǎng)絡(luò)國(guó)際會(huì)議上，提出了無線傳感器網(wǎng)絡(luò)是下一個(gè)世紀(jì)面臨的發(fā)展機(jī)遇。2003年，美國(guó)《技術(shù)評(píng)論》雜志論述未來新興十大技術(shù)時(shí)，無線傳感器網(wǎng)絡(luò)被列為第一項(xiàng)未來新興技術(shù)。同年，美國(guó)《商業(yè)周刊》未來技術(shù)專版，論述四大新技術(shù)時(shí)，無線傳感器網(wǎng)絡(luò)也列人其中。美國(guó)《今日防務(wù)》雜志更認(rèn)為無線傳感器網(wǎng)絡(luò)的應(yīng)用和發(fā)展，將引起一場(chǎng)劃時(shí)代的軍事技術(shù)革命和未來戰(zhàn)爭(zhēng)的變革。2004年(IEEESpectrum)雜志發(fā)表一期專集：傳感器的國(guó)度，論述無線傳感器網(wǎng)絡(luò)的發(fā)展和可能的廣泛應(yīng)用?？梢灶A(yù)計(jì)，無線傳感器網(wǎng)絡(luò)的發(fā)展和廣泛應(yīng)用，將對(duì)人們的社會(huì)生活、產(chǎn)業(yè)變革帶來極大的影響和產(chǎn)生巨大的推動(dòng)[1]。1.2國(guó)內(nèi)外研究現(xiàn)狀無線傳感器網(wǎng)絡(luò)是從傳感器網(wǎng)絡(luò)開始的，第一代傳感器網(wǎng)絡(luò)出現(xiàn)在20世紀(jì)70年代。使用具有簡(jiǎn)單信息信號(hào)獲取能力的傳統(tǒng)傳感器，采用點(diǎn)對(duì)點(diǎn)傳輸、連接傳感控制器構(gòu)成傳感器網(wǎng)絡(luò)；第二代傳感器網(wǎng)絡(luò)，具有獲取多種信息信號(hào)的綜合能力，采用串、并接口(如Rs-232、RS-485)與傳感控制器相聯(lián)，構(gòu)成有綜合多種信息的傳感器網(wǎng)絡(luò)；第三代傳感器網(wǎng)絡(luò)出現(xiàn)在20世紀(jì)90年代后期和本世紀(jì)初，用具有智能獲取多種信息信號(hào)的傳感器，采用現(xiàn)場(chǎng)總線連接傳感控制器，構(gòu)成局域網(wǎng)絡(luò)，成為智能化傳感器網(wǎng)絡(luò)；第四代傳感器網(wǎng)絡(luò)正在研究開發(fā)，目前成形并大量投入使用的產(chǎn)品還沒有出現(xiàn)．用大量的具有多功能多信息信號(hào)獲取能力的傳感器，采用自組織無線接入網(wǎng)絡(luò)，與傳感器網(wǎng)絡(luò)控制器連接，構(gòu)成無線傳感器網(wǎng)絡(luò)。20世紀(jì)90年代在美國(guó)發(fā)端了現(xiàn)代意義的無線傳感器網(wǎng)絡(luò)技術(shù)。隨后，該技術(shù)被一些重要機(jī)構(gòu)預(yù)測(cè)為將改變世界的重要新技術(shù)，相關(guān)研究工作在各主要發(fā)達(dá)國(guó)家轟轟烈烈地開展起來。我國(guó)現(xiàn)代意義的無線傳感器網(wǎng)絡(luò)及其應(yīng)用研究幾乎與發(fā)達(dá)國(guó)家同步啟動(dòng)，首次正式出現(xiàn)于1999年中國(guó)科學(xué)院《知識(shí)創(chuàng)新工程試點(diǎn)領(lǐng)域方向研究》的“信息與自動(dòng)化領(lǐng)域研究報(bào)告”中，最為該領(lǐng)域提出的五個(gè)重大項(xiàng)目之一。隨著知識(shí)創(chuàng)新工程試點(diǎn)工作的深入，2001年中國(guó)科學(xué)院依托上海微系統(tǒng)所成立微系統(tǒng)研究與發(fā)展中心，旨在引領(lǐng)中國(guó)科學(xué)院內(nèi)部的相關(guān)工作。為系統(tǒng)研究與發(fā)展中心在無線傳感器網(wǎng)絡(luò)方向上陸續(xù)部署了若干重大研究項(xiàng)目和方向性項(xiàng)目，參加單位包括上海微系統(tǒng)所、聲學(xué)所、微電子所、半導(dǎo)體所、電子所、軟件以及中國(guó)科技大學(xué)等10余個(gè)研究所和高校。進(jìn)過幾年的努力，初步建立了傳感器網(wǎng)絡(luò)系統(tǒng)的研究平臺(tái)，在無線智能傳感器網(wǎng)絡(luò)通信技術(shù)、微型傳感器、傳感器端機(jī)、移動(dòng)基站和應(yīng)用系統(tǒng)等方面取得了很大進(jìn)展。2004年9月相關(guān)成果在北京盡心了大規(guī)模外場(chǎng)演出，部分成果已在實(shí)際工程系統(tǒng)中應(yīng)用[2]。1.3本文研究?jī)?nèi)容在滿足網(wǎng)絡(luò)覆蓋度和連通度的前提下，通過功率控制和骨干網(wǎng)節(jié)點(diǎn)選擇，剔除節(jié)點(diǎn)之間不必要的通信鏈路，形成一個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。功率控制機(jī)制調(diào)節(jié)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的發(fā)射功率，在滿足網(wǎng)絡(luò)連通度的前提下，均衡節(jié)點(diǎn)的單跳可達(dá)鄰居數(shù)目。層次型拓?fù)淇刂评梅执貦C(jī)制，讓一些節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，由簇頭節(jié)點(diǎn)形成一個(gè)處理并轉(zhuǎn)發(fā)數(shù)據(jù)的骨干網(wǎng)，其他非骨干網(wǎng)節(jié)點(diǎn)可以暫時(shí)關(guān)閉通信模塊，進(jìn)入休眠轉(zhuǎn)臺(tái)以節(jié)省能量。本次設(shè)計(jì)主要研究的問題是：（1）影響整個(gè)網(wǎng)絡(luò)的生存時(shí)間的因素；（2）減小結(jié)點(diǎn)間通信干擾、提高網(wǎng)絡(luò)通信效率的方法；（3）如何彌補(bǔ)節(jié)點(diǎn)失效的影響。[3]1.4本文組織結(jié)構(gòu)本文分為6章，第1章主要介紹了課題研究的目的、意義和國(guó)內(nèi)外的發(fā)展?fàn)顩r；第2章是介紹無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)、特征、關(guān)鍵技術(shù)和應(yīng)用等相關(guān)概念；第3章介紹了無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂频幕靖拍睿⒂脙蓚€(gè)算法加以舉例；第4章對(duì)LEACH協(xié)議進(jìn)行詳細(xì)闡述，如算法的原理、特點(diǎn)、存在的問題以及改進(jìn)方法；第5章介紹在NS2平臺(tái)上對(duì)LEACH算法進(jìn)行仿真的步驟、過程以及對(duì)仿真過程中所得結(jié)果進(jìn)行分析；第6章對(duì)全文進(jìn)行總結(jié)。

第2章無線傳感器網(wǎng)絡(luò)概述2.1無線傳感器網(wǎng)絡(luò)基本概念2.1.1無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)傳感器網(wǎng)絡(luò)系統(tǒng)通常包括傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)。大量傳感器節(jié)點(diǎn)部署在檢測(cè)區(qū)域內(nèi)或者附近，能夠通過自組織方式構(gòu)成網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)檢測(cè)的數(shù)據(jù)沿著其他傳感器節(jié)點(diǎn)逐跳地進(jìn)行傳輸，在傳輸過程中檢測(cè)數(shù)據(jù)可能被多個(gè)節(jié)點(diǎn)處理，經(jīng)過多跳后路由到匯聚節(jié)點(diǎn)，最后通過互聯(lián)網(wǎng)或者衛(wèi)星到達(dá)管理節(jié)點(diǎn)。用戶通過管理節(jié)點(diǎn)對(duì)傳感器網(wǎng)絡(luò)進(jìn)行配置和管理，發(fā)布監(jiān)測(cè)任務(wù)以及收集監(jiān)測(cè)數(shù)據(jù)。大量的傳感器節(jié)點(diǎn)將探測(cè)數(shù)據(jù)，通過匯聚節(jié)點(diǎn)經(jīng)其它網(wǎng)絡(luò)發(fā)送給了用戶。在這個(gè)定義中，傳感器網(wǎng)絡(luò)實(shí)現(xiàn)了數(shù)據(jù)采集、處理和傳輸?shù)娜N功能，而這正對(duì)應(yīng)著現(xiàn)代信息技術(shù)的三大基礎(chǔ)技術(shù)，即傳感器技術(shù)、計(jì)算機(jī)技術(shù)和通信技術(shù)。如下圖所示：圖2-1無線傳感器網(wǎng)絡(luò)組織結(jié)構(gòu)圖2.1.2傳感器網(wǎng)絡(luò)的特征（1）大規(guī)模網(wǎng)絡(luò)；（2）自組織網(wǎng)絡(luò)；（3）動(dòng)態(tài)性網(wǎng)絡(luò)；（4）可靠的網(wǎng)絡(luò)；（5）應(yīng)用相關(guān)的網(wǎng)絡(luò)；（6）以數(shù)據(jù)為中心的網(wǎng)絡(luò)。[4]2.2無線傳感器網(wǎng)絡(luò)的應(yīng)用傳感器網(wǎng)絡(luò)的應(yīng)用前景非常廣闊，能夠廣泛應(yīng)用于軍事、環(huán)境監(jiān)測(cè)和預(yù)報(bào)、健康護(hù)理、智能家居、建筑物狀態(tài)監(jiān)測(cè)、復(fù)雜機(jī)械監(jiān)控、城市交通、空間探索、大型車間和倉(cāng)庫(kù)管理，以及機(jī)場(chǎng)、大型工業(yè)園區(qū)的安全監(jiān)測(cè)等領(lǐng)域。隨著傳感器網(wǎng)絡(luò)的深入研究和廣泛應(yīng)用，傳感器網(wǎng)絡(luò)將逐漸深入到人類生活的各個(gè)領(lǐng)域。（1）軍事應(yīng)用：傳感器網(wǎng)絡(luò)具有可快速部署、可自組織、隱蔽性強(qiáng)和高容錯(cuò)性的特點(diǎn)，因此非常適合在軍事上應(yīng)用。利用傳感器網(wǎng)絡(luò)能夠?qū)崿F(xiàn)對(duì)敵軍兵力和裝備的監(jiān)控、戰(zhàn)場(chǎng)的實(shí)時(shí)監(jiān)控、目標(biāo)的定位、戰(zhàn)場(chǎng)評(píng)估、核攻擊和生物化學(xué)攻擊的檢測(cè)和搜索等功能。（2）環(huán)境觀測(cè)和預(yù)報(bào)系統(tǒng)：隨著人們對(duì)于環(huán)境的日益關(guān)注，環(huán)境科學(xué)所涉及的范圍越來越廣泛。傳感器網(wǎng)絡(luò)在環(huán)境研究方面可用于監(jiān)視農(nóng)作物灌溉情況、土壤空氣情況、牲畜和家禽的環(huán)境狀況和大面積的地標(biāo)監(jiān)測(cè)等，可用于行星探測(cè)、氣象和地理研究、洪水泛濫等，還可以通過跟蹤鳥類、小型動(dòng)物和昆蟲進(jìn)行群復(fù)雜度的研究等。（3）醫(yī)療護(hù)理：傳感器網(wǎng)絡(luò)在醫(yī)療系統(tǒng)和健康護(hù)理方面的應(yīng)用包括監(jiān)測(cè)人體的各種生理數(shù)據(jù)，跟蹤和監(jiān)控醫(yī)院內(nèi)醫(yī)生和患者的行動(dòng)，醫(yī)院的藥物管理等。如果在住院病人身上安裝特殊用途的傳感器節(jié)點(diǎn)，如心率和血壓監(jiān)測(cè)設(shè)備，醫(yī)生利用傳感器網(wǎng)絡(luò)就可以隨時(shí)了解被監(jiān)護(hù)病人的病情，發(fā)現(xiàn)異常能夠迅速搶救。（4）智能家居：傳感器網(wǎng)絡(luò)能夠應(yīng)用在家居中。在家電和家具中嵌入傳感器節(jié)點(diǎn)，通過無線網(wǎng)絡(luò)與Internet連接在一起，將會(huì)為人們提供更加舒適、方便和更具人性化的智能家居環(huán)境。利用遠(yuǎn)程監(jiān)控系統(tǒng)，可完成對(duì)家電的遠(yuǎn)程控制，例如可以在回家之前半小時(shí)打開空調(diào)，這樣回家的時(shí)候就可以直接享受適合的室溫，也可以遙控電飯鍋、微波爐、電冰箱、電話機(jī)、電視機(jī)、錄像機(jī)、電腦等家電，按照自己的意愿完成相應(yīng)的煮飯、燒菜、查收電話留言、選擇錄制電視和電臺(tái)節(jié)目以及下載網(wǎng)上資料到電腦中等工作，也可以通過圖像傳感設(shè)備隨時(shí)監(jiān)控家庭安全情況[5]。2.3無線傳感器的關(guān)鍵技術(shù)（1）網(wǎng)絡(luò)拓?fù)淇刂疲簜鞲衅骶W(wǎng)絡(luò)拓?fù)淇刂颇壳爸饕难芯繂栴}是在滿足網(wǎng)絡(luò)覆蓋度和連通度的前提下，通過功率控制和骨干網(wǎng)節(jié)點(diǎn)選擇，刪除節(jié)點(diǎn)之間不必要的無線通信鏈路，生產(chǎn)一個(gè)高效的數(shù)據(jù)轉(zhuǎn)發(fā)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。拓?fù)淇刂瓶梢苑譃楣?jié)點(diǎn)功率控制和層次型拓?fù)浣Y(jié)構(gòu)形成兩個(gè)方面。功率控制方面目前已經(jīng)提出了COMPOW，LINT/LILT，CBTC，LMST，RNG，DRNG和DLSS等算法，層次型拓?fù)淇刂颇壳疤岢隽薚opDisc，GAF，LEACH和HEED等算法。（2）網(wǎng)絡(luò)協(xié)議：由于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的硬件資源有限和拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化，網(wǎng)絡(luò)協(xié)議不能太復(fù)雜但又要高效。目前研究的重點(diǎn)是網(wǎng)絡(luò)層協(xié)議和數(shù)據(jù)鏈路層協(xié)議。網(wǎng)絡(luò)層的路由協(xié)議決定檢測(cè)信息的傳輸路徑，目前提出了多種類型的協(xié)議，如多個(gè)能量感知的路由協(xié)議，定向擴(kuò)散和謠傳路由等基于查詢的路由協(xié)議，GEAR和GEM等基于地理位置的路由協(xié)議，SPEED和ReInForM等支持的QoS的路由協(xié)議。數(shù)據(jù)鏈路層的介質(zhì)訪問控制用來構(gòu)建底層的基礎(chǔ)結(jié)構(gòu)，控制傳感器節(jié)點(diǎn)的通信過程和工作模式。目前提出了S-MAC、T-MAC和Sift等基于競(jìng)爭(zhēng)的MAC協(xié)議，DEANA、TRAMA、DMAC和周期性調(diào)度等時(shí)分復(fù)用的MAC協(xié)議等。（3）時(shí)間同步：時(shí)間同步是需要協(xié)同工作的傳感器網(wǎng)絡(luò)系統(tǒng)的一個(gè)關(guān)鍵機(jī)制。JeremyElson和KayRomer在2002年8月的HotNets-I國(guó)際會(huì)議上首次提出并闡述了無線傳感器網(wǎng)絡(luò)中的時(shí)間同步機(jī)制的研究課題，在傳感器網(wǎng)絡(luò)研究領(lǐng)域引起了關(guān)注。目前已提出了多個(gè)時(shí)間同步機(jī)制，其中RBS、TINY/MINI-SYNC和TPSN被認(rèn)為是三個(gè)基本的同步機(jī)制。（4）定位技術(shù)：位置信息是傳感器節(jié)點(diǎn)采集數(shù)據(jù)中不可缺少的部分，沒有位置信息的檢測(cè)消息通常毫無意義。確定事件發(fā)生的位置或采集數(shù)據(jù)的節(jié)點(diǎn)位置是傳感器網(wǎng)絡(luò)最基本的功能之一。目前的定位技術(shù)有基于距離的定位，如基于TOA的定位、基于AOA的定位、基于RSSI的定位等；和與距離無關(guān)的定位算法，如質(zhì)心算法、DV-Hop算法、APIT算法等等[6]。

第3章無線傳感器網(wǎng)絡(luò)拓?fù)淇刂?.1拓?fù)淇刂聘攀鐾負(fù)淇刂萍夹g(shù)是無線傳感器網(wǎng)絡(luò)中最重要的技術(shù)之一。在由無線傳感器網(wǎng)絡(luò)生成的網(wǎng)絡(luò)拓?fù)渲?，可以直接通信的兩個(gè)結(jié)點(diǎn)之間存在一條拓?fù)溥?。如果沒有拓?fù)淇刂疲薪Y(jié)點(diǎn)都會(huì)以最大無線傳輸功率工作。在這種情況下，一方面，結(jié)點(diǎn)有限的能量將被通信部件快速消耗，降低了網(wǎng)絡(luò)的生命周期。同時(shí)，網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)的無線信號(hào)將覆蓋大量其他結(jié)點(diǎn)，造成無線信號(hào)沖突頻繁，影響結(jié)點(diǎn)的無線通信質(zhì)量，降低網(wǎng)絡(luò)的吞吐率。另一方面，在生成的網(wǎng)絡(luò)拓?fù)渲袑⒋嬖诖罅康倪?，從而?dǎo)致網(wǎng)絡(luò)拓?fù)湫畔⒘看螅酚捎?jì)算復(fù)雜，浪費(fèi)了寶貴的計(jì)算資源。因此，需要研究無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂茊栴}，在維持拓?fù)涞哪承┤中再|(zhì)的前提下，通過調(diào)整結(jié)點(diǎn)的發(fā)送功率來延長(zhǎng)網(wǎng)絡(luò)生命周期，提高網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)干擾，節(jié)約結(jié)點(diǎn)資源。（1）應(yīng)滿足的性質(zhì)：拓?fù)淇刂扑惴ǖ哪繕?biāo)是通過控制結(jié)點(diǎn)的傳輸范圍使生成的網(wǎng)絡(luò)拓?fù)錆M足一定的性質(zhì)，以延長(zhǎng)網(wǎng)絡(luò)生命周期，降低網(wǎng)絡(luò)干擾，提高吞吐率。拓?fù)淇刂扑惴ǖ哪繕?biāo)是通過控制結(jié)點(diǎn)的傳輸范圍使生成的網(wǎng)絡(luò)拓?fù)錆M足一定的性質(zhì)，以延長(zhǎng)網(wǎng)絡(luò)生命周期，降低網(wǎng)絡(luò)干擾，提高吞吐率。一般假設(shè)結(jié)點(diǎn)分布在二維平面上，所有結(jié)點(diǎn)都是同構(gòu)的，都使用無向天線。以有向圖建模無線傳感器網(wǎng)絡(luò)，如果結(jié)點(diǎn)i的傳輸功率Pi大于從結(jié)點(diǎn)i到結(jié)點(diǎn)j需要的傳輸功率Pij，則結(jié)點(diǎn)i到結(jié)點(diǎn)j之間有一條有向邊。所有結(jié)點(diǎn)都以最大功率工作時(shí)所生成的拓?fù)浞Q為UDG圖(UnitDiskGraph)。一般假設(shè)結(jié)點(diǎn)分布在二維平面上，所有結(jié)點(diǎn)都是同構(gòu)的，都使用無向天線。以有向圖建模無線傳感器網(wǎng)絡(luò)，如果結(jié)點(diǎn)i的傳輸功率Pi大于從結(jié)點(diǎn)i到結(jié)點(diǎn)j需要的傳輸功率Pij，則結(jié)點(diǎn)i到結(jié)點(diǎn)j之間有一條有向邊。所有結(jié)點(diǎn)都以最大功率工作時(shí)所生成的拓?fù)浞Q為UDG圖(UnitDiskGraph)。（2）研究方法：目前對(duì)拓?fù)淇刂频难芯靠梢苑譃閮纱箢悺Ｒ活愂怯?jì)算幾何方法，以某些幾何結(jié)構(gòu)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)的拓?fù)洌詽M足某些性質(zhì)。另一類是概率分析方法，在結(jié)點(diǎn)按照某種概率密度分布情況下，計(jì)算使拓?fù)湟源蟾怕蕽M足某些性質(zhì)時(shí)結(jié)點(diǎn)所需的最小傳輸功率和最小鄰居個(gè)數(shù)。計(jì)算幾何方法：該方法常使用的幾何結(jié)構(gòu)有如下幾種：=1\*GB3①最小生成樹(MST)網(wǎng)絡(luò)拓?fù)涫且越Y(jié)點(diǎn)間的歐式距離為度量的最小生成樹。結(jié)點(diǎn)的傳輸半徑設(shè)為與該結(jié)點(diǎn)相鄰的最長(zhǎng)邊的長(zhǎng)度。以MST為拓?fù)涞木W(wǎng)絡(luò)能保證網(wǎng)絡(luò)的連通性。由于在分布式環(huán)境下構(gòu)造MST開銷巨大，一種折中的方法是結(jié)點(diǎn)采用局部MST方法設(shè)置傳輸范圍。=2\*GB3②GG圖(GabrielGraph)在傳輸功率正比傳輸距離的平方時(shí)，GG圖是最節(jié)能的拓?fù)?。MST是GG圖的子圖，GG圖也滿足連通性。=3\*GB3③RNG圖(RelativeNeighborGraph)其稀疏程度在MST和GG圖之間，連通性也在MST和GG圖之間，優(yōu)于MST，沖突干擾優(yōu)于GG圖，是兩者的折中。RNG圖易于用分布式算法構(gòu)造。=4\*GB3④DT圖(DelaunayTriangulation)UDG與DT圖的交集稱為UDel圖(UnitDelaunayTriangulation)。UDel圖是稀疏的平面圖，適合于地理路由協(xié)議、節(jié)能、簡(jiǎn)化路由計(jì)算，以及降低干擾，因此十分適合作為無線底層拓?fù)鋄7]。3.2功率控制3.2.1概述無線自組織網(wǎng)絡(luò)中的功率控制問題是指分布式系統(tǒng)中的節(jié)點(diǎn)在無線通信過程中選擇最恰當(dāng)?shù)墓β始?jí)發(fā)送分組，以此達(dá)到優(yōu)化網(wǎng)絡(luò)應(yīng)用相關(guān)性能的目的。由于節(jié)點(diǎn)發(fā)射功率級(jí)的選擇對(duì)網(wǎng)絡(luò)多方面的性能均會(huì)產(chǎn)生影響，因此，網(wǎng)絡(luò)中的節(jié)點(diǎn)采用多大的功率級(jí)發(fā)送分組是一個(gè)非常復(fù)雜并具有挑戰(zhàn)性的課題。功率控制對(duì)無線自組織網(wǎng)絡(luò)的性能影響顯著，主要表現(xiàn)在以下5個(gè)方面：（1）功率控制對(duì)網(wǎng)絡(luò)能量有效性的影響；（2）功率控制對(duì)網(wǎng)絡(luò)連通性和拓?fù)浣Y(jié)構(gòu)的影響；（3）功率控制對(duì)網(wǎng)絡(luò)平均競(jìng)爭(zhēng)強(qiáng)度的影響；（4）功率控制對(duì)網(wǎng)絡(luò)容量的影響；（5）功率控制對(duì)網(wǎng)絡(luò)實(shí)時(shí)性的影響[8]。3.2.2基于節(jié)點(diǎn)度的算法一個(gè)節(jié)點(diǎn)的度數(shù)是指所有距離該節(jié)點(diǎn)一跳的鄰居節(jié)點(diǎn)的數(shù)目。基于節(jié)點(diǎn)度算法的核心思想是給定節(jié)點(diǎn)度的上限和下限需求，動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的發(fā)射功率，使得節(jié)點(diǎn)的度數(shù)落在上限和下限之間?；诠?jié)點(diǎn)度的算法利用局部信息來調(diào)整相鄰節(jié)點(diǎn)間的連通性，從而保證了整個(gè)網(wǎng)絡(luò)的連通性，同時(shí)保證節(jié)點(diǎn)間的鏈路具有一定的冗余性和可擴(kuò)展性。下面是兩種典型的基于節(jié)點(diǎn)度的算法。本地平均算法LMA(localmeanalgorithm)和本地鄰居平均算法LMN(localmeanofneighborsalgorithm)是兩種周期性動(dòng)態(tài)調(diào)整節(jié)點(diǎn)發(fā)射功率的算法。它們之間的區(qū)別在于計(jì)算節(jié)點(diǎn)度的策略不同。（1）本地平均算法本地平均算法LMA具體步驟如下：=1\*GB3①開始時(shí)所有節(jié)點(diǎn)都有相同的發(fā)射功率TransPower，每個(gè)節(jié)點(diǎn)定期廣播一個(gè)包含自己ID的LifeMsg消息。=2\*GB3②如果節(jié)點(diǎn)接收到LifeMsg消息，發(fā)送一個(gè)LifeAckMsg應(yīng)答消息。該消息中包含所應(yīng)答的LifeMsg消息中的結(jié)點(diǎn)ID。=3\*GB3③每個(gè)節(jié)點(diǎn)在下一次發(fā)送LifeMsg時(shí)，首先檢查已經(jīng)收到的LifeAckMsg消息，利用這些消息統(tǒng)計(jì)出自己的鄰居數(shù)NodeResp。=4\*GB3④如果NodeResp小于鄰居數(shù)下限NodeMinThresh，那么節(jié)點(diǎn)在這輪發(fā)送中將增大發(fā)射功率，但發(fā)射功率不能超過發(fā)射功率的Bmax倍，如式：TransPower=min{Bmax﹡TransPower，Ainc﹡(NodeMinThresh-NodeResp)﹡TransPower}同理，如果NodeResp大于鄰居節(jié)點(diǎn)數(shù)上限，那么節(jié)點(diǎn)將減小發(fā)射功率，用式子TransPower=max{Bmin﹡TransPower，Adec﹡(1-(NodeResp-NodeMaxThresh))﹡TransPower}表示，其中的Bmax、Bmin、Ainc和Adec是四個(gè)可調(diào)參數(shù)，它們會(huì)影響功率調(diào)節(jié)的精度和范圍。（2）本地鄰居平均算法本地鄰居平均算法LMN與本地平均算法LMA類似，唯一的區(qū)別是在鄰居數(shù)NodeResp的計(jì)算方法上。在LMN算法中，每個(gè)節(jié)點(diǎn)發(fā)送LifeAckMsg消息時(shí)，將自己的鄰居數(shù)放入消息中，發(fā)送LifeMsg消息的節(jié)點(diǎn)在收集完所有的LifeAckMsg消息后，將所有鄰居的鄰居數(shù)求平均值并作為自己的鄰居數(shù)。這兩種算法都缺少嚴(yán)格的理論推導(dǎo)。通過計(jì)算機(jī)仿真結(jié)果確定：這兩種算法的收斂性和網(wǎng)絡(luò)的連通性是可以保證的，它們通過少量的局部信息達(dá)到了一定程度的優(yōu)化效果。這兩種算法對(duì)無線傳感器節(jié)點(diǎn)的要求不高，不需要嚴(yán)格的時(shí)鐘同步。但算法還存在一些明顯不完善的地方，例如，需要進(jìn)一步研究合理的鄰居節(jié)點(diǎn)判斷條件，從鄰居節(jié)點(diǎn)得到的消息是否根據(jù)信號(hào)的強(qiáng)弱給予不同的權(quán)重等[9]。3.2.3基于鄰近圖的算法（1）鄰近圖圖可以用G=(V,E)的形式表示，其中V代表圖中頂點(diǎn)的集合，E代表圖中邊的集合。E中的元素可以表示為l=(u,v)，其中u,v∈V。所謂由一個(gè)圖G=(V,E)導(dǎo)出的鄰近圖G’=(V,E’)是指：對(duì)于任意一個(gè)節(jié)點(diǎn)v∈V，給定其鄰居的判定條件q，E中滿足q的邊(u,v)屬于E’。經(jīng)典的鄰近圖模型有RNG（relativeneighborhoodgraph）、GG(Gabrielgraph)、YG(yaograph)以及MST(minimumspanningtree)等。基于鄰近圖的功率控制算法是指：所有節(jié)點(diǎn)都使用最大功率發(fā)射時(shí)形成的拓?fù)鋱D為圖G，按照一定的規(guī)則q求出該圖的鄰近圖G’，最后G’中每個(gè)節(jié)點(diǎn)以自己所鄰接的最遠(yuǎn)通信節(jié)點(diǎn)來確定發(fā)射功率。這是一種解決功率分配問題的近似解法。考慮到傳感器網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)形成的邊是有向的，為了避免形成單向邊，一般在運(yùn)用基于鄰近圖的算法形成網(wǎng)絡(luò)拓?fù)渲螅€需要進(jìn)行節(jié)點(diǎn)之間邊的增刪，以使最后得到的網(wǎng)絡(luò)拓?fù)涫请p向連通的。在傳感器網(wǎng)絡(luò)中，基于鄰近圖的算法的作用是使節(jié)點(diǎn)確定自己的鄰居集合，調(diào)整適當(dāng)?shù)陌l(fā)射功率，從而在建立起一個(gè)連通的網(wǎng)絡(luò)同時(shí)，達(dá)到節(jié)省能力的目的。在已有的傳感器網(wǎng)絡(luò)拓?fù)渌惴ㄖ校卩徑鼒D的算法還不多，比較完善的有DRNG算法和DLSS算法。（2）DRNG算法和DLSS算法DRNG（directedrelativeneighborhoodgraph）算法和DLSS（directedlocalspanningsubgraph）算法是兩種以鄰近圖的觀點(diǎn)考慮拓?fù)鋯栴}的算法，它們是較早的針對(duì)節(jié)點(diǎn)發(fā)送功率不一致問題提出的拓?fù)浣鉀Q方案。這兩種算法以經(jīng)典鄰近圖RNG、LMST等理論為基礎(chǔ)，全面考慮了網(wǎng)絡(luò)的連通性和雙向連通性問題。在DRNG算法中，其確定了節(jié)點(diǎn)鄰居集合。其沒有給出算法的詳細(xì)步驟，但給出了確定的標(biāo)準(zhǔn)。假設(shè)u,v滿足d(u,v)<=r,r為節(jié)點(diǎn)u的通信距離，當(dāng)不存在另一節(jié)點(diǎn)p同時(shí)滿足w(u,p)<w(w,v),w(p,v)<w(u,v)和d(p,v)<=r時(shí)，節(jié)點(diǎn)v就被選為節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)。如下圖所示：圖3-1DRNG算法模型圖不論是在DRNG算法中還是在DLSS算法中，節(jié)點(diǎn)都需要知道一些必要信息，所以在拓?fù)湫纬芍坝幸粋€(gè)信息收集階段。在這個(gè)階段中，每個(gè)節(jié)點(diǎn)以自己的最大發(fā)射功率廣播HELLO消息，該消息中至少要包括自己的ID和自己所在的位置。這個(gè)階段完成后，每個(gè)節(jié)點(diǎn)通過接受到的HELLO消息確定自己可達(dá)的鄰居集合。DRNG和DLSS算法著重考慮網(wǎng)絡(luò)的連通性，充分利用鄰近圖的理論，考慮到傳感器網(wǎng)絡(luò)的特點(diǎn)，它們是同類算法中的典型算法，以原始網(wǎng)絡(luò)拓?fù)潆p向連通為前提，保證優(yōu)化后的拓?fù)湟彩请p向連通的。下圖是DRNG算法和DLSS算法優(yōu)化拓?fù)浣Y(jié)構(gòu)的例子，其中圖a是每個(gè)節(jié)點(diǎn)以最大功率發(fā)射形成的原始拓?fù)浣Y(jié)構(gòu)，圖b是經(jīng)過DRNG算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)，圖c是經(jīng)過DLSS算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)?？梢钥闯?，無論是DRNG算法還是DLSS算法，都使得網(wǎng)絡(luò)拓?fù)鋱D中邊的數(shù)量明顯減少，降低了節(jié)點(diǎn)的發(fā)射功率，同時(shí)減少了節(jié)點(diǎn)間的通信干擾。最大功率連通圖DRNG算法優(yōu)化圖DLSS算法優(yōu)化圖圖3-2三種算法網(wǎng)絡(luò)拓?fù)鋱D對(duì)比除了以上提到的兩種功率分配算法，還有一些貪心算法，如CONNECT算法和FPA/VPA算法等，但它們對(duì)網(wǎng)絡(luò)和節(jié)點(diǎn)要求相對(duì)苛刻，這里不再一一舉例。3.3層次型拓?fù)浣Y(jié)構(gòu)控制3.3.1LEACH算法為了提高整個(gè)網(wǎng)絡(luò)的的生存時(shí)間，將功耗均衡的分配到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，麻省理工學(xué)院的WendiRabinerHeinzelman等人提出了一種低功耗的自適應(yīng)路由協(xié)議——LEACH協(xié)議(Low-EnergyAdaptiveClusteriingHierarchy)。在LEACH協(xié)議中，每個(gè)傳感節(jié)點(diǎn)都有機(jī)會(huì)充當(dāng)簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)的選擇主要依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點(diǎn)個(gè)數(shù)與到目前為止每個(gè)節(jié)點(diǎn)已經(jīng)充當(dāng)簇頭節(jié)點(diǎn)的次數(shù)來判定的。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在0～1之間隨機(jī)選擇一個(gè)數(shù)，如果選擇的數(shù)小于規(guī)定閥值T(n)，則該節(jié)點(diǎn)就充當(dāng)簇首節(jié)點(diǎn)。T(n)的計(jì)算如下：（3-1）上式中，p表示在無線網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所占的百分比，r為當(dāng)前循環(huán)次數(shù)，G是在前1/p輪中未充當(dāng)過簇頭節(jié)點(diǎn)的集合。LEACH算法通過設(shè)置T(n)值，以保證每個(gè)節(jié)點(diǎn)在1/p輪內(nèi)都有機(jī)會(huì)充當(dāng)一次簇頭節(jié)點(diǎn)，從而平衡了節(jié)點(diǎn)的能量消耗。簇頭節(jié)點(diǎn)確定之后，簇頭節(jié)點(diǎn)通過廣播告知整個(gè)網(wǎng)絡(luò)自己已經(jīng)成為簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)在廣播過程中采用CSMAMAC協(xié)議來避免沖突。這時(shí)，網(wǎng)絡(luò)中的非簇頭節(jié)點(diǎn)可以根據(jù)接收到的信號(hào)強(qiáng)度來決定自己要從屬于哪個(gè)簇，選擇信號(hào)強(qiáng)度最強(qiáng)的源節(jié)點(diǎn)作為自己的簇頭節(jié)點(diǎn)，并告知相關(guān)的簇頭節(jié)點(diǎn)，自己則成為簇內(nèi)組員[10]。3.3.2GAF算法GAF（geographicaladaptivefidelity）算法是以節(jié)點(diǎn)地理位置為依據(jù)的分簇算法。該算法把監(jiān)測(cè)區(qū)域劃分成虛擬單元格，將節(jié)點(diǎn)按照位置信息劃入相應(yīng)的單元格；在每個(gè)單元格中定期選舉產(chǎn)生一個(gè)簇頭節(jié)點(diǎn)，只有簇頭節(jié)點(diǎn)保持活動(dòng)，其他節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。GAF是adhoc網(wǎng)絡(luò)中提出的一種路由算法，將其引入傳感器網(wǎng)絡(luò)，是因?yàn)樗奶摂M單元格思想為分簇機(jī)制提供了新思路。GAF算法的執(zhí)行過程包括兩個(gè)階段。第一階段是虛擬單元格的劃分。根據(jù)節(jié)點(diǎn)的位置信息和通信半徑，將網(wǎng)絡(luò)區(qū)域劃分成若干虛擬單元格，保證相鄰單元格中的任意兩個(gè)節(jié)點(diǎn)都能夠直接通信。假設(shè)節(jié)點(diǎn)已知整個(gè)檢測(cè)區(qū)域的位置信息和本身的位置信息，節(jié)點(diǎn)可以通過計(jì)算得知自己屬于哪個(gè)單元格。假設(shè)所有節(jié)點(diǎn)的通信半徑為R，網(wǎng)絡(luò)區(qū)域劃分為邊長(zhǎng)為r的正方形虛擬單元格，為了保證相鄰兩個(gè)單元格內(nèi)的任意兩個(gè)節(jié)點(diǎn)能夠直接通信，需要滿足如下關(guān)系式：（3-2）所以從分組轉(zhuǎn)發(fā)的角度來看，屬于同一單元格的節(jié)點(diǎn)可以認(rèn)為是等價(jià)的，每個(gè)單元格只需要選出一個(gè)節(jié)點(diǎn)保持活動(dòng)狀態(tài)。GAF算法的第二階段是虛擬單元格中簇頭節(jié)點(diǎn)的選擇。節(jié)點(diǎn)周期性地進(jìn)入睡眠和工作狀態(tài)，從睡眠狀態(tài)喚醒之后與本單元內(nèi)其他節(jié)點(diǎn)交換信息，以確定自己是否需要成為簇頭節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)可以處于發(fā)現(xiàn)、活動(dòng)以及睡眠三種狀態(tài)，如圖所示：圖3-3GAF算法狀態(tài)轉(zhuǎn)換圖

第4章LEACH算法協(xié)議4.1LEACH算法原理LEACH來源于WendiRabinerHeinzelman,AnanthaChandrakasan,和HariBalakrishnan三人在2000年P(guān)roceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences上的一篇文章Energy-EfficientCommunicationProtocolforWirelessMicrosensorNetworks。LEACH全稱是“低功耗自適應(yīng)集簇分層型協(xié)議”(LowEnergyAdaptiveClusteringHierarchy)。該算法基本思想是：以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而達(dá)到降低網(wǎng)絡(luò)能源消耗、提高網(wǎng)絡(luò)整體生存時(shí)間的目的。仿真表明，與一般的平面多跳路由協(xié)議和靜態(tài)分層算法相比，LEACH可以將網(wǎng)絡(luò)生命周期延長(zhǎng)15%。4.2LEACH算法的分析與實(shí)現(xiàn)LEACH在運(yùn)行過程中不斷的循環(huán)執(zhí)行簇的重構(gòu)過程，每個(gè)簇重構(gòu)過程可以用回合的概念來描述。每個(gè)回合可以分成兩個(gè)階段：簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段。為了節(jié)省資源開銷，穩(wěn)定階段的持續(xù)時(shí)間要大于建立階段的持續(xù)時(shí)間。簇的建立過程可分成4個(gè)階段：簇頭節(jié)點(diǎn)的選擇、簇頭節(jié)點(diǎn)的廣播、簇頭節(jié)點(diǎn)的建立和調(diào)度機(jī)制的生成。簇頭節(jié)點(diǎn)的選擇依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點(diǎn)總數(shù)和迄今為止每個(gè)節(jié)點(diǎn)已成為簇頭節(jié)點(diǎn)的次數(shù)來決定。具體的選擇辦法是：每個(gè)傳感器節(jié)點(diǎn)隨機(jī)選擇0-1之間的一個(gè)值。如果選定的值小于某一個(gè)閥值，那么這個(gè)節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)。選定簇頭節(jié)點(diǎn)后，通過廣播告知整個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)接收信息的信號(hào)強(qiáng)度決定從屬的簇，并通知相應(yīng)的簇頭節(jié)點(diǎn)，完成簇的建立。最后，簇頭節(jié)點(diǎn)采用TDMA方式為簇中每個(gè)節(jié)點(diǎn)分配向其傳遞數(shù)據(jù)的時(shí)間點(diǎn)。穩(wěn)定階段中，傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)對(duì)簇中所有節(jié)點(diǎn)所采集的數(shù)據(jù)進(jìn)行信息融合后再傳送給匯聚節(jié)點(diǎn)，這是一種叫少通信業(yè)務(wù)量的合理工作模型。穩(wěn)定階段持續(xù)一段時(shí)間后，網(wǎng)絡(luò)重新進(jìn)入簇的建立階段，進(jìn)行下一回合的簇重構(gòu)，不斷循環(huán)，每個(gè)簇采用不同的CDMA代碼進(jìn)行通信來減少其他簇內(nèi)節(jié)點(diǎn)的干擾。其中閥值，T(n)按照下列公式計(jì)算：（4-1）式中：P為節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的百分?jǐn)?shù)，r為當(dāng)前輪數(shù)，G為在最近的1/p輪中未當(dāng)選簇頭的節(jié)點(diǎn)集合。簇頭節(jié)點(diǎn)選定后，廣播自己成為簇頭的消息，節(jié)點(diǎn)根據(jù)接收到的消息的強(qiáng)度決定加入哪個(gè)簇，并告知相應(yīng)的簇頭，完成簇的建立過程。然后，簇頭節(jié)點(diǎn)采用TDMA的方式，為簇內(nèi)成員分配傳送數(shù)據(jù)的時(shí)隙。在穩(wěn)定階段，傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)對(duì)采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后再將信息傳送給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)將數(shù)據(jù)傳送給監(jiān)控中心來進(jìn)行數(shù)據(jù)的處理。穩(wěn)定階段持續(xù)一段時(shí)間后，網(wǎng)絡(luò)重新進(jìn)入簇的建立階段，進(jìn)行下一輪的簇重建，不斷循環(huán)。4.3LEACH算法的特點(diǎn)（1）為了減少傳送到匯聚節(jié)點(diǎn)的信息數(shù)量，簇首節(jié)點(diǎn)負(fù)責(zé)融合來自蔟內(nèi)不同源節(jié)點(diǎn)所產(chǎn)生的數(shù)據(jù)，并將融合后的數(shù)據(jù)發(fā)送到匯聚點(diǎn)。（2）LEACH采用基于TDMA/CDMA的MAC層機(jī)制來減少蔟內(nèi)和蔟間的沖突。（3）由于數(shù)據(jù)采集是集中的和周期性的，因此該協(xié)議非常適合于要求連續(xù)監(jiān)控的應(yīng)用系統(tǒng)。（4）對(duì)于終端使用者來說，由于它并不需要立即得到所有的數(shù)據(jù)，因此協(xié)議不需要周期性的傳輸數(shù)據(jù)，這樣可以達(dá)到限制傳感器節(jié)點(diǎn)能量消耗的目的。（5）在給定的時(shí)間間隔后，協(xié)議重新選舉簇首節(jié)點(diǎn)，以保證無線傳感器網(wǎng)絡(luò)獲取同意的能量分布[11]。4.4算法中存在的問題分析及改進(jìn)4.4.1算法中的問題（1）剛開始假設(shè)每個(gè)節(jié)點(diǎn)能量相同，在現(xiàn)實(shí)環(huán)境中很難做到；（2）每個(gè)節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率相同，這樣可能導(dǎo)致一些高能量節(jié)點(diǎn)沒機(jī)會(huì)成為簇首節(jié)點(diǎn)，而一些低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。一旦這些低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)，將會(huì)很快耗盡其能量；（3）LEACH協(xié)議不能保證簇頭在每個(gè)區(qū)域都分布均勻，雖然統(tǒng)計(jì)上面是均勻的，但是由于簇頭產(chǎn)生帶有極大的隨機(jī)性，有些區(qū)域可能簇頭數(shù)會(huì)較多；（4）簇首節(jié)點(diǎn)在通信過程中采用單跳與基站通信，這樣就會(huì)導(dǎo)致較遠(yuǎn)的簇首節(jié)點(diǎn)能量消耗過大，而過早死亡，影響整個(gè)網(wǎng)絡(luò)的性能；（5）整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)在兩跳范圍內(nèi)，這樣不符合大規(guī)模網(wǎng)絡(luò)需求[12]。4.4.2LEACH算法的改進(jìn)（1）根據(jù)節(jié)點(diǎn)初始能量不同改進(jìn)：根據(jù)整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)能量的初始不同，GeorgiosSmaragdakis等人提出了一種改進(jìn)行分簇算法——SEP算法(aStableElectionProto-colforclusteredheterogeneous)，先把整個(gè)網(wǎng)絡(luò)分成兩類節(jié)點(diǎn)，能量較高的節(jié)點(diǎn)稱為高能量節(jié)點(diǎn)，能量低的稱為正常節(jié)點(diǎn)?？梢钥闯?，高能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的機(jī)會(huì)大于低能量節(jié)點(diǎn)。相對(duì)于LEACH算法，充分利用了整個(gè)網(wǎng)絡(luò)的功耗。為整個(gè)網(wǎng)絡(luò)簇首節(jié)點(diǎn)的概率，Pnrm為正常節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率，Padv為高能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率。r為當(dāng)前循環(huán)次數(shù)，G1是在前1/p輪中正常節(jié)點(diǎn)未充當(dāng)過簇頭節(jié)點(diǎn)的集合。G2是在前1/p輪中高能量節(jié)點(diǎn)未充當(dāng)過簇頭節(jié)點(diǎn)的集合。m為網(wǎng)絡(luò)中高能量節(jié)點(diǎn)的比例。a為高能量節(jié)點(diǎn)高于正常節(jié)點(diǎn)能量部分。在參考文獻(xiàn)中，作者對(duì)SEp算法進(jìn)行再次改進(jìn)，利用整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的平均能量與節(jié)點(diǎn)當(dāng)前能量的比值來限制節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率，兩類節(jié)點(diǎn)成為簇首節(jié)點(diǎn)概率如下式所示。（4-2）可以看出進(jìn)一步限制的低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率[13]。（2）根據(jù)節(jié)點(diǎn)剩余能量的不同而改進(jìn)：M.J.Handy等人提出了DCHS(DeterministicClus-ter-HeadSelection)算法，根據(jù)LEACH算法中的T(n)計(jì)算不足之處，對(duì)其進(jìn)行改進(jìn)，如下式所示。（4-3）式中En_current表示節(jié)點(diǎn)當(dāng)前的能量，En_max表示節(jié)點(diǎn)初始的能量。由改進(jìn)后的算法可以看出，當(dāng)前節(jié)點(diǎn)能量比較高的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率變大，從而降低了低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率，提高了整個(gè)網(wǎng)絡(luò)的性能。然而根據(jù)上式可以看出，當(dāng)整個(gè)網(wǎng)絡(luò)運(yùn)行到一定的時(shí)間后，大部分節(jié)點(diǎn)的能量都將剩余不多，相應(yīng)的T(n)就會(huì)變小，那么整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)成為簇首的概率變小，從而影響到整個(gè)網(wǎng)絡(luò)的性能。M.J.Handy等人對(duì)上式進(jìn)一步改進(jìn)，得到下式，從而有效解決了上式的不足之處：（4-4）在上式中rs表示節(jié)點(diǎn)連續(xù)未當(dāng)選過簇頭的輪次。一旦節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)，則rs置零。（3）根據(jù)簇首節(jié)點(diǎn)隨機(jī)分布不均而改進(jìn)：LEACH-C算法是LEACH算法的集中式控制版本，采用模擬退火算法獲得更優(yōu)的簇頭選舉策略，克服了LEACH算法中每輪產(chǎn)生的簇頭數(shù)與位置的隨機(jī)性。LEACH-C算法可以把每個(gè)節(jié)點(diǎn)的地理位置以及節(jié)點(diǎn)當(dāng)前的能量報(bào)告給基站?；景阉泄?jié)點(diǎn)的能量取平均，當(dāng)網(wǎng)絡(luò)中某些節(jié)點(diǎn)的能量低于平均值時(shí)，將不能成為候選簇頭節(jié)點(diǎn)，從而更加有效地解決了低能量節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的概率。（4）根據(jù)LEACH實(shí)時(shí)性不強(qiáng)而改進(jìn)：根據(jù)LEACH算法實(shí)時(shí)性不強(qiáng)的問題，ManjeshwarA等人提出了TEEN算法，TEEN算法與LEACH算法較大的不同點(diǎn)是，在簇首節(jié)點(diǎn)的選舉過程中，協(xié)議設(shè)置了兩個(gè)閾值，分別為硬閾值、軟閾值兩個(gè)參數(shù)。硬閾值是被檢測(cè)數(shù)據(jù)不能超過的數(shù)值，而且軟閾值決定了被測(cè)數(shù)據(jù)的波動(dòng)范圍。只有當(dāng)被監(jiān)測(cè)數(shù)據(jù)超過硬閾值且被監(jiān)測(cè)數(shù)據(jù)的變化幅度大于軟閾值時(shí)，節(jié)點(diǎn)才會(huì)傳送最新的監(jiān)測(cè)數(shù)據(jù)，并設(shè)置為新的硬閾值。相對(duì)于LEACH算法，TEEN算法能夠較大地減少節(jié)點(diǎn)之間數(shù)據(jù)傳送的次數(shù)，從而有效減少了整個(gè)網(wǎng)絡(luò)的功耗，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。APTEEN算法則結(jié)合了LEACH與TEEN兩種算法，是一種主動(dòng)型與響應(yīng)型混合的數(shù)據(jù)傳輸模式。但網(wǎng)絡(luò)中有突發(fā)事件時(shí)，數(shù)據(jù)傳輸模式將會(huì)采用與TEEN相同的模式(響應(yīng)型模式)，只不過AFTEEN算法多了一個(gè)計(jì)數(shù)器，節(jié)點(diǎn)每傳送一次數(shù)據(jù)，對(duì)應(yīng)的計(jì)數(shù)器將清零。當(dāng)計(jì)數(shù)器的時(shí)間到達(dá)的時(shí)候，將采取主動(dòng)發(fā)送這個(gè)數(shù)據(jù)，不再判斷軟、硬門限值[14]。（5）根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布密度不均而改進(jìn)：在LEACH算法中并未考慮節(jié)點(diǎn)分布密度對(duì)網(wǎng)絡(luò)的影響，在分布密度大的區(qū)域，相對(duì)簇首節(jié)點(diǎn)的負(fù)擔(dān)也較重，能量也容易耗盡，因此應(yīng)該增加該區(qū)域簇首節(jié)點(diǎn)的個(gè)數(shù)。參考文獻(xiàn)中根據(jù)無線網(wǎng)絡(luò)中周圍節(jié)點(diǎn)存活個(gè)數(shù)不同，來改變?cè)搮^(qū)域內(nèi)節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率。為了在節(jié)點(diǎn)密集區(qū)域增加簇頭的個(gè)數(shù)，只需要增大對(duì)應(yīng)節(jié)點(diǎn)成為簇頭的概率，對(duì)于節(jié)點(diǎn)稀疏區(qū)域則降低其中節(jié)點(diǎn)成為簇頭的概率即可。因此將簇頭選舉的閾值修改為：（4-5）上式中Neighbor(n)_alive與Network_alive分別表示表示節(jié)點(diǎn)n鄰居集中以及整個(gè)網(wǎng)絡(luò)中存活節(jié)點(diǎn)的數(shù)目，1/p表示平均每簇中節(jié)點(diǎn)的個(gè)數(shù)，從上式可以看出當(dāng)節(jié)點(diǎn)周圍存活個(gè)數(shù)大于平均值時(shí)，該區(qū)域節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率將增大，反之則降低。（6）根據(jù)大規(guī)模多跳網(wǎng)絡(luò)而改進(jìn)：根據(jù)LEACH算法跳距的局限性，在LEACH算法中，整個(gè)網(wǎng)絡(luò)最大跳距為兩跳，這樣就會(huì)導(dǎo)致遠(yuǎn)離基站的簇首節(jié)點(diǎn)，能量消耗太大而過早死亡，影響到整個(gè)網(wǎng)絡(luò)的性能，SivaD.Muruganathan等人提出了BCDCP多跳分簇算法，簇首節(jié)點(diǎn)的選擇由基站來控制，基站首先將每個(gè)節(jié)點(diǎn)的當(dāng)前能量取平均，只有大于平均值的節(jié)點(diǎn)才有機(jī)會(huì)成為簇首節(jié)點(diǎn)，這樣就避開了低能量節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的可能。當(dāng)簇首節(jié)點(diǎn)與基站的距離超過一定時(shí)，不直接與基站通信，而是借助其他簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)到基站，選擇其他簇首節(jié)點(diǎn)是采用的是最小生成樹算法，這樣就減輕了遠(yuǎn)離基站簇首節(jié)點(diǎn)的負(fù)擔(dān)，也擴(kuò)展了整個(gè)網(wǎng)絡(luò)的規(guī)模。

第5章LEACH算法仿真5.1NS2仿真軟件5.1.1NS2仿真軟件概述NS2是指NetworkSimulatorversion2，NS（NetworkSimulator）是一種針對(duì)網(wǎng)絡(luò)技術(shù)的、源代碼公開的、免費(fèi)的軟件模擬平臺(tái)，研究人員使用它可以很容易的進(jìn)行網(wǎng)絡(luò)技術(shù)的開發(fā)，而且發(fā)展到今天，它所包含的模塊幾乎涉及到了網(wǎng)絡(luò)技術(shù)的所有方面。所以，NS成了目前學(xué)術(shù)界廣泛使用的一種網(wǎng)絡(luò)模擬軟件。此外，NS也可作為一種輔助教學(xué)的工具，已被廣泛應(yīng)用在了網(wǎng)絡(luò)技術(shù)的教學(xué)方面。因此，目前在學(xué)術(shù)界和教育界，有大量的人正在使用或試圖使用NS。然而，對(duì)初學(xué)者來說，NS是非常難于掌握的，一般人從學(xué)習(xí)NS到上手至少需要半年多時(shí)間。原因是多方面的：一方面，NS內(nèi)容龐雜，隨軟件所提供的手冊(cè)更新不夠快，初學(xué)者閱讀起來非常困難；另一方面，使用NS還要掌握其它很多必備的相關(guān)知識(shí)以及相關(guān)工具，這會(huì)使初學(xué)者感到無從入手；有的使用者可能還不了解網(wǎng)絡(luò)模擬的過程或是對(duì)NS軟件的機(jī)制缺乏理解，這也影響了對(duì)NS的掌握。另外，不論在國(guó)外還是國(guó)內(nèi)，還沒有一本書能集中回答和解決這些問題，這也是NS難于被掌握的一個(gè)重要原因。NS2使用C++和Otcl作為開發(fā)語言。NS可以說是Otcl的腳本解釋器，它包含仿真事件調(diào)度器、網(wǎng)絡(luò)組件對(duì)象庫(kù)以及網(wǎng)絡(luò)構(gòu)建模型庫(kù)等。事件調(diào)度器計(jì)算仿真時(shí)間，并且激活事件隊(duì)列中的當(dāng)前事件，執(zhí)行一些相關(guān)的事件，網(wǎng)絡(luò)組件通過傳遞分組來相互通信，但這并不耗費(fèi)仿真時(shí)間。所有需要花費(fèi)仿真時(shí)間來處理分組的網(wǎng)絡(luò)組件都必須要使用事件調(diào)度器。它先為這個(gè)分組發(fā)出一個(gè)事件，然后等待這個(gè)事件被調(diào)度回來之后，才能做下一步的處理工作。事件調(diào)度器的另一個(gè)用處就是計(jì)時(shí)。NS是用Otcl和C++編寫的。由于效率的原因，NS將數(shù)據(jù)通道和控制通道的實(shí)現(xiàn)相分離。為了減少分組和事件的處理時(shí)間，事件調(diào)度器和數(shù)據(jù)通道上的基本網(wǎng)絡(luò)組件對(duì)象都使用C++寫出并編譯的，這些對(duì)象通過映射對(duì)Otcl解釋器可見。當(dāng)仿真完成以后，NS將會(huì)產(chǎn)生一個(gè)或多個(gè)基于文本的跟蹤文件。只要在Tcl腳本中加入一些簡(jiǎn)單的語句，這些文件中就會(huì)包含詳細(xì)的跟蹤信息。這些數(shù)據(jù)可以用于下一步的分析處理，也可以使用NAM將整個(gè)仿真過程展示出來。從用戶的角度來看，兩種結(jié)構(gòu)的類之間有一一對(duì)應(yīng)的。用戶通過解釋器創(chuàng)立新的仿真對(duì)象之后，解釋器對(duì)它進(jìn)行初始化，與編譯類結(jié)構(gòu)中相應(yīng)的對(duì)象建立映射[15]。圖5-1NS2軟件組成5.1.2NS2擴(kuò)展功能NS是一個(gè)面向?qū)ο蟮哪M器，用C++編寫，且前端使用OTCL解釋器。存在有兩個(gè)類框架：(1)C++類框架：文檔中稱為編譯的類編譯框架；(2)OTcl類框架：文檔中稱為解釋的類框架。兩個(gè)類彼此緊密相關(guān)。從用戶的觀點(diǎn)，在兩類中是一一對(duì)應(yīng)的關(guān)系。在解釋類中的基本父類是TclObject，用戶通過解釋器來建立一個(gè)模擬對(duì)象；對(duì)象在解釋器中創(chuàng)建并映射到編譯類中去。通過在TclClass中定義的方法建立了解釋類的框架，在類TclObject中定義的方法來映射用戶的使用對(duì)象。圖5-2 NS2組建結(jié)構(gòu)圖5.1.3NS2軟件構(gòu)成TclObject在類層次結(jié)構(gòu)中處于最高層，所有其他主要的類都從它派生而來。它有一個(gè)靜態(tài)鏈表記錄了用戶創(chuàng)建的所有對(duì)象，每一個(gè)對(duì)象都有一個(gè)唯一的標(biāo)識(shí)，記錄了每個(gè)對(duì)象所屬的類名。使用這種公共基類的好處是各種對(duì)象可以存儲(chǔ)在同一個(gè)鏈表中。使用對(duì)象的函數(shù)知道如何處理對(duì)象和簡(jiǎn)單地進(jìn)行強(qiáng)制類型轉(zhuǎn)換以滿足自己的需要。（1）調(diào)度器(Scheduler)調(diào)度器是仿真器的心臟，它記錄當(dāng)前時(shí)間，調(diào)度網(wǎng)絡(luò)事件鏈表中的事件。它有一個(gè)靜態(tài)成員變量instance_，供所有的類訪問同一個(gè)調(diào)度器。提供函數(shù)產(chǎn)生新事件，指定事件發(fā)生的時(shí)間。（2）事件和TCP分組(Event&TCPPacket)事件表示仿真器產(chǎn)生的實(shí)際事件，包括事件產(chǎn)生的時(shí)間，處理事件的事件處理器。派生了兩個(gè)類:Packet和AtHandler。使用這種方法的好處是無論哪個(gè)處理器要處理事件，都可以把事件的類型轉(zhuǎn)換成它所需要的，然后相應(yīng)地處理。（3）事件處理器(Handler)Handler是所有處理事件類的基類，它只是一個(gè)虛擬函數(shù)，每個(gè)繼承類實(shí)現(xiàn)自己的功能。（4）匹配器類(Matcher)匹配器類用來標(biāo)識(shí)有實(shí)例對(duì)象生成的類，用戶給出標(biāo)識(shí)匹配類的關(guān)鍵字，匹配類返回相應(yīng)的新建對(duì)象。匹配器類被定義成靜態(tài)的，只允許一個(gè)實(shí)例對(duì)象。（5）變量(Var)用來存放系統(tǒng)變量和缺省變量。每當(dāng)新建對(duì)象后，通過搜索適當(dāng)?shù)淖兞亢皖惷梢缘玫絽?shù)的缺省值。（6）NS對(duì)象(NsObject)Nsobject是所有網(wǎng)絡(luò)實(shí)體的基類，包括節(jié)點(diǎn)、鏈路、代理，業(yè)務(wù)記錄(Trace)和數(shù)據(jù)源等。節(jié)點(diǎn)、鏈路、代理同時(shí)繼承了NsObject和事件處理器類，因?yàn)檫@三種對(duì)象要處理多種事件，其他對(duì)象則不需要。（7）節(jié)點(diǎn)(Node)節(jié)點(diǎn)類表示網(wǎng)絡(luò)中實(shí)際的節(jié)點(diǎn)和路由器。它有一個(gè)靜態(tài)變量cnt_用來記錄當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)。多個(gè)業(yè)務(wù)源可以連接到一個(gè)節(jié)點(diǎn)的不同端口，但一個(gè)節(jié)點(diǎn)的端口數(shù)是有限制的。節(jié)點(diǎn)有一個(gè)路由表，路由算法，基于目的地址轉(zhuǎn)發(fā)數(shù)據(jù)包，節(jié)點(diǎn)本身并不產(chǎn)生分組，而是由代理來產(chǎn)生和消費(fèi)分組。（8）代理(Agent)代理是實(shí)際產(chǎn)生和消費(fèi)分組的對(duì)象，它們屬于傳輸層實(shí)體，運(yùn)行在端主機(jī)(模擬)，節(jié)點(diǎn)的每一個(gè)代理自動(dòng)被賦與一個(gè)唯一的端口號(hào)(模擬tcp/udp端口)，代理知道與它相連的節(jié)點(diǎn)，以便把分組轉(zhuǎn)發(fā)給節(jié)點(diǎn)，它也知道分組大小，業(yè)務(wù)類型，目的地址。Agent類是各種TCP實(shí)現(xiàn)類的基類，如Reno，Newreno，sack1及TCP吸收端(sinks)，如elACKSink，SACK1TCPSink，SACK1DelACKTcpSink。代理被保存在一個(gè)稱為demux_的鏈表中。（9）鏈路(Link)鏈路用來連接節(jié)點(diǎn)和路由器。一個(gè)節(jié)點(diǎn)可以有一條或多條輸出鏈路(如路由器)。所有的鏈路都以隊(duì)列的形式來管理分組到達(dá)、離開或丟棄，統(tǒng)計(jì)并保存字節(jié)數(shù)和分組數(shù)。另外還有一個(gè)獨(dú)立的對(duì)象來記錄(Tracing)隊(duì)列日志。5.1.4使用方法使用NS進(jìn)行網(wǎng)絡(luò)仿真的方法和一般過程。進(jìn)行網(wǎng)絡(luò)仿真前，首先分析仿真涉及哪個(gè)層次，NS仿真分兩個(gè)層次：一個(gè)是基于OTcl編程的層次。利用NS已有的網(wǎng)絡(luò)元素實(shí)現(xiàn)仿真，無需修改NS本身，只需編寫OTcl腳本。另一個(gè)是基于C++和OTcl編程的層次。如果NS中沒有所需的網(wǎng)絡(luò)元素，則需要對(duì)NS進(jìn)行擴(kuò)展，添加所需網(wǎng)絡(luò)元素，即添加新的C++和OTcl類，編寫新的OTcl腳本。假設(shè)用戶已經(jīng)完成了對(duì)NS的擴(kuò)展，或者NS所包含的構(gòu)件已經(jīng)滿足了要求，那么進(jìn)行一次仿真的步驟大致如下：（1）開始編寫OTcl腳本。首先配置模擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，此時(shí)可以確定鏈路的基本特性，如延遲、帶寬和丟失策略等；（2）建立協(xié)議代理，包括端設(shè)備的協(xié)議綁定和通信業(yè)務(wù)量模型的建立；（3）配置業(yè)務(wù)量模型的參數(shù)，從而確定網(wǎng)絡(luò)上的業(yè)務(wù)量分布；（4）設(shè)置Trace對(duì)象。NS通過Trace文件來保存整個(gè)模擬過程。仿真完后，用戶可以對(duì)Trace文件進(jìn)行分析研究；（5）編寫其他的輔助過程，設(shè)定模擬結(jié)束時(shí)間，至此OTcl腳本編寫完成；（6）用NS解釋執(zhí)行剛才編寫的OTcl腳本；（7）對(duì)Trace文件進(jìn)行分析，得出有用的數(shù)據(jù)；（8）調(diào)整配置拓?fù)浣Y(jié)構(gòu)和業(yè)務(wù)量模型，重新進(jìn)行上述模擬過程；NS2采用兩級(jí)體系結(jié)構(gòu)，為了提高代碼的執(zhí)行效率，NS2將數(shù)據(jù)操作與控制部分的實(shí)現(xiàn)相分離，事件調(diào)度器和大部分基本的網(wǎng)絡(luò)組件對(duì)象后臺(tái)使用C++實(shí)現(xiàn)和編譯，稱為編譯層，主要功能是實(shí)現(xiàn)對(duì)數(shù)據(jù)包的處理；NS2的前端是一個(gè)OTcl解釋器，稱為解釋層，主要功能是對(duì)模擬環(huán)境的配置、建立。從用戶角度看，NS2是一個(gè)具有仿真事件驅(qū)動(dòng)、網(wǎng)絡(luò)構(gòu)件對(duì)象庫(kù)和網(wǎng)絡(luò)配置模塊庫(kù)的OTcl腳本解釋器。NS2中編譯類對(duì)象通過OTcl連接建立了與之對(duì)應(yīng)的解釋類對(duì)象，這樣用戶間能夠方便地對(duì)C++對(duì)象的函數(shù)進(jìn)行修改與配置，充分體現(xiàn)了仿真器的一致性和靈活性。5.2LEACH算法仿真5.2.1LEACH算法實(shí)現(xiàn)=1\*GB3①安裝cygwin圖5-3NS2安裝歡迎界面在RootDirectory中，可以選擇安裝的目錄，不過在這里建議大家使用內(nèi)定的路徑c:\cygwin。其它另外兩個(gè)選項(xiàng)也使用內(nèi)定值即可。按“下一步”。圖5-4NS2安裝路徑選擇界面按“下一步”。圖5-5NS2插件安裝選擇界面選擇要安裝的軟件套件。在這邊可以先點(diǎn)選View，使得旁邊的Category變成Full，這樣就可以對(duì)于細(xì)部的選項(xiàng)做選擇。圖5-6NS2插件安裝選擇要選擇的有XFree86-base、XFree86-bin、XFree86-prog、XFree86-lib、XFree86-etc、make、patch、perl、gcc、gcc-g++、gawk、gnuplot、tar和gzip。圖5-7插件安裝效果圖按“下一步”。開始下載并安裝。圖5-8安裝完成界面完成后，會(huì)詢問使用者是否想要產(chǎn)生小圖示于桌面和開始選單。按完成以結(jié)束安裝程序。若是還有需要安裝其它的軟件套件需要安裝，可以重新執(zhí)行setup安裝即可。=2\*GB3②安裝ns2點(diǎn)選桌面上的cygwin小圖示。圖5-9生成家目錄第一次執(zhí)行的時(shí)候，會(huì)根據(jù)目前計(jì)算機(jī)的使用者和計(jì)算機(jī)的名稱等信息，在cygwin的home的目錄下產(chǎn)一個(gè)使用者的數(shù)據(jù)夾，并放入環(huán)境變量設(shè)定等相關(guān)檔案(.bashrc、.bashrc_profile和.inputrc)。使用tarxvfzns-allinone-2.29.tar.gz解開所下載的壓縮檔。進(jìn)入ns-allinone-2.29的目錄，并開始安裝ns2。圖5-10開始安裝在安裝的過程中，由于我們沒有安裝diff，所以安裝程序會(huì)問使用者要不要繼續(xù)，選擇y繼續(xù)安裝。圖5-11安裝過程界面在安裝的過程中，需要花一些時(shí)間，所以請(qǐng)使用者耐心的等待安裝完成。圖5-12安裝成功完成ns2的編譯后，要開始設(shè)定環(huán)境變量。請(qǐng)編輯家目錄下的.bashrc，把ns2相關(guān)的路徑加入PATH中。exportNS_HOME=`pwd`/ns-allinone-2.29exportPATH=$NS_HOME/tcl8.4.5/unix:$NS_HOME/tk8.4.5/unix:$NS_HOME/bin:$PATHexportLD_LIBRARY_PATH=$NS_HOME/tcl8.4.5/unix:$NS_HOME/tk8.4.5/unix:$NS_HOME/otcl-1.8:$NS_HOME/lib:$LD_LIBRARY_PATHexportTCL_LIBRARY=$NS_HOME/tcl8.4.5/library=3\*GB3③配置LEACH協(xié)議首先我們先找個(gè)目錄把mit.tar.gz文件解壓開來，使的gunzipmit.tar.gz和tar–xvfmit.tar解壓，但是不直接解壓到目錄/ns-allinone-2.29/ns-2.29下。將解壓出來的文件A一一的對(duì)應(yīng)我們/ns-allinone-2.29/ns-2.29目錄下的文件B進(jìn)行修改，將A中與B內(nèi)容不同的地方，添加進(jìn)B去，切記，不是完全復(fù)制，是添加進(jìn)去，而B中多出來的內(nèi)容，也許是你以前添加進(jìn)去的協(xié)議，不要?jiǎng)h掉。注意一點(diǎn)，添加的過程中，聲明變量的地方，有時(shí)會(huì)是兩種聲明方式，其中一種被注釋掉了，這時(shí)，如果需要更改聲明另一種方式時(shí)，一定要把第一種注釋掉，避免重復(fù)聲明的錯(cuò)誤產(chǎn)生。強(qiáng)調(diào)一點(diǎn)，mac/channel.cc文件中：distCST_=TwoRayGetDist(wifp->getCSThresh(),wifp->getPt(),1.0,1.0,highestZ,highestZ);改成distCST_=wifp->getDist(wifp->getCSThresh(),wifp->getPt(),1.0,1.0,highestZ,highestZ,wifp->getL(),wifp->getLambda());(注：2.29里面的channel.cc不用修改)。mac/wireless-phy.cc文件中的（node*）改成（MobileNode*）(注：2.29里面的channel.cc不用修改)。修改MakeFile文件，按照下面三步來進(jìn)行：（1）將DMIT_uAMPS添加到DEFINE行的最后，即為DEFINE =-DTCP_DELAY_BIND_ALL……-Drng_test-DMIT_uAMPS（2）將I./mit/rcaI./mit/uAMPS添加到INCLUDE列的后面，即為：INCLUDES=\ …… -I./diffusion3/lib/main-I./diffusion3/lib\ -I./diffusion3/lib/nr-I./diffusion3/ns\ -I./diffusion3/filter_core-I./asim/-I./qs\ -I./mit/rca-I./mit/uAMPS\……將代碼mit/rca/energy.omit/rca/rcagent.o\mit/rca/rca-ll.omit/rca/resource.o\mac/mac-sensor-timers.omac/mac-sensor.omit/uAMPS/bsagent.o\添加到代碼gaf/gaf.o\之前將MakeFile文件中的mit/mit.omit/mit注銷掉。這樣，文件我們就都修改完了，下面就是編譯了，即需要make了。進(jìn)入到/ns-allinone-2.29/ns-2.29目錄下，輸入makeclean。如果沒有出錯(cuò)，輸入make，這時(shí)就需要很長(zhǎng)時(shí)間的等待了。如果你改的文件是makefile.in，那么應(yīng)該有提示說你的makefile.in文件比make文件新，需要重新configure，這時(shí)輸入./configure即可。5.2.2核心代碼分析NS2軟件可以對(duì).tcl文件進(jìn)行編譯，生成.nam文件，NS2的圖形仿真器便可執(zhí)行所生成的.nam文件，產(chǎn)生圖形動(dòng)畫。本次設(shè)計(jì)中編寫和修改的TCL文件有wireless.tcl、leach.tcl、ns-leach.tcl、uamps.tcl、ns-ranode.tcl、ns-resource-manager.tcl、ns-energy-resource.tcl、ns-neighbor-resource.tcl、ns-bsapp.tcl、extras.tcl、stats.tcl。文件的結(jié)構(gòu)和功用如下圖：圖5-13LEACH源代碼結(jié)構(gòu)圖現(xiàn)對(duì)其中的核心代碼進(jìn)行分析（完全版的代碼見附錄）。=1\*GB3①wireless.tcl文件：1、讀取參數(shù)并設(shè)置：getopt$argc$argv;#讀取leach_test中的參數(shù)并設(shè)置

procgetopt{argcargv}{

globalopt

lappendoptlistcpnnseedscstoptrxyfor{seti0}{$i<$argc}{incri}{

setarg[lindex$argv$i]

;#取出argv中第i個(gè)內(nèi)容

if{[stringrange$arg00]!="-"}continue;#如果argvi第i個(gè)內(nèi)容第一個(gè)字符內(nèi)容不為"-"，結(jié)束循環(huán)setname[stringrange$arg1end];#讀取argv第i個(gè)參數(shù)到name就是arg的內(nèi)容

setopt($name)[lindex$argv[expr$i+1]];#把name后面的參數(shù)進(jìn)行設(shè)置

}

}2、設(shè)置全局變量：setns_

[newSimulator]

setchan

[new$opt(chan)]

setprop

[new$opt(prop)]

settopo

[newTopography]

settracefd

[open$opt(tr)w]3、載入拓?fù)?topoload_flatgrid$opt(x)$opt(y)$proptopography$topo4、創(chuàng)建節(jié)點(diǎn)elseif{[stringcompare$opt(rp)"leach"]==0}{

for{seti0}{$i<$opt(nn)}{incri}{

leach-create-mobile-node$i5、節(jié)點(diǎn)結(jié)束時(shí)間for{seti0}{$i<$opt(nn)}{incri}{

$ns_at$opt(stop).000000001"$node_($i)reset";

}

$ns_at$opt(stop).00000001"puts\"NSEXITING...\";$ns_halt"6、載入場(chǎng)景文件if{$opt(sc)==""}{

puts"***NOTE:noscenariofilespecified."

setopt(sc)"none"}else{

puts"Loadingscenariofile..."

source$opt(sc)

puts"Loadcomplete..."7、開始仿真puts"StartingSimulation..."

$ns_run=2\*GB3②ns-leach.tcl文件：1、設(shè)置信息常量：setADV_CH0setJOIN_REQ1setADV_SCH2setDATA3setMAC_BROADCAST0xffffffffsetLINK_BROADCAST0xffffffffsetBYTES_ID22、設(shè)置初始化參數(shù)：setrng_[newRNG]$rng_seed0setisch_0sethasbeench_0setnext_change_time_0setround_0setclusterChoices_""setclusterDist_""setclusterNodes_""setcurrentCH_""setxmitTime_""setTDMAschedule_""setdist_0setcode_0setnow_0setalive_1setframe_time_$opt(frame_time)setend_frm_time_0setbegin_idle_0setbegin_sleep_0setmyADVnum_0setreceivedFrom_""setdataReceived_""3、其他：本文件中還配置有簇頭節(jié)點(diǎn)功能設(shè)置、分散簇組織功能設(shè)置、接收功能設(shè)置、發(fā)送功能設(shè)置和幫助功能設(shè)置，由于代碼量過大，具體請(qǐng)見附錄。=3\*GB3③uamps.tcl文件：1、導(dǎo)入資源自適應(yīng)節(jié)點(diǎn)：source$env(RCA_LIBRARY)/ns-ranode.tclsource$env(uAMPS_LIBRARY)/ns-bsapp.tclsource$env(uAMPS_LIBRARY)/extras.tclsource$env(uAMPS_LIBRARY)/stats.tcl#Uncommenttheselinestousegdbtodebugtheccode#sourcemit/uAMPS/ns-bsapp.tcl#sourcemit/uAMPS/extras.tcl#sourcemit/uAMPS/stats.tclsource$env(RCA_LIBRARY)/resources/ns-resource-manager.tclsource$env(RCA_LIBRARY)/resources/ns-energy-resource.tclsource$env(RCA_LIBRARY)/resources/ns-neighbor-resource.tcl2、缺失腳本配置：setopt(bsapp)"Application/BSApp";#BSapplicationtypesetopt(mtype)"";#Nometa-datausedsetopt(nn_)[expr$opt(nn)-1];#Numberofnon-BSnodessetopt(bsID)$opt(nn_);#BSnodenumbersetopt(bsCode)0;#SpreadingcodeforBSsetopt(quiet)1;#0=printinfo,1=quietsetopt(bw)1e6;#1Mbpsradiospeedsetopt(delay)1e-12;#Linksdelaysetopt(prop_speed)3e8;;#Meterspersecondsetopt(ll)RCALinkLayer;#Arplesslink-layersetopt(mac)Mac/Sensor;#Sensormacprotocolsetopt(ifq)Queue/DropTail;#DropTailQsetopt(ifqlen)100;#Maxpacketsinifqsetopt(netif)Phy/WirelessPhy;#Wirelesschannelsetopt(ant)Antenna/OmniAntenna;#Omnidirectionalantena#TimerequiredtotransmitnumbytesbytesofdataprocTxTime{numbytes}{globaloptreturn[expr$numbytes*8/$opt(bw)]}setopt(hdr_size)25;#Bytesforheadersetopt(sig_size)500;#Bytesfordatasignal#Packettransmissiontimesetopt(slot_time)[expr[TxTime[expr$opt(sig_size)+$opt(hdr_size)]]]#Spread-spectrumpackettransmissiontimesetopt(ss_slot_time)[expr$opt(slot_time)*$opt(spreading)]#MaximumTDMAframetime(ifallnodesinonecluster)setopt(frame_time)[expr$opt(ss_slot_time)*$opt(nn_)]setopt(ch_change)[expr10*$opt(init_energy)];#Timeforeachroundsetopt(check_energy)10;#Timebtwnenergytracessetopt(freq)914e+6;#Carrierfrequencysetopt(L)1.0;#System(non-propogation)losssetopt(Gt)1.0;#Txantennagainsetopt(Gr)1.0;#Rxantennagainsetopt(ht)1.5;#Antennaheightsetopt(CSThresh)1e-9;#Receivethresholdis1nWsetopt(RXThresh)6e-9;#Successthresholdis6nWsetPI3.1415926setl[expr3e8/$opt(freq)];#Wavelengthofcarrier5.2.3NSG2可視化工具介紹NSG是一個(gè)專為ns2所設(shè)計(jì)的劇本產(chǎn)生器，目前最新的版本為第