郭劍，孫力娟，許文君，王汝傳，肖甫

（1. 南京郵電大學(xué) 計(jì)算機(jī)學(xué)院， 江蘇 南京210003；2. 南京郵電大學(xué) 江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；3. 南京郵電大學(xué) 寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003）

1 引言

無線傳感器網(wǎng)絡(luò)[1,2]（WSN, wireless sensor network）是一種具有廣泛用途的網(wǎng)絡(luò)，數(shù)據(jù)采集是其基本應(yīng)用之一。人們在工作環(huán)境中布置大量的傳感器節(jié)點(diǎn)，并對需要的各種數(shù)據(jù)進(jìn)行采集，如溫度、濕度、濃度、圖像、聲音、視頻等。實(shí)際應(yīng)用中，許多業(yè)務(wù)的數(shù)據(jù)量都較大，比如圖像和視頻相關(guān)的應(yīng)用，這就給數(shù)據(jù)采集方案的設(shè)計(jì)帶來了一定的挑戰(zhàn)。傳統(tǒng)的處理方法中，所有節(jié)點(diǎn)位置固定，采集到數(shù)據(jù)后，借助于路由協(xié)議將信息提交給sink。它的主要問題是：1）漏斗效應(yīng)，距離 sink越近的節(jié)點(diǎn)能量消耗越大，網(wǎng)絡(luò)會(huì)較早地出現(xiàn)分割，大數(shù)據(jù)量的業(yè)務(wù)尤其如此；2）通信開銷，無論是哪種路由算法，都會(huì)有一定的控制開銷，需要耗費(fèi)節(jié)點(diǎn)的能量；3）連通約束，網(wǎng)絡(luò)不連通時(shí)必然有部分節(jié)點(diǎn)的數(shù)據(jù)無法提交。

圖1 可移動(dòng)節(jié)點(diǎn)

上述缺陷的部分根源在于sink的靜止性。隨著RacemoteZ[3]、quadcopter[4]等可移動(dòng)節(jié)點(diǎn)的提出（如圖 1所示），一些學(xué)者提出了基于移動(dòng)節(jié)點(diǎn)的采集方案[5,6]，部分解決了上述問題。此類方法的問題是存在一些時(shí)延[7,8]，并且難以確定 sink節(jié)點(diǎn)的移動(dòng)方案。由于大多數(shù)數(shù)據(jù)采集型應(yīng)用（data-gathering applications）對實(shí)時(shí)性要求不高，因此sink的移動(dòng)控制才是關(guān)鍵，目前已有這方面的一些成果發(fā)表。隨機(jī)漫游[9]策略算法簡單，但是它不考慮節(jié)點(diǎn)的分布狀況，會(huì)導(dǎo)致節(jié)點(diǎn)能耗嚴(yán)重不均衡。AKKAYA等提出了一個(gè)啟發(fā)式移動(dòng)策略[10]，sink每次向發(fā)送數(shù)據(jù)量最多的節(jié)點(diǎn)移動(dòng)。這個(gè)策略比較適合事件驅(qū)動(dòng)型應(yīng)用（event-driven applications），但不適合數(shù)據(jù)采集型網(wǎng)絡(luò)。LUO[11]等提出了沿區(qū)域邊際移動(dòng)的Peripheral策略，但Peripheral較為理想化，對MAC層的沖突考慮不夠。LMREM[12]方案根據(jù)節(jié)點(diǎn)的剩余能量來選擇移動(dòng)位置，它的計(jì)算開銷較大，并且節(jié)點(diǎn)還需要保存和轉(zhuǎn)發(fā)較多的數(shù)據(jù)，網(wǎng)絡(luò)負(fù)荷很重時(shí)，節(jié)點(diǎn)很容易死亡。

針對這些問題，本文提出了一種軌跡固定的數(shù)據(jù)采集方案（DCSR, data collection scheme with regular track）。DCSR的移動(dòng)策略包括2個(gè)環(huán)節(jié)：第一，根據(jù)節(jié)點(diǎn)的分布狀況選出一批采集點(diǎn)；第二，找到經(jīng)過這些點(diǎn)的最短環(huán)路。這個(gè)環(huán)路就作為sink的采集路線，sink沿著它運(yùn)動(dòng)和收集數(shù)據(jù)。根據(jù)文獻(xiàn)[10]，在網(wǎng)絡(luò)中尋找最優(yōu)采集地點(diǎn)是一個(gè) NP問題。而計(jì)算最短環(huán)路是一個(gè)旅行商問題，也屬于NP問題。這2個(gè)步驟都沒有特別好的處理方法，因此本文均進(jìn)行了簡化與近似。選取采集點(diǎn)時(shí)，DCSR盡量少選一些采集點(diǎn)，計(jì)算最短環(huán)路時(shí)，DCSR使用了量子遺傳算法[13,14]（QGA, quantum genetic algorithm）。對比測試表明，DCSR的性能較好，且能夠收集更多的數(shù)據(jù)。

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

本文使用了如下的網(wǎng)絡(luò)模型。

1) 傳感器節(jié)點(diǎn)：網(wǎng)絡(luò)中使用的是同類型的傳感器節(jié)點(diǎn)，且它們具有相同的初始能量。這些節(jié)點(diǎn)被隨機(jī)部署在一個(gè)邊長為e的正方形監(jiān)控區(qū)域中，且放置后不可移動(dòng)。

2) sink節(jié)點(diǎn)：sink節(jié)點(diǎn)具有充沛的電池能量與較高的存儲(chǔ)容量，并有一定的移動(dòng)能力。sink節(jié)點(diǎn)的通信距離與普通節(jié)點(diǎn)相同，均為r。

3) 業(yè)務(wù)類型：周期采集型業(yè)務(wù)，節(jié)點(diǎn)定期從傳感器上收集數(shù)據(jù)。

4) 數(shù)據(jù)提交模式：被動(dòng)提交。節(jié)點(diǎn)收集到數(shù)據(jù)后存入自己的緩存；只有當(dāng)它收到sink節(jié)點(diǎn)的通知時(shí)，它才提交數(shù)據(jù)。

在上述假設(shè)中，sink節(jié)點(diǎn)是較為關(guān)鍵的一個(gè)環(huán)節(jié)，實(shí)現(xiàn)時(shí)可以采用 RacemoteZ、quadcopter等可移動(dòng)節(jié)點(diǎn)來獲得移動(dòng)性，并通過大容量電池或定期充電等方式來保障能量供應(yīng)。此外，本文在計(jì)算sink的移動(dòng)路線時(shí)，沒有考慮現(xiàn)實(shí)道路情況對節(jié)點(diǎn)移動(dòng)路徑的限制，也就是假設(shè)監(jiān)控場景中地面較為平整，sink可以任意移動(dòng)。當(dāng)然，如果 sink采用quadcopter等飛行傳感器節(jié)點(diǎn)，這個(gè)問題就不存在。

3 采集點(diǎn)的確定

在第1個(gè)階段中，DCSR需要從監(jiān)控區(qū)域中選出一批采集點(diǎn)。采集點(diǎn)的數(shù)量應(yīng)該盡可能少，這樣可以減輕第2個(gè)階段的計(jì)算量，并且計(jì)算出的最短環(huán)路也相對更短。由于sink在每個(gè)采集點(diǎn)的通信范圍可以看成一個(gè)以采集點(diǎn)位置為圓心的圓盤，因此，第1個(gè)階段的任務(wù)就是找到一組坐標(biāo)集合，并滿足如下條件：

1) 坐標(biāo)的數(shù)量盡可能少；

2) 以這些坐標(biāo)為圓心，r為半徑的一組圓盤能夠覆蓋監(jiān)控區(qū)域。

3.1 圓盤位置的確定

在部署圓盤時(shí)，為了避免空隙，相鄰圓盤必然相互重疊。如圖2所示，圓盤A與B相鄰，它們相互重疊，而它們下方的空隙又由圓盤C來覆蓋，因此圓盤C也和它們相交。為了減少圓盤數(shù)，重疊的部分應(yīng)越小越好。因此C的邊界應(yīng)恰好覆蓋A與B的交點(diǎn)O。否則，它們之間或者產(chǎn)生三重重疊，或者出現(xiàn)空洞。此時(shí)就有了定理1。

圖2 相互重疊的3個(gè)圓盤

定理1 當(dāng)兩兩重疊的3個(gè)圓盤圓心組成等邊三角形時(shí)，它們的重疊面積最小[15]。

證明 假設(shè)圓盤 A、B、C重疊的面積分別為SAB、SBC、SAC，則重疊的總面積S為

由于AXCYBZ是一個(gè)六邊形，因此有

2α+(π-α)+2β+(π-β)+2γ+(π-γ) = 4π

即

這里就是要求解滿足式(2)條件下的式(1)的極值。根據(jù)拉格朗日乘數(shù)法，可求得當(dāng) α= β= γ = π/3時(shí)，S的值最小。此時(shí)3個(gè)圓盤的圓心組成等邊三角形，且三角形的邊長為 3r。

滿足定理1的圓盤位置集合有多組，其中一組如式（3）所示，圖3為其分布示意。

圖3 圓盤分布示意

其中，m1、m2、m3、m4皆為非負(fù)整數(shù)，且滿足

3.2 采集點(diǎn)的選取

確定完所有的圓盤后，DCSR將在每個(gè)圓盤中選擇一個(gè)采集點(diǎn)。確定這個(gè)位置時(shí)，DCSR主要考慮了能耗的因素。

根據(jù)文獻(xiàn)[16]，當(dāng)傳感器節(jié)點(diǎn)向外發(fā)送數(shù)據(jù)時(shí)，遵循式(4)。

其中，Gr、Gt分別表示接收端和發(fā)送端的天線增益，Pr、Pt分別表示接收端和發(fā)送端的天線功率，d為源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的距離，L表示系統(tǒng)損耗因子，λ表示載波波長，通常Gr、Gt、L、λ都是常量。對于某一個(gè)具體的網(wǎng)絡(luò)來說，如果節(jié)點(diǎn)同質(zhì)且干擾抑制較為理想，則Pr也可以認(rèn)為是一個(gè)常量。因此式(4)可以簡寫為式(5)。

假定一個(gè)圓盤中有n個(gè)節(jié)點(diǎn)，則每次數(shù)據(jù)采集過程中，n個(gè)節(jié)點(diǎn)的總發(fā)射功率P為

其中，（xi，yi）表示第 i個(gè)節(jié)點(diǎn)的位置，(xs，ys)表示采集點(diǎn)的位置。

從式（6）可以看出，要使總發(fā)射功率最小，就應(yīng)該選擇合理的采集點(diǎn)位置，使所有節(jié)點(diǎn)到它的距離平方和最小。

定理2 假定半徑為r的圓域中有n個(gè)點(diǎn)，每個(gè)點(diǎn)的坐標(biāo)為（xi，yi），1≤i≤n。欲在該圓中找到一點(diǎn)，使得它到所有節(jié)點(diǎn)距離的平方和最小，則該點(diǎn)坐標(biāo)是

證明 假設(shè)圓心的坐標(biāo)為（xc，yc），該點(diǎn)坐標(biāo)為（xs，ys），每個(gè)點(diǎn)到它的距離為di，1≤i≤n，則所有距離的平方和fs為

式(7)受式(8)的約束，

根據(jù)拉格朗日乘數(shù)法，可求得

定理2指出了sink節(jié)點(diǎn)的理想位置。但是，定理2不保證每個(gè)節(jié)點(diǎn)到該位置的距離di≤r。因此如果sink節(jié)點(diǎn)選擇該位置，部分節(jié)點(diǎn)的信息有可能會(huì)收集不到。此時(shí)就有了定理3。

定理 3 假設(shè)圓盤中最大、最小橫縱坐標(biāo)分別為 xmax、xmin、ymax、ymin，(xs，ys)是所有節(jié)點(diǎn)坐標(biāo)的平均值，則當(dāng)式(10)成立時(shí)，圓盤內(nèi)節(jié)點(diǎn)到（xs，ys）的距離均小于r。

因此，（xs，ys）到任一節(jié)點(diǎn)的距離

定理3說明，當(dāng)圓盤內(nèi)的節(jié)點(diǎn)分布符合式(10)時(shí)，可以采用式(9)計(jì)算采集點(diǎn)的位置。

進(jìn)一步對節(jié)點(diǎn)分布進(jìn)行分析。由于圓盤的半徑為r，易知

即(xs，ys)的范圍不會(huì)超出一個(gè)矩形區(qū)域，如圖4所示。假設(shè)該矩形的邊長分別為l1、l2。則有

圖4 采集點(diǎn)位置的坐標(biāo)范圍

由式（11）可以看出，當(dāng)圓盤中節(jié)點(diǎn)較為集中時(shí)，l1、l2相對較大，矩形面積SR也較大；反之當(dāng)節(jié)點(diǎn)較為分散時(shí)，SR較小。由此可以得到定理4。

定理 4 當(dāng)矩形面積 SR滿足式(12)時(shí)，式(10)成立。

證明 將式(12)展開并整理，即可得式(10)。

定理4說明，當(dāng)矩形面積較大，滿足式(12)時(shí)，可采用所有節(jié)點(diǎn)的坐標(biāo)均值作為采集點(diǎn)位置。

而當(dāng)矩形的面積較小時(shí)，定理2不再適用。DCSR進(jìn)行了近似處理，在水平方向和垂直方向上分別用 l條直線對這個(gè)矩形區(qū)域進(jìn)行等分。等分之后，包括邊界在內(nèi)，相交得到了(l+2)2個(gè)點(diǎn)。DCSR依次對這些點(diǎn)進(jìn)行嘗試，找出距離之和最小的位置作為采集點(diǎn)。l值的大小跟求解精度相關(guān)，本文中取值40。

綜合以上各種情況，DCSR采用如下方法來計(jì)算采集點(diǎn)位置。

對于任一圓盤，設(shè)其中有n個(gè)節(jié)點(diǎn)，(xs，ys)為待求的采集點(diǎn)位置：

① 如果n=0，該圓盤內(nèi)不設(shè)采集點(diǎn)；

② 如果 n=1，采集點(diǎn)位置即為唯一的節(jié)點(diǎn)坐標(biāo)；

③ 如果n=2，取兩節(jié)點(diǎn)連線的中點(diǎn)作為采集點(diǎn)；

④ 如果n＞2，計(jì)算(xs，ys)所在的矩形區(qū)域：當(dāng)該矩形區(qū)域面積較大，滿足式(12)時(shí)，計(jì)算所有節(jié)點(diǎn)坐標(biāo)的平均值作為采集點(diǎn)，否則采用劃分網(wǎng)格的方法求近似點(diǎn)。

4 移動(dòng)路徑的計(jì)算

得到了采集點(diǎn)之后，DCSR采用QGA來尋找經(jīng)過這些點(diǎn)的最短環(huán)路。QGA是在遺傳算法的基礎(chǔ)上發(fā)展起來的一種算法。它引入了量子計(jì)算的概念，具有快速的收斂速度和較強(qiáng)的并行搜索能力，被廣泛運(yùn)用于求解各種優(yōu)化問題。在QGA中，組成種群的基本單位是量子染色體。每個(gè)量子染色體由多個(gè)量子比特組成。一條典型的量子染色體如式(13)所示。

其中，αij、βij∈C，且滿足i∈[1, n]，j∈[1, k]。n為染色體中的基因數(shù)，k為基因中的量子比特個(gè)數(shù)。

量子染色體向傳統(tǒng)染色體的轉(zhuǎn)換通過量子觀測操作實(shí)現(xiàn)，量子染色體的更新通過量子旋轉(zhuǎn)門實(shí)現(xiàn)。應(yīng)用QGA的主要問題是染色體的編碼和適應(yīng)度的計(jì)算。下面分別進(jìn)行說明。

1) 染色體的編碼

DCSR采用了對采集點(diǎn)可選鏈路進(jìn)行編碼的方法，在這種編碼策略中，染色體的每個(gè)基因?qū)?yīng)一個(gè)采集點(diǎn)，基因的值就是在該采集點(diǎn)選中的鏈路編號。圖5給出了一個(gè)監(jiān)控區(qū)域的實(shí)例，在圖5中共有A～G 7個(gè)采集點(diǎn)，連線表示可選的鏈路（過長的已剔除）。表1給出了這些鏈路的編號。圖6給出了一條染色體示例，它代表環(huán)路A-B-C-E-F-G-D-A。

圖5 采集點(diǎn)分布示意

表1 各采集點(diǎn)的鏈路編號

圖6 染色體示例

2) 適應(yīng)度的計(jì)算

適應(yīng)度主要考查2個(gè)因素：第一，染色體包含的鏈路中所構(gòu)成的最長路徑是多少跳；第二，該最長路徑的長度是多少。適應(yīng)度的計(jì)算如式(14)所示。

其中，f是計(jì)算出的適應(yīng)度值，h是染色體中的鏈路所形成的最長路徑的跳數(shù)，l是該最長路徑的長度，α是調(diào)節(jié)系數(shù)，根據(jù)具體網(wǎng)絡(luò)決定。

5 DCSR方案

5.1 DCSR的具體步驟

DCSR的具體步驟如下。

1) 初始化：各節(jié)點(diǎn)向 sink節(jié)點(diǎn)匯報(bào)自己的位置信息。

2) 路徑計(jì)算：sink根據(jù)各節(jié)點(diǎn)的位置分布，依次采用第3節(jié)和第4節(jié)的方法分別計(jì)算出本網(wǎng)絡(luò)所需要的采集點(diǎn)以及經(jīng)過這些采集點(diǎn)的最短回路。

3) 數(shù)據(jù)收集：sink沿計(jì)算好的路線移動(dòng)，每到達(dá)一個(gè)采集點(diǎn)便廣播一條收集通知。附近的節(jié)點(diǎn)收到通知后，將保存的數(shù)據(jù)提交。為減少信道沖突，每個(gè)節(jié)點(diǎn)回復(fù)數(shù)據(jù)前需要隨機(jī)等待一段時(shí)間。

5.2 DCSR方案的性能分析

1) 時(shí)間復(fù)雜度

DCSR的路徑規(guī)劃包含2個(gè)步驟：計(jì)算采集點(diǎn)和計(jì)算路徑。

計(jì)算采集點(diǎn)時(shí)，由第3節(jié)可知，對于邊長為e的區(qū)域，其中至多有個(gè)圓盤，每個(gè)圓盤在最壞情況下嘗試(l+2)2個(gè)點(diǎn)，因此這一步驟的時(shí)間復(fù)雜度為

計(jì)算路徑采用了QGA。QGA的復(fù)雜性分析較難，學(xué)術(shù)界還沒有精確的理論成果發(fā)表，此處僅作近似分析。根據(jù)第4節(jié)的編碼方式，每個(gè)染色體有個(gè)基因，每個(gè)基因最多有個(gè)量子比特，因此每條染色體最多有個(gè)量子比特。假設(shè)QGA一共有m個(gè)染色體，算法一共迭代n次，每次迭代中要進(jìn)行染色體的觀測、適應(yīng)度的計(jì)算、染色體的更新和最優(yōu)染色體的選擇4個(gè)操作，其時(shí)間復(fù)雜度分別為、O(m)。因此計(jì)算路徑的時(shí)間復(fù)雜度應(yīng)為

由于l值不需要取很大，通常有mn＞ l2，因此，綜合這 2個(gè)步驟可知 DCSR的時(shí)間復(fù)雜度為

2) 通信代價(jià)及效率

采集數(shù)據(jù)時(shí)，DCSR在每個(gè)采集點(diǎn)僅廣播一條通知。整個(gè)監(jiān)控區(qū)域至多有個(gè)圓盤，因此DCSR的通信代價(jià)是。

假設(shè)傳感器網(wǎng)絡(luò)由k個(gè)節(jié)點(diǎn)組成。在每一輪的數(shù)據(jù)采集中，sink節(jié)點(diǎn)至多廣播條通知，至少收到k個(gè)數(shù)據(jù)分組，因此，通信效率應(yīng)不小于

6 仿真及測試

6.1 場景設(shè)置及測試指標(biāo)

本文在NS 2.34環(huán)境下實(shí)現(xiàn)了DCSR 協(xié)議。為了驗(yàn)證其性能，本文將它與靜止sink（stationary）方式、隨機(jī)（random）漫游策略和 Peripheral協(xié)議進(jìn)行了對比測試。在這4個(gè)策略中，DCSR、Random采用了被動(dòng)提交模式，節(jié)點(diǎn)收集到數(shù)據(jù)后將其保存在本地，收到通知后才發(fā)送給sink節(jié)點(diǎn)，Stationary、Peripheral采用了主動(dòng)提交模式，節(jié)點(diǎn)收集到任何數(shù)據(jù)都主動(dòng)向sink節(jié)點(diǎn)發(fā)送，因此需要借助于路由協(xié)議。其他實(shí)驗(yàn)參數(shù)的設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

在測試時(shí)，本文主要考察了如下6個(gè)指標(biāo)。

1) 采集數(shù)據(jù)量：到達(dá) sink節(jié)點(diǎn)的有效數(shù)據(jù)分組的數(shù)量。所謂有效數(shù)據(jù)分組是指含有采集數(shù)據(jù)的數(shù)據(jù)分組。

2) 吞吐量：網(wǎng)絡(luò)中所有數(shù)據(jù)分組的總數(shù)與網(wǎng)絡(luò)工作時(shí)間之比。網(wǎng)絡(luò)中的所有數(shù)據(jù)分組包括發(fā)送的數(shù)據(jù)分組、沖突重發(fā)的數(shù)據(jù)分組、節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組、路由探詢分組和路由控制分組等。

3) 效率：sink收到的有效數(shù)據(jù)分組總數(shù)與網(wǎng)絡(luò)中所有數(shù)據(jù)分組的總數(shù)之比。

4) 剩余能量：網(wǎng)絡(luò)不能正常工作，即 sink采集不到數(shù)據(jù)時(shí)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余能量。

5) 能量利用率：sink收集到的數(shù)據(jù)總量與網(wǎng)絡(luò)的總耗能之比。

6) 平均時(shí)延：到達(dá) sink節(jié)點(diǎn)的有效數(shù)據(jù)分組的時(shí)延平均值。

6.2 實(shí)驗(yàn)結(jié)果

1) 采集數(shù)據(jù)量

4種協(xié)議的采集數(shù)據(jù)量對比如圖7所示。其中，圖7(a) sink以5m/s的速度移動(dòng)，圖7(b)sink以25m/s的速度移動(dòng)，Stationary的sink節(jié)點(diǎn)均靜止不動(dòng)，下同。從圖中可以發(fā)現(xiàn)，由于節(jié)點(diǎn)的增多和移動(dòng)速度的加快，網(wǎng)絡(luò)中的沖突增加，因此所有方案收集的數(shù)據(jù)量均有所下降。DCSR由于節(jié)點(diǎn)不需要轉(zhuǎn)發(fā)數(shù)據(jù)，所以能耗較輕，工作時(shí)間相對較長，采集到的數(shù)據(jù)最多。Random由于路線不夠合理，會(huì)出現(xiàn)部分節(jié)點(diǎn)過早死亡和部分節(jié)點(diǎn)訪問不到的情況，因此收集的數(shù)據(jù)量要少一些。Stationary由于網(wǎng)絡(luò)很早就中斷，因此收集數(shù)據(jù)最少。

圖7 采集的數(shù)據(jù)量

2) 效率

4種協(xié)議的采集效率比較如圖 8所示。由于DCSR沒有路由開銷，且節(jié)點(diǎn)不需要轉(zhuǎn)發(fā)數(shù)據(jù)，因此采集效率較高。

3) 吞吐量

4種協(xié)議的網(wǎng)絡(luò)吞吐量（單位：分組數(shù)/s）比較如圖9所示。網(wǎng)絡(luò)吞吐量是衡量網(wǎng)絡(luò)性能的重要指標(biāo)之一。從圖中可以看出，被動(dòng)提交模式網(wǎng)絡(luò)的吞吐量要高于主動(dòng)提交模式的網(wǎng)絡(luò)。這是因?yàn)楣?jié)點(diǎn)沒有轉(zhuǎn)發(fā)數(shù)據(jù)的負(fù)擔(dān)，因此可以一直工作，不會(huì)過早死亡。而主動(dòng)提交模式的網(wǎng)絡(luò)，大量節(jié)點(diǎn)很早就死亡，個(gè)別節(jié)點(diǎn)的數(shù)據(jù)sink節(jié)點(diǎn)又不易采集，因此網(wǎng)絡(luò)的吞吐量較低。DCSR由于路線比Random合理，數(shù)據(jù)采集更穩(wěn)定，吞吐量更高。

圖8 網(wǎng)絡(luò)效率

圖9 吞吐量

4) 剩余能量

4種協(xié)議的網(wǎng)絡(luò)剩余能量比較如圖10所示。從圖中可以看出，在Stationary策略中，sink靜止不動(dòng)導(dǎo)致周圍節(jié)點(diǎn)很快死亡，網(wǎng)絡(luò)很早中斷，所以剩余能量較多，這實(shí)際上也是能量的浪費(fèi)。在使用移動(dòng)sink的3種策略中，DCSR的路線最為合理，且節(jié)點(diǎn)不承擔(dān)轉(zhuǎn)發(fā)任務(wù)，能量消耗較為均衡，因此網(wǎng)絡(luò)工作結(jié)束時(shí)，能量幾乎全部消耗完，且全部用在提交數(shù)據(jù)上。

圖10 剩余能量

5) 能量利用率

4種協(xié)議的能量利用率比較如圖11所示。它的實(shí)際意義是網(wǎng)絡(luò)每消耗1J能量，sink所能采集到的有效數(shù)據(jù)量。從圖中可以看出，DCSR能量的利用率比其他3個(gè)協(xié)議都高。

圖11 能量利用率

6) 平均時(shí)延

4種協(xié)議的平均時(shí)延比較如圖12所示。從圖中可以發(fā)現(xiàn)，被動(dòng)提交模式的時(shí)延比主動(dòng)提交模式的時(shí)延要高，這是因?yàn)閿?shù)據(jù)的轉(zhuǎn)發(fā)速度要高于sink的移動(dòng)速度。而Random的時(shí)延又要遠(yuǎn)高于DCSR，這是由于DCSR盡量尋找最短的路徑，路線較為合理，因此時(shí)間較少。需要說明的是，大多數(shù)數(shù)據(jù)采集型應(yīng)用，尤其是非實(shí)時(shí)業(yè)務(wù)，其時(shí)延要求并不高，DCSR還是比較適用的。

圖12 平均時(shí)延

7 結(jié)束語

在數(shù)據(jù)采集型應(yīng)用中采用移動(dòng)sink節(jié)點(diǎn)能夠帶來多方面的好處。它可以提升網(wǎng)絡(luò)的吞吐量，均衡節(jié)點(diǎn)的能量消耗，提高數(shù)據(jù)的采集效率，并且當(dāng)網(wǎng)絡(luò)出現(xiàn)分割時(shí)也能正常工作。本文設(shè)計(jì)的DCSR協(xié)議，較好地體現(xiàn)了這些優(yōu)勢。受到節(jié)點(diǎn)移動(dòng)速度的限制，DCSR協(xié)議在收集數(shù)據(jù)時(shí)會(huì)產(chǎn)生一定的時(shí)延。因此，對于數(shù)據(jù)量較大、時(shí)限要求不高的采集型業(yè)務(wù)，DCSR協(xié)議具有較好的應(yīng)用前景。下一步的研究內(nèi)容是在傳感器節(jié)點(diǎn)上引入數(shù)據(jù)融合機(jī)制，將它與DCSR協(xié)議結(jié)合后，網(wǎng)絡(luò)的性能應(yīng)該會(huì)更好。

[1] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[2] POTDAR V, SHARIF A, CHANG E. Wireless sensor networks: a survey[A]. Proceedings of International Conference on Advanced Information Networking and Applications[C]. Bradford, 2009. 636-641.

[3] SONG G M, ZHOU Y X, DING F, et al. A mobile sensor network system for monitoring of unfriendly environments[J]. Sensors, 2008, 8:7259-7274.

[4] ACHTELIK M, ZHANG T G, KUHNLENZ K, et al. Visual tracking and control of a quadcopter using a stereo camera system and inertial sensors[A]. Proceedings of the International Conference on Mechatronics and Automation[C]. Changchun, China, 2009. 2863-2869.

[5] WANG W, SRINIVASAN V, CHAING K C. Using mobile relays to prolong the lifetime of wireless sensor networks[A]. Proceedings of the 11th Annual International Conference on Mobile Computing and Networking[C]. Cologne, 2005. 270-283.

[6] BI Y Z, SUN L M, MA J, et al. HUMS: an autonomous moving strategy for mobile sinks in data-gathering sensor networks[J]. EURASIP Journal on Wireless Communications and Networking, 2007: 1-15.

[7] XING G L, WANG T, XIE Z H, et al. Rendezvous planning in wireless sensor networks with mobile elements[J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1430-1442.

[8] 郜帥, 張宏科, 徐懷松. Sink 軌跡固定傳感器網(wǎng)絡(luò)的高效數(shù)據(jù)采集機(jī)制[J]. 軟件學(xué)報(bào), 2010, 21(1): 147-162.GAO S, ZHANG H K, XU H S. Efficient data gathering approach in sensor networks with path-fixed sinks[J]. Journal of Software, 2010,21(1): 147-162.

[9] JAIN S, SHAH R C, BORRIELLO G. Exploiting mobility for energy efficient data collection in sensor networks[J]. Mobile Networks and Applications, 2006, 11(3): 327-339.

[10] AKKAYA K, YOUNIS M, BANGAD M. Sink repositioning for enhanced performance in wireless sensor networks[J]. Computer Networks, 2005, 49(4): 512-534.

[11] LUO J, HUBAUX J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[A]. Proceedings of the 24th Annual Conf of the IEEE Computer and Communications Societies[C]. Miami,2005. 1735-1746.

[12] TAN C G, XU K, WANG J X, et al. A sink moving scheme based on local residual energy of nodes in wireless sensor networks[J]. Journal of Central South University of Technology, 2009, 16(2): 265-268.

[13] XIAO J, YAN YP, ZHANG J, et al. A quantum-inspired genetic algorithm for k-means clustering[J]. Expert Systems with Applications,2010, 37(7): 4966-4973.

[14] GU J W, GU M Z, CAO C W, et al. A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem[J]. Computers & Operations Research, 2010,37(5): 927-937.

[15] ZHANG H H, HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Ad Hoc & Sensor Wireless Networks, 2005, 1(1-2): 89-124.

[16] PAOLO S. Topology Control in Wireless Ad Hoc and Sensor Networks[M]. Chichester: John Wiley & Sons Ltd, 2005.

[17] SETHI S, ROUT A, MOHANTA D. Hybrid activities of AODV for wireless ad hoc sensor network[A]. Proceedings of International Conference on Recent Trends in Business Administration and Information[C]. Trivandrum, 2010. 39-44.