Ad Hoc Wireless Network: Operating Principles

Get Complete Project Material File(s) Now! »

Chapter 2: Background

Introduction to Ad Hoc Networks

A wireless mobile ad hoc network consists of mobile nodes that are interconnected by wireless- multi- hop communication paths. These ad hoc wireless networks are self-creating, self-organizing, and self-administering. Figure 2.1 depicts a sample mobile ad hoc network.
These mobile ad hoc networks offer unique benefits and versatility for certain environments and applications. With no prerequisites of fixed infrastructure or base stations, they can be created and used anytime, anywhere. Such networks could be intrinsically fault-resilient, for they do not operate under the limitations of a fixed topology. Since all nodes are allowed to be mobile, the topology of such networks is necessarily time varying. The addition and deletion of nodes occur only by interactions with other nodes. Thus these types of networks offer many advantages where setting up wired- line networks is not feasible. Such advantages attracted immediate interest in its early use among military, police, and rescue agencies, and especially under disorganized or hostile environments, including isolated scenes of natural disaster and armed conflict. Recently, home or small-office networking and collaborative computing with laptop computers in a small area (e.g., a conference or classroom, single building, convention center, etc.) have emerged as other major areas of application. In addition, people have recognized from the beginning that ad hoc networking has an obvious, potential use in all the traditional areas of interest for mobile computing.
This concept of mobile ad hoc networking emerged as an attempt to extend the services provided by the traditional Internet to the wireless mobile environment. All current works, as well as our research here, consider the ad hoc networks as a wireless extension to the Internet, based on the ubiquitous IP networking mechanisms and protocols. Today’s Internet possesses an essentially static infrastructure where network elements are interconnected over traditional wire- line technology, and these elements, especially the elements that provide the routing or switching functions, do not move. In a mobile ad hoc network, by definition, all the network elements move. As a result, numerous more stringent challenges must be overcome to realize the practical benefits of ad hoc networking.
In addition, the mobility of nodes imposes limitations on their power capacity, and hence, on their transmission range. These nodes must often also satisfy stringent weight limitations for portability. Further these mobile hosts are no longer just end systems; they are also required to relay packets generated by other nodes, hence each node must also be able to function as a router. As the nodes move in and out of range with respect to each other, including those that are operating as routers, the resulting topology needs to be communicated to all other nodes as appropriate to maintain the connectivity information. In accommodating the communication needs of the user applications, the limited bandwidth of wireless channels and their generally- hostile transmission characteristics, impose additional constraints on how much administrative and control information may be exchanged, and how often. Ensuring effective routing is one of the major challenges for ad hoc networking.
As these mobile ad hoc networks are being increasingly considered for more and more complex applications, the various Quality of Service (QoS) attributes for these applications must also be satisfied as a set of pre-determined service requirements. In addition, because of the increasing use of the ad hoc networks for military/police use, and also due to the increasing commercial applications being envisioned to be supported on these type of networks, various security issues also need to be addressed. These issues, however, are out of the scope of this thesis.
The organization of the rest of the chapter is as follows. Section 2.2 presents a brief review of the operating principles of an ad hoc network and introduces some networking concepts pertinent to routing and QoS. The general issue of routing in mobile ad hoc networks is reviewed in Section 2.3. This section also cites some of the existing routing protocols in mobile ad hoc networks, with special emphasis on the DSDV (Destination Sequence Distance Vector) algorithm, as this algorithm is the basis of our research.

Ad Hoc Wireless Network: Operating Principles

To illustrate the general operating principles of a mobile ad hoc network, consider figure 2.2, which depicts the peer-level, multi- hop representation of a sample ad hoc network. Here, mobile node A communicates directly (single-hop) with another such node B whenever a radio channel with adequate propagation characteristics is available between them. Otherwise, multi- hop communication is necessary where one or more intermediate nodes must act as a relay (router) between the communicating nodes. For example, there is no direct radio channel (sho wn by the lines) between A and C or between A and E as shown in figure 2.2. Nodes B and D must serve as intermediate routers for communication between A and C, and between A and E, respectively. Thus, a distinguishing feature of ad hoc networks is that all nodes must be able to function as routers on demand along with acting as source and destination for packets. To prevent packets from traversing infinitely long paths, an obvious essential requirement for choosing a path is that it must be loop-free. And this loop- free path between a pair of nodes is called a route.
An ad hoc network begins with at least two nodes, broadcasting their presence (beaconing) with their respective address information. If node A is able to establish direct communication with node B as in figure 2.2, verified by exchanging suitable control messages between them, they both update their routing tables. When a third node C joins the network with its beacon signal, two scenarios are possible. The first is where both A and B determine that single-hop communication with C is feasible. The second is where only one of the nodes, say B, recognizes the beacon signal from C and establishes direct communication with C. The distinct topology updates, consisting of both address and route updates, are made available in all three nodes immediately afterwards. In the first case, all routes are direct. For the other, the route update first happens between B and C, then between B and A, and then again between B and C, confirming the mutual reachability between A and C via B.
As the node moves, it may cause the reachability relations to change in time, requiring route updates. Assume that, for some reason, the link between B and C is no longer available as shown in figure 2.3. Nodes A and C are still reachable from each other, although this time only via nodes D and E. Equivalently, the original loop- free route  A « B « C  is now replaced by the new loop- free route  A « D « E « C  . All five nodes in the network are required to update their routing tables appropriately to reflect this topology change, which will be first detected by nodes B and C, then communicated to A, E, and D.
This reachability relation among the nodes may also change for various reasons. For example, a node may wander too far out of range, its battery may be depleted, or it may just suffer from software or hardware failure. As more nodes join the network, or some of the existing nodes leave, the topology updates become more numerous, complex, and usually, more frequent, thus diminishing the network resources available for exchanging user information (i.e., data).
Finding a loop- free path between a source-destination pair may therefore become impossible if the changes in network topology occur too frequently. Too frequently here means that there may not be enough time to propagate to all the pertinent nodes the change s arising from the last change in network topology. Thus the ability to communicate degrades with increasing mobility and as a result the knowledge of the network topology becomes increasingly inconsistent. A network is combinatorially stable if, and only if, the topology changes occur slow enough to allow successful propagation of all topology updates as necessary or if the routing algorithm is efficient enough to propagate the changes in the network before the next change occurs. Clearly, combinatorial stability is determined not only by the connectivity properties of the networks, but also by the efficiency of the routing protocol in use and the instantaneous computational capacity of the nodes, among others. Combinatorial stability thus forms an essential consideration for attaining efficient routing objectives in an ad hoc network.
In the next section, we list some of the characteristics that an efficient routing algorithm for an ad hoc network must posses in order to increase the throughput of the network with the least amount of overhead.

Desirable properties of an efficient routing algorithm

Many routing protocols for ad hoc networks have been proposed so far, each one offering some advantage over the previous approach. But in general, there are some common desirable properties that any routing protocol for an ad hoc network should possess as mentioned in [30]. These are:

• Loop free: Presence of loops in the path from the source to the destination result in inefficient routing. In the worst-case situation, the packets may keep traversing the loop indefinitely and never reach their destination.
• Distributed control: In a centralized routing scheme, one node stores all the topological information and makes all routing decisions; therefore, it is neither robust, nor scalable. The central router can be a single point of failure; also, the network in the vicinity of the central router may get congested with routing queries and responses.
• Fast routing: The quicker the routing decisions are made, the sooner the packets can be routed towards the destination, as the probability that the packets take the chosen route before it gets disrupted because of node mobility is quite high.
• Localized reaction to topological changes: Topological changes in one part of the network should lead to minimal changes in routing strategy in other distant parts of the network. This will keep the routing update overheads in check and make the algorithm scalable.
• Multiplicity of routes: Even if node mobility results in disruption of some routes, other routes should be ava ilable for packet delivery.
• Power efficient: A routing protocol should be power efficient. That is the protocol should distribute the load; otherwise shut-off nodes may cause partitioned topologies that may result in inaccessible routes.
• Secure: A rout ing protocol should be secure. We need authentication for communicating nodes, non-repudiation and encryption for private networking to avoid routing deceptions.
• QoS aware: A routing protocol should also be aware of Quality of Service. It should know about the delay and throughput for a source destination pair, and must be able to verify its longevity so that a real-time application may rely on it.

Routing in Mobile Ad Hoc Networks

Now that we have a general overview of an ad hoc network and its operating principles, we move on to take a deeper look into the various approaches for routing in ad hoc networks proposed so far.
Several approaches toward routing in ad hoc networks have been proposed with the goal of achieving efficient routing. And with the ever-changing topology, an intuitive approach of routing messages could be that the sender of the message specifies the exact path that the message should take from the sender to the receiver. But this assumes that the sender knows the entire topology of the network, which is not quite a realistic assumption. Another alternative could be to forward the message to a neighbor in the general direction of the destination, and the neighbor then makes a similar decision regarding how to route the message.
Based on the above- mentioned approaches, many routing algorithms have been put forward. And as we have mentioned earlier, most of the routing algorithms proposed so far for ad hoc networks have been adapted from the routing techniques employed in wire-line networks that have fixed network topology. But the routing algorithms devised for wire- line networks are based on the determination of the shortest path between the source and the destination. Hence these routing algorithms cannot be applied to ad hoc networks without modification as the network topology in ad hoc networks is always in a state of flux with changes in graph topology in one region of the network altering the shortest path between several pairs of nodes. Also, in ad hoc networks, this information takes time to propagate to other nodes in the system. If the topology information is not updated promptly, the nodes may continue to route messages based on the outdated information, which may lead to packet losses.

CHAPTER 1: INTRODUCTION 
1.1 Motivation
1.2 Thesis Organization
1.3 Thesis Contributions
1.4 Chapter Summary
CHAPTER 2: BACKGROUND 
2.1 Introduction to Ad Hoc Networks
2.2 Ad Hoc Wireless Network: Operating Principles
2.3 Routing in Mobile Ad Hoc Networks
2.4 Chapter Summary
CHAPTER 3. MOBILITY PATTERNS AND HISTORY 
3.1 Need for Characterization of Mobility
3.2 Mobility Patterns
3.3 Location Prediction
3.4 History
3.5 Chapter Summary
CHAPTER 4. MOBILITY PATTERN ADAPTIVE ROUTING PROTOCOL 
4.1 Review of DSDV
4.2 Mobility Pattern Aware Routing Protocol
4.3 Provision for Imposing QoS Routing (future work)
4.4 Chapter Summary
CHAPTER 5. SIMULATION METHODOLOGY AND PERFORMANCE EVALUATION 
5.1 Simulation Environment
5.2 Simulation Methodology
5.3 Verification and Validation
5.4 Results and Analysis
5.5 Additional Results – Accuracy of Location Prediction
5.6 Chapter Summary
CHAPTER 6: CONCLUSION AND FUTURE WORK 
6.1 Conclusion
6.2 Future Work
REFERENCES 
APPENDIX 
GET THE COMPLETE PROJECT
Mobility Pattern Aware Routing in Mobile Ad Hoc Networks