Subject: RE: [manet] Carrier sense threshold/range control

From: "Yang, Lily L" <[email-masked]>
Date: Wed, 9 Jul 2003 10:37:34 -0700

Is this threshold commonly adjustable in the driver for most 802.11 cards? I agree with Mineo that this threshold by itself may not be adaquate for the hidden node problem. I would rather want to adjust the threshold to maximize the network capacity. As Mineo pointed out, when it is set too conservatively (which I think is the case), it causes the nodes to backoff unnecessarily and hence sacrifice spatial reuse potential and network capacity ultimately. 

> -----Original Message-----
> From: Mineo Takai [mailto:[email-masked]]
> Sent: Wednesday, July 09, 2003 10:02 AM
> To: Ram Ramanathan
> Cc: [email-masked]
> Subject: Re: [manet] Carrier sense threshold/range control
> 
> 
> (I forgot to comment on this in my previous message other 
> than giving a pointer..)
> 
> It is possible to avoid many hidden terminal cases by setting 
> the sensing range 
> more than twice the communication range, though there are 
> some caveats. We can 
> set/adjust the CS threshold, but not the pathloss that is to 
> be determined by 
> the environment. The CS range is a function of the CS 
> threshold and pathloss 
> (and TX power, antenna gains etc.), so the radio can hardly 
> know what the 
> resulting CS range is for a given CS threshold value. We can 
> make each radio 
> very sensitive by setting the CS threshold sufficiently low, 
> but that would 
> severely limit the network capacity as each radio becomes too 
> conservative for 
> signal transmission. Moreover, hidden terminal problems may 
> show up regardless 
> of the CS threshold due to irregular pathloss values. Imagine 
> Nodes A, B and C 
> are placed in an equal distance from each other (triangular 
> topology), but Nodes 
> B and C are obstructed by a wall that completely shuts down 
> the communication 
> link between them (pathloss equal to infinity). This clearly 
> creates a hidden 
> terminal problem at Node A regardless of the CS threshold. 
> (RTS/CTS should still 
> work in this situation.) Finally, other factors (fading, 
> noise sources nearby, 
> cumulative interference, interference/noise estimation errors 
> etc.) make the CS 
> mechanism less than perfect.
> 
> I'm not saying physical carrier sense is useless (In fact, I 
> think it's very 
> useful). Virtual carrier sense (RTS/CTS) is not a perfect 
> solution either and 
> comes with big overheads.
> 
> Mineo
> 
> Mineo Takai wrote:
> > Hello Ram,
> > 
> > This issue was discussed in my part of a tutorial on "MAC 
> protocols for 
> > MANET" (by Nitin Vaidya, Rajive Bagrodia and Mineo Takai) 
> in MobiHoc 
> > 2001. Some of the slides seem to have corrupted, but you 
> can take a look 
> > at Slides 31 through 34 of 
> > http://www.scalable-networks.com/pdf/mobihocpreso.pdf. I will try 
> > regenerating the slides and ask them to update.
> > 
> > Regards,
> > 
> > Mineo
> > 
> > Ram Ramanathan wrote:
> > 
> >> I am looking for pointers to research on the control of carrier 
> >> sensing range in lieu of using RTS/CTS to address the hidden node 
> >> problem?
> >>
> >> To elaborate, the threshold for when carrier is declared to be 
> >> "sensed" can be adjusted in many radios. Using this facility, one 
> >> could possibly
> >> make the "carrier sense range" approximately twice the 
> "communication 
> >> range"
> >> (successful packet reception), and detect hidden nodes.
> >>
> >> This is by no means a new idea, and I vaguely recally some 
> mention of
> >> it on this list. Of course, there are a number of factors 
> that make 
> >> the problem far more complex than the simple statement above 
> >> indicates, and
> >> it is not immediately clear whether it will be effective at all.
> >>
> >> I am looking for papers, tech reports, or any publicly 
> available material
> >> (non-proprietary) on this issue.
> >>
> >> Many thanks in advance,
> >>
> >> -Ram.
> >>
> >> _______________________________________________
> >> manet mailing list
> >> [email-masked]
> >> https://www1.ietf.org/mailman/listinfo/manet
> > 
> > 
> 
> 
> 
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet
> 

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "John Mullen" <[email-masked]>
Date: Wed, 9 Jul 2003 16:43:42 -0600

Hi Zygmunt,

Well, there is still a problem or two with RTS/CTS alone.  

Say, as in the illustration, B wishes to send to A.  Terminal B sends a
RTS, which C hears.  However, C never hears the CTS from A because A is
too far away.  What are C's choices if it wishes to send to D?  One is
to hold off for a random period of time, just in case A intends to send
a CTS.  If A doesn't send a CTS, then C has missed an opportunity to
send.  On the other hand, if C sends its RTS, it may cause a data
collision at B.  Assuming C cannot hear A, it is not possible for C to
know.  

Of course, once B starts to transmit, the risk of a collision at B is
not a problem, but now C would not be able to hear a CTS from D due to
interference from B.  In theory, C can send to D without causing a
problem, but in practice, unless the timing is just right, C will not
know that.

Unless terminals have perfect knowledge of the local topology and
exactly what each of their neighbors are doing, it will not be possible
to eliminate both the hidden and exposed terminal problems entirely. It
should also be borne in mind that one can include in RTS and CTS an
estimate of the duration of the channel's use so terminals that can hear
will know how long to wait before trying to seize the channel.  Carrier
sensing, while useful, does not have this capability.

An interesting approach is in the paper "Floor Acquisition Multiple
Access (FAMA) for Packet-Radio Networks," available at 
http://citeseer.nj.nec.com/fullmer95floor.html

In FAMA, time slots are reserved for RTS and CTS so data and control
packets do not collide.  Furthermore, the authors contend that data
packets will never collide.  The trade-off, of course, is the number of
time slots to reserve for signaling.  I'm not that current on MAC
protocols and there may be more recent papers.

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: Wednesday, July 09, 2003 2:40 PM
To: Dmitri D. Perkins
Cc: [email-masked]; Ram Ramanathan; Mineo Takai; [email-masked]
Subject: Re: [manet] Carrier sense threshold/range control 

Hi Dmitri,

On Wed, 9 Jul 2003, Dmitri D. Perkins wrote:
> Using the illustration referenced and assuming an RTS/CTS/DATA/ACK
> transmission scenario, the RTS must disable all nodes within range of 
> B (since B must also recieve an ACK from A). Using the same 
> illustration, if C is allowed transmit to D while B is transmitting to

> A, how will be B receive and ACK from A? It may now send C's 
> transmission will like interfere.

Please note that I referred to the RTS/CTS dialogue only, and not to the
RTS/CTS/DATA/ACK exchange. In the former, there is no need for RTS to
disable 
the nodes around the transmitter for more than the duration of the
RTS/CTS 
exchange only. Thus, while B transmits DATA to A, C is not disabled and
can transmit to A.

You are correct in saying that RTS/CTS/DATA/ACK dialogue requires to
disable nodes around both, the transmitter and the receiver, just to
cover the ACK going back to the transmitter. But this is not the case in
"pure" RTS/CTS dialogue, where the ACK can be sent on higher layer than
the MAC.

Hopes this clarifies the issue.

Zygmunt.
==-==-===
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-
Prof. Zygmunt J. Haas
http://people.ece.cornell.edu/haas 
Wireless Networks Laboratory		 http://wnl.ece.cornell.edu
School of Electrical Engineering         
Cornell University			 tel: +1-607-255-3454
323 Frank Rhodes Hall			 fax: +1-607-255-9072
Ithaca, NY 14853			 e-mail: [email-masked]
U.S.A                             
	WNL web page: http://wnl.ece.cornell.edu
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-

---

From: "[email-masked]" <[email-masked]>
Date: Wed, 9 Jul 2003 18:44:53 -0400 (EDT)

Hi John,

> collision at B.  Assuming C cannot hear A, it is not possible for C to

The MACA algorithm that I was referring to allows RTS to "reserve" the
channel for the duration of the RTS/CTS exchange only. Thus C will be
disabled for the duration of that time only. There is no need for C to
guess - if it did not hear CTS by the end of this period, it is free to
access the channel.

Again, the correctness of the MACA protocol depends on its theoretical
assumptions that there are no transmission errors, etc ... i.e., if a RTS
or CTS packet is sent, it is reliably received by all the nodes in the 
vicinity of the respective transmitter.

> problem, but in practice, unless the timing is just right, C will not

Correct. This issue (and few others) were addressed in the MACAW paper.

My statement was that under some theoretical assumptions, MACA provides
for both hidden- and exposed-terminal problems. In practice, as I have
stated, this is incorrect. This is why other schemes came in to fill in
the gap, the FAMA, as you have mentioned, and the DBTMA, as I have.

Cheers ... (I am off the line - have to do some work today ...(;-)).

Zygmunt.
===--=====
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas                    http://people.ece.cornell.edu/haas 
Wireless Networks Laboratory		 http://wnl.ece.cornell.edu
School of Electrical Engineering         
Cornell University			 tel: +1-607-255-3454
323 Frank Rhodes Hall			 fax: +1-607-255-9072
Ithaca, NY 14853			 e-mail: [email-masked]
U.S.A                             
	WNL web page: http://wnl.ece.cornell.edu
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

---

From: Chien-Chung Shen <[email-masked]>
Date: Thu, 10 Jul 2003 10:03:38 -0400 (EDT)

Greetings,

  We have paper that compared (omnidirectional) 802.11, MACA,
  and DBTMA, and their directional versions (with directional
  antenna) published in IEEE Globecom, 2002.

    Zhuochuan Huang and Chien-Chung Shen
    A Comparison Study of Omnidirectional and Directional
    MAC Protocols for Ad hoc Networks

  Thanks.

Chien-Chung

---

From: "#LI ZHIFEI#" <[email-masked]>
Date: Thu, 10 Jul 2003 22:08:29 +0800

Hi, Ram

In my view, even the Carrier Sensing Range (SR) is two times of the Transmission Range (TR ), the hidden-termianl problem is still there.
This can be illustrated as the following two topologies:

Topology 1:                                               Topology 2:

A -> B <- C                                                A -> B   C<- D

(note that the distance between two neighboring nodes are equal to the transmission range, i.e., one hop)

The first topology is tipycally used to illustrate the well-known hidden-terminal problem, but with an implicit assumption, i.e., SR=TR.
If SR=2*TR, the hidden-terminal problem seems not exist any more in this topology as the nodes A and C can sense the transmission of each other.

However, even SR=2*TR, the problem will arise in the second topology. Specically, when node A starts to transmit to node B, since node D
is out of the SR of node A, it cannot detect the transmission. Therefore, node D may also start to transmit to node C, resulting in collision (or capture).
In such case, we can say that nodes A and D are hidden terminal of each other. We do find the similarities of the performance between the two cases: 
topology 1 when SR=TR; and topology 2 when SR=2*TR

When SR>TR, another problem is that how a node should defer its transmission when it detects a SR frame. This is not an easy job since the node cannot 
interpret the content of the SR frame. In the IEEE 802.11, whenever a node detects a SR frame, it will defer by a fixed EFIS value. However, our results show
this fixed value will cause many problems, e.g., unfairness. Moreover, the capture ability will also greatly affect the performace when SR>TR.
For a detailed descrition of these issues, please refer to the attached references:

Zhifei Li, Sukumar Nandi, Anil K. Gupta, 
"Improving Fairness in IEEE 802.11 based MANETs using Enhanced Carrier Sensing", submitted to conference, April 2003
http://www.ntu.edu.sg/home5/pg03802331/papers/ecs.pdf

Zhifei Li, Sukumar Nandi, Anil K. Gupta, 
"Study of IEEE 802.11 Fairness and its Interaction with Routing Mechanism", accepted by IEEE MWCN 2003 Singapore, May 2003
http://www.ntu.edu.sg/home5/pg03802331/papers/mwcn03.pdf

Though the above papers mainly focus on the the fairness issue when SR>TR, the descirtion should also apply to the analysis of the channel utilization.
I hope that they will  relate to your work and help you.

Best regards 
Li ZhiFei 
PhD candidate,  
Center For Multimedia And Network Technology
School Of Computer Engineering
Nanyang Technological University
N4-b2c-08, Nanyang Avenue
Singapore 639798
tel:(65)67906579 
website: <http://www.ntu.edu.sg/home5/pg03802331> 

-----Original Message-----
From: Ram Ramanathan [mailto:[email-masked]]
Sent: dijous, 10 / juliol / 2003 00:09
To: [email-masked]
Cc: [email-masked]
Subject: [manet] Carrier sense threshold/range control

I am looking for pointers to research on the control of carrier sensing 
range in lieu of using RTS/CTS to address the hidden node problem?

To elaborate, the threshold for when carrier is declared to be "sensed" 
can be adjusted in many radios. Using this facility, one could possibly
make the "carrier sense range" approximately twice the "communication range"
(successful packet reception), and detect hidden nodes.

This is by no means a new idea, and I vaguely recally some mention of
it on this list. Of course, there are a number of factors that make the 
problem far more complex than the simple statement above indicates, and
it is not immediately clear whether it will be effective at all.

I am looking for papers, tech reports, or any publicly available material
(non-proprietary) on this issue.

Many thanks in advance,

-Ram.

---

From: Vikram Dham <[email-masked]>
Date: Thu, 10 Jul 2003 11:02:00 -0400

Hello Zhifei Li,

Though topology 2 also may have scenarios with hidden terminal, but in a 
wireless network,

probability (distance between nodes > 2SR) =< probability (distance between 
nodes > SR ).

 Though we may not be elminating all the hidden terminals but we may decrease 
the probability of occurence of hidden terminals by extending sensing range to 
2SR.

Regards

Vikram Dham
>===== Original Message From #LI ZHIFEI# <[email-masked]> =====
>Hi, Ram
>
>In my view, even the Carrier Sensing Range (SR) is two times of the 
Transmission Range (TR ), the hidden-termianl problem is still there.
>The first topology is tipycally used to illustrate the well-known 
hidden-terminal problem, but with an implicit assumption, i.e., SR=TR.
>If SR=2*TR, the hidden-terminal problem seems not exist any more in this 
topology as the nodes A and C can sense the transmission of each other.
>
>However, even SR=2*TR, the problem will arise in the second topology. 
Specically, when node A starts to transmit to node B, since node D
>is out of the SR of node A, it cannot detect the transmission. Therefore, 
node D may also start to transmit to node C, resulting in collision (or 
capture).
>In such case, we can say that nodes A and D are hidden terminal of each 
other. We do find the similarities of the performance between the two cases:
>When SR>TR, another problem is that how a node should defer its transmission 
when it detects a SR frame. This is not an easy job since the node cannot
>interpret the content of the SR frame. In the IEEE 802.11, whenever a node 
detects a SR frame, it will defer by a fixed EFIS value. However, our results 
show
>this fixed value will cause many problems, e.g., unfairness. Moreover, the 
capture ability will also greatly affect the performace when SR>TR.
>"Improving Fairness in IEEE 802.11 based MANETs using Enhanced Carrier 
Sensing", submitted to conference, April 2003
>"Study of IEEE 802.11 Fairness and its Interaction with Routing Mechanism", 
accepted by IEEE MWCN 2003 Singapore, May 2003
>Though the above papers mainly focus on the the fairness issue when SR>TR, 
the descirtion should also apply to the analysis of the channel utilization.

---

From: "#LI ZHIFEI#" <[email-masked]>
Date: Fri, 11 Jul 2003 10:32:17 +0800

Yes, the objective of the handshaking (RTS/CTS/Data/ACK) is mainly to protect the Data frame, which is normmally long.
Therefore, the collision of short RTSs will not affect the channel utilization too much. However, it will result in major problems if we
consider fairness. As for the CTS, since its reception will enable the transmission of Data, we should also preventing it from colliding.
I think that is the main idea in  DBTMA, i.e., protecting CTS and Data.

-----Original Message-----
From: Jing Deng [mailto:[email-masked]]
Sent: divendres, 11 / juliol / 2003 04:58
To: John Mullen
Cc: #LI ZHIFEI#; [email-masked]
Subject: RE: [manet] Carrier sense threshold/range control 

Dr. Mullen,

I agree with you. It will be very difficult to eliminate collisions when
distributed nodes (such as those in MANETs) are competing for a single
shared channel. Due to signal propagation delays, carrier sensing delays,
and processing delays, collisions will still exist even if carrier sensing
technique is used (as you have assumed).

However, if we use the busy tone or signaling channels properly, data
packet collisions can be avoided. Only channel requests (RTS packets) are
subject to possible collisions. Since the RTS packets are of much shorter
length, performance gain of throughput can still be achieved.

In what ratio the single channel is split affects the performance of the
MAC scheme significantly (as you pointed out in your earlier post),
especially when the RTS/CTS dialogues are to be transmitted on the control
channel. We have found some interesting results and shown them in the
following paper:

J. Deng, Y. S. Han, and Z. J. Haas, "Analyzing Split Channel Medium Access
Control Schemes with ALOHA Reservation," ADHOC-NOW '03, Montreal, Canada,
October 8-10, 2003. (to appear)

I will be happy to share it with anyone who is interested.

Cheers,

Jing

-----------------------------------------------------------
Dr. Jing Deng               http://www.cis.syr.edu/~jdeng01
2-191 CST, CASE Center      Email: [email-masked]
Dept. of EECS               Phone:  (315) 443-3029
Syracuse University         Fax:    (315) 443-4745
Syracuse, NY 13244
--------------------------- @_@ ---------------------------

On Thu, 10 Jul 2003, John Mullen wrote:

> Hi Li,
>
> I'm not entirely sure how you use the busy tone channels, so my
> statement may not be correct.  However, a fundamental problem is in how
> a terminal gets the right to use a channel.  If terminals transmit RTSs
> as the need arises, there is always a chance that those of different
> terminals will collide with each other.  This contention will have to
> occur somewhere, whether on the signaling channel or the data channel.
> So, wherever this signaling occurs is where the problem will be.
>
> Another problem is the short, but significant, transmission delay.  A
> terminal may sense that the busy channel is idle and begin to transmit,
> unaware that another terminal has made the same decision.  Because the
> carriers takes a finite, though brief, time to reach the other terminal
> and there is inherent delay in the sensing and control processes, by the
> time the carrier could be sensed, the terminal will already be sending.
>
>
> Later,
> John Mullen
>
> #LI ZHIFEI#
> Sent: Thursday, July 10, 2003 7:06 AM
> To: John Mullen
> Cc: [email-masked]
> Subject: RE: [manet] Carrier sense threshold/range control
>
>
>
>
> >What you say is correct, but only to a point and with a reservation.
> >First of all, although you can avoid collisions on the data channel, I
> >don't think you can avoid them completely on the busy tone channels.
>
> As for my understanding, in the busy channels, other potentailly
> interfering nodes need not interpret the content but just sensing the
> existence of busy carrier. So what do you mean for the collisions on the
> busy channel?
>
>
> >The more significant problem is that you are reserving part of your
> >available spectrum for signaling.  Whether this is done with a separate
>
> >radio channel or with time division on a single channel, you are
> >allowing only a fraction of the allotted band for data.  Thus, you need
>
> >to determine how much of the channel(s) need to be reserved for
> >signaling.  This would be a design matter and probably a tuning
> >parameter, since the distribution of message lengths would determine
> >the optimal signaling/data ratio.
>
> >This is not to say that such a thing is a bad idea, just that if not
> >done properly, it could be an inefficient use of the available
> >spectrum.
>
> I accept your viewpoint without any doubt. In addition to the issue
> about the spectrum efficience, complexity may be another issue by
> introducing multiple channels.
>
>
> Best regards
>
> Li zhifei
>
>
>

---

From: "Leena Chandran-Wadia" <[email-masked]>
Date: Fri, 11 Jul 2003 15:41:12 +0530

Dear Dr. Perkins,

On Wed, 9 Jul 2003, Dmitri D. Perkins wrote:

>Question...Referencing the previous illustration (A<-----B    C------>D),
>is there any work showing the benefit versus overhead or complexity for
>the following scenario:
>
>1. allow node C to transmit to D while B is transmitting a data frame to A
>2. force C to keep silent just in time for B to receive the ACK from A.
>
>This MAY result in better channel utilization but SHOULD require a more
>complex access/NAV scheme. Any thoughts...

We have tried 1. and 2. on 802.11 ad hoc networks. As mentioned by Nitin
Vaidya, packet sizes become important if one wants to allow parallel
transmission. C can indeed transmit to D while B is sending data to A,
provided it has a packet small enough so that it can finish transmission and
be silent in time for B to receive the ACK from A. Also, the transmission
from C to D must not use RTS/CTS. C can even receive an ACK from D provided
the end of transmission of its data is aligned with that of B.

We have implemented this in GloMoSim - turns out to be not too complex. The
details are available in a paper just accepted to ICCCN
http://www.it.iitb.ac.in/~sri/papers/expnode-ic3n03.pdf

The camera ready version of this paper is due on August 1st. If you and
others on the list can offer comments/criticisms, we would be glad to try
and incorporate them - at least the ones we can handle in the next 2
weeks...We can also make the implementation available if somone wants to
experiment with it.

There is also another effort in this direction. The authors have a much more
complex algorithm, called MACA-P, which involves negotiations between pairs
of transmitting nodes. There is an IBM research report (RC 22528) somewhere
in cyberspace. The paper was presented at IEEE PerCom 2003.

Thanks,
Leena

------------------------
Dr. Leena Chandran-Wadia
Infosys Research Fellow
Kanwal Rekhi School of Information Technology
IIT-Bombay, Powai
Mumbai - 400 076
mailto:[email-masked]
--------------------------