Subscribe Now Subscribe Today
Short Communication
 

Adaptive Symbol-level Network Coding for Broadcasting Retransmission



Wu Wei, Peng Qian, Bo Zhang and Benxiong Huang
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

Recently, network coding has been introduced for broadcasting retransmission. It can be noted that, under the same bit error rate, the block error rate would decrease while the size of block decrease. However, traditional network coding based broadcasting retransmission require that the size of coded block re-broadcasted is the same as the size of packets which are received successfully at previous broadcasting. Thus, there are several limitations exit when the AP tunes the size of coded block in traditional network coding based broadcasting retransmission. In this study, we propose a scheme based on adaptive symbol-level network coding to overcome the problem. In the simulation based on 802.11b, it is obvious that this scheme is better in average number of broadcasting retransmission.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Wu Wei, Peng Qian, Bo Zhang and Benxiong Huang, 2011. Adaptive Symbol-level Network Coding for Broadcasting Retransmission. Information Technology Journal, 10: 1264-1267.

DOI: 10.3923/itj.2011.1264.1267

URL: https://scialert.net/abstract/?doi=itj.2011.1264.1267
 
Received: December 06, 2010; Accepted: March 22, 2011; Published: May 13, 2011



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:

There are one sender (AP) and M receivers (M>1)
The sender uses random linear network coding based approach to combine lost data segments
Data are sent in packets, and each packet is sent in a fixed time slot
The AP node can know the received states of all received nodes
Packets lost at received node i follow Bernoulli distribution with parameter Pi and the lost packets at different received nodes are uncorrelated

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 xi. The sender chooses a set of coding coefficients C [c1,c2,...,cn] 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 x1...x8. And xi 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 x3, x4, x7 and x8.

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 x1, x2, x5 and x6 which is easily solvable. Through Gauss-Jordan elimination, the node R1 can get the original symbols x1, x2, x5 and x6, 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 PEb, thus the block error probability PEB is:

(3)

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

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 Nt in ASNC with M receivers as:

(4)

We define that Pm = maxi∈{1...M} {PEbi}. From Eq. 2 and 3, we can get:

(5)

Under the same Pm, 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.

CONCLUSION

In this study, we present a scheme based on adaptive symbol-level network coding to improve performance of network coding based broadcasting retransmission. In the scheme, the AP adjusts coded block size to the link quality before broadcasting retransmission. Meanwhile, the AP and received nodes operate network coding over symbols composed of bits which is helpful to neglect differences between coded blocks and original packets in size. Based on numerical analysis and simulation results, in average number of broadcasting retransmission, the scheme is better than the approach based on traditional network coding by exploiting the relationship between block size and block error rate under the same bit error rate.

ACKNOWLEDGMENT

This research is sponsored by the National Science Foundation of China NSFC under the Grant No. 60803005.

REFERENCES
1:  Ahlswede, R., N. Cai, S.Y.R. Li and R.W. Yeung, 2000. Network information flow. IEEE Trans. Inform. Theory, 46: 1204-1216.
CrossRef  |  

2:  Dong, N., T. Nguyen and B. Bose, 2009. Wireless broadcast using network coding. IEEE Trans. Vehicular Technol., 58: 914-925.
Direct Link  |  

3:  Xiao, X., L. Yang, W. Wang and S. Zhang, 2008. A broadcasting retransmission approach based on random linear network coding. Proceedings of the 9th International Conference for Young Computer Scientists (ICYCS), Nov. 18-21, Hunan, pp: 457-461.

4:  Jin, J. and L. Baochun, 2008. Adaptive random network coding in WiMAX. Proceedings of the IEEE International Conference on Communications (ICC), May 19-23, Beijing, pp: 2576-2580.

5:  Katti, S., D. Katabi W. Hu H. Rahul and M. Medard, 2006. The importance of being opportunistic: Practical network coding for wireless environments. Proceedings of the 43rd Annual Allerton Conference on Communication. http://www.mit.edu/~medard/PAPERS/paper142.pdf.

©  2021 Science Alert. All Rights Reserved