張 鸰

（南京交通職業(yè)技術學院，江蘇 南京 211188）

1 引言

無線傳感器網(wǎng)絡部署了大量小型智能設備，這些設備形成分布式自組織網(wǎng)絡，用于數(shù)據(jù)收集和管理，可應用于各種領域，如棲息地監(jiān)測、機器監(jiān)控、農(nóng)業(yè)精確定位、室內(nèi)控制、智能報警和軍事應用等［1］。然而隨機部署、傳感器電池耗盡硬件故障、軟件缺陷和安全攻擊等原因可能會造成覆蓋漏洞，嚴重降低了效率、可靠性和服務質(zhì)量［2］。

一般通過拓撲控制解決覆蓋漏洞，拓撲控制方案的主要研究領域可分為兩類：基于節(jié)點重新定位的方案和基于功率傳輸?shù)姆桨福?］。重新定位方案可分為虛擬力方案、Voronoi 方案和翻轉(zhuǎn)方案。文獻［4］提出了一種基于徑向虛擬力的重新定位方法，稱為分布式自蔓延算法（DSSA）。文獻［5］提出了一種基于Voronoi方案和翻轉(zhuǎn)方案混合的自適應檢測修復策略，有效綜合了Voronoi方案的高精度優(yōu)點以及翻轉(zhuǎn)方案的簡易特性，盡管上述方法在傳感器移動和小范圍覆蓋漏洞恢復方面性能良好，但它在大范圍覆蓋漏洞中并不有效，因為它需要大量的迭代計算。另外由于獨立和分布式的運動，節(jié)點重新定位可能會產(chǎn)生新的小覆蓋漏洞。在某些情況下，某些節(jié)點的運動可能在平均最大化方面無效，并可能耗盡傳感器電池電源，降低其到達和修復覆蓋漏洞的能力。

為了進一步提升回復覆蓋漏洞的效果，考慮將智能算法引入回復策略中。文獻［6］提出了一種基于模糊粒子群優(yōu)化算法的無線傳感器網(wǎng)絡漏洞修復方法，有效提升了傳感器位置優(yōu)化，從而強化了修復能力。文獻［7］提出一種基于Delaunay圖的人工蜂群算法控制移動節(jié)點的部署策略，通過固定節(jié)點形成的Delaunay圖先找出覆蓋漏洞，估算覆蓋漏洞面積并計算出移動節(jié)點。文獻［8］提出了一種基于深度神經(jīng)網(wǎng)絡與模糊熵相結(jié)合的集中式傳感器網(wǎng)絡漏洞恢復方法，極大地提升了恢復效果。但是上述方法由于需要進行智能優(yōu)化，因此系統(tǒng)整體能耗成本較大，對于實際應用存在一定難度。另外上述方法考慮的傳感器系統(tǒng)均為集中式系統(tǒng)，針對分布式傳感器系統(tǒng)中存在的漏洞恢復是否有效還需要驗證。

為此，這里提出了一種基于Q學習算法的博弈論的無線傳感器網(wǎng)絡混合覆蓋漏洞恢復方法。設計了一種能夠以分散、動態(tài)和自治的方式縮小覆蓋差距的混合算法，該方法利用基于Q學習算法的博弈論概念，融合了節(jié)點重新定位和功率傳輸調(diào)整兩種覆蓋控制方案。仿真結(jié)果證明了提出方法的有效性。

2 相關理論

2.1 系統(tǒng)模型

無線傳感器網(wǎng)絡可以看作是一個連通圖G(V，E)，其中，V是表示節(jié)點的頂點集合，E表示節(jié)點間鏈接的邊集合。每個傳感器可以設計為二維矩形區(qū)域中的單位圓盤圖，表示為Δ=[xmin；xmax]×[ymin；ymax]，具有感應半徑Rs和通信半徑Rc。為了簡單起見，這里假設S中的所有節(jié)點都具有相同的Rc。設S1∈S，S2∈S，如果S1在S2的傳輸范圍內(nèi)，則這對節(jié)點(S1，S2)是雙向連接的，令Ei表示傳感器節(jié)點i的起始能量。假設每個節(jié)點都是通過GPS定位的，由于傳感器節(jié)點的可預測或不可預測的無效性，例如電池電量耗盡或長期放置導致的爆炸，可能會出現(xiàn)覆蓋漏洞。覆蓋漏洞i可視為半徑為和圓心為(xHi，yHi)的圓，此圓表示節(jié)點故障發(fā)生的區(qū)域。通過組合不同圓心和半徑的多個覆蓋漏洞，可以輕松估計不同形狀且復雜的覆蓋漏洞。設節(jié)點D表示受損節(jié)點集，U節(jié)點表示未受損節(jié)點集，位于空洞區(qū)域的每個傳感器節(jié)點Si∈S屬于D節(jié)點；否則，將其視為未損壞的節(jié)點，屬于U節(jié)點。

2.2 博弈論

博弈論（Game Theory，GT）是一種用于在不確定環(huán)境中做出戰(zhàn)略決策的數(shù)學模型，它關注的是情景建模，以描述相互依賴代理的可能行為，從而確定最優(yōu)策略。在處理GT中的競爭情況時，一個代理選擇行動的結(jié)果在很大程度上取決于其他代理的行動。

定義1（博弈論）［9］：策略形式ξ={τ，Λ，υ} 的博弈由三個基本部分組成，定義如下：

（1）參與者集合τ={1，…，n}，其中，n是參與者的數(shù)量。用-i表示不是i的參與者。

（2）行為空間Λ={ Λ1，Λ2，…，Λn}，每個參與者i都有各自的策略Λi，其中Λi是一系列參與者的行為。

（3）效用函數(shù)集合υ，其中每個參與者i都有各自的效用函數(shù)υi：Λ →R，用來評估參與者的回報。

用Λi表示動作輪廓{a1，a2，…，am}，?i∈τ。由除i以外的策略配置文件表示，即除i：{ Λ1，…Λi-1，Λi+1，…，Λn}之外的所有參與者的行動集合。

定義2（納什均衡（Nash Equilibrium，NE））［10］：在這種狀態(tài)下，考慮到其他參與者采用的策略，任何參與者都不打算改變自己的策略。如果策略是ξ的NE，對于所有滿足ai∈Λi和，?i∈τ，那么設ξ是一個策略形式的博弈。

定義3（精確勢博弈）［11］。戰(zhàn)略形式博弈Ψ是一種具有勢函數(shù)φ：Λ →R的精確勢博弈，如果對于每個i∈τ，滿足a-i∈Λ-i且可以得到：

這里將覆蓋漏洞問題描述為一個潛在的多人重復博弈，在該博弈過程中，傳感器節(jié)點代表參與者彼此之間可以通信，從而彌補覆蓋差距。

2.3 Q學習

Q學習是一種基于馬爾可夫決策過程（Markov Decision Pro‐cess，MDP）的強化學習算法，主要依賴于代理與環(huán)境之間的迭代交互［11］。在Q學習中，代理選擇從當前狀態(tài)st在時刻t執(zhí)行動作，該動作會獲得新狀態(tài)st+1并提供獎勵rt。因此，它包括學習根據(jù)當前狀態(tài)獲得的先前經(jīng)驗而執(zhí)行的動作。策略pi(s)是代理選擇每個可能狀態(tài)的計劃，由于學習系統(tǒng)和環(huán)境之間的相互作用，參與者策略逐漸得到改進。然而，在實踐中，并不直接使用強化學習算法；更傾向于使用迭代求近似值函數(shù)Q(s，a)。因此，將Q(s，a)定義為未來估計收益，一旦學習到這些值，最佳策略就是選擇對應于最大Q值的動作。

對于單個參與者系統(tǒng)，狀態(tài)的效用計算為該狀態(tài)關于所有可能動作的最大Q值。然而，對于多參與者系統(tǒng)，取決于其他參與者的聯(lián)合動作，所以最優(yōu)性準則不能只考慮個體的動作。因此，將Q學習擴展到多參與者框架時，應考慮其他參與者在選擇動作時的行為。

事實上，Q學習算法在離散狀態(tài)和動作下的性能良好［12］。然而，在現(xiàn)實應用中，通常是連續(xù)的空間，具有無限的狀態(tài)和動作組合。Q學習不能直接適用于連續(xù)變量，空間通常需要使用近似函數(shù)進行離散化，如梯度下降、特征的線性組合和神經(jīng)網(wǎng)絡。

3 混合恢復算法

3.1 覆蓋問題表達式

基于上述問題，參與者是傳感器節(jié)點，可以彼此同時互相通信，以最小的功耗增強自己的覆蓋區(qū)域。此外，這里假設所有參與者都是理性的，每個參與者都試圖根據(jù)其對網(wǎng)絡的局部期望和自己對其他參與者可能采取的行動的預測來增加其預期效用函數(shù)。在每個時間步長t＞0時的動作集，節(jié)點i∈τ可以選擇其可能作用的集合ai∈Λi。如上文所述，混合拓撲控制使用節(jié)點重新定位和功率傳輸調(diào)整。因此，每個移動傳感器i∈τ可以選擇改變其位置pi和功率傳輸（傳感器感應范圍r）i的組合動作：ai=(pi，ri)，?ai∈Λi。（1）假設pi=(pxi，pyi)是節(jié)點i在二維空間中的當前位置：pi→p'i是其位置的變化，其中是節(jié)點i的下一個位置。（2）假設分別是節(jié)點i的當前和下一次時間感應范圍，ri→r'表示傳感器感應范圍的變化，Rmin和Rmax分別是傳感器節(jié)點的最小和最大傳感范圍。效用函數(shù)每個節(jié)點i都有一個效用函數(shù)或收益函數(shù)υi：Λ →R，定義為：

式中：P(ai，a-1)、C(ai)—節(jié)點i所選擇的策略的利潤和成本；μα、μβ—平衡博弈利潤和成本的權重。

在一個重復的博弈過程中，每個時間t參與者同時選擇他們的行動策略，并接收他們的效用函數(shù)，該效用函數(shù)取決于應有的回報和付出。當所有參與者正確預測對方參與者的策略并對他們的預測做出最佳反應時，得到的結(jié)果就是納什均衡狀態(tài)。

每個節(jié)點都有一個非重疊傳感區(qū)域（Non-Overlapping Sens‐ing Area，NOSA），定義為僅由相關節(jié)點覆蓋的區(qū)域，如圖3所示。為了使總覆蓋面積最大化，縮小覆蓋間隙，傳感器節(jié)點應減少與相鄰節(jié)點的重疊區(qū)域；因此，將利潤函數(shù)最大化等同于NOSA值最大化：

式中：Ni—節(jié)點i的鄰域的集合，花銷成本表示恢復覆蓋漏洞時傳感器節(jié)點消耗的能量。

該成本主要包括兩種類型：

（1）改變用Epow表示的傳感器工作時功率消耗的能量：

（2）運動時消耗的能量，從而改變由Emot表示的位置。與改變節(jié)點i的感應功率相關的能量的表達式如下：

與節(jié)點運動相關的能量的表達式為：

式中：Rsi—感應范圍；t—持續(xù)時間或跨度。

考慮到傳感器運動和感應功率變化，總消耗能量Etot為消耗能量之和：

引理1：指定的覆蓋博弈ξcov是一個精確勢博弈，如果存在一個函數(shù)φ：Λ →R，從而滿足?ai，-i∈Λi，?a-i∈Λ-i，那么有：

φ的定義式如下：

式中：Ptot—網(wǎng)絡總覆蓋率；C—傳感器節(jié)點能耗。

證明。對于任何一個策略a：(ai，a-i)∈Λ，?i∈τ，這里從Λ中任意選擇一個策略：=(，a-i)。將覆蓋博弈算法ξconv定義為精確勢博弈。為了證明這一點，將節(jié)點i的策略從ai改為，并不改變其他策略。

可以得到：

通常，由于節(jié)點i重疊覆蓋區(qū)域至少已經(jīng)被另一個傳感器節(jié)點覆蓋，所以其任何變化都不會對整個網(wǎng)絡覆蓋產(chǎn)生任何影響：

因此，可以得到：

因此，當參與者i從策略ai轉(zhuǎn)換到策略ddotai時，潛在函數(shù)的變化等于回報/效用函數(shù)的變化。通過參考定義3，可以證明覆蓋率博弈是一個精確勢博弈。

3.2 基于分布式收益的Q學習算法

收益函數(shù)不僅取決于傳感器節(jié)點動作，還取決于其鄰域的動作。由于分布式學習方法只需要從前面的步驟中獲得回報，因此是最合適的解決方案，參與者調(diào)整自己的行為以適應其他參與者行為的變化。這里提出了一種新的基于分布式收益的Q學習算法來執(zhí)行先前制定的覆蓋博弈，處理的是多個參與者的博弈；因此，采用了多智能體強化學習的概念。這里所提出的算法流程如算法1所示。

算法1：基于分布式收益的Q學習算法

（1）初始化：在t=1時，所有傳感器節(jié)點保持其初始隨機位置。隨機初始化Q(s，ai，a-i)，NbC(s，a-i)←0和n(s)←0，其中?s∈S；?ai∈Λi；?a-i∈Λ-i。令α∈[ 0，1 ]作為初始學習率，ε為初始探索率。

（2）選擇動作并更新狀態(tài)：每次t≥2時，每個傳感器節(jié)點根據(jù)以下規(guī)則更新其狀態(tài)：

（3）觀察電流s：n(s)←n(s)+1

（4）選擇探索速率ε

（5）概率ε返回隨機動作

（6）否則，概率為(1 -ε)。通過求解：

（7）學習：觀察對方的行為a-i、獎勵R(s，ai)和下一個狀態(tài)：

（8）重復：傳感器i重復執(zhí)行步驟（2）、步驟（3），直到滿足結(jié)束條件。

回報函數(shù)在探索和利用過程之間切換，以找到最佳的行動序列。事實上，探索過程有助于節(jié)點快速發(fā)現(xiàn)未知環(huán)境，而開發(fā)過程則使節(jié)點能夠保持有效場景，指標ε控制系統(tǒng)先前獲得的信息的利用與環(huán)境探索之間的權衡。

4 仿真結(jié)果分析

4.1 仿真參數(shù)設置

在模擬過程中考慮了一個正方形區(qū)域δ，其邊長為100m，將其劃分為預定義數(shù)量的小正方形。每個小正方形的面積為1m2，其中心是要覆蓋的點，用Matlab進行了仿真試驗。節(jié)點通過均勻分布隨機部署在感興趣的領域（AoI）δ中。傳輸范圍固定為30m，傳感范圍在7m和15m之間隨機選擇，如表1所示。如果通信半徑大于傳感半徑的兩倍，則假定網(wǎng)絡連接已滿。

表1 模擬參數(shù)值設置Tab.1 Analog Parameter Value Setting

如上所述，Q學習不適用于連續(xù)空間，需要一個近似函數(shù)來離散該空間，這里使用了一種簡單的離散化形式。事實上，代理執(zhí)行兩個操作，即更改位置和功率傳輸。對于每個算法迭代，節(jié)點通過沿左、右、上或下的方向移動一步來更改其位置。傳感器感應半徑在該集合中取一個值：7、9、11、13或15。文獻［13］提出的分布式混合覆蓋漏洞恢復方法縮寫為DHCHRA。

算法中使用ε來平衡探索和勘探過程。使用表中給出的取值范圍有助于Q學習算法收斂到最優(yōu)解。

在這里，考慮了傳感器移動所消耗的能量及其傳感范圍的變化，因此傳感器應該提高其傳感范圍，以避免不必要的移動，尤其是在頻繁出現(xiàn)覆蓋漏洞的情況下。針對每個場景生成了四個不同大小的破壞事件。在每個新出現(xiàn)的覆蓋漏洞之后，算法保持活動狀態(tài)，直到達到95%的總覆蓋率。如果未滿足此閾值，則當?shù)螖?shù)達到500次時，算法將停止運行。最大迭代次數(shù)設為500次，以防止傳感器節(jié)點因電池中剩余能量耗盡而集體失效。

4.2 仿真結(jié)果

4.2.1 無障礙情景下的AoI

將這里的算法結(jié)果與DSSA和DHCHRA的結(jié)果進行了比較，使用四種不同的場景在相同的初始節(jié)點分布上測試了所有算法的實例。

在該場景中，呈現(xiàn)了一個無物理障礙的檢測區(qū)域，并生成了四個破壞事件。破壞事件時間序列為1s、14s、57s和161s。一個時間樣本結(jié)果，如圖1所示。證明了所提出的基于博弈論的Q學習算法恢復覆蓋漏洞的能力，圖中的顏色是指可以覆蓋區(qū)域的傳感器數(shù)量。準確地說，隨著顏色變?yōu)樗{色，區(qū)域中的傳感器數(shù)量減少；而當顏色變?yōu)榧t色時，傳感器數(shù)量增加。

圖1 時間樣本結(jié)果Fig.1 Time Sample Results

然而，一種色表示區(qū)域未被任何傳感器節(jié)點覆蓋。從圖1（b）、圖1（d）、圖1（f）和圖1（h）可以發(fā)現(xiàn)，由于連續(xù)破壞性事件而出現(xiàn)的新覆蓋漏洞，圖1（c）、圖1（e）、圖1（g）和圖1（j）說明了處理四個覆蓋漏洞的勢博弈行為。這些結(jié)果圖清楚地顯示了這里拓撲控制方案在連續(xù)覆蓋漏洞后，修復網(wǎng)絡并保持最高覆蓋閾值的效率。傳感器節(jié)點調(diào)整傳感范圍和位置，以便快速準確地彌補覆蓋范圍的差距。

給定算法中出現(xiàn)每個覆蓋漏洞NS=250個節(jié)點后所需迭代次數(shù)的平均值，如圖2所示。對于這三種算法，迭代次數(shù)隨著連續(xù)事件的出現(xiàn)而增加。DSSA和DHCHRA分別在事件2和事件3后達到停止標準，迭代次數(shù)等于500。與其他方法相比，該方法收斂速度更快。它成功地恢復了四個覆蓋漏洞，并在達到停止標準之前達到上述覆蓋閾值，即總覆蓋面積的95%。

圖2 迭代次數(shù)的平均值Fig.2 Average Number of Iterations

DHCHRA、DSSA的總覆蓋率的百分比，以及考慮到AoI中部署的傳感器節(jié)點（50到250個節(jié)點）的數(shù)量，總覆蓋率性能對比，如圖3所示。在連續(xù)四個覆蓋漏洞出現(xiàn)期間，對總覆蓋率進行評估。從圖3中可以看出，所提出的算法在整體網(wǎng)絡覆蓋方面優(yōu)于上述算法，并模擬了DSSA、DHCHRA 和提出的方法在能耗方面的效率。

圖3 總覆蓋率性能對比Fig.3 Comparison of Total Coverage Performance

與感測功率的變化相關的消耗能量、與節(jié)點運動相關的消耗能量以及總消耗能量，如圖4（a）～圖4（c）所示。結(jié)果表明，這里的方法在能耗方面優(yōu)于其他兩種方法。如圖2 所示，與DSSA 和DHCHRA 相比，所提出的方法對連續(xù)覆蓋漏洞具有快速響應。這些結(jié)果意味著傳感器節(jié)點在覆蓋范圍方面移動占據(jù)其最佳位置的可能性較小，這使網(wǎng)絡能夠消耗較少的能量，如圖4 所示。從而能夠擴展網(wǎng)絡的生存能力。

圖4 三種情況下的能量消耗Fig.4 Energy Consumption in Three Cases

4.2.2 有障礙情景下的AoI

為了使這里模擬更接近實際情況，我們在模擬場景中考慮了兩種障礙物形狀：矩形和T形，將障礙物放在AoI的中心，傳感器節(jié)點可以放置在障礙物的邊界上。這兩種情況的結(jié)果如下，一個時間段的示例，證明了所提出的基于博弈論的Q學習算法能夠分別恢復包含矩形和T形障礙物的檢測區(qū)域中的覆蓋漏洞，如圖5、圖6所示。

圖5 矩形時間樣本事例Fig.5 Time Sample Examples of Rectangle

圖6 T形時間樣本事例Fig.6 Time Sample Examples of T

矩形障礙場景和T形障礙場景中由于連續(xù)破壞性事件而出現(xiàn)的新覆蓋漏洞，如圖5（b）、圖5（d）、圖5（f）、圖5（h）和圖6（b）、圖6（d）、圖6（f）、圖6（h）。矩形障礙情景和T形障礙情景的破壞事件時間序列分別為1s、5s、70s和273s，以及1s、11s、169s和312s。其他子圖說明了處理矩形障礙物形狀檢測區(qū)域中四個覆蓋漏洞的方法的行為。圖中結(jié)果證明了這里的方法即使存在障礙物的情況下仍舊具備消除覆蓋漏洞的能力。

針對所提出的障礙場景恢復每個覆蓋漏洞所需的迭代次數(shù)的平均值，如圖7所示。對于矩形障礙物場景，DSSA和DHCHRA在事件2后達到停止標準。這里的方法恢復了四個覆蓋漏洞，在達到停止標準之前成功地達到了覆蓋閾值。對于T形障礙場景，DSSA 和DHCHRA 分別在事件1 和事件2 后達到停止標準。然而，這里的方法在達到總覆蓋面積的92%之前恢復了四個覆蓋漏洞。

圖7 迭代次數(shù)的平均值Fig.7 Average Number of Iterations

DHCHRA、DSSA 的總覆蓋率的百分比，以及這里的算法改變部署在具有障礙物的檢測區(qū)域中的傳感器節(jié)點的數(shù)量如圖8所示。在連續(xù)四個覆蓋漏洞出現(xiàn)期間，對總覆蓋率進行評估。從圖中可以發(fā)現(xiàn)，即使在存在障礙的情況下，提出的算法在總體網(wǎng)絡覆蓋率方面也優(yōu)于其他算法。

圖8 覆蓋率情況Fig.8 Overall Coverage

DSSA、DHCHRA 的效率，以及這里的算法在有障礙物的探測區(qū)域消耗的能量，如圖9、圖10所示。與感測功率變化相關的消耗能量、與節(jié)點運動相關的消耗能量和總消耗能量，如圖9（a）、圖9（b）、圖9（c）、圖10（a）、圖10（b）、圖10（c）所示。結(jié)果表明，這里的方法在能耗方面優(yōu)于兩種方法。

圖9 矩形障礙下的能量消耗Fig.9 Energy Consumption Under Rectangular Obstacles

圖10 T形障礙下的能量消耗Fig.10 Energy Consumption Under T Obstacles

4.2.3 無需功率調(diào)整的拓撲控制方案

許多無線傳感器網(wǎng)絡應用不支持功率傳輸調(diào)整，因此，在本節(jié)中，提出了一種在無障礙AoI中測試的無功率控制拓撲控制策略，節(jié)點的動作僅限于位置調(diào)整。針對不同建議場景，即無障礙AoI、矩形障礙AoI、T形障礙AoI以及無障礙AoI無功率調(diào)整的控制拓撲方案，這里的方法的總覆蓋面積的百分比，如圖11所示。通過改變傳感器節(jié)點的數(shù)量（從50到250個節(jié)點），評估總覆蓋率的百分比。從圖11可以發(fā)現(xiàn)，對于每個提出的場景，即50、100、150和200個節(jié)點，這里的方法均獲得了令人滿意的覆蓋率。此外，有250個節(jié)點達到了覆蓋閾值（總覆蓋面積的95%），但T形障礙場景僅達到總覆蓋面積的93%。這里的方法在所有場景中的能耗結(jié)果，如圖12所示。對于無障礙場景、矩形障礙場景和T形障礙場景，能耗值均是收斂的。然而，在不進行功率調(diào)整的情況下，該方法的能耗明顯增加。

圖11 這里方法的總覆蓋百分比Fig.11 Total Coverage Percentage of Proposed Method

圖12 能耗結(jié)果Fig.12 Energy Consumption Results

5 結(jié)論

針對惡劣環(huán)境下分布式無線傳感器網(wǎng)絡，為了降低成本與恢復能力，提出了一種Q學習博弈論的無線傳感器網(wǎng)絡混合覆蓋漏洞恢復方法。最后仿真結(jié)果可以證明如下結(jié)論：

（1）提出的方法有助于傳感器有效預測應采取的最佳策略，并執(zhí)行最準確、最成功的決策，從而能夠在實現(xiàn)惡劣環(huán)境下分布式無線傳感器網(wǎng)絡的覆蓋漏洞恢復，并且能夠降低能耗成本。

（2）與其他算法相比，在無功率調(diào)整的情況下，該算法的覆蓋率是收斂的，然而，能耗有所上升。

（3）在無障礙AoI場景和有障礙AoI場景中，這里的方法所產(chǎn)生的拓撲控制方案在能耗和覆蓋率方面優(yōu)于其他方法。但是，在有障礙物的情況下，在遵守預定義的覆蓋閾值的同時恢復覆蓋漏洞的方法的降低了恢復速度。