4003-541-70/4005-741-70 Data Communications and Networks II Undergraduate Programming Project 2 Prof. Alan Kaminsky -- Spring Quarter 2006 Rochester Institute of Technology -- Department of Computer Science Overview Software Requirements Questions Submission Requirements Grading Criteria Late Projects Plagiarism Overview A wildfire is raging within a 5 kilometer by 5 kilometer tract of land. The firefighters deploy an ad hoc sensor network to monitor the fire. An airplane flies over the tract and drops N sensors. The sensors land at random locations within the 5-km x 5-km square. Each sensor has a thermometer, a Global Positioning System (GPS) unit, a radio, and an embedded controller. Each sensor periodically transmits a data packet containing the sensor's location (from GPS) and the sensor's temperature measurement. Since the sensors are battery powered, each sensor's radio can transmit data only for a limited distance. When a sensor transmits a packet, only those sensors within 1 kilometer of the transmitting sensor will receive the packet. The firefighter's headquarters is located at one corner of the tract. The firefighters need to receive data from as many sensors as possible in order to monitor the fire accurately. Since most sensors are too far away from headquarters to transmit packets directly, the sensor network uses flooding to route the packets. Whenever a sensor receives a packet, the sensor retransmits the packet; a hop counter in each packet prevents the packets from circulating forever. Provided there is a route from each sensor to headquarters, eventually one or more copies of each packet will arrive at headquarters. Given that the sensors end up at random locations, data from only some fraction F <= 1 of the sensors will be able to reach headquarters. This fraction depends on the number of sensors N. Write a Monte Carlo simulation program to calculate and plot F as a function of N. In the program, the tract of land is represented as a square with (x,y) coordinates going from (0.0,0.0) to (5.0,5.0). The firefighter's headquarters is located at (0.0,0.0). The program does a simulation run for each value of N from 5 to 150 in steps of 5 (N = 5, 10, 15, . . . 140, 145, 150). For each simulation run, the program does K trials, where K is specified on the command line. For each trial, the program generates N random sensor locations within the 5-km x 5-km square and calculates F as described above. For each simulation run, the program prints and plots the average value of F over all K trials. Software Requirements Requirement 1. The program is called Wildfire. The program is run by typing this command:   java Wildfire <seed> <K>   where <seed> is the pseudorandom number generator seed and <K> is the number of trials for each simulation run. (Note: This means that the main program class must be named Wildfire, and this class must not be in a package.) Requirement 2. For each simulation run, the program must print the following line on the standard output: the value of N, a tab character, and the value of F. There is no additional white space before, after, or within the line. The lines must be printed in ascending order of N. Requirement 3. The program must display a plot of F versus N (the same values the program printed out). The program must use the following code to display the plot. The plotting classes come from the Computer Science Course Library. The variable fvsnSeries is an X-Y series that contains the (N,F) data to be plotted. XYPlot fvsnPlot = new XYPlot (new LinearAxis (0, 150, 15, 1, 0, 600, new Ticks (new DecimalFormat ("0")), (Ticks) null), new LinearAxis (0, 1, 10, 1, 0, 300, new Ticks (new DecimalFormat ("0.0")), (Ticks) null), new Grid()); fvsnPlot.addPlotSeries (new XYPlotSeries (fvsnSeries, Strokes.solid (3), Color.black)); fvsnPlot.addLabel (new Label ("Number of sensors N", 75, 0, Label.BELOW, 30)); fvsnPlot.addLabel (new Label ("Fraction of reachable sensors F", 0, 0.5, Label.LEFT+Label.ROTATE_LEFT, 36)); fvsnPlot.addLabel (new Label ("Sensor Network F vs. N", 75, 1, Label.ABOVE, 30, new Font ("sanserif", Font.BOLD, 14))); DisplayableFrame frame = new DisplayableFrame ("Wildfire", fvsnPlot); frame.setVisible (true); Questions Answer the following questions based on your program's output. Record your answers in a plain text file named "questions.txt" and include this file in your project submission. (5 points) If the firefighters drop 50 sensors, what fraction of the sensors will be reachable from headquarters? Explain how you derived your answer.   (5 points) If the firefighters want at least 95% of the sensors to be reachable from headquarters, what is the minimum number of sensors they will have to drop? Explain how you derived your answer. Submission Requirements Your project submission will consist of a Java archive (JAR) file containing all the Java source files for your project as well as the file "questions.txt". Each Java source file name must end in ".java".   Each class or interface must include a Javadoc comment describing the overall class or interface.   Each method within each class or interface must include a Javadoc comment describing the overall method, the arguments if any, the return value if any, and the exceptions thrown if any. See my Java source files which we studied in class for the style of Javadoc comments I'm looking for. Put all the source files into a JAR file named "<username>.jar", replacing <username> with the user name from your Computer Science Department account. The command is: jar cvf <username>.jar *.java questions.txt If your project used classes from the Computer Science Course Library without modifications, you do not need to include the source files for these classes in your submission. If your project used classes from the Computer Science Course Library with modifications, you do need to include the source files for these classes in your submission. Send your JAR file to me by email at ark­@­cs.rit.edu. Include your full name and your computer account name in the email message, and include the JAR file as an attachment. When I get your email message, I will extract the contents of your JAR file into a directory. I will set my Java class path to include the following directories: the directory where I extracted your files, and the Computer Science Course Library directory. I will compile all the Java source files in your submission using the JDK 1.5.0 compiler. I will then send you a reply message acknowledging I received your project and stating whether I was able to compile all the source files. If you have not received a reply within one business day (i.e., not counting weekends), please contact me. Your project is not successfully submitted until I have sent you an acknowledgment stating I was able to compile all the source files. The submission deadline is Tuesday, May 2, 2006 at 11:59pm. The date/time at which your email message arrives in my inbox (not the time when I actually read the message, which will be some time later than when it arrives in my inbox) will determine whether your project meets the deadline. If you submit your project before the deadline, but I do not accept it (e.g. I can't compile all the source files), and you cannot or do not submit your project again before the deadline, the project will be late (see below). I strongly advise you to submit the project several days before the deadline, so there will be time to deal with any problems that may arise in the submission process. Grading Criteria 50% of your project grade will be based on the design of your project as documented in the Javadoc and as implemented in the source code. Your project should: Be designed using object oriented design principles. Make use of reusable software components where appropriate. Be documented using proper Javadoc style as described above. Correctly implement the Monte Carlo simulation. 40% of your project grade will be based on test runs of your project. The grade for this portion will be based on whether your project produces the correct data on the standard output and the correct plot as specified in the Software Requirements. Every incorrect output will result in a loss of points. There is one exception: If your application does not run using the command line stated in Requirement 1, you will receive 0 points for this portion of your grade. Any deviation from the requirements will result in loss of points. This includes errors in the output formatting (such as incorrect number of spaces, incorrect capitalization, or incorrect punctuation), misspelled output, and extraneous output not called for in the requirements. The requirements state exactly what the output is supposed to be, and there is no excuse for outputting anything different. If any requirement is unclear, please ask for clarification. 10% of your project grade will be based on your answers to the Questions. Late Projects See the Course Policies for my policy on extensions. I will not accept a late programming project unless you arrange with me for an extension. A late programming project will receive a grade of 0. Plagiarism See the Course Policies for my policy on plagiarism. You may use any resources you wish to do the programming project, including resources discussed in class and resources you find on your own. You may discuss the programming project at a general level with others in the class. However, the programming project you turn in must be entirely your own work. You are not allowed to collaborate with anyone else on the programming project. You are not allowed to use any current or past student's work in any way when working on your programming project. I will not tolerate plagiarism. If in my judgment the programming project is not entirely your own work, you will get a grade of 0 for the programming project. I will also place a report of the plagiarism incident in your permanent file in the Computer Science Department office. Repeated plagiarism incidents will result in disciplinary action in accordance with Computer Science Department policy and RIT policy. There are only two exceptions to the prohibition on plagiarism: You may reuse without modification a source file from the Computer Science Course Library.   You may take a source file from the Computer Science Course Library and add your own modifications, provided you state that you have done so and give credit to the original author. Ad Hoc Networks • 4003-543-01/4005-742-01 • Spring Quarter 2007 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 18-Apr-2006. Please send comments to ark­@­cs.rit.edu.