文章快速检索    
  深空探测学报  2018, Vol. 5 Issue (2): 129-139  DOI: 10.15982/j.issn.2095-7777.2018.02.004
0

引用本文 

Raymond W. YEUNG, DONG Guangliang, ZHU Jian, et al. Space Communication and BATS Codes: A Marriage Made in Heaven[J]. Journal of Deep Space Exploration, 2018, 5(2): 129-139. DOI: 10.15982/j.issn.2095-7777.2018.02.004.
杨伟豪, 董光亮, 朱键, 等. 空间通信与BATS码:天成之合[J]. 深空探测学报, 2018, 5(2): 129-139. DOI: 10.15982/j.issn.2095-7777.2018.02.004.

文章历史

收稿日期:2018-02-09
修回日期:2018-03-31
Space Communication and BATS Codes: A Marriage Made in Heaven
Raymond W. YEUNG 1,2, DONG Guangliang 3, ZHU Jian 1,2, LI Haitao 3, YANG Shenghao 4, CHEN Chao 5     
1. Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong, China;
2. Shenzhen Research Insititute, The Chinese University of Hong Kong, Shenzhen 518072, China;
3. Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China;
4. Network Coding Laboratory, The Chinese University of Hong Kong, Shenzhen 518072, China;
5. State Key Laboratory of ISN, Xidian University, Xi’an 710071, China
Abstract: Innovative communication technologies are in great demand in the national space development program. In this paper, space communication with network coding is studied, with the aim of exploring the feasibility and potential of network coding for future space communication. The characteristics of space communication are first discussed, and an overview of different coding based methods is given. As a potentially applicable technology, network coding based Batched Sparse (BATS) code is presented to address the packet loss problem in multi-hop relay networks. In particular, a BATS code prototype is designed and implemented, and the experiment results demonstrate the advantages of BATS codes over alternative technologies. Finally, the prospect of deployment of BATS codes in space communication is discussed.
Key words: space communication    packet loss    network coding    BATS code    
空间通信与BATS码:天成之合
杨伟豪 1,2, 董光亮 3, 朱键 1,2, 李海涛 3, 杨升浩 4, 陈超 5     
1. 香港中文大学 网络编码研究所,香港;
2. 香港中文大学深圳研究院,深圳 518072;
3. 北京跟踪与通信技术研究所,北京 100094;
4. 香港中文大学(深圳),深圳 518072;
5. 西安电子科技大学 通信工程学院,西安 710071
摘要:创新通信技术在国家重大空间技术开发计划中有着巨大的需求。本文综述了基于网络编码的空间通信技术,旨在探索未来基于网络编码的空间通信技术的可行性和潜力。首先讨论了空间通信的特点,并给出了不同编码方法的概述;详细介绍了基于网络编码的批量稀疏编码(BATS码)创新技术。BATS码作为一种潜在的应用技术可以很好地解决多跳中继网络中严重丢包问题;给出一个BATS码原型设计和实现,实验结果证明BATS码比现有技术具有明显优势;最后,讨论了BATS码在空间通信中的应用前景。
关键词空间通信    丢包    网络编码    BATS码    

Hight lights:

  1. ● The scarcity of resources in space communication necessitates optimal use of such resources for various communication goals.
  2. ● Network coding can significantly improve network bandwidth efficiency, network reliability and network security.
  3. ● BATS codes are a class of network codes that can be very useful for space exploration to combat both high packet loss and long delay.
0 Introduction

Space exploration is of paramount importance in the national strategic development. In recent years, China has made significant advance in the field of space exploration. Tens of Earth satellites have already been successfully launched[1]. The development of manned spaceflight is beginning to take shape[2]. In-depth discussions on the trends of deep space exploration can be found in literatures [3-4].

Communication technology is a crucial enabler of space exploration. However, due to the special characteristics of space communication, technologies for terrestrial communication must be suitable adapted before they can be applied to space communication.

As a revolutionary communication technology, network coding was launched by the paper[5] in 2000. In a nutshell, network coding refutes the folklore that information can be treated as a commodity in network communication. Rather, information needs to be not only routed and replicated but also coded within the network in order to achieve bandwidth optimality. When there is only one information source to be multicast, linear network coding suffices[6-7].

In the past 15 years, network coding has been developed into a cross-disciplinary field of research that straddles channel coding, wireless communication, computer networks, data storage, and cryptography. Both theory and practice show that network coding can significantly improve network bandwidth efficiency, network reliability and network security. In particular, BATS codes, a recent addition to network coding to be discussed later in this paper, can be very useful for space exploration to combat both high packet loss and long delay, especially for multi-hop space network.

With respect to the space missions that are ongoing or already scheduled, space communication can be classified as near-Earth or deep-space, depending on the position of the spacecraft with respect to the Earth stations[8]. The first case refers to data communications between Earth control centers and nodes located at altitudes below 2 × 106 km, with signal propagation delay less than 6.6 s. The second case refers to communication between Earth control centers and nodes located at distance greater than 2 × 106 km (e.g., spacecraft and landers), with signal propagation delay ranges from tens of minutes up to hours.

It is envisioned that future space exploration demands a space communication network[9]. The network will connect spacecraft with one another and in turn with Earth’s terrestrial internet (or core network in general) that can efficiently transfer data back and forth. As a basic building block, relay satellite (s) or spacecraft will be widely deployed for the space network. Fig. 1 shows a possible future deep-space communication network architecture that portrays remote planetary networks communicating with Earth based Internet. It is seen that information from Mars or other planets is acquired by the Earth stations through several relays. Hence, multi-hop transmission is essential for such networks.

Fig. 1 Future deep-space network architecture[9]

Space communications are typically characterized by long delays, high packet loss, and occasional intermittent connectivity and link disruptions. These characteristics make ARQ hardly applicable. To ensure reliable transmission, coding-based schemes need to be considered[10].

A very important factor we need to consider is the storage and processing capability at the intermediate nodes (spacecraft or satellites). In the multi-hop scenario, if transmission on each hop is susceptible to packet loss and each intermediate node performs only store-and-forward, then packet loss would accumulate along the way and impair the end-to-end transmission rate. Specifically, the end-to-end transmission rate would drop exponentially fast as the number of hops increases.

In order to prevent the transmission rate from dropping as the number of hops increases, each intermediate node can in principle decode the transmitted message and then encode it for the transmission on the next hop. However, such a solution is not practical due to the limited storage and processing capability of the intermediate nodes.

In this paper, we propose the use of a new coding scheme, called BATS (Batched Sparse) code[11], for reliable transmission in space networks. BATS code is an efficient random linear network coding scheme suitable for multi-hop networks with packet loss. It has the following features[12]

1) Low encoding complexity at the source node and low decoding complexity at the destination nodes.

2) Constant computational complexity for encoding a packet and constant buffer requirement at an intermediate node.

3) Small protocol and coefficient vector overhead.

4) High transmission rate.

This paper will focus on the basic coding principles and fundamental features of BATS codes. The practical design of BATS code is investigated and it is implemented in a prototype under a real multi-hop environment[13].

The rest of the paper is organized as follows. Section 1 gives a brief introduction to space transmission. Section 2 presents the existing packet-level coding methods for reliable transmission. Section 3 focuses on BATS codes. Several aspects of such codes, including the application background, encoding and decoding methods, and practical design, are discussed. In Section 4, the effectiveness of BATS coded transmission is validated through an implementation prototype. Finally, we make a conclusion and envision the potential application of BATS codes in future space communication systems.

1 Space Communication

Space communication is characterized by long delays, high packet loss, and occasionally intermittent connectivity and link disruptions[10]. An important factor influencing the overall system performance is asymmetric bandwidth availability. Usually, the uplink (connecting Earth to spacecraft) is used to transport command messages and offers an available bit rate in the order of 10 kb/s. The downlink handles image and measurement data, and offers a bit rate up to a few megabits per second. Outage events also likely happen due to ① synchronization loss between the transmitting and receiving stations and ② bad weather conditions, such as rain in the Ka frequency band (26.5–40 GHz) and wind.s

There are two basic methods for reliable transmission:① ARQ based transmission and ② coding based transmission. In the scenario of space communication, however, there are several factors which make ACK-based ARQ inadequate[14].

1) Long delays

The long propagation delay, characteristic of geosynchronous satellites, severely limits the ARQ performance. Long delay channels require larger windows than what standard ARQ employs, and require a more accurate estimation on the Round Trip Time (RTT). In addition, cumulative ACKs and delayed ACKs are not particularly suitable for long-delay satellite environment. Moreover, congestion control becomes rather difficult in the presence of long propagation delay.

2) Asymmetry of link

Space communications are very often used to provide asymmetric bandwidth services. Typical applications require relatively low bandwidth from the user (Earth station) to the information provider (spacecraft or satellite) and relatively high bandwidth towards the user. This strong asymmetry has a non-negligible effect on the ARQ. In the ARQ paradigm, a source sends a new packet only when it receives an ACK for the previously sent packet. Thus the rate at which the source injects packets matches the rate at which the ACKs are returned. This implies that the throughput downstream is controlled by the rate of the ACK flow on the upstream. Therefore, a decrease in the throughput would be caused by the strong asymmetry.

3) Transmission errors

Space communication links are subject to bit errors. In addition, errors often occur in bursts. Typical raw channel bit error rate for satellite links today are ranging from 10–1 to 10–3. ARQ strategy will severely degrade the throughput because of frequent retransmissions.

In summary, ACK-based ARQ is not suitable for reliable space communication. Coding based transmission methods need to be considered[14].

According to the studies performed in space communications, two main scenarios are identified[15-17]

- Optical Near-Earth and Deep-Space communications;

- RF Near-Earth and Deep-Space communications.

Optical communications over deep-space and near-Earth links can be affected by signal degradations because of channel fading introduced by several sources[15]:① atmospheric perturbations due to optical turbulence can cause symbol-level synchronization loss and data loss:② cloud coverage causes signal blockage.

The use of larger telescope apertures usually leads to fading events of duration in the order of 1–10 ms. On the other hand, bandwidth of the tracking control loop is in the order of kHz, thus potentially leading to fading events of duration comparable to those caused by turbulence.

Numerical evidence of the above phenomena has been recorded in the literature. The measurements revealed fluctuations of the received power, giving rise to fading events causing the degradation of the optical link performance. In particular, fading durations ranging between 2 ms and 6 ms were recorded. Fig. 2 illustrates an example of such measurements[15].

Fig. 2 Typical fading pattern in optical downlinks[15]

The aforementioned fading event duration (1–10 ms) can result in the erasure of a significant amount of information, especially at the high data-rate provided by optical links. For example, the transmission of an image file carrying 10 M bytes transported by 1 024 bytes at the data rate of 100 Mbit/s over 1ms fading events would approximately correspond to the reception of 90% of the data volume.

RF communications can be affected by several factors[15]:① Effects of weather on the received signal can last from a fraction of an hour to several hours, in particular in very high frequency bands such as Ka band. This causes the received data to be unreliable over such a period. This may effectively generate a very long burst of erasures in the received data;② Because of antenna pointing errors, the receiver needs to reacquire the signal. During this time the data is lost or unreliable, resulting in possibly many frame erasures;③ Erasures in digital transmission of data can be due to initial acquisition of synchronization and occasional loss of synchronization. In these circumstances, data are lost when the receiver is resynchronizing.

Adverse weather conditions can be hardly compensated by the use of packet-level codes since the long duration of such events (in the order of hours) would require the implementation of very large storage units for decoding purposes, which is an option not currently feasible on spacecrafts. As such, out-of-sync receiver is particularly promising for the application of packet-level codes to compensate for the loss of tens of frames.

2 Coding Schemes for Reliable Transmission

To provide reliable transmission in space communications, error control techniques are usually adopted. Several coding options have been recommended, including the “classical” Reed-Solomon (RS) codes and convolutional codes, and the “modern” iteratively decodable Turbo codes and LDPC codes. These bit-level channel codes operate at the physical layer[8].

However, the bit-level channel coding schemes fail to provide down/up-link reliability in many scenarios. Some data may be lost at the higher layer. These lost data are called erasures. Recent advances of iterative decoding allow further performance improvement by coupling traditional bit-level channel codes with packet-level coding schemes at higher layer.

The motivation for using packet-level erasure correcting codes in space communications comes from the need to achieve reliable data communications in an environment where large propagation delay and limited storage capability of spacecrafts make the use of only conventional channel coding schemes inadequate. An effective channel model from the higher-layer perspective is a Packet Erasure Channel (PEC), where a packet is either correctly received or lost.

Packet-level coding complements bit-level channel coding at the physical layer to provide greater robustness against link errors. The implementation of a packet-level code at higher layers does not aim to replace the bit-level channel code, i.e., the two coding schemes can coexist in the same system.

In space communications, erasures are typically correlated. The PEC can be modeled as a two-state Gilbert erasure channel[16], as shown in Fig. 3. It is based on a discrete-time Markov chain with one good state (G) and one bad state (B). The stationary probabilities that the channel is in the state G and B are denoted by PB and PG, respectively. Essentially no information loss is observed in state G, whereas erasures are experienced in state B. State transition probabilities are denoted by PGG, PGB, PBG, and PBB, respectively. From the stationary assumption, it can be shown that $ P_{\rm GB}\;=\;\frac {P_{\rm B}}{1-P_{\rm B}} P_{\rm BG}$ .The probabilities of receiving an erased symbol when the channel is in the state G and B are eG and eB, respectively. In the state G, the erasure probability eG is very close to 0, while in the state B, it is reasonably assumed that 0.5 ≤ eG ≤ 1. The average erasure rate is $\varepsilon \;=\;{P_{\rm G}}{e_{\rm G}} \;+\;{P_{\rm B}}{e_{\rm G}} $ . In space communication, erasure rates can range from 0.1 to 0.4.

Fig. 3 Two-state Gilbert channel model

In our investigation, we set eG = 0 and eB = 1, respectively. In this case, PB coincides with $\varepsilon $ . Introducing the average permanence in the state B, namely ${\Delta _{\rm B}} \;=\;{\raise0.7ex\hbox{$1$} /\!\lower0.7ex\hbox{${{P_{\rm BG}}}$}} $ , the channel is completely specified by either $\varepsilon $ or $ {\Delta _{\rm B}}$ . Note that $ {\Delta _{\rm B}}$ corresponds to the average erasure burst length, and represents a measure of the channel correlation.

Packet-level coding differs from bit-level coding in the following aspects:First, packets are either correctly received or lost. Second, some degree of side-information about the packet is usually appended in the packet header.

In the literature, there are several classes of packet-level erasure codes. From the practical point of view, only linear codes are concerned. Below, we give an overview of these codes.

1) Fixed-rate erasure codes

An (n, k) erasure code encodes k packets of source data into n packets. One packet of data often amounts to hundreds or thousands of bits. To reconstruct the source data, we need to receive at least k encoded packets[17-18]. If any subset of k encoded packets suffices to reconstruct the source data, the erasure code is called a maximum distance separable (MDS) code. Such a code allows the receiver to recover from up to n-k packet losses.

Another important class of erasure codes is Low-Density Parity-Check (LDPC) codes. LDPC codes have sparse parity-check matrices, i.e., there are a small number of ‘1’s in the parity-check matrix. An LDPC code may also be represented via a bipartite Tanner graph, i.e., a graph with two types of nodes, Variable Nodes (VNs) and Check Nodes (CNs), such that each edge connects two different types of nodes.

LDPC codes are of practical interest since they can be decoded by efficient iterative decoding algorithms, which are sub-optimal but nevertheless perform very well. Recently, long LDPC erasure codes are being considered by the CCSDS (The Consultative Committee for Space Data System) for space applications.

2) Fountain codes

Information transmission in space communication system can be modeled as an erasure channel whose erasure probability can be time-varying or may not be known ahead of time. Therefore, it is not possible to always transmit at a rate closed to the capacity by employing a fixed rate erasure code.

Fountain codes provide an elegant solution to the above problem[18]. Fountain codes are rateless in the sense that the number of encoded packets that can be generated from the source message is potentially unlimited:and the number of encoded packets generated can be determined on the fly.

Besides the rateless property, an ideal fountain code should also have the following properties. A receiver that receives any subset of k [distinct] encoded packets should be able to use a fountain decoder to decode an exact copy of the original source block, independent of which subset of the generated encoded packets is received and independent of whether the subset was generated by one sender or generated by more than one sender from the original block of source data. The computation time for encoding and decoding should be linear, i.e., the time to generate each encoded packet should be linearly proportional to its size, and similarly the time to decode an original source block from encoded packets should be linearly proportional to the original size of the source block.

LT codes were the first practical realization of fountain codes[19]. The LT code retains the good performance of the random linear fountain code, while drastically reducing the encoding and decoding complexities. We can think of the LT code as a sparse random linear fountain code, with an efficient decoding algorithm.

The encoding and decoding costs of the LT codes grow with klgk. To achieve linear encoding and decoding complexity, Raptor codes were proposed by Shokrollahi[20], which concatenate a weakened LT code with an outer code.

3) Network coding

In contrast to the traditional store-and-forward concept, the essence of network coding is to allow encoding of data packets at the intermediate nodes and a receiver decodes the original data when it receives enough encoded packets[5-6].

In packet erasure networks, network coding has been considered to provide reliable transmission. Rateless versions of network coding (e.g., BATS codes will be discussed in Section 3) and fountain coding essentially share a common concept:both schemes can potentially encode source packets into an infinite data stream of encoded packets and receivers can reconstruct the original packets once they have collected a certain number of encoded packets.

By exploiting the redundancy in the network, the receivers are able to successfully recover the original packets from a large number of packet losses[21]. The main difference of network coding and fountain coding is that network coding allows the intermediate nodes to encode packets they have received whereas in fountain coding only the source node generates encode packets. Decoding for network coding can be done by Gaussian elimination, which is similar to that of random fountain codes.

An important class of network coding is called random linear network coding[13], where the encoding at intermediate nodes is performed by randomly combining the incoming packets. The advantage of random linear network coding is that it can be applied when the network topology is dynamic, and the distributed network operations can be performed without prior knowledge of the network topology.

3 BATS Codes 3.1 Motivation

Packet loss in network communications is a general phenomenon. For example, due to noise and interference in wireless communication, the packets transmitted on the network links may not be correctly received. The corrupted packets are detected and treated as lost packets.

It is well known that for multicast networks, linear network coding in general has throughput gain over forwarding. For unicast networks, in the presence of packet loss, network coding can also improve the throughput. For example, wireless network links exist only between two neighboring nodes, as illustrated in the line network in Fig. 4, where node R0 is the source node, node R3 is the destination node, and nodes R1 and R2 are the intermediate nodes that do not demand the input packets. Each link can transmit one packet per timeslot. Suppose the packets transmitted on a network link are erased independently with probability 0.1. If only forwarding is applied at the intermediate nodes, after L hops, the network throughput is upper bounded by (1–0.1)L packet per timeslot. In other words, while the capacity of the network is 0.9 packet per timeslot regardless of L, the network throughput decreases exponentially with L.

By means of retransmission, it is actually possible to achieve the capacity of the network in Fig. 4 in an ideal setting. One typical retransmission scheme is that the source node encodes its packet using a fountain code (e.g., LT codes, Raptor codes) and each node retransmits the packets that are not correctly received by the node at the next hop. However, the feedback required by retransmission costs bandwidth, which can be expensive, e.g., in wireless communication. In scenarios like satellite and deep space communication, feedback has long delay or may not even be available. Moreover, a retransmission scheme as described is not capacity achieving for networks with multicast links, e.g., the example in Fig. 5.

Fig. 4 A three-hop wireless network
Fig. 5 A tree-type wireless network with multicast links

It is proved that network coding can achieve the multicast capacity for networks with packet loss in a wide range of scenarios. The source node transmits random linear combinations of the input packets and an intermediate node transmits random linear combinations of the packets it has received. Note that no erasure codes are required for each link though packet loss is allowed. Network coding itself plays the role of end-to-end erasure codes. A destination node can decode the input packets when it receives enough coded packets with linearly independent coding vectors. This scheme is referred to as the baseline random linear network coding scheme (baseline RLNC scheme).

However, complexity issues prevent practical implementation of the baseline RLNC scheme for real systems. These issues include:① the computational cost of encoding and decoding at the source and sink nodes, respectively;② the storage and computational cost of network coding at the intermediate nodes;and ③ the coefficient vector overhead.

One effective strategy to resolve the above issues is to restrict the application of network coding to small subsets of the input packets. In addition to disjoint subsets of the input packets, this strategy can be applied on overlapped subsets of the input packets. More sophisticated approaches apply network coding to small subsets of the coded packets generated from the input packets. Among these approaches, BATS codes have the highest and close-to-optimal achievable rates. Further, as the outer code of a BATS code is a matrix generalization of a fountain code, BATS codes inherit the rateless property of fountain codes:A BATS code encoder can generate potentially unlimited number of batches, each of which consists of a set of coded packets. During the network transmission, network coding is restricted to the packets belonging to the same batch.

3.2 Encoding

In the sequel, a packet is regarded as a column vector over a finite field F of size q (e.g., q = 28). Fix integers K and T. We encode K input packets, each of which denoted by a column vector in FT . We equate a set of packets to a matrix formed by juxtaposing the packets in this set.

A BATS code consists of an inner code and an outer code over the field F. The outer code is a matrix generalization of a fountain code, and hence rateless. The outer code encodes the file to be transmitted into batches, each containing M packets.

A batch is generated as follows:

1) Sample a degree distribution $\psi \;=\;({\psi _0}, {\psi _1}, \cdots , {\psi _D}) $ and obtain a degree d with probability $ \psi _d$ , where D is the maximum degree:

2) Uniformly at random choose d input packets and form a matrix B by juxtaposing the d packets:

3) The batch X is generated by

${ X} \;= \;{ B}{ G}$ (1)

where G is a d × M matrix over F, called the generator matrix of the batch.

All the batches are independently generated using the same three steps. The generator matrix G can be generated randomly or designed deterministically, and is known by the decoder. When M = 1 and the components of the generator matrices are all nonzero, the above batch encoding process becomes the encoding of LT codes.

We now turn to the inner code, which is formed by the linear transformations on the batches. The batches generated by the outer code are transmitted in a network employing linear network coding. We assume that linear network coding at the intermediate network nodes is only performed among packets belonging to the same batch so that the end-to-end transformation of each batch is a linear operation. Let H be the transfer matrix of a batch and Y be the output (received) packets of the batch. We have

${ Y} \;= \;{ {XH}} \;=\;{ {BGH}}$ (2)

The number of rows of H is M. The number of columns of H corresponds to the number of packets received for the i-th batch, which may vary for different batches and is finite. We assume that H is known by the decoder. In linear network coding, this knowledge can be obtained at the destination nodes through the coefficient vectors.

Suppose that the transfer matrices of the first n batches are ${H_1}, {H_2}, \cdots , {H_n} $ . Denote by rk (H) the rank of a matrix H. Let

${h_r} \;= \;\frac{{\left| {\left\{ {k \in \{ 1, 2, \cdots , n\} :rk({ H}) \;= \;r} \right\}} \right|}}{n}$ (3)

The empirical rank distribution of the transfer matrices ${ h} \;= \; ({h_0}, {h_1}, \cdots , {h_M}) $ is an important parameter for the design of BATS codes.

3.3 Decoding

The inner code preserves the degrees of the batches so that an efficient belief propagation (BP) decoding algorithm can be used to jointly decode the outer code and the inner code. A destination node tries to decode the input packets using Y and the knowledge of G and H for all the received batches. We say a batch is decodable if rk (GH) is equal to the degree d, i.e., the linear system (2) with B as the variable has a unique solution. The BP decoding of BATS codes keeps looking for decodable batches. If a decodable batch is found, the input packets of this batch are recovered by solving the associated linear system (2) and the recovered input packets are substituted into the batches that have not been solved. If a decodable batch cannot be found, the BP decoding stops. Our goal is to decode a given fraction of the input packets before the BP decoding stops.

To guarantee the success of the BP decoding, a proper degree distribution is crucial. The asymptotic analysis of BP decoding induces a degree-distribution optimization problem, which maximizes the coding rate and has the rank distribution h as a parameter. It is demonstrated numerically for general cases that the BATS code with BP decoding achieves rates very close to the average empirical rank $\sum\limits_i {i{h_i}} $ , the theoretical upper bound on the achievable rate of the code in packets per batch.

3.4 Practical Design

We have discussed how to recover a given fraction of the input packets. To reliably transmit all the input packets, we can use the precoding technique first introduced for Raptor codes. That is, before applying the batch encoding process, the input packets are first encoded using a traditional erasure code (called a precode). The batch encoding process is applied to the precoded input packets generated by the precode. If the BP decoding of the BATS code can recover a given fraction of the precoded input packets, the precode is able to recover the original input packets in face of a fixed fraction of erasures. Due to similar requirements, the precode for Raptor codes can be applied to BATS without much modification.

Though the degree distribution optimized asymptotically performs well when the number of input packets is very large (e.g., 100 000), when the number of input packets is small, BP decoding tends to stop before the desired fraction of input packets are decoded. When the BP decoding stops, one approach to continue the decoding process is inactivation. With inactivation, when there are no decodable batches, we instead pick an undecoded input packet b and mark it as inactive. We substitute the inactive packet b into the batches like a decoded packet, except that b is an indeterminate. The decoding process is repeated until all input packets are either decoded or inactive. The inactive input packets can be recovered by solving a linear system of equations using Gaussian elimination. In a nutshell, inactivation decoding trades computation cost (decoding inactive input symbols using Gaussian elimination) with coding overhead. BATS codes with inactivation decoding have demonstrated nearly optimal performance in simulation.

4 Experiments 4.1 Computer Simulation

Since the channel packet loss is unknown in advance, fixed rate coding schemes are not suitable for space multi-hop transmission. Therefore, we only consider rateless coding schemes. So far, fountain codes and BATS codes represent two most typical rateless coding schemes.

We focus on comparing BATS codes with fountain codes where the encoding/decoding is similar to BATS encoding/decoding module with M = 1, but the intermediate nodes only forward packets. The experiment results are given in Fig. 6, where the x-axis and y-axis represent the number of hops and throughput (in Kbit/s), respectively. For both BATS codes and fountain codes, we use K = 5 120, q = 28 and T = 1 024. For the BATS codes, we use batch size 16. It is seen that BATS codes perform much better than fountain codes in the same setup. Here the advantage of BATS codes over fountain codes as observed does not rely on the particular settings of the parameters K, q and T.

Fig. 6 Comparisons of BATS and fountain codes when the link loss rate is 10% and 20%

Though BATS code works very well when the link loss is independent as we demonstrated in the last section, the advantage of network coding in BATS code can be reduced when the link loss is bursty. Burst loss tends to occur in wireless transmission due to interference and fading.

Let us use an example to illustrate the issue of burst loss. Suppose in a line network, 10 percent of the packets transmitted on a link are erased, but the losses on each link are not independent:the packets belonging to a batch are either all erased or all correctly received. Then an intermediate node always receives M packets for a batch. For such a loss pattern, the performance of BATS code is reduced to (1–0.1)L packet per timeslot for L hops, the same as that of the fountain code calculated in the introduction. It is because for the batches that contain lost packets, the BATS code cannot regenerate new packets from the remaining packets in the batch (there is none) to compensate for the lost packets.

In a real-world scenario, the burst loss is not as extreme as the above example. We sample an empirical rank distribution in our simulations given in Fig. 7, where the expected rank distributions of independent link loss are also plotted for comparison. The two curves marked by 10% and 20% loss are the expected rank distributions of the four-hop line network with 10% and 20% percent independent loss rates (per hop), respectively. The average ranks of the three cases are 11.07, 13.13 and 11.12, respectively.

Fig. 7 Empirical rank distribution example in a four-hop line network
4.2 Real Implementation

The main difference between space and indoor environments lies in the packet loss. The software defined method is adopted for the emulation of the channel condition.

We have conducted many tests in which a video captured by a web cam is transmitted over ten (10) pieces of Raspberry Pi 3 (‘Pi’) on a multi-hop Wi-Fi relay network. We adjusted several parameters which affected the test results, and compared the performances of such relay traffic between the traditional fountain code and our proposed BATS code.

In our experiments, we used 1) two i7 notebooks PC’s as the sender (with Logitech C920 USB ‘web cam’) and the receiver, and 2) ten Pi’s each with two EDUP USB Wi-Fi dongles (Fig. 8) serving as an intermediate relay node formed a linear relay network of 11 hops (Fig. 9, R.H.S on the floor). The sender captured a real-time video signal from the web cam, and then encoded and transmitted the video stream through the 10 intermediate nodes to the destination notebook PC for decoding (Fig. 9, L.H.S.).

Fig. 8 Real intermediate relay node
Fig. 9 A linear relay network of 11 hops

In setting up the Pi’s up, we must pay attention to the following:1) the mobile power supply must be able to provide greater than 2.4 A electric current constantly for the Wi-Fi dongles;2) the power cable must be stable enough to support greater than 2 A current;3) the Wi-Fi dongles must have Raspbian driver that supports both 2.4 GHz and 5 GHz frequency bands (dual-band). We also tried to tune the following setup/parameters:① set single Wi-Fi as both client and AP mode;② use dual Wi-Fi dongles, one in AP and the other in station mode;③ vary the hop distance;④ shield the test equipment against the noisy environment;⑤ use an attenuator to reduce the signal strength;⑥ minimize the TCP retransmission setting;⑦ tune the bit rate produced by the web cam;⑧ and use different Linux tools such as a) speedometer;b) hostapd;c) dnsmasq;d) iperf & iperf3;e) terminator;and f) putty & pkill.

We have developed a mechanism to connect the Pi’s and the two PC’s automatically. After that, a routing table is modified for each Pi after boot up. Finally, a set of network monitoring and commanding script is developed. As a result, a linear network was formed and the live video stream at around 6 Mbps was successfully transmitted from the source to the destination. The intermediate nodes ran both fountain code and BATS code simultaneously for comparison. Experimental results show that BATS code outperforms fountain code very much in the multi-hop relay network configuration, as the adverse impact of accumulated packet loss in the fountain code is severe in a multi-hop network, but BATS code could regenerate the lost packets in real-time at every intermediate node so that the video playback can be kept smooth. To see an illustration of BATS codes and a video of the above experiment, please visit[22].

5 Conclusion and Prospect

To accommodate the characteristics of space communication, a network coding scheme, called BATS codes, was proposed for reliable and efficient transmission. The basic principles of BATS codes were expounded. As a packet-level coding scheme, BATS codes are featured by rateless property and low encoding/decoding complexity. Experiments showed that BATS code achieve much higher rates than fountain codes in multi-hop wireless networks.

Recently, the space network is under planning. Several candidate technologies are being considered and investigated. As a basic building block, the multi-hop sub-network should guarantee reliable and efficient transmission. Our studies show that BATS-coded transmission provides a feasible scheme. By further considering more practical aspects, we believe that the BATS-coded system has the potential to be applied in future space information networks.

参考文献
[1]
YI K C, LI Y S, CHEN H, et al. Recent development and its prospect of satellite communications[J]. Journal on Communications, 2015, 36(6): 157-172. (0)
[2]
ZHOU J P. Rendezvous and docking technology of manned space flight[J]. Manned Spaceflight, 2011(2):1-8. (0)
[3]
ZHANG N T, LI H, ZHANG Q Y. Thought and developing trend in deep space exploration and communication[J]. Journal of Astronautics, 2007, 28(4): 786-793. (0)
[4]
SUN Z Z, MENG L Z. Current situation and sustainable development trend of deep space exploration in China[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2015, 47(6): 785-791.   https://link.springer.com/article/10.1007/s40565-016-0199-2 (0)
[5]
AHLSWEDE R, CAI N, LI R S Y, et al. Network information flow[J]. IEEE Transaction on Information Theory, 2000, 46(4): 1204-1216. DOI:10.1109/18.850663 (0)
[6]
LI R S Y, YEUNG W R, CAI N. Linear network coding[J]. IEEE Transaction on Information Theory, 2003, 49(2): 371-381. DOI:10.1109/TIT.2002.807285 (0)
[7]
KOETTER R, MEDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795. DOI:10.1109/TNET.2003.818197 (0)
[8]
CALZOLARI G P, CHIANI M, CHIARALUCE F, et al. Channel coding for future space missions, new requirements and trends[J]. Proceedings of the IEEE, 2007, 95(11): 2157-2170. DOI:10.1109/JPROC.2007.905134 (0)
[9]
MUKHERJEE J, RAMAMURTHY B. Communication technologies and architectures for space network and interplanetary internet[J]. IEEE Communications Surveys and Tutorials, 2013, 15(2): 881-897. DOI:10.1109/SURV.2012.062612.00134 (0)
[10]
COLA T D, PAOLINI E, LIVA G, et al. Reliability options for data communications in the future deep-space missions[J]. Proceedings of the IEEE, 2011, 99(11): 2056-2074. DOI:10.1109/JPROC.2011.2159571 (0)
[11]
YANG S H, YEUNG W R. Batched sparse codes[J] IEEE Transactions on Information Theory, 2014, 60(9): 5322-5346. DOI:10.1109/TIT.2014.2334315 (0)
[12]
YANG S H, YEUNG W R. BATS codes: theory and practice[M]. [S.l]: Morgan & Claypool Publishers, 2017. (0)
[13]
HO T, MéDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transaction on Information Theory ,2006, 52(10): 4413-4430. DOI:10.1109/TIT.2006.881746 (0)
[14]
COLA T, MARCHESE M. Reliable data delivery over deep space networks: benefits of long erasure codes over ARQ strategies[J]. IEEE Wireless Communications, 2010, 17(2): 57-65. DOI:10.1109/MWC.2010.5450661 (0)
[15]
Consultative Committee for Space Data Systems. Erasure correcting codes for use in near-earth and deep-space communications[M]. Washington, DC, USA: CCSDS Secretariat National Aeronautics and Space Administration, 2014. (0)
[16]
LIVA G, MATUZ B, KATONA Z, et al. On construction of moderate-length LDPC codes over correlated erasure channels[C]//Communications, 2009, ICC '09. IEEE International Conference on. Dresden, Germany: IEEE, 2009. (0)
[17]
RIZZO L. Effective erasure codes for reliable computer communication protocols[J]. ACM Computer Communication Review, 1997, 27(2): 24-36. DOI:10.1145/263876 (0)
[18]
MACKAY D J C. Fountain codes[J]. IEE Proceedings–Communications, 2005, 152(6): 1062-1068. DOI:10.1049/ip-com:20050237 (0)
[19]
LUBY M. LT codes[C]//The 43rd Annual IEEE Symposium on Foundations of Computer Science. Vancouver, BC, Canada: IEEE, 2002. (0)
[20]
SHOKROLLAHI A, LUBY M. Raptor codes, ser. foundations and trends in communications and information theory[J]. Communications and Information Theory, 2009(6): 213-322. (0)
[21]
CHOU P A, WU Y, JAIN K. Practical network coding[C]//Proceeding Allerton Conference. Communication, Control, and Computing. Monticello, IL: [s.n], 2003. (0)
[22]
Institute of network coding, CUHK. Multi-hop on problem introducing BATS[EB/OL]. [2018-04-12]. http://iest2.ie.cuhk.edu.hk/~whyeung/BATS.mp4. (0)