基于遺傳算法的傳感器優化部署方法研究*

陳升來，陸 宏，李 濤

（中國電子科技集團公司第二十八研究所，江蘇 南京 210007）

基于遺傳算法的傳感器優化部署方法研究*

陳升來，陸 宏，李 濤

（中國電子科技集團公司第二十八研究所，江蘇 南京 210007）

針對傳感器優化部署問題，提出了基于遺傳算法的傳感器優化部署方法。以空間覆蓋率、覆蓋重數、資源利用率為評價指標，構建傳感器優化部署模型，提出了基于遺傳算法的傳感器部署模型求解方法。仿真實驗表明，提出的方法能夠實現傳感器優化部署，遺傳算法經過迭代后，一般區域覆蓋率達到了92%，重點區域覆蓋率達到了99%。此外，與基于二進制編碼的遺傳算法相比，該方法具有算法收斂快、傳感器資源利用率高等優點。

遺傳算法；優化部署；混合編碼；傳感器網絡

0　引 言

傳感器組網是實施情報感知的基礎。在網絡中心戰中，地理上分散的傳感器通過有線或無線網絡組成網絡化探測系統，對作戰目標進行協同感知和融合處理，生成實時或近實時情報信息，為作戰部隊、武器系統提供實時戰場態勢。

為發揮網絡化探測系統整體效能，提高探測系統的檢測概率，必須對有限的傳感器資源進行優化部署及合理使用［1-2］，實現對戰場空間的全方位探測。

由于受探測任務、探測效能、資源效費比等條件的約束，傳感器部署成為一個復雜的非線性、多約束問題。本文從空間覆蓋率、覆蓋重數、資源利用率等方面研究傳感器優化部署問題，建立傳感器優化部署模型，提出基于遺傳算法的最優求解方法，實現了部署模型的快速求解，并通過仿真實驗實現了驗證。

1　模型建立

在軍事領域，根據重要性的不同，傳感器探測區域分為一般區域和重點區域。前者側重于目標監視，后者側重于目標跟蹤。由于目標監視和目標跟蹤的側重點不同，故對傳感器探測提出了不同的要求：第一，為了達到警戒效果，要盡可能覆蓋一般區域；第二，為了確保重點區域的目標都能被監視和跟蹤，要完全覆蓋重點區域；第三，為了提升重點區域目標跟蹤效能和探測概率，要對重點區域實施多重覆蓋；第四，為了提高傳感器資源效費比，減少電磁輻射，參與探測的傳感器數量要盡可能少，避免傳感器過度冗余。

針對上述要求，利用一般區域覆蓋率、覆蓋重數、重點區域覆蓋率、傳感器資源利用率等指標建立傳感器優化部署模型。

1.1 一般區域覆蓋率

一般區域覆蓋率，定義為傳感器覆蓋區域總面積與一般區域面積的比值，即：

式中，Si為第i部傳感器的探測區域，S為給定的一般區域，N為傳感器總數，ρ∈［0，1］表示覆蓋率。

1.2 覆蓋重數

覆蓋重數說明傳感器探測區域覆蓋的重數。它與覆蓋率并不矛盾，只是兩者關注的側重點不同。覆蓋率關注的是目標區域整體的覆蓋情況，而覆蓋重數側重于局部的重點觀測情況［3］。

覆蓋重數定義為：一般來說，覆蓋重數超過3時，不會明顯增大傳感器的聯合探測概率。本文要求重點區域覆蓋重數λarea≥2，一般區域的覆蓋重數λ一般≥1。

1.3 重點區域覆蓋率

重點區域覆蓋率是指二重覆蓋條件下，傳感器對重點區域的覆蓋率，即：

式中，Sarea為重點區域，Sarea2為二重覆蓋下傳感器覆蓋的區域，θ為重點區域的覆蓋率；約束條件表示Sarea2區域至少為二重覆蓋。

1.4 傳感器資源利用率

為了節約傳感器資源，需要將傳感器資源限制在感興趣的區域內。

資源利用率定義為：

1.5 傳感器優化部署模型

利用式（1）～式（4）可以得出，傳感器優化部署模型為：式中q1、q2、q3為權重系數，且q1+q2+q3=1；C則為傳感器部署優化效能。

2　基于遺傳算法的模型求解

遺傳算法（Genetic Algorithm）是一類借鑒生物界進化規律演化而來的隨機優化搜索方法［4-5］。原理是通過生物選擇、遺傳和變異等操作，維持優秀基因并促使群體進化，從而獲取最優解。目前，遺傳算法已被廣泛應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域［6］。

針對傳感器優化部署這一復雜問題，對遺傳算法的編碼、選擇、變異等方法進行改進，具體如下。

2.1 編碼

影響傳感器i（i=1，2，…，N）覆蓋范圍的參數有：工作狀態oi、傳感器位置（xi， yi）、作用半徑ri等。其中，ri屬于傳感器的固有特性，可以預先獲知，不需要編碼。

為了精確獲取傳感器部署位置，需選擇混合編碼的方法，即工作狀態oi采用二進制編碼，表示傳感器開關機狀態；傳感器位置（xi， yi）采用實數編碼。因此，一個基因包括三個分量Gk=（xi，yi，oi）；個體由N個基因組成，即I=（G1，G2，…GN）；種群P=｛I1，I2，…，Ik｝，其中K為種群大小。

2.2 適應度函數

傳感器優化部署模型的適應性函數定義如下：

2.3 選擇

為了實現快速收斂，本文采用精英選擇和比例選擇相結合的方法，即通過精英選擇將群體中最優秀的個體不經選擇環節直接進入下一代，而其余個體仍然通過比例選擇法得到。

比例選擇時，需要計算所有個體的適應度函數，以確定其被選擇的概率和染色體累積概率。假設第k個個體的適應度為fk，則個體選擇概率pk和染色體累積概率qk的計算方法為：

2.4 交叉

針對混合編碼方案，交叉方法如下：

（1）以一定的概率選擇兩個需要交叉的個體Ir、Is；

（2）在交叉個體中，隨機選擇兩個需要交叉的基因Gm、Gn；

（3）對基因中的工作狀態o采用單點交叉方法；對于基因中的x值采用算術交叉方法，即：

式中a為比例因子。

同理，y值通過相同的方法進行交叉。

2.5 變異

變異操作類似于交叉操作，先是隨機選擇一個個體，然后以一定的突變概率選擇基因，最后對基因進行變異。對工作狀態o采用取反操作，對基因中的x值則采用如下的計算變異公式：

式（9）中，Lxmin為一般區域x方向的起點，Lxman為一般區域x方向的終點。

同樣地，y值采用相同的方法進行變異。

3　仿真實驗

假設由10個傳感器組成的傳感器網絡對某作戰區域進行探測。傳感器作用距離為25 km；一般區域為100 km×100 km的方形區域；重點區域是以（60，60）為中心，大小為40 km×40 km的方形區域。

遺傳算法的參數設置如下：初始種群大小為50；交叉概率為0.8；變異概率為0.15；模型權重系數q1=0.30，q2=0.50，q3=0.2。遺傳算法停止迭代的條件是：一般區域覆蓋率ρ≥90%，重點區域覆蓋率θ≥99%，迭代次數小于50。隨機選取個體初值，算法經過46次迭代后收斂，獲取傳感器的部署參數，如表1所示。從表1可知，只需開機8個傳感器就能完成探測任務。一般區域和重點區域的覆蓋情況如圖1所示，其中一般區域覆蓋率達到了92%，重點區域覆蓋率達到了99%。可見，遺傳算法能夠很好地解算傳感器部署問題。覆蓋率隨迭代次數變化的曲線，如圖2所示。由圖2可見，重點區域的覆蓋率收斂較快，這是因為傳感器優化部署模型中重點區域的覆蓋率項被賦予了較大權值。

實驗中，還采用基于二進制編碼的遺傳算法對傳感器優化部署模型進行了解算，即組成基因的三個分量都使用二進制來表示，其中工作狀態oi使用1位二進制碼表示，傳感器位置xi和yi分別使用16位二進制碼表示，共同組成33位二進制編碼串。隨機設置個體初值，經過50次迭代后算法停止，獲取傳感器的部署參數，如表1所示。此時，9個傳感器開機探測，一般區域覆蓋率只達到了85.1%，重點區域覆蓋率達到了95.3%。類似地，從圖2看出，二進制編碼的遺傳算法與本文方法相比，收斂速度較慢。

表1　傳感器部署情況

圖1　傳感器覆蓋情況

圖2　覆蓋率變化曲線

4　結 語

傳感器網絡中，如何有效部署傳感器成為傳感器網絡技術研究的一個重要方向。本文從覆蓋率、覆蓋重數、資源利用率等方面開展研究，建立了傳感器網絡優化部署模型，提出了一種改進的遺傳算法，實現了模型的快速、有效解算。仿真實驗表明，該模型不僅能夠對重點區域進行重點探測，提高目標探測概率，而且能夠有效利用傳感器資源，從而為實際的傳感器部署提供參考。

［1］ Ghosh A，Das S K.Review：Coverage and Connectivity Issues in Wireless Sensor Networks：A Survey［J］. Pervasive and Mobile Computing，2008，4（03）：303-334.

［2］ Dhillon S S，Chakrabarty K.Sensor Placemen for Effective coverage and Surveillance in Distributed Sensor Networks［C］.Proc of IEEE Wireless Communications and Networking conf，2003：1609-1614.

［3］ Huang C，Tseng Y.The Coverage Problem in a Wireless Sensor Network［C］.Proc of the 2nd ACM International Conference on Wireless Sensor Networks and Applications，2003：115-121.

［4］ 夏磊，俞能海.基于遺傳算法的小衛星任務調度［J］.通信技術，2013，46（11）：64-68. XIA Lei，YU Neng-hai.Genetic Algorithm based Small Satellites Range Scheduling［J］.Communications Technology，2013，46（11）：64-68.

［5］ 狄海進，高璇.遺傳模擬退火算法在多目標分配中的應用［J］.指揮信息系統與技術，2012，3（06）：22-24. DI Hai-jin，GAO Xuan.Application of Genetic Simulated Annealing Algorithm in Multi-target Assignment［J］.Command Information System and Technology，2012，3（06）：22-24.

［6］ 鄭世明，苗壯，董磊.基于云遺傳算法的防空火力優化分配［J］.指揮信息系統與技術，2011，2（01）：21-26. ZHENG Shi-ming，MIAO Zhuang，DONG Lei.Optimization of the Allocation of Targets of Air Defense based on Cloud-Model Genetic Algorithms［J］.Command Information System and Technology，2011，2（01）：21-26.

陳升來（1978—），男，博士，高級工程師，主要研究方向為總體技術、傳感器網絡控制技術；

陸 宏（1980—），女，本科，高級工程師，主要研究方向為傳感器網絡控制與仿真技術；

李 濤（1973—），男，博士，高級工程師，主要研究方向為傳感器網絡控制與數據融合技術。

Optimal Deployment Method of Sensors based on Genetic Algorithm

CHEN Sheng-lai， LU Hong， LI Tao
（The 28th Research Institute of China Electronics Technology Group Corporation， Nanjing Jiangsu 210007， China）

Optimal deployment method of sensors based on genetic algorithm is proposed， thus to solve the problem of sensors optimal deployment. With coverage ratio， resource utilization and coverage coefficient as the evaluation indexes， the optimal deployment model is established， and at the same time the solution to sensor deployment model based genetic algorithm designed. Simulation results indicate that the proposed method for optimal sensor network deployment is feasible and effective， with ordinary area coverage percentage reaching 92%， and the important area coverage percentage reaching 99% after genetic algorithm iteration. In addition， the proposed method is fairly high in convergence speed and sensor utilization ratio as compared with the traditional methods.

genetic algorithm； optimal deployment； hybrid encoding； sensor network

TP393.04

A

1002-0802（2016）-10-1360-04

10.3969/j.issn.1002-0802.2016.10.018

2016-06-07；

2016-09-23

data：2016-06-07；Revised data：2016-09-23