94.536 Mobile Computing

Solutions to Midterm, Fall 2002

 

Question 1. Frequency Reuse (10 marks)

Briefly explain the concept of frequency reuse that underlies cellular systems. Also explain why frequency reuse is necessary.

 

Answer:

·        Most cellular system cannot assign the same frequency to separate users at the same time (exception: CDMA). The use of the same frequency at the same moment by physically close senders leads to collision

·        Typical solution: each cell uses only subset of frequencies, with different subset of available frequencies assigned to neighboring cells

·        Each frequency set is reused eventually, frequency plan (assignment of frequencies to cells) typically follows a regular pattern such as 3, 4, or 7 groups of cells

·        Reuse distance is distance between two cells that use same subset of frequencies. Distance should be such that transmissions in one cell will not cause interference in other cell (radio wave propagation attenuates with distance, empirical evidence suggests a proportionality factor of roughly r-4).

Question 2. GSM (5 marks)

How are users authenticated in GSM? Explain all necessary steps, assuming that a user inserts his/her SIM into a new device in an unknown network and powers up the device.

 

Answer:

1.      First the user has to authenticate him/herself to the SIM card, using a secret PIN

2.      Next, the SIM card authenticates itself with the nextwork as follows:

 

 

 

Question 3. Wireless LANs (15 marks)

1.      IEEE 802.11, Hiperlan, and Bluetooth are all developed to allow IP packets to be carried over a wireless media. Based on the respective MAC protocols, how likely are packet collisions for each networking technology?

 

Answer (6 marks):

The answer depends on what MAC protocol we use in IEEE 802.11. In DCF, packet collision is the most likely to occur among all three protocols. This is in particular the case when the network is lightly loaded, since two stations with data to transmit will sense the medium to be idle and start transmission after DFS. In Hiperlan, with its more complex CAC protocol, packet collisions are less likely and require that two stations have packets with same priority level and selecting the same random number twice, overall rather unlikely. In Bluetooth and IEEE 802.11 PCF, packet transmissions are scheduled under the control of the AP or master, so assuming correct operation of the protocol, no packet collisions will occur.

 

2.      Compare the overhead introduced by the three MAC schemes and the resulting performance at zero load, light load, and high load of the medium.

 

Answer (9 marks):

Again, the answer will depend on the MAC protocol we choose for IEEE 802.11, so we have to look at four alternatives:

Question 4. IEEE 802.11 (15 marks)

Describe how clock synchronization and power saving is achieved in IEEE 802.11 for both Infrastructure Networks and Ad-hoc Networks.

 

Answer:

1)     Clock synchronization:

access

point
 

medium
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Infrastructure network: Access point broadcasts timestamp periodically, adjusted in case medium is busy (in the latter case, access point waits for medium to become idle and then broadcasts beacon, but resumes broadcasts at regular schedule….).

 

Without infrastructure network: stations compete to broadcast beacon with timestamp, station with shortest random interval wins (assuming medium is idle).

 

 

 

station1
 

station2
 

medium
 
 

 

 

 

 

 

 

 

 

 

 

 



2) Power saving:

 

station
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Infrastructure network: with every beacon, a traffic indication map (TIM) is sent. The TIM contains the list of stations for which unicast data frames are buffered in the access point. Mobiles have to wake up to listen to beacon/TIM. If TIM indicates a unicast frame for that mobile, station stays awake for transmission and responds that it is ready to received the frame (PS poll). Message exchange follows and the exchange can be duplex, afterwards station goes into sleep mode again. For multicast/broadcast message, mobile will also stay awake. Multicast/broadcasts are delivered every DTIM interval. As before, the beginning of an interval (TIM or DTIM) can be delayed if the medium is busy.

 

In ad-hoc networks, power management is more complicated: each station needs to buffer data it wants to send to a power-saving station. All stations announce a list of buffered frames during a period when they all wake up, in a structure called ad hoc traffic indication map (ATIM). The announcement window is called the ATIM window/interval.

 

ATIM

window
 

beacon interval
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

random delay
 

awake
 
 

 

 

 

 



Question 5. Bluetooth (5 marks)

Outline how connections are established and data exchanged in Bluetooth. (10 marks)

 

Answer:

Connection procedure: one device becomes master, initiates connection by PAGE (if address is known) or INQUIRY, followed by PAGE (if address unknown)

 

PAGE: send 16 identical page messages on 16 of 32 defined hop frequencies for slave device, if no response, send page on remaining 16 frequencies

     - maximum delay: 2.56 seconds

     - average delay 0.64 seconds

INQUIRY: similar to PAGE, but may require one additional train to collect responses, used for device discovery

 

Time Division Duplex (TDD) scheme for full-duplex transmissions: master device establishes connection, slave devices synchronize their clock with master clock for duration of connection

Synchronous Connection Oriented (SCO) type (used primarily for voice)

·        channel symmetric, only data packets retransmitted

Asynchronous Connectionless (ACL) type (used primarily for packet data)

·        master unit controls the link bandwidth and decides how much piconet bandwidth is given to each slave, and the symmetry of the traffic

·        slaves must be polled before they can transmit data.

·        The ACL link also supports broadcast messages from the master to all slaves in the piconet