Part of this thesis is funded by Microsoft Research in the project "Wireless Ad Hoc Messenger," for which the PI is Dr. Ing-Ray Chen and Co-PIs are Dr. Scott Midkiff, Dr. Luiz DaSilva, Dr. Denis Gracanin and Dr. Shawn Bohner. This work is based on a MS thesis at Virginia Polytechnic Institute and State University for the degree of Master of Science in Computer Science by Jin-Hee Cho. The thesis committee chair was Dr. Ing-Ray Chen and two other committee members were Dr. Luiz DaSilva and Dr. Denis Gracanin.

Keywords: Mobile ad hoc networks, dynamic source routing (DSR), network routing protocols, instant messaging, random waypoint mobility model, wireless communication.

           Popularity of mobile devices along with the presence of ad hoc networks requiring no infrastructure has contributed to recent advances in the field of mobile computing in ad hoc networks. Mobile ad hoc networks have been mostly utilized in military environments. The recent advances in ad hoc network technology now introduce a new class of applications.
           In this thesis, we design, implement and analyze a multi-hop ad hoc messenger application using Pocket PCs and Microsoft .Net Compact Framework. Pocket PCs communicate wirelessly with each other using the IEEE 802.11b technology without the use of an infrastructure. The main protocol implemented in this application is based on Dynamic Source Routing (DSR), which consists of two important mechanisms, Route Discovery and Route Maintenance. We adopt DSR since DSR operates solely based on source routing and "on-demand" process, so each packet does not have to transmit any periodic advertisement packets or routing information. These characteristics are desirable for the ad hoc messenger application for which a conversation is source-initiated on-demand.
           To test our application easily, we have developed a testing strategy by which a mobility configuration file is pre-generated describing the mobility pattern of each node generated based on the random waypoint mobility model. A mobility configuration file thus defines topology changes at runtime and is used by all nodes to know whether they can communicate with others in a single-hop or multi-hops during an experimental run.
           We use five standard metrics to test the performance of the wireless ad hoc messenger application implemented based on DSR, namely, (1) average latency to find a new route, (2) average latency to deliver a data packet, (3) delivery ratio of data packets, (4) normalized control overhead, and (5) throughput. These metrics test the correctness and efficiency of the wireless ad hoc messenger application using the DSR protocol in an 802.11 ad hoc network that imposes limitations on bandwidth and resources of each mobile device.
           We test the effectiveness of certain design alternatives for implementing the ad hoc messenger application with these five metrics under various topology change conditions by manipulating the speed and pause-time parameters in the random waypoint model. The design alternatives evaluated include (1) Sliding Window Size (SWS) for end-to-end reliable communication control; (2) the use of per-hop acknowledgement packets (called receipt packets) deigned for rapid detection of route errors by intermediate nodes; and (3) the use of cache for path look-up during route discovery and maintenance.
           Our analysis results indicate that as the node speed increases, the system performance deteriorates because a higher node speed causes the network topology to change more frequently under the random waypoint mobility model, causing routes to be broken. On the other hand, as the pause time increases, the system performance improves due to a more stable network topology. For the design alternatives evaluated in our wireless ad hoc messenger, we discover that as SWS increases, the system performance also increases until it reaches an optimal SWS value that maximizes the performance due to a balance of a higher level of data parallelism introduced and a higher level of medium contention in 802.11 because of more packets being transmitted simultaneously as SWS increases. Beyond the optimal SWS, the system performance deteriorates as SWS increases because the heavy medium contention effect outweighs the benefit due to data parallelism. We also discover that the use of receipt packets is helpful in a rapidly changing network but is not beneficial in a stable network. There is a break-even point in the frequency of topology changes beyond which the use of receipt packets helps quickly detect route errors in a dynamic network and would improve the system performance. Lastly, the use of cache is rather harmful in a frequently changing network because stale information stored in the cache of a source node may adversely cause more route errors and generate a higher delay for the route discovery process. There exists a break-even point beyond which the use of cache is not beneficial.
           Our wireless ad hoc messenger application can be used in a real chatting setting allowing Pocket PC users to chat instantly in 802.11 environments. The design and development of the dynamic topology simulation tool to model movements of nodes and the automatic testing and data collection tool to facilitate input data selection and output data analysis using XML are also a major contribution. The experimental results obtained indicate that there exists an optimal operational setting in the use of SWS, receipt packets and cache, suggesting that the wireless ad hoc messenger should be implemented in an adaptive manner to fine-tune these design parameters based on the current network condition and performance data monitored to maximize the system performance.