RWSNs中基于效用最大化的數(shù)據(jù)收集方案研究

摘 要： 無線傳感器網(wǎng)絡(luò)在惡劣環(huán)境下的各種應(yīng)用受到傳感器電池的約束，且在數(shù)據(jù)收集方面存在多種困難。這里提出利用無線能量傳輸技術(shù)來補(bǔ)充傳感器集群的能量，同時針對部署于惡劣環(huán)境下的無線可充電傳感器集群提出一種高效的數(shù)據(jù)收集方案。面對惡劣環(huán)境，該方案利用無人機(jī)（UAV）到達(dá)傳感器集群位置，然后采集數(shù)據(jù)并對相應(yīng)集群的傳感器充電。定義了數(shù)據(jù)收集效用函數(shù)，將數(shù)據(jù)收集問題描述為一種以數(shù)據(jù)收集效用最大化為目標(biāo)的優(yōu)化問題，并提出單邊偏好匹配算法和基于雙邊偏好匹配的貪婪算法解決上述問題。理論分析和仿真實(shí)驗表明，利用貪婪算法確定的UAV和傳感器集群間的匹配關(guān)系可生成使數(shù)據(jù)收集效用最大化的最優(yōu)解，且可實(shí)現(xiàn)傳感器數(shù)據(jù)的高效收集。

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 數(shù)據(jù)收集； 單邊匹配； 貪婪算法； 最優(yōu)解

中圖分類號： TN711?34； TP393 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）15?0008?06

Abstract： The various applications of wireless sensor networks （WSNs） are restrained by the sensor′ battery in severe environment， and the WSNs face various difficulties in data collection， so the wireless energy transfer technology used to replenish the energy of sensor cluster is proposed. Aiming at the wireless rechargeable senor cluster deployed in severe environment， an efficient data collection scheme is proposed. In the scheme， the unmanned aerial vehicle （UAV） is used to arrive at the site of the sensor cluster in severe environment， after that the data is collected， and the sensors corresponding to the cluster are charged. In this paper， the utility function of data collection is defined to describe the data collection problem as an optimal problem taking utility maximization of data collection as the target， and the greedy algorithm based on bilateral preference matching and unilateral preference matching algorithm are proposed to solve the above problems. The theoretical analysis and simulation experiment results show that the matching relation of UAV and sensor cluster determined with the proposed greedy algorithm can generate the optimal solution of making data collection utility maximum， and can realize the efficient collection of sensor data.

Keywords： wireless sensor network； data collection； unilateral matching； greedy algorithm； optimal solution

0 引 言

在過去10年間，無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）獲得了人們的廣泛關(guān)注[1?2]。究其原因，一方面是因為WSN部署簡單，另一方面是因為在戰(zhàn)場偵察、環(huán)境監(jiān)測、生物觀察等領(lǐng)域具有巨大的應(yīng)用潛力[3?4]。數(shù)據(jù)處理和計算技術(shù)的進(jìn)步，使傳感器可以測量多種領(lǐng)域中的數(shù)據(jù)（比如溫度、壓力、光照、濕度及紅外線等）。但是電池技術(shù)進(jìn)展緩慢，使電量有限的傳感器受到嚴(yán)重的能量約束。此外，人們還希望利用WSN對廣大區(qū)域?qū)崿F(xiàn)無人值守式觀察。雖然傳感器部署簡單（比如通過飛機(jī)散播在廣大區(qū)域上），但是使WSN保持長時間運(yùn)行，在大面積部署區(qū)域尤其是惡劣環(huán)境條件下實(shí)現(xiàn)傳感數(shù)據(jù)的高效收集（比如高溫沙漠、密林、雪山），難度很大[5]。

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

無線能量傳輸技術(shù)在近期取得突破[10]，為WSN的傳感器能量補(bǔ)充提供了一種有力途徑。具體來說，文獻(xiàn)[11]中提出了3種無線能量傳輸技術(shù)，即：感應(yīng)耦合技術(shù)、電磁輻射技術(shù)及磁共振耦合技術(shù)，同時介紹了這些技術(shù)在WSN中的應(yīng)用。美國國家航空航天局（NASA）的電磁輻射實(shí)驗[12]證明了能量遠(yuǎn)距離高效傳輸?shù)目尚行裕涸贕oldstone網(wǎng)絡(luò)實(shí)驗中，NASA在1.5 km的距離上傳輸了34 000 W的能量，效率達(dá)到82%。另外，無人機(jī)（Unmanned Aerial Vehicle，UAV）技術(shù)越來越成熟，成本也不斷下降。在此背景下，文獻(xiàn)[13]利用一個無人機(jī)攜帶充電設(shè)備，周期性地訪問傳感器集群，對傳感器實(shí)施無線充電，進(jìn)而使WSN永久工作。文獻(xiàn)[14]設(shè)計了一種移動式無線充電車，并通過實(shí)驗驗證了無線充電車在為WSN補(bǔ)充能量方面的性能。雖然在這些創(chuàng)新性研究中傳感器能量得以補(bǔ)充，但WSN將數(shù)據(jù)以多跳方式從數(shù)據(jù)源向Sink節(jié)點(diǎn)傳輸時仍然浪費(fèi)了大量能量。此外，對于部署在惡劣環(huán)境中的傳感器集群，無線充電設(shè)備到達(dá)這些區(qū)域并收集這些感應(yīng)數(shù)據(jù)將會消耗大量時間和成本。針對以上不足，本文并不是使用無線充電車，而是提出使用無人機(jī)攜帶無線充電器（如圖1所示），同時利用UAV選擇傳感器集群，飛往被選擇的傳感器集群，并對集群中的傳感器進(jìn)行充電，同時將這些集群中的感應(yīng)數(shù)據(jù)傳輸給Sink節(jié)點(diǎn)。本文的主要工作如下：

（1） 提出利用攜帶無線充電傳輸設(shè)備的UAV收集部署于惡劣環(huán)境下的傳感器集群的感應(yīng)數(shù)據(jù)，同時對相應(yīng)集群中的傳感器補(bǔ)充能量。具體而言，本文根據(jù)UAV到傳感器集群間的距離、從傳感器集群收集到的數(shù)據(jù)以及集群內(nèi)傳感器的剩余能量，定義了數(shù)據(jù)收集效用函數(shù)，并將數(shù)據(jù)收集問題描述為以數(shù)據(jù)收集效用函數(shù)最大化為目標(biāo)的優(yōu)化問題。

（2） 提出單邊匹配算法和基于雙邊偏好匹配的貪婪算法解決上述問題，并通過理論分析和仿真實(shí)驗驗證了利用本文貪婪算法確定UAV和傳感器集群間的匹配關(guān)系可生成使數(shù)據(jù)收集效用最大化的最優(yōu)解，且可實(shí)現(xiàn)傳感器數(shù)據(jù)的高效收集。

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

假設(shè)在感應(yīng)/監(jiān)測應(yīng)用中，多個傳感器集群部署于惡劣環(huán)境中。每個集群包括一個中央Sink節(jié)點(diǎn)和一組傳感器，其中傳感器將其感應(yīng)到的數(shù)據(jù)周期性地發(fā)往Sink節(jié)點(diǎn)。為了補(bǔ)充傳感器的能量損耗、收集傳感器的感應(yīng)數(shù)據(jù)，利用一個或多個UAV飛往傳感器集群，對集群中的傳感器進(jìn)行充電，通過相應(yīng)集群中的Sink節(jié)點(diǎn)收集傳感器感應(yīng)數(shù)據(jù)。網(wǎng)絡(luò)模型如圖2所示。

2 本文算法

下面以匹配理論為基礎(chǔ)，提出兩種分布式算法來獲得上述問題的最優(yōu)解。首先給出單邊偏好匹配算法，然后根據(jù)文獻(xiàn)[15]中的Gale?Shapley算法將單邊偏好匹配算法擴(kuò)展為基于雙邊偏好匹配的貪婪算法。最后通過理論分析證明了算法的正確性。

2.1 匹配定義

匹配理論主要是解決如何將一組不可分的物品分配給一組申請人。每個申請人可能有多種偏好。以上述匹配概念為基礎(chǔ)，可將本文研究的數(shù)據(jù)收集問題闡述如下：

設(shè)有一個實(shí)例[I]表示一組UAV[N=UA1，UA2，…，UAn]及一組傳感器集群[?=SC1，SC2，…，SCm]。實(shí)例[I]中的主體是[??N]中的UAV和傳感器集群?？山邮艿腢AV?SC匹配對為集合[ε?N×?]。每個UAV[UAi∈N]有一組可接受的傳感器集群[AUAi，]其中[AUAi=][SCj∈?：UAi，SCj∈ε]。類似地，每個集群[SCj∈?]有一個可接受的申請人[ASCj，]其中[ASCj=][UAi∈N ：UAi，SCj∈ε]。本文將[UAi]和[SCj]的匹配關(guān)系定義如下：

定義1 匹配關(guān)系[Φ]為如下函數(shù)：

[ΦUAi∈???，]且[ΦUAi∈0，1，…；ΦSCj∈][N ??，][ΦSCj∈0，1，]其中[ΦUAi=SCj]且[ΦSCj=][UAii∈N， j∈?]。

該定義表明，如果函數(shù)的輸入是[SCj，]則[Φ]是一個單對單匹配。另一方面，如果函數(shù)的輸入是[UAi，]則[Φ]是一個多對單匹配。在匹配理論中，本文中的主體（即UAV和SC）需要一個偏好列表才能開始匹配過程。因此，本文在選擇傳感器集群進(jìn)行能量補(bǔ)充和數(shù)據(jù)收集前，要求每個[UAi]根據(jù)自己相對所有集群的效用形成一個降序排列的偏好列表。

2.2 單邊偏好匹配算法

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

3. 算法結(jié)束

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

第2.2節(jié)從UAV角度給出了單邊偏好匹配算法。為了進(jìn)一步提升系統(tǒng)效用，本文進(jìn)行雙邊偏好匹配，即從UAV和傳感器集群兩個角度進(jìn)行匹配。

傳感器集群也可以構(gòu)建它們自己的偏好列表。然后，每個[UAi∈N]或每個[SCj∈?]均有一個按嚴(yán)格次序排列且互不相同的偏好列表。

文獻(xiàn)[15]提出一種可以始終找到穩(wěn)定性匹配關(guān)系的Gale?Shapley算法。本文以該算法為基礎(chǔ)提出一種貪婪算法。在第一階段，它計算UAV和傳感器集群的效用函數(shù)。然后，構(gòu)建按降序排列的偏好列表[UALISTi]和[SCLISTj]。它還構(gòu)建未匹配傳感器集群組成的集合UNMATCH。根據(jù)偏好列表[UALISTi，][UAi]向[UALISTi]列表中之前從未拒絕過自己且層次最高的集群[SCj]做出申請。如果[SCj]還未被匹配，則保留配對[UAi，SCj]。如果[SCj]已經(jīng)被匹配，則[SCj]檢察新采用的[UAi]和上一次迭代時的[UAi]的等級。[SCj]與其[SCLISTi]列表中等級較高者匹配，排除另外一個。被拒絕的[SCj]添加到UNMATCH中，等待下一輪匹配過程。如果[UNMATCH≠?，]則算法回到第2步。即使[UNMATCH=?，]但[UAi]還沒有結(jié)束對所有[SCj（j∈?）]的申請，則算法仍然回到步驟2。只有[UNMATCH=?]且每個UAV均申請過所有[SCj（j∈?）]時，算法才終止。

3.算法結(jié)束

2.4 理論分析

為了便于分析，下面首先給出了“最優(yōu)匹配”的定義。

定義2 最優(yōu)匹配：如果在約束條件[j∈?xij≤1]下，對匹配關(guān)系[Φ，]式[i∈Nj∈?UUAji]被最大化，則認(rèn)為[Φ]為最優(yōu)匹配。

以該最優(yōu)匹配定義為基礎(chǔ)，有如下理論：

定理1 貪婪算法獲得的匹配關(guān)系[Φg]為最優(yōu)匹配。

證明：如果對匹配關(guān)系[Φ，]在約束[j∈?xij≤1]下，式[i∈Nj∈?UUAji]最大化，則每個[SCj]必與其偏好列表中層次最高的[UAi]相匹配，現(xiàn)將其表示為[UAjf]。

假設(shè)[Φ]最優(yōu)，但是至少有一個[SCj]不與其[UAjf]匹配。根據(jù)貪婪算法，在第一輪中，[SCj]與向其申請且等級最高的[UAi]匹配，現(xiàn)將其表示為[UAjrh]。在下一輪中，如果新申請的[UAjrh]級別高于[UAjrh，]則[SCj]將會與[UAjrh]匹配且[UAjrh]被拒絕。因此，發(fā)現(xiàn)[SCj]總是與UAV中級別最高且向[SCj]做出申請的UAV相匹配。每個[UAi]有一個偏好列表包括所有的[SCjj∈?]，這說明所有的UAV將會向各個[SCj]做出申請。于是，每個[SCj]均與其[UAjf]匹配，與至少有一個[SCj]不與其[UAjf]相匹配的結(jié)論相矛盾。所以，貪婪算法獲得的匹配關(guān)系[Φg]是最優(yōu)匹配。證畢。

3 性能評估

3.1 仿真配置

本文利用部署在10 km[×]10 km區(qū)域上的UAV和傳感器集群進(jìn)行仿真實(shí)驗。電池容量為[emax=70 J，][SCj]中傳感器節(jié)點(diǎn)的剩余能量為[ejk∈60，65 J]。每個集群中的傳感器數(shù)量為[SCj∈50，100]。發(fā)射功率為[Si=1.2 W，]UAV的速度為120 km/h。對于其他參數(shù)，傳感器的數(shù)據(jù)率從[1，10] Kb/s中隨機(jī)生成。在網(wǎng)格拓?fù)浜碗S機(jī)拓?fù)浣Y(jié)構(gòu)上分別進(jìn)行了仿真實(shí)驗，取20次仿真結(jié)果的平均值作為最終的實(shí)驗結(jié)果。

3.2 結(jié)果和分析

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

圖4給出了系統(tǒng)效用隨網(wǎng)絡(luò)規(guī)模的變化關(guān)系。當(dāng)網(wǎng)絡(luò)規(guī)模增加時，系統(tǒng)效用增加。此外，當(dāng)網(wǎng)絡(luò)規(guī)模增加時，貪婪算法與單邊算法及隨機(jī)匹配算法間的性能差異增加。這表明，當(dāng)UAV的數(shù)量和位置固定時，相比于單邊匹配算法和隨機(jī)算法，本文貪婪算法更適用于大規(guī)模WSN。當(dāng)網(wǎng)絡(luò)規(guī)模增加時，受歡迎傳感器集群的數(shù)量也在增加（在所有UAV偏好列表中均有較高等級的集群定義為受歡迎集群）。無論在單邊匹配算法還是隨機(jī)匹配算法，受歡迎集群均無法擁有其偏好列表。因此，傳感器集群很可能做出非最優(yōu)決策，降低系統(tǒng)效用。

圖5給出了匹配決策和航行時間之間的關(guān)系。為便于討論，這里只給出包含兩架UAV的情況。采用貪婪算法確定UAV和集群間的匹配。星星表示UAV飛到每個集群處的時間，方形表示飛到與[UAi]相匹配的[SCj]處的航行時間，圓圈表示飛到未被匹配[SCj]處的航行時間，該時間至少比一個被匹配的[SCj]短。在圖5中發(fā)現(xiàn)雖然部分集群與UAV較近，但它們未與任何UAV相匹配，這是因為匹配決策不僅與航行時間有關(guān)，還與充電時間和傳感器集群的數(shù)據(jù)量有關(guān)。匹配關(guān)系并不只存在于相距最近的UAV和傳感器集群間。此外，在圖3中還發(fā)現(xiàn)最優(yōu)算法的曲線與貪婪算法的曲線相吻合。仿真實(shí)驗證明了貪婪算法確定的匹配關(guān)系是最優(yōu)匹配這一結(jié)論。

4 結(jié) 語

本文研究了如何使用UAV高效收集部署于惡劣環(huán)境中的無線可充電傳感器集群的感應(yīng)數(shù)據(jù)。通過考慮無線能量傳輸?shù)奶攸c(diǎn)，將高效數(shù)據(jù)收集問題描述為多種約束條件（即UAV和集群間的距離，集群中Sink節(jié)點(diǎn)處匯集的數(shù)據(jù)量以及集群中傳感器的剩余能量）下的優(yōu)化問題。為了使上述問題中的系統(tǒng)效用最大，提出兩種基于匹配理論的分布式算法，單邊匹配算法和貪婪算法，同時證明貪婪算法最優(yōu)。仿真實(shí)驗驗證了本文的理論分析結(jié)果，證明本文算法可實(shí)現(xiàn)感應(yīng)數(shù)據(jù)的高效收集，同時可對惡劣環(huán)境中的傳感器集群充電。在下一步工作中，將分析移動Sink條件下傳感器節(jié)點(diǎn)無線充電與數(shù)據(jù)收集質(zhì)量的關(guān)系，研究面向高效數(shù)據(jù)收集的移動Sink路徑規(guī)劃算法。

參考文獻(xiàn)

[1] 李建中，高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計算機(jī)研究與發(fā)展，2008，45（1）：1?15.

[2] 郭忠文，羅漢江，洪鋒，等.水下無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計算機(jī)研究與發(fā)展，2010，47（3）：377?389.

[3] 張豫鶴，黃希，崔莉.面向交通信息收集的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)[J].計算機(jī)研究與發(fā)展，2008，45（1）：110?118.

[4] GUO S， HE L， GU Y， et al. Opportunistic flooding in low?duty?cycle wireless sensor networks with unreliable links [J]. IEEE transactions on computers， 2014， 63（11）： 2787?2802.

[5] ZHAO M， LI J， YANG Y Y. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks [J]. IEEE transactions on mobile computing， 2014， 13（12）： 2689?2705.

[6] BOUABDALLAH F， BOUABDALLAH N， BOUTABA R. Cross?layer design for energy conservation in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Communications. Dresden： IEEE， 2009： 1?6.

[7] PARK C， CHOU P H. AmbiMax： autonomous energy harves?ting platform for multi?supply wireless sensor nodes [C]// Proceedings of 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston： IEEE， 2006： 168?177.

[8] FAN K W， ZHENG Z， SINHA P. Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks [C]// Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems. Raleigh： ACM， 2008： 239?252.

[9] PENG Y， LI Z， ZHANG W， et al. Prolonging sensor network lifetime through wireless charging [C]// Proceedings of 2010 31st IEEE Real?Time Systems Symposium. San Diego： IEEE， 2010： 129?139.

[10] BEH T C， KATO M， IMURA T， et al. Automated impedance matching system for robust wireless power transfer via magnetic resonance coupling [J]. IEEE transactions on industrial electronics， 2013， 60（9）： 3689?3698.

[11] XIE L， SHI Y， HOU Y T， et al. Wireless power transfer and applications to sensor networks [J]. IEEE wireless communications， 2013， 20（4）： 140?145.

[12] WANG R， YE D， DONG S， et al. Optimal matched rectifying surface for space solar power satellite applications [J]. IEEE transactions on microwave theory and techniques， 2014， 62（4）： 1080?1089.

[13] XIE L， SHI Y， HOU Y T， et al. Making sensor networks immortal： an energy?renewal approach with wireless power transfer [J]. IEEE/ACM transactions on networking （TON）， 2012， 20（6）： 1748?1761.

[14] SHI Y， XIE L， HOU Y T， et al. On renewable sensor networks with wireless energy transfer [C]// Proceedings of 2011 IEEE INFOCOM. Shanghai， China： IEEE， 2011： 1350?1358.

[15] GALE D， SHAPLEY L S. College admissions and the stability of marriage [J]. The American mathematical monthly， 2013， 120（5）： 386?391.