Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

From: Phillip Neumiller <[email-masked]>
Date: Thu, 19 Sep 2002 13:53:08 -0400

Multiple spreading codes that are pseudo-orthogonal (or completely
orthogonal in the case of a synchronous system) can be used to 
provide multiple channels in the same bandwidth.  That could help
alleviate the hidden node problem, but is difficult to acheive
in a pure ad hoc system without very expensive clocks.

The solution to hidden nodes is MUCH easier.  Get rid of the omni
antennas and hidden node, exposed node, self-interference all go
away.  This is easier said than done.  This is the "real" solution
since it gets rid of the problem rather than dancing around it
at the MAC layer with RTS CTS handshaking.  

It is far better to do the root cause analysis here.  If you think
about this long enough, you will realize that using omnis in an
ad hoc network is the "Easy way out" and only a few folks have thought
carefully about the alternatives.  

Best regards,

Phil

-----Original Message-----
From: Mullen, John P. (Contractor)
[mailto:[email-masked]]
Sent: Thursday, September 19, 2002 1:32 PM
To: Sumeeth Nagaraj
Cc: [email-masked]
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi Sumeeth,

I'm not sure what you mean by "multiple codes."  Could you expand on this?

Thanks,

John Mullen

-----Original Message-----
From: Sumeeth Nagaraj [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 10:45 AM
To: Mullen, John P. (Contractor); Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Hello John,

I think, the hidden node and the exposed node problems can even be tackled
at the Physical layer, by using multiple codes, like the transmitter
directed codes?

Best Regards,
Sumeeth
----- Original Message -----
From: "Mullen, John P. (Contractor)"
<[email-masked]>
To: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Cc: <[email-masked]>
Sent: Thursday, September 19, 2002 7:47 AM
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

> Hi Liaw,
>
> You will probably get several answers on this.  Here is my view.
>
> 1.  The hidden and exposed terminal problems can be alleviated at the MAC
> level, but will impact the MANET protocol.  That is, the MAC's job is to
> manage the problem, but the MANET protocol should make allowances for it
> because "solve" may mean waiting until the condition goes away.  I'm not
> aware of any MANET protocols that attempt to solve these problems, but
they
> are generally designed with those possibilities in mind.
>
> 2.  It depends what you mean by "perfect."  The goal of the MAC layer is
to
> manage things in order to get the best performance possible out of the
> media.  The hidden and exposed terminal problems are situations that can
be
> handled, but the handling is likely to introduce some delay.  Other media
> problems might lead to corrupted packets, which will have to be resent.
> There is also a matter of control packets, such as RTS and CTS.  So, if
your
> "perfect" model provides for a loss of bandwidth due to overhead and delay
> in some way, you will have a realistic simulation.  However, if by
"perfect"
> you mean that every packet is sent the first time without delay, you will
> have something that is not realistic.  This is not to say you cannot do
> this.  In fact, most people start with such an ideal MAC to simplify
> debugging of their higher-layer models. However, if you do not later
> introduce a more realistic MAC model, your results will be overly
optimistic
> and you may miss conditions that could arise from MAC overhead and delay.
>
> I recently worked with a student who was comparing protocols for satellite
> communications.  When he had a noise-free channel, there were very large
> differences among the alternatives.  However, when he introduced noise,
the
> differences became much smaller and, what had looked like the best
> alternative in the noise-free model became one of the worst in the more
> realistic one.
>
> 3.  Again, you should allow for the impact of the solution on bandwidth
and
> delay.  MAC protocols are effective, but they cannot do magic.
>
> 4.  This is hard to say.  If the multipath fans out and areas of activity
> end up being far enough from each other that there is no mutual
> interference, the impact could be minimal.  It is possible that the MAC
> could make multipath very efficient.  It is also typical that the MANET
and
> MAC protocols would make multipath more efficient than the alternative of
> sending the packets to each of the intended destinations, one at a time.
>
> When a node transmits a packet, all nodes within range can hear it.  When
> there is a single path, only one of those nodes will rebroadcast in order
to
> forward the packet.  In multipath, several may do so.  The MAC can reduce
> interference if it "knows" who has heard each broadcast and minimizes the
> number of nodes that rebroadcast to a set that will propagate the multiple
> paths.
>
> This could be considered a MANET task, in which case, the MAC will provide
> the MANET protocol with a table of nodes that are expected receive each
> broadcast and the MANET protocol will choose which ones will rebroadcast.
> On the other hand, the problem could be handled directly in the MAC.  For
> example, the MANET protocol could specify that nodes a, b, c, and d are on
> the multipath, but the MAC suppresses c, knowing that if a, b, and d
> rebroadcast, all nodes covered by c would have already received the
packet.
> I don't think the division of tasks at this point has been finalized (I
> could be wrong on this).
>
> Good luck in your research.  This is an interesting and significant
problem
> to study.  However, just remember what Einstein said:
>
> Things should be made as simple as possible,
> But, no simpler.
>
> :-)
>
> John Mullen
>
>
> -----Original Message-----
> From: Liaw, Yong Shyang - LIAYS001
> [mailto:[email-masked]]
> Sent: Thursday, September 19, 2002 2:47 AM
> To: [email-masked]'
> Subject: [manet] Hiden- & exposed terminal problem in MANET
>
>
> Hi,
>
> I had read a few papers that described hiden-terminal & exposed terminal
> problem in MAC that severely hinder the transmission of data packets in
> multihop (i.e. MANET) environment.  For example, it can causes "false"
link
> failure by ad-hoc routing protocol suchb as DSR, to initiate a route
> discovery.
> I have few questions and would appreciate if you can help me:
>
> 1. The hidden-terminal and exposed terminal problems are MAC layer
problem,
> hence they should be solved in the MAC layer.  Is this a fair statement?
>
> 2. If it is, does that mean that I can design an ad-hoc routing protocol
(or
> higher protocol) without any consideration for the MAC charateristics? Or
in
> another word, can I assume that I have a "perfect" MAC layer (i.e. without
> the
> hidden- & exposed-terminal problems), and simulate my ad-hoc
> routing/transport
> with this assumption?
>
> 3. I would like to argue that the above 2 problems in MAC will probably be
> solved in the future by new MAC, such as the Dual Busy Tone Multiple
Access
> (DBTMA), and hence the above assumption is reasonable. (assuming that I am
> only
> interested in the ad-hoc routing protocol). Is this a weak arguement?  Are
> there any other MACs that address the above 2 MAC problems?
>
> 4. More specifically, I'm particularly interested in the multipath routing
> in
> MANET.  My concern is that multipath may allow us to inject more traffic
> into
> the MANET, and excite more nodes simultaneously. This will likely to mean
> that
> there are more MAC contention problems due to hidden-terminal, and
> exposed-terminal problem. Am I right?
>
> I would appreciate if you can help me, or point me to works that address
the
> problem.  Thank you.
> _______________________________________________
> 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
****************************************************************************
This e-mail is intended only for the addressee named above and may contain
confidential, proprietary or privileged information. If you are not the
named addressee or the person responsible for delivering the message to the
named addressee, please inform us promptly by reply e-mail, then delete the
e-mail and destroy any printed copy. The contents should not be disclosed to
anyone and no copies should be made. We take reasonable precautions to
ensure that our emails are virus free. However we accept no responsibility
for any virus transmitted by us and recommend that you subject any incoming
e-mail to your own virus checking procedures. 
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: David Young <[email-masked]>
Date: Thu, 19 Sep 2002 13:47:40 -0500

> at the MAC layer with RTS CTS handshaking.  

Phillip,

What omni replacement do you have in mind?  How does it solve the
problem? Do you have in mind a so-called "smart antenna" whose beam can
be pointed by software?

Dave

-- 
David Young             OJC Technologies
[email-masked]      Engineering from the Right Brain
                        Urbana, IL * (217) 278-3933
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: David Young <[email-masked]>
Date: Thu, 19 Sep 2002 13:47:40 -0500

Phillip,

Dave

---

From: Shweta Bhandare <[email-masked]>
Date: Thu, 19 Sep 2002 22:06:32 -0600

Why can't we use RTS/CTS handshaking to get rid of the hidden node problem.

Can anyone explain the exposed node problem?

Thanks,
Shweta

University of Colorado at Boulder.

---

From: Shweta Bhandare <[email-masked]>
Date: Thu, 19 Sep 2002 22:06:32 -0600

Thanks,
Shweta

---

From: Sumeeth Nagaraj <[email-masked]>
Date: Thu, 19 Sep 2002 22:32:32 -0600

Hi,

> Why can't we use RTS/CTS handshaking to get rid of the hidden node
problem.

yeah, RTS-CTS exchange is used to aviod hidden node problem.

> Can anyone explain the exposed node problem?

Consider 4 nodes, 1, 2, 3, 4: Node 1 cannot hear node 3 and 4 and same holds
good the other way too. node 3  can hear node 2 and 4,  but node 2 and node
4 cannot hear each other.

1         2             3             4

When node 2 has data packet to send to node 1, node 3 on hearing the RTS
packet(though data packet is meant for node 1), node 3 refrains from sending
data packet to node 4.  Here node 3 is exposed to node 2's transmission.
result is poor resource utilization.

Hope I am clear 8-)

Best Regards,
Sumeeth

---

From: Sumeeth Nagaraj <[email-masked]>
Date: Thu, 19 Sep 2002 22:32:32 -0600

Hi,

1         2             3             4

Hope I am clear 8-)

Best Regards,
Sumeeth

---

From: "Nitin Vaidya" <[email-masked]>
Date: Thu, 19 Sep 2002 13:26:57 -0500

Phil:
Out of curiosity, what sort of directional antennas would you say
are feasible for mobile devices today (hand-helds, laptops).

If the directional beams are not very narrow, using directional
antennas does not make the problem go away altogether, just make
it less severe.

- nitin

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf Of
Phillip Neumiller
Sent: Thursday, September 19, 2002 11:53 AM
To: Mullen, John P. (Contractor); Sumeeth Nagaraj
Cc: [email-masked]
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Best regards,

Phil

-----Original Message-----

Hi Sumeeth,

Thanks,

John Mullen

-----Original Message-----
From: Sumeeth Nagaraj [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 10:45 AM
To: Mullen, John P. (Contractor); Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Hello John,

Best Regards,
Sumeeth
----- Original Message -----

they
to
be
your
"perfect"
optimistic
the
and
and
to
packet.
problem
link
problem,
(or
in
Access
the

---

From: Vikram Kanodia <[email-masked]>
Date: Fri, 20 Sep 2002 16:00:09 -0500 (CDT)

RTS/CTS do not fully solve the problem. 
Check out the paper:
"Ordered Packet Scheduling in Wireless
 Ad Hoc Networks: Mechanisms and Performance Analysis,", Mobihoc 2002.

-Vikram

-- 

Department of ECE, Rice University | 713 348 3786 (O)| 713 664 5650(H)
WWW: http://www.ece.rice.edu/~kanodia

---

From: Vikram Kanodia <[email-masked]>
Date: Fri, 20 Sep 2002 16:00:09 -0500 (CDT)

-Vikram

--

---

From: "Nitin Vaidya" <[email-masked]>
Date: Thu, 19 Sep 2002 13:26:57 -0500

Phil:

- nitin

-----Original Message-----

Best regards,

Phil

-----Original Message-----

Hi Sumeeth,

Thanks,

John Mullen

-----Original Message-----
From: Sumeeth Nagaraj [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 10:45 AM
To: Mullen, John P. (Contractor); Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Hello John,

Best Regards,
Sumeeth
----- Original Message -----

they
to
be
your
"perfect"
optimistic
the
and
and
to
packet.
problem
link
problem,
(or
in
Access
the

---

From: Cesar Santivanez <[email-masked]>
Date: Fri, 20 Sep 2002 18:06:17 -0400

Yeah... Nodes may miss RTS/CTSs. Higher loads make the problem
of losing `state information' worse.

To observe how easily RTS/CTS infor may be lost, consider the following
example for single channel operation:

A -- B -- C -- D -- E

Assume that node D transmits a packet to node E (using the RTS/CTS
handshake) and when  the packet is in transit Node A decides
to start transmitting to node B, also using the RTS//CTS hanshake.
 Let's see what node C experience:

(1) C receives Node D's  RTS.
(2) C receives Node D's DATA. (It becomes `jammed' by this transmission)
(3) C receives Node B's CTS  (sent in response of node A's RTS).
Since node C is jammed by the DATA sent from D to E, it can not
succesfully decode node B's CTS. Therefore, node C will not learn that
node B is about to receive a packet. So, node C looses `state' information.

(4) After Node D completes its transmission, node C is free to transmit.
Node C does not know that B is receiving a packet, so he thinks he is free to transmit.
Let's say that node C decides to transmit to node D.

(5) Node C sends an RTS to D, get s a CTS back and starts sending DATA.

At this point, node C's DATA (or even the RTS) collides (at node B) with
the DATA node A'ss ws sending.

The above example illustrates how easy is for a node to loose `state' information.
Moreever, once one node looses state information and start `misbehaving',
he causes other nodes to also loose state info.  For example, if in the
previous example assume that in (4), node D decides to transmit to node C
(instead of node C transmitting to D). Now, 5b will be that node C sends a
CTS answering node D's RTS, and node C's CTS collides (and destroys?? in
no FEC is provided)  with the node A's DATA packet at node B.
Note that at his point node B also looses state information (misses the CTS)  and
therefore it not only lost the packet it was received but it is not aware of the
D --> C comunication and may decide to transmit to A or to respond with
a CTS to future A's RTS. As so on, the `lost of state' virus is propagated in the
network,

Note that similar situations (although less often) can occur at multichannel systems, where
the trigger of `lost of state'  is not jammering of a node due to simultaneous communication
but due to the fact that during normal reception (in a single transceiver system)
a node can only listen to one channel. Thus, if a node is listening in the DATA channel
he will be `deaf' to what is going on in the control channel, and may loose state information.

Hope this helps

Cesar

---

From: Cesar Santivanez <[email-masked]>
Date: Fri, 20 Sep 2002 18:06:17 -0400

A -- B -- C -- D -- E

Hope this helps

Cesar

---

From: Cesar Santivanez <[email-masked]>
Date: Tue, 24 Sep 2002 09:46:21 -0400

Brahim BENSAOU wrote:

> This was an interesting example, except that it does not take
> account of the different time scales under consideration and
> most importantly it ignored the double dimension of the
> carrier sensing mechanism of 802.11.

Actually, I tried to make the example related to the general RTS/CTS handshake
and somewhat independent of any particular protocol.

Regarding your comments I agree that generally the sensing range is greater than
the transmission  range (distance -- or patloss -- needed to  successfully decode packets).
However, this is not necessaryly an advantage, since the greater the sensing range,
the worse the `exposed terminal' problem become. I have no doubt that small
carrier sensing threshold in a 802.11-like protocol will tend to reduce the
hidden terminal problem, but at the cost of reducing spatial reuse due to the
exposed terminal problem.  So, obviously you do not want to make this value
too small nor to have a large `sensing range'. In the other hand, being more
`aggressive' -- i.e. increasing the carrier sensing threshold to better exploit spatial
reuse --  may initially increase throughput but after a point it will
induce to many collisions due to the hidden terminal problem.

Besides that, you can not guarantee that in 802.11 the sensing range will be twice
the transmission range. Obviously this depends on the propagation model
you are using. With obstacles, etc., pathloss may decay way faster than you
expected. In the scenarios I play with, this is usually the case and that is
why I picked the example below. But you can easily think of other examples
of situation when you loss `state' information.  IMHO, the true of the matter is: losing
state information is not the exception but the norm in 802.11-like protocols,
at least in scenaros where pathloss decay is dominated by obstructions instead of
distance.

BTW, I am interested at looking at your sim results, specially if you
played around with the carrier sensing threshold.  Is there a place where
I can look at them??

Thanks

Cesar

> In 802.11 we are talking about distances of around 250 m a hop
>  to be able to decode the packets thus a propagation delay of
> the order of magnitude of 1 microsecond (right?).
>
> Before node C starts the RTS it needs to defer (DIFS), backoff
> and then send and RTS, the backoff timer is dicrete and counted
> in slots of 6 microseconds each (if I remember well).
> Each slot of backoff gives any frame the time to propagate
> around 6 hops away, I believe that's enough time to cover two hops.
>
> The energy of the signal decays with a power of the distance so
> what about hidden terminals ...
> 802.11 mandates two types of sensing:
> - packet sensing done by the MAC layer. Packets  can be decoded if
> they reach the station at a given energy level they thus
> contribute to updating the station's NAV. and
> - carrier sensing done by the physical layer at another lower
> energy level which mandates that a station
> that hears a level of energy higher than a given threshold
> must defer for a random time and try again later.
> Thus even when a station is two hops away it can potentially
> defer for a random time because it can detect activity on the channel.
>
> Going back to the example, normally, node B will not reply with
> a CTS to A in the first place, because when it gets A's RTS, it
> senses the carrier and although it can't decode the data packet
> from D to E it can probably detect the transmission in the
> physical layer and defers ... as mandated by 802.11.
>
> Assuming that B sends the CTS to A anayway, in 4) node C indeed KNOWS
> that node B is receiving "something" because it can sense
> the carrier (not the packet).  So instead of starting to
> send it will defer for a random time and try again later.
>
> We did some simulations on the same simple topology in NS-2
> and played with the two thresholds and the results were
> amazingly different. (I do advise many to verify their
> simulations, because the 250 m distance in NS corresponds
> in fact to packet sensing, so when you assume that you
> have hidden terminals and all that jazz, they are
> not really hidden because they continue sensing
> each other at the physical layer If I remember well
> our calculations with the default thresholds of NS-2
> put the distance of complete hidden-ness at 550 m.)
>
> Now going back to Vikram's `state' information, yeah I agree that
> the more sensitive is the information you carry as a piggyback
> to RTS and CTS, (and his is sensitive) the more vulnerable is your
> protocol to the hidden and exposed terminal problem, because
> you can loose such information and the worse is that such "loss"
> is location dependent, some nodes get the information and others
> don't yet such nodes can compete with each other. As a consequence
>  we loose consistency in the state information thus coordination.
>
> my two cents.
>
> - B.
>
> Cesar Santivanez wrote:
> >
> Brahim Bensaou             | Computer Science Department.
> Assistant Professor        | Hong Kong University of Science &
> Technology
> [email-masked]           | Clear Water Bay, Kowloon, Hong Kong.
> http://www.cs.ust.hk/~csbb | Ph: +852 23587014, Fax: +852 23581477

---

From: Cesar Santivanez <[email-masked]>
Date: Tue, 24 Sep 2002 09:46:21 -0400

Thanks

Cesar

---

From: Brahim BENSAOU <[email-masked]>
Date: Tue, 24 Sep 2002 16:15:43 +0800

my two cents.

- B.

---

From: Brahim BENSAOU <[email-masked]>
Date: Tue, 24 Sep 2002 16:15:43 +0800

my two cents.

- B.