王 田 ，成 培

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

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

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

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

1 移動設(shè)備調(diào)度問題

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

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

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

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

2 算法描述

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

2.1 TR算法

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

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

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

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

（4）重復步驟（3），直到?jīng)]有節(jié)點可以移入 t。

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

2.2 TE算法

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

其中，pmax代表最大時間約束，dmax代表網(wǎng)絡(luò)中距離最遠的兩節(jié)點間的距離。

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

3 分析與討論

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

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

4 模擬研究

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

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

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

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

圖1 時間約束值對移動設(shè)備數(shù)目的影響

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

圖2 時間約束值對總數(shù)據(jù)收集時間的影響

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

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

[1]任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)[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.