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

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

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

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

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

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

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

由于大多數(shù)傳感器設(shè)備是由不可再生的電池供電，而評估無線傳感器網(wǎng)絡(luò)的基本準(zhǔn)則是網(wǎng)絡(luò)生命周期［1］，所以如何優(yōu)化延長網(wǎng)絡(luò)生命周期的研究成為了無線傳感器網(wǎng)絡(luò)的研究熱點和難點。盡管在同構(gòu)無線傳感器網(wǎng)絡(luò)［2］中存在一些方法來解決這一問題，但是在異構(gòu)無線傳感器網(wǎng)絡(luò)［3，4］中關(guān)于這一問題的研究進(jìn)展緩慢。本文所考慮的異構(gòu)無線傳感器網(wǎng)絡(luò)是Sensor和Sink節(jié)點半徑、數(shù)量的異構(gòu)。針對這種異構(gòu)，現(xiàn)有延長異構(gòu)網(wǎng)絡(luò)生命周期的方法，是找到多組連通覆蓋子集［5，6］（每個子集設(shè)備可以解決網(wǎng)絡(luò)覆蓋和連通性問題），其中一個子集設(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ò)覆蓋和連通問題，但該算法只能處理離散點的覆蓋問題。文獻(xiàn)［10］提出了基于蟻群優(yōu)化算法最大化異構(gòu)無線傳感器網(wǎng)絡(luò)的生命周期，它可以處理點覆蓋和區(qū)域覆蓋，但算法初期由于信息素影響，易陷入局部收斂，影響全局搜索能力和收斂速度，同時節(jié)點存在大量冗余。針對以上各算法存在的收斂速度慢和節(jié)點冗余等問題，本文在蟻群算法的基礎(chǔ)上，將魚群擁擠度的概念引入到蟻群算法中，同時針對子集中的冗余節(jié)點，本文提出了用關(guān)鍵域法去冗余的方法。仿真實驗表明，該算法具有更好的全局搜索能力和收斂速度，同時提高了節(jié)點利用率并且延長異構(gòu)網(wǎng)絡(luò)的生命周期。

1 連通覆蓋問題描述

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

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

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

2 核心問題描述

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

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

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

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

表1 本文變量定義描述

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

2.2 目標(biāo)評價函數(shù)

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

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

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

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

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

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

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

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

式中，w0，w1，w2，w3＞0是預(yù)定義值，是S中連通覆蓋子集數(shù)量，它隨著迭代次數(shù)的增加而增加。由式（4）可知，目標(biāo)函數(shù)由兩部分組成：第一部分總結(jié)了所有子集滿足約束條件的情況；第二部分定義了基于連通覆蓋數(shù)量的目標(biāo)值。本文提出的算法是通過螞蟻迭代尋優(yōu)構(gòu)建連通覆蓋子集，構(gòu)建過程中可以由式（4）求出該子集的目標(biāo)評價函數(shù)值，并與實驗初始設(shè)置的目標(biāo)評價函數(shù)值進(jìn)行比較，將比較值中較大的作為下一次比較的初始值，在每一輪中直到所有螞蟻完成子集構(gòu)建，此時目標(biāo)評價函數(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完全問題。但蟻群算法本身也存在一些缺點，如收斂速度慢、易陷入局部最優(yōu)等問題。

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

3.2 群混合智能算法思想

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

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

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

圖3中（v11，v32，v23，v44，v25，v36，v17，v48，v29，v310，v111，v412）（由黑箭頭定義），代表一個連通覆蓋集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é)點分配到某個子集中。其中使用上述的信息素和啟發(fā)式信息的設(shè)計方法，分配一個未配置的節(jié)點j到一個子集Si（i=1，2，…，|CF|）的概率計算如式（5）所示：

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

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

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

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

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

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

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

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

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

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

3.4 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 群混合算法流程圖

4 仿真實驗

4.1 仿真環(huán)境

為驗證本文提出的算法的有效性，利用蟻群算法（ACO）與本文的群混合智能算法（HSIAO）進(jìn)行對比。在搜索過程中，由于蟻群算法與改進(jìn)后群混合智能算法都含有一定的隨機(jī)性，為減小隨機(jī)性帶來的誤差，在本文每組實驗中，每個算法都執(zhí)行25次獨立試驗，分別取各算法的平均值（除不盡的平均值保留二位小數(shù)）作為最后的實驗結(jié)果。其中實驗中的控制參數(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 實驗結(jié)果分析

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

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

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

為了更加直觀說明改進(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)測區(qū)域，●表示傳感器節(jié)點，▲表示收集器節(jié)點，圖中編號0-99是不同傳感器節(jié)點，100-149是不同收集器節(jié)點，其中以傳感器節(jié)點為圓心和rs為半徑所畫的深色圓代表傳感器節(jié)點對目標(biāo)區(qū)域監(jiān)測效果，以收集節(jié)點為圓心和rt為半徑所畫的淺色圓區(qū)域代表收集節(jié)點對傳感器節(jié)點信息收集效果。從圖6（a）～（i）子圖中可以看出，每一組子圖的傳感器節(jié)點都能對目標(biāo)監(jiān)測區(qū)域?qū)崿F(xiàn)完全覆蓋，且全部傳感器節(jié)點至少處于一個收集節(jié)點的收集半徑內(nèi)，實現(xiàn)了收集節(jié)點對傳感器節(jié)點信息的收集。從圖7（a）～（i）子圖中可以看出，以收集節(jié)點為圓心和Rt為半徑所畫的圓區(qū)域，每個子圖中任意兩個收集器節(jié)點能進(jìn)行傳輸通信，即形成了一個無線連通網(wǎng)絡(luò)，同時9層連通覆蓋子集節(jié)點冗余度極少，可以看出本文算法的有效性。

圖6 覆蓋收集子集示意圖

圖7 連通子集示意圖

4.2.2 魚群擁擠度對實驗結(jié)果影響分析

為了說明魚群擁擠度對本文提出的群混合算法實驗結(jié)果的影響，在相同的仿真條件下，分別對蟻群算法和本文提出的群混合算法進(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。對圖8的曲線分析可知，在算法初期，本文提出的群混合算法在魚群擁擠度作用下，能夠更快地跳出局部最優(yōu)，這表明該算法增強(qiáng)了全局尋優(yōu)能力，并且在相同迭代次數(shù)下，本文提出的群混合算法找到的平均子集數(shù)較蟻群算法多，更說明本文算法尋優(yōu)效果明顯。

4.2.3 節(jié)點冗余分析

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

圖8 魚群擁擠度對實驗結(jié)果影響分析

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

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

5 結(jié)論

針對異構(gòu)無線傳感器網(wǎng)絡(luò)中多層覆蓋問題，本文結(jié)合了基本魚群算法和蟻群算法各自的優(yōu)點，將魚群擁擠度引進(jìn)到蟻群算法中，防止算法早期陷入局部最優(yōu)，該混合智能算法提高了算法的收斂速度，增強(qiáng)了全局尋優(yōu)能力；同時提出的關(guān)鍵域法去冗余，提高了節(jié)點利用率，延長了網(wǎng)絡(luò)生命周期。通過對理論的分析以及實驗的仿真，結(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ǎng)絡(luò)柵欄覆蓋優(yōu)化研究［J］.傳感技術(shù)學(xué)報，2015，28（7）：1058-1065.

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

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

［5］張蕾.無線傳感器網(wǎng)絡(luò)中多重覆蓋算法的研究［J］.傳感技術(shù)學(xué)報，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ǎng)絡(luò)自調(diào)節(jié)圓周覆蓋協(xié)議［J］.計算機(jī)應(yīng)用研究，2010，24（4）：1407-1409.

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

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

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

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

羅小娟（1974-），女，博士，講師，主要研究方向為網(wǎng)絡(luò)優(yōu)化，物聯(lián)網(wǎng)及無線傳感器網(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

項目來源：上海市自然科學(xué)基金項目（15ZR1408700）

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