水下無線傳感器網絡節點部署優化研究

孫宇晶

（沈陽化工大學，遼寧 沈陽 110000）

0 引 言

水下無線傳感器網絡（Underwater Wireless Sensor Network, UWSN）通常由規定的水下環境區域內一種或多種不同類型的傳感器節點構成，這些不同種類的傳感器節點一般會利用自身移動或人工的方式部署，最后實現特定的組網模式，并對該規定區域內的信息進行采集、收集和整理[1-2]。相較于陸地上的通信環境，水下環境較為復雜，其數據傳輸可靠性差，通常為了保證節點數據信息的成功傳輸，往往需要重發數據，此舉使節點能量消耗過快，不僅提高了節點的部署成本，也會導致網絡的連通率下降。因此在水下無線傳感器網絡的覆蓋控制問題中，節點的部署至關重要。傳感器節點部署將直接影響到節點能耗問題以及監測信息的準確性[3]。許多學者針對水下節點部署問題展開了研究，文獻[4]針對節點的隨機部署方式結合泰森多邊形和狄洛尼三角法提出了基于深度調節的水下無線傳感器網絡節點部署方案，實現了大覆蓋率及連通率，延長了網絡生命周期；文獻[5]主要針對移動受限節點部署方式產生的問題，提出了基于不均勻分簇半徑可調的自部署算法，該算法不僅提高了網絡性能，更提高了網絡覆蓋率。文獻[6]研究了深度調節機制下的水下無線傳感器節點部署優化算法，采用確定性感知模型，以沃羅諾伊多邊形面積實現對目標區域的分層覆蓋，以保證覆蓋率；文獻[7]融合智能魚群算法提出了一種基于黏性流體算法的節點部署優化策略，該算法有效提升了覆蓋度和均勻度。Yuanming Ding等人提出了基于移動節點部署的UWSNs雙覆蓋算法，該算法不僅保證了覆蓋率并且減少了節點的能量消耗[8]。通過相關文獻可知，優化水下無線傳感器網絡節點部署問題一般分為2個方向，即在不影響網絡性能的前提下減少節點數量或是在節點數目固定的情況下優化網絡結構，使得網絡性能達到最優。

1 系統模型

1.1 節點感知模型

節點感知模型分為確定性感知模型、概率性感知模型，一般用于表達節點感知周圍環境的能力。不同場景需要用到不同的感知模型。本文研究的環境為復雜的水下，因此采用確定性感知模型中的0-1感知模型。在二維平面中，0-1感知模型的感知范圍為一個圓盤區域，假設一個節點作為其圓心，節點的感知半徑為R，處于圓之外范圍的節點皆無法被感知。0-1感知模型如圖1所示。

圖1 0-1感知模型

1.2 網絡拓撲模型

Katti等人分析研究了水下無線傳感器網絡拓撲結構，如正方形網絡結構、三角形網絡結構以及六邊形網絡結構相對應部署方式的覆蓋度和所需傳感器節點個數。結果顯示，三角形網絡拓撲結構的覆蓋范圍更廣，但相對所需節點數目也更多，部署成本較高；六邊形網絡拓撲結構所需部署的節點較少，但其數據傳輸不可靠；正方形傳感器部署方案在節點個數和覆蓋度兩方面性能較平均。本文采用的網絡節點部署優化指標為覆蓋率和傳感器節點數目。

2 算法設計

利用遺傳算法求解上述優化問題的搜索空間為2N×N，其中N×N為網格點的數量，這是一個NP難題[9]。針對這一問題，我們可以利用遺傳算法進行求解。本文中的傳感器部署模型為0-1模型，非常適合使用二進制編碼。在求解過程中，分別以網絡節點數和覆蓋率作為適應度函數對該問題進行求解，具體求解流程如下。

Step1：首先對傳感器網絡中的參數進行初始化，其中包括網格數量、格點間距離、網格類型、傳感器覆蓋范圍等參數，然后對遺傳算法中涉及的相關參數進行初始化，其中包括遺傳算法的選擇函數、變異概率和交叉方式等。

Step2：計算種群中個體的適應度函數，并計算個體是否滿足覆蓋率和傳感器個數等條件，符合要求的個體，其適應度函數保持不變；不符合要求的個體，其適應度函數需要進行相應的修正。

Step3：根據適應度函數的大小對個體排序，選擇相應的個體兩兩交叉，將得到的新個體放入下一代種群中，最后對該種群進行變異操作。

Step4：檢查當前迭代數是否達到預設的最大迭代次數，如達到，則算法終止，否則跳到Step2。

算法流程如圖2所示。

圖2 算法流程

3 仿真實驗

為驗證本文所提算法的可行性，采用MATLAB a2015版本的軟件進行仿真。在覆蓋率給定時，需部署的傳感器節點數量可利用遺傳算法優化。假定水下二維目標水域的面積為90 m×90 m，把該區域劃分為10×10的網格，需覆蓋的目標位置在網格點上。假定該傳感器網絡在部署后需滿足的覆蓋率要求分別為90%、85%、80%和75%，將傳感器部署在三角形劃分的網格點上，其覆蓋半徑為12 m。設置初始種群為50，算法的最大迭代次數為200次。通過錦標賽法選擇算子，交叉算子為兩點交叉，變異算子的變異概率為50%。對個體進行隨機初始化，0表示該位置未部署傳感器，1表示該位置部署傳感器，單個個體為10×10的0-1傳感器部署矩陣。

將傳感器的覆蓋率作為適應度函數。當覆蓋率滿足要求時，適應度為傳感器節點個數；當覆蓋率不滿足要求時，須對適應度函數進行修正，適應度=傳感器節點個數/覆蓋率。

目標覆蓋率分別為92%、90%、84%、76%時，算法的優化過程以及傳感器部署如圖3～圖6所示。

從圖3（a）可以看出，在初始的100個迭代過程中，適應度函數降低較快，而在迭代后，最優適應度將不再變化。從圖3（b）傳感器部署圖可以看出，最終的傳感器部署仍存在部分冗余，這是因為初始種群數較低，增加初始種群個體數可以優化最終結果，但是計算時間將呈指數級增加。

圖3 覆蓋率為92%時算法的迭代優化過程及傳感器部署位置

圖4 覆蓋率為90%時算法的迭代優化過程及傳感器部署位置

圖5 覆蓋率為84%時算法的迭代優化過程及傳感器部署位置

圖6 覆蓋率為76%時算法的迭代優化過程及傳感器部署位置

4 結 語

從上述結果可以看出，本文設計的遺傳算法具有快速收斂的特性，可以降低計算量和計算時間。當單個傳感器的覆蓋半徑減少時，要保持覆蓋率不變則需要增加傳感器個數。當傳感器的覆蓋半徑略大于網格點距離時（r＞d），傳感器的利用效率較高。當傳感器的覆蓋半徑變為d＜r＜2d時，傳感器數量減少不明顯，但網絡覆蓋范圍會隨r的增加而增大。