基于概率优化的水下通道感知能量优化路由

万智萍

中山大学 新华学院，广州 510520

1 引言

水下传感器网络（UWSNs）在海洋资源保护，污染监测，设置海洋军事预警区等方面都有重要作用[1-2]，但与地面传感器所使用的电磁波和光波通信模式不同，水下传感器网络主要通过水声通信。由于水声传播受水表面的反射、表层声道、水声介质、水下交汇层等的影响[3-4]，信号延迟时间长且延迟时间变化频率高，而且在多径水声信道的恶劣条件下会出现信号衰减快和多普勒失真等现象，这些问题使水下传感器网络相比地面传感器网络的研究难度更大，实际解决方案少。由于海洋环境复杂，无线传感器在水下部署只能依靠电池供电，通常只能携带能量十分有限的电池，因此只有对整个水下传感器网络的能量进行合理利用，才可以维持网络的正常生命周期[5]，解决过多的能量损耗问题也是现阶段国内外在水下传感器网络上的研究重点。

国内文献对水下多径水声信道条件下的无线传感器网络研究较少，在水声无线传感器网络的能量优化上国外有较为突出的研究成果。Andrej Stefanov[6]等人提出了一种水声通信网络规划和性能分析方案，在水下传感器网络的节点间通信信道中使用与频率相关的路径损耗模型和莱斯衰落信道模型。并通过一个分层的水下声传感器网络体系架构使集电极站与传感器操作在不同层，避免了集电极网络与无线传感器网络的交叉干扰，优化了网络的能量和带宽效率。Wang等[7]提出一种水下传感器网络节能高效的数据传输协议，该协议针对水下拓扑变化快及高延迟问题，根据节点剩余能量和节点位置提出一种能量消耗模型来选择最优的簇头，簇头会根据剩余能量、位置和端到端延迟来搜索下一跳节点，提升能源效率并延长网络寿命。Zhou等[8]提出一种水下传感器网络节能路由协议，该协议会尝试避免控制分组的转发，并根据汇聚节点的需要在每个时间点选择最合适的中继节点，当传输环境稳定时，还会通过减少感测数据的传输次数来减少能量消耗。Dario Pompili[9]等人研究水声传感器网络路由功能特点和水声信道之间的互相作用，并针对延迟敏感和延迟不敏感的水声信道的应用需求，提出一种分布式地理路由算法，最大化的减少能量消耗。上述算法对水下传感器网络的能耗与延迟控制研究较为深入，但算法的复杂性较大，也没有考虑到水下传感器节点感测覆盖的数量最小化问题，而节点资源设备数量的最小化可以有效地减少总体能量的额外过度损耗。

文章不仅在传统的路由层面上考虑能量优化问题，针对水下传感器网络的基础设备损耗问题，通过计算一定概率条件下需要的最少节点数目，有利于在进行传感器节点的实际部署问题上能有计划地投入合适的传感器数量，防止过多的多余传感器节点带来额外的能耗，给工作方带来经济上和能源上的负担。在延迟问题上简要分析了可控的延迟因素，主要解决由于误码率过大引起的数据重传问题所带来的延迟时间，并采用了合适的错误控制方案。实验上通过对比分析的方法来体现PPUN算法的优势。

2 能量优化

2.1 水下节点三维分布模型

水下传感器是通过固定在海面下不同深度的浮标上进行部署，图1给出了水下三维分布的节点通信模型，假设水声传感器节点的水声正常传播范围为一个球体，且通信半径为r，位于通信半径的节点之间直接通信，如m1和m2，超过通信范围的节点通过中继点进行数据转发。为了使水声传感器节点的感测范围能完整覆盖特定区域，往往这个传感器网络的感测覆盖范围都会超过实际所需的覆盖范围，为了更加直观地进行分析，给出了图1水下节点三维分布模型的一个节点正面分布图，如图2（a）所示，正方形区为实际所需覆盖范围，黑色圆框为当前模型的传感器通信范围，虚线圆框为为了满足覆盖需要而加入的其他传感器的通信范围，可以看出为了达到覆盖正方形区的目的，传感器节点的感测覆盖范围已经超过了实际所需范围。由于整个水下传感器网络的能耗取决于所有传感器节点的能耗总和，因此在保证特定区域的感测覆盖范围且覆盖的传感器能连接成功的条件下，尽可能地减少传感器的数量，可以降低水下传感器网络的能量消耗。

图1 水下节点三维分布模型

图2 参考模型

2.2 传感器数量的概率优化

2.2.1 最少所需感测覆盖节点计算

以一个无向连通图G=(M,E)作为传感器网络的模型，其中M=(m1,m2,...,mN)表示传感器组，E表示传感器之间的双向链路。假设传感器节点mi∈M有固定的感测范围，用球形区域V表示，半径为r。对于一个传感器节点mi与其他节点可以在感测范围V内通信，引出如下四个基本定义：

定义1mi的相邻节点组被定义为P={mj|d(mi,mj)≤r},mi,mj∈M}，其中d(mi,mj)表示节点mi与mj的欧几里德距离，mj可以在V 内的任何地方，用极坐标(ρ,φ,θ)计算两个节点间的距离：

其中：

定义2区域D为实际所需感测体积，是一个a×a×a的正方体，图2（b）是一个二维的正面分析图。D区域内的每个节点位置通过一对笛卡尔坐标x、y、z表示，其中：

定义3B为带圆角的正面体，所有传感器都位于B内，在B内的传感器的感测范围都能覆盖到D（参照图2（b））。

定义4用η表示感测覆盖率，即在区域D内的任何一点都能被传感器覆盖时D在B中所占的范围，0＜η＜1。

由计算体积的数学表达式可以得到B=(α2+6αr+3πr2)×(2r+a)，假设一个在D内的点q不能被一个在B内的随机传感器mi覆盖的概率为Pq(x,y,z)，每个随机传感器的覆盖范围为V，Pq(x,y,z)为：

实际所需的感测覆盖范围D=a3，则可以得出D中不被传感器感测范围覆盖的概率为：

即感测覆盖率η可以得出：

因此，在满足感测覆盖率η的条件下可以得到所需的最少传感器数目为：

但这里所得到的最少节点数目n是满足感测覆盖范围的最少节点，但满足了实际需要的覆盖范围，却不考虑传感器之间的连通问题，则整个传感器网络无法正常工作。因此接下来需要计算出在B范围内传感网络能连通条件下需要的最少节点数目，即n个传感器能连通的概率，从而求出在满足感测覆盖率条件和传感器连通条件下的概率，再求出满足概率条件的最少节点个数n。

2.2.2 n个传感器连通概率

假设在B范围内有传感器的数目为n，N为一个节点集合，初始值为，即只有一个节点。代表另一个节点集合为源节点通过邻居节点连通至汇聚节点所需要的步骤，即需要经历的下一跳次数，初始值为0。

定义5Pi为任意一个传感器能找到邻居节点的概率。

定义6在每一个步骤之后各增加1减少，即与N集合中的节点连通的集合中的节点会归属到集合N中，在最后一个步骤l=n-1时节点连通工作结束。

定义7PN,l表示集合N中的一个节点在步骤l与集合 Nˉ中至少一个节点连通的概率；PNˉ,l表示集合 Nˉ中的一个节点在步骤l与集合N中至少一个节点连通的概率。

在进行步骤l后可以得到PN,l和PNˉ,l为：

其中Pi=V/D，V为前面提到的传感器的覆盖范围。得到PNˉ,l之后，可以求出n个传感器节点连通的概率为：

最终求同时满足感测覆盖率η和传感器连通条件下的概率P(η|Pn)，采用的是概率乘法公式，根据概率乘法公式的定义，事件A与B是相互独立的。如图2的参考模型所示，传感器节点的分布满足了覆盖D的要求，但有个别节点并没有与其他节点互相连通，而节点在互相连通的条件下不一定满足感测范围完全覆盖D的条件，因此感测覆盖率和传感器连通概率是互相独立的，因此可得：

当确定了所需的感测覆盖率和所需的传感器节点连通率，就可以通过得出的P(η|Pn)值来求得最少所需的节点个数n。

2.3 节点链路优化的通道感知路由

在最少传感器节点个数n随机部署的条件下，再进行通道感知的路由算法分析，对节点间的链路选择进行优化，使节点通过选择更合适的中继节点，并得出了预期的跳距离，在链路规划上对网络的能量消耗进一步优化。

假设节点mi为了向汇聚节点发送数据，需要通过中继节点mj向汇聚节点转发数据，mi与mj的距离表示为d(mi,mj)=rij，用球坐标来表示预期的下一跳节点距离：

其中，Pηj表示选择j∈M为下一跳节点的概率。图3为向中继节点转发数据的三维模型，由于多径水声信道的信号衰减符合瑞利衰落信道模型[10-11]，假设有一传输损耗阈值En，节点的每一次数据包转发所耗能量都不能超过此值，否则会影响汇聚节点对数据的正常接收，节点mi选择mj为下一节点需要消耗的能量为Ej，选择比mj更靠近汇聚节点的节点k所消耗的能量Ek≥En，与汇聚节点的距离为Rk＜R（如图3所示，R为节点mi到mj的距离）。因此，被选择作为下一跳的节点mj应满足Ej＜En。选择下一跳节点为mj的概率为：

其中，P{Nd=R=1}表示与汇聚节点的距离为R的节点只有一个的概率，P{L[i,j]≥R}是下一跳距离大于节点k到汇聚节点的距离的概率。设ρ是水下传感器网络的每单位体积节点密度，可得P{ }Nd=R=1为：

图3 数据转发模型

当ρr2sinθdθdφdr→0时，即dθ、dr或dφ有一个取值为零时

由瑞利分布[12-13]可知：

其中，Pm通过计算V(Rm＜R)与mi感测范围的总体积之比得出：

结合式（1）、（7）～（12）可以得出预期下一跳节点距离

对节点转发数据的跳距离的计算，保证了在多径水声信道的恶劣条件下信号能通过中继点转发到达汇聚节点，不会因为转发过程出现的信号衰减而导致信号丢失，并且在这一前提下选择了最短的转发路径，降低了能量损耗。

3 延迟分析

3.1 水声信道延迟因素

水下传感器网络在整个生命周期所消耗的时间主要有：传感器感测数据所耗时间、数据包的传输时间、数据包解码所消耗的时间。延迟时间出现在传播延迟、解码延迟。传播延迟受水下传播环境的影响，因此传播延迟属于不可控制因素，解码延迟是由于数据包出现误码和丢失现象导致数据重传而引起的，解码延迟可以通过降低误码率，合适的纠错方法来加以控制。

3.2 错误率控制方法

为了降低误包率，使用带QAM调制的OFDM传输，用16-QAM调制方案[14]的错误率为：

其中，Pb是比特错误率，ψ=10ζ10，BN是噪声带宽，υTX是数据速率。ζ是指在一个有多个干扰节点的采用扩频的码分多址技术（CDMA）的水下传感器网络的接收端处，一个水声信号的信号与干扰加噪声比（SINR）。BCH、RS和FEC块码用(q,n,k,σ)表示，误包率为：

其中，qo是指该数据单元的长度，n是块长度，k是有效负载长度，σ是位的纠错能力。

错误率控制采用的是完全递增冗余重传机制改进方案（HARQ-III）[15]，HARQ-III方案结合了自动请求重传（ARQ）和前向纠错编码（FEC），并且对发送的数据包采用互补删除的方式，使各个数据包不仅可以单独译码，也可以合成一个具有更大冗余信息的编码包进行合并译码。防止在恶劣的慢衰落的条件下数据包仍不断重传导致的耗时，并且用HARQ-III方案合并的码字能够覆盖FEC编码中的比特位，译码信息更全面。

整个HARQ-III方案的工作时间为：

其中，λ为预期的重传次数，接收机的分组成功概率在一定值内接近一个阶跃函数。Tnode为感测数据所花费的时间，T1和T2为数据包的传输时间，TP是数据传播过程的延迟，TACK表示接受方成功的接收到数据，回复一个ACK数据确认所消耗的时间。PS表示一个数据包在一定距离被成功接收到且不使用HARQ重传的概率，TB1和TB2为用于解码FEC码的时间，包含了FEC块码进行解码时的延迟时间。一个FEC块码进行解码时的延迟时间为：

其中Tadd和Tmult分别是在Galois字段的字段元素m=[lbk+1]的加法和乘法的延迟时间。

4 计算复杂度分析

在本文算法中，对传感器数量进行概率优化的计算部分，其中公式（6）只需进行一次计算，求满足感测覆盖率条件下最少节点数目n1，假设计算时间为t1。根据确定的传感器连通概率，公式（9）求出最少节点数量n2，假设计算时间为t2，由于最终的传感器数量因此在传感器数量概率优化上的时间开销大约为t1+t2。在路由问题上，根据公式（12）计算选择下一跳节点的概率，假设每个节点的平均计算时间为w1，则m个邻居节点的计算开销为mw1，而m个节点在计算出选择概率后，进行概率大小的比较，所花费的比较时间假设为w2。则算法的计算时间总开销为：t1+t2+mw1+w2，计算复杂度则为。

在实际应用上，本文的传感器数量概率优化方法适用于对水下监测环境的节点投入数量进行预估，防止投入过多节点，减少传感器节点的设备投入成本。而通道感知路由算法通过优化中继选择及对延迟时间的控制，在采集水下检测数据上可以带来更好的健壮性和高效性。

5 实验结果及分析

5.1 仿真条件

分析本文的水下传感器网络方案在能量优化和延迟控制上的效果，需要研究水下声学信道的特性，建立相应的水下声学信道仿真环境。算法都采用C++进行编程实现，在水下仿真环境参数的选取上借鉴了文献[6]和文献[16]，根据实际的水下监测和预警需要，节点随机部署范围较大，这里模拟水下节点部署空间为1 000 m×1 000 m×1 000 m的水下监控区，节点覆盖半径为100 m。水下信道水声传播速度为1 500 m/s，通过分析水下多径信道影响声音传播过程而造成的延迟时间，规定每分钟固定延时1.5 ms，而载波频率为7.5 kHz，发送功率为30 W。其他仿真条件如表1所示。

5.2 仿真实验

表1 仿真参数

实验中采用比较法来验证PPUN算法的性能，对比组算法为文献[17]提出了一种新的非对称多路径分离水声网络通信（AMDC）算法，以及文献[18]提出一种水下传感器网络的链路状态自适应反馈路由算法（LAFR）。其中文献[17]以构建基于树的多路径原理划分水下通信空间并把AMDC能量效率问题作为一个分布式优化问题进行分析，并在仿真实验中体现出AMDC机制在能源效率优化和总数据包错误率控制上的优势。文献[18]使用链路检测机制来获取链路状态信息（链接对称或不对称的链接），通过充分利用水下非对称链路，节省能源。并采用基于信任的路由表更新机制，通过路由表的频繁更新来减少能源消耗。

对于水下数据传输能耗方面的比较，图4分别给出了不同比特速率下三种算法的每比特数据的平均传输能耗情况。从图中可以看出，AMDC算法在不同比特速率下的传输能耗波动最大，LAFR和PPUN算法的波动幅度较小，在比特速率达到3 kb/s时，三种算法的每比特数据平均传输能耗接近相等，当比特速率大于3.8 kb/s时，PPUN算法的每比特平均传输能耗低于LAFR算法和AMDC算法。这是由于PPUN采用节点链路优化的通道感知路由方法，考虑了能耗阈值条件下的最短传输路径，有效避免数据转发失效而消耗能量，因此在传输速率或数据传输量较大的情况下，PPUN算法在减少数据传输能耗上所发挥的作用更加明显。

图4 每比特数据的平均传输能耗

图5给出了三种算法在不同数据传输速率下的网络总能耗上的对比情况，从图中可以看出，三种算法在数据传输速率变化时网络总能耗逐渐增大，在Data rate=10 kb/s时LAFR算法的能耗总量为672 J，AMDC算法为723 J，PPUN算法为712 J。在10＜Data rate≤30 kb/s，LAFR算法的能耗总量最少，AMDC算法最大。在Data rate≥30 kb/s，PPUN算法的能耗总量最少，AMDC算法最大。在Data rate=50 kb/s时LAFR算法的能耗总量为1 086 J，AMDC算法为1 125 J，PPUN算法为936 J。并且在图中可以看出，随着数据传输速率的增大，PPUN算法的能耗总量增长幅度最小。从Data rate=10 kb/s到Data rate=50 kb/s，PPUN算法的能耗总量增长了224 J，AMDC算法增长了402 J，LAFR算法增长了374 J。可以看出，PPUN算法采用传感器节点数量优化和通道感知的路由优化方法，在减少网络能耗总量上得到了一定的效果。

图5 不同数据传输速率下的能量消耗总量

实际应用中，在水下监测范围内投入不同的传感器节点数量会对水下网络的性能带来影响，例如平均能耗和丢包率。图6显示了在监测范围固定的条件下，投入不同的节点数量时网络的节点平均能耗情况。从图中可以看出，随着网络的节点密度增大，节点平均能耗量逐渐降低，这是由于节点数量的增多使得节点平均中继距离变小，因此传输能耗降低。其中PPUN算法的通道感知路由算法能够搜索最短的转发路径，并且通过对数据传输的能量消耗量进行规划，从而减少由于传输能量不足而引起的丢包概率，避免网络在数据重传上消耗更多的能量，因此PPUN算法的节点平均传输能耗更低。图7中也可以看出PPUN算法在控制丢包率上的有效性，根据图7中的数据显示，PPUN算法的平均丢包率分别为LAFR算法和AMDC算法的85.7%、77.2%。

图6 不同节点密度条件下的节点平均能耗

图7 不同节点密度条件下的丢包率

对延迟控制的分析以时间为变量，其他参数如表1所示不做更改。观察在模拟仿真期间出现的延迟时间，并通过数据分析得到了图8的延迟时间分析图。从图中可以看出，在仿真期间LAFR算法的延迟时间较大，处于46.9 ms至61.2 ms之间，AMDC算法处在43.5 ms至59.8 ms之间，PPUN算法的延迟时间和波动幅度较小，处在42.3 ms至46.1 ms之间。从仿真分析结果可以得出，PPUN算法结合带QAM调制的OFDM传输与HARQ-III错误控制方案的方法，对整个传输过程的延迟控制起到了一定的效果。

图8 延迟时间

6 结论

本文针对水下传感器网络的能量损耗和延迟问题，提出了一种基于概率优化的水下通道感知能量优化路由，算法从传感器的感测覆盖问题和节点链路问题上对网络进行总体能量优化，分析数据错误率并采用合适的错误控制方案来缩短解码延迟时间，提高水下传感器网络的延迟控制效率。对能量损耗、延迟控制问题进行了仿真实验，从仿真结果可以看出，算法在能量优化上具有一定的作用，在缩短延迟时间上，也得到较好的效果。

[1]魏志强，杨光，丛艳平.水下传感器网络安全研究[J].计算机学报，2012，35（8）：1595-1606.

[2]黄艳，梁韦华，于海斌.一种高效覆盖的水下传感器网络部署策略[J].电子与信息学报，2009，31（5）：1036-1040.

[3]Zhou Zhong，Peng Zheng，Cui Junhong.Efficient multipath communication for time-critical applications in underwater acoustic sensor networks[J].IEEE-ACM Transactions on Networking，2011，19（1）：28-41.

[4]Li Bin，Zhou Zheng，Zou Weixia.Quantum memetic evolutionary algorithm-based low-complexity signal detection for underwater acoustic sensor networks[J].IEEE Transactions on Systems，2012，42（5）：626-640.

[5]夏娜，王长生，郑榕.鱼群启发的水下传感器节点布置[J].自动化学报，2012，38（2）：296-303.

[6]Stefanov A，Stojanovic M.Design and performance analysis of underwater acoustic networks[J].IEEE Journal on Selected Areas in Communications，2011，29（10）：2012-2021.

[7]Wang K，Gao H，Xu X，et al.An energy-efficient reliable data transmission scheme for complex environmental monitoring in underwater acoustic sensor networks[J].IEEE Sensors Journal，2015，16（11）：4051-4062.

[8]Zhou Z，Yao B，Xing R，et al.E-CARP：An energy efficient routing protocol for UWSNs in the Internet of underwater things[J].IEEE Sensors Journal，2015，16（11）：4072-4082.

[9]Pompili D，Akyildiz I F.A multimedia cross-layer protocol for underwater acoustic sensor networks[J].IEEE Transactions on Wireless Communications，2010，9（9）：2924-2933.

[10]Polprasert C，Ritcey J A，Stojanovic M.Capacity of OFDM systems over fading underwater acoustic channels[J].IEEE Journal of Oceanic Engineering，2011，36（4）：514-524.

[11]Liu Chunshan，Zakharov Y V，Chen Teyan.Doubly selective underwater acoustic channel model for a moving transmitter/receiver[J].IEEE Transactions on Vehicular Technology，2012，61（3）：938-950.

[12]Yang Wenbin，Yang T C.High-frequency channel characterization for M-ary frequencyshift-keying underwater acoustic communications[J].Journal of the Acoustical Society of America，2006，120（5）：2615-2626.

[13]Bhatnagar M R.Performance analysis of a path selection scheme in multi-hop decode-and-forward protocol[J].IEEE Communications Letters，2012，16（12）：1980-1983.

[14]Pelekanakis K，Baggeroer A B.Exploiting space-timefrequency diversity with MIMO-OFDM for underwater acoustic communications[J].IEEE Journal of Oceanic Engineering，2011，36（4）：502-513.

[15]Karmokar A K，Djonin D V，Bhargava V K.Cross-layer rate and power adaptation strategies for IR-HARQ systems over fading channels with memory：A SMDP-based approach[J].IEEE Transactions on Communications，2006，56（8）：1352-1365.

[16]Pompili D，Melodia T，Akyildiz I F.Distributed routing algorithms for underwater acoustic sensor networks[J].IEEE Transactions on Wireless Communications，2010，9（9）：2934-2944.

[17]Xu Junfeng，Li Keqiu，Min Geyong.Asymmetric multipath division communications in underwater acoustic networks with fading channels[J].Journal of Computer and System Sciences，2013，79（2）：269-278.

[18]Zhang Song，Li Deshi，Chen Jian.A link-state based adaptive feedback routing for underwater acoustic Sensor networks[J].IEEE Sensors Journal，2013，13（11）：4402-4412.