A novel approach to evaluating implementations of location-based software

A Novel Approach to Evaluating
Implementations of Location-Based Software
Daniel Herrscher, Steffen Maier, Jing Tian*, Kurt Rothermel
University of Stuttgart, Institute of Parallel and Distributed Systems (IPVS) Universitätsstr. 38, D-70569 Stuttgart, Germany Keywords: performance analysis, network emulation, loca-
resource requirements prohibit measurements in larger sce- tion-based software, positioning devices, mobile ad hoc net- Network emulation testbeds allow these measurements to be conducted in the laboratory. These testbeds consist of a Abstract
number of PC nodes connected by an emulated network. Spe- There are two main approaches to measuring the performance cial testbeds for mobile ad-hoc network (MANET) emulation of location-based software for mobile ad hoc networks: live control the network properties according to virtual node posi- testing and measurements in an emulation testbed. The tions. The reproduction of the desired network properties is former is problematic because of high resource costs and low performed by network emulation tools running on each test- reproducibility. The latter offers the advantage of reproduc- ible network conditions in the laboratory. In addition, loca- However, current testbeds are not suitable to evaluate loca- tion-based software has to be provided with appropriate tion-based software. Software that needs location informa- location information. We develop virtual devices that mimic tion has to access a positioning device, which is not the interface and functionality of actual positioning devices, physically present in a testbed. In this paper, we propose to in- and integrate these into an existing network emulation test- tegrate a virtual positioning device to an existing MANET bed. The combination of mobile network emulation and posi- emulation testbed. The virtual device exactly mimics the in- tioning device emulation facilitates the evaluation of terface and functionality of a real positioning device. Soft- location-based software in different scenarios. We provide ware running on testbed nodes can access the virtual device sample measurements using an existing location-based ad- through a serial interface, just like a real device. The position hoc routing protocol implementation for inter-vehicle com- information that is provided by the emulated device matches munication in a scenario with 50 emulated cars. The results the virtual position of the testbed node according to the emu- are in good agreement with the available simulations.
lation scenario. This facilitates the evaluation of location-based software in emulated environments in the laboratory.
I. INTRODUCTION
To show the applicability of our approach, we present mea- During the development of software for mobile devices, it is surements with an existing location-based routing protocol essential to analyze the impact of different scenario parame- implementation designed for inter-vehicle communication ters on performance. These parameters usually include move- For a scenario with 50 cars driving around in a typical city ment characteristics and network properties, such as center, we measure the overall delivery ratio for different communication range and bandwidth. In early design stages, transmission ranges. The results are in good agreement with performance is compared by mathematical analysis and sim- ulation. Measurements are used to check the theoretical re- The remainder of this paper is organized as follows: Relat- sults as soon as implementations become available.
Comparative performance measurements in real environ- present our approach to MANET emulation. de- ments are considered problematic for two reasons. First, in scribes the integration of the emulated positioning devices in scenarios with mobile nodes and wireless networking, it is our emulation infrastructure. provides sample hard to obtain multiple comparable measurement runs. The node movements have a strong impact on the quality of wire-less communication, and having several nodes exactly followa predefined choreography is not straightforward. Secondly, * Jing Tian is funded by the European Project CarTalk2000, contract number IST-2000-28185 II. RELATED WORK
pact of collisions on a shared media network can be The evaluation of location-based software in real MANET environments suffers from two problems: Limited repeatabil- While one of the approaches to MANET emulation makes ity and high resource costs. To alleviate the repeatability the virtual position information available on the nodes problem, proposes a MANET testbed consisting of sever- this information is not accessible for user programs. The po- al notebooks equipped with wireless network interfaces. Ac- sition information is only intended to be used by processes cording to a predefined choreography, the notebooks display belonging to the emulation infrastructure, e.g. location-based movement commands to be followed by students carrying the load generators. To our knowledge, there is no existing posi- notebooks. Although the original paper does not mention it, tioning device emulation in network emulation testbeds.
the approach would also be suitable for the analysis of loca-tion-based software if the notebooks were equipped with po- III. MANET EMULATION
sitioning devices. While the approach does provide In this section, we briefly describe our approach to MANET repeatable node movements with limited accuracy, the re- emulation. We use a testbed running a software-based distrib- peatability of the resulting network properties is still not guar- uted emulation approach with a versatile emulation tool.
anteed due to other influences that cannot be eliminated. Of First, we give an overview of the testbed architecture. Then, course, the resource cost problem remains.
we explain the basic functionality of our MANET emulation Therefore, it is reasonable to build MANET testbeds that do not require to distribute the nodes physically. The basicchallenge is to mimic the influence of virtual node mobility A. Architecture
on the actual network properties. Hardware-based approaches The testbed we use for the emulation of MANET environ- use wireless networking devices with additional hardware to ments consists of 64 Linux PC nodes connected by Gigabit control signal attenuation, and thus to emulate the changing Ethernet. For detailed information about the testbed architec- communication quality of the respective nodes Be- ture, please refer to Each PC node represents one mobile cause of the special resource requirements of these approach- node in a MANET scenario and serves as execution environ- es, the software-based emulation of MANET properties is ment for software to be evaluated. A custom emulation tool runs on each node. The tool inserts an additional emulation Software-based MANET emulation approaches can be layer into the communication stack. This layer mimics the be- classified into two sub-categories: Centralized and distribut- havior of a wireless network, including the properties of both ed. The centralized approaches require all traffic in a testbed the wireless networking device and the underlying wireless to be sent to a central instance. This instance maintains a node mobility model and decides which transmissions can be suc- A central scenario controller that runs on a dedicated high- cessfully delivered, based on the position and the transmis- performance PC is responsible for setting up and maintaining sion range of the emulated MANET nodes. The existing the scenario. It simulates the node mobility in real time ac- solutions for centralized MANET emulation differ in cording to a movement trace. Typical node movement traces the complexity of the network and signal propagation model for MANET scenarios can be generated on the basis of mo- that is considered by the central instance, but have in common bility models Since most available mobility model im- that this instance constitutes a performance bottleneck limit- plementations generate movement traces in the file format ing the overall network traffic in a scenario.
used by the simulator ns-2 we use the same format as in- In distributed MANET emulation, there is still a central in- stance that maintains a mobility model, but the traffic pro- The network properties for each node are calculated based cessing is done by local emulation tools directly on the on the nodes’ virtual positions. Currently, we use a simplified respective testbed nodes. This allows for much larger scenar- model to derive the network properties: If two nodes are with- ios without traffic limitations. Both the central model and the in a fixed transmission range, they can communicate via an local tools have impact on the realism of the emulation. Some emulated channel with parameters that are specified before- approaches simply use the built-in firewall of the operating hand. If their distance exceeds the threshold, the connection system as emulation tool Because firewalls can be con- is cut off completely. This model assumes uniform free-space figured to drop frames depending on the sender address, this radio propagation, which is the basis for most other approach- is sufficient to model the changing connectivity in a MANET.
es modelling MANET communication characteristics The introduction of dedicated emulation tools that run inside We are currently investigating the integration of more sophis- the communication stack facilitates to control more parame- ticated wave propagation models that consider spatial infor- ters, such as loss probabilities and delay Even the im- mation, such as buildings or streets .
Figure 1. Location of the emulation layer in the protocol stack.
Because the scenario controller does not process the actual frames. Ingress traffic is subject to a frame loss ratio, which traffic in the emulation scenario, we cannot consider the ef- can be specified separately for each sender address. As a con- fects of traffic on the network properties here, namely inter- sequence, it is possible to emulate the limited propagation ference and collisions. These effects have to be addressed by range of a transmission in a MANET. A broadcast transmis- the distributed emulation tools. In other words, the central in- sion issued by node N is physically delivered to all other stance computes which nodes have the chance to communi- nodes in the emulation testbed. On nodes within N’s propaga- cate based on their position. Depending on the actual traffic tion range, the drop rate for N is set to 0%, and therefore in- in a specific area, the emulation tools have to determine if an coming transmissions from N are passed to the upper layers.
actual transmission can be received successfully.
On nodes that are too far away from N according to the sce- The central scenario controller sends the current network nario, the emulation tool is configured to drop 100% of N’s parameters to a configuration daemon running on each node.
transmissions. This way, it is straightforward to implement We use simple UDP messages to send the parameter updates.
“neighbor tables” on each node. Furthermore, intermediate An additional separated administration network connects the loss rates can also be used to model the changing signal qual- control PC to all testbed nodes to ensure that the frequent up- ity, depending on node distance and other factors affecting the date messages do not interfere with traffic inside the emula- tion scenario. Upon reception of a parameter update, the The current version of our MANET emulation tool does not daemon configures the actual emulation tool by I/O control yet consider the effects of interference and collisions. There- fore, the behavior of the emulated MANET is only realistic The central scenario control eases the setup and manage- for scenarios with low network load. However, we are cur- ment of scenarios and synchronizes the emulation tools, rently developing an improved version that can mimic these while the actual traffic processing is done in a distributed effects, based on an emulation of the MAC protocol specified fashion. Thus, our architecture is scalable in terms of network in the IEEE 802.11b standard. In prior work, we already proved that the software-based emulation of a MAC protocol B. Emulation Layer
In order to emulate the properties of the physical layer and the
IV. VIRTUAL POSITIONING DEVICE
medium access sublayer (MAC) of the data link layer, our The emulation testbed described in facilitates the emulation tool offers the same service abstraction as the performance analysis of distributed applications and proto- cols designed to run in MANET environments. However, if Starting with logical link control (LLC), the layers above the software under test is location-based, it needs to access a the emulation layer experience the emulated network proper- positioning device. We cannot assume that this resource is ties. For these layers, we can choose to use the original proto- physically present in a testbed. Instead, we have to provide col implementations of Linux, or replace them with the software under test with a virtual positioning device. The experimental implementations. The presence of the emula- device provides position data that is consistent with the virtu- tion layer is completely transparent to the above layers.
al node position according to the emulation scenario.
The emulation tool processes both egress and ingress traf- fic. According to the desired network parameters, the toollimits the bandwidth of egress traffic and adds delay to the Figure 2. Network parameter and location updates.
A. Interface
vice outputs NMEA 0183 messages including the current po- There are many positioning and tracking technologies that a sition and other information (time, speed, etc.) at a regular MANET node could use in reality to obtain its position. Be- cause of its general availability, however, most existing sys- tems for outdoor use rely on GPS as positioning system. The NMEA 0183 messages, they can also process configuration standard application interface for GPS devices has been de- messages that are sent to the device. These messages include fined by the National Marine Electronics Association subscription information for special NMEA 0183 messages, (NMEA), and is referred to as the “NMEA 0183 standard” the setting of waypoints, etc. Our virtual device can handle a superset of NMEA 0183 messages that are considered by sev- Most GPS devices can be connected to a serial port. Even devices designed as interface card for PCI or PCMCIA slots Our primary implementation goal for the virtual position- are accessed by (virtual) serial ports. For that reason, we pro- ing device was to act exactly like a real positioning device, vide a virtual GPS device implementing the NMEA 0183 i.e. output and process NMEA 0183 messages on a serial standard that talks through a virtual serial port. This way, we port. In UNIX like operating systems, such as Linux, serial exactly implement the interface of a real GPS device. Conse- ports are accessed through character device special files in quently, existing location-based applications can interact with the “/dev” directory. We created a special file looking like a our virtual GPS device just like with any other GPS device.
serial port, and configured it to redirect all accesses to thispseudo file to our virtual device implementation By B. Implementation
this technique, any software accessing the virtual device per- As described in we maintain a model of the node ceives exactly the same behavior as with a real device.
positions to derive the network properties. Therefore, we canuse the same position information as input for the virtual po- V. SAMPLE MEASUREMENTS
sitioning devices. Because we use movement traces in ns-2 In order to test the applicability of our emulation environment format to specify node movement, we work with the same rel- for performance evaluation of location-based software, we ative node coordinates as ns-2. By defining an offset for this conducted measurements with a location-based routing pro- coordinate system, we map the relative coordinates to mean- tocol that was developed as part of the CarTalk 2000 project ingful absolute positions in the global WGS84 format used by The routing protocol especially addresses inter-vehicle communication. During the development process, first of all Similar to the real-time updates of the emulated network a simulation model for ns-2 has been implemented. After parameters, the administrative network of our testbed is used simulations with ns-2, the protocol was implemented on the to send the position information from the central model to the Linux platform. Preliminary tests were conducted using five respective nodes via UDP packets On each node, an cars with laptops, IEEE 802.11b wireless LAN adapters, and instance of the virtual device processes the position updates.
GPS receivers. Finally, we used our emulation testbed to eval- To applications, this instance behaves exactly like an actual uate the performance of the implementation in a larger sce- GPS device that is connected to a serial port. The virtual de- /dev/ttyS1
Figure 3. How to mimic a GPS device.
In this section, we briefly explain the routing algorithm, and the local neighbor table, which is constantly updated by greedy location-based routing, and show some implementa- a beaconing process. If a unicast packet queued for transmis- tion issues. Then, we describe the scenario for our measure- sion by a local application does not have a destination loca- ments. Finally, we present the measurement results we tion yet, the protocol queries a location service. The current obtained from our testbed, and compare them to the perfor- location service implementation uses simple flooding to dis- mance predictions from the ns-2 simulation model.
seminate location request messages. The destination sendsback location reply messages by location-based unicast to the A. Greedy Location-Based Routing
original sender. To minimize the expensive flooding opera- A number of special routing algorithms exist for MANETs.
tions, each node maintains a location cache.
While it is possible to do MANET routing without using lo-cation information, the efficiency in highly mobile scenarios C. Sample Scenario
can be improved significantly by using the node location as We set up a sample scenario with 50 cars, moving around in the city center of Stuttgart (2500m × 1800m) according to a The nodes participating in location-based routing deter- graph-based mobility model Initially, the cars are placed mine their own positions through positioning devices. Each randomly on the graph. During the scenario run time of node issues local broadcasts with its position (“beacons”) pe- 5 minutes, they move to a random target point on the graph, riodically. Based on the beacons that a node receives, it can with a speed ranging from 5 to 20m/s. After a random pause maintain an up-to-date neighbor table including the positions time of up to 20s, they move to the next target point. Each car randomly selects a communication partner and sends constant In contrast to traditional routing strategies that are based on bitrate traffic to it (one 64-byte packet per second). We mea- symbolic addresses, the destination location forms the basis sured the overall delivery ratio while we varied the transmis- for the packet forwarding strategy. The sender has to use a lo- cation service to resolve symbolic addresses to locations.
Greedy forwarding with MFR (Most Forward within Radi- D. Results
us) is a widely used forwarding strategy for location-based shows the measurement results we obtained from our routing From the set of current direct neighbors, the pro- emulation testbed, compared to the performance predictions tocol selects the node that is geographically closest to the des- from the ns-2 simulation model. Each point in the figure rep- tination as the next hop. Admittedly, greedy forwarding is not resents the mean value of three simulation or emulation runs, the ideal strategy for location-based inter-vehicle routing.
respectively. Because the connectivity of the nodes and there- The forwarding efficiency can be further improved by using fore the delivery ratio highly depends on the node movement, we generated three different movement patterns for the threeruns, and used the same set of movement traces for emulation B. Implementation
and simulation. The results reveal that the implementation Greedy location-based routing with MFR has been imple- shows the same qualitative behavior as predicted by the sim- mented as part of the CarTALK 2000 project The rout- ulation model. However, the delivery ratio of the actual im- ing protocol implementation runs on standard Linux in user plementation stays below the values of the simulation. This space, and uses raw sockets to send and receive frames direct- can be explained by implementation details that were not part ly on data link layer. Each node obtains its current position of the idealized simulation model. For example, the imple- from a GPS device. The routing core makes the packet for- mentation uses a location service based on flooding, while the warding decision based on the packet’s destination position cation-based software is a valuable complement to the tradi- tional approaches simulation and live measurement.
REFERENCES
D. Reichardt, M. Miglietta, L. Moretti, P. Morsink, and W.
Schulz, “CarTALK 2000 – Safe and Comfortable Driving Based Upon Inter-Vehicle-Communication,” in Proceedingsof the IEEE Intelligent Vehicle Symposium, Versailles, France, H. Lundgren, D. Lundberg, J. Nielsen, E. Nordström, and C.
Tschudin, “A Large-scale Testbed for Reproducible Ad hocProtocol Evaluations,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC 2002), J. Kaba and D. Raichle, “Testbed on a Desktop: Strategies andTechniques to Support Multi-hop MANET Routing Protocol Figure 4. Performance in simulation model vs. performance
Development,” in Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (Mo- simulation model queries an omniscient location service ob- biHoc’01), pp. 164–172, Long Beach, CA, Oct. 2001.
E. Hernandez and A. Helal, “RAMON: Rapid-Mobility Net-work Emulator,” in Proceedings of the 27th Annual IEEE Our conclusion from the sample measurements is that per- Conference on Local Computer Networks (LCN’02), pp. 809– formance evaluations in emulated network environments pro- duce reasonable results for implementations which are Q. Ke, D. Maltz, and D. Johnson, “Emulation of Multi-Hop comparable to the results simulators produce on the basis of Wireless Ad Hoc Networks,” in Proceedings of the 7th Inter- national Workshop on Mobile Multimedia Communications(MoMuC 2000), Tokyo, Japan, 2000.
VI. SUMMARY
J. Flynn, H. Tewari, and D. O’Mahony, “A Real-Time Emula- Performance evaluation of location-based software in real tion System for Ad Hoc Networks,” in Proceedings of the MANETs hardly provides reproducible results and makes Communication Networks and Distributed Systems Modeling high resource demands. Therefore, it is reasonable to run the and Simulation Conference (CNDS 2002), pp. 115–120, San evaluations in an emulated environment. While existing em- T. Lin, S. Midkiff and J. Park, “A Dynamic Topology Switch ulation testbeds can emulate the characteristic network prop- for the Emulation of Wireless Ad Hoc Networks Using a erties of a MANET to some extent, location-based software Wired Network,” in Proceedings of the 27th Annual IEEE needs to access a positioning device, which is not physically Conference on Local Computer Networks (LCN’02) (Wireless Local Network Workshop), pp. 791–798, Tampa, Florida, Nov.
In this paper, we proposed an approach to mimic both the interface and the functionality of a positioning device. The Y. Zhang and W. Li, “An Integrated Environment for Testing emulated positioning device is seamlessly integrated into a Mobile Ad-Hoc Networks,” in Proceedings of the Third ACM MANET testbed, i.e. network emulation and positioning de- International Symposium on Mobile Ad Hoc Networking & vice emulation work on the same node movement model. The Computing (MobiHoc’02), pp. 104–111, Lausanne, Switzer- virtual device can be accessed through a serial port exactly like a real device, and outputs and understands NMEA 0183 W. Chao, J. Macker, and J. Weston, “NRL Mobile NetworkEmulator,” Naval Research Lab Formal Report 5523--03- messages, which is the standard format for GPS devices.
Thus, to an application, it is completely transparent that the [10] W. Liu and H. Song, “Research and Implementation of Mobile Ad Hoc Network Emulation System,” in Proceedings of the To show the applicability of our approach, we measured the International Workshop on Smart Appliances and Wearable performance of an existing implementation for location- Computing (IWSAWC’02), Vienna, Austria, 2002.
based inter-vehicle routing, and compared the results to the [11] D. Herrscher, S. Maier, and K. Rothermel, “Distributed Emu- predictions of a simulation model. The promising experienc- lation of Shared Media Networks,” in Proceedings of the 2003 es from the sample measurements in our testbed lead us to the International Symposium on Performance Evaluation of Com- conclusion that our approach to performance evaluation of lo- puter and Telecommunication Systems (SPECTS 2003),pp. 226–233, Montréal, Canada, July 2003.
[12] D. Herrscher and K. Rothermel, “A Dynamic Network Sce- nario Emulation Tool,” in Proceedings of the 11th Internation-al Conference on Computer Communications and Networks(ICCCN’02), pp. 262–267, Miami, Oct. 2002.
[13] J. Tian, J. Hähner, C. Becker, I. Stepanov, and K. Rothermel, “Graph-based Mobility Model for Mobile Ad Hoc NetworkSimulation,” in Proceedings of the 35th Annual SimulationSymposium (ANSS-35 2002), pp. 337–344, San Diego, Cali-fornia, Apr. 2002.
[14] L. Breslau, D. Estrin, K. Fall, S. Floyd, J. Heidemann, A.
Helmy, P. Huang, S. McCanne, K. Varadhan, Y. Xu, and H. Yu,“Advances in Network Simulation,” in IEEE Computer,vol. 33, no. 5, pp. 59–67, May 2000.
[15] J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva, “A Per- formance Comparison of Multi-Hop Wireless Ad Hoc Net-work Routing Protocols,” in Proceedings of the 4th AnnualACM/IEEE International Conference on Mobile Computingand Networking (MobiCom’98), pp. 85–97, Dallas, Texas,Oct. 1998.
[16] F. M. Landstorfer, “Wave propagation models for the planning of mobile communication networks,” in Proceedings of the29th European Microwave Conference, vol. 1, pp. 1–6, Mu-nich, Germany, Oct. 1999.
[17] National Marine Electronics Association, “The NMEA 0183 Interface Standard, Version 3.01,” available from NMEA,7 Riggs Ave., Severna Park, MD 21146, USA, http://www.nmea.org, Jan. 2002 [18] M. Mauve, J. Widmer, and H. Hartenstein, “A survey on posi- tion-based routing in mobile ad hoc networks,” in IEEE Net-work Magazine, vol. 15, no. 6, pp. 30–39, Nov. 2001.
[19] H. Takagi and L. Kleinrock, “Optimal transmission ranges for randomly distributed packet radio terminals,” in IEEE Trans-actions on Communications, vol. 32, no. 3, pp. 246–257,Mar. 1984.
[20] J. Tian, C. Maihoefer, M. Nelisse, M. Provera, I. Dagli, M.
Tepfenhart, and C. Brenzel, “CarTalk2000 Deliverable D7:Routing Protocol Implementation,” available from http://www.cartalk2000.net, Oct. 2003 [21] J. Tian, L. Han, K. Rothermel, and C. Cseh, “Spatially Aware Packet Routing for Mobile Ad Hoc Inter-Vehicle Radio Net-works,” in Proceedings of the 6th IEEE International Confer-ence on Intelligent Transportation Systems (ITSC 03),pp. 1546–1551, Shanghai, China, Oct. 2003.

Source: ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/INPROC-2004-26/INPROC-2004-26.pdf