無線傳感器網(wǎng)絡(luò)flooding路由協(xié)議的MATLAB仿真

摘要無線傳感器網(wǎng)絡(luò)是計算機科學技術(shù)的一個新的研究領(lǐng)域，是傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù)相結(jié)合的產(chǎn)物。與傳統(tǒng)網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)具有造價低、功耗低、布局靈活性強、監(jiān)測精度高等特點，因此在軍事、醫(yī)療、家用等多個領(lǐng)域均有廣闊的應(yīng)用市場。本文重點研究基于無線傳感器網(wǎng)絡(luò)的泛洪式路由協(xié)議，無線傳感器網(wǎng)絡(luò)節(jié)點數(shù)量龐大、單個節(jié)點資源有限，其路由協(xié)議設(shè)計的首要目標是提高能量有效性，延長網(wǎng)絡(luò)壽命。本文總結(jié)了WSN的概念、結(jié)構(gòu)、特點，分析了WSN的關(guān)鍵性技術(shù)問題及網(wǎng)絡(luò)協(xié)議；研究了WSN的網(wǎng)絡(luò)協(xié)議體系和路由協(xié)議的分類，分析比擬了目前國內(nèi)外學者提出的幾種有代表性的路由協(xié)議及其性能優(yōu)缺點；選擇了flooding路由協(xié)議為研究重點，分析了該路由算法的具體實現(xiàn)，針對傳感器節(jié)點能量及傳輸范圍有限等特點，提出了一種基于延遲的自適應(yīng)泛洪路由算法，首先通過源節(jié)點在網(wǎng)內(nèi)用較小的路由請求報文和路由回復(fù)報文來建立路由，路由建立的過程中自適應(yīng)地確定等待時間以使更優(yōu)的路由請求報文得到轉(zhuǎn)發(fā)，然后源節(jié)點再沿著建立好的路徑轉(zhuǎn)發(fā)較大的數(shù)據(jù)報文。并采用MATLAB網(wǎng)絡(luò)仿真工具對該路由協(xié)議進行了整體仿真，并對其數(shù)據(jù)進行了分析。仿真實驗說明新算法較Flooding節(jié)能，能較好的克服Flooding算法中報文冗余度高、能耗大等缺乏。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；flooding路由協(xié)議；MATLAB仿真AbstractWirelesssensornetworksareanewresearchfieldofcomputerscienceandtechnology.Theyaretheintegrationofsensortechniques,nestedcomputationtechniques,distributedcomputationtechniquesandwirelesscommunicationtechniques.Comparingwithtraditionalnetworks,thewirelesssensornetworksfeatureswithlowcost,lowpowerloss,flexiblelayoutandhighmonitorprecision,thereforethesensornetworkscanbeusedforvariousapplicationareassuchasmilitary,chemical,home.ThisarticlefocusonwirelesssensornetworksbasedonthePanHung-routingprotocol,wirelesssensornetworknodeslargenumberofindividualnodeswithlimitedresources,theroutingprotocoldesignedfirstandforemostobjectiveistoimproveenergyefficiencyandextendthenetworklifetime.ThispapersummarizestheWSNtheconcept,structureandcharacteristicsoftheWSNthekeytechnicalproblemsandnetworkprotocols;studyoftheWSNsystemandnetworkroutingprotocolagreementtheclassification,analysisandcomparisonofthecurrentdomesticandforeignscholarshaveproposedseveralrepresentativesTheroutingoftheagreementanditsperformanceadvantagesanddisadvantages;chosenthefloodingfocusonroutingprotocols,analysisoftheroutingalgorithmtoachievethespecific,thesensornodesthelimitedscopeofenergyandtransmissioncharacteristics,adelaybasedontheAdaptiveFloodroutingalgorithm,firstofallthroughthenodesinthenetworksourceinthesmallerrouting,androutingtherequesttorestorethetexttocreatearouting,routingtheprocessofestablishingadaptivetodeterminethewaitingtimetomakebetterRoutingtherequestwastransmittedbytext,andthenanothersourcenodesalongthepathforwardtheestablishmentofgooddataonthelargertext.MATLABandusethenetworksimulationtoolfortheoverallroutingprotocolsimulation,andthedatawereanalyzed.ThesimulationshowsthatthenewalgorithmthanFloodingenergy-saving,canbetterovercomeFloodingalgorithmmessageredundancyandhighenergyconsumption,suchastheinsufficient.Keywords：WSN；floodingroutingprotocols；MATLABSimulation目錄TOC\o"1-3"\u1緒論 11.1課題背景 11.2國內(nèi)外技術(shù)研究現(xiàn)狀 21.3課題研究的目的和意義 32WSN綜述 42.1WSN的概念 42.2WSN的結(jié)構(gòu) 42.2.1節(jié)點結(jié)構(gòu) 42.2.2網(wǎng)絡(luò)體系結(jié)構(gòu) 52.3WSN協(xié)議棧 62.4WSN的拓撲結(jié)構(gòu) 72.5WSN的特點 102.6WSN的關(guān)鍵性技術(shù)問題 112.6.1功耗問題 122.6.2節(jié)能策略 122.6.3通信問題 142.6.4網(wǎng)絡(luò)平安問題 152.6.5定位問題 152.6.6數(shù)據(jù)管理 152.6.7效勞質(zhì)量 162.6.8嵌入式操作系統(tǒng) 163.WSN路由協(xié)議算法分析 163.1WSN路由協(xié)議的分類方法 173.2幾種典型路由協(xié)議的分析 183.2.1平面路由協(xié)議 183.2.2分層路由協(xié)議 214 Flooding路由協(xié)議的分析與研究 274.1泛洪算法模型 274.2算法流程圖 284.3基于延遲的自適應(yīng)洪泛路由算法 294.3.1算法中用到的報文和數(shù)據(jù) 294.3.2SFD算法描述 304.3.3性能比擬尺度 314.3.4理論分析 325Flooding路由協(xié)議的MATLAB仿真 355.1MATLAB仿真平臺介紹 355.2算法仿真實驗參數(shù) 385.3實驗結(jié)果 396 結(jié)論 42致謝 43參考文獻 44附錄A：英文原文 45附錄B：中文翻譯 51附錄C：程序代碼 551緒論1.1課題背景無線傳感器網(wǎng)絡(luò)是新興的下一代傳感器網(wǎng)絡(luò)，最早的代表性論述出現(xiàn)在1999年，題為“傳感器走向無線時代”。隨后在美國的移動計算和網(wǎng)絡(luò)國際會議上，提出了WSN下一個世紀面臨的開展機遇。2003年，美國《技術(shù)評論》雜志在論述未來新興十大技術(shù)時，WSN名列第一；同年，美國Businessweek預(yù)測的未來四大新技術(shù)：效用計算、傳感器網(wǎng)絡(luò)、塑料電子學和仿生人體器官，QSN也列入其中。2004年((IEEEspectrum》雜志發(fā)表一期專集《傳感器的國度》，論述了WSN的開展和可能的廣泛應(yīng)用?？梢灶A(yù)計，WSN的開展和廣泛應(yīng)用，將對人們的社會生活和產(chǎn)業(yè)變革帶來極大的影響和產(chǎn)生巨大的推動。有專家預(yù)計，WSN的廣泛應(yīng)用是一種必然趨勢，它的出現(xiàn)將會給人類社會帶來極大的變革。傳感器網(wǎng)絡(luò)的開展主要經(jīng)歷了4代：(1)第一代：上世紀70年代，就出現(xiàn)了具有簡單模擬信號傳輸功能的傳統(tǒng)傳感器所組成的點對點輸出的測控系統(tǒng)網(wǎng)絡(luò)。該網(wǎng)絡(luò)具有簡單信息獲取能力，只是初步實現(xiàn)了信息的單向傳遞，其缺點是布線復(fù)雜、抗干擾性差。(2)第二代：隨著相關(guān)學科的不斷開展和進步，傳感器網(wǎng)絡(luò)具有了獲取多種信息的綜合處理能力，并通過采用串/并接口與傳感控制器的相聯(lián)，組成了有信息綜合和處理能力的傳感器網(wǎng)絡(luò)。(3)第三代：20世紀90年代后期，出現(xiàn)了基于現(xiàn)場總線技術(shù)的智能傳感器網(wǎng)絡(luò)?，F(xiàn)場總線是連接智能化現(xiàn)場設(shè)備和控制室的全數(shù)字、開放式的雙向通信網(wǎng)絡(luò)智能傳感器的通信技術(shù)進入局域網(wǎng)階段，其局部測控網(wǎng)絡(luò)通過網(wǎng)關(guān)和路由器可以實現(xiàn)與Intimae燈Intranet連接。(4)第四代：大量多功能傳感器被運用，并采用無線通信機制，因此也稱為。WSN，正處于研究和開發(fā)階段。WSN是一種無根底設(shè)施的網(wǎng)絡(luò)，由一定數(shù)目的傳感器節(jié)點構(gòu)成，它綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù)，能協(xié)作地實時監(jiān)測、感知和采集節(jié)點部署區(qū)域的各種環(huán)境或監(jiān)測對象的信息(如光強、溫度、濕度、噪音和有害氣體濃度等物理現(xiàn)象)，并對這些數(shù)據(jù)進行處理，獲得詳盡而準確的信息，通過無線網(wǎng)絡(luò)最終發(fā)送給觀察者。在環(huán)境監(jiān)測、醫(yī)療護理、搶險救災(zāi)、智能家居、工業(yè)生產(chǎn)控制以及商業(yè)等領(lǐng)域具有廣闊的應(yīng)用前景。1.2國內(nèi)外技術(shù)研究現(xiàn)狀目前，國內(nèi)外WSN研究主要集中于網(wǎng)絡(luò)協(xié)議、能量、定位、可靠性、網(wǎng)絡(luò)架構(gòu)以及數(shù)據(jù)處理等問題，網(wǎng)絡(luò)協(xié)議的研究是其中的熱點之一。針對無線自主網(wǎng)絡(luò)的特點，經(jīng)過多年的研究，國內(nèi)外的研究人員相繼提出了許多專門應(yīng)用于無線自主網(wǎng)絡(luò)的路由協(xié)議。目前提出的各種路由協(xié)議根本上可以按照三種思路進行分類。按照獲取路由信息的時機分類，可分為主動路由協(xié)議和按需路由協(xié)議。主動路由有DSDV、WRP、STARA；按需路由協(xié)議主要有DSR、AODV。按照網(wǎng)絡(luò)的層次分類，可分為平面結(jié)構(gòu)路由和層次結(jié)構(gòu)路由。平面路由協(xié)議主要有flooding、SPIN、DD、HREEMR、SAR；層次結(jié)構(gòu)路由主要有LEACH、PEGASIS等。按照協(xié)議的功能分類，可分為支持地理定位輔助路由和不支持地理定位輔助路由；支持效勞質(zhì)量QoS的路由協(xié)議和不支持QoS的路由協(xié)議；支持組播通信的路由協(xié)議和不支持組播通信的路由協(xié)議等。地理定位輔助協(xié)議主要有MECN和SMECN。無線傳感器網(wǎng)絡(luò)的研究起始于20世紀90年代末期，由于具有巨大的應(yīng)用價值，它己經(jīng)引起了世界許多國家的軍事界、工業(yè)界和學術(shù)界的極大關(guān)注。從2000年起，國際上開始出現(xiàn)一些有關(guān)傳感器網(wǎng)絡(luò)研究的報道，美國自然科學基金委員會2003年制定了傳感器網(wǎng)絡(luò)研究方案，支持相關(guān)根底理論的研究。在美國自然科學基金委員會的推動下，美國的加州大學伯克利分校、麻省理工學院、康奈爾大學、加州大學洛杉磯分校等學校開始了傳感器網(wǎng)絡(luò)的根底理論和關(guān)鍵技術(shù)的研究。美國國防部和各軍事部門都對傳感器網(wǎng)絡(luò)高度重視，把傳感器網(wǎng)絡(luò)作為一個重要研究領(lǐng)域，設(shè)立了一系列的軍事傳感器網(wǎng)絡(luò)研究工程。美國英特爾公司、微軟公司等信息業(yè)巨頭也開始了傳感器網(wǎng)絡(luò)方面的研究工作。日本、德國、英國、意大利等科技興旺國家也對無線傳感器網(wǎng)絡(luò)表現(xiàn)出了極大的興趣，紛紛展開了該領(lǐng)域的研究工作。我國在WSN方面的研究工作剛剛開始，清華大學、電子科技大學、哈爾濱工業(yè)大學等單位已經(jīng)進行了該領(lǐng)域的研究工作，但目前主要集中在介紹國外的研究進展，提出新的研究問題，尚未見有新的協(xié)議提出。由于WSN是一門新興技術(shù)，IEEE尚未成立WSN的標準制定小組，美國也是在2000年才開始出現(xiàn)一些有關(guān)WSN研究結(jié)果的報道，所以國內(nèi)與國際水平的差距并不大，電子科技大學計算機學院正在開展WSN路由協(xié)議的設(shè)計和仿真工作，力爭在5年內(nèi)到達國際水平。但WSN尚未到達完全實用階段，大局部工作仍處在仿真和實驗階段，仿真規(guī)模在數(shù)百至數(shù)千個節(jié)點，實驗規(guī)模在幾十個節(jié)點左右。1.3課題研究的目的和意義如前所述，WSN有著廣泛而有價值的應(yīng)用領(lǐng)域，比方水工建筑物平安監(jiān)測，大型工程建筑物的運行平安，結(jié)合現(xiàn)代監(jiān)測理論及WSN技術(shù)，布置節(jié)點實現(xiàn)無人值守，為設(shè)計施工及時反響信息，對減輕觀測的勞動強度，提高平安監(jiān)控的技術(shù)水平，具有重大的社會經(jīng)濟效益和應(yīng)用價值。而在個人通信和接入網(wǎng)等方面的應(yīng)用那么具有良好的商業(yè)前景。因此，對WSN網(wǎng)絡(luò)技術(shù)的研究既有重要的社會意義又蘊含著潛在的經(jīng)濟價值。因此它已經(jīng)引起了世界工業(yè)界和學術(shù)界的極大關(guān)注，開展這項對人類未來生活影響深遠的前沿科技的研究，對整個國家的社會、經(jīng)濟將有重大的戰(zhàn)略意義。而從網(wǎng)絡(luò)層模型的角度分析，每一層都有需要結(jié)合WSN的特點進行細致研究的問題，己有的研究主要集中在網(wǎng)絡(luò)層和鏈路層。網(wǎng)絡(luò)數(shù)據(jù)傳輸離不開路由協(xié)議，路由協(xié)議是其組網(wǎng)的根底。路由技術(shù)是WSN通信層的核心技術(shù)。路由選擇問題是WSN網(wǎng)絡(luò)構(gòu)建時所要著重考慮的一個問題，從路由的角度來看，WSN有其自身的特點，使它既不同于傳統(tǒng)網(wǎng)絡(luò)，又不同于無線自組網(wǎng)Adhoc網(wǎng)絡(luò)。傳統(tǒng)的無線Adhoc網(wǎng)絡(luò)路由協(xié)議不適合用于WSN，我們必須設(shè)計全新的、適合于WSN特點的路由協(xié)議。路由協(xié)議作為影響網(wǎng)絡(luò)性能的一個重要因素，是確保WSN網(wǎng)絡(luò)正常運行的關(guān)鍵。雖然己提出了很多的協(xié)議，但是到底那一種是最適宜的還沒有一個定論。因此研究這些路由協(xié)議，比擬分析哪一種路由協(xié)議是相對適宜的顯得尤為重要，也是此論文的意義所在。本課題重點研究基于無線傳感器網(wǎng)絡(luò)的泛洪式路由協(xié)議，無限傳感器網(wǎng)絡(luò)節(jié)點數(shù)量龐大、單個節(jié)點資源有限，其路由協(xié)議設(shè)計的首要目標是提高能量有效性，延長網(wǎng)絡(luò)壽命。本文總結(jié)了WSN的概念、結(jié)構(gòu)、特點，分析了WSN的關(guān)鍵性技術(shù)問題及網(wǎng)絡(luò)協(xié)議；研究了WSN的網(wǎng)絡(luò)協(xié)議體系和路由協(xié)議的分類，分析比擬了目前國內(nèi)外學者提出的集中有代表性的路由協(xié)議及其性能優(yōu)缺點；選擇了flooding路由協(xié)議為研究重點，分析了該路由算法的具體實現(xiàn)，并采用MATLAB網(wǎng)絡(luò)仿真工具對flooding路由協(xié)議進行了整體仿真，并對其數(shù)據(jù)進行了分析。2WSN綜述無線傳感器網(wǎng)絡(luò)是傳感器技術(shù)、網(wǎng)絡(luò)通信和計算機技術(shù)的集大成者，是一種全新的信息獲取和處理技術(shù)。美國《技術(shù)評論》雜志在論述未來新興十大技術(shù)時,更是將無線傳感器網(wǎng)絡(luò)名列第一；美國BusinessWeek預(yù)測的未來四大新技術(shù)：效用計算、傳感器網(wǎng)絡(luò)、塑料電子學和仿生人體器官，無線傳感器網(wǎng)絡(luò)也列入其中。有專家預(yù)計，無線傳感器網(wǎng)絡(luò)的廣泛應(yīng)用是一種必然趨勢，它的出現(xiàn)將會給人類社會帶來極大的變革。2.1WSN的概念無線傳感器網(wǎng)絡(luò)是由一個個具有數(shù)據(jù)采集、計算和通信能力的傳感器節(jié)點，通過自組織網(wǎng)絡(luò)形成的一個動態(tài)、自適應(yīng)的分布式計算平臺。每個傳感器都是典型的嵌入式系統(tǒng)，具有存儲容量小、運算能力差、功耗低、易失效的特點。2.2WSN的結(jié)構(gòu)節(jié)點結(jié)構(gòu)在不同應(yīng)用中，傳感器節(jié)點的結(jié)構(gòu)不盡相同，但一般都由傳感器模塊、處理器模塊、無線通信模塊和能量供給模塊四局部組成，如圖2.1所示。傳感器模塊負責監(jiān)測區(qū)域內(nèi)信息的采集和數(shù)據(jù)轉(zhuǎn)換，傳感器的類型是由被監(jiān)測物理信號的形式?jīng)Q定的，如用于溫度監(jiān)測的鉑電阻傳感器，用于壓力傳感的電容式傳感器等;處理器模塊負責控制整個傳感器節(jié)點的操作，存儲和處理本身采集的數(shù)據(jù)以及其他節(jié)點發(fā)送來的數(shù)據(jù);無線通信模塊負責與其他傳感器節(jié)點進行無線通信，交換控制信息和收發(fā)采集數(shù)據(jù);能量供給模塊為傳感器節(jié)點提供運行所需的能量，通常采用微型電池，不過已有公司探索從周圍環(huán)境取得能量并將其轉(zhuǎn)換成微瓦電能的方法。傳感器傳感器AC/DC傳感器模塊網(wǎng)絡(luò)MAC收發(fā)器無線通信模塊處理器存儲器處理器模塊能量供給模塊圖2.1傳感器網(wǎng)絡(luò)節(jié)點結(jié)構(gòu)網(wǎng)絡(luò)體系結(jié)構(gòu)在傳感器網(wǎng)絡(luò)中,節(jié)點任意散落在被監(jiān)測區(qū)域內(nèi),這一過程是通過飛行器撒播、人工埋置和火箭彈射等方式完成的。節(jié)點以自組織形式構(gòu)成網(wǎng)絡(luò),通過多跳中繼方式將監(jiān)測數(shù)據(jù)傳到sink節(jié)點,最終借助長距離或臨時建立的sink鏈路將整個區(qū)域內(nèi)的數(shù)據(jù)傳送到遠程中心進行集中處理。衛(wèi)星鏈路可用作sink鏈路,借助游弋在監(jiān)測區(qū)上空的無人飛機回收sink節(jié)點上的數(shù)據(jù)也是一種方式,UCBerkeley在進行UAV(unmannedaerialvehicle)工程的外場測試時便采用了這種方式。如果網(wǎng)絡(luò)規(guī)模太大,可以采用聚類分層的管理模式,圖2.2給出了傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)一般形式的描述。圖2.2傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)2.3WSN協(xié)議棧無線傳感器網(wǎng)絡(luò)協(xié)議棧包括物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸聯(lián)網(wǎng)協(xié)議棧的五層協(xié)議相對應(yīng)，如圖2.3所示。另外，協(xié)議棧還包括動管理平臺和任務(wù)管理平臺。這些管理平臺使得傳感器節(jié)點能夠按照同工作，在節(jié)點移動的傳感器網(wǎng)絡(luò)中轉(zhuǎn)發(fā)數(shù)據(jù)，并支持多任務(wù)和資源平臺的功能如下：物理層提供簡單但健壯的信號調(diào)制和無線收發(fā)技術(shù)；數(shù)據(jù)鏈路層負責數(shù)據(jù)成幀，幀檢測、媒體訪問和過失控制；網(wǎng)絡(luò)層主要負責路由生成與路由選擇；傳輸層負責數(shù)據(jù)流的傳輸控制，是保證通信效勞質(zhì)量的重要；應(yīng)用層包括一系列基于監(jiān)測任務(wù)的應(yīng)用層軟件；能量管理平臺管理傳感器節(jié)點如何使用能源，在各個協(xié)議層量；移動管理平臺檢測并注冊傳感器節(jié)點的移動，維護到會聚節(jié)感器節(jié)點能夠動態(tài)跟蹤其鄰居的位置；任務(wù)管理平臺在一個給定的區(qū)域內(nèi)平衡和調(diào)度檢測任務(wù)。能量管理平臺能量管理平臺移動管理平臺任務(wù)管理平臺應(yīng)用層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層傳輸層物理層圖2.3無線傳感器網(wǎng)絡(luò)協(xié)議棧2.4WSN的拓撲結(jié)構(gòu)在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點是體積微小的嵌入式設(shè)備，采用能量有限的電池供電，它的計算能力和通信能力十分有限，所以除了要設(shè)計能量高效的MAC協(xié)議、路由協(xié)議以及應(yīng)用層協(xié)議之外，還要設(shè)計優(yōu)化的網(wǎng)絡(luò)拓撲控制機制。對于自組織的無線傳感器網(wǎng)絡(luò)而言，網(wǎng)絡(luò)拓撲控制對網(wǎng)絡(luò)性能影響很大。良好的拓撲結(jié)構(gòu)能夠提高路由協(xié)議和MAC協(xié)議的效率，為數(shù)據(jù)融合、時間同步和目標定位等很多方面提供根底，有利于延長整個網(wǎng)絡(luò)的生存時間。所以，拓撲控制是傳感器網(wǎng)絡(luò)中的一個根本問題。在無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)控制有著十分重要的意義，主要表現(xiàn)在以下幾個方面:影響整個網(wǎng)絡(luò)的生命周期?；跓o線傳感器網(wǎng)絡(luò)有限的能量，節(jié)能是網(wǎng)絡(luò)設(shè)計主要考慮的問題之一，拓撲控制的一個重要目標就是在保證網(wǎng)絡(luò)連通性和覆蓋率的情況下，盡量合理高效地使用網(wǎng)絡(luò)能量，延長整個網(wǎng)絡(luò)的生存時間。減小節(jié)點間通信干擾，提高網(wǎng)絡(luò)通信效率。無線傳感器網(wǎng)絡(luò)中節(jié)點通常密集分布，如果每個節(jié)點都以大功率進行通信，會加劇節(jié)點之間的干擾，降低通信效率，并造成節(jié)點能量的浪費。另一方面，如果選擇太小的發(fā)射功率，會影響網(wǎng)絡(luò)的連通性。為路由協(xié)議提供根底。在無線傳感器網(wǎng)絡(luò)中，只有活動的節(jié)點才能進行數(shù)據(jù)轉(zhuǎn)發(fā)，而拓撲結(jié)構(gòu)控制可以確定由哪些節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，同時確定節(jié)點之間的鄰居關(guān)系。影響數(shù)據(jù)融合。無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)融合指傳感器節(jié)點將采集的數(shù)據(jù)發(fā)送給中心節(jié)點，中心節(jié)點進行數(shù)據(jù)融合，并把融合后的數(shù)據(jù)發(fā)送給會聚節(jié)點。而中心節(jié)點的選擇是拓撲結(jié)構(gòu)控制的一個重要內(nèi)容。彌補節(jié)點失效的影響。傳感器節(jié)點可能部署在惡劣的環(huán)境中，在軍事應(yīng)用中甚至部署在敵方區(qū)域中，所以很容易受到破壞而失效。這就要求網(wǎng)絡(luò)拓撲結(jié)構(gòu)具有魯棒性以適應(yīng)這種情況。無線傳感器網(wǎng)絡(luò)特定的應(yīng)用環(huán)境及其固有的特征，對傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)的設(shè)計提出了新的要求。在無線傳感器網(wǎng)絡(luò)中，節(jié)點需要完全以自組織的形式構(gòu)成自治型網(wǎng)絡(luò)，并且能夠工作在無人值守的惡劣環(huán)境當中。到目前為止，無線傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)的研究主要集中在兩個方向，即平面型拓撲結(jié)構(gòu)和層次型拓撲結(jié)構(gòu)。平面型拓撲結(jié)構(gòu)平面型拓撲結(jié)構(gòu)，所有節(jié)點的地位平等、作用相同，既采集數(shù)據(jù)又進行數(shù)據(jù)通信的中轉(zhuǎn)，網(wǎng)絡(luò)中不存在集中式控制中心。為了有效地節(jié)省能量，遠距離節(jié)點之間以多跳通信方式，如圖2.4所示。平面結(jié)構(gòu)網(wǎng)絡(luò)比擬簡單，無需任何的結(jié)構(gòu)維護過程，節(jié)點根據(jù)預(yù)定的路由協(xié)議自組織成無線網(wǎng)絡(luò)。由于隨機分布、高密度等特性，源節(jié)點和目的節(jié)點之間可能存在多條傳輸路徑，如圖2.4中節(jié)點A和E之間存在兩條路徑:A一>C一>D一>E和A一>C一>F一>E，既可以使用多條路徑實現(xiàn)負載分擔，也可以為不同的數(shù)據(jù)傳輸需求選擇適當?shù)穆窂健Ｆ矫娼Y(jié)構(gòu)網(wǎng)絡(luò)中所有的傳感器節(jié)點理論上是對等的，不存在瓶頸和單點故障，所以比擬健壯，但是網(wǎng)絡(luò)規(guī)模受限，動態(tài)擴展性差，難以維護。在平面結(jié)構(gòu)中，源節(jié)點為了獲得目的節(jié)點信息通常需要傳輸大量的查詢消息，而且由于網(wǎng)絡(luò)的動態(tài)性，如節(jié)點失效、增加等，維護這些動態(tài)變化的路由信息需要發(fā)送大量的控制消息。網(wǎng)絡(luò)規(guī)模越大路由維護的開銷就越大，當網(wǎng)絡(luò)的規(guī)模增加到某個程度時，網(wǎng)絡(luò)的所有帶寬可能被路由協(xié)議消耗掉，所以平面式結(jié)構(gòu)的網(wǎng)絡(luò)擴展性較差。InternetInternetSinkCDFEAB傳感器節(jié)點傳感區(qū)域圖2.4平面型拓撲結(jié)構(gòu)層次型拓撲結(jié)構(gòu)層次型拓撲結(jié)構(gòu)中，網(wǎng)絡(luò)根據(jù)具體應(yīng)用需求，如地理區(qū)域、能源、應(yīng)用類型等，劃分為簇(Cluster)，每個簇由一個簇頭節(jié)點和多個簇成員構(gòu)成，多個簇頭節(jié)點抽象成高一級的網(wǎng)絡(luò)，在高一級網(wǎng)絡(luò)中可以繼續(xù)分簇，形成更高一級網(wǎng)絡(luò)，最終形成多層次組織結(jié)構(gòu)的傳感器網(wǎng)絡(luò)，如圖2.5所示。C1C1C2C3AB傳感器節(jié)點簇頭圖2.5層次拓撲結(jié)構(gòu)層次型拓撲結(jié)構(gòu)中，不同層次以自己的局部概念進行交互，聚集起來實現(xiàn)期望的全局任務(wù)。分層組織結(jié)構(gòu)中，簇內(nèi)成員節(jié)點負責感知任務(wù)，以多跳方式將采集的信息發(fā)送到簇頭節(jié)點。簇頭節(jié)點作為簇類的中心節(jié)點，擔負著與遠程終端通訊、發(fā)布簇類管理信息、執(zhí)行更高層次的數(shù)據(jù)融合和數(shù)據(jù)分析等使命。為了有效利用能源和延長網(wǎng)絡(luò)的生命周期，簇頭節(jié)點通常依據(jù)能量概率分布由網(wǎng)絡(luò)節(jié)點輪流充當。這樣可以使簇頭節(jié)點的高能量消耗平均到網(wǎng)絡(luò)節(jié)點上，同時也防止了固定簇頭引起的網(wǎng)絡(luò)的脆弱性和不穩(wěn)定性，而且可以通過簇拆分來增加簇的個數(shù)或者簇聚合形成更高一級網(wǎng)絡(luò)來提高整個網(wǎng)絡(luò)的容量。但缺點是，為了維護層次化結(jié)構(gòu)需要仔細設(shè)計簇頭選擇算法。而且簇間節(jié)點為了完成數(shù)據(jù)通信需要經(jīng)過簇頭轉(zhuǎn)發(fā)，因此不一定能使用最正確路由，例如圖2.5中的A、B節(jié)點，物理距離很接近，在平面結(jié)構(gòu)中可以直接通信，但分簇后需要通過兩個簇的簇頭中繼進行通信。2.5WSN的特點傳感節(jié)點體積小，本錢低，計算能力有限無線傳感器網(wǎng)絡(luò)是在MEMS技術(shù)、數(shù)字電路技術(shù)根底上開展起來的，傳感節(jié)點各局部集成度很高，因此具有體積小的優(yōu)點，當然從應(yīng)用角度講，減小節(jié)點尺寸也是必須考慮的設(shè)計要素。傳感網(wǎng)絡(luò)是由大量的傳感節(jié)點組成的，單個節(jié)點的本錢直接影響到網(wǎng)絡(luò)的總體本錢，如果總體本錢比使用傳統(tǒng)傳感器的本錢高，勢必會影響無線傳感網(wǎng)絡(luò)的競爭力。由于體積、本錢以及能量的限制，嵌入式處理器和存儲器的能力和容量有限，因此傳感器的計算能力十分有限。傳感節(jié)點數(shù)量大、易失效，具有自適應(yīng)性根據(jù)應(yīng)用的不同，傳感器節(jié)點的數(shù)量可能到達幾百萬個甚至更多。此外，傳感器網(wǎng)絡(luò)工作在比擬惡劣的環(huán)境中，經(jīng)常有新節(jié)點參加或已有節(jié)點失效，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)變化很快，而且網(wǎng)絡(luò)一旦形成，人很少干預(yù)其運行。因此，傳感器網(wǎng)絡(luò)的硬件必須具有高強壯性和容錯性，相應(yīng)的通信協(xié)議必須具有可重構(gòu)和自適應(yīng)性。通信半徑小，帶寬很低無線傳感器網(wǎng)絡(luò)是利用多跳來實現(xiàn)低功耗下的數(shù)據(jù)傳輸，因此其設(shè)計的通信覆蓋范圍只有幾十米。和傳統(tǒng)無線網(wǎng)絡(luò)不同，傳感器網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)大局部是經(jīng)過節(jié)點處理過的數(shù)據(jù)，因此流量較小。根據(jù)目前觀察到的現(xiàn)象特性來看，傳感數(shù)據(jù)所需的帶寬將會很低(l~100kbi燈s)。電源能量是網(wǎng)絡(luò)壽命的關(guān)鍵無線傳感器網(wǎng)絡(luò)中通常運行在人無法接近的惡劣甚至危險的遠程環(huán)境中，能源無法替代，只能選擇鈕扣式電池供電，電源能量極其有限，網(wǎng)絡(luò)中的傳感器由于電源能量的原因經(jīng)常失效或廢棄，因此電源效率是設(shè)計考慮的關(guān)鍵因素。以數(shù)據(jù)為中心的網(wǎng)絡(luò)對于觀察者來說，傳感器網(wǎng)絡(luò)的核心是感知數(shù)據(jù)，而不是網(wǎng)絡(luò)硬件。比方在智能家居應(yīng)用中人們可能希望知道“現(xiàn)在客廳的溫度室多少”，而不會關(guān)心“2號節(jié)點感測到的溫度是多少”。以數(shù)據(jù)為中心的特點要求傳感器網(wǎng)絡(luò)的設(shè)計必須以對感知數(shù)據(jù)的管理和處理為中心，把數(shù)據(jù)庫技術(shù)和網(wǎng)絡(luò)技術(shù)緊密結(jié)合，從邏輯概念和軟、硬件技術(shù)兩個方面實現(xiàn)一個高性能的以數(shù)據(jù)為中心的網(wǎng)絡(luò)系統(tǒng)，使用戶如同使用通常的數(shù)據(jù)庫管理系統(tǒng)和數(shù)據(jù)處理系統(tǒng)一樣自如地在傳感器網(wǎng)絡(luò)上對感知數(shù)據(jù)進行管理和處理。2.6WSN的關(guān)鍵性技術(shù)問題無線傳感器網(wǎng)絡(luò)與傳統(tǒng)的無線網(wǎng)絡(luò)(如WLAN和蜂窩移動網(wǎng)絡(luò))有著不同的設(shè)計目標，后者在高度移動的環(huán)境中通過優(yōu)化路由和資源管理策略最大化帶寬的利用率，同時為用戶提供一定的效勞質(zhì)量保證。在無線傳感器網(wǎng)絡(luò)中，除了少數(shù)節(jié)點需要移動以外,大局部節(jié)點都是靜止的。因為它們通常運行在人無法接近的惡劣甚至危險的遠程環(huán)境中,能源無法替代，設(shè)計有效的策略延長網(wǎng)絡(luò)的生命周期成為無線傳感器網(wǎng)絡(luò)的核心問題。當然,從理論上講,太陽能電池能持久地補給能源，但工程實踐中生產(chǎn)這種微型化的電池還有相當?shù)碾y度。在無線傳感器網(wǎng)絡(luò)的研究初期，人們一度認為成熟的Internet技術(shù)加上Ad-hoc路由機制對傳感器網(wǎng)絡(luò)的設(shè)計是足夠充分的,但深入的研究說明:傳感器網(wǎng)絡(luò)有著與傳統(tǒng)網(wǎng)絡(luò)明顯不同的技術(shù)要求。前者以數(shù)據(jù)為中心,后者以傳輸數(shù)據(jù)為目的.為了適應(yīng)廣泛的應(yīng)用程序,傳統(tǒng)網(wǎng)絡(luò)的設(shè)計遵循著“端到端”的邊緣論思想,強調(diào)將一切與功能相關(guān)的處理都放在網(wǎng)絡(luò)的端系統(tǒng)上,中間節(jié)點僅僅負責數(shù)據(jù)分組的轉(zhuǎn)發(fā),對于傳感器網(wǎng)絡(luò),這未必是一種合理的選擇。一些為自組織的Ad-hoc網(wǎng)絡(luò)設(shè)計的協(xié)議和算法未必適合傳感器網(wǎng)絡(luò)的特點和應(yīng)用的要求。節(jié)點標識(如地址等)的作用在傳感器網(wǎng)絡(luò)中就顯得不是十分重要,因為應(yīng)用程序不怎么關(guān)心單節(jié)點上的信息；中間節(jié)點上與具體應(yīng)用相關(guān)的數(shù)據(jù)處理、融合和緩存也顯得很有必要。在密集性的傳感器網(wǎng)絡(luò)中,相鄰節(jié)點間的距離非常短,低功耗的多跳通信模式節(jié)省功耗,同時增加了通信的隱蔽性,也防止了長距離的無線通信易受外界噪聲干擾的影響。這些獨特的要求和制約因素為傳感器網(wǎng)絡(luò)的研究提出了新的技術(shù)問題。功耗問題作為一種微電子設(shè)備，無線傳感器節(jié)點只能配置電池，電池電量一般小于0.SAh，電壓為1.2v-3.3V。在一些具體應(yīng)用中，電池更換是不現(xiàn)實的。所以，節(jié)點生命期嚴重依賴于電池供電的持續(xù)時間。在WSN中，每個節(jié)點都起著數(shù)據(jù)采集器和路由器的雙重作用。一些節(jié)點的故障會引起拓撲的明顯變化，可能要求重建路由或重組織網(wǎng)絡(luò)。所以，能量保護和能量管理至關(guān)重要。傳感節(jié)點的主要功能是感知、處理和數(shù)據(jù)傳輸，其能耗也主要分布在這三個方面。感知能耗與具體應(yīng)用環(huán)境中攜帶的不同傳感單元有關(guān)。通信能耗在節(jié)點能耗中比例最大，需要考慮啟動功耗、接收功耗和發(fā)送功耗，無線電收發(fā)器能耗公式如下:〔2.1〕其中，Pc為無線通信功耗；PT和PR分別為無線發(fā)送和接收器件的功耗；PouT為無線發(fā)送器的輸出功率；Ton、Ron伽分別為每個單位時間內(nèi)無線發(fā)送器和無線接收器的翻開的時間；Tst、RST分別為發(fā)送和接收的啟動時間；NT、NR為單位時間內(nèi)接收和發(fā)送的次數(shù)，依賴于任務(wù)和采用的媒介訪問控制(MAC)策略；Ton也可寫成L/R，L為數(shù)據(jù)包大小，R為數(shù)據(jù)傳輸速率。數(shù)據(jù)處理功耗比通信功耗要小得多，例如:假定瑞利衰落且能量與距離的4次方成正比損耗，實驗說明，無線傳輸1K比特的數(shù)據(jù)100米的能量可以讓l00MIPS/W的處理器處理300萬條指令。因此盡可能地進行本地數(shù)據(jù)處理而減少數(shù)據(jù)的無線傳輸是降低WSN能耗的有效方法之一。針對數(shù)據(jù)采集、接收、發(fā)送和計算這四者的能耗問題，curtSchurgers等人進行了實驗。實驗結(jié)果說明，發(fā)送數(shù)據(jù)(Tx)的能耗略大于接收數(shù)據(jù)(Rx)，二者遠大于數(shù)據(jù)處理(計算)和數(shù)據(jù)采集的能耗。2.6.2節(jié)能策略由于無線通信是WSN能耗的主要局部，因此對無線收發(fā)系統(tǒng)的能耗管理非常重要，可以采取以下措施減少通信模塊的能量損耗。(l)減少通信流量減少通信流量的方法有：a.本地計算和數(shù)據(jù)融合b.減少沖突，增加錯誤檢測和校正機制d.減少控制包的開銷和包頭長度。(2)增加睡眠時間無線通信模塊有發(fā)送、接收、空閑和睡眠4種狀態(tài)。無線通信模塊在空閑狀態(tài)一直監(jiān)聽無線信道的使用情況，檢查是否有數(shù)據(jù)發(fā)送給自己，而在睡眠狀態(tài)那么關(guān)閉通信模塊。從實驗中可以看到：無線通信模塊在發(fā)送狀態(tài)的能量消耗最大，而在空閑狀態(tài)和接收狀態(tài)的能量消耗接近，略少于發(fā)送狀態(tài)的能量消耗，在睡眠狀態(tài)的能量消耗最少。因此不需要通信時，盡快進入睡眠狀態(tài)是WSN協(xié)議設(shè)計重點考慮的問題。(3)采用多跳短距離無線通信方式無線通信消耗能量E與通信距離d的關(guān)系為E=kdn。其中，參數(shù)n滿足關(guān)系2≤n<6，考慮諸多因素，一般取n為3。隨著通信距離的增加，能耗將急劇增加。因此，在滿足通信速率的前提下，應(yīng)該盡量減少單跳通信距離。一般傳感器節(jié)點的通信半徑在10Om以內(nèi)較為適宜。(4)動態(tài)功率管理(dynamicpowermanagement，簡稱DPM)DPM技術(shù)的核心問題是狀態(tài)轉(zhuǎn)換策略，由于狀態(tài)轉(zhuǎn)換需要消耗一定的能量并且?guī)в袝r延，如果狀態(tài)轉(zhuǎn)換策略不適宜，不僅無法節(jié)能，反而會導致能耗的增加，還會影響實時性能。DPM的狀態(tài)轉(zhuǎn)換可如圖2.6所示，假定狀態(tài)轉(zhuǎn)換分別發(fā)生在t1和t2時刻，其中t2=ti+t1，在tl時刻節(jié)點K想要從Sm狀態(tài)進入休眠狀態(tài)Sn，在t2時刻需要從Sn返回到Sm狀態(tài)，每個狀態(tài)都有對應(yīng)的能耗Pm和Pn，狀態(tài)轉(zhuǎn)換分別需要時間tdk和tuk那么能量節(jié)約如公式所示:〔2.2〕只有當ti大于某一數(shù)值時，Esave才能大于零，從而實現(xiàn)節(jié)能。ttdktukSnSmt2t1t1tPnPmE圖2.6狀態(tài)轉(zhuǎn)換和能量的關(guān)系(5)動態(tài)電壓調(diào)度(dynamicvoltagescheduling，簡稱DVS)DVS的主要原理是基于負載狀態(tài)動態(tài)調(diào)節(jié)供電電壓來減小系統(tǒng)功耗，并被應(yīng)用到PDA之類的個人移動設(shè)備上?？蓪⑵鋺?yīng)用到WSN中，如圖2.7所示的功率控制原理圖。節(jié)點上的嵌入式操作系統(tǒng)負責調(diào)度來自不同任務(wù)隊列的請求接受效勞，并實時監(jiān)測處理器的利用率和任務(wù)隊列的長度，負載觀測器依據(jù)這兩個參數(shù)的序列值計算負載的標稱值。，直流/直流變換器參照該值輸出幅值為A的電壓，支持處理器的正常工作。這構(gòu)成了一個典型的閉環(huán)反響系統(tǒng)?？刂评碚撝谐墒斓姆椒梢詾樵撓到y(tǒng)中各個模塊的設(shè)計提供有力的支持。傳感器節(jié)點大局部時間計算負載較低，在低負載時調(diào)卑微處理器的電壓可以有效節(jié)約能量。DC/DCDC/DC負載觀測器標準電壓WV〔A〕r帶可變電壓的處理器LVrixod圖2.7:DVS功率控制原理圖通信問題WSN內(nèi)正常通信聯(lián)系中，信號可能被一些障礙物或其它電子信號干擾而受到影響，如何平安有效的進行通信是個有待研究的問題。WSN需要具有能對信道衰落不敏感、發(fā)射信號功率譜密度低、低截獲低功耗短距離的無線通信技術(shù)。IEEE802.15.4標準是針對低速無線個人域網(wǎng)絡(luò)的無線通信標準，由于它的網(wǎng)絡(luò)特征和WSN存在很多相似之處，故很多研究機構(gòu)將它作為WSN的無線通信平臺。超寬帶技術(shù)(UWB)是一種極具潛力的無線通信技術(shù)。超寬帶技術(shù)具有系統(tǒng)復(fù)雜度低、能提供精確至數(shù)厘米的定位精度等優(yōu)點，非常適合應(yīng)用于WSN。網(wǎng)絡(luò)平安問題平安是系統(tǒng)可用的前提，WSN是網(wǎng)絡(luò)家庭的新成員，像其他網(wǎng)絡(luò)一樣需要考慮平安問題。WSN的平安問題主要以下幾個方面：傳統(tǒng)無線電磁干擾；對路由機制進行攻擊；對能量的攻擊，侵入節(jié)點導致網(wǎng)絡(luò)的某些節(jié)點和網(wǎng)絡(luò)段互發(fā)大量的垃圾數(shù)據(jù)，使WSN能量迅速耗盡，網(wǎng)絡(luò)分立，形成監(jiān)測黑洞，無法完成正常的監(jiān)測工作；針對以上各種不同的攻擊方式，一般可采用擴頻通信、sensor接入認證/鑒權(quán)、數(shù)據(jù)水銀和數(shù)據(jù)加密技術(shù)以提高網(wǎng)絡(luò)的平安性。根本思想有兩種:一種是從維護路由平安的角度出發(fā)，尋找盡可能平安的路由以保證網(wǎng)絡(luò)的平安。如果路由協(xié)議被破壞導致傳送的消息被篡改，那么對于應(yīng)用層上的數(shù)據(jù)包來說沒有任何的平安性可言。另一種是把著重點放在平安協(xié)議方面。定位問題WSN的定位機制與算法包括兩局部:節(jié)點自身定位和外部目標定位，前者是后者的根底。獲得節(jié)點位置的一個直接方法就是使用全球定位系統(tǒng)GPS，但該定位裝置價格昂貴而且在有遮擋的情況下使用效果不佳;對于精度不高的還可以采用LPS(LocalPositionSystem)。為每個節(jié)點都配備GPS定位裝置是一個高本錢的設(shè)計思想，是一個不現(xiàn)實的想法，因此一般采用GPS+絕對定位或相對定位來實現(xiàn)。數(shù)據(jù)管理從數(shù)據(jù)存儲的角度來看，無線傳感器網(wǎng)絡(luò)可被視為一種分布式數(shù)據(jù)庫。以數(shù)據(jù)庫的方法在無線傳感器網(wǎng)絡(luò)中進行數(shù)據(jù)管理，可以將存儲在網(wǎng)絡(luò)中的數(shù)據(jù)的邏輯視圖與網(wǎng)絡(luò)中的實現(xiàn)進行別離，使得無線傳感器網(wǎng)絡(luò)的用戶只需要關(guān)心數(shù)據(jù)查詢的邏輯結(jié)構(gòu)，無需關(guān)心實現(xiàn)細節(jié)。雖然對節(jié)點感知到的數(shù)據(jù)進行抽象在一定程度上影響執(zhí)行效率，但可以顯著增強傳感器網(wǎng)絡(luò)的易用性。美國加州大學伯克利分校的TinyDB系統(tǒng)和Comell大學的Cougar系統(tǒng)是目前具有代表性的傳感器網(wǎng)絡(luò)數(shù)據(jù)管理系統(tǒng)。傳感器網(wǎng)絡(luò)的數(shù)據(jù)管理與傳統(tǒng)的分布式數(shù)據(jù)庫有很大的差異。由于傳感器節(jié)點能量受限且容易失效，數(shù)據(jù)管理系統(tǒng)必須在盡量減少能量消耗的同時提供有效的數(shù)據(jù)效勞。同時，傳感器網(wǎng)絡(luò)中節(jié)點數(shù)量龐大，且傳感器節(jié)點產(chǎn)生的是無限的數(shù)據(jù)流，無法通過傳統(tǒng)的分布式數(shù)據(jù)庫的數(shù)據(jù)管理技術(shù)進行分析處理。此外，對傳感器網(wǎng)絡(luò)數(shù)據(jù)的查詢經(jīng)常是連續(xù)的查詢或隨機抽樣的查詢，這也使得傳統(tǒng)分布式數(shù)據(jù)庫的數(shù)據(jù)管理技術(shù)不適用于傳感器網(wǎng)絡(luò)。效勞質(zhì)量在某些應(yīng)用中，數(shù)據(jù)應(yīng)是剛感受到的一段時間內(nèi)，否那么數(shù)據(jù)將無用的。因此，范圍潛伏期為數(shù)據(jù)傳送是另一個條件，時間約束的應(yīng)用。然而，在許多應(yīng)用中，節(jié)約能源是直接關(guān)系到網(wǎng)絡(luò)的一生，被認為是相對來得重要數(shù)據(jù)的質(zhì)量發(fā)送。當能量耗盡之時，該網(wǎng)絡(luò)可能必須減少質(zhì)量，以減少節(jié)點能量損耗和從此延長整個網(wǎng)絡(luò)壽命。因此，路由協(xié)議能量是必須有這個必備的條件。嵌入式操作系統(tǒng)傳感器節(jié)點是一個微型的嵌入式系統(tǒng)，攜帶非常有限的硬件資源，需要操作系統(tǒng)能夠節(jié)能高效地使用其有限地內(nèi)存、處理器和通信模塊，且能夠?qū)Ω鞣N特定應(yīng)用提供最大的支持。在面向無線傳感器網(wǎng)絡(luò)的操作系統(tǒng)的支持下，多個應(yīng)用可以并發(fā)地使用系統(tǒng)的有限資源。傳感器節(jié)點有兩個突出的特點。一個特點是并發(fā)性密集，即可能存在多個需要同時執(zhí)行的邏輯控制，這需要操作系統(tǒng)有效地滿足這種發(fā)生頻繁、并發(fā)程度高、執(zhí)行過程比擬短的邏輯控制流程;另一個特點是傳感器節(jié)點模塊化程度很高，要求操作系統(tǒng)能夠讓應(yīng)用程序方便地對硬件進行控制。上述這些特點對設(shè)計面向無線傳感器網(wǎng)絡(luò)的操作系統(tǒng)提出了新的挑戰(zhàn)。3.WSN路由協(xié)議算法分析3.1WSN路由協(xié)議的分類方法WSNs路由協(xié)議負責在sink點和其余節(jié)點間可靠地傳輸數(shù)據(jù)。由于WSNs與應(yīng)用高度相關(guān)，單一的路由協(xié)議不能滿足各種應(yīng)用需求，因而人們研究了眾多的路由協(xié)議。為揭示協(xié)議特點，我們根據(jù)一些路由協(xié)議采用的通信模式、路由結(jié)構(gòu)、路由建立時機、狀態(tài)維護、節(jié)點標識和投遞方式等策略，運用多種分類方法對其進行了分類。由于研究人員組合多種策略來實現(xiàn)路由機制，故同一路由協(xié)議可分屬不同類別。根據(jù)傳輸過程中采用路徑的多少，可分為單路徑路由協(xié)議和多路徑路由協(xié)議。單路徑路由節(jié)約存儲空間,數(shù)據(jù)通信量少；多路徑路由容錯性強,健壯性好,且可從眾多路由中選擇一條最優(yōu)路由。根據(jù)節(jié)點在路由過程中是否有層次結(jié)構(gòu)、作用是否有差異，可分為平面路由協(xié)議和層次路由協(xié)議。平面路由簡單,健壯性好,但建立、維護路由的開銷大，數(shù)據(jù)傳輸跳數(shù)多，適合小規(guī)模網(wǎng)絡(luò)；層次路由擴展性好，適合大規(guī)模網(wǎng)絡(luò)，但簇的維護開銷大，且簇頭是路由的關(guān)鍵節(jié)點，其失效將導致路由失敗。根據(jù)路由建立時機與數(shù)據(jù)發(fā)送的關(guān)系，可分為主動路由協(xié)議、按需路由協(xié)議和混合路由協(xié)議。主動路由建立、維護路由的開銷大，資源要求高；按需路由在傳輸前需計算路由，時延大；混合路由那么綜合利用這兩種方式。根據(jù)是否以地理位置來標識目的地、路由計算中是否利用地理位置信息，可分為基于位置的路由協(xié)議和非基于位置的路由協(xié)議。有大量WSNs應(yīng)用需要知道突發(fā)事件的地理位置，這是基于位置的路由協(xié)議的應(yīng)用根底，但需要GPS定位系統(tǒng)或者其他定位方法協(xié)助節(jié)點計算位置信息。根據(jù)是否以數(shù)據(jù)來標識目的地，可分為基于數(shù)據(jù)的路由協(xié)議和非基于數(shù)據(jù)的路由協(xié)議。有大量WSNs應(yīng)用要求查詢或上報具有某種類型的數(shù)據(jù)，這是基于數(shù)據(jù)的路由協(xié)議的應(yīng)用根底，但需要分類機制對數(shù)據(jù)類型進行命名。根據(jù)節(jié)點是否編址、是否以地址標識目的地，可分為基于地址的路由協(xié)議和非基于地址的路由協(xié)議。基于地址的路由在傳統(tǒng)路由協(xié)議中較常見，,而在WSNs中一般不單獨使用而與其他策略結(jié)合使用。根據(jù)路由選擇是否考慮QoS約束，可分為保證QoS的路由協(xié)議和不保證QoS的路由協(xié)議。保證QoS的路由協(xié)議是指在路由建立時，考慮時延、丟包率等QoS參數(shù)，從眾多可行路由中選擇一條最適合QoS應(yīng)用要求的路由。根據(jù)數(shù)據(jù)在傳輸過程中是否進行聚合處理，可分為數(shù)據(jù)聚合的路由協(xié)議和非數(shù)據(jù)聚合的路由協(xié)議。數(shù)據(jù)聚合能減少通信量，但需要時間同步技術(shù)的支持，并使傳輸時延增加。根據(jù)路由是否由源節(jié)點指定，可分為源站路由協(xié)議和非源站路由協(xié)議。源站路由協(xié)議節(jié)點無須建立、維護路由信息，從而節(jié)約存儲空間，減少通信開銷。但如果網(wǎng)絡(luò)規(guī)模較大，數(shù)據(jù)包頭的路由信息開銷也大，而且如果網(wǎng)絡(luò)拓撲變化頻繁，將導致路由失敗。根據(jù)路由建立時機是否與查詢有關(guān)，可分為查詢驅(qū)動的路由協(xié)議和非查詢驅(qū)動的路由協(xié)議。查詢驅(qū)動的路由協(xié)議能夠節(jié)約節(jié)點存儲空間，但數(shù)據(jù)時延較大，且不適合環(huán)境監(jiān)測等需緊急上報的應(yīng)用。3.2幾種典型路由協(xié)議的分析3.2.1平面路由協(xié)議平面路由協(xié)議主要特點有：所需的信息域較小，一般僅需一跳〔1hop〕內(nèi)的信息；無需進行周期性的路由信息維護；復(fù)雜度較低。Flooding泛洪是一種傳統(tǒng)的路由技術(shù)，不要求維護網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，并進行路由計算，接收到消息的節(jié)點以播送形式轉(zhuǎn)發(fā)分組。對于自組織的傳感器網(wǎng)絡(luò)，泛洪路由是一種較直接的實現(xiàn)方法，但消息的“內(nèi)爆”(implosion)和“重疊”(overlap)是其固有的缺陷。為了克服這些缺陷，S.hedetniemi等人提出了Gossiping策略，節(jié)點隨機選取一個相鄰節(jié)點轉(zhuǎn)發(fā)它接收到的分組，而不是采用播送形式。這種方法防止了消息的“內(nèi)爆”現(xiàn)象，但有可能增加端到端的傳輸延時。圖3.1Flooding路由協(xié)議中的內(nèi)爆和重疊問題SPIN(sensorprotocolforinformationvianegotiation)SPIN是以數(shù)據(jù)為中心的自適應(yīng)路由協(xié)議，通過協(xié)商機制來解決泛洪算法中的“內(nèi)爆”和“重疊”問題。傳感器節(jié)點僅播送采集數(shù)據(jù)的描述信息，當有相應(yīng)的請求時，才有目的地發(fā)送數(shù)據(jù)信息。SPIN協(xié)議中有3種類型的消息，即ADV，REQ和DATA。ADV—用于新數(shù)據(jù)播送。當一個節(jié)點有數(shù)據(jù)可共享時，它以播送方式向外發(fā)送DATA數(shù)據(jù)包中的元數(shù)據(jù)。REQ—用于請求發(fā)送數(shù)據(jù)。當一個節(jié)點希望接收DATA數(shù)據(jù)包時，發(fā)送REQ數(shù)據(jù)包。DATA—包含附上元數(shù)據(jù)頭(meta一header)的實際數(shù)據(jù)包。SPIN協(xié)議有4種不同的形式:?SPIN-PP：采用點到點的通信模式，并假定兩節(jié)點間的通信不受其他節(jié)點的干擾，分組不會喪失，功率沒有任何限制。要發(fā)送數(shù)據(jù)的節(jié)點通過ADV向它的相鄰節(jié)點播送消息，感興趣的節(jié)點通過REQ發(fā)送請求，數(shù)據(jù)源向請求者發(fā)送數(shù)據(jù)。接收到數(shù)據(jù)的節(jié)點再向它的相鄰節(jié)點播送ADV消息，如此重復(fù)，使所有節(jié)點都有時機接收到任何數(shù)據(jù)。?SPIN-EC：在SPIN-PP的根底上考慮了節(jié)點的功耗，只有能夠順利完成所有任務(wù)且能量不低于設(shè)定閾值的節(jié)點才可參與數(shù)據(jù)交換。?SPIN-BC：設(shè)計了播送信道，使所有在有效半徑內(nèi)的節(jié)點可以同時完成數(shù)據(jù)交換。為了防止產(chǎn)生重復(fù)的REQ請求，節(jié)點在聽到ADV消息以后，設(shè)定一個隨機定時器來控制REQ請求的發(fā)送，其他節(jié)點聽到該請求，主動放棄請求權(quán)利。?SPIN-RL：它是對SPIN-BC的完善，主要考慮如何恢復(fù)無線鏈路引入的分組過失與喪失。記錄ADV消息的相關(guān)狀態(tài)，如果在確定時間間隔內(nèi)接收不到請求數(shù)據(jù)，那么發(fā)送重傳請求，重傳請求的次數(shù)有一定的限制。圖3.2說明了SPIN協(xié)議的路由建立與數(shù)據(jù)傳送。圖3.2SPIN協(xié)議的路由建立與數(shù)據(jù)傳送基于數(shù)據(jù)描述的協(xié)商機制和能量自適應(yīng)機制的SP創(chuàng)協(xié)議能夠很好地解決傳統(tǒng)的Flooding協(xié)議所帶來的信息爆炸、信息重復(fù)和資源浪費等問題。此外，由于協(xié)議中每個節(jié)點只需知道其單跳鄰居節(jié)點的信息，拓撲改變呈現(xiàn)本地化特征。SP州協(xié)議的缺點是數(shù)據(jù)廣告機制不能保證數(shù)據(jù)的可靠傳遞，如果對數(shù)據(jù)感興趣的節(jié)點遠離源節(jié)點或者在源節(jié)點和目的節(jié)點中間的節(jié)點對數(shù)據(jù)不感興趣，那么數(shù)據(jù)就不可能被傳遞到目的地。因此，對于入侵發(fā)現(xiàn)等需要在定期間隔內(nèi)可靠傳遞數(shù)據(jù)的應(yīng)用系統(tǒng)來說，SP州并不是一個很好的選擇。SAR(sequentialassignmentrouting)在選擇路徑時，有序分配路由(SAR)策略充分考慮了功耗、QoS和分組優(yōu)先權(quán)等特殊要求，采用局部路徑恢復(fù)和多路經(jīng)備份策略，防止節(jié)點或鏈路失敗時進行路由重計算需要的過量計算開銷。為了在每個節(jié)點與sink節(jié)點間生成多條路經(jīng)，需要維護多個樹結(jié)構(gòu)，每個樹以落在sink節(jié)點有效傳輸半徑內(nèi)的節(jié)點為根向外生長，枝干的選擇需滿足一定QOS要求并要有一定的能量儲藏。這一處理使大多數(shù)傳感器節(jié)點可能同時屬于多個樹，可任選其一將采集數(shù)據(jù)回傳到sink節(jié)點。定向擴散(directeddiffusion)DD是以數(shù)據(jù)為中心的路由協(xié)議開展過程的里程碑，其突出特點是引入了梯度來描述網(wǎng)絡(luò)中間節(jié)點對該方向繼續(xù)搜索獲得匹配數(shù)據(jù)的可能性。這是一個重要的基于數(shù)據(jù)的、查詢驅(qū)動的路由協(xié)議。該協(xié)議用屬性/值對命名數(shù)據(jù)。為建立路由，sink點flooding包含屬性列表、上報間隔、持續(xù)時間、地理區(qū)域等信息的查詢請求Interest(該過程本質(zhì)上是設(shè)置一個監(jiān)測任務(wù))。沿途節(jié)點按需對各Interest進行緩存與合并，并根據(jù)Interest計算、創(chuàng)立包含數(shù)據(jù)上報率、下一跳等信息的梯度(gradient),從而建立多條指向sink點的路徑。Interest中的地理區(qū)域內(nèi)節(jié)點那么按要求啟動監(jiān)測任務(wù)，并周期性地上報數(shù)據(jù)，途中各節(jié)點可對數(shù)據(jù)進行緩存與聚合。sink點可在數(shù)據(jù)傳輸過程中通過對某條路徑發(fā)送上報間隔更小或更大的Interest，以增強或減弱數(shù)據(jù)上報率。該協(xié)議采用多路徑，健壯性好；使用數(shù)據(jù)聚合能減少數(shù)據(jù)通信量；sink點根據(jù)實際情況采取增強或減弱方式能有效利用能量；使用查詢驅(qū)動機制按需建立路由，防止了保存全網(wǎng)信息，但不適合環(huán)境監(jiān)測等應(yīng)用。而且，Gradient的建立開銷很大，不適合多sink點網(wǎng)絡(luò)；數(shù)據(jù)聚合過程采用時間同步技術(shù)，會帶來較大開銷和時延。圖3.3描述了定向擴散模型的工作原理。圖3.3定向擴散模型的工作原理DD路由是一種經(jīng)典的以數(shù)據(jù)為中心的路由機制。Sink節(jié)點根據(jù)不同的應(yīng)用需求定義不同的任務(wù)類型、目標區(qū)域等參數(shù)的興趣消息，通過向網(wǎng)絡(luò)中播送興趣消息啟動路由建立過程。中間傳感器節(jié)點通過興趣表建立從數(shù)據(jù)源到Sink節(jié)點的數(shù)據(jù)傳輸梯度，自動形成數(shù)據(jù)傳輸?shù)亩鄺l路徑。DD采用相鄰節(jié)點間通信的方式來防止維護全局拓撲，采用查詢驅(qū)動數(shù)據(jù)傳送模式和局部數(shù)據(jù)聚集而減少網(wǎng)絡(luò)數(shù)據(jù)流，因此是一種高能源有效性的協(xié)議。它的缺點是，在需要連續(xù)數(shù)據(jù)傳送的應(yīng)用中(環(huán)境監(jiān)測等)不能很好的應(yīng)用；數(shù)據(jù)命名只能針對于特定的應(yīng)用預(yù)先進行；初始查詢的擴散開銷大?；谧钚〈鷥r場的路由算法：算法開始之前，所有的節(jié)點都將自己的代價設(shè)為無窮大。網(wǎng)關(guān)播送一個代價為0的廣告報文，其他節(jié)點接收到廣告報文后，如果報文中所表示的代價小于節(jié)點自己的代價，那么使用這個新的代價作為自己的代價，并將新的代價播送出去；反之，那么丟棄該信息。最終每個節(jié)點都獲得了自己距離網(wǎng)關(guān)的最小代價，由此建立代價場，報文沿著最小代價路徑向網(wǎng)關(guān)發(fā)送。當報文被發(fā)送的時候它將附帶源節(jié)點的最小代價，及從源節(jié)點到當前節(jié)點所消耗的代價，一個鄰居節(jié)點接收到報文，只有該報文已消耗的代價和自己的代價之和等于源節(jié)點代價的時候，才轉(zhuǎn)發(fā)這個報文。采用這種方法，節(jié)點不需要維持任何的路徑信息，就可以實現(xiàn)報文的最短路徑發(fā)送。3.2.2分層路由協(xié)議在層次路由協(xié)議中，網(wǎng)絡(luò)通常被劃分為簇〔cluster〕，每個簇由一個簇頭〔cluster-head〕和多個簇成員〔cluster-member〕組成，低一級網(wǎng)絡(luò)的簇頭是高一級網(wǎng)絡(luò)中的簇成員。在這種分級結(jié)構(gòu)中，簇頭不僅負責簇內(nèi)信息的收集和融合處理，還負責簇間數(shù)據(jù)轉(zhuǎn)發(fā)。層次路由協(xié)議中簇的形成通常是基于節(jié)點的能量和其與簇頭間的距離。為了延長整個網(wǎng)絡(luò)的生存期，簇頭節(jié)點需要周期更新。層次路由的優(yōu)點是便于管理，可以對系統(tǒng)變化做出快速反響，能夠提供高質(zhì)量的通信效勞，能量利用率較高。但簇的維護開銷較大。LEACH(lowenergyadaptiveclusteringhierarchy)LEACH是MIT的Chandrakasan等人為無線傳感器網(wǎng)絡(luò)設(shè)計的低功耗自適應(yīng)聚類路由算法。與一般的平面多跳路由協(xié)議和靜態(tài)聚類算法相比,LEACH可以將網(wǎng)絡(luò)生命周期延長15%,主要通過隨機選擇聚類首領(lǐng),平均分擔中繼通信業(yè)務(wù)來實現(xiàn)。LEACH定義了“輪”(round)的概念,一輪由初始化和穩(wěn)定工作兩個階段組成。為了防止額外的處理開銷,穩(wěn)定態(tài)一般持續(xù)相對較長的時間。如圖3.4所示：初始化階段初始化階段穩(wěn)定工作階段時間圖3.4LEACH協(xié)議的時序圖在初始化階段,聚類首領(lǐng)是通過下面的機制產(chǎn)生的。傳感器節(jié)點生成0,1之間的隨機數(shù),如果大于閾值T,那么選該節(jié)點為聚類首領(lǐng).T的計算方法如下:〔3.1〕其中p為節(jié)點中成為聚類首領(lǐng)的百分數(shù),r是當前的輪數(shù)。當簇頭選定之后，簇頭節(jié)點主動向網(wǎng)絡(luò)中節(jié)點播送自己成為簇頭的消息(ADV_CH)。接收到此消息的節(jié)點，依據(jù)接收信號的強度，選擇它所要參加的簇，并發(fā)消息通知相應(yīng)的簇頭(JOIN_REQ)?；跁r分多址(TimeDivisionMultipleAddress，簡稱TDMA)的方式，簇頭節(jié)點為其中的每個成員分配通信時隙，并以播送的形式通知所有的簇內(nèi)節(jié)點(ADVSCH)。這樣保證了簇內(nèi)每個節(jié)點在指定的傳輸時隙進行數(shù)據(jù)傳輸，而在其他時間進入休眠狀態(tài)，減少了能量消耗。在穩(wěn)定工作階段，節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，在自身傳輸時隙到來時把監(jiān)測數(shù)據(jù)傳給簇頭節(jié)點(DATA)，如圖3.5所示。簇頭節(jié)點對接收到數(shù)據(jù)進行融合處理之后，發(fā)送到Sink節(jié)點，這是一種減小通信業(yè)務(wù)量的合理工作模式。持續(xù)一段時間以后，整個網(wǎng)絡(luò)進入下一輪工作周期，重新選擇簇頭節(jié)點。圖3.5LEACH協(xié)議LEACH協(xié)議采用動態(tài)轉(zhuǎn)換簇頭的方法來平均網(wǎng)絡(luò)節(jié)點的能量消耗，使因能量耗盡而失效的節(jié)點呈隨機分布狀態(tài)，因而與一般的多跳路由協(xié)議和靜態(tài)簇算法相比，LEACH可以將網(wǎng)絡(luò)生命周期延長15%。但是LEACH協(xié)議在每輪固定簇頭節(jié)點后在劃分簇的過程中，簇頭節(jié)點開銷較大。并且簇頭節(jié)點的選擇無法到達最優(yōu)，有可能簇頭節(jié)點位于網(wǎng)絡(luò)的邊緣或者幾個簇頭節(jié)點相鄰，某些節(jié)點不得不傳輸較遠的距離來與簇頭通信，這就導致了大量能量消耗。而且LEACH協(xié)議所有簇頭節(jié)點直接與Sink節(jié)點通信，采用連續(xù)數(shù)據(jù)發(fā)送模式和單跳路徑選擇模式，使得每輪中簇頭節(jié)點能耗巨大，因此不適合在大規(guī)模的傳感器網(wǎng)絡(luò)中應(yīng)用。TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)依照應(yīng)用模式的不同，通常可以簡單地將無線自組織網(wǎng)絡(luò)(包括傳感器網(wǎng)絡(luò)和Ad-hoc網(wǎng)絡(luò))分為主動(proactive)和響應(yīng)(reactive)兩種類型。主動型傳感器網(wǎng)絡(luò)持續(xù)監(jiān)測周圍的物質(zhì)現(xiàn)象，并以恒定速率發(fā)送監(jiān)測數(shù)據(jù)；而響應(yīng)型傳感器網(wǎng)絡(luò)只是在被觀測變量發(fā)生突變時才傳送數(shù)據(jù)。相比之下,響應(yīng)型傳感器網(wǎng)絡(luò)更適合應(yīng)用在敏感時間的應(yīng)用中。TEEN和LEACH的實現(xiàn)機制非常相似,只是前者是響應(yīng)型的，而后者屬于主動型傳感器網(wǎng)絡(luò)。在TEEN中定義了硬、軟兩個門限值，以確定是否需要發(fā)送監(jiān)測數(shù)據(jù)。當監(jiān)測數(shù)據(jù)第一次超過設(shè)定的硬門限時,節(jié)點用它作為新的硬門限,并在接著到來的時隙內(nèi)發(fā)送它。在接下來的過程中，如果監(jiān)測數(shù)據(jù)的變化幅度大于軟門限界定的范圍，那么節(jié)點傳送最新采集的數(shù)據(jù)，并將它設(shè)定為新的硬門限。通過調(diào)節(jié)軟門限值的大小，可以在監(jiān)測精度和系統(tǒng)能耗之間取得合理的平衡。圖3.6表示的是TEEN協(xié)議中由聚簇構(gòu)成的層次結(jié)構(gòu)。SinkSinkHighlevelclusterheadClusteringNormalsensornodeLowlevelclusterhead圖3.6TEEN協(xié)議中由聚簇構(gòu)成的層次結(jié)構(gòu)TENE適用于實時性要求較高的應(yīng)用場合，比方入侵警報，爆炸預(yù)警等，用戶可以及時獲取感興趣的信息。而且用戶可以通過設(shè)置不同的軟門限方便地平衡監(jiān)測的準確性與系統(tǒng)節(jié)能性兩項指標。但是這個方案也有一些缺乏之處，例如門限值達不到，節(jié)點就永遠不會和簇頭節(jié)點通信，用戶就無法從網(wǎng)絡(luò)得到任何數(shù)據(jù);沒有相應(yīng)的機制去區(qū)分那些沒有感應(yīng)到足夠大變化的節(jié)點和處于關(guān)閉狀態(tài)的節(jié)點，所以TEEN協(xié)議不適合應(yīng)用在。PEGAGIS(power-efficientgatheringinsensorinformationsystem)PEGASIS由LEACH開展而來。它假定組成網(wǎng)絡(luò)的傳感器節(jié)點是同構(gòu)且靜止的。節(jié)點發(fā)送能量遞減的測試信號，通過檢測應(yīng)答來確定離自己最近的相鄰節(jié)點。在收集數(shù)據(jù)前，首先利用貪心算法將網(wǎng)絡(luò)中的所有節(jié)點連接成一條單鏈。通過這種方式，網(wǎng)絡(luò)中的所有節(jié)點能夠了解彼此的位置關(guān)系，進而每個節(jié)點依據(jù)自己的位置選擇所屬的聚類，聚類的首領(lǐng)向鏈的兩端發(fā)出收集數(shù)據(jù)的請求，數(shù)據(jù)從單鏈的兩個端點向首領(lǐng)流動。中間節(jié)點在傳遞數(shù)據(jù)前要執(zhí)行融合操作，最終由首領(lǐng)節(jié)點將結(jié)果數(shù)據(jù)傳送給Sink節(jié)點。因為PEGASIS中每個節(jié)點都以最小功率發(fā)送數(shù)據(jù)分組，并有條件完成必要的數(shù)據(jù)融合，減小業(yè)務(wù)流量。因此,整個網(wǎng)絡(luò)的功耗較小。研究結(jié)果說明，PEGASIS支持的傳感器網(wǎng)絡(luò)的生命周期是LEACH的近兩倍。SinkSink0123456圖3.7PEGAGIS的單鏈結(jié)構(gòu)單鏈結(jié)構(gòu)的PEGASSI算法主要有以下兩點缺陷:第一點是平均延遲較大:數(shù)據(jù)需要沿著單鏈結(jié)構(gòu)順序傳送，收集數(shù)據(jù)的延遲決定于首領(lǐng)節(jié)點與單鏈端節(jié)點的距離，因此平均延遲與節(jié)點數(shù)成正比；第二點是魯棒性較差:由于傳感器節(jié)點的易失效性，如果不采取適當?shù)男迯?fù)策略，單鏈結(jié)構(gòu)的傳輸路徑容易增大數(shù)據(jù)收集請求的失敗率。多層聚類算法多層聚類算法是Estrin為傳感器網(wǎng)絡(luò)設(shè)計的一種新的聚類實現(xiàn)機制。工作在網(wǎng)絡(luò)中的傳感器節(jié)點處于不同的層，所處層次越高，所覆蓋面積越大。起初，所有節(jié)點均在最低層，通過競爭獲得提升高層的時機。新的工作周期開始時，每一個節(jié)點都播送自己的狀態(tài)信息，包括儲藏能量、所在層次和首領(lǐng)的ID(如果有)等，然后進入等待狀態(tài)以便相互了解信息，等待時間與所在層次成正比。處在最低層的節(jié)點如果沒有首領(lǐng)，等待狀態(tài)結(jié)束后，立刻啟動一個“晉升定時器”，定時時間與自身能量以及接收到同層其他節(jié)點播送消息的數(shù)目成反比，目的是為能量較高且在密集區(qū)的節(jié)點獲得較多的提升時機。一旦定時時間到，節(jié)點升入高層，將有發(fā)給自己播送消息的節(jié)點視為潛在的子節(jié)點，并播送自己新的狀態(tài)信息，低層節(jié)點選擇響應(yīng)這些準首領(lǐng)的播送消息，最終確定惟一的通信關(guān)系。選擇了首領(lǐng)的節(jié)點，自己的“晉升定時器”將停止工作，也就意味著本輪放棄了晉升時機。在每一個工作周期結(jié)束以后，高層節(jié)點將視自己的狀態(tài)信息(如有無子節(jié)點，功率是否充足)決定是否讓出首領(lǐng)位置。上述的多層聚類算法具有遞歸性，Estrin等人用兩層模型驗證了它在傳感器網(wǎng)絡(luò)中的有效性。Younis等人提出了基于三層體系結(jié)構(gòu)的路由協(xié)議。與LEACH不同的是，該協(xié)議要求在網(wǎng)絡(luò)運行前由終端用戶將傳感器節(jié)點劃分成簇，并通知每個簇頭節(jié)點的ID標識和簇內(nèi)所分配節(jié)點的位置信息。簇內(nèi)節(jié)點可以以感知、轉(zhuǎn)發(fā)、感知并轉(zhuǎn)發(fā)、休眠這四種方式之一存在。簇頭不受能量的限制，它可以監(jiān)控節(jié)點的能量變化，決定并維護傳感器的四種狀態(tài)，并利用代價函數(shù)作為鏈路本錢，選擇最小本錢的路徑作為節(jié)點與其通信的最優(yōu)路徑。表3.1幾種常見平面路由協(xié)議比擬名稱主要思想Flooding收到數(shù)據(jù)的節(jié)點向所有鄰居節(jié)點播送報文Gossiping收到的數(shù)據(jù)節(jié)點隨機選取地選擇一個鄰節(jié)點轉(zhuǎn)發(fā)報文SAR依據(jù)每條路徑上的能量資源和QoS要求來決策路由SPIN根據(jù)臨時的請求、應(yīng)答的方式轉(zhuǎn)發(fā)數(shù)據(jù)DD在所有節(jié)點中為Sink的請求建立一個臨時的“梯度”場；匹配數(shù)據(jù)沿“梯度”最大的方向中繼回Sink基于最小代價場的路由算法每個節(jié)點獲得了自己距離網(wǎng)關(guān)的最小代價后建立代價場，報文沿最小代價路徑向網(wǎng)關(guān)發(fā)送表3.2幾種常見分層路由協(xié)議的比擬MAC協(xié)議描述SMACS固定時隙收發(fā)數(shù)據(jù)，并在空閑時將節(jié)點轉(zhuǎn)入休眠狀態(tài)以減小能耗基于CSMA的介質(zhì)基于競爭機制隨機接入，通過調(diào)整相位防止沖突重復(fù)發(fā)生TDMA/FDMA組合方案選擇適宜數(shù)量的信道，在相應(yīng)中心頻率信道內(nèi)時分復(fù)用Flooding路由協(xié)議的分析與研究泛洪(Flooding)路由算法是一種經(jīng)典的路由算法，由于其具有實現(xiàn)簡單，容錯能力強等特點，無論在有線網(wǎng)絡(luò)中還是在無線網(wǎng)絡(luò)中都得到了廣泛的應(yīng)用。由于實現(xiàn)簡單，泛洪算法在傳感器網(wǎng)絡(luò)中也得到了廣泛應(yīng)用。但是泛洪算法能耗過大的缺點又在相當程度上抵消了其優(yōu)勢，使其不適合直接地應(yīng)用于無線傳感器網(wǎng)絡(luò)。如果將泛洪作為一種路由算法應(yīng)用于傳感器網(wǎng)絡(luò)，需要解決其能耗過大、數(shù)據(jù)冗余量高問題。如DD、SPIN、Gossiping等算法都是Flooding的改良算法。4.1泛洪算法模型在泛洪算法中，任一節(jié)點ni接收到報文的動作可用如下偽代碼描述。每個報文都包含TTL〔報文存活時間〕、DATA〔數(shù)據(jù)〕等內(nèi)容。算法根本步驟如下：Step1：Sink和其他節(jié)點播送自己的位置信息和序列號；Step2：源節(jié)點播送報文；Step3：假設(shè)收到報文的節(jié)點為Sink那么報文已傳送到目的地；否那么轉(zhuǎn)Step4；Step4：假設(shè)報文的TTL－1＝0或節(jié)點已收到過該報文，那么轉(zhuǎn)Step5，否那么轉(zhuǎn)Step6；Step5：節(jié)點丟棄該報文；Step6：節(jié)點將報文轉(zhuǎn)發(fā)給它所有的鄰居節(jié)點。報文中的TTL字段，通常用來防止報文在網(wǎng)絡(luò)內(nèi)被無限制的轉(zhuǎn)發(fā)，在洪泛的工作模式下，網(wǎng)絡(luò)中有節(jié)點要發(fā)送報文時，它將把報文發(fā)送給所有的鄰居節(jié)點；而收到報文的節(jié)點那么將報文轉(zhuǎn)發(fā)給自己所有的鄰居節(jié)點，除非TTL－1＝0或接收節(jié)點本身就是聚集點。其中TTL通常表示跳數(shù)或時間，當TTL－1＝0時，報文將被丟棄。傳感器網(wǎng)絡(luò)中基于自適應(yīng)的路由算法研究。4.2算法流程圖SinkSink和其他節(jié)點播送自己的位置信息和序列號源節(jié)點播送報文節(jié)點已收到過該報文丟棄該報文收到報文的節(jié)點為Sink報文的TTL－1＝0？將數(shù)據(jù)包交高層處理并失去對該數(shù)據(jù)包的轉(zhuǎn)發(fā)權(quán)否是否否是丟棄該報文是開始圖4.1泛洪算法流程圖4.3基于延遲的自適應(yīng)泛洪路由算法在整個網(wǎng)絡(luò)內(nèi)進行泛洪時，因為每個節(jié)點無論是否在最終的轉(zhuǎn)發(fā)路徑上，都要轉(zhuǎn)發(fā)報文，這使網(wǎng)絡(luò)中充滿了大量的無用報文，浪費了許多資源，節(jié)點的能量也消耗很快。為了解決泛洪模型的缺陷，本章提出了一種基于延遲的自適應(yīng)泛洪模型，算法的主要思想是初始化階段后，源節(jié)點先在全網(wǎng)內(nèi)用較小的路由請求報文(RoutingRequestPackets，RREQ)和路由回復(fù)報文(RoutingReplyPackets，RREP)來建立路由，在建立路由的過程中當有節(jié)點收到RREQ時，假設(shè)它比上一跳節(jié)點離Sink更遠或該報文的TTL－1＝0那么它不轉(zhuǎn)發(fā)RREQ并丟棄該報文；否那么，節(jié)點先根據(jù)網(wǎng)絡(luò)的實際情況等待一段時間看是否有更優(yōu)的來自同一Source的RREQ，假設(shè)有那么轉(zhuǎn)發(fā)更優(yōu)的RREQ直到Sink。Sink接收到RREQ后向最優(yōu)路回復(fù)RREP。而后源節(jié)點將沿著建立好的路徑轉(zhuǎn)發(fā)較大的數(shù)據(jù)報文。新算法可以分為初始化、路由建立和數(shù)據(jù)傳輸階段。其中，路由建立階段主要是找到一條較優(yōu)的從源節(jié)點到目的節(jié)點的路徑，而數(shù)據(jù)傳輸階段那么依據(jù)路由建立階段建立的路徑傳輸數(shù)據(jù)報文。4.3.1算法中用到的報文和數(shù)據(jù)各階段中用到的報文和各節(jié)點需要維護的表格分別如表4.1、4.3所示：表4.1flooding報文表報文名稱報文中包含的域長度〔bit〕NIP：NeighborsInformationPacket(節(jié)點信息報文)PT＝0,POS,SN21RRE：RoutingRequestPacket(路由請求報文)PT＝1,SNL,POSS,E,TTL≥24RREP：RoutingReplyPacket(路由回復(fù)報文)PT＝2,SNL,POSS,TTL≥16DP：DataPacket〔數(shù)據(jù)報文〕PT＝3,SNL,Data2000RR：Rerouting(重建路由報文)PT＝5,SN11表4.2對flooding報文及表格中各數(shù)據(jù)域的說明域名注解長度〔bit〕PTPacketType，報文類型，PT＝0..5分別表示NIP、RREQ、RREP和DP、RR五種中不同的報文3SNSerialNumber，節(jié)點序列號8POSSPosition，位置信息，其中POSS表示源節(jié)點位置信息10EEnergy，記錄報文傳送到目前為止所消耗的能量8TTLTime-to-live，報文存活時間3SNLSSerialNumbersList序列號表，將報文經(jīng)過的節(jié)點序列號都依次列出來=報文經(jīng)過的節(jié)點數(shù)×8Data數(shù)據(jù)，數(shù)據(jù)報文一律統(tǒng)一為2000bit－Type節(jié)點類型，TYPE=0,1分別表示存活(Alive，默認值)或死亡1表4.3flooding中各節(jié)點需要維護的表格表格名稱表格中包含的域NIT：NeighborsInformationTable(鄰居信息表)POS，SN，TypeRQT：RREQTable(RREQ表)SNL，POSSRPT：RREPTable(RREP表)SNL，POSSSFD算法描述算法包括以下三個階段：初始化階段〔InitializationPhase，InP〕、路由建立階段〔RoutingBuildingPhase，RBP〕和數(shù)據(jù)傳輸階段〔DataForwardingPhase，DFP〕。1、初始化階段〔InitializationPhase，InP〕Step1：各節(jié)點播送節(jié)點信息報文NIP；Step2：收到NIP報文的節(jié)點將相關(guān)信息存儲到鄰居信息表NIT中。2、路由建立階段〔RoutingBuildingPhase，RBP〕Step1：Source查找RPT表，假設(shè)它是某個RREP報文SNL中的一個節(jié)點，那么它直接沿該RREP確定的路徑轉(zhuǎn)發(fā)DP，否那么播送一個新的RREQ；Step2：節(jié)點ni接收到RREQ后查找RPT表，假設(shè)它是某個RREP報文SNL中的一個節(jié)點，那么它直接沿該RREP確定的路徑向它的上一跳節(jié)點回復(fù)RREP，否那么：StepI：假設(shè)報文的TTL－1＝0，或ni的剩余能量已不夠轉(zhuǎn)發(fā)一個DP，那么轉(zhuǎn)StepIV，否那么轉(zhuǎn)StepII；StepII：ni分別計算ni和該RREQ上一跳節(jié)點與Sink之間的距離，假設(shè)ni較上一跳離Sink更近，那么轉(zhuǎn)StepIII，否那么轉(zhuǎn)StepIV；StepIII：ni等待Δt時間，假設(shè)來自同源節(jié)點有轉(zhuǎn)發(fā)能耗更小的RREQ，那么將到目前為止收到的來自同一源節(jié)點的RREQ中能耗最小的那個報文轉(zhuǎn)發(fā)，直到RREQ到達Sink；StepIV：ni丟棄該報文。Step3：Sink收到RREQ后，沿能耗最小的那些RREQ確定的路徑回復(fù)RREP，直到RREP到達指定的Source。3、數(shù)據(jù)轉(zhuǎn)發(fā)階段〔DataForwardingPhase，DFP〕Step1：Source收到RREP后沿該RREP指定的路徑向Sink發(fā)送數(shù)據(jù)報文。Step2：當ni剩余能耗不夠轉(zhuǎn)發(fā)DP時，那么其播送RR報文，收到該報文的節(jié)點在其NIT中將ni狀態(tài)改為Dead。假設(shè)ni是目前正在使用的到Sink的路徑中的一個節(jié)點，那么其在該路徑中的鄰居節(jié)點向自己在路徑中的上一跳節(jié)點發(fā)送RR報文，并將RPT表中對應(yīng)的RREP信息刪除，直到RR報文到達該路徑的起點。當Source收到RR后，轉(zhuǎn)2。〔RR報文中記錄了ni的序列號〕傳感器網(wǎng)絡(luò)中基于自適應(yīng)的路由算法研究4.3.3性能比擬尺度為了更好的比擬各路由算法的優(yōu)缺點，本文定義了如下一些尺度來具體地衡量算法性能。本文在后面幾章中進行算法的性能評價時，仍然使用這些指標。(1)時間復(fù)雜度〔TimeComplexity，TC〕：算法實現(xiàn)時所消耗的時間量級。(2)消息域〔MessageField，MF〕：算法實現(xiàn)時所需要的信息范圍。(3)網(wǎng)絡(luò)檢測到的事件總數(shù)〔即從Source傳送到Sink的數(shù)據(jù)報文總數(shù)，TotalDetectedEvents，TDE〕：反映了系統(tǒng)的吞吐量。(4)傳送一個事件的平均能耗(AverageEnergyExpenditureperEvent，AEE)：。(5)第一個死亡節(jié)點出現(xiàn)的輪次與總輪次的百分比〔AppearanceRateoftheroundwhichthefirstnodedead，ARR〕。理論分析由4.3節(jié)對SFD的描述可知SFD具有以下性質(zhì)：性質(zhì)1.SFD的時間復(fù)雜度TC和消息域MF與Flooding相同。說明：Flooding和SFD中每個節(jié)點的動作只需要一個循環(huán)即可完全描述，因此，它們的TC均為O(n)。二者都滿足分布式特性=>二者均只需一跳信息，即二者消息域相同，均為1hop。綜上所述，新算法的時間復(fù)雜度和洪泛算法一致，同時保持了洪泛算法可以分布式實現(xiàn)的優(yōu)點。性質(zhì)2.SFD較Flooding節(jié)能。說明：SFD的能量由初始化、路由建立階段和數(shù)據(jù)傳輸階段三局部構(gòu)成，F(xiàn)looding的能耗由初始化和數(shù)據(jù)傳輸階段兩局部構(gòu)成。易知二者在初始化階段的能耗是相同的。在SFD的路由建立階段，RREQ報文沿多路徑轉(zhuǎn)發(fā)給Sink，每次轉(zhuǎn)發(fā)后，接收的節(jié)點除了根據(jù)報文自帶的TTL外還會根據(jù)自己的位置信息判斷是否丟棄該報文。如果報文的TTL－1≠0且節(jié)點較上一跳離Sink更近，那么節(jié)點等待Δt時間看是否有更優(yōu)的RREQ到來。以此來轉(zhuǎn)發(fā)較優(yōu)的RREQ。因為多跳可能優(yōu)于少跳，故節(jié)點等待Δt時間是很必要的，有利于減少報文的轉(zhuǎn)發(fā)量，并有利于找到更優(yōu)的路徑。當RREQ到達Sink后，Sink將沿它的反路徑傳送RREP報文直到Source?？梢?，路由建立階段，節(jié)點是有選擇的重傳，網(wǎng)絡(luò)中報文的冗余量并不大，且越接近Sink，轉(zhuǎn)發(fā)報文的節(jié)點越少。雖然，F(xiàn)looding沒有路由建立階段，但它在數(shù)據(jù)傳輸階段毫無目的的轉(zhuǎn)發(fā)數(shù)據(jù)報文。網(wǎng)絡(luò)中數(shù)據(jù)的冗余量很大。而在數(shù)據(jù)傳輸階段，SFD根據(jù)路由建立階段建立的路由轉(zhuǎn)發(fā)報文。故SFD報文轉(zhuǎn)發(fā)的目的性很強。同時，RREQ和RREP報文的位數(shù)都較小，在整個傳輸過程中能耗較小。故SFD較Flooding節(jié)能。分析：Δt確實定〔Δt為節(jié)點等待能耗更小的RREQ的等待時間〕說明：假設(shè)時隙等長，數(shù)據(jù)包正好能在一時隙內(nèi)從一個節(jié)點傳送到另外一個節(jié)點。所有節(jié)點同步。第一次，一個包在等待假設(shè)干個時隙后發(fā)送。其中等待的時隙數(shù)是從{0,1,…,W0}中隨機選擇的一個數(shù)，W0≥1是表示最小競爭尺度。假設(shè)某節(jié)點發(fā)送的包出現(xiàn)了沖突，那么該節(jié)點的競爭窗口大小乘以系數(shù)α。〔5.1〕設(shè)PS表示每個節(jié)點在每個時隙發(fā)送報文的概率，n表示對每個節(jié)點而言參與競爭發(fā)送報文時隙的節(jié)點數(shù)，對于每個節(jié)點來說n的值等于其1hop鄰居數(shù)。那么對二元的指數(shù)退避策略，有又：〔5.2〕將〔5.2〕代入〔5.1〕得〔5.3〕其中n取參與競爭發(fā)送報文時隙的節(jié)點數(shù)的平均值，即〔5.4〕〔5.4〕中r為節(jié)點的傳輸范圍，ρ為網(wǎng)絡(luò)中節(jié)點密度〔node/m2〕。平均的來說，設(shè)節(jié)點在發(fā)送第i＋1〔i＝0，1..〕個報文時〔即已發(fā)送i個報文〕將等待個時隙，那么〔5.5〕考慮Wi=α，又算法采用的是二元指數(shù)退避策略，故α=2。所以，發(fā)送第i＋1個報