傳感器網絡中數據時新性移動設備的調度*

王 田 ，成 培

（1.華僑大學 計算機科學與技術學院，福建 廈門 361021；2.香港城市大學 深圳研究院，廣東 深圳 518057）

近幾年來，國內外傳感器的硬件技術、數字芯片技術以及無線通信技術的飛速發展使得應用大規模無線傳感器網絡 WSN（Wireless Sensor Network）成為可能[1-2]。世界主要國家都在積極地研究無線傳感器網絡的熱點技術，特別是最近興起的物聯網，更是把無線傳感器網絡的應用推向高潮，無線傳感器網絡已經應用或即將應用到人們工作和生活的方方面面。

在傳統無線傳感器網絡的應用中，傳感器節點采集數據，然后通過節點之間的多跳無線傳輸，最終建立路由把采集的數據傳輸到基站（sink）進行處理。這樣的傳輸方式類似于傳統因特網的路由，但是無線通信不同于因特網的有線通信，這樣帶來的最大問題是，普通傳感器節點需要消耗大量的能量，因為每個傳感器節點都要幫助別的節點轉發數據，尤其是靠近基站的節點，一般都是最先耗盡能量的。而另一方面，傳感器節點通常一經部署，需要連續工作幾個月甚至幾年，能量的過快消耗將導致傳感器網絡的癱瘓。因此，傳感器網絡研究的一個熱點方向就是如何高效地收集數據。近年來，為了節省傳感器網絡中的能量消耗，部分研究者將移動設備引入到網絡中來[3-4]。例如，參考文獻[5]用移動數據收集器來收集數據，因為移動設備的能量比傳感器節點充足，并且由于可以移動，它們可以移動到可以補充能量的地方。通過移動設備的輔助，可以大大地減少普通傳感器節點的能量，從而延長網絡生存時間。

在某些應用中，收集的數據必須在限定時間內送到基站以保證數據的時新性。例如，對于森林溫度的監測，sink可以要求各傳感器節點在20 min內將采集的溫度數據傳送一次，以連續不斷地完成對溫度的監測[2]。本文把該最大數據延遲時間（Maximum Latency Requirements）稱為傳輸時間約束，其取決于具體實際應用對數據敏感性的需求程度。本文著重研究移動設備ME（Mobile Element）的路徑規劃問題，即如何規劃ME的移動路徑，使得收集數據在滿足時間約束的前提下，傳感器網絡中節點的能量消耗得最少。

1 移動設備調度問題

本文研究的問題可描述如下：在一個傳感器網絡中，已知有一組數據采集節點的物理位置和數據傳輸的時間約束。ME可以在任意2個節點之間自由地勻速直線移動，本文假設ME的能量相對于傳感器節點的能量是無窮的，因為ME可以移動到可以充電的地點。顯然，傳輸時間約束可轉化為ME移動路徑的長度約束。問題的目標是規劃1個ME的路徑，使得每個ME從sink節點出發，依次訪問傳感器節點收集數據，最后回到sink節點，所有節點的數據都應滿足規定的傳輸時間約束，而目標是ME移動的路徑總長度 （即數據傳輸時間）最小化。本文將該問題稱為數據敏感性環境下的移動設備調 度 問 題DFMES （Data FreshnessMobile Elements Scheduling）。

DFMES問題的形式化定義如下：n個傳感器節點的集合為 V={v1，…，vn}，每個節點的物理位置（x，y）已知。基站節點vs∈V。ME的移動路徑可看作是1個全連通圖G=，其中，E=V×V。 d（u，v）表示頂點 u，v∈V 之間的直線距離。移動設備的移動路徑可以表示為一系列節點的有序序列，即從某一節點開始，依次訪問后續節點，如移動路徑 T=。移動路徑的總長度可表示為：

每個頂點v∈V的時間約束記為pv，表示ME連續訪問該頂點所允許的最大時間間隔。節點的時間約束集合為 P=，Pmax=max{Pv：v∈V}表示最大的時間約束。 假設 v∈V 滿足 pv≥2d（vs，v），否則所述問題不存在一個可行的解決方案。

DFMES問題的目標是找到一個路徑集合，滿足4點：（1）sink節點 vs是所有路徑的起止節點；（2）每個頂點（除sink節點）屬于且僅屬于一條路徑；（3）如果某條路徑包括頂點v，則該路徑數據收集時間（或路徑長度）小于 pv；（4）所有路徑長度總和最小化。

2 算法描述

本文提出兩種算法來解決DFMES問題。第一種方法適應于實時性要求相對較低的應用，即基于貨郎擔問題的解法，將原問題分割成較小集合，然后逐步求解小問題。第二種適應于數據敏感性要求較高的應用，以貪婪式算法逐步建立移動設備的移動路徑，即從sink開始迭代選擇代價值最小的節點，直到不能再添加節點進移動路徑中。本文將前者簡稱為TR式（Tour Reduction）算法，后者簡稱為 TE（Tour Expand）式算法。

2.1 TR算法

TR啟發式算法始于一個簡單的包含所有節點的TSP路徑（本文使用 Christofides算法[6]來計算初始 TSP路徑），然后遞歸得出子路徑，過程描述如下（其中T代表初始TSP路徑解集，t表示當前子路徑）：

（1）若初始構造的移動路徑T滿足所有節點的時間約束，則算法結束，T即為輸出的移動路徑。

（2）從 T中選擇pv值最小 （即時間最為敏感的約束）的節點 v，t←。

（3）在 T 中選取滿足或的節點 v：判斷路徑或者的長度滿足節點 v 與 t中所有節點的約束條件，則 t←or。 當 t中任一方向的鄰居v都滿足約束條件時，選擇時間敏感性要求較低的節點加入t。

（4）重復步驟（3），直到沒有節點可以移入 t。

（5）即最終解中的一條子路徑， 從 T 中刪除t內的所有節點，對T剩下的部分遞歸地執行該算法。

2.2 TE算法

TE算法是一種啟發式的貪婪算法。本文定義1個代價函數c（vi，T）。代價函數用來度量節點在路徑中的權重，每一輪迭代都選取代價 c（vi，T）值最低的節點嘗試添加至子路徑中，并判斷是否違反約束條件，直到現有路徑無法再擴展，再從sink節點開始重新生成新的子路徑。代價值取決于節點的時間約束與其距當前路徑的距離。節點v與當前路徑的距離 d（v，T）定義為節點 v與當前路徑T中最近節點間的距離。節點vi的代價函數為：

其中，pmax代表最大時間約束，dmax代表網絡中距離最遠的兩節點間的距離。

每次都選取當前根據式（2）計算出的最小代價vi，添加到ME的移動路徑中，然后對剩余節點重新計算代價函數，再選出新的節點vi，直到當前的ME不能再添加任何節點進去，再添加1個新的ME，重復以上過程，直到所有的節點都被包含進來，這是貪心算法的主要內容。

3 分析與討論

TR算法是基于一條完整的初始TSP路徑，然后逐步選取節點生成子路徑，并使得所有子路徑集滿足條件約束。由于該算法是對原始路徑進行修改而得來的，因此計算出的子路徑保留了原始TSP解集的大部分結構，對初始TSP路徑的依賴較大，在最終解路徑數量相對較少的情況下，能最大程度利用初始路徑，算法性能較好，適合于數據敏感性要求較低的環境中。而TE算法是以貪婪的方式建立全新的移動路徑，逐步添加節點，該算法適合于數據敏感性要求較高的環境中，本文將會以模擬實驗來進行進一步的對比分析。

從兩種算法的時間復雜度看，TR啟發式算法的復雜度主要取決于構造初始TSP所需要的時間，例如，當使用Christofides算法[6]構造最初TSP解時，如時間復雜度為 O（n3），則最終的時間復雜度為 O（n3）。 而 TE啟發式算法中，每次迭代都需重新計算代價函數，判斷節點能否添加到路徑中耗時O（n），總的時間復雜度為O（n2）。因此，一般來說TE算法的運算速度要快于 TR算法。

4 模擬研究

為了證明本文所提算法的性能，用C++編程來實現對兩種算法的模擬，并與已有算法進行對比。在模擬場景中，300個傳感器節點隨機部署在400 m×400 m的矩形區域中。節點的時間約束在一個[L，H]的范圍中隨機取值。

本文主要用兩個指標來衡量算法的性能：（1）算法生成的子路徑條數，即所需ME個數；（2）路徑的總長度（總數據收集時間）。第1個指標反映了移動設備收集數據所需要的成本，不難理解，完成同樣的功能，所需要的ME個數越少，則成本越低。而第2個指標反映了ME移動路徑的優良與否，移動總路徑越短，說明ME的移動路線規劃得越好，即能夠用較短的移動路線收集到所有的數據。

為了說明所提算法的性能，本文將提出的算法與VRPTW （Vehicle Routing Problem With Time Windows）問題的算法[5，7]（本文簡稱為 VR1算法與 VR2算法）進行比較。在VR1算法與VR2算法中，ME必須在每個節點預定的時間范圍內訪問并收集數據，當第一個訪問節點確定后，算法反復添加最優節點至路徑并且滿足時間窗約束。VR1算法與VR2算法的區別在于它們添加節點至路徑的標準不同：VR1算法考慮引入節點對當前部分路徑的影響，而VR2算法考慮能最小化當前路徑總時間的節點加入路徑中。

圖1所示為4種算法在不同的時間約束條件下移動設備的數目變化情況。從圖1可以看出，當約束時間增大時，即對數據傳送的敏感性要求較低時，4種算法的趨勢都是一致的，即隨著約束時間的增大其所需要的移動設備數量下降。這是因為，單個移動設備可以有更多的時間去完成數據的收集，從而可以不需要那么多的移動設備就可以完成預定的任務。此外，從圖1可以看出，TR和TE算法都比VR1和VR2好，在最好的情況下，完成同樣的數據收集，本文提出的算法可以只需要近1/3的ME，這充分說明了本文提出算法的有效性。

圖1 時間約束值對移動設備數目的影響

圖2所示為4種算法分別在不同的時間約束條件下數據收集的總時間的情況。與上面的分析類似，不難理解，數據收集的總時間隨著時間約束的放松而呈下降趨勢。從圖2也可以看出，TE算法的性能比其他算法要優，因為TE算法在代價函數中考慮了傳輸約束和節點之間的距離，并且平衡了兩者的影響。相對于其他3種算法，在最好情況下能提升約3倍的性能。而TR算法雖然在開始的時候不及VR2和VR1，但是隨著時間約束值的放松，性能越來越好，說明TR算法比較適合于對數據敏感性要求不太高的應用中。

圖2 時間約束值對總數據收集時間的影響

為了最大程度地節省傳感器節點的能量，從而能夠滿足傳感器網絡對時間敏感性數據的收集，本文引入移動基站來收集數據，并主要提出了兩種啟發式算法，其一是基于貨郎擔問題的解法，將原問題分割成較小集合，然后逐步求解小問題，該算法適用于數據敏感性要求相對較低的應用；而當數據敏感性要求較高時，提出的貪婪式算法逐步建立移動設備的移動路徑，即從sink開始迭代選擇代價值最小的節點，直到不能再添加節點進移動路徑中。理論分析和模擬結果表明，與已有算法相比，本文提出的算法可以減少數據收集過程中所需的移動設備的數量，而且大大節省了數據收集的總時間，從而可以應用在大規模網絡中。

在未來的工作中，將進一步考慮數據融合的場景。數據融合可以將多份數據融合為一份數據，因此，傳感器節點可以預先進行小范圍的協商，從而選舉部分節點作為數據融合匯集點，其他的節點將采集的數據發送給該匯集點，而移動基站則只需要訪問這些選定的匯集點，從而可以更加節省移動所需要的總長度，從而能夠更快、更節省地幫助傳感器網絡收集數據。此外，在大規模的傳感器網絡環境下，往往會采用多個sink協同處理、收集數據，因此，考慮多個sink存在的場景，也是另外一個值得研究的方向。

[1]任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14（7）：1282-1291.

[2]Wang Tian， Wang Guojun， Guo Minyi， et al.Hash-areabased data dissemination protocol in wireless sensor networks[J].Journal of Central South University of Technology，2008， 15（3）： 392-398.

[3] HAMIDA E B， CHELIUS G. Strategies for data dissemination to mobile sinks in wireless sensor networks[J].IEEE Wireless Communications， 2008，15（6）：31-37.

[4]MARTA M，CARDEI M.Improved sensor network lifetime with multiple mobile sinks [J].Pervasive and Mobile Computing， 2009， 5（6）：542–555.

[5]XING G， WANG T， XIE Z， et al.Rendezvous planning in wireless sensor networks with mobile elements[J].IEEE Transactions on Mobile Computing， 2008， 7（12）： 1430-1443.

[6]CHRISTOFIDES N.Worst-case analysis of a new heuristic for the traveling salesman problem[C].Graduate School of Industrial Administration， Carnegie-Mellon University，Technical Report 388，1976.

[7]ALMI′ANIK， SELVADURAIS， VIGLASA.Periodic mobile multi gateway scheduling[C].Ninth International Conference on Parallel and Distributed Computing，Applications and Technologies （PDCAT）， New Zealand，2008：195-202.