基于类二叉树的圆锥型UWSNs的研究*

2015-01-12 09:04张长江
传感器与微系统 2015年9期
关键词:二叉树浮标活跃

陈 军, 张长江

(1.浙江师范大学 数理与信息工程学院,浙江 金华 321004;2.浙江工业职业技术学院 设计与艺术学院,浙江 绍兴 312000)



基于类二叉树的圆锥型UWSNs的研究*

陈 军1,2, 张长江1

(1.浙江师范大学 数理与信息工程学院,浙江 金华 321004;2.浙江工业职业技术学院 设计与艺术学院,浙江 绍兴 312000)

针对水下无线传感器网络(UWSNs)能量损耗严重,节点分布不均匀无规律等现象,提出以各个水面浮标节点为顶点,构建一种圆锥型UWSNs信息网(传感器节点能根据能量大小而移动),并将其活跃节点与备选节点抽象成类二叉树结构,简化了拓扑控制与路由传递。传感器节点采集信息后,能通过活跃节点沿着类二叉树的右节点传递到浮标节点。通过Matlab实现了算法的性能仿真测试,探讨了同样水深的层数为4,6,8的类二叉树数据包传递率,结果显示:层数越多,传递率越高;将6层类二叉树的圆锥型UWSNs算法和深层路由(DBR)算法进行比较,结果显示,该算法数据包传递率高,能耗低。

水下无线传感器网络; 二叉树结构; 活跃节点; 浮标节点

0 引 言

水下无线传感器网络[1](underwater wireless sensor networks,UWSNs)通常用来对水体环境监测、水下目标探测等应用,将收集的数据做处理,以声波传输的方式传送到汇水上浮标节点。UWSNs是由具有声学通信与计算能力的传感器节点构成的水下监测网络系统,随着无线传感器技术的发展,当前UWSNs的研究已经引起了学术界的高度重视,针对UWSNs的系统结构水下定位水声通信等研究领域已经开展了大量基础研究,并取得了一定的成果。其对于保护水资源、开发利用海洋资源等提供有力的保障,因此,UWSNs的研究越来越热,尤其UWSNs的拓扑控制[2](拓扑构建、维护更新等)和路由协议成为其中一个重要的研究方向[3~5]。

针对UWSNs能量损耗严重,节点分布不均匀无规律等现象[6,7],本文提出利用水面浮标节点为顶点,构建一个圆锥型UWSNs,并按照节点能量为衡量标准,设置节点的沉浮,协调节点之间的远近距离,形成各扇形区域,所有活跃节点、备选节点形成一个类二叉树结构的拓扑控制和路由(所谓类二叉树是指该树第一层有3个子树,其余节点均为二叉树,为了表述方便简称之)。通过仿真模拟测试[8],比较不同总层数的效果,并比较了总层数为6的算法与深层路由(depth-based routing,DBR)算法[9],取得一定的效果。

1 圆锥型UWSNs

三维UWSNs定位系统一般如图 1所示,由卫星、基站、测量船、水上浮标、UWSNs节点组成一个特殊的无线传感器网络。悬浮在水中的传感器节点分布在不同深度,用于监测不同深度的数据信息,通过UWSNs的路由将信息传递到水上浮标网络,然后在以无线电通信方式将信息发送至地面基站或者水面测量船,解算完毕后由卫星信号发送至用户手中完成测量。本文的水中无线传感器节点,以能量大小作为沉浮的标准,能量越大分布的越深;反之,则越浅,如果能量不足,漂浮水面退出UWSNs。

图1 三维UWSNs定位系统

1.1 圆锥形UWSNs模型

文中提出基于圆锥型UWSNs的有效传感器节点部署和路由算法。在整个过程中,水上浮标与地面基站及测量船构成一个UWSNs,而UWSNs以每一个浮标为基准构成一个圆锥型通信网络。现任取一个浮标S,以其为中心,把该节点对应的UWSNs模型抽象成一个圆锥模型,如图 2所示。S为水上浮标节点,A,B,C为第一层活跃的传感器节点,A',B',C'为第二层活跃的传感器节点,依次类推……。为了表述方便,将其俯视成二维平面图如图 3所示。其中涉及的概念简述如下:

活跃节点:指在扇形区域中能量最大的一个,用于收集该区域的其他传感器节点的数据。以A'为例,定时活动于所在扇形区域的中心线上,用于收集该扇形区域所有传感器节点的数据,并处理转发给上级节点。

睡眠节点:是指该节点的核心处理模块处于睡眠状态,只开启信号采集模块,采集附近水域信息,并按照能量大小分布于活跃节点附近,能量越大越吸引到活跃节点附近;否则,排斥到边缘区域。

备选节点:是指该扇形区域所有睡眠节点中能量最大的节点,其比睡眠节点多一个额外的侦听功能。以A'为例,其备选节点最靠近节点A',以便A'出现故障或者能量不足,及时唤醒并替换节点A'。

图3中空心圈表示处于睡眠的无线传感器节点,圈中带点表示活跃节点。

图2 圆锥型UWSNs三维图

图3 圆锥型UWSNs二维俯视图

以浮标S为中心的UWSNs中,无线传感器节点根据能量大小能上下左右移动,传感器节点之间采用超声波通信,按照从下往上,向最近的上级节点传递信息。

1.2 圆锥型UWSNs拓扑构建的思想

1)从整体考虑(层与层之间角度):以传感器节点的能量作为判断节点沉浮的判断标准,如第一层的能量最低标准为N1,第二层的能量最低标准为N2(N2>N1),则如果第二层传感器节点能量小于N2,则该传感器节点上浮到第一层,并由第一层节点能量状态来决定是活跃、备选还是睡眠;而第二层的传感器节点则激活备用节点,成为新的第二层传感器节点,而备选节点则从睡眠节点中选取;如果仍然小于N1则漂浮出水面退出网络。

2)从局部考虑(扇形或者扇环立体区域角度):区域内的无线传感器节点以能量大小为标准,该区域中能量大的节点往区域中心靠拢,能量小的节点远离区域中心。能量最大的节点,则被激活为该区域的活跃节点,倘若在第一层,该活跃节点则成为浮标S的子节点;否则,成为上层的右节点;而该区域的其他节点则按照能量大小形成分布于活跃节点附近,处于睡眠状态,其中最靠近活跃节点的,选作备选节点,能量仅次于该区域的活跃节点,并把该节点链接到活跃传感器节点的左节点,随时待命。

1.3 UWSNs拓扑构建维护

以浮标为中心,从上到下,按照树结构的思想,连接活跃节点。首先浮标先连接第一层的三个活跃节点,然后各层按照左节点连接该层的备用节点,右节点连接下层活跃节点的思想,水下圆锥通信网络的活跃传感器节点与备选节点,形成了一个类二叉树结构,UWSNs类二叉树型俯视图如图 4所示,简化类二叉树型如图 5所示。其中,X备表示父节点的备份节点。

图5 UWSNs节点的简化树型拓扑结构

若某层活跃节点能量不足,则发送信息给左节点,激活并启用替代父节点;并选取新备用节点为左节点,启用侦听状态;原父节点则上浮到上层节点,判断是否小于该层最小能量,如果成立继续上浮;否则,插入到该层的睡眠节点中。

1.4 UWSNs的路由信息

如图6,在路由开始阶段,浮标节点S查询其路由邻居信息表中存储的发送邻居节点所需的最小发送功率Pmin,选取合适的P,使其覆盖第一层的三个活跃传感器节点。浮标节点S组播路由链接请求(routing link request,RLR)信息,其包含有ID、层级信息等。邻节点收到RLR信息,判断是否应答,如果是,则反馈路由链接应答(routing link answer,RLA)信息,其包含ID、层级、剩余能量等信息,节点根据RLA信息更新路由表,依次类推,维护建立路由表信息。

图6 路由发起示意图

UWSNs节点采集到水下信息,由睡眠节点到活跃节点,然后沿着父节点依次逐级往上传递。水面浮标更新信息,则是首先判断A,B,C区域,再沿右节点逐级更新。

2 仿真与性能分析

基于Matlab实现了所涉及的圆锥型UWSNs路由仿真。在实验中,无线传感器节点随机分布在水下三维900 m×900 m×900 m环境中,分布后,按照能量大小进行由远到近移动,上下浮动,形成以浮标为中心的圆锥型网络,而树节点的位置固定在各个扇形区域中心。活跃节点有最大传送范围,能辐射所在扇形区域的所有数据。

首先,比较在圆锥型UWSNs中,相同水深,不同总层数的类二叉树下,探讨总层数为4层、6层、8层,而传感器数量从200只递增到800只时,三种总层数的数据包传递率情况。通过仿真模拟观察(仿真40次),相同的水深环境下,总层数越多,数据包传递率越大,随着传感器数量的增加,数据包传递率(PDR)不断增加,对比图如图7所示。

图7 传输半径100 m时的数据包传递率对比

其次,本文的算法以6层类二叉树为例,与DBR算法进行能耗对比,能耗关系到UWSNs的生命周期,水下无线传感器在水下很难更新电源,所以节能成为研究重点,能耗越小,则构建拓扑稳定性就越好。具体仿真模拟效果如图8所示。

图8 DBR算法与本文算法的总能耗对比图

3 结束语

本文根据UWSNs的特点,首先构建以水面浮标为中心的圆锥型UWSNs,接着分成三个扇形,各个扇形根据能量大小自动形成活跃节点、备选节点、睡眠节点等,然后按照类二叉树思想,左节点连接同一个扇形区域的备选节点,右节点连接其所对应的下层活跃节点,如果下层活跃节点因为能量消耗不足或者其他故障,则把该节点上浮到上层,由上层决定其状态,而与此同时,左节点备选节点替换原父节点。仿真实验表明:相同水深情况下,层数越多,传输包投递率越高,与DBR算法比较,能耗降低了。

[1] Ayaz M,Nubaig I,Abdullah A,et al.A survey on routing techniques in underwater wireless sensor networks[J].Journal of Network and Computer Application,2011,34(6):1908-1927.

[2] 刘爱平,刘 忠,罗亚松.一种水下无线传感器网络的连通性覆盖算法[J].传感技术学报,2009,22(1):116-120.

[3] 钟永信,黄建国,韩 晶.基于空间唤醒的水声传感器网络节能路由协议[J].电子与信息学报,2011,33(6):1326-1331.

[4] 傅质馨,徐志良,黄 成,等.无线传感器网络节点部署问题研究[J].传感器与微系统,2008,27(3):116-120.

[5] 徐 明,刘广钟.三维水声传感器网络中高效路由协议的研究[J].计算机科学,2012,39(10):90-124.

[6] 仲元昌,陈 锋,李发传,等.大规模无线传感器网络覆盖优化算法[J].传感器与微系统,2014,33(11):117-120.

[7] 夏 娜,郑语晨,杜华争,等.刚性驱动水下传感器节点自组织布置[J].计算机学报,2013,36(3):494-505.

[8] 刘玉梁,潘仲明.水下无线传感器网络能量路由协议的仿真研究[J].传感技术学报,2011,24(6):905-908.

[9] Yan H,Shi Zhijie,Cui J H.DBR:Depth-based routing for underwater sensor networks[C]∥Proceedings of Networking,2008:72-86.

陈 军(1980-),浙江金华人,副教授,研究方向为网络安全、系统仿真。

Study of cone type UWSNs based on special binary tree*

CHEN Jun1,2, ZHANG Chang-jiang1

(1.College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China; 2.School of Design and Arts,Zhejiang Industry Polytechnic College,Shaoxing 312000,China)

Aiming at problem of serious energy loss in underwater wireless sensor networks(UWSNs)and the phenomenon of irregular sensor node distribution,construct a new cone type UWSNs,setting each surface buoy nodes as the vertex,the sensor node can move according to energy,the active nodes and the backup node will be abstracted to binary tree structure, which simplifies topology control and routing transmission.Simulation test of algorithm is achieved by Matlab,and respectively discuss the different data packet delivery rate to 4 layers binary tree, 6 layers binary tree 4 and 8 layers binary tree.The results show that the greater the number of layers have, the high the transfer rate is;then compare the algorithm for UWSNs with depth-based routing(DBR)algorithm,it shows that this algorithm has high data packet transfer rate and low energy consumption.

underwater wireless sensor networks(UWSNs); binary tree structure; active node; buoy node

2015—02—08

浙江省自然科学基金资助项目(Y12E050087);浙江省科技厅公益性应用研究计划资助项目(2012C23027);浙江省重中之重学科开放基金资助项目(ZC323011014)

10.13873/J.1000—9787(2015)09—0035—03

TP 393

A

1000—9787(2015)09—0035—03

猜你喜欢
二叉树浮标活跃
浅谈浮标灵敏度的判断
浅谈浮标的吃铅比数值
二叉树创建方法
一种浮标位置修正算法*
提问:冬钓轻口鱼如何选择浮标?
活跃在抗洪救灾一线的巾帼身影
数据结构与虚拟仪器结合教学案例
——基于二叉树的图像加密
这些活跃在INS的时髦萌娃,你Follow了吗?
一种由层次遍历和其它遍历构造二叉树的新算法
一种由遍历序列构造二叉树的改进算法