張淳

摘要：數(shù)據(jù)采集是無線傳感器網(wǎng)絡(luò)中的重要技術(shù)之一。多跳傳輸算法是傳統(tǒng)的數(shù)據(jù)傳輸算法，但是傳感器需要耗費(fèi)大量能量將數(shù)據(jù)發(fā)送給基站。因此一種應(yīng)用多個(gè)移動(dòng)小車在被監(jiān)測(cè)范圍內(nèi)采集數(shù)據(jù)的算法被提出。首先，被監(jiān)測(cè)范圍被劃分為多個(gè)區(qū)域，其次，對(duì)最小化移動(dòng)小車數(shù)量的問題進(jìn)行建模，然后，提出了一種多移動(dòng)小車的調(diào)度算法。仿真實(shí)驗(yàn)顯示，這種算法能夠有效降低數(shù)據(jù)延遲。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；數(shù)據(jù)采集；數(shù)據(jù)延遲

中圖分類號(hào)： TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2018）15-0055-03

A Data Collection Algorithm in Wireless Sensor Networks Based on Mobile Collectors

ZHANG Chun

（School of Computer Science and Technology， Nanjing University of Posts and Telecommunications， Nanjing210023， China）

Abstract：Data collection is one of the key technology of wireless sensor networks. The multi-hop routing algorithm is the traditional transmission algorithm， but sensors consume much energy sending data to the sink. Therefore， a data collection algorithm using multiple mobile data collectors is proposed. First， the monitoring area is divided into multiple regions. Second， the data collection problem is modeled as minimizing the number of data collectors. Third， a dispatching algorithm for data collectors is proposed. Simulations shows that this algorithm can reduce the data delay effectively.

Key words： wireless sensor networks； data collection； data delay

1 引言

在目標(biāo)跟蹤應(yīng)用中，無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)要把目標(biāo)信息傳遞給基站，基站根據(jù)接收到的信息計(jì)算目標(biāo)的運(yùn)動(dòng)軌跡，并將對(duì)節(jié)點(diǎn)的建議和用戶需求及時(shí)通告給節(jié)點(diǎn)，因此，數(shù)據(jù)采集是目標(biāo)跟蹤中用到的一項(xiàng)關(guān)鍵技術(shù)[1]。多跳傳輸是無線傳感器網(wǎng)絡(luò)中常用的一種路由算法，節(jié)點(diǎn)監(jiān)測(cè)到事件的發(fā)生并產(chǎn)生數(shù)據(jù)包后，需要耗費(fèi)大量能量將數(shù)據(jù)發(fā)送回基站（sink），即控制中心。由于節(jié)點(diǎn)依靠攜帶的電池供電，在很多應(yīng)用環(huán)境中，電池?zé)o法更換，則當(dāng)節(jié)點(diǎn)電量耗盡后，無線傳感器網(wǎng)絡(luò)將會(huì)面臨很多問題，如產(chǎn)生通信空洞、覆蓋空洞等；另外，越靠近sink的節(jié)點(diǎn)，能量消耗越多，這就造成了網(wǎng)絡(luò)內(nèi)能耗不均衡，因此，在無線傳感器網(wǎng)絡(luò)中引入移動(dòng)小車是十分必要的；應(yīng)用移動(dòng)小車還可以提高數(shù)據(jù)傳輸?shù)馁|(zhì)量，數(shù)據(jù)包的接收率會(huì)受到無線信道的擁塞程度和傳輸路徑長(zhǎng)短的影響，無線信道越繁忙、數(shù)據(jù)傳輸路徑越長(zhǎng)，產(chǎn)生碰撞的概率越高，數(shù)據(jù)包丟包概率越高，因此，應(yīng)用移動(dòng)小車還可以降低丟包概率。雖然應(yīng)用移動(dòng)小車有很多優(yōu)點(diǎn)，但是會(huì)產(chǎn)生數(shù)據(jù)延遲。

因此，本文需要解決的問題是：引入多個(gè)移動(dòng)小車在被監(jiān)測(cè)區(qū)域中采集數(shù)據(jù)，降低無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)延遲。數(shù)據(jù)延遲指的是，傳感器節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包的時(shí)間和基站接收到數(shù)據(jù)包之間的時(shí)間差。

近年來，越來越多的文獻(xiàn)中引入移動(dòng)的概念來解決數(shù)據(jù)采集問題。文獻(xiàn)[2]提出了移動(dòng)基站的幾種移動(dòng)方式，由于移動(dòng)基站不停地在運(yùn)動(dòng)，因此它的一跳鄰居節(jié)點(diǎn)也不斷在變化，避免了一部分傳感器消耗能量過多，一部分傳感器空閑時(shí)間多的問題。文獻(xiàn)[3]假設(shè)每個(gè)傳感器以一定的速率產(chǎn)生數(shù)據(jù)，且移動(dòng)小車需要運(yùn)動(dòng)到每個(gè)傳感器附近去采集數(shù)據(jù)，目標(biāo)是為每個(gè)移動(dòng)小車規(guī)劃一條路徑，這條路徑需要經(jīng)過網(wǎng)絡(luò)內(nèi)的所有傳感器。文獻(xiàn)[4]將移動(dòng)小車的移動(dòng)問題建模成旅行商問題。文獻(xiàn)[5]對(duì)移動(dòng)小車的各種問題進(jìn)行了綜述，指出了應(yīng)用移動(dòng)小車的優(yōu)點(diǎn)和缺點(diǎn)。

2 多移動(dòng)小車數(shù)據(jù)采集方法

2.1 移動(dòng)小車的數(shù)量最小化問題

因?yàn)楸槐O(jiān)測(cè)范圍較大，因此首先把被監(jiān)測(cè)范圍劃分成幾個(gè)區(qū)域。在很多文獻(xiàn)[6，7，8]中已對(duì)分簇算法進(jìn)行了研究，因此分簇算法不是本文研究的重點(diǎn)。本文中應(yīng)用文獻(xiàn)[6]中提出的分簇算法，將被監(jiān)測(cè)范圍劃分成若干個(gè)區(qū)域，每個(gè)區(qū)域由二級(jí)簇首、一級(jí)簇首和普通簇成員構(gòu)成。

傳感器節(jié)點(diǎn)的存儲(chǔ)能力是有限的，傳感器節(jié)點(diǎn)能夠緩存數(shù)據(jù)的時(shí)間長(zhǎng)度[tst]取決于節(jié)點(diǎn)的存儲(chǔ)能力和數(shù)據(jù)采集速率，假設(shè)節(jié)點(diǎn)能夠存儲(chǔ)[tst]秒內(nèi)收集的數(shù)據(jù)，為了避免節(jié)點(diǎn)采集到的數(shù)據(jù)包丟失，當(dāng)sink接收到節(jié)點(diǎn)發(fā)送的請(qǐng)求信息后，移動(dòng)小車要在[tst]秒內(nèi)將節(jié)點(diǎn)的數(shù)據(jù)包取走。當(dāng)無線傳感器網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的數(shù)目較多時(shí)，sink可能在短時(shí)間內(nèi)收到很多節(jié)點(diǎn)的請(qǐng)求信息，單個(gè)移動(dòng)小車的運(yùn)動(dòng)速度有限，需要很長(zhǎng)時(shí)間才能訪問完所有需要訪問的節(jié)點(diǎn)，這個(gè)時(shí)間長(zhǎng)度可能已經(jīng)遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)能夠緩存數(shù)據(jù)的時(shí)間長(zhǎng)度，為了避免數(shù)據(jù)溢出，只有同時(shí)應(yīng)用多個(gè)移動(dòng)小車才能保證節(jié)點(diǎn)采集到的數(shù)據(jù)不會(huì)因?yàn)閿?shù)據(jù)溢出而丟失。以下給出幾個(gè)定義。

定義1 請(qǐng)求序列集：傳感器節(jié)點(diǎn)為事件觸發(fā)型，節(jié)點(diǎn)監(jiān)測(cè)到事件的發(fā)生后，產(chǎn)生一個(gè)事件數(shù)據(jù)包，然后發(fā)送給簇頭節(jié)點(diǎn)，簇頭收到事件數(shù)據(jù)包后，會(huì)發(fā)送一個(gè)請(qǐng)求信息給sink節(jié)點(diǎn)，請(qǐng)求sink派遣移動(dòng)小車來采集數(shù)據(jù)包，請(qǐng)求信息中包含了監(jiān)測(cè)到事件的時(shí)間[T]，由于網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)量較多，sink在短時(shí)間內(nèi)可能接收到很多簇頭節(jié)點(diǎn)發(fā)送來的請(qǐng)求信息，這些請(qǐng)求信息構(gòu)成了一個(gè)集合[request]，[request=ΨT1，ΨT2，...，ΨTk]，其中[ΨTk]代表了儲(chǔ)存有時(shí)間[Tk]監(jiān)測(cè)到的事件數(shù)據(jù)包的簇頭的集合，且[T1

定義2 移動(dòng)小車的數(shù)據(jù)采集周期：當(dāng)sink接收到簇頭發(fā)送的請(qǐng)求信息后，這些請(qǐng)求信息形成一個(gè)請(qǐng)求序列集，sink查詢請(qǐng)求序列集，根據(jù)事件數(shù)據(jù)包產(chǎn)生的時(shí)間和位置這兩個(gè)因素，調(diào)度多個(gè)移動(dòng)小車去采集數(shù)據(jù)。用[A=A1，A2，...，An]表示移動(dòng)小車的集合，[KnT]表示在[T]時(shí)刻sink分配給[An]的需要去訪問的簇頭集合，[KnT?Ψl]或[KnT?（Ψ'l?...?Ψ'm）]，其中[Ψ'l?Ψl]，[Ψ'm?Ψm]，[l]、[m]表示不同的時(shí)間值，[An]當(dāng)前所在位置作為它的出發(fā)點(diǎn)。則[An]從出發(fā)點(diǎn)出發(fā)，訪問完[KnT]內(nèi)的節(jié)點(diǎn)后，將采集到的數(shù)據(jù)包發(fā)送給sink，這個(gè)過程稱為[An]的一個(gè)數(shù)據(jù)采集周期；然后，[An]進(jìn)入“等待”狀態(tài)，當(dāng)接收到sink發(fā)送過來的任務(wù)后，進(jìn)入下一個(gè)數(shù)據(jù)采集周期。

定義3 采集路徑：移動(dòng)小車的采集路徑是指，對(duì)于任意一個(gè)移動(dòng)小車[An]，設(shè)在一個(gè)數(shù)據(jù)采集周期內(nèi)需要訪問的簇頭集合為[KnT]，[KnT=Si，Sj，...，Sl，Sm]，[Si]、[Sj]、…、[Sl]、[Sm]為 [An]需要依次訪問的節(jié)點(diǎn)序列，[P=pi，pj，...，pl，pm]為[An]對(duì)[KnT]的訪問點(diǎn)序列，[pst]為[An]的出發(fā)點(diǎn)，則依次連接[pst]和[P]集合內(nèi)訪問點(diǎn)的直線被稱為[An]在一個(gè)數(shù)據(jù)采集周期的采集路徑。

由于在同一時(shí)間，網(wǎng)絡(luò)中可能有多個(gè)節(jié)點(diǎn)同時(shí)監(jiān)測(cè)到事件的發(fā)生，因此sink在短時(shí)間內(nèi)可能收集到多個(gè)請(qǐng)求信息，設(shè)sink每隔一段時(shí)間[t]查詢一次請(qǐng)求序列[request]，然后派遣移動(dòng)小車去訪問請(qǐng)求序列中的節(jié)點(diǎn)，其中[t

[request=rga，rgb，...，rge] （1）

[RG1?RG2?...?RGi=rga，rgb，...，rge] （2） [RG1?RG2?...?RGi=?] （3）

Object [MinimizeRG]

S.t. [Dj

2.2 移動(dòng)小車的分配問題

根據(jù)1.1節(jié)中給被監(jiān)測(cè)范圍進(jìn)行分區(qū)的方法，將被監(jiān)測(cè)范圍劃分為多個(gè)區(qū)域。本節(jié)將給出為移動(dòng)小車分配區(qū)域去采集數(shù)據(jù)的方法。

初始時(shí)刻，設(shè)為[t1]，經(jīng)過一段時(shí)間[t]后，sink查詢[[t1，t1+t]]時(shí)間段內(nèi)的請(qǐng)求序列[request（t1，t1+t）]，用式（5）表示，其中[rgTn]表示在[T]時(shí)刻標(biāo)識(shí)號(hào)為[n]的小區(qū)域內(nèi)有需要被采集的節(jié)點(diǎn)，因?yàn)楣?jié)點(diǎn)的數(shù)據(jù)包都發(fā)送給一級(jí)簇頭，因此[rgTn]保存的節(jié)點(diǎn)均為一級(jí)簇頭。

[request（t1，t1+t）=Ψth，Ψtk，...，Ψtm=rgtha，rgthc，...，rgthe，rgtkd，rgtkk，...，rgtkf，...，rgtmh，rgtmj，...，rgtmm] （5）

設(shè)[t1]時(shí)刻多個(gè)移動(dòng)小車都位于sink附近，首先考慮[th]時(shí)刻監(jiān)測(cè)到事件的節(jié)點(diǎn)，包括以下兩種情況：

（1）[th]時(shí)刻僅標(biāo)識(shí)號(hào)為[a]的區(qū)域內(nèi)的節(jié)點(diǎn)監(jiān)測(cè)到事件

對(duì)于任意一個(gè)空閑的移動(dòng)小車（簡(jiǎn)稱為[MDC]），假設(shè)為[MDCa]，sink計(jì)算[MDCa]訪問[rgtha]中的一級(jí)簇頭要行進(jìn)的距離[Dtha]，考慮以下三種不同的情況：

1）[Dtha

尋找[rgtkd，rgtkk，...，rgtkf]內(nèi)距離[rga]最近的區(qū)域（定義任意兩個(gè)區(qū)域[rgn]、[rgm]之間的距離為[rgn]和[rgm]的二級(jí)簇頭之間的距離），假設(shè)為[rgd]，計(jì)算[Dtkd]，如果滿足式（6），其中[d（a，d）]為[MDCa]從[rga]移動(dòng)到[rgd]要經(jīng)過的距離，則[RG1={rgtha}]，其中[RG1]為sink得到的派遣[MDCa]去訪問的節(jié)點(diǎn)集合；如果滿足式（7），則[RG1={rgtha，rgtkd}]；如果滿足式（8），則按照事件發(fā)生的先后順序，繼續(xù)尋找和當(dāng)前區(qū)域[rgd]距離最近的區(qū)域，作為下一步要訪問的區(qū)域，并計(jì)算[MDCa]的行進(jìn)要經(jīng)過的距離，重復(fù)此過程，直到行進(jìn)距離[D>vtst]，然后把[D>vtst]之前計(jì)算得到的[MDCa]要經(jīng)過的區(qū)域放入[RG1]中；

[Dtha+Dtkd+d（a，d）>vtst] （6）

[Dtha+Dtkd+d（a，d）=vtst] （7）

[Dtha+Dtkd+d（a，d）

2）[Dtha=vtst]

在這種情況下，[RG1={rgtha}]；

3）[Dtha>vtst]

這種情況說明[MDCa]訪問[rgtha]內(nèi)所有節(jié)點(diǎn)經(jīng)過的距離大于[vtst]，則根據(jù)路徑規(guī)劃得到的訪問[rgtha]內(nèi)節(jié)點(diǎn)的順序，計(jì)算[MDCa]訪問這些節(jié)點(diǎn)行進(jìn)的距離[D]，直到[D>vtst]，然后將[D>vtst]之前[MDCa]訪問的區(qū)域放入[RG1]中；

（2）[th]時(shí)刻監(jiān)測(cè)到事件的節(jié)點(diǎn)分布在多個(gè)區(qū)域內(nèi)

sink對(duì)節(jié)點(diǎn)的數(shù)據(jù)采集采用由近及遠(yuǎn)的方式，首先尋找[{rgtha，rgthc，...，rgthe}]內(nèi)距離[MDCa]最近的區(qū)域（本節(jié)中，定義sink和任意區(qū)域[rgn]的距離為sink和[rgn]中二級(jí)簇頭的距離），假設(shè)為[rgc]，sink計(jì)算[MDCa]訪問[rgthc]中的一級(jí)簇頭要行進(jìn)的距離[Dthc]，然后根據(jù)[Dthc]和[vtst]之間的關(guān)系，根據(jù)第（1）種情況中所采取的方法，依次類推，計(jì)算得到[RG1]；

通過以上步驟，得到了一條訪問路徑[RG1]，sink派遣[MDCa]去訪問[RG1]中的節(jié)點(diǎn)；然后，sink查詢[request（t1，t1+t）]，如果除了[RG1]中的節(jié)點(diǎn)外，還有未被訪問的節(jié)點(diǎn)，則sink為當(dāng)前空閑的任意移動(dòng)小車，假設(shè)為[MDCb]，應(yīng)用以上計(jì)算[RG1]的方法，計(jì)算得到第二條訪問路徑[RG2]，派遣[MDCb]去訪問；再次查詢[request（t1，t1+t）]，直到[request（t1，t1+t）]中的節(jié)點(diǎn)全部被移動(dòng)小車訪問。

移動(dòng)小車采集完網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)后，要及時(shí)把數(shù)據(jù)發(fā)送給sink進(jìn)行分析、處理，小車移動(dòng)的位移矢量用[d→=（d，θ）]表示，小車將采集到的數(shù)據(jù)發(fā)送給sink后，就進(jìn)入“等待”狀態(tài)，等待sink再次發(fā)出任務(wù)指令。

[d→=（（dms-Rm），θ）ifdms>Rm0ifdms≤Rm] （9）

其中，[d]表示移動(dòng)的長(zhǎng)度，[θ]表示移動(dòng)的角度，為小車和sink之間的連線與水平坐標(biāo)之間的夾角，[dms]為小車的當(dāng)前位置與sink之間的距離，[Rm]表示小車的通信距離。

3 仿真實(shí)驗(yàn)

在本節(jié)的仿真實(shí)驗(yàn)中，100個(gè)傳感器節(jié)點(diǎn)隨機(jī)地分布在一個(gè)正方形區(qū)域中，sink的射頻帶寬為1Mbps，節(jié)點(diǎn)的感知距離為20米，移動(dòng)小車的通信范圍為35米，移動(dòng)小車的速度為5米/秒，事件數(shù)據(jù)包大小為100bytes。本文提出的算法被命名為MDDC，文獻(xiàn)[9]中的算法被命名為OMET算法，被用來與本文的算法進(jìn)行比較。

圖1顯示的是數(shù)據(jù)延遲和移動(dòng)小車的數(shù)量的關(guān)系圖。從圖中可以看出，MDDC算法的數(shù)據(jù)延遲小于OMET的數(shù)據(jù)延遲，且隨著移動(dòng)小車數(shù)量的增加，MDDC算法的曲線下降趨勢(shì)比OMET明顯。這是由于，MDDC算法中，多個(gè)區(qū)域中的數(shù)據(jù)包由多個(gè)移動(dòng)小車進(jìn)行采集，所以隨著小車數(shù)量的增加，數(shù)據(jù)延遲明顯降低。

圖2顯示的是小車平均移動(dòng)路徑長(zhǎng)度和小車數(shù)量的關(guān)系圖。從圖中可以看出，應(yīng)用MDDC算法，移動(dòng)小車的移動(dòng)距離要小于OMET算法。且隨著小車數(shù)量的增加，小車的平均移動(dòng)距離呈下降趨勢(shì)。

圖3顯示的是小車平均移動(dòng)路徑長(zhǎng)度和小車數(shù)量的關(guān)系圖。從圖中可以看出，隨著被監(jiān)測(cè)范圍的增大，MDDC算法和OMET算法的平均數(shù)據(jù)延遲增加，且兩種算法之間的差距呈增大趨勢(shì)。

4 結(jié)束語(yǔ)

本文提出了以區(qū)域?yàn)閱挝粸槎鄠€(gè)移動(dòng)小車分配采集任務(wù)的思路，并以節(jié)點(diǎn)的最大存儲(chǔ)量作為約束條件，對(duì)移動(dòng)小車數(shù)量最小化的問題進(jìn)行建模，從而提出一種啟發(fā)式的移動(dòng)小車調(diào)度算法；通過仿真實(shí)驗(yàn)證明，應(yīng)用這種數(shù)據(jù)采集方法，能有效降低無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)延遲。

參考文獻(xiàn)：

[1] 黨小超， 楊冬冬， 郝占軍. 基于虛擬力的傳感器網(wǎng)絡(luò)三維覆蓋算法[J]. 計(jì)算機(jī)應(yīng)用， 2015， 35（11）， 3021–3025.

[2] Chatzigiannakis I， Kinalis A， Nikoletseas S. Sink Mobility Protocols for Data Collection in Wireless Sensor Networks [C]//Proceedings of the International Workshop on Mobility Management and Wireless Access： Torremolinos， Malaga， Spain， October 2006： 52-59.

[3] Somasundara A A， Ramamoorthy A and Srivastava M B. Mobile Element Scheduling with Dynamic Deadlines [J]. IEEE Trans. Mobile Computing， 2007， 6（4）： 395-410.

[4] Kumar A K， Sivalingam K M. Energy-Efficient Mobile Data Collection in Wireless Sensor Networks with Delay Reduction Using Wireless Communication [C]//Proceedings of the 2th International Conference on COMSNETS， Bangalore， Jan 2010： 1-10.

[5] Xu L， Amiya N， Lvan S. Exploiting Actuator Mobility for Energy-Efficient Data Collection in Delay-Tolerant Wireless Sensor Networks [C]// Proceedings of the 5th International Conference on Network and Services， Valencia， April 2009： 216-221.

[6] 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： 328-344.

[7] Yu J， Chong P. A survey of clustering schemes for mobile Ad hoc Networks[J]. IEEE Communications Surveys， 2005， 7（1）： 32-48.

[8] Israr N， Awan I. Coverage based inter cluster communication for load balancing in heterogeneous wireless sensor networks[J]. Telecommunication Systems， 2008， 38： 121-132.

[9] He Liang， Xu Jingdong， Yu Yuntao. Optimize multiple mobile elements touring in wireless sensor networks[C] //Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications， Chengdu， August 10-12， 2009： 317-323.