一種低延遲可靠數(shù)據(jù)收集算法在帶狀無線傳感網(wǎng)的應(yīng)用

大同煤炭職業(yè)技術(shù)學(xué)院 山西大同 037000

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

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

1 網(wǎng)絡(luò)模型

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

2 DCFAN 算法

2.1 線節(jié)點

2.1.1 線節(jié)點序列構(gòu)建

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

圖1 網(wǎng)絡(luò)模型圖Fig.1 Network model

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

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

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

則稱Nj是Ni的后繼節(jié)點，Ni是Nj的前驅(qū)節(jié)點。依此創(chuàng)建的序列叫做連續(xù)節(jié)點序列。

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

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

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

2.1.2 線節(jié)點更新機制

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

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

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

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

2.2 構(gòu)造代理節(jié)點

2.2.1 構(gòu)造代理節(jié)點的原則

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

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

代理節(jié)點由 Sink 在移動過程中產(chǎn)生，直接進行通信的是直接代理節(jié)點，不能直接通信的叫做間接代理節(jié)點。如果 Sink 移動到同步代理節(jié)點通信范圍外，就會導(dǎo)致數(shù)據(jù)傳輸中斷。為了數(shù)據(jù)傳輸?shù)目煽啃裕琒ink 在離開同步代理節(jié)點通信范圍，產(chǎn)生新的同步代理節(jié)點前，需滿足條件

代理節(jié)點更新頻率用參數(shù)ε控制，其更新速度隨參數(shù)值變小而變慢，對數(shù)據(jù)傳輸?shù)目煽啃杂绊戄^大；相反，更新速度過快，會頻繁發(fā)送控制消息從而使節(jié)點能耗增大。為了更新頻率與降低通信開銷，且滿足能量約束條件，代理節(jié)點ANi+1應(yīng)是到 Sink 距離最近的ANi的鄰居節(jié)點。

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

2.2.2 更新同步代理節(jié)點

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

2.2.3 代理節(jié)點的生命期

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

2.3 主動定位

2.3.1 請求節(jié)點位置信息

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

圖3 移動 Sink 收集數(shù)據(jù)Fig.3 Data collection by mobile Sink

2.3.2 數(shù)據(jù)傳輸

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

2.4 算法局限性

DCFAN 算法如果應(yīng)用于非帶狀傳感器網(wǎng)絡(luò)中，會有如下局限性。

(1) DCFAN 算法沿帶狀區(qū)域中心軸構(gòu)建線節(jié)點序列，若將此方法在非帶狀傳感器網(wǎng)絡(luò)中應(yīng)用，會使線節(jié)點和代理節(jié)點與邊緣數(shù)據(jù)節(jié)點之間的距離增大，及代理節(jié)點的存儲和普通節(jié)點的能耗增加。

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

3 時間復(fù)雜度

假設(shè)帶狀網(wǎng)絡(luò)節(jié)點數(shù)量用N表示，P和M分別表示代理節(jié)點與線節(jié)點的數(shù)量。將該算法分成 4 個步驟，每個步驟的時間復(fù)雜度為：

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

5 結(jié)論

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