劉 俞

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

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

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

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

1 能量多路徑路由算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）在路徑建立過程中，每個節(jié)點都要進行大量的復雜運算，這對節(jié)點的性能和能耗本身就是一個挑戰(zhàn)。

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

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

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

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

2.1 DPEMR算法的基本思想

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

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

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

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

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

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

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

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

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

struct RouteTable{

char ID；//節(jié)點的 ID 標識號

int P； //節(jié)點的優(yōu)先級

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

}RTdata；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗仿真

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

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

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

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

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

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

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

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

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

4 結(jié)語

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