International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1551

ISSN 2229-5518

Delay Optimization in Networks Using

PEAR Algorithm

Venkatesh.K, Vigneshwaran.R, Senthil.P.

AbstractAccording to our simulation, potential-based entropy adaptive routing (PEAR) has achieved high delivery rate on a wide range of mobility entropy, while link-state routing has worked well only at small entropy scenarios and controlled replication-based routing only at large entropy environments. Many message routing schemes have been proposed in the context of delay tolerant networks (DTN) and intermittently connected mobile networks (ICMN).

Index TermsDelay Optimization Networks, Mobility Entropy, Community- Structured Environment, Potential-Based Routing.

—————————— ——————————

1 INTRODUCTION

he communication paradigm of delay and disruption of tolerant networks (DTN) such as hop-by-hop application message delivery, is promising in many fields especially where stable Internet connectivity is not available (e.g., com-
munication in disaster-affected areas, developing regions,
wildlife tracking and wireless sensor networks). It has also
been discussed in the context of intermittently connected mo-
bile networks (ICMN), where an end-to-end connected path
rarely or never exists because of highly dynamic properties of
topology changes and node mobility.
DTLS has adopted link-state routing for communication among villages in developing regions. MaxProp and RAPID discussed message delivery among city buses. PROPHET and SOLAR focused on particular sociological mobile scenarios and evaluated their proposed routing schemes on them. Ran- dom waypoint mobility (RWP) has been widely used for eval- uation of message routing in ICMNs. These works commonly focus on their particular environments with regard to mobility complexity to discuss their proposed routing schemes.
Community-structured environment (CSE) is for evaluat- ing routing schemes over wide range of mobility complexity. In order to parameterize the complexity, we define mobility entropy in CSE. Mobility entropy works as an objective crite- rion of complexity. Thus, it acts important factor in networks.

————————————————

Vigneshwaran.R is currently pursuing masters degree program in I nformation

Technology in SRM University,Chennai, India

PH-9894905205,E-mail:honey.viks@gmail.com

Senthil.Pis currently pursuing masters degree program in Information Technol- ogy in SRM University, Chennai India

PH-994128413, E-mail:senthil_20@ymail.com

Venkatesh.K is currently working as an Assistant Proffessor in the Department of Information Technology in SRM University,

Chennai India, PH-9962008082 Email:venkatesh.k@ktr.srmuniv.ac.in
The Potential-based entropy adaptive routing (PEAR), which carries out message routing adaptively over the change of mobility. PEAR dynamically changes message replication on level depending on mobility entropy to always achieve high delivery rate. A node basically transfers messages toward the nodes of higher delivery probability with less message replication at smaller entropy, but it replicates more messages at larger entropy to maintain delivery rate. PEAR is not aware of entropy by itself. Node mobility initiates replication, and this makes PEAR entropy-adaptive.
PEAR inherits the concept of potential-based routing PBR), which is a family of message routing protocols that a node has a scalar value called potential for each destination, forwards messages toward the neighbor that has the lowest potential. The advantage of PBR is that a node can make for- warding decisions without a global knowledge of network topology. PBR only requires neighbor information for this purpose.
The forwarding decisions in PBR are made by potentials over nodes, which we call potential-field. We define a recur- rence formula for potential-field computa-tion in PEAR, which basically works in autonomously and totally distributed man- ner. The recurrence formu-lation enables dynamic computa- tion of potential-field without using a global knowledge of network status. It only uses neighbor network status, but con- structs global potential-fields appropriately.
We carry out simulations on various CSEs with changing
mobility entropy in order that we investigate the effect of mo-
bility entropy on message routing perfor-mance. We recognize
that the performance is affected by many environmental fea-
tures such as network band-width, media-access control
(MAC) protocol, message buffer capacity as well as mobility.
However, in this work, we assume an ideal environment to
demonstrate the relationship between mobility entropy and
routing performance.
Small entropy is associated with well-structured mobile envi- ronments. A random or chaotic mobility model gives large entropy.

IJSER © 2013

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1552

ISSN 2229-5518

2 RELATED WORKS

Traditionally, in order to evaluate the performance of routing in ICMNs, random-based mobility models have been adopted. Such mobility models include random waypoint (RWP), and random walk (RW) and random direction (RD). It has been as recently widely acknowledged that random-based mobility is unrealistic and that routing schemes are frequently discussed on sociologically-organized mobility models, which are stud- ied in the context of buses, taxi, and also in the sociological orbitand pedestrians.
Community-based mobility is also proposed but it is as basically random direction mobility which hierarchically as defined. The problem is that these mobility models possess a particular environmental feature with regard to as mobility entropy; e.g., random-based mobility gives extremely large entropy and sociologically-organized mobility gives smaller entropy.
SOLAR has proposed partially repetitive orbital mobility pattern that a node goes around in a small set of location points, which seems to be better suited to practical scenarios than random-based mobility. A CP corresponds to a commu- nity in CSE and node moves in a small set of communities in CSE. In this paper, we add the concept of mobility entropy in the context of CSE.
As for routing in DTNs and ICMNs, several routing schemes have been proposed. Link-state routing scheme was adopted to communication between villages in developing regions. Depending on the methods of computing the link cost, maximum delivery probability (MDP), minimum ex- pected delay (MED) and mini-mum expected dependent delay
(MEDD) are proposed. Basically, link-state routing is effective
only in the case of well-structured environment. Message path
becomes meaningless at a highly dynamic mobile network if used as an enhancement.
Epidemic routing ensures message delivery even in through partitioned networks of highly dynamic topology. But, basically, epidemic routing is flooding-based routing scheme, which copies message to all the nodes encountered, and the copy-received nodes start to copy the message in the same manner. It ideally achieves minimum delivery latency, but, it is said that epidemic routing consumes lots of network
resources and buffer space, which results in traffic congestion
and to poor performance in realistic scenarios.
Compared to epidemic routing, Spray and Wait improves the overhead of message replication by con-trolling the maxi- mum number of message copy. Mes-sage routing in Spray and Wait is composed of two phases. At first, in spray phase, the message source node makes message copies to neighbor nodes encoun-terd with limitation. Then, it waits until one of the nodes encounters the destination. Controlled replication-based routing like Spray and Wait is useful only in the case of ran- domly contactable scenarios where random mobility guaran- tees delivery probability.
In PBR, a node forward messages toward the neighbor that
has the lowest potential. Followed by this work, PWave has
applied PBR to wireless sensor networks for routing of sensor
readings to sink nodes. The concept of using the scenario of
Volcano routing scheme (VRS) is also an extention of PBR that

computes potential-field to diffuse messages from densely message buffered areas.
Fig. 1 Communities Organized by Node Traces at Mobility Entropy S = 0, 1, 2, 3
Utility-based routing was proposed by in mobile ad hoc networks (MANET) to support disconnected transitive communication. Utility is a scalar value that shows logical proximity to the destination. In that, utility-based routing is the same as potential-based routing in nature. The node of the highest utility will relay mes-sage to its destination with higher probability than any other nodes.

Fig. 2 Nodes Organized by Contacts at Mobility
Entropy S = 0, 1, 2, 3

IJSER © 2013

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1553

ISSN 2229-5518

3. COMMUNITY STRUCTURED ENVIRONMENT

Let N be a set of nodes in the network, and C a set of com-

munities. A node n N belongs to a sub set of C, which we

denote by Cn. In the stay mode, a node n stays at one of Cn,
which is given by location (n). In the transition mode, n moves

from community ci to community cj where ci, cj Cn and i = j.

A node is in contact with the nodes that stay in the same
community. That is,
”Node n and k are within direct transmission range”
”Node n and k are in contact with each other”
∃c ∈ C, location(n) = c ∧ location(k) = c (1)
Location (n) gives undefined when node n is in tran-sition
state.

We define CSE node mobility as follows (||Cn|| gives the number of elements in Set Cn),

1. Node n stays at community ci Cn.

2. Choose a random value r uniformly in [0, 1).

3. If p < r or ||Cn|| = 1, goto 1. Parameter p is probability of transition from stay mode to transit mode.

4. Choose a destination community cd from Cn −{ci} at the

random.

5. Let n move to cd with transitive time T (ci, cd).

6. After n reached the destination, ci := cd and goto 1. We formally define mobility entropy S of CSE as,

S = ||N|| n∑∈N log2

Here, if every node belongs to the same number of over the

communities (i.e., ||Ci|| = ||Cj||), S can be described as,

S = log2Ω (3)

Ω is the number of communities that every node belongs
to.
We show CSE instances in the case of S = 0, 1, 2, 3 in figure 1 and 2. In figure 1, a community is denoted by a vertex of the graph, and node traces are denoted by the edges. In the figure
2, a node is denote by a vertex of the graph, and a node-to- node contact ability is denoted by an edge. A pair of vertexes that connected by an edge indicates that those nodes are pos- sible to encounter with each other.
As these figures indicate, randomly contactable environment is characterized by larger entropy (e.g., S = 3). Stable or well- structured mobile environments provide small entropy (e.g., S
= 0, 1). In fact, random way-point mobility is given by setting
Ω = ||C||, which is the case at the largest S.

4 MESSAGE DELIVERY IN PEAR

Here, we focus on message delivery method under the as- sumption that potential-fields are already given. We discuss autonomous construction of potential-fields in PEAR in the next section.we denote the neighbor nodes (including itself) of node n by nbr (n). nbr (n) is a set of nodes within the same community of location(n) if it is defined(i.e., in stay mode). Otherwise, nbr (n) ={n}.
In potential-based routing, a node has a scalar value that shows a kind of distance to its destination. We call the value potential and describe it as V d (n). When we consider the change of potential over time, we describe it as V d (n, t), which means the potential for destination d at node n at time t. In this section, we assume that V d (n) is given and we focus on mes- sage delivery on it.
Basically, message delivery in PBR is carried out by forward- ing messages toward the node of the lowest potential among its neighbors. After a node forwarded a message to the next
node, it usually removes the message from the local buffer. In
stable networks (i.e., wired and connected networks), this
message delivery scheme is appropriate. However, in DTN
scenarios, message delivery should be carried out more re-
dundantly to improve delivery probability and latency.
In DTN environment, we consider that messages should not be just forwarded to the next node; it should be copied but
should not be deleted from the local buffer. The copy-source
node tries to make another copy of messages again when it
encounters to another node. Message replication in this way
will improve the delivery probability and latency. When we
introduce replication, the network must deal with replica management that involves message deletion after it has reached the destination.
Copy:
The process of making a clone of a message from this node
into the other node.
Forward:
The process of making a clone of a message from this node into the other node and deleting the original message.
Replicated messages:
Messages left in the network by the process of copy.
Delete:
The process of eliminating replicated messages from the
network.

IJSER © 2013

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1554

ISSN 2229-5518

Thus, in this context, we distinguish the terms of copy, for- ward, replicated messages and delete.

4.1 SELECTION OF HOP NODES

Let M be a set of messages in the network, and Md(M)
be the messages which destination is d. To deliver a message m
more than β (> 0). MCS chooses multiple next hop nodes at the same time.
Fig. 3 demonstrates how PEAR delivers on to a message of m
(M d) to destination d. In this figure, nodes are mapped ac-
cording to their potential V d(n) in the verti-cal axis, and the
edges show node-to-node contactability (i.e., intermittent con-
nectivity) between nodes. At first, m is possessed by n7, which has the highest potential in the figure. During n7 that is not connected to neither of n5 or n8, it does nothing. When it en- counters both of n5 and n8 at the same time, it copies the mes-
sage to n5 since F d (n7) > F d (n7) in BCS, whereas in MCS it

Md, node n must determine the next hop nodes of m, at first.

copies them to both of n
and n . In BCS (n
does not possess

5 8 8

We define two next hop selection schemes: i.e., best or single
candidate selection (BCS) and multiple candidate selec-
tion(MCS).
Best (or Single) Candidate Selection (BCS):

nexthopdBCS (n) = {k|k nbr (n) Fk (n) = max {Fj (n)} > α(4)}

m), after n5 has left from n7, n7 copies m to n8 since Fn 8 (n7) now provides the strongest force among its neighbors. n5, n8 and any other nodes behave in the same way and the message m will be copied to the lower potential nodes until they reach the destination.

d d

Where, jnbr (n) (4)

Here, F d(n) is the force that affects on the message md from
node n toward neighbor k, which we define as

F d(n) = V d(n) − V d(k) (5)

Lower potential of neighbor k enlarge the force from node n to

k. In BCS, node n chooses the neighbor k that gives the maxi-

At small entropy (e.g., S = 1), PEAR only uses a small set of nodes for message delivery, saving resources as much as pos- sible. As entropy S becomes larger, probability of meeting of nodes (e.g., between n5 and n7) decreases and message deliv- ery on that paths may fail. However, PEAR maintains delivery probability even in larger S by replicating more messages in the network. At large entropy, n7 also has links with n1, n4 and n9. Thus, m will be copied to those nodes, which increase the
mum Fk (n) as the next hop of Md
at every time unit. Here, the
replication level, and achieves high delivery rate.
force must be more than a constant value α, the threshold of
the least force level. Other-wise, no selection are made for des-
tination d. Nodes encounter and leave as time elapses, and the

best can-didate changes according to nbr(n).
Fig. 3 Message Delivery in PEAR Multiple Candidate Selection (MCS):

nexthopdMCS(n) = {k|k nbr(n) Fk (n) > β} (6)

In MCS, next hop nodes are such neighbors that the force is

4.2REPLICA MANAGEMENT

After nexthopd(n) is determined by BCS or MCS at node n. n

tries to copy message m Md to them. Here, some of them

may already have a replica of the mes-sage or others may
know that the message has already reached the destination.
Replica management should be carried out in PEAR in order
to reduce the overhead of message duplication and to efficient- ly use buffer space by removing replicas of delivered message
from the net-work.
In PEAR, message m must contain the following in-formation as well as the message body in its header at least.
 MessageID
 Destination
 Time to Live (TTL)
The following information should be managed at ev-ery node locally for each m.
 DisseminationTTL
 IsDelivered
MessageID must be uniquely defined in the network. TTL is a message life time which decreases, for example, every second.

IJSER © 2013

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1555

ISSN 2229-5518

When TTL reaches zero, the message expires (with freeing memory allocated for m including headers). TTL corresponds to the left time for delivery deadline.
DisseminationTTL describes whether node n can send the message to other nodes or not. Initially, node n sets it to TTL of the message when received the message. It decreases in the same manner as TTL does. As we describe later, thus it is the Dissemination TTL changes depending on the process of mes- sage replication. If it has expired, node n does not transfer the message to its next hop nodes any longer and deletes the body of it (with free-ing allocated memory space for message body), but continues to check the existence of a delivery certification at the next hop nodes. IsDelivered shows whether de-livery has been certified or not. Originally, when this node receives a message, IsDelivered is set to false. After finding the delivery certification, it is set to true. The first certificate will be pub- lished by the destination node after it has received the mes- sage.
crease. In this way, nodes farther from the destination gets higher potential, and nodes closer to the destination gets lower potential. Message delivery is carried out from the higher po- tential node to the lower potential node.

5.2 DYNAMICS

We illustrate how PEAR autonomously constructs a poten- tial-field by Eqn. 7 and achieves message delivery. We assume a quite simple case to make the discussion easy: i.e., four nodes and three communities. Here, n1 belongs to a communi- ty c1. n2 belongs to c1 and c2. n3 belongs to c2 and c3, and n4 to c3. Nodes are in contact with each other only when they are locat- ed at the same community; i.e., n1 and n2 are in contact when n2 locates at c1, n2 and n3 are in contact when they stay at c2, and so on. A contact is denoted by a line, and disconnection is
Initially, nodes have the same potential value at zero. They except V n1 (n1) start to increase by ρ.
(b ) As time elapses, V n1 (n2) stays at ρ
n1 (n4) continues to increase at speed ρ.
, while V n1 (n3) and V

4.3 LOOP FREENESS

Loop-freeness in potential-based routing is proved by in the case of static potential-field. Basically, a message which has been forwarded to the lower potential node cannot come again from the upper potential node.
In our modified version of PBR, message delivery is carried out by copying, not by forwarding. Message remains at the nodes where it has infected. Therefore, even in dynamically potential-changing scenarios, messages never loop in PEAR.
(c) The physical topology has changed, and only n2 and n3 are in contact. V n1 (n2) starts to increase at speed ρ, while V n1 (n3) decreases toward V n1 (n2). Here, n3 copies its Mn1 to n2.
(d) When the link between n2 and n3 is disrupted and instead the link between n3 and n4 has set up,

V n1 (n2) and V n1 (n3) increases at speed ρ, while V n1 (n4) de- creases toward V n1 (n3). In this situa-tion, n4 copies its Mn1 to n3.

ρ

5 POTENTIAL FIELD CONSTRUCTION

We described a message delivery scheme in PEAR on a given potential-field. In this section, we describe potential-

n2 is now in contact with n1. V n1 (n2) decreases to D

transfer its Mn1 to n1.

6 SIMULATION

, and n2
field construction method in PEAR, which autonomously and dynamically computes the field. Potential computation in PEAR does not require global topology information. It only uses neighbor information but makes an appropriate potential field globally. This is the same property that next hop decision schemes possess.

5.1 RECURRENCE CONSTRUCTION

The potential of node n at the next time step (t + 1) is calculat- ed on the potential of neighbors at current time t. Basically, it inflates by ρ, but the inflation is depressed by the smallest po- tential among neighbors. This depression is weighted by D,
which we call minimum-potential diffusion constant.
All the po-tential value starts at zero. gives a boundary condi-
tion that a node must always have zero potential for itself,
which means that the potential at the desti-nation must be
always set to zero.
The potential at the destination node V d(d) = 0 dif-fuses from the message destination around the network with some in-

We evaluated PEAR, regarding to delivery rate and total mes- sage transmissions, on various CSEs by simulation. The pur- pose of this experiment is to analyze the features of routing schemes in terms of mobility entropy. Thus, we carried out the simulation without being aware of transmission properties (e.g., node-to-node link bandwidth and average message size).
In this way, we focused on an ideal case where the effect of
them can be ignored.
We set 100 nodes over 50 communities throughout the simula- tion with changing Ω from 2 to 48: i.e., entropy S from 1 to 5.6. We assumed the case that every node belongs to the same number (= Ω) of communities in each CSE. Throughout the experiment, we set D = 0.001 and ρ = 0.00001 for potential- field construction (Eqn. 10), and α = 0.8 and β = 0.8 for next hop selection (Eqn. 4 and Eqn. 6). The message lifetime was set to 20000.
We carried out the simulation of node mobility, po-tential field construction and message delivery during the time inter-
val [50000, 20000]. While t [50000, 0), no messages were
submitted into the network; only the movement of nodes and

IJSER © 2013

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1556

ISSN 2229-5518

potential-field construction were simulated. At t = 0, every
node sent messages to all the nodes in the network. While t
(0, 20000], message de-livery was also simulated as well as the
node movement and potential-field construction.
We evaluated PEAR with other routing schemes such as epi- demic routing], Spray and Wait (2-hop scheme) , Minimum Expected Delay(MED) and Maximum Delivery Probabil- ity(MDP). In the comparison with these schemes we have pre- pared completely the same set of CSEs.

6.1 DELIVERY RATE

Link-state routing (i.e., MED and MDP) achieved about 95% message delivery at S = 1, but it failed 50% at larger entropy. Spray and Wait delivered only 28% of messages at S = 1, whereas it delivered about 95% at larger entropy. PEAR achieved more than 95% delivery rate over any entropy envi- ronments, which is almost the same level that Epidemic rout- ing did. These results indicate that PEAR has dynamically adapted to any given environments whether they are highly- dynamic or relatively well-organized. However, link-state routing and Spray and Wait have achieved good performance at the specific situations.
The latency of message delivery in MED and MDP gets large sharply as S increases, resulting in unsuccessful message de- livery at time 20000. As for other routing schemes, Epidemic routing totally performed a good performance with regard to delivery rate, and Spray and Wait stopped the increase of message delivery rate at 28% around time 5000 at S = 1, but the rate sharply increased at S = 3, 5.
From these results, we summarize that PEAR is useful for wider mobility entropy scenarios than the other routing schemes except Epidemic routing. Link-state routing (i.e., MED and MDP) is just useful at quite small entropy. Spray and Wait routing is useful for larger entropy scenarios, where nodes are possible to directly contact with most of the nodes in the network.

6.2 TOTAL MESSAGE TRANSMISSIONS

A total message transmission is the total count of ap-plication message exchange among nodes. Figure 8 shows the relation- ship between total message transmissions and entropy. PEAR (BCS) reduced the transmissions to about 11% (at S = 1) and
23% (at S = 5) of Epidemic routing. Link-state routing (i.e., MED and MDP) transmitted about 3.5% of Epidemic routing at S = 1, where they achieved high delivery rate. Spray and Wait transmitted about 12% at S = 5. PEAR generated two or three times more transmissions than link-state routing and Spray and Wait.
Figure 4 shows total message transmissions over the time in- terval from t = 0 to t = 20000. These graphs show the summary of transmission: e.g., 1000 transmissions at time 3000 means
that 1000 messages have been exchanged in the network dur- ing [0, 3000]. From the re-sults we read that message delivery in Spray and Wait was carried out mostly during [0, 5000] at any CSEs. This is the same feature of Epidemic routing. An- other thing we read from the results is that link-state routing and PEAR carried out the delivery process gradually at S = 3,
5 though it has finished around t = 5000 at S = 1.
Finally, on careful manipulation, we get the correct rule that matches the packet with lowest number of active rules in hand, with a space complexity of O (n) and time complexity of O(log n) thereby, reducing the number of cor- rupted packets occurring in the network

7 CONCLUSION

We proposed community-structured environment (CSE) and potential-based entropy adaptive routing (PEAR) in this pa- per. CSE has enabled the classification of mobile environments in terms of mobility entropy. In CSE, stable or well-structured mobile environments are characterized by small entropy. Randomly contactable environments are characterized by large entropy.
Using CSE, we have analyzed the features of routing schemes by simulation. In our experiment, link-state routing (e.g., MED and MDP) has worked well at small entropy environments such as S = 1 but failed to 50% delivery at larger entropy. Spray and Wait has achieved good performance at larger en- tropy, but only 28% messages have been delivered at S = 1.
PEAR has achieved more than 95% message deliv-ery over any mobility entropy environments by adap-tively changing the message delivery form. At small entropy, PEAR has ag- gressively transferred a message in hop-by-hop manner using the appropriately developed potential-fields. At large entropy, PEAR has au-tomatically shifted to let mobility deliver the message with making more replicas in the network. In this way, PEAR has maintained the delivery rate.

IJSER © 2013

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 1557

ISSN 2229-5518

[5] Z. Haas, J. Y. Halpern, and L. Li. Gossip-based ad hoc routing.

In IEEE INFOCOM, 2002.

[6] J. Hahner, C. Becker, and K. Rothermel. A protocol for data

dissemination in frequently partitioned mobile ad hoc networks.

In IEEE ISCC, 2003.

[7] X. Chen and A. L. Murphy. Enabling disconnected transitive communication in mobile ad hoc networks. In ACM POMC, 2001.

Fig. 4 Light,Temperature and Humidity Sensors.

Fig. 5 Light,Temperature and Humidity Values.

Acknowledgment

We specially thank our HOD and the staff members of SRM University for rendering us valuable information and encouraging us throughout our research.

REFERENCES

[1] A. Balasubramanian, B. N. Levine, and A.Venkataramani.

DTN routing as a resource allocation problem. In ACM SIGCOMM,

2007.

[2] A. Basu, A. Lin, and S. Ramanathan. Routing using potentials: A

dynamic traffic-aware routing algorithm. In ACM SIGCOMM 2003,

2003.

[3] J. Ghosh, H. Q. Ngo, and C. Qiao. Mobility profile

based routing within intermittently connected mobile ad hoc networks (ICMAN). In

ACM IWCMC, 2006.

[4] J. Ghosh, S. J. Philip, and C. Qiao. Sociological orbit aware location

approximation and routing (SOLAR) in MANET. ACM Ad Hoc

Networks, 5(2):189–209, Mar 2007.

IJSER © 2013

http://www.ijser.org