張希偉，沈琳，蔣益峰

（1.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 210098; 2.江蘇理工學(xué)院 電氣信息工程學(xué)院，江蘇 常州 213001）

1 引言

無線傳感器網(wǎng)絡(luò)（WSN, wireless sensor network）中存在能量空洞（energy hole）、冗余覆蓋（overlap）和熱點(diǎn)（hot spot）等問題[1～3]。盡管可以在基站周圍部署更多的節(jié)點(diǎn)輪流工作（即離基站近的區(qū)域節(jié)點(diǎn)密度較大）[3～6]，但無疑會(huì)增加網(wǎng)絡(luò)的成本和計(jì)算代價(jià)。

在無線傳感器網(wǎng)絡(luò)中引入了移動(dòng)性，即在Sink節(jié)點(diǎn)上配備移動(dòng)裝置可以有效地解決上述問題。通過基站的移動(dòng)，使負(fù)責(zé)向 Sink轉(zhuǎn)發(fā)的節(jié)點(diǎn)經(jīng)常變化，將網(wǎng)絡(luò)負(fù)載分擔(dān)到不同的節(jié)點(diǎn)上。利用移動(dòng)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)收集的一個(gè)典型是 Shah等提出的數(shù)據(jù)騾子（data mule）的模式[3]。近年來在煤礦、森林等傳感器網(wǎng)絡(luò)應(yīng)用中也出現(xiàn)了利用移動(dòng)節(jié)點(diǎn)來進(jìn)行數(shù)據(jù)收集的例子[7,8]。

移動(dòng)性帶來的一個(gè)問題是增加了數(shù)據(jù)的延時(shí)。由于移動(dòng)Sink的運(yùn)行速度有限（一般為1～2m/s），遠(yuǎn)遠(yuǎn)小于無線網(wǎng)絡(luò)傳輸?shù)乃俣?，因此，在選擇移動(dòng)Sink傳輸和無線傳輸中存在一個(gè)折中[9]。例如在圖1中，移動(dòng)Sink綜合考慮了能量和延時(shí)之間的關(guān)系，并不是訪問所有的靜態(tài)節(jié)點(diǎn)，而是只訪問數(shù)據(jù)匯聚點(diǎn)（CP, collection point）。靜態(tài)節(jié)點(diǎn)事先將數(shù)據(jù)發(fā)送到匯聚點(diǎn)，當(dāng)移動(dòng)Sink到來時(shí)再進(jìn)行轉(zhuǎn)發(fā)。文獻(xiàn)[10]提出了一種基于旅行商問題的匯聚點(diǎn)選擇算法，總是選擇那些能夠節(jié)約最大能量的位置作為匯聚點(diǎn)。文獻(xiàn)[11]在此基礎(chǔ)上提出了基于虛擬點(diǎn)優(yōu)先級的移動(dòng)Sink路徑優(yōu)化方法。同樣地，當(dāng)傳感器通信范圍內(nèi)存在多個(gè)移動(dòng) Sink時(shí)，需選擇一個(gè)合適的 Sink進(jìn)行數(shù)據(jù)傳輸[12]。

圖1 一個(gè)典型的利用移動(dòng)Sink收集數(shù)據(jù)的WSN應(yīng)用

本文主要研究移動(dòng)Sink的路徑優(yōu)化策略。通過分析移動(dòng)路徑和網(wǎng)絡(luò)能耗之間的制約關(guān)系，建立優(yōu)化模型。根據(jù)數(shù)據(jù)采集的不確定性，提出了一種基于訪問概率的匯聚節(jié)點(diǎn)選擇算法。移動(dòng)Sink按照一定的概率訪問匯聚節(jié)點(diǎn)，在滿足數(shù)據(jù)收集效率的前提下，該方法可以有效地縮短移動(dòng)軌跡。

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

本文的主要目標(biāo)是:針對Sink移動(dòng)軌跡可控的無線傳感器網(wǎng)絡(luò)，綜合考慮數(shù)據(jù)延時(shí)和能耗兩項(xiàng)技術(shù)指標(biāo)，提出了一種優(yōu)化的Sink路徑選擇機(jī)制，提高了系統(tǒng)能耗利用率，具體包含以下2個(gè)優(yōu)化目標(biāo):

1) 移動(dòng)距離在滿足系統(tǒng)要求的情況下最短化；2) 在目標(biāo)1) 的基礎(chǔ)上，系統(tǒng)整體能耗最小化。首先，定義一個(gè)由N個(gè)傳感器節(jié)點(diǎn)和一個(gè)Sink節(jié)點(diǎn)組成的無線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)是全連通的。節(jié)點(diǎn)間采用多跳方式通信；節(jié)點(diǎn)具有相同的初始能量，且能量有限，但Sink的能量不受限制；每個(gè)節(jié)點(diǎn)可以通過 GPS或其他定位算法知道各自的位置信息；Sink節(jié)點(diǎn)具有移動(dòng)性，并且移動(dòng)方式可控，其以恒定的速度 Vm移動(dòng)。

采用樹形結(jié)構(gòu)來表示網(wǎng)絡(luò)的拓?fù)?。設(shè)移動(dòng)Sink從節(jié)點(diǎn)B出發(fā)，并最終回到節(jié)點(diǎn)B。令 T( V, E)為以B為根節(jié)點(diǎn)的一顆樹，其中，V為所有傳感器節(jié)點(diǎn)，E為這些節(jié)點(diǎn)間的連接線。所有源節(jié)點(diǎn)的集合S = {Si}? V ；所有CP節(jié)點(diǎn)的集合表示為 C ={ p0,…, pnp-1}，pi表示第i個(gè)CP節(jié)點(diǎn)。當(dāng)然一個(gè)CP節(jié)點(diǎn)也是一個(gè)源傳感器節(jié)點(diǎn)。此時(shí)，將以每個(gè) pi為根節(jié)點(diǎn)形成子樹，子樹中的每個(gè)節(jié)點(diǎn)將數(shù)據(jù)傳輸給 pi并等待Sink節(jié)點(diǎn)來收集數(shù)據(jù)。用 np和 nnumber來表示CP節(jié)點(diǎn)的數(shù)量和成員節(jié)點(diǎn)的數(shù)量。即

2.1 移動(dòng)路徑最短化

利用移動(dòng)Sink進(jìn)行數(shù)據(jù)收集時(shí)，數(shù)據(jù)延時(shí)等于數(shù)據(jù)產(chǎn)生到移動(dòng)Sink收集該數(shù)據(jù)的時(shí)間差?？梢钥闯觯畲髷?shù)據(jù)延時(shí)是移動(dòng)Sink訪問所有CP節(jié)點(diǎn)所需要的時(shí)間。數(shù)據(jù)延時(shí)要求越小，Sink的移動(dòng)路徑越短。

假設(shè)在Sink的移動(dòng)路徑上共有 np個(gè)CP節(jié)點(diǎn)，每一對 CP節(jié)點(diǎn)間的直線距離可以表示為 [p0,p1],[p1,p2],…, [pnp-2,pnp-1]，這里可以用{z0,z1,… , znp-2}來表示。對于用戶給定的最大數(shù)據(jù)延時(shí) Dr，應(yīng)該滿足

2.2 系統(tǒng)能耗最小化

本文采用文獻(xiàn)[13]中的簡化能耗模型，節(jié)點(diǎn)總能耗p由接收和發(fā)送的數(shù)據(jù)總量kr和kt來決定。e為常數(shù)，表示發(fā)送和接收單位比特?cái)?shù)據(jù)的能耗。如式(3)所示。

當(dāng) Sink移動(dòng)到終點(diǎn)并返回到起點(diǎn)時(shí)，稱其完成一“輪”移動(dòng)。在每一輪中，任意節(jié)點(diǎn)i接收數(shù)據(jù)量和發(fā)送數(shù)據(jù)量之間的關(guān)系為=+q，q表示節(jié)點(diǎn)i在單輪中所采集到的數(shù)據(jù)總量。故有下式

其中，hi表示節(jié)點(diǎn)i到其所屬CP節(jié)點(diǎn)的最短跳數(shù)。如果節(jié)點(diǎn)i為CP，則hi為0。根據(jù)式（4）可以將單輪系統(tǒng)總能耗ptotal表述為最小跳數(shù)和的形式。

其中，pi為任意節(jié)點(diǎn)i的單輪總能耗。根據(jù)式（5）可知，系統(tǒng)總能耗最小化問題等價(jià)于全網(wǎng)節(jié)點(diǎn)距離其所屬CP節(jié)點(diǎn)跳數(shù)和的最小化問題。

2.3 最小能耗最短路徑問題

根據(jù)上述分析，可以發(fā)現(xiàn)當(dāng)選擇較長的 Sink節(jié)點(diǎn)移動(dòng)路徑時(shí)，移動(dòng)Sink可以訪問更多的CP點(diǎn)，使每個(gè)以CP點(diǎn)為根節(jié)點(diǎn)的子樹規(guī)模較小，從而節(jié)約網(wǎng)絡(luò)的能耗。但由于移動(dòng)路徑較長，數(shù)據(jù)傳輸?shù)难訒r(shí)會(huì)增加。相反，要求較小的數(shù)據(jù)延時(shí)，網(wǎng)絡(luò)的能耗也會(huì)變大。因此，在網(wǎng)絡(luò)能耗與移動(dòng)路徑的長度上存在一個(gè)折中，稱為最小能耗最短路徑問題（MEMD, min-energy min-distance）。Sink移動(dòng)路徑的優(yōu)化問題可描述為

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

滿足約束條件

3 匯聚節(jié)點(diǎn)的選擇

3.1 問題定義

定義1 （MEMD問題）給定樹結(jié)構(gòu) T( V, E)，由根節(jié)點(diǎn)（B）和一組傳感器節(jié)點(diǎn) S =? V 組成。尋找一條路徑U，從B出發(fā)，并訪問所有CP節(jié)點(diǎn)后回到B。使得路徑U的長度不超過規(guī)定延時(shí)內(nèi)的移動(dòng)距離，即 Drvm，同時(shí)滿足

定理1 MEMD是NP-hard問題。

證明 可以將 MEMD問題規(guī)約為一個(gè)旅行商問題（TSP, traveling salesman problem）。MEMD問題的一個(gè)特例是尋找一條移動(dòng)路徑使得網(wǎng)絡(luò)的傳輸能耗為 0。在這種情況下，所有的源節(jié)點(diǎn)都必須為CP節(jié)點(diǎn)，即移動(dòng)Sink訪問所有傳感器節(jié)點(diǎn)。此時(shí)，可以規(guī)約為一種旅行商問題，在規(guī)定的時(shí)間內(nèi)訪問一組城市并使路徑最短。

證畢。

3.2 基于效用的貪心算法

這里給出一種基于效用的貪心算法（utilitybased greedy heuristic）來選擇CP節(jié)點(diǎn)，稱為CPUG算法。該算法總是選擇那些能夠節(jié)約最大網(wǎng)絡(luò)能量的節(jié)點(diǎn)作為CP，并且所有CP節(jié)點(diǎn)間的距離和不超過Drvm。因此效用（utility）可定義為該CP節(jié)點(diǎn)節(jié)約的網(wǎng)絡(luò)能量與增加的移動(dòng)距離之間的比值。

需要注意的是，CP節(jié)點(diǎn)的功效會(huì)隨著移動(dòng)路徑長度的變化而變化。如在圖2所示，如果移動(dòng)Sink的路徑只能覆蓋B和其余一個(gè)CP點(diǎn)，即p1、p2或p3，那么應(yīng)該選擇p1，因?yàn)橛?個(gè)源節(jié)點(diǎn)在它的子樹中，其節(jié)約的能量最多。如果移動(dòng)Sink的路徑可以覆蓋 B、p2和 p3，所有的數(shù)據(jù)將在 p2和 p3點(diǎn)收集，p1的效用將為0。因此，CPUG算法必須在Sink的移動(dòng)過程中動(dòng)態(tài)地更新每一個(gè)節(jié)點(diǎn)的效用，通過多次迭代執(zhí)行獲得最佳的CP集合。

圖2 CPUG算法執(zhí)行示例

圖3給出了CPUG算法的偽代碼。初始情況下CP隊(duì)列中只包含根節(jié)點(diǎn)B，通過計(jì)算節(jié)點(diǎn)的效用不斷地加入CP節(jié)點(diǎn)。CPUG算法利用TSP()I過程來計(jì)算訪問集合I中所有節(jié)點(diǎn)的最短路徑。TSP()I可以采用基于幾何結(jié)構(gòu)的旅行商問題求解算法。每次迭代時(shí)，首先確定所有的CP候選節(jié)點(diǎn)（第2）步）。如果一個(gè)節(jié)點(diǎn)的加入使得移動(dòng)Sink以更短的路徑訪問所有的CP，同時(shí)這些CP節(jié)點(diǎn)的子樹中源節(jié)點(diǎn)的跳數(shù)和減少，那么該節(jié)點(diǎn)可以是一個(gè)候選節(jié)點(diǎn)。

候選節(jié)點(diǎn)x的效用定義為

u(x)等于源節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)跳數(shù)的減少和Sink移動(dòng)距離的增加之間的比值。CPUG算法選擇具有最大效用值的CP候選節(jié)點(diǎn)加入到CP隊(duì)列中（3）和4）），同時(shí)將CP隊(duì)列中效用值變?yōu)?的節(jié)點(diǎn)清除出去（5））。如果所有的源節(jié)點(diǎn)都已在Q中，則結(jié)束，否則開始新一輪的迭代。

圖3 CPUG—— 一種基于效用的CP節(jié)點(diǎn)選擇算法

以圖2中的例子來說明CPUG的執(zhí)行過程。圖2給出了CP隊(duì)列，需要3次迭代完成。在第1次迭代過程中選擇 s1作為CP節(jié)點(diǎn)。第2次迭代中，在所有節(jié)點(diǎn)中 s2具有最大的效用值。盡管 s2和 s3在路徑的距離增加上是相同的，但 s2節(jié)約的能量比 s3多，因?yàn)?s3的子樹中只有一個(gè)源節(jié)點(diǎn)，而 s2的子樹中有2個(gè)。在第3次迭代中 s3也被選擇CP節(jié)點(diǎn)，同時(shí)由于 s1的效用值變?yōu)?，將 s1清除出CP節(jié)點(diǎn)隊(duì)列。

4 概率路徑選擇算法

在 WSN應(yīng)用中，sensor節(jié)點(diǎn)按照一定的duty-cycle進(jìn)行工作。數(shù)據(jù)的產(chǎn)生具有時(shí)間性。當(dāng)移動(dòng)Sink對某個(gè)CP節(jié)點(diǎn)收集數(shù)據(jù)時(shí)，如果該CP節(jié)點(diǎn)沒有數(shù)據(jù)上傳，那將造成訪問該節(jié)點(diǎn)的時(shí)間浪費(fèi)。因此，移動(dòng)Sink對CP節(jié)點(diǎn)可以按照某種概率進(jìn)行訪問，通過概率的變化和移動(dòng)Sink的數(shù)量來保證數(shù)據(jù)收集的完整性。

4.1 數(shù)據(jù)延時(shí)限制

通常情況下，用戶對數(shù)據(jù)采集的延時(shí)會(huì)提出要求，例如最大數(shù)據(jù)延時(shí)為 Dr，而系統(tǒng)必須保證數(shù)據(jù)延時(shí)值不大于Dr。設(shè)移動(dòng)Sink訪問所有CP節(jié)點(diǎn)一次為一個(gè)周期，所需要的時(shí)間為τperiod。為了實(shí)現(xiàn)時(shí)間限制，首先給出訪問率的定義。

定義2 訪問率:一個(gè)CP節(jié)點(diǎn)在一個(gè)周期內(nèi)被移動(dòng)Sink至少訪問一次的概率定義為該CP的訪問率γp。

設(shè)某CP節(jié)點(diǎn)p的數(shù)據(jù)傳輸延時(shí)為Dp，則Dp和γp之間存在如下關(guān)系。

定理2 Dp的累積分布函數(shù)（cdf）如下

證明 Dp的cdf函數(shù)表示為

這表示在時(shí)間長度為d的范圍內(nèi)，沒有移動(dòng)Sink訪問該節(jié)點(diǎn)。共經(jīng)歷了k個(gè)τperiod周期以及剩余的d-kτperiod時(shí)間。τperiod內(nèi)未訪問該節(jié)點(diǎn)的概率為1-γp，d-kτperiod時(shí)間未訪問該節(jié)點(diǎn)的概率為1-γp。

證畢。

根據(jù)這個(gè)性質(zhì)，可以得到傳輸延時(shí)的上限。定義CP節(jié)點(diǎn)的最小訪問率為γ0，其數(shù)據(jù)傳輸延時(shí)D0應(yīng)該滿足

顯然，如果CP節(jié)點(diǎn)的訪問率大于該最小訪問率，那么數(shù)據(jù)傳輸延時(shí)應(yīng)更小，即

結(jié)合式（11）和式（12），可以得到

因此，當(dāng)確保對每一個(gè)CP節(jié)點(diǎn)的訪問率均大于γ0，那么可以保證所有數(shù)據(jù)的傳輸延時(shí)都低于用戶要求的最大延時(shí)Dr。由于對Dr要求的不同，因此γ0也會(huì)隨之變化。γ0情況下D0的期望如式(14)所示。

定理3 當(dāng)CP節(jié)點(diǎn)的訪問率為γ0時(shí)，D0的期望為

因此，可以得到D0的期望為

證畢。

上式中可以看出D0的期望值是γ0的單調(diào)遞減函數(shù)。

4.2 基于訪問概率的最短路徑選擇

本文給出了一種基于CP節(jié)點(diǎn)訪問概率的路徑選擇優(yōu)化算法。每個(gè)CP節(jié)點(diǎn)在系統(tǒng)初始化時(shí)分配一個(gè)訪問概率，該訪問概率由最大數(shù)據(jù)延時(shí)、Sink移動(dòng)路徑長度和移動(dòng)Sink的數(shù)量等因素決定，以保證在最大數(shù)據(jù)延時(shí)內(nèi)獲得最長的路徑，相應(yīng)地可以選擇更多的CP節(jié)點(diǎn)來節(jié)約網(wǎng)絡(luò)能量。

圖4給出了一個(gè)基于概率訪問的簡單例子。圖4(a)中，移動(dòng)Sink需要訪問5個(gè)CP節(jié)點(diǎn)。對于每個(gè) CP節(jié)點(diǎn) pi（pi∈C），其訪問概率設(shè)為βi，而忽略該節(jié)點(diǎn)的概率為1-βi。在Sink的移動(dòng)過程中，要實(shí)現(xiàn)平滑的移動(dòng)路線是很困難的，采用圖4(b)中的方法，用節(jié)點(diǎn)間的歐式距離作為移動(dòng)長度。每個(gè)連線上的權(quán)值即為該節(jié)點(diǎn)的訪問概率。

圖4 概率路徑選擇問題

結(jié)合CP節(jié)點(diǎn)的訪問概率和歐式距離來處理最短路徑選擇算法。對于CP隊(duì)列中每一個(gè)CP節(jié)點(diǎn)pi，其訪問概率為βi，設(shè)前一個(gè)CP節(jié)點(diǎn)到pi節(jié)點(diǎn)的歐式距離為 wi，當(dāng)前系統(tǒng)中共使用了m個(gè)移動(dòng)Sink來收集數(shù)據(jù)。那么，可以構(gòu)造整型線性規(guī)劃（IPL）模型為

滿足約束條件

式（18）確保了CP節(jié)點(diǎn)的訪問率不低于最大延時(shí)需求下的訪問率。

本文采用了單一訪問概率方法（identical probability schema），在多個(gè)移動(dòng)Sink訪問某CP時(shí)采用單一的概率，并且在系統(tǒng)的運(yùn)行過程中不變?？梢郧蟪鯟P節(jié)點(diǎn)的傳輸延時(shí)期望與訪問概率之間的關(guān)系。

定理 4 當(dāng)對 CP節(jié)點(diǎn)采用單一訪問概率方法時(shí)，其數(shù)據(jù)傳輸延時(shí)的期望值為

證明 設(shè)M為該 CP節(jié)點(diǎn)的數(shù)據(jù)被移動(dòng) Sink收集前經(jīng)過的訪問輪數(shù)，那么M的概率分布函數(shù)為

其中，θ為單輪內(nèi)CP節(jié)點(diǎn)的訪問概率，則

將θ代入式（20）中，得

如果數(shù)據(jù)在第i輪被收集，那么將增加傳輸延時(shí) （i- 1）τperiod，因此，計(jì)算條件M下的期望值為

證畢。

5 性能分析

5.1 實(shí)驗(yàn)設(shè)置

本節(jié)采用 NS2模擬器和真實(shí)的移動(dòng)傳感器實(shí)驗(yàn)床來測試CPUG算法和基于路徑選擇算法在網(wǎng)絡(luò)能耗和數(shù)據(jù)傳輸延時(shí)方面的性能。

在 NS2模擬器中主要測試網(wǎng)絡(luò)的能耗。設(shè)在300m × 300m的區(qū)域內(nèi)隨機(jī)部署400個(gè)節(jié)點(diǎn)，并從中選取100個(gè)節(jié)點(diǎn)作為CP節(jié)點(diǎn)。假設(shè)移動(dòng)Sink從區(qū)域的左上角出發(fā)。源節(jié)點(diǎn)以較低的duty-cycle進(jìn)行數(shù)據(jù)采集，并傳輸給CP節(jié)點(diǎn)。最大數(shù)據(jù)延時(shí)為5min，那么duty-cycle可在5min以內(nèi)。

模擬實(shí)驗(yàn)采用 C++語言編寫。通信規(guī)范符合CC2420 協(xié)議（Mica2 節(jié)點(diǎn)）[14]。傳輸帶寬為 40kbit/s，傳輸能耗為4dBm。設(shè)數(shù)據(jù)分組的大小為30byte。為了模擬網(wǎng)絡(luò)鏈接的不可靠性，采用USC鏈接層模型[15]。

筆者在室內(nèi)進(jìn)行真實(shí)的實(shí)驗(yàn)床性能測試。如圖5所示，在15m×15m的房間內(nèi)劃分成11×11的網(wǎng)格，20個(gè)TelosB傳感器節(jié)點(diǎn)（配置CC2420通信模塊）隨機(jī)放置在這些網(wǎng)格中，每個(gè)網(wǎng)格最多放置一個(gè)節(jié)點(diǎn)。傳感器節(jié)點(diǎn)使用TinyOS 2.x操作系統(tǒng)，編程語言為nesC。移動(dòng)Sink節(jié)點(diǎn)使用自主設(shè)計(jì)的DataTruck移動(dòng)傳感器節(jié)點(diǎn)[16]。該節(jié)點(diǎn)具有強(qiáng)計(jì)算能力和大存儲(chǔ)容量，采用了32bit ARM處理芯片，配置4個(gè)直流電機(jī)，最快速度接近2m/s。移動(dòng)Sink節(jié)點(diǎn)如圖5(b)所示。

圖5 實(shí)驗(yàn)環(huán)境及移動(dòng)Sink

5.2 網(wǎng)絡(luò)能耗

為了便于觀察網(wǎng)絡(luò)的性能，將本文算法和其他2種方法進(jìn)行比較。一種是未使用移動(dòng)Sink的情況，即通過多跳協(xié)議進(jìn)行數(shù)據(jù)傳輸，稱之為NET；另一種是文獻(xiàn)[10]中使用的RP-CP算法，它也是一種利用移動(dòng)節(jié)點(diǎn)和匯聚點(diǎn)進(jìn)行數(shù)據(jù)收集的方法。首先，測試網(wǎng)絡(luò)能耗與移動(dòng)節(jié)點(diǎn)速度的關(guān)系。從圖6中可以看出，隨著移動(dòng)Sink速度的增加，網(wǎng)絡(luò)能耗逐漸減少。這是因?yàn)橐苿?dòng)Sink可以在規(guī)定的時(shí)間范圍內(nèi)收集更多的數(shù)據(jù)。圖6中的CPUG-PPS方法是指利用CPUG并結(jié)合概率路徑選擇算法共同完成數(shù)據(jù)收集?？梢钥闯鯟PUG-PPS方法收集相同數(shù)據(jù)量時(shí)所需的能量開銷更小，是由于它可以減少更多的時(shí)間。如果按照特定的移動(dòng)路徑，CPUG-PPS方法比NET方法節(jié)約40%～70%的能量?？梢钥闯鲆苿?dòng)速度對網(wǎng)絡(luò)能耗有較大的影響，在下面的實(shí)驗(yàn)中固定Sink的移動(dòng)速度為1.5m/s。

圖6 網(wǎng)絡(luò)能耗與移動(dòng)Sink的速度關(guān)系

圖7給出不同節(jié)點(diǎn)密度下性能的比較。當(dāng)節(jié)點(diǎn)密度高時(shí)，網(wǎng)絡(luò)的鏈接性能將會(huì)更佳，所以在能耗方面3個(gè)算法的性能都優(yōu)于密度低的情況。同樣地，因?yàn)?CPUG-PPS方法忽略了一些沒有數(shù)據(jù)傳輸?shù)腃P節(jié)點(diǎn)，節(jié)約了更多的網(wǎng)絡(luò)能量。

圖7 網(wǎng)絡(luò)能耗與傳感器節(jié)點(diǎn)的關(guān)系

接下來，關(guān)注在不同的傳輸延時(shí)要求下算法的性能變化。設(shè)有8個(gè)不同的時(shí)延上限，從5min到40min，每個(gè)時(shí)延間隔5min。從最低的5min開始，每個(gè)條件下的源節(jié)點(diǎn)數(shù)目相同。從圖8中可以看出，隨著時(shí)延上限的增加，網(wǎng)絡(luò)的能耗卻相應(yīng)地減少。這是因?yàn)樵谳^長的時(shí)延上限情況下，算法可以訪問更多的CP節(jié)點(diǎn)，減少了源節(jié)點(diǎn)到CP節(jié)點(diǎn)的跳數(shù)，從而節(jié)約了能量。

圖8 網(wǎng)絡(luò)能耗與延時(shí)限制的關(guān)系

網(wǎng)絡(luò)能耗的一個(gè)指標(biāo)是以CP節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹中數(shù)據(jù)傳輸?shù)奶鴶?shù)之和。為了方便起見，通過統(tǒng)計(jì)所有子樹的路由長度來表示。路由長度越長，相應(yīng)地，數(shù)據(jù)傳輸?shù)奶鴶?shù)也越多。圖9給出了不同算法下網(wǎng)絡(luò)中所有子樹的路由長度。可以看出，當(dāng)規(guī)定的時(shí)延上限增加時(shí)，由于可以選擇更多的CP節(jié)點(diǎn)，因此路由的長度減少了。圖10說明了當(dāng)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)增加時(shí)，由于每個(gè)CP節(jié)點(diǎn)的子樹規(guī)模也會(huì)增加，因此網(wǎng)絡(luò)能耗也增加了。

圖9 節(jié)點(diǎn)路由樹長度與延時(shí)限制的關(guān)系

圖10 節(jié)點(diǎn)路由樹長度與節(jié)點(diǎn)數(shù)量的關(guān)系

另一組實(shí)驗(yàn)用來測試移動(dòng) Sink數(shù)目變化時(shí)網(wǎng)絡(luò)的性能。每個(gè)移動(dòng)Sink輪流訪問CP隊(duì)列中的節(jié)點(diǎn)，其間隔可根據(jù)移動(dòng)Sink數(shù)據(jù)的增加相應(yīng)減少。從圖11可以看出，當(dāng)移動(dòng)Sink的數(shù)目增加時(shí)，由于在相同的規(guī)定時(shí)間內(nèi)可以訪問更多的CP節(jié)點(diǎn)，所以網(wǎng)絡(luò)能耗逐漸減少。

圖11 網(wǎng)絡(luò)能耗與移動(dòng)Sink數(shù)量的關(guān)系

5.3 概率路徑選擇算法性能

利用移動(dòng)傳感器實(shí)驗(yàn)床單獨(dú)測試概率路徑選擇算法的性能。主要包括2個(gè)性能參數(shù)，一個(gè)是傳輸?shù)臅r(shí)延，一個(gè)是路由樹的長度。

為了標(biāo)識網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)必須具有唯一的地址以及特定的數(shù)據(jù)傳輸格式。節(jié)點(diǎn)地址可以用數(shù)字來表示，傳輸格式如圖12所示。

字段的含義如下:

實(shí)驗(yàn)中選擇5個(gè)節(jié)點(diǎn)作為CP節(jié)點(diǎn)，其他作為源節(jié)點(diǎn)。移動(dòng)Sink按照一定的概率訪問這5個(gè)CP節(jié)點(diǎn)。通常情況下移動(dòng)Sink以閉環(huán)的方式循環(huán)訪問這些CP節(jié)點(diǎn)，通過測量可知這 5個(gè)節(jié)點(diǎn)間的最短距離為50m，那么平均延時(shí)為25s左右。圖13給出了CP節(jié)點(diǎn)的訪問概率與平均傳輸延時(shí)之間的關(guān)系。從圖13中可以看出，移動(dòng)Sink根據(jù)訪問概率會(huì)避免訪問一些 CP節(jié)點(diǎn)，減少了移動(dòng)路徑，因此縮短了傳輸延時(shí)。圖14中的曲線說明了當(dāng)一些 CP節(jié)點(diǎn)沒有訪問但其有數(shù)據(jù)需要傳輸時(shí)，在最大延時(shí)之前通過多跳的方式發(fā)送到基站，這樣增加了網(wǎng)絡(luò)能量的開銷，所以隨著訪問概率的降低能耗會(huì)增大。

圖13 平均傳輸延時(shí)與初始概率的關(guān)系

圖14 節(jié)點(diǎn)路由樹長度與初始概率的關(guān)系

在第2組實(shí)驗(yàn)中，假設(shè)20個(gè)傳感器節(jié)點(diǎn)均為CP節(jié)點(diǎn)，當(dāng)一個(gè)移動(dòng)Sink訪問這些節(jié)點(diǎn)的概率均為80%，那么它在2輪中對這些節(jié)點(diǎn)的訪問情況如圖15所示。可以看出在這兩輪中，移動(dòng)Sink訪問90%以上的節(jié)點(diǎn)。因此，可以說當(dāng)對 CP節(jié)點(diǎn)確保相對較高的訪問概率時(shí)，絕大部分的節(jié)點(diǎn)可以在較少的時(shí)間內(nèi)訪問到。

圖15 單個(gè)Sink在2輪移動(dòng)過程中的路徑選擇情況

6 結(jié)束語

本文利用移動(dòng)Sink來解決WSN中能量空洞等問題。提出了一種最短移動(dòng)距離最小能耗的路徑優(yōu)化算法，并證明了該模型是一個(gè)NP-hard問題。為了在規(guī)定的最大傳輸延時(shí)范圍內(nèi)訪問盡可能多的CP節(jié)點(diǎn)，提出了一種基于CP節(jié)點(diǎn)訪問概率的路徑選擇算法。通過模擬實(shí)驗(yàn)以及實(shí)驗(yàn)床的真實(shí)數(shù)據(jù)，驗(yàn)證了本文提出的算法能夠很好地在滿足延時(shí)要求的同時(shí)節(jié)約網(wǎng)絡(luò)的能量。

[1]TOLLE G, POLASTRE J, SZEWCZYK R, et al.Amacroscope in the redwoods[A].ACM SenSys[C].San Diego, USA, 2005.51-63.

[2]MAYER K, ELLIS K, TAYLOR K.Cattle health mon-itoring using wireless sensor networks[A].Proc of the ACM IASTED[C].Cambridge, Massachusetts, USA, 2004.375-380.

[3]XUE W, LUO Q, CHEN L, et al.Contour mapmatching for event detection in sensor networks[A].Proc of the ACM SIGMOD[C].Chicago, USA, 2006.375-380.

[4]DU W, FANG L, NING P.Lad:localization anomaly detection for wireless sensor networks[A].Proc of the IEEE IPDPS[C].Denver,Colorado, 2005.121- 127.

[5]ASLAM J, BUTLER Z, CONSTANTIN F, et al.Tracking a moving object with a binary sensor network[A].Proc of the ACM SenSys[C].San Diego, USA, 2005.150-161.

[6]SRINIVASAN W W V, CHUA K C.Trade-offs between mobility and density for coverage in wireless sensor networks[A].Proc of the ACM MobiCom[C].Montreal, Quebec, Canada, 2007.39-50.

[7]LI Z J, LI M, WANG J L, et al.Ubiquitous data collection for mobile users in wireless sensor networks[A].Proc of the IEEE INFOCOM[C].Shanghai, China, 2011.2246-2254.

[8]LUO J, ZHANG Q, WANG D.Delay tolerant event collection for underground coal mine using mobile sinks[A].Proc of the IEEE IWQoS[C].Charleston, USA, 2009.1-9.

[9]SUGIHARA R, GUPTA R K.Optimizing energy-latency trade-off in sensor networks with controlled mobility[A].Proc of the IEEE INFOCOM[C].Rio, Brazil, 2009.1398-1408.

[10]XING G L, WANG T, JIA W J, et al.Rendezvous design algorithms for wireless sensor networks with a mobile base station[A].Proc of the ACM MobiHoc[C].Hongkong, China, 2008.231-240.

[11]郜帥, 張宏科.時(shí)延受限傳感器網(wǎng)絡(luò)移動(dòng) Sink路徑選擇方法研究[J].電子學(xué)報(bào), 2011, 39(4):742-747.GAO S, ZHANG H K.Optimal path selection for mobile Sink in delayguaranteed sensor networks[J].Acta Electronica Sinica, 2011,39(4):742-747.

[12]程龍, 陳燦峰, 馬建.無線傳感器網(wǎng)絡(luò)中多移動(dòng) Sink的選擇策略[J].通信學(xué)報(bào), 2008, 29(11):12-18.CHENG L, CHEN C F, MA J.Selection schema of mobile Sinks in wireless sensor networks[J].Journal on Communications, 2008, 29(11):12-18.

[13]KIM H S, ABDELZAHER T F, KWON W H.Dynamic delay- constrained minimum-energy dissemination in wireless sensor networks[J].ACM Transactions on Embedded Computing System, 2005,4(3):679-706.

[14]CROSSBOW.Mica and mica2 wireless measurement system datasheets[EB/OL].2004.

[15]ZHAO J, GOVINDAN R.Understanding packet delivery performance in dense wireless sensor networks[A].Proc of the ACM SenSys[C].Los Angeles, USA, 2003.311-320.

[16]張希偉，陳貴海.基于SDMA應(yīng)用的移動(dòng)Sink節(jié)點(diǎn)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展, 2012, 49(3):541-549.ZHANG X W, CHEN G H.Design of mobile Sink node for SDMA applications in WSN[J].Journal of Computer Research and Development, 2012, 49(3):541-549.