孫宇晶

（沈陽化工大學(xué)，遼寧 沈陽 110000）

0 引 言

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

1 系統(tǒng)模型

1.1 節(jié)點(diǎn)感知模型

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

圖1 0-1感知模型

1.2 網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

Katti等人分析研究了水下無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如正方形網(wǎng)絡(luò)結(jié)構(gòu)、三角形網(wǎng)絡(luò)結(jié)構(gòu)以及六邊形網(wǎng)絡(luò)結(jié)構(gòu)相對應(yīng)部署方式的覆蓋度和所需傳感器節(jié)點(diǎn)個(gè)數(shù)。結(jié)果顯示，三角形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的覆蓋范圍更廣，但相對所需節(jié)點(diǎn)數(shù)目也更多，部署成本較高；六邊形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)所需部署的節(jié)點(diǎn)較少，但其數(shù)據(jù)傳輸不可靠；正方形傳感器部署方案在節(jié)點(diǎn)個(gè)數(shù)和覆蓋度兩方面性能較平均。本文采用的網(wǎng)絡(luò)節(jié)點(diǎn)部署優(yōu)化指標(biāo)為覆蓋率和傳感器節(jié)點(diǎn)數(shù)目。

2 算法設(shè)計(jì)

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

Step1：首先對傳感器網(wǎng)絡(luò)中的參數(shù)進(jìn)行初始化，其中包括網(wǎng)格數(shù)量、格點(diǎn)間距離、網(wǎng)格類型、傳感器覆蓋范圍等參數(shù)，然后對遺傳算法中涉及的相關(guān)參數(shù)進(jìn)行初始化，其中包括遺傳算法的選擇函數(shù)、變異概率和交叉方式等。

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

Step3：根據(jù)適應(yīng)度函數(shù)的大小對個(gè)體排序，選擇相應(yīng)的個(gè)體兩兩交叉，將得到的新個(gè)體放入下一代種群中，最后對該種群進(jìn)行變異操作。

Step4：檢查當(dāng)前迭代數(shù)是否達(dá)到預(yù)設(shè)的最大迭代次數(shù)，如達(dá)到，則算法終止，否則跳到Step2。

算法流程如圖2所示。

圖2 算法流程

3 仿真實(shí)驗(yàn)

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

將傳感器的覆蓋率作為適應(yīng)度函數(shù)。當(dāng)覆蓋率滿足要求時(shí)，適應(yīng)度為傳感器節(jié)點(diǎn)個(gè)數(shù)；當(dāng)覆蓋率不滿足要求時(shí)，須對適應(yīng)度函數(shù)進(jìn)行修正，適應(yīng)度=傳感器節(jié)點(diǎn)個(gè)數(shù)/覆蓋率。

目標(biāo)覆蓋率分別為92%、90%、84%、76%時(shí)，算法的優(yōu)化過程以及傳感器部署如圖3～圖6所示。

從圖3（a）可以看出，在初始的100個(gè)迭代過程中，適應(yīng)度函數(shù)降低較快，而在迭代后，最優(yōu)適應(yīng)度將不再變化。從圖3（b）傳感器部署圖可以看出，最終的傳感器部署仍存在部分冗余，這是因?yàn)槌跏挤N群數(shù)較低，增加初始種群個(gè)體數(shù)可以優(yōu)化最終結(jié)果，但是計(jì)算時(shí)間將呈指數(shù)級增加。

圖3 覆蓋率為92%時(shí)算法的迭代優(yōu)化過程及傳感器部署位置

圖4 覆蓋率為90%時(shí)算法的迭代優(yōu)化過程及傳感器部署位置

圖5 覆蓋率為84%時(shí)算法的迭代優(yōu)化過程及傳感器部署位置

圖6 覆蓋率為76%時(shí)算法的迭代優(yōu)化過程及傳感器部署位置

4 結(jié) 語

從上述結(jié)果可以看出，本文設(shè)計(jì)的遺傳算法具有快速收斂的特性，可以降低計(jì)算量和計(jì)算時(shí)間。當(dāng)單個(gè)傳感器的覆蓋半徑減少時(shí)，要保持覆蓋率不變則需要增加傳感器個(gè)數(shù)。當(dāng)傳感器的覆蓋半徑略大于網(wǎng)格點(diǎn)距離時(shí)（r＞d），傳感器的利用效率較高。當(dāng)傳感器的覆蓋半徑變?yōu)閐＜r＜2d時(shí)，傳感器數(shù)量減少不明顯，但網(wǎng)絡(luò)覆蓋范圍會隨r的增加而增大。