Lab 3

Routing in Wireless Ad-hoc Networks
Warning: you must not attempt to get help from external sources such as online sites that offer
solutions or obtain code from other students. Any submission for grading must be your own work.
You must not copy from others or allow your work to be copied. We will check for similarities of code.
Any violation will result in your receiving zero for this project or an F for this course. No exception.
The lab submission must include a well-written report. Your report must adequately describe your
solutions, such as algorithm design, pseudo code, time complexity etc.
Total points: 100
This lab must be completed using Java and is an individual project. Naming of your programs must
strictly follow the following convention: (1) one file for each part; (2) Lab1 followed by your Uid and I
for part I (for example Lab1U00998499I.java). Upload only your source code (one file for each part), and
a report to the Pilot dropbox.
Note: The location of the input file and the output file must be your local directory. In your programs,
a directory or a path MUST NOT be used for your input/output files. Use only a file name, i.e, no
absolute path.
The solution time complexity for this lab is an important consideration in grading. Therefore, you
should design and implement your solutions carefully. Test cases will exercise your programs
thoroughly. Your programs should efficiently handle potentially large problems. Your code must
produce correct solutions for all test cases within 4-5 seconds.
Grading. You will be given only 1 simple case in the problem description below. Your solutions will
be tested with more cases that are of much larger size. These test cases will NOT be provided to
you. In real-world, you never know what the test cases are. Test cases will exercise your programs
thoroughly. Therefore, your programs should efficiently handle potentially large problems. Your lab
will be graded based on how many test cases you can pass. There will be no partial credit for a
case. Therefore, you should devise more cases on your own to test your code. You need to consider
border cases and cases of very large size before submitting your lab.
Problem An ad-hoc wireless network consists of numerous nodes. In the lecture, we discuss that we
can model the wireless communication channel in different ways, such as point-to-point model or
broadcast channel model.
In this lab, you will be asked to implement two algorithms to construct a broadcast tree rooted at a
given source node in the network.
Part I. Broadcast Incremental Power (BIP)
In Part I, you are asked to write a program to implement the BIP algorithm for constructing a
broadcast tree and determine the units of power needed. In this part, the BIP algorithm takes
advantage of the broadcast nature (i.e., assume the broadcast channel model) of the communication
channel.
INPUT FORMAT (file adhoc1.txt):
The first line of input has 3 numbers, specifying the source node, number of nodes, N (where
1≤N≤100,000), and M pairs of nodes (or wireless links). Each of the next M lines contains three
integers a, b, and p that describe transmission power between two nodes a and b where p units of
power are needed for one node to reach the other (assuming symmetric channel).
OUTPUT FORMAT (file adhoc1out.txt):

Your solution must produce a single integer to indicate the total units of power needed by the BIP
algorithm to construct a broadcast tree that reaches all nodes of the ad-hoc wireless network.
SAMPLE INPUT:
1 5 7
1 2 5
1 3 1
1 4 3
1 5 10
2 3 3
3 4 7
4 5 1
SAMPLE OUTPUT:
Part II. Minimum Spanning Tree
In Part II, we consider the same ad-hoc wireless network, but assume point-to-point communication
channel. You will implement the minimum spanning tree algorithm (the Prim’s algorithm) to construct
a broadcast tree (i.e., the minimum spanning tree).
INPUT FORMAT (file adhoc2.txt):
The input format is the same as that of Part I.
OUTPUT FORMAT (file adhoc2out.txt):
Your solution must produce a single integer to indicate the total units of power needed by the
minimum spanning tree algorithm to construct a broadcast tree that reaches all nodes of the ad-hoc
wireless network.
SAMPLE INPUT:
1 5 7
1 2 5
1 3 1
1 4 3
1 5 10
2 3 3
3 4 7
4 5 1
SAMPLE OUTPUT:

Lab 3

Uploaded by

Copyright:

Available Formats

Lab 3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab 3

Uploaded by

Copyright:

Available Formats

Routing in Wireless Ad-hoc Networks

Total points: 100

Part I. Broadcast Incremental Power (BIP)

INPUT FORMAT (file adhoc1.txt):

OUTPUT FORMAT (file adhoc1out.txt):

Part II. Minimum Spanning Tree

INPUT FORMAT (file adhoc2.txt):

The input format is the same as that of Part I.

OUTPUT FORMAT (file adhoc2out.txt):

You might also like