第5章路由協(xié)議

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

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

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

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

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

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

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

2.SNGF算法：SNGF算法用來(lái)選擇滿足傳輸速率要求的下一跳節(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)計(jì)算到其FCS集合中的某個(gè)節(jié)點(diǎn)的傳輸速率。FCS集合中的節(jié)點(diǎn)又根據(jù)傳輸速率是否滿足預(yù)定的傳輸速率閾值，再分為兩類：大于速率閡值的鄰節(jié)點(diǎn)和小于速率閾值的鄰節(jié)點(diǎn)。若FCS集合中有節(jié)點(diǎn)的傳輸速率大于速率閡值，則在這些節(jié)