Solutions to Hidden Terminal Problems in Wireless Networks
Chane L.Fullmer and J.J.Garcia-Luna-Aceves
Computer Engineering Department
School of Engineering
University of California
Santa Cruz,CA95064
chane,jj@cse.ucsc.edu
Abstract
Thefloor acquisition multiple access(FAMA)discipline is ana-
lyzed in networks with hidden terminals.According to FAMA,
control of the channel(thefloor)is assigned to at most one station
in the network at any given time,and this station is guaranteed to be
able to transmit one or more data packets to different destinations
with no collisions.The FAMA protocols described consist of non-
persistent carrier or packet sensing,plus a collision-avoidance dia-
logue between a source and the intended receiver of a packet.Suf-
ficient conditions under which these protocols provide correctfloor
acquisition are presented and verified for networks with hidden ter-
minals;it is shown that FAMA protocols must use carrier sensing to
support correctfloor acquisition.The throughput of FAMA proto-
cols is analyzed for single-channel networks with hidden terminals;
it is shown that carrier-sensing FAMA protocols perform better than
ALOHA and CSMA protocols in the presence of hidden terminals.
1Introduction
The medium access control(MAC)protocol with which packet-
radios(or stations)can share a common broadcast channel is es-
sential in a packet-radio network.CSMA(carrier sense multiple
access)protocols[8]have been used in a number of packet-radio
networks in the past[9];these protocols attempt to prevent a sta-
tion from transmitting simultaneously with other stations within its
transmitting range by requiring each station to listen to the chan-
nel before transmitting.Unfortunately,“hidden terminal”problems
[14]degrade the performance of CSMA substantially,because car-
rier sensing cannot prevent collisions in that case.
The busy tone multiple access(BTMA)protocol was thefirst
proposal to combat the hidden-terminal problems of CSMA.
BTMA is designed for station-based networks and divides the chan-
nel into a message channel and the busy-tone channel.The base sta-
1With packet sensing,stations only react to complete error free packets,
and do not detect carrier on the channel.As such,they do not react to noise
or partial packets in the channel.
(i.e.,sent an RTS)can only be achieved by the receivers.Accord-ingly,a FAMA protocol ensures that the CTS from a receiver lasts long enough(or is repeated enough times)to jam any hidden sender that did not hear the RTS being acknowledged.FAMA protocols constitute variations of existing MAC protocols based on RTS-CTS handshakes that eliminate collisions of data packets.Section2 introduces two representative FAMA protocols for single-channel networks.中脑边缘系统 Although the original motivation for MACA,IEEE802.11, MACAW[1],and BAPU[16]was to solve the hidden-terminal problems of CSMA by using RTS-CTS handshakes,it is easy to show by example that simply introducing three-way handshakes (RTS-CTS-data)or even more complex handshakes(RTS-CTS-data-ACK or others)does not suffice to eliminate all instances in which two or more senders are led to believe that they can transmit data packets to their intended receivers,only to create collisions. This is the case even if carrier sensing and RTS-CTS based hand-shakes are used in combination.Section3verifies sufficient con-ditions for correctfloor acquisition in single-channel networks that have hidden terminals.We show that carrier sensing is necessary in FAMA protocols to eliminate hidden-terminal problems efficiently in single-channel networks.Additionally,we show that,to provide protection from hidden terminals,packet sensing has limited ability to scale or operate dynamically.
Section4analyzes the throughput of FAMA protocols in net-works with hidden terminals.Our analysis shows that FAMA pro-tocols that use carrier sensing attain higher throughput than FAMA protocols that use packet sensing.In the case of a network with a base station and hidden terminals,FAMA protocols achieve higher throughput than CSMA.In practice,different applications may uti-lize the same channel,and while some applications benefit from very large data packet ,transfers of
videofiles)others do ,a telnet session).Our results show that,if data pack-ets cannot be arbitrarily large,FAMA protocols should be used to transmit packet trains whose duration is much longer than the du-ration of the RTS-CTS handshake.(A packet train is made up of a bounded number of packets sent by the station holding thefloor.) Section5compares by simulation the performance of FAMA-NCS with MACAW,which is based on RTS-CTS handshake and is packet sensing[1].Our results show very clearly thatfloor acquisi-tion and carrier sensing are critical to the performance and simplic-ity of MAC protocols based on RTS-CTS handshakes for networks with hidden-terminals.These results,together with the results of Section3demonstrate that collision avoidance should be done at both sender and receiver.
2FAMA Protocols
2.1Overview
A FAMA protocol requires a station who wishes to send one or more packets to acquire thefloor before transmitting a packet train. Thefloor is acquired using an RTS-CTS exchange multiplexed to-gether with the data packets in such a way that,although mul-tiple RTSs and CTSs may collide,data packets are always sent free of collisions.The basic principles offloor acquisition are inspired by the
earlier work of Kleinrock and Tobagi on BTMA [14]and the provision of priority acknowledgments in ALOHA and CSMA[15].
To acquire thefloor,a station sends an RTS using either packet sensing or carrier sensing.Thefirst variant corresponds to using the ALOHA protocol for the transmission of RTSs;the second consists of using a CSMA protocol to transmit RTSs.A station sends a CTS after receiving an error-free RTS addressed to it.When a station re-ceives an error-free CTS,it knows that thefloor has been acquired by the station to whom the CTS is addressed.Afterfloor acqui-sition,either thefloor holder or any of the receivers addressed by thefloor holder are able to send data packets and acknowledgments free of collisions over the channel.Any reliable link control scheme can be implemented on top of FAMA between thefloor holder and the stations with whom it wishes to communicate.This is accom-plished by forcing stations that do not have thefloor to wait a prede-fined minimum amount of time(at least twice the maximum prop-agation delay)before being able to bid for thefloor.This is similar to the schemes for the provision of priority acknowledgments pro-posed for CSMA and ALOHA by Kleinrock and Tobagi[15].
To ensure thatfloor acquisition is enforced among competing senders hidden from one another and who have requested thefloor (i.e.,sent an RTS),the CTS sent by a receiver is guaranteed to last long
enough(or to be repeated enough times)to jam any hidden sender that did not hear the RTS being acknowledged.This cor-responds to a single-channel BTMA scheme in which sensing of error-free CTSs(for packet sensing)or the carrier of a CTS(for carrier sensing)over the same data channel is used instead of a busy-tone signal sent over a separate channel.
When a station with data to send fails to acquire thefloor or detects thefloor being held by another station,it must resched-ule its bid for thefloor.This can be done using different per-sistence and backoff strategies.In this paper,we consider only non-persistent protocols.We also specify FAMA protocols that use a uniform distribution when choosing backoff times;however, other backoff strategies can be ,see those proposed for MACAW[1]).
To simplify our analysis and description of FAMA protocols,we do not address the effect of acknowledgments in the rest of this paper,and assume the simplest three-way handshake(RTS-CTS-data)with no acknowledgments sent after data packets.
2.2FAMA-NCS
Thefirst variant of FAMA,which we call FAMA-NCS(for non-persistent carrier sensing)combines non-persistent carrier sensing with the RTS-CTS exchange.This variant of FAMA is similar to the protocol
proposed for IEEE802.11[2],and Apple’s Local Talk Link Access protocol[12].However,those and other protocols based on carrier sensing and RTS-CTS handshakes do not guar-anteefloor acquisition in networks with hidden terminals.
The length of an RTS is larger than the maximum channel prop-agation delay plus any processing time.This is required to avoid one station hearing a complete RTS before another has started to receive it.
The length of a CTS in FAMA-NCS is larger than the aggregate of the length of an RTS plus one maximum round trip time across the channel,the transmit to receive turn around time,and any pro-cessing time.The relationship of the size of the CTS to the RTS gives the CTS dominance over the RTS in the channel.Once a station has begun transmission of a CTS,any other station within range of it that transmits an RTS ,within one propagation delay of the beginning of the CTS)will hear at least a
portion of the dominating CTS after returning from transmit mode and backoff,thereby allowing the data packet that will follow to arrive free from collision.The dominating CTS plays the role of a busy tone by providing a jamming signal to possible interfering transmitters within range of the sender of the CTS.
Figure1shows an example of how the CTS dominance operates in more detail.Station is sending a CTS while station is at-tempting to send its RTS and acquire thefloor.can send its RTS no later than seconds after starts its CTS(otherwise it would hear the CTS and wait).In this example’s CTS arrives at just as begins its RTS transmission(Figure1a).Because’s CTS is longer than the RTS plus the transmit to receive turnaround time, hears the overlap as noise and backs off.On the other hand,can begin its RTS and interfere with’s CTS no earlier than seconds before begins its CTS transmission(otherwise would have detected the signal and not sent the CTS).In this case(shown in Figure1b),the CTS arrives at seconds after that of’s RTS. Again,because the CTS is longer than the RTS plus the transmit to receive turnaround time,hears the end of the CTS as noise and backs off.
a) A sends RTS after B’s CTS b) A sends RTS before CTS at B Figure1:
邢台水灾
Dominance of the CTS in FAMA for hidden-terminal: a)begins its RTS just as’s CTS arrives at
b)begins its RTS seconds in advance of the CTS from
Figure2specifies FAMA-NCS in detail.A station that has just been initialized must wait the time it takes to transmit the maximum-size data packet in the channel plus one maximum round-trip time across the channel.This allows any neighboring station involved in the process of receiving a data packet to com-plete the reception un-obstructed.The initialization time also gives the station the ability to learn of any local traffic in progress.If no carrier is detected during the initialization period,the station transitions to the PASSIVE state.Otherwise,it transitions to the REMOTE state.A station can only be in the PASSIVE state if it is properly ,has no packet to send,and senses an idle channel).In all other states,the station must have listened to the channel for a time period that is sufficiently long for any neighbor involved in receiving data to havefinished.
A station that is in the PASSIVE state and senses carrier transi-tions to the REMOTE state.On the other hand,a station that re-ceives a packet to send in the PASSIVE state transmits an RTS and transitions to the RTS state.The sending station waits long enough for the destination to send the CTS.If the CTS is not received within the time allowed,the sender transitions to the BACKOFF state.If the sender hears noise on the channel after its RTS,it assumes a collision with a neighbor’s dominating CTS and waits long enough for a maximum-length data packet to be received.Otherwise,
upon receiving the CTS,the sender transmits its data packet.Because the CTS could be corrupted at the sender,once the destination station sends its CTS,it only needs to wait one maximum round-trip time to sense the beginning of the data packet from the source.If the data packet does not begin,the destination transitions either to the BACKOFF state(if it has traffic pending)or to the PASSIVE state. In the BACKOFF state,if no carrier is detected during the entire backoff waiting period computed by the station,the station trans-mits an RTS and transitions to the RTS state as before;otherwise, after sensing carrier the station transitions to the REMOTE state. For stations in the REMOTE state,FAMA-NCS enforces differ-ent waiting periods on passive stations(those stations not directly involved in the current transmission period)based on what was last heard on the channel.Any passive station that detects carrier transi-tions to the REMOTE state,and after the channel clears the waiting period is determined as follows:
After hearing an RTS for another station,the station must wait long enough for a CTS to be transmitted by the destination and received by the sender,and the data packet to begin.
After hearing a CTS from another station,the station must wait long enough to allow the other station to receive its data packet.
After hearing a data packet,the waiting time is the enforced FAMA waiting period.
After hearing noise(colliding control packets)on the chan-nel,the waiting period must be long enough to allow another station time to receive a maximum size data packet.
The channel becomes idle when all stations are in either the PAS-SIVE or BACKOFF state.The next access to the channel is driven by the arrival of new packets to the network and retransmission of packets that have been backed off.
To increase the efficiency of the channel,a station that has suc-cessfully acquired thefloor can dynamically send multiple packets together in a train,bounded by an upper limit.To allow this to be successful in a hidden-terminal environment,the destination station must alert its neighbors that it has more data packets coming,and to continue to defer their transmissions.FAMA-NCS uses a simple handshake mechanism to support packet trains.
Because a receiver’s neighbors are only required to defer trans-mission for the length of a maximum-sized data packet,data pack-ets are not concatenated.Instead,a CTS is sent after each data packet in a packet train(except the last packet in the train).
If the sending station has multiple packets to send,it sets a MOREflag in the header of the data packet.When the destination receives the data packet and sees the MOREflag set,it immediately res
ponds with a CTS,just as when hearing an RTS.This CTS alerts all neighbors that might interfere with the next data packet that they must continue to defer.
Additionally,stations in the REMOTE state must extend their waiting period after hearing a data packet with the MOREflag set to allow additional time for the sender to receive the CTS from the destination signaling that it can receive the next data packet.
2.3FAMA-NPS
The second variant of FAMA that we address is called FAMA-NPS (for non-persistent packet sensing).The key aspect of this variant of FAMA protocols is that stations do not sense the channel before
Variable Definitions
CD=Carrier Detected
=Maximum channel propagation delay
=Processing time for carrier detection
=Transmit to receive turn-around time
=Time to transmit an RTS packet
=Time to transmit a CTS packet
=Time to transmit a maximum sized data packet
Burst=Number of packets to send in a burst
Procedure START()
Begin
Timer
While(
No Local Packet)wait
If(CD)Then call REMOTE((),FALSE) Else Begin
Burst maximum burst
Transmit RTS Packet
谁欠谁的幸福 作者call RTS()
End End
Procedure RTS()
Begin
Timer
While(
Timer not expired)wait
If(CD)Then call REMOTE((),FALSE) Else Begin
Burst maximum burst
Transmit RTS Packet
call RTS()
End End
Procedure REMOTE(,)
Begin
Timer
While(
Variable Definitions
=Maximum channel propagationdelay
=Transmission time of an RTS packet
=Transmission time of a CTS packet
=Transmission time of a DATA packet
=Time to transition from transmit to receive Procedure START()
Begin
Timer
While(Timer not expired)wait
call PASSIVE()
End
Procedure PASSIVE()
Begin
While(No Packet Received No Local Packet)wait
If(Packet Received)Then call REMOTE(received packet) Else call RTS()
End
Procedure RTS()
Begin
Transmit RTS
Timer
While(Timer not expired No Packet Received)wait
If(Timer expired)Then call BACKOFF()
Else DO CASE of(received packet type)
Begin
Local CTS:call XMIT()
Default:call REMOTE(received packet)
End
End Procedure BACKOFF()
Begin
Timer RANDOM(1,)
While(Timer not expired No Packet Received)wait
If(Timer expired)Then call PASSIVE()
Else call REMOTE(received packet)
End
Procedure XMIT()
Begin
Wait
Transmit Data Packet
call PASSIVE()
End
Procedure REMOTE(packet)
Begin
主教
之友DO CASE of(packet type)
Begin
Local RTS:
Wait
Transmit CTS
timer
Other RTS:timer
CTS:timer
DATA:
If(Local DATA)Then pass packet to upper layer
call PASSIVE()
End
While(Timer not expired No Packet Received)wait
If(Timer expired)Then call PASSIVE()
Else call REMOTE(received packet)
End
Figure3:FAMA-NPS Specification
assumptions to prove the theorem:2
A0)The maximum end-to-end propagation time in the channel is .
A1)A packet sent over the channel that does not collide with other transmissions is delivered error free with probability.
A2)A station sends an RTS to the intended destination and re-ceives a CTS in return that does not collide with any other transmission with probability larger than0.
A3)All stations execute FAMA-NCS correctly.
A4)The transmission time of an RTS is,the transmission time of a CTS is,the maximum transmission time of
a data packet is,and the hardware transmit-to-receive
transition time is.
A5)There is no capture or fading on the channel.
A6)Any overlap by transmissions at a particular receiver causes that receiver to not understand either packet.
Theorem1FAMA-NCS provides correctfloor acquisition in the presenceof hidden terminals,provided that and
.
Proof:Figure4illustrates any possible case of hidden terminals with respect to a given pair of source and receiver.Station characterizes any neighbor of that is hidden from but can cause interference at.Station characterizes any neighbor of hidden from that can cause interference at and can prevent from following’s dialogue with.Similarly,Station is a neighbor of that is hidden from but can cause interference at ;and station is a neighbor of that is hidden from and can prevent from following’s dialogue with.The proof must show that,if sends a data packet to,no other
transmission Figure4:Stations involved in interference of the exchange between and
can collide with it,regardless of the possible transmissions of other interfering nodes.
For to be able to send data packets to,it mustfirst receive a CTS from.Without loss of generality,assume that,at time, sends an RTS to.
Because the channel has a minimum propagation delay larger than0,any neighbor ,Station)must start receiving’s RTS at time.If receives’s RTS correctly,then it must back off for a period of time larger than after the end of ’s RTS reaches,which means that backs off for
seconds after.Alternatively,if the reaches in error or Station’s transmission interferes with’s RTS at Station,then, starting with the end of carrier,Station must back off for a period of time larger than.The minimum amount of time that must back off then corresponds to the case in which the end of carrier coincides with the end of’s RTS.Accordingly,must back off for seconds after.It follows that the RTS sent by at time forces any neighbor of other than to back off until time.
If the RTS is received at Station with errors or collides with transmissions from other neighbors of who are hidden from (e.g.,),then cannot send a CTS and cannot send its data packet in return.
Assume that’s RTS is received correctly by at time.If receives’s CTS with errors or the CTS collides with transmis-sions from neighbors of hidden ,),then cannot
send its data packet.
For the rest of the proof,assume that the RTS that sends at time is received error free at station within one maximum propa-
gation delay,which means that must start sending its CTS to at time(given that zero processing delays are as-sumed).This CTS must reach within one maximum propagation
delay after sends it.Therefore,must receive’s entire CTS at time.
Because,it follows that any potential interfering neigh-
bor ,),must back off long enough for to be able to receive’s CTS without collisions.
Station must start to receive’s CTS no later than seconds after starts its transmission,and must receive’s entire CTS and send its data packet at time.In turn,Station must receive the end of’s data packet by time
.
On the other hand,any station other than within range of
must start receiving’s CTS at time.If receives’s CTS with no errors,then it must back off for a period of time larger than after the end of’s CTS reaches,which means that backs off for seconds after.Conversely,if’s CTS reaches in error or a transmission from one of its neighbors hidden from,call it,interferes with the CTS,then,starting with the end of carrier,must back off for more than seconds. The minimum amount of time that backs off corresponds to the case in which the time when detects the end of carrier equals the time when receives’s entire CTS;therefore,must back off for seconds after.It follows that the CTS sent by at time forces and any neighbor of other than to back off until time.
Because,it follows that Station and any other poten-
tial interfering neighbor of must back off long enough for to be able to receive’s data packet without collisions.Accordingly,it is true that FAMA-NCS allows a station to transmit a data packet only after a successful RTS-CTS exchange and no data packet collides with other transmissions.
3.2Packet-Sensing Protocols
The following theorem shows that,although a FAMA protocol based on packet sensing can support correctfloor acquisition in the presence of hidden terminals,it would be impractical to do so in a dens
e network because CTSs must be repeated too many times. The theorem relies on the following assumptions,which extend or modify the assumptions introduced in Section3.1:
A7)A station only recognizes complete packets,and cannot un-derstand noise,or partial packets.
A8)is the total number of neighbors any node in the network may have,plus the maximum number of neighbors any one of those neighbors may have(not including the sender and intended receiver).
A9)is the size of an RTS and CTS.
To understand the problem,assume that Station sends an RTS that is received correctly at Station,then immediately begins transmission of a CTS to.Figures5and6show two cases where the CTSs are not understood by stations in’s neighborhood.In thefirst case,station in s neighborhood transmits an RTS to
,blocking itself and all other stations in s neighborhood from understanding thefirst and second CTSs.In the second case,a station in the neighborhood of(and not or)transmits an RTS that blocks s CTS from allowing to transmit an RTS itself blocking additional CTSs.In either case,at least does not understand the CTS and can transmit an RTS that collides at with the data packet from if not enough CTSs are sent by station
.
S
R
X
RTS
RTS
鄢礼华
CTS CTS CTS
Case 1
DATA
Figure5:Packet Sensing with hidden terminals,N=1
RTS
RTS
CTS CTS
DATA
Case 2
S
R
X
RTS
CTS CTS
Y
Figure6:Packet Sensing with hidden terminals,N=2
To resolve the contention in thefirst case,the receiver needs to send at least three separate CTSs().This is necessary,be-cause a station considers the channel clear until any packet trans-mission is completely received free of error,and until that point there is no detection of traffic on the channel and transmissions are possible.As such,station can transmit its RTS just before the very end of receiving the CTS from,and in the process also trans-mits over the beginning of the next CTS.waits to get the CTS for it from and instead sees the CTS to,and defers further transmission.
In the second case,must send at leastfive CTSs(). Here,the neighbor of transmits an RTS that can collide with thefirst and second CTS blocking them from,allowing it to send an RTS masking the third and fourth CTSs.Thefifth CTS will be understood at forcing it to defer after that point. Theorem2A FAMA protocol using packet sensing provides cor-rectfloor acquisition in the presence of hidden terminals,provided that the receiver transmits at least CTSs in responseto an
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议