基于串型路由的水声通信网络ALOHA协议性能分析

汪生泉, 孙大军, 张友文

(1. 哈尔滨工程大学 水声技术重点实验室，黑龙江 哈尔滨 150001；2. 哈尔滨工程大学 水声工程学院，黑龙江 哈尔滨 150001)



基于串型路由的水声通信网络ALOHA协议性能分析

汪生泉1,2, 孙大军1,2, 张友文1,2

(1. 哈尔滨工程大学 水声技术重点实验室，黑龙江 哈尔滨 150001；2. 哈尔滨工程大学 水声工程学院，黑龙江 哈尔滨 150001)

摘要：针对水下通信网络串型路由应用，为获取ALOHA协议最佳性能，基于现有水声通信装备及水声信道参数，建立了串型水声通信网络模型。分析了ALOHA协议在串型水声通信网络的交付率、吞吐量及端对端时延等网络性能测度，推导了获取最佳网络性能的网络参数配置条件，并通过NS3仿真软件对基于串型路由的水声通信网络ALOHA协议性能进行仿真分析，结果表明：该协议在负载的若干特定点上能够获得最佳性能，仿真结果与理论分析一致，进而为该协议的实际应用提供了理论依据。

关键词：ALOHA协议；串型路由；交付率；吞吐量；端到端时延

由于通信网络节点发送功率和水声信道带宽的限制[1-4]，基于水声通信网络的点对点远距离稳健数据交互面临着极大的挑战，有效的路由协议是水声通信网络信息交互性能的关键。串型路由ALOHA协议[5]在复杂的水声通信网络中也取得了广泛的应用，深入研究ALOHA协议在串型路由水声通信网络中的网络性能具有重要意义。纯ALOHA协议由于缺少避碰机制，其最大吞吐量仅为0.184[6]。针对ALOHA协议改进的协议有很多，如N. Chirdchoo等提出了碰撞避免Aloha(Aloha-CA)和预先通知Aloha(Aloha-AN)[7]等，在一定程度上提高了网络吞吐量。但针对现有水声通信装备性能及水声信道参数约束下串型路由ALOHA协议的最优网络性能参数配置的理论研究尚无深入研究。本文通过建立串型路由水声通信网络模型，研究ALOHA协议在串型水声通信网络的交付率、吞吐量及端对端时延等网络性能测度，推导出获取最佳网络性能的网络参数配置，从而为ALOHA协议在串型路由水声通信网路中的应用提供理论支撑。

1水声通信网络串型路由模型

由n个通信节点构成的串型水下通信网络 (如图1所示)，其中第1个节点(编号为1)和最后一个节点(编号为n)为水面节点，中间为水下节点(编号从2～n-1)。相邻节点间距离相等，仅节点1产生数据流采用固定间隔发送数据模式，水下节点仅负责转发，将上一跳节点的数据转发给下一跳节点，节点n为目的节点负责接收。

图1　串型路由水声通信网络模型Fig. 1　A model of string underwater sensor networks

对于任意节点j(1

在该模型下，在水声信道环境较好的情况下，在节点2处会导致数据包丢失的原因如下：1)节点1发送的前后2个数据包的间隙小于数据包的发送时延，造成节点2转发节点1的前一个数据包时，节点1发出的后一个数据包已经到达，此时由于节点2处于发送状态无法接收。2)节点1发送的数据包与节点3转发的数据包在节点2处发生碰撞。

2最优网络性能测度

作如下假设：

1)所有数据包长度相同，数据包调制/解调所需时间用Td表示，归一化为1；

2)节点之间的平均传播时延为τ，归一化后为α=τ/Td；

3)节点1发送数据包按固定间隔产生，前后2个数据包之间的时间间隙为Tinterval，归一化后为β=Tinterval/Td；

4)网络运行时间为Tsim。

2.1碰撞规律

碰撞规律定理：节点1发送的第k个数据包经过节点2、节点3转发后再次到达节点2，如果节点1发送的第j个数据包(j>k)，与第k个数据包在节点2处没有发生碰撞，那么这2个数据包也不会在后续的节点处发生碰撞。

证明：

第k个数据包的发送时间是(k-1)β+(k-1)经过节点2、节点3转发后再次到达节点2，被节点2接收的时间区间为

(1)

第j个数据包发送时间是(j-1)β+(j-1)，节点2接收第j个数据包的时间区间为

(2)

结合式(1)、(2)可得第k个数据包与第j个数据包碰撞的充要条件:

或

推导后可得

(3)

那么第k个数据包与第j个数据包不碰撞的充要条件为

(4)

同理可得：如果节点1发送的第j个数据包(j>k)，与第k个数据包在节点2处没有发生碰撞，则第j个数据包到达节点3的时间区间为

(5)

第k个数据包的发送时间是(k-1)β+(k-1)经过节点2、节点3、节点4转发后再次到达节点3的时间区间为

(6)

同上，得到第k个数据包与第j个数据包在节点3处不碰撞的充要条件为

(7)

式(4)、(7)完全相同，即如果第k个数据包与第j个数据包在节点2处不碰撞，那么第k个数据包与第j个数据包在节点3处不碰撞。以此类推，第k个数据包与第j个数据包在后续节点处均不会发生碰撞，从而命题结论得证。

碰撞规律推论：数据包的碰撞仅仅会发生在节点2处。

2.2网络交付率

网络的交付率是串型路由水声通信网络关注的重要指标，若相邻节点链路的交付率为Pj→j+1，则串型网络的整体交付率P表达式为

(8)

根据推论可知当j≥2时，Pj→j+1=1，则串型网络的整体交付率P表达式为

(9)

2.3网络吞吐量

网络吞吐量与交付率关系表达式如下

(10)

(11)

2.3.1当0≤β<1时网络吞吐量分析

当0≤β<1时，节点1发送的2个数据包之间的间隙小于数据包的发送时间，导致在节点3发数据包的信号到达节点2时会和节点1发出的数据包中的1个或者连续2个发生碰撞。

若节点3转发的数据包为第1个包，根据式(4)可知，节点1发出的第j个数据包与节点3转发的数据包在节点2处碰撞的条件为

(12)

当α∈[k,k+0.5)，k是大于或等于0的整数，则节点1发出的第k+2个数据包至第个2(k+2)个数据包，一共涉及k+3个数据包中的1个或者连续2个数据包会与节点3转发的数据包在节点2处碰撞。根据β取值的不同，碰撞的点也不一样，图2是0≤β<1时的碰撞规律示意图。

图2　当0≤β<1时的碰撞规律示意图Fig. 2　Regular patterns of data packets collisions where 0≤β<1

设j是自然数，且j∈[k+2,2(k+2)]。

1)若j是偶数。

假设2α=2k+ε,(0≤ε<1)，有

若j=2k+4，则节点3发出的数据包仅与节点1发出的第j个数据包数据包发生碰撞是不可能的。原因是节点1的第j=2k+4个数据包与节点3的数据包发生碰撞的β区间为

左侧为

右侧为

这与0≤β<1矛盾，因此，j=2k+4时，节点3的数据包是不可能仅与节点1发出的第j个数据包发生碰撞的。

2)若j是奇数。

综上，将上述0≤β<1，α∈[k,k+0.5)且α>0时的吞吐量表达式如下

(13)

同样，当α∈[k-0.5,k)，k是自然数。则节点1发出的第k+2个数据包至第2(k+2)-1个数据包中的1个或连续2个与节点3转发的数据包在节点2处碰撞。设j是自然数，且j∈[k+2,2(k+2)-1]，则吞吐量表达式如下

(14)

2.3.2当β≥1时网络吞吐量分析

当α∈[k-0.5,k+0.5)，k是自然数。则节点1发出的第2～k+2个共计k+1个数据包中的1个可能会与节点3转发的数据包在节点2处碰撞。

设j是自然数，且j∈[2,k+2]。

综上，将上述β≥1，α∈[k-0.5,k+0.5)时的吞吐量表达式总结如下

(15)

图3　β≥1时的碰撞规律示意图Fig. 3　Regular patterns of data packets collisions where β≥1

图4　β∈[0,1),α∈[k,k+0.5)最大吞吐量原理图Fig. 4　The maximum throughput whereβ∈[0,1),α∈[k,k+0.5)

2.3.3网络最大吞吐量分析

1)当β∈[0,1)时的最大网络吞吐量分析。

①β∈[0,1),α∈[k,k+0.5)时。

根据式(13)，在β∈[0,1),α∈[k,k+0.5)区域内，节点碰撞被分为4种碰撞类型，节点3与第奇数个包、与第偶数个包以及与以奇数开头的连续2个包碰撞、与以偶数开头的连续2个包碰撞。各种类型碰撞的吞吐量结果不同，在相应的区间上随着β的增大，其吞吐量不断减小，因此对应各个碰撞类型的吞吐量最大值在相应区间最左侧的点处。

设与以奇数开头的连续2个包碰撞的吞吐量最大值为TP1，则

(16)

设与第奇数个包碰撞的最大吞吐量为TP2，则

(17)

设与以偶数开头的连续2个包碰撞的吞吐量最大值为TP3，则

(18)

设与第偶数个包碰撞的吞吐量最大值为TP4，则

(19)

比较式(16)～(19)可知：TP2=TP4>TP1，TP2=TP4>TP3。

②β∈[0,1),α∈[k-0.5,k)时。

图5　β∈[0,1),α∈[k-0.5,k)时最大吞吐量原理图Fig. 5　The maximum throughput whereβ∈[0,1),α∈[k-0.5,k)

根据式(14)，当β∈[0,1),α∈[k-0.5,k)，节点碰撞分为4种类型。即：节点3与第奇数个包、与第偶数个包、与以奇数开头的连续2个包、与以偶数开头的连续2个包碰撞。各种类型的吞吐量在相应的区间上随着β的增大而减小，因此对应各种碰撞类型的最大吞吐量在相应区间最左侧的点处。

设与以偶数开头的连续2个包碰撞的最大吞吐量为TP5，则

(20)

设与第偶数个包碰撞的最大吞吐量为TP6，则

(21)

设与以奇数开头的连续2个包碰撞的最大吞吐量为TP7，则

(22)

设与第奇数个包碰撞的最大吞吐量为TP8，则

(23)

比较式(20)～(23)有

TP6>max{TP5,TP7,TP8}

综上所述，当β∈[0,1)时，吞吐量的最大值是节点3转发的包仅与节点1发出的第2k+3(最大奇数)个或第2k+2(最大偶数)个数据包碰撞的时候达到，其中2个包之间的间隙β取对应区间的最小值。

图6　β∈[1,+)时最大吞吐量原理图Fig. 6　The maximum throughput whereβ∈[1,+)

设碰撞的最大吞吐量为TP9，则

(24)

设不碰撞的最大吞吐量为TP10，则

(25)

比较式(24)、(25)可知：TP10>TP9。

综合式(17)、(19)、(21)、(25)，可得以下重要结论。即在给定α的条件下，网络的最大吞吐量为

(26)

3仿真实验分析

3.1实验参数配置

仿真采用NS3仿真软件进行仿真，仿真参数配置为：节点数量7个，相邻节点距离为5 000 m，声速1 500 m/s，数据包长度为2 048 bit，发送速率为1 024 bit/s，仿真时间为3 600 s。

3.2仿真结果及分析

仿真不断改变数据包间隙β(即网络负载)，仿真结果与理论计算结果对比如图7～9所示。

1)吞吐量分析

仿真值比理论值稍滞后一点，原因是由于处理时延非常小，在吞吐量理论分析时没有考虑数据包的处理时延造成的偏移。从图7可以看出，实验结果存在2个吞吐量最大值的点，一个在其数据包发送间隙0～1区间上，另一个在大于1的区间上，与理论分析一致。

图7　网络吞吐量随数据包发送间隙β变化曲线Fig. 7　Throughput as the delivering interval β between data packets is varied

2)交付率分析

交付率的仿真值和理论值一致，由于理论分析时没有考虑数据包的处理时延造成的存在仿真值比理论值稍滞后一点。图中存在三段交付率为1的区间，其数据包发送间隙β均大于1。很显然，β值较小的区间其吞吐量更大。

图8 交付率随数据包发送间隙β变化曲线Fig. 8　Delivery rate as the delivering intervalβbetween data packets is varied

3)网络时延分析

从图9可以看出，网络时延基本保持在32.4 s左右，很稳定，原因是发送时延、数据处理时延以及传播时延基本是固定不变的。

图9　端到端时延随数据包发送间隙β变化曲线Fig. 9　End-to-end delay as the delivering interval β between data packets is varied

4)综合分析

综合对比图7、8可知，在0≤β<1区间上取得吞吐量最大值的点，所在区间的交付为0.5，也就是说，节点1发送的数据包有一半丢失了，尽管吞吐量较大，但节点消耗的能量较多。在β≥1区间上取得吞吐量最大值的点，所在区间恰好是三段交付率为1的区间的第一段，与0≤β<1区间上的取得吞吐量最大值的点比较，2个点吞吐量一样大，但此处交付率为1，没有造成包的丢失，能耗较小。上述2个点端到端时延基本没有区别。

4结束语

目前ALOHA协议在功能较为单一水声通信网络中应用广泛，但其实际的最优性能与节点布放以及通信装备的参数有着密切的关系，本文基于水声通信网络的3种性能评价指标(即数据交付率、吞吐量以及端对端时延)，推导了串型路由条件下获取最佳网络综合性能的参数配置条件，仿真实验验证了本文的理论分析结论，该理论分析为该协议的实际应用提供有力的指导依据。

参考文献：

[1]周密, 崔勇, 徐兴福, 等. 水声传感网MAC协议综述[J]. 计算机科学, 2011, 38(9): 5-10, 17.

ZHOU Mi, CUI Yong, XU Xingfu, et al. Survey of the MAC protocols on underwater acoustic sensor network[J]. Computer science, 2011, 38(9): 5-10, 17.

[2]DOMINGO M C. Overview of channel models for underwater wireless communication networks[J]. Physical communication, 2008, 1(3): 163-182.

[3]NASRI N, KACHOURI A, ANDRIEUX L, et al. Design considerations for wireless underwater communication transceiver[C]//Proceedings of the 2nd international conference on signals, circuits and systems (SCS). Monastir: IEEE, 2008: 1-5.

[4]CATIPOVIC J A. Performance limitations in underwater acoustic telemetry[J]. IEEE journal of oceanic engineering, 1990, 15(3): 205-216.

[5]ROBERTS L G. ALOHA packet system with and without slots and capture[J]. ACM SIGCOMM computer communication review, 1975, 5(2): 28-42.

[6]BERTSEKAS D P, GALLAGER R. Data networks[M]. 2nd ed. New Jersey: Prentice hall, 1992.

[7]CHIRDCHOO N, SOH W S, CHUA K C. Aloha-based MAC protocols with collision avoidance for underwater acoustic networks[C]//Proceedings of the 26th IEEE international conference on computer communications. Anchorage, AK, USA: IEEE, 2007. -----------------------------------------------------------------------------------------------------------

Performance analysis for ALOHA protocol of underwater acoustic networks with a serial route

WANG Shengquan1,2, SUN Dajun1,2, ZHANG Youwen1,2

(1. Acoustic Science and Technology Laboratory, Harbin Engineering University, Harbin 150001, China; 2. College of Underwater Acoustic Engineering, Harbin Engineering University, Harbin 150001, China)

Abstract：Based on the application of a serial route for underwater acoustic communication networks, in order to optimize the performance of the ALOHA protocol, we designed a serial route underwater acoustic network model that uses available underwater acoustic communication equipment and underwater acoustic channel parameters. We analyzed the performance measurements of the ALOHA protocol in terms of delivery rate, throughput, and end-to-end delay, and deduced the optimal conditions for parameter configuration. The network performance was also appraised via NS3 simulation software. The simulation results suggest that at certain network load points, optimal performance can be achieved. The results of our simulation and theoretical analysis are almost identical, providing a basis for further application of this protocol.

Keywords：ALOHA protocol; serial route; delivery rate; throughput; end-to-end delay

中图分类号：TN929

文献标志码：A

文章编号：1006-7043(2016)03-360-08

doi:10.11990/jheu.201501013

作者简介：汪生泉(1980-), 男, 助理研究员,博士；通信作者：孙大军，E-mail：sundajun@hrbeu.edu.cn.

基金项目：国家自然科学基金资助项目(50909029,61471138).

收稿日期：2015-01-12.

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160105.1604.004.html

网络出版日期：2016-01-05.

孙大军(1972-), 男, 教授,博士生导师.