Com-BIS: A Community-Based Barter Incentive Scheme in Socially Aware Networking

Abstract

Socially aware networking (SAN) provides a new paradigm for intermittently connected networks which exploits social properties of mobile users to guide the design of protocols. In SAN, data forwarding performance will be degraded dramatically due to the existence of users' selfish behaviors. To address the selfishness problem, barter-based incentive scheme is a fair approach in which two encounter nodes exchange the same amount of data with one another. However, it is a challenging issue for nodes to decide when two nodes contact and how many messages they will exchange for their next contacts. We consider this problem as a resource allocation problem and propose a community-based Barter incentive scheme for SAN paradigm (Com-BIS). In this method, network nodes are grouped into communities and they allocate their forwarding services for different communities optimally using 0-1 knapsack algorithm. The simulation results show that Com-BIS stimulates selfish nodes to cooperate in data delivery for other nodes effectively which improves the forwarding performance considerably.

1. Introduction

Delay tolerant networks (DTNs) enable intermittent connected mobile devices to communicate via short-range networking interfaces such as Bluetooth and WiFi [1, 2]. The broad utilization of mobile devices in our social life brings increasingly close connection between mobile devices and their carriers (human) [3]. Social features of mobile devices such as community, centrality, and similarity, which are more stable than mobility, have been extrapolated to improve the routing and dissemination performance in DTNs [4–6]. As a consequence, socially aware networking (SAN) [7] has emerged as a new paradigm to improve network protocol performance by exploiting social properties of mobile users.

Generally, due to nodes’ mobility, an end-to-end path between source and destination is difficult to maintain [8]. Consequently, nodes usually follow store-carry-and-forward fashion to share data. This means that nodes have to store messages in their buffer and forward them closer and closer to their destination hop by hop. Obviously, the cooperation of nodes is the basic principle in this fashion. However, in reality, nodes usually adopt selfish behavior in order to save limited resources or protect their private information [9–11], which affects the forwarding performance heavily.

In DTNs, nodes have two forms of selfishness: individual selfishness and social selfishness [12]. Nodes with individual selfishness have the same degree of selfishness toward all other nodes while nodes with social selfishness prefer to provide services to others based on their social relationships. For instance, individual selfish nodes do not relay messages even for their friends, whereas social selfish nodes relay messages for those with stronger social ties (i.e., close friends) and refuse to carry messages for strangers.

In order to tackle the selfishness issue, incentive mechanism is necessary to stimulate selfish nodes to cooperate in SAN. Recent incentive mechanisms for DTNs can be classified into four categories: reputation-based, credit-based, game-theoretic, and barter-based [13]. Reputation-based strategy refers nodes’ cooperation behavior as reputation and nodes with low reputation will be punished for their selfishness. Credit-based strategy stimulates nodes to cooperate by awarding virtual credit for message forwarding. Game-theoretic one explores the application of Game Theory to treat selfishness. Barter-based strategy is based on bartering or Tit-For-Tat (TFT) in which two contact nodes exchange the same amount of messages.

In general, a node is willing to forward messages for nodes which can offer same amount of services to itself. From this point of view, barter-based strategy is the most fair and simplest incentive strategy. A selfish node can not get required messages when it does not relay messages for other nodes before. In order to get enough future benefit, nodes will select appropriate messages to carry for other nodes. In this way, nodes’ cooperation consciousness will be stimulated. However, in reality, the routing performance will be degraded dramatically in the case that one of the two nodes has fewer messages. For instance, node A encounters node B and possesses some messages destined to node B. These messages may not be delivered successfully due to the insufficient messages of node B for exchanging. Only if the two nodes have enough and similar number of messages, the higher routing performance will be achieved.

On the other hand, the storage space of mobile node is limited. Hence, in a fixed time period, a node could only provide restricted forwarding services for several nodes due to the limited number of messages stored in space for exchange. To obtain higher performance, a node should select messages for nodes which it can contact in the future in order to increase the exchange probability. However, it is very difficult to predict when two nodes will contact and how many messages they will exchange. What's more, the number of messages exchanged directly between nodes is usually rarely less. Therefore, the routing performance of barter between nodes is not very satisfied.

In a SAN paradigm, nodes are normally grouped into different communities according to their social relationships such as family and classmates. For instance, there are communities constructed by different families. Suppose that a father in a community provides forwarding services for other person in another community. As a return, the person will give similar forwarding services for the father in future. It is reasonable that the father would like to share these services with his family members. Therefore, nodes can manage their forwarding services according to communities [14, 15]. Based on the barter theory, a node gets as many services from a community as the forwarding services it provides for it.

In this paper, we propose the concept of Node-to-Community barter (Node-to-Com barter for simplicity), which considers bartering forwarding services between node and communities [16]. A node makes contribution to a community when it provides forwarding services for nodes in that community, whereas a node gets benefit from a community when it gets forwarding help from nodes in that community. A node balances the contribution and the benefit with a community. The concept of Node-to-Com barter aims at improving the message exchanging probabilities by expanding bartering range.

Following the philosophy of Node-to-Com barter, a barter incentive scheme, called Com-BIS, is presented to stimulate noncooperative nodes for data relaying in community-based SAN. Generally, forwarding services of nodes are limited in a time period. Therefore, how to allocate forwarding resource among communities is a key issue. We model the Com-BIS as a resource optimal allocation problem and obtain approximate optimal solutions using 0-1 knapsack algorithm.

The contributions of this paper are as follows. (i)

To tackle the selfishness issue, we propose the concept of Node-to-Com barter, which exchanges same amount of forwarding services between node and communities. The Node-to-Com barter is beneficial for improving the message exchange probability.

(ii)

We present a community-based barter incentive scheme, called Com-BIS, which is based on Node-to-Com barter. Nodes balance their contribution and benefit among different communities. Com-BIS converts stimulation issue to resource optimal allocation problem and obtains approximate optimal solutions by use of 0-1 knapsack algorithm.

(iii)

We simulate and evaluate the performance of Com-BIS and compare it with Non-Incentive, Social Selfish, and Cooperation mechanisms. The four incentive mechanisms are all based on PROPHET routing algorithm. The results demonstrate that Com-BIS can effectively stimulate selfish nodes to cooperate and improve the routing performance which outperforms other three mechanisms. In addition, we analyze the influence of several impact factors on Com-BIS.

The rest of this paper is organized as follows. An overview of incentive mechanisms, especially barter-based strategies, is presented in Section 2. In Section 3, we introduce resource optimal allocation model in Com-BIS and analyze approximate optimal solution. Then, we give a description of Com-BIS in Section 4 and its implementation is outlined in Section 5. Simulation results are presented in Section 6. The paper is concluded in Section 7.

2. Related Work

Selfishness issue in DTNs has gained much attention recently and a lot of works have been done. The impact of selfishness on the performance of data forwarding protocols is extensively explored [17–19], which demonstrates that the performance is degraded seriously if a part of nodes in the network are selfish. To tackle selfishness issue, various incentive mechanisms have been proposed. An overview on state-of-the-art works on selfishness is presented in [13]. The existing incentive mechanisms can be classified into four categories: reputation-based, credit-based, game-theoretic, and barter-based.

In reputation-based incentive mechanisms, the reputation of a node indicates the belief of other nodes about the cooperation degree of it. Clearly, cooperative nodes have high value of reputation in comparison to noncooperative nodes. IRONMAN [20], for example, utilizes preexisting social network information to detect the selfish nodes. In IRONMAN, the sender of a message keeps the records of the encountered nodes and the forwarding records which contain the identifier of the message, the destination of the message, and the forwarding time. However, the performance of a reputation-based strategy is seriously affected when messages lose.

In credit-based mechanisms, a node receives a certain amount of credits as a reward if it cooperates in message relaying for others and can utilize credits later for its own benefit. Practical incentive (Pi) [21] is a hybrid single-copy protocol which stimulates nodes to cooperate in bundle forwarding using credit-based incentive as well as reputation-based incentive. Ning et al. [22] proposed a credit-based incentive scheme based on the assumptions that data fall into a range of interest types and each node may have multiple interests. Content exchange between two nodes is formulated as a two-person cooperative game and a utility function is created for every node to maximize its expected credit reward. Other well-known credit-based incentive strategies include, for example, [23, 24].

Some researchers have embedded the game-theoretic techniques to stimulate selfish nodes for message relaying. For instance, Wu et al. [25] proposed a game-theoretic approach based on bargaining. This approach is motivated by the observation that message exchange in probabilistic routing is analogous to commodity exchange in markets.

Barter-based incentive mechanisms, also called pair-wise Tit-For-Tat (TFT) strategy, mean that two encounter nodes exchange the same amount of messages. Buttyán et al. [26] presented barter trade strategy to stimulate cooperation of nodes. The messages are divided into two types according to nodes’ interest: primary messages and secondary messages. A message is a primary message for a given node if the node is interested in the content of message. Otherwise, the message is a secondary message for the node. When two nodes are in contact, they select and decide the number of required messages, respectively. Finally, they exchange K messages with each other, where K is the minimum size of the nodes’ required numbers. Thus, a node must relay some number of secondary messages in order to exchange for its primary messages in the future. These barter trade is carried out between nodes. We name this barter strategy as Node-to-Node barter.

Consub [27] is an incentive-based pub/sub scheme which utilizes TFT mechanism to deal with selfish behaviors. Considering the limited storage space, it is a key optimization problem that how nodes should act with TFT mechanism to maximize their own revenues. To answer this question, Consub introduces a content utility to decide the exchange order of content. The content utility is calculated according to contact probability and cooperation level between the current node and neighbors subscribing to this content.

Barter trade strategy and Consub are all presented for data dissemination. A kind of messages may be received by many destination nodes. Therefore, the probability of message exchange between nodes may be higher. In contrast, a message only has one destination in routing scenario. It is uncommon that two encountered nodes happen to have messages destined for each other. Thus, the probability of message exchange between nodes will be degraded largely. Further, the routing performance will be influenced when nodes do not have enough messages to exchange.

Com-BIS is designed for routing scenario with only one destination. In order to increase the message exchanging opportunities, we expand the exchanging range from Node-to-Node barter to Node-to-Com barter, which will improve the exchanging probabilities. In addition, we also take limited storage space into consideration. Com-BIS refers forwarding services as resource and allocates them optimally among communities in order to balance nodes’ contribution and benefit for each community. Recently, more and more researchers utilize social features especially the concept of community to tackle routing and data dissemination issues, as well as in selfishness area. For instance, SSAR [12] utilizes social selfishness to cope with user selfishness and provides good routing performance. Com-BIS is a social based mechanism and allocates forwarding resource according to different social relationships between nodes and communities.

3. Optimal Allocation Model of Com-BIS

In Com-BIS, we suppose that nodes are grouped into several communities according to some social relationship and we do not concern how the communities form. Compared to the huge number of mobile nodes, the information of communities is limited which is easier to maintain. Furthermore, we treat nodes’ forwarding services (forwarding behaviors) as forwarding resource. For a given node, it has limited forwarding resource in a unit time period due to the limited buffer space. Then, how to allocate forwarding resource among different communities in a unit time interval is a key problem which influences the forwarding performance. That is a resource allocation problem.

We illustrate the resource allocation problem with an instance, as shown in Figure 1. Figure 1(a) shows that node A allocates its forwarding resource among four different communities, where red circle represents node A. Figures 1(b)~1(d) illustrate three different allocation strategies, where gray rectangle represents node A's contribution (forwarding services node A provided) and orange rectangle represents node A's benefit (forwarding services node A received). In Figure 1(b), node A adopts complete cooperation strategy and forwards for other nodes when they are needed. Figure 1(c) is the average allocation strategy which allocates the same forwarding services to different communities. Figure 1(d) adopts barter strategy in which node A provides the same amount of forwarding services to a community as it gets from this community. Node A usually has different relationship degrees with different communities; therefore, three allocation strategies achieve different revenues of communities.

Figure 1

Resource optimal allocation model.

Com-BIS barters the forwarding services between node and communities. Node A forwards the same number of messages for nodes in a community as nodes in this community forward for it. Thus, nodes aim at getting maximum benefit with minimum contribution through an optimal allocation strategy. Therefore, Com-BIS can be modelled as resource optimal allocation problem as follows.

A node has K forwarding resource to allocate among N communities. Nodes need to pay for the forwarding services using their own forwarding resource. We introduce Con (contribution) and Ben (benefit) to represent the node's forwarding behavior. A node makes contribution to Community i (denoted as $C o m_{i}$ ) when it provides forwarding services to nodes in $C o m_{i}$ , while a node gets benefit from $C o m_{i}$ when it gets forwarding services from nodes in $C o m_{i}$ .

We assume that, in a unit time interval t, node A gives $C o n_{i} (t)$ contribution to $C o m_{i}$ and gets $B e n_{i} (t)$ benefit from $C o m_{i}$ , where $C o n_{i} (t)$ and $B e n_{i} (t)$ indicate the amount of contribution and benefit, respectively. For the all running time T $(T \in [0, M \times t])$ , the total contribution (resource) node A allocates to $C o m_{i}$ is $\sum_{j = 0}^{M} ‍ C o n_{i} (t_{j})$ ; then, the total resource node A provides to all communities is $\sum_{i = 1}^{N} ‍ \sum_{j = 0}^{M} ‍ C o n_{i} (t_{j})$ . The total benefit node A obtains from $C o m_{i}$ is $\sum_{j = 0}^{M} ‍ B e n_{i} (t_{j})$ ; then, the total benefit node A obtains from all communities is $\sum_{i = 1}^{N} ‍ \sum_{j = 0}^{M} ‍ B e n_{i} (t_{j})$ .

The objective of resource optimal allocation model is to find an allocation strategy with which node can obtain maximum benefit with minimum contribution. For any node, its contribution must be no less than its benefit. Thus, the allocation strategy must satisfy

\begin{array}{l} m a x (\sum_{i = 1}^{N} ‍ \sum_{j = 0}^{M} ‍ B e n_{i} (t_{j})), \\ m i n (\sum_{i = 1}^{N} ‍ \sum_{j = 0}^{M} ‍ C o n_{i} (t_{j})), \\ \sum_{j = 0}^{M} ‍ B e n_{i} (t_{j}) \leq \sum_{j = 0}^{M} ‍ C o n_{i} (t_{j}) \leq K . \end{array}

(1)

Obviously, it is a optimization variant of an NP-completeness. We convert the global optimal problem as local optimal problem; that is, in unit time interval t, allocation strategy must satisfy

\begin{array}{l} m a x (\sum_{i = 1}^{N} ‍ B e n_{i} (t)), \\ m i n (\sum_{i = 1}^{N} ‍ C o n_{i} (t)), \\ B e n_{i} (t) \leq C o n_{i} (t) \leq K . \end{array}

(2)

We can see that if node A adopts selfish behavior, its contribution to any community is 0, and its benefit is 0, too. No other nodes will forward for it, and node A's routing performance may be decreased. However, if node A adopts complete cooperative behavior and provides forwarding services when other nodes need at any time, the performance is also influenced due to unequal relationship degrees of different communities. Therefore, the key problem is to allocate resource appropriately. This optimization problem can be referred to as the following 0-1 knapsack problem, as (3) illustrated:

\begin{array}{l} m a x (\frac{B e n_{i} (t)}{C o n_{i} (t)}), \\ B e n_{i} (t) \leq C o n_{i} (t) \leq K, \end{array}

(3)

where

B e n_{i} (t) / C o n_{i} (t)

is the ratio of benefit and contribution of node for community i in a time interval t, and

B e n_{i} (t) / C o n_{i} (t) \in [0,1]

. Our objective is getting the maximum value of

B e n_{i} (t) / C o n_{i} (t)

. Obviously, when

B e n_{i} (t)

is closer to

C o n_{i} (t)

, the value of

B e n_{i} (t) / C o n_{i} (t)

is bigger. When the number of forwarding resource is not very large, solving such problems is very fast from a computational standpoint [28]. Such a solution is, therefore, suitable to be implemented in resource constrained mobile devices. Additionally, node's contribution

C o n_{i} (t)

and benefit

B e n_{i} (t)

are changed dynamically. We assume a range

[m i n S i z e, m a x S i z e]

for

C o n_{i} (t) - B e n_{i} (t)

and

m i n S i z e > 0

. Node A takes a barter strategy which decides to adopt selfish or cooperation behavior according to current

C o n_{i} (t)

and

B e n_{i} (t)

. The barter strategy is as follows.

(1)

$m i n S i z e \leq C o n_{i} (t) - B e n_{i} (t) \leq m a x S i z e$ . For a community $C o m_{i}$ , if the value of $C o n_{i} (t) - B e n_{i} (t)$ is between minSize and $m a x S i z e$ , the node will continue to allocate resource to $C o m_{i}$ and forward for nodes in $C o m_{i}$ .

(2)

$C o n_{i} (t) - B e n_{i} (t) > m a x S i z e$ . For a community $C o m_{i}$ , if the value of $C o n_{i} (t) - B e n_{i} (t)$ is larger than $m a x S i z e$ , the node's contribution to $C o m_{i}$ is far more than its benefit which represents that the node has allocated enough resource to $C o m_{i}$ . Therefore, the node does not need to allocate any resource to $C o m_{i}$ and refuses to forward for nodes in $C o m_{i}$ .

(3)

$C o n_{i} (t) - B e n_{i} (t) < m i n S i z e$ . For a community $C o m_{i}$ , if the value of $C o n_{i} (t) - B e n_{i} (t)$ is lower than minSize, the node's contribution to $C o m_{i}$ is fewer, which will be punished by nodes in $C o m_{i}$ . Thus, nodes in $C o m_{i}$ will refuse to forward for this node.

4. Com-BIS Incentive Scheme

4.1. Overview of Com-BIS

In Com-BIS, nodes barter with communities for forwarding services. We suppose that nodes constitute several communities according to some social relationships. They maintain tradeoff between contribution and benefit with each community. Every node records its contribution (Con) and benefit (Ben) for communities in a unit time interval. We suppose that all nodes are honest to record the real Con and Ben.

Figure 2 shows an example. Nodes A and B are in contact and need to decide whether to take cooperative behavior or not. Firstly, they exchange their related Con and Ben information. In Figure 2, node A belongs to community 1, while node B belongs to community 2. Thus, they should exchange the Con and Ben information related community 1 and 2, respectively. According to these information, two nodes make a cooperation or selfish decision.

Figure 2

An example of Com-BIS.

From A's perspective, two factors affect A's decision. The first factor is A's Con and Ben related to community 2. Node A can check the current Con and Ben related to community 2 in its buffer and computes the value of $(C o n - B e n)$ . According to the threshold setting of $[m i n S i z e, m a x S i z e]$ ( $[10, 50]$ in Figure 2), A can make a decision. In Figure 2, node A's Con with community 2 is 50, while Ben is 10. The value of $(C o n - B e n)$ is 40 which is lower than maxSize. Therefore, A decides to cooperate for nodes in community 2 (here, node B) from first factor's aspect. The second factor is B's Con and Ben related to community 1. Node A can check the B's Con and Ben related to community 1 from exchanged information and computes the value of $(C o n - B e n)$ . As seen in Figure 2, the value of $(C o n - B e n)$ in B is 2 which is lower than minSize. Thus, node B should be punished for its selfishness. Thus, node A decides to be selfish to node B from second factor's aspect and then refuses to forward for it. Integrating the two factors, node A can make the final decision. That is, node A adopts selfish action for node B in this contact. Similarly, we can analyze that node B will make cooperative decision for node A. In a word, a node takes cooperative action if and only if both factors decide cooperation.

4.2. Architecture of Com-BIS

Figure 3 depicts the architecture and working process of Com-BIS. Com-BIS consists of five components: C&B, Node-to-Com Barter, Node-to-Node Barter, Forwarding Strategy, and C&B Update.

Figure 3

The architecture and work process of Com-BIS.

C&B is a data structure which records node's contribution and benefit associated with each community in current time interval. Every community is mapped to a record with a structure of (Com ID, Con, Ben). Com ID records communities’ ID. Con indicates nodes’ contribution for a community. When a node provides forwarding services for nodes in one community, the corresponding community's Con is increased. Ben indicates nodes’ benefit for a community. When the node gets forwarding help from other nodes in one community, the Ben of corresponding community is increased.

Both Node-to-Com Barter module and Node-to-Node Barter module are barter strategy modules which are responsible for deciding whether to adopt cooperative behavior or not. Node-to-Com Barter is responsible to barter forwarding services between node and communities. The services are treated as contribution or benefit of nodes. In addition, Com-BIS also takes message exchange between nodes into consideration, which is Node-to-Node Barter. For two contact nodes, Node-to-Node Barter exchanges same amount of messages destined to other side directly. Thus, the exchanging services under Node-to-Node Barter are fairly for two node, which will not be included in nodes’ contribution and benefit.

When a node decides to cooperate to forward for others, it is Forwarding Strategy that selects appropriate messages to exchange from message list in order to improve routing efficiency. Many recent utility-based forwarding strategies can be used here. We utilize PROPHET algorithm [29] as forwarding strategy in this paper.

The C&B Update module updates and maintains the information of contribution and benefit of node in current time interval after messages are successfully forwarded.

4.3. Workflow of Com-BIS

As shown in Figure 3, the working process of Com-BIS consists of 6 steps as follows. (1)

When two nodes contact with each other, they exchange their information firstly including node's ID, community, and C&B.

(2)

Then Node-to-Node Barter works and decides the message list between the two nodes according to node's ID.

(3)

Next, Node-to-Com Barter decides whether to adopt cooperative action or not. That is, whether a node forwards messages for the other side.

(4)

If a node decides to adopt cooperate behavior and forward for the other side, it will form forwarding list from message list according to Forwarding Strategy.

(5)

If the forwarding list is not empty, messages in forwarding list will be transmitted.

(6)

Nodes update their contribution and benefit values according to their forwarding services after transmission ends.

5. Implementation of Com-BIS

This section describes the implementation of Com-BIS. Table 1 summarizes the notations for ease of reference.

Table 1

Explanation of notations.

Notation	Explanation
$A, B$	Node A, Node B
$Co m_{A}, Co m_{B}$	Node A's community, Node B's community
$Con (A, Co m_{B})$	Node A's contribution to $Co m_{B}$
$Con (B, Co m_{A})$	Node B's contribution to $Co m_{A}$
$Ben (A, Co m_{B})$	Node A's benefit from $Co m_{B}$
$Ben (B, Co m_{A})$	Node B's benefit from $Co m_{A}$
minSize, maxSize	Threshold to forwarding decision
MSG	Message in message list
$MS G_{SN}$	Message's source node
$MS G_{DN}$	Message's destination node

5.1. Node-to-Node Barter Strategy

In Com-BIS, we take barter strategy between nodes into consideration. Node-to-Node barter strategy is that two contact nodes exchange the same amount of messages directed to the other side. It will improve the successful delivery ratio when messages meet their destination nodes.

For instance, node A and node B meet each other; node A can check the number of messages directed to node B, expressed as $N_{A}$ . Similarly, node B can check the number of messages destined to node A, expressed as $N_{B}$ . Then, A and B can exchange at most $m i n {N_{A}, N_{B}}$ messages. The corresponding number of exchange messages are selected and added into the forwarding list waiting for transmission. The principle of Node-to-Node barter strategy is borrowed from [26].

Obviously, nodes exchange the same amount of forwarding services in Node-to-Node barter. This kind of forwarding behaviors do not need to be included into the contribution and benefit. To distinguish messages exchanged from Node-to-Node barter, a property direct is assigned to message. All messages’ direct is initialized as 0 when they are created. If a message is delivered to its destination through Node-to-Node Barter module, its direct is set as 1. If the message's direct is 1, the C&B Update module will exclude the message from the process.

5.2. Node-to-Com Barter Strategy

Node-to-Com barter strategy balances contribution and benefit between node and communities. Nodes make cooperative or selfish decisions according to their current contribution and benefit associated with the community of other side.

We assume node A belongs to $C o m_{A}$ and node B belongs to $C o m_{B}$ . $C o n (A, C o m_{B})$ and $B e n (A, C o m_{B})$ represent node A's contribution and benefit corresponding to $C o m_{B}$ , while $C o n (B, C o m_{A})$ and $B e n (B, C o m_{A})$ represent node B's contribution and benefit corresponding to $C o m_{A}$ . Node A and B exchange $C o n (A, C o m_{B})$ , $B e n (A, C o m_{B})$ and $C o n (B, C o m_{A})$ , $B e n (B, C o m_{A})$ , respectively, and make decisions according to these information. Without loss of generality, we only describe the decision process from node A's aspect, as the same process happens to B. The minSize and maxSize are the thresholds and the main strategy is as follows. (1)

$C o n (A, C o m_{B}) - B e n (A, C o m_{B}) > m a x S i z e$ . If the value of $C o n (A, C o m_{B}) - B e n (A, C o m_{B})$ is larger than maxSize, the contribution of node A to $C o m_{B}$ is far larger than its benefit, which represents that the node has allocated enough resource to $C o m_{B}$ . In order to guarantee its own benefit, node A will save its forwarding resource and refuse to forward for node B. Thus, node A will make a selfish decision.

(2)

$C o n (A, C o m_{B}) - B e n (A, C o m_{B}) \leq m a x S i z e$ . If the value of $C o n (A, C o m_{B}) - B e n (A, C o m_{B})$ is not larger than maxSize, node A's contribution matches with its benefit. And node A is willing to continue to allocate more forwarding resource to $C o m_{B}$ . In this condition, we need to further consider node B's situation.

(a)

$C o n (B, C o m_{A}) - B e n (B, C o m_{A}) < m i n S i z e$ . If the value of $C o n (B, C o m_{A}) - B e n (B, C o m_{A})$ is lower than minSize, it represents that node B has adopted more selfish behaviours to $C o m_{A}$ . Thus, nodes in $C o m_{A}$ will refuse to forward for node B, which is a punishment strategy for the selfish node. Node A decides to refuse forwarding for node B. Thus, node A will make a selfish decision.

(b)

$C o n (B, C o m_{A}) - B e n (B, C o m_{A}) \geq m i n S i z e$ . If the value of $C o n (B, C o m_{A}) - B e n (B, C o m_{A})$ is not lower than minSize, it represents that node B has adopted more cooperative behaviours to $C o m_{A}$ . Thus, it should get benefit as a return from nodes in $C o m_{A}$ , and node A will make a cooperative decision to forward for node B.

Algorithm 1 illustrates the Node-to-Com barter strategy.

Algorithm 1: Pseudocode of Node-to-Com Barter strategy.

(1) // illustrate from node A's viewpoint

(2) if $Con (A, Co m_{B}) - Ben (A, Co m_{B}) > maxSize$ then

(3) Node A refuses to forward for node B

(4) else

(5) if $Con (B, Co m_{A}) - Ben (B, Co m_{A}) < minSize$ then

(6) Node A refuses to forward for node B

(7) else

(8) Node A forwards for node B

(9) end if

(10) end if

If node A decides to forward for node B according to Node-to-Com barter strategy, it will select forwarding messages from B's message list by using forwarding strategy and add them to the forwarding list. Otherwise, if node A refuses to forward for node B, no messages will be added to the forwarding list. If the forwarding list is not empty, the messages on it will be transmitted one by one.

5.3. C&B Update

After a message is transmitted successfully, nodes will update contribution or benefit according to nodes’ behavior and messages’ property. Obviously, two kinds of messages appear in forwarding list, which are identified by property direct. One kind is selected from Node-to-Com barter strategy with direct of 0, while the other kind is chosen by Node-to-Node barter strategy with direct of 1. Messages selected from Node-to-Node barter strategy will be not included in the process of C&B Update. C&B Update only involves messages chosen by Node-to-Com barter strategy.

Generally, there are three relationships between nodes and messages. That is, a node may be source node, destination node, or intermediate node for a message. We discuss the update process from four different situations according to these relationships. We suppose that node A receives messages and C&B Update module is triggered. Note that, for the received messages, A should not be their source node due to the PROPHET forwarding strategy. (1)

For a message, neither node A nor node B is its source node or destination node. That is, both A and B are intermediate nodes. In this case, node A forwards message for $C o m_{B}$ which implies that A makes contribution to $C o m_{B}$ . Node B gets forwarding help from $C o m_{A}$ which represents that B gets benefit from $C o m_{A}$ . Therefore, $C o n (A, C o m_{B})$ and $B e n (B, C o m_{A})$ will be increased, respectively.

(2)

For a message, node A is an intermediate node and node B is its source node. The update process is similar to (1). $C o n (A, C o m_{B})$ and $B e n (B, C o m_{A})$ will be increased, respectively.

(3)

For a message, node A is the destination node and node B is an intermediate node. In this case, node A obtains the required message and gets benefit from $C o m_{B}$ . While node B provides forwarding service for $C o m_{A}$ . Therefore, $B e n (A, C o m_{B})$ and $C o n (B, C o m_{A})$ will be increased, respectively.

(4)

For a message, node A is the destination node and node B is the source node. Two nodes provide services with each other. The contribution and benefit of them are counteracted. None of them will be increased.

We assign α and β as increment value of contribution and benefit, respectively. That is, contribution is increased by α when forwarding one message for other node, whereas benefit is increased by β when one message forwarded by other node. Algorithm 2 illustrates the process of C&B Update.

Algorithm 2: Pseudocode of C&B Update.

(1) // When node A receives a message MSG

(2) if $MSG . d i r e c t \neq 1$ then

(3) if $A \neq MS G_{DN}$ then

(4) $Con (A, Co m_{B}) = Con (A, Co m_{B}) + α$

(5) $Ben (B, Co m_{A}) = Ben (B, Co m_{A}) + β$

(6) else

(7) if $B \neq MS G_{SN}$ then

(8) $Con (B, Co m_{A}) = Con (B, Co m_{A}) + α$

$(9) Ben(A, Co m_{B}) = Ben (A, Co m_{B}) + β$

(10) end if

(11) end if

(12) end if

6. Evaluation

In this section, we conduct simulations to evaluate the performance of Com-BIS as compared with three other incentive mechanisms. Simulations are carried out to analyze the influence of impact factors on Com-BIS, such as history data of contribution and benefit, threshold, and message generation frequency.

6.1. Simulation Setup

The simulations are carried out in the Opportunistic Network Environment (ONE) simulator [30] based on real trace dataset of INFOCOM2006 [31]. The dataset is collected during IEEE INFOCOM2006. Seventy-eight participants are asked to keep a iMotes with them during the conference period in order to collect the opportunistic contact data and mobility statistics in experiment. Participants are specially selected who belong to four subgroups according to academic affiliations, so we divide nodes of INFOCOM2006 into four communities based on the affiliations. The simulation time is set to 14 hours which is active and continuous time period selected from the dataset.

We compare the performance of Com-BIS with three other mechanisms which are Non-Incentive, Social Selfishness, and Cooperation. All incentive mechanisms adopt PROPHET as forwarding strategy. (i)

Non-Incentive mechanism. Nodes are all selfishness which refuse to forward for any other nodes. That is, there is no incentive mechanism.

(ii)

Social Selfishness incentive mechanism. Nodes are social selfishness which forward for other nodes in same community and refuse to forward for outsiders.

(iii)

Cooperation mechanism. Nodes are willing to forward for all the others. That is, all nodes are cooperative.

We run the simulation 30 times and calculate the average values. Table 2 summarizes the basic simulation parameters.

Table 2

Simulation parameters.

Simulation parameters	Values
Duration period	14 (hour)
Warm up	5000 (second)
Nodes number	78
Wait time at destination	100~200 (second)
Interface type	Blue tooth
Transmit speed	250 KB
Transmit range	10 m
Moment model	External movement
DataSet	INFOCOM2006
Event interval	20~200
Message size	500~1024
Message TTL	5 (hour)
Nodes' buffer	10 (M)
minSize	0
maxSize	10
α	2
β	1

In each simulation, we compare the protocols based on the following four metrics. (i)

Delivery Ratio: the ratio of successfully delivered messages to the total number of unique messages created (with the redundant messages excluded) in a given period.

(ii)

Overhead: the ratio of relayed messages (delivered messages excluded) and delivered messages, reflecting the ratio of message replicas propagated into the network.

(iii)

Average Latency: the average time between the time a message is generated and the time it is delivered successfully (including buffering delays).

(iv)

Average Hop Count: the average hop-counts when messages are received successfully.

6.2. Performance Comparison

6.2.1. Efficiency

Figure 4 shows the efficiency comparison of four incentive mechanisms under different simulation times. It consists of 4 subfigures which represent performance comparison from delivery ratio, overhead, average latency, and average hop count, respectively. From Figure 4, we can see that Com-BIS outperforms other three mechanisms with higher delivery ratio, less overhead, shorter average latency, and more average hop count.

Figure 4

Performance comparison of four incentive mechanisms.

For the delivery ratio in Figure 4(a), Com-BIS is higher than other mechanisms. For instance, at the 8th hour, the delivery ratio of Com-BIS is 84.9%, which is 2.7% higher than Cooperation (82.2), 13.9% higher than Social Selfishness (71%), and 28.9% higher than Non-Incentive (56%). In Non-Incentive, nodes deliver messages by themselves. When the source node contacts destination node, the message will be delivered successfully. It's delivery ratio is lowest. In Social Selfishness mechanism, there are parts of nodes participating in forwarding (in community). Therefore, its delivery ratio is higher than Non-Incentive mechanism. Cooperation mechanism in which all nodes are cooperative induces higher delivery ratio than Non-Incentive and Social Selfishness incentive mechanisms. However, message replications will be increased when nodes help forward for others, which causes higher overhead. Further more, the network congestion will be serious, which degrades the forwarding performance.

On the contrary, in Com-BIS, nodes do not take blind cooperation strategy, but take optimal allocation strategy according to social relationships between nodes and communities by using Node-to-Com barter strategy. Com-BIS provides effective cooperation for messages which have more successful delivery probabilities and improves resource utilization. Consequently, Com-BIS allocates the forwarding resource effectively and obtains highest delivery ratio.

For the overhead in Figure 4(b), Cooperation mechanism generates highest overhead followed by Com-BIS, Social Selfishness, and Non-Incentive mechanism. Non-Incentive mechanism does not generate any message copies and gets lowest overhead (0). For instance at the 6th hour, Com-BIS generates highest overhead (49.2), which is still 4.2 lower than Cooperation (53.4), 34.9 higher than Social Selfishness (14.3), and 49.2 higher than Non-Incentive.

For average latency Figure 4(c), Com-BIS and Cooperation are similar, and both of them are shorter than Social Selfishness and Non-Incentive. The average latency of Social Selfishness is higher than Non-Incentive.

Non-Incentive delivers the least number of messages and these few successful ones are delivered through one-hop transmission, whereas the higher message delivery ratio in Social Selfishness is implemented by multihop transmission due to part cooperation. Therefore, the average latency of Non-Incentive is shorter than Social Selfishness.

For average hop count in Figure 4(d), Com-BIS has more hop counts than other three mechanisms. At the 10th hour, the average hop count of Com-BIS is 4.3, while Cooperation, Social selfishness, and Non-Incentive are 4, 2.2, and 1, respectively. On the forwarding path, it is the Com-BIS that has the most number of intermediate nodes, which means that more nodes take cooperative behaviors to participate in message forwarding.

In a word, Com-BIS not only stimulates selfish nodes to cooperate successfully, but also allocates the forwarding resource rationally, which improves the forwarding performance effectively.

6.2.2. C&B Value Analysis

In order to trace and analyze the changing of contribution and benefit value, we record the history value of $\sum_{j = 0}^{M} ‍ (C o n_{i} (t_{j}) - B e n_{i} (t_{j}))$ for different communities. Figure 5 shows the value changing curves of Node 2 and Node 22. Four communities are represented as community 1~community 4, respectively. Both of Node 2 and Node 22 belong to community 1. As we can see, two nodes have different closeness of relationships with community 1~community 4. Node 2 has closer relationships with communities 1 and 3, while Node 22 more closely relates to communities 3 and 2. It is proved again that optimal allocation of forwarding resource is very necessary to stimulate nodes’ selfish behaviors and improve forwarding performance.

Figure 5

History accumulation of C&B in Node 2 and 22.

6.3. Influences of Impact Factors

6.3.1. Influence of History Data

In previous simulations, we only consider node's contribution and benefit in current time interval and exclude the impact of history data. In a new time interval; the new round of balance starts and the remaining values of last time interval are ignored. To evaluate the impact of history contribution and benefit, we perform a set of simulations. The Node-to-Com barter strategy is decided by jointing history value and current value, as illustrate by (4), where γ is an efficient factor which decides the current values’ influence. We set γ to 0.5, 0.7, and 1 in simulations:

\begin{matrix} C o n (t) = C o n_{c u r} (t) \times γ + C o n_{h i s t o r y} (t) \times (1 - γ), \\ B e n (t) = B e n_{c u r} (t) \times γ + B e n_{h i s t o r y} (t) \times (1 - γ) . \end{matrix}

(4)

The results are shown in Figure 6. The performance of Com-BIS is improved with the increasing of γ. When γ is 1, Com-BIS obtains highest delivery ratio, shortest average latency, and most number of average hop counts. For instance, at 8th hour in Figure 6(a), the delivery ratio of Com-BIS with 1 is 84.9% which is higher than 0.5 (73.2%) and 0.7 (74.9%). In Figure 6(c) at same hour, the average latency of Com-BIS with 1 is 730 s which is shorter than 0.5 (974) and 0.7 (843). While in Figure 6(d), the average hop count of Com-BIS with 1 is 4 which is more than 0.5 (2.9) and 0.7 (3.2). However, the overhead of Com-BIS with 1 is slightly higher than that of 0.5 and 0.7. At 8th hour in Figure 6(b), the overhead of of Com-BIS with 1 is 47.8 while those of Com-BIS with 0.5 and 0.7 are 31 and 37.6, respectively. We can see that history data degrades the performance of Com-BIS.

Figure 6

Impact of history contribution and benefit on Com-BIS.

6.3.2. Influence of Threshold

Figure 7 shows the impact on Com-BIS of threshold $[m i n S i z e, m a x S i z e]$ . We set four different thresholds which are $[0 – 5], [0 – 10], [10 – 20]$ and $[20 – 30]$ , respectively. In addition, we use Non-Incentive for comparison. As shown in Figure 7, the performances of Com-BIS with four different thresholds are all better than Non-Incentive mechanism. Com-BIS with $[0 – 5]$ is similar to $[0 – 10]$ , both of which achieve better performance than $[10 – 20]$ and $[20 – 30]$ . Settings $[10 – 20]$ and $[20 – 30]$ obtain similar performance. For instance, at the 8th hour in Figure 7(a), the delivery ratios of $[0 – 5], [0 – 10], [10 – 20]$ , and $[20 – 30]$ are 84.7%, 84.9%, 69.8%, and 70.6%, respectively, while Non-Incentive is 56%. The overhead of $[0 – 5], [0 – 10], [10 – 20]$ , and $[20 – 30]$ are 47.6, 47.8, 14, and 13.4, as Figure 7(b) has shown. The average latency of $[0 – 5], [0 – 10], [10 – 20]$ , and $[20 – 30]$ is 734.7 s, 730.3 s, 1281.5 s, and 1314.6 in Figure 7(c). In Figure 7(d), we can see that the average hop count of $[0 – 5], [0 – 10], [10 – 20]$ , and $[20 – 30]$ is 3.9, 4.0, 2, and 2, respectively.

Figure 7

Impact of threshold on Com-BIS.

In situations with threshold of $[0 – 5]$ and $[0 – 10]$ , the number of nodes’ benefit is close to their contribution. Therefore, the ratio of benefit and contribution is close to 1 which obtains approximate optimal solution. Compared to $[0 – 5]$ and $[0 – 10]$ , in situations of $[10 – 20]$ and $[20 – 30]$ , nodes are cooperative only if the number of contribution is far larger than benefit. Thus, nodes’ cooperations are limited and lower performances are obtained.

6.3.3. Influence of Message Generation Frequency

We evaluate the impact of Com-BIS with different message generation frequencies which are 20–40 seconds, 50–70 seconds, 100–120 seconds, 180–200 seconds, and 100–200 seconds, respectively. The smaller the message generation frequency, the more messages will be generated in network. Figure 8 shows the simulation results. We have seen that the performance of Com-BIS degrades with the increasing number of messages. The reason is that huge number of messages increase the buffer replacement and decrease the time nodes carried, which decreases the delivery opportunities. For example, at the 10th hour in Figure 8(a), the delivery ratio of 180–200 is highest with 87.2%, followed by 100–200 (82.24%), 100–120 (77.5%), 50–70 (65.6%), and 20–40 (57.7%). In Figure 8(b), the overhead of 180–200 is 50.2 which is higher than 100–200 (48), 100–120 (43.2), 50–70 (38.4), and 20–40 (29.7). In Figure 8(c), the average latency of 180–200 is 854 s, while 100–200 is 873 s, 100–120 is 762 s, 50–70 is 618.5 s, and 20–40 is 486.8. In Figure 8(d), the average hop count follows the similar changing tendency. The average hop count of 180–200 is 4.1 which is fewer than 100–200 (4.3) and more than 100–120 (3.8), 50–70 (3.2), and 20–40 (2.7).

Figure 8

Impact of message generation frequency on Com-BIS.

7. Conclusion

In this paper, we have presented a community-based barter incentive scheme for SAN paradigm (Com-BIS) which barters forwarding services between nodes and communities. A node makes contribution to a community when it provides forwarding services for nodes in this community, whereas a node obtains benefit from a community when it gets forwarding services from nodes in this community. Nodes balance their contribution and benefit with communities and allocate forwarding services optimally to communities by using 0-1 knapsack algorithm. The simulation results demonstrate that Com-BIS not only stimulates selfish nodes to cooperate in data delivery for other nodes effectively but also improves the forwarding performance considerably.

In this paper, we discuss Com-BIS in routing scenario and concentrate on the relationships between two contact nodes and messages. In future work, we will continue to examine the efficiency of Com-BIS in data dissemination scenario.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was partially supported by the Foundation of Key Laboratory of System Control and Information Processing, Ministry of Education, China, under Grant no. SCIP2012001 and the Liaoning Provincial Natural Science Foundation of China under Grant no. 201202032.

References

Goncharov

Delay-Tolerant Networks 2010

Lehrstuhl für Rechnernetze und Telematik, Institut für Informatik, Albert-Ludwigs-Universität Freiburg

Khabbaz

M. J.

Assi

C. M.

Fawaz

W. F.

Disruption-tolerant networking: a comprehensive survey on recent developments and persisting challenges

IEEE Communications Surveys and Tutorials 2012 14 2 607 640

10.1109/SURV.2011.041911.00093

2-s2.0-84860886202

Guo

Zhang

Wang

Zhou

Opportunistic IoT: exploring the harmonious interaction between human and the internet of things

Journal of Network and Computer Applications 2013 36 6 1531 1539

10.1016/j.jnca.2012.12.028

2-s2.0-84873054229

Xia

Ahmed

A. M.

Yang

L. T.

Rodrigues

Exploiting social relationship to enable efficient replica al location in ad-hoc social networks

IEEE Transactions on Parallel and Distributed Systems 2014

10.1109/TPDS.2013.2295805

Liaqat

H. B.

Xia

Yang

L. T.

Ahmed

A. M.

Asabere

N. Y.

Social-similarity-aware TCP with collision avoidance in ad hoc social networks

IEEE Systems Journal 2014 99 1 12

10.1109/JSYST.2014.2305191

Zhang

Guo

The emergence of social and community intelligence

Computer 2011 44 7 21 28

10.1109/MC.2011.65

2-s2.0-79960927340

Xia

Liu

Vasilakos

A. V.

Socially aware networking: a survey

IEEE Systems Journal 2013

10.1109/JSYST.2013.2281262

Gani

Nayeem

G. M.

Shiraz

Sookhak

Whaiduzzaman

Khan

A review on interworking and mobility techniques for seamless connectivity in mobile cloud computing

Journal of Network and Computer Applications 2014 43 84 102

10.1016/j.jnca.2014.04.009

Gong

Zhang

Social contribution-based routing protocol for vehicular network with selfish nodes

International Journal of Distributed Sensor Networks 2014 2014 12

753024

10.1155/2014/753024

10.

Bao

Tang

Optimal control of epidemic routing in delay tolerant networks with selfish behaviors

International Journal of Distributed Sensor Networks 2014 2014 10

680197

10.1155/2014/680197

11.

Zhu

Shi

Wang

A survey of social-based routing in delay tolerant networks: positive and negative social effects

IEEE Communications Surveys and Tutorials 2013 15 1 387 401

10.1109/surv.2012.032612.00004

2-s2.0-84873732697

12.

Gao

Zhu

Cao

A routing protocol for socially selfish delay tolerant networks

Ad Hoc Networks 2012 10 8 1619 1632

10.1016/j.adhoc.2011.07.007

2-s2.0-84863369462

13.

Miao

Hasan

Mokhtar

S. B.

Brunie

Yim

An investigation on the unwillingness of nodes to participate in mobile delay tolerant network routing

International Journal of Information Management 2012 33 252 226

10.1016/j.ijinfomgt.2012.11.001

2-s2.0-84871434084

14.

Xia

Ahmed

A. M.

Yang

L. T.

Luo

Community-based event dissemination with optimal load balancing

IEEE Transactions on Computers 2014

10.1109/TC.2014.2345409

15.

Xia

Liu

Ahmed

A. M.

Yang

L. T.

Beeinfo: an interest-based forwarding scheme using artificial bee colony for sociallyaware networking

IEEE Transactions on Vehicular Technology 2014

10.1109/TVT.2014.2305192

16.

Xia

Yang

Liu

Qiu

Chen

Cis: a communitybased incentive scheme for socially-aware networking

Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′14)

August 2014

Philadelphia, Pa, USA

ACM

17.

Wang

Evaluating the effects of node cooperation on DTN routing

AEU-International Journal of Electronics and Communications 2012 66 1 62 67

10.1016/j.aeue.2011.05.001

2-s2.0-81155152700

18.

Keränen

Pitkänen

Vuori

Ott

Effect of non-cooperative nodes in mobile DTNs

Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM ′11)

June 2011

1 7

10.1109/WoWMoM.2011.5986144

2-s2.0-80052765349

19.

D. O.

Jin

Zeng

The impact of node selfishness on multicasting in delay tolerant networks

IEEE Transactions on Vehicular Technology 2011 60 5 2224 2238

10.1109/TVT.2011.2149552

2-s2.0-79959276613

20.

Bigwood

Henderson

IRONMAN: using social networks to add incentives and reputation to opportunistic networks

Proceedings of the IEEE 3rd International Conference on Social Computing (SocialCom ′11)

October 2011

Boston, Mass, USA

65 72

10.1109/PASSAT/SocialCom.2011.60

2-s2.0-84856137651

21.

Lin

Zhu

Shen

Preiss

Pi: a practical incentive protocol for delay tolerant networks

IEEE Transactions on Wireless Communications 2010 9 4 1483 1493

10.1109/TWC.2010.04.090557

2-s2.0-77951292577

22.

Ning

Yang

Xie

Incentive-aware data dissemination in delay-tolerant mobile networks

Proceedings of the 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '11)

June 2011

539 547

10.1109/SAHCN.2011.5984940

2-s2.0-80052804290

23.

Chen

B. B.

Chan

M. C.

MobiCent: a credit-based incentive system for disruption tolerant network

Proceedings of the 2010 IEEE INFOCOM

March 2010

1 9

10.1109/INFCOM.2010.5462136

2-s2.0-77953298005

24.

Ning

Yang

Han

Self-interest-driven incentives for ad dissemination in autonomous mobile social networks

Proceedings of the IEEE INFOCOM

2013

2310 2318

25.

Chen

Zhong

Qiao

Chen

A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks

IEEE Transactions on Wireless Communications 2013 12 4 1573 1583

10.1109/TWC.2013.022113.120282

2-s2.0-84877735772

26.

Buttyán

Dóra

Félegyhazi

Vajda

Barter trade improves message delivery in opportunistic networks

Ad Hoc Networks 2010 8 1 1 14

27.

Zhou

Chen

Fan

Das

S. K.

ConSub: incentive-based content subscribing in selfish opportunistic mobile networks

IEEE Journal on Selected Areas in Communications 2013 31 9 669 679

10.1109/JSAC.2013.SUP.0513058

2-s2.0-84883353197

28.

Kellerer

Pferschy

Pisinger

Knapsack Problems 2004

Springer

10.1007/978-3-540-24777-7

MR2161720

29.

Lindgren

Doria

Schelén

Probabilistic routing in intermittently connected networks

ACM SIGMOBILE Mobile Computing and Communications Review 2003 7 3 19 20

10.1145/961268.961272

30.

Keränen

Kärkkäinen

Ott

Simulating mobility and DTNs with the one

Journal of Communications 2010 5 2 92 105

10.4304/jcm.5.2.92-105

2-s2.0-78651570092

31.

Scott

Gass

Crowcroft

Hui

Diot

Chaintreau

CRAWDAD trace cambridge/haggle/imote/infocom2006 (v. 2009-05-29)

2009, http://crawdad.org/cambridge/haggle/