第5章路由協(xié)議

第五章無線傳感網(wǎng)路由協(xié)議

路由協(xié)議是解決數(shù)據(jù)傳輸路徑問題，它完成將數(shù)據(jù)分組從源節(jié)點(diǎn)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的功能，是無線傳感網(wǎng)的關(guān)鍵技術(shù)之一。與傳統(tǒng)通信網(wǎng)絡(luò)不同，無線傳感網(wǎng)中沒有基礎(chǔ)設(shè)施和全網(wǎng)統(tǒng)一的控制中心，是一種分布式的自組織網(wǎng)絡(luò)，必須采取分布式的方式獲取網(wǎng)絡(luò)拓?fù)湫畔?。由于無線傳感網(wǎng)是由大量的結(jié)構(gòu)簡單的低成本、能量受限、通信能力受限以及存儲和處理能力受限的節(jié)點(diǎn)構(gòu)成，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化。所以，傳統(tǒng)的自組織網(wǎng)絡(luò)的路由協(xié)議不能直接使用，必須針對傳感網(wǎng)的特點(diǎn)和應(yīng)用設(shè)計高能效的傳感網(wǎng)路由協(xié)議。本章針對傳感網(wǎng)的特點(diǎn)，分析了路由協(xié)議考慮的因素以及分類方式，分別介紹了能量感知路由協(xié)議、平面路由協(xié)議、分層路由協(xié)議、基于查詢的路由協(xié)議和基于地理位置路由協(xié)議。內(nèi)容提要5.1概述5.2能量感知路由協(xié)議5.3平面路由協(xié)議5.4層次路由協(xié)議5.5基于查詢的路由協(xié)議5.6基于地理位置路由5.7本章小結(jié)思考題5.1概述5.1.1WSN路由協(xié)議的特點(diǎn)5.1.2路由協(xié)議的分類5.1.1WSN路由協(xié)議的特點(diǎn)無線傳感網(wǎng)路由協(xié)議負(fù)責(zé)將分組從源節(jié)點(diǎn)通過網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，它主要包括兩個方面的功能：①尋找源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的優(yōu)化路徑；②將數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)。傳統(tǒng)無線網(wǎng)絡(luò)的目標(biāo)：提供高服務(wù)質(zhì)量和公平高效地利用網(wǎng)絡(luò)帶寬.因此這些網(wǎng)絡(luò)路由協(xié)議的主要任務(wù)是尋找源節(jié)點(diǎn)到目的節(jié)點(diǎn)間通信延遲小的路徑，同時提高整個網(wǎng)絡(luò)的利用率，避免產(chǎn)生通信擁塞并均衡網(wǎng)絡(luò)流量等，而能量消耗問題不是這類網(wǎng)絡(luò)考慮的重點(diǎn)。無線傳感網(wǎng)節(jié)點(diǎn)能量有限（一般由電池供電），并且由于網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目往往過大，節(jié)點(diǎn)只能獲取局部拓?fù)浣Y(jié)構(gòu)信息，因此要求路由協(xié)議不僅要高效的利用能量，還要在此基礎(chǔ)上能夠在只獲取局部網(wǎng)絡(luò)信息的情況下選擇合適的路徑。5.1.1WSN路由協(xié)議的特點(diǎn)與傳統(tǒng)網(wǎng)絡(luò)的路由協(xié)議相比，無線傳感網(wǎng)路由協(xié)議具有以下的特點(diǎn)：（1）能量優(yōu)先。傳統(tǒng)路由協(xié)議在選擇最優(yōu)路徑時，很少考慮節(jié)點(diǎn)的能量消耗問題。而無線傳感網(wǎng)中節(jié)點(diǎn)的能量有限，延長整個網(wǎng)絡(luò)的生存期成為傳感網(wǎng)路由協(xié)議設(shè)計的重要目標(biāo)，因此需要考慮節(jié)點(diǎn)的能量消耗以及網(wǎng)絡(luò)能量均衡使用的問題。（2）基于局部拓?fù)湫畔ⅰo線傳感網(wǎng)為了節(jié)省通信能量，通常采用多跳的通信模式，而節(jié)點(diǎn)有限的存儲資源和計算資源，使得節(jié)點(diǎn)不能存儲大量的路由信息，不進(jìn)行太復(fù)雜的路由計算。在節(jié)點(diǎn)只能獲取局部拓?fù)湫畔⒑唾Y源有限的情況下，如何實(shí)現(xiàn)簡單高效的路由機(jī)制是無線傳感網(wǎng)的一個基本問題。（3）以數(shù)據(jù)為中心。傳統(tǒng)的路由協(xié)議通常以地址作為節(jié)點(diǎn)的標(biāo)識和路由的依據(jù)，而無線傳感器網(wǎng)絡(luò)中大量節(jié)點(diǎn)隨機(jī)部署，所關(guān)注的是監(jiān)測區(qū)域的感知數(shù)據(jù)，而不是具體哪個節(jié)點(diǎn)獲取的信息。用戶使用傳感網(wǎng)查詢事件時，直接將所關(guān)心的事件通告給網(wǎng)絡(luò)，而不是通告給某個確定編號的節(jié)點(diǎn)。網(wǎng)絡(luò)在獲得指定事件的信息后匯報給用戶。這種以數(shù)據(jù)本身作為查詢或傳輸線索的思想更接近于自然語言交流的習(xí)慣。所以通常又說傳感網(wǎng)是一個以數(shù)據(jù)為中心的網(wǎng)絡(luò)。（4）應(yīng)用相關(guān)。傳感網(wǎng)的應(yīng)用環(huán)境千差萬別，數(shù)據(jù)通信模式不同，沒有一個路由機(jī)制適合所有的應(yīng)用，這是傳感網(wǎng)應(yīng)用相關(guān)性的一個體現(xiàn)。5.1.2路由協(xié)議的分類1．按源節(jié)點(diǎn)獲取路徑策略劃分（1）主動路由協(xié)議。也叫表驅(qū)動(TableDriven)路由協(xié)議，主動路由的路由發(fā)現(xiàn)策略與傳統(tǒng)路由協(xié)議類似，節(jié)點(diǎn)通過周期性地廣播路由信息分組，交換路由信息，主動發(fā)現(xiàn)路由。節(jié)點(diǎn)必須維護(hù)去往全網(wǎng)所有節(jié)點(diǎn)的路由，并且每一個節(jié)點(diǎn)都要保存一個或更多的路由表來存儲路由信息。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時，節(jié)點(diǎn)就在全網(wǎng)內(nèi)廣播路由更新信息，這樣每一個節(jié)點(diǎn)就能連續(xù)不斷地獲得網(wǎng)絡(luò)拓?fù)湫畔?。?yōu)點(diǎn)是只要目的節(jié)點(diǎn)路由存在，所需的延時就會很小。缺點(diǎn)是需要花費(fèi)較大開銷，盡可能使得路由更新能夠緊隨當(dāng)前拓?fù)浣Y(jié)構(gòu)的變化，浪費(fèi)了一些資源來建立和重建那些根本沒有被使用的路由。（2）按需路由協(xié)議。也稱被動路由協(xié)議，只有在源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)到目的節(jié)點(diǎn)時，源節(jié)點(diǎn)才發(fā)起創(chuàng)建路由的過程。路由表的內(nèi)容是按需建立的，它可能僅僅是整個拓?fù)浣Y(jié)構(gòu)信息的一部分，在通信過程中維護(hù)路由，通信完畢后便不再對其進(jìn)行維護(hù)。按需路由的優(yōu)點(diǎn)是不需要周期性的路由信息廣播，路由表僅僅是局部路由，因而節(jié)省了一定的網(wǎng)絡(luò)資源。缺點(diǎn)是發(fā)送數(shù)據(jù)分組時，如果沒有去往目的節(jié)點(diǎn)的路由，需要計算路由，因此時延較大。（3）混合路由協(xié)議：混合路由則綜合利用了主動和按需路由兩種方式。一般來說，對于經(jīng)常被使用并且拓?fù)渥兓淮蟮木W(wǎng)絡(luò)部分，可以采用主動路由的方式建立并維護(hù)相應(yīng)的路由信息，而對于傳輸數(shù)據(jù)較少或拓?fù)渥兓^快的網(wǎng)絡(luò)部分，則采用按需路由的方式建立路由，以取得效用和時延的折中。5.1.2路由協(xié)議的分類2．按通信的邏輯結(jié)構(gòu)劃分（1）平面路由協(xié)議：網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的地位都是平等的，實(shí)現(xiàn)的路由功能也大致相同。當(dāng)一個節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)的時候，可能以其他節(jié)點(diǎn)為中繼節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，最后到達(dá)目的節(jié)點(diǎn)。通常來說，在目的節(jié)點(diǎn)附近的節(jié)點(diǎn)參與數(shù)據(jù)中繼的概率要比遠(yuǎn)離目的節(jié)點(diǎn)的節(jié)點(diǎn)參與數(shù)據(jù)中繼的概率高。因此，目的節(jié)點(diǎn)附近的節(jié)點(diǎn)由于過于頻繁地參與數(shù)據(jù)中繼，會較快地耗盡能量。所以，平面路由協(xié)議的優(yōu)點(diǎn)是網(wǎng)絡(luò)中沒有特殊節(jié)點(diǎn)，網(wǎng)絡(luò)流量均勻地分散在網(wǎng)絡(luò)中，路由算法易于實(shí)現(xiàn)。缺點(diǎn)是可擴(kuò)展性小，在一定程度上限制了網(wǎng)絡(luò)的規(guī)模。（2）層次路由協(xié)議：將若干個相鄰節(jié)點(diǎn)構(gòu)成一個簇，每一個簇有一個簇首。簇與簇之間可以通過網(wǎng)關(guān)通信。網(wǎng)關(guān)可以是簇首也可以是其它簇成員。網(wǎng)關(guān)之間的連接構(gòu)成上層骨干網(wǎng)，所有簇間通信都通過骨干網(wǎng)轉(zhuǎn)發(fā)。每個簇群內(nèi)收集到的監(jiān)控信息都交給簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)完成數(shù)據(jù)聚集和融合過程減少傳播的信息量。相比于其他路由協(xié)議，層次型路由協(xié)議能滿足傳感網(wǎng)的可擴(kuò)展性需求，能有效地減少傳輸節(jié)點(diǎn)的能量消耗，從而延長網(wǎng)絡(luò)生命周期。但是，在此類協(xié)議中，簇首節(jié)點(diǎn)的能量消耗遠(yuǎn)大于其他節(jié)點(diǎn)，因此其網(wǎng)絡(luò)協(xié)議需要采取選擇滿足條件的節(jié)點(diǎn)輪流擔(dān)當(dāng)簇首節(jié)點(diǎn)的方法來均衡能耗。5.1.2路由協(xié)議的分類3．按路由的發(fā)現(xiàn)過程劃分（1）以位置信息為中心的路由協(xié)議：它利用節(jié)點(diǎn)的位置信息，把查詢或者數(shù)據(jù)轉(zhuǎn)發(fā)給需要的地域，從而縮小了數(shù)據(jù)的傳送范圍。許多傳感網(wǎng)的路由協(xié)議都假設(shè)節(jié)點(diǎn)的位置信息是已知的，所以可以方便地利用節(jié)點(diǎn)的位置信息將節(jié)點(diǎn)分為不同的域，并基于域進(jìn)行數(shù)據(jù)傳送，能縮小傳送范圍，減少中間節(jié)點(diǎn)的能耗，從而延長網(wǎng)絡(luò)的生命周期。（2）以數(shù)據(jù)為中心的路由協(xié)議：它提出對傳感網(wǎng)中的數(shù)據(jù)用特定的描述方式命名，數(shù)據(jù)傳送基于數(shù)據(jù)查詢并依賴于數(shù)據(jù)命名，所有的數(shù)據(jù)通信都被限制在局部范圍內(nèi)。這種通信方式不再依賴于特定的節(jié)點(diǎn)，而是依賴于網(wǎng)絡(luò)中的數(shù)據(jù)，從而減少了網(wǎng)絡(luò)中傳送的大量重復(fù)的冗余數(shù)據(jù)，降低了不必要的開銷，從而延長了網(wǎng)絡(luò)生命周期。另外，還可以按路由選擇是否考慮服務(wù)質(zhì)量(QoS)約束來劃分，基于QoS的路由協(xié)議是指在路由建立時，考慮時延、丟包率等QoS參數(shù)，從多條可行的路由中選擇一條最適合QoS應(yīng)用要求的路由?；蛘呤歉鶕?jù)業(yè)務(wù)類型，選擇能保證滿足不同業(yè)務(wù)需求的QoS路由協(xié)議。由于無線傳感網(wǎng)路由協(xié)議種類繁多，其分類方法也多種多樣，除了上述介紹的分類方法之外還有根據(jù)路徑數(shù)量、應(yīng)用場合、數(shù)據(jù)傳輸方式等方法的劃分。5.2能量感知路由協(xié)議高效利用網(wǎng)絡(luò)能量是傳感網(wǎng)路由協(xié)議的一個重要特征。早期提出的傳感網(wǎng)路由協(xié)議，為了強(qiáng)調(diào)能量效率的重要性，往往僅僅考慮了能量因素，可以將它們劃分為能量感知路由協(xié)議，該協(xié)議從數(shù)據(jù)傳輸中的能量消耗出發(fā)，討論最優(yōu)的能量消耗傳輸路經(jīng)。5.2能量感知路由協(xié)議5.2.1能量路由5.2.2能量多路徑路由高效利用網(wǎng)絡(luò)能量是傳感網(wǎng)路由協(xié)議的一個重要特征。早期提出的傳感網(wǎng)路由協(xié)議，為了強(qiáng)調(diào)能量效率的重要性，往往僅僅考慮了能量因素，可以將它們劃分為能量感知路由協(xié)議，該協(xié)議從數(shù)據(jù)傳輸中的能量消耗出發(fā)，討論最優(yōu)的能量消耗傳輸路經(jīng)。5.2.1能量路由能量路由是最早提出的傳感網(wǎng)路由協(xié)議之一，它根據(jù)節(jié)點(diǎn)的可用能量（poweravailable，PA）或傳輸路徑上的能量需求，選擇數(shù)據(jù)的轉(zhuǎn)發(fā)路徑。節(jié)點(diǎn)可用能量就是節(jié)點(diǎn)當(dāng)前的剩余能量。如圖5-1所示，網(wǎng)絡(luò)中的大寫字母表示節(jié)點(diǎn)符號，如節(jié)點(diǎn)A，節(jié)點(diǎn)右側(cè)括號內(nèi)的數(shù)字表示節(jié)點(diǎn)的可用能量，如PA=2，表示節(jié)點(diǎn)A的能量為2，圖中的雙向線表示節(jié)點(diǎn)之間的通信鏈路，鏈路上的數(shù)字表示在該鏈路上發(fā)送數(shù)據(jù)消耗的能量。源節(jié)點(diǎn)是一般功能的傳感器節(jié)點(diǎn)，完成數(shù)據(jù)采集工作，匯聚節(jié)點(diǎn)是數(shù)據(jù)發(fā)送的目標(biāo)節(jié)點(diǎn)。5.2.1能量路由從源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的可能路徑有：(1)路徑1：源節(jié)點(diǎn)—B—A—匯聚節(jié)點(diǎn)，所有節(jié)點(diǎn)PA之和為4，發(fā)送分組需要的能量之和為3；(2)路徑2：源節(jié)點(diǎn)—C—B—A—匯聚節(jié)點(diǎn)，所有節(jié)點(diǎn)PA之和為6，發(fā)送分組需要的能量之和為6；(3)路徑3：源節(jié)點(diǎn)—D—匯聚節(jié)點(diǎn)，所有節(jié)點(diǎn)PA之和為3，發(fā)送分組需要的能量之和為4；(4)路徑4：源節(jié)點(diǎn)—F—E—匯聚節(jié)點(diǎn)，所有節(jié)點(diǎn)PA之和為5，發(fā)送分組需要的能量之和為6。圖5-1能量路由算法示意圖5.2.1能量路由_能量路由策略

（1）最大PA路由：從數(shù)據(jù)源到匯聚節(jié)點(diǎn)的所有路徑中選取節(jié)點(diǎn)PA之和最大的路徑。在圖5-1中路徑2的PA之和最大，但路徑2包含了路徑1，因此不是高效的，從而被排除，選擇路徑4。（2）最小能量消耗路由：從數(shù)據(jù)源到匯聚節(jié)點(diǎn)的所有路徑中選取節(jié)點(diǎn)耗能之和最少的路徑。在圖5-1中選擇路徑1。（3）最少跳數(shù)路由：選取從數(shù)據(jù)源到匯聚節(jié)點(diǎn)跳數(shù)最少的路徑。在圖5-1中選擇路徑3。（4）最大最小PA節(jié)點(diǎn)路由：每條路徑上有多個節(jié)點(diǎn)，且節(jié)點(diǎn)的可用能量不同，從中選取每條路徑中可用能量最小的節(jié)點(diǎn)來表示這條路徑的可用能量。如路徑4中節(jié)點(diǎn)E的可用能量最小為1，所以該路徑的可用能量是1。最大最小PA節(jié)點(diǎn)路由策略就是選擇路徑可用能量最大的路徑。在圖5-1中選擇路徑3。5.2.2能量多路徑路由傳統(tǒng)網(wǎng)絡(luò)的路由機(jī)制往往選擇源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間跳數(shù)最小的路徑傳輸數(shù)據(jù)，但在無線傳感網(wǎng)中，如果頻繁使用同一條路徑傳輸數(shù)據(jù)，就會造成該路徑上的節(jié)點(diǎn)因能量消耗過快而過早失效，從而使整個網(wǎng)絡(luò)分割成互不相連的孤立部分，減少了整個網(wǎng)絡(luò)的生存期。為了避免這種情況的出現(xiàn)。要盡可能地保證每個節(jié)點(diǎn)都有較為公平的機(jī)會成為路徑上的一環(huán)，各個節(jié)點(diǎn)在相對較長的時間內(nèi)，能量消耗的比例一致。能量多路徑路由機(jī)制：就是在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立多條路徑，根據(jù)路徑上節(jié)點(diǎn)的通信能量消耗以及節(jié)點(diǎn)的剩余能量情況，給每條路徑賦予一定的選擇概率，使得數(shù)據(jù)傳輸均衡消耗整個網(wǎng)絡(luò)的能量，延長整個網(wǎng)絡(luò)的生存期。能量多路徑路由協(xié)議：包括路徑建立、數(shù)據(jù)傳播和路由維護(hù)三個過程。路徑建立過程是該協(xié)議的重點(diǎn)內(nèi)容。每個節(jié)點(diǎn)需要知道到達(dá)目的節(jié)點(diǎn)的所有下一跳節(jié)點(diǎn)，并計算選擇每個下一跳節(jié)點(diǎn)傳輸數(shù)據(jù)的概率。概率的選擇是根據(jù)節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信代價來計算的。因為每個節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的路徑很多，所以這個代價值是各個路徑的加權(quán)平均值。5.2.2能量多路徑路由（1）發(fā)起路徑建立過程目的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播路徑建立消息，啟動路徑建立過程。路徑建立消息中包含一個代價域，表示發(fā)出該消息的節(jié)點(diǎn)到目的節(jié)點(diǎn)路徑上的能量信息，初始值設(shè)置為0。（2）判斷是否轉(zhuǎn)發(fā)路徑建立消息當(dāng)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)送的路徑建立消息時，相對發(fā)送該消息的鄰居節(jié)點(diǎn)，只有當(dāng)自己距源節(jié)點(diǎn)更近，而且距目的節(jié)點(diǎn)更遠(yuǎn)的情況下，才需要轉(zhuǎn)發(fā)該消息，否則將丟棄該消息。（3）計算能量代價如果節(jié)點(diǎn)決定轉(zhuǎn)發(fā)路徑建立消息，需要計算新的代價值來替換原來的代價值。當(dāng)路徑建立消息從節(jié)點(diǎn)Ni發(fā)送到節(jié)點(diǎn)Nj時，該路徑的通信代價值為節(jié)點(diǎn)的代價值加上兩個節(jié)點(diǎn)間的通信能量消耗，即：節(jié)點(diǎn)Nj到節(jié)點(diǎn)Ni的通信能量消耗（4）節(jié)點(diǎn)加入路徑條件節(jié)點(diǎn)要放棄代價太大的路徑，節(jié)點(diǎn)j將節(jié)點(diǎn)i加入本地路由表中的條件是：其中α為大于1的系統(tǒng)參數(shù)。（5）節(jié)點(diǎn)選擇概率計算節(jié)點(diǎn)為路由表中每個下一跳節(jié)點(diǎn)計算選擇概率，節(jié)點(diǎn)選擇概率與能量消耗成反比。節(jié)點(diǎn)使用如下公式計算選擇節(jié)點(diǎn)的概率：

（6）代價平均值計算節(jié)點(diǎn)根據(jù)路由表中每項的能量代價和下一跳節(jié)點(diǎn)選擇概率計算本身到目的節(jié)點(diǎn)的代價。其定義為經(jīng)由路由表中節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)代價的平均值，即：

節(jié)點(diǎn)Nj將用cos（Nj）值替換消息中原有的代價值，然后向鄰居節(jié)點(diǎn)廣播該路由建立消息。在數(shù)據(jù)傳播階段，對于接收的每個數(shù)據(jù)分組，節(jié)點(diǎn)根據(jù)概率從多個下一跳節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)，并將數(shù)據(jù)分組轉(zhuǎn)發(fā)給該節(jié)點(diǎn)。路由的維護(hù)是通過周期性地從目的節(jié)點(diǎn)到源節(jié)點(diǎn)實(shí)施洪泛查詢來維持所有路徑的活動性。能量多路徑路由綜合考慮了通信路徑上的消耗能量和剩余能量，節(jié)點(diǎn)根據(jù)概率在路由表中選擇一個節(jié)點(diǎn)作為路由的下一跳節(jié)點(diǎn)。由于這個概率是與能量相關(guān)的，可以將通信能耗分散到多條路徑上，從而可實(shí)現(xiàn)整個網(wǎng)絡(luò)的能量均衡，最大限度地延長網(wǎng)絡(luò)的生存期。5.3平面路由協(xié)議5.3.1Flooding和Gosipping協(xié)議5.3.2SPIN協(xié)議5.3平面路由協(xié)議基于平面結(jié)構(gòu)的路由協(xié)議是最簡單的路由形式，其中每一個點(diǎn)都具有對等的功能。其優(yōu)點(diǎn)是不存在特殊節(jié)點(diǎn)，路由協(xié)議的魯棒性較好，通信流量被平均地分散在網(wǎng)絡(luò)中，而其缺點(diǎn)是缺乏可擴(kuò)展性，限制了網(wǎng)絡(luò)規(guī)模。最有代表性的算法是泛洪Flooding算法、Gosipping以及SPIN算法。5.3.1Flooding和Gosipping協(xié)議1．洪泛路由協(xié)議洪泛路由協(xié)議（FloodingProtocol）是一種最早的路由協(xié)議，接收到消息的節(jié)點(diǎn)以廣播的形式轉(zhuǎn)發(fā)報文給所有的鄰居節(jié)點(diǎn)。如圖5-2所示，源節(jié)點(diǎn)S希望發(fā)送數(shù)據(jù)給目的節(jié)點(diǎn)D，首先要通過網(wǎng)絡(luò)將數(shù)據(jù)分組傳送給它的每一個鄰居節(jié)點(diǎn)，各個鄰居節(jié)點(diǎn)又將其傳播給各自的鄰居節(jié)點(diǎn)，直到數(shù)據(jù)遍歷全網(wǎng)或者達(dá)到規(guī)定的最大跳數(shù)。洪泛法的優(yōu)點(diǎn)和缺點(diǎn)都十分突出。優(yōu)點(diǎn)：是不用維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由計算，實(shí)現(xiàn)簡單，適用于健壯性要求高的場合，缺點(diǎn)：是存在信息內(nèi)爆、重疊以及資源盲點(diǎn)等問題，如圖5-2所示。1．洪泛路由協(xié)議——內(nèi)爆圖5-2Flooding的“內(nèi)暴”現(xiàn)象內(nèi)爆現(xiàn)象：如圖5-2所示，節(jié)點(diǎn)S通過廣播將數(shù)據(jù)發(fā)送給自己的鄰居節(jié)點(diǎn)A、B和C，A、B和C又將同樣的數(shù)據(jù)包轉(zhuǎn)發(fā)給D，這種將同一個數(shù)據(jù)包多次轉(zhuǎn)發(fā)給同一個節(jié)點(diǎn)的現(xiàn)象就是內(nèi)爆，這極大浪費(fèi)節(jié)點(diǎn)能量。1．洪泛路由協(xié)議——重疊重疊現(xiàn)象：是無線傳感器網(wǎng)絡(luò)特有的，如圖5-3所示，節(jié)點(diǎn)A和B感知范圍發(fā)生了重疊，重疊區(qū)域的事件被相鄰的兩個節(jié)點(diǎn)探測到，那么同一事件被傳給它們共同的鄰居節(jié)點(diǎn)C多次，這也浪費(fèi)能量。重疊現(xiàn)象是一個很復(fù)雜的問題，比內(nèi)爆問題更難解決。圖5-3Flooding的“重疊”現(xiàn)象2.Gosipping協(xié)議--閑聊法閑聊法（Gossiping）是洪泛法的改進(jìn)版本。為了減少資源的無謂消耗，閑聊法引入了隨機(jī)發(fā)送數(shù)據(jù)的方法。某一個節(jié)點(diǎn)發(fā)送數(shù)據(jù)時，不再像洪泛法那樣給它的每個鄰后節(jié)點(diǎn)都發(fā)送數(shù)據(jù)副本，而是隨機(jī)選擇某個鄰居節(jié)點(diǎn)，向它發(fā)送一份數(shù)據(jù)副本。接收到數(shù)據(jù)的節(jié)點(diǎn)采用相同的方法，隨機(jī)選擇下一個接收節(jié)點(diǎn)發(fā)送數(shù)據(jù)，如圖5-4所示。需要注意的是，如果一個節(jié)點(diǎn)已收到了它的鄰居節(jié)點(diǎn)B的數(shù)據(jù)副本，若再次收到，那么它會將此數(shù)據(jù)發(fā)回它的鄰居節(jié)點(diǎn)B。由于一般無線傳感網(wǎng)的鏈路冗余度較大，適當(dāng)選擇轉(zhuǎn)發(fā)的鄰居數(shù)量，可以保證幾乎所有節(jié)點(diǎn)都可以接收到數(shù)據(jù)包。5.3.2SPIN協(xié)議基于信息協(xié)商機(jī)制的傳感網(wǎng)協(xié)議（SensorProtocolforInformationViaNegotiation,SPIN）是最早的—類無線傳感器路由協(xié)議的代表，它主要是對洪泛路由協(xié)議的改進(jìn)。SPIN協(xié)議是一種以數(shù)據(jù)為中心的自適應(yīng)路由協(xié)議。該協(xié)議考慮到了WSN中的數(shù)據(jù)冗余問題。臨近的節(jié)點(diǎn)所感知的數(shù)據(jù)具有相似性，通過節(jié)點(diǎn)間協(xié)商（Nagotiation）的方式減少網(wǎng)絡(luò)中數(shù)據(jù)的傳輸數(shù)據(jù)量。節(jié)點(diǎn)只廣播其他節(jié)點(diǎn)所沒有的數(shù)據(jù)以減少冗余數(shù)據(jù)，從而有效減少能量消耗。1．SPIN協(xié)議工作原理先介紹SPIN協(xié)議中的基本概念。①元數(shù)據(jù)（metedata）。元數(shù)據(jù)是原始感知數(shù)據(jù)的一個映射，用來描述原始感知數(shù)據(jù)。元數(shù)據(jù)所需的數(shù)據(jù)位比原始感知數(shù)據(jù)要小，采用這種變相的數(shù)據(jù)壓縮策略可以進(jìn)一步減少通信過程中的能量消耗。②SPIN協(xié)議采用三次握手協(xié)議來實(shí)現(xiàn)數(shù)據(jù)的交互，協(xié)議運(yùn)行過程中使用三種報文數(shù)據(jù)，分別為ADV、REQ和DATA。ADV:用于數(shù)據(jù)的廣播，當(dāng)某一個節(jié)點(diǎn)有數(shù)據(jù)可以共享時，用ADV數(shù)據(jù)包通知其鄰居節(jié)點(diǎn)；REQ:用于請求發(fā)送數(shù)據(jù)，當(dāng)某一個收到ADV的節(jié)點(diǎn)希望接收DATA數(shù)據(jù)包時，發(fā)送REQ數(shù)據(jù)包；DATA:為原始感知數(shù)據(jù)包，里面裝載了原始感知數(shù)據(jù)。③SPIN協(xié)議有兩種工作模式：SPIN1和SPIN2，SPIN2在SPIN1的基礎(chǔ)上作了一些能量上的考慮，本質(zhì)上還是一樣的。SPIN1協(xié)議的工作過程(1)當(dāng)節(jié)點(diǎn)A感知到新事件后，主動給其鄰居節(jié)點(diǎn)廣播描述該事件的元數(shù)據(jù)ADV報文.(2)節(jié)點(diǎn)B收到A的報文,檢查自己是否擁有ADV報文中所描述的數(shù)據(jù)，如果沒有的話，節(jié)點(diǎn)B就向A發(fā)送REQ報文，在REQ報文列出需要A節(jié)點(diǎn)給出的數(shù)據(jù)列表，如圖(b)。(3)當(dāng)節(jié)點(diǎn)A收到了REQ請求報文，它就將相關(guān)的數(shù)據(jù)發(fā)送給節(jié)點(diǎn)B，如圖(c)。(4)節(jié)點(diǎn)B發(fā)送ADV報文通知其鄰居節(jié)點(diǎn)自已有新的消息，如圖(d).由于A節(jié)點(diǎn)中保存有ADV的內(nèi)容，A節(jié)點(diǎn)不會響應(yīng)B節(jié)點(diǎn)的ADV消息。(5)如果收到ADV報文的節(jié)點(diǎn)發(fā)現(xiàn)自己已經(jīng)擁有了ADV報文中描述的數(shù)據(jù)，那么它不發(fā)送REQ報文，圖(e)中有一個節(jié)點(diǎn)沒有發(fā)送RCQ報文。SPIN協(xié)議特點(diǎn)SPIN協(xié)議下，節(jié)點(diǎn)不需要維護(hù)鄰居節(jié)點(diǎn)的信息，一定程度上能適應(yīng)節(jié)點(diǎn)移動的情況。在能耗方面，比傳統(tǒng)模式減少一半以上。不過，該算法不能確保數(shù)據(jù)一定能到達(dá)目標(biāo)節(jié)點(diǎn)，尤其是不適用于高密度節(jié)點(diǎn)分布的情況。由于SPIN協(xié)議通過節(jié)點(diǎn)之間的協(xié)商，解決了flooding協(xié)議的內(nèi)爆和重疊現(xiàn)象。SPIN協(xié)議是一種不需要了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的路由協(xié)議，由于它幾乎不需要了解“一跳”范圍內(nèi)的節(jié)點(diǎn)狀態(tài)，網(wǎng)絡(luò)的拓?fù)涓淖儗λ挠绊懹邢?，因此該協(xié)議也適合在節(jié)點(diǎn)可以移動的WSN中使用。SPIN協(xié)議通過使用協(xié)商機(jī)制和能量自適應(yīng)機(jī)制，節(jié)省了能量，解決了內(nèi)爆的問題。SPIN協(xié)議引入了元數(shù)據(jù)的概念，通過這種數(shù)據(jù)壓縮方法來減少數(shù)據(jù)的傳輸量，是一種值得借鑒的方法。在SPIN協(xié)議中出現(xiàn)了多個節(jié)點(diǎn)向同一個節(jié)點(diǎn)同時發(fā)送請求的情況，有關(guān)的退避機(jī)制需要考慮。5.4層次路由協(xié)議5.4.1LEACH協(xié)議5.4.2PEGASIS協(xié)議5.4.3TEEN協(xié)議5.4層次路由協(xié)議在基于層次的路由協(xié)議中，網(wǎng)絡(luò)被劃分為大小不等的簇（CIuster）。簇.就是具有某種關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點(diǎn)集合。每個簇由一個簇頭（Clusterhead）和多個簇內(nèi)成員（Clustermember）組成。在分層的簇結(jié)構(gòu)網(wǎng)絡(luò)中，低一級網(wǎng)絡(luò)的簇頭是高一級網(wǎng)絡(luò)中的簇內(nèi)成員，由最高層的簇頭與匯聚節(jié)點(diǎn)（Sinknode）通信。這類算法將整個網(wǎng)絡(luò)劃分為相連的區(qū)域。在分簇的拓?fù)涔芾頇C(jī)制下，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以劃分為簇頭節(jié)點(diǎn)和簇內(nèi)成員節(jié)點(diǎn)兩大類。在每個簇內(nèi)，根據(jù)一定的算法選取某個節(jié)點(diǎn)作為簇頭，用于管理或控制整個簇內(nèi)成員節(jié)點(diǎn)，協(xié)調(diào)成員節(jié)點(diǎn)之間的工作，負(fù)責(zé)簇內(nèi)信息的收集和數(shù)據(jù)的融合處理以及簇間轉(zhuǎn)發(fā)。層次路由的優(yōu)點(diǎn)：是適合大規(guī)模的傳感器網(wǎng)絡(luò)環(huán)境，可擴(kuò)展性較好，而其缺點(diǎn)是簇頭節(jié)點(diǎn)的可靠性和穩(wěn)定性對全網(wǎng)性能的影響較大，信息的采集和處理也會消耗簇頭節(jié)點(diǎn)的大量能量。典型的層次路由協(xié)議，LEACH協(xié)議、PEGASIS協(xié)議以及TEEN協(xié)議。5.4.1LEACH協(xié)議低功耗自適應(yīng)聚類分級（LowEnergyAdaptiveClusteringHierarchy，LEACH）協(xié)議采用層次路由算法。定義出了輪的概念，每一輪有初始狀態(tài)和穩(wěn)定運(yùn)行狀態(tài)兩種模式。初始狀態(tài)是用來根據(jù)算法隨機(jī)選擇簇頭節(jié)點(diǎn)，同時廣播自己成為簇頭節(jié)點(diǎn)的事實(shí)，其它節(jié)點(diǎn)收到廣播信號后通過判斷信號的強(qiáng)弱來決定加入哪個簇，并告知簇頭節(jié)點(diǎn)。穩(wěn)定工作時候，節(jié)點(diǎn)將信息傳遞給簇頭節(jié)點(diǎn)，然后簇頭節(jié)點(diǎn)將信息傳遞給匯集節(jié)點(diǎn)。當(dāng)一輪完成后重新選舉簇頭。該算法通過輪流擔(dān)任簇頭的方式來均等消耗能量，達(dá)到延長網(wǎng)絡(luò)生存周期的目的。但是因為每一個節(jié)點(diǎn)都可以成為簇頭，也即都可以將數(shù)據(jù)直接傳給匯集節(jié)點(diǎn)，該算法只是適用于單跳的小型網(wǎng)絡(luò)。LEACH節(jié)約能量的主要原因：就是它運(yùn)用了數(shù)據(jù)壓縮技術(shù)和分簇動態(tài)路由技術(shù)，通過本地的聯(lián)合工作來提高網(wǎng)絡(luò)的可擴(kuò)展性和魯棒性，通過數(shù)據(jù)融合來減少發(fā)送的數(shù)據(jù)量，通過把節(jié)點(diǎn)隨機(jī)的設(shè)置成“簇頭節(jié)點(diǎn)”來達(dá)到在網(wǎng)絡(luò)內(nèi)部負(fù)載均衡的目的，防止簇頭節(jié)點(diǎn)的過快死亡。1．分簇式路由協(xié)議的工作原理通過等概率地隨機(jī)循環(huán)選擇簇頭，將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個傳感器節(jié)點(diǎn)，從而達(dá)到降低網(wǎng)絡(luò)能量耗費(fèi)、延長網(wǎng)絡(luò)生命周期的目的。分簇式路由協(xié)議的執(zhí)行過程是以輪(round)為單位的，每輪循環(huán)的基本過程是：（1）簇的建立階段。每個節(jié)點(diǎn)選取一個介于0和1之間的隨機(jī)數(shù)，如果這個數(shù)小于某個閾值，該節(jié)點(diǎn)成為簇頭。然后，簇頭向所有節(jié)點(diǎn)廣播自己成為簇頭的消息。每個節(jié)點(diǎn)根據(jù)接收到廣播信號的強(qiáng)弱來決定加入哪個簇，并回復(fù)該簇簇頭。（2）數(shù)據(jù)傳輸階段。簇內(nèi)的所有節(jié)點(diǎn)按照TDMA（時分復(fù)用）時隙向簇頭發(fā)送數(shù)據(jù)。簇頭將數(shù)據(jù)融合之后把結(jié)果發(fā)給匯聚節(jié)點(diǎn)。（3）重新成簇。在持續(xù)工作一段時間之后，網(wǎng)絡(luò)重新進(jìn)入啟動階段，進(jìn)行下一輪的簇頭選取并重新建立簇。2.LEACH協(xié)議工作原理LEACH協(xié)議的工作分為兩個階段：（1）簇的建立階段：負(fù)責(zé)簇的形成和簇頭的選舉。在LEACH協(xié)議中，節(jié)點(diǎn)決定自己是否成為簇頭的算法如下：每個傳感器節(jié)點(diǎn)產(chǎn)生一個0~1之間的隨機(jī)數(shù)，如果這個數(shù)小于概率值T(n)，則發(fā)布自己是簇頭的公告消息。在每輪循環(huán)中，如果節(jié)點(diǎn)己經(jīng)當(dāng)選過簇頭，則設(shè)T(n)=0，這樣該節(jié)點(diǎn)不會再次當(dāng)選為簇頭。對于未當(dāng)選過簇頭的節(jié)點(diǎn)，則將以T(n)的概率當(dāng)選；隨著當(dāng)選過簇頭的節(jié)點(diǎn)數(shù)目增加，剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)隨之增大，節(jié)點(diǎn)產(chǎn)生小于T(n)的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選簇頭的概率增大。當(dāng)只剩下一個節(jié)點(diǎn)未當(dāng)選時，T(n)=1，表示這個節(jié)點(diǎn)一定當(dāng)選。2.LEACH協(xié)議工作原理(2)概率表達(dá)式為：其中：p是簇頭占所有節(jié)點(diǎn)的百分比，即節(jié)點(diǎn)當(dāng)選簇頭的概率；r是目前循環(huán)進(jìn)行的輪數(shù)；G是最近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合。所有被推選出的簇頭都向網(wǎng)絡(luò)中的其它節(jié)點(diǎn)廣播一個通告來宣布自己的簇頭角色。而所有其它節(jié)點(diǎn)在收到這些通告之后，會根據(jù)通告的強(qiáng)度來決定自己到底加入哪個簇。簇頭節(jié)點(diǎn)在收到愿意加入簇的節(jié)點(diǎn)的回應(yīng)信息后，就會根據(jù)簇內(nèi)節(jié)點(diǎn)的數(shù)目創(chuàng)建一個TDMA表為每個簇內(nèi)節(jié)點(diǎn)分配一個傳輸時隙。最后簇頭節(jié)點(diǎn)將這張表的信息以廣播的方式告知簇內(nèi)的成員。同時不同的簇用不同的TDMA通信方式，這樣就減少了不同簇的節(jié)點(diǎn)之間的干擾。2.LEACH協(xié)議工作原理(3)（2）穩(wěn)定階段：負(fù)責(zé)收集數(shù)據(jù)和給簇頭傳輸數(shù)據(jù)。簇頭節(jié)點(diǎn)在收到簇內(nèi)成員的數(shù)據(jù)之后會對這些數(shù)據(jù)進(jìn)行聚合后傳送給匯集結(jié)點(diǎn)。經(jīng)過一段時間之后，網(wǎng)絡(luò)就會再一次回到協(xié)議的建立階段，開始新一輪的工作。3.LEACH協(xié)議的特點(diǎn)優(yōu)點(diǎn)：①將區(qū)域劃分成簇、簇內(nèi)本地化協(xié)調(diào)和控制的形式有效的進(jìn)行了數(shù)據(jù)收集。大多數(shù)的節(jié)點(diǎn)只需要短距離的數(shù)據(jù)傳輸?shù)酱仡^節(jié)點(diǎn)，僅有小部分的節(jié)點(diǎn)（簇頭節(jié)點(diǎn)）負(fù)責(zé)遠(yuǎn)距離的數(shù)據(jù)傳送到匯集節(jié)點(diǎn)，從而節(jié)省更多節(jié)點(diǎn)的能量。②獨(dú)特的選簇算法保證簇頭位置的隨機(jī)輪換，節(jié)點(diǎn)是否決定要成為簇頭要看其是否在輪中當(dāng)選過簇頭。同時所做決定是獨(dú)立于其它節(jié)點(diǎn)不需要協(xié)商的。這種機(jī)制保證了能量消耗平均分布于全網(wǎng)。③運(yùn)用了數(shù)據(jù)融合技術(shù)本地數(shù)據(jù)融合大大減少了簇頭節(jié)點(diǎn)傳送到匯集節(jié)點(diǎn)的數(shù)據(jù)量，進(jìn)一步減少了能量消耗提高了網(wǎng)絡(luò)壽命。3.LEACH協(xié)議的特點(diǎn)（2）缺點(diǎn)：①簇頭能量消耗比較大：由于簇頭節(jié)點(diǎn)負(fù)責(zé)接收簇內(nèi)成員節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，進(jìn)行數(shù)據(jù)融合，然后將數(shù)據(jù)傳送到基站，簇頭消耗能量比較大，是網(wǎng)絡(luò)中的瓶頸。②LEACH協(xié)議中簇頭選舉是隨機(jī)循環(huán)選舉，有可能簇頭位于網(wǎng)絡(luò)的邊緣或者幾個簇頭相鄰較近，某些節(jié)點(diǎn)不得不傳輸較遠(yuǎn)的距離來與簇頭通信，這就導(dǎo)致消耗的能耗大大增加。③簇頭選舉沒有根據(jù)節(jié)點(diǎn)的剩余能量以及位置等因素，會導(dǎo)致有的簇過早死亡，簇與簇之間節(jié)點(diǎn)的能量消耗不均衡。④LEACH協(xié)議要求節(jié)點(diǎn)之間以及節(jié)點(diǎn)與匯集節(jié)點(diǎn)之間均可以直接通信，網(wǎng)絡(luò)的擴(kuò)展性不強(qiáng)，不適用于大型網(wǎng)絡(luò)。對于大型網(wǎng)絡(luò)而言，對離簇頭較遠(yuǎn)的簇內(nèi)節(jié)點(diǎn)和離匯聚節(jié)點(diǎn)較遠(yuǎn)的簇頭而言，傳輸所消耗的能量大大增加。這樣簇頭節(jié)點(diǎn)能耗分布不均勻，導(dǎo)致某些節(jié)點(diǎn)快速死亡，從而降低了網(wǎng)絡(luò)的性能。5.4.2PEGASIS協(xié)議高能效采集傳感器信息系統(tǒng)（Power-EfficientGatheringinSensorInformationSystems，PEGASIS）并不是嚴(yán)格意義上的分簇路由協(xié)議，它只是借鑒了LEACH中分簇算法的思想。PEGASIS中的簇是一條基于地理位置的鏈。其成簇的基本思想是，假設(shè)所有節(jié)點(diǎn)都是靜止的，根據(jù)節(jié)點(diǎn)的地理位置形成一條相鄰節(jié)點(diǎn)之間距離最短的鏈。這類似于旅行商問題，是一個經(jīng)典的NP問題。其算法是假設(shè)節(jié)點(diǎn)通過定位裝置或者通過發(fā)送能量遞減的測試信號來發(fā)現(xiàn)距自己最近的鄰居節(jié)點(diǎn)，然后從距匯集節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)開始，采用貪婪算法來構(gòu)造整條鏈。與LEACH算法相比，PEGASIS中通信只限于相鄰節(jié)點(diǎn)之間。這樣，每個節(jié)點(diǎn)都以最小功率發(fā)送數(shù)據(jù)，并且每輪只隨機(jī)選擇一個簇頭與匯集節(jié)點(diǎn)通信，減少了數(shù)據(jù)通信量。PEGASIS支持的傳感網(wǎng)的生命周期是LEACH的近兩倍。5.4.2PEGASIS協(xié)議（2）PEGASIS的模型假設(shè)如下。（1）節(jié)點(diǎn)都知道其他節(jié)點(diǎn)的位置信息，每個節(jié)點(diǎn)都具有直接和匯集節(jié)點(diǎn)（基站）通信的能力。（2）傳感器節(jié)點(diǎn)不具有移動性。（3）其他的模型假設(shè)和LEACH中的相同。該路由協(xié)議使用貪婪算法（GreedyAlgorithm）來形成鏈，如圖5-6所示。在每一輪通信之前才形成鏈。為確保每個節(jié)點(diǎn)都有其相鄰節(jié)點(diǎn)，鏈從離基站最遠(yuǎn)的節(jié)點(diǎn)開始構(gòu)建，鏈中鄰居節(jié)點(diǎn)的距離會逐漸增大，因為已經(jīng)在鏈中的節(jié)點(diǎn)不能再次被訪問。當(dāng)其中一個節(jié)點(diǎn)失效時，鏈必須重構(gòu)。5.4.2PEGASIS協(xié)議（3）PEGASIS協(xié)議中數(shù)據(jù)的傳輸使用Token令牌機(jī)制，Token很小，故耗能較少。在一輪中，簇頭用Token控制數(shù)據(jù)從鏈尾開始傳輸。網(wǎng)絡(luò)中某些節(jié)點(diǎn)可能因與鄰居節(jié)點(diǎn)距離較遠(yuǎn)而消耗能量較大。可以通過設(shè)置一個門限值限定此節(jié)點(diǎn)作為接頭。當(dāng)該鏈重構(gòu)時，此門限值可被改變以重新決定哪些節(jié)點(diǎn)可做簇頭，從而增強(qiáng)網(wǎng)絡(luò)的健壯性。圖中，c2為簇頭，將token沿著鏈傳輸給c0，c0傳送數(shù)據(jù)給c1，c1將c0數(shù)據(jù)與自身數(shù)據(jù)進(jìn)行融合形成一個相同長度的數(shù)據(jù)包，再傳給c2。此后，c2將token傳給c3，并以同樣的方式收集c3和c4的數(shù)據(jù)。這些數(shù)據(jù)在c2處進(jìn)行融合后，被發(fā)送給基站5.4.3TEEN協(xié)議閾值敏感的高效傳感器網(wǎng)絡(luò)協(xié)議（ThresholdSensitiveEnergyeEfficientSensorNetworkProtocol，TEEN）采用類似LEACH的分簇算法，只是在數(shù)據(jù)傳送階段使用不同的策略。根據(jù)數(shù)據(jù)傳輸模式的不同，通常可以簡單地把傳感器網(wǎng)絡(luò)分為主動型（proactive）和響應(yīng)型（reactive）兩種類型。主動型網(wǎng)絡(luò)不斷采集被監(jiān)測對象的相關(guān)信息，并以特定時間間隔向匯集節(jié)點(diǎn)發(fā)送這些信息；響應(yīng)型網(wǎng)絡(luò)主要用來監(jiān)測某個特定事件的發(fā)生，傳感器節(jié)點(diǎn)只有在節(jié)點(diǎn)檢測到相關(guān)事件時才會向匯集節(jié)點(diǎn)發(fā)送信息，如對災(zāi)害的監(jiān)測、暖通空調(diào)設(shè)備的防凍監(jiān)測等。對于監(jiān)測特定的事件，適于使用響應(yīng)型無線傳感器網(wǎng)絡(luò)。TEEN協(xié)議是專門為響應(yīng)型應(yīng)用環(huán)境下的網(wǎng)絡(luò)路由協(xié)議，利用過濾方式來減少數(shù)據(jù)傳輸量。TEEN和LEACH的實(shí)現(xiàn)機(jī)制是相似的，只是LEACH適用于主動型網(wǎng)絡(luò)。與LEACH一樣，TEEN也采用分簇結(jié)構(gòu)和近于相同的運(yùn)行方式，具體做法是在協(xié)議中設(shè)置了硬、軟兩個閾值，以減少發(fā)送數(shù)據(jù)的次數(shù)。5.4.3TEEN協(xié)議(2)TEEN協(xié)議實(shí)現(xiàn)簇的建立過程中，隨著簇頭節(jié)點(diǎn)的選定，簇頭除了通過TDMA方式調(diào)度數(shù)據(jù)外，同時向簇內(nèi)成員廣播發(fā)送有關(guān)數(shù)據(jù)的硬閾值和軟閾值參數(shù)，兩個參數(shù)用來決定是否發(fā)送監(jiān)測數(shù)據(jù)。硬閾值用于監(jiān)視被監(jiān)測值的絕對大小，軟閾值用于監(jiān)視被監(jiān)測值的變化幅度。在傳感器節(jié)點(diǎn)簇進(jìn)入穩(wěn)定工作階段后，傳感器節(jié)點(diǎn)不斷感知及監(jiān)測周圍環(huán)境中的被監(jiān)測參量。當(dāng)首次監(jiān)測到數(shù)據(jù)超過硬閾值時，便向簇頭傳送數(shù)據(jù)，同時將該監(jiān)測數(shù)據(jù)保存為監(jiān)測值(sensorvalue)。此后，只有在監(jiān)測到的數(shù)據(jù)值比硬閾值大，并且與保存的監(jiān)測值SV之差的絕對值不小于軟閾值時，節(jié)點(diǎn)才向簇頭上傳數(shù)據(jù)，同時將當(dāng)前監(jiān)測數(shù)據(jù)保存為SV。TEEN通過調(diào)節(jié)兩個閾值的大小，可以在精度要求和系統(tǒng)能耗之間取得合理的平衡。采用這樣的方法，可以監(jiān)視一些突發(fā)事件和熱點(diǎn)地區(qū)，減少網(wǎng)絡(luò)通信量。5.4.3TEEN協(xié)議(3)如果一輪的運(yùn)行已經(jīng)結(jié)束，開始了又一個新的輪，并且在初始化階段中，簇頭已經(jīng)確定，則該簇頭將重新設(shè)定和發(fā)布硬閾值和軟閾值參數(shù)。這一過程如圖5-7所示。5.4.3TEEN協(xié)議(3)TEEN路由協(xié)議適用于對一些事件的實(shí)時感知偵測，并利用軟閾值、硬閾值設(shè)置來較大幅度地減小數(shù)據(jù)傳輸量。在輪的更替中，隨著簇頭的變化，用戶可以根據(jù)需要重新設(shè)定軟、硬閾值參數(shù)值，來控制數(shù)據(jù)傳輸?shù)拇螖?shù)。TEEN路由協(xié)議同LEACH協(xié)議類似，協(xié)議實(shí)現(xiàn)的一個前提就是網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都能夠與網(wǎng)關(guān)節(jié)點(diǎn)直接建立通信，這就限制了該協(xié)議僅適合于小規(guī)模的無線傳感網(wǎng)。5.5基于查詢的路由協(xié)議5.5.1定向擴(kuò)散路由5.5.2謠傳路由5.5基于查詢的路由協(xié)議在需要不斷查詢傳感器節(jié)點(diǎn)采集的數(shù)據(jù)的應(yīng)用中，通信流量主要產(chǎn)生于查詢節(jié)點(diǎn)和傳感器節(jié)點(diǎn)之間的命令和數(shù)據(jù)傳輸。同時傳感器節(jié)點(diǎn)的采樣信息通常要在傳輸路徑上進(jìn)行數(shù)據(jù)融合，并通過減少通信流量來節(jié)省能量。5.5.1定向擴(kuò)散路由定向擴(kuò)散（Directedfusion，DD)路由協(xié)議是一種基于查詢的路由方法，這和傳統(tǒng)路由算法的概念不同。DD算法是一種基于數(shù)據(jù)相關(guān)的路由算法，匯集節(jié)點(diǎn)周期地通過洪泛的方式廣播一種稱為“興趣”的數(shù)據(jù)包，告訴網(wǎng)絡(luò)中的節(jié)點(diǎn)它需要收集什么樣的信息?！芭d趣”在網(wǎng)絡(luò)中擴(kuò)散的時候同時也建立了路由路徑，采集到和“興趣”相關(guān)的數(shù)據(jù)的節(jié)點(diǎn)通過“興趣”擴(kuò)散階段建立的路徑將采集到的“興趣”數(shù)據(jù)傳送到匯集節(jié)點(diǎn)。在興趣消息的傳播過程中，協(xié)議逐跳地在各個傳感器節(jié)點(diǎn)上建立反向的從數(shù)據(jù)源到匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸梯度(Gradient)，傳感器節(jié)點(diǎn)將采集到的數(shù)據(jù)沿著梯度方向傳送到匯聚節(jié)點(diǎn)。定向擴(kuò)散路由機(jī)制包括周期性的興趣擴(kuò)散、梯度建立、數(shù)據(jù)傳播與路徑加強(qiáng)等階段。在梯度建立后或者路徑加強(qiáng)后都不可避免地要進(jìn)行數(shù)據(jù)傳輸，這也是路由協(xié)議的最終目的。廣義來說，數(shù)據(jù)傳輸也算是該路由機(jī)制中的一個階段。5.5.1定向擴(kuò)散路由如圖5-8所示為DD協(xié)議的幾個階段的數(shù)據(jù)傳播路徑和方向。1．興趣擴(kuò)散階段

在定向擴(kuò)散協(xié)議中，首先描述需要感知的任務(wù)，并選擇一個簡單的屬性組命名機(jī)制來描述興趣消息和分組數(shù)據(jù)。在興趣擴(kuò)散階段，匯聚節(jié)點(diǎn)周期性地向鄰居節(jié)點(diǎn)廣播興趣消息。興趣消息中包括任務(wù)類型、事件區(qū)域、數(shù)據(jù)發(fā)送速率、時間戳等參數(shù)。每個節(jié)點(diǎn)都在本地保存一個興趣列表，對于每一個興趣，列表中都有一個表項來記錄該消息的鄰居節(jié)點(diǎn)、數(shù)據(jù)發(fā)送速率和時間戳等任務(wù)相關(guān)的信息，以建立該節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳遞數(shù)據(jù)的梯度關(guān)系?！獋€興趣可能對應(yīng)多個鄰居節(jié)點(diǎn)，一個鄰居節(jié)點(diǎn)對應(yīng)一個梯度信息。通過定義不同的梯度相關(guān)參數(shù)，可以滿足不同的應(yīng)用需求。每個表項中還有一個字段用來表示該表項的有效時間值。超過這個時間后，節(jié)點(diǎn)將刪除這個表項。節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)的興趣消息時，首先檢查興趣列表中是否存有參數(shù)類型與收到興趣相同的表項，而且其對應(yīng)的發(fā)送節(jié)點(diǎn)也是該鄰居節(jié)點(diǎn)。如果有對應(yīng)的表項，就更新該項的有效時間值。如果只是參數(shù)類型相同，但不包含發(fā)送該興趣消息的鄰居節(jié)點(diǎn)，就在相應(yīng)表項中添加這個鄰居節(jié)點(diǎn)。對于任何其他的情況，都需要建立一個新表項來記錄這個新的興趣。如果收到的興趣消息和節(jié)點(diǎn)剛剛轉(zhuǎn)發(fā)的興趣消息是一樣的，為避免消息循環(huán)，則丟棄該信息。否則。轉(zhuǎn)發(fā)收到的興趣消息。2．梯度建立階段DD協(xié)議需要在傳感器節(jié)點(diǎn)和匯集節(jié)點(diǎn)之間建立梯度，以保證可靠的數(shù)據(jù)傳輸。網(wǎng)絡(luò)中的節(jié)點(diǎn)從鄰居節(jié)點(diǎn)接收到一個興趣消息時，無法判斷此消息是否是已處理過的，或者是否和另一個方向的鄰居節(jié)點(diǎn)發(fā)來的興趣消息相同，所以當(dāng)興趣消息在整個網(wǎng)絡(luò)擴(kuò)散的時候，相鄰的節(jié)點(diǎn)彼此都建立一個梯度。這樣的優(yōu)點(diǎn)是加快了無效路徑的修復(fù)，有利于路徑的加強(qiáng)，從而不會產(chǎn)生持久的環(huán)路，但同時也會導(dǎo)致一個節(jié)點(diǎn)可能接收到多個相同的興趣消息，造成消息在網(wǎng)絡(luò)中的泛濫。3．?dāng)?shù)據(jù)傳播階段當(dāng)傳感器節(jié)點(diǎn)采集到與興趣匹配的數(shù)據(jù)時，就把數(shù)據(jù)發(fā)送到梯度上的鄰居節(jié)點(diǎn)，并按照梯度上的數(shù)據(jù)傳輸速率設(shè)定傳感器模塊采集數(shù)據(jù)的速率。由于可能會從多個鄰居節(jié)點(diǎn)收到興趣消息，而且節(jié)點(diǎn)會向多個鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)，匯聚節(jié)點(diǎn)可能會接收到經(jīng)過多個不同路徑的相同數(shù)據(jù)，中間節(jié)點(diǎn)收到其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)后，首先查詢興趣列表的表項。如果沒有匹配的興趣表項就丟棄數(shù)據(jù)，如果存在相應(yīng)的興趣表項，則檢查與這個興趣對應(yīng)的數(shù)據(jù)緩沖區(qū)，其中數(shù)據(jù)緩沖區(qū)保存了最近轉(zhuǎn)發(fā)的數(shù)據(jù)。如果在數(shù)據(jù)緩沖區(qū)中有與接收到的數(shù)據(jù)匹配的副本，則說明巳經(jīng)轉(zhuǎn)發(fā)過這個數(shù)據(jù)了，為避免出現(xiàn)傳輸環(huán)路，將丟棄這個數(shù)據(jù)。否則，檢查該興趣表頂中的鄰居節(jié)點(diǎn)信息。如果設(shè)置的鄰居節(jié)點(diǎn)的數(shù)據(jù)發(fā)送速率大于等于接收的數(shù)據(jù)速率，則全部轉(zhuǎn)發(fā)接收的數(shù)據(jù)。如果記錄的鄰居節(jié)點(diǎn)的數(shù)據(jù)發(fā)送速率小于接收的數(shù)據(jù)速率，則按照比例轉(zhuǎn)發(fā)。對于轉(zhuǎn)發(fā)的數(shù)據(jù)，數(shù)據(jù)緩沖區(qū)將保留一個副本，并記錄轉(zhuǎn)發(fā)時間。4．路徑加強(qiáng)階段定向擴(kuò)散路由機(jī)制通過正向加強(qiáng)機(jī)制來建立優(yōu)化路徑，并根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓薷臄?shù)據(jù)轉(zhuǎn)發(fā)的梯度關(guān)系。興趣擴(kuò)散階段要建立源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑，數(shù)據(jù)源節(jié)點(diǎn)將以較低的速率采集和發(fā)送數(shù)據(jù)，稱這個階段建立的梯度為探測梯度（ProbeGradient）。匯聚節(jié)點(diǎn)在收到從源節(jié)點(diǎn)發(fā)來的數(shù)據(jù)后，啟動建立匯聚節(jié)點(diǎn)到源節(jié)點(diǎn)的加強(qiáng)路徑的過程，后續(xù)數(shù)據(jù)將沿著加強(qiáng)路徑以較高的數(shù)據(jù)速率進(jìn)行傳輸，加強(qiáng)后的梯度被稱為數(shù)據(jù)梯度（DataGradient）。DD路由特點(diǎn)定向擴(kuò)散路由是一種以數(shù)據(jù)為中心的經(jīng)典的路由機(jī)制。為了動態(tài)適應(yīng)節(jié)點(diǎn)失效、拓?fù)渥兓惹闆r。定向擴(kuò)散路由周期性地進(jìn)行興趣擴(kuò)散、梯度建立、數(shù)據(jù)傳播與路徑加強(qiáng)4個階段的操作。定向擴(kuò)散路由在路由建立時需要有一個擴(kuò)散的洪泛傳播，其能量和時間開銷都比較大，尤其是當(dāng)?shù)讓覯AC協(xié)議采用了休眠機(jī)制時，可能會造成興趣建立的不一致。DD路由協(xié)議中，為了對失效路徑進(jìn)行修復(fù)和重建，規(guī)定已經(jīng)加強(qiáng)過的路徑上的節(jié)點(diǎn)都可以觸發(fā)和啟動路徑的加強(qiáng)過程。DD算法中采用了數(shù)據(jù)融合的方法，數(shù)據(jù)融合包括梯度建立階段興趣消息的融合和數(shù)據(jù)發(fā)送階段的數(shù)據(jù)融合，這兩種融合方法都需要緩存數(shù)據(jù)。DD中數(shù)據(jù)融合采用的是抑制副本的方法，即記錄轉(zhuǎn)發(fā)過的數(shù)據(jù)，收到重復(fù)的數(shù)據(jù)不予轉(zhuǎn)發(fā)。其中采用的這些數(shù)據(jù)融合方法、實(shí)現(xiàn)起來簡單，與路由技術(shù)結(jié)合能夠有效地減少網(wǎng)絡(luò)中的數(shù)據(jù)量，節(jié)省節(jié)點(diǎn)能量、提高帶寬利用率。5.5.2謠傳路由在有些傳感器網(wǎng)絡(luò)的應(yīng)用中，數(shù)據(jù)傳輸量較少或者已知事件區(qū)域，如果采用定向擴(kuò)散路由，需要經(jīng)過查詢消息的洪泛傳播和路徑加強(qiáng)機(jī)制才能確定一條優(yōu)化的數(shù)據(jù)傳輸路徑。因此，在這類應(yīng)用中，定向擴(kuò)散路由并不是高效的路由機(jī)制。謠傳路由（rumorrouting）適用于數(shù)據(jù)傳輸量較小的無線傳感網(wǎng)。謠傳路由機(jī)制引入了查詢消息的單播隨機(jī)轉(zhuǎn)發(fā)，克服了使用洪泛方式建立轉(zhuǎn)發(fā)路徑帶來的開銷過大問題。謠傳路由的基本思想是：事件區(qū)域中的傳感器節(jié)點(diǎn)產(chǎn)生代理（agent）消息，代理消息沿隨機(jī)路徑向外擴(kuò)散傳播，同時匯聚節(jié)點(diǎn)發(fā)送的查詢消息也沿隨機(jī)路徑在網(wǎng)絡(luò)中傳播。當(dāng)代理消息和查詢消息的傳輸路徑交叉在一起時，就會形成一條匯聚節(jié)點(diǎn)到事件區(qū)域的完整路徑。謠傳路由的原理如圖所示，灰色區(qū)域表示發(fā)生事件的區(qū)域，圓點(diǎn)表示傳感器節(jié)點(diǎn)，黑色圓點(diǎn)表示代理消息經(jīng)過的傳感器節(jié)點(diǎn)，灰色節(jié)點(diǎn)表示查詢消息經(jīng)過的傳感器節(jié)點(diǎn)，連接灰色節(jié)點(diǎn)和部分黑色節(jié)點(diǎn)的路徑表示事件區(qū)域到匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑。謠傳路由的工作過程（1）（1）每個傳感器節(jié)點(diǎn)維護(hù)一個鄰居列表和一個事件列表。事件列表的每個表項都記錄事件相關(guān)的信息，包括事件名稱、到事件區(qū)域的跳數(shù)和到事件區(qū)域的下一跳鄰居等信息。當(dāng)傳感器節(jié)點(diǎn)在本地監(jiān)測到一個事件發(fā)生時，在事件列表中增加一個表項，設(shè)置事件名稱、跳數(shù)（為零）等，同時根據(jù)一定的概率產(chǎn)生一個代理消息。（2）代理消息是一個包含生命期等事件相關(guān)信息的分組，用來將攜帶的事件信息通告給它傳輸經(jīng)過的每一個傳感器節(jié)點(diǎn)。對于收到代理消息的節(jié)點(diǎn)，首先檢查事件列表中是否有該事件相關(guān)的表項，列表中存在相關(guān)表項就比較代理消息和表項中的跳數(shù)值，如果代理中的跳數(shù)小，就更新表項中的跳數(shù)值，否則更新代理消息中的跳數(shù)值。如果事件列表中沒有該事件相關(guān)的表項，就增加一個表項來記錄代理消息攜帶的事件信息。然后，節(jié)點(diǎn)將代理消息中的生存值減1，在網(wǎng)絡(luò)中隨機(jī)選擇鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)代理消息，直到其生存值減少為零。通過代理消息在其有限生存期的傳輸過程，形成一段到達(dá)事件區(qū)域的路徑。謠傳路由的工作過程（2）（3）網(wǎng)絡(luò)中的任何節(jié)點(diǎn)都可能生成一個對特定事件的查詢消息。如果節(jié)點(diǎn)的事件列表中保存有該事件的相關(guān)表項，說明該節(jié)點(diǎn)在到達(dá)事件區(qū)域的路徑上，它沿著這條路徑轉(zhuǎn)發(fā)查詢消息。否則，節(jié)點(diǎn)隨機(jī)選擇鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢消息。查詢消息經(jīng)過的節(jié)點(diǎn)按照同樣方式轉(zhuǎn)發(fā)，并記錄查詢消息中的相關(guān)信息，形成查詢消息的路徑。查詢消息也具有一定的生存期，以解決環(huán)路問題。（4）如果查詢消息和代理消息的路徑交叉，交叉節(jié)點(diǎn)會沿查詢消息的反向路徑將事件信息傳送到查詢節(jié)點(diǎn)。如果查詢節(jié)點(diǎn)在一段時間沒有收到事件消息，就認(rèn)為查詢消息沒有到達(dá)事件區(qū)域，可以選擇重傳、放棄或者洪泛查詢消息的方法。由于洪泛查詢機(jī)制的代價過高，一般作為最后的選擇。與定向擴(kuò)散路由相比，謠傳路由可以有效地減少路由建立的開銷。但是，由于謠傳路由使用隨機(jī)方式生成路徑，所以數(shù)據(jù)傳輸路徑不是最優(yōu)路徑，并且可能存在路由環(huán)路問題。5.6基于地理位置路由5.6.1GEAR路由5.6.2GAF路由5.6.3GPSR路由在無線傳感網(wǎng)中，節(jié)點(diǎn)通常需要獲取它的位置信息，這樣它采集的數(shù)據(jù)才有意義。如在森林防火的應(yīng)用中，消防人員不僅要知道森林中發(fā)生火災(zāi)事件，而且還要知道火災(zāi)的具體位置。地理位置路由假設(shè)節(jié)點(diǎn)知道自己的地理位置信息，以及目的節(jié)點(diǎn)或者目的區(qū)域的地理位置，利用這些地理位置信息作為路由選擇的依據(jù)，節(jié)點(diǎn)按照一定策略轉(zhuǎn)發(fā)數(shù)據(jù)到目的節(jié)點(diǎn)。地理位置的精確度和代價相關(guān)，在不同的應(yīng)用中會選擇不同精確度的位置信息來實(shí)現(xiàn)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。5.6.1GEAR路由GEAR（geographicalandenergyawarerouting）路由機(jī)制根據(jù)事件區(qū)域的地理位置信息，建立匯聚節(jié)點(diǎn)到事件區(qū)域的優(yōu)化路徑，避免了洪泛傳播方式，從而減少了路由建立的開銷。GEAR路由假設(shè)已知事件區(qū)域的位置信息，每個節(jié)點(diǎn)知道自己的位置信息和剩余能量信息，并通過一個簡單的Hello消息交換機(jī)制知道所有鄰居節(jié)點(diǎn)的位置信息和剩余能量信息。在GEAR路由中，節(jié)點(diǎn)間的無線鏈路是對稱的。GEAR路由中查詢消息傳播包括兩個階段。首先匯聚節(jié)點(diǎn)發(fā)出查詢命令，并根據(jù)事件區(qū)域的地理位置將查詢命令傳送到區(qū)域內(nèi)距匯聚節(jié)點(diǎn)最近的節(jié)點(diǎn)，然后從該節(jié)點(diǎn)將查詢命令傳播到區(qū)域內(nèi)的其他所有節(jié)點(diǎn)。監(jiān)測數(shù)據(jù)沿查詢消息的反向路徑向匯聚節(jié)點(diǎn)傳送。（1）查詢消息傳送到事件區(qū)域GEAR路由用實(shí)際代價（learnedcost）和估計代價（estimatecost）兩種代價值表示路徑代價。當(dāng)沒有建立從匯聚節(jié)點(diǎn)到事件區(qū)域的路徑時，中間節(jié)點(diǎn)使用估計代價來決定下一跳節(jié)點(diǎn)。估計代價定義為歸一化的節(jié)點(diǎn)到事件區(qū)域的距離以及節(jié)點(diǎn)的剩余能量兩部分，節(jié)點(diǎn)到事件區(qū)域的距離用節(jié)點(diǎn)到事件區(qū)域幾何中心的距離來表示。由于所有節(jié)點(diǎn)都知道自己的位置和事件區(qū)域的位置，因而所有節(jié)點(diǎn)都能夠計算出自己到事件區(qū)域幾何中心的距離。節(jié)點(diǎn)計算自己到事件區(qū)域估計代價的公式如下：（5.7）式中，C(N,R)為節(jié)點(diǎn)N到事件區(qū)域R的估計代價，d(N,R)為節(jié)點(diǎn)N到事件區(qū)域R的距離，e(N)為節(jié)點(diǎn)的剩余能量，α為比例參數(shù)。式中的d()和e()都是歸一化后的參數(shù)值。查詢信息到達(dá)事件區(qū)域后，事件區(qū)域的節(jié)點(diǎn)沿查詢路徑的反方向傳輸監(jiān)測數(shù)據(jù)，數(shù)據(jù)消息中“捎帶”每跳節(jié)點(diǎn)到事件區(qū)域的實(shí)際能量消耗值。對于數(shù)據(jù)傳輸經(jīng)過的每個節(jié)點(diǎn)，首先記錄捎帶信息中的能量代價，然后將消息中的能量代價加上它發(fā)送該消息到下一跳節(jié)點(diǎn)的能量消耗，替代消息中的原有“捎帶”值來轉(zhuǎn)發(fā)數(shù)據(jù)。節(jié)點(diǎn)下一次轉(zhuǎn)發(fā)查詢消息時，用剛才記錄的到事件區(qū)域的實(shí)際能量代價代替式（5.7）中的d(N,R)，計算它到匯聚節(jié)點(diǎn)的實(shí)際代價。節(jié)點(diǎn)用調(diào)整后的實(shí)際代價選擇到事件區(qū)域的優(yōu)化路徑。從匯聚節(jié)點(diǎn)開始的路徑建立過程采用貪婪算法，節(jié)點(diǎn)在鄰居節(jié)點(diǎn)中選擇到事件區(qū)域代價最小的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，并將自己的路由代價設(shè)為該下一跳節(jié)點(diǎn)的路由代價加上到該節(jié)點(diǎn)一跳通信的代價。如果節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)到事件區(qū)域路由代價都比自己的大，則陷入了路由空洞（routingvoid）。路由空洞如圖所示，節(jié)點(diǎn)C是節(jié)點(diǎn)S的鄰居節(jié)點(diǎn)中到目的節(jié)點(diǎn)T代價最小的節(jié)點(diǎn)，但節(jié)點(diǎn)G，H，I為失效節(jié)點(diǎn)，節(jié)點(diǎn)C的所有鄰居節(jié)點(diǎn)到節(jié)點(diǎn)T的代價都比節(jié)點(diǎn)C大?？刹捎萌缦路绞浇鉀Q路由空洞問題：節(jié)點(diǎn)C選取鄰居中代價最小的節(jié)點(diǎn)B作為下一跳節(jié)點(diǎn)，并將自己的代價值設(shè)為B的代價加上節(jié)點(diǎn)C到節(jié)點(diǎn)B一跳通信的代價，同時將這個新代價值通知節(jié)點(diǎn)S。當(dāng)節(jié)點(diǎn)S再轉(zhuǎn)發(fā)查詢命令到節(jié)點(diǎn)T時就會選擇節(jié)點(diǎn)B而不是節(jié)點(diǎn)C作為下一跳節(jié)點(diǎn)。

（2）查詢消息在事件區(qū)域內(nèi)傳播當(dāng)查詢命令傳送到事件區(qū)域后，可以通過洪泛方式傳播到事件區(qū)域內(nèi)的所有節(jié)點(diǎn)。但當(dāng)節(jié)點(diǎn)密度比較大時，洪泛方式開銷比較大，這時可以采用迭代地理轉(zhuǎn)發(fā)策略。如圖5-12所示，事件區(qū)域內(nèi)首先收到查詢命令的節(jié)點(diǎn)將事件區(qū)域分為若干子區(qū)域，并向所有子區(qū)域的中心位置轉(zhuǎn)發(fā)查詢命令。在每個子區(qū)域中，最靠近區(qū)域中心的節(jié)點(diǎn)（如圖5-12中Ni節(jié)點(diǎn)）接收查詢命令，并將自己所在的子區(qū)域再劃分為若干子區(qū)域并向各個子區(qū)域中心轉(zhuǎn)發(fā)查詢命令。該消息傳播過程是一個迭代過程，當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)自己是某個子區(qū)域內(nèi)惟一的節(jié)點(diǎn)，或者某個子區(qū)域沒有節(jié)點(diǎn)存在時，停止向這個子區(qū)域發(fā)送查詢命令。當(dāng)所有子區(qū)域轉(zhuǎn)發(fā)過程全部結(jié)束時，整個迭代過程終止。圖5-12GEAR路由特點(diǎn)洪泛機(jī)制和迭代地理轉(zhuǎn)發(fā)機(jī)制各有利弊。當(dāng)事件區(qū)域內(nèi)節(jié)點(diǎn)較多時，迭代地理轉(zhuǎn)發(fā)的消息轉(zhuǎn)發(fā)次數(shù)少，而節(jié)點(diǎn)較少時使用洪泛策略的路由效率高。GEAR路由可以使用如下方法在兩種機(jī)制中作出選擇：當(dāng)查詢命令到達(dá)區(qū)域內(nèi)的第一個節(jié)點(diǎn)時，如果該節(jié)點(diǎn)的鄰居數(shù)量大于一個預(yù)設(shè)的閾值，則使用迭代地理轉(zhuǎn)發(fā)機(jī)制，否則使用洪泛機(jī)制。GEAR路由通過定義估計路由代價:為節(jié)點(diǎn)到事件區(qū)域的距離和節(jié)點(diǎn)剩余能量，并利用捎帶機(jī)制獲取實(shí)際路由代價，進(jìn)行數(shù)據(jù)傳輸?shù)穆窂絻?yōu)化，從而形成能量高效的數(shù)據(jù)傳輸路徑。GEAR路由采用的貪婪算法是一個局部最優(yōu)的算法，適合無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)只知道局部拓?fù)湫畔⒌那闆r，其缺點(diǎn)是由于缺乏足夠的拓?fù)湫畔?，路由過程中可能遇到路由空洞，反而降低了路由效率。如果節(jié)點(diǎn)擁有相鄰兩跳節(jié)點(diǎn)的地理位置信息，可以大大減少路由空洞的產(chǎn)生概率。GEAR路由中假設(shè)節(jié)點(diǎn)的地理位置固定或變化不頻繁，適用于節(jié)點(diǎn)移動性不強(qiáng)的應(yīng)用環(huán)境。5.6.2GAF路由地域自適應(yīng)保真算法（GeographicAdaptiveFidility，GAF）是基于有限能量和位置信息的路由算法。GAF原本是為移動AdHoc網(wǎng)絡(luò)設(shè)計的，但同樣可以應(yīng)用于傳感器網(wǎng)絡(luò)，因為它的虛擬網(wǎng)格思想為分族機(jī)制提供了新思路，GAF在不影響路由有效性的情況下，通過關(guān)閉一些不需要的節(jié)點(diǎn)來節(jié)省能量，同時還考慮了所有節(jié)點(diǎn)能量消耗的均衡性。在GAF路由協(xié)議中，網(wǎng)絡(luò)被劃分為若干固定區(qū)域，形成了一個虛擬網(wǎng)格。節(jié)點(diǎn)通過GPS定位獲取自己在網(wǎng)格中所處的“位置”，如果兩個節(jié)點(diǎn)處在相同的“位置”，則認(rèn)為它們在路由時是等價的，前提是它們分組轉(zhuǎn)發(fā)能耗水平相等。等價節(jié)點(diǎn)中只需有一個處于工作狀態(tài)，其余節(jié)點(diǎn)可以進(jìn)入睡眠。如圖5-13所示。因此，GAF能夠有效地延長網(wǎng)絡(luò)的生命周期。圖5-13在圖5-14中的節(jié)點(diǎn)2、3、4在同一個柵格B中，因此只需要保留其中一個節(jié)點(diǎn)處于工作狀態(tài)，另外兩個可以處于睡眠狀態(tài)。而這在adHoc網(wǎng)絡(luò)中是絕對不可取的，因為在AdHoc網(wǎng)絡(luò)中，即使是同一個柵格內(nèi)的節(jié)點(diǎn)，也還是代表了不同的移動終端，根本不能相互代替。但在WSN中，這就是一個優(yōu)點(diǎn)，相當(dāng)于用1個節(jié)點(diǎn)代表了3個節(jié)點(diǎn)，類似于層次路由中的簇頭節(jié)點(diǎn)，但這個類似于簇頭的代表節(jié)點(diǎn)卻不進(jìn)行柵格內(nèi)的數(shù)據(jù)融合。節(jié)點(diǎn)間的數(shù)據(jù)通信只能在相鄰柵格間進(jìn)行，即A柵格內(nèi)的節(jié)點(diǎn)1只能與B柵格內(nèi)的2、3、4節(jié)點(diǎn)通信，而不能直接和C柵格內(nèi)的節(jié)點(diǎn)5通信。圖5-14雖然GAF按柵格選擇代表節(jié)點(diǎn)的方法和SOA選擇靜止節(jié)點(diǎn)做轉(zhuǎn)發(fā)點(diǎn)的方法不同，但兩者都是在全部節(jié)點(diǎn)中選擇部分節(jié)點(diǎn)，相當(dāng)于從整個集合中選擇子集，并且都是根據(jù)節(jié)點(diǎn)的當(dāng)前狀態(tài)來決定是否選擇該節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，它們都能有效地延長網(wǎng)絡(luò)的生存時間。GAF算法的執(zhí)行過程包括兩個階段。（1）第一階段是虛擬網(wǎng)格的劃分。根據(jù)節(jié)點(diǎn)的位置信息和通信半徑，將網(wǎng)絡(luò)區(qū)域劃分成若干虛擬網(wǎng)格，保證相鄰單元格中的任意兩個節(jié)點(diǎn)都能夠直接通信。假設(shè)節(jié)點(diǎn)已知整個監(jiān)測區(qū)域的位置信息和本身的位置信息，則可以通過計算得知自己屬于哪個網(wǎng)格。（2）第二階段是虛擬網(wǎng)格中簇頭節(jié)點(diǎn)的選擇。節(jié)點(diǎn)周期性地進(jìn)入睡眠和工作狀態(tài)，從睡眠狀態(tài)喚醒之后與本單元其他節(jié)點(diǎn)交換信息，以確定自已是否需要成為簇頭節(jié)點(diǎn)。每個節(jié)點(diǎn)都處于發(fā)現(xiàn)(Discovery)、活動(Active)以及睡眠(sleeping)3種狀態(tài)，如圖5-15所示。在網(wǎng)絡(luò)初始化時，所有節(jié)點(diǎn)都處于發(fā)現(xiàn)狀態(tài)，每個節(jié)點(diǎn)都通過發(fā)送消息通告自己的位置、ID等信息。經(jīng)過這個階段，節(jié)點(diǎn)能得知同一單元格內(nèi)其他節(jié)點(diǎn)的信息。然后，每個節(jié)點(diǎn)將自身定時器設(shè)置為某個區(qū)間內(nèi)的隨機(jī)值。一旦定時器超時，節(jié)點(diǎn)就發(fā)送消息，聲明它進(jìn)入活動狀態(tài)，并成為簇頭節(jié)點(diǎn)。節(jié)點(diǎn)如果在定時器超時之前收到來自同一單元格內(nèi)其他節(jié)點(diǎn)成為簇頭的聲明，說明它自己這次競爭簇頭失敗，從而轉(zhuǎn)入睡眠狀態(tài)。成為簇頭的節(jié)點(diǎn)設(shè)置定時器，代表它處于活動狀態(tài)的時間。在超時之前，簇頭節(jié)點(diǎn)定期發(fā)送廣播包聲明自己處于活動狀態(tài)，以抑制其他處于發(fā)現(xiàn)狀態(tài)的節(jié)點(diǎn)進(jìn)入活動狀態(tài)。在超時后，簇頭節(jié)點(diǎn)重新回到發(fā)現(xiàn)狀態(tài)。處于睡眠狀態(tài)的節(jié)點(diǎn)設(shè)置定時器為，并在超時后，節(jié)點(diǎn)重新回到發(fā)現(xiàn)狀態(tài)。處于活動狀態(tài)或發(fā)現(xiàn)狀態(tài)的節(jié)點(diǎn)如果發(fā)現(xiàn)本單元格中出現(xiàn)了更適合成為簇頭的節(jié)點(diǎn)時，會自動進(jìn)入睡眠狀態(tài)。由于節(jié)點(diǎn)處于監(jiān)聽狀態(tài)也會消耗很多能量，讓節(jié)點(diǎn)盡量處于睡眠狀態(tài)成為傳感器網(wǎng)絡(luò)拓?fù)渌惴ㄖ薪?jīng)常采用的方法。GAF是較早采用這種方法的算法。由于傳感器節(jié)點(diǎn)自身體積和資源受限，GAF對傳感器節(jié)點(diǎn)提出的要求較高。且GAF算法是基于平面模型的，沒有考慮到實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)之間距離的鄰近并不能代表節(jié)點(diǎn)之間可以直接通信的問題，因此存在一些不足。5.6.3GPSR路由無狀態(tài)的貪婪周邊路由協(xié)議（GreedyPerimeterStatelessRouting，GPSR）是一個典型的基于位置的路由協(xié)議。該協(xié)議，網(wǎng)絡(luò)中的所有傳感器節(jié)點(diǎn)均知道自身的坐標(biāo)位置信息，而且這些坐標(biāo)位置被統(tǒng)一編址，傳感器節(jié)點(diǎn)按照貪婪算法盡量地沿直線將數(shù)據(jù)傳送出去。采集到數(shù)據(jù)的節(jié)點(diǎn)經(jīng)過判別哪個相鄰節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離最近，就將數(shù)據(jù)傳送給該鄰居節(jié)點(diǎn)。數(shù)據(jù)可以使用兩種模式來傳送：貪婪轉(zhuǎn)發(fā)模式和周邊轉(zhuǎn)發(fā)模式。使用貪婪轉(zhuǎn)發(fā)模式時，接收到數(shù)據(jù)的傳感器節(jié)點(diǎn)，查詢它的鄰節(jié)點(diǎn)表，如果某個鄰節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)的距離小于自身節(jié)點(diǎn)到網(wǎng)關(guān)節(jié)點(diǎn)的距離，就保持當(dāng)前的數(shù)據(jù)模式，同時將數(shù)據(jù)轉(zhuǎn)發(fā)給選定的鄰節(jié)點(diǎn)；如果滿足不了上述要求，就改變數(shù)據(jù)模式為周邊轉(zhuǎn)發(fā)模式。GPSR路由工作原理在傳送的數(shù)據(jù)包中包括目標(biāo)節(jié)點(diǎn)的位置信息，中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)利用貪婪轉(zhuǎn)發(fā)模式來確定下一跳的節(jié)點(diǎn)，這個節(jié)點(diǎn)是距離目標(biāo)節(jié)點(diǎn)最近的那個鄰節(jié)點(diǎn)。用這種方式連續(xù)不斷的選擇距目標(biāo)節(jié)點(diǎn)更近的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)中繼轉(zhuǎn)發(fā)，直至將數(shù)據(jù)傳送給目標(biāo)節(jié)點(diǎn)為止。使用貪婪轉(zhuǎn)發(fā)策略選擇下一跳節(jié)點(diǎn)的情況如圖5-16所示。設(shè)定中繼節(jié)點(diǎn)A接收到一個到目標(biāo)節(jié)點(diǎn)D的數(shù)據(jù)包，節(jié)點(diǎn)A的傳輸覆蓋范圍是以A點(diǎn)為圓心的虛線圓區(qū)域，以D點(diǎn)為圓心，線段DB為半徑畫圓，圓弧交節(jié)點(diǎn)B，由于節(jié)點(diǎn)B與目標(biāo)節(jié)點(diǎn)D之間的距離小于A節(jié)點(diǎn)所有的其它鄰節(jié)點(diǎn)，因此就選節(jié)點(diǎn)B做下一跳節(jié)點(diǎn)。按照這種方式繼續(xù)前向轉(zhuǎn)發(fā)傳遞數(shù)據(jù)，直到目標(biāo)節(jié)點(diǎn)D獲得數(shù)據(jù)為止。GPSR路由工作原理GPSR路由工作原理-路由空洞產(chǎn)生空洞的情況如圖5-17所示，給定網(wǎng)絡(luò)特定的拓?fù)浼皞鞲衅鞴?jié)點(diǎn)的位置分布，節(jié)點(diǎn)T到目標(biāo)節(jié)點(diǎn)D的距離要小于相鄰兩個節(jié)點(diǎn)U、V到目標(biāo)節(jié)點(diǎn)D的距離。將數(shù)據(jù)由節(jié)點(diǎn)T轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)D，有兩條路徑：(T-U-W-D)和(T-V-X-D)，但是使用貪婪轉(zhuǎn)發(fā)策略進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時，就不會選擇U或V作為下一跳的節(jié)點(diǎn)，因為節(jié)點(diǎn)T到目標(biāo)節(jié)點(diǎn)D的距離要小于U或V各自到D的距離，這樣就出現(xiàn)了空洞，導(dǎo)致數(shù)據(jù)無法傳輸。要解決空洞現(xiàn)象，可以使用周邊轉(zhuǎn)發(fā)機(jī)制，這里的闡述就從略了。GPSR路由特點(diǎn)使用貪婪轉(zhuǎn)發(fā)策略會出現(xiàn)所謂路由空洞的缺欠。使用該協(xié)議避免了在節(jié)點(diǎn)中建立、維護(hù)和存儲路由表的工作，僅使用直接毗鄰的節(jié)點(diǎn)進(jìn)行路由選擇。另外，路由選擇中是使用接近于最短歐氏距離的路由，數(shù)據(jù)傳輸時延小，實(shí)時性增強(qiáng)。5.6.4GEM路由GEM（graphembedding）路由是—種適用于數(shù)據(jù)中心存儲方式的地理路由?；舅枷胧墙⒁粋€虛擬極坐標(biāo)系統(tǒng)來表示實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，由于匯集節(jié)點(diǎn)將角度范圍分配給每個子節(jié)點(diǎn)，每個子節(jié)點(diǎn)得到的角度范圍正比于以該節(jié)點(diǎn)為根的子樹大小，子節(jié)點(diǎn)按照同樣的方式將自己的角度范圍分配給它的子節(jié)點(diǎn)，這個過程一直持續(xù)進(jìn)行，直到每個子節(jié)點(diǎn)都分配到一個角度范圍。這樣，節(jié)點(diǎn)可以根據(jù)一個統(tǒng)一規(guī)則（如順時針方向）為子節(jié)點(diǎn)設(shè)定角度范圍，使得同一級節(jié)點(diǎn)的角度范圍順序遞增或遞減，于是到匯聚節(jié)點(diǎn)跳數(shù)相同的節(jié)點(diǎn)就形成了一個環(huán)形結(jié)構(gòu)，整個網(wǎng)絡(luò)則形成一個以匯聚節(jié)點(diǎn)為根的帶環(huán)樹。GEM路由工作機(jī)制節(jié)點(diǎn)在發(fā)送消息時，如果目的節(jié)點(diǎn)位置的角度不在自己的角度范圍內(nèi)，就將消息傳送給父節(jié)點(diǎn)。父節(jié)點(diǎn)按照同樣的規(guī)則處理，直到該消息到達(dá)角度范圍包含目的節(jié)點(diǎn)位置的某個節(jié)點(diǎn)，這個節(jié)點(diǎn)是源節(jié)點(diǎn)和目的節(jié)點(diǎn)的共同祖先。消息再從這個節(jié)點(diǎn)向下傳送，直至到達(dá)目的節(jié)點(diǎn)，如圖5-18(a)所示。上述算法需要上層節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，開銷比較大，可作適當(dāng)改進(jìn)。節(jié)點(diǎn)在向上傳送消息之前，首先檢查鄰節(jié)點(diǎn)是否包含目的節(jié)點(diǎn)位置的角度。如果包含，則直接傳送給該鄰節(jié)點(diǎn)而不再向上傳送，如圖5-18(b)所示。更進(jìn)一步的改進(jìn)算法是可利用前面提到的環(huán)形結(jié)構(gòu)，節(jié)點(diǎn)檢查相鄰節(jié)點(diǎn)的角度范圍是否離目的地的位置更近，如果更近就將消息傳送給該鄰節(jié)點(diǎn)，否則才向上層傳送，如圖5-18(c)所示。GEM路由機(jī)制圖5-18GEM路由機(jī)制（a）消息直接向上層傳遞圖5-18（b）檢查鄰居節(jié)點(diǎn)的角度范圍圖5-18（c）利用環(huán)形樹結(jié)構(gòu)5.7基于QoS的路由協(xié)議無線傳感網(wǎng)的某些應(yīng)用對通信質(zhì)量有較高要求，如高可靠性和實(shí)用性等；而由于網(wǎng)絡(luò)鏈路的穩(wěn)定性難以保證，通信信道質(zhì)量比較低，拓?fù)渥兓容^頻繁，要在無線傳感網(wǎng)中實(shí)現(xiàn)一定服務(wù)質(zhì)量的保證，需要設(shè)計基于QoS的路由協(xié)議。5.7.1SPEED5.7.2SAR5.7.3ReInForM5.7.1SPEED

SPEED協(xié)議是一種實(shí)時有效的可靠路由協(xié)議，在一定程度上實(shí)現(xiàn)了端到端的傳輸速率保證、網(wǎng)絡(luò)擁塞控制以及負(fù)載平衡機(jī)制。該協(xié)議首先在相鄰節(jié)點(diǎn)之間交換傳輸延遲，以得到網(wǎng)絡(luò)負(fù)載情況。然后利用局部地理信息和傳輸速率信息選擇下一跳節(jié)點(diǎn)，同時通過鄰居反饋機(jī)制保證網(wǎng)絡(luò)傳輸暢通，并通過反向壓力路由變更機(jī)制避開延遲太大的鏈路和“洞”現(xiàn)象。SPEED協(xié)議主要由四部分組成。1.延遲估計機(jī)制：延遲估計機(jī)制用來得到網(wǎng)絡(luò)的負(fù)載狀況，判斷網(wǎng)絡(luò)是否發(fā)生擁塞。節(jié)點(diǎn)記錄到鄰節(jié)點(diǎn)的通信延遲以表示網(wǎng)絡(luò)的局部通信負(fù)載。具體過程是：發(fā)送節(jié)點(diǎn)給數(shù)據(jù)分組并加上時間戳；接收節(jié)點(diǎn)計算從收到數(shù)據(jù)分組到發(fā)出ACK的時間間隔，并將其作為一個字段加入ACK報文；發(fā)送節(jié)點(diǎn)收到ACK后，從收發(fā)時間差中減去接收節(jié)點(diǎn)的處理時間，得到一跳的通信延遲。

2.SNGF算法：SNGF算法用來選擇滿足傳輸速率要求的下一跳節(jié)點(diǎn)。鄰節(jié)點(diǎn)分為兩類：比自己距離目標(biāo)區(qū)域更近的節(jié)點(diǎn)和比自己距離目標(biāo)區(qū)域更遠(yuǎn)的節(jié)點(diǎn)，前者稱為“候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集合(FCS)”。節(jié)點(diǎn)計算到其FCS集合中的某個節(jié)點(diǎn)的傳輸速率。FCS集合中的節(jié)點(diǎn)又根據(jù)傳輸速率是否滿足預(yù)定的傳輸速率閾值，再分為兩類：大于速率閡值的鄰節(jié)點(diǎn)和小于速率閾值的鄰節(jié)點(diǎn)。若FCS集合中有節(jié)點(diǎn)的傳輸速率大于速率閡值，則在這些節(jié)