基于加權博弈的傳感網路由算法研究*

唐 勇

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

0 引言

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

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

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

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

2 公平博弈的傳感網絡路由算法

2.1 參數定義

2.1.1 公平性

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

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

2.1.2 節點流服務指數

2.1.3 節點平均服務指數

S n是指節點n平均服務指數,是周期時間內m條流的加權平均.

2.1.4 鄰節點平均服務指數

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

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

2.2 基于博弈論下的發送概率

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

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

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

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

2.3 退避時間

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

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

在公式(5)中,B代表退避基數時間,所有流的值都相同.隨著信息流發送,競爭不斷推進,出現了競爭不公平現象,節點流利用公式(6)調整S退避時間,實現公平競爭,整個網絡達到納什均衡狀態.

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

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

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

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

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

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

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

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

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

3 實驗仿真

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

表1 主要仿真參數Tab.1 Main Simulation Parameters

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

3.1 平均能耗

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

3.2 網絡壽命

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

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

圖2 網絡壽命對比Fig.2 Network life comparison

3.3 平均傳輸次數

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

3.4 端到端延時

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

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

圖4 端到端延時對比Fig.4 End to end delay comparison

3.5 數據包傳遞率

WGRA、DETR 和REER 數據包傳遞方面的性能見圖5.WGRA 的數據包傳遞率相比DETR 和REER更具優勢,數據傳遞率與信道有效利用率和傳輸距離有直接關系,信道有效利用率越高,數據傳遞率越高;傳輸距離越短,傳遞率越高.節點數據越多,節點越密集,傳輸距離越短,數據包傳遞率越高.

圖5 數據包傳遞率對比Fig.5 Packet delivery rate comparison

4 結語

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