# GTDM: A DTN Routing on Noncooperative Game Theory in  a City Environment

Authors: Wenzao Li; Feng Lin; Jiliu Zhou; Yan Wang
Journal: Journal of Sensors
 (2015)

---

## Abstract

The performance of delay tolerant networks (DTNs) can be influenced by movement model in different application environments. The existing routing algorithms of DTNs do not meet the current city environments due to the large differences in node densities, social characteristics, and limited energy. The key indicators of DTNs such as success delivery ratio, average delivery latency, network lifetime, and network overhead ratio can influence the performances of civil DTNs applications. Aiming to improve the key indicators of DTNs in city environments, this paper presents a fixed sink station based structure and a more proper routing algorithm named Game Theory Based Decision Making (GTDM). GTDM shows decision-making process for neighborhood selection and packet delivering strategy which is based on the noncooperative game theory method and city environment characteristics. GTDM performance is evaluated using numerical simulations under Working Day Movement (WDM) model and the results suggested that GTDM outperforms other traditional DTNs routing approaches, such as Epidemic and Prophet algorithms.


---

## Body

## 1. Introduction

A delay tolerant network (DTN) is a network of thousands of resource-constrained mobile sensors for communication in some challenging environments. DTNs are characterized by their high latency, low delivery ratio, and long periods of disconnection due to the fact that network topology is changing continually. In recent years, the use of DTNs in metropolitan areas has attracted increasing attention [1–3]. In the future, “smart” cities may be created by essential public services using cutting-edge computing technologies [4], which are mainly realized on DTN platform. Unlike the use in other environments, such as battlefields, space, and oceans [5–7], there are more opportunities with the rapid development of portable smart devices. DTN routing problems are discussed based on the different requirements for various deployment environments and applications. Although there are several existing DTNs routing algorithms which can be applied to urban environments, the poor performance affects the efficiency of urban based DTN system. Thus, we focus on improving DTN performance in city scenarios; more efficient routing algorithm is designed for mobile nodes with constrained energy. In this paper, we propose a framework of sensor selection based on the game theory approach and the optimization of data queue management, which can find an energy consumption balance and have better network performance than Epidemic and Prophet routing algorithms. The main contributions of this paper are listed as follows.(1)
We describe the distributed fixed sink stations for data collection and the mobile node as the role of data source or relay node in a city environment. Then, a neighborhood node selection method is introduced.
(2)
A packet delivering decision-making algorithm GTDM for DTNs is proposed based on game theory approach. It is for routing determination of DTNs in city environments. The GTDM can determine punishment or reward between a pair of nodes through a game, and the active node can be measured by node asset.
(3)
The packet priority and packets transmission strategy between two nodes is present; in this way, a packet determined which node is the most proper packet carrier.
(4)
The performance of the proposed algorithm is validated by a series of experiments under WDM movement model. The result shows that GTDM can prolong the network lifetime and has better routing performance than Epidemic and Prophet routing algorithms.The remainder of the paper is organized as follows: Section2 describes the related works of the city environment based routing algorithm and Section 3 describes the suitable scenario and GTDM algorithm process. In Section 4, this paper gives the forwarding decision based on game theory (GT). In Section 5, we present the simulation settings and the results, and the paper is concluded in Section 6.


## 2. Related Work

A DTN protocol should be cautious in how it saves the limited network resources. So, a packet is transmitted to improper relay node, which can cause the decreasing of network performance. Then, how to determine whether a node sends packets to another node? In some instances, GT can be applied to solve such problem [8, 9]. Generally, there are two kinds of GT: cooperative game theory and noncooperative game theory. Cooperative game theory pays more attention to the maximal profits of the group through cooperative efforts. A node will act selfishly by minimizing their individual utility in a distributed decision-making environment. Noncooperative game theory focuses on each node’s individual utility, and less attention is given to the utility of the whole DTNs. The noncooperative method does not require nodes to have global knowledge. By contrast, under a cooperative approach, nodes with cooperative GT must agree on the premediated strategies and participants have global knowledge [10, 11]. Mobile nodes require a large amount of communication maintenance costs for global knowledge by cooperative approach; thus, DTNs with complete global knowledge are not realistic in reality. Considering the above, game formulations designed should adopt a noncooperative game approach which makes them more realistic.Based on the same considerations, El-Azouzi et al. [12] proposed a noncooperative game approach, where source and destination nodes were enclosed in two partly overlapping regions. The authors used the Epidemic routing algorithm for a high number of nodes. The Epidemic forwarding algorithm in DTNs maximizes the probability of successful data delivery. However, it ignores the existence of relationships between two people in a city environment. For example, two colleagues will spend all day working, which causes the mobile nodes to have repeated contact [13]. In addition, we believe that there are active objects and inactive objects in city environments [14]. The former objects will have more encounter opportunity than inactive objects, and the active sensor carrier is suitable as relay node. Besides that, mobile nodes have movement regularity and cyclical contact in city environments; regularity of encounters can be expected by history. Unfortunately, these conditions were not put into account by common DTN routing algorithms. Therefore, most of the existing routing algorithms do not work at their highest efficiency in cities. Focusing on the forwarding decision problem of routing patterns, Prophet is a probabilistic routing protocol that uses the past-encounter history and aging methods for forwarding decision and is one of the most commonly used routing algorithms in DTNs. Obviously, the Prophet routing algorithm does not consider all the characteristics of social relationships and the routines of pedestrians in city environments. Likewise, Epidemic routing algorithm cannot release ability under the limited resource scenario. Thus, we propose a more practical and effective GTDM-based routing algorithm, it takes into account various aspects of city environments, and it is a more flexible and scalable DTN routing algorithm for city environments.


## 3. GTDM Routing Algorithm

In city environment, the delivery ability of each node is not the same because of the limitation of moving range and individual regularity. And GTDM is designed for high ability nodes selection which is judged by history game process. Thus, it is suitable for some scenarios with regular moving nodes. In game-based DTN, the mobile nodes are considered to be participants in the game and must abide by the rules of the designing mechanisms. The forwarding nodes are offered by using incentives, and the misbehaving nodes are punished by the mechanisms. Moreover, any transmission behavior should be cautious; the meaningless forwarding also consumed the nodes’ energy. Obviously, the energy hole will decrease the performance of DTN; thus, the energy balance should be necessary to be considered in GTDM.


### 3.1. Mobile Nodes and Fixed Sink Stations in City Environments

When DTN is deployed in city environments, it can be used for data collection. Therefore, the mobile nodes should be data generator and relay carrier. The mobile nodes usually represent pedestrians, vehicles which are carrier sensors. In addition, some static stations as data collector are located in high node density regions. It is described as fixed sink station in this paper, and we have proposed it in the literature [15]. The mobile nodes and fixed stations are realistic schemes for application in city environments. For instance, Pham and Fdida [16] suggested that DTNs could aid in the distribution of news within cities through the use of fixed nodes. For another instance, the detection of malicious behavior through the use of a Misbehavior Detection System (MDS) was proposed to improve network performance, and it had been discussed in vehicular DTNs of metropolitan areas by Guo et al. [17]. There are some common traits between these described applications, such as node movement trajectory and regular moving. The trajectory can easily overlap the high-density path area with minimal costs and is matched with the given environment map. In addition, the Working Day Movement (WDM) model describes the dynamic behavior of people in cities [18]. So, we believe that the mobile nodes have many contact opportunities in higher path density regions, and fixed sink station is suitable for distributed location in such regions because of this regularity. In this way, DTNs can flexibly adjust the number of fixed sink station and fixed locations to achieve the desired performance. Further, the nodes have certain movement regularities within a moving region and active nodes can be selected by the history record. From what we have mentioned above, the routing algorithm should be designed based on this scenario’s features.


### 3.2. The GTDM Algorithm Process

The idea of GTDM is to build a series of determined strategies. Multiple indicators are established in each node; these indicators are changed constantly during the game process and delivering history. Then, several determinations are made in sequence.The details of GTDM routing algorithm are described as follows.(
1
) GTDM follows the normal form game of DTNs by a three-tuple G
=
N
,
S
,
F, which represents the game. Here, N
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
n
} is a finite set of n mobile nodes, which currently have effective connections. The strategy set space is described as {
S
1
,
S
2
,
…
,
S
i
,
…
,
S
n
}, where S
i represents strategy selection of the node i. The strategy combination is S
=
{
s
i
,
s
ı
-
}, where strategy s
i represents the choice of node i and s
ı
- is the choice of the other n
-
1 mobile nodes. F
=
{
F
1
,
F
2
,
…
,
F
i
,
…
,
F
n
} is the payoff function of the mobile node, which is defined as F
=
{
η
,
η
i
∗
}. Here, η is the award function and η
∗ is the punish function.(
2
) The mobile nodes in the DTNs are considered as participants of the game, and the nodes do not know the entire topology or the network parameters. Each mobile node establishes a metric list T, which contains the successful delivery of nodes list ω, coins count C
r
i, asset value v, the remaining buffer size L
r, and the energy level E
r. The list T of mobile node supports real-time updates. The value ω
i and energy level E
i
r of node i in list T are calculated in formulas (1) and (2) as follows:(1)
ω
i
φ
t
=
∑
t
=
0
t
ε
ω
i
φ
,
t
,where ω
i
φ
t represents the accumulated packet delivery statistics at time t, φ is the destination address set, and ε is the event counting function(2)
E
i
r
=
E
i
ini
-
∑
0
t
ε
′
(
E
b
,
t
)
E
i
ini
,where E
i
ini is the initial energy of node i. The energy consumption function is described by ε
′.(
3
) The mobile nodes are continuously scanning for neighbors. The routing process starts once a mobile node has packets to deliver. If node i finds neighbor nodes in the communication area, the node’s neighbor set is built as a finite N
i. Then, the first stage of packet delivery is started, and it includes two steps.Step 1.
Nodei traverses the packet in the sending buffer to determine whether the packet’s destination belongs to the set N
i. If the destination of the packets belongs to a neighbor node j, node i will be delivered directly to j. In GTDM, each packet destination is a fixed sink station. On the other hand, GTDM will only conduct neighbor scanning when N
i
=
∅.Step 2.
The destinations of the packets that belong to the setN
i are rearranged by increasing TTL values and are transmitted based on this order.(
4
) During the second stage, node i selects a neighbor as a relay node from set N
i to transmit the remaining packets. Node selection of the competition in the GTDM depends on asset v of the node in game theory. It satisfies the corresponding payoff function f
i
(
s
i
,
s
ı
-
)
≥
f
i
(
s
i
∗
,
s
ı
-
) for s
i
∗
∈
S
i. In the design of GTDM, the asset v is defined as follows:(3)
v
=
v
0
initial
value
v
i
otherwise
,
v
i
s
i
=
γ
η
c
i
if
node
wins
in
game
γ
η
∗
c
i
if
node
loses
in
game
,where v
i obeys the exponential distribution in [
-
∞
,
+
∞
]. γ is the reward factor and 0
≤
γ
≤
1, which represents the asset changes in intensity. η
c
i is the reward function, and η
∗
c
i is the punish function. The node j with the most powerful asset is selected. Once the decision is taken, each node cannot find whether the behavior influences the whole efficiency, because each sensor does not know about the networks.(
5
) After the neighbor node j has been selected as a proxy node, node i will selectively transmit the remaining packets with second traversal in the sending buffer. The node i then determines which packets will be transmitted to the proxy node j using the multidecision method. This process is described as follows.Step 1.
By first comparing the energy level ofE
r, node i will stop delivering packets if the condition E
i
r
>
E
j
r
+
Δ
E is satisfied. If this condition is not satisfied, node i will continue to Step 2.Step 2.
Each pending packet of nodei is calculated with node j for comprehensive forwarding weight τ. Here, τ
i of node i is calculated in the following:(4)
τ
i
=
α
ρ
p
i
j
σ
+
β
L
L
i
r
,where α, β are weight factors. Here, σ represents the destination address of the packet and σ
∈
φ. ρ
p
i
j
σ is the probability of delivering proportion. It represents which of the two nodes is more likely to successfully deliver packet and it is calculated in formula (5). L
L
i
r represents the free buffer ratio function and can be derived from formula (6):(5)
ρ
p
i
j
σ
=
ω
i
σ
(
t
)
ω
i
σ
t
+
ω
j
σ
(
t
)
t
≠
0
,
ω
i
j
σ
t
≠
0
0
otherwise
,
(6)
L
L
i
r
=
L
i
r
L
i
total
,where L
i
total represents the buffer size of node i. A higher value indicates a higher carrying capacity.Step 3.
At each stop in this second traversal, GTDM determines whether or not nodei transmits the current packet based on its comprehensive forwarding weight τ. Node i will be allowed to transmit the packet if the condition τ
i
<
τ
j is met.(
6
) When node i transmits a packet to the proxy node j, it represents a failure of node i in the game, and node i is punished by the function η
∗
c
i. Likewise, node j wins the game and it is rewarded by the function η
c
i. η
c
i, η
∗
c
i are calculated as follows:(7)
η
c
i
=
c
r
i
+
1
,
η
∗
c
i
=
c
r
i
-
1
.The asset value v of each node is changed by function (4) after this delivery decision. There are two traverses for neighborhood selection and packets selection in GTDM; the time complexity of GTDM is O
(
N
2
).


## 3.1. Mobile Nodes and Fixed Sink Stations in City Environments

When DTN is deployed in city environments, it can be used for data collection. Therefore, the mobile nodes should be data generator and relay carrier. The mobile nodes usually represent pedestrians, vehicles which are carrier sensors. In addition, some static stations as data collector are located in high node density regions. It is described as fixed sink station in this paper, and we have proposed it in the literature [15]. The mobile nodes and fixed stations are realistic schemes for application in city environments. For instance, Pham and Fdida [16] suggested that DTNs could aid in the distribution of news within cities through the use of fixed nodes. For another instance, the detection of malicious behavior through the use of a Misbehavior Detection System (MDS) was proposed to improve network performance, and it had been discussed in vehicular DTNs of metropolitan areas by Guo et al. [17]. There are some common traits between these described applications, such as node movement trajectory and regular moving. The trajectory can easily overlap the high-density path area with minimal costs and is matched with the given environment map. In addition, the Working Day Movement (WDM) model describes the dynamic behavior of people in cities [18]. So, we believe that the mobile nodes have many contact opportunities in higher path density regions, and fixed sink station is suitable for distributed location in such regions because of this regularity. In this way, DTNs can flexibly adjust the number of fixed sink station and fixed locations to achieve the desired performance. Further, the nodes have certain movement regularities within a moving region and active nodes can be selected by the history record. From what we have mentioned above, the routing algorithm should be designed based on this scenario’s features.


## 3.2. The GTDM Algorithm Process

The idea of GTDM is to build a series of determined strategies. Multiple indicators are established in each node; these indicators are changed constantly during the game process and delivering history. Then, several determinations are made in sequence.The details of GTDM routing algorithm are described as follows.(
1
) GTDM follows the normal form game of DTNs by a three-tuple G
=
N
,
S
,
F, which represents the game. Here, N
=
{
N
1
,
N
2
,
…
,
N
i
,
…
,
N
n
} is a finite set of n mobile nodes, which currently have effective connections. The strategy set space is described as {
S
1
,
S
2
,
…
,
S
i
,
…
,
S
n
}, where S
i represents strategy selection of the node i. The strategy combination is S
=
{
s
i
,
s
ı
-
}, where strategy s
i represents the choice of node i and s
ı
- is the choice of the other n
-
1 mobile nodes. F
=
{
F
1
,
F
2
,
…
,
F
i
,
…
,
F
n
} is the payoff function of the mobile node, which is defined as F
=
{
η
,
η
i
∗
}. Here, η is the award function and η
∗ is the punish function.(
2
) The mobile nodes in the DTNs are considered as participants of the game, and the nodes do not know the entire topology or the network parameters. Each mobile node establishes a metric list T, which contains the successful delivery of nodes list ω, coins count C
r
i, asset value v, the remaining buffer size L
r, and the energy level E
r. The list T of mobile node supports real-time updates. The value ω
i and energy level E
i
r of node i in list T are calculated in formulas (1) and (2) as follows:(1)
ω
i
φ
t
=
∑
t
=
0
t
ε
ω
i
φ
,
t
,where ω
i
φ
t represents the accumulated packet delivery statistics at time t, φ is the destination address set, and ε is the event counting function(2)
E
i
r
=
E
i
ini
-
∑
0
t
ε
′
(
E
b
,
t
)
E
i
ini
,where E
i
ini is the initial energy of node i. The energy consumption function is described by ε
′.(
3
) The mobile nodes are continuously scanning for neighbors. The routing process starts once a mobile node has packets to deliver. If node i finds neighbor nodes in the communication area, the node’s neighbor set is built as a finite N
i. Then, the first stage of packet delivery is started, and it includes two steps.Step 1.
Nodei traverses the packet in the sending buffer to determine whether the packet’s destination belongs to the set N
i. If the destination of the packets belongs to a neighbor node j, node i will be delivered directly to j. In GTDM, each packet destination is a fixed sink station. On the other hand, GTDM will only conduct neighbor scanning when N
i
=
∅.Step 2.
The destinations of the packets that belong to the setN
i are rearranged by increasing TTL values and are transmitted based on this order.(
4
) During the second stage, node i selects a neighbor as a relay node from set N
i to transmit the remaining packets. Node selection of the competition in the GTDM depends on asset v of the node in game theory. It satisfies the corresponding payoff function f
i
(
s
i
,
s
ı
-
)
≥
f
i
(
s
i
∗
,
s
ı
-
) for s
i
∗
∈
S
i. In the design of GTDM, the asset v is defined as follows:(3)
v
=
v
0
initial
value
v
i
otherwise
,
v
i
s
i
=
γ
η
c
i
if
node
wins
in
game
γ
η
∗
c
i
if
node
loses
in
game
,where v
i obeys the exponential distribution in [
-
∞
,
+
∞
]. γ is the reward factor and 0
≤
γ
≤
1, which represents the asset changes in intensity. η
c
i is the reward function, and η
∗
c
i is the punish function. The node j with the most powerful asset is selected. Once the decision is taken, each node cannot find whether the behavior influences the whole efficiency, because each sensor does not know about the networks.(
5
) After the neighbor node j has been selected as a proxy node, node i will selectively transmit the remaining packets with second traversal in the sending buffer. The node i then determines which packets will be transmitted to the proxy node j using the multidecision method. This process is described as follows.Step 1.
By first comparing the energy level ofE
r, node i will stop delivering packets if the condition E
i
r
>
E
j
r
+
Δ
E is satisfied. If this condition is not satisfied, node i will continue to Step 2.Step 2.
Each pending packet of nodei is calculated with node j for comprehensive forwarding weight τ. Here, τ
i of node i is calculated in the following:(4)
τ
i
=
α
ρ
p
i
j
σ
+
β
L
L
i
r
,where α, β are weight factors. Here, σ represents the destination address of the packet and σ
∈
φ. ρ
p
i
j
σ is the probability of delivering proportion. It represents which of the two nodes is more likely to successfully deliver packet and it is calculated in formula (5). L
L
i
r represents the free buffer ratio function and can be derived from formula (6):(5)
ρ
p
i
j
σ
=
ω
i
σ
(
t
)
ω
i
σ
t
+
ω
j
σ
(
t
)
t
≠
0
,
ω
i
j
σ
t
≠
0
0
otherwise
,
(6)
L
L
i
r
=
L
i
r
L
i
total
,where L
i
total represents the buffer size of node i. A higher value indicates a higher carrying capacity.Step 3.
At each stop in this second traversal, GTDM determines whether or not nodei transmits the current packet based on its comprehensive forwarding weight τ. Node i will be allowed to transmit the packet if the condition τ
i
<
τ
j is met.(
6
) When node i transmits a packet to the proxy node j, it represents a failure of node i in the game, and node i is punished by the function η
∗
c
i. Likewise, node j wins the game and it is rewarded by the function η
c
i. η
c
i, η
∗
c
i are calculated as follows:(7)
η
c
i
=
c
r
i
+
1
,
η
∗
c
i
=
c
r
i
-
1
.The asset value v of each node is changed by function (4) after this delivery decision. There are two traverses for neighborhood selection and packets selection in GTDM; the time complexity of GTDM is O
(
N
2
).


## 4. Forwarding Strategy Based on GT

In this section, we present the forwarding strategy used when there are two nodes based on GT. Game theory is a mathematical description that works to resolve conflict among self-decision-making players. Unlike the GTDM algorithm, the common GT considers both of the mobile nodes as individuals who can refuse the packets from the others. This behavior increases the complexity of the algorithm. After the forward decision is determined using the GT approach, nodei transmits all the packets. The transmission range of a mobile node in a city environment is likely to cover several nodes due to population density characteristics. In GTDM, set N is defined as a finite covered node set. The Sender Node (SN) broadcasts the information to the Receiver Node (RN), which is selected from the set N
i by the competition approach. The assets function represents the efficient functioning of node i and consists of two parts. The reward function allows the nodes to receive a profit for winning the game, while the punish function costs the nodes when they lose.In DTNs deployed in a city, pedestrian nodes move regularly with WDM in a relatively small area, and the destination addresses of each node packet may belong to different fixed stations. Under such circumstances, the node must deliver each packet to an appropriate relay. In other words, the packet would select a relay which is more likely to deliver a packet successfully or wait for a better opportunity.Figure1 suggests that the active pedestrian areas are relatively small and that the pedestrians have a regular routine. Based on the previous assumptions, if node i or node j has delivered the packets to the fix station successfully, the sink station will be nearby one or both of them in WDM. We calculate the delivery probability proportion by ρ
p
i
j
σ to solve the problem of whether or not node i will transmit a packet to node j. According to the above factors, this strategy determines whether to transmit the packet to j or to wait for a better competitor.Figure 1
The positions of two pedestrian nodes in simulation map at sampled period for 3600 s.It is assumed that a value of 1 of SN represents the forwarding decision and a value of 0 represents the abandonment of forwarding. An RN value of 1 represents receiving and an RN value of 0 represents failure of receiving. Summing up the strategies and assets of SN and RN, the payment matrix in GTDM is shown in Table1.Table 1
Game payment matrix of SN and RN:c
p represents the predicted cost value, and c
f represents the predicted profit value. c
r and c
s are the coin numbers of the RN and SN, respectively, before transmitting.
RN
0
1
SN
0
—
—
1
c
s
-
c
p, −
c
s
-
c
p, c
r
+
c
fFrom this, we are able to gradually marginalize the inactive nodes. In this game, we use the Nash Equilibrium to make the RN transmission decision.Selection Process
When RN selects 0: if SN selects 0, it will get the value 0. When SN selects 1, it will getc
s
-
c
p. Obviously, (
c
s
-
c
p
)
>
0 and then SN should select 1.
When RN selects 1: if SN selects 0, it will get the value 0. When SN selects 1, it will getc
r
+
c
f. Obviously, (
c
r
+
c
f
)
>
0, and then SN should select 1. The equilibrium is (
1,1
), and it means that the SN and RN are encouraged to perform transmission and receiving. It is a Pure Strategy Nash Equilibrium.


## 5. Simulation and Results

### 5.1. Simulation Design

The Opportunistic Network Environment (ONE) simulator [19] is chosen to realize the GTDM algorithm. Comparisons have been made between GTDM and the existing DTN routing algorithms, such as Epidemic and Prophet algorithms.Several assumptions are associated with simulation. First, pedestrians, buses, fixed sink stations, and taxies are each represented by a different node type. The pedestrian nodes have limited energy and run on a regular routine. Using the energy model outlined in [19], the energy constrained mobile nodes are based on an energy budget approach and the energy consumption E
b of a node can be expressed as follows:(8)
E
b
=
E
s
+
E
tr
⁡
+
E
sr
⁡
,where E
s represents the energy consumption associated with node scans. E
tr
⁡ is the transmission energy consumption per second when a message is sent. E
sr
⁡ is the energy consumption of each scanning response. The other types of nodes have no power constraints due to a constant power supply.Secondly, the mobile nodes are the data source and relay nodes which forward the packets to the fixed sink stations. Six fixed station nodes are distributed at the relatively high path density associated with city environments (Figure2).Figure 2
Fixed sink station in simulation scenario.Thirdly, for the purpose of mimicking “real world” environments as accurately as possible, each mobile node follows the WDM movement model. The WDM contains information about the locations of shops, houses, and offices. The residency time of a mobile node in any one location is controlled by the same mechanism. The map of downtown Helsinki is used as the deployment target. Additional city map details are provided by the ONE simulator [19].


### 5.2. Key Simulation Parameter Settings

In this simulation scenario, pedestrian nodes move regularly among shops, houses, and offices. These nodes are controlled by the WDM data set, which is provided by the ONE simulator. The key parameters of simulation scenario are shown in Table2, and the assumed key parameters of GTDM simulation are shown in Table 3.Table 2
Key simulation parameters.
Parameter name
Value
Word size
10000
∗
8000
Simulation time
5 days
City map
Helsinki
Buffer size
5 M
Message size
500 k–1 M
Message creation interval
10–15 seconds
Message TTL
1433 seconds
Transmission range for pedestrian
10 m
Transmission range for the others (taxi, station, and bus) nodes
100 m
Movement model for pedestrian
WDM
Movement model for taxi, bus
Shortest path of map based, bus movement modelTable 3
Key parameters set to GTDM algorithm.
Parameter symbol
Value
E
i
ini
300 K mAh
E
s, E
sr
⁡
1 mAh/s
E
tr
⁡
2 mAh/s
Δ
E
0.1
α, β
0.5
γ
0.98
v
0
0.5We should notice that we should fetch rational parameters. For instance, the mobile devices are commonly equipped with Bluetooth module, so the transmission range for pedestrian is 10 m.


### 5.3. Simulation Results

The DTN performance can be influenced by many factors such as the node density, packet size, and buffer size. Generally speaking, the more nodes lead us to encounter more opportunities, and then the game times in the high node density are more than the ones in the low node density. So, we observe the GTDM performance under different density.The delivery ratio is important indicator for DTNs; the better algorithm should have relative higher delivery ratio. The delivery ratios of the three algorithms with equal parameters and settings are shown in Figure3. We found that the delivery ratio of GTDM with the growth of node density is better than that of Epidemic or Prophet. At low node density, there is not a clear delivery ratio difference between Prophet and GTDM algorithms; it is more likely that the neighbor set N has only one node and it is not able to fully compete in the node selection. GTDM has better performance than the other algorithms when DTNs are at high node density. The Epidemic algorithm has the worst performance due to its limited buffer size and unselected forwarding.Figure 3
Packet delivery ratio comparison among different routing algorithms with mobile node density growth.The overhead cost ratio of DTNs is another important performance indicator. One of the purposes for DTN routing algorithm design is to minimize the network overhead costs, which result from a high number of packet copies. The overhead ratio is described as repetition rate. A higher overhead ratio results in lower DTN delivery efficiency. The overhead ratioR
ξ is calculated in the following:(9)
R
ξ
=
∑
0
t
ϖ
s
-
∑
0
t
ρ
s
∑
0
t
ρ
s
,where ϖ
s presents the successful transmitting times and ρ
s is the successful delivery times. If the R
ξ equals zero, it means that each transmitting behavior is a perfect delivery process.The overhead ratio of GTDM is better than that of the other two algorithms (Figure4). The overhead ratio of Epidemic and the Prophet algorithms becomes higher as the node density increases, meaning that the nodes cannot make efficient decisions as more opportunities become available.Figure 4
Overhead ratio comparison among different routing algorithms with mobile node density growth.The number of packets will increase with time lapse. The WDM captures the characteristic movement of real life scenarios, giving a greater number of contact opportunities at the peak of the crowd. The contact probability periodically changes over time (Figure5). Prophet algorithm does not take into account this long time period. The proper transmission opportunity will be missed because of the predicted value decrease with time. Similarly, Epidemic algorithm forwarded too many packets during the low number of contacting periods. So, this behavior results in higher overhead ratio than others.Figure 5
110-node contact statistics under WDM.The delivery predictabilityP
i
j of the Prophet algorithm impacts the decision-making and is influenced by an aging constant. For instance, even if a node has the ability to deliver a packet to the shop, its working time in the office may be much longer. In such case, P
i
j decreases over time, which may result in losing a delivery opportunity. Therefore, Prophet is not a suitable algorithm for the city environment. Due to the characteristics of the WDM movement, the latency trends of the average curve fluctuate by the three algorithms (Figure 6). The result suggests that latency average of GTDM is less than that of Epidemic or Prophet all the time.Figure 6
Latency average of Epidemic, Prophet, and GTDM with 110 nodes.We have observed the 110-node survival status under the city scenario. Most of nodes are dead in Epidemic when time is 298800 seconds (Figure7). The rest of nodes cannot maintain the normal performance of the system.Figure 7
Survival status of mobile nodes in Epidemic algorithm when time is 298800 s.Likewise, most nodes exhaust the energy under the same condition with Prophet algorithm (Figure8). The survived nodes are more in Prophet than in Epidemic routing.Figure 8
Survival status of mobile nodes in Prophet algorithm when time is 298800 s.From Figure9, it is shown that the survival nodes of GTDM algorithm are more than the other algorithms. It is clear that, in Epidemic routing, the node transmits packets to any node that it may come into contact with and the unlimited flooding algorithm will waste energy constantly. The Prophet algorithm transmits packets to a node with a relatively high delivery probability, but it is disturbed by the aging constant. Due to this, there are groups of node that have a similarly low delivery probability after a long period; thus, it is difficult to determine the relay node. Some nodes transmit the packets to others which have relatively high delivery probability under a period of time, and then the potential nodes will die out quickly. Obviously, the cascading effect will appear to shorten the DTNs lifetime.Figure 9
Survival status of mobile nodes in GTDM when time is 298800 s.In order to verify the energy balance by GTDM, the energy sample variance with time lapse is calculated by(10)
S
2
=
∑
i
=
1
n
x
i
-
E
x
2
n
-
1
,where E
(
x
) represents the sample mean and x
i is the energy sample value. A higher S
2 value indicates higher energy gap in nodes, which could cause premature death of some nodes. From Figure 10, it is shown that GTDM algorithm works well in balancing energy consumption of mobile nodes by decreasing the quantity of failed nodes and prolonging the network lifetime.Figure 10
Energy sample variance of three algorithms.


## 5.1. Simulation Design

The Opportunistic Network Environment (ONE) simulator [19] is chosen to realize the GTDM algorithm. Comparisons have been made between GTDM and the existing DTN routing algorithms, such as Epidemic and Prophet algorithms.Several assumptions are associated with simulation. First, pedestrians, buses, fixed sink stations, and taxies are each represented by a different node type. The pedestrian nodes have limited energy and run on a regular routine. Using the energy model outlined in [19], the energy constrained mobile nodes are based on an energy budget approach and the energy consumption E
b of a node can be expressed as follows:(8)
E
b
=
E
s
+
E
tr
⁡
+
E
sr
⁡
,where E
s represents the energy consumption associated with node scans. E
tr
⁡ is the transmission energy consumption per second when a message is sent. E
sr
⁡ is the energy consumption of each scanning response. The other types of nodes have no power constraints due to a constant power supply.Secondly, the mobile nodes are the data source and relay nodes which forward the packets to the fixed sink stations. Six fixed station nodes are distributed at the relatively high path density associated with city environments (Figure2).Figure 2
Fixed sink station in simulation scenario.Thirdly, for the purpose of mimicking “real world” environments as accurately as possible, each mobile node follows the WDM movement model. The WDM contains information about the locations of shops, houses, and offices. The residency time of a mobile node in any one location is controlled by the same mechanism. The map of downtown Helsinki is used as the deployment target. Additional city map details are provided by the ONE simulator [19].


## 5.2. Key Simulation Parameter Settings

In this simulation scenario, pedestrian nodes move regularly among shops, houses, and offices. These nodes are controlled by the WDM data set, which is provided by the ONE simulator. The key parameters of simulation scenario are shown in Table2, and the assumed key parameters of GTDM simulation are shown in Table 3.Table 2
Key simulation parameters.
Parameter name
Value
Word size
10000
∗
8000
Simulation time
5 days
City map
Helsinki
Buffer size
5 M
Message size
500 k–1 M
Message creation interval
10–15 seconds
Message TTL
1433 seconds
Transmission range for pedestrian
10 m
Transmission range for the others (taxi, station, and bus) nodes
100 m
Movement model for pedestrian
WDM
Movement model for taxi, bus
Shortest path of map based, bus movement modelTable 3
Key parameters set to GTDM algorithm.
Parameter symbol
Value
E
i
ini
300 K mAh
E
s, E
sr
⁡
1 mAh/s
E
tr
⁡
2 mAh/s
Δ
E
0.1
α, β
0.5
γ
0.98
v
0
0.5We should notice that we should fetch rational parameters. For instance, the mobile devices are commonly equipped with Bluetooth module, so the transmission range for pedestrian is 10 m.


## 5.3. Simulation Results

The DTN performance can be influenced by many factors such as the node density, packet size, and buffer size. Generally speaking, the more nodes lead us to encounter more opportunities, and then the game times in the high node density are more than the ones in the low node density. So, we observe the GTDM performance under different density.The delivery ratio is important indicator for DTNs; the better algorithm should have relative higher delivery ratio. The delivery ratios of the three algorithms with equal parameters and settings are shown in Figure3. We found that the delivery ratio of GTDM with the growth of node density is better than that of Epidemic or Prophet. At low node density, there is not a clear delivery ratio difference between Prophet and GTDM algorithms; it is more likely that the neighbor set N has only one node and it is not able to fully compete in the node selection. GTDM has better performance than the other algorithms when DTNs are at high node density. The Epidemic algorithm has the worst performance due to its limited buffer size and unselected forwarding.Figure 3
Packet delivery ratio comparison among different routing algorithms with mobile node density growth.The overhead cost ratio of DTNs is another important performance indicator. One of the purposes for DTN routing algorithm design is to minimize the network overhead costs, which result from a high number of packet copies. The overhead ratio is described as repetition rate. A higher overhead ratio results in lower DTN delivery efficiency. The overhead ratioR
ξ is calculated in the following:(9)
R
ξ
=
∑
0
t
ϖ
s
-
∑
0
t
ρ
s
∑
0
t
ρ
s
,where ϖ
s presents the successful transmitting times and ρ
s is the successful delivery times. If the R
ξ equals zero, it means that each transmitting behavior is a perfect delivery process.The overhead ratio of GTDM is better than that of the other two algorithms (Figure4). The overhead ratio of Epidemic and the Prophet algorithms becomes higher as the node density increases, meaning that the nodes cannot make efficient decisions as more opportunities become available.Figure 4
Overhead ratio comparison among different routing algorithms with mobile node density growth.The number of packets will increase with time lapse. The WDM captures the characteristic movement of real life scenarios, giving a greater number of contact opportunities at the peak of the crowd. The contact probability periodically changes over time (Figure5). Prophet algorithm does not take into account this long time period. The proper transmission opportunity will be missed because of the predicted value decrease with time. Similarly, Epidemic algorithm forwarded too many packets during the low number of contacting periods. So, this behavior results in higher overhead ratio than others.Figure 5
110-node contact statistics under WDM.The delivery predictabilityP
i
j of the Prophet algorithm impacts the decision-making and is influenced by an aging constant. For instance, even if a node has the ability to deliver a packet to the shop, its working time in the office may be much longer. In such case, P
i
j decreases over time, which may result in losing a delivery opportunity. Therefore, Prophet is not a suitable algorithm for the city environment. Due to the characteristics of the WDM movement, the latency trends of the average curve fluctuate by the three algorithms (Figure 6). The result suggests that latency average of GTDM is less than that of Epidemic or Prophet all the time.Figure 6
Latency average of Epidemic, Prophet, and GTDM with 110 nodes.We have observed the 110-node survival status under the city scenario. Most of nodes are dead in Epidemic when time is 298800 seconds (Figure7). The rest of nodes cannot maintain the normal performance of the system.Figure 7
Survival status of mobile nodes in Epidemic algorithm when time is 298800 s.Likewise, most nodes exhaust the energy under the same condition with Prophet algorithm (Figure8). The survived nodes are more in Prophet than in Epidemic routing.Figure 8
Survival status of mobile nodes in Prophet algorithm when time is 298800 s.From Figure9, it is shown that the survival nodes of GTDM algorithm are more than the other algorithms. It is clear that, in Epidemic routing, the node transmits packets to any node that it may come into contact with and the unlimited flooding algorithm will waste energy constantly. The Prophet algorithm transmits packets to a node with a relatively high delivery probability, but it is disturbed by the aging constant. Due to this, there are groups of node that have a similarly low delivery probability after a long period; thus, it is difficult to determine the relay node. Some nodes transmit the packets to others which have relatively high delivery probability under a period of time, and then the potential nodes will die out quickly. Obviously, the cascading effect will appear to shorten the DTNs lifetime.Figure 9
Survival status of mobile nodes in GTDM when time is 298800 s.In order to verify the energy balance by GTDM, the energy sample variance with time lapse is calculated by(10)
S
2
=
∑
i
=
1
n
x
i
-
E
x
2
n
-
1
,where E
(
x
) represents the sample mean and x
i is the energy sample value. A higher S
2 value indicates higher energy gap in nodes, which could cause premature death of some nodes. From Figure 10, it is shown that GTDM algorithm works well in balancing energy consumption of mobile nodes by decreasing the quantity of failed nodes and prolonging the network lifetime.Figure 10
Energy sample variance of three algorithms.


## 6. Conclusion

Currently, the suitable DTN routing algorithm for city environments is one of the most important topics and it attracts numerous scholars’ concern. We present GTDM algorithm, a routing algorithm of transmitting decision-making based on game theory. With the GTDM framework, several operations are implemented to adjust the transmitting queues and ensure that the proper node is chosen to transmit the proper packets. The overhead cost ratio, energy consumption, and average latency in GTDM are minimized through comparison with the algorithms of Epidemic and Prophet. Other simulation results by WDM, such as delivery ratio and network lifetime, support GTDM over Epidemic and Prophet algorithms in city environments. The provision, an algorithm with better energy balance, more efficient forwarding mode, and more flexible deployment, will help pave the way for future smart city networks and diverse applications of DTNs. Further studies are still necessary in the future; we should look for more efficient payoff functions for performance optimization and make further experimentation using real data set. In addition, there should be an efficient sleeping and awakening mechanism for energy-saving in city environments.



---

*Source: 410298-2015-06-01.xml*