唐玲艷，吳 雪，吳 喆，羅小娟

（華東理工大學(xué)信息科學(xué)與工程學(xué)院電子與通信工程系，上海200237）

群混合智能算法優(yōu)化異構(gòu)WSN的生命周期*

唐玲艷，吳 雪*，吳 喆，羅小娟

（華東理工大學(xué)信息科學(xué)與工程學(xué)院電子與通信工程系，上海200237）

為了優(yōu)化異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的生命周期，找到盡可能多的連通覆蓋子集（CCS），本文建立了以網(wǎng)絡(luò)覆蓋約束、收集約束、連通約束作為目標(biāo)評(píng)價(jià)函數(shù)的模型。針對(duì)該模型，在蟻群算法基礎(chǔ)上，引進(jìn)魚群擁擠度的概念，解決了蟻群在算法初期陷入局部收斂的問題。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)算法比一般蟻群算法具有更好的全局搜索能力和收斂速度，同時(shí)針對(duì)蟻群算法在構(gòu)建子集中存在大量冗余節(jié)點(diǎn)的問題，提出了關(guān)鍵域法（KFM）判斷各子集中冗余節(jié)點(diǎn)且利用冗余節(jié)點(diǎn)構(gòu)建新的子集，這不僅能有效提高節(jié)點(diǎn)的利用率，而且延長(zhǎng)了異構(gòu)網(wǎng)絡(luò)的生命周期。

異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)生命周期；連通覆蓋子集；蟻群算法；魚群擁擠度；關(guān)鍵域法

由于大多數(shù)傳感器設(shè)備是由不可再生的電池供電，而評(píng)估無(wú)線傳感器網(wǎng)絡(luò)的基本準(zhǔn)則是網(wǎng)絡(luò)生命周期［1］，所以如何優(yōu)化延長(zhǎng)網(wǎng)絡(luò)生命周期的研究成為了無(wú)線傳感器網(wǎng)絡(luò)的研究熱點(diǎn)和難點(diǎn)。盡管在同構(gòu)無(wú)線傳感器網(wǎng)絡(luò)［2］中存在一些方法來(lái)解決這一問題，但是在異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)［3，4］中關(guān)于這一問題的研究進(jìn)展緩慢。本文所考慮的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)是Sensor和Sink節(jié)點(diǎn)半徑、數(shù)量的異構(gòu)。針對(duì)這種異構(gòu)，現(xiàn)有延長(zhǎng)異構(gòu)網(wǎng)絡(luò)生命周期的方法，是找到多組連通覆蓋子集［5，6］（每個(gè)子集設(shè)備可以解決網(wǎng)絡(luò)覆蓋和連通性問題），其中一個(gè)子集設(shè)備工作，其余設(shè)備可以改用節(jié)能的睡眠狀態(tài)。

為了找到盡量多的連通覆蓋子集，文獻(xiàn)［7］提出了啟發(fā)式算法，所得到的連通覆蓋子集在某些標(biāo)準(zhǔn)下是最優(yōu)的，但是并不能一定保證網(wǎng)絡(luò)生命周期的優(yōu)化。文獻(xiàn)［8］提出了基于前向編碼的混合遺傳算法，該算法沒有考慮網(wǎng)絡(luò)的連通性問題。文獻(xiàn)［9］提出了貪婪算法，雖然解決了網(wǎng)絡(luò)覆蓋和連通問題，但該算法只能處理離散點(diǎn)的覆蓋問題。文獻(xiàn)［10］提出了基于蟻群優(yōu)化算法最大化異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的生命周期，它可以處理點(diǎn)覆蓋和區(qū)域覆蓋，但算法初期由于信息素影響，易陷入局部收斂，影響全局搜索能力和收斂速度，同時(shí)節(jié)點(diǎn)存在大量冗余。針對(duì)以上各算法存在的收斂速度慢和節(jié)點(diǎn)冗余等問題，本文在蟻群算法的基礎(chǔ)上，將魚群擁擠度的概念引入到蟻群算法中，同時(shí)針對(duì)子集中的冗余節(jié)點(diǎn)，本文提出了用關(guān)鍵域法去冗余的方法。仿真實(shí)驗(yàn)表明，該算法具有更好的全局搜索能力和收斂速度，同時(shí)提高了節(jié)點(diǎn)利用率并且延長(zhǎng)異構(gòu)網(wǎng)絡(luò)的生命周期。

1 連通覆蓋問題描述

在無(wú)線傳感器網(wǎng)絡(luò)中，連通與覆蓋是兩個(gè)最基本的問題。覆蓋是指利用網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)對(duì)整個(gè)目標(biāo)區(qū)域進(jìn)行監(jiān)測(cè)，從而達(dá)到信息采集的目的。連通是指網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間都能夠進(jìn)行通信，并且連通也是節(jié)點(diǎn)自組織形成網(wǎng)絡(luò)的前提。本文涉及到的連通覆蓋問題，不僅需要考慮網(wǎng)絡(luò)的感知覆蓋而且需要考慮網(wǎng)絡(luò)的連通性需求。

本文構(gòu)建的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)通過(guò)傳感器（Sensor）和收集器（Sink）的配合來(lái)解決連通覆蓋問題。傳感器監(jiān)測(cè)目標(biāo)并傳輸監(jiān)測(cè)結(jié)果給收集器。收集器轉(zhuǎn)播監(jiān)測(cè)結(jié)果到目的地。因此在解決連通覆蓋問題的過(guò)程中，需要滿足以下三個(gè)約束條件：（1）傳感器對(duì)目標(biāo)區(qū)域形成完全覆蓋；（2）所有傳感器的監(jiān)測(cè)結(jié)果都能被收集器所收集；（3）收集器組成一個(gè)無(wú)線連通網(wǎng)絡(luò)。如圖1所示，圓點(diǎn)代表Sensor，三角形代表Sink，圖1所描述的是一層連通覆蓋子集需要滿足的三個(gè)約束條件，可以看出滿足了這三個(gè)條件，就可以解決感知覆蓋和網(wǎng)絡(luò)連通性問題。

圖1 一層連通覆蓋子集示意圖

2 核心問題描述

2.1 關(guān)鍵區(qū)域集CF與優(yōu)化連通覆蓋子集上界值|CF|

在無(wú)線傳感器網(wǎng)絡(luò)中，解決連通覆蓋問題既需滿足感知覆蓋也要滿足連通性需求，而覆蓋只需要滿足感知覆蓋。因此，在部署相同節(jié)點(diǎn)數(shù)情況下，滿足連通覆蓋最優(yōu)子集的數(shù)量少于滿足感知覆蓋最優(yōu)子集的數(shù)量，即連通覆蓋最優(yōu)子集數(shù)可以趨近感知覆蓋最優(yōu)子集的數(shù)量但不會(huì)超過(guò)它，因此感知覆蓋最優(yōu)子集的數(shù)量可以作為連通覆蓋子集的上界［10，11］，這個(gè)上界值稱為優(yōu)化連通覆蓋子集（OCCS）。找到感知覆蓋子集最優(yōu)數(shù)量是一個(gè)NP問題，可以用下面的方法求解。

由于本文涉及到的變量較多，在介紹求解問題之前將本文出現(xiàn)的變量定義如表1所示。

假設(shè)在L×W區(qū)域里（目標(biāo)區(qū)域初始化網(wǎng)格點(diǎn)）部署了足夠多的傳感器節(jié)點(diǎn)SR={SR1，SR2，SR3，…，SRn}和收集器節(jié)點(diǎn)SK={SK1，SK2，SK3，…，，SKm}，當(dāng)所有傳感器節(jié)點(diǎn)部署完成后，通過(guò)分析傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域網(wǎng)格點(diǎn)覆蓋的情況，將目標(biāo)區(qū)域分為若干區(qū)域，如圖2所示5個(gè)傳感器節(jié)點(diǎn)把整個(gè)目標(biāo)區(qū)域分成15個(gè)區(qū)域，可知C1={SR1}，C2={SR2}，C3={SR1，SR2}，C4={SR4，SR5}，C5={SR1，SR5}，C6={SR2，SR4，SR5}，C7={SR1，SR2，SR5}，C8={SR1，SR3}，C9={SR3}，C10={SR1，SR3，SR5}，C11={SR2，SR5}，C12={SR3，SR5}，C13={SR2，SR4}，C14={SR5}，C15={SR4}，由文獻(xiàn)［7］可知，在目標(biāo)區(qū)域內(nèi)存在一些關(guān)鍵區(qū)域集CF，這些關(guān)鍵區(qū)域集由最少傳感器節(jié)點(diǎn)所覆蓋。由圖2可知C1，C2，C9，C14，C15五個(gè)區(qū)域都只被一個(gè)傳感器節(jié)點(diǎn)所覆蓋，因此關(guān)鍵區(qū)域集CF={C1，C2，C9，C14，C15}。文獻(xiàn)［7］中定義優(yōu)化連通覆蓋子集上界值為關(guān)鍵區(qū)域集的模，即|CF|=5，則可以找出5層連通覆蓋子集。以上述5層連通覆蓋子集為例，當(dāng)其中任意一層子集工作時(shí)，其他子集均休眠，若工作的子集生命周期耗盡，啟用休眠中的一層子集繼續(xù)工作，從而達(dá)到延長(zhǎng)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)生命周期的目的。

表1 本文變量定義描述

圖2 區(qū)域與關(guān)鍵區(qū)域示意圖

2.2 目標(biāo)評(píng)價(jià)函數(shù)

為了找到盡可能多的滿足連通覆蓋子集數(shù)，并且確保找出的子集是當(dāng)前最優(yōu)解，本文構(gòu)建的目標(biāo)評(píng)價(jià)函數(shù)是由網(wǎng)絡(luò)覆蓋約束、收集約束、連通約束組成，用它來(lái)對(duì)各子集進(jìn)行滿意程度評(píng)價(jià)。以下是目標(biāo)評(píng)價(jià)函數(shù)的具體描述。

定義一組連通覆蓋集S={S1，S2，S3，…，S|CF|}，其中Si∈SR∪SK，表示由傳感器和收集器組成的一組子集且i=1，2，3，…，|CF|。用以下三個(gè)約束標(biāo)準(zhǔn)來(lái)評(píng)價(jià)每組子集滿意程度。

覆蓋約束：Si的覆蓋率可以直接用作覆蓋約束的標(biāo)準(zhǔn)。將監(jiān)測(cè)區(qū)域初始化為網(wǎng)格，每個(gè)網(wǎng)格是否被傳感器節(jié)點(diǎn)覆蓋作為衡量標(biāo)準(zhǔn)。本文覆蓋率Fi表示覆蓋的網(wǎng)格面積與整個(gè)監(jiān)測(cè)區(qū)域面積的比例，如式（1）所示：

式中，Aj表示被覆蓋的網(wǎng)格面積，A表示監(jiān)測(cè)區(qū)域面積，Si表示第i組連通覆蓋子集，SRj表示Si中傳感器節(jié)點(diǎn)。

收集約束：實(shí)現(xiàn)對(duì)傳感器節(jié)點(diǎn)監(jiān)測(cè)信息的收集，則要求每一個(gè)傳感器節(jié)點(diǎn)都至少處于一個(gè)收集節(jié)點(diǎn)的收集半徑內(nèi)，這樣所有的監(jiān)測(cè)信息才能被成功地傳輸?shù)绞占?jié)點(diǎn)。本文在Si中的收集約束可以定義為每組子集能被收集節(jié)點(diǎn)有效收集的傳感器節(jié)點(diǎn)數(shù)與其總的傳感器節(jié)點(diǎn)數(shù)的比值，即Xi，如式（2）所示：

式中，CollectNum（SRj）表示在子集Si中，能被收集節(jié)點(diǎn)有效收集的傳感器節(jié)點(diǎn)的數(shù)量，AllNum（SRj）表示子集Si中總的傳感器節(jié)點(diǎn)數(shù)量。

連通約束：收集節(jié)點(diǎn)收集到的監(jiān)測(cè)信息能有效地傳遞到目的地，需要收集節(jié)點(diǎn)組成一個(gè)無(wú)線連通網(wǎng)絡(luò)，當(dāng)且僅當(dāng)Gi是一個(gè)連接圖?；趫D論的知識(shí)，一個(gè)圖的連通可以通過(guò)它的極大連通子圖［12］的相對(duì)尺寸Li來(lái)測(cè)量出來(lái)。連通約束標(biāo)準(zhǔn)定義公式如式（3）所示，其中Bi表示極大連通子圖中收集節(jié)點(diǎn)的數(shù)量，Si表示第i組連通覆蓋子集，AllNum（SKj）表示子集Si中總的收集節(jié)點(diǎn)數(shù)量：

上述三個(gè)標(biāo)準(zhǔn)值都在［0，1］的范圍內(nèi)。值越大表明找出的子集越優(yōu)。如果Fi=Xi=Li=1，則Si實(shí)現(xiàn)了三個(gè)約束條件并且構(gòu)建了一個(gè)連通覆蓋子集。應(yīng)用這三個(gè)標(biāo)準(zhǔn)來(lái)評(píng)估所有的S集，目標(biāo)優(yōu)化函數(shù)可以定義為如式（4）所示：

式中，w0，w1，w2，w3＞0是預(yù)定義值，是S中連通覆蓋子集數(shù)量，它隨著迭代次數(shù)的增加而增加。由式（4）可知，目標(biāo)函數(shù)由兩部分組成：第一部分總結(jié)了所有子集滿足約束條件的情況；第二部分定義了基于連通覆蓋數(shù)量的目標(biāo)值。本文提出的算法是通過(guò)螞蟻迭代尋優(yōu)構(gòu)建連通覆蓋子集，構(gòu)建過(guò)程中可以由式（4）求出該子集的目標(biāo)評(píng)價(jià)函數(shù)值，并與實(shí)驗(yàn)初始設(shè)置的目標(biāo)評(píng)價(jià)函數(shù)值進(jìn)行比較，將比較值中較大的作為下一次比較的初始值，在每一輪中直到所有螞蟻完成子集構(gòu)建，此時(shí)目標(biāo)評(píng)價(jià)函數(shù)值最大的子集即是目前最優(yōu)子集，重復(fù)上述步驟，直到完成最大迭代次數(shù)，得到全局優(yōu)化子集，從而達(dá)到尋優(yōu)目的。

3 群混合智能算法

3.1 蟻群與魚群混合算法

蟻群算法［13］是Dorigo M等學(xué)者于1991年提出的一種優(yōu)化算法，它以螞蟻的覓食行為為基礎(chǔ)，用螞蟻的行走路線表示待求解問題的可行解，不依賴于具體問題的數(shù)學(xué)描述，具有很強(qiáng)的全局優(yōu)化能力，已廣泛應(yīng)用于解決組合優(yōu)化問題中的NP完全問題。但蟻群算法本身也存在一些缺點(diǎn)，如收斂速度慢、易陷入局部最優(yōu)等問題。

魚群算法［14］于2002年首次提出，通過(guò)模擬魚群的覓食活動(dòng)來(lái)實(shí)現(xiàn)空間尋優(yōu)的一種新智能算法。它具有對(duì)初值和參數(shù)選擇不敏感、簡(jiǎn)單、易實(shí)現(xiàn)、不易陷入局部最優(yōu)等優(yōu)勢(shì)，它主要有覓食、聚群、追尾、隨機(jī)四種行為。

3.2 群混合智能算法思想

人工魚群算法和蟻群算法相融合的基本思想：在蟻群算法前期引入魚群擁擠度，初期可以避免個(gè)體過(guò)早地集結(jié)到信息素高的路徑上來(lái)，從而可避免算法出現(xiàn)早熟的現(xiàn)象，提高算法的全局尋優(yōu)能力。在算法后期，由于擁擠度逐漸減為零，完全由蟻群信息素和啟發(fā)信息來(lái)尋優(yōu)，加速全局收斂。

3.2.1 群混合智能算法構(gòu)建子集規(guī)則

該算法通過(guò)魚群擁擠度、蟻群信息素、啟發(fā)式信息的共同作用，把節(jié)點(diǎn)分配到相應(yīng)的子集中，然后找到滿足連通覆蓋的子集，這樣在每一輪迭代結(jié)束，就可以找出一條當(dāng)前最優(yōu)路徑。如圖3所示，描述是該算法尋優(yōu)路徑的結(jié)構(gòu)構(gòu)造示意圖，圖中SRj表示傳感器節(jié)點(diǎn)，SKj表示收集器節(jié)點(diǎn)，灰色線代表螞蟻的潛在路徑，黑色箭頭代表螞蟻選擇的一條較優(yōu)路徑。

圖3中（v11，v32，v23，v44，v25，v36，v17，v48，v29，v310，v111，v412）（由黑箭頭定義），代表一個(gè)連通覆蓋集S={S1，S2，S3，S4}，其中S1={SR1，SR7，SK3}，S2={SR3，SR5，SK1}，S3= {SR2，SR6，SK2}，S4={SR4，SR8，SK4}是連通覆蓋集中的4層子集。根據(jù)上述子集構(gòu)建規(guī)則，其步驟描述如下：

Step 1 首先螞蟻根據(jù)路徑上的初始信息素濃度和啟發(fā)式信息的轉(zhuǎn)移概率大小，把當(dāng)前節(jié)點(diǎn)分配到某個(gè)子集中。其中使用上述的信息素和啟發(fā)式信息的設(shè)計(jì)方法，分配一個(gè)未配置的節(jié)點(diǎn)j到一個(gè)子集Si（i=1，2，…，|CF|）的概率計(jì)算如式（5）所示：

式中，Ti（j）表示j節(jié)點(diǎn)分配到i子集中的平均信息素濃度；ηi（j）表示j節(jié)點(diǎn)被分配到i子集中啟發(fā)式信息的變化率，如果j節(jié)點(diǎn)是傳感器節(jié)點(diǎn)，則啟發(fā)式信息表示j節(jié)點(diǎn)分配到i子集中覆蓋百分比變化量；若j節(jié)點(diǎn)是收集器節(jié)點(diǎn)則啟發(fā)式信息是j節(jié)點(diǎn)分配到i子集中收集器能有效收集傳感器節(jié)點(diǎn)的變化率；TK（j）和ηK（j）分別表示j節(jié)點(diǎn)分配到任意子集中的平均信息素濃度和啟發(fā)式信息的變化率；β是一個(gè)預(yù)定義的參數(shù)，用來(lái)控制啟發(fā)信息的影響。

Step 2 按照上述轉(zhuǎn)移概率，把未分配的節(jié)點(diǎn)分配到預(yù)分配子集時(shí)，利用魚群擁擠度的概念，計(jì)算該子集的擁擠度qi（j）如式（6）所示：

如果qi（j）＜σ（t），則表示路徑不擁擠，選擇當(dāng)前j節(jié)點(diǎn)分配到i子集中，否則，表示該路徑擁擠，則在可行鄰域內(nèi)重新計(jì)算當(dāng)前j節(jié)點(diǎn)分配到其他子集的期望。其中，σ（t）表示t時(shí)刻的擁擠度閾值，按式（7）進(jìn)行更新：

式中，c為閾值變化系數(shù)。

Step 3 重復(fù)上述Step1～Step2步驟，直到所有螞蟻完成子集構(gòu)建。

圖3 構(gòu)建子集結(jié)構(gòu)示意圖

3.3 關(guān)鍵域法（KFM）

在實(shí)際應(yīng)用中，為了保證監(jiān)控區(qū)域被完全覆蓋甚至多重覆蓋，傳感器節(jié)點(diǎn)通常大量、隨機(jī)地部署在監(jiān)測(cè)區(qū)域內(nèi)，從而會(huì)產(chǎn)生很多冗余節(jié)點(diǎn)。為了除去冗余節(jié)點(diǎn)，提高節(jié)點(diǎn)利用率，現(xiàn)有的CCP算法［15］、圓周覆蓋算法（CCA）［16］在去除冗余節(jié)點(diǎn)后網(wǎng)絡(luò)會(huì)產(chǎn)生覆蓋盲區(qū)，基于Voronoi圖［17］的算法計(jì)算量大且只能用于同構(gòu)網(wǎng)絡(luò)，本文提出了用關(guān)鍵域法去冗余的方法，分別對(duì)各子集進(jìn)行冗余節(jié)點(diǎn)判斷，不僅不會(huì)產(chǎn)生覆蓋盲區(qū)，而且可以用于異構(gòu)網(wǎng)絡(luò)。

如圖4所示，傳感器節(jié)點(diǎn)1，2，3，4，5實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域完全覆蓋。由文獻(xiàn)［2］知，圖4中灰色區(qū)域即為關(guān)鍵區(qū)域集（由最少傳感器節(jié)點(diǎn)所覆蓋區(qū)域）。要實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域覆蓋，傳感器節(jié)點(diǎn)1，2，3，4必須存在，剩下節(jié)點(diǎn)可能是冗余節(jié)點(diǎn)，需要通過(guò)進(jìn)一步計(jì)算判斷。若移除節(jié)點(diǎn)，整個(gè)目標(biāo)區(qū)域覆蓋率未變化，即為冗余節(jié)點(diǎn)，反之不是。由圖可知節(jié)點(diǎn)5為冗余節(jié)點(diǎn)。在判斷出所有冗余節(jié)點(diǎn)后，對(duì)其進(jìn)行新的子集構(gòu)建，構(gòu)建出更多覆蓋子集，這不僅提高了節(jié)點(diǎn)利用率，同時(shí)延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖4 關(guān)鍵區(qū)域判斷

3.4 算法流程

本文提出的群混合智能算法是通過(guò)魚群擁擠度、蟻群信息素、啟發(fā)式信息的共同作用來(lái)構(gòu)建連通覆蓋子集，當(dāng)螞蟻完成連通覆蓋子集的構(gòu)建后需要進(jìn)行局部信息素更新，然后利用目標(biāo)評(píng)價(jià)函數(shù)對(duì)各子集進(jìn)行評(píng)優(yōu)，找出當(dāng)前最優(yōu)子集，接著通過(guò)關(guān)鍵域法去冗余，構(gòu)建出更多子集，最后對(duì)當(dāng)前最優(yōu)子集的節(jié)點(diǎn)進(jìn)行全局信息素更新，直到迭代完成，找出全局優(yōu)化連通覆蓋子集。以下是對(duì)算法流程的具體描述：

①初始化節(jié)點(diǎn)，設(shè)置螞蟻數(shù)m，最大迭代次數(shù)max及優(yōu)化參數(shù)（β，τ0，ρ，ζ，w0，w1，w2，w3，c）。

②預(yù)估優(yōu)化連通覆蓋子集上界值|CF|。

③基于魚群擁擠度、蟻群信息素、啟發(fā)信息構(gòu)建連通覆蓋子集。

④局部蟻群信息素更新：在螞蟻構(gòu)建完子集后，對(duì)每個(gè)子集中任意兩個(gè)節(jié)點(diǎn)J、K間進(jìn)行信息素更新，并按式（8）更新為：

式中，ρ∈（0，1）是局部信息素更新的蒸發(fā)率，τ0表示初始信息素濃度。

⑤評(píng)估出當(dāng)前最優(yōu)子集Sbs：綜合考慮構(gòu)建的各連通覆蓋子集對(duì)覆蓋約束、收集約束、連通約束的滿足程度，通過(guò)式（9）目標(biāo)評(píng)價(jià)函數(shù)進(jìn)行評(píng)估：

⑥對(duì)當(dāng)前最優(yōu)子集Sbs進(jìn)行關(guān)鍵域法去冗余。

Step 1 對(duì)Sbs各層子集分別進(jìn)行關(guān)鍵域計(jì)算，并判斷覆蓋關(guān)鍵域的節(jié)點(diǎn)，即判斷非冗余節(jié)點(diǎn)。

Step 2 遍歷子集中剩余節(jié)點(diǎn)，進(jìn)行冗余判斷。判斷標(biāo)準(zhǔn)為：移除節(jié)點(diǎn)是否降低目標(biāo)區(qū)域覆蓋率，若減少，非冗余節(jié)點(diǎn)；反之為冗余節(jié)點(diǎn)。

Step 3 對(duì)所有冗余節(jié)點(diǎn)進(jìn)行新的子集構(gòu)建。

⑦全局蟻群信息素更新：為了保留連通覆蓋子集的結(jié)構(gòu)特征，吸引更多螞蟻至全局最優(yōu)解的周圍進(jìn)行搜索。將去冗余后的優(yōu)化子集的任意兩個(gè)節(jié)點(diǎn)J、K間進(jìn)行全局信息素更新，如式（10）所示：

式中，ζ∈（0，1）是全局信息素更新的蒸發(fā)率，δτ是信息素濃度增量，由式（11）定義：

⑧算法每一次完成全局信息素更新即算法完成一次迭代，此時(shí)如滿足停止條件，則終止整個(gè)算法并得到優(yōu)化連通覆蓋子集，否則返回（3）繼續(xù)優(yōu)化。

根據(jù)上述算法流程，可得算法流程圖如圖5所示。

圖5 群混合算法流程圖

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

4.1 仿真環(huán)境

為驗(yàn)證本文提出的算法的有效性，利用蟻群算法（ACO）與本文的群混合智能算法（HSIAO）進(jìn)行對(duì)比。在搜索過(guò)程中，由于蟻群算法與改進(jìn)后群混合智能算法都含有一定的隨機(jī)性，為減小隨機(jī)性帶來(lái)的誤差，在本文每組實(shí)驗(yàn)中，每個(gè)算法都執(zhí)行25次獨(dú)立試驗(yàn)，分別取各算法的平均值（除不盡的平均值保留二位小數(shù)）作為最后的實(shí)驗(yàn)結(jié)果。其中實(shí)驗(yàn)中的控制參數(shù)設(shè)置為螞蟻數(shù)m=5，β=2，ρ=ζ=0.1，w0，w1，w2= 1/3，w3=|CF|，最大迭代次數(shù)max=10，閾值c=1。仿真結(jié)果表明，本文所提出的算法效果上優(yōu)于蟻群算法。

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 優(yōu)化連通覆蓋子集數(shù)的均值比較

實(shí)驗(yàn)在50 m×50 m目標(biāo)監(jiān)測(cè)區(qū)域進(jìn)行。隨機(jī)部署大量SR和SK節(jié)點(diǎn)。表1匯總了網(wǎng)絡(luò)的設(shè)置，包括|SR|和|SK|數(shù)量，傳感器感知半徑rs，收集器收集半徑rt，收集器傳輸半徑Rt，理想連通覆蓋子集數(shù)量的上界值|CF|，兩種算法尋優(yōu)的平均優(yōu)化連通覆蓋子集數(shù)。一共進(jìn)行了十組不同的實(shí)驗(yàn)，其中每組的節(jié)點(diǎn)規(guī)模不同。從表1中可以看出，在|SR|=100、|SK|=50、rs=15、rt=18、Rt=32、|CF|=9相同情況下，本文算法平均找出了9層連通覆蓋子集，而蟻群算法只找出6.83層連通覆蓋子集，沒能達(dá)到理想連通覆蓋數(shù)量的上界值|CF|。同時(shí)由整個(gè)列表結(jié)果可以得知，本文算法明顯優(yōu)于蟻群算法，并且在迭代次數(shù)相同條件下，本文算法比蟻群算法更早找到全局最優(yōu)值。

表2 兩種算法構(gòu)建優(yōu)化連通覆蓋子集數(shù)的均值比較

為了更加直觀說(shuō)明改進(jìn)后算法優(yōu)越性，本文畫出了在|SR|=100、|SK|=50、rs=15、rt=18、Rt=32、|CF|=9參數(shù)下，改進(jìn)后的群混合智能算法完成10次迭代后，找到的9層連通覆蓋子集在目標(biāo)區(qū)域內(nèi)滿足覆蓋約束、收集約束、連通約束效果示意圖，如圖6和圖7所示。其中圖中方框代表50 m×50 m的目標(biāo)監(jiān)測(cè)區(qū)域，●表示傳感器節(jié)點(diǎn)，▲表示收集器節(jié)點(diǎn)，圖中編號(hào)0-99是不同傳感器節(jié)點(diǎn)，100-149是不同收集器節(jié)點(diǎn)，其中以傳感器節(jié)點(diǎn)為圓心和rs為半徑所畫的深色圓代表傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域監(jiān)測(cè)效果，以收集節(jié)點(diǎn)為圓心和rt為半徑所畫的淺色圓區(qū)域代表收集節(jié)點(diǎn)對(duì)傳感器節(jié)點(diǎn)信息收集效果。從圖6（a）～（i）子圖中可以看出，每一組子圖的傳感器節(jié)點(diǎn)都能對(duì)目標(biāo)監(jiān)測(cè)區(qū)域?qū)崿F(xiàn)完全覆蓋，且全部傳感器節(jié)點(diǎn)至少處于一個(gè)收集節(jié)點(diǎn)的收集半徑內(nèi)，實(shí)現(xiàn)了收集節(jié)點(diǎn)對(duì)傳感器節(jié)點(diǎn)信息的收集。從圖7（a）～（i）子圖中可以看出，以收集節(jié)點(diǎn)為圓心和Rt為半徑所畫的圓區(qū)域，每個(gè)子圖中任意兩個(gè)收集器節(jié)點(diǎn)能進(jìn)行傳輸通信，即形成了一個(gè)無(wú)線連通網(wǎng)絡(luò)，同時(shí)9層連通覆蓋子集節(jié)點(diǎn)冗余度極少，可以看出本文算法的有效性。

圖6 覆蓋收集子集示意圖

圖7 連通子集示意圖

4.2.2 魚群擁擠度對(duì)實(shí)驗(yàn)結(jié)果影響分析

為了說(shuō)明魚群擁擠度對(duì)本文提出的群混合算法實(shí)驗(yàn)結(jié)果的影響，在相同的仿真條件下，分別對(duì)蟻群算法和本文提出的群混合算法進(jìn)行了尋優(yōu)值收斂性分析。圖8（a）、（b）分別在|SR|=100，|SK|= 50，rs=15，rt=18，Rt=32和|SR|=800，|SK|=150，rs=8，rt= 18，Rt=30的條件下，所得到的結(jié)果。橫坐標(biāo)代表迭代次數(shù)，本文最大迭代次數(shù)設(shè)為10，縱坐標(biāo)表示滿足連通覆蓋的平均優(yōu)化子集數(shù)S。對(duì)圖8的曲線分析可知，在算法初期，本文提出的群混合算法在魚群擁擠度作用下，能夠更快地跳出局部最優(yōu)，這表明該算法增強(qiáng)了全局尋優(yōu)能力，并且在相同迭代次數(shù)下，本文提出的群混合算法找到的平均子集數(shù)較蟻群算法多，更說(shuō)明本文算法尋優(yōu)效果明顯。

4.2.3 節(jié)點(diǎn)冗余分析

為了說(shuō)明本文提出的關(guān)鍵域法去冗余節(jié)點(diǎn)的有效性，在算法前期利用蟻群算法構(gòu)建子集解，而在算法后期分別應(yīng)用關(guān)鍵域法（KFM）、圓周覆蓋算法（CCA）判斷冗余節(jié)點(diǎn)。圖9所示是在|SK|=100，rs=10，rt=20，Rt=32的條件下，部署不同傳感器節(jié)點(diǎn)數(shù)a所產(chǎn)生平均冗余節(jié)點(diǎn)的個(gè)數(shù)變化，即是平均冗余節(jié)點(diǎn)數(shù)b。

圖8 魚群擁擠度對(duì)實(shí)驗(yàn)結(jié)果影響分析

圖9 部署傳感器數(shù)與節(jié)點(diǎn)冗余數(shù)比較

圖9中橫坐標(biāo)表示隨機(jī)部署不同傳感器節(jié)點(diǎn)數(shù)，縱坐標(biāo)表示不同傳感器節(jié)點(diǎn)數(shù)下，構(gòu)建子集出現(xiàn)的平均冗余節(jié)點(diǎn)數(shù)量。從圖9可以看出蟻群算法構(gòu)建子集存在大量冗余節(jié)點(diǎn)，在應(yīng)用去冗余算法后，可有效地減少冗余節(jié)點(diǎn)，對(duì)比圖中各曲線，可以看出關(guān)鍵域法去冗余效果比圓周覆蓋算法更優(yōu)。

5 結(jié)論

針對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中多層覆蓋問題，本文結(jié)合了基本魚群算法和蟻群算法各自的優(yōu)點(diǎn)，將魚群擁擠度引進(jìn)到蟻群算法中，防止算法早期陷入局部最優(yōu)，該混合智能算法提高了算法的收斂速度，增強(qiáng)了全局尋優(yōu)能力；同時(shí)提出的關(guān)鍵域法去冗余，提高了節(jié)點(diǎn)利用率，延長(zhǎng)了網(wǎng)絡(luò)生命周期。通過(guò)對(duì)理論的分析以及實(shí)驗(yàn)的仿真，結(jié)果都表明該方法模型的有效性。

［1］Dietrich I，Dressler F.On the Lifetime of Wireless Sensor Net?works［J］.ACM Trans Sensor Networks，2009，5（1）：1-37.

［2］毛科技，陳慶章.基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋優(yōu)化研究［J］.傳感技術(shù)學(xué)報(bào)，2015，28（7）：1058-1065.

［3］杜曉玉，孫力娟.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法［J］.電子與信息學(xué)報(bào)，2013，36（3）：696-701.

［4］陳業(yè)鋼，徐則同.無(wú)線傳感器網(wǎng)絡(luò)最小連通覆蓋的節(jié)能算法［J］.計(jì)算機(jī)仿真，2014，31（3）：324-350.

［5］張蕾.無(wú)線傳感器網(wǎng)絡(luò)中多重覆蓋算法的研究［J］.傳感技術(shù)學(xué)報(bào)，2014，27（6）：802-806.

［6］Zhu C，Zheng C L.A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks［M］.Journal of Network and Comput?er Applications，2012，35（2）：619-632.

［7］Slijepcevic S，Potkonjak M.Power Efficient Organization of Wire?less Sensor Networks［C］//IEEE International Conference on Com?munication，2001，2：472-476.

［8］Hu X M，Luo X N.Hybrid Genetic Algorithm Using a Forward En?coding Scheme for Lifetime Maximization of Wireless Sensor Net?works［J］.IEEE，2010，14（5）：766-781.

［9］Attea B A，Khalil E A.A Multi-Objective Disjoint Set Covers for Reliable Lifetime Maximization of Wireless Sensor Networks［J］.Wireless Pers Commun，2015，81（2）：819-838.

［10］Lin ，Zhang J.An Ant Colony Optimization Approach for Maxi?mizing the Lifetime of Heterogeneous Wireless Sensor Networks［J］.IEEE Transactions on Systems，2012，42（3）：408-420.

［11］Zhong Y P，Huang P W，Wang B.Maximum Lifetime Routing Based on Ant Colony Algorithm for Wireless Sensor Networks［C］//IET Conference on Wireless，Mobile，Sensor Networks，Shanghai，2007：789-792.

［12］Chartrand G，Zhang P.Introduction to Graph Theory［M］.The People’s Post Telecommun，2006：140-156.

［13］Liao T，Socha K.Ant Colony Optimization for Mixed-Variable Op?timization［J］.IEEE Transactions on Evolutionary Computation，2014，18（4）：503-518.

［14］Huang Y Y，Li K Q.Coverage Optimization of Wireless Sensor Network Based on Artificial Fish Swarm Algorithm［J］.Applica?tion Research of Computer，2013，30（2）：554-556.

［15］Xing G L，Wang X R.Integrated Coverage and Connectivity Con?figuration for Energy Conversation in Sensor Network［J］.ACM Transactions on Sensor Networks，2010，1（1）：36-72.

［16］劉瀟，張錦.SCCP無(wú)線傳感器網(wǎng)絡(luò)自調(diào)節(jié)圓周覆蓋協(xié)議［J］.計(jì)算機(jī)應(yīng)用研究，2010，24（4）：1407-1409.

［17］楊海靂，趙靜.基于Voronoi圖的無(wú)線傳感器網(wǎng)絡(luò)覆蓋算法研究［J］.信息通信，2015，151（7）：28-31.

唐玲艷（1991-），女，華東理工大學(xué)碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)；

吳 雪（1957-），通信作者，女，副教授，碩士研究生導(dǎo)師，先后任教于華中科技大學(xué)、天津大學(xué)和華東理工大學(xué)。主要研究方向?yàn)橛?jì)算智能與自然計(jì)算，圖論及通信網(wǎng)系統(tǒng)優(yōu)化，無(wú)線傳感器網(wǎng)絡(luò)，wuxue@ecust.edu.cn；

吳 喆（1991-），男，華東理工大學(xué)碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

羅小娟（1974-），女，博士，講師，主要研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化，物聯(lián)網(wǎng)及無(wú)線傳感器網(wǎng)絡(luò)。

Hybrid Swarm Intelligence Algorithm Optimizing Heterogeneous Wireless Sensor Network LifeTime*

TANG Lingyan，WU Xue*，WU Zhe，LUO Xiaojuan
（School of Information Science and Engineering，East China University of Science and Technology，Shanghai 200237，China）

In order to optimize the lifetime of heterogeneous wireless sensor network，the key methodology is based on finding more connected covers subsets.This paper proposes to form the target evaluation function from coverage constraints，collection constraints and connectivity constraints.According to the model，this paper introduces the fish crowded degree into the ant colony algorithm to prevent ant colony algorithm from local convergence at the be?ginning of the algorithm.The experiments show that the improved algorithm is better than general ant colony algo?rithm in global search ability and convergence speed.And as for the ant colony algorithm in building a subset that exists a number of redundant nodes，this paper puts forward the key field method（KFM）to judge redundant nodes in each subset and constructs new subsets by the use of the redundant nodes.Not only it improves the utilization effi?ciency of nodes，but also extends the lifetime of heterogeneous networks.

heterogeneous wireless sensor network；network lifetime；connected covers subsets；ant colony algo?rithm；fish crowded degree；key field method

TP212.9；TP18；TP393

A

1004-1699（2016）11-1759-09

EEACC：6150P；6210C 10.3969/j.issn.1004-1699.2016.11.022

項(xiàng)目來(lái)源：上海市自然科學(xué)基金項(xiàng)目（15ZR1408700）

2016-03-28 修改日期：2016-07-27