基于全局時延最小化的移動Sink數(shù)據(jù)收集算法*

常　捷，張　靈，曾　碧

（廣東工業(yè)大學(xué)計算機(jī)學(xué)院，廣州510006）

?

基于全局時延最小化的移動Sink數(shù)據(jù)收集算法*

常捷，張靈*，曾碧

（廣東工業(yè)大學(xué)計算機(jī)學(xué)院，廣州510006）

摘要：針對Sink節(jié)點(diǎn)移動所帶來的時延問題，提出了一種基于最優(yōu)路徑的移動Sink數(shù)據(jù)收集方案OPDG（Data Gathering Based on Optimal-Path）。首先由MWHA（Minimum Weighted Heuristic Algorithm）算法得到匯聚節(jié)點(diǎn)RP（Rendezvous Point）的集合，然后根據(jù)這些RP節(jié)點(diǎn)求出移動Sink的最佳駐留點(diǎn)集合，最后求出經(jīng)過駐留點(diǎn)的最短路徑。Sink沿著這條路徑周期性采集數(shù)據(jù)。通過NS-2中大量的仿真實驗結(jié)果表明，與已有算法相比，OPDG算法能最大限度的減小時延，延長網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；時延；移動Sink；匯聚節(jié)點(diǎn)

無線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Net?work）由大量微型的且能量受限的傳感器節(jié)點(diǎn)組成。其中數(shù)據(jù)收集是WSN的主要應(yīng)用之一，傳感器節(jié)點(diǎn)通過逐跳通信的方式將感知的數(shù)據(jù)傳送給Sink或基站。早期的研究工作側(cè)重于靜態(tài)網(wǎng)絡(luò)［1］，容易使Sink周圍的節(jié)點(diǎn)因過多的轉(zhuǎn)發(fā)數(shù)據(jù)而很快死亡，從而造成“網(wǎng)絡(luò)分割”，產(chǎn)生能量空洞［2］，使網(wǎng)絡(luò)壽命大大降低。

因此很多研究者引入移動Sink來解決上述問題，相比靜態(tài)網(wǎng)絡(luò)，用移動Sink充當(dāng)數(shù)據(jù)收集器［3-4］可以有效的解決能量空洞問題，緩解節(jié)點(diǎn)負(fù)載不均問題，而且，Sink的移動性還能減少節(jié)點(diǎn)將數(shù)據(jù)傳輸給Sink所需要的跳數(shù)，從而減少節(jié)點(diǎn)的能耗，延長網(wǎng)絡(luò)壽命［5-6］。然而移動Sink的路徑選擇直接影響數(shù)據(jù)的收集效率以及網(wǎng)絡(luò)的整體性能。Zhangc?hun［7］等采用一種自組織分簇算法選取合適的簇頭作為數(shù)據(jù)收集點(diǎn)，可有效降低網(wǎng)絡(luò)能耗。文獻(xiàn)［8-9］提出時延受限時移動Sink的數(shù)據(jù)收集算法。文獻(xiàn)［10］提出一種優(yōu)化網(wǎng)絡(luò)生存時間的Sink節(jié)點(diǎn)移動路徑選擇算法MPSA，通過將監(jiān)測區(qū)域分成大小一致的網(wǎng)格來收集單跳范圍內(nèi)的傳感器數(shù)據(jù)。文獻(xiàn)［11］以滿足時延要求和最小化網(wǎng)絡(luò)能耗為目標(biāo)，提出了一種基于虛擬點(diǎn)優(yōu)先級的移動Sink路徑優(yōu)化方法，在算法中由網(wǎng)格方法劃分虛擬點(diǎn)用TSP算法求解最短路徑后由Sink沿著此路徑收集傳感器節(jié)點(diǎn)的數(shù)據(jù)。文獻(xiàn)［12］提出一種基于可移動Sink的數(shù)據(jù)采集方案DCSR，通過確定采集點(diǎn)，再由量子遺傳算法求解最短回路的方法來收集數(shù)據(jù)。文獻(xiàn)［13］采用分布式思想與網(wǎng)絡(luò)的局部信息選擇最優(yōu)路徑，實現(xiàn)了網(wǎng)絡(luò)能耗與傳輸時延之間的折中。文獻(xiàn)［14］提出一種基于旅行商問題的匯聚節(jié)點(diǎn)選擇算法。文獻(xiàn)［15］提出一種Sink移動速度控制算法，在節(jié)點(diǎn)稀疏的區(qū)域增大移動速度在節(jié)點(diǎn)稠密的區(qū)域減小移動速度，提高了數(shù)據(jù)采集效率。

本文針對時延受限的無線傳感器網(wǎng)絡(luò)，提出了基于最優(yōu)路徑的數(shù)據(jù)收集方案OPDG（Data Gather?ing Based Optimal-Path）。主要包含兩個階段：第一階段，由網(wǎng)絡(luò)中節(jié)點(diǎn)的部署情況選出一系列RP節(jié)點(diǎn)。第二個階段，在RP節(jié)點(diǎn)的基礎(chǔ)上進(jìn)一步找到Sink的最佳駐留點(diǎn)集合，再找到經(jīng)過這些點(diǎn)的最短路徑，使移動Sink沿著該路徑收集數(shù)據(jù)。

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

假設(shè)傳感器節(jié)點(diǎn)以隨機(jī)的方式部署到一個L×L的矩形監(jiān)測區(qū)域內(nèi)，形成一個多跳自組織網(wǎng)絡(luò)，其中①網(wǎng)絡(luò)是全連通的，且其中所有的節(jié)點(diǎn)有唯一的ID（0，…，n-1）號標(biāo)識，且部署后就不再移動。②每一個節(jié)點(diǎn)具有相同的通信半徑R。③每一個節(jié)點(diǎn)具有相同的初始能量E，但Sink的能量不受限制。④每一個節(jié)點(diǎn)可以獲得自己的地理位置信息（例如采用GPS或節(jié)點(diǎn)定位算法獲得）。⑤Sink RP節(jié)點(diǎn)具有移動性，且移動方式可控，以恒定的速度V移動。

本文用簡單的能耗模型，假設(shè)網(wǎng)絡(luò)中每個節(jié)點(diǎn)采用固定的發(fā)射功率和接收功率。當(dāng)Sink移動到終點(diǎn)并返回到起點(diǎn)時，稱其完成一“輪”移動。et表示發(fā)送單位數(shù)據(jù)的能耗，er表示接收單位數(shù)據(jù)的能耗。則在每一輪中的能耗表示如下式：

其中，hi表示節(jié)點(diǎn)i將數(shù)據(jù)發(fā)送到所屬RP節(jié)點(diǎn)的最小跳數(shù)，且如果當(dāng)前節(jié)點(diǎn)i即為RP節(jié)點(diǎn)，則hi=0。則將網(wǎng)絡(luò)的單輪總能耗用最小跳數(shù)的形式表示如下：

從式（3）可知整個網(wǎng)絡(luò)的能耗最小化問題相當(dāng)于所有節(jié)點(diǎn)到其所屬的RP節(jié)點(diǎn)的跳數(shù)之和的最小化，因此RP節(jié)點(diǎn)的選擇至關(guān)重要。

2　匯聚節(jié)點(diǎn)

訪問每個傳感器節(jié)點(diǎn)會增加移動Sink的路徑長度，這樣將導(dǎo)致數(shù)據(jù)收集時延的增加。因此提出建立匯聚點(diǎn)的模型，靜態(tài)傳感器節(jié)點(diǎn)將數(shù)據(jù)發(fā)送到RP節(jié)點(diǎn)，移動Sink只需訪問一系列的匯聚點(diǎn)即可。為了減輕下個階段最短路徑的計算量，RP節(jié)點(diǎn)集的建立應(yīng)盡可能少量且能覆蓋整個網(wǎng)絡(luò)。

2.1問題描述

給定一個全連通網(wǎng)絡(luò)G=（L，A），每條邊aij∈A有一個非負(fù)代價eij，且eij相當(dāng)于節(jié)點(diǎn)si與sj之間距離的代價，則最短路徑數(shù)據(jù)收集問題可以定義為一個混合的線性規(guī)劃問題：

目標(biāo)函數(shù)

最小值

約束條件

該模型中定義的決策變量如下：

上面的公式中，目標(biāo)函數(shù)（4）是指數(shù)據(jù)收集路徑上的最小值。xij是用來表示邊aij（從si到sj）是否在最優(yōu)路徑上的一個變量，變量Ii表明RP節(jié)點(diǎn)ci是否在最優(yōu)路徑上。限制條件（5）和（6）確保路徑上的每個節(jié)點(diǎn)必須有一條指向它的邊和另一條遠(yuǎn)離它的邊。公式（7）強(qiáng)調(diào)了每個傳感器節(jié)點(diǎn)必須在至少一個屬于收集路徑上的RP節(jié)點(diǎn)的鄰居集合內(nèi)，這樣移動Sink可以收集到全網(wǎng)范圍內(nèi)的傳感器節(jié)點(diǎn)的信息。由此可看出與TSP（Traveling Sales?man Problem）相似是一個NP-hard問題。因此提出一個啟發(fā)式算法來解決這個問題。

2.2算法實現(xiàn)

由上節(jié)中的模型可知，選取RP節(jié)點(diǎn)時應(yīng)盡量減少普通節(jié)點(diǎn)到RP節(jié)點(diǎn)的傳輸跳數(shù)。傳感器節(jié)點(diǎn)的鄰居集合應(yīng)該包含在該節(jié)點(diǎn)一跳范圍內(nèi)的所有節(jié)點(diǎn)。這樣我們可以得到全網(wǎng)范圍內(nèi)所有傳感器節(jié)點(diǎn)的位置信息，以及每個節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)，且每個節(jié)點(diǎn)會定時發(fā)消息來維護(hù)自己的鄰居表，每個傳感器節(jié)點(diǎn)也可以通過廣播來發(fā)現(xiàn)一跳范圍內(nèi)的鄰居節(jié)點(diǎn)。因此，每個節(jié)點(diǎn)都可能是候選的RP節(jié)點(diǎn)。

我們舉例說明鄰居集合，RP節(jié)點(diǎn)的定義，在圖1（a）中，其中s1，s2，s3，s44個節(jié)點(diǎn)，它們都可能成為RP節(jié)點(diǎn)，si∈{s1，s2，s3，s4}，候選的RP節(jié)點(diǎn)集C={s1，s2，s3，s4}。s1的鄰居集合為{s1，s2，s3，s4}，s4的鄰居集合為{s4，s1}，s2和s3的鄰居集合為{s1，s2，s3}。

圖2基于最小權(quán)值的啟發(fā)算法MWHA（Mini?mum Weighted Heuristic Algorithm）由迭代執(zhí)行來選出RP節(jié)點(diǎn)，從而選取最短路徑，簡稱MWHA算法。在該算法中，當(dāng)某個節(jié)點(diǎn)被選作RP節(jié)點(diǎn)時它的鄰居節(jié)點(diǎn)也會被覆蓋。該算法盡量用最小的代價覆蓋每一個未被覆蓋的節(jié)點(diǎn)的鄰居集合。其中權(quán)值α定義為覆蓋S中每個未被覆蓋的節(jié)點(diǎn)的平均代價。計算每個候選RP節(jié)點(diǎn)的權(quán)重值，首先，定義一個空集C，C將包含所有的RP節(jié)點(diǎn)，U包含所有的傳感器節(jié)點(diǎn)。F是所有節(jié)點(diǎn)的鄰居集合的總集。兩個鄰居集合之間的距離被定義為兩個相關(guān)的RP節(jié)點(diǎn)的距離。cost{S}是未被覆蓋的鄰居集合S的代價相當(dāng)于S和任一覆蓋的鄰居集合之間的最短距離。

圖1　MWHA執(zhí)行示例

Create an empty set C

Create a set U containing all remaining sensors

Create the family set F of all neighbor sets

while U=Φ

Cover sensors in S

Add the corresponding polling point of S into C Remove sensors in S from U

end while

Find an approximate shortest tour on polling points in C

圖2 MWHA——基于最小權(quán)值的RP選擇算法

3　OPDG算法

交付時延即為移動Sink節(jié)點(diǎn)在整個路徑上消耗的時間。因而Sink的訪問路徑越長，相應(yīng)的時延也就越大。受Sink移動速率的限制，移動Sink由求出的TSP路徑依次遍歷網(wǎng)絡(luò)區(qū)域內(nèi)所有的匯聚節(jié)點(diǎn)，移動的距離較長，需要的時間也較長，且Sink移動得越頻繁，網(wǎng)絡(luò)的穩(wěn)定性就越差。為進(jìn)一步縮短Sink的移動路徑，降低數(shù)據(jù)交付時延。提出了基于最優(yōu)路徑的數(shù)據(jù)收集算法。

3.1問題模型

傳感器節(jié)點(diǎn)隨機(jī)部署在網(wǎng)絡(luò)中，RP節(jié)點(diǎn)存在集合C中，由圖3可知，移動Sink s0的路徑由一系列連接的線段組成。要使移動Sink的移動路徑最短，即讓所有的線段之和達(dá)到最小值。即

其中l(wèi)（ci，cj）代表RP節(jié)點(diǎn)ci和cj之間的距離。

交付時延即為Sink節(jié)點(diǎn)在整個路徑上消耗的時間與在每個駐留點(diǎn)的停留時間之和。可以線性表示為：

其中V是移動Sink節(jié)點(diǎn)s0的移動速度，tk代表移動節(jié)點(diǎn)在駐留點(diǎn)k處所停留的時間，A表示Sink所有的停留位置集合。要使交付時延Tmin取得最小值，一方面要使移動節(jié)點(diǎn)的移動路徑Lmin最短，另一方面應(yīng)盡量減少移動節(jié)點(diǎn)的訪問停留點(diǎn)。

3.2路徑優(yōu)化算法實現(xiàn)

步驟①：求出TSP路徑

由上節(jié)中得到的RP節(jié)點(diǎn)集合C求出移動Sink的一條TSP路徑ρ=（s0，c1，…，ck，s0）如圖3所示的TSP路徑為ρTSP=（s0，c1，c2，c3，c4，c5，c6，c7，s0）。

圖3　TSP路徑

步驟②：選擇駐留點(diǎn)AP（Access Point）

若要使節(jié)點(diǎn)s0的移動路徑更短，AP個數(shù)更少，移動Sink的訪問停留點(diǎn)應(yīng)該在傳感器節(jié)點(diǎn)通信范圍的相交點(diǎn)。

首先由求出的TSP路徑結(jié)合C中的匯聚節(jié)點(diǎn)找到在匯聚節(jié)點(diǎn)通信范圍邊界上的合適的駐留點(diǎn)AP（Access Point）并將其加入到集合A中。如圖4所示，假設(shè)路徑ρ=（s0，t1，b0，a0，t2，t3，a6，a7，s0）為當(dāng)前最短路徑。其中a0在節(jié)點(diǎn)的通信范圍之外，b0在節(jié)點(diǎn)的通信范圍之內(nèi)，其他訪問停留點(diǎn)均在節(jié)點(diǎn)通信范圍的邊界上。l（t1，b0′）＜I（t1，b0）+I（b0，b0′），訪問點(diǎn)b0使移動路徑變長，同理，l（t2，a0）＜I（t2，a0′）+I（a0，a0′），a0也使移動路徑變長。我們可以通過讓線段t0b0′代替t1，b0和b0，b0′，t2，a0′代替a0，a0′和t2，a0來使Sink的移動路徑變得更短。因此，每個駐留點(diǎn)必須在節(jié)點(diǎn)通信范圍的邊界上。否則我們總能找到能使路徑變短的更適合的點(diǎn)來代替它們。

其次，為了通過減少駐留點(diǎn)的個數(shù)來降低時延，判斷如果匯聚節(jié)點(diǎn)ci和cj相交，則相交點(diǎn)成為新的AP。如圖3中c1和c2相交，交點(diǎn)為t1，t1同時在RP節(jié)點(diǎn)c1和c2通信范圍的邊界上。因此s0停留在t1處能夠同時接收到c1和c2的數(shù)據(jù)，這樣減少了移動Sink的駐留點(diǎn)個數(shù)，從而減小了系統(tǒng)的交付時延。當(dāng)前的AP集合為S={t1，t2，t3，a6，a7}，即得到最佳駐留點(diǎn)集合后的路徑ρAP=（s0，t1，t2，t3，a6，a7，s0）。

圖4　步驟2得到的路徑

步驟③：線段組合優(yōu)化

這種線段組合方法必須滿足兩個條件，一個就是兩條相鄰邊的長度之和必須大于它們的歐氏距離，另一個就是要保證線段組合后所有的匯聚點(diǎn)仍然可以被訪問。

如圖5所示，t1是RP節(jié)點(diǎn)c1和c2的交叉點(diǎn)，由三角形定理可知d（t3，a6）+d（a6，a7）＞d（t3，a7），d0代表訪問停留點(diǎn)t3與a7之間的距離，d1代表RP節(jié)點(diǎn)c6到線段t3a7之間的距離，R是節(jié)點(diǎn)的通信半徑。假設(shè)t3的坐標(biāo)為（x1，y1），a7的坐標(biāo)為（x2，y2），c6的坐標(biāo)為（x3，y3），則該線段的斜率是k=（y2-y1）/（x2-x1），方程為y-k（x-x1）-y1=0。由此可知

圖5　最優(yōu)路徑

如果d1＜R，即Sink節(jié)點(diǎn)的移動路徑經(jīng)過c6的通信范圍。故移動節(jié)點(diǎn)s0到此節(jié)點(diǎn)通信范圍時仍可以直接接收c6節(jié)點(diǎn)的數(shù)據(jù)（即移動路徑變短，收集的數(shù)據(jù)沒變），也就保證了線段組合后所有的RP節(jié)點(diǎn)仍可以被訪問。很顯然，通過沿ρbest=（s0，t1，t2，t3，a7）這條最短路徑移動，可以在最短的時間內(nèi)獲得時延最小的數(shù)據(jù)。

OPDG算法如下：

Create an empty set A

diis the distance between ciand line ai-1ai+1

While C≠ΦChoose a point aion the communication bound of ciAdd the access point aiinto AIf（ciand cjhave intersection point ti）{Add tiinto A instead of aiand aj

}

End while

While A≠ΦIf（（d（ai-1，ai+1）＜d（ai-1，ai，）+d（ai，ai+1））&&（di＜R））{Remove aifrom A

}

End while

Find a shortest tour ρbeston access points in A

3.3停留時間分配

在一個采集周期中，每個匯聚節(jié)點(diǎn)發(fā)送的最大數(shù)據(jù)量是固定的，因此，在一定的網(wǎng)絡(luò)生存時間內(nèi)，可以根據(jù)在駐留點(diǎn)處Sink通信范圍內(nèi)各個匯聚節(jié)點(diǎn)的緩存數(shù)據(jù)量之和來改變停留時間。令Sink的最大移動速率為v，每個節(jié)點(diǎn)的數(shù)據(jù)發(fā)送速率為vg，則每一輪移動的總時間為Lmin/v，各訪問點(diǎn)的停頓時間以及總停頓時間在如式（11）、式（12）所示：

其中，ak表示第k個訪問點(diǎn)與Sink通信的匯聚節(jié)點(diǎn)的個數(shù)，qkj表示第k個訪問點(diǎn)的第j個匯聚節(jié)點(diǎn)當(dāng)前緩存的數(shù)據(jù)量，A表示Sink停留位置的集合，|C|表示集合C中匯聚節(jié)點(diǎn)的總數(shù)量。

4　仿真結(jié)果與性能分析

本文采用NS2仿真平臺，對所提的時延受限的傳感器網(wǎng)絡(luò)移動Sink數(shù)據(jù)收集算法進(jìn)行性能分析。實驗中，我們假設(shè)節(jié)點(diǎn)隨機(jī)分布在1 000 m× 1 000 m的網(wǎng)絡(luò)區(qū)域中，且移動Sink的移動速度設(shè)為50 m/s，平臺中節(jié)點(diǎn)的默認(rèn)通信半徑為200 m，而算法中駐留點(diǎn)的選取與節(jié)點(diǎn)的通信范圍有關(guān)，因此，為了驗證OPDG算法的良好性能，將本文中的OPDG算法與DCSR［12］算法進(jìn)行比較，它也是一種利用移動Sink節(jié)點(diǎn)進(jìn)行收集數(shù)據(jù)的方法。對兩種算法所形成的路徑長度，網(wǎng)絡(luò)的時延以及生命周期加以統(tǒng)計比較。其中20個節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)如圖6所示。

圖6　拓?fù)浣Y(jié)構(gòu)

當(dāng)在比較稀疏的網(wǎng)絡(luò)中，且節(jié)點(diǎn)通信范圍較小時，可能會造成整個網(wǎng)絡(luò)不連通，這樣，無論哪種算法，移動Sink都需要訪問每個傳感器節(jié)點(diǎn)。我們計算了在節(jié)點(diǎn)的通信半徑分別為100 m和200 m，節(jié)點(diǎn)個數(shù)由20依次增加到60時，DCSR算法和OPDG算法各自的相對路徑長度，由圖7可知，一，當(dāng)節(jié)點(diǎn)個數(shù)相同時，節(jié)點(diǎn)的通信范圍越大，Sink節(jié)點(diǎn)移動的路徑長度就越短。二，任意的通信范圍，隨著節(jié)點(diǎn)個數(shù)的增加，移動Sink的路徑長度增長都趨于平緩。三，OPDG算法無論在何種情況下所求得的路徑長度均明顯少于DCSR算法。

圖7　路徑長度

交付時延指的是移動Sink完成一輪數(shù)據(jù)采集所消耗的時間。只有交付時延達(dá)到最小，每個數(shù)據(jù)包被上交給基站的時延才會最小。由圖8可知，節(jié)點(diǎn)個數(shù)越多，時延越大，但當(dāng)節(jié)點(diǎn)個數(shù)足夠多時趨于平穩(wěn)狀態(tài)。節(jié)點(diǎn)通信范圍越小，系統(tǒng)的整體時延也會相對增加。

圖9中，可以看出，隨著節(jié)點(diǎn)數(shù)目的增加，兩種算法中網(wǎng)絡(luò)的生命周期（輪數(shù)）都隨之減小，且逐漸趨于平緩，然而OPDG算法的網(wǎng)絡(luò)生命周期明顯要長于DCSR算法。由圖（a）圖（b）比較可知，在相同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)中，節(jié)點(diǎn)的通信范圍越大，網(wǎng)絡(luò)的生命周期越長。因此，在同一網(wǎng)絡(luò)中，本文中的OPDG算法相比DCSR算法能更好的延長網(wǎng)絡(luò)的生命周期。

以上結(jié)果表明OPDG算法能很好的適用于節(jié)點(diǎn)通信范圍大的網(wǎng)絡(luò)中。在網(wǎng)絡(luò)中節(jié)點(diǎn)分布情況相同時，節(jié)點(diǎn)通信范圍越大，它能覆蓋的鄰居節(jié)點(diǎn)數(shù)越多，我們得到的駐留點(diǎn)數(shù)越少，相對來說，優(yōu)化所得的路徑將會更短，故而時延越小。綜上所述，OPDG算法能夠極好的減小移動Sink的路徑長度，從而最大限度的減小了系統(tǒng)的交付時延。

圖9　網(wǎng)絡(luò)生命周期

5　總結(jié)

本文為減小系統(tǒng)的交付時延，提出了一種基于最優(yōu)路徑的數(shù)據(jù)收集算法。先由MWHA算法求出匯聚節(jié)點(diǎn)集，在TSP算法的基礎(chǔ)上經(jīng)過優(yōu)化求出一系列最佳駐留點(diǎn)，通過線段優(yōu)化算法得到一條最短路徑，使移動Sink能夠盡快完成一個數(shù)據(jù)采集周期，從而減小時延。通過模擬平臺的實驗驗證了本文的OPDG算法能夠在最短路徑的條件下減小系統(tǒng)的交付時延，延長網(wǎng)絡(luò)的生命周期。下一步我們將考慮多個Sink移動的數(shù)據(jù)收集以及它們之間的協(xié)作通信問題。

參考文獻(xiàn)：

［1］Lung C H，Zhou C J.Using Hierarchical Agglomerative Clustering in Wireless Sensor Networks：An Energy-Efficient and Flexible Approach［J］.Ad Hoc Networks，2010，8（3）：328-344.

［2］Tang L，Jian P，Xiao F W et al.Research on the Energy Hole Prob?lem Based on Non-Uniform Node Distribution for Wireless Sensor Network［J］.Transactions on Internet and Information Systems，2012，6（9）：2017-2036.

［3］Yang Y，F(xiàn)onoage M I，Cardei M.Improving Network Lifetime with Mobile Wireless Sensor Networks［J］.Computer Communications，2010，33（4）：409-419.

［4］Zhang X W，Chen G H.Design of Mobile Sink Node for SDMA Applications in WSN［J］.Journal of Computer Research and De?velopment，2012，49（3）：541-549.

［5］惠曉威，劉彥每.WSN數(shù)據(jù)收集中移動Sink的路徑規(guī)劃和簇頭節(jié)點(diǎn)選取問題的綜合研究［J］.傳感技術(shù)學(xué)報，2014，27（1）：118-122.

［6］張蕾，張堃.無線傳感器網(wǎng)絡(luò)中一種基于移動Sink的數(shù)據(jù)收集算法［J］.傳感技術(shù)學(xué)報，2012，25（5）：673-677.

［7］Zhang Chun，F(xiàn)ei Shumin，Zhou Xingpeng.Energy Efficient Data Collection in Hierarchical Wireless Sensor Networks［J］.China Communications，2012，9（9）：79-88.

［8］Gao S，Zhang H，Das S K.Efficient Data Collection in Wireless Sensor Networks with Path-Constrained Mobile Sinks［J］.IEEE Transactions on Mobile Computing，2011，10（4）：592-608

［9］郜帥，張宏科.時延受限傳感器網(wǎng)絡(luò)移動Sink路徑選擇方法研究［J］.電子學(xué)報，2011，39（4）：742-747.

［10］王章權(quán)，陳友榮，尉理哲，等.優(yōu)化網(wǎng)絡(luò)生存時間的Sink節(jié)點(diǎn)移動路徑選擇算法［J］.傳感技術(shù)學(xué)報，2014，27（3）：409-415.

［11］張希偉，沈琳，蔣益峰，等.移動協(xié)助傳感器網(wǎng)絡(luò)中Sink的路徑優(yōu)化策略［J］.通信學(xué)報，2013，34（2）：85-93.［12］郭劍，孫力娟，許文君，等.基于移動Sink的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案［J］.通信學(xué)報，2012，33（9）：176-184.

［13］Somasundara A A，Kansal A，Jea D.Controllably Mobile Infra?structure for Low Energy Embedded Networks［J］.IEEE Transac?tions on Mobile Computing，2006，5（8）：958-973.

［14］Xing G L，Wang T，Jia W J，et al.Rendezvous Design Algorithms for Wireless Sensor Networks with a Mobile Base Station［C］//Proc of the ACM MobiHoc.Hongkong，China，2008，5317（6）：231-240.

［15］Bhadauria D，Tekdas O，Isler V.Robotic Data Mules for Collect?ing Data over Sparse Sensor Fields［J］.Journal of Field Robotics，2011，28（3）：388-404.

常　捷（1991-），女，河南人，廣東工業(yè)大學(xué)在讀碩士，主要研究方向為智能優(yōu)化算法研究與應(yīng)用，無線傳感網(wǎng)絡(luò)傳輸技術(shù)；

張　靈（1968-），女，廣西人，博士，廣東工業(yè)大學(xué)計算機(jī)學(xué)院教授。主要研究方向為智能優(yōu)化算法研究與應(yīng)用，無線傳感網(wǎng)絡(luò)傳輸技術(shù)，1252875930@qq.com。

Data Gathering Algorithm for Mobile Sink Based on the Global Delivery Latency Minimization*

CHANG Jie，ZHANG Ling*，ZENG Bi
（Faculty of Computer，Guangdong University of Technology，Guangzhou 510006，China）

Abstract：For the latency problem brought by the movement of Sink node，this paper presents a mobile Sink data gathering program based on optimal path（OPDG）.Firstly，a set of rendezvous points（RP）are obtained by MWHA （Minimum Weighted Heuristic Algorithm）algorithm.Then a best set of access points are selected according to the RP set.Finally，the shortest path is found across the access points.The mobile Sink will travel along this path peri?odically and collect data at each access point.Lots of simulation results show that compared with existing algorithm，OPDG algorithm can shorten the delivery latency and prolong the network lifetime.

Key words：wireless sensor networks；delivery latency；mobile Sink；rendezvous point

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.02.019

收稿日期：2015-08-13修改日期：2015-11-18

中圖分類號：TP393.01

文獻(xiàn)標(biāo)識碼：A

文章編號：1004-1699（2016）02-0264-07

項目來源：廣東省產(chǎn)學(xué)研合作專項項目(2014B090904080)；廣州市科技計劃項目(2014J4100228)