夏化冰+潘偉

收稿日期：2013-12-29

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（60974091）

作者簡(jiǎn)介：夏化冰（1971—），男，安徽合肥人，副教授，碩士，研究方向：炮兵通信指揮、遺傳算法應(yīng)用等。

通訊聯(lián)系人，E-mail：pan.w@126.com

文章編號(hào)：1003-6199（2014）03-0035-04

摘 要：針對(duì)節(jié)點(diǎn)高密度部署的炮兵通信網(wǎng)絡(luò)中優(yōu)化工作節(jié)點(diǎn)集的選取問題，提出一種基于參數(shù)可變遺傳算法的覆蓋控制優(yōu)化方法。設(shè)計(jì)了密度檢測(cè)機(jī)制優(yōu)化初始種群，并設(shè)計(jì)了即考慮到進(jìn)化代數(shù)對(duì)算法影響，又考慮到每代中不同個(gè)體適應(yīng)度對(duì)算法作用的自適應(yīng)交叉概率和變異概率。仿真實(shí)驗(yàn)及分析表明，該優(yōu)化方法快速有效地實(shí)現(xiàn)了工作節(jié)點(diǎn)數(shù)目少、節(jié)點(diǎn)集覆蓋率高的工作節(jié)點(diǎn)集的選取，可有效地降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

關(guān)鍵詞：炮兵通信網(wǎng)絡(luò)；覆蓋；工作節(jié)點(diǎn)集；參數(shù)可變遺傳算法

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A

Optimal Coverage Strategy Based on Alterable Parameter

Genetic Algorithm in Artillery Commutation Networks

Xia Hua-bing， Pan Wei

（Shenyang Artillery Academy，Shenyang，Liaoning 110867，China）

Abstract：An optimal coverage strategy based on adaptive genetic algorithm in wireless sensor networks is proposed for solving the problem of selecting the optimal coverage set of nodes for artillery commutation networks with high density nodes. The mechanism of density detection is designed to optimize the initial population. The adaptive crossover probability and adaptive mutation probability are proposed， which consider the influence of every generation to algorithm and the effect individual fitness in every generation. Simulation and analysis results show that the optimal coverage set of nodes with less nodes and high coverage percentage is achieved by the proposed algorithm. Under the condition， sleeping chance is ensured adequately， which decreases the energy expenditure effectively and prolongs the lifetime of the network.

Key words：artillery commutation networks；coverage；coverage set of nodes；alterable parameter genetic algorithm

1 引 言

未來信息化條件下，炮兵作為陸軍的火力突擊骨干力量，將擔(dān)負(fù)更加繁重的作戰(zhàn)任務(wù)，這要求炮兵部隊(duì)必須具備良好的信息獲取及處理能力，以便控制復(fù)雜的信息化戰(zhàn)場(chǎng)。炮兵群通信系統(tǒng)由通信網(wǎng)和炮兵通信節(jié)點(diǎn)組成，主要應(yīng)用于各級(jí)指揮單元和行動(dòng)單元，完成信息的傳輸，是聯(lián)接指揮控制等分系統(tǒng)的紐帶[1]。

網(wǎng)絡(luò)覆蓋是炮兵通信網(wǎng)絡(luò)的基本問題之一，反映了網(wǎng)絡(luò)對(duì)被監(jiān)測(cè)區(qū)域或目標(biāo)對(duì)象物理信息的感知能力。網(wǎng)絡(luò)覆蓋問題近年來受到廣泛研究[2]，由于通信節(jié)點(diǎn)的高密度部署特性，部分節(jié)點(diǎn)間的覆蓋區(qū)域完全或部分交迭，如果所有節(jié)點(diǎn)同時(shí)工作會(huì)造成大量的能量消耗，縮短網(wǎng)絡(luò)生存時(shí)間。因此，如何在實(shí)現(xiàn)極大化網(wǎng)絡(luò)覆蓋的同時(shí)采用盡量少的節(jié)點(diǎn)組成優(yōu)化工作節(jié)點(diǎn)集，和調(diào)度各個(gè)節(jié)點(diǎn)集輪流工作是解決炮兵通信網(wǎng)絡(luò)能量有限與延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間之間矛盾的重要手段[3]。

2 問題建模

2.1 相關(guān)假設(shè)

目標(biāo)區(qū)域A為二維矩形平面，N個(gè)通信網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署于其中，網(wǎng)絡(luò)中含有一個(gè)具有較強(qiáng)計(jì)算能力的匯聚（sink）節(jié)點(diǎn)，用于工作節(jié)點(diǎn)集選取的計(jì)算，且sink節(jié)點(diǎn)可以獲得部署于網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的位置信息；使用全向天線，節(jié)點(diǎn)的通信范圍是以節(jié)點(diǎn)為圓心，半徑為Rc的圓形區(qū)域，節(jié)點(diǎn)感知半徑為Rs且Rc=2Rs，這樣保證了網(wǎng)絡(luò)的連通性，在此基礎(chǔ)上的覆蓋問題包含了連通問題；位于節(jié)點(diǎn)一倍感知半徑內(nèi)的鄰居節(jié)點(diǎn)為第一類鄰居節(jié)點(diǎn)，位于一倍感知半徑與兩倍感知半徑之間的節(jié)點(diǎn)為第二類鄰居節(jié)點(diǎn)；若點(diǎn)p與節(jié)點(diǎn)si之間的歐式距離d（si， p）滿足d（si， p）≤Rs，則點(diǎn)p被si覆蓋，且通信網(wǎng)絡(luò)節(jié)點(diǎn)間互相獨(dú)立。

2.2問題模型

炮兵通信網(wǎng)絡(luò)優(yōu)化覆蓋問題是一個(gè)典型的目標(biāo)優(yōu)化問題。網(wǎng)絡(luò)有效覆蓋率、工作節(jié)點(diǎn)數(shù)目是衡量工作節(jié)點(diǎn)集選取的重要指標(biāo)，綜合考慮二者設(shè)計(jì)適值函數(shù)F（x）與優(yōu)化模型Fopt分別為

F（x）=α×Pcov +β×xsize3Rs×2×ysize3Rsnumworknodes（1）

Fopt=max F（x）（2）

式中，α，β為調(diào)節(jié)系數(shù)，其值取決于網(wǎng)絡(luò)設(shè)計(jì)者對(duì)網(wǎng)絡(luò)性能指標(biāo)的綜合要求，Pcov為工作節(jié)點(diǎn)集的有效覆蓋率，numworknodes為工作節(jié)點(diǎn)集的節(jié)點(diǎn)數(shù)目，xsize為目標(biāo)區(qū)域長(zhǎng)度，ysize為目標(biāo)區(qū)域?qū)挾?，符?hào)[ ]表示取整，xsize3Rs×2×ysize3Rs為覆蓋目標(biāo)區(qū)域所需要的最少節(jié)點(diǎn)個(gè)數(shù)[4]。

為了計(jì)算Pcov，將目標(biāo)區(qū)域劃分為m×n個(gè)網(wǎng)格，以網(wǎng)格中心被覆蓋的程度代表網(wǎng)格被覆蓋的程度，△s表示一個(gè)網(wǎng)格的面積，As表示矩形的面積，則有

Δs=Asm×n=xsize×ysizem×n（3）

網(wǎng)格G（xl， yω）被節(jié)點(diǎn)i覆蓋的概率為

pRi=Pc（xl，yω，i）=

1，（xl-xi）2+（yω-yi）2≤Rs

0，others（4）

式中，（xl， yω）為網(wǎng)格中心點(diǎn)坐標(biāo)。

節(jié)點(diǎn)間彼此獨(dú)立，則有

RRi∪Rj=1-pi∪j=

1-pipj （5）

網(wǎng)格被節(jié)點(diǎn)集覆蓋的概率為

p∪numworknodesi=1R=1-p∩numworknodesi=1i=

1-∏numworknodesi=1Pc（xl，yω，i）（6）

則工作節(jié)點(diǎn)集的有效覆蓋率Pcov為

Pcov =節(jié)點(diǎn)集覆蓋的面積總面積=

∑ml=1∑mω=1p∪numworknodesi=1RΔsAs（7）

3 遺傳算法求解步驟

3.1 初始種群優(yōu)化

1）密度檢測(cè)

節(jié)點(diǎn)計(jì)算由第一類鄰居節(jié)點(diǎn)覆蓋形成的近似扇形區(qū)域?qū)?yīng)的圓心角并集θ，若θ=360°，該點(diǎn)處密度較大，節(jié)點(diǎn)冗余；若θ=0°，該點(diǎn)處密度過小；若θ∈[0°， 360°]，計(jì)算第一類鄰居節(jié)點(diǎn)中距離該點(diǎn)最近距離α及圓心角并集形成扇形的邊與節(jié)點(diǎn)感知圓周的交點(diǎn)，在扇形兩邊上分別取得與對(duì)應(yīng)交點(diǎn)距離為α的關(guān)鍵點(diǎn)，由關(guān)鍵點(diǎn)及交點(diǎn)組成判定點(diǎn)，若判定點(diǎn)能夠被第二類鄰居節(jié)點(diǎn)覆蓋，則該節(jié)點(diǎn)處密度較大，該點(diǎn)冗余。密度檢測(cè)如圖1所示，圖1（a）中節(jié)點(diǎn)A為密度檢測(cè)點(diǎn)，θ為第一類鄰居節(jié)點(diǎn)覆蓋形成的近似扇形區(qū)域?qū)?yīng)的圓心角并集，G、H為近似扇形的兩邊與點(diǎn)A感知圓周的交點(diǎn)，G1、H1為關(guān)鍵點(diǎn)，G、H、G1、H1構(gòu)成判定點(diǎn)；若第一類鄰居節(jié)點(diǎn)覆蓋形成的區(qū)域由兩部分獨(dú)立的近似扇形區(qū)域構(gòu)成，即θ=θ1∪θ2，如圖1（b）所示，對(duì)兩組判定點(diǎn)G、H、G1、H1，E、F、E1、F1進(jìn)行密度檢測(cè)原理同上。

2）優(yōu)化過程

密度檢測(cè)識(shí)別出冗余節(jié)點(diǎn)并獲得所有節(jié)點(diǎn)被鄰居節(jié)點(diǎn)覆蓋的圓心角度后，根據(jù)密度檢測(cè)的結(jié)果及節(jié)點(diǎn)間的位置關(guān)系設(shè)定節(jié)點(diǎn)及鄰居節(jié)點(diǎn)的工作概率，保證初始化種群的質(zhì)量，使算法在較少的迭代次數(shù)獲得較高的適值個(gè)體。優(yōu)化過程如下（c為優(yōu)化比例，G為初始種群規(guī)模）：隨機(jī)初始化G（1-c）個(gè)隨機(jī)個(gè)體，對(duì)個(gè)體中節(jié)點(diǎn)進(jìn)行密度檢測(cè)，若節(jié)點(diǎn)非冗余，且密度檢測(cè)獲得的圓心角為0，則將節(jié)點(diǎn)工作概率置1；若密度檢測(cè)獲得的圓心角非0，找出該節(jié)點(diǎn)的第一類鄰居節(jié)點(diǎn)，并根據(jù)圓心角及第一類鄰居節(jié)點(diǎn)的數(shù)目設(shè)置節(jié)點(diǎn)工作概率；若密度檢測(cè)得到節(jié)點(diǎn)冗余，則設(shè)置節(jié)點(diǎn)工作概率為0.5；經(jīng)過工作概率設(shè)置后，若節(jié)點(diǎn)被選為工作，繼續(xù)檢查該節(jié)點(diǎn)第一類鄰居節(jié)點(diǎn)的工作狀態(tài)，若第一類鄰居節(jié)點(diǎn)工作概率非1，相應(yīng)降低第一類鄰居節(jié)點(diǎn)的工作概率，完成每個(gè)隨機(jī)個(gè)體中所有節(jié)點(diǎn)及第一類鄰居節(jié)點(diǎn)的工作概率設(shè)置，即完成個(gè)體優(yōu)化；循環(huán)直至優(yōu)化個(gè)體比例達(dá)到要求。

3.2 遺傳操作

遺傳操作包括選擇、交叉、變異三種操作算子，本文采用標(biāo)準(zhǔn)遺傳操作，選擇操作是排序選擇+最佳個(gè)體保存法，交叉操作是依據(jù)交叉概率的單點(diǎn)交叉，變異操作是依據(jù)變異概率的單基因突變。選擇操作是遺傳算法的基礎(chǔ)，變異操作是遺傳算法的核心，交叉操作是遺傳算法的補(bǔ)充[5]。

3.3 交叉概率的自適應(yīng)確定

交叉算子在遺傳操作中起核心作用，主要用來產(chǎn)生新個(gè)體，實(shí)現(xiàn)算法的全局搜索能力。從群體整體進(jìn)化過程來看，交叉概率應(yīng)該能隨進(jìn)化過程逐漸變小，到最后趨于某一穩(wěn)定值，以避免對(duì)算法后期的穩(wěn)定性造成沖擊而導(dǎo)致算法不能收斂，或收斂過程加長(zhǎng)；而從產(chǎn)生新個(gè)體的角度來看，群體中的所有個(gè)體在交叉操作上應(yīng)該具有同等地位，相同概率，從而使GA在搜索空間具有各個(gè)方向的勻性[6]。因此，本文設(shè)計(jì)了與進(jìn)化代數(shù)相關(guān)的交叉概率：

Pc=11+eαG+β（8）

其中，G為進(jìn)化代數(shù)，α、β為定常系數(shù)，α代表交叉概率的變化曲率，β代表交叉概率的收斂極限。

3.4 變異概率的自適應(yīng)確定

變異算子在遺傳操作中起輔助作用，主要用來維持群體多樣性，防止出現(xiàn)未成熟收斂。在算法早期，群體中個(gè)體多樣性豐富，此時(shí)的變異概率應(yīng)該小些，以提高算法的運(yùn)行速度；而隨著進(jìn)化的進(jìn)行，個(gè)體越來越向適應(yīng)度高的個(gè)體靠近，致使個(gè)體越來越單一，此時(shí)的變異概率就應(yīng)該大些，以維持群體的多樣性。同樣的原因，同一代群體中個(gè)體的變異概率應(yīng)該隨個(gè)體的優(yōu)劣而變化，即加大優(yōu)質(zhì)個(gè)體變異概率。為此設(shè)計(jì)了如下的與遺傳進(jìn)化代數(shù)和個(gè)體適應(yīng)度相關(guān)的自適應(yīng)變異概率：

Pm=k11+e-αG-ffmax-f>

k2f≤ （9）

其中，f為當(dāng)前個(gè)體適應(yīng)度值，fmax為當(dāng)前群體中最大個(gè)體適應(yīng)度值，為當(dāng)前群體平均適應(yīng)度值，G為進(jìn)化代數(shù)，α、k1、k2為定常系數(shù)。α代表變異概率的變化速度；k1與具體問題有關(guān)，是為保證遺傳算法不退化為隨機(jī)搜索，pm所能取到的最大值；k2為一個(gè)比較小的變異概率，一般取0.001。

3.5 實(shí)施步驟

初始化覆蓋控制優(yōu)化中各參數(shù)，包括節(jié)點(diǎn)數(shù)目N，種群優(yōu)化比例c，遺傳算法的種群規(guī)模G，工作節(jié)點(diǎn)集的有效覆蓋率閾值Pcovm。

步驟1 采用二進(jìn)制N位編碼方式對(duì)初始種群進(jìn)行編碼，0表示節(jié)點(diǎn)不工作，1表示節(jié)點(diǎn)工作，每個(gè)工作節(jié)點(diǎn)集即種群中每個(gè)個(gè)體用N位編碼表示；根據(jù)密度檢測(cè)進(jìn)行初始種群的優(yōu)化；

步驟2 根據(jù)式（1）計(jì)算種群內(nèi)個(gè)體適值、判斷終止條件，若滿足，則轉(zhuǎn)入步驟5，否則轉(zhuǎn)入步驟3；

步驟3 遺傳操作；

步驟4 構(gòu)成下一代種群個(gè)體，轉(zhuǎn)入步驟2；

步驟5 獲得優(yōu)化工作節(jié)點(diǎn)集，覆蓋控制結(jié)束。

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

采用MATLAB仿真平臺(tái)，對(duì)在GA、采用密度檢測(cè)機(jī)制優(yōu)化種群的GA（GA+密度檢測(cè)）、APGA三種算法下工作節(jié)點(diǎn)集選取的性能進(jìn)行驗(yàn)證，仿真實(shí)驗(yàn)中各參數(shù)采用通信網(wǎng)絡(luò)研究的通用設(shè)置。

APGA比GA算法的復(fù)雜度高，但APGA經(jīng)過合理設(shè)計(jì)后優(yōu)化性能優(yōu)于GA算法且優(yōu)化速度較快。進(jìn)行50次獨(dú)立的隨機(jī)拓?fù)鋵?shí)驗(yàn)，得到APGA與GA算法的平均最優(yōu)適值、平均計(jì)算時(shí)間和平均迭代次數(shù)關(guān)系，如表1所示。

表1 50次獨(dú)立優(yōu)化實(shí)驗(yàn)的平均性能

可見，APGA的優(yōu)化效果優(yōu)于GA算法，且優(yōu)化速度較快。這主要是由于GA算法具有容易陷入局部最優(yōu)的特點(diǎn)，參數(shù)可變遺傳操作可以跳出局部極小值陷阱和避免循環(huán)搜索，從而使得APGA算法快速的獲得了更優(yōu)的工作節(jié)點(diǎn)集。

圖2給出優(yōu)化工作節(jié)點(diǎn)集適值的性能，可見，在遺傳迭代穩(wěn)定后，APGA算法的適值總體性能明顯優(yōu)于其它兩種算法，大約可以高出GA算法50%，高出GA+密度檢測(cè)算法28%。算法的全局尋優(yōu)能力更強(qiáng)，且優(yōu)化速度較快，有效地減少了算法迭代次數(shù)，使得算法以較少的迭代次數(shù)獲得了更優(yōu)的工作節(jié)點(diǎn)集，有益于降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

圖3給出優(yōu)化工作節(jié)點(diǎn)集中工作節(jié)點(diǎn)數(shù)目的性能，可見，在滿足有效覆蓋率98%閾值條件下，APGA算法下選取的工作節(jié)點(diǎn)集中工作節(jié)點(diǎn)數(shù)目最少，約為GA的50%，約為GA+密度檢測(cè)的75%。APGA算法獲得了最少的工作節(jié)點(diǎn)，有利于充分休眠冗余節(jié)點(diǎn)，從而降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

5 結(jié) 語

本文以網(wǎng)絡(luò)覆蓋率、工作節(jié)點(diǎn)數(shù)目構(gòu)成優(yōu)化目標(biāo)，研究了節(jié)點(diǎn)高密度部署的炮兵通信網(wǎng)絡(luò)中優(yōu)化工作節(jié)點(diǎn)集選取的問題，提出了一種基于參數(shù)可變遺傳算法的覆蓋控制優(yōu)化方法。理論分析和實(shí)驗(yàn)數(shù)據(jù)表明，該方法通過密度檢測(cè)機(jī)制優(yōu)化了種群質(zhì)量，提高了優(yōu)化速度，通過自適應(yīng)遺傳操作增強(qiáng)了全局尋優(yōu)能力，從而快速有效地實(shí)現(xiàn)了工作節(jié)點(diǎn)數(shù)目少、節(jié)點(diǎn)集覆蓋率高的工作節(jié)點(diǎn)集的優(yōu)化選取，在較高的覆蓋質(zhì)量條件下休眠了更多的冗余節(jié)點(diǎn)，有效地降低了能耗，延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

參考文獻(xiàn)

[1] 劉樹海. 軍隊(duì)指揮自動(dòng)化系統(tǒng)[M]. 北京：解放軍出版社， 2002.

[2] WANG X， WANG S. An improved particle filter for target tracking in sensor system [J].Sensors，2007，7（1）：144-156.

[3] WANG X， MA J J， WANG S. Prediction-based dynamic power optimization in wireless sensor networks [J].Sensors，2007，7 （3）：251-266.

[4] JIA J，CHEN J，CHANG G R. Efficient cover set selection in wireless sensor networks[J].Acta Automatica Sinica，2008，34（9）：1157-1162.

[5] 潘偉. 基于參數(shù)可變遺傳算法的多普勒雷達(dá)目標(biāo)識(shí)別方法 [J]. 計(jì)算技術(shù)與自動(dòng)化， 2011， 30（2）： 105- 108.

步驟1 采用二進(jìn)制N位編碼方式對(duì)初始種群進(jìn)行編碼，0表示節(jié)點(diǎn)不工作，1表示節(jié)點(diǎn)工作，每個(gè)工作節(jié)點(diǎn)集即種群中每個(gè)個(gè)體用N位編碼表示；根據(jù)密度檢測(cè)進(jìn)行初始種群的優(yōu)化；

步驟2 根據(jù)式（1）計(jì)算種群內(nèi)個(gè)體適值、判斷終止條件，若滿足，則轉(zhuǎn)入步驟5，否則轉(zhuǎn)入步驟3；

步驟3 遺傳操作；

步驟4 構(gòu)成下一代種群個(gè)體，轉(zhuǎn)入步驟2；

步驟5 獲得優(yōu)化工作節(jié)點(diǎn)集，覆蓋控制結(jié)束。

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

采用MATLAB仿真平臺(tái)，對(duì)在GA、采用密度檢測(cè)機(jī)制優(yōu)化種群的GA（GA+密度檢測(cè)）、APGA三種算法下工作節(jié)點(diǎn)集選取的性能進(jìn)行驗(yàn)證，仿真實(shí)驗(yàn)中各參數(shù)采用通信網(wǎng)絡(luò)研究的通用設(shè)置。

APGA比GA算法的復(fù)雜度高，但APGA經(jīng)過合理設(shè)計(jì)后優(yōu)化性能優(yōu)于GA算法且優(yōu)化速度較快。進(jìn)行50次獨(dú)立的隨機(jī)拓?fù)鋵?shí)驗(yàn)，得到APGA與GA算法的平均最優(yōu)適值、平均計(jì)算時(shí)間和平均迭代次數(shù)關(guān)系，如表1所示。

表1 50次獨(dú)立優(yōu)化實(shí)驗(yàn)的平均性能

可見，APGA的優(yōu)化效果優(yōu)于GA算法，且優(yōu)化速度較快。這主要是由于GA算法具有容易陷入局部最優(yōu)的特點(diǎn)，參數(shù)可變遺傳操作可以跳出局部極小值陷阱和避免循環(huán)搜索，從而使得APGA算法快速的獲得了更優(yōu)的工作節(jié)點(diǎn)集。

圖2給出優(yōu)化工作節(jié)點(diǎn)集適值的性能，可見，在遺傳迭代穩(wěn)定后，APGA算法的適值總體性能明顯優(yōu)于其它兩種算法，大約可以高出GA算法50%，高出GA+密度檢測(cè)算法28%。算法的全局尋優(yōu)能力更強(qiáng)，且優(yōu)化速度較快，有效地減少了算法迭代次數(shù)，使得算法以較少的迭代次數(shù)獲得了更優(yōu)的工作節(jié)點(diǎn)集，有益于降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

圖3給出優(yōu)化工作節(jié)點(diǎn)集中工作節(jié)點(diǎn)數(shù)目的性能，可見，在滿足有效覆蓋率98%閾值條件下，APGA算法下選取的工作節(jié)點(diǎn)集中工作節(jié)點(diǎn)數(shù)目最少，約為GA的50%，約為GA+密度檢測(cè)的75%。APGA算法獲得了最少的工作節(jié)點(diǎn)，有利于充分休眠冗余節(jié)點(diǎn)，從而降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

5 結(jié) 語

本文以網(wǎng)絡(luò)覆蓋率、工作節(jié)點(diǎn)數(shù)目構(gòu)成優(yōu)化目標(biāo)，研究了節(jié)點(diǎn)高密度部署的炮兵通信網(wǎng)絡(luò)中優(yōu)化工作節(jié)點(diǎn)集選取的問題，提出了一種基于參數(shù)可變遺傳算法的覆蓋控制優(yōu)化方法。理論分析和實(shí)驗(yàn)數(shù)據(jù)表明，該方法通過密度檢測(cè)機(jī)制優(yōu)化了種群質(zhì)量，提高了優(yōu)化速度，通過自適應(yīng)遺傳操作增強(qiáng)了全局尋優(yōu)能力，從而快速有效地實(shí)現(xiàn)了工作節(jié)點(diǎn)數(shù)目少、節(jié)點(diǎn)集覆蓋率高的工作節(jié)點(diǎn)集的優(yōu)化選取，在較高的覆蓋質(zhì)量條件下休眠了更多的冗余節(jié)點(diǎn)，有效地降低了能耗，延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

參考文獻(xiàn)

[1] 劉樹海. 軍隊(duì)指揮自動(dòng)化系統(tǒng)[M]. 北京：解放軍出版社， 2002.

[2] WANG X， WANG S. An improved particle filter for target tracking in sensor system [J].Sensors，2007，7（1）：144-156.

[3] WANG X， MA J J， WANG S. Prediction-based dynamic power optimization in wireless sensor networks [J].Sensors，2007，7 （3）：251-266.

[4] JIA J，CHEN J，CHANG G R. Efficient cover set selection in wireless sensor networks[J].Acta Automatica Sinica，2008，34（9）：1157-1162.

[5] 潘偉. 基于參數(shù)可變遺傳算法的多普勒雷達(dá)目標(biāo)識(shí)別方法 [J]. 計(jì)算技術(shù)與自動(dòng)化， 2011， 30（2）： 105- 108.

步驟1 采用二進(jìn)制N位編碼方式對(duì)初始種群進(jìn)行編碼，0表示節(jié)點(diǎn)不工作，1表示節(jié)點(diǎn)工作，每個(gè)工作節(jié)點(diǎn)集即種群中每個(gè)個(gè)體用N位編碼表示；根據(jù)密度檢測(cè)進(jìn)行初始種群的優(yōu)化；

步驟2 根據(jù)式（1）計(jì)算種群內(nèi)個(gè)體適值、判斷終止條件，若滿足，則轉(zhuǎn)入步驟5，否則轉(zhuǎn)入步驟3；

步驟3 遺傳操作；

步驟4 構(gòu)成下一代種群個(gè)體，轉(zhuǎn)入步驟2；

步驟5 獲得優(yōu)化工作節(jié)點(diǎn)集，覆蓋控制結(jié)束。

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

采用MATLAB仿真平臺(tái)，對(duì)在GA、采用密度檢測(cè)機(jī)制優(yōu)化種群的GA（GA+密度檢測(cè)）、APGA三種算法下工作節(jié)點(diǎn)集選取的性能進(jìn)行驗(yàn)證，仿真實(shí)驗(yàn)中各參數(shù)采用通信網(wǎng)絡(luò)研究的通用設(shè)置。

APGA比GA算法的復(fù)雜度高，但APGA經(jīng)過合理設(shè)計(jì)后優(yōu)化性能優(yōu)于GA算法且優(yōu)化速度較快。進(jìn)行50次獨(dú)立的隨機(jī)拓?fù)鋵?shí)驗(yàn)，得到APGA與GA算法的平均最優(yōu)適值、平均計(jì)算時(shí)間和平均迭代次數(shù)關(guān)系，如表1所示。

表1 50次獨(dú)立優(yōu)化實(shí)驗(yàn)的平均性能

可見，APGA的優(yōu)化效果優(yōu)于GA算法，且優(yōu)化速度較快。這主要是由于GA算法具有容易陷入局部最優(yōu)的特點(diǎn)，參數(shù)可變遺傳操作可以跳出局部極小值陷阱和避免循環(huán)搜索，從而使得APGA算法快速的獲得了更優(yōu)的工作節(jié)點(diǎn)集。

圖2給出優(yōu)化工作節(jié)點(diǎn)集適值的性能，可見，在遺傳迭代穩(wěn)定后，APGA算法的適值總體性能明顯優(yōu)于其它兩種算法，大約可以高出GA算法50%，高出GA+密度檢測(cè)算法28%。算法的全局尋優(yōu)能力更強(qiáng)，且優(yōu)化速度較快，有效地減少了算法迭代次數(shù)，使得算法以較少的迭代次數(shù)獲得了更優(yōu)的工作節(jié)點(diǎn)集，有益于降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

圖3給出優(yōu)化工作節(jié)點(diǎn)集中工作節(jié)點(diǎn)數(shù)目的性能，可見，在滿足有效覆蓋率98%閾值條件下，APGA算法下選取的工作節(jié)點(diǎn)集中工作節(jié)點(diǎn)數(shù)目最少，約為GA的50%，約為GA+密度檢測(cè)的75%。APGA算法獲得了最少的工作節(jié)點(diǎn)，有利于充分休眠冗余節(jié)點(diǎn)，從而降低能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

5 結(jié) 語

本文以網(wǎng)絡(luò)覆蓋率、工作節(jié)點(diǎn)數(shù)目構(gòu)成優(yōu)化目標(biāo)，研究了節(jié)點(diǎn)高密度部署的炮兵通信網(wǎng)絡(luò)中優(yōu)化工作節(jié)點(diǎn)集選取的問題，提出了一種基于參數(shù)可變遺傳算法的覆蓋控制優(yōu)化方法。理論分析和實(shí)驗(yàn)數(shù)據(jù)表明，該方法通過密度檢測(cè)機(jī)制優(yōu)化了種群質(zhì)量，提高了優(yōu)化速度，通過自適應(yīng)遺傳操作增強(qiáng)了全局尋優(yōu)能力，從而快速有效地實(shí)現(xiàn)了工作節(jié)點(diǎn)數(shù)目少、節(jié)點(diǎn)集覆蓋率高的工作節(jié)點(diǎn)集的優(yōu)化選取，在較高的覆蓋質(zhì)量條件下休眠了更多的冗余節(jié)點(diǎn)，有效地降低了能耗，延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

參考文獻(xiàn)

[1] 劉樹海. 軍隊(duì)指揮自動(dòng)化系統(tǒng)[M]. 北京：解放軍出版社， 2002.

[2] WANG X， WANG S. An improved particle filter for target tracking in sensor system [J].Sensors，2007，7（1）：144-156.

[3] WANG X， MA J J， WANG S. Prediction-based dynamic power optimization in wireless sensor networks [J].Sensors，2007，7 （3）：251-266.

[4] JIA J，CHEN J，CHANG G R. Efficient cover set selection in wireless sensor networks[J].Acta Automatica Sinica，2008，34（9）：1157-1162.

[5] 潘偉. 基于參數(shù)可變遺傳算法的多普勒雷達(dá)目標(biāo)識(shí)別方法 [J]. 計(jì)算技術(shù)與自動(dòng)化， 2011， 30（2）： 105- 108.