【文章內(nèi)容簡介】 很大的差別。盡管它和無線自組織網(wǎng)絡(luò)都是無線自組織多跳網(wǎng)絡(luò)，但二者存在著很大的差異。這使得傳統(tǒng)網(wǎng)絡(luò)的路由協(xié)議和MANET 的路由協(xié)議均不適用于無線傳感器網(wǎng)絡(luò)，必須依據(jù)無線傳感器網(wǎng)絡(luò)的特點設(shè)計新的路由協(xié)議，使之 有效地保證無線傳感器網(wǎng)絡(luò)功能的正常實施。 無線傳感器網(wǎng)絡(luò)路由協(xié)議研究 無線傳感器網(wǎng)絡(luò)路由協(xié)議負責(zé)在匯聚節(jié)點和傳感器節(jié)點間可靠地傳輸數(shù)據(jù)。由于其應(yīng)用相關(guān)性，單一的路由協(xié)議不能滿足各種應(yīng)用需求 ,因而研究人員提出了多種不同的路由協(xié)議。但到目前為止，還是缺乏一個完整 和清晰的路由協(xié)議分類。 無線傳感器網(wǎng)絡(luò)的路由協(xié)議不同于傳統(tǒng)網(wǎng)絡(luò)的協(xié)議，它具有能量優(yōu)先、基于局部的拓撲信息、以數(shù)據(jù)為中心和應(yīng)用相關(guān)四個特點，因而，根據(jù)具體的應(yīng)用設(shè)計路由機制時，從四個方面衡量路由協(xié)議的優(yōu)劣： 能量高效 傳統(tǒng)路由協(xié)議在選擇 最優(yōu)路徑時，很少考慮節(jié)點的能量問題。由于無線傳感器網(wǎng)絡(luò)中節(jié)點的能量有限，傳感器網(wǎng)絡(luò)路由協(xié)議不僅要選擇能量消耗小的消息傳輸路徑，更要能量均衡消耗，實現(xiàn)簡單而且高效的傳輸，盡可能地延長整個網(wǎng)絡(luò)的生存期。 可擴展性 無線傳感器網(wǎng)絡(luò)的應(yīng)用決定了它的網(wǎng)絡(luò)規(guī)模不是永遠不變的，而且很容易造成拓撲結(jié)構(gòu)動態(tài)發(fā)生變化，所以要求路由協(xié)議有可擴展性，可以適應(yīng)結(jié)構(gòu)的變化。具體表現(xiàn)于傳感器的數(shù)量、網(wǎng)絡(luò)覆蓋區(qū)域、網(wǎng)絡(luò)生命周期、網(wǎng)絡(luò)時間延遲和網(wǎng)絡(luò)感知精度等方面。 魯棒性 無線傳感器網(wǎng)絡(luò)中，由于環(huán)境和節(jié)點的能量耗盡造成傳感器的失效、 通信質(zhì)量的降低使網(wǎng)絡(luò)變得不可靠，所以在路由協(xié)議的設(shè)計過程中必須考慮軟硬件的高容錯性，保障網(wǎng)絡(luò)的健壯性 。 12 快速收斂性 由于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的動態(tài)變化，要求路由協(xié)議能夠快速收斂，以適應(yīng)拓撲的動態(tài)變化，提高帶寬和節(jié)點能量等有限資源的利用率和消息傳輸效率。 本文根據(jù)不同的無線傳感器網(wǎng)絡(luò)路由結(jié)構(gòu)和數(shù)據(jù)傳輸模型 ,對目前的路由協(xié)議作 了以下四種分類：廣播式路由協(xié)議、坐標(biāo)式路由協(xié)議 、分簇式路由路由和 QoS 的路由協(xié)議，并對各類路由協(xié)議進行了分析。 廣播式路由協(xié)議 擴散法（ Flooding） 擴散法是一 種傳統(tǒng)的網(wǎng)絡(luò)通信路由協(xié)議。它實現(xiàn)簡單，不需要為保持網(wǎng)絡(luò)拓撲信息和實現(xiàn)復(fù)雜的路由算法消耗計算資源，適用于健壯性要求高的場合。但是，擴散法存在信息爆炸問題，即能出現(xiàn)一個節(jié)點可能得到數(shù)據(jù)多個副本的情況，并且也會出現(xiàn)部分重疊的現(xiàn)象，另外，擴散法沒有計算各個節(jié)點的能量，不能作出相應(yīng)的自適應(yīng)路由選擇，當(dāng)一個節(jié)點能量耗盡時，網(wǎng)絡(luò)就會消滅。 具體實現(xiàn)：節(jié)點 A 希望發(fā)送數(shù)據(jù)給節(jié)點 B，節(jié)點 A 首先通過網(wǎng)絡(luò)將數(shù)據(jù)的副本傳給其每一個鄰居節(jié)點，每一個鄰居節(jié)點又將其傳給除 A外的其他的鄰居節(jié)點，直到將數(shù)據(jù)傳到 B為止或者為該數(shù)據(jù)設(shè)定的生命期限 變?yōu)榱銥橹够蛘咚泄?jié)點擁有此副本為止。 定向路由擴散 DD（ Directed Diffusion） 它通過泛洪方式給所有的傳感器節(jié)點廣播興趣消息，伴隨興趣消息在整個網(wǎng)絡(luò)中傳播，協(xié)議逐跳地在每個節(jié)點上建立反向的從數(shù)據(jù)源節(jié)點到基站或者匯聚節(jié)點的傳輸梯度。該協(xié)議通過將來自不同源節(jié)點的數(shù)據(jù)聚集再重新路由達到消除冗余和最大程度降低數(shù)據(jù)傳輸量的目的，因此可以節(jié)約網(wǎng)絡(luò)能量、延長系統(tǒng)的生存期。然而，路徑建立時的興趣消息擴散要執(zhí)行一個泛洪廣播操作，時間和能量消耗非常大。 具體實現(xiàn)：首先是興趣消息擴散，每個節(jié)點都在本地保存一 個興趣列表，其中專門存在一個表項用來記錄發(fā)送該興趣消息的鄰居節(jié)點、數(shù)據(jù)發(fā)送速率和時間戳等相關(guān)信息，之后建立傳輸梯度。數(shù)據(jù)沿著建立好的梯度路徑傳輸。 謠傳路由（ Rumor Routing） 13 D. Braginsky 等人提出的適用于數(shù)據(jù)傳輸量較小的無線傳感器網(wǎng)絡(luò)路由協(xié)議。它的基本思想是時間監(jiān)測區(qū)域的感應(yīng)節(jié)點產(chǎn)生代理消息，代理消息沿著隨機路徑向鄰居節(jié)點擴散傳播。同時，基站或者匯聚節(jié)點發(fā)送的查詢消息也會沿著隨機路徑在網(wǎng)絡(luò)中傳播。當(dāng)查詢消息和代理消息的傳播路徑交叉在一起時就會形成一條基站或匯聚節(jié)點到時間監(jiān)測區(qū)域的 完整路徑。 具體實現(xiàn)：每個傳感器節(jié)點維護一個鄰居列表和一個事件列表，當(dāng)傳感器節(jié)點監(jiān)測到一個事件發(fā)生時，在事件列表中增加一個表項并根據(jù)概率產(chǎn)生一個代理消息，代理消息是一個包含事件相關(guān)信息的分組，將事件傳給經(jīng)過的節(jié)點，收到代理消息的節(jié)點檢查表項進行更新和增加表項的操作。節(jié)點根據(jù)事件列表到達事件區(qū)域的路徑，或者節(jié)點隨機選擇鄰居轉(zhuǎn)發(fā)查詢消息。 SPIN（ Sensor Protocols for Information via Negotiation） W. Heinzelman 等人提出的一種自適應(yīng)的 SPIN 路由 協(xié)議。該協(xié)議假設(shè)網(wǎng)絡(luò)中的所有節(jié)點都是 Sink 節(jié)點，每一個節(jié)點都有用戶需要的信息，而且相鄰的節(jié)點擁有類似的數(shù)據(jù)，所以只要發(fā)送其他節(jié)點所沒有的數(shù)據(jù)。 SPIN 協(xié)議通過協(xié)商完成資源自適應(yīng)算法，即在發(fā)送真正數(shù)據(jù)之前，經(jīng)過協(xié)商壓縮重復(fù)的信息，避免冗余數(shù)據(jù)的發(fā)送；另外， SPIN協(xié)議有權(quán)訪問每個節(jié)點的當(dāng)前能量水平，根據(jù)節(jié)點剩余能量水平調(diào)整協(xié)議，所以可以延長網(wǎng)絡(luò)的生存期。 具體實現(xiàn)： SPIN 采用了 3種數(shù)據(jù)包來通信： ADV 用于新數(shù)據(jù)的廣播，當(dāng)節(jié)點有數(shù)據(jù)要發(fā)送時，利用該數(shù)據(jù)包向外廣播； REQ 用于請求發(fā)送數(shù)據(jù)，當(dāng)節(jié)點希望接收數(shù) 據(jù)時，發(fā)送該報文； DATA 包含帶有 Metadata 頭部數(shù)據(jù)的數(shù)據(jù)報文；當(dāng)一個傳感器節(jié)點在發(fā)送一個 DATA 數(shù)據(jù)包之前，首先向其鄰居節(jié)點廣播式地發(fā)送 ADV 數(shù)據(jù)包，如果一個鄰居希望接收該 DATA 數(shù)據(jù)包，則像該節(jié)點發(fā)送 REQ 數(shù)據(jù)包，接著節(jié)點向其鄰居節(jié)點發(fā)送 DATA數(shù)據(jù)包。 GEAR（ Geographical and Energy Aware Routing） Y. Yu 等人提出了 GEAR 路由協(xié)議，即根據(jù)時間區(qū)域的地址位置，建立基站或者匯聚節(jié)點到時間區(qū)域的優(yōu)化路徑。把 GEAR 劃分為廣播式路由協(xié)議有點不合適，但 是由于它是在利用地理信息的基礎(chǔ)上將數(shù)據(jù)發(fā)送到合適的區(qū)域，而且又是基于 DD 提出，這里仍然作為廣播式的一種。 14 具體實現(xiàn)：首先向目標(biāo)區(qū)域傳遞數(shù)據(jù)包，當(dāng)節(jié)點收到數(shù)據(jù)包時，先檢查是否有鄰居比它更接近目標(biāo)區(qū)域。如有就選擇離目標(biāo)區(qū)域最近的節(jié)點作數(shù)據(jù)傳遞的下一跳節(jié)點。如果數(shù)據(jù)包已經(jīng)到達目標(biāo)區(qū)域，利用遞歸的地理傳遞方式和受限的擴散方式發(fā)布該數(shù)據(jù)。 坐標(biāo)式路由協(xié)議 GEM（ Graph Embedding） J. Newsome 和 D. Song 提出了建立一個虛擬極坐標(biāo)系統(tǒng) GEM 路由協(xié)議，用來代表實際的網(wǎng)絡(luò)拓 撲結(jié)構(gòu)。整個網(wǎng)絡(luò)節(jié)點形成一個以基站或匯聚節(jié)點為根的帶環(huán)樹。每個節(jié)點用距離樹根的跳數(shù)距離和角度范圍兩個參數(shù)表示： 具體實現(xiàn)：首先建立虛擬極坐標(biāo)系統(tǒng)，主要有三個階段：由跳數(shù)建立路由并擴展到整個網(wǎng)絡(luò)形成生成樹型結(jié)構(gòu)，再從葉節(jié)點開始反饋子樹的大小，即樹中包含的節(jié)點數(shù)目，最后確定每個子節(jié)點的虛擬角度范圍。建立好系統(tǒng)之后，利用虛擬極坐標(biāo)算法發(fā)送消息，即節(jié)點收到消息檢查是否在自己的角度范圍之內(nèi)，不在就向父節(jié)點傳遞消息，直到消息到達包含目的位置角度的節(jié)點。另外，當(dāng)實際網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生變化時，需要及時更新，如節(jié)點加入和節(jié)點失 效。 GRWLI（ Geographic Routing Without Location Information） A. Rao 等人提出了建立全局坐標(biāo)系的路由協(xié)議，其前提是需要少數(shù)節(jié)點精確位置信息。首先確定節(jié)點在坐標(biāo)系中的位置，根據(jù)位置進行數(shù)據(jù)路由。關(guān)鍵是利用某些知道自己位置信息的信標(biāo)節(jié)點確定全局坐標(biāo)系及其他節(jié)點在坐標(biāo)系中的位置。 具體實現(xiàn)： A. Rao 等人提出了 3中策略確定信標(biāo)節(jié)點。一是確定邊界節(jié)點都為信標(biāo)節(jié)點，則非邊界節(jié)點通過邊界節(jié)點確定自己的位置信息。在平面情況下，節(jié)點通過鄰居節(jié)點位置的平均值計算 。二是使用兩個信標(biāo)節(jié)點，則邊界節(jié)點只知道自己處于網(wǎng)絡(luò)邊界不知道自己的精確位置消息。引入兩個信標(biāo)節(jié)點，并通過邊界節(jié)點交換信息建立全局坐標(biāo)系。三是使用一個信標(biāo)節(jié)點，到信標(biāo)節(jié)點最大的節(jié)點標(biāo)記自己為邊界節(jié)點。 分簇式路由協(xié)議 為了保證網(wǎng)絡(luò)的可擴展性而且不降低服務(wù)質(zhì)量，很多路由協(xié)議的設(shè)計中使用了分簇的思想。通過將整個無線傳感器網(wǎng)絡(luò)區(qū)域分為若干個簇，每個簇中選舉一個簇頭，通過 15 多跳通信及數(shù)據(jù)融合來減少傳送到匯聚節(jié)點的信息量，從而節(jié)約能量消耗。 LEACH 協(xié)議是最早的分簇協(xié)議，許多其他層次路由協(xié)議都是基于 LEACH的。 LEACH（ Low Energy Adaptive Clustering Hierarchy） MIT 的 Chandrakasan 等人為無線傳感器設(shè)計的一種分簇路由算法，它的基本思想是以循環(huán)的方式隨機選擇簇首節(jié)點，平均分配整個網(wǎng)絡(luò)的能量到每個傳感器節(jié)點，從而可以降低網(wǎng)絡(luò)能源消耗，延長網(wǎng)絡(luò)的生存時間。簇首的產(chǎn)生是簇形成的基礎(chǔ)，簇首的選取一般基于節(jié)點的剩余能量、簇首到基站或匯聚節(jié)點的距離、簇首的位置和簇內(nèi)的通信代價。簇首的產(chǎn)生算法可以被分為分布式和集中式兩種。與節(jié)點直接與匯聚節(jié)點通信相比，LEACH 協(xié)議降低了 7 倍的能耗，與最小傳輸能量路由相比，其降低了 4到 8 倍的能耗。但利用 LEACH算法選舉出的簇頭分布不均勻，且不適合大規(guī)模網(wǎng)絡(luò)及能量不均衡的網(wǎng)絡(luò)。 具體實現(xiàn)： LEACH 不斷地循環(huán)執(zhí)行簇的重構(gòu)過程，可以分為兩個階段：一是簇的建立，即包括簇首節(jié)點的選擇、簇首節(jié)點的廣播、簇首節(jié)點的建立和調(diào)度機制的生成。二是傳輸數(shù)據(jù)的穩(wěn)定階段。每個節(jié)點隨機選一個值，小于某閾值的節(jié)點就成為簇首節(jié)點，之后廣播告知整個網(wǎng)絡(luò)，完成簇的建立。在穩(wěn)定階段中，節(jié)點將采集的數(shù)據(jù)送到簇首節(jié)點，簇首節(jié)點將信息融合后送給匯聚點。一段時間后，重新建 立簇，不斷循環(huán)。 GAF（ Geographic Adaptive Fidelity） Y. Xu 等人提出的一種利用分簇進行通信的路由算法。它最初是為移動 Ad Hoc 網(wǎng)絡(luò)應(yīng)用設(shè)計的，也可以適用于無線傳感器網(wǎng)絡(luò)。其基本思想是網(wǎng)絡(luò)區(qū)被分成固定區(qū)域，形成虛擬網(wǎng)格，每個網(wǎng)格里選出一個簇首節(jié)點在某段時間內(nèi)保持清醒，其他節(jié)點都進入睡眠狀態(tài)，但是簇首節(jié)點并不做任何數(shù)據(jù)匯聚或者融合工作。 GAF 算法即關(guān)掉網(wǎng)絡(luò)中不必要的節(jié)點節(jié)省能量，同樣可以達到延長網(wǎng)絡(luò)生存期的目的。 具體實現(xiàn)：當(dāng)劃分好固定的虛擬網(wǎng)格之后，網(wǎng)絡(luò)中每個節(jié)點利用 GPS 接受卡指示的位置信息將節(jié)點本身與虛擬網(wǎng)格中某個點關(guān)聯(lián)映射起來。網(wǎng)格上同一個點關(guān)聯(lián)的節(jié)點對分組路由的代價是等價的，因而可以使某個特定網(wǎng)格區(qū)域的一些節(jié)點睡眠，而且隨著網(wǎng)絡(luò)節(jié)點數(shù)目的增加可以極大地提高網(wǎng)絡(luò)的壽命，在可擴展性上有很好的表現(xiàn)。 QoS 路由協(xié)議 除了上述三種路由協(xié)議分類之外，還有一些路由協(xié)議在路由建立時，需要考慮吞吐 16 量、端到端時延等 QoS 性能參數(shù)，特別是在采集視頻和音頻數(shù)據(jù)時。 QoS 是一個提供軟實時端到端速率保證、網(wǎng)絡(luò)擁塞控制及負載均衡的路由協(xié)議。該協(xié) 議 要 求 每 個 節(jié) 點 維 護 其 鄰 居 信 息 ， 使 用 SNGF （ stateless geographic nondeterministic forwarding）算法尋找路徑，并確保每個報文分組能以指定速度轉(zhuǎn)發(fā)給匯聚節(jié)點。 SPEED 中的路由模塊 SNGF 和其它四個模塊一起構(gòu)成其協(xié)議的框架，其中信標(biāo)交換模塊主要是搜集節(jié)點的地理位置信息；延遲估計模塊主要計算數(shù)據(jù)包的傳輸延遲并將其發(fā)送給 SNGF模塊；鄰居反饋模塊 NFL主要提供數(shù)據(jù)的轉(zhuǎn)發(fā)率并將其返回給 SNGF模塊；反向重路由模塊主要通過向源節(jié)點發(fā)送回送消息來避免路由空洞。與 MANET 的 DSR和 AODV 協(xié)議相 比， SPEED 在端到端時延、丟包率及能量消耗上均優(yōu)于二者。但是 SPEED協(xié)議在路由過程沒有考慮在多條路徑上傳輸以提高平均壽命 ,傳輸?shù)膱笪囊矝]有優(yōu)先級機制 .[2] 比較與分析 表 21 三種協(xié)議性能比較 經(jīng)過上面的簡單介紹，每個協(xié)議在其設(shè)計的時候都有各自的側(cè)重點和最優(yōu)的方面，按照衡量標(biāo)準(zhǔn)可以把以上協(xié)議做簡略的比較并找出相對較好的一類協(xié)議。其中，如何提 能量高效 可擴展性 魯棒性 快速收斂性 廣 播 擴散法 不是 好 不好 不好 DD 是 受限 好 好 謠傳路由 不是 好 不好 不好 SPIN 是 受限 好 好 GEAR 是 受限 好 好 GEM 是 好 好 好 GRWLI 是 好 好 很好 LEACH 是 不好 好 很好 GAF 是 不好 好 很好 坐 標(biāo) 分 簇 17 供有效的節(jié)能，即能量有效性是無線傳感器網(wǎng)絡(luò)路由協(xié)議最首要注重的方面，可擴展性和魯棒性是路由協(xié)議應(yīng)該滿足的基本要求，而快速收斂性和網(wǎng)絡(luò)存在的時間有緊密的聯(lián)系。依據(jù)上述四個標(biāo)準(zhǔn)，對本文所列舉的路由協(xié)議的比較見表 21。 由上表可見，廣播式總是存在一種矛盾，當(dāng)具有好的擴展性時勢必以差 的魯棒性和能量高效為代價，即以犧牲魯棒性換取擴展性和高能量，這同時也嚴(yán)重影響了節(jié)點的快速收斂性。而坐標(biāo)式彌補了廣播式的不足，可以同時達到四個衡量標(biāo)準(zhǔn)。分簇式相對于前兩種方式來說，具備了較好的性能，可以滿足人們對傳感器網(wǎng)絡(luò)的一般要求。所以，以能量高效、可擴展性、魯棒性和快速收斂性四個基本標(biāo)準(zhǔn)來衡量路由協(xié)議，