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

袁紅春,余躍,梅海彬

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

袁紅春,余躍*,梅海彬

上海海洋大學 信息學院, 上海 201306

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

無線傳感器網絡; 隱馬爾可夫模型; 非合作博弈; 低功耗

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

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

1 基于非合作博弈的WSN幀結構

無線傳感網由一個匯聚節點和若干個采集節點組成[7]。匯聚節點負責接收和轉發來自多個采集節點的數據，采集節點從周圍環境中采集數據，傳輸給匯聚節點[4]。若一個網絡中存在多個采集節點以星型拓撲連接，則不同節點對于簇首節點的信道資源存在競爭關系[8]，這種關系視作一種博弈。

基于碼分多址（CDMA）的單跳無線傳感網結構[5]（圖1），其拓撲方式為星型，其中一個節點作為簇首（Cluster Head），Sink節點從簇首獲取采集節點的數據[9,10]。該系統中每個節點的傳輸信道狀態服從于一個2狀態隱馬爾可夫鏈，其中狀態“0”表示繁忙，狀態“1”表示空閑，轉移概率為P。信道狀態為“1”表示允許通過該信道傳輸數據，狀態為“0”表示不允許傳輸。

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

式（1）中，表示擴頻增益，C表示由其他節點在簇首節點產生的干涉，其中C定義為：

圖 1 WSN星型拓撲

圖 2 幀結構

2 基于HMM的WSN節點建模

2.1 HMM建模原理

隱馬爾可夫模型是一種統計分析模型，被廣泛應用于信號處理與分析。一個典型的HMM由兩個隨機過程組成，一個可以被觀測，另一個是不可觀測的隱含狀態轉移過程。HMM的核心思想，是通過可觀測過程，實現對不可觀測的隱狀態的推測。一個隱馬爾可夫模型如式3：=(,,,,)(3)

式中，為隱狀態，為可觀測狀態，為初始態概率矩陣，為可觀測狀態轉移概率矩陣，為隱狀態轉移概率矩陣。

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

2.2 模型的馬爾可夫性和平穩性證明

定義1節點推測其他信道的過程是隱馬爾可夫過程

證明：根據馬爾可夫過程的定義，隨機過程在任一時刻的狀態，只與前一時刻1有關，而與其他時刻無關，可簡記為：

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

由于信道狀態?為一個2狀態隱馬爾可夫鏈，根據馬爾可夫過程的定義，可得：

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

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

定義2上述隱馬爾可夫過程是廣義平穩的。

證明：若一個隨機過程是廣義平穩的，則必須滿足

1、隨機過程的數學期望()是常數。

令為一個幀結構中每個時隙的長度，根據馬爾可夫過程的定義有：

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

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

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

財務部門提供的會計信息，應是提供科學依據用于企業的各項決策，其本應是指導性部門。然而記賬、報賬等范圍，是當前很多企業財務部門集中范圍，其并無對數據行財務分析，單純是核算會計數據，所以出現財務信息指導性不高、前瞻性不強的局面。并沒有向企業領導提供反映很多的經濟效益分析、企業融資籌資能力、成本測算、負債能力測算等，對企業領導行財務信息決策產生極大的不利作用。

該極小值點即為第個節點的效用函數最小值點。為確保通信質量，式10必須滿足約束條件：0<λC≤。將式1代入式10，可以得出方程的解為：

利用定點迭代算法求解，每個節點執行迭代方程：

根據式9和式11：

將式14帶入式13：

因此，當迭代次數足夠大時，系統必然達到納什均衡。

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

定義3納什均衡的存在性

證明：當納什均衡存在時，節點的效用函數必須滿足以下兩個條件：

1、節點的行為空間p是一個非空、封閉、有界的凸集。

2、效用函數U(p)在p內是連續且擬凹的。

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

定義4納什均衡的唯一性

證明：根據納什均衡的定義，當納什均衡唯一時，由U(p)得出的最優功率函數=()必須滿足以下3個條件：

1、正性：()>0；

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

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

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

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

③可擴展性：如果">1：

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

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

圖 3 控制流程圖

5 實驗與分析

表 1 參數表

在以下實驗中，基于隱馬爾可夫模型和非合作博弈的功率控制法簡稱HMM法；基于非合作博弈的功率控制法簡稱NCG法。

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

圖 4 傳輸效益比-價值系數

圖 5 傳輸功率-迭代次

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

圖 6 最大生命周期

圖7 平均信噪比

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

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

6 總結

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

[1] 董哲,宋紅霞.ZigBee-WiFi協同無線傳感網絡的節能技術[J].計算機工程與設計,2015,36(1):22-29

[2] 王會霞,李娜.無線傳感器網絡中基于能量感知的QoS路由協議[J].南京理工大學學報,2016,40(4):467-471

[3] 高德民,錢煥延,嚴筱永,等. 無線傳感器網絡最大生命期數據融合算法[J].南京理工大學學報,2012,36(1):55-60

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

[5] 劉保見,張效義,李青.基于演化博弈論的無線傳感網監測節點分群算法[J].計算機應用,2016,36(8):2157-2162

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

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

[8] 朱亞東,高翠芳.基于博弈論能耗均衡的無線傳感網絡路由算法[J].電子技術應用,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] 汪志偉,曹建福,鄭輯光.一種面向分簇無線傳感器網絡的多信道跨層協議[J].西安交通大學學報,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

國家自然科學基金委員會資助項目(41776142)

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

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