# A Routing Algorithm for the Sparse Opportunistic Networks Based on Node Intimacy

Authors: Gang Xu; Xinyue Wang; Na Zhang; Zhifei Wang; Lin Yu; Liqiang He
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Opportunistic networks are becoming more and more important in the Internet of Things. The opportunistic network routing algorithm is a very important algorithm, especially based on the historical encounters of the nodes. Such an algorithm can improve message delivery quality in scenarios where nodes meet regularly. At present, many kinds of opportunistic network routing algorithms based on historical message have been provided. According to the encounter information of the nodes in the last time slice, the routing algorithms predict probability that nodes will meet in the subsequent time slice. However, if opportunistic network is constructed in remote rural and pastoral areas with few nodes, there are few encounters in the network. Then, due to the inability to obtain sufficient encounter information, the existing routing algorithms cannot accurately predict whether there are encounters between nodes in subsequent time slices. For the purpose of improving the accuracy in the environment of sparse opportunistic networks, a prediction model based on nodes intimacy is proposed. And opportunistic network routing algorithm is designed. The experimental results show that the ONBTM model effectively improves the delivery quality of messages in sparse opportunistic networks and reduces network resources consumed during message delivery.


---

## Body

## 1. Introduction

In the early days, wireless networks used fixed infrastructure for communication. The infrastructure is called a wireless access point, which can receive wireless signals and connect to a wired network. The wireless communication terminal is connected to the AP. When the wireless communication terminal communicates with other nodes, the message must be routed through the AP. Although the terminal has achieved wireless access to the network, the terminal can only move within the signal coverage area of the infrastructure, and the network topology is stable. In this wireless network, although the communication terminal can move as a node, the nodes communicating with each other still requires infrastructure, such as a cellular network or a wireless local area network with the help of infrastructure (such as a wireless router).In order to solve the terminal’s reliance on infrastructure and use wireless network technology in a wider field or a harsh environment, researchers have proposed a wireless MANET (mobile ad hoc network). MANET has good adaptability to changes in topology and does not need to build infrastructure. When the node wants to communicate, other wireless nodes forward messages hop by hop to complete the communication task, and the nodes that pass through during forwarding form a wireless communication link. This technology is often used for communications in military environments and harsh environments. In wireless mobile ad hoc network, one or more stable links need to be established between communicating nodes, that is, the network is basically connected within a period of time.However, under more severe conditions, all nodes in the network are mobile. Not only does the network have no infrastructure to use, but also, it has no basic connected links. The nodes are in multiple disconnected areas, and these areas are connected by the mobile nodes over a period of time. In this kind of network, people move randomly, there is no stable connection between nodes, which causes the topology of the network to change all the time, and there is almost no link between the two nodes. In this case, if the traditional wireless mobile ad hoc network routing algorithm is used for message transmission, the communication success rate is very low. Since it is necessary to wait for the establishment of a connected link during routing, the communication delay is greatly increased and the communication opportunity is lost.For solving the above-mentioned problem of intermittent network connectivity, researchers proposed the concept of opportunistic networks [1]. Opportunistic network evolved from wireless MANET, which is not same as the traditional wireless MANET. In opportunistic networks, because communication nodes are mobile and signals are frequently interrupted by interference, there are no stable communication links between nodes, and the network is divided into multiple disconnected subnetworks [2–4]. Therefore, in traditional wireless ad hoc networks, message routing strategies based on end-to-end links cannot be applied in opportunistic networks. In opportunistic networks, an opportunistic network routing strategy of “storage-carry-forward” is adopted [5, 6]. That is, when the split network cannot be connected, the message is stored locally; when the split network is bridged by the mobile node, the message is forwarded.


## 2. Related Work

Routing algorithm is the focus of research in the field of opportunistic network. A detailed description of the opportunistic network routing algorithm is as follows.There are two types of opportunistic network routing algorithm [7]. One is zero-message, including flooding mechanism [8], direct forwarding mechanism [9], two-hop forwarding mechanism [10], and fixed backup mechanism [11, 12]. The other is message-assisted, including routing algorithms based on data attributes [13, 14], routing algorithms based on node information [15–17], routing algorithms based on topology information [18, 19], and routing algorithm for information fusion [20, 21]. In recent years, some researchers studied opportunities networks using methods such as sensor networks, machine learning [22–24], and social networks in many different kinds of scenes. For example, wireless sensor networks (WSNs) [25–27] is used to analyse opportunities networks. What is more, some researchers [28–31] established models based on machine learning for optimal routing in the opportunistic network. However, the time series and sociality are more important to improve the message transmission quality [32–34]. In recent years, some scholars have integrated opportunistic network routing algorithms with Internet of Vehicles and edge computing to promote the development of the two fields [35–37].Opportunistic networks have high utilization value for future communication networks, Internet of Things [38, 39], wireless sensor networks, etc. By studying the information of the nodes in the last time slice, the existing history-based opportunistic network routing algorithms predict the probability that nodes will meet in the next time slice. However, due to vast territory and small population in rural and pastoral areas, few nodes and encounters existed in the opportunistic network. Therefore, the existing opportunistic network routing algorithms obtained little encounter information in previous time slices and cannot accurately predict whether there are encounters between nodes in subsequent time slices, which will decrease the success rate of message delivery and result in an increase in delivery latency. Due to the existing history-based opportunistic network, routing algorithms are not fit to applied in rural and pastoral areas, that is to say, it is not suitable for the opportunistic network environment with sparse nodes of pedestrians. Therefore, this paper studies the node intimacy model, and the opportunistic network routing algorithm is provided. The proposed algorithm improves the efficiency of data forwarding in the sparse opportunity network composed of pedestrians.There are two challenges for the algorithm based on history behavior of nodes: formal representation of encounter records and the way for converting into encounter state; classification of node encounter state.In this paper, the main contributions include the following:(1)
According to characteristics of node behavior, contact duration, and encounter interval, we quantify the encounter records of nodes(2)
We constructed the probabilistic model of node encounter state for dynamic social relationship and classified the encounter state by using support vector machine. Based on the encounter state, the node intimacy calculation model is established(3)
An opportunistic network routing algorithm ONBTM is proposed to forward messages in the network(4)
The final results show that the ONBTM algorithm can achieve higher message delivery quality with less resource consumption than other routing algorithms, including epidemic, spray and wait, and prophet algorithm.In this paper, the rest of the sections are organized as follows. Some preliminary knowledge are provided in “Problem Definition.” In “Opportunistic Network Routing Algorithm Based on Node Intimacy,” we introduced the algorithm in detail. Simulation experiments and some useful results are obtained in “Experiments.” The main work of this paper is concluded in “Conclusion.”


## 3. Problem Definition

We firstly give several preliminary knowledge, including time series, initial state of node encounter, marked state of node encounter, node intimacy, and node intimacy based on time series.Definition 1.
Time series. LetRi=T0,T1,⋯,Tk, where Tk denotes the kth time slice and Ri is a time series. In the opportunistic network, time series is used to analyse the periodic laws of node movement models, social relationships, encounter timings, and changes of communication state.Definition 2.
Initial state of encounter. LetRc=Cij0≤i≤n,0≤j≤n, n is the node number, and Cij denotes initial state when the node i and the node j encounter with each other. TEij describes the communication time of the node i and the node j, and TCij denotes the time required for nodes i and j to transmit a valid data. PCij,Tk describes the state of the nodes i and j which meet in the kth time slice, where C∈0,1. The initial state of encounter indicates the time that node remains within the range of communication, where Cij=TCij/TEij.Definition 3.
Marked state of encounter. In the opportunistic network, encounter state can be divided into two types: valid encounter state and invalid encounter state. A valid encounter indicates that there may be some correlation between nodes, which can be used for data transmission. Invalid encounter represents that there is no association between nodes. BecauseCij is uncertain, it is necessary to map the encounter state to valid state or invalid state to indicate whether the encounter of nodes i and j is valid. The mapped encounter state is represented by C_Satij=C_Satij∣0,C_Satij∣1C_Satij∣0=0,C_Satij∣1=1.LetRC_Sat=C_Satij0≤i≤n,0≤j≤n represent the set of marked states that nodes meet each other in the opportunistic network, where C_Satij is the encounter state after node i and node j are mapped and n denotes the node number.For analysing the existence of encounter relationship between nodes, the initial encounter state needs to be mapped to marked state.Rc indicates that the initial state set of nodes meets any element in the set Cij∈0,1. It is necessary to map initial state Cij to marked state C_Satij by using the mapping function FCij=C_Satij. The mapping model of encounter state is defined by FRC→RC_Sat=fCij→C_Satij, where Cij∈RC,C_Satij∈RC_Sat,i∈0,n,j∈0,n and n represents node number in the network.
(1)f:RC→RC_Sat,Rt=fCif→C_SatifTx,0≤x≤α=∑x=0αwx⋅ϕTx+b,whereK is called the latest time slice in the time slice series, wx is the complexity of mapping, Tx is the time slice, ΦTx is mapping function, and b is mapping factor. The model of Equation (1) describes support vector regression model for mapping the initial state into marked state. The optimization problem of Equation (1) can be abstracted into minimum loss model of minEw:
(2)minEw=12w⋅w+C∑x=α+1kTx−fCij→C_SatijTx,0≤x≤αε.In the model of Equation (2), w⋅w describes the complexity of function ∑x=α+1kTx−fCij→C_SatijTx,0≤x≤αε in Equation (1) which represents the average loss on the training set; constant C is used to reduce the complexity fx and decrease the average loss. Equation (2) is used to optimize Equation (1). Equation (3) is optimized by Equation (2).
(3)minw,ξx,ξx∗,b12w⋅w+C⋅1k∑T=1kξx+ξx∗s.t.w⋅ϕXT+b−CSatij≤ε+ξxCSatij−w⋅ϕTx+b≤ε+ξx∗,whereξx,ξx∗≥0.
(4)maxβx,βx∗∑x=1kβx∗CSatij−ε−βxCSatij+ε−12∑x=1k∑y=1kβx−βx∗βy−βx∗Kβx,βys.t.∑x=1kβx−βx∗=0,0≤βx,βx∗≤ck.In Equation (4), Kβx,βy=ϕβxϕβy denotes the kernel function, and we use it to predict the experimental results, β,β∗ is the solution. In order to map the initial encounter state to marked state, state mapping model is constructed with Equation (1). In Equation (1), parameter b is uncertain. Equation (5) is derived from Equations (1), (3), and (4).
(5)fCij→C_SatijTx,0≤x≤α=∑x=0αβx¯−βx∗¯Kβx,βy+b¯.By using Equation (5), we can obtain the mapping factor b¯.
(6)b¯=CSatij−∑y=0αβy−βx∗Kβx,βy−ε,βx∈0,ck.Based on above analysis, the initial encounter state is first established between the nodes. And then, the initial state is mapped to the marked state using the node state mapping model.Based on marked encounter state of nodes, opportunistic network probabilistic routing based on node intimacy is designed, which relies on the prediction of likelihood of nodes encountering. In order to calculate the probability of nodes meeting, node intimacy model is proposed.Definition 4.
Node intimacy. Node intimacy represents the intimacy of social relationships between nodes. The higher the intimacy, the bigger possibility that the nodes meet with each other. In the opportunistic network, the node intimacy of any two nodesu and v is calculated by Equation (7):
(7)Cohu,v=12nc∑u=1c∑v=1cAuvPuv,
wherec is the node number in the opportunistic network topology, Puv denotes the historical encounter probability of nodes, and Auv describes the social network topology of the opportunistic network.Definition 5.
Node intimacy based on time series. LetPr_cohu,v denote the probability of intimacy between nodes a and b. Pr_cohu,vold denotes the probability of intimacy in previous time slice between nodes u and v. Pr_cohinit is the initialization constant between nodes, which is computed by Equation (7). For all nodes in the opportunistic network, the probability Pr_cohu,v=Pr_cohu,vold+1−Pr_cohu,vold∗Pr_cohinit generally takes initial intimacy of any two nodes u and v. The initial intimacy values on possible worlds of opportunistic networks are denoted by OptN. By using intimacy of the last time slice node u and node v, we can calculate the intimacy Pr_cohu,v of nodes a and b under the current time. Pr_cohu,v is susceptible to the frequency of node encounters in the current time slice, which may cause the calculated node intimacy to have jumps in different time slices. In order to overcome the sensitivity of Pr_cohu,v to the frequency of node encounters in different time slices, we define new intimacy probability Pr_cohu,vnew from node u to node v on the opportunistic networks named OptN.
(8)Pr_cohu,vnew=Pr_cohu,vold∗last_timecur_time+Pr_cohu,vold∗cur_time−last_timecur_time.
For all the nodeu∈VN, we can compute the Pr_cohu,vnew by Equation (8). The last_time is the time slice that recently updated the probability value of node intimacy, and cur_time is time since the opportunistic network has been running.


## 4. Opportunistic Network Routing Algorithm Based on Node Intimacy

Let node intimacy describe the valid encounter of nodes. Node intimacy can predict the encounter probability of nodes in a future time slice. Based on the fusion of historical encounter probability and time series, the method of calculating node intimacy is proposed.Algorithm1 calculates the node intimacy of nodes u and v, and Pr_cohu=Pr_cohv=Pr_cohu,v.Algorithm 1:Pr_cohOptNnew.
1:for all u∈VOptNdo2:Pr_cohinit←random(0,1)3:end for4:for all v∈VOptNdo5:Pr_cohu,v←Pr_cohu,vold+1−Pr_cohu,vold∗Pr_cohinit6:cur_time←get_current_slice_time7:last_time←get_last_slice_time8:α←Pr_cohu,vold∗last_time+Pr_cohu,v∗cur_time−last_time/cur_time9:Pr_cohu,vnew←α10:end for11:returnPr_cohOptNnewBy calculating node intimacy, opportunistic network routing algorithm based on node intimacy is proposed. The routing algorithm balances resource consumption, delivery latency, and delivery success rate. And it is a multicopy replication propagation routing algorithm, which is message-limited. In Algorithm1, when node A carrying message M meets node B, they exchange their message list. If there is no message M in node B’ message list, B obtains the permission to transmit the message M. Then node A and node B compare their transmission predictions Pr_cohOptNnew. If Pr_cohB≥Pr_cohA, node A copies the carried message M to node B. In opportunistic network topology, messages are always propagated in the direction that has a higher probability of reaching the target node.Algorithm 2: ONBTM.
1:S∈VOptN2:for all A∈VOptNdo3:A←S. request ()4:ifPr_cohA≥Pr_cohSthen5:  S←A.service_confirm()6:end if7:if S.get(A.service_confirm()) then8:  A.buffer()←S.send(M)9:end if10:end for11: updatePr_cohS,Anew12:returnPr_cohS,AnewIn Algorithm2, S.request() is the request sent by node S to node A. The request message contains the id and size of the message M, and destination node. A.service_confirm() is receiving service confirmation sent to A when node A receives node S. Node S sends the message after receiving the confirmation from node A, finally updating the intimacy of node A and node S.


## 5. Experiments

We conducted several experiments to evaluate proposed algorithms. The experimental results are as follows.


### 5.1. Experimental Setting

The experiments were run on a Thinkpad T440p with 2.5GHz Intel Core i5 CPU and 16GB of RAM, and Windows 10 is installed on the machine.By using the famous simulation platform ONE (Opportunistic Networking Environment) [2], we simulated a sparse opportunistic network with pedestrians as nodes. In the network, the node speed is the walking speed, and the node storage size is set to a smaller value. We also simulated the opportunistic network routing algorithm based on node intimacy. Then, the proposed algorithm are compared with several well-known routing algorithms, for example, prophet, epidemic, and spray and wait. For the purpose of making the experimental environment more stable, it is necessary to generate message after simulation platform runs for 1000 seconds. The parameter settings are shown in Table 1.Table 1
The parameter of simulation scenario.
CategoryParameter (unit)ValuesScenario settingsSimulation time (s)43200Simulation region (m)4500∗3400Group characteristicsGroup movement modelShortest path map-based movementBuffer size (MB)5Wait time (s)0~120Speed (m/s)0.5~1.5msgTtl (m)300Message characteristicsEvents.nrof1Events1.classMessageEventGeneratorEvents1.interval25~35Events1.size (kB)500~1000Events1.hosts0~29


### 5.2. Experimental Results and Analysis

#### 5.2.1. Experimental Results

(1) Average Buffer Time. It is used to represent that the occupancy of the node buffer when the opportunistic network routing strategy forwards message. The average buffer time of nodes=∑i=1destinationnodeτi/messagesreceivedbydestinationnode, and τi represents the total buffer time of message i at each node in opportunistic network. In the experiment, we compared the average buffer time of opportunistic network routing algorithm ONBTM and other three algorithms. The node number is varied from 0 to 180. Figure 1 reports the effects of average buffer time of nodes in different node numbers. The experimental results indicate that ONBTM is a very effective algorithm. Compared with epidemic and prophet algorithms, algorithm proposed by this paper shows a steady downward trend as the nodes number increases.Figure 1
The comparison of buffertime_avg under different routing protocols.(2) Delivery Probability. It indicates the ability that the opportunistic network routing strategy transmits messages to the target node. What is more, the delivery probability can measure the performance of the routing strategy.
(9)deliveryprobability=messagesreceivedbydestinationnodemessagesreceivedbysourcenode.In the experiment, we compared delivery success rate of ONBTM, prophet, epidemic, and spray and wait. From Figure2, we have some observations:
(i)
When the nodes are less than 60, all algorithms have similar delivery probability(ii)
When the node number is greater than 60, ONBTM is significantly better than epidemic and prophet. Our algorithm ONBTM shows a steady upward trend as the node number increases(iii)
Compared with the spray and wait algorithm, ONBTM has a slightly lower delivery probability. But ONBTM has much lower average buffer time than spray and wait. That is, ONBTM achieves a higher delivery success rate than epidemic and prophet with lower resource consumption and a slightly lower delivery success rate than spray and wait.Figure 2
The comparison of delivery_prob under different routing protocols.(3) Average Hop Count. It represents the consumption of resources when messages are transmitted in the network.
(10)averagehopcount=∑i=1destinationnodeSinumberofmessagereceivedbydestinationnode.Si represents the relay nodes that message i passes before reaching the destination node in the opportunistic network.In the experiment, we examined the average hop count of ONBTM, prophet, epidemic, and spray and wait. There are some observations from Figure3:
(i)
In the opportunistic network, the node number ranges from 20 to 180. Compared with the other three algorithms, epidemic has the highest average hop count, because messages are forwarded as long as the nodes meet, which results in high resource consumption, high cost of message forwarding, and message congestion in the network. In terms of average hop counts, the ONBTM and the prophet show similar trend, but the spray and wait is lower than the other three algorithms. As the node number increases, the average hop of epidemic strategy increases fastest. This is because as the nodes number increases, network congestion will increase. The average hop count of ONBTM, prophet, and spray and wait grows slowly as the nodes increases, and when nodes increase to 150, the average hop count tends to be stable(ii)
The ONBTM algorithm has higher average hop than spray and wait. However, the algorithm ONBTM has much lower average buffer time than spray and wait. It indicates that ONBTM obtains a lower average hop count and delivery resource consumption with a smaller resource consumption.Figure 3
The comparison of hopcount_avg under different routing protocols.(4) Average Latency. It represents the time that message from generation to successful delivery. It is used to measure the timeliness of the opportunistic network routing strategy in delivering the message.
(11)averagelatency=∑i=1messagesreceivedbydestinationnodeti−ti0messagesreceivedbydestinationnode.ti0 is the produced time of message i, and ti is the time that message i reaches the destination nodes.In this experiment, we tested the average latency of ONBTM, prophet, epidemic, and spray and wait. Some observations from Figure4 are as follows:
(i)
In the experiment, the nodes ranged from 20 to 180. When the node number is greater than 60, the average latency obtained by ONBTM, prophet and epidemic shows similar trends. As the nodes increase to 60, the average latency of all routing algorithms shows a different degree of decline. The average latency obtained by ONBTM is close to epidemic, both are slightly better than prophet, and spray and wait has the fastest decline rate. It also can be seen that the four routing algorithms have similar average latency when running in a sparse opportunistic network.Figure 4
The comparison of latency_avg under different routing protocols.


#### 5.2.2. Analysis

Firstly, we compared the average buffer time of nodes by using four different routing algorithms. ONBTM, prophet, and epidemic are relatively similar to each other in average buffer time, but spray and wait is much larger than the above three algorithms. With the increase of nodes, our algorithm ONBTM performs well than spray and wait, which shows that our algorithm has a better control over network resource consumption.Secondly, we compared the delivery success rate of messages by using four different routing algorithms. Compared with prophet and epidemic, ONBTM has a large increase in the sparse and dense opportunistic network. Although spray and wait performs slightly better than ONBTM, it occupies more network resources and increases the energy consumption. Algorithm ONBTM has a good balance between network resource consumption and delivery probability.Thirdly, we compared the average hop count of message delivery by using four different routing algorithms. Algorithm epidemic has a higher average hop count for message delivery, especially when the node number is more than 80. As the nodes increase from 20 to 180, ONBTM and prophet get similar average hop. When the nodes exceed 80, the spray and wait obtains smaller average hop; this is because the spray and wait algorithm gets smaller average hop count with more persistent network resources.Finally, we compared the average latency of the four different routing algorithms. As the nodes increase from 20 to 180, the ONBTM, epidemic, prophet, and spray and wait algorithms all show a steady downward trend. However, the prophet and epidemic algorithms consume a higher average latency in the opportunistic network. When the nodes are less than 60, the ONBTM algorithm and the spray and wait algorithm have similar average latency. In the opportunistic network where nodes increase from 60 to 180, the average latency of the spray and wait is lower than ONBTM. The reason is that when the message is delivered using spray and wait, the message takes up more network resources for a longer time.In summary, compared with existing opportunistic network routing algorithms, ONBTM proposed in the paper has a smaller network resource occupation and consumption, smaller delivery latency and average hop count, and higher delivery success rate. What is more, ONBTM algorithm achieves a good balance between message delivery and resource consumption, thus achieving higher quality of message delivery with low resource usage.


## 5.1. Experimental Setting

The experiments were run on a Thinkpad T440p with 2.5GHz Intel Core i5 CPU and 16GB of RAM, and Windows 10 is installed on the machine.By using the famous simulation platform ONE (Opportunistic Networking Environment) [2], we simulated a sparse opportunistic network with pedestrians as nodes. In the network, the node speed is the walking speed, and the node storage size is set to a smaller value. We also simulated the opportunistic network routing algorithm based on node intimacy. Then, the proposed algorithm are compared with several well-known routing algorithms, for example, prophet, epidemic, and spray and wait. For the purpose of making the experimental environment more stable, it is necessary to generate message after simulation platform runs for 1000 seconds. The parameter settings are shown in Table 1.Table 1
The parameter of simulation scenario.
CategoryParameter (unit)ValuesScenario settingsSimulation time (s)43200Simulation region (m)4500∗3400Group characteristicsGroup movement modelShortest path map-based movementBuffer size (MB)5Wait time (s)0~120Speed (m/s)0.5~1.5msgTtl (m)300Message characteristicsEvents.nrof1Events1.classMessageEventGeneratorEvents1.interval25~35Events1.size (kB)500~1000Events1.hosts0~29


## 5.2. Experimental Results and Analysis

### 5.2.1. Experimental Results

(1) Average Buffer Time. It is used to represent that the occupancy of the node buffer when the opportunistic network routing strategy forwards message. The average buffer time of nodes=∑i=1destinationnodeτi/messagesreceivedbydestinationnode, and τi represents the total buffer time of message i at each node in opportunistic network. In the experiment, we compared the average buffer time of opportunistic network routing algorithm ONBTM and other three algorithms. The node number is varied from 0 to 180. Figure 1 reports the effects of average buffer time of nodes in different node numbers. The experimental results indicate that ONBTM is a very effective algorithm. Compared with epidemic and prophet algorithms, algorithm proposed by this paper shows a steady downward trend as the nodes number increases.Figure 1
The comparison of buffertime_avg under different routing protocols.(2) Delivery Probability. It indicates the ability that the opportunistic network routing strategy transmits messages to the target node. What is more, the delivery probability can measure the performance of the routing strategy.
(9)deliveryprobability=messagesreceivedbydestinationnodemessagesreceivedbysourcenode.In the experiment, we compared delivery success rate of ONBTM, prophet, epidemic, and spray and wait. From Figure2, we have some observations:
(i)
When the nodes are less than 60, all algorithms have similar delivery probability(ii)
When the node number is greater than 60, ONBTM is significantly better than epidemic and prophet. Our algorithm ONBTM shows a steady upward trend as the node number increases(iii)
Compared with the spray and wait algorithm, ONBTM has a slightly lower delivery probability. But ONBTM has much lower average buffer time than spray and wait. That is, ONBTM achieves a higher delivery success rate than epidemic and prophet with lower resource consumption and a slightly lower delivery success rate than spray and wait.Figure 2
The comparison of delivery_prob under different routing protocols.(3) Average Hop Count. It represents the consumption of resources when messages are transmitted in the network.
(10)averagehopcount=∑i=1destinationnodeSinumberofmessagereceivedbydestinationnode.Si represents the relay nodes that message i passes before reaching the destination node in the opportunistic network.In the experiment, we examined the average hop count of ONBTM, prophet, epidemic, and spray and wait. There are some observations from Figure3:
(i)
In the opportunistic network, the node number ranges from 20 to 180. Compared with the other three algorithms, epidemic has the highest average hop count, because messages are forwarded as long as the nodes meet, which results in high resource consumption, high cost of message forwarding, and message congestion in the network. In terms of average hop counts, the ONBTM and the prophet show similar trend, but the spray and wait is lower than the other three algorithms. As the node number increases, the average hop of epidemic strategy increases fastest. This is because as the nodes number increases, network congestion will increase. The average hop count of ONBTM, prophet, and spray and wait grows slowly as the nodes increases, and when nodes increase to 150, the average hop count tends to be stable(ii)
The ONBTM algorithm has higher average hop than spray and wait. However, the algorithm ONBTM has much lower average buffer time than spray and wait. It indicates that ONBTM obtains a lower average hop count and delivery resource consumption with a smaller resource consumption.Figure 3
The comparison of hopcount_avg under different routing protocols.(4) Average Latency. It represents the time that message from generation to successful delivery. It is used to measure the timeliness of the opportunistic network routing strategy in delivering the message.
(11)averagelatency=∑i=1messagesreceivedbydestinationnodeti−ti0messagesreceivedbydestinationnode.ti0 is the produced time of message i, and ti is the time that message i reaches the destination nodes.In this experiment, we tested the average latency of ONBTM, prophet, epidemic, and spray and wait. Some observations from Figure4 are as follows:
(i)
In the experiment, the nodes ranged from 20 to 180. When the node number is greater than 60, the average latency obtained by ONBTM, prophet and epidemic shows similar trends. As the nodes increase to 60, the average latency of all routing algorithms shows a different degree of decline. The average latency obtained by ONBTM is close to epidemic, both are slightly better than prophet, and spray and wait has the fastest decline rate. It also can be seen that the four routing algorithms have similar average latency when running in a sparse opportunistic network.Figure 4
The comparison of latency_avg under different routing protocols.


### 5.2.2. Analysis

Firstly, we compared the average buffer time of nodes by using four different routing algorithms. ONBTM, prophet, and epidemic are relatively similar to each other in average buffer time, but spray and wait is much larger than the above three algorithms. With the increase of nodes, our algorithm ONBTM performs well than spray and wait, which shows that our algorithm has a better control over network resource consumption.Secondly, we compared the delivery success rate of messages by using four different routing algorithms. Compared with prophet and epidemic, ONBTM has a large increase in the sparse and dense opportunistic network. Although spray and wait performs slightly better than ONBTM, it occupies more network resources and increases the energy consumption. Algorithm ONBTM has a good balance between network resource consumption and delivery probability.Thirdly, we compared the average hop count of message delivery by using four different routing algorithms. Algorithm epidemic has a higher average hop count for message delivery, especially when the node number is more than 80. As the nodes increase from 20 to 180, ONBTM and prophet get similar average hop. When the nodes exceed 80, the spray and wait obtains smaller average hop; this is because the spray and wait algorithm gets smaller average hop count with more persistent network resources.Finally, we compared the average latency of the four different routing algorithms. As the nodes increase from 20 to 180, the ONBTM, epidemic, prophet, and spray and wait algorithms all show a steady downward trend. However, the prophet and epidemic algorithms consume a higher average latency in the opportunistic network. When the nodes are less than 60, the ONBTM algorithm and the spray and wait algorithm have similar average latency. In the opportunistic network where nodes increase from 60 to 180, the average latency of the spray and wait is lower than ONBTM. The reason is that when the message is delivered using spray and wait, the message takes up more network resources for a longer time.In summary, compared with existing opportunistic network routing algorithms, ONBTM proposed in the paper has a smaller network resource occupation and consumption, smaller delivery latency and average hop count, and higher delivery success rate. What is more, ONBTM algorithm achieves a good balance between message delivery and resource consumption, thus achieving higher quality of message delivery with low resource usage.


## 5.2.1. Experimental Results

(1) Average Buffer Time. It is used to represent that the occupancy of the node buffer when the opportunistic network routing strategy forwards message. The average buffer time of nodes=∑i=1destinationnodeτi/messagesreceivedbydestinationnode, and τi represents the total buffer time of message i at each node in opportunistic network. In the experiment, we compared the average buffer time of opportunistic network routing algorithm ONBTM and other three algorithms. The node number is varied from 0 to 180. Figure 1 reports the effects of average buffer time of nodes in different node numbers. The experimental results indicate that ONBTM is a very effective algorithm. Compared with epidemic and prophet algorithms, algorithm proposed by this paper shows a steady downward trend as the nodes number increases.Figure 1
The comparison of buffertime_avg under different routing protocols.(2) Delivery Probability. It indicates the ability that the opportunistic network routing strategy transmits messages to the target node. What is more, the delivery probability can measure the performance of the routing strategy.
(9)deliveryprobability=messagesreceivedbydestinationnodemessagesreceivedbysourcenode.In the experiment, we compared delivery success rate of ONBTM, prophet, epidemic, and spray and wait. From Figure2, we have some observations:
(i)
When the nodes are less than 60, all algorithms have similar delivery probability(ii)
When the node number is greater than 60, ONBTM is significantly better than epidemic and prophet. Our algorithm ONBTM shows a steady upward trend as the node number increases(iii)
Compared with the spray and wait algorithm, ONBTM has a slightly lower delivery probability. But ONBTM has much lower average buffer time than spray and wait. That is, ONBTM achieves a higher delivery success rate than epidemic and prophet with lower resource consumption and a slightly lower delivery success rate than spray and wait.Figure 2
The comparison of delivery_prob under different routing protocols.(3) Average Hop Count. It represents the consumption of resources when messages are transmitted in the network.
(10)averagehopcount=∑i=1destinationnodeSinumberofmessagereceivedbydestinationnode.Si represents the relay nodes that message i passes before reaching the destination node in the opportunistic network.In the experiment, we examined the average hop count of ONBTM, prophet, epidemic, and spray and wait. There are some observations from Figure3:
(i)
In the opportunistic network, the node number ranges from 20 to 180. Compared with the other three algorithms, epidemic has the highest average hop count, because messages are forwarded as long as the nodes meet, which results in high resource consumption, high cost of message forwarding, and message congestion in the network. In terms of average hop counts, the ONBTM and the prophet show similar trend, but the spray and wait is lower than the other three algorithms. As the node number increases, the average hop of epidemic strategy increases fastest. This is because as the nodes number increases, network congestion will increase. The average hop count of ONBTM, prophet, and spray and wait grows slowly as the nodes increases, and when nodes increase to 150, the average hop count tends to be stable(ii)
The ONBTM algorithm has higher average hop than spray and wait. However, the algorithm ONBTM has much lower average buffer time than spray and wait. It indicates that ONBTM obtains a lower average hop count and delivery resource consumption with a smaller resource consumption.Figure 3
The comparison of hopcount_avg under different routing protocols.(4) Average Latency. It represents the time that message from generation to successful delivery. It is used to measure the timeliness of the opportunistic network routing strategy in delivering the message.
(11)averagelatency=∑i=1messagesreceivedbydestinationnodeti−ti0messagesreceivedbydestinationnode.ti0 is the produced time of message i, and ti is the time that message i reaches the destination nodes.In this experiment, we tested the average latency of ONBTM, prophet, epidemic, and spray and wait. Some observations from Figure4 are as follows:
(i)
In the experiment, the nodes ranged from 20 to 180. When the node number is greater than 60, the average latency obtained by ONBTM, prophet and epidemic shows similar trends. As the nodes increase to 60, the average latency of all routing algorithms shows a different degree of decline. The average latency obtained by ONBTM is close to epidemic, both are slightly better than prophet, and spray and wait has the fastest decline rate. It also can be seen that the four routing algorithms have similar average latency when running in a sparse opportunistic network.Figure 4
The comparison of latency_avg under different routing protocols.


## 5.2.2. Analysis

Firstly, we compared the average buffer time of nodes by using four different routing algorithms. ONBTM, prophet, and epidemic are relatively similar to each other in average buffer time, but spray and wait is much larger than the above three algorithms. With the increase of nodes, our algorithm ONBTM performs well than spray and wait, which shows that our algorithm has a better control over network resource consumption.Secondly, we compared the delivery success rate of messages by using four different routing algorithms. Compared with prophet and epidemic, ONBTM has a large increase in the sparse and dense opportunistic network. Although spray and wait performs slightly better than ONBTM, it occupies more network resources and increases the energy consumption. Algorithm ONBTM has a good balance between network resource consumption and delivery probability.Thirdly, we compared the average hop count of message delivery by using four different routing algorithms. Algorithm epidemic has a higher average hop count for message delivery, especially when the node number is more than 80. As the nodes increase from 20 to 180, ONBTM and prophet get similar average hop. When the nodes exceed 80, the spray and wait obtains smaller average hop; this is because the spray and wait algorithm gets smaller average hop count with more persistent network resources.Finally, we compared the average latency of the four different routing algorithms. As the nodes increase from 20 to 180, the ONBTM, epidemic, prophet, and spray and wait algorithms all show a steady downward trend. However, the prophet and epidemic algorithms consume a higher average latency in the opportunistic network. When the nodes are less than 60, the ONBTM algorithm and the spray and wait algorithm have similar average latency. In the opportunistic network where nodes increase from 60 to 180, the average latency of the spray and wait is lower than ONBTM. The reason is that when the message is delivered using spray and wait, the message takes up more network resources for a longer time.In summary, compared with existing opportunistic network routing algorithms, ONBTM proposed in the paper has a smaller network resource occupation and consumption, smaller delivery latency and average hop count, and higher delivery success rate. What is more, ONBTM algorithm achieves a good balance between message delivery and resource consumption, thus achieving higher quality of message delivery with low resource usage.


## 6. Conclusion

The paper defined some concepts related to node intimacy and proposed the ONBTM algorithm. Unlike the existing opportunistic network routing algorithms, ONBTM has strong adaptability and stability, especially suitable for sparse opportunistic networks. Experimental results show that ONBTM and optimization technique proposed in the paper are effective and efficient. To lay foundations for node intimacy, we study the ONBTM in the sparse opportunistic network. Through comparing four different routing algorithms with different numbers of nodes, we find that the ONBTM algorithm is more effective and efficient.



---

*Source: 6666211-2021-03-03.xml*