一種基于鏈路質(zhì)量的自維護(hù)拓?fù)淇刂撇┺乃惴?/h1>

2016-11-25 08:17:20辛敏潔劉偉靜郝曉辰汝小月

電子學(xué)報(bào)訂閱 2016年9期 收藏

關(guān)鍵詞：發(fā)射功率鏈路收益

陳 白,辛敏潔,劉偉靜,姚 寧,郝曉辰,汝小月

(燕山大學(xué)電氣工程學(xué)院,河北秦皇島 066004)

?

一種基于鏈路質(zhì)量的自維護(hù)拓?fù)淇刂撇┺乃惴?/p>

陳 白,辛敏潔,劉偉靜,姚 寧,郝曉辰,汝小月

(燕山大學(xué)電氣工程學(xué)院,河北秦皇島 066004)

針對無線傳感器網(wǎng)絡(luò)拓?fù)湫阅軆?yōu)化單一的問題,本文首先定義了表征雙向通信質(zhì)量的指標(biāo).其后將鏈路質(zhì)量,節(jié)點(diǎn)干擾,剩余能量均衡性等參數(shù)融入收益函數(shù),設(shè)計(jì)了一種基于鏈路質(zhì)量的自維護(hù)拓?fù)淇刂撇┺乃惴⊿MGLQ.理論證明該算法能保證各節(jié)點(diǎn)收斂到帕累托最優(yōu).仿真實(shí)驗(yàn)表明它能為網(wǎng)絡(luò)選擇通信質(zhì)量較好的鏈路,并降低能耗.

無線傳感器網(wǎng)絡(luò)；拓?fù)淇刂?；鏈路質(zhì)量；博弈論

1 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是一種多跳的自組織無線通信網(wǎng)絡(luò).拓?fù)浣Y(jié)構(gòu)是WSN的支撐構(gòu)架,有著非常重要的作用.由于節(jié)點(diǎn)的能量有限,目前對拓?fù)淇刂扑惴ǖ难芯恐饕杏谌绾窝娱L網(wǎng)絡(luò)生命期.然而隨著WSN日益廣泛的應(yīng)用,僅延長網(wǎng)絡(luò)生命期已經(jīng)不能滿足使用需求.因此,如何在延長網(wǎng)絡(luò)生命期時(shí)兼顧網(wǎng)絡(luò)其他性能對拓?fù)淇刂凭哂兄匾饬x.

拓?fù)湫阅芟嗷オ?dú)立又相互影響,針對這一特點(diǎn),博弈論被用來優(yōu)化網(wǎng)絡(luò)性能.文獻(xiàn)[1]引入虛擬博弈完成算法構(gòu)建過程,進(jìn)一步降低了博弈過程中信息交互的能耗.Cho等人設(shè)計(jì)的算法能兼顧網(wǎng)絡(luò)能耗與覆蓋率[2],然而,在能耗較低時(shí)網(wǎng)絡(luò)覆蓋性較差.文獻(xiàn)[3]以節(jié)能與降低干擾為目的,使用信干噪比構(gòu)造收益函數(shù);Miao等人致力于能耗與網(wǎng)絡(luò)延時(shí)的協(xié)同優(yōu)化[4],需要注意的是,網(wǎng)絡(luò)延時(shí)和干擾并不僅僅與拓?fù)湫阅芟嚓P(guān).這些算法重點(diǎn)提高了拓?fù)淠骋环矫娴男阅?其余性能的優(yōu)化只是作為附加效果,并不能對拓?fù)涞男阅茏龀稣w性提高.文獻(xiàn)[5]中提出的EBRGA算法融合了各層信息構(gòu)建博弈模型,對網(wǎng)絡(luò)性能做出較全面的優(yōu)化,但在構(gòu)建拓?fù)鋾r(shí)并沒有考慮網(wǎng)絡(luò)中鏈路的通信質(zhì)量.文獻(xiàn)[6]分析并證明了數(shù)據(jù)傳輸正確率對網(wǎng)絡(luò)性能的重要性,因此需要通過選擇通信質(zhì)量較好的鏈路以增加數(shù)據(jù)傳輸正確率.XTC算法僅僅定性地使用路徑長度來度量鏈路通信質(zhì)量.其后,節(jié)點(diǎn)間最小可達(dá)功率[7],期望傳輸數(shù)ETX[8]也被用作鏈路質(zhì)量的評價(jià)標(biāo)準(zhǔn).這些指標(biāo)從側(cè)面反映了當(dāng)前鏈路的通信質(zhì)量,并不能體現(xiàn)出通信情況的動(dòng)態(tài)變化.接收信號強(qiáng)度指標(biāo)(Received Signal Strength Indicator,RSSI)能反映當(dāng)前通信鏈路的信噪比,因此許多算法將其作為鏈路通信質(zhì)量的評價(jià)標(biāo)準(zhǔn)[9].然而RSSI并不能準(zhǔn)確表示當(dāng)前的鏈路質(zhì)量,因此需要更全面精準(zhǔn)的度量標(biāo)準(zhǔn)來衡量鏈路通信質(zhì)量.

針對上述情況,本文將多種性能參數(shù)融入收益函數(shù),設(shè)計(jì)了一種基于鏈路質(zhì)量的自維護(hù)拓?fù)淇刂撇┺乃惴⊿MGLQ.理論分析證明該算法能保證網(wǎng)絡(luò)連通并且網(wǎng)絡(luò)中所有節(jié)點(diǎn)均能達(dá)到帕累托最優(yōu)納什均衡狀態(tài).仿真結(jié)果表明SMGLQ算法所構(gòu)建的拓?fù)洳粌H具有良好的魯棒性和稀疏性,還能有效延長網(wǎng)絡(luò)生命期.

2 鏈路通信質(zhì)量評價(jià)指標(biāo)

目前鏈路質(zhì)量評價(jià)指標(biāo)中最常用的有三種:收包率PRR,鏈路質(zhì)量指標(biāo)LQI,信號接收強(qiáng)度指標(biāo)RSSI.其中,PRR最能明確反映鏈路通信質(zhì)量,然而,由于它是統(tǒng)計(jì)量,無法直接通過硬件測得.與PRR不同,RSSI和LQI均可通過硬件實(shí)時(shí)測得.與RSSI相比,LQI能更加準(zhǔn)確地描述鏈路通信質(zhì)量,但是LQI并不能及時(shí)將通信的變化反映到自身數(shù)值上.RSSI雖然能隨著通信環(huán)境的變動(dòng)而變化,但是其數(shù)值并不能精準(zhǔn)地表示當(dāng)前環(huán)境下的通信質(zhì)量.由此可知,單一的使用LQI或者RSSI表示鏈路通信質(zhì)量是不全面的,應(yīng)考慮綜合LQI的準(zhǔn)確性與RSSI的靈敏性來衡量鏈路通信質(zhì)量.

在實(shí)際通信中,低功耗無線模塊的通信模式通常具有不規(guī)則性,尤其是節(jié)點(diǎn)進(jìn)行地面通信時(shí),這個(gè)問題會更加顯著.鏈路的不對稱性體現(xiàn)在,當(dāng)節(jié)點(diǎn)對進(jìn)行相互通信時(shí),正反向的鏈路質(zhì)量不一致,因此導(dǎo)致正反向的收包率不一致.不對稱鏈路會引發(fā)一系列問題,比如在網(wǎng)絡(luò)層,不能正常建立路由樹;在MAC層,不能通過確認(rèn)消息進(jìn)行沖突避免等.鑒于此類原因,應(yīng)在拓?fù)錁?gòu)建過程中考慮鏈路的不對稱性,用正反兩向的鏈路質(zhì)量指標(biāo)綜合地表示該鏈路的通信質(zhì)量.網(wǎng)絡(luò)中任意節(jié)點(diǎn)對i,j之間進(jìn)行通信時(shí),j每次接收到i發(fā)送的數(shù)據(jù)后直接讀取相應(yīng)的RSSI(i,j)和LQI(i,j),其后求出鏈路ij的通信質(zhì)量CQ (Communication Quality)

(1)

當(dāng)i,j進(jìn)行相互通信時(shí),鏈路ij的雙向通信質(zhì)量可表示為

Bi-CQ(ij)=CQ(i,j)×CQ(j,i)

(2)

其中,RSSI(i,j)∈[RSSImin,0],LQI(i,j)∈[0,LQImax].λ,η表示其對應(yīng)部分在評價(jià)指標(biāo)CQ中所占的比例,說明了鏈路質(zhì)量指標(biāo)與信號接收強(qiáng)度指標(biāo)對CQ的影響.使用相同發(fā)射功率時(shí),RSSI(i,j)和LQI(i,j)的值越大,表明當(dāng)前的鏈路通信狀況越好.

3 博弈模型建立

3.1 基于鏈路質(zhì)量的拓?fù)淇刂撇┺哪Ｐ?/p>

拓?fù)湫阅芟嗷オ?dú)立又相互影響,而博弈論能很好的處理相互決策過程中的最優(yōu)化問題.因此本文使用博弈實(shí)現(xiàn)多種性能協(xié)同優(yōu)化的目標(biāo).基本的博弈三要素記為G={I,s,u},具體說明為:

(1)參與者集合I.所有傳感器節(jié)點(diǎn)作為博弈的參與者I可表示為I={1,2,…,N}.其中N是參與者的數(shù)量.

(2)策略空間s.策略集合s={s1,s2,…,sN}為其策略空間.其中si=(pi)為節(jié)點(diǎn)i的策略空間,pi∈P,P為節(jié)點(diǎn)的可選功率集合.

(3)收益函數(shù)u.本文從以下方面來設(shè)計(jì)任意節(jié)點(diǎn)i的收益函數(shù)ui.

①網(wǎng)絡(luò)連通性.對于任意拓?fù)涠?連通性都是必須滿足的首要性能.定義網(wǎng)絡(luò)連通因子為fi(pi,p-i).當(dāng)網(wǎng)絡(luò)連通時(shí)fi(pi,p-i)=1,反之fi(pi,p-i)=0.顯然,對于網(wǎng)絡(luò)中任意節(jié)點(diǎn)i∈I,且發(fā)射功率滿足pi>qi時(shí),fi(pi,p-i)≥fi(qi,p-i).

②節(jié)點(diǎn)發(fā)射功率.傳感器節(jié)點(diǎn)能量有限并且補(bǔ)給困難,因此,需要為剩余能量較低的節(jié)點(diǎn)分配較小的功率以延長節(jié)點(diǎn)生存時(shí)間.定義功率與節(jié)點(diǎn)剩余能量間的關(guān)系為pe(pi)=pi/Ei.其中,pi是節(jié)點(diǎn)i當(dāng)前發(fā)射功率,Ei為當(dāng)前剩余能量.

④剩余能量均衡性.當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量分布不均衡時(shí),能量較小的節(jié)點(diǎn)會較早死亡,從而對網(wǎng)絡(luò)性能造成影響.節(jié)點(diǎn)i單跳范圍內(nèi)所有鄰居的剩余能量方差可表示i的剩余能量均衡性

(3)

⑤節(jié)點(diǎn)度.節(jié)點(diǎn)度能影響網(wǎng)絡(luò)的魯棒性、稀疏性等.令節(jié)點(diǎn)度代價(jià)函數(shù)為xi(pi)=(ni(pi)-nei(pi))2.其中,當(dāng)節(jié)點(diǎn)i的發(fā)射功率為pi時(shí),nei(pi)表示期望節(jié)點(diǎn)度,ni(pi)表示節(jié)點(diǎn)當(dāng)前的鄰居個(gè)數(shù).

綜上所述,定義節(jié)點(diǎn)i的收益函數(shù)為

(4)

其中,α,β為權(quán)重因子且都是正數(shù).當(dāng)網(wǎng)絡(luò)連通時(shí)fi(pi,p-i)=1;當(dāng)網(wǎng)絡(luò)不連通時(shí),fi(pi,p-i)=0,因此,網(wǎng)絡(luò)不連通時(shí)的收益一定小于網(wǎng)絡(luò)連通時(shí)的收益.當(dāng)節(jié)點(diǎn)發(fā)射功率越大時(shí),節(jié)點(diǎn)度也會增加,干擾節(jié)點(diǎn)也可能會隨之增多,節(jié)點(diǎn)的剩余能量均衡性會降低;而如果發(fā)射功率過小,網(wǎng)絡(luò)可能無法保持連通狀態(tài),因此,這些因素是相互制約相互影響的.

3.2 基于鏈路質(zhì)量的拓?fù)淇刂撇┺姆治?/p>

定義2(順勢博弈與順勢函數(shù))[10]對策略型博弈G={I,s,u}而言,如果存在函數(shù)V:s→R,對于任意i∈I,pi∈si,qi∈si滿足V(pi,p-i)-V(qi,p-i)>0 ?ui(pi,p-i)-ui(qi,p-i)>0,那么G就是一個(gè)順勢博弈,函數(shù)V稱為G的順勢函數(shù).

定義3(帕累托最優(yōu))[10]如果不存在一個(gè)策略集合s′∈s使得任意i∈I滿足ui(s*)≤ui(s′),并且uj(s*)

定理1[10]如果策略型博弈G={I,s,u}是順勢博弈且V是其順勢函數(shù),那么使得V最大化的策略組合s*就是博弈G={I,s,u}的一個(gè)納什均衡.

定理2 基于鏈路質(zhì)量的拓?fù)淇刂撇┺哪Ｐ褪且粋€(gè)順勢博弈.

(5)

假定pi和qi在節(jié)點(diǎn)i可選功率集內(nèi),且滿足條件pi>qi.根據(jù)公式(4)所定義的收益函數(shù)可知,當(dāng)節(jié)點(diǎn)i分別選擇pi和qi作為功率時(shí)的收益差為

(6)

順勢函數(shù)之差為

ΔV=V(pi,p-i)-V(qi,p-i)

(7)

由于連通代價(jià)因子是單調(diào)的,因此當(dāng)pi>qi,fk(pi,p-i)>fk(qi,p-i)時(shí),Δui>0,此時(shí),Δui與ΔV同號;在fk(pi,p-i)=fk(qi,p-i)時(shí),ΔV的第一項(xiàng)為0,此時(shí),ΔV=Δui.由此根據(jù)定義2可知V(pi,p-i)是一個(gè)順勢函數(shù),G={I,s,u}是一個(gè)順勢博弈.

推論 基于鏈路質(zhì)量的拓?fù)淇刂撇┺哪Ｐ鸵欢ù嬖诩{什均衡解.

證明 由定理2可知該模型是順勢博弈,因此,使得順勢函數(shù)V(pi,p-i)最大化的策略組合就是納什均衡解.網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的發(fā)射功率pi∈(0,Pmax],因此,一定存在能夠使順勢函數(shù)V(pi,p-i)最大的策略組合.根據(jù)定理1,基于鏈路質(zhì)量的拓?fù)淇刂撇┺哪Ｐ鸵欢ù嬖诩{什均衡解.

4 拓?fù)淇刂扑惴⊿MGLQ

拓?fù)淇刂扑惴⊿MGLQ的實(shí)現(xiàn)需要建立在傳感器節(jié)點(diǎn)滿足如下幾個(gè)條件的前提上:①節(jié)點(diǎn)在部署時(shí)能量初值不同;②節(jié)點(diǎn)具有一定的運(yùn)算與儲存能力,可獲取自身的發(fā)射功率,接收功率以及當(dāng)前剩余能量狀態(tài);③節(jié)點(diǎn)的發(fā)射功率可調(diào),且最大功率一致;④互為鄰居的節(jié)點(diǎn)對滿足雙向通信;⑤每成功接收到一個(gè)數(shù)據(jù)包,節(jié)點(diǎn)都能直接測得其相應(yīng)的RSSI,LQI和接收功率pr.

SMGLQ共分為四個(gè)階段:鄰居發(fā)現(xiàn)階段,拓?fù)錁?gòu)建階段,功率確定階段和拓?fù)渚S護(hù)階段.

4.1 鄰居發(fā)現(xiàn)階段

網(wǎng)絡(luò)中所有節(jié)點(diǎn)依次以最大發(fā)射功率Pmax廣播Hello消息,其中包含節(jié)點(diǎn)的ID編號,當(dāng)前發(fā)射功率Pmax,節(jié)點(diǎn)當(dāng)前能量值Ei.任意節(jié)點(diǎn)j收到節(jié)點(diǎn)i發(fā)送的Hello消息后,先讀取相應(yīng)的RSSI(i,j)和LQI(i,j),然后計(jì)算i與其正常通信時(shí)所需的最小發(fā)射功率pmin(i→j).節(jié)點(diǎn)j將自身的ID編號,當(dāng)前發(fā)射功率Pmax,當(dāng)前能量值Ej,pmin(i→j),RSSI(i,j)和LQI(i,j)打包為Ack消息回復(fù)給i.當(dāng)i收到Ack消息之后,先讀取相應(yīng)的RSSI(j,i)和LQI(j,i),然后解析Ack消息,按照式(2)計(jì)算鏈路ij的通信質(zhì)量;最后按表1的形式將節(jié)點(diǎn)j加入自己的鄰居列表Ti當(dāng)中.其中,各節(jié)點(diǎn)的初始收益值均為-∞.

表1 節(jié)點(diǎn)i的鄰居列表

4.2 拓?fù)錁?gòu)建階段

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰居列表都建立完成以后,節(jié)點(diǎn)i按照pmin(i→j)的值對Ti中的所有鄰居(m個(gè))進(jìn)行升序排序.在排序過程中,計(jì)算并統(tǒng)計(jì)當(dāng)前發(fā)射功率下的鄰居節(jié)點(diǎn)數(shù)目ni(pmin(i→j)),期望節(jié)點(diǎn)度nei(pmin(i→j)),鏈路質(zhì)量Lq(ij).之后,網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)以符號T標(biāo)記自身,開始博弈過程,依次判斷自身當(dāng)前功率對網(wǎng)絡(luò)連通狀況造成的影響.i設(shè)置參數(shù)numi=1,從鄰居列表中第一個(gè)鄰居Ti(1)開始算起,此時(shí)i的功率為pi(i→Ti(1)),判斷網(wǎng)絡(luò)當(dāng)前的連通狀況:⑴如果網(wǎng)絡(luò)在當(dāng)前功率時(shí)不連通,令連通因子為0,修改Ti中相應(yīng)的收益.此時(shí),如果numi=m,那么i維持原功率;如果numi

對于網(wǎng)絡(luò)中任意節(jié)點(diǎn)i,當(dāng)numi≠1時(shí),設(shè)置numi=numi-1且pi(i→Ti(numi)),判斷此時(shí)網(wǎng)絡(luò)是否連通:如果不連通,那么設(shè)置numi=numi+1,此時(shí)節(jié)點(diǎn)i的發(fā)射功率為pi(i→Ti(numi)),并用F標(biāo)記自身.如果此時(shí)網(wǎng)絡(luò)連通,則功率等級不變.標(biāo)記自身為F的點(diǎn)i,如果Ti中具有滿足pi(i→j)>pi(i→Ti(numi))的任意節(jié)點(diǎn)j,則按照收益函數(shù)修改Ti中對應(yīng)的收益.當(dāng)任意節(jié)點(diǎn)i的都以F標(biāo)記過自身之后,博弈結(jié)束.

4.3 功率確定階段

在經(jīng)過拓?fù)錁?gòu)建階段之后,節(jié)點(diǎn)i計(jì)算并存儲了滿足網(wǎng)絡(luò)連通的各級功率所對應(yīng)的收益.i比較所有收益,根據(jù)最佳回應(yīng)策略設(shè)置自身功率pi

ui(pi,p-i)=maxui(pi(i→j),p-i(i→j)),j∈Ti

(8)

研究表明,RSSI與發(fā)送節(jié)點(diǎn)的發(fā)射功率近似成線性關(guān)系.因此,當(dāng)網(wǎng)絡(luò)中任意節(jié)點(diǎn)按式(8)重新確定了自己的發(fā)射功率后,鏈路的通信質(zhì)量雖然沒有改變,但是度量指標(biāo)Bi-CQ會發(fā)生變化.節(jié)點(diǎn)i按自身當(dāng)前發(fā)射功率pi廣播一條包含自身ID的請求消息Request.當(dāng)j收到Request后,讀取該信息相應(yīng)的RSSI(i,j)和LQI(i,j),計(jì)算CQ(i,j)并將其與pj一起打包成Ack消息發(fā)送給i.i收到Ack消息后,讀取相應(yīng)的RSSI(j,i)和LQI(j,i),解析Ack消息,按照式(2)計(jì)算Bi-CQ(i,j),更新Ti.4.4 拓?fù)渚S護(hù)階段

拓?fù)錁?gòu)建完成后,隨著網(wǎng)絡(luò)運(yùn)行,節(jié)點(diǎn)剩余能量會變得不均衡.此外,可能出現(xiàn)的各種突發(fā)狀況也會影響鏈路的通信質(zhì)量,造成誤碼率增加甚至于數(shù)據(jù)包丟失.因此,應(yīng)隨著實(shí)際情況調(diào)整拓?fù)?

(1)當(dāng)節(jié)點(diǎn)i檢測到自身能量等級降低之后,使用Pmax廣播剩余能量檢測請求消息(SED)取當(dāng)前通信范圍內(nèi)鄰居節(jié)點(diǎn)的剩余能量.認(rèn)為沒有回復(fù)SED消息的節(jié)點(diǎn)已死亡,標(biāo)記為D.

(2)在網(wǎng)絡(luò)運(yùn)行過程中,每收到一個(gè)數(shù)據(jù)包,都計(jì)算相應(yīng)的CQ.如果節(jié)點(diǎn)i與其鄰居j進(jìn)行通信時(shí),鏈路質(zhì)量突然從Bi-CQ(i,j)大幅度下降,那么i標(biāo)記j為可疑節(jié)點(diǎn)SN,鏈路ij為可疑鏈路SL后繼續(xù)通信.如果在后續(xù)5次通信過程中,鏈路質(zhì)量恢復(fù)到原有水平,則撤銷對節(jié)點(diǎn)j以及鏈路ij的標(biāo)注,繼續(xù)正常通信.而如果在后續(xù)5次通信過程中,鏈路質(zhì)量持續(xù)下降或者發(fā)生很大波動(dòng),則中斷鏈路ij,i從鄰居列表中刪除節(jié)點(diǎn)j.

在這兩種情況下,節(jié)點(diǎn)i根據(jù)收集到的最新數(shù)據(jù)重新博弈,選擇當(dāng)前狀態(tài)下使得收益最大的功率作為發(fā)射功率pi.判斷此時(shí)網(wǎng)絡(luò)連通性:如果網(wǎng)絡(luò)連通,那么i采用pi繼續(xù)通信;如果此時(shí)網(wǎng)絡(luò)已不連通,那么節(jié)點(diǎn)i清空自身鄰居列表并以Pmax廣播網(wǎng)絡(luò)重構(gòu)消息(Reconsitution),標(biāo)記自身為T.收到重構(gòu)消息的節(jié)點(diǎn)清空自身鄰居列表并以Pmax廣播重構(gòu)消息,標(biāo)記自身為T;已標(biāo)記自身為T的節(jié)點(diǎn)不再廣播重構(gòu)消息.當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都以T標(biāo)記自身之后開始重新構(gòu)建拓?fù)?轉(zhuǎn)至4.1.

5 SMGLQ算法證明與性能分析

5.1 算法證明

為便于書寫,將最大功率拓?fù)浔硎緸镚max,SMGLQ算法構(gòu)建的拓?fù)浣Y(jié)構(gòu)表示為GSMGLQ.

定理3 SMGLQ能使節(jié)點(diǎn)收斂至納什均衡.

證明 推論表明基于鏈路質(zhì)量的拓?fù)淇刂撇┺哪Ｐ痛嬖诩{什均衡,其對應(yīng)的順勢函數(shù)如式(4),即V是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的收益總和.由于在功率確定階段,網(wǎng)絡(luò)中任意節(jié)點(diǎn)均選擇了能使自身收益最大的功率,所以,這些收益總和是最大值.至此,各節(jié)點(diǎn)功率組合就是SMGLQ的納什均衡解.

定理4 如果Gmax連通,那么GSMGLQ也連通.

證明 在定理3中已經(jīng)證得在執(zhí)行完SMGLQ后網(wǎng)絡(luò)中各節(jié)點(diǎn)均收斂至納什均衡.設(shè)節(jié)點(diǎn)i達(dá)到納什均衡時(shí)的功率為pi,那么肯定存在pi

ui(pi,p-i)-ui(Pmax,p-i)≥0

(9)

由于Pmax一定能保證網(wǎng)絡(luò)連通,因此

ui(Pmax,p-i)

(10)

采用反證法,假設(shè)i選擇功率pi時(shí)網(wǎng)絡(luò)不連通,

(11)

此時(shí)

(12)

定理5 SMGLQ能收斂到帕累托最優(yōu).

證明 由無線傳感器網(wǎng)絡(luò)的特性可知,當(dāng)節(jié)點(diǎn)發(fā)射功率增大或減小時(shí),其干擾節(jié)點(diǎn)數(shù)目,鄰居節(jié)點(diǎn)數(shù)目隨之增大或減小,因此?Ri(pi)/?pi>0,?ni(pi)/?pi>0.下面首先分析收益函數(shù).

(1)當(dāng)nei(pi)=max(4ω×EDev(i),ni(pi))=ni(pi)時(shí),對收益函數(shù)進(jìn)行求導(dǎo)

(13)

(2)當(dāng)nei(pi)=max(4ω×EDev(i),ni(pi))=4×EDev(i)時(shí),對收益函數(shù)進(jìn)行求導(dǎo)

(14)

因此,收益函數(shù)ui(pi,p-i)與發(fā)射功率pi的關(guān)系為

(15)

因此,ui(pi,p-i)是發(fā)射功率pi的單調(diào)減函數(shù).

首先根據(jù)納什均衡定義可知,沒有一個(gè)節(jié)點(diǎn)可以通過降低自身功率來獲取更高的收益,如果強(qiáng)行降低功率只會降低自身收益,甚至使得網(wǎng)絡(luò)無法連通.其次,不存在k(k≥2)個(gè)節(jié)點(diǎn)在保證網(wǎng)絡(luò)連通的條件下同時(shí)降低發(fā)射功率來增加自身收益.這是因?yàn)槿绻嬖诠?jié)點(diǎn)i可以通過降低自身發(fā)射功率pi,從而減小ni(pi)來增加收益,那么必然存在節(jié)點(diǎn)j為了保持網(wǎng)絡(luò)連通性而增大自身發(fā)射功率pj,由于收益函數(shù)uj(pj,p-j)是減函數(shù),那么j的收益必然減小,更何況k個(gè)節(jié)點(diǎn)同時(shí)降低自身功率以獲取更大收益了.因此不存在任意節(jié)點(diǎn)在能不降低其他節(jié)點(diǎn)收益的情況下增大自身收益.即SMGLQ算法達(dá)到的納什均衡是帕累托最優(yōu)的.

5.2 性能分析

λ,η表示其對應(yīng)部分在CQ中的比重,確定它們的取值對CQ有很大意義,首先通過仿真實(shí)驗(yàn)分析λ,η對CQ的影響規(guī)律.將50個(gè)節(jié)點(diǎn)隨機(jī)分布在500m×500m的區(qū)域,將Bi-CQ作為鏈路質(zhì)量指標(biāo),采用EG模型搭建拓?fù)?設(shè)定最大傳輸范圍為150m.令λ=10,分別為η賦值為1,2,5,7,8,10,進(jìn)行10次仿真實(shí)驗(yàn)對比網(wǎng)絡(luò)性能,選取最佳的參數(shù)組合,如圖1所示.由于節(jié)點(diǎn)發(fā)射功率與最大發(fā)射功率的比值表明了發(fā)射功率的相對大小,不受最大發(fā)射功率值的限制,因此,本文均采用發(fā)射功率與最大發(fā)射功率的比值表示節(jié)點(diǎn)發(fā)射功率.由圖1可知,當(dāng)λ=10時(shí),網(wǎng)絡(luò)平均節(jié)點(diǎn)度隨著η的增大而減小;圖2表示網(wǎng)絡(luò)中的平均發(fā)射功率隨著η的增大而增大.在圖3中,網(wǎng)絡(luò)中平均功率的方差隨著η的增加而增大.因此,綜合拓?fù)浣Y(jié)構(gòu)的各方面性能,選取組合λ=10,η=5.

由于EBRGA也是以節(jié)點(diǎn)自身各項(xiàng)性能的相互制約相互影響來構(gòu)建拓?fù)涞?因此將EBRGA作為對比算法;VGEB算法無需節(jié)點(diǎn)信息實(shí)時(shí)交互,可最大程度降低能耗,因此也將其作為對比算法,驗(yàn)證SMGLQ拓?fù)淇刂扑惴ǖ目尚行院陀行?首先分析收益函數(shù)中α,β值對拓?fù)湫阅艿挠绊?隨機(jī)布撒100個(gè)節(jié)點(diǎn)在500m×500m的區(qū)域內(nèi),最大傳輸半徑設(shè)為150m.求取性能參數(shù),通過5次實(shí)驗(yàn)數(shù)據(jù)取平均值進(jìn)行分析來確定α,β的值.因此,首先令α=1,通過改變β的取值來觀察參數(shù)α,β對網(wǎng)絡(luò)性能的影響,如圖4所示.從圖4(a),4(b)中可以看出,β=100時(shí)平均發(fā)射功率與平均發(fā)射功率方差都較小,也就是說網(wǎng)絡(luò)具有較小能耗.此時(shí)平均鏈路質(zhì)量較高,平均節(jié)點(diǎn)度曲線也較為穩(wěn)定.因此,將權(quán)重因子設(shè)置為α=1,β=100.

EBRGA算法中并沒有拓?fù)渚S護(hù)部分,VGEB算法也并沒有給出詳細(xì)的維護(hù)過程.為方便比對,在拓?fù)浣Y(jié)構(gòu)和性能分析(1)～(6)的仿真比較過程中并未加入拓?fù)渚S護(hù)環(huán)節(jié).在500m×500m的區(qū)域內(nèi)隨機(jī)布點(diǎn)100個(gè),最大傳輸半徑設(shè)為150m.分別執(zhí)行SMGLQ,EBRGA和VGEB算法,得到的拓?fù)浣Y(jié)構(gòu)如圖5所示.可知,由于這三種算法選擇鏈路時(shí)遵守的準(zhǔn)則不同,所形成的拓?fù)浣Y(jié)構(gòu)也不同.EBRGA拓?fù)滏溌份^為密集,VGEB拓?fù)漭^為稀疏,SMGLQ拓?fù)鋭t位于兩者之中.

在300m×300m的區(qū)域內(nèi)分別布點(diǎn)50,60,70,80,90,100個(gè),以100m為傳輸半徑.分別執(zhí)行100次EBRGA算法,VGEB算法,SMGLQ算法來構(gòu)建拓?fù)?對網(wǎng)絡(luò)進(jìn)行性能分析.

(1)平均節(jié)點(diǎn)度比較.由圖6可知,EBRGA算法的平均節(jié)點(diǎn)度隨網(wǎng)絡(luò)規(guī)模變化不大,這是由于其期望節(jié)點(diǎn)度為3.隨著節(jié)點(diǎn)密度的增大,VGEB算法的平均節(jié)點(diǎn)度呈下降趨勢,而SMGLQ算法的平均節(jié)點(diǎn)度不斷上升,在網(wǎng)絡(luò)密度較大時(shí),SMGLQ算法能更好的保證網(wǎng)絡(luò)魯棒性.

(2)平均干擾節(jié)點(diǎn)數(shù)比較.隨著網(wǎng)絡(luò)密度的增大,圖7中的平均干擾節(jié)點(diǎn)數(shù)曲線都在上升.其中,EBRGA算法干擾過大,VGEB算法干擾節(jié)點(diǎn)過少降低了網(wǎng)絡(luò)魯棒性,SMGLQ拓?fù)涞母蓴_節(jié)點(diǎn)數(shù)目居中,能降低干擾并增強(qiáng)網(wǎng)絡(luò)魯棒性.

(3)平均發(fā)射功率比較.從圖8中可以看出,平均發(fā)射功率曲線都隨著網(wǎng)絡(luò)密度的增大而減小.VGEB算法僅以降低能耗為優(yōu)化目標(biāo),因此具有較低的發(fā)射功率.與EBRGA算法相比,SMGLQ算法在通過降低發(fā)射功率減小網(wǎng)絡(luò)能耗方面具有更好的性能.

(4)平均發(fā)射功率方差比較.如圖9所示,隨著網(wǎng)絡(luò)密度的增大,節(jié)點(diǎn)平均發(fā)射功率方差呈遞減趨勢.VGEB算法的收益函數(shù)僅與功率相關(guān),因此在能耗均衡性方面也具有優(yōu)勢.SMGLQ拓?fù)涞钠骄l(fā)射功率方差小于EBRGA拓?fù)?因此,SMGLQ算法在能耗均衡方面優(yōu)于EBRGA算法.

(5)平均鏈路質(zhì)量比較.EBRGA,VGEB算法中并沒有定義鏈路質(zhì)量,為方便對比,本部分采用節(jié)點(diǎn)使用最大功率時(shí)各鏈路對應(yīng)的評價(jià)指標(biāo)Lq為EBRGA與VGEB中的鏈路質(zhì)量賦值.從圖10中可以看出,隨著網(wǎng)絡(luò)密度的增大,這三種算法所構(gòu)建的拓?fù)渲墟溌焚|(zhì)量均增大.相比而言,SMGLQ拓?fù)涞钠骄溌焚|(zhì)量更大一些.圖11中的平均鏈路質(zhì)量方差曲線則表明,在網(wǎng)絡(luò)密度較小時(shí),由于可供選擇的鏈路較少,鏈路質(zhì)量相差就比較大;當(dāng)可選鏈路較多時(shí),鏈路質(zhì)量比較均衡.

(6)剩余能量方差比較.如圖12所示,平均剩余能量方差曲線隨節(jié)點(diǎn)數(shù)目的增加而減小.其中SMGLQ算法的平均剩余能量方差最小,這說明它可以為節(jié)點(diǎn)選擇剩余能量較為均衡的鄰居.

(7)網(wǎng)絡(luò)生命期比較.本文定義當(dāng)網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)超過總節(jié)點(diǎn)數(shù)的20%以后,網(wǎng)絡(luò)死亡.將100個(gè)節(jié)點(diǎn)布撒在區(qū)域內(nèi),分別使用EBRGA算法,SMGLQ算法,VGEB算法構(gòu)建拓?fù)?由圖13可以看出,首先出現(xiàn)死亡節(jié)點(diǎn)的是EBRGA拓?fù)?隨著網(wǎng)絡(luò)運(yùn)行,這三種拓?fù)涞乃劳龉?jié)點(diǎn)數(shù)目都不斷增加.無維護(hù)環(huán)節(jié)的SMGLQ算法與VGEB算法生命期相差不大.拓?fù)渚S護(hù)的目的就是使網(wǎng)絡(luò)始終處于最優(yōu)或者接近最優(yōu)的狀態(tài),最終達(dá)到延長網(wǎng)絡(luò)生命期的目的.由圖13可看出加入維護(hù)環(huán)節(jié)后,SMGLQ算法的生命期被顯著延長,這也說明了拓?fù)渚S護(hù)的必要性.

6 結(jié)論

本文首先定義了一種表征鏈路雙向通信質(zhì)量的鏈路通信質(zhì)量評價(jià)指標(biāo).其后,構(gòu)建了拓?fù)淇刂撇┺哪Ｐ?該模型將網(wǎng)絡(luò)的各項(xiàng)性能指標(biāo)融入收益函數(shù).理論分析并證明了該模型具有納什均衡解.最后,本文設(shè)計(jì)了一種基于鏈路質(zhì)量的自維護(hù)拓?fù)淇刂撇┺乃惴⊿MGLQ,理論分析表明執(zhí)行SMGLQ算法能保證網(wǎng)絡(luò)連通,還能使所有節(jié)點(diǎn)收斂到帕累托最優(yōu).同時(shí),仿真結(jié)果顯示SMGLQ算法不僅能選擇通信質(zhì)量好的鏈路,還能有效減小網(wǎng)絡(luò)能耗,最主要的是,能顯著地延長網(wǎng)絡(luò)生命期.

[1]Hao X C,Zhang Y X,Jia N,et al.Virtual game-based energy balanced topology control algorithm for wireless sensor networks[J].Wireless Personal Communications,2013,69(4):1289-1308.

[2]Cho H H,Tseng F H,Shih T K,et al.Ak-cooperative analysis in game-based WSN environment [J].Lecture Notes in Electrical Engineering,2014,260:1215-1225.

[3]Guoyan Yang,Xin Guan.A non-cooperative game theoretic approach to energy-efficient power control in wireless sensor networks[J].International Journal of Future Generation Communication and Networking,2014,7(1):169-180.

[4]Miao X N,Xu G.Cooperative differential game model based on trade-off between energy and delay for wireless sensor networks[J].Annals of Operations Research,2013,206(1):297-310.

[5]郝曉辰,張亞曉,劉彬,等.一種能耗均衡的傳感器網(wǎng)絡(luò)可靠拓?fù)洳┺乃惴╗J].軟件學(xué)報(bào),2011,22 (Suppl1):1-12.Hao Xiao-chen,Zhang Ya-xiao,Liu Bin,et al.Energy-balanced and reliable topology control game algorithm for sensor networks [J].Journal of Software,2011,22 (Suppl1):1-12.(in Chinese)

[6]王紹青,聶景楠.一種無線傳感器網(wǎng)絡(luò)性能評估及優(yōu)化方法[J].電子學(xué)報(bào),2010,38(4):882-886.

WANG Shao-qing,NIE Jian-nan.An approach of performance analysis and optimization for wireless sensor networks[J].Acta Electronica Sinica,2010,38(4):882-886.(in Chinese)

[7]Xing G,Lu C,Jia X,et al.Localized and configurable topology control in lossy wireless sensor networks[J].Ad Hoc Networks,2013,11(4):1345-1358.

[8]Dinh Duong Mai,Anh Tai Tran,Myung Kyun Kim.Measuring link quality based on ETX metric in multi-hop wireless networks[J].Advanced Science and Technology Letters,2014,46(Networking and Communication 2014):115-118.

[9]呂濤,施偉斌.無線傳感器網(wǎng)絡(luò)自適應(yīng)功率調(diào)整機(jī)制研究[J].信息技術(shù),2014,(3):134-136.

Lü Tao,Shi Wei-bin.Adaptive power adjustment mechanism for wireless sensor networks[J].Information Technology,2014(3):134-136.(in Chinese)

[10]Xiao Mi,Shao Xin-yu,Gao Liang,Luo Zhen.A new methodology for multi-objective multidisciplinary design optimization problems based on game theory[J].Expert Systems with Applications,2015,42(3):1602-1612.

陳 白 女,1981生于浙江磐安.河北省燕山大學(xué)電氣工程學(xué)院實(shí)驗(yàn)師.研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?、信道分配算?

E-mail:chenbai@ysu.edu.cn

辛敏潔 女,1990年生于陜西寶雞,河北省燕山大學(xué)電氣工程學(xué)院碩士研究生.研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?

E-mail:xlxmjysu@126.com

SMGLQ:A Self-Maintaining Topology Control Game Algorithm Based on Link Quality

CHEN Bai,XIN Min-jie,LIU Wei-jing,YAO Ning,HAO Xiao-chen,RU Xiao-yue

(InstituteofElectricalEngineering,YanshanUniversity,Qinhuangdao,Hebei066004,China)

In order to overcome the problem that the topology performance optimization of wireless sensor network is single,an indicator which can represent the bi-directional communication quality of a link is defined.Then the link communication quality,node interference and balance of surplus energy are integrated into the utility function.Finally,a self-maintaining topology control game algorithm based on link quality (SMGLQ) is proposed.The theoretical analysis proves that SMGLQ algorithm can converge to a Pareto optimal.Simulation results show that SMGLQ chooses the links with better communication quality for the network.Moreover,it can reduce the energy consumption.

wireless sensor network (WSN); topology control; link quality; game theory

2014-07-18;

2015-05-25;責(zé)任編輯:梅志強(qiáng)

國家自然科學(xué)基金(No.61403336); 河北省自然科學(xué)基金(No.F2015203342); 燕山大學(xué)青年教師自主研究計(jì)劃課題(No.13LGA008,No.15LGB007)

TP393

A

0372-2112 (2016)09-2227-08

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.030

猜你喜歡

發(fā)射功率鏈路收益

家紡“全鏈路”升級

紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10

天空地一體化網(wǎng)絡(luò)多中繼鏈路自適應(yīng)調(diào)度技術(shù)

移動(dòng)通信(2021年5期)2021-10-25 11:41:48

螃蟹爬上“網(wǎng)” 收益落進(jìn)兜

今日農(nóng)業(yè)(2020年20期)2020-12-15 15:53:19

放大轉(zhuǎn)發(fā)中繼器降低發(fā)射功率的選擇策略研究

無線互聯(lián)科技(2017年24期)2018-01-22 10:39:24

淺談AC在WLAN系統(tǒng)中的應(yīng)用

中國管理信息化(2017年18期)2018-01-04 18:41:52

基于功率分配最優(yōu)中繼選擇的研究

物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11

2015年理財(cái)“6宗最”誰能給你穩(wěn)穩(wěn)的收益

金色年華(2016年1期)2016-02-28 01:38:19

東芝驚爆會計(jì)丑聞 憑空捏造1518億日元收益

IT時(shí)代周刊(2015年8期)2015-11-11 05:50:38

基于3G的VPDN技術(shù)在高速公路備份鏈路中的應(yīng)用

中國交通信息化(2014年3期)2014-06-05 03:07:09

高速光纖鏈路通信HSSL的設(shè)計(jì)與實(shí)現(xiàn)

自動(dòng)化與儀表(2014年10期)2014-02-26 08:21:17

電子學(xué)報(bào)2016年9期

電子學(xué)報(bào)的其它文章

語義推薦算法研究綜述

基于傳染病模型的LPA特征閥值社團(tuán)劃分方法

一種基于稀疏約束的穩(wěn)健波束形成方法

基于路徑自動(dòng)分割的測試數(shù)據(jù)生成方法

面向運(yùn)動(dòng)目標(biāo)檢測的粒子濾波視覺注意力模型

觸發(fā)器可靠度計(jì)算的F-PTM方法