避免路由循環和空洞節點的水下傳感器網絡深度路由算法*

蔡文郁，張銘坤，張美燕

(1.杭州電子科技大學電子信息學院，浙江 杭州 310018；2.浙江水利水電學院電氣工程學院，浙江 杭州 310018)

隨著陸地自然資源逐漸枯竭，越來越多的科學研究和新能源探索逐漸轉移到水下環境，這使得水下無線傳感器網絡(UWSN)受到了世界各國的廣泛關注[1]。水下無線傳感器網絡可以廣泛應用于軍事防御系統、海岸線監視與保護、海底資源勘探、海洋環境監測和輔助導航等場合。由于水體環境的無線電信號衰減非常嚴重，而水聲信號卻可以傳播到較遠的距離，因此在水下環境中水聲通信是目前的主要技術方式[2]。然而，水聲通信存在著傳播速度低、帶寬有限、動態性高、能量有限和部署成本高等問題[3]，并且水下信道具有多徑衰落、噪聲、路徑損耗和多普勒擴頻等特性，導致較高的丟包率和數據包傳輸時延等問題[4-5]。此外，節點移動性也是水下無線傳感網絡中一個不可忽視的重要影響因素。水下節點的移動特性導致傳統的無線路由協議無法用于水下無線傳感網絡[6]。因此，針對UWSN 的可靠數據路由技術仍然是一個巨大的挑戰。

現有的水下無線傳感網絡路由方法可以分為兩類:基于地理信息的路由協議[7-8]和無地理信息的路由協議[9-10]。基于地理信息的路由協議需要獲取水下傳感器節點的位置信息，條件較為苛刻，很難進行實用，因此無地理信息的路由協議是目前的主要研究方向。基于深度信息的路由協議(DBR)[9]根據鄰居節點的深度來選擇下一跳節點:假設每個水下節點都能獲知其鄰居節點的深度信息，并選取深度最小的鄰居節點作為下一跳轉發節點。但是DBR 沒有考慮轉發節點的剩余能量和節點連通性，容易導致節點能量消耗的不均衡，也容易陷入局部最優的路由循環。能量優化的深度路由協議(EEDBR)[10]根據網絡節點的剩余能量和深度信息計算轉發權重，并更新數據包的保持時間，有效降低了節點能量消耗和端到端傳輸延遲，但是EEDBR 協議還存在著負荷分配不均衡的問題。基于深度的多跳路由協議(DBMR)[11]采用多跳轉發的方式，減少了數據包冗余傳輸以及通信信道的占用。能量均衡、高效、可靠的路由協議(EBER2)[12]通過結合考慮下一跳節點的能量和潛在轉發節點的數量來均衡網絡能耗，提高網絡壽命。但是EBER2 協議只是單純的貪婪轉發策略，存在較高的傳輸延遲，并且通過高速的光纖鏈路實現與海面Sink 節點的通信，部署成本非常昂貴。基于轉發區域劃分的加權深度路由協議(WDFAD-DBR)[13]在DBR 的基礎上還考慮了2-Hop鄰居節點的深度值，減少了空洞節點發生的概率，提高了網絡的可靠性和數據包投遞率。但是，WDDAD-DBR 協議在計算數據包轉發權重時并沒有考慮剩余能量，導致節點能量消耗不均衡，從而降低了網絡整體生存周期。增強空洞避免路由協議(E-VAR)[14]可以實現對空洞節點的標記，優先選擇非空洞節點作為下一跳轉發節點。E-VAR 協議可以避免部分空洞節點，但是還可能存在路由循環現象，導致數據包的冗余傳輸。

針對現有路由協議存在的問題，提出了一種避免路由循環和空洞節點的深度路由協議PE-VAR，對節點是否屬于空洞節點進行自我標記，以循環路徑中節點的鄰居數、能量、深度等參數綜合計算正向推進距離值和替換優先值，遴選出需要替代或者避開的節點，從而抑制出現循環路徑時的冗余傳輸。相比較E-VAR 協議，PE-VAR 協議無需獲取網絡節點的三維坐標，增加了節點的替換優先值計算以及對路由路徑循環的監測環節，有效解決數據傳輸過程中出現的循環路由情況，減少數據包的冗余傳輸，提升整個網絡的生命周期。

1 系統模型與假設

1.1 UWSN 網絡模型

水下無線傳感網絡是由隨機分布在三維空間內的眾多水下傳感器節點和隨機分布在水面上的Sink節點組成，假設每個水下節點都配置了水壓傳感器，因此可以獲取節點自身所處的深度值。源節點采集周圍環境的感知數據并利用水聲通信模塊發送，中繼節點接收到后進行優化轉發，最后將感知數據傳輸到海面Sink 節點。假設水下無線傳感網絡中水下節點的內部時鐘都可以保持同步狀態，并具有相同的初始能量E0，由于水面Sink 節點的電能不限，因此假設所有水下節點都能收到水面Sink 節點的HELLO 數據包。綜上所述，本文研究的UWSN 模型如圖1 所示。

圖1 UWSN 網絡模型

1.2 水聲傳播衰減模型

水聲傳播過程中主要有兩方面的衰減:①擴散損失，聲波在不斷擴散過程中引起聲強衰減；②吸收損失，由于介質粘滯、熱傳導以及其他弛豫過程導致的衰減[11]。水聲傳播衰減模型的表達式如下:

式中，d為傳播距離，n在淺海中取值為1.5，a為吸收系數，單位為dB/km，計算方法如式(2)所示[12]:

式中，f為聲波頻率，單位為kHz。

1.3 節點移動模型

水下傳感器網絡一般應用于淺水區域，水流速度相對較慢，水下傳感器的節點運動較為緩慢。文獻[6]提出了一種基于歐拉方法的節點移動模型，如下式所示:

式中，Vx表示的是節點x軸方向的速度，Vy表示的是節點y軸方向的速度。k1，k2，k3和λ與潮汐、深度等水體環境相關，k4，k5是兩個隨機變量。本文傳感器節點的移動模型采用了上述移動模型，參數取值與文獻[6]一致:k1，k2是服從N(π，0.1π)分布的隨機數；k3是服從N(2π，0.2π)分布的隨機數；k4，k5是服從N(1，0.1)分布的隨機數；λ是服從N(3，0.3)分布的隨機數。

1.4 能量消耗模型

本文采用文獻[13]中的節點能量消耗模型，忽略數據接收所需的能量，發送數據的能耗公式如下所示:

式中，m表示傳輸數據的長度，Eelec表示節點發送(接收)1 bit 數據所消耗的能量，εfs表示自由空間模型信號放大倍數，εamp表示多徑衰減模型信號放大倍數，d0表示功率距離閾值，d為數據收發兩端之間的距離。

2 PE-VAR 路由協議

DBR 協議[9]的主要思想是貪婪轉發策略，即讓發送節點選擇所有其鄰居節點中深度最小的節點作為最優的下一跳轉發節點。但是，DBR 協議容易陷入局部最優，遇到空洞節點后，會使得數據包在兩個或多個節點間循環傳輸。根據節點在水下網絡中的位置不同，可以分為普通節點(擁有正向推進鄰居節點，即存在鄰居節點深度小于當前節點深度的情況)、孤立節點(沒有鄰居節點)、空洞節點(沒有正向推進的鄰居節點，即所有鄰居節點深度都不小于當前節點深度)、死亡節點(能量耗盡沒有數據轉發能力的節點)。圖2 表示了三維水下無線傳感網絡中典型的路由循環場景:節點Ni沒有發現比當前節點具有更小深度的鄰居節點，而且節點Ni也無法與Sink 節點直接單跳通信，因此Ni為空洞節點。而且，節點Nj選擇的下一跳節點為Ni，之后的數據包傳遞將會再次重復原路由路徑，出現了無謂的路由循環情況，數據包無法可靠、及時地發送到水面Sink 節點。

圖2 空洞節點和路由循環案例

E-VAR 協議[14]會對空洞節點的標記，優先選擇非空洞節點作為下一跳轉發節點，雖然能在傳輸時避免途徑部分空洞節點，但依然可能存在路由循環現象，導致數據包的冗余傳輸。為此，PE-VAR 協議增設了節點的替換優先值計算以及對路由路徑循環的監測環節，有效地解決了E-VAR 協議存在的問題。

針對以上路由循環和空洞節點問題，PE-VAR協議的主要思想如下:當水下節點啟動或者定時器觸發時，每個節點執行自我標記流程，完成后將自身信息廣播給其鄰居節點；然后，水下節點進行數據包的轉發，若檢測到當前路由路徑中出現路由循環，則觸發路由循環處理機制，更換轉發節點；最終，避免路由循環陷阱，實現數據包的有效轉發。PE-VAR協議主要分為以下三個階段:自我標識定義、選擇轉發節點、避免路由循環。

2.1 自我標識定義

當節點啟動開始工作或者達到預設的定時時間，啟動自我標識過程:傳感器節點Ni和Sink 節點都會廣播HELLO 數據包，用來告知其鄰居節點自身的信息，HELLO 數據包含如下信息:HELLO 標簽、發送節點ID、剩余能量Ei、發送節點深度信息Hi、發送時間戳。網絡中所有節點收到HELLO 數據包后通過統計計算，獲取節點Ni的鄰居節點集Gi、鄰居節點集的長度｜Gi｜。節點Nj∈Gi(j＝1，2，…，｜Gi｜)收到HELLO 數據包后回復REPLY 數據包，包含以下字段信息:REPLY 標簽、發送節點ID、剩余能量Ej、發送節點空洞標記Fj(若節點無正向推進鄰居節點，則值為1，反之為0)、發送時間戳和鄰居節點集信息，鄰居節點集Gj數據包含如下信息:鄰居節點ID、鄰居節點剩余能量、鄰居節點深度數據。水下傳感器節點根據收發HELLO 數據包的時間戳差值，依據水聲通信速率計算出與鄰居節點間的歐氏距離。

節點Ni的自我標識流程如圖3 所示:初始化時Ni的空洞標識為0，鄰居節點集Gi為空。根據HELLO 包中的時間戳與自身內部時鐘插值，來計算節點Ni與Sink 節點之間的歐式距離Dis，當Dis小于最大傳輸范圍Rmax時，節點Ni與Sink 節點直接單跳通信；否則，節點Ni更新其鄰居節點集Gi，并保存鄰居節點Nj到離其最近Sink 的歐氏距離Djs。若Dis小于其所有鄰居中最小的Djs，則表示節點Ni為空洞節點，并進行標記，即Fi＝1，否則Ni為正常節點，保持Fi＝0。

圖3 節點Ni 的自我標識機制

2.2 選擇轉發節點

PE-VAR 協議的數據包轉發策略如圖4 所示，節點根據數據轉發策略選擇優化的下一跳節點。如圖4 所示，數據發送節點Ni遍歷鄰居表Gi，若鄰居表為空，則當前節點為孤立節點，丟棄數據包，等待下一次節點自我標識過程；若鄰居表不為空，搜索鄰居表中是否包含Sink 節點，若包含則直接將數據包傳輸給Sink 節點，否則對鄰居節點集進行正向推進距離值計算，如果存在普通節點，則優先考慮鄰居節點集中的正常節點，其次才考慮空洞節點。計算鄰居節點的正向推進距離值Adv(即發送節點Ni離其最近Sink 節點的歐式距離Dis與其鄰居節點Nj到其最近Sink 節點的歐式距離Djs之差)，如下式所示:

圖4 數據包轉發策略

如果鄰居節點Nj為空洞節點(Fj＝1)，則要避免其被選為下一跳轉發節點。由于(Dis-Djs)∈(0，2×Rmax]，若鄰居節點Nj為空洞節點則要將其Dis與Djs的差值再減去2 倍最大傳輸半徑Rmax，則可確保其被選擇的概率低于所有非空洞鄰居節點被選擇的概率。最終選擇Adv 值最大的鄰居節點作為下一跳轉發節點。

2.3 避免路由循環機制

當數據傳輸中出現循環路徑時，PE-VAR 協議設計了一種路由循環避免機制。多跳傳輸的數據包中按序記錄了轉發節點的ID，如果下一跳轉發節點ID 在當前路由路徑中出現過，則可判斷出現路由循環。節點Ni的替換優先級值Pi定義如下:

式中，｜Gi｜表示節點Ni鄰居節點集的長度，Hi表示節點Ni的深度，表示節點Ni的鄰居節點集中第k個節點的深度，表示當前節點Ni與其鄰居節點Nk的歐氏距離，δ表示的系數，Rmax表示節點最大傳輸半徑，Ei表示節點Ni的剩余能量，E0表示節點的初始能量。

替換優先級既考慮了當前節點與其所有鄰居節點歐氏距離，又考慮了剩余能量率因素。而且，本文對替換優先級的影響因素采用了線性歸一化處理，綜合權衡了距離值與剩余能量率等因素。歸一化后歐氏距離的差值越大，說明選擇該下一跳節點能夠傳輸更遠，推進數據包的正向傳輸。歸一化后的剩余能量率越小，則盡量不選擇其為轉發節點，防止該節點過早死亡，影響下一輪次的數據包傳遞。

如果檢測發現了數據傳輸路由循環，PE-VAR協議根據路由循環中各節點的替換優先級值來選擇合適的下一跳節點。如圖5 所示，Ni根據鄰居表中各鄰居節點的Adv 值選擇預轉發節點Nj，發送節點遍歷當前路徑列表Rcur，若Nj未在Rcur中出現過，則直接確定下一跳節點為Nj；如果Nj已在Rcur中出現過，則截取記錄當前循環路徑。循環路徑Sc截取方式:先找到重復節點Nj在Rcur中的位置，將該位置作為截取路徑的起始位置，然后依次向后遍歷Rcur直至尾部，并將所遍歷到的節點按序存入循環路徑Sc中。

圖5 循環路徑處理流程

綜上所述，Pi值越大表示節點Ni具有更優的鄰居節點可供選擇。為了避免路由循環問題，在替換優先級最大節點的鄰居節點中，將其當前的最優候選轉發節點存入避選節點集中，以避免冗余循環傳輸。循環避免的示例如圖6(a)所示:路由循環由3、4、20、6、7、8 節點組成，假設7 號節點的優先級最大，因此7 號節點的預選轉發節點8 號節點將存入避選節點集中，避免其被選為下一跳節點。當數據包再次傳輸到7號節點時，選擇其鄰居節點中Adv 值最大的12 號節點作為下一跳轉發節點，如圖6(b)所示。因此，轉發路徑就不會按照原先的路徑繼續重復傳輸，避免了無謂的路由循環。

圖6 路由循環處理

3 仿真結果

本文采用MATLAB R2020b 仿真平臺對本文所研究的PE-VAR 算法進行性能驗證，與現有的DBR、E-VAR 算法在數據包投遞成功率(Packet Delivery Success Rate，SR)、數據包投遞時延(Packet Delivery Delay，PD)、節點死亡率(Node Dead Rate，DR)、能量消耗(Energy Consumption，EC)等方面進行對比。DBR、E-VAR、PE-VAR 三種路由方式采用的網絡仿真環境以及參數相同，主要參數如表1 所示。

表1 仿真參數

為了提高仿真結果的可靠性，每種仿真場景重復20 次實驗，每次實驗300 輪。每一輪仿真結束后，依照上文的水下節點運動模型改變傳感器節點的位置。每次實驗的數據源節點從當前網絡中未死亡的節點中隨機選擇，最后取數據平均值作為最終結果。網絡仿真場景如圖7 所示，節點移動路徑如圖8 所示。

圖7 UWSN 仿真模型

圖8 水下節點移動路徑

在相同的USNs 絡模型和起始節點情況下，PE-VAR、DBR、E-VAR 三種算法獲取的路徑對比如圖9 所示。在相同的仿真網絡環境下，三種路由方法均以節點12 作為源節點進行數據包發送遞，DBR方法在節點79 和節點45 之間出現雙節點路由循環，導致一個節點死亡，另一節點沒有鄰居節點進行數據傳遞，最終路由失敗；E-VAR 方法，出現節點79、11、3 之間的多節點循環，導致一個節點能量先耗盡，導致路由方向向下，最后失敗于節點85 和節點57 造成的雙節點循環；PE-VAR 避免了上述的路由循環問題，根據替換優先級，對造成這種情況影響較大的節點避免作為下一跳節點，最終成功將數據包傳輸給Sink 節點。

圖9 路徑對比結果

圖10 和圖11 比較了DBR、E-VAR、PE-VAR 三種路由在節點靜態和節點動態兩種仿真環境下性能對比。無論是節點靜態還是節點動態情況，本文提出的PE-VAR 路由協議在四項性能指標上，在節點個數為100～300 時，均優于DBR 和E-VAR 協議，當節點數為300～400 時，由于節點密度過大，使得該區域網絡負載過大，在迭代一定次數后節點死亡數量大，導致三種路由在節點死亡率與網絡能耗性能差異不明顯。仿真結果表明，PE-VAR 算法較DBR和E-VAR 算法而言，提高了數據包投遞成功率，降低了數據包平均投遞時延、節點死亡率以及網絡總體能量消耗百分比，最終提升了整體網絡的性能，延長了網絡生命周期。

圖10 節點靜態時網絡性能對比

圖11 節點動態時網絡性能對比

4 結語

通過考慮路由過程中出現的循環冗余傳輸情況，提出了一種避免路由循環和空洞節點的基于節點深度值的路由協議，通過比較路由循環中各節點的優先級，更換替換優先級值最大的節點的原轉發節點，跳出循環并繼續進行數據包的轉發。仿真結果表明，PE-VAR 算法在數據包投遞成功率、數據包投遞平均時延、節點死亡率、平均能量消耗性能方面，相比較DBR 算法和E-VAR 算法，都有一定提升。