基于REPBR跳數效用轉發(fā)的改進路由算法

吳鏡汝，袁 丁，嚴 清

(1.四川師范大學 計算機科學學院，四川 成都 610101；2.重慶移通學院 計算機學院，重慶 400000)

0 引 言

水下無線傳感器網絡(underwater wireless sensor networks，UWSNs)是一種復雜的、高效的、基于聲學傳感器的、可實現高速數據傳輸和高精度計算的水下監(jiān)測系統(tǒng)[1-3]。

電磁波在水下網絡環(huán)境的傳播距離只有50 cm～100 cm，不能作為水下的傳輸介質。因此，目前主要采用聲波作為傳輸方式，從無線電的3×108m/s降為1.5×103m/s，這意味著傳輸延遲更大，帶寬更低[4]。再加上多普勒效應、多徑效應、背景噪聲等多種因素的干擾，進一步限制了傳輸帶寬[5]。另外，水下節(jié)點面臨能量問題，因為這些節(jié)點配備了電池作為唯一可用的電源。與地面無線傳感器網絡相比，由于使用聲波作為通信介質，UWSNs中的傳輸和接收能耗有所增加[6]。因此，數據包的發(fā)送和接收消耗了水下傳感器節(jié)點的大部分能量。水下傳感器節(jié)點的路由是網絡中負責轉發(fā)和接收數據包的主要部分[7]，為保證路由算法的工作效率，降低能耗，減少時延，選擇最節(jié)能、最可靠的節(jié)點進行數據轉發(fā)，必須設計高效節(jié)能的路由算法。

DBR[8](depth-based routing for underwater sensor networks)路由協議是第一個無本地化的路由協議，它的優(yōu)點是不需要完整的尺寸位置信息，考慮傳感器節(jié)點的深度信息，從源節(jié)點中選擇具有最小深度的節(jié)點作為轉發(fā)器，但是它的缺點是深度小的節(jié)點更早死亡，導致路由網絡壽命更短；EEDBR[9](energy-efficient depth-based routing protocol for underwater wireless sensor networks)路由協議主要分為信息獲取階段和數據轉發(fā)階段。在信息獲取階段，傳感器節(jié)點基于較高的剩余能量和最小的深度找到鄰居，并將其ID存儲在路由表中。在轉發(fā)階段，選擇路由表中剩余能量最高和深度最小的節(jié)點進行數據包轉發(fā)，降低能量消耗，但它的缺點是沒有考慮鏈路質量，導致不穩(wěn)定鏈路帶來更多的能量消耗。REPBR[10](reliable energy-efficient pressure-based routing protocol for underwater wireless sensor network)路由協議用三角形度量方法估計鏈路質量，考慮鏈路質量、深度和剩余能量3個參數，平衡能耗和可靠的數據傳輸，設計基于路由代價計算的多尺度數據轉發(fā)算法，但其缺點是過長的路徑轉發(fā)提高了網絡的延時，降低了數據包的轉發(fā)效率。以上基于無定位路由協議對比見表1。

表1 基于無定位路由協議對比

1 REPBR路由算法研究

REPBR路由協議是一種無位置、可靠、節(jié)能的壓力路由協議，它利用深度、剩余能量和鏈路質量3個參數來選擇下一個轉發(fā)節(jié)點。該協議由信息獲取階段和數據轉發(fā)階段構成。

信息獲取階段：在此階段，每個節(jié)點在較小深度的節(jié)點之間交換特定的信息。首先，每個節(jié)點定期向它的單跳鄰居廣播一個Hello報文，Hello報文里面包括節(jié)點的ID、剩余能量和深度。每個節(jié)點收到Hello報文后，提取Hello報文的深度信息，并與鄰居節(jié)點作比較，如果Hello報文的深度小于它的深度，它將節(jié)點保存在它的鄰居信息表中，否則丟棄此報文，完成鄰居信息表的更新。每個節(jié)點用鏈路質量算法計算每個鄰居的距離，對鏈路質量進行估計，其Hello報文格式如圖1所示。

圖1 Hello報文格式

數據轉發(fā)階段：在此階段，數據包從源節(jié)點轉發(fā)到sink節(jié)點。源節(jié)點檢索它的鄰居信息表中的節(jié)點信息，并使用公式計算路由開銷，然后選擇路由開銷最小的節(jié)點作為轉發(fā)節(jié)點的最佳候選節(jié)點。然后發(fā)送方將所選節(jié)點的ID嵌入數據包進行廣播，鄰居節(jié)點只有收到與自己節(jié)點ID相同的才會接收數據包。路由開銷計算用式(1)表示

(1)

式中：Ei和Einit分別為當前節(jié)點i的剩余能量和初始能量，d(x，y) 是發(fā)送節(jié)點和轉發(fā)節(jié)點之間計算出的鏈路質量值，dmax是系統(tǒng)參數值，根據環(huán)境設置。

為減少不必要的數據轉發(fā)，選擇最可靠、最高效的節(jié)點，本文提出一種在超低通信速率環(huán)境下，基于REPBR跳數效用轉發(fā)的改進路由算法(簡稱HUF)，在數據包傳輸階段考慮最優(yōu)最短路徑節(jié)點的選擇，跳數最少的路由可以保證任意節(jié)點的信息沿著最優(yōu)路徑發(fā)送到網關節(jié)點，同時綜合鏈路質量、剩余能量選擇最優(yōu)的下一跳轉發(fā)節(jié)點，使得整個信息傳輸過程消耗的總能量最小[11]，降低網絡時延。

2 改進路由算法(HUF)

在進行海洋資源探索時，水下傳感器網絡可以采集海洋油氣資源勘探所需的數據信息并經過水下節(jié)點層層傳輸，最后由基站接收[12]。REPBR路由協議通過加入鏈路質量的計算提高網絡的生存時間，但是該協議沒有考慮發(fā)送節(jié)點到接收節(jié)點之間的最短路徑，導致時延增加，不能更快接收海洋數據信息。因此為降低網絡時延，減少能量消耗，避免不必要的路徑傳輸，本文改進路由算法引入效用函數策略(綜合鏈路質量、剩余能量、節(jié)點間的跳數)選擇最優(yōu)的下一跳轉發(fā)節(jié)點，降低網絡時延，提高UWSNs網絡性能。

2.1 效用函數模型

HUF路由算法建立了基于節(jié)點理性偏好特征的博弈模型來研究水下無線傳感器網絡中的路由問題。首先，將博弈模型的3個要素定義為一個三元組 (N，S，U)[13]。 其中，N代表博弈中的所有節(jié)點的集合；S代表博弈中各個節(jié)點到匯聚節(jié)點的路徑集合；U代表博弈中各個節(jié)點的效用函數，在本文的博弈模型中根據節(jié)點的效用函數值確定最優(yōu)轉發(fā)節(jié)點，并結合該節(jié)點向基站轉發(fā)數據時的跳數、當前剩余能量值和節(jié)點之間的鏈路質量給出效用函數，如式(2)所示

U=α(Mhcmax/Mhi)+β(Ei/Einit)+γ(LQ)

(2)

式中：Mhi表示當前節(jié)點向基站轉發(fā)數據路徑上的最小跳數，Mhcmax表示參與節(jié)點與基站的最大跳數，Ei和Einit分別為當前節(jié)點i的剩余能量和初始能量，LQ是發(fā)送節(jié)點和轉發(fā)節(jié)點之間計算出的鏈路質量值。ɑ，β，γ為權重因子[14]，目的是根據網絡的實際情況，調整各個參數對博弈結果的影響程度。

2.2 鏈路質量計算

在水下無線傳感器網絡中，傳感器節(jié)點在數據傳輸時，容易受到周圍環(huán)境的影響和干擾[15]。在已有的很多路由協議的設計與仿真中，很多都忽視了對通信鏈路的鏈路質量進行評估，而這種評估往往是建立在一個理想鏈路的基礎上。然而，在實踐中，通信鏈路具有隨機的波動性[16]。這樣的變化會帶來諸如網絡吞吐量下降和能耗上升等問題。在實際中，正確地評價鏈接質量，是保證可靠的網絡通訊的前提，具有重要意義。

在本文中，鏈路質量的計算結合LQI[17]和RSSI[18]兩個評估指標：RSSI是接收信號指示強度，是指無線傳感器通信過程中的信號功率；LQI是鏈路質量指示器，在硬件設備的支持下，RSSI和LQI都可以實時測量，并且可以以較低的網絡成本快速反映鏈路質量的變化，LQI和RSSI值之間存在相關性[19]，當節(jié)點i向節(jié)點j發(fā)送數據時，節(jié)點之間的鏈路質量表示為式(3)

(3)

2.3 最小跳數模型

最小跳數路由協議(LHR)是在定向擴散算法(directed diffulion，DD)[20]和洪泛算法[21](Flooding)的基礎上，引入跳數的概念而發(fā)展起來。通過發(fā)布洪泛消息，將數據分組從全網各個節(jié)點發(fā)送至Sink節(jié)點，并以最短的跳數將其傳輸至目的地，這一過程包括梯度場構建、數據分組傳輸、查詢分組傳輸以及路由維護4個步驟。通過采用最小跳數路由算法，可以有效降低開銷，節(jié)省能源，同時還可以通過路由維護來提升算法的靈活性，從而更好地適應動態(tài)網絡拓撲。

(1)梯度場建立階段：

1)我們把匯聚節(jié)點的跳躍次數設定為0，而對于其它節(jié)點，則把它們的跳躍次數調整為255。

2)sink節(jié)點通過洪泛的方法向水下無線傳感器網絡傳輸數據檢索信息，這些信息中包括了匯聚節(jié)點ID、節(jié)點深度以及最小跳躍數值HC等。

3)在接收到匯聚節(jié)點的相關信息之后，我們會把最小跳數HC+1的新HC值和匯聚節(jié)點內部的HC值做對照，若是新HC值低于原來的HC值，則用新的HC值替換報文中的HC值，替換原先的發(fā)送節(jié)點ID為代價節(jié)點ID，接著用廣播的方式將修訂過的查詢信息傳遞給相鄰的節(jié)點；若新的HC值超過了原有的值，那么就會舍棄查詢包并不做任何處理。

4)在其它節(jié)點接收到查詢信息后，再次執(zhí)行之前的處理步驟，最后形成最小跳躍數梯度場如圖2所示。

圖2 梯度建立階段

(2)數據傳輸階段：

數據傳輸過程中，一旦接收端的設備收集了信息，它會通過Flooding的形式將其傳送至匯總端。在這個過程中，每一次的HC值都會降低1，這樣就能將來自接收端的信息傳送至匯總端，并且這個過程會按照一個逐步降低的最低跳數值進行。如圖3所示。

圖3 數據傳輸階段

通過以上初始化過程，每個節(jié)點均獲得到sink節(jié)點的最小跳數，建立了到sink節(jié)點的多條最小跳數路徑，為數據包的路由轉發(fā)計算做好了準備。

2.4 HUF路由算法

2.4.1 數據獲取階段

在此階段，每個節(jié)點在較小深度的節(jié)點之間交換特定的信息。首先，每個節(jié)點定期的向它的單跳鄰居廣播一個Hello報文，Hello報文里面包括節(jié)點的跳數、剩余能量和深度。每個節(jié)點收到Hello報文后，提取Hello報文的深度信息，并與鄰居節(jié)點作比較，如果Hello報文的深度小于它的深度，它將節(jié)點保存在它的鄰居信息表中。否則丟棄此報文，完成鄰居信息表的更新，每個節(jié)點用鏈路質量算法計算節(jié)點鄰居間的鏈路質量值，Hello報文如圖4所示。

如算法1所示，信息獲取階段每個傳感器節(jié)點在特定的時間間隔內生成一個新的Hello數據包，并將其廣播給它的單跳鄰居，接著調用了接收Hello數據包來檢查信息，并調用鏈路質量算法。

算法1：信息獲取階段

// 生成Hello數據包

(1)生成Hello數據包

(2)將節(jié)點ID、深度、剩余能量和節(jié)點跳數加入數據包

(3)廣播數據包

//接收Hello數據包

(4)if 節(jié)點i的深度大于數據包的節(jié)點深度 then

(5)if 節(jié)點ID不存在于節(jié)點i的NIT中 then

(6) 將數據包的節(jié)點加入節(jié)點i的NIT中

(7)else 更新節(jié)點i的NIT

(8)end if

(9) 計算節(jié)點i的鏈路質量

(10)else

(11) 丟棄Hello數據包

(12)end if

在水下無線傳感器網絡中，節(jié)點的位置是不斷變化的，因此一些節(jié)點可能會進入另一個節(jié)點的范圍，或者一些現有的鄰居超出了節(jié)點的范圍。所以在特定的時間間隔內周期性地調用信息獲取階段，以此更新每個傳感器節(jié)點的NIT。

2.4.2 數據轉發(fā)階段

在此階段，數據包從源節(jié)點轉發(fā)到sink節(jié)點。源節(jié)點檢索它的鄰居信息表中的節(jié)點信息，并使用效用函數式(4)計算路由效益U，然后選擇路由效益最優(yōu)的節(jié)點作為轉發(fā)節(jié)點的最佳候選節(jié)點。然后發(fā)送方將所選節(jié)點的ID嵌入數據包進行廣播，鄰居節(jié)點只有收到與自己節(jié)點ID相同的才會接收數據包，鄰居信息表如圖5所示

圖5 鄰居信息表

U=α(Mhcmax/Mhi)+β(Ei/Einit)+γ(LQ)

(4)

該方程基于3個不同的指標計算路由收益，在本文中，深度低于發(fā)送方的節(jié)點具有更高的剩余能量和更好的鏈路質量以及路徑最優(yōu)，從而使路由效益最大化體現。

如算法2所示，數據轉發(fā)階段發(fā)送方節(jié)點檢索所有鄰居節(jié)點的信息，并用式(4)計算路由效益。然后發(fā)送方節(jié)點選擇路由效益最大的節(jié)點作為轉發(fā)器節(jié)點的最佳候選節(jié)點。發(fā)送方將所選節(jié)點的ID嵌入數據包，并將數據包廣播給其單跳鄰居。在接收到分組時，接收節(jié)點將其ID與嵌入分組中的ID進行比較，只有找到與其ID和嵌入在數據包中的ID匹配的節(jié)點才會接收數據包，而所有其它相鄰節(jié)點都會丟棄該數據包。該過程持續(xù)重復，直到數據包到達其中一個接收器節(jié)點。此外，發(fā)送方節(jié)點嘗試以最優(yōu)最短的路徑傳輸數據包，在保證鏈路質量穩(wěn)定的網絡狀態(tài)下選擇最優(yōu)的路徑，減少了轉發(fā)路徑過程中的網絡時延、能量消耗，提高了網絡生命周期。

算法2：數據轉發(fā)階段

//判斷節(jié)點ID是否匹配

(1)if 節(jié)點i的ID匹配數據包中的轉發(fā)ID then

//計算鄰居節(jié)點的路由效益

(2)U=α(Mhcmax/Mhi)+β(Ei/Einit)+γ(LQ)

(3)將節(jié)點的路由效益加入鄰居信息表中

(4)else 丟棄數據包

(5)按照節(jié)點的跳數和路由效益對鄰居節(jié)點進行排序

(6)end if 選擇鄰居節(jié)點中，路由效益最大的節(jié)點作為轉發(fā)節(jié)點

3 實驗仿真

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

在本文中，使用MATLAB實驗平臺進行仿真，分析了針對UWSNs提出的跳數協議的性能，基于實驗環(huán)境，給出了平臺中的某些參數的假設，見表2。

表2 實驗平臺的參數設置

3.2 實驗參數

對于實驗中所用到的對比參數：端到端時延、數據包投遞率、網絡生命周期、能量消耗，進行如下的說明：

(1)端到端時延(end-to-end delay)：數據包在網絡中從源節(jié)點到目的節(jié)點或者目的節(jié)點到源節(jié)點花費的時間，它是源節(jié)點到sink節(jié)點之間每個鏈路的傳輸延遲、傳播延遲和處理延遲的疊加。

(2)數據包投遞率(packet delivery ratio)：源節(jié)點生成的數據包數量與接收器的數據包數量之間的比率。

(3)網絡生命周期(network life time)：網絡與傳感器節(jié)點保持活動狀態(tài)的總持續(xù)時間，它是網絡啟動時間到網絡最后一個節(jié)點停電時間之間的時間間隔。

(4)能量消耗(energy consumption)：數據傳輸后的初始能量與剩余能量之差。

3.3 仿真實驗結果分析

如圖6所示，分別測量了HUF、REPBR、DBR和EEDBR的網絡壽命，并與之進行比較?？梢钥闯鯠BR的生命周期比HUF、REPBR、EEDBR短，這是由于在DBR中沒有考慮剩余能量度量，而是只依賴深度信息進行下一個節(jié)點的選擇。因此較小深度的節(jié)點會更快地耗盡其能量，導致網絡崩潰。相比之下，EEDBR的網絡生存時間比DBR長，這是由于在EEDBR中利用剩余能量和深度信息，導致節(jié)點間能量消耗均衡。HUF和REPBR在網絡生存方面的性能優(yōu)于DBR和EEDBR，在REPBR中，每個發(fā)送節(jié)點都選擇剩余能量更高、鏈路質量更好的轉發(fā)節(jié)點，因此在網絡拓撲中，網絡生存時間都較長，但是HUF考慮了節(jié)點信息中跳數最小、剩余能量更高、鏈路質量更好的最優(yōu)轉發(fā)節(jié)點，所以網絡生存周期比REPBR更長，同時跳數的選擇計算也需要消耗一定的節(jié)點能量，所以HUF的生存時間略高于REPBR。DBR和EEDBR的網絡生存時間都是隨著節(jié)點數的增加而減少，DBR只利用深度信息來選擇最短路徑，而不考慮剩余能量，總是選擇深度最大的節(jié)點，這樣可以更快地耗盡節(jié)點的能量，減少網絡的生存時間，EEDBR缺乏鏈路質量指標，導致跳數增加，進一步減少網絡生存期。REPBR和HUF隨著網絡中節(jié)點數量的增加而獲得更穩(wěn)定的網絡生存期，這是因為下一個轉發(fā)節(jié)點的選擇是基于路由效益的，REPBR路由效益通過鏈路質量和剩余能量計算，平衡能量消耗，HUF利用最小跳數、剩余能量和鏈路質量，減少跳數轉發(fā)、平衡能量消耗，因此REPBR的網絡生存時間比HUF略短。

圖6 生命周期對比

如圖7所示，本文測量DBR、EEDBR、REPBR和HUF的能量消耗，結果表明，算法的能量消耗隨著節(jié)點數量的增加而增加。HUF的能耗明顯比DBR、EEDBR低，略低于REPBR。DBR沒有任何能量因子，只利用深度信息來選擇下一個轉發(fā)節(jié)點，是不斷增加能量消耗的主要原因，此外，冗余報文在DBR中傳輸時，也會產生較高的能量消耗。EEDBR比DBR能耗低，這是因為EEDBR不僅利用剩余能量和深度信息來選擇下一個轉發(fā)節(jié)點，還減少了報文的傳輸數量，以此均衡節(jié)點間的能量消耗。REPBR和HUF都具有較好的能量平衡能力，都利用了剩余能量和鏈路質量度量，可以平衡節(jié)點之間的能量消耗和最佳的鏈路質量，所以在網絡初始階段節(jié)點數為100、150、200時，兩者的能量消耗幾乎持平，然后隨著節(jié)點數量的增加，由于REPBR沒有對下一轉發(fā)節(jié)點的跳數進行處理，故傳輸路徑的長度增加，而HUF根據協議選擇跳數最小的轉發(fā)節(jié)點，根據路由效益選擇全局最優(yōu)路徑，減少節(jié)點之間的轉發(fā)，從而減少能量消耗，所以在節(jié)點數逐漸增加時，HUF的能耗略低于REPBR，具有更低的能量消耗。

圖7 能量消耗對比

如圖8所示，可以看出，HUF的端到端時延比REPBR、EEDBR、DBR低。這是由于HUF減少了源節(jié)點到匯聚節(jié)點之間的轉發(fā)跳數，結合剩余能量和鏈路質量，選擇了全局最優(yōu)最短路徑，從而減少整個端到端網絡時延，總體性能優(yōu)于DBR和EEDBR，特別是在網絡密集，即網絡中節(jié)點數量較多的情況下。隨著傳輸節(jié)點的增加，DBR只依賴深度信息轉發(fā)數據，具有更高的端到端時延，EEDBR基于剩余能量的數據包保持時間，但是如果第一轉發(fā)節(jié)點的數據包丟失，接下來的保持節(jié)點轉發(fā)數據包會造成相當大的延遲。REPBR具有良好的鏈路質量，但是對于鄰居節(jié)點之間的最短路徑選擇，它并沒有給出任何解決方案，因此，加入轉發(fā)過程的節(jié)點數量隨著節(jié)點數增加而增加，導致轉發(fā)路徑繁雜，跳數增加，進而增加了端時延。

圖8 端到端時延對比

如圖9所示，隨著網絡中節(jié)點數量的增加，HUF的數據包投遞率總體上比DBR、EEDBR和REPBR要高。DBR獲得的數據包傳遞率幾乎相同，這是因為節(jié)點數量的增加，缺乏鏈路質量指標，所以候選節(jié)點的數量也會增加。另外，DBR是基于深度信息，并且是基于接收者的路由方式，故增加了不必要的轉發(fā)，導致丟包概率高。EEDBR根據剩余能量來選擇下一個轉發(fā)節(jié)點，導致跳數增加，進而降低了數據包的傳遞率。REPBR利用剩余能量和鏈路質量來選擇最短路徑，但在高密度網絡中，選擇最佳轉發(fā)節(jié)點的效率較低，導致數據包傳遞率相對偏低。在節(jié)點數目設置為150時，HUF的數據包投遞率略低于REPBR，但是隨著節(jié)點數量的增加，HUF獲得了更高的數據包投遞率，這是因為HUF在路由效益中考慮了鏈路質量和可靠的節(jié)能最短路徑選擇，有效地實現了數據包的成功傳遞。例如，在路由效益計算中，選擇剩余能量最高、鏈路質量最好、路徑傳輸最短的節(jié)點，可以平衡能量消耗，獲得穩(wěn)定的鏈路，保證數據包的轉發(fā)。HUF算法選擇最短路徑，抑制不必要的轉發(fā)，從而在合理的數據包投遞率下減少轉發(fā)的數據包總數。如圖所示，節(jié)點數為400時，HUF比DBR、EEDBR、REPBR分別提高了約3%、10%、2%。

圖9 包投遞率對比

4 結束語

為解決水下無線傳感器網絡在節(jié)點不斷移動和增加的情況下，節(jié)點轉發(fā)不是最優(yōu)最短路徑、能量消耗不均衡、端時延較高等問題，本文提出一種基于REPBR跳數效用轉發(fā)的改進路由算法，該算法選擇下一個最優(yōu)轉發(fā)節(jié)點進行數據轉發(fā)，與目前最先進的技術相比，顯著提高了UWSNs的性能。實驗結果表明HUF算法提高了路由效益，數據包傳遞率更高、端到端時延更低、網絡生存周期更長和能量消耗更低。在未來的工作中，將考慮通過結合預計期望傳輸次數選擇更合適的轉發(fā)節(jié)點，進一步優(yōu)化路由協議的性能。