基于改进禁忌算法的无线传感网络覆盖优化研究

关健

（闽江学院现代教育技术中心，福建 福州350108）

林耿

（闽江学院数学系，福建 福州350108）

无线传感器网络（WSNs）由大量具有感知、计算和通信能力的微型传感器以自组织方式构成，通过网内节点协作完成数据的采集与传送，广泛应用于军用和民用领域［1］。无线传感器网络节点具有高密度部署（密度可高达20nodes／m）［2］的特点，由此带来严重的网络冗余问题，因此探索覆盖优化机制是无线传感器网络应用的一个重要研究方向。目前已有许多学者对无线传感器网络覆盖优化机制进行研究并取得成果，特别是近年来将启发式算法引入到WSNs覆盖优化的研究中：文献 ［3］研究了加权遗传算法和基于约束遗传算法的优化覆盖机制，计算出传感器网络充分覆盖指定区域所需的近似最优工作节点集，并对2种优化机制的性能进行分析对比；文献 ［4］通过粒子群算法实现覆盖控制，并分析了传感器感知半径对覆盖性能的影响；文献 ［5］提出一种混合杂交算法的优化覆盖机制，采用混合杂交和间歇变异来提高算法的搜索能力并用于无线传感器网络覆盖模型的优化中。遗传算法具有全局搜索能力，并行搜索能力强，但收敛速度慢，很难满足动态节点选取的实时性要求。标准粒子群算法在空间搜索时，容易陷入 “早熟”现象，限制了粒子的搜索范围，影响覆盖效果［6］。

禁忌搜索算法（TS）具有较强的 “爬山”能力，在搜索过程中可以接受劣解，跳出局部最优解。为此，笔者基于改进禁忌搜索算法对无线传感网络覆盖优化问题进行了研究。

1 WSNs覆盖模型

假设1 各传感器节点的参数相同，全方向感知，有效感知半径均为r，即其覆盖范围是一个半径为r的圆形区域。

假设2 各传感器节点只具有工作和休眠2种状态。

假设3 假设一个像素被各传感器节点覆盖的事件是相互独立的。

假设4 监测区域为二维平面，形状规则，且传感器节点均在二维平面上，节点坐标可知。

定义1 监测区域A离散化为m×n个像素，每个像素面积为1，所有像素称为该区域的像素集E，E＝｛exy｜x∈ ｛1，2，…，m｝，y∈ ｛1，2， …，n｝｝，exy为像素点，坐标为（x，y）。

定义2 在监测区域A中投放N个传感器节点，每个节点的覆盖模型可表示为以节点坐标为圆心，r为半径的圆，所有圆称为传感器节点集C。C＝｛c1，c2， …，cN｝，其中ci＝｛xi，yi，r｝为节点ci的覆盖模型，（xi，yi）为节点ci的坐标，r为节点ci的有效感知半径，i∈｛1，2，…，N｝。

网络覆盖优化就是从大量的传感器节点中选取一组优秀节点，处于工作状态保证区域充分覆盖，同时尽量减少冗余节点，使其进入低功耗休眠状态，形成最优的覆盖节点集，不仅节约能源而且延长网络的生命周期。定义一个布尔向量S＝｛s1，s2， …，sN｝作为节点状态的标识，si＝1表示节点ci处于工作状态，si＝0表示处于休眠状态。传感器节点集C的数量为｜C｜，其中处于工作状态的节点集记为C′，其数量为｜C′｜，则网络节点利用率为：

WSNs中的传感节点都具有一个固定的有效感知半径，监测区域中的一点位于一个传感器节点的感知半径内则认为其被覆盖。

将监测区域A中像素点exy被传感器节点ci所覆盖的事件定义为hi，i∈｛1，2，…，N｝，该事件发生的概率记为P｛hi｝，表示像素点exy被传感器节点ci所覆盖的概率：

式（2）表明，如果传感器节点ci处于工作状态，且像素点exy到传感器节点ci的距离不大于节点的感知半径r，P｛hi｝＝1，则像素点exy被传感器节点ci覆盖，否则未被覆盖。而像素点exy被传感器节点ci和cj覆盖的随机事件hi和hj是相互独立的，i，j∈｛1，2，…，N｝且i≠j，则：

像素点exy被节点集C所覆盖的事件h发生的概率为hi并集的概率，即：

传感器节点集C所覆盖的像素面积之和即为该节点集的区域覆盖面积，记为A（C），有：

则网络有效覆盖率为：

式中，SA为整个区域的像素面积。

WSNs覆盖优化的目标是在保证最大化网络覆盖率的情况下，努力减少节点利用率，即要考察2个子目标函数：网络覆盖率函数和网络节点利用率函数。通过加权这2个子目标函数转化为总体目标函数，并将其作为算法求解的适应值函数，定义为：

式中，S为标识节点状态的向量；ω1，ω2为子目标函数对应的权值，ω1，ω2∈（0，1）且ω1＋ω2＝1，总体目标函数值介于0～1之间。

2 覆盖优化算法

2.1 基于ITS算法的覆盖优化

TS具有强大的局部搜索能力，收敛速度快，但是对初始解具有较强的依赖性［7］。基于TS算法框架，采用具有贪婪和随机性质的初始解构造方法，引入多样化扰动策略［8］，笔者提出一种改进的禁忌搜索算法（ITS），其主要思想如下：首先，利用具有贪婪和随机性质的初始解构造方法产生一个质量较好的初始解；然后，对初始解进行禁忌搜索，得到一个局部最优解并将其存储；最后，从存储的局部最优解集中随机选取一个解进行多样化扰动，作为下一轮禁忌搜索的初始解，如此循环，实现无线传感网络的覆盖优化。具体算法步骤描述如下。

Step1 初始化算法参数，令精英解集ES＝∅，长度为ER，被选择的精英解在解集中的位置Er＝0，基因的变换次数FF［i］＝0， 精英解集中基因为1的次数EF［i］＝0，i∈｛1，2，…，N｝。

Step2 由初始解构造算法产生一个初始解S0。

Step3 由禁忌搜索算法对S0进行局部搜索，得到解S＊，如果S＊∈ES，则转Step6。

Step4 如果Er＜ER，则ES＝ES＋｛S＊｝，Er＝Er＋1，EF＝EF＋S＊，转Step6。

Step5 如果f（S＊）＞f（Sw）（Sw为ES中最差解）， 则ES＝ES＋｛S＊｝－｛Sw｝，EF＝EF＋S＊－Sw。

Step6 判断是否满足算法终止条件，若是，则输出最优结果，结束算法；否则，从ES中随机选择一个精英解S′，由多样化扰动策略算法（算法4）扰动操作得到解S0，转Step3。

2.2 初始解构造方法

解采用二进制编码，1表示传感节点处于工作状态，0表示传感节点处于休眠状态。受到GRASP算法［9］的启发，可以通过改进轮盘赌算法［10］实现具有贪婪和随机性质的初始解构造，其主要思想如下：首先，计算各个传感节点单独的覆盖率，即每个传感节点单独处于工作状态，其他节点处于休眠状态时的覆盖率；然后，将所有节点处于休眠状态；最后，利用轮盘赌算法不断从休眠的节点中选择节点处于工作状态，直达停止条件满足，实现初始解的构造。具体算法步骤描述如下：

Step1 初始化算法参数，计算各个传感节点单独的覆盖率CR（i），i＝1，2，…，N，并令休眠的节点集CS＝｛si，i＝1，2，…，N ｝，工作的节点集CW＝∅。

Step2 更新CS中各个节点的积累概率pC（i）。

Step3 随机产生一个概率pR∈U（0，1），如果pC（i－1）≤pR＜pC（i），则节点si被选择处于工作状态，CS＝CS－｛si｝，CW ＝CW ＋｛si｝。

Step4 判断是否满足算法终止条件，若是，结束算法；否则，转Step2。

2.3 邻域结构

采用1－变换邻域构造邻域集［11］，设一个解为S＝（s1，s2，…，sN），si∈｛0，1｝，i＝1，2，…，N，则该解的邻域集为N（S）＝｛Si｜Si＝（s1，s2，…，1－si，si＋1，…，sN），i＝1，2，…，N｝即仅有一个节点状态发生变换。

2.4 禁忌搜索

禁忌搜索的最大特点是可以接受劣解，从而跳出局部最优，并引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，再通过特赦准则来赦免一些被禁忌的优良解，进而保证多样化的有效探索，最终实现全局优化［12］。具体算法步骤描述如下：

Step1 初始化算法参数，令当前解Snow＝S0，计算当前解的适应值fnow，全局最优解fgbest＝fnow，置禁忌表为空。

Step2 构造Snow的邻域解集N（Snow）＝｛S1，S2，…，SN｝，计算各邻域解的适应值并排序，适应值最大的记作flbest，其对应的邻域解记作Slbest。

Step3 特赦准则判断，如果flbest＞fgbest，则Snow＝Slbest，fgbest＝flbest，否则，从N（Snow）中选择未被禁忌且适应值最大的解Slfbest，Snow＝Slfbest，如果flfbest＞fgbest，则flbest＝fgbest。

Step4 将相应的禁忌对象加入禁忌表，修改禁忌表中各禁忌对象的禁忌期，对应的基因变换次数FF［i］加1。

Step5 判断是否满足算法终止条件。若满足，则输出最优结果，结束算法；否则，执行Step2。

2.5 多样化扰动策略算法

多样化扰动策略的思想是通过存储精英解集作为禁忌搜索的初始解，这样保证了初始解的质量和多样性，并存储各种频率信息，最终通过扰动评分函数来决定参与扰动的基因［13］。扰动评分函数如下：

该扰动评分函数尽量避免精英解集中稳定的基因及已多次变换的基因发生扰动，保持了优秀基因并减少冗余操作，其具体算法步骤描述如下：

Step1 由式（8）计算解向量中每个基因的扰动分数。

Step2 选择扰动分数较高的基因。

Step3 对选择的基因进行扰动操作。

Step4 发生扰动的基因的变换次数FF［i］加1，i为发生扰动的基因的位置，结束算法。

3 仿真试验及分析

3.1 覆盖模型的参数设置

参照文献 ［5］设置覆盖模型的参数，监测区域为100m×100m，离散为100×100个像素，节点感知半径为11.5m。根据区域的面积和传感器参数，首先确定性部署39个节点以正六边形结构最优化分布于监测区域（见图1）。然后随机播撒61个节点于该监测区域（见图2（a））。此外，式（7）中ω1＝0.1，ω2＝0.9。

图1 最优节点分布图

3.2 算法的有效性试验

采用ITS算法求解从图2（a）中选取一组优秀的节点集，算法运行70代，观察不同代数下区域的覆盖情况，并记录相应的节点利用率、覆盖率和适应值的试验数据。图2（b）～图2（f）分别表示初始、5代、10代、30代和70代时的节点分布，表1所示为各代对应的试验数据。由图2和表1可以看出，算法求解过程向着全局的最优解方向进行，70代时的节点分布图（见图2（f））非常接近于图1中的最优节点分布，共使用41个节点，获得99.77%的覆盖率，达到了优化覆盖的目的，这表明ITS是一种有效的WSNs覆盖优化算法。

图2 基于ITS算法的节点分布图

3.3 算法性能试验

ITS算法的收敛曲线图如图3所示。从图3（a）可以看出，该算法具有快速的收敛速度。从图3（b）可以看出，该算法在搜索过程中可以接受劣解，跳出局部最优解，具有较强的 “爬山”能力，从而搜索到更优的解。

图3 ITS算法收敛曲线图

图4所示为ITS算法运行50代覆盖优化试验的数据曲线图，其中，最大适应值为0.95802，最小适应值为0.94785，平均适应值为0.955514，方差为3.69×10－6，说明运行ITS算法不仅可以得到较好的解，而且有较好的稳定性。

表1 不同迭代次数的试验数据表

将ITS算法、基本遗传算法、基本模拟退火算法、粒子群算法、混合杂交算法的仿真结果进行对比，结果如表2所示。由表2可知，ITS算法的适应值优于其他算法，表明ITS算法得到的解更优。

图4 ITS算法运行50代的数据曲线图

表2 不同算法仿真结果的对比表

4 结语

针对WSNs的优化覆盖问题，根据传统禁忌搜索算法框架，提出了改进禁忌搜索算法。仿真试验表明，与粒子群算法、模拟退火算法、遗传算法、混合杂交算法相比，改进禁忌搜索算法的收敛速度快，稳定性好，在保证尽可能高的网络覆盖率下，减少节点的利用率，可以解决高密度部署的WSNs工作节点集选取问题。

［1］Xue Wang，Jun－Jie ma，Sheng Wang，et al.Distributed particle swarm optimization and simulated annealing for energy－efficient coverage in wireless sensor networks ［J］.Sensors，2007，7（5）：628～648.

［2］Shih E，Ickes N，Sinha A，et al.Physical layer driven protocol and algorithm design for energy－efficient wireless sensor networks ［A］.In：Christopher R，Mahmound N，Michele Z，eds.Proc.Of the 7th Annual Int’l Conf（C）.on Mobile Computing and Networking ［C］.ACM Press，2001：272～287.

［3］贾杰，陈剑，常桂然.无线传感器网络中基于遗传算法的优化覆盖机制 ［J］.控制与决策，2007，22（11）：1289～1292.

［4］林祝亮，冯远静.基于粒子群算法的无线传感器网络覆盖优化策略 ［J］.计算机仿真，2009，26（4）：190～193.

［5］林梅金，苏彩红，王飞.无线传感器网络覆盖优化算法研究 ［J］.计算机仿真，2011，28（3）：178～181.

［6］沈海洋.基于遗传PSO的无线传感网络覆盖优化算法研究 ［J］.微电子学与计算机，2013，30（3）：148～151.

［7］蒋大奎，李波，谭佳音.一类求解订单分配和排序问题的集成优化算法 ［J］.控制与决策，2013，28（2）：217～222.

［8］Glover F.Diversification－driven tabu search for unconstrained binary quadratic problems ［J］.4ORQ J Oper Res，2010，8（3）：239～253.

［9］朱文兴，程泓.VLSI电路划分问题的分散搜索算法 ［J］.电子学报，2012，40（6）：1207～1212.

［10］汪定伟.智能优化方法 ［M］.北京：高等教育出版社，2007.

［11］林耿，朱文兴.多维背包问题的变邻域填充函数算法 ［J］.福州大学学报，2012，40（1）：14～21.

［12］刘霞，齐欢.最小－最大车辆路径问题的禁忌搜索算法 ［J］.系统工程，2007，25（1）：49～51.

［13］陈铁梅，罗家祥，杜娟，等.带扰动和变异因子的改进禁忌搜索算法求解贴片机贴装过程优化 ［J］.控制与决策，2013，28（3）：363～368.