一種基于WSN時(shí)變性與節(jié)點(diǎn)剩余能量均衡的機(jī)會(huì)路由算法

丁 男 譚國(guó)真 由 笛 張 偉

(大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 大連 116023)

1 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)，與移動(dòng)Ad hoc網(wǎng)絡(luò)和無線MESH網(wǎng)絡(luò)一樣，在很多重要領(lǐng)域被認(rèn)為是一種方便的、經(jīng)濟(jì)的解決方案，比如交通監(jiān)控、環(huán)境監(jiān)測(cè)、軍事安全等。

在實(shí)際應(yīng)用中，多數(shù)用于 WSN的多跳路由算法是從有線網(wǎng)絡(luò)中演變過來的。因此，在此類路由算法的設(shè)計(jì)過程中，往往需要假設(shè) WSN是一個(gè)拓?fù)湟阎木W(wǎng)絡(luò)，其通信鏈路是靜態(tài)的、不變的。數(shù)據(jù)報(bào)文在利用該類路由算法進(jìn)行傳輸過程時(shí)，是基于已建立好的路經(jīng)進(jìn)行傳輸?shù)模瑳]有考慮網(wǎng)絡(luò)拓?fù)浼案鞴?jié)點(diǎn)狀態(tài)的動(dòng)態(tài)變化[1,2]。

機(jī)會(huì)路由是近幾年所提出的一種新的基于多跳的動(dòng)態(tài)路由。文獻(xiàn)[3]根據(jù)無線信道的衰減和干擾特性，認(rèn)為WSN 中節(jié)點(diǎn)正確接收的數(shù)據(jù)報(bào)文服從一定的概率分布，并提出一種基于機(jī)會(huì)的傳輸方式，即當(dāng)無線信道的條件合適時(shí)，無線節(jié)點(diǎn)才進(jìn)行通信。機(jī)會(huì)路由機(jī)制可以提高數(shù)據(jù)報(bào)文在無線通信網(wǎng)絡(luò)中傳輸性能，但是動(dòng)態(tài)建立路徑也給機(jī)會(huì)路由算法在設(shè)計(jì)上帶來了難題[4]。

目前已有的工作主要集中在兩方面研究。一方面是集中在為數(shù)據(jù)報(bào)文在傳輸過程中尋找基于WSN時(shí)變特性下的最短路徑的策略與相應(yīng)路由算法研究。文獻(xiàn)[5]通過結(jié)合圖論和網(wǎng)絡(luò)流理論，針對(duì)最大網(wǎng)絡(luò)流最短路徑問題為機(jī)會(huì)路由的吞吐率建立了優(yōu)化模型，為機(jī)會(huì)路由動(dòng)態(tài)建立傳輸路徑的相關(guān)研究提供了理論依據(jù)。文獻(xiàn)[6]將數(shù)據(jù)包傳輸過程模仿蜜蜂采蜜的過程，設(shè)計(jì)了一個(gè) RSSI(Received Signal Strength Indicator)機(jī)會(huì)路由算法，根據(jù)傳輸中各節(jié)點(diǎn)的信號(hào)強(qiáng)度動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的機(jī)會(huì)選擇概率，以機(jī)會(huì)概率值選擇報(bào)文所能到達(dá)的最佳節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。文獻(xiàn)[7]引入蟻群優(yōu)化算法，將 WSN中數(shù)據(jù)傳輸路徑的動(dòng)態(tài)選擇，模擬螞蟻覓食過程中在路徑上殘留的信息素誘導(dǎo)后面的螞蟻盡快地找到到達(dá)目的地的過程。另一方面是以考慮網(wǎng)絡(luò)中節(jié)點(diǎn)能耗問題為核心的動(dòng)態(tài)路徑建立策略及相應(yīng)機(jī)會(huì)路由算法研究。文獻(xiàn)[8]提出了兩種考慮能耗的適用于機(jī)會(huì)傳輸?shù)膫鬏敳呗?，一種是利用閾值判斷的方法在動(dòng)態(tài)建立傳輸路徑時(shí)，排除網(wǎng)絡(luò)中剩余能量少的節(jié)點(diǎn)，該策略適用于所有機(jī)會(huì)傳輸方式，另一種策略是針對(duì)無線傳感器網(wǎng)絡(luò)傳輸具有中心性的特點(diǎn)，將網(wǎng)絡(luò)中節(jié)點(diǎn)以接收節(jié)點(diǎn)為中心，分成同心環(huán)型層次，在考慮剩余能量的基礎(chǔ)上，使得各節(jié)點(diǎn)能量消耗分配更合理。文獻(xiàn)[9]結(jié)合基于已建立傳輸路徑整體的剩余能量問題，利用蟻群優(yōu)化算法提出了一個(gè)EEABR(Energy Efficient Ant Based Routing)的路由算法。

分析上述研究，機(jī)會(huì)路由在動(dòng)態(tài)建立路徑過程中，網(wǎng)絡(luò)傳輸?shù)淖疃搪窂絾栴}與網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量的均衡問題既相互影響，又相互制約。一些學(xué)者雖然考慮這兩方面的關(guān)系，提出一些機(jī)會(huì)路由算法，主要是在考慮節(jié)點(diǎn)能耗的同時(shí)利用蟻群優(yōu)化等啟發(fā)式算法給出傳輸路徑選擇策略[10,11]。目前，缺少針對(duì)時(shí)變特性的網(wǎng)絡(luò)路徑優(yōu)化與節(jié)點(diǎn)剩余能量均衡問題協(xié)同考慮的理論模型與分析方法。因?yàn)樵诳紤]網(wǎng)絡(luò)時(shí)變特性，傳統(tǒng)靜態(tài)網(wǎng)絡(luò)相關(guān)理論是失效的[12,13]。

針對(duì)上述問題，本文結(jié)合熱力學(xué)第2定律，在考慮網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量以及在選擇數(shù)據(jù)報(bào)文最優(yōu)傳輸路徑的時(shí)變性等因素前提下，對(duì) WSN數(shù)據(jù)傳輸過程進(jìn)行理論分析與描述，提出了機(jī)會(huì)熵模型，并以此為依據(jù)，結(jié)合蟻群優(yōu)化(ACO)算法，提出了一個(gè)新的路由算法 ATDOP(ACO for Time Dependent Opportunistic-routing Protocol)。

2 網(wǎng)絡(luò)模型與問題分析

2.1 網(wǎng)絡(luò)模型

本文假設(shè)網(wǎng)絡(luò)中各節(jié)點(diǎn)隨機(jī)分布在一個(gè)矩形區(qū)域內(nèi)，并且具有如下性質(zhì)：(1)網(wǎng)絡(luò)內(nèi)Sink節(jié)點(diǎn)惟一，部署在網(wǎng)絡(luò)中央位置，其余傳感器節(jié)點(diǎn)部署后不再移動(dòng)，并且各節(jié)點(diǎn)的地理位置信息不可知；(2)每個(gè)節(jié)點(diǎn)有惟一的標(biāo)識(shí)；(3)所有節(jié)點(diǎn)平等，具有相同的計(jì)算、通信能力以及初始能量。

結(jié)合上面假設(shè)，給出網(wǎng)絡(luò)模型的如下定義：

定義2通信距離。在圖G中，通信距離，記為hu，表示節(jié)點(diǎn)u與Sink節(jié)點(diǎn)之間的通信跳數(shù)，用以表示距離Sink節(jié)點(diǎn)的距離。

定義3網(wǎng)絡(luò)壽命。本文將從 WSN開始工作直到網(wǎng)絡(luò)內(nèi)第1個(gè)節(jié)點(diǎn)死去時(shí)，Sink節(jié)點(diǎn)所接收到的所有數(shù)據(jù)報(bào)文，其各自傳輸過程中到達(dá)Sink節(jié)點(diǎn)的跳數(shù)累計(jì)之和，定義為網(wǎng)絡(luò)壽命。

定義 4節(jié)點(diǎn)o的鄰居集，記為N(o)=ui(ui∈U,eoui∈E)，表示與節(jié)點(diǎn)o直接通信的節(jié)點(diǎn)ui集合。

2.2 時(shí)間依賴的最短路徑

在圖G中，任意節(jié)點(diǎn)o與Sink節(jié)點(diǎn)s之間路徑(o,u1,…,ui,…,s)，為了能夠讓數(shù)據(jù)報(bào)文沿著向Sink節(jié)點(diǎn)接近的方向快速傳遞，根據(jù)文獻(xiàn)[3]所提出的機(jī)會(huì)概率模型，在考慮網(wǎng)絡(luò)的時(shí)變特性，我們提出了一個(gè)在節(jié)點(diǎn)o的鄰居節(jié)點(diǎn)中選擇下一跳節(jié)點(diǎn)方法。

式中hu代表u節(jié)點(diǎn)距離s節(jié)點(diǎn)的距離。wu(t)表示在t時(shí)刻，節(jié)點(diǎn)o與其鄰居集合N(o)中節(jié)點(diǎn)u的通信權(quán)重，其值在實(shí)驗(yàn)中可根據(jù)隨機(jī)概率模型獲得，例如文獻(xiàn)[4]，在實(shí)際應(yīng)用中，可以通過測(cè)量信號(hào)強(qiáng)度獲得。

為了便于描述與分析該問題，結(jié)合網(wǎng)絡(luò)中基于時(shí)間依賴的最短路徑的研究[13]，本文對(duì)機(jī)會(huì)路由的最短傳輸路徑進(jìn)行如下規(guī)劃：

其中D(o,s,t)表示，在t時(shí)刻下，由源點(diǎn)o到目的點(diǎn)s的傳輸路徑。

定理1在無線傳感器網(wǎng)絡(luò)中，采用機(jī)會(huì)傳輸方式的WSN是一個(gè)no-FIFO的網(wǎng)絡(luò)。

證明假設(shè)該 WSN拓?fù)鋱DG(V,E)，如圖 1所示。其中V={o,u1,u2,u3,u4,u5,u6,u7,s},E={e(o,u1),e(u1,u2),e(u1,u3),e(u2,u3),e(u2,u4),e(u3,u4),e(u3,u5),e(u4,u6),e(u5,u7),e(u6,s),e(u7,s)}各節(jié)點(diǎn)從接收?qǐng)?bào)文或產(chǎn)生報(bào)文，到將該數(shù)據(jù)轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)需要Δt時(shí)間。假設(shè)在t1時(shí)刻，由o節(jié)點(diǎn)發(fā)送一數(shù)據(jù)報(bào)文M1，在t1+Δt時(shí)刻，o節(jié)點(diǎn)發(fā)送M2。當(dāng)M1達(dá)到u1時(shí)，u1選擇u2作為M1的下一跳。當(dāng)M1到達(dá)u2時(shí)，由于能量消耗等問題，u1,u2之間的通信權(quán)重發(fā)生變化，u1在轉(zhuǎn)發(fā)M2時(shí)選擇u3作為下一跳節(jié)點(diǎn)。而當(dāng)M1到達(dá)u4時(shí)，u6節(jié)點(diǎn)由于網(wǎng)絡(luò)擁塞或者故障等原因，u4選擇u3作為下一跳節(jié)點(diǎn)，這樣在t1+4Δt時(shí)，M1到達(dá)u3，而M2到達(dá)u5。最終，M2比M1早到s節(jié)點(diǎn)。M1經(jīng)過的路徑為Pa(M1)={o,u1,u2,u4,u3,u5,u7,s}，用時(shí)7Δt；而M2經(jīng)過的路徑為Pa(M2)={o,u1,u3,u5,u7,s} ，用時(shí)5Δt。因此，在考慮通信連路的時(shí)間依賴特性，采用機(jī)會(huì)傳輸方式的無線傳感器網(wǎng)絡(luò)的鏈路傳輸是no-FIFO的。 證畢

圖1 網(wǎng)絡(luò)通信圖案例

定理2采用機(jī)會(huì)傳輸方式的WSN，其基于時(shí)間依賴特性的最短路徑問題是一個(gè)NP難解問題。

證明根據(jù)定理 1，基于機(jī)會(huì)路由通信機(jī)制的WSN網(wǎng)絡(luò)，其網(wǎng)絡(luò)通信具有no-FIFO特性。 而文獻(xiàn)[12]已證明，在時(shí)變網(wǎng)絡(luò)中如果通信連路是 no-FIFO，其最短路徑算法的復(fù)雜度是NP的。因此，在機(jī)會(huì)路由中，基于時(shí)變的最短路徑問題是一個(gè)NP難解問題。 證畢

2.3 能量問題

(1)能量消耗矩陣 根據(jù)文獻(xiàn)[14]無線傳感器節(jié)點(diǎn)存在3個(gè)工作狀態(tài)：空閑、發(fā)送和接收，我們建立能量消耗矩陣E為

其中各元素Eij，當(dāng)i≠j，表示狀態(tài)i轉(zhuǎn)變成狀態(tài)j所需消耗的能量，當(dāng)i=j，表示節(jié)點(diǎn)在持續(xù)狀態(tài)i時(shí)所消耗的能量。

(2)基于時(shí)間依賴的能量預(yù)測(cè)模型 根據(jù)上述能量消耗的能量矩陣，建立節(jié)點(diǎn)剩余能量的最優(yōu)估計(jì)值Eop(t)：

其中El(t)表示當(dāng)前節(jié)點(diǎn)剩余能量，可由節(jié)點(diǎn)實(shí)時(shí)獲得；Es(t)表示t時(shí)刻，在i狀態(tài)下，節(jié)點(diǎn)在T時(shí)間內(nèi)能源消耗的預(yù)測(cè)值，其值基于能量消耗可能量矩陣E，根據(jù)式(6)計(jì)算而得，其中，T=2。

2.4 機(jī)會(huì)熵

1850年，德國(guó)物理學(xué)家魯?shù)婪颉た藙谛匏固岢觯涸谝粋€(gè)獨(dú)立的系統(tǒng)中，能量密度的差異傾向于變成均等。這也是熱力學(xué)第2定律的核心思想。并且定義熵(S)表示系統(tǒng)在不受外部干擾的情況下，系統(tǒng)通常往內(nèi)部最穩(wěn)定狀態(tài)發(fā)展的特性。1872年，波爾茲曼進(jìn)一步從分子運(yùn)動(dòng)的角度對(duì)克勞修斯的熱力學(xué)熵理論進(jìn)行了發(fā)展，進(jìn)一步解釋了系統(tǒng)由不穩(wěn)定到穩(wěn)定過程中，各分子的能量衰減過程，并提出了微觀態(tài)的概念[15]，從微觀的角度體現(xiàn)了一個(gè)物質(zhì)系統(tǒng)中各分子能量的衰竭程度。通過比較各分子的熵值大小，就可以辨別出系統(tǒng)的轉(zhuǎn)化方向，即往S值大的趨勢(shì)發(fā)展。

這個(gè)現(xiàn)象可以用于描述數(shù)據(jù)報(bào)文在 WSN傳輸過程中，各節(jié)點(diǎn)狀態(tài)以及剩余能量的變化趨勢(shì)。根據(jù)熱力學(xué)第2定律，將整個(gè)WSN看作是一個(gè)獨(dú)立的、密閉的系統(tǒng)，我們通過定義機(jī)會(huì)熵，來描述每個(gè)WSN節(jié)點(diǎn)的狀態(tài)。

定義5機(jī)會(huì)熵(opportunistic entropy)用Sop表示，它表征節(jié)點(diǎn)在自身能量有限并且能量不可再生的前提下，其自身狀態(tài)的活躍程度，表示為

其中，剩余能量的最優(yōu)估計(jì)值Eop(t)，由式(5)可得。wu(t)同式(3)。

3 基于蟻群算法的機(jī)會(huì)路由算法ATDOP

3.1 基于Sop的機(jī)會(huì)概率模型

根據(jù)傳統(tǒng)蟻群優(yōu)化算法中用信息素作為節(jié)點(diǎn)被選概率模型的思想[7]，結(jié)合機(jī)會(huì)熵Sop，本文提出了一個(gè)新的概率計(jì)算公式。

其中N(u)為u節(jié)點(diǎn)的鄰居集，ui和uj分別為u節(jié)點(diǎn)鄰居集中的節(jié)點(diǎn)；P(uj,t)為在第t時(shí)刻，螞蟻將報(bào)文從節(jié)點(diǎn)u傳遞到下一節(jié)點(diǎn)uj的概率，即當(dāng)前節(jié)點(diǎn)選擇節(jié)點(diǎn)uj作為下一跳的概率；τ(uj,t)為在第t時(shí)刻下，節(jié)點(diǎn)uj上的信息素濃度；Sop(uj,t)為在第t時(shí)刻下，節(jié)點(diǎn)uj的機(jī)會(huì)熵；β為系統(tǒng)參數(shù)，它用來調(diào)整Sop(uj,t)對(duì)P(uj,t)中的影響程度，其值根據(jù)具體實(shí)驗(yàn)環(huán)境由經(jīng)驗(yàn)設(shè)定，本文實(shí)驗(yàn)中β=1?；谑?8)，在傳輸過程中，選擇P值最大的節(jié)點(diǎn)作為下一接收節(jié)點(diǎn)。

3.2 信息素更新

當(dāng)節(jié)點(diǎn)u將數(shù)據(jù)報(bào)文發(fā)送給節(jié)點(diǎn)uj完畢之后，節(jié)點(diǎn)uj會(huì)自我更新信息素τ(uj,t)。由于信息素是決定螞蟻選擇路徑的關(guān)鍵因素之一。因此，本文在提出信息素計(jì)算模型時(shí)引入了殘留率ρ(t)。

其值與當(dāng)前節(jié)點(diǎn)剩余能量相關(guān)，當(dāng)節(jié)點(diǎn)能量剩余越少，ρ(t)值越小，意味著信息素的揮發(fā)越快。Einit表示節(jié)點(diǎn)初始能量值。通過根據(jù)能量調(diào)整殘留率ρ(t)，可以使剩余能量少的節(jié)點(diǎn)的信息素?fù)]發(fā)速度快。

初始化時(shí)，網(wǎng)絡(luò)中各節(jié)點(diǎn)都被設(shè)置為相同的初始值；τ(uj,t-1)表示t-1時(shí)刻節(jié)點(diǎn)uj的信息素；Δτ(uj,t)表示第t時(shí)刻節(jié)點(diǎn)uj信息素的增加值，其值由式(11)可得

3.3 ATDOP算法

根據(jù)上述的信息素以及機(jī)會(huì)概率的計(jì)算模型，本文設(shè)計(jì)了基于蟻群優(yōu)化算法的時(shí)間依賴機(jī)會(huì)路由協(xié)議算法(ATDOP)。其結(jié)構(gòu)如圖2所示。

(1)初始化 該狀態(tài)下，由Sink節(jié)點(diǎn)通過泛洪的方式在網(wǎng)絡(luò)內(nèi)發(fā)送初始化信息，主要對(duì)算法中所需的各節(jié)點(diǎn)距離Sink節(jié)點(diǎn)的最短跳數(shù)h，信息素更新時(shí)間Tw，鄰居節(jié)點(diǎn)集信息收集等待Tc，能量枯竭判斷閾值ε，螞蟻(數(shù)據(jù)報(bào)文)到達(dá)標(biāo)志Fa,β, Δω等信息進(jìn)行初值化。

圖2 ATDOP結(jié)構(gòu)圖

(2)等待螞蟻 一方面等待自身節(jié)點(diǎn)是否產(chǎn)生新螞蟻要發(fā)送，如果有，則進(jìn)行鄰居節(jié)點(diǎn)的狀態(tài)查詢。另一方面監(jiān)聽網(wǎng)絡(luò)，如果有鄰居螞蟻達(dá)到，判斷該報(bào)文是否是查詢節(jié)點(diǎn)狀態(tài)，如果是，則返回自身節(jié)點(diǎn)狀態(tài)(ID，機(jī)會(huì)熵Sop，信息素信息τ(uj,t))，然后再次進(jìn)入監(jiān)聽狀態(tài)；如果是需要轉(zhuǎn)發(fā)的報(bào)文，則進(jìn)行鄰居節(jié)點(diǎn)的狀態(tài)查詢，為報(bào)文轉(zhuǎn)發(fā)做準(zhǔn)備。

(3)查詢鄰居節(jié)點(diǎn)狀態(tài) 該節(jié)點(diǎn)會(huì)向鄰居節(jié)點(diǎn)集N發(fā)送請(qǐng)求信息，在等待時(shí)間Tc內(nèi)，收集鄰居節(jié)點(diǎn)返回的各自Sop和τ(uj,t)，并計(jì)算機(jī)會(huì)選擇概率P(uj,t)。

(4)選擇節(jié)點(diǎn) 選擇機(jī)會(huì)選擇概率P(uj,t)最大的節(jié)點(diǎn)，建立傳輸路徑，發(fā)送螞蟻。

(5)信息素更新 信息素的自我更新，該狀態(tài)主要有兩個(gè)進(jìn)入源：其一是在發(fā)送螞蟻后立即自我更新，其二是在節(jié)點(diǎn)等待Tw時(shí)間后，進(jìn)行自我更新(該處是對(duì)信息素的揮發(fā)處理)。

4 實(shí)驗(yàn)仿真與性能分析

4.1 仿真環(huán)境的建立

本文利用 NS-2 實(shí)驗(yàn)軟件進(jìn)行相關(guān)實(shí)驗(yàn)驗(yàn)證。仿真參數(shù)如表1所示。

表1 實(shí)驗(yàn)參數(shù)

4.2 性能分析與比較

本實(shí)驗(yàn)環(huán)節(jié)將ATDOP算法與以下兩個(gè)路由算法進(jìn)行比較：(1)基于傳統(tǒng)的蟻群算法的路由算法，BACO(Basic Ant Colony Optimization)，文獻(xiàn)[7,11]將傳統(tǒng)的蟻群算法用在求解近似最短路由；(2)EEABR(Energy Efficient Ant Based Routing)路由算法[9]，該算法同樣是基于蟻群算法，并參考了整體路徑的剩余能量，剩余能量多的，將具有高的被選擇機(jī)會(huì)。

在相同的仿真環(huán)境以及網(wǎng)絡(luò)拓?fù)湟?guī)模，根據(jù)本文中對(duì)網(wǎng)絡(luò)壽命的定義，即當(dāng)網(wǎng)絡(luò)內(nèi)任意一節(jié)點(diǎn)的剩余能量低于枯竭判斷閾值ε時(shí)，實(shí)驗(yàn)停止。實(shí)驗(yàn)中，ε取能量初始值的10%。

(1)針對(duì)網(wǎng)絡(luò)壽命，采用 BACO, EEABR和ATDOP 3個(gè)路由算法，分別進(jìn)行了100次實(shí)驗(yàn)，結(jié)果如表2所示。

表2 平均網(wǎng)絡(luò)壽命

傳統(tǒng)的蟻群算法由于沒有考慮節(jié)點(diǎn)的能耗，使得信息素高的節(jié)點(diǎn)被頻繁選中傳輸信息，所以導(dǎo)致網(wǎng)絡(luò)壽命最短；EEABR路由算法參考了路徑中的節(jié)點(diǎn)的平均能量，并且在數(shù)據(jù)包到達(dá)Sink后再對(duì)整條路徑上的節(jié)點(diǎn)一起更新，但該路徑上個(gè)節(jié)點(diǎn)的剩余能量的沒有單獨(dú)考慮，雖然在網(wǎng)絡(luò)壽命上有很大提高，但是仍略低于本文的ATDOP算法。

(2)針對(duì)各節(jié)點(diǎn)剩余能量的分布情況，我們同樣統(tǒng)計(jì)了上述100次的實(shí)驗(yàn)結(jié)果，如圖3所示，其中橫軸為能量剩余率，縱軸為占節(jié)點(diǎn)總數(shù)比例。

BACO路由算法，由于螞蟻在行進(jìn)過程中沒有考慮能量，信息的傳輸主要集中在最初所建立的近似最優(yōu)路徑上，能量的消耗也主要集中在這部分節(jié)點(diǎn)上，實(shí)驗(yàn)停止時(shí)只有 30%的節(jié)點(diǎn)剩余能量低于35%。而EEABR與ATDOP算法由于考慮到剩余能量問題，實(shí)驗(yàn)停止時(shí)大約70%以上的節(jié)點(diǎn)剩余能量低于能量初始值的35%。

(3)針對(duì)網(wǎng)絡(luò)吞吐率，本實(shí)驗(yàn)將上述3個(gè)路由算法進(jìn)行了100次的實(shí)驗(yàn)比較，其吞吐率分析如圖4所示。

其縱軸為Sink節(jié)點(diǎn)接收到數(shù)據(jù)包，橫軸為網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)的累計(jì)跳數(shù)和，斜率即為該時(shí)刻所對(duì)應(yīng)的吞吐率。3個(gè)路由算法在實(shí)驗(yàn)初期，其吞吐率接近，但隨著實(shí)驗(yàn)的進(jìn)行，由于傳統(tǒng)蟻群算法沒有考慮能耗，所以該算法的吞吐率比較穩(wěn)定，而EEBAR與ATDOP由于考慮了節(jié)點(diǎn)的剩余能量，因此在實(shí)驗(yàn)后期，傳輸路徑會(huì)動(dòng)態(tài)地調(diào)整，跳數(shù)增多，二者的吞吐率都有下降，但ATDOP由于同時(shí)考慮了最短路徑問題，因此其吞吐率好于EEBAR算法。

5 結(jié)論

本文在分析已有的機(jī)會(huì)路由算法的基礎(chǔ)上，利用熱力學(xué)第2定律對(duì)在時(shí)變特性下WSN網(wǎng)絡(luò)數(shù)據(jù)報(bào)文的傳輸過程進(jìn)行分析與描述，并參考熱力學(xué)中熵的概念，以節(jié)點(diǎn)剩余能量和距離Sink節(jié)點(diǎn)的傳輸距離作為狀態(tài)變量，提出了機(jī)會(huì)熵模型，并用以表征 WSN中各節(jié)點(diǎn)的傳輸狀態(tài)?；谠撃Ｐ?，數(shù)據(jù)報(bào)文動(dòng)態(tài)選擇傳輸路徑也就是選擇機(jī)會(huì)熵小的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。進(jìn)而，本文將機(jī)會(huì)熵模型與蟻群優(yōu)化算法相結(jié)合，提出了一個(gè)適用于時(shí)變網(wǎng)絡(luò)模型的考慮網(wǎng)絡(luò)資源負(fù)載均衡的機(jī)會(huì)路由算法(ATDOP)。最后，實(shí)驗(yàn)仿真表明，該路由算法相對(duì)于已有的基于原始蟻群算法的機(jī)會(huì)路由算法以及考慮能量的EEBAR機(jī)會(huì)路由算法的網(wǎng)絡(luò)工作壽命更長(zhǎng)，能量消耗的更均勻，網(wǎng)絡(luò)資源分配的更合理。

圖3 節(jié)點(diǎn)剩余能量的分布

圖4 吞吐率

[1]Abhijeet B, Mohammad N, Javidi T,et al.. Adaptive opportunistic routing for wireless ad hoc networks[J].IEEE/ACM Transactions on Networking, 2012, 20(1):243-256.

[2]熊永平, 孫利民, 牛建偉, 等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2009,20(1): 124-137.

Xiong Yong-ping, Sun Li-min, Niu Jian-wei,et al.. Opportunistic networks[J].Journal of Software, 2009, 20(1): 124-137.

[3]Sanjit B and Robert M. ExOR: opportunistic multi-hop routing for wireless networks[C]. Proceedings of ACM SIGCOMM, Pennsylvania, 2005: 133-143.

[4]Bo H, Pan H, and Kumar A. Mobile data offloading through opportunistic communications and social participation[J].IEEE Transactions on Mobile Computing, 2012, 11(5):821-834.

[5]Kai Z, Wenjing L, and Hongqiang Z. On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[C]. Proceedings of the IEEE INFOCOM, Phoenix, AZ, USA, 2008: 1490-1498.

[6]霍廣城, 王曉東. 移動(dòng)傳感網(wǎng)中一種基于RSSI 的機(jī)會(huì)主義路由設(shè)計(jì)[J]. 電子學(xué)報(bào), 2009, 37(3): 608-613.

Huo Guang-cheng and Wang Xiao-dong. An opportunistic routing for mobile wireless sensor networks based on RSSI[J].Acta Electronica Sinica, 2009, 37(3): 608-613.

[7]Paquereau L and Helvik E. Opportunistic ant-based path management for wireless mesh networks[C]. International Conference on Swarm Intelligence, Beijing, China, 2010:480-487.

[8]Lakshmi V, Kailas A, and Ingram A. Two energy-saving schemes for cooperative transmission with opportunistic large arrays[C]. Proceedings of IEEE GLOBECOM, Washington DC, USA, 2007: 1038-1042.

[9]Tiago C, Carlos C, Jorge S,et al.. An energy-efficient ant-based routing algorithm for wireless sensor networks[C].Ant Colony Optimization and Swarm Intelligence, 2006, 4150:49-59.

[10]宋超, 劉明, 龔海剛, 等. 基于蟻群優(yōu)化解決傳感器網(wǎng)絡(luò)中的能量洞問題[J]. 軟件學(xué)報(bào), 2009, 20(10): 2729-2743.

Song Chao, Liu Ming, Gong Hai-gang,et al.. ACO-based algorithm for solving energy hole problems in wireless sensor networks[J].Journal of Software, 2009, 20(10): 2729-2743.

[11]Lee W. Ant-colony-based scheduling algorithm for energyefficient coverage of WSN[J].IEEE Sensors Journal, 2012,12(10): 3036-3046.

[12]Ariel O and Rapheal R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length[J].Journal of the ACM, 1990, 37(3): 607-625.

[13]譚國(guó)真, 高文. 時(shí)間依賴的網(wǎng)絡(luò)中最小時(shí)間路徑算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2002, 25(2): 165-172.

Tan Guo-zhen and Gao Wen. Shortest path algorithm in time-dependent networks[J].Chinese Journal on Computers,2002, 25(2): 165-172.

[14]Al-Jarrah O and Megdadi O. Enhanced AODV routing protocol for bluetooth scatternet[J].Computers and Electrical Engineering, 2009, 35(1): 197-208.

[15]Pincus S M. Approximate entropy as a measure of system complexity[J].Proceedings of the National Academy of Sciences of the United States America, 1991, 88(6):2297-2301.