基于博弈理論無(wú)線(xiàn)傳感網(wǎng)覆蓋空洞修復(fù)算法

段鴻軒，李躍新

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

0 引 言

在無(wú)線(xiàn)傳感網(wǎng)絡(luò)中節(jié)點(diǎn)失效將會(huì)導(dǎo)致覆蓋空洞(cove-rage holes，CH)，并且降低網(wǎng)絡(luò)可靠性和完整性[1-4]。目前已研究出各種網(wǎng)絡(luò)修復(fù)和拓?fù)淇刂?topology control，TC)方案用于降低節(jié)點(diǎn)失效的不良影響，比如節(jié)點(diǎn)遷移、功率調(diào)整以及聚類(lèi)方法[5,6]。

近期，研究人員提出了一種混合拓?fù)淇刂品桨竅7,8]，該方案使移動(dòng)無(wú)線(xiàn)傳感網(wǎng)能夠調(diào)整其位置和傳送功率以修改或者維持位置最佳網(wǎng)絡(luò)覆蓋，在修復(fù)覆蓋空洞中，節(jié)點(diǎn)調(diào)整對(duì)于降低能源需求至關(guān)重要。因此，網(wǎng)絡(luò)壽命與恢復(fù)可以得到改善。一般來(lái)說(shuō)，混合拓?fù)淇刂菩枰袇f(xié)調(diào)，以便跟蹤拓?fù)渥兓?。然而，由于覆蓋空洞隨機(jī)出現(xiàn)的特性，多數(shù)情況下并不是都可以獲得覆蓋空洞精確的時(shí)間和區(qū)域信息。

實(shí)際上，分布式拓?fù)淇刂剖欠浅Ｓ袃r(jià)值的[7,8]，在該控制策略中對(duì)于非相鄰節(jié)點(diǎn)，節(jié)點(diǎn)幾乎一無(wú)所知。在網(wǎng)絡(luò)出現(xiàn)覆蓋空洞的情況下，每個(gè)幸存節(jié)點(diǎn)能夠獨(dú)立自發(fā)反應(yīng)。每一個(gè)節(jié)點(diǎn)測(cè)量周?chē)锤采w區(qū)域，與相鄰節(jié)點(diǎn)相互作用，并且采取分布式節(jié)能行動(dòng)，延伸剩余幸存網(wǎng)絡(luò)的覆蓋以取代覆蓋空洞。這種方法的潛在益處在于節(jié)點(diǎn)可以?xún)?yōu)化它們自己的能源使用，同時(shí)也有助于網(wǎng)絡(luò)的整體壽命。由于在每一個(gè)獨(dú)立傳感器節(jié)點(diǎn)無(wú)法獲得整體網(wǎng)絡(luò)的全局視圖，很難保障這種分布式方法的收斂性。

因此，我們提出一種基于博弈理論的分布式算法以緩解覆蓋空洞，該方法使節(jié)點(diǎn)以不對(duì)等的、分散化的方式做出混合拓?fù)淇刂茮Q策?；诓┺睦碚撚^(guān)念[9,10]，該方法可以結(jié)合不同拓?fù)浞桨?，比如遷移和傳送功率控制。我們用公式表示了新的勢(shì)博弈，其中節(jié)點(diǎn)可以自主有效地決定適當(dāng)拓?fù)淇刂菩袨?也就是物理移動(dòng)或者調(diào)整功率)。由于決策基于節(jié)點(diǎn)狀態(tài)以及從相鄰節(jié)點(diǎn)收集來(lái)的信息，該覆蓋空洞算法能夠解決實(shí)時(shí)反應(yīng)和覆蓋需求，尤其是對(duì)于部署在惡劣環(huán)境中并且沒(méi)有合適集中控制的網(wǎng)絡(luò)。提出的博弈理論混合拓?fù)淇刂扑惴ǎ娱L(zhǎng)了移動(dòng)傳感網(wǎng)絡(luò)壽命。該算法容許每個(gè)傳感器改變其位置和傳感覆蓋區(qū)域以節(jié)能有效地填補(bǔ)網(wǎng)絡(luò)傳感覆蓋空隙。分析驗(yàn)證了該拓?fù)淇刂扑惴ㄊ羌s束的勢(shì)博弈。綜合仿真與對(duì)比研究結(jié)果表明，所提算法在連續(xù)隨機(jī)覆蓋空洞情況下有效改善了網(wǎng)絡(luò)彈性。

1 系統(tǒng)模型

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

(1)

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

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

2 提出的分布式修復(fù)算法

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

2.1 博弈問(wèn)題表述

在這個(gè)問(wèn)題中，傳感器允許同時(shí)與另外一個(gè)傳感器彼此相互作用，將其覆蓋區(qū)域擴(kuò)到最大限度。每一個(gè)傳感器基于其對(duì)局部網(wǎng)絡(luò)的了解、環(huán)境和其它玩家的行為預(yù)測(cè)，力圖最大化其實(shí)用功能。雙向互動(dòng)可以建模為一個(gè)博弈，其中傳感器為參與者，每次步驟t，博弈重復(fù)。在步驟t>0，每個(gè)傳感器i∈V選擇一個(gè)行動(dòng)si∈Ai以最大化其期望效用。Ai為節(jié)點(diǎn)i可以采取的行動(dòng)集合。每個(gè)參與者的效用不僅僅取決于行動(dòng)，還取決于其它所有參與者的行動(dòng)。

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

(2)

式中：P(si,s-i)和C(si)分別代表策略si在節(jié)點(diǎn)i的效益和成本。w1和w2分別代表與效益和成本相關(guān)聯(lián)的權(quán)重，用于平衡這兩個(gè)方面以及調(diào)整博弈速率。所有參與者改變策略的動(dòng)機(jī)可以通過(guò)一個(gè)單一整體函數(shù)表示，我們稱(chēng)之為勢(shì)函數(shù)。

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

(3)

圖1 傳感器節(jié)點(diǎn)i收益

成本的兩種類(lèi)型均為能源消耗形式，皆考慮在內(nèi)。其中一種對(duì)應(yīng)節(jié)點(diǎn)傳感功率變化，通過(guò)Cp(si)表示；另一種對(duì)應(yīng)節(jié)點(diǎn)位置變化，通過(guò)CT(si)表示。

節(jié)點(diǎn)i傳感功率變化的成本可以通過(guò)如下公式得知

(4)

式中：T為兩個(gè)連續(xù)覆蓋空洞之間的預(yù)期間隔持續(xù)時(shí)間；|·|代表絕對(duì)操作；c1為約束常數(shù)，是為了阻止網(wǎng)絡(luò)不必要的功率頻繁變化。注意，這里指數(shù)函數(shù)是用于定義成本以抑制傳感器傳感范圍過(guò)度變化。這是因?yàn)槌杀驹鲩L(zhǎng)遠(yuǎn)遠(yuǎn)快于傳感范圍增加。另外，還需要注意，在Δpi<0的情況下，成本取得負(fù)值并變成收益，這會(huì)激勵(lì)節(jié)點(diǎn)四處移動(dòng)以降低過(guò)高的傳感功率，從而達(dá)到延長(zhǎng)節(jié)點(diǎn)壽命的效果。

節(jié)點(diǎn)位置變化成本通過(guò)如下公式表示

(5)

式中：Δai表示節(jié)點(diǎn)i移動(dòng)距離；常數(shù)c2用于預(yù)防不必要的頻繁小移動(dòng)。指數(shù)函數(shù)同時(shí)也用于定義傳感器位置變化的成本以阻止傳感器移動(dòng)過(guò)遠(yuǎn)。

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

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

(6)

式中：k1為傳感功率變化成本權(quán)重系數(shù)；k2為位置變化成本權(quán)重系數(shù)。注意的是節(jié)點(diǎn)i成本只取決于其策略si，并且與其它節(jié)點(diǎn)策略s-i無(wú)關(guān)，所以

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

(7)

定理1 定義覆蓋博弈是一個(gè)約束勢(shì)博弈，通過(guò)如下勢(shì)函數(shù)表示

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

(8)

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

(9)

參考式(3)，我們得出

因此，我們可以證明

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

2.2 分布式學(xué)習(xí)算法

每個(gè)節(jié)點(diǎn)的效用取決于相鄰節(jié)點(diǎn)動(dòng)作。節(jié)點(diǎn)不能預(yù)先訪(fǎng)問(wèn)效用值。因此，基于動(dòng)作的學(xué)習(xí)算法，比如更好(或最好)答復(fù)學(xué)習(xí)算法和自適應(yīng)學(xué)習(xí)算法并不能用于解決這個(gè)問(wèn)題。所以，分布式學(xué)習(xí)算法是最為合適的，僅需要從先前步驟中接收到的支付。參與者根據(jù)對(duì)其它參與者動(dòng)作的觀(guān)察而調(diào)整自己動(dòng)作。在特殊情況下，參與者既不知道其它參與者采取的動(dòng)作也不了解支付函數(shù)結(jié)構(gòu)形態(tài)。

我們提出了一種基于支付函數(shù)的分布式學(xué)習(xí)算法，以便實(shí)現(xiàn)勢(shì)博弈。在提出的算法中，對(duì)于每個(gè)t≥0和i∈V，我們將傳感器i更加成功的行動(dòng)表示為τi(t)

(10)

提出的學(xué)習(xí)算法步驟如下：

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

(2)更新：在每個(gè)時(shí)間點(diǎn)t≥2，每個(gè)傳感器遵循如下規(guī)則更新?tīng)顟B(tài)：

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

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

(3)重復(fù)：傳感器i執(zhí)行(2)。

3 仿真結(jié)果與分析

通過(guò)Matlab仿真軟件對(duì)提出算法進(jìn)行了驗(yàn)證分析。傳感器節(jié)點(diǎn)隨機(jī)均勻部署于200 m×200 m的二維矩形區(qū)域內(nèi)。節(jié)點(diǎn)通信范圍設(shè)置為30 m，節(jié)點(diǎn)傳感范圍隨機(jī)初始化7 m至15 m均勻分布，使用不同數(shù)量節(jié)點(diǎn)N進(jìn)行了測(cè)試，從60到500個(gè)節(jié)點(diǎn)，探測(cè)率ε=0.3，仿真參數(shù)見(jiàn)表1。采用覆蓋率和能量消耗兩個(gè)指標(biāo)來(lái)評(píng)估提出算法的性能[2]，并與文獻(xiàn)[12]提出的基于移動(dòng)節(jié)點(diǎn)的修復(fù)策略和文獻(xiàn)[7]提出的分布均勻同步覆蓋學(xué)習(xí)算法進(jìn)行了比較。

表1 仿真參數(shù)

3.1 網(wǎng)絡(luò)覆蓋質(zhì)量結(jié)果

采用區(qū)域覆蓋率指標(biāo)來(lái)評(píng)價(jià)算法修復(fù)覆蓋空洞的能力。將二維矩形監(jiān)測(cè)區(qū)域劃分成M×N大小的網(wǎng)格，如果網(wǎng)格單元坐標(biāo)都在節(jié)點(diǎn)范圍內(nèi)，那它們便是被傳感節(jié)點(diǎn)覆蓋。覆蓋率可以定義為覆蓋至少一個(gè)傳感節(jié)點(diǎn)的網(wǎng)格數(shù)量與給定區(qū)域內(nèi)總網(wǎng)格數(shù)量比，即

(11)

式中：x和y——節(jié)點(diǎn)橫縱坐標(biāo)，F(xiàn)q——每個(gè)網(wǎng)格是否被覆蓋。

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

圖2 不同算法的覆蓋率結(jié)果對(duì)比曲線(xiàn)，N=400

圖3 隨著節(jié)點(diǎn)密度增加時(shí)，不同算法的覆蓋率結(jié)果對(duì)比曲線(xiàn)

3.2 能耗結(jié)果分析

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

圖4 隨著網(wǎng)絡(luò)覆蓋率增加，替換單個(gè)失敗節(jié)點(diǎn)的平均能耗

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

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

[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).[王珊,王慶生,樊茂森.基于移動(dòng)節(jié)點(diǎn)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)方法[J].傳感器與微系統(tǒng),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ìn)虛擬力算法的通信基站再部署策略[J].電訊技術(shù),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).[黃月,吳成東,張?jiān)浦?等.混合無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略[J].江南大學(xué)學(xué)報(bào)(自然科學(xué)版),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.