傳感器網(wǎng)絡(luò)中數(shù)據(jù)時(shí)新性移動(dòng)設(shè)備的調(diào)度*

王 田 ，成 培

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

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

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

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

1 移動(dòng)設(shè)備調(diào)度問(wèn)題

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

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

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

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

2 算法描述

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

2.1 TR算法

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

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

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

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

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

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

2.2 TE算法

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

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

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

3 分析與討論

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

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

4 模擬研究

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

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

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

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

圖1 時(shí)間約束值對(duì)移動(dòng)設(shè)備數(shù)目的影響

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

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

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

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

[1]任豐原，黃海寧，林闖.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，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.