# An Enhanced Hybrid Social Based Routing Algorithm for MANET-DTN

Authors: Martin Matis; L’ubomír Doboš; Ján Papaj
Journal: Mobile Information Systems
 (2016)

---

## Abstract

A new routing algorithm for mobile ad hoc networks is proposed in this paper: an Enhanced Hybrid Social Based Routing (HSBR) algorithm for MANET-DTN as optimal solution for well-connected multihop mobile networks (MANET) and/or worse connected MANET with small density of the nodes and/or due to mobility fragmented MANET into two or more subnetworks or islands. This proposed HSBR algorithm is fully decentralized combining main features of both Dynamic Source Routing (DSR) and Social Based Opportunistic Routing (SBOR) algorithms. The proposed scheme is simulated and evaluated by replaying real life traces which exhibit this highly dynamic topology. Evaluation of new proposed HSBR algorithm was made by comparison with DSR and SBOR. All methods were simulated with different levels of velocity. The results show that HSBR has the highest success of packet delivery, but with higher delay in comparison with DSR, and much lower in comparison with SBOR. Simulation results indicate that HSBR approach can be applicable in networks, where MANET or DTN solutions are separately useless or ineffective. This method provides delivery of the message in every possible situation in areas without infrastructure and can be used as backup method for disaster situation when infrastructure is destroyed.


---

## Body

## 1. Introduction

Transport of data through mobile ad hoc network (MANET) [1] is possible thanks to routing protocols, such as proactive, reactive, or their combination [2]. When the mobile nodes have high mobility and/or the network is very sparse, MANET can be fragmented on many subnetworks (islands). It is impossible to find END-TO-END connection (path between source, S, and destination, D) or maintenance of this path during overall relation. Using of standard MANET routing protocol became ineffective or impossible in those situations [3]. However, mobility of nodes represents a big advantage in cases when the data are transported through a MANET controlled by Opportunistic Routing protocols. On the other site, data delivery delay is increasing. This type of the network is called Delay-Tolerant Network (DTN) [4, 5].Due to mobility of nodes and/or its sparse deployment, the network may split to two or more islands with relatively stable connectivity inside them. It would be appropriate to use standard MANET routing inside the islands and opportunistic routing between islands. This solution promises significant improvements in cases where END-TO-END connection between S and D is aborted during message sending and it is not possible to find alternative path in maintenance process. In the standard MANET, the overall message sending must be repeated after next successful finding of new path between S and D. However, MANET routing protocol can be still locally successful in partial path inside island even if it fails globally (END-TO-END between S and D). The last node on partial path in island may act as virtual sourceV
S for the rest of unsent messages or virtual destination for undelivered messages or part of message [3, 6].In this paper our hybrid algorithm is proposed combining routing techniques, both traditional MANET and DTN approaches, exploiting their advantages. This proposal uses DSR paths [7] at first or opportunistic sending based on social relation between nodes [8–11] for data transmission. In the case when DSR path is destroyed, V
S is used on partial path so as to bring it closer to destination.The paper is organised as follows. In Section2 are described situations, when MANET is splitting to subnetworks or islands due to mobility and velocity influence. Next, MANET and DTN are compared and two cases of communication (END-TO-END and device-to device) are analysed. Section 3 described needed modifications of standard DSR algorithm. Section 4 briefly explains the social based DTN. Section 5 described our proposal of Hybrid Social Based Routing (HSBR) algorithm. Section 6 describes simulation of proposed HSBR algorithm and main results are analysed and compared with Social Based Opportunistic Routing (SBOR) and Dynamic Source Routing (DSR) algorithms.


## 2. Problem Definition

### 2.1. Overview

The main topic of this paper is a creation of routing protocol which combines advantages of MANET [1, 12] and DTN [4, 5] solutions. DEVICE-TO-DEVICE approach, carrying of message, and selection of next hop node [3, 6, 13–16] can be the answer for the delivery of messages between source and destination in network without infrastructure, with or without END-TO-END connectivity with minimum of overhead.In MANET the following situations may occur.Network with END-TO-END Connection (Figure1). There is a possibility to find and to maintain the path and to send the data from S to D. The basic MANET routing protocols [12] can be used for this situation.Figure 1
Network with END-TO-END connection.Network without END-TO-END Connection (Figure2). The deployment of the mobile nodes in MANET is very sparse or consists of two or more subnetworks (islands) without connection between them where S and D nodes are from different islands. It is impossible to find path between S and D with obvious MANET routing. In these situations, it is possible to use opportunistic sending of the message. The DTN routing approaches can be used [17].Figure 2
Network without END-TO-END connection.Network with Lost Connection (Figure3). The network topology is often changing because of the high mobility of mobile nodes. It is possible to find the path between S and D nodes, but it is not possible to maintain it during overall communication and connection can be lost between S and D. The MANET is fragmented into two or more subnetworks or islands. Number of these islands and number of nodes which create these islands are changing in time. In such a situation it should be useful to send complete message (all packets) from source node to the last node which lost connection with the next hop on the path to the destination. This path from source to last node is called partial path. For example, the last node 4 in Figure 3 belongs to actual island. This node can act now as virtual source, V
S, and as first step it attempts to find path to destination with basic MANET routing. If first attempt is not successful then it follows second attempt to send message in opportunistic manner by DTN routing approaches [14, 15].Figure 3
Network with lost connection.


### 2.2. Comparison of MANET and DTN

MANET and DTN routing methods can be used for transfer between nodes in network without infrastructure, which are not in direct radio range. MANET and DTN are different from each other [18].Transmission Methods for MANET and DTN. As shown in Figure 4, MANET establishes END-TO-END path between nodes and transmits messages to the destination directly along this path. If the message does not reach the destination, the source attempts to perform retransmission. Thus, when the path is stable, the number of retransmissions is small. However, with the increasing of hop count between S and D, the path tends to become unstable due to the frequent disconnection of path caused by the movements of intermediate nodes. In this situation, the S node has to retransmit the message many times.Figure 4
MANET transfer of message.On the other hand, in DTN, the nodes forward a message in a DEVICE-TO-DEVICE manner from theS to the D as shown in Figure 5. Each node stores the messages in its storage during each transmission. As a result, the effect of the hop count in DTN is less than that in MANET because transmissions are independent of each other [18].Figure 5
DTN transfer of message.Depending on the hop count and the stability of the paths, the two transmission methods show different performances. In order to make a comparison, we consider a simple network model as shown in Figure6. In this model, the nodes line up and each node is in the radio range of its left and right neighbours. Additionally, we define the transmission success probability between the node i and node (i
+
1) as p
i, where p
i can be any value in the range from 0 to 1. In practice, this parameter is a function of node density, mobility, and so on.Figure 6
Network model.At first, we consider aone-hop transmission. In the situation that the node n
i tries to send a message to the node n
i
+
1, node n
i continues to retransmit until the transmission becomes successful. As the decreasing of the value of p
i, the number of retransmissions becomes bigger. The expected number of transmissions required to have the success of transmission represents value E in (1). In a one-hop transmission, there is no difference between MANET and DTN in terms of the value of E:(1)
E
=
∑
k
=
1
∞
k
1
-
p
i
k
-
1
=
1
p
i
.Secondly, we consider amultihop transmission in Figure 6. In this situation, node n
1 tries to send a message to node n
N. In MANET, the source node sends a message by using END-TO-END paths, and thus, the transmission success probability P on this path is calculated in (2), where N is the number of nodes:(2)
P
=
∏
i
=
1
N
-
1
p
i
.Therefore, in MANET, the number of transmissions E
M
A
N
E
T is expressed in (3)
E
M
A
N
E
T
=
1
P
.In DTN, the source node sends a message by using DEVICE-TO-DEVICE transmissions as shown in Figure 5. The expected number of transmissions in DTN, E
D
T
N, is expressed in [18](4)
E
D
T
N
=
∑
i
=
1
N
-
1
1
p
i
.The differenceD
(
h
) between E
M
A
N
E
T and E
D
T
N in the h hops transmission is expressed in (5), where h is the hop count between the source and the destination:(5)
D
h
=
E
D
T
N
-
E
M
A
N
E
T
=
h
p
-
1
p
h
.If the value ofD
(
h
) is positive, MANET can provide connection more effectively than DTN in terms of the lower number of transmissions. Additionally, D
(
h
) has a maximum value with a certain hop count because D
(
h
) is the convex function.Therefore, it is possible to determine a more effective transmission method, END-TO-END (MANET) or DEVICE-TO-DEVICE (DTN), based on the calculation of maximum hop count. This maximum hop counth
m
a
x is calculated by expression (6), where the value of ln
⁡
p
ln
⁡
1
/
p
/
ln
⁡
p is equal to the maximum value of h, and in the right side of this equation, the maximum value of h is rounded off because the hop count has to be the integer value:(6)
h
m
a
x
=
ln
⁡
p
ln
⁡
1
/
p
ln
⁡
p
.Based on the result ofh
m
a
x it is possible to select transmission method from both possibilities (END-TO-END or DEVICE-TO-DEVICE) [18].


## 2.1. Overview

The main topic of this paper is a creation of routing protocol which combines advantages of MANET [1, 12] and DTN [4, 5] solutions. DEVICE-TO-DEVICE approach, carrying of message, and selection of next hop node [3, 6, 13–16] can be the answer for the delivery of messages between source and destination in network without infrastructure, with or without END-TO-END connectivity with minimum of overhead.In MANET the following situations may occur.Network with END-TO-END Connection (Figure1). There is a possibility to find and to maintain the path and to send the data from S to D. The basic MANET routing protocols [12] can be used for this situation.Figure 1
Network with END-TO-END connection.Network without END-TO-END Connection (Figure2). The deployment of the mobile nodes in MANET is very sparse or consists of two or more subnetworks (islands) without connection between them where S and D nodes are from different islands. It is impossible to find path between S and D with obvious MANET routing. In these situations, it is possible to use opportunistic sending of the message. The DTN routing approaches can be used [17].Figure 2
Network without END-TO-END connection.Network with Lost Connection (Figure3). The network topology is often changing because of the high mobility of mobile nodes. It is possible to find the path between S and D nodes, but it is not possible to maintain it during overall communication and connection can be lost between S and D. The MANET is fragmented into two or more subnetworks or islands. Number of these islands and number of nodes which create these islands are changing in time. In such a situation it should be useful to send complete message (all packets) from source node to the last node which lost connection with the next hop on the path to the destination. This path from source to last node is called partial path. For example, the last node 4 in Figure 3 belongs to actual island. This node can act now as virtual source, V
S, and as first step it attempts to find path to destination with basic MANET routing. If first attempt is not successful then it follows second attempt to send message in opportunistic manner by DTN routing approaches [14, 15].Figure 3
Network with lost connection.


## 2.2. Comparison of MANET and DTN

MANET and DTN routing methods can be used for transfer between nodes in network without infrastructure, which are not in direct radio range. MANET and DTN are different from each other [18].Transmission Methods for MANET and DTN. As shown in Figure 4, MANET establishes END-TO-END path between nodes and transmits messages to the destination directly along this path. If the message does not reach the destination, the source attempts to perform retransmission. Thus, when the path is stable, the number of retransmissions is small. However, with the increasing of hop count between S and D, the path tends to become unstable due to the frequent disconnection of path caused by the movements of intermediate nodes. In this situation, the S node has to retransmit the message many times.Figure 4
MANET transfer of message.On the other hand, in DTN, the nodes forward a message in a DEVICE-TO-DEVICE manner from theS to the D as shown in Figure 5. Each node stores the messages in its storage during each transmission. As a result, the effect of the hop count in DTN is less than that in MANET because transmissions are independent of each other [18].Figure 5
DTN transfer of message.Depending on the hop count and the stability of the paths, the two transmission methods show different performances. In order to make a comparison, we consider a simple network model as shown in Figure6. In this model, the nodes line up and each node is in the radio range of its left and right neighbours. Additionally, we define the transmission success probability between the node i and node (i
+
1) as p
i, where p
i can be any value in the range from 0 to 1. In practice, this parameter is a function of node density, mobility, and so on.Figure 6
Network model.At first, we consider aone-hop transmission. In the situation that the node n
i tries to send a message to the node n
i
+
1, node n
i continues to retransmit until the transmission becomes successful. As the decreasing of the value of p
i, the number of retransmissions becomes bigger. The expected number of transmissions required to have the success of transmission represents value E in (1). In a one-hop transmission, there is no difference between MANET and DTN in terms of the value of E:(1)
E
=
∑
k
=
1
∞
k
1
-
p
i
k
-
1
=
1
p
i
.Secondly, we consider amultihop transmission in Figure 6. In this situation, node n
1 tries to send a message to node n
N. In MANET, the source node sends a message by using END-TO-END paths, and thus, the transmission success probability P on this path is calculated in (2), where N is the number of nodes:(2)
P
=
∏
i
=
1
N
-
1
p
i
.Therefore, in MANET, the number of transmissions E
M
A
N
E
T is expressed in (3)
E
M
A
N
E
T
=
1
P
.In DTN, the source node sends a message by using DEVICE-TO-DEVICE transmissions as shown in Figure 5. The expected number of transmissions in DTN, E
D
T
N, is expressed in [18](4)
E
D
T
N
=
∑
i
=
1
N
-
1
1
p
i
.The differenceD
(
h
) between E
M
A
N
E
T and E
D
T
N in the h hops transmission is expressed in (5), where h is the hop count between the source and the destination:(5)
D
h
=
E
D
T
N
-
E
M
A
N
E
T
=
h
p
-
1
p
h
.If the value ofD
(
h
) is positive, MANET can provide connection more effectively than DTN in terms of the lower number of transmissions. Additionally, D
(
h
) has a maximum value with a certain hop count because D
(
h
) is the convex function.Therefore, it is possible to determine a more effective transmission method, END-TO-END (MANET) or DEVICE-TO-DEVICE (DTN), based on the calculation of maximum hop count. This maximum hop counth
m
a
x is calculated by expression (6), where the value of ln
⁡
p
ln
⁡
1
/
p
/
ln
⁡
p is equal to the maximum value of h, and in the right side of this equation, the maximum value of h is rounded off because the hop count has to be the integer value:(6)
h
m
a
x
=
ln
⁡
p
ln
⁡
1
/
p
ln
⁡
p
.Based on the result ofh
m
a
x it is possible to select transmission method from both possibilities (END-TO-END or DEVICE-TO-DEVICE) [18].


## 3. Modification of DSR Algorithm

In this section, a new modification of DSR algorithm (M-DSR) is introduced, which should solve a situation when connection betweenS and D is lost and it is impossible to maintain the connection in the basic manner.


### 3.1. Dynamic Source Routing (DSR)

M-DSR arises from standard DSR protocol based on RFC 4728 [7], which is simple and efficient, on-demand routing protocol designed for usage in multihop wireless ad hoc networks. DSR allows the network to be completely self-organisable and self-configurable. The protocol is composed of two main mechanisms of “Route Discovery” and “Route Maintenance,” which allow discovering path from S to D and retaining connection between them during overall communication [7, 19].


### 3.2. Modified Dynamic Source Routing (M-DSR)

Modification of DSR implies the following:(i)
Route request (RREQ) is extended about the destination’s additional message (social based internode relation information).
(ii)
Probabilities of message delivery are calculated based on user profile table (explained later).
(iii)
Detection and usage of the last node (in connection with S) on disconnected path as virtual source (V
S).
(iv)
Route maintenance process is changed due to sending data to the last node on the partial path, toV
S.Two main mechanisms, which are used in standard DSR, must be adapted for the feature usage in HSBR. Proposed modification is as follows [7]:(i)
Route Discovery. S sends route request packet (RREQ) to all neighbour nodes. These nodes send RREQ to their neighbours, and so forth, until D is found. RREQ packet stores and carries the nodes’ ID through which the RREQ is sent. If the finding is successful, the destination node sends route replay (RREP) packet back to S by stored nodes’ ID. When the RREP arrives to S, then the path is established and S can use this path for sending the data packets. Modification of DSR especially RREQ packet includes specific additional message about destination to RREQ packet. This additional message can be represented as social relation [10, 11] between S and D and it can be used for maintenance of next communication (will be explained later). Kind as well as type of specific message is varied and depends on method for selection of next hop node with the highest probability connection with destination (number of all neighbour nodes in range).
(ii)
Route Maintenance. It is responsible for finding alternative path in such a situation when an actual used path is interrupted during sending of packets. This process utilizes backup path or paths, which is found during Route Discovery. If some of the nodes detect failed link, then it will send Route Error (RERR) message to S, which tries to use alternative path selected from route cash if it exists. If alternative path does not exist, standard maintenance process will be stopped and sending of packets is cancelled, so the transfer is unsuccessful. This modification of this process utilizes knowledge about losing of connection between a couple of neighbors on the path from S to D (basically RERR). The process of the packet sending does not stop. The rest of the packets are sent like preferred message from S to last node in the disconnected and partial path, which is detected in maintenance process. This node becomes the virtual source V
S.


## 3.1. Dynamic Source Routing (DSR)

M-DSR arises from standard DSR protocol based on RFC 4728 [7], which is simple and efficient, on-demand routing protocol designed for usage in multihop wireless ad hoc networks. DSR allows the network to be completely self-organisable and self-configurable. The protocol is composed of two main mechanisms of “Route Discovery” and “Route Maintenance,” which allow discovering path from S to D and retaining connection between them during overall communication [7, 19].


## 3.2. Modified Dynamic Source Routing (M-DSR)

Modification of DSR implies the following:(i)
Route request (RREQ) is extended about the destination’s additional message (social based internode relation information).
(ii)
Probabilities of message delivery are calculated based on user profile table (explained later).
(iii)
Detection and usage of the last node (in connection with S) on disconnected path as virtual source (V
S).
(iv)
Route maintenance process is changed due to sending data to the last node on the partial path, toV
S.Two main mechanisms, which are used in standard DSR, must be adapted for the feature usage in HSBR. Proposed modification is as follows [7]:(i)
Route Discovery. S sends route request packet (RREQ) to all neighbour nodes. These nodes send RREQ to their neighbours, and so forth, until D is found. RREQ packet stores and carries the nodes’ ID through which the RREQ is sent. If the finding is successful, the destination node sends route replay (RREP) packet back to S by stored nodes’ ID. When the RREP arrives to S, then the path is established and S can use this path for sending the data packets. Modification of DSR especially RREQ packet includes specific additional message about destination to RREQ packet. This additional message can be represented as social relation [10, 11] between S and D and it can be used for maintenance of next communication (will be explained later). Kind as well as type of specific message is varied and depends on method for selection of next hop node with the highest probability connection with destination (number of all neighbour nodes in range).
(ii)
Route Maintenance. It is responsible for finding alternative path in such a situation when an actual used path is interrupted during sending of packets. This process utilizes backup path or paths, which is found during Route Discovery. If some of the nodes detect failed link, then it will send Route Error (RERR) message to S, which tries to use alternative path selected from route cash if it exists. If alternative path does not exist, standard maintenance process will be stopped and sending of packets is cancelled, so the transfer is unsuccessful. This modification of this process utilizes knowledge about losing of connection between a couple of neighbors on the path from S to D (basically RERR). The process of the packet sending does not stop. The rest of the packets are sent like preferred message from S to last node in the disconnected and partial path, which is detected in maintenance process. This node becomes the virtual source V
S.


## 4. SBOR Algorithm

The main and typical considerations of DTN are sparse and intermitted connected network consisting of mobile devices. Routing algorithms there can be used for disconnected networks and communication between islands and networks with high mobility too [5].It is impossible to create an END-TO-END path betweenS and D in those cases. Therefore, sending of data from S to next node towards D is provided by DEVICE-TO-DEVICE transfer. Sending can be provided based on many criterions and different methods. Repeating sending or carrying will deliver the message to destination or closer to destination.One of the possible ways for how to transfer data in DTN is usage of Social Based Opportunistic Routing (SBOR). This method can assume a flooding based routing [4] for sending “extended RREQ (E-RREQ) packet” and direct transfer of single copy forwarding based schema for sending of data. The selection of the next hop neighbour from potential nodes is provided by probability of delivery. This probability is calculated using message from E-RREQ packet. That message is about social relation and behaviour about D [8–11, 17]. Every node, which receives an E-RREQ for SBOR, calculates a probability of delivery and sends modified RREP for SBOR with calculated probability of delivery from E-RREQ. The source node receives probabilities from all neighbours and chooses the next hop node with best probability to send all data packets. This next hop will become new virtual source (V
S) of communication. New V
S tries to send data to another next node with suitable probability with a similar manner. If no neighbours of S
/
V
S are in radio range or the node already had the data or the nodes have unfit probability, then the node, which has the message, will store and carry this message, as long as it will be the better opportunity to relay the message. This process is repeated till the message arrives to destination node.Many other possibilities can be used for providing transfer of data through network. Their idea can work based on flooding or control flooding transfer. Other selections of the best candidate can be based on calculation of probability of delivery by social message or history of contacts among nodes.


## 5. Proposal of Hybrid Social Based Routing (HSBR) Algorithm

### 5.1. Integration of Social Based Internode Relation Message to HSBR

Our proposal of Hybrid Social Based Routing (HSBR) protocol considers that every mobile device/node is owned by a particular person. It is assumed that theS has message about D (owner’s message about node D). This message can be obtained as follows: (
1
) adding contact’s message to address book in mobile device and/or (
2
) exchanging personal profile between S and D at the first or later contact and/or (
3
) synchronizing and actualizing personal profile between S and D at every meeting.We defined an idea that relationship among nodes is calculated based on nodes profiles. Social relations are integrated to HSBR by defined node profiles. But there are many other possible methods for how to determine a probability of delivery. For example, it can be based on number of contacts, social relations, history of meeting, and so forth or by the combination of those methods [20].Nodes Profiles. The approach of social relation is considered in described proposal. For this purposepersonal (private) profile of node andcontact profile of node are used, which the device has in its address book. Both types of profiles have the same entries (Table 1), where entry represents string or number. E defines sequence of entry and W represents priority of entry.Table 1
Example of common set of entries for extension of RREQ.
Common set of entries
Number
Entry
E
Weight (W)
0
ID
0
1111
1
Surname
1
1000
2
Street (home)
2
1101
⋮
⋮
⋮
⋮
15
Tram (number of links)
F
110Personal (Private) Profile (PP). It is an obligatory profile in every device and all entries are necessary to be filled. These entries are filled by the owner of the device, so this profile represents the device and its owner.Contact Profile of Node (CP). It is common set of entries about people, which the owner of device knows. CP consists of partial or full message, which owner has in its address book about node. One CP belongs to one contact in address book. This CP of one node is perceived as additional message in E-RREQ used by path finding. Contact profile completes its owner using obligatory entries (unique identifier of the device and name of the person) or other optional entries (address where the person lives and works, how the person travels to work and home, where the person spends free time, and so forth).Every node has oneprivate (personal) profile and manycontacts profiles (address book). Every value and number of entries in personal profile and contact profile is changed to string of characters with same length usinghash mechanism MD5. Hash mechanism creates 128-bit length string of hexadecimal symbols of the hash functions from every row in personal and contact profile. These are called personal hash functions and contact hash functions. These hash functions are better for allocation of bits in the heather of RREQ, in comparison with other nodes and secure transfer [20, 21].


### 5.2. Detection and Usage of the Last Node

Usable path is monitored during the time of sending the data as process of route maintenance. This process is remodelled and described in modified DSR. In the case when no usable backup paths exist,S knows which node sent RERR and will send the rest of the data like priority task.In Figure7 is shown a lost connection between nodes and determination of last node on the partial path. It can be noticed that one node on the path lost radio link with its neighbour, which is the next hop on the initial path. Process of route maintenance will crash and the node 4, which determines losing of connection with neighbour node 10, will send RERR to S by partial path (4, 6, 3, 1, S).Figure 7
Detection and application of the last node.Node 4 is the last node on the partial path and will become a newV
S or S and as first step attempts to find path to destination with modified DSR. If first attempt is not successful it follows second attempting to send message in opportunistic manner with DTN routing.


### 5.3. A Description of Enhanced Hybrid Social Based Routing (HSBR) Algorithm

Hybrid Social Based Routing (HSBR) algorithm is optimal solution for well-connected networks or sparse network. From those cases we will be able to create network with sparsely or densely distributed mobile nodes with or without high mobility, with intermitted connection among nodes. The connections between couples S and D can be created with or without END-TO-END paths. Occurring networks can be divided into two or more islands (subnetworks) [15].HSBR algorithm (see Algorithm1) establishes delivery of message from S or V
S to D when standard MANET routing protocols fail or they are impossible to use. HSBR has an opportunity to deliver the message to D such as (i) using only modified DSR, when the path between S and D is founded and maintained, (ii) the message being gradually brought closer to destination node using the last node on disconnected path, when the path is found, but the topology is changed, process of maintenance will be crashed, or the well-connected island will be divided into two or more islands, and (iii) sending data to neighbour node with highest probability based on proposed DTN routing, when the network is sparse and no path exists between S and D.Algorithm 1:New proposal of HSBR algorithm.
(1)
Assumption_1: Personal profile (PP) and Contacts profiles (CP) exist in every device. PP is filled by owner of device and CP can
be filled by owner or retrieved from other nodes/mobile devices.
(2)
Assumption_2: Personal profile composes from created set of entries with the associated weight for each row.
(3)
Assumption_3: Plain text of entries is transformed using hash mechanism MD5 to unique Hash function for every string in
the PP and CP.
(4)
Assumption_4: Every node is located in specified area. Source (S) node 9 wants to transfer a message to Destination (D) 5 based
on proposed Hybrid MANET DTN routing. Social information is added to RREQ packet with message about D, which owns S.
Every node, which receives extended RREQ with additional message, will calculate a probability of delivery.
(5)
Initialization: Extended RREQ, PP and CP are used. Created set of entries are compared based on extended RREQ and PP
(6)S sends Extended RREQ for DTN routing to neighbour nodes
(7)
While The message does not arrive to the destination, time or number of hops will be not spend, do
(8)-S or V
S attempts to find destination using Modified DSR (M-DSR) routing algorithm at first.
(9)
If M-DSR crashed,do
IfUsable paths are found based on M-DSR, do
(i) Process of maintenance is used, when it is possible, in the manner, that the backup paths exist.
(ii) In the case, when no backup paths exist, S tries to use partial paths.
(iii) New source (V
S) is set and rest of data are sent to it, by partial path.
(iv) Source is perceived as a new source or virtual source (V
S) of communication and the process of HSBRstarts again
from Source.
(10)
Elseif Usable paths are not found based on M-DSR, do
(i) S selects the node with highest probability of delivery from neighbour nodes, based on DTN routing algorithm.
(ii) After this process S, as V
S, can be selected or the message is stored and carried in the storage of actual node till
a better situation arises in the network.
(iii) When the new source is selected, than the process of Hybrid MANET DTN routing starts again from V
S
End
(11)  Elseif M-DSR is not crashed, do
The transfer can be completed successfully.
EndProposal of HSBR algorithm works based on modified DSR protocol (see Section3.2) and SBOR algorithm (see Section 4).


### 5.4. Communication and Routing for HSBR

Every communication starts from source nodeS using M-DSR by finding of path, when E-RREQ is sent with additional message about D. Based on RREP packet, which is expected in S, the path between S and D is or is not known.Based on result of M-DSR the following situations are expected:(i)
RREP is returned to S. Connection during communication isnot interrupted or communication is maintained by standard reactive meaning. Subsequently, the message will be successfully delivered to the destination only by M-DSR.
(ii)
RREP is returned and during communication the connection isinterrupted, modified DSR with maintenance fails, two or more islands arise, and maintenance mechanism sends all data to the last node on the partial path. The choice of the last node is described in Section 5.2.
(iii)
RREP is not returned, so the path doesnot exist; only proposed SBOR can be used, because the destination node is in another island. Next hop is chosen by source node based on highest probability or second highest probability, when the node with highest probability is used during the same communication. This node will become virtual source of message. If no node from neighbours is usable based on probability of delivery, then the rest of the message remains in the node, which will be perceived as a V
S and process of HSBR will start again from new V
S.


## 5.1. Integration of Social Based Internode Relation Message to HSBR

Our proposal of Hybrid Social Based Routing (HSBR) protocol considers that every mobile device/node is owned by a particular person. It is assumed that theS has message about D (owner’s message about node D). This message can be obtained as follows: (
1
) adding contact’s message to address book in mobile device and/or (
2
) exchanging personal profile between S and D at the first or later contact and/or (
3
) synchronizing and actualizing personal profile between S and D at every meeting.We defined an idea that relationship among nodes is calculated based on nodes profiles. Social relations are integrated to HSBR by defined node profiles. But there are many other possible methods for how to determine a probability of delivery. For example, it can be based on number of contacts, social relations, history of meeting, and so forth or by the combination of those methods [20].Nodes Profiles. The approach of social relation is considered in described proposal. For this purposepersonal (private) profile of node andcontact profile of node are used, which the device has in its address book. Both types of profiles have the same entries (Table 1), where entry represents string or number. E defines sequence of entry and W represents priority of entry.Table 1
Example of common set of entries for extension of RREQ.
Common set of entries
Number
Entry
E
Weight (W)
0
ID
0
1111
1
Surname
1
1000
2
Street (home)
2
1101
⋮
⋮
⋮
⋮
15
Tram (number of links)
F
110Personal (Private) Profile (PP). It is an obligatory profile in every device and all entries are necessary to be filled. These entries are filled by the owner of the device, so this profile represents the device and its owner.Contact Profile of Node (CP). It is common set of entries about people, which the owner of device knows. CP consists of partial or full message, which owner has in its address book about node. One CP belongs to one contact in address book. This CP of one node is perceived as additional message in E-RREQ used by path finding. Contact profile completes its owner using obligatory entries (unique identifier of the device and name of the person) or other optional entries (address where the person lives and works, how the person travels to work and home, where the person spends free time, and so forth).Every node has oneprivate (personal) profile and manycontacts profiles (address book). Every value and number of entries in personal profile and contact profile is changed to string of characters with same length usinghash mechanism MD5. Hash mechanism creates 128-bit length string of hexadecimal symbols of the hash functions from every row in personal and contact profile. These are called personal hash functions and contact hash functions. These hash functions are better for allocation of bits in the heather of RREQ, in comparison with other nodes and secure transfer [20, 21].


## 5.2. Detection and Usage of the Last Node

Usable path is monitored during the time of sending the data as process of route maintenance. This process is remodelled and described in modified DSR. In the case when no usable backup paths exist,S knows which node sent RERR and will send the rest of the data like priority task.In Figure7 is shown a lost connection between nodes and determination of last node on the partial path. It can be noticed that one node on the path lost radio link with its neighbour, which is the next hop on the initial path. Process of route maintenance will crash and the node 4, which determines losing of connection with neighbour node 10, will send RERR to S by partial path (4, 6, 3, 1, S).Figure 7
Detection and application of the last node.Node 4 is the last node on the partial path and will become a newV
S or S and as first step attempts to find path to destination with modified DSR. If first attempt is not successful it follows second attempting to send message in opportunistic manner with DTN routing.


## 5.3. A Description of Enhanced Hybrid Social Based Routing (HSBR) Algorithm

Hybrid Social Based Routing (HSBR) algorithm is optimal solution for well-connected networks or sparse network. From those cases we will be able to create network with sparsely or densely distributed mobile nodes with or without high mobility, with intermitted connection among nodes. The connections between couples S and D can be created with or without END-TO-END paths. Occurring networks can be divided into two or more islands (subnetworks) [15].HSBR algorithm (see Algorithm1) establishes delivery of message from S or V
S to D when standard MANET routing protocols fail or they are impossible to use. HSBR has an opportunity to deliver the message to D such as (i) using only modified DSR, when the path between S and D is founded and maintained, (ii) the message being gradually brought closer to destination node using the last node on disconnected path, when the path is found, but the topology is changed, process of maintenance will be crashed, or the well-connected island will be divided into two or more islands, and (iii) sending data to neighbour node with highest probability based on proposed DTN routing, when the network is sparse and no path exists between S and D.Algorithm 1:New proposal of HSBR algorithm.
(1)
Assumption_1: Personal profile (PP) and Contacts profiles (CP) exist in every device. PP is filled by owner of device and CP can
be filled by owner or retrieved from other nodes/mobile devices.
(2)
Assumption_2: Personal profile composes from created set of entries with the associated weight for each row.
(3)
Assumption_3: Plain text of entries is transformed using hash mechanism MD5 to unique Hash function for every string in
the PP and CP.
(4)
Assumption_4: Every node is located in specified area. Source (S) node 9 wants to transfer a message to Destination (D) 5 based
on proposed Hybrid MANET DTN routing. Social information is added to RREQ packet with message about D, which owns S.
Every node, which receives extended RREQ with additional message, will calculate a probability of delivery.
(5)
Initialization: Extended RREQ, PP and CP are used. Created set of entries are compared based on extended RREQ and PP
(6)S sends Extended RREQ for DTN routing to neighbour nodes
(7)
While The message does not arrive to the destination, time or number of hops will be not spend, do
(8)-S or V
S attempts to find destination using Modified DSR (M-DSR) routing algorithm at first.
(9)
If M-DSR crashed,do
IfUsable paths are found based on M-DSR, do
(i) Process of maintenance is used, when it is possible, in the manner, that the backup paths exist.
(ii) In the case, when no backup paths exist, S tries to use partial paths.
(iii) New source (V
S) is set and rest of data are sent to it, by partial path.
(iv) Source is perceived as a new source or virtual source (V
S) of communication and the process of HSBRstarts again
from Source.
(10)
Elseif Usable paths are not found based on M-DSR, do
(i) S selects the node with highest probability of delivery from neighbour nodes, based on DTN routing algorithm.
(ii) After this process S, as V
S, can be selected or the message is stored and carried in the storage of actual node till
a better situation arises in the network.
(iii) When the new source is selected, than the process of Hybrid MANET DTN routing starts again from V
S
End
(11)  Elseif M-DSR is not crashed, do
The transfer can be completed successfully.
EndProposal of HSBR algorithm works based on modified DSR protocol (see Section3.2) and SBOR algorithm (see Section 4).


## 5.4. Communication and Routing for HSBR

Every communication starts from source nodeS using M-DSR by finding of path, when E-RREQ is sent with additional message about D. Based on RREP packet, which is expected in S, the path between S and D is or is not known.Based on result of M-DSR the following situations are expected:(i)
RREP is returned to S. Connection during communication isnot interrupted or communication is maintained by standard reactive meaning. Subsequently, the message will be successfully delivered to the destination only by M-DSR.
(ii)
RREP is returned and during communication the connection isinterrupted, modified DSR with maintenance fails, two or more islands arise, and maintenance mechanism sends all data to the last node on the partial path. The choice of the last node is described in Section 5.2.
(iii)
RREP is not returned, so the path doesnot exist; only proposed SBOR can be used, because the destination node is in another island. Next hop is chosen by source node based on highest probability or second highest probability, when the node with highest probability is used during the same communication. This node will become virtual source of message. If no node from neighbours is usable based on probability of delivery, then the rest of the message remains in the node, which will be perceived as a V
S and process of HSBR will start again from new V
S.


## 6. Simulations and Results

Proposal of HSBR is simulated and verified in software Matlab together with two other types of routing protocols: HSBR, DSR protocol based on RFC 4728, and SBOR based on social relation between nodes and probability of delivery.Set of variable’s values for our simulations can be seen in Table2. Simulations are oriented on comparison of three routing protocols, which are usable in MANET environment. In the simulations are observed some main results as success of transfers, success of packets delivery, delay of successful transfer, and, in addition, other analyses of simulated routing methods.Table 2
Set values of variables for simulations.
Variable
Value
Area [m]
1000 × 1000
Number of nodes
100
Radio range [m]
130
Number of transmitted messages
5
Limited number of attempts to send the message
200
Number of simulations repetitions
100
Velocity
(i) Slow walking
1.4 m/s
(ii) Fast walking
2.8 m/s
(iii) Running/cycling
5.6 m/s
(iv) Driving in a city
11.2 m/s
(v) Driving out of a city
22.4 m/sWe want to transfer the message fromS to D, which is not in the same network, because the start topology of mobile nodes consisted of 4 subnetworks without END-TO-END paths between S and D. The S is represented by node 9, which is in Figure 8 in the circle, and the destination node is represented by node 5, which is in Figure 8 in the diamond. All lines represent radio range connections between nodes. Figure 8 represents this same network in another time where the nodes are moving from start positions to other positions by influence of mobility. The delivery of message is provided by M-DSR finding path or using partial path and opportunistic jumping or carrying, depending on routing method.Figure 8
Example of mobile nodes deployment in initial time (time slot 0) and after some time period (time slot 5) for velocity 1.4 m/s.


### 6.1. Mobility Model

Positions of 100 nodes are located and generated in area of1000
×
1000 m. The movement of mobile nodes is created by random mobility model with different level of velocity. One possibility of deployment of mobile nodes is shown in Figure 8. This figure represents simulation in zero and fifth time slots. Based on this deployment four islands of connectivity are created, which are changed during the time. S and D nodes are selected from different islands in time slot 0 (Figure 8). The same start topology of the network from time slot 0 (Figure 8) is used for every beginning of simulations.The new position is created from previous position for every node in the network in every time slot, whose duration is 15 second. The movement of mobile nodes is depending on mobility model. Our simulation keeps position from every 15th second (one time slot), when deployment of nodes and communication links among nodes is displayed based on radio range. S/V
S tries to use given topology for sending data to destination or closer to the destination by selecting new V
S. It can find paths or try to use existing paths.


### 6.2. Messaging for Simulated Protocols

HSBR Algorithm. In every 15 sec time period, one message or some number of packets (one message should be represented by one or more packets) is sent to destination or closer to destination. When sending of the message is not possible for a different reason, the actual node with message or the rest of the message carries it to the next time slot.DSR. In every 15 sec time period, one packet of messages is sent by the actual or backup path. When the S and D are in different islands, the transfer is provided only by maintenance process.SBOR. In every 15 sec time period, full message is sent to neighbour or is carried by actual node. This process is repeated till the message reaches the D.We limited the number of attempts (NOA) for every simulation. The number of attempts means how many attempts can be used for communication, because every attempt represents time period in which it is possible to send data to destination or to next node which is closer to destination. On the other hand, when this limitation is perceived as time limitation which can be reached during transfer, the maximum delay for our simulation is 3000 sec due to taking of time period or time slot 15 sec. NOA has direct impact on success of delivery, because more attempts or longer time can provide better success of delivery for simulations.Every simulation of each routing protocol is repeated 100 times. It is applied for every level of velocity.


### 6.3. Success of Transfers

The main result of this simulation is evaluation of HSBR, SBOR, and DSR protocol by three types of transfers (Complete, Partial, and Null) (Figure9).Figure 9
Transfer success for HSBR, SBOR, and DSR represented by Complete, Partial, and Null transfer in simulations depending on velocity.Complete transfer represents number of simulations, in which complete message is transferred to destination node.Partial transfer represents number of simulations, in which not complete message is transferred to destination node (only some of the packets). It means that the transfers in given simulations are partially successful. Theoretically, longer simulation time can provide delivery of packets from partial transfer.Null transfer represents number of simulations, in which the path between source and destination is never created or source (virtual source) never met with destination. Zero packets of messages are delivered to destination node.One of most important results for transfer of message is delivering of full message to destination node. We show evolution of transfer for all created simulation in our research. Figure9 shows Complete, Partial, and Null type of transfer for HSBR, SBOR, and DSR method depending on velocity.First set of bars,Complete, represents number of simulations, which finished as successful, and full message is transmitted. Five bars represent five levels of velocity. It has decreased tendency for HSBR due to increasing velocity. HSBR reaches the highest number of successful simulations. DSR reaches very low number of successful transfers, because source and destination are in different subnetworks at the start of simulation and only process of maintenance provided searching of paths.Second set of bars,Partial, shows number of simulations, which finished only by some delivered packets for 5 levels of velocities. In this case, only a few packets from all required packets are delivered. In these results it is possible to get full message to destination by HSBR algorithm by more time slots. DSR cannot reach better result, because source and destination are in different subnetworks at the start of simulations. SBOR never reaches partial transfer, because it is opportunistic routing method. Full message is transmitted by every contact with other device. The result with minimum of partial transfer is perceived as the best.Third set of bars,Null, represents the result of number of simulations for five levels of velocity, which finished by error or without possibility to transfer message or some packets to destination node by path, partial path, or meeting. HSBR reaches the best result, because number of simulations is lowest for every velocity.


### 6.4. Success of Packets Delivery and Average Delay

The next simulations are focused on delay of only successful delivered messages from source to destination. Delay in these cases means how long is the message transferred through network, until the message reaches the destination node. It is depending on used routing method and velocity level. Shown results (Figure10) of delay are displayed together with success of delivery.Figure 10
Success of delivery and average delay (only successful deliveries) for Hybrid Social Based Routing, Social Based Opportunistic Routing, and DSR protocol.Average delay for successful delivering of message is increasing for HSBR due to velocity. For low velocity where success is almost 100%, the average delay for successful delivering is the lowest.On the other hand, for the same scenario and velocity, but other routing method, SBOR is much higher, because by low velocity message is transmitted through network slower.Finally, from Figure10 it is perceived that the delay is lowest for DSR protocol. The result, which is shown, represents only successful deliveries and DSR has very low number of successful deliveries, because the network was dividing, dynamically changing, and with high velocity of mobile devices. For that reason, DSR receives the lowest delay, but on the other hand DSR does not have suitable success, what is more important.For the hybrid network, which can be sparse or dense, with low or high velocity, and in addition can be created from one or many subnetworks, some delay is allowed, because the main reason of this network is successful transfer. Our proposal had good success with suitable delay.


### 6.5. Success of Delivery and Number of Attempts

The main result of this simulation is identification of differences among routing protocols and determining which routing protocol is the best solution for successful delivery of packets from S to D for disconnected MANET due to velocity. Those results of simulations are displayed together with the average number of attempts to deliver packets to destination and with standard deviation of NOA.One of the main results, success of delivery, is represented by percentage of received packets and all packets necessary to be sent during all simulations. The other result, average number of attempts with standard deviation, shows how many attempts are needed to reach given success of delivery. Standard deviation shows differences in quantity of NOA for this simulation due to mobility model.Left axes together with bar graphs in Figure11 represent average success of delivery for Hybrid Social Based Routing (HSBR), Social Based Routing (SBOR), and Dynamic Source Routing (DSR). Right axis together with green line represents average number of attempts for successful deliveries for all three methods. The last parameter in Figure 11 is standard deviation (7) for number of attempts, where N represents number of success transfers of message to D, x
i represents NOA for i simulation, and x
- represents average value of NOA for given velocity. All routing methods are simulated for 5 levels of velocity:(7)
σ
=
1
N
∑
i
=
1
N
x
i
-
x
¯
2
.Figure 11
Success of delivery, average number of attempts (NOA) with standard deviation for Hybrid Social Based Routing, Social Based Opportunistic Routing, and DSR protocol.The highest success of delivery is reached by HSBR algorithm with decreased tendency due to increased velocity. Low average number of attempts for successful deliveries is for slow movement, 4.2 m/s with the lowest standard deviation of number of attempts. NOA and standard deviation have increasing tendency for higher velocities. Standard deviation reaches higher values for different velocities, because simulation’s movements are different from each other due to mobile nodes’ random movement.On the other hand, SBOR gets lower success for lower velocities with comparison with HSBR. We get similar success for higher velocities for SBOR and HSBR, but with different average number of attempts. SBOR has much higher NOA compared with HABR for the velocity 1.4 m/s and standard deviation is higher too.Finally, after comparison of hybrid, opportunistic, and MANET solution with the same mobile environment, it is possible to write that MANET protocol DSR is not suitable. This is because of selection of S and D from different subnetworks. In our case, when S and D occur in different subnetworks at the start of simulation, we get very low success of delivery in cases, when SBOR, especially HSBR, reaches much higher results. This success of delivery is decreasing due to velocity. We can see the average values of NOA for successful deliveries are almost the same and the values of the success are multiply higher in comparison with HSBR. The higher velocities cause that the average values of NOA for the successful DSR transfers become the lowest in comparison with other methods. On the other hand, if there is only one successful transfer from 100 transfers, the DSR has the lowest values of the NOA. Based on the results, we can conclude that the DSR has the low values of NOA taking into account the success of delivery, but it is unusable for hybrid networks and higher velocity levels.


### 6.6. Analyses of HSBR

Average Number of Maintenance of Communication by Paths and Partial Paths in HSBR. The main idea of result, process of maintenance for HSBR, is focused on average number of attempts needed to keep communication by HSBR algorithm for five levels of velocity. The limitation of duration in terms of allowed number of attempts for simulation is changed and continually extended from 5 to 200 by the step 5 attempts. It is possible to observe in Figure 12 that average number of maintenance is growing up from 5 to 60 allowed numbers of attempts for simulations radically and softly later. It is mostly for velocities 1.4–5.6 m/s.Figure 12
Average number of maintenance process for proposed HSBR algorithm by paths between source/virtual source and destination.This result represents a possibility of network to keep communication and transfer packets by founded paths. When average number of maintenance is low, it means that transfer is provided by DTN transfer mostly. For example, this situation can be observed by velocity 22.4 m/s.Average Number of Opportunistic Transfers in HSBR. The result shown in Figure 13 represents average number of DTN transfers for HSBR depending on  allowed number of attempts from 5 to 200 with the step 5 attempts for five levels of velocity. Higher velocity has direct impact on number of DTN transfers, because the network is divided and changed due to movement. Number of DTN transfers represents transfer of message from device to device based on probability of delivery or carrying the message through network by some device until the destination is found or the time of simulation expires.Figure 13
Average number of opportunistic transfers depending on allowed number of attempts for five levels of velocity.The slowest movement reaches lower values of DTN transfer due to founding and maintaining paths between source and virtual source to destination node.


### 6.7. Success of Delivery Depending on Allowed Number of Attempts for HSBR and SBOR

We want to show impact of allowed number of attempts to success of delivery for HSBR and SBOR algorithm in Figures14 and 15. Allowed number of attempts is continually increased from 5 to 200 attempts with the step 5 attempts. Success of delivery is inversing due to increasing number of attempts, because number of attempts has direct impact on allowed time of delivery.Figure 14
Success of delivery for HSBR depending on permitted number of attempts to communicate for 5 speed limits.Figure 15
Success of delivery for SBOR, depending on allowed number of attempts for five levels of velocity.Longer time of delivery can influence success of delivery in positive form. Simulations with slower movement have lower success of delivery for increasing number of attempts as faster velocities, especially for the velocity level 11.2 m/s for SBOR. On the other hand, HSBR reaches highest success of delivery for lowest velocity level depending on allowed number of attempts.


## 6.1. Mobility Model

Positions of 100 nodes are located and generated in area of1000
×
1000 m. The movement of mobile nodes is created by random mobility model with different level of velocity. One possibility of deployment of mobile nodes is shown in Figure 8. This figure represents simulation in zero and fifth time slots. Based on this deployment four islands of connectivity are created, which are changed during the time. S and D nodes are selected from different islands in time slot 0 (Figure 8). The same start topology of the network from time slot 0 (Figure 8) is used for every beginning of simulations.The new position is created from previous position for every node in the network in every time slot, whose duration is 15 second. The movement of mobile nodes is depending on mobility model. Our simulation keeps position from every 15th second (one time slot), when deployment of nodes and communication links among nodes is displayed based on radio range. S/V
S tries to use given topology for sending data to destination or closer to the destination by selecting new V
S. It can find paths or try to use existing paths.


## 6.2. Messaging for Simulated Protocols

HSBR Algorithm. In every 15 sec time period, one message or some number of packets (one message should be represented by one or more packets) is sent to destination or closer to destination. When sending of the message is not possible for a different reason, the actual node with message or the rest of the message carries it to the next time slot.DSR. In every 15 sec time period, one packet of messages is sent by the actual or backup path. When the S and D are in different islands, the transfer is provided only by maintenance process.SBOR. In every 15 sec time period, full message is sent to neighbour or is carried by actual node. This process is repeated till the message reaches the D.We limited the number of attempts (NOA) for every simulation. The number of attempts means how many attempts can be used for communication, because every attempt represents time period in which it is possible to send data to destination or to next node which is closer to destination. On the other hand, when this limitation is perceived as time limitation which can be reached during transfer, the maximum delay for our simulation is 3000 sec due to taking of time period or time slot 15 sec. NOA has direct impact on success of delivery, because more attempts or longer time can provide better success of delivery for simulations.Every simulation of each routing protocol is repeated 100 times. It is applied for every level of velocity.


## 6.3. Success of Transfers

The main result of this simulation is evaluation of HSBR, SBOR, and DSR protocol by three types of transfers (Complete, Partial, and Null) (Figure9).Figure 9
Transfer success for HSBR, SBOR, and DSR represented by Complete, Partial, and Null transfer in simulations depending on velocity.Complete transfer represents number of simulations, in which complete message is transferred to destination node.Partial transfer represents number of simulations, in which not complete message is transferred to destination node (only some of the packets). It means that the transfers in given simulations are partially successful. Theoretically, longer simulation time can provide delivery of packets from partial transfer.Null transfer represents number of simulations, in which the path between source and destination is never created or source (virtual source) never met with destination. Zero packets of messages are delivered to destination node.One of most important results for transfer of message is delivering of full message to destination node. We show evolution of transfer for all created simulation in our research. Figure9 shows Complete, Partial, and Null type of transfer for HSBR, SBOR, and DSR method depending on velocity.First set of bars,Complete, represents number of simulations, which finished as successful, and full message is transmitted. Five bars represent five levels of velocity. It has decreased tendency for HSBR due to increasing velocity. HSBR reaches the highest number of successful simulations. DSR reaches very low number of successful transfers, because source and destination are in different subnetworks at the start of simulation and only process of maintenance provided searching of paths.Second set of bars,Partial, shows number of simulations, which finished only by some delivered packets for 5 levels of velocities. In this case, only a few packets from all required packets are delivered. In these results it is possible to get full message to destination by HSBR algorithm by more time slots. DSR cannot reach better result, because source and destination are in different subnetworks at the start of simulations. SBOR never reaches partial transfer, because it is opportunistic routing method. Full message is transmitted by every contact with other device. The result with minimum of partial transfer is perceived as the best.Third set of bars,Null, represents the result of number of simulations for five levels of velocity, which finished by error or without possibility to transfer message or some packets to destination node by path, partial path, or meeting. HSBR reaches the best result, because number of simulations is lowest for every velocity.


## 6.4. Success of Packets Delivery and Average Delay

The next simulations are focused on delay of only successful delivered messages from source to destination. Delay in these cases means how long is the message transferred through network, until the message reaches the destination node. It is depending on used routing method and velocity level. Shown results (Figure10) of delay are displayed together with success of delivery.Figure 10
Success of delivery and average delay (only successful deliveries) for Hybrid Social Based Routing, Social Based Opportunistic Routing, and DSR protocol.Average delay for successful delivering of message is increasing for HSBR due to velocity. For low velocity where success is almost 100%, the average delay for successful delivering is the lowest.On the other hand, for the same scenario and velocity, but other routing method, SBOR is much higher, because by low velocity message is transmitted through network slower.Finally, from Figure10 it is perceived that the delay is lowest for DSR protocol. The result, which is shown, represents only successful deliveries and DSR has very low number of successful deliveries, because the network was dividing, dynamically changing, and with high velocity of mobile devices. For that reason, DSR receives the lowest delay, but on the other hand DSR does not have suitable success, what is more important.For the hybrid network, which can be sparse or dense, with low or high velocity, and in addition can be created from one or many subnetworks, some delay is allowed, because the main reason of this network is successful transfer. Our proposal had good success with suitable delay.


## 6.5. Success of Delivery and Number of Attempts

The main result of this simulation is identification of differences among routing protocols and determining which routing protocol is the best solution for successful delivery of packets from S to D for disconnected MANET due to velocity. Those results of simulations are displayed together with the average number of attempts to deliver packets to destination and with standard deviation of NOA.One of the main results, success of delivery, is represented by percentage of received packets and all packets necessary to be sent during all simulations. The other result, average number of attempts with standard deviation, shows how many attempts are needed to reach given success of delivery. Standard deviation shows differences in quantity of NOA for this simulation due to mobility model.Left axes together with bar graphs in Figure11 represent average success of delivery for Hybrid Social Based Routing (HSBR), Social Based Routing (SBOR), and Dynamic Source Routing (DSR). Right axis together with green line represents average number of attempts for successful deliveries for all three methods. The last parameter in Figure 11 is standard deviation (7) for number of attempts, where N represents number of success transfers of message to D, x
i represents NOA for i simulation, and x
- represents average value of NOA for given velocity. All routing methods are simulated for 5 levels of velocity:(7)
σ
=
1
N
∑
i
=
1
N
x
i
-
x
¯
2
.Figure 11
Success of delivery, average number of attempts (NOA) with standard deviation for Hybrid Social Based Routing, Social Based Opportunistic Routing, and DSR protocol.The highest success of delivery is reached by HSBR algorithm with decreased tendency due to increased velocity. Low average number of attempts for successful deliveries is for slow movement, 4.2 m/s with the lowest standard deviation of number of attempts. NOA and standard deviation have increasing tendency for higher velocities. Standard deviation reaches higher values for different velocities, because simulation’s movements are different from each other due to mobile nodes’ random movement.On the other hand, SBOR gets lower success for lower velocities with comparison with HSBR. We get similar success for higher velocities for SBOR and HSBR, but with different average number of attempts. SBOR has much higher NOA compared with HABR for the velocity 1.4 m/s and standard deviation is higher too.Finally, after comparison of hybrid, opportunistic, and MANET solution with the same mobile environment, it is possible to write that MANET protocol DSR is not suitable. This is because of selection of S and D from different subnetworks. In our case, when S and D occur in different subnetworks at the start of simulation, we get very low success of delivery in cases, when SBOR, especially HSBR, reaches much higher results. This success of delivery is decreasing due to velocity. We can see the average values of NOA for successful deliveries are almost the same and the values of the success are multiply higher in comparison with HSBR. The higher velocities cause that the average values of NOA for the successful DSR transfers become the lowest in comparison with other methods. On the other hand, if there is only one successful transfer from 100 transfers, the DSR has the lowest values of the NOA. Based on the results, we can conclude that the DSR has the low values of NOA taking into account the success of delivery, but it is unusable for hybrid networks and higher velocity levels.


## 6.6. Analyses of HSBR

Average Number of Maintenance of Communication by Paths and Partial Paths in HSBR. The main idea of result, process of maintenance for HSBR, is focused on average number of attempts needed to keep communication by HSBR algorithm for five levels of velocity. The limitation of duration in terms of allowed number of attempts for simulation is changed and continually extended from 5 to 200 by the step 5 attempts. It is possible to observe in Figure 12 that average number of maintenance is growing up from 5 to 60 allowed numbers of attempts for simulations radically and softly later. It is mostly for velocities 1.4–5.6 m/s.Figure 12
Average number of maintenance process for proposed HSBR algorithm by paths between source/virtual source and destination.This result represents a possibility of network to keep communication and transfer packets by founded paths. When average number of maintenance is low, it means that transfer is provided by DTN transfer mostly. For example, this situation can be observed by velocity 22.4 m/s.Average Number of Opportunistic Transfers in HSBR. The result shown in Figure 13 represents average number of DTN transfers for HSBR depending on  allowed number of attempts from 5 to 200 with the step 5 attempts for five levels of velocity. Higher velocity has direct impact on number of DTN transfers, because the network is divided and changed due to movement. Number of DTN transfers represents transfer of message from device to device based on probability of delivery or carrying the message through network by some device until the destination is found or the time of simulation expires.Figure 13
Average number of opportunistic transfers depending on allowed number of attempts for five levels of velocity.The slowest movement reaches lower values of DTN transfer due to founding and maintaining paths between source and virtual source to destination node.


## 6.7. Success of Delivery Depending on Allowed Number of Attempts for HSBR and SBOR

We want to show impact of allowed number of attempts to success of delivery for HSBR and SBOR algorithm in Figures14 and 15. Allowed number of attempts is continually increased from 5 to 200 attempts with the step 5 attempts. Success of delivery is inversing due to increasing number of attempts, because number of attempts has direct impact on allowed time of delivery.Figure 14
Success of delivery for HSBR depending on permitted number of attempts to communicate for 5 speed limits.Figure 15
Success of delivery for SBOR, depending on allowed number of attempts for five levels of velocity.Longer time of delivery can influence success of delivery in positive form. Simulations with slower movement have lower success of delivery for increasing number of attempts as faster velocities, especially for the velocity level 11.2 m/s for SBOR. On the other hand, HSBR reaches highest success of delivery for lowest velocity level depending on allowed number of attempts.


## 7. Conclusion and Future Work

In this paper, the Enhanced Hybrid Social Based Routing (HSBR) algorithm for MANET-DTN is proposed after analyses of MANET and DTN routing and forwarding methods. This solution is usable in situations when the infrastructure is destroyed due to a natural disaster or in areas where infrastructure was never created. This routing solution can be used as backup-free method for transfer of messages (text, voice, photos, etc.) in society, but with assumption of expected delay in some situations.The optimal routing protocol can be chosen after analyses of the results. Not all routing methods, which are presented, can be used for all velocities in such MANET environment. Our simulated MANET environment is created by mobile devices with different level of velocity for different type of simulations. The network can be sparse and dense, consisting of one and more subnetworks or islands. These islands are sequentially connected, disconnected, and reorganized due to mobility during simulations. We use three routing methods in this difficult and divergent MANET environment, Dynamic Source Routing (DSR), Social Based Opportunistic Routing (SBOR) algorithm, and Hybrid Social Based Routing (HSBR) algorithm. All routing methods have to transfer the message from source to destination node based on its features. Results show big differences and some similarity between them.DSR protocol is usable for MANET environment, which is well-connected; source and destination are in the same subnetwork and velocity level of mobile nodes is low.SBOR algorithm as our proposal of social opportunistic routing can provide transfer of message in such MANET environment based on probability of delivery. Higher velocities are helpful for this type of opportunistic routing.HSBR algorithm is a new proposal of hybrid method for complicated and diversified MANET-DTN environment with different level of velocities of mobile devices. HSBR has an opportunity to use paths between source and destination especially for lower level of velocities and get high success. On the other hand, for more divided networks due to higher velocities it is possible to use DTN mechanism in hybrid solution, which provides transfer based on probability of delivery. HSBR gets the best success for our MANET environment. The extension of the MANET routing protocol DSR by DTN mechanism store-carry-forward enables the transmission between S and D. Our simulations reach higher standard deviation. We want to implement new model of mobility for devices, social mobility model, which can improve success of delivery for SBOR and HSBR methods.For as much as DSR provides transfer in well-connected networks with low movement and SBOR reaches suitable success by higher speed of movement, consequently HSBR, as new method, has an opportunity to provide transfer of message in diversified type of MANET environment. The SBOR and HSBR expand the functionalities of the using of MANET. The main idea of HSBR is ensuring transfer of message from source to destination from different start conditions and different continuance of mobile network.We want to create social mobility model for mobile nodes and compare the results.



---

*Source: 4803242-2016-04-30.xml*