RWSNs中基于效用最大化的數據收集方案研究

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

關鍵詞： 無線傳感器網絡； 數據收集； 單邊匹配； 貪婪算法； 最優解

中圖分類號： TN711?34； TP393 文獻標識碼： 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年間，無線傳感器網絡（Wireless Sensor Network，WSN）獲得了人們的廣泛關注[1?2]。究其原因，一方面是因為WSN部署簡單，另一方面是因為在戰場偵察、環境監測、生物觀察等領域具有巨大的應用潛力[3?4]。數據處理和計算技術的進步，使傳感器可以測量多種領域中的數據（比如溫度、壓力、光照、濕度及紅外線等）。但是電池技術進展緩慢，使電量有限的傳感器受到嚴重的能量約束。此外，人們還希望利用WSN對廣大區域實現無人值守式觀察。雖然傳感器部署簡單（比如通過飛機散播在廣大區域上），但是使WSN保持長時間運行，在大面積部署區域尤其是惡劣環境條件下實現傳感數據的高效收集（比如高溫沙漠、密林、雪山），難度很大[5]。

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

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

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

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

1 網絡模型

假設在感應/監測應用中，多個傳感器集群部署于惡劣環境中。每個集群包括一個中央Sink節點和一組傳感器，其中傳感器將其感應到的數據周期性地發往Sink節點。為了補充傳感器的能量損耗、收集傳感器的感應數據，利用一個或多個UAV飛往傳感器集群，對集群中的傳感器進行充電，通過相應集群中的Sink節點收集傳感器感應數據。網絡模型如圖2所示。

2 本文算法

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

2.1 匹配定義

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

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

定義1 匹配關系[Φ]為如下函數：

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

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

2.2 單邊偏好匹配算法

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

3. 算法結束

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

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

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

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

3.算法結束

2.4 理論分析

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

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

以該最優匹配定義為基礎，有如下理論：

定理1 貪婪算法獲得的匹配關系[Φg]為最優匹配。

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

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

3 性能評估

3.1 仿真配置

本文利用部署在10 km[×]10 km區域上的UAV和傳感器集群進行仿真實驗。電池容量為[emax=70 J，][SCj]中傳感器節點的剩余能量為[ejk∈60，65 J]。每個集群中的傳感器數量為[SCj∈50，100]。發射功率為[Si=1.2 W，]UAV的速度為120 km/h。對于其他參數，傳感器的數據率從[1，10] Kb/s中隨機生成。在網格拓撲和隨機拓撲結構上分別進行了仿真實驗，取20次仿真結果的平均值作為最終的實驗結果。

3.2 結果和分析

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

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

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

4 結 語

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

參考文獻

[1] 李建中，高宏.無線傳感器網絡的研究進展[J].計算機研究與發展，2008，45（1）：1?15.

[2] 郭忠文，羅漢江，洪鋒，等.水下無線傳感器網絡的研究進展[J].計算機研究與發展，2010，47（3）：377?389.

[3] 張豫鶴，黃希，崔莉.面向交通信息收集的無線傳感器網絡節點[J].計算機研究與發展，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.