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

From: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Date: Thu, 19 Sep 2002 18:16:43 +0930

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

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 19 Sep 2002 07:47:42 -0600

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,

failure by ad-hoc routing protocol suchb as DSR, to initiate a route
discovery.

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?  

(DBTMA), and hence the above assumption is reasonable. (assuming that I am
only

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?

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 19 Sep 2002 09:08:24 -0600

Hi Jing,

I agree that solving the exposed terminal problem will increase throughput,
but I don't see how to do this without introducing some sort of signaling,
which will lead to consequent delay and overhead.  Certainly, a MAC that
solves this problem would improve the performance of an actual network.
However, it would still have some additional delay and/or loss of bandwidth,
compared to the "perfect" MAC Liaw was considering.

:-)

John Mullen

-----Original Message-----
From: Jing Deng [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 8:48 AM
To: [email-masked]'
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi John,

I have a slightly different view regarding to the hidden/exposed terminal
problem. While the hidden terminal problem may degrade the transmission
throughput and increase the overall delay (so we need to solve it), the
exposed terminal problem is actually "beneficial" if it is solved.

The reason is that exposed terminals should re-use the channel, but they
will not be allowed to do so if the MAC layer protocol is not designed
carefully.

By solving the exposed terminal problem, we can actually improve the
throughput and delay performance because of the space reuse of the
shared channel.

So solving the problem does not introduce "extra waiting". On the
contrary, it shortens the unnecessary waiting.

Best Regards,

Jing

----------------------------------------------------
Dr. Jing Deng             Email: [email-masked]
2-191 CST, CASE Center    Phone:  (315) 443-3029 (O)
Syracuse University
Syracuse, NY 13244
---------------------- @_@ -------------------------

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 19 Sep 2002 11:32:02 -0600

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

---

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,

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 -----

_______________________________________________
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: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 19 Sep 2002 12:54:27 -0600

Sorry about this, but I just got an image of people walking around with
little log-periodic antennas (they would have to be about five inches high)
on their heads connected to little motors that rotate them.

It would be an interesting fashion statement.  Maybe the next status symbol?

:-)

John Mullen

-----Original Message-----
From: David Young [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 12:48 PM
To: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

> 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
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 19 Sep 2002 12:54:27 -0600

:-)

John Mullen

-----Original Message-----
From: David Young [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 12:48 PM
To: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Phillip,

Dave

---

From: Phillip Neumiller <[email-masked]>
Date: Thu, 19 Sep 2002 15:33:29 -0400

YES! Smart antennas that are VERY small are THE answer for MANETs!

-----Original Message-----
From: David Young [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 2:48 PM
To: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Phillip,

Dave

---

From: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Date: Fri, 20 Sep 2002 18:01:31 +0930

Hi John and many others,

Thank you for all your responses.

It seems to me that it is next to impossible to have a "perfect" MAC (or still
far off). So I would take "perfect" MAC to mean a MAC where the transmission is
not significantly hidden by the hidden- & exposed- terminal problems. Can
someone explain to me why the problems cannot be solved with dual-channel MAC
such as the Dual Busy Tone Multiple Access(DBTMA) by Haas, etc? Isn't DBTMA
designed to solve the above problems?

Thank you, and have a nice weekend.

-----Original Message-----
From: Mullen, John P. (Contractor)
[mailto:[email-masked]]
Sent: Thursday, 19 September 2002 23:18
To: Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]'
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi Liaw,

:-)

John Mullen

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

Hi,

---

From: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Date: Fri, 20 Sep 2002 18:01:31 +0930

Hi John and many others,

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

Hi Liaw,

:-)

John Mullen

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

Hi,

---

From: Phillip Neumiller <[email-masked]>
Date: Fri, 20 Sep 2002 08:52:44 -0400

Given three mobile nodes:

A - B - C

A can't see what C is doing  and will occasionally cause
interference a B.  That is the hidden node problem.  The
RTS/CTS/DATA/ACK is used to "treat" this condition but it
does not cure the disease the way tiny smart antennas could.

-----Original Message-----
From: Shweta Bhandare [mailto:[email-masked]]
Sent: Friday, September 20, 2002 12:07 AM
To: Phillip Neumiller
Cc: Mullen, John P. (Contractor); Sumeeth Nagaraj; [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

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.

Phillip Neumiller wrote:
>>aware of any MANET protocols that attempt to solve these problems, but
> 
> they
> 
>>2.  It depends what you mean by "perfect."  The goal of the MAC layer is
> 
> to
> 
>>media.  The hidden and exposed terminal problems are situations that can
> 
> be
> 
>>There is also a matter of control packets, such as RTS and CTS.  So, if
> 
> your
> 
>>in some way, you will have a realistic simulation.  However, if by
> 
> "perfect"
> 
>>introduce a more realistic MAC model, your results will be overly
> 
> optimistic
> 
>>differences among the alternatives.  However, when he introduced noise,
> 
> the
> 
>>3.  Again, you should allow for the impact of the solution on bandwidth
> 
> and
> 
>>could make multipath very efficient.  It is also typical that the MANET
> 
> and
> 
>>there is a single path, only one of those nodes will rebroadcast in order
> 
> to
> 
>>rebroadcast, all nodes covered by c would have already received the
> 
> packet.
> 
>>Good luck in your research.  This is an interesting and significant
> 
> problem
> 
>>multihop (i.e. MANET) environment.  For example, it can causes "false"
> 
> link
> 
>>1. The hidden-terminal and exposed terminal problems are MAC layer
> 
> problem,
> 
>>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
> 
>>solved in the future by new MAC, such as the Dual Busy Tone Multiple
> 
> Access
> 
>>I would appreciate if you can help me, or point me to works that address
> 
> the
> 
>>problem.  Thank you.

---

From: Phillip Neumiller <[email-masked]>
Date: Fri, 20 Sep 2002 08:52:44 -0400

A - B - C

-----Original Message-----
From: Shweta Bhandare [mailto:[email-masked]]
Sent: Friday, September 20, 2002 12:07 AM
To: Phillip Neumiller
Cc: Mullen, John P. (Contractor); Sumeeth Nagaraj; [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Thanks,
Shweta

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Fri, 20 Sep 2002 07:08:57 -0600

Hi,

Just a bit more on clarification.

The issue is that Node 3 refrains from transmitting because it detects Node
2's carrier.  On a wired shared channel, such as Ethernet, hearing an active
signal indicates the channel is busy, so the protocol dictates that Node 3
should wait.

However, radio channels are not like wired channels.  It is possible for one
to have a channel locally busy, yet available at another location.  Node 3
could actually transmit in this case.  The signal from Node 2 will not cause
a data collision at Node 4 and a signal from Node 3 will not cause a data
collision at Node 1.

The problem is how to make Node 3 aware of the fact that it can transmit.
That is, Node 3 must know:

 1.  That its transmission will not cause a data collision at any of the
intended receivers of the current transmission and

 2.  That the current transmission will not cause a data collision at any of
the intended receivers of its transmission.

Bearing in mind that the standard error of the best RF propagation
prediction models is about 6dB and that each node must know, not only the
location of each affected node, but also salient characteristics of the
intervening terrain, it is a highly non-trivial problem.

John Mullen

-----Original Message-----
From: Sumeeth Nagaraj [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 10:33 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

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: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Fri, 20 Sep 2002 07:08:57 -0600

Hi,

John Mullen

-----Original Message-----
From: Sumeeth Nagaraj [mailto:[email-masked]]
Sent: Thursday, September 19, 2002 10:33 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Hi,

1         2             3             4

Hope I am clear 8-)

Best Regards,
Sumeeth

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Fri, 20 Sep 2002 17:57:53 -0400

> The idea of using multiple codes was to remove the RTS-CTS over head.
> RTS-CTS can cause congestion problems for a netowork with 
> high density of
> nodes.
> 
> You can give a look at the channel access scheme proposed by 
> Dr. Schlegel:
> Here they have a common  header spread with a identical  code 
> that uses the
> basic aloha scheme and the data is spread by a random 
> spreading code, that
> is sent to the destinatioin in the header.
> http://www2.elen.utah.edu/~schlegel/publications/KotSch01.pdf
> 
> and also, the MAC protocol proposed by Dr. Rabaey for the pico radio
> project(BWRC).

How intriguing. Seems like going to a cellular telephone CDMA-like protocol, to establish unique, signaled links between hosts. The difference being that the initial setup is done with an aloha protocol instead of having a base station keep things organized?

Bert

---

From: Phillip Neumiller <[email-masked]>
Date: Mon, 23 Sep 2002 09:02:11 -0400

Nothing special from me, but I am aware of some DARPA research
that if commercialized could indeed revolutionize antennas.  This
would make ad hoc networks much more practical.  Its still probably
many years from being commercially viable though.  Meta-materials.

See:

http://www.darpa.mil/dso/thrust/md/meta.htm

I think maybe you were going down the MIMO road, and that looks
promising too.

-Phil

-----Original Message-----
From: Fred L. Templin [mailto:[email-masked]]
Sent: Friday, September 20, 2002 6:20 PM
To: Phillip Neumiller
Cc: [email-masked]; [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Hi Phil,

> YES! Smart antennas that are VERY small are THE answer for MANETs!

Are you talking OFDM here, or is there something else on the horizon
that we will soon be seeing?

Thanks,

Fred
[email-masked]

---

From: Phillip Neumiller <[email-masked]>
Date: Mon, 23 Sep 2002 09:02:11 -0400

See:

-Phil

-----Original Message-----
From: Fred L. Templin [mailto:[email-masked]]
Sent: Friday, September 20, 2002 6:20 PM
To: Phillip Neumiller
Cc: [email-masked]; [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Hi Phil,

Thanks,

Fred
[email-masked]

---

From: Phillip Neumiller <[email-masked]>
Date: Mon, 23 Sep 2002 09:05:41 -0400

Let us assume that, for the sake of argument, one could construct
an antenna capable of synthesizing perfectly power controlled
pencil beams that could track other mobiles as they move
relative to each other.  If this *WAS* possible, wouldn't all
forms of self-interference be more-or-less mitigated?  Of course
multi-path makes life more complicated (and that would need to
be addressed), but I am just trying to get at what the heart of
the issue is, i.e. the incessant use of omnis in MANETs.

Thanks,

Phil

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

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: Phillip Neumiller <[email-masked]>
Date: Mon, 23 Sep 2002 09:05:41 -0400

Thanks,

Phil

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

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: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 23 Sep 2002 07:29:23 -0600

Hi Phil,

The problem with such a hypothetical solution is that it ignores the very
real problem of keeping each node informed of the location of all others
nodes.  If each communicator uses such beams for communications, how will
other nodes find out where the other nodes are?  How will a new node enter
the network? Even if there were pencil beams and these could be used for
communications, there would still be a need for omnidirectional
broadcasting.  Thus, any antenna system must be able to function in both
ways.

If both transmitter and receiver employ directional antennas, we have the
problem of how a node would know another node is attempting to contact it.
Therefore, at least when starting up the link, the receiver can be expected
to have an omni receiving antenna.

If the option to use beams exists, the implicit gain of the focused beam
would imply that two nodes can communicate reliably over much greater
distances than in the omnidirectional mode.  For example, if both antennas
show a 6 dB gain, the effective signal will be sixteen times as strong, so
the effective range could be from two to four times as great.  If that is
the case, then we will need MANET protocols that seek to locate a node
precisely in order to set up a temporary point-to-point link, rather than
find a multi-hop path.  Of course, if the range is too far, there will also
be a need to set up multihop paths, but each link could be of the form of
vectors, rather than nodes.  This may be worth it, but it will be more
complex.

There is at least one other wrinkle in this plan.  With omnidirectional
broadcasts, it is not always necessary to send an ACK.  If A sends a packet
to B for forwarding, as B rebroadcasts the packet, A hears it and knows all
is well.  An explicit ACK in this case is not needed.  Directional antennas
will foster a need for the explicit ACK in almost all cases.

This is not to say that directional antennas are a bad idea.  It just means
that a directional mode would require an omnidirectional mode for support
and the protocols would be more complex.  The question of whether or not
this is a good idea would turn on the tradeoff between the higher complexity
(and implied lower reliability) verses any increase in performance.  This is
not possible to gauge at this time because the technology to carry this off
is not yet available.

John Mullen

-----Original Message-----
From: Phillip Neumiller [mailto:[email-masked]]
Sent: Monday, September 23, 2002 7:06 AM
To: Nitin Vaidya; Phillip Neumiller; Mullen, John P. (Contractor);
Sumeeth Nagaraj
Cc: [email-masked]

Thanks,

Phil

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

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: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 23 Sep 2002 07:29:23 -0600

Hi Phil,

John Mullen

-----Original Message-----
From: Phillip Neumiller [mailto:[email-masked]]
Sent: Monday, September 23, 2002 7:06 AM
To: Nitin Vaidya; Phillip Neumiller; Mullen, John P. (Contractor);
Sumeeth Nagaraj
Cc: [email-masked]

Thanks,

Phil

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

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: Vikram Dham <[email-masked]>
Date: Mon, 23 Sep 2002 10:02:36 -0400

Hello John & Phil,

  We have been looking into use of Smart Antennas in MANET and have had to 
modify mac as well as routing protocols to accomodate smart antennas into 
network effectively.

  Using Smart Antennas doesn't necessarily mitigate interference unless use is 
made of power control mechanisms besides the assumption of knowdelge of 
location of destination nodes in network.

 As pointed by John there is possibility of establishing "extended links " 
"multihop term -- used by John" by orienting receive and transmit antennas of 
communicating nodes towards each other. This would involve use of signaling 
mechanism based on top of routing layer to send orienation commands. The 
question left answered is information about location of nodes ? One safe way 
out might be to just assume the use of GPS by all nodes, ( I wonder how cost 
effective it would be ? ) Another option which might be worth exploring is 
extending approaches such as CRICKET ( developed at LCS MIT ) to scenarios 
which invovle use of smart antennas. Smart Antennas provide edge over omni 
directional antennas as they can provide information regarding angle of 
arrival of arriving signal. Using received signal power and angle of arrival 
it might be possible to establish relative location of nodes in network 
atleast in line of sight environments.

 Besides the possibility of establishing extended links the problem of routing 
becomes even more murkier because of the availablity of multiple interfaces on 
node using smart antennas.

 We have been running simulation for MANETS with Smart Antennas and the 
performance gain acheived with respect to omni directional nodes is drastic.It 
might be sometime before smart antennas reach commerical setups but their 
incorporation would definately be a challenge for present mac and routing 
protocols. I even wonder if the time being spent in developing routing 
protocols assuming omni directional antennas is worth the effort :)

Best Regards

Vikram Dham

>===== Original Message From "Mullen, John P. (Contractor)" 
<[email-masked]> =====

---

From: Vikram Dham <[email-masked]>
Date: Mon, 23 Sep 2002 10:02:36 -0400

Hello John & Phil,

Best Regards

Vikram Dham

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 23 Sep 2002 08:21:20 -0600

Hi Vikram,

The problem with GPS is that you also need to know the intervening terrain
and any local anomalies that would interfere with or modify a LOS path.
This can me a very tricky problem in an urban setting.  The smart receiving
antenna looks promising, though, since it sidesteps these problems.  The
trouble is, how does the one initiating the transmission decide which way to
point the antenna?  

If the platform is in motion, you would need some sort of correction element
to maintain the orientation.  If a car makes a left turn, something has to
know that and shift the antenna orientation 90 degrees to compensate.  Back
in the city, however, this may not be enough.  One may be communicating over
a reflected path, due to no LOS path being available, and as you move, the
manner in which the communication can be effected could be a very complex
problem.  Life becomes even more complicated if motion can be in 3D space,
such as in an airplane or with a PDA.  

John Mullen

-----Original Message-----
From: Vikram Dham [mailto:[email-masked]]
Sent: Monday, September 23, 2002 8:03 AM
To: Mullen, John P. (Contractor); Phillip Neumiller
Cc: manet
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hello John & Phil,

  Using Smart Antennas doesn't necessarily mitigate interference unless use
is 
made of power control mechanisms besides the assumption of knowdelge of 
location of destination nodes in network.

"multihop term -- used by John" by orienting receive and transmit antennas
of 

 Besides the possibility of establishing extended links the problem of
routing 
becomes even more murkier because of the availablity of multiple interfaces
on 
node using smart antennas.

performance gain acheived with respect to omni directional nodes is
drastic.It 

Best Regards

Vikram Dham

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 23 Sep 2002 11:29:17 -0600

Hi Rex,

You are probably right.

I suppose at this time, the useful question is to ask what part of this sort
of thing would require a change in MANET protocols and what part would be
handled in the MAC?

I would advocate handling as much as possible in the MAC because the merit
of this approach will depend on a bunch of factors, including cost.  I
suspect those that want and need it will pay the bucks for the necessary
hardware while others will be satisfied with the omni approach.  Also, I
suspect the solutions will remain proprietary, at least in the short run.  

However, if some element of the interface is important to establish, then it
might be a good idea for the MANET protocol designers address it now.  This
reduces the chance of having to deal with a number of mutually incompatible
MANET-MAC interfaces in the future.

John Mullen

-----Original Message-----
From: Rex Buddenberg [mailto:[email-masked]]
Sent: Monday, September 23, 2002 11:11 AM
To: Mullen, John P. (Contractor); Vikram Dham
Cc: manet
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

Looks like you're getting to the same reasoning that almost everybody else 
gets to when thinking through a revised MAC.  You need two queue's in the 
MAC, one for contention and one for traffic.  In this case, looking at the 
MAC from the physical layer, contention =~ omni -- see who's out there to 
link with (and where they are).  Once you have that data, you can inform the

second queue and set up some kind of planned access (which way to point the 
directional antenna beam when).  

On Monday 23 September 2002 07:21 am, Mullen, John P. (Contractor) wrote:
> trouble is, how does the one initiating the transmission decide which way
> to point the antenna?
>
> If the platform is in motion, you would need some sort of correction
> element to maintain the orientation.  If a car makes a left turn,
something
> has to know that and shift the antenna orientation 90 degrees to
> compensate.  Back in the city, however, this may not be enough.  One may
be
> communicating over a reflected path, due to no LOS path being available,
> and as you move, the manner in which the communication can be effected
> could be a very complex problem.  Life becomes even more complicated if
> motion can be in 3D space, such as in an airplane or with a PDA.
>
> John Mullen

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 23 Sep 2002 11:29:17 -0600

Hi Rex,

You are probably right.

John Mullen

-----Original Message-----
From: Rex Buddenberg [mailto:[email-masked]]
Sent: Monday, September 23, 2002 11:11 AM
To: Mullen, John P. (Contractor); Vikram Dham
Cc: manet
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

something
be

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Mon, 23 Sep 2002 15:49:12 -0400

Sumeeth Nagaraj wrote, concerning

http://www2.elen.utah.edu/~schlegel/publications/KotSch01.pdf:

> I would think its considerably a different idea when compared to the
> cellular systems and applying the idea of multiple codes to 
> mobile ad-hoc
> networks should also be considered?(your inputs please).

Hi Sumeeth,

I have a knee jerk reaction, which is that spreading in IEEE 802.11b seems inadequate to support multiple users in a single 5 MHz frequency band. In fact, it seems that only 8 or 11 chips per symbol are used, respectively for the 5.5 and 11 Mb/s options and for the the 1 and 2 Mb/s options.

>  Every node, has a header  which is spread by a known 
> spreading code and the
> data part is spread by the random code sent to the destination by the
> source. This is done for each packet sent by the source and 
> the random code
> changes each time the source has some data packet to send 
> which is not the
> case in cellular systems.

Without digging through the details of cellular CDMA, however, the difference does not appear to be so great? In the cellular model, the base station negotiates the code for each channel with each mobile unit requesting service, on the synchronization channel(?), before the data stream begins. Seems to me that both systems have to start somewhere to establish the unique code for each data stream, and the only difference here is in the details of how the individual codes are assigned. Thereafter, you have non-shared channels on which data are sent, which seem dedicated to that user and the base station for the duration of the session? Unless I misunderstand the concept, seems to have aspects of circuit switching.

> The available bandwidth is pretty well utilized. The base 
> station still
> exists and they have not said anything to replace the base 
> station as noted
> by you.

Correct you are. But this makes it more similar, rather than less similar, to the telephony model. And less like a MANET.

> Although the success, is in proper detection of the 
> header, which
> is spread using a common spreading code, I would think this 
> should not be
> that problem, the same scenario exists in sending the RTS, 
> CTS , data packet
> and also the ACK in IEEE 802.11. The loss of any of the control/data
> packets, which is very likely to happen, for the Unicast 
> packets, involves
> starting the whole process of sending the RTS-CTS-Data and ACK again.
> Guessing the states of other nodes in the network(locally), 
> as noted by
> Cesar, is one tough job unless the node timeouts and starts 
> all over again.

Yes, I have no problem with the above. But depending on the base station removes this from MANET territiory. It would be interesting to see this channelized concept applied to a true MANET. That would require mobile hosts to simultaneously participate in the Aloha common channel, and then establish unique circuits to forward data between other hosts, using different quasi-orthogonal codes. Hmmm.

Bert

---

From: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Date: Tue, 24 Sep 2002 14:50:39 +0930

Hi, 

It seems that my last email was not sent out to the mailing list.
Thanks.

-----Original Message-----
From: Liaw, Yong Shyang - LIAYS001 
Sent: Friday, 20 September 2002 18:02
To: 'Mullen, John P. (Contractor)'; Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]'
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi John and many others,

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

Hi Liaw,

:-)

John Mullen

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

Hi,

---

From: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Date: Tue, 24 Sep 2002 14:50:39 +0930

Hi, 

-----Original Message-----
From: Liaw, Yong Shyang - LIAYS001 
Sent: Friday, 20 September 2002 18:02
To: 'Mullen, John P. (Contractor)'; Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]'
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi John and many others,

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

Hi Liaw,

:-)

John Mullen

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

Hi,

---

From: "Phil Neumiller" <[email-masked]>
Date: Tue, 24 Sep 2002 09:25:46 -0400

Hi Yong Shyang,

>designed to solve the above problems?

At the risk of riding a dead horse, it seems that Karn's MACA, Haas's DBTM
and other related/derived MAC schemes are treating the "symptom" of hidden nodes
which is caused by the "disease" of omni-directional antennas. 

Hidden node problems don't exist in switched wired networks.  If we could make
antennas behave like switched wired meshes, we would remove the hidden node
problem (for the most part).  There would always be side-lobes and some RF spill-
over to deal with, but that is an engineering problem not a science problem.  

Beacons, broadcasts, initial signal acquisition all use omni-directional coverage, 
but once a link is established it  should do its best to "act like a piece of wire", or in
RF parlance, a motion tracking power controlled pencil beam.  The practicality of
this type of scheme (especially small and inexpensive) is the real engineering 
problem here [a difficult one at that].  

So, in the mean time, while we must use omnis for practical purposes, mult-
channel schemes hybridized with MACA or DBT make perfect sense.  What is not
occuring though is the cross-layer cooperation between the routing protocol and
the MAC layer to enable globally fair/QoS capability in ad hoc networks (to be
fair there is some work published here, but its not a MANET or an IETF thing
at all).

Thanks,

Phil

--
Phillip D. Neumiller ([email-masked])
My PGP key can be imported from the following URL: http://pgpkeys.mit.edu
BTW:  It is undecidable whether an arithmetical formula is true!
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Phil Neumiller" <[email-masked]>
Date: Tue, 24 Sep 2002 09:25:46 -0400

Hi Yong Shyang,

Thanks,

Phil

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Tue, 24 Sep 2002 08:00:10 -0600

Hi Liaw,

At this point, I would say a "perfect" MAC would be one that manages the
hidden- and exposed-terminal problems as well as can be managed.  These, and
other realities of wireless communications, are part of what make MANETs
interesting.  

Current "solutions" are methods to reduce the impact of situations in the
MAC layer.  They are not solutions in the sense that they completely
eliminate the occurrence of the problem.  In addition, each "solution" has a
corresponding set of costs.  

I suppose what is really needed is good canned models of MACs compatible
with the simulation language you are using.  With such models you can
include the MAC effects into your analysis without getting into the messy
details of how they work.  I believe people mention such models here from
time to time here.  However, you might also want to check:

http://students.cs.tamu.edu/youngbae/mac_adhoc.html

John Mullen

-----Original Message-----
From: Liaw, Yong Shyang - LIAYS001
[mailto:[email-masked]]
Sent: Monday, September 23, 2002 11:21 PM
To: [email-masked]'
Subject: FW: [manet] Hiden- & exposed terminal problem in MANET

Hi, 

-----Original Message-----
From: Liaw, Yong Shyang - LIAYS001 
Sent: Friday, 20 September 2002 18:02
To: 'Mullen, John P. (Contractor)'; Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]'
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi John and many others,

It seems to me that it is next to impossible to have a "perfect" MAC (or
still
far off). So I would take "perfect" MAC to mean a MAC where the transmission
is
not significantly hidden by the hidden- & exposed- terminal problems. Can
someone explain to me why the problems cannot be solved with dual-channel
MAC
such as the Dual Busy Tone Multiple Access(DBTMA) by Haas, etc? Isn't DBTMA
designed to solve the above problems?

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

Hi Liaw,

:-)

John Mullen

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

Hi,

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Tue, 24 Sep 2002 08:00:10 -0600

Hi Liaw,

John Mullen

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

Hi, 

-----Original Message-----
From: Liaw, Yong Shyang - LIAYS001 
Sent: Friday, 20 September 2002 18:02
To: 'Mullen, John P. (Contractor)'; Liaw, Yong Shyang - LIAYS001
Cc: [email-masked]'
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi John and many others,

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

Hi Liaw,

:-)

John Mullen

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

Hi,

---

From: "Martin Layley" <[email-masked]>
Date: Tue, 24 Sep 2002 15:31:16 +0100

The last time someone said to me "that is an engineering problem not a science problem.", it turned out that they had ignored several laws of physics.

		Martin Layley
		SERI

-----Original Message-----
From: Phil Neumiller [mailto:[email-masked]]
Sent: 24 September 2002 14:26
To: [email-masked]; [email-masked]
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi Yong Shyang,

Thanks,

Phil

The mail message has been scanned by MAILsweeper
for content analysis.

---

From: "Martin Layley" <[email-masked]>
Date: Tue, 24 Sep 2002 15:31:16 +0100

Martin Layley
		SERI

-----Original Message-----
From: Phil Neumiller [mailto:[email-masked]]
Sent: 24 September 2002 14:26
To: [email-masked]; [email-masked]
Subject: RE: [manet] Hiden- & exposed terminal problem in MANET

Hi Yong Shyang,

Thanks,

Phil

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 30 Sep 2002 06:52:49 -0600

Hi Brahim,

Pretty good two cents!

I just want to point out that a terminal can also be hidden due to an
obstruction, such as a building or a geographical feature, in which case the
sending terminal might not detect the carrier.

I also remember from an earlier post by somebody that the ratio of detection
to reception range can be as small as 1.1 and as large as 2, so depending on
the carrier frequency, etc., results may vary.

John Mullen

-----Original Message-----
From: Brahim BENSAOU [mailto:[email-masked]]
Sent: Tuesday, September 24, 2002 2:16 AM
To: Cesar Santivanez
Cc: Vikram Kanodia; [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

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.

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.

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 30 Sep 2002 06:52:49 -0600

Hi Brahim,

Pretty good two cents!

John Mullen

-----Original Message-----
From: Brahim BENSAOU [mailto:[email-masked]]
Sent: Tuesday, September 24, 2002 2:16 AM
To: Cesar Santivanez
Cc: Vikram Kanodia; [email-masked]
Subject: Re: [manet] Hiden- & exposed terminal problem in MANET

my two cents.

- B.