一种基于改进遗传算法的无线网络覆盖研究

叶剑春（山西煤炭职业技术学院 计算机系，山西 太原030031）

覆盖优化机制成为无线传感器网络应用的一个重要问题[1]。目前已有很多学者对无线传感器网络覆盖优化机制进行研究并取得成果。有学者研究了加权遗传算法[2]和基于约束遗传算法[3]的优化覆盖机制，计算出传感器网络充分覆盖指定区域所需的近似最优工作节点集，只说明该算法应用的有效性而没有说明它应用的优越性；还有研究学者通过粒子群算法[4]实现覆盖控制，并分析了传感半径对覆盖性能的影响，但是其优化目标不考虑节点利用率所得到的优化结果，不利于延长网络生存周期。由于无线传感器网络的节点由能量有限的电池供电，其大多数都部署在野外和战场等复杂环境下，为其进行充电不太现实。因此在保证网络覆盖率的条件下同时延长网络的生命周期成为传感器网络研究中的热点。

随着越来越多的大中型规模网络采用多WLAN来进行无缝覆盖，如何放置无线接入访问点以使得在有限发射功率条件下达到最大网络有效覆盖率的问题变得越来越突出，网络规划迫切地需要一种优化算法来解决这个问题。目前还没有成熟的理论和工具，虽然在基于CDMA或TDM技术的蜂窝系统中已提出许多基站放置优化算法，但都不能直接应用在WLAN环境。目前已有一些无线局域网规划软件可以根据无线信号强度来确定AP的放置方案，但并没有针对大规模局域网系统的接入点放置优化算法。本文针对当前传感器网络的算法中存在的热点问题提出一种改进的遗传算法，通过设置合理的接入访问点位置实现网络有效覆盖率的最大化，并有效避免小区间的同频干扰。该算法以网络有效覆盖率为优化目标，改进了遗传算法中的交叉和变异策略。实验表明，改进的遗传算法可有效提高网络的覆盖率，实现了网络性能优化。

1 无线传感器网络覆盖原理

在需要获得较高覆盖率的无线网络中，通常以加大节点的布设密度来减少感知盲点出现的几率。但是，大量冗余节点会使网络数据传输产生冲突，导致能量过分消耗，造成网络过早失效。若某节点的感知区域能被其他节点完全覆盖，则此节点为冗余节点，可以进入休眠状态。通过一定的算法判断网络中的冗余节点，在保证网络覆盖率最大化的同时使用尽可能少的工作节点并让冗余节点进入休眠状态是一种满足网络覆盖要求并减小能耗的有效方法。因此，在网络初始阶段，工作节点的合理选取对提高网络性能和降低运行成本有重要意义。与此同时，网络能量的均衡消耗对于网络的稳定运行和网络寿命的延长至关重要，这就存在与覆盖率和工作节点数相互矛盾的问题。因此需要对多个目标进行优化。

设目标区域内网格总数为m，AP备选位置共n个，预设所需的AP数量为k，该AP的有效覆盖范围为Di，i∈I={1，2，…，n}。则问题转化为从 n个备选位置中选择k个最优位置，使得总覆盖区域 D最大化[5-6]。

本文采用Two-ray-ground模型来模拟接收信号强度分布，接收信号功率Pr为：

其中Pt为发送信号功率，Gt、Gr为发送、接收天线增益，ht、hr为发送、接收天线高度，d为信号传输距离，L为信道干扰。

基于上述描述，用1表示接收功率大于-60 dBm的网格，即有效覆盖网格；用0表示接收信号功率小于-60 dBm的网格，即无效覆盖网络。则可得到一个m×n的矩阵M：

矩阵共n列代表备选AP的数量，每一列m个元素代表该备选AP所覆盖区域的有效性。如：

网络中k个AP的覆盖率可表示为有效覆盖的网格数量与目标区域网格总量之比，则网络有效覆盖率Rcov可表示为：

2 改进的遗传算法无线网络覆盖

遗传操作包括三个基本遗传算子：选择、交叉和变异。其中交叉和变异对算法的影响最大。交叉通过把两个父代个体的部分结构加以替换重组而生成新个体，变异则是对群体中的个体串的某些基因位上的基因值进行改动，交叉和变异使遗传算法的搜索能力得到提高。交叉算子因其全局搜索能力作为主要算子，变异算子因其局部搜索能力作为辅助算子。

传统的遗传算法采用固定的交叉和变异概率，在迭代后期可能会导致若干问题，如小的变异和交叉概率容易引起收敛缓慢和早熟等问题，而大的变异概率则会导致算法无法收敛。

为解决以上问题，本文采用了一种自适应的交叉和变异算子，使不同的个体自适应地改变交叉和变异概率。相似度较高的父代个体降低其交叉概率，而相似度低的父代个体则提高其交叉概率，以提高交叉操作的有效性，实现更有效的全局搜索；同时对适应度高的个体采用低的交叉概率，对适应度低的个体采用高的交叉概率，有利于保持种群的多样性，加快收敛并避免陷入局部最优。自适应交叉和变异算子的计算如下：

其中 ci，j，n为第 i和第 j个父代在第 n 代的交叉概率，si，j为第i和第j个父代之间的相似度，本文中采用Hamming距 离 ，mi，n为 第 i个个体 在 第 n 代的 变 异 概 率 ，fi，n为第i个体在第n代的适应度。

如果备选AP总数量为n，k为预设的AP数量，则在该问题中可能的设置方案为种情况。本算法中采用的编码方式将染色体I分成k个部分，每个部分用长度为l的行向量表示，对应一个AP位置的编号，l的长度为：

则染色体总长度为k×l。由于编码后的染色体的交叉、变异范围为2l，可能超出总量为n的可行解范围造成溢出。为解决上述问题，需在解码时进行相应的线性变换，将染色体的值转换到[0，n]范围内。

式(9)中，ID′为转换后的十进制编号值并且 0≤ID′≤n。

算法对于子代的选择方式采用轮盘赌算子。将整个种群视为一个圆盘，根据每个染色体适应度值确定该染色体的权重，通过产生的随机指针选择要复制的子代[7]。

交叉是对任意两个个体按某种方式互换其部分基因，从而形成两个新的个体，是遗传算法中产生新个体的主要方法。变异是指将个体编码串中的某些基因值用其他基因值来替换，生成一个新的个体。本文算法中交叉和变异过程采用均匀交叉算子和均匀变异算子，将每个染色体上对应的基因以相同的概率进行交叉、变异。

适应度用来度量个体在优化计算中可能到达最优解的优良程度，个体的适应度通过适应度函数产生。直接用有效覆盖率作为适应度函数，则适应度函数f1(I)可表示为：

其中cov表示目标区域内有效覆盖的网格数量，m为区域内网格总数量。仿真结果显示，式(10)所示的适应度函数在实际算法的应用中存在收敛速度过快或过慢的问题，容易收敛于局部最优值，而不能准确达到全局最优解。下面对f1(I)进行部分改进，做线性变换得到f2(I)[8]：

式(11)中的系数 a、b使 f2(I)满足：

c的取值为f的最大值与均值的比例。由式(11)、式(12)可得：

由式(13)得到系数 a、b，进而由式(11)得到 f2(I)。

在上述适应度函数的基础上，提出第三种适应度函数f3(I)：

f3(I)的值在一定范围内随有效覆盖率的提高呈指数增长。

3 仿真结果分析

本文所有的实验都是在PC P4 T2310 1.86 GHz、2 GB RAM、Inte182865G显卡的计算机上完成，实验环境为MATLAB7.0，为了验证本文提出的改进算法的有效性，根据无线传感器网络确定性覆盖方法[9-11]，选取的目标区域为160 m×160 m的正方形自由区域，网格划分的步长为2 m，则总网格数为6 400个。在目标区域中随机生成40个不相邻点作为备选位置，取预设AP数为3，则所有可能的情况为即9 880个。无线接收信号强度分布模型采用Two-ray-ground模型，接收信号功率大于-60 dBm为有效覆盖网格。算法核心在于从40个备选位置中选择3个最优AP放置点，使目标区域内的有效覆盖率最大化。设置遗传算法的参数：初始交叉率为0.1，初始变异率为 0.6，迭代次数为200。

图1和图2分别为算法运行20次适应度均值。从图中可以看出，算法总体收敛性很好。对于适应度函数1，算法在40代前可达到收敛，并对种群数量变化的灵敏度不大。对于适应度函数2，算法收敛速度与适应度函数1相比较慢，种群数量对算法性能影响较大，数量为50的种群性能优于数量为5的种群。进一步分析表明，并不是种群数量越大，算法性能越好。若种群数量过大易造成系统数据量过大，影响运算效率。

图1 不同种群数量优化值比较(适应度函数1)

图2 不同种群数量优化值比较(适应度函数2)

从上面两幅图中可以看出，适应度函数2可达到的最大覆盖率最高，另外适应度函数2的最大覆盖率高于适应度函数1。由于适应度函数是覆盖率的反映，引导着算法收敛的方向，但并不与覆盖率完全正相关。在60代左右，适应度函数2与覆盖率进化方向产生差别导致噪声产生。

表1所示为两种适应度函数仿真结果比较，可见适应度函数2可达的最高覆盖率较高，适应度函数1的收敛速度比适应度函数2快，从整体性能来看，适应度函数2性能较好。

表1 两种适应度函数比较

无线传感器网络极大地提高了人们认识和改造世界的能力。而网络覆盖控制作为无线传感器网络实施过程中的一个重要问题，反映了网络所能提供的感知服务质量。本文立足于无线传感器网络的优化覆盖问题，提出了一种改进的遗传算法无线传感器网络覆盖优化机制，通过与两种适应度函数比较、仿真实验结果表明，该优化机制能更有效地跳出局部最优，获得更精确的结果，从而更好更有效地实现了无线传感器网络布局的全局优化。

[1]毛莺池，陈力军，陈道蓄，等.无线传感器网络覆盖控制技术研究[J].计算机科学，2007，34(3)：20-22.

[2]汪学清，杨永田，孙亭，等.无线传感器网络中基于网格的覆盖问题研究[J].计算机科学，2006，33(11)：38-39，78.

[3]屈斌，胡访宇.高效节能的无线传感器网络路由协议研究[J].计算机仿真，2008，25(5)：113-116.

[4]周永华，李鹏，毛宗源.一种新的混合杂交方法及其在约束优化中的应用[J].计算机工程与应用，2006，42(6)：48-50.

[5]HERRERA F，LOZANO M.Gradual distributed Real Coded genetic algorithms[J].IEEE Trans on Evolutionary Computation，2000，5(1)：43-63.

[6]张轮.一种无线传感器网络覆盖的粒子群优化方法[J].同济大学学报(自然科学版)，2009，37(2)：262-266.

[7]刘丽萍，王智，孙优贤.无线传感器网络部署及其覆盖问题研究[J].电子与信息学，2006，28(9)：1752-175.

[8]杜辉，肖德贵，罗娟，等.一种无线传感器网络覆盖度确定算法[J].计算机仿真，2007，24(12)：117-120.

[9]YOUNIS O，FAHMY S.HEED：a hybrid，energy-efficient，distributed clustering approach for Ad hoc sensor networks[J].IEEE Transactions on Mobile Computing，2004，3(4)：660-669.

[10]李捷，刘先省，韩志杰.基于ARMA的无线传感器网络流量预测模型的研究[J].电子与信息学报，2007，29(5)：1224-1227.

[11]YE M，LI C F，CHEN G H，et al.An energy efficient clustering scheme in wireless sensor networks[J].International Journal of Ad Hoc&Sensor Wireless Networks，2007，3(2)：99-119.