夏化冰+潘伟

收稿日期：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.