蔡文郁,张美燕
(1.杭州电子科技大学电子信息学院,杭州310018;2.浙江水利水电学院电气工程系,杭州310018)
稀疏水下传感网中AUV数据移动收集技术研究*
蔡文郁1,张美燕2*
(1.杭州电子科技大学电子信息学院,杭州310018;2.浙江水利水电学院电气工程系,杭州310018)
由于水下传感器节点的水声通信距离有限、价格昂贵,水下传感器网络中一般采用稀疏方式部署,因此很难保证整体网络的连通性及数据采集效率。自主水下航行器AUV(Autonomous Underwater Vehicle)作为天然的移动数据采集平台,可以弥补固定Sink节点数据采集方式的缺陷。提出了一种基于移动AUV的水下传感网移动数据收集机制。以AUV覆盖区域内的传感器节点作为临时Sink节点,其他传感器节点以临时Sink节点为根节点,采用最小生成树MST(Minimum Spanning Tree)方法将传感数据传输到这些临时Sink节点,然后通过临时Sink节点将汇聚数据传输给AUV。随着AUV的自主移动轨迹,水下传感网的传感数据都能简单高效地被收集起来。仿真结果验证了该方法在保证网络能耗的前提下提高了数据采集效率。
稀疏水下传感网;传感数据收集;移动AUV;移动路径规划
EEACC:6150P doi:10.3969/j.issn.1004-1699.2016.10.020
水下传感器网络作为无线传感器网络的一个重要分支,已经成为一种具有广泛应用前景新型海洋观测技术[1-2]。水下传感器网络部署在极其复杂多变的水下环境中,采用了带宽受限、延时较大、信道不可靠的水声通信方式,因此与陆地无线传感网有很多的不同。众所周知,无线传感网通过多跳传输进行数据收集会引起能量空洞问题,而在水下三维传感网中也面临着同样的问题。水下监测区域范围大,水下传感器节点价格昂贵,一般都是稀疏部署,所以水下传感网无法保证全网节点全连通。传统的固定Sink节点方式有着无法克服的缺陷:越靠近Sink的节点承担了越多的数据流量,容易形成空洞区;网络不能保证全连通时有部分节点的数据无法提交,因此无法适用于水下传感器网络。AUV(自主水下航行器,Autonomous Underwater Vehicle)作为水下传感器网络中普遍采用的一种监测或运载设备,可以天然地作为移动Sink节点[3]。
目前一些学者提出了以移动Sink节点作为数据收集的新方式,可以解决均衡节点能量消耗以延长网络生存周期的问题,水下传感器网络属于一种特殊的三维传感网,具有其自身特点,目前还没有得到深入研究。本文研究了一种基于移动AUV的水下传感网数据移动收集技术:AUV采集覆盖区域内的传感器节点作为临时Sink节点,其他传感器节点以临时Sink节点为树根节点,采用最小生成树MST(Minimum Spanning Tree)将传感数据传输到该临时Sink节点,然后通过Sink节点将汇聚数据传输给AUV。由于归属于最小生成树集合时会产生冲突,本文利用位置最近的方式实现了节点的最优归属。最终通过软件仿真,验证了本文所提出算法在保证网络能耗均衡的前提下,提高了网络的数据采集效率。
以固定Sink节点进行数据收集的传统技术会导致近Sink节点耗费更多能量,产生能量空洞现象。目前有一些研究者对无线传感器网络的动态Sink数据采集进行了研究,利用Sink节点的动态移动特性提高网络能量特性。张希伟等人[4]提出利用移动数据收集器进行传感器网络中感知数据的收集,可以有效地减少传感器将数据发送到静止基站的传输跳数,节约网络的能量,延长网络寿命。同时,文献[4]分类总结了近年来提出的一些典型的基于MDC(Mobile Data Collection)的算法和协议,着重讨论了MDC在网络能量、延迟、路由和传输等方面带来的性能变化。Can Tunca等人[5]对目前的分布式动态Sink节点路由方式做了综述,对几十种层次型和非层次型动态路由机制进行了分析,提出了相应的优缺点及开放性研究方向。
除了上述综述性文献以外,王章权等人[6]研究了一种优化网络生存时间的Sink节点移动路径选择算法(MPSA),在MPSA算法中,将单跳传输的无线传感网监测区域分成多个大小一致的网格,Sink节点可移动到任一网格中心,停留收集单跳最大通信范围内的传感节点数据。郜帅等人[7]以满足时延要求和最小化网络整体能耗为优化目标,提出了一种基于虚拟点优先级的移动sink路径优化选择方法。徐佳等人[8]通过建立最大化最小能耗概率模型,提出了一种MMPEC数据收集方法,对网络中子节点与汇聚节点之间的路径长度进行分布式优化。惠晓威等人[9]提出了一种基于移动Sink的簇头节点数据收集算法(MSRDG),该算法基于图论原理,在满足时延性的条件下,综合考虑了普通节点到簇头节点路由和移动Sink遍历路经选取的问题,构建了一条通过的簇头节点尽可能多的移动轨迹。任条娟等人[10]提出Sink节点移动的无线传感网生存时间优化算法(LOAMSN),该算法分析Sink节点移动时的流量平衡约束、最大传输速率约束、节点能耗约束等约束条件,将生存时间优化问题转化成优化模型。最新文献[11]提出以具有自主运动能力的AUV作为移动收集节点,从而优化数据收集的能量消耗,但是没有利用水下传感器网络的拓扑架构实现能量优化传输。
针对稀疏特性的三维水下传感器网络,目前还缺乏相应研究成果。上述面向无线传感器网络的动态Sink算法机制也无法直接应用于三维水下传感器网络,因此本文研究面向稀疏水下传感网的AUV数据移动采集技术。
基于AUV的移动数据收集机制如图1所示,具有自主移动能力的AUV穿梭于水下传感网中,通过广播方式唤醒覆盖区域内的水下传感器节点,然后进行传感数据的收集,数据采集完之后AUV移动到另一个位置再次进行数据收集。
图1 AUV移动数据收集机制
考虑到水下传感网的实际特点,假设本文算法研究的模型如下:①所有的水下传感器节点具有相同的通信半径、初始能量和能耗模型。②由于水下区域范围较大,水下传感器节点的部署具有稀疏性,难以完全连通。③移动AUV具有可控制的移动性,其能量、容量、计算能力等均不受限制。④由于AUV移动速度远大于海洋洋流效应,因此认为水下传感器节点为相对静止。⑤在无线通信范围内的水下传感器节点间可以相互通信,交互必要的数据。⑥休眠的水下传感器节点的通信功能处于开启状态,可以随时接收到广播数据。⑦水下传感器节点和AUV都具有有限的通信距离,无法覆盖整个监测区域。⑧水下传感器节点可通过各种定位算法获取自身的精确坐标位置。
水下传感器节点被随机地部署在长宽高为L×L×L的水下三维区间内,水下三维传感网的拓扑模型可以用有向图G(V⋃VAUV,E⋃EAUV)来表示,其中V⋃VAUV为所有传感器节点加上AUV的节点集合,E⋃EAUV为所有节点边及节点与AUV之间链路的集合。在水下三维传感器网络的实际应用中,用于数据收集的AUV往往事先设置好运动轨迹,AUV依靠惯性导航实现预定轨迹移动,因此本文研究点主要是调度水下传感器节点的数据传输路径实现网络生存周期的最大化。本文研究算法的思路如下:当水下传感器节点不处于AUV的覆盖范围时,传感数据都保存在节点的缓存中,此时可认为传感器节点处于休眠状态;当传感节点收到AUV的广播信号时,即处于AUV的最大通信范围内时,水下传感器节点进入工作状态,并以自己为树根节点广播构造MST树消息,收到消息的树叶节点通过MST多跳通信的方式将数据发送给AUV。
假设水下传感器节点具有一致的初始能量,网络生存周期定义为从开始运行到第一个节点由于能量耗尽而失效的时间。
在第p次移动时,如果只有一个节点或者没有节点与AUV节点位置重合,即:
对于网络中的任意节点,必须满足如下流量平衡约束条件,
其中lij和lji分别表示节点i到节点j和节点j到节点i的链路,V0表示节点i的邻居节点,fij和 fji分别为节点i发送给节点 j和节点 j发送给节点i的数据总量,为节点i在 p时刻通过节点k发送给AUV的数据总量,tp为p时刻AUV巡航停留时间,λi为节点i的数据产生率。
在经典的网络流量模型下,在生命周期内节点能量消耗必须小于总能量:
最优化目标如下:
上述网络生存时间优化模型属于典型的线性规划LP(Linear Programming)问题[12]。
如图2所示的具体实现过程如下:AUV采集覆盖区域内存在有传感器节点Sink_A和 Sink_B,Sink_A和 Sink_B各自作为 Cluster_A簇和 Cluster_B簇的临时Sink节点,其他归属于Cluster_A簇和 Cluster_B簇范围的传感器节点以 Sink_A和Sink_B节点作为树根节点,采用最小生成树(MST)将传感数据传输到该临时Sink_A和Sink_B节点,然后将汇聚所得的数据传输给AUV。
图2 AUV移动数据收集机制
在本文算法中,假设传感器节点都已知自身的坐标位置,因此,当传感器节点接收到多个临时Sink节点的MST组网数据包时,会面临最优MST域的选择,本文使用了地理位置最近原则来进行裁决。本算法的工作过程如下:
①每个传感器节点Si广播Beacon信息(包括自身ID值及剩余能量值)MiB=<IDi,Ei,TTLi>,TTLi表示往返时间,其一跳邻居节点收到后将发送回Reply消息,从而获取其一跳邻居节点集 NBi=表示传感器节点的通信距离。
②移动AUV广播Wake UP消息(包括时间间隔及自身坐标值):MtW=<Tt,Xt,Yt,Zt>;
③接收到AUV广播消息的传感器节点成为Root节点,标志自身为Root节点,广播MST消息:MkM=<IDk,xk,yk,zk,TTLk>;
④接收到MST消息的传感器节点,根据MST算法选择加入相应Root节点的最小生成树集合,然后广播转发MST消息,从而形成多个最小生成树集合;
⑤每个最小生成树集合节点根据MST路径发送数据到相应的Root节点,Root节点将汇总的传感器数据发送给AUV;
⑥AUV收集完数据后,自主移动到下一个坐标位置,重复步骤②。
以上算法的简化模型为选择单个节点作为Root节点,此时所有传感器节点的数据通过最小生成树发送到Root节点,该Root节点将汇总数据发送给AUV。该简化算法实现更加简单,可以离AUV的最近节点作为Root节点,虽然Root节点会消耗很多能量,但是由于随着AUV的运动轨迹,Root节点会逐渐替换,因此可以达到能量均衡的效果。
上述方法存在如下问题:如图3所示,由于AUV覆盖范围的改变,有可能形成同一个簇重复出现在AUV覆盖范围的情况,因此在每次充当临时Sink节点后必须记录,以免重复进行数据采集,保证在算法运行的每轮间隔,每个传感器节点都可以发送一次传感数据。
图3 同簇最小生成树变更情况
本文采用Matlab构建仿真平台,对本文算法进行性能分析。仿真环境的主要参数为:Nsensor个传感器节点随机分布在半径为10×10×10的三维区域内,传感器节点的覆盖半径Rcover。水声通信的速率一般为几千波特率,因此传感器节点每次的数据包长度设置为m=512 bit。最小生成树的构成方式采用了Kruskal算法[13]。由于水下传感器网络采用稀疏部署,因此无法保证每个传感器节点都可以满足连通性要求,这些孤立的传感器节点无法进行数据采集。仿真采用的节点能量模型如下:假设每个传感器节点的初始能量都为E0=10 J,能量消耗模型采用常用的平方消耗模型,仿真的具体参数如下公式所示:
AUV运动轨迹采用了随机运动模型,移动一个时间间隔后悬停一段时间,用于采集传感数据,本文将AUV的每次运动周期定义为一轮,网络生命周期采用仿真轮数值来表示。
其中(x(t+1),y(t+1),z(t+1)和(x(t),y(t),z(t)分别代表AUV在t+1时刻和t时刻的位置,Vauv表示AUV的随机运动速度,以Step为最大值随机分布,θxy和θz分别表示X-Y平面和Z平面的随机方向,仿真场景及AUV运动轨迹如图4所示,图4(a)为最大步进值Step=2时100轮的运动轨迹,图4(b)为最大步进值Step=1时200轮的运动轨迹。覆盖情况及AUV运动轨迹如图5所示,图5(a)为Nsensor=50,Rcover=1时的网络三维覆盖情况,图 5(b)为 Nsensor=20,Rcover=2时的网络三维覆盖情况。移动AUV下传感数据单MST收集如图6所示,图6(a)为Rcover=2时的单MST采集树,图6(b)为Rcover=2.5的单MST采集树,从仿真图可以发现:覆盖半径越小,未并入MST采集树的单独节点越多。移动AUV下传感数据多条MST收集如图7所示,图7(a)为2条MST采集树,图7(b)为3条MST采集树,图7(c)为4条MST采集树,图7(d)为5条MST采集树。
本文通过移动AUV进行传感数据采集,用以提高网络的能量效率。本文所提出的算法与固定Sink节点方式进行了网络生命周期的比较,假设固定Sink节点的坐标为(5,5,5),网络生命周期定义为网络中出现至少一个节点耗尽能量时的仿真轮数,该网络生命周期的定义要求所有网内的传感器节点都要正常工作,否则就认为水下传感器网络无法完成监测功能而失效。
通过多次仿真取平均值,固定Sink节点最小生成树方式(称为对比算法)与本文算法的网络生命周期对比结果如图8所示,本文算法网络失效周期为254轮,对比算法的网络失效周期为62轮,可见本文提出的算法可以大幅度提高网络生命周期。
网络失效时节点剩余能量情况如图9所示,当本文算法网络失效时,网络平均剩余能量只剩余至4.571 2 J,而应用对比算法网络失效时,网络平均剩余能量还剩余8.221 2 J。因此可以发现,应用了本文算法后,网络中众多节点的能量能够得到充分利用,由于本文算法发挥了自主运动AUV进行移动数据采集的优势,因此避免了三维网络中的能量空洞现象,提高了整体网络的能耗性能。
图4 仿真场景及AUV运动轨迹
图5 不同覆盖情况及AUV运动轨迹
图6 移动AUV下传感数据单MST收集
图7 移动AUV下传感数据多MST收集
图8 网络生命周期(Nsensor=100,Rcover=2.5)
图9 网络失效时节点剩余能量(Nsensor=100,Rcover=2.5)
本文针对水下传感器网络中大范围区域数据收集的难题,利用具有自主运动能力的AUV作为移动Sink节点实现传感数据的动态收集。以AUV覆盖区域内的传感器节点作为临时Sink节点,其他传感器节点采用最小生成树(MST)将传感数据传输到临时Sink节点进行汇总。下一步的工作将研究利用多个AUV实现水下传感器网络的高效数据收集,重点研究多AUV之间的协同作业技术,以进一步提高水下传感器网络数据收集的效率。
[1]Akyildiz I,Pompili D,Melodia T.Underwater Acoustic Sensor Networks:Research Challenges[J].Ad Hoc Networks,2005,3(3):257-279.
[2]Cui Junhong,Kong Jiejun,Mario Gerla,et al.Challenges:Building Scalable Mobile Underwater Wireless Sensor Networks for Aquatic Applications[J].IEEE Network,Special Issue on Wireless Sensor Networking,2006,20(3):12-18.
[3]Hollinger G,Choudhary S,Qarabaqi P,et al.Underwater Data Collection Using Robotic Sensor Networks[J].IEEE Journal on Selected Areas in Communications,2012,30(5):899-911.
[4]张希伟,戴海鹏,徐力杰,等.无线传感器网络中移动协助的数据收集策略[J].软件学报,2013,24(2):198-214.
[5]Can Tunca,Sinan Isik M,Yunus Donmez,et al.Distributed Mobile Sink Routing for Wireless Sensor Networks:A Survey[J].IEEE Communications Surveys&Tutorials,2014,16(2):877-897.
[6]王章权,陈友荣,尉理哲,等.优化网络生存时间的Sink节点移动路径选择算法[J].传感技术学报,2014,27(3):409-415.
[7]郜帅,张宏科.时延受限传感器网络移动Sink路径选择方法研究[J].电子学报,2011,39(4):742-747.
[8]徐佳,冯鑫,杨富贵,等.最大化最小能耗概率的移动Sink无线传感器网络数据收集方法[J].电子学报,2015,43(12):2470-2475.
[9]惠晓威,刘彦每.WSN数据收集中移动Sink的路径规划和簇头节点选取问题的综合研究[J].传感技术学报,2014,27(1):118-122.
[10]任条娟,杨海波,陈友荣.Sink节点移动的无线传感网生存时间优化算法[J].传感技术学报,2012,25(5):683-690.
[11]Mariam Akbar,Nadeem Javaid,Ayesha Hussain Khan,et al.Efficient Data Gathering in 3D Linear Underwater Wireless Sensor Networks Using Sink Mobility[J].Sensors,2016,16(3):404-415.
[12]Gu Yu,Ji Yusheng,Li Jie,et al.ESWC:Efficient Scheduling for the Mobile Sink in Wireless Sensor Networks with Delay Constraint[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(7):1310-1320.
[13]Kruskal J B.On the Shortest Spanning Subtree of A Graph and the Traveling Salesman Problem[J].Amer Math Soc,1956,7:48-50.
蔡文郁(1979-),男,博士,副教授,主要从事物联网、无线传感网及嵌入式技术研究。主持和参与国家自然科学基金2项、浙江省自然科学基金3项、浙江省公益性行业专项3项,国家863计划项目2项、国家海洋局行业专项1项、浙江省重大科技专项1项,横向课题10余项。近年来发表论文40余篇,被SCI/EI收录20余篇,申请专利及软著40余项,授权30余项;
张美燕(1983-),女,讲师,从事无线传感网络、新型能源技术、物联网技术等研究,主持浙江省自然科学基金2项,浙江省公益性行业专项2项,浙江省水利厅科技项目1项,参与浙江省厅级项目多项。近年来发表论文20余篇,被三大索引收录论文10余篇,申请发明专利和实用新型专利20余项。
Sensory Data Gather Technology with Mobile AUV for Sparse Underwater Sensor Networks*
CAI Wenyu1,ZHANG Meiyan2*
(1.School of Electronics&Information,Hangzhou Dianzi University,Hangzhou 310018,China;2.School of Electrical Engineering,Zhejiang University of Water Resources and Electric Power,Hangzhou 310018,China)
Due to limited communication distance and high price of underwater acoustic nodes,underwater sensor networks are generally deployed in a sparse manner.Therefore,it is hard to guarantee overall network connectivity and data collection efficiency.AUV,which is a natural platform for mobile data collection,can overcome the shortcomings of data acquisition with fixed Sink node.This paper proposed a mobile data collection mechanism with mobile AUV for underwater sensor networks.In the proposed mechanism,sensor nodes covered by AUV are regarded as temporary Sink nodes.The other sensor nodes transmit sensory data to temporary Sink nodes using minimum spanning tree(MST)transmission method.Finally,temporary Sink nodes gather data and deliver them to AUV.Along with the movement trajectory of AUV,sensory data of the whole networks can be collected in a simple and efficient way.The simulation results verified that the proposed algorithm can improve data collection efficiency in the constraint of network energy consumption.
sparse underwater sensor networks;sensory data gathering;mobile AUV;mobile path planning
TP393
A
1004-1699(2016)10-1589-07
项目来源:浙江省自然科学基金项目(LY15F030018,LY16F030004)
2016-04-23修改日期:2016-06-15