Algorithms and Analysis of Circle-Avoidance ROFC-LF with Unequal Error Protection for Underwater Acoustic Networks

LIU Xiu-xiu, DU Xiu-juan, HAN Duo-liang

ACTA ELECTRONICA SINICA ›› 2024, Vol. 52 ›› Issue (8) : 2591-2606.

PDF(1627 KB)
CIE Homepage  |  Join CIE  |  Login CIE  |  中文 
PDF(1627 KB)
ACTA ELECTRONICA SINICA ›› 2024, Vol. 52 ›› Issue (8) : 2591-2606. DOI: 10.12263/DZXB.20230660
PAPER

Algorithms and Analysis of Circle-Avoidance ROFC-LF with Unequal Error Protection for Underwater Acoustic Networks

Author information +

Abstract

With the development of smart ocean, the transmission of multimedia data in underwater acoustic networks (UANs) has received much attention from scholars. The highly dynamic topology of UANs leads to incomplete data transmission between neighboring nodes, and the different portions of compressed data such as underwater images or videos have different effects on their reconstruction quality. Hence, UANs require coding mechanisms with unequal error protection (UEP) to encode and decode multimedia data. The recursive online fountain code with limited feedback (ROFC-LF) has the advantages of low overhead, less feedback and simple compiled codes, which is suitable for UANs. Combined with the characteristics of underwater acoustic channels, such as narrow bandwidth, long delay and energy limitation, this paper systematically analyzes the problem of the cycles existing in the build-up phase of ROFC-LF and proposes two optimization objectives to address the cycle problem as well as the UEP problem. In addition, a circle-avoidance ROFC-LF with UEP is presented for UANs. This coding mechanism reduces the number of useless encoded packets due to the presence of cycles in the largest component during the the build-up phase, which in turn decreases the energy consumption. To achieve the UEP property, a weighted-selection strategy is used in the build-up phase, whereas a priority strategy is employed in the completion phase. The proposed coding mechanism is analyzed based on the random graph theory, and the theoretical results are consistent with the simulation experimental results. The results show that the proposed coding mechanism can quickly recover important data while reducing the number of coded packets, and is suitable for transmitting multimedia data of varying importance in UANs with dynamically changing network topology.

Key words

underwater acoustic networks / recursive online fountain code with limited feedback / unequal error protection / circle-avoidance / weighted-selection / data priority

Cite this article

Download Citations
LIU Xiu-xiu , DU Xiu-juan , HAN Duo-liang. Algorithms and Analysis of Circle-Avoidance ROFC-LF with Unequal Error Protection for Underwater Acoustic Networks[J]. Acta Electronica Sinica, 2024, 52(8): 2591-2606. https://doi.org/10.12263/DZXB.20230660

1 引言

水声网络(Underwater Acoustic Networks,UANs)是智慧海洋的重要组成部分,是实现海洋数字化、生态化、安全化与和谐化的关键技术.UANs采用声波通信,声波在UANs中的传播速度仅1500m/s,比光波和电磁波低5个数量级,导致UANs传播时延长;UANs传输数据率低造成传输时延长;水声Modem采用半双工通信,收发状态转换时延长;这些情况导致UANs节点之间通信时延长.UANs一般多采用电池供电,由于水下环境恶劣,导致电池更换难度大;传感器节点长期浸泡在海水中,由于海水腐蚀和环境影响,节点容易损坏,更换困难;水下传感器节点随水流移动,尤其随着自主水下航行器(Autonomous Undersea Vehicles,AUV)的发展,节点移动速度更快,导致短时间内两个原本相邻的节点移出传输范围;例如,如果传输范围为1 500 m,两个节点之间的初始距离为750 m,如果这两个节点向相反方向移动,移动速度是3 m/s,它们大约125 s内超出彼此的传输范围.以上这些情况导致UANs网络拓扑结构高度动态变化1~3.
长时延和动态网络拓扑特性导致水下传感器节点单跳内传输的数据量受限;传输MPEG或H.264压缩后的水下图像或视频时,由于不同类的数据对图像或视频重建质量影响不同,对视频或图像重建起着至关重要作用的数据需要更快、更好、更准确地恢复4~6;特殊应用中控制信息比用户数据更重要6,也需要更快、更准确地完成译码恢复,比如水下机器人作业.水声信道带宽窄,需要合理分配有限的带宽资源,使得恢复的图像或视频满足人眼视觉要求,需要尽快恢复出重要数据7.因此,UANs具有带宽窄、延时长、能源受限、网络拓扑结构动态变化等特点,这些特点导致UANs需要对数据进行不等差错保护(Unequal Error Protection,UEP),实现重要数据的快速恢复.
UANs数据的不等差错保护有基于调制技术的UEP,基于编码的UEP,调制和编码结合实现UEP特性等.Esmaiel等人8提出了基于空间调制(Spatial Modulation,SM)的水下物联网图像传输的不等差错保护方案,该方案利用不同的调制方式来实现数据的不等差错保护,重要的数据信息通过低误码率SM传输携带信息单元进行传输.该方案仅仅利用底层调制技术来实现UEP特性,无法保证数据的可靠传输.Rahmati等人9为了将水下自适应视频传输失真保持在可接受的阈值之内,提出利用发散空间多路复用和不等差错保护的跨层技术来保证视频效果.该技术仅通过增加重要数据的冗余实现不等重要性数据的UEP,数据冗余只是复制数据,是最简单的实现UEP的方式,同样也无法实现数据的可靠传输.因此,将编码和UEP结合能很好地实现不等差错保护和可靠传输.Cai等人7提出了利用低密度奇偶校验(Low-Density Parity-Check,LDPC)编码对水下图像传输进行非对等保护,LDPC码是采用固定码率的纠错码,不适用于具有可变纠删概率的水声信道.Esmaiel等人10提出了水声信道中利用里德-所罗门码(Reed-Solomon codes,RS codes)与分层正交幅度调制相结合的不等差错保护技术,保护传输敏感的编码信息,然而,RS codes编译码过程要求域运算,计算开销较大,不适用于计算资源受限的水下传感器节点.Zhao等人5为了满足水下图像或视频的传输,提出了加权扩展窗喷泉码,通过不均匀选择每个窗口内的原始包来实现UEP.喷泉码是一类无码率编码,更适合于高动态变化的水声信道11,且能保证数据的可靠传输.因此,研究具有UEP特性的喷泉码引起了国内外学者的关注.
目前,具有UEP特性的喷泉码分为三种类型:加权UEP喷泉码1213、加窗类UEP喷泉码14~19和复制过程类UEP喷泉码20.宋鑫等人12提出了系统 UEP-LT(Luby Transform)编码方案,无速率段的节点采用加权方式选取邻居消息节点,实现了重要数据优先译码的功能;但LT码依据度分布函数生成度值,发送方无法了解解码状态.田远等人13通过分析多信源的中继通信系统中各信源的原始数据长度差异,对传输可靠性的需求不同,提出了分布式不等差错保护喷泉码;但该研究是面向无线体域网的,不能直接用于UANs.Sejdinovic等人16提出了扩展窗口喷泉码来实现UEP特性,相比LT码,该文献提出的扩展窗口喷泉码需要附加参数,增加了设计复杂性.黄太奇等人17提出了一种可适用于加性高斯白噪声信道的融合扩展窗喷泉码和规则变量节点度LT码的UEP算法,能对重要等级数据提供较强保护;除了要依据度分布函数外,还需要依据变量节点度分布函数,发送方仍无法了解解码状态,还增加了编码复杂度.石东新等人18提出一种删除信道下具有UEP特性的系统Raptor码,该码采用简化的扩展窗喷泉码技术对RFC 5053标准系统Raptor码的中间符号进行编码,使得编码符号在具有UEP性能的同时仍能维持系统性;但需要舍去部分次重要数据.王慧等人19提出了一种自适应UEP喷泉编码策略,其能根据信道丢包率不同自适应选择编码参数及编码方案,提高了信息传输效率;但重要信息解码完成后仍存在占用编码冗余的问题.邓在辉等人20对基于块复制的UEP喷泉码进行了理论分析,提出了改进的信息符号选取策略,让度1编码符号全部在重要数据中选取,一定数量度2编码符号分别在重要数据和次要数据中选取,从局部上提升对重要数据的保护;同样存在发送方无法了解解码状态的问题.综上所述,喷泉码要依靠度分布函数生成度值,无法进行在线控制.
由于喷泉码的解码过程不能被接收者控制和监督,因此,近几年,学者们提出了具有在线控制能力的在线喷泉码(Online Fountain Code,OFC)21.与喷泉码相比,OFC具有良好的实时性能及编译码开销低的特点;因此,越来越多的学者开始研究具有UEP特性的OFC来实现数据的不等差错保护.Huang等人22提出了一种采用加权选择策略和扩展窗口策略来实现具有UEP特性的OFC,重要数据完全恢复后,次重要数据仍然采用扩展窗策略,在所有原始包中选择原始包进行编码,增加了无用编码包的数量.Cai等人23采用扩展窗口策略实现两种具有UEP特性的OFC,保证了优先级越高的数据需要更少的恢复时间,和文献[22]相同,完成阶段恢复次重要性数据时,降低了有用编码包的概率.Duan等人24提出了一种新的具有顺序窗口策略的UEP特性的OFC,能在完成阶段先完成重要数据解码,并给次重要数据提供最佳的保护;但在建立阶段增加最大组件占比将影响数据的恢复速度.Shi等人25提出了一种高效的不等差错保护OFC;在构建阶段,提出了遍历选择策略来选择最重要数据;然后,在完成阶段,应用加权选择策略以提供低开销;但在完成阶段采用权重策略,不能以最快速度恢复重要数据信息.
文献[22~25]均是将UEP和OFC结合来实现数据的不等差错保护.但是OFC在完成阶段传输了部分对解码无用的编码包以及较多的反馈包26.考虑UANs低带宽、长传播延时、高误码率、长状态切换延时等特点,传输无用的编码包和过多的反馈包将降低水声信道利用率,消耗能源,缩短网络生命周期.因此,文献[22~25]基于OFC实现数据的UEP特性不适用于UANs.因此,本文基于文献[26]的UANs中递归与限制反馈的OFC(Recursive OFC with Limited Feedback,ROFC-LF),结合UEP特性和对文献[22~25]的分析,提出不等差错保护的避环ROFC-LF码用于UANs.
ROFC-LF编码机制是适合UANs的无速率编码,比OFC的开销低,反馈包数量少,其为数据的传输提供等差错误保护(Equal Error Protection,EEP)26.然而,对于网络拓扑动态变化的UANs而言,需要使用具有UEP功能的编码机制来处理原始数据包.因此,本文改进ROFC-LF的编解码算法,提出了不等差错保护的避环ROFC-LF码用于UANs传输具有UEP特性的多媒体数据.本文的主要贡献概括如下.
(1)针对UANs的带宽窄、延时长和能量受限等特点,分析了ROFC-LF机制在建立阶段的连通组件中环的形成带来的弊端,提出数据不等差错保护和避环的优化目标.根据优化目标,对ROFC-LF码算法进行改进,提出了不等差错保护的避环ROFC-LF编码机制,利用算法1避免了ROFC-LF码最大组件形成环的问题,避免了无效编码包,在提高信道利用率、减少能耗的同时,能更快地恢复重要性数据.
(2)采用了权重策略和优先级策略实现不等差错保护;改变建立阶段权重占比,可以调节数据的恢复速度;提高重要数据占比,在编码包总数量不变的前提下加快了重要数据的恢复;完成阶段采用集合优先级策略,在不影响次重要数据的恢复前提下能快速恢复重要数据信息,实现了对数据的不等差错保护.
(3)基于随机图理论分析了不等差错保护的避环ROFC-LF码解码所有原始包需要的编码包数量和解码不同重要性数据需要的编码包数量问题.理论分析和仿真实验表明,该编码机制在恢复重要性数据、次重要数据和恢复所有数据三方面均具有较好的性能,适用于网络拓扑结构高度动态变化的UANs传输重要性不等的多媒体数据.

2 相关工作

相比有线网络和陆上无线传感器网络,UANs多媒体数据的可靠传输面临着更多挑战.一方面,水下环境复杂多变以及网络拓扑结构高度动态变化,这就需要尽可能快地传输重要的多媒体数据信息;另一方面,除了保证重要数据更快传输,还需考虑节能、有效的利用带宽资源等问题.因此,UANs需要开销低、反馈少、能对多媒体数据实现不等差错保护的高效编码机制.近几年,学者们将喷泉码用于UANs来实现UEP特性和可靠传输235.喷泉码是基于二部图的高性能稀疏无码率编码,编码冗余少,对于恢复 k个原始包,需要 n(nk)个编码包7.喷泉码具有简单的编译码算法、较小的编译码开销和较低的编译码复杂度,适合用于删除信道.为了更好地控制喷泉码的编解码过程,Cassuto等人21提出的OFC备受关注,其具有在线编解码能力,能根据任何给定的解码状态计算出最优的编码策略,无速率编码,相比LT码和Growth码,OFC在译码开销方面也具有较好的性能.
在完成阶段,虽然OFC已是寻找最优策略进行编码,但接收方仍然丢弃了很多已经成功接收的编码包.OFC通过反馈实现在线性能,接收者能够控制和监督编解码过程,但是对于半双工通信的UANs而言,OFC的反馈包数量过多.传输无用的编码包和过多的反馈包将降低了信道利用率,缩短了网络生命周期.因此,适用于UANs的OFC应该不传输无用的编码包且具有较少的反馈.综上所述,OFC不能直接用于UANs.文献[2627]根据UANs的特点,提出了适用于UANs的OFC编码机制,其中文献[26]给出了解码相同数量的原始包,ROFC-LF码开销更低,比如成功解码1 000个原始包,Growth码的开销约为0.5,LT码的开销约为0.4,OFC码的开销约为0.2,而ROFC-LF码的开销约为0.05;可见,ROFC-LF码更适合UANs.ROFC-LF编码机制对数据进行等差错误保护,无法优先恢复重要数据,本文根据UANs的特点,结合UEP特性,对ROFC-LF编码机制的编解码算法进行改进,提出了具有不等差错保护的避环ROFC-LF编码机制.因此,本文相关的研究工作主要包括不等差错保护和ROFC-LF编码机制.

2.1 不等差错保护

具有不等重要性的数据需要在信道编码时对重要等级的数据进行保护,这就是不等差错保护 (Unequal Error Protection,UEP),也就是为重要数据(Most Important Data,MID)和次重要数据(Least Important Data,LID)提供不同程度的保护,从而使MID能够被优先恢复出来5612~2022~25.UANs网络拓扑动态变化及水声信道带宽窄,导致了需要尽快恢复重要的多媒体数据;因此,UANs多媒体数据的传输需要采用UEP保护,让MID尽快恢复.
喷泉码是无码率码,无须考虑水声信道删除概率,且编译码简单,因此,很多学者研究喷泉码的不等差错保护.近几年,随着具有在线控制能力的OFC21提出,很多学者着手研究OFC的性能,与喷泉码相比,OFC具有良好的实时性能及编译码开销低等优点,因此,具有UEP特性的OFC引起学者关注22~25.目前,OFC实现UEP特性主要有四种方法,权重、扩展窗、按序窗口和优先级.权重是通过对MID和LID添加不同权重比例来实现MID恢复的比LID更快.扩展窗策略主要通过以不同概率选择扩展窗的方式来提高MID参与编码的概率.按序窗口和优先级主要根据数据的重要等级顺序来依次编解码.

(1) 权重策略

假设有 k个原始包,原始包序号越小优先级越高,根据数据优先级划分为 r个等级集合,即 s1 s2 s3,…, sr;这些等级集合分别包含 α1k α2k α3k,…, αrk个原始包,其中, i=1rαi=1,如图1所示. r个等级集合的数据重要性随着 r的增大而降低.权重策略就是给 r个等级集合分配被选择的权重,通过权重不同达到MID的优先恢复的目的.
图1 等级集合

Full size|PPT slide

(2) 扩展窗策略

和权重策略相同,首先将数据根据重要性划分为 r个等级集合.设置第1个窗口 W1=s1,第2个窗口 W2=s1+s2,以此类推,第 n个窗口 Wn=i=1nsi 1nr).根据窗口选择分布函数 P(x)=n=1rPnxn,预先给第 n个窗口设置选择概率 Pn r个窗口的选择概率和为1.首先通过窗口选择概率 Pn选定窗口 Wn,然后再从窗口 Wn中随机选择原始包编码.

(3) 按序窗口策略和优先级策略

根据图1设置的数据等级集合,按照等级顺序完成数据的编解码.也就是先完成集合 s1所有原始包的编解码,再去编解码集合 s2,以此类推,直到集合 sr完成数据的编解码.

2.2 ROFC-LF编解码机制

ROFC-LF编解码过程由建立阶段和完成阶段组成,两个阶段的解码图用一部图表示,如图2所示.图2中的一个节点表示一个原始包,一条边表示由两个原始包异或产生的一个编码包.已被成功解码的原始包表示为黑色节点,未被成功解码的原始包表示为白色节点.图2中标记了部分节点( k1 k2 k3 k4 k5 k6)和边( E1 E2 E3).连接到一起白色节点及其连边称为一个连通组件(the Connected Component),没有任何一个白色节点连接到其所在的连通组件之外.一个单独的白色节点也称为一个连通组件.连通组件中白色节点的数量称为连通组件大小(the Size of Connected Component).解码图中组件大小最大的连通组件称为最大连通组件(the Largest Connected Component).ROFC-LF详细的编解码过程如下.
图2 解码图

Full size|PPT slide

(1) 编码过程

在建立阶段,发送方在所有原始包中随机选取2个原始包进行编码,形成和发送度2的编码包,直到接收到含“解码图中最大连通组件已达到 kβ0”的反馈包( β0是一个预设的小数,指最大组件的大小与所有原始包数量的比值).根据反馈信息,发送者从所有原始包中随机选择一个原始包,形成和发送度1的编码包,直到收到含“最大组件解码成功”的反馈包.
在完成阶段,发送方根据反馈信息,将所有原始包分为成功解码的原始包集合 Yi(A,SNs)和未成功解码的原始包集合 Wi(k-A,SNs) i表示反馈的次数.发送方接收到反馈包后,根据反馈包中原始包解码状态信息更新集合 Wi(k-A,SNs) Yi(A,SNs).发送方根据类型1与类型2编码包的优化比从集合 Wi(k-A,SNs)中随机选择原始包进行递归编码,发送类型1和类型2编码包,直到接收到含“所有原始包解码成功”信息的反馈包.类型1和类型2编码包定义如下.
类型1:随机从集合 Wi(k-A,SNs)选择一个原始包形成度1的编码包;
类型2:随机从集合 Wi(k-A,SNs)选择两个原始包形成度2的编码包.

(2) 解码过程

在建立阶段的初始,接收方接收度2的编码包,更新解码图并计算最大组件大小;当最大组件达到 kβ0时,接收方反馈“解码图中最大连通组件已达到 kβ0”的反馈包.之后开始接收度1的编码包,直到最大组件解码成功,然后发送“最大组件解码成功”的反馈包.
在完成阶段,接收方接收类型1和类型2的编码包,更新解码图并解码,根据前后两次的解码比例差值 Δβ是否大于阈值 δ来确定是否发送反馈包.也就是:如果连续两次的解码比例差大于 δ就发送反馈包,发送带原始包解码状态的反馈包给发送方;否则,不发送反馈包.持续该过程,直到所有原始包解码成功.
ROFC-LF编码机制根据反馈包中原始包的解码状态字段来获得最优编码方式,解码状态表示为
F'(A)=0,0,0,0,,1,0,0,,0,1,0kbits,thenumberof1isA
(1)
其中,上式中共有 k个比特,按照原始包序号排列,每个比特代表着一个原始包的解码状态,0表示没有解码成功,1表示解码成功.

3 不等差错保护的避环ROFC-LF编码机制

3.1 编码机制

根据文献[26]知,ROFC-LF编码机制在开销、计算复杂度、编码效率和能耗等方面优于现有的OFC编码机制,适合UANs.随着AUV的快速发展,导致UANs网络拓扑结构高度动态变化,需要快速的恢复重要性数据.但ROFC-LF编码机制无法完成MID的快速编解码,因此,需要改进ROFC-LF编码机制的编解码算法来实现数据的不等差错保护.根据文献[21]的推论和文献[28]随机图理论有引理1.根据引理1推断出OFC编码机制在建立阶段形成最大组件过程中产生了环.ROFC-LF和OFC两种编码机制的建立阶段编解码方式相同,因此,ROFC-LF编码机制在建立阶段也存在环的问题.环是对解码无用的编码包,传输无用的编码包将占用信道带宽资源,增大传输延时,消耗能量.综上所述,ROFC-LF编码机制存在两个优化目标,一是避免建立阶段最大组件环的产生;二是改进编解码算法,实现数据的不等差错保护.因此,ROFC-LF编码机制完成以上两个目标的优化,才能更好地适用于网络拓扑动态变化的UANs具有不等重要性的多媒体数据传输.
引理1 OFC编码机制在 c>1的随机图 G(k,c/k)中,除大组件外,几乎所有组件的大小都是 O(logk),带环小组件的数量是非常少的.其中, c是每个原始包平均被选择的次数, k是原始包数量, O表示渐进上界2128.

(1) 环的问题

根据引理1,ROFC-LF编码机制在建立阶段最大组件形成过程中会产生环,如图3所示.图3中,圆圈表示原始包,圈与圈之间的边表示编码包;蓝色圈构成了解码图的最大组件,继续发送4个度2编码包,会产生有用的编码包(蓝线)和无用编码包(带×标志的蓝线).图3中有编码包 E1=k1k2 E2=k2k4 E3=k1k3 E4=k3k4,如果原始包 k1解码成功,则通过编码包 E1 E2 E3,能解码成功原始包 k2 k3 k4.因此,编码包 E4是冗余的、无用的编码包,同时使得图3中形成了含 k1 k2 k3 k4的环,可见,环是对解码无用的.
图3 存在环的最大组件

Full size|PPT slide

假设当解码图中的最大组件达到 kβ kβ<kβ0) 时,继续发送一个度2编码包,只要选择的两个原始包在目前最大组件 kβ中,就会产生环.从最大组件 kβ中选择两个原始包的种类有 Ckβ2种类型,从所有原始包 k中选择两个原始包的种类有 Ck2种类型,则该编码包使得最大组件产生环的概率为 Pcycles=Ckβ2/Ck2=β(kβ-1)/(k-1),如图4所示.从图4看出,随着当前最大组件占比的增大,发送的下一个编码包使得最大组件产生环的概率逐渐增大.例如原始包数量 k=1 000 β0=0.65 β=0.6时,发送的下一个编码包使得最大组件产生环的概率 Pcycles0.3.建立阶段最大组件是随着发送编码包数量的增加而不断增大的过程.根据当前最大组件的大小,能计算出下一个编码包使得最大组件产生环的概率.从图4可知,当前最大组件越大,发送的下一个编码包使得最大组件产生环的概率越大.由此推断,最大组件形成过程中会产生一定数量的环.对于延时大、带宽窄的UANs而言,应该减少无用编码包的数量,环是对解码无用的编码包,因此,在UANs中,采取措施避免最大组件形成环是非常必要的.
图4 下一个编码包使得最大组件产生环的概率

Full size|PPT slide

根据香农定理知,信道容量 C=Blog2(1+S/N)(bit/s),其中, B是信道带宽(Hz), S是信道内所传信号的平均功率(W), N是信道内部的高斯噪声功率(W).对于噪声干扰严重的水声信道而言,信道容量可理解为信道能够达到的最大数据传输速率(bit/s).由于水声信道带宽窄,一般是在几千赫兹到几万赫兹之间,导致信道最大数据传输速率较低;如果在数据传输速率较低的信道上,再传输无用的编码包,将降低带宽的利用率;UANs能量受限,传输无用编码包将增大网络能量消耗,缩短网络生命周期.则应用于UANs中的编码机制应避免最大组件形成环;对于误码率高的UANs,需要增加有效反馈来避免最大组件形成环;因此,本文提出算法1避环算法来改进ROFC-LF的建立阶段,避免解码图中最大组件产生环,提出避环ROFC-LF编码机制.

算法1 避环算法

输入: 存储最大组件原始包序号数组为 D,存储被选择的原始包序号数组为 pos;常数 h=0

输出: 最后选中的2个原始包的序号 m n

1. 首先, pos置空,然后,发送方随机从 k个原始包中选择2个原始包 km kn;存储2个原始包序号 m n到数组 pos

2. FOR i=1:1:pos DO

3.  FOR j=1:1:D DO

4.   IF pos(i)==D(j) THEN

5.     h=h+1

6.   END IF

7.  END FOR

8. END FOR

9. IF h=2 THEN

10.  goto line (1)

11. END IF

表1给出了最大组件占比 β0对ROFC-LF和避环ROFC-LF两种编码需要的编码包和反馈包数量的影响. NROFC-LFe NCAROFC-LFe分别表示ROFC-LF和避环ROFC-LF需要的编码包数量, NROFC-LFf NCAROFC-LFf分别表示ROFC-LF和避环ROFC-LF需要的反馈包数量.根据文献[26]的ROFC-LF编码机制设置仿真参数,原始包数量 k=1 000,反馈限制 δ=0.01,情况1类型编码包占比为0.1.仿真实验结果表明:避环ROFC-LF编码机制比ROFC-LF编码机制需要的编码包数量平均减少了2.4%,验证了避环的有效性.
表1 β0对两种编码机制的编码包和反馈包数量的影响
β0 NROFC-LFe NROFC-LFf NCAROFC-LFe NCAROFC-LFf
0.3 1 036 16 1 038 16
0.4 1 040 15 1 031 15
0.5 1 054 14 1 030 14
0.55 1 062 13 1 028 13
0.65 1 087 11 1 026 11

(2) 不等差错保护

根据表1知,最大组件占比 β0越大,避环ROFC-LF编码机制需要的编码包数量和反馈包数量均越少.考虑到UANs资源的局限性,最大组件占比 β0越大,避环ROFC-LF编码机制越适用于UANs.根据文献[22~25]知,目前建立阶段采用权重策略,最大组件占比相对较大;因此,本文在建立阶段采用权重策略.当建立阶段确定了权重比例后,选择MID集合和LID集合的概率也就确定了.为了让MID更快地完成编解码,完成阶段选择基于优先级的策略来保证最重要的数据能很快完成编解码.综上,为了实现避环ROFC-LF编码机制对数据的不等差错保护功能,建立阶段引入权重策略,完成阶段按数据优先级划分的等级集合序号顺序,从小到大逐个等级完成编解码,达到MID快速恢复的目的.
ROFC-LF编码机制建立阶段通过不同权重实现MID优先编码,也就是让权重高的原始包多参与编码,通过权重来控制不同重要性数据参与编码的频繁程度;完成阶段直接按等级集合序号顺序完成编解码.通过权重和数据优先级两项策略来实现ROFC-LF编码机制对数据的不等差错保护.结合算法1避环算法,对ROFC-LF编码机制的编解码算法进行改进,提出了不等差错保护的避环ROFC-LF编码机制.

3.2 编解码算法

不等差错保护的避环ROFC-LF编码机制建立阶段采用权重策略,和2.1节的权重策略相同,同样假设有 k个原始包,原始包序号越小优先级越高,划分 r个等级集合, s1 s2 s3,…, sr,分别包含 α1k α2k α3k,…, αrk个原始包,其中, i=1rαi=1,如图1所示.建立阶段在形成最大组件之前,均是发送度2的编码包. r个等级集合,一共有 r+1种类型的原始包选择方法,同时产生 r+1种类型的编码包集合,编码包集合记为 C1 C2 C3,…, Cr Cr+1,如图5所示.编码包集合 C1是从原始包等级集合 s1中随机选择2个原始包,形成和发送的度2的编码包;编码包集合 C2是从原始包等级集合 s2中随机选择2个原始包,形成和发送度2的编码包;编码包集合 Cr是从原始包等级集合 sr中随机选择2个原始包,形成和发送度2的编码包;编码包集合 Cr+1是从 k个原始包中随机选择2个原始包,形成和发送度2的编码包.产生 Cr+1编码包集合的原因是为了让各个独立的编码包集合连通起来形成最大组件. r+1个原始包集合被选择的概率分别为 q1 q2 q3,…, qr qr+1,且 q1+q2+q3++qr+qr+1=1.不等差错保护的避环ROFC-LF编码机制达到最大组件后,在 k个原始包中随机选择一个原始包,发送度1的编码包直到最大组件解码成功.完成阶段采用数据优先级策略编解码,即按着等级集合序号从小到大依次完成编解码.结合算法1,详细的编解码过程见算法2.
图5 编码包集合

Full size|PPT slide

算法2 不等差错保护的避环ROFC-LF编解码过程

输入: k个原始包;存储最大组件原始包序号 D;集合 s1, s2, s3,…, sr+1;权重 q1, q2, q3,…, qr, qr+1

输出: 编码包数量,反馈包数量

1. WHILE 未成功解码DO

2. 建立阶段

3. WHILE 发送方未收到含“达到最大组件”反馈DO

4.  根据 r个集合的权重选择集合 sj( 1jr+1),在集合 sj随机选择2个原始包 km kn

5.  执行算法1

6.  2个原始包编码,发送该编码包,记录编码包数量;重构最大连通组件;判断2个原始包序号是否属于最大组件,然后决定2个原始包的序号是否存储到 D

7.  IF 最大组件大小 Dkβ0 THEN

8.    接收方发送含“已达到最大组件”反馈包,反馈包数量加1

9.  END IF

10. END WHILE

11. WHILE 解码的原始包数量 kβ<kβ0 DO

12.  在所有原始包中随机选择1个原始包,发送度1的编码包,记录编码包数量;接收方解码并更新已解码的原始包数量

13. END WHILE

14. 接收方向发送方发送含“原始包解码状态”和“最大组件已解码”的反馈包,反馈包数量加1

15. 完成阶段

16. 发送方根据最大组件解码成功的反馈包信息,更新未成功解码的原始包集合 Wi(k-A,SNs)

17. 根据原始包划分的等级集合,不等差错保护的避环ROFC-LF编码机制将集合 sj中未解码原始包集合表示为 Wij(αjk-Aj,SNs),已解码集合为 Aij(Aj,SNs)

18. FOR j=1:1:r DO

19.  IF 集合 sj没有解码成功 THEN

20.    根据度1和度2编码包各自所占概率,从集合 Wij(αjk-Aj,SNs)选择原始包递归编码,记录编码包数量,并解码;若收到含“所有原始包的解码状态”信息的反馈包,则更新集合 Wij(αjk-Aj,SNs), j随着反馈次数更新

21.    IF 连续两次的解码比例差 ΔβδTHEN

22.      接收方发送包含“原始包解码状态”的反馈包,反馈包数量加1

23.    END IF

24.   END IF

25. END FOR

26.END WHILE

4 编解码分析

不等差错保护的避环ROFC-LF编码机制在建立阶段避免了最大组件形成环,减少了无用编码包的数量,导致建立阶段的编码过程不是完全随机选择;该编码机制在完成阶段限制了反馈包数量,导致完成阶段未解码原始包集合更新不及时,在编码过程中可能出现重复的编码包;因此,基于这两个原因无法直接分析不等差错保护的避环ROFC-LF编码机制.当不等差错保护的避环ROFC-LF编码机制在建立阶段不进行避环设置,在完成阶段不限制反馈时,为不等差错保护的ROFC编码机制,标记为UEPROFC编码机制;UEPROFC编码机制在建立阶段是随机选择原始包进行编码,完成阶段不限制反馈,每个等级集合在完成阶段的编解码方式和ROFC编码机制完成阶段的编解码方式一致(详情见文献[26]),保证了完成阶段产生的编码包基本上都是有用的.因此,当信道丢包率 ϵ=0时,本文优先分析UEPROFC编码机制,然后根据UEPROFC和不等差错保护的避环ROFC-LF编码机制的区别来分析不等差错保护的避环ROFC-LF编码机制.
UEPROFC编码机制在建立阶段采用权重策略,给 r个等级集合 ( s1 s2 s3,…, sr),设置 r个权重占比 q1 q2 q3,…, qr,根据权重占比,不均匀地选择等级集合 si,然后在选中的集合中随机选择原始包编码;再通过在所有 k个原始包中随机选择原始包编码,最终解码图达到最大组件 kβ0.根据文献[2126]知,当ROFC编码机制建立阶段最大组件达到 kβ0时,解码图记为 g(k,c/k).根据文献[29]第10章随机图理论知,解码图中的节点代表着原始包, c表示每个原始包被平均选择的次数.根据文献[29]第10章随机图理论和[2126]有引理2,引理2给出了 c β0之间的关系.
引理2 最大连通组件占比 β0和每个原始包平均被选择的次数 c之间满足以下关系:
β0+e-cβ0=1
(2)
根据随机图理论和文献[22]知,当概率 qr+1趋近于0时,UEPROFC编码机制建立阶段能被当作 r个独立的建立阶段, r个等级集合互不影响.否则,次重要等级集合中的小组件将和重要等级集合形成的大组件相连,影响MID的恢复速度.划分 r个等级集合,只有在概率 qr+1范围内选择原始包时,才能形成最大组件.当最大组件达到 kβ0时,标记 r个等级集合中最大组件占比分别为 β01 β02 β03,…, β0r.每个等级集合中每个原始包被平均选择的次数记为 c1 c2 c3,…, cr.因此,根据引理2,UEPROFC达到最大组件 kβ0时,根据归一化可认为每个等级集合中的原始包也达到了每个等级集合中的最大组件,因此,每个等级集合的最大组件占比和原始包平均被选择的次数之间满足以下关系:
β01+e-c1β01=1β02+e-c2β02=1β03+e-c3β03=1β0r+e-crβ0r=1
(3)
其中,相对应等级集合中每个原始包被平均选择的次数跟相对应等级集合被选择的概率成正比,跟相对应等级集合中原始包的数量成反比;因此, c1 c2 c3,…, cr之间比值设置为
c1:c2:c3::cr=q1α1k:q2α2k:q3α3k::qrαrk
(4)
建立阶段,UEPROFC编码机制的 r个等级集合中原始包,通过概率 qr+1在所有原始包中随机选择原始包,最后达到最大组件 kβ0,因此,有
α1kβ01+α2kβ02+α3kβ03++αrkβ0r=kβ0
(5)
化简式(5)得:
α1β01+α2β02+α3β03++αrβ0r=β0
(6)
结合式(3)~(6),能得到引理3.
引理3 给定 q1 q2 q3,…, qr α1 α2 α3,…, αr,可以计算得出 c1 c2 c3,…, cr β01 β02 β03,…, β0r.
β01+e-c1β01=1β02+e-c2β02=1β03+e-c3β03=1β0r+e-crβ0r=1c1:c2:c3::cr=q1α1k:q2α2k:q3α3k::qrαrkα1β01+α2β02+α3β03++αrβ0r=β0
(7)
推理1 根据引理3,UEPROFC编码机制建立阶段需要的度2编码包数量 Nd=2bp
Nd=2bp=12α1kc1+12α2kc2+12α3kc3++12αrkcr
(8)
证明 根据随机图理论知,在等级集合 s1中有 α1k个原始包,一共被选择 α1kc1次,系数 1/2表示一个编码包由2个原始包编码得来,因此,等级集合 s1中一共发送 α1kc1/2个编码包;以此类推,建立阶段期望发送的度2的编码包数量为 Nd=2bp.证毕.
UEPROFC编码机制和ROFC编码机制建立阶段均是最大组件达到 kβ0,然后随机从所有原始包中选择原始包来解码最大组件,因此,建立阶段期望传输的度1的编码包数量为
Nd=1bp=1/β0
(9)
引理4 根据文献[2126]及随机图理论知,建立阶段结束,去除最大组件的解码图也是一部图,记为 G(t, t/d),其中 t=(1-β0)k d=(1-β0)c;图 G(t, t/d)期望的边数为 td/2.
推理2 完成阶段,UEPROFC编码机制有用的编码包分为建立阶段未解码的度2的编码包,完成阶段度1和度2的编码包.由于UEPROFC完成阶段传输的编码包都是对解码有用的,因此,完成阶段期望传输的编码包数量为
Nd=1|2cp=α1k(1-β01)[1-12c1(1-β01)]+α2k(1-β02)[1-12c2(1-β02)]+α3k(1-β03)[1-12c3(1-β03)]++αrk(1-β0r)[1-12cr(1-β0r)]
(10)
证明 建立阶段结束后,在等级集合 s1中去除最大组件 α1β01后,剩余的图记为 g1(t1,t1/d1),其中 t1=(1-β01)α1k d1=(1-β01)c1,根据引理4,建立阶段未解码的度2,编码包数量为 t1d1/2.以此类推,等级集合 s2中建立阶段未解码的度2的编码包数量为 t2d2/2.等级集合 s3中建立阶段未解码的度2的编码包数量为 t3d3/2.等级集合 sr中建立阶段未解码的度2的编码包数量为 trdr/2.根据文献[26]的定理知,在完成阶段平均恢复一个编码包需要一个有用的编码包.等级集合 s1中未恢复的原始包数量为 t1=(1-β01)α1k,建立阶段未解码的度2的编码包数量为 t1d1/2,UEPROFC有用的编码包分为建立阶段未解码的度2的编码包,完成阶段度1和度2的编码包.因此,等级集合 s1完成阶段需要的编码包数量为 t1-t1d1/2=α1k(1-β01)[1-c1(1-β01)/2].以此类推,等级集合 s2完成阶段需要的编码包数量为 t2-t2d2/2=α2k(1-β02)[1-c2(1-β02)/2].等级集合 s3完成阶段需要的编码包数量为 t3-t3d3/2=α3k(1-β03)[1-c3(1-β03)/2].等级集合 sr完成阶段需要的编码包数量为 tr-trdr/2=αrk(1-β0r)[1-cr(1-β0r)/2].综上,完成阶段需要的编码包数量是各个等级集合需要的编码包数量之和.证毕.
综上,完全恢复 k个原始包,UEPROFC编码机制期望传输的编码包数量为
EUEPROFC=Nd=2bp+Nd=1bp+Nd=1|2cp=12α1kc1+12α2kc2+12α3kc3++12αrkcr+1β0+α1k(1-β01)[1-12c1(1-β01)]+α2k(1-β02)[1-12c2(1-β02)]+α3k(1-β03)[1-12c3(1-β03)]++αrk(1-β0r)[1-12cr(1-β0r)]
(11)
根据等级集合划分原则,第一个等级集合中的原始包数据是最重要的,那么恢复最重要数据需要的编码包数量为
EUEPROFCMID1=12α1kc1+12α2kc2+12α3kc3++12αrkcr+1β0+α1k(1-β01)[1-12c1(1-β01)]
(12)
根据等级集合划分原则,恢复第 i 2ir)等级集合需要的编码包数量为
EUEPROFCi=12α1kc1+12α2kc2+12α3kc3++12αrkcr+1β0+α1k(1-β01)[1-12c1(1-β01)]++αik(1-β0i)[1-12ci(1-β0i)]
(13)
不等差错保护的避环ROFC-LF编码机制建立阶段避免了最大组件形成环,减少了无用编码包的数量,因此不等差错保护的避环ROFC-LF编码机制需要的编码包数量少于UEPROFC编码机制;由于不等差错保护的避环ROFC-LF编码机制在完成阶段限制了反馈包数量,导致未解码集合不能及时更新,可能产生重复的度1和度2的编码包.因此,不等差错保护的避环ROFC-LF编码机制期望的编码包数量与UEPROFC期望传输的编码包数量存在一定的大小关系.
建立阶段最大组件的大小为 kβ0,在最大组件形成过程中,最大组件的大小由0到 kβ0增大,随着最大组件的增大,形成环的概率变大,如图4所示.因此,不等差错保护的避环ROFC-LF编码机制需要的数据包数量将减少.完成阶段限制了反馈包数量,随着未解码的原始包数量由多变少,产生重复编码包的概率增大;根据文献[26],当反馈限制 δ<0.02时,ROFC-LF编码机制和ROFC编码机制需要的编码包数量基本相同;当反馈限制 δ0.02时,ROFC-LF编码机制比ROFC编码机制需要的编码包数量多.不等差错保护的避环ROFC-LF编码机制与UEPROFC编码机制需要的编码包数量之间的关系和ROFC-LF与ROFC需要的编码包之间的关系类似;反馈限制 δ的取值直接影响了不等差错保护的避环ROFC-LF编码机制与UEPROFC编码机制需要的编码包数量之间的关系.由于不等差错保护的避环ROFC-LF编码机制在建立阶段设置了避环策略,导致建立阶段需要的编码包数量小于UEPROFC编码机制.因此,两种编码机制需要的编码包数量的大小关系分界值将稍大于0.02.
概率 qr+1的值需要权衡,才能满足在发送的编码包数量相对较少的情况下,既能使得建立阶段达到最大组件又能解码较多的最重要数据.假设 r=2,在解码过程中,此时MID集合形成的最大组件为 kβ1,LID集合形成的最大组件为 kβ2,从所有原始包集合选择原始包的概率为 q3,发送的下一个编码能够在所有原始包中形成最大组件的概率为 PLCC=[(Ckβ11Ckβ21)/Ck2]q3.如果原始包数量 k趋近于无穷大, PLCC=2β1β2q3,其中, 0<β1<1 0<β2<1 0<β1β2<minβ1,β2.则发送的下一个编码能够在所有原始包中形成最大组件的概率 PLCC<2q3,则下一个编码包能够形成最大组件的概率与 q3直接相关.当发送的编码包数量 Nsendkβ0时,才有可能达到最大组件,从所有原始包集合中选择原始包编码的次数 Numkβ0q3,且 kβ0q31,因此, q31/kβ0.以此类推,概率 qr+11/kβ0.为了尽快恢复MID集合,应该尽量避免次重要等级集合中的小组件和重要等级集合形成的大组件相连.因此, 1/kβ0qr+1η,但 η具体取值需要权衡,本文通过仿真实验来权衡 η最优值,最终界定出 qr+1的最优取值范围.

5 仿真实验

通过仿真实验对本文提出的不等差错保护的避环ROFC-LF编码机制进行性能评估,为了验证该编码机制的性能,与文献[22]的OFC-UEP(On-line Fountain Codes with Unequal Error Protection)编码机制、文献[23]的OFC-URT(Online Fountain Codes With Unequal Recovery Time)编码机制、文献[24]的UEPOFC-SWS(UEP Online Fountain Codes with Sequential Window Strategy)编码机制及文献[26]的ROFC-LF编码机制做对比实验分析.由于对比文献之间仿真参数设置不同,本文分别画图将提出的编码机制与以上四篇文献进行对比实验分析,实验数据均是运行多次求平均数.图表中用“UEPCAROFC-LF”来表示不等差错保护的避环ROFC-LF编码机制,用“UEPROFC-LF”来表示不等差错保护的ROFC-LF编码机制.由于本文对比的具有UEP特性的OFC22~24均设置原始包数量为1 000,因此,本文仿真实验中设置原始包数量 k=1 000;根据文献[26]的ROFC-LF编码机制,设置本文提出的编码机制类型1编码包的占比为0.1.
为了使仿真实验环境更接近水声信道环境,本文结合青海湖湖试获得的优化的数据包长度进行仿真实验.湖试的试验场景见图6.图6中一共部署了4个水声网络节点,其中Sink部署在靠近岸边的水下,另3个节点部署在湖中.节点硬件由水声Modem、树莓派主板、蓄电池、电缆、WIFI模块组成.水声Modem部署在水下3~5 m的范围内,节点相距1 000 m左右.由于调制方式和传输距离不同,水声信道的误码率通常在10-7~10-3范围内.根据文献[30]和湖试试验知,UANs优化的数据包长度一般为200字节,据此计算的信道丢包率在1.6×10-4~0.798 3之间,该丢包率用在本节的仿真实验设置.
图6 湖试的试验场景

Full size|PPT slide

图7是反馈限制 δ对需要的编码包和反馈包数量的影响.不等差错保护的避环ROFC-LF编码机制将所有原始包划分为2个等级集合, α1=α2=0.5.根据文献[22]OFC-UEP编码机制的仿真参数,不等差错保护的避环ROFC-LF编码机制参数设置如下:将所有原始包划分为2个等级集合, α1=α2=0.5,MID和LID集合分别有500个原始包,按原始包序号顺序,前面500个原始包为MID,后面500个原始包为LID;分别从MID集合、LID集合和所有原始包集合中选择原始包编码,三个集合的权重标记为 q1 q2 q3,权重比例为 q1:q2:q3=0.582:0.388:0.03,最大组件占比 β0=0.55.从图7a)看出,当 δ<0.027 5时,不等差错保护的避环ROFC-LF编码需要的编码包数量少于UEPROFC;当 δ>0.027 5时,不等差错保护的避环ROFC-LF编码机制需要的编码包数量多于UEPROFC;因此,实验结果完全符合第4节的理论分析.从图7b)看出,不等差错保护的避环ROFC-LF编码机制需要的反馈包数量明显少于UEPROFC编码机制需要的反馈包数量.由于UANs采用半双工通信,过多的反馈包将增大水声信道冲突,大量冲突导致信道无法通信.因此,UEPROFC不适用于UANs,有反馈限制的不等差错保护的避环ROFC-LF编码机制是适用于UANs的.权衡编码包和反馈包数量,不等差错保护的避环ROFC-LF编码机制选择反馈限制 δ=0.02.
图7 δ对需要的编码包和反馈包数量的影响

Full size|PPT slide

根据第4节的理论分析知,概率 qr+1需要满足 1/kβ0qr+1η,但无法通过理论分析得出具体的取值范围,因此,借鉴文献[26]和文献[31],通过仿真实验来界定概率 qr+1的最优取值范围.仿真参数设置和图7相同,其中 β0=0.55,且将所有数据包划分成2个集合,则 q30.002.同时为了防止LID集合中的小组件和MID集合中最大组件相连, q3在[0.001,0.4]范围内取值进行仿真实验,且 q1 q2始终保持 q1/q2=1.5.最大组件解码成功时,解码的MID数量标记为 NMIDD,解码的LID数量标记为 NLIDD,解码最大组件需要的编码包数量记为 Ncon,解码所有原始包需要的编码包数量记为 Nall.
当概率 q3=0.001时,10次仿真结果见表2.从表2看出,10组仿真数据中有4组数据异常(表2中数字加粗列).可见下一个编码包能够形成最大组件的概率 PLCC<0.002时,无法保证MID和LID数据集合有效相连,和理论分析一致.由于一直在随机选择2个原始包进行编码,造成除最大组件外,其他组件也形成了很多环(环是对解码无用的编码包),因此,在形成最大组件的过程中,也形成了很多其他较大组件,造成完成阶段仅需几个编码包就能完成编解码.当 q3=0.005时,其他参数不变,仿真结果也存在一组异常数据( Ncon=1 298 Nall=1 342),因此,概率 q3=0.005也不符合条件.综上,概率 qr+1的值要大于0.005.
2 概率 q3=0.001时,仿真结果
Ncon 757 1 401 1 871 787 747 730 1 859 1 822 784 738
Nall 1 157 1 420 1 872 1 107 1 067 1 057 1 861 1 829 1 030 1 038
注: 表2中4组加粗数字是由于概率 q3=0.001太小,导致建立阶段发送大量编码包才能形成最大组件,因此属于异常数据.
表3是原始包数量为1 000时,概率 q3对编解码的影响,从表3看出,随着 q3的增大,解码的MID相对越来越少,LID先变少后边多(以0.07为界);解码所有原始包需要的编码包数量相差不大;但当 q3=0.008 q3=0.009时,发送的编码包数量较多;且达到最大组件需要的编码包数量相对也较多,造成MID解码速度慢.因此,概率 qr+1值在0.01到0.07的范围内时,编解码性能较好.通过仿真实验得出了原始包数量为1 000时,划分2个等级集合, α1=α2=0.5时,概率 qr+1最优的取值范围.当仅有原始包数量变化时,由于MID和LID划分比例不变,最大组件占比不变,不会影响MID的速度(表4验证了该理论推测,原始包数量为500).因此,在集合划分和最大组件占比不变的情况下,概率 qr+1在[0.01,0.07]范围内取值,本文提出的编码机制性能最优.
表3 原始包数量为1 000时,概率 q3对编解码的影响
q3 0.008 0.009 0.01 0.03 0.05 0.07 0.08 0.09 0.1 0.15 0.2 0.4
NMIDD 410 404 366 367 365 368 358 357 357 347 340 313
NLIDD 264 248 194 192 195 195 200 201 201 206 219 242
Ncon 801 777 730 710 711 716 703 708 708 698 700 692
Nall 1 070 1 063 1 054 1 048 1 056 1 050 1 046 1 049 1 044 1 050 1 051 1 043
表4 原始包数量为500时,概率 q3对编解码的影响
q3 0.008 0.009 0.01 0.02 0.03 0.05 0.07 0.08 0.1
NMIDD 210 204 207 191 188 188 182 179 173
NLIDD 149 135 129 114 110 104 100 103 107
Ncon 427 411 402 374 366 363 352 357 352
Nall 567 567 547 546 549 547 541 541 543
根据文献[26]和图7的仿真结果,不等差错保护的避环ROFC-LF编码机制反馈限制 δ=0.02,反馈限制根据划分的集合数量进行控制,ROFC-LF编码机制是等差保护,仅有一个原始包集合,设置反馈限制 δ=0.01.当所有原始包划分为10个等级集合时,反馈限制 δ=0.1.表5是不等差错保护的避环ROFC-LF编码机制和不等差错保护的ROFC-LF编码机制对比实验,参数设置和图7参数设置相同.
表5 划分2个等级集合时, 两种编码机制对比实验
编码机制 编码包数量 反馈包数量 恢复MID需要的编码包数量
UEPCAROFC-LF 1 048 13 832
UEPROFC-LF 1 114 13 894
表5看出,两种编码机制需要的反馈包数量相同,而不等差错保护的避环ROFC-LF编码机制需要的编码包数量比不等差错保护的ROFC-LF编码机制少66个编码包,再次验证了避环策略的有效性,符合3.1节的理论分析.ROFC-LF编码机制采用不等差错保护机制以后,建立阶段最大组件形成环的数量增加,完成阶段无用编码包数量增加,因此,需要的编码包数量较多.从表5看出,对于恢复相同数量的重要数据包而言,不等差错保护的避环ROFC-LF编码机制仅需要832个编码包,而不采用避环策略的不等差错保护的ROFC-LF编码机制,需要发送894个编码包.结合表1,解码所有原始包,不等差错保护的避环ROFC-LF编码机制需要1 048个编码包,而ROFC-LF编码机制需要1 062个编码包.可见,不等差错保护的避环ROFC-LF编码机制不仅能尽快恢复MID,且传输的总编码包数量较少;因此,本文提出的编码机制适合网络拓扑动态变化的UANs.
表6是不等差错保护的避环ROFC-LF编码机制和OFC-UEP编码机制进行对比实验分析.根据OFC-UEP编码机制设置本文提出编码机制的仿真参数,和图7的参数设置相同.设置两个编码机制完全恢复MID所需要的编码包数量标记为 NMID,完全恢复所有原始包需要的编码包数量标记为 Nall.由于不等差错保护的避环ROFC-LF编码机制无法直接理论分析出确定的编码包的数量,因此,表6给出了UEPROFC编码机制的具体理论分析结果.当反馈限制 δ=0.02时,图7与第4节理论分析均能说明,不等差错保护的避环ROFC-LF编码机制需要的编码包数量要少于UEPROFC编码机制需要的编码包数量,因此表6的仿真结果和理论分析相符.无论完全恢复MID还是完全恢复所有数据,不等差错保护的避环ROFC-LF编码机制比OFC-UEP编码机制需要的编码包数量平均少200个编码包左右.完全恢复所有原始包,不等差错保护的避环ROFC-LF编码机制仅需要1 048个编码包,而OFC-UEP编码机制需要1 226个编码包,减少了14.5%;不等差错保护的避环ROFC-LF编码机制传输832个编码包就能恢复出MID,而OFC-UEP编码机制需要1 042个编码包,减少了20.2%.因此,对于单跳内传输数据量受限的UANs而言,不等差错保护的避环ROFC-LF编码机制性能更好.
表6 不等差错保护的避环ROFC-LF和OFC-UEP对比实验
参数

OFC-UEP

分析

OFC-UEP

仿真

UEPROFC

分析

UEPCAROFC-LF仿真
β01 0.75 0.73 0.75 0.723
β02 0.35 0.37 0.35 0.377
c1 1.848 1.815 1.848 1.776
c2 1.231 1.227 1.231 1.255
NMID 1 097上界 1 042 868 832
Nall 1 256上界 1 226 1 063 1 048
图8是存在丢包率 ϵ时,发送的编码包数量与恢复的MID和LID之间关系.本文提出的编码机制根据文献[24]的UEPOFC-SWS编码机制设置仿真参数,设置 k=1 000,将1 000个原始包分成2个等级集合, α1=α2=0.5,即MID数量是500,LID数量也是500,MID集合、LID集合和所有原始包集合三者权重比例为 q1:q2:q3,UEPOFC-SWS编码机制建立阶段最大组件大小是MID的0.65,而本文提出的编码机制的最大组件是在所有原始包中形成,因此,本文提出的编码机制最大组件占比 β0=0.325.在图8中,图例中“UEPCAROFC-LF”表示权重比例为 q1:q2:q3=0.6:0.37:0.03的不等差错保护的避环ROFC-LF编码机制仿真结果(红色线),“UEPCAROFC-LF1”表示权重比例为 q1:q2:q3=0.75:0.22:0.03的不等差错保护的避环ROFC-LF编码机制仿真结果(黑色线).图例“UEPCAROFC-LF-0”最后的“0”表示信道丢包率为0;同理,“UEPCAROFC-LF-0.1”最后的“0.1”表示信道丢包率为0.1;“UEPCAROFC-LF-0.2”最后的“0.2”表示信道丢包率为0.2;其他编码机制表示方法相同.
图8 发送的编码包数量对恢复MID和LID的影响

Full size|PPT slide

UEPOFC-SWS编码机制在建立阶段采用扩展窗策略实现不等差错保护,两个窗口的选择概率分别为0.6和0.4,也就是MID所在窗口选择的概率是0.6.因此,第一组权重比例设置为 q1:q2:q3=0.6:0.37:0.03.从图8a)看出,当权重比例为 q1:q2:q3=0.6:0.37:0.03时,相比UEPOFC-SWS编码机制,本文提出的编码机制在解码初期,MID恢复率低;但随着编码包数量的增加,不等差错保护的避环ROFC-LF编码机制MID恢复率明显变高,且信道丢包率越大,越明显;完全解码MID,无论是否存在丢包,本文提出的编码机制需要的编码包数量明显少于UEPOFC-SWS编码机制.由于UEPOFC-SWS编码机制在建立阶段除了以0.6的概率在MID中选择原始包编码外,还以0.4的概率在所有原始包(所有原始包是MID和LID的总和)中选择原始包编码;而本文提出的编码机制仅以0.6的概率从MID中选择原始包编码;这是导致本文提出的解码机制在解码初期MID恢复率低的原因.因此,本文提高MID权重占比,当权重比例为 q1:q2:q3=0.75:0.22:0.03(黑色线)时,明显看出,无论是否存在信道丢包,本文提出的编码机制MID恢复率高于UEPOFC-SWS机制.
图8b)看出,无论是否存在信道丢包,解码前期,不等差错保护的避环ROFC-LF编码机制比UEPOFC-SWS机制在恢复LID方面慢;然而,随着编码包数量的增加,不等差错保护的避环ROFC-LF编码机制LID恢复速度明显比UEPOFC-SWS机制快;且完全恢复LID需要的编码包数量约减少17%.两种不同权重比例对比(红色线和黑色线),增加MID的权重,不仅能快速的恢复MID,且基本不影响LID的恢复速度.LID完全恢复就表示所有原始包已完成编解码.可见,增加MID的权重,不仅能快速的恢复MID,且不影响所有原始包的恢复速度.不等差错保护的避环ROFC-LF编码机制在恢复MID和LID数据两方面均占一定优势,且需要的总的编码包数量较少,适合能源受限和误码率高的UANs.
表7是不等差错保护的避环ROFC-LF编码机制和UEPOFC-SWS做对比实验分析,同样根据文献[24]的UEPOFC-SWS编码机制设置仿真参数,设置 k=1 000,将1 000个原始包分成2个等级, α1=α2=0.5 q1:q2:q3=0.582:0.388:0.03;和图8的原理一样,不等差错保护的避环ROFC-LF编码机制设置最大组件占比 β0=0.325.
表7 MID占比对编码包数量的影响
MID占比 0.1 0.2 0.3 0.4 0.5
NUEPCAROFC-LF 1 095 1 058 1 054 1 054 1 048
NUEPOFC-SWS 1 195 1 204 1 212 1 219 1 222
表7是MID占比变化时,不等差错保护的避环ROFC-LF和UEPOFC-SWS两种编码机制的对比实验.不等差错保护的避环ROFC-LF和UEPOFC-SWS两种编码机制需要的编码包数量分别标记为 NUEPCAROFC-LF NUEPOFC-SWS.从表7看出,无论MID占比多少,不等差错保护的避环ROFC-LF编码机制比UEPOFC-SWS编码机制平均少发送150个左右编码包,最少降低8.4%,最多降低14.24%.对于资源受限的UANs网络,不等差错保护的避环ROFC-LF编码机制更适合用来传输重要性不同的多媒体数据.
表8图9图10是不等差错保护的避环ROFC-LF编码机制和OFC-URT进行对比实验.为了和文献[23]的OFC-URT编码机制进行对比实验分析,本文提出的编码机制的仿真参数是根据OFC-URT编码机制的仿真参数进行设置的, k=1 000,最大组件占比 β0=0.65,不等差错保护的避环ROFC-LF编码机制将1 000个原始包分成10个等级集合,每个等级集合有100个原始包, α1=α2=α3==α9=α10=0.1,10个等级集合以及从所有原始包中随机选择原始包进行编码的权重分别标记为 q1 q2 q3,…, q10 qall,比值为0.15∶0.15∶0.1∶0.1∶0.1∶0.1∶0.05∶0.05∶0.05∶0.05∶0.1,总和为1.
表8 划分10个等级集合时,两种编码机制对比实验
编码机制 编码包数量 反馈包数量 恢复MID需要的编码包数量
UEPCAROFC-LF 1 132 25 786
UEPROFC-LF 1 297 25 952
图9 发送的编码包数量与恢复的原始包数量之间关系

Full size|PPT slide

图10 等级集合恢复速度与发送的编码包数量之间关系

Full size|PPT slide

表8看出,将原始包划分10个等级集合后,两种编码机制需要的反馈包数量相差不大,而需要的编码包数量相差165个,和表5的结果相似,说明设置避环策略是非常必要的.具有不等差错保护功能的编码机制,建立阶段最大组件形成的环的数量增加,完成阶段无用编码包数量增加,尤其划分10个等级集合后,具有不等差错保护的编码机制无用编码包数量进一步增多,因此,不等差错保护的ROFC-LF编码机制需要的编码包数量达到了1 297个.建立阶段最大组件形成过程中采用避环策略后,不等差错保护的避环ROFC-LF编码机制需要的编码包数量明显减少,仅需要1 132个编码包.从表8看出,恢复最重要数据,不等差错保护的避环ROFC-LF编码机制仅需要786个编码包.对于资源受限的UANs而言,需要更快恢复MID且总的编码包数量少的编码机制,因此,不等差错保护的避环ROFC-LF编码机制能更好的实现不等差错保护功能.
图9是发送的编码包数量与恢复的原始包数量之间关系.OFC-URT1是OFC-URT编码机制结构1的仿真实验,OFC-URT2是OFC-URT编码机制结构2的仿真实验.当发送的编码包数量少于800时,不等差错保护的避环ROFC-LF编码机制比OFC-URT编码机制原始包恢复得慢,这是由于OFC-URT编码机制开始先发送了部分度1的编码包;随着编码包数量的增加,不等差错保护的避环ROFC-LF编码机制比OFC-URT编码机制原始包恢复速度明显快,且需要的总编码包数量比OFC-URT编码机制少.不等差错保护的避环ROFC-LF与ROFC-LF编码机制的原始包恢复情况相差不大.图10中,黄色线表示ROFC-LF编码机制,红色线表示不等差错保护的避环ROFC-LF编码机制,结合图10的仿真结果,ROFC-LF编码机制无论解码MID还是LID,均需完成所有原始包编解码,需要约1 080个编码包.而不等差错保护的避环ROFC-LF编码机制发送约800个编码包就能解码MID集合1,且随着编码包数量增加,其他数据集合也能快速解码;完全解码所有原始包,不等差错保护的避环ROFC-LF编码机制发送的编码包数量仅比ROFC-LF编码机制多4.52%.因此,结合图10,不等差错保护的避环ROFC-LF编码机制在不影响总体原始包恢复率的同时,能优先恢复MID,适合用于UANs中传输和编码具有不同等重要性的多媒体数据.
图10是不同等级集合原始包恢复速度与发送的编码包数量之间关系,明显看出OFC-URT1机制恢复MID需要的编码包数量最少,但是恢复LID需要的编码包数量最多,不适合资源受限的UANs.不等差错保护的避环ROFC-LF编码机制在恢复MID和LID两方面性能均较好,且对于恢复所有原始包而言,需要的编码包数量较少,权衡两种数据的恢复情况及总体需要的编码包数量,不等差错保护的避环ROFC-LF编码机制更适合UANs.

6 总结

由于UANs具有带宽窄、时延长、能量受限、拓扑结构动态变化等特点,这些特点造成UANs需要尽快恢复重要的多媒体数据.根据这一需求,本文进一步分析了ROFC-LF编码机制建立阶段环的问题,通过采取避环策略,有效的减少了无用编码包数量;通过采用权重和数据优先级两项策略来实现UEP特性,使得重要的多媒体数据优先恢复;因此,本文提出了具有UEP特性的避环ROFC-LF编码机制,并基于随机图理论对不等差错保护的避环ROFC-LF编码机制需要的编码包数量和原始包数量之间的关系进行理论分析,理论分析和仿真实验结果一致.实验结果表明:相比ROFC-LF编码机制,避环ROFC-LF编码机制需要的编码包数量平均减少2.4%.如果原始数据划分等级集合数量少时,不等差错保护的避环ROFC-LF编码机制需要的编码包数量和反馈包数量和ROFC-LF编码机制相差不大;如果原始数据划分等级集合数量较多时,不等差错保护的避环ROFC-LF编码机制需要的编码包数量和反馈包数量比ROFC-LF编码机制要多;但对于恢复MID而言,不等差错保护的避环ROFC-LF编码机制比ROFC-LF编码机制发送的编码包数量至少减少21.7%.不等差错保护的避环ROFC-LF编码机制比OFC-UEP总的需要的编码包数量减少14.5%,恢复MID需要的编码包数量减少20.2%.不等差错保护的避环ROFC-LF编码机制比OFC-URT编码机制总的需要的编码包数量少,且能快速的恢复MID.相比UEPOFC-SWS编码机制,不等差错保护的避环ROFC-LF编码机制总体需要的编码包数量约少200个编码包,至少降低8.4%,且增加MID的权重,不仅能快速的恢复MID,且不影响所有原始包的恢复速度.通过理论分析和仿真实验均证明该机制在恢复UANs MID、整体编码包数量和反馈包数量三方面具有明显优势,适合长时延和网络拓扑动态变化的UANs具有不等重要性的多媒体数据传输.

References

1
ZHANG Y, ZHANG Z M, CHEN L, et al. Reinforcement learning-based opportunistic routing protocol for underwater acoustic sensor networks[J]. IEEE Transactions on Vehicular Technology, 2021, 70(3): 2756-2770.
2
JIANG S M. On reliable data transfer in underwater acoustic networks: A survey from networking perspective[J]. IEEE Communications Surveys & Tutorials, 2018, 20(2): 1036-1055.
3
XIE P, ZHOU Z, PENG Z, et al. SDRT: A reliable data transport protocol for underwater sensor networks[J]. Ad Hoc Networks, 2010, 8(7): 708-722.
4
SCHWARZ H, MARPE D, WIEGAND T. Overview of the scalable video coding extension of the H.264/AVC standard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2007, 17(9): 1103-1120.
5
ZHAO D F, WEN J, SI J X. A UEP LT codes design with feedback for underwater communication[J]. Journal of Sensors, 2016, 2016: 2390734.
6
HUSSAIN I, XIAO M, RASMUSSEN L K. Design of LT codes with equal and unequal erasure protection over binary erasure channels[J]. IEEE Communications Letters, 2013, 17(2): 261-264.
7
蔡雅琼. 基于感知质量驱动的水下图像压缩与非对等保护研究[D]. 厦门: 厦门大学, 2018.
CAI Y Q. Underwater Image Compression and Unequal Error Protection Based on Image Perceived Quality[D]. Xiamen: Xiamen University, 2018. (in Chinese)
8
ESMAIEL H, QASEM Z A H, SUN H X, et al. Underwater image transmission using spatial modulation unequal error protection for Internet of underwater things[J]. Sensors, 2019, 19(23): 5271.
9
RAHMATI M, QI Z R, POMPILI D. Underwater adaptive video transmissions using MIMO-based software-defined acoustic modems[J]. IEEE Transactions on Multimedia, 2023, 25: 473-485.
10
ESMAIEL H, JIANG D C. SPIHT coded image transmission over underwater acoustic channel with unequal error protection using HQAM[C]//2013 IEEE Third International Conference on Information Science and Technology (ICIST). Piscataway: IEEE, 2013: 1365-1371.
11
MACKAY D J C. Fountain codes[J]. IEE Proceedings - Communications, 2005, 152(6): 1062.
12
宋鑫, 倪淑燕, 张喆, 等. 面向不等差错保护的低误码平台LT编码算法[J]. 通信学报, 2022, 43(6): 85-97.
SONG X, NI S Y, ZHANG Z, et al. Low error floor LT coding algorithm for unequal error protection[J]. Journal on Communications, 2022, 43(6): 85-97. (in Chinese)
13
田远. 分布式不等差错保护喷泉码的研究与应用[D]. 广州: 华南理工大学, 2017.
TIAN Y. Research and Application of Distributed Unequal Error Protection Fountain Codes[D]. Guangzhou: South China University of Technology, 2017. (in Chinese)
14
邓克岩. 基于喷泉码的不等差错保护传输方案研究[D]. 兰州: 兰州大学, 2017.
DENG K Y. Unequal Error Protection Transmission Scheme Based on Fountain Codes[D]. Lanzhou: Lanzhou University, 2017. (in Chinese)
15
李亚芳. LT码及其在不等差错保护方案中的研究[D]. 郑州: 郑州大学, 2017.
LI Y F. Research of LT Code and Its Unequal Error Protection Schemes[D]. Zhengzhou: Zhengzhou University, 2017. (in Chinese)
16
SEJDINOVIC D, VUKOBRATOVIC D, DOUFEXI A, et al. Expanding window fountain codes for unequal error protection[J]. IEEE Transactions on Communications, 2009, 57(9): 2510-2516.
17
黄太奇, 易本顺, 姚渭箐, 等. 基于规则变量节点度和扩展窗喷泉码的不等差错保护算法[J]. 电子与信息学报, 2015, 37(8): 1931-1936.
HUANG T Q, YI B S, YAO W Q, et al. Novel scheme of unequal error protection based on regularized variable-node and expanding window fountain codes[J]. Journal of Electronics & Information Technology, 2015, 37(8): 1931-1936. (in Chinese)
18
石东新, 杨占昕. 不等差错保护的系统Raptor码[J]. 华中科技大学学报(自然科学版), 2016, 44(5): 47-53.
SHI D X, YANG Z X. Systematic raptor codes for unequal error protection[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2016, 44(5): 47-53. (in Chinese)
19
王慧. 自适应不等差错保护喷泉编码策略研究[D]. 西安: 西安电子科技大学, 2021.
WANG H. Adaptive Unequal Error Protection Fountain Codes[D]. Xi’an: Xidian University, 2021. (in Chinese)
20
邓在辉, 同小军, 甘良才. 改进的块复制不等差错保护喷泉码[J]. 数据采集与处理, 2015, 30(3): 591-598.
DENG Z H, TONG X J, GAN L C. Improvement of unequal error protected fountain codes based on block duplication[J]. Journal of Data Acquisition and Processing, 2015, 30(3): 591-598. (in Chinese)
21
CASSUTO Y, SHOKROLLAHI A. Online fountain codes with low overhead[J]. IEEE Transactions on Information Theory, 2015, 61(6): 3137-3149.
22
HUANG J X, FEI Z S, CAO C Z, et al. On-line fountain codes with unequal error protection[J]. IEEE Communications Letters, 2017, 21(6): 1225-1228.
23
CAI P X, ZHANG Y, PAN C Y, et al. Online fountain codes with unequal recovery time[J]. IEEE Communications Letters, 2019, 23(7): 1136-1140.
24
DUAN Y F, DING L H, YANG F, et al. UEP online fountain codes with sequential window strategy[C]//2020 IEEE/CIC International Conference on Communications in China (ICCC). Piscataway: IEEE, 2020: 899-904.
25
SHI P C, WANG Z Y, LI D Z, et al. Efficient unequal error protection for online fountain codes[J]. Journal of Systems Engineering and Electronics, 2024, 35(2): 286-293.
26
LIU X X, DU X J, ZHANG J L, et al. ROFC-LF: Recursive online fountain code with limited feedback for underwater acoustic networks[J]. IEEE Transactions on Communications, 2022, 70(7): 4327-4342.
27
柳秀秀, 杜秀娟, 韩多亮. 水声网络按序递归与限制反馈的在线喷泉码算法与分析[J]. 电子学报, 2023, 51(7): 1734-1740.
LIU X X, DU X J, HAN D L. Algorithm and analysis of sequential recursive online fountain code with limited feedback in underwater acoustic networks[J]. Acta Electronica Sinica, 2023, 51(7): 1734-1740. (in Chinese)
28
ERDÖS P, RÉNYI A. On the evolution of random graphs[J]. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, 5(43): 17-61.
29
ALON N, SPENCER J H. The Probabilistic Method[M]. Hoboken: Wiley, 2004.
30
DU X J, LIU X X, SU Y S. Underwater acoustic networks testbed for ecological monitoring of Qinghai Lake[C]//OCEANS 2016 - Shanghai. Piscataway: IEEE, 2016: 1-4.
31
HUANG J X, FEI Z S, CAO C Z, et al. Performance analysis and improvement of online fountain codes[J]. IEEE Transactions on Communications, 2018, 66(12): 5916-5926.

Funding

Qinghai Provincial Natural Science Foundation(2024-ZJ-929)
National Natural Science Foundation of China(61962052)
PDF(1627 KB)

1213

Accesses

0

Citation

Detail

Sections
Recommended

/