劉 昊，王 鑫，李 靜，魯旭濤

（1.中北大學(xué)信息與通信工程學(xué)院，太原 030051；2.西北機(jī)電工程研究所，陜西 咸陽 712000；3.中北大學(xué)電氣與控制工程學(xué)院，太原 030051）

0 引言

水污染問題一直是影響全球的嚴(yán)重問題［1］，直接關(guān)系到人類的健康［2］，水質(zhì)檢測(cè)是治理水面污染的第一步。水質(zhì)監(jiān)測(cè)機(jī)器人的出現(xiàn)［3］，使得水質(zhì)移動(dòng)監(jiān)測(cè)成為現(xiàn)實(shí)，其具有環(huán)境適應(yīng)能力強(qiáng)、數(shù)據(jù)傳輸快等優(yōu)勢(shì)，在環(huán)境監(jiān)測(cè)、漁業(yè)等方面有著廣泛的前景。隨著水域范圍的擴(kuò)大，諸多行業(yè)需要長期、實(shí)時(shí)獲取一個(gè)大范圍的水域內(nèi)水面的相關(guān)信息時(shí)，需要建立多組機(jī)器人編隊(duì)［4］。編隊(duì)之間要進(jìn)行實(shí)時(shí)的信息傳輸，則需要彼此建立起通信網(wǎng)絡(luò)。如何設(shè)計(jì)一個(gè)合理的通信網(wǎng)絡(luò)部署方案，是降低通信能耗、提升機(jī)器人壽命、優(yōu)化機(jī)器人通信網(wǎng)絡(luò)性能的關(guān)鍵所在，因而成為國內(nèi)外一項(xiàng)研究熱點(diǎn)。針對(duì)此類問題，Sapre S 等人將蝙蝠算法（BA）、內(nèi)部搜索算法（ISA）以及飛蛾撲火優(yōu)化算法（MFO）等自然啟發(fā)式算法，運(yùn)用到優(yōu)化網(wǎng)絡(luò)中繼節(jié)點(diǎn)的部署來實(shí)現(xiàn)網(wǎng)絡(luò)的全聯(lián)通，保證了信息傳輸?shù)目煽啃裕?］；苗春雨等人提出了面向數(shù)量最少化的雙層WSN 中繼節(jié)點(diǎn)部署算法，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目進(jìn)行了優(yōu)化［6］。但此類研究目標(biāo)比較單一，且場(chǎng)景比較理想化，僅僅進(jìn)行了理論層面的研究，缺乏在具體領(lǐng)域內(nèi)的應(yīng)用。

對(duì)此，本文考慮水面多機(jī)器人組網(wǎng)通信系統(tǒng)結(jié)構(gòu)，以真實(shí)水面為例，在以具體地理位置以及對(duì)實(shí)際環(huán)境的影響為權(quán)重的前提下，以編隊(duì)通信網(wǎng)絡(luò)全聯(lián)通以及優(yōu)化能耗為目標(biāo)，采用中繼節(jié)點(diǎn)及匯聚節(jié)點(diǎn)的多級(jí)、分層式信息傳輸方法。通過建立相關(guān)模型，并基于免疫遺傳算法設(shè)計(jì)相關(guān)優(yōu)化求解方法，來獲得節(jié)點(diǎn)的優(yōu)化部署方案。此外，為保證所述方法的先進(jìn)性，采用傳統(tǒng)的蝙蝠算法、遺傳算法進(jìn)行了對(duì)比實(shí)驗(yàn)與分析。

1 模型建立

1.1 被監(jiān)測(cè)水域模型

本文以安徽省巢湖為例［7］，考慮實(shí)際地理位置、環(huán)境條件等對(duì)節(jié)點(diǎn)部署所帶來的影響來對(duì)湖面進(jìn)行區(qū)域劃分，通過在地圖上建立直角坐標(biāo)系來獲取各個(gè)節(jié)點(diǎn)的位置。水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)在指定區(qū)域、按照規(guī)劃路徑進(jìn)行數(shù)據(jù)采集。

根據(jù)實(shí)際地理位置情況，首先將湖面劃分為A、B、C、D、E 5 個(gè)區(qū)域，在每一個(gè)區(qū)域內(nèi)部署一個(gè)信息中繼節(jié)點(diǎn)。圖中坐標(biāo)系依據(jù)地圖與實(shí)際比例建立，坐標(biāo)值與實(shí)際值比例為1∶10。即：每一刻度值之間間隔為500，其表示實(shí)際距離5 km?？紤]到每個(gè)區(qū)域面積過大，單個(gè)機(jī)器人編隊(duì)續(xù)航能力有限的情況，將5 個(gè)區(qū)域中每一個(gè)區(qū)域繼續(xù)劃分為4 個(gè)小區(qū)域，（盡量使得每一區(qū)域面積相等）區(qū)域編碼為1 到20，每一區(qū)域內(nèi)由一支水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)來工作；之后對(duì)地圖進(jìn)行柵格化劃分，結(jié)果如圖2 所示。

圖中每一柵格尺寸為62.5×62.5，換算為實(shí)際距離為625 m×625 m。理想條件下，單個(gè)水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)監(jiān)測(cè)路徑如圖2 所示。

圖2 機(jī)器人監(jiān)測(cè)路徑圖

假定機(jī)器人編隊(duì)每隔625 m 進(jìn)行一次水面數(shù)據(jù)采集，根據(jù)劃分的水域內(nèi)柵格的數(shù)量（包括對(duì)不完整的柵格進(jìn)行拼接）可以估算出在指定水域內(nèi)，機(jī)器人編隊(duì)進(jìn)行的數(shù)據(jù)采集次數(shù)n。機(jī)器人編隊(duì)對(duì)指定水域完成一輪水質(zhì)數(shù)據(jù)監(jiān)測(cè)時(shí)，才通過信息中繼節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳送監(jiān)測(cè)數(shù)據(jù)，由于所有機(jī)器人每次數(shù)據(jù)采樣指標(biāo)相同，可以認(rèn)為其每次所采集的數(shù)據(jù)包大小基本相等，其每次的數(shù)據(jù)采集量用k 表示。則20 個(gè)機(jī)器人編隊(duì)中，每一機(jī)器人編隊(duì)每次向信息中繼節(jié)點(diǎn)所發(fā)送的數(shù)據(jù)量為：

1.2 多水質(zhì)機(jī)器人編隊(duì)通信網(wǎng)絡(luò)全聯(lián)通模型

考慮到水面任務(wù)的特殊性以及水面環(huán)境的復(fù)雜性，為保證穩(wěn)定可靠的信息傳輸，提高工作效率，避免遠(yuǎn)距離兩節(jié)點(diǎn)之間采用大功率直接傳輸帶來的高能耗，水質(zhì)監(jiān)測(cè)機(jī)器人之間的通信采用多跳式通信，多臺(tái)機(jī)器人編隊(duì)組成一個(gè)無線多跳式自組織網(wǎng)絡(luò)。水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)通信網(wǎng)絡(luò)，如下頁圖3 所示。

其中，W1，W2，…，Wn為n 臺(tái)機(jī)器人組成的通信網(wǎng)絡(luò)節(jié)點(diǎn)；Wp為n 臺(tái)機(jī)器人通信節(jié)點(diǎn)所對(duì)應(yīng)的信息中繼節(jié)點(diǎn)；DA 為信息匯聚節(jié)點(diǎn)（指揮中心）；di，j表示節(jié)點(diǎn)Wi到節(jié)點(diǎn)Wj的距離（其中，i=1～（n-1），j=2～n）；di，p表示節(jié)點(diǎn)Wi（其中i= 1～n）到信息中繼節(jié)點(diǎn)Wp的距離。

圖3 水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)通信網(wǎng)絡(luò)示意圖

水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)通信流程圖如圖4 所示。

圖4 水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)通信流程圖

在整個(gè)工作過程中，每一臺(tái)水質(zhì)監(jiān)測(cè)機(jī)器人負(fù)責(zé)指區(qū)域的數(shù)據(jù)采集，并將所采集的數(shù)據(jù)傳送給距離最近且空閑的節(jié)點(diǎn)，依此類推，若某節(jié)點(diǎn)Wi距離信息中繼節(jié)點(diǎn)Wp最近，則由該節(jié)點(diǎn)傳遞信息至Wp，最后由Wp將所有節(jié)點(diǎn)所采集的數(shù)據(jù)實(shí)時(shí)傳回信息中心。

假定W=W1，W2，…，Wn為部署在水面上的一組水質(zhì)機(jī)器人。任意兩個(gè)水質(zhì)監(jiān)測(cè)機(jī)器人之間的距離可用式（3）來描述：

1.3 編隊(duì)通信網(wǎng)絡(luò)節(jié)點(diǎn)部署及傳輸能耗模型

針對(duì)水質(zhì)監(jiān)測(cè)機(jī)器人在特大面積水域工作時(shí)的遠(yuǎn)距離信息傳輸問題，采用中繼節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的多級(jí)、分層式信息傳輸方法。

首先，作出如下假設(shè)：

1）信息中繼節(jié)點(diǎn)的最大信息轉(zhuǎn)發(fā)量總可以滿足所在區(qū)域各機(jī)器人編隊(duì)的需求，并且由其所在區(qū)域的所有編隊(duì)發(fā)送的總信息量決定；

2）一個(gè)信息中繼節(jié)點(diǎn)只負(fù)責(zé)其所在水域的信息轉(zhuǎn)發(fā)；

3）考慮到實(shí)際情況，信息匯聚節(jié)點(diǎn)不能建立在水面上。

基于上述假設(shè)建立模型。目標(biāo)函數(shù)是使得每一信息中繼節(jié)點(diǎn)到所在區(qū)域的各編隊(duì)、匯聚節(jié)點(diǎn)到每一信息中繼節(jié)點(diǎn)的信息量和距離值的乘積之和最?。?/p>

N=｛1，2，…，20｝表示所有機(jī)器人編隊(duì)的集合；

Mi為備選信息中繼節(jié)點(diǎn)位置到機(jī)器人編隊(duì)i 的距離小于s 的集合，i∈N，Mi?N；wi表示機(jī)器人編隊(duì)的單次發(fā)送信息量；

dij表示機(jī)器人編隊(duì)i 到它最近的信息中繼節(jié)點(diǎn)j 的距離；

s 為信息中繼節(jié)點(diǎn)距離機(jī)器人編隊(duì)的距離上限。

在信息匯聚節(jié)點(diǎn)部署時(shí)：

N=｛1，2，…，5｝表示所有信息中繼節(jié)點(diǎn)的集合；

Mi為備選信息匯聚節(jié)點(diǎn)位置到信息中繼節(jié)點(diǎn)i的距離小于s 的集合，i∈N，Mi?N；wi表示中繼節(jié)點(diǎn)的單次發(fā)送信息量；

dij表示信息中繼節(jié)點(diǎn)i 到它最近的信息匯聚節(jié)點(diǎn)j 的距離；

Zij為0～1 變量，表示信息中繼節(jié)點(diǎn)對(duì)匯聚節(jié)點(diǎn)的需求關(guān)系，若信息中繼節(jié)點(diǎn)要向匯聚節(jié)點(diǎn)j 發(fā)送信息則Zij=1，否則Zij=0；hj為0～1 變量，hj=1，表示節(jié)點(diǎn)j 被選為信息匯聚節(jié)點(diǎn)；

s 為信息匯聚節(jié)點(diǎn)到信息中繼節(jié)點(diǎn)距離上限。

對(duì)于每一個(gè)機(jī)器人編隊(duì)完成一次指定水域數(shù)據(jù)采集時(shí)，通過中繼節(jié)點(diǎn)向匯聚節(jié)點(diǎn)完成一次信息傳輸?shù)哪芎腅a用如下公式計(jì)算［8］：

相關(guān)符號(hào)說明如表1 所示：

2 算法設(shè)計(jì)及參數(shù)設(shè)定

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

免疫遺傳算法（ImmuneGeneticAlgorithm，IGA）［9］，是將遺傳算法與免疫算法組合的一種啟發(fā)式智能算法。此算法將免疫算法中免疫算子引入遺傳算法中，避免了遺傳算法在優(yōu)化求解過程中種群的退化，以獲得全局最優(yōu)解。

本文中，將式（6）的目標(biāo)函數(shù)D 在式（7）的約束條件下的最小值作為免疫算法中的抗原，所有的備選節(jié)點(diǎn)對(duì)應(yīng)為抗體。在尋優(yōu)過程中，通過親和度函數(shù)的值來評(píng)價(jià)所求節(jié)點(diǎn)部署位置解的優(yōu)劣性。親和度函數(shù)F 設(shè)計(jì)過程如下：

首先，針對(duì)算法求得違反通信網(wǎng)絡(luò)全聯(lián)通約束

2.2 參數(shù)設(shè)定

按照1.1 對(duì)各個(gè)區(qū)域的柵格劃分思路，結(jié)合1.2所闡述的網(wǎng)絡(luò)全聯(lián)通的情況下，通過對(duì)實(shí)際區(qū)域進(jìn)行考察調(diào)研，在以環(huán)境、地理位置等因素為權(quán)重的前提下進(jìn)行綜合考量，確定節(jié)點(diǎn)部署的可行位置：在ABCDE 每個(gè)區(qū)域內(nèi)確定機(jī)器人向中繼節(jié)點(diǎn)發(fā)送信息的位置，并且在每一區(qū)域各確定3 個(gè)備選中繼節(jié)點(diǎn)，在全地圖范圍內(nèi)設(shè)立5 個(gè)備選匯聚節(jié)點(diǎn)。具體分布如圖5 所示。

圖5 候選節(jié)點(diǎn)分布圖

通過對(duì)各個(gè)區(qū)域內(nèi)柵格個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，根據(jù)式（2）獲得每一機(jī)器人編隊(duì)對(duì)指定水域完成一次監(jiān)測(cè)向中繼節(jié)點(diǎn)發(fā)送的信息量，如下頁表2 所示。

各區(qū)域的備選中繼節(jié)點(diǎn)，備選匯聚節(jié)點(diǎn)的坐標(biāo)（備用節(jié)點(diǎn)和匯聚節(jié)點(diǎn)編號(hào)按橫坐標(biāo)從左到右順序）及信息量如表3 所示。

不同類型節(jié)點(diǎn)的覆蓋半徑如表4 所示。算法參數(shù)設(shè)定如表5 所示。

2.3 仿真流程

仿真實(shí)驗(yàn)步驟如下：

1）抗原識(shí)別：通過識(shí)別目標(biāo)函數(shù)及約束條件（抗原），判斷此問題是否被處理過。若有解決記錄，則搜尋對(duì)應(yīng)記憶細(xì)胞；

2）產(chǎn)生初始抗體群：隨機(jī)產(chǎn)生N 個(gè)個(gè)體，然后從記憶庫中提取m 個(gè)個(gè)體構(gòu)成初始群體；

3）親和度評(píng)價(jià)：利用親和度評(píng)價(jià)公式，對(duì)步驟（2）中的群體中各個(gè)抗體進(jìn)行評(píng)價(jià)；

4）抑制和促進(jìn)抗體：選擇親和度高的抗體進(jìn)行記憶并存入記憶庫中；

表2 機(jī)器人編隊(duì)發(fā)送節(jié)點(diǎn)位置及信息量

表3 備選節(jié)點(diǎn)位置及信息量

表4 不同類型節(jié)點(diǎn)的覆蓋范圍

表5 算法參數(shù)設(shè)定

5）選擇算子：按照輪盤賭選擇機(jī)制進(jìn)行選擇操作；

6）交叉算子：在節(jié)點(diǎn)部署問題中，采用單點(diǎn)交叉法進(jìn)行操作；

7）變異算子：采用隨機(jī)選擇變異位進(jìn)行變異操作；

8）新種群：基于步驟4）的計(jì)算結(jié)果對(duì)抗體群體進(jìn)行選擇、交叉、變異等操作得到新的群體，之后再從記憶庫中取出新的記憶個(gè)體，共同構(gòu)成新一代群體；

9）判斷是否滿足迭代終止條件，是則輸出最優(yōu)節(jié)點(diǎn)，否則返回執(zhí)行步驟3）。

算法流程圖如圖6 所示：

圖6 IGA 算法流程圖

3 實(shí)驗(yàn)結(jié)果及數(shù)據(jù)分析

通過matlab 2016a 對(duì)上述模型按照所述步驟進(jìn)行仿真。使用IGA 算法得出的節(jié)點(diǎn)部署方案如圖7所示。

圖7 IGA 節(jié)點(diǎn)部署方案

同樣，本文利用傳統(tǒng)的遺傳算法（Genetic Algorithm，GA）［10］以及蝙蝠算法（Bat Algorithm，BA）［11］進(jìn)行了仿真對(duì)比實(shí)驗(yàn)。得出在不同方案下，最終得到的信息中繼節(jié)點(diǎn)以及信息匯聚節(jié)點(diǎn)坐標(biāo)，具體結(jié)果如表6 所示。

在不同算法所得方案下，利用式（3）求得各機(jī)器人編隊(duì)到其所在區(qū)域的中繼節(jié)點(diǎn)的距離及該中繼節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離。

求解結(jié)果如圖8、圖9 所示。

圖8 各求解方案下編隊(duì)節(jié)點(diǎn)到各區(qū)域中繼節(jié)點(diǎn)距離

由圖8、圖9 綜合表4 節(jié)點(diǎn)覆蓋范圍，可得出在本文提出的方案下，各編隊(duì)的通信節(jié)點(diǎn)均處在其所屬的中繼節(jié)點(diǎn)的覆蓋半徑內(nèi)；各區(qū)域中繼節(jié)點(diǎn)同樣也處于匯聚節(jié)點(diǎn)的覆蓋范圍內(nèi)。3 種算法求解結(jié)果均保證了整個(gè)水域內(nèi)的機(jī)器編隊(duì)通信網(wǎng)絡(luò)全聯(lián)通。

圖9 各求解方案下各區(qū)中繼節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離

在此基礎(chǔ)上，利用式（8）分別求得在3 種方案下水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)所在區(qū)域中繼節(jié)點(diǎn)向匯聚節(jié)點(diǎn)完成一次信息傳輸時(shí)的能耗。同理，可求得3種方案下水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)向所在區(qū)域中繼節(jié)點(diǎn)完成一次信息所需能耗，進(jìn)而求得不同方案下的總能耗，求解結(jié)果如圖10、圖11 所示。

圖10 各區(qū)中繼節(jié)點(diǎn)向匯聚節(jié)點(diǎn)完成一次信息發(fā)送能耗對(duì)比

圖11 不同算法方案下總能耗對(duì)比

綜合圖10、圖11 的能耗結(jié)果，可以看出，在IGA 算法的求解方案下，各區(qū)域節(jié)點(diǎn)能耗波動(dòng)最小、總能耗最小，能夠有效避免中繼節(jié)點(diǎn)因能耗差而造成網(wǎng)絡(luò)脫節(jié)。相比在BA 算法方案下，其優(yōu)化效果比較接近IGA 算法，但從圖10 中可以看出其最終完成一次信息傳輸總能耗要比IGA 算法的方案高出7 038 mW。而對(duì)于GA 算法，在C、D、E 區(qū)均取得了最優(yōu)解，但在從全局結(jié)果來看其求解方案能耗波動(dòng)比較大，總能耗與其他算法方案相比最高，很明顯其暴露出了GA 算法容易“早熟”的缺陷，求解結(jié)果陷入了局部最優(yōu)。由此可見IGA 算法相對(duì)BA 和GA 算法具有較強(qiáng)的尋優(yōu)和跳出局部最優(yōu)的能力。以上結(jié)果表明，在本文所提出的基于免疫遺傳算法的方案下，通過優(yōu)化中繼節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的部署，保證了水質(zhì)機(jī)器人編隊(duì)信息傳輸網(wǎng)絡(luò)全聯(lián)通，有效提升了水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)通信網(wǎng)絡(luò)的續(xù)航能力和存活能力，其求解結(jié)果也符合實(shí)際的問題背景。

表6 不同算法求得各區(qū)域節(jié)點(diǎn)坐標(biāo)

4 結(jié)論

本文對(duì)多水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)在大面積水域環(huán)境監(jiān)測(cè)過程中信息傳輸?shù)膯栴}，采用信息中繼節(jié)點(diǎn)、匯聚節(jié)點(diǎn)的多級(jí)、分層式信息傳輸方法，并針對(duì)節(jié)點(diǎn)部署問題，提出一種基于免疫遺傳算法的解決方案。實(shí)驗(yàn)對(duì)比結(jié)果表明：本方法在保證整個(gè)水質(zhì)監(jiān)測(cè)機(jī)器人編隊(duì)網(wǎng)絡(luò)全聯(lián)通的前提下，精確地完成了各個(gè)節(jié)點(diǎn)優(yōu)化的部署。所述方法具有實(shí)際的參考意義，特別是在解決大面積水域上組網(wǎng)通信時(shí)節(jié)點(diǎn)的部署問題方面具有較強(qiáng)的應(yīng)用價(jià)值。