4.4.1　基于數據的路由協議

無線傳感器網絡是一種以數據為中心的網絡，因此以數據為中心的路由協議是專門針對無線傳感器網絡設計的，在無線傳感器網絡中也是提出最早的一類路由協議。目前有許多比較經典的路由協議算法，下面介紹兩種比較有代表性的路由協議算法，即傳感器信息協商協議（Sensor Protocol for Information via Negotiation，SPIN）和定向擴散（Directed Diffusion，DD）路由協議算法。

1. SPIN路由協議算法

SPIN是一種以數據為中心的路由協議，主要是針對泛洪路由協議做了一定的改進。

1）基本思想

SPIN是一類基于協商、以數據為中心的路由協議。SPIN假設所有的網絡節點都是潛在的Sink節點，某一個要發送數據的節點把數據傳送給任何需要該數據的節點，并通過協商機制減少網絡中傳輸的數據量。節點只廣播其他節點沒有的數據以減少冗余數據，從而有效地減少能量消耗。

SPIN使用三種類型的數據包，即ADV、REQ和DATA。

（1）ADV：廣播數據包，當一個節點需要發送數據時，就向周圍廣播一個帶有本節點屬性、類型等信息的數據包，該數據包通常要遠遠小于數據本身的大小。

（2）REQ：請求包，如果接收到ADV的節點需要該數據就發送一個REQ。

（3）DATA：數據包，接收REQ后，要發送數據的節點就發送一個DATA，DATA中包含有效數據。

SPIN的協商過程采用了三次握手方式，其工作流程如圖4.1所示。源節點在發送DATA信息前，首先向相鄰節點廣播包含DATA數據描述機制的ADV信息，如圖4.1（a）所示；需要該DATA信息的相鄰節點向源節點發送REQ請求消息，如圖4.1（b）所示；源節點在收到REQ請求信息后，有選擇地將DATA信息發送給相應的相鄰節點，如圖4.1（c）所示；收到DATA后，該相鄰節點可以作為信息源，重復前面的過程將DATA信息傳送給網絡中的其他節點，如圖4.1（d）、圖4.1（e）和圖4.1（f）所示。需要注意的是，當節點中已經存在相鄰節點傳送的DATA數據時，就不會再發送REQ報文來請求數據，如圖4.1（e）所示，有一個節點沒有發送REQ消息，網絡中所有節點最終都將獲得該數據。

SPIN除了提供協商機制，還引入了基于閾值的能量適應機制，當節點發送數據時，首先查看其剩余能量，如果能量充足的話，則采用協商過程進行通信；否則便減少參與行為，并通過進一步協商以確保參與后其剩余能量仍高于最低能量閾值。

在SPIN中，節點不需要維護相鄰節點的信息，這在一定程度上能適應節點移動的情況。在能耗方面，模擬結果證明SPIN比傳統模式減少一半以上能耗。不過，該算法不能確保數據一定能夠到達目標節點，尤其不適用于高密度節點分布的情況。

2）主要問題

SPIN通過節點之間的協商，解決Flooding協議和Gossiping協議的內爆和重疊問題。

Flooding協議是一種最原始的泛洪協議，用于無線傳感器網絡，在此協議中，節點從其他相鄰節點接收到消息之后立即向其所有相鄰節點廣播，直至數據到達目的節點才停止。例如，節點S想要將數據發送給目的節點D，可以通過三個相鄰節點A、B、C來實現，直至傳送到目的節點D。但是，Flooding協議存在嚴重的不足：內爆和重疊。內爆現象是指節點在同一時刻接收到了多份相同的數據，如圖4.2所示，節點D收到來自A、B、C三個節點的數據，這將浪費大量能量。重疊現象是指節點多次收到來自同一區域傳感器節點的關于同一事件的數據，如圖4.3所示。重疊區域內的事件被相鄰的節點探測到，那么這個事件就會通過這兩個節點傳到Sink節點，當節點更多時，傳送的次數也就更多，浪費了大量能量。

Gossiping協議對Flooding協議進行了一定的改進，在發送數據時不再采用廣播的形式，而是隨機選取相鄰節點來進行數據的傳送，這就抑制了內爆現象，但卻無法解決由重疊現象引起的事件的重復發送問題。

SPIN通過協商機制，解決了傳統的Flooding協議和Gossiping協議的內爆和重疊問題，另外SPIN還能夠進行簡單的能量監測，即根據能量剩余值來進行路由的選擇，并進行簡單的數據融合，從而大大減小網絡負載。

數據融合的核心思想是以數據為中心，數據融合可在多層實現，在轉發數據的過程中，中間節點不是根據最短路徑來傳送數據的，而是首先對多個數據源的數據進行融合處理，提取里面的有效信息，然后再轉發給下一跳節點，從而不用多個數據源同時對Sink節點發送數據，可大大減小網絡負載。

總的說來，SPIN非常簡單而且不需要維護周圍節點的狀態，協議的轉發只牽涉到相鄰節點之間的數據通信。但是這樣也存在一個問題，即如果相鄰節點都不需要接收該信息，那么該信息將不能夠繼續轉發，Sink節點將接收不到該信息；另外，SPIN沒有考慮到多個節點同時向一個節點發送消息的情況，有關的退避算法機制還需要進一步考慮。

2. DD路由協議算法

定向擴散（Directed Diffusion，DD）路由協議是一種以數據為中心的路由協議，采用的是基于查詢的方法。與上面所提到的SPIN有所不同，DD路由協議是通過Sink節點在全網內廣播自己需要的數據的，同時在廣播的過程中形成了一條由節點到Sink節點的路徑，節點采集到數據之后將會沿著這條路徑來傳送數據，Sink節點通過選擇一條最優的路徑來接收數據。

1）基本思想

DD路由協議提供了一種查詢的方法，該協議中包括三個不同的階段：興趣擴散、梯度建立和路徑加強。如圖4.4所示，Sink節點首先向全網廣播一條被稱為“興趣”的數據包，告知自己需要的數據，這就是興趣擴散，它是建立路由的開始。興趣數據包被中間節點逐步轉發到網絡中相關節點，在這個過程中，逐步地轉發建立了多條從興趣的源節點到Sink節點的路徑，這個過程就叫作梯度建立。依據最低代價的原則，興趣數據包傳送到相關數據之后，梯度建立也就完成了。當網絡中的相關節點采集到興趣數據包中所要求的數據之后，也采取廣播的方式來向Sink節點發送數據，通過多跳方式最終傳送到Sink節點，Sink節點就會從多條路徑接收到源節點傳送過來的數據。之后，Sink節點根據最小代價原則從這些路徑中選擇一條最優的路徑來繼續接收數據，其余路徑將被放棄。

2）主要問題

定向擴散路由協議的主要問題就是怎樣有效地在Sink節點興趣擴散過程中進行路徑的梯度建立，數據接收之后強化路徑的最終選擇和維護。

在興趣擴散階段，基站節點周期性地向相鄰節點廣播興趣消息。興趣消息中含有任務類型、目標區域、數據發送速率、時間戳等參數。每個節點在本地保存一個興趣列表，對于每一個興趣，列表中都有一個表項記錄該興趣消息的相鄰節點、數據發送率和時間戳等任務相關信息，以建立該節點向基站節點傳遞數據的梯度關系。每個興趣可能對應多個相鄰節點，每個相鄰節點對應一個梯度信息。通過定義不同的梯度相關參數，可以適應不同的應用需求。每個表項還有一個字段用來表示該表項的有效時間值，超過這個時間后，節點將刪除這個表項。當節點收到相鄰節點的興趣消息時，首先檢查興趣列表中是否存有參數類型與收到興趣相同的表項，而且對應的發送節點是該相鄰節點。如果有對應的表項，就更新表項的有效時間值：如果只是參數類型相同，但不包含發送該興趣消息的相鄰節點，就在相應的表項中添加這個相鄰節點；對于其他任意情況，都要建立一個新的表項來記錄這個新的興趣。如果收到的興趣消息和節點剛轉發的興趣消息一樣，為了避免消息循環則丟棄該信息；否則，轉發收到的興趣消息。

當傳感器節點采集到與興趣匹配的數據時，把數據發送到梯度上的相鄰節點，并按照梯度上的數據傳輸速率設定傳感器模塊采集數據的速率。由于可能從多個相鄰節點收到興趣消息，節點向多個相鄰節點發送數據，基站節點可能收到經過多個路徑的相同數據。中間節點收到其他節點轉發的數據后首先查詢興趣列表的表項，如果沒有匹配的興趣表項就丟棄數據；如果存在相應的興趣表項，則首先檢查與這個興趣對應的數據緩沖池（Data Cache），數據緩沖池用來保存最近轉發的數據，如果在數據緩沖池中有與接收到的數據匹配的副本，說明已經轉發過這個數據，為避免出現傳輸環路而丟棄這個數據；否則，檢查該興趣表項中的相鄰節點的信息，如果設置的相鄰節點的數據發送速率大于或等于接收的數據速率，則全部轉發接收的數據；如果記錄的相鄰節點數據發送速率小于接收的數據速率，則按照比例轉發。對于轉發的數據，數據緩沖池中保留一個副本，并記錄轉發的時間。

定向擴散路由協議通過正向增強機制來建立優化的路徑，并根據網絡拓撲的變化修改數據轉發的梯度關系。興趣擴散階段的目的是建立源節點到基站節點的數據傳輸路徑，數據源節點以較低的速率采集和發送數據，這個階段建立的梯度稱為探測梯度（Probe Gradient）。基站節點在收到從源節點發來的數據后，啟動建立到源節點的增強路徑，后續的數據將沿著增強的路徑以較高的數據速率進行傳輸。加強后的梯度稱為數據梯度（Data Gradient）。假設以數據傳輸延遲作為路由增強的標準，基站節點選擇先發來最新數據的相鄰節點作為增強路徑的下一跳節點，向該相鄰節點發送路徑增強消息，路徑增強消息中包含新設定的較高發送數據速率值；相鄰節點收到消息后，經過分析確定該消息描述的是一個已有的興趣，只是增加了數據發送速率，則斷定這是一條路徑增強消息，從而更新相應興趣表項中到相鄰節點的發送數據速率。同時，按照同樣的規則選擇增強路徑的下一跳相鄰節點。

路由增強的標準也不是唯一的，可以選擇在一定時間內發送數據最多的節點作為路徑增強的下一跳節點，也可以選擇數據傳輸最穩定的節點作為路徑增強的下一跳節點。在增強路徑上的節點如果發現下一跳節點的發送數據速率明顯減小，或者收到來自其他節點的新位置估計信息，則推斷增強路徑的下一跳節點失效，就需要使用上述路徑增強機制重新確定下一跳節點。

定向擴散路由協議是一種經典的以數據為中心的路由協議。基站節點根據不同的應用需求定義不同的任務類型、目標區域、上報間隔等參數的興趣消息，通過向網絡中泛洪這些查詢請求進行路由的建立。收到消息的中間節點通過對興趣消息的緩存與合并，根據參數值計算創建包含數據傳輸率、下一跳節點信息的數據傳遞梯度，從而建立多條指向基站節點的路徑。興趣消息中指定的地理區域內的傳感器節點啟動監測任務，并周期性地上報監測數據。基站節點在數據傳輸過程中，選擇某條路徑發送上報間隔更小或更大的興趣消息，以達到減弱或增強路徑的目的。定向擴散路由協議由于采用多路徑，魯棒性好；使用數據聚合能減少通信量；基站節點根據實際情況增強路徑可以合理地利用能量；使用查詢驅動的機制建立路由，避免了保存全網信息。但是為了動態適應節點失效、拓撲變化等情況，定向擴散路由協議需要周期性地廣播興趣消息，另外，梯度的建立也需要較大的時間和能量開銷。