一种采用改进的人工蜂群算法的无线传感器部署方法

摘要

采用改进的人工蜂群算法的无线传感器部署方法，应用于在一个给定的空间中部署无线传感器以达到最大的无线传感器覆盖，首先，指定需要部署无线传感器的区域，其次，指定无线传感器的覆盖半径和数量，最后，不断调整无线传感器的位置，已尽可能达到最大的无线传感器覆盖率；具体包含5个步骤：包括初始化步骤；雇佣蜂步骤：设置优化计数trail是为了在侦查蜂阶段选择无法再优化的食物源重新初始化而设置得到；计算选择概率步骤；跟随蜂步骤和侦查蜂步骤：侦查蜂步骤会通过食物源已进行邻居优化的尝试次数优化计数trail对食物源进行优化。

主权项

采用改进的人工蜂群算法的无线传感器部署方法，应用于在一个给定的空间中部署无线传感器以达到最大的无线传感器覆盖的问题，其特征在于：首先，指定需要部署无线传感器的区域，其次，指定无线传感器的覆盖半径和数量，最后，不断调整无线传感器的位置，已尽可能达到最大的无线传感器覆盖率；利用改进的人工蜂群算法进行无线传感器的部署具体包含5个步骤：1)初始化步骤：假设需要将N个覆盖半径为r的无线传感器部署在一个边长为a的正方形房间；设定参数scale，表示切割出的小空间的边长和无线传感器覆盖半径的比例，参数scale的取值范围为[2,4]，根据空间的切割逆向推出；根据此参数计算出无线传感器均匀分布的数量count；$count=\frac{a^2}{{(scale\times r)}^2}$对count和N进行比较，如果count大于N，那么无线传感器的数量无法满足这一比例的均匀分布，那么需要调整参数scale的大小重新进行计算；如果count刚好等于N，那么初始化就能将所有无线传感器按顺序装入对应的切割出的小空间中，即在小空间的范围中进行坐标的随机取得；大部分情况下，count小于N，这时就将前count个无线传感器在对应的小空间中进行初始化，而剩余的无线传感器再进行全局范围的随机取值；食物源的初始化方法如下：x_ij＝(x_max‑x_min)×rand(0,1)+x_min,其中i为食物源序号，j为食物源中的变量编号，x_min和x_max分别为变量x_ij取值范围的最小值和最大值，对于前count个无线传感器，x_min和x_max为每个对应小的正方形的坐标上下限，而对于剩余的N‑count个无线传感器，x_min和x_max的取值范围为整个大的方形的坐标上下限；rand(0,1)为随机取得的(0,1)之间的随机数；随机算法总共生成SN个食物源(x_i,i∈[1,SN])，SN一般取蜂群大小的一半,每个食物源包含M个变量(x_ij,j∈[1,M])；2)雇佣蜂步骤：雇佣蜂步骤会对每个食物源进行邻居优化；雇佣蜂根据其对于食物源i的位置进行邻居搜索，随机获取食物源i的邻居食物源k，并且通过邻居食物源优化其对应的食物源，公式如下：y_ij＝x_ij+rand(‑1,1)×(x_kj‑x_ij),其中j∈[1,M]为所要优化的变量序号，分别为当前食物源和当前食物源选定的邻居食物源，rand(0,1)为[‑1,1]之间随机取得的随机数；当经过邻居优化取得的变量值超过其取值范围x_min和x_max时，直接取其接近的最值，此处的x_min和x_max值根据初始化步骤的改变需要做出相应的变化，对于前count个无线传感器，x_min和x_max为每个对应小的正方形的坐标上下限，而对于剩余的N‑count个无线传感器，x_min和x_max的取值范围为整个大的方形的坐标上下限；雇佣蜂会比较原始的食物源x_i和优化后的食物源y_i的适应度，如果原始食物源x_i的适应度更高，则不改变食物源，对食物源的优化计数trail加1；如果优化后的食物源y_i的适应度更高，则将原始食物源x_i替换成邻居优化后的食物源y_i，并将优化计数trail置0；设置优化计数trail是为了在侦查蜂阶段选择无法再优化的食物源重新初始化而设置得到；在进行一次邻居优化后，雇佣蜂会对对应的食物源继续进行优化，策略为：循环生成随机数r，只要r<MR，就继续进行优化，只有随机数r取值取得大于等于MR的值时，才停止优化；其中MR为邻居优化阈值，是算法中预先设定好的常数；当所有的雇佣蜂对每个食物源都进行邻居优化之后，记录邻居优化后所有食物源的新的适应度：适应度描述一个解即食物源对于全局最优解的接近程度，计算方式一般跟所求解的具体问题相关；适应度fitness_i的计算在标准人工蜂群算法中，方法如下公式所示：${\mathrm{fitness}}_i=\left\{\begin{array}{c}\frac{1}{1+f_i},(f_i\ge 0)\\ 1-f_i,(f_i<0)\end{array}\right.$其中，f_i为解i在求解问题函数中对应的函数值；3)计算选择概率步骤：在原始的人工蜂群算法中，选择概率的计算方式为计算食物源适应度在所有食物源适应度之和中所占的比例；为了能够更好的控制跟随蜂阶段的优化进度，改进的人工蜂群算法中引入了参数选择概率阈值θ来控制选择概率的计算，方法如下：${\mathrm{prob}}_k=\theta \times \frac{{\mathrm{fitness}}_k}{{\Sigma }_{i=1}^{SN}{\mathrm{fitness}}_i}+1-\theta ,$其中fitness_i为适应度，SN为食物源数量，选择概率阈值θ为算法一开始需要设定好的参数，取值范围为[0,1]；θ值越大，计算所得的选择概率prob_k越小，跟随蜂步骤对于低适应度的食物源进行邻居优化的概率越高；θ值越小，计算所得的选择概率prob_k越大，跟随蜂步骤越可能对于高适应度的食物源进行优化；4)跟随蜂步骤：在跟随蜂步骤中，原始的人工蜂群算法会通过选择概率决定要优化的食物源，采用如下策略对食物源进行邻居优化；在改进的人工蜂群算法中，邻居优化采用了一种新的策略，加入了邻居因子和遗忘因子两个参数，将邻居优化与当前食物源和选择的邻居食物源的适应度y_ij建立了关联，方法如下公式所示；y_ij＝η×x_ij+τ×rand(‑1,1)×(x_kj‑x_ij),其中η为邻居因子,τ为遗忘因子；η与当前食物源邻居优化选择的邻居食物源有关，与循环次数正相关以防止陷入局部最优；τ与当前待优化食物源有关，与循环次数负相关，用于保持当前食物源的信息；这两个参数的计算如下公式所示；τ＝λ×ω_τ,η＝λ×ω_η,其中λ为根据当前食物源和所选定的邻居源的关系，为算法一开始要设定的两个常数值,这两个常数值一个大于1，一个小于1；当当前食物源的邻居食物源的适应度低于当前食物源的适应度时，则λ>1；反之则λ<1；只与当前循环数相关，关系如下公式所示；${\omega }_{\tau }={\omega }_1+{\left(\frac{\max cycle-iter}{\max cycle}\right)}^{\beta }\times ({\omega }_2-{\omega }_1),$${\omega }_{\eta }={\omega }_4-{\left(\frac{\max cycle-iter}{\max cycle}\right)}^{\alpha }\times ({\omega }_4-{\omega }_3),$其中ω₁,ω₂,ω₃,ω₄,α,β为算法一开始需要设定的常数,iter为算法的当前循环次数,maxcycle为算法设定的最大循环次数；α和β的取值范围分别为[0.8,1]和[1,1.2]；5)侦查蜂步骤：侦查蜂步骤会通过食物源已进行邻居优化的尝试次数优化计数trail对食物源进行优化；根据雇佣蜂中对邻居优化的描述，食物源每进行一次邻居优化，如果食物源未优化成功，即生成的新的食物源适应度低于原始食物源，则该食物源的优化计数trail加1，反之，则该食物源的优化计数trail置0；在侦查蜂步骤，侦察蜂会对尝试次数超过最大尝试次数limit的食物源中优化计数trail最大的一个食物源进行重新初始化。