基于混合遗传算法的物联网无线节点定位研究

2020-01-14李元熙

武汉工程职业技术学院学报 2019年4期

李元熙

（1．无锡商业职业技术学院物联网技术学院江苏无锡：214153；2．江苏省无线传感系统应用工程技术研究开发中心江苏无锡：214000）

0 引言

随着智能技术的兴起，自动驾驶作为物联网的一种新应用日益成为研究热点。仓储区域内自动行驶车辆通常装载无线模块和传感器，其作为一个典型的物联网无线节点与网络内其他节点按射程以多跳方式组成底层的无线网络，构建出物联网的网络层结构。因此，物联网无线节点的定位问题可以演化为底层无线网络节点的定位问题。物联网中无线节点分布离散且不均匀，利用其进行目标定位和跟踪受环境、成本等因素影响较大，因而设计一种底层无线节点的位置估算方法，在低成本条件下提高定位精度是物联网无线节点在自动驾驶应用中的一个重要需求。

目前，大部分定位算法都是利用一些锚点［1］通过计算连通度或者距离等方式来定位未知节点，如Shang Y提出的MDS－MAP算法［2］、Niculescu D的DV－Hop或DV－Distance方法［5］等，这些方法虽然成本不高，但由于算法本身受到网络规模或邻居节点信息准确度影响，应用场景受限且精度较粗。近些年也有学者提出了新方法，如Tam V利用遗传算法提出了GAL定位算法和Kannan A．A．提出的SAL算法［5］，这些方法利用群体算法优化提高定位精度，但受制于参数的设定和计算复杂度，目前都处于发展阶段。

由于无线网络资源受限，为了在低成本条件下提高物联网中底层无线节点的定位精度，本文混合使用遗传算法（GA）与模拟退火算法（SA）进行计算，利用退火算法具备概率性向“优”和“劣”两个方向搜索的特点，优化遗传算子，克服“早熟”现象，加速定位值最优解计算，提高无线网络中未知节点的定位精度和效率。

1 理论与方法

1．1 无线节点定位方法

无线节点定位模型采用二维空间表示，每个节点坐标为（xi，yi）。空间共有X个锚点和Y个待测节点，锚点坐标为（xm，ym）其中m＝1，2，3，…，X，组成锚点坐标向量Xm＝［x1，x2，…，xX］′，Ym＝［y1，y2，…，yX］′。定位问题就可以转换为利用X个锚点，通过通信约束条件求解Y个待测节点的坐标（xn，yn）其中Xn＝［xX＋1，xX＋2，…，xX＋Y］′，Yn＝［yX＋1，yX＋2，…，yX＋Y］′，即求解下列的方程：

其中x，y是待测点坐标，x1，2，…，X和y1，2，…，X是锚点坐标，d1，2，…，X是锚点与待测点间的距离。由于实际测量时距离存在误差，因而定位可以转换成可以求解方程的极小值问题。

在计算距离di时，可采用DV－Hop算法实现估算，该方法使用平均每跳距离Hopzizei替代无线射程作为多跳网络中每跳的距离，两点间距离计算公式di＝N×Hopzizei，其中N的待测两点间的最小跳数。Hopzizei的计算可利用两个锚点间距离通过均分跳数来获取，计算方法如下

其中hj是当前锚点（xi，yi）与远程锚点（xj，yj）间的跳数。DV－Hop方法是利用锚点间多跳距离和来估算直线距离，该方法对硬件要求低，实现简单，在均匀分布网络中效果较好，但在非均匀分布或稀疏分布的网络中，会有误差。

1．2 遗传与退火算法

遗传算法是一种模仿自然生物选择和进化规律发展起来的全局搜索与优化方法［2］，在优化时采用适度值替代梯度作为选择依据，因而具有很强的鲁棒性和全局搜素能力。遗传算法通过选择、交叉和变异实现父代与子代间的进化。选择操作利用适度值作为下一代个体出现的概率，体现种群的进化方向；交叉概率Pc是新个体出现的方法，体现了父代与子代间的信息交互；变异概率Pm是给种群带入小概率扰动以保持种群多样性，其体现局部搜索能力。

模拟退火算法是将优化问题与热平衡问题进行对比，利用Metropolis准则以一定概率接受“优化”与“恶化”解，使算法跳出局部最优的陷阱［5］。退火算法过程是从初始温度开始求解，在等温过程中由扰动变化出新解后利用Metropolis准则接受新解，冷却过程利用降温速率参数控制迭代过程。退火算法能以最大概率求得最优解，具有全局收敛性，对目标和约束函数没有要求，具有较广的适用性。

1．3 优化方法

混合算法的优化方法是利用遗传算法全局搜索能力强的优势［4］，结合退火算法摆脱局部最优解，丰富全局并行与局部串行的搜索能力［3］，削弱了算法参数选择要求。优化方法思路是在遗传算法的选择策略中引入退火算法的Metropolis接受准则，即对个体i随机交换部分基因生成新个体j，i和j通过Metropolis准则竞争进入下一代种群，具体选择方法如下：计算个体i和j的评价函数为f（i）和f（j），获取评价增量Δf＝f（j）－f（i）。当Δf＜0时，新个体j以概率1进入下代种群；当Δf＞0时，随机在［0，1］间产生一个参考数r，如果满足r＜exp（－Δf／T），则仍将新个体j放入下代种群，否则，将原个体i放入下代种群。其Metropolis接受准则如下：

其中P为进入下代种群的接受概率，T为当前温度。

2 实现过程与参数设置

2．1 遗传算法实现

1）编码与种群设定

混合算法中待优化的参数是未知节点坐标（xn，yn），采用实数编码方式有利于降低计算复杂度［6］。在种群数量设定方面，一般要求选择较大的种群规模有利于多样性的保持，但过大的种群数量也将增加计算复杂度，故本文采用经验值设定为50。

2）适度函数设计

遗传算法的进化方向是通过计算个体的适度值来进行的，本文的混合定位算法选取连通域内与待测节点距离最近的3个锚点作为计算锚点，因此遗传算法的适度函数设计为

其中ki是权重系数用于描述距离测量精度，fi（x，y）＝（－di）2，即锚点与待测点位置估值（＾x，＾y）间的差值。

3）选择算子

选择算子的设置既要保证种群多样性，又要能加速收敛到最优解，因而为了防止GA进入局部最佳，选择算子采用SA算法中的Metropolis接受准则，以一定概率选择优解进入下代种群。

4）交叉算子

为了简化计算，交叉算子Pc采用单点交叉方式，随机设定交叉点。

5）变异算子

变异方式采用优先保留优势个体的均匀变异策略，即当个体为最优个体时，保留不变，而其他个体用均匀分布的随机数选出变异基因。

2．2 模拟退火算法实现

1）加温操作（初始化设置）

设置内容包括：设定初始化温度T0应该足够大，令T＝T0，取任意初始解S0，确定每个T时的迭代次数（即Metropolis链长L）。

2）等温操作（Metropolis抽样）

对当前解Si增加一个随机扰动，产生新解Si＋1，计算增量Δf＝f（Si＋1）－f（Si），其中f（Si）是解Si评价函数。以Metropolis接受准则进行选择，当Δf＜0时，接受解Si＋1为新的当前解；否则，以概率exp（－Δf／T）接受Si＋1为新解。

3）冷却操作

该过程对应控制参数下降，即更新当前温度为T＝α×T，其中α是［0，1］间的冷却系数。

4）终止条件

计算终止条件可以设置为在连续若干个Metropolis链中都没有接受新解Si＋1，或者达到设定结束温度时结束计算，否则降温后继续进行等温操作。

2．3 算法优化

算法流程分为两大部分，分别是遗传计算和退火计算，两者在适度值计算后选择进入下代种群时产生结合，利用退火算法优化遗传的选择过程，具体流程图如图1所示。

在该流程中混合算法初始化设置包含种群规模M，进化代数MAXGEN，交叉概率Pc，变异概率Pm，初始温度T0，冷却系数α等。适度函数选择带权重的距离估算差值，初始化种群时利用DV－Hop算法计算出种群，随后进入GA算法流程求解每个染色体的适度值，在选择步骤中引入SA算法，通过扰动产生的新个体使用Metropolis准则接受进入下代种群，同时保持最优个体直接进入下代种群，其他个体进入交叉和变异环节，这样在新种群中可以保证每代的最优不变，最后进入降温环节，收敛搜索范围。

图1 混合遗传算法流程图

3 仿真与结果分析

3．1 环境设置

文章选择MATLAB2016作为对定位算法进行测试工具，计算机配置为Intel－i7处理器，8G内存，Windows7系统。仿真模拟物联网无线节点部署在100m×100m的区域内（位于第一象限），节点随机分布，总数为100，锚点比例10%，假设每个节点具有相同无线射程且布置完成后不再移动。遗传算法使用Sheffield工具箱，模拟退火算法使用GADST工具箱，算法参数设置见表1。

表1 GASA定位算法参数表

3．2 实验与分析

为了评价混合遗传算法的性能，本文将优化算法与传统的遗传算法做比较，两种算法选用相同的遗传参数，其中交叉概率＝0．8，变异概率＝0．02。从图2和图3中可见GASA算法在5代后获取了最优值，而传统GA算法要在8代后达到最优值，因而在函数寻优在收敛速度上GASA要优于传统的GA算法；同时在图3中最优值下降较快，表现出GA算法在早期出现适度值较高的个体后容易陷于早熟收敛，而GASA通过引入退火模拟算法中的Metropolis准则，有利于避免这种情况的发生，同时对小规模种群也能通过进化获取更优解。

图2 GASA算法优化过程图

图3 传统GA算法优化过程图

为了评价无线节点定位的精度，实验比较了混合遗传算法与改进DV－Hop算法的定位效果，两种算法选用相同的10%锚点比例和无线射程，所有节点在正方形区域内采用均匀随机分布。图4给出了10锚点的节点与90未知节点分布结构，图5给出了待定位的90个节点误差分布。可见采用混合遗传退火算法后未知节点定位最大误差为9．3%，最小误差为0．1%，节点平均误差在6．7%。表2列出了5次重复试验的两种定位算法的误差结果对比，结果显示混合遗传算法比DV－Hop算法在定位精确度上提高了20%左右。