روش مسیر یابی مرکب برای شبکه های ویژه بی سیم A Combined Routing Method for Wireless Ad Hoc Networks

Abstract— To make ad hoc wireless networks adaptive to different mobility and traffic patterns, this paper proposes an approach to swap from one protocol to another protocol dynamically, while routing continues. By the insertion of a thin new layer, we were able to make each node in the ad hoc wireless network notify each other about the protocol swap. To ensure that routing works efficiently after the protocol swap, we initialized the destination routing protocol’s data structures and reused the previous routing information to build the new routing table. We also tested our approach under different network topologies and traffic patterns in static networks to learn whether the swap was fast and whether the swap incurred too much overhead. We found that the swap latency was related to the nature of the destination protocol and the topology of the network. We also found that the control packet ratio after swap was close to that of the protocol running without swap, which indicates that our method does not incur too much overhead for the swap. I. INTRODUCTION A mobile ad hoc network (MANET) is a collection of moving computers connected by wireless links. By routing packets cooperatively among the nodes, these nodes can communicate with each other without any infrastructure. Thus, ad hoc networks are often proposed for use in emergency situations, such as disaster environments and military con- flicts. It is important that ad hoc networks should react to network topological changes and traffic demands quickly and efficiently, and respect the inherent bandwidth and energy constraints [24]. Several projects compare the performance of different ad hoc routing algorithms [20], [10], [5], [17]. They all found that each routing algorithm can outperform the others in certain conditions, depending on the workload, terrain, network characteristics, or node mobility pattern. Gray et al. [10] compared four different routing algorithms: AODV [25], ODMRP [16], APRL [15] and STARA [11], [12]. The authors used both simulations and real testbed experiments and found that under different wireless network conditions the relative performance was not the same. For example, ODMRP’s message delivery ratio is better than AODV’s ratio outdoors, while AODV has a higher message delivery ratio indoors [10]. Broch et al. [5] compared DSDV, TORA, DSR and AODV. They found that DSDVs routing overhead was almost constant with respect to mobility rate while TORA, DSR and AODVs routing overhead dropped as the mobility rate dropped. Lee et al. [17] compared ODMRP, AMRoute [4], CAMP [8], AMRIS [29], and flooding. They found that “in a mobile scenario, mesh-based protocols (ODMRP) outperformed tree-based protocols (AODV)”, but they also pointed out that ODMRP showed “a trend of rapidly increasing overhead as the number of senders increased”. Nanda [20] compared LAR, MLAR, AODV and AOMDV in extensive simulations in 2D and 3D mobility patterns and found distinct advantages for one protocol over the other in different relative traffic and mobility conditions. Ad hoc wireless network routing protocols are usually divided into two groups: Proactive (Table Driven) and Reactive (On-Demand) routing [26]. Proactive routing protocols compute the routes in advance while reactive routing protocols compute the routes only when necessary. Both have advantages and disadvantages. Thus several hybrid routing protocols have been proposed to combine both proactive and reactive routing modes [13], [21], [23]. The zone routing protocol (ZRP) [13] divides the network into overlapping, variable-size zones. Routing within a zone uses proactive algorithms and routing between zones uses reactive algorithms. There are some other hybrid routing algorithms that combine proactive and reactive routing algorithms, such as HARP [21] and SHARP [23]. To reduce overhead, these hybrid methods group nearby nodes and use proactive routing algorithms within groups and use reactive routing algorithms between groups. Chen et al. [6] proposed adaptive routing using clusters, which improves throughput by up to 80%. Belding-Royer et al. [3] proposed hierarchical protocols to reduce the overhead and gain more scalability. However, since the technique uses higher-level topological information, the route to a destination might not be optimal, and the extra topological information itself requires more memory. Hoebeke et al. [14] proposed an adaptive multimode routing algorithm. The implementation added a statistical component at the network layer: they collected non-local statistics through periodic broadcasting of a hello message to neighbors. Their method improved efficiency by switching to different protocols. To achieve this efficiency, however, they introduced many more components for the routing algorithm, which increased the complexity of the algorithm. A common aspect of previous efforts is to allow the routing algorithm to adapt by combining multiple protocols because it is hard to come up with a routing protocol that is best for all situations. Our approach is to dynamically select one of three existing routing protocols rather than to create a new adaptive routing algorithm. We aim to achieve better performance by dynamically switching to the best protocol according to current wireless network conditions. In this paper we focus on the mechanism for switching protocols, rather than the policy for choosing when to switch. Specifically, we develop and evaluate a mechanism for a network of nodes to switch to a new routing protocol. To simplify our combined method, we assume that we already know these existing protocols’ characteristics, and that some mechanism exists to choose the best routing protocol based on the current network traffic pattern. We could use, for example, Hoebeke’s method to gather statistics about current network traffic, identify the traffic pattern, and then select a proactive or reactive protocol accordingly. In ad hoc networks, each node acts both as a host and a router. We thus use the term “node” instead of “host” or “router”. We also use the two terms “routing algorithm” and “routing protocol” interchangeably. In Section 2, we introduce three different routing algorithms, AODV, ODMRP, and APRL. We describe the differences among these three protocols and compare their performance. We also introduce SWAN, a simulator on which our experiments run. In Section 3, we propose a method to switch among the three routing algorithms and discuss the implementation issues of this approach. In Section 4, we explain our experimental setup; in Section 5 we study the performance of this approach and in Section 6 we discuss the advantages. In Section 7, we summarize and draw conclusions.