Subject: [manet] Temporal Logic

From: Alicia Triviño <[email-masked]>
Date: Tue, 02 Mar 2004 16:33:02 +0100

Does anyone know where I could find any paper about "temporal logic" and ad 
hoc network?

Thanks in advance

Alicia Triviño                               / Tl. +34-95.213.28.44
Dpto. Tecnologia Electronica
E.T.S. Ing. Telecomunicacion
Universidad de Malaga
Campus Universitario de Teatinos
29071 Malaga, Spain

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

---

From: "ying ge" <[email-masked]>
Date: Tue, 2 Mar 2004 13:29:08 -0500

Dear group,

I'm looking at the proposed OLSR_RFC MPR selection mechanism, and have the
following questions:

1) in step 1 of MPR calculation -- "Start with an MPR set made of all
members of N with N_willingness equal to WILL_ALWAYS"

     Does it mean that a "WILL_ALWAYS" neighbor has to be selected as MPR
even if it has no connection to any 2-hop neighbors? In this case, the MID
and TC messages would be unnecessarily relayed by that neighbor, which may
make the wireless media busier. Can we put it as "Start with an MPR set made
of all members of N with N_willingness equal to WILL_ALWAYS, and N has at
least one 2_hop_neighbor"?

2) in step 4.2 -- "Select as a MPR the node with highest N_willingness among
the nodes in N with non-zero reachability. In case of multiple choice select
the node which provides reachability to the maximum number of nodes in N2.
In case of multiple nodes providing the same amount of reachability, select
the node as MPR whose D(y) is greater. Remove the nodes from N2 which are
now covered by a node in the MPR set. "

     If we select neighbors with higher willingness as MPR, regardless how
many two hop neighbors it is connected to, may we ended up choose a lot of
MPRs? If there is too many MPRs in the network, the control overhead of the
OLSR may be very high, which may degrade the routing protocol's performance
(more data packet may be dropped because of the busy media, the end-to-end
delay of the data packets may be very long...).

     I have such a question because I used to introduce QoS routing into
OLSR, and tried to select as MPR the neighbors which have the best QoS
conditions, which is similar to the concept that "to select as the highest
willingness neighbors as MPR". From the OPENT simulation, I found that with
such mechanism, much more MPRs is selected, compared with the mechanism
proposed in OLSR draft version 3 (select the neighbor which have the most
reachability to the 2-hop-neighbors). Further more, the OPNET simulation
result shows that because of the large numbers of MPRs in the network, the
overhead is high, and the routing protocol's performance ("packet delivery
ratio" and "end-to-end-delay" for data packets) is not satisfactory.

     My idea to solve this problem is to define a formula, and put the
neighbor "willingness" and "reachability to 2-hop-neighbors" as two
inputs -- such as Weight(willingness, reachability) = neighbor' willingness
+ neighbor's reachability. Then select the neighbour that has the highest
"Weight" as MPR. Will this work? Please give me your ideas...

Maybe there are some special reasons or special scenarios the proposed MPR
selection mechanism should apply? If yes, would you please kindly tell me?

Thanks and Best regards

Ying

Ying Ge
Communications Research Centre Canada | Centre de recherches sur les
communications Canada
3701 Carling Ave. | 3701, avenue Carling
PO Box 11490, Station H | CP 11490, succursale H
Ottawa ON K2H 8S2 | Ottawa (Ontario) K2H 8S2
(613) 998-2819 | [email-masked] |
Web site / Site web : www.crc.ca
Government of Canada | Gouvernement du Canada

---

From: Justin Lipman <[email-masked]>
Date: Wed, 3 Mar 2004 12:02:41 +1100

Hi Ying,

Just read your email and thought I might offer some thoughts.

> delay of the data packets may be very long...).

I have a paper on a more generic form of mpr selection which is called Utility 
Based Flooding. The following is a link to the paper. 

http://www.cse.unsw.edu.au/~justinl/raid_icon03.pdf

UBF has similar performance to MPR in terms of the number of relays selected, 
but more importantly, allows for those relays to be selected based upon their 
overall utility.

> "Weight" as MPR. Will this work? Please give me your ideas...

You can apply the above technique to the UBF algorithm by using a utility 
function which is a function of willingness and reachability.

If you use the greedy MRP algorithm as used by OLSR, then your choice of relay 
nodes is limited as the 1st step of the algorithm always selects those 1 hop 
neighbours with distinct 2-hop neighbours first, irrespective of their 
utility (willingness). Thus the remaining number of possible relays that may 
be selected based upon willingness is rather limited. UBF circumvents this 
problem by removing this 1st step and prioritising the selection of relays 
based upon the highest utility. Thus the best relays nodes are selected 
first. Those 1-hop relays that "must be selected" because of distinct 2-hop 
neighbours and which have a low utility are selected at the end (to satisfy 
coverage). This introduces a little more overhead than MPR, however it allows 
for the best relays to be selected!

I think you may also find that optimised flooding mechanisms such as MPR 
suffer in the presence of background traffic be it data or other broadcasts. 
By suffer, I mean the number of nodes in the ad hoc network that are reached 
by a flood is greatly reduced. You can see the reliability results of some 
optimised flooding mechanisms (MPR, LMST) and Blind flooding in the following 
paper: Thus as the network traffic increases, the number of nodes receiving 
route request information or link state updates decreases.

http://www.cse.unsw.edu.au/~justinl/rmst.pdf

Hope this helps,
Justin

-- 
Research Associate
Smart Internet Technology Cooperative Research Centre
http://www.titr.uow.edu.au/~justin

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 2 Mar 2004 20:40:50 +0100

Dear Yi,

My comments are in the text.

Philippe
----- Original Message -----
From: ying ge <[email-masked]>
To: <[email-masked]>
Sent: Tuesday, March 02, 2004 7:29 PM
Subject: [manet] OLSR - questions on MPR calculation

> least one 2_hop_neighbor"?

Basic OLSR routers should not have willingness equal to WILL_ALWAYS. We use
WIL_ALWAYS when the network contains
a set of node that the administrator wants to manually set as a wireless
backbone.
> delay of the data packets may be very long...).
This is true to some extend for broadcast control traffic (the increase is
not that big) but not true for data traffic which should take the most
bandwidth. The routes are still the shortest path with willingness, excepted
that routes will take relay nodes with highest willingness. Willingness
should be used with care, for example in order to reflect the battery
capacity of the host. It helps to spread the broadcast relaying so that it
does not kill the battery of some relay faster than it could be.