Advanced Wireless Networks - 4G Technologies

148 ADAPTIVE AND RECONFIGURABLE LINK LAYER

[50]V. Vitsas and A.C. Boucouvalas, Optimization of IrDA IrLAP link access protocol, IEEE Trans. Wireless Commun., vol. 2, no. 5, 2003, pp. 926–938.

[51]V. Vitsas and A.C. Boucouvalas, Throughput analysis of the IrDA IrLAP optical wireless link access protocol, in Proc. 3rd Conf. Telecommunications, Figueira da Foz, 23–24 April 2001, pp. 225–229.

[52]D.J.T. Heatly, D.R. Wisely, I. Neild and P. Cochrane, Optical wireless: the story so far, IEEE Commun. Mag., vol. 36, 1998, pp. 72–82.

[53]A.C. Boucouvalas and Z. Ghassemlooy, Editorial, special issue on optical wireless communications, Proc. Inst. Elect. Eng. J. Optoelectron., vol. 147, 2000, p. 279.

[54]S.Williams, IrDA: past, present and future, IEEE Person. Commun., vol. 7, 2000,

pp.11–19.

[55]I. Millar, M. Beale, B.J. Donoghue, K.W. Lindstrom and S. Williams, The IrDA standard for high-speed infrared communications, Hewlett-Packard J., vol. 49, no. 1, 1998,

pp.10–26.

[56]IrDA, Serial Infrared Physical Layer Specification – Version 1.4. Infrared Data Association, 2001.

[57]IrDA, Serial Infrared Physical Layer Specification – Version 1.0. Infrared Data Association, 1994.

[58]IrDA, Serial Infrared Physical Layer Specification – Version 1.1. Infrared Data Association, 1995.

[59]IrDA, Serial Infrared Physical Layer Specification for 16 Mb/s Addition (VFIR) – Errata to version 1.3. Infrared Data Association, 1999.

[60]IrDA: Serial Infrared Link Access Protocol (IrLAP) – Version 1.1. Infrared Data Association, 1996.

[61]IrDA: Serial Infrared Link Access Protocol Specification for 16 Mb/s Addition (VFIR) – Errata to Version 1.1. Infrared Data Association, 1999.

[62]P. Barker, A.C. Boucouvalas and V. Vitsas, Performance modeling of the IrDA infrared wireless communications protocol, Int. J. Commun. Syst., vol. 13, 2000, pp. 589–604.

[63]P. Barker and A.C. Boucouvalas, Performance analysis of the IrDA protocol in wireless communications, in Proc. 1st Int. Symp. Communication Systems Digital Signal Processing, Sheffield, 1998, April, 6–8, pp. 6–9.

[64]W. Bux and K. Kummerle, Balanced HDLC procedures: a performance analysis, IEEE Trans. Commun., vol. 28, 1980, pp. 1889–1898.

[65]S. Williams and I. Millar, The IrDA platform, in Proc. 2nd Int. Workshop Mobile Multimedia Communications, Bristol, 11–14 April 1995.

5

Adaptive Medium

Access Control

Introductory material on MAC is presented in Appendix B (please go to www.wiley.com/go/ glisic). Within this chapter we focus only on few specific solutions in WLAN, ad hoc and sensor networks.

5.1 WLAN ENHANCED DISTRIBUTED COORDINATION FUNCTION

The last few years have witnessed an explosive growth in 802.11 WLAN [1]. Unfortunately, the current 802.11 MAC does not possess any effective service differentiation capability, because it treats all the upper-layer traffic in the same fashion. Hence, a special working group, IEEE 802.11e [2–12], was established to enhance the 802.11 MAC to meet QoS requirements for a wide variety of applications. The 802.11e EDCF (extended distributed coordination function) is an extension of the basic DCF mechanism of current 802.11 (Chapter 1). Unlike DCF, EDCF is not a separate coordination function, but a part of a single coordination function of 802.11e called the hybrid coordination function (HCF). The HCF combines both DCF and PCF (point coordination function) from the current 802.11 specification with new QoS specific enhancements. It uses EDCF and a polling mechanism for contention-based and contention-free channel access, respectively. In EDCF, each station can have multiple queues that buffer packets of different priorities. Each frame from the upper layers bears a priority value which is passed down to the MAC layer. Up to eight priorities are supported in a 802.11e station and they are mapped into four different access categories (AC) at the MAC layer [3]. A set of EDCF parameters, namely the arbitration interframe space (AIFS[AC]), minimum contention window size (CWMin[AC]) and maximum contention window size (CWMax[AC]), is associated with each access category to differentiate the channel access. AIFS[AC] is the number of time slots a packet of a given

Advanced Wireless Networks: 4G Technologies Savo G. Glisic

C 2006 John Wiley & Sons, Ltd.

150 ADAPTIVE MEDIUM ACCESS CONTROL

AC has to wait after the end of a time interval equal to a short interframe spacing (SIFS) duration before it can start the backoff process or transmit. After i(i ≥ 0) collisions, the backoff counter in 802.11e is selected uniformly from [1, 2i × CWMin[AC]], until it reaches the backoff stage i such that 2i × CWMin[AC] = CWMax[AC]. At that point, the packet will still be retransmitted, if a collision occurs, until the total number of retransmissions equals the maximum number of allowable retransmissions (RetryLimit[AC]) specified in IST WSI [13], with the backoff counters always chosen from the range [1, CWMax[AC]]. Since multiple priorities exist within a single station, it is likely that they will collide with each other when their backoff counters decrement to zero simultaneously. This phenomenon is called an internal collision in 802.11e and is resolved by letting the highest priority involved in the collision win the contention. Of course, it is still possible for this winning priority to collide with packets from other station(s).

Performance example – the basic parameters used in simulation are:

Packet payload size 8184 bits at 11 Mbps

MAC header 272 bits at 11 Mbps

PHY header 192 bits at 1 Mbps

ACK 112 bits + PHY header

Propagation delay 1 μs

Slot time 20 μs

SIFS 10 μs

The QoS parameters, i.e. CWMin[AC], CWMax[AC] and AIFS[AC], used in the following discussion are similar to the values specified by IEEE 802.11e Working Group for voice and video traffic [12].

Simulation with the same parameters is also presented for example, in Tao and Panwar [14]. In Figure 5.1, each station contains two priorities, which are only differentiated by the internal collision resolution algorithm discussed before. As expected, internal collision resolution by itself can provide some differentiation for channel access between different priorities.

The two priorities in each station are further differentiated by AIFS and CWMin/CWMax in Figures 5.2 and 5.3, respectively. It can be seen that AIFS may have a more marked effect on service differentiation than CWMin/CWMax alone. When all QoS mechanisms in 802.11e EDCF are enabled, the resulting throughput is shown in Figure 5.4. Comparing Figure 5.4 with Figure 5.2, we find that the QoS differentiation effect of AIFS is almost identical to the aggregate impact of AIFS plus CWMin/CWMax.

All the figures reveal that, as the number of stations in the network grows, the throughput for each priority as well as the total throughput drop fairly fast, especially when the QoSspecific parameters are small. Under heavy load assumption, the throughput for low priority often decreases to almost zero before the number of stations reaches 10. For this region, the high priority traffic dominates.

5.2 ADAPTIVE MAC FOR WLAN WITH ADAPTIVE ANTENNAS

Smart antennas (or adaptive array antennas) have some unique properties that enable us to achieve high throughputs in ad hoc network scenarios. A transmitter equipped with a

ADAPTIVE MAC FOR WLAN WITH ADAPTIVE ANTENNAS

151

Throughput

	0.5
	0.45	High priority (simulation)
		Low priority (simulation)
	0.4	Total (simulation)
		High priority (analysis)
		Low priority (analysis)
	0.35	Total (analysis)
	0.3
	0.25

0.2

0.15

0.1

0.05

0

2

4

6

8

10

12

14

16

18

20

Number of nodes

Figure 5.1 Two priorities differentiated only by internal collision resolution: CWMin/ Max[0] = 8/16, CWMin/Max[1] = 8/16, AIFS[0] = 2, AIFS[1] = 2.

Throughput

0.5
0.45						High priority (simulation)
						Low priority (simulation)
0.4						Total (simulation)
						High priority (analysis)
						Low priority (analysis)
0.35						Total (analysis)
0.3
0.25
0.2
0.15
0.1
0.05
0
2	4	6	8	10	12	14	16	18	20
				Number of nodes

Figure 5.2 Two priorities with different AIFS values: CWMin/Max[0] = 8/16, CWMin/ Max[1] = 8/16, AIFS[0] = 2, AIFS[1] = 3.

152 ADAPTIVE MEDIUM ACCESS CONTROL

Throughput

0.5
0.45						High priority (simulation)
						Low priority (simulation)
0.4						Total (simulation)
						High priority (analysis)
						Low priority (analysis)
0.35						Total (analysis)
0.3
0.25
0.2
0.15
0.1
0.05
0
2	4	6	8	10	12	14	16	18	20
				Number of nodes

Figure 5.3 Two priorities with different CWMin and CWMax. AIFS[0] = 2, AIFS[1] = 2, CWMin/Max[0] = 8/16, CWMin/Max[1] = 10/20.

Throughput

	0.5
	0.45	High priority (simulation)
		Low priority (simulation)
	0.4	Total (simulation)
		High priority (analysis)
		Low priority (analysis)
	0.35	Total (analysis)
	0.3
	0.25

0.2

0.15

0.1

0.05

0

2

4

6

8

10

12

14

16

18

20

Number of nodes

Figure 5.4 Two priorities with different CWMin, CWMax and AIFS: AIFS[0] = 2, AIFS[1] = 3, CWMin/Max[0] = 8/16, CWMin/Max[1] = 10/20.

ADAPTIVE MAC FOR WLAN WITH ADAPTIVE ANTENNAS

153

smart antenna can form a directed beam towards its receiver and a receiver can similarly form a directed beam towards the sender, resulting in very high gain. A receiver can also identify the direction of multiple simultaneous transmitters by running DOA algorithms and use this information to determine the directions in which it should place the nulls. Placing nulls effectively cancels out the impact of interfering transmitters. In this paper we present a simple 802.11b-based MAC protocol called Smart-802.11b that explicitly uses these three properties of smart antennas (beamforming, DOA and nulling) to achieve high throughputs. The two protocols are called Smart-Aloha [15, 16] and Smart-802.11b and, as the name implies, these two protocols are modifications to the well-known Aloha and 802.11b protocols. In both cases, functionality at the MAC layer is added to allow it to directly control the antenna: the MAC layer controls the direction of the beam and the direction of the nulls. In addition, the antenna provides the MAC layer with DOA information for all transmissions it can hear along with signal strength information. The main results are that these protocols show a very high throughput while maintaining fairness. Table 5.1 summarizes the main throughput results of the MAC protocols designed for directional antenna equipped nodes [15–26].

5.2.1 Description of the protocols

Consider the case when a node a needs to transmit a packet to node b which is its one-hop neighbor. It is assumed that a knows the angular direction of b and it can therefore form a beam in the direction of b. However, to maximize SINR, b should also form a beam towards a and form nulls in the direction of all other transmitters. In order to do this, b needs to know two things – first, that a is attempting to transmit to it, and second, the angular direction of all the other transmitters that interfere at b. The two protocols discussed in this section answer these two questions somewhat differently.

Smart-Aloha is a slightly modified version of the standard Slotted-Aloha protocol. To transmit a packet, a transmitter forms a beam towards its receiver and begins transmission. However, it prefaces its packet transmission with the transmission of a short (8 byte) pure tone (this is a simple sinusoid). Idle nodes remain in an omnidirectional mode and receive a complex sum of all such tones (note that the tones are identical for all nodes and thus we cannot identify the nodes based on the tone) and run a DOA algorithm to identify the direction and strength of the various signals. An idle node then beamforms in the direction of the maximum received signal strength and forms nulls in other directions, and receives the transmitted packet. If the receiver node was the intended destination for the packet, it immediately sends an ACK using the already formed directed beam. On the other hand, if the packet was intended for some other node, then the receiver discards it.

A sender waits for an ACK immediately after transmission of the packet and if it does not receive the ACK, it enters backoff in the standard way. Thus, the Smart-Aloha protocol follows a Tone/Packet/Ack sequence. The intuition behind the receiver beamforming in the direction of the maximum signal is that, because of the directivity of the antenna, there is a high probability that it is the intended recipient for the packet. However, in some cases, as in Figure 5.5, the receiver d incorrectly beamforms towards a because a’s signal is stronger than b’s. While this is not a serious problem in most cases, we can envision scenarios where the b → d transmission gets starved due to a large volume of a → c traffic. A possible

Table 5.1 Performance of MAC protocols using adaptive antennas. (Reproduced by permission of IEEE [27].)

	Characteristics of
Prior work	simulation experiments		Maximum throughput
[17]	Switched beam antenna 45◦	Random topology		(N = 25.4 hops)		Mesh topology
	beamwidth, 10 dB gain, 250 m
	range for omni, 900 m	MMAC	DMAC	802.11	MMAC	DMAC	802.11
	directional 4CBR sources,
		1000 kbps	400	200	800	300	200
	75 kbps to 2 Mbps each	(5×)	(2×)	(1×)	(4×)	(1.5×)	(1×)
[18]	Multi-beam antenna (1, 2, 4, beams	Fully connected (20 nodes)			Multi-hop (100 nodes, 5 hops)
	each) 30◦ beamwidth, 2 Mbps
	channel slotted (8 ms slot),	1 beam	2	4	1	2	4
	16 kbit packet (throughput
	converted to bps from	12 Mbps	30	60	60	150	300
	pkts/slot/net)		(Max over ROMA, UxDMA)
[19]	Adaptive antenna: 4 × 4, 8 × 8	4 × 4				8×8
	planar arrays, TDMA-802.11,
	1-hop			(55 nodes)
		8 pkts/packet time			9 pkts/packet time
[20]	Switched beam, 60◦ beamwidth	Proposed		DRTS/DCTS		CSMA/CA
				( 50 nodes )
		3.5 Mbps			2.5	2

CONTROL ACCESS MEDIUM ADAPTIVE 154

[21]Circular adaptive antenna array,

beamwidth 64◦, 8 dB gain (improvement over 802.11)

[22]Ideal adaptive antenna 20 nodes, no

nulling (improvement over omni case) Packet transmission is directional at sender/receiver

	25 nodes (grid)			225 nodes (grid)
No PC	Global PC	Local PC	No PC	Global PC	Local PC
1.3×	1.7×	(PC, power control)		4.75×	5.25×
		2.1×	2.6×
	Protocol		Beamwidth
O, omnidirectional		90◦	(20 nodes, degree = 7.5)		10◦
D, directional			60◦	30◦
ORTS/DCTS		35 %	57 %	100 %	142 %
DRTS/DCTS		64 %	107 %	143 %	186 %
DRTS/OCTS		28 %	43 %	n/a	57 %
ORTS/OCTS		29 %	50 %	86 %	121 %
STDMA		n/a	400 %	n/a	400 %

[23]Six-element circular antenna array

(10 fixed patterns, no adaptation)

45◦ beamwidth, 100 nodes,

1500 m2 2-ray propagation model, no nulling

	No mobility
Omni	RX directional	DVCS	DVCS-Ideal
	TX omnidirectional	TX, RX directional
400 kbps	800 kbps	1.4 Mbps	2.2 Mbps

ANTENNAS ADAPTIVE WITH WLAN FOR MAC ADAPTIVE

155

156 ADAPTIVE MEDIUM ACCESS CONTROL

a has a packet for c

d

a

b has a packet for d

b

c

Node d mistakenly forms a beam towards a because

a′s signal is stronger than b’s signal at d

Figure 5.5 False beamforming. (Reproduced by permission of IEEE [27].)

optimization is a single-entry cache scheme which works as follows:

If a node beamforms incorrectly in a given timeslot, it remembers that direction in a single-entry cache.

In the next slot, if the maximum signal strength is again in the direction recorded in the single-entry cache, then the node ignores that direction and beamforms towards the second strongest signal. If the node receives a packet correctly (i.e. it was the intended recipient), it does not change the cache. If it receives a packet incorrectly, it updates the cache with this new direction.

If there is no packet in a slot from the direction recorded in the cache, the cache is reset.

The Smart-802.11b protocol is based on the 802.11b standard. As in the case of the SmartAloha protocol, transmitters beamform towards their receivers and transmit a short sendertone to initiate communication. However, unlike Smart-Aloha, the transmitter does not immediately follow the tone with a packet. Instead, it waits for a receiver-tone and only then transmits its packet. After transmission of a packet, it waits for the receipt of an ACK. If there is no ACK, it enters backoff as in 802.11b. Figure 5.6 presents a state diagram of tone-based protocol. The behavior of the protocol in various states can be summarized as follows.

5.2.1.1 Idle

In case a node has no packet to send, it will remain in the idle state and set its antenna to operate in the omnidirectional mode. If it receives a sender-tone from some other node, it will move into the data receive wait state. On the other hand, if it wishes to send data, it will beamform in the direction of the receiver. It chooses a random number [0–CW] and sets the CW (contention window) timer 1. When the CW timer expires, it sends a sender-tone in the direction of the receiver and moves to the ACK wait state. If, before the CW timer expires, the node receives a sender-tone from another node, it will freeze its CW timer and move to data receive wait state.

5.2.1.2 Data receive wait

A node will move to this state in the event it receives a sender-tone. The node will beamform towards the sender and then randomly defer transmitting the receiver-tone by choosing a

ADAPTIVE MAC FOR WLAN WITH ADAPTIVE ANTENNAS

157

While in backoff receive sender-tone

Receive sender-tone (freeze CW timer and service

Data receive wait

sender-tone)

Idle

		ACKsendvalid,andreceivedDataOR expirestimereceiveData updatetheninvalidisreceiveddataIf cache		offbacktomoveexpires,timerACK	ACK	tone-sendersendexpires,timerCW	tone,
					Back off
	Valid ACK received				Wait		receiverReceive-	datasend
	Send sender-tone

and wait for receiver-tone

Figure 5.6 State diagram of the Smart-802.11b protocol.

random waiting period of [0–32] × 20 μs. The reason for deferring the reply is to minimize the chance of several receiver-tones colliding at sender 2. After transmitting a receivertone, the node remains in this state for 2τ (twice the maximum propagation delay + tone transmission time). If it does not hear a transmission, it returns to the idle state. If it hears the start of a transmission, it remains in this state and receives the packet. It then discards the packet if the packet was meant for some other node If, however, the packet was meant for it, then it sends an ACK.

5.2.1.3 Ack wait

If the sender node receives a receiver-tone before the tone RTT timer goes off (which is twice the tone transmission time plus propagation delay), it will transmit the data packet. Reception of a valid ACK will move the node to the idle state, and if packets are there in the queue then it will schedule the one at the head of the queue. The node will move to the backoff state under two conditions: (1) a receiver-tone did not arrive; (2) an ACK was not received following transmission of the data packet.

5.2.1.4 Backoff

The node computes a random backoff interval (as in 802.11) and remains in backoff for this time period (it also resets its antenna to omnidirectional mode). If, however, a sender-tone is received, it freezes the backoff timer and enters the data receive wait state. If the node is in backoff, upon expiration of the timer, it retransmits the sender-tone, increments the retransmit counter and enters the ACK wait state. A packet is discarded after the retransmit counter exceeds Max Retransmit = 7, as in the IEEE 802.11 standard.

The reception of a data packet by a node may be interfered with by transmissions of sender-tones, receiver-tones or other data packets (since the protocol does not take care of