You need Adobe Reader 7.0 or later in order to read PDF files on this site.
If Adobe Reader is not installed on your computer, click the button below and go to the download site.

Letters

Vol. 8, No. 3, pp. 25–30, Mar. 2010. https://doi.org/10.53829/ntr201003le1

Research and Development of Wireless Network Coding to Achieve High-efficiency Multihop Wireless Systems

Nobuaki Otsuki^†, Yusuke Asai, and Takatoshi Sugiyama

Abstract

We are developing multihop wireless systems that achieve high spectrum utilization efficiency by using network coding, which has mainly been studied to mitigate congestion in wired networks. In this article, we explain diversity and wireless hybrid network coding techniques that can improve the communication quality of multihop wireless systems.

†	NTT Access Network Service Systems Laboratories Yokosuka-shi, 239-0847 Japan

1. Introduction

With high-speed, high-capacity access networks based on optical fibers becoming more common, the number of customers using broadband services is growing rapidly. However, there are customers who cannot receive broadband service because of the physical difficulty of laying optical fiber to their homes. Wireless access networks, typified by WIPAS (wireless IP access system, IP: Internet protocol) [1], have received much attention and are seen as an attractive means of providing broadband access networks to such customers. They are cost-effective as access networks because no optical fiber construction is required for the access network segment.

Multihop wireless systems are now a hot research topic because they can expand the service area of wireless access networks (Fig. 1). Moreover, they make it easy to change the network topologies. By exploiting these features, multihop wireless access networks can provide broadband service to rural areas very effectively. Thus, they are expected to overcome the digital divide in rural areas where broadband service is not provided because the optical fiber construction cost per user is too high. However, multihop wireless systems have some problems:

(1) System throughput degrades as the number of hops increases.

(2) Communication quality is poorer than for optical access networks.

Fig. 1. Multihop wireless network.

To prevent system throughput degradation, network coding (NC) is being studied. To improve communication quality, we have invented a diversity technique for NC as well as wireless hybrid network coding (WHNC). These techniques are explained below.

2. Wireless network coding

Although NC was invented to mitigate traffic congestion in wired networks [2], its application to wireless networks is now being intensely studied [3]. Wireless network coding (WNC) created by applying NC to a multihop wireless network is shown in Fig. 2. In this network, end nodes A and B exchange information via relay node R because A and B are too far apart to communicate directly. This topology, called the Alice-and-Bob topology, is the simplest multihop wireless network to which NC is applicable.

Fig. 2. Alice-and-Bob topology.

The information that A and B send is denoted by α and β respectively. Without WNC, four time slots are necessary for communication between A and B, as shown in Fig. 3. On the other hand, with WNC, only three time slots are necessary, as shown in Fig. 4. In time slot T₃, R encodes the received information, α and β, to generate new information γ, which it broadcasts to A and B. Although various NC methods have been proposed [4], we chose to use bitwise XOR (exclusive OR) in the study reported here. In the same time slot T₃, A decodes received information γ by XORing γ using its own information α to obtain desired information β. Likewise, B processes γ received in T₃ using its own information β to obtain desired information α. The function blocks for B’s operations with conventional WNC are shown in Fig. 5. WNC can improve the system throughput by decreasing the number of time slots needed for communication.

Fig. 3. Transmission without network coding.

Fig. 4. Transmission with network coding.

Fig. 5. Function blocks for B’s operations with conventional WNC.

3. Techniques for improving communication quality

We have been collaborating with Kyoto University to study WNC and address the communication quality degradation in WNC. NTT is mainly studying the physical (PHY) layer of WNC while Kyoto University is tackling its media access control (MAC) layer [4]. In this article, we introduce the WNC diversity and WHNC techniques invented by NTT.

3.1 WNC diversity

In multihop wireless networks, the quality communication between end nodes can never exceed that of the intermediate wireless link (hop) with the lowest quality. Therefore, the communication quality degrades as the number of hops is increased to extend the service area. To improve the communication quality, we have invented a WNC diversity technique that uses the signals exchanged directly between end nodes (see Fig. 2) [5].

The processes in our technique are explained below using B’s operations as an example. Since signals transmitted in wireless communications are broadcast, information α transmitted from A to R can also reach B, albeit with greatly attenuated signal power. This weak direct signal is called the overreach signal. B can improve the communication quality by diversity combining γ received from R and the overreach signal. Since these two pieces of information are different, conventional diversity schemes in the physical (PHY) layer cannot be used. To solve this problem, our technique performs network decoding in the PHY layer by processing the soft values of information signals, i.e., the received bit sequences of information, prior to forward error correction (FEC) decoding, although the usual approach is to implement network decoding in the MAC layer by processing data streams consisting of hard values, “1” or “0”, posterior to FEC decoding. Since B can obtain α in the PHY layer by network decoding in the PHY layer, diversity combining in the PHY layer can be used for α from the overreach signal and for α extracted from γ.

The function blocks for B’s operations with WNC and diversity (our technique) are shown in Fig. 6. The differences from the conventional scheme without WNC in Fig. 5 are as follows:

The processing order of FEC decoding and network coding/decoding is reversed (but the resulting output is exactly the same).
With WNC, B has an additional memory circuit to store the overreach signal.
With WNC, B has an additional diversity combining circuit.

Fig. 6. Function blocks for B’s operations with WNC and diversity.

B receives and stores α received from A in time slot T₁ in its memory circuit (Fig. 6(a)). In T₂, B transmits β and retains the FEC-coded β in memory (Fig. 6(b)). In T₃, B demodulates γ and extracts α by network decoding using the FEC-coded β in its memory. After the diversity combining of α from the overreach signal (held in memory) and extracted information α, the combined α is FEC decoded (Fig. 6(c)). This leads to a higher probability of successful FEC decoding and improves the communication quality.

3.2 WHNC

In our hybrid version of WNC called WHNC (wireless hybrid network coding), R has two operating modes to counter the error propagation problem. R decodes α and β and checks for bit errors. If α or β or both contain bit errors, R superposes the two radio signals from A and B and transmits the result. The conventional approach—demodulating the signals and XORing the information at the bit level—means that any errors are fixed and cannot be removed by any subsequent processing, which degrades the overall communication quality. Our approach of superposing the radio signals allows for the possibility that processing at the end node will yield correct reception. If the α and β demodulated at R do not contain any error bits, R transmits XORed γ in the conventional manner.

4. Combined scheme (WNC diversity + WHNC)

We evaluated the communication quality and system throughput by computer simulation to verify the effectiveness of our combined scheme (WNC diversity and WHNC). Communication quality was evaluated in terms of the frame error rate (FER). The simulation parameters are listed in Table 1. The PHY layer parameters comply with the IEEE802.11a standard. To avoid mutual interference, only one node transmitted at a time. The FER of α sent from A to B and the system throughput were evaluated using a frame length of 1000 bytes.

Table 1. Simulation parameters.

The FER versus the signal-to-noise ratio (SNR) of α is shown in Fig. 7. We found that the communication quality was better with our scheme than with only WNC. For example, in the case of 54 Mbit/s, our scheme achieved an SNR improvement of 0.7 dB at an FER of 10^–3. When we consider that the received radio power falls in proportion to the square of the propagation distance, a 0.7-dB improvement in SNR corresponds to an increase of 8.3% in the maximum communication distance between end nodes for the same communication quality. With the conventional scheme, the maximum communication distance is 7.14 km. Our new scheme can extend it by 600 m, which is a significant increase in service area.

Fig. 7. FER versus SNR.

The system throughput performance is shown in Fig. 8. Here, the throughput with our scheme is compared with that of a conventional multihop wireless network without WNC. Our scheme achieved a throughput improvement of up to 9 Mbit/s for SNR = 18 dB.

Fig. 8. Throughput versus SNR.

These simulation results confirm that communication quality can be improved by using diversity and WHNC techniques and that system throughput can be enhanced by using WNC.

5. Conclusion

This article explained WNC, which raises the spectrum utilization efficiency of multihop wireless networks. It also introduced diversity and WHNC techniques, which can improve the communication quality. Computer simulations verified that these techniques can improve both the SNR for a given FER and the system throughput.

References

[1]	Y. Mizumoto, T. Yoshie, Y. Hatakeyama, H. Maruyama, and M. Baba, “Improvements to WIPAS (Wireless IP Access System) for Application-area Expansion,’’ NTT Technical Review, Vol. 2, No. 9, pp. 55–61, 2004. https://www.ntt-review.jp/archive/ntttechnical.php?contents=ntr200409055.pdf
[2]	R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, “Network information flow,’’ IEEE Trans. Inf. Theory, Vol. 46, No. 4, pp. 1204–1216, 2000.
[3]	S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “XORs in the Air: Practical Wireless Network Coding,” IEEE/ACM Transaction on Networking, Vol. 16, No. 3, pp. 497–510, 2008.
[4]	T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Trans. on Information Theory, Vol. 52, No. 10, pp. 4413–4430, 2006.
[5]	D. Umehara, T. Hirano, S. Denno, M. Morikura, and T. Sugiyama, “Wireless network coding in slotted ALOHA with two-hop unbalanced traffic,” IEEE Journal on Selected Areas in Communications, Vol. 27, No. 5, pp. 647–661, 2009.
[6]	N. Otsuki, Y. Asai, T. Ichikawa, and M. Mizoguchi, “A Packet Combining Demodulation Scheme for Multihop Wireless Systems using Network Coding,” IEEE Vehicular Technology Conference 2008-Fall, Calgary, BC, Canada, 2008.

	Nobuaki Otsuki NTT Access Network Service Systems Laboratories. He received the B.E. degree in electronic engineering and the M.E. degree in information science and technology from Hokkaido University in 2003 and 2007, respectively. He joined NTT Access Network Service Systems Laboratories in 2007 and has been engaged in R&D of signal processing in multihop wireless networks using network coding. He is a member of IEEE and the Institute of Electronics, Information and Communication Engineers (IEICE) of Japan.
	Yusuke Asai Research Engineer, Wireless Systems Innovation Laboratory, NTT Network Innovation Laboratories. He received the B.E. and M.E. degrees in information electronics from Nagoya University, Aichi, in 1997 and 1999, respectively. He joined NTT Network Innovation Laboratories in 1999 and has been engaged in R&D of signal processing in wireless communication systems, especially for IEEE802.11 wireless local area network standards. He received the Young Engineer Award from IEICE in 2003. He is a member of IEEE and IEICE.
	Takatoshi Sugiyama Senior Research Engineer, Supervisor, Group Leader, NTT Access Network Service Systems Laboratories. He received the B.E., M.E., and Ph.D. degrees from Keio University, Kanagawa, in 1987, 1989, and 1998, respectively. After joining NTT in 1989, he was engaged in R&D of forward error correction, interference compensation, CDMA, modulation-demodulation, and MIMO-OFDM for wireless communication systems such as satellite and mobile systems. From 1988 to 2001, he was in charge of business planning for international satellite communication services in NTT Communications. From 2004 to 2007, he was in the Wireless Laboratories of NTT DoCoMo, Inc., where he was engaged in R&D of wireless resource management schemes, plug-and-play base stations, and wireless mesh networks. He is currently responsible for R&D of intelligent interference compensation techniques and radio propagation modeling for future wireless communication systems. He received the Young Engineer Award from IEICE in 1996. He is a member of IEEE and IEICE.

↑ TOP