一種低延遲可靠數據收集算法在帶狀無線傳感網的應用

大同煤炭職業技術學院 山西大同 037000

無線傳感器網 WSN (Wireless Sensor Network) 所研究的數據收集是其最基本的問題[1]。對于應用在管道輸送、峽谷、野外長城及長距離橋梁的無線傳感器網絡，其共同的特點表現為長距離的帶狀結構[2-4]，從兩側聚集到匯聚點 Sink 的數據流，在其附近容易形成嚴重的熱點區，會形成不均衡的能量消耗[5]。傳統意義上的 WSN 靜態數據收集有較大局限性，然而，采用移動 Sink 數據收集能夠在一定程度上緩解熱點問題，但因其移動速度不快 (0.4～ 2.5 m/s)，因此，數據收集延遲 6～21 min[6]，無法滿足性能的需求。如何在有效延遲內使感知數據傳輸到 Sink，經典方法是定位數據節點的同時建立通往 Sink 的路徑，比如，在網絡內部建立廣播自身位置的機制，但該方法影響其網絡生命期。Y.Yue 等人[7]提出的一種移動 Sink 數據收集協議是基于代理節點的，代理節點保存其位置信息，且隨其位置變化而實時更新，而源節點通過代理節點就可獲得 Sink 的位置信息。B.V.Cherkassky 等人[8]提出的基于訪問與代理節點的協議，訪問節點可直接與 Sink 進行通信，代理節點經訪問節點傳輸至 Sink，協議生成代理節點的方式使其能耗較大。R.Rahmatizadeh 等人[9]提出基于 WSN 節能混合路由的方式，通過降低平均跳數與控制消息，使控制消息的開銷減少，從而增強網絡的壽命。E.B.Hamida 等人[10]提出的 E-TAG 增強跟蹤算法與 TAG跟蹤算法，使定位 Sink 需要的消息轉發跳數得到了降低。M.Frenkel-morgenstern 等人[11]提出的基于查詢LBDD 移動 Sink 數據收集方法，通過其給線節點發送查詢請求，接收到含有位置信息的查詢請求，從而獲得最新的節點位置信息，不足之處是線節點變成了熱點區域，使網絡生命期降低。T.Kato 等人[12]提出的E-TRAIL 協議是基于構建數據傳輸樹產生的，Sink給指定區域里的節點廣播其位置信息，其離開傳輸樹后，把其位置信息廣播給兩跳節點，使源節點到 Sink一直擁有路由路徑。以上方法無法滿足帶狀傳感器網的應用場景，存在可靠性不足及高延遲的問題。

移動 Sink 帶狀傳感器網的方法是專門針對其延遲性能要求提出的，提出的 DCFAN 數據收集算法是基于同步代理節點轉發 Sink，其貢獻主要是：根據帶狀傳感網的特點，創建移動 Sink 同步代理節點，進而創建線節點序列以便存儲代理節點，然后通過代理節點轉發數據至 Sink 節點，代理節點中斷輸送恢復機制及線節點更新機制使數據傳輸可靠性得到了保證。

1 網絡模型

在帶狀區域內部節點隨機分布，兩端分別用 L、R 表示。通信模型與節點感知采用布爾模型[13]，通信與感知半徑分別用RT、RG表示。Sink 在 L 側，在區域內向 R 側移動收集數據，然后返回初始位置。在L、R 的中心點布置能量較足的節點NL、NR。假設每個節點位置已知，則存儲空間與 Sink 的能量沒有限制。

2 DCFAN 算法

2.1 線節點

2.1.1 線節點序列構建

同步代理節點的位置信息由線節點來存儲。網絡模型圖如圖 1 所示。算法始于節點NL，至NR結束，采用貪心算法確定下一節點，則節點

圖1 網絡模型圖Fig.1 Network model

Nj=argmin∑Nk∈Neighbor (Ni) dist (Nk，NR)，(1)最終形成有序序列L=(LNL，LN1，…，LNR)。若L是連續性的，且其中節點符合帶狀約束與能量約束條件，則L被稱做線節點序列。

(1) 連續性約束 假設非空節點集N＝(N0，N1，N2，…，Nk) 中，存在唯一始節點N0與唯一尾節點Nk，任意節點Ni的前驅節點Ni-1與后繼節點Ni+1都是唯一的，則N是連續性節點序列。當前驅與后繼節點滿足

就稱為鄰居節點；若Ni，Nj同時符合

則稱Nj是Ni的后繼節點，Ni是Nj的前驅節點。依此創建的序列叫做連續節點序列。

(2) 能量約束 序列L=(LNL，LN1，…，LNR)中，任一線節點需符合的能量約束條件。若某個線節點不滿足此條件，會使線節點的更新機制觸發，從而使數據傳輸可靠性得到保證。

(3) 帶狀約束 為使帶形區域軸兩側的邊緣節點不被選做線節點，從而減弱算法性能，增大存儲代理節點的能量開銷與時間，故而線節點序列L中，任意線節點至中心軸的距離，不大于d。

式中：(xi，yi) 為節點LNi位置的坐標；Ax＋By＋C＝0為帶形區域內中心軸方程，由已知的兩點坐標進行確定。

2.1.2 線節點更新機制

線節點因為匯聚點的移動而不斷對其存儲的同步代理節點信息進行更新，因數據節點發送位置請求消息，使線節點消耗的能量不均衡，局部節點能量會消耗殆盡，從而使線節點序列無法滿足連續性約束條件，致使數據傳輸的可靠性不高。鑒于此，應對能量較低的線節點進行及時更新，更新過程包含消息通知和候補線節點查找 2 個步驟。

(1) 查找候補線節點 當線節點LNi不符合式 (4)的條件時，則其鄰居節點LNk被選取為新的線節點，且要求LNk同時是LNi-1、LNi與LNi+1的鄰居節點，即LNk是LNi-1、LNi與LNi+1通信覆蓋區域內具有最大能量的節點，并符合

節點LNi的通信范圍用Si來表征。若LNk同時符合帶狀約束與能量約束的條件，則LNk替換LNi，因此新序列依然是線節點序列。如果沒有節點LNk符合此條件，就按最短路徑算法[14-16]，起點為LNk-1，查找能替換節點LNi的節點序列，假設此序列中的所有節點都符合帶狀約束與能量約束條件，則新序列L＝(LNL，LN1，…，Ni-1，Nk1，Nk2，Nkm，Ni+1，…，NR) 即是線節點序列。

(2) 消息通知 當LNk或Nk1、Nk2、Nkm接收到節點LNi發送的角色變更消息后，則向其鄰居節點發送LN_Notice 的通知消息，以保證所有節點對其鄰居節點的線節點信息進行了存儲。最后，當鄰居節點接收到LNi發送的線節點取消消息后，刪除鄰居表里的LNi節點信息，以完成更新線節點。

2.2 構造代理節點

2.2.1 構造代理節點的原則

需要定義數據跟隨機制以達到 Sink 移動時對數據收集的低延時性能要求。

假設非空節點集N＝(N0，N1，N2，…，Nk)，除了首尾 2 節點之外，余下所有節點Ni都對前驅與后繼節點地址進行了存儲，因而序列中任意節點可發送到端節點。

代理節點由 Sink 在移動過程中產生，直接進行通信的是直接代理節點，不能直接通信的叫做間接代理節點。如果 Sink 移動到同步代理節點通信范圍外，就會導致數據傳輸中斷。為了數據傳輸的可靠性，Sink 在離開同步代理節點通信范圍，產生新的同步代理節點前，需滿足條件

代理節點更新頻率用參數ε控制，其更新速度隨參數值變小而變慢，對數據傳輸的可靠性影響較大；相反，更新速度過快，會頻繁發送控制消息從而使節點能耗增大。為了更新頻率與降低通信開銷，且滿足能量約束條件，代理節點ANi+1應是到 Sink 距離最近的ANi的鄰居節點。

Sink 與代理節點ANi的通信覆蓋范圍用 Sink 與Si來表示。Sink 節點的位置信息與剩余能量在代理節點序列生成的過程中完成收集。Sink 生成代理節點序列的過程如圖 2 所示，后繼代理節點位置信息存儲下來，奠定了通過代理節點跟隨機制將數據轉發至 Sink的基礎。

2.2.2 更新同步代理節點

如果同步代理節點的鄰居節點含有線節點類型的節點，則位置消息就直接發送至此線節點。否則，因地理路由算法簡單、方便實現、存儲空間與計算開銷低的優勢，源節點至 Sink 數據轉發的基礎路由可由該算法表征[17-20]。代理節點通過此算法把位置消息發送至鄰居節點里距目標點P(xi，yi) 最近的節點。循環此步驟，直至鄰居節點是線節點的Nx節點收到此位置消息。然后發送至其鄰居線節點，用LNi表示此線節點。節點ANi+1(xANi+1，yANi+1) 至帶狀區ζ軸線的垂足為此目標點。假設后繼與前序節點位置信息已被線節點序列中所有節點存儲，使用跟隨機制將獲得代理節點位置信息的線節點向后繼與前序節點分別發送位置消息，直至首尾兩端節點都接受此消息，則序列中的同步代理節點就完成了位置信息更新。

2.2.3 代理節點的生命期

用參數T表示代理節點生命期，若任意代理節點的生命期大于T，則此節點失效。隨著T值變大，則數據傳輸的延遲也會隨之變大，也會引發網絡能量空洞；若值變小，則存儲的代理節點極易失效，會造成反復請求發送位置消息，使通信能耗變大[21-22]。所以T值的選取需要綜合考慮數據收集延遲與節點的能耗。

2.3 主動定位

2.3.1 請求節點位置信息

移動 Sink 收集數據如圖 3 所示。當代理節點失效或者未保存代理節點時，就依據地理路由算法發送節點位置請求消息給最近的線節點，按圖 3 所示的路徑 1 進行傳輸。線節點LNi接收含轉發節點序列的節點位置請求消息，依據傳輸路徑，發送代理節點位置響應消息給節點Ni，按圖 3 所示的路徑 2 進行傳輸。全部節點在位置消息與節點位置響應消息傳輸過程中同時得到同步代理節點的位置信息[23]。所以，不需要發送請求，就可將節點能耗、控制消息規模、數據收集延遲降低。

圖3 移動 Sink 收集數據Fig.3 Data collection by mobile Sink

2.3.2 數據傳輸

得到同步代理節點位置信息的節點Ni，經算法將數據發給節點ANi。若在 Sink 通信區域內，則將數據直接發給 Sink；若其離開通信區域，則通過跟隨機制將數據傳至 Sink：Ni→…→ANi→ANi+1→…→Sink，按圖 3 所示的路徑 3 進行傳輸；若代理節點的生命期T過大，會導致代理節點傳輸中斷，即后續代理節點能量耗盡，致使數據傳輸失敗。為解決該難題，節點ANk-1得到同步代理節點位置后，則數據傳輸重啟，進而傳至 Sink。

2.4 算法局限性

DCFAN 算法如果應用于非帶狀傳感器網絡中，會有如下局限性。

(1) DCFAN 算法沿帶狀區域中心軸構建線節點序列，若將此方法在非帶狀傳感器網絡中應用，會使線節點和代理節點與邊緣數據節點之間的距離增大，及代理節點的存儲和普通節點的能耗增加。

(2) 同步代理節點的形成會受 Sink 移動方式的改變，對算法效率造成影響。移動 Sink 在帶狀網絡帶狀區內的兩端進行固定往返運動，因此，同步代理節點的分布呈現規律性。而 Sink 在非帶狀網絡的運動比較靈活，所以代理節點分布呈現不規則性，對代理節點的更新造成一定的影響，從而使算法性能降低。

3 時間復雜度

假設帶狀網絡節點數量用N表示，P和M分別表示代理節點與線節點的數量。將該算法分成 4 個步驟，每個步驟的時間復雜度為：

(1) 步驟 1 構造線節點序列。該階段線節點序列只考慮了節點能量與節點位置，時間復雜度最壞情況下是 O(M)；

(2) 步驟 2 更新同步代理節點。該階段地理路由算法將位置消息發送至鄰近線節點，則序列L中的同步代理節點得到更新，時間復雜度最壞情況下是O(N)+O(M)；

(3) 步驟 3 代理節點位置信息請求。請求代理節點信息向最近的線節點，且按原路徑返回同步代理節點位置信息，時間復雜度最壞情況下是 O(N)；

(4) 步驟 4 傳輸源節點數據至 Sink。首先將數據從源節點傳輸至代理節點，進而通過跟隨機制轉發至 Sink，時間復雜度最壞情況下是 O(N)+O(P)。

綜上所述，該算法的時間復雜度最壞情況下為O(M+N+P)。

4 仿真分析

仿真平臺選取軟件 MATLAB 7.0，在 900 m×400 m 的帶狀區域里隨機布置 300 個傳感器節點，將不同移動 Sink 速度下 LBDD、E-TRAIL 和 DCFAN 算法的平均網絡能耗、數據轉發延遲性能及轉發率進行比較。3 種算法的仿真中，皆用單個移動 Sink，初始能量為 250 mJ，感知半徑為 10 m，通信半徑為 85 m。

(1) 網絡節點平均能耗 不同移動 Sink 速度下平均節點能耗如圖 4 所示。從圖 4 可以看到，3 種算法的平均節點能耗隨 Sink 移動速度的增加而變大。DCFAN 算法由于代理節點更新頻率隨 Sink 移動速度的增加而變大，致使增大了數據傳輸量，從而使節點能耗變大；而 LBDD 算法由于沒有節點更新機制，當傳輸數據增大時，平均節點能耗更加嚴重；E-TRAIL算法的分簇過程消耗大量能量，其運行過程中，Sink的線路更新又受限于兩跳范圍，故能耗較平穩，從圖 4 可以看出，E-TRAIL 算法整體平均節點能耗較大，而且變化比較平緩。

圖4 不同 Sink 移動速度下平均節點能耗Fig.4 Average node energy consumption at various Sink moving speed

(2) 數據收集延遲 在不同移動 Sink 速度下的數據收集延遲如圖 5 所示。從圖 5 可以看到，3 種算法的數據收集延遲隨及 Sink 移動速度的增加而減少。另外，DCFAN 算法性能低于 LBDD 算法，原因在于 DCFAN 算法依賴代理節點將數據轉發至 Sink，而 LBDD 算法是直接將數據發送給線節點。E-TRAL的數據收集延遲在 3 種算法中表現最短，原因是簇頭節點以多跳的形式將數據直接傳輸給 Sink，但其是以犧牲網絡節點能量來得到優異的數據收集延遲性能。

圖5 不同 Sink 移動速度下數據收集延遲Fig.5 Data collection delayat various Sink moving speed

(3) 數據收集率 Sink 節點的數據量和源節點采集的數據量的比稱為數據收集率。不同移動 Sink 速度下數據收集率如圖 6 所示。從圖 6 可以看到，3 種算法的數據收集率隨 Sink 移動速度的增加而降低。折線圖中 DCFAN 算法的數據收集率在 3 種算法表現最好，原因在于在通信區域內 Sink 收集的節點將數據發給代理節點，然后通過跟隨機制傳給 Sink，中斷處理機制則確保在傳輸失敗后數據傳輸的可靠性；隨網絡運行，LBDD 算法在傳輸大塊數據時，會使局部節點的能量消耗殆盡，從而使數據傳輸可靠性降低；而 E-TRAIL 算法簇頭周邊節點隨其周期性更新，致使負擔越來越重，導致節點失效，從而使 Sink 數據收集率降低。

圖6 不同 Sink 移動速度下數據收集率Fig.6 Data collection rate at various Sink moving speed

5 結論

基于同步代理節點轉發移動 Sink，DCFAN 算法定義了同步代理節點與線節點，通過跟隨機制、代理節點將數據傳輸至 Sink。研究結果表明：DCFAN 算法的數據收集延遲與平均網絡節點能耗較低，而其數據收集率較高。因此，該算法可在對數據收集延遲有相關要求的帶狀無線傳感網場景中得到應用。