一種基于非合作博弈的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)功率控制算法*

朱 赟，徐友云，潘成康，管少華

(1.贛南師范學(xué)院 物理與電子信息學(xué)院，江西 贛州341000;2.解放軍理工大學(xué)通信工程學(xué)院，江蘇南京210007;3.中國(guó)移動(dòng)通信研究院，北京100053)

0 引言

在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)可通過(guò)動(dòng)態(tài)調(diào)整其發(fā)射功率，在保證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不變、雙向連通或者多連通的前提下，使網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗最小，從而延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間［1］。文獻(xiàn)［2］為分析無(wú)線(xiàn)網(wǎng)絡(luò)的功率控制問(wèn)題，提出了基于線(xiàn)性成本函數(shù)的非合作功率控制博弈模型。文獻(xiàn)［3］給出了一種無(wú)線(xiàn)自組織網(wǎng)中基于線(xiàn)性成本函數(shù)的功率控制博弈算法。但采用線(xiàn)性成本函數(shù)作為代價(jià)函數(shù)，使得節(jié)點(diǎn)為追求收益而不斷增大發(fā)射功率，從而加劇節(jié)點(diǎn)間分組碰撞概率［4］。在保證無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的連通性前提下，將容量最大化和網(wǎng)絡(luò)半徑最小作為設(shè)計(jì)目標(biāo)，本文提出了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的功率控制博弈算法GTPC(gametheoretic power control algorithm for WSNs)，采用非線(xiàn)性成本函數(shù)以有效壓制傳感器節(jié)點(diǎn)采用較大發(fā)射功率，從而接近全局最優(yōu)來(lái)提高擴(kuò)大網(wǎng)絡(luò)容量和節(jié)點(diǎn)的能量效率，以延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

1 算法描述

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的功率控制問(wèn)題可看作非合作博弈問(wèn)題，則用策略式博弈Γ=〈N，{pi}，{Ji}〉可表示，其中網(wǎng)絡(luò)中的節(jié)點(diǎn)N={1，2，…，n}，每個(gè)節(jié)點(diǎn)的策略空間{pi}為{0，pmax}，pmax為最大發(fā)射功率，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)根據(jù)收益函數(shù)確定使自己收益最大的策略［5］。設(shè)定無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)均勻分布在平面的監(jiān)測(cè)區(qū)域中，所有節(jié)點(diǎn)采用半雙工通信后可自行調(diào)整自己的發(fā)射功率，且該網(wǎng)絡(luò)中不存在單向鏈路。為了簡(jiǎn)化收益函數(shù)的設(shè)計(jì)，在滿(mǎn)足網(wǎng)絡(luò)容量最大化和網(wǎng)絡(luò)半徑最小的前提下使收益函數(shù)不依賴(lài)節(jié)點(diǎn)采用何種信號(hào)處理方式，本文采用Ji(pi)=Ui(pi)－Ci(pi)來(lái)定義收益函數(shù)，其中效益函數(shù)Ui(pi)與代價(jià)函數(shù)Ci(pi)分別對(duì)應(yīng)博弈中參與方的收入和成本。根據(jù)系統(tǒng)吞吐量目標(biāo)，效益函數(shù)參照仙農(nóng)公式可簡(jiǎn)化表示為［3］

其中，SIRi為節(jié)點(diǎn)k接收來(lái)自發(fā)送節(jié)點(diǎn)i報(bào)文時(shí)有用信號(hào)與干擾信號(hào)的比值，σ2為高斯信道噪聲，hik為節(jié)點(diǎn)i與k間的鏈路增益為在節(jié)點(diǎn)i發(fā)送報(bào)文期間在其干擾范圍內(nèi)的節(jié)點(diǎn)發(fā)送報(bào)文而對(duì)節(jié)點(diǎn)k接收?qǐng)?bào)文所產(chǎn)生的干擾總和，Ni為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。

代價(jià)函數(shù)采用如下形式的非線(xiàn)性成本函數(shù)

其中，ai，bi皆為正代價(jià)系數(shù)，可根據(jù)節(jié)點(diǎn)i的當(dāng)前剩余能量與初始能量的比例進(jìn)行設(shè)置。

由于每個(gè)節(jié)點(diǎn)的策略空間定義在［0，pmax］上，則該策略空間為歐幾里德空間中非空的、閉的、有界的凸集。Ji(pi)在pi上連續(xù)，且由式(1)和式(2)可得

根據(jù)極大值定理得

其中，代價(jià)系數(shù)ai和bi需滿(mǎn)足

定理1 在GTPC算法的非合作博弈中存在納什均衡。

證明:在GTPC算法的非合作博弈Γ=〈N，{pi}，}Ji}〉中，策略空間{pi}為歐幾里德空間中非空的、閉的、有界的凸集。對(duì)Ji(pi)進(jìn)行二次求導(dǎo)可得

定理2 在GTPC算法中非合作博弈的納什均衡是唯一的。

證明:根據(jù)式(4)，給出函數(shù) f(pi)=

可見(jiàn)f(pi)符合標(biāo)準(zhǔn)函數(shù)的條件。納什均衡可以通過(guò)反映對(duì)應(yīng)rj(pj)=來(lái)描述［6］，則在GTPC算法的非合作博弈中，rj(pj)可用映射f表示。由于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都可以通過(guò)調(diào)整功率來(lái)獲得一定的收益，則rj(pj)＞0。由于在標(biāo)準(zhǔn)函數(shù)中不動(dòng)點(diǎn)是唯一的，根據(jù)博弈論存在納什均衡的條件，則在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的分布式功率控制博弈過(guò)程中存在唯一的納什均衡點(diǎn)，該納什均衡點(diǎn)就是節(jié)點(diǎn)的最佳發(fā)射功率p*。定理2得證。

通過(guò)分布式迭代可確定各傳感器節(jié)點(diǎn)的發(fā)射功率［1］，具體步驟如下:

1)在初始化時(shí)刻 t=0，pi(0)=pmax，i∈N;

2)在控制幀中添加本地發(fā)射功率域，則節(jié)點(diǎn)在發(fā)送控制幀的過(guò)程中可將自己的發(fā)射功率信息告知相鄰節(jié)點(diǎn);

3)當(dāng)時(shí)刻t時(shí)，在給定相鄰節(jié)點(diǎn)發(fā)射功率條件節(jié)點(diǎn)i的收益函數(shù)達(dá)到最大時(shí)節(jié)點(diǎn)i的發(fā)射功率為ri(t)=arg max Ji(pi(t)，p－i(t－1));

4)節(jié)點(diǎn)i的最優(yōu)發(fā)射功率pi(t)=min［ri(t)］。

當(dāng)給定代價(jià)系數(shù)時(shí)，GTPC算法可快速地產(chǎn)生一組收斂于最小的納什均衡的功率解向量，且在功率消耗上是Pareto有效的。

2 仿真分析

在實(shí)驗(yàn)仿真中將GTPC算法在網(wǎng)絡(luò)軟件GloMoSim中進(jìn)行性能分析。將350個(gè)節(jié)點(diǎn)分布在邊長(zhǎng)為1 000 m的矩形平面，最大發(fā)射功率為10 mW，背景噪聲為－120 dBm，ai，bi分別設(shè)為0.6，0.4。圖1給出各算法中的節(jié)點(diǎn)平均能耗比較，其中CPC算法采用保證網(wǎng)絡(luò)連通的最小發(fā)射功率，“max”為最大發(fā)射功率，“Linear”為式(2)中采用線(xiàn)性成本函數(shù)［3］?？梢?jiàn)采用CPC算法時(shí)能耗最低，而采用“max”時(shí)各節(jié)點(diǎn)的能耗明顯高于其他算法。在非合作博弈功率控制中當(dāng)所有節(jié)點(diǎn)的發(fā)射功率收斂后，節(jié)點(diǎn)的效益函數(shù)達(dá)到最大，此時(shí)任何節(jié)點(diǎn)單獨(dú)改變發(fā)射功率，并不能提高其效益函數(shù)值，則任何節(jié)點(diǎn)都沒(méi)有改變策略的積極性，可見(jiàn)所有節(jié)點(diǎn)的發(fā)射功率向量即策略組合達(dá)到納什均衡。而采用GTPC算法時(shí)，采用較大的發(fā)射功率需要相比更高的成本，從而有效抑制節(jié)點(diǎn)采用較大發(fā)射功率，因此節(jié)點(diǎn)的能耗效率有所提高。

圖2給出的是節(jié)點(diǎn)成功發(fā)送比例在不同負(fù)載下的性能比較。隨著業(yè)務(wù)負(fù)荷的增大，節(jié)點(diǎn)間報(bào)文碰撞問(wèn)題的加劇及隱終端問(wèn)題的惡化，從而導(dǎo)致節(jié)點(diǎn)成功發(fā)送的比例明顯降低。采用最大發(fā)射功率使得節(jié)點(diǎn)間的通信競(jìng)爭(zhēng)更為激烈。而采用網(wǎng)絡(luò)連通的最小發(fā)射功率值并不能減少隱終端問(wèn)題帶來(lái)的干擾，而且，由于在接收節(jié)點(diǎn)中信號(hào)的接收信噪比較小，未能提高抗干擾能力。采用非合作功率控制博弈后，可根據(jù)信道情況動(dòng)態(tài)地調(diào)整發(fā)射功率，得到較為適合的發(fā)射功率，從而降低節(jié)點(diǎn)間干擾。在保證良好的網(wǎng)絡(luò)連通性下，GTPC算法相比“Linear”可有效抑制較大發(fā)射功率，從而進(jìn)一步緩解報(bào)文碰撞問(wèn)題以提高節(jié)點(diǎn)成功發(fā)送比例。

圖1 節(jié)點(diǎn)平均能耗Fig 1 Average energy consumption of node

圖2 節(jié)點(diǎn)成功發(fā)送比例Fig 2 Successful transmission ratio of node

圖3顯示了系統(tǒng)吞吐率隨節(jié)點(diǎn)負(fù)載變化的情況。在節(jié)點(diǎn)負(fù)載較低時(shí)，系統(tǒng)吞吐率隨節(jié)點(diǎn)報(bào)文到達(dá)速率的增加而線(xiàn)性提高，當(dāng)網(wǎng)絡(luò)負(fù)荷達(dá)到一定程度后達(dá)到最大飽和吞吐率。而當(dāng)負(fù)荷繼續(xù)增大，系統(tǒng)吞吐率均呈下降趨勢(shì)。由于CPC算法采用網(wǎng)絡(luò)連通的最小發(fā)射功率發(fā)送數(shù)據(jù)，導(dǎo)致接收節(jié)點(diǎn)處的接收信號(hào)強(qiáng)度也隨之減小，導(dǎo)致大量的報(bào)文不能被正確接收，因而其最大系統(tǒng)吞吐率較小。利用信道容量作為功率控制的收益函數(shù)，通過(guò)節(jié)點(diǎn)間的博弈使得信道容量達(dá)到最大。而GTPC算法中可有效壓制較大的發(fā)射功率，從而使得傳感器節(jié)點(diǎn)的數(shù)據(jù)傳輸范圍和載波偵聽(tīng)?zhēng)鄬?duì)有所縮小，以提高網(wǎng)絡(luò)的空分復(fù)用度，并允許更多的鄰居節(jié)點(diǎn)對(duì)進(jìn)行通信來(lái)提高系統(tǒng)吞吐率。

圖3 系統(tǒng)吞吐率Fig 3 Throughput rate of the system

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

在本文中以網(wǎng)絡(luò)容量為設(shè)計(jì)目標(biāo)，提出了一種無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的功率控制博弈算法，采用非線(xiàn)性成本函數(shù)根據(jù)網(wǎng)絡(luò)信道干擾情況動(dòng)態(tài)地調(diào)整節(jié)點(diǎn)發(fā)射功率，并證明了其納什均衡的存在性和唯一性。理論分析和仿真實(shí)驗(yàn)表明:該算法可有效壓制傳感器節(jié)點(diǎn)采用較大發(fā)射功率，從而緩解節(jié)點(diǎn)競(jìng)爭(zhēng)激烈狀況以提高網(wǎng)絡(luò)容量，并可提高節(jié)點(diǎn)的能量效率來(lái)延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

［1］Rasti M，Sharafat A R，Seyfe B.Pareto-efficient and goal-driven power control in wireless networks:A game-theoretic approach with a novel pricing scheme［J］.IEEE/ACM Transactions on Networking，2009，17(2):556－569.

［2］Long Chengnian，Zhang Qian.Non-cooperative power control for wireless Ad Hoc networks with repeated games［J］.IEEE Selected Areas in Communications，2007，25(6):1101－1112.

［3］孫 強(qiáng)，李臘元，陳年生.一種基于博弈論模型的Ad Hoc網(wǎng)絡(luò)功率控制算法［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32(1):169－176.

［4］Zhao Liqiang，Guo Le，Zhang Guopeng.An energy-efficient MAC protocol for WSNs:Game-theoretic constraint optimization［C］∥11th IEEE International Conference on Communication Systems Singapore，ICCS2008，2008:114－118.

［5］Jorswieck E A，Larsson E G，Luise M.Game theory in signal processing and communications［J］.IEEE Signal Processing Magazine，2009，26(5):117－132.

［6］Sengupta S，Chatterjee M，Kwiat K A.A game theoretic framework for power control in wireless sensor networks［J］.IEEE Transactions on Computers，2010，59(2):231－242.