ABSTRACT

As one of the key problems addressed in the application of wireless sensor networks (WSNs), sensor deployment is the significant methods of guaranteeing the quality of service in networks. In this paper, from the optimal node deployment, we introduce and analyze two kinds of algorithm to solve the optimal solutions.

Keywords:Wireless Sensor Networks, Sensor Deployment, Genetic Algorithm, Binary Particle Swarm Optimization Algorithm

智慧城市中无线网络成本最优节点部署机制

谭静静

潍坊学院，数学与信息科学学院，山东 潍坊

收稿日期：2018年10月25日；录用日期：2018年11月6日；发布日期：2018年11月16日

摘 要

节点部署作为无线传感器网络应用的一个核心问题，是保证服务质量的重要手段。本文主要从优化节点成本出发，介绍并分析了问题求解最优解的两类有效工具遗传算法、粒子群优化算法及其改进算法。

关键词 :无线传感器网络，节点部署，遗传算法，粒子群优化算法

Copyright © 2018 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着经济快速发展，城市人口持续增长，传统运行模式下的城市面临严峻的挑战，如：资源紧缺等。智慧城市的城市发展理念是基于城市中的多元业务传输的网络资源优化，是新型城市化的重要内容，也是对传统城市发展的改革 [1] 。智慧城市中无线网络基础通信设施部署优化问题可以归结为，在给定的平面上部署合适的网络节点，使信号不仅可以覆盖到所在的移动终端，同时保证最优的服务质量。

无线传感器网络(WSNs)最初是在军事领域中提出的。但随着无线通讯技术、微电子技术的发展，低功耗的传感器节点越来越廉价，无线传感器网络也从军事应用转向民用。在无线传感器网络中，网络节点部署问题是WSNs的一个基本问题，直接影响到服务质量 [2] [3] 。遗传算法、粒子群优化算法及其改进算法作为问题求最优解的有效工具，在WSNs节点部署优化中得到了广泛的应用 [4] [5] 。

2. 遗传算法

遗传算法GA (genetic algorithm)，也称进化算法，是受达尔文的进化论启发，借鉴生物进化模型提出的迭代式自适应随机搜索方法。通过模拟自然界中生物进化的发展规律，在人工系统中实现特定目标的优化。遗传算法步骤如下：

1) 选择初始生命种群；

2) 循环：评价种群中的个体适应度；以比例原则(分数高的挑中的概率也较高)选择下一种群；通过交叉和变异改变种群；

3) 直到停止循环的条件满足。

对于优化问题，染色体的设计如图1所示

图1. 染色体设计

其中 $z_i$ 表示待选的放置传感器节点的栅格位置， $k_i$ 表示不同传感器类型，取1表示某类型的传感器节点部署在该区域。利用编码映射，建立遗传算法中的初始种群为：

$\begin{array}{l}{p}_1=\left\{g_{11},g_{12},\cdots ,g_{1\left|N\right|\left|K\right|}\right\},\\ p_2=\left\{g_{21},g_{22},\cdots ,g_{2\left|N\right|\left|K\right|}\right\},\\ ⋮\\ p_i=\left\{g_{i1},g_{i2},\cdots ,g_{i\left|N\right|\left|K\right|}\right\},\\ ⋮\\ p_s=\left\{g_{s1},g_{s2},\cdots ,g_{s\left|N\right|\left|K\right|}\right\},\end{array}$

其中N表示候选的可放置传感器节点的栅格数，K表示传感器类型的数目。个体解的优劣通过“适应度”来评估，通过适应度函数，GA就能判断出一个解的优劣程度，适值高的个体具有较高的生存率。适值函数如下：

$f={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{c}_{ik}{x}_{ik}+M\left\{\min {\left\{0,\left\{{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{a}_{ijk}{x}_{ik}-b_i}}\right\}\right\}}^2\right\}}}$

这里M表示罚数因子，一般取任意大的正整数。

通常选择的变异策略和变异方法为：将不同类型的传感器相互交换，即随机将染色体任意位置的值取反，即将1取反变成0，将0取反变成1。

3. 粒子群优化算法

粒子群(POS)算法是由Kennedy和Eberhart等于1995年提出的种群智能算法。基于群体搜索策略，将粒子随机分布与搜索空间，一个粒子即代表一个空间点，粒子在飞行单位时间之后，根据自己和群体的历史记录不断改变自己的飞行速度(速率和方向)。粒子飞行速度主要受3个方面因素的影响：惯性因素、自我学习因素和社会学习因素。粒子在飞行过程中，通过不断改变速度来搜索最优位置，每个粒子的运动轨迹由整个种群的历史最好位置及其个体所经历的最好位置决定。粒子群算法具有概念简单、搜索效率高等特点。Eberhart通过优化可连续变化的二进制概率达到间接优化二进制变量的目的，提出二进制粒子群算法，解决了实际工程应用的组合优化问题。

标准POS中微粒i的各维度及粒子位置更新公式如下：

$V_{ij}\left(t+1\right)=W{V}_{ij}\left(t\right)+c_{1}r\left(p_{ij}\left(t\right)-x_{ij}\left(t\right)\right)+c_{2}r\left(g_{ij}\left(t\right)-x_{ij}\left(t\right)\right)$ (1)

$x_{ij}\left(t+1\right)=x_{ij}\left(t\right)+V_{ij}\left(t+1\right)$

其中 $V_{ij}$ 表示粒子的速度， $x_{ij}$ 表示粒子的位置，i表示第i个粒子，j表示在j方向上的分量。W表示惯性权重， $c_1$ 、 $c_2$ 为学习因子，r是在[0,1]范围之间均匀分布的随机数， $p_{ij}$ 表示粒子在历史上已经寻到的最优位置， $g_{ij}$ 表示种群中所有粒子所经历的最好位置，即全局最优最优解。为使粒子速度不至过大，通常会设定速度上限 $V_{\max }$ ：

$V_{ij}=\{\begin{array}{l}{V}_{\max },V_i>V_{\max },\\ -V_{\max }\text{,}{V}_i<-V_{\max }.\end{array}$

而二进制PSO中微粒i的各维速度更新公式同标准POS相同，但粒子位置更新公式却不同，为：

$x_{ij}\left(t+1\right)=\{\begin{array}{l}1,r<sig\left(V_{ij}\left(t+1\right)\right),\\ 0,r\ge sig\left(V_{ij}\left(t+1\right)\right),\end{array}$ (2)

其中 $sig\left(x\right)=\frac{1}{1+{\text{e}}^{-x}}$ 为sigmoid函数。从式(1)中，可以看出二进制POS中速度分量 $V_{ij}$ 决定了位置分

量 $x_{ij}$ 取1或0的概率， $V_{ij}$ 越大，则 $x_{ij}$ 取1的概率越大。 $V_{\max }$ 则能够限制 $x_{ij}$ 取1或0的概率， $V_{\max }$ 值越大，则算法接近于当前最优解附近的局部搜索，相反，则算法越接近于全局搜索。为了避免 $S\left(V_{ij}\right)$ 太接近于0.0或1.0，可以通过限制 $V_{ij}$ 的大小来实现。具体过程为：起始阶段，对粒子进行编码以及粒子群初始化，初始化粒子群的参数 $w,c_1,c_2$ 。在 $\omega$ 中引入自适应扰动机制，增强粒子群跳出局部最优的能力

$\omega ={\omega }_{\max }-\frac{{\omega }_{\max }-{\omega }_{\min }}{ite{r}_{\max }}\times iter\times {\left[1-\frac{g}{2g_{\max }}\right]}^g$ (3)

$g=\{\begin{array}{l}0,若最优解在进化\\ g+1,若最优解已G次没有进化,且g+1\le g_{\max },\\ g_{\max },其他情况.\end{array}$ (4)

其中 ${\omega }_{\max },{\omega }_{\min }$ 是 $\omega$ 的极大值和极小值，iter是当前的迭代次数， $ite{r}_{\max }$ 是总的迭代次数， $g_{\max }$ 是扰动因子g的极大值。粒子群的初始位置为随机的二进制向量，速度在[−4,4]之间取值，粒子速度为

$f={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{c}_{ik}{x}_{ik}+M\left\{\min {\left\{0,\left\{{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{k=1}{\overset{K}{\sum }}{a}_{ijk}{x}_{ik}-b_i}}\right\}\right\}}^2\right\}}}$ (5)

迭代判断：按照式(1)、(2)对粒子的速度和位置进行更新，利用式(5)进行粒子适应度评价，循环执行，直到粒子的适应度变化小于给定的阈值，或者算法迭代次数达到预定的迭代次数，算法停止。

4. 结论

每种算法都有各自的特点和应用环境，没有哪种最优的。总体说来，在保证网络容错性和健壮性的前提下，降低了网络部署的成本，提高了目标检测的质量，通过对上面各种定位算法的分析，认为对无线传感器网络成本最优节点部署机制的研究还存在以下技术挑战：首先，目前主要的算法集中于确定性静止异构节点部署方法，节点的位置预先计算后进行部署，而在实际中，节点的位置一般不能预先得到，今后的工作将集中解决在节点位置近似于最优位置时的部署优化问题。其次，研究的异构节点部署仅仅假定其感知半径不同，下一步的工作将解决在节点的寿命、状态切换能力、移动性能等不同情况下的节点优化部署问题。

基金项目

智慧城市中网络节点部署方案优化研究(2017GX025)。

文章引用

谭静静. 智慧城市中无线网络成本最优节点部署机制
Optimal Node Deployment Scheme for Wireless Network in Smart City[J]. 理论数学, 2018, 08(06): 672-675. https://doi.org/10.12677/PM.2018.86090

参考文献