# A Data Dissemination Method Based on Region Type Correlations for Mobile Opportunistic Networks

Authors: Linfeng Liu; Daoliang Chen
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

In Mobile Opportunistic Networks (MONs), due to the node movements and the uncontrollable on/off switches of the carried communication devices, the contacts between nodes may be scarce and momentary, and thus a data packet should be transferred through some discrete hops. To avoid the costly flooding of data packets, the data packets are typically disseminated to some relay nodes selected by data holders. However, the mobility patterns of nodes will become different in different types of regions (such as residential regions, commercial regions, scenery regions, or industrial regions); i.e., the movement directions and movement ranges of nodes are frequently varied when the nodes move among various regions. At present, the issues regarding the region types and region type correlations have not been investigated for the data dissemination in existing works. To this end, we propose a Region Type based Data Dissemination Method (RTDDM) for MONs, which exploits the region type correlations and selects the proper relay nodes through a Markov decision model. To verify the performance of RTDDM, we give some theoretical analysis as well as an elaborated simulation study, the results of which show that RTDDM can improve the delivery ratio and reduce the delivery delay, especially in the applications with various region types.


---

## Body

## 1. Introduction

Mobile Opportunistic Network (MON) [1, 2] is one of the emerging communication paradigms in wireless mobile communications. An MON is defined as a mobile network where the communications between nodes are challenged by sporadic and intermittent contacts, as well as the frequent disconnections and reconnections, and thus a stable communication path from the source to the destination usually cannot be obtained. The MON applications are diverse, such as the vehicle networks for traffic information sharing, the mobile sensor networks for wildlife tracking, and the pocket switched networks comprised of human-carried mobile devices.In most traditional routing methods, the end-to-end paths must be established, and then the data packets are disseminated along these paths. Therefore, the global connectivity of network topology should be satisfied, such that at least a stable end-to-end communication path can be found from the network topology. However, the MON nodes always move frequently, and the communication devices carried by nodes are switched between on/off statuses unpredictably. These characteristics of MONs make the end-to-end paths extremely difficult to be established, and hence the traditional routing methods cannot be applied to MONs. In MONs, the node contacts must be exploited for the data dissemination; i.e., the data packets are disseminated from thedataholders (the nodes carrying data packets) to the encountered ordinarynodes (the nodes not carrying data packets) and finally are transferred to the destination node through discrete hops.Therefore, the held data packets are allowed to be disseminated to some relay nodes by the data holders. Due to the unpredictability in future movements of nodes, the data dissemination method (especially how to select the proper relay nodes) becomes a vital issue for the improvement of delivery ratio and the reduction of delivery delay.The node contacts are concerned with the region types. In many MON applications, the nodes are likely to appear in some regions with special types more frequently or stay in these regions for a longer period. For example, the tourists visit some scenery regions more frequently, and the residents are more likely to stay in some residential regions, as shown in Figure1. These features can help improve the data dissemination in MONs; i.e., the future contacts between nodes can be predicted according to the region types, and the proper relay nodes can be selected to make the data packets be delivered to the destination nodes as soon as possible. At present, the issues regarding the region types and the region type correlations have not been paid enough attention for the data dissemination of MONs. Note that the mobility patterns of nodes will be different in the different types of regions, and the movement directions and movement ranges of nodes are frequently varied when the nodes move among various regions. Thus, the data dissemination can be improved through differentiating the region types and investigating the region type correlations.Figure 1
Example regions of different types.Our research is also inspired by the following observations: (a) the movements of communication devices in MONs are controlled by their carriers (human beings), and the mobility of human beings is driven by their habits which are typically stable in long terms. Therefore, the movement directions and movement ranges in different types of regions (such as residential regions, commercial regions, scenery regions, or industrial regions) are quite different; (b) the randomness in node mobility makes the data dissemination problem be mapped into a sequential decision problem mathematically. Besides, the Markov decision method is a preferable decision method and is suitable for the sequence decision problem [3, 4].This work is an extension of our previous conference paper [5]. In this paper, we improve the Region Type based Data Dissemination Method (RTDDM), especially in terms of the action determinations and message interactions, and some theoretical analysis is conducted for RTDDM. Besides, more simulation results are also provided to further clarify the merits of RTDDM. The remainder of this paper is organized as follows. Section 2 discusses related studies. Section 3 describes the network model. Section 4 presents our algorithm. Section 5 provides some theoretical analysis regarding RTDDM. The simulation study is reported in Section 6. This paper is concluded by Section 7.


## 2. Related Work

Recently, some relevant research has been conducted on the data dissemination in MONs. Mcgeehanet al. propose a message routing approach ChitChat [6], which exploits users' direct and transient social interests via discriminatory gossiping to penetrate messages deeper into the network. ChitChat enables message carriers to make opportunistic and distributed routing decisions based on the likelihood of forwarding the messages to the destination. In [7], a geographic-based spray-and-relay (GSaR) routing scheme is proposed. By estimating the movement range of the destination via the historical geographic information, GSaR expedites the message being sprayed toward this range and postpones that out of this range. Reference [8] gives two sociality based routings, named as the contact based routing and community aware two-hop routing, respectively. These routings are designed based on the graph properties (such as the average path length and modularity) and the node encounter process. Caiet al. construct a cross-layer distributed opportunistic routing protocol [9], which considers the channel sensing strategy, the forwarder selection for each secondary user, and the package division scheme on each link.To overcome the communication problems of changing topology and missing infrastructure, [10] presents a lightweight and scalable routing protocol that exploits the limited social circle of each node. In [11], the Community-Based Forwarding (CBF) considering the community interactions is developed. CBF is able to explore the intermediate connections between clusters to route the messages with more balanced node participation and higher levels of reliability. To improve the dissemination efficiency, [12] presents a routing algorithm called Popular Node Gateway Protocol (PNGP). PNGP is validated through simulations, the results of which indicate that it performs satisfactorily in terms of delivery ratio, delivery delay, and transmission cost. In [13], an analytical model of message dissemination by applying the concept of mean free path is proposed, and each node contact is represented as a collision between two particles. In order to relieve the congestion without affecting the delivery delay, Ciobanuet al. present an interest-based dissemination algorithm where nodes tend to group together based on interests [14]. Reference [15] proposes a stochastic approach for modeling the message dissemination in opportunistic networks to choose the appropriate relay nodes according to the features of the application scenario.In this paper, the issues of region type correlations and region weights are specially exploited and formulated, and then a Markov decision model is applied to determine the relay nodes of data holders. Thus, the data packets could be continuously propagated to the proper relay nodes to improve the delivery ratio and reduce the delivery delay.


## 3. Network Model

The time is divided into discrete time slots with an equal lengthτs. Each data packet needs to be disseminated from the source node to the destination region during t∗ time slots.


### 3.1. Nodes

Suppose there areN mobile nodes in the network, denoted by 1,2,…,i,…,N, and each node is with the same communication range rc. The coordinate of node i at the t-th time slot is denoted by C(i)(t). The distance between node i and node j at the t-th time slot is marked as d(i,j)(t). If d(i,j)(t)≤rc, then i and j are neighbors.


### 3.2. Regions

The network areaΩ is divided into K regions R1,R2,…,Rk,…,RK. Each region Rk is denoted by a triple (xk,yk,Tk), where (xk,yk) is the center coordinate of Rk, and Tk denotes the region type of Rk. Suppose there are M different region types, such as residential regions, business regions, industrial regions, and educational regions. The distance between two regions Rk and Rk′ is calculated as(1)Rk-Rk′=xk-xk′2+yk-yk′2.The human mobility in MONs is analyzed by a real-world dataset (Dartmouth Colleges wireless local area network (WLAN) trajectories [16]) which are recorded as the connections or disconnections of nodes with some access points (APs). Figure 2 illustrates that the nodes usually visit a few APs frequently, and note that the average probability of visiting these APs is even larger than 0.7. The results inspire us to put forward the notionhome regions for nodes; i.e., the nodes will appear in the home regions with very large probabilities. The home regions of node i are marked as a region set H(i), where the probability of i appearing in each region belonging to the set H(i) is larger than a preset threshold ph.Figure 2
Average probabilities of visiting APs. The movement trajectories during the periods 09/21/2003-10/20/2003, 10/21/2003-11/19/2003, 01/28/2004-02/26/2004, and 04/20/2004-05/19/2004 are analyzed. Ten most frequently visited APs are selected and sorted for each node, and then the probabilities of nodes visiting these APs are averaged and given in this figure.Besides, the distance betweenH(i) and H(j) is denoted by Dij, and Dij is computed as the minimum distance between H(i) and H(j),(2)Dij=Hi-Hj=minRk-Rk′,∀Rk∈Hi,Rk′∈Hj


### 3.3. Region Type Correlation and Region Weight

The nodes are prone to appear in the correlated regions. The correlation of different region types is calculated based on the movement trajectories of nodes. With regard to each regionRk, the correlation between Rk and Rk′ is computed as(3)CorRk,Rk′=1,ifTk=Tk′,∑1≤i≤NBi,Rk,Rk′N,otherwise,where B(i,Rk,Rk′) is set as 1 if there are at least two regions belonging to H(i) simultaneously; otherwise, B(i,Rk,Rk′) is set as 0.The region weight ofRk is denoted by Wk, where Wk∈[0,1]. The value of Wk indicates the possibility of data packets being disseminated from Rk to the destination region Rd. Wk is expressed as(4)Wk=CorRk,Rdα·Rk-Rdmax1≤k′≤K⁡Rk′-Rdγ,where α and γ are preset exponents. The value of α and γ reflects the influences of region type and region distance on the region weight, respectively.At thet-th time slot, the weight of j receiving and storing the data packets is expressed as(5)wtj=∑∀Rk∈HjPj,Rk·Wk∑∀Rk∈HjPj,Rk.


## 3.1. Nodes

Suppose there areN mobile nodes in the network, denoted by 1,2,…,i,…,N, and each node is with the same communication range rc. The coordinate of node i at the t-th time slot is denoted by C(i)(t). The distance between node i and node j at the t-th time slot is marked as d(i,j)(t). If d(i,j)(t)≤rc, then i and j are neighbors.


## 3.2. Regions

The network areaΩ is divided into K regions R1,R2,…,Rk,…,RK. Each region Rk is denoted by a triple (xk,yk,Tk), where (xk,yk) is the center coordinate of Rk, and Tk denotes the region type of Rk. Suppose there are M different region types, such as residential regions, business regions, industrial regions, and educational regions. The distance between two regions Rk and Rk′ is calculated as(1)Rk-Rk′=xk-xk′2+yk-yk′2.The human mobility in MONs is analyzed by a real-world dataset (Dartmouth Colleges wireless local area network (WLAN) trajectories [16]) which are recorded as the connections or disconnections of nodes with some access points (APs). Figure 2 illustrates that the nodes usually visit a few APs frequently, and note that the average probability of visiting these APs is even larger than 0.7. The results inspire us to put forward the notionhome regions for nodes; i.e., the nodes will appear in the home regions with very large probabilities. The home regions of node i are marked as a region set H(i), where the probability of i appearing in each region belonging to the set H(i) is larger than a preset threshold ph.Figure 2
Average probabilities of visiting APs. The movement trajectories during the periods 09/21/2003-10/20/2003, 10/21/2003-11/19/2003, 01/28/2004-02/26/2004, and 04/20/2004-05/19/2004 are analyzed. Ten most frequently visited APs are selected and sorted for each node, and then the probabilities of nodes visiting these APs are averaged and given in this figure.Besides, the distance betweenH(i) and H(j) is denoted by Dij, and Dij is computed as the minimum distance between H(i) and H(j),(2)Dij=Hi-Hj=minRk-Rk′,∀Rk∈Hi,Rk′∈Hj


## 3.3. Region Type Correlation and Region Weight

The nodes are prone to appear in the correlated regions. The correlation of different region types is calculated based on the movement trajectories of nodes. With regard to each regionRk, the correlation between Rk and Rk′ is computed as(3)CorRk,Rk′=1,ifTk=Tk′,∑1≤i≤NBi,Rk,Rk′N,otherwise,where B(i,Rk,Rk′) is set as 1 if there are at least two regions belonging to H(i) simultaneously; otherwise, B(i,Rk,Rk′) is set as 0.The region weight ofRk is denoted by Wk, where Wk∈[0,1]. The value of Wk indicates the possibility of data packets being disseminated from Rk to the destination region Rd. Wk is expressed as(4)Wk=CorRk,Rdα·Rk-Rdmax1≤k′≤K⁡Rk′-Rdγ,where α and γ are preset exponents. The value of α and γ reflects the influences of region type and region distance on the region weight, respectively.At thet-th time slot, the weight of j receiving and storing the data packets is expressed as(5)wtj=∑∀Rk∈HjPj,Rk·Wk∑∀Rk∈HjPj,Rk.


## 4. Data Dissemination Method

In this section, we propose a Region Type based Data Dissemination Method (RTDDM) for MONs. In particular, in RTDDM, the Markov decision model is used to determine the relay nodes whose home regions are with larger region weights.


### 4.1. Dissemination Process Based on Markov Decision

The dissemination process based on Markov decision is described as follows:(1) Decision stages:T={1,…,F}, which indicates that the node encounters F neighbors during a time slot.(2) State set:S={0,1,△} is a finite set of states, where “1” indicates that the current encountered node is the best relay node and “0” indicates that the current encountered node is not the best relay node. △ indicates the termination of dissemination at current time slot; i.e., the data holder has already encountered F nodes or the data packets have been disseminated to the encountered nodes.(3) Action set: the action setA(s) is defined as(6)As=R,E,ifs∈0,1,R,ifs=△,where s denotes the current state. E is the action of the current encountered node storing the data packets, and R is the action of the current encountered node rejecting the data packets.(4) Reward function: when the number of nodes is large enough, the nodes are considered to be evenly distributed approximatively. At thet-th time slot, the obtained reward is expressed as(7)rmts,a=0,ifs∈0,1anda=R,wth·mF,ifs∈0,1,a=Eandm<F,0,ifs=△,where m/F is the probability of the best relay node falling into the set of the first m encountered nodes and h denotes the m-th encountered node.(5) Transition probability: the transition probability is denoted byPmt(s′∣s,a), where s′ and s denote the future state and the current state, respectively. The expression of Pmt(s′∣s,a) is written as(8)Pmts′∣s,a=1m+1,ifs∈0,1,a=Rands′=1,mm+1,ifs∈0,1,a=Rands′=0,1,ifs∈0,1,a=Eands′=△,0,otherwise.According to (8), the transition probability is equal to 1/m+1 when the (m+1)-th encountered node is by far the best relay node.Then, we give the solution process for the above problem. At thet-th time slot, the maximum probability of the best relay node having been selected during the period from the current decision stage to the end stage is denoted by um(t)(1); i.e., the m-th encountered node is the best one in the previous encountered nodes. Likewise, from the next decision stage to the end stage, the maximum probability of selecting the best relay node is denoted by um(t)(0); i.e., the m-th encountered node is not the best one in the previous encountered nodes. uF(t)(1) and uF(t)(0) should satisfy the following equations:(9)uFt1=1,uFt0=0,uFt△=0.Form=1,2,…,F-1, um(t)(1) and um(t)(0) can be written as(10)umt1=maxrmt1,E+um+1t△,rm+1t1,E·Pmt1∣1,R·um+1t1+Pmt0∣1,R·um+1t0=maxrmt1,E,rm+1t1,E·um+1t1m+1+m·um+1t0m+1,(11)umt0=maxrmt0,E+um+1t△,rm+1t0,E·Pmt1∣0,R·um+1t1+Pmt0∣0,R·um+1t0=maxrmt0,E,rm+1t0,E·um+1t1m+1+m·um+1t0m+1.In particular, there isum(t)(△)=0. Thus, the optimal actions can be obtained by solving (10) and (11).


### 4.2. RTDDM

In RTDDM, to restrict the dissemination cost, the maximum number of disseminated copies at each time slot is set asNd (Nd≤F). At each time slot, the relay nodes will be selected through a Markov decision model as described in Section 4.1. In particular, in RTDDM each data holder makes the decision about whether to disseminate the held data packets to the neighbors through several decision stages. In each decision stage, each data holder disseminates the held data packets to at most Nd neighbors, a part of which will become the relay nodes. Thus, the decision stages will be repeated until Nd relay nodes have been selected or all the neighbors have received the data packets. The detailed description of RTDDM is given as follows.Step 1.
According to the previous trajectories of nodes, each node determines its home regions. The region type correlations and the region weights are calculated.Step 2.
At each time slot (suppose thet-th time slot), each node i broadcasts an inquire message inquire_msg, as shown in Figure 3, where data_list(i) denotes the list of held data packets by i at the current time slot.Figure 3
Message structures.Step 3.
After the reception ofinquire_msg (as shown in Figure 3) from i, each neighboring node j responds with a reply_msg. If the destination node has received an inquire_msg from i, it will send the data packets to destination node immediately; otherwise, Step 4 is carried out.Step 4.
Each data holder disseminates the held data packetsdata_msgs to Nd nearest nodes. With regard to the receivers of the data packets, if the current state of the m-th neighbor (denoted by s) is equal to 1, and there is w(t)(h)·m/F≥um(t)(0), then the action E will be taken; otherwise, if s is equal to 0 or there is w(t)(h)·m/F<um(t)(0), then the action R will be taken. As mentioned above, the action a(s) is determined by the following expression:(12)as=E,ifs=1andwth·mF≥umt0R,ifs=0orwth·mF<umt0.Step 5.
Ifk neighbors have chosen the action E at the last decision stage, then m and Nd should be updated as(13)m←m+Nd,Nd←Nd-k.
After that, ifm and Nd satisfy that m<F and Nd>0, Steps 4 and 5 will be repeated; if F and Nd satisfy that m=F or Nd=0, the dissemination process at the current time slot is terminated.Step 6.
The above steps will be repeated until the data packets have been disseminated to the destination region, or the period oft∗ time slots has been expired. If the data packets have been delivered to destination region before the deadline (t∗ time slots), an announcement message will be propagated to all data holders to stop the further dissemination. The size of announcement message is very small and can be piggybacked with other messages.The pseudocode of RTDDM is depicted in Algorithm1.Algorithm 1:RTDDM pseudo-code.
1:t←1. 2:while  t≤t∗, and data packets have not been delivered  do 3:for  each node 1≤i≤N  do 4:i broadcasts an inquire_msg. 5:Each receiver responds a reply_msg. 6:end for 7:Neighbor sets of nodes are updated. 8:for  each data holder i  do 9:while  m<F and Nd>0  do 10:i disseminates the held data packets to Nd neighbors; 11:for  each neighbor having received the data packets  do 12:a(s) is calculated; 13:The received data packets are stored or rejected according to a(s); 14:end for 15:k (k≤Nd) neighbors become the relay nodes. 16:m←m+Nd, Nd←Nd-k. 17:end while 18:end for 19:t←t+1. 20:end while


## 4.1. Dissemination Process Based on Markov Decision

The dissemination process based on Markov decision is described as follows:(1) Decision stages:T={1,…,F}, which indicates that the node encounters F neighbors during a time slot.(2) State set:S={0,1,△} is a finite set of states, where “1” indicates that the current encountered node is the best relay node and “0” indicates that the current encountered node is not the best relay node. △ indicates the termination of dissemination at current time slot; i.e., the data holder has already encountered F nodes or the data packets have been disseminated to the encountered nodes.(3) Action set: the action setA(s) is defined as(6)As=R,E,ifs∈0,1,R,ifs=△,where s denotes the current state. E is the action of the current encountered node storing the data packets, and R is the action of the current encountered node rejecting the data packets.(4) Reward function: when the number of nodes is large enough, the nodes are considered to be evenly distributed approximatively. At thet-th time slot, the obtained reward is expressed as(7)rmts,a=0,ifs∈0,1anda=R,wth·mF,ifs∈0,1,a=Eandm<F,0,ifs=△,where m/F is the probability of the best relay node falling into the set of the first m encountered nodes and h denotes the m-th encountered node.(5) Transition probability: the transition probability is denoted byPmt(s′∣s,a), where s′ and s denote the future state and the current state, respectively. The expression of Pmt(s′∣s,a) is written as(8)Pmts′∣s,a=1m+1,ifs∈0,1,a=Rands′=1,mm+1,ifs∈0,1,a=Rands′=0,1,ifs∈0,1,a=Eands′=△,0,otherwise.According to (8), the transition probability is equal to 1/m+1 when the (m+1)-th encountered node is by far the best relay node.Then, we give the solution process for the above problem. At thet-th time slot, the maximum probability of the best relay node having been selected during the period from the current decision stage to the end stage is denoted by um(t)(1); i.e., the m-th encountered node is the best one in the previous encountered nodes. Likewise, from the next decision stage to the end stage, the maximum probability of selecting the best relay node is denoted by um(t)(0); i.e., the m-th encountered node is not the best one in the previous encountered nodes. uF(t)(1) and uF(t)(0) should satisfy the following equations:(9)uFt1=1,uFt0=0,uFt△=0.Form=1,2,…,F-1, um(t)(1) and um(t)(0) can be written as(10)umt1=maxrmt1,E+um+1t△,rm+1t1,E·Pmt1∣1,R·um+1t1+Pmt0∣1,R·um+1t0=maxrmt1,E,rm+1t1,E·um+1t1m+1+m·um+1t0m+1,(11)umt0=maxrmt0,E+um+1t△,rm+1t0,E·Pmt1∣0,R·um+1t1+Pmt0∣0,R·um+1t0=maxrmt0,E,rm+1t0,E·um+1t1m+1+m·um+1t0m+1.In particular, there isum(t)(△)=0. Thus, the optimal actions can be obtained by solving (10) and (11).


## 4.2. RTDDM

In RTDDM, to restrict the dissemination cost, the maximum number of disseminated copies at each time slot is set asNd (Nd≤F). At each time slot, the relay nodes will be selected through a Markov decision model as described in Section 4.1. In particular, in RTDDM each data holder makes the decision about whether to disseminate the held data packets to the neighbors through several decision stages. In each decision stage, each data holder disseminates the held data packets to at most Nd neighbors, a part of which will become the relay nodes. Thus, the decision stages will be repeated until Nd relay nodes have been selected or all the neighbors have received the data packets. The detailed description of RTDDM is given as follows.Step 1.
According to the previous trajectories of nodes, each node determines its home regions. The region type correlations and the region weights are calculated.Step 2.
At each time slot (suppose thet-th time slot), each node i broadcasts an inquire message inquire_msg, as shown in Figure 3, where data_list(i) denotes the list of held data packets by i at the current time slot.Figure 3
Message structures.Step 3.
After the reception ofinquire_msg (as shown in Figure 3) from i, each neighboring node j responds with a reply_msg. If the destination node has received an inquire_msg from i, it will send the data packets to destination node immediately; otherwise, Step 4 is carried out.Step 4.
Each data holder disseminates the held data packetsdata_msgs to Nd nearest nodes. With regard to the receivers of the data packets, if the current state of the m-th neighbor (denoted by s) is equal to 1, and there is w(t)(h)·m/F≥um(t)(0), then the action E will be taken; otherwise, if s is equal to 0 or there is w(t)(h)·m/F<um(t)(0), then the action R will be taken. As mentioned above, the action a(s) is determined by the following expression:(12)as=E,ifs=1andwth·mF≥umt0R,ifs=0orwth·mF<umt0.Step 5.
Ifk neighbors have chosen the action E at the last decision stage, then m and Nd should be updated as(13)m←m+Nd,Nd←Nd-k.
After that, ifm and Nd satisfy that m<F and Nd>0, Steps 4 and 5 will be repeated; if F and Nd satisfy that m=F or Nd=0, the dissemination process at the current time slot is terminated.Step 6.
The above steps will be repeated until the data packets have been disseminated to the destination region, or the period oft∗ time slots has been expired. If the data packets have been delivered to destination region before the deadline (t∗ time slots), an announcement message will be propagated to all data holders to stop the further dissemination. The size of announcement message is very small and can be piggybacked with other messages.The pseudocode of RTDDM is depicted in Algorithm1.Algorithm 1:RTDDM pseudo-code.
1:t←1. 2:while  t≤t∗, and data packets have not been delivered  do 3:for  each node 1≤i≤N  do 4:i broadcasts an inquire_msg. 5:Each receiver responds a reply_msg. 6:end for 7:Neighbor sets of nodes are updated. 8:for  each data holder i  do 9:while  m<F and Nd>0  do 10:i disseminates the held data packets to Nd neighbors; 11:for  each neighbor having received the data packets  do 12:a(s) is calculated; 13:The received data packets are stored or rejected according to a(s); 14:end for 15:k (k≤Nd) neighbors become the relay nodes. 16:m←m+Nd, Nd←Nd-k. 17:end while 18:end for 19:t←t+1. 20:end while


## 5. Theoretical Analysis

In this section, we give a theoretical analysis for RTDDM.


### 5.1. RTDDM Complexity

In Step2, each node broadcasts an inquire_msg; therefore the total message amount will reach N. In Step 3, there will be N2·π·rc2/Ω  reply_msgs to be transmitted. Steps 4 and 5 make each data holder disseminate at least Nd copies of data packets, and thus the number of transmitted messages is O(N). As a result, the total number of transmitted messages of RTDDM is at most O(N2).


### 5.2. Expected Delivery Ratio and Expected Delivery Delay

With regard to each data packet, the total number of copies duringt∗ time slots is expressed as (Nd+1)t∗. Similar to [17], we apply the continuous-time Markov model to analyze RTDDM, as shown in Figure 4, where Q=(Nd+1)t∗. The state n indicates that there are n data holders in network, and the state O indicates that the data packets have been delivered to the destination region. p(n∣n-1) denotes the probability of the transition from state n-1 to state n.Figure 4
Continuous-time Markov model.When there aren data holders, the probability of the data packet being disseminated to the neighbors is expressed as (N-n)·Nd/N·F. The average contact rate between nodes is marked as β which can be computed from the historical trajectories. Hence, p(O∣n) is expressed as β·∑i=1nw(t)(i)/N, and p(n∣n-1) is expressed as(14)pn∣n-1=n·N-n·NdN·F·β,if1≤n<Q,0,ifn=Q.LetFn(t) and Fo(t) be the probability distribution of delivery delay of the state n and the state O, respectively. According to Kolmogorov equation [18], we obtain the first-order derivative of Fn(t) as(15)Fn′t=-pn∣n-1+pO∣n·Fnt,ifn=1,-pn∣n-1+pO∣n·Fnt+pn-1∣n-2·Fn-1t,if2≤n≤Q-1,-pO∣n·Fnt+pn-1∣n-2·Fn-1t,ifn=Q,∑q=1QpO∣q·Fqt,ifn=O.Because there areF1(0)=1 and Fn(0)=Fo(0)=0, we can further obtain the probability density function of delivery delay through Laplace transform and inverse Laplace transformation:(16)fot=∑n=1QpQ∣n⨂q=1npq-1∣q-2·e-pq∣q-1-pO∣q·t,where ⨂ denotes the convolution operation. Therefore, the expected delivery delay is expressed as(17)EDl=∫0∞t·fotdt,and the expected delivery ratio is expressed as(18)ERt=∫0t∗fotdt.The theoretical delivery delay and theoretical delivery ratio are calculated from (17) and (18) to compare against the simulation results of RTDDM in the next section.


## 5.1. RTDDM Complexity

In Step2, each node broadcasts an inquire_msg; therefore the total message amount will reach N. In Step 3, there will be N2·π·rc2/Ω  reply_msgs to be transmitted. Steps 4 and 5 make each data holder disseminate at least Nd copies of data packets, and thus the number of transmitted messages is O(N). As a result, the total number of transmitted messages of RTDDM is at most O(N2).


## 5.2. Expected Delivery Ratio and Expected Delivery Delay

With regard to each data packet, the total number of copies duringt∗ time slots is expressed as (Nd+1)t∗. Similar to [17], we apply the continuous-time Markov model to analyze RTDDM, as shown in Figure 4, where Q=(Nd+1)t∗. The state n indicates that there are n data holders in network, and the state O indicates that the data packets have been delivered to the destination region. p(n∣n-1) denotes the probability of the transition from state n-1 to state n.Figure 4
Continuous-time Markov model.When there aren data holders, the probability of the data packet being disseminated to the neighbors is expressed as (N-n)·Nd/N·F. The average contact rate between nodes is marked as β which can be computed from the historical trajectories. Hence, p(O∣n) is expressed as β·∑i=1nw(t)(i)/N, and p(n∣n-1) is expressed as(14)pn∣n-1=n·N-n·NdN·F·β,if1≤n<Q,0,ifn=Q.LetFn(t) and Fo(t) be the probability distribution of delivery delay of the state n and the state O, respectively. According to Kolmogorov equation [18], we obtain the first-order derivative of Fn(t) as(15)Fn′t=-pn∣n-1+pO∣n·Fnt,ifn=1,-pn∣n-1+pO∣n·Fnt+pn-1∣n-2·Fn-1t,if2≤n≤Q-1,-pO∣n·Fnt+pn-1∣n-2·Fn-1t,ifn=Q,∑q=1QpO∣q·Fqt,ifn=O.Because there areF1(0)=1 and Fn(0)=Fo(0)=0, we can further obtain the probability density function of delivery delay through Laplace transform and inverse Laplace transformation:(16)fot=∑n=1QpQ∣n⨂q=1npq-1∣q-2·e-pq∣q-1-pO∣q·t,where ⨂ denotes the convolution operation. Therefore, the expected delivery delay is expressed as(17)EDl=∫0∞t·fotdt,and the expected delivery ratio is expressed as(18)ERt=∫0t∗fotdt.The theoretical delivery delay and theoretical delivery ratio are calculated from (17) and (18) to compare against the simulation results of RTDDM in the next section.


## 6. Simulations

In this section, we present a thorough performance evaluation of our proposed RTDDM, along with a comparison study with the binary spray [19] (labeled by BINARY), BUBBLE Rap [20] (labeled by BUBBLE), and GSaR [7]. The performance metrics include the delivery ratio and the delivery delay. We develop a simulator using C++ language, and the mechanisms of overhearing and collisions (including the messages interactions for synchronization and backoff) have been realized in our simulator. Besides, the simulation results are averaged over 500 runs. The main parameter settings are shown in Table 1.Table 1
Simulation Parameters.
Parameter Description Value N Number of nodes 3,000 |D| Network space 100 × 100 m 2 rc Communication range 15 m t∗ Number of allowable time slots 9 τs Duration of each time slot 6 s K Number of regions 100 M Number of region types 10 ph Threshold of home region 0.35 α Exponent parameter 0.6 γ Exponent parameter 0.4Before the simulations, we collect the historical trajectories of node movements during the first 40 time slots, so that the average contact rate between nodes can be calculated, and the home regions of nodes can be determined. We compare the simulation results of RTDDM with theoretical results which are calculated by (17) and (18). From Figure 5, we observe that the overall trends of the two kinds of results are consistent, and the theoretical results are superior to the simulation results of RTDDM. This is because the theoretical results are always the optimal results which are obtained from centralized computations. Note that the standard deviation curves drop gradually with the increase of the number of nodes, which indicates that the simulation results of RTDDM can approach the optimal results when the nodes are deployed densely.Figure 5
Theoretical results versus simulation results of RTDDM.
(a)
Delivery ratio (b)
Delivery delayFigure6 shows the results of RTDDM, BINARY, BUBBLE, and GSaR. Obviously, the delivery ratios of three algorithms are increasing as the number of nodes increases. This is because a denser deployment of nodes usually provides more opportunities for data holders to disseminate the held data packets. As illustrated in Figure 6(a), RTDDM achieves a larger delivery ratio than the other algorithms. Similarly, in Figure 6(b), RTDDM also outperforms other algorithms in terms of delivery delay, and this phenomenon is attributed to the fact that RTDDM exploits the region type correlations which can reflect the movement preferences of nodes, and thus the data packets can be delivered to the destination region more quickly.Figure 6
Impacts of the number of nodes.
(a)
Delivery ratio (b)
Delivery delayThe delivery ratios of three algorithms perform better when the number of allowable times slots becomes larger, and the reason is that more data packets can be delivered to the destination region during a longer period, as shown in Figure7.Figure 7
Impact oft∗ on delivery ratio.Besides, we observe the impact of the maximum number of copiesQ, and the results are given in Figure 8. We find that a larger Q (i.e., more copies of each data packet) gives rise to a larger delivery ratio, along with a shorter delivery delay, although the dissemination cost will be accordingly increased. In some practical applications (especially the cost-sensitive applications), the dissemination cost must be taken into account, and the value of Q should be restricted to make a preferable tradeoff among the metrics of delivery ratio, delivery delay, and dissemination cost.Figure 8
Impacts of the maximum number of copiesQ.
(a)
Delivery ratio (b)
Delivery delay


## 7. Conclusions

This study explores the data dissemination problem for the delivery ratio enhancement and delivery delay reduction in MONs. The region type correlations and region weights are explored and utilized to select the relay nodes for data holders. Then, a Region Type based Data Dissemination Method (RTDDM) is proposed. In RTDDM, the region type correlations are first calculated, and then the relay nodes are determined through a Markov decision model. Simulation results suggest that RTDDM can improve the delivery ratio and reduce the delivery delay, and it is especially suitable for the MONs where there are various region types concerning the node contacts, such as the pocket switched networks comprised of human-carried mobile devices.



---

*Source: 1576286-2018-10-15.xml*