劉廣鐘，耿 偉

(上海海事大學(xué) 信息工程學(xué)院，上海201306)

水聲傳感器網(wǎng)絡(luò) (Underwater Acoustic Sensor Networks)是水聲通信技術(shù)與無線傳感器網(wǎng)絡(luò)結(jié)合所產(chǎn)生的一個(gè)新的研究領(lǐng)域，經(jīng)常應(yīng)用于對(duì)固定海域的長期監(jiān)測(cè)。這種網(wǎng)絡(luò)一旦部署完畢，就需要在水下長期工作，而且，在此期間一般不會(huì)更換節(jié)點(diǎn)電池，因此延長網(wǎng)絡(luò)生命期成為水聲傳感器網(wǎng)絡(luò)的一個(gè)熱點(diǎn)問題。在路由協(xié)議中，合理地選擇路由對(duì)提高節(jié)點(diǎn)的能量效率、延長網(wǎng)絡(luò)生命期十分重要[1]。LEACH協(xié)議分簇概念被引入之后，使得網(wǎng)絡(luò)在節(jié)能以及網(wǎng)絡(luò)壽命方面得到了很大提高，然而LEACH協(xié)議在水聲傳感器網(wǎng)絡(luò)中的應(yīng)用也有其自身不可忽略的局限性[2]。本文在LEACH算法的基礎(chǔ)上介紹了一種改進(jìn)的路由算法PBCP(Position-based Clustering Protocol)，該算法在簇首選舉過程中充分考慮節(jié)點(diǎn)的能量因素，避免剩余能量較低的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。

1 LEACH協(xié)議及性能分析

1.1 LEACH算法描述

LEACH協(xié)議的全稱是“低功耗自適應(yīng)集群分層協(xié)議”(Low Energy Adaptive Clustering Hierarchy)，它采用動(dòng)態(tài)分簇技術(shù)，使網(wǎng)絡(luò)中的所有節(jié)點(diǎn)輪換充當(dāng)簇首，以均衡網(wǎng)絡(luò)中的能量消耗，延長整個(gè)網(wǎng)絡(luò)的生命周期。在LEACH算法中，節(jié)點(diǎn)自組織成不同的簇，每個(gè)簇只有一個(gè)簇首。所有非簇首節(jié)點(diǎn)將自己的數(shù)據(jù)發(fā)給所屬簇的簇首節(jié)點(diǎn)，為減少冗余數(shù)據(jù)的傳輸，簇首節(jié)點(diǎn)在數(shù)據(jù)融合后將數(shù)據(jù)發(fā)送給遠(yuǎn)方的Sink節(jié)點(diǎn)[3]。這樣，每個(gè)非簇首節(jié)點(diǎn)都只需要知道自己所屬簇的簇首信息即可，簇首也只需要維持很小的路由表，為了避免簇首能量消耗過快，每個(gè)節(jié)點(diǎn)須輪流擔(dān)任簇首。

因此LEACH算法的實(shí)現(xiàn)分成若干輪，每一輪又可分成簇形成階段和簇傳輸階段，而簇傳輸階段遠(yuǎn)遠(yuǎn)長于簇形成階段。在簇形成階段，每一個(gè)還沒有擔(dān)任過簇首的節(jié)點(diǎn)分別生成0～1之間的隨機(jī)數(shù)，如果生成的隨機(jī)數(shù)小于給定的閾值T(n)，則選擇為簇首。T(n)的計(jì)算方法如下：

其中，p是簇首在所有節(jié)點(diǎn)中所占的百分比，r是選舉輪數(shù)，G代表最近l/p輪中還沒有當(dāng)選過簇首的節(jié)點(diǎn)集合。

一旦節(jié)點(diǎn)被選定為簇首后，就向外發(fā)送簇首廣播信息。非簇首節(jié)點(diǎn)根據(jù)收到的簇首廣播信息的信號(hào)強(qiáng)弱決定要加入哪個(gè)簇，并向?qū)⒁尤氪氐拇厥装l(fā)送入簇請(qǐng)求。簇首在收到請(qǐng)求后將該節(jié)點(diǎn)加入自己的路由表并為每個(gè)節(jié)點(diǎn)設(shè)定一個(gè)TDMA定時(shí)消息，并且通知該簇中所有節(jié)點(diǎn)。此后的簇傳輸階段，簇內(nèi)節(jié)點(diǎn)按照該TDMA時(shí)間表與簇首進(jìn)行通信，簇首節(jié)點(diǎn)接收簇內(nèi)其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，并將這些數(shù)據(jù)進(jìn)行融合，然后發(fā)送給Sink節(jié)點(diǎn)。每隔一定時(shí)問，整個(gè)網(wǎng)絡(luò)重新進(jìn)入簇形成階段開始新一輪的簇首選舉過程。

1.2 LEACH算法的不足

LEACH協(xié)議采用層次結(jié)構(gòu)，與平面路由相比簡(jiǎn)化了路徑的選擇及路由信息的存儲(chǔ)，同時(shí)自適應(yīng)隨機(jī)選取簇首節(jié)點(diǎn)，利于實(shí)現(xiàn)全網(wǎng)負(fù)載的均衡。但是LEACH協(xié)議存在下列3個(gè)方面的問題，制約著網(wǎng)絡(luò)能量的均衡消耗。

（1）節(jié)點(diǎn)擔(dān)任簇首是嚴(yán)格的等概率選擇，能量較低的節(jié)點(diǎn)一旦成為簇首很容易耗盡能量而死亡；

（2）每一輪通信結(jié)束后都要重新執(zhí)行簇首選擇和簇內(nèi)、簇間路由的建立，導(dǎo)致了大量的能量消耗；

（3）簇首節(jié)點(diǎn)以單跳形式向基站傳送數(shù)據(jù)，不僅會(huì)導(dǎo)致距離基站較遠(yuǎn)節(jié)點(diǎn)的能量消耗過大，也不利于網(wǎng)絡(luò)的大規(guī)模擴(kuò)展。

2 改進(jìn)的算法PBCP

2.1 水聲傳感器節(jié)點(diǎn)能量模型

[4]給出了水聲傳感器節(jié)點(diǎn)數(shù)據(jù)通信的能量模型。設(shè)P0為數(shù)據(jù)包能被接收端正常接收的最低功率水平，x為數(shù)據(jù)包的傳輸距離(單跳距離)，則發(fā)送端發(fā)送數(shù)據(jù)包的最低功率可表示為：

式中，k為能量擴(kuò)展系數(shù)，此處取 k=1.5；a=10a(f)/10，a與頻率有關(guān)，由吸收系數(shù)a(f)獲得，據(jù)Thorp表達(dá)式得：

則發(fā)送l bit的數(shù)據(jù)包，傳輸距離為x時(shí)發(fā)射端能耗為：

接收端接收這個(gè)數(shù)據(jù)包的能耗為：

式中，Pr為取決于設(shè)備的常數(shù)。

由上述能量公式可知，傳感器節(jié)點(diǎn)的接收功率為一個(gè)常數(shù)，而發(fā)送功率隨著傳輸距離x的增大呈指數(shù)級(jí)增長，因此縮短節(jié)點(diǎn)間的一跳傳輸距離成為節(jié)約節(jié)點(diǎn)能耗、延長網(wǎng)絡(luò)生存時(shí)間的關(guān)鍵。

2.2 鏈路層協(xié)議

2.2.1 鏈路層協(xié)議的選擇

與陸地傳感器網(wǎng)絡(luò)不同，水聲傳感器網(wǎng)絡(luò)具有傳輸時(shí)延大、可用頻帶有限、嚴(yán)重的時(shí)變多途影響等。因此選取合理有效的鏈路層協(xié)議顯得至關(guān)重要。鏈路層協(xié)議的基本任務(wù)是為傳感器節(jié)點(diǎn)分配有限的水聲信道資源，避免沖突。

由于水聲信道為共享介質(zhì)，節(jié)點(diǎn)發(fā)送數(shù)據(jù)的過程中可能會(huì)與其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)產(chǎn)生碰撞，造成發(fā)送包被丟棄，需重傳發(fā)送的數(shù)據(jù)，導(dǎo)致碰撞節(jié)點(diǎn)發(fā)送這些數(shù)據(jù)消耗更多額外的能量，同時(shí)節(jié)點(diǎn)會(huì)接收并處理不必要的數(shù)據(jù)，然后再將其丟棄，造成節(jié)點(diǎn)的無線接收模塊和處理器模塊消耗更多的能量。因此需要考慮采用信道復(fù)用技術(shù)來合理分配水聲信道。常用的信道復(fù)用技術(shù)包括頻分多址FDMA、時(shí)分多址TDMA和碼分多址CDMA[5]。由于水聲信道的通信帶寬非常有限，通常只有幾千赫量級(jí)，基本無法使用頻分多址技術(shù)實(shí)現(xiàn)多用戶通信；而時(shí)分多址要求有時(shí)間保護(hù)間隔，且對(duì)時(shí)間同步的要求非常高，所以不適合大范圍的水聲通信；碼分多址是實(shí)現(xiàn)水下多用戶通信的可行技術(shù)選擇[6]。

碼分多址具有系統(tǒng)容量高、功耗低、抗干擾性好、抗多徑衰落、保密安全性高、擴(kuò)展性好等優(yōu)點(diǎn)[7]。碼分多址系統(tǒng)為每個(gè)用戶分配了各自特定的地址碼，利用地址碼序列的正交性和準(zhǔn)正交性來區(qū)分不同用戶，在同頻、同時(shí)的條件下，各接收機(jī)根據(jù)不同信號(hào)碼型之間的差異分離出需要的信號(hào)[8]。

基于以上因素，本文考慮采用基于時(shí)分多址和碼分多址的混合信道復(fù)用技術(shù)，即Sink節(jié)點(diǎn)采用一個(gè)彼此共知的CDMA擴(kuò)頻碼（以下簡(jiǎn)稱公共信道）與所有節(jié)點(diǎn)之間通信，每個(gè)簇內(nèi)采用唯一的CDMA擴(kuò)頻碼進(jìn)行通信，避免簇間的信道沖突。簇內(nèi)節(jié)點(diǎn)與簇首之間的通信采用時(shí)分復(fù)用技術(shù)，簇內(nèi)節(jié)點(diǎn)只在規(guī)定的時(shí)隙向簇首節(jié)點(diǎn)發(fā)送數(shù)據(jù)。簇首與Sink節(jié)點(diǎn)之間進(jìn)行多跳傳輸時(shí)每個(gè)簇首節(jié)點(diǎn)都將要傳輸?shù)臄?shù)據(jù)通過下一跳節(jié)點(diǎn)的跳頻碼字發(fā)送。

2.2.2 擴(kuò)頻地址碼的分配

由于碼分多址要求每條信道所采用的擴(kuò)頻地址碼唯一，故考慮在簇首選出后由Sink節(jié)點(diǎn)對(duì)擴(kuò)頻地址碼進(jìn)行統(tǒng)一分配。簇首節(jié)點(diǎn)在收到分配給本簇的擴(kuò)頻碼后將自身當(dāng)選簇首的消息連同自身位置信息和該擴(kuò)頻碼通過公共信道進(jìn)行廣播，為了避免多個(gè)簇首節(jié)點(diǎn)在同一時(shí)刻廣播自己的消息造成信道沖突，本文考慮采用MACA協(xié)議中的RTS/CTS握手機(jī)制[9]：每個(gè)節(jié)點(diǎn)在當(dāng)選簇首后通過公共信道向Sink節(jié)點(diǎn)發(fā)送一個(gè)RTS請(qǐng)求，Sink節(jié)點(diǎn)在收到所有的請(qǐng)求后為每個(gè)簇首節(jié)點(diǎn)分配一個(gè)唯一的CDMA擴(kuò)頻碼，并按照請(qǐng)求的順序依次給相應(yīng)簇首發(fā)送攜帶其擴(kuò)頻碼的CTS回應(yīng)，簇首節(jié)點(diǎn)在收到CTS后，使用公共信道向全網(wǎng)廣播自己當(dāng)選簇首的消息，Sink節(jié)點(diǎn)在收到這一廣播后繼續(xù)給下一個(gè)簇首節(jié)點(diǎn)發(fā)送CTS回應(yīng),直到所有的簇首節(jié)點(diǎn)都將自己的消息廣播出去。

2.3 網(wǎng)絡(luò)模型假設(shè)

(1)水聲傳感器網(wǎng)絡(luò)是同構(gòu)網(wǎng)絡(luò)，Sink節(jié)點(diǎn)沒有能量限制；

(2)本文討論的水聲無線傳感器網(wǎng)絡(luò)為二維靜態(tài)網(wǎng)絡(luò)，不考慮節(jié)點(diǎn)的移動(dòng)性；

(3)各節(jié)點(diǎn)的初始能量相等，各節(jié)點(diǎn)都有功率調(diào)節(jié)裝置，可以根據(jù)距離的遠(yuǎn)近調(diào)整發(fā)射功率；

(4)傳感器節(jié)點(diǎn)可以通過外部設(shè)施或是其他的定位機(jī)制獲得其地理位置信息；

(5)每個(gè)傳感器節(jié)點(diǎn)都有一個(gè)唯一的ID作為其在網(wǎng)絡(luò)中的標(biāo)識(shí)；

(6)網(wǎng)絡(luò)規(guī)模較小，每個(gè)傳感器節(jié)點(diǎn)的通信范圍都可以覆蓋整個(gè)網(wǎng)絡(luò)。

2.4 改進(jìn)算法的描述

2.4.1 簇首節(jié)點(diǎn)的選擇

在每一輪的信息傳遞中，所有節(jié)點(diǎn)都把自身的當(dāng)前能量值隨采集到的數(shù)據(jù)信息發(fā)送給簇首，簇首在進(jìn)行數(shù)據(jù)融合后連同自己的剩余能量信息發(fā)送給Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)在每輪通信結(jié)束后便掌握了所有節(jié)點(diǎn)的剩余能量信息。這樣Sink節(jié)點(diǎn)便可以計(jì)算出當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)的平均能量Eavg并在發(fā)出開始下一輪簇首選舉的命令中攜帶這一參數(shù)。所有節(jié)點(diǎn)在收到簇首選舉命令后將自身能量E與Eavg進(jìn)行比較，若E>Eavg，則參與簇首選舉，反之，放棄選舉簇首。簇首的選舉依據(jù)式(6)：

每個(gè)節(jié)點(diǎn)生成一個(gè)0～1之間的隨機(jī)數(shù)，如果生成的隨機(jī)數(shù)小于T(n)，則選擇為簇首。其中G為剩余能量E>Eavg的節(jié)點(diǎn)的集合。

2.4.2 簇內(nèi)、簇間路由的建立

簇首節(jié)點(diǎn)選出后，所有當(dāng)選簇首的節(jié)點(diǎn)如前文所述依次向全網(wǎng)廣播自己當(dāng)選簇首的消息，消息中包含自身的位置信息和所采用的CDMA擴(kuò)頻碼。非簇首節(jié)點(diǎn)根據(jù)收到的簇首廣播信息的信號(hào)強(qiáng)弱決定要加入哪個(gè)簇，采用該簇首的擴(kuò)頻碼向其發(fā)送入簇請(qǐng)求并結(jié)合簇首位置信息和自身位置計(jì)算與簇首間的距離以確定向簇首發(fā)送數(shù)據(jù)時(shí)的發(fā)送功率。簇首在收到請(qǐng)求后將該節(jié)點(diǎn)加入自己的路由表并為每個(gè)節(jié)點(diǎn)設(shè)定一個(gè)TDMA定時(shí)消息，并且通知該簇中所有節(jié)點(diǎn)。

每一個(gè)簇首節(jié)點(diǎn)在收到其他簇首節(jié)點(diǎn)廣播的消息后，根據(jù)其位置信息找到自己的前向簇首節(jié)點(diǎn)。判斷方法如下：

(1)簇首節(jié)點(diǎn)先計(jì)算出與Sink節(jié)點(diǎn)間的距離：

(2)計(jì)算其他簇首節(jié)點(diǎn)與Sink節(jié)點(diǎn)間的距離：

(3)選 擇 滿 足 D(sink，this)>D(sink，clusteri)的 節(jié) 點(diǎn) 并對(duì)這些節(jié)點(diǎn)分別計(jì)算：

(4)若沒有其他簇首節(jié)點(diǎn)滿足 D(sink，this)>D(sink，clusteri)，則Sink節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的下一跳。反之，從D(this，clusteri)中選出最小值 Dmin(this，cluster)，若 Dmin(this，cluster)D(sink，this)，則選取Sink節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的前向簇首。前向簇首選定后，每個(gè)簇首將下一跳的擴(kuò)頻碼作為發(fā)送數(shù)據(jù)的擴(kuò)頻碼并根據(jù)與下一跳節(jié)點(diǎn)間的距離確定發(fā)送功率。由前文的能量模型可知，這樣選擇前向簇首可以保證每一個(gè)簇首節(jié)點(diǎn)都可以以最小能耗代價(jià)將數(shù)據(jù)發(fā)送到Sink節(jié)點(diǎn)。

式(7)～式(9)中，s_x、s_y分別為 Sink節(jié)點(diǎn)的橫縱坐標(biāo)，t_x、t_y分別為當(dāng)前簇首節(jié)點(diǎn)的橫縱坐標(biāo)，c_x、c_y為其他簇首節(jié)點(diǎn)i的橫縱坐標(biāo)。

2.4.3 完成一輪通信及開始下一輪通信

簇內(nèi)、簇間路由建立完成后，Sink節(jié)點(diǎn)向全網(wǎng)發(fā)送傳輸開始指令開始一輪的數(shù)據(jù)傳輸階段。所有簇內(nèi)節(jié)點(diǎn)即按照自己的時(shí)隙在規(guī)定時(shí)間將收集到的數(shù)據(jù)連同自己的剩余能量值發(fā)送給簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合后將數(shù)據(jù)發(fā)送給自己的前向節(jié)點(diǎn)，直至所有數(shù)據(jù)都發(fā)送到Sink節(jié)點(diǎn)，一輪通信結(jié)束。開始下一輪通信。整個(gè)流程如圖1所示。

圖1 完成一輪通信后的處理流程

由于所選出的簇首節(jié)點(diǎn)能量均高于節(jié)點(diǎn)的平均能量，這樣便可以保證整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)在一定時(shí)期內(nèi)相對(duì)穩(wěn)定。在出現(xiàn)了能量過低的簇首節(jié)點(diǎn)而執(zhí)行簇內(nèi)簇首重選時(shí)，只更改了本簇內(nèi)的網(wǎng)絡(luò)結(jié)構(gòu)和上一跳簇首節(jié)點(diǎn)的路由表，分簇結(jié)構(gòu)的主體結(jié)構(gòu)并沒有改變，避免了每輪重選簇首造成的大量能耗和長時(shí)延。

3 算法的仿真分析

3.1 仿真參數(shù)

為了驗(yàn)證PBCP算法的性能,在MATLAB環(huán)境中對(duì)PBCP和LEACH協(xié)議進(jìn)行了仿真比較。網(wǎng)絡(luò)規(guī)模為一個(gè)Sink節(jié)點(diǎn)和 100個(gè)sensor節(jié)點(diǎn)，分布在20 km×20 km的區(qū)域內(nèi)。仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置

3.2 仿真結(jié)果

圖2顯示了在第一輪簇首選舉過后，整個(gè)網(wǎng)絡(luò)的簇內(nèi)、簇間路由（Sink節(jié)點(diǎn)位于仿真區(qū)域中心）。從中可以看出，每個(gè)普通節(jié)點(diǎn)都加入了距離自己最近的簇首節(jié)點(diǎn)所在的簇，簇首節(jié)點(diǎn)之間按上文所述的最小代價(jià)建立起以Sink節(jié)點(diǎn)為目的地的多跳連接。

從圖3中可以看出，PBCP協(xié)議的死亡節(jié)點(diǎn)達(dá)到一半時(shí)，LEACH協(xié)議的節(jié)點(diǎn)數(shù)已經(jīng)接近全部死亡。與應(yīng)用LEACH協(xié)議相比網(wǎng)絡(luò)生存期延長了約45%，并且大大推遲了第一個(gè)節(jié)點(diǎn)死亡的時(shí)間，仿真結(jié)果表明，應(yīng)用PBCP協(xié)議能夠有效節(jié)約節(jié)點(diǎn)能量，平衡網(wǎng)絡(luò)負(fù)載，延長網(wǎng)絡(luò)生存時(shí)間。

延長網(wǎng)絡(luò)生命期成為水聲傳感器網(wǎng)絡(luò)的一個(gè)熱點(diǎn)問題。在路由協(xié)議中，合理地選擇路由，對(duì)提高節(jié)點(diǎn)的能量效率，延長網(wǎng)絡(luò)生命期十分重要。本文在LEACH算法的基礎(chǔ)上，介紹了一種改進(jìn)的路由算法PBCP，該算法在簇首選舉過程中充分考慮節(jié)點(diǎn)的能量因素，避免剩余能量較低的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。下一步的研究包括：在簇首節(jié)點(diǎn)的選舉中綜合考慮能量位置等因素；保證簇首節(jié)點(diǎn)在地理上均勻分布；驗(yàn)證該協(xié)議在三維環(huán)境中的能耗性能；優(yōu)化執(zhí)行簇內(nèi)簇首重選、簇結(jié)構(gòu)重新建立的閾值參數(shù)等。

參考文獻(xiàn)

[1]魏昕，趙力，李霞，等.水聲通信網(wǎng)綜述[J].電路與系統(tǒng)學(xué)報(bào)，2009，14(6)：98-106.

[2]張光旭.水聲傳感器網(wǎng)絡(luò)可靠路由協(xié)議的研究[D].中國海洋大學(xué)碩士學(xué)位論文.青島：中國海洋大學(xué)，2008.

[3]邢達(dá)波.水聲傳感器網(wǎng)絡(luò)路由算法仿真研究[D].哈爾濱工程大學(xué)碩士學(xué)位論文.哈爾濱：哈爾濱工程大學(xué)，2009.

[4]SOZER E M，STOJANOVIC M，PROAKIS J G.Underwater acoustic networks[J].IEEE Journal of Oceanic Engineering，2000，25(1)：72-83.

[5]張林波，劉彤，劉國枝.水聲通信網(wǎng)路由協(xié)議比較研究[J].哈爾濱理工大學(xué)學(xué)報(bào)，2004，9(5)：39-42.

[6]AKYILDIZ，POMPILI D，MELODIA T.Underwater acoustic sensor networks：Research challenges[J].Elsevier's Journal of Ad Hoc Networks，2005，3(3)：257-279.

[7]STOJANOVIC M.On the relationship between capacity and distance in an underwater acoustic communication channel[C].ACM WUWNet.Los Angeles：[s.n.]，2006：41-47.

[8]BANEOEE S，MISRA A.Minimum energy paths for reliable communication in multi-hop wireless networks[C].Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc).Lausanne：ACM，2002.

[9]LINDSEY S，RAGHAVENDRA C，SIVALINGAM K.Data gathering in sensor networks using the energy delay metric[C].In 15th IPDPS Workshop on Issues in Wireless Networks and Mobile Computing，2001.