無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展及發(fā)展趨勢(shì)

摘要：描述了無(wú)線傳感器路由協(xié)議所面臨的問(wèn)題與挑戰(zhàn)，分析和比較了典型的平面路由協(xié)議及層次路由協(xié)議。最后總結(jié)了理想路由協(xié)議應(yīng)該具有的特點(diǎn)以及路由協(xié)議未來(lái)的研究策略及發(fā)展趨勢(shì)。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)； 路由協(xié)議； 平面路由； 層次路由； 研究進(jìn)展

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)06－1616－06

隨著無(wú)線通信、電子與傳感技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)（WSN）引起了人們的廣泛關(guān)注[1]。WSNs由具有傳感、數(shù)據(jù)處理和短距離無(wú)線通信等功能的傳感器組成，在軍事國(guó)防、環(huán)境監(jiān)測(cè)、生物醫(yī)療、搶險(xiǎn)救災(zāi)以及商業(yè)應(yīng)用等領(lǐng)域具有廣闊的應(yīng)用前景[1]。

與傳統(tǒng)的無(wú)線自組織(Ad hoc)網(wǎng)絡(luò)不同，WSNs節(jié)點(diǎn)之間沒(méi)有統(tǒng)一的標(biāo)志，節(jié)點(diǎn)之間通過(guò)廣播、多跳通信方式進(jìn)行數(shù)據(jù)交換。另外，網(wǎng)絡(luò)內(nèi)每個(gè)傳感器節(jié)點(diǎn)的電能通常是有限的、不可更換的。節(jié)點(diǎn)的計(jì)算、通信、存儲(chǔ)能力也非常有限[2]。因此，WSNs路由協(xié)議必須以節(jié)約能源為主要目標(biāo)，并采用折中機(jī)制，使用戶可以在延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間、提高網(wǎng)絡(luò)吞吐量、降低通信延遲間進(jìn)行選擇。

1路由協(xié)議面臨的問(wèn)題和挑戰(zhàn)

與傳統(tǒng)Ad hoc網(wǎng)絡(luò)路由協(xié)議相比，WSNs路由協(xié)議有其固有的特點(diǎn)。比如傳感器節(jié)點(diǎn)數(shù)量大，不可能建立全局地址；在多數(shù)應(yīng)用中，除了少數(shù)節(jié)點(diǎn)移動(dòng)外，一般節(jié)點(diǎn)在部署后保持固定；路由協(xié)議與特定的應(yīng)用有關(guān)；節(jié)點(diǎn)間的數(shù)據(jù)冗余度高，路由協(xié)議需要具有良好的數(shù)據(jù)匯聚能力。因此，常規(guī)路由協(xié)議都不適合在WSNs環(huán)境中運(yùn)行，這就為WSNs路由協(xié)議的設(shè)計(jì)提出了新的問(wèn)題和挑戰(zhàn)。具體體現(xiàn)在以下幾點(diǎn)：

a)節(jié)點(diǎn)沒(méi)有統(tǒng)一的標(biāo)志——由于WSNs中節(jié)點(diǎn)數(shù)目巨大，WSNs節(jié)點(diǎn)沒(méi)有統(tǒng)一的標(biāo)志，節(jié)點(diǎn)間采用廣播式的通信方式進(jìn)行數(shù)據(jù)交換。

b)能量受限——WSNs的一個(gè)重要特征就是能量受限。因此，WSNs協(xié)議必須以節(jié)約能源為主要目標(biāo)并盡可能延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間。

c)面向特定應(yīng)用——在WSNs中，傳感器節(jié)點(diǎn)和物理環(huán)境交互密切，WSNs的通信構(gòu)架及其所采用的路由協(xié)議都是針對(duì)每個(gè)特定的應(yīng)用而設(shè)計(jì)的。

d)頻繁變化的拓?fù)浣Y(jié)構(gòu)——在WSNs中，網(wǎng)絡(luò)拓?fù)鋾?huì)因?yàn)楣?jié)點(diǎn)損壞而變化頻繁。路由協(xié)議必須要適應(yīng)WSNs頻繁變化的拓?fù)浣Y(jié)構(gòu)。

e)容錯(cuò)性——傳感器節(jié)點(diǎn)容易失效，因此路由協(xié)議必須具備良好的容錯(cuò)性，以便形成新的鏈路。

f)可擴(kuò)展性——傳感器節(jié)點(diǎn)一般成百上千，路由協(xié)議應(yīng)該具有可擴(kuò)展性來(lái)適應(yīng)相應(yīng)的應(yīng)用環(huán)境。

g)連通性——由于網(wǎng)絡(luò)節(jié)點(diǎn)失效，很難預(yù)測(cè)網(wǎng)絡(luò)拓?fù)浜痛笮〉淖兓酚蓞f(xié)議必須保證節(jié)點(diǎn)的連通性。

h)數(shù)據(jù)融合——傳感器節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)具有較大的冗余度，因此路由協(xié)議必須能進(jìn)行數(shù)據(jù)融合， 以便節(jié)省能量有效和使數(shù)據(jù)傳輸最優(yōu)化。

i)服務(wù)質(zhì)量(QoS)——許多應(yīng)用中如視頻應(yīng)用，需要路由協(xié)議提供滿足要求的服務(wù)質(zhì)量。

j)安全機(jī)制——路由協(xié)議極易受到安全威脅，因此必須考慮安全機(jī)制，尤其在軍事應(yīng)用中。

2WSNs路由協(xié)議分類

由于WSNs與應(yīng)用高度相關(guān)，單一的路由協(xié)議不能滿足所有應(yīng)用需求。因此，研究人員提出了多種路由協(xié)議。為了更好地分析各種協(xié)議的特點(diǎn)，表1運(yùn)用了多種分類方法對(duì)WSNs路由協(xié)議進(jìn)行分類。

本文將按照網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)路由協(xié)議進(jìn)行分類，分別研究平面路由協(xié)議和層次路由協(xié)議中較典型的路由協(xié)議。

3路由協(xié)議分析

3．1平面路由協(xié)議

在平面路由協(xié)議中，所有節(jié)點(diǎn)的地位是平等的，不存在等級(jí)和層次的差異。它們通過(guò)局部操作和信息反饋來(lái)生成路由，原則上不存在瓶頸問(wèn)題。平面路由協(xié)議的優(yōu)點(diǎn)是簡(jiǎn)單、具有較好的健壯性；其缺點(diǎn)是可擴(kuò)展性差。另外，平面路由協(xié)議需要維持路由表，在大規(guī)模網(wǎng)絡(luò)中會(huì)消耗節(jié)點(diǎn)大量的存儲(chǔ)空間，同時(shí)由于發(fā)送信息中包含了路由信息，會(huì)引起網(wǎng)絡(luò)中通信負(fù)擔(dān)的加重。

3．1．1Flooding協(xié)議及Gossiping協(xié)議[3]

這是兩個(gè)最為經(jīng)典和簡(jiǎn)單的傳統(tǒng)網(wǎng)絡(luò)路由協(xié)議。在 Flooding 協(xié)議中，節(jié)點(diǎn)產(chǎn)生或收到數(shù)據(jù)后向所有鄰節(jié)點(diǎn)廣播，直到數(shù)據(jù)包過(guò)期或到達(dá)目的地。該協(xié)議具有嚴(yán)重缺陷：內(nèi)爆（節(jié)點(diǎn)幾乎同時(shí)從鄰節(jié)點(diǎn)收到多份相同數(shù)據(jù)）、交疊（節(jié)點(diǎn)先后收到監(jiān)控同一區(qū)域的多個(gè)節(jié)點(diǎn)發(fā)送的幾乎相同的數(shù)據(jù)）、盲目利用資源（節(jié)點(diǎn)不考慮自身資源限制，在任何情況下都轉(zhuǎn)發(fā)數(shù)據(jù)）。Gossiping 協(xié)議是對(duì) Flooding協(xié)議的改進(jìn)，節(jié)點(diǎn)將產(chǎn)生或收到的數(shù)據(jù)隨機(jī)轉(zhuǎn)發(fā)，避免了內(nèi)爆，但增加了時(shí)延。這兩個(gè)協(xié)議都不需要維護(hù)路由信息，也不需要任何算法，簡(jiǎn)單但擴(kuò)展性很差。

3．1．2DD路由協(xié)議[4]

DD(directed diffusion)協(xié)議是以數(shù)據(jù)為中心的路由算法的一個(gè)重要里程碑。該協(xié)議用屬性/值對(duì)命名數(shù)據(jù)。為建立路由，sink點(diǎn)向網(wǎng)絡(luò)中Flooding包含屬性列表、上報(bào)間隔、持續(xù)時(shí)間、地理區(qū)域等信息的查詢請(qǐng)求Interest(該過(guò)程本質(zhì)上是設(shè)置一個(gè)監(jiān)測(cè)任務(wù))。沿途節(jié)點(diǎn)按需對(duì)各Interest進(jìn)行緩存與合并，并根據(jù)Interest計(jì)算、創(chuàng)建包含數(shù)據(jù)上報(bào)率、下一跳等信息的梯度(gradient)，從而建立多條指向sink點(diǎn)的路徑。Interest中的地理區(qū)域內(nèi)節(jié)點(diǎn)則按要求啟動(dòng)監(jiān)測(cè)任務(wù)，并周期性地上報(bào)數(shù)據(jù)。途中各節(jié)點(diǎn)可對(duì)數(shù)據(jù)進(jìn)行緩存與聚合。Sink 點(diǎn)可在數(shù)據(jù)傳輸過(guò)程中通過(guò)對(duì)某條路徑發(fā)送上報(bào)間隔更小或更大的Interest，以增強(qiáng)或減弱數(shù)據(jù)上報(bào)率。該協(xié)議健壯性好；使用數(shù)據(jù)聚合能減少數(shù)據(jù)通信量；sink點(diǎn)根據(jù)實(shí)際情況采取增強(qiáng)或減弱方式能有效利用能量；使用查詢驅(qū)動(dòng)機(jī)制按需建立路由，避免了保存全網(wǎng)信息，但不適合環(huán)境監(jiān)測(cè)等應(yīng)用。而且gradient的建立開(kāi)銷很大，不適合多sink點(diǎn)網(wǎng)絡(luò)；數(shù)據(jù)聚合過(guò)程采用時(shí)間同步技術(shù)，這其實(shí)在傳感器網(wǎng)絡(luò)中并不容易實(shí)現(xiàn)。

經(jīng)仿真分析，DD路由協(xié)議具有較好的節(jié)能性，適用于在傳感器節(jié)點(diǎn)接收到數(shù)據(jù)請(qǐng)求后，較長(zhǎng)時(shí)間內(nèi)需要連續(xù)向sink節(jié)點(diǎn)傳送數(shù)據(jù)的場(chǎng)合，不適用于收到請(qǐng)求后只發(fā)一次少量數(shù)據(jù)的場(chǎng)合。因?yàn)镈D算法建立梯度需要花費(fèi)較大的代價(jià)。

3．1．3Rumor協(xié)議[5]

如果sink點(diǎn)的一次查詢只需一次上報(bào)，DD協(xié)議開(kāi)銷太大。Rumor協(xié)議正是為解決此問(wèn)題而設(shè)計(jì)的。該協(xié)議借鑒了歐氏平面圖上任意兩條曲線交叉幾率很大的思想。節(jié)點(diǎn)監(jiān)測(cè)到事件后將其保存，并創(chuàng)建稱為agent的生命周期較長(zhǎng)的包括事件和源節(jié)點(diǎn)信息的數(shù)據(jù)包，將其按一條或多條隨機(jī)路徑在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)。收到agent的節(jié)點(diǎn)根據(jù)事件和源節(jié)點(diǎn)信息建立反向路徑，并將agent再次隨機(jī)發(fā)送到相鄰節(jié)點(diǎn)，并可在再次發(fā)送前在agent中增加其已知的事件信息。Sink查詢請(qǐng)求也沿著一條隨機(jī)路徑轉(zhuǎn)發(fā)，當(dāng)兩路徑交叉時(shí)則路由建立；如不交叉，sink可Flooding查詢請(qǐng)求。在多sink點(diǎn)、查詢請(qǐng)求數(shù)目很大、網(wǎng)絡(luò)事件很少的情況下，仿真結(jié)果表明Rumor 協(xié)議能顯著地降低路由開(kāi)銷，節(jié)約能量。但對(duì)于事件數(shù)較多的情況，維護(hù)事件表和處理代理所花費(fèi)的開(kāi)銷會(huì)急劇增長(zhǎng)。同時(shí)，由于路由使用隨機(jī)的方式生成路徑，數(shù)據(jù)傳輸?shù)穆窂讲皇亲顑?yōu)路徑，并且可能存在路由環(huán)路問(wèn)題。

3．1．4SPIN協(xié)議[6]

SPIN（sensor protocol for information via negotiation)路由算法是一種平面式的自適應(yīng)通信路由協(xié)議。其目標(biāo)是通過(guò)使用節(jié)點(diǎn)間的協(xié)商制度和資源自適應(yīng)機(jī)制，解決傳統(tǒng)泛洪法存在的不足之處。在SPIN算法中，假設(shè)所有的傳感器節(jié)點(diǎn)均可能是希望獲得數(shù)據(jù)的sink，每個(gè)傳感器節(jié)點(diǎn)知道自己是否需要數(shù)據(jù)或是否在數(shù)據(jù)源到sink的路徑上。傳感器節(jié)點(diǎn)在發(fā)送數(shù)據(jù)前先進(jìn)行協(xié)商，僅將數(shù)據(jù)發(fā)送到需要的相鄰節(jié)點(diǎn)。這種協(xié)商制度可以確保有效的數(shù)據(jù)傳輸。傳感器節(jié)點(diǎn)間通過(guò)發(fā)送元數(shù)據(jù)（meta－data，即描述傳感器節(jié)點(diǎn)采集的數(shù)據(jù)屬性的數(shù)據(jù)），而非采集到的整個(gè)數(shù)據(jù)進(jìn)行協(xié)商。由于元數(shù)據(jù)小于采集的數(shù)據(jù)，傳輸元數(shù)據(jù)消耗的能量相對(duì)較少。在發(fā)送或接收數(shù)據(jù)之前，每個(gè)節(jié)點(diǎn)都必須檢查各自可用的能量狀況。如果處于低能量水平，則必須中斷一些操作，如充當(dāng)數(shù)據(jù)中轉(zhuǎn)（路由器）的角色，停止數(shù)據(jù)轉(zhuǎn)發(fā)操作。SPIN協(xié)議中使用三種類型的消息：a)ADV，用于新數(shù)據(jù)廣播。當(dāng)一個(gè)傳感器節(jié)點(diǎn)有數(shù)據(jù)需要傳輸時(shí)，它就使用ADV數(shù)據(jù)包（包括元數(shù)據(jù)）對(duì)外廣播。b) REQ，用于請(qǐng)求發(fā)送數(shù)據(jù)。當(dāng)一個(gè)傳感器節(jié)點(diǎn)希望接收DATA數(shù)據(jù)包時(shí)，便發(fā)送REQ。c)DATA，包含了元數(shù)據(jù)頭、傳感器節(jié)點(diǎn)采集數(shù)據(jù)的數(shù)據(jù)包。

在發(fā)送DATA 數(shù)據(jù)包之前，傳感器節(jié)點(diǎn)首先對(duì)外廣播ADV消息。如果一個(gè)鄰近節(jié)點(diǎn)在收到ADV后希望接收該DATA數(shù)據(jù)包，那么它向該節(jié)點(diǎn)發(fā)送一個(gè)REQ；接著該節(jié)點(diǎn)向它發(fā)送DATA數(shù)據(jù)包。類似的過(guò)程繼續(xù)下去，DATA數(shù)據(jù)包就會(huì)被傳輸?shù)竭h(yuǎn)方sink。

SPIN家族的協(xié)議有很多，主要的兩個(gè)協(xié)議是SPIN－1和SPIN－2。SPIN－1協(xié)議就是前面闡述的基本三次握手協(xié)商機(jī)制。擴(kuò)展的SPIN－2協(xié)議是基于預(yù)設(shè)值資源提醒機(jī)制協(xié)議。當(dāng)資源充足時(shí)，SPIN－2使用的是三次握手協(xié)商機(jī)制；當(dāng)資源低于某個(gè)預(yù)設(shè)值時(shí)，它將減少參與數(shù)據(jù)發(fā)送的次數(shù)。總體上，SPIN－1和SPIN－2都是簡(jiǎn)單高效的協(xié)議，不用維護(hù)每個(gè)鄰居的狀態(tài)。其他的SPIN家族協(xié)議還有：a) SPIN－PP，用于點(diǎn)對(duì)點(diǎn)的通信，如hop－by－h(huán)op路由；b) SPIN－EC，在SPIN－PP的基礎(chǔ)上考慮了節(jié)點(diǎn)的功耗，當(dāng)能量不低于設(shè)定閾值的節(jié)點(diǎn)時(shí)才參與數(shù)據(jù)交換；c) SPIN－BC，設(shè)計(jì)了廣播信道，使所有在有效半徑內(nèi)的節(jié)點(diǎn)可以同時(shí)完成數(shù)據(jù)交換；d) SPIN－RL，是對(duì)SPIN－BC的完善，主要考慮如何恢復(fù)無(wú)線鏈路引入的分組差錯(cuò)與丟失。

該協(xié)議的優(yōu)點(diǎn)在于其簡(jiǎn)單性，節(jié)點(diǎn)僅需要知道其鄰近節(jié)點(diǎn)，無(wú)須其他拓?fù)湫畔ⅰPIN協(xié)議的缺陷也很明顯，它的擴(kuò)展受限，如果sink對(duì)網(wǎng)絡(luò)中的多個(gè)事件感興趣，sink周圍的節(jié)點(diǎn)能量會(huì)很快耗盡；另外，數(shù)據(jù)會(huì)在整個(gè)網(wǎng)絡(luò)中傳輸。

3．1．5EAR協(xié)議[7]

EAR（energy aware routing)協(xié)議是一個(gè)反應(yīng)式路由協(xié)議，其主要目的是用于延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。協(xié)議操作可以分成三個(gè)主要階段：

a)協(xié)議初始化。由sink點(diǎn)發(fā)起協(xié)議初始化過(guò)程。初始化報(bào)文攜帶了路徑代價(jià)信息，每一個(gè)轉(zhuǎn)發(fā)初始化報(bào)文的節(jié)點(diǎn)都將本節(jié)點(diǎn)的代價(jià)加入到路徑的總代價(jià)中。這樣每個(gè)節(jié)點(diǎn)均能建立一條或多條到sink節(jié)點(diǎn)的路由，并且知道每條路由的代價(jià)。

b)數(shù)據(jù)傳輸。節(jié)點(diǎn)向sink點(diǎn)傳送數(shù)據(jù)時(shí)，可從多條路徑中按某種概率選取一條。代價(jià)越大的路徑，轉(zhuǎn)發(fā)的概率越小。

c)路由維護(hù)。通過(guò)局部的泛洪來(lái)更新路徑代價(jià)。如果節(jié)點(diǎn)的能量低于某個(gè)門(mén)限，可以使這條路徑失效。

EAR路由協(xié)議類似于DD協(xié)議，但它維護(hù)多條路徑而不是強(qiáng)迫使用一個(gè)最優(yōu)化路徑。它通過(guò)一定的概率選擇路徑并維護(hù)它們，概率值的確定依賴于每條路徑的能量情況。這樣可以防止過(guò)分依賴某條路徑而導(dǎo)致該路徑能量消耗過(guò)大。仿真結(jié)果表明，該協(xié)議相比DD協(xié)議可以使網(wǎng)絡(luò)壽命延長(zhǎng)44%；但該協(xié)議的缺點(diǎn)是需要收集位置信息并建立編址機(jī)制，增加了路由建立的復(fù)雜度和開(kāi)銷。

3．1．6GBR協(xié)議[8]

GBR（gradient based routing)路由協(xié)議是DD協(xié)議的一種改進(jìn)路由算法，目的是使數(shù)據(jù)報(bào)文傳輸?shù)目偺鴶?shù)最小。其關(guān)鍵思想是當(dāng)DD協(xié)議中的興趣消息擴(kuò)散到整個(gè)網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)需要記錄到sink節(jié)點(diǎn)的最小跳數(shù)，將這個(gè)跳數(shù)作為節(jié)點(diǎn)的height；鄰居節(jié)點(diǎn)之間的height差就是鏈路的梯度。當(dāng)數(shù)據(jù)報(bào)文發(fā)往sink節(jié)點(diǎn)時(shí)，沿著梯度最大的方向傳送。GBR使用諸如數(shù)據(jù)融合、負(fù)載均衡等技術(shù)，以獲得均勻的網(wǎng)絡(luò)負(fù)載。當(dāng)多條路徑都要通過(guò)同一個(gè)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)就成為一個(gè)關(guān)鍵節(jié)點(diǎn)。關(guān)鍵節(jié)點(diǎn)可以采用三種數(shù)據(jù)分發(fā)技術(shù)：

a)隨機(jī)機(jī)制。當(dāng)有多個(gè)鏈路的梯度相同時(shí)，節(jié)點(diǎn)隨機(jī)選擇一個(gè)梯度方向發(fā)送。

b)基于能量的機(jī)制。當(dāng)一個(gè)節(jié)點(diǎn)的能量低于某個(gè)門(mén)限時(shí)，該節(jié)點(diǎn)增加它的梯度。這樣，節(jié)點(diǎn)就能減少中繼的數(shù)據(jù)量。

c)基于流的機(jī)制。當(dāng)一條路徑正在為其他數(shù)據(jù)流服務(wù)時(shí)，新增加的數(shù)據(jù)流用另外一條路徑傳輸，從而使各條路徑流量均衡。

仿真結(jié)果表明，GBR協(xié)議可以均衡網(wǎng)絡(luò)負(fù)載、延長(zhǎng)網(wǎng)絡(luò)壽命；但GBR協(xié)議同樣增加了路由建立的復(fù)雜度。

3．1．7HREEMR協(xié)議[9]

HREEMR（highly－resilient，energy－efficient multi－path routing)與Rumor協(xié)議的不同之處在于它利用多路徑(multi－path)技術(shù)實(shí)現(xiàn)了能源有效的故障恢復(fù)，并解決了DD協(xié)議為提高協(xié)議的健壯性，采用周期低速率擴(kuò)散數(shù)據(jù)而帶來(lái)的能源浪費(fèi)問(wèn)題。它采用與DD相同的本地化算法建立source與sink間的最優(yōu)路徑p。為了保障p發(fā)生失效時(shí)協(xié)議仍能正常運(yùn)行，構(gòu)建多條與p不相交的冗余路徑，一旦發(fā)生失效現(xiàn)象，即可啟用冗余路徑進(jìn)行通信。

3．1．8SMECN協(xié)議[10]

SMECN(small minimum energy communication network)協(xié)議是節(jié)點(diǎn)定位的路由協(xié)議，它是在針對(duì)Ad hoc網(wǎng)絡(luò)設(shè)計(jì)的MECN[11]協(xié)議基礎(chǔ)上進(jìn)行改進(jìn)的。該協(xié)議通過(guò)構(gòu)建具有ME(最小能量)屬性的子圖來(lái)降低傳輸數(shù)據(jù)所消耗的能量，從而更好地滿足了WSNs對(duì)節(jié)能性的需求。仿真結(jié)果顯示，在廣播范圍能夠達(dá)到環(huán)繞著廣播機(jī)區(qū)域內(nèi)的所有節(jié)點(diǎn)的情況下，SMECN 構(gòu)建的子圖小于MECN 構(gòu)建的子圖，在拓?fù)渥兓惶l繁的傳感器網(wǎng)絡(luò)中能夠很好地應(yīng)用。

3．1．9GEM協(xié)議[12]

GEM(graph embedding)路由協(xié)議是一種適用于數(shù)據(jù)中心存儲(chǔ)(data－centric storage)方式的基于位置的路由協(xié)議。其基本思想是建立一個(gè)虛擬極坐標(biāo)系統(tǒng)，用來(lái)表示實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。網(wǎng)絡(luò)中的節(jié)點(diǎn)形成一個(gè)以匯聚節(jié)點(diǎn)為根的帶環(huán)樹(shù)(ringed tree)。每個(gè)節(jié)點(diǎn)用樹(shù)根的跳數(shù)和角度范圍來(lái)表示。整個(gè)網(wǎng)絡(luò)形成一個(gè)樹(shù)狀的拓?fù)浣Y(jié)構(gòu)，越靠近樹(shù)根的節(jié)點(diǎn)，對(duì)網(wǎng)絡(luò)整體的結(jié)構(gòu)就了解越多。當(dāng)一個(gè)節(jié)點(diǎn)不知道目的節(jié)點(diǎn)的路由時(shí)，就將數(shù)據(jù)報(bào)文向根的方向傳送，直到某個(gè)節(jié)點(diǎn)知道了到目的節(jié)點(diǎn)的路由。由于大部分?jǐn)?shù)據(jù)都是發(fā)送到樹(shù)根的，這種樹(shù)狀結(jié)構(gòu)能很好地應(yīng)用于傳感器網(wǎng)絡(luò)中。

GEM帶環(huán)樹(shù)的建立由匯聚點(diǎn)發(fā)起，通過(guò)逐步擴(kuò)散從而建立覆蓋整個(gè)網(wǎng)絡(luò)的拓?fù)錁?shù)。它不依賴節(jié)點(diǎn)的精確位置信息，將網(wǎng)絡(luò)的實(shí)際拓?fù)溆成涞揭粋€(gè)易于進(jìn)行路由處理的邏輯拓?fù)渲小．?dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)位置改變引起網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)，樹(shù)的調(diào)整比較復(fù)雜，因此GEM適應(yīng)于拓?fù)浣Y(jié)構(gòu)相對(duì)穩(wěn)定的傳感器網(wǎng)絡(luò)。

3．1．10SCBR協(xié)議[13]

一般基于地理位置信息的路由協(xié)議均要求每個(gè)節(jié)點(diǎn)具備感知位置信息的能力，這在傳感器網(wǎng)絡(luò)中往往無(wú)法實(shí)現(xiàn)。SCBR路由算法只需少數(shù)節(jié)點(diǎn)具有精確位置信息即可進(jìn)行正確路由的定位路由機(jī)制。其基本思想是通過(guò)少數(shù)能夠得到精確位置信息的節(jié)點(diǎn)(稱為信標(biāo)點(diǎn))來(lái)確定一個(gè)全局的坐標(biāo)系。通過(guò)迭代算法計(jì)算其他節(jié)點(diǎn)在這個(gè)坐標(biāo)系中的位置；當(dāng)所有節(jié)點(diǎn)的坐標(biāo)位置確定之后，就可以使用貪婪算法選擇合適的路由。因此，協(xié)議的關(guān)鍵部分是利用信標(biāo)節(jié)點(diǎn)建立坐標(biāo)系以及確定其他節(jié)點(diǎn)在坐標(biāo)系中的位置。

SCBR(scalable coordinate－based routing)提到在三種情況下確定節(jié)點(diǎn)位置的算法：a)網(wǎng)絡(luò)實(shí)際邊界上的節(jié)點(diǎn)都是信標(biāo)節(jié)點(diǎn)；b)使用兩個(gè)信標(biāo)節(jié)點(diǎn)；c)使用一個(gè)信標(biāo)節(jié)點(diǎn)的情況。信標(biāo)點(diǎn)越少，計(jì)算越復(fù)雜。與其他基于位置的路由協(xié)議相比，SCBR只需要知道少數(shù)節(jié)點(diǎn)精確位置信息，其降低了對(duì)傳感器節(jié)點(diǎn)的要求，使網(wǎng)絡(luò)成本降低。但是，為了確定全局坐標(biāo)系和節(jié)點(diǎn)在坐標(biāo)系中的位置，節(jié)點(diǎn)需要交換大量信息，通信開(kāi)銷大；同時(shí)使用迭代算法，節(jié)點(diǎn)的計(jì)算開(kāi)銷也大。

3．1．11SAR協(xié)議[14]

SAR(sequential assignment routing)協(xié)議是第一個(gè)具有QoS的路由協(xié)議。該協(xié)議通過(guò)構(gòu)建以sink的單跳鄰居節(jié)點(diǎn)為根節(jié)點(diǎn)的多播樹(shù)實(shí)現(xiàn)傳感器節(jié)點(diǎn)到sink的多跳路徑。它的特點(diǎn)是路由決策不僅要考慮到每條路徑的能源，還涉及到端到端的延遲需求和待發(fā)送數(shù)據(jù)包的優(yōu)先級(jí)。仿真結(jié)果顯示，與只考慮路徑能量消耗的最小能量度量協(xié)議相比， SAR的能量消耗較少。該算法的缺點(diǎn)是不適用于大型的和拓?fù)漕l繁變化的網(wǎng)絡(luò)。

3．2層次路由協(xié)議

在層次型結(jié)構(gòu)的網(wǎng)絡(luò)中，具有某種關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點(diǎn)組成簇。在簇內(nèi)，通常有一個(gè)按一定規(guī)則選舉產(chǎn)生的，被稱為簇頭(cluster head)的節(jié)點(diǎn)。除了簇頭節(jié)點(diǎn)外，一般節(jié)點(diǎn)成員(cluster member)的功能較簡(jiǎn)單，無(wú)須維護(hù)復(fù)雜的路由信息。

層次化路由機(jī)制具有以下幾個(gè)優(yōu)點(diǎn)[15]：

a)簇頭融合了成員節(jié)點(diǎn)的數(shù)據(jù)之后再進(jìn)行轉(zhuǎn)發(fā)，減少了數(shù)據(jù)通信量，從而節(jié)省了網(wǎng)絡(luò)能量。

b)成員節(jié)點(diǎn)大部分時(shí)間可以關(guān)閉通信模塊，由簇頭構(gòu)成一個(gè)更上一層的連通網(wǎng)絡(luò)來(lái)負(fù)責(zé)數(shù)據(jù)的長(zhǎng)距離路由轉(zhuǎn)發(fā)。這樣既保證了原有覆蓋范圍內(nèi)的數(shù)據(jù)通信，也在很大程度上節(jié)省了網(wǎng)絡(luò)能量。

c)成員節(jié)點(diǎn)的功能比較簡(jiǎn)單，無(wú)須維護(hù)復(fù)雜的路由信息，這大大減少了網(wǎng)絡(luò)中路由控制信息的數(shù)量，減少了通信量。

d)分簇拓?fù)浣Y(jié)構(gòu)便于管理，有利于分布式算法的應(yīng)用，可以對(duì)系統(tǒng)變化作出快速反應(yīng)，具有較好的可擴(kuò)展性，適合大規(guī)模網(wǎng)絡(luò)。

e)與平面路由相比，更容易克服傳感器節(jié)點(diǎn)移動(dòng)帶來(lái)的問(wèn)題。

層次路由的缺點(diǎn)就是簇頭節(jié)點(diǎn)容易成為網(wǎng)絡(luò)的瓶頸，因此要求路由算法具有一定的容錯(cuò)性；同時(shí)簇的負(fù)載均衡也是分布式成簇的一大挑戰(zhàn)。

3．2．1LEACH協(xié)議[16]

LEACH的基本思想是通過(guò)等概率地隨機(jī)循環(huán)選擇簇頭，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)，從而達(dá)到降低網(wǎng)絡(luò)能量耗費(fèi)、延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。LEACH的執(zhí)行過(guò)程是周期性的，每輪循環(huán)的基本過(guò)程是：在簇的建立階段，每個(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ù)該簇簇頭。在數(shù)據(jù)傳輸階段，簇內(nèi)的所有節(jié)點(diǎn)按照TDMA(時(shí)分復(fù)用)時(shí)隙向簇頭發(fā)送數(shù)據(jù)。簇頭將數(shù)據(jù)融合之后把結(jié)果發(fā)給基站。在持續(xù)工作一段時(shí)間之后，網(wǎng)絡(luò)重新進(jìn)入啟動(dòng)階段，進(jìn)行下一輪的簇頭選取并重新建立簇。LEACH算法包括以下幾個(gè)階段:簇頭的產(chǎn)生；簇的形成；簇的路由。

為了節(jié)省資源開(kāi)銷，LEACH穩(wěn)定階段的持續(xù)時(shí)間要長(zhǎng)于建立階段的持續(xù)時(shí)間。該協(xié)議采用隨機(jī)選舉簇頭的方式避免簇頭過(guò)分消耗能量，提高了網(wǎng)絡(luò)生存時(shí)間；數(shù)據(jù)聚合能有效減少通信量。但協(xié)議層次化的目的在于數(shù)據(jù)聚合，仍采用一跳通信，雖然傳輸時(shí)延小，但要求節(jié)點(diǎn)具有較大功率通信能力，擴(kuò)展性差，不適合大規(guī)模網(wǎng)絡(luò)；即使在小規(guī)模網(wǎng)絡(luò)中，離sink點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)由于采用大功率通信也會(huì)導(dǎo)致生存時(shí)間較短；而且頻繁選舉簇頭引發(fā)的通信量耗費(fèi)了能量。

LEACH－C[17]和LEACH－F(LEACH－fixed)[17]都是集中式的簇頭產(chǎn)生算法，由基站負(fù)責(zé)挑選簇頭。LEACH是由每個(gè)節(jié)點(diǎn)根據(jù)隨機(jī)數(shù)自主決定是否當(dāng)選簇頭，每輪產(chǎn)生的簇頭沒(méi)有確定的數(shù)量和位置。LEACH－C根據(jù)全局信息挑選簇頭，可以有效解決LEACH的這一不足，每個(gè)節(jié)點(diǎn)把自身地理位置和當(dāng)前能量報(bào)告給基站。基站根據(jù)所有節(jié)點(diǎn)的報(bào)告計(jì)算平均能量。當(dāng)前能量低于平均能量的節(jié)點(diǎn)不能成為候選簇頭，從剩余候選節(jié)點(diǎn)中選出合適數(shù)量和最優(yōu)地理位置的簇頭集合是一個(gè)NP問(wèn)題。基站根據(jù)所有成員節(jié)點(diǎn)到簇頭的距離平方和最小的原則，采用模擬退火算法解決該NP問(wèn)題。最后，基站把簇頭集合和簇的結(jié)構(gòu)廣播出去。

LEACH－F也在LEACH基礎(chǔ)上作了一些改變。簇的形成與LEACH－C一樣，也是基站采用模擬退火算法生成簇。同時(shí)，基站為每個(gè)簇生成一個(gè)簇頭列表，指示簇內(nèi)節(jié)點(diǎn)輪流當(dāng)選簇頭的順序。一旦簇形成之后，簇的結(jié)構(gòu)就不再改變，簇內(nèi)節(jié)點(diǎn)根據(jù)簇頭列表依次成為簇頭。與LEACH和LEACH－C相比，LEACH－F最大的優(yōu)點(diǎn)就是無(wú)須每輪循環(huán)都構(gòu)造簇，減少了構(gòu)造簇的開(kāi)銷。但是，LEACH－F并不適合真實(shí)的網(wǎng)絡(luò)應(yīng)用，因?yàn)樗荒軇?dòng)態(tài)處理節(jié)點(diǎn)的加入、失敗和移動(dòng)。同時(shí)它還增加了簇間的信號(hào)干擾。

3．2．2PEGASIS協(xié)議[18]

PEGASIS(power－efficient gathering in sensor information systems)并不是嚴(yán)格意義上的分簇路由協(xié)議，但它借鑒了LEACH中分簇算法的思想。該協(xié)議要求每個(gè)節(jié)點(diǎn)都知道網(wǎng)絡(luò)中其他節(jié)點(diǎn)的位置，通過(guò)貪婪算法選擇最近的鄰節(jié)點(diǎn)形成鏈。動(dòng)態(tài)選舉簇頭的方法很簡(jiǎn)單：設(shè)網(wǎng)絡(luò)中 N個(gè)節(jié)點(diǎn)都用1-N的自然數(shù)編號(hào)，第j輪選取的簇頭是第i個(gè)節(jié)點(diǎn)，i=j mod N(i為0時(shí)，取 N)。簇頭與 sink點(diǎn)一跳通信，利用令牌控制鏈兩端數(shù)據(jù)沿鏈傳送到簇頭本身，在傳送過(guò)程中可聚合數(shù)據(jù)。當(dāng)鏈兩端數(shù)據(jù)都傳送完成時(shí)，開(kāi)始新一輪選舉與傳輸。該協(xié)議通過(guò)避免LEACH協(xié)議頻繁選舉簇頭帶來(lái)的通信開(kāi)銷以及自身有效的鏈?zhǔn)綌?shù)據(jù)聚合，極大地減少了數(shù)據(jù)傳輸次數(shù)和通信量；節(jié)點(diǎn)采用小功率與最近距離鄰節(jié)點(diǎn)通信，形成多跳通信方式，有效地利用了能量，與LEACH協(xié)議相比能大幅提高網(wǎng)絡(luò)生存時(shí)間。但單簇方法使得簇頭成為關(guān)鍵點(diǎn)，其失效會(huì)導(dǎo)致路由失敗；且要求節(jié)點(diǎn)都具有與sink點(diǎn)通信的能力；如果鏈過(guò)長(zhǎng)，數(shù)據(jù)傳輸時(shí)延將會(huì)增大，不適合實(shí)時(shí)應(yīng)用；成鏈算法要求節(jié)點(diǎn)知道其他節(jié)點(diǎn)位置，開(kāi)銷非常大。

3．2．3TEEN協(xié)議[19]

TEEN(threshold sensitive energy efficient sensor network protocol)采用類似LEACH的分簇算法，只是在數(shù)據(jù)傳送階段使用不同的策略。根據(jù)數(shù)據(jù)傳輸模式的不同，通常可以簡(jiǎn)單地把WSNs分為主動(dòng)型(proactive)和響應(yīng)型(reactive)兩種類型。主動(dòng)型WSNs持續(xù)監(jiān)測(cè)周圍環(huán)境，并以恒定速率發(fā)送監(jiān)測(cè)數(shù)據(jù)；而響應(yīng)型WSNs只是在被監(jiān)測(cè)對(duì)象發(fā)生突變時(shí)才傳送監(jiān)測(cè)數(shù)據(jù)。 

TEEN的具體做法是在協(xié)議中設(shè)置了硬、軟兩個(gè)閾值，以減少發(fā)送數(shù)據(jù)的次數(shù)。在每輪簇頭輪換時(shí)將兩個(gè)閾值廣播出去。當(dāng)監(jiān)測(cè)數(shù)據(jù)第一次超過(guò)設(shè)置的硬閾值時(shí)，節(jié)點(diǎn)把這次數(shù)據(jù)設(shè)為新的硬閾值，并在接下來(lái)的時(shí)隙內(nèi)發(fā)送它。之后，只有監(jiān)測(cè)數(shù)據(jù)超過(guò)硬閾值并且監(jiān)測(cè)數(shù)據(jù)的變化幅度大于軟閾值時(shí)，節(jié)點(diǎn)才會(huì)傳送最新的監(jiān)測(cè)數(shù)據(jù)，并將它設(shè)為新的硬閾值。 

通過(guò)調(diào)節(jié)兩個(gè)閾值的大小，可以在精度要求與系統(tǒng)能耗之間取得合理的平衡。采用這樣的方法，可以監(jiān)視一些突發(fā)事件和熱點(diǎn)地區(qū)，減少網(wǎng)絡(luò)通信量。仿真結(jié)果表明，TEEN比LEACH更有效。但TEEN存在兩個(gè)缺陷：a)如果閾值不能達(dá)到，節(jié)點(diǎn)不會(huì)傳送任何數(shù)據(jù)；b)數(shù)據(jù)一旦符合閾值要求，節(jié)點(diǎn)立即傳送，容易造成信號(hào)干擾，如果采用TDMA，則會(huì)造成數(shù)據(jù)延遲。采用ARTEEN[20]則可以在一定程度上克服這種缺陷。ARTEEN是一種混合式的路由協(xié)議，平時(shí)采用與TEEN協(xié)議一樣的工作方式，但是如果超過(guò)一定的時(shí)間節(jié)點(diǎn)沒(méi)有發(fā)送任何數(shù)據(jù)，則強(qiáng)制要求節(jié)點(diǎn)傳送一次數(shù)據(jù)。它的主要缺點(diǎn)是增加了協(xié)議的復(fù)雜度，需要一個(gè)軟、硬門(mén)限值和定時(shí)。

3．2．4GAF協(xié)議[21]

GAF路由協(xié)議是基于位置信息的能量感知路由協(xié)議，其最初是應(yīng)用在Ad hoc網(wǎng)絡(luò)中，但對(duì)于很多傳感器網(wǎng)絡(luò)同樣適用。協(xié)議的基本思想是將網(wǎng)絡(luò)區(qū)域劃分成很多小區(qū)，每個(gè)小區(qū)內(nèi)的節(jié)點(diǎn)相互協(xié)作，一部分節(jié)點(diǎn)保持正常工作狀態(tài)，完成數(shù)據(jù)收集和轉(zhuǎn)發(fā)等任務(wù)；另一部分節(jié)點(diǎn)可以處于睡眠狀態(tài)以節(jié)省能量，延長(zhǎng)網(wǎng)絡(luò)整體壽命。小區(qū)內(nèi)處于正常工作的節(jié)點(diǎn)就相當(dāng)于簇首。

GAF的缺點(diǎn)是每個(gè)節(jié)點(diǎn)都需要通過(guò)GPS得到自己的地理信息，這大大增加了節(jié)點(diǎn)的成本和復(fù)雜度，不適用于很多場(chǎng)合。

3．2．5GEAR協(xié)議[22]

GEAR(geographic and energy aware routing)與GAF協(xié)議一樣基于位置信息的能量感知路由，并將整體網(wǎng)絡(luò)按地理區(qū)域劃分成多個(gè)小區(qū)域。GEAR適用于節(jié)點(diǎn)移動(dòng)較少的網(wǎng)絡(luò)場(chǎng)合。其核心思想是將定向擴(kuò)散協(xié)議的興趣消息限制在一定的區(qū)域，而不是在全網(wǎng)廣播。GEAR協(xié)議中，節(jié)點(diǎn)根據(jù)能量和距離信息估計(jì)到目的地的路徑代價(jià)。當(dāng)一個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的代價(jià)比所有鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)的代價(jià)都大時(shí)，這個(gè)節(jié)點(diǎn)就是路由空洞點(diǎn)。通過(guò)調(diào)整路徑代價(jià)可以解決路由空洞問(wèn)題。每當(dāng)一個(gè)數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)時(shí)，通過(guò)反饋代價(jià)信息調(diào)整下一個(gè)數(shù)據(jù)包的傳輸路徑。數(shù)據(jù)傳輸可以分成兩個(gè)部分：從其他區(qū)域傳遞到目的區(qū)域；在區(qū)域內(nèi)的傳輸。相當(dāng)于群間的傳輸和群內(nèi)的傳輸。

3．2．6SPAN協(xié)議[23]

SPAN是一種基于位置的路由協(xié)議，協(xié)議根據(jù)各個(gè)節(jié)點(diǎn)的地理位置，從中選取出一些協(xié)調(diào)點(diǎn)。協(xié)調(diào)點(diǎn)將組成一個(gè)骨干網(wǎng)；傳感器節(jié)點(diǎn)收集的信息沿著協(xié)調(diào)點(diǎn)組成的骨干網(wǎng)傳送到sink點(diǎn)。協(xié)調(diào)點(diǎn)的選取有一個(gè)基本原則：如果其兩個(gè)鄰居節(jié)點(diǎn)不能直接通信，并且通過(guò)現(xiàn)有的一個(gè)或兩個(gè)協(xié)調(diào)點(diǎn)依然無(wú)法連接通信，那么這個(gè)節(jié)點(diǎn)將成為協(xié)調(diào)點(diǎn)。SPAN協(xié)議中，協(xié)調(diào)點(diǎn)需要保存兩跳或三跳范圍內(nèi)的節(jié)點(diǎn)信息，因此協(xié)調(diào)點(diǎn)并不需要直接相連。

3．2．7SOP[24]

SOP(self－organization protocol)將網(wǎng)絡(luò)中的節(jié)點(diǎn)分成兩類，即傳感器節(jié)點(diǎn)和路由節(jié)點(diǎn)。協(xié)議中的傳感器節(jié)點(diǎn)是可以移動(dòng)的，但路由節(jié)點(diǎn)不能移動(dòng)。路由節(jié)點(diǎn)形成主干網(wǎng)，傳感器節(jié)點(diǎn)收集的數(shù)據(jù)經(jīng)過(guò)路由節(jié)點(diǎn)到達(dá)sink點(diǎn)；每個(gè)傳感器應(yīng)該能夠到達(dá)一個(gè)路由器。路由節(jié)點(diǎn)之間構(gòu)成一個(gè)樹(shù)狀拓?fù)洌瑥亩csink相連接。傳感器節(jié)點(diǎn)僅僅與最近的路由節(jié)點(diǎn)保持連接。協(xié)議的操作可以分成四個(gè)階段:

a)發(fā)現(xiàn)階段——發(fā)現(xiàn)自己的鄰居節(jié)點(diǎn)。

b)自組織階段——形成分簇結(jié)構(gòu)，計(jì)算簇內(nèi)和簇首到sink間的路由，形成樹(shù)狀結(jié)構(gòu)。

c)維護(hù)階段——維護(hù)傳感器節(jié)點(diǎn)移動(dòng)和鏈路斷開(kāi)以后的拓?fù)渥兓＊?/p>

d)重組階段——當(dāng)路由節(jié)點(diǎn)失效或者網(wǎng)絡(luò)出現(xiàn)分裂時(shí)，重新組織網(wǎng)絡(luò)結(jié)構(gòu)。

3．2．8MECN協(xié)議[25]

MECN(minimum energy communication network)協(xié)議本質(zhì)上是為無(wú)線網(wǎng)絡(luò)設(shè)計(jì)的，但是也可直接應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)。該算法的實(shí)質(zhì)是利用低功率的GPS，通過(guò)構(gòu)建最小能量屬性子圖來(lái)降低傳輸數(shù)據(jù)所消耗的能量。協(xié)議為每個(gè)節(jié)點(diǎn)定義了一個(gè)中繼區(qū)域(relay region)。中繼區(qū)域由一系列節(jié)點(diǎn)構(gòu)成， 傳感器通過(guò)中繼區(qū)域?qū)?shù)據(jù)轉(zhuǎn)發(fā)給sink點(diǎn)，比自己直接發(fā)送給sink點(diǎn)更節(jié)約能量，使得各個(gè)節(jié)點(diǎn)的能量消耗更平均。中繼區(qū)域可以通過(guò)局部查找算法確定。

可見(jiàn)，該算法是能自配置的，很好地解決了節(jié)點(diǎn)失效問(wèn)題，能適應(yīng)網(wǎng)絡(luò)動(dòng)態(tài)變化小的應(yīng)用場(chǎng)合；但是對(duì)于節(jié)點(diǎn)運(yùn)動(dòng)的情況而言，該算法計(jì)算中繼區(qū)域內(nèi)的路徑代價(jià)急劇上升。

3．2．9EARSN協(xié)議[26]

EARSN(energy－aware routing for cluster－based sensor network)是基于三層體系結(jié)構(gòu)的路由協(xié)議。該協(xié)議要求網(wǎng)絡(luò)運(yùn)行前由終端用戶sink將傳感器節(jié)點(diǎn)劃分成簇，并通知每個(gè)簇首節(jié)點(diǎn)的ID標(biāo)志和簇內(nèi)所分配節(jié)點(diǎn)的位置信息。傳感器節(jié)點(diǎn)可以活動(dòng)和備用的低能源兩種方式運(yùn)行，并以下面這四種方式之一存在：感知、轉(zhuǎn)發(fā)、感知并轉(zhuǎn)發(fā)、休眠。與一般層次路由協(xié)議不同的是，該協(xié)議的簇首不受能量的限制。它作為網(wǎng)絡(luò)的中心管理者，可以監(jiān)控節(jié)點(diǎn)的能量變化，決定并維護(hù)傳感器的四種狀態(tài)。算法依據(jù)兩個(gè)節(jié)點(diǎn)間的能量消耗、延遲最優(yōu)化等性能指標(biāo)計(jì)算路徑代價(jià)函數(shù)。簇首節(jié)點(diǎn)利用代價(jià)函數(shù)作為鏈路成本，選擇最小成本的路徑作為節(jié)點(diǎn)與其通信的最優(yōu)路徑。經(jīng)仿真分析，該協(xié)議在運(yùn)行過(guò)程中具有很好的節(jié)能性、較高的吞吐量和較低的通信延遲。

4協(xié)議綜合比較

WSNs路由協(xié)議的性能可以從多個(gè)方面進(jìn)行評(píng)價(jià)。本文將從路由協(xié)議的路由結(jié)構(gòu)、網(wǎng)絡(luò)生存時(shí)間、節(jié)點(diǎn)定位、數(shù)據(jù)傳輸路徑、健壯性、擴(kuò)展性、節(jié)能策略、節(jié)點(diǎn)移動(dòng)、安全機(jī)制、是否支持QoS等方面進(jìn)行總結(jié)，如表2所示。

5研究展望

由于WSNs資源有限且與應(yīng)用高度相關(guān)，研究人員在設(shè)計(jì)路由協(xié)議時(shí)采用了多種策略。其中好的協(xié)議應(yīng)具有以下特點(diǎn)：針對(duì)節(jié)點(diǎn)能量高度受限，路由協(xié)議必須要高效利用能量以便延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間；針對(duì)節(jié)點(diǎn)數(shù)據(jù)有相關(guān)性、包頭開(kāi)銷大、節(jié)點(diǎn)能量有限等特點(diǎn)，路由協(xié)議需要采用數(shù)據(jù)聚合、數(shù)據(jù)過(guò)濾等技術(shù)；針對(duì)節(jié)點(diǎn)移動(dòng)性不大的特點(diǎn)，路由協(xié)議不需要維護(hù)節(jié)點(diǎn)的移動(dòng)性；針對(duì)節(jié)點(diǎn)因所處位置及承擔(dān)的責(zé)任不同而導(dǎo)致負(fù)載不平衡的特點(diǎn)，路由協(xié)議需采用通信量負(fù)載均衡技術(shù)；針對(duì)網(wǎng)絡(luò)相對(duì)封閉、不提供計(jì)算等特點(diǎn)，路由協(xié)議只在sink點(diǎn)考慮與其他網(wǎng)絡(luò)互連；針對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)不常編址的特點(diǎn)，路由協(xié)議需采用基于數(shù)據(jù)或基于位置的通信機(jī)制；針對(duì)節(jié)點(diǎn)易失效的特點(diǎn)，通信協(xié)議需采用多路徑機(jī)制。

通過(guò)對(duì)當(dāng)前的各種路由協(xié)議進(jìn)行分析與總結(jié)可以看出，將來(lái)WSNs路由協(xié)議的研究策略與發(fā)展趨勢(shì)如下： 

a)減少通信量。由于WSNs中數(shù)據(jù)通信最為耗能，應(yīng)在協(xié)議中盡量減少數(shù)據(jù)通信量。例如，可采用過(guò)濾機(jī)制以抑制不必要的數(shù)據(jù)上傳；也可采用數(shù)據(jù)聚合機(jī)制。

b)負(fù)載均衡。通過(guò)更加靈活地使用路由策略讓各個(gè)節(jié)點(diǎn)分擔(dān)數(shù)據(jù)傳輸，平衡節(jié)點(diǎn)的剩余能量，以提高整個(gè)網(wǎng)絡(luò)的生存時(shí)間。

c)支持移動(dòng)性。目前的WSNs路由協(xié)議對(duì)網(wǎng)絡(luò)的拓?fù)涓兄芰鸵苿?dòng)性的支持比較差，許多路由協(xié)議只適應(yīng)在拓?fù)渥兓苌俚膱?chǎng)合。因此，如何在控制協(xié)議開(kāi)銷的前提下，支持節(jié)點(diǎn)移動(dòng)及拓?fù)涓兄锹酚蓞f(xié)議研究的一個(gè)重要挑戰(zhàn)。

d)容錯(cuò)性。由于WSNs節(jié)點(diǎn)容易發(fā)生故障，應(yīng)盡量利用節(jié)點(diǎn)易獲得的網(wǎng)絡(luò)信息計(jì)算路由，以確保在路由出現(xiàn)故障時(shí)能夠盡快得到恢復(fù)，并且可采用多路徑傳輸來(lái)提高數(shù)據(jù)傳輸?shù)目煽啃浴＊?/p>

e)組播路由。其本身就是網(wǎng)絡(luò)的一個(gè)難題，在WSNs的動(dòng)態(tài)環(huán)境中進(jìn)行組播路由則更具有挑戰(zhàn)性。

f)路由安全。由于WSNs的固有特性，其路由協(xié)議極易受到安全威脅，尤其是在軍事應(yīng)用中。目前的路由協(xié)議很少考慮安全問(wèn)題，因此在一些應(yīng)用中必須考慮設(shè)計(jì)具有安全機(jī)制的路由協(xié)議。

g)可擴(kuò)展性。這是衡量路由協(xié)議性能的一個(gè)重要方面。無(wú)論平面路由協(xié)議還是分級(jí)的路由協(xié)議，提高可擴(kuò)展性以適應(yīng)網(wǎng)絡(luò)規(guī)模的擴(kuò)大是一個(gè)無(wú)法回避的問(wèn)題。

h)QoS路由。它對(duì)于一些視頻及圖像傳感等實(shí)時(shí)應(yīng)用非常必要。在WSNs中，由于增加了動(dòng)態(tài)拓?fù)洹①Y源有限等因素，QoS路由的實(shí)現(xiàn)是WSNs路由協(xié)議研究的極大挑戰(zhàn)。

i)跨層協(xié)議優(yōu)化。將網(wǎng)絡(luò)層與鏈路層協(xié)議甚至應(yīng)用層協(xié)議等結(jié)合起來(lái)設(shè)計(jì)跨層路由協(xié)議，以實(shí)現(xiàn)協(xié)議的優(yōu)化。j)與 IPv6結(jié)合。IPv6協(xié)議已成為下一代網(wǎng)絡(luò)的核心，WSNs也將朝著與IPv6結(jié)合的方向發(fā)展。但由于受資源的限制， WSNs只能采用精簡(jiǎn)格式的IPv6協(xié)議。

WSNs路由協(xié)議將繼續(xù)向基于數(shù)據(jù)、基于位置的方向發(fā)展。這是由 WSNs 一般不統(tǒng)一編址和以數(shù)據(jù)、位置為中心的特點(diǎn)決定的。

6結(jié)束語(yǔ)

無(wú)線傳感器網(wǎng)絡(luò)的路由算法是無(wú)線傳感器網(wǎng)絡(luò)研究中的熱點(diǎn)問(wèn)題。本文對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的各種典型協(xié)議進(jìn)行了分類，對(duì)算法的思想進(jìn)行了總結(jié)，并分析和比較了各典型協(xié)議的特點(diǎn)。盡管人們提出了多種較好的路由算法，但與實(shí)際應(yīng)用還有一段差距，需要進(jìn)一步改進(jìn)原有算法或者設(shè)計(jì)新的算法，以便路由算法能適應(yīng)各種實(shí)際應(yīng)用。本文最后總結(jié)了理想路由協(xié)議應(yīng)該具有的特點(diǎn)以及路由協(xié)議未來(lái)的研究策略及發(fā)展趨勢(shì)。

參考文獻(xiàn)：

［1］AKYILDIZ I F， SU Wei－lian， SANKARASUBRAMANIAM Y，et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，40(8):102－114.

[2]POTTIE G， KAISER W. Wireless integrated network sensors[J].Communications of the ACM，2000，43(5):551－558.

[3]HAAS Z J， HALPERN J Y， LI Li. Gossip－based Ad hoc routing[C]//Proc of IEEE INFOCOM. New York: IEEE Communications Society， 2002:1707－1716.

[4]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D， et al. Direc－ted diffusion for wireless sensor networking[J].IEEE/ACM Trans on Networking， 2003，11(1):2－16.

[5]BRAGINSKY D， ESTRIN D. Rumor routing algorithm for sensor networks[C]//Proc of the 1st Workshop on Sensor Networks and Applications. 2002:22－31.

[6]KULIK J， W R HEINZELMAN W R， BALAKRISHNAN H. Negotiation－based protocols for disseminating information in wireless sensor networks[J].Wireless Networks， 2002，8 (2－3):169－185.

[7]SHAH R C， RABAEY J. Energy aware routing for low energy Ad hoc sensor networks[C]//Proc of IEEE Wireless Communications and Networking Conference.2002:350－355.

[8]SCHURGERS C， SRIVASTAVA M B. Energy efficient routing in wireless sensor networks[C]//Proc of Communications for Network－Centric Operations: Creating the Information Force.2001:357－361.

[9]GANESAN D， GOVINDAN R， SHENKER S， et al. Highly－resilient， energy efficient multi－path routing in wireless sensor networks[C]//Proc of Mobile Computing and Communications Review.2002:251－254.

[10]LI Li， HALPERN J Y. Minimum energy mobile wireless networks revisited[C]//Proc of IEEE International Conference on Communications. Piscataway: IEEE， 2001:278－283.

[11]LIN C R， GERLA M. Adaptive clustering for mobile wireless networks[J]. IEEE Journal on Selected Areas in Communications， 1997，15(7):1265－1275.

[12]NEWSOME J， SONG D. GEM: graph embedding for routing and data centric storage in sensor networks without geographic information [C]//Proc of the 1st ACM Conf on Embedded Networked Sensor Systems.2003:76－88.

[13]RAO A， RATNASAMY S， PAPADIMITRIOU S，et al. Geographic routing without location information[C]//Proc of the 9th Annual International Conf on Mobile Computing and Networking.2003:96－108.

[14]SOHRABI K， GAO J， AILAWADHI V， et al. Protocols for self－organization of a wireless sensor network [J]. IEEE Personal Communications， 2000，7(5):16－27.

[15]沈波，張世永，鐘亦平. 無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J]. 軟件學(xué)報(bào)，2006，17(7):1588－1600.

[16]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H.Energy efficient communication protocol for wireless micro－sensor networks[C]//Proc of the 33rd Hawaii International Conference on System Sciences. 2000:3005－3014.

[17]HEINZELMAN W.Application－specific protocol architectures for wireless networks [D]. Boston: Massachusetts Institute of Technology， 2000.

[18]LINDSEY S， RAGHAVENDRA C S.PEGASIS:power－efficient gathe－ring in sensor information systems[C]//Proc of IEEE Aerospace Conference. Montana: IEEE Aerospace and Electronic Systems Society， 2002: 1125－1130.

[19]MANJESHWAR A，AGARWAL D P. TEEN: a routing protocol for enhanced efficiency in wireless sensor networks[C]//Proc of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing.2001: 2009－2015.

[20]MANJESHWAR A， AGRAWAL D P. APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks[C]//Proc of International，Parallel and Distributed Processing Symposium.Florida:IEEE Computer Society，2002:195－202.

[21] XU Ya， HEIDEMANN J， ESTRIN D. Geography informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking.New York:ACM Press，2001: 70－84.

[22]YU Yan， ESTRIN D， GOVINDAN R. Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks，UCLA/CSD－TR－01－0023[R].[S.l.]: UCLA Computer Science Department， 2001:1－11.

[23]CHEN Ben－jie，JAMIESON K，BALAKRISHNAN H， et al. SPAN: an energy efficient coordination algorithm for topology maintenance in Ad hoc wireless networks[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking.New York:ACM Press，2001:85－96.

[24]SUBRAMANIAN L， KATZ R H. An architecture for building self configurable systems[C]//Proc of the 1st ACM International Symposium on Mobile Ad hoc Networking and Computing.Piscateway:IEEE Press，2000: 63－73.

[25]RODOPLU V， MENG T H. Minimum energy mobile wireless networks [J]. IEEE Journal Selected Areas in Communications， 1999，17(8):1333－1344.

[26]YOUNIS M， YOUSSEF M， ARISHA K. Energy aware routing in cluster－based sensor networks[C]//Proc of the 10th IEEE International Symposium on Modeling， Analysis and Simulation of Computer and Telecommunications Systems.Washington DC:IEEE Computer Society，2002:129－136.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文