基于博弈理論無線傳感網覆蓋空洞修復算法

段鴻軒，李躍新

(1.東北石油大學 計算機系，黑龍江 大慶 163318；2.湖北大學 計算機與信息工程學院，湖北 武漢430064)

0 引 言

在無線傳感網絡中節點失效將會導致覆蓋空洞(cove-rage holes，CH)，并且降低網絡可靠性和完整性[1-4]。目前已研究出各種網絡修復和拓撲控制(topology control，TC)方案用于降低節點失效的不良影響，比如節點遷移、功率調整以及聚類方法[5,6]。

近期，研究人員提出了一種混合拓撲控制方案[7,8]，該方案使移動無線傳感網能夠調整其位置和傳送功率以修改或者維持位置最佳網絡覆蓋，在修復覆蓋空洞中，節點調整對于降低能源需求至關重要。因此，網絡壽命與恢復可以得到改善。一般來說，混合拓撲控制需要集中協調，以便跟蹤拓撲變化。然而，由于覆蓋空洞隨機出現的特性，多數情況下并不是都可以獲得覆蓋空洞精確的時間和區域信息。

實際上，分布式拓撲控制是非常有價值的[7,8]，在該控制策略中對于非相鄰節點，節點幾乎一無所知。在網絡出現覆蓋空洞的情況下，每個幸存節點能夠獨立自發反應。每一個節點測量周圍未覆蓋區域，與相鄰節點相互作用，并且采取分布式節能行動，延伸剩余幸存網絡的覆蓋以取代覆蓋空洞。這種方法的潛在益處在于節點可以優化它們自己的能源使用，同時也有助于網絡的整體壽命。由于在每一個獨立傳感器節點無法獲得整體網絡的全局視圖，很難保障這種分布式方法的收斂性。

因此，我們提出一種基于博弈理論的分布式算法以緩解覆蓋空洞，該方法使節點以不對等的、分散化的方式做出混合拓撲控制決策。基于博弈理論觀念[9,10]，該方法可以結合不同拓撲方案，比如遷移和傳送功率控制。我們用公式表示了新的勢博弈，其中節點可以自主有效地決定適當拓撲控制行為(也就是物理移動或者調整功率)。由于決策基于節點狀態以及從相鄰節點收集來的信息，該覆蓋空洞算法能夠解決實時反應和覆蓋需求，尤其是對于部署在惡劣環境中并且沒有合適集中控制的網絡。提出的博弈理論混合拓撲控制算法，延長了移動傳感網絡壽命。該算法容許每個傳感器改變其位置和傳感覆蓋區域以節能有效地填補網絡傳感覆蓋空隙。分析驗證了該拓撲控制算法是約束的勢博弈。綜合仿真與對比研究結果表明，所提算法在連續隨機覆蓋空洞情況下有效改善了網絡彈性。

1 系統模型

我們用Ei表示節點有限能量，i∈V。每一個節點通過GPS或者一些其它定位方法知道自己的位置。傳感節點i相鄰節點的集合表示如下

(1)

覆蓋空洞k可以看成是一個圓的半徑rHolek以(xHolek,yHolek)為中心。這個圓代表節點在該位置發生故障的事件，可能是由于物理性損傷造成的。

通過結合不同中心和半徑的多種覆蓋空洞，任何復雜的空洞(凸或非凸形狀)都可以輕易計算得出，部署節點分類為損壞節點(D-nodes)和未損壞節點(U-nodes)[11]。損壞節點為失效節點的集合，存在于損壞區域。未損壞節點會直接或間接受到影響。我們假設如果在其范圍內存在至少一個損壞節點時，未損壞節點均能夠獨立檢測損壞事件。

2 提出的分布式修復算法

在這部分中，本文提出利用博弈理論方法修復覆蓋空洞。該方法證明為勢博弈，并且具有整體收斂性和穩定性。

2.1 博弈問題表述

在這個問題中，傳感器允許同時與另外一個傳感器彼此相互作用，將其覆蓋區域擴到最大限度。每一個傳感器基于其對局部網絡的了解、環境和其它玩家的行為預測，力圖最大化其實用功能。雙向互動可以建模為一個博弈，其中傳感器為參與者，每次步驟t，博弈重復。在步驟t>0，每個傳感器i∈V選擇一個行動si∈Ai以最大化其期望效用。Ai為節點i可以采取的行動集合。每個參與者的效用不僅僅取決于行動，還取決于其它所有參與者的行動。

ui(si,s-i)=w1×P(si,s-i)-w2×C(si)

(2)

式中：P(si,s-i)和C(si)分別代表策略si在節點i的效益和成本。w1和w2分別代表與效益和成本相關聯的權重，用于平衡這兩個方面以及調整博弈速率。所有參與者改變策略的動機可以通過一個單一整體函數表示，我們稱之為勢函數。

效用函數或者支付函數確定一個節點在覆蓋一個區域時候收獲多少收益以及付出多少成本。收益必須足夠高才能有助于傳感器對于覆蓋空洞的修復，成本也必須足以避免可能發生的多余運作。為了最大化網絡傳感覆蓋，每一個節點旨在減少與其相鄰節點的重疊傳感覆蓋范圍。為此，我們定義節點i收益為P(si,s-i)，表示只由該節點覆蓋的區域，如圖1所示，公式如下

(3)

圖1 傳感器節點i收益

成本的兩種類型均為能源消耗形式，皆考慮在內。其中一種對應節點傳感功率變化，通過Cp(si)表示；另一種對應節點位置變化，通過CT(si)表示。

節點i傳感功率變化的成本可以通過如下公式得知

(4)

式中：T為兩個連續覆蓋空洞之間的預期間隔持續時間；|·|代表絕對操作；c1為約束常數，是為了阻止網絡不必要的功率頻繁變化。注意，這里指數函數是用于定義成本以抑制傳感器傳感范圍過度變化。這是因為成本增長遠遠快于傳感范圍增加。另外，還需要注意，在Δpi<0的情況下，成本取得負值并變成收益，這會激勵節點四處移動以降低過高的傳感功率，從而達到延長節點壽命的效果。

節點位置變化成本通過如下公式表示

(5)

式中：Δai表示節點i移動距離；常數c2用于預防不必要的頻繁小移動。指數函數同時也用于定義傳感器位置變化的成本以阻止傳感器移動過遠。

因此，總成本可以通過如下公式求得

C(si)=k1CP(si)+k2CT(si)

(6)

式中：k1為傳感功率變化成本權重系數；k2為位置變化成本權重系數。注意的是節點i成本只取決于其策略si，并且與其它節點策略s-i無關，所以

C(si,s-i)=C(si)

(7)

定理1 定義覆蓋博弈是一個約束勢博弈，通過如下勢函數表示

φ(s)=w1S(s)-w2C(s)

(8)

式中：s={si,s-i}表示所有節點策略的集合；S(·)表示傳感器整體覆蓋范圍。

(9)

參考式(3)，我們得出

因此，我們可以證明

也就是說，任何傳感器改變其策略的誘因都可以使用單一整體勢函數表示，因此提出的博弈被證明為勢博弈。

2.2 分布式學習算法

每個節點的效用取決于相鄰節點動作。節點不能預先訪問效用值。因此，基于動作的學習算法，比如更好(或最好)答復學習算法和自適應學習算法并不能用于解決這個問題。所以，分布式學習算法是最為合適的，僅需要從先前步驟中接收到的支付。參與者根據對其它參與者動作的觀察而調整自己動作。在特殊情況下，參與者既不知道其它參與者采取的動作也不了解支付函數結構形態。

我們提出了一種基于支付函數的分布式學習算法，以便實現勢博弈。在提出的算法中，對于每個t≥0和i∈V，我們將傳感器i更加成功的行動表示為τi(t)

(10)

提出的學習算法步驟如下：

(1)初始化：t=1，所有傳感器保持其最初狀態。

(2)更新：在每個時間點t≥2，每個傳感器遵循如下規則更新狀態：

1)傳感器i選擇探索率ε∈(0,0.5]并計算si(τi(t))；

3)基于概率1-ε，傳感器i在時間點t+1保持時間點t的策略；

(3)重復：傳感器i執行(2)。

3 仿真結果與分析

通過Matlab仿真軟件對提出算法進行了驗證分析。傳感器節點隨機均勻部署于200 m×200 m的二維矩形區域內。節點通信范圍設置為30 m，節點傳感范圍隨機初始化7 m至15 m均勻分布，使用不同數量節點N進行了測試，從60到500個節點，探測率ε=0.3，仿真參數見表1。采用覆蓋率和能量消耗兩個指標來評估提出算法的性能[2]，并與文獻[12]提出的基于移動節點的修復策略和文獻[7]提出的分布均勻同步覆蓋學習算法進行了比較。

表1 仿真參數

3.1 網絡覆蓋質量結果

采用區域覆蓋率指標來評價算法修復覆蓋空洞的能力。將二維矩形監測區域劃分成M×N大小的網格，如果網格單元坐標都在節點范圍內，那它們便是被傳感節點覆蓋。覆蓋率可以定義為覆蓋至少一個傳感節點的網格數量與給定區域內總網格數量比，即

(11)

式中：x和y——節點橫縱坐標，Fq——每個網格是否被覆蓋。

每次實驗中，我們進行50次測試，每個實驗由5個連續隨機故障組成，均勻分布于部署區域。當覆蓋率在70%以上時，網絡才有效，當N=400時，該算法修復連續覆蓋空洞的能力(依據覆蓋率)，如圖2所示。一開始的覆蓋率為100%，當節點開始失敗時，網絡覆蓋率開始下降。從圖2可以看出，本文提出算法可以保持網絡有效覆蓋256到437個時間單位，比其它兩種策略分別多出約75、100個時間單位。并且當節點開始失敗時，提出算法的網絡覆蓋率下降速率最慢，可見提出的算法優于其它覆蓋空洞修復策略并且有效維護了網絡覆蓋。圖3顯示了隨著節點數量從60到500逐漸增加時，即傳感節點密度增加時，3種算法的覆蓋率變化情況。通過50次測試計算平均覆蓋，從圖3可以看出，提出算法能夠維持更高覆蓋率。

圖2 不同算法的覆蓋率結果對比曲線，N=400

圖3 隨著節點密度增加時，不同算法的覆蓋率結果對比曲線

3.2 能耗結果分析

圖4顯示了其它兩種方法和本文算法在替換失敗節點所需的平均能耗方面的性能比較結果。當網絡覆蓋率達到90%以上時，提出算法替換失敗節點所需的平均能耗趨于平穩。隨著網絡覆蓋率的增加，空洞數量不斷減少，3種方法替換失敗節點所需的平均能耗均也不斷減少，但是本文提出算法明顯勝于其它算法，所需的平均能耗最少，如圖4所示。

圖4 隨著網絡覆蓋率增加，替換單個失敗節點的平均能耗

4 結束語

本文提出了一種無線傳感網覆蓋空洞修復算法。該算法基于博弈理論，結合了傳感功率控制和物理節點遷移。通過具體仿真研究，在不同節點密度和覆蓋率條件下，對該提議方法性能進行了研究分析。結果顯示，無論在覆蓋率還是能耗方面，該算法都優于其它兩種覆蓋空洞修復算法，延長了網絡生存時間，更好地保持了網絡覆蓋。在后續研究工作中，我們計劃通過實際約束條件進一步優化該算法，以便提高其適用性，比如，傳感器的移動限制在某個方向上。

[1]Sahoo P,Liao WC.HORA:A distributed coverage hole repair algorithm for wireless sensor networks[J].IEEE Tran-sactions on Mobile Computing,2015,14(7):1397-1410.

[2]WANG Shan,WANG Qingsheng,FAN Maosen.A method of wireless sensor network coverage hole repair based on mobile node[J].Sensor and Micro System,2015,34(4):134-136(in Chinese).[王珊,王慶生,樊茂森.基于移動節點的無線傳感器網絡覆蓋空洞修復方法[J].傳感器與微系統,2015,34(4):134-136.]

[3]Rafiei A,Maali Y,Abolhasan M,et al.A tuned fuzzy logic relocation model in WSNS using particle swarm optimization[C]//IEEE Vehicular Technology Conference Vtc-fall,2013,14(6):1-5.

[4]Zhang J,Li S,Li Q,et al.Coverage hole recovery algorithm based on perceived probability in heterogeneous wireless sensor network[J].Journal of Computational Information Systems,2014,10(7):2983-2990.

[5]Xu N,Huang A,Hou TW,et al.Coverage and connectivity guaranteed topology control algorithm for cluster-based wireless sensor networks[J].Wireless Communications & Mobile Computing,2012,12(1):23-32.

[6]ZHAO Haifu,CHEN Jiong,GU Yuantao.Mobile base station’s relocate method based on improved virtual force algorithm[J].Telecommunication Engineering,2012,52(3):294-299(in Chinese).[趙海富,陳炯,谷源濤.基于改進虛擬力算法的通信基站再部署策略[J].電訊技術,2012,52(3):294-299.]

[7]Zhu M,Martínez S.Distributed coverage games for energy-aware mobile sensor networks[J].Siam Journal on Control & Optimization,2013,51(51):1-27.

[8]Miranda K,Molinaro A,Razafindralambo T.A survey on rapidly deployable solutions for post-disaster networks[J].IEEE Communications Magazine,2016,54(4):117-123.

[9]Qin N,Guo L,Ding Z,et al.A vector algebraic algorithm for coverage compensation in hybrid wireless sensor networks[J].International Journal of Distributed Sensor Networks,2013(1):1-8.

[10]Bialek-Davenet S,Leflon-Guibout V,Minh OT,et al.Hole detection for increasing coverage in wireless sensor network using triangular structure[J].International Journal of Computer Science Issues,2012,9(1):672-673.

[11]Han CY.Repair method for coverage holes of wireless sensor networks based on distance[J].Transducer & Microsystem Technologies,2013,32(4):91-94.

[12]HUANG Yue,WU Chengdong,ZHANG Yunzhou,et al.Repair strategy of coverage holes in hybrid wireless sensor networks[J].Journal of Jiangnan University(Natural Science Edition),2012,11(4):418-422(in Chinese).[黃月,吳成東,張云洲,等.混合無線傳感器網絡覆蓋空洞修復策略[J].江南大學學報(自然科學版),2012,11(4):418-422.]

[13]Wang X,Zheng W,Lu Z,et al.Dense femtocell networks power self-optimization:An exact potential game approach[J].International Journal of Communication Systems,2016,29(1):16-32.