一種改進型PEGASIS 算法在水聲通信組網中的應用

王文琮，石建飛，張學磊，田甜

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

0 引 言

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

特別是近十年來，水聲組網的技術呈現了很多新的趨勢，尤其是在多設備融合方面，水聲通信結合了無線傳感器網絡（wireless sensor network，WSN）中的成熟算法，產生出很多基于WSN 的水聲通信組網方式。

WSN 是一種把傳感器節點部署在監控區域內，起到監控區域目的的無線組網方式。WSN 內部一般根據數據傳輸方向分為節點，匯聚節點（又稱為簇頭）以及客戶端，節點負責采集數據，匯聚節點負責匯總各節點采集到的數據融合，發送給客戶端，這種數據傳輸過程也稱為分簇過程，分簇示意如圖1 所示。

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

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

1 經典拓撲組網協議

1.1 LEACH 協議

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

利用 Matlab 軟件在 100×100 的區域內隨機產生 12個節點，中心位置為客戶端位置，將節點劃分為4 部分，每個部分都有 1 個匯聚節點和 2 個子節點，按照LEACH 協議進行數據的傳遞，網絡拓撲圖如圖2 所示。

圖2 LEACH 網絡拓撲圖Fig.2 LEACH network topology diagram

1.2 PEGASIS 協議

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

按照PEGASIS 協議產生的拓撲結構如圖3 所示。

圖3 PEGASIS 網絡拓撲圖Fig.3 PEGASIS network topology diagram

2 改進型PEGASIS 算法在水聲通信組網中運用

根據水文環境不同，水聲傳感器需要根據水文環境大小調節聲壓級，當水聲信道環境較為復雜時，聲壓級需要變大，相反時，聲壓級需要調小。同時，水聲傳播損失與距離的公式（柱面波），也說明傳播損失與距離成正相關的關系。

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

計算出Max（To_List）的節點，記為；

將距離最近的節點記為；

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

之后將節點設置為，重復3 個步驟。

改進型PEGASIS 組網協議流程圖如圖4 所示。

圖4 改進型PEGASIS 組網協議流程圖Fig.4 Improved PEGASIS networking flowchart

12 個節點按照改進型的PEGASIS 協議產生的拓撲結構如圖5 所示。

圖5 改進型 PEGASIS 網絡拓撲圖Fig.5 Improved PEGASIS topology diagram

3 組網方式的比較

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

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

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

4 結 語

根據仿真結果，改進型的 PEGASIS 組網效率更高，尤其在解決傳統 PEGASIS 組網中出現的鏈過長，傳輸能效低，傳輸時間長的問題時，效果較為良好，改進型的 PEAGASIS 可以優化傳輸中的數據鏈，減少單鏈的節點數，在傳輸效能上大大提高，可以廣泛應用于水聲傳感器組網。