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

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

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

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

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

5、現(xiàn)了網(wǎng)絡(luò)的自動(dòng)組織和運(yùn)行。2. 自組織網(wǎng)絡(luò)特點(diǎn)無(wú)線自組織網(wǎng)絡(luò)具有無(wú)中心和自組織性。網(wǎng)絡(luò)中沒(méi)有絕對(duì)的控制中心，所有節(jié)點(diǎn)的地位平等，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)分布式算法來(lái)協(xié)調(diào)彼此的行為，無(wú)需人工干預(yù)和任何其它預(yù)置的網(wǎng)絡(luò)設(shè)施，可以在任何時(shí)刻任何地方快速展開(kāi)并自動(dòng)組網(wǎng)。由于網(wǎng)絡(luò)的分布式特征、節(jié)點(diǎn)的冗余性和不存在單點(diǎn)故障點(diǎn)，使得網(wǎng)絡(luò)的健壯性和抗毀性很好。所以與傳統(tǒng)網(wǎng)絡(luò)相比，無(wú)線自組織網(wǎng)絡(luò)有以下特性：1. 自動(dòng)配置：自動(dòng)配置是無(wú)線自組織網(wǎng)絡(luò)的一個(gè)特征，節(jié)點(diǎn)必須檢測(cè)其它節(jié)點(diǎn)以及它們可以提供的服務(wù)。由于網(wǎng)絡(luò)動(dòng)態(tài)變化，自動(dòng)配置過(guò)程需要確保網(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)、平面和分級(jí)），這依賴(lài)于網(wǎng)絡(luò)的類(lèi)型、底層的無(wú)線技術(shù)和應(yīng)用的需求。 2 .多跳性:由于節(jié)點(diǎn)發(fā)射功率的限制，其通信范圍有限。當(dāng)它要與其通信范圍之外的節(jié)點(diǎn)進(jìn)行通信時(shí)，需要中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)。另外， Adhoc網(wǎng)絡(luò)中的多跳是由普通節(jié)點(diǎn)協(xié)作完成的，而不需要專(zhuān)用的路由設(shè)備(如路由器)來(lái)完成。3.無(wú)中心和自組織性 :網(wǎng)絡(luò)中沒(méi)有絕對(duì)的控制中心，所有節(jié)點(diǎn)的地位平等，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)分布式算法來(lái)協(xié)調(diào)彼此的行為自組成網(wǎng)，無(wú)需人工干預(yù)和任何其它預(yù)置的網(wǎng)絡(luò)設(shè)施。由于網(wǎng)絡(luò)的分布式特征、節(jié)點(diǎn)的冗余性和不存在單點(diǎn)故障點(diǎn)，使得網(wǎng)絡(luò)的健壯性和抗毀性很好。4.動(dòng)態(tài)拓

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

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

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

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

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

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

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

14、。在AdHoc網(wǎng)絡(luò)當(dāng)中，無(wú)論采用平面結(jié)構(gòu)還是分級(jí)結(jié)構(gòu)有一點(diǎn)是共同的:所有站點(diǎn)共享一個(gè)物理信道。分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)雖然能夠限制簇內(nèi)部的路由信息向其它簇?cái)U(kuò)散，但是分簇和分級(jí)都只是限于站點(diǎn)間邏輯關(guān)系而言，并不能隔離站點(diǎn)對(duì)物理信道的競(jìng)爭(zhēng)。當(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ú)線信道是空閑還是正被一個(gè)隱藏終端使用，物理信道沖突比有線以太網(wǎng)和單跳無(wú)線網(wǎng)絡(luò)中更復(fù)雜。4.無(wú)線傳感自組織網(wǎng)的應(yīng)用無(wú)線自組織網(wǎng)絡(luò)的許多優(yōu)良特性為它在民用和軍事通信領(lǐng)域占據(jù)一席之地提供了有

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

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

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

18、的多跳轉(zhuǎn)發(fā)能力擴(kuò)大蜂窩移動(dòng)通信系統(tǒng)的覆蓋范圍、均衡相鄰小區(qū)的業(yè)務(wù)、提高小區(qū)邊緣的數(shù)據(jù)速率等。6.商業(yè)應(yīng)用：組建家庭無(wú)線網(wǎng)絡(luò)、無(wú)線數(shù)據(jù)網(wǎng)絡(luò)、移動(dòng)醫(yī)療監(jiān)護(hù)系統(tǒng)和無(wú)線設(shè)備網(wǎng)絡(luò)，開(kāi)展移動(dòng)和可攜帶計(jì)算以及無(wú)所不在的通信業(yè)務(wù)等。7.其它應(yīng)用:考慮到Adhoc網(wǎng)絡(luò)具有很多優(yōu)良特性，它的應(yīng)用領(lǐng)域還有很多，這需要我們進(jìn)一步去挖掘。比如它可以用來(lái)擴(kuò)展現(xiàn)有蜂窩移動(dòng)通信系統(tǒng)的覆蓋范圍，實(shí)現(xiàn)地鐵和隧道等場(chǎng)合的無(wú)線覆蓋，實(shí)現(xiàn)汽車(chē)和飛機(jī)等交通工具之間的通信，用于輔助教學(xué)和構(gòu)建未來(lái)的移動(dòng)無(wú)線城域網(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)的移動(dòng)性，網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)可能發(fā)生改變，因此路由算法要能滿(mǎn)足動(dòng)態(tài)路由的要求。選擇和設(shè)計(jì)一個(gè)高效的路由算法對(duì)于一個(gè)ad-hoc網(wǎng)絡(luò)來(lái)說(shuō)顯得非常重要，路由算法的好壞直接影響到ad-hoc網(wǎng)絡(luò)的性能。Ad-hoc路由算法設(shè)計(jì)的首要問(wèn)題是要求簡(jiǎn)單、高效并且控制開(kāi)銷(xiāo)小。本章主要研究ad-hoc路由算法的設(shè)計(jì)。路由算法的任務(wù)是在節(jié)點(diǎn)和節(jié)點(diǎn)之間建立路由，實(shí)現(xiàn)可靠地?cái)?shù)據(jù)傳遞，一個(gè)完整的路由算法應(yīng)包括路由方式、路由發(fā)現(xiàn)和路由維護(hù)等內(nèi)容。要設(shè)計(jì)一個(gè)好的路由算法通常有以下的一個(gè)或多個(gè)設(shè)計(jì)目標(biāo):1.簡(jiǎn)單、最優(yōu)化、高效、低耗、控制開(kāi)銷(xiāo)小自組織無(wú)線傳輸帶寬有限，傳送控制開(kāi)銷(xiāo)不可避免地消耗掉一

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

21、況。3.健壯、穩(wěn)定、靈活路由算法必須健壯，即在出現(xiàn)不正?；虿豢深A(yù)見(jiàn)事件的情況下仍能正常處理，例如硬件故障、高負(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)鏈路中斷時(shí)，路由算法要迅速選擇次佳的路徑。2.網(wǎng)絡(luò)的組成部分無(wú)線傳感器網(wǎng)絡(luò)是由大量節(jié)點(diǎn)以自組織形式構(gòu)成的網(wǎng)絡(luò)。在被監(jiān)視區(qū)域內(nèi)，節(jié)點(diǎn)被任意散落后，每個(gè)節(jié)點(diǎn)都可以收集數(shù)據(jù)，網(wǎng)絡(luò)中節(jié)點(diǎn)通過(guò)自組織快速形成一個(gè)無(wú)線網(wǎng)絡(luò)，它們之間相互協(xié)作進(jìn)行數(shù)據(jù)收集，融合和傳遞。如圖2.1所示，典型的無(wú)線傳感器網(wǎng)絡(luò)是由傳感器節(jié)點(diǎn)、簇節(jié)點(diǎn) (clusternode)、匯聚節(jié)點(diǎn)(也稱(chēng)為網(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)。首先，每個(gè)節(jié)點(diǎn)將自己收集的數(shù)據(jù)傳送給自己傳輸范圍內(nèi)的簇節(jié)點(diǎn)(或可到達(dá)簇節(jié)點(diǎn)的路由節(jié)點(diǎn))，各個(gè)簇節(jié)點(diǎn)通過(guò)多跳中繼方式將監(jiān)測(cè)數(shù)據(jù)傳到sink節(jié)點(diǎn)，最終通過(guò)Internet或衛(wèi)星通訊網(wǎng)傳送到監(jiān)控中心，最終實(shí)現(xiàn)任務(wù)管理節(jié)點(diǎn)(觀察者)與傳感器之間的通信。圖2.1無(wú)線傳感器網(wǎng)絡(luò)是在移動(dòng)Ad一Hoc網(wǎng)絡(luò)的基礎(chǔ)上發(fā)展起來(lái)的，在自組織和多跳通信等方面與移動(dòng)Ad一Hoc網(wǎng)絡(luò)在某些方面具有一定相似性。但無(wú)線傳感器網(wǎng)絡(luò)具有自己的特點(diǎn)以及局限性，主要表現(xiàn)在:(1)傳感器節(jié)點(diǎn)體積小，成本低，這是無(wú)線傳感器網(wǎng)絡(luò)的一大

23、特點(diǎn)和標(biāo)志。同時(shí)也應(yīng)看到，正由于節(jié)點(diǎn)體積小，傳感器節(jié)點(diǎn)的使用(包括電源和時(shí)間)是有限的。如圖2.1所示，無(wú)線傳感器網(wǎng)絡(luò)的多跳中繼通信，使得越靠近sink節(jié)點(diǎn)，節(jié)點(diǎn)承擔(dān)的流量就越大，通信時(shí)間越長(zhǎng)，能耗也越大。關(guān)鍵節(jié)點(diǎn)過(guò)早能量耗盡，即使其它節(jié)點(diǎn)能量充足，網(wǎng)絡(luò)仍然會(huì)因?yàn)橥ㄐ挪粫扯率拐麄€(gè)區(qū)域通信癱瘓。(2)不同于一般網(wǎng)絡(luò)的下TCP/IP協(xié)議，無(wú)線傳感器網(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ù);傳輸層提供差錯(cuò)控制和流量控

24、制;應(yīng)用層由各種傳感器網(wǎng)絡(luò)應(yīng)用軟件系統(tǒng)構(gòu)成，可以實(shí)現(xiàn)不同的應(yīng)用目的。(3)無(wú)線傳感器網(wǎng)絡(luò)是動(dòng)態(tài)自組織的。由于節(jié)點(diǎn)的有限性，無(wú)線傳感器網(wǎng)絡(luò)中時(shí)常有節(jié)點(diǎn)失效或新節(jié)點(diǎn)的補(bǔ)入，因此節(jié)點(diǎn)之間是不斷以自組織方式構(gòu)成新的傳輸路徑，確保網(wǎng)絡(luò)的暢通。3. 節(jié)點(diǎn)結(jié)構(gòu)組成無(wú)線傳感器網(wǎng)絡(luò)的基本單位是無(wú)線傳感器節(jié)點(diǎn)，它是構(gòu)成無(wú)線傳感器網(wǎng)絡(luò)的基礎(chǔ)平臺(tái)，節(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ú)線傳感器網(wǎng)絡(luò)的組成不盡相同，但一般是由傳感單元(由傳感器、模數(shù)轉(zhuǎn)換功能

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

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

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

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

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

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

31、控制信息的開(kāi)銷(xiāo)，但是它的不足在于難以適應(yīng)速度變化快的移動(dò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)用來(lái)控制一組節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)，網(wǎng)關(guān)節(jié)點(diǎn)是兩個(gè)簇之間的節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)要發(fā)送分組時(shí)，這個(gè)分組首先到達(dá)該發(fā)送節(jié)點(diǎn)的簇首節(jié)點(diǎn)，然后簇首節(jié)點(diǎn)把這個(gè)分組通過(guò)網(wǎng)關(guān)節(jié)點(diǎn)轉(zhuǎn)發(fā)給另一個(gè)簇首節(jié)點(diǎn)，不斷重復(fù)這個(gè)過(guò)程直到分組到達(dá)目的節(jié)點(diǎn)。因此，每個(gè)節(jié)點(diǎn)都必須有其簇成員的路由表。CSGR利用DSDV作為其底層路由選擇機(jī)制，并針對(duì)分級(jí)網(wǎng)絡(luò)做了適當(dāng)?shù)母倪M(jìn)，尋路是通過(guò)簇首節(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ū)動(dòng)路由協(xié)議，在網(wǎng)絡(luò)的節(jié)點(diǎn)中保存路由信息。每個(gè)節(jié)點(diǎn)保存在路由表中的信息如下：距離、路由、鏈路開(kāi)銷(xiāo)和重傳消息的列表(MRL)。MRL記錄關(guān)于消息序列號(hào)、重傳計(jì)數(shù)器、每一個(gè)鄰節(jié)點(diǎn)正確應(yīng)答所需的標(biāo)識(shí)和更新消息的更新列表等信息，這就使得節(jié)點(diǎn)可以決定何時(shí)發(fā)送更新消息以及發(fā)送給哪個(gè)節(jié)點(diǎn)。更新消息包括目的節(jié)點(diǎn)的地址、到目的節(jié)點(diǎn)的距離和目的節(jié)點(diǎn)的上游節(jié)點(diǎn)。然后鄰節(jié)點(diǎn)就修改自己的路由表并試圖通過(guò)預(yù)備的節(jié)點(diǎn)建立新的路由。WRP的優(yōu)點(diǎn)就是當(dāng)

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

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

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

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

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

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

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

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

41、更大的興趣信息Interest，以增強(qiáng)或減弱數(shù)據(jù)上報(bào)率。該協(xié)議采用鄰節(jié)點(diǎn)間通信方式來(lái)避免維護(hù)全局拓?fù)?，并采用查?xún)驅(qū)動(dòng)數(shù)據(jù)傳送模式和局部數(shù)據(jù)聚集來(lái)減少網(wǎng)絡(luò)數(shù)據(jù)流，因而是一種高能效的協(xié)議。它的缺點(diǎn)是在需要連續(xù)傳送數(shù)據(jù)的應(yīng)用中(如環(huán)境監(jiān)測(cè)等)不能很好的應(yīng)用，其數(shù)據(jù)命名只能針對(duì)于特定的應(yīng)用預(yù)先進(jìn)行，同時(shí)初始查詢(xún)的擴(kuò)散開(kāi)銷(xiāo)也較大。圖3一2表示了定向擴(kuò)散協(xié)議的路由建立過(guò)程。DD協(xié)議是以數(shù)據(jù)為中心的路由協(xié)議，所有通信都局限在鄰居節(jié)點(diǎn)之間，每個(gè)節(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)對(duì)于網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)?/p>

42、具有更強(qiáng)的適應(yīng)性。按需驅(qū)動(dòng)數(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)建多顆樹(shù)，每顆樹(shù)的樹(shù)根都是Sink的一跳鄰居。在算法的初始階段，樹(shù)從根節(jié)點(diǎn)開(kāi)始，不斷吸收新的節(jié)點(diǎn)加入。在樹(shù)延伸的過(guò)程中，將避免那些QoS不好及能量已經(jīng)消耗較多的節(jié)點(diǎn)。初始階段結(jié)束后，大多數(shù)節(jié)點(diǎn)都加入了某個(gè)樹(shù)，各節(jié)點(diǎn)只需要知道自己的上一跳鄰居，以轉(zhuǎn)發(fā)報(bào)文。在網(wǎng)絡(luò)工作過(guò)程中，一些樹(shù)可能由于中間節(jié)點(diǎn)能量耗盡而斷開(kāi)，也可能有新的節(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é)議，通過(guò)使用節(jié)點(diǎn)間的協(xié)商機(jī)制和資源自適應(yīng)機(jī)制來(lái)解決擴(kuò)散法存在的不足。為了避免出現(xiàn)擴(kuò)散法的信息爆炸問(wèn)題和部分重疊現(xiàn)象，傳感器節(jié)點(diǎn)在傳送數(shù)據(jù)之前彼此進(jìn)行協(xié)商，協(xié)商制度可以確保傳輸有用數(shù)據(jù)。節(jié)點(diǎn)間通過(guò)發(fā)送元數(shù)據(jù)，即描述傳感器節(jié)點(diǎn)采集的數(shù)據(jù)屬性的數(shù)據(jù)，而不是采集的整個(gè)數(shù)據(jù)進(jìn)行協(xié)商。由于元數(shù)據(jù)大小小于采集的數(shù)據(jù)，所以，傳輸元數(shù)據(jù)消耗的能量相對(duì)較少。為避免盲目使用資源，所有傳感器節(jié)點(diǎn)必須監(jiān)控各

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

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

46、隨機(jī)選擇簇首節(jié)點(diǎn)，平均分擔(dān)中繼通信業(yè)務(wù)來(lái)實(shí)現(xiàn)。Leach定義了“輪”(round)的概念，并以“輪”為單位周期性工作。每一輪由初始化和穩(wěn)定工作兩個(gè)階段組成，為了使能耗最小化、降低初始化開(kāi)銷(xiāo)，穩(wěn)定工作階段持續(xù)的時(shí)間比初始化階段長(zhǎng)。初始化階段，網(wǎng)絡(luò)隨機(jī)選擇簇首，然后動(dòng)態(tài)成簇；穩(wěn)定工作階段，節(jié)點(diǎn)將采集到的數(shù)據(jù)傳送至簇首，簇首經(jīng)過(guò)融合處理之后，發(fā)送到sink節(jié)點(diǎn)。持續(xù)工作一段時(shí)間以后，整個(gè)網(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)度來(lái)選擇所要加入的簇，并告知相應(yīng)的簇首節(jié)點(diǎn)。1、簇首選舉辦法：節(jié)點(diǎn)產(chǎn)生一個(gè)0-1之間的隨機(jī)數(shù)，若當(dāng)前輪中這個(gè)數(shù)值小于設(shè)定的閥值T(n)，則該節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。T(n)值按如下公式計(jì)算：以1/p為輪數(shù)周期，在每個(gè)輪數(shù)周期中，每個(gè)節(jié)點(diǎn)都會(huì)當(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時(shí)，每一個(gè)節(jié)點(diǎn)將會(huì)以相同的概率p成為簇首。經(jīng)過(guò)(1/p)-1輪后，T(n)的值變?yōu)?，這時(shí)還沒(méi)有擔(dān)當(dāng)過(guò)簇首的那些節(jié)

48、點(diǎn)就被選擇為簇首。在經(jīng)過(guò)1/p輪后，所有的節(jié)點(diǎn)再次以開(kāi)始平等的競(jìng)選簇首。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)簇首接收到所有的加入信息后，會(huì)產(chǎn)生一個(gè)TDMA定時(shí)控制消息，并且通知該簇中所有節(jié)點(diǎn)，簇內(nèi)節(jié)點(diǎn)收到這個(gè)廣播消息后，在穩(wěn)定工作階段就會(huì)在各自的時(shí)間槽內(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個(gè)簇，圖中黑色節(jié)點(diǎn)代表簇首，白色節(jié)點(diǎn)為非簇首成員節(jié)點(diǎn)。二、穩(wěn)定工作階段在穩(wěn)定工作階段，傳感

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