劉 芳，馬爭(zhēng)先

(1.廣西財(cái)經(jīng)學(xué)院 實(shí)驗(yàn)教學(xué)中心，廣西 南寧 530003；2.格力電器股份有限公司，廣東 珠海 519070)

基于馬爾可夫博弈的WSN功率控制研究

劉 芳1，馬爭(zhēng)先2

(1.廣西財(cái)經(jīng)學(xué)院 實(shí)驗(yàn)教學(xué)中心，廣西 南寧 530003；2.格力電器股份有限公司，廣東 珠海 519070)

無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能量有限、工作環(huán)境復(fù)雜，易導(dǎo)致節(jié)點(diǎn)能量消耗不均，節(jié)點(diǎn)耗能不均將極大地縮短網(wǎng)絡(luò)生命周期。針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量有限和耗能不均問(wèn)題，建立了一種基于馬爾可夫博弈的功率控制模型。該模型引用分簇結(jié)構(gòu)，確定研究對(duì)象為簇頭節(jié)點(diǎn)；引入多信道技術(shù)，不同信道使用不同概率調(diào)節(jié)各自簇頭節(jié)點(diǎn)的發(fā)射功率來(lái)降低節(jié)點(diǎn)之間的相互干擾，進(jìn)行節(jié)點(diǎn)功率優(yōu)化；通過(guò)迭代方式進(jìn)行功率和概率補(bǔ)償，求解功率控制模型中的納什均衡，使節(jié)點(diǎn)發(fā)射功率達(dá)到最優(yōu)，達(dá)到整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)能量的均衡消耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。仿真結(jié)果表明，該模型在網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗的均勻程度、加強(qiáng)節(jié)點(diǎn)之間的合作、減少節(jié)點(diǎn)間信道競(jìng)爭(zhēng)和延長(zhǎng)網(wǎng)絡(luò)生命周期上都有顯著效果。

馬爾可夫博弈；功率控制；納什均衡；無(wú)線傳感器網(wǎng)絡(luò)

0 引 言

綜合無(wú)線通信、傳感器和分布式信息處理技術(shù)的無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)已經(jīng)成為當(dāng)前涉及多學(xué)科高度交叉、知識(shí)高度集成的前沿?zé)狳c(diǎn)研究領(lǐng)域。其在環(huán)境檢測(cè)、戰(zhàn)場(chǎng)監(jiān)視以及交通流量監(jiān)測(cè)等方面應(yīng)用廣泛[1-2]。然而，無(wú)線傳感器網(wǎng)絡(luò)由大量微型傳感器組成，傳感器節(jié)點(diǎn)不僅能量有限、成本高、體積小，而且節(jié)點(diǎn)繁多、工作環(huán)境復(fù)雜，更換電池或電池充電較難。如何在有限能量的條件下最大化網(wǎng)絡(luò)生命周期是傳感器網(wǎng)絡(luò)面臨的首要挑戰(zhàn)。

功率控制技術(shù)能夠有效降低能量消耗，是延長(zhǎng)傳感器網(wǎng)絡(luò)使用壽命的有效手段[3]。CLUSTERPOW路由協(xié)議[4]使用不同的傳輸功率對(duì)不同的目的節(jié)點(diǎn)能夠保證通信的最小發(fā)射功率，但節(jié)點(diǎn)要維護(hù)路由表，增加網(wǎng)絡(luò)能量的消耗。CLUSTERPOW-DSDV路由協(xié)議[5]對(duì)CLUSTERPOW路由協(xié)議進(jìn)行改進(jìn)，降低路由開(kāi)銷(xiāo)。Chaturvedi A等[6]對(duì)標(biāo)準(zhǔn)協(xié)議進(jìn)行改進(jìn)，提高了網(wǎng)絡(luò)吞吐量。Harold S等[7]提出的協(xié)議以最大傳輸功率計(jì)算發(fā)送數(shù)據(jù)需要的最小發(fā)射功率，以最小發(fā)射功率進(jìn)行通信，但最大功率會(huì)使能量消耗過(guò)多并增加信道相互干擾的概率。Vejarano G等[8]提出了一種分布式最優(yōu)化吞吐量的功率分配算法，增加網(wǎng)絡(luò)吞吐量。

上述算法和協(xié)議從節(jié)點(diǎn)單方面進(jìn)行能量?jī)?yōu)化，不能優(yōu)化整個(gè)網(wǎng)絡(luò)能量消耗。針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的耗能問(wèn)題，在現(xiàn)有功率控制算法和協(xié)議的基礎(chǔ)上，引入馬爾可夫博弈，給出了基于馬爾可夫博弈的功率控制模型(MGTPC)。該模型能夠有效調(diào)節(jié)能量的均衡消耗。

1 簇

無(wú)線傳感器網(wǎng)絡(luò)不同于傳統(tǒng)的無(wú)線網(wǎng)絡(luò)，其所有節(jié)點(diǎn)都向匯聚節(jié)點(diǎn)傳輸數(shù)據(jù)，屬于多對(duì)一的通信網(wǎng)絡(luò)。到匯聚節(jié)點(diǎn)距離不同可能導(dǎo)致能量使用不均，從而使局部節(jié)點(diǎn)過(guò)早死亡，引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化[9]。在傳感器網(wǎng)絡(luò)中，為保證原有覆蓋范圍內(nèi)的數(shù)據(jù)通信，節(jié)省節(jié)點(diǎn)能量，使用分簇式體系結(jié)構(gòu)[10]。網(wǎng)絡(luò)節(jié)點(diǎn)包括簇頭節(jié)點(diǎn)和簇內(nèi)節(jié)點(diǎn)(普通節(jié)點(diǎn))，簇頭節(jié)點(diǎn)對(duì)簇內(nèi)節(jié)點(diǎn)進(jìn)行管轄，如圖1所示。

圖1 簇結(jié)構(gòu)

傳感器網(wǎng)絡(luò)中研究的對(duì)象即為簇節(jié)點(diǎn)，簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)傳輸給簇節(jié)點(diǎn)，簇節(jié)點(diǎn)收集數(shù)據(jù)并直接或間接地向匯聚節(jié)點(diǎn)發(fā)送，簇節(jié)點(diǎn)之間的通訊是雙向的。無(wú)線傳輸過(guò)程存在噪音干擾，為抑制信噪比，節(jié)點(diǎn)會(huì)提高發(fā)射功率。當(dāng)所有節(jié)點(diǎn)都提高發(fā)射功率，將占有很大范圍的頻率，浪費(fèi)節(jié)點(diǎn)能量，并出現(xiàn)干擾現(xiàn)象。為了避免數(shù)據(jù)擁塞和相互干擾現(xiàn)象，假設(shè)每個(gè)簇被劃分為n個(gè)數(shù)據(jù)傳輸信道(數(shù)據(jù)傳輸)和1個(gè)控制信道(確定簇節(jié)點(diǎn)工作狀態(tài))。

節(jié)點(diǎn)啟動(dòng)后，若在一段時(shí)間內(nèi)沒(méi)有接收到其他節(jié)點(diǎn)發(fā)送的控制信號(hào)，節(jié)點(diǎn)將向其他節(jié)點(diǎn)發(fā)送控制信號(hào)，成為簇頭；節(jié)點(diǎn)若接收到控制信號(hào)，則不成為簇頭。簇頭形成后，其他節(jié)點(diǎn)向簇頭節(jié)點(diǎn)發(fā)送信息確定節(jié)點(diǎn)所在的簇。簇節(jié)點(diǎn)會(huì)把簇內(nèi)節(jié)點(diǎn)的相關(guān)信息保存到自己的節(jié)點(diǎn)列表中。簇形成后，簇內(nèi)節(jié)點(diǎn)必須通過(guò)單跳的形式給簇頭節(jié)點(diǎn)傳遞信息，簇頭節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳遞數(shù)據(jù)根據(jù)能量消耗的最優(yōu)方式來(lái)選擇單跳或多跳。若簇頭節(jié)點(diǎn)的能量消耗過(guò)多，簇頭節(jié)點(diǎn)將自動(dòng)成為普通節(jié)點(diǎn)，其他節(jié)點(diǎn)根據(jù)自身的能量情況，成為新的簇頭節(jié)點(diǎn)并進(jìn)行通信。簇內(nèi)的通信都是固定的單跳通信，如簇頭能量不多時(shí)可以自行調(diào)整。研究重點(diǎn)是簇頭之間的通信，研究對(duì)象也是簇頭節(jié)點(diǎn)。

2 功率控制模型

2.1 模 型

無(wú)線傳感器網(wǎng)絡(luò)的功率控制，引入多信道技術(shù)，采用不同功率進(jìn)行通信。若功率過(guò)大，會(huì)浪費(fèi)能量；反之會(huì)增加通信的信噪比，無(wú)法保證通信質(zhì)量；功率相近會(huì)產(chǎn)生干擾[11]。為解決上述問(wèn)題，通過(guò)建立馬爾可夫博弈模型進(jìn)行功率控制。不同信道使用不同概率進(jìn)行功率發(fā)送，從而避免能量浪費(fèi)，增加通信信噪比，降低節(jié)點(diǎn)之間的相互干擾程度。假設(shè)有C個(gè)簇節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有m個(gè)數(shù)據(jù)傳輸信道。馬爾可夫博弈模型為：

Γ=(A,S,P,G,R)

(1)

其中，A表示參與者的集合，研究的網(wǎng)絡(luò)場(chǎng)景中有n個(gè)簇節(jié)點(diǎn)，ai(ai∈A)表示第i(1≤i≤n)個(gè)參與者；S表示狀態(tài)集，S={0,1}，0表示節(jié)點(diǎn)不參與數(shù)據(jù)的轉(zhuǎn)發(fā)過(guò)程，1表示節(jié)點(diǎn)參與數(shù)據(jù)的轉(zhuǎn)發(fā)過(guò)程；P表示節(jié)點(diǎn)的發(fā)射功率，針對(duì)m個(gè)數(shù)據(jù)傳輸信道，用Pj表示第j(1≤j≤m)個(gè)數(shù)據(jù)傳輸信道的發(fā)射功率；G表示節(jié)點(diǎn)發(fā)射功率對(duì)應(yīng)的概率，Gj表示對(duì)應(yīng)Pj發(fā)送功率的概率；R表示參與者參與博弈后的收益，Ri表示第i(1≤i≤n)個(gè)參與者的收益。

2.2 參數(shù)計(jì)算

2.2.1 功率計(jì)算

2.2.2 概率計(jì)算

由于整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)幾乎都是分布在同一環(huán)境下，檢測(cè)相同對(duì)象，所以節(jié)點(diǎn)數(shù)據(jù)的重要程度也應(yīng)該一樣。不同信道的發(fā)射功率的概率根據(jù)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的大小來(lái)確定。用Byte-j表示第j(1≤j≤m)個(gè)信道中要傳輸數(shù)據(jù)的大小。信道j以功率Pj發(fā)送數(shù)據(jù)的概率為：

(2)

2.2.3 收益計(jì)算

收益R為衡量策略?xún)?yōu)劣和尋求納什均衡點(diǎn)的標(biāo)準(zhǔn)，它為節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)發(fā)送數(shù)據(jù)大小的函數(shù)。則：

R=f(E_remain)+g(Byte_send)

(3)

由于能量的單位為J(焦耳)，數(shù)據(jù)大小的單位是B(比特)，所以?xún)烧咧g無(wú)法直接計(jì)算，要通過(guò)歸一化處理使二者都變成無(wú)量綱的數(shù)據(jù)，從而有利于數(shù)學(xué)上的直接計(jì)算。

f(E_remain)=E_remain/E

(4)

g(Byte_send)w+1=

(5)

其中，w為通信次數(shù)。

3 博弈策略

在基于馬爾可夫博弈的功率控制模型中，針對(duì)節(jié)點(diǎn)發(fā)射功率選擇，通過(guò)概率的調(diào)節(jié)，進(jìn)行功率分配，采用迭代方法進(jìn)行功率和概率補(bǔ)償，從而使網(wǎng)絡(luò)收益函數(shù)達(dá)到最大，實(shí)現(xiàn)網(wǎng)絡(luò)功率優(yōu)化。

3.1 功率和概率的調(diào)節(jié)

節(jié)點(diǎn)的功率必須在保證通信質(zhì)量的前提下進(jìn)行討論，即Pmin≤P≤Pmax。發(fā)射功率不能太大，否則會(huì)對(duì)低發(fā)射功率的節(jié)點(diǎn)產(chǎn)生“壓制作用”，使公平性降低；發(fā)射功率如果太小，通信將不能更好地抑制噪聲，從而無(wú)法保證通信質(zhì)量。

控制信道發(fā)現(xiàn)當(dāng)前發(fā)射功率不適宜或者節(jié)點(diǎn)之間出現(xiàn)相互干擾的行為時(shí)，節(jié)點(diǎn)將自動(dòng)進(jìn)行發(fā)送功率和概率的補(bǔ)償。

P'=P+Δ(P)

(6)

G'=G+Δ(G)

(7)

其中，Δ(P)和Δ(G)分別為補(bǔ)償功率和補(bǔ)償概率。

(8)

(9)

節(jié)點(diǎn)發(fā)送功率和信道發(fā)射功率的概率通過(guò)上述公式依次迭代，直至最優(yōu)。

3.2 總體收益

在n個(gè)簇頭節(jié)點(diǎn)的網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)有m個(gè)數(shù)據(jù)傳輸信道。節(jié)點(diǎn)i的功率矩陣為：

(10)

通信時(shí)間間隔矩陣為：

(11)

狀態(tài)矩陣為：

(12)

其中，sij∈{0,1}。

則節(jié)點(diǎn)i的耗能為：

E_consumei=Pi×Si×ti=

(13)

節(jié)點(diǎn)i發(fā)送數(shù)據(jù)大小為：

Byte-sendi=[Byte-send1,Byte-send2,…,

(14)

節(jié)點(diǎn)的剩余能量為：

E_remaini=E-E_consumei

(15)

將式(14)和式(15)帶入式(3)求出節(jié)點(diǎn)i的收益：

Ri=f(E_remain)+g(Byte_send)

(16)

則：

(17)

通過(guò)迭代求出(P*,G*)，使之滿足R-all(P*,G*)≥R-all(P,G)，即R-all最大，此時(shí)(P*,G*)為納什均衡點(diǎn)。

4 仿真實(shí)驗(yàn)與分析

4.1 仿真環(huán)境

使用PRISM和MATLAB作為仿真工具，為評(píng)估基于馬爾可夫博弈的功率控制模型的性能，將已有的功率控制模型進(jìn)行比較。

實(shí)驗(yàn)參數(shù)如表1所示。

為了說(shuō)明基于馬爾可夫博弈的功率控制模型更具一般性，在目標(biāo)區(qū)域內(nèi)采用隨機(jī)生成節(jié)點(diǎn)的方法，所研究的節(jié)點(diǎn)均為簇頭節(jié)點(diǎn)。隨機(jī)生成80個(gè)節(jié)點(diǎn)的分布圖，如圖2所示。

4.2 網(wǎng)絡(luò)吞吐量

不同算法下,網(wǎng)絡(luò)有效吞吐量的比較如圖3所示。LSC-RPC[12]是一種基于跨層設(shè)計(jì)的能動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化的分簇功率控制算法；SMAC-CRPC[13]是一種通過(guò)調(diào)整發(fā)射功率的概率，減少信道沖突，實(shí)現(xiàn)功率控制的算法，對(duì)硬件設(shè)備的要求較高。AODV-802.11協(xié)議[14]是一種網(wǎng)絡(luò)經(jīng)典協(xié)議。由圖3可知，所有算法的吞吐量都是隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加而減小，因?yàn)殡S著節(jié)點(diǎn)的增加，節(jié)點(diǎn)信道之間競(jìng)爭(zhēng)比較激烈，影響了節(jié)點(diǎn)間的通信。

表1 實(shí)驗(yàn)參數(shù)

圖2 80個(gè)節(jié)點(diǎn)分布圖

圖3 網(wǎng)絡(luò)有效吞吐量對(duì)比

LSC-RPC從網(wǎng)絡(luò)跨層優(yōu)化的角度出發(fā)，綜合考慮能量效率和節(jié)點(diǎn)通信的公平性，所以該算法的有效吞吐量趨向于平滑。SMAC-CRPC協(xié)議根據(jù)最優(yōu)鄰居原則，采用調(diào)用機(jī)制維護(hù)節(jié)點(diǎn)調(diào)度信息，從而提高網(wǎng)絡(luò)吞吐量，但在節(jié)點(diǎn)數(shù)量少的情況下吞吐量變化波動(dòng)大。由于引入基于馬爾可夫博弈，加強(qiáng)了節(jié)點(diǎn)之間的合作，減少了節(jié)點(diǎn)之間的信道競(jìng)爭(zhēng)，而且隨著節(jié)點(diǎn)的增多變化趨勢(shì)趨于平穩(wěn)。

4.3 剩余能量

當(dāng)任意節(jié)點(diǎn)出現(xiàn)能量剩余低于40 J的時(shí)候，仿真實(shí)驗(yàn)終止，比較這種情況下的節(jié)點(diǎn)剩余能量。圖4給出了四種協(xié)議下，節(jié)點(diǎn)ID號(hào)為5,10,…,80的節(jié)點(diǎn)能量剩余圖。

圖4 節(jié)點(diǎn)能量剩余對(duì)比

由圖4可知，MGTPC中節(jié)點(diǎn)能量剩余曲線較平穩(wěn)，節(jié)點(diǎn)的能量剩余方差也相對(duì)較小，節(jié)點(diǎn)耗能更接近于均勻。MGTPC可以有效提高網(wǎng)絡(luò)節(jié)點(diǎn)能耗的均勻程度，有效延長(zhǎng)網(wǎng)絡(luò)生命周期。

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

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)耗能不均問(wèn)題，定義了基于節(jié)點(diǎn)功率和信道控制的博弈模型，成功引入馬爾可夫博弈，建立了基于馬爾可夫博弈的功率控制模型。仿真實(shí)驗(yàn)結(jié)果表明，與其他模型相比，所定義的模型有效地增加了網(wǎng)絡(luò)節(jié)點(diǎn)能耗的均勻程度，延長(zhǎng)了網(wǎng)絡(luò)生命周期，并提高了網(wǎng)絡(luò)的有效吞吐量。

[1] 馬爭(zhēng)先,董榮勝,王玉斌,等.針對(duì)竊聽(tīng)問(wèn)題的馬爾可夫博弈路由模型的研究[J].計(jì)算機(jī)科學(xué),2011,38(11):34-36.

[2] 張 法,Antonio Fernandez Anta,王 林,等.網(wǎng)絡(luò)能耗系統(tǒng)模型及能效算法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(3):603-615.

[3] 于 凱,謝志軍,金 光,等.基于功率控制的無(wú)線傳感器網(wǎng)絡(luò)MAC協(xié)議研究[J].傳感技術(shù)學(xué)報(bào),2013,26(9):1297-1302.

[4] 張文彬,楊孝宗.改進(jìn)的路由協(xié)議BLOCKING-COMPOW[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(16):89-92.

[5] Rahman J,Hasan M A M,Lslam M K B.Comparative analysis the performance of AODV,DSDV and DSR routing protocols in wireless sensor network[C]//Proceedings of the ICECE.[s.l.]:[s.n.],2012:283-286.

[6] Chaturvedi A,Tiwari D,Bhadoria R S,et al.Route discovery protocol for optimizing the power consumption in wireless ad-hoc network[C]//Proceedings of the CSNT.[s.l.]:[s.n.],2013:290-294.

[7] Harold S,Vijayalakshmi A.Enhanced power control MAC protocol for wireless ad hoc networks[C]//Proceedings of the ICCSP.[s.l.]:[s.n.],2012:6-11.

[8] Vejarano G,Wang Dexiang,Dubey R,et al.Distributed thro-ughput maximization in wireless networks using the stability region[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1713-1723.

[9] 董榮勝,馬爭(zhēng)先,郭云川,等.一種基于馬爾可夫博弈的能量均衡路由算法[J].計(jì)算機(jī)學(xué)報(bào)，2013,36(7):1500-1508.

[10] 劉新華,李方敏,方藝霖,等.一種基于鏈路級(jí)功率控制的分簇路由算法[J].計(jì)算機(jī)科學(xué)，2012,39(9):64-70.

[11] Azad A K M,Kamruzzaman J.Energy balanced transmission policies for wireless sensor networks[J].IEEE Transactions on Mobile Computing,2011,10(7):927-940.

[12] 劉 韜,李天瑞,談文蓉,等.基于分布式與聯(lián)合優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)匯聚機(jī)制[J].通信學(xué)報(bào),2015,36(7):18-30.

[13] 牛建軍,鄧志東,李 超.無(wú)線傳感器網(wǎng)絡(luò)分布式調(diào)度方法研究[J].自動(dòng)化學(xué)報(bào),2011,37(5):517-528.

[14] 沈 奔,秦 軍,萬(wàn) 麗.無(wú)線Ad Hoc網(wǎng)絡(luò)中AODV路由算法的研究與改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(3):150-153.

Investigation on WSN Power Control with Markov Game

LIU Fang1,MA Zheng-xian2

(1.Experimental Teaching Center,Guangxi University of Finance and Economics,Nanning 530003,China；2.Gree Electric Appliances,Inc.,Zhuhai 519070,China)

It can result in imbalance of energy consuming and shortening of network life that limited energy and complex work environment of network nodes in wireless sensor network.Aiming at limited energy and imbalance of energy consuming in wireless sensor networks,the power control model is constructed based on Markov game.Referencing cluster structure,research object are cluster head nodes.Then introducing multi-channel technology,the node power can be optimized through using different probability to adjust transmit power with different channel to reduce mutual interference between nodes.Method of adopting iteration computation is used to compensate transmitting power and probability to obtain the Nash equilibrium,to optimize node transmitting power,to balance network nodes energy consumption and prolong left-time of the network.The experimental results show that the model can effectively improve the uniformity of energy consumption of network nodes,strengthen cooperation between nodes,reduce node channel competition and prolong left-time of the network.

Markov game;power control;Nash equilibrium;wireless sensor network

2016-05-17

2016-09-09

時(shí)間：2017-03-07

廣西高校中青年教師基礎(chǔ)能力提升項(xiàng)目(KY2016LX314)；廣西教育科研項(xiàng)目(201106LX191)；廣西財(cái)經(jīng)學(xué)院校級(jí)課題(2016D101)

劉 芳(1984-)，女，碩士研究生，講師，研究方向?yàn)榫W(wǎng)絡(luò)安全和電子商務(wù)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0921.038.html

TP393

A

1673-629X(2017)04-0188-04

10.3969/j.issn.1673-629X.2017.04.042