唐 勇

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

0 引言

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

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

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

當代學者從不同的角度對傳感網(wǎng)路由進行了優(yōu)化,從優(yōu)化結果來看,大多優(yōu)化了單方面或者兩方面的指標,對多個指標同時優(yōu)化尚缺乏對策.

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

2.1 參數(shù)定義

2.1.1 公平性

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

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

2.1.2 節(jié)點流服務指數(shù)

2.1.3 節(jié)點平均服務指數(shù)

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

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

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

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

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

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

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

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

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

2.3 退避時間

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

在一個節(jié)點里,對于每個流的退避時間:

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

2.4 基于加權博弈的算法機制

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

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

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

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

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

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

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

(7)簇節(jié)點周期時間T 進行簇頭重新選舉,剩余能量最多者當選為簇頭.

3 實驗仿真

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

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

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

3.1 平均能耗

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

3.2 網(wǎng)絡壽命

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

圖1 平均能耗對比Fig.1 Average energy consumption comparison

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

3.3 平均傳輸次數(shù)

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

3.4 端到端延時

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

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

圖4 端到端延時對比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ù)傳遞率與信道有效利用率和傳輸距離有直接關系,信道有效利用率越高,數(shù)據(jù)傳遞率越高;傳輸距離越短,傳遞率越高.節(jié)點數(shù)據(jù)越多,節(jié)點越密集,傳輸距離越短,數(shù)據(jù)包傳遞率越高.

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

4 結語

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