陳升來，陸 宏，李 濤

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

基于遺傳算法的傳感器優(yōu)化部署方法研究*

陳升來，陸 宏，李 濤

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

針對(duì)傳感器優(yōu)化部署問題，提出了基于遺傳算法的傳感器優(yōu)化部署方法。以空間覆蓋率、覆蓋重?cái)?shù)、資源利用率為評(píng)價(jià)指標(biāo)，構(gòu)建傳感器優(yōu)化部署模型，提出了基于遺傳算法的傳感器部署模型求解方法。仿真實(shí)驗(yàn)表明，提出的方法能夠?qū)崿F(xiàn)傳感器優(yōu)化部署，遺傳算法經(jīng)過迭代后，一般區(qū)域覆蓋率達(dá)到了92%，重點(diǎn)區(qū)域覆蓋率達(dá)到了99%。此外，與基于二進(jìn)制編碼的遺傳算法相比，該方法具有算法收斂快、傳感器資源利用率高等優(yōu)點(diǎn)。

遺傳算法；優(yōu)化部署；混合編碼；傳感器網(wǎng)絡(luò)

0　引 言

傳感器組網(wǎng)是實(shí)施情報(bào)感知的基礎(chǔ)。在網(wǎng)絡(luò)中心戰(zhàn)中，地理上分散的傳感器通過有線或無線網(wǎng)絡(luò)組成網(wǎng)絡(luò)化探測(cè)系統(tǒng)，對(duì)作戰(zhàn)目標(biāo)進(jìn)行協(xié)同感知和融合處理，生成實(shí)時(shí)或近實(shí)時(shí)情報(bào)信息，為作戰(zhàn)部隊(duì)、武器系統(tǒng)提供實(shí)時(shí)戰(zhàn)場(chǎng)態(tài)勢(shì)。

為發(fā)揮網(wǎng)絡(luò)化探測(cè)系統(tǒng)整體效能，提高探測(cè)系統(tǒng)的檢測(cè)概率，必須對(duì)有限的傳感器資源進(jìn)行優(yōu)化部署及合理使用［1-2］，實(shí)現(xiàn)對(duì)戰(zhàn)場(chǎng)空間的全方位探測(cè)。

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

1　模型建立

在軍事領(lǐng)域，根據(jù)重要性的不同，傳感器探測(cè)區(qū)域分為一般區(qū)域和重點(diǎn)區(qū)域。前者側(cè)重于目標(biāo)監(jiān)視，后者側(cè)重于目標(biāo)跟蹤。由于目標(biāo)監(jiān)視和目標(biāo)跟蹤的側(cè)重點(diǎn)不同，故對(duì)傳感器探測(cè)提出了不同的要求：第一，為了達(dá)到警戒效果，要盡可能覆蓋一般區(qū)域；第二，為了確保重點(diǎn)區(qū)域的目標(biāo)都能被監(jiān)視和跟蹤，要完全覆蓋重點(diǎn)區(qū)域；第三，為了提升重點(diǎn)區(qū)域目標(biāo)跟蹤效能和探測(cè)概率，要對(duì)重點(diǎn)區(qū)域?qū)嵤┒嘀馗采w；第四，為了提高傳感器資源效費(fèi)比，減少電磁輻射，參與探測(cè)的傳感器數(shù)量要盡可能少，避免傳感器過度冗余。

針對(duì)上述要求，利用一般區(qū)域覆蓋率、覆蓋重?cái)?shù)、重點(diǎn)區(qū)域覆蓋率、傳感器資源利用率等指標(biāo)建立傳感器優(yōu)化部署模型。

1.1 一般區(qū)域覆蓋率

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

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

1.2 覆蓋重?cái)?shù)

覆蓋重?cái)?shù)說明傳感器探測(cè)區(qū)域覆蓋的重?cái)?shù)。它與覆蓋率并不矛盾，只是兩者關(guān)注的側(cè)重點(diǎn)不同。覆蓋率關(guān)注的是目標(biāo)區(qū)域整體的覆蓋情況，而覆蓋重?cái)?shù)側(cè)重于局部的重點(diǎn)觀測(cè)情況［3］。

覆蓋重?cái)?shù)定義為：一般來說，覆蓋重?cái)?shù)超過3時(shí)，不會(huì)明顯增大傳感器的聯(lián)合探測(cè)概率。本文要求重點(diǎn)區(qū)域覆蓋重?cái)?shù)λarea≥2，一般區(qū)域的覆蓋重?cái)?shù)λ一般≥1。

1.3 重點(diǎn)區(qū)域覆蓋率

重點(diǎn)區(qū)域覆蓋率是指二重覆蓋條件下，傳感器對(duì)重點(diǎn)區(qū)域的覆蓋率，即：

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

1.4 傳感器資源利用率

為了節(jié)約傳感器資源，需要將傳感器資源限制在感興趣的區(qū)域內(nèi)。

資源利用率定義為：

1.5 傳感器優(yōu)化部署模型

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

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

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

針對(duì)傳感器優(yōu)化部署這一復(fù)雜問題，對(duì)遺傳算法的編碼、選擇、變異等方法進(jìn)行改進(jìn)，具體如下。

2.1 編碼

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

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

2.2 適應(yīng)度函數(shù)

傳感器優(yōu)化部署模型的適應(yīng)性函數(shù)定義如下：

2.3 選擇

為了實(shí)現(xiàn)快速收斂，本文采用精英選擇和比例選擇相結(jié)合的方法，即通過精英選擇將群體中最優(yōu)秀的個(gè)體不經(jīng)選擇環(huán)節(jié)直接進(jìn)入下一代，而其余個(gè)體仍然通過比例選擇法得到。

比例選擇時(shí)，需要計(jì)算所有個(gè)體的適應(yīng)度函數(shù)，以確定其被選擇的概率和染色體累積概率。假設(shè)第k個(gè)個(gè)體的適應(yīng)度為fk，則個(gè)體選擇概率pk和染色體累積概率qk的計(jì)算方法為：

2.4 交叉

針對(duì)混合編碼方案，交叉方法如下：

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

（2）在交叉?zhèn)€體中，隨機(jī)選擇兩個(gè)需要交叉的基因Gm、Gn；

（3）對(duì)基因中的工作狀態(tài)o采用單點(diǎn)交叉方法；對(duì)于基因中的x值采用算術(shù)交叉方法，即：

式中a為比例因子。

同理，y值通過相同的方法進(jìn)行交叉。

2.5 變異

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

式（9）中，Lxmin為一般區(qū)域x方向的起點(diǎn)，Lxman為一般區(qū)域x方向的終點(diǎn)。

同樣地，y值采用相同的方法進(jìn)行變異。

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

假設(shè)由10個(gè)傳感器組成的傳感器網(wǎng)絡(luò)對(duì)某作戰(zhàn)區(qū)域進(jìn)行探測(cè)。傳感器作用距離為25 km；一般區(qū)域?yàn)?00 km×100 km的方形區(qū)域；重點(diǎn)區(qū)域是以（60，60）為中心，大小為40 km×40 km的方形區(qū)域。

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

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

表1　傳感器部署情況

圖1　傳感器覆蓋情況

圖2　覆蓋率變化曲線

4　結(jié) 語

傳感器網(wǎng)絡(luò)中，如何有效部署傳感器成為傳感器網(wǎng)絡(luò)技術(shù)研究的一個(gè)重要方向。本文從覆蓋率、覆蓋重?cái)?shù)、資源利用率等方面開展研究，建立了傳感器網(wǎng)絡(luò)優(yōu)化部署模型，提出了一種改進(jìn)的遺傳算法，實(shí)現(xiàn)了模型的快速、有效解算。仿真實(shí)驗(yàn)表明，該模型不僅能夠?qū)χ攸c(diǎn)區(qū)域進(jìn)行重點(diǎn)探測(cè)，提高目標(biāo)探測(cè)概率，而且能夠有效利用傳感器資源，從而為實(shí)際的傳感器部署提供參考。

［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］ 夏磊，俞能海.基于遺傳算法的小衛(wèi)星任務(wù)調(diào)度［J］.通信技術(shù)，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ìn)，高璇.遺傳模擬退火算法在多目標(biāo)分配中的應(yīng)用［J］.指揮信息系統(tǒng)與技術(shù)，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］ 鄭世明，苗壯，董磊.基于云遺傳算法的防空火力優(yōu)化分配［J］.指揮信息系統(tǒng)與技術(shù)，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—），男，博士，高級(jí)工程師，主要研究方向?yàn)榭傮w技術(shù)、傳感器網(wǎng)絡(luò)控制技術(shù)；

陸 宏（1980—），女，本科，高級(jí)工程師，主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)控制與仿真技術(shù)；

李 濤（1973—），男，博士，高級(jí)工程師，主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)控制與數(shù)據(jù)融合技術(shù)。

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