\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage[pdftex]{graphicx}
\input{epsf}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newif\ifexam
%\examtrue
\examfalse

\ifexam
\newcommand{\answer}[1]{}
\else
\newcommand{\answer}[1]{{\bf Answer:} #1}
\fi


\head{CS6710}{Wireless Networks}{Spring 2010}{12 March 2010}{7}

\ifexam
\begin{center}
\Large{\bf Midterm}
\end{center}
\else
\begin{center}
\Large{\bf Sample Midterm}
\end{center}
\fi

\ifexam
{\bf Instructions.}
\begin{itemize}
\item 
This is a 90-minute open-book open-notes exam.  

\item
The exam is divided into two parts.  Part I has 5 short-answer
questions, for a total of 16 points.  Part II has 5 problems, for a
total of 34 points.  

\item
You may want to read all the problems through first and attack them in
the order that allows you to make the most progress.

\item 
Your grade on any problem will be determined on the basis of the
  correctness of the solution and the clarity of the description.
  Having the correct solution approach is much more important than
  getting the specific calculations right.

\item
Show your work, as partial credit will be given.  If you need extra
space, use the blank facing page.

\item
Best of luck!
\end{itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 4 \\ \hline
2 & & 4 \\ \hline
3 & & 4 \\ \hline
4 & & 4 \\ \hline
5 & & 5 \\ \hline
6 & & 6 \\ \hline
7 & & 7 \\ \hline
8 & & 7 \\ \hline
9 & & 9 \\ \hline
Total & & 50 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill

\newpage
\fi

\begin{center}
{\large{\bf Part I (4 $\times$ 4 = 16 points)}}
\end{center}

{\bf 1.} Explain how the RTS/CTS mechanism alleviates the hidden
terminal problem?  Why is it important to include the length of the
data packet in both the RTS and CTS packets?

\answer{
The hidden terminal problem occurs when a node C transmits to B while
B is receiving from A, a node that C cannot hear.  If the A-B
communication is preceded by an RTS-CTS mechanism, then C hears the
CTS sent by B, which contains the length of the packet transmission,
and waits until the completion of the data transmission to initiate
its communication with B.

Packet length is important to include in CTS since that indicates to
neighbors how long the channel is going to be occupied.  For the
length to be included in CTS, the sender needs to send the packet
length in RTS.
}
\vfill

{\bf 2.} For a digital modulation technique, the {\em power
efficiency}\/ is measured by the $E_b/N_0$ ratio needed to achieve a
given bit-error-rate and the {\em spectral efficiency}\/ is measured
by the ratio of the information rate to the bandwidth.  Explain why
there is a tradeoff between spectral efficiency and power efficiency
in digital modulation.  In phase shift-keying (PSK), increasing the
number of bits per symbol generally increases the spectral efficiency
at the expense of power efficiency.  Why?

\answer{ A digital modulation technique is specified by a mapping of
symbols to signal elements.  A modulation technique with superior
error control has higher power efficiency, but lower bandwidth
efficiency since the different data symbols are encoded by signals
that are well-separated in the signal space.  

The greater the maximum distance between two signal points, the higher
the power efficiency since the more immune is the encoding technique
to noise.  In PSK, increasing the number of bits per symbol increases
the number of signal elements packed in the two-dimensional signal
space.  As a result, the spectral efficiency increases -- this can
also be seen in the PSK formulae on text -- but power efficiency
decreases.  Thus, for example, QAM is more bandwidth-efficient than
QPSK but less power-efficient.  QPSK has the same power-efficiency as
BPSK but better bandwidth-efficiency.  } \vfill

\newpage

{\bf 3.} Consider a linear block code where each codeword consists of
three data bits and one parity bit.  Find all codewords in this code.
How many bit errors can the code detect?  How many bit errors can the
code correct?

\answer{ The codewords are 0000, 0011, 0101, 0110, 1001, 1010, 1100,
1111.

It can detect 1 bit errors.  It can correct no errors.
}
\vfill

{\bf 4.} Give one reason why Mobile IP is difficult to implement with
firewalls.  Give one advantage and one disadvantage of the use of
reverse tunneling (setting up a tunnel from the Foreign Agent to the
Home Agent for transporting packets originating from the Mobile
Node).

\answer{ Mobile IP is difficult to implement with firewalls because
many firewalls forward packets only with source address within an
associated subnet.  A mobile node in a foreign network sends packets
with its original IP address as source, which is not part of the
foreign subnet; hence a packet originating from this mobile station
may be rejected by the firewall.

Reverse tunneling alleviates the above problem since every packet from
the mobile node is sent to the foreign agent which then encapsulates
the packet within an IP packet destined to the Home Agent, with the
Foreign Agent as source.  The Home Agent then decapsulates and sends
it off to the intended destination.  The main disadvantage with
reverse tunneling is that it can hijacked by a third party, who
pretends to be the Mobile Node and sends a packet to the foreign
agent, which then forwards it through the Home Agent on to the
Internet.  } \vfill
\newpage

\begin{center}
{\large{\bf Part II }}
\end{center}

{\bf 5. (5 points) Antennas and propagation} 

Two antennas, each with a directivity gain of 5 dB, are separated by a
distance of 10 km.  If the transmitted power of a signal by one
antenna on frequency 100 MHz is 1 W, what is the received power at the
other antenna?  Assume a free space path loss model and that the two
antennas are aligned so that directive gains are achieved.

\answer{ Each gain equals $10^{5/10}$, so the total gain is $10$.  The
received power equals
\[
\frac{10 \cdot 1 \cdot 9 \cdot 10^{16}}{(4\pi)^2 \cdot 10^{16} \cdot
10^8} = 5.7 \times 10^{-9} \mbox{W}.
\]
}
\newpage

{\bf 6. (6 points) Spread Spectrum} 

Sketch or describe the Direct Sequence Spread Spectrum signal $s(t)
c(t)$ over two bit time periods assuming that $s(t)$ is BPSK modulated
with carrier frequency 8 MHz and bit time period equal to $1 \mu$s.
Assume that there are four chips per bit in the spreading code $c(t)$
and that the chips alternate between $\pm 1$, with the first chip
equal to +1.  Assume that the first data bit is a 1 and the second
data bit is a 0.

\answer{ The signal has 8 time periods in 1 $\mu$s.  So each chip
should have 2 time periods of the signal. Since there are 4 chips per
bit, we would have phase shifts every 2 time periods of the signal;
at the $1\mu s$ point, however, when we move from a 1 bit to a 0 bit,
there will not be any phase shift since the chip change and bit change
cancel each other.

\begin{figure}[ht]
\begin{center}
\centerline{\epsfxsize = 6in \epsffile{signal.eps}}
\end{center}
\end{figure}
}

\newpage

{\bf 7. (7 points) The DCF mode of 802.11}

An infrastructure network using a 1 Mb/s IEEE 802.11 has 3 nodes N1,
N2, N3, connecting to an access point AP.  At time 0, N1 begins the
transmission of a data packet to AP.  There is no other ongoing
transmission.  At time 10 $\mu$s, N2 has a packet to be sent to AP
and at 30 $\mu$s, N3 has a packet to be sent to AP.  Assume that the
random number generator (for backoff) will give the following values
for N1: 1, 4, \ldots; for N2: 2, 5, \ldots; for N3: 3, 3, \ldots.

Show the execution of the DCF mode of IEEE 802.11 for the above
transmissions.  Assume that SIFS is 10 $\mu$s, DIFS 50 $\mu$s, and
slot time is 20 $\mu$s.  Assume that we don't use RTS/CTS or
fragmentation, and that all data packets have the same length of 125
bytes and that the Ack packet has length 25 bytes. Furthermore the
channel bit error rate is assumed to be 0, and 802.11 provides the
maximum possible throughput when there are no collisions.

\answer{
All times are in $\mu$s.

1000: N1's packet completed

1010: SIFS completed

1210: ACK completed 

1260: DIFS completed, backoff begins

1300: N2 transmits

2300: N2's packet completed

2310: SIFS completed

2510: ACK completed 

2560: DIFS completed, backoff resumes

2580: N3 transmits

3580: N3 completes

3590: SIFS completed

3790: ACK completed.
}

\newpage

{\bf 8. (2 + 2 + 3 = 7 points) Capacity of a cellular network}

Consider a cellular system with hexagonal cells of radius $R = 1$ km.
Suppose the minimum distance between cell centers using the same
frequency must be $D = 6$ km to maintain the required
signal-to-interference ratio.
\begin{itemize}
\item[{\bf (a)}] Find the required reuse factor $N$.

\answer{$N = (D/R)^2/3 = 12$.}

\vfill

\item[{\bf (b)}] If the total available bandwidth is $24$ MHz and each
user channel requires $20$ KHz, find the number of user channels that
can be assigned to each cell.

\answer{The number of user channels that can be assigned to each cell
is 1200/12 = 100.}

\vfill

\item[{\bf (c)}] Suppose each subscriber generates an average of one
call an hour, with a mean holding time of 100 seconds.  If the
cellular network operator wants to offer a grade of service of 0.02,
how many subscribers can the network support per cell?  Please refer
to the Erlang table given in the text, if needed.

\answer{For a GOS of 0.02, with 100 servers, the number of Erlangs
that can be supported is 87.97.  Traffic generated by a subscriber in
holding time equals $1/36$ Erlangs.  So the number of subscribers that
can be supported in the cell is $87.97\cdot 36 \approx 3167$.}

\vfill
\end{itemize}

\newpage

{\bf 9. (4 + 2 + 3 = 9 points) Path loss, frame error rates, and error
correction}

Two wireless nodes are communicating with each other through a
wireless network using BPSK modulation and operating at a frequency
band centered around 1 GHz.  One node transmits at a power level of
100mW and the noise density in the area is $10^{-16}$ W/Hz.  Assume a
free space path loss model, no other interference, and a frame length
of 100 bits.  Use the following formula for bit-error rate of BPSK.
\[
BER = Q\left(\sqrt{\frac{2E_b}{N_0}}\right).
\]
A table for the $Q$-function is given on the last page of this
document, for reference.  Please use the nearest values whenever you
do not find the exact values you are looking for.
\begin{itemize}
\item[{\bf (a)}] Find the separation distance at which a transmission
rate of 1 Mbps can be achieved with a frame error rate of 5\%.  Assume
no error-correction is used.

\answer{ FER = 100*BER.  So BER needs to be 0.0005.  From the
Q-function table, $\sqrt{2E_b/N_0}$ needs to be $Q^{-1}(0.0005) =
3.3$, so $E_b/N_0$ has to be at least 5.445.

\[
\frac{E_b}{N_0} = \frac{10^{-1}\cdot 10^{16}\cdot 9 \cdot 10^{16}
}{16\pi^2 \cdot 10^6\cdot 1^2 \cdot 10^{18} d^2} = \frac{9 \cdot
10^{30}}{16 \pi^2 \cdot 10^{24} d^2} = 570510/d^2.
\]

Therefore, $d$ is at most $323.69$ meters.  }

\newpage

\item[{\bf (b)}] At the separation distance that you obtain for (a),
what is the frame error rate incurred if the transmission rate is set
to 2 Mbps?  Assume no error-correction is used.

\answer{ $E_b/N_0$ now becomes $5.445/2 = 2.722$, so $\sqrt{2E_b/N_0}
= 2.33$.  So the BER is between $0.01072$ and $0.00820$.
Interpolation gives an approximate value of $0.01$.  For this BER, the
FER is $1 - .99^{100} = 0.634$, a very high frame error rate.}

\vfill

\item[{\bf (c)}]
Suppose now that each packet is encoded using a 1/2 rate encoding
technique with a minimum distance of 11.  The packet length, after
encoding, is set to be the same as before.  What is the frame error
rate incurred if the encoded packets are transmitted at a rate of 2
Mbps?  Compare the results of this approach with that of part (a).

\answer{ Given that BER equals $0.01$, FER now equals the probability
that there are at least six bit errors, which is ${100 \choose 6}
(BER)^6/720 = 0.00119$.  Thus, we obtain an effective throughput of 1
Mbps with a frame error rate of approximately .1\%, much better than
part (a).}

\vfill
\end{itemize}

\newpage
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
$z$ & $Q(z)$ & $z$ & $Q(z)$\\\hline
0.0 & 0.50000 & 2.0 & 0.02275\\\hline
0.1 & 0.46017 & 2.1 & 0.01786\\\hline
0.2 & 0.42074 & 2.2 & 0.01390\\\hline
0.3 & 0.38209 & 2.3 & 0.01072\\\hline
0.4 & 0.34458 & 2.4 & 0.00820\\\hline
0.5 & 0.30854 & 2.5 & 0.00621\\\hline
0.6 & 0.27425 & 2.6 & 0.00466\\\hline
0.7 & 0.24196 & 2.7 & 0.00347\\\hline
0.8 & 0.21186 & 2.8 & 0.00256\\\hline
0.9 & 0.18406 & 2.9 & 0.00187\\\hline
1.0 & 0.15866 & 3.0 & 0.00135\\\hline
1.1 & 0.13567 & 3.1 & 0.00097\\\hline
1.2 & 0.11507 & 3.2 & 0.00069\\\hline
1.3 & 0.09680 & 3.3 & 0.00048\\\hline
1.4 & 0.08076 & 3.4 & 0.00034\\\hline
1.5 & 0.06681 & 3.5 & 0.00023\\\hline
1.6 & 0.05480 & 3.6 & 0.00016\\\hline
1.7 & 0.04457 & 3.7 & 0.00011\\\hline
1.8 & 0.03593 & 3.8 & 0.00007\\\hline
1.9 & 0.02872 & 3.9 & 0.00005\\\hline
\end{tabular}
\end{center}

\end{document}



