一種改進(jìn)型PEGASIS 算法在水聲通信組網(wǎng)中的應(yīng)用

王文琮，石建飛，張學(xué)磊，田甜

(中國電子科技集團(tuán)公司第三研究所，北京 100015)

0 引 言

隨著近年來人類對海洋的深入探索，水聲領(lǐng)域也得到了飛速發(fā)展，水聲通信作為水聲學(xué)研究的重點(diǎn)課題之一，也越來越受到關(guān)注。以往水聲通信領(lǐng)域主要關(guān)注的是調(diào)制方式和編碼方式，但是隨著越來越多的水聲傳感器設(shè)備的投放，設(shè)備間的組網(wǎng)也成為了重要的研究方向。

特別是近十年來，水聲組網(wǎng)的技術(shù)呈現(xiàn)了很多新的趨勢，尤其是在多設(shè)備融合方面，水聲通信結(jié)合了無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）中的成熟算法，產(chǎn)生出很多基于WSN 的水聲通信組網(wǎng)方式。

WSN 是一種把傳感器節(jié)點(diǎn)部署在監(jiān)控區(qū)域內(nèi)，起到監(jiān)控區(qū)域目的的無線組網(wǎng)方式。WSN 內(nèi)部一般根據(jù)數(shù)據(jù)傳輸方向分為節(jié)點(diǎn)，匯聚節(jié)點(diǎn)（又稱為簇頭）以及客戶端，節(jié)點(diǎn)負(fù)責(zé)采集數(shù)據(jù)，匯聚節(jié)點(diǎn)負(fù)責(zé)匯總各節(jié)點(diǎn)采集到的數(shù)據(jù)融合，發(fā)送給客戶端，這種數(shù)據(jù)傳輸過程也稱為分簇過程，分簇示意如圖1 所示。

圖1 分簇路由示意圖Fig.1 Schematic diagram of cluster routing

將WSN 結(jié)合到水聲通信領(lǐng)域，當(dāng)需要監(jiān)測一片水域的聲場情況的時候，通常需要將多個水聲換能器布防在此海域，換能器之間通過多跳路由的方式將信息匯總到匯聚節(jié)點(diǎn)，以供研究使用。但是在傳統(tǒng)的多跳路由組網(wǎng)過程中需考慮以下2 個問題：1）當(dāng)數(shù)據(jù)從最遠(yuǎn)節(jié)點(diǎn)傳遞至匯聚節(jié)點(diǎn)的時候，存在一定的延時，中間節(jié)點(diǎn)個數(shù)越多，延時時間越長，匯聚節(jié)點(diǎn)收到信息不實(shí)時；2）單個節(jié)點(diǎn)所攜帶電量有限，且主要消耗電量的是發(fā)射換能器，發(fā)射換能器工作次數(shù)應(yīng)越少越好。這些問題對新型的通信網(wǎng)絡(luò)協(xié)議提出了要求。

1 經(jīng)典拓?fù)浣M網(wǎng)協(xié)議

1.1 LEACH 協(xié)議

LEACH 是首個分簇路由協(xié)議，其執(zhí)行過程主要分為 2 個階段，簇建立階段以及數(shù)據(jù)傳輸階段，一個完整的簇包含一個簇頭和多個簇節(jié)點(diǎn)，簇建立階段主要進(jìn)行了簇頭的選擇以及形成一個完整簇結(jié)構(gòu)，數(shù)據(jù)傳輸階段主要由簇頭接收簇節(jié)點(diǎn)發(fā)來的信息，簇頭對信息進(jìn)行融合然后再將信息發(fā)送至客戶端。由于簇頭既要融合數(shù)據(jù)，還需要將數(shù)據(jù)發(fā)送出去，所以簇頭的功耗最大，因此簇頭的選擇是 LEACH 協(xié)議的重點(diǎn)。LEACH 協(xié)議為了解決功耗問題，采用了隨機(jī)閾值算法，即隨機(jī)的根據(jù)節(jié)點(diǎn)產(chǎn)生的數(shù)值與閾值相比較，當(dāng)大于閾值時，此節(jié)點(diǎn)成為簇頭，成為簇頭的節(jié)點(diǎn)在之后的幾次傳輸過程中成為簇頭的概率會很低，整個網(wǎng)絡(luò)各個節(jié)點(diǎn)消耗能量較為均衡，不會出現(xiàn)簇頭頻繁死亡的情況，但是LEACH 由于本身的機(jī)制，會出現(xiàn)2 個問題：1）網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較大時，成為簇頭的節(jié)點(diǎn)有可能頻繁成為簇頭；2）由于簇頭的頻繁更換，所以每次簇頭需要通知到簇中子節(jié)點(diǎn)所在的簇，建簇過程功耗較大。

利用 Matlab 軟件在 100×100 的區(qū)域內(nèi)隨機(jī)產(chǎn)生 12個節(jié)點(diǎn)，中心位置為客戶端位置，將節(jié)點(diǎn)劃分為4 部分，每個部分都有 1 個匯聚節(jié)點(diǎn)和 2 個子節(jié)點(diǎn)，按照LEACH 協(xié)議進(jìn)行數(shù)據(jù)的傳遞，網(wǎng)絡(luò)拓?fù)鋱D如圖2 所示。

圖2 LEACH 網(wǎng)絡(luò)拓?fù)鋱DFig.2 LEACH network topology diagram

1.2 PEGASIS 協(xié)議

PEGASIS 作為分簇路由的重要組成部分，同樣分為2 個過程：建鏈過程和穩(wěn)定過程。建鏈過程中，各簇節(jié)點(diǎn)向簇頭發(fā)送信號，接收簇頭反饋的確認(rèn)信號，根據(jù)通信指令判斷簇頭與各個簇節(jié)點(diǎn)的距離，找出與簇頭最遠(yuǎn)距離的簇節(jié)點(diǎn)，然后節(jié)點(diǎn)向其他簇節(jié)點(diǎn)發(fā)送信號，根據(jù)反饋信號確定與距離最近的簇節(jié)點(diǎn)，節(jié)點(diǎn)遍歷此過程，最終建立簇鏈;穩(wěn)定過程即數(shù)據(jù)傳輸融合過程，簇鏈中按照距離簇頭由遠(yuǎn)到近以此將信息傳遞至下一個簇節(jié)點(diǎn)，直到所有信息匯聚到簇頭為止。PEGASIS 采用的是典型的貪心算法，即只匹配此簇鏈中的最優(yōu)解，但是對于多設(shè)備組網(wǎng)會出現(xiàn)如下問題：1）由于形成鏈過程隨機(jī)，當(dāng)鏈過長時，單個鏈功耗會很大，且時延較長，無法提高網(wǎng)絡(luò)消耗的均衡性；2）網(wǎng)絡(luò)中簇鏈之間由于節(jié)點(diǎn)數(shù)不一致，會導(dǎo)致客戶端融合數(shù)據(jù)發(fā)生困難；3）局部均衡并不意味著整體均衡，有時不能滿足最優(yōu)解。

按照PEGASIS 協(xié)議產(chǎn)生的拓?fù)浣Y(jié)構(gòu)如圖3 所示。

圖3 PEGASIS 網(wǎng)絡(luò)拓?fù)鋱DFig.3 PEGASIS network topology diagram

2 改進(jìn)型PEGASIS 算法在水聲通信組網(wǎng)中運(yùn)用

根據(jù)水文環(huán)境不同，水聲傳感器需要根據(jù)水文環(huán)境大小調(diào)節(jié)聲壓級，當(dāng)水聲信道環(huán)境較為復(fù)雜時，聲壓級需要變大，相反時，聲壓級需要調(diào)小。同時，水聲傳播損失與距離的公式（柱面波），也說明傳播損失與距離成正相關(guān)的關(guān)系。

遠(yuǎn)程的浮潛標(biāo)由于自帶電池能量有限，多個浮潛標(biāo)組網(wǎng)后為了能工作的時間更長，需要設(shè)計網(wǎng)路使聲傳播距離最近，傳播損耗更低。根據(jù)PEGASIS 組網(wǎng)協(xié)議提出了一種改進(jìn)型的PEGASIS 組網(wǎng)協(xié)議，這種協(xié)議與傳統(tǒng)PEGASIS 最大的區(qū)別是每個簇頭需要根據(jù)之前的同步消息比較下一個節(jié)點(diǎn)到自己的距離與到客戶端的距離大小，當(dāng)下一個節(jié)點(diǎn)到簇頭距離較近時，將信息傳遞至簇頭；當(dāng)節(jié)點(diǎn)距離客戶端距離近時，將信息傳遞至客戶端。將每一個節(jié)點(diǎn)（,...）距客戶端（記為）距離記為To_List，之后按照以下步驟完成：

計算出Max（To_List）的節(jié)點(diǎn)，記為；

將距離最近的節(jié)點(diǎn)記為；

，間距記為__，鏈接路徑記為，利用如下算法：

之后將節(jié)點(diǎn)設(shè)置為，重復(fù)3 個步驟。

改進(jìn)型PEGASIS 組網(wǎng)協(xié)議流程圖如圖4 所示。

圖4 改進(jìn)型PEGASIS 組網(wǎng)協(xié)議流程圖Fig.4 Improved PEGASIS networking flowchart

12 個節(jié)點(diǎn)按照改進(jìn)型的PEGASIS 協(xié)議產(chǎn)生的拓?fù)浣Y(jié)構(gòu)如圖5 所示。

圖5 改進(jìn)型 PEGASIS 網(wǎng)絡(luò)拓?fù)鋱DFig.5 Improved PEGASIS topology diagram

3 組網(wǎng)方式的比較

針對構(gòu)建的12 個節(jié)點(diǎn)模型對LEACH，PEGASIS 以及改進(jìn)型的PEGASIS 的3 個組網(wǎng)協(xié)議傳播損失對比圖以及數(shù)據(jù)同步一個周期內(nèi)鏈路通信次數(shù)排序進(jìn)行Matlab 仿真，結(jié)果如圖6 和圖7 所示。可以看出，此次模型中，改進(jìn)型的PEGASIS 協(xié)議與典型的PEGASIS 協(xié)議只有在二象限4-5-6 節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)有不同，改進(jìn)型的PEGASIS 傳播損失更低（此模型中相較于PEGASIS 傳播損失降低5%），且需要的周期更短（4-5-6 節(jié)點(diǎn)只需要2 個周期），可以縮短網(wǎng)絡(luò)延時，綜合單鏈功耗降低以及周期更短的特性，改進(jìn)型PEGASIS 協(xié)議實(shí)際傳輸中能耗可降低20%以上。

圖6 傳播損失對比圖Fig.6 Transmission loss comparison chart

圖7 周期對比圖Fig.7 Cycle comparison chart

4 結(jié) 語

根據(jù)仿真結(jié)果，改進(jìn)型的 PEGASIS 組網(wǎng)效率更高，尤其在解決傳統(tǒng) PEGASIS 組網(wǎng)中出現(xiàn)的鏈過長，傳輸能效低，傳輸時間長的問題時，效果較為良好，改進(jìn)型的 PEAGASIS 可以優(yōu)化傳輸中的數(shù)據(jù)鏈，減少單鏈的節(jié)點(diǎn)數(shù)，在傳輸效能上大大提高，可以廣泛應(yīng)用于水聲傳感器組網(wǎng)。