移動匯聚節點在倉儲中的數據采集技術及應用

常 李，管有慶

(南京郵電大學 物聯網學院，江蘇 南京 210003)

1 概 述

智能物流和智能倉儲是物聯網發展的重點之一，無線傳感器網絡在智能倉儲中的應用越來越多。目前國內最成熟的智能倉儲解決方案之一就是RFID(射頻識別技術)手持機管理模式，員工可以使用手持機進行單據確認、盤點、查詢統計。RFID手持機管理模式是將電子標簽貼在相應的物品上，用閱讀器收集信息，以此來實現庫存的盤點和查詢等功能。但是，由于現代倉儲的規模越來越大，以及特殊物品(如農作物、化學物品)需要特殊的保存環境，所以在倉庫中直接部署傳感器的感知節點，顯得更為方便。

1.1 研究背景

文獻[1]中指出，當匯聚節點是靜止狀態時，匯聚節點通常需要消耗大量的能量將傳感器節點收集的數據傳送到較遠的地方，因此匯聚節點會很快耗盡能量，導致整個網絡出現故障，無法提供足夠的服務質量。因此針對移動匯聚節點對特定錨節點進行數據收集已延長網絡生存時間的問題進行研究，并通過實驗證明該問題是非確定性多項式的；此外，還提出了一種加權聚集規劃方法(wireless routing protocol，WRP)來延長網絡壽命。

文獻[2]中提出了基于移動匯聚節點的數據采集算法樹，即TCBDGA算法。主要特點是基于樹結構重量，即包括剩余能量、鄰居節點的數量以及到基站的距離，同時考慮到了樹中節點的選擇，缺點是限制了數據收集的范圍。

為了研究移動匯聚節點收集數據的特點和性能，查閱了兩種類別的相關文獻，一類是基于輪詢或基于匯合點的方法，其中移動匯聚節點訪問每個特定的輪詢點或匯合點，通過短程的通信收集傳感器的數據。在這一類方法中，需要考慮能量消耗和數據收集延遲以及移動匯集節點運動軌跡的長短。另一類是采用現有的聚類算法選擇合適的錨節點進行數據聚合和上傳，將傳感器節點組織成不同的簇，并且處于整個網絡的下層。傳感器節點將數據傳送到特定錨節點，而移動匯聚節點從上層的錨節點收集數據，不同的簇就是整個網絡的骨干結構。

文中融合上述兩類方法的優勢，考慮能量消耗的同時盡可能覆蓋更多的數據收集范圍，使用輪詢的方法組織不同的簇，盡最大努力收集數據。

1.2 研究方向

傳感器節點對倉庫的溫度、環境進行監控，能夠有效保證倉庫的環境，增強倉庫的安全系數，出現安全隱患時直接報警。無線傳感器網絡具有低功耗、低成本、低速率等特點，能夠通過微型感知器完成數據采集，并將信息傳給倉庫管理員。文中設計的模型為各無線感知節點被安裝在固定的地方，數據的采集靠人工移動的方法，即在工作人員進行取貨、補貨時的移動車架上安裝收集數據的匯聚節點。考慮到傳感器節點能量較少，所以需要進行能量均衡設計和最短路徑規劃設計，因此提出了基于空間的HLSA算法。

傳感器節點被分布在不同的地方，可能是不同高度、不同距離，根據員工每次需要運動的軌跡，動態地選出收集感知節點信息的錨節點，每次的錨節點都由其中特定的感知節點擔當，這種身份擔當不是固定的，即感知節點和錨節點的身份是可以互相轉化的。錨節點的選擇基于節點剩余能量和與員工運動軌跡的距離。員工手推載貨的推車，車上安裝有移動匯聚節點，從各個錨節點采集信息。一次運動軌跡結束，完成一輪信息采集。按照現在倉儲的搬運、卸貨模式，每天可以完成多次信息采集，對倉庫的環境能達到有效的監控。系統網絡模型如圖1所示。

圖1 系統網絡模型

在系統網絡中，根據數據經過的傳感器節點的跳數，網絡可以劃分為數據直傳傳輸網絡和多跳數據傳輸網絡。由于研究的是固定倉儲，所以選擇了直接數據傳輸網絡。文中選擇了部分感知節點的位置作為錨節點的位置[3]，然后，將移動匯聚節點移動到錨節點的位置收集附近感知節點的數據。

移動匯聚節點的主要特點是完成直接數據傳送和周期性數據采集。在直接傳送數據中，終端節點采用單跳方式將數據發送給移動匯聚節點；在周期性數據采集中，每次貨車運送貨物，都算是一次數據采集周期。從出發點位置到目標貨物位置的路徑可以看成是移動匯聚節點移動的路徑，路徑經過的地方附近的錨節點將收集到的數據傳送過來。其余沒有經過的地方在剩下的周期中會被覆蓋到，每輪數據包括溫度、濕度、方位、剩余的節點能量[4]。

2 系統模型

無線傳感器網絡由傳感器和稱為接收器的特殊節點(即匯聚節點)組成，傳感器能夠感測環境，匯聚節點可以從傳感器收集數據。假設無線傳感器網絡的每個傳感器每隔一段時間可以感測環境數據。另外假設所有傳感節點都隨機分布，節點到節點的距離不一致。為了使所有感知節點到匯聚節點的距離近似相等，進而使運動軌跡最短，減少數據傳輸的總長度和能量消耗，必須挑選出一個錨節點，使得它與各個感知節點的距離近似相等。文中假設了一個無向加權圖G(VG,EG,w)。其中VG表示包含在內的節點，邊(vi，vi+1)表示節點vi和vi+1可以互相通信，EG表示節點剩余的能量，w表示傳感器節點v在一段時間內可以生成的原始數據單位。文中假設網絡生成的感知數據能夠被傳感器節點重復轉發，直到其到達目的地[5]。

在系統網絡中，用包含根節點的樹來收集數據是通用結構，這里采用的樹結構只有兩層，根節點即為錨節點，葉子節點為普通的感知節點。感知節點采集到數據后轉發給錨節點，當移動匯聚節點停留在錨節點附近時，錨節點可以將收集的數據轉發給移動匯聚節點。給定無線傳感器網絡的無向圖G(VG,EG,w)，用于收集數據的簇用T(anchor,VT,ET)表示，其中ET?EG，VT?VG。當數據通過簇結構T(anchor,VT,ET)轉發到錨節點(這邊的錨節點并不是最終的錨節點，只是備用的錨節點)時，樹中的每個節點負責轉發自身收集的數據。因此，在每一段時間，每個除了錨節點以外的節點vnode∈VT，負責轉發自身收集的w(vnode)個單位的數據，p(vanchor)表示由錨節點vanchor轉發的原始數據的單位總和，可以用以下形式定義：

(1)

其中，vT表示樹T中v節點的集合[6]。

需要注意的是，選出的錨節點只收集距離它只有一跳的節點數據，即距離不超過設定的常數R。

文中假設所有的原始數據可以由無線傳感器網絡中的傳感器節點進行聚合，以減少轉發數據的能耗。這里，使用α表示允許聚合成一個數據包的原始數據的最大單位數。因此，通過式1，在每個時間段，每個錨節點負責轉發的分組數可以用δ(vanchor)表示，定義如下：

(2)

等式中向上取整是為了防止w(vanchor)和α的除數不是整數，得出的組數不能包含余數，這樣能夠最大化地將所有數據都被分組。

由于T中的每個錨節點vanchor必須在每個時間段內轉發δ(vanchor)個分組，但是傳感器的能量通常受到限制，當傳感器耗盡能量時，無線傳感器網絡可能無法維持服務質量。這里，假設網絡中每個錨節點消耗的用于發送分組后的剩余能量為Ev。文中假設傳感器節點的壽命周期為能量耗盡的時間，即Ev≤0的時候[7]。

在無線傳感器網絡中，當移動匯聚節點是移動的時候，采集的數據可以轉發到簇中的錨節點，并等待移動匯聚節點來收集數據。由于移動匯聚節點的距離通常受到限制，即工作人員不可能完整遍歷倉庫中所有的錨節點，那么可以設置一個常數L，使得工作人員推著裝有移動匯聚節點的推車經過的錨節點的距離不大于這個常數[8]，即錨節點與移動匯聚節點的距離不超過L。假設員工出發的倉庫門口為初始位置，到達的補貨或取貨地點為終點，那么這條路線上的所有節點，要快速地選出合適的錨節點，使得在有限的距離內的移動匯聚節點可以從錨節點中收集到足夠多的數據。

3 啟發式-列表搜索算法

當給定無線傳感器網絡G和常數L時，為了減少節點的能量消耗，錨節點與它下面的任意感知節點之間的跳距被認為是盡可能最小[9]。為了找到所有可能的錨節點，可以使用啟發式算法。為了挑選出移動匯聚節點路徑到各備用錨節點vanchor的最小跳距離，用式3表示為：

(3)

其中，γ(vanchor)表示最小距離。

對于每個G中的節點，挑選出以移動匯聚節點的移動路線為基礎的具有最小距離γ(vanchor)的節點，作為第一個備用的錨節點，它周圍的距離小于R的其他感知節點，就以該節點為錨節點，形成第一個簇[10]。將第一個錨節點加入到備用列表M中，同時將該簇中的所有節點刪除，接下來重復該步驟，選出第二個備用的錨節點，加入到列表M中。不斷重復上述操作，直到所有節點全部被考慮，這樣選出的所有的備用錨節點都在列表M中[11]。

在啟發式算法的第二步中，用貪婪算法來訪問列表M中所有的備用錨節點。因為錨節點負責收集和報告數據到移動匯聚節點，所以具有較高剩余能量的傳感器節點被優先考慮。另外，當備用的錨節點vanchor具有較高數量的需要轉發分組或最多的剩余能量時，vanchor被認為是最終的錨節點[12]。以上方法確保了能快速找到具有較高剩余能量的傳感器節點。遍歷備用的錨節點來選擇最終的錨節點時，可以根據以下等式：

(4)

當η(vanchor)小于等于0時，只有一種情況，即節點的能量耗盡。這時，將該節點從備用列表M中刪除，該節點所在簇的信息不予收集。等待下一輪數據收集時重新選擇錨節點。當所有的備用錨節點都被遍歷過后，滿足條件的(即η(vanchor)大于0的節點)就是最終的錨節點[13]。

啟發式-列表搜索算法：

Input:VG,EG,R,L,path//輸入所有的節點，節點能量，節點分布的密度，設定錨節點與移動匯聚節點路徑的距離常數，移動匯聚節點的路徑

Output:anchors //輸出所有的錨節點

1.compare all distances between every node and path //比較所有節點與移動路徑的距離

2.Select nodes whose distance are less thanL+R//選出與移動路徑相距不大于L+R的節點

3.rank the distance from small to lager and formation a sorted listN

//按照距離從小到大排序，形成有序表N

//N中的頭節點為備用錨節點，γ(vanchor)表示它與移動路徑的距離

5.ifγ(vanchor)>L

6.RemovevanchorfromN//錨節點與移動路徑大于L時，從N中刪除該錨節點

7.else {pick other nodesvsensorwhose distance withvanchoris lower thanR

//與備用錨節點距離相距小于R的節點作為感知節點

8.formation a cluster with these nodes

//步驟4和7挑選出的感知節點和錨節點形成一個簇

9.Add thevanchortoM//將這個備用錨節點加入至列表M中

10.drop nodes in the cluster from theN} //將簇中的節點從有序表N中刪除

11.ifNis not nul Go to step4; //重復上述步驟4，直到選擇出所有的備用錨節點

12.whilevanchor∈M//遍歷M中所有的備用錨節點

{

//根據剩余能量和轉發組數，與移動路徑距離，計算備用錨節點的權值

16.ifη(vanchor)≤0 //當且僅當錨節點的能量耗盡

17.then remove thevanchor

//能量耗盡的錨節點所在簇中的節點，會在下一次數據采集時重新規劃分簇。

18.else anchor←vanchor//符合條件的即為最后的錨節點

}

19.output all anchor

20.end

4 仿真環境設計及性能評估

本節通過模擬來評估提出的HLSA算法的性能[14]。仿真利用NS-2進行。模擬時，在60 m×100 m場中隨機分布300個傳感器，其中橫向分布的傳感器節點為60～240。另外，每個傳感器的傳輸范圍R設定為2 m，L設定為1.5 m(L是錨節點和移動匯聚節點的最大距離)。另外，傳感器的剩余能量隨機設定為40～100。

將WRP與HLSA算法在網絡壽命方面進行了比較[15]。在WRP中，為了確定錨節點，v中需要轉發的數據包的數量用于網絡中每個傳感器v的轉發負載，假設平均100個數據。

圖2為移動接收器收集數據時網絡壽命方面的仿真結果。很明顯，HLSA算法具有比WRP更高的網絡壽命。這是因為HLSA算法在確定錨節點時，會考慮到錨節點的位置和感知節點的剩余能量。

實驗仿真參數設置基于IEEE 802.15.4標準，模擬時的參數見表1。對HLSA算法和WRP算法進行了網絡壽命的比較，評估性能的指標為生命周期和節點數量。觀察不同數量節點的生命周期是否存在優勢。

表1 參數設置

圖2 仿真結果比較

從圖2中可以看出，當節點設置為60時，HLSA算法的生命周期優勢最大，每個節點的生命周期差距可以達到4 000 s。隨著節點分布數量增加(可認為倉庫的面積增大)，節點的生命周期優勢逐步減小。考慮到節點分布密度，高達60節點橫向距離的倉庫面積是目前的主流倉庫面積，所以可以得出結論，在一般的物流中轉站中，數據采集算法采用啟發式-列表算法的優勢更大。

5 結束語

研究了錨節點的選擇，使得移動匯聚節點到錨節點的距離最短，以此來降低數據傳輸的能量消耗。考慮到傳感器節點的數據聚集和工作中節點能量不平衡的問題，以及經常被忽略的空間問題，提出了HLSA算法，在數據聚合和傳感器初始能量不平衡的同時延長了數據采集中節點的網絡壽命。仿真結果表明，HLSA比WRP算法提供了更長的網絡壽命。