Voronoi-BFO水面移动基站路径规划算法

赵 青, 夏 娜, 束 强, 伊 君

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

Voronoi-BFO水面移动基站路径规划算法

赵 青, 夏 娜, 束 强, 伊 君

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

在水面无线传感器网络(surface wireless sensor networks,SWSNs)中,传感器节点布置稀疏,节点间距离大于节点通信距离,移动基站需有效收集节点数据信息。完整收集节点数据,使基站移动路径最短或近似最短是一个关键问题。文章在节点间距离大于节点通信距离的前提下,利用Voronoi图理论生成基站移动候选子路径,并使用细菌觅食优化(bacterial foraging optimization，BFO)算法求解,以使规划路径最短或近似最短,网络通信能耗降低。结果表明,该方法在不同网络规模情况下均具有最短或近似最短的路径长度,且网络通信能耗低。

水面无线传感器网络;Voronoi图;细菌觅食优化算法;移动基站;路径规划

水面无线传感器网络(surface wireless sensor networks,SWSNs)是由分布在水面环境中的多个浮标式传感器节点组成的无线传感器网络[1]。该网络中的节点配以多种传感器采集水面或水下数据信息,并以射频通信方式传输信息和采集数据,可用于海洋、河流及湖泊等环境监测领域,具有重要的应用价值[2]。

SWSNs的组成结构如图1所示。其中水面传感器节点(surface sensor node,SSN)用于收集水面或水下数据,并通过无线射频通信传输数据;移动基站 (mobile base station,MBS)负责采集整个网络中SSN信息。SWSNs与节点密集部署的陆地无线传感器网络相比,通常有着传感器节点布置稀疏的特点,即节点通信半径小于节点间距离,导致无法采用节点间的多跳路由方法进行数据的汇聚,而采用MBS遍历各个SSN进行数据采集是当前主要的数据汇聚方法。在监测水域中规划出一条基站移动路径,不仅可以收集到所有SSN的数据,而且可以达到路径最短和网络节能。

图1 水面无线传感器网络组成结构

近年来,学者们针对无线传感器网络提出了多种基站移动方法。按数据收集方式不同,可分为基于节点单跳通信的基站移动方法[3-5]和基于节点多跳路由的基站移动方法[6-8]两类。以单跳通信的方式,传感器节点的数据信息直接发送至基站,不需要其他节点转发。这种方式有效降低了节点的通信能耗,且容易实现。但文献[3-4]中单基站是随机移动的,其随机性无法保障完整收集数据,同时也无法预估完整数据收集的路径长度和耗时。文献[5]采用多基站收集数据，存在着资源浪费、不易统筹等问题。而文献[6-8]中基于多跳路由的移动方法,在节点布置稀疏的SWSNs中,因为节点间难以直接通信,不易构建节点间的通信路由,所以多跳路由在实际SWSNs中难以使用。

本文研究了基于节点单跳通信的基站移动方法,提出了一种Voronoi图(维诺图)构造细菌觅食优化 (bacteria foraging optimization,BFO)算法的水面移动基站路径规划方法。首先利用Voronoi图理论生成基站移动的候选子路径,然后采用BFO算法求解最优路径。算法中设计的合法解判别方法同时具有将非法解改造成合法解的功能。仿真结果证明了该方法具有生成路径短和网络通信能耗低的优点。

1 网络及通信模型

水面上传感器节点随机分布,位置固定且已知。MBS根据规划路径在该二维平面内移动并进行节点的数据信息采集。假设满足下列条件:

(1) 节点布置稀疏,即节点间的距离大于节点的通信半径,节点间不能直接通信。

(2) MBS和传感器节点的通信以请求-应答方式为主。MBS到达某位置,广播数据请求消息,收到请求的节点由休眠模式切换至工作模式,并将自身的数据发送给MBS,完成数据传输即刻切换至休眠模式。短时间内节点不再响应基站的数据请求消息。

(3) 传感器节点的能耗主要由处理器、传感器和无线通信模块3个部分的能耗组成,其中无线通信的能耗占据绝大部分,故传感器节点的能耗可近似等于其通信能耗。本文采用典型的自由空间通信能耗模型[9],如图2所示,传感器节点的能耗为:

(1)

其中,k1、k2分别为节点收发的数据量;cs为传感器节点收发电路的能耗系数;εs为传感器节点发射功率的放大系数;d为通信距离。

图2 传感器节点的能耗模型

(4) MBS能耗主要包括移动能耗和通信能耗，其中移动能耗主要由移动距离决定，通信能耗与传感器节点通信能耗模型相同，则MBS在整个移动和数据收集过程中的能耗为:

(2)

其中,P为移动基站航行功率;l为移动路径长度;v为航行速度;n为传感器节点个数;q为移动基站广播次数;k1为移动基站一次广播消息的数据量;k2为单个传感器节点发送来的数据量;cB为基站发射或接收电路的能耗系数;εB为基站发射功率放大系数;R为基站广播的通信半径,R足够大。

2 水面移动基站路径规划方法设计

2.1 Voronoi图理论生成基站移动候选子路径

通过Voronoi图理论划分SWSNs结构,得到一系列基站移动的候选子路径。Voronoi图又叫泰森多边形或Dirichlet图,是计算几何中重要的几何结构,具有很高的应用价值[10]。它是由许多连接两邻点线段的垂直平分线段构成的连续多边形所组成。n个在二维平面上位置不一的点,根据最邻近原则划分平面结构,每个点其最邻近区域相关联。

依据SWSNs中n个节点的位置,按照Voronoi图划分平面的方法,将整个二维区域划分为n个子区域,且形成一系列的Voronoi边。

在监测区域A中有4个传感器节点s1、s2、s3、s4,它们的位置如图3所示。按照Voronoi图划分区域的方法,可以将监测区域A划分为4个子区域,并形成5条Voronoi边e1、e2、e3、e4、e5,如图3所示。

图3 基于传感器节点位置生成的Voronoi图

定理1 基站在Voronoi边上收集相邻传感器节点(距离该Voronoi边最近的传感器节点)数据,可以达到传感器节点通信能耗最小。

证明 假设一条Voronoi边ek,其相邻传感器节点为si和sj,如图4a所示。由Voronoi图理论可知,ek是si和sj的垂直平分线,即si和sj距离o点的距离相等,表示为d。当基站沿着Voronoi边移动到o点时,广播数据请求消息。si和sj收到消息,并将自身的数据发送给移动基站。

节点si接收消息并发送数据的能耗为:

其中,k1为节点si接收消息的数据量;k2为节点si发送的数据量。

节点si和sj总的通信能耗为:

节点si和sj总的通信能耗为:

图4 基站沿Voronoi边和任意边收集传感器节点数据

将上述2种情况下的通信能耗进行比较，计算可得:

因为di+dj=2d,所以有:

即E′≥E。可见,基站在Voronoi边上收集相邻传感器节点数据,可以达到传感器节点通信能耗最小。证毕。

条件3 路径长度最短。

2.2 基于BFO算法求解最优的候选子路径集合

BFO算法是模拟大肠杆菌(E.coli)觅食行为的一种新型仿生启发式优化算法[11]。由于其在求解优化问题过程中对初值不敏感,无需优化对象的梯度信息,且具有分布并行搜索和全局寻优能力强等优点。BFO算法的离散化形式非常适合于求解本文的组合优化问题。

2.2.1 细菌的一维二进制编码

BFO算法作为一种群智能优化算法,通过细菌种群的进化过程(趋化、复制和迁徙)完成对最优解的搜索。种群由若干细菌组成,细菌通常以数值编码的形式表达。对于本文优化问题,设计的细菌一维二进制编码为x=(x1x2… xm),其中x1,x2,…,xm分别对应了m条候选子路径,即m条Voronoi边,xi=1(1≤i≤m)表示第i条Voronoi边被选择,xi=0表示该Voronoi边未被选择。

2.2.2 细菌的初始化

随机产生m个二进制数,构成一个细菌编码x=(x1x2… xm)。但是该编码很可能不满足上述条件1和条件2,即所选出的Voronoi边不一定能顾及到所有传感器节点,或不能构成一条连续路径。可以通过以下方法判断编码x=(x1x2… xm)能否满足条件1和条件2。

定义1 Voronoi边-节点关系矩阵。将监测区域中所有Voronoi边及其顾及到的传感器节点用关系矩阵O加以描述。具体形式如图5所示。

图5 Voronoi边-节点关系矩阵O

Voronoi边-节点关系矩阵O=[oij],其中，i=1,2,…,n；j=1,2,…,m。oij=1表示Voronoi边ej可以顾及到节点si；oij=0则表示Voronoi边ej未顾及到节点si。

若x·O≥(k1k2k3…kn)T,k1,k2,k3,…,kn均为大于等于1的整数,则满足条件1。

现使用深度优先搜索算法[12]将细菌编码所对应的Voronoi边的端点遍历以判断其组成的路径是否连续。若连续,则满足条件2。

定义2 在非连续的路径图中,选择最近的端点相连,形成的边称为虚拟Voronoi边。

算法步骤为:

步骤1 将选中子路径顶点(vi,…,vs,bj,…,bt)初始化,visited[vi]=false。

步骤2 从某条选中子路径的顶点vi出发,并将visited[vi]=true。

步骤3 若vi的邻接点vk存在,判断其访问状态,若visited[vk]=false,则设置visited[vk]=true。依次检验vk的邻接点是否存在；若存在，则判断其访问状态,若为false，则置其状态为true。重复此步骤。

步骤4 检验是否所有点满足visited[vk]=true；若是，则路径连续。

步骤5 若仍有顶点未被访问到,则建立虚拟Voronoi边使路径连续,使非可行解变为可行解。

条件3即为求

(3)

其中，ci为Voronoi边ei的长度；i=1,2,…,m。

2.2.3 改进BFO算法

本文将BFO算法应用于MBS路径规划模型的组合优化问题中并作出如下改进:

(1) 路径规划模型的组合优化是一个多约束条件的整数规划问题。一般情况下细菌的取值变量是变量取值范围内的任意实数,但本文将所有Voronoi边的选择情况作为细菌变量,使用BFO算法应注意所有变量取值应为0或1,以解集选中情况x([x1x2… xm])组成的空间矢量θ([θ1θ2… θm]T)作为一个细菌,采用 (3) 式的值对应搜索空间中细菌的健康状态，即适应度函数J(θ),即在满足条件1和条件2的情况下，路径长度越短，则适应度函数值越小。

在BFO算法中使用Sigmoid函数,将其各维如下离散成0～1的二元数值。BFO算法在趋向性操作中细菌i的位置更新描述如下:

(4)

(5)

(2) 判断每个细菌生成的解中每一维是否满足条件2,若不满足,则继续游动,直到满足条件2或达到额定游动次数Ns，完成一次趋化操作。若满足约束条件,则根据(3)式计算细菌的适应度函数值。

改进BFO算法步骤为:

步骤1 给定Voronoi边-节点关系矩阵O,确定细菌种群规模S和细菌向量长度m。

步骤2 设置趋化、复制和迁徙操作的次数Nc、Nre、Ned,按照本文方法初始化细菌种群和迁徙概率Ped。

步骤4 细菌种群进行复制操作。细菌执行完趋化操作后,根据适应度函数计算出所有细菌的健康度函数值并按从大到小的顺序进行排列,保留较大的Sr个并进行复制,淘汰较小的Sr个。

步骤5 细菌种群执行迁徙操作。复制操作

完成后,生成一个随机概率并将其与Ped比较,若小于Ped，则执行细菌的迁徙操作,并重新执行趋化操作。

步骤6 判断循环结束条件,若满足,则结束,并输出结果。

3 仿真实验分析

为了验证本文Voronoi-BFO水面移动基站路径规划方法的正确性和有效性,在Matlab7.0平台上进行了3组规模不同的实验,并将该方法与其他文献中的具有代表性的路径规划方法相比较。

实验1 100 m×100 m 监测水域,50个水面传感器节点{s1,s2,…,s50}。

实验2 100 m×100 m监测水域,75个水面传感器节点{s1,s2,…,s75}。

实验3 100 m×100 m监测水域,100个水面传感器节点{s1,s2,…,s100}。

本文采用通信能耗模型,其中参数分别为cs=50 nJ/bit,cB=200 nJ/bit,εs=100 pJ/(bit·m2),εB=500 pJ/(bit·m2),k1=50 bit,k2=1 000 bit,P=10 W,v=1 m/s。其中,cs和εs的取值参考文献[9]。

3.1 可行性分析

在3组实验中,采用本文方法规划的基站移动路径如图6所示。

图6 不同点路径规划图

由图6可以看出,采用本文提出的Voronoi-BFO水面移动基站路径规划算法,可以求解并优选出基站移动路径。基站按照该路径进行移动,可以收集所有传感器节点的数据,并保证路径连续,且路径长度分别为507.354、563.496、610.63 m。

3.2 与相关方法的性能比较

文献[3]的方法是一种随机的基站移动方法,且当基站靠近传感器节点时收集节点数据。文献[5]研究无线传感器网络中移动基站遍历固定位置的传感器节点,将路径规划直接转化为旅行商问题(travelling salesperson problem,TSP)求解。

3.2.1 路径长度比较

在3组实验中,本文方法、文献[3]方法和文献[5]方法分别规划出的基站的移动路径见表1所列。由表1可知,本文方法所规划的路径长度明显小于文献[3]和文献[5]的方法。在基站移动速度一定的情况下,采用本文方法移动基站可以用较短的时间完成对监测区域中传感器数据的收集,以至基站移动路径长度短、能耗更低。

表1 3种方法所规划的路径长度 m

3.2.2 网络总能耗比较

在3组实验中,MBS分别按照本文方法、文

献[3]方法和文献[5]方法规划出的路径收集传感器节点数据,基站能耗包括移动能耗和通信能耗，具体见表2所列。

由表2可见,在3组实验中本文方法的网络总能耗均是最小的,这主要得益于本文方法规划出了最短的基站移动路径,从而有效减小了基站的移动能耗。

因为在文献[3]方法和文献[5]方法中,基站均移动至传感器节点处收集数据,所以节点通信能耗较低；而本文方法在一定程度上发挥了节点的通信能力,大幅度减小了基站移动路径长度和能耗,使网络总能耗达到了最低。

表2 3种方法网络总能耗比较

4 结 论

本文将Voronoi图理论引入到MBS路径规划的研究中,完善了相关理论方法，并将矩阵问题与节点数据收集完整相结合,将该问题具象化,采用BFO算法可有效解决该问题模型。大量仿真实验结果表明，本文方法在不同网络规模下均能求出最短或近似最短路径,因此可作为SWSNs路径规划的有效方法。下一步工作是在实际水面环境中进行理论的方法测试,并拓展其综合应用。

[1] GKIKOPOULI A,NIKOLAKOPOULOS G,MANESIS S.A survey on underwater wireless sensor networks and applications[C]//Proceedings of the 20th Mediterranean Conference on Control & Automation.[S.l.]:IEEE,2012：1147-1154.

[2] DAVIS A,CHANG H.Underwater wireless sensor networks [J].Oceans,2012,4(Ⅶ)：1-5.

[3] SHAH R C,ROY S,JAIN S,et al.Data MULEs：modeling and analysis of three-tier architecture for sparse sensor networks [J].Ad Hoc Networks,2003,1(2/3)：215-233.

[4] CHATZIGIANNAKIS I,KINALIS A,NIKOLETSEAS S.Efficient data propagation strategies in wireless sensor networks using a single mobile sink [J].Computer Communications,2008,31(5)：896-914.

[5] LIANG W F,SCHWEITZER P,XU Z C,et al.Approximation algorithms for capacitated minimum forest problems in wireless sensor networks with a mobile sink[J].IEEE Transactions on Computers,2013,62(10):1932-1944.

[6] 张建军,万磊,翟琰,等.基于能量区域代理机制的移动Sink 路由算法[J].合肥工业大学学报(自然科学版),2015,38(1)：34-39.

[7] 陈涛,郭得科,罗雪山,等.一种基于移动基站的无线传感器网络数据收集方法[J].国防科技大学学报,2011,33(2):49-53.

[8] WANG Z M,BASAGNI S,MELACHRINOUDIS E,et al.Exploiting sink mobility for maximizing sensor networks lifetime.[C]//Proceedings of the 38th Hawaii International Conference on System Sciences.[S.l.:s.n.],2005：1-9.

[9] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks [C]//Proceedings of the 33rd Hawaii International Conference on System Sciences.[S.l.:s.n.],2000：10-20.

[10] 夏娜,倪成春,徐朝农,等.逆向捕获时间差的Voronoi声源定位机制[J].通信学报,2013,34(11)：140-152.

[11] PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems,2002,22(3)：52-67.[12] TARJAN R.Depth-first search and linear graph algorithms[J].SIAM Journal on Computing,1972,1(2)：146-160.

(责任编辑 闫杏丽)

A path planning algorithm for water surface mobile base station based on Voronoi diagram and bacterial foraging optimization algorithm

ZHAO Qing, XIA Na, SHU Qiang, YI Jun

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In surface wireless sensor networks(SWSNs), the sensor nodes are arranged sparsely, the distance between nodes is greater than the communication distance of the nodes, and the mobile base station needs to collect data of the nodes effectively. So the way to collect data completely so that the path is the shortest or the shortest approximately is a key problem. On the premise that the distance between nodes is greater than communication distance of the nodes, the base station moving candidate sub-path is generated by using the Voronoi diagram theory, and the bacterial foraging optimization(BFO) algorithm is proposed to solve the problem, so as to achieve a shortest path or approximate shortest path with lower energy consumption of network communication. The effectiveness of the proposed approach at different network scales is validated through extensive simulations.

surface wireless sensor networks(SWSNs); Voronoi diagram; bacterial foraging optimization(BFO) algorithm; mobile base station(MBS); path planning

2015-11-16；

2016-01-05

国家自然科学基金资助项目(61100211；61003307)；教育部新世纪优秀人才支持计划资助项目(NCET-13-0768)和安徽省杰出青年科学基金资助项目(1408085J05)

赵 青(1990-),女,湖北荆州人,合肥工业大学硕士生; 夏 娜(1979-)，男，安徽芜湖人，博士，合肥工业大学教授，硕士生导师.

10.3969/j.issn.1003-5060.2016.12.009

TP393.09

A

1003-5060(2016)12-1633-06