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

?！〗荩瑥垺§`，曾　碧

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

?

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

常捷，張靈*，曾碧

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

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

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

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

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

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

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

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

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

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

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

2　匯聚節(jié)點

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

2.1問題描述

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

目標函數(shù)

最小值

約束條件

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

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

2.2算法實現(xiàn)

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

我們舉例說明鄰居集合，RP節(jié)點的定義，在圖1（a）中，其中s1，s2，s3，s44個節(jié)點，它們都可能成為RP節(jié)點，si∈{s1，s2，s3，s4}，候選的RP節(jié)點集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é)點，從而選取最短路徑，簡稱MWHA算法。在該算法中，當某個節(jié)點被選作RP節(jié)點時它的鄰居節(jié)點也會被覆蓋。該算法盡量用最小的代價覆蓋每一個未被覆蓋的節(jié)點的鄰居集合。其中權(quán)值α定義為覆蓋S中每個未被覆蓋的節(jié)點的平均代價。計算每個候選RP節(jié)點的權(quán)重值，首先，定義一個空集C，C將包含所有的RP節(jié)點，U包含所有的傳感器節(jié)點。F是所有節(jié)點的鄰居集合的總集。兩個鄰居集合之間的距離被定義為兩個相關(guān)的RP節(jié)點的距離。cost{S}是未被覆蓋的鄰居集合S的代價相當于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é)點在整個路徑上消耗的時間。因而Sink的訪問路徑越長，相應(yīng)的時延也就越大。受Sink移動速率的限制，移動Sink由求出的TSP路徑依次遍歷網(wǎng)絡(luò)區(qū)域內(nèi)所有的匯聚節(jié)點，移動的距離較長，需要的時間也較長，且Sink移動得越頻繁，網(wǎng)絡(luò)的穩(wěn)定性就越差。為進一步縮短Sink的移動路徑，降低數(shù)據(jù)交付時延。提出了基于最優(yōu)路徑的數(shù)據(jù)收集算法。

3.1問題模型

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

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

交付時延即為Sink節(jié)點在整個路徑上消耗的時間與在每個駐留點的停留時間之和?？梢跃€性表示為：

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

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

步驟①：求出TSP路徑

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

圖3　TSP路徑

步驟②：選擇駐留點AP（Access Point）

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

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

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

圖4　步驟2得到的路徑

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

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

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

圖5　最優(yōu)路徑

如果d1＜R，即Sink節(jié)點的移動路徑經(jīng)過c6的通信范圍。故移動節(jié)點s0到此節(jié)點通信范圍時仍可以直接接收c6節(jié)點的數(shù)據(jù)（即移動路徑變短，收集的數(shù)據(jù)沒變），也就保證了線段組合后所有的RP節(jié)點仍可以被訪問。很顯然，通過沿ρ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é)點發(fā)送的最大數(shù)據(jù)量是固定的，因此，在一定的網(wǎng)絡(luò)生存時間內(nèi)，可以根據(jù)在駐留點處Sink通信范圍內(nèi)各個匯聚節(jié)點的緩存數(shù)據(jù)量之和來改變停留時間。令Sink的最大移動速率為v，每個節(jié)點的數(shù)據(jù)發(fā)送速率為vg，則每一輪移動的總時間為Lmin/v，各訪問點的停頓時間以及總停頓時間在如式（11）、式（12）所示：

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

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

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

圖6　拓撲結(jié)構(gòu)

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

圖7　路徑長度

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

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

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

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

5　總結(jié)

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

參考文獻：

［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é)點選取問題的綜合研究［J］.傳感技術(shù)學報，2014，27（1）：118-122.

［6］張蕾，張堃.無線傳感器網(wǎng)絡(luò)中一種基于移動Sink的數(shù)據(jù)收集算法［J］.傳感技術(shù)學報，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］.電子學報，2011，39（4）：742-747.

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

［11］張希偉，沈琳，蔣益峰，等.移動協(xié)助傳感器網(wǎng)絡(luò)中Sink的路徑優(yōu)化策略［J］.通信學報，2013，34（2）：85-93.［12］郭劍，孫力娟，許文君，等.基于移動Sink的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案［J］.通信學報，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è)大學在讀碩士，主要研究方向為智能優(yōu)化算法研究與應(yīng)用，無線傳感網(wǎng)絡(luò)傳輸技術(shù)；

張　靈（1968-），女，廣西人，博士，廣東工業(yè)大學計算機學院教授。主要研究方向為智能優(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

文獻標識碼：A

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

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