20-09-2016, 03:35 PM
1455436673-journal.docx (Size: 736.56 KB / Downloads: 7)
Abstract
Hybrid wireless networks combining the advantages of both mobile ad-hoc networks and infrastructure wireless networks. An efficient data routing protocol is important in such networks for high network capacity and scalability.However, most routing protocols for these networks simply combine the ad-hoc transmission mode with the cellular transmission mode, which inherits the drawbacks of ad-hoc transmission. This paper presents a concept of improving the capacity of hybrid wireless network using by multi hop routing protocol. To take full advantage of the widespread base stations, DTR divides a message data stream into segments and transmits the segments in a distributed manner. It makes full spatial reuse of a system via its high speed ad-hoc interface and alleviates mobile gateway congestion via its cellular interface. Furthermore, sending segments to a number of base stations simultaneously increases throughput and makes full use of widespread base stations. In addition, DTR significantly reduces overhead due to short path lengths and the elimination of route discovery and maintenance. DTR also has a congestion control algorithm to avoid overloading base stations. Theoretical analysis and simulation results show the superiority of DTR in comparison with other routing protocols in terms of throughput capacity, scalability and mobility resilience. The results also show the effectiveness of the congestion control algorithm in balancing the load between base stations
INTRODUCTION
Over the past few years, wireless networks including infrastructure wireless networks and mobile ad-hoc networks (MANETs) have attracted significant research interest. The growing desire to increase wireless network capacity for high performance applications has stimulated the development of hybrid wireless networks [1–6]. A hybrid wireless network consists of both an infrastructure wireless network and a mobile ad-hoc network. Wireless devices such as smart-phones, tablets and laptops, have both an infrastructure interface and an adhoc interface. As the number of such devices has been increasing sharply in recent years, a hybrid transmission structure will be widely used in the near future. Such a structure synergistically combines the inherent advantages and overcome the disadvantages of the infrastructure wireless networks and mobile ad-hoc networks.
In a mobile ad-hoc network, with the absence of a central control infrastructure, data is routed to its destination through the intermediate nodes in a multi-hop manner. The multi-hop routing needs on-demand route discovery or route maintenance [7–10]. Since the messages are transmitted in wireless channels and through dynamic routing paths, mobile ad-hoc networks are not as reliable as infrastructure wireless networks. Furthermore, because of the multi-hop transmission feature, mobile ad-hoc networks are only suitable for local area data transmission.A hybrid wireless network synergistically combines an infrastructure wireless network and a mobile adhoc network to leverage their advantages and overcome their shortcomings, and finally increases the throughput capacity of a wide-area wireless network. A routing protocol is a critical component that affects the throughput capacity of a wireless network in data transmission. Most current routing protocols in hybrid wireless networks [1, 5, 6, 12–18] simply combine the cellular transmission mode (i.e. BS transmission mode) in infrastructure wireless networks and the ad-hoc transmission mode in mobile ad-hoc networks [8, 9, 7]. That is, as shown in Figure 1 (a), the protocols use the multi-hop routing to forward a message to the mobile gateway nodes that are closest to the BSes or have the highest bandwidth to the BSes. The bandwidth of a channel is the maximum throughput (i.e., transmission rate in bits/s) that can be achieved. The mobile gateway nodes then forward the messages to the BSes, functioning as bridges to connect the ad-hoc network and the infrastructure network.
However, direct combination of the two transmission modes inherits the following problems that are rooted in the ad-hoc transmission mode.
• High overhead. Route discovery and maintenance incur high overhead. The wireless random access medium access control (MAC) required in mobile ad-hoc networks, which utilizes control handshaking and a backoff mechanism, further increases overhead.
• Hot spots. The mobile gateway nodes can easily become hot spots. The RTS-CTS random access, in which most traffic goes through the same gateway, and the flooding employed in mobile ad-hoc routing to discover routes
may exacerbate the hot spot problem. In addition, mobile nodes only use the channel resources in their route direction, which may generate hot spots while leave resources in other directions under-utilized. Hot spots lead to low transmission rates, severe network congestion, and high data dropping rates.
• Low reliability. Dynamic and long routing paths lead to unreliable routing. Noise interference and neighbor interference during the multi-hop transmission process cause a high data drop rate. Long routing paths increase the probability of the occurrence of path breakdown due to the highly dynamic nature of wireless ad-hoc networks.
These problems become an obstacle in achieving high throughput capacity and scalability in hybrid wireless networks. Considering the widespread BSes, the mobile nodes have a high probability of encountering a BS while moving. Taking advantage of this feature, we propose a Distributed Three-hop Data Routing protocol (DTR). In DTR, as shown in Figure 1 (b), a source node divides a message stream into a number of segments. Each segment is sent to a neighbor mobile node. Based on the QoS requirement, these mobile relay nodes choose between direct transmission or relay transmission to the BS. In relay transmission, a segment is forwarded to another mobile node with higher capacity to a BS than the current node. In direct transmission, a segment is directly forwarded to a BS. In the infrastructure, the segments are rearranged in their original order and sent to the destination. The number of routing hops in DTR is confined to three, including at most two hops in the ad-hoc transmission mode and one hop in the cellular transmission mode. To overcome the aforementioned shortcomings, DTR tries to limit the number of hops. The first hop forwarding distributes the segments of a message in different directions to fully utilize the resources, and the possible second hop forwarding ensures the high capacity of the forwarder. DTR also has a congestioncontrol algorithm to balance the traffic load between the nearby BSes in order to avoid traffic congestion at BSes.
Using self-adaptive and distributed routing with highspeed and short-path ad-hoc transmission, DTR significantly increases the throughput capacity and scalability of hybrid wireless networks by overcoming the three shortcomings of the previous routing algorithms. It has the following features:
• Low overhead. It eliminates overhead caused by route discovery and maintenance in the ad-hoc transmission mode, especially in a dynamic environment.
• Hot spot reduction. It alleviates traffic congestion at mobile gateway nodes while makes full use of channel resources through a distributed multi-path relay.
• High reliability. Because of its small hop path length with a short physical distance in each step, it alleviates noise and neighbor interference and avoids the adverse effect of route breakdown during data transmission. Thus, it reduces the packet drop rate and makes full use of spacial reuse, in which several source and destination nodes can communicate simultaneously without interference.
RELATED WORK
In inter-cell transmission [1, 5, 6], a message is forwarded via the ad-hoc interface to the gateway mobile node that is closest to or has the highest uplink transmission bandwidth to a BS. The gateway mobile node then forwards the message to the BS using the cellular interface. However, most of these routing protocols simply combine routing schemes in ad-hoc networks and infrastructure networks, hence inherit the drawbacks of the ad-hoc transmission mode as explained previously.
DTR is similar to the Two-hop transmission protocol [19] in terms of the elimination of route maintenance and the limited number of hops in routing. In Two-hop, when a node’s bandwidth to a BS is larger than that of each neighbor, it directly sends a message to the BS. Otherwise, it chooses a neighbor with a higher channel and sends a message to it, which further forwards the message to the BS. DTR is different from Two-hop in three aspects. First, Two-hop only considers the node transmission within a single cell, while DTR can also deal with inter-cell transmission, which is more challenging and more common than intra-cell communication in the real world. Second, DTR uses distributed transmission involving multiple cells, which makes full use of system resources and dynamically balances the traffic load between neighboring cells. In contrast, Two-hop employs single-path transmission.
There are other methods proposed to improve routing performance in hybrid wireless networks. Wu et al. [3] proposed using ad-hoc relay stations to dynamically relay traffic from one cell to another in order to avoid traffic congestion in BSes. Li et al. [20] surveyed a number of multi-hop cellular network (MCN) architectures in literature, and compared and discussed methods to reduce the cost of deployment for MCNs. The work in [21] investigates how to allocate the bandwidth to users to improve the performance of hybrid wireless networks. Thulasiramanet al. [22] further considered the wireless interference in optimizing the resource allocation in hybrid wireless networks. The work in [23] proposes a coalitional game theory based cooperative packet delivery scheme in hybrid wireless networks. There are also some works [24–26] that study radio frequency allocation for direction transmission and relay transmission in hybrid wireless networks. These works are orthogonal to our study in this paper and can be incorporated into DTR to further enhance its performance. The throughput capacity of the hybrid wireless network under different settings has also been an active research topic in the hybrid wireless network. The works in [17, 27] have studied the throughput of hybrid network with n nodes and m stations. Liu et al. [28] theoretically studied the capacity of hybrid wireless networks under an one-dimensional network topology and a twodimensional strip topology. Wang et al. [29] studied the multicast throughput of hybrid wireless networks and designed an optimal multicast strategy based on deduced throughput.
DISTRIBUTED THREE-HOP ROUTING PROTOCOL
Assumption and Overview
Since BSes are connected with a wired backbone, we assume that there are no bandwidth and power constraints on transmissions between BSes. We use intermediate nodes to denote relay nodes that function as gateways connecting an infrastructure wireless network and a mobile ad-hoc network. We assume every mobile node is dual-mode; that is, it has ad-hoc network interface such as a WLAN radio interface and infrastructure network interface such as a 3G cellular interface.
DTR aims to shift the routing burden from the adhoc network to the infrastructure network by taking advantage of widespread base stations in a hybrid wireless network. Rather than using one multi-hop path to forward a message to one BS, DTR uses at most two hops to relay the segments of a message to different BSes in a distributed manner, and relies on BSes to combine the segments. Figure 2 demonstrates the process of DTR in a hybrid wireless network. We simplify the routings in the infrastructure network for clarity. As shown in the figure, when a source node wants to transmit a message stream to a destination node, it divides the message stream into a number of partial streams called segments and transmits each segment to a neighbor node. Upon receiving a segment from the source node, a neighbor node locally decides between direct transmission and relay transmission based on the QoS requirement of the application. The neighbor nodes forward these segments in a distributed manner to nearby BSes. Relying on the infrastructure network routing, the BSes further transmit the segments to the BS where the destination node resides. The final BS rearranges the segments into the original order and forwards the segments to the destination. It uses the cellular IP transmission method [30] to send segments to the destination if the destination moves to another BS during segment transmission.
Our DTR algorithm avoids the shortcomings of adhoc transmission in the previous routing algorithms that directly combine an ad-hoc transmission mode and a cellular transmission mode. Rather than using the multihop ad-hoc transmission, DTR uses two hop forwarding by relying on node movement and widespread base stations. All other aspects remain the same as those in the previous routing algorithms (including the interaction with the TCP layer). DTR works on the Internet layer. It receives packets from the TCP layer and routes it to the destination node, where DTR forwards the packet to the TCP layer.
The data routing process in DTR can be divided into two steps: uplink from a source node to the first BS and downlink from the final BS to the data’s destination. Critical problems that need to be solved include how a source node or relay node chooses nodes for efficient segment forwarding, and how to ensure that the final BS sends segments in the right order so that a destination node receives the correct data. Also, since traffic is not evenly distributed in the network, how to avoid overloading BSes is another problem. Below, Section 3.2 will present the details for forwarding node selection in uplink transmission and Section 3.3 will present the segment structure that helps ensure the correct final order of segments in a message, and DTR’s strategy for downlink transmission. Section 3.4 will present the congestion control algorithm for balancing a load between BSes.
Uplink Data Routing
A long routing path will lead to high overhead, hot spots and low reliability. Thus, DTR tries to limit the path length. It uses one hop to forward the segments of a message in a distributed manner and uses another hop to find high-capacity forwarder for high performance routing. As a result, DTR limits the path length of uplink routing to two hops in order to avoid the problems of long-path multi-hop routing in the ad-hoc networks. Specifically, in the uplink routing, a source node initially divides its message stream into a number of segments, then transmits the segments to its neighbor nodes. The neighbor nodes forward segments to BSes, which will forward the segments to the BS where the destination resides.Below, we first explain how to define capacity, then introduce the way for a node to collect the capacity information from its neighbors, and finally present the details of the DTR routing algorithm.
Different applications may have different QoS requirements, such as efficiency, throughput, and routing speed. For example, delay-tolerant applications (e.g. voice mail, e-mail and text messaging) do not necessarily need fast real-time transmission and may make throughput the highest consideration to ensure successful data transmission. Some applications may take high mobility as their priority to avoid hot spots and blank spots. Hot spots are areas where BS channels are congested, while blank spots are areas without signals or with very weak signals. High-mobility nodes can quickly move out of a hot spot or blank spot and enter a cell with high bandwidth to a BS, thus providing efficient data transmission. Throughput can be measured by bandwidth, mobility can be measured by the speed of node movement, and routing speed can be measured by the speed of data forwarding. Bandwidth can be estimated using the nonintrusive technique proposed in [31]. In this work, we take throughput and routing speed as examples for the QoS requirement. We use a bandwidth/queue metric to reflect node capacity in throughput and fast data forwarding. The metric is the ratio of a node’s channel bandwidth to its message queue size. A larger bandwidth/queue value means higher throughput and message forwarding speed, and vice versa.
When choosing neighbors for data forwarding, a node needs the capacity information (i.e., queue size and bandwidth) of its neighbors. Also, a selected neighbor should have enough storage space for a segment. To keep track of the capacity and storage space of its neighbors, each node periodically exchanges its current capacity and storage information with its neighbors. In the adhoc network component, every node needs to periodically send “hello” messages to identify its neighbors. Taking advantage of this policy, nodes piggyback the capacity and storage information onto the “hello” messages in order to reduce the overhead caused by the information exchanges. If a node’s capacity and storage space are changed after its last “hello” message sending when it receives a segment, it sends its current capacity and storage information to the segment forwarder. Then, the segmentforwarder will choose the highest capacity nodes in its neighbors based on the most updated information.
When a source node sends out message segments, it chooses the neighbors that have enough space for storing a segment, and then chooses neighbors that have the highest capacity. In order to find higher capacity forwarders in a larger neighborhood around the source, each segment receiver further forwards its received segment to its neighbor with the highest capacity. That is, after a neighbor node mi receives a segment from the source, it uses either direct transmission or relay transmission. If the capacity of each of its neighbors is no greater than itself, relay node mi uses direct transmission. Otherwise, it uses relay transmission. In direct transmission, the relay node sends the segment to a BS if it is in a BS’s region. Otherwise, it stores the segment while moving until it enters a BS’s region. In relay transmission, relay node mi chooses its highest-capacity neighbor as the second relay node based on the QoS requirement. The second relay node will use direct transmission to forward the segment directly to a BS. As a result, the number of transmission hops in the ad-hoc network component is confined to no more than two. The small number of hops help to increase the capacity of the network and reduce channel contention in ad-hoc transmission. Algorithm 1 shows the pseudo-code for neighbor node selection and message forwarding in DTR.
Congestion Control in Base Stations Compared to the previous routing algorithms in hybrid wireless networks, DTR can distribute traffic load among mobile nodes more evenly. Though the distributed routing in DTR can distribute traffic load among nearby BSes, if the traffic load is not distributed evenly in the network, some BSes may become overloaded while other BSes remain lightly loaded. We propose a congestion control algorithm to avoid overloading BSes in uplink transmission (e.g., B1, B2 and B3 in Figure 1 (b)) and downlink transmission (e.g., B4 in Figure 1 (b)), respectively.