定向擴散路由

定向擴散(Directed Diffusion,DD)路由協定是一種基於查詢的路由機制。匯聚(sink)節點通過興趣訊息(interest)發出查詢任務,採用洪泛方式傳播興趣訊息到整個區域的或部分區域內的所有感測器節點。興趣訊息用來表示查詢的任務,表達網路用戶對檢測地區感興趣的信息,例如檢測區的溫度、濕度和光照等環境信息。在興趣訊息傳播的過程中,協定逐跳地在每個感測器節點上建立反向的從數據源到匯聚節點的數據傳輸梯度(gradient)。感測器節點將採集到的數據沿著梯度方向傳送到匯聚節點。

路由機制

1 命名機制

在定向擴散協定中,採用命名機制的方式來描述需要感知的任務。比如,一個車輛跟蹤任務可以描述如下:

類型=有輪機車 //檢測機車位置

間隔= 20ms // 每隔20ms傳送一次事件

持續時間= 10s //興趣持續時間

矩形坐標= [-100.100.200.400] //選定在此矩形區域內的節點

顯然,這樣的任務描述方式通過一組屬性值指定了一個興趣,所以該任務描述就稱之為“興趣”。源節點收集到“興趣”後,也用一組與之相匹配的屬性值來命名它生成的數據。假設一個感測器網路支持一系列任務,在定向擴散協定中,首要任務是選擇一個恰當的命名機制來描述這些任務。本文選擇了一個簡單的屬性組命名機制來描述興趣和數據。一般而言,每個屬性都有相關的數值範圍。例如,類型屬性的數值範圍就是一切可移動的物體,包括車輛,動物和人等。一個屬性的數值可能是它的範圍內的任何子集。本文中,興趣中類型屬性的數值就是有輪機車。

2 興趣的擴散

用命名機制描述的任務就構成了一個興趣,它首先由接收器(sink)產生,然後按照一定的數據率擴散到網路中的每個節點。擴散的數據率可以從描述興趣的屬性組推算,比如指定了一個興趣的間隔為10ms,那么就可以推算出其數據率是每秒傳送100 個任務。sink 節點記錄任務傳送時間,當傳送時間超過興趣屬性設定的持續時間,sink節點就自動清除該任務。當興趣從sink 節點開始擴散時,這個最初的興趣可以被認為是“探索”,它試著確定是否有感測器節點可以檢測到機車位置,一般指定一個較低數據率,假如本文指定數據率是每秒1個事件,則最初興趣可被描述如下:

類型=有輪機車 //檢測機車位置

間隔= 1s // 每隔1s傳送一次事件

持續時間= 10s //興趣持續時間

矩形坐標=[-100.100.200.400]

選定在此矩形區域內的節點定向擴散中設定興趣處於活動狀態,可被sink節點更新。對於同一個興趣,sink 節點只是簡單地更新時間坐標,周期地重複傳送此興趣來進行更新。這樣也可保證了興趣在網路上的可靠傳輸。每個節點都有一個興趣cache,cache 中的每項都對應著不同的興趣。Cache中的每個興趣Entry包含如下幾個欄位:時間欄位指示最近收到匹配興趣的時間信息,梯度欄位指示相鄰節點所需的數據率和數據傳送方向,持續時間欄位指示興趣大致的生命周期。當一個節點接收到一個興趣時,它首先在cache中檢查是否存在相同的興趣,如果沒有相同的興趣Entry存在,那就根據接收到的興趣信息創建一個興趣Entry,包含的信息有數據率和一個指向興趣來源的梯度;如果該節點有相同的興趣Entry存在,但是沒有興趣來源的梯度信息,節點會以指定的數據率增加一個梯度,並更新Entry的時間信息和持續欄位;如果該節點都包含了興趣Entry和梯度信息,那么只是簡單進行時間信息和持續欄位的更新。節點接收到一個興趣之後,類似sink節點,再次把興趣傳送給與自己相鄰的節點。

3 梯度的建立

網路中的節點從相鄰節點接收到一個興趣時,它無法判斷此興趣是否自己已經處理過的,或者是否和另一個方向的鄰節點所發來的興趣相同,因此,當興趣在整個網路擴散的時候,梯度的建立情況如圖2所示。相鄰的兩個節點彼此都建立了一個梯度。這樣就導致了一個節點可能會收到多個同樣的興趣。但是,這樣的梯度建立方法加快了失敗路徑的修復,有利經驗路徑的加強,從而不會產生持久的環路。在感測器網路中,梯度明確指定了數據率和傳送數據的方向。定向擴散協定對於梯度的建立是靈活,在圖1(c)中,使用了兩個梯度來傳送數據,而在圖2中確使用了若干個梯度來傳送數據。總之,定向擴散協定的任務是在感測器節點和sink節點之間建立梯度,以便可靠地傳遞數據。

4 數據的傳播

興趣指定的矩形區域內的某個感測器節點在接收到興趣後,就開始採集數據信息,然後在cache中搜尋相匹配的興趣Entry。本文中,興趣匹配指的是,感測器必須在興趣所指定的範圍內,並且感測器所檢測目標的類型也是有輪機車。興趣匹配之後,感測器節點在它所擁有的梯度信息中,計算出數據率的最大值,以這個速率把數據信息傳送給相鄰節點。本文,最初的數據率是每妙一個數據事件,直到採用了加強規則後才有所改變。感測器節點生成的數據信息如下:類型=有輪機車 //看到的機車型號實例=卡車 //該機車類型實例定位 = [125,220]//節點位置強度= 0.6 // 信號幅度測量置信度= 0.85 // 匹配確信度時間坐標= 01 :20 :40 //事件的產生時間節點從它的相鄰節點接收到一個數據信息後,首先在cache中查找是否有相匹配的興趣Entry,如果沒有匹配的興趣Entry,那么該數據信息就被丟掉,如果找到了匹配的興趣Entry,就在數據cache中查找最近是否收到過相同的數據信息(防止形成環路),如果不存在相同的數據信息,就把該信息加入到cache中,否則就再次丟掉該數據信息。通過檢查數據cache,節點還可以確定再次傳送接收到的數據信息的數據率。 如果所有鄰節點的梯度值大於剛接收到的數據信息的數據率,那么該節點仍以同樣的數據率再次傳送數據信息,如果有鄰節點的梯度值小於此數據率,該節點就降低對此鄰節點的傳送速率。

5 路徑的建立和加強

Sink節點最初以較低的速率在網路中擴散興趣,稱之為“探索”,同樣的,源節點以較低速率建立起的梯度,也稱為“探索”梯度。源節點採集到匹配的數據後,首先沿著“探索”梯度從多條路徑傳送給sink 節點。當sink 節點開始接收數據信息時,它只會加強其中一條路徑,並從該路逕取回自己所需要的數據,稱該路徑為數據梯度。⑴採用正加強建立路徑。“探索”梯度建立完之後,sink節點以一個更小的時間間隔(更高的數據率)再次傳送興趣給任意鄰節點。該鄰節點收到興趣後,發現自己已經接收過相同的興趣,並且當前新數據率比以前的更高,通過查看興趣cache,如果當前的新數據率還要比此時所擁有的“探索”梯度值大,那該鄰節點以同樣的方法繼續加強它的鄰節點,直到到達源節點。⑵失敗路徑的修復和重建。本文前面討論的路徑的正加強是由sink節點觸發的,在定向擴散協定中,為了實現失敗路徑的修復和重建,規定已經加強過的路徑中的節點可以觸發,啟動路徑的加強。如圖4所示,節點c能正常收到來自鄰節點的事件,可是長時間沒有收到來自數據源的事件,節點c就斷定它和數據源之間的路徑出現故障。節點c就主動觸發一次路徑正加強,重新建立它和數據源之間的路徑。⑶採用負加強切斷路徑。採用正加強建立的路徑會導致不只一條路徑被加強了。sink已經加強了鄰節點A的路徑,可是由於又收到來自節點B的事件,對節點B的路徑進行了錯誤加強,這時,從數據源到sink 節點就有兩條路徑被加強了,就會浪費能量。因此,在定向擴散協定中可以採取負加強規則來處理這種情況。經過短暫的運行時間,sink 節點發現節點B 的事件總是來得比節點A 的早,sink 節點就傳送數據率較低的興趣給節點A,讓它降低和sink 節點之間的梯度值,而且,節點A還會把剛才收到的興趣轉發給所有給它傳送過數據的鄰節點,對與它相鄰的節點進行負加強,直到到達源節點。

性能評價

Directed Diffusion 採用鄰節點間通信的方式來避免維護全局拓撲,採用查詢驅動數據傳送模式和局部數據聚集而減少網路數據流,因此是一種高能源有效性的協定。它的缺點是,在需要連續數據傳送的套用中(環境監測等)不能很好的套用;數據命名只能針對於特定的套用預先進行;初始查詢的擴散開銷大。

相關詞條

相關搜尋

熱門詞條

聯絡我們