淺水環境中基于熵的能量均衡路由優化算法

馮立波　丁魏魏　王金麗　張梅　羅桂蘭　陳本輝

摘 要： 淺水環境具有覆蓋面積小、水位低、水底環境較為復雜的特點，當在水下部署傳感器節點時，其傳輸路徑容易受到水底障礙物、水中雜物、水浪等影響，給水下傳感器的路由選擇帶來困擾。針對淺水中傳感器節點路由選擇困難、能量消耗不均、生命周期短的問題，提出一種基于熵的能量均衡路由算法。該算法綜合多種節點部署形式，在節點均勻分布和非均勻分布兩種條件下分別計算傳感器網絡通信的能量損耗，權衡考慮節點的剩余能量和位置信息來選擇下一跳節點，從而均衡網絡能耗。利用NS?2仿真工具對該算法的性能進行仿真分析。結果表明該算法能夠實現淺水中的節點通信，有效延長網絡生命周期。

關鍵詞： 淺水環境； 熵； 能量均衡； 路由算法； 路由優化

中圖分類號： TN911?34； TP391； TN915 文獻標識碼： A 文章編號： 1004?373X（2017）06?0040?05

Abstract： The shallow water environment has the characteristics of small size， low water level and complex underwater environment. When the sensor nodes are deployed in the water， their transmission paths are easy to be influenced by underwater obstacles， debris， waves and so on. Aiming at the problems， such as difficult routing choice， unbalanced energy consumption and short life cycle， a kind of energy balance routing algorithm based on entropy is proposed. In this algorithm， the energy loss model of sensor network communication is calculated under two different conditions of uniform distribution and non uniform distribution of the nodes. The performance of the algorithm is simulated with NS?2. The results show that the proposed algorithm can achieve the node communication in shallow water and prolong the network lifetime effectively.

Keywords： shallow water； entropy； energy balance； routing algorithm； routing optimization

水下傳感器網絡由大量低價格、低功耗的傳感器節點構成。這些節點通過各種傳感器感知、收集信息，并通過中間節點將這些信息傳送給基站，廣泛應用于湖泊海洋水質監測、水文資源管理等領域[1]。相對于海洋大范圍水文監測，淺水環境具有覆蓋面積相對較小、深度低，湖底環境較為復雜等特點。更好地將傳感器網絡應用于高原湖泊的水文監測，已經成為當前的一個研究熱點。針對湖泊環境特點，建立傳感器網絡的通信模型以及將環境監測數據快速傳送到監測中心是水下傳感器網絡應用的中心環節。水下無線傳感器網絡面臨的最大挑戰是網絡的能量非常有限。傳感器網絡節點能量供應是一個重要問題，因此需要最大限度地提高節點及網絡的能量有效性，提高網絡的生存期，是該類網絡的主要設計目標之一[2]。本文提出一種基于熵的能量均衡路由算法（EBRABOE）。該算法根據能量損耗模型，綜合考慮節點的剩余能量和位置信息來選擇下一跳節點，從而平衡網絡能耗。當節點確定分布時，主要考慮下一跳到Sink節點的能量消耗來確定下一跳；當節點非均勻分布時，先計算各自下一跳到Sink節點的距離，如果有出現兩個節點的距離相等再考慮各自的能耗情況。

1 水下傳感器網絡通信模型

1.1 布爾感知模型

三維空間的無線傳感器網絡節點采用布爾感知模型[3]。

在感知模型中，三維傳感器網絡的覆蓋具有等大小、可互相重疊的特性，具備一個球體對空間覆蓋的含義。在三維無線傳感器網絡空間[4?5]中，計算節點之間的最優部署方法，可以轉變為計算三維空間中最節約的球覆蓋方法，也即是將此問題轉換為三維球形的覆蓋問題。二維平面上正六邊形的蜂窩覆蓋是最優的覆蓋模型，同理可知，三維空間的最優覆蓋形式應該是三個坐標平面的投影都應該是二維空間的最優覆蓋形式（即正六邊形覆蓋），但這種模型是不存在的。因此下面將要對現有的立方格（六面體）、體心立方格（截角八面體）、面心立方格（十二面體）進行比較。

1.2 現有模型的比較

簡單立方格的Voronoi單元為立方體（六面體），體心立方格[6]的Voronoi單元為截八面體，面心立方格的Voronoi單元為菱形十二面體。如圖1所示，在正六面體、八面體和十二面體下的圖形。

其中Voronoi是泰森多邊形又稱Dirichlet圖，它是由一組由連接兩鄰點直線的垂直平分線組成的連續多邊形組成。泰森多邊形的特性是：每個泰森多邊形內僅含有一個離散點數據；泰森多邊形內的點到相應離散點的距離最近；位于泰森多邊形邊上的點到其兩邊的離散點的距離相等。

用Vvor表示Voronoi單元的體積，R是Voronoi單元的內接球半徑，覆蓋半徑Rf是Voronoi單元的外接球半徑，所以由空間幾何知識可得表1。

由表1可以看出，當內接球半徑R為常數值，體心立方格的覆蓋半徑最大，即覆蓋范圍最廣。由此可知，體心立方格是三維空間中最節約節點的覆蓋形式。

1.3 無空洞覆蓋

三維空間中的無空洞覆蓋問題可以轉換為三維球體覆蓋問題。這是由于等大小、可互相重疊的球體對空間的覆蓋是基于三維感知模型的三維傳感器網絡覆蓋的固定特性，該特性的存在導致解決三維傳感器網絡的最優部署問題直接相當于解決三維空間中最節約的球覆蓋問題。給出公式[d=43πR3Vvor]，可以分別計算得出三種立方格的覆蓋厚度d，如表2所示?？梢钥闯鋈咧畜w心立方格的覆蓋厚度d最小。

1.4 能耗模型

Pd表示數據包被接收的最低功率值，d表示數據包的傳輸距離，則節點的發送能耗Esend（d）可以表示為：

[Esendd=Pd?T?Eattenuationd] （1）

式中：T表示數據包發送消耗的時間；[Eattenuationd]表示數據包傳輸距離為d時的能量衰減，表示為：

[Eattenuationd=dλad] （2）

式中：[λ]為能量擴散因子；參數[a=10a（f）/10]由吸收系數a（f）決定，a（f）表示如下：

[a（f）=0.1110-3f21+f2+4410-3f24 100+f2+2.75×10-7f2+3×10-6] （3）

式中：f為載波頻率，單位為kHz；吸收系數a（f）的單位為dB/m。

2 算法思想與實現

2.1 算法思想

本文中提出EBRABOE充分考慮了能量均衡因素，考慮兩種情況，節點確定分布和非均勻分布。傳感器網絡上的能量損耗與網絡傳輸的數據量和節點距離基站距離有關[7]。傳輸的數據量越大，節點距離基站的距離越遠，能量損耗就越大，大大降低了網絡生命周期[8]。這樣就要求算法在確定下一跳時，使具有較大能量且距離基站近的節點有較大的發送數據的機會，使能量較低、遠距離的節點發送或接收數據的機率變小。熵被定義為從開始到結束一組節點相對耗能最少的量。這就是基于熵的能量均衡算法思想。

2.2 熵的定義

如果一組節點從開始到結束節點的接收傳送能量消耗最小，則這條路徑就可以被認為是最優路徑。本文取3個量來衡量：節點的位置、能耗及其傳感半徑。假定a，b為兩個相鄰的節點，分別距離Sink節點為d0，d1，且d0>d1。

由自由空間傳播模型可知，Free Space傳播模型假定了一種理想化傳播環境，即在發射方和接收方只有一條無障礙的直線路徑。H.T.Friis提出了一種接收信號功率的計算公式如下：

[Pd=PtGtGrλ24π2d2L] （4）

式中：d為發送方和接收方的距離；[Pt]為發射信號的功率；[Gt]和[Gr]分別為發送方和接收方的天線增益；L（L≥1）為系統損耗；[λ]為波長。

經過第一次接收數據和發送數據，a節點的相關特征數值表示為：

[Va=posa，x，y，zEconsumea，r-Econsumea，s] （5）

式中：[posa，x，y，z]表示節點的位置；[Econsumea，r]表示節點接收數據消耗的能量；[Econsumea，s]表示節點發送數據消耗的能量。

由上述設定條件可知，假設節點A發送一個數據包到節點B，節點B又把該數據包發送給C，可以認為A到B消耗的能量與B到C消耗的能量大體是相等的即EA?B，EB?C，即轉發同樣的數據分組時，節點所消耗的能量大體相等，節點能量消耗只與轉發數據有關。即[Econsumea，r]為常數，而由上述公式可知：

[Econsumea，s=ε2d0] （6）

式中：d0為節點到Sink節點的距離；ε為無線信號傳播參數。同理，b節點的相關特征數值表示為：

[Vb=posb，x，y，zEconsumeb，r-Econsumeb，s] （7）

[Econsumeb，r=Econsumea，r]時發送數據耗能公式為：

[Econsumea，s=ε2d1] （8）

由上述公式中可以看出，定義熵為：

[ENTROPY=Econsumei=Econsumei，r+Econsumei，s] （9）

式中，i表示節點，i[∈1，2，…，n]，n表示節點個數。

當熵的值最小，即能量消耗最少時，該條路徑為最優路徑。

2.3 算法實現過程

算法主要分為4個階段，首先進行三維虛擬網格剖分，向節點發送廣播信息，其次是鄰居節點集合建立并獲取鄰居節點位置信息，然后通過判斷節點是否均勻分布，當均勻分布時通過計算節點剩余能量來確定下一跳；當節點是非均勻分布時通過計算到下一跳鄰居節點的距離來確定下一跳，最后進入數據穩定傳輸階段。

（1） 網絡初始化。在此階段，形成虛擬單元格，每個虛擬單元格根據所處位置有一個標號，方便數據傳輸，同時每個虛擬單元格內（即一個簇內）的節點都要有一個簇內惟一的ID。如圖2所示。

（2） 鄰居節點集合建立。產生數據的源節點i以一定的廣播半徑R廣播Hello尋路信息。Hello尋路信息中包含源節點的位置信息和發送功率信息，在廣播范圍R內的j節點計算出與源節點的度量值d，并且通過自身位置信息和求出的距離來判斷能否作為下一跳節點，滿足成為下一跳條件的節點以通信距離d向源節點發送應答信息。

（3） 確定下一跳。同時有多個節點對尋路做出應答，那么源節點必須做出選擇，選出最佳的下一跳節點。分為以下兩種情況：

① 節點確定分布。由上述設定條件可知，假設節點A發送一個數據包到節點B，節點B又把該數據包發送給C，可以認為A到B消耗的能量與B到C消耗的能量大體是相等的即EA?B=EB?C，即轉發同樣的數據分組時，節點所消耗的能量大體相等，節點能量消耗只與轉發數據有關。

每個節點消耗的能量有兩方面：與n-1個節點進行數據收發消耗的能量；與Sink節點通信消耗的能量。

參照自由空間模型，即在發射方和接收方只有一條無障礙的直線路徑，如圖3所示。

A點到Sink節點就只有一條直線路徑，有：

[Econsume=n-1Ee+Ee+εd2BS] （10）

式中：[Ee]表示接收或發送數據消耗的能量；dBS表示節點到Sink節點的距離；ε表示無線信號傳播參數；n表示節點的個數。Econsume數值越小，表明消耗的能量越小，即剩余能量越多。剩余能量越多，說明采用這種算法建立的路由在數據傳輸過程中消耗的能量越少，也就是說這種路由算法在保證傳輸能耗方面具有相對較好的特性；反之，總剩余能量越小，說明這種路由算法在數據傳輸過程中消耗的能量較大，不利于節省網絡能量。

② 節點非均勻分布。每個節點是不規則地隨機分布，每個節點都有惟一的ID號。傳感器節點是非地理位置感知的，如圖4所示。

如果節點A發送數據給C，選擇節點B作為下一跳的條件是當且僅當：

[D2A-C>D2A-B+D2B-C] （11）

成立時，節點A選擇節點B作為下一跳將數據轉發給C。其中DA?C，DA?B，DB?C分別表示節點A與C、節點A與B、節點B與C之間的距離。

（4） 數據按照建好的路由結構傳輸給BS。源節點在選擇好下一跳路由后發送采集得到的有用信息然后該轉發節點變成源節點，繼續尋找選擇最優下一跳節點。

3 算法仿真和性能分析

3.1 仿真場景及參數

為了分析EBRABOE算法的有效性，本文利用仿真平臺NS?2對網絡生存時間、網絡平均時延、節點平均能量消耗等指標進行仿真和分析。

仿真時，將50個傳感器節點部署在水下三維監測區域中，分為隨機部署和確定部署。監測區域大小為300 m×300 m×300 m，Sink節點位于水平面中心即坐標為（150，150，300）。進行虛擬網格剖分時，為了方便計算，將監測區域劃分為300×300×300個小立方格，每個立方格的大小為1 m×1 m×1 m。仿真結果是50輪仿真實驗所得結果的平均值，其他參數設置如表3所示。

表3 仿真環境參數設置

3.2 性能測試和分析

在前面工作基礎上，分別對節點網絡生存時間、網絡平均時延和節點平均能耗進行了仿真。

3.2.1 網絡生存時間

在兩種條件下進行網絡生存時間的仿真分析： 網絡中第一個節點死亡的時間；網絡中生存節點個數。

圖5和圖6為EBRABOE網絡生存期測試結果。從圖5可以看出在仿真過程中，節點確定分布情況下第一個節點的死亡時間要比節點隨機分布晚。

當網絡規模小于30個節點時，網絡壽命將提高。這是因為隨著網絡規模的變大，廣播Hello包的數量也隨之增加，節點找到一條從源節點到Sink節點的最優路徑時間變長，算法收斂速度變小，導致能耗也因此增加。

從圖6可以看出，從開始到90 s左右的這段時間內，節點確定分布情況下沒有節點死亡，而節點非均勻分布時從60 s開始就有節點持續死亡。節點確定分布情況下在時間200 s之后死亡節點將逐漸減少，生存節點個數維持在20個左右。而在節點非均勻分布情況下，仿真時間進行到200 s之后，生存節點個數維持在10個左右。

3.2.2 網絡平均時延

圖7為EBRABOE的網絡時延測試結果。

從圖7中可以看出，平均端到端的延遲在節點數量較小時，兩者時延相當并且隨著網絡節點數的增加而增加，變化沒有規律，這是因為在尋找下一跳到達目的節點時，數據包必須在接口隊列中等待一段時間。但總體上，節點非均勻分布時比節點確定分布時，時延大。這是因為當路由表建立后，隨著節點的移動和節點數的增加，需要更新路由表次數頻繁，影響數據包傳送的時間。

3.2.3 節點平均能耗

在兩種條件下進行節點平均能耗的仿真。相同仿真時間內，消耗能量總量與節點數目之比；相同節點數目內，消耗能量總量與仿真時間之比。

圖8和圖9為EBRABOE節點平均能耗測試結果。

由圖8可知，當節點非均勻分布時消耗的能量大于節點均勻分布時消耗的能量。這是因為當節點確定分布時，各鄰居節點的地理位置已知，在一定程度上避免了路由環路的發生，選擇下一跳時只需要考慮能耗，并且節點能夠快速找到Sink節點，增加了算法的收斂速度，所以節點平均能量消耗較少。而當節點非均勻分布時，需要考慮路徑因素及能量損耗，導致了算法的收斂速度減慢，加大了節點能量的消耗。

從圖9可以看出，當時間小于70 s左右時，節點確定分布情況下的平均能量消耗大于節點隨機分布情況下的平均能耗。因為節點確定分布時，每個節點都獲悉其他節點的位置即保存著相應節點的鄰居表，在開始階段收發節點報文的開銷比節點隨機分布要大，但隨著時間的進行，仿真時間大于80 s之后，節點隨機分布情況下的平均能耗增長速度明顯大于節點確定分布情況下。因為在尋路過程中，節點不能有效地預防路由環路的發生，當確定下一跳時，訪問一個已經訪問過的節點，節點就丟棄它，相比節點確定分布，算法的收斂速度較慢，尋路過程較復雜，加大了節點能量的消耗。

4 結 論

根據淺水環境中的水下無線傳感器網絡的特征，本文深入研究了淺水環境下無線傳感器節點通信模型的建立和能量消耗均衡性的問題，提出了一種基于熵的能量均衡路由算法EBRABOE，權衡考慮節點的剩余能量和位置信息來選擇下一跳節點，從而平衡網絡能耗，達到延長網絡生存周期的目的。本文利用NS?2仿真平臺對EBRABOE的性能進行了仿真分析，結果表明，EBRABOE在網絡生存時間、網絡平均時延及能量消耗等參數方面，表現出了良好的性能。本文研究對于水下傳感器網絡的應用具有一定的參考價值。

參考文獻

[1] 張劍，黃本雄，張帆.一種適合水下無線傳感器網絡的能量有效協議[J].計算機科學，2008，35（1）：38?41.

[2] 蔣鵬，阮斌鋒，譚劼.全覆蓋需求的水下傳感器網絡覆蓋保持算法[J].傳感技術學報，2012，25（11）：1591?1598.

[3] 張亞斌，劉建明，李宏周，等.基于NS?2的水聲通信信道的擴展與仿真[J].計算機仿真，2012，29（7）：163?167.

[4] 劉華峰，陳果娃，金士堯.三維水下監視傳感器網絡的拓撲生成算法[J].計算機工程與應用，2008，44（2）：163?168.

[5] 康文靜，劉功亮，李亞星.基于深度和距離感知的三維水下傳感器網絡路由算法[J].科學技術與工程，2011（35）：8780?8784.

[6] 曾斌，鐘德歡，姚路.考慮水流影響的水下傳感器網絡移動算法研究[J].計算機應用研究，2010，27（10）：3926?3928.

[7] 劉湘雯，薛峰，李彥，等.一種分布式無線傳感器網絡能量均衡路由算法[J].計算機科學，2010，37（1）：122?125.

[8] 周雪，朱小明，陳立建，等.基于停車誘導系統的能量均衡可靠路由協議的設計[J].傳感技術學報，2015，28（9）：1408?1417.

[9] 黃艷，梁韡，于海斌.一種高效覆蓋的水下傳感器網絡部署策略[J].電子與信息學報，2009，31（5）：1035?1039.

[10] 趙文強，胡濱，康文靜，等.可調分辨率的水下傳感器網絡壓縮感知重構算法[J].傳感技術學報，2015，28（5）：723?728.