一種基于動(dòng)態(tài)優(yōu)先級(jí)的無(wú)線傳感器網(wǎng)絡(luò)能量多路徑路由算法

劉 俞

（馬鞍山職業(yè)技術(shù)學(xué)院 電子信息系，安徽 馬鞍山 243031）

無(wú)線傳感器網(wǎng)絡(luò)路由算法［1-2］的任務(wù)是在源節(jié)點(diǎn)和匯聚節(jié)點(diǎn)間尋找優(yōu)化路徑完成數(shù)據(jù)傳輸。在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的能量是有限的且難以補(bǔ)充，因此路由算法要高效地利用能量［3-4］。

無(wú)線傳感器網(wǎng)絡(luò)的路由算法分為平面路由算法和分簇路由算法兩種類(lèi)型［5］。文獻(xiàn)［6］提出的能量多路徑路由算法是最早提出的無(wú)線傳感器網(wǎng)絡(luò)平面路由算法之一，該路由算法重點(diǎn)考慮能量高效，在數(shù)據(jù)傳輸過(guò)程中，選擇能量消耗小且能量相對(duì)充足的路徑完成數(shù)據(jù)由源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的傳輸。但是，在算法中沒(méi)有動(dòng)態(tài)考慮各節(jié)點(diǎn)能量損耗情況，一旦概率確定，在整個(gè)生存期內(nèi)不再變化。這樣會(huì)導(dǎo)致在數(shù)據(jù)傳輸時(shí)，選擇概率高的路徑會(huì)被頻繁選中，造成各節(jié)點(diǎn)的能量消耗不均衡［7-8］。

本文提出基于動(dòng)態(tài)優(yōu)先級(jí)的能量多路徑路由算法。在算法中通過(guò)為節(jié)點(diǎn)設(shè)置優(yōu)先級(jí)來(lái)衡量其與匯聚節(jié)點(diǎn)的通信能量代價(jià)及其節(jié)點(diǎn)剩余能量，在數(shù)據(jù)傳輸過(guò)程中依照優(yōu)先級(jí)的大小進(jìn)行路徑選擇。同時(shí)，節(jié)點(diǎn)的優(yōu)先級(jí)隨著其能量損耗動(dòng)態(tài)變化。初始時(shí)所有節(jié)點(diǎn)有著相同的能量，賦予它們相同的初始優(yōu)先級(jí)。在路徑建立過(guò)程中，根據(jù)節(jié)點(diǎn)與匯聚節(jié)點(diǎn)間距離的跳數(shù)值［9］更新它們的優(yōu)先級(jí)。在數(shù)據(jù)傳播過(guò)程中，根據(jù)節(jié)點(diǎn)采集的數(shù)據(jù)量和轉(zhuǎn)發(fā)的數(shù)據(jù)包數(shù)量實(shí)時(shí)地更新其優(yōu)先級(jí)。該算法能有效降低和平衡各節(jié)點(diǎn)的能耗，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生存期。

1 能量多路徑路由算法

1.1 能量多路徑路由算法中路徑建立算法的步驟

能量多路徑路由算法中路徑建立算法具體執(zhí)行步驟如下：

步驟1啟動(dòng)路徑建立，匯聚節(jié)點(diǎn)廣播路徑建立數(shù)據(jù)包。

步驟2相鄰節(jié)點(diǎn)接收到路徑建立數(shù)據(jù)包后，根據(jù)數(shù)據(jù)包中的坐標(biāo)信息計(jì)算本節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離，然后和上一節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離值進(jìn)行比較，若本節(jié)點(diǎn)較上一節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)更遠(yuǎn)時(shí)，則本節(jié)點(diǎn)轉(zhuǎn)發(fā)此數(shù)據(jù)包，否則將此數(shù)據(jù)包丟棄，以避免產(chǎn)生回路。

步驟3如圖1 所示，如果節(jié)點(diǎn)Dj接收到節(jié)點(diǎn)Di發(fā)來(lái)的路徑建立數(shù)據(jù)包，經(jīng)過(guò)步驟2 的判斷，在轉(zhuǎn)發(fā)該數(shù)據(jù)包之前，迭代計(jì)算節(jié)點(diǎn)Dj經(jīng)過(guò)節(jié)點(diǎn)Di與匯聚節(jié)點(diǎn)Ds相連通的路徑通信能耗代價(jià)C(Dj，Di)，計(jì)算如下式：

圖1 路徑建立示意圖Fig.1 Diagram of path establishment

Exp(Dj,Di)為節(jié)點(diǎn)Dj到節(jié)點(diǎn)Di通信所產(chǎn)生的能耗，此能耗值是由節(jié)點(diǎn)Dj到節(jié)點(diǎn)Di通信產(chǎn)生的直接能耗值與節(jié)點(diǎn)Di的剩余能量值計(jì)算得出的，綜合考慮了兩個(gè)節(jié)點(diǎn)通信的直接能耗和上一節(jié)點(diǎn)的剩余能量值。

步驟4節(jié)點(diǎn)對(duì)路徑進(jìn)行篩選，放棄能耗過(guò)大的路徑。如節(jié)點(diǎn)Dj要根據(jù)以下條件判斷是否將節(jié)點(diǎn)Di存入自身的路由表中：

其中γ的值是根據(jù)節(jié)點(diǎn)的路由表存儲(chǔ)空間和系統(tǒng)對(duì)路由路徑數(shù)量的需求預(yù)設(shè)的。當(dāng)γ較小時(shí)，該節(jié)點(diǎn)路由表中保存的路徑數(shù)少；反之，則保存的路徑數(shù)多。

步驟5節(jié)點(diǎn)計(jì)算自身路由表中所有下一節(jié)點(diǎn)的選擇概率，如：節(jié)點(diǎn)Di在節(jié)點(diǎn)Dj的路由表中，是節(jié)點(diǎn)Dj下一節(jié)點(diǎn)，因此節(jié)點(diǎn)Dj要計(jì)算節(jié)點(diǎn)Di的選擇概率，計(jì)算如下式：

其中PDj(Di)表示在節(jié)點(diǎn)Dj的路由表中，節(jié)點(diǎn)Di被選中作為數(shù)據(jù)傳輸?shù)南乱还?jié)點(diǎn)的概率值?？梢钥闯?，通過(guò)某節(jié)點(diǎn)的路徑通信能耗越高，此節(jié)點(diǎn)的選中概率越低。

步驟6節(jié)點(diǎn)以路由表中每項(xiàng)下一跳節(jié)點(diǎn)選擇概率為權(quán)值，如節(jié)點(diǎn)Dj計(jì)算出所有項(xiàng)的能量代價(jià)加權(quán)平均值Cost(Dj)作為新的能量代價(jià)值。其含義為經(jīng)由路由表中節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)代價(jià)的平均值，計(jì)算如下式：

接下來(lái)，節(jié)點(diǎn)Dj將新的代價(jià)值Cost(Dj)置入路徑建立消息中，向鄰居節(jié)點(diǎn)廣播該消息。然后轉(zhuǎn)至步驟2，不斷重復(fù)，直至所有節(jié)點(diǎn)的路由信息建立完成。

1.2 數(shù)據(jù)傳輸路徑選擇過(guò)程

路徑建立完成后，當(dāng)源節(jié)點(diǎn)要將獲取的信息傳輸給匯聚節(jié)點(diǎn)時(shí)，從源節(jié)點(diǎn)開(kāi)始，選擇其路由表中選擇概率最大的節(jié)點(diǎn)作為下一節(jié)點(diǎn)，依次將信息轉(zhuǎn)發(fā)，直至發(fā)送到匯聚節(jié)點(diǎn)。

1.3 能量多路徑路由算法的缺陷分析

能量多路徑路由算法通過(guò)綜合考慮各路徑上的能量消耗及路徑上各節(jié)點(diǎn)的剩余能量來(lái)選擇最優(yōu)路徑，使各路徑實(shí)現(xiàn)了能量負(fù)載均衡。但經(jīng)過(guò)分析，可以發(fā)現(xiàn)能量多路徑路由算法還存在下述一些缺陷。

1）在路徑建立過(guò)程中，需要計(jì)算節(jié)點(diǎn)之間數(shù)據(jù)傳輸所需的能耗以及節(jié)點(diǎn)的剩余能量，在現(xiàn)實(shí)系統(tǒng)中很難實(shí)現(xiàn)，因?yàn)檫@些能耗和剩余能量很難計(jì)量。

2）在路徑建立過(guò)程中，每個(gè)節(jié)點(diǎn)都要進(jìn)行大量的復(fù)雜運(yùn)算，這對(duì)節(jié)點(diǎn)的性能和能耗本身就是一個(gè)挑戰(zhàn)。

3）算法中沒(méi)有動(dòng)態(tài)考慮各節(jié)點(diǎn)能量損耗情況，一旦概率確定，在整個(gè)生存期內(nèi)不再變化。這樣會(huì)導(dǎo)致在數(shù)據(jù)傳輸時(shí)，選擇概率高的路徑會(huì)被頻繁選中，造成這些路徑上的節(jié)點(diǎn)能量過(guò)度損耗而過(guò)早失效。

4）若采用周期性地由匯聚節(jié)點(diǎn)到其他節(jié)點(diǎn)實(shí)施泛洪來(lái)重新計(jì)算各參數(shù)，每次都會(huì)產(chǎn)生大量的運(yùn)算及數(shù)據(jù)傳輸，累加起來(lái)所帶來(lái)的能量損耗十分可觀，從而導(dǎo)致整個(gè)網(wǎng)絡(luò)生存期的縮短。

2 基于動(dòng)態(tài)優(yōu)先級(jí)的能量多路徑路由算法

針對(duì)已有的能量多路徑路由算法的缺陷，本研究提出一種基于動(dòng)態(tài)優(yōu)先級(jí)的能量多路徑路由（dynamic priority energy multipath routing，DPEMR）算法。

2.1 DPEMR算法的基本思想

在DPEMR 算法中，設(shè)置優(yōu)先級(jí)的作用是在數(shù)據(jù)傳輸過(guò)程中，當(dāng)一個(gè)節(jié)點(diǎn)要將數(shù)據(jù)轉(zhuǎn)發(fā)給下一個(gè)節(jié)點(diǎn)，在其路由表中選中優(yōu)先級(jí)最高的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，將數(shù)據(jù)轉(zhuǎn)發(fā)給它，以此方式依次轉(zhuǎn)發(fā)，直到通過(guò)此路徑將數(shù)據(jù)傳送至匯聚節(jié)點(diǎn)。在路徑建立階段，記錄路徑上各節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù)值來(lái)替代它們之間的能量代價(jià)，根據(jù)跳數(shù)值對(duì)節(jié)點(diǎn)的初始優(yōu)先級(jí)進(jìn)行計(jì)算設(shè)置。在網(wǎng)絡(luò)工作階段，根據(jù)節(jié)點(diǎn)工作的頻度和負(fù)荷［10］（節(jié)點(diǎn)接收及轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)量）不斷更新其優(yōu)先級(jí)。

2.2 DPEMR算法路徑建立算法的步驟

DPEMR 算法路徑建立算法具體執(zhí)行步驟如下：

步驟1匯聚節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播路徑建立數(shù)據(jù)包SetPath（idi，x0，y0，si，hopsi）。其中，idi是消息發(fā)送節(jié)點(diǎn)i的ID 號(hào)（網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有唯一的ID 標(biāo)識(shí)號(hào)）；（x0，y0）是匯聚節(jié)點(diǎn)的位置坐標(biāo)值（在網(wǎng)絡(luò)部署后，通過(guò)定位算法，每個(gè)節(jié)點(diǎn)都計(jì)算出自身的位置坐標(biāo)值并存儲(chǔ)）；si是節(jié)點(diǎn)i與匯聚節(jié)點(diǎn)之間的距離（匯聚節(jié)點(diǎn)發(fā)出的數(shù)據(jù)包中，其值為0）；hopsi是節(jié)點(diǎn)i距匯聚節(jié)點(diǎn)的跳數(shù)（匯聚節(jié)點(diǎn)發(fā)出的數(shù)據(jù)包中，其值為0）。

步驟2當(dāng)相鄰的節(jié)點(diǎn)j接收到節(jié)點(diǎn)i發(fā)來(lái)的SetPath 數(shù)據(jù)包后，根據(jù)匯聚節(jié)點(diǎn)及自身的位置坐標(biāo)值計(jì)算出其與匯聚節(jié)點(diǎn)的距離值sj，比較sj與si的大小關(guān)系，若sj ＞si，說(shuō)明節(jié)點(diǎn)j比節(jié)點(diǎn)i距匯聚節(jié)點(diǎn)更遠(yuǎn)，接下來(lái)對(duì)數(shù)據(jù)包中的相關(guān)數(shù)據(jù)進(jìn)行計(jì)算、記錄，更新該數(shù)據(jù)包（執(zhí)行第3 步至第5 步）后繼續(xù)向相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)，否則將數(shù)據(jù)包丟棄。節(jié)點(diǎn)j與匯聚節(jié)點(diǎn)的距離值計(jì)算公式如下：

步驟3如果節(jié)點(diǎn)j接收到節(jié)點(diǎn)i發(fā)來(lái)的路徑建立數(shù)據(jù)包SetPath，經(jīng)過(guò)步驟2 的判斷，在轉(zhuǎn)發(fā)該數(shù)據(jù)包之前，計(jì)算經(jīng)由節(jié)點(diǎn)i的路徑代價(jià)（hopsi=hopsi+1，因?yàn)閰R聚節(jié)點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)i到節(jié)點(diǎn)j，跳數(shù)增加1），根據(jù)是否滿(mǎn)足條件，決定是否將節(jié)點(diǎn)i加入自身存儲(chǔ)的路由表中，判定選擇條件如下：

經(jīng)過(guò)（6）式的判斷，若節(jié)點(diǎn)i滿(mǎn)足條件，則被存儲(chǔ)到節(jié)點(diǎn)j的路由表中。

在這里，統(tǒng)計(jì)節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的跳數(shù)值是用來(lái)替代路徑能耗代價(jià)的，因?yàn)橐粭l路徑上的跳數(shù)值越大，數(shù)據(jù)被轉(zhuǎn)發(fā)的次數(shù)也越多，能耗代價(jià)也就越大。

節(jié)點(diǎn)路由表的數(shù)據(jù)結(jié)構(gòu)定義如下：

struct RouteTable{

char ID；//節(jié)點(diǎn)的 ID 標(biāo)識(shí)號(hào)

int P； //節(jié)點(diǎn)的優(yōu)先級(jí)

int hops；//節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的跳數(shù)

}RTdata；

步驟4節(jié)點(diǎn)的路由表建立完成后，節(jié)點(diǎn)根據(jù)路徑跳數(shù)值計(jì)算其路由表中每個(gè)下一跳節(jié)點(diǎn)的初始優(yōu)先級(jí)，假設(shè)節(jié)點(diǎn)i在節(jié)點(diǎn)j的路由表中，以計(jì)算節(jié)點(diǎn)i的優(yōu)先級(jí)為例，計(jì)算公式如下：

其中n為節(jié)點(diǎn)j的路由表中節(jié)點(diǎn)的個(gè)數(shù)，(∑k∈RTj hopsk)/n為節(jié)點(diǎn)j路由表中所有下一跳節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)跳數(shù)值的平均值，hopsi為節(jié)點(diǎn)i距離匯聚節(jié)點(diǎn)的跳數(shù)值，Emax為節(jié)點(diǎn)i的初始能量值。

步驟5節(jié)點(diǎn)j更新 SetPath（idj，x0，y0，sj，hopsj）數(shù)據(jù)包，其中，sj是步驟 2 所計(jì)算出的節(jié)點(diǎn)j與匯聚節(jié)點(diǎn)的距離值，hopsj是節(jié)點(diǎn)j通過(guò)自身路由表中各節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)跳數(shù)值的加權(quán)平均值，其計(jì)算公式如下：

由（8）式可知，節(jié)點(diǎn)j到匯聚節(jié)點(diǎn)的跳數(shù)hopsj是節(jié)點(diǎn)j通過(guò)自身路由表中各節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)的跳數(shù)與以?xún)?yōu)先級(jí)為權(quán)值得到的加權(quán)平均數(shù)，其值反映了由節(jié)點(diǎn)j傳輸數(shù)據(jù)至匯聚節(jié)點(diǎn)的平均能耗。

新的SetPath 數(shù)據(jù)包更新完成后，節(jié)點(diǎn)j將其向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)。

步驟6跳轉(zhuǎn)至步驟2，循環(huán)迭代，直至全部節(jié)點(diǎn)的路由表建立完成，路徑建立過(guò)程結(jié)束。

2.3 數(shù)據(jù)傳輸路徑選擇及節(jié)點(diǎn)優(yōu)先級(jí)更新過(guò)程

整個(gè)網(wǎng)絡(luò)的路由路徑建立完成后，網(wǎng)絡(luò)進(jìn)入工作狀態(tài)。源節(jié)點(diǎn)采集后的數(shù)據(jù)要傳輸至匯聚節(jié)點(diǎn)，此時(shí)，需要通過(guò)各節(jié)點(diǎn)的路由表選擇優(yōu)先級(jí)高的路徑，將數(shù)據(jù)從源節(jié)點(diǎn)傳輸至匯聚節(jié)點(diǎn)。源節(jié)點(diǎn)采集數(shù)據(jù)及數(shù)據(jù)傳輸路徑上的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)都產(chǎn)生能量損耗，因此，同時(shí)要對(duì)源節(jié)點(diǎn)及選中的傳輸路徑上各個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)進(jìn)行更新。以下按圖2 所示的情況對(duì)具體步驟進(jìn)行分析。

步驟1假設(shè)某一時(shí)刻，節(jié)點(diǎn)i采集外界的信息，形成數(shù)據(jù)包Message（idi，idnext，data）將發(fā)送至匯聚節(jié)點(diǎn)s，其中idi是節(jié)點(diǎn)i的ID 標(biāo)識(shí)號(hào)，idnext是節(jié)點(diǎn)i路由表中優(yōu)先級(jí)最高的下一跳節(jié)點(diǎn)（例如圖2 中的節(jié)點(diǎn)j）的ID 標(biāo)識(shí)號(hào)，data是其所采集到的數(shù)據(jù)。

此時(shí)，節(jié)點(diǎn)i要將自身存儲(chǔ)的路由表中相關(guān)節(jié)點(diǎn)的優(yōu)先級(jí)進(jìn)行更新，例如，在圖2 中節(jié)點(diǎn)i選中的下一跳節(jié)點(diǎn)是節(jié)點(diǎn)j，節(jié)點(diǎn)j將接收及轉(zhuǎn)發(fā)該數(shù)據(jù)包，因此根據(jù)將產(chǎn)生的能耗更新節(jié)點(diǎn)j的優(yōu)先級(jí)，計(jì)算公式如下：

其中Etx(n,d)為節(jié)點(diǎn)轉(zhuǎn)發(fā)一個(gè)nbit 數(shù)據(jù)包所產(chǎn)生的能耗，Etx(n)為節(jié)點(diǎn)接收一個(gè)nbit 數(shù)據(jù)包所產(chǎn)生的能耗，Pmin是整個(gè)網(wǎng)絡(luò)統(tǒng)一的優(yōu)先級(jí)下限，主要考慮節(jié)點(diǎn)數(shù)據(jù)傳輸之外的能耗，若節(jié)點(diǎn)的優(yōu)先級(jí)降為此值視為死亡。

圖2 數(shù)據(jù)傳輸路徑選擇及節(jié)點(diǎn)優(yōu)先級(jí)更新過(guò)程示意圖Fig.2 Diagram of data transmission path selection and nodes priority renewing process

步驟2節(jié)點(diǎn)i向鄰居節(jié)點(diǎn)廣播Message 數(shù)據(jù)包，處于節(jié)點(diǎn)i在1 跳范圍內(nèi)的節(jié)點(diǎn)都將收到此數(shù)據(jù)包，如圖2 中虛線方框內(nèi)包括節(jié)點(diǎn)j和節(jié)點(diǎn)m在內(nèi)共6 個(gè)節(jié)點(diǎn)都是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，它們都在節(jié)點(diǎn)i的直接通信范圍內(nèi)。

節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)分為4 種情況，不同情況的節(jié)點(diǎn)收到Message 數(shù)據(jù)包后進(jìn)行不同的處理，如下所述：

1）當(dāng)相鄰節(jié)點(diǎn)收到Message 數(shù)據(jù)包后，發(fā)現(xiàn)自己的ID 標(biāo)識(shí)號(hào)與數(shù)據(jù)包中idnext相等（例如圖2 中節(jié)點(diǎn)j），則該節(jié)點(diǎn)就是上一節(jié)點(diǎn)選中的轉(zhuǎn)發(fā)數(shù)據(jù)的下一節(jié)點(diǎn)，然后在自身路由表中查詢(xún)優(yōu)先級(jí)最高的下一跳節(jié)點(diǎn)（例如圖2 中節(jié)點(diǎn)g），用這個(gè)節(jié)點(diǎn)的ID 標(biāo)識(shí)號(hào)更新Message 數(shù)據(jù)包中的idnext。同時(shí)，在自身的路由表中將idnext節(jié)點(diǎn)的優(yōu)先級(jí)降低，按公式（9）將其優(yōu)先級(jí)計(jì)算更新。接下來(lái)向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)Message數(shù)據(jù)包。

2）當(dāng)相鄰節(jié)點(diǎn)收到Message 數(shù)據(jù)包后，發(fā)現(xiàn)自己的ID 標(biāo)識(shí)號(hào)與數(shù)據(jù)包中idnext不相等，但數(shù)據(jù)包中的idnext節(jié)點(diǎn)在自身的路由表中（例如圖2 中節(jié)點(diǎn)h、節(jié)點(diǎn)j在其路由表中），那么該節(jié)點(diǎn)將其路由表中的節(jié)點(diǎn)idnext的優(yōu)先級(jí)降低，例如，節(jié)點(diǎn)h將其路由表中節(jié)點(diǎn)j的優(yōu)先級(jí)按公式（9）進(jìn)行計(jì)算更新，然后將Message 數(shù)據(jù)包丟棄。

3）當(dāng)相鄰節(jié)點(diǎn)收到Message 數(shù)據(jù)包后，發(fā)現(xiàn)自己的ID 標(biāo)識(shí)號(hào)與數(shù)據(jù)包中idnext不相等，數(shù)據(jù)包中idnext節(jié)點(diǎn)也不在自身的路由表中，但數(shù)據(jù)包中的idi在其路由表中（例如圖2 中節(jié)點(diǎn)m、節(jié)點(diǎn)i在其路由表中），那么該節(jié)點(diǎn)將其路由表中的idi節(jié)點(diǎn)的優(yōu)先級(jí)降低，例如，節(jié)點(diǎn)m將其路由表中節(jié)點(diǎn)i的優(yōu)先級(jí)進(jìn)行更新，然后將Message 數(shù)據(jù)包丟棄。優(yōu)先級(jí)更新公式如下：

4）當(dāng)相鄰節(jié)點(diǎn)收到Message 數(shù)據(jù)包后，經(jīng)判斷不滿(mǎn)足以上任何一種情況，直接將Message 數(shù)據(jù)包丟棄。

步驟3下一個(gè)節(jié)點(diǎn)繼續(xù)轉(zhuǎn)發(fā)Message 數(shù)據(jù)包，轉(zhuǎn)至步驟2，不斷重復(fù)，直至數(shù)據(jù)包到達(dá)匯聚節(jié)點(diǎn)。

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

為了驗(yàn)證DPEMR 算法的性能，在NS-2 仿真環(huán)境中對(duì)能量多路徑路由算法和DPEMR 算法進(jìn)行仿真，對(duì)比分別使用兩種路由算法下的網(wǎng)絡(luò)負(fù)載均衡性（load balance factor，LBF）和網(wǎng)絡(luò)生存周期。仿真環(huán)境的參數(shù)設(shè)置如表1 所示。

公式（11）與公式（12）分別為節(jié)點(diǎn)發(fā)送與接收數(shù)據(jù)能耗的計(jì)算公式。

LBF 是某時(shí)刻網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量最大值與最小值的比值，反映網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載均衡程度。兩種算法的LBF 與運(yùn)行輪數(shù)的關(guān)系情況如圖3 所示。

表1 實(shí)驗(yàn)仿真參數(shù)表Tab.1 Parameters of simulation experiment

圖3 負(fù)載均衡指數(shù)對(duì)比Fig.3 Comparison of load balance index

從圖3 可以看出，隨著運(yùn)行輪數(shù)的推進(jìn)，DPEMR 算法的LBF 明顯小于原算法且增幅較小。說(shuō)明DPEMR 算法的網(wǎng)絡(luò)負(fù)載均衡性?xún)?yōu)于原路由算法，其原因是由于算法利用動(dòng)態(tài)優(yōu)先級(jí)使得網(wǎng)絡(luò)在數(shù)據(jù)傳輸時(shí)的路徑選擇更為合理。

兩種算法的存活節(jié)點(diǎn)數(shù)量與運(yùn)行輪數(shù)的關(guān)系如圖4 所示。

圖4 網(wǎng)絡(luò)生存期對(duì)比Fig.4 Comparison of network life cycle

從圖4 可以看出，使用DPEMR 算法的網(wǎng)絡(luò)中，第一個(gè)節(jié)點(diǎn)能量耗盡到最后一個(gè)節(jié)點(diǎn)能量耗盡的時(shí)間均遲于使用原有路由算法的網(wǎng)絡(luò)。這是因?yàn)樵贒PEMR 算法中，網(wǎng)絡(luò)的負(fù)載均衡性得到了明顯提高，避免了采用原算法所出現(xiàn)的部分節(jié)點(diǎn)能量過(guò)度消耗的現(xiàn)象，使網(wǎng)絡(luò)壽命得以延長(zhǎng)。

4 結(jié)語(yǔ)

本文在現(xiàn)有的能量多路徑路由算法的基礎(chǔ)上提出了DPEMR 算法。該算法為節(jié)點(diǎn)設(shè)置優(yōu)先級(jí)來(lái)衡量其與匯聚節(jié)點(diǎn)的通信能量代價(jià)及其節(jié)點(diǎn)剩余能量，在路徑建立過(guò)程中，根據(jù)節(jié)點(diǎn)與匯聚節(jié)點(diǎn)間距離的跳數(shù)值計(jì)算出它們的初始優(yōu)先級(jí)。在數(shù)據(jù)傳輸過(guò)程中依照優(yōu)先級(jí)的大小進(jìn)行路徑選擇。同時(shí)，根據(jù)節(jié)點(diǎn)接收和轉(zhuǎn)發(fā)的數(shù)據(jù)包數(shù)量實(shí)時(shí)地更新其優(yōu)先級(jí)。經(jīng)分析可以得出，DPEMR 算法實(shí)現(xiàn)簡(jiǎn)單、復(fù)雜度低、計(jì)算量小，優(yōu)先級(jí)的更新在數(shù)據(jù)傳輸過(guò)程中同時(shí)完成，避免了周期性路由維護(hù)所帶來(lái)的時(shí)間與能量損失。仿真實(shí)驗(yàn)的結(jié)果表明，DPEMR 算法有效降低和平衡了各節(jié)點(diǎn)的能耗，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生存期。