胡小平， 楊向萍

(東華大學(xué) 機(jī)械工程學(xué)院，上海 201620)

?

可充電WSNs中基于效用最大化的數(shù)據(jù)收集方案

胡小平， 楊向萍

(東華大學(xué) 機(jī)械工程學(xué)院，上海 201620)

利用無(wú)人機(jī)(UAV)到達(dá)傳感器集群位置，然后采集數(shù)據(jù)并對(duì)相應(yīng)集群的傳感器充電。定義了數(shù)據(jù)收集效用函數(shù)，將數(shù)據(jù)收集問(wèn)題描述為一種以數(shù)據(jù)收集效用最大化為目標(biāo)的優(yōu)化問(wèn)題，并提出單邊偏好匹配算法和基于雙邊偏好匹配的貪婪算法來(lái)解決上述問(wèn)題。仿真實(shí)驗(yàn)表明:利用本文貪婪算法確定的UAV和傳感器集群間的匹配關(guān)系可生成使數(shù)據(jù)收集效用最大化的最優(yōu)解，且可實(shí)現(xiàn)傳感器數(shù)據(jù)的高效收集。

無(wú)線傳感器網(wǎng)絡(luò)； 數(shù)據(jù)收集； 效用； 單邊匹配； 貪婪算法； 最優(yōu)解

0 引 言

在過(guò)去10年間，無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)獲得了人們的廣泛關(guān)注[1]。數(shù)據(jù)處理和計(jì)算技術(shù)的進(jìn)步，使傳感器可以測(cè)量多種領(lǐng)域[2]中的數(shù)據(jù)(比如溫度、壓力、光照、濕度及紅外線等)。但是電池技術(shù)進(jìn)展緩慢，使電量有限的傳感器受到嚴(yán)重的能量約束。此外，人們還希望利用WSNs對(duì)廣大區(qū)域?qū)崿F(xiàn)無(wú)人值守式觀察。雖然傳感器部署簡(jiǎn)單，但是使WSNs保持長(zhǎng)時(shí)間運(yùn)行，在大面積部署區(qū)域尤其是惡劣環(huán)境條件(比如高溫沙漠、密林、雪山)下實(shí)現(xiàn)傳感數(shù)據(jù)的高效收集，難度很大[3]。

為了避免傳感器的能量消耗完，人們已經(jīng)在之前文獻(xiàn)中提出了多種能量節(jié)約[4]、環(huán)境能量利用[5]和增量部署算法[6]。然而，能量節(jié)約算法只能延緩能量被消耗的步伐，無(wú)法補(bǔ)充能量。對(duì)太陽(yáng)能、風(fēng)能和振動(dòng)能等環(huán)境能量進(jìn)行利用時(shí)，會(huì)受到這些能量可用性的約束，且這些能量的可用性往往不受人力控制。此外，部署的傳感器節(jié)點(diǎn)可能會(huì)污染環(huán)境，因此增量部署算法對(duì)環(huán)境不夠友好。

然而，無(wú)線能量傳輸技術(shù)在近期取得突破，為WSNs的傳感器能量補(bǔ)充提供了一種有力途徑。美國(guó)國(guó)家航空航天局(NASA)的電磁輻射實(shí)驗(yàn)[7]證明了能量遠(yuǎn)距離高效傳輸?shù)目尚行裕涸贕oldstone網(wǎng)絡(luò)實(shí)驗(yàn)中，NASA在1.5 km的距離上傳輸了34 000 W的能量，效率達(dá)到82 %。文獻(xiàn)[8]利用一個(gè)無(wú)人機(jī)(unmanned aerial vehicle,UAV)攜帶充電設(shè)備，周期性地訪問(wèn)傳感器集群，對(duì)傳感器實(shí)施無(wú)線充電，進(jìn)而使WSNs永久工作。文獻(xiàn)[9]設(shè)計(jì)了一種移動(dòng)式無(wú)線充電車，并通過(guò)實(shí)驗(yàn)驗(yàn)證了無(wú)線充電車在為WSNs補(bǔ)充能量方面的性能。雖然在這些創(chuàng)新性研究中，傳感器能量得以補(bǔ)充，但WSNs將數(shù)據(jù)以多跳方式從數(shù)據(jù)源向Sink節(jié)點(diǎn)傳輸時(shí)仍然浪費(fèi)了大量能量。此外，對(duì)于部署在惡劣環(huán)境中的傳感器集群，無(wú)線充電設(shè)備到達(dá)這些區(qū)域并收集這些感應(yīng)數(shù)據(jù)將會(huì)消耗大量時(shí)間和成本。

針對(duì)以上不足，本文利用無(wú)人機(jī)攜帶無(wú)線充電器，提出一種基于效用最大化的數(shù)據(jù)收集方案，并通過(guò)仿真驗(yàn)證了該方案的有效性。

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

(1)

假設(shè)UAi及其匹配SCj間的距離為dij，UAi的速度為vi?？紤]到UAV在被選傳感器集群和Sink節(jié)點(diǎn)間的往返行程，UAV航行時(shí)間可表示為

(2)

如果一個(gè)UAV與多個(gè)集群相匹配，本文則假設(shè)UAV必須逐個(gè)從這些集群中收集數(shù)據(jù)。從當(dāng)前集群中收集完數(shù)據(jù)后，UAV必須回到Sink節(jié)點(diǎn)處傳輸數(shù)據(jù)，然后再飛往下一個(gè)集群。

根據(jù)上節(jié)所示的網(wǎng)絡(luò)模型，UAV的效用函數(shù)定義為

(3)

為了提高效用，UAV需要考慮UAi和SCj間的距離，SCjSink節(jié)點(diǎn)處匯聚的數(shù)據(jù)量，以及SCj中傳感器的剩余能量。另外，設(shè)x表示N×M矩陣，該矩陣的第(i,j)個(gè)元素為xij={0,1}，表示本文中的匹配關(guān)系。如果xij=1，則第i個(gè)UAV與第j個(gè)集群相匹配;否則，它們不匹配。因?yàn)槊總€(gè)集群只能與一個(gè)UAV匹配，所以,本文有如下約束

(4)

為了實(shí)現(xiàn)感知數(shù)據(jù)的高效收集，本文試圖確定傳感器集群和UAV間的最優(yōu)匹配對(duì)，以便使集群到UAV的數(shù)據(jù)傳遞速率最大化，同時(shí)保證這些集群中的傳感器得到能量補(bǔ)充。因此，無(wú)線可充電傳感器集群的高效數(shù)據(jù)收集問(wèn)題可表示如下

(5)

2 本文算法

2.1 匹配定義

設(shè)有一個(gè)實(shí)例I表示一組UAVN={UA1,…,UAn}及一組傳感器集群M={SC1,…,SCm}。實(shí)例I中的主體是M∪N中的UAV和傳感器集群?？山邮艿腢AV—SC匹配對(duì)為集合ε?N×M。每個(gè)UAVUAi∈N有一組可接受的傳感器集群A(UAi)，其中A(UAi)={SCj∈M:(UAi,SCj)∈ε}。類似地，每個(gè)集群SCj∈M有一個(gè)可接受的申請(qǐng)人A(SCj)，其中,A(SCj)={UAi∈N:(UAi,SCj)∈ε}。本文將UAi和SCj的匹配關(guān)系定義如下：

定義1 匹配關(guān)系Φ為如下函數(shù)：Φ(UAi)∈M∪{?}，且|Φ(UAi)|∈{0,1,…};Φ(SCj)∈N∪{?},|Φ(SCj)|∈{0,1}，其中,Φ(UAi)=SCj且Φ(SCj)=UAi(i∈N,j∈M)。

在匹配理論中，本文中的主體(即UAV和SC)，需要一個(gè)偏好列表才能開(kāi)始匹配過(guò)程。因此，本文在選擇傳感器集群進(jìn)行能量補(bǔ)充和數(shù)據(jù)收集前，要求每個(gè)UAi根據(jù)自己相對(duì)所有集群的效用，形成一個(gè)降序排列的偏好列表。

2.2 單邊偏好匹配算法

單邊偏好匹配算法分為兩步:1)計(jì)算UAV的效用函數(shù);然后，構(gòu)建降序排列的偏好列表UALISTi;同時(shí)構(gòu)建一組未匹配的傳感器集群UNMATCH。2)根據(jù)偏好列表UALISTi構(gòu)建匹配關(guān)系。UAi向UALIST中層次最高的未匹配集群SCj做出申請(qǐng)，并將SCj從UNMATCH中移除。如果UNMATCH≠?，則算法回到第2步開(kāi)始時(shí)。算法不斷進(jìn)行匹配過(guò)程的迭代，直到UNMATCH為空集。

算法1：?jiǎn)芜吰ヅ渌惴?/p>

1)初始化

構(gòu)建未被匹配的傳感器集群列表UNMATCH;

2)匹配

for eachUAi,i∈Ndo

向之前從未拒絕過(guò)自己的最高等級(jí)SCj提出申請(qǐng)；

ifSCj∈UNMATCHthen

保存匹配對(duì)(SCj,UAj)；

將SCj從UNMATCH中刪除；

else

拒絕做出申請(qǐng)的UAi;

end if

end for

ifUNMATCH≠? then

跳到第2步；

else

跳到第3步；

end if

3)算法結(jié)束

2.3 貪婪算法：雙邊偏好匹配

(6)

傳感器集群也可以構(gòu)建它們自己的偏好列表。然后，每個(gè)UAi∈N或每個(gè)SCi∈M均有一個(gè)按嚴(yán)格次序排列且互不相同的偏好列表。文獻(xiàn)[10]提出一種可以始終找到穩(wěn)定性匹配關(guān)系Gale—Shapley算法。本文以該算法為基礎(chǔ)提出一種基于雙邊偏好匹配的貪婪算法，如算法2所示。

算法2：貪婪算法(雙邊偏好匹配)

1)初始化

構(gòu)建未被匹配的集群組成的集合UNMATCH;

2)匹配

for eachUAi,i∈Ndo

向之前從未拒絕過(guò)自己的最高等級(jí)SCj做出申請(qǐng)；

ifSCj∈UNMATCHthen

保留匹配對(duì)(SCj,UAi);

將SCj從UNMATCH列表中刪除；

else

比較新UAi′的等級(jí)Rank(i′)和SCLISTj中指定UAi的等級(jí)Rank(i)；

ifRank(i)>Rank(i′)then

拒絕新申請(qǐng)的UAi′;

else

保留新的匹配對(duì)(SCj,UAi′);

拒絕先前做出申請(qǐng)的UAi;

end if

end if

end for

ifUNMATCH≠? then

跳到第2步；

end of

ifUNMATCH=?且部分UAi沒(méi)有結(jié)束對(duì)所有集群的申請(qǐng)then

跳到第2步；

end if

3)算法結(jié)束

3 性能評(píng)估

3.1 仿真配置

3.2 結(jié)果和分析

圖1給出了UAV數(shù)量固定時(shí)的仿真結(jié)果，此時(shí)傳感器集群數(shù)量為25～40個(gè)，傳感器集群分別部署于網(wǎng)格拓?fù)浜碗S機(jī)拓?fù)浣Y(jié)構(gòu)上。從圖1中可以發(fā)現(xiàn)，本文提出的貪婪算法的性能和最優(yōu)匹配的性能一樣，而單邊匹配算法的性能遠(yuǎn)優(yōu)于UAi(i∈N)和SCj(j∈M)的隨機(jī)匹配算法。因?yàn)閱芜吰ヅ渌惴紤]了UAV的偏好列表，每個(gè)UAi(i∈N)有機(jī)會(huì)向其UALISTi偏好列表中的最高級(jí)別SCj做出申請(qǐng)，所以,單邊匹配算法的性能優(yōu)于隨機(jī)匹配算法。此外，貪婪算法的性能優(yōu)于單邊算法。在貪婪算法中，集群在構(gòu)建偏好列表時(shí)的效用函數(shù)與UAV進(jìn)行決策時(shí)的效用函數(shù)相同。SCj可拒絕向其做出申請(qǐng)的UAi，選擇可顯著提升系統(tǒng)效用的更為合適的UAV。

圖1 不同算法的性能比較Fig 1 Performance comparison of different algorithms

圖2給出了系統(tǒng)效用隨網(wǎng)絡(luò)規(guī)模的變化關(guān)系。當(dāng)網(wǎng)絡(luò)規(guī)模增加時(shí)，系統(tǒng)效用增加。此外，當(dāng)網(wǎng)絡(luò)規(guī)模增加時(shí)，貪婪算法與單邊算法及隨機(jī)匹配算法間的性能差異增加。這表明，當(dāng)UAV的數(shù)量和位置固定時(shí)，相比于單邊匹配算法和隨機(jī)算法，本文貪婪算法更適用于大規(guī)模WSNs。

圖2 系統(tǒng)效用隨網(wǎng)絡(luò)規(guī)模的變化情況Fig 2 System utilities varies with network scale

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

本文研究了如何使用UAV來(lái)高效收集部署于惡劣環(huán)境中的無(wú)線可充電傳感器集群的感應(yīng)數(shù)據(jù)。通過(guò)考慮無(wú)線能量傳輸?shù)奶攸c(diǎn)，將高效數(shù)據(jù)收集問(wèn)題描述為多種約束條件下的優(yōu)化問(wèn)題。為了使上述問(wèn)題中的系統(tǒng)效用最大，文中提出兩種基于匹配理論的分布式算法。仿真實(shí)驗(yàn)結(jié)果表明:本文算法可實(shí)現(xiàn)感應(yīng)數(shù)據(jù)的高效收集，同時(shí)可對(duì)惡劣環(huán)境中的傳感器集群充電。

[1] 彭珍瑞,李 輝,董海棠,等.基于和聲搜索的低延遲和低能耗無(wú)線傳感器網(wǎng)絡(luò)[J].傳感器與微系統(tǒng),2015,34(1):36-39.

[2] 吳騰飛,熊慶國(guó),李文翔,等.方格拓?fù)錈o(wú)線傳感器網(wǎng)絡(luò)源路由策略的能耗分析[J].傳感器與微系統(tǒng),2014,33(10):36-39.

[3]ZhaoM,LiJ,YangY.Aframeworkofjointmobileenergyreple-nishmentanddatagatheringinwirelessrechargeablesensornetworks[J].IEEETransactionsonMobileComputing,2014,13(12):2689-2705.

[4]BouabdallahF,BouabdallahN,BoutabaR.Cross-layerdesignforenergyconservationinwirelesssensornetworks[C]∥IEEEInternationalConferenceonCommunications(ICC),Dresden,Germany:IEEE,2009:1-6.

[5]ParkC,ChouPH.Ambimax:Autonomousenergyharvestingplatformformulti-supplywirelesssensornodes[C]∥2012 9thAn-nualIEEECommunicationsSocietyonSensorandAdHocCommunicationsandNetworks(SECON),Seoul,Korea:IEEE,2012:168-177.

[6]PengY,LiZ,ZhangW,etal.Prolongingsensornetworklifetimethroughwirelesscharging[C]∥2010IEEE31stReal-TimeSystemsSymposium(RTSS),Rome,Italy:IEEE,2010:129-139.

[7]WangR,YeD,DongS,etal.Optimalmatchedrectifyingsurfaceforspacesolarpowersatelliteapplications[J].IEEETransactionsonMicrowaveTheoryandTechniques,2014,62(4):1080-1089.

[8]XieL,ShiY,HouYT,etal.Makingsensornetworksimmortal:Anenergy-renewalapproachwithwirelesspowertransfer[J].IEEE/ACMTransactionsonNetworking(TON),2012,20(6):1748-1761.

[9]ShiY,XieL,HouYT,etal.Onrenewablesensornetworkswithwirelessenergytransfer[C]∥2011ProceedingsoftheIEEEINFOCOM,Shanghai,China:IEEE,2011:1350-1358.

[10]GaleD,ShapleyLS.Collegeadmissionsandthestabilityofmarriage[J].TheAmericanMathematicalMonthly,2013,120(5):386-391.

Data gathering scheme based on utility maximization in rechargeable WSNs

HU Xiao-ping, YANG Xiang-ping

(School of Mechanical Engineering,Donghua University,Shanghai 201620,China)

Unmanned aerial vehicles(UAV) is employed to travel to the sites of sensor clusters,collect data,and recharge the sensors in corresponding clusters.Define utility function of data collection,formulate the data collection problem into optimization problem with objective of maximizing data collection utility,and one side p

matching algorithm and greedy algorithm based on two-side preferences matching are proposed to solve the above problems.Simulation experiments show that the matching between UAVs and SCs by the proposed greedy algorithm can yield the optimal solution in terms of data collection utility,and the data of sensor can be efficiently collected.

wireless sensor networks(WSNs); data gathering; utility; one side matching; greedy algorithm; optimal solution

2015—11—09

10.13873/J.1000—9787(2016)10—0052—04

TP 393

A

1000—9787(2016)10—0052—04

胡小平(1989-)，男，四川瀘州人，碩士研究生,主要研究方向?yàn)闊o(wú)線傳感網(wǎng)、機(jī)電一體化。