INTRODUCTION

The network coding is a new transmission paradigm, whose core idea is to allow intermediate nodes inside the network to encode and decode information from different flows (Ahlswede et al., 2000). Some initial investigation of network coding in wireless broadcasting retransmission has been reported, e.g., the AP combines and transmits the lost packets of different received nodes, instead of any single packet (Dong et al., 2009; Xiao et al., 2008).

Even though network coding reduces the retransmission number, there are some features which can be tuned to improve the performance of its application to wireless broadcasting retransmission. It is noted that under the same bit error rate, a decreasing block size would decrease the block error rate as well, similarly, it can be argued that if the block size increases, the resulting block error rate increases as well (Jin and Baochun, 2008). The failure of previous broadcast indicates that the packet (block) error rate is high under the same size of packet (block) and the same bit error rate. From the previous study, it can be argued that if the AP decreases the coded block size when it combines the groups of bits in the lost packets, the error rate of coded block would decrease, and the performance of network coding in broadcasting retransmission can be improved. However, when receivers decode network coded packets, they need packets received at previous broadcasting and the coded data combined by the lost data. Thus, some limitations in received node’s decoding exit due to different size between previous received packets and coded block, when the AP tunes the coded block size.

The study presents an Adaptive Symbol-level Network Coding (ASNC) in wireless broadcasting retransmission. The core component of the ASNC protocol is a new network coding for broadcasting retransmission that operates on small groups of bits, these groups are called symbols. In ASNC, the AP can tune coded block size adaptively in order to decrease block error rate under the same bit error rate, then, received nodes array and split data segments of packets received successfully at previous broadcast, at last they decode in order to get unknown symbols and array all symbols according to priority. Through operating on symbol level, the scheme proposed can overcome the different size between coded block and previously received packets, and further improve the performance of broadcasting retransmission based on network coding because of the lower block error rate.

SYSTEM MODEL

Wireless broadcasting retransmission model: The model for wireless broadcasting retransmission is as follows:

Basic idea of ASNC: In order to reduce rebroadcast number, ASNC calculates different linear coding packets to achieve retransmission. In ASNC, when a data segment is to be transmitted, it is divided into n blocks, each of which has a fixed number of bits. To decrease block error rate, the block size is adapted to link quality. Each block is denoted as x_i. The sender chooses a set of coding coefficients C [c₁,c₂,...,c_n] in the Galois field and produces a coded block y as a linear combination of the original data blocks:

(1)

The sender keeps on transmitting coded blocks to receivers until all the receivers can decode blocks. When receivers decode blocks, they use coded blocks at rebroadcast and the received packets at previous broadcast in symbol level. First, they split the data segment into several small groups of bits. The data segment is composed of bits which are successfully received previously, and the size of group is the same as the size of coded block. Second, through Gauss-Jordan elimination, each receiver gets unknown groups of bits. At last, the receiver combines groups according to priority, and does the AP broadcast original data.

Figure 1 illustrates the example of ASNC with two received nodes. At previous broadcast, the AP sent four packets P1, P2, P3 and P4 to all received nodes. Packets P1 and P3 are lost in the node R1; packets P2 and P4 are lost in the node R2. To provide reliability, the AP should retransmit the lost packets.

In traditional retransmission approach based on random linear network coding (Xiao et al., 2008), the coded block is a linear combination of packets P1, P2, P3 and P4.

However, in ASNC, the AP splits the data segment adapting to the link quality firstly. Of course, there is a tradeoff between transmission number and transmission reliability. For simple explaining, in Fig. 1, the AP splits it into eight blocks x₁...x₈. And x_i is the ith symbol of data segment. The AP calculates and to construct the coded blocks. Then the AP broadcasts the linear coded blocks. The node R1 has received packets P2 and P4 at previous broadcast, after the node R1 received four uncorrelated random linear coding packets and with the help of coefficients taken by the header of random linear coded packets, it can split P2 and P4 into x₃, x₄, x₇ and x₈.

Fig. 1:	Example of ASNC with two received nodes

Thus, it can convert the random linear coded packets to eight linear equations as shown in Eq. 2.

The equations set has four unknown symbols x₁, x₂, x₅ and x₆ which is easily solvable. Through Gauss-Jordan elimination, the node R1 can get the original symbols x₁, x₂, x₅ and x₆, further gets the P1 and P3. The node R2 can get the lost packets in the same way. Hence, ASNC can achieve retransmission.

(2)

IMPLEMENTATION

As shown in Fig. 1, it is obvious that, through random linear coding, ASNC can mix and extract lost data groups in symbol level to achieve retransmission. However, in practical ASNC, there are some difficulties in operating adaptive network coding over symbol.

Adaptive block size: It is obvious that fewer redundant coded blocks need to be retransmitted caused by smaller block size. If the AP chooses an optimal block size, under the poor channel conditions, the goodput will be raised and the average number of transmission will be decreased.

We utilize feedback of previous broadcasting to achieve adaptive block size tuning. Through feedback, the AP can get channel conditions. With such knowledge, the AP dynamically adjusts block size for network coded broadcasting retransmission. To refer the approach of Jin and Baochun (2008), we propose three types of feedback to identify packet error rate and the changes in block size according to the feedback which are shown in Table 1.

Fig. 2:	Packet format in ASNC

Table 1:	The list of block size adjustment

For example, “1/10” implies to decrease block size by 1/10 of the size of original packets. With the adaptive block size algorithm, the AP dynamically changes block size before network coded broadcasting retransmission, which will lead to less average number of transmissions.

Architecture: In ASNC, we insert a coding layer between MAC layer and networking layer like COPE (Katti et al., 2006). In retransmission process, the coding layer in the AP side arrays packets to construct data segment at first; second, it splits data segment into several blocks adapting to link quality; third, blocks are random linear combined to construct coded blocks; at last, the coding layer inserts the header in front of each coded block to produce coded packet and transmits them to MAC layer.

On the other side, the coding layer in the received nodes gets coded packets from MAC layer at first; second, referring to coefficients in the header, it picks up corresponding groups of bits from packets which are received successfully at previous broadcast, we call these groups as original symbols and then, it operates on decoding to get symbols containing unknown bits; at last, the coding layer arrays these.

Packet format: ASNC inserts a header in each coded packet, as shown in Fig. 2. The header contains code vector, sequence vector and block size. The code vector describes coding coefficients of coded block contained by this packet. The sequence vector describes the order of packets which are arrayed by AP. The block size presents the size of symbol which is the unit operated by nodes in ASNC.

Fig. 3:	Average transmission number of ASNC compared with the scheme based on traditional network coding symbols according to priority and transfers them to networking layer

The value of field that describe code vector is obtained by classic algorithm, and initialized by the AP node. The value of the field that describes sequence vector and block size is initialized by the AP node too. And with the help of these values, received nodes pick up correspond symbols from packets which they received at previous broadcast.

ANALYSIS AND NUMERICAL RESULTS

Coded block error probability: The size of data block in each packet is n bits. The bit error probability is P_Eb, thus the block error probability P_EB is:

(3)

In ASNC, the AP tuned the value of n adapting to the max P_Eb.

Average number of transmission in ASNC: From the presented view of Dong et al. (2009) and Xiao et al. (2008), we can get the average number of transmission N_t in ASNC with M receivers as:

(4)

We define that P_m = max_i∈{1...M} {P_Ebi}. From Eq. 2 and 3, we can get:

(5)

Under the same P_m, the average number of retransmission is the function of n which is the size of coded block.

Numerical results: The simulation layout consists of one AP and five receivers in 802.11b. We assume the size of original packets is 1500 bytes.

Figure 3 shows the result of ASNC and the scheme based on traditional network coding. As we analyzed, the average transmission number of ASNC is less than traditional network coding. This is because the ASNC adjusts the coded block size to channel condition, which could decrease the block error rate.