基于数据冗余的BDS长报文传输机制改进算法*

唐懿芳,钟达夫

(1.广东科学技术职业学院，广东珠海　519090;

2.企业信息化与物联网测控技术四川省高校重点实验室,四川自贡　643099)



基于数据冗余的BDS长报文传输机制改进算法*

唐懿芳1,2,钟达夫1

(1.广东科学技术职业学院，广东珠海519090;

2.企业信息化与物联网测控技术四川省高校重点实验室,四川自贡643099)

摘要:北斗卫星导航系统(Beidou Satellite Navigation System,BDS)只能传输字节受限的短报文,对于长报文需要通过分包和多次重传改善报文传输的成功率,这样会造成系统平台数据发送延误和网络拥塞。提出一种基于数据冗余的数据分包传输机制,该传输机制以数据包为处理对象,采用异或运算得到冗余包,编码简单,编码解码速度快。通过Matlab仿真,证明基于冗余编码机制比无冗余编码单次发送机制的数据接收成功率高15%以上,两次发送对多包的数据接收成功率有较大提高。

关键词:北斗卫星导航系统;数据传输;短报文;数据冗余;异或算法

修回日期： 2015-10-29

钟达夫(1972-),男，副教授。

自2003年12月“北斗”系统(BDS)建成以来,逐渐应用于中国及周边地区的地质灾害监测、渔业、抢险救灾、交通运输、森林防火等领域,并取得了一定的成果[1-3]。

BDS由用户终端、地面段和空间段三部分组成[4]，如图1所示。BDS短报文通信的工作流程为:用户终端将包含接收方地址和通信内容的数据传递到BDS用户终端,用户终端对数据按照预定的协议及加密机制进行处理后,通过空间段的北斗卫星将数据转发到地面中心站;地面中心站将数据转发给地面网管中心,地面网管中心接收到通信申请信号后,经解密和再加密后发送至地面中心站;地面中心站将其加入持续广播的出站电文中,经卫星广播或地面网络将数据传输给用户;用户机接收出站信号,解调解密出站电文,完成一次通信[4]。

图1　BDS通信系统示意图

BDS具有用户与用户、用户与地面控制中心之间的双向报文通信能力。这种简短双向报文通信服务有效地满足了通信信息量较少、实时性要求高的场合,但从具体应用方面来看,北斗短报文通信在远距离长报文数据传输中存在诸多限制:1)短报文信道带宽小,民用终端机一般一次传送120Byte,北斗卫星导航系统的短报文有较严格的限制,不能直接用于长报文信息的传输;2)通信频度有限,北斗系统每发送完一条报文后需等待一段时间才能进行下一条报文的发送,一般来说,民用北斗的通信频度是60s左右;3)北斗卫星通信链路是不可靠的通信连接,在连续传输多条报文后,传输成功率会极大降低,另外,民用北斗通信没有使用回执,即发送方无法知道接收方是否正确收到了数据。

BDS除具备常用的定位、授时和导航功能外,还拥有短报文通信功能,信号覆盖范围广、几乎不受自然灾害影响等优点[5-6]。但BDS只能传输字节受限的短报文,对于长报文需要通过分包和多次重传,以改善报文传输的成功率,这样又会造成系统平台数据发送延误和网络拥塞的问题。本文将研究一种基于数据冗余的数据分包传输机制应用于BDS通信的长报文传输,可以提高BDS通信的长报文传输的可靠性。

1基于BDS的远距离长报文传输机制设计

1.1BDS通信协议

用户在利用BDS用户终端完成数据的远距离传输时,用户终端机所采用的通信模式为应答式,即外设需要向用户终端机串口发送指令,执行完外设的请求后,将结果再返回有服务请求的外设。

BDS通信协议的基本格式如图2所示。

图2　BDS通信协议示意图

1.2数据分组传输机制分析

普通的北斗终端间短报文通信是点对点的通信方式,每个北斗终端都配有一张IC卡,每个IC卡都有唯一的ID号码进行标识。两个普通的北斗终端间发送信息时,首先要输入信息接收的目的ID,北斗系统才能将短信息发送至目的终端。

北斗系统短报文传输每次的短报文通信一般只能传输120Byte[7],待传数据长度一般比北斗短报文规定的通信长度长,因此,待传数据需要分成几个数据包进行传输。远端的监控中心,在接收到所有数据包的情况下,才能解析出完整的数据。如果在传输过程中,丢失任意一个数据包,监控中心服务器都不能对数据进行还原,从而造成数据传输失败。

传输成功率是北斗短报文通信的重要性能参数。

假设BDS短报文传输成功率为η,数据分包的数目为n,则单次发送数据传输的成功率:

P1=ηn

(1)

在北斗通信系统中,单次报文的传输成功率为97%[8], 短报文正确接收概率与北斗通信系统的传输成功率成正比的,而与信息拆包数目成反比。在北斗短文分10次拆包进行传输时,且通信系统传输成功率为70%时,短报文正确接收概率不足75%,而这样的接收成功率是远远满足不了系统要求的。

提高信息的正确接收率,最简单的方法就是将一条信息进行多次发送。信息接收端利用重传的数据包,将短报文进行整合,从而恢复正确信息。

相比单次发送,数据重发明显改善了短报文正确接收概率。但是对于比较重要的信号,在数据量较大的时候,数据正确接收概率还是不能够满足系统需求。采用单纯的数据重发机制,可以提高数据的正确接收概率。但是当重复发送次数过多,信息接收成功率提高的同时,所付出的代价是成倍地消耗北斗系统宝贵的带宽资源,甚至可能造成系统平台数据发送极大地延误和网络拥塞。因而仅靠简单的重复发送是不行的,必须找到一种更加合理有效的方式来提高数据的接收成功率。

1.3单包丢失的前向纠错编码算法

1) 前向纠错技术

目前,通信系统中解决数据丢包的问题,应用比较广泛的两种方法是自动重传请求技术和前向纠错技术[7, 9]。自动重传请求技术是指通过信息回执,将数据的接收情况反馈给发送方,接收方根据回执内容决定是否重发或补发数据包;前向纠错技术是一种通过增加冗余数据来实现数据的恢复技术,虽然这类方法在传输时需要额外的宽带资源,但是其具有时延低和恢复丢包效率高的优点[10-11]。本文中采用前向纠错技术实现数据包的恢复。

前向纠错技术有物理层和应用层两种。物理层前向纠错技术在数据链路层广泛应用,通常用硬件实现长度相对较短的比特级的检错和纠错[12-13]。由于本文中比特级数据流的传输是由北斗终端来控制的,用户无法设计,所以采用应用层级的前向纠错技术。

前向纠错码(FEC)的码字是具有一定纠错能力的码型,它在接收端解码后,不仅可以发现错误,而且能够判断错误码元所在的位置,并自动纠错[14]。这种纠错码信息不需要储存,不需要反馈,实时性好,所以在单向传输系统都采用这种信道编码方式。

两个普通的北斗终端在进行相互通信时,在发送方编码,在接收方解码,传统的前向纠错码不适用于北斗通信,是因为其复杂的算法带来了较高的额外的能量开销和时间开销,对时效性要求高的传输不能接受太复杂的算法,必须寻求一种较少计算和存储开销的算法。

本文以数据包为处理对象,将报文M拆成编号为1到k的短报文,数据发送时增加一个奇偶校验包C,即冗余包的个数为一个。其冗余包产生原理如图3所示。

图3　奇偶校验数据冗余原理图

在源数据端发送K+1个数据包的情况下,只要接收端能收到K个数据包就可以完成源数据的恢复,则基于数据冗余技术的数据传输的成功概率公式为

(2)

2)源数据的具体编码算法

源数据端把报文M拆分成k个包,每个包为定长l+1(≤120Byte),源数据编码模型如下:

图4　报文拆分的编码模型和冗余编码模型

设di(1≤i≤k)为拆分的第i个数据包,一般的终端机的短报文最多传送120Byte,则每个di的定长为L+1个字节(<120Byte),不能等于120Byte,要预留一些bit位给必要的补充信息。冗余包编码规则为

Cj=d1j⨁d2j⨁…dkj

(3)

式中，符号“⨁”表示异或操作,所得到的奇偶校验冗余包将随着数据一起发送,一共有k+1个数据包,只要正确接收任意k个数据包即可正确解码。接收端解码的公式如下:

……

(4)

(5)

源节点把数据拆成k个包,每个包为定长的L+1比特,编码如图5所示。

图5　报文编码示意图

根据短报文的编号,接收端在只有一个数据包丢失的情况下,完全可以经过异或运算进行恢复,如果只有基本校验包C丢失,则表明原始数据包已经成功传送至接收终端,不需纠错,如果某个数据短报文丢失,则接收端可根据基本校验包C进行恢复,但如何知道传送的短报文哪些是数据包,哪些是冗余的校验包呢?而且如前所述,相比单次发送,数据重发明显改善了短报文正确接收概率,所以在保证带宽和时延的前提下,本文采用次数较少的重复传输。

为使接收端能够正确有序地还原拆包信息,必须在拆包的短报文中添加一些必要的控制信息[7],如流水号,本条信息的传输总次数,是第几次传输,本条信息分几包传输,本包是第几包,是否是数据包还是冗余包,添加的数据如图6所示。

图6　封装了包头的短报文内容

其中1位置标识消息的流水号,同一个消息被拆成多个包,它的流水号应该是相同的,2位置标识传输的次数,3位置标识本次为第几次传输,4位置标识消息分为多少包进行传输,5位置标识本消息是第几包,6标识是普通的数据包还是冗余包。至于每个位置怎样表示可以根据具体情况来编码,一起传输后,根据包头标识数据,真正有用的数据是去掉包头的。

1.4多包丢失的前向纠错编码算法

在多包丢失的情况下,考虑最大化源数据包之间的相关性增强前向纠错编码算法的纠错能力。算法针对k个数据包,增加k+1个冗余包进行纠错。虽然对增加k+1个冗余包来说,编码效率如下所示:

(6)

但是计算和存储的花费还是远小于需要复杂高斯消去法的传统的FEC前向纠错算法。

多包丢失编码算法如图7所示。

图7　多包丢失冗余编码模型

根据式(3)可得到基本校验包C0,C1到Ck的编码如式(7)所示。

C1=d1⨁d2⨁d3⨁…⨁dk-1

C2=d2⨁d3⨁d4⨁…⨁dk

⋮

Ck=dk⨁d1⨁d2⨁…⨁dk-2

(7)

校验数据C0,C1,C2,…,Ck将随着源数据包d1,d2,…,dk一起发送出去。

可以证明本文提到的基于冗余数据包的算法,在发送2k+1个数据包的情况下,丢失最多k个数据包,仍然可以恢复源数据。简略证明如下。

证明:根据校验数据包C0,C1,C2,…,Ck能够恢复原始数据为:

d1=C0⨁C2

d2=C0⨁C3

⋮

dk=C0⨁C1

(8)

对每两个校验包Ci,Cj(1≤i,j≤k,i≠j)进行异或运算,可得到两个原始数据的异或值:

Ci⨁Cj=di⨁dk(i=1,i

Ci⨁Cj=di-1⨁dj-1(i≥2,i

(9)

因为异或运算满足交换律,即

di⨁dj=dj⨁di(1≤i,j≤k)

(10)

任何一个源数据包di与其它k-2个源数据包异或操作,都可得到校验值Ci,再根据式(7),(8),(9)以及成功传送的数据,可恢复出丢失的数据包,所以当丢失的数据包不大于k时可以解码成功。证毕。

例如图8所示,4个数据包,得到5个校验码,一起发送出去。最多丢失4个数据包,可以恢复源数据。

图8　源数据与校验码编码实例示意图

以图8为例,在极端情况下,假设所有数据包丢失,即d1,d2,d3,d4数据全丢失,我们仍然可以用公式(8)恢复所有的数据,如果基本校验包C0丢失,只要还有5个数据包,仍然可以通过异或关系恢复它们的数据。仍以图(8)为例,假设丢失d1,d2,d3,C0,可用公式(9)的异或关系恢复。

2基于数据冗余技术的北斗短报文功能收发数据性能分析

对于基于数据冗余技术的仿真与上述的基于数据重发技术的数据传输仿真条件与环境完全相同。将没有冗余技术的单次数据重发仿真效果与具有冗余技术的数据传输仿真效果进行对比,仿真图如图9所示。

图9　基于冗余编码机制与无冗余编码单次发送机制的数据收发成功率比较图

从仿真结果可以看出,在与数据分包数目与短报文传输成功率相同的条件下,基于数据冗余技术的数据传输成功率明显高于没有冗余编码的数据传输。对于宽带的占用而言,只是在每次进行数据传输时,多增加一个数据包的传输。将基于数据冗余技术的单次数据收发成功率与无冗余编码的两次数据收发成功率作对比其仿真图如图10所示。分组数据两次重发机制的概率公式为

P3=1-(1-ηn)2

(11)

图10　基于冗余编码机制与无冗余编码两次发送机制的数据收发成功率比较图

由以上仿真结果可以看出,基于冗余编码机制比无冗余编码单次发送机制的数据接收成功率高15%以上,两次发送对多包的数据接收成功率有较大提高。因此,该机制不但提高了数据的传输成功率,而且大大节省了北斗通信有限的宽带资源。所以采用数据冗余技术作为北斗通信链路的数据通信机制具有明显优势。

3结束语

本文针对BDS短报文数据容量小、通信频度有限制,不适合传输大数据长报文的数据问题,提出了通过使用基于冗余技术的数据分组机制解决BDS的大数据传输瓶颈,接收成功率提高15%以上。下一步应根据本文提出的基于数据冗余的分组数据传输机制产生的时延问题展开研究。

参考文献:

[1]唐金元, 于潞, 王思臣. 北斗卫星导航定位系统应用现状分析[J]. 全球定位系统, 2008, 33(2): 26-30.

[2]范一大, 张宝军. 中国北斗卫星导航系统减灾应用概述与展望[J]. 中国航天, 2010(2):7-9.

[3]王海涛, 孙桂新. 基于北斗定位技术的试验靶船自动监测系统[J]. 指挥控制与仿真, 2006, 28(5):104-106，110.

[4]刘传润. 北斗卫星导航定位系统的功能原理与前景展望[J]. China Water Transport, 2008, 8(1): 165-166.

[5]朱永辉, 白征东, 过静珺,等. 基于北斗一号地质灾害自动监测系统[J]. 测绘通报, 2010, 56(2):5-7.

[6]欧健. 北斗导航系统在环境自动监测及应急监测中的应用[J]. 环境监测管理与技术, 2011,23(4):64-67.

[7]薛瑞. 基于北斗的预警信息传输关键技术研究[D]. 天津： 河北工业大学, 2011.

[8]谷军霞,王春芳,宋之光. 北斗短报文通信信道性能测试与统计分析[J]. 气象科技,2015, 43(3):458-463.

[9]熊志强. 无线传感器网络数据传输容错技术研究[D]. 武汉：华中科技大学, 2007.

[10]彭伟, 徐俊臣, 杜玉杰,等. 基于北斗系统的海洋环境监测数据传输系统设计[J]. 海洋技术, 2009,28 (3):13-15.

[11]Huang C W, Somsak S. An embedded packet train and adaptive FEC scheme for VoIP over wired/wireless IP networks[C]∥ICASSP 2006 Processings, Washington, 2006: 429-432.

[12]Moreira J C, Farrell P G.Essentials of error-control coding[M]. Chichester: John Wiley and Sons, 2006.

[13]Al-Shaikhi A, Ilow J. Vandermonde matrix packet-level FEC for joint recovery from errors and packet loss PIMRC[C]∥IEEE Personal, Indoor and Mobile Radio Communications(PIM-RC 2008), Cannes, 2008.

[14]路利宁, 余玉材, 刘纯青. 一种单向卫星网络中冗余递增的数据分发机制[J]. 科学技术与工程,2010,19(10):4668-4673.

Improved Algorithm about Long Message Transmission Mechanism of Beidou Navigation Satellite System Based on Data Redundancy

TANG Yi-fang1,2,ZHONG Da-fu1

(1. Guangdong Institute of Science and Technology, Zhuhai 519090;

2.Key Lab of Enterprise Informationization and Internet of Things of Sichuan Province, Zigong 643000, China)

Abstract:Beidou Navigation Satellite System (BDS) only supports byte-limited short message transmitting. For long message transmitting, BDS adopts a sub-packeting and multiple retransmission method to improve the success rate of packet transmission, which may cause data delay and network congestion. In this paper, a data redundancy based packet transmission mechanism is proposed. In this mechanism, the date packets are processed using XOR-based algorithm to obtain redundant packets. This mechanism features in simple and efficient coding and encoding. Through Matlab simulation, it is proved that the single transmission-reception success rate based on redundancy mechanism is 15% higher than that without redundancy, and the twice retransmission method helps to improve the sucess rate of multiple packet reception.

Key words:BDS; data transmission; short message; data redundancy; XOR-based algorithm

作者简介：唐懿芳(1976-),女，广西富川人,博士,研究方向为计算机软件与理论、无线传感器网络。

*基金项目：企业信息化与物联网测控技术四川省高校重点实验室(2014WYJ07);广东省高科技发展专项基金(2013B010401036)

收稿日期：2015-10-12

中图分类号:TP393.04

文献标志码:A

DOI:10.3969/j.issn.1673-3819.2016.01.014

文章编号：1673-3819(2016)01-0061-05