3.1 Environment of the Application Development
3.2 Application System Design
3.3 Performance Evaluation: Input Parameters and Metrics
3.4 XML Files Used for Describing Results of Experiments
3.5 Summary

           This Chapter describes the methodology for the implementation our multi-hop ad hoc instant messenger application using Pocket PCs and IEEE 802.11b.

3.1 ENVIRONMENT OF THE APPLICATION DEVELOPMENT

3.1.1 Network Testing Environment

           Figure 3.1 shows the network environment for our application development, modified based on Ye’s independent study project done at Virginia Polytechnic and State University in Fall 2002 [Ye2002]. Ye previously worked on this ad hoc messenger project. As Figure 3.1 shows, in our network environment for the application development, any access point or any other infrastructures are not required to set up the wireless ad hoc network. The compiled final executable files can be installed on the Pocket PCs through Microsoft ActiveSync and a cradle, either using a serial port or USB port. Multiple Pocket PCs can be synchronized with the laptop through setting up a partnership. During the experiments, Pocket PCs communicate with each other through the Compaq wireless WLAN card’s 802.11b P2P capability. The total number of participating Pocket PCs in this wireless ad hoc network is 7. For the convenient use of Pocket PCs, each Pocket PC is named and its IP address is assigned manually as follows:

3.1.2 Software Components

           The development software components are as follows:

           For the Application Development:

3.1.3 Hardware Components

           The development hardware components are as follows:

           The following is the main technical specification of Compaq iPAQ 3870 Pocket PC:

           The Compaq WL 110 Wireless PC card [Compaq2001] has the following specifications:

           The range of the wireless signal is associated with the Transmit Rate of the wireless communication. Communications at lower Transmit range will travel larger distances [Compaq2001].
           Experiments in our work are done with channel 10, which is a default value.

3.2 APPLICATION SYSTEM DESIGN

3.2.1 Basic Implementation of Client and Server

           Our main tool to develop this multi-hop ad hoc instant messenger is Microsoft .Net Compact Framework 2003 in C#. In C#, the UdpClient class is used to create a Client and a Thread is created as a Server to listen to arrivals of packets. The Client handles all the client functionalities including sending packets. UDP is chosen to send and receive packets, and its size is set to 512 bytes.

3.2.2 Implementation of the DSR Protocol

           TThis Section describes the features of the DSR protocol [Johnson2001] implemented in our ad hoc messenger application.

3.2.2.1 Initial Route Discovery

           The initial Route Discovery process uses the same procedures as the regular Route Discovery process. In our application, the following packets are used for the initial Route Discovery:

           When the destination node agrees to chat with the source node, all routes found through the initial Route Discovery packets (Start Chat Packets) will be stored in the source’s cache. When the current route is broken, the source will try alternative routes in its route cache to retransmit the data packet. Only when there is no alternative route available in the route cache of a source node, will a new Route Discovery be performed. The new Route Discovery process is described in more details in the following subsection.
           Note that the first route from a source to a destination always exists when the ACM (All nodes are Connected with Multi-hops) selection is turned on by the application. The ACM selection is an option allowing the application to be tested in a network environment in which all nodes are connected with multiple hops and will be explained with more details later.

3.2.2.2 Data Packet Transmission

           After the initial Route Discovery is done and a chat session begins, the source node or destination node can transmit data packets containing conversation contents by using the following packets:

3.2.2.3 Route Maintenance

3.2.2.4 Use of Route Cache Structure

3.2.2.6 Hang-Up

           The Hang-Up stage is the final stage when a chat session is ended. The operation of Hang-Up Packet (HUP) and Reply Hang-Up Packet (RHUP) is the same as Data Packet (DP) and Route Reply Packet (RRP). The following packets are utilized as follows:

3.2.2.7 Other Components

           Figures 3.3 and 3.4 show network topologies for both unadjusted and adjusted network topologies obtained from the GEN application based on the Random Waypoint Model (RWM), corresponding to Table 3.6.

3.2.3 XML-Based Packet Components

           This Section illustrates each component of a packet used in our multi-hop ad hoc instant messenger.

3.2.3.1 Regular Packet Format

           The regular packet format is used for communication between a source node and a destination node. A regular packet contains 10 fields (or components) as follows:

Note: On Calling Packet

< Session Number, Source ID, Destination ID, Sequence Number >

Session Number: Randomly selected unique number to distinguish each chat session.
Sequence Number: When a data packet is transmitted, a sequence number is used to process each data packet in order at the receiver. The sequence number starts from 1 and is incremented by one as more data packets are sent. When a Route Discovery packet is transmitted, a different sequence number is used. The sequence number for Route Discovery packets starts from – 4 and decremented by 1 as more Route Discovery packets are sent . This sequence number for Route Discovery packets is utilized to measure latency to find a new route.

< Current Node ID, Next Node ID, Unique Integer Number>

Unique Integer Number: This number is randomly selected, but does not overlapped with already selected number used in Receipt ID to distinguish each receipt packet.

3.2.3.2 Receipt Packet Format

           The Receipt Packets are used for hop-by-hop packet delivery confirmation. Three fields are used as follows:

3.2.3.3 Examples of a Regular Packet and a Receipt Packet in XML Format

           Figure 3.5 shows an example data packet in XML format. The packet type specifies that the packet is a data packet. The “Request ID” field indicates that 3452 is the session ID of the chat session, the source node is A, the destination node is G, and the packet is the first data packet with a sequence number of 1. The current node is D and the current route record is updated to include the current node in the partial route found. The “Route Cache” field indicates that the previously Route Discovery process has found a new route A-C-D-G. Thus, this data packet will be forwarded to G based on the information of Route Cache. The “Receipt ID” field is used to indicate that D should receive a receipt packet from the next node, G. The time at which node D sends this packet to G is at T=18 seconds, which is the time elapsed since the session begins.

           Figure 3.6 also illustrates the structure of a receipt packet in XML format. This receipt packet is for packet delivery confirmation between D and G in which 6785 is a unique integer number to distinguish each receipt packet. The time at which node D sends this receipt packet to G is at T=19 seconds, as indicated in the “Time Stamp” field.

3.2.4 Network Topology Design

           Since the actual testing environment for an ad hoc network is difficult to set up, the Random Waypoint Mobility Model has been employed to pre-generate a dynamic network topology as a function of time for nodes to follow in a simulation run. This Section gives a brief overview of the Random Waypoint Model and describes how our GEN application generates simulated network topologies based on different input values.

3.2.4.1 Random Waypoint Mobility Model

           The Random Waypoint Mobility Model contains pause time between changes in direction and/or speed [Camp2002b, Bettstetter2003]. Once a Mobile Node (MN) begins to move, it stays in one location for a specified pause time. After the specified pause time is elapsed, the MN randomly selects the next destination in the simulation area and chooses a speed uniformly distributed between the minimum speed and maximum speed. Then, the MN continues its journey toward the newly selected destination at the chosen speed. As soon as the MN arrives at the destination, it stays again for the indicated pause time before repeating the process [Camp2002b].

           Camp et al. give a demonstration of an example traveling pattern of an MN generated by the Random Waypoint Mobility Model, as shown in Figure 3.7 [Camp2002b]. The pattern starts at a randomly selected point (133, 180) with the speed of the MN uniformly selected from 0 m/s to 10 m/s.

           When MNs move based on the Random Waypoint Model, there is a complicated relationship between node speed and pause time [Camp2002b]. For instance, a scenario with a higher speed and longer pause time generates a more stable network than a scenario with a lower speed and shorter pause time. Long pause times, for example over 20 seconds, generate a stable network topology, such as few link changes per MN, even at high speeds, as demonstrated in Figure 3.8. In other words, even though speed is very high, if pause time is over 20 seconds, this random waypoint model produces a very stable network. Thus, in order to set up the very fluctuating network scenario by mainly controlling speed, high speed and very short pause time like 0 second are required.

3.2.4.2 GEN Application

           We developed a GEN application to generate a dynamic topology configuration file to be followed by all nodes based on the random waypoint mobility model. This Section discusses how GEN creates a configuration file to simulate a dynamically changing network and describes how we use XML to describe the configuration file (output of GEN) and the basic information file (input to GEN).

3.2.4.2.1 User Interfaces of the GEN Application

           The GEN program is to be loaded in each Pocket PC. According to the scenario of each experiment, the same configuration file will be loaded in each Pocket PC. The following shows the user interfaces of the GEN program:

           Figure 3.9 is the first user interface we can see when the GEN program is loaded. A user can add or remove or reset a node’s ID and IP address. After appropriate information is added and the user wants to set other variables, such as a simulation area, power range, speed, and pause time, etc., the user may click the button named the “Set Other Variables.” The “Set Other Variable” button brings the second interface shown in Figure 3.10. Simulation area and power range (transmission range) can be entered manually. A user can also manipulate speed and pause time. The specified pause time and speed will be applied to all randomly selected destinations, which are randomly selected positions within the chosen simulation area.

           After proper input values are chosen, the “Generate conf.xml” button shows the third interface, illustrated in Figure 3.11. Figure 3.11 shows the moving pattern of each mobile node based on the random waypoint model. The forth interface of the GEN program in Figure 3.12 demonstrates network topology at a specified time (T) equal to 3 seconds, which means that 3 seconds are elapsed since the session begins. Also, ACM is used for all nodes to be connected with multi-hops as a default condition.

3.2.4.2.2 Network Configuration File in XML Format

           The network configuration file (conf.xml) will contain randomly selected 10 destination positions (i.e. (x, y)) each with speed and pause time. Instead of selecting each random destination whenever each node moves as explained in Section 3.2.4.2 based on the Random Waypoint Mobility Model, 10 destination positions are pre-generated. After each node moves all 10 destinations, then it returns to the first destination and continues to move to the next destination.

           As explained in the User Interface of the GEN Application in previous subsection, a user can manipulate speed and pause time in the configuration file. Each node (Pocket PC) will see the same configuration file and move in the same simulated network. In the simulated network, each node stays at one destination location for specified pause time, and then moves to the next destination location with the specified speed. Since our experiments will be implemented based on various speed and pause time, a user can control speed and pause time by entering them as input values.

           Figure 3.13 shows an example network configuration file in XML format based on the random waypoint model. This configuration file is generated by the GEN application. Appendix C.1 gives a true example of the network configuration file (conf.xml).

3.2.4.2.3 Basic Information File in XML Format

           To describe the input parameter values to the GEN application, another XML file is generated based on the chosen input values from the second interface shown in Figure 3.10.
           Figure 3.14 illustrates an example XML-based file containing basic information selected for the GEN application. A true example of this XML file is given in Appendix C.2.

3.2.5 User Interfaces of the Chat Application

           The DSR protocol is implemented in our prototype ad hoc messenger (UserChat) with the following default conditions:

           Note that the use of the configuration file for simulating a dynamic network topology can be on or off based on the user’s preference in the real chatting prototype.

           The prototype application of multi-hop ad hoc messenger using Pocket PCs has the following two user interfaces:

           Figure 3.15 shows the first interface a user sees when the application is loaded. The “Buddy List” displays IDs and IP addresses of all other participating nodes except its own. Figure 3.16 is the second interface when a chat session begins.

           A use scenario is as follows:

1. When node A (source) wants to chat with node G (destination), A selects G in the Buddy List.

2. G has the option to accept or reject the chat request from A, as displayed in Figure 3.17.

3. A may or may not have a chat session by receiving “Accept” message or “Reject” message from a destination node, G, as Figure 3.18 and Figure 3.19 show.

4. If G accepts the chat request from A, A and G can have a conversation, as Figure 3.20 and Figure 3.21 demonstrate.

5. When A or G want to end the conversation, either of them can click the “Hang-Up” button. Then, the buddy node will have the message that the conversation is ended, as Figure 3.22 illustrates.

6. After the chat session is closed, both parties automatically go back to the first interface showing a buddy list to chat with a new buddy.

3.2.6 Design for the Automatic Data Collection Application

           To facilitate automatic data collection, another version of the wireless ad hoc messenger application is created. The underlying design and implementation is exactly the same as the prototype ad hoc messenger discussed earlier except that it is augmented with automatic testing and data collecting capabilities. The Automatic Data Collection application provides a user interface to allow a tester to specify scenario conditions. Figures 3.23 and 3.24 illustrate a use scenario:

1. A source node selects a buddy randomly by clicking the “Select buddy” button.

2. All other conditions can be selected using check boxes, such as ACM (All nodes are Connected with Multi-hops), use of cache structure, and use of receipt packet.

3. A user can enter Sliding Window Size (SWS) and the total number of data packets to be transmitted (for the chat contents) in each text box.

4. When the “Start” button is clicked, one packet containing all selected options and input values is broadcast to all nodes including its own. All nodes set the same scenario conditions selected and synchronize their time clock so that all nodes follow the same dynamic network topology based on the configuration file generated by the GEN at the same time.

5. After clock synchronization, the source node starts sending data packets until all are transmitted.

6. After all data packets are transmitted and the source node receives all ACKs for the transmitted data packets, the session is closed and proper result files are generated to measure the performances of our ad hoc messenger under the specified scenario.

7. The result files generated in each Pocket PC are transmitted through a program named the “Send And Receive Files,” to a laptop. A program named the “Statistical Analyzer” running on the laptop then takes all the result files from each node and produces X-Y graphs to analyze the impact of the selected environmental or design condition on the performance of our application.

           Figures 3.23 and 3.24 show snapshots of the user interface provided by the Automatic Data Collection application. More detailed user interfaces for the Send And Receive Files and Statistical Analyzer for achieving wireless file transfer and analysis of result files are listed in Appendix B.1 and Appendix B.2, respectively.

3.3 PERFORMANCE EVALUATION: INPUT PARAMETERS AND METRICS

           This Section describes input parameters to both the GEN and Automatic Data Collection applications, and defines performance metrics to evaluate the performance of our wireless ad hoc messenger application.

3.3.1 Input Parameters

For the GEN Application:

For the Automatic Data Collection Application:

3.3.2 Metrics Used

           We select five metrics to evaluate the performance of our wireless ad hoc messenger, namely, average latency to find a new route, average latency to deliver a data packet, delivery ratio of data packets, normalized control overhead, and throughput.

3.3.2.1 Average Latency to Find a New Route

           This metric indicates the average delay experienced to find a new route. This metric is chosen to measure the performance of our application because a short delay to find a new route in the presence of dynamically changing network topologies is a good indication that our application functions well. There are two situations to estimate the average latency to find a new route, as summarized in Table 3.8 and Table 3.9:

3.3.2.2 Average Latency to Deliver a Data Packet

           This metric indicates the delay experienced to successfully deliver a data packet from a source to a destination. This metric is selected also because it measures how our application functions under dynamically changing network topologies.
           More specifically, this average latency to deliver a data packet is the average delay for one-way trip of a data packet from a source to a destination. Therefore, in order to gauge this one-way trip time of a data packet, this latency starts when a data packet is sent by the sender and ends when a data packet is received by the receiver.

3.3.2.3 Delivery Ratio of Data Packets

           This metric indicates how many data packets (including retransmission due to errors) are transmitted in order to deliver the same number of data packets. For example, when there are 10 data packets to be delivered but 20 data packets are actually transmitted, then the delivery ratio is 50% since 10 data packets are transmitted but not delivered. This data delivery ratio is selected also to measure the performance of our application when the topology is rapidly changing causing links to be broken easily. This metric is defined by the following function:

Delivery Ratio of Data Packets =
                               Total number of data packets delivered / Total number of data packets transmitted.

3.3.2.4 Normalized Control Overhead

           This metric represents how many control packets are transmitted per data packet delivered. Since constrained resources are an issue in an ad hoc network, using fewer control packets per data packet is desirable to help reduce the use of bandwidth, battery power of each mobile device, etc. The normalized control overhead is computed by the following formula:

Normalized Control Overhead =
                               Total number of control packets used / Total number of data packets delivered.

           Control packets are used for Route Discovery and Route Maintenance. Examples of control packets are Route Reply Packet, Route Error Packet, Start Chat Packet, Accept Start Chat Packet, Reject Start Chat Packet, Route Discovery Packet, Reply Route Discovery Packet, Hang-Up Packet, and Reply Hang-Up Packet. We do not consider receipt packets as control packets because they are just used for hop-by-hop delivery confirmation. In a simulation experiment, we collect control packets sent by each node in order to avoid double counting.

3.3.2.5 Throughput

           This metric shows how many data packets are delivered per time unit (second). It is used to measure the degree of parallelism allowed by the system to handle the delivery of multiple data packets simultaneously. The throughput is calculated as follows:

Throughput = Total number of data packets delivered / Total time elapsed.

           The total time elapsed starts when the first Route Discovery packet (Start Chat Packet) is sent and ends when the ACK of the last data packet (Route Reply Packet for the last data packet sent) is received by the sender. When the throughput is high, it means that more packets can be transmitted per second or less time will be spent to deliver a fixed number of data packets.

3.4 XML FILES USED FOR DESCRIBING RESULTS OF EXPERIMENTS

           There are three XML files used to describe experimental results from the Automatic Data Collection application as follows: ADC_basicInfo.xml, Result_(NodeID).xml, and DataAnalysis_(NodeID).xml.
           Figure 3.25 shows an example file of ADC_basicInfo.xml obtained from the Automatic Data Collection application. This file contains basic information about selected nodes and options, such as source node, target node, use of cache structure, SWS, etc. After this file is moved to the Statistical Analyzer running on the laptop, the information in this file is looked up when result graphs are generated.

           Figure 3.26 displays an example file of DataAnalysis_A.xml generated from the Automatic Data Collection application. This source node’s file is mainly looked up by the Statistical Analyzer application in the laptop to produce proper result graphs according to a set of selected x-parameter and y-parameter. An example file in a non-source node is given in Figure 3.27.

           As most information needed for data analysis can be obtained from the source node except the total number of control packets sent, the files from non-source nodes do not have to contain all other information like components of the file from the source node. However, since the total number of control packets sent should be collected from all nodes participating in the network, it is recorded in each DataAnalysis_(NodeID).xml even for non-source nodes.

           Figure 3.28 shows an example file of Result_A. xml that includes the history of all packets sent and received by the source node. This file is used as a sanity check that all processes are functioning properly based on the design of the DSR protocol in our application. As illustrated in Figure 3.28, each result packet consists of 7 fields as follows:

3.5 SUMMARY

           This Chapter detailed the methodology used for the design, implementation and evaluation of the wireless ad hoc messenger application using Pocket PCs based on the DSR protocol.
           First, we discussed our development environment based on seven Pocket PCs with manually assigned IP addresses to evaluate the performance of our wireless ad hoc messenger based on the DSR protocol. For wireless communications between participating nodes, WLAN cards with 802.11b P2P capability are utilized. The main tool to develop the application is Microsoft Visual Studio .Net C# 2003, Microsoft .Net Compact Framework 2003, and Microsoft Pocket PC 2002 SDK. For the communication between Pocket PCs and a laptop, Microsoft ActiveSync is employed.
           Second, we discussed our design methodology for the implementation of DSR with basic features and alternative designs including the use of XML to describe data and receipt packets, the use of a dynamic network topology configuration file generated by the GEN application using the random waypoint model to account for node mobility, the interface design for a real ad hoc messenger, and the use of automatic data collection to facilitate testing and performance analysis.
           Third, for performance evaluation we described our user interface design that allows a tester to specify input parameters to reflect environmental and operational conditions and test their effect on system performance. We also defined five performance metrics, i.e., average latency to find a new route, average latency to deliver a data packet, delivery ratio of data packets, normalized control overhead, and throughput, as the basis for performance evaluation.
           Finally, we discussed our design methodology in using XML to describe experimental results to facility data exchanges between processes that generate data and those that analyze data and display results so that performance analysis after experiments are done can be performed automatically.

           In Chapter 4, experimental results will be presented and analyzed in terms of the five selected performance metrics.