1.1 Mobile Ad Hoc Routing Protocols
1.2 Purpose of Study
1.3 Contributions
1.4 Structure of Thesis

           Mobile devices, such as laptop computers, Pocket PCs, cellular phones, etc., are now easily affordable, and are becoming more popular in everyday life [Johnson1994, Johnson1996]. At the same time, network connectivity options for mobile hosts have grown tremendously, as the support for wireless networking products based on radio and infrared has been greatly increased over the past few years.
           With the availability of mobile computing devices, mobile users have a natural tendency to share information between them. Often mobile users want to have a meeting, even though it is not planned in advance and there is no Internet connection available. For instance, there may be situations that employees find themselves together in a meeting room, or friends or business acquaintances may encounter each other in an airport terminal, or some scholars and researchers may meet in a hotel ballroom for a conference or workshop. In those situations, requiring each user to connect to a wide-area network to communicate with each other may not be convenient or practical because of the lack of Internet connectivity or because of the time or cost required for such a connection.
           This thesis aims to design, implement and evaluate an instant messaging application for mobile users in these situations without requiring the users to connect to the Internet. A network of mobile hosts without an infrastructure is known as an ad hoc network [Johnson1996]. According to Johnson [Johnson1994], an ad hoc network is defined as follows:

"An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any centralized administration or standard support services regularly available on the wide-area network to which the hosts may normally be connected."

           In general, a multi-hop routing protocol is needed in a mobile ad hoc network, because two hosts wishing to exchange packets may not be able to communicate directly with each other because they are out of radio range [Johnson1994]. Johnson illustrated a simple ad hoc network of three mobile hosts using wireless network interfaces, as shown in Figure 1.1 [Johnson1994]. Host C is not included within the wireless transmission range of host A, as indicated by the circle around A. Also, host A is not within the wireless transmission range of host C. If A and C want to communicate with each other by exchanging packets, they may ask host B to forward packets for them because host B is within the overlapped wireless transmission range between host A and host C. In any practical ad hoc network, the maximum number of network hops for a packet to travel from one mobile host to another mobile host may be small but is likely to be greater than one as demonstrated in Figure 1.1. In a real ad hoc network, the routing problem may be even more complex than this example shown, because wireless transmission has inherent non-uniform propagation features and any or all of the hosts associated with the network may move at any time [Johnson1994].

1.1 MOBILE AD HOC ROUTING PROTOCOLS

           A conventional way of providing routing in an ad hoc network is to make each mobile host take the role as a router, and apply an existing routing protocol between them [Jubin1987, Perkins1994]. This Section briefly summarizes existing routing protocols devised for mobile ad hoc networks and the reason why we adopt DSR as the routing protocol for our implementation of the instant messaging application.

1.1.1 Reactive vs. Proactive Ad Hoc Routing Protocols

           Most routing protocols in mobile ad hoc networks derive from distance vector or link state algorithms.
           In distance-vector routing, each router maintains a table containing the distance from itself to all possible destinations. Each router periodically transmits this table information to all its neighbor routers, and updates its own table by using the values received from its neighbors. Based on the comparison of the distances obtained from its neighbors for each destination, a router can decide the next hop as the shortest path from itself to the specified destination. When each router has a packet to send to some destination, it simply forwards the packet to the decided next hop router. When the routing table is frequently updated, the algorithm speeds up the convergence to the correct path. However, the overhead in CPU time and network bandwidth for flooding routing updates also increases. Perkins and Bhagwat [Perkins1994] devised a Destination-Sequenced Distance Vector (DSDV) protocol based on the classical Bellman-Ford routing algorithm to apply to mobile ad hoc networks. DSDV also has the feature of the distance-vector protocol in that each node holds a routing table including the next-hop information for each possible destination. Each entry has a sequence number. If a new entry is obtained, the protocol prefers to select the entry having the largest sequence number. If their sequence number is the same, the protocol selects the metric with the lowest value. Each node transmits advertisement packets using increasing sequence numbers [Perkins1994]. A study of performance evaluation on DSDV [Broch1998] shows that DSDV is able to deliver virtually all data packets when each node moves with relatively low speed. However, when the mobility of each node increases, the speed at which the system converges to the correct path decreases [Broch1998].
           While DSDV is a proactive protocol that always tries to maintain the correct information regarding network topology, Ad hoc On-demand Distance Vector (AODV) [Perkins1999] is a reactive protocol to perform Route Discovery only when a new route needs to be found. Thus, AODV does not maintain any routing information nor transmit any periodic advertisement packets for exchanging routing tables. That is, only when two nodes need to communicate with each other, will they forward routing packets to maintain connectivity between the two nodes. Usually, when there is a need for communication between two nodes, each mobile node transmits a local broadcast packet known as a hello message. Routing tables of the nodes within the neighborhood are organized for the optimization of response time to local movements and the support of rapid response time for requests to establish a new route. AODV is similar with the Dynamic Source Routing (DSR) protocol, which will be explained with more details in the following sections, in terms of the nature of on-demand. However, while DSR is based on source routing, AODV is dependent upon dynamically establishing route table entries at intermediate nodes.
           In link state routing, each router has a complete picture of the whole network topology. Each router checks the cost of the link to each of its neighbor routers, and floods periodically updated information to all other routers in the network. After each router receives this updated information of the cost of each link in the network, each router calculates the shortest path to each possible destination. When each router needs to forward a packet to some destination, it transmits the packet to the next hop router based on the best path to the destination acquired from the updated information. The link state routing protocols show high speed of convergence to the correct network picture when the network is changed. However, in general, compared to the distance vector algorithm, this protocol requires more CPU time for computing the complete shortest route to each possible destination, and more network bandwidth for broadcasting the routing updates from each router to all other routers in the whole network. In order to reduce the disadvantage of the link state routing algorithm, one optimized protocol is proposed, called an Optimized Link State Routing (OLSR)[Jacquet2001].
           OLSR is one of protocols using link state routing with a proactive nature, which allows periodic exchange of knowledge of network topology among all the nodes of the network. Because of this proactive nature in OLSR, it has a benefit of knowing the routes immediately when needed. A pure link state routing protocol has the characteristic that all the links with neighbor nodes are declared and are broadcast to the whole network. However, since OLSR is the optimization of the link state routing protocol for an ad hoc network, it uses the reduced size of control packets, declaring only a subset of links with its neighbors who are its multipoint relay selectors, instead of all links. Besides, OLSR minimizes flooding of this control packet by using only the selected nodes, called multipoint relay, to disperse its messages in the network. The multipoint relay is the idea to diminish the flooding of broadcast packets in the network by lessening duplicate retransmission in the same region.
           In addition to the viewpoint categorizing routing protocols in terms of either distance vector or link state routing, routing protocols for ad hoc networks also can be classified as reactive routing protocols versus proactive routing protocols, as mentioned previously [Jacquet2001]. In the reactive routing approach, a routing protocol does not initiate Route Discovery until it is needed. The protocols only attempt to find a route to a destination totally based on demand. Examples of reactive routing protocols for ad hoc networks include AODV [Perkins1999], DSR [Johnson2001, Johnson1999, Maltz2001], ODMRP [Lee2000], and TORA [Park1997]. On the contrary, the proactive routing approach is based on the exchange of knowledge of network topology periodically [Jacquet2001]. The proactive protocols provide a needed route instantly at the expense of bandwidth because of transmitting periodic updates of topology frequently. Examples of proactive routing protocols include DSDV [Perkins1994], STAR [Garcia-Luna-Aceves1999], and TBRPF [Orgier2004], etc.

1.1.2 Adopting DSR as the Routing Protocol for the Ad Hoc Messenger Application

           In the previous section, we gave an overview of reactive and proactive protocols in mobile ad hoc networks based on distance vector or link state routing. In this Section, we list some known problems [Johnson 1994] associated with these protocols and give reasons why we adopt DSR as the protocol for the implementation of our Ad Hoc Messenger application.
           First, sending and receiving between two hosts over a wireless network does not necessarily work equally well in both directions. In Figure 1.1, host A may receive routing information from B reporting that B is the closest node to C and thus would be the next hop for A to obtain the shortest path to C. However, host A may not be able to transmit a packet back to B. Figure 1.1 indicates that the transmission range of all hosts is the same and uniform on all sides of the host, but radio and infrared propagation does not always work that nicely in real situations. Therefore, routes discovered by distance vector or link state routing based protocols may not work in wireless environments.
           Second, most links between routers provided by the routing protocols may be redundant. In Figure 1.1, assume that there are many mobile hosts within the transmission range of host A. Then all intermediate hosts including host B are equally good as an intermediate router for transmitting packets of host A to host C. These redundant routes in a wireless network cause a high volume of route updates flooded over the network, and cause high CPU overhead to process each routing update and to calculate new routes.
           Third, network bandwidth is often wasted in forwarding routing updates periodically. Under a stable network that does not change the topology often, even though nothing changes from one routing update to the next, each router still has to transmit periodic updates. Routing updates from mobile hosts outside each other's transmission range will not give any interference to each other. However, when there are many mobile hosts within the transmission range of each other, their routing updates will consume each other's network bandwidth.
           Forth, battery power is wasted because of periodically transmitting routing updates. Most mobile hosts in an ad hoc network will be operated based on battery power. Thus, transmitting each packet uses a considerable amount of battery power. Even though generally receiving a packet requires less consumption of battery power than sending it, the periodically arriving routing updates effectively prevent a host from conserving its own battery power by changing its mode to "sleep" or "standby" when not busy.
           Finally, distance vector or link state routing based protocols may not be suitable for dynamically changing networks that may often occur in ad hoc networks. In ad hoc networks, since movements of mobile hosts are common, using distance vector or link state routing based protocols may bring slow convergence to new and stable routes. The speed of convergence may be improved by flooding routing updates more frequently. However, such a modification wastes more bandwidth and battery power under a less frequently changing network topology.
           Some protocols have been purposed to improve the disadvantages of the conventional protocols, such as OLSR, as we introduced previously. However, many of the problems still remain unsolved.
           We adopt the Dynamic Source Routing (DSR) protocol [Johnson1994, Johnson1996, Johnson2001, Maltz2001, Broch1998, Zhong2003, Leung2001, Raju2001, Wenjing2002, Maltz1999, Camp2002, Jiang2002, Wu2002, Seet2003, Hu2000] for our implementation of the wireless ad hoc messenger application. The main reason is that DSR is a reactive on-demand protocol initiated by a source node to send information to a destination node without the need to maintain routing table information, thus eliminating many of the problems associated with distance vector or link state routing based protocols. Moreover, our wireless ad hoc messenger application also has the property that a chatting session is initiated by a user on-demand and that nodes move without a pattern so asking nodes to maintain routing table information is not practical.
           Another reason is that while some previous research work has been done to study the performance of DSR, most researches just use simulation experiments (e.g., based on the ns-2 network simulator). We aim to develop a real-world application using DSR as the underlying routing protocol and to test the effectiveness of certain design alternatives on the performance of the application.

1.2 PURPOSE OF STUDY

           As mentioned in the beginning of the introduction Section, people with mobile devices, such as a Pocket PC, often have the desire to share information when they are together unexpectedly and there is no Internet connection available. For example, users carrying Pocket PCs may want to exchange information during the middle of a conference or desire to share their ideas while listening to others' presentations via Instant Messaging without using any wireless infrastructure. In order to achieve the situation that each user carrying a Pocket PC can communicate with another by sending instant messages without the aid of any infrastructure, we have designed, implemented and evaluated an ad hoc messenger using Pocket PCs in wireless ad hoc environments in this thesis.

           The purposes of this thesis are as follows:

1.3 CONTRIBUTIONS

           The contributions of the thesis are as follows:

• As many users are carrying various types of mobile devices, such as laptops, Pocket PCs, cell phones, etc., there are increasing needs to communicate with each other without any aid of infrastructure. The application developed and evaluated in this thesis takes a role as an initiative to realize the popular use of Pocket PCs for exchanging information under environments with no infrastructure or Internet connections.

• While other studies on the DSR protocol have usually evaluated its performance using a simulator such as the ns-2 network simulator, this thesis designs and implements a real world chat program, a wireless ad hoc instant messenger application, using Pocket PCs, IEEE 802.11b wireless technology, Microsoft .Net Compact Framework (C#), and XML technology. It is valuable that a real ad hoc chat application using Pocket PCs has been properly designed, implemented and evaluated based on the DSR protocol. This work deserves some attention in that the performance of the DSR protocol is properly evaluated by developing a real world mobile ad hoc chat application.

• An innovative evaluation environment has been designed and implemented to ease the analysis of the effect of topology changes and design alternatives, and to ease performance data collection, including the design to generate network configuration files based on the random waypoint mobility model and the design to automatically generate test data and collect performance data based on XML data format and representation.

• Several design alternatives have been implemented and evaluated, and conditions under which one design alternative should be adopted over others are identified to improve the performance of the wireless ad hoc instant messenger application.

1.4 STRUCTURE OF THESIS

           This thesis consists of five chapters. The rest of the thesis is organized as follows.

           Chapter 2 describes background and related work. In particular, knowledge backgrounds for readers to easily understand the analysis regarding the results of experiments are discussed, including the characteristics of wireless ad hoc networks (Section 2.1), the main features of the DSR protocol (Section 2.2), and the IEEE 802.11 MAC protocol (Section 2.3). In Section 2.4, related work is introduced in terms of evaluation of the DSR protocol and testing of the optimized features of DSR. Section 2.4 also summarizes Chapter 2.

           In Chapter 3, detailed methodologies of this study are described, such as environment of the application development (Section 3.1), application system design (Section 3.2), performance evaluation (Section 3.3) in terms of input parameters and metrics used, and XML files used for describing and representing the results of experiments (Section 3.4). Then, Section 3.5 gives a summary of Chapter 3.

           Chapter 4 presents the experimental results based on the performance metrics used, and gives the interpretations of the results obtained. Section 4.1 describes the default conditions for input variables. From Section 4.2 to Section 4.6, the results of experiments under a variety of scenarios are presented and discussed.

           Finally, Chapter 5 concludes the thesis and outlines future work. Section 5.1 summarizes the results reported in Chapter 4. Section 5.2 describes the achievements of this thesis work. Section 5.3 suggests future work in terms of possible improvements of design and implementation of DSR on Pocket PCs in an ad hoc network.

           The bibliography includes all references used in this work. The appendices provide additional information that readers can refer if needed, such as user interfaces for automatic data collection, and complete XML files used to generate results.