自組織網(wǎng)絡及其路由技術

1、自組織網(wǎng)絡及其路由技術一、背景及概念1.發(fā)展歷史無線通信網(wǎng)一般都是有中心的，要基于預設的網(wǎng)絡基礎架構才能運行。例如，蜂窩移動通信系統(tǒng)要有基站的支持；無線局域網(wǎng)一般也工作在有接入點（AP）和有線骨干網(wǎng)的模式下。但對于有些特殊場合來說，有中心的移動網(wǎng)絡并不能勝任。比如，戰(zhàn)場上部隊快速展開和推進，地震或水災后的營救等。這些場合的通信不能依賴于任何預設的網(wǎng)絡設施，而需要一種能夠臨時快速自動組網(wǎng)的移動網(wǎng)絡。無線自組織網(wǎng)絡即可以滿足這樣的應用。 自組織網(wǎng)絡技術的研究始于 20 世紀 70 年代。美國 DARPA 出于軍事需要，開始研究分組無線網(wǎng)（PRNET）在戰(zhàn)場環(huán)境下數(shù)據(jù)通信中的應用。項目完成之后，DA

2、PRA 又在 1993 年啟動了高殘存性自適應網(wǎng)絡項目。研究如何將 PRNET的成果加以擴展，以支持更大規(guī)模的網(wǎng)絡，還要開發(fā)能夠適應戰(zhàn)場快速變化環(huán)境下的自適應網(wǎng)絡協(xié)議。1994 年， DARPA 又啟動了全球移動信息系統(tǒng)項目。在分組無線網(wǎng)已有成果的基礎上對能夠滿足軍事應用需要的、可快速展開、高抗毀性的移動信息系統(tǒng)進行全面深入的研究，并一直持續(xù)至今。1991 年成立的 IEEE 802.11 標準委員會采用了“無線自組織網(wǎng)絡”一詞描述這種特殊的對等式無線移動網(wǎng)絡。 美國福布斯雜志報道了加州大學洛杉磯分校的無線傳感器網(wǎng)絡的研究項目，指出通過無線傳感器網(wǎng)絡，我們將實實在在地掌握這個物理世界。2003

3、年美國商業(yè)周刊將無線傳感器網(wǎng)絡列為21世紀改變世界的10大技術之一。美國技術評論雜志評出對世界產(chǎn)生深遠影響的十大新興技術，無線傳感器網(wǎng)絡排名第一。另外，像 IEEE(ComPuter等眾多雜志也都發(fā)表了一些關于無限傳感器網(wǎng)絡的論文。我國也非常重視無線傳感器網(wǎng)絡的研究，中國國家自然科學基金委員會在2003年已經(jīng)開始對無線傳感器網(wǎng)絡的研究進行了資助，并于2004年將其列為重點項目。2005年我國開始傳感網(wǎng)絡標準化研究工作。2006年，國家973計劃，國家863高技術計劃等國家和省部級科技發(fā)展“十一五”規(guī)劃也設專項資助該領域的理論、方法和關鍵技術研究。同年，我國政府將發(fā)展無線傳感器網(wǎng)絡列入未來15年

4、的國家中長期科學和技術發(fā)展規(guī)劃綱要(2006一2020年)。2008年9月啟動的國家16個重大專項中03專項設立7個方向，無線傳感器網(wǎng)絡為第6個一“短距離無線互聯(lián)與傳感器網(wǎng)絡研發(fā)”。未來科學家預言無線傳感器將引發(fā)新的信息革命，一些專家將傳感器網(wǎng)絡、塑料電子學和仿生人體器官并稱為全球未來的三大高科技產(chǎn)業(yè)，它們將掀起新的產(chǎn)業(yè)浪潮。這些都預示著未來到處是以電池為能源的無線傳感器網(wǎng)絡，這些傳感器可監(jiān)控環(huán)境、機器甚至人類自己。在自組織網(wǎng)絡中，節(jié)點具有報文轉(zhuǎn)發(fā)能力，節(jié)點間的通信可能要經(jīng)過多個中間節(jié)點的轉(zhuǎn)發(fā)，即經(jīng)過多跳，這是自組織網(wǎng)絡與其它移動網(wǎng)絡的最根本區(qū)別。節(jié)點通過分層的網(wǎng)絡協(xié)議和分布式算法相互協(xié)調(diào)，實

5、現(xiàn)了網(wǎng)絡的自動組織和運行。2. 自組織網(wǎng)絡特點無線自組織網(wǎng)絡具有無中心和自組織性。網(wǎng)絡中沒有絕對的控制中心，所有節(jié)點的地位平等，網(wǎng)絡中的節(jié)點通過分布式算法來協(xié)調(diào)彼此的行為，無需人工干預和任何其它預置的網(wǎng)絡設施，可以在任何時刻任何地方快速展開并自動組網(wǎng)。由于網(wǎng)絡的分布式特征、節(jié)點的冗余性和不存在單點故障點，使得網(wǎng)絡的健壯性和抗毀性很好。所以與傳統(tǒng)網(wǎng)絡相比，無線自組織網(wǎng)絡有以下特性：1. 自動配置：自動配置是無線自組織網(wǎng)絡的一個特征，節(jié)點必須檢測其它節(jié)點以及它們可以提供的服務。由于網(wǎng)絡動態(tài)變化，自動配置過程需要確保網(wǎng)絡能夠正常工作，這涉及到連接 Internet 的網(wǎng)關節(jié)點的更換，簇頭的更新等。在

6、網(wǎng)絡形成階段，節(jié)點可以就網(wǎng)絡拓撲進行協(xié)商（星形、環(huán)形、點到點、點到多點、平面和分級），這依賴于網(wǎng)絡的類型、底層的無線技術和應用的需求。 2 .多跳性:由于節(jié)點發(fā)射功率的限制，其通信范圍有限。當它要與其通信范圍之外的節(jié)點進行通信時，需要中間節(jié)點的轉(zhuǎn)發(fā)。另外， Adhoc網(wǎng)絡中的多跳是由普通節(jié)點協(xié)作完成的，而不需要專用的路由設備(如路由器)來完成。3.無中心和自組織性 :網(wǎng)絡中沒有絕對的控制中心，所有節(jié)點的地位平等，網(wǎng)絡中的節(jié)點通過分布式算法來協(xié)調(diào)彼此的行為自組成網(wǎng)，無需人工干預和任何其它預置的網(wǎng)絡設施。由于網(wǎng)絡的分布式特征、節(jié)點的冗余性和不存在單點故障點，使得網(wǎng)絡的健壯性和抗毀性很好。4.動態(tài)拓

7、撲 :網(wǎng)絡中，移動終端能夠以較隨意的速度和方式移動，并可以隨時關閉電臺，加上無線發(fā)送裝置的天線類型多種多樣、發(fā)送功率的變化、無線信道間的互相干擾、地形和天氣等綜合因素的影響，移動終端間通過無線信道形成的網(wǎng)絡拓撲可能隨時發(fā)生變化，而且變化的方式和趨勢都難以預測。5.帶寬的限制 :自組織網(wǎng)絡采用無線傳輸技術作為底層通信手段，由于無線信道本身的物理特性，它所能提供的網(wǎng)絡帶寬相對有線信道要低得多。此外，同時無線自組織網(wǎng)絡受限于無線傳輸帶寬，由于采用無線傳輸技術作為底層通信手段，它所能提供的網(wǎng)絡帶寬相對有線信道要低得多。此外考慮到競爭共享無線信道產(chǎn)生的沖突、信號衰減、噪音和信道之間干擾等多種因素，移動終

8、端得到的實際帶寬遠遠小于理論上的最大帶寬。6.移動終端的局限性 :自組織網(wǎng)絡中的移動終端具有攜帶方便、輕便靈巧等好處，但是也存在固有缺陷，例如能量有限、內(nèi)存較小、CPU性能較低等，從而給應用程序設計開發(fā)帶來一定的難度，同時屏幕等外設較小，不利于開展功能較復雜的業(yè)務。7.存在單向信道 :自組織網(wǎng)絡采用無線信道通信，由于地形環(huán)境或發(fā)射功率等因素影響，一對節(jié)點之間可能產(chǎn)生單向信道。8.安全性較差 :自組織網(wǎng)絡是一種特殊的無線移動網(wǎng)絡，由于采用無線信道、無中心、分布式控制和臨時組織等技術，它更加容易受到被動竊聽、主動入侵、拒絕服務、剝奪“睡眠”等網(wǎng)絡攻擊。信道加密、抗干擾、用戶認證和其它安全措施都需要

9、特別考慮。3.Ad-hoc網(wǎng)絡AdHoc網(wǎng)絡是目前討論的最多的自組織網(wǎng)技術。這種網(wǎng)絡不需要固定的基站設備和路由器，應此不依賴于蜂窩移動通信網(wǎng)絡。網(wǎng)絡中的節(jié)點可在一定區(qū)域內(nèi)隨意移動并能于網(wǎng)絡中的任意站點相互通信。每一個節(jié)點都能實現(xiàn)路由器的功能而在網(wǎng)絡中搜尋、維護到另一節(jié)點的路由。自組織網(wǎng)可用在事故的突發(fā)現(xiàn)場以及人們希望能迅速共享信息的會議、辦公室等場所。AdHoc網(wǎng)絡根據(jù)站點間的邏輯關系可以分為兩種網(wǎng)絡結構:平面網(wǎng)絡結構、分級網(wǎng)絡結構。如圖1-1所示，左邊的自組織網(wǎng)絡是一個平面結構的網(wǎng)絡，而右邊的則是一個二級結構的自組織網(wǎng)絡。平面結構中，所有節(jié)點地位平等，也被稱為是對等式結構。與之相對的分級結構

10、中，網(wǎng)絡被劃分為多個簇(cluster)，每個簇由一個簇首(cluster一header)和多個簇成員(cluster一member)組成。這些簇首在邏輯上組成了一個高一級的網(wǎng)絡，而在這個高一級的網(wǎng)絡中又可以分簇，形成更高一級的網(wǎng)絡，直至最高級。任意兩個不在一個簇之內(nèi)的簇成員之間的通信都要通過各自的簇首來中轉(zhuǎn)。圖1.1 平面結構VS分級結構平面結構的自組織網(wǎng)絡結構簡單，由于站點間是對等一的邏輯關系無需任何的結構維護過程。源節(jié)點和目的節(jié)點之間可以存在多條路徑，當一條路徑繁忙時，可能通過另一條路徑繼續(xù)通信。由于網(wǎng)絡中所有節(jié)點是對等的，原則上不存在瓶頸，所以比較健壯。平面結構的最大缺點是網(wǎng)絡規(guī)模受限

11、。在平面結構中，每一個節(jié)點都需要知道到達其它所有節(jié)點的路由。由于節(jié)點的移動性，維護這些動態(tài)變化的路由信息需要大量的控制消息。網(wǎng)絡規(guī)模越大，路由維護的開銷就越大。當網(wǎng)絡的規(guī)模增加到某個程度時，所有的帶寬都可能會被路由協(xié)議消耗掉。所以平面式結構網(wǎng)絡的可擴展性較差。分級結構的最大優(yōu)點則是可以有效控制路由信息量的膨脹，可以支持更大的網(wǎng)絡的規(guī)模，必要的時候可以通過增加新的簇或者增加網(wǎng)絡級數(shù)來提高整個網(wǎng)絡的容量。分級結構中，簇內(nèi)成員只需要維護簇內(nèi)站點間的路由信息，與簇外站點的通信交給簇首處理。即簡化了成員站點的功能，又使得簇內(nèi)的網(wǎng)絡管理信息量大大減少，節(jié)省了網(wǎng)絡開銷。簇內(nèi)成員無須知道其他簇的拓撲結構，一個

12、簇的拓撲變化不會被其它簇的節(jié)點感知，這就大大減少了網(wǎng)絡中路由信息對無線鏈路帶寬的消耗。簇首的功能較為復雜一些，不僅需要維護到達其他簇的路由信息，還要知道所有節(jié)點與簇的關系。網(wǎng)絡中主要的路由功能由簇首完成，大部分路由、管理信息在由簇首組成的高級網(wǎng)絡中傳播。一般情況下簇首只是網(wǎng)絡中的少數(shù)站點，在同樣規(guī)模網(wǎng)絡的條件下分級結構的路由開銷要比平面結構的小。如果簇內(nèi)通信的信息流量在整個網(wǎng)絡的通信量中占較大比例的時候，更能夠明顯提高整個網(wǎng)絡的吞吐量。當然分級結構也有其缺點存在。首先維護不同層次結構間站點的邏輯關系較為復雜。簇首站點如果由事先指定，在站點移動情況下無法保證各個簇的規(guī)模相當;選舉產(chǎn)生簇首的算法又

13、較為復雜，需要仔細設計。其次簇內(nèi)的節(jié)點與簇外的節(jié)點進行通信時必須經(jīng)過簇頭，所得到的路由不一定是最佳路由。第三簇首的通信負擔較重，容易成為網(wǎng)絡中的通信瓶頸。從上面的比較可以看出，平面結構和分級結構的自組織網(wǎng)絡各自具有不同的優(yōu)勢。平面結構的自組織網(wǎng)絡結構簡單，站點間的路由較為靈活，不容易出現(xiàn)網(wǎng)絡瓶頸。但是，在網(wǎng)絡規(guī)模較大時路由更新信息的負載較重造成通信容量的下降。平面結構更適合較小規(guī)模的網(wǎng)絡。分級結構通過路由信息局部化減小路由控制報文的開銷，提高了系統(tǒng)的吞吐量;通過增加新的簇分級結構可以支持更大的網(wǎng)絡規(guī)模，有較好的可擴展性;另外分級結構可通過簇首的管理功能為網(wǎng)絡提供用戶接入控制和站點定位等輔助功能

14、。在AdHoc網(wǎng)絡當中，無論采用平面結構還是分級結構有一點是共同的:所有站點共享一個物理信道。分級結構網(wǎng)絡雖然能夠限制簇內(nèi)部的路由信息向其它簇擴散，但是分簇和分級都只是限于站點間邏輯關系而言，并不能隔離站點對物理信道的競爭。當網(wǎng)絡中有站點數(shù)量越大，站點取得信道資源就越困難，出現(xiàn)信道沖突的可能性也相應增加。由于站點的通信距離限制，多數(shù)情況下AdHoc 。網(wǎng)絡中存在多跳路徑。多跳網(wǎng)絡中隱藏終端的存在使得站點難以區(qū)分無線信道是空閑還是正被一個隱藏終端使用，物理信道沖突比有線以太網(wǎng)和單跳無線網(wǎng)絡中更復雜。4.無線傳感自組織網(wǎng)的應用無線自組織網(wǎng)絡的許多優(yōu)良特性為它在民用和軍事通信領域占據(jù)一席之地提供了有

15、利的依據(jù)。首先，網(wǎng)絡的自組織性提供了廉價而且快速部署網(wǎng)絡的可能。其次，多跳和中間節(jié)點的轉(zhuǎn)發(fā)特性可以在不降低網(wǎng)絡覆蓋范圍的條件下減少每個終端的發(fā)射范圍，從而降低設計天線和相關發(fā)射（接收）部件的難度，也降低了設備的功耗，從而為移動終端的小型化、低功耗提供了可能。從共享無線信道的角度來看，自組織網(wǎng)絡降低了信號沖突的幾率，提高了信道利用率。從對使用者的保護來看，高功率的無線電波產(chǎn)生的電磁輻射對用戶的身體健康也有影響。另外，網(wǎng)絡的魯棒性、抗毀性滿足了某些特定應用需求。它的應用場合可以分為以下幾類： 1.緊急場合：在發(fā)生了地震、水災、強熱帶風暴或遭受其它災難打擊后，固定的通信網(wǎng)絡設施（如有線通信網(wǎng)絡、蜂窩

16、移動通信網(wǎng)絡的基站等網(wǎng)絡設施、衛(wèi)星通信地球站以及微波接力站等）可能被全部摧毀或無法正常工作，對于搶險救災來說，這時就需要無線自組織網(wǎng)絡這種不依賴任何固定網(wǎng)絡設施又能快速布設的自組織網(wǎng)絡技術。類似地，處于邊遠或偏僻野外地區(qū)時，同樣無法依賴固定或預設的網(wǎng)絡設施進行通信。無線自組織網(wǎng)絡技術的獨立組網(wǎng)能力和自組織特點，是這些場合通信的最佳選擇。2.軍事應用：軍事應用是無線自組織網(wǎng)絡技術的主要應用領域。因其特有的無需架設網(wǎng)絡設施、可快速展開、抗毀性強等特點，它是數(shù)字化戰(zhàn)場通信的首選技術。無線自組織網(wǎng)絡技術已經(jīng)成為美軍戰(zhàn)術互聯(lián)網(wǎng)的核心技術。美軍的近期數(shù)字電臺和無線互聯(lián)網(wǎng)控制器等主要通信裝備都使用了自組織網(wǎng)

17、絡技術。 3.個人通信：個人局域網(wǎng)是無線自組織網(wǎng)絡技術的另一應用領域。不僅可用于實現(xiàn) PDA、手機、手提電腦等個人電子通信設備之間的通信，還可用于個人局域網(wǎng)之間的多跳通信。 4.傳感器網(wǎng)絡：傳感器網(wǎng)絡是無線自組織網(wǎng)絡技術的另一大應用領域。對于很多應用場合來說傳感器網(wǎng)絡只能使用無線通信技術。而考慮到體積和節(jié)能等因素，傳感器的發(fā)射功率不可能很大。使用無線自組織網(wǎng)絡實現(xiàn)多跳通信是非常實用的解決方法。分散在各處的傳感器組成無線自組織網(wǎng)絡，可以實現(xiàn)傳感器之間和與控制中心之間的通信。這在爆炸殘留物檢測等領域具有非常廣闊的應用前景。5.移動通信系統(tǒng)補充：無線自組織網(wǎng)絡還可以與蜂窩移動通信系統(tǒng)相結合利用移動臺

18、的多跳轉(zhuǎn)發(fā)能力擴大蜂窩移動通信系統(tǒng)的覆蓋范圍、均衡相鄰小區(qū)的業(yè)務、提高小區(qū)邊緣的數(shù)據(jù)速率等。6.商業(yè)應用：組建家庭無線網(wǎng)絡、無線數(shù)據(jù)網(wǎng)絡、移動醫(yī)療監(jiān)護系統(tǒng)和無線設備網(wǎng)絡，開展移動和可攜帶計算以及無所不在的通信業(yè)務等。7.其它應用:考慮到Adhoc網(wǎng)絡具有很多優(yōu)良特性，它的應用領域還有很多，這需要我們進一步去挖掘。比如它可以用來擴展現(xiàn)有蜂窩移動通信系統(tǒng)的覆蓋范圍，實現(xiàn)地鐵和隧道等場合的無線覆蓋，實現(xiàn)汽車和飛機等交通工具之間的通信，用于輔助教學和構建未來的移動無線城域網(wǎng)和自組織廣域網(wǎng)等。二、自組織網(wǎng)絡的路由技術1.路由算法設計目標路由協(xié)議是ad-hoc網(wǎng)絡的核心，是節(jié)點之間進行通信而采用的協(xié)議，主

19、要由路由算法實現(xiàn)。由于網(wǎng)絡中節(jié)點的移動性，網(wǎng)絡拓撲的結構可能發(fā)生改變，因此路由算法要能滿足動態(tài)路由的要求。選擇和設計一個高效的路由算法對于一個ad-hoc網(wǎng)絡來說顯得非常重要，路由算法的好壞直接影響到ad-hoc網(wǎng)絡的性能。Ad-hoc路由算法設計的首要問題是要求簡單、高效并且控制開銷小。本章主要研究ad-hoc路由算法的設計。路由算法的任務是在節(jié)點和節(jié)點之間建立路由，實現(xiàn)可靠地數(shù)據(jù)傳遞，一個完整的路由算法應包括路由方式、路由發(fā)現(xiàn)和路由維護等內(nèi)容。要設計一個好的路由算法通常有以下的一個或多個設計目標:1.簡單、最優(yōu)化、高效、低耗、控制開銷小自組織無線傳輸帶寬有限，傳送控制開銷不可避免地消耗掉一

20、部分帶寬資源，因此路由算法首先應盡量簡單可靠，并具有選擇最佳路徑的能力，這樣有助于減少各種開銷。另外路由算法也必須高效的提供其功能，盡可能減少軟件和應用的開銷。不能在節(jié)點保存太多的狀態(tài)信息，節(jié)點間不能交換太多的路由信息。2.無環(huán)路、快速收斂路由算法必須能夠保證不會產(chǎn)生路由環(huán)路，并且能快速收斂，收斂是所有路由器對最佳路徑達成一致的過程。由于自組織網(wǎng)狀網(wǎng)絡是動態(tài)的，隨時處于變化之中，會導致大量已有路由信息在短時間內(nèi)作廢，從而更容易產(chǎn)生路由環(huán)路。因此無環(huán)路的路由算法就顯得尤為重要，另外，路由算法必須對拓撲的變化具有快速反應能力，在計算路由時能夠快速收斂，及時獲得有效的路由，避免出現(xiàn)目的節(jié)點不可達的情

21、況。3.健壯、穩(wěn)定、靈活路由算法必須健壯，即在出現(xiàn)不正?；虿豢深A見事件的情況下仍能正常處理，例如硬件故障、高負載和不正確的實現(xiàn)方法等。路由算法還應該是靈活的，即它們應該迅速、準確地適應各種網(wǎng)絡環(huán)境，例如，當發(fā)現(xiàn)網(wǎng)絡中出現(xiàn)鏈路中斷時，路由算法要迅速選擇次佳的路徑。2.網(wǎng)絡的組成部分無線傳感器網(wǎng)絡是由大量節(jié)點以自組織形式構成的網(wǎng)絡。在被監(jiān)視區(qū)域內(nèi)，節(jié)點被任意散落后，每個節(jié)點都可以收集數(shù)據(jù)，網(wǎng)絡中節(jié)點通過自組織快速形成一個無線網(wǎng)絡，它們之間相互協(xié)作進行數(shù)據(jù)收集，融合和傳遞。如圖2.1所示，典型的無線傳感器網(wǎng)絡是由傳感器節(jié)點、簇節(jié)點 (clusternode)、匯聚節(jié)點(也稱為網(wǎng)關節(jié)點，sink節(jié)點)

22、、internet或衛(wèi)星通訊網(wǎng)組成的。傳感器節(jié)點既負責采集和發(fā)送信息，也可負責作為其它節(jié)點信息的路由傳輸點。首先，每個節(jié)點將自己收集的數(shù)據(jù)傳送給自己傳輸范圍內(nèi)的簇節(jié)點(或可到達簇節(jié)點的路由節(jié)點)，各個簇節(jié)點通過多跳中繼方式將監(jiān)測數(shù)據(jù)傳到sink節(jié)點，最終通過Internet或衛(wèi)星通訊網(wǎng)傳送到監(jiān)控中心，最終實現(xiàn)任務管理節(jié)點(觀察者)與傳感器之間的通信。圖2.1無線傳感器網(wǎng)絡是在移動Ad一Hoc網(wǎng)絡的基礎上發(fā)展起來的，在自組織和多跳通信等方面與移動Ad一Hoc網(wǎng)絡在某些方面具有一定相似性。但無線傳感器網(wǎng)絡具有自己的特點以及局限性，主要表現(xiàn)在:(1)傳感器節(jié)點體積小，成本低，這是無線傳感器網(wǎng)絡的一大

23、特點和標志。同時也應看到，正由于節(jié)點體積小，傳感器節(jié)點的使用(包括電源和時間)是有限的。如圖2.1所示，無線傳感器網(wǎng)絡的多跳中繼通信，使得越靠近sink節(jié)點，節(jié)點承擔的流量就越大，通信時間越長，能耗也越大。關鍵節(jié)點過早能量耗盡，即使其它節(jié)點能量充足，網(wǎng)絡仍然會因為通信不暢而致使整個區(qū)域通信癱瘓。(2)不同于一般網(wǎng)絡的下TCP/IP協(xié)議，無線傳感器網(wǎng)絡劃分為物理層、數(shù)據(jù)鏈路層、網(wǎng)絡層、傳輸層和應用層五層。其中，物理層進行比特流的傳輸;數(shù)據(jù)鏈路層主要負責節(jié)點的接入，降低節(jié)點間的傳輸沖突;網(wǎng)絡層實現(xiàn)傳感器與傳感器、傳感器與觀察者之間的通信，支持多傳感器協(xié)作完成大型感知任務;傳輸層提供差錯控制和流量控

24、制;應用層由各種傳感器網(wǎng)絡應用軟件系統(tǒng)構成，可以實現(xiàn)不同的應用目的。(3)無線傳感器網(wǎng)絡是動態(tài)自組織的。由于節(jié)點的有限性，無線傳感器網(wǎng)絡中時常有節(jié)點失效或新節(jié)點的補入，因此節(jié)點之間是不斷以自組織方式構成新的傳輸路徑，確保網(wǎng)絡的暢通。3. 節(jié)點結構組成無線傳感器網(wǎng)絡的基本單位是無線傳感器節(jié)點，它是構成無線傳感器網(wǎng)絡的基礎平臺，節(jié)點在網(wǎng)絡中可以充當數(shù)據(jù)采集者、數(shù)據(jù)中轉(zhuǎn)站或簇頭節(jié)點 (cluster-head_node)等角色。主要用于完成采集信息、融合并傳送數(shù)據(jù)的作用。它的重要特征就是低功耗、低成本和小體積。盡管在不同應用中，無線傳感器網(wǎng)絡的組成不盡相同，但一般是由傳感單元(由傳感器、模數(shù)轉(zhuǎn)換功能

25、模塊即A/D轉(zhuǎn)換器組成)、處理單元(CPU、存儲器和嵌入式操作系統(tǒng)等)、無線通信單元(無線收發(fā)電路)以及電源四部分組成。另外，在有些應用中還可包括電源自供電系統(tǒng)單元、定位系統(tǒng)單元等。如圖2.2所示圖2.2節(jié)點結構圖一般而言，傳感器節(jié)點的類型通常是由被監(jiān)測物理信號的形式?jīng)Q定的。單元模塊的功能大同小異。傳感單元負責信號的采集和轉(zhuǎn)換。該單元收集周圍環(huán)境的數(shù)據(jù)(如溫度、噪聲等)，通過路由通信協(xié)議直接或間接的將數(shù)據(jù)傳輸給遠方匯聚節(jié)點(Sink但其各部分濕度、壓力、node);數(shù)據(jù)轉(zhuǎn)換時，為了進行一些比較復雜的監(jiān)測操作或需要監(jiān)測不同數(shù)據(jù)信息(如溫度、濕度、壓力、噪聲等)，一個傳感器節(jié)點常常裝備了多種傳感器

26、。無線通信單元要接收鄰居節(jié)點的數(shù)據(jù)，同時將其轉(zhuǎn)發(fā)給距離簇節(jié)點更近的鄰居節(jié)點或者直接轉(zhuǎn)發(fā)給匯聚節(jié)點。經(jīng)研究表明，節(jié)點無線通信單元的能量開銷占節(jié)點總能耗的90%以上，因此降低能耗的關鍵是降低通信模塊的能耗。節(jié)點的電源一般采用只能攜帶有限能量的電池來實現(xiàn)，一旦電源耗盡，節(jié)點就失去了工作能力。并且，若更換節(jié)點電池的成本會比重新布放節(jié)點的成本還要高，因此，決定了無線傳感器在使用過程中不太可能更換電池，而節(jié)能則成為無線傳感器網(wǎng)絡的一大關注點。為了最大限度的節(jié)約電源，在硬件方面，要盡量改善器件耗能量，甚至在不需要傳輸數(shù)據(jù)時，可以切斷射頻部分電源;在軟件方面，各層通信協(xié)議應該以節(jié)能為中心。節(jié)點通過各功能單元之

27、間的協(xié)作可以感受各種數(shù)據(jù)的變化。每個無線傳感器節(jié)點作為一個簡單的個體將傳感器節(jié)點收集到的信息轉(zhuǎn)化成為數(shù)字信號，進行編碼，通過多跳的方式傳送到匯聚節(jié)點(sink)，匯聚節(jié)點(sink)再連接到Internet，最后接入管理中心的電腦。這樣人們就可以進行干預，遙控和管理。無線傳感器網(wǎng)絡節(jié)點在早期是一些復雜的物理化學裝置，通過把物理量變成電信號，經(jīng)過信號線接入計算機進行數(shù)據(jù)處理。隨著無線傳感器網(wǎng)絡的研究成為熱點，很多國家投入巨資進行該方面的研究。同時，也受益于微機電技術，計算機技術以及無線通信技術的等各項技術的發(fā)展，使得傳感器節(jié)點的各個功能模塊單元的體積越來越小，甚至可以集成到一塊芯片中，現(xiàn)在傳感器

28、的尺寸越來越小，可以組成一個尺寸小、功耗少、成本低的傳感器節(jié)點。4. 路由算法技術和分類根據(jù)路由發(fā)現(xiàn)的驅(qū)動模式的不同，移動AdHoc網(wǎng)絡的路由協(xié)議可分為表驅(qū)動(Table-driven)和按需(on-demand)路由協(xié)議，這種劃分方法是目前國內(nèi)外學術界對移動AdHoc網(wǎng)絡的路由協(xié)議的主流的劃分方法。表驅(qū)動路由協(xié)議又稱為先驗式路由協(xié)議。在這種路由協(xié)議中，網(wǎng)絡中的每個節(jié)點都會維護一張路由表，路由表中包含著到達網(wǎng)絡中其它節(jié)點的路由信息。當源節(jié)點要向某個目的節(jié)點發(fā)送數(shù)據(jù)包時，則可以立即從路由表中獲得路由。如果節(jié)點檢測到網(wǎng)絡的拓撲結構發(fā)生變化，節(jié)點將在網(wǎng)絡中發(fā)送更新消息；而收到更新消息的節(jié)點將相應地更

29、新自己的路由表，以維護一致的、及時的、準確的路由信息。所以路由表可以準確地反映網(wǎng)絡的拓撲結構，因此這種路由協(xié)議的時延較?。坏怯捎谛枰皶r的更新路由信息，路由協(xié)議的開銷較大。典型的表驅(qū)型路由協(xié)議有DSDV、CGSR、FSR、WRP、DBF，GSR、HSR、ZHLS等。(1)DSDVDSDV(Destination-Sequenced Distance Vector)路由協(xié)議是一種無環(huán)路距離向量路由協(xié)議，它是根據(jù)傳統(tǒng)的路由選擇算法改良而發(fā)展出來的。在協(xié)議中，每個移動節(jié)點都需要維護一個路由表，路由表的表項包括目的節(jié)點、跳數(shù)、下一跳節(jié)點和目的節(jié)點號。其中目的節(jié)點號由目的節(jié)點分配，主要用于判別路由是否

30、過時，并可防止路由環(huán)路的產(chǎn)生。每個節(jié)點必須周期性的與鄰居節(jié)點交換路由信息，這種交換可以分為時間驅(qū)動和事件驅(qū)動兩種類型。在節(jié)點發(fā)送分組時，將添加一個序號到分組中，節(jié)點從鄰居節(jié)點收到新的信息，只使用序列號最高的記錄信息，如果兩個路由具有相同的序列號，那么將選擇最優(yōu)的路由(如跳數(shù)最小)。DSDV路由表更新采用觸發(fā)的方式來更新網(wǎng)絡鏈路。為減少路由分組的長度，使用兩種更新方式：一種是全部更新，即拓撲更新消息中將包括整個路由表，主要應用于網(wǎng)絡變化較快的情況，另一種方式是部分更新，更新消息中僅包含變化的路由部分，通常適用于網(wǎng)絡變化較慢的情況。DSDV協(xié)議的主要優(yōu)點是消除了路由環(huán)路，加快了收斂速度，同時減少了

31、控制信息的開銷，但是它的不足在于難以適應速度變化快的移動AdHoc網(wǎng)絡。（2）CGSRCGSR(Clusterhead Gateway Switch Routing)使用了層次結構路由，指定了簇首節(jié)點和網(wǎng)關節(jié)點，其中簇首節(jié)點用來控制一組節(jié)點和網(wǎng)關節(jié)點，網(wǎng)關節(jié)點是兩個簇之間的節(jié)點。當一個節(jié)點要發(fā)送分組時，這個分組首先到達該發(fā)送節(jié)點的簇首節(jié)點，然后簇首節(jié)點把這個分組通過網(wǎng)關節(jié)點轉(zhuǎn)發(fā)給另一個簇首節(jié)點，不斷重復這個過程直到分組到達目的節(jié)點。因此，每個節(jié)點都必須有其簇成員的路由表。CSGR利用DSDV作為其底層路由選擇機制，并針對分級網(wǎng)絡做了適當?shù)母倪M，尋路是通過簇首節(jié)點和網(wǎng)關節(jié)點完成的，簇內(nèi)路由方式為

32、成員節(jié)點-簇首節(jié)點-成員節(jié)點方式，簇間路由方式采用成員節(jié)點-簇首-網(wǎng)關-簇首-成員節(jié)點方式。（3）WRPWRP(wireless routing protocol)協(xié)議是另一種表驅(qū)動路由協(xié)議，在網(wǎng)絡的節(jié)點中保存路由信息。每個節(jié)點保存在路由表中的信息如下：距離、路由、鏈路開銷和重傳消息的列表(MRL)。MRL記錄關于消息序列號、重傳計數(shù)器、每一個鄰節(jié)點正確應答所需的標識和更新消息的更新列表等信息，這就使得節(jié)點可以決定何時發(fā)送更新消息以及發(fā)送給哪個節(jié)點。更新消息包括目的節(jié)點的地址、到目的節(jié)點的距離和目的節(jié)點的上游節(jié)點。然后鄰節(jié)點就修改自己的路由表并試圖通過預備的節(jié)點建立新的路由。WRP的優(yōu)點就是當

33、一個節(jié)點試圖執(zhí)行路徑計劃算法時，可以通過目的節(jié)點的上游節(jié)點所保存的信息和鄰節(jié)點所保存的信息來限制算法，使得算法收斂得更快并避免路由當中的環(huán)路。由于WRP需要保存4個路由表，所以比大多數(shù)的協(xié)議需要更大的內(nèi)存。此外，WRP還依賴于周期性的HELLO消息，這也要占用帶寬。按需路由協(xié)議又稱為反應式路由協(xié)議，是一種當節(jié)點需要發(fā)送數(shù)據(jù)包時才查找路由的路由算法。在這種路由協(xié)議中，網(wǎng)絡中的節(jié)點不需要維護及時準確的路由信息，只有當向目的節(jié)點發(fā)送數(shù)據(jù)包時，源節(jié)點才在網(wǎng)絡中發(fā)起路由發(fā)現(xiàn)過程，尋找相應的路由。與先驗式路由協(xié)議相比，反應式路由協(xié)議的開銷比較小，但是由于發(fā)包時要進行路由發(fā)現(xiàn)過程，數(shù)據(jù)報傳送的時延較大。典型

34、的按需驅(qū)動路由協(xié)議有DSR、AODV、TORA、ABR等。（1）DSRDSR(Dynamic Source Routing)是一種基于源路由的按需驅(qū)動路由協(xié)議，它使用源路由算法而不是按逐跳路由的方法。網(wǎng)絡中每一個節(jié)點都需要維護一個已知的路由表，并且當發(fā)現(xiàn)新的路由時就更新該路由表。每一個數(shù)據(jù)包的包頭都包含該數(shù)據(jù)包從源節(jié)點到目的節(jié)點路由所經(jīng)過的中間節(jié)點序列信息，故稱為源路由算法。DSR主要包括兩個過程：路由發(fā)現(xiàn)和路由維護。當節(jié)點S向節(jié)點D發(fā)送數(shù)據(jù)時，它首先檢查緩存是否存在未過期的到目的節(jié)點的路由，如果存在，則直接使用可用的路由，否則啟動路由發(fā)現(xiàn)過程。DSR協(xié)議的優(yōu)點在于節(jié)點不需要周期性地發(fā)送路由廣

35、播分組，僅需要維護與之通信節(jié)點的路由，協(xié)議開銷較小，節(jié)省了能量和網(wǎng)絡帶寬；使用路由緩存技術，減少了路由發(fā)現(xiàn)的耗費，一次路由發(fā)現(xiàn)過程可能會產(chǎn)生多條到目的節(jié)點的路由，將有助于路由選擇，能完全消除路由環(huán)路。DSR協(xié)議的缺點在于由于每個數(shù)據(jù)包的頭部都需要攜帶路由信息，數(shù)據(jù)包的額外開銷較大；路由請求消息采用泛洪方式，相鄰節(jié)點路由請求消息可能發(fā)生傳播沖突并可能會產(chǎn)生重復廣播。由于使用緩存路由，過期路由會影響路由選擇的準確性。(2)AODVAODV(On-Demand Distance Vector Routing)協(xié)議是一個建立在DSR和DSDV上的按需路由協(xié)議，借用了DSR中路由發(fā)現(xiàn)和維護的基礎，采用D

36、SDV逐跳路由，順序編號和路由維護階段的周期更新機制。在協(xié)議中，當中間節(jié)點收到一個路由請求分組后，它能夠通過反向?qū)W習來取得源節(jié)點的路徑，目的節(jié)點最終收到這個路由請求分組后，可以根據(jù)這個路徑恢復這個路由請求，在源節(jié)點和目的節(jié)點間建立了一條全雙工路徑。AODV協(xié)議的特點在于它采用逐跳轉(zhuǎn)發(fā)分組方式，同時加入了組播路由協(xié)議擴展。其主要缺點是依賴對稱式的鏈路，不支持非對稱鏈路。(3)TORATORA(Temporally Ordered Routing Algorithm)協(xié)議是在有向無環(huán)圖算法(DirectedAcyclic Graphic)的基礎上，結合反向鏈路算法提出來的自適應的分布式路由算法，主

37、要用于高動態(tài)的多跳無線網(wǎng)絡。TORA協(xié)議能夠按需快速地發(fā)現(xiàn)多個路由，盡管這些路由不一定是最優(yōu)的，但是TORA協(xié)議能夠保證這些路由是無環(huán)的。TORA的主要特點是當拓撲結構發(fā)生改變時，控制消息只在拓撲發(fā)生變化的局部范圍傳播，節(jié)點只需要維護相鄰節(jié)點的路由信息。TORA協(xié)議的優(yōu)點在于可以處理高密度的網(wǎng)絡，具有很好的分布性。但是TORA協(xié)議是基于同步時鐘的，時鐘的不同可以導致路由的故障，并且當多個節(jié)點同時進行選路和刪除路由時會產(chǎn)生路由振蕩現(xiàn)象。3、 一些經(jīng)典的路由算法1. 平面路由協(xié)議（1）泛洪協(xié)議Flooding協(xié)議即洪泛協(xié)議，節(jié)點以洪泛廣播方式發(fā)送自身采集的消息或者收到的消息包，這些消息包會在網(wǎng)絡中

38、不斷進行洪泛廣播直至到達目的節(jié)點。其優(yōu)點在于實現(xiàn)簡單，不需要維護復雜的網(wǎng)絡拓撲信息，但缺點也顯而易見，盲目利用計算和通信資源，不適合傳感器網(wǎng)絡實際的應用需要。Gossiping協(xié)議是對Flooding協(xié)議的改進，在Gossiping協(xié)議中，節(jié)點將自身采集的信息和自己收到的數(shù)據(jù)消息，轉(zhuǎn)發(fā)給隨機選擇的下一跳節(jié)點，該協(xié)議很大程度上降低了洪泛協(xié)議的開銷，但是增加了網(wǎng)絡時延，且擴展性較差。 圖3.3 信息爆炸優(yōu)點：實現(xiàn)簡單，不需要為保持網(wǎng)絡拓撲信息和實現(xiàn)復雜的路由發(fā)現(xiàn)算法而消耗計算資源；適用于健壯性要求高的場合。不足：存在信息爆炸(Implosion)問題，即出現(xiàn)一個節(jié)點可能得到一個數(shù)據(jù)多個副本的現(xiàn)象，

39、如圖3-1所示。出現(xiàn)部分重疊(Overlap)現(xiàn)象，如果處于同一觀測環(huán)境的兩個相鄰同類傳感器節(jié)點同時對一個事件做出反應，二者采集的數(shù)據(jù)性質(zhì)相同，數(shù)值相近，那么，這兩個節(jié)點的鄰居節(jié)點將收到雙份數(shù)據(jù)副本。盲目使用資源，即擴散法不考慮各節(jié)點數(shù)量可用狀況因而無法做出相應的自適應路由選擇。（2）定向擴散該協(xié)議是一種以數(shù)據(jù)為中心的平面結構協(xié)議，且能夠同時承載多個應用。DD協(xié)議的最大特點是首次提出了網(wǎng)絡梯度的概念，并與數(shù)據(jù)融合算法相結合，能夠用較小的成本完成數(shù)據(jù)搜索的功能。定向擴散算法的主要思想是對網(wǎng)絡中的數(shù)據(jù)用一組屬性對來命名，并基于數(shù)據(jù)進行通信。其突出特點是引入了梯度來描述網(wǎng)絡中間節(jié)點在某方向繼續(xù)搜索以

40、獲得匹配數(shù)據(jù)的可能性。為建立路由，匯聚節(jié)點(Sink節(jié)點)向所有傳感器節(jié)點發(fā)送查詢請求興趣信息(Interest)，興趣信息Interest包括屬性列表、上報間隔、持續(xù)時間、地理區(qū)域等信息。沿途節(jié)點按需對各興趣信息Interest進行緩存與合并，并根據(jù)興趣信息Interest設計、創(chuàng)建包含數(shù)據(jù)上報率、下一跳等信息的梯度(gradient)，從而建立多條指向Sink節(jié)點的路徑。興趣信息Interest中的地理區(qū)域內(nèi)節(jié)點則按要求啟動監(jiān)測任務，并周期性地上報數(shù)據(jù)。源節(jié)點采集的數(shù)據(jù)首先在本地采用匯聚融合技術進行整合，然后在傳感器網(wǎng)絡中傳輸。Sink節(jié)點可在數(shù)據(jù)傳輸過程中通過對某條路徑發(fā)送上報間隔更小或

41、更大的興趣信息Interest，以增強或減弱數(shù)據(jù)上報率。該協(xié)議采用鄰節(jié)點間通信方式來避免維護全局拓撲，并采用查詢驅(qū)動數(shù)據(jù)傳送模式和局部數(shù)據(jù)聚集來減少網(wǎng)絡數(shù)據(jù)流，因而是一種高能效的協(xié)議。它的缺點是在需要連續(xù)傳送數(shù)據(jù)的應用中(如環(huán)境監(jiān)測等)不能很好的應用，其數(shù)據(jù)命名只能針對于特定的應用預先進行，同時初始查詢的擴散開銷也較大。圖3一2表示了定向擴散協(xié)議的路由建立過程。DD協(xié)議是以數(shù)據(jù)為中心的路由協(xié)議，所有通信都局限在鄰居節(jié)點之間，每個節(jié)點都具有收集數(shù)據(jù)，進行數(shù)據(jù)聚集和緩存數(shù)據(jù)的功能，這種特性減少了網(wǎng)絡數(shù)據(jù)流也降低了數(shù)據(jù)傳輸延遲。DD協(xié)議路徑創(chuàng)建靈活，且路徑恢復的局部算法設計使得系統(tǒng)對于網(wǎng)絡的動態(tài)拓撲

42、具有更強的適應性。按需驅(qū)動數(shù)據(jù)的傳送模式和不需要維護全局網(wǎng)絡拓撲結構，使得DD協(xié)議成為一種高能源有效性的協(xié)議。圖3.2 定向擴散（3）SARSAR(Sequential Assignment Routing)協(xié)議算法創(chuàng)建多顆樹，每顆樹的樹根都是Sink的一跳鄰居。在算法的初始階段，樹從根節(jié)點開始，不斷吸收新的節(jié)點加入。在樹延伸的過程中，將避免那些QoS不好及能量已經(jīng)消耗較多的節(jié)點。初始階段結束后，大多數(shù)節(jié)點都加入了某個樹，各節(jié)點只需要知道自己的上一跳鄰居，以轉(zhuǎn)發(fā)報文。在網(wǎng)絡工作過程中，一些樹可能由于中間節(jié)點能量耗盡而斷開，也可能有新的節(jié)點加入網(wǎng)絡而使網(wǎng)絡拓撲結構發(fā)生變化。所以網(wǎng)關周期性的發(fā)起“

43、重新建立路徑”的命令，以保證網(wǎng)絡的連通性和最優(yōu)的服務質(zhì)量。 （4）SPINSPIN(Sensor Protocol for Information via Negotiation)是一種以數(shù)據(jù)為中心的自適應通信路由協(xié)議，通過使用節(jié)點間的協(xié)商機制和資源自適應機制來解決擴散法存在的不足。為了避免出現(xiàn)擴散法的信息爆炸問題和部分重疊現(xiàn)象，傳感器節(jié)點在傳送數(shù)據(jù)之前彼此進行協(xié)商，協(xié)商制度可以確保傳輸有用數(shù)據(jù)。節(jié)點間通過發(fā)送元數(shù)據(jù)，即描述傳感器節(jié)點采集的數(shù)據(jù)屬性的數(shù)據(jù)，而不是采集的整個數(shù)據(jù)進行協(xié)商。由于元數(shù)據(jù)大小小于采集的數(shù)據(jù)，所以，傳輸元數(shù)據(jù)消耗的能量相對較少。為避免盲目使用資源，所有傳感器節(jié)點必須監(jiān)控各

44、自的能量變化情況。在傳輸或接收數(shù)據(jù)之前，每個節(jié)點都必須檢查各自可用的能量狀況，如果處于低能量水平，必須中止一些操作，比如充當數(shù)據(jù)中轉(zhuǎn)站(路由器)角色的一些數(shù)據(jù)轉(zhuǎn)發(fā)操作。SPIN有三種數(shù)據(jù)包類型，即ADV、REQ和DATA。ADV用于新數(shù)據(jù)廣播。當一個節(jié)點有數(shù)據(jù)可共享時，它可用ADV數(shù)據(jù)包(包含元數(shù)據(jù))對外廣播。REQ用于請求發(fā)送數(shù)據(jù)。當一個節(jié)點希望接收DATA數(shù)據(jù)包時，發(fā)送REQ數(shù)據(jù)包。DATA包含附上元數(shù)據(jù)頭(Meta-Data Header)的傳感器采集的數(shù)據(jù)的數(shù)據(jù)包。在發(fā)送一個DATA數(shù)據(jù)包之前，一個傳感器節(jié)點首先對外廣播ADV數(shù)據(jù)包；如果一個鄰居節(jié)點在收到ADV后有意愿接收該DATA數(shù)

45、據(jù)包，那么它向該節(jié)點發(fā)送一個REQ數(shù)據(jù)包，接著節(jié)點向該鄰居節(jié)點發(fā)送DATA數(shù)據(jù)包。類似地進行下去，DATA數(shù)據(jù)包可被傳輸?shù)竭h方匯聚節(jié)點或基站。圖3-4表示了SPIN協(xié)議的工作過程。圖3.4 spin工作流程2. 分層路由協(xié)議（1） LEACH低功耗自適應聚類路由算法Leach(low energy adaptive clustering hierarchy)是在無線傳感器網(wǎng)絡中提出的第一個層次型路由協(xié)議，是分簇式路由協(xié)議的代表，具有典型的研究價值。其后的大部分分簇式路由協(xié)議都是在它的基礎上發(fā)展而來的。與一般的平面多跳路由協(xié)議和靜態(tài)聚類算法相比，Leach可以將網(wǎng)絡生命周期延長15%，主要是通過

46、隨機選擇簇首節(jié)點，平均分擔中繼通信業(yè)務來實現(xiàn)。Leach定義了“輪”(round)的概念，并以“輪”為單位周期性工作。每一輪由初始化和穩(wěn)定工作兩個階段組成，為了使能耗最小化、降低初始化開銷，穩(wěn)定工作階段持續(xù)的時間比初始化階段長。初始化階段，網(wǎng)絡隨機選擇簇首，然后動態(tài)成簇；穩(wěn)定工作階段，節(jié)點將采集到的數(shù)據(jù)傳送至簇首，簇首經(jīng)過融合處理之后，發(fā)送到sink節(jié)點。持續(xù)工作一段時間以后，整個網(wǎng)絡進入下一輪工作周期，重新選擇簇首。1、 初始化階段在初始化階段，隨機選擇節(jié)點作為簇首節(jié)點，隨機性可以確保簇首的高能耗均勻地分攤到所有傳感器節(jié)點上；然后，成為簇首的節(jié)點向網(wǎng)絡廣播信息，其它節(jié)點根據(jù)接收到各簇首廣播信

47、息的強度來選擇所要加入的簇，并告知相應的簇首節(jié)點。1、簇首選舉辦法：節(jié)點產(chǎn)生一個0-1之間的隨機數(shù)，若當前輪中這個數(shù)值小于設定的閥值T(n)，則該節(jié)點成為簇首節(jié)點。T(n)值按如下公式計算：以1/p為輪數(shù)周期，在每個輪數(shù)周期中，每個節(jié)點都會當選為一次簇首。其中，p=k/N為期望的簇首節(jié)點數(shù)量在所有傳感器節(jié)點中的百分比，其中k為網(wǎng)絡中每輪需要產(chǎn)生的簇首數(shù)量；N為網(wǎng)絡中傳感器節(jié)點的總數(shù)；r為當前輪數(shù)；G為當前輪數(shù)周期中，在剩余輪中未成為簇首節(jié)點的傳感器節(jié)點組成的集合。在第0輪，即r=0時，每一個節(jié)點將會以相同的概率p成為簇首。經(jīng)過(1/p)-1輪后，T(n)的值變?yōu)?，這時還沒有擔當過簇首的那些節(jié)

48、點就被選擇為簇首。在經(jīng)過1/p輪后，所有的節(jié)點再次以開始平等的競選簇首。2、成簇節(jié)點當選簇首以后，便將當選的消息向網(wǎng)絡廣播。非簇首節(jié)點再根據(jù)接收到的各簇首節(jié)點廣播消息的強度，選擇接收強度最大的節(jié)點為自己的簇首，并告知相應簇首。當簇首接收到所有的加入信息后，會產(chǎn)生一個TDMA定時控制消息，并且通知該簇中所有節(jié)點，簇內(nèi)節(jié)點收到這個廣播消息后，在穩(wěn)定工作階段就會在各自的時間槽內(nèi)向簇首節(jié)點發(fā)送數(shù)據(jù)。Leach協(xié)議WSN節(jié)點成簇后，各簇分布如圖3.5所示：4.5 Leach 協(xié)議族分簇該圖所示網(wǎng)絡覆蓋區(qū)域被劃分成5個簇，圖中黑色節(jié)點代表簇首，白色節(jié)點為非簇首成員節(jié)點。二、穩(wěn)定工作階段在穩(wěn)定工作階段，傳感

49、器節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，并按各自TDMA分配的時隙向簇首發(fā)送，在簇首對數(shù)據(jù)進行必要的融合等處理之后，發(fā)送至網(wǎng)關。穩(wěn)定工作階段持續(xù)給定時間（遠長于初始化階段）后,網(wǎng)絡進入下一輪工作周期,重新選擇簇首。三、相關的Leach改進算法Leach算法假設網(wǎng)絡中所有的節(jié)點都能直接與簇首節(jié)點和終端節(jié)點通信，數(shù)據(jù)傳輸采用單跳路徑模式，因此不適用于監(jiān)測范圍較大的網(wǎng)絡；另外，對于節(jié)點數(shù)量較多、節(jié)點密度較大的網(wǎng)絡，部分簇首節(jié)點會因為簇內(nèi)數(shù)據(jù)量較多、能耗過大而較先死亡。可見Leach算法具有較多的局限性。在Leach算法基礎之上，研究人員陸續(xù)提出了一些較好的改進算法。Leach-C算法，采用集中式簇首選擇機制，該算法根據(jù)網(wǎng)絡全局信息包括節(jié)點地理位置、當前能量等，從網(wǎng)絡中選取K個最優(yōu)節(jié)點充當簇首，簇首選擇更加合理，但屬于典型的NP-hard問題,時間復雜度較大。Heed協(xié)議針對Leach算法簇首分布不均勻問題進行了改進。協(xié)議中以簇內(nèi)平均可達能量AMRP(average minimum reachability power)作為衡量簇內(nèi)通信成本的標準。節(jié)點以不同的初始概率CHprob發(fā)送競爭消息。初始化概率CHpro