基于加權(quán)博弈的傳感網(wǎng)路由算法研究*

唐 勇

(廣西國際商務(wù)職業(yè)技術(shù)學(xué)院,廣西 南寧530007)

0 引言

傳感網(wǎng)由系列傳感器組成,傳感器節(jié)點(diǎn)感知信息后,通過節(jié)點(diǎn)相互轉(zhuǎn)發(fā)將信息從感知節(jié)點(diǎn)傳遞到目的終端.[1]由于具備便捷性、易構(gòu)性、低成本、分布式、自組織等優(yōu)良特性,被廣泛應(yīng)用于軍事、交通、醫(yī)療等眾多領(lǐng)域.[2]傳感節(jié)點(diǎn)大多采用電池供電方式,節(jié)點(diǎn)能量有限,如何節(jié)省能耗以延長節(jié)點(diǎn)壽命,是無線傳感網(wǎng)絡(luò)需要著重解決的問題.無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)會(huì)移動(dòng),網(wǎng)絡(luò)結(jié)構(gòu)不斷變化,快速判斷網(wǎng)絡(luò)結(jié)構(gòu),制定最優(yōu)路由策略,是節(jié)省能量有效途徑,也是傳感網(wǎng)路由目前研究的熱點(diǎn).

1 傳感器路由策略的研究分析

對(duì)無線傳感網(wǎng)絡(luò)路由的研究,學(xué)者的切入點(diǎn)有很多,研究成果也很豐富.宋海軍提出了基于分布式學(xué)習(xí)的穩(wěn)定路由策略,[3]策略將源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑看成多約束條件的路徑,利用約束算法優(yōu)化路徑,優(yōu)化了端到端的傳輸質(zhì)量.尚亞麗提出了基于能效傳播路由,[4]利用期望能耗來判斷轉(zhuǎn)發(fā)集結(jié)點(diǎn),減少評(píng)價(jià)發(fā)送能耗和無效發(fā)送,提高了傳感設(shè)備生存時(shí)間.蘇凡軍提出了基于信任度的節(jié)能機(jī)會(huì)路由算法,[5]利用節(jié)點(diǎn)間的信任度,減少惡意節(jié)點(diǎn)的聯(lián)通和惡意行為,提高了傳輸效率.陳明明等人提出了能耗均衡路由算法,[6]利用鄰居節(jié)點(diǎn)的剩余能量和位置,限定了參與路由的節(jié)點(diǎn)數(shù)量,節(jié)省了能量.崔亞楠等人提出了基于粒子群最優(yōu)算法的LEACH(Low Energy Adaptive Clustering Hierarchy)的改進(jìn)路由,[7]對(duì)經(jīng)典分簇算法進(jìn)行了改進(jìn),提高了路由效率和效能.林勇提出了基于鏈路質(zhì)量的無線傳感網(wǎng)絡(luò)路由算法,[8]綜合考慮發(fā)送時(shí)延和發(fā)送質(zhì)量,將兩者聯(lián)合起來,形成了一個(gè)混合路由.胡春安提出了基于鯨魚算法的無線傳感器網(wǎng)絡(luò)分簇路由算法,[9]形成了一個(gè)更加合理的簇頭——能量模型,減少了簇頭交換的頻率.任秀麗提出了一種無線傳感網(wǎng)中數(shù)據(jù)傳輸延時(shí)優(yōu)化的路由協(xié)議,[10]將有效探測占比與傳輸效率作為節(jié)點(diǎn)傳輸有效性,通過傳輸有效性來控制優(yōu)化傳輸?shù)陌l(fā)送排隊(duì),從而達(dá)到優(yōu)化整個(gè)網(wǎng)絡(luò)的目的.

當(dāng)代學(xué)者從不同的角度對(duì)傳感網(wǎng)路由進(jìn)行了優(yōu)化,從優(yōu)化結(jié)果來看,大多優(yōu)化了單方面或者兩方面的指標(biāo),對(duì)多個(gè)指標(biāo)同時(shí)優(yōu)化尚缺乏對(duì)策.

2 公平博弈的傳感網(wǎng)絡(luò)路由算法

2.1 參數(shù)定義

2.1.1 公平性

在傳感網(wǎng)絡(luò)中,公平性是指節(jié)點(diǎn)或者數(shù)據(jù)流公平使用信道轉(zhuǎn)發(fā)信息能力的比值,定義為FI(Fairness Index).

公式(1)中,T f為節(jié)點(diǎn)f的吞吐量,w(f)為權(quán)值.權(quán)值越大,需要獲得的更高發(fā)送權(quán)限.當(dāng)FI的值為1時(shí),實(shí)現(xiàn)絕對(duì)公平.

2.1.2 節(jié)點(diǎn)流服務(wù)指數(shù)

2.1.3 節(jié)點(diǎn)平均服務(wù)指數(shù)

S n是指節(jié)點(diǎn)n平均服務(wù)指數(shù),是周期時(shí)間內(nèi)m條流的加權(quán)平均.

2.1.4 鄰節(jié)點(diǎn)平均服務(wù)指數(shù)

AS n值指在t1至t2時(shí)間段里,節(jié)點(diǎn)n的所有鄰居節(jié)點(diǎn)獲得的平均服務(wù)指數(shù).

通過公式(1)～(4)可以推算,如實(shí)現(xiàn)了局部公平.|S n-S m|=0,實(shí)現(xiàn)了全局公平.

2.2 基于博弈論下的發(fā)送概率

在博弈論模型下,在無線傳感網(wǎng)中,如只有節(jié)點(diǎn)i發(fā)送信息,節(jié)點(diǎn)i成功占用信道,則其收益為A;若除站點(diǎn)i外,其他N-1個(gè)節(jié)點(diǎn)同時(shí)向某節(jié)點(diǎn)發(fā)送信息,信道產(chǎn)生沖突,則i的代價(jià)為B,若此時(shí)i選擇不傳輸,則收益為節(jié)省的能量減去傳送的機(jī)會(huì)的代價(jià),記為C,則站點(diǎn)i的效益函數(shù)為:

根據(jù)文獻(xiàn)[11]表明若站點(diǎn)采用隨即退避機(jī)制接入競爭,接入概率為:

其中,m為最大退避級(jí)數(shù),CW為競爭窗口.

P c(α-i)為站點(diǎn)i的條件碰撞概率,

2.3 退避時(shí)間

一個(gè)節(jié)點(diǎn)n的m條流,如果流i的S in過大,則說明流i獲得了更多的發(fā)送權(quán),對(duì)于其他的數(shù)據(jù)流來說不公平,可以提高此流的退避時(shí)間來降低流i的競爭力,實(shí)現(xiàn)節(jié)點(diǎn)n的局部公平性.相反,如果流i的S in過小,則縮短它的退避時(shí)間來提高流i的競爭力.同時(shí),一個(gè)節(jié)點(diǎn)的S n比AS n大,此節(jié)點(diǎn)大整體競爭能力過強(qiáng),延長節(jié)點(diǎn)退避時(shí)間降低競爭力.

在一個(gè)節(jié)點(diǎn)里,對(duì)于每個(gè)流的退避時(shí)間:

在公式(5)中,B代表退避基數(shù)時(shí)間,所有流的值都相同.隨著信息流發(fā)送,競爭不斷推進(jìn),出現(xiàn)了競爭不公平現(xiàn)象,節(jié)點(diǎn)流利用公式(6)調(diào)整S退避時(shí)間,實(shí)現(xiàn)公平競爭,整個(gè)網(wǎng)絡(luò)達(dá)到納什均衡狀態(tài).

2.4 基于加權(quán)博弈的算法機(jī)制

本文WGRA(Weighted game routing algorithm)算法機(jī)制如下:

(1)每個(gè)傳感節(jié)點(diǎn)維護(hù)一張路由表,表里包含id,Sin,Sn和ASn等參數(shù).鄰居節(jié)點(diǎn)相互傳輸交換Sin,用Sin參數(shù)調(diào)節(jié)退避時(shí)間.為了節(jié)約開銷,Sin不單獨(dú)傳送,Sin嵌入發(fā)送的數(shù)據(jù)流中.

(2)開始時(shí),所有的流、節(jié)點(diǎn)的競爭力都相同.節(jié)點(diǎn)每隔一個(gè)周期,統(tǒng)計(jì)本身每條流的服務(wù)指數(shù)Sin,計(jì)算節(jié)點(diǎn)Sn和ASn參數(shù)的值.

(3)當(dāng)FI=1時(shí),已經(jīng)實(shí)現(xiàn)絕對(duì)公平,所有節(jié)點(diǎn)按照當(dāng)前退避方式進(jìn)行退避,不另行調(diào)整,直接跳轉(zhuǎn)到第(6).當(dāng)FI≠1時(shí),進(jìn)入第(4).

(4)與鄰居節(jié)點(diǎn)交換Sin,Sn和ASn參數(shù).為了節(jié)約信息開銷,算法只在以下3種情況下觸發(fā)交換機(jī)制:①Sin,Sn和ASn的值出現(xiàn)了變化時(shí).②鄰居節(jié)點(diǎn)出現(xiàn)變化.③達(dá)到了信息交換周期最大值.

(5)利用退避時(shí)間公式BT=B×(1+S)×α*i,計(jì)算節(jié)點(diǎn)和流退避時(shí)間,調(diào)整競爭力.當(dāng)FI=1時(shí),跳轉(zhuǎn)到第(3).

(6)退避時(shí)間到,節(jié)點(diǎn)發(fā)送信息.

(7)簇節(jié)點(diǎn)周期時(shí)間T 進(jìn)行簇頭重新選舉,剩余能量最多者當(dāng)選為簇頭.

3 實(shí)驗(yàn)仿真

利用NS2(Network Simulator Version 2)對(duì)WGRA 算法進(jìn)行模擬分析.主要仿真參數(shù)見表1:

表1 主要仿真參數(shù)Tab.1 Main Simulation Parameters

為了進(jìn)行對(duì)比研究,選取文獻(xiàn)[12]可靠能效路由和文獻(xiàn)[13]時(shí)延路由進(jìn)行對(duì)比,主要分析平均能耗、網(wǎng)絡(luò)壽命、平均傳輸次數(shù)、端到端延時(shí)、數(shù)據(jù)包傳遞率5個(gè)方面的性能指標(biāo).

3.1 平均能耗

三種算法的平均能耗如從圖1所示,WGRA 平均能耗相對(duì)于REER 和DETR 更低,原因是WGRA算法采用了競爭博弈算法.依照博弈論,當(dāng)系統(tǒng)達(dá)到納什均衡點(diǎn)時(shí),系統(tǒng)的利益達(dá)到最大化.REER 通過能耗最低節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā),但能耗最低的節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí),存在信道競爭失敗情況.而DETR 算法主要是優(yōu)化時(shí)延,能耗相對(duì)較大.

3.2 網(wǎng)絡(luò)壽命

網(wǎng)絡(luò)壽命與能耗息息相關(guān),在能量定量情況下,能耗越高的網(wǎng)絡(luò)壽命越短.兩者之間非線性關(guān)系,傳感網(wǎng)中所有信息節(jié)點(diǎn)非持續(xù)性的定量地發(fā)送信息,網(wǎng)絡(luò)結(jié)構(gòu)也非持續(xù)性穩(wěn)定不變.從圖2看出,WGRA 綜合耗能最低,其網(wǎng)絡(luò)壽命時(shí)間越長,而REER 算法綜合耗能較高,網(wǎng)絡(luò)壽命較短.

圖1 平均能耗對(duì)比Fig.1 Average energy consumption comparison

圖2 網(wǎng)絡(luò)壽命對(duì)比Fig.2 Network life comparison

3.3 平均傳輸次數(shù)

在WGRA 算法中,首先考慮到信道的使用公平,通過相互博弈,局部和全局的加權(quán)最公平,使得信道有效利用率較高,無效探測較少,實(shí)現(xiàn)了平均傳輸次數(shù)較少.DETR 算法從傳輸路徑考慮,REER 算法從能量約束的條件下考慮,平均傳輸次數(shù)與能量相關(guān),REER 在一定程度上優(yōu)化了平均傳輸次數(shù),REER 的平均傳輸次數(shù)比DETR 的傳輸次數(shù)少.平均傳輸次數(shù)對(duì)比見圖3.

3.4 端到端延時(shí)

從圖4可以看出,WGRA 算法在延時(shí)方面也有較好的性能.端到端延時(shí)跟信道有效利用率有密切關(guān)系,WGRA 通過博弈算法使信道使用達(dá)到了最大值,無效發(fā)送比率降低,信道擁塞程度降低,端到端延時(shí)較少.REER 算法對(duì)延時(shí)沒有特殊處理,DETR 算法通過優(yōu)化路由,縮短了路由距離,端到端延時(shí)相對(duì)REER 算法較好.

圖3 平均傳輸次數(shù)對(duì)比Fig.3 Comparison of average transmission times

圖4 端到端延時(shí)對(duì)比Fig.4 End to end delay comparison

3.5 數(shù)據(jù)包傳遞率

WGRA、DETR 和REER 數(shù)據(jù)包傳遞方面的性能見圖5.WGRA 的數(shù)據(jù)包傳遞率相比DETR 和REER更具優(yōu)勢,數(shù)據(jù)傳遞率與信道有效利用率和傳輸距離有直接關(guān)系,信道有效利用率越高,數(shù)據(jù)傳遞率越高;傳輸距離越短,傳遞率越高.節(jié)點(diǎn)數(shù)據(jù)越多,節(jié)點(diǎn)越密集,傳輸距離越短,數(shù)據(jù)包傳遞率越高.

圖5 數(shù)據(jù)包傳遞率對(duì)比Fig.5 Packet delivery rate comparison

4 結(jié)語

針對(duì)無線傳感網(wǎng)絡(luò)路由,引進(jìn)博弈論使節(jié)點(diǎn)通過競爭以到納什均衡,從而實(shí)現(xiàn)節(jié)點(diǎn)對(duì)信道利用的最大化、能耗最小化,達(dá)到優(yōu)化路由的目的.近些年,學(xué)者對(duì)無線傳感網(wǎng)絡(luò)路由問題的研究有了新的方法,主要是引進(jìn)一些智能算法,使路由算法能實(shí)現(xiàn)自我學(xué)習(xí)、自我調(diào)節(jié),從而達(dá)到優(yōu)化路由的目的,這也是未來一段時(shí)間的研究熱點(diǎn).