水下无线传感器网络DBR路由协议研究

黄 芬，陈名松

(桂林电子科技大学 信息与通信学院，广西 桂林541004)

随着世界各国海洋开发和海洋军事领域的飞速发展，水下无线传感器网络及其应用成为新的研究热点［1］。其路由协议的研究必不可少。由于水下无线传感器网络的特性，提供一种可靠的、可扩展的有效路由协议是非常大的挑战。近年来，学者们针对水下无线传感器网络具有动态拓扑结构、通信带宽低、传播时延大、误码率高等特点，提出了许多路由协议，尤其是基于地理位置的路由协议成为研究重点，但是它们大部分都需要借助昂贵的GPS定位。而这是水下无线传感器网络的另一大难题。

1 DBR网络模型

DBR(Depth Based Routing)［2］采用的是多Sink节点水下无线传感器网络结构［3］，见图1。在网络中有两种传感器节点:一种是Sink节点，部署在水面上;另一种是普通传感器节点(UW_sensor node)，部署在感兴趣的水下3D区域内。Sink节点配备了RF调制解调器和水声调制解调器。前者用于Sink节点之间以及Sink节点和接收站之间的通信;后者用于Sink节点与UW_sensor node之间的通信。UW_sensor node只有水声调制解调器，并且每个UW_sensor node都配备有深度传感器，它不仅可以将探测到的数据发送给邻节点，还可以将邻节点发送过来的数据转发出去。DBR路由协议只考虑Sink节点和UW_sensor node之间的通信，不考虑Sink节点之间的通信。由于所有Sink节点都配有RF调制解调器，如果任何一个Sink节点成功接收到数据包，都可以通过无线电传播很快地将数据包转发给其他Sink节点和接收站。因此只要数据包成功到达任何一个Sink节点，则认为其成功到达目的节点。

图1 多Sink节点水下传感器网络拓扑结构

2 DBR路由算法

2.1 基本思想

DBR路由算法是一种简单的基于节点深度信息的水下传感器网络路由协议，网络中所有节点的决定都取决于节点深度信息。不同于其他基于地理位置的路由协议，如VBF［4］，HH-VBF［5］，FBR［6］，DFR［7］等，DBR不需要知道节点的全三维位置信息，只需要知道节点的局部深度信息。节点深度信息可以很容易通过安装在节点中的深度传感器获得。

DBR采用贪婪转发策略将数据包发送给水面Sink节点。试图选择离目的节点最近的节点，即深度最小的节点为下一跳转发节点;同时防止其他邻节点转发同样的数据包来减小能耗。在这个过程中，数据包越接近目的节点，转发节点的深度越小。在空洞不存在的情况下，如果减小每一跳转发节点的深度，数据包可以到达水面Sink节点。当某个节点有数据要发送时，简单地通过广播洪泛的形式将数据发送出去。其他节点接收到数据之后，借助于深度传感器计算它们的深度并与发送节点的深度做比较。如果其深度小于发送节点的深度，则具有转发数据的资格;对收到的数据进行相应的处理，并同样通过广播的形式将数据转发出去，否则将简单丢弃数据包。

2.2 路由表的维护

DBR中数据分组包括4个域，具体如图2所示。

图2 数据包格式

包序列号是由源节点分配给每个包的特殊序列号，和源节点ID一起组成数据包的Unique packet ID，用于区别不同的数据包。节点深度Depth是最近一次发送某个数据包的节点深度。Depth值逐跳更新，即数据包每被转发一次，Depth值更新一次。

在DBR中，为了减小转发节点的数量和控制数据包的重复发送，每个节点必须维护priority queue Q1和packet history buffer Q2两张路由表。节点通过维护Q1和Q2这两个序列，可以减少转发节点数目，控制转发路径，保证节点在一段时间内对相同的数据包只发送一次。网络初始化时，每个节点的Q1和Q2序列都为空。Q1是临时路由表，用来设置数据包转发优先级的，当数据包成功发送出去之后释放;Q2用来记录节点最近发送数据包的情况。每当节点成功发送一个数据包后，则将此数据包的Unique packet ID写入Q2中。当Q2已满，最近最少被访问的Unique packet ID将被最新的Unique packet ID取代。路由表Q1和Q2的路由条目如图3所示。

图3 由表Q1，Q2路由条目

节点接收到数据包之后，如果之前没有发送过这个数据包(即Q2中无此包的记录)，将此数据包写入Q1中，并在holding time时间之后，将数据包转发给深度更小的节点。若在holding time时间内，此数据包再次被接收到有两种情况:第一，从深度更大的节点或同样深度的节点再次接收到此包，丢弃此包并释放Q1;第二，从深度更小的节点再次接收到此包，更新数据包，预计发送时间ST，ST值也是逐跳更新。节点将此数据包发送出去后，释放Q1并将此包的Unique packet ID写入Q2中。

2.3 转发节点集的选择

为了更好地控制转发节点的数量，引进深度阈值dth参数。只有当上一跳节点与当前节点的深度差Δd(Δd=dp-dc)大于dth时，当前节点才具有转发资格。dth的取值范围为［-R，R)。当dth=0时，说明比当前节点深度低的节点都具有转发资格;当dth=-R时，相当于全局洪泛协议。dth值是数据包成功传递率与网络平均能耗之间的一个权衡，当dth值小时，数据包成功传递率高，能耗也大;dth值大时，数据包成功传递率低，能耗也低。所以需要合理地选择dth值，保证数据包成功传递率高，能耗也低，以满足网络需求。

2.4 数据包转发优先级

DBR采用数据包转发优先级的方法来抑制冗余数据报的传输。数据包转发优先级是通过Q1中的数据包预计转发时间ST来体现的。节点的ST越早，其优先级越高。每个接收到数据包的节点，首先计算数据包的预计发送时间ST，并写入到优先序列Q1中。包预计发送时间ST与Holding Time(HT)和接收到数据包的时刻有关(ST=接收到数据包的时间+HT)。即当某个节点接收到一个数据包时，不是立即将数据包发送出去，而是先保持HT时间再发送。HT和上一跳节点与当前接收节点的距离Δd有关。HT的计算式如

式中:τ=R/c;R为节点最大传输距离;c为水声传播速度，约等于1 500 m/s;Δd为上一跳节点与当前节点的深度差。当δ取值较小时，节点HT较长，参与数据包转发的节点较少，能耗减少，但是端到端延时会变长。

2.5 数据转发策略

在DBR中，每个节点在数据包中增加了一个深度信息。接收到数据包的节点，只有其深度小于发送节点的深度时，才具备转发数据的资格。DBR试图选择Depth值最小的邻节点作为转发节点，同时防止其他邻节点转发同样的数据包来减小能耗。

DBR中数据包转发算法总结如下:当某个节点接收到数据包时，它首先根据上一跳节点和当前节点的深度信息与深度阈值判断自己是否具有数据转发资格，如果没有转发资格，则查询Q1中是否存在数据包，若不存在，丢弃收到的数据包;否则，丢弃数据包并删除Q1中数据包。如果具有转发资格，在查询Q2中是否存在这个数据包，若Q2中已存在这个数据包，则丢弃;否则查询Q1中是否存在数据包，若不存在，则更新数据包中Depth域为当前节点深度dc，及根据当前系统时间(即接收到数据包p的时间)及HT计算出数据包预计发送时间，然后将数据包及其预计发送时间ST写入到Q1中。否则，从Q1中的数据包中提取出此数据包先前的预计发送时间STp，用min{ST，STp}更新Q1中的包预计发送时间域。如某节点接收到数据包P，其转发流程图如图4所示。

图4数据包转发流程图

图5 说明了数据包转发情况。节点S是发送节点，节点n1，n2，n3，n4和n5是S的所有一跳邻节点。当节点S有数据包要发送时，将数据包广播发送出去，所有邻节点都能接收到这个数据包。节点n4和n5在节点S下面(ds-dni＜dth，i=4，5)，dth=0，不具备转发资格，丢弃此数据包。尽管n1，n2和n3都具备转发资格，但是根据节点转发优先级策略，可知n1的优先级高于n2和n3，更适合转发数据。n1将最先将数据包转发出去，n2和n3在它们的数据包预计发送时间内将接收到节点n1发送的数据包，通过检查Q2可以抑制数据包的发送。

图5 转发节点的选择

3 扩展分析

DBR协议的关键思想是网络中所有节点转发数据包的决定取决于节点深度信息。在采用贪婪转发算法的时候，节点依据一定的标准选择一个邻节点作为数据包的下一跳节点。DBR相对于其他基于地理位置信息的水下传感器网络路由协议，不需要知道节点全三维位置信息，只需要知道节点的局部深度信息。同时，DBR采用的是多Sink节点网络结构，继承了此网络节点的特点并未带来额外的网络成本。但是DBR仍然存在一些问题，这些问题会影响网络的性能。

第一，DBR采用洪泛传播机制，如果每个节点都参与数据的转发，将增加网络的复杂度，产生大量的冗余数据，导致过多的能量消耗，且降低了网络带宽利用率。同时所有接收到数据包的节点每次都要计算他们的深度信息，同样会消耗网络能量。第二，DBR网络的性能与网络密度有关。比如在某些区域节点部署稀疏，可能由于候选节点的深度都比发送节点大，导致发送节点找不到转发节点，从而进入到不断寻找候选节点的死循环中，即存在局部路由空洞现象。即使有些比发送节点深度大的节点可以成功转发数据到目的节点，但是DBR中并没用提出处理局部路由空洞现象的机制。第三，网络中每个节点必须配置深度传感器，增加网络成本，同时深度传感器也要消耗一部分能量，会降低网络寿命。

Uichin Lee等人针对DBR路由协议存在隐藏终端和局部路由空洞现象，提出了Hydrocast协议［8］。在转发节点集的选择策略中考虑了如何避免隐藏终端现象，并提出了局部更低深度节点优先路由恢复机制。但是Hydrocast协议同样会出现多个转发节点传递同一个数据包的现象，造成信息的冗余发送和节点能量的浪费。

Hydrocast协议利用局部拓扑信息，采用简单的贪婪算法选择最优候选节点集，且不存在隐藏终端问题。具体工作如下:节点根据数据包到目的节点的最大期望(EPA)来选择转发节点集。EPA的大小与数据包传递率和节点到目的节点的距离有关。源节点选择EPA值最大的节点ni作为转发节点，如果ni的邻节点通信范围覆盖了ni通信范围的一半，这些邻节点和ni便形成了一个转发节点集。转发节点集中的节点可以互相侦听对方，因为它们之间的距离都小于最大传输距离R，这样就保证不会出现隐藏终端现象。Hydrocast协议同样采用数据包转发优先级的方法来抑制冗余数据包的传输。节点EPA值越大优先级越高，EPA值最大的节点ni优先级最高，即节点ni等待发送时间最短。转发节点集中的节点在侦听到高优先级的节点时，将抑制自己的传输。

在Hydrocast协议中，当某节点所有一跳邻节点的深度都比它的大时，此节点为局部极值点。每个局部极值点都维持着到比其深度更低的节点的恢复路径，用于避免发生路由空洞。当数据包在局部极值点的一条路径或多条路径中断时，可以通过路由恢复路径走出空洞区域，回到贪婪转发模式。局部更低深度节点优先恢复机制(local lower-depth-first recovery)将抑制节点的洪泛，只有表面节点参加洪泛转发。被邻节点包围的节点不是表面节点，否则就是表面节点。采用四面体的方法决定一个节点是否为表面节点，通过这种方法找到表面节点后，数据包将从一个表面节点传输到另一个表面节点。经过几次传输后，回到贪婪转发模式。

VAPR协议［9］采用基于地理位置的路由协议中固有的信标机制(beaconing mechanism)来避免路由空洞现象。在每个信标数据包中嵌入节点的位置信息(在这是节点深度信息)，节点通过比较邻节点与自己的深度，可以很容易地确定自己是否为局部极值点。当某节点为局部极值点时，广播告知其一跳邻节点。具体如下:每个节点都周期性地向其一跳邻节点发送信标数据包，信标数据包中包括5个域:节点ID、节点深度、局部极值点标志位、节点界限、超时间隔。VAPR协议中信标数据包只需存储一跳邻节点的信息，所以每个信标数据包中只包括广播这个信标数据包的信息。

DBMR协议［10］也是一种基于深度的路由协议，但不是采用洪泛传播机制，所以不会像DBR协议一样产生大量的冗余数据，导致过多的能量消耗，可以平衡网络能耗，但是同样存在路由空洞现象。它分为路由发现和数据转发两个过程。所有节点部署完后，就开始探测它们的深度，启动路由发现过程选择它们的下一跳节点，并存入路由表中。当某节点有数据包要发送时，将通过多跳的方式把数据包发送给Sink节点。具体做法如下:首先查询路由表中是否有下一跳节点，若没有则发送失败，触发路由发现过程找到下一跳节点，然后发送数据包。当邻节点接收到数据包之后，首先检查自己是否是Sink节点，如果是Sink节点，数据包成功接收;否则，继续转发数据包直到数据包被Sink节点成功接收。

4 小结

本文详细描述了水下无线传感器网络基于深度信息路由协议DBR的特性。DBR协议是水下无线传感器网络中第一个基于深度信息的路由协议，采用贪婪转发策略将数据包发送给水面Sink节点。虽然相对于其他基于地理位置的路由协议具有许多优点，但还是存在很多不足，有待改进。在扩展分析中，详细阐述了DBR路由协议的优缺点及几种DBR路由协议的改进算法。随着该协议的不断改进，可达到很好地节省节点能量的目的，延长整个网络的寿命。

［1］朱昌平，韩庆邦.水声通信基本原理与应用［M］.北京:电子工业出版社，2009:252-320.

［2］YAN Hai，SHI Zhijie，CUI Junhong.DBR:depth based routing for underwater sensor networks［C］//Proc.NETWORKING＇08.［S.l.］:Springer-Verlag Berlin，2008:16-1221.

［3］SEACH W K G，TAN H X.Multipath virtual sink architecture for underwater sensor networks［C］//Proc.OCEANS 2006-Asia Pacific.［S.l.］:IEEE Press，2006:1-6.

［4］XIE P，CUI J H，LAO L.VBF:vector-based forwarding protocol for Underwater Sensor Networks［EB/OL］.［2012-01-01］.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.4529＆rep=rep1＆type=pdf.

［5］NICOLAOU N，ANDREW S，XIE P.Improving the robustness of location-based routing for Underwater Sensor networks［C］//Proc.IEEE OCEANS.［S.l.］:IEEE Press，2007:1-6.

［6］JORNET M，STOJANOVIC M，ZORZI M.Focused beam routing protocol for underwater acoustic networks［C］//Proc.WuWNeT＇08.New York，NY，USA:ACM，2008:75-82.

［7］HWANG D，KIM D.DFR:directional flooding-based routing protocol for underwater sensor networks［C］//Proc.IEEE OCEANS.［S.l.］:IEEE Press，2008:1-7.

［8］LEE U，WANG P，NOH Y，et al.Pressure routing for underwater sensor networks［C］//Proc.IEEE INFOCOM.［S.l.］:IEEE Press，2010:1-9.

［9］NOH Y，WANG P，LEE U，et al.VAPR:void aware pressure routing protocol［EB/OL］.［2011-09-30］.http://cs.ucla.edu/～ytnoh/publication/WuWNet10_VAPR.pdf.

［10］LIU Guangzhong，LI Zhibin.Depth-based multi-hop routing protocol for underwater sensor network［C］//Proc.2nd International Conference on Industrial Mechatronics and Automation.［S.l.］:IEEE Press，2010:268-270.