基于參數可變遺傳算法的炮兵通信網絡覆蓋控制優化

夏化冰+潘偉

收稿日期：2013-12-29

基金項目：國家自然科學基金資助項目（60974091）

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

通訊聯系人，E-mail：pan.w@126.com

文章編號：1003-6199（2014）03-0035-04

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

關鍵詞：炮兵通信網絡；覆蓋；工作節點集；參數可變遺傳算法

中圖分類號：TP31 文獻標識碼：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 引 言

未來信息化條件下，炮兵作為陸軍的火力突擊骨干力量，將擔負更加繁重的作戰任務，這要求炮兵部隊必須具備良好的信息獲取及處理能力，以便控制復雜的信息化戰場。炮兵群通信系統由通信網和炮兵通信節點組成，主要應用于各級指揮單元和行動單元，完成信息的傳輸，是聯接指揮控制等分系統的紐帶[1]。

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

2 問題建模

2.1 相關假設

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

2.2問題模型

炮兵通信網絡優化覆蓋問題是一個典型的目標優化問題。網絡有效覆蓋率、工作節點數目是衡量工作節點集選取的重要指標，綜合考慮二者設計適值函數F（x）與優化模型Fopt分別為

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

Fopt=max F（x）（2）

式中，α，β為調節系數，其值取決于網絡設計者對網絡性能指標的綜合要求，Pcov為工作節點集的有效覆蓋率，numworknodes為工作節點集的節點數目，xsize為目標區域長度，ysize為目標區域寬度，符號[ ]表示取整，xsize3Rs×2×ysize3Rs為覆蓋目標區域所需要的最少節點個數[4]。

為了計算Pcov，將目標區域劃分為m×n個網格，以網格中心被覆蓋的程度代表網格被覆蓋的程度，△s表示一個網格的面積，As表示矩形的面積，則有

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

網格G（xl， yω）被節點i覆蓋的概率為

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

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

0，others（4）

式中，（xl， yω）為網格中心點坐標。

節點間彼此獨立，則有

RRi∪Rj=1-pi∪j=

1-pipj （5）

網格被節點集覆蓋的概率為

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

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

則工作節點集的有效覆蓋率Pcov為

Pcov =節點集覆蓋的面積總面積=

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

3 遺傳算法求解步驟

3.1 初始種群優化

1）密度檢測

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

2）優化過程

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

3.2 遺傳操作

遺傳操作包括選擇、交叉、變異三種操作算子，本文采用標準遺傳操作，選擇操作是排序選擇+最佳個體保存法，交叉操作是依據交叉概率的單點交叉，變異操作是依據變異概率的單基因突變。選擇操作是遺傳算法的基礎，變異操作是遺傳算法的核心，交叉操作是遺傳算法的補充[5]。

3.3 交叉概率的自適應確定

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

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

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

3.4 變異概率的自適應確定

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

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

k2f≤ （9）

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

3.5 實施步驟

初始化覆蓋控制優化中各參數，包括節點數目N，種群優化比例c，遺傳算法的種群規模G，工作節點集的有效覆蓋率閾值Pcovm。

步驟1 采用二進制N位編碼方式對初始種群進行編碼，0表示節點不工作，1表示節點工作，每個工作節點集即種群中每個個體用N位編碼表示；根據密度檢測進行初始種群的優化；

步驟2 根據式（1）計算種群內個體適值、判斷終止條件，若滿足，則轉入步驟5，否則轉入步驟3；

步驟3 遺傳操作；

步驟4 構成下一代種群個體，轉入步驟2；

步驟5 獲得優化工作節點集，覆蓋控制結束。

4 仿真實驗

采用MATLAB仿真平臺，對在GA、采用密度檢測機制優化種群的GA（GA+密度檢測）、APGA三種算法下工作節點集選取的性能進行驗證，仿真實驗中各參數采用通信網絡研究的通用設置。

APGA比GA算法的復雜度高，但APGA經過合理設計后優化性能優于GA算法且優化速度較快。進行50次獨立的隨機拓撲實驗，得到APGA與GA算法的平均最優適值、平均計算時間和平均迭代次數關系，如表1所示。

表1 50次獨立優化實驗的平均性能

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

圖2給出優化工作節點集適值的性能，可見，在遺傳迭代穩定后，APGA算法的適值總體性能明顯優于其它兩種算法，大約可以高出GA算法50%，高出GA+密度檢測算法28%。算法的全局尋優能力更強，且優化速度較快，有效地減少了算法迭代次數，使得算法以較少的迭代次數獲得了更優的工作節點集，有益于降低能耗，延長網絡生存時間。

圖3給出優化工作節點集中工作節點數目的性能，可見，在滿足有效覆蓋率98%閾值條件下，APGA算法下選取的工作節點集中工作節點數目最少，約為GA的50%，約為GA+密度檢測的75%。APGA算法獲得了最少的工作節點，有利于充分休眠冗余節點，從而降低能耗，延長網絡生存時間。

5 結 語

本文以網絡覆蓋率、工作節點數目構成優化目標，研究了節點高密度部署的炮兵通信網絡中優化工作節點集選取的問題，提出了一種基于參數可變遺傳算法的覆蓋控制優化方法。理論分析和實驗數據表明，該方法通過密度檢測機制優化了種群質量，提高了優化速度，通過自適應遺傳操作增強了全局尋優能力，從而快速有效地實現了工作節點數目少、節點集覆蓋率高的工作節點集的優化選取，在較高的覆蓋質量條件下休眠了更多的冗余節點，有效地降低了能耗，延長了網絡生存時間。

參考文獻

[1] 劉樹海. 軍隊指揮自動化系統[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] 潘偉. 基于參數可變遺傳算法的多普勒雷達目標識別方法 [J]. 計算技術與自動化， 2011， 30（2）： 105- 108.

步驟1 采用二進制N位編碼方式對初始種群進行編碼，0表示節點不工作，1表示節點工作，每個工作節點集即種群中每個個體用N位編碼表示；根據密度檢測進行初始種群的優化；

步驟2 根據式（1）計算種群內個體適值、判斷終止條件，若滿足，則轉入步驟5，否則轉入步驟3；

步驟3 遺傳操作；

步驟4 構成下一代種群個體，轉入步驟2；

步驟5 獲得優化工作節點集，覆蓋控制結束。

4 仿真實驗

采用MATLAB仿真平臺，對在GA、采用密度檢測機制優化種群的GA（GA+密度檢測）、APGA三種算法下工作節點集選取的性能進行驗證，仿真實驗中各參數采用通信網絡研究的通用設置。

APGA比GA算法的復雜度高，但APGA經過合理設計后優化性能優于GA算法且優化速度較快。進行50次獨立的隨機拓撲實驗，得到APGA與GA算法的平均最優適值、平均計算時間和平均迭代次數關系，如表1所示。

表1 50次獨立優化實驗的平均性能

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

圖2給出優化工作節點集適值的性能，可見，在遺傳迭代穩定后，APGA算法的適值總體性能明顯優于其它兩種算法，大約可以高出GA算法50%，高出GA+密度檢測算法28%。算法的全局尋優能力更強，且優化速度較快，有效地減少了算法迭代次數，使得算法以較少的迭代次數獲得了更優的工作節點集，有益于降低能耗，延長網絡生存時間。

圖3給出優化工作節點集中工作節點數目的性能，可見，在滿足有效覆蓋率98%閾值條件下，APGA算法下選取的工作節點集中工作節點數目最少，約為GA的50%，約為GA+密度檢測的75%。APGA算法獲得了最少的工作節點，有利于充分休眠冗余節點，從而降低能耗，延長網絡生存時間。

5 結 語

本文以網絡覆蓋率、工作節點數目構成優化目標，研究了節點高密度部署的炮兵通信網絡中優化工作節點集選取的問題，提出了一種基于參數可變遺傳算法的覆蓋控制優化方法。理論分析和實驗數據表明，該方法通過密度檢測機制優化了種群質量，提高了優化速度，通過自適應遺傳操作增強了全局尋優能力，從而快速有效地實現了工作節點數目少、節點集覆蓋率高的工作節點集的優化選取，在較高的覆蓋質量條件下休眠了更多的冗余節點，有效地降低了能耗，延長了網絡生存時間。

參考文獻

[1] 劉樹海. 軍隊指揮自動化系統[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] 潘偉. 基于參數可變遺傳算法的多普勒雷達目標識別方法 [J]. 計算技術與自動化， 2011， 30（2）： 105- 108.

步驟1 采用二進制N位編碼方式對初始種群進行編碼，0表示節點不工作，1表示節點工作，每個工作節點集即種群中每個個體用N位編碼表示；根據密度檢測進行初始種群的優化；

步驟2 根據式（1）計算種群內個體適值、判斷終止條件，若滿足，則轉入步驟5，否則轉入步驟3；

步驟3 遺傳操作；

步驟4 構成下一代種群個體，轉入步驟2；

步驟5 獲得優化工作節點集，覆蓋控制結束。

4 仿真實驗

采用MATLAB仿真平臺，對在GA、采用密度檢測機制優化種群的GA（GA+密度檢測）、APGA三種算法下工作節點集選取的性能進行驗證，仿真實驗中各參數采用通信網絡研究的通用設置。

APGA比GA算法的復雜度高，但APGA經過合理設計后優化性能優于GA算法且優化速度較快。進行50次獨立的隨機拓撲實驗，得到APGA與GA算法的平均最優適值、平均計算時間和平均迭代次數關系，如表1所示。

表1 50次獨立優化實驗的平均性能

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

圖2給出優化工作節點集適值的性能，可見，在遺傳迭代穩定后，APGA算法的適值總體性能明顯優于其它兩種算法，大約可以高出GA算法50%，高出GA+密度檢測算法28%。算法的全局尋優能力更強，且優化速度較快，有效地減少了算法迭代次數，使得算法以較少的迭代次數獲得了更優的工作節點集，有益于降低能耗，延長網絡生存時間。

圖3給出優化工作節點集中工作節點數目的性能，可見，在滿足有效覆蓋率98%閾值條件下，APGA算法下選取的工作節點集中工作節點數目最少，約為GA的50%，約為GA+密度檢測的75%。APGA算法獲得了最少的工作節點，有利于充分休眠冗余節點，從而降低能耗，延長網絡生存時間。

5 結 語

本文以網絡覆蓋率、工作節點數目構成優化目標，研究了節點高密度部署的炮兵通信網絡中優化工作節點集選取的問題，提出了一種基于參數可變遺傳算法的覆蓋控制優化方法。理論分析和實驗數據表明，該方法通過密度檢測機制優化了種群質量，提高了優化速度，通過自適應遺傳操作增強了全局尋優能力，從而快速有效地實現了工作節點數目少、節點集覆蓋率高的工作節點集的優化選取，在較高的覆蓋質量條件下休眠了更多的冗余節點，有效地降低了能耗，延長了網絡生存時間。

參考文獻

[1] 劉樹海. 軍隊指揮自動化系統[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] 潘偉. 基于參數可變遺傳算法的多普勒雷達目標識別方法 [J]. 計算技術與自動化， 2011， 30（2）： 105- 108.