工程科学与技术   2017, Vol. 49 Issue (2): 160-168
辅助定位信标节点的移动路径规划算法研究
陈友荣1,2, 万锦昊2, 苏子漪1, 张瑞1     
1. 浙江树人大学 信息科技学院, 浙江 杭州 310015;
2. 常州大学 信息科学与工程学院, 江苏 常州 213164
基金项目: 国家自然科学基金资助项目(61501403);浙江省自然科学基金资助项目(LY15F030004);浙江省公益性技术应用研究计划项目资助(2016C33038)
摘要: 为快速实现监控区域内所有传感节点的定位,利用辅助定位信标节点的移动,提出无线传感网中辅助定位信标节点的移动路径规划算法(MPPA)。在MPPA算法中,考虑由多个六边形网格组成的监控区域,分析sink节点的移动特点,考虑其移动路径中停留位置只是六边形网格的顶点和中心,不在同一位置停留,相邻3个停留位置不共线以及每一个网格至少被3个以上不同停留位置覆盖等约束条件,提出信标节点的移动路径约束和传感节点定位约束,并建立其移动路径规划模型。根据邻居停留位置的信息素浓度决定下一个停留位置,根据蚂蚁选择的路径释放和挥发信息素。经过蚁群算法的多次迭代,可获知能覆盖所有网格的信标节点最优移动路径。信标节点沿着该路径移动时,传感节点可获知信标节点的不同位置信息,收集通信时的RSSI值,采用Kalman滤波算法降低通信噪声,采用最大似然估计算法计算自身位置坐标。仿真结果表明:MPPA算法可根据网格中心和顶点的位置,收敛于移动距离最短且能实现监控区域任何位置上传感节点定位的最优移动路径。MPPA算法降低了信标节点的移动路径长度和停留位置个数,降低了网络启动后所有传感节点获知自身位置所需要的时间,并将传感节点平均定位误差保持在较低的水平。在一定的条件下,MPPA算法比SCAN、DOUBLE_SCAN、HILBERT、CIRCLES和ZSCAN算法更优。
关键词: 无线传感网    传感节点    位置    路径规划    
Study on Movement Path Planning Algorithm of Auxiliary Locating Beacon Node
CHEN Yourong1,2, WAN Jinhao2, SU Ziyi1, Zhang Rui1     
1. College of Info. Sci. and Technol., Zhejiang Shuren Univ., Hangzhou 310015, China;
2. School of Info. Sci. & Eng., Changzhou Univ., Changzhou 213164, China
Abstract: To quickly realize the localization of all sensor nodes in the monitoring area, a movement path planning algorithm of auxiliary locating beacon node in wireless sensor networks (MPPA) was proposed by using movement of auxiliary locating beacon node.In MPPA algorithm, the monitoring area consisting of multiple hexagonal grids was considered.Analyzing mobile characteristic of sink node, four constraint conditions were assumed:1) Sojourn locations of sink node only were centers and vertexes of hexagonal grids; 2) The sojourn location was not stayed twice by sink node; 3) Three adjacent sojourn locations were non-collinear; 4) Each grid was covered by at least three different sojourn locations.Movement path constraints of beacon node and localization constraint of sensor nodes were then proposed.Movement path planning model was flowingly established.Next sojourn location was judged according to the pheromone concentration of neighbor sojourn locations and the pheromone was released and volatilized according to the selected path of ant.After several iterations of ant colony algorithm, the optimal path of beacon node covering all grids was obtained.When beacon node moved along the path, in each sensor node different sojourn location information of beacon node was obtained and RSSI value of communication was collected.Kalman filter algorithm was used to reduce communication noise and maximum likelihood estimation algorithm was used to calculate its own location coordinates.Simulation results showed that according to the location information of centers and vertexes of grids, MPPA algorithm converged to optimal movement path with shortest movement distance and realized the localization of sensor nodes at any location in the monitoring area.MPPA algorithm reduced the movement path length of beacon node and the number of sojourn locations.Meanwhile, it reduced the time that sensor nodes need to know their own locations, and maintained localization error at a low level.Under certain conditions, MPPA algorithm outperforms SCAN, DOUBLE_SCAN, HILBERT, CIRCLES and ZSCAN algorithms.
Key words: wireless sensor networks    sensor nodes    localization    path planning    

无线传感网 (wireless sensor networks,WSNs) 由大量部署的传感节点组成,可感知,收集和处理网络覆盖范围内传感节点的信息,是一个多跳自组织网络。它可应用于军事、工业、家居、医疗、海洋等领域,特别是在自然灾害监测、预警、救援等紧急情况,应用前景广阔[1]

在很多无线传感网的应用中,所有信息的收集需要传感节点的准确位置,因此定位是WSNs的基本技术和核心技术之一。目前,卫星定位系统如全球定位系统 (global positioning system,GPS) 和北斗定位系统,是一种可使用的户外定位方法。但是由于WSNs的节点能量有限,而且卫星定位模块工作电流需要几十毫安,其能耗相当于节点的无线通信能耗。如果所有传感节点都安装卫星定位模块,则传感节点的能耗和成本较高,不适用于环境监测等需要长期监测的应用,因此需要一种可降低传感节点能耗和应用成本的定位新方法。

在WSNs中,部分节点安装卫星定位模块。利用这些节点的位置信息,计算其他节点的位置坐标是一种新的方法。目前,该方法的研究取得一定的成果。有些学者侧重于利用可获知自身位置的静止节点,研究移动节点定位算法。如文献[2]提出一种无线传感网移动目标的消息有效位置预测算法。该算法根据消息通信开销,提出一个高斯马尔可夫参数估计器,用于预测移动目标的位置,并启动相关传感节点监控移动目标。文献[3]提出一种室内移动目标的位置预测算法。该算法采用最大似然估计 (maximum likelihood estimation,MLE) 计算当前移动目标位置,根据路径规划模型和历史位置数据,预测下一个时刻的移动目标位置。文献[4]提出一种位置估计算法。该算法采用松散的时间同步机制,根据本地时间和位置估计公式,预测汇聚节点的位置。文献[5]采集RSSI (received signal strength indication) 值,采用Kalman滤波算法降低信号噪声,采用线上半监督支持向量回归算法计算移动目标的位置。文献[6]将节点分成多个簇,提出基于分簇的移动节点定位算法。该算法根据与同一个簇内移动节点通信的RSSI值,采用质心定位算法进行位置计算。文献[2-6]为定位移动目标,需要一定数量的安装了卫星定位模块的静止节点作为信标节点,其系统成本较高。

因此,另一些学者侧重于利用少量可获知自身位置的信标节点,研究辅助定位信标节点的移动路径和静态节点定位算法。如文献[1]分析了SCAN、DOUBLE_SCAN、HILBERT等信标节点的多种经典移动路径。文献[7]提出了圆形移动路径 (CIRCLES),可减少移动路径的共线性停留位置。针对信标节点移动造成的分布不均衡,文献[8]提出基于蒙特卡洛方法的移动传感网节点定位优化算法。该算法筛选出定位精度高的节点作为临时锚节点,协助其他节点定位,并通过待定位节点的蒙特卡洛盒和粒子滤波条件实现节点的精确定位。文献[9]根据周围传感节点的信息,采用虚拟力的原理计算信标节点的移动路径,提出一种导标动态移动策略。文献[10]将监控区域分成多个网格,提出一种信标节点的移动算法。未定位节点根据与信标节点通信的RSSI值和三点定位方法,计算自身的位置。文献[11]提出一种信标节点的修正Hibert移动路径。该路径可提高待定位节点的定位精度。文献[12]提出可辅助定位的移动信标节点高级路径规划机制 (ZSCAN)。根据该移动轨迹可定位所有部署的传感节点。

文献[8]没有利用信标节点的移动性这个关键特点,而文献[7, 9-12]都提出了信标节点的移动路径,即信标节点在不同位置上停留,为静态节点的定位提供多个位置的坐标、RSSI值等信息。但是这些移动路径长度是否已经达到最短路径,仍需要进一步研究。因此在上述文献的基础上,采用最优化理论研究信标节点的移动路径,提出了一种无线传感网中辅助定位信标节点的移动路径规划算法 (movement path planning algorithm of auxiliary locating beacon node in wireless sensor networks, MPPA)。MPPA算法将监控区域分成若干个大小一致的六边形网格,并根据从左到右、从上到下的原则对每一个六边形网格和顶点进行编码。MPPA算法分析网格和顶点编码、信标节点移动和传感节点的定位,提炼信标节点移动经过的路径、下一个停留位置集合等参数的数学表达式,提出移动路径约束和节点定位约束,提出信标节点的移动路径优化模型。其中,移动路径约束包括由六边形网格的顶点和中心组成的最优路径移动约束,相邻3个停留位置不共线约束和最优移动路径中不存在相同的停留位置约束。在节点定位约束中,每一个网格至少被3个以上不同停留位置覆盖,则该网格内传感节点可根据信标节点的信息计算自身的位置。为了快速搜索优化模型的最优解,MPPA算法采用蚁群优化算法 (ant colony optimization,ACO)。在ACO算法的路径搜索过程中,根据顶点和网格中心的信息素,提出下一个停留位置选择方法和所选路径的网格覆盖计算方法。根据每轮迭代的最短路径,释放和挥发相关信息素,并经过蚁群算法的多次迭代,可获知能覆盖所有网格的信标节点最优移动路径。信标节点沿着该路径移动时,传感节点可获知信标节点的不同位置信息,收集通信时的RSSI值,采用Kalman滤波算法降低通信噪声,采用最大似然估计算法计算自身位置坐标。

1 算法原理

在MPPA算法中,假设无线传感网在2维监控区域上均匀分布[12]。在无线传感网中,存在部署时自身位置未知的静止传感节点和一个可移动的信标节点。信标节点安装GPS、北斗等任一卫星定位模块,可获知自身的位置坐标。如果存在多个信标节点,则可划分监控区域。每个信标节点负责其中部分区域,则多个信标节点的移动路径规划问题转换成单个信标节点的移动路径规划问题,MPPA算法也适用。MPPA算法原理见图 1

图1 MPPA算法原理 Fig. 1 MPPA algorithm principle

图 1所示,传感节点随机均匀分布在监控区域内且需要获知自身的位置。信标节点将监控区域分成若干个大小一致的六边形网格[13],并根据从左到右、从上到下的原则对每一个六边形网格和其顶点进行编码。如grid(i, j) 表示从左开始计数的第i列中从下到上计数的第j个六边形网格,ding(i, j) 表示从左开始计数的第i列中从下到上计数的第j个顶点。信标节点从初始网格中心开始,从自身所在网格的顶点中选择一个未停留过的顶点,并在该顶点上停留一段时间发送自身的位置信息后选择具有该顶点且未停留过的网格中心作为下一时刻的停留位置。由于相邻3个停留位置不能共线,因此在选择停留位置时,需要删除与前面两个位置共线的位置。信标节点不停移动和发送自身位置信息,直到所有传感节点都能计算自身位置坐标。但是, MPPA算法仍需要解决以下2个问题:

一是, 如何运用数据公式表达信标节点的移动路径约束、节点定位约束等约束条件,如何建立移动路径长度最短的优化模型。

二是, 如何采用蚁群优化算法求解优化模型,获得信标节点的最优移动路径。下面讨论如何具体解决这2个问题。

1.1 优化模型建立

根据信标节点的移动路径约束和节点定位约束,建立以下优化模型。求解该模型 (1),可获知信标节点的最短移动路径且保证所有传感节点都能获知自身的位置坐标。

$ \min ({N_{\rm{L}}}) $ (1)
$ {\rm{s}}{\rm{.t}}{\rm{.}}\;\boldsymbol{P} = \{ {p_1}, {p_2}, \cdots, {p_{{N_{\rm{L}}}}}\} $ (1a)
$ {p_{g + 1}} \in {G_g}, g = 1, 2, \cdots, {N_{\rm{L}}}-1, $ (1b)
$ {p_g} \ne {p_v}, \forall {p_g}, {p_v} \in \boldsymbol{P}{\rm{ }}且{\rm{ }}g \ne v, $ (1c)
$ {\lambda _{{p_g}, {p_{g + 1}}, {p_{g + 2}}}} = 0, g = 1, 2, \cdots, {N_{\rm{L}}}-2, $ (1d)
$ {s_{ij}} \ge 3, \forall i, j $ (1e)

其中: NL表示信标节点经过的停留位置个数。P={p1, p2, …, pNL}表示信标节点的移动路径,即经过的停留位置集合。集合P中每一个元素表示信标节点的停留位置,是一个1×3的向量 (k1k2k3)。该向量的第1个元素k1表示停留位置的列数;第2个元素k2表示停留位置的行数;第3个元素k3表示停留位置的类型,取值0、1。如果k3=0,则表示该元素是六边形网格中心; 否则, 表示该元素是六边形网格的顶点。Gg表示停留位置pg的可选下一个停留位置集合。${\lambda _{{p_g}, {p_{g + 1}}, {p_{g + 2}}}}$表示3个停留位置pgpg+1pg+2是否共线的标识符,为1表示共线,为0表示不共线。sij表示网格grid(i, j) 被不同位置上的信标节点覆盖的次数。

优化模型中,主要有移动路径约束 (式 (1a)~1(d)) 和节点定位约束 (式 (1e))。其中,式 (1a) 表示信标节点移动经过的最优路径,由六边形网格的顶点和中心组成。式 (1b) 表示当信标节点在位置pg停留时,只从位置集合Gg中选择下一个停留位置。如图 1所示,当前位置为网格中心时,下一个停留位置为该网格的顶点,即集合Gg为:

$ {G_g} = \left\{ \begin{array}{l} \{ ding\left( {1, 2j-1} \right), ding\left( {1, 2j} \right), \\ \;\;\;\;\;ding\left( {1, 2j + 1} \right)\}, {p_g} = c\left( {1, j} \right);\\ \{ ding\left( {n-1, 2j-1} \right), ding\left( {n - 1, 2j} \right), \\ \;\;\;\;ding\left( {n - 1, 2j + 1} \right)\}, {p_g} = c\left( {n, j} \right);\\ \{ ding\left( {i - 1, 1} \right), ding\left( {i - 1, 2j} \right), ding\left( {i, 1} \right), \\ \;\;\;\;ding\left( {i, 2} \right)\}, {p_g} = c\left( {i, 1} \right)且i{\rm{为偶数}};\\ \{ ding\left( {i - 1, 2m} \right), ding\left( {i - 1, 2m + 1} \right), \\ \;\;\;\;\;ding\left( {i, 2m} \right), ding\left( {i, 2m + 1} \right)\}, \\ \;\;\;\;\;{p_g} = c\left( {i, m + 1} \right)且i为偶数;\\ \{ ding\left( {i - 1, 2j - 2} \right), ding\left( {i - 1, 2j - 1} \right), \\ \;\;\;\;ding\left( {i - 1, 2j} \right)\}, \{ ding\left( {i, 2j - 2} \right), \\ \;\;\;\;ding\left( {i, 2j - 1} \right), ding\left( {i, 2j} \right)\}, 其他i为偶数;\\ \{ ding\left( {i - 1, 2j - 1} \right), ding\left( {i - 1, 2j} \right), \\ \;\;\;\;ding\left( {i - 1, 2j + 1} \right)\}, \{ ding\left( {i, 2j - 1} \right), \\ \;\;\;\;ding\left( {i, 2j} \right), ding\left( {i, 2j + 1} \right)\}, 其他i为奇数; \end{array} \right.{\rm{ }} $ (2)

其中,c(i,j)表示六边形网格grid(i,j)的中心,m表示监控区域内第1列网格的数量,n表示监控区域内网格的列数且是奇数。当停留位置为顶点时,下一个停留位置为具有该顶点的网格的中心,即集合Gg为:

$ {G_g} = \left\{ \begin{array}{l} \{ c\left( {i, 1} \right), c\left( {i + 1, 1} \right)\}, {\rm{ }}{p_g} = ding\left( {i, 1} \right);\\ \{ c\left( {i, m} \right), c\left( {i + 1, m + 1} \right)\}, \\ {p_g} = ding\left( {i, 2m + 1} \right)且i为奇数;{\rm{ }}\\ \{ c\left( {i, m + 1} \right), c\left( {i + 1, m + 1} \right)\}, \\ {p_g} = ding\left( {i, 2m + 1} \right)且i为偶数;{\rm{ }}\\ \{ c\left( {i, j/2-1/2} \right)\}, c\left( {i, j/2 + 1/2} \right), \\ c\left( {i + 1, j/2 + 1/2} \right)\}, \\ 其他i为奇数, j为偶数;\\ \{ c\left( {i, j/2} \right), c\left( {i + 1, {\rm{ }}j/2} \right), c\left( {i + 1, j/2 + 1} \right)\}, \\ 其他i为奇数, j为偶数;\\ \{ c\left( {i, j/2 + 1/2} \right)\}, c\left( {i + 1, j/2-1/2} \right), \\ c\left( {i + 1, j/2 + 1/2} \right)\}, \\ 其他i为偶数, j为奇数;\\ \{ c\left( {i, j/2} \right)\}, c\left( {i, {\rm{ }}j/2} \right), c\left( {i + 1, j/2} \right)\}, \\ 其他i为偶数, j为奇数 \end{array} \right. $ (3)

式 (1c) 表示信标节点不在同一个位置停留2次以上,则路径P中不存在相同的停留位置。由于传感节点采用最大似然估计算法计算自身的位置坐标, 需要3个以上且不能共线的信标节点位置信息,因此,式 (1d) 表示路径P中任意3个相邻停留位置不在同一条直线上。式 (1e) 表示每一个网格至少被3个以上不同停留位置覆盖。当停留位置为网格中心时,该网格和其邻居网格的sij加1。当停留位置为网格顶点时,具有该顶点的网格sij加1。

1.2 优化模型求解

蚁群优化算法 (ACO) 是一种模拟真实蚂蚁觅食行为的著名启发式算法。在ACO算法中,蚂蚁在一个结构图上移动寻找解决方案。这种搜索行为使ACO算法适合解决组合优化问题[14]。因此采用ACO算法搜索模型 (1) 的最优解,具体内容如下。

多个蚂蚁在初始停留位置上根据式 (2) 和 (3) 寻找下一个停留位置集合。处理该集合,选择未停留过且不能与前两个停留位置共线的位置,组成新的停留位置集合。当信标节点停留在网格顶点时,根据网格中心的信息素浓度决定下一个停留位置。当信标节点停留在网格中心时,根据网格顶点的信息素浓度决定下一个停留位置。则t时刻蚂蚁k从位置v到位置w的概率Pvwk为:

$ P_{vw}^k\left( t \right) = \left\{ \begin{array}{l} [f_w^{\rm{C}}\left( t \right)]/\sum\limits_{w \in {N_{\rm{v}}}} {[f_w^{\rm{C}}\left( t \right)]}, 当前位置是网格顶点;\\ [f_w^{\rm{D}}\left( t \right)]/\sum\limits_{w \in {N_{\rm{v}}}} {[f_w^{\rm{D}}\left( t \right)]}, 当前位置是网格中心 \end{array} \right. $ (4)

其中,fwC(t) 表示t时刻网格中心w的信息素, fwD(t) 表示t时刻网格顶点w的信息素。根据概率Pvwk,采用转轮赌法选择下一个时刻停留位置,将该位置坐标添加到已选择路径Py,并采用如图 2所示的覆盖计算方法分析该路径是否覆盖整个监控区域。

图2 网格覆盖计算原理 Fig. 2 Grid covering calculation principle

图 2所示,黑色六角星表示信标节点。当信标节点停留在网格中心时,其所在的网格和邻居网格内所有传感节点都能接收到信标节点的位置信息包,则这些网格被信标节点的停留位置覆盖。当信标节点停留在网格顶点时,具有该顶点的网格被信标节点的停留位置覆盖。如果监控区域内所有网格被信标节点移动路径中3个以上且不共线的停留位置覆盖,则找到一条满足约束条件 (1a)~(1e) 的路径,停止寻找,否则继续寻找路径。

为快速寻找到最短路径,在完成一轮路径寻找后,即每一个蚂蚁寻找到自身的路径,选择其中一条最短路径作为该轮迭代的最短路径。分析该路径的长度,如果大于或等于历史最短路径,只挥发所有位置的信息素;否则,对该路径上的相关停留位置信息素进行释放,且挥发所有位置的信息素。

$ {f_v}\left( {t + 1} \right) = \left\{ \begin{array}{l} \left( {1-\rho } \right){f_v}\left( t \right) + \Delta {f_v}\left( t \right), {\rm{ }}Len\left( t \right) < LenBest;\\ \left( {1-\rho } \right){f_v}\left( t \right), Len\left( t \right) \ge LenBest \end{array} \right. $ (5)
$ \Delta {f_v}\left( t \right) = \left\{ \begin{array}{l} Q/Len\left( t \right), 位置v在移动路径上;\\ 0, 其他 \end{array} \right. $ (6)

其中,fv(t) 为t时刻位置v的信息素,Δfv(t) 为t时刻蚂蚁沿着该路径移动时在该位置v上释放的信息素,Q表为信息素释放总量,ρ为信息素挥发因子,Len(t) 为t时刻移动路径的长度,LenBest为迭代过程中出现的最优移动路径长度。总之,经过多次迭代,可寻找到模型 (1) 的最优解,即信标节点的移动路径。

2 算法实现

网络启动后,如图 3所示,信标节点循环执行以下步骤,获得其最优移动路径。

图3 信标节点的移动路径规划流程图 Fig. 3 Movement path planning flowchart of beacon node

步骤1:初始化算法中当前蚂蚁k=1、迭代次数初值m1=1、信息素挥发因子ρ、信息素释放总量Q、最大迭代次数M1、蚂蚁个数K、监控区域边长、六边形网格边长等参数。

步骤2:根据监控区域边长和六边形网格高度,计算第1列六边形网格个数,计算全覆盖监控区域的六边形网格列个数和行个数。对所有六边形网格的中心和顶点分别采用从左到右、从下到上的原则进行编码,并计算六边形网格中心和顶点的位置坐标,获得相关矩阵向量。其中,第1列六边形网格个数是大于或者等于监控区域边长和六边形网格高度相除的最小整数值。如果第1列六边形网格个数是奇数,则网格列个数是其值加2;否则,网格列个数是其值加1。奇数列的网格行个数是第1列六边形网格个数,偶数列的网格行个数是第1列六边形网格个数加1。

步骤3:根据式 (2) 和 (3),计算每一个网格中心和网格顶点的可选下一个停留位置集合。

步骤4:初始化蚂蚁k的初始位置和已选路径Py

步骤5:蚂蚁k分析下一个停留位置集合中所有位置元素,如果当前路径Py添加了位置元素后,不符合约束条件 (1a)~(1d),则删除该位置元素,最终建立新的下一个停留位置集合。如果该新的下一个停留位置集合为空集,则进入“死胡同”,跳到步骤4,在初始位置重新寻找路径; 否则, 根据式 (4) 选择下一个停留位置,将该停留位置添加到已选路径Py中。

步骤6:判断已选路径Py是否全覆盖监控区域内所有网格。如果Py未全覆盖监控区域内所有网格,跳到步骤5, 继续寻找; 否则, 记录当前选择路径和其长度。如果k < K,则还有蚂蚁未寻找到路径,k=k+1,下一个蚂蚁开始寻找路径,跳到步骤4;否则, 跳到步骤7。

步骤7:计算所有蚂蚁寻找的路径长度,选择长度最短路径作为第m1轮的最优路径,并记录该最优路径和长度Len(m1)。如果Len(m1)≥LenBest,挥发所有位置的信息素,否则LenBest=Len(m1), 通过式 (5)~(6) 更新所有位置的信息素。如果m1 < M1,则k=1,m1=m1+1,跳到步骤4;否则, 结束算法, 输出最优移动路径。

分析MPPA算法的时间复杂性。如图 3所示,MPPA算法主要是M1K个蚂蚁寻找能全覆盖监控区域的移动路径。蚂蚁在路径寻找过程中,每选择一个停留位置都需要判断是否覆盖所有网格,即一个蚂蚁的路径寻找的时间复杂度是Θ(mn)。因此,MPPA算法的时间复杂度是Θ(M1Kmn)。根据上述获得的移动路径,传感节点的定位方法如下:信标节点沿着获得的移动路径,重复执行以下操作。当信标节点在某一个位置停留时,通过北斗定位模块获取自身的经纬度坐标,转化成地球坐标后,广播自身的位置信息包。当停留一段时间后,移动到下一个停留位置,广播自身最新的位置信息包;传感节点接收信标节点的位置信息包,获取信标节点ID、位置坐标、链路RSSI值等信息,并将这些信息放入信标节点位置信息表中。同时,传感节点分析接收到信标节点的不同位置信息。当有3个以上且不共线位置的信息,采用Kalman滤波算法降低RSSI值的噪声,采用最大似然估计算法计算自身的位置坐标。

3 算法仿真 3.1 仿真参数和算法性能参数

在算法仿真中,选择以下参数计算信标节点移动路径长度、停留位置个数、传感节点平均定位误差和平均周围停留位置个数:监控区域边长60、80、100、120、140、160 m,六边形网格高度20 m,传感节点个数100,节点有效位置信息包的通信半径30 m,信息素释放总量Q为600,信息素挥发因子ρ为0.2,最大迭代次数M1为300,蚂蚁个数K为30,初始位置为网格grid(2, 1) 的中心。其中,信标节点移动路径长度定义为信标节点沿着所选路径移动的路程。停留位置个数定义为移动路径中信标节点停留的次数。传感节点的平均定位误差定义为所有传感节点根据接收到的信标节点位置信息,采用最大似然估计算法计算自身的位置坐标和真实坐标的误差平均值。传感节点的平均周围停留位置个数定义为所有传感节点获知信标节点停留位置个数的平均值。

3.2 仿真结果分析

选择3.1节中的参数,考虑所有算法都能全覆盖监控区域,分别计算MPPA、SCAN[1]、DOUBLE_SCAN[1]、HILBERT[1]、CIRCLES[7]和ZSCAN[12]的信标节点移动路径长度、停留位置个数、传感节点平均定位误差和平均周围停留位置个数。并以边长为120 m的监控区域为例,比较这些算法的移动路径。如图 4所示,SCAN算法采用类似矩形波的移动路径全扫描整个监控区域。但是SCAN算法在监控区域4个顶点附近容易出现覆盖盲区且多个停留位置共线,因此其移动间隔不宜过大。DOUBLE_SCAN算法采用两倍的SCAN算法移动间隔,从水平方向和垂直方向进行移动,尽量不让停留位置共线。HILBERT算法的停留位置个数是4的幂次方。随着监控区域边长的增加,其停留位置个数增加较多。CIRCLES算法采用圆形的路径遍历整个监控区域,但是也较难覆盖到监控区域4个顶点附近区域。ZSCAN算法可覆盖到整个监控区域,但是也同样存在HILBERT算法的问题。同时,这5个算法只是根据某一个规律移动,其移动路径长度不是最优的。MPPA算法将120 m×120 m区域分成45个六边形网格。根据这些网格中心和顶点位置,选择了49个停留位置组成的移动路径,其长度比其他算法短且能实现监控区域任何位置上传感节点的定位。

图4 各算法移动路径比较 Fig. 4 Movement path comparison of algorithms

图 5所示,在求解模型 (1) 的200次迭代中,在第82次迭代,MPPA算法能寻找到该模型的一个移动距离最短的路径,之后一直收敛于该移动路径,因此MPPA算法是收敛的。

图5 MPPA算法收敛图 Fig. 5 Convergence figure of MPPA algorithm

图 6所示,当监控区域边长较小时,可选择的停留位置不多,因此这6个算法的移动路径长度差距不是特别大,MPPA算法的移动路径长度略低与其他算法的移动路径长度。当监控区域边长较大时,MPPA算法建立优化模型,采用蚁群优化算法寻找到最优路径,在全覆盖监控区域的同时,降低了移动路径长度。SCAN、DOUBLE_SCAN、HILBERT、CIRCLES和ZSCAN算法需要信标节点出现在监控区域各个区域,这增加了其移动路径长度。尤其当监控区域边长为160 m且节点感知范围一定时,HILBERT和ZSCAN算法为全覆盖整个监控区域,提高了自身的停留位置个数阶数,其移动路径急剧增加。总之,相比于SCAN、DOUBLE_SCAN、HILBERT、CIRCLES和ZSCAN算法,MPPA算法的移动路径长度最短。

图6 信标节点移动路径长度比较 Fig. 6 Movement path length comparison of beacon node

MPPA算法采用蚁群优化算法寻找若干个可覆盖整个监控区域的停留位置。如表 1所示,其信标节点的停留位置个数小于SCAN、DOUBLE_SCAN、HILBERT和CIRCLES算法的停留位置个数,且随着监控区域边长的增大,其停留位置个数下降较明显。由于信标节点的移动时间由在停留位置上的停留时间和路径移动时间组成,而且MPPA算法的移动路径长度短且停留位置个数少,因此MPPA算法降低了网络启动后所有传感节点获知自身位置所需要的时间。

表1 信标节点停留位置个数比较 Tab. 1 Number comparison of beacon node's sojourn locations

表 2所示,由于MPPA算法的停留位置只满足每一个网格被3个以上的停留位置覆盖,且信标节点的移动路径长度较短,相对其他算法的停留位置个数也较少,因此传感节点的平均可接收的信标节点停留位置个数也最少。

表2 传感节点平均周围停留位置个数比较 Tab. 2 Average number comparison of sojourn locations surrounding the sensor nodes

在算法仿真中,采用最大似然估计算法计算自身的位置坐标。当可获知的停留位置个数较多时,最大似然估计算法比较准确。由于MPPA算法中传感节点可接收到的信标节点停留位置个数小于其他算法,因此如图 7所示,MPPA算法的传感节点平均定位误差略高于SCAN、DOUBLE_SCAN、HILBERT和ZSCAN算法的平均定位误差,但是其平均定位误差相差不是特别大。当监控区域边长是80、100、120、140和160 m时,MPPA算法的传感节点平均定位误差低于CIRCLES算法的平均定位误差。因此,MPPA算法将传感节点的平均定位误差保持在较低的水平。

图7 传感节点平均定位误差比较图 Fig. 7 Average localization error comparison of sensor nodes

4 结论

考虑无线传感网中信标节点的移动,提出一种辅助定位信标节点的移动路径规划算法。首先,提出算法假设和移动路径优化模型。其次,采用蚁群优化算法求解该优化模型,获得可行解,即信标节点的最短移动路径。信标节点沿着该路径移动,传感节点获知信标节点不同位置的信息包,计算自身的位置坐标。接着,提出算法的实现步骤。最后,给出算法的仿真参数和性能参数,比较MPPA、SCAN、DOUBLE_SCAN、HILBERT、CIRCLES和ZSCAN算法的性能。

MPPA算法根据监控区域的边长,划分了多个六边形网格,建立和求解优化模型,获得最优解。MPPA算法降低了信标节点的移动路径长度和停留位置个数,降低了网络启动后所有传感节点获知自身位置所需要的时间,并将传感节点平均定位误差保持在较低的水平。

MPPA、SCAN、DOUBLE_SCAN、HILBERT、CIRCLES和ZSCAN算法都比较适用于节点均匀分布的无线传感网。当节点密集分布在某一个子区域时,这些算法的移动路径仍覆盖整个监控区域,其部分停留位置覆盖的网格内不存在传感节点,存在多余的停留位置。因此非均匀分布的无线传感网下辅助定位信标节点的移动路径规划算法研究是一种新的挑战。下一阶段目标是利用非均匀分布的传感节点的通信信息,引导信标节点的移动,删除不必要的停留位置。

参考文献
[1]
Han Guanjie, Xu Huiui, Duong T Q, et al. Localization algorithms of wireless sensor networks:A survey[J]. Telecommun System, 2013, 52(4): 2419-2436. DOI:10.1007/s11235-011-9564-7
[2]
Liu Binghong, Chen Minlun, Tsai Mingjie. Message-efficient location prediction for mobile objects in wireless sensor networks using a maximum likelihood technique[J]. IEEE Transactions on Computers, 2011, 60(6): 865-878. DOI:10.1109/TC.2010.217
[3]
Gao Peng, Shi Weiren, Zhou Wei, et al. A location predicting method for indoor mobile target localization in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2013, 2013(2013): 1-11.
[4]
Zhu Chuan, Wang Yao, Han Guangjie, et al. LPTA:location predictive and time adaptive data gathering scheme with mobile sink for wireless sensor networks[J]. The Scientientific World Journal, 2014, 2014(2014): 1-14.
[5]
Yoo J, Kim H J. Target localization in wireless sensor networks using online semi-supervised support vector regression[J]. Sensors, 2015, 15(6): 12539-12559.
[6]
Wang Yan, Shan Xinxin, Jiang Wei. The mobile nodes location technology in wireless sesnsor network[J]. Chinese Journal of Sensors and Actuators, 2011, 24(9): 1326-1330. [王焱, 单欣欣, 姜伟. 无线传感网络中移动节点定位技术研究[J]. 传感技术学报, 2011, 24(9): 1326-1330.]
[7]
Huang Rui, Zaruba G V.Static path planning for mobile beacons to localize sensor networks[C]//Proceedings of the Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops.Piscateway:IEEE, 2007:323-330.
[8]
Mei Ju, Chen Di, Xin Ling. Optimized localization scheme for mobile wireless sensor networks based on Monte Carlo method[J]. Chinese Journal of Sensors and Actuators, 2013, 26(5): 689-694. [梅举, 陈涤, 辛玲. 基于蒙特卡洛方法的移动传感网节点定位优化算法[J]. 传感技术学报, 2013, 26(5): 689-694.]
[9]
Liu Kezhong, Chen Weibo, Zhan Zhen, et al. Beacon dynamic movement strategy in node localization for wireless sesnor networks[J]. Journal of Computer Research and Development, 2012, 49(11): 2494-2500. [刘克中, 陈巍博, 占真, 等. 无线传感网络节点定位中的导标动态移动策略[J]. 计算机研究与发展, 2012, 49(11): 2494-2500.]
[10]
Huang Kuofeng, Chen Poju, Jou E. Grid-based localization mechanism with mobile reference node in wireless sensor networks[J]. Journal of Electronic Science and Technology, 2014, 12(3): 283-287.
[11]
Farmani M, Moradi H, Dehghan S M, et al. The modified Hilbert path for mobile-beacon-based localization in wireless sensor networks[J]. Transactions of the Institute of Measurement and Control, 2013, 36(7): 916-923.
[12]
Rezazadeh J, Moradi M, Ismail A S, et al. Superior path planning mechanism for mobile beacon-assisted localization in wireless sensor networks[J]. IEEE Sensors Journal, 2014, 14(9): 3052-3064.
[13]
Hung Liling, Huang Yuwei, Lin Chuncheng. Temporal coverage mechanism for distinct quality of monitoring in wireless mobile sensor networks[J]. Ad Hoc Networks, 2014, 21(21): 97-108.
[14]
Lin Yin, Zhang Jun, Chung H S, et al. An ant colony optimization approach for maximizing the lifetime of heterogeneous wireless sensor networks[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2012, 42(3): 408-420. DOI:10.1109/TSMCC.2011.2129570