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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、新自己的路由表，以維護(hù)一致的、及時的、準(zhǔn)確的路由信息。所以路由表可以準(zhǔn)確地反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，因此這種路由協(xié)議的時延較??；但是由于需要及時的更新路由信息，路由協(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é)點(diǎn)都需要維護(hù)一個路由表，路由表的表項(xiàng)包括目的節(jié)點(diǎn)、跳數(shù)、下一跳節(jié)點(diǎn)和目的節(jié)點(diǎn)號。其中目的節(jié)點(diǎn)號由目的節(jié)點(diǎn)分配，主要用于判別路由是否

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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