Printer Friendly

IAR-GT: An Incentive Aware Routing based on Game Theory for Selfish Opportunistic Networks.

1. Introduction

Opportunistic networks (OPPNETs) [1] have been used in many scenario of wireless communication. In OPPNETs, the node forwards mesasges through encounter opportunities with a "store-carry-and-forward" manner. Due to the special transmission manner, many routing protocols have been proposed. Epidemic routing [2] is a classic routing in OPPNETs, which uses a flooding method to forward the message copies to all neighbors encountered. PROPHET routing [3] is also a multi-copy routing. In the scheme, the node forwards message to the neighbors which have higher historical encounter probability to the destination than that of the current node. Spray-and-Wait (SNW) [4] combines Epidemic and direct forwarding, flooding the message to a fixed number, and then transmitting them by direct transmission. Moreover, Some single-copy routing schemes have been discussed in reference[5]. In order to achieve a better tradeoff between the single-copy and multi-copy routing, Li et al. [6] proposed a Nash bargaining solution based routing scheme for resource constraint OPPNETs. In addition, Taking in account the social characteristics of the node, Moreira et al. [7] presented a novel routing dLifeComm, which considers social daily routines and use centrality when forwarding message. Moreover, for the content-based message delivery, Musolesi et al. [8] presented routing scheme based on the context information for delay-tolerant mobile networks. Zhao et al. [9] proposed an energy-efficient content delivery scheme, in which using D2D opportunistic transmission manner among mobile devices with constrained resources. Furthermore, in order to make full use of energy and spectrum for massive video delivery in ultra-dense networks, Zhou et al. [10] proposed an intelligent collaboration based content delivery scheme.

However, the aforementioned existing works did not consider the node's selfish, which assumed that the mobile users are cooperative and never decline service to the others. In reality, the mobile users may be selfish for saving their limited resources. The selfishness of nodes can be divided into two types: social selfishness and individual selfishness [11]. The individual selfishness means that the selfish node has the same degree of selfishness to the others, and the social selfishness means that the selfish node have a preference to service the nodes which have social relationship with it.

There are many incentive based forwarding schemes for the selfish behavior of nodes in data transmission. For the individual selfishness, Shevade et al. [12] employed pair-wise tit for tat (TFT) model to incentivize selfish node forwarding for delay tolerant networks (DTNs).This routing makes every selfish node forward as much traffic for a neighbor as the neighbor forwards. Wei et al. [13] proposed a novel incentive scheme MobiID for DTNs, which is based on the social aware reputation and user centric. Ciobanu et al. [14] proposed a novel social-based collaborative content and context-based selfish node detection and incentive mechanism for OPPNETs. Jo et al. [15] researches the selfish problem in cognitive radio ad hoc networks, in which the authors identify a new selfish attack type and proposed an efficient selfish attack detection technique. In addition, Zhu et al.[16] proposed a secure multilayer credit-based incentive scheme (SMART) for selfish DTN, which makes use of the virtual electronic credit to reward and charge for the relayer. Similarly, Lu et al. [17] also proposed a practical credit-based incentive protocol, which focuses on the fairness issue in DTNs. Furthermore, in order to slove the selfish problem for probabilistic routing, Wu et al. [18] presented a incentive scheme based on a game-theoretic model. Moreover, incentive compatible routing protocol (ICRP) [19] has been proposed for two-hop DTNs, by employing optimal sequential stopping rule and game theory model. However, all the above works did not consider social selfishness in OPPNETs, which plays an important role in network performance optimization.

On the other hand, the social selfishness also affects node behaviors. A node may prefer to help some nodes that have stronger ties with it. However, there are few works incorporating incentive with social selfishness for cooperation in OPPNETs. In [11], Li et al. presented a social selfishness aware routing for selfish DTNs, which considers the willingness of user and their contact chances. In [20], Li et al. studied the influence of social selfishness to the Epidemic routing, by using two dimensional continuous time Markov chain, it achieves message transmission between social selfish nodes. Moreover, in [21], Jedari et al. proposed a novel incentive mechanism for the social-aware routing from a game theory perspective, which can stimulate selfish nodes to participate forwarding message. Taking into account the social and individual selfishness, Sermpezis et al. [22] considered the effect of social selfishness in data transmission, and presented a framework from the mobility patterns and social features. They modeled selfishness in heterogeneous OPPNETs and studied the effect of it in delivery delay, average power consumption and delivery probability. However, this evaluation only addressed the impact of social selfishness on the performance of OPPNETs.

In short, the existed research works did not comprehensively consider the two kinds of selfishness, and did not effectively utilize the node's encounter status.

In this paper, we propose IAR-GT scheme for selfish OPPNETs.The main contributions can be listed as below.

* We investigate the factors that can affect individual selfishness and social selfishness, and present a new method to calculate social relations among nodes, by using the contact history information.

* We model the data forwarding between two selfish nodes as a Rubinstein-Stahl bargain game, and introduce the virtual currency for paying for the relay service. In the construction of the price function, we consider many factors that can impact the player's price, such as user's resources, social relationship, owned virtual currency, and message inforamtion.

* A novel incentive aware data forwarding algorithm is proposed, which exploits multi-copy routing with limited replications, and uses the incentive scheme to achieve efficient data transmission among selfish nodes.

* By using MIT Reality traces from 3 different selfish situations, the performance of IAR-GT scheme has been evaluated. Through the evaluation, we found that IAR-GT scheme performs better than the comparative routing protocols.

The rest of this paper is arranged as follows. Section II describes the system model. Section III gives the factors that affect node selfishness. Section IV gives our incentive aware routing scheme. Simulation results are shown in Section V. Finally, we give the conclusion in Section VI.

2. System Model

In this part, by studying the selfishness of nodes, we propose a novel system model. We first introduce some knowledge about the Rubinstein-Stahl bargain game [23]. In this model, two players are bargaining on the partition of a cake of size 1. Each player, in turn offers a partition (x,1- x), and his opponent may agree to the offer "Y" or reject it "N". Acceptance of the offer ends the bargaining. After rejection, the rejected player must make a counter offer and so on. This game can run many rounds, but with increase of the number of round, the benefits of two players will discount at the geometric rate [[delta].sub.1], and [[delta].sub.2] (0 < [[delta].sub.1], [[delta].sub.2] < 1), which can be interpreted as cost of delay or "cake spoiling".

In our system model, as shown in the Fig. 1, selfish user 1 hopes that selfish user 2 can help it forward message m, and user 1 and user 2 may have social ties. By using the Rubinstein-Stahl bargain game model, the buyer B is a node carring message, such as user 1 in Fig.1, and the seller S is a node that can provide forwarding services, such as user 2, the commodity is the forwarding service.

Furthermore, we suppose that each node has some type of virtual currency for payment. To enable nodes to pay, we assume that there is a Credit Clearance Center (CCC) [18] in order to manage the virtual currency for nodes. The CCC is a server connected to the Internet, hence, the node in OPPNETs can access the CCC when it connects to the Internet. Each node should register on the CCC, and obtains an account. When two nodes reach the agreement through the bargaining game, the relay node which provided the forwarding service will give a digitally signed receipt, and charges its payment by submitting the receipt to the CCC. After the message is successfully transmitted, the destination sends an ACK to the CCC, CCC verifies the receipts and pays the corresponding virtual currency to the relay node according to the receipt. Furthermore, CCC will charge for the message carrier node, which periodically contacts the CCC to renew its certificate and pays virtual currency for the relay services it received from the relay node. After that, CCC clears their signed receipts. Each node tries to pursue the virtual currency in order to afford the relay services from other nodes for its own message in the future.

In addition, our incentive aware routing makes the following assumptions:

* There are two kinds of nodes in the network: normal (cooperation) nodes and selfish nodes. In addition, selfish nodes are not malicious nodes, each node does not delete the message, does not fake and tamper the information of itself and the message.

* Selfish nodes are limited rational. That is, each node will maximize its profit. Meanwhile, nodes only consider whether their profits are maximized at the moment of accepting a message, but will not consider whether they may consume more benefits when they forward this message.

Factors Affecting Node Selfishness

In OPPNETs, nodes may appear individually selfish for their limited resources, and socially selfish for the different social ties. In fact, many factors can induce node selfishness. In the following, we first give the factors that can affect the node selfishness.

There are many factors which can impact the nodes selfishness. The first factor is the node resource. Suppose that the i's total energy is [E.sub.i], and the i's buffer size is [S.sub.i], which are known at time t. The residual buffer space and energy of node i at time t define as [r.sup.S.sub.i] (t) and [r.sup.B.sub.i](t). For node i, its estimated residual resource ratio at time t is

[R.sub.i](t) = [[[[omega].sub.1][r.sup.S.sub.i](t)]/[S.sub.i]] + [[[[omega].sub.2][r.sup.E.sub.i](t)]/[E.sub.i]] (1)

where [[omega].sub.1] and [[omega].sub.2] are the weights, being constrained by [[omega].sub.1] + [[omega].sub.2] = 1.

Furthermore, nodes can show social selfishness because some social relationships. In the paper, we measure the strength of sicial relations relying on the social pressure metric [24] and the social similarity. The social pressure metric (SPM) can show 3 characteristics of strong relationship: high encounter frequency, regularity, and longevity. The SPM of node i and j is caculated by

[SPM.sub.i,j] = [[[[integral].sup.T.sub.t=0]f(t)dt]/T] (2)

where T is the time interval, f(t) is the remaining time to the first encounter of these nodes after time t.

The social similarity between nodes i and j can be denoted as [socsim.sub.i,j], which can reflect the degree of similarity between two nodes. Suppose that the number of i's (j's) neighbors is expressed as [n.sub.i] ([n.sub.j]), and the number of common neighbors between i and j denotes as [com.sub.t,j], so, [socsim.sub.i,j] is computed as follows

[socsim.sub.i,j] = [[com.sub.i,j]/[n.sub.i] + [n.sub.j]] (3)

After defining the social pressure metric and the social similarity, we can give the social ties [ST.sub.i,j] between node i and j, which is expressed by

[ST.sub.I,J] = 1/[phi][SPM.sub.i,j] + (1-[phi])[socsim.sub.i,j] (4)

where [phi]([member of] [0,1]) is the weight factor.

4. Incentive Aware Routing Scheme

Because nodes in the networks are selfish without any incentive mechanism, they may not relay messages for the other nodes. Hence, we use the Rubinstein-Stahl bargain game to incentivize selfish nodes, and then make use of the incentive scheme to data forwarding.

4.1. Incentive Scheme based on Rubinstein-Stahl Bargain Game

In the bargain game, we need to define the price function for two players because they will offer price alternatively.

For the buyer B, it is the message carrier, its goal is to buy the relay service of the seller S for a message, which may be affected by many factors. First, the message size can affect the buyer's price. If the message size is very large, the buyer should spend more money, because it will consume more resources for relaying this message. Second, the message residual TTL (Time-to-Live) is also a factor that can affect the buyer's price. This is because if the message residual TTL is short, which means message owner wants to forward it to the destination as quickly as possible, hence, it will give a higher price for the relay node. In addition, the buyer node's residual resource affects its price. Because if the buyer has enough resource, it will be more patient to wait more suitable relay nodes, so, the buyer will give a lower price. Finally, the number of virtual currencies owned by buyer B also affects the price. This is because if the buyer has enough virtual currencies, it is willing to pay more virtual currencies for relay service. Hence, the price of buyer B for the message m at time t can be discribed as

[pr.sub.B,m](t) = [[sigma].sub.B] x [L.sub.(m)] x [C.sub.B](t) x (1/[[rho].sub.1][R.sub.B](t) + [[rho].sub.2][T.sub.B,m]) (5)

where [[sigma].sub.B] is a buyer B's price factor, [C.sub.B] (t) is the number of virtual currencies owned by B at time t, [L.sub.(m)] is the message m's size, [R.sub.B](t) is the residual resource ratio of buyer at time t, [[rho].sub.1] and [[rho].sub.2] are the weight factors satisfying [[rho].sub.1] + [[rho].sub.2] = 1, and [T.sub.B,m] is the message m's residual TTL ratio for buyer B at time t, which is computed as

[T.sub.B,m] = [RT.sub.B,m]/[TTL.sub.m] (6)

where [RT.sub.B,m] is the message m's residual TTL at time t, and [TTL.sub.m] is the total TTL of message m. We consider the TTL in the buyer's price, this is because the nodes that carried the message should forward as soon as possible when the TTL of a message is going to expire.

For the seller S, it is a relay node, which can provide relay service to the buyer B. Its price may be affected by the relationship between the seller and the buyer besides the virtual currency and residual resource. The reason is that if the residual resource of seller is insufficient, and it spends scarce resources to provide relay service for the buyer, it will charge more money. In addition, if the seller has enough virtual currencies, it will have more patience to obtain more money. Moreover, the price of the seller will be discounted according to the relationship between it and the buyer, the better the social relationship between them is, the greater the price discount it has. So, the price of seller S is discribed as

[pr.sub.S,m](t) = [[sigma].sub.S] x [L.sub.(m)] x 1/[ST.sub.S,B] x [C.sub.S](t) x [1/[R.sub.S](t)] (7)

where [[sigma].sub.S] is a seller S's price factor, [ST.sub.S,B] is social ties between S and B, [C.sub.S](t) is the number of virtual currencies owned by S at time t.

In the bargain game, two players make offers [pr.sub.Bm] (t) and [pr.sub.S,m] (t) alternately, and they may come to an agreement only when the price of buyer B is greater than the price of seller S. In the paper, we define the difference between the two prices as the total profit of the bargain game, which is expressed as follows

[Val.sub.m](t) = [pr.sub.B,m] (t) - [pr.sub.S,m] (t) (8)

The two players will divide the total profit by bargaining game. The set of the possible agreement is

X = {([x.sub.S], [x.sub.B]) [member of] [R.sup.2]: [x.sub.S] [greater than or equal to] 0, [x.sub.B] [greater than or equal to] 0, [x.sub.S] + [x.sub.B] = 1} (9)

where [x.sub.S] and [x.sub.B] are the ratio of the total profits divided for S and B respectively.

Furthermore, two selfish players try to maximize their benefits, each of them wants to get profit as much as possible. So, the utility of two players for message m will be describe as

[u.sub.S,m]([x.sub.S]) = [x.sub.S][Val.sub.m], [u.sub.B,m]([x.sub.B]) = [x.sub.B][Val.sub.m] (10)

The Rubinstein-Stahl bargain game may be carried out in many rounds, and each round of game will consume a certain amount of utility, this cost is defined as the discount factor. Suppose that [[delta].sub.S] and [[delta].sub.B] are the discount factor for seller S and buyer B respectively. So, two palyer's utility function will be described as

[u.sub.S,m]([x.sub.S]) = [[delta].sub.S][x.sub.S][Val.sub.m], [u.sub.B,m]([x.sub.B]) = [[delta].sub.B][x.sub.B][Val.sub.m] (11)

In the game, the player's patience will affect the negotiation process. If the buyer's virtual currency and its estimated residual resource are enough, furthermore, the message m's residual TTL is also enough, it will expect to obtain more proportion of the benefit. So, the buyer may be more patient in the negotiation. The value of patience is from 0 to 1. Hence, for the buyer B, the conditions of its patience functions can be defined as follows

[[d[[delta].sub.B] ([C.sub.B] (t) x [R.sub.B](t) x [T.sub.B,m])]/d([C.sub.B] (t) x [R.sub.B] (t) x [T.sub.B,m)]] [[delta].sub.B] (0) = 0, [[delta].sub.B] ([infinity]) = 1 (12)

In the paper, we use the following function [25] to express the patience of buyer B

[[delta].sub.B](y) = [[[e.sup.[lambda]y] - [e.sup.-[lambda]y]]/[e.sup.[lambda]y] + [e.sup.-[lambda]y]] (13)

where [lambda] is the buyer's patience coefficient, and y = [C.sub.B] (t) x [R.sub.B] (t) x [T.sub.B,m] is an independent variable, which changes according to the buyer's currently resources and message residual TTL.

The seller S will try its best to win more virtual currency from different users, so, it lacks patience in the game, and its patience will change from 1 to 0. Hence, for the seller S, the conditions of its patience functions can be defined as follows

[[d[[delta].sub.S]([ST.sub.S,B] X [C.sub.S](t) x [R.sub.S](t))]/d([ST.sub.S,B] X [C.sub.S](t) x [R.sub.S](t))] [[delta].sub.B](0)=1, [[delta].sub.B]([infinity])=0 (14)

In the paper, the seller S's patience can be expressed by using the following function [25].

[[delta].sub.s] (x) = [[[e.sup.[micro]x] - [e.sup.-[micro]x]]/[e.sup.[micro]x] + [e.sup.-[micro]x]] (15)

where [micro] is the seller's patience coefficient, and x = [ST.sub.S,B] x [C.sub.S] (t) x [R.sub.S] (t) is an independent variable, which is determined by the social ties, the seller's virtual currency and the estimated residual resource.

There exists a unique subgame perfect Nash Equilibrium for the Rubinstein-Stahl bargaining game. After several rounds of game, both players will reach an agreement, and the final agreement is described as follows.

([x.sup*.sub.B],[x.sup*.sub.S]) = ([[[1-[[delta].sub.S]]/1-[[delta].sub.B][[delta].sub.S]], [[[delta].sub.B](1-[[delta].sub.S])]/1-[[delta].sub.B][[delta].sub.B]]) (16)

The final results of the bargain game can be caculated by exchanging both patience factors, so, the real bargaining process is not necessary for reducing overhead and excessive workload caused by the bargining.

After determining the equilibrium solution of the bargaining game. If two players achieves a transaction, the transaction price of providing relay service for message m can be discribed as

[,m] = [pr.sub.B,m](t)-[x*.sub.B][Val.sub.m] (17)

4.2. Forwarding Scheme

After constructing the incentive model for selfish nodes, we present the forwarding scheme. We use a multi-copy strategy with the limited numer of copies, that is, the source should copy the limited number of message copies and forwards one of the copies to its encountered node that has the higher predictability to the destination than that of the source node, and this relay node will use the direct transmission to forward message. In order to clearly illustrate the forwarding process of our incentive aware routing, we give an example in the following.

Suppose two nodes i and j have a chance to meet, and node i wants to forward message m to destination D. Node i firstly determines whether node j is the destination D of message m; if so, then node i forwards message m to j; otherwise, node i determines whether node j has a higher history probability to meet destination D by probe packet. If node j has a higher probability to encounter D than the current node i, then node i will bargain with node j so as to incentivize selfish node j to forward message m; otherwise, node i will continue carry the message m, and look for new relay nodes.

When two nodes perform the bargain game, the node i firstly sends message ID, size [L.sub.(m)], its patience factor [[delta].sub.i](y) and price [pr.sub.i,m] (t) to node j. The node j is a selfish relay, which sells its service for forwarding message m. When j receives the information sent by i, it caculates the social ties [ST.subg.i,j], its price [pr.sub.j,m] (t), and determines whether the price of buyer i is greater than that of the seller j. If [pr.sub.i,m] (t) < [pr.sub.j,m] (t), the game will be over; otherwise, the node j computers the value ([x.sub.j], [x.sub.i]) and transaction price [,m], and feedbacks the information about ([x*.sub.j], [x*.sub.i]), [pr.sub.j,m] (t), and [,m] to node i. After receiving the information, node i will determine whether its utility is greater than 0, if [u.sub.i,m] ([x.sub.i]) > 0, node i will send message m to the relay j, as shown in Fig. 2.

When the buyer i and the seller node j complete the transaction, they will sign a digitally signed receipt about this transaction, which includes the message m's ID and its transaction price, and each side of node will hold a copy of receipt. The seller node j claims its payment by submitting its signed receipts to the CCC when it connects to the Internet. After receiving the message m, the destination will send an ACK to the CCC, CCC verifies the receipts and pays the corresponding virtual currency to the relay node j based on the signed receipt. In addition, CCC will charge for the buyer node i based on the signed receipt. The buyer periodically contacts the CCC to renew its certificate and pay for the services (message relay) he received from the seller according to the transactions' receipts. After that, CCC clears their signed receipts.

The forwarding algorithm and the incentive aware algorithm are shown in Algorithm 1 and Algorithm 2.
Algorithm 1 Forwarding Algorithm

1: node i carries message m and encounters node j
2: if (node j is the destination of message m) then
3: node i forwards message m to node j
4:    else if (node i has higher history probability to encounter the
         destination of m than the node j) then
5:       node i continue to carry the message m
6:     else
7:       node i will bargain with node j (Algorithm 2)
8:     end if
9: end if

Algorithm 2 Incentive-Aware Algorithm

 1: node i sends the information about message ID, [L.sub.(m)],
    [pr.sub.i,m] (t), and [[delta].sub.i](y) to node j
 2: node j caculates the social ties [ST.sub.i,j] and its price
    [pr.sub.j,m] (t)
 3: if ([pr.sub.i,m] (t) < [pr.sub.j,m](t)) then
 4: the bargaining game will be over
 5: else
 6: node j calculates ([x*.sub.j], [x*.sub.i]), [u.sub.j,m]
    ([x*.sub.j], and piggybacks ([x*.sub.j], [x*.sub.i])
    with [pr.sub.j,m] (t) and [[delta].sub.j] (y) to node i through
    acknowledgement packet
 7: node i determines whether its utility [u.sub.i,m]([x*.sub.i])
    is greater than 0
 8:   if ([u.sub.i,m] ([x*.sub.i]) > 0) then
 9:   node i will send message m to node j
10:   else
11:   the bargain game will be over
12:   end if
13: end if

5. Performance Evaluation

In this section, we compare the performance of the IAR-GT scheme with existing works in the ONE [26]. We firstly give the simulation settings, and analyze the simulation results.

5.1. Simulation Settings

We use the MIT Reality data traces [27] from the CRAWDAD [28]. The MIT Reality data set consists of the traces of 97 Nokia 6600 smart phones which were carried by students and staff at MIT over nine months. In our simulations, we only used a part of data for simulation. Some other simulation parameters are shown in Table 1.

In additions, we construct a weighted social graph for the Reality data trace by refering to the method in [29], modifying it according to (4), which can efficiently reflect the strength of social ties between two nodes. Furthermore, the initial energy of node is set to be 2000J, the mainly consumed energy of the node is used for message processing (receive and forward), we assume that the energy consumed for processing one message is (2 + 0.006X) J [30], where X (kB) is the message size. In addition, the node's energy can attenuate with increasing of time, the energy of node after the time [DELTA]t is [E.sub.[DELTA]t] = [e.sup.-[lambda][DELTA]t][E.sub.t], where [lambda] = 0.1. Every node has an initial vittual currency of 150.

5.2. Evaluation Metrics

We evaluate the performance of routing protocols in terms of the following metrics:

Message Delivery Ratio = [number of delivered messages/number of generated messages]

Average Delay: It is given by the time duration between the message generation and their delivery.

Overhead = [number of relayed messages--number of successfully delivered messages/number of successfully delivered messages]

Delivery Ratio x (1 / Average Delay) x Goodput [31]: the metric evaluates the overall performance of a specific protocol, where

Goodput = [number of successfully delivered messages/number of relayed messages]

5.3. Simulation Results and Analysis

We compare the incentive-aware routing IAR-GT with the other four classical routing protocols.

Epidemic [2]: Epidemic routing is flooding routing in OPPNETs, which is a classical multi-copy routing schemes.

dLifeComm [7]:The scheme is designed based on the users' daily routine, and our routing IAR-GT is also designed for social-based environment.

Spray-and-Wait (SNW) [4]: This scheme is a classical quota-based routing protocol in OPPNETs.

ICRP [19]: ICRP is an incentive-compatible routing protocol, which is designed for selfish two-hop DTNs.

Furthermore, for Spray-and-Wait, ICRP and IAR-GT, the number of copies is 8.

(1) Comparison Results with different Selfish Nodes

In this experiment, the percentage of selfish nodes varies from 0% to 80%. Moreover, the buffer size is 15M, and the message's TTL is 1440 minutes.

Fig. 3 (a) presents the delivery ratio of five protocols, in which the delivery ratio decreses as increasing the number of selfish nodes. However, the other three routings have smaller delivery ratio than that of ICRP and IAR-GT, because they are no incentive mechanism to incentivize selfish nodes for transmission. Moreover, Epidemic routing has the lowest delivery ratio. This is because Epidemic routing floods its message replicates to all their neighbors, but its drawbacks are also very obvious, Epidemic routing induces a large number of redundant packets and consumes a large amount of resources. So, in enough resources situation, Epidemic routing can achieve the highest delivery ratio. But in our simulation, the node's resources are limited, Epidemic routing will induce serious message loss in this situation, furthermore, because it does not adopts incentive mechanism when nodes are selfish. Hence, Epidemic routing has the worst performance in delivery ratio. The IAR-GT scheme achieves the highest delivery ratio, this is because the scheme considers individual and social selfishness, which can incentivize more selfish nodes to participate forwarding copies. The ICRP has smaller delivery ratio due to without considering social features in routing design.

Fig. 3 (b) depicts the average delay on different selfish nodes among five routing protocols, in which the average delay increses as increasing the number of selfish nodes. and the Epidemic scheme has the smallest average delay, since it floods messages to all encountered neighbors, hence the messages will be quickly delivered to their destinations. The IAR-GT has a smaller delay than the other three routings due to jointly considering many factors to characterise nodes' selfish behaviors in bargaining game, and then it can enhance the packets forwarding processing.

Fig. 3 (c) depicts the overhead on these five routing protocols. The overhead of Epidemic is far larger than the others, because the flooding-based forwarding manner and selfish nodes will induce and serious packet loss. In the subfigure, we can see that the IAR-GT scheme' overhead is slightly higher than that of the ICRP and SNW. Because the incentive mechanism of IAR-GT can use more selfish nodes to enhance the packets forwarding processing, guaranteeing the delivery ratio. The ICRP scheme adopts a two-hop manner, only the source and its one-hop relayer directly forward messages. SNW scheme will fall into "Wait" stage after spraying fixed number of message, and it does not exploit incentive mechanism, when the percentage of selfish nodes in the networks is 0.2, there are also 80% non-selfish nodes in the networks, hence, the SNW routing can also forward message through non-selfish nodes. Furthermore, in two hop relay routing, since only source can decide packet relaying, the relay node either forward the message when meeting the destination or drop the message. But SNW routing allows more relay node to forward message in spraying stage, hence, SNW can forward more messages and has higher overhead than that of ICRP when the percentage of selfish nodes is low. When the percentage of selfish nodes in the networks increases to 0.6, there are large of selfish nodes in the networks, which can obstruct the message's relay if without efficient incentive scheme. Hence, the overhead of SNW routing is smaller than that of ICRP routing when the percentage of selfish nodes is 0.6.

Fig. 3 (d) presents the composite metric on these five routing protocols: Delivery Ratio x (1/ Average Delay) X Goodput, which can reflect the overall performance. It is shown that the IAR-GT scheme outperforms other protocols in terms of the overall performance.

(2) Comparison Results with Increasing Message TTL

In addition, the message TTL can also greatly impact the performance of routing. Hence, we vary the message TTL from 60 minutes to 1800 minutes, while the percentage of selfish nodes is 0.6 and the buffer size is 15M.

Fig. 4 (a) presents the delivery ratio of all protocols with increasing of the message TTL. With increasing of message TTL, more messages can be delivered, and the delivery ratio of all protocols will increase except the Epidemic routing. This is because Epidemic routing exploits a flooding method, and when the nodes are selfish and their resources are limited, the longer the message TTL is, the more serious the message loss will be, hence the delivery ratio of Epidemic routing will decrease. Our incentive aware scheme IAR-GT achieves the highest delivery ratio, because IAR-GT exploits a novel incentive mechanism to stimulate selfish nodes, and limits the message copies. Hence, with the message TTL increasing, the delivery ratio of IAR-GT will increase.

Fig. 4 (b) and Fig. 4 (c) show the average delay and the overhead of the five protocols. From Fig. 4 (b) we can see that the average delay of all protocols will increase with the message TTL, and the Epidemic routing achieves the smallest average delay, followed by IAR-GT routing. On the contrary, the overhead of all protocols will decrease with the message TTL except Epidemic scheme (as shown in Fig. 4 (c)). With increasing of the message TTL, the messages will be carried for a long time and have more chances to be forwarded to the destination. The Epidemic scheme will transmit more quickly due to flooding, but has the largest overhead. However, The IAR-GT scheme considers the factor of message TTL when constructing the price function, hence IAR-GT has the smaller average delay (as shown in Fig. 4 (b)). However, since IAR-GT can efficiently promote selfish nodes to cooperatively forward and so that the number of relayed messages is larger than SNW and ICRP, the overhead of IAR-GT will be larger than the other three protocols (as shown in Fig. 4 (c)). Furthermore, in Fig.4 (c), we can see that when the message TTL is 60 minutes, the overhead of SNW routing is slightly larger than that of ICRP routing, but when the message TTL is larger than 360 minutes, SNW routing achieves the lower overhead than the ICRP routing. This is because ICRP is a two hop relay incentive routing, only source can decide packet relaying, when the message TTL is small (smaller than 60 minutes), the chances that the source forwarding will decrease, so the total number of messages relayed is also smaller than that of the SNW routing. But the delivery ratio of ICRP routing (0.19) is higher than that of the SNW routing (0.16), hence, the overhead of ICRP is smaller than that of SNW. However, with increasing of message TTL (larger than 360 minutes), for ICRP routing, its source will have more chances to forward message, so the total number of messages relayed will increase. SNW does not exploit incentive scheme, which can affects its message relaying under the selfish situation (percentage of selfish nodes is 0.6). Hence, the overhead of ICRP routing is larger than SNW routing when the message TTL is larger than 360 minutes.

Fig. 4 (d) presents the composite metric performance over the routing protocols: Delivery Ratio x(1/ Average Delay)xGoodput. Although the overhead and average delay of IAR-GT scheme is not the smallest of all protocols, the overall performance of the IAR-GT protocol outperforms other protocols.

(3) Comparison Results with Increasing Buffer Size

In this experiment, the buffer size varies from 5M to 50M. Moreover, the percentage of selfish nodes is 0.6, and the message TTL is 1440 minutes.

Fig. 5 (a) presents the delivery ratio of the five protocols with increasing of the buffer size. With increasing of buffer size, nodes may store more messages, and the message delivery ratio will also increase, but when the buffer size is larger than 15M, the delivery ratio of all protocols will become smooth except the Epidemic routing. This is because the total number of created messages is constant, moreover, SNW, ICRP and IAR-GT protocols fix the message copies to 8, and dLifeComm routing is designed based on the users' daily routine. Hence, when the buffer size is larger than 15M, the increasing of buffer size will have little effect on the performance of these four types of routing (dLifeComm, SNW, ICRP, and IAR-GT). But for Epidemic routing, due to the flooding-based forwarding, its delivery ratio will keep increasing with the buffer size. However, it is the best performance for IAR-GT. This is because IAR-GT considers the nodes resources when constructing the bargaining function, and takes the buffer size as a factor for node selfishness.

Fig. 5 (b) and Fig. 5 (c) show the average delay and the overhead of five protocols. From Fig. 5 (b) we can see that the average delay of all protocols will increase smoothly with increasing buffer size, especially when the buffer size is larger than 15M. Our proposed scheme IAR-GT achieves the smaller average delay than the dLifeComm, SNW, and ICRP. On the contrary, the overhead of all protocols are decrease with increasing the buffer size, but Epidemic still has the largest overhead, and it is far larger than the other four scheme's overhead (as shown in Fig. 5 (c)). And the overhead of our scheme IAR-GT is slightly higher than the dLifeComm, SNW, and ICRP.

Fig. 5 (d) presents the comparison results of five protocols in terms of composite metric. From the figure we can see that the overall performance of IAR-GT scheme outperforms other four protocols, i.e., our proposed incentive-aware routing can achieve better performance.

6. Conclusion

In this article, we present an incentive aware routing from a game theory perspective in selfish OPPNETs, which jointly considers two types of selfishness. The proposed scheme contains two parts: an incentive scheme and a forwarding scheme. In the incentive scheme, we propose a novel bargaining game based method, which not only considers the resource utilization of nodes but also considers their social ties, to stimulate nodes' selfish behavior. In the forwarding scheme, we exploit multi-copy routing with limited copies, incorporating an incentive mechanism, so that the messages are forwarded efficiently between selfish nodes. The MIT Reality traces simulation results demonstrate that our scheme IAR-GT performs better than the comparative routing protocols.


[1] L. Pelusi, A. Passarella, and M. Conti, "Opportunistic networking: Data forwarding in disconnected mobile ad hoc networks," IEEE Communication Magazine, vol. 44, no. 11, pp. 134-141, 2006. Article (CrossRef Link)

[2] A. Vahdat and D. Becker, "Epidemic routing for partially connected ad hoc networks," Duke Univ., Durham, NC, USA, Tech. Rep. CS-200006, 2000. Article (CrossRef Link)

[3] A. Lindgren, A. Doria, and O. Schelen, "Probabilistic routing in intermittently connected networks," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 7, no. 3, pp. 19-20, 2003. Article (CrossRef Link)

[4] T. Spyropoulos, K. Psounis, and C. Raghavendra, "Efficient routing in intermittently connected mobile networks: The multiple-copy case," IEEE/ACM Trans. on Networking, vol. 16, no.1, pp: 77-90, 2008. Article (CrossRef Link)

[5] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Efficient routing in intermittently connected mobile networks: The single-copy case," IEEE/ACM Trans. on Networking, vol. 16, no. 1, pp. 63-76, 2008. Article (CrossRef Link)

[6] L. Li, Y. Qin, and X. Zhong, "A novel routing scheme for resource-constraint opportunistic netoworks: A cooperative multi-player bargaining game approach," IEEE Trans. on Vehicular Technology, vol. 65, no. 8, pp: 6547-6561, 2016. Article (CrossRef Link)

[7] W. A. Moreira, P. Mendes, and S. Sargento, "Opportunistic routing based on daily routines," in Proc. IEEE WOWMOM, pp. 1-6, 2012. Article (CrossRef Link)

[8] M. Musolesi and C. Mascolo, "CAR: Context-aware adaptive routing for delay-tolerant mobile networks," IEEE Trans. on Mobile Computing, vol. 8, no. 2, pp. 246-260, 2009. Article (CrossRef Link)

[9] L. Zhou, D. Wu, J. Chen, and Z. Dong, "Greening the smart cities: Energy-efficient massive content delivery via D2D communications," IEEE Trans. on Industrial Informatics, vol.14, no.4, pp: 1626-1634, 2018. Article (CrossRef Link)

[10] L. Zhou, D. Wu, Z. Dong, and X. Li, "When collaboration hugs intelligence: Content delivery over ultra-dense networks," IEEE Communications Magazine, vol. 55, no. 12, pp. 91-95, 2017. Article (CrossRef Link)

[11] Q. Li, S. Zhu, and G. Cao, "Routing in socially selfish delay tolerant networks," in Proc. of IEEE INFOCOM, pp.1-9, 2010. Article (CrossRef Link)

[12] U. Shevade, H. H. Song, L. Qiu, and Y. Zhang, "Incentive-aware routing in DTNs," in Proc. of ICNP, pp. 238-247, 2008. Article (CrossRef Link)

[13] L. Wei, H. Zhu, Z. Cao, and X. Shen, "MobiID: A user-centric and social-aware reputation based incentive scheme for delay/disruption tolerant networks," in Proc. ADHOC-NOW, pp. 177-190, 2011. Article (CrossRef Link)

[14] R. Ciobanu, C. Dobre, M. Dascalu, S. Trausan-Matu V.Cristea, "SENSE: A collaborative selfish node detection and incentive mechanism for opportunistic networks," Journal of Network and Computer Applications, vol. 41, pp. 240-249, 2014. Article (CrossRef Link)

[15] M. Jo, L. Han, D. Kim, H. Peter In, "Selfish attacks and detection in cognitive radio ad-hoc networks," IEEE Network, vol. 27, no.3, pp. 46-50, 2013. Article (CrossRef Link)

[16] H. Zhu, X. Lin, R. Lu, Y. Fan, and X. Shen, "SMART: A secure multilayer credit-based incentive scheme for delay-tolerant networks," IEEE Trans. on Vehicular Technology, vol. 58, no. 8, pp. 4628-4639, 2009. Article (CrossRef Link)

[17] R. Lu, X. Lin, H. Zhu, X. Shen, and B. Preiss, "Pi: A practical incentive protocol for delay tolerant networks," IEEE Trans. on Wireless Communications, vol. 9, no. 4, pp. 1483-1493, 2010. Article (CrossRef Link)

[18] F. Wu, T. Chen, S. Zhong, C. Qiao, and G. Chen, "A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks," IEEE Trans. on Wireless Communications, vol.12, no. 4, pp. 1573 - 1583, 2013. Article (CrossRef Link)

[19] Y. Cai, Y. Fan, D. Wen, "An incentive-compatible routing protocol for two-hop delay-tolerant networks," IEEE Trans. Vehicular Technology, vol. 65, no.1, pp: 266-277, 2016. Article (CrossRef Link)

[20] Y. Li, P. Hui, D. Jin, et al., "Evaluating the impact of social selfishness on the epidemic routing in delay tolerant networks," IEEE Communications Letters, vol. 14, no. 11, pp. 1026- 1028, 2010. Article (CrossRef Link)

[21] B. Jedari, L. Liu, T. Qiu, A. Rahim, F. Xia, "A game-theoretic incentive scheme for social-aware routing in selfish mobile social networks," Future Generation Computer Systems 70:178-190, 2017. Article (CrossRef Link)

[22] P. Sermpezis, T. Spyropoulos, "Understanding the effects of social selfishness on the performance of heterogeneous opportunistic networks," Computer Communications, vol. 48, pp: 71-83, 2014. Article (CrossRef Link)

[23] R. Ariel, "Perfect equilibrium in a bargaining model," Econometrica, vol. 50, no. 1, pp. 97-109, 1982. Article (CrossRef Link)

[24] E. Bulut and B. K. Szymanski, "Exploiting friendship relations for efficient routing in mobile social networks," IEEE Trans. on Parallel and Distributed Systems, vol. 23, no. 12, pp. 2254-2265, 2012. Article (CrossRef Link)

[25] V. Le, Y. Lin, X. Wang, et al., "A cell based dynamic spectrum management scheme with interference mitigation for cognitive network," in Proc. IEEE VTC, 2008, pp. 1594-1598. Article (CrossRef Link)

[26] A. Keranen, The opportunistic network environment simulator, Dept. Commun. Netw., Helsinki Univ. Technol., Espoo, Finland, Special Assignment Rep., May 2008. Article (CrossRef Link)

[27] N. Eagle, A. Pentland, and D. Lazer, "Inferring social network structure using mobile phone data," Proc. Nat'l Academy of Sciences of USA, vol. 106, no. 36, pp. 15274-15278, 2009. Article (CrossRef Link)

[28] CRAWDAD Data Set,, 2012. Article (CrossRef Link)

[29] M. Granovetter, "The strength of weak ties," The American Journal of Sociology, vol. 78, no. 6, 1973. Article (CrossRef Link)

[30] L. Wang, H. Xiong, and D. Zhang, "effSense: Energy-efficient and cost-effective data uploading in mobile crowdsensing," in Proc. ACM UbiComp, pp. 1075-1086, 2013. Article (CrossRef Link)

[31] S. C. Nelson, M. Bakht, and R. Kravets, "Encounter-based routing in DTNs," in Proc. of IEEE INFOCOM 2009, pp. 846-854. Article (CrossRef Link)

Li Li received her Ph.D degree in computer science from Harbin Institute of Technology, China, in 2017. She is currently a postdoctoral fellow with the Graduate School at Shenzhen, Tsinghua University, China. Her research interest is in the area of wireless networks and opportunistic networks.

Xiaoxiong Zhong (S' 12-M'16) received his Ph.D degree in computer science from Harbin Institute of Technology, China, in 2015. He is currently a postdoctoral fellow with the Graduate School at Shenzhen, Tsinghua University, China. His general research interests include mobile edge computing, internet of things and wireless big data.

Yong Jiang received the Ph.D. degree from Tsinghua University in 2002. He is currently a Professor and a Ph.D. supervisor with the Graduate School at Shenzhen, Tsinghua University. He hosted and participated in a lot of national projects, such as 863 Project, 973 Project, and so on. He has authored over 50 papers in top international journals and international conferences. His general research interests include computer network architecture, Internet applications, and Information security.

Li Li (1), Xiaoxiong Zhong (1,2,*), Yong Jiang (1)

(1) Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China

(2) Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China

Email: {lilihitcs, xixzhong},

(*) Corresponding author: Xiaoxiong Zhong

Received January 25, 2018; revised April 10, 2018; accepted May 8, 2018; published January 31, 2019

An earlier version of the works was presented at the 8th IEEE International Conference on Wireless Communications & Signal Processing, WCSP 2016. This work was supported by the National Natural Science Foundation of China (Grant Nos. 61802220, 61802221), the Natural Science Foundation of Guangxi Province under grant 2016GXNSFBA380010, 2017GXNSFAA198192, and the Shenzhen Key Laboratory of Software Defined Networking under No. ZDSYS20140509172959989.
Table 1. Simulation parameters

Parameters         Value

Simulation time    342915 seconds
Message Number     2857
Message Size       0.1M-0.5M randomly
Message creation   120 seconds
Message TTL        60 minutes ~1800 minutes
Node's buffer      5MB ~50MB
Weight factors     [[omega].sub.1] = 0.45, [[omega].sub.2] = 0.55
                   [phi] = 0.5, [[rho].sub.1] = 0.6, [[rho].sub.2] = 0.4
COPYRIGHT 2019 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2019 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Li, Li; Zhong, Xiaoxiong; Jiang, Yong
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Jan 1, 2019
Previous Article:An Optimal Peer Selection Algorithm for Mesh-based Peer-to-Peer Networks.
Next Article:Channel Fading Effect Analysis on Diffusion Cooperation Strategies over Adaptive Networks.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |