Int'l J. of Communications, Network and System Sciences
Vol.2 No.1(2009), Article ID:182,7 pages DOI:10.4236/ijcns.2009.21006

Parallel-Transmission: A New Usage of Multi-Radio Diversity in Wireless Mesh Network

Yun HU1, Shoubao YANG, Qi ZHANG, Peng ZHANG

Department of Computer Science, University of Science and Technology of China, Hefei, Anhui, China

Emails: 1geajy@mail.ustc.edu.cn

Received September 5, 2008; revised December 1, 2008; accepted December 31, 2008

Keywords: Wireless Mesh Network, Radio Diversity, Parallel Transmission, Scheduling Algorithm

Abstract

To fully utilize the diversity of multi-radio, a new parallel transmission method for wireless mesh network is proposed. Compared with conventional packet transmission which follows “one flow on one radio”, it uses the radio diversity to transmit the packets on different radios simultaneously. Three components are presented to achieve parallel-transmission, which are control module, selection module and schedule module. A localized selecting algorithm selects the right radios based on the quality of wireless links. Two kinds of distributed scheduling algorithms are implemented to transmit packets on the selected radios. Finally, a parallel-adaptive routing metric is presented. Simulation results by NS2 show that this parallel-transmission scheme could enhance the average throughput of network by more than 10%.

1.  Introduction

Wireless local network (WLAN) is widely implemented today to provide hot spot coverage. Wireless Mesh Network (WMN) [1,2], a new wireless architecture is emerging as a latest trend in development because of its lower cost and wider coverage. A WMN is made up of Mesh Routers (MRs) and Mesh Clients (MCs). MRs with less mobility form the backbone of WMN, provide access to Internet for MCs. MCs might be mobile or stationary, and they can be linked to MRs directly or with the help of other clients. Some of MRs work as gateways. As a result, all the covered equipments can be linked to Internet in several hops.

Recently the tremendous popularity of wireless systems has led to the commoditization of RF transceivers (radios) whose prices have fallen dramatically. The use of two or more radio modules in a device is becoming economically feasible. On the other hand, MRs and MCs must content for single channel to forward packets in Single-Radio WMN. The channel contention leads to a low network capacity and non-predictable network delay. Due to the physical limitation it is very hard to improve the performance through protocol redesign. Therefore, to further improve the flexibility of WMN, a MR is usually equipped with multiple radios. BelAir [20] reports the capacity of 3 modes (single-radio, dual-radio and multi-radio) of WMN in its white paper. It’s shown that multi-radio mode has the best performance. Bahl [3] shows wireless systems using multiple radios in a collaborative manner dramatically improve performance and functionality over the traditional single radio wireless systems, that is popular today in terms of energy management, capacity enhancement, mobility management, channel failure recovery, and last-hop packet scheduling behavior. On the basis of this work, a great number of related researches have been done in terms of routing, medium access control, channel assignment etc [4-8,12].

Most works on MR-WMN are based on “one flow transmission on one radio”, that is to say the system will select a best radio to use when transmission occurs. [5] selects the best link quality corresponding to one radio. Some other researches focus on channel assignment which tries to make the network with lower interference and higher capacity [13,14]. As node only selects the best radio, mostly, some radios are free. Links between two nodes are always more than one in multi-radio environments, and they work on different channel, so packets could be parallel transmitted on them. It will enhance the throughput of transmission. To make all the radios collaboratively work on one node, utilizing the radios’ diversity will be the main point of this paper. We provide a parallel-transmission method here, meanwhile, a parallel-adaptive routing metric is provided when mesh nodes are selecting routes. The contributions of this paper are as follows:

•     It’s the first provision of adopting parallel transmission to advance the multi-radio utilization.

•     A Parallel-transmission model proposed, which makes parallel-transmission operate as on one radio.

•     The selecting algorithm operating on the model is localized and the selection is based on the quality of wireless links. This algorithm adapts to the asymmetry of wireless environments.

•     Two distributed scheduling algorithms are presented for our model in different ways. Algorithm 1 transmits multiple, possibly erroneous copies of a given frame on selected-radios. Algorithm 2 transmits packets on different radios with random probability.

•     A parallel-adaptive routing metric is introduced for routing selection.

Some simulation experiments are carried to show that parallel transmission could exactly enhance the performance of wireless mesh networks. Three key performance metrics are analyzed in this paper. Our two parallel algorithms both could improve the throughput by 10-50%, and the delay could exactly fit the transmission of some special applications such as VoIP and so on. Meanwhile, the retransmission probability reduces using scheduling algorithm 1.

The rest of the paper is organized as follows. In Section 2, we present a review of related work in this area. Motivations of this paper are provided in section 3. Section 4 describes our parallel transmission mechanism. And in section 5, an adaptive routing is proposed. Section 6 shows the simulation results. Finally, section 7 concludes this paper.

2.  Related Work

2.1.  Media Access Control for Multi-Radio System

Several researchers have submitted extra mechanisms to improve the performance of multi-radio wireless network using multi-radio diversity. For wireless local area network, the Multi-Radio Diversity (MRD) wireless system is presented in [9], which uses path diversity to improve loss resilience. It incorporates two techniques to recover from bit errors and reduce the loss rates observed by higher layers, without consuming much extra bandwidth. One is frame combining, and the other is request-for-acknowledgement (RFA).

In multi-hop wireless network, another multi-radio unification protocol (MUP) is introduced in [6]. MUP conceals multiple NICs from layers above it by presenting a single virtual interface, and then MUP periodically monitors the channel quality on each interface to each of its neighbors. When it is time to send a packet to a neighbor, it selects the right interface to forward the packet on. This means that at one time MUP only allows one interface to work and the other interfaces are out of work. It’s a low utility ratio of multi-radio.

2.2.  Routing in MR-WMN

As a simply implemented metric, hop count is widely used in wired network routing protocols. However, minimal hop count couldn’t be equal to good link quality because of the complexity of wireless link. Most researches try to achieve a good routing metric to character the quality of wireless link. [10] presents the expected number of transmission (ETX) which is measured as follows:

(1)

df (forward delivery ratio): probability that a data packet successfully arrives at the recipient.

dr (reverse delivery ratio): probability that the ACK packet is successfully received.

Analysis done in [11] shows that ETX has the best performance compared to hop count, RTT and PktPair in static multi-hop wireless networks. Based on ETX, [5] provides a new routing metric called WCETT which could character the diversity of multi-channel. It is based on the idea of MUP. Now, most routing designing in based on the above work. On one hand, many routing metrics [5,10] provide better characterization of link state. On the other hand, routing protocols for multiradio environments [5,6] use these metrics to find a transmission path. However, all of them have the same disadvantage, which is the low utilization of multi-radio.

To fully utilize the diversity of multi-radio, a paralleltransmission scheme is provided. This paralleltransmission is adaptive to multi-hop wireless mesh network.

3.  Motivation

3.1.  Parallel Transmission

Two interfaces working on different frequency can forward the packet simultaneously as it is regarded as no self-interference. To achieve more capacity, the utilization of diversity of multi-radio and multi-channel becomes a key point. Many channel assignment algorithms [14-16] try to find the optimization assignment using both centralized and distributed methods. Multi-channel and multi-radio comes in order to decrease the self-interference under the transmission range and enhance throughput of end-to-end transmission. However, the mere usage of diversity of multi-radio for preventing inter-flow or intra-flow interference is not enough. This paper proposes a new usage of the diversity of multi-radio, which is called parallel transmission. Figure 1 shows that the two transmitting nodes are equipped with dual-radio and they work on different channels with no interference. Thus the packets on link1 and link2 can transmit simultaneously just as P1 and P2 do. The existing researches only considered the parallel transmitting between links in which the transmitting node pairs are different.

Figure 1. Parallel transmission between two nodes.

Utilizing radio diversity to improve network performance can be considered in both the MAC design and in routing selection. In MAC design, parallel transmission control strategy is a supposed scheme. Packets in the transmission queue are divided to transmit from different links between the transferring node pair according to the link performance. In routing path selecting, a node equipped with multi-radio could be seen as multihosts and which is called layer-2 routing. In this paper, the parallel strategy is considered in MAC design.

3.2.  Parallel Transmission Adaptive Routing Metric

Mesh routing metrics such as ETX [10], ETT, and WCETT [5] are mostly link characterized. A unicast routing is to select a path formed by several links which have the best performance. Thus the selection is on the link instead of on the node. The attention should be focused on the parallelized links when parallel transmission occurs. Since we could get performance of each link, one unique metric should be integrated to character quality of the parallel transmission links. Both the cost and time decreasing caused by parallelization should be considered. A routing metric adaptive parallel transmission achieving by mathematics analyzing is presented latter in section 5.

4.  Parallel Transmission System

4.1.  Parallel Transmission System Model

Figure 2 shows the model of parallel transmission. The left part is the protocol stack. Parallel transmission mechanism is implemented at the link layer called parallel-adaptive MAC. It does the collaboration of multiple interfaces and exposes a virtual MAC address in place of the multiple physical MAC address. Thus, from the application perspective it operates as if there is only a single wireless network interface.

The parallel-adaptive MAC includes three components: control module (V-MAC), selection module, and schedule module. Selection module selects the right interfaces for each flow using a localized algorithm. Schedule module will transmit packets using these selected interfaces. V-MAC is designed to do the unification work such as exposes the virtual MAC address to the upper layer. Since the transmission mode is changed, transmission quality between two nodes has been motivated. A parallel-adaptive metric is proposed in routing layer.

Figure 2. Parallel Transmission System Model.

Figure 3. A transmission example.

For each node, a virtual MAC address is assigned, otherwise, each NIC has its real physical address. When node discovers a neighbor, not only the virtual address of this neighbor should be known, but also the real address of the interface. As seen in Figure 3, there’s two links (Link 1 & Link 2) between node N1 and N2. We use the following format to character Link 1:

(IdN1, IdRadio1)-(IdN2, IdRadio2)

IdNi denotes the id of node Ni. virtual MAC address could be used here. IdRadio(i) figures the real physical address of which radio is linked.

In this paper, link metric is proposed to character the quality of link. Thus, each network interface will provide a link list which includes all links using this interface. Table 1 describes each element of this data structure. Meanwhile, we call it Mac Metric (M_Metric).

As described above, (Idnode, IdNIC) could character the information of both node and interface. Link Metric is used to character the quality of this link. There’re many types of metrics have been researched, such as ETX, etc. ETT [5] is proposed to fit multi-radio system, thus it is used to characterize link metric in this paper.

(2)

S is the size of packet and B is the bandwidth of this link.

M_Metric of each NIC is input to Selection Module. When a link is selected, the link Status filed in the M_Metric of it will be updated to 1 (1 indicates selected and 0 unselected). After selecting completes, the V-MAC exposes a single virtual MAC address in place of the selected multiple physical MAC addresses used by the wireless Network Interface Cards (NICs).

4.2.  Parallel Transmission Scheduling

As described above, Selection Module and Scheduling Module will determine which interfaces to choose for parallel transmission and how to schedule them.

1) Localized Selecting Algorithm When a transmission occurs on node u, it must know which radios to transmit these packets firstly. A localized selecting algorithm is provided here based on the quality of wireless links. M_Metric of each link is INPUT of this algorithm. While selecting ends, it gives a structure (SUM-MAC) which is the OUTPUT of this algorithm. SUM-MAC should indicate the information of selected radios.

The basic idea for this selecting algorithm can be sketched below. NIC with the best link-metric for each link is selected first. Then the algorithm will select certain NICs which have the similar link quality with the best. And is a common-sense value. The selected NICs are added to SUM-MAC and the field of Link Status is set to 1. Finally a combining work is done for each link and SUM-MAC of node u is outputted.

Note that Algorithm 1 is a localized one with each node u running a copy and making its decisions independently. As we know, links of wireless environments are asymmetric due to interference of neighbor nodes, background noise and so on. E.g. as shown in Figure 3, the quality of transmission from node N1 to node N2 with link 1 may be different from transmission from node N2 to node N1 with link1. Thus, the selecting results between transmission (N1->N2) and transmission (N2->N1) are different. It is suitable for asymmetry of wireless environments.

2) Two Scheduling Algorithm After certain radios are selected, schedule module assigns packets transmitted to these radios for transmitting. INPUT of scheduling is SUM_MAC and OUTPUT is SCH_D which is packet queue for transmitting. Two kinds of scheduling algorithms are implemented here.

A SCH_D (u) for each transmission m will be gotten by this algorithm. Packets are copied and sent on each selected NIC in SUM_MAC. At the receiver, Virtual MAC handles data transmissions and retransmissions. Since the packets are copy-sent, loss resilience is improved here. For example, there’re two links are selected between two nodes. We assume that loss rate of them are p1, p2 separately. Packets are lost only if link 1 and link 2 all missed. The probability is.

Multi-transmission with one packet will affect the performance of network when it is with heavy load. Another algorithm called partition-based scheduling is present as follows. It aims to improve throughput of network.

The basic idea of Algorithm 2.2 is sketched below. Node u, the source, first gets the neighbor node which the packets will be transmitted to. For each packet, it is transmitted by the selected NICs with a random probability. This probability is denoted as follows. We assume that there’re t links are selected and the metric of them are ETT1, ETT2…ETTt. The probability of each link is:

(3)

This probability is obtained by these rules:

(4)

It is possible that there is only one best link, in this case, it will be a one-link selected. For each packet i, it will be randomly transmitted on NIC k with a probability of probk, which is computed by (2). For example, if two radios are selected, and link metric of them (ETT) are 0.2s and 0.4s separately. Then, prob1 =ETT2/(ETT1+ ETT2) =2/3, and prob2 = ETT1/(ETT1+ETT2) =1/3.

Some other link metric could also be used here. However, it must be short-term and propagated localized. In Wireless Mesh Network, the locations of nodes are fixed, and therefore the set of potential neighbors (adjacencies) of a node that are within its transmission range is also static. On the other hand, the quality of a wireless channel between adjacent nodes varies frequently because of various factors such as external interference, channel fading, and inclement weather. So our parallel-transmission is based on a neighbor pair. In other words, it is just one hop, and our link metric is short-term based.

5.  Parallel Adaptive Routing Metric

As stated in [11] the metric “hop count” cannot work well in static wireless networks. Meanwhile, wireless link quality characterization is a hard problem because of the variability of wireless network. As a result, forecasting more veracious information of the wireless network performance is kernel part of the routing design.

However, as the main work of this paper focuses on parallel-transmission, designing a new link metric for wireless mesh network is not considered here. This part only proposes a parallel-adaptive routing metric which is improved from ETT.

An assumption is made that link 1 and link 2 between the node pair A and B are selected to join the parallel transmission.

As in Parallel-1 Algorithm, packet p will be sent both on link 1 and link 2. Packet will be come first when link has the best ETT. Thus, for Parallel-1 Algorithm, the metric of sending time is calculated as follows:

(5)

While in the previous description of Parallel-2, the packet list is divided into two parts, which will transmit separately. Suppose the expected transmission time is ETT1 on link 1 and ETT2 on link 2, and there are n packets, each of size S0, waiting to be sent. As described above, the number of packets transmitted on link i will be:

(6)

Then the sending time will be:

(7)

Now, let us denote the constant cost of packet scheduling is T0. The routing metric Cost Time (CT) is defined as follows:

(8)

Equation (8) gives a routing metric which is adapting to our scheduling mechanism for the two parallel scheduling. It works well for routing protocol.

6.  Simulation Results

The distributed algorithms presented in Section 4 were implemented in ns-2 [17]. The simulation for our protocol proposed in this paper uses the topology creator to randomly create the scenarios. Table 2 gives the default parameter setting used in the simulation study.

Each node is equipped with 5 radios. Two kinds of traffic source are set, one is CBR, and the other is FTP. The source-destination pairs are spread randomly over the network.

Evaluation of the serial algorithm and our 2 parallel scheduling algorithms are investigated. Meanwhile three key performance metrics are evaluated: (1) Throughput – the data packets delivered to the destination generated by the CBR and FTP sources; (2) Delay-the delay jitter above the minimum one-way packet delivery time; (3) Retransmission probability-number of retransmission packets with a certain number of sending packets.

6.1.  Throughput

As described above, 10 pairs of UDP and TCP flows are run in the scenario randomly. We compare the performance of none-parallel scheme (MUP) against our two parallel schemes.

1) Impact on UDP Throughput We now consider the 10 pairs UDP transmissions in the scenario. Each throughput of the 10 pairs is shown in Figure 4. As shown in Figure 4, both the two parallel algorithms improve the throughput in UDP flows. The average throughput over 10 UDP flows for the noneparallel experiments is 2.86Mbps. Meanwhile, our parallel-1 is 3.31Mbps and parallel-2 is 5.44Mbps. The two parallel algorithms constitute improvements of 10% and 90% separately.

Table 2. Basic settings for simulation experiment.

Figure 4. UDP throughput comparison.

Table 3. Average throughput for UDP transmissions.

2) Impact on TCP Throughput We now consider the impact of parallel on TCP transmissions. 10 pairs of TCP transmissions are also tested in the simulation. The results of throughput are shown in Figure 5. Table 4" target="_self"> Table 4 figures the average throughput of the three kinds of transmissions. Noneparallel is 2.48 Mbps, Parallel-1 is 2.89 Mbps and Parallel-2 is 2.80 Mbps. The average throughput of both two parallel algorithms improves by more than 10% to the original scheduling. Compared to UDP flows, it has less impact on TCP flows. It is caused by that performance of TCP flows is influenced by RTT. When the node doesn’t choose the best link to transmit packets, it will cause more delay. It increases the value of RTT. Thus, TCP performance decreases. However, the whole capacity enhances.

Figure 5. TCP throughput comparison.

Table 4. Average throughput for TCP transmissions.

6.2.  Delay Analysis

Many applications such as VoIP and video streaming require a relatively low packet delivery delay not exceeding 100-150 ms [18,19]. Here, we investigate all the flows described above. In other words, both the TCP transmissions and UPD transmissions are calculated here. To simply analysis, retransmissions are neglected, and only the one-way packet delivery delay is captured.

Figure 6 shows the one way delay distribution of our simulations. Compared to none-parallel scheduling, parallel-1 delivers packets with a lot smaller delay because it is able to recover most corrupt frame retransmission to the neighbor, and meanwhile, it could improve the bandwidth of the network. Parallel-2 could also improve the throughput of the network. Since parallel-2 uses some devices which have more packet loss probability, it may impact the delay. However, it still has 5% more packets delivered than none-parallel scheme below 1ms. However, about 25% of the packets in the two parallel scheduling mechanisms are delivered with a significantly higher delay than none-parallel. Nonetheless, our parallel scheduling is able to deliver 95% of the packets within a delay of 45 ms, which is well below the delay bound of 150 ms that can be tolerated by telephony and video applications.

6.3.  Retransmission Probability Analysis

To characterize the loss probability of each link by higher layer, we summarize the number of retransmission packets. The comparison of 3 scheduling is shown in Figure 7. This is based that we have limited the number of packets sending. We set the maxpkts_ to 1500. That means the application only procedure 1500 packets. And the sum of retransmission packets for all flows is calculated. We could see that the none-parallel and parallel-2 schedule almost have the same number of retransmission packets, because parallel-2 only choose these NICs which have the similar loss probability as the best one. However, as multi-send of packets by parallel-1, it has the less retransmission numbers than others.

Figure 6. Delivery delay comparison.

7.  Conclusions

In this paper we present a new usage of multi-radio diversity in wireless mesh network. A new paralleltransmission model is proposed which makes packets transmit on different radios simultaneously. Based on this model, a radio selecting algorithm and two distributed scheduling algorithms are presented. We also provide an adaptive routing metric based on our paralleltransmission, which can fully take advantage of the diversity of multi-radio.

Simulation results show that our new scheme could enhance the performance of network both in throughput and delivery delay. And also the whole retransmission probability decreases.

The main work of this paper is to provide a new transmission scheme. There’re still many works to be done in the future. For example, some scheduling optimization based on multi-hop could be further investigated, which will require the analysis of behavior of flows.

8.  Acknowledgements

The research is supported by USTC Innovation Foundation for Graduate Students 2007 under Grant No. KD2007048 and Natural Science Foundation of AnHui under Grant No. KJ2007A053.

We are grateful to Dr. Vivy Suhendra, who has made a lot of help in this paper. We are also grateful to anonymous reviews for their invaluable and constructive comments and suggestions.

9.  References

[1]       R. Bruno, M. Conti, and E. Gregori, “Mesh networks: Commodity multihop ad hoc networks”, IEEE Communications Magazine, Vol. 43, No. 3, pp. 123-131, March 2005.

[2]       I. F. Akyildiz, X. D. Wang, and W. L. Wang, “Wireless mesh networks: A survey,” Computer Networks and ISDN Systems, Vol. 47, No. 4, pp. 445-487, March 15, 2005.

[3]       P. Bahl, A. Adya, J. Padhye, and A. Wolman, “Reconsidering wireless systems with multiple radios,” ACM SIGCOMM Computer Communication Review, Vol. 34, pp. 39-46, October 2004.

[4]       A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. D. Zhou, “A multi-radio unification protocol for IEEE 802.11 wireless networks,” Proceedings of the First International Conference on Broadband Networks (BROADNETS’04), pp.344-354, October 25-29, 2004.

[5]       R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks,” Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom’04), pp. 114-128.

[6]       A. A. Pirzada, M. Portmann, and J. Indulsk, “Evaluation of multi-radio extensions to AODV for wireless mesh networks,” Proceedings of the International Workshop on Mobility Management and Wireless Access (MOBIWAC 2006), pp. 45-51.

[7]       M. Kodialam and T. Nandagopal, “Characterizing the capacity region in multi-radio multi-channel wireless mesh networks,” Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (Mobicom’05), pp.73-87, September 2005.

[8]       M. Alicherry, R. Bhatia, and L. Li, “Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks,” Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (Mobicom’05), pp. 58-72, September 2005.

[9]       A. Miu, H. Balakrishnan, and C. E. Koksal, “Improving loss resilience with multi-radio diversity in wireless network,” Proceedings of the 11th Annual International Conference on Mobile and Networking (Mobicom’05), September 2005.

[10]    S. Douglas, J. De Couto, D. Aguayo, J. Bicket, and R. Morris, “A high-throughput path metric for multi-hop wireless network,” Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (Mobicom’03), pp. 134-146, San Diego, California, September 2003.

[11]    R. Draves, J. Padhye, and B. Zill, “Comparison of routing metrics for static multi-hop wireless networks”, Proceedings of the Sigcomm’04, 2004.

[12]    Y. H. Kim and J. B. Sunk, “Performance improvement for best-effort traffic of IEEE 802.11e QoS MAC in mobile ad hoc networks,” Proceedings of WiCOM 2006.

[13]    P. Kyasanur and N. H. Vaidya, “Routing and interface assignment in multi-channel multi-interface wireless networks,” Proceedings of Wireless Communications and Networking Conference 2005, Vol. 4, pp. 2051-2056, March 2005.

[14]    A. P. Subramanian, H. Gupta, and S. R. Das, “Minimum interface channel assignment in multi-radio wireless mesh networks,” Proceedings of the Fourth Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON 2007), June 2007.

[15]    Trops Network: Assignment of channels to links of nodes within a mesh network.

[16]    B. J. Ko, V. Misra, J. Padhye, and D. Rubenstein, “Distributed channel assignment in multi-radio 802.11 mesh networks,” Proceedings of IEEE WCNC 2007, Hong Kong, China, March 2007.

[17]    NS2, http://www.isi.edu/nsnam/ns/.

[18]    A. Kopsel and A. Woliz, “Voice transmission in an IEEE 802.11 WLAN based access network,” in Proceeding of ACM WoWMoM (Rome, Italy), pp. 23-32, July 2001.

[19]    S. W. Lu, Thyagarajan, and V. Bharghavan, “Design and analysis of an algorithm for fair service in error-prone wireless channels,” Wireless Network, Vol. 6, pp. 323- 343, 2000.

[20]    Bel Air Networks, http://www.belairnetworks.com/.