A Hint-Based Probabilistic Protocol for Unicast Communications in
MANETs
R. Beraldi, L. Querzoni, R. Baldoni Dipartimento di Informatica e Sistemistica
Universit`a di Roma “La Sapienza”
Via Salaria 113, 00198, Roma, Italy
Abstract
Point-to-point transmissions represent a fundamental primitive in any communication network. Despite many proposals have appeared in the literature, providing an ef- ficient implementation of such an abstraction in Mobile Ad Hoc Networks still remains an open issue.
This paper proposes a probabilistic protocol for unicast packet delivery in a MANET. Unlike the classical routing protocols, in our proposal packet forwarding is not driven by a previously computed path. Rather, the nodes of the network exploit a set of routing meta-information (called hints) to discover a path to the destination on-the-fly.
This assure robustness to topological changes, while re- quiring a very low overhead.
A node gathers hints from the nodes located within a small number of hops (called the protocol’s lookahead) from itself. As showed through simulations, very good performance can be obtained with small lookahead. The main statistical properties of hints have been investigated through an analytical model, which is also reported in the paper.
1. Introduction
Mobile Ad hoc networks (MANETs) are emerging as an important class of ad hoc networks with many applications in the real life [8]. In a MANET two nodes can communi- cate directly only when they lie within one another’s trans- mission range. This is quite an unlikely condition since the network’s diameter is usually much bigger than the transmis- sion rane, hence unicast packet transmission is multi-hop in nature. Multi-hop communications are challenging in time- varying topologies. Despite many proposals appeared in the literature, finding an efficient solution to such a problem still remains an open issue.
The usual approach to implement unicast can be classified as deterministic and structure-based. The goal of a protocol of
This work is part of the “IS-MANET” project.
this kind, namely a routing protocol, is to maintain some log- ical structure on top of the physical network, which nodes ex- ploit for taking their packet forwarding decisions. For exam- ple, in the class of proactive routing protocols such a structure is a set of N trees, each rooted at one of the N nodes form- ing the MANET, which are stored in a distributed fashion into the nodes’ routing table. The next-hop node is obtained by a simple table’s lookup and thus packet latency is mini- mized. However, maintaining the routing information can be- come not efficient under frequent topological changes. Rep- resentative proactive protocols are: Destination-Sequenced Distance Vector (DSDV) [5], Optimization Link State Rout- ing (OLSR)[13] and Topology Based on Reverse Path For- warding (TBRPF) [3].
In reactive protocols a logical path from a source node to the destination is discovered on-demand and maintained af- terwards. The main drawback of such a solution is that the de- lay required to discover or repair a path can be perceived at the application level; moreover an interference with the conges- tion control mechanism can arise (for example, a route break detection normally takes several seconds [17]). Examples of protocols of this family are: Dynamic Source Route (DSR) [14] and Ad hoc On Demand Distance Vector (AODV) [6].
A vast number of routing protocols are proposed in the lit- erature along these lines, with several variants, e.g., hybrid protocols [11]. The interested reader can refer to [1] for a sur- vey on routing protocols.
Probabilistic algorithms provide an interesting alternative to realize unicast packet delivery in dynamic networks, due to their resilience to topological changes, as well as the low- overhead, scalability and locality properties they enjoy. In the context of MANET, probabilistic protocols have already been applied to improve the route discovery process [10], as well as an alternative to implement network wide broadcast [16]. However, at the best of our knowledge, only few papers have explored the more important option of embedding the probabilistic logic in the forwarding process itself. The solu- tions appeared in the literature aim at defining a biased ran- dom walk. For example, in [15] the behavior of a community of ants is mimed. Tuning the parameters of the protocol is, however, not trivial in this technique. Moreover, before data packet can be sent, a path still needs to be discovered through
W τLG W W W W
∆WLG W± W
5 QRGHL
QRGHG
Figure 1. Meaning of time information.
natural random walkers.
In this paper we introduce a framework for probabilis- tic forwarding in mobile environments, which exploits meta- information (in the form of hints) to direct a packet towards the general direction of the destination. Some preliminary idea of the protocol can be found in [2]. A hint hidcomputed by a node i w.r.t. a destination node d, is a positive value which indicates the chance of i being in the neighborhood of d. The lower the hint the higher such a probability, with the singu- lar case of hid= 0 when i and d are 1-hop neighbors i.e., they lie within one another’s transmission range. Each node i peri- odically receives the hints for d from the nodes located at dis- tance at most of L hops from itself (the value L is called the Lookahead of the protocol).
Packets are forwarded as follows. On receiving a packet destined to d, a node i uses the neighbor from which the best (lowest) hint has been received, and such that it didn’t see the packet before as next-hop node. If no nodes can be selected the packet is discarded. This procedure is repeated at each for- warding step. This algorithm is clearly resilient to topological changes. If the selected next-hop node cannot be reached, an- other one can promptly be used. Moreover, we argue that a small lookahead can be sufficient for a node to gather cor- rect hints; thus, a small amount of control overhead is re- quired. There is no guarantee that the next-hop node lies on a path towards the destination and this qualifies the proto- col as a probabilistic one.
The hint of i w.r.t. d is defined as hid=∆Tid
τid , where ∆Tid
is the time elapsed since d has most recently moved out of the i’s transmission range, and τidis the duration of the last wire- less link established between i and d, see Figure 1. In gen- eral, if ∆Tidis small, the nodes i and d are with high prob- ability in the nearby of each other. This intuitive conjecture has already been exploited in [9], where some numerical ev- idence is also given (in [9] this time interval is called the en- counter age). The value τidprovides a simple way to estimate the relative speed of the two nodes. Thus, the rationale is to assume that a correlation between hidand the distance be- tween i and d exits. Some insight into such a relationship has been obtained through an analytical model reported in the paper. Note that for sufficient dense networks a hint also pro- vides a way to estimate the distance in number of hops be- tween i and d.
The performance of the forwarding protocol has been stud-
ied through simulations and compared against the AODV routing protocol. The results show that good delivery perfor- mance can be obtained while generating low overhead.
The paper is organized as follows: the next Section sum- marizes the main works related to our approach; Section 3 provides model and assumptions; Section 4 describes the hint based protocol; in Section 5 an analytical model for study- ing the hint-distance correlation is presented. Simulation re- sults are provided in Section 6 and a conclusion in Section 7.
2. The Hint-based Protocol
2.1. Model and notations
We consider a system composed of N mobile devices, here- after also called nodes, each uniquely identified. We say that two nodes are direct neighbors, or simply neighbors, if they lie within one another’s transmission range. We assume that a node, on the average, has ˜N neighbors. We call the Looka- head Zone of node i with parameter L, ZL(i), the set of nodes at distance less than or equal to L hops from i.
The transmission range is a circle with radius R, cen- tered at the sending node. A node i can use the primitive:
(i) send(pkt, j) to send the packet pkt to j with the result of the transmission notified; (ii) bcast(pkt) to unreliably send the packet pkt to the nodes within the transmission range. In the latter case, the result of the transmission is unknown.
Each node maintains a local clock, not synchronized with the others. The value of the local clock is accessible through the clock() primitive.
When the distance between two nodes, say i and j, is de- creasing (increasing) and it reaches R at time t, we say that i and j come in contact (loose their contact) at time t. From the time when they came in contact until they lost the con- tact we call them neighbors. This time interval is called the duration of the contact or, equivalently, the duration of the link between i and j, denoted τij.
2.2. Algorithm description
Let us first describe the algorithm in general terms. Each node i is in charge of computing the hint hidfor any possi- ble destination node d. The hint hid(t) computed at time t is zero if at this time i and d are neighbors, while it is ∞ if they never came in contact before t. If, however, they were 1-hop neighbors in the past and their last contact was lost at time t∗, then the hint is hid(t) = t−tτ ∗
id . Hints are dissemi- nated within at most L hops from the estimating node.
When a node n needs to forward a packet destined to d, it sends the packet to the neighbor n∗ which provides the best hint among the neighbors that never forwarded the same packet before. Note that a hint can be generated by a node be- hind n∗. If no such node can be found, then the packet is dis- carded.
Figure 2 shows an example of packet forwarding from the source node S to destination D, assuming lookahead L = 1.
Hints are reported close to the generating nodes.
Figure 2. An example of packet forwarding.
2.3. Algorithm details
We now describe an implementation of the three main functionalities of our protocol, namely (i) Hint Computation, (ii) Hint dissemination and (iii) Packet forwarding.
2.3.1. Hint Computation To implement this func- tion each node i uses a vector of time information, V Hi, where V Hi[j] is the entry for the node j. The entry contains:
V Hi[j].tstart, the time when j was detected; V Hi[j].tbrk, the time when the link with j was broken; V Hi[j].tlast, the time of the last heartbeat (see later) received from j ; V Hi[j].τ , the duration of the last contact with j. Initially, V Hi[j].tbrk=∞.
By definition V Hi[j].tbrk= 0 means that j is a neighbor.
Each node sends a heartbeat packet every ∆TB s. If the node i receives a heartbeat from j at time t, it sets V Hi[j].tlast = t; moreover, if V Hi[j].tbrk = 0, then it sets V Hi[j].tbrk = 0 and V Hi[j].tstart = t. When i has not re- ceived the heartbeat from j for α ∆TBtime units (α > 1 is a real number) it sets V Hi[j].τ = V Hi[j].tlast− V Hi[j].tstart
and V Hi[j].tbrk= V Hi[j].tlast.
The hint at time t computed by the node j for the destina- tion d is:
hjd=
0 if V Hj[d].tbrk= 0
t−V Hj[d].tbrk
V Hj[d].τ if 0 < V Hj[d].tbrk< ∞
∞ otherwise
where the values in the formula are the ones stored at time t.
2.3.2. Hint dissemination Each node i manages a hint table, HTi, which contains an entry HTi[d] for each destina- tion node d. Such an entry stores a list of tuples, (n, hop, h, b), where n is a i’s neighbor, hop a number of hops, h the best hint computed by the nodes at distance hop hops from i and 0≤ b ≤ B is an integer representing the time to live of the en- try. The average size of the table is (N − 1) × L × ˜N .
For L = 1 the hint table is maintained by the following simple protocol. Every ∆TH= ∆TBs each node i deletes all the tuples with b = 0 from HTi, decreases the time-to-live field of the remaining ones and broadcasts a hint dissemina- tion control packet, which carries the hints of i w.r.t. the des- tinations. The packet also serves as a beacon for i. Upon re- ceiving a control packet from a neighbor j, say carrying the hint hjdfor d, the node i updates the tuple (j, 1, h, b) in the en- try HTi[d] with (j, 1, h = hjd, b = B), or creates it if neces- sary.
Procedure Forward(pkt, d) / * Behavior of node i * / 1. S = {j : V H[j].tbrk= 0} − {j : pkt.V [j] = 1};
2. Order S w.r.t. hints in HT [][d];
3. pkt.V [i] = 1;
4. for k = 1 ... |S| do
5. send ok =send(pkt, Sk);
6. if (send ok) return 1;
7. V H[Sk].tbrk= clock();
8. V H[Sk].τ = t − V H[Sk].tstart; 9. endfor;
10. Discard pkt; return 0;
End.
Figure 3. Pseudocode of the forward procedure.
When L = 2 the table is maintained by a similar proto- col. Its generalization to L > 2 can be easily derived, but it is omitted due to the lack of space. Again, each node exe- cutes an update every ∆THs, i.e., it deletes the expired en- tries from HTi, decreases the time-to-live field of the remain- ing ones and broadcasts a control packet.
For each destination d, the control packet sent by a node i now carries the value hid, plus the tuples in HTi[d] having hop = 1. The list thus contains 1 + ˜N elements on the aver- age.
When a node i receives a control packet from a neighbor, say j, for each tuple (n, 1, h, b) such that n = i and say corre- sponding to a destination d, it appends the tuple (j, 2, h, b) to HTi[d]. Moreover, the tuple (j, 1, h = hjd, B) is created or re- freshed if already present.
2.3.3. Packet Forwarding The pseudo-code of the for- warding algorithm is reported in Figure 3. The protocol as- sumes that each packet is equipped with a vector V of visited node, initialized to Ø. Upon receiving the packet destined to d, i determines an ordered list of possible next-hop nodes (line 1). The order is determined by the value of the hints, with ties broken by the number of hops and then at random (line 2).
Then, it tries to forward the packet to the node at the head of the list (line 5). If the transmission fails then the time infor- mation associated to the first node, S1, are updated (7-8) and i can promptly use S2, the second node of the list; if also this attempt fails, the third node could be used, and so on, un- til either the packet is successfully sent or the list is empty and consequently the packet is dropped. A simple modifica- tion can be introduced here: before giving up, the node i could solicit hint gathering from the neighbors, in the hope that a new neighbor is available.
The above forwarding protocol satisfies the following prop- erty.
Property (loop free) The Hybrid Probabilistic pro- tocol either delivers a packet to the destination within at most N − 1 forwarding steps, or it discards the packet within at most N − 2 forwarding steps.
This property follows from the definition of the algo- rithm. Suppose that after N − 2 forwarding steps the
G [
\
+
+
D
E
Figure 4. A configuration on a2H x 2H torus.
packet has neither delivered or discarded. Since at each for- warding step a new node is selected, therefore the packet visited N − 1 nodes; thus, the remaining node is the des- tination. The node that is currently holding the packet can perform another forwarding steps only if the desti- nation is its neighbor (in this case a total of N − 1 steps are required to deliver the packet), otherwise it must dis- card the packet. Note that the topology of the network can change during packet forwarding.
3. The hint-distance correlation
This section describes a discrete-time discrete-space ana- lytical model for studying the hint-distance relationship. The model is inspired to the so called Manhattan-like topology, which is used to represent a city with major streets running east-west and north-south. In this topology, the user can move along either the horizontal or the vertical direction.
In particular, we will derive the conditional probability that the distance between two nodes is k assuming that the time elapsed since they lost their contact is t. The relative speed is also capture by the model.
3.1. Model
Consider two mobiles, a and b, that can move on a 2-D torus with 2H x 2H points, see Figure 4. The elementary move- ments are discrete in time. At each time tick a mobile decides either, with probability α < 1, to remain in the same place or, with probability β = 1−α4 , to move to an adjacent point.
The relative position of the mobiles at time t is expressed by a vector of random variables, Dt = (x, y), where x and y ∈ [0, .., H] (recall that the topology is wrapped). The pair d = (x, y) is called a configuration (see Figure 4). The dis- tance norm is||(x, y)|| = x + y.
If d ∈ A=. {(0, 0), (0, 1), (1, 0)} then we say that a wire- less link between a and b exits or, equivalently, that the mobiles are neighbors. Thus, two users communicate di- rectly when they are at distance at most of one city block from each other.
The probability that the distance is k, namely P {M = k}, where k = 0, .., 2H, is given by
P r{M = k} = 1 H2
14 if k = 0 or k = H k 0 < k < H H −12 k = H 2H − k otherwise
(1)
Let us now calculate the conditional probability of the con- figuration between the two nodes being (x, y) assuming that at time t = −1 they were neighbors and that for all times k, 0 ≤ k ≤ t, they weren’t, namely P r{Dt = (x, y)|D−1 ∈ A ∧ Di ∈ A, i = 0..t}. Such a probability will be denoted as/ Pc(t, x, y).
Consider the discrete-time Markov chain whose states cor- respond to configurations. The states belonging to A are absorbing states. The Figure also sketches the state transi- tions allowed from two representative states, as detailed next in this section. The initial state of the chain, s, belongs to B = {(0, 2), (2, 0), (3, 0), (0, 3), (2, 1), (1, 2), (1, 1)}. The set B is composed of the configurations reached after the wire- less link between the mobiles breaks.
If P r{Xt = (x, y)|X0= s} is the probability that at time t the state of the chain is (x, y) assuming the initial state s, then the ratio
P r{Xt= (x, y)|X0= s}
(i,j) /∈AP r{Xt= (i, j)|X0= s}
gives the probability that at time t the state is (x, y), assuming that (x, y) is not an absorbing state and that the initial state of the chain was s. This is also the probability that the config- uration of the two nodes on the torus at time t is (x, y) assum- ing that after they broke the link the configuration was s (i.e., D−1 ∈ A, and D0 = s) and that they never met again af- ter such a breakage. Thus, we can write
Pc(t, x, y) =
ρss.t.s∈B
ρs P r{Xt= (x, y)|X0 = s}
(i,j) /∈AP r{Xt= (i, j)|X0= s}; (2) where ρsis the probability of the configuration s being ob- served after a link breakage.
Let us now return to the definition of the chain. The state transition probabilities can be conveniently writ- ten by exploiting the relationship between two consec- utive configurations, d and d. For this purpose, we use the update vector δ = (δx, δy), where δx, δy are inte- gers such that|δx+ δy| ≤ 2 and |δx|, |δy| ≤ 2, to determine a change in the configuration; the relationship can be writ- ten as d = d⊕Hδ = (x ⊕Hδx, y ⊕Hδy), where the opera- tor⊕His defined as
x ⊕Hδx=
x + δx if 0≤ x + δx≤ H;
2H − (x + δx) if x + δx> H
|x + δx| otherwise
We associate to the vector δ the probability pδ with which it can be generated by two elementary move- ments. The probability is readily obtained by thinking one node fixed while the other one is performing two move-
'LVWDQFH N
3U^GLVW N_W`
W
Figure 5. Conditional probability of the distance.
ments per unit of time and by assuming H = ∞ and x + y > 2. Hence,
p(0,0)= α2+ 4β2
p(1,0)= p(−1,0)= p(0,1)= p(0,−1)= 2αβ p(2,0)= p(−2,0)= p(0,2)= p(0,−2)= β2 p(1,1)= p(1,−1)= p(−1,1)= p(−1,−1)= 2β2
The probability of transition from state (x, y) to state (x, y), P(x,y),(x,y), is one if (x, y) = (x, y) ∈ A (these are the ab- sorbing states), and zero if|x − x| + |y − y| > 2. For the other cases (i.e.,|x − x| + |y − y| ≤ 2 and (x, y) /∈ A):
P(x,y),(x,y)=
∀δs.t.(x,y)⊕Hδ=(x,y)
pδ
As far as the probability ρsis concerned, we note that the probability of observing the configuration s ∈ B after a break- age, namely ρs .
= P r{D−1∈ A, D0= s}, is given by:
ρ(2,0)= ρ(0,2)= P r{M = 0} β2+P r{M=1)2 2αβ ρ(1,1)= P r{M = 0) 4αβP r{M = 0} + 2β2 ρ(3,0)= ρ(0,3)=P r{M =1}2 β2
ρ(1,2)= ρ(2,1)=P r{M =1}2 3β2
from which, normalizing, we obtain ρs=ρs
z∈Bρz. Pc(.) can now be obtained by solving the chain and using (2).
3.2. Numerical results
We now give some numerical result assuming H = 25. Fig- ure 5 shows the probability that, after t time units the link be- tween the mobile was broken, the distance between the mo- biles is k, namely
x+y=kPc(t, x, y). The curves are calcu- lated for α = 0 and for t = 10, 20, ..., 90, 1000. For t high such a distribution approaches the distribution of M , see Equa- tion 1. We can see that for t short there is a high probability that the mobiles are close to each other.
Figure 6 plots the average distance of the two mobiles as- suming t units from the link breakage are elapsed. α is given as a parameter and takes on the values 0, 0.2, 0.6, 0.8. Note that α determines the relative speed of the mobiles. The aver- age value increases with time and approaches the average dis- tance observed at a random time between the mobiles. The
7LPH W
(>0_W@ α
Figure 6. Conditional expected distance vs elapsed time.
time interval during which an appreciable difference between these two distances exists can be taken as a measure of the life- time of the hint-distance correlation. The shortest duration is clearly achieved when α = 0, since at each time tick a mo- bile changes its position.
4. Simulation
To asses the performance of the protocol we have devel- oped a discrete event simulation tool, with which we observed 120 nodes moving into a 1.5 km× 1.5 km region according to the random waypoint mobility model having zero pause time, see [14]. At the beginning of the simulation nodes were placed uniformly at random in the region. Each node then se- lects a new point and travels towards it at a constant speed, which is chosen in the range [1..vmax] m/s uniformly at ran- dom. When the node arrives at the destination, it repeats the same behavior.
Packets are generated at the constant rate of 5 packets/s and are 512 bytes in length. A source always sends packets to the same destination. The default number of sources is ten. Packet transmissions are governed by an ideal scheduler.
A FIFO buffer of 20 packets in size is used at each node. A packet is served (i.e., initiated) after the channel is idle for a Random Assessment Delay (RAD) randomly chosen in the range [0..500] ms. The transmission radius is R=250 m and the transmission speed 11 Mbps. We guess that such a sim- plified model captures the main behavior of a typical wireless link layer, while avoiding to bind results to a specific imple- mentation.
We simulated the Hint Based Protocol with lookahead L = k (HP-k), for k = 0, 1, 2 and an AODV protocol. The case L = 0 corresponds to a random walk and is used to vali- date the effectiveness of the hint mechanism. Hints are adver- tised every ∆TH = 500 ms, while α = 1.5 s and B = 2. In the AODV protocol we considered, a node s floods the network with a Route REQuest packet (RREQ) for a node d when it determines that it needs a route to d. Each node retrans- mits the packet if it was seen for the first time. In this case it also sets a backward path toward s. When the RREQ packet reaches the destination, a Route REPply packet (RREP) is sent back to the source along the backward path. Each node
0D[LPXPVSHHG PV
'HOLYHU\SUREDELOLW\
$2'9 +3
+3
+3
Figure 7. Delivery probability vs speed.
that participates in forwarding the RREP back to the origi- nator of the request, the node s, creates a forward route to d.
If not used, backward paths are deleted after a time-out. If a RREP packet is not received within 3 s, a new discovery is ini- tiated. The number of attempts is 3. When a node of an es- tablished path cannot forward a data packet, it sends a Route ERRor packet (RERR) back to the source, which then trig- gers a new route discovery.
Performance metrics The following metrics were esti- mated during a simulation:
• Delivery probability, ratio of the number of data packets delivered to the destinations to those generated by the traffic sources;
• Normalized overhead, ratio of the number of control packets to the number of data packets delivered to the destinations. For packets sent over multiple hops each single hop is counted as one transmission;
• Average path length, given in number of hops;.
• End to end packet delay, the time elapsed from when a packet is generated by the source until it is delivered to the destination.
A warm up period of 200 s. was used before collecting statis- tical data.
4.1. Simulation results
This section reports the performance results as a function of the speed. Please note that by increasing the maximum ve- locity, vmax, both the mean and the variance of the nodes’
speed increase.
Delivery probability The delivery probability is depicted in Figure 7. In AODV the probability to deliver a packet de- creases with vmax, since the reduction implies shorter paths’
lifetime. Two main opposite aspects determine the delivery probability of the HP protocols. On one hand, a high speed helps nodes to come in contact with each other; thus, the prob- ability that a neighbor has a valid hint for the destination in- creases with the speed. On the other hand, as the speed in- creases the validity of the correlation is shortened. This ex- plain why initially the delivery probability increases and then decreases. Note that the delivery probability is much lower if hints are ignored (see curve HP0); this validates hints as a use- ful means to track a node.
0D[LPXPVSHHG PV
1XPEHURIKRSV
$2'9 +3
+3
0D[LPXPVSHHG PV
'HOD\ PV
$2'9 +3
+3
Figure 8. Number of hops (top) and average de- lay (bottom) vs speed.
Number of hops Figure 8 shows how the number of hops varies with the speed. In AODV a path is used until it breaks.
Thus, even if due to a movement a shorter path is created, such a path will not be used until a new discovery is trig- gered. Under low mobility the probability that we are using a path longer than the shortest one is higher than under high mobility, since the increase in mobility triggers a path dis- covery more often. On the other hand, when the mobility is higher, paths shorter than the one currently in use are more likely to appear.
The path length of HP is influenced by the two opposite ef- fects previously mentioned for the delivery probability, which justify the behavior of the curve. Note that while the path length of HP1 is considerable longer than AODV’s one, un- der HP2 such a difference is much lower. The path’s length found by HP0, not reported in the figure, was≈ 15 hops.
Delay The end to end packet delay is portrayed in Figure 8 as a function of the speed. The figure clearly shows the suitabil- ity of our protocol to deal with high mobility. When the speed is increased, in fact, the delay of the AODV protocol increases since the number of route request increases. Moreover, by an- alyzing simulation traces, we observed that when the mobil- ity is high a route reply packet can be lost so that a new dis- covery can be initiated only after the time-out. On the con- trary, in our protocol the delay is almost independent from the speed.
0D[LPXPVSHHG PV
1RUPDOL]HGRYHUKHDG SNWV
$2'9 23
23
Figure 9. Normalized overhead vs speed.
Normalized overhead The overhead generated by AODV increases with mobility as a consequence of the shorter paths’s lifetime, see Figure 9 . The overhead of our protocol is al- most independent from the speed, since it is generated peri- odically; thus, the difference with AODV increases remark- ably with the speed. The lookahead value L = 2 provides a very small overhead that coupled with the previous results qualifies HP2 as a good solution for packets routing.
5. Conclusion
This paper proposed a probabilistic protocol for unicast packet delivery in mobile ad hoc networks. Instead of using pre-computed paths, packet forwarding is driven by the meta- information (hints) a node gathers from the neighbors located within a small number L of hops (the protocol’s lookahead) from itself. We have shown through simulations that a small lookahead can result in a very good compromises between the delivery performance and the number of control pack- ets. The paper also reported an analytical model for studying the hint-distance correlation. This approach can be extended to other communication paradigms, like multicasting, or dy- namic group communications.
References
[1] M. Abolhasan, T. Wysocki and E. Dutkiewicz, “A review of routing protocols for mobile ad hoc networks”, Ad Hoc Networks, Volume 2, Issue 1, Jan 2004, Elsevier.
[2] R. Beraldi, “On Message Delivery through Approximate Information in Highly Dynamic Mobile Ad Hoc Net- works”, The Seventh International Symposium on Wire- less Personal Multimedia Communications, Italy 12-15 September 2004
[3] B. Bellur, R.G. Ogier, F.L. Templin, “Topology broadcast based on reverse-path forwarding (TBRPF)”, IETF In- ternet Draft, draft-ietf-manet-tbrpf-01.txt, March 2001.
[4] J. Broch et al., “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols”, In Pro- ceedings of Mobicom 98
[5] Charles E. Perkins, P. Bhagwat, “Highly dynamic des- tinationsequenced distance-vector routing (DSDV) for mobile computers”, Computer Communications Review (October 1994) 234244.
[6] Charles E. Perkins and Elizabeth M. Royer. “Ad hoc On-Demand Distance Vector Routing”, Proc. of the 2nd IEEE Workshop on Mobile Computing Systems and Ap- plications, February 1999, New Orleans, LA.
[7] X. Chen, A.L. Murphy, “Enabling Disconnected Tran- sitive Communicaiton in Mobile Ad Hoc Networks”, in Workshop on Principles of Mobile Computing, colocated with PODC’01, August 2001 Newport, RI (USA).
[8] I. Chlamtac, M.Conti,J. J.-N. Liu “Mobile ad hoc net- working; imperatives and challanges” Ad Hoc Networks 1, (2003) 13-64.
[9] H. Dubois-Ferriere, M. Grossglauser, M. Vetterli “Age matters: efficient route discovery in mobile ad hoc net- works using encounter ages”, Proc of ACM MobiHoc2003, June 1-3 2003, Annapolis, MD.
[10] Z.J.Haas, J.Y.Halpen, “Gossip-based Ad Hoc Routing”, proceeding of IEEE INFOCOM 2002, New York, June 23- 27 2002
[11] Z.J. Haas, M.R. Pearlman, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks”, draft-ietf-manet-zone-zrp- 02.txt, (Work in progress) June 1999.
[12] James A. Davis et al., “Wearable Computers as Packet Transport Mechanisms in Highly-Partitioned Ad-Hoc Networks”, Proc. of ISWC 2001, Oct 7-9 2001, Zurich.
[13] P. Jacquet, P. Muhlethaler, A. Qayyum, “Optimized Link State Routing Protocol”, Internet Draft, draft-ietf- manetolsr- 00.txt, November 1998.
[14] D.B. Johnson, D.A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networking”, In Mobile Computing, chapter 5, Kluwer Academic, 1996.
[15] M. Roth, S.Wicker, “Termite: Emergent Ad-Hoc Net- working”, The Second Mediterranean Workshop on Ad- Hoc Networks, Medhia, Tunisia, 2003.
[16] S.Ni, Y. Tseng, Y. Chen, J. Sheu “The Broadcast Storm Problem in a Mobile Ad Hoc Network”, Proceedings of MobiCom’99, Seattle, WA, pp. 151–162, August 1999.
[17] Q. Xue, A. Ganz, “Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks”, Journal of Paral- lel and Distributed Computing, Volume 63, Issue 2, Feb 2003, Academic Press.
