【文章內(nèi)容簡(jiǎn)介】 GAGIS。其中TEEN和PEGAGIS都是由LEACH發(fā)展而來的，本文以LEACH為例來說明該類路由協(xié)議的基本思想。上述三種均是單等級(jí)路由協(xié)議，Estrin等研究人員又設(shè)計(jì)了多等級(jí)路由協(xié)議，其基本思想大致可認(rèn)為是一種遞歸的單等級(jí)路由協(xié)議構(gòu)成的。I EACH 的基本思想是將整個(gè)網(wǎng)絡(luò)劃分為不同的簇，簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)發(fā)送和接收由簇頭負(fù)責(zé)。因而其關(guān)鍵之處就是如何選取簇頭。LEACH采用輪(round)的方法選取簇頭，在每輪內(nèi)的簇頭由各節(jié)點(diǎn)競(jìng)爭(zhēng)擔(dān)任。一旦某個(gè)節(jié)點(diǎn)成為簇頭后，就穩(wěn)定地?fù)?dān)任簇頭一定的時(shí)間，然后進(jìn)行下一輪的簇頭選取。簇頭的選取過程是：每個(gè)節(jié)點(diǎn)選取隨機(jī)產(chǎn)生一個(gè)0～ 1之間的數(shù)，然后和下面的公式計(jì)算的數(shù)字進(jìn)行比較，如果大于計(jì)算的值，則發(fā)送報(bào)文聲明其為簇頭，各個(gè)節(jié)點(diǎn)根據(jù)收到簇頭發(fā)送報(bào)文的信號(hào)強(qiáng)弱決定其加入哪個(gè)簇，通過一個(gè)報(bào)告報(bào)文告訴簇頭。其中計(jì)算公式如下：其中： 節(jié)點(diǎn)中成為簇頭的百分?jǐn)?shù)；r 當(dāng)前的輪數(shù)；G 在最后1／p輪中沒有被選為簇頭的節(jié)點(diǎn)集合。所以，該方法可以保證每個(gè)節(jié)點(diǎn)在1／P輪內(nèi)可以有一次機(jī)會(huì)成為簇頭。LEACH可以在相當(dāng)程度上節(jié)省節(jié)點(diǎn)能耗，與一般協(xié)議相比，至少可以使網(wǎng)絡(luò)生命周期延長(zhǎng)15 ；但是LEACH中每個(gè)簇頭可以和sink直接通信的假定并不是在任何情況都可以成立的，因而限制了該算法的應(yīng)用。但是，I EACH 等層次算法具有較好的可擴(kuò)展性，在網(wǎng)絡(luò)規(guī)模很大的情況下也可以正常地工作。 基于平面的路由協(xié)議此類路由協(xié)議和傳統(tǒng)的路由協(xié)議非常接近，借用了很多傳統(tǒng)有線網(wǎng)絡(luò)的路由協(xié)議的思想，認(rèn)為所有節(jié)點(diǎn)是平等的。代表性的路由協(xié)議主要是flood—ing Gossipin g、SPIN_j 和SAR等。圖5 SPIN數(shù)據(jù)轉(zhuǎn)發(fā)其中SPIN通過三種報(bào)文進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，如圖5所示。如果A有數(shù)據(jù)轉(zhuǎn)發(fā)，A通過一個(gè)ADV報(bào)文廣播給其鄰居B(如圖5．a(chǎn))，B通過REQ報(bào)文響應(yīng)如果B愿意接收該報(bào)文(如圖5．b)，A將數(shù)據(jù)發(fā)送給B(如圖5．c)，然后B以同樣的方式發(fā)送其收到的報(bào)文。SPIN主要思想是通過協(xié)商的方式進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，如果節(jié)點(diǎn)不希望接收數(shù)據(jù)，節(jié)點(diǎn)只需不發(fā)送REQ報(bào)文即可實(shí)現(xiàn)，如圖5．e所示。Gossiping是對(duì)Flooding的改進(jìn)，Gossiping在選取下一跳路徑時(shí)不是將報(bào)文發(fā)送給其所有的鄰居節(jié)點(diǎn)，而是隨機(jī)選取一個(gè)鄰居節(jié)點(diǎn)發(fā)送過去，相對(duì)Flooding而言，保留算法簡(jiǎn)單的優(yōu)點(diǎn)，但是路徑會(huì)變得更長(zhǎng)些。而SAR則是類似于有線網(wǎng)絡(luò)內(nèi)的帶有QoS的路由算法，路徑選取時(shí)考慮到了功耗、分組優(yōu)先級(jí)等附件條件進(jìn)行選路，并采用多路徑方法和局部恢復(fù)的策略防止路徑失效時(shí)重新查找路徑而帶來的開銷。 基于位置的路由協(xié)議此類路由協(xié)議是自組織無線網(wǎng)絡(luò)所特有的，由于GPS定位技術(shù)的發(fā)展，使得節(jié)點(diǎn)只需一個(gè)簡(jiǎn)單的接收裝置就可以得知其精確的位置信息，研究人員據(jù)此設(shè)計(jì)了一些基于位置的路由算法。代表性的路由協(xié)議包括：Rumor Routing 、GEAR、TTDD 和GPSR。本文以Rumor Routing(RR，圖6)為例說明其基本思想。對(duì)應(yīng)此類路由協(xié)議，其前提假定是網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)都可以得知其精確的位置信息。對(duì)于RumorRouting而言，其路徑選取可以描述如下：在事件域(Event)中的節(jié)點(diǎn)發(fā)出代理(Agent)報(bào)文通告其探知的數(shù)據(jù)類型，同時(shí)需要數(shù)據(jù)的sink也發(fā)出代理報(bào)文通告其所需的數(shù)據(jù)類型。同時(shí)，中間節(jié)點(diǎn)維持一個(gè)相應(yīng)的表(Event，Distance，Dir)，代理在轉(zhuǎn)發(fā)的時(shí)候，根據(jù)表進(jìn)行同步驗(yàn)證找到一條更好的路。顯然一旦兩種代理走過的路徑相交，就表明已經(jīng)有了一條從源到目的的路由。為了保證代理走過的路徑相交，已經(jīng)證明，源和目的分別隨機(jī)選取5個(gè)方向轉(zhuǎn)發(fā)報(bào)文將有99．7 的相交概率。而TTDD 是根據(jù)節(jié)點(diǎn)位置信息構(gòu)造網(wǎng)格(grid)，由網(wǎng)格頂點(diǎn)復(fù)雜網(wǎng)格內(nèi)節(jié)點(diǎn)的行為；GEAR根據(jù)節(jié)點(diǎn)位置信息采用遞歸方法進(jìn)行報(bào)文轉(zhuǎn)發(fā)。此類路由協(xié)議，一般具有算法簡(jiǎn)單，易于實(shí)現(xiàn)的特點(diǎn)，對(duì)應(yīng)傳感器網(wǎng)絡(luò)而言是一種比較理想的路由協(xié)議。第四章 無線傳感器網(wǎng)絡(luò)路由協(xié)議比較研究與發(fā)展 前言普遍的網(wǎng)絡(luò)化、微機(jī)電系統(tǒng)(MEMS)和片上系統(tǒng)(SOC)的迅速發(fā)展，以及這三方面的高度集成孕育出了許多新的信息獲取和處理模式，傳感器網(wǎng)絡(luò)就是其中一例。在研究初期，人們一度認(rèn)為成熟的Internet技術(shù)加上Ad—hoc路由機(jī)制對(duì)傳感器網(wǎng)絡(luò)的設(shè)計(jì)是足夠充分的，但深人的研究表明：傳感器網(wǎng)絡(luò)有著與傳統(tǒng)網(wǎng)絡(luò)明顯不同的技術(shù)要求。前者以數(shù)據(jù)為中心，后者以傳輸數(shù)據(jù)為目的。為了適應(yīng)廣泛的應(yīng)用程序，傳統(tǒng)網(wǎng)絡(luò)的設(shè)計(jì)遵循著“端到端”的邊緣論思想，強(qiáng)調(diào)將一切與功能相關(guān)的處理都放在網(wǎng)絡(luò)的端系統(tǒng)上，中間節(jié)點(diǎn)僅僅負(fù)責(zé)數(shù)據(jù)分組的轉(zhuǎn)發(fā)，對(duì)于傳感器網(wǎng)絡(luò)，這未必是一種合理的選擇。在無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)中，網(wǎng)絡(luò)層中的路由協(xié)議非常重要，但是隨著應(yīng)用和網(wǎng)絡(luò)基礎(chǔ)結(jié)構(gòu)的不同而有所差異。網(wǎng)絡(luò)層主要的目標(biāo)是：尋找用于傳感器網(wǎng)絡(luò)的高能效的路由建立和可靠的數(shù)據(jù)傳輸方法，從而使網(wǎng)絡(luò)壽命最長(zhǎng)。由于傳感器網(wǎng)絡(luò)有幾個(gè)不同于傳統(tǒng)無線Ad—hoc網(wǎng)絡(luò)的特點(diǎn)，因此它的路由非常有挑戰(zhàn)性。首先，由于節(jié)點(diǎn)眾多，不可能建立一個(gè)全局的地址機(jī)制；其次，產(chǎn)生的數(shù)據(jù)流量有顯著的冗余性，因此可以利用數(shù)據(jù)聚合來提高能量和帶寬的利用率；第三，節(jié)點(diǎn)能量和處理存儲(chǔ)能，需要精細(xì)的資源管理；最后，由于網(wǎng)絡(luò)拓?fù)渥兓l繁，需要路由協(xié)議有很好的魯棒性和可擴(kuò)展性。本章中著重對(duì)路由協(xié)議進(jìn)行了一些比較研究，以及探討了無線傳感器網(wǎng)絡(luò)路由協(xié)議的發(fā)展趨勢(shì)。 路協(xié)議比較研究 【Flooding) 傳統(tǒng)模式Flooding and gossiping這種算法L4J也是傳統(tǒng)網(wǎng)絡(luò)中最基本的路由方式，不需要知道網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和使用任何路由算法。每個(gè)傳感器節(jié)點(diǎn)把自己接收到的packet發(fā)送給所有它的鄰居節(jié)點(diǎn)，這個(gè)過程一直重復(fù)直到該分組到達(dá)sink節(jié)點(diǎn)或者該分組的生命到期(1vrL，在傳感器網(wǎng)絡(luò)里面通常定義為最大跳數(shù))。Gossiping 算法改進(jìn)了Flooding 過程，每個(gè)傳感器節(jié)點(diǎn)只把自己接收到的packet隨機(jī)發(fā)送給它的某個(gè)鄰居節(jié)點(diǎn)，其他不變。這種方式雖然實(shí)現(xiàn)簡(jiǎn)單，但是并不實(shí)用于相關(guān)應(yīng)用程序，而且還很容易帶來內(nèi)爆(implosion)和交疊(overlap)問題。(event—driven) SPIN 算法(Sensor Protocols forInformation via Negotiation)該協(xié)議[5]注意到鄰近的節(jié)點(diǎn)所感知的數(shù)據(jù)具有相似性，所以希望通過節(jié)點(diǎn)間協(xié)商(Negotiation)的方式，sensor節(jié)點(diǎn)只廣播其它節(jié)點(diǎn)所沒有的數(shù)據(jù)以減少冗余數(shù)據(jù)，從而有效減少能量消耗。同時(shí)，又提出使用元數(shù)據(jù)(metadata，是對(duì)節(jié)點(diǎn)感知數(shù)據(jù)的抽象描述)而非原始感知數(shù)據(jù)來交換節(jié)點(diǎn)感知事件的信息。SPIN算法使用三種報(bào)文數(shù)據(jù)：ADV、REQ和DAT ADV報(bào)文用于已感知事件發(fā)生的sensor節(jié)點(diǎn)給自己相鄰節(jié)點(diǎn)廣播元數(shù)據(jù)；REQ報(bào)文用于sensor節(jié)點(diǎn)通知某鄰節(jié)點(diǎn)開始發(fā)送事件原始數(shù)據(jù)；DATA報(bào)文是指事件原始數(shù)據(jù)。如圖2所示，在SPIN一1中，當(dāng)某個(gè)sensor節(jié)點(diǎn)感知事件之后，主動(dòng)給其鄰節(jié)點(diǎn)廣播描述該事件的元數(shù)據(jù)ADV報(bào)文，該過程重復(fù)直至ADV報(bào)文泛洪到所有網(wǎng)絡(luò)中的sensor節(jié)點(diǎn)，其他sensor節(jié)點(diǎn)根據(jù)保存的多個(gè)ADV報(bào)文，當(dāng)需要獲取某個(gè)數(shù)據(jù)報(bào)文時(shí)，則廣播REQ報(bào)文，源節(jié)點(diǎn)收到該報(bào)文后，將DATA報(bào)文廣播。文獻(xiàn)[6]SPIN2考慮了sensor節(jié)點(diǎn)剩余能量值，當(dāng)其剩余能量低于某個(gè)門限值就不再參與任何報(bào)文的轉(zhuǎn)發(fā)，僅能夠接收來自其它鄰節(jié)點(diǎn)的報(bào)文和發(fā)出REQ報(bào)文。該協(xié)議族算法中，sensor節(jié)點(diǎn)不維護(hù)相鄰節(jié)點(diǎn)的信息，故一定程度上能適應(yīng)節(jié)點(diǎn)移動(dòng)的情況；在能耗方面，模擬結(jié)果證明比傳統(tǒng)模式減少一半以上。不過，該算法不能確保數(shù)據(jù)一定能到達(dá)目標(biāo)節(jié)點(diǎn)，尤其是不適用于高密度節(jié)點(diǎn)分布的情況。圖2 SPIN協(xié)議工作流程在該算法中[7]，每個(gè)sensor節(jié)點(diǎn)都維持一個(gè)事件列表，其表項(xiàng)包含事件的基本描述、播報(bào)該事件的源節(jié)點(diǎn)、最先傳遞該事件的上一跳sensor節(jié)點(diǎn)；另外，引人了一個(gè)具有長(zhǎng)生命周期的報(bào)文，Agent，用于源節(jié)點(diǎn)廣播感知事件的描述信息并在網(wǎng)絡(luò)中傳播。該算法其本質(zhì)如同SPIN算法，與之不同的是，該算法通過sensor節(jié)點(diǎn)維護(hù)的事件列表信息，能夠維護(hù)一條與源節(jié)點(diǎn)間之間的路徑，所以經(jīng)過初始化的泛洪后，相應(yīng)路由信息即建立起來了，從而避免了SPIN協(xié)議中的大量泛洪過程，達(dá)到顯著節(jié)省能量的目的。該算法主要適用于具有大量查詢和少量事件的應(yīng)用場(chǎng)景，如果網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變動(dòng)，該算法性能即大幅下降。該算法同時(shí)也是下文將介紹的Directed Diffusion算法的一個(gè)改進(jìn)。．2 Energyaware routing該算法L8J 8的主要思路是考慮到如果所有報(bào)文都在某幾條最優(yōu)路徑傳輸，會(huì)造成該路徑相關(guān)sensor節(jié)點(diǎn)能量很快被耗盡的情況，在建立路由的過程中，同時(shí)建立多條次優(yōu)路徑和概率模型，最終根據(jù)每條路徑對(duì)應(yīng)的概率值進(jìn)行報(bào)文轉(zhuǎn)發(fā)以實(shí)現(xiàn)初步的網(wǎng)絡(luò)負(fù)載均衡，從而達(dá)到提高網(wǎng)絡(luò)整體生命期的目的。不足的是，該算法在建立多條路徑的時(shí)候需要交換相鄰節(jié)點(diǎn)的位置信息以及對(duì)節(jié)點(diǎn)進(jìn)行統(tǒng)一的編址，這在很大程度上加大了路由建立過程的代價(jià)。該算法對(duì)于節(jié)點(diǎn)失效的考慮不充分，也不適合sensor節(jié)點(diǎn)具有移動(dòng)的特性。 Querydriven Directed Diffusion該算法 J的核心是：對(duì)數(shù)據(jù)使用了命名后在sensor節(jié)點(diǎn)間進(jìn)行直接傳輸，數(shù)據(jù)傳輸由sink節(jié)點(diǎn)發(fā)起。如圖所示，該算法引人interest報(bào)文，以屬性一值的方式，包含了查詢的相關(guān)屬性，每個(gè)interest報(bào)文還包含了gradient的字段，該字段在其傳播過程中不斷更新，由sensor節(jié)點(diǎn)在本地記錄所有傳播該interest的上一跳sensor節(jié)點(diǎn)，記錄的節(jié)點(diǎn)順序按照收到轉(zhuǎn)發(fā)報(bào)文的次序。interest由sink節(jié)點(diǎn)發(fā)出，通過泛洪的方式到達(dá)傳感器網(wǎng)絡(luò)中所有sensor節(jié)點(diǎn)，sensor節(jié)點(diǎn)在本地維持了interest的緩存。如此，每個(gè)節(jié)點(diǎn)都可以通過本次緩存的interest報(bào)文維持與sink節(jié)點(diǎn)間的通路。Sensor節(jié)點(diǎn)感知的數(shù)據(jù)如果符合interest查詢要求，則沿該路徑進(jìn)行轉(zhuǎn)發(fā)。圖3 Dir~ted Diffusion協(xié)議工作流程文獻(xiàn)[9]中，按照選取最先轉(zhuǎn)發(fā)interest報(bào)文的鄰居節(jié)點(diǎn)原則，由源節(jié)點(diǎn)發(fā)送一個(gè)報(bào)文來建立最優(yōu)路徑，路徑建立后，sink節(jié)點(diǎn)周期性發(fā)送一個(gè)reinforcement報(bào)文來維護(hù)它以及重復(fù)該算法進(jìn)行路徑修復(fù)的過程。該算法也允許路由選擇多條通路。該算法最顯著的特點(diǎn)是，預(yù)先廣播查詢事件的interest報(bào)文，通過泛洪的方式，來建立sink節(jié)點(diǎn)到所有sensor節(jié)點(diǎn)間的路由。但是，這同時(shí)也局限了該算法的應(yīng)用范圍，如應(yīng)用要求sink 節(jié)點(diǎn)周期性獲得多種類型的感知數(shù)據(jù)，則在每個(gè)sensor節(jié)點(diǎn)維持interest緩存的代價(jià)急劇增加。 Gradientbased Routing該算法[10]是