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

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

關(guān)鍵詞： 淺水環(huán)境； 熵； 能量均衡； 路由算法； 路由優(yōu)化

中圖分類號： 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

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

1 水下傳感器網(wǎng)絡(luò)通信模型

1.1 布爾感知模型

三維空間的無線傳感器網(wǎng)絡(luò)節(jié)點采用布爾感知模型[3]。

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

1.2 現(xiàn)有模型的比較

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

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

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

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

1.3 無空洞覆蓋

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

1.4 能耗模型

Pd表示數(shù)據(jù)包被接收的最低功率值，d表示數(shù)據(jù)包的傳輸距離，則節(jié)點的發(fā)送能耗Esend（d）可以表示為：

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

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

[Eattenuationd=dλad] （2）

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

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

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

2 算法思想與實現(xiàn)

2.1 算法思想

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

2.2 熵的定義

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

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

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

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

經(jīng)過第一次接收數(shù)據(jù)和發(fā)送數(shù)據(jù)，a節(jié)點的相關(guān)特征數(shù)值表示為：

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

式中：[posa，x，y，z]表示節(jié)點的位置；[Econsumea，r]表示節(jié)點接收數(shù)據(jù)消耗的能量；[Econsumea，s]表示節(jié)點發(fā)送數(shù)據(jù)消耗的能量。

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

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

式中：d0為節(jié)點到Sink節(jié)點的距離；ε為無線信號傳播參數(shù)。同理，b節(jié)點的相關(guān)特征數(shù)值表示為：

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

[Econsumeb，r=Econsumea，r]時發(fā)送數(shù)據(jù)耗能公式為：

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

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

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

式中，i表示節(jié)點，i[∈1，2，…，n]，n表示節(jié)點個數(shù)。

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

2.3 算法實現(xiàn)過程

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

（1） 網(wǎng)絡(luò)初始化。在此階段，形成虛擬單元格，每個虛擬單元格根據(jù)所處位置有一個標號，方便數(shù)據(jù)傳輸，同時每個虛擬單元格內(nèi)（即一個簇內(nèi)）的節(jié)點都要有一個簇內(nèi)惟一的ID。如圖2所示。

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

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

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

每個節(jié)點消耗的能量有兩方面：與n-1個節(jié)點進行數(shù)據(jù)收發(fā)消耗的能量；與Sink節(jié)點通信消耗的能量。

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

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

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

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

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

如果節(jié)點A發(fā)送數(shù)據(jù)給C，選擇節(jié)點B作為下一跳的條件是當且僅當：

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

成立時，節(jié)點A選擇節(jié)點B作為下一跳將數(shù)據(jù)轉(zhuǎn)發(fā)給C。其中DA?C，DA?B，DB?C分別表示節(jié)點A與C、節(jié)點A與B、節(jié)點B與C之間的距離。

（4） 數(shù)據(jù)按照建好的路由結(jié)構(gòu)傳輸給BS。源節(jié)點在選擇好下一跳路由后發(fā)送采集得到的有用信息然后該轉(zhuǎn)發(fā)節(jié)點變成源節(jié)點，繼續(xù)尋找選擇最優(yōu)下一跳節(jié)點。

3 算法仿真和性能分析

3.1 仿真場景及參數(shù)

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

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

表3 仿真環(huán)境參數(shù)設(shè)置

3.2 性能測試和分析

在前面工作基礎(chǔ)上，分別對節(jié)點網(wǎng)絡(luò)生存時間、網(wǎng)絡(luò)平均時延和節(jié)點平均能耗進行了仿真。

3.2.1 網(wǎng)絡(luò)生存時間

在兩種條件下進行網(wǎng)絡(luò)生存時間的仿真分析： 網(wǎng)絡(luò)中第一個節(jié)點死亡的時間；網(wǎng)絡(luò)中生存節(jié)點個數(shù)。

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

當網(wǎng)絡(luò)規(guī)模小于30個節(jié)點時，網(wǎng)絡(luò)壽命將提高。這是因為隨著網(wǎng)絡(luò)規(guī)模的變大，廣播Hello包的數(shù)量也隨之增加，節(jié)點找到一條從源節(jié)點到Sink節(jié)點的最優(yōu)路徑時間變長，算法收斂速度變小，導(dǎo)致能耗也因此增加。

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

3.2.2 網(wǎng)絡(luò)平均時延

圖7為EBRABOE的網(wǎng)絡(luò)時延測試結(jié)果。

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

3.2.3 節(jié)點平均能耗

在兩種條件下進行節(jié)點平均能耗的仿真。相同仿真時間內(nèi)，消耗能量總量與節(jié)點數(shù)目之比；相同節(jié)點數(shù)目內(nèi)，消耗能量總量與仿真時間之比。

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

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

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

4 結(jié) 論

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

參考文獻

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

[2] 蔣鵬，阮斌鋒，譚劼.全覆蓋需求的水下傳感器網(wǎng)絡(luò)覆蓋保持算法[J].傳感技術(shù)學(xué)報，2012，25（11）：1591?1598.

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

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

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

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

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

[8] 周雪，朱小明，陳立建，等.基于停車誘導(dǎo)系統(tǒng)的能量均衡可靠路由協(xié)議的設(shè)計[J].傳感技術(shù)學(xué)報，2015，28（9）：1408?1417.

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

[10] 趙文強，胡濱，康文靜，等.可調(diào)分辨率的水下傳感器網(wǎng)絡(luò)壓縮感知重構(gòu)算法[J].傳感技術(shù)學(xué)報，2015，28（5）：723?728.