摘  要： 通過(guò)分析LEACH協(xié)議的優(yōu)缺點(diǎn)，提出了一種改進(jìn)的基于位置的水聲傳感器網(wǎng)絡(luò)分簇路由協(xié)議——PBCP。該協(xié)議對(duì)LEACH的簇首選擇機(jī)制進(jìn)行了改進(jìn)，同時(shí)基于位置信息將簇首與Sink節(jié)點(diǎn)之間的通信由單跳改為多跳。仿真結(jié)果表明，與LEACH協(xié)議相比，PBCP協(xié)議能夠有效節(jié)約節(jié)點(diǎn)能量，平衡網(wǎng)絡(luò)負(fù)載，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。
關(guān)鍵詞： 水聲傳感器網(wǎng)絡(luò)；位置；分簇；路由協(xié)議

    水聲傳感器網(wǎng)絡(luò)(Underwater Acoustic Sensor Networks)是水聲通信技術(shù)與無(wú)線傳感器網(wǎng)絡(luò)結(jié)合所產(chǎn)生的一個(gè)新的研究領(lǐng)域，經(jīng)常應(yīng)用于對(duì)固定海域的長(zhǎng)期監(jiān)測(cè)。這種網(wǎng)絡(luò)一旦部署完畢，就需要在水下長(zhǎng)期工作，而且，在此期間一般不會(huì)更換節(jié)點(diǎn)電池，因此延長(zhǎng)網(wǎng)絡(luò)生命期成為水聲傳感器網(wǎng)絡(luò)的一個(gè)熱點(diǎn)問(wèn)題。在路由協(xié)議中，合理地選擇路由對(duì)提高節(jié)點(diǎn)的能量效率、延長(zhǎng)網(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)，該算法在簇首選舉過(guò)程中充分考慮節(jié)點(diǎn)的能量因素，避免剩余能量較低的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。
1 LEACH協(xié)議及性能分析
1.1 LEACH算法描述
    LEACH協(xié)議的全稱(chēng)是“低功耗自適應(yīng)集群分層協(xié)議”(Low Energy Adaptive Clustering Hierarchy)，它采用動(dòng)態(tài)分簇技術(shù)，使網(wǎng)絡(luò)中的所有節(jié)點(diǎn)輪換充當(dāng)簇首，以均衡網(wǎng)絡(luò)中的能量消耗，延長(zhǎng)整個(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)都只需要知道自己所屬簇的簇首信息即可，簇首也只需要維持很小的路由表，為了避免簇首能量消耗過(guò)快，每個(gè)節(jié)點(diǎn)須輪流擔(dān)任簇首。
    因此LEACH算法的實(shí)現(xiàn)分成若干輪，每一輪又可分成簇形成階段和簇傳輸階段，而簇傳輸階段遠(yuǎn)遠(yuǎn)長(zhǎng)于簇形成階段。在簇形成階段，每一個(gè)還沒(méi)有擔(dān)任過(guò)簇首的節(jié)點(diǎn)分別生成0～1之間的隨機(jī)數(shù)，如果生成的隨機(jī)數(shù)小于給定的閾值T(n)，則選擇為簇首。T(n)的計(jì)算方法如下：    
    
其中，p是簇首在所有節(jié)點(diǎn)中所占的百分比，r是選舉輪數(shù)，G代表最近l/p輪中還沒(méi)有當(dāng)選過(guò)簇首的節(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í)問(wèn)，整個(gè)網(wǎng)絡(luò)重新進(jìn)入簇形成階段開(kāi)始新一輪的簇首選舉過(guò)程。
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èn)題，制約著網(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)的能量消耗過(guò)大，也不利于網(wǎng)絡(luò)的大規(guī)模擴(kuò)展。

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ù)的過(guò)程中可能會(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)的無(wú)線接收模塊和處理器模塊消耗更多的能量。因此需要考慮采用信道復(fù)用技術(shù)來(lái)合理分配水聲信道。常用的信道復(fù)用技術(shù)包括頻分多址FDMA、時(shí)分多址TDMA和碼分多址CDMA[5]。由于水聲信道的通信帶寬非常有限，通常只有幾千赫量級(jí)，基本無(wú)法使用頻分多址技術(shù)實(shí)現(xiàn)多用戶(hù)通信；而時(shí)分多址要求有時(shí)間保護(hù)間隔，且對(duì)時(shí)間同步的要求非常高，所以不適合大范圍的水聲通信；碼分多址是實(shí)現(xiàn)水下多用戶(hù)通信的可行技術(shù)選擇[6]。
    碼分多址具有系統(tǒng)容量高、功耗低、抗干擾性好、抗多徑衰落、保密安全性高、擴(kuò)展性好等優(yōu)點(diǎn)[7]。碼分多址系統(tǒng)為每個(gè)用戶(hù)分配了各自特定的地址碼，利用地址碼序列的正交性和準(zhǔn)正交性來(lái)區(qū)分不同用戶(hù)，在同頻、同時(shí)的條件下，各接收機(jī)根據(jù)不同信號(hào)碼型之間的差異分離出需要的信號(hào)[8]。
    基于以上因素，本文考慮采用基于時(shí)分多址和碼分多址的混合信道復(fù)用技術(shù)，即Sink節(jié)點(diǎn)采用一個(gè)彼此共知的CDMA擴(kuò)頻碼（以下簡(jiǎn)稱(chēng)公共信道）與所有節(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ù)通過(guò)下一跳節(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ò)頻碼通過(guò)公共信道進(jìn)行廣播，為了避免多個(gè)簇首節(jié)點(diǎn)在同一時(shí)刻廣播自己的消息造成信道沖突，本文考慮采用MACA協(xié)議中的RTS/CTS握手機(jī)制[9]：每個(gè)節(jié)點(diǎn)在當(dāng)選簇首后通過(guò)公共信道向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)沒(méi)有能量限制；
    (2)本文討論的水聲無(wú)線傳感器網(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)可以通過(guò)外部設(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ā)出開(kāi)始下一輪簇首選舉的命令中攜帶這一參數(shù)。所有節(jié)點(diǎn)在收到簇首選舉命令后將自身能量E與Eavg進(jìn)行比較，若E>Eavg，則參與簇首選舉，反之，放棄選舉簇首。簇首的選舉依據(jù)式(6)：
  
 

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

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

    延長(zhǎng)網(wǎng)絡(luò)生命期成為水聲傳感器網(wǎng)絡(luò)的一個(gè)熱點(diǎn)問(wèn)題。在路由協(xié)議中，合理地選擇路由，對(duì)提高節(jié)點(diǎn)的能量效率，延長(zhǎng)網(wǎng)絡(luò)生命期十分重要。本文在LEACH算法的基礎(chǔ)上，介紹了一種改進(jìn)的路由算法PBCP，該算法在簇首選舉過(guò)程中充分考慮節(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].中國(guó)海洋大學(xué)碩士學(xué)位論文.青島：中國(guó)海洋大學(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] 張林波，劉彤，劉國(guó)枝.水聲通信網(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.