可充電WSNs中基于效用最大化的數據收集方案

胡小平， 楊向萍

(東華大學 機械工程學院，上海 201620)

?

可充電WSNs中基于效用最大化的數據收集方案

胡小平， 楊向萍

(東華大學 機械工程學院，上海 201620)

利用無人機(UAV)到達傳感器集群位置，然后采集數據并對相應集群的傳感器充電。定義了數據收集效用函數，將數據收集問題描述為一種以數據收集效用最大化為目標的優化問題，并提出單邊偏好匹配算法和基于雙邊偏好匹配的貪婪算法來解決上述問題。仿真實驗表明:利用本文貪婪算法確定的UAV和傳感器集群間的匹配關系可生成使數據收集效用最大化的最優解，且可實現傳感器數據的高效收集。

無線傳感器網絡； 數據收集； 效用； 單邊匹配； 貪婪算法； 最優解

0 引 言

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

為了避免傳感器的能量消耗完，人們已經在之前文獻中提出了多種能量節約[4]、環境能量利用[5]和增量部署算法[6]。然而，能量節約算法只能延緩能量被消耗的步伐，無法補充能量。對太陽能、風能和振動能等環境能量進行利用時，會受到這些能量可用性的約束，且這些能量的可用性往往不受人力控制。此外，部署的傳感器節點可能會污染環境，因此增量部署算法對環境不夠友好。

然而，無線能量傳輸技術在近期取得突破，為WSNs的傳感器能量補充提供了一種有力途徑。美國國家航空航天局(NASA)的電磁輻射實驗[7]證明了能量遠距離高效傳輸的可行性：在Goldstone網絡實驗中，NASA在1.5 km的距離上傳輸了34 000 W的能量，效率達到82 %。文獻[8]利用一個無人機(unmanned aerial vehicle,UAV)攜帶充電設備，周期性地訪問傳感器集群，對傳感器實施無線充電，進而使WSNs永久工作。文獻[9]設計了一種移動式無線充電車，并通過實驗驗證了無線充電車在為WSNs補充能量方面的性能。雖然在這些創新性研究中，傳感器能量得以補充，但WSNs將數據以多跳方式從數據源向Sink節點傳輸時仍然浪費了大量能量。此外，對于部署在惡劣環境中的傳感器集群，無線充電設備到達這些區域并收集這些感應數據將會消耗大量時間和成本。

針對以上不足，本文利用無人機攜帶無線充電器，提出一種基于效用最大化的數據收集方案，并通過仿真驗證了該方案的有效性。

1 網絡模型

(1)

假設UAi及其匹配SCj間的距離為dij，UAi的速度為vi。考慮到UAV在被選傳感器集群和Sink節點間的往返行程，UAV航行時間可表示為

(2)

如果一個UAV與多個集群相匹配，本文則假設UAV必須逐個從這些集群中收集數據。從當前集群中收集完數據后，UAV必須回到Sink節點處傳輸數據，然后再飛往下一個集群。

根據上節所示的網絡模型，UAV的效用函數定義為

(3)

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

(4)

為了實現感知數據的高效收集，本文試圖確定傳感器集群和UAV間的最優匹配對，以便使集群到UAV的數據傳遞速率最大化，同時保證這些集群中的傳感器得到能量補充。因此，無線可充電傳感器集群的高效數據收集問題可表示如下

(5)

2 本文算法

2.1 匹配定義

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

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

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

2.2 單邊偏好匹配算法

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

算法1：單邊匹配算法

1)初始化

構建未被匹配的傳感器集群列表UNMATCH;

2)匹配

for eachUAi,i∈Ndo

向之前從未拒絕過自己的最高等級SCj提出申請；

ifSCj∈UNMATCHthen

保存匹配對(SCj,UAj)；

將SCj從UNMATCH中刪除；

else

拒絕做出申請的UAi;

end if

end for

ifUNMATCH≠? then

跳到第2步；

else

跳到第3步；

end if

3)算法結束

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

(6)

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

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

1)初始化

構建未被匹配的集群組成的集合UNMATCH;

2)匹配

for eachUAi,i∈Ndo

向之前從未拒絕過自己的最高等級SCj做出申請；

ifSCj∈UNMATCHthen

保留匹配對(SCj,UAi);

將SCj從UNMATCH列表中刪除；

else

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

ifRank(i)>Rank(i′)then

拒絕新申請的UAi′;

else

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

拒絕先前做出申請的UAi;

end if

end if

end for

ifUNMATCH≠? then

跳到第2步；

end of

ifUNMATCH=?且部分UAi沒有結束對所有集群的申請then

跳到第2步；

end if

3)算法結束

3 性能評估

3.1 仿真配置

3.2 結果和分析

圖1給出了UAV數量固定時的仿真結果，此時傳感器集群數量為25～40個，傳感器集群分別部署于網格拓撲和隨機拓撲結構上。從圖1中可以發現，本文提出的貪婪算法的性能和最優匹配的性能一樣，而單邊匹配算法的性能遠優于UAi(i∈N)和SCj(j∈M)的隨機匹配算法。因為單邊匹配算法考慮了UAV的偏好列表，每個UAi(i∈N)有機會向其UALISTi偏好列表中的最高級別SCj做出申請，所以,單邊匹配算法的性能優于隨機匹配算法。此外，貪婪算法的性能優于單邊算法。在貪婪算法中，集群在構建偏好列表時的效用函數與UAV進行決策時的效用函數相同。SCj可拒絕向其做出申請的UAi，選擇可顯著提升系統效用的更為合適的UAV。

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

圖2給出了系統效用隨網絡規模的變化關系。當網絡規模增加時，系統效用增加。此外，當網絡規模增加時，貪婪算法與單邊算法及隨機匹配算法間的性能差異增加。這表明，當UAV的數量和位置固定時，相比于單邊匹配算法和隨機算法，本文貪婪算法更適用于大規模WSNs。

圖2 系統效用隨網絡規模的變化情況Fig 2 System utilities varies with network scale

4 結束語

本文研究了如何使用UAV來高效收集部署于惡劣環境中的無線可充電傳感器集群的感應數據。通過考慮無線能量傳輸的特點，將高效數據收集問題描述為多種約束條件下的優化問題。為了使上述問題中的系統效用最大，文中提出兩種基于匹配理論的分布式算法。仿真實驗結果表明:本文算法可實現感應數據的高效收集，同時可對惡劣環境中的傳感器集群充電。

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

[2] 吳騰飛,熊慶國,李文翔,等.方格拓撲無線傳感器網絡源路由策略的能耗分析[J].傳感器與微系統,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-)，男，四川瀘州人，碩士研究生,主要研究方向為無線傳感網、機電一體化。