袁紅春,余躍,梅海彬

基于隱馬爾可夫模型和非合作博弈的功率控制

袁紅春,余躍*,梅海彬

上海海洋大學(xué) 信息學(xué)院, 上海 201306

降低功耗是無線傳感網(wǎng)研究中的重要問題之一。針對(duì)現(xiàn)有無線傳感網(wǎng)存在功耗高、能量利用率低等問題，本文提出一種基于隱馬爾可夫模型和非合作博弈的功率控制方法。證明了該方法中納什均衡的存在性和唯一性以及隱馬爾可夫模型(HMM)在特定條件下的廣義平穩(wěn)性。通過仿真實(shí)驗(yàn)將該算法與已有的基于非合作博弈的控制方法進(jìn)行比較。仿真結(jié)果表明，該算法在能量利用率、收斂性、降低功耗方面均優(yōu)于原有算法，能夠有效延長(zhǎng)網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò); 隱馬爾可夫模型; 非合作博弈; 低功耗

無線傳感器網(wǎng)絡(luò)(WSN)被廣泛應(yīng)用于工業(yè)、醫(yī)學(xué)、經(jīng)濟(jì)等領(lǐng)域[1]，經(jīng)過數(shù)十年發(fā)展，無線傳感網(wǎng)的帶寬和頻譜利用率已經(jīng)提高[2]。為滿足通信質(zhì)量和覆蓋范圍要求，無線傳感網(wǎng)的功耗越來越高。建立適當(dāng)?shù)墓β士刂茩C(jī)制，最大化無線傳感網(wǎng)生命周期，已成為無線傳感網(wǎng)研究熱點(diǎn)之一[3]。目前，已有學(xué)者提出基于博弈論的控制方法來解決無線傳感網(wǎng)傳輸功耗過高問題，并取得一定成效[4]。文獻(xiàn)[5]提出了基于非合作博弈的控制方法，該方法通過在非合作博弈中達(dá)到納什均衡進(jìn)行功率優(yōu)化。但該方法只在所有節(jié)點(diǎn)信息完全已知的情況下適用，沒有考慮由于信道阻塞引起的信息缺失問題。另外，文獻(xiàn)[6]也提到了基于非合作博弈的控制方法，有效地降低節(jié)點(diǎn)功耗。但該方法只評(píng)價(jià)控制機(jī)制對(duì)于降低功耗能力的優(yōu)劣，未涉及到能量利用率問題。

本文提出了基于隱馬爾可夫模型（HMM）和非合作博弈的功率控制方法，該機(jī)制根據(jù)信道感知結(jié)果的差異來調(diào)整數(shù)據(jù)傳輸策略。根據(jù)該方法，WSN節(jié)點(diǎn)可以準(zhǔn)確地預(yù)測(cè)其他節(jié)點(diǎn)的信道狀態(tài)從而自主決定下一時(shí)刻自身的通信狀態(tài)，不再依賴簇首節(jié)點(diǎn)的調(diào)配，減少與簇首頻繁通信造成的功率損失。此外，每次傳輸都以當(dāng)前的納什均衡功率進(jìn)行傳輸，通過減少過剩信噪比性能換取更高的傳輸效率和更低的傳輸功率。

1 基于非合作博弈的WSN幀結(jié)構(gòu)

無線傳感網(wǎng)由一個(gè)匯聚節(jié)點(diǎn)和若干個(gè)采集節(jié)點(diǎn)組成[7]。匯聚節(jié)點(diǎn)負(fù)責(zé)接收和轉(zhuǎn)發(fā)來自多個(gè)采集節(jié)點(diǎn)的數(shù)據(jù)，采集節(jié)點(diǎn)從周圍環(huán)境中采集數(shù)據(jù)，傳輸給匯聚節(jié)點(diǎn)[4]。若一個(gè)網(wǎng)絡(luò)中存在多個(gè)采集節(jié)點(diǎn)以星型拓?fù)溥B接，則不同節(jié)點(diǎn)對(duì)于簇首節(jié)點(diǎn)的信道資源存在競(jìng)爭(zhēng)關(guān)系[8]，這種關(guān)系視作一種博弈。

基于碼分多址（CDMA）的單跳無線傳感網(wǎng)結(jié)構(gòu)[5]（圖1），其拓?fù)浞绞綖樾切停渲幸粋€(gè)節(jié)點(diǎn)作為簇首（Cluster Head），Sink節(jié)點(diǎn)從簇首獲取采集節(jié)點(diǎn)的數(shù)據(jù)[9,10]。該系統(tǒng)中每個(gè)節(jié)點(diǎn)的傳輸信道狀態(tài)服從于一個(gè)2狀態(tài)隱馬爾可夫鏈，其中狀態(tài)“0”表示繁忙，狀態(tài)“1”表示空閑，轉(zhuǎn)移概率為P。信道狀態(tài)為“1”表示允許通過該信道傳輸數(shù)據(jù)，狀態(tài)為“0”表示不允許傳輸。

無線傳感網(wǎng)的幀結(jié)構(gòu)（圖2）。在該結(jié)構(gòu)中每一幀被分為多個(gè)時(shí)隙[11]，每次時(shí)隙和信道狀態(tài)的切換導(dǎo)致節(jié)點(diǎn)與簇首進(jìn)行通信，之后簇首將控制信息反饋給節(jié)點(diǎn)，這種反饋增加了網(wǎng)絡(luò)功耗。因此，本文采用一種基于博弈論的無反饋控制機(jī)制，通過多次迭代實(shí)現(xiàn)時(shí)隙內(nèi)均衡博弈。將可用帶寬分為控制信道和數(shù)據(jù)信道，假定每一個(gè)采集節(jié)點(diǎn)相對(duì)靜止，在一幀時(shí)間內(nèi)信道增益不變。在每一幀中，標(biāo)識(shí)為“0”的時(shí)隙用于對(duì)信道增益和環(huán)境噪聲進(jìn)行估計(jì)并接收來自簇首的廣播，標(biāo)識(shí)為“1”的時(shí)隙用于感知信道狀態(tài)是否被占用。若信道可用，則基于HMM和非博弈的功率控制方法生效并傳輸數(shù)據(jù)。在數(shù)據(jù)從簇首節(jié)點(diǎn)傳送至匯聚節(jié)點(diǎn)的過程中，若簇首判定信道處于空閑狀態(tài)，則通過HMM推測(cè)出節(jié)點(diǎn)進(jìn)行競(jìng)爭(zhēng)的信息，簇首根據(jù)該信息參與博弈，在達(dá)到均衡傳輸功率時(shí)進(jìn)行傳輸。假定信道帶寬為，第個(gè)節(jié)點(diǎn)的傳輸功率為P，對(duì)應(yīng)的信道增益為h，傳輸率為，簇首節(jié)點(diǎn)的噪聲功率為加性高斯白噪聲0，則第個(gè)節(jié)點(diǎn)的信噪比（SINR）可表示為：

式（1）中，表示擴(kuò)頻增益，C表示由其他節(jié)點(diǎn)在簇首節(jié)點(diǎn)產(chǎn)生的干涉，其中C定義為：

圖 1 WSN星型拓?fù)?/p>

圖 2 幀結(jié)構(gòu)

2 基于HMM的WSN節(jié)點(diǎn)建模

2.1 HMM建模原理

隱馬爾可夫模型是一種統(tǒng)計(jì)分析模型，被廣泛應(yīng)用于信號(hào)處理與分析。一個(gè)典型的HMM由兩個(gè)隨機(jī)過程組成，一個(gè)可以被觀測(cè)，另一個(gè)是不可觀測(cè)的隱含狀態(tài)轉(zhuǎn)移過程。HMM的核心思想，是通過可觀測(cè)過程，實(shí)現(xiàn)對(duì)不可觀測(cè)的隱狀態(tài)的推測(cè)。一個(gè)隱馬爾可夫模型如式3：=(,,,,)(3)

式中，為隱狀態(tài)，為可觀測(cè)狀態(tài)，為初始態(tài)概率矩陣，為可觀測(cè)狀態(tài)轉(zhuǎn)移概率矩陣，為隱狀態(tài)轉(zhuǎn)移概率矩陣。

采集節(jié)點(diǎn)根據(jù)自身信道狀態(tài)推測(cè)其他采集節(jié)點(diǎn)信道狀態(tài)的過程,可視作一個(gè)隱馬爾可夫過程（證明見2.2）。根據(jù)式3建立數(shù)學(xué)模型：第個(gè)采集節(jié)點(diǎn)自身信道狀態(tài)?={=0,=1}，為可觀測(cè)狀態(tài)。第個(gè)采集節(jié)點(diǎn)推測(cè)其他采集節(jié)點(diǎn)的信道狀態(tài)?={=0,=1}，為隱狀態(tài)。將狀態(tài)集和視作常數(shù)，式3的HMM可簡(jiǎn)化為三元組=(,,)，π為采集節(jié)點(diǎn)初始信道狀態(tài)轉(zhuǎn)移概率矩陣。為=a=(S+1=s|S=s)，是采集節(jié)點(diǎn)從時(shí)隙為、信道狀態(tài)為S，轉(zhuǎn)移到時(shí)隙+1、信道狀態(tài)為S的轉(zhuǎn)移概率。為={b()} (,=0,1)，是當(dāng)采集節(jié)點(diǎn)自身信道狀態(tài)為時(shí)，推測(cè)其他信道狀態(tài)為的條件概率。用節(jié)點(diǎn)自身狀態(tài)推測(cè)其他信道狀態(tài)的HMM，是以可觀測(cè)狀態(tài)推算最佳隱狀態(tài)的經(jīng)典問題，可用Baum-Welch和維特比算法求解，具體求解過程不在本文討論范圍。

2.2 模型的馬爾可夫性和平穩(wěn)性證明

定義1節(jié)點(diǎn)推測(cè)其他信道的過程是隱馬爾可夫過程

證明：根據(jù)馬爾可夫過程的定義，隨機(jī)過程在任一時(shí)刻的狀態(tài)，只與前一時(shí)刻1有關(guān)，而與其他時(shí)刻無關(guān)，可簡(jiǎn)記為：

(X|X-1X-2…1)=(X|X-1) (4)

由于信道狀態(tài)?為一個(gè)2狀態(tài)隱馬爾可夫鏈，根據(jù)馬爾可夫過程的定義，可得：

將式（6）代入式（5），可推得：

顯然式（7）滿足馬爾可夫性，并且該隨機(jī)過程存在隱狀態(tài)，因而該隨機(jī)過程是隱馬爾可夫過程。

定義2上述隱馬爾可夫過程是廣義平穩(wěn)的。

證明：若一個(gè)隨機(jī)過程是廣義平穩(wěn)的，則必須滿足

1、隨機(jī)過程的數(shù)學(xué)期望()是常數(shù)。

令為一個(gè)幀結(jié)構(gòu)中每個(gè)時(shí)隙的長(zhǎng)度，根據(jù)馬爾可夫過程的定義有：

3 基于非合作博弈功率的控制方法

3.1 基于非合作博弈的功率控制建模

在碼分多址通信模式的WSN中，所有采集節(jié)點(diǎn)共享有限的信道帶寬，節(jié)點(diǎn)之間競(jìng)爭(zhēng)信道增益以提高自身SINR，而有限的增益帶寬積限制了每個(gè)節(jié)點(diǎn)能獲得的功率。因而一個(gè)簇內(nèi)節(jié)點(diǎn)間競(jìng)爭(zhēng)信道增益的行為可視作非合作博弈。

財(cái)務(wù)部門提供的會(huì)計(jì)信息，應(yīng)是提供科學(xué)依據(jù)用于企業(yè)的各項(xiàng)決策，其本應(yīng)是指導(dǎo)性部門。然而記賬、報(bào)賬等范圍，是當(dāng)前很多企業(yè)財(cái)務(wù)部門集中范圍，其并無對(duì)數(shù)據(jù)行財(cái)務(wù)分析，單純是核算會(huì)計(jì)數(shù)據(jù)，所以出現(xiàn)財(cái)務(wù)信息指導(dǎo)性不高、前瞻性不強(qiáng)的局面。并沒有向企業(yè)領(lǐng)導(dǎo)提供反映很多的經(jīng)濟(jì)效益分析、企業(yè)融資籌資能力、成本測(cè)算、負(fù)債能力測(cè)算等，對(duì)企業(yè)領(lǐng)導(dǎo)行財(cái)務(wù)信息決策產(chǎn)生極大的不利作用。

該極小值點(diǎn)即為第個(gè)節(jié)點(diǎn)的效用函數(shù)最小值點(diǎn)。為確保通信質(zhì)量，式10必須滿足約束條件：0<λC≤。將式1代入式10，可以得出方程的解為：

利用定點(diǎn)迭代算法求解，每個(gè)節(jié)點(diǎn)執(zhí)行迭代方程：

根據(jù)式9和式11：

將式14帶入式13：

因此，當(dāng)?shù)螖?shù)足夠大時(shí)，系統(tǒng)必然達(dá)到納什均衡。

3.2 納什均衡的存在性和唯一性

定義3納什均衡的存在性

證明：當(dāng)納什均衡存在時(shí)，節(jié)點(diǎn)的效用函數(shù)必須滿足以下兩個(gè)條件：

1、節(jié)點(diǎn)的行為空間p是一個(gè)非空、封閉、有界的凸集。

2、效用函數(shù)U(p)在p內(nèi)是連續(xù)且擬凹的。

所以U(p)是p的凹函數(shù)。因此節(jié)點(diǎn)的效用函數(shù)同時(shí)滿足條件1和條件2，納什均衡存在。

定義4納什均衡的唯一性

證明：根據(jù)納什均衡的定義，當(dāng)納什均衡唯一時(shí)，由U(p)得出的最優(yōu)功率函數(shù)=()必須滿足以下3個(gè)條件：

1、正性：()>0；

2、單調(diào)性: 如果?≥，有(?)≥()；

3、可擴(kuò)展性：如果">1，有()>()。

①正性：由于約束條件0<λC≤，必有(p)>0。

②單調(diào)性：如果?≥,那么",?≥p，有?-C>0，并且：

③可擴(kuò)展性：如果">1：

由于=()滿足上述3個(gè)條件，所以納什均衡是唯一的。

4 基于隱馬爾可夫和非合作博弈的功率控制

圖 3 控制流程圖

5 實(shí)驗(yàn)與分析

表 1 參數(shù)表

在以下實(shí)驗(yàn)中，基于隱馬爾可夫模型和非合作博弈的功率控制法簡(jiǎn)稱HMM法；基于非合作博弈的功率控制法簡(jiǎn)稱NCG法。

滿意度系數(shù)為1.2時(shí)，不同方法的價(jià)值系數(shù)對(duì)傳輸效益比的關(guān)系(圖4)。傳輸效益比定義為傳輸?shù)臄?shù)據(jù)量與傳輸所消耗能量的比值，反映能量的利用效率。從圖4得出傳輸效益比隨著價(jià)值系數(shù)的增加而增加。相同價(jià)值系數(shù)的情況下，HMM法比NCG法擁有更高的傳輸效益比（兩者擁有相同的信噪比SINR），因此HMM法中單位能量可以傳輸更多的數(shù)據(jù)量，對(duì)能量的利用效率高于NCG法。

圖 4 傳輸效益比-價(jià)值系數(shù)

圖 5 傳輸功率-迭代次

傳輸功率與迭代次數(shù)的關(guān)系(圖5)。某一節(jié)點(diǎn)達(dá)到均衡傳輸功率時(shí)所需迭代次數(shù)反映算法的收斂速度。當(dāng)同一節(jié)點(diǎn)在非合作博弈中達(dá)到均衡功率20 mW時(shí)，HMM法需迭代10次，而NCG法需要迭代14次，迭代次數(shù)隨傳輸功率的增加而增加。對(duì)比兩種算法的收斂性，HMM法具有更快的收斂速度。HMM法通過對(duì)其他節(jié)點(diǎn)信道狀態(tài)推測(cè)，減少對(duì)狀態(tài)“0”的信道運(yùn)算量，從而節(jié)約運(yùn)算時(shí)間。

圖 6 最大生命周期

圖7 平均信噪比

在相同起始能量的情況下，采用不同方法的最大生命周期（見圖6）。在起始能量為2.5 J的情況下，NCG法大約可持續(xù)工作1500 s，而HMM法可以持續(xù)工作1900 s。采用HMM法可以使得網(wǎng)絡(luò)的生命周期更長(zhǎng)，功耗更低。

平均信噪比隨著節(jié)點(diǎn)數(shù)增多的變化趨勢(shì)（見圖7）。兩種方法隨著節(jié)點(diǎn)數(shù)的增加，平均信噪比都在降低。在仿真中0設(shè)置為5 dB，顯然HMM法比NCG法更接近0，可以更好地降低功率。

6 總結(jié)

本文將隱馬爾可夫模型結(jié)合非合作博弈過程提出了HMM法，用數(shù)學(xué)論證了該算法中納什均衡的存在性與唯一性。HMM法以降低過剩信噪比性能換取盡可能高的能量利用率，并用HMM模型推測(cè)節(jié)點(diǎn)信道狀態(tài)節(jié)省了計(jì)算量，減少了迭代次數(shù)。通過仿真驗(yàn)證，在相同條件下，HMM法在能量利用率、算法收斂性和低功耗3個(gè)方面都優(yōu)于NCG法。

[1] 董哲,宋紅霞.ZigBee-WiFi協(xié)同無線傳感網(wǎng)絡(luò)的節(jié)能技術(shù)[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(1):22-29

[2] 王會(huì)霞,李娜.無線傳感器網(wǎng)絡(luò)中基于能量感知的QoS路由協(xié)議[J].南京理工大學(xué)學(xué)報(bào),2016,40(4):467-471

[3] 高德民,錢煥延,嚴(yán)筱永,等. 無線傳感器網(wǎng)絡(luò)最大生命期數(shù)據(jù)融合算法[J].南京理工大學(xué)學(xué)報(bào),2012,36(1):55-60

[4] 段鴻軒,李躍新.基于博弈理論無線傳感網(wǎng)覆蓋空洞修復(fù)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2018,39(2):326-330

[5] 劉保見,張效義,李青.基于演化博弈論的無線傳感網(wǎng)監(jiān)測(cè)節(jié)點(diǎn)分群算法[J].計(jì)算機(jī)應(yīng)用,2016,36(8):2157-2162

[6] 孫慶中,余強(qiáng),宋偉.基于博弈論能耗均衡的WSN非均勻分簇路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2014,34(11):3164-3169

[7] 卜范玉,張清辰.基于博弈論的無線傳感網(wǎng)能量均衡模型[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(5):152-155

[8] 朱亞東,高翠芳.基于博弈論能耗均衡的無線傳感網(wǎng)絡(luò)路由算法[J].電子技術(shù)應(yīng)用,2017,43(7):114-116

[9] Movassagh M, Aghdasi HS. Game theory based node scheduling as a distributed solution for coverage control in wireless sensor networks[J]. Engineering Applications of Artificial Intelligence, 2017,65(7):137-146

[10] AlSkaif T, Zapata MG, Bellalta B. Game theory for energy efficiency in Wireless Sensor Networks: Latest trends[J]. Journal of Network and Computer Applications, 2015,54(3):33-61

[11] 汪志偉,曹建福,鄭輯光.一種面向分簇?zé)o線傳感器網(wǎng)絡(luò)的多信道跨層協(xié)議[J].西安交通大學(xué)學(xué)報(bào),2013,47(6):61-67

Power Control Based on Hidden Markov Model and Non-cooperative Game

YUAN Hong-chun, YU Yue*, MEI Hai-bin

201306,

Reducing power consumption is one of the important issues of Wireless Sensor Network (WSN). To solve the problems of high power consumption and low energy efficiency, this paper proposes an algorithm for controlling power based on the Hidden Markov Model (HMM) and non-cooperative game, in which the existence and uniqueness of Nash equilibrium of the proposed algorithm and generalized stationarity of HMM under certain condition are proved. Comparing the proposed algorithm with a previous control algorithm based on non-cooperative game through a simulation experiment, this paper concludes that the proposed algorithm is superior to the previous algorithm in energy utilization, convergence, and power consumption reduction, thus being capable of extending network life cycle effectively

Wireless sensor network; hidden Markov model; non-cooperative game; low power consumption

TN914.53

A

1000-2324(2019)04-0724-05

2018-02-05

2018-04-23

國(guó)家自然科學(xué)基金委員會(huì)資助項(xiàng)目(41776142)

袁紅春(1971-),男,博士,教授,博士生導(dǎo)師,主要從事專家系統(tǒng)、智能計(jì)算、智能信息處理等研究. E-mail:hcyuan@shou.edu.cn

Author for correspondence. E-mail:839602885@qq.com