水声传感器网中基于网络编码的多径路由协议*

徐 明

(1.上海海事大学 信息工程学院，上海201306;2.复旦大学 上海市智能信息处理重点实验室，上海200433)

0 引 言

水声传感器网是一门新兴的网络技术，在海洋环境监测、水下导航和水下预警等领域有着广泛的应用［1，2］。路由协议的效率是水声传感器网研究的一个重要课题。由于声波在水中的传播速度比无线电波在空气中的传播速度小5 个数量级，并且水声信道的带宽非常有限，水声传感器网实际可获得的链路容量比无线传感网低很多［3］，这将严重影响水声传感器网的网络吞吐量。此外，由于传感器节点部署在无人值守的恶劣水下环境，造成更换电池非常困难。这对路由协议的能量有效性提出很高的要求。

多径路由是一种提高无线传感器网传输带宽的有效手段，并已成为自组织网络路由的研究热点。按需多径路由(on－demand multi－path routing，ODMR)协议［4］的仿真实验结果表明:进行多径路由时，采用2 条路由路径的效果最优。在定向泛洪路由(directional flooding－based routing，DFR)协议［5］中，源节点将根据邻居节点到自身和目标节点方向的夹角以及链路质量来选择路由转发的中继节点，这样可以在一定程度上减少网络中冗余数据包的数量，从而减轻网络负担。但是，当链路质量不好时，会有多个邻居节点参与同一数据包的转发，造成DFR 的性能急剧下降。多径虚拟汇聚(multipath virtual sink，MVS)节点［6］技术将水声传感器网分为多个簇，每个簇拥有一个或多个聚合点，这些聚合点形成了一个小型的网状网络，并连接到本地汇聚节点，各个本地汇聚节点组成了一个虚拟的汇聚节点，本地汇聚节点之间通过高速射频通信的方式链接到一起。MVS通过将冗余数据包沿着多条路径转发到多个本地汇聚节点的方式提高网络的可靠性和吞吐量，因此，冗余数据包重传造成的能量消耗问题较为突出。

针对传统多径路由存在的问题，本文提出一种基于网络编码的多径路由协议(multi－path routing protocol using network coding，MRNC)。MRNC 在路由过程中通过在主链路和后备链路之间动态切换创造更多的网络编码机会进行数据传输，从而优化网络带宽利用率，并降低冗余数据包重传造成的能量消耗。

1 网络模型

考虑一个由n 个分布在监测区域的水声传感器节点组成的水声传感器网 G(V，E)，其中，V 是节点集，E 是边集。这些水声传感器节点相对于水声信号传播速度而言具有较低的移动性。每个水声传感器节点都被分配一个三维坐标(x，y，z)，并且这些节点都具有相同大小的水声通信半径r。假设所有的水声传感器节点都配备传感设备，能够从外部环境中采集数据，并且可以通过一跳或者多跳传输的方式将采集到的数据聚集到汇聚节点上。汇聚节点是生成数据聚集结果的节点，也是数据传输的目标位置。一条由m 个节点组成的路径 p 表示为 p ={n1，n2，…，nm}，其中，(ni，ni+1)∈E，i∈［1，…，m －1］，路径 p 的长度表示为 L(p)。节点之间的通信是双向的，即如果(ni，nj)∈E，则(nj，ni)∈E。如果从源节点到汇聚节点之间存在l 条路径p1，p2，…，pl，那么这 l 条路径表示为 χ = {p1，p2，…，pl}，其长度为L(χ)=∑L(pi)。

定义1 三维欧拉空间中任意2 个节点nu和nv之间的距离由函数 δ(u，v)给出

当nu和nv之间的欧拉距离小于r 时，则nu和nv成为邻居节点，并且nu和nv之间存在一条链路。

考虑2 个最小跳数距离h 上的节点nu和nv，存在阈值u(h)和v(h)使得u(h)≤δ(u，v)≤v(h)。其中，阈值的大小依赖于水声传感器网络的节点密度ρ，并且对任意h ＞0存在

为了建立水声传感器网中节点的状态模型，本文用随机变量X(u)来表示节点nu的状态，X(u)服从如下的Bernoulli 分布

定义2 节点 nu将一个数据包正确转发的概率Pr(X(u)=1)称为节点nu的数据转发率，用γ(nu)来表示。

路由路径p={n1，n2，…，nm}的状态模型用Y(p)来表示，Y(p)服从如下分布

定义3 给定源节点nu和目标节点nv，则水声传感器模型定义为

其中，λ ＞0，并且 ε ＞0;λ 为水声信号幅值;k 为水声传感器参数;ε 为一个预定义参数，用来处理源节点和目标节点位置相同的情况。

2 路由协议

针对水声传感器网络的路由协议具有自身的特殊性。首先，水声传感器网络节点的计算、存储和通信能力相对较弱，因此，在其上不能实现复杂的路由协议;其次，水声传感器网络以数据为中心，这与传统网络根据节点编址选择路径不同。

本文提出的MRNC 协议包含2 个阶段:路由发现阶段和数据包传输阶段。在路由发现阶段，源节点发出的数据包到达汇聚节点后，在返回的过程中会为主链路建立相应的后备链路。在数据包传输阶段，为了最大限度地降低数据传输带宽消耗，MRNC 采用COPE(coding opportunistically)［7］协议的异或(XOR)编码方式对数据进行网络编码，通过在主链路和后备链路之间动态切换创造更多的网络编码机会进行数据传输。

假设链路丢包率为e，则链路的可靠性为1 －e，那么，将一个编码包从源节点经过一条h 跳的路径成功转发到汇聚节点的概率为(1 －e)h，而成功发送一组数据包的概率rs可用公式(7)计算得到

这组包中每个原始数据包在路径中被转发的次数N 由公式(8)计算得到

因为一个编码包的包头要携带编码系数，所以，一个编码包的长度是原始数据包的长度与全局编码向量域的长度之和。假设全局编码向量占b 个字节，则全局编码向量域的长度为bK;若一个数据包的长度为lp，那么一个数据包与一个编码包的长度之比为lp/(lp+bK)。

由于节点在路由的过程中实际消耗的能量与数据包转发的次数呈正比关系，对于任一数据包，令Ti代表该数据包从第i－1 个节点转发到第i 个节点的平均次数，则数据包转发的总平均次数T 可由公式(9)计算得到

图1 描绘了基于网络编码的多径路由协议中数据包编码和传输的过程。其中，ns为源节点，nd为汇聚节点。节点np对主链路上的数据包A 和后备链路上的数据包B 进行异或编码。传输完成后用各自侦听到的数据包进行解码操作来恢复相应的数据包。

图1 基于网络编码的多径路由示意图Fig 1 Diagram of MRNC

声波信号在浅海(水深小于100 m 的水域)和深海(水深大于100 m 的水域)的传播方式并不相同。在浅海中，声波信号的传输被限制在海面和海底构成的圆柱体中，其传播过程中能量消耗可表示为

其中，δ(u，v)为发送方和接收方之间的距离，m;α 为吸收系数，dB/km;εt为能耗，dB。

在深海中，声波主要以球状扩散为主，传播过程中能量消耗主要由球面扩散和吸收损失两部分造成，可表示为

从公式(10)和公式(11)中可以看出:在浅海和深海中声波传播的能量消耗主要由与距离相关的传输衰减以及与频率相关的吸收损失造成。

3 仿真实验与分析

本文采用Aqua－Sim［8］作为评测水声传感器网中多源异质数据流突发检测性能的模拟器。

表1 给出了仿真实验的参数与默认值。此外，本文将根据以下指标来评价3 种路由协议DFR，MVS 和MRNC 的性能。

表1 实验参数与默认值Tab 1 Experimental parameters and default values

在第1 组实验中，本文比较了不同路由协议中网络吞吐量与节点数量之间的关系。如图2 所示，3 种路由协议的网络吞吐量都与节点数量呈正比。其中，MRNC 的网络吞吐量在节点数量相同的情况下超过其他2 种路由协议。MVS 的网络吞吐量比DFR 平均高出5.6%，而MRNC 的网络吞吐量比MVS 平均高出25.7%。

图2 网络吞吐量与节点数量的关系Fig 2 Relation between network throughput and number of nodes

在第2 组实验中，本文比较了不同路由协议中网络吞吐量与平均数据传送率之间的关系。如图3 所示，3 种路由协议的网络吞吐量均与平均数据传送率呈正比。其中，MRNC 的网络吞吐量在平均数据传送率相同的情况下明显超过其他两种路由协议。此外，在平均数据传送率较小时，MVS 的网络吞吐量略高于DFR，而MRNC 的网络吞吐量比DFR 和MVS 平均分别高出31.7%和11.8%。

图3 网络吞吐量与数据传送率的关系Fig 3 Relation between network throughput and data transfer rate

在第3 组实验中，本文比较了不同路由协议中能量消耗与节点数量之间的关系。如图4 所示，3 种路由协议的能量消耗都与节点数量呈正比。其中，MRNC 的能量消耗在节点数量相同的情况下低于其他两种路由协议，并且增长的速率也更为缓和。MVS 的能量消耗比 DFR 平均低10.7%，而MRNC 的能量消耗比MVS 平均低28.9%。

图4 能量消耗与节点数量的关系Fig 4 Relation between energy consumption and number of nodes

在第4 组实验中，本文比较了不同路由协议中能量消耗与平均跳步距离(hops)之间的关系。如图5 所示，3 种路由协议的能量消耗都与平均跳步距离呈正比。其中，MRNC的能量消耗在平均跳步距离相同的情况下低于其他2 种路由协议。MVS 的能量消耗比DFR 平均低17.8%，而MRNC的能量消耗比MVS 平均低21.3%。

图5 能量消耗与平均跳步距离的关系Fig 5 Relation between of energy consumption and average hop distances

4 结 论

针对水声传感器网通信带宽低、节点能耗高的特点，提出一种基于网络编码的多径路由协议。该协议在路由过程中通过在主链路和后备链路之间动态切换创造更多的网络编码机会进行数据传输，从而优化网络带宽利用率，并降低冗余数据包重传造成的能量消耗。仿真结果表明:基于网络编码的多径路由协议可以在提高水声传感器网吞吐量的同时，有效降低网络能量消耗。

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

［2］ Manjula R，Sunilkumar S.Issues in underwater acoustic sensor networks［J］.International Journal of Computer and Electrical Engineering，2011，3(1):101 －110.

［3］ Jornet J，Stojanovic M，Zorzi M.On joint frequency and power allocation in a cross－layer protocol for underwater acoustic networks［J］.IEEE Journal of Oceanic Engineering，2010，35(4):936 －947.

［4］ Nasipuri A，Castaneda R，Das S R.Performance of multipath routing for on－demand protocols in mobile Ad Hoc networks［J］.Mobile Networks and Applications，2001，6(4):339 － 349.

［5］ Hwang D Y.DFR:Directional flooding－based routing protocol for underwater sensor networks［C］∥Proceedings of OCEANS 2008，Kobe，Japan，IEEE，2008.

［6］ Seah W G，Tan H X.Multipath virtual Sink architecture for underwater sensor networks［C］∥Proceedings of OCEANS 2006，Boston，USA，IEEE，2006.

［7］ Katti S，Rahul H，Hu W J，et al.Xors in the air:Practical wireless network coding［J］.IEEE/ACM Transaction on Networking，2008，16(3):497 －510.

［8］ Xie P，Zhou Z，Peng Z，et al.Aqua－sim:An NS－2 based simulator for underwater ssensor networks［C］∥Proceedings of OCEANS 2009，Biloxi，USA，IEEE，2009.