坎 香 ，方 偉

1.江陰職業(yè)技術學院 計算機科學系， 江蘇 江陰 214405；2.江南大學 物聯(lián)網(wǎng)工程學院， 江蘇 無錫 214122

無線傳感器網(wǎng)絡（wireless sensor networks，WSN）涉及傳感器技術、無線通信技術、嵌入式技術、分布式信息處理技術等多個學科領域的內容，是當今學術研究的熱點領域之一［1-3］。WSN中的傳感器節(jié)點采用無線連接，以多跳自組織方式形成網(wǎng)絡，將感知信息傳送至匯聚節(jié)點，再由匯聚節(jié)點通過衛(wèi)星或物聯(lián)網(wǎng)發(fā)送至終端的任務管理節(jié)點進行統(tǒng)一分析管理。WSN 的覆蓋方法是WSN 的一項關鍵基本技術，該方法的優(yōu)劣關系到組網(wǎng)成本和網(wǎng)絡容錯能力，以及整個網(wǎng)絡的工作效率。因此，WSN 的覆蓋優(yōu)化方法是國內外專家學者的重點研究方向之一［4-6］。

近年來，群體智能算法由于出色的尋優(yōu)能力被廣泛應用于WSN 的覆蓋優(yōu)化［7-9］。文獻［10-11］提出利用遺傳算法較強的全局搜索能力和并行搜索能力實現(xiàn)WSN 的覆蓋優(yōu)化，但受局部搜索能力的限制，算法在最優(yōu)解附近收斂速度慢，從而導致動態(tài)節(jié)點選擇的實時性不高；文獻［12］以最大化節(jié)點間的距離為適應度函數(shù)，將微粒群算法應用于WSN 的覆蓋問題，實現(xiàn)以簇頭節(jié)點為中心向外均勻分布的節(jié)點部署形式，但該算法未考慮邊界約束問題。

微分進化算法是Rainer Storn 和Kenneth Price在1995年為求解切比雪夫多項式而提出，主要特點是收斂速度快、可調參數(shù)少、魯棒性好、算法簡單，其基本思想在于利用當前種群不同個體之間的差異，通過重組得到中間種群，并在子代與父代中選擇較優(yōu)個體來獲得新一代種群。作為一種新穎的進化算法，微分進化算法在面對非線性、不可微、多目標、多約束的復雜優(yōu)化問題時顯示出高效的尋優(yōu)能力，目前已成功應用于攝像機標定、生物信息學、工業(yè)生產優(yōu)化、變電站規(guī)劃、電力系統(tǒng)調度等領域。

目前微分進化算法在WSN 路由算法上的應用較多，但在WSN 覆蓋部署問題上的應用尚少。本文針對微分進化算法在WSN 覆蓋問題上的應用特點，嘗試完善覆蓋模型、改進算法的適應度評價函數(shù)和選擇機制，以實驗論證微分進化算法在WSN覆蓋問題上的可行性。

1 無線傳感器網(wǎng)絡覆蓋模型及改進

1.1 基本覆蓋模型

設WSN 的監(jiān)測區(qū)域A 為L×W的二維長方形平面，將監(jiān)測區(qū)域A劃分為m×n個網(wǎng)格點，并布置N個傳感器節(jié)點。傳感器節(jié)點的集合為C={c1，c2，…，cN}，其中ci={xi，yi，r}（(xi，yi)為節(jié)點ci的位置坐標，r為節(jié)點ci的傳感半徑），i=1，2，...，N。

本文采用二元感知模型，將節(jié)點的感知范圍等效成一個以節(jié)點位置為圓心、傳感半徑r為半徑的圓。網(wǎng)格點（x，y）是否被傳感器所覆蓋，可用式（1）進行判斷，即

式中：Pcov(x，y，ci)為感知概率，i=1，2，...，N。

在監(jiān)測區(qū)域A 內m×n個網(wǎng)格點中，只要存在一個網(wǎng)格點（x，y），使得Pcov(x，y，ci) = 1，即認為該網(wǎng)格點（x，y）被傳感器節(jié)點ci所覆蓋。統(tǒng)計監(jiān)測區(qū)域A內被覆蓋的總網(wǎng)格點數(shù)，再由式（2）計算WSN在監(jiān)測區(qū)域A內的覆蓋率，即

式中：f為監(jiān)測區(qū)域A內的覆蓋率，D為A內被覆蓋的總網(wǎng)格點數(shù)。

1.2 覆蓋模型的改進

1.2.1 傳感器圓心范圍的約束處理

在對監(jiān)測區(qū)域A 內的L×W二維平面使用微分進化算法進行變異交叉過程中，可能會出現(xiàn)圓心落在區(qū)域外的節(jié)點，從而減小了節(jié)點的覆蓋面積。為此，需要將圓心落至監(jiān)測區(qū)域外的節(jié)點通過移動的方式移動至監(jiān)測區(qū)域內，具體操作方式如下：

式中：x、y分別表示監(jiān)測區(qū)域內任一傳感器節(jié)點的橫坐標與縱坐標；L、W分別表示監(jiān)測區(qū)域的長和寬，m。

1.2.2 節(jié)點過于聚集的處理

為了提高WSN 的覆蓋率，在傳感器節(jié)點部署過程中，很可能出現(xiàn)傳感器節(jié)點過于聚集導致節(jié)點重疊的情況。為限制各覆蓋區(qū)域內重疊節(jié)點的數(shù)量，減少節(jié)點的重疊區(qū)域，需要根據(jù)傳感器節(jié)點ci的位置，計算周邊的重疊節(jié)點數(shù)O(xi，yi)，公式如式（4）所示，即

式中：xj、yj分別表示監(jiān)測區(qū)域A內傳感器節(jié)點cj的橫坐標與縱坐標，j=1，2，...，N。

令M是與監(jiān)測區(qū)域A的面積及傳感器節(jié)點個數(shù)N有關的常數(shù)，當O(xi，yi)＞M時，節(jié)點ci的位置需要重新在覆蓋區(qū)域內隨機生成。

2 基于改進微分進化算法的無線傳感器覆蓋優(yōu)化方法

2.1 基本微分進化算法

微分進化算法與遺傳算法相似，都含有變異、交叉和選擇幾個步驟，但相對于遺傳算法又具有參數(shù)少的優(yōu)點。

2.1.1 變異

微分進化算法的變異操作是在種群中隨機選擇兩個個體作差分運算，然后將所得向量差加權后，根據(jù)一定的規(guī)則加到第三個個體（基向量）上。這種變異方式有效利用群體中個體間的分布差異，增強了全局搜索性能。

在微分進化中常用的變異算子有5 種，本文采用DE/rand/1的方式，即在傳感器分布時從群體中隨機選擇2 個個體Xr(t)、Xs(t)，以及種群中的最優(yōu)個體Xbest(t)，按照式（5）產生新的個體，即

式中：Xr(t) -Xs(t)為2個個體的向量差；F為縮放因子。

2.1.2 交叉

變異中差分運算是微分進化算法的關鍵。在變異操作完成后微分進化算法采用均勻交叉的方法產生一些試驗向量，以增加種群的多樣性。具體地說，在無線傳感器網(wǎng)絡覆蓋中，監(jiān)測區(qū)域是個二維平面，種群中第i個個體的位置坐標Xi=(Xi，1，Xi，2)（Xi，1表示第i個個體的第1 維分量，Xi，2表示第i個個體的第2 維分量）；對種群中第i個個體的每個分量Xi，k（k=1，2），隨機生成一個0～1之間的實數(shù)b，將經(jīng)過變異操作得到的中間個體Ui(t+ 1)和當前進化個體Xi(t)進行雜交操作，得到候選個體Vi(t+ 1)，其中第k維分量的操作如式（6）所示，即

式中：交叉因子R∈[0，1]；z是針對第i個個體生成的一個屬于［1，2］且均勻分布的隨機整數(shù)。

這種交叉策略使得Vi，k(t+ 1)至少取到一個Ui，k(t+ 1)的值，即候選個體Vi(t+ 1)至少繼承一維中間個體Ui(t+ 1)的分量，以確保每個個體都有交叉，從而更有效地提高種群的多樣性，保證個體的進化，防止陷入局部最優(yōu)。

2.1.3 選擇

為了保證算法收斂，基本微分進化算法依照貪婪準則進行選擇操作，即將經(jīng)過變異、交叉后產生新個體的適應度值與父代個體的適應度值作比較，讓適應度值好的個體進入下一代。因此，在無線傳感器網(wǎng)絡覆蓋問題中，通常將區(qū)域覆蓋率f作為微分進化算法的適應度函數(shù)。選擇操作如式（7）所示，即

式中：f(t)為第t代種群的覆蓋率，Ct為第t代種群集合。

通常區(qū)域覆蓋率越大，種群的覆蓋能力越強，就更可能被選入下一代中。

2.2 改進的微分進化算法

為提高微分進化算法應用于WSN 覆蓋問題上的收斂速度和尋優(yōu)能力，本文針對微分進化算法中的選擇操作，提出一種改進的選擇優(yōu)化機制，具體流程如圖1所示。

圖1 基于改進微分進化算法WSN覆蓋優(yōu)化方法流程圖Fig. 1 Flow chart of WSN coverage optimization method based on improved differential evolution algorithm

在微分進化算法中，如何選擇最優(yōu)個體進入下一次迭代是個十分重要的問題。在原微分進化算法中，最優(yōu)個體的選擇采用“優(yōu)勝劣汰”的淘汰機制，即將變異后的子代個體與原父代個體進行對比，如果比父代更適合生存，那么用子代個體取代父代個體，否則仍采用父代個體。這種算法的特點是收斂速度較慢。

為提高算法的收斂速率，新的群體選擇不再采用原來的單個個體的優(yōu)勝劣汰，而是在原父代Ct與變異后子代群體Ct+1中選出最優(yōu)的H個個體作為新的種群，并進入下一次迭代過程。在新的選擇操作中，采用單個節(jié)點的覆蓋率（即單個節(jié)點的覆蓋率對總覆蓋率有無提升）對個體進行適應度評價，從而在保證個體變異隨機性的同時加大了上一代優(yōu)異因子留下來的可能性。

按照圖1的流程，覆蓋優(yōu)化方法步驟如下：

（1） 明確問題定義域，輸入WSN 監(jiān)測區(qū)域、傳感器節(jié)點以及改進微分進化算法的相關參數(shù)。

（2） 初始化H個個體的坐標，即在問題定義域中隨機產生H個傳感器節(jié)點的原始位置，創(chuàng)建初始種群，初始化交叉因子、縮放因子等環(huán)境參數(shù)。

（3） 按式（5）計算傳感器群體中各個節(jié)點經(jīng)過變異操作后的坐標。

（4） 將經(jīng)過變異后各節(jié)點的中間個體坐標按式（6）計算傳感器群體中各個節(jié)點經(jīng)過交叉操作后的坐標。

（5） 判斷傳感器群體中各個節(jié)點圓心是否落在監(jiān)測區(qū)域外。針對落在監(jiān)測區(qū)域外的節(jié)點，按式（3）對這些節(jié)點的坐標進行重新計算，使得這些節(jié)點移動至監(jiān)測區(qū)域內，以對其進行圓心范圍的約束處理。

（6） 根據(jù)傳感器群體中每個節(jié)點ci的坐標位置，按式（4）計算周邊的重疊節(jié)點數(shù)O(xi，yi)；當O(xi，yi)＞M時，將節(jié)點ci的位置重新在覆蓋區(qū)域內隨機生成。

（7） 對經(jīng)過上述步驟產生的候選傳感器節(jié)點群體中的每個節(jié)點，采用每個節(jié)點的覆蓋率對每個節(jié)點進行適應度評價；然后從候選傳感器節(jié)點群體和當前傳感器節(jié)點群體中選出H個適應度值（節(jié)點覆蓋率）最大的節(jié)點，作為新的傳感器群體中的節(jié)點。

（8） 判斷當前傳感器節(jié)點群體的覆蓋率是否達到預先設定的值或者當前算法的迭代次數(shù)是否達到最大迭代次數(shù)。若滿足，則算法結束，輸出最優(yōu)解即為傳感器群體中最優(yōu)的節(jié)點；否則，返回步驟（3），繼續(xù)進行下一次迭代。

3 仿真實驗及分析

假設仿真實驗需要覆蓋的傳感區(qū)域為100 m×100 m，種群規(guī)模H=40，即有40 個相同配置的無線傳感器，每個傳感器的傳感半徑r=12 m，最大迭代次數(shù)d=200，縮放因子F=0.7，交叉因子R=0.5。仿真實驗在MATLAB 環(huán)境下進行，每個實驗都隨機進行30次，并記錄平均覆蓋率。

3.1 傳感器圓心范圍的約束處理對覆蓋率的影響

采用基本微分進化算法，比較覆蓋優(yōu)化模型在傳感器圓心范圍約束處理前后的影響，結果如圖2 所示。從圖2 可以看出，覆蓋優(yōu)化模型加入范圍約束后，隨著迭代次數(shù)的增加，迭代曲線更加平緩，平均覆蓋率從82.67%上升到89.87%。說明圓心范圍的約束措施是有效的。

圖2 覆蓋率收斂曲線Fig. 2 Coverage convergence curve

3.2 重疊節(jié)點的處理對覆蓋率的影響

采用基本微分進化算法，比較覆蓋優(yōu)化模型在處理重疊節(jié)點前后的覆蓋能力，結果如圖3 所示。由圖3 可以看出，覆蓋優(yōu)化模型引入重疊節(jié)點的處理之后，隨著迭代次數(shù)的增加，迭代曲線更加平緩，平均覆蓋率從81.79% 上升到89.68%。說明節(jié)點的重疊處理措施是有效的。

圖3 覆蓋率收斂曲線Fig. 3 Coverage convergence curve

3.3 不同微分進化算法對覆蓋率的影響

利用改進的覆蓋模型，采用基本微分進化算法與改進微分進化算法綜合比較算法的平均覆蓋率，結果如圖4 所示。由圖4 的收斂曲線可見，相比基本微分進化算法，隨著迭代次數(shù)的增加，改進的微分進化算法迭代曲線更加平緩，平均覆蓋率從81.40%上升到89.53%。

圖4 覆蓋率收斂曲線Fig. 4 Coverage convergence curve

3.4 改進覆蓋模型及改進微分進化算法對覆蓋率的影響

采用改進的覆蓋模型和改進的微分進化算法進行仿真，結果如圖5 所示。由圖5 可見，在優(yōu)化過程的第一代時，群體的平均覆蓋率僅為78.91%；到了第50 代的時候，群體的平均覆蓋率達到了88.80%；到了第150 代時，平均覆蓋率已達到89.72%。說明隨著進化代數(shù)的增加，覆蓋率逐步上升，即采用的傳感器圓心范圍約束及重疊節(jié)點處理的措施是有效的，能夠提高無線傳感器的網(wǎng)絡覆蓋范圍。

圖5 基于改進微分進化算法及改進覆蓋模型的覆蓋率收斂曲線Fig. 5 Convergence curve of coverage based on improved differential evolution algorithm and improved coverage model

4 結論

通過將微分進化算法應用于無線傳感器分布優(yōu)化的研究，在對微分進化算法的選擇操作進行改進后，發(fā)現(xiàn)在同等條件下，與基本微分進化算法相比，改進算法的性能及收斂性能都有了較大提升；改進覆蓋優(yōu)化模型對無線傳感器網(wǎng)絡的覆蓋率也有明顯提高。因此，要改善算法的性能，提高網(wǎng)絡節(jié)點覆蓋率，應對覆蓋模型進行有效處理，并對基本微分進化算法進行一定的改進。