群混合智能算法優化異構WSN的生命周期*

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

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

群混合智能算法優化異構WSN的生命周期*

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

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

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

異構無線傳感器網絡；網絡生命周期；連通覆蓋子集；蟻群算法；魚群擁擠度；關鍵域法

由于大多數傳感器設備是由不可再生的電池供電，而評估無線傳感器網絡的基本準則是網絡生命周期［1］，所以如何優化延長網絡生命周期的研究成為了無線傳感器網絡的研究熱點和難點。盡管在同構無線傳感器網絡［2］中存在一些方法來解決這一問題，但是在異構無線傳感器網絡［3，4］中關于這一問題的研究進展緩慢。本文所考慮的異構無線傳感器網絡是Sensor和Sink節點半徑、數量的異構。針對這種異構，現有延長異構網絡生命周期的方法，是找到多組連通覆蓋子集［5，6］（每個子集設備可以解決網絡覆蓋和連通性問題），其中一個子集設備工作，其余設備可以改用節能的睡眠狀態。

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

1 連通覆蓋問題描述

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

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

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

2 核心問題描述

2.1 關鍵區域集CF與優化連通覆蓋子集上界值|CF|

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

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

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

表1 本文變量定義描述

圖2 區域與關鍵區域示意圖

2.2 目標評價函數

為了找到盡可能多的滿足連通覆蓋子集數，并且確保找出的子集是當前最優解，本文構建的目標評價函數是由網絡覆蓋約束、收集約束、連通約束組成，用它來對各子集進行滿意程度評價。以下是目標評價函數的具體描述。

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

覆蓋約束：Si的覆蓋率可以直接用作覆蓋約束的標準。將監測區域初始化為網格，每個網格是否被傳感器節點覆蓋作為衡量標準。本文覆蓋率Fi表示覆蓋的網格面積與整個監測區域面積的比例，如式（1）所示：

式中，Aj表示被覆蓋的網格面積，A表示監測區域面積，Si表示第i組連通覆蓋子集，SRj表示Si中傳感器節點。

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

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

連通約束：收集節點收集到的監測信息能有效地傳遞到目的地，需要收集節點組成一個無線連通網絡，當且僅當Gi是一個連接圖。基于圖論的知識，一個圖的連通可以通過它的極大連通子圖［12］的相對尺寸Li來測量出來。連通約束標準定義公式如式（3）所示，其中Bi表示極大連通子圖中收集節點的數量，Si表示第i組連通覆蓋子集，AllNum（SKj）表示子集Si中總的收集節點數量：

上述三個標準值都在［0，1］的范圍內。值越大表明找出的子集越優。如果Fi=Xi=Li=1，則Si實現了三個約束條件并且構建了一個連通覆蓋子集。應用這三個標準來評估所有的S集，目標優化函數可以定義為如式（4）所示：

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

3 群混合智能算法

3.1 蟻群與魚群混合算法

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

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

3.2 群混合智能算法思想

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

3.2.1 群混合智能算法構建子集規則

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

圖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層子集。根據上述子集構建規則，其步驟描述如下：

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

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

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

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

式中，c為閾值變化系數。

Step 3 重復上述Step1～Step2步驟，直到所有螞蟻完成子集構建。

圖3 構建子集結構示意圖

3.3 關鍵域法（KFM）

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

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

圖4 關鍵區域判斷

3.4 算法流程

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

①初始化節點，設置螞蟻數m，最大迭代次數max及優化參數（β，τ0，ρ，ζ，w0，w1，w2，w3，c）。

②預估優化連通覆蓋子集上界值|CF|。

③基于魚群擁擠度、蟻群信息素、啟發信息構建連通覆蓋子集。

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

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

⑤評估出當前最優子集Sbs：綜合考慮構建的各連通覆蓋子集對覆蓋約束、收集約束、連通約束的滿足程度，通過式（9）目標評價函數進行評估：

⑥對當前最優子集Sbs進行關鍵域法去冗余。

Step 1 對Sbs各層子集分別進行關鍵域計算，并判斷覆蓋關鍵域的節點，即判斷非冗余節點。

Step 2 遍歷子集中剩余節點，進行冗余判斷。判斷標準為：移除節點是否降低目標區域覆蓋率，若減少，非冗余節點；反之為冗余節點。

Step 3 對所有冗余節點進行新的子集構建。

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

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

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

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

圖5 群混合算法流程圖

4 仿真實驗

4.1 仿真環境

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

4.2 實驗結果分析

4.2.1 優化連通覆蓋子集數的均值比較

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

表2 兩種算法構建優化連通覆蓋子集數的均值比較

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

圖6 覆蓋收集子集示意圖

圖7 連通子集示意圖

4.2.2 魚群擁擠度對實驗結果影響分析

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

4.2.3 節點冗余分析

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

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

圖9 部署傳感器數與節點冗余數比較

圖9中橫坐標表示隨機部署不同傳感器節點數，縱坐標表示不同傳感器節點數下，構建子集出現的平均冗余節點數量。從圖9可以看出蟻群算法構建子集存在大量冗余節點，在應用去冗余算法后，可有效地減少冗余節點，對比圖中各曲線，可以看出關鍵域法去冗余效果比圓周覆蓋算法更優。

5 結論

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

［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］.傳感技術學報，2015，28（7）：1058-1065.

［3］杜曉玉，孫力娟.異構無線傳感器網絡覆蓋優化算法［J］.電子與信息學報，2013，36（3）：696-701.

［4］陳業鋼，徐則同.無線傳感器網絡最小連通覆蓋的節能算法［J］.計算機仿真，2014，31（3）：324-350.

［5］張蕾.無線傳感器網絡中多重覆蓋算法的研究［J］.傳感技術學報，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無線傳感器網絡自調節圓周覆蓋協議［J］.計算機應用研究，2010，24（4）：1407-1409.

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

唐玲艷（1991-），女，華東理工大學碩士研究生，主要研究方向為無線傳感器網絡；

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

吳 喆（1991-），男，華東理工大學碩士研究生，主要研究方向為無線傳感器網絡。

羅小娟（1974-），女，博士，講師，主要研究方向為網絡優化，物聯網及無線傳感器網絡。

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

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

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